IntroductionRelated WorksApPRoximate Nearest Neighbor SearchSimilarity Preserving Binary CodesITQ代碼

Introduction

large-scale image retrieval的主要挑戰(zhàn)： 1. define similarity between images(圖片間相似度定義-cv的基礎(chǔ)問(wèn)題) 2. design compact representation for images so we can store them(設(shè)計(jì)圖片的緊湊表達(dá)，高效存儲(chǔ)) 3. design fast search schemes so we can efficiently find similar images(設(shè)計(jì)高效搜索方法)

LSH:Locality-sensitive hashing. high-dimensional vectors -> discrete representation. Based on: random projections to perform spatial partitioning.

擴(kuò)展閱讀： 1. boosting. 2. restricted Boltzmann machines.

Related Works

Approximate Nearest Neighbor Search

方法總體上來(lái)說(shuō)有O(logn)$O(logn)$和O(n)$O(n)$兩種復(fù)雜度。第一種復(fù)雜度專注于一些數(shù)據(jù)結(jié)構(gòu)，比如樹(shù)；第二種是讓暴力方法更加高效。第一種的例子是kd-tree，第二種是LSH。

Similarity Preserving Binary Codes

相似度保存的二值編碼，主要有一下三步： 1. Projection learning, or ?nding a linear or nonlinear projection of the data;(映射數(shù)據(jù)) 2. Binary thresholding, or quantizing continuous projected data to binary vectors;(量化映射后的數(shù)據(jù)到二值向量) 3. Similarity computation, or ?nding distances between query and database points.(相似度計(jì)算)

ITQ

主要思路：先對(duì)原始空間的數(shù)據(jù)集X∈Rn?d$X /in /mathbb{R}^{n * d}$用PCA進(jìn)行降維處理，設(shè)經(jīng)過(guò)PCA降維后的數(shù)據(jù)集為V∈Rn?c$V /in /mathbb{R}^{n * c}$，該問(wèn)題就可以轉(zhuǎn)化為將該數(shù)據(jù)集中的數(shù)據(jù)點(diǎn)映射到一個(gè)二進(jìn)制超立方體的頂點(diǎn)上，使得對(duì)應(yīng)的量化誤差最小，從而得到對(duì)應(yīng)該數(shù)據(jù)集優(yōu)良的二進(jìn)制編碼。

設(shè)v∈Rc$v /in /mathbb{R}^{c}$為原特征空間中某一數(shù)據(jù)點(diǎn)經(jīng)過(guò)PCA降維后的表示形式，對(duì)應(yīng)在超立方體中的頂點(diǎn)用sgn(v)∈{?1,1}c$sgn(v)/in/{?1,1/}^c$來(lái)表示，要使量化誤差最小，即v∈Rc$v/in R^c$與sgn(v)∈{?1,1}c$sgn(v)/in /{?1,1/}^c$的歐式距離最小，即min||sgn(v)?v)||2$min||sgn(v)?v)||^2$，對(duì)于所有的數(shù)據(jù)點(diǎn)進(jìn)行二進(jìn)制編碼后用B$B$表示，PCA降維后V=X?W$V=X*W$，對(duì)整個(gè)數(shù)據(jù)集為min||B?V||2$min||B?V||^2$ 。由于對(duì)矩陣進(jìn)行旋轉(zhuǎn)可以降低量化誤差，如下圖示： 從圖1可以看出，對(duì)投影后的矩陣V進(jìn)行隨機(jī)旋轉(zhuǎn)后，量化誤差降低至0.93，對(duì)于找到的最優(yōu)的旋轉(zhuǎn)矩陣，量化誤差降低至0.88(矩陣與正交矩陣相乘實(shí)際上就是對(duì)矩陣做旋轉(zhuǎn))。基于這樣一個(gè)事實(shí)，考慮將投影后的數(shù)據(jù)集V$V$進(jìn)行旋轉(zhuǎn)變換，min||B?V||2$min||B?V||^2$便變換為min||B?VR||2$min||B?VR||^2$，R∈Rc?c$R/in /mathbb{R}^{c*c}$為旋轉(zhuǎn)矩陣，正交。整個(gè)問(wèn)題域就變成了min||B?VR||2$min||B?VR||^2$的優(yōu)化問(wèn)題，即找出最優(yōu)的旋轉(zhuǎn)矩陣R$R$和與之對(duì)應(yīng)的編碼B$B$。 該式的優(yōu)化可以采用交替迭代的求解方法：先生成隨機(jī)矩陣并對(duì)其進(jìn)行SVD分解得到對(duì)應(yīng)的正交矩陣作為R$R$的初始值，然后固定R$R$求B$B$， B=sgn(V×D)$B=sgn(V×D)$（注意這里截距 b=0 ,因?yàn)樵谠臻g已對(duì)數(shù)據(jù)中心化，非常重要）,B$B$求出來(lái)再通過(guò)對(duì) B×V$B×V$進(jìn)行SVD更新R，交替迭代若干次即可，文中選用的是50次。 總結(jié)一下，整個(gè)過(guò)程可以概括為：先對(duì)數(shù)據(jù)集進(jìn)行PCA降維，然后尋找量化誤差最小的旋轉(zhuǎn)矩陣即可得到對(duì)應(yīng)該最優(yōu)旋轉(zhuǎn)矩陣下的特征向量的二進(jìn)制編碼。

代碼