杜丹蕾，羅恩韜，唐雅媛，李延浚

（1.湖南科技學院電子與信息工程學院，湖南 永州 425100；2.中南大學信息科學與工程學院，長沙410083；3.朝陽科技大學，中國臺灣 臺中 41349）

面向圖像檢索的累加乘積量化方法研究

杜丹蕾1，羅恩韜2，唐雅媛1，李延浚3

（1.湖南科技學院電子與信息工程學院，湖南 永州 425100；2.中南大學信息科學與工程學院，長沙410083；3.朝陽科技大學，中國臺灣 臺中 41349）

針對經典的乘積量化方法易受數據相互依賴關系限制的問題，提出一種累加乘積量化方法。對高維特征向量進行正交分解，得到相互獨立的特征向量子空間，依據壓縮效率要求，對各特征向量子空間進行進一步分解，得到相互不獨立的特征向量次子空間，對次子空間采用累加量化方法進行編碼，對子空間采用乘積量化方法進行編碼，在保障壓縮效率的前提下降低數據相互依賴關系對量化精度的影響。實驗結果表明，與經典的乘積量化方法和笛卡爾K-均值方法相比，該方法的編碼誤差較小，在圖像檢索應用中的查全率較高。

圖像檢索；特征提取；編碼；乘積量化；非對稱距離計算

DO I：10.3969/j.issn.1000-3428.2015.10.042

1 概述

近些年多媒體技術發(fā)展迅猛，圖像作為最為基本的多媒體信息，應用非常廣泛。隨著圖像數據規(guī)模的擴大，如何從海量圖像數據中高效、準確地找到需要的圖像數據成為迫切需要解決的問題。圖像檢索技術是解決這一問題的關鍵技術，已成為多媒體領域的研究熱點［1］。按照檢索內容進行分類，圖像檢索技術可分為2類：基于文本的圖像檢索（Text-based Image Retrieval，TBIR）［2］和基于內容的圖像檢索（Content-based Image Retrieval，CBIR）［3］。TBIR需要事先對圖像進行文本注釋，然后通過基于文本的數據庫管理技術實現圖像檢索，但文本注釋工作量大，且易受人的主觀因素影響。CBIR通過理解圖像內容來實現圖像檢索，基本思路是：首先從圖像中提取特征，然后構建特征向量，最后通過計算特征向量

之間的距離來查詢圖像之間的相似度，尋找最相似的圖像作為圖像檢索結果。CBIR的相似度查詢過程可以看成特征向量空間的最近鄰（Nearest Neighbor，NN）搜索問題［4］，通過計算查詢向量與整個數據庫中特征向量的距離，并按距離進行排序，篩選出距離最近的特征向量作為最近鄰搜索的解。當特征向量維數較高時，最近鄰搜索的計算量會大幅增加，引起“維數災難”［5-6］，此時必須采用有效的高維數據索引機制來加速檢索過程［7］。量化是降低特征向量維數、實現高維數據索引的有效途徑［8］，其基本原理是：編碼時構建碼本，從中搜索與輸入特征向量最匹配的碼字，用其索引輸入特征向量，進行傳輸、存儲和處理；解碼時采用簡單的查表操作，還原出原特征向量。量化可以大幅降低特征維數，從而降低數據處理的空間復雜度，為面向高維數據的圖像檢索提供條件。

常用的量化方法可分為2類：一類是采用二值編碼的思想［9-10］，將特征向量壓縮為較短的比特流數據，降低數據存儲空間，再采用壓縮向量之間的漢明距離近似替代原始向量之間的歐氏距離，從而可以在低維空間上實現特征的檢索。另一類是采用乘積量化（Product Quantization，PQ）的思想［11-13］，將特征向量進行正交分解，在分解后的低維正交子空間上進行量化，由于低維空間可以采用較小的碼本進行編碼，因此可以降低數據存儲空間［14］。PQ方法采用基于查找表的非對稱距離計算（Asymmetric Distance Computation，ADC）快速求取特征向量之間的距離，在壓縮比相同的情況下，與采用漢明距離的二值編碼方法，采用ADC的PQ方法的檢索精度更高。然而，PQ方法假設各子空間的數據分布相互獨立，當子空間數據的相互依賴較強時檢索精度下降嚴重。

