原文：http://blog.csdn.net/le_le_name/article/details/51615915?locationNum=2
看過的文章，不做記錄，即便當時理解透了，過一段時間后，知識總會模糊不清。所以從現(xiàn)在開始，對一些自己閱讀過的一些精彩的文章，悉心記錄，方便自己查閱溫故，當然如果對同行有所裨益的話，亦是一件開心的事。
好了，回歸正題。這篇文章發(fā)表在2011年CVRP上，一作是Yunchao Gong，師從Sanjiv Kumar，關于Sanjiv Kumar可以到她的HomePage上了解。
這篇文章的主要思路是先對原始空間的數(shù)據(jù)集?X∈Rn×d?用PCA進行降維處理，設經(jīng)過PCA降維后的數(shù)據(jù)集為?V∈Rn×c?，該問題就可以轉(zhuǎn)化為將該數(shù)據(jù)集中的數(shù)據(jù)點映射到一個二進制超立方體的頂點上，使得對應的量化誤差最小，從而而已得到對應該數(shù)據(jù)集優(yōu)良的二進制編碼。
對于PCA降維部分，不做詳解，具體可以參閱該文[1]。設?v∈Rc?為原特征空間中某一數(shù)據(jù)點經(jīng)過PCA降維后的表示形式，對應在超立方體中的頂點用?sgn(v)∈{?1,1}c?來表示，要使量化誤差最小，即?v∈Rc?與?sgn(v)∈{?1,1}c的歐式距離最小，即?min||sgn(v)?v)||2?，對于所有的數(shù)據(jù)點進行二進制編碼后用B表示，PCA降維后?V=X×W，對整個數(shù)據(jù)集為?min||B?V||2?。由于對矩陣進行旋轉(zhuǎn)可以降低量化誤差，如下圖示：
從圖1可以看出，對投影后的矩陣V進行隨機旋轉(zhuǎn)后，量化誤差降低至0.93，對于找到的最優(yōu)的旋轉(zhuǎn)矩陣，量化誤差降低至0.88(矩陣與正交矩陣相乘實際上就是對矩陣做旋轉(zhuǎn))?；谶@樣一個事實，考慮將投影后的數(shù)據(jù)集V進行旋轉(zhuǎn)變換，?min||B?V||2?便變換為?min||B?VR||2?，R為旋轉(zhuǎn)矩陣。整個問題域就變成了?min||B?VR||2?的優(yōu)化問題，即找出最優(yōu)的旋轉(zhuǎn)矩陣R和與之對應的編碼B。該式的優(yōu)化可以采用交替跌倒的求解方法：先生成隨機矩陣并對其進行SVD分解得到對應的正交矩陣作為R的初始值，然后固定R求B，?B=sgn(V×D)?（注意這里截距?b=0?,因為在原空間已對數(shù)據(jù)中心化，非常重要）,B求出來再通過對?B×V?進行SVD更新R，交替迭代若干次即可，文中選用的是50次。
通過上面過程便可經(jīng)過PCA降維后的數(shù)據(jù)完成編碼過程，后面的相似性采用漢明距離進行度量，這里不贅述。
總結一下，整個過程可以概括為：先對數(shù)據(jù)集進行PCA降維，然后尋找量化誤差最小的旋轉(zhuǎn)矩陣即可得到對應該最優(yōu)旋轉(zhuǎn)矩陣下的特征向量的二進制編碼。
論文給出了檢索飛機的一個實例效果：
Matlab源代碼：Yunchao Gong?Homepage上公開了源碼，不過并提供數(shù)據(jù)庫，直接運行不了，我已經(jīng)對源碼進行了modify，有需要的可以看LSH、ITQ、SKLSH圖像檢索實驗實現(xiàn)(Code)這篇文章，在這篇文章中提供了modified后的代碼，也可以直接到我的GitHub主頁上下載modified后的代碼。
Github:?https://github.com/willard-yuan/ITQ_ImageRetrieval
[1]. Yunchao Gong?and S.?Lazebnik.?Iterative Quantization: A Procrustean Approach to Learning Binary Codes.?In: IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), 2011.
