基于SIFT特征點改進聚類的圖像檢索方法研究

張磊磊　陳麗芳

摘 要：由于SIFT特征點能對圖像局部特征進行合理、精確描述，有效使用SIFT特征點實現(xiàn)基于內(nèi)容的圖像檢索成為當前計算機視覺領(lǐng)域中的熱點問題。針對該問題，提出一種基于SIFT特征點的改進聚類的圖像檢索新方法。該方法包括圖像顏色轉(zhuǎn)換、特征點改進聚類算法，以及基于該算法的更有效的灰度直方圖構(gòu)建方法。與現(xiàn)有基于流光法的檢索方法相比，該方法能有效解決聚類后特征點分組不確定和依賴特征點顏色信息和空間信息權(quán)重的問題。從公共圖像庫上的實驗結(jié)果可以看出，該方法與現(xiàn)有方法相比具有較高的檢索精度。

關(guān)鍵詞：圖像檢索；SIFT特征點；聚類算法

DOI：10.11907/rjdk.171512

中圖分類號：TP317.4 文獻標識碼：A 文章編號：1672-7800（2017）009-0188-04

Abstract：Because SIFT feature points can represent the local feature of images effectively and accurately， how to realize content-based image retrieval by SIFT feature points is a hot issue in the computer vision. So， a novel image retrieval method based on the improvement combinatorial clustering of SIFT feature points is proposed. The proposed method consists of image color space transformation， improvement combinatorial clustering algorithm of SIFT feature points and effective local color histogram building approach. Compared with existing methods based on FLOW feature points and local color histogram， the proposed method can solve the problem that uncertain sets of feature points after clustering and existing methods are sensitive to the weight of position and the color of feature points. According to experimental results on public image database， it can be seen that the proposed method is more effective than existing methods.

Key Words：content-based image retrieval； SIFT feature points； improvement combinatorial clustering

0 引言

基于內(nèi)容的圖像檢索一直是計算機視覺領(lǐng)域的研究熱點[1-2]，其實現(xiàn)主要是通過抽取圖像特征來表示圖像內(nèi)容，通過計算特征間的相似性來表示兩幅圖像是否相似，從而找出與檢索條件最為相似的圖像。近年來，基于特征點的局部特征能有效描述圖像內(nèi)容[4]，因此被廣泛應用于圖像檢索中。

在已有特征點的基礎(chǔ)上，再通過局部顏色直方圖，既可實現(xiàn)對像素點顏色進行取值統(tǒng)計，又不會忽略像素點的空間分布特征?；谔卣鼽c組合聚類圖像檢索方法的主要思想是根據(jù)視頻流光算法或者SIFT算法得到圖像的特征點；然后根據(jù)聚類的思想[3]對特征點的顏色和空間位置進行聚類分組，得到一系列特征點集合；每個集合構(gòu)建一個局部顏色直方圖，通過計算局部顏色直方圖之間的距離來表示圖像間的相似性[4]。雖然這種方法具有一定的有效性，但仍存在以下問題：①圖像特征點聚類分組依賴像素點的顏色信息和空間信息，顏色信息和空間信息權(quán)重對結(jié)果的影響很大；②圖像特征點聚類后特征點分組結(jié)果不確定，計算圖像的相似度時影響比較大；③計算圖像相似性時，局部直方圖的距離算法沒有充分考慮特征點分組后的空間信息；④在聚類和匹配過程中沒有對算法進行優(yōu)化，匹配速度較慢。

針對上述存在的一些問題，本文基于SIFT特征點的空間信息聚類方法，在聚類時不用考慮顏色信息和空間信息的權(quán)重問題，而且匹配結(jié)果是確定的。計算圖像相似性時，充分考慮分組后直方圖的空間信息，同時對聚類和局部灰度直方圖匹配算法進行了一定的優(yōu)化。實驗結(jié)果表明，本文方法具有一定的有效性和速度優(yōu)勢。

1 基于SIFT特征點改進聚類的檢索方法

SIFT算法由DAVID G L于1999年提出[5]，并于2004年進行了發(fā)展和完善[6]，MIKOLAJCZYK[7]對多種描述子進行實驗分析，結(jié)果證實了當圖像進行旋轉(zhuǎn)、平移、尺度縮放、仿射變換時，SIFT特征具有很好的穩(wěn)定性和魯棒性。

