Liocean

Paper Information

Gong, Yunchao, and Svetlana Lazebnik. “Iterative quantization: A procrustean approach to learning binary codes.

" Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on. IEEE, 2011.

Introduction

當我們在做照片的檢索時，例如google的以圖找圖，為了加快搜尋時間以及降低index的儲存空間，

必須先將高維的圖片以低維的二元編碼來表示，如此可以加快搜尋時間。

至於該如何合理的編碼是此篇論文欲探討的問題

Contribution

編碼必須符合三個原則：

1.編碼的長度必須夠短，否則所需的儲存空間仍然可觀

2.像似的圖片其編碼的Hamming distance要越短越好

3.編碼過程的效率要高

此篇論文探討的是原則二

Summarization

這篇論文使用的方法為Iterative Quantization (ITQ)，透過將資料mapping到以0為中心的binary hypercube, 使得quantization error最小化。

步驟一：先利用PCA降維以減少維度

X：原始數據

V：降維後的數據

W：欲求

步驟二：利用Binary quantization進行優化

對v進行量化的動作得到sgn(v), 求v與sgn(v)的Euclidean distance最小化。將所有數據集進行二進位編碼後可得B, 所有v所組成的矩陣為V, 則我們欲求的式子為min|| B – V ||²。

對矩陣旋轉可讓量化誤差更小, 誤差從1降為0.93:

最佳化公式可以改成以下：

求(B、R)得最佳化