一種改進模糊C均值聚類的圖像標注方法

李長磊,呂學強,張 凱,董志安

1(北京信息科技大學 網絡文化與數字傳播北京市重點實驗室,北京 100101) 2(首都師范大學 中國語言智能研究中心,北京100048) 3(北京市朝陽區市政市容管理委員會,北京 100021) E-mail:292369843@qq.com

1 引 言

近年來,隨著計算機技術、存儲技術的發展越來越快,以及數字圖像信息和互聯網的普及,大量的數據每天通過各大網站和數碼產品產生出來,并以極快的速度在互聯網上進行傳播.大量的無規則的數據需要進行區分和處理,再識別和規范這些數據的存儲,以便更方便的進行應用.這就給如何有效的檢索和處理這些成堆的數據建立了難題.自動圖像標注技術(Automatic Image Annotation,AIA)就很好的解決了這些標注圖像的語義問題,通過自動的給這些圖像進行標注關鍵詞來反映圖像的內容.這個技術通過已經標注好的圖像庫或其他工具訓練了一套語義與圖像特征空間的關系模型,并通過這個模型對未標注的圖像進行語義標注,它嘗試建立圖像語義特征和圖像底層特征的對應關系,來處理圖像的語義鴻溝問題.

基于分類的圖像標注是將標注問題定義為一個分類問題,每一個詞對應一個類型,并對應一個分類器.文獻[1]使用Bayes方法,文獻[2]使用SVM或Ensemble SVM,這些方法都是利用圖像底層特征和標簽來建模,實現圖像標注.文獻[3,4]用隱馬爾可夫模型方法,文獻[5,6]用SVM方法實現了多類分類標注,且處理的圖像可以關聯多個關鍵詞.

基于概率模型的標注方法是從概率角度出發,通過計算機視覺特征與標注詞的相關性以及概率關系來預測標注詞.Mori于1999 年提出了共生模型[7],通過計算圖像柵格與標注詞的共存關系來標注各個圖像柵格.Duygulu提出了機器翻譯模型以改進共生模型[8],此模型把文本標注詞視為與視覺特征相同的用來描述圖像內容的方法,區別只在于它們屬于不同模態.文獻[9]提出了多伯努利相關模型,該模型針對跨媒體相關模型和連續空間相關模型存在的不足進行了修改.基于主題的標注則通過引入潛在主題概念建立高層語義與低層圖像特征之間的聯系實現圖像標注.文獻[10]首次把文本領域的潛在語義關系使用到圖像標注中.文獻[11]引入了概率潛語義分析通過引入若干個潛在主題變量從概率角度解釋圖像視覺特征與語義標注詞的關聯關系.

李志欣等人[12]提出了融合語義的主題的圖像標注模型,首次在概率潛語義的基礎上,融合了主題語義的方法進行標注.盧漢青等人[13]利用了圖學習的方法,通過圖像相似性的圖學習方法和詞匯間語義的相關性來改善圖像標注模型.袁瑩等人[14]利用稀疏效應和多核學習的方法在標注中去得了很好的效果.[15]鮑泓等人介紹了圖像標注發展階段的三大方法,并具體介紹了基于區域劃分的圖像自動標注方法.[16]劉凱等人利用深度玻爾茲曼機實現圖像與文本的低層次特征向稀疏高層次抽象概念的轉變.[17]張曉春利用基于統計的模型的最大概率方法,結合最近鄰準則的方法,改進了圖像標注方法.

2 改進的距離測度

傳統的聚類算法中的距離測度主要有歐式聚類、馬氏距離、閔可夫斯基距離、漢明距離等,它們描述的都是圖像底層特征的相似度.在基于分類的聚類算法中,常常利用特征向量進行距離的計算,即相似度的計算.不同的相似度對算法的影響很大,所以針對不同的數據要選取合適的相似度方法.

模糊C均值聚類采用的是傳統的歐式距離為相似度,它一般是利用X=(x1,x2,…,xn),Y=(y1,y2,…,yn)兩向量進行相似度運算.歐幾里得距離是典型的相似度計算方法.

(1)

式(1)表示的是高維度向量中點到點之間的距離,其xi、yi∈X中,且xi、yi分別表示X和Y的第i個坐標的值.

