इमेज आउटलाइन डिटेक्शन एल्गोरिदम

लेख चार सबसे आम लूप डिटेक्शन एल्गोरिदम प्रस्तुत करता है।

पहले दो, अर्थात् एल्गोरिथ्म वर्गों के लिए और मूर के परिवेश का पता लगाने के लिए लागू करना आसान है, और इसलिए अक्सर किसी दिए गए पैटर्न के समोच्च को निर्धारित करने के लिए उपयोग किया जाता है। दुर्भाग्य से, दोनों एल्गोरिदम में कई कमजोरियां हैं, जो उनके विशेष प्रकार के आसन्न के कारण पैटर्न के एक बड़े वर्ग के समोच्च का पता लगाना असंभव बनाता है ।

ये एल्गोरिदम पैटर्न में सभी "छेद" को अनदेखा करेंगे। उदाहरण के लिए, यदि हमारे पास चित्र 1 में दिखाए गए समान पैटर्न है, तो एल्गोरिदम द्वारा ज्ञात सर्किट चित्र 2 में दिखाए गए के समान होगा (रूपरेखा नीले पिक्सल द्वारा इंगित की गई है)। आवेदन के कुछ क्षेत्रों में यह काफी स्वीकार्य है, लेकिन अन्य क्षेत्रों में, उदाहरण के लिए, चरित्र मान्यता में, एक पैटर्न के आंतरिक भागों का पता लगाने के लिए उन सभी रिक्त स्थान को खोजने की आवश्यकता होती है जो एक विशिष्ट चरित्र को अलग करते हैं। ( चित्र 3 पैटर्न की "पूर्ण" रूपरेखा दिखाता है।)



इसलिए, एक पूर्ण समोच्च प्राप्त करने के लिए, "छेद खोज" एल्गोरिथ्म का उपयोग करना आवश्यक है जो किसी दिए गए पैटर्न में छेद निर्धारित करता है, और फिर प्रत्येक छेद में समोच्च पहचान एल्गोरिथ्म लागू करता है।

कनेक्टिविटी क्या है?

द्विआधारी मूल्यों के साथ डिजिटल छवियों में, एक पिक्सेल में निम्न मान हो सकते हैं: 1 - जब यह पैटर्न का हिस्सा होता है, या 0 - जब यह पृष्ठभूमि का हिस्सा होता है, अर्थात। ग्रे का कोई उन्नयन। (हम मानेंगे कि 1 के मान वाले पिक्सेल काले हैं, और 0 के मान के साथ सफेद हैं)।

डिजिटल पैटर्न में वस्तुओं की पहचान करने के लिए, हमें उन ब्लैक पिक्सल्स के समूहों को खोजने की जरूरत है जो एक दूसरे से "जुड़े" हैं। दूसरे शब्दों में, किसी दिए गए डिजिटल पैटर्न में ऑब्जेक्ट इस पैटर्न के जुड़े हुए घटक हैं ।

सामान्य स्थिति में, एक जुड़ा घटक ब्लैक पिक्सल्स पी का एक सेट होता है, जैसे कि पी के प्रत्येक जोड़े के लिए पी _आई और पी _जे में पी पिक्सल पी का एक अनुक्रम होता है _i , ..., p _j ऐसा कि:

a) अनुक्रम में सभी पिक्सेल सेट P , अर्थात् में हैं। काले हैं, और

बी) एक दूसरे के बगल में अनुक्रम में हर 2 पिक्सल "पड़ोसी" हैं।

एक महत्वपूर्ण सवाल उठता है: हम कब कह सकते हैं कि 2 पिक्सेल "पड़ोसी" हैं? चूँकि हम वर्ग पिक्सेल का उपयोग करते हैं, इसलिए पिछले प्रश्न का उत्तर निम्न कारणों से तुच्छ नहीं है: वर्ग टसेलेशन में, पिक्सेल का एक सामान्य किनारा या एक शीर्ष होता है, या इनमें कुछ भी सामान्य नहीं होता है। प्रत्येक पिक्सेल में इसके साथ सामान्य रूप से 8 पिक्सेल होते हैं; ऐसे पिक्सेल उस पिक्सेल का "मूर पड़ोस" बनाते हैं। क्या हमें "पड़ोसी" पिक्सल पर विचार करना चाहिए जिसमें केवल एक ही सामान्य शीर्ष है? या "पड़ोसी" माने जाने के लिए, दो पिक्सल्स में एक सामान्य बढ़त होनी चाहिए?

तो कनेक्टिविटी के दो प्रकार हैं, अर्थात्: 4-कनेक्टिविटी और 8-कनेक्टिविटी।

4-कनेक्टिविटी

हम कब कह सकते हैं कि काले पिक्सेल का एक सेट 4-जुड़ा हुआ है? सबसे पहले, आपको 4-पड़ोसी की अवधारणा को परिभाषित करने की आवश्यकता है (जिसे प्रत्यक्ष पड़ोसी भी कहा जाता है ):

4-पड़ोसी परिभाषा : एक पिक्सेल क्यू किसी दिए गए पिक्सेल P का 4-पड़ोसी है यदि Q और P में एक आम बढ़त है। पिक्सेल पी के 4-पड़ोसियों को नीचे चित्र 2 में पी 2, पी 4, पी 6, और पी 8 के रूप में निर्दिष्ट किया गया है।


4-कनेक्टेड कंपोनेंट की परिभाषा : ब्लैक पिक्स पी का सेट एक 4-कनेक्टेड कंपोनेंट है यदि पी के प्रत्येक जोड़े के लिए पी _आई और पी _जे है तो पिक्सल्स पी का एक अनुक्रम है _i , ..., p _j ऐसा कि:

a) अनुक्रम में सभी पिक्सेल सेट P , अर्थात् में हैं। काले हैं, और

बी) अनुक्रम में आसन्न हर दो पिक्सेल 4 पड़ोसी हैं

4-जुड़े पैटर्न के उदाहरण

नीचे दिए गए आरेख 4-जुड़े पैटर्न के उदाहरण दिखाते हैं:

8-कनेक्टिविटी

मैं कब कह सकता हूं कि काले पिक्सेल का एक सेट 8-जुड़ा हुआ है ? सबसे पहले, हमें 8-पड़ोसी (जिसे अप्रत्यक्ष पड़ोसी भी कहा जाता है ) की अवधारणा को परिभाषित करने की आवश्यकता है:

