इसोफोट्स का पता लगाना

मुझे एक बार आइसोफ़ेट्स (छवियों में समान तीव्रता की रेखाएं) की गणना करने की आवश्यकता थी, हालांकि, मुझे कोई भी तैयार-किए गए पुस्तकालय नहीं मिले, लेकिन मैं वास्तव में किसी और के कोड (उदाहरण के लिए, उसी ऑक्टेव या इराफ) में तल्लीन नहीं करना चाहता था। सबसे सरल एल्गोरिथ्म के रूप में, मुझे पैदल चलने की विधि मिली। हालांकि, इस विधि से आइसोफोट नोड्स की गणना करते समय स्थानिक रिज़ॉल्यूशन बहुत कम हो जाता है, इसलिए मैंने इसे थोड़ा संशोधित करने और स्क्वाड को ओवरलैप करने का निर्णय लिया।
पहला कार्यान्वयन (वैसे, बहुत तेज़) असफल रहा: मैंने एक मुखौटा बनाया जो सभी स्तरों के लिए सामान्य था, और एक विशिष्ट स्तर के लिए मैं अलग से अंकन करता था, उन बिंदुओं पर जिसके माध्यम से कई आइसोलेट्स गुजरते हैं, अंतराल थे। कोड में चारों ओर उठाकर अधिक से अधिक गतिरोधों और झंडों का नेतृत्व किया, इसलिए मैंने प्रदर्शन को समझौता करने और अपनी तीव्रता के स्तर के लिए अलग से मास्क की गणना करने का निर्णय लिया।

तो, संक्षेप में दोहराएं कि "चलने वाले वर्गों" की विधि क्या है। I स्तर के आइसोफोट्स के निर्माण के लिए, एक विशेष मास्क का पहली बार निर्माण किया गया है: छवि में प्रत्येक पिक्सेल के लिए, "पड़ोसी" की सापेक्ष स्थिति दाईं ओर, नीचे और नीचे दाईं ओर एन्कोडेड है। आप इसे अलग-अलग तरीकों से सांकेतिक शब्दों में बदलना कर सकते हैं, मैंने बस कोड को एक बिट मास्क 000abcd के रूप में प्रस्तुत किया है, जहाँ a, b, c और d संबंधित पिक्सेल में सापेक्ष तीव्रता हैं (एक छवि में हमारा वर्तमान पिक्सेल है)

यदि पिक्सेल में मान समोच्च के स्तर से अधिक है, तो संबंधित बिट को एक असाइन किया जाता है, अन्यथा, शून्य। यदि w छवि की चौड़ाई है, और * में पिक्सेल a के लिए सूचक है, तो इस पिक्सेल के लिए मुखौटा मान (* आउट) की गणना इस प्रकार की जाती है:

*out = (unsigned char) ((in[0]>lvl)<<3) | ((in[1]>lvl)<<2) | ((in[w]>lvl)<<1) | (in[w+1]>lvl); 

परिणामस्वरूप, पिक्सेल के विन्यास के आधार पर, हमें 16 में से एक मान मिलता है:

मुखौटा का आकार छवि के आकार की तुलना में दोनों आयामों में एक कम है।

अगला कदम शून्य और असमानता के लिए एक-एक करके मास्क के सभी पिक्सल की जांच करना है। जैसे ही हमें ऐसा पिक्सेल मिलता है, हम उससे एक समोच्च का निर्माण शुरू करते हैं। सही ढंग से आकृति का निर्माण करने के लिए, हमें उस दिशा को याद रखने की आवश्यकता है, जिससे हमने इस पिक्सेल से संपर्क किया था। ऊपर दिए गए आंकड़े में, तीर मुखौटा के प्रत्येक पिक्सेल से संभव "वंश" पथ को इंगित करता है। यदि हम निषिद्ध दिशा (जिसमें से हम आए थे) को ध्यान में नहीं रखते हैं, तो हमें या तो मुखौटा के अतिरिक्त पिक्सेल की जांच करनी होगी, या (विशेष अंक 6 और 9 के मामले में, लेकिन उनके बारे में थोड़ी देर बाद), हम आम तौर पर अगले आइसोफोट बिंदु की स्थिति चुन सकते हैं।
जैसा कि आप मुखौटा के पिक्सल को देखते हैं (बाएं से दाएं और ऊपर से नीचे तक, यदि आप ऊपरी बाएं कोने में छवि की उत्पत्ति की गणना करते हैं), जबकि हम केवल खाली कक्ष पाते हैं, "निषिद्ध" दिशा "बाईं" दिशा है। जैसे ही हमें समोच्च के एक खंड युक्त एक सेल मिलता है, हम, "दिशाओं" की पूर्व-तैयार सरणी के अनुसार, "निषिद्ध" को काटते हुए, अगली दिशा का चयन करते हैं। यदि ऐसी दो दिशाएँ हैं, तो हम वामावर्त या बाईं ओर ऊपर ("प्राथमिकता" के लिए प्राथमिकता के साथ) दाहिने या नीचे (प्राथमिकता के साथ "सही") का चयन करते हैं, जब वामावर्त (आगे इस बारे में अधिक) चलते हैं।
उसके बाद, हम एक विशिष्ट पिक्सेल के लिए समोच्च नोड की स्थिति की गणना करते हैं। यह इस पिक्सेल में मास्क के मूल्य के अनुसार, कार्यों की एक सरणी का उपयोग करके किया जाता है। नीचे दिया गया आंकड़ा बताता है कि इस स्थिति की गणना कैसे की जाती है।

