,

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

一種基于融合的詞袋模型和大裕度最近鄰分類算法的圖像識別方法

楊亦波, 王斌*,王劍鋒

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海200234)

圖像分類作為圖像處理和計(jì)算機(jī)視覺的重要組成部分,能夠快速準(zhǔn)確地對數(shù)字圖像進(jìn)行分析和管理.對基于bagofword(BOW)模型的分類問題進(jìn)行了研究,針對圖像理解中的圖像相似度之間的關(guān)系,提出了一種最大間隔最近鄰居分類算法,通過對成對約束的度量學(xué)習(xí)算法,在優(yōu)化目標(biāo)中增加原空間數(shù)據(jù)分類的約束,學(xué)習(xí)到了一個可以反映當(dāng)前樣本數(shù)據(jù)的距離函數(shù),并且在k-NearestNeighbor(KNN)分類器上使用該學(xué)習(xí)到的距離函數(shù)來構(gòu)建分類器,并在多個國際標(biāo)準(zhǔn)圖像數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),結(jié)果表明:該算法相比傳統(tǒng)的基于歐式距離的算法具備更高的正確率.

圖像分類; 詞袋模型; 大裕度最近鄰分類算法

0 引 言

超過80%的自然界信息都是通過視覺被人類所接收的,而圖像又作為視覺信息的基礎(chǔ)載體,具有呈現(xiàn)直觀、內(nèi)容復(fù)雜多變、蘊(yùn)含豐富信息等特點(diǎn).隨著數(shù)字互聯(lián)網(wǎng)的蓬勃發(fā)展,社會生活數(shù)字化程度逐漸加深,包含視覺信息的數(shù)字圖像數(shù)量增長迅猛,并廣泛地充斥于人們的生活當(dāng)中.因此,人們急切地需要依據(jù)計(jì)算機(jī)來智能地理解這些數(shù)字圖像的語義內(nèi)容及信息,進(jìn)而便于數(shù)字圖像的智能化管理、分析及應(yīng)用.

近幾年來,有大量關(guān)于圖像理解的研究成果發(fā)表在國際頂級學(xué)術(shù)期刊以及頂級學(xué)術(shù)會議上.圖像理解的定義為:利用計(jì)算機(jī)從影像中提取被攝景物的語義信息,以實(shí)現(xiàn)識別、分類和判讀的過程[1].其主要的任務(wù)就是對圖像中的實(shí)體進(jìn)行識別、判斷圖像所表達(dá)的主題和分析圖像中所包含的語義信息.

由于圖像是非結(jié)構(gòu)化的數(shù)據(jù),并沒有一個原始的自然的向量表達(dá)形式,很多傳統(tǒng)的基于向量空間輸入的機(jī)器學(xué)習(xí)算法對此并不適用.近年來,圖像bag of word(BOW)模型受到了非常廣泛的關(guān)注,并且在各種場景圖像分類任務(wù)中都取得了非常好的效果.在早期的基于BOW模型的分類方法中[2],常常假定圖像局部區(qū)域之間是彼此獨(dú)立的.Wang[3]釋放獨(dú)立性假設(shè)條件,對圖像局部區(qū)域之間的關(guān)系進(jìn)行顯示建模.Wu[4]于2007年提出了一種基于視覺語言模型的方法,其將每幅圖像都轉(zhuǎn)化為視覺單詞的矩陣并假設(shè)視覺單詞之間是條件相關(guān)的.隨后,Tkmy[5]提出了一種新的視覺語句圖像表示方法,該方法在BOW模型的基礎(chǔ)上利用視覺單詞之間的空間關(guān)系構(gòu)成相應(yīng)的“句子”,然后再對圖像進(jìn)行分類.

