基于重心坐標乘積量化的圖像檢索方法

張萬麒，王永利，陳廣生

(1.南京理工大學 計算機科學與工程學院， 江蘇 南京 210094；2.華電能源股份有限公司 佳木斯熱電廠， 黑龍江 佳木斯 154000)

0 引 言

相似性查詢，亦稱為最近鄰(NN)查詢，由于維數災難，對于高維數據而言，準確的最近鄰查詢是極具挑戰的問題。為了盡可能用較少的查詢時間和內存損耗發現最近鄰，從而解決高維數據的最近鄰查詢問題，相關領域出現許多有關近似最近鄰(ANN)查詢方法的研究，例如哈希、基于樹方法、矢量量化等方法。

本文研究的是近似最近鄰查詢中的矢量量化(VQ)方法，對于ANN查詢來說是一個典型高效的數據編碼方法。VQ需要更多位數來減少量化誤差。但隨著編碼位數增加，碼本大小也呈指數級增長，基于VQ的方法對于高維數據來說作用效果不明顯。為了解決這個問題，乘積量化(PQ)[1]給出一個高效索引高維圖像特征的范例。采取將高維特征空間分解成低維特征子空間的笛卡爾積的形式，然后分別進行量化。因為每個子空間維數相對較小，使用一個小尺寸碼本很容易獲取到令人滿意的查詢效果。盡管將長矢量分解成子部分的形式會使計算損耗明顯減少，但由于高量化誤差，PQ不能在高精準度情況下檢索一個查詢值的確切最近鄰。目前已有一些方法來解決這個問題。Gong和Lazebnik[2]提出一種迭代量化的方法，將數據映射成二進制編碼來進行快速檢索。Cartesian K-means[3]和Optimized Product Quantization[4]兩種方法采用了旋轉原始數據的方法來減小量化誤差。但包括PQ在內的這些方法均遵循著VQ的基本原理，都不可避免地造成了高量化誤差。為了解決高量化誤差問題，本文提出一種方法，稱作重心坐標乘積量化(BCPQ)。乘積量化方法可高效地壓縮數據空間，在其基礎上改進編碼方式，將任意矢量量化到距離其最近的3個碼字所形成單純形的重心上，可有效地減少編碼所帶來的量化誤差，并大幅提高ANN的查詢精度。

1 相關工作

1.1 近似最近鄰查詢技術

最近鄰查詢是在學術上進行大量研究的一個熱點課題，如多媒體應用、圖像分類和機器學習等。最近鄰查詢方法大體上被分為3類：基于哈希的方法[5]、KD樹[6]和矢量量化方法[1,4]。

基于哈希的近似最近鄰查詢方法獲得了大量的學術關注。大部分采用了隨機映射或者基于學習的方法來形成壓縮二進制編碼。作為結果，兩個數據矢量間的相似性近似地用它們哈希編碼的漢明距離來表示。隨機映射是一個保存成對數據點間距離的有效方法。最具有代表性的例子是局部感知哈希(LSH)[7]。根據Jonson Lindenstrauss定理，LSH需要O(lnn/ε2)的隨機映射來保存成對距離值，其中是相對誤差。因此，LSH需要使用長編碼位數來增強映射表現，但這會造成大的計算損耗和內存需求。另一方面，基于學習的哈希方法嘗試學習輸入數據的結構。大部分這些算法通過使用數據關聯矩陣的譜特性來形成二進制編碼，例如項與項之間的相似性。一些其它的哈希方法也使用了多模態數據或語義信息。盡管用相當短的編碼可以實現很好的效果，但這些方法隨著編碼長度的增加都不能獲得最近鄰查詢效果。

研究的第二類別是用KD樹來加速ANN查詢。KD樹查詢的平均復雜度是O(Dlogn)，同時窮舉查詢的平均復雜度是O(nD)。然而，由于維數災難，對于高維數據來說，KD樹不如窮舉查詢更高效。盡管如此，隨機KD樹[8]和分層K-means[9]都提升了KD樹的查詢表現。特別地，這兩種方法都包含在FLANN。FLANN用于在高維空間中執行快速近似最近鄰查詢的庫。包含已經發現的最適合最近鄰查詢的算法集合，以及根據數據集自動選擇最佳算法和最優參數的系統。FLANN比起其它公開可得的ANN查詢軟件更快。然而，KD樹方法需要完全掌握數據空間的數據結構，因此在查詢階段需要更多的內存。