तो, छवि को आकृति में दिखाए गए तीव्रता (कोशिकाओं के अंदर की संख्या) होने दें। हम 30 के स्तर पर इसोफ़ोटेस का संचालन करते हैं। पिक्सेल पड़ोसियों (x _i , y _i ) का कॉन्फ़िगरेशन सात के मास्क मान से मेल खाता है। हम संबंधित फ़ंक्शन को कॉल करते हैं, जो सही दो पिक्सल को लंबवत और निचले दो क्षैतिज रूप से जोड़ने वाली रेखाओं पर रैखिक प्रक्षेप विधि द्वारा समोच्च रेखा के नियंत्रण बिंदुओं के निर्देशांक की गणना करता है। अनुरूप डॉट्स खुले लाल हलकों के साथ चिह्नित हैं। उन्हें एक सीधी रेखा से जोड़ने और इसके केंद्र को खोजने पर, हमें वांछित आइसोफोट नोड (एक हरे रंग के भराव के साथ लाल वृत्त के साथ चिह्नित, "हमारी बात") मिलता है। यह, ज़ाहिर है, एक बहुत ही सही तरीका नहीं है, लेकिन अधिकांश कार्यों के लिए यह पर्याप्त है। प्रत्येक नोड को संबंधित सूची की पूंछ में जोड़ा जाता है।
संबंधित मास्क मान का उपयोग किए जाने के बाद, यह शून्य पर रीसेट हो जाता है और हम मास्क के अगले पड़ोसी पिक्सेल पर चले जाते हैं। यदि इसकी सामग्री आइसोफोट के अगले नोड के अनुरूप है, तो हम गणना जारी रखते हैं, अन्यथा, हम आइसोफोट को "बंद" करते हैं। आइसोफोट के "बंद होने" के ठीक बाद, हम जांच करते हैं, सबसे पहले, चाहे वह बहुत छोटा हो (एक पिक्सेल के आसपास), और दूसरी बात, हम इसकी निकटता की जांच करते हैं: यदि आइसोफोट्स की शुरुआत और अंत इससे कहीं अधिक झूठ बोलते हैं, तो कहना , 2 पिक्सेल के अलावा, हम इसे बंद मानते हैं।
इसोफ़ोटेस को "बंद" करने की प्रक्रिया "बस के मामले में" है कि क्या आइसोफ़ेट्स विपरीत दिशा में अपने पहले बिंदु से जारी है। ऐसा करने के लिए, हम आगे बढ़ने पर प्रतिबंध के साथ मुखौटा के पहले पिक्सेल के नीचे जाते हैं। यदि हमें वहां आइसोफोट की निरंतरता का पता चलता है, तो हम इसके अंत तक सही जाते हैं, सूची के "सिर" में नोड्स जोड़ते हैं और प्राथमिकता के रूप में वामावर्त दिशाओं का चयन करते हैं।