8-पड़ोसी परिभाषा : एक पिक्सेल क्यू किसी दिए गए पिक्सेल P का 8-पड़ोसी (या सिर्फ एक पड़ोसी ) है यदि Q और P में एक सामान्य किनारा या शीर्ष है। किसी दिए गए पिक्सेल P के 8 पड़ोसी इस पिक्सेल के मूर पड़ोस को बनाते हैं।

8-कनेक्टेड कंपोनेंट की परिभाषा : ब्लैक पिक्स पी का सेट एक 8-कनेक्टेड कंपोनेंट (या सिर्फ एक कनेक्टेड कंपोनेंट ) है अगर पिक्सल्स की प्रत्येक जोड़ी के लिए p _i और p _j P में पिक्सल्स p, _i , ..., p _j जैसे का एक क्रम है। :

a) अनुक्रम में सभी पिक्सेल सेट P , अर्थात् में हैं। काले हैं, और

बी) इस क्रम में आसन्न हर दो पिक्सेल 8 पड़ोसी हैं

नोट : सभी 4-कनेक्टेड पैटर्न 8-कनेक्टेड हैं, अर्थात 4-कनेक्टेड पैटर्न कई 8-कनेक्टेड पैटर्न का एक सबसेट है। दूसरी ओर, 8-कनेक्टेड पैटर्न 4-कनेक्टेड नहीं हो सकता है।

8-लिंक्ड पैटर्न उदाहरण

नीचे दिए गए आरेख में एक पैटर्न दिखाया गया है जो 8-जुड़ा हुआ है लेकिन 4-जुड़ा नहीं है:

गैर-कनेक्टेड पैटर्न का एक उदाहरण:

नीचे दिए गए आरेख में एक पैटर्न का उदाहरण दिखाया गया है जो 8 से जुड़ा नहीं है, अर्थात्। एक से अधिक जुड़े हुए घटकों से बना (आरेख तीन जुड़े घटकों को दिखाता है):

स्क्वायर ट्रेस एल्गोरिथम

विचार

वर्ग अनुरेखण एल्गोरिथ्म के पीछे का विचार बहुत सरल है; यह इस तथ्य के लिए जिम्मेदार ठहराया जा सकता है कि एल्गोरिथ्म एक द्विआधारी पैटर्न के समोच्च का पता लगाने के पहले प्रयासों में से एक था।

यह समझने के लिए कि यह कैसे काम करता है, आपको थोड़ी कल्पना की आवश्यकता है ...

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

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

, , ,

, , ,

.

आपके द्वारा परिकल्पित ब्लैक पिक्सल्स पैटर्न की रूपरेखा होगी।


वर्ग ट्रेस एल्गोरिथ्म का एक महत्वपूर्ण पहलू "दिशा की भावना" है। बाईं और दाईं ओर के मोड़ वर्तमान स्थान के सापेक्ष किए गए हैं, जो इस बात पर निर्भर करता है कि आपको वर्तमान पिक्सेल में कैसे मिला। इसलिए, सही चाल बनाने के लिए, आपको अपनी दिशा को ट्रैक करने की आवश्यकता है।

एल्गोरिथ्म

निम्नलिखित वर्ग ट्रेस एल्गोरिथ्म का एक औपचारिक विवरण है:

इनपुट: काले कोशिकाओं के जुड़े घटक पी युक्त वर्ग टसेलेशन , टी ।

आउटपुट: बॉर्डर पिक्सल की पंक्ति बी (बी ₁ , बी ₂ , ..., बी _के ) , अर्थात्। सर्किट।

शुरुआत

• B को एक खाली सेट के रूप में परिभाषित करें।
• कोशिकाओं को नीचे से ऊपर तक स्कैन करें और दाएं से बाएं जब तक पी से एक काले पिक्सेल एस नहीं मिलता है ।
• बी में डालें ।
• वर्तमान पिक्सेल को प्रारंभिक पिक्सेल s बनाएँ।
• बाएं मुड़ें, अर्थात्। पी के बाईं ओर पड़ोसी पिक्सेल पर जाएं।
• अपडेट पी , यानी यह वर्तमान पिक्सेल बन जाता है।
• जबकि p s के बराबर नहीं है, निष्पादित करें
  
  यदि वर्तमान पिक्सेल p काला है
  
  • बी में पी डालें और बाएं मुड़ें ( पी के बाईं ओर पड़ोसी पिक्सेल पर जाएं)।
  • अपडेट पी , यानी यह वर्तमान पिक्सेल बन जाता है।
  
  अन्यथा
  
  • दाएं मुड़ें ( p के दाईं ओर अगले पिक्सेल पर जाएं)।
  • अपडेट पी , यानी यह वर्तमान पिक्सेल बन जाता है।
  
  "बाय" चक्र का अंत

अंत

नोट: "बाएं" और "दाएं" की अवधारणाओं को पृष्ठ या पाठक के संबंध में नहीं, बल्कि स्कैनिंग के दौरान "वर्तमान" पिक्सेल में प्रवेश की दिशा के संबंध में माना जाना चाहिए।

प्रदर्शन

निम्नलिखित एक एनिमेटेड प्रदर्शन है कि कैसे स्क्वायर ट्रेस एल्गोरिथ्म एक पैटर्न की रूपरेखा का पता लगाता है। यह मत भूलो कि लेडीबग पिक्सल में चलता है; ध्यान दें कि बाएँ और दाएँ मुड़ते समय इसकी दिशा कैसे बदलती है। बाएँ और दाएँ मुड़ें पिक्सेल में वर्तमान दिशा के सापेक्ष किए जाते हैं, अर्थात्। लेडीबग ओरिएंटेशन।

के विश्लेषण

यह पता चला है कि वर्ग ट्रेस एल्गोरिथ्म की क्षमताएं बहुत सीमित हैं। वह पैटर्न के एक बड़े परिवार के संदर्भों का पता लगाने में असमर्थ है जो अक्सर वास्तविक दुनिया के अनुप्रयोगों में उत्पन्न होते हैं।

यह मुख्य रूप से इस तथ्य के कारण है कि बाएं और दाएं घुमाव "साथ स्थित पिक्सेल" को ध्यान में नहीं रखते हैं
विकर्ण ”वर्तमान पिक्सेल से।