一般的FCM算法都是以圖像特征的值與聚類中心之差作為目標函數與同類樣本的相似度,即為Dik=‖xk-ci‖2.FCM聚類算法一般以樣本之間的相似度測度作為距離,表示的是樣本與聚類中心的距離,當樣本與某一類聚類中心的隸屬度越大時,他們之間的距離越小,反之當樣本與聚類中心的距離越大時,他們之間的隸屬度越小.但是針對FCM聚類來講,他們樣本到類的隸屬度不是絕對的0和1,而是在0到1之間的模糊值,這就是使的分類的準確性不高,分類的界限較為模糊,一定程度上會使類與類之間區分不夠明顯.

本論文為了提高模糊C均值聚類的準確性,采用了一種新的距離測度算法[15],基于單方面考慮同類之間距離,引起的聚類中心和隸屬度互相約束的缺陷,提出一種將類與類間的距離和同類距離進行融合的新距離測度,利用圖像語義標簽作為同類樣本和異類樣本間距離的判定,學習到了的新的距離測度不僅考慮到了同類樣本的緊密程度還考慮到了不同樣本間的稀疏程度,式(2)為新的距離測度.

(2)

(3)

通過距離測度可以有效的體現聚類中點到點之間的所屬關系,可以有效提高標注的精準度.新的距離測度同時考慮到了同類樣本的距離與異類樣本之間的距離,不單單是把點到聚類中心的距離作為唯一的度量,異類樣本距離的介入改進了傳統的距離思想,并通過做差取絕對值動態的平衡同類異類樣本距離的比重,使之能取得更好的聚類效果,提高標注準確率.

3 改進的FCM聚類算法

3.1 FCM聚類算法

傳統的FCM聚類算法是通過隸屬度來確定聚類中的點屬于哪一個類的程度的算法.FCM聚類算法是一種基于劃分的聚類算法,其中的模糊的概念是一種不確定性,確定性指的是非黑即白,只將事物分為正反兩種可能性.不確定性是一種模糊的概念,他表示的是一件事情趨于一種可能性的程度,是一種可能性.他可以把這種可能性描述成從0到1的一個數值,而不是非0則1.那么我們把一個樣本點所屬一個類型的相似程度稱為隸屬度,利用u來表示隸屬度.其隸屬度U滿足式(4),一個樣本庫中的隸屬度總和為1.

(4)

上式即為約束條件的條件公式.那么FCM的目標函數的一般化形式為:

(5)

上述公式中目標函數是由隸屬度與各個樣本到聚類中心的距離所組成的,m是隸屬度的乘子,可以部署樣本的權重.對目標函數使用拉格朗日乘數法,以及結合隸屬度的約束條件,首先對uij求偏導可以計算出隸屬度公式為:

(6)

其次對ci就求偏導可得聚類中心函數為:

(7)

由公式可見,聚類中心函數和隸屬度函數是互相影響的,彼此包含的關系.任意賦給兩者其中一個初值,只要滿足條件即可迭代生成,直到目標函數J趨于穩定,最后當J收斂到一個穩定的值時趨于穩定.

3.2 FCM聚類算法的改進

本文采用的新的距離測度算法[18],改善了傳統聚類算法的缺陷,傳統FCM聚類算法對于數值點的判斷較為孤立,對于隨機產生的聚類中心沒有有效的調整方法.本文采用的同類異類樣本距離的差值,改善了傳統聚類算法中只考慮單個類內距離關系的問題,距離測度沒有考慮同類異類樣本間的整體關系.式(8)為改進后的目標函數.

(8)

式(9)通過在目標函數中加入拉格朗日乘子得到新的無約束的目標函數.

(9)

對目標函數對于隸屬度uik求導得:

(10)

通過隸屬度之和為1的約束,上式可以化簡得到隸屬度公式為:

(11)

接著對聚類中心vi求導可推導出聚類中心公式為:

(12)

其中

(13)

若i=j

(14)

若i≠j

(15)

本文中的(8)-(15)為基于同類異類樣本改進的FCM聚類算法的改進流程,是利用相同標簽和不同標簽當做同類和異類的樣本進行試驗,(8)為改進后的目標函數,(11)為基于新的距離測度得到的隸屬度函數,(12)為改進后的聚類中心函數.

