2012-12-18 23 views
6

में सुपरपिक्सेल के पड़ोस को खोजने और स्टोर करने के लिए एल्गोरिदम और डेटा संरचना मेरे पास एक छवि है, इस तरह से विभाजन का परिणाम है। enter image description hereसी ++

मुझे विभिन्न रंगों में रंगीन पैच के पड़ोस का ग्राफ बनाना होगा। नतीजतन मैं एक संरचना करना चाहते हैं, का प्रतिनिधित्व निम्नलिखित enter image description here

यहाँ संख्या अलग पैच का प्रतिनिधित्व करते हैं, और लाइनों पैच 'पड़ोस का प्रतिनिधित्व करते हैं। वर्तमान में मैं यह नहीं समझ सकता कि कहां से शुरू करना है, कौन सा कीवर्ड Google पर है।

कोई भी कुछ भी उपयोगी सुझाव दे सकता है?

छवि ओपनसीवी के सीवी :: मैट क्लास में संग्रहीत है, ग्राफ के लिए, मैं Boost.Graph लाइब्रेरी का उपयोग करने की योजना बना रहा हूं।

तो, कृपया मुझे कोड नमूने और एल्गोरिदम, या कीवर्ड के कुछ लिंक दें।

धन्यवाद।

अद्यतन। कॉफी ब्रेक और कुछ चर्चाओं के बाद, निम्नलिखित मेरे दिमाग में आया है।

  1. एक बड़ा जाली ग्राफ बनाएं, जहां प्रत्येक नोड प्रत्येक छवि पिक्सेल से मेल खाता है, और लिंक 8 या 4 पड़ोसियों को जोड़ते हैं।
  2. प्रत्येक ग्राफ़ नोड को इसी पिक्सेल मान के साथ लेबल करें।
  3. उसी लेबल के साथ किसी भी तरह नोड्स को मर्ज करने का प्रयास करें।

मेरी एक और समस्या यह है कि मैं बीजीएल से परिचित नहीं हूं (लेकिन पुस्तक रास्ते पर है :))।

तो, आप इस समाधान के बारे में क्या सोचते हैं?

अद्यतन 2 शायद, यह link मदद कर सकता है।

हालांकि, समाधान अभी भी नहीं मिला है।

उत्तर

5

आप उस तरह इसे हल कर सकते हैं:

  1. (ग्राफ में अपनी संख्या) क्षेत्रों को परिभाषित करें

    • एक 2D सरणी, जिस पर क्षेत्र संख्या संग्रहीत करता
    • शुरू कर (0/0) और इसे 1 (क्षेत्र संख्या)
    • पर सेट करें, पूरे क्षेत्र को बाढ़फिल एल्गोरिदम या कुछ का उपयोग करके 1 के रूप में सेट करें।
    • बाढ़ के दौरान आप शायद समन्वय का सामना करते हैं जिसमें अलग-अलग रंग होते हैं। एक कतार के अंदर उनको स्टोर करें। यदि आपका पिछला भर पूरा हो गया है तो उन निर्देशांकों और वृद्धि क्षेत्र संख्या से भरना शुरू करें।

  2. अपने 2 डी सरणी के माध्यम से क्षेत्रों

    • पुनरावृति के बीच संबंध बनाओ।
    • यदि आपके पड़ोसी नंबर हैं, तो संख्या जोड़ी को स्टोर करें (शायद एक क्रमबद्ध तरीके से, आपको यह भी जांचना होगा कि जोड़ी पहले से मौजूद है या नहीं)। यदि आप बाएं से दाएं से आगे बढ़ते हैं, तो आपको केवल नीचे दिए गए तत्व को दाएं और दाईं ओर एक विकर्ण की जांच करनी होगी।

हालांकि मैं स्वीकार करने के लिए मैं इस विषय .. बस अपना सरल विचार के बारे में एक बात पता नहीं है है ..

0

मुझे लगता है कि अगर अपने रंग पैच कि यादृच्छिक कर रहे हैं, तो आप शायद होगा जो भी आप चाहते हैं उसे करने के लिए एक ब्रूट फोर्स एल्गोरिदम की आवश्यकता है। एक विचार हो सकता है:

  • पहला ब्रूट फोर्स पास करें। इसे सभी पैच की पहचान करनी है। उदाहरण के लिए, छवि के समान आकार का एक मैट्रिक्स ए बनाएं, और इसे 0 पर प्रारंभ करें। प्रत्येक पिक्सेल के लिए जो अभी भी शून्य है, उससे शुरू करें और इसे एक नए पैच के रूप में चिह्नित करें, और संपूर्ण खोजने के लिए एक ब्रूट फोर्स दृष्टिकोण आज़माएं पैच की सीमा। प्रत्येक मैट्रिक्स सेल के बाद उसके पास पैच की संख्या के बराबर मान होगा।
  • पैच संख्या 2^N होनी चाहिए, उदाहरण के लिए 1, 2, 4, 8, ...
  • छवि के आकार का एक और मैट्रिक्स बी बनाएं, लेकिन प्रत्येक सेल में दो मान होते हैं। यह पिक्सेल के बीच कनेक्शन का प्रतिनिधित्व करेगा। मैट्रिक्स बी के प्रत्येक सेल के लिए, पहला मान पिक्सेल में पैच संख्या और आसन्न पिक्सेल के पैच संख्या के बीच पूर्ण अंतर होगा। पहला मान नीचे पिक्सेल के साथ अंतर है, दूसरा पिक्सेल बाईं ओर है।
  • मैट्रिक्स बी में सभी अद्वितीय मान चुनें, आपके पास सभी कनेक्शन संभव हैं।

यह काम करता है क्योंकि पैच संख्या के बीच प्रत्येक अंतर अद्वितीय है। उदाहरण के लिए, यदि बी में आप संख्या 3, 6, 7 के साथ समाप्त होते हैं तो इसका अर्थ यह होगा कि पैच (4,1), (8,2) और (8,1) के बीच संपर्क हैं। पाठ्यक्रम 0 का मतलब है कि एक दूसरे के बगल में एक ही पैच में दो पिक्सल हैं, इसलिए आप उन्हें अनदेखा करते हैं।

2

आप क्षेत्रों को चिह्नित करने के लिए BFS का उपयोग कर सकते हैं।

सीवी :: बीजीएल को मैट का खुलासा करने के लिए आपको बहुत सारे कोड लिखना चाहिए। मुझे लगता है कि अपने स्वयं के बीएफएस लिखना ज्यादा आसान है।

प्रत्येक दो नकारात्मक लोगों के लिए आप उनके अंक std::set<std::pair<mark_t, mark_t>> पर लिखते हैं। और उससे ग्राफ बनाने के बजाय।