近似最近鄰搜索中投影增強型殘差量化方法

艾列富，程宏俊，馮學軍

(1.安慶師范大學 計算機與信息學院，安慶 246133；2.安慶師范大學 智能感知與計算安徽省高校重點實驗室，安慶 246133)

引 言

最近鄰搜索是圖像檢索和機器學習領域的重要基礎性問題，但以圖像特征為代表的大規模高維特征使得精確最近鄰搜索需要花費更多的時間和更大的存儲開銷。如何快速并準確地獲得特征向量的近似最近鄰成為一個重要研究內容，即：在保證近似表示精度的情況下，如何設計緊湊的編碼來標識特征向量，降低存儲空間以及加速特征向量之間歐氏距離的計算。

根據衡量特征向量之間相似度距離的方式的不同，用于圖像特征向量近似表示的編碼算法可以劃分為哈希編碼算法和基于量化的編碼算法兩大類[1]。雖然都用于降低圖像信息的存儲空間需求，但不同于圖像壓縮[2]，用編碼對特征向量進行壓縮存儲時，允許特征向量在重構時存在誤差，但要盡可能小。

歐氏距離比漢明距離對計算需求較大，但具有更好的相似度區分能力。基于量化的編碼算法不僅采用二進制編碼標識特征向量以減少存儲空間需求，還使用近似歐氏距離保持區分能力。向量量化采用一種映射方式，又稱為量化器[3]，將特征向量映射到事先訓練的碼書中最相似的單詞,并且用于近似表示該特征向量，單詞的二進制編號用于標識與之對應的特征向量。

率先將量化模型用于近似最近鄰搜索和圖像特征檢索的積量化算法(product quantization，PQ)[4-5]，將特征向量分割為若干段子向量，并分別在子向量所在的向量空間訓練量化器。將特征向量在各量化器的量化輸出串聯起來,用于近似表示該特征向量。基于PQ的思想，學者們提出了各種改進方法，具有代表性的研究工作包括：GE等人提出用帶參量和無參量兩種笛卡爾優化分解來最小化量化誤差[6]；參考文獻[7]中采用倒排索引或多索引對特征向量集進行劃分后，再在每一個子集上進行笛卡爾優化分解；為了進一步減少量化誤差，HEO等人[8]編碼總長度不變的情況下，預留一定長度的部分編碼給相同量化輸出但量化誤差不同的向量；NOROUZI等人提出了正交k均值算法及笛卡爾積k均值算法[9]；雙層PQ[10]和局部優化PQ[11]以及利用圖形處理器(graphics processing unit,GPU)[12]從硬件層面對PQ進行加速以及用于聚類[13]等PQ的擴展應用研究。

PQ思想基于一個假設前提：特征向量的各個維度分量相互獨立，不存在相互關聯。然而，實際情況一般不會總是滿足這種假設。為此，BRANDT[14]將轉換編碼和PQ相結合，在特征向量的每個主成分維度上分別訓練量化模型。在此基礎上，子空間量化算法(即通過將向量空間劃分為多個子空間)被用來解決特征向量維度的空間分布不平衡問題[15]。類似的研究工作還包括樹形量化方法[16]對特征進行分解，在子向量空間訓練子碼書的同時對各子碼書之間非正交聯系進行約束。

上述量化模型大都考慮如何在單層碼書的前提下，盡可能地減少量化誤差，然而碼書的大小決定了量化誤差的大小。通常地，碼書中單詞的數量越多,會使量化誤差越小，然而這帶來問題的碼書訓練所需要的開銷也就越大。對此，殘差向量量化(residual vector quantization，RVQ)[17]利用多層小規模碼書構成的量化器，其碼書層數越多，量化誤差越小，特征向量的近似表示精度越高。通過對RVQ引入正交約束條件，正交RVQ[18]設計了查詢點和重構點之間近似歐氏距離計算方法。在前期研究中，提出了增強型殘差量化(enhanced residual vector quantization, ERVQ)[19]，在RVQ基礎上對碼書訓練過程進行迭代優化，主要目的是在不增加碼書規模的條件下，降低總體量化誤差，得到更準確的碼書，進而提升檢索精度。

這類模型雖然訓練得到的碼書的區分度較高，但訓練以及量化過程均發生在特征向量所在的原始向量空間。向量維度越高，帶來的最直接影響是在高維向量空間訓練碼書花費的時間越多。因此，特征向量的高維度現象是制約這類量化方法的訓練效率的關鍵因素之一。參考文獻[20]中雖然將高維向量投影到低維空間來訓練碼書，但沒有考慮到投影過程中所帶來的投影誤差。參考文獻[21]中提出了一種投影殘差量化(projected residual vector quantization,PRVQ)，在訓練量化模型時同時考慮到了投影誤差，然而卻沒有考慮殘差量化方法中存在碼書訓練并不是最優化總體量化誤差的不足。

