一種基于詞袋模型的大規(guī)模圖像層次化分組算法

錢 鈞，楊 恒，劉培楨，姜文濤，周鋒飛

（西安應(yīng)用光學(xué)研究所，陜西 西安710065）

引言

隨著光電技術(shù)和互聯(lián)網(wǎng)的高速發(fā)展，人們可以很容易地獲取大規(guī)模場景的圖像數(shù)據(jù)，因此從大規(guī)模圖像集合去恢復(fù)三維場景結(jié)構(gòu)的需求和應(yīng)用也就應(yīng)運而生［1-4］。但是由于獲取圖像的傳感器參數(shù)不同，拍攝視場和角度不同，圖像集合中不但包含多個不同場景內(nèi)容的圖像，還包含噪聲污染、模糊抖動甚至錯誤圖像。因此，對雜亂無序的圖像集合進(jìn)行預(yù)處理，將內(nèi)容關(guān)聯(lián)的圖像進(jìn)行分組，不但有助于用戶快速組織和掌握圖像內(nèi)容，也是場景三維重建的前提條件和關(guān)鍵步驟。但是在無序?qū)捇€條件下，如何進(jìn)行高效的圖像分組是一項極具挑戰(zhàn)的任務(wù)。

許多學(xué)者根據(jù)不同的應(yīng)用提出了各種各樣的圖像分組算法。常用的思路是先在圖像集合中進(jìn)行兩兩圖之間的特征匹配，求出圖像間的相似度度量，再根據(jù)相似性度量矩陣對圖像進(jìn)行分組合并。美國華盛頓大學(xué)和微軟聯(lián)合開發(fā)的Photo Tourism［1］系統(tǒng)是一個基于大規(guī)模圖像的3D重建和瀏覽系統(tǒng)，該系統(tǒng)可以對輸入圖像自動分組，并在組內(nèi)進(jìn)行攝像機標(biāo)定和3D場景的重建。Photo Tourism系統(tǒng)的分組算法也是采用一種窮盡匹配策略，首先對每兩幅圖像之間用最近鄰搜索算法進(jìn)行特征點匹配，生成一個以圖像為節(jié)點，以圖像間匹配數(shù)量為權(quán)重的全連通圖；然后，將匹配特征數(shù)量小于閾值的圖像連接關(guān)系斷開，得到最終的圖像連接分組關(guān)系。Simon等人［2］在獲得所有圖像對間精確特征匹配的基礎(chǔ)上，借鑒聚類思想構(gòu)造目標(biāo)函數(shù)，采用迭代優(yōu)化該目標(biāo)函數(shù)的方法對圖像數(shù)據(jù)庫進(jìn)行分組聚類。Zheng等人［3］以圖像中的目標(biāo)區(qū)域為單元，構(gòu)造出一個區(qū)域連接圖。最后，采用匯聚聚類算法（agglomerative clustering）將這些目標(biāo)區(qū)域進(jìn)行聚類，從而得到圖像之間的分組聚類。Zeng等人［4］提出了一種利用模擬退火優(yōu)化算法進(jìn)行圖像分組的策略，通過構(gòu)造目標(biāo)函數(shù)，并采用模擬退火優(yōu)化算法求解該目標(biāo)函數(shù)的極值，以完成圖像分組。Kang等人［5］則是針對大規(guī)模圖像集合先建立一個圖像樣本空間，并在這個空間中定義了全局的索引特征。這樣每幅圖像在樣本空間中，按照是否包含全局索引特征表示為一個二進(jìn)制序列；然后，利用信息熵理論對二進(jìn)制序列進(jìn)行聚類。Chum等人［6］則采用隨機數(shù)據(jù)挖掘技術(shù)來進(jìn)行圖像分組，其核心算法是先隨機找出一些圖像作為種子，采用最小哈希算法找出他們的閉集作為一個分組；然后再在剩余的圖像中找圖像種子，進(jìn)行哈希索引進(jìn)行分組，直到所有的圖像都進(jìn)行了分組。Chen等人［7］則通過對圖像中提取的特征進(jìn)行分析，找出最具區(qū)分力的特征集合，然后通過這些特征找出最具代表性的圖像，再以這些代表圖像去和數(shù)據(jù)集合中的其他圖像進(jìn)行匹配，從而完成整個圖像集合的聚類。

