image Elasticsearch में phash दूरी द्वारा इसी तरह की छवि खोज




hamming-distance (5)

इसी तरह की छवि खोज समस्या

  • लाखों छवियों phash 'ed और Elasticsearch में संग्रहित।
  • प्रारूप "11001101 ... 11" (लंबाई 64) है, लेकिन बदला जा सकता है (बेहतर नहीं)।

विषय छवि के हैश "100111..10" को देखते हुए हम 8 की दूरी पर हैमिंगसेच इंडेक्स में सभी समान छवि हैंश ढूंढना चाहते हैं।

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

हमारे वर्तमान मानचित्रण

प्रत्येक दस्तावेज़ में images घोंसला होता है जिसमें छवि हैश होते हैं:

{
  "images": {
    "type": "nested", 
    "properties": {
      "pHashFingerprint": {"index": "not_analysed", "type": "string"}
    }
  }
}

हमारा खराब समाधान

तथ्य: Elasticsearch अस्पष्ट क्वेरी केवल अधिकतम 2 की लेवेनशेटिन दूरी का समर्थन करती है।

हमने 16 बिट्स के 4 समूहों में 64 बिट स्ट्रिंग को विभाजित करने के लिए कस्टम टोकनेज़र का उपयोग किया और चार फ़ज़ी क्वेरी के साथ 4 समूह खोज करें।

विश्लेषक:

{
   "analysis": {
      "analyzer": {
         "split4_fingerprint_analyzer": {
            "type": "custom",
            "tokenizer": "split4_fingerprint_tokenizer"
         }
      },
      "tokenizer": {
         "split4_fingerprint_tokenizer": {
            "type": "pattern",
            "group": 0,
            "pattern": "([01]{16})"
         }
      }
   }
}

फिर नया क्षेत्र मैपिंग:

"index_analyzer": "split4_fingerprint_analyzer",

फिर पूछताछ करें:

{
   "query": {
      "filtered": {
         "query": {
            "nested": {
               "path": "images",
               "query": {
                  "bool": {
                     "minimum_should_match": 2,
                     "should": [
                        {
                           "fuzzy": {
                              "phashFingerprint.split4": {
                                 "value": "0010100100111001",
                                 "fuzziness": 2
                              }
                           }
                        },
                        {
                           "fuzzy": {
                              "phashFingerprint.split4": {
                                 "value": "1010100100111001",
                                 "fuzziness": 2
                              }
                           }
                        },
                        {
                           "fuzzy": {
                              "phashFingerprint.split4": {
                                 "value": "0110100100111001",
                                 "fuzziness": 2
                              }
                           }
                        },
                        {
                           "fuzzy": {
                              "phashFingerprint.split4": {
                                 "value": "1110100100111001",
                                 "fuzziness": 2
                              }
                           }
                        }
                     ]
                  }
               }
            }
         },
         "filter": {}
      }
   }
}

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

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

जैसा कि अपेक्षित है, अगर minimum_should_match 3 और 4 तक बढ़ रहा है, तो केवल छवियों का सबसेट जो मिलना चाहिए, लौटाया जाता है, लेकिन परिणामस्वरूप सेट छोटा और तेज़ होता है। minimum_should_match 9 5% आवश्यक छवियों को minimum_should_match == 3 के साथ वापस कर दिया गया है, लेकिन हमें minimum_should_match == 2 के साथ 100% (या 99.9%) की minimum_should_match

हमने एन-ग्राम के साथ समान दृष्टिकोण की कोशिश की, लेकिन अभी भी बहुत सारे परिणामों के समान फैशन में ज्यादा सफलता नहीं मिली है।

अन्य डेटा संरचनाओं और प्रश्नों के किसी भी समाधान?

संपादित करें :

हमने देखा, कि हमारी मूल्यांकन प्रक्रिया में एक बग था, और minimum_should_match == 2 परिणाम 100% देता है। हालांकि, बाद में प्रसंस्करण समय औसत 5 सेकंड लेता है। हम देखेंगे कि स्क्रिप्ट अनुकूलन योग्य है या नहीं।


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

मेरा समाधान अब तक है:

मूल स्कोरिंग फ़ंक्शन लिखें और इसे प्लगइन के रूप में पंजीकृत करें। फिर दस्तावेजों के _score मूल्य को समायोजित करने के लिए पूछताछ करते समय इसे कॉल करें जब वे वापस आते हैं।

