कनेक्ट किए गए घटक लेबलिंग में डिसजॉइंट सेट का उपयोग कैसे करें?

Question

मुझे कनेक्टेड घटक लेबलिंग में डिसजॉइंट सेट का उपयोग करने में कुछ कठिन समय है। मैंने कई उदाहरणों और this question पर भी देखा है जहां Bo Tian ने सी ++ लिंक्ड सूची के रूप में डिसजॉइंट सेट का बहुत अच्छा कार्यान्वयन प्रदान किया है। मैंने अपने प्रोग्राम में कनेक्टेड घटक लेबलिंग (लेबल्स सरल पूर्णांक) को पहले से ही कार्यान्वित कर दिया है, लेकिन मुझे असंगत सेट वाले लेबलों के बीच समकक्षों को हल करने में वास्तव में कठिन समय है।

क्या कोई मुझे उस पर मदद कर सकता है - शायद बो टियां के कार्यान्वयन का उपयोग कर? मुझे लगता है कि जब वे इस बिंदु पर आते हैं तो दूसरों की भी मदद करेंगे।

संपादित

मेरे एल्गोरिथ्म छवि के माध्यम से चला जाता है और जब यह दो लेबल भिन्न लेबल वाली दो जुड़े पिक्सल पाता है यह तुल्यता रजिस्ट्री 'में एक नोट बनाने के लिए है (जुदा वन सेट होगा जो) । पूरी छवि को लूप करने के बाद मुझे रजिस्ट्री को देखकर (छवि पर दूसरे पास जाने) द्वारा समकक्षों को हल करना होगा और फिर इन पिक्सल को चिह्नित करना होगा जिनके पास सेट के न्यूनतम से बराबर लेबल हैं।

Answer 1

यह tutorial on DJS देखें। केवल संशोधन यह है कि संघ के दौरान आपको अधिक से कम कनेक्ट करना होगा, इसलिए रूट हमेशा सेट का न्यूनतम होता है।

Answer 2

संबंध तोड़ना सेट जंगल की आपूर्ति दो आपरेशन:

• संघ है, जो दो वस्तुओं लेता है और उन्हें लिंक होता है और
• का पता लगाएं, जो समूह की दो वस्तुओं लेता है और आईडी रिटर्न वे अंदर हैं।

डिजॉइंट-सेट वन मुख्य रूप से विभिन्न समूहों के परिवार में वस्तुओं के समूह के विभाजन को बनाए रखने के लिए उपयोग किए जाते हैं, जिनमें से प्रत्येक डिस्प्ले है दूसरे से संयुक्त (यानी, प्रत्येक वस्तु एक समूह में है)। डिज्जॉइंट-सेट वन आपको प्रत्येक ऑब्जेक्ट के लिए क्लस्टर आईडी निर्धारित करने के लिए कुशलतापूर्वक बताता है कि प्रत्येक समूह में कौन सी ऑब्जेक्ट्स हैं, या (लगभग ओ (एन) समय में)।

एक पृथक सेट वन का उपयोग करने के लिए, आप प्रत्येक ऑब्जेक्ट को अपने क्लस्टर में डालकर शुरू करेंगे। उस बिंदु से आगे, हर बार जब आप दो अलग-अलग ऑब्जेक्ट्स को चिह्नित करना चाहते थे, उसी क्लस्टर में होते हैं, तो आप उन्हें यूनियन ऑपरेशन का उपयोग एक साथ जोड़ने के लिए करेंगे। अंत में, आप पर प्रत्येक बिंदु पर को यह निर्धारित करने के लिए कॉल करेंगे कि यह कौन सा क्लस्टर है, और वहां से यह पता चल सकता है कि कौन सा समूह सब कुछ संबंधित है।

आशा है कि इससे मदद मिलती है!

Answer 3

आप सही हैं, कनेक्टेड सेट लेबलिंग केवल आधा काम किया जाता है। समकक्षों का उपयोग करके पृथक सेट ढूंढना भी उतना ही कठिन हिस्सा है। मुझे सटीक परिदृश्य का सामना करना पड़ा।

संघ-खोज एल्गोरिदम का उपयोग करके डिसजॉइंट सेट (लेबलिंग के बाद) ढूंढने का एक तरीका है। निम्नलिखित आलेख देखें। आप स्क्रैच से समझेंगे कि लेबलिंग और डिज्जॉइंट सेट को कैसे कार्यान्वित किया जाता है। नमूना इनपुट और आउटपुट matrices के साथ चित्र भी दिए जाते हैं।

http://www.codeding.com/articles/connected-sets-labeling

Answer 4

असंबंधित समूह के साथ जुड़े घटक लेबलिंग बारे में एक ब्लॉग है:

http://www.keithlantz.net/2011/04/c-implementation-of-the-connected-component-labeling-method-using-the-disjoint-set-data-structure/