पिछले कुछ महीनों में, कई लोगों ने मुझसे पूछा है कि टिनएई कैसे काम करता है और मूल रूप से समान छवियों के लिए खोज कैसे काम करती है।

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

यह एक धारणा है!

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

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

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

यह अच्छा लग रहा है

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

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



1. आकार कम करें। उच्च आवृत्तियों से छुटकारा पाने का सबसे तेज़ तरीका छवि को कम करना है। इस मामले में, हम इसे 8x8 तक कम कर देते हैं, इसलिए कुल पिक्सेल की संख्या 64 है। आप अनुपात के बारे में चिंता नहीं कर सकते, बस इसे एक वर्ग आठ से आठ में ड्राइव करें। इस प्रकार, हैश आकार और पहलू अनुपात की परवाह किए बिना छवि के सभी संस्करणों के अनुरूप होगा।

=

2. रंग निकालें। एक छोटी छवि ग्रेस्केल में अनुवादित की जाती है, इसलिए हैश को तीन गुना घटाया जाता है: 64 पिक्सेल (64 मान, लाल, 64 हरा और 64 नीला) से लेकर 64 रंग मान।

3. माध्य ज्ञात करें। सभी 64 रंगों के लिए औसत की गणना करें।

4. बिट्स की श्रृंखला। यह सबसे मजेदार है: प्रत्येक रंग के लिए आपको 1 या 0 मिलता है, यह इस बात पर निर्भर करता है कि यह औसत से अधिक या कम है।

5. हैश का निर्माण करें। 64 व्यक्तिगत बिट्स को एकल 64-बिट मान में कनवर्ट करें। यदि यह स्थिर रखा जाता है तो आदेश कोई फर्क नहीं पड़ता (मैं ऊपर से नीचे तक बाएं से दाएं लिखता हूं)।

= = 8f373714acfcf4d0

परिणामस्वरूप हैश नहीं बदलेगा अगर छवि को छोटा, संकुचित, या फैला हुआ है। चमक या कंट्रास्ट बदलना, या यहां तक ​​कि रंगों में हेरफेर करना भी परिणाम को बहुत प्रभावित नहीं करेगा। और सबसे महत्वपूर्ण बात: इस तरह के एक एल्गोरिथ्म बहुत तेज है!

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

पीएचएएस की कोशिश कर रहा है

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

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

1. आकार कम करें। औसत हैश के साथ की तरह, एक छोटे से चित्र के आकार में फेश काम करता है। हालांकि, यहां छवि 8x8 से बड़ी है, यहां 32x32 एक अच्छा आकार है। यह वास्तव में डीसीटी को सरल बनाने के लिए किया जाता है, न कि उच्च आवृत्तियों को खत्म करने के लिए।



2. रंग निकालें। इसी तरह, आगे की गणना को सरल बनाने के लिए रंगीन चैनलों को हटा दिया जाता है।

3. असतत कोसाइन ट्रांसफ़ॉर्म चलाएं। डीसीटी आवृत्तियों और वैक्टर के एक सेट में एक तस्वीर को विभाजित करता है । जबकि JPEG एल्गोरिथ्म 8x8 ब्लॉकों पर DCT चलाता है, इस एल्गोरिथ्म में DCT 32x32 पर चलता है।

4. डीसीटी कम करें। यह एक जादुई कदम है। जबकि मूल ब्लॉक 32x32 था, केवल ऊपरी बाएँ ब्लॉक 8x8 को सहेजें। इसमें चित्र से सबसे कम आवृत्तियाँ होती हैं।

5. औसत मूल्य की गणना करें। जैसे हैश में औसत डीसीटी मान की गणना यहां की जाती है, इसकी गणना 8x8 ब्लॉक पर की जाती है और बहुत पहले गुणांक को हैश विवरण से खाली जानकारी निकालने के लिए गणना से बाहर रखा जाना चाहिए, उदाहरण के लिए, समान रंग।

6. डीसीटी को और कम करना। एक जादुई कदम भी। 64 DCT मान 0 या 1 में से प्रत्येक को असाइन करें, यह इस बात पर निर्भर करता है कि यह औसत से बड़ा है या छोटा। यह विकल्प पहले से ही गामा सुधार या समस्याओं के बिना हिस्टोग्राम में बदलाव का सामना कर सकता है।

7. हैश का निर्माण करें। 64 बिट्स 64-बिट मान में बदल जाते हैं, यहां भी, ऑर्डर मायने नहीं रखता। यह देखने के लिए कि फ़िंगरप्रिंट कैसा दिखता है, आप प्रत्येक पिक्सेल को 5:5 और -255 असाइन कर सकते हैं, यह निर्भर करता है कि यह 1 या 0 है या नहीं, और डीसीटी 32x32 (उच्च आवृत्तियों के लिए शून्य के साथ) को 32x32 छवि में बदल दें।

= 8a0303769b3ec8cd

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

औसत हैश में के रूप में, एक ही हैमिंग दूरी एल्गोरिथ्म का उपयोग करके एक दूसरे के साथ फेश मूल्यों की तुलना की जा सकती है (प्रत्येक बिट के मूल्य की तुलना की जाती है और अंतर की संख्या की गणना की जाती है)।

कक्षा में सर्वश्रेष्ठ?

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

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

जाति

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

अन्य किस्में रंग के समग्र वितरण का विश्लेषण कर सकती हैं (उदाहरण के लिए, उसके बाल नीले या हरे रंग की तुलना में अधिक लाल हैं, और पृष्ठभूमि अंधेरे की तुलना में अधिक हल्की है) या लाइनों की सापेक्ष स्थिति।

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