आइए विभिन्न संयोजनों के साथ अलग-अलग पैटर्न देखें और देखें कि स्क्वायर ट्रेस एल्गोरिथ्म विफल क्यों होता है। इसके अलावा, हम एल्गोरिथ्म की क्षमताओं में सुधार करने के तरीकों का अध्ययन करेंगे और उन पैटर्नों के साथ भी काम करेंगे, जिनमें एक विशेष प्रकार की कनेक्टिविटी है।

कसौटी बंद करो

एल्गोरिथ्म की कमजोरियों में से एक स्टॉपिंग मानदंड का विकल्प है। दूसरे शब्दों में, एक एल्गोरिथ्म निष्पादित कब बंद होता है?

वर्ग ट्रेस एल्गोरिथ्म के मूल विवरण में, पूरा होने की स्थिति प्रारंभिक पिक्सेल को दूसरी बार हिट करना है। यह पता चला है कि यदि एल्गोरिथ्म इस तरह के मानदंड पर निर्भर करता है, तो यह पैटर्न के एक बड़े परिवार के आकृति का पता लगाने में सक्षम नहीं होगा।

निम्नलिखित एक एनिमेटेड डेमो है जो बताता है कि एल्गोरिथ्म एक खराब मानदंड के चयन के कारण पैटर्न के सटीक समोच्च का पता लगाने में कैसे असमर्थ है:


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

a) केवल शुरुआती पिक्सेल n बार जाकर रोकें, जहाँ n कम से कम 2, या है

b) स्टार्ट पिक्सेल को दूसरी बार हिट करने के बाद रोकें, जैसे हम इसे शुरू में मारते हैं।

यह मानदंड जैकब एलियोसॉफ द्वारा प्रस्तावित किया गया था, इसलिए हम इसे जैकब को रोकने के लिए कसौटी कहेंगे।

सामान्य मामले में स्टॉपिंग मानदंड बदलने से स्क्वायर ट्रेस एल्गोरिथ्म की प्रभावशीलता में सुधार होता है, लेकिन अन्य कमजोरियों को दूर नहीं करता है जो विशेष प्रकार की कनेक्टिविटी के साथ पैटर्न के मामले में है।

स्क्वायर ट्रेसिंग एलगोरिदम 8 के कनेक्टिविटी वाले पैटर्न के परिवार के समोच्च का पता लगाने में असमर्थ है जिसमें 4 की कनेक्टिविटी नहीं है।

निम्न का एक एनिमेटेड प्रदर्शन है कि कैसे स्क्वायर ट्रेस एल्गोरिथ्म (जैकब की रोक मानदंड के साथ) कनेक्टिविटी 4 के बिना कनेक्टिविटी 8 के साथ एक पैटर्न की सही रूपरेखा का पता लगाने में विफल रहता है:

क्या यह एल्गोरिथ्म पूरी तरह से बेकार है?

यदि आप उपरोक्त विश्लेषण पढ़ते हैं, तो आप शायद सोचते हैं कि वर्ग ट्रेस एल्गोरिथ्म अधिकांश पैटर्न की रूपरेखा का पता लगाने में विफल रहता है। लेकिन यह पता चला है। वहाँ पैटर्न का एक विशेष परिवार है जिसमें पथ पूरी तरह से स्क्वायर ट्रेस एल्गोरिथ्म द्वारा पता लगाया जाता है।

बता दें कि P ग्रिड पर कनेक्टिविटी 4 के साथ ब्लैक पिक्सल का सेट है। चलो ग्रिड के सफेद पिक्सेल, अर्थात बैकग्राउंड पिक्सल्स डब्ल्यू की कनेक्टिविटी भी 4. यह पता चलता है कि पैटर्न और इसकी पृष्ठभूमि की ऐसी स्थितियों के तहत, यह साबित किया जा सकता है कि स्क्वायर ट्रेस एल्गोरिथ्म (जैकब स्टॉप मानदंड के साथ) हमेशा समोच्च के निर्धारण से सफलतापूर्वक निपटेगा।

नीचे इस बात का प्रमाण है कि जिस स्थिति में पैटर्न और बैकग्राउंड पिक्सल दोनों जुड़े हुए हैं, जैकब स्टॉप मानदंड का उपयोग करते समय स्क्वायर ट्रेस एल्गोरिथ्म सही ढंग से समोच्च निर्धारित करेगा।

सबूत
यह देखते हुए : पैटर्न पी ऐसा है कि पैटर्न के सभी पिक्सल (यानी काले) और पृष्ठभूमि के पिक्सल (यानी सफेद) डब्ल्यू में 4 की कनेक्टिविटी है।

पहला अवलोकन

चूंकि सफेद पिक्सेल डब्ल्यू के सेट में 4 की कनेक्टिविटी होती है, इसका मतलब है कि पैटर्न में कोई भी " छेद " नहीं हो सकता है (अनौपचारिक शब्दों में कहें तो " छेद " का मतलब है कि सफेद पिक्सल के समूह पूरी तरह से पैटर्न के काले पिक्सल से घिरे हैं)।

पैटर्न में किसी भी " छेद " की उपस्थिति शेष सफेद पिक्सेल से सफेद पिक्सेल के समूह को अलग करने की ओर ले जाएगी; हालाँकि, कई सफेद पिक्सेल कनेक्टिविटी 4 खो देते हैं।

नीचे दिए गए चित्र 2 और चित्र 3 में दो प्रकार के " छेद " दिखाई देते हैं जो कि कनेक्टिविटी 4 के साथ एक पैटर्न में हो सकते हैं:



दूसरा अवलोकन

MUST पैटर्न के किसी भी दो ब्लैक पिक्सल में एक सामान्य पक्ष होता है।

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


निम्नानुसार इस तरह के पैटर्न का प्रतिनिधित्व करना उपयोगी है:

पहले हम सीमा पिक्सल पर विचार करते हैं, अर्थात्। पैटर्न की रूपरेखा। फिर, यदि हम प्रत्येक सीमा पिक्सेल को इकाई लंबाई के 4 किनारों के रूप में मानते हैं, तो हम देखेंगे कि इनमें से कुछ किनारे पड़ोसी सफेद पिक्सेल के साथ आम हैं। हम ऐसे किनारों को सीमा किनारा कहेंगे।

इस तरह के सीमा किनारों को बहुभुज के किनारों के रूप में माना जा सकता है। चित्र में
नीचे 5 , यह विचार ऊपर चित्र 4 से पैटर्न के अनुरूप बहुभुज के उदाहरण द्वारा प्रदर्शित किया गया है:


