Libpuzzle索引數百萬張照片？

Question

其關於來自Frank Denis先生的php的libpuzzle libray（http://libpuzzle.pureftpd.org/project/libpuzzle）。我試圖瞭解如何索引和存儲我的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個字節，使用內置的 壓縮/解壓縮功能。

相似的簽名共享相同的「單詞」，即。相同位置處的值相同的 序列。通過使用複合索引（字+ 位置），可能類似向量的集合大大減少了 ，並且在大多數情況下，實際上並不需要向量計算得到 。

通過單詞和位置進行索引還可以很容易地將 數據拆分爲多個表和服務器。

所以，是的，拼圖庫與 項目需要索引數百萬張照片是完全不兼容的。

而且我發現這個描述關於索引：

------------------------分度----- -------------------

如何快速找到類似的圖片，如果他們是數百萬記錄？

原始紙張有一個簡單而有效的答案。

以固定長度的單詞剪切矢量。例如，讓我們考慮 以下矢量：

[ABCDEFGHIJKLMNOPQRSTU VWXYZ]

隨着字長（K）的10，就可以得到下面的話：

[ABCDEFGHIJ]在位置0找到[bcdefghijk] 發現在1位[cdefghijkl]發現在位置2等 直到位置N-1

然後，索引你與（字+位置）的化合物索引向量。

即使有數百萬的圖像，K = 10和N = 100也應該足以讓 只有很少的條目共享相同的索引。

這裏是一個非常基本的示例數據庫模式：

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

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

我建議拆分至少「字」表分成多個 表和/或服務器。

默認情況下（lambas = 9）簽名長度爲544個字節。爲了節省 的存儲空間，可以通過puzzle_compress_cvec（）函數將它們壓縮到其原始大小的三分之一（原來的 大小）。在使用之前，它們必須使用puzzle_uncompress_cvec（）進行解壓縮。

我認爲壓縮是錯誤的方式，因此我必須在比較之前解壓縮每個矢量。

我現在的問題是 - 如何處理數百萬張照片，以及如何快速有效地比較它們。我不能理解「切割矢量」應該如何幫助我解決我的問題。

非常感謝 - 也許我可以在這裏找到與libpuzzle libaray一起工作的人。

乾杯。

Answer 1

我已經嘗試過使用libpuzzle - 只有你。沒有真正開始正確的實施。也不清楚究竟該如何去做。 （和被遺棄的項目由於缺乏時間 - 所以真正地沒有與它堅持）

反正現在看，會盡量提供我的理解 - 也許我們之間，我們可以工作了:)

查詢使用2階段過程 -

1. 首先您使用單詞表。
   1. 採取「參考」形象，並制定出其簽名。
   2. 制定出它的成分的話，
   3. 諮詢話表中查找所有可能的匹配。這可以使用數據庫引擎的「索引」進行有效的查詢。
   4. 編譯所有sig_ids的列表。 （會得到一些重複中3）
2. 然後諮詢簽名表
   1. retreive並解壓縮所有可能從簽名（因爲你有一個預過濾列表中的號碼應該是比較小）
   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) 
); 

現在你插入到該表的前面加上這裏所說的被發現的位置索引，讓你知道當一個字相匹配，這在同PLAC匹配E在簽名：因此

// 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"); 

你可以通過添加至少需要strength一個HAVING條款提高了查詢，從而進一步減少您的匹配集。

我不能保證這是最有效的設置，但它應該大致功能完成您正在尋找的東西。

基本上，以這種方式拆分和存儲單詞可以讓您進行粗略的距離檢查，而無需在簽名上運行專門的功能。

Answer 3

我在GitHub上做了一個libpuzzle DEMO項目：https://github.com/alsotang/libpuzzle_demo。

該項目使用Jason在上面提出的方式。

數據庫架構顯示了：https://github.com/alsotang/libpuzzle_demo/blob/master/schema.sql

---

我會給出關於libpuzzle的簽名的更多信息。

現在我們有兩個圖像，並讓我算算他們的簽名。

的奇數行是用於圖像1（左側的一個），而偶數線是用於圖像2.

，可以看到在大多數情況下，在相同的位置的數目是一樣。

....

---

我的英語這麼差，所以我不能表達我的腦海裏不斷......我認爲任何人誰想要指數百萬計的圖像應檢查libpuzzle DEMO我的GitHub庫..

Answer 4

我也在研究php中的libpuzzle，並且對如何從圖像簽名中生成單詞有一些懷疑。上述 JASONS答案似乎是正確的，但我有這部分的問題：

// 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); 
 
}

簽名向量是544個字母，並用文字上面創建我們始終只使用前110它的信件。 含義我們代表圖像內容的上三分之一索引，如果我正確理解這一點。

如果您閱讀基於libpuzzle的原始文章（An Image Signature for any kind of Image），他們解釋說應該生成單詞「...可能不連續並且重疊」。 我不確定它們是否意味着非連續和不重疊，或者不連續和重疊...

但是，如果它們表示非重疊，我猜這些單詞應該散佈在整個簽名向量中。這也會更有意義，因爲矢量是通過從左到右，從上到下評估圖像的區域而創建的。通過在整個矢量上傳播單詞將意味着您正在考慮整個圖像而不是整個矢量的上半部分（如果從矢量的開頭生成所有單詞）。

很想聽聽你們如何理解這一點。