汪宇雷 畢樹(shù)生 孫明磊 蔡月日

(北京航空航天大學(xué) 機(jī)械工程及自動(dòng)化學(xué)院，北京100191)

圖像作為最基本、最重要的多媒體信息形式之一，憑借其表象直觀、內(nèi)容豐富的優(yōu)勢(shì)，已廣泛地應(yīng)用在眾多領(lǐng)域，而快速準(zhǔn)確搜索到所需相關(guān)圖像已成為國(guó)內(nèi)外信息檢索領(lǐng)域的研究熱點(diǎn).

目前，已經(jīng)存在的圖像檢索方法主要分為基于文本的方法和基于內(nèi)容的方法［1］.基于文本的方法首先對(duì)圖像進(jìn)行文本標(biāo)注，然后將文本數(shù)據(jù)存入數(shù)據(jù)庫(kù)，用戶檢索時(shí)是通過(guò)查詢數(shù)據(jù)庫(kù)中存儲(chǔ)的文本信息來(lái)實(shí)現(xiàn)圖像檢索.基于內(nèi)容的方法又可分為基于顏色［2］、紋理［3］、形狀［4］、空間［5］等特征的方法，雖然提取特征不一樣，但基本過(guò)程類似，均通過(guò)比較圖像間的相同特征來(lái)判斷是否相似，從而給出符合要求的搜索結(jié)果.由于局部視覺(jué)特征擁有優(yōu)秀的緊湊性與魯棒性，更多的系統(tǒng)采用基于興趣點(diǎn)的局部特征進(jìn)行圖像檢索［6-11］.文獻(xiàn)［7-8］中分別使用近似K-Means算法和對(duì)局部空間進(jìn)行網(wǎng)格結(jié)構(gòu)均分得到視覺(jué)詞匯表，但這兩種做法會(huì)忽略圖像的語(yǔ)義部分.文獻(xiàn)［9］提出使用隱馬爾可夫模型(HMM，Hidden Markov Model)將圖像語(yǔ)義和視覺(jué)特征整合以構(gòu)建詞匯表.文獻(xiàn)［10］提出結(jié)合各類局部特征的顏色矩陣和Gabor特征進(jìn)行檢索.文獻(xiàn)［11］提出通過(guò)比較各興趣點(diǎn)局部澤尼克矩的歐氏距離來(lái)提取最優(yōu)匹配點(diǎn)，然后以興趣點(diǎn)的空間離散度計(jì)算圖像匹配性.

以上這些研究成果更多地考慮在匹配過(guò)程中采用不同的算法比較興趣點(diǎn)特征以提高檢索速度和準(zhǔn)確性，但在檢索過(guò)程開(kāi)始前，剔除大部分不相干圖片也可以加快檢索進(jìn)程.針對(duì)這一點(diǎn)，本文在考慮圖像語(yǔ)義的基礎(chǔ)上提出一種新的圖像檢索方法:采用K-Means算法生成視覺(jué)詞袋模型后利用潛在狄利克雷分布(LDA，Latent Dirichlet Allocation)算法將圖片庫(kù)進(jìn)行預(yù)分類，用戶提交待檢索的圖片后，先將其歸類，最后在此類下采用特征點(diǎn)匹配方法檢索到合適的圖片.算法創(chuàng)新之處有2點(diǎn):

1)通過(guò)LDA算法分析圖像語(yǔ)義，將圖庫(kù)中相關(guān)性較大的圖片自動(dòng)歸為一類，而不引入人為因素;

2)待檢索的圖片提取興趣點(diǎn)特征后，經(jīng)過(guò)計(jì)算可被歸為合適的類別，后再進(jìn)行匹配比對(duì)，由于不需要與所有圖片進(jìn)行對(duì)比，一方面減少檢索時(shí)間，另一方面檢索準(zhǔn)確率和檢索召回率都可提高.此算法可用于圖像內(nèi)容特征區(qū)別較明顯的圖像庫(kù)檢索工作.