यदि हम सीमा पिक्सल के सभी संभावित "कॉन्फ़िगरेशन" पर विचार करते हैं जो ऐसे पैटर्न में हो सकते हैं, तो हम देखेंगे कि दो सरल मामले हैं, नीचे चित्र 6 और चित्र 7 में दिखाए गए हैं।

सीमा पिक्सेल इन मामलों या अन्य व्यवस्थाओं के गुणक हो सकते हैं, अर्थात्। इन दो मामलों के मोड़ और मोड़। सीमा पसलियों को E1, E2, E3 और E4 के रूप में नीले रंग में चिह्नित किया गया है।


तीसरा अवलोकन

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

दो अवधारणाओं को यहां स्पष्ट करने की आवश्यकता है:

क) एल्गोरिथ्म "वापस चला जाता है" , जब पूरी सीमा को ट्रेस करने से पहले यह पहले से ही देखे गए पिक्सेल, और

बी) प्रत्येक सीमा रिब के लिए, "इनवर्ड" से गुजरने के दो तरीके हैं, अर्थात् "इनवर्ड" और "आउटवर्ड" (जहां "इनवर्ड" का अर्थ है, संबंधित पॉलीगॉन की आवक और "आउटवर्ड" - बहुभुज का बाहरी भाग)। "

इसके अलावा, जब एल्गोरिथ्म सीमा के किनारों में से एक के माध्यम से "आवक" गुजरता है, तो यह अगली सीमा के किनारे से "बाहर की ओर" गुजर जाएगा, अर्थात। वर्ग ट्रेस एल्गोरिथ्म उसी तरह से दो लगातार किनारों से गुजरने में सक्षम नहीं होना चाहिए।

अंतिम अवलोकन

प्रत्येक पैटर्न में सीमा किनारों की एक समान संख्या होती है ।

यदि आप चित्रा 5 से बहुभुज को देखते हैं, तो आप देख सकते हैं:

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

इसलिए, जब ट्रेसिंग वर्गों के लिए एल्गोरिथ्म दूसरी बार प्रारंभिक सीमा किनारे (प्रारंभिक पिक्सेल) के माध्यम से प्रवेश करता है, तो यह पहली बार के रूप में उसी दिशा में करेगा।

इसका कारण यह है कि चूंकि सीमा के किनारे से जाने के दो रास्ते हैं, और एल्गोरिथ्म बारी-बारी से भीतर और बाहर की ओर बढ़ता है, और सीमा किनारों की एक समान संख्या होती है, एल्गोरिथ्म दूसरी बार के लिए प्रारंभिक सीमा किनारे से होकर उसी तरह जाएगा। पहला वाला।

निष्कर्ष

4-जुड़े पैटर्न और पृष्ठभूमि के मामले में, स्क्वायर ट्रेस एल्गोरिथ्म पूरी सीमा का पता लगाएगा, अर्थात। समोच्च, पैटर्न और एकल ट्रेस के बाद काम करना बंद कर देगा, अर्थात। यह इसे फिर से ट्रेस नहीं करेगा, क्योंकि जब यह दूसरी बार प्रारंभिक सीमा तक पहुंचता है, तो यह पहली बार के समान ही प्रवेश करेगा। नतीजतन, जैकब के स्टॉप मानदंड के साथ स्क्वायर ट्रेस एल्गोरिथ्म किसी भी पैटर्न के काउंटर को सही ढंग से निर्धारित करेगा, बशर्ते कि पैटर्न और पृष्ठभूमि दोनों 4-जुड़े हों।

मूर के परिवेश का पता लगाना

विचार

मूर-नेबर ट्रेसिंग के पीछे का विचार सरल है; लेकिन इसे समझाने से पहले, हमें एक महत्वपूर्ण अवधारणा को समझाने की आवश्यकता है: एक पिक्सेल का मूर पड़ोस ।

मूर का पड़ोस

एक पिक्सेल P का मूर पड़ोस 8 पिक्सल का एक सेट है जिसमें उस पिक्सेल के साथ एक सामान्य शीर्ष या किनारे होता है। ऐसे पिक्सेल, जैसे P1, P2, P3, P4, P5, P6, P7 और P8 , चित्र 1 में दिखाए गए हैं।

मूर पड़ोस (जिसे 8-पड़ोसी या अप्रत्यक्ष पड़ोसी भी कहा जाता है ) एक महत्वपूर्ण अवधारणा है जिसे अक्सर साहित्य में संदर्भित किया जाता है।


अब हम मूर के परिवेश का पता लगाने वाले विचार से परिचित होने के लिए तैयार हैं।

एक डिजिटल पैटर्न होने दें, अर्थात काले पिक्सेल का एक समूह, सफेद पिक्सेल की पृष्ठभूमि पर, अर्थात ग्रिड पर; ब्लैक पिक्सेल ढूंढें और इसे " प्रारंभिक " पिक्सेल घोषित करें। (" प्रारंभिक " पिक्सेल को खोजने के कई तरीके हैं, लेकिन हम, पहले की तरह, निचले बाएँ कोने से शुरू करेंगे और क्रम में पिक्सेल के सभी स्तंभों को स्कैन करेंगे, जब तक कि हम पहले काले पिक्सेल नहीं पाते, जिसे हम " प्रारंभिक " घोषित करेंगे।)

अब फिर से, कल्पना कीजिए कि आप शुरू के पिक्सेल पर खड़े एक लेडीबग हैं, जैसा कि नीचे चित्र 2 में दिखाया गया है। सामान्यीकरण के नुकसान के बिना, हम पैटर्न को दक्षिणावर्त घुमाकर रूपरेखा का पता लगाएंगे। (कोई फर्क नहीं पड़ता कि हम किस दिशा को चुनते हैं, मुख्य बात यह है कि इसे एल्गोरिथ्म में लगातार उपयोग करना है)।

सामान्य विचार इस प्रकार है: हर बार जब हम काले पिक्सेल पी में आते हैं , तो हम वापस जाते हैं, अर्थात, उस सफेद पिक्सेल में, जिसमें आप पहले खड़े थे। फिर हम पिक्स पी के चारों ओर घूमते हैं, मूर के आसपास के हर पिक्सेल का दौरा करते हैं, जब तक कि हम ब्लैक पिक्सेल पर नहीं जाते। एल्गोरिथ्म तब समाप्त होता है जब स्टार्ट पिक्सेल दूसरी बार स्टार्ट पिक्सेल तक पहुँचता है।

