😦 🥁 🌺 अवधारणात्मक हैश का उपयोग करके डुप्लिकेट छवियों का पता लगाना 📑 👩🏼‍⚕️ 👋🏽

यह आलेख चर्चा करेगा कि किसी चित्र के टुकड़े या फसल द्वारा डुप्लिकेट खोजने का छोटा कार्य कैसे हल किया गया था।

प्रस्तावना

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

जांच

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

वास्तव में, मैं SIFT / SURF के वर्णनकर्ताओं के समान चित्र में कुछ संकेतों को उजागर करना चाहूंगा, लेकिन संयोग की जल्दी से जांच करने की क्षमता के साथ।

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

संक्षेप में, एक अवधारणात्मक हैश कुछ संकेतों का एक दृढ़ संकल्प है जो एक तस्वीर का वर्णन करता है।

इस तरह के हैश का मुख्य लाभ यह है कि वे हैमिंग दूरी का उपयोग करके अन्य हैश के साथ तुलना करना आसान है।

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

SELECT * FROM image_hash WHERE BIT_COUNT( 0x2f1f76767e5e7f33 ^ hash ) <= 10

यह पता लगाना बाकी है कि इस तरह के हैश को बेहतर कैसे किया जा सकता है।

एक बाद के लेख में , इस प्रकार के हैश को अलग करने के तीन तरीकों का वर्णन किया गया था।

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

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

सामान्य तौर पर, यदि कोई छोटा कॉपीराइट चिह्न इसके लिए लागू किया गया है, तब भी फ़ोटोश किसी चित्र की पहचान को सत्यापित करने में सक्षम होता है। यह रंग, इसके विपरीत, चमक, आकार और यहां तक कि मामूली ज्यामितीय परिवर्तनों के लिए असंवेदनशील है।

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

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

हल करने का प्रयास

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

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

एक चित्र प्रति हैश एक समान समस्या को हल करने में तेजी से असमर्थ है।

लेकिन, इस तरह के हैश को लागू करने की सादगी के कारण, मैं थोड़ा सोचना चाहता था कि आप इस सीमा के आसपास कैसे पहुंच सकते हैं और उनकी मदद से छवि की फसल पा सकते हैं।

चूंकि एक हैश अच्छा नहीं है, आपको हैश की एक सूची मिलनी चाहिए। जहां प्रत्येक हैश केवल छवि के अपने हिस्से का वर्णन करता है।

लेकिन हम यह कैसे जानते हैं कि तस्वीर को कहाँ और कैसे काटना है?
यह वह जगह है जहाँ SURF के साथ स्थानीय विशेषताएँ काम में आ रही हैं।

दूसरे शब्दों में, यह किसी भी तरह से पाया बिंदुओं से चित्रों को काटने के लिए आवश्यक था।

चित्र 1. अनुरोधित छवि से अंक मिले।

चित्र 2. सहेजी गई छवि से अंक मिले

चूंकि हमें चित्र को काटने की आवश्यकता है ताकि (कम से कम थोड़ा) समान क्षेत्रों का संयोग हो, कुंजी बिंदुओं (सुविधाओं) के k- साधन क्लस्टरिंग की कोशिश की गई थी।

ऐसा लगता था कि यदि चित्र सामग्री में बहुत अधिक परिवर्तन नहीं हुआ और पाया गया कि स्थानीय विशेषताएं लगभग अपरिवर्तित रहीं, तो संभवतः इन स्थानीय बिंदुओं के क्लस्टरिंग के बाद केन्द्रक भी लगभग संयोग होना चाहिए।

यह इस दृष्टिकोण का मुख्य विचार है।

चित्रा 3. बिंदु एक क्लस्टर का केंद्र दिखाता है।

अंजीर। 4. अंक तीन समूहों के केंद्रों का वर्णन करते हैं। यदि आप बारीकी से देखते हैं, तो ऊपरी सेंट्रोइड लगभग छवि 3 से केंद्र के साथ मेल खाता है।

ऐसे सेंट्रोइड्स को खोजने के लिए जो लगभग अभिसरण करेंगे, क्लस्टरिंग प्रदर्शन करना आवश्यक था, उदाहरण के लिए, 20 बार, क्लस्टर की संख्या को बदलना।

और प्रत्येक क्लस्टर के चरम बिंदुओं पर कटौती करना संभव था।

