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

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

यह एक कार्य की तरह दिखता है जिसे स्वचालित करना आसान है। ऐसा करने के लिए, यह एक प्रोग्राम बनाने के लिए पर्याप्त है जो बैनर पर "मूल्य टैग" के लिए एक स्थानीयकृत मूल्य रिक्त करेगा और बटन पर कार्रवाई ("अब खरीदें" जैसा वाक्यांश) को कॉल करेगा। यदि किसी चित्र में टेक्स्ट प्रिंट करना काफी सरल है, तो यह निर्धारित करना कि आपको इसे कहाँ रखना है, यह हमेशा मामूली नहीं है। पेपरकॉर्न कहते हैं कि बटन अलग-अलग रंगों में आता है, और आकार में थोड़ा अलग है।

यह लेख समर्पित है: चित्र में निर्दिष्ट ऑब्जेक्ट कैसे ढूंढें? लोकप्रिय तरीकों को हल किया जाएगा; आवेदन, सुविधाओं, पेशेवरों और विपक्ष के क्षेत्र। उपरोक्त तरीकों का उपयोग अन्य उद्देश्यों के लिए किया जा सकता है: सुरक्षा कैमरों के लिए विकासशील कार्यक्रम, परीक्षण यूआई के स्वचालन, और जैसे। वर्णित कठिनाइयों को अन्य कार्यों में पाया जा सकता है, और उपयोग किए गए तरीकों का उपयोग अन्य उद्देश्यों के लिए किया जा सकता है। उदाहरण के लिए, कैनी एज डिटेक्टर का उपयोग अक्सर छवियों को प्रीप्रोसेस करने के लिए किया जाता है, और किसी छवि की "जटिलता" के मूल्यांकन के लिए कीपॉइंट की संख्या का उपयोग किया जा सकता है।

मुझे उम्मीद है कि वर्णित समाधान समस्याओं को हल करने के लिए आपके शस्त्रागार उपकरण और चाल की भरपाई करेंगे।

कोड पायथन 3.6 ( रिपॉजिटरी ) में है; OpenCV पुस्तकालय की आवश्यकता पाठक से रैखिक बीजगणित और कंप्यूटर दृष्टि की मूल बातें समझने की उम्मीद की जाती है।

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

टेम्पलेट मिलान

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

आप एक मीट्रिक के रूप में विभिन्न विकल्पों का उपयोग कर सकते हैं, उदाहरण के लिए, टेम्पलेट और चित्र के बीच चुकता अंतर का योग (वर्ग अंतर, SSD का योग), या क्रॉस-सहसंबंध (CCORR) का उपयोग करें। एफ और जी आयामों (के, एल) और (एम, एन) के साथ क्रमशः छवि और पैटर्न हो सकते हैं (हम अब तक रंग चैनलों की उपेक्षा करेंगे); i, j - उस छवि पर स्थिति जिस पर हमने "टेम्पलेट" संलग्न किया है।

$$

$$SSD_ {i, j} = \ sum_ {a = 0..m, b = 0..n} {(f_ {i + a, j + b} - g_ {a, b}) ^ 2}$$

$$

$$CCORR_ {i, j} = \ sum_ {a = 0..m, b = 0..n} {(f_ {i + a, j + b} \ cdot g_ {a, b}) ^ 2}$$

चलो एक बिल्ली का बच्चा खोजने के लिए वर्गों के अंतर को लागू करने का प्रयास करें

चित्र में

(पेटा कैरिंग फॉर कैट्स से ली गई तस्वीर)।

बाईं तस्वीर टेम्पलेट के चित्र में स्थान की समानता का मीट्रिक मूल्य है (यानी, अलग-अलग i, j के लिए SSD मान)। डार्क एरिया वह जगह है जहां अंतर न्यूनतम होता है। यह उस जगह के लिए एक संकेतक है जो सबसे अधिक एक टेम्पलेट जैसा दिखता है - सही तस्वीर में यह जगह परिचालित है।

क्रॉस-सहसंबंध वास्तव में दो छवियों का एक दृढ़ संकल्प है। तेजी से फूरियर रूपांतरण का उपयोग करके वार्तालापों को जल्दी से लागू किया जा सकता है। कनवल्शन प्रमेय के अनुसार, फूरियर रूपांतरण के बाद, कनविक्शन एक सरल तत्व के गुणन में बदल जाता है:

