टुकड़े करके छवियों के लिए खोजें

अपने भाषण में, अलेक्जेंडर क्रेनोव ने बताया कि कैसे Yandex.Pictures ने नकली छवियों को क्लस्टर किया। दूसरे शब्दों में, डुप्लिकेट चित्रों को अलग और फ़िल्टर किया गया था। जहां मुख्य विचार DoG फ़िल्टर का उपयोग करके छवि के आकृति को उजागर करना था, फिर मुख्य बिंदुओं को ढूंढें और उनके विवरण प्राप्त करें।
क्लस्टरिंग डुप्लिकेट मेल खाने वाले डिस्क्रिप्टर मैचों के लिए नीचे आता है। यह छवि खोज में डुप्लिकेट डुप्लिकेट लेख से मुख्य बिंदुओं का "डिजिटल प्रारूप" है।

लेकिन मैं थोड़ा और सीखना चाहूंगा कि ये वर्णनकर्ता क्या हैं और उन्हें कैसे खोजना है।

वर्णनकर्ता

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

प्रमुख बिंदुओं के प्रभावी आवंटन, उनके विवरण, साथ ही साथ मैचों की जाँच के तरीके की खोज अभी भी एजेंडे में है।

लेकिन आपको कहीं से शुरुआत करनी होगी, इसलिए मदद के लिए OpenCV लाइब्रेरी की ओर रुख करें।

आपकी आंख को पकड़ने वाली पहली चीज SURF विवरणकर्ता है।
जो असाधारण सटीकता का वादा करते हैं। जिसकी पुष्टि परीक्षणों के बाद हुई है।

लेकिन कुछ बारीकियां हैं।
SURF वर्णनकर्ता प्रति बिंदु 128 (या 64) संख्या के वैक्टर हैं। निकटतम बिंदु (या यहां तक ​​कि दो) की खोज करके मिलान किया जाता है। और बिंदु के करीब, बेहतर है।

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

SIFT और SURF से परिचित होने के बाद, मैं एक छोटे सर्वर या डिवाइस पर इसका उपयोग करने की क्षमता के साथ लागू करने के लिए कुछ सरल चाहता था।

अवधारणात्मक हैश

और अवधारणात्मक या अवधारणात्मक हैश पाए गए।
कौन सा कार्य यह है कि छवि में एक छोटे से परिवर्तन के साथ, हैश भी थोड़ा बदल जाता है।

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

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

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

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

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

इस पद्धति के ढाई महत्वपूर्ण नुकसान हैं:
1. हैश के बड़े सेट पर संयोग के लिए जाँच की कम गति। 1 मिलियन हैश की खोज में 20 सेकंड लगे
2. मुख्य बिंदुओं को प्राप्त करने की कम गति
3. कम सटीकता, झूठी सकारात्मक, लक्ष्य आधार के लिए उच्च आवश्यकताओं, सभी चित्रों के लिए उपयुक्त नहीं, पूर्व-मॉडरेशन की आवश्यकता होती है, आदि।

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

इसलिए, इन समस्याओं के समाधान खोजने का प्रयास करने का निर्णय लिया गया।

धीमी नमूना दर

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

SURF और प्रमुख बिंदु

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

सामान्य तौर पर, OpenCV दो प्रकार के विवरण प्रदान करता है:

- फ्लोटिंग पॉइंट डिस्क्रिप्टर
- और बाइनरी डिस्क्रिप्टर

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

ORB: SIFT या SURF का एक कुशल विकल्प

OpenCV में पहले से ही SURF का एक उत्कृष्ट विकल्प है, जो न केवल खुला है और लाइसेंस प्रतिबंध के बिना, यह और भी आसान और तेज है [1]।

ORB ओरिएंटेड फास्ट एंड रोटेटेड BRIEF - एक बेहतर संस्करण और FAST क्यू पॉइंट डिटेक्टर और BRIEF बाइनरी डिस्क्रिप्टर का संयोजन है।