उन ब्लैक पिक्सल्स जिन्हें एल्गोरिथ्म का दौरा किया गया है, पैटर्न की रूपरेखा होगी।

एल्गोरिथ्म

निम्नलिखित मूर पड़ोस अनुरेखण एल्गोरिथ्म का एक औपचारिक विवरण है:

इनपुट: काली कोशिकाओं से जुड़ा घटक P युक्त वर्गाकार टेसेलेशन टी ।

आउटपुट: सीमा पिक्सल की पंक्ति बी (बी ₁ , बी ₂ , ..., बी _के ) , यानी। सर्किट।

एम द्वारा निरूपित (ए) पिक्सेल के मूर पड़ोस।

आज्ञा देना वर्तमान सीमा पिक्सेल हो।

आइए c वर्तमान विचाराधीन पिक्सेल हो, अर्थात c , M (p) में है ।

शुरुआत

• B को एक खाली सेट के रूप में परिभाषित करें।
• नीचे से ऊपर तक और बाएं से दाएं, कोशिकाओं को तब तक स्कैन करें जब तक कि हम पी से एक काले रंग की पिक्सेल नहीं पाते ।
• बी में डालें ।
• हमने बिंदु s को वर्तमान सीमा बिंदु p के रूप में सेट किया है, अर्थात। पी = एस
• चलिए वापस चलते हैं, यानी चलो उस पिक्सेल पर चलते हैं जहाँ से हम s पर आए थे।
• C को M (p) में अगला क्लॉकवाइज पिक्सेल होने दें।
• जबकि c , s के बराबर नहीं है, निष्पादित करें
  
  
  • अगर c काला है
    
    • B में c डालें
    • हम p = c सेट करते हैं
    • वापस जाएं (वर्तमान पिक्सेल c को उस पिक्सेल पर ले जाएँ जहाँ से हमें p मिला है)
    
    अन्यथा
    
    • वर्तमान पिक्सेल को M (p) में अगली दक्षिणावर्त पिक्सेल में ले जाएँ
    
    बाय साइकिल का अंत

अंत

प्रदर्शन

निम्नलिखित मूर के पड़ोस ट्रेस पैटर्न की रूपरेखा का पता लगाने के तरीके का एक एनिमेटेड प्रदर्शन है। (हमने रूपरेखा को दक्षिणावर्त ट्रेस करने का निर्णय लिया।)

के विश्लेषण

मूर के परिवेश का पता लगाने में मुख्य कमजोरी मापदंड को रोकने के विकल्प में है।

मूर के परिवेश का पता लगाने के लिए एल्गोरिथम के मूल विवरण में, दूसरी बार प्रारंभिक पिक्सेल को हिट करने के लिए स्टॉपिंग मानदंड है। स्क्वायर ट्रेस एल्गोरिथ्म के समान, यह पता चला है कि इस मानदंड का उपयोग करके मूर के परिवेश का पता लगाना पैटर्न के एक बड़े परिवार के आकृति का पता नहीं लगा सकता है।

निम्नलिखित एक एनिमेटेड डेमो है जो यह बताता है कि एल्गोरिथ्म एक खराब रोक सीमा के चयन के कारण पैटर्न की सटीक रूपरेखा क्यों नहीं पा सकता है:


जैसा कि आप देख सकते हैं, ट्रेसिंग मानदंड में सुधार करना ट्रेस के समग्र प्रदर्शन को बेहतर बनाने के लिए एक अच्छी शुरुआत हो सकती है। जैकब शटडाउन मानदंड के समान शटडाउन मानदंड के लिए दो प्रभावी विकल्प हैं।

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

इसका कारण मुख्य रूप से है क्योंकि एल्गोरिदम अगले सीमा पिक्सेल के लिए खोज करने के लिए सीमा पिक्सेल के पूरे मूर पड़ोस की जांच करता है। स्क्वायर ट्रेस एल्गोरिथ्म के विपरीत, जो केवल बाएं और दाएं घूमता है और पिक्सल को "तिरछे" से याद करता है, मूर का पड़ोस ट्रेस हमेशा किसी भी जुड़े घटक की बाहरी सीमा का पता लगाने में सक्षम होगा। इसका कारण यह है: किसी भी 8-कनेक्टेड (या बस कनेक्टेड ) पैटर्न के लिए, अगला बॉर्डर पिक्सेल वर्तमान बॉर्डर पिक्सेल के मूर पड़ोस के भीतर स्थित है। क्योंकि मूर का पड़ोस मौजूदा सीमा पिक्सेल के मूर पड़ोस में प्रत्येक पिक्सेल की जांच करता है, इसे अगली सीमा पिक्सेल का पता लगाना चाहिए।

जब मुरा का पड़ोस ट्रेसिंग पिक्सेल में दूसरी बार उसी तरह पहुंचता है जैसे उसने पहली बार किया था, तो इसका मतलब है कि पैटर्न की पूरी बाहरी रूपरेखा का पता चला है, और यदि एल्गोरिथ्म को रोका नहीं गया है, तो यह फिर से उसी रूपरेखा का पता लगाएगा।

रेडियल स्कैन

रेडियल स्वीप एल्गोरिथ्म एक समोच्च पहचान एल्गोरिथ्म कुछ पुस्तकों में चर्चा की है। जटिल नाम के बावजूद, अंतर्निहित विचार बहुत सरल है। वास्तव में, यह पता चला है कि रेडियल स्वीप एल्गोरिथ्म मूर के परिवेश के समान है। एक पूछ सकता है: "हम उसका उल्लेख क्यों करते हैं?"

मूर के आसपास के वातावरण को एक निश्चित दिशा (वर्तमान में हमने दक्षिणावर्त दिशा चुना) के लिए मूर के आसपास के क्षेत्र में खोज करता है जब तक कि यह एक काला पिक्सेल न मिल जाए। वह उस पिक्सेल को वर्तमान सीमा पिक्सेल घोषित करता है और जारी रखता है।

रेडियल स्कैन एल्गोरिथ्म वही करता है। दूसरी ओर, यह किसी दिए गए सीमा पिक्सेल के मूर पड़ोस में अगले ब्लैक पिक्सेल को खोजने का एक दिलचस्प तरीका प्रदान करता है।

विधि निम्नलिखित विचार पर आधारित है:

