基于PCA的哈希圖像檢索算法

馬紹覃，張 鴻

(1.武漢科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430065；2.武漢科技大學(xué) 智能信息處理與實(shí)時(shí)工業(yè)系統(tǒng)湖北省重點(diǎn)實(shí)驗(yàn)室,湖北 武漢 430065)

0 引 言

基于哈希[1-6]的圖像檢索技術(shù)致力于解決大規(guī)模數(shù)據(jù)集下圖像的查找問(wèn)題，通過(guò)將原圖像轉(zhuǎn)化為二進(jìn)制編碼表示，圖像特征轉(zhuǎn)化為對(duì)應(yīng)的二進(jìn)制編碼，不僅可以極大壓縮存儲(chǔ)空間，還能夠大幅度提高檢索速度。

圖像哈希技術(shù)的主要步驟可分為投影與量化，已有學(xué)者證明[7]，兩個(gè)階段對(duì)于圖像哈希編碼的性能都有著巨大的影響。而現(xiàn)在的研究更加偏向于投影階段，對(duì)于量化階段研究較少。本文同時(shí)從兩個(gè)方面進(jìn)行分析，在投影階段，將主成分分析(principal component analysis)嵌入，對(duì)原數(shù)據(jù)特征矩陣進(jìn)行降維，將其投影到新的特征空間中，同時(shí)盡量降低了信息的損失。在量化階段，不同于現(xiàn)在大多數(shù)哈希算法所采用的單比特量化(single-bit quantization，SBQ)，使用了一種全新的量化方法，稱為適應(yīng)性比特量化(adaptive-bit quantization，ABQ)，減少量化帶來(lái)的誤差。最后，通過(guò)綜合性的實(shí)驗(yàn)驗(yàn)證了所提算法的有效性。

1 相關(guān)工作

圖像哈希技術(shù)源自于20世紀(jì)90年代末，其思想是利用哈希函數(shù)將表示原圖像的高維特征映射到低維的漢明空間中，同時(shí)以一定的概率保證在原空間中距離較近的點(diǎn)投影后距離也近，而距離較遠(yuǎn)的點(diǎn)投影后距離也遠(yuǎn)，然后在低維的漢明空間中，利用漢明距離來(lái)衡量點(diǎn)之間的相似度。如果能產(chǎn)生良好的哈希編碼去表示原圖像，不僅能夠顯著地提升計(jì)算速度，因?yàn)楸容^距離只需要進(jìn)行簡(jiǎn)單的位運(yùn)算，而且還可以大幅度降低存儲(chǔ)量，比如，原來(lái)空間中每個(gè)數(shù)據(jù)樣本都被一個(gè)1024 B的向量表示，一個(gè)包含一億個(gè)樣本的數(shù)據(jù)集需要占用100 GB的存儲(chǔ)空間。但是,如果把每個(gè)數(shù)據(jù)樣本都映射為128位的哈希碼表示，一億個(gè)樣本的存儲(chǔ)空間只需要1.6 GB。

