劉 翔 宇

(北京大學(xué)軟件與微電子學(xué)院 北京 116024)

0 引 言

基于內(nèi)容的圖像檢索技術(shù)[1]CBIR突破了傳統(tǒng)基于文本的圖像檢索TBIR所造成的工作量大量性和主觀注釋信息不穩(wěn)定性的瓶頸，大大提高了圖像資源的利用率，為使用者提供了全新的體驗。基于內(nèi)容的圖像檢索技術(shù)這一概念于1992年由T.Kato提出[15]。他在論文中構(gòu)建了一個基于色彩與形狀的圖像數(shù)據(jù)庫，并提供了一定的檢索功能進(jìn)行實驗。近似圖像被定義為對于同一物體或場景，在不同的拍攝情況(遮擋，位移，光線變化，背景，色差)下獲取的圖像，是CBIR重要檢索對象之一。根據(jù)文獻(xiàn)[16]可知，互聯(lián)網(wǎng)20億幅圖像中，有22%存在近似圖像，而且8%的圖像擁有超過10幅近似圖像。

而基于內(nèi)容的搜索引擎的出現(xiàn)以及查找具有版權(quán)問題的未授權(quán)圖像的需求和一些分析類的場景對近似圖像檢索的科研需求愈來愈高[14]。另外，近似圖像檢索技術(shù)對于傳統(tǒng)的基于內(nèi)容檢索技術(shù)同樣大有裨益。例如，近似圖像是基于倒數(shù)最近鄰[17]或數(shù)據(jù)庫擴(kuò)充技術(shù)[12]的搜索技術(shù)的先決條件。

近似圖像檢索的整個過程大致分為如下幾個步驟：

(1) 對圖像集進(jìn)行特征提取，如使用SIFT算法[2]等。

(2) 對提取的特征點進(jìn)行聚類，如K-means[3]等方法。

(3) 生成Bag-of-Words模型描述圖像信息。

(4) 利用相關(guān)算法進(jìn)行圖像相關(guān)性的計算。

Min-Hash算法是一種經(jīng)典的算法，Chum等在2008年BMVC中將min-Hash應(yīng)用于近似圖像檢索中[16]。2013年由趙萬磊和Hervé Jégou等在ACMMM2013提出了基于min-Hash算法的改進(jìn)算法sim-min-Hash算法[4]，提高了圖像檢索的準(zhǔn)確性。

本文基于sim-min-Hash算法繼續(xù)進(jìn)行改進(jìn)，引用了分塊機(jī)制，提出了分塊sim-min-Hash算法。

1 min-Hash算法

1.1 Jaccard相似度

比較兩個集合相似度的時候常用到Jaccard系數(shù)[5]，即對于給定的集合A和集合B，A、B中公有的元素個數(shù)占A和B的總元素個數(shù)的比重：

1.2 min-Hash算法

min-Hash算法是加速計算Jaccard相似度的一個很好的算法。盡管對于準(zhǔn)確性上，min-Hash算法有一定的損失，但是min-Hash這種算法卻可以大大地減少計算Jaccard相似度所耗費的時間[6]。

min-Hash的原理為，假設(shè)存在兩個集合A、B,將集合A、B中的元素經(jīng)過哈希函數(shù)轉(zhuǎn)換后，如果其中具有最小哈希值的元素如果既在A∪B中也在A∩B中，那么hmin(A)=hmin(B)，集合A和B的相似度就可以表示為集合A、B的最小哈希值相等的概率，即：A和B的相似度就可以表示為集合A、B的最小哈希值相等的概率，即：

J(A,B)=Pr[hmin(A)=hmin(B)]

而min-Hash算法應(yīng)用在近似圖像檢索中，就是先對對圖像進(jìn)行特征提取，聚類，生成詞袋模型后，再進(jìn)行min-Hash的計算，來計算出圖像的相似程度。

在工程實踐中，常常引入sketch作為新的計算對象來進(jìn)行計算，起到加速計算的目的。

如果把幾個哈希值合而為一，再進(jìn)行運算，那么就會起到加速的作用。我們把幾個哈希值合而為一的產(chǎn)物就是sketch。

2 sim-min-Hash算法

min-Hash算法的核心思想就是將所提取的圖像的特征值(一般用Bag-of-Words來表示)進(jìn)行哈希變換，然后通過對于通過哈希變換所得到的一系列值進(jìn)行相關(guān)處理，來比較圖像的相似性。

這種將圖像提取特征，將圖像特征進(jìn)行再變換，然后再進(jìn)行比較的方法，由于在提取圖像特征值的過程中已經(jīng)損耗了一定的對于圖像特征的表示的信息量，而且再度進(jìn)行哈希變換過程中，又不可避免地?fù)p耗掉了一定的信息量，對于圖像比較相似度的精確度，肯定會有一定的影響。