已有的這些分組算法都是通過兩兩圖像間的最近鄰特征匹配，或者是利用全局特征聚類對圖像進(jìn)行分組，當(dāng)圖像規(guī)模很大時，這些算法的時間復(fù)雜度都非常高，不利于實際應(yīng)用。針對這個問題，有學(xué)者使用并行計算GPU技術(shù)對計算流程進(jìn)行加速［8］。而本文則從算法設(shè)計角度出發(fā)，提出了一種層次化的圖像分組算法，目的是增加分組準(zhǔn)確性的同時提高分組速度。首先，采用詞袋模型（bag-of-words，BOW）對雜亂無序的圖像集合進(jìn)行粗分組。BOW算法早期是用來文檔搜索的，后被研究人員引入到圖像搜索領(lǐng)域［9-11］。對一幅參考圖像，通過BOW算法可以非?？焖俚貜拇笠?guī)模數(shù)據(jù)庫中找出與這幅圖像內(nèi)容相似的圖像。BOW算法的關(guān)鍵是要把一幅圖像根據(jù)其提取出來的特征向量集合，映射為一個超高維的視詞向量（visual word vector）。這樣，圖像與圖像之間的相似性度量就轉(zhuǎn)換成視詞向量之間的相似性度量了。為了減少視詞向量的量化誤差，本文提出了一種多路量化（multiple paths quantization，MPQ）方法，可以有效減少量化誤差，從而提高圖像粗分組的準(zhǔn)確性。然后，對每一個類別，再使用特征匹配方法，并引入一種仿射不變量（面積比）的約束條件，來去除那些明顯不滿足條件的錯誤匹配，以增加特征匹配精度，從而可以獲得更加精細(xì)化的圖像分組結(jié)果。

1 基于視詞向量的粗分組

基于BOW模型的圖像間相似度計算方法，并不是直接使用圖像中的特征向量匹配作為圖像間相似度度量，而是將這些特征量化到一個超高維的視詞向量空間，每一幅圖像對應(yīng)一個視詞向量，而相似的圖像具有相似的視詞向量。在搜索過程中使用倒排文件（inverted file）數(shù)據(jù)結(jié)構(gòu)來存儲圖像的視詞向量，計算圖像間相似度，可以大幅度提高圖像檢索的效率。然而，這類算法由于特征量化造成的信息損失較大，使得圖像間相似度的準(zhǔn)確性較低。

圖1是采用字典樹算法［9］進(jìn)行特征量化時，在樹的某一層上產(chǎn)生量化誤差的原因。點A到D表示聚類中心，點1，2，3表示待量化的特征向量，實線表示聚類中心A到D定義的邊界。特征點1，2，3由于彼此近鄰，本應(yīng)該被量化至同一個葉子節(jié)點上，即在當(dāng)前層應(yīng)該被分配到同一個節(jié)點，但是按照字典樹的量化規(guī)則，它們被分配到了不同節(jié)點，最終導(dǎo)致它們會有不同的量化結(jié)果。

圖1 字典樹產(chǎn)生量化誤差示意圖Fig.1 Quantization error caused from lexicographic tree

本文提出一種多路量化算法（multiple paths quantization，MPQ）來進(jìn)行特征量化，以減少量化誤差的影響。MPQ算法的具體步驟見算法1，在每一層不是只選擇一個最近鄰節(jié)點，而是選擇M個最近鄰節(jié)點，在下一層通過比較k×M個聚類中心再選出M 個最近鄰節(jié)點，直到葉子節(jié)點所在的層，最后選出一個最近鄰節(jié)點作為量化結(jié)果，具體過程見算法1。MPQ算法通過增加候選節(jié)點個數(shù)M（M＞1），在一定程度上減小了量化誤差的風(fēng)險，從而提高了量化精度。