為了克服PQ方法受數據依賴關系影響大的問題，本文提出一種累加乘積量化（Cumulative Product Quantization，CPQ）方法。與PQ方法類似，CPQ方法也將特征向量分解為若干部分，每一部分采用獨立的碼本進行編碼，再由各部分編碼數據的累加和來表示原特征向量。特征向量之間的距離也可采用基于查找表的ADC方法快速求取。但在特征向量的分解過程中，CPQ只需將相互獨立的數據劃分到正交子空間，而各子空間的數據再進行分解時不受數據相互依賴關系的影響，但最終的壓縮效率可以與PQ方法相當。另外，CPQ中的碼本可以采用優(yōu)化方法進行學習，從而提高檢索精度。

2 乘積量化

一般地，特征向量維數越大，特征匹配效果越好，如尺度不變特征轉換（Scale-invariant Feature Transform，SIFT）［15］特征。然而，維數的增大導致計算復雜度增加、存儲空間占用增大。為解決這一問題，常采用量化技術對數據進行壓縮處理，降低表示空間的基數。

設X∈RD表示一個D維向量，量化過程可以表示為：

其中，f表示量化函數；ci表示第i個碼本；C為對應碼本的質心，也稱碼字。

可見，量化是采用碼字重構特征向量的過程。這一過程難免存在誤差，常采用均方誤差最小準則來選擇失真最小的碼字進行量化，即：

其中，向量χ為輸入圖像的向量表示。

均方誤差越小，量化性能越好。因此，需要采用優(yōu)化理論訓練出最優(yōu)的量化器，常用的是L loyd算法。但是當特征向量維數很大時，訓練量化器的空間復雜度也很大。對于一個可產生64位（8 Byte）編碼的量化器，對應碼字為K=28個，此時，訓練量化器的空間復雜度很大，采用Lloyd算法存儲包含K個碼字的D×K個浮點數據是很難實現的。此時可以采用乘積量化方法，降低量化器訓練的空間復雜度。具體地，將特征向量X劃分為M個子向量uj，1≤j≤M，這樣每個子向量的維數下降為以前的1/M。然后每個子向量單獨使用一個量化器進行量化，這樣特征向量X被映射成如下形式：

其中，fj是第j個子向量的量化器，對應的碼本為cj。這樣，特征向量X的碼本可以表示為各個子向量碼本的乘積形式，即：

由于每一個子向量的維數大幅降低，采用L loyd算法訓練各個子量化器的空間復雜度也大幅降低。在碼字相同的情況下，存儲空間消耗可降低為原來的1/M。

3 本文方法原理

3.1 CPQ介紹

據前一節(jié)所述，PQ方法通過將高維特征向量拆分為多個低維特征向量來降低向量編碼的空間復雜度。然而，PQ方法有一個前提條件，即假設拆分后的各子空間相互獨立。對于一個D維的特征向量，為了降低編碼的空間復雜度，拆分后的子空間數量M越大越好。然而，在許多實際應用中，D維特征向

量很難拆分為許多相互獨立的子向量。假設D維特征向量最多可以拆分為M1組相互獨立的子向量，而空間復雜度要求是將其拆分為M（M大于M1）。如果拆分為M組子空間，那么這M組子空間的數據存在依賴關系，會影響量化精度。為了解決這一問題，本文提出CPQ方法，具體是將采用PQ方法拆分的M1個子空間再進行一次拆分，每個子空間拆分為M2個子空間，且M=M1×M2。在M2個子空間上，采用累加量化（Cumulative Quantization，CQ）方法進行量化處理，在保障量化效率的同時，降低空間復雜度和提高量化精度。

3.2 CQ原理

CQ與PQ方法一樣，也是將D維向量劃分為M個子向量，對應M個碼本，每個碼本包含K個碼字。記第j個碼本為cj，第i個碼字中的第j個碼本為cj（i）。然而，PQ中碼字長度為D/M，而CQ中碼字長度為D，與待編碼特征向量長度一致。

對于特征向量X，采用CQ方法可以將其編碼為M個碼字的總和：

對于相同的參數M和K，CQ和PQ編碼向量的內存占用相同，但CQ編碼的精度更高。

本文提出的CPQ方法包含距離計算，向量編碼和碼本學習3個階段：

（1）距離計算

在圖像檢索過程中，數據量龐大的特征向量數據庫需要采用高效的量化方法進行壓縮存儲，同時，在進行特征檢索時，還需要從數據庫中快速找到與待查詢的未壓縮的特征向量相匹配的壓縮特征向量，匹配準則一般為最近鄰準則。PQ量化的最大優(yōu)點是可以采用ADC算法快速計算待查詢特征向量和量化后的特征向量數據庫之間的距離，這一過程僅需要M次查表運算、M-1次加法運算和其他所需的少量運算，而 CQ量化也可具備這一優(yōu)勢。