基于SIFT特征點改進聚類的檢索方法包含5個步驟：①圖像顏色轉(zhuǎn)換；②使用SIFT算法提取圖像的特征點；③使用改進聚類算法將特征點進行分組；④統(tǒng)計每個分組特征點的灰度值，構(gòu)建一個灰度直方圖，該直方圖為圖像的局部灰度直方圖；⑤根據(jù)直方圖計算圖像之間的距離，返回匹配結(jié)果。

1.1 顏色轉(zhuǎn)換

顏色是檢索系統(tǒng)中最常用的圖像特征。顏色表示模型有很多種，數(shù)字圖像一般使用RGB表示模型存儲其二進制數(shù)據(jù)，其可分辨色差是非線性的。HSV顏色表示模型是基于人眼對色彩的識別，是一種從視覺角度定義的顏色表示模型。本文在特征點提取之前，首先將圖像從RGB模型轉(zhuǎn)為HSV模型。endprint

HSV顏色模型中，H表示色調(diào)，S表示飽和度，V表示亮度。RGB顏色表示模型與HSV顏色表示模型之間的轉(zhuǎn)換公式如下：T=arccos（R-G）+（R-B）2（R-G）2+4（R-B）（R-G）

H=T，B≤G

2π-T，B>G

S=max（R，G，B）-min（R，G，B）max（R，G，B）

V=max（R，G，B）255 其中，R，G，B∈[0～255]，由公式得到H、S、V的值，H∈[0～360]，S∈[0～1]，V∈[0～1]。按照上式轉(zhuǎn)換圖片顏色模型。

1.2 圖像特征點提取

圖片顏色轉(zhuǎn)換之后，使用SIFT算法提取圖像的特征點。傳統(tǒng)SIFT算法主要分為4個步驟：①檢測尺度空間極值點；②精確定位極值點；③為每個關(guān)鍵點指定方向參數(shù)；④關(guān)鍵點描述子的生成。

SIFT特征點提取時使用OpenCV庫中的SIFT算法對圖片進行處理，得到特征點后使用聚類算法進行分組。

1.3 改進的聚類算法

傳統(tǒng)聚類算法步驟如下：

輸入：聚類對象集合A={a1，a2，…，an}，其中每個對象ai由m個特征向量表示，ai=（v1i，v2i，…，vmi）；簇中心數(shù)目k（k

輸出：k個簇中心。

流程如下：

（1）給出k個初始的簇中心與算法迭代次數(shù)的變量t：c1=d1，c2=d2，…，ck=dk

t=0 （2）計算A中每個對象到各簇中心的距離。若ai=（1≤i≤n）與cj（1≤j≤k）的距離值最小，則ai屬于第j個簇。

（3）一輪分簇結(jié)束后，再計算簇中心，記錄k個新的簇中心。

（4）t=t+1，若t

（5）新舊簇中心二者比較，若不相同返回步驟（2）；若相同則算法收斂，算法結(jié)束。

傳統(tǒng)聚類算法中，初始簇中心是隨機選取的，同一個圖片特征點在兩次聚類后，特征點分組情況是不同的，如圖1所示，結(jié)果導致最后的檢索查全率和查準率不穩(wěn)定。

針對以上問題，本文方法中，提出了確定聚類初始簇中心的新方法。

計算集合A的中心點，即平均值cm；集合對象A中距離cm最遠的對象d1為第一個初始簇中心c1；集合對象中距離c1最遠的對象d2為第二個初始簇中心c2；集合對象中距離c1和c2的中心點最遠的對象d3為第三個初始簇中心c3；重復上一步直至找到第k個初始簇中心ck。

對特征點進行聚類時，使用像素點的位置信息，若pi表示第i個特征點，有：pi=（xi，yi） 其中，xi，yi表示pi的位置信息。

若聚類對象ai和第j類中心cj分別為ai=（v1i，v2i）和cj=（v1j，v2j），則二者的歐氏距離為：d（ai，cj）=（v1i-v1j）2+（v1j-v2j）2 分組時，本文方法的好處是每次初始化簇的中心是確定的，分類之后的結(jié)果是唯一的，圖像檢索的結(jié)果是確定的，而且避免了聚類后結(jié)果匹配的不確定性。同時，本文方法計算特征點距離時只考慮空間信息，避免檢索結(jié)果對權(quán)重的依賴。本文算法對同一個圖片聚類后結(jié)果如圖2所示，這說明基于改進聚類算法的檢索方法可以克服現(xiàn)有方法中存在的問題。

1.4 相似度計算方法