而在min-Hash算法運算的過程中，最關(guān)鍵的一步就是只是找到最小哈希值進(jìn)行Jaccard距離的計算。那么如果對于后續(xù)的過程中，我們不使用哈希值來運算，而是使用進(jìn)行哈希變換前的原值進(jìn)行運算，而哈希變換只是提供了尋找能得到最小的幾個哈希值的原值的手段。由于原值包含的信息量和進(jìn)行哈希變換后所得到的信息量相比更大，更能代表圖像的信息，如果用這種方法，精確度可以得到提升，但運算的時間復(fù)雜度卻并沒有增加。

基于這種思想，sim-min-Hash算法應(yīng)運而生。簡單來說就是在min-Hash算法的具體操作中用原值代替了哈希值來組成sketch來進(jìn)行運算。

3 分塊sim-min-Hash算法

3.1 分塊sim-min-Hash的算法思想原理

根據(jù)對于大量近似圖像的觀察，近似圖像中的近似部分往往都具有一定的集中性，相似部分大多只是分布于圖像的某一區(qū)域，而不是散布在整幅圖像中，或者是占據(jù)整幅圖像。

由此，發(fā)現(xiàn)如果對圖像進(jìn)行分塊化處理(圖1(a))，則可大大降低特征點被sim-min-Hash的次數(shù)，從而提高算法效率。而且，分塊還可以將圖像網(wǎng)格化，通過查找相似網(wǎng)格可以實現(xiàn)對近似目標(biāo)的定位，大大增強(qiáng)了檢索的應(yīng)用范圍。

圖1 分塊sim-min-Hash算法原理

基于這種思想，提出了分塊sim-min-Hash(Partition sim-min-Hash，PsmH)這種新型的算法( 當(dāng)然也可以對min-Hash進(jìn)行分塊處理，但處理的效果顯然不如對于sim-min-Hash算法進(jìn)行分塊處理，因為sim-min-Hash算法本身就已經(jīng)是對min-Hash算法的一種優(yōu)化)。但是，由于分塊可能會將近似區(qū)域失去完整性(圖1(b))，因此采用了塊重疊技術(shù)來提高近似部分被分塊完整覆蓋的概率，并由此提高了檢索的準(zhǔn)確性，如圖1(c)所示。塊重疊技術(shù)可以將圖像分為許多小的網(wǎng)格，然后通過合并相似的網(wǎng)格作為同一分塊來達(dá)到分塊完整覆蓋近似部分的目的。

實驗結(jié)果證明，PsmH在查準(zhǔn)率、查全率和速度方面都大大強(qiáng)于min-Hash以及sim-min-Hash。并且PsmH更加容易實現(xiàn)，只要在sim-min-Hash算法的基礎(chǔ)上，增加分塊大小和重疊門限兩個參數(shù)的設(shè)置即可。

3.2 PsmH算法來比較圖像相似性的實現(xiàn)過程

設(shè)一共有i幅圖像，首先將每幅圖像被分為p個相等的矩形區(qū)域(p1,p2,…,pp)，每個區(qū)域就被稱為一個分塊。然后，對每個分塊分別進(jìn)行提取SIFT描述子，并對所有SIFT描述子集合，進(jìn)行K-means聚類，而不是像sim-min-Hash一樣在整幅圖像中提取SIFT描述子。根據(jù)聚類結(jié)果，分別對每個分塊獨立生成Bag-of-Words模型。再對每個分塊獨立進(jìn)行sim-min-Hash，組成在sim-min-Hash下的sketch，將結(jié)果存入Hash表中。

然后分別比較不同圖像間不同分塊的沖突概率，如果大于某一設(shè)定的門限，則可判定這兩個分塊相似。最后通過比較不同圖像間擁有相似分塊的數(shù)目來判斷這些圖像的相似性。

3.3 塊重疊技術(shù)

要進(jìn)行分塊sim-min-Hash，第一步一定要進(jìn)行塊重疊的判定。

如果圖像I1中的兩個相鄰分塊p1、p2都與圖像I2中的分塊p3相似，即可認(rèn)為p1、p2共同描述了I2和p3中的特征。

但是，值得注意的是，由于此時是為了查出更多的相似塊，而不是對不同分塊進(jìn)行篩選，因此我們應(yīng)該設(shè)定新的較小的不同于T1的相似性門限T2，即T1

3.4 目標(biāo)定位技術(shù)

為了使待檢索目標(biāo)能夠被更準(zhǔn)確地識別，減少背景特征的干擾，因而需要保證定位環(huán)節(jié)在以確定的同類圖像間執(zhí)行。當(dāng)然，如果只有少量的干擾圖像，那么對結(jié)果也不會產(chǎn)生過大影響。