假設q為量化前的特征向量，也稱查詢向量，y為量化后特征向量數據庫中的任一向量，數據庫中總樣本數為L，q與y之間的歐氏距離為：

對于采用CQ方法得到的壓縮向量y，可以表示為式（1）的形式。此時，可以采用查找表快速計算〈q，y〉，具體地，令：

則：

而當查詢向量q確定時，Tm（i）可以預先計算

m并存儲在查找表中。這樣，遍歷數據庫計算〈q，y〉時，總的計算復雜度包括計算查找表的復雜度O（D×M×K）和計算實際內積的復雜度O（M×L）。盡管PQ中計算查找表的復雜度只有O（D×K），但實際應用中數據庫中的樣本數L遠大于D×K，故O（M×L）的計算量遠大于O（D×M×K），因此CQ和PQ方法在距離計算方面的計算量相當。的計算也可以采用查找表的方法進行，具體地：其中，式（9）右邊的部分都是數據庫中的已知項，可以預先計算并存儲在查找表中。這樣，計算大約需要M2/2次查表和加法運算。可見，的計算花費與空間維數 D無關。而且由于與待查詢向量q無關，也即對于任意查詢向量是相同的，可在構建數據庫時一起計算并存儲為查找表，這樣在實際的特征向量檢索過程中，的計算僅用一次查表運算即可。

（2）向量編碼

對于特征向量y，給定碼本為c1，c2，…，cm，尋找使編碼誤差E最小的碼字來作為向量χ的CQ編碼，其中：

將上式代入式（6），則：

M

對于給定的y，Um（im）和Vm（im）可以預先計算和存儲，而是常量，對于最小化E沒有意義，可以省略。故式（11）可以改寫為：

上式可采用條件迭代模型（Iterative Model

Conditions，ICM）算法［16］和環(huán)路置信傳播（Loopy Belief Propagation，LBP）算法［17］等常用的最優(yōu)化方法求解。

（3）碼本學習

碼本學習就是尋找一組碼本｛c1，c2，…，cm｝對特征向量Y=｛y1，y2，…，yn｝進行編碼，使編碼誤差最小，也即：

與其他碼本學習方法相似，本文采用塊坐標下降策略，在imj和cm之間交替進行最小化。給定碼本的編碼變量最小化需要編碼給定碼本的向量 yj，而更新碼本對應碼字的過程可以等價于以下最小二乘問題：

當參數n和D較大時，上述最小二乘問題的求解非常困難。為此，將式（16）分解為 D個最小二乘問題，每個最小二乘問題涉及的變量只有 K和 M。這樣，可以采用如下的線性方程求解：

其中，cm（k）表示第d個cm（k），同樣向量y表示

d

j，d第d個向量yj。式（18）定義了n個關于變量K和M的方程，可以采用最小二乘法求解。另外，對于D個不同尺寸的最小二乘求解問題，由于式（18）在不同尺寸下存在遞推關系，因此可以采用遞推方法快速求解。

4 基于CPQ的圖像檢索

如圖1所示，圖像檢索主要包括建庫和檢索2個過程：

（1）建庫：對于給定的圖像數據庫，通過圖像理解模塊提取各個圖像的特征向量，通過量化技術對特征向量進行壓縮處理，建立圖像數據庫對應的特征數據庫。

（2）檢索：對于輸入的待檢索圖像，通過與建庫過程相同的圖像理解模塊提取圖像的特征向量（查詢向量），計算查詢向量與特征數據庫中量化后的各特征向量之間的距離，選擇距離最近一個或多個的特征向量作為匹配的特征向量，再通過索引查找這些特征向量對應的圖像，即可得到要檢索的圖像。

圖1 圖像檢索流程

在上述過程中，圖像的特征向量提取有很多種方法，譬如SIFT、Haar［18］等，特征向量提取的好壞對圖像檢索結果影響很大，但這部分不是本文的研究重點，這里不再贅述。

一般地，圖像數據庫中圖像數量龐大。為提高圖像查全率，需要對圖像的特征向量進行壓縮處理。本文采用CPQ方法進行壓縮，步驟如下：

Step1 對D維特征向量進行正交分解，得到M1個子特征向量。

Step2 對M1個子特征向量進一步分解，得到M2個次子特征向量。

Step3 采用CQ方法，對M2個次子特征向量進行量化編碼。

Step4 采用PQ方法，對M1個子特征向量的CQ編碼結果進行進一步量化編碼，最終得到含M= M1×M2個碼本的編碼結果。

在特征向量查詢階段，按前文所述的距離計算方法，求取查詢向量與數據庫中特征向量間的距離，返回距離最近的T個特征向量作為查詢結果。

