लिपपोल इंडेक्सिंग लाखों चित्रों?

Question

श्री फ्रैंक डेनिस से PHP (http://libpuzzle.pureftpd.org/project/libpuzzle) के लिए libpuzzle libray के बारे में। मैं अपने mysql डेटाबेस में डेटा को अनुक्रमणित और संग्रहीत करने का तरीका समझने की कोशिश कर रहा हूं। वेक्टर की पीढ़ी पूरी तरह से कोई समस्या नहीं है।

उदाहरण:

# Compute signatures for two images 
$cvec1 = puzzle_fill_cvec_from_file('img1.jpg'); 
$cvec2 = puzzle_fill_cvec_from_file('img2.jpg'); 

# Compute the distance between both signatures 
$d = puzzle_vector_normalized_distance($cvec1, $cvec2); 

# Are pictures similar? 
if ($d < PUZZLE_CVEC_SIMILARITY_LOWER_THRESHOLD) { 
    echo "Pictures are looking similar\n"; 
} else { 
    echo "Pictures are different, distance=$d\n"; 
} 

यही सब मेरे लिए स्पष्ट है - लेकिन अब मैं कैसे काम करते हैं जब मैं चित्रों> 1.000.000 का एक बड़ा राशि है? मैं वेक्टर की गणना करता हूं और डेटाबेस में फ़ाइल नाम के साथ स्टोर करता हूं? अब इसी तरह की तस्वीरों को कैसे ढूंढें? अगर मैं mysql में प्रत्येक वेक्टर को स्टोर करता हूं तो मुझे प्रत्येक रिकॉर्ड खोलना होगा और puzzle_vector_normalized_distance फ़ंक्शन के साथ दूरी की गणना करना होगा। प्रक्रियाओं के लिए समय की बहुत लेता है यही कारण है कि (प्रत्येक डेटाबेस प्रविष्टि खोलने - यह समारोह फेंक कर दिया, ...)

मैं lib पहेली libaray से रीडमी पढ़ सकते हैं और निम्नलिखित पाया:

इसके साथ काम करेंगे एक डेटाबेस जिसमें लाखों चित्र हैं?

अंतर्निहित संपीड़न/डिकंप्रेशन फ़ंक्शन का उपयोग करके एक सामान्य छवि हस्ताक्षर के लिए केवल 182 बाइट की आवश्यकता होती है।

इसी तरह के हस्ताक्षर समान "शब्द" साझा करते हैं, यानी। उसी स्थिति में मानों के समान अनुक्रम। यौगिक इंडेक्स (शब्द + स्थिति) का उपयोग करके, संभावित समान वैक्टरों का सेट नाटकीय रूप से कम हो गया है, और ज्यादातर मामलों में, वास्तव में कोई वेक्टर दूरी गणना करने की आवश्यकता नहीं है।

शब्दों और पदों के माध्यम से अनुक्रमण करना डेटा को कई तालिकाओं और सर्वरों में विभाजित करना आसान बनाता है।

तो हाँ, पहेली लाइब्रेरी निश्चित रूप से परियोजनाओं के साथ असंगत नहीं है जो लाखों चित्रों को अनुक्रमित करने की आवश्यकता है।

इसके अलावा मैं अनुक्रमण के बारे में इस विवरण पाया:

------------------------ अनुक्रमण ----- -------------------

अगर वे लाखों रिकॉर्ड हैं तो जल्दी से चित्रों को कैसे ढूंढें?

मूल पेपर का एक सरल, अभी तक कुशल उत्तर है।

निश्चित लंबाई वाले शब्दों में वेक्टर को काटें। उदाहरण के लिए, निम्नलिखित वेक्टर पर विचार करते हैं:

[सहमति का प्रतीक]

एक शब्द लंबाई (के) 10 में, आपको निम्न शब्द प्राप्त कर सकते हैं के साथ

:

[abcdefghij] स्थिति 0 पर पाया [bcdefghijk] स्थिति 1 में पाया जब तक (शब्द + स्थिति) का एक यौगिक सूचकांक के साथ अपने वेक्टर स्थिति N-1

फिर, सूचकांक [cdefghijkl] स्थिति 2 आदि में पाया।

लाखों छवियों के साथ भी, के = 10 और एन = 100 के लिए पर्याप्त होना चाहिए, उसी सूचकांक को साझा करने में बहुत कम प्रविष्टियां हैं।

+-----------------------------+ 
| signatures | 
+-----------------------------+ 
| sig_id | signature | pic_id | 
+--------+-----------+--------+ 

+--------------------------+ 
| words | 
+--------------------------+ 
| pos_and_word | fk_sig_id | 
+--------------+-----------+ 

मैं कई में विभाजित कम से कम "शब्द" तालिका की सलाह देते हैं टेबल और/या सर्वर:

यहाँ एक बहुत ही बुनियादी नमूना डेटाबेस स्कीमा है।

डिफ़ॉल्ट रूप से (lambas = 9) हस्ताक्षर 544 बाइट लंबा हैं। स्टोरेज स्पेस को सहेजने के लिए, उन्हें puzzle_compress_cvec() फ़ंक्शन के माध्यम से उनके मूल आकार के 1/तिहाई तक संपीड़ित किया जा सकता है। उपयोग करने से पहले, वे पहेली_uncompress_cvec() के साथ असम्पीडित होना चाहिए।

मुझे लगता है कि संपीड़न गलत तरीका है तो मुझे इसकी तुलना करने से पहले हर वेक्टर को असम्पीडित करना होगा।

मेरा प्रश्न अब है - लाखों चित्रों को संभालने का तरीका और तेज़ और कुशल तरीके से उनकी तुलना कैसे करें। मैं समझ नहीं पा रहा हूं कि "वेक्टर काटने" को मेरी समस्या से कैसे मदद करनी चाहिए।

बहुत धन्यवाद - शायद मैं यहां किसी को ढूंढ सकता हूं जो libpuzzle libaray के साथ काम कर रहा है।

चीयर्स।

Answer 1

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

वैसे भी, अब की तलाश में, मेरी समझ की पेशकश करने की कोशिश करेंगे - हम दोनों के बीच हो सकता है हम इस पर काम कर सकते हैं :)

