परिचय

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

बुनियादी एल्गोरिथम

छवि समानता उपाय

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

विभिन्न आकारों के चित्र

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

मुख्य चरण

तो, समान छवियों की तुलना करने के लिए एल्गोरिथ्म का सबसे सरल संस्करण निम्नलिखित चरणों को शामिल करेगा:

1. सभी छवियों को एक ही आकार में लाना (निश्चितता के लिए, 32x32 लें)।
2. रंग जानकारी (एक ग्रे छवि में परिवर्तित करना) को छोड़ना।
3. कम ग्रे छवियों के प्रत्येक जोड़े के लिए आरएमएस अंतर खोजना।
4. एक निश्चित सीमा के साथ प्राप्त आरएमएस अंतर की तुलना।

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

बुनियादी एल्गोरिथ्म का नुकसान

इस एल्गोरिथ्म के नुकसान में इसकी खराब संवेदनशीलता शामिल है जब कमजोर विपरीत छवियों की तुलना की जाती है, साथ ही बड़े पैमाने पर सुविधाओं के बिना चित्र (समोच्च चित्र, पाठ चित्र)। कमजोर संवेदनशीलता को इस तथ्य से समझाया जाता है कि जब मूल छवि 32x32 के आकार तक कम हो जाती है, तो एक नियम के रूप में, ऐसी सभी छवियां एक दूसरे से अप्रभेद्य बन जाती हैं। इसके अलावा, एल्गोरिथ्म के निष्पादन समय की कुल निर्भरता छवियों की कुल संख्या के आधार पर इस दृष्टिकोण का एक दोष माना जा सकता है, क्योंकि छवियों के प्रत्येक जोड़ी के लिए एक तुलना की जानी चाहिए। इसलिए, एक दूसरे के साथ सामान्यीकृत छवियों की एक जोड़ी की तुलना करने के लिए, एल्गोरिथ्म को लगभग 10 ^ 3 अंकगणितीय संचालन करने की आवश्यकता होती है, फिर एक हजार छवियों के लिए यह लगभग 10 ^ 9 संचालन है, और एक लाख छवियों के लिए - 10 ^ 15 ऑपरेशन। बेशक, प्रत्येक उपयोगकर्ता के पास एक लाख चित्रों के साथ छवियों का संग्रह नहीं है, लेकिन यहां तक ​​कि 100 हजार छवियों (जो शौकिया फोटोग्राफरों के लिए इतना असामान्य नहीं है) की तुलना करने के लिए, हमें लगभग 10 ^ 13 ऑपरेशन पूरा करने की आवश्यकता है, जो आधुनिक हार्डवेयर पर भी काफी समय ले सकता है।

फास्ट एल्गोरिथ्म

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

पहलू अनुपात

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

प्रारंभिक तुलना

पहला सबसे स्पष्ट कदम: यदि हमने एक बार छवि को कम कर दिया है, तो फिर से क्यों नहीं? हम एक 32x32 छवि से 4x4 छवि बनाते हैं, जहां कम छवि का प्रत्येक बिंदु मूल छवि के संबंधित 8x4 आकार के हिस्से की औसत चमक का प्रतिनिधित्व करता है। यह गणितीय रूप से कठोरता से साबित किया जा सकता है कि इस कम की गई छवि के लिए rms अंतर मूल छवि के rms अंतर से अधिक नहीं होगा। इसलिए, हम कम 4x4 छवियों की प्रारंभिक तुलना करके, एक प्रकार का फ़िल्टर बना सकते हैं जो अधिकांश उम्मीदवारों को पूर्ण तुलना के लिए फ़िल्टर करेगा (बशर्ते कि नमूने में अधिकांश छवियां अपेक्षाकृत अद्वितीय हों)। इस तरह की एक सरल तकनीक प्राप्त कर सकती है, क्योंकि गणना करना आसान है, लगभग 50-गुना त्वरण। हालांकि, यह स्पष्ट है कि जिस सीमा पर हम छवियों की तुलना करते हैं, इस फिल्टर की दक्षता उतनी ही कम होती है।

एक आयामी छवि अनुक्रमण

जैसा कि आप जानते हैं, एक ऑर्डर किए गए डेटा ऐरे में खोज O (ln (N)) के आदेश के समय में की जा सकती है, एक अनियंत्रित के विपरीत, जिसमें O (N) की आवश्यकता होती है। इस प्रकार, यदि हम किसी तरह से छवियों को व्यवस्थित करने का प्रबंधन करते हैं, तो सैद्धांतिक रूप से ओ (एन ^ 2) के लिए खोज की द्विघात जटिलता को कम करना संभव है - ओ (एन * एलएन (एन))। और इसलिए हम एक सूचकांक बनाने की कोशिश करेंगे जिसके साथ हम छवियों को सॉर्ट करेंगे। ऐसा करने के लिए, हमारे 4x4 थंबनेल को लें और इसे दो गुना घटाकर 2x4 करें। इस चित्र से पहला सूचकांक बनाना आसान है:

i [0] = (p [0] [0] + p [0] [1] + p [1] [0] + p [1] [1]) / 4

