基于分塊sim-min-Hash的近似圖像檢索

劉 翔 宇

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

0 引 言

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

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

近似圖像檢索的整個(gè)過(guò)程大致分為如下幾個(gè)步驟：

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

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

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

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

Min-Hash算法是一種經(jīng)典的算法，Chum等在2008年BMVC中將min-Hash應(yīng)用于近似圖像檢索中[16]。2013年由趙萬(wàn)磊和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相似度

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

1.2 min-Hash算法

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

min-Hash的原理為，假設(shè)存在兩個(gè)集合A、B,將集合A、B中的元素經(jīng)過(guò)哈希函數(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)用在近似圖像檢索中，就是先對(duì)對(duì)圖像進(jìn)行特征提取，聚類，生成詞袋模型后，再進(jìn)行min-Hash的計(jì)算，來(lái)計(jì)算出圖像的相似程度。

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

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

2 sim-min-Hash算法

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

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

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

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

3 分塊sim-min-Hash算法

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

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

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

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

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

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

3.2 PsmH算法來(lái)比較圖像相似性的實(shí)現(xiàn)過(guò)程

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

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

3.3 塊重疊技術(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 實(shí)驗(yàn)結(jié)果與分析

5.1 實(shí)驗(yàn)數(shù)據(jù)

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

圖4 牛津建筑庫(kù)

5.2 結(jié)果分析

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

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

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

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

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

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

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

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

6 結(jié) 語(yǔ)

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