फास्ट एंड सरल छवि हैशिंग एल्गोरिदम

Question

मुझे एक (अधिमानतः सरल और तेज़) छवि हैशिंग एल्गोरिदम चाहिए। हैश वैल्यू को लुकअप टेबल में इस्तेमाल किया जाता है, न कि क्रिप्टोग्राफी के लिए।

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

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

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

मुझे आश्चर्य है कि पसंदीदा हैशिंग एल्गोरिदम क्या है।

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

लेकिन इस तरह के एक बेवकूफ एल्गोरिदम का उपयोग "कृत्रिम" ग्राफिक्स के साथ नहीं किया जा सकता है। समान पिक्सल, पैटर्न दोहराते हुए, ज्यामितीय ऑफ़सेट आविष्कार ऐसी छवियों के लिए बहुत आम हैं। सभी पिक्सल XOR-ing किसी भी छवि के लिए 0 समान पिक्सेल की संख्या के साथ 0 देगा।

सीआरटी -32 जैसे कुछ का उपयोग कुछ हद तक आशाजनक दिखता है, लेकिन मैं कुछ तेज़ी से समझना चाहता हूं। मैं पुनरावृत्ति सूत्र के बारे में सोचा, प्रत्येक नए पिक्सेल वर्तमान हैश मान mutates, इस तरह:,

hashValue = (hashValue * /*something*/ | newPixelValue) % /* huge prime */ 

सापेक्ष अभाज्य संख्या कर शायद एक अच्छा फैलाव देना चाहिए ताकि मैं इस विकल्प की ओर झुकाव रहा हूँ। लेकिन मैं जानना चाहता हूं कि बेहतर विक्रेता हैं या नहीं।

अग्रिम धन्यवाद।

Answer 1

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

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

एक सरल एल्गोरिथ्म

Random generator = new generator(2847) // Initialized with fixed seed 
int num_iterations = 100 

int hash(Image image) { 
    generator.reset() //To ensure consistency on each evaluation 
    int value = 0 
    for num_iteration steps { 
     int nextValue = image.getPixel(generator.nextInt()%image.getSize()).getValue() 
     value = value + nextValue*generator.nextInt() 
    } 
    return value 
} 

Answer 2

की छद्म कोड phash एल्गोरिथ्म http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html जो बारीकी से मिलान छवियों को खोजने के लिए किया जाता है पर इस ट्यूटोरियल पर एक नज़र डालें।