कैनी बाउंड्री डिटेक्टर

आपका दिन शुभ हो!

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

अपने खाली समय में, आत्म-शिक्षा के उद्देश्य के लिए, मैं एल्गोरिदम (मशीन दृष्टि सहित) का अध्ययन करता हूं। मैं इसे अनप्रोफेशनली कर रहा हूं, काफी हद तक वैज्ञानिक साहित्य या अपने स्वयं के एल्गोरिदम समाधानों का पालन कर रहा हूं।
एक ओर कोडिंग को सरल बनाने के लिए, और दूसरी ओर ब्रेनफैक प्रोग्रामिंग के कथात्मक नोट्स देने के लिए, मैं कंप्यूटर बीजगणित के वातावरण में कार्यान्वयन को दिखाऊंगा Mathcad (एल्गोरिदम का परीक्षण 13 और 14 के संस्करणों में किया गया था, जिसमें विशिष्ट अंतर्निहित विधियों का कम उपयोग संभव था। यह दृष्टिकोण, मेरी राय में, प्रदर्शन की धारणा में सुधार करता है, और एल्गोरिदम के अन्य डिजाइन / विकास वातावरण में संभव हस्तांतरण की सुविधा देता है। यह ध्यान दिया जाना चाहिए कि कैनी डिटेक्टर ऑपरेशन के कुछ चरण न केवल विभिन्न अनुकूलन (उदाहरण के लिए, प्रोसेसर कमांड सिस्टम के SIMD एक्सटेंशन का उपयोग करके सोबेल ऑपरेटर के सॉफ्टवेयर कार्यान्वयन) को लागू कर सकते हैं, बल्कि कुछ ऑपरेटरों (विधियों) को दूसरों की जगह लेने की संभावना भी है (उदाहरण के लिए, सोबेल ऑपरेटर को बदला जा सकता है) रॉबर्ट्स या प्रुइट द्वारा ऑपरेटर), और ऑपरेटरों के मापदंडों को निर्दिष्ट करने वाले गुणांक को अलग करने की संभावना।
यह संस्करण मैथकड वातावरण में कार्यान्वयन में अधिकतम आसानी के कारणों के लिए बनाया गया था, संभवतः गति और पहचान की गुणवत्ता के मामले में प्रदर्शन की गिरावट के लिए, और इसे कैनी डिटेक्टर के कामकाज के मुख्य चरणों के प्रदर्शन के रूप में प्रस्तुत किया गया है।

सीमा बांधना

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

कार्य

एल्गोरिथ्म के प्रदर्शन के रूप में, अगली छवि में सीमाओं को उजागर करने का कार्य हल किया जाएगा।

एल्गोरिथ्म में पाँच अलग-अलग चरण होते हैं:

1. चिकना करना । शोर को हटाने के लिए धुंधला छवि।
2. ग्रेडियरों के लिए खोजें । सीमाओं को चिह्नित किया जाता है जहां छवि ढाल अपने अधिकतम मूल्य पर ले जाता है।
3. गैर-मैक्सिमा का दमन । केवल स्थानीय अधिकतम सीमा के रूप में चिह्नित हैं।
4. डबल सीमा फ़िल्टरिंग । संभावित सीमाएं थ्रेसहोल्ड द्वारा निर्धारित की जाती हैं।
5. अस्पष्टता क्षेत्र का पता लगाएं । परिणामी सीमाएं उन सभी किनारों को दबाकर निर्धारित की जाती हैं जो कुछ (मजबूत) सीमाओं से संबंधित नहीं हैं।

डिटेक्टर का उपयोग करने से पहले, हम कम्प्यूटेशनल लागत को कम करने के लिए छवि को ग्रे के रंगों में परिवर्तित करते हैं। यह चरण कई छवि प्रसंस्करण विधियों की विशेषता है।

ग्रेस्केल में परिवर्तित करें

मूल छवि को ग्रेस्केल में छवि में बदलने के लिए, आपको इसके "चमक" घटक को प्राप्त करने की आवश्यकता है। इसके लिए, छवि को YUV रंग मॉडल (या एचएसएल, एचएसवी, अन्य) में प्रस्तुत करना सुविधाजनक है।
प्रारंभ में, चित्र को RGB रंग मॉडल में प्रस्तुत किया जाता है, और डाउनलोड फ़ंक्शन एक मैट्रिक्स के रूप में तीन घटक देता है।

छवि को YUV मॉडल में स्थानांतरित करने के लिए, हम निम्नलिखित ऑपरेशन करते हैं।
हम मॉडल (आर, जी, बी) के घटकों का वर्णन करने वाले मैट्रीस प्राप्त करते हैं:


हम YUV मॉडल के Y- घटक की गणना करते हैं:


अनुवाद गुणांक (वे मानवीय धारणा की विशेषताओं द्वारा स्थिर और निर्धारित हैं, और यह उस व्यक्ति की स्थिति से ठीक है जिसे हम यहां सीमाओं का मूल्यांकन करते हैं):


रूपांतरण परिणाम:

चौरसाई

शोर को दबाने के लिए, हम छवि धुंधली गॉसियन फ़िल्टर का उपयोग करते हैं।
दो आयामी मामले के लिए गॉस कार्य:

पैरामीटर that के साथ आकार आकार के फिल्टर कोर को बनाने वाली विधि:

प्रक्रिया, मैट्रिक्स आकार मैट्रिक्स के आकार और पैरामीटर के कर्नेल के साथ एक फ़िल्टर लागू करना:

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

हम σ = 1.0 चुनते हैं।
फ़िल्टर कोर बहुत जल्दी शून्य से कम हो जाता है जब बिंदु (0, 0) से दूर जा रहा है, और इसलिए, व्यवहार में, हम अपने आप को एक छोटी सी खिड़की (0, 0) के आसपास के साथ दृढ़ संकल्प तक सीमित कर सकते हैं (उदाहरण के लिए, तीन सिगनल नियम द्वारा निर्देशित, हम विंडो त्रिज्या को 3σ के बराबर लेते हैं)। नीचे पैरामीटर is और एक अलग कोर आकार (पैरामीटर आकार ) के एक निश्चित मूल्य के साथ एक फिल्टर लगाने का परिणाम है।

आकार = 7 चुनें। चयनित मापदंडों के साथ फ़िल्टर को लागू करने का परिणाम ऊपर की आकृति में दिखाया गया है।

ग्रेडिएंट सर्च

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

कार्यान्वयन (एक ढाल वेक्टर के लिए प्रत्येक बिंदु को मैप करता है):

वेक्टर का कोण 45 ° से परिमाणित होता है - ये ऐसे मान हैं जो निम्न चरणों में से एक के लिए आवश्यक हैं।
नीचे दिया गया आंकड़ा ऑपरेटर को एक धुंधली (ए) और मूल (ग्रेस्केल में) छवि (बी) पर लागू करने का परिणाम दिखाता है।

गैर-मैक्सिमा का दमन

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

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

मूल्य तुलना:

दमन कार्यान्वयन:

गैर-मैक्सिमा को दबाने के बाद, किनारे अधिक सटीक और पतले हो गए।

नीचे, पहले आंकड़े में, पूरे मूल (यानी, दमन से पहले) छवि के प्रस्तुतिकरण के ग्रेडिएंट्स (कोण 45 ° के गुणक हैं) और दूसरे में - एक छोटा सा टुकड़ा।

दोहरी सीमा फ़िल्टरिंग

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

55% और 60% सीमा के थ्रेसहोल्ड का उपयोग करने का परिणाम नीचे दिए गए आंकड़े में दिखाया गया है।

विसंगति क्षेत्र ट्रेस

सरलीकृत, कार्य पिक्सेल के समूहों का चयन करना है जो पिछले चरण में एक मध्यवर्ती मूल्य प्राप्त करते हैं, और उन्हें सीमा पर असाइन करते हैं (यदि वे किसी निर्धारित सीमा से जुड़े हैं) या उन्हें दबाएं (अन्यथा)। यदि यह 8 दिशाओं में से किसी एक के संपर्क में आता है, तो एक पिक्सेल समूह में जोड़ा जाता है।
कार्यान्वयन:

ट्रेस परिणाम:

सूत्रों की सूची

विकास प्रक्रिया में, मैंने निम्नलिखित स्रोतों का उपयोग किया (मुख्यतः [1]):

1. कैनी एज डिटेक्शन www.cvmt.dk/education/teaching/f09/VGIS8/AIP
2. विकिपीडिया। एज डिटेक्शन en.wikipedia.org/wiki/Edge_detection
3. विकिपीडिया। Sobel Operator ru.wikipedia.org/wiki/Sobel_Operator
4. रेखापुंज ग्राफिक्स की एल्गोरिथम मूल बातें www.intuit.ru/depbox/graphics/rastrgraph/8/rastrgraph_8.html

मुझे आलोचना और टिप्पणियों पर खुशी होगी, क्योंकि मशीन दृष्टि का क्षेत्र मेरी पेशेवर गतिविधि से संबंधित नहीं है।

अद्यतन और यहाँ आलोचना है। एल्गोरिथ्म में मौलिक त्रुटियों और लेख के लिंक के लिए ( यहां ) इंगित करने के लिए andivivanoff का धन्यवाद।

upd2 andreyivanoff यहाँ एल्गोरिथम पर महत्वपूर्ण टिप्पणी देता है ।