作者在前期關于增強型殘差量化模型的研究工作基礎上，提出一種將主成分分析方法與該模型相結合的量化方法，通過將特征向量從原始高維向量空間投影到低維向量空間,并低維向量空間進行碼書訓練，提高碼書訓練的時間效率。由于降維過程使特征在投影過程中產生投影誤差，會降低所訓練的低維向量碼書的精度，而碼書的精度直接影響到特征的檢索準確率。為此，在優化碼書的過程中，同時考慮訓練碼書產生的總體量化誤差以及投影所產生的誤差。在低維空間訓練碼書旨在提高碼書訓練的時間效率；碼書優化旨在保證訓練所生成的碼書的精度。在此基礎上，設計一種針對該量化模型的特征向量之間的歐氏距離近似計算方法，提高檢索效率。

1 前期工作

作者前期所提出的ERVQ[19]是由多層碼書構成，逐級量化的量化模型。所有層的量化輸出向量通過累加形成輸入特征向量的重構向量。除去第1層和最后一層，利用每層碼書進行量化時產生的量化誤差作為下一層的量化輸入，旨在對特征向量應用多層量化盡可能地減少特征向量的近似表示誤差。ERVQ由碼書訓練和量化特征向量兩個部分構成。

1.1 ERVQ碼書訓練

為了使訓練得到的多層碼書能更準確地對輸入特征向量近似表示，ERVQ利用k均值算法訓練得到每一層初始碼書后，通過總體量化誤差目標函數對初始碼書進行迭代優化。其中，采用RVQ[17]來訓練進行迭代優化所需的初始碼書；在此基礎上，對每一層碼書按順序進行迭代優化，不斷更新碼書。

一次迭代過程包括所有層碼書的順序優化。對于某一層碼書，其優化的具體實現思路是基于其它層的碼書，把該層碼書當作最后一層碼書進行重新訓練，并將新的碼書代替原來的碼書以及更新訓練集的量化輸出[22]。當目標函數收斂到一定程度時，迭代優化過程停止。

1.2 ERVQ量化特征向量

給定特征向量v，圖1是一個兩層ERVQ的逐層量化過程示意圖。

Fig.1 Quantizing feature vector by ERVQ

(1)

式中，i表示當前層碼書的層號；C1為第1層碼書的k個聚類中心對應的集合，k為每層碼書的聚類中心數；ci,j為第i層碼書中第j個聚類中心。

(2)根據下式，計算v的第1層量化誤差對應的誤差向量e1:

(2)

對于層數大于2的ERVQ，需要繼續將第2層的量化誤差輸入到第3層進行量化,直到最后一層。

2 投影增強型殘差量化

投影增強型殘差量化方法將主成分分析方法和前期研究的增強型殘差量化方法相結合，在低維空間訓練量化模型得到碼書以提高訓練效率，與此同時，為了減少投影誤差對碼書精度的影響，通過迭代優化的方式提升碼書精度。

投影增強型殘差量化分為訓練階段和量化階段，其中，訓練階段用于量化模型訓練得到多層低維空間的碼書；量化階段則是對圖像特征向量進行量化生成編碼的過程。

2.1 碼書訓練

碼書訓練分為兩個階段：初始碼書訓練和碼書優化兩個階段。

2.1.1 初始碼書訓練 初始碼書訓練過程采用類似于PRVQ[21]方法，每層初始碼書的訓練過程需包括步驟：利用主成分分析(principle component analysis,PCA)構造降維投影矩陣、訓練集投影降維、低維向量空間上利用k均值算法訓練碼書、低維向量空間上量化訓練集、逆投影和總體殘差向量計算。

針對圖2所示訓練兩層初始碼書的示例，第1層初始碼書訓練過程如下：首先，利用PCA在訓練集X上生成用于特征向量降維的投影矩陣M1，并將X投影到低維向量空間得到X1；然后，利用k均值算法對投影降維后的訓練集進行聚類，生成第1層碼書C1；緊接著，利用第1層碼書，根據(1)式對訓練樣本集X1中特征向量進行量化；最后，利用逆投影矩陣，將X1的量化結果逆投影到原始維度,計算和原始向量之間的誤差向量集E1并作為第2層碼書訓練的輸入。

第2層初始碼書C2的訓練同第1層初始碼書的訓練方法一致，同樣通過以上幾個步驟完成。