हर बार जब हम एक नई सीमा पिक्सेल पाते हैं, तो इसे वर्तमान पिक्सेल P बनाते हैं, और P को पिछले सीमा पिक्सेल से जोड़ने वाला एक काल्पनिक रेखा खंड बनाते हैं। तब P को दक्षिणावर्त तब खंड को घुमाएं जब तक कि यह पिक्सेल P के मूर पड़ोस में एक काले पिक्सेल के पार न आ जाए । मूर पी के आसपास के प्रत्येक पिक्सेल की जांच करने के लिए लाइन का रोटेशन समान है ।

हमने एक एनिमेटेड प्रदर्शन बनाया कि रेडियल स्कैन एल्गोरिदम कैसे काम करता है और यह मूर के परिवेश को कैसे ट्रेस करता है।


और रेडियल स्वीप एल्गोरिदम कब बंद होता है?

आइए निम्नलिखित स्टॉपिंग मानदंड का उपयोग करके एल्गोरिथ्म के व्यवहार की व्याख्या करें ...

कसौटी बंद करो १

रेडियल स्कैन एल्गोरिथ्म को पूरा होने दें, जब यह दूसरी बार प्रारंभिक पिक्सेल पर जाता है।

नीचे एक एनिमेटेड डेमो है, जिसमें से यह स्पष्ट है कि ब्रेक मानदंड को सही ढंग से क्यों बदला जाएगा।


यह भी ध्यान देने योग्य है कि दोनों एल्गोरिदम में इस स्टॉपिंग मानदंड का उपयोग करते समय, रेडियल स्कैन एल्गोरिथ्म की प्रभावशीलता मूर के परिवेश के अनुरेखण के समान है।

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

हैं तो याकूब की रोक मानदंड को एल्गोरिथ्म को निष्पादित करना बंद करना पड़ता है । दुर्भाग्य से, हम रेडियल स्वीप एल्गोरिदम में जेकब स्टॉप मानदंड का उपयोग नहीं कर सकते हैं। कारण यह है कि रेडियल स्कैन एल्गोरिथ्म अवधारणा को परिभाषित नहीं करता है

"दिशा" जिसमें यह सीमा पिक्सेल को हिट करता है । दूसरे शब्दों में, यह "दिशा" स्पष्ट नहीं है जिसमें एल्गोरिथ्म सीमा पिक्सेल में गिर गया (और इसकी परिभाषा nontrivial है)।

इसलिए, हमें एक और रोक मानदंड का प्रस्ताव करने की आवश्यकता है, जो एक निश्चित पिक्सेल मारने की दिशा पर निर्भर नहीं करता है, जो रेडियल स्कैन एल्गोरिथ्म की प्रभावशीलता में सुधार कर सकता है ...

कसौटी 2 बंद करो

मान लें कि हर बार एल्गोरिथ्म एक नई सीमा पिक्सेल P _{i का} पता लगाता है , इसे सीमा पिक्सेल की श्रृंखला में डाला जाता है : P ₁ , P ₂ , P ₃ , ..., P _i ; और वर्तमान सीमा पिक्सेल के रूप में घोषित किया गया। ( पी ₁ हम प्रारंभिक पिक्सेल पर विचार करेंगे )। इसका मतलब यह है कि हम प्रत्येक मौजूदा बॉर्डर पिक्सेल P _i के पिछले बॉर्डर पिक्सेल P _{i-1 को} जानते हैं । ( शुरुआती पिक्सेल के लिए , हम मान लेंगे कि पी _{0 है}एक काल्पनिक पिक्सेल है जो ग्रिड पर किसी भी पिक्सेल के लिए किसी भी तरह से कोई नहीं है जो सीमा पिक्सेल की पंक्ति में प्रारंभिक पिक्सेल का सामना करता है )।

उपरोक्त मान्यताओं के आधार पर, हम निम्न मानदंड निर्धारित कर सकते हैं:

एल्गोरिथ्म निष्पादन तब बंद हो जाता है:

a) वर्तमान सीमा पिक्सेल P _i , जो पहले पिक्सेल P _j (जहाँ j <i ) सीमा पिक्सेल की एक श्रृंखला के रूप में मिला है, और

b: P _{i- 1} = पी _{जे -1} ।

दूसरे शब्दों में, एल्गोरिथ्म निष्पादन को पूरा करता है जब यह दूसरे में सीमा पिक्सेल पी पर जाता हैयदि दूसरी बार P के पहले सीमा पिक्सेल (सीमा पिक्सेल की पंक्ति में) एक ही पिक्सेल है, तो यह P से पहले P के पहली बार देखे जाने पर था ।

यदि स्टॉप मानदंड की स्थिति संतुष्ट है और एल्गोरिथ्म बंद नहीं होता है, तो रेडियल स्कैन एल्गोरिथ्म दूसरी बार उसी सीमा का पता लगाना जारी रखेगा ।

इस स्टॉपिंग मानदंड के साथ रेडियल स्वीप एल्गोरिदम का प्रदर्शन मूर पड़ोस को याकूब को रोकने के मानदंड के प्रदर्शन के समान है।

थियो पावलिडिस एल्गोरिथम

विचार

यह एल्गोरिथ्म Theo Pavlidis द्वारा प्रस्तावित नवीनतम लूप डिटेक्शन एल्गोरिदम में से एक है । उन्होंने अपनी 1982 की पुस्तक एल्गोरिथम फॉर ग्राफिक्स एंड इमेज प्रोसेसिंग (अध्याय 7, खंड 5) में इसका हवाला दिया । यह वर्गों या मूर के परिवेश का पता लगाने के लिए एल्गोरिथ्म के रूप में इतना सरल नहीं है, लेकिन यह इतना जटिल नहीं है (यह सबसे समोच्च पहचान एल्गोरिदम की विशेषता है)।

हम इस एल्गोरिथ्म को उसी तरह नहीं समझाएंगे जैसे यह उनकी पुस्तक में किया गया था। हमारा दृष्टिकोण समझना आसान है और एल्गोरिथ्म में अंतर्निहित सामान्य विचार का एक विचार देता है।

सामान्यीकरण के नुकसान के बिना, हमने लेख में प्रस्तुत अन्य सभी एल्गोरिदम के क्रम से मिलान करने के लिए लूप क्लॉकवाइज के चारों ओर जाने का फैसला किया। दूसरी ओर, पावलिडिस ने दिशा को वामावर्त चुना। यह एल्गोरिथ्म के प्रदर्शन को प्रभावित नहीं करेगा। एकमात्र अंतर आंदोलनों की सापेक्ष दिशा है जो हम समोच्च के चारों ओर जाने पर करेंगे।