圖像哈希算法基本上可分為兩大類(lèi)，一類(lèi)是數(shù)據(jù)獨(dú)立型的，較為經(jīng)典的是局部敏感哈希(locality sensitive hashing，LSH)[8]和其擴(kuò)展方法[9]等，這類(lèi)方法不依賴于具體的數(shù)據(jù)，采用多個(gè)隨機(jī)生成的函數(shù)構(gòu)成投影函數(shù)簇，然后量化得到最終的哈希編碼，隨著編碼位數(shù)的提高能獲得較好的編碼效果。一類(lèi)是數(shù)據(jù)依賴型的哈希算法，也稱為基于學(xué)習(xí)的哈希算法[10-12]，通過(guò)分析樣本數(shù)據(jù)的信息來(lái)構(gòu)造投影函數(shù)，如數(shù)據(jù)固有的結(jié)構(gòu)信息和語(yǔ)義信息等。在兩類(lèi)哈希算法中，通過(guò)學(xué)習(xí)得到的哈希函數(shù)相比較隨機(jī)映射的哈希函數(shù)，在編碼位數(shù)相同的情況下，前者比后者編碼的效果普遍更好，所以現(xiàn)在的研究熱點(diǎn)基本上都是針對(duì)于前者。在數(shù)據(jù)依賴型的方法中，基于PCA的哈希算法是較為經(jīng)典的[13-15]，其大致做法是首先對(duì)原數(shù)據(jù)做PCA，得到降維矩陣后再進(jìn)行量化處理。但是，對(duì)于PCA來(lái)說(shuō)，方差越大的方向攜帶的信息也越多，將各個(gè)方向的投影數(shù)據(jù)等比特編碼會(huì)導(dǎo)致極大的量化誤差，現(xiàn)在的大多數(shù)方法都是采用的單比特量化，即將投影后的數(shù)據(jù)，每一位都與設(shè)定的閾值相比較，大于閾值量化為1，小于則量化為0。這樣不僅忽略了不同方差方向所攜帶信息的不同，也使得閾值兩邊極為接近的數(shù)據(jù)被量化成了不同的比特位。Weiss等[13]為了減少量化的損失，使用拉普拉斯特征函數(shù)公式在數(shù)據(jù)范圍大的方向分配更多的比特，但是這種方法依賴于數(shù)據(jù)在高維空間均勻分布的假設(shè)之上。Wang等[14]為了捕獲數(shù)據(jù)方差大的方向，對(duì)其目標(biāo)函數(shù)進(jìn)行了一系列的放松，雖然最后的實(shí)驗(yàn)效果有所改善，但是沒(méi)有擺脫單比特量化的局限性。

2 研究方法

在本文中，為了保證最后哈希編碼性能的優(yōu)越性，將從投影和量化兩個(gè)階段進(jìn)行研究。投影階段，通過(guò)分析，嵌入PCA算法；量化階段，結(jié)合投影方法的特性，提出了適應(yīng)性比特量化算法(ABQ)。具體來(lái)說(shuō)，即將PCA投影后的數(shù)據(jù)，根據(jù)閾值劃分量化空間，對(duì)不同空間的數(shù)據(jù)采取不同的量化方法，減少誤差的同時(shí)，保證量化速度。

2.1 PCA嵌入

根據(jù)Weiss等[13]，Wang等[14]以及香農(nóng)定理，要想得到緊湊且有效的哈希編碼，編碼后每個(gè)比特之間的方差應(yīng)該最大且編碼之間要互不相關(guān)。所以最大化如下目標(biāo)函數(shù)

(1)

W為投影矩陣，其維度與具體的量化函數(shù)有關(guān)，后面會(huì)做具體的分析，x={x1,x2,…,xn} 為數(shù)據(jù)集，xi∈Rd， var(·) 表示一個(gè)向量或矩陣的方差，h(x) 表示數(shù)據(jù)集x對(duì)應(yīng)的哈希函數(shù)，q(v) 表示量化函數(shù)，hk(x)=q(xtk)，B是量化后編碼矩陣，B∈Rn×c。 由于式(1)的離散問(wèn)題和編碼之間正交的限制，我們將目標(biāo)函數(shù)進(jìn)行放松

(2)

X∈Rn×d是由xi組成的數(shù)據(jù)矩陣，式(2)所尋求的目標(biāo)和PCA正好是一致的，尋找協(xié)方差矩陣XTX的前k個(gè)最大的特征值對(duì)應(yīng)的特征向量所組成的投影矩陣W， 用于最大限度保留原始數(shù)據(jù)的整體相似性。W的維度或者說(shuō)k的大小與具體量化方法有關(guān)，后面會(huì)做相關(guān)的分析。

2.2 適應(yīng)性比特量化