एक ग्रोवी लिपि के रूप में, कस्टम स्कोरिंग फ़ंक्शन चलाने के लिए लिया गया समय अत्यंत अप्रत्याशित था, लेकिन इसे देशी स्कोरिंग फ़ंक्शन के रूप में लिखना (जैसा कि कुछ हद तक वृद्ध ब्लॉग पोस्ट में दिखाया गया है: http://www.spacevatican.org/2012/5/12/elasticsearch-native-scripts-for-dummies/ ) तीव्रता के आदेश तेजी से थे।

मेरा हैमिंगडिस्टेंसस्क्रिप्ट इस तरह कुछ देखा:

public class HammingDistanceScript extends AbstractFloatSearchScript {

    private String field;
    private String hash;
    private int length;

    public HammingDistanceScript(Map<String, Object> params) {
        super();
        field = (String) params.get("param_field");
        hash = (String) params.get("param_hash");
        if(hash != null){
            length = hash.length() * 8;
        }
    }

    private int hammingDistance(CharSequence lhs, CharSequence rhs){          
        return length - new BigInteger(lhs, 16).xor(new BigInteger(rhs, 16)).bitCount();
    }

    @Override
    public float runAsFloat() {
        String fieldValue = ((ScriptDocValues.Strings) doc().get(field)).getValue();
        //Serious arse covering:
        if(hash == null || fieldValue == null || fieldValue.length() != hash.length()){
            return 0.0f;
        }

        return hammingDistance(fieldValue, hash);
    }
}

इस बिंदु पर उल्लेख करना उचित है कि मेरे हैंश हेक्स-एन्कोडेड बाइनरी स्ट्रिंग्स हैं। तो, आपके जैसा ही है, लेकिन हेक्स-एन्कोडेड स्टोरेज आकार को कम करने के लिए।

इसके अलावा, मैं एक param_field पैरामीटर की उम्मीद कर रहा हूं, जो यह पहचानता है कि किस फ़ील्ड मान के खिलाफ मैं हथौड़ा दूरी करना चाहता हूं। आपको ऐसा करने की आवश्यकता नहीं है, लेकिन मैं एकाधिक फ़ील्ड के खिलाफ एक ही स्क्रिप्ट का उपयोग कर रहा हूं, इसलिए मैं करता हूं :)

मैं इसे इस तरह के प्रश्नों में उपयोग करता हूं:

curl -XPOST 'http://localhost:9200/scf/_search?pretty' -d '{
  "query": {
    "function_score": {     
      "min_score": MY IDEAL MIN SCORE HERE,
      "query":{
       "match_all":{}
      },
      "functions": [
        {
          "script_score": {
            "script": "hamming_distance",
            "lang" : "native",
            "params": {
              "param_hash": "HASH TO COMPARE WITH",
              "param_field":"phash"
            }
          }
        }
      ]
    }
  }
}'

मुझे उम्मीद है कि यह किसी भी तरह से मदद करता है!

यदि आप इस मार्ग पर जाते हैं तो अन्य जानकारी जो आपके लिए उपयोगी हो सकती है:

1. es-plugin.properties फ़ाइल याद रखें
इसे आपकी जार फ़ाइल की जड़ में संकलित किया जाना है (यदि आप इसे / src / main / संसाधनों में चिपकाते हैं तो अपने जार का निर्माण करें, यह सही जगह पर जाएगा)।

मेरा ऐसा दिखता है:

plugin=com.example.elasticsearch.plugins.HammingDistancePlugin
name=hamming_distance
version=0.1.0
jvm=true
classname=com.example.elasticsearch.plugins.HammingDistancePlugin
java.version=1.7
elasticsearch.version=1.7.3

2. elasticsearch.yml में अपने कस्टम नेटस्क्रिप्ट फैक्टरी इत्यादि का संदर्भ लें
बस वृद्ध ब्लॉग पोस्ट की तरह।

मेरा ऐसा दिखता है:

script.native:
    hamming_distance.type: com.example.elasticsearch.plugins.HammingDistanceScriptFactory