算法1 MPQ量化算法

在特征量化后，每幅圖像便映射成視詞空間的一個高維向量，再用倒排文件組織視詞和圖像之間的映射關(guān)系，這樣可以快速地計算視詞向量之間的距離，得到圖像間的相似度。兩兩圖像之間的相似度可以表示為相似度矩陣Mn×n的形式。獲得矩陣Mn×n是非常高效的，在本文的實驗中，對于n＝1 249幅圖像只需要2s就可以計算得到相似度矩陣中的所有數(shù)值。

最后，采用視圖-生成樹算法對矩陣所表示的加權(quán)圖進(jìn)行分割，先將兩幅相似度最高的節(jié)點（圖像）加入樹，然后加入一幅和樹中已有節(jié)點相似度最高的節(jié)點，直到再沒有余下的節(jié)點和樹中節(jié)點相似度超過給定閾值，這樣就生成了一棵樹。將這棵樹的節(jié)點從整個圖像節(jié)點中移除，在剩下的節(jié)點集合中重復(fù)這個過程，直到數(shù)據(jù)節(jié)點集合為空，或者再也找不出兩幅圖像節(jié)點之間相似度大于給定閾值為止。這樣生成的這些樹就是對整個圖像集合的劃分，一棵樹就是一個分組結(jié)果，而將那些獨立的節(jié)點視為污染圖像，系統(tǒng)將自動去除它們。

2 基于仿射不變量約束的細(xì)化分組

為了進(jìn)一步提高圖像分組的準(zhǔn)確性，還需要對每個分組進(jìn)行更加精細(xì)化的處理。這時候可以利用特征向量匹配來提高圖像間相似性度量，因為特征向量所包含的信息要比其量化值豐富得多，但是特征向量間的最近鄰搜索的效率較低，系統(tǒng)響應(yīng)時間過長。

本文提出的方案是首先利用前面步驟中的量化結(jié)果來進(jìn)行特征匹配；然后，給出了一種利用仿射不變量（面積比）的約束條件去除誤匹配的方法。首先，特征之間的初始匹配由量化結(jié)果決定，即認(rèn)為具有相同量化值的特征之間是匹配的。算法2給出了具有相同量化值的特征匹配的實現(xiàn)細(xì)節(jié)。接著，利用面積比這個仿射不變量進(jìn)一步去除誤配，算法3給出這一步驟具體實現(xiàn)的細(xì)節(jié)。去除誤配后，剩余的內(nèi)點數(shù)量可以作為圖像間增強的相似度度量。最后，再次使用最小生成樹算法對組內(nèi)圖像重新分割。精細(xì)分組過程使得原來的粗分組結(jié)果更加準(zhǔn)確和細(xì)致，其結(jié)果是：可能會去除組內(nèi)那些相似度低的圖像，也可能改變原先組內(nèi)圖像間連接拓?fù)潢P(guān)系，甚至?xí)⒃瓉淼姆纸M關(guān)系再次分割成更加精細(xì)的小組。

算法2 對于量化結(jié)果是第i個視詞的特征匹配算法

算法3 仿射不變量約束

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

本文從互聯(lián)網(wǎng)站上按照搜索關(guān)鍵詞自動下載大量圖像集合，設(shè)計了一個圖像集合的自動分組系統(tǒng)，該系統(tǒng)不但可以使用戶方便自動有效管理下載的大量無序圖像集合，建立集合間的分組關(guān)系和集合內(nèi)的排序關(guān)系，還能夠為下一步的場景三維重建提供數(shù)據(jù)支撐。使用到的數(shù)據(jù)庫是從圖像共享網(wǎng)站Flickr上下載的1 249幅關(guān)于西安鐘樓（Bell-Tower）的圖像數(shù)據(jù)庫。實驗在普通PC機環(huán)境上運行，其配置是Intel雙核CPU E6750＠2.66GHz和2 G內(nèi)存。算法程序采用VC6.0編寫。