針對(duì)單比特量化和雙比特量化(double-bit quantization，DBQ)在基于PCA哈希量化過(guò)程中的優(yōu)勢(shì)與缺陷，我們提出了ABQ。按照PCA的理論之一，其投影矩陣W是逐一選取方差最大的方向所組成的，方差大的方向上的投影所包含的信息量會(huì)更大，也就是說(shuō)，這一部分的信息會(huì)更加重要，應(yīng)該在量化的過(guò)程中體現(xiàn)這一重要特性，僅僅使用SBQ或者DBQ這樣等比特編碼方式是無(wú)法做到的。上一小節(jié)提到過(guò)W的維度或者說(shuō)特征向量k的個(gè)數(shù)是與量化函數(shù)和編碼長(zhǎng)度有關(guān)的。設(shè)編碼長(zhǎng)度為c，若采用SBQ，則k的大小等于c，因?yàn)橥队昂竺總€(gè)數(shù)據(jù)位量化為一個(gè)比特位，這樣SBQ最大程度的利用了投影矩陣，保留了更多的編碼信息，但缺點(diǎn)是量化誤差較大。采用DBQ則k等于c的一半，相比SBQ，DBQ只利用到投影矩陣的一半，加快了速度，但是同時(shí)也丟失了更多的編碼信息。本文提出的ABQ不僅速度上要快于SBQ，而且相比DBQ保留了更多的編碼信息。對(duì)于長(zhǎng)度為c的編碼，首先確定一個(gè)比例系數(shù)λ，依據(jù)λ去劃分待量化的數(shù)據(jù)域，對(duì)于原特征空間中投影后的新特征空間中的向量，認(rèn)為數(shù)據(jù)位的前λc位是比較重要的，每位量化為兩個(gè)比特，而數(shù)據(jù)位的后c-λc位相對(duì)來(lái)說(shuō)次要一些，每位量化為一個(gè)比特。

3 算法實(shí)現(xiàn)

本文算法大致分為兩步，投影與量化。投影階段運(yùn)用PCA，將數(shù)據(jù)矩陣X∈Rn×d映射到新的低維空間(這里假設(shè)數(shù)據(jù)矩陣是零中心化的)，得到降維矩陣Z∈Rn×k。 對(duì)于新的特征空間采用ABQ進(jìn)行量化。

投影階段之前已做了較為詳細(xì)的分析，不再重述，在量化階段，首先確定一個(gè)比例系數(shù)λ， 實(shí)驗(yàn)結(jié)果表明設(shè)置λ=0.75在不同位數(shù)的編碼上都能取得較好的效果，我們也會(huì)給出λ 取不同值情況下的實(shí)驗(yàn)對(duì)比效果。對(duì)于待量化的數(shù)據(jù)，單比特量化的部分，使用如下方法

(3)