अब आइए विचार पर

चलते हैं ... मान लें कि हमारे पास एक डिजिटल पैटर्न है, अर्थात्। सफेद पिक्सेल की पृष्ठभूमि पर काले पिक्सेल का एक समूह, अर्थात ग्रिड पर; ब्लैक पिक्सेल ढूंढें और इसे " प्रारंभिक " पिक्सेल घोषित करें । आप " शुरुआती " पिक्सेल को विभिन्न तरीकों से खोज सकते हैं, उदाहरण के लिए, जैसा कि ऊपर वर्णित है। प्रारंभिक

खोजने के लिएइस विधि का उपयोग करने के लिए पिक्सल वैकल्पिक है। इसके बजाय, हम एक शुरुआती पिक्सेल का चयन करेंगे जो एक शुरुआती पिक्सेल का चयन करने के लिए पाव्लिडिस एल्गोरिथ्म द्वारा लगाए गए निम्नलिखित प्रतिबंधों को संतुष्ट करता है:

जिस दिशा में हम शुरू करने वाले पिक्सेल

में प्रवेश करते हैं, उस दिशा में एक महत्वपूर्ण सीमा वास्तव में, आप इस शर्त के तहत शुरुआती स्ट्रीमिंग के रूप में किसी भी ब्लैक बॉर्डर पिक्सेल का चयन कर सकते हैं : यदि आप शुरू में खड़े होते हैं उस पर, बाएं पड़ोसी पिक्सेल काला नहीं है। दूसरे शब्दों में, आपको शुरुआती पिक्सेल को ऐसी दिशा में दर्ज करने की आवश्यकता है कि बाईं पड़ोसी पिक्सेल सफेद है ("बाएं" यहां उस दिशा के सापेक्ष लिया गया है जिसमें हम शुरुआती पिक्सेल दर्ज करते हैं )।

अब सोचिए कि आप एक लेडीबग हैं, जो खड़ी हैपिक्सेल शुरू करना , जैसा कि नीचे चित्र 1 में दिखाया गया है । एल्गोरिथ्म के निष्पादन के दौरान, हम आपके सामने केवल तीन पिक्सेल में रुचि रखेंगे, अर्थात। चित्र 1 में दिखाया गया P1, P2 और P3 । (हम द्वारा निरूपित P2 पिक्सेल से पहले आप, P1 - की बाईं करने के लिए एक पिक्सेल है P2 , और पी 3 पिक्सेल का सही - P2 )।


स्क्वायर ट्रेस एल्गोरिथ्म के साथ के रूप में, पाव्लिडिस एल्गोरिथ्म में सबसे महत्वपूर्ण बात "दिशा की भावना" है। बाएं और दाएं मोड़ वर्तमान स्थिति के सापेक्ष हैं, जो इस बात पर निर्भर करता है कि आपने वर्तमान पिक्सेल में कैसे प्रवेश किया। इसलिए, सही चाल बनाने के लिए, अपने वर्तमान अभिविन्यास पर नज़र रखना महत्वपूर्ण है। लेकिन कोई फर्क नहीं पड़ता कि आप कैसे स्थित हैं, पिक्सेल पी 1, पी 2 और पी 3 को ऊपर वर्णित के अनुसार निर्धारित किया जाता है।

इस जानकारी के होने के बाद, हम एल्गोरिदम को समझाने के लिए तैयार हैं ...

हर बार जब आप वर्तमान सीमा पिक्सेल (जो कि शुरुआती पिक्सेल हैं) पर खड़े होते हैं , तो हम निम्नलिखित करते हैं:

सबसे पहले , पिक्सेल P1 की जाँच करें । यदि पी 1 काला है, तो पी 1 घोषित करेंवर्तमान सीमा पिक्सेल और एक कदम आगे बढ़ाएं, और फिर P1 पर बाईं ओर एक कदम उठाएं ( चालों का क्रम बहुत महत्वपूर्ण है)।

में चित्र 2 नीचे इस मामले को दिखाता है। P1 पर जाने का मार्ग नीले रंग में दिखाया गया है।


और केवल अगर पी 1 सफेद है, हम पी 2 की जांच करने के लिए आगे बढ़ते हैं ...

यदि पी 2 काला है, तो पी 2 को वर्तमान सीमा पिक्सेल घोषित करें और पी 2 पर होने के लिए एक कदम आगे बढ़ाएं । यह मामला नीचे चित्र 3 में दिखाया गया है । पी 2 पर आपको जिस पथ का अनुसरण करने की आवश्यकता है, वह नीले रंग में दिखाया गया है।


केवल अगर पी 1 और पी 2 दोनों सफेद हैं, तो पी 3 की जांच करें ...

यदि पी 3 काला है, तो पी 3 को वर्तमान सीमा पिक्सेल घोषित करें और एक कदम दाईं ओर ले जाएं, और फिर बाईं ओर एक कदम , जैसा कि नीचे चित्र 4 में दिखाया गया है।


वह सब है! तीन सरल मामलों के लिए तीन सरल नियम। जैसा कि आप देख सकते हैं, कॉर्नरिंग करते समय अपनी दिशा पर नज़र रखना महत्वपूर्ण है, क्योंकि सभी चालें वर्तमान अभिविन्यास के सापेक्ष बनाई गई हैं। लेकिन ऐसा लगता है कि हम कुछ भूल गए? अगर हमारे सामने तीनों पिक्सेल सफेद हैं तो क्या होगा? फिर हम अपने सामने तीन पिक्सेल का एक नया सेट देखने के लिए 90 डिग्री दक्षिणावर्त घुमाते हैं (वर्तमान सीमा पिक्सेल पर खड़े हैं)। फिर हम इन नए पिक्सेल के लिए एक ही जाँच करते हैं। आपके पास अभी भी एक प्रश्न हो सकता है: क्या होगा अगर ये तीनों पिक्सेल सफेद हैं! फिर फिर से हम 90 डिग्री दक्षिणावर्त मुड़ते हैं, उसी पिक्सेल पर खड़े होते हैं। इससे पहले कि आप मूर के पिक्सेल के पूरे पड़ोस की जांच करें, आप तीन बार (प्रत्येक बार 90 डिग्री दक्षिणावर्त) घूम सकते हैं।