1 基本框架

本文所提出的檢索算法實(shí)現(xiàn)過(guò)程主要有兩個(gè)階段:

1)預(yù)備階段中系統(tǒng)首先通過(guò)尺度不變特征變換(SIFT，Scale Invariant Feature Transform)特征提取算法提取圖片庫(kù)中所有圖片的特征，然后采用K-Means聚類算法將所有特征聚類生成基本詞庫(kù)，最后采用LDA主體模型算法結(jié)合基本詞庫(kù)將圖片庫(kù)中圖片按照各自本身內(nèi)容進(jìn)行分類，同時(shí)得到概率分配參數(shù)表;

2)實(shí)現(xiàn)檢索階段中，用戶向系統(tǒng)提交待檢索圖片(用S表示)，系統(tǒng)首先提取S圖片特征，然后利用已生成的基本詞庫(kù)將S圖片特征歸類，用概率分配參數(shù)表歸類S圖片，最后在該類下采用SIFT特征點(diǎn)匹配算法尋找與S圖片的最相似圖片.

圖1為整個(gè)檢索算法的運(yùn)行流程.

圖1 圖像檢索流程Fig.1 Process of image retrieval

值得注意的是預(yù)備階段可在搜索階段之前進(jìn)行，故預(yù)備工作階段的運(yùn)行時(shí)間與用戶的訪問(wèn)時(shí)間無(wú)關(guān).

2 預(yù)備工作

執(zhí)行檢索功能前，系統(tǒng)需要一定的預(yù)備工作，產(chǎn)生必要的基礎(chǔ)文件——基本詞庫(kù)、概率分配參數(shù)表和已經(jīng)分類的圖片庫(kù).此3份文件通過(guò)特征庫(kù)建立、基本詞庫(kù)建立和圖片分類3個(gè)步驟生成.

2.1 特征庫(kù)建立

由于本文實(shí)現(xiàn)的檢索功能是基于本地計(jì)算機(jī)的，故需準(zhǔn)備一些圖片作為將來(lái)的搜索對(duì)象.這些圖片構(gòu)成圖片庫(kù)P，用pm表示其中任意一張圖片，D表示圖片總量，則圖片庫(kù)集合為

將來(lái)的搜索工作便是基于此庫(kù)尋找與用戶提交的圖片相匹配的圖片.

建立特征庫(kù)即是提取圖片庫(kù)中所有圖片的有效特征.本文選擇的是基于興趣點(diǎn)特征的SIFT［12］特征檢測(cè)技術(shù).建立具體實(shí)現(xiàn)過(guò)程是通過(guò)SIFT特征檢測(cè)算法依次讀入圖片庫(kù)P中所有圖片并生成特征庫(kù)Q.圖片pm對(duì)應(yīng)生成特征集fm，則特征庫(kù)集合為

每個(gè)特征集文件是對(duì)應(yīng)單個(gè)圖像文件的特征向量集:

其中Nm表示第m個(gè)特征集文件包含Nm個(gè)特征向量，則特征庫(kù)中特征向量總數(shù):

由于每張圖片內(nèi)容不一樣，一般每個(gè)特征向量集中所包含的特征向量總數(shù)和具體值都不一樣.

2.2 基本詞庫(kù)建立

特征庫(kù)可視為特征向量的集合，這些特征向量集對(duì)應(yīng)圖片的基本信息，為了簡(jiǎn)化生成的特征庫(kù)，需要將這些特征向量進(jìn)行歸類.由于這些特征向量是基于歐式空間的128維向量，K-Means算法作為一種基于距離和劃分的聚類算法，可以在歐式空間中對(duì)這些特征向量進(jìn)行歸類［13］.

特征庫(kù)中所有特征向量經(jīng)過(guò)K-Means算法聚類后生成基本詞庫(kù)H，用wk表示其中任意一個(gè)基本單詞，V表示基本單詞總數(shù)，則基本詞庫(kù)集合表示為