對于構(gòu)建好的BOW模型,現(xiàn)有的大部分圖像相似度比較方法都是使用向量空間的距離函數(shù)作為圖像相似度的衡量準(zhǔn)則,并在經(jīng)典的機(jī)器學(xué)習(xí)分類器上進(jìn)行學(xué)習(xí)和判斷.其本質(zhì)就是把每一副用于訓(xùn)練的圖像通過某種函數(shù)關(guān)系映射到歐式空間里的一個點(diǎn),并利用歐式空間的良好性質(zhì)在其中進(jìn)行分類器的訓(xùn)練和學(xué)習(xí).最常用的就是k-NearestNeighbor(KNN)分類器,其基本原理是根據(jù)與測試樣本最近的k個訓(xùn)練樣本的類別來決定測試樣本的類別.最初用于解決文本分類的問題,后來廣泛地應(yīng)用于模式識別的各個領(lǐng)域.雖然KNN應(yīng)用很廣,但KNN中點(diǎn)與點(diǎn)之間的距離通常采用歐式距離度量,該距離對所有屬性特征同等對待,忽略了屬性特征間的主次關(guān)系,沒有突出不同的屬性特征對分類帶來不同的影響,因此會降低分類器的性能.為了克服歐氏距離的缺點(diǎn),本文作者提出了一種大裕度最近鄰的度量學(xué)習(xí)算法,通過對樣本的訓(xùn)練學(xué)習(xí)到模型間的內(nèi)在關(guān)系,更好地提高了分類的效果.

1 詞袋模型及圖像分類流程

1.1BOW模型

BOW模型最早出現(xiàn)在自然語言處理(NLP)和信息檢索(IR)領(lǐng)域中[6],常被用于處理文檔的識別與分類.如下兩個句子:(1)John likes to watch movies.Mary likes too.(2)John also likes to watch football games.根據(jù)這兩句話中出現(xiàn)的單詞,先構(gòu)建一個單詞的詞典,如下{1‘John’,2‘likes’,3‘to’,4‘watch’,5‘movies’,6‘a(chǎn)lso’,7‘football’,8‘games’,9‘Mary’,10‘too’}.這個詞典中包含了所有10個單詞,每個單詞有著它自己的唯一索引,根據(jù)這個詞典,統(tǒng)計(jì)每個單詞所出現(xiàn)的次數(shù),就能夠?qū)⑸鲜鰞删湓捴匦卤磉_(dá)為下面兩個變量:(1)[1,2,1,1,1,0,0,0,1,1],(2)[1,1,1,1,0,1,1,1,0,0],然后就可以直接計(jì)算這兩個向量間的距離知道這兩句話是否相似.

近些年來,BOW模型因其簡單且行之有效的優(yōu)點(diǎn)得到了更加廣泛的應(yīng)用,受BOW模型在文檔分類中的啟發(fā),Li等[7]利用BOW模型將圖像類比為文檔提出了用BOW模型表達(dá)圖像的方法.文檔和圖像在BOW模型下的對應(yīng)關(guān)系如下:

文集對應(yīng)圖像集,單詞對應(yīng)視覺單詞,詞典對應(yīng)視覺詞典.

1.2圖像分類的基本流程

如今,BOW模型被廣泛地應(yīng)用到圖像的目標(biāo)分類與場景分類中,在基于BOW的模型的圖像分類技術(shù)中,通常包含了如下3個主要部分:1)特征提取;2)視覺詞典構(gòu)造;3)分類器的訓(xùn)練.特征提取主要是從給定的圖像集中提取全局或者局部不變特征,得到圖像的表示.視覺詞典的構(gòu)造主要是對提取的圖像特征進(jìn)行聚類,將聚類中心作為視覺單詞,所有聚類中心的集合即為構(gòu)造的視覺詞典.分類的訓(xùn)練是針對于要進(jìn)行的圖像分類任務(wù)所進(jìn)行的操作,結(jié)合訓(xùn)練的分類器即可進(jìn)行圖像的分類與識別.圖1給出了BOW模型應(yīng)用于圖像分類的基本流程,首先提取訓(xùn)練圖像和測試圖像,然后用簡單的k-means聚類方法將提取的特征聚成300類,如此,每張訓(xùn)練圖像和測試圖像就可以用一個300維的向量表示了.接著,將訓(xùn)練圖像輸入到分類器里,調(diào)整分類器的各個參數(shù),再用訓(xùn)練好的分類器來預(yù)測測試圖像,得到其分類結(jié)果.