5 實驗結果與分析

實驗的目標為驗證本文方法的性能。為了便于對比，本文不考慮圖像特征的提取過程，直接選用文獻［12］所述的SIFT特征庫作為實驗數據庫，執(zhí)行圖像檢索的建庫和查詢2個核心任務。該數據庫包括100 000個SIFT特征向量和10 000個查詢向量，每

個特征向量的維數D=128，每個查詢向量在數據庫中對應一個匹配向量，已事先標記。

實驗中將本文提出的CPQ方法與經典的PQ［12］和笛卡爾K-均值（Cartesian K-means，CKM）［13］方法進行對比。在建庫階段，采用3種不同的量化方法對數據庫中的SIFT特征向量進行壓縮，計算采用不同方法產生的編碼誤差，評價不同方法的量化精度。在查詢階段，計算查詢向量與數據庫中采用不同量化方法得到的壓縮向量之間的歐氏距離，采用最近鄰搜索方法在數據庫中搜索與查詢向量距離最近的T個壓縮向量，再與事先標記的匹配結果進行對比，統計查全率指標，評價不同方法的檢索性能。

5.1 編碼誤差

量化是一種有損編碼方法，普遍存在編碼誤差。編碼誤差越小，說明量化方法的性能越好。本文對比了不同量化方法在不同編碼長度（即碼本個數M）和碼字尺寸（即每個碼本碼字個數 K）下的編碼誤差（原向量與量化后向量平方差），如圖2和圖3所示。

圖2 編碼長度不同時的編碼誤差對比

圖3 碼字尺寸不同時的編碼誤差對比

在圖2中，取參數K=256，M分別取4，8和16，CPQ方法中M1和M2與M的對應關系如表1所示。

表1 CPQ方法中編碼長度參數取值

在圖3中，取參數M=4，K分別取32，64，128，256和512。從圖中可以看出，在不同的編碼長度和碼字尺寸下，CPQ方法的編碼誤差都要低于PQ和CKM方法。

5.2 查全率

查全率是圖像檢索常用的評價指標［19］。假設數據庫內特征向量總數為 L，對于第i個查詢向量，數據庫中相匹配的特征向量數量為Ni，檢索輸出相似度最大的Ni+T幅圖像（T為檢索余量）。如果輸出圖像中包含ni幅相匹配的圖像，則查全率為：

圖4和圖5顯示了不同方法在不同參數T下的查全率曲線，其中，圖4所示為M=8的情況，圖5所示為M=16的情況。CPQ方法中M1和M2與M的對應關系仍如表1所示，參數K都取為256。從圖中可以看出，相同參數下CPQ方法的查全率要高于PQ和CKM方法。

圖4 M為8時不同方法的查全率對比

圖5 M為16時不同方法的查全率對比

表2對比了不同方法的檢索耗時。為便于對比，以PQ方法為基準，其檢索耗時記為1。從表中可見，CKM和CPQ方法檢索耗時都要大于PQ方法，且CPQ方法耗時最多，可見CPQ方法還需要進一步提升。

表2 不同算法檢索耗時對比

6 結束語

本文對經典的PQ方法進行改進，提出一種新的CPQ方法。通過對高維特征向量進行降維來提高壓縮效率。為了克服PQ方法對數據獨立性的依賴，先采用正交分解得到相互獨立的子空間，再對不具備獨立性的數據子空間采用普通分解，得到次子空間，最后在非正交的次子空間上采用CQ方法進行編碼，而在正交的子空間上采用PQ方法進行編碼，這樣可以在壓縮效率與PQ方法相當的情況下，降低數據相互依賴關系對量化精度的影響。實驗結果表明，該方法在圖像檢索應用中編碼誤差較小，查全率較高。

［1］ Worring M，Santini S，Gupta A，et al.Content-based Image Retrieval at the End of the Early Years［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（12）：1349-1380.

［2］ 黃祥林，高 蕓.一種基于關鍵詞的中文文檔圖像檢索方法［J］.中文信息學報，2007，21（4）：61-64.

［3］ 萬華林，Chowdhury U M，胡 宏，等.圖像紋理特征及其在CBIR中的應用［J］.計算機輔助設計與圖形學學報，2003，15（2）：195-199.

［4］ Cover T.Nearest Neighbor Pattern Classification［J］.IEEE Transactions on Information Theory，1967，13（1）：21-27.

［5］ Laughlin D C.The Intrinsic Dimensionality of Plant Traits and Its Relevance to Community Assembly［J］. Journal of Ecology，2014，102（1）：186-193.