對(duì)于雙比特量化的數(shù)據(jù)，我們采用一種動(dòng)態(tài)閾值劃分的方法，根據(jù)待量化的數(shù)據(jù)獲取一個(gè)下閾值a和上閾值b， 通過(guò)a和b將需要量化的數(shù)據(jù)劃分為3個(gè)子集S1={x|-∞

(4)

μi表示子集Si的均值。首先設(shè)置μ2為0，表示中間子集S2以0作為均值，那么式(4)轉(zhuǎn)化為

(5)

|Si| 表示相應(yīng)子集Si中元素的個(gè)數(shù)。可以看出，式(5)的第一部分為常量，則最終優(yōu)化目標(biāo)轉(zhuǎn)化為最大化如下目標(biāo)函數(shù)

(6)

通過(guò)式(6)學(xué)習(xí)到動(dòng)態(tài)閾值a和b， 將待量化的數(shù)據(jù)劃分為3個(gè)區(qū)域。采用如圖1(b)的方法進(jìn)行量化。結(jié)合單比特量化階段數(shù)據(jù)編碼的結(jié)果，組合成最終的編碼矩陣B=[b1,b2,…,bc]。 DBQ算法流程如下所示：

算法1：DBQ算法流程

輸入：數(shù)據(jù)集S；

輸出：閾值上限a， 閾值下限b；

(1)將數(shù)據(jù)劃分為3個(gè)子集：

S1={x|-∞

S2=?，

S3={x|0

(2)將S1和S3分別排序，設(shè)置max=0；

(3)判斷S1或者S3是否為空集，如果為空轉(zhuǎn)向步驟(4)，否則轉(zhuǎn)向步驟(8)；

(4)計(jì)算S2中的數(shù)據(jù)和，如果小于等于0，則把S3中最小的數(shù)移到S2中，反之則把S1中最大的數(shù)移到S2；

(5)根據(jù)式(6)計(jì)算F；

(6)比較F與max的大小，如果F大于max, 則把max更新為F， 設(shè)置a為當(dāng)前S2中的最小值，b為當(dāng)前S2中的最大值；

(7)回到步驟(3)；

(8)返回a和b。

圖1 (a)SBQ與(b)DBQ的量化效果

算法的全部流程如下所示：

算法2：PCA-ABQ算法流程

4．地勢(shì)高危，道路險(xiǎn)要。因王罕嶺山體三面騰空而起，而剩下的一面又是連接大湖山主峰，山勢(shì)坡度大，懸崖峭壁分布眾多，從而形成了古詩(shī)文所述的“高崖萬(wàn)沓，邃澗千回”“喬峰迥峭，擘漢分星”“其險(xiǎn)如崩，其聳如騰”和“白云生石壁”等自然特征。如人要上王罕嶺，必須沿騰空的山巖攀登，路途之艱險(xiǎn)就不難想象了。

輸入：訓(xùn)練集X∈Rn×d， 比例系數(shù)λ， 編碼位數(shù)c； 輸出：矩陣B∈Rn×c。

(1)通過(guò)式(2)計(jì)算出投影矩陣W；

(2)根據(jù)步驟(1)的結(jié)果將原數(shù)據(jù)進(jìn)行投影得到低維空間的數(shù)據(jù)，Z∈Rn×k；

(3)將Z按照λ， 劃分為兩個(gè)子矩陣，Z1和Z2， 對(duì)于Z1采用雙比特量化得到編碼矩陣B1， 對(duì)于Z2采用單比特量化得到編碼矩陣B2；

(4)組合B1和B2得到最終編碼矩陣B。

4 實(shí)驗(yàn)結(jié)果和分析

4.1 數(shù)據(jù)集

CIFAR-10：CIFAR-10數(shù)據(jù)集包括60 000張彩色的圖片，被劃分為10個(gè)圖像類(lèi)別，每張圖片包含32×32個(gè)像素點(diǎn)，實(shí)驗(yàn)中以512維的GIST描述子表示。

CALTECH256：CALTECH256數(shù)據(jù)集包含256種類(lèi)別的物體，大約30 607張圖像，每類(lèi)包含圖片最少80張，最多827張。每張圖片用一個(gè)2048維的特征向量表示。

4.2 實(shí)驗(yàn)對(duì)比方法

LSH(locality sensitive hashing)：數(shù)據(jù)獨(dú)立型的哈希算法，其哈希函數(shù)為隨機(jī)生成的線性函數(shù)。

SH(spectral hashing)：將圖像特征向量的編碼過(guò)程視為圖分割問(wèn)題，借助于對(duì)相似圖的拉普拉斯矩陣特征值和特征向量的分析對(duì)圖的分割問(wèn)題提供一個(gè)松弛解。

KLSH(kernelized locality sensitive hashing)：核局部敏感哈希，將目標(biāo)函數(shù)映射到核空間。

DSH(deep supervised hashing)[16]：針對(duì)單純地使用隨機(jī)投影帶來(lái)的較大誤差，通過(guò)分析數(shù)據(jù)的幾何結(jié)構(gòu)，選擇與原始數(shù)據(jù)分布最相似的哈希函數(shù)。

SPH(spherical Hashing)[17]：使用基于超球面的哈希函數(shù)將數(shù)據(jù)點(diǎn)映射成二進(jìn)制向量。

4.3 評(píng)價(jià)指標(biāo)

MAP(mean average precision)：檢索得到的所有訓(xùn)練樣本的平均準(zhǔn)確率，被廣泛地應(yīng)用在哈希算法性能的評(píng)判中。

Precision-Recall：Precision即查準(zhǔn)率，Recall為查全率，前者是指檢出的相關(guān)目標(biāo)數(shù)占檢出總數(shù)的百分比，反映了檢索的準(zhǔn)確性；后者指檢索的相關(guān)目標(biāo)數(shù)占系統(tǒng)中相關(guān)目標(biāo)總數(shù)的百分比，反映檢索的全面性。通常是希望檢索結(jié)果的查準(zhǔn)率越高越好，同時(shí)查全率也越高越好，但實(shí)際上這兩個(gè)指標(biāo)是負(fù)相關(guān)的關(guān)系。在信息檢索中常常使用Precision-Recall曲線來(lái)評(píng)判檢索性能，其曲線高低和檢索效果是呈現(xiàn)正相關(guān)關(guān)系的。

4.4 性能分析

實(shí)驗(yàn)分別在兩個(gè)數(shù)據(jù)集上進(jìn)行，每個(gè)數(shù)據(jù)集隨機(jī)取1000個(gè)樣本作為測(cè)試數(shù)據(jù)集，剩余的樣本作為訓(xùn)練數(shù)據(jù)集。為了保證實(shí)驗(yàn)效果的公平和準(zhǔn)確，我們?cè)诿糠N方法上循環(huán)10次以獲取最終的實(shí)驗(yàn)結(jié)果。并以圖表的形式展現(xiàn)。表1展現(xiàn)的是λ 設(shè)置不同值時(shí)，在CIFAR-10數(shù)據(jù)集和CALTECH256數(shù)據(jù)集上MAP值。值得說(shuō)明的是λ=0時(shí)對(duì)應(yīng)為SBQ，λ=1時(shí)對(duì)應(yīng)DBQ。從實(shí)驗(yàn)的結(jié)果可以看到λ=0.75時(shí)，在兩個(gè)數(shù)據(jù)集上的檢索效果基本上都是最好的，如在CALTECH256數(shù)據(jù)集上，相比SBQ其MAP值平均提高了12%，比DBQ提高了6%，這是因?yàn)榇藭r(shí)不但很好地減少了量化誤差，也盡可能多地保留了投影信息，這也可以說(shuō)明量化階段對(duì)于編碼性能的重要性。其中CALTECH256上的MAP值在整體上要高于CIFRA-10，是因?yàn)闃颖咎卣魈崛》椒ú煌木壒?，本文研究的重點(diǎn)不在于此，故不做贅述，但這并不影響對(duì)實(shí)驗(yàn)效果的分析與比較。圖2和圖3對(duì)應(yīng)了不同哈希算法兩個(gè)數(shù)據(jù)集上的PR曲線,我們提出的PCA-ABQ在不同位數(shù)上的編碼效果均要優(yōu)于現(xiàn)有流行的哈希算法?？梢钥吹剑琍CA-SBQ方法在整體上的編碼效果是比較差的，因?yàn)榱炕鶐?lái)的誤差太大，雖然保留了較多的投影信息，但是量化的誤差也較大，PCA-DBQ的檢索效果整體上則要優(yōu)于PCA-SBQ，因?yàn)闇p小了量化帶來(lái)的誤差，而PCA-ABQ充分利用了基于PCA哈希的特性，在減少量化誤差，與保留投影信息之間尋找到一個(gè)平衡點(diǎn)，取得了最好的檢索效果。相較于隨機(jī)投影的哈希算法，PCA-ABQ無(wú)論是在低位和高位編碼上都能取得較好的檢索效果，而基于隨機(jī)投影的算法，在低位編碼上的性能是比較差的，因?yàn)槠涔：瘮?shù)的碰撞幾率比較大，只有在編碼位數(shù)比較高的情況下，才能達(dá)到較好的檢索效果。