圖1 圖像分類的基本流程圖

2 Large Margin Nearest Neighbor(LMNN)算法

在所有的分類器中,KNN算法是最簡單有效的分類算法,但是KNN忽略了屬性特征之間的主次關(guān)系,會降低分類器的性能.因此,為了克服歐氏距離的缺點(diǎn),Xing在文獻(xiàn)[8]中提出了基于成對約束度量學(xué)習(xí)框架的LMNN算法.

LMNN算法是一種基于馬氏距離的分類方法,該方法的原理是通過最小化目標(biāo)函數(shù),來縮小同類樣本之間的距離,加大屬于不同類樣本之間的距離.設(shè)n維歐式空間中的兩個點(diǎn)x=(x1,x2,…,xn)T和y=(y1,y2,…,yn)T,則點(diǎn)x和y之間的馬氏距離為:

(1)

其中,A必須是一個半正定的矩陣,才能夠保證M的度量性.矩陣A實(shí)際上包含了對原空間坐標(biāo)的線性變換和伸縮操作.可以對A進(jìn)行特征分解,分解為A=VTDV,其中V是A的特征向量組成的矩陣,D是對角陣并且其各個元素分別對應(yīng)矩陣A的特征值,則有:

(2)

(2)式中矩陣A實(shí)際上是通過線性變換V作用到樣本點(diǎn)上,然后對每一個坐標(biāo)進(jìn)行伸縮處理(乘以D).在度量學(xué)習(xí)問題中,這是一個優(yōu)化問題,可以通過確定矩陣A,得到符合一定條件和要求的度量函數(shù).而在Xing[8]的工作中,增加了同類樣本之間的成對約束來求解這個優(yōu)化問題,最終可以來確定A矩陣中的參數(shù).形式上,該優(yōu)化問題可以表述如下:

(3)

(4)

A≥0.

(5)

(3)、(4)式中集合S表示同類樣本對所組成的集合,D表示不同類樣本對所組成的集合.該優(yōu)化問題要求不同類樣本對之間的距離之和大于等于一個常數(shù),而優(yōu)化的目標(biāo)是使相同類別的樣本對之間的距離和盡可能的小.文獻(xiàn)[9]中提出了一個梯度下降的迭代算法,來求解滿足條件的A.該算法雖然能夠很好地找出滿足條件的A矩陣,但是面對十分龐大的樣本數(shù)據(jù)集,計(jì)算的復(fù)雜程度也明顯上升,這是由于當(dāng)訓(xùn)練樣本集比較大時(shí),所構(gòu)造出來的集合S和D反應(yīng)的是樣本對之間的關(guān)系,也會非常大.假設(shè)對于兩分類的訓(xùn)練集,訓(xùn)練樣本集的大小為L,其中正例有P個,反例有N個,則同類樣本對的集合S中元素的個數(shù)為(P2+N2)/2-P-N個,而不同類樣本對的集合D中元素個數(shù)為PN/2個[10].因此在實(shí)際問題中往往隨機(jī)從S和D中抽取一些元素進(jìn)行優(yōu)化.

3 實(shí)驗(yàn)過程

3.1實(shí)驗(yàn)數(shù)據(jù)