यदि आप ऐसा नहीं करते हैं, तो यह अभी भी प्लगइन्स सूची (बाद में देखें) पर दिखाई देता है लेकिन जब आप इसका उपयोग करने का प्रयास करते हैं तो आपको त्रुटियां मिलेंगी, कह रही है कि elasticsearch इसे नहीं ढूंढ सकता है।

3. इसे स्थापित करने के लिए elasticsearch प्लगइन स्क्रिप्ट का उपयोग परेशान मत करो
यह सिर्फ गधे का दर्द है और ऐसा लगता है कि यह आपके सामान को अनपैक कर रहा है - थोड़ा व्यर्थ। इसके बजाय, बस इसे %ELASTICSEARCH_HOME%/plugins/hamming_distance और elasticsearch को पुनरारंभ करें।

अगर सब ठीक हो गया है, तो आप इसे elasticsearch स्टार्टअप पर लोड किया जाएगा:

[2016-02-09 12:02:43,765][INFO ][plugins                  ] [Junta] loaded [mapper-attachments, marvel, knapsack-1.7.2.0-954d066, hamming_distance, euclidean_distance, cloud-aws], sites [marvel, bigdesk]

और जब आप प्लगइन की सूची कहते हैं तो यह वहां होगा:

curl http://localhost:9200/_cat/plugins?v

कुछ ऐसा उत्पन्न करता है:

name        component                version type url
Junta       hamming_distance         0.1.0   j

मैं अगले हफ्ते में लाखों दस्तावेजों के ऊपर परीक्षण करने में सक्षम होने की उम्मीद कर रहा हूं। यदि मैं मदद करता हूं, तो मैं इसे वापस पॉप करने और परिणामों के साथ अपडेट करने की कोशिश करूंगा।


@NikoNyrh's जवाब के लिए 64 बिट समाधान यहां दिया गया है। हैमिंग दूरी की गणना केवल XOR ऑपरेटर का उपयोग करके CUDA के अंतर्निहित __popcll फ़ंक्शन के साथ की जा सकती है।

struct HammingDistanceFilter
{
    const uint64_t _target, _maxDistance;

    HammingDistanceFilter(const uint64_t target, const uint64_t maxDistance) :
            _target(target), _maxDistance(maxDistance) {
    }

    __device__ bool operator()(const uint64_t hash) {
        return __popcll(_target ^ hash) <= _maxDistance;
    }
};

यहां एक सुरुचिपूर्ण, लेकिन सटीक (ब्रूट फोर्स) समाधान है जिसके लिए आपकी सुविधा हैश को अलग-अलग बूलियन फ़ील्ड में डिस्कोस्ट्रक्चर करने की आवश्यकता है ताकि आप इस तरह की क्वेरी चला सकें:

"query": {
    "bool": {
      "minimum_should_match": -8,
      "should": [
          { "term": { "phash.0": true } },
          { "term": { "phash.1": false } },
          ...
          { "term": { "phash.63": true } }
        ]
    }
}

मुझे यकीन नहीं है कि यह बनाम fuzzy_like_this कैसे करेगा, लेकिन एफएलटी कार्यान्वयन को समाप्त करने का कारण यह है कि इसे संपादन दूरी की गणना करने के लिए सूचकांक में प्रत्येक शब्द का दौरा करना है।

(जबकि यहां / ऊपर, आप लुसीन के अंतर्निहित उलटा-सूचकांक डेटा-स्ट्रक्चर और ऑप्टिमाइज्ड सेट ऑपरेशंस का लाभ उठा रहे हैं, जो आपके लाभ के लिए काम करना चाहिए, बशर्ते आपके पास शायद काफी स्पेशल फीचर्स हों)


मैंने लैपटॉप GeForce 650M ग्राफिक्स कार्ड पर भी कुछ अच्छे परिणामों के साथ सीयूडीए दृष्टिकोण को लागू किया। Thrust पुस्तकालय के साथ कार्यान्वयन आसान था। मुझे उम्मीद है कि कोड में बग नहीं हैं (मैंने इसका परीक्षण नहीं किया है) लेकिन यह बेंचमार्क परिणामों को प्रभावित नहीं करना चाहिए। कम से कम मैंने उच्च-परिशुद्धता टाइमर को रोकने से पहले thrust::system::cuda::detail::synchronize() कहा जाता है।