$$

$$CCORR_ {i, j} = f \ circledast g = IFFT (FFT (f \ circledast g)) = IFFT (FFT (f) \ cdot FFT (g))$$

जहाँ $$$\ $ - कनविक्शन ऑपरेटर। इस तरह हम जल्दी से क्रॉस-सहसंबंध की गणना कर सकते हैं। यह ओ (kllog (kl) + mnlog (mn)) , बनाम O (klmn) की समग्र जटिलता देता है जब सिर पर लागू किया जाता है। अंतर के वर्ग को भी कनवल्शन का उपयोग करके महसूस किया जा सकता है, क्योंकि ब्रैकेट खोलने के बाद यह छवि के पिक्सेल मानों और क्रॉस-सहसंबंध के वर्गों के योग के बीच अंतर में बदल जाएगा:

$$

$$SSD_ {i, j} = \ sum_ {a = 0..m, b = 0..n} {(f_ {i + a, j + b} - g_ {a, b}) ^ 2} =$$

$$

$$= \ sum_ {a = 0..m, b = 0..n} {f_ {i + a, j + b} ^ 2 - 2 f_ {i + a, j + b} g_ {a, b} + g_ {a, b} ^ 2} =$$

$$

$$= \ sum_ {a = 0..m, b = 0..n} {f_ {i + a, j + b} ^ 2 + g_ {a, b} ^ 2} - 2CCOR_ {i, j}$$

विवरण इस प्रस्तुति में देखा जा सकता है।

आइए कार्यान्वयन के लिए आगे बढ़ें। सौभाग्य से, इंटेल के निज़नी नोवगोरोड विभाग के सहयोगियों ने ओपनसीवी लाइब्रेरी बनाकर हमारा ध्यान रखा, यह पहले से ही मैचटेम्पलेट विधि का उपयोग करके एक टेम्पलेट खोज को लागू करता है (वैसे, यह एफएफटी के माध्यम से कार्यान्वयन का उपयोग करता है, हालांकि यह प्रलेखन में उल्लेख नहीं किया गया है), विभिन्न विसंगतियों का उपयोग करके मैट्रिक्स :

• CV_TM_SQDIFF - पिक्सेल मानों में अंतर के वर्गों का योग
• CV_TM_SQDIFF_NORMED - वर्ग अंतर का योग, सामान्य श्रेणी के लिए 0..1।
• CV_TM_CCORR - टेम्पलेट और छवि खंड के तत्व-बाय-एलिमेंट उत्पादों का योग
• CV_TM_CCORR_NORMED - श्रेणी -1 के लिए सामान्यीकृत तत्व का योग।
• CV_TM_CCOEFF - औसत के बिना छवियों का क्रॉस-सहसंबंध
• CV_TM_CCOEFF_NORMED - औसत के बिना छवियों के बीच क्रॉस-सहसंबंध, सामान्यीकृत -1..1 (पियर्सन सहसंबंध)

हम एक बिल्ली का बच्चा खोजने के लिए उनका उपयोग करेंगे:

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

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

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

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

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

इसी समय, बैनर पर बटन विभिन्न प्रकार, रंग और आकार के होंगे:

बटन को आकार देने के मामले में, विधि सही ढंग से काम नहीं करती है। यह इस तथ्य के कारण है कि विधि में क्षैतिज और लंबवत दोनों समान समय में बटन को आकार देना शामिल है। हालांकि, यह हमेशा मामला नहीं होता है। सही तस्वीर में, बटन का आकार लंबवत नहीं बदला है, लेकिन क्षैतिज रूप से बहुत कम हो गया है। यदि आकार बदलना बहुत बड़ा है, तो लॉग-ध्रुवीय परिवर्तन के कारण होने वाली विकृतियाँ खोज को अस्थिर बनाती हैं। इस संबंध में, विधि तीसरे मामले में बटन का पता नहीं लगा सकी।

कीपॉइंट डिटेक्शन

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

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

हैरिस कॉर्नर डिटेक्टर

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