研究的第三類別是矢量量化方法，嘗試用碼本中的碼字來近似數據矢量。Jègou等[1]提出了一個高效的乘積量化(PQ)方法。PQ的關鍵是把高維特征空間分解成一個低維特征子空間的笛卡爾積的形式，然后使用相應預定義的碼本分別進行量化。之后查詢相似性矢量可以用對稱距離計算(SDC)或非對稱距離計算(ADC)。同時，應用倒排文件系統可以進行高效的非窮舉查詢。實驗結果表明，就精確性而言，PQ明顯優于基于哈希的方法。正如在文獻[1]中被討論的一樣，輸入數據底層結構的先驗知識對于VQ是至關重要的。最近，Ge等[4]把PQ視作一個優化問題，通過優化查詢碼本和空間分解來最小量化誤差。但由于VQ[10]固有的性質，通過硬編碼方式，將數據矢量量化到最近的碼字上，造成了高量化誤差影響。

1.2 軟編碼

詞袋(bag of words)是一個在信息檢索中針對文本文件(網頁)處理的典型模型。已成功地應用到計算機視覺領域，包括基于內容的圖像檢索，圖像分類，精細目標分類。計算機視覺里的詞袋模型把局部圖像特征視作單詞，因此典型地稱為視覺詞袋(bag of visual words)模型。視覺詞袋模型首先匹配從圖像區域中提取的圖像局部描述符，然后把描述符量化到一個單一矢量上，最后根據簽名矢量來檢索圖像。視覺詞袋模型與矢量量化緊密相關，把一個描述符編碼到最近鄰上。然而VQ中的硬匹配導致較大的量化誤差，降低了圖像檢索表現。對于這個問題的直觀解決方案是設計一個軟編碼，讓編碼分布到多個鄰近詞上。這樣一個軟編碼實質上減小由VQ固有的硬編碼所造成的量化誤差，提升了檢索精度。

在文獻[12]中提出一種根據與描述符距離成反比的核函數來分配權重的軟編碼方案，稱為核碼書編碼(KCB)。基于稀疏和局部編碼方案[13,14]，提出了局部軟編碼(LSA)編碼方案[15]。這個方案使用了局部性和最大池化，比已有的稀疏或局部編碼方案實現起來有更好的表現。盡管KCB和LSA都具有視覺詞的不確定性，但這些視覺詞的不確定性是“人為的”，因為是通過累加分子使得分母歸一化產生的。在本文中提出一個新穎的基于重心坐標的軟編碼方案。其中視覺詞的不確定性是“自然的”，因為它是作為區域坐標的重心坐標，一種物理上的幾何屬性。

綜上所述，現有的乘積量化方法基于VQ的硬編碼導致較大的量化誤差，無法滿足更高的檢索精度。本文結合重心坐標軟編碼概念，結合重心坐標軟編碼和乘積量化方法，可以將檢索精度提升到一個滿意的結果。

2 模型與定義

本文提出重心坐標乘積量化(BCPQ)方法進行圖像檢索，方法框架如圖1所示。

圖1給出了一個數據集，提取出圖像特征，分為訓練集和gallery集。然后把訓練特征集劃分成乘積空間形式來構建碼本。通過碼本和Gallery集來進行量化編碼。對應編碼和碼本放在查詢表中，給出的查詢集圖像根據查詢表找出最相似的圖像。

圖1 BCPQ方法框架

2.1 矢量量化

定義1 碼本(codebook)：一個數據集分成一些組，設x是數據集中的一個D維矢量，即x∈D，c是將數據集分組后相應組的聚心，I是一個有窮下標集，令I=1,…,k，q為一個量化器，令q(x)∈C={ci;i∈I}，C是長度為k的碼本。

矢量量化(VQ)是數據壓縮的一個經典的技術。給出一個向量x∈D，VQ把x映射到一個預訓練碼本C={ci,i=1,2,…,k}如下

(1)

定義2 量化誤差：輸入矢量x和它的量化值q(x)之間的平方誤差

(2)

稱e(x)為x的量化誤差。

2.2 乘積量化

遵循著乘積量化(PQ)，本文把高維空間分解成低維子空間的笛卡爾積形式，然后分別在每個子空間上執行矢量量化。具體地，一個矢量x可視作m個子矢量的串聯：x=[x1,x2,…,xm]，碼本可定義為C=C1×C2×…×Cm。