本算法是在Matlab平臺上搭建圖像檢索系統(tǒng)實(shí)現(xiàn)的,實(shí)驗(yàn)開始時(shí)首先將訓(xùn)練集與測試集的圖片一起加載入系統(tǒng),采用簡單的k-means聚類方法得到數(shù)據(jù)集的視覺詞典,構(gòu)建好詞袋模型.接著用訓(xùn)練集的構(gòu)建好的詞袋來訓(xùn)練分類器,由于數(shù)據(jù)龐大的原因,首先在每個類別中只選擇10個樣本進(jìn)行訓(xùn)練,這100個樣本兩兩構(gòu)成約束對,利用梯度下降法得到最小的誤差以及對應(yīng)的距離矩陣.若誤差不滿足預(yù)期的要求,則每個類別增加5個樣本,以此類推,直到求得符合預(yù)期要求的距離矩陣.本實(shí)驗(yàn)選用了4個國際標(biāo)準(zhǔn)的圖像分類集,分別是CVCL、Caltech101中選取10類、Ground Truth中8類、Corel中10類.其中CVCL和Corel這2個圖像集中每一類別的圖片的大小是相同的,而Caltech 101和Ground Trurh中每類圖片的大小層次不齊.具體數(shù)據(jù)集的相關(guān)屬性如表2所示.

表2 樣本數(shù)據(jù)集

3.2實(shí)驗(yàn)分析

在實(shí)驗(yàn)中,對比了傳統(tǒng)基于歐氏距離的KNN以及基于馬氏距離的可學(xué)習(xí)的LMNN算法,其中KNN和LMNN算法中K取值為3.KNN算法只是根據(jù)最近鄰的3個樣本來確定該圖像屬于的類別,由于選取的數(shù)據(jù)集都不是很大,因此LMNN通過所有訓(xùn)練集的樣本來學(xué)習(xí)得到一個適合的矩陣,然后來預(yù)測測試集的類別,用準(zhǔn)確率作為判別算法優(yōu)劣的準(zhǔn)則.實(shí)驗(yàn)數(shù)據(jù)如表3所示.

表3 各數(shù)據(jù)集預(yù)測準(zhǔn)確率 (%)

從表3中數(shù)據(jù)可以反映出,運(yùn)用本文算法后,在各個數(shù)據(jù)集上預(yù)測的準(zhǔn)確率都有明顯的提升,在某些測試集上準(zhǔn)確率相比傳統(tǒng)算法提高了將近20個百分點(diǎn),這結(jié)果令人較為滿意.

一個完美的圖像分類模型預(yù)測結(jié)果與實(shí)際一致,但在實(shí)驗(yàn)過程中,該模型的預(yù)測與實(shí)際之間存在誤差.為了探測模型預(yù)測的正確率,引入“混淆矩陣”.

通過比較計(jì)算每個實(shí)測像元與分類圖像的位置和分類,可以得出混淆矩陣.其每一列代表了預(yù)測類別,每一列的總數(shù)表示預(yù)測為該類別的數(shù)據(jù)的數(shù)目;每一行代表了數(shù)據(jù)的真實(shí)歸屬類別,每一行的數(shù)據(jù)總數(shù)表示該類別的數(shù)據(jù)實(shí)際的數(shù)目.如圖2所示,在LMNN算法下,4個圖像數(shù)據(jù)集的混淆矩陣.

圖2 LMNN中4個數(shù)據(jù)集的混淆矩陣

從實(shí)驗(yàn)結(jié)果可以看出,LMNN比KNN在這4個數(shù)據(jù)集上預(yù)測分類的結(jié)果正確率較高,但是對于Caltech101和Ground Truth這2個數(shù)據(jù)集,兩種算法都有較高的錯誤率,可能是由于圖片大小不同,在建立BOW模型時(shí),特征提取方面存在問題,這將是未來研究需要改善的地方.

4 結(jié) 論

