杜丙新

(安陽師范學(xué)院 傳媒學(xué)院，河南 安陽 455000)

圖像檢索研究綜述及系統(tǒng)實現(xiàn)

杜丙新

(安陽師范學(xué)院 傳媒學(xué)院，河南 安陽 455000)

摘要利用文獻可視化分析工具對圖像檢索研究現(xiàn)狀進行了綜述，同時設(shè)計了一種基于位置敏感哈希算法的圖像檢索系統(tǒng)。通過位置敏感哈希算法將圖像的特征向量映射到哈希桶中，從而有效地降低了計算復(fù)雜度并提高了圖像檢索的效率。實驗結(jié)果表明，文中設(shè)計的方法在檢索效率以及查全率-查準率兩個測度上均獲得了較好的性能。

關(guān)鍵詞位置敏感哈希；圖像檢索；圖像特征向量

目前，圖像檢索技術(shù)以使用圖像視覺特征信息從圖像數(shù)據(jù)庫中檢索相似圖像為主流技術(shù)形式，即通常所說的基于內(nèi)容的圖像檢索。該技術(shù)從上世紀90年代至今經(jīng)歷了20多年的發(fā)展，已經(jīng)取得了豐碩的研究成果。但該領(lǐng)域仍存在眾多有待進一步解決的問題，依然吸引了不同領(lǐng)域研究者的持續(xù)關(guān)注[1]。

事實上，20多年的研究已經(jīng)為人們帶來了一些實驗性的商用產(chǎn)品：如百度識圖、谷歌圖像搜索引擎等，然而由于用戶需求的多樣性和龐雜性以及基于內(nèi)容圖像檢索技術(shù)自身并不成熟，目前，正在使用的基于內(nèi)容圖像檢索系統(tǒng)的檢索結(jié)果并不能完全達到預(yù)期。同時，隨著Internet由IPv4協(xié)議向IPv6協(xié)議逐漸過渡、云計算服務(wù)的日趨成熟，在可預(yù)見的未來，Internet提供的網(wǎng)絡(luò)服務(wù)將具有更大帶寬和更強運算能力。因此，基于內(nèi)容的圖像檢索技術(shù)將有較大的應(yīng)用前景。

1研究現(xiàn)狀

1.1圖像檢索基本框架

如圖1所示，分別為帶有反饋機制和引入圖像語義信息的圖像檢索系統(tǒng)基本框圖。從框圖中可看出，基于內(nèi)容圖像檢索的系統(tǒng)主要由圖像視覺特征提取和表示、特征索引與相似性匹配、用戶相關(guān)反饋技術(shù)和語義標(biāo)注4個部分組成。因此，基于內(nèi)容圖像檢索技術(shù)的研究也基本圍繞這4方面展開。

圖1　圖像檢索系統(tǒng)基本框架示意圖

1.2知識圖譜的視角下的研究現(xiàn)狀

利用CiteSpaceII[2]進行引文分析，為縮小引文分析范圍，在WebofScience中，利用“ImageRetrieval”為關(guān)鍵詞搜索2007～2014年間發(fā)表的SCI索引論文，共搜到相關(guān)論文2 115篇。在CiteSpaceII中分別從科研機構(gòu)分布、學(xué)科分布、作者共被引、文獻共被引和科研領(lǐng)域關(guān)鍵詞共現(xiàn)這幾個角度對搜索的2 115篇SCI論文進行分析。