首先通過PsmH查找出相似的分塊，由于待檢索圖像都已確定屬于同一類，即包含同一類相似特征，因此待檢索特征的出現(xiàn)概率應(yīng)該最大，然后可以對輸入檢索圖像中相似塊的進(jìn)行出現(xiàn)概率排序來過濾出最需要的檢索目標(biāo)。

例如，在圖2(a)第一列中，只有含有星巴克商標(biāo)的分塊在不同圖像中多次近似出現(xiàn)，它的出現(xiàn)概率最大，因而可以將它篩選出來，如圖3(a)所示。當(dāng)然，背景特征由于具有多樣性也可能會產(chǎn)生很大的出現(xiàn)概率，進(jìn)而影響定位結(jié)果，如圖3(b)所示，但是這種影響可以通過多次運行來進(jìn)行消除。

(a) 自建庫 (b) 牛津建筑圖2 檢索出的近似圖像對

圖3 用PsmH方式定位結(jié)果

4 PsmH的優(yōu)勢分析

4.1 時間效率的優(yōu)勢分析

在討論時間效率上，首先我們要知道在算法的運行(尤其在工程實踐)中，時間都耗費在了什么地方：

運行時間主要分兩部分：(1) 生成sketch的時間，其中包括Hash方程建立時間和min-Hash值計算時間；(2) 其他前期操作的時間,如從磁盤讀取數(shù)據(jù)的時間、提取SIFT描述子的時間、K-means聚類的時間、Bag-of-Words(或Set-of-Words)模型生成的時間和建立Hash表的時間等等。

而在sim-min-Hash和PsmH兩種算法中，由于圖像總量和每幅圖像中提取的sketch數(shù)量相同，因此前期操作時間基本一致，所有主要時間差距主要體現(xiàn)在sketch的生成環(huán)節(jié)上。

由于PsmH只是選取了一部分分塊來進(jìn)行運算，在生成sketch的過程中，需要進(jìn)行操作的原始數(shù)據(jù)本身就少了，所以PsmH的時間效率顯而易見地更高。

4.2 查全率和查準(zhǔn)率的優(yōu)勢分析

下面將要分析分塊sim-min-Hash生成的sketch比min-Hash和sim-min-Hash具有更強(qiáng)的識別力的原因。并且通過分析真近似圖像對和偽近似圖像對的沖突概率，對查準(zhǔn)率(Precision)和查全率(Recall)進(jìn)行評估。

查全率主要由真近似圖像對的沖突概率體現(xiàn)，定義為返回值中的真近似圖像對的數(shù)量比上真近似圖像對的總數(shù)。查準(zhǔn)率和偽近似圖像對的沖突概率相關(guān)，但不相等，定義為返回值中的真近似圖像對的數(shù)量比上返回圖像對的總數(shù)量。

PsmH提高了真近似圖像對的沖突概率和降低偽近似圖像對的沖突概率，因而具有更高的查準(zhǔn)率和查全率。

首先，分析真近似圖像對的沖突概率。為了簡化分析過程，先不考慮塊重疊的情況。近似部分在分塊中的位置可以分為三種情況，如圖1所示。在分析中，假設(shè)所有特征點都均勻散布在整幅圖像中，并且同一幅圖像的每個分塊中含有等量的特征點(包括成對和不成對出現(xiàn)的背景特征)。

我們可以通過如下四種情況進(jìn)行比較分析：

情況1：近似特征全部集中在一個分塊中；

情況2：近似特征分布在不同分塊中；

情況3：近似特征只集中于一幅圖的一個分塊中，而分散在另一幅圖的所有分塊中；

情況4：偽近似圖像對的沖突概率假設(shè)在偽近似圖像對中，兩幅圖像的近似特征隨機(jī)分散在圖像中，而不是集中在特定分塊中。

通過實驗可以證明，無論這四種情況中的哪種情況出現(xiàn)，在查全率和查準(zhǔn)率方面，都是PsmH更具備優(yōu)勢。

5 實驗結(jié)果與分析

5.1 實驗數(shù)據(jù)

使用牛津建筑庫來進(jìn)行實驗，如圖4所示。牛津建筑庫中包含5 062幅從FLICKR下載的牛津地標(biāo)性建筑，圖像尺寸大約為1 000×1 000，對每幅圖像提取大約2 500個SIFT特征點，并使用K-means進(jìn)行1 000個中心的聚類。同樣由于數(shù)據(jù)庫過于龐大，無法對全部圖像進(jìn)行測試，因而隨機(jī)選取了其中的552幅圖像，并且將其分為14類進(jìn)行檢索。

圖4 牛津建筑庫

5.2 結(jié)果分析