本文在[18]的改進算法的基礎上,提出了一種新的利用迭代生成的聚類方法,首次計算異類樣本之間距離時,利用傳統的聚類算法得到每個標簽中的中心點,作為計算不同類間距離所需要的參數.隨后利用本文采用的改進后的聚類算法分別對每類標簽樣本進行聚類,得到每類樣本的若干聚類中心,在得到每類的聚類中心后,將結果中的聚類中心的均值點作為新的異類距離的中心點,通過對每一類樣本進行聚類可以不斷得到新的中心點以及每一標簽樣本的新的聚類結果.利用中心點的距離作為異類樣本之間的距離,當達到指定的迭代次數時停止迭代.

本方法的中心思想就是利用同類樣本的距離和異類樣本之間的距離對聚類算法進行改進,通過不斷的迭代使聚類效果趨于穩定.通過計算同類樣本內的聚類中心點來確定類內的中心點,以中心點來計算異類樣本之間的距離,并通過改進后的隸屬度公式和聚類中心公式來改進FCM聚類算法.改進后的算法不僅考慮到了類內的緊密度,還考慮到了類與類之間的稀疏程度.對傳統的聚類算法只考慮點到聚類中心的距離的思想進行了改進,具體算法的實現過程如下所示:

1)首先得到不同標簽樣本中心點的集合為C{(c1,c2,…,cj)},其中j代表樣本類的個數,隨后得到每一個標簽類的特征分別存入集合Xij{(xi1,xi2,…,xin)}其中i代表類內的圖片個數,j代表類的個數,n代表樣本特征維數.

3)利用改進后的距離測度更新聚類中心函數:

以及隸屬度函數:

4 改進FCM聚類的圖像標注方法

在本章節中,標注采用了3.2中的基于同類異類樣本的標注方法,是結合相同語義和不同語義樣本間的關系,得到新的距離測度并改進了傳統FCM聚類算法的聚類模型,將新的聚類算法利用到了圖像標注中.

本文之所以選擇模糊C均值聚類方法,是因為它相比傳統的硬聚類方法,會計算每一個樣本對所屬類的隸屬度.也就是對于數據集中的任意樣本,并非只有屬于某類或者不屬于某類兩種情況.

本文提出的聚類方法對比于傳統的標注方法,常規的基于聚類的標注方法是對整個數據集進行聚類,然后根據聚類結果對訓練圖像進行分類,再確定測試圖像所屬的類,最后統計類中的標注信息,即為測試圖像的標注詞.但是FCM聚類屬于一種無監督的聚類算法,在數據集較大時,分類效果并不理想.由于圖像底層特征的界限較為模糊,可能會將不同語義樣本的圖像分為一類,會將相同語義樣本分為不同類,這樣會影響標注效果.本文提出的改進的FCM聚類算法在此基礎上進行了改進,利用改進后的算法對每一個語義標簽類進行聚類,而不是在整體的數據集中進行聚類.

其標注過程分為以下幾個步驟:

步驟1.利用3.2改進后的標注方法對數據集中的每一個標簽樣本利用改進的FCM聚類分類,將不同語義的數據集劃分為不同的類,得到每一個類的聚類中心集合Cj{(ck1,ck2,…,ckn)}.

步驟2.得到測試圖像的底層特征,計算圖像到類的聚類中心的歐式距離,通過圖像到各個類的聚類中心的歐式距離與當前所在樣本中的聚類中心個數,式(16)是得到待標注圖像到各個類的平均距離并求得最小距離的一個類即為圖像的標注類.

(16)

步驟3.在確定了圖像的標注類以后,在改進后的FCM聚類結果的基礎上,找到測試圖像到類中聚類中心距離最近的一個類,統計類中出現最多的標注詞即為圖像的標注詞.

改進的FCM聚類標注算法,考慮到了測試集中圖像的語義信息,并對每個語義的樣本分別進行了聚類,避免了在不同標簽中的圖像相距離較小,相同標簽的圖像相距離較大的問題.

5 實驗數據與結果分析