प्रश्नों एक का उपयोग 2 चरण प्रक्रिया -

1. पहले आप शब्द तालिका का उपयोग करते हैं।
   1. 'संदर्भ' छवि लें और इसके हस्ताक्षर कार्य करें।
   2. बाहर काम उसके घटक शब्द,
   3. सभी संभव मैचों को खोजने के लिए शब्द से परामर्श तालिका। यह कुशल क्वेरी के लिए डेटाबेस इंजन 'इंडेक्स' का उपयोग कर सकता है।
   4. सभी sig_ids की एक सूची संकलित करें। (3. में कुछ डुप्लिकेट मिल जाएगा)
2. फिर हस्ताक्षर तालिका सभी संभव हस्ताक्षर से परामर्श
   1. पुनर्प्राप्त और संपीड़ित (क्योंकि आप एक prefiltered सूची है संख्या अपेक्षाकृत छोटा होना चाहिए)
   2. एक वास्तविक दूरी को काम करने के लिए puzzle_vector_normalized_distance का उपयोग करें।
   3. तरह और के रूप में आवश्यक

परिणामों की श्रेणी (आप केवल हस्ताक्षर पर संपीड़न का उपयोग यानी तालिका। शब्द असम्पीडित बनी हुई है, इसलिए उस पर तेजी से क्वेरी चला सकते हैं)

शब्द तालिका उलटा सूचकांक का एक रूप है। वास्तव में मुझे https://stackoverflow.com/questions/tagged/sphinx का उपयोग डेटाबेस डेटाबेस तालिका के बजाय करने के लिए दिमाग में है, क्योंकि यह विशेष रूप से एक बहुत तेज़ उलटा इंडेक्स के रूप में डिज़ाइन किया गया है।

... सिद्धांत किसी भी तरह ...

Answer 2

तो, के उदाहरण वे दे पर एक नज़र डालें और विस्तार करने के लिए कोशिश करते हैं।

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

CREATE TABLE images (
    image_id INTEGER NOT NULL PRIMARY KEY, 
    name TEXT, 
    description TEXT, 
    file_path TEXT NOT NULL, 
    url_path TEXT NOT NULL, 
    signature TEXT NOT NULL 
); 

आप शुरू में हस्ताक्षर की गणना करते समय आपके पास हस्ताक्षर से शब्दों की एक संख्या की गणना करने के लिए जा रहे हैं:

// this will be run once for each image: 
$cvec = puzzle_fill_cvec_from_file('img1.jpg'); 
$words = array(); 
$wordlen = 10; // this is $k from the example 
$wordcnt = 100; // this is $n from the example 
for ($i=0; $i<min($wordcnt, strlen($cvec)-$wordlen+1); $i++) { 
    $words[] = substr($cvec, $i, $wordlen); 
} 

अब तुम एक में उन शब्दों को डाल सकते हैं की इस प्रकार उस तालिका को निर्धारित करते हैं मेज, इस प्रकार परिभाषित:

CREATE TABLE img_sig_words (
    image_id INTEGER NOT NULL, 
    sig_word TEXT NOT NULL, 
    FOREIGN KEY (image_id) REFERENCES images (image_id), 
    INDEX (image_id, sig_word) 
); 

