原文：http://blog.csdn.net/liuheng0111/article/details/52242491
IterativeQuantization: A Procrustean Approach to Learning Binary Codes 論文理解及代碼講解
這篇文章發(fā)表在2011年CVRP上，一作是Yunchao Gong，師從Sanjiv Kumar，關(guān)于Sanjiv Kumar可以到她的HomePage上了解。
文章目的：學(xué)習(xí)保留相似度的二值碼彰阴，以用于高效的在大規(guī)模數(shù)據(jù)集中做圖像檢索。本文介紹了在無監(jiān)督的數(shù)據(jù)集中用PCA來學(xué)習(xí)ITQ锈麸，在有監(jiān)督的數(shù)據(jù)集中用CCA來學(xué)習(xí)ITQ讼育。
首先介紹學(xué)習(xí)二值碼的重要性：
計算機視覺越來越重視學(xué)習(xí)相似性保存的二進制代碼來代表大規(guī)模的圖像集合手形。它主要有三個優(yōu)點：
（1）?????用短的二值碼來代圖像啥供，可以在內(nèi)存中存儲大量的圖像。
（2）?????比較兩幅圖像相似性库糠，用二值碼來計算hamming距離滤灯，非常快速曼玩，高校鳞骤。
（3）?????用這個方法可以代替大規(guī)模圖像索引方法。
學(xué)習(xí)二值碼有三個重要的特性：
（1）?????編碼要短黍判。（16G的內(nèi)存豫尽，存儲250million圖像在內(nèi)存里的話，對于每圖像只能使用64bits）
（2）?????圖像映射到二值碼后顷帖，兩個編碼要盡可能的相似美旧，也就是原來兩幅圖像距離大，映射到二值碼后贬墩，hamming距離也很大榴嗅。
（3）?????用來學(xué)習(xí)二值碼的算法要足夠的高效，并且對新的圖像編碼成二值碼要efficient陶舞。
ITQ的思想：
（1）?????用PCA對原始數(shù)據(jù)進行降維（如果有監(jiān)督則用CCA來降維）
（2）?????然后把把原始數(shù)據(jù)分別映射到超立方體的頂點嗽测，因為超立方體的頂點是二值碼，求解量化誤差最小的映射方式。量化二值碼的方法是：hk(x) = sgn(xwk)唠粥，用sgn函數(shù)來量化疏魏。
（3）?????本文的創(chuàng)新點是對這個超立方體在空間中旋轉(zhuǎn)，然后求解初旋轉(zhuǎn)矩陣就可以得到最好的映射方式晤愧。
（注意：文章不是直接對超立方體進行旋轉(zhuǎn)大莫，而是對數(shù)據(jù)進行旋轉(zhuǎn)后，再映射到立方體上官份，相當(dāng)于物理上運動的相對性只厘，數(shù)據(jù)旋轉(zhuǎn)，立方體不動舅巷，可以看成數(shù)據(jù)不動羔味，立方體在旋轉(zhuǎn)，一樣的道理悄谐，文章為了方便求解旋轉(zhuǎn)矩陣介评，對數(shù)據(jù)進行旋轉(zhuǎn)库北。）
對于unsupervised code learning
ITQ 步驟可以簡答的概括為（將原始d維向量映射到c維的二值碼）：
（1）假設(shè)數(shù)據(jù)是centralized爬舰，如果不是，用程序進行centralized寒瓦。X是原始數(shù)據(jù)（n*d維矩陣）情屹，中心化的matlab代碼：
sample_mean = mean(X, 1);
X = bsxfun(@minus, X,sample_mean);
（2）將原始數(shù)據(jù)做一個PCA投影，這一步主要是為了降維杂腰。具體PCA降維過程不做過多贅述垃你。
covX = X' * X / size(X,1);?
OPTS.disp = 0;
[eigVec, eigVal] =eigs(double(covX), num_bits, 'LM', OPTS);
X = X * eigVec;
（求解離散度矩陣的特征值，選出前C個最大特征值對應(yīng)的特征向量做為投影矩陣喂很，這樣就把原始數(shù)據(jù)降維到c維）
（3）二值量化
假設(shè)第二步求得降維矩陣維W惜颇，然后將數(shù)據(jù)映射到了空間中的一個一個點，現(xiàn)在就是要將空間中的點映射到一個邊長為1的超立方體中少辣，以原點為空心凌摄，方方正正的放在空間中的超立方體是二值碼的（為方面記這個超立方體為Q0）。但如果我們對數(shù)據(jù)進行一個旋轉(zhuǎn)再映射到這個空間中漓帅，會得到更小的量化誤差锨亏。這個想法類似于如果我們只是要將數(shù)據(jù)映射到邊長為1的立方體中，而不需要固定超立方體的具體位置忙干，這就等同于對數(shù)據(jù)進行旋轉(zhuǎn)器予，再映射到以Q0。
降維后的數(shù)據(jù)：V=XW
旋轉(zhuǎn)后的數(shù)據(jù)：VR?? （R是旋轉(zhuǎn)矩陣捐迫，必須是c*c維的正交矩陣）
最小化映射誤差：
等價于：
問題等價于最大化：
但是這里R也是未知的乾翔，B也是未知的，對于求解這樣的為題施戴，我們使用迭代求解的方法末融，固定一個钧惧，優(yōu)化另一個。
求解這個問題分兩步：
（1）????固定R,求解B
由于R是正交矩陣勾习，作者使用隨機初始化R為正交矩陣浓瞪。隨機的方法：
R = randn(bit,bit);? // 隨機生成一個矩陣
[U11 S2 V2] = svd(R); //對矩陣做SVD分解，U和V都是正交矩陣
R = U11(:,1:bit);?? //選取U作為隨機初始化的正交矩陣R
R固定了巧婶，求解B相當(dāng)簡單乾颁。最大化
因為這里B的元素只有1和-1（因為是二值碼，作者用-1表示0艺栈，這樣只是為了求解問題簡單）英岭，所以B =sgn(V R)。
?
（2）????? 固定B,求解R
這是一個線性代數(shù)的問題orthogonal Procrustes problem湿右。
這個為題的原型是對A做一個正交投影诅妹，于B盡量相似：
所以本文中，
文章迭代求解50步毅人，即可得到最后二值碼的編碼方式吭狡。
?% ITQ to find optimal rotation
for iter=0:n_iter
??? if mod(iter,10)==0
??????? fprintf('ITQ: iter: %d \n', iter);
??? end
??? Z = V * R;?????
??? UX = ones(size(Z,1),size(Z,2)).*-1;
??? UX(Z>=0) = 1;
??? C = UX' * V;
??? [UB,sigma,UA] = svd(C);???
??? R = UA * UB';
end
% make B binary
B = UX;
B(B<0) = 0;
求得B,R之后，整體的編碼方式是：
BincodeXtrainingITQ =compactbit(bsxfun(@minus, Xtraining, sample_mean) * eigVec * R > 0);
?
利用label信息的ITQ二值碼的映射：
給你一個訓(xùn)練集矩陣X丈莺，n*d維划煮，一共n個向量，每個向量有d維〉薅恚現(xiàn)在額外給你一個帶標簽的矩陣Y弛秋，n*t維，你是訓(xùn)練集矩陣的向量個數(shù)俐载，t是標簽的個數(shù)蟹略，Y(i,j)=1,表示訓(xùn)練集中的第i個向量和第j個標簽有關(guān)系。反之Y(i,j)=0表示訓(xùn)練集中的第i個向量和第j個標簽沒有關(guān)系遏佣。對PCA比較了解的人都知道挖炬，PCA是無監(jiān)督的降維方法。PCA降維出來的矩陣只是最大限度的保留矩陣的能量贼急，但是不能確保選擇的投影pc對于分類是有用的茅茂，比如原來的數(shù)據(jù)是完全可分的，但用PCA降維后完全不可分太抓。所以作者給出了利用帶標簽的降維方法空闲，CCA。
CCA 的英文全稱是Canonical Correlation Analysis走敌，目標是找到特征的投影W矩陣和標簽的投影矩陣U碴倾，是的投影后的XW和YU的相關(guān)性最大。
在本文中，作者使用
如果我們得到了W,就不用得到U跌榔，應(yīng)為我們得到W的作用是對數(shù)據(jù)進行降維异雁，而U在以后的ITQ過程中是無用的。
得到降維矩陣后僧须，其余操作和前面相同纲刀。