जो हमारी छवि की औसत चमक का प्रतिनिधित्व करता है। वास्तव में, यह छवि 1x1 के आकार तक कम हो जाती है। स्रोत छवियों का मूल-माध्य-वर्ग अंतर उनकी तीव्रता में अंतर से कम नहीं होगा। इस प्रकार, यदि छवियों की तुलना करने की सीमा t है, तो तुलना के लिए सभी संभावित उम्मीदवारों को i [0] - t से i [0] + t तक की सीमा में औसत चमक होनी चाहिए। वास्तव में, यदि हम अनुक्रमणिका i [0] द्वारा सभी छवियों को क्रमबद्ध करते हैं, तो हम काफी कम संख्या में छवियों की तुलना कर सकते हैं - 2 * t / 255। यह गणना करना मुश्किल नहीं है कि 5% की एक सामान्य सीमा के लिए, हमारे पास 10 गुना का सैद्धांतिक लाभ है। व्यवहार में, लाभ कम होगा, क्योंकि औसत चमक द्वारा छवियों का सांख्यिकीय वितरण सीमा [0 ... 255] में समान नहीं है, लेकिन 127 के पास एक घंटी के आकार का अधिकतम होता है और सीमा के किनारों पर गिर जाता है। इसकी वास्तविक चौड़ाई, और, परिणामस्वरूप, सैद्धांतिक रूप से एल्गोरिथ्म का व्यावहारिक लाभ लगभग 70-80% है।

बहुआयामी छवि अनुक्रमण

औसत चमक I [0] के अलावा, एक अन्य 3 अतिरिक्त अनुक्रमित एक 2x2 छवि से बनाया जा सकता है:

i [1] = 128 + (p [0] [0] - p [0] [1] + p [1] [0] - p [1] [1]) / 4,)

i [2] = 128 + (p [0] [0] + p [0] [1] - p [1] [0] - p [1] [1]) / 4,)

i [3] = 128 + (p [0] [0] - p [0] [1] - p [1] [0] + p [1] [1]) / 4,)

जिसका एक सरल भौतिक अर्थ है: अनुक्रमणिका i [1] दर्शाता है कि छवि का बायां भाग दाईं ओर से कितना चमकीला है, i [2] - ऊपरी भाग नीचे से कितना तेज है, और मैं [3] - छवि के विकर्ण कितने भिन्न हैं। इन सभी सूचकांकों के लिए, आप छवियों को, साथ ही पहले के लिए भी सॉर्ट कर सकते हैं, और तुलना के लिए सभी संभावित उम्मीदवार i [j] - t से i [j] + t तक की सीमा में होंगे। यानी इन सूचकांकों द्वारा गठित चार-आयामी अंतरिक्ष में, खोज क्षेत्र एक 4-आयामी क्यूब का प्रतिनिधित्व करेगा 2 * टी साइड और वांछित छवि के सूचकांक द्वारा गठित निर्देशांक के साथ एक केंद्र। सैद्धांतिक त्वरण सूचकांक स्थान के कुल आयतन के लिए इस 4-आयामी घन की मात्रा के अनुपात के बराबर है और (2 * t / 255) ^ 4 = 1/10000 के बराबर है। व्यावहारिक त्वरण बहुत अधिक मामूली है, क्योंकि सूचकांकों i [1] और i [2] द्वारा छवियों के वितरण की प्रभावी चौड़ाई लगभग 40-50% है, और i [3] अधिकतम संभव का केवल 20-30% है। संकीर्ण वास्तविक सीमा के कारण, व्यवहार में, बाद के सूचकांक का उपयोग अक्सर बिल्कुल उचित नहीं होता है, इसलिए, हम खुद को पहले 3 सूचकांकों तक सीमित कर सकते हैं। फिर भी, व्यावहारिक रूप से प्राप्त त्वरण परिमाण के दो आदेशों (5% की दहलीज अंतर के लिए) तक पहुंचता है।

बेहतर एल्गोरिथ्म के मुख्य चरण

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

1. सभी छवियों को एक आकार (32x32) तक कम करना और रंग जानकारी को त्यागना।
2. एक प्रारंभिक 4x4 तुलना के लिए एक थंबनेल ढूँढना।
3. प्रारंभिक तुलना के लिए एक छवि के आधार पर एक छवि के एन-आयामी सूचकांक का निर्माण।
4. N- डायमेंशनल इंडेक्स स्पेस में किसी खोज क्षेत्र की सीमाओं को परिभाषित करना।
5. इस क्षेत्र के उम्मीदवारों के पहलू अनुपात की जाँच करना।
6. पिछले पैराग्राफ में उत्तीर्ण उम्मीदवारों के साथ छवियों की प्रारंभिक तुलना का संचालन करना।
7. पिछले पैराग्राफ के अतीत के उम्मीदवारों के साथ छवियों की पूरी तुलना का संचालन करना।

एक तेज एल्गोरिथ्म के नुकसान

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

निष्कर्ष

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

मुझे उम्मीद है कि पाठकों को मेरी प्रस्तुति में दिलचस्पी है। शायद किसी को भी यह उपयोगी लगा। प्रतिक्रिया की प्रतीक्षा है।

पुनश्च सॉफ्टवेयर कार्यान्वयन

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