圖2分別從研究機構(gòu)和學(xué)科領(lǐng)域角度分析了文獻相關(guān)信息。從圖2(a)中可看出，在該領(lǐng)域較為活躍的科研機構(gòu)有中國科學(xué)院、哈爾濱工業(yè)大學(xué)、北京大學(xué)、香港科技大學(xué)、卡內(nèi)基-梅隆大學(xué)、微軟亞洲研究院等科研院所和高校。另外，從圖2(b)中可以看出，與圖像檢索研究相關(guān)的學(xué)科領(lǐng)域以計算機科學(xué)領(lǐng)域為主，涵蓋到工程、數(shù)學(xué)、信息科學(xué)、自動控制等領(lǐng)域。隨著圖像檢索技術(shù)逐漸趨于成熟，其可能的應(yīng)用領(lǐng)域?qū)⒃絹碓蕉?。同樣，圖像檢索技術(shù)的進步也需要不斷借鑒相關(guān)學(xué)科的科研成果。例如檢索系統(tǒng)的用戶界面設(shè)計和用戶反饋的設(shè)計可能會用到用戶行為分析和評價等管理科學(xué)方面知識，這一點在圖譜中亦有所呈現(xiàn)。

圖2　圖像檢索文獻的知識圖譜

為清晰描述目前CBIR領(lǐng)域的關(guān)鍵技術(shù)，利用知識圖譜方式對WebofScience中引文文獻進行分析，如圖3所示，除了圖像抽象表示和相似性判斷外，目前CBIR熱門的研究領(lǐng)域還有檢索系統(tǒng)的框架設(shè)計、圖像標(biāo)注、圖像分割、圖像分類、相關(guān)性反饋、檢索性能評價、支持向量機的應(yīng)用等。

圖3　CBIR領(lǐng)域關(guān)鍵詞共現(xiàn)圖譜

1.3基于內(nèi)容圖像檢索的關(guān)鍵技術(shù)

CBIR技術(shù)主要的研究內(nèi)容可以歸納為以下幾方面[3]：

(1)基于全局視覺特征的圖像檢索，主要是研究如何利用圖像全局特征來描述圖像的視覺特性，再根據(jù)圖像全局特征間的相似性進行匹配。其特點是全局特征的運算速度較快、實現(xiàn)簡單，然而不足之處是全局特征往往很難準確表示圖像的實際意義。因此單純依靠全局特征的方法在早期圖像檢索研究的文獻中較為多見，在較新的文獻中，全局方法通常和局部方法配合使用以期得到更好的檢索效果;

(2)基于區(qū)域視覺特征的圖像檢索，這種方法的主要思想是首先利用一定的準則對圖像進行區(qū)域分割，然后對分割后區(qū)域分別提取其相應(yīng)的視覺特性進行匹配。其特點是實現(xiàn)技術(shù)相對復(fù)雜，但由于其以若干區(qū)域信息表示一幅圖像，因此其特征描述往往更加精確，在圖像檢索時搜索效果相對較好;

(3)相關(guān)反饋機制[4]，如圖1(a)所示，為提高檢索的精準度，在一些實際檢索系統(tǒng)中，會引入用戶反饋機制，對檢索結(jié)果按照相關(guān)度排序，然后由用戶確定檢索結(jié)果與自己意圖的接近性。從而可減小底層特征和高級語義之間的差距。反饋機制與機器學(xué)習(xí)相關(guān)技術(shù)關(guān)聯(lián)，是目前圖像檢索研究的一個重要分支；

(4)基于內(nèi)容和語義信息檢索，基于內(nèi)容圖像檢索主要依靠圖像的底層視覺信息，而使用者檢索圖像時通常是建立在對圖像高層意義的理解上。圖像的底層特征與圖像的高層語義之間往往會存在差異。這種差異性被描述為“語義鴻溝”[5]。“語義鴻溝”的存在讓一些看似成熟的特征檢測和匹配技術(shù)在實際應(yīng)用中難以取得預(yù)期效果。針對這一問題，研究者開始嘗試在圖像檢索中引入圖像語義信息。到目前為止，“語義鴻溝”問題并未得到完美解決，該方向在未來一段時間內(nèi)依然值得不斷探索研究。