當一幅圖像表示為多個局部顏色直方圖時，圖像間相似性的計算過程為：計算對應的兩個直方圖之間的距離，再將多個距離值進行相加，距離值的總和即可用來表示兩幅圖像間的相似性，該值越小，圖像間的相似性越小。

在文獻[4]流光子算法特征點組合聚類算法中，通過計算局部灰度直方圖之間的歐氏距離，若兩個直方圖之間的距離最小，則二者存在對應關(guān)系。將所有具有兩兩對應關(guān)系的直方圖間的距離進行累加，最終得到兩個圖像間的距離，以此表示兩幅圖像的相似性，值越小，相似度越大。然而計算過程中會出現(xiàn)一幅圖像里多個局部灰度直方圖匹配另一個圖像里一個局部灰度直方圖的情況。如圖3所示，在兩幅圖為不同類別的情況下，由于沒有充分考慮局部灰度直方圖的空間信息，在計算圖像相似性時，局部灰度直方圖會發(fā)生局部匹配，一部分局部直方圖沒有參加匹配，導致錯誤的匹配結(jié)果。

為解決這一問題，在本文方法中，使用改進的圖像距離計算算法。假設(shè)待檢索圖像與庫中的一幅圖像可以分別表示為兩個直方圖的集合：Hi=（h1i，h2i，…，hni）和Hj=（h1j，h2j，…，hnj） 則二者間距離：

d1為Hi和Hj里直方圖間歐氏距離最小值，去掉集合中兩個匹配最小值的直方圖，得到兩個新的直方圖集合H1i和H1j；d2為H1i和H1j里直方圖間歐氏距離最小值，去掉兩個匹配最小值的直方圖，得到兩個新的直方圖集合H2i和H2j；重復上述步驟最終得到dn；累加直方圖距離得到圖像距離D：D=d1+d2+…+dn 圖4為從圖片庫中選擇一幅圖使用文獻[4]中的圖像距離計算方法匹配后的結(jié)果。由于沒有充分考慮圖像局部灰度直方圖之間的空間信息，匹配結(jié)果中出現(xiàn)了錯誤的匹配。

圖5為本文方法檢索后返回的前十幅圖的結(jié)果，由于充分考慮了圖像的局部灰度直方圖之間的空間信息，較文獻[4]中方法，本文方法更具有效性。

1.5 算法優(yōu)化

圖像匹配過程主要分為前期圖像預處理和后期圖像距離計算并返回結(jié)果兩部分。前期圖像預處理主要包括SIFT特征點提取和特征點聚類分組，后期匹配結(jié)果使用K近鄰算法返回前K個距離最小的有效值。

針對以上情況，主要從以下兩方面進行算法優(yōu)化：①SIFT特征點提取時，只計算特征點的坐標值，忽略特征點描述信息的計算；②聚類算法和K近鄰算法中排序算法占了很大一部分，基于此，提出改進的二分法插入排序算法。

傳統(tǒng)二分法插入排序在插入第i個元素時，對前面的0～i-1元素進行折半，先與它們中間的那個元素相比，如果小，則對前半再進行折半，否則對后半進行折半，直到left>right，然后將第i個元素前1位與目標位置之間的所有元素后移，再把第i個元素放在目標位置上。

本文提出的二分插入排序算法是：①在第j個元素成功插入后記錄其在有序數(shù)組中的位置lj，其中l(wèi)eft≤lj≤right；②插入第j+1個元素時，先與第j個元素比較大??；如果小，使right=lj；如果大，使left=lj；③如果right≥left，在left和right之間繼續(xù)二分查找，否則找到元素待插入位置lj+1；④將lj+1以及后面的元素向后依次移位，將第j+1個元素插入該位置。

通過以上兩部分算法優(yōu)化，可以減少不必要的計算步驟，能夠有效提高匹配速度。

2 實驗結(jié)果對比

為了驗證本文方法的有效性，在公共圖像庫上分別用流光法算法和本文算法來實現(xiàn)圖像檢索，通過檢索結(jié)果的比較來驗證本文方法的優(yōu)越性。實驗中，所選公共圖像庫為Simplicity系統(tǒng)評測時所采用的圖像庫[8]，該圖像庫包含了取自Corel圖像庫的1 000幅圖像，這些圖像來自不同的10個類別，本文為了客觀地對兩種檢索方法進行對比，將圖像庫中的每一幅圖像都作為檢索條件，執(zhí)行一次檢索過程，最后統(tǒng)計1 000次檢索后的平均檢索精度。

整個實驗包括兩個部分，其中第一部分是比較兩種檢索方法的平均性能，第二部分比較每一類的檢索性能。