typedef unsigned __int32 uint32_t;
typedef unsigned __int64 uint64_t;

// Maybe there is a simple 64-bit solution out there?
__host__ __device__ inline int hammingWeight(uint32_t v)
{
    v = v - ((v>>1) & 0x55555555);
    v = (v & 0x33333333) + ((v>>2) & 0x33333333);

    return ((v + (v>>4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

__host__ __device__ inline int hammingDistance(const uint64_t a, const uint64_t b)
{
    const uint64_t delta = a ^ b;
    return hammingWeight(delta & 0xffffffffULL) + hammingWeight(delta >> 32);
}

struct HammingDistanceFilter
{
    const uint64_t _target, _maxDistance;

    HammingDistanceFilter(const uint64_t target, const uint64_t maxDistance) :
            _target(target), _maxDistance(maxDistance) {
    }

    __host__ __device__ bool operator()(const uint64_t hash) {
        return hammingDistance(_target, hash) <= _maxDistance;
    }
};

रैखिक खोज उतनी आसान थी जितनी

thrust::copy_if(
    hashesGpu.cbegin(), hashesGpu.cend(), matchesGpu.begin(),
    HammingDistanceFilter(target_hash, maxDistance)
)

खोज 50% सटीक और मेरे लोचदार खोज उत्तर से तेज़ तरीका था, 50 मिलीसेकंड में सीयूडीए 35 मिलियन हैश के माध्यम से स्ट्रीम कर सकता था! मुझे यकीन है कि नए डेस्कटॉप कार्ड इससे भी तेज हैं। इसके अलावा हम खोज समय के बहुत कम भिन्नता और लगातार रैखिक विकास प्राप्त करते हैं क्योंकि हम अधिक से अधिक डेटा के माध्यम से जाते हैं। बढ़ते नमूने डेटा के कारण ElasticSearch बड़े प्रश्नों पर खराब स्मृति समस्याओं को मारा।

तो यहां मैं "इन एन हैश से, परिणामों को रिपोर्ट कर रहा हूं, जो एक हैश एच से 8 हैमिंग दूरी के भीतर हैं"। मैं इन 500 बार चलाता हूं और प्रतिशत की सूचना देता हूं।

कुछ कर्नेल लॉन्च ओवरहेड हैं लेकिन खोज स्थान के बाद 5 मिलियन से अधिक हैश की खोज गति 700 मिलियन हैश / सेकेंड पर काफी सुसंगत है। स्वाभाविक रूप से खोज की जाने वाली हैश की संख्या पर ऊपरी सीमा जीपीयू की रैम द्वारा निर्धारित की जाती है।


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

minimum_should_match bool query पर term फ़िल्टर का उपयोग अपेक्षाकृत कम minimum_should_match थ्रेसहोल्ड के साथ should । निचली दहलीज उच्च "अस्पष्टता" से मेल खाती है। दुर्भाग्यवश आपको इस दृष्टिकोण का परीक्षण करने के लिए अपनी सभी छवियों को पुन: अनुक्रमणिका करने की आवश्यकता है।

मुझे लगता है कि { "term": { "phash.0": true } } प्रश्न अच्छी तरह से प्रदर्शन नहीं करते थे क्योंकि औसतन प्रत्येक फ़िल्टर 50% दस्तावेजों से मेल खाता है। 16 बिट्स / नमूना के साथ प्रत्येक नमूना 2^-16 = 0.0015% दस्तावेज़ों से मेल खाता है।

मैं निम्नलिखित सेटिंग्स के साथ अपने परीक्षण चलाता हूं:

  • 1024 नमूने / हैश (डॉक्टर फ़ील्ड में संग्रहीत "0" - "ff" )
  • 16 बिट्स / नमूना ( short प्रकार, doc_values = true संग्रहीत)
  • 4 शर्ड्स और 1 मिलियन हैश / इंडेक्स, लगभग 17.6 जीबी स्टोरेज ( _source और नमूने को संग्रहित करके कम किया जा सकता है, केवल मूल बाइनरी हैश)
  • minimum_should_match = 150 (1024 में से)
  • 4 मिलियन डॉक्स (4 इंडेक्स) के साथ बेंचमार्क किया गया

आपको कम नमूने के साथ तेज़ गति और कम डिस्क उपयोग मिलता है लेकिन 8 और 9 की दूरी को धुंधला करने के बीच दस्तावेज़ अलग-अलग नहीं होते हैं (मेरे सिमुलेशन के अनुसार)। 1024 खंडों की अधिकतम संख्या प्रतीत होता है।

टेस्ट एक कोर i5 3570K, 24 जीबी रैम, ईएस के लिए 8 जीबी, संस्करण 1.7.1 पर चलाए गए थे। 500 प्रश्नों के परिणाम (नीचे नोट देखें, परिणाम बहुत आशावादी हैं) :

Mean time: 221.330 ms
Mean docs: 197

Percentiles:
   1st = 140.51ms
   5th = 150.17ms
  25th = 172.29ms
  50th = 207.92ms
  75th = 233.25ms
  95th = 296.27ms
  99th = 533.88ms

मैं परीक्षण करूंगा कि यह कैसे 15 मिलियन दस्तावेजों के पैमाने पर है लेकिन प्रत्येक इंडेक्स में 1 मिलियन दस्तावेज़ उत्पन्न करने और स्टोर करने में 3 घंटे लगते हैं।

आपको परीक्षण या गणना करना चाहिए कि मिस्ड मैचों और गलत मैचों के बीच वांछित व्यापार-बंद प्राप्त करने के लिए आपको minimum_should_match कितना कम सेट करना चाहिए, यह आपके minimum_should_match के वितरण पर निर्भर करता है।

उदाहरण क्वेरी (दिखाए गए 1024 फ़ील्ड में से 3):

{
  "bool": {
    "should": [
      {
        "filtered": {
          "filter": {
            "term": {
              "0": -12094,
              "_cache": false
            }
          }
        }
      },
      {
        "filtered": {
          "filter": {
            "term": {
              "_cache": false,
              "1": -20275
            }
          }
        }
      },
      {
        "filtered": {
          "filter": {
            "term": {
              "ff": 15724,
              "_cache": false
            }
          }
        }
      }
    ],
    "minimum_should_match": 150
  }
}

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

नए परिणाम पहले ग्राफ में दिखाए गए हैं, मेरे पास ईएस के लिए 4 जीबी मेमोरी थी और ओएस के लिए शेष 20 जीबी थी। खोज 1 - 3 इंडेक्स में अच्छा प्रदर्शन था (औसत समय 0.1 - 0.2 सेकंड) लेकिन इसके परिणामस्वरूप अधिक से अधिक डिस्क आईओ और 9 से 11 सेकंड लगने लगे प्रश्न! इसे हैश के कम नमूने लेकर घिराया जा सकता है लेकिन फिर याद रखें और सटीक दरें उतनी अच्छी नहीं होंगी, वैकल्पिक रूप से आपके पास 64 जीबी रैम वाली मशीन हो सकती है और देखें कि आप कितनी दूर पाएंगे।

संपादित करें 2: मैंने _source: false साथ डेटा फिर से उत्पन्न किया है _source: false और हैश नमूने (केवल कच्चे हैश) को संग्रहित नहीं करता है, यह कम भंडारण स्थान 60% से लगभग 6.7 जीबी / सूचकांक (1 मिलियन दस्तावेज़ों) तक कम हो जाता है। इससे छोटे डेटासेट पर क्वेरी स्पीड प्रभावित नहीं हुआ, लेकिन जब रैम पर्याप्त नहीं था और डिस्क का इस्तेमाल किया जाना था तो प्रश्न लगभग 40% तेज थे।

संपादित करें 3: मैंने 30 मिलियन दस्तावेज़ों के सेट पर 2 की संपादन दूरी के साथ fuzzy खोज का परीक्षण किया, और इसकी तुलना में हैश के 256 यादृच्छिक नमूने अनुमानित परिणाम प्राप्त करने के लिए। इन स्थितियों के तहत विधियां मोटे तौर पर एक ही गति होती हैं लेकिन fuzzy सटीक परिणाम देती है और उस अतिरिक्त डिस्क स्थान की आवश्यकता नहीं होती है। मुझे लगता है कि यह दृष्टिकोण केवल "बहुत अस्पष्ट" प्रश्नों के लिए उपयोगी है जैसे 3 से अधिक की हैमिंग दूरी।







phash