Lost in Binarization : Query-Adaptive Ranking for Similar Image Search with Compact Codes

Lost in Binarization : Query-Adaptive Ranking for Similar Image Search with Compact Codes

Summary:
本篇作者為了改進Hamming Distance會有很多vector pair會共享同樣的distance，但在作image search的時候如此就無法找出較適合的ranking，進而會使效果變差。作者提出了一個在同樣的Hamming Distance時query-adaptive ranking的方法，能夠預先算好在每個class中的weighting，而當query進來的時候再去動態算出一個屬於query的weighting，進而達到較好的image search結果。
這篇paper提出的query-adaptive weight，主要有兩個好處。一是利用bit-level weights，可以將query找出的結果找出一個從粗到細的rank，也就是可以把ranking的精細度從原來的d提升到2的d次方。二是相較只用既有的一組weight來給query使用，作者提出的query-adaptive weight可以使query找出一個更貼近其主題的weight，進而達到更好的效果。

其細節如下:
1. 作者探討了三種資料結構，包含inverted index、tree-based index和binary embedding。當把inverted index套用到VW作image search時，會碰到一個原來在text裡面沒有的問題-關鍵字太多，一個文字的搜尋關鍵字平均而言只會有四個，但在一個image query中VW的數量可能高達幾百個，因此不適合。而在tree-based index則會遇到不適合拿來作高維向量的問題。因為假設是d維向量，有n個sample時，tree-based index要在n>>2^d時才會比exhaustive search有效率。因此作者選用了binary embedding中的SSH和DBN來使用。
2. 其系統的架構如下:
a. 利用Lowe的DoG detector和SIFT descriptor來計算BoW feature，在此系統使用了約500個VW。有了每張圖的BoW feature之後，再透過SSH或DBN轉成binary code(Hamming space)。
b. 在有了每張圖的binary code之後，再利用已經label好的圖片，對於每個semantic class算出屬於那個class的bit-level weight。假設共有k組semantic class，這k組weight的解，則是希望達到兩個目的:
i. Intra-class中的總和distance最小，有點像是K-means的那種感覺，同一個class中的每個點到其中心(每個點的平均)之距離要越小越好。而在這裡的distance則是經過weight(ai)加成過的，即|| ai˙x – ai˙ci ||^2 。
ii. Inter-class中的總和distance最大，即每個class兩兩之間的距離要越大越好，這裡的距離則是經由各自weight(ai & aj)加成過的向量差所算出來的，即|| ai˙ci – aj˙cj ||^2 。
但是同時要作的這兩個項的極小化，作者提出了以遞迴的方式來解目標的quadratic program，最終可以求出每一組class所對應到的weight。
c. 每當有一個query進來的時候，系統會動態算出一個屬於這個query的bit-level weight(aq)，而計算每兩張圖之間的距離的公式就會變成: || aq˙xq – aq˙xt ||^2 。但是這邊的aq要如何算出呢? 作者假設在query中top k的解(直接用hamming distance所算出來的解)當中，數量前三多的class中的weight的加權平均，即為aq的解，如此一來就可以算出query-adaptive weight了。
3. 在實驗的部分，作者使用了NUS-WIDE dataset來測試，因為其已經label好了81個semantic class/label。作者分別對DBN和SSH兩種方式來作測試，其在code length為48時表現皆比為36時好，並且和baseline傳統的hamming distance相比，表現有4.6%~9.5%的成長。

Critiques:
這篇提出的query-adaptive weight的方法，成功改進了原來的hamming distance沒辦法在同一群內排出ranking的問題，且在training process雖然要花上一天左右的時間，但實際在搜尋一張圖時只要花很短時間，很符合作搜尋的需求。另外，在這篇裡面所使用的SIFT加到BoW的概念，不知是否能夠改成套用上周的那篇paper中所提到的aggregating的概念，說不定會有意想不到的好效果。