［6］ 薄樹奎，李盛陽，朱重光.基于統計學的最近鄰查詢中維數災難的研究［J］.計算機工程，2006，32（21）：6-8.

［7］ 薛向陽，羅航哉，吳立德.LIFT：一種用于高維數據的索引結構［J］.電子學報，2001，29（2）：192-195.

［8］ 葉航軍，徐光祐.基于矢量量化的快速圖像檢索［J］.軟件學報，2004，15（5）：712-719.

［9］ Buhler J.Efficient Large-scale Sequence Comparison by Locality-sensitive Hashing［J］.Bioinformatics，2001，17（5）：419-428.

［10］ Gong Y，Lazebnik S.Iterative Quantization：A Procrustean Approach to Learning Binary Codes［J］.IEEE Conference on Computer Vision and Pattern Recognition，2011，42（7）：817-824.

［11］ Ge Tiezheng.Optimized Product Quantization for Approximate Nearest Neighbor Search［J］.Conference on Computer Vision and Pattern Recognition，2013，36（4）：2946-2953.

［12］ Jegou H，Douze M.Product Quantization for Nearest Neighbor Search［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（1）：117-128.

［13］ Norouzi M，Fleet D J.Cartesian K-means［C］//Proceedings of IEEE Conference on Computer Vision& Pattern Recognition.Washington D.C.，USA：IEEE Press，2013：3017-3024.

［14］ 李 峰，蔡 瓊.基于SIFT的圖像盲取證方法［J］.計算機工程，2011，37（14）：233-235.

［15］ 紀 華，吳元昊.結合全局信息的SIFT特征匹配算法［J］.光學 精密工程，2009，17（2）：439-444.

［16］ Besag J.On the Statistical Analysis of Dirty Pictures［J］.Journal of the Royal Statistical Society B，1986，48（3）：48-259.

［17］ Andersen S K，Judea P.Probabilistic Reasoning in Intelligent System s：Networks of Plausible Inference［J］. Artificial Intelligence，1991，48（91）：117-124.

［18］ 甘 玲，朱 江，苗 東.擴展Haar特征檢測人眼的方法［J］.電子科技大學學報，2010，39（2）：247-250.

［19］ 魏 海，沈蘭蓀.基于分類矢量量化的圖像壓縮和檢索算法［J］.電子學報，2001，29（7）：933-936.

編輯 劉冰

Research on Cumulative Product Quantization Method for Image Retrieval

DU Danlei1，LUO Entao2，TANG Yayuan1，LEE Yenchun3
（1.School of Electronics and Information Engineering，Hunan University of Science and Engineering，Yongzhou 425100，China；2.School of Information Science and Engineering，Central South University，Changsha 410083，China；3.Chaoyang University of Technology，Taichung 41349，Taiwan，China）

For solving the problem that the classic Product Quantization（PQ）method is restricted on data’s independence，a Cumulative PQ（CPQ）method is proposed in this paper.Orthogonal decomposition is executed on the high-dimensional feature vectors to obtain independent sub-spaces of feature vectors，and decomposes every subspace again according to the compression efficiency，and obtains dependent sub-sub-spaces of feature vectors，uses Cumulative Quantization（CQ）method to quantify the vectors sub-sub-spaces，and uses PQ method to quantify the vectors from subspaces.The new method reduces the impact of data’s independence on accuracy of quantization，under the premise of maintaining the compression efficiency.Experimental results show that the new method has small code error compared with classical PQ and Cartesian K-means（CKM）methods，and high recall rate in the application of image retrieval.

image retrieval；feature extraction；encoding；Product Quantization（PQ）；Asymmetric Distance Computation（ADC）

杜丹蕾，羅恩韜，唐雅媛，等.面向圖像檢索的累加乘積量化方法研究［J］.計算機工程，2015，41（10）：226-231.

英文引用格式：Du Danlei，Luo Entao，Tang Yayuan，et al.Research on Cumulative Product Quantization Method for Image Retrieval［J］.Computer Engineering，2015，41（10）：226-231.

1000-3428（2015）10-0226-06

A

TP391

湖南省科技廳科技計劃基金資助項目（2014FJ6095）；湖南省教育廳高校優(yōu)秀青年基金資助項目（14B070）；湖南省教育廳科學研究基金資助項目（湘財教指［2011］91號）；永州市指導性科技計劃基金資助項目（永科發(fā)［2013］17號）。

杜丹蕾（1981-），女，講師、碩士，主研方向：圖形圖像處理；羅恩韜，副教授、博士；唐雅媛，講師、碩士；李延浚，副教授、博士。

2015-04-10

2015-05-30E-m ail：dudanleihn@163.com