由此整個(gè)特征庫(kù)分成了V簇，而每個(gè)基本單詞實(shí)際上也是基于歐式空間的128維向量.由于所有屬于第k簇的特征向量可被基本單詞wk所替代，故第m特征集可轉(zhuǎn)化為

其中Lm，g表示第g個(gè)基本單詞在第m個(gè)特征文件中所出現(xiàn)的頻次，且按照K-Means算法的要求，V應(yīng)小于E，即基本單詞總數(shù)小于特征向量總數(shù)，故整個(gè)特征庫(kù)得到了簡(jiǎn)化.雖然此步驟損失了圖像存儲(chǔ)精度，但它是圖片分類的決定性步驟.

經(jīng)過(guò)特征庫(kù)建立和基本詞庫(kù)建立兩步驟之后，圖片庫(kù)P轉(zhuǎn)化對(duì)應(yīng)的單詞組合文本庫(kù)T，其集合為

每個(gè)文本文件dm所含信息為每個(gè)單詞在對(duì)應(yīng)特征向量集fm出現(xiàn)的頻次，即

由于單詞組合文本替代了難以描述化的圖片，系統(tǒng)便可依據(jù)此文本庫(kù)將對(duì)應(yīng)的圖片識(shí)別分類.

2.3 圖片分類

提高圖片檢索效率最關(guān)鍵步驟在于圖片分類.由于圖片主體往往存在一個(gè)主題，比如天空、建筑、道路或者商場(chǎng)等等，而主題模型理論能夠發(fā)現(xiàn)文本中使用詞語(yǔ)的規(guī)律，并且把規(guī)律相似的文本聯(lián)系到一起［14］，故本文采用已經(jīng)應(yīng)用到郵件、科技文獻(xiàn)摘要、新聞稿等各類文本上的主題模型理論將圖片按照其潛在性的主題進(jìn)行分類.本文采用主題模型理論中的LDA模型［15］對(duì)圖片庫(kù)進(jìn)行無(wú)主題分類.

LDA為3層貝葉斯模型，由單詞(word)、文本(doc)、主題(topic)組成，其模型結(jié)構(gòu)如圖2所示.

圖2 LDA主題模型Fig.2 LDA topic model

將LDA模型應(yīng)用于本算法提出的單詞組合文本庫(kù)T，其生成過(guò)程如下:

1)設(shè)定圖片庫(kù)主題總數(shù)F，參數(shù)α和β;

2)對(duì)于每個(gè)主題，從參數(shù)為β的Dirichlet先驗(yàn)分布中抽樣，并作為1個(gè)多項(xiàng)分布φ(z)，此步驟重復(fù)F次;

3)對(duì)于每個(gè)特征集合文本，從參數(shù)為α的Dirichlet先驗(yàn)分布中抽樣，并作為1個(gè)多項(xiàng)分布θ(m)，為了生成文本dm中每個(gè)單詞wmi，需從多項(xiàng)分布中抽取一個(gè)主題，然后根據(jù)此主題對(duì)應(yīng)的多項(xiàng)分布抽取一個(gè)單詞，重復(fù)Nm次后便生成文本dm，由于每個(gè)文本沒(méi)有相互關(guān)系，只需重復(fù)M次，便可生成整個(gè)文本庫(kù)T.

LDA主題模型的目標(biāo)是根據(jù)已有的單詞組合文本庫(kù)(每個(gè)word是可觀察到的)重建θ(m)和φzmi(第m個(gè)文本中第i個(gè)單詞所對(duì)應(yīng)的topicwords多項(xiàng)式分布).經(jīng)推導(dǎo)可得到第m篇文章中第i個(gè)單詞生成第z個(gè)主題的概率，如式(1)所示.

LDA模型迭代計(jì)算成功后，每個(gè)單詞的主題即得到明確分配，故可得到 θmz和 φzv矩陣:θmz表示文本m生成主題z的概率，即條件概率m)，其符合多項(xiàng)分布:

nm，z表示文本m與主題z的所有共現(xiàn)次數(shù);φzv表示在主題為z時(shí)，生成單詞v的概率，即條件概率，其符合多項(xiàng)分布:

nz，v表示主題z與單詞v的所有共現(xiàn)次數(shù).通過(guò)比較概率值可確定文檔所在主題，繼而可將相對(duì)應(yīng)圖片劃分到相同類別中，而φzv矩陣所含數(shù)據(jù)即是主題概率分配參數(shù)表的數(shù)據(jù)源.為使算法可通過(guò)編程實(shí)現(xiàn)，α設(shè)定為50/V，β設(shè)定為0.1，兩者均不隨模型中的參數(shù)變化.

3 檢索實(shí)現(xiàn)

預(yù)備工作完成后，可得到基本詞庫(kù)、概率分配參數(shù)表和已經(jīng)分類的圖片庫(kù)3份基礎(chǔ)文件，搜索的執(zhí)行過(guò)程將以此為基礎(chǔ)，經(jīng)過(guò)特征集提取、特征集歸類、圖片歸類和特征匹配4個(gè)步驟完成.假設(shè)用戶需在本地搜索圖片S的相似圖片，整個(gè)搜索過(guò)程如下.

1)特征集提取.

與特征庫(kù)建立過(guò)程類似，系統(tǒng)讀入S圖片，采用SIFT特征檢測(cè)算法生成S圖片特征集fS.

2)特征集歸類.

預(yù)備工作中第2步驟已生成針對(duì)整個(gè)圖片庫(kù)P的基本詞庫(kù)H，由于一般情況圖片庫(kù)中圖片數(shù)量較多，故本文提出如下假設(shè):

假設(shè)1 單張圖片的引入不會(huì)造成原圖片庫(kù)整個(gè)特征向量集在128維歐式空間產(chǎn)生嚴(yán)重畸變.

基于此假設(shè)，S圖片特征集的簡(jiǎn)化可直接在基本詞庫(kù)H的基礎(chǔ)上進(jìn)行.具體執(zhí)行方案是利用歐式距離作為判別準(zhǔn)則，以窮舉法為查找方法，循環(huán)查詢fS中所有特征向量，找到與基本詞庫(kù)H特征向量最近的單詞，然后用此單詞替代特征向量，查詢完成后，統(tǒng)計(jì)每個(gè)單詞詞頻，生成與S圖片對(duì)應(yīng)的文本文件dS，其內(nèi)容為

其中 Sv，V表示wV在 dS的詞頻.

3)圖片歸類.

預(yù)備工作中第3步驟生成的主題概率分配表是針對(duì)系統(tǒng)中已經(jīng)存在的圖片庫(kù)進(jìn)行迭代生成的，由于圖片數(shù)據(jù)量較大，且具有一定的普遍性，故本文提出如下假設(shè):

假設(shè)2 單張圖片的引入不會(huì)造成主題概率分配表數(shù)據(jù)的大范圍變化.

基于此假設(shè)，S圖片可以采用分配表的數(shù)據(jù)進(jìn)行分類，采用式(2)進(jìn)行計(jì)算.

計(jì)算S圖片生成各個(gè)主題的概率后可確定S圖片屬于每個(gè)主題的概率，假設(shè)z*為概率值最大的類別，一般將S圖片劃分到z*類中.

4)特征匹配.

在S圖片所屬類別z*中存在有多幅圖片，需通過(guò)特征匹配方法尋找最匹配圖片.本文首先選用SIFT特征點(diǎn)作為依據(jù)，歐式距離作為準(zhǔn)則進(jìn)行匹配操作，然后搜索z*每張圖片中每個(gè)特征向量到S圖片中每個(gè)特征向量的距離.若采用線性掃描，也稱為窮舉搜索的方法，依次計(jì)算其中每個(gè)特征向量的距離將會(huì)十分耗時(shí).因?yàn)閷?shí)際數(shù)據(jù)都會(huì)呈現(xiàn)簇狀的聚類形態(tài)，本文采用Beis和Lowe提出的BBF［16］(Best-Bin-Fist)的kd-trees近似算法，利用該算法搜索SIFT特征點(diǎn)的最近鄰點(diǎn)時(shí)，可以以更高的概率搜索到精確的最近鄰點(diǎn).kd-trees近似算法匹配標(biāo)準(zhǔn)為歐氏距離最小值與次最小值的比值在一定閾值內(nèi)時(shí)，即可認(rèn)為配準(zhǔn)成功，在本文算法中選取此閾值為0.45.

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