依據(jù)經(jīng)驗，對牛津建筑庫中的圖像進(jìn)行了分塊數(shù)從16～81塊的測試，實驗結(jié)果證明，當(dāng)分塊數(shù)為25的時候，PsmH的效果最好，因為此時近似特征被單一分塊完整覆蓋的幾率較大，還可以減少背景元素的干擾，定位的效果也很好。依據(jù)不同的sketch數(shù)量，min-Hash的門限T會隨之變化，以突出近似部分的重要性。根據(jù)實驗數(shù)據(jù)，當(dāng)每個sketch中min-Hash數(shù)量k=2時，Hash在準(zhǔn)確度和速度上得到最佳均衡，因此在測試中，保持k=2不變，來考察sketch的數(shù)量n=200、500、1 000變化時，PsmH和sim-min-Hash相對于min-Hash在查準(zhǔn)率、查全率和速度上的提升。

在查全率方面，通過實驗，當(dāng)sketch數(shù)量n=200時，PsmH的查準(zhǔn)率為0.629 2，相對于min-Hash的0.554 6有13.5%的提升，但是仍落后于sim-min-Hash的0.823 4，如圖5所示。

(a) Recall (b)Precision圖5 自建庫在固定sketch數(shù)量下的運行結(jié)果(□代表min-Hash，△代表sim-min-Hash，◇代表PsmH)

當(dāng)n=500時，PsmH的查全率相對于n=200時自身有了35.6%的提高，達(dá)到了0.853 1，相對min-Hash提高了40.2%，而且超過了sim-min-Hash。sim-min-Hash雖然落后于PsmH，但相對于min-Hash仍有35%的提高。而min-Hash雖然也有一定提高，但是幅度大大小于PsmH。當(dāng)n=1 000時，PsmH在查全率的優(yōu)勢達(dá)到峰值，比同條件下min-Hash提高了60.9%，同時高出sim-min-Hash 20.6%。sim-min-Hash高于min-Hash 33.4%。

當(dāng)n=500時，PsmH的查準(zhǔn)率相對自身提升有了75%的大幅提升，超過同條件下min-Hash 60.9%，并且超過sim-min-Hash。此時，sim-min-Hash仍高出min-Hash 35.7%。當(dāng)n=1 000時，雖然min-Hash的查準(zhǔn)率有一定提升，但是仍落后于sim-min-Hash 20.8%，僅僅是PsmH的49%。

可以看出，n在200～1 000范圍內(nèi)，PsmH和sim-min-Hash在查準(zhǔn)率方面相對于min-Hash都有較大的提升。當(dāng)n比較小時，應(yīng)該選擇sim-min-Hash。而隨著n的增長，PsmH的優(yōu)勢迅速擴(kuò)大。主要是查準(zhǔn)率和偽近似圖像對的沖突概率相關(guān)，如前文分析的一樣，PsmH和sim-min-Hash都提高了真近似圖像對的沖突概率并降低了偽近似圖像的沖突概率，因而查準(zhǔn)率相對于min-Hash大大提高，與理論分析一致。

為了比較Psmh運算速度的優(yōu)越性，并且說明n值增加對速度的影響，專門從牛津建筑庫中選取了15幅圖并對其進(jìn)行中心數(shù)量為300的K-means聚類，然后進(jìn)行sketch生成速度測試。結(jié)果表明，如圖6所示，min-Hash與sim-min-Hash的速度基本相同。而當(dāng)n增加到5 000時，sim-min-Hash耗時131.276 468 s，而PsmH為2.577 719 s，僅為sim-min-Hash的1.96%。當(dāng)n進(jìn)一步增加到10 000時，PsmH耗時7.481 789 s，而sim-min-Hash為541.257 151 s，PsmH僅為sim-min-Hash的1.38%，速度提升72.6倍。因此可推斷，隨著n的增加，PsmH帶來的速度優(yōu)勢會越來越明顯。

圖6 當(dāng)n=5 000到n=10 000時，PsmH和sim-min-Hash、min-Hash速度對比(□代表mH，△代表sim-min-Hash，◇代表PsmH)

6 結(jié) 語

本文對min-Hash算法和sim-min-Hash算法進(jìn)行了改進(jìn)，提出了分塊sim-min-Hash(PsmH)算法，從而獲得了更高的查準(zhǔn)率和查全率。分塊sim-min-Hash利用了近似特征在近似圖像中區(qū)域性分布的特點，將圖像分塊化處理，對每一個分塊獨立進(jìn)行sim-min-Hash變換，進(jìn)而提高了真近似對的沖突概率，降低了偽近似對的沖突概率，在三種方法中擁有最高的查準(zhǔn)率和查全率。其中，在牛津庫的測試中，PsmH平均查準(zhǔn)率相對sim-min-Hash最大提升107%，而平均查全率最大提升57.4%。塊重疊技術(shù)的引進(jìn)使得分塊sim-min-Hash的效率得到了進(jìn)一步提高。而且分塊sim-min-Hash大大降低了所需Hash方程的數(shù)量和sketch生成的時間，當(dāng)sketch數(shù)量巨大時，速度提升效果明顯。