1. तीव्रता से $$$मैं$ एक्स और वाई अक्ष के साथ डेरिवेटिव हैं ( $$$I_x$ और $$$I_y$ क्रमशः)। उन्हें पाया जा सकता है, उदाहरण के लिए, सोबेल फ़िल्टर को लागू करके।

   
   

2. एक पिक्सेल के लिए, वर्ग पर विचार करें $$$I_x$ वर्ग $$$I_y$ और काम करता है $$$I_x$ और $$$I_y$ । कुछ स्रोत उन्हें लेबल करते हैं $$$I_ {xx}$ । $$$I_ {xy}$ और $$$I_ {xy}$ - जो स्पष्टता नहीं जोड़ता है, क्योंकि कोई सोच सकता है कि ये तीव्रता का दूसरा व्युत्पन्न है (और ऐसा नहीं है)।

   
   

3. प्रत्येक पिक्सेल के लिए, हम एक निश्चित पड़ोस (1 पिक्सेल से अधिक) में निम्नलिखित विशेषताओं पर विचार करते हैं:

   $$

   $$A = \ sum_ {x, y} {w (x, y) I_xI_x}$$
   
   

   $$

   $$B = \ sum_ {x, y} {w (x, y) I_xI_y}$$
   
   

   $$

   $$C = \ sum_ {x, y} {w (x, y) I_yI_y}$$
   
   टेम्प्लेट डिटेक्शन की तरह, बड़ी खिड़कियों के लिए इस प्रक्रिया को कुशलता से प्रमेय का उपयोग करके किया जा सकता है।
   

4. प्रत्येक पिक्सेल के लिए, मान की गणना करें $$$^ \ _ स्टार$ हेयुरिस्टिक आर

   $$

   $$R = Det (H) - k (Tr (H)) ^ 2 = (AB - C ^ 2) - k (A + B) ^ 2$$
   
   मूल्य $$$k$ क्रमिक रूप से चयनित श्रेणी [0.04, 0.06] में $$$आर$ कुछ पिक्सेल की एक निश्चित सीमा होती है, फिर पड़ोस $$$w$ इस पिक्सेल में एक कोण होता है, और हम इसे एक प्रमुख बिंदु के रूप में चिह्नित करते हैं।
   

5. पिछला सूत्र एक दूसरे के बगल में झूठ बोलने वाले महत्वपूर्ण बिंदुओं के समूह बना सकता है, जिस स्थिति में उन्हें हटाने के लायक है। यह प्रत्येक बिंदु के लिए जाँच करके किया जा सकता है कि क्या इसका कोई मूल्य है $$$आर$ निकटतम पड़ोसियों के बीच अधिकतम। यदि नहीं, तो मुख्य बिंदु को फ़िल्टर किया जाता है। इस प्रक्रिया को गैर-अधिकतम दमन कहा जाता है।

   
   

$$$\ _ $ स्टा$ सूत्र $$$आर$ तो एक कारण के लिए चुना। $$$ए, बी, सी$ - संरचनात्मक टेंसर के घटक - पड़ोस में ढाल के व्यवहार का वर्णन करने वाले मैट्रिक्स:

$$

$$H = \ start {pmatrix} A & C \\ C & B \ end {pmatrix}$$

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

Http://www.visiondummy.com/2014/04/geometric-interpretation-covariance-matrix/ से ली गई छवि

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

$$

$$R = \ lambda_1 \ lambda_2 - k (\ lambda_1 + \ lambda_2) ^ 2$$

जब दोनों स्वदेशी बड़े होंगे तो इस अनुमान का मूल्य बड़ा होगा।

आइजनवेल्यूज का योग मैट्रिक्स का ट्रेस है, जिसकी गणना विकर्ण पर तत्वों के योग के रूप में की जा सकती है (और यदि आप सूत्र ए और बी को देखते हैं, तो यह स्पष्ट हो जाता है कि यह क्षेत्र में ग्रेडिएंट्स की लंबाई के वर्गों का योग भी है):

$$

$$\ lambda_1 + \ lambda_2 = Tr (H) = A + B$$

Eigenvalues ​​का उत्पाद एक मैट्रिक्स का निर्धारक है, जो 2x2 के मामले में लिखना आसान है:

$$