表1 λ取值不同時(shí)在兩個(gè)數(shù)據(jù)集上的MAP值

圖2 不同哈希算法在CIFAR-10數(shù)據(jù)集上的precision-recall曲線

圖3 不同哈希算法在Caltech256數(shù)據(jù)集上的precision-recall曲線

5 結(jié)束語(yǔ)

本文基于PCA哈希的相關(guān)理論，提出了一種高效的哈希算法——PCA-ABQ。對(duì)于圖像哈希的兩個(gè)階段，投影與量化，投影階段我們采用現(xiàn)在流行的降維方法PCA將原特征空間的數(shù)據(jù)映射到新的子空間。量化階段，針對(duì)PCA的特性，采用一種分段量化的思想，通過(guò)實(shí)驗(yàn)來(lái)確定最佳的比例系數(shù)。實(shí)驗(yàn)中，我們?cè)诓煌瑪?shù)據(jù)集，不同評(píng)價(jià)指標(biāo)上與現(xiàn)在主流的圖像哈希算法進(jìn)行了對(duì)比，驗(yàn)證了我們算法的優(yōu)越性。但是仍然有值得改進(jìn)的地方，在投影階段，是基于PCA構(gòu)造的投影函數(shù)，使得訓(xùn)練的時(shí)間比較長(zhǎng)，量化階段是建立在PCA降維的基礎(chǔ)之上的，有一定的局限性。在今后的工作中，我們將進(jìn)一步研究如何降低投影階段的時(shí)間復(fù)雜度，如何把這種分段量化的思想應(yīng)用到其它的哈希算法之中。