對于PQ，每個子矢量被映射為相應碼本的一個子碼字

(3)

式中：qi是x的第i個子向量的量化器。x被均等地劃分以便全部子向量xi∈D/M，其中D是m的倍數。注意到根據不同的碼本，每個子向量被分別編碼。在這種情況下，碼本C中x的任何碼字c將是m個子碼字的串聯：c=[c1,c2,c3,…,cm]，其中每個ci∈Ci，i∈[1,m]。

通常，本文需要量化一組向量x={xi,i=1,…,n}而不是單獨一個。因此x的量化誤差可定義為E(x)=∑x∈Xe(x)。

正如在等式(3)中，可見PQ把等式(1)劃分成m個子VQ問題，從而分別解決。因此，PQ方法可有效地減小特征空間維度，壓縮數據空間，而產生ANN查詢的精準結果。然而，由于矢量量化[10]固有的硬編碼方式導致不可避免的量化誤差，限制了它查詢精準性的表現。

下面將介紹一種方法，能夠高效地降低量化誤差并提升查詢精度。

2.3 重心坐標

重心坐標被Mobius在1827年[14]中提出。它們形容一個參考三角形的重心為3個質心的幾何聚心。在三角形內，重心也稱為區域坐標，因為一個三角形的內部點P的重心與這個點及其相對應外部三角形頂點形成的子三角形區域成比例(如圖2(a)中分別為ΔPBC,ΔPAC,ΔPAB)。

圖2 重心坐標與截斷

定義3 重心坐標：設Λ設為一個仿射空間，p1,…,pk是Λ中的頂點，可以形成一個單純形。對于Λ中的某點p，如果

(u1+…+uK)p=u1p1+…+uKpK

(4)

滿足u1,…,uK中至少一個不等于0，稱系數(u1,…,uK)為點p對應于仿射空間Λ中p1,…,pk的重心。

以上定義的重心坐標為同質的，等價于一個常量。為了獲取唯一的重心坐標，采用歸一化

(5)

仿射變換下不變，故重心坐標具有仿射不變性。

重心坐標定義中p1,…,pk是單純形的頂點，則意味著矢量p2-p1,…,pk-p1是線性獨立的。然而這個需求不是一直滿足的。因此，根據單純形定義一個普遍的重心坐標。

假設Ω為仿射空間Λ中頂點p1,…,pk形成的一個單純形。如果滿足以下3個屬性，uk:Ω→,k=1,…,K可稱為一個普遍的重心坐標。

uk(p)≥0,?k(non-negativity)

(6)

(7)

(8)

注意非負條件式(6)只在點p∈Ω有效。如果一個點在單純形Ω外，普遍的重心坐標為負，考慮此種情況如下，采用截斷的方式，如圖2(b)所示。

2.4 基于重心坐標的軟編碼

重心坐標軟編碼的基本想法是把一個數據矢量量化到3個局部最近鄰形成的單純形重心上，代替量化到一個最近鄰。

令c1,…,cK為碼本的K個聚心。在重心坐標軟編碼中讓C=(ci1,…,ciM)∈D×M成為一個局部描述符d∈D的M個最近鄰，其中D為描述符的維數，u為描述符d的重心坐標。根據重心坐標的定義，以及3個屬性式(6)～式(8)將推導出以下等式

C×u=d

(9)

(10)

其中，式(10)結合式(9),讓

(11)

其中，引進λ(如：λ=104)，使其歸一化。可得到一個單一等式

(12)

這樣原始式(1)現在重新被公式化為

(13)

Subject toum≥0,?m

(14)

以上的等式是一個非負最小二乘法問題，可通過迭代地計算一組基本矢量和相應的對偶矢量來解決。然而這個計算對于大量的描述符的編碼效率不高。為了解決這個問題，應用一個簡單的截斷技術(如圖2(b)中展示的)。重心坐標[-0.43，0.57，0.87]的點P=(1.0,1.5)截斷后的坐標為[0,0.57,0.87]，然后用l1范數正則化為[0,0.4,0.6]，表示近似點P’=(0.40,1.05)。

提出的重心坐標軟編碼方案遵循以下步驟：

(2)把負數u元素截斷為0：um=max(0,um),?m；

(3)用l1范數重新正則化u。

2.5 重心坐標乘積量化