2.1.2 碼書聯合優化 基于上述得到的初始碼書，提出一種聯合優化方法，通過降低特征向量的總體量化誤差來對初始碼書進行優化，期望得到區分度更高的多層碼書，進而提高特征向量的近似表示精度。

對于L層(碼書總層數L>1)初始碼書，其優化方法是一個順序優化的過程，即：從第1層碼書開始依次優化直到最后一層碼書。

對于第i層(1≤i≤L)碼書，其優化過程通過以下步驟完成：(1)計算訓練樣本集中每個樣本特征向量與其它層對應的量化結果對應向量之和的殘差向量。這里，由于特征向量與其對應量化結果對應的向量維度不同，因而在此計算過程中，需要根據每層碼書對應的逆投影矩陣，將量化結果投影到原始向量的維度空間;(2)更新碼書。對具有相同第i層編碼的樣本特征向量對應的殘差向量求均值,并將其作為新的碼書;(3)根據新生成的碼書，對訓練樣本集進行量化，更新從第i層碼書到最后一層碼書對應的編碼。

Fig.2 Training two-level initial codebooks

2.2 特征向量量化

給定一個特征向量v，圖3中給出了投影增強型殘差量化對v進行量化的兩層示例。具體過程如下：(1)利用訓練階段得到的第1層投影矩陣，將v投影降維到第1層碼書所在低維向量空間得到vp；(2)基于第1層碼書，根據(1)式對vp進行量化,得到Q(vp);(3)利用投影逆矩陣，將第1層的量化輸出逆投影到原始高維向量空間，計算v與逆投影向量之間的殘差向量e1；(4)利用事先訓練的第2層投影矩陣，將e1投影降維到第2層碼書所在的低維向量空間得到e1,p；(5)根據第2層碼書，利用(1)式對e1,p進行量化,得到Q(e1,p)。

Fig.3 Quantizing vector by projection-based enhanced residual vector quantization

如果投影增強型殘差量化模型的層數大于2，那么特征向量在之后碼書層的量化方式與第2層一致。

3 近似最近鄰完全檢索

為了評估投影增強型殘差量化對特征向量的近似表示精度，類似于參考文獻[19]，設計近似歐氏距離計算方法并用于完全檢索。

(3)

式中,μ為應用PCA之前用于調整中心的均值向量，cv,l∈Cl,cv, l(D×1向量)為v(d×1向量)在第l層碼書Cl的量化輸出，D為投影降維后的向量維度，d為向量的原始維度，L為投影增強型殘差量化的碼書總層數，MlT(d×D投影矩陣)為第l層的逆投影矩陣。

(4)

4 實 驗

4.1 實驗數據集和實驗環境

本文中將在GIST和VLAD兩個公開數據集[23]上評估應用了投影增強型殘差量化在碼書訓練和完全檢索方面的性能。如表1所示，GIST和VLAD兩個數據集包含3個子集，其中，訓練集用于訓練碼書；數據庫集是用于獲取從中檢索同查詢點近似的特征向量；查詢集用于對檢索算法進行性能評估。

Table 1 Information of experimental datasets

所有實驗都是在一臺Intel Core i5 2.8GHZ CPU, 32G內存的PC，MATLAB 2011環境下完成的。

4.2 投影維度對量化誤差的影響

圖4和圖5反映了GIST和VLAD數據集上投影維度D∈{23,24,25,26,27,28,29}對總體量化誤差的影響。實驗參量設置中，投影增強型殘差量化的每層碼書中聚類中心數量k固定為256，碼書層數為L∈{4,8,16}。

Fig.4 Overall quantization errors over variant projected dimensionality on GIST

Fig.5 Overall quantization errors over variant projected dimensionality on VLAD

如圖4和圖5所示，當碼書層數固定時(如L=8)，隨著PCA投影的維度從512維～8維的變化，總體誤差呈現出先減少后增加的曲線變化。觀察發現，當投影維度D=128維時，GIST和VLAD數據集上總體量化誤差最小。

4.3 投影維度對檢索精度的影響

圖6和圖7反映了GIST和VLAD數據集上投影維度D∈{23,24,25,26,27,28,29}對檢索精度(用召回率Rrecall@n(n=100)表示，其中n表示檢索返回的結果數量)的影響。實驗參量設置中，投影增強型殘差量化的每層碼書中聚類中心數量k固定為256，碼書層數為L∈{4,8,16}。

如圖6和圖7所示，從投影維度512維開始，檢索精度先是隨著維度降低而不斷提升直到投影維度為128維，隨后檢索精度隨著投影維度的降低而不斷降低。對比圖6和圖7，參量D的變化對VLAD數據集上檢索精度的影響比GIST更大。