5.1 實驗數據集以及特征選取

本方法采用的是常規的Corel5K數據集進行試驗,其中包含了50個語義類,每一個類中共有100個圖片,本實驗選取總共有374個標注詞的訓練集,使用了263個標注詞的測試集,庫中的每張圖片被標注了1-5個標注詞.其中訓練集4000張,驗證集500張,測試集500張.以及iaprtc12數據集,其中包含了41個類別,276個標注詞,20000張圖片.

本實驗采用mAP評價標準即平均標注準確率進行準確度計算,式(18)是標注詞相對每個圖片標注后準確率的平均值.首先式(17)先求出標注詞對于單個圖片的標注的準確率,再統計所有圖片對于當前標注詞的準確率的平均值,式(18)將所有標注詞的準確率統一取平均后得到最終的平均準確率.

(17)

(18)

本實驗選取的特征有HOG特征、SIFT特征以及HSV顏色直方圖特征.其中HOG特征選取32×32的塊大小,滑動步長為16×16,胞元大小為16×16,選用方向提取直方圖進行計算.SIFT特征將16×16邊長的區域劃分為16塊子區域,每塊區域是8個方向的直方圖統計結果.

5.2 對比實驗1

通過驗證可以證明,本方法有效提升了標注準確率,以下的對比實驗是比較在不同距離測度下,不同的特征對于標注準確率的影響.實驗證明,本方法所采用的改進FCM聚類方法能夠提升標注的準確性,表1表示Corel5K數據集的標注結果,表2為iaprtc12數據集的標注結果,其中DLD為本文提到的距離測度.

表1 Corel5K數據集的標注結果Table 1 Corel5K data set label results

表2 iaprtc12數據集的標注結果Table 2 Results of the iaprtc12 dataset

5.3 對比實驗2

本文采用的改進FCM聚類的標注方法是傳統分類標注方法的改進,本文采用的對比實驗是使用了如下幾種機器學習算法進行的,例如:支持向量機(SVM),FCM聚類算法,K-Means聚類算法,AdaBoost以及本文提出的改進的FCM聚類算法.在相同特征下對不同機器學習算法進行比較,使用的特征分別是HOG特征,SIFT特征以及HSV特征,并且在Corel5K和iaprtc12數據集中進行了測試.測試結果如圖1和圖2所示,其中DLD-FCM為本文所提出的改進FCM聚類的圖像標注方法.從實驗數據可以看出,該算法在Corel5K和iaprtc12數據集上均取得較好的聚類效果,在Corel5K使用HOG特征的mAP值達到了最高0.31,使用其余兩個特征的mAP值也比不同算法至少高出了0.05的mAP值,這就證明了該方法提出的聚類模型較傳統的聚類模型在圖像標注的準確率上有較大的提升,要高于傳統機器學習方法的準確率.在iaprtc12數據集中mAP的最高值為HOG特征達到的0.37,這相較其他類型的算法有了很大程度的提升,本數據集的計算結果大于Corel5K的原因是本數據集擁有更大的圖片集以及更多的標注詞.最終結果表明,本方法提出的標注方法相較于傳統聚類算法標注的結果更精確.通過在Corel5K和iaprtc12數據集上的測試,本標注方法比傳統的FCM聚類算法在各個特征下的標注準確率都有很大程度的提高,在相同特征下相比其他的機器學習算法也有明顯的提升.

圖1 Corel5K數據集的標注結果Fig.1 Annotation results for the Corel5K data set圖2 iaprtc12數據集的結果柱狀圖Fig.2 Histogram of the results of the iaprtc12 data set

6 結 論

本文中的改進的FCM聚類算法的圖像標注方法,是結合圖像的底層特征和圖像的語義信息進行改進的聚類方法,有效的解決了傳統FCM聚類算法對于數值點的判斷較為孤立和單一的缺點,結合了圖像的語義信息提升了標注的準確率,緩解了圖像的“語義鴻溝”問題.通過在Corel5K和iaprtc12中進行測試,使用不同測度以及不同標注模型進行對比實驗的結果發現,本文的改進FCM聚類有效的提升了標注的準確性.圖像的語義標簽在新的算法中起到了重要的作用.