圖3展示了一個2D-toy的例子來解釋本文提出方法的關鍵想法。圖3(a)為ADC示例，其中x為查詢值，y為數據集中一個D維矢量，q(y)為距離y最近的3個碼字形成單純形的重心坐標。在VQ中將y量化編碼到距離其最近的d2碼字上，屬于硬編碼。而在提出的BCPQ方法中將y軟編碼量化到重心坐標q(y)，這種量化編碼進一步減少了硬編碼所帶來的量化誤差。圖3(b)為SDC示例，將查詢值x同樣進行軟編碼量化。其中x屬于圖2(b)情況，量化到q(x)。

選擇BCPQ的優勢在于：

性質1 重心坐標乘積量化保留了編碼的線性順序精度

證明：

提出的BCPQ方法的一個特性是普遍重心坐標能夠保留線性順序精度。令uk:Ω→,k=1,…,K為一個單純形Ω內的重心坐標，Φ:Ω→Ω是任一線性轉化

(15)

上述公式直接由普遍重心坐標定義而來，結合式(8)和線性化

(16)

這個屬性理論上證明了提出的BCPQ方法對于編碼線性轉換具有魯棒性。

證畢。

在提出的重心坐標矢量量化方法中，本文表示數據庫中每個矢量x如下：x≈C×u，其中u為x的重心坐標。受乘積量化所推動，在本文中，本文使用所提出的重心坐標乘積量化(BCPQ)方法。根據向量劃分為子向量方法，將x替換成它的子向量xi。因此，本文能夠通過等式來近似xi:xi≈Ci×ui,i=1,2…,m。

圖3 重心坐標矢量量化的2D-toy示例,分別為ADC和SDC兩種情況

3 算 法

3.1 量化編碼

重心坐標乘積量化編碼階段算法1。

Algorithm 1：Encoding stage in barycentric coordinates product quantization

Input:

The databaseX=[x1,…,xn]，the codebook sizek,

the subspace numbers

Output: barycentric coordinatesu

(1) Sample a subsetXsofX.

(4) end for

(5) for each subspaceXiofXdo

(7) Truncate the negativeucomponents to 0:um=max(0,um),?m

(8) Re-normalizeuwith l1norm.

(9)endfor

算法復雜度分析：編碼部分包括提取數據庫中子集后進行的碼本學習和在數據庫的每個子空間下進行重心坐標的求解。讓D表示每個特征矢量的維度，對于一個給定的查詢，編碼部分算法復雜度為Ο(nD+kD)，取決于數據庫中的總項數n和碼本尺寸k。

3.2 近似最近鄰查詢

本文將提到的BCPQ方法應用到針對大范圍圖像檢索任務的ANN查詢。

特別地，為了加快ANN查詢，本文使用提出的BCPQ方法來編碼庫中的全部數據矢量。然后本文計算一個查詢q和數據庫中數據的距離，使用兩種距離測量：ADC和SDC。

根據定義，ADC公式化為

(17)

至于SDC計算，本文使用重心坐標乘積量化來近似查詢矢量q：qi≈Ci×vi,i=1,2…,m，相似地，SDC可計算為

(18)

為了更好地解釋，圖3展示了一個2D距離計算的ADC和SDC版本。

SDC相比于ADC唯一的優勢在于限制了與查詢矢量相關的內存消耗，因為查詢矢量用一個編碼定義。然而在大多數情況下影響不大，使用非對稱版本可以在相似的復雜度情況下獲得一個更多的距離失真。因此在文本提出的BCPQ方法中使用ADC版本，相應的查詢階段算法2如下：

Algorithm 2：Query stage in barycentric coordinates product quantization

Input：The query setQ=[q1,…,qm]and the number of NNp

Output：The toppANN indexsI, the toppANN distancesD

(1) for each queryqof Q

(2) for each subspaceqiofqdo

(3) Precompute lookup tableTiwithqiandCi

(4) UsinguandTito compute the approximate distancesEito the dababase on this subspace.

(5) end for

(6) Sum up the approximate distancesE=∑iEi.

(7) Search the toppNNs based onEand save them toIandD.

(8) End for

算法復雜度分析：查詢部分中輸入查詢集和最近鄰數，為每一個查詢值的每一個子空間進行lookup表查詢，時間復雜度為O(ms)，其中s為每個查詢值矢量的子空間數，m為查詢集的大小。

4 實驗分析