$$\ lambda_1 \ lambda_2 = Det (H) = AB - C ^ 2$$

इस प्रकार, हम प्रभावी रूप से गणना कर सकते हैं $$$आर$ , संरचनात्मक टैंसर के घटकों के संदर्भ में इसे व्यक्त करना।

फास्ट

हैरिस की विधि अच्छी है, लेकिन इसके कई विकल्प हैं। हम सब कुछ उसी तरह से नहीं मानेंगे जैसा कि ऊपर की विधि है, हम दिलचस्प चाल दिखाने और कार्रवाई में उनकी तुलना करने के लिए केवल कुछ लोकप्रिय लोगों का उल्लेख करेंगे।

FAST एल्गोरिथ्म द्वारा सत्यापित पिक्सेल

हैरिस विधि का एक विकल्प फास्ट है । जैसा कि नाम से पता चलता है, FAST उपरोक्त विधि की तुलना में बहुत तेज है। यह एल्गोरिदम उन बिंदुओं को खोजने की कोशिश करता है जो वस्तुओं के किनारों और कोनों पर झूठ बोलते हैं, अर्थात्। विपरीत अंतर के स्थानों में। उनका स्थान निम्नानुसार है: फास्ट उम्मीदवार पिक्सेल के चारों ओर त्रिज्या आर के एक चक्र का निर्माण करता है और यह देखने के लिए जांचता है कि क्या यह कश्मीर इकाइयों द्वारा लंबाई के टी (या हल्का) के पिक्सेल के निरंतर खंड के पिक्सेल है। यदि यह स्थिति पूरी होती है, तो पिक्सेल को "मुख्य बिंदु" माना जाता है। निश्चित टी के लिए, हम कुछ प्रारंभिक जांचों को जोड़कर कुशलता से इस अनुमान को लागू कर सकते हैं जो गैर-कोनों की गारंटी वाले पिक्सल को काट देंगे। उदाहरण के लिए, जब $$$R = 3$ और $$$t = 12$ , यह जांचने के लिए पर्याप्त है कि क्या 4 चरम पिक्सेल के बीच लगातार 3 पिक्सेल हैं जो K पर केंद्र की तुलना में कड़ाई से गहरा / हल्का हैं (चित्र में - 1, 5, 9, 13)। यह स्थिति आपको उन उम्मीदवारों को प्रभावी रूप से काट देती है जो निश्चित रूप से महत्वपूर्ण बिंदु नहीं हैं।

झारना

दोनों पिछले एल्गोरिदम छवि आकार के प्रतिरोधी नहीं हैं। वे आपको तस्वीर में एक टेम्पलेट खोजने की अनुमति नहीं देते हैं यदि ऑब्जेक्ट के पैमाने को बदल दिया गया है। SIFT (स्केल-इनवायरेंट फीचर ट्रांसफ़ॉर्मेशन) इस समस्या का समाधान प्रस्तुत करता है। वह छवि लें जिसमें से हम मुख्य बिंदुओं को निकालते हैं, और कुछ छोटे कदम के साथ धीरे-धीरे इसके आकार को कम करना शुरू करते हैं, और प्रत्येक पैमाने के विकल्प के लिए हम प्रमुख बिंदुओं को पाएंगे। स्केलिंग एक कठिन प्रक्रिया है, लेकिन इसे 2/4/8 / ... तक कम करना पिक्सल को स्किप करने से कुशलतापूर्वक किया जा सकता है (SIFT में, इन कई पैमानों को "ओक्टेव्स" कहा जाता है)। इंटरमीडिएट तराजू को तस्वीर के लिए एक अलग कोर आकार के साथ एक गाऊसी ब्लाउर को लगाकर लगाया जा सकता है। जैसा कि हमने ऊपर वर्णित किया है, यह कम्प्यूटेशनल रूप से कुशलतापूर्वक किया जा सकता है। परिणाम ऐसा दिखेगा जैसे हमने पहली बार छवि को कम किया है और फिर उसे अपने मूल आकार में बड़ा कर दिया है - छोटे विवरण खो गए हैं, छवि "धुंधली" हो गई है।

