कनेक्टेड-कंपोनेंट लेबलिंग (CCL), जिसे कनेक्टेड-कंपोनेंट विश्लेषण, ब्लॉब निष्कर्षण, क्षेत्र लेबलिंग, या ब्लॉब खोज के रूप में भी जाना जाता है, ग्राफ सिद्धांत का एक एल्गोरिथ्मिक अनुप्रयोग है जिसमें कनेक्टेड कंपोनेंट्स के उपसमुच्चय को दिए गए अनुमानी के आधार पर विशिष्ट रूप से लेबल किया जाता है। इसका उपयोग कंप्यूटर विज़न में बाइनरी डिजिटल छवियों में कनेक्टेड क्षेत्रों का पता लगाने के लिए किया जाता है, हालांकि रंगीन छवियों और उच्च-आयामी डेटा को भी संसाधित किया जा सकता है। CCL, छवि विभाजन से अलग है, और ब्लॉब निष्कर्षण, ब्लॉब पहचान से संबंधित लेकिन भिन्न है।
व्यवहार में, CCL इनपुट डेटा से निर्मित ग्राफ पर संचालित होता है, जहां शीर्ष पिक्सेल या तत्वों का प्रतिनिधित्व करते हैं और किनारे पड़ोसियों के बीच कनेक्टिविटी का संकेत देते हैं। एक एल्गोरिद्म ग्राफ को पार करता है, कनेक्टिविटी और सापेक्ष मूल्यों के आधार पर शीर्षों को लेबल निर्दिष्ट करता है। लेबलिंग के बाद, ग्राफ को उपसमुच्चय में विभाजित किया जा सकता है, जिससे मूल जानकारी को पुनर्प्राप्त और संसाधित किया जा सकता है, जैसे कि ब्लॉब्स की गिनती, फ़िल्टरिंग, और ट्रैकिंग जैसे कार्यों के लिए।
परिभाषा और शब्दावली
शब्द कनेक्टेड-कंपोनेंट लेबलिंग शैक्षणिक साहित्य में लगातार उपयोग किया जाता है, जबकि कनेक्टेड-कंपोनेंट विश्लेषण (CCA) शब्दावली और समस्या परिभाषा दोनों में भिन्न होता है। रोसेनफेल्ड एट अल. CCL को एक लेबल की गई छवि के निर्माण के रूप में परिभाषित करते हैं जिसमें बाइनरी इनपुट छवि के समान कनेक्टेड कंपोनेंट से जुड़े स्थानों का एक अद्वितीय लेबल होता है। शापिरो एट अल. CCL को एक ऑपरेटर के रूप में वर्णित करते हैं जिसका इनपुट एक बाइनरी छवि है और आउटपुट एक प्रतीकात्मक छवि है जहां प्रत्येक पिक्सेल का लेबल एक पूर्णांक है जो विशिष्ट रूप से इसके कनेक्टेड कंपोनेंट की पहचान करता है।
CCA की परिभाषा पर कोई सहमति नहीं है; इसे अक्सर CCL के साथ परस्पर उपयोग किया जाता है। शापिरो एट अल. द्वारा एक अधिक व्यापक परिभाषा बताती है कि CCA में काले पिक्सेल की कनेक्टेड-कंपोनेंट लेबलिंग, उसके बाद कंपोनेंट क्षेत्रों की संपत्ति माप और निर्णय लेना शामिल है। यह लेख एक व्यापक व्याख्या अपनाता है जो इन दृष्टिकोणों को शामिल करता है।
ग्राफ निर्माण और कनेक्टिविटी
प्रासंगिक इनपुट डेटा से एक ग्राफ बनाया जाता है, जिसमें शीर्ष तुलना अनुमानी के लिए आवश्यक जानकारी रखते हैं और किनारे कनेक्टेड पड़ोसियों को इंगित करते हैं। एल्गोरिद्म ग्राफ को पार करता है, कनेक्टिविटी और सापेक्ष मूल्यों के आधार पर शीर्षों को लेबल करता है। कनेक्टिविटी माध्यम द्वारा निर्धारित होती है; छवि ग्राफ के लिए, सामान्य पड़ोस में 4-कनेक्टेड (उत्तर, दक्षिण, पूर्व, पश्चिम) और 8-कनेक्टेड (विकर्ण सहित) शामिल हैं।
लेबलिंग के बाद, ग्राफ को उपसमुच्चय में विभाजित किया जा सकता है, जिसके बाद मूल जानकारी को पुनर्प्राप्त और संसाधित किया जा सकता है। यह दृष्टिकोण मनमाने आयामों के लिए सामान्यीकृत होता है, हालांकि समय और स्थान जटिलता तदनुसार बढ़ जाती है।
एक समय में एक कंपोनेंट एल्गोरिद्म
एक-समय-में-एक-कंपोनेंट एल्गोरिद्म तेज़, लागू करने में सरल है, और ग्राफ ट्रैवर्सल विधियों पर आधारित है। यह विंसेंट और सोइल के वाटरशेड विभाजन एल्गोरिद्म का हिस्सा है, जिसमें अन्य कार्यान्वयन भी मौजूद हैं। विधि कनेक्टेड पिक्सेल के सूचकांक रखने के लिए एक लिंक्ड सूची का उपयोग करती है, जिसमें गहराई-पहले या चौड़ाई-पहले खोज का चुनाव इस अनुप्रयोग के लिए व्यावहारिक अंतर नहीं रखता है।
एल्गोरिद्म एक बाइनरी छवि मानता है जिसमें अग्रभूमि और पृष्ठभूमि पिक्सेल होते हैं, जिसका उद्देश्य अग्रभूमि में कनेक्टेड कंपोनेंट्स को लेबल करना है। चरण:
- पहले पिक्सेल से शुरू करें, वर्तमान लेबल को 1 पर सेट करें।
- यदि पिक्सेल अग्रभूमि है और अलेबल है, तो वर्तमान लेबल निर्दिष्ट करें और इसे कतार में जोड़ें; अन्यथा, अगले पिक्सेल पर जाएं।
- कतार से एक तत्व निकालें, इसके पड़ोसियों की जांच करें (कनेक्टिविटी प्रकार के आधार पर)। यदि कोई पड़ोसी अग्रभूमि और अलेबल है, तो वर्तमान लेबल निर्दिष्ट करें और इसे कतार में जोड़ें। कतार खाली होने तक दोहराएं।
- अगले पिक्सेल पर जाएं और वर्तमान लेबल बढ़ाएं।
पिक्सेल को कतार में जोड़ने से पहले लेबल किया जाता है, और प्रत्येक अग्रभूमि पिक्सेल के पड़ोसियों की केवल एक बार जांच की जाती है; पृष्ठभूमि पिक्सेल के पड़ोसियों की जांच नहीं की जाती है। स्यूडोकोड पिक्सेल प्रसंस्करण को प्रबंधित करने के लिए दो कतारों का उपयोग करता है, जिससे कुशल ट्रैवर्सल सुनिश्चित होता है।
कंप्यूटर विज़न में अनुप्रयोग
CCL का व्यापक रूप से कंप्यूटर विज़न में बाइनरी छवियों में कनेक्टेड क्षेत्रों का पता लगाने के लिए उपयोग किया जाता है, अक्सर थ्रेशोल्डिंग चरण के बाद। ब्लॉब निष्कर्षण को ग्रे-स्केल और रंगीन छवियों पर भी लागू किया जा सकता है। ब्लॉब्स को गिना, फ़िल्टर किया और ट्रैक किया जा सकता है, जिससे CCL छवि पहचान प्रणालियों और मानव-कंप्यूटर इंटरैक्शन इंटरफेस में मूल्यवान बन जाता है।
उदाहरण के लिए, Machine learning पाइपलाइनों में, CCL ऑब्जेक्ट डिटेक्शन या विभाजन कार्यों के लिए छवियों को पूर्व-संसाधित कर सकता है, जैसे U-Net आर्किटेक्चर जैसी तकनीकों का पूरक। इसका उपयोग Artificial intelligence प्रणालियों में चिकित्सा छवियों, औद्योगिक निरीक्षण, और स्वायत्त ड्राइविंग के विश्लेषण के लिए भी किया जाता है, जहां कनेक्टेड क्षेत्रों की पहचान महत्वपूर्ण है।
संबंधित अवधारणाएं और विस्तार
CCL, ब्लॉब पहचान से संबंधित लेकिन अलग है, जो तीव्रता भिन्नताओं के आधार पर रुचि के क्षेत्रों की पहचान पर केंद्रित है। इसके विपरीत, CCL कनेक्टिविटी के आधार पर सभी कनेक्टेड कंपोनेंट्स को लेबल करता है। एल्गोरिद्म को उच्च-आयामी डेटा, जैसे चिकित्सा इमेजिंग में 3D वॉल्यूम, तक बढ़ाया जा सकता है, जिसमें बढ़ी हुई कम्प्यूटेशनल लागत होती है।
Deep learning और Neural network मॉडल में हालिया प्रगति ने विभाजन के लिए सीखे गए दृष्टिकोणों को जन्म दिया है, लेकिन CCL पोस्ट-प्रोसेसिंग और विश्लेषण के लिए एक मौलिक उपकरण बना हुआ है। इसकी सरलता और दक्षता इसे कंप्यूटर विज़न लाइब्रेरी और फ्रेमवर्क में एक प्रमुख उपकरण बनाती है, जिसे अक्सर प्रशिक्षण पाइपलाइनों में Data Augmentation और Loss Functions के साथ संयोजन में उपयोग किया जाता है।
यह भी देखें
- कंप्यूटर विज़न
- छवि विभाजन
- ब्लॉब पहचान
- ग्राफ सिद्धांत