為了驗證本文所提出的近似最近鄰查詢模型BCPQ的高效性，將進行一組大規模實驗，驗證在3個數據集上的表現，同時與幾個先進的ANN方法進行比較。本實驗擬從誤差度(distoration)、準確率(precision)、召回率(recall)、平均正確率(mAP)這4個指標來評價算法的性能。本文利用matlab語言實現了本文的BCPQ算法，實現環境見表1。

表1 實驗環境

4.1 數據集

本文采用的3個數據集均為公開可得的圖像特征集SIFT、GIST以及MNIST。每個數據集被劃分成3個部分：訓練集，gallery set和查詢集。這些數據集總結如下：

(1)SIFT數據集由1 000 000個128維的局部SIFT特征組成，其中100 000個樣本被用來學習碼本。全部1 000 000個樣本被用來作為gallery set，10 000個樣本被用來作為評估。其中訓練集和gallery set間沒有重合，因為前者從Flicker圖像提取的，后者是從INRIA Holidays圖像中提取的；

(2)GIST由960維全局特征組成。有50 000個樣本被使用來學習碼本。相似地，在數據庫中的1 000 000個樣本被視作gallery set，1000個樣本被用作查詢評估。它們分別從tiny圖像集，Holidays圖像集，Flicker1 M Holiday集中提取的；

(3)MNIST是全部70 000幅784維手寫數字的圖像集。在本文的實驗中，本文隨機地采用1000幅圖像作為查詢，余下的數據被視作gallery set。為了學習碼本，本文隨機地從gallery set獲取7000幅。

表2總結了在本文實驗中使用的數據集的統計數字。

表2 本文實驗中使用的數據集的統計數字

4.2 對比方法

本文用以下主流的方法，包括乘積量化(PQ)、優化乘積量化(OPQ)、笛卡爾積K-means(CK-means),以及FLANN，與本文提出的BCPQ方法進行比較。

(1)product quantization(PQ)試圖在笛卡爾積空間構建碼本，被看作基線。IVFPQ引用倒排文件結構在PQ上。在實驗PQ的全部結果從原始實現中復現。

(2)optimized product quantization(OPQ)針對發現PQ的一個優化空間分解。相似地，本文采用他們自己的實現作為默認配置。

(3)Cartesian K-means(CK-means)是另一種來發現PQ最優的空間分解方式。

(4)FLANN是基于搜索樹框架最受歡迎的開源ANN查詢工具箱。能夠自動地選取最好的算法和參數對于給定的數據集。

4.3 與基于矢量量化的其它方法相比

第一列到第三列分別是SIFT，GIST和MNIST數據集。第一排呈現的是誤差vs編碼位數的測試比較；第二排呈現的是mAP vs編碼位數的測試比較；第三排呈現的是當發現50個最近鄰時R vs Recall的測試比較。

首先本文檢測在不同編碼長度下不同方法的量化誤差。通過圖4可以看出，本文提出的BCPQ方法在全部數據集上與其它矢量量化方法相比均有更小的量化誤差。然后本文使用了mAP作為測量標準。結果如圖4所示，可見本文的方法優于其余方法。最后本文測試了當查詢50個真實最近鄰時的召回率。同樣從結果中清晰可見，本文的方法優于其它相比較的方法。

4.4 與FLANN相比

本實驗本文采用SIFT作為實驗數據集，評估了在給定查詢時間下的精準率。如參照PQ[15]，本文采用一個倒排文件來加速BCPQ方法。FLANN包括重排序階段來計算參考最近鄰的確切距離，本文也在BCPQ方法里添加了重排序功能。通過實驗，本文的方法在6 s的時間里獲得了95.4%的準確率，FLANN花費6.4 s獲得了84.2%的準確率。圖5展示了實驗結果。

5 結束語

本文提出一個重心坐標乘積量化的方法把高維特征空間編碼成稀疏表示。兩個矢量間使用量化后的編碼計算歐氏距離，來獲得最近鄰。使用數據矢量稀疏表示的方式最小化了量化誤差，使結果表示更接近實際中的原始數據。本文已經在3個公開數據集上進行了大量的實驗來評估提出的重心坐標乘積量化方法。實驗結果表明本文的方法更快更精確。今后的研究方向，進一步縮短內存和計算損耗的同時，來提高查詢精準性。

圖4 在不同數據集上與FLANN測試比較

圖5 與FLANN進行的測試比較