本文采用Corel圖像庫(kù)作為測(cè)試集進(jìn)行實(shí)驗(yàn).圖片庫(kù)總共1000幅圖片，均分為10個(gè)類別.實(shí)驗(yàn)設(shè)置聚類數(shù)為20，聚類數(shù)設(shè)置過(guò)少不能達(dá)到很好的分類效果，而聚類數(shù)過(guò)多會(huì)導(dǎo)致聚類過(guò)程非常緩慢.另外由于圖片庫(kù)主題數(shù)為10，故設(shè)置算法中LDA分類數(shù)為10.由于在實(shí)際檢索系統(tǒng)中，用戶一般只關(guān)心排序靠前的結(jié)果，因此這里取前60個(gè)結(jié)果作為有效檢索結(jié)果進(jìn)行比較.

該實(shí)驗(yàn)用來(lái)對(duì)比的方法有2個(gè)，基于興趣區(qū)域的方法和基于興趣點(diǎn)最小覆蓋圓的方法［17］.圖3和圖4展示了不同返回圖像數(shù)目時(shí)，3種算法間平均正確率和平均召回率的比較結(jié)果.

從圖3和圖4顯示的對(duì)比結(jié)果中不難看出，正確率和召回率均明顯優(yōu)于文獻(xiàn)［17］提出的兩種算法，且在返回圖像數(shù)目越少時(shí)算法優(yōu)越性越明顯.具體原因有兩點(diǎn):

1)由于要檢索的圖片只與已經(jīng)無(wú)監(jiān)督分類的同類圖片進(jìn)行比對(duì)，減少了不相關(guān)圖片的干擾，故返回圖像數(shù)目較少時(shí)準(zhǔn)確率較高;

2)算法的局限性使得一些主題特征不是很明顯的圖片會(huì)被錯(cuò)誤分類，這就導(dǎo)致在返回圖像數(shù)目過(guò)多時(shí)，準(zhǔn)確率與召回率的減少速度大于另外兩種算法.

圖3 圖像檢索結(jié)果平均正確率比較Fig.3 Average accuracy comparison of retrieval result

圖4 圖像檢索結(jié)果平均召回率比較Fig.4 Average recall rate comparison of retrieval result

5 結(jié)論

本文在綜合分析SIFT，K-Means和LDA的基本原理基礎(chǔ)上提出了一種新的圖像檢索算法，經(jīng)實(shí)驗(yàn)驗(yàn)證表明:

1)算法可實(shí)現(xiàn)較為優(yōu)異的檢索性能，例如返回10張結(jié)果條件下算法檢索正確率83.15%，召回率8.42%，在60張下正確率39.33%，召回率24.61%;

2)算法提出單張圖片的引入不會(huì)造成原圖片庫(kù)的特征向量集和主題概率分配發(fā)生嚴(yán)重畸變的兩個(gè)假設(shè)在一定范圍(待檢索圖片與原圖庫(kù)特征類似)內(nèi)是成立的;

3)算法的預(yù)備工作使檢索范圍由原先整個(gè)庫(kù)縮小至某個(gè)子類中，雖使召回率有所損失，但檢索時(shí)間得到較大的縮短;

4)可預(yù)估對(duì)于特征較接近的圖片庫(kù)，比如人臉庫(kù)，圖片預(yù)備工作會(huì)產(chǎn)生較大的分類誤差，且可能進(jìn)一步影響檢索性能.