अब आप उस तालिका में सम्मिलित है, जहां शब्द मिला था की स्थिति सूचकांक prepending ताकि आपको पता है, जब शब्द से मेल खाता है कि यह वही प्लेसमेंट में मिलान हस्ताक्षर में ई:

// the signature, along with all other data, has already been inserted into the images 
// table, and $image_id has been populated with the resulting primary key 
foreach ($words as $index => $word) { 
    $sig_word = $index.'__'.$word; 
    $dbobj->query("INSERT INTO img_sig_words (image_id, sig_word) VALUES ($image_id, 
     '$sig_word')"); // figure a suitably defined db abstraction layer... 
} 

आपका डाटा इस प्रकार प्रारंभ, आप अपेक्षाकृत आसानी से शब्दों से मेल खाती के साथ छवियों को हड़पने कर सकते हैं:

// $image_id is set to the base image that you are trying to find matches to 
$dbobj->query("SELECT i.*, COUNT(isw.sig_word) as strength FROM images i JOIN img_sig_words 
    isw ON i.image_id = isw.image_id JOIN img_sig_words isw_search ON isw.sig_word = 
    isw_search.sig_word AND isw.image_id != isw_search.image_id WHERE 
    isw_search.image_id = $image_id GROUP BY i.image_id, i.name, i.description, 
    i.file_path, i.url_path, i.signature ORDER BY strength DESC"); 

आप एक HAVING खंड है कि एक न्यूनतम strength आवश्यकता जोड़कर क्वेरी सुधार सकता है, इस प्रकार आपके मिलान सेट को और कम कर देता है।

मुझे कोई गारंटी नहीं है कि यह सबसे कुशल सेटअप है, लेकिन यह जो भी आप ढूंढ रहे हैं उसे पूरा करने के लिए लगभग कार्यात्मक होना चाहिए।

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

Answer 3

मैंने गिटहब पर एक libpuzzle डेमो परियोजना बनाई है: https://github.com/alsotang/libpuzzle_demo।

प्रोजेक्ट जिस तरह से जेसन ने ऊपर प्रस्तावित किया है उसका उपयोग करें।

डेटाबेस स्कीमा पर पता चलता है: https://github.com/alsotang/libpuzzle_demo/blob/master/schema.sql

---

और मैं libpuzzle के हस्ताक्षर बारे में अधिक जानकारी दे देंगे।

अब हम दो छवियों है, और मुझे उनके हस्ताक्षर की गणना करते हैं।

अजीब लाइनों छवि 1 (बाएं से एक) के लिए है, और यहां तक ​​कि लाइनों छवि के लिए है 2.

आपको लगता है कि ज्यादातर मामलों में पा सकते हैं, एक ही स्थिति में संख्या है वही।

....

---

मेरी अंग्रेजी इतना गरीब है, इसलिए मैं व्यक्त नहीं कर सकते मेरे मन जारी रखने के लिए ... मुझे लगता है कि किसी को जो छवियों के सूचकांक लाखों चाहते libpuzzle डेमो की मेरी GitHub रेपो का निरीक्षण किया जाना चाहिए ..

Answer 4

मैं php में libpuzzle पर भी काम कर रहा हूं और मुझे छवि हस्ताक्षर से शब्दों को उत्पन्न करने के बारे में कुछ संदेह हैं। Jasons जवाब ऊपर सही लगता है, लेकिन मैं इस भाग के साथ एक समस्या है: 544 अक्षर लंबा और शब्दों के ऊपर निर्माण हम हमेशा केवल पहले 110 का उपयोग कर रहे साथ

// this will be run once for each image: 
 
$cvec = puzzle_fill_cvec_from_file('img1.jpg'); 
 
$words = array(); 
 
$wordlen = 10; // this is $k from the example 
 
$wordcnt = 100; // this is $n from the example 
 
for ($i=0; $i<min($wordcnt, strlen($cvec)-$wordlen+1); $i++) { 
 
    $words[] = substr($cvec, $i, $wordlen); 
 
}

हस्ताक्षर वेक्टर है इसके पत्र मतलब है कि अगर मैं इसे सही ढंग से समझता हूं तो हम छवि सामग्री के ऊपरी तिहाई की ओर से अनुक्रमणित कर रहे हैं।

आप मूल लेख (An Image Signature for any kind of Image) जिस पर libpuzzle पर आधारित है पढ़ते हैं, वे समझाने कि शब्द उत्पन्न किया जाना चाहिए "... संभवतः गैर-निरंतर और ओवरलैपिंग"। मुझे यकीन नहीं है कि उनका मतलब गैर-संगत और गैर-ओवरलैपिंग, या गैर-संगत और ओवरलैपिंग है ...

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

यह सुनना अच्छा लगेगा कि आप इसे कैसे समझते हैं।