CBIR研究需要解決的核心問題有兩個，即圖像特征提取與表示和高維空間特征向量的快速比較[6]。基于圖像內(nèi)容信息提取的基本方法常用的有全局特征和局部特征。全局特征有顏色、紋理、形狀等基本特征的提取和特征生成；局部特征有SIFT、SURF等特征點檢測算法[7]。在實際檢索系統(tǒng)中，這些圖像內(nèi)容特征通常會綜合使用，而非單一使用某一種，這樣能進一步提升檢索的準確性。此外，特征表示出來后，在檢索階段需要由特征向量匹配的相應(yīng)算法。這些算法的核心是要解決高維空間向量快速匹配問題。針對這一問題，常用B樹、B+樹、K維分類樹和散列方法[8]?；跇湫徒Y(jié)構(gòu)的索引匹配可以在一定程度上提升檢索匹配的效率，但樹型結(jié)構(gòu)的快速匹配是以犧牲圖像檢索的準確度為代價的，因此，散列表索引匹配方式也成為一種高維空間匹配常用方法。本文的研究就是基于局部敏感哈希方法的一種圖像檢索的技術(shù)實現(xiàn)。

2本文系統(tǒng)實現(xiàn)的方法

2.1高維空間索引的研究

為圖像特征建立索引是提高圖像檢索效率的常用方法。特征檢測算法提取出的圖像特征描述子通常是幾十維甚至上百維的向量。傳統(tǒng)的低維空間比較方法無法直接用于高維數(shù)據(jù)空間。解決方法一般是采用基于數(shù)據(jù)分布、空間劃分或者是散列降維的方式來提高特征向量的比較速度。

一般來說，圖像特征向量的分布不是獨立的。利用數(shù)據(jù)分布劃分的方法對特征向量索引形成的數(shù)據(jù)密集區(qū)的點具有相似性，從而可將查詢范圍縮小到某個區(qū)域，達到加速檢索的目的。但是基于數(shù)據(jù)分布劃分會在不同的結(jié)點區(qū)域產(chǎn)生重疊現(xiàn)象。

基于空間劃分的方法認為在數(shù)據(jù)空間中相互接近的點在特征上具有相似性，采用某些固定范圍對數(shù)據(jù)空間劃分，使查詢范圍限定在包含與查詢點的同一空間的鄰域內(nèi)，會提高查找速度。如四元樹、AV-File、網(wǎng)格文件等。然而，基于空間劃分思想的算法存在的問題是該方法假設(shè)數(shù)據(jù)在空間上的分布是均勻的，使得在實際的檢索中難以取得理想的結(jié)果。

以上基于數(shù)據(jù)分布和空間劃分的索引方法都存在無法克服的缺陷。例如，當(dāng)特征向量維數(shù)超過一定值時，K-D樹搜索的效率甚至不如窮盡搜索的方法。如果特征向量的分布是均勻的，基于空間劃分的方法將能夠合理的將特征向量分布在不同的檢索路徑上，從而得到較為高效的檢索效率和準確的檢索結(jié)果，但是實際上，圖像特征向量之間的相關(guān)性會導(dǎo)致進行空間劃分時，某些節(jié)點數(shù)據(jù)較為集中，而某些節(jié)點沒有數(shù)據(jù)的情況，從而影響檢索效率，降低檢索的精度。

位置敏感哈希算法(LocalitySensitiveHashingAlgorithm，LSH)是常用的高維據(jù)索引方法之一。該算法核心思想是將高維空間中的元素視為點并賦以坐標(biāo)值。通過一族哈希函數(shù)將空間所有點映射到n個哈希表中。LSH不再使用空間劃分方法，利用哈希表的思路為特征建立索引：首先將特征向量投影到某個坐標(biāo)空間并賦以坐標(biāo)值；然后利用k個哈希函數(shù)對坐標(biāo)值進行哈希運算。兩個輸出相近哈希碼的高維數(shù)據(jù)點會被認為可能是近鄰而散列到同一個哈希桶中。