為使本文提出的算法能處理各種類型的圖片，仍需要優(yōu)化預(yù)備工作和檢索實(shí)現(xiàn)過(guò)程的各項(xiàng)參數(shù).

References)

［1］ Rui Y，Huang T S，Chang S F.Image retrieval:current techniques，promising directions，and open issues［J］.Journal of Visual Communication and Image Representation，1999，10(1):39-62

［2］ Younes A A，Truck I，Akdag H.Image retrieval using fuzzy representation of colors［J］.Journal of Soft Computing，2007，2(3):287-298

［3］ Bhuiyan S M A，Adhami R R，Khan J F.A novel approach of fast and adaptive bidimensional empirical mode decomposition［C］//IEEE International Conference on Acoustics，Speech and Signal Processing.Piscataway，NJ:IEEE，2008:1313-1316

［4］ Yang X，Latecki L.Affinity learning on a tensor product graph with applications to shape and image retrieval［C］//Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition(CVPR).Piscataway，NJ:IEEE，2011:2369-2376

［5］ Jégou H，Douze M，Schmid C.Improving bag-of-features for large scale image search［J］.International Journal of Computer Vision，2010，87(3):316-336

［6］ Zakariya S M，Ali R，Ahmad N.Combining visual features of an image at different precision value of unsupervised content based image retrieval［C］//Proceedings of International Conference on Computational Intelligence and Computing Research.Piscataway，NJ:IEEE Computer Society，2010:110-113

［7］ Philbin J，Chum O，Isard M，et al.Object retrieval with large vocabularies and fast spatial matching［C］//Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition(CVPR).Piscataway，NJ:IEEE，2007:1-8

［8］ Tuytelaars T，Schmid C.Vector quantizing feature space with a regular lattice［C］//Proceedings of IEEE International Conference on Computer Vision(ICCV).Piscataway，NJ:IEEE，2007:1-8

［9］ Ji R，Yao H，Sun X，et al.Towards semantic embedding in visual wordbulary［C］//Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition(CVPR).Piscataway，NJ:IEEE，2010:918-925

［10］ Jian M W，Chen S.Image retrieval based on clustering of salient points［C］//2nd International Symposium on Intelligent Information Technology Application.Piscataway，NJ:IEEE，2008:347-351

［11］符祥，曾接賢.基于興趣點(diǎn)匹配和空間分布的圖像檢索方法［J］.中國(guó)激光，2010，37(3):774-778 Fu Xiang，Zeng Jiexian.A novel image retrieval method based on interest points matching and distribution［J］.Chinese Journal of Lasers，2010，37(3):774-778(in Chinese)

［12］ Lowe D G.Object recognition from local scale-invariant features［C］//Proceedings of the Seventh IEEE International Conference on Computer Vision.Piscataway，NJ:IEEE，1999:1150-1157

［13］周愛(ài)武，于亞飛.K-Means聚類算法的研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2011，21(2):62-65 Zhou Aiwu，Yu Yafei.The research about clustering agorithm of K-Means［J］.Computer Technology and Development，2011，21(2):62-65(in Chinese)

［14］ Wei X，Croft B W.LDA-based document models for ad-hoc retrieval［C］//Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval，2006:178-185

［15］ Blei D M，Ng A Y，Jordan M I.Latent dirichlet allocation［J］.Journal of Machine Learning Research，2003(3):993-1022

［16］ Beis J S，Lowe D G.Shape indexing using approximate nearestneighbour search in high-dimensional spaces［C］//Proceedings of IEEE Society Conference on Computer Vision and Pattern Recognition(CVPR).Piscataway，NJ:IEEE，1997:1000-1006

［17］齊恒.基于內(nèi)容圖像檢索的關(guān)鍵技術(shù)研究［D］.大連:大連理工大學(xué)，2012 Qi Heng.The research of key techniques in content-based image retrieval［D］.Dalian:Dalian University of Technology，2012(in Chinese)