एकल एल्गोरिथ्म पार्सिंग, समान छवियों के लिए खोजें

मुझे हाल ही में डुप्लिकेट छवियों की खोज के अनुकूलन की समस्या को हल करना पड़ा।

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

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

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

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

यह कैसे काम करता है:

1. छवि को 8-बिट काले और सफेद प्रारूप में परिवर्तित किया जाता है (0-255 में एक डॉट एक बाइट है)
2. छवि को इस तरह से क्रॉप किया जाता है जैसे चारों तरफ से प्रत्येक से 5% संचित अंतर (अधिक नीचे) को छोड़ना। उदाहरण के लिए, छवि के चारों ओर एक काला फ्रेम।
3. एक कार्य ग्रिड का चयन किया जाता है (डिफ़ॉल्ट रूप से 9x9), जिसके नोड्स छवि हस्ताक्षर के संदर्भ बिंदुओं के रूप में काम करेंगे।
4. प्रत्येक संदर्भ बिंदु के लिए, उसके चारों ओर एक निश्चित क्षेत्र के आधार पर, इसकी चमक की गणना की जाती है।
5. प्रत्येक संदर्भ बिंदु के लिए, यह गणना की जाती है कि वह अपने आठ पड़ोसियों की तुलना में कितना उज्ज्वल / गहरा है। पांच उन्नयन का उपयोग किया जाता है, -2 (बहुत गहरा) से 2 (बहुत उज्जवल)।
6. यह सब "आनन्द" एक आयामी सरणी (वेक्टर) में प्रकट होता है और इसे छवि हस्ताक्षर द्वारा कहा जाता है।

दो छवियों की समानता निम्नानुसार जाँच की जाती है:



कम डी, बेहतर है। वास्तव में, डी <0.3 पहचान की गारंटी है।

अब और विस्तार से।

पहला कदम

मुझे लगता है कि ग्रेस्केल में परिवर्तित करने के बारे में बात करना थोड़ा समझ में आता है।

दूसरा कदम

मान लीजिए कि हमारे पास इस तरह की एक तस्वीर है:


यह देखा जा सकता है कि दाईं और बाईं ओर 3 पिक्सेल का एक काला फ्रेम है और ऊपर और नीचे 2 पिक्सेल हैं, जिनकी तुलना में हमें बिल्कुल भी ज़रूरत नहीं है

कटऑफ बॉर्डर निम्नलिखित एल्गोरिदम द्वारा निर्धारित किया जाता है:

1. प्रत्येक स्तंभ के लिए, हम पड़ोसी तत्वों के पूर्ण अंतर के योग की गणना करते हैं।
   
2. हम उन पिक्सल की संख्या को छोड़ देते हैं और सही करते हैं जिनके कुल संचयी अंतर में योगदान 5% से कम है।

हम कॉलम के लिए भी ऐसा ही करते हैं।

एक महत्वपूर्ण स्पष्टीकरण: यदि परिणामस्वरूप छवि के आयाम चरण 4 के लिए अपर्याप्त हैं, तो हम फसल नहीं करते हैं!

चरण तीन

खैर, यहां सब कुछ काफी सरल है, हम चित्र को समान भागों में विभाजित करते हैं और नोडल बिंदुओं का चयन करते हैं।

चौथा चरण

लंगर बिंदु की चमक की गणना उसके चारों ओर के चौकोर क्षेत्र में सभी बिंदुओं की औसत चमक के रूप में की जाती है। मूल कार्य में, इस वर्ग के पक्षों की गणना के लिए निम्न सूत्र का उपयोग किया जाता है:

पांचवां चरण

प्रत्येक संदर्भ बिंदु के लिए, इसके आठ पड़ोसियों की चमक के साथ इसकी चमक में अंतर की गणना की जाती है। उन बिंदुओं के लिए जिनके लिए कोई पड़ोसी (ऊपरी और निचली पंक्तियां, बाएं और दाएं कॉलम) नहीं हैं, अंतर 0 के रूप में लिया जाता है।

इसके अलावा, इन अंतरों को पांच ग्रेडेशन तक घटाया जाता है:


यह इस मैट्रिक्स की तरह कुछ निकलता है:

छठा चरण

मुझे लगता है कि किसी स्पष्टीकरण की आवश्यकता नहीं है।

और अब अनुकूलन के बारे में

मूल काम में, यह ठीक से इंगित किया गया है कि परिणामस्वरूप हस्ताक्षर से मैट्रिक्स के किनारों के साथ शून्य मानों को पूरी तरह से मिटा देना संभव है, क्योंकि वे सभी छवियों के लिए समान होंगे।


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


जाहिर है, जब वर्गों के योग की गणना करते हैं, तो प्रत्येक x के लिए निश्चित रूप से एक समान modulo x होगा ' और मान की गणना के लिए सूत्र कुछ इस तरह लिखा जा सकता है (बिना रीइंडेक्स किए बिना)


यह अंश के लिए और भाजक के दोनों पदों के लिए सत्य है।

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

हम भंडारण के लिए ऐसी योजना का उपयोग करते हैं, प्रति श्रेणी 4 बिट्स:

हां, 21 के मुकाबले, केवल 16 ग्रेडेशन एक अनसाइनड लॉन्ग में फिट होंगे, लेकिन फिर दो हस्ताक्षरों के अंतर की सरणी की गणना एक एक्सर और 15 शिफ्ट्स के साथ दाईं ओर की जाएगी, जो कि प्रत्येक बदलाव के लिए सेट बिट्स की संख्या की गणना के साथ दाईं ओर होगी। यानी


संकेत हमारे लिए कोई मायने नहीं रखता, क्योंकि सभी मूल्य चुकेंगे।

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

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

दरअसल, बस इतना ही। आपका ध्यान के लिए धन्यवाद। :)