3.1 Bell-Tower數(shù)據(jù)庫分組結(jié)果及分析

Bell-Tower數(shù)據(jù)庫包含1 249幅圖像，部分圖像見圖2所示?？梢钥闯?，這樣一個數(shù)據(jù)庫包含不少污染圖像，例如許多游客把在鐘樓附近的商店里所拍攝的圖像上傳到網(wǎng)站上后，也會把圖像標(biāo)記為Bell Tower。

圖2 Bell-Tower數(shù)據(jù)庫中的部分圖像實例Fig.2 Image examples from Bell-Tower database

從整個數(shù)據(jù)庫中一共提取出867 352個SIFT圖像特征點，使用這些特征訓(xùn)練了一個5層10分支的字典樹，然后先進(jìn)行粗分組，共有293幅圖像被系統(tǒng)當(dāng)作污染圖像去除，將保留下來的956幅圖像分成14個組。圖3（a）給出了一個粗分組的示例。在精細(xì)分組階段，對每個組內(nèi)的圖像采用增強的相似度準(zhǔn)則重新分組，其結(jié)果可能是一些弱相關(guān)的圖像被系統(tǒng)排除，或者是組內(nèi)生成樹的連接關(guān)系被重新確定，甚至?xí)澐殖龈泳?xì)的分組。圖3給出一個粗分組被重新分割成2個更加精細(xì)分組的例子。圖3（a）中的圖像看上去彼此相似，因為它們都包含樓塔、房屋和街道這些景物。但實際上這些圖像包含了兩個不同的場景。精細(xì)分組結(jié)果如圖3（b）和3（c）所示，在組3（b）中出現(xiàn)的樓塔建筑實際上是西安市中心的鼓樓，而出現(xiàn)在組3（c）中的塔樓建筑才是鐘樓，這兩個建筑以及周邊環(huán)境確實有些類似。

圖3 粗分組結(jié)果被劃分成2個更加精細(xì)分組Fig.3 Two refined groups divided from coarse grouping results

在精細(xì)分組階段之后，一共有874幅圖像被保留下來，共分成17個組別。圖4給出其中5個分組的部分圖像例子。為了評價提出算法的分組性能，預(yù)先采用手工的方法對圖像集合進(jìn)行了標(biāo)記。標(biāo)記方法對拍攝鐘樓建筑的不同方位、不同的街道視景，甚至拍攝時間是白晝還是黑夜都進(jìn)行了區(qū)分。這些標(biāo)記可以用來評價系統(tǒng)的分組性能。圖5給出了系統(tǒng)不同階段，圖像分組的查準(zhǔn)率-查全率（precision-recall）曲線?？梢钥闯?，精細(xì)分組過程確實可以顯著提高粗分組精度，同時在精細(xì)分組階段，使用約束條件比不使用約束還能獲得更高的分組精度。

圖4 層次化分組算法在Bell-Tower數(shù)據(jù)庫上的5個分組結(jié)果Fig.4 5 grouping results of Bell-Tower database by hierarchical grouping algorithm

圖5 在不同階段圖像分組的查準(zhǔn)率-查全率曲線比較Fig.5 Contrast of precision-recall curves in different image grouping stages

3.2 約束條件有效性驗證