इस प्रक्रिया के बाद, हम पड़ोसी तराजू के बीच अंतर की गणना करते हैं। इस अंतर में बड़े (निरपेक्ष मूल्य) मानों को बाहर कर दिया जाएगा यदि कुछ छोटे विस्तार के पैमाने के अगले स्तर पर दिखाई देना बंद हो जाता है, या, इसके विपरीत, पैमाने का अगला स्तर कुछ हिस्से पर कब्जा करना शुरू कर देता है जो पिछले एक पर दिखाई नहीं दे रहा था। इस तकनीक को DoG कहा जाता है, Gaussian का अंतर। हम मान सकते हैं कि इस अंतर में बहुत महत्व पहले से ही एक संकेत है कि छवि पर इस जगह में कुछ दिलचस्प है। लेकिन हम उस पैमाने में रुचि रखते हैं जिसके लिए यह मुख्य बिंदु सबसे अधिक अभिव्यंजक होगा। ऐसा करने के लिए, हम एक महत्वपूर्ण बिंदु पर न केवल एक बिंदु के रूप में विचार करेंगे, जो इसके परिवेश से अलग है, बल्कि विभिन्न छवि तराजूओं के बीच सबसे दृढ़ता से भिन्न है। दूसरे शब्दों में, हम न केवल अंतरिक्ष X और Y में, बल्कि अंतरिक्ष में एक महत्वपूर्ण बिंदु चुनेंगे $$$(X, Y, स्केल)$ । SIFT में, यह DoG (गॉसियंस का अंतर) में अंक ढूंढने के द्वारा किया जाता है, जो स्थानीय उच्च या चढ़ाव में हैं $$$3x3x3$ अंतरिक्ष का घन $$$(X, Y, स्केल)$ उसके आसपास:

प्रमुख बिंदुओं को खोजने और SIFT और SURF वर्णनकर्ताओं के निर्माण के लिए एल्गोरिदम का पेटेंट कराया गया है। यही है, उनके व्यावसायिक उपयोग के लिए लाइसेंस प्राप्त करना आवश्यक है। यही कारण है कि वे मुख्य opencv पैकेज से उपलब्ध नहीं हैं, लेकिन केवल एक अलग opencv_contrib पैकेज से। हालांकि, अब तक हमारा शोध पूरी तरह से प्रकृति में अकादमिक है, इसलिए, कुछ भी हमें तुलना में SIFT में भाग लेने से नहीं रोकता है।

वर्णनकर्ता

आइए टेम्पलेट और चित्र के लिए किसी प्रकार के डिटेक्टर (उदाहरण के लिए, हैरिस) को लागू करने का प्रयास करें।

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

संक्षिप्त

(.. 0 1), , XOR , . ? , N . , i- , , — i- 1. N. - (, — ), : , “”. , ( ). BRIEF .

. . , GII .

, , (.. , , ). OpenCV .

SIFT

SIFT , . SIFT 1616 , 44 . ( , ). 8 (, -, , ..). — 8 , , . . , 8- . 128 ( 4*4 = 16 , 8 ). .

तुलना

( — , ), - :

— . ?

, . , , . , , , , . ? BRIEF, , , . , BRIEF 1/16 . SIFT — - 1/4 .

SIFT.

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

हैरिस कॉर्नर डिटेक्टर	फास्ट	झारना

SIFT बटन पर बहुत कम महत्वपूर्ण बिंदु पाए गए। यह समझ में आता है - बटन एक काफी छोटी और सपाट वस्तु है, और ज़ूमिंग महत्वपूर्ण बिंदुओं को खोजने में मदद नहीं करता है।

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

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

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

कंटूर का पता लगाना

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

बढ़त का पता लगाना

