• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

      2019-07-15 11:18:44
      關(guān)鍵詞:查全率查準(zhǔn)率哈希

      劉 翔 宇

      (北京大學(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í),速度提升效果明顯。

      猜你喜歡
      查全率查準(zhǔn)率哈希
      海量圖書館檔案信息的快速檢索方法
      基于數(shù)據(jù)挖掘技術(shù)的網(wǎng)絡(luò)信息過(guò)濾系統(tǒng)設(shè)計(jì)
      基于詞嵌入語(yǔ)義的精準(zhǔn)檢索式構(gòu)建方法
      大數(shù)據(jù)環(huán)境下的文本信息挖掘方法
      基于深度特征分析的雙線性圖像相似度匹配算法
      基于OpenCV與均值哈希算法的人臉相似識(shí)別系統(tǒng)
      基于維度分解的哈希多維快速流分類算法
      基于同態(tài)哈希函數(shù)的云數(shù)據(jù)完整性驗(yàn)證算法
      一種基于Bigram二級(jí)哈希的中文索引結(jié)構(gòu)
      中文分詞技術(shù)對(duì)中文搜索引擎的查準(zhǔn)率及查全率的影響
      始兴县| 丰城市| 丰都县| 思南县| 东丰县| 敦化市| 衡东县| 贵定县| 新河县| 磴口县| 牡丹江市| 永嘉县| 卢龙县| 永泰县| 长泰县| 沂南县| 邵阳县| 利川市| 桐城市| 永定县| 兴城市| 澜沧| 张家口市| 潼关县| 和平县| 于都县| 通渭县| 北票市| 汝城县| 山阳县| 商城县| 崇州市| 专栏| 会同县| 八宿县| 内黄县| 辛集市| 忻州市| 乐昌市| 沈丘县| 博乐市|