उपरोक्त सभी सही है जब तक कि हम विशेष पिक्सल पर "ठोकर" नहीं देते: 6 और 9. दो आइसोफोटिक लाइनें मुखौटा के इन पिक्सल से गुजरती हैं, इसलिए यह आवश्यक है, "निषिद्ध" दिशा के आधार पर, सही अगली दिशा चुनने के लिए। इसलिए, उदाहरण के लिए, अगर हम बाईं ओर आने वाले मान 6 पर "ठोकर" खाते हैं, तो अगली दिशा "ऊपर" होगी।
अगले पास में एक और समोच्च बिंदु के बारे में "भूल" नहीं करने के लिए, हम विशेष मूल्य को "विशेष नहीं" के साथ प्रतिस्थापित करते हैं, बस "पहले से इस्तेमाल किए गए पिक्सेल" पर पेंटिंग करके (उदाहरण के लिए, यदि हम बाईं ओर "छह" मारते हैं, तो हम " "ऊपरी बाएं पिक्सेल पर पेंट करें, यानी 6 को 7 से बदलें)। यह विधि, दुर्भाग्य से, तीव्रता के "कूबड़" में एकल-पिक्सेल "डिप्स" की उपस्थिति के मामले में "ओवरसाइट्स" का कारण बनती है। लेकिन, दुर्भाग्य से, इस का सुधार एक बहुत ही जटिल एल्गोरिथमिक कार्य है, जो कि इसोफोट्स के निर्माण में बहुत अधिक कंप्यूटर समय लेगा। और अधिकांश छवियों के लिए, वर्णित विधि ठीक काम करती है।
इस प्रकार, "विशेष" पिक्सल का उपयोग दो बार किया जाता है, केवल दूसरे पास के बाद शून्य करना। विशेष बिंदुओं पर नोड्स की गणना दूसरे तरीके से की जाती है: इसके लिए, एक फ़ंक्शन उपयोग किए गए पिक्सेल के विपरीत पिक्सेल के "शेडिंग" के साथ लिया जाता है।

मैं नीचे दिए गए चित्र में दिखाए गए दो पिक्सेल के "शिखर" को दरकिनार करके उदाहरण के एल्गोरिथ्म के संचालन का वर्णन करूंगा।

4x4 पिक्सेल छवि का दिया गया अनुभाग 3x3 पिक्सेल मास्क (दाईं ओर) से मेल खाता है। हम छवि के ऊपरी बाएं पिक्सेल से आंदोलन शुरू करते हैं। क्योंकि मास्क पर, यह शून्य से मेल खाती है, हम मुखौटा के अगले दाहिने पिक्सेल पर जाते हैं (हमें याद है कि हमारे पास "सही" दिशा में "प्रतिबंध" है)। निषिद्ध दिशाओं को अंजीर में दिखाया गया है। दाईं ओर लाल तीर, एक काले तीर के साथ "खाली" संक्रमण, हरे तीर के साथ आइसोलिन नोड्स की गणना के साथ संक्रमण।
तो, हम आठ पर "ठोकर" खाते हैं और पहले आइसोफोट नोड की स्थिति को इसी फ़ंक्शन की सहायता से गणना करते हैं। अगला, हम पहले से तैयार किए गए सरणी को देखते हैं और देखते हैं कि वर्तमान पिक्सेल से "वंश" की दिशाएं "सही" या "सही" हैं। हम "दाईं ओर" दिशा चुनते हैं और अगले पिक्सेल (4) पर जाते हैं, मास्क के पहले से ही इस्तेमाल किए गए पिक्सेल को रीसेट करने की भूल नहीं करते हैं (पिक्सेल के ऊपरी दाएं कोने में पिक्सल के शून्य को लाल शून्य से चिह्नित किया जाता है)।
इसके बाद, हम मान 1 पर जाते हैं, और उसके बाद मान 6 के साथ एकवचन बिंदु पर। 6. चूंकि हम दाईं ओर आए, फिर नोड मान की गणना मुखौटा मान के लिए सात के बराबर होती है, और मास्क पर छह को 14. से बदल दिया जाता है। उसके बाद, हम एकता के लिए नीचे जाते हैं।
इकाई, दो और आठ से गुजरने के बाद, हम अपने "विशेष" पिक्सेल पर लौट आते हैं, लेकिन पहले से ही 14 का मान होगा, अर्थात्। आगे की गणना "जैसे कि कुछ नहीं हुआ था" होगी, जिसके बाद हमें ऊपर जाने की आवश्यकता होगी। हालाँकि, शीर्ष पर हम शून्य पर आते हैं। हम या तो नोड्स की सूची के "प्रमुख" के लिए कुछ भी नहीं जोड़ सकते हैं, क्योंकि समोच्च के शुरुआती पिक्सेल के तहत मूल्य भी शून्य पर रीसेट है। इसलिए, हम लाइन के प्रारंभ और अंत नोड्स की निकटता की जांच करते हैं। वे काफी करीब हैं, और हम इस समोच्च को बंद के रूप में चिह्नित कर सकते हैं।

एल्गोरिथ्म के सभी स्रोत यहां मिल सकते हैं । मैं कम से कम 4..8 समानांतर धागे शुरू करने के लिए विभिन्न स्तरों की आकृति की गणना के समानांतर जोड़ने की योजना बनाता हूं। अब तक, एक धारा में, 3000x3000 पिक्सेल की एक परीक्षण छवि के लिए, 16 स्तरों पर आइसोफोट्स के निर्माण में लगभग 1.2s लगते हैं।