本文作者融合了BOW詞袋模型和度量學(xué)習(xí)中的LMNN大裕度最近鄰分類算法,提出了一種新的圖像分類算法.BOW詞袋模型最早用于文檔的分類中,運(yùn)用到圖像分類中可以大大減少訓(xùn)練樣本的輸入維度,方便計(jì)算.LMNN算法是對傳統(tǒng)KNN算法的改進(jìn),傳統(tǒng)的KNN只是簡單地計(jì)算2個樣本的歐氏距離,而LMNN算法的思想是要求同類樣本之間的距離盡可能小,而非同類樣本之間的距離要大于等于某個固定的常數(shù),根據(jù)這個條件,就可以優(yōu)化出一個滿足要求的矩陣.通過在4個國際標(biāo)準(zhǔn)的圖像數(shù)據(jù)集上的實(shí)驗(yàn),也證明了該算法能在一定程度上提高分類性能.但是,在實(shí)驗(yàn)過程中也遇到了許多新的問題,比如對于不同大小,不同像素的圖像,BOW詞袋模型也具有一定的局限性.對于K數(shù)值的確定,為了減少計(jì)算量,取值為3,但是提高K值是否會提高分類性能,或者對于不同數(shù)據(jù)集是否都有一個最佳的K值,這些都是要在未來作進(jìn)一步深入研究和探討.

[1] Chen Y,Wang J Z.Image categorization by learning and reasoning with regions [J].Journal of Machine Learning Research,2004,5(4):913-939.

[2] Sivic J,Russell B C,Efros A A,et al.Discovering object categories in image collections [R].Cambridge:Massachusetts Institute of Technology Computer Science & Artificial Intelligence Laboratory,2005.

[3] Wang G,Zhang Y,Li F F.Using dependent regions for object categorization in a generativeFramework [C].2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition,New York:IEEE,2006.

[4] Wu L,Li M,Li Z,et al.Visual language modeling for image classification [C].Proceedings of the 9th ACM SIGMM International Workshop on Multimedia Information Retrieval,Augsburg:ACM,2007.

[5] Tirilly P,ClaveauV,Gros P.Language modeling for bag-of-visual words image categorization [C].Proceedings of the 7th ACM International Conference on Image and Video Retrieval,Niagara Falls:ACM,2008.

[6] Lewis D D,Jones K S.Natural language processing for informationretrieval [J].Communications of the ACM,1996,39(1):92-101.

[7] Li F F,Perona P.A bayesian hierachical model for learning natural scene categories [C].IEEE Computer Society Conference on IEEE,2005,2(2):524-531.

[8] Xing E P,Ng A Y,Jordan M I,et al.Distance metric learning with application to clustering with Side-information [J].Advances in Neural Information Processing System,2002,15:505-512.

[9] Schutz M,Joachims T.Learning a Distance Metric from Relative Comparisons [C].Proceedings of the 16th International Conference on Neural Information Processing Systems,Whistler:ACM,2003.

[10] Davis J V,Kulis B,Jain P,et al.Information-theoretic metric learning [C].Proceedings of the 24th international conference on Machine learning,Corvallis:ACM,2007.

(責(zé)任編輯：包震宇)

Animagerecognitionmethodbasedonbag-of-wordmodelandlargemarginnearestneighborclassificationalgorithm

Yang Yibo,WangBin*,WangJianfeng

(The College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai200234,China)

As an important part of image processing and computer vision,image classification can analyze and manage digital images quickly and accurately.This paper studies the classification problem based on bag of word (BOW)model and learns the relationship between image similarities in image comprehension.Then,this paper proposes a maximum-interval Nearest Neighbor classification algorithm.By learning the pair-wise constraint metric and adding the constraint of the original spatial data classification to the optimal target.This paper learns a distance function which can reflect the current sample data and uses this function to construct the classifier according to thek-NearestNeighbor(KNN) classifier.Compared with the traditional Euclidean distance algorithm,the classifier based on metric learning has higher correct rate than the traditional one based on the experiments on several international standard image datasets.

image classification; bag of word model; large margin nearest neighbor classification algorithm

2016-11-27

國家自然科學(xué)基金(61503251)

楊亦波(1992-),男,碩士研究生,主要從事圖像處理方面的研究.E-mail:530056910@qq.com

導(dǎo)師簡介: 王 斌(1986-),女,講師,主要從事圖像處理方面的研究.E-mail:binwang@shnu.edu.cn

TP391

:A

:1000-5137(2017)04-0584-06

*