基于SIFT，K-Means和LDA的圖像檢索算法

汪宇雷 畢樹生 孫明磊 蔡月日

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

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

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

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

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

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

1 基本框架

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

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

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

圖1為整個檢索算法的運行流程.

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

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

2 預(yù)備工作

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

2.1 特征庫建立

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

將來的搜索工作便是基于此庫尋找與用戶提交的圖片相匹配的圖片.

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

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

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

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

2.2 基本詞庫建立

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

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

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

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

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

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

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

2.3 圖片分類

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

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

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

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

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

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

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

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

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

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

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

3 檢索實現(xiàn)

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

1)特征集提取.

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

2)特征集歸類.

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

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

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

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

3)圖片歸類.

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

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

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

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

4)特征匹配.

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

4 實驗結(jié)果

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

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

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

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

2)算法的局限性使得一些主題特征不是很明顯的圖片會被錯誤分類，這就導(dǎo)致在返回圖像數(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)實驗驗證表明:

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

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

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

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

為使本文提出的算法能處理各種類型的圖片，仍需要優(yōu)化預(yù)備工作和檢索實現(xiàn)過程的各項參數(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］符祥，曾接賢.基于興趣點匹配和空間分布的圖像檢索方法［J］.中國激光，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］周愛武，于亞飛.K-Means聚類算法的研究［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)