ओआरबी में हमारे लिए एक महत्वपूर्ण बारीकियां हैं - विवरणकर्ताओं का आकार प्रति बिंदु 32 बाइट्स है।
एक मिलान जाँच विवरणक के प्रत्येक बाइट के लिए हैमिंग दूरी का योग है (पहले की तुलना पहले के साथ की जाती है, दूसरे के साथ दूसरे की तुलना की जाती है)।

हमारे कार्य में, यह माना जाता है कि एक बिंदु एक मूल्य देता है, और यहां हमें 32 मिलता है, जिसे लक्ष्य डेटाबेस में सूचकांक द्वारा पहले वाले (पहले के साथ दूसरे, दूसरे के साथ, आदि) के साथ संक्षेपित किया जाना चाहिए।

चूंकि हमारा हैश 64-बिट नंबर है, इसलिए यह 8 बाइट्स में निचोड़ने के लिए डिस्क्रिप्टर के 32 बाइट्स लेता है और साथ ही साथ सटीकता में बहुत अधिक नहीं खोता है।

कुछ परीक्षणों के बाद, इन 32 बाइट्स को 16x16 बिट मैट्रिक्स के रूप में पेश करने का प्रयास करने का निर्णय लिया गया। और फिर इस मैट्रिक्स को PHash अवधारणात्मक हैश के माध्यम से पास करें। परिणाम सिर्फ 64 बिट संख्या होना चाहिए था।

अब हम अवधारणा के पूर्ण विवरण पर आते हैं।

कैसे अनुक्रमण काम करता है

1. प्रमुख बिंदु और ओआरबी विवरण प्राप्त करें, छवि में आवश्यक बिंदुओं की संख्या का चयन करें।
2. 32 बाइट्स के परिणामस्वरूप डिस्क्रिप्टर 16x16 बिट मैट्रिक्स के रूप में प्रस्तुत किए जाते हैं।
3. PHash का उपयोग करके मैट्रिक्स को 64 बिट संख्या में परिवर्तित करें।
4. MySQL में 64bit फिंगरप्रिंट को सेव करें।
5. आवश्यक हैमिंग दूरी का चयन करें और HEngine डेमन चलाएं, जो खोज का प्रदर्शन करेगा।

कैसे काम करता है खोज

हम अनुक्रमण से समान चरण 1 से 3 का प्रदर्शन करते हैं, लेकिन केवल अनुरोधित छवि पर।
4. हम HEngine डेमॉन के लिए एक अनुरोध करते हैं, जो दी गई सीमा में सभी हैश को लौटाता है।
5. यदि आवश्यक हो, अप्रासंगिक परिणामों को फ़िल्टर करें।


अंजीर 1. हैमिंग दूरी सीमा 7. ग्रे डॉट्स प्रमुख बिंदु पाए जाते हैं। हरे - मिलान अंक। लाल - मानक ORB संपूर्ण खोज से मेल खाता है।

परिणाम क्या है?

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

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


चित्रा 2. शुक्रवार तक मीठा

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

संदर्भ

[१] एथन रुबले, विंसेंट रबॉड, कर्ट कोनोलिज, गैरी आर। ब्रैडस्की: ORB: SIFT या SURF का एक कुशल विकल्प। ICCV 2011: 2564-2571।
[२] en.wikipedia.org/wiki/SURF
[३] en.wikipedia.org/wiki/ Hamming_Distance
[४] phash.org
[५] habrahabr.ru/post/143667 Yandex.Pictures में डुप्लिकेट की क्लस्टरिंग
[६] habrahabr.ru/post/211264 HEngine - एक बड़े डेटा सेट पर दिए गए हैमिंग की दूरी के भीतर हैश की खोज के लिए एल्गोरिथ्म
[[] Github.com/valbok/img.chk मेरा टुकड़ा खोज प्रोटोटाइप है