實驗1 兩種檢索方法的性能比較

在該部分實驗中，每幅圖先用SIFT算法提取圖像的特征點，然后特征點通過改進聚類算法分配到3個集合中。圖像檢索結(jié)果中，排序靠前的圖像往往被視為有效結(jié)果。實驗中，分別將返回圖像的前十到前五十位作為有效檢索結(jié)果，并計算檢索精度來進行性能評價。假設(shè)有效結(jié)果數(shù)目為N，其中正確結(jié)果數(shù)目為Ne，則檢索精度P為：P=（NeN）×100% 如圖6所示，基于SIFT特征點改進聚類的平均性能最優(yōu)，原因在于該算法對特征點的分組更加合理有效。而且本文匹配正確率隨著檢索結(jié)果數(shù)量的增加而比較穩(wěn)定，表明本文對圖像間的距離計算方法更合理有效。

實驗2 每一類圖像的檢索性能

利用改進聚類方法對特征點分簇時，只考慮了特征點的空間信息。針對TOP10結(jié)果計算檢索精度，每類圖像所對應的檢索精度平均值由表1給出。其中，F(xiàn)-MAX為文獻[4]中每類匹配的最大值，F(xiàn)-MEAN為文獻[4]中每類匹配的平均值。不難看出，針對大多數(shù)類別而言，在使用SIFT算法提取特征點時，僅考慮空間信息時，其平均搜索精度優(yōu)于使用流光子算法。避免了文獻中既要考慮空間信息又要考慮顏色信息，并且檢索結(jié)果依賴于空間信息和顏色信息之間的權(quán)重。

實驗二的結(jié)果驗證了基于SIFT特征點改進聚類的方法中，聚類分組時使用SIFT特征點的空間信息在圖像檢索中仍然具較好的有效性。為了進一步提高檢索性能，適當使用特征點的其它描述信息值得進一步研究。

實驗3 檢索速度比較

算法優(yōu)化之前，由于前期SIFT特征點提取與聚類分組和后期匹配的影響，從檢索開始到返回結(jié)果，耗費時間太長，用戶體驗較差。

在原來算法基礎(chǔ)上通過改良SIFT特征點提取算法和改進的二分插入排序算法。圖7結(jié)果表明，在不影響匹配正確率的情況下，能有效提高檢索速度。

3 結(jié)語

基于SIFT特征點改進聚類的圖像檢索方法，是一種以局部顏色直方圖作為圖像特征的檢索方法。與文獻[4]相比，該方法包含3個創(chuàng)新點：①使用SIFT特征點代替流光子特征點；②使用改進的聚類算法；③使用改進的圖像局部直方圖距離算法；④對匹配過程中算法進行了一定的優(yōu)化。

本文在公共圖像庫上進行了實驗驗證分析，從最終結(jié)果的對比分析可以看出，僅僅以局部顏色直方圖作為圖像特征時，本文方法在檢索正確率和檢索速度方面要優(yōu)于現(xiàn)有方法。

在后續(xù)研究工作中，為了進一步提高檢索性能，可以考慮使用特征點的其它描述信息，并且，在不影響檢索性能的情況下，重點考慮進一步提高檢索速度。

參考文獻：

[1] SMEULDERS A， WORRING M， SANTINI S， et al. Content-based image retrieval at the end of the early years [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（12）：1349-1380.

[2] LEW M S， SEBE N， DJERABA C， et al. Content-based multimedia information retrieval： state of the art and challenges[J]. ACM Transactions on Multimedia Computing， Communications and Applications，2006，2（1）：1-19.

[3] 孫吉貴，劉杰，趙連宇.聚類算法的研究[J].軟件學報，2008，19（1）：48-61.

[4] 齊恒，李克秋，申彥明，等.基于特征點組合聚類的圖像檢索新方法[J].大連理工大學學報，2014（4）：477-481.

[5] DAVID G L. Object recognition from local scale-invarint features[C]. International Conference on Computer Vision，1999：1150-1157.

[6] DAVID G L. Distinctive image features from scale-invariant key-points[J]. International Journal of Computer Vision，2004，60（2）：91-110.

[7] MIKOLAJCZYK K， SCHMID C. A performance evaluation of local descriptors [J].IEEE Transactions on Pattern Analysis，2008.

[8] WANG J Z， LI JIA， WIEDERHOLD G. SIMPLIcity： semantics-sensitive integrated matching for picture libraries[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23（9）：947-963.

（責任編輯：孫 娟）endprint