कीपॉइंट डिटेक्शन के विपरीत, हम न केवल महत्वपूर्ण बिंदु कोणों, बल्कि किनारों में भी रुचि रखते हैं। हालाँकि, मूल विचार हम वहाँ से ले सकते हैं। एक गाऊसी फिल्टर के साथ छवि को चिकना करें, और हैरिस कोने के डिटेक्टर की तरह। फिर हम तीव्रता के डेरिवेटिव की गणना करते हैं $$$I_x$ और $$$I_y$ । चूंकि हमें किनारों से कोणों को अलग करने की आवश्यकता नहीं है, इसलिए हमें संरचनात्मक तन्यता पर विचार करने की आवश्यकता नहीं है - यह ढाल की ताकत की गणना करने के लिए पर्याप्त है: $$$I_l = I_x ^ 2 + I_y ^ 2$ (वैसे, यह जड़ है $$$ट्र (एच)$ , या संरचनात्मक तन्यता के विकर्ण के योग से)। उसके बाद, हम केवल उन्हीं पिक्सेल को छोड़ते हैं जो के संदर्भ में स्थानीय अधिकतम हैं $$$I_l$ (पहले से ही गैर-अधिकतम दमन का उपयोग करते हुए), लेकिन स्थानीय के रूप में हम 8 पड़ोसी पिक्सल का चयन नहीं करेंगे, लेकिन इन पिक्सल इन 8 से, जिनके लिए मुझे निर्देशित किया गया है, और विपरीत पक्ष से:

प्रश्न में पिक्सेल नीला है, तीर दिशा I है। हरे रंग के पिक्सेल वे हैं जिन्हें गैर-अधिकतम दमन के दौरान ध्यान में रखा जाएगा।

तुलना के लिए पिक्सल का ऐसा असामान्य विकल्प इस तथ्य के कारण है कि हम सीमा में अंतराल नहीं बनाना चाहते हैं। बाईं तस्वीर में, चेहरा ऊपर से नीचे की ओर जाता है, और चूंकि गैर-अधिकतम दमन नीले और ऊपर के पिक्सल के साथ तीव्रता की तुलना नहीं करेगा, हमें एक निरंतर चेहरा मिलता है।

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

हल्का नीला "कमजोर पसलियों" को इंगित करता है, गहरा नीला - मजबूत। निचले हिस्से में पसलियों को बाहर निकाला जाता है, क्योंकि वे किसी भी मजबूत पसली से नहीं जुड़े होते हैं।

हमने सिर्फ कैनी एज डिटेक्टर का वर्णन किया है। यह इस दिन को एक सरल और त्वरित प्रक्रिया के रूप में व्यापक रूप से उपयोग किया जाता है जो आपको वस्तुओं की आकृति खोजने की अनुमति देता है।

बॉर्डर ट्रैकिंग

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

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

पथ फ़िल्टरिंग

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

• बटन काफी बड़ा है (100 पिक्सेल से अधिक क्षेत्र)
• पक्ष समन्वय अक्षों के समानांतर हैं
• बाउंडिंग आयत के क्षेत्र के आंकड़े के क्षेत्र का अनुपात एकता के काफी करीब होना चाहिए। हमने दहलीज को 0.8 पर सेट किया है, क्योंकि बटन एक अक्ष के साथ समन्वय अक्षों के समानांतर पक्षों के साथ है, और लापता 20% गोल कोनों है।

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

हम परिणामी दृष्टिकोण को लागू करते हैं:

कैनी फिल्टर एप्लिकेशन (चित्र 2) को आवश्यक आकार मिला, लेकिन बटन के जटिल आकार और ढाल के कारण, कई आकृति एक ही बार में पाई गईं, और अधिकतम-अधिकतम दमन के कारण उनमें से कुछ को बंद नहीं किया गया। धुंधला (3 चित्र) को लागू करने से समस्या ठीक हो गई।

परीक्षण दृष्टिकोण

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

| | | |

परिणामी डिज़ाइन में परीक्षण छवियों पर बटन पाए गए। सभी बैनरों पर एक रन से पता चलता है कि कभी-कभार (~ 20 में से 1 मामला), एक बटन के बजाय, यह आईओएस ऐपस्टोर और Google ऐप या अन्य आयताकार वस्तुओं (फोन के मामलों) के आयताकार टाइलों का चयन करता है। इसलिए, एक गलत निर्धारण के उस दुर्लभ मामले में स्थिति को मैन्युअल रूप से इंगित करने की क्षमता को जोड़ते हुए, हमने स्थानीयकरण उपकरण में इस विकल्प को लागू किया।

निष्कर्ष

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

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

नोटपैड के साथ कोड जो वर्णित विधियों को लागू करते हैं और लेख के चित्र खींचते हैं ( भंडार में पाए जा सकते हैं)।