LSH索引在數(shù)據(jù)維數(shù)增加時依然能表現(xiàn)出較好的檢索性能，因此吸引了較多學(xué)者的關(guān)注。目前，LSH算法已經(jīng)逐漸應(yīng)用到圖像檢索系統(tǒng)。

2.2LSH算法的實現(xiàn)

與一般哈希函數(shù)不同的是位置敏感哈希函數(shù)的位置敏感性，即散列前的相似點經(jīng)過哈希之后，也能在一定程度上相似，并具有一定的概率保證。

這一特性可形式化定義：對于任意我q,p屬于S，若從集合S到U的函數(shù)族H={h1,h2,…,hn}對距離函數(shù)D(·)，滿足條件(1)若D(p,q)≤r則pro[h(p)=h(q)]≥p1;(2)若D(p,q)>r(1+ε)則pro[h(p)=h(q)]≤p2。則稱D(；)是位置敏感的。

圖4　位置敏感哈希運算示意圖

通過分析不難看出，位置敏感哈希算法將相似度較高的樣本映射到同一個哈希桶(Hash Bucket)中，通過增加存儲開銷來降低樣本的查找區(qū)間，如圖4所示。按圖5所示，位置敏感哈希算法的可進一步描述為：假定給定的數(shù)據(jù)點v和q屬于集合S，那么若從集合S到集合U的函數(shù)族H={h:S→U}對距離函數(shù)Dis(;)滿足條件：(1)當(dāng)條件Dis(v,q)≤r1滿足時，PrH[h(q)=h(v)]≥p1成立;(2)當(dāng)條件Dis(v,q)≤r2滿足時，PrH[h(q)=h(v)]≥p2成立。則認為函數(shù)族H={h:S→U}對函數(shù)Dis(;)是(r1,r2,p1,p2)敏感的。 并且只有條件p1>p2和p均都成立時，位置敏感哈希函數(shù)才有實際意義。

假定G表示哈希函數(shù)族，從其中隨機地抽取哈希函數(shù)集合g={h1,h2,…,hk}。數(shù)據(jù)點g(p)=[h1(p),…,hk(p)]可表示為g(p)=[h1(p),…,hk(p)]，接下來，把哈希函數(shù)集g(p)映射對應(yīng)到哈希表。論文使用下述函數(shù)進行圖像相似度的計算

(1)

其中，參數(shù)a是服從高斯分布的d維隨機變量，參數(shù)b是從數(shù)值區(qū)間[0,r]中的實數(shù)。 函數(shù)fab(V):Rd→N將d維向量V映射到整數(shù)空間。

在位置敏感哈希算法的基礎(chǔ)上，本文按如圖5所示算法進行圖像檢索。

圖5　本文方法流程示意圖

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

從圖像檢索時間和圖像檢索召回率兩個角度來衡量算法的有效性。在比較系統(tǒng)檢索運行時間時，將本文算法與基于Lucence方法的圖像索引檢索方法進行比較分析。Lucence作為開源的Java全文檢索平臺已經(jīng)在多個領(lǐng)域有所研究。

實驗在Core-i5 CPU和4 GB內(nèi)存的計算機上進行，如圖6所示，從索引和檢索時間來看，與Lucence檢索相比，論文采用LSH方法能有效提高對圖像數(shù)據(jù)庫和圖像檢索的時間。

圖6　圖像數(shù)據(jù)庫索引與圖像檢索時間對比圖

此外，為衡量算法檢索的準確性，文中從圖像檢索查準率和查全率兩方面來衡量LSH索引的檢索圖像準確率的性能。查準率是指查出圖像結(jié)果集中準確圖像所占的比率，即

(2)

而查全率是用來衡量檢索出的結(jié)果集中正確圖像數(shù)量與數(shù)據(jù)庫中實際正確匹配結(jié)果的比率，如式(3)所示

(3)