Fig.6 Rrecall@100 over variant parameter D on GIST

Fig.7 Rrecall@100 over variant parameter D on VLAD

4.4 同其它方法實驗對比

針對最近鄰搜索的性能對比，將投影增強型殘差量化(projected enhanced residual vector quantization,PERVQ)與其它4種方法(見表2)從檢索精度和檢索效率(檢索時間)兩個方面進行比較。在表2所示4種方法的相關文獻[4,17-19]中，依據參考文獻中實驗數據，綜合檢索速度和檢索精度平衡，都是采用8個子碼書,并且每個子碼書都是由256個聚類中心構成。

Table 2 Description of compared methods

所有方法均采用相同的編碼長度，檢索精度用召回率Rrecall@n指標進行評估。

為公平起見，PERVQ采用同PQ，RVQ，ERVQ和正交RVQ相同的碼書參量，即L=8層碼書構成的8級子量化器，并且每層碼書的碼書規模設置為256。

4.4.1 訓練碼書的時間開銷對比 PERVQ建立在ERVQ的基礎上，解決ERVQ在原始高維向量空間訓練碼書帶來的碼書訓練時間效率受特征向量維度制約的問題，旨在提升碼書的訓練效率的同時，綜合投影誤差和量化誤差對低維向量空間的碼書進行優化。

圖8為GIST數據集上RVQ,ERVQ以及投影到各個向量維度D∈{23,24,25,26,27,28,29}上，訓練8層碼書對應碼書所花費的時間。相比RVQ，由于ERVQ和PERVQ都增加了碼書優化步驟用于提升碼書精度，因而額外增加了優化碼書階段的時間開銷。從圖8可以觀察到，將PCA和ERVQ結合后，PERVQ訓練碼書花費的時間要明顯少于ERVQ，此外，當D∈{23,24,25}時，PERVQ訓練碼書所花費的時間比RVQ少。

Fig.8 Time cost comparison of different methods on GIST

4.4.2 檢索精度對比 從圖6可以觀察到，在GIST數據集上，當L=8，各層碼書規模為256個聚類中心，PERVQ在D=128時，具有最優的近似最近鄰完全檢索精度。圖9為在GIST數據集上不同方法的檢索精度。PERVQ采用8層碼書，每層碼書初始聚類中心數為256。從圖9可以看出，PQ方法檢索性能明顯不如其它方法，RVQ和ERVQ由于考慮了量化誤差，在相同編碼長度下，其檢索精度有了較大提升，優于積量化。PERVQ不僅考慮了總體量化誤差，也考慮了投影誤差，檢索精度較殘差量化方法好于RVQ,ERVQ和PQ。PERVQ同orthogonal RVQ具有相當的檢索精度，但orthogonal RVQ是在原始高維向量空間進行多層碼書訓練和優化。

Fig.9 Rrecall@n comparison of different methods on GIST

4.4.3 檢索效率對比 在GIST數據集上對不同方法的檢索時間進行了比較，所有方法的參量設置同上，檢索時間如表3所示。

Table 3 Comparison of search time on GIST

PERVQ,ERVQ,RVQ和orthogonal RVQ在應用完全檢索時都是利用向量的近似表示來計算查詢向量和庫向量之間的近似歐氏距離。不同之處在于ERVQ,RVQ以及orthogonal RVQ的查找表構造是在高維空間進行，而PERVQ的查找表是在低維空間進行構造，因而PERVQ生成查找表比ERVQ和RVQ具有更快的速度，但是PERVQ將查詢向量投影到低維空間相比RVQ和ERVQ需要花費額外的投影時間。因此當構造查找表對效率的提升程度大于向量投影對時間效率影響程度時，PERVQ比ERVQ,RVQ以及orthogonal RVQ具有更好的檢索速度。

由表3可見，PERVQ的近似最近鄰完全檢索在投影維度D∈{23,24,25}時，其檢索時間花費少于PQ,RVQ和ERVQ。結合圖6和圖9，當D∈{23,24,25}，PERVQ仍具有同ERVQ和orthogonal RVQ相當的檢索精度。

5 結 論

提出了一種投影增強型殘差量化方法，通過結合前期研究工作，在訓練碼書時，將圖像視覺特征從高維向量空間投影到低維向量空間，降低訓練過程中的時間開銷；為了降低投影到低維向量空間帶來的投影誤差，在訓練碼書的過程中，同時考慮量化和投影所產生的誤差，進而保證所生成碼書的精度。實驗結果表明，提出的PERVQ在碼書訓練時間效率上，較ERVQ具有明顯提升作用，同時保證了檢索精度。