20 समूहों की सीमा के साथ, 21 * 20/2 = 210 सेंट्रोइड प्राप्त होते हैं। और कुल चित्र प्रति हैश 210 = हैश की पूरी तस्वीर = 211 हैश।
लेकिन हम 32 पिक्सेल से कम की कतरनों को छोड़ देते हैं और अंत में हमें उदाहरण के लिए, 191 हैश मिलता है।

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

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

मैंने इसे प्रहार विधि का उपयोग करके उठाया, ताकि कट चित्र का समन्वय आठ से अधिक हो।

चित्र 5. क्लस्टरिंग द्वारा मिलान चित्रों को काटें

प्रोटोटाइप

अगला, व्यवहार में इस तरह के एक मॉडल की परिचालनता को सत्यापित करना आवश्यक था।
चित्रों के साथ सब कुछ जल्दी से कब्रिस्तान में स्थानांतरित कर दिया गया और पूरे डेटाबेस को अनुक्रमित किया गया।
इसने डेटाबेस में 1,235 चित्र और 194,710 हैश का पता लगाया।

और फिर यह पता चला कि BIT_COUNT (hash1 ^ hash2) एक महंगा ऑपरेशन है और अतिरिक्त ध्यान देने की आवश्यकता है।
और एक बार में सभी 200 हैश के साथ एक बड़े अनुरोध को निष्पादित करने की तुलना में 200 अनुरोधों को निष्पादित करने में अधिक समय लगता है।

मेरे कमजोर सर्वर पर, इस तरह के एक बड़े अनुरोध में कम से कम 2 सेकंड लगते हैं।

कुल मिलाकर, एक तस्वीर की खोज के लिए हैमिंग दूरी की गणना के लिए 200 * 194 710 = 38 942 000 संचालन की आवश्यकता होती है।

इसलिए, मैंने यह जांचने का फैसला किया कि अगर मैंने MySQL में दूरी की गणना के अपने कार्यान्वयन को लिखा तो क्या अंतर होगा।
यह अंतर नगण्य है और इसके अलावा, कस्टम कार्यों के पक्ष में नहीं है।

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

C ++ में हेमिंग की दूरी की गणना करने का एक उदाहरण

 typedef unsigned long long longlong; inline longlong hamming_distance( longlong hash1, longlong hash2 ) { longlong x = hash1 ^ hash2; const longlong m1 = 0x5555555555555555ULL; const longlong m2 = 0x3333333333333333ULL; const longlong h01 = 0x0101010101010101ULL; const longlong m4 = 0x0f0f0f0f0f0f0f0fULL; x -= (x >> 1) & m1; x = (x & m2) + ((x >> 2) & m2); x = (x + (x >> 4)) & m4; return (x * h01)>>56; }

और ऐसा विचार SQL क्वेरी के माध्यम से दोगुना तेजी से पूरा होता है।

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

उदाहरण के लिए, यदि दो सौ मैचों में से एक हैश, चित्र को डुप्लिकेट मानते हैं? शायद नहीं।
ऐसे मामले भी थे जब 20% से अधिक हैश ने संयोग किया, लेकिन तस्वीर निश्चित रूप से एक डुप्लिकेट नहीं है।
और 10% मैच हैं, लेकिन यह एक डुप्लिकेट है।
तो कुल संख्या को मिली हैश की संख्या सत्यापन की गारंटी नहीं है।

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

उपसंहार

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

संदर्भ

habrahabr.ru/post/120562 - हैश का वर्णन, अनुवाद
en.wikipedia.org/wiki/ Hamming_Distance - हैमिंग दूरी
en.wikipedia.org/wiki/SURF - SURF प्रमुख बिंदु
en.wikipedia.org/wiki/K-means - क्लस्टरिंग
phash.org - पीएचएएस परियोजना
www.hackerfactor.com/blog/index.php?/archives/529-Kind-of-Like-That.html - हैश प्रकारों की तुलना करना
01101001.net/differencehash.php - अंतर हैश
github.com/valbok/img.chk/blob/master/bin/example.py - छवि से हैश निष्कर्षण का मेरा कार्यान्वयन
github.com/valbok/leie/blob/master/classes/image/leieImage.php - मेरे हैश का एक और प्रकार, लेकिन PHP में