表1列出了對應(yīng)圖3（b）連接關(guān)系中圖像對間特征匹配結(jié)果。圖像之間的單對應(yīng)矩陣采用RANSAC魯棒估計算法進(jìn)行估計，并作為驗證特征間是否匹配的依據(jù)：如果投影誤差小于或者等于3個像素，則認(rèn)為特征之間匹配關(guān)系正確。從表1中可以看出，仿射不變量約束可以有效地去除誤匹配，雖然這種弱約束條件也同時去除了少量正確匹配，但是特征匹配的精度得到了較大地提高，這有利于提供更加準(zhǔn)確的圖像相似度度量，從而獲得性能更優(yōu)的圖像分組結(jié)果。另外，圖6給出一個特征匹配的例子，可以看出上述約束明顯地去除了許多誤匹配。

表1 使用約束前后的特征匹配結(jié)果Table 1 Results of feature marching before and after using constraints

圖6 使用仿射不變量約束去除錯誤特征匹配Fig.6 Removing incorrect feature marching by using affine invariant constraint

4 結(jié)論

針對大規(guī)模無序圖像的自動分組應(yīng)用，本文提出了一種層次化圖像分組聚類算法。先采用詞袋模型對無序圖像集合進(jìn)行粗分組；然后，在粗分組基礎(chǔ)上，采用特征向量匹配的方法，獲得圖像之間更精確的相似度，從而完成圖像集合的精細(xì)分組。實驗結(jié)果表明，本文算法能夠快速去除圖像集合中大量的與內(nèi)容無關(guān)的污染圖像，并按照數(shù)據(jù)集合中不同圖像場景內(nèi)容對圖像集合進(jìn)行準(zhǔn)確劃分，同時還完成了圖像組內(nèi)的特征級匹配，這不但能夠幫助用戶迅速掌握圖像集合內(nèi)容，還可以為后續(xù)大規(guī)模場景的三維重建工作提供有效的基礎(chǔ)數(shù)據(jù)。

［1］ Snavely N，Seitz S，Szeliski R.Photo tourism：explo-ring photo collections in 3D［J］.ACM Transactions on Graphics，2006，25（3），835-846.

［2］ Simon I，Snavely N，Seitz S M.Scene summarization for online image collections［C］／／In Proceedings of the International Conference on Computer Vision.USA：IEEE，2007：1-8.

［3］ Zheng Y，Zhao M，Song Y，et al.Tour the world：building a web-scale landmark recognition engine［C］／／In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Miami，USA：IEEE，2009：1085-1092.

［4］ Zeng X，Wang Q，Xu J.Map model for large-scale 3dreconstruction and coarse matching for unordered wide-baseline photos［C］／／In Proceedings of British Machine Vision Conference.Leeds，UK：BMVC Press，2008.

［5］ Kang L，Wu L，Yang Y H，A novel unsupervised approach for multilevel image clustering from unordered image collection［J］.Frontiers of Computer Science in China，2013，7（1）：69-82.

［6］ Chum O，Matas J.Large-scale discovery of spatially related image［J］.IEEE Transactions on Pattern A-nalysis and Machine Intelligence，2010，32（2）：371-377.

［7］ Chen Xu，Das M，Loui A.An efficient framework for location-based scene matching in image databases［J］.International Journal of Multimedia Information Retrieval，2012，1（2）：103-114.

［8］ Johnson T，Georgel P F，Raguram R，et al.Fast organization of large photo collections using CUDA［C］／／European conference on Trends and Topics in Computer Vision.Pennsylvania.USA：Pennsylvania State University，2012：463-476.

［9］ Nistér D，Stewénius H.Scalable recognition with a vocabulary tree［C］／／In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.New York：IEEE，2006，2161-2168.

［10］ Wang C Q，Zhang B C，Qin Z C，et al.Spatial weighting for bag-of-features based image retrieval［C］.USA：Lecture Notes in Computer Science，2013：91-100.

［11］ Wang F，Wang H，Li H，et al.Large scale image retrieval with practical spatial weighting for bag-of-visualwords［C］.USA：Advances in Multimedia Modeling Lecture Notes in Computer Science，2013：513-523.