這兩個指標(biāo)實際上是互相影響的。從實驗驗證角度來看，提高查準率是以犧牲查全率為代價的，同樣在查全率提高的同時，錯誤檢索結(jié)果也會相應(yīng)增加，實際檢索中，要靠檢索閾值的調(diào)節(jié)來達到檢索需求。

如圖7所示，直觀來看，對于不同類型的圖像，本文設(shè)計的方法得到的檢索準確率并不完全相同，但能保證基本檢索結(jié)果的準確性。

圖7　不同類型圖像的檢索結(jié)果示意圖

從實際系統(tǒng)分析來看，查準率和查全率的比較關(guān)系如圖8所示。本文選用的LSH索引方法與Lucence索引方法有比較接近的圖像檢索準確率。

圖8　兩種方法的查準率和查全率比較關(guān)系圖

4結(jié)束語

設(shè)計了一種基于位置敏感哈希算法的快速圖像檢索技術(shù)。該技術(shù)利用將圖像高維特征映射到不同哈希桶中的方式實現(xiàn)降維處理，從而能在一定程度上提高圖像索引和檢索的效率。實驗結(jié)果表明，利用位置敏感哈希的降維方法在保證查全率-查準率前提下，能較好提高圖像檢索的速度。本文研究僅限于單機版的個人圖像數(shù)據(jù)庫中，因此所得結(jié)論的全面性還有待進一步論證。后續(xù)研究中應(yīng)考慮采用多種形式圖像特征表示以及在大數(shù)據(jù)環(huán)境下進行系統(tǒng)實測，以獲取更為科學(xué)、全面的研究數(shù)據(jù)。

參考文獻

[1]Ritendra Datta,Joshi Dhiraj.Image retrieval: ideas, influences, and trends of the new age[J]. ACM Computing Surveys,2008,40(2):1-60.

[2]Chen C. Cite space II:detecting and visualizing emerging trends and transient patterns in scientific literature[J]. Journal of the American Society for Information Science and Technology,2006,57(3):359-377.

[3]齊恒.基于內(nèi)容圖像檢索的關(guān)鍵技術(shù)研究[D].大連:大連理工大學(xué),2012.

[4]Yang C,Dong M,Fotouhi F. Semantic feedback for interactive image retrieval[C].MA,USA:In Proceedings of the ACM International Conference on Multimedia,2005.

[5]Arnold W,Worring M,Santini S,et al.Content-based image retrieval at the end of the early years[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(12):3845-3849.

[6]許銳.基于顏色和紋理特征的圖像檢索技術(shù)研究[D].長沙:中南大學(xué),2008.

[7]Jia Li,James Z Wang.Automatic linguistic indexing of pictures by a statistical modeling approach[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,25(9):1075-1088.

[8]劉婉,徐望明,石漢路.基于高維局部特征和 LSH 索引的圖像檢索技術(shù)[J].電子設(shè)計工程,2011,19(20):110-112.

Survey and System Implementation of Image Retrieval

DUBingxin

(SchoolofMediaandCommunications,AnyangNormalUniversity,Anyang455000,China)

AbstractThe paper summarizes the research status of image retrieval based on the visual analysis tools, and an image retrieval system is implemented based on Locality Sensitive Hashing. Image feature vectors are mapped to hash bucket by LSH method, thereby, the method effectively reducing the computational complexity and improves the efficiency of the image retrieval. Experimental results show that, the method in the paper are both obtain better performance on retrieval efficiency and recall -precision of two measures.

Keywordslocality sensitive hashing；image retrieval；image feature vector

收稿日期:2015-11-07

基金項目:河南省科技廳研究基金資助項目(112102210373)

作者簡介:杜丙新(1982-)，男，碩士研究生。研究方向：計算機圖形圖像及機器視覺。

doi:10.16180/j.cnki.issn1007-7820.2016.06.053

中圖分類號TP391.41

文獻標(biāo)識碼A

文章編號1007-7820(2016)06-185-05