यदि हम कभी भी ब्लैक पिक्सल्स को देखे बिना तीन बार घुमाते हैं, तो इसका मतलब है कि हम एक अलग पिक्सेल पर खड़े हैं , किसी अन्य ब्लैक पिक्सेल से नहीं जुड़े हैं। यही कारण है कि एल्गोरिथ्म आपको तीन बार घुमाने की अनुमति देता है, और फिर इसका निष्पादन पूरा करता है।

एक अन्य पहलू: एल्गोरिथ्म कब पूरा होता है?

एल्गोरिथ्म दो मामलों में समाप्त होता है:

ए) जैसा कि ऊपर उल्लेख किया गया है। एल्गोरिथ्म आपको तीन बार (90 डिग्री हर बार दक्षिणावर्त) घुमाने की अनुमति देता है, क्योंकि यह निष्पादन को पूरा करता है और पिक्सेल को अलग-थलग करने की घोषणा करता है या

b) जब वर्तमान सीमा पिक्सेल प्रारंभिक पिक्सेल होता है, तो एल्गोरिथ्म "घोषणा" करके निष्पादन को पूरा करता है जो पैटर्न की रूपरेखा का पता लगाता है।

एल्गोरिथ्म

निम्नलिखित पावलिडिस एल्गोरिथ्म का एक औपचारिक विवरण है:

इनपुट: स्क्वायर सेसलेशन टी जिसमें काले कोशिकाओं का एक जुड़ा हुआ घटक P होता है।

आउटपुट: सीमा पिक्सल की पंक्ति बी (बी ₁ , बी ₂ , ..., बी _के ) , यानी। सर्किट।

परिभाषाएं:

• की तरह निरूपित पी वर्तमान सीमा पिक्सेल, अर्थात पिक्सेल जिस पर हम खड़े हैं।
• P1, P2 और P3 को निम्नानुसार परिभाषित करें : (ऊपर चित्र 1 भी देखें)
• पी 2 आपके सामने पिक्सेल है, आप जिस पर खड़े हैं, उससे सटे, यानी पिक्सेल के साथ पी ।
• P1 — , P2 .
• P3 — , P2 .
• «» .

शुरुआत

• B .
• T , s P (. , )
• s B .
• p s .
• :
  P1
  
  • P1 B
  • p=P1
  • ,
  
  P2
  
  • P2 B
  • p=P2
  • (. 3)
  
  P3
  
  • P3 B
  • p=P3
  • , (. 4)
  
  90 , p
  
  • कार्यक्रम को समाप्त करें और p को एक पृथक पिक्सेल घोषित करें
  
  अन्यथा
  
  • 90 डिग्री दक्षिणावर्त घुमाएँ, वर्तमान पिक्सेल पी पर खड़े
  
  अब तक p = s (दोहराव समाप्त करें)

अंत

प्रदर्शन

निम्नलिखित एक एनिमेटेड प्रदर्शन है कि कैसे पैवेलिडिस एल्गोरिथ्म एक दिए गए पैटर्न के समोच्च का पता लगाता है। मत भूलो कि हम पिक्सेल में चलते हैं; ध्यान दें कि बाएं या दाएं मुड़ते समय ओरिएंटेशन कैसे बदलता है। एल्गोरिथ्म को अधिक से अधिक विस्तार से समझाने के लिए, हमने इसमें सभी संभावित मामलों को शामिल किया।

के विश्लेषण

यदि आपको लगता है कि पैवेलिडिस एल्गोरिथ्म पैटर्न की रूपरेखाओं का पता लगाने के लिए आदर्श है, तो आपको अपना विचार बदलना चाहिए ...

यह एल्गोरिथ्म मूर के परिवेश का पता लगाने की तुलना में वास्तव में थोड़ा अधिक जटिल है, जिसमें कोई विशेष मामले नहीं हैं जो अलग-अलग प्रसंस्करण करते हैं, लेकिन वह एक बड़ी रूपरेखा की रूपरेखा निर्धारित करने में सक्षम नहीं होंगे। पैटर्न का एक परिवार जिसमें एक निश्चित प्रकार की कनेक्टिविटी होती है।

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


एक एल्गोरिथ्म को संशोधित करने के दो सरल तरीके हैं जो इसके प्रदर्शन को बेहतर बनाने में मदद करते हैं।

a) स्टॉपिंग मापदंड को बदलने के

बजाय एल्गोरिथ्म को पूरा करने के बजाय जब यह दूसरी बार स्टार्ट पिक्सेल पर जाता है, तो आप इसे समाप्त कर सकते हैं जब यह शुरू करने वाले पिक्सेल को तीसरी या चौथी बार भी देखता है। यह एल्गोरिथ्म के समग्र प्रदर्शन में सुधार करेगा।

या

b) प्रारंभ पिक्सेल का चयन करने से पहले समस्या के स्रोत पर पहुंचें, अर्थात्,

उस दिशा के संबंध में एक महत्वपूर्ण सीमा है जिसमें प्रारंभ पिक्सेल में प्रवेश किया जाता है। अनिवार्य रूप से, आपको प्रारंभ पिक्सेल दर्ज करने की आवश्यकता है ताकि जब आप उस पर खड़े हों, तो आपके बाईं ओर का पिक्सेल सफेद हो। इस प्रतिबंध को शुरू करने का कारण यह है: क्योंकि हम हमेशा हमारे सामने तीन पिक्सल को देखते हैंएक निश्चित क्रम में , कुछ पैटर्न में हम सीमा पिक्सेल को सीधे प्रारंभिक पिक्सेल के बाईं ओर छोड़ देंगे।

हमें प्रारंभिक पिक्सेल से न केवल बाएं पड़ोसी पिक्सेल को गायब करने का जोखिम है, बल्कि इसके ठीक नीचे पिक्सेल (जैसा कि विश्लेषण में प्रदर्शित किया गया है)। इसके अलावा, कुछ पैटर्न में, नीचे चित्र 5 में पिक्सेल आर के समान एक पिक्सेल को छोड़ दिया जाएगा । इसलिए, हम मानते हैं कि शुरुआती पिक्सेल को इस तरह से हिट करने की आवश्यकता है कि नीचे दिए गए चित्र 5 में दिखाए गए पिक्सेल एल, डब्ल्यू और आर के अनुरूप पिक्सेल सफेद हैं।


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