Aggregating local descriptors into a compact image representation

Summary:

本篇作者提出了一個利用local descriptor(SIFT)中的特性，來對於整張圖片作一個描述，進而可以利用dimension reduction等方法，在image search中不論在運算效率上和記憶體的使用上皆有了改善。其細部內容如下:

1. 作者提出了一個方法VLAD(vector of locally aggregated descriptors)，其方法是如同BOF先建立出一個有k個visual word的codebook，而不同於BOF將一個local descriptor用NN分類到最近的visual word中，VLAD所採用的是計算出local descriptor和每個visual word(c­_i)在每個分量上的差距，將每個分量的差距加總起來，就可以形成一個新的向量來代表圖片。

2. 之後再利用asymmetric distance computation(ADC)的方式來作approximate nearest neighbor的動作。而ADC的方式是用將原來一個query在一個set中找NN的方法，改成把set中的既有的n個向量y先利用一個有k個centroid的quantizer先切好，這樣一來就可以將y的向量encode成log2(k) bit。此外，由於如果當k值很大時(文中舉例當k=2^64)，要建出codebook將是不太可行的方式，於是他再將每個D維向量再切成m個D/m維的subvector，每個subvector再去建立一個ks個centroid的codebook，如此一來就大大降低了運算量，從最原來的O(D x n)降至O(D x ks) (因為ks<。

3. 而作者還提到了另外一個部分是要作dimensionality reduction的部分，利用PCA來降維。在裡面提到了有兩個要注意的地方，第一個是因為要在作完PCA之後再來作quantization的動作，但是作完PCA之後其實向量在每個方向的分量之variance會變得很不平衡，eigenvalue較大的向量其variance較大，但是如果照著之前一段一段去quantize的話這樣在eigenvalue較大的向量上作出來的quantization error就會變大，因此要採用一個在主要component切的較細，但是比較不重要的component的部分就切的鬆一些；第二個是降的維度D’，如果D'大的話，projection error就會小但是quantization error就會大，如果D’小的話，則是相反的情況，所以D’的選擇也是一個trade-off。

4. 作者還提出了針對D’的最佳化，並和BOF、Fisher的效能作比較。也對於有沒有對D'作optimization作比較，還有D'、k值等對效能來作探討。

Critiques:

本篇利用local descriptor的方法套入image search之中，將原本找特徵點的descriptor拿來difference累加進而描述一張image，尤其是在1000萬張圖片中的large scale database中還有一定的mAP，這種將現有的東西加以改進並套用在其他方面的想法相當新奇。而在此篇所提到的dimensionality reduction和ADC的概念，如果套到之前的object search好像也是可以實行的。