Aggregating local descriptors into a compact image representation

Aggregating local descriptors into a compact image representation

Herv´e J´egou INRIA Rennes
Matthijs Douze INRIA Grenoble
Cordelia Schmid INRIA Grenoble
Patrick P´erez Technicolor
========================================================

這篇paper主要的目的是要做一個large-scale image search
著力點在三方面：
1. accuracy
2. efficiency
3. memory usage
所以這個系統不但要結果好，同時在空間及時間運用上都要有效率

paper裡提到很多篇related work
上面所提到的三個目的在很多paper 裡都有研究
但通常都是只針對其中的某一項
這篇的作者比較像是集大成然後再統整
所以方法也是用之前別人用過的，然後再加以修改
步驟跟目的也有說明很清楚，主要可以分為三個
1. aggregate local descriptors
2. dimensionality reduction
3. indexing system
以下將對每項作說明：

1. aggregate local descriptors:
這步就是取feature然後作fusion，最後會形成一個high-dimension vector
這裡用的方法是BOF跟Fisher kernel，然後再aggregate成SIFT descriptors
作者把最後的結果vector 稱為VLAD
再用 K-means 作quantization 然後把每個word跟centroid difference 存起來

2. dimensionality reduction:
在1. 作完之後，每張image都有一個high dimension vector可以代表
這步的目的就是要做降維，用兩個方法 a. projection(PCA), b. quantization
這裡找 nearest neighbor用的方法是 product quantization-based approximate search method
先找出重要的 centroids 再把之前的結果 quantize 成這些 codes
再用PCA去找出最具代表性的dimensions
這裡在paper裡用比較多的數學來說明他們的結果可以work及運算方法

3. indexing system:
有了2. 的codes後，就可以把每張image都用這些codes來表示
然後用IR的方法去作inverted indexing
利用這樣去加速搜尋的結果，而不能用pair-wise comparison
paper裡最後用20 bytes 來代表一張圖

實驗的部分
作者有作了一些實驗去找出適合的 K 和 D 的值
然後去算出他的方法mAP
接著再跟 miniBOF(state-of-art)方法比較
他提出的方法用的byte較少，mAP也比較高
最後再用large-scale data 上去算 mAP 效果也能夠維持
有提到用inverted file ADC 只要 46 ms 就可以，等於是可以real-time
========================================================

這篇paper的條理很清楚
一步一步依序寫下來，用的字也很淺顯易懂
大概是對image search 比較有概念，所以都能理解他做這些步驟的目的跟想法

優點：
1. 這篇算是集大成，求好、求快、求效率，全部都有考慮到
2. 方法論述很清楚，都會說明這個步驟的目的，而不是單純寫作法
3. 相關的related work 優缺點都有提出，並且說明哪個方法為什麼不用，哪裡要改進
4. 實驗有提供state-of-art的結果，更加有說服力

缺點：
1. K 跟 D 的值像是用trial-and-error的方法去找，沒有比較有說服力的決定方法
但這個部分是trade-off 因為 K 跟 D 愈大，搜尋花的時間就愈高
2. 最後用的real-time方法 IVFADC or ADC 對 mAP的犧牲都很大，從圖上可以看到
跟baseline(BOF)至少下降0.1  等於是變差至少30%，但paper裡對這個部分說明沒有很清楚
只有強調花的時間很少
3. state-of-art 只是針對accuracy，並不是跟large-scale system的state-of-art做比較(除非沒有)
而且這篇的方法是去improve state-of-art 因此在不考慮時間效率下，應該就是要比較好