一種基于改進SURF和K-Means聚類的布料圖像匹配算法

張雪芹, 劉遠遠, 曹逸塵, 張鵬飛

(華東理工大學(xué)信息科學(xué)與工程學(xué)院,上海 200237)

一種基于改進SURF和K-Means聚類的布料圖像匹配算法

張雪芹, 劉遠遠, 曹逸塵, 張鵬飛

(華東理工大學(xué)信息科學(xué)與工程學(xué)院,上海 200237)

計算機圖像智能處理技術(shù)為服裝設(shè)計師開展設(shè)計、啟發(fā)靈感提供了方便和可能。通過提取布料圖像的SURF特征可以實現(xiàn)布料圖像形狀分析,但由于SURF特征維數(shù)高、特征提取是基于灰度圖進行,因此存在匹配速度慢、匹配結(jié)果不夠符合人眼視覺特點的問題。本文提出了基于小波變換的自適應(yīng)SURF特征提取算法和基于K-Means聚類的布料圖像顏色分析方法。通過融合圖像形狀特征、顏色特征,加快了布料圖像匹配速度,使布料圖像的匹配結(jié)果更加符合人眼視覺感受。在8種不同類型布料圖像上的實驗驗證了該算法的有效性。

布料圖像匹配; SURF特征; 小波變換; K-Means聚類

近年來,圖像處理技術(shù)越來越多地運用到紡織領(lǐng)域中,如織物外觀性能的測試、織物的密度測定等。對于服裝設(shè)計師而言,當他們根據(jù)已知的布料圖案(比如來自于街拍或時裝發(fā)布會的模特照片)選取服裝設(shè)計布料時有兩種需求:一是希望在布料庫中找到近乎相同的布料;二是希望在布料庫中找到圖案類別、圖案空間分布或顏色相近的布料,以啟發(fā)其設(shè)計靈感。若靠人工從成千上萬的布料圖像庫中找到相關(guān)圖片是極其耗時和困難的。計算機圖像的智能分析技術(shù)為該應(yīng)用提供了可能。

常見的圖像匹配方法有兩種:基于灰度的圖像匹配和基于特征的圖像匹配?；诨叶鹊膱D像匹配[1]根據(jù)全局最優(yōu)化像素間的相似度來度量兩幅圖像的匹配度,如平均絕對差 (MAD)、序貫相似性檢測 (SSAD)、歸一化灰度組合相關(guān) (NIC)和去均值歸一化互相關(guān) (NNPROD)等?；谔卣鞯膱D像匹配[2]根據(jù)提取的圖像特征點來實現(xiàn)圖像之間的匹配,如Forstner、Harris、Moravec、SIFT、SURF等。

Lowe等[3]提出將SIFT算法應(yīng)用于圖像配準、圖像拼接、人臉識別等領(lǐng)域,但計算量較大、算法較復(fù)雜以及花費時間長。Bay等[4]提出的SURF算法在速度上較SIFT算法有明顯的優(yōu)勢,但是正確率低、誤匹配點多。針對上述問題,Yanke等[5]提出了PCA-SIFT算法，采用主成分分析法實現(xiàn)對特征描述符的降維;Mikolajczyk等[6]提出了GLOH(Gradient Location Orientation Histog-ram)算法進一步增強了特征描述符的獨特性;Morel等[7]提出ASIFT(Affine-SIFT)抗仿射SIFT變換用于實現(xiàn)全仿射不變性。

針對輔助服裝設(shè)計師選取布料、啟發(fā)設(shè)計靈感這一目的,在分析布料圖像特點的基礎(chǔ)上,本文提出了基于小波變換的自適應(yīng)SURF特征提取方法和基于K-Means聚類的布料圖像顏色提取方法,通過融合圖像的形狀和顏色特征實現(xiàn)圖像間的匹配,提高了布料圖像匹配速度,并使匹配結(jié)果更符合人眼視覺特性。該算法與SIFT、SURF等算法相比在匹配速度和正確率上都有較好的改善。

1 算法簡介

1.1 SURF算法

SURF算法是Bay等[8]提出的基于特征的圖像匹配算法。其主要思想是:采用離散化和裁剪的DOH(Determinant of Hessian)來獲取特征點,用 Harr小波模板提取特征,并采用積分圖像來加速計算DOH和Haar模板響應(yīng)。SURF算法主要包含特征點檢測和特征描述子兩個部分。

1.1.1 特征點檢測

(1) 積分圖像。積分圖像可以快速實現(xiàn)方框卷積濾波的功能。設(shè)X=(x,y)表示圖像I上的某一像素點,則其積分圖像I(X)定義為

(1)

如圖1所示,以A、B、C、D為頂點的矩形區(qū)域像素值的和為S=I(D)-I(B)-I(C)+I(A)。

圖1 積分圖像示意圖

引入積分圖后,矩形區(qū)域內(nèi)像素值的計算與圖像的坐標值無關(guān),只需根據(jù)矩形的4個頂點坐標即可得到,極大地提高了計算速度。

(2) Hessian 矩陣檢測極值點。圖像I上的一點X=(x,y)在尺度σ下的Hessian矩陣H(X,σ)定義為

(2)

其中,Lxx、Lyy、Lxy分別描述了圖像在x、y及x-y方向上的高斯濾波。用方框濾波代替二階高斯濾波,則可用近似Hessian矩陣行列式det(Happrox)來估計H。

(3)

式中,Dxx、Dyy、Dxy分別表示圖像在x、y及x-y方向上的方框濾波。若行列式的值大于0,則可確定該點為局部極值點。然后在尺度空間金字塔3×3×3的立體鄰域內(nèi)進行非極大值抑制,只有當該局部極值點比上一尺度、下一尺度及本尺度周圍的26個鄰域值都大或者都小時,該局部極值點成為特征點。

1.1.2 特征描述子

(1) 確定特征點主方向。以特征點為圓心,6s(s為特征點尺度)為半徑畫圓,計算圓內(nèi)的所有像素點在x和y方向上的Haar小波響應(yīng)。然后,以特征點為圓心,以60°范圍的扇形區(qū)域為窗口,對整個圓形區(qū)域進行遍歷,以扇形區(qū)域內(nèi)的所有像素點的Haar小波響應(yīng)之和作為新的矢量，遍歷一周,選擇最大矢量的方向作為該特征點的主方向。

1.2 小波變換

1.2.1 概述Mallat等[9]提出了多分辨率圖像分解的小波表示。小波變換的基本思想:將基本小波經(jīng)過伸縮和平移,分解成一系列具有不同空間分辨率、不同頻率及不同方向特性的子帶信號,實現(xiàn)對信號時間、頻率的局部化分析。由于圖像為二維離散信號,這里應(yīng)用到的小波變換為二維離散小波變換。

1.2.2 二維小波函數(shù) 令φ(x)為一維尺度函數(shù),ψ(x)為一維小波函數(shù),則其小波基的離散化形式為

(4)

式中:m為伸縮因子;n為平移因子。對于二維空間來說,其尺度函數(shù)為

(5)

小波函數(shù)為

(6)

式中:n1、n2分別為x和y方向的平移因子;上標H、V、D分別代表水平、垂直和對角斜線方向。

1.2.3 二維圖像的離散小波分解 對于一幅圖像I(x,y)來說,設(shè)其原始圖像的尺度為1。在每個層次的變換中,圖像都被分成4個大小為原圖1/4的子頻帶信號。則對于第j層(j = 0,1…,K,K為設(shè)定變換的層次數(shù)),其4個子頻帶信號可表示為

(7)

式中:IjL(x,y),IjH(x,y),IjV(x,y),IjD(x,y)分別表示圖像I(x,y)在分辨率j上的低頻分量,以及在水平、垂直和對角3個方向的高頻分量。

1.3RANSAC算法

RANSAC算法[10]常用于剔除基于特征圖像匹配中的誤匹配的特征點。RANSAC算法的具體步驟如下:

假設(shè)數(shù)據(jù)集合S是由n對匹配點組成的,由于本文中使用的是仿射變換模型,所以至少需要3對匹配點數(shù)據(jù)方可求出模型。

初始化:誤差閾值Def_T,預(yù)設(shè)閾值Pre_T;

(1) 從數(shù)據(jù)集合S中隨機選取3對不共線的初始匹配點,利用最小二乘法得到其初始的變換矩陣H;

(2) 對其余的n-3對匹配點,分別計算其與模型之間的距離,若小于誤差閾值Def_T,則認為該特征點為匹配對的內(nèi)點(Inliers),否則為外點(Outliers),統(tǒng)計內(nèi)點個數(shù)num;

(3) 重復(fù)步驟(1)、步驟(2),當num的值不再變化且大于預(yù)設(shè)閾值Pre_T時,對應(yīng)的內(nèi)點集合即為最大內(nèi)點域,此時的變換矩陣H為最優(yōu)模型矩陣。

2 基于小波變換和SURF的圖像匹配

2.1WtSurf圖像匹配算法

SURF算法能夠較好地提取圖像的形狀特征,實現(xiàn)圖像與圖像間的形狀匹配。但是由于其特征維數(shù)較高,因此存在匹配速度慢的問題。針對以上問題,本文提出了基于小波變換和SURF的圖像匹配算法(WtSurf)。

WtSurf算法首先對圖像進行小波分解獲得其低頻分量,然后提取低頻圖像的SURF特征,最后通過交叉過濾法和RANSAC算法剔除誤匹配特征點,以匹配到的特征點對數(shù)占待測圖片特征點數(shù)的比例作為圖像間相似度的判據(jù)。由于經(jīng)過RANSAC算法進一步篩選匹配對后,會使得某些圖片的匹配對數(shù)過少,所以算法最終采用保留交叉匹配的結(jié)果,對經(jīng)RANSAC算法篩選保留的匹配對,通過加大判別權(quán)重來綜合計算圖像間的相似度。

WtSurf算法的流程圖如圖2所示。

圖2 WtSurf算法流程圖

算法步驟如下:

Step 1 待測圖像和圖像庫中的目標圖像通過小波變換分別得到其低頻圖像Q和T;

Step 2 分別提取圖像Q和T的SURF特征,得到特征點集Q={q1,q2,…,qn1}和T={t1,t2,…,tn2},按圖像遍歷順序分別為兩個特征點集中的特征點建立索引號,其中,n1和n2分別為待測圖像和目標圖像的特征點數(shù);

Step3 對特征點集Q和T做交叉匹配。即,雙向計算Q中所有特征點和T中所有特征點的歐式距離。如果Q中某個特征點qx與T中某個特征點ty彼此為最近點,且索引號相同,則保留該特征點對。經(jīng)過交叉匹配分別得到匹配的特征點集Q*={q1*,q2*,…,qm1*}和T*={t1*,t2*,…,tm1*},其中,m1為雙向匹配得到的特征點對數(shù);

Step4 用RANSAC算法進一步剔除特征點集Q*和T*的誤匹配特征點組,得到FQ={fq1,fq2,…,fqm2}和FT={ft1,ft2,…,ftm2},其中,m2為最終匹配得到的特征點對數(shù);

Step5 計算Vs=k1×m1/n1+k2×m2/n1,把Vs的值作為度量圖像間形狀的相似度的依據(jù),其中,k1、k2為權(quán)值。

2.2 自適應(yīng)WtSurf圖像匹配算法(AWtSurf)

SURF算法的可調(diào)參數(shù)主要有組數(shù)(nOctaves)、層數(shù)(nOctaveLayer)和Hessian行列式閾值(Hessian threshold)。其中,組數(shù)和層數(shù)決定了方框濾波模板的大小,即從哪些尺度空間中提取特征點,Hessian行列式閾值的大小表征圖像中對應(yīng)位置特征的強弱程度。綜合考慮圖像的特點及應(yīng)用場景選擇組數(shù)、層數(shù)和Hessian行列式的閾值,可使算法有更好的效率和穩(wěn)定性。

實驗發(fā)現(xiàn),由于布料圖像的千差萬別,固定的Hessian行列式閾值很難滿足所有布料圖像特征提取的需求。比如當采用算法默認的Hessian行列式閾值100時,對于波點類型的布料圖像,易出現(xiàn)因提取到的特征點數(shù)過少而導(dǎo)致匹配失敗。但是簡單地降低Hessian行列式閾值,對于像蕾絲、花類型的布料圖像來說,不僅不會提高布料圖像的匹配能力,反而增加了布料圖像匹配時間。因此,本文提出在實驗確定組數(shù)和層數(shù)的基礎(chǔ)上,在WtSurf算法的Step 2,采取動態(tài)設(shè)定Hessian行列式閾值方法提取特征點集。其流程如圖3所示。

3 基于顏色聚類和特征的圖像匹配

3.1 概述

基于SURF算法可以實現(xiàn)圖像間的形狀特征的匹配,但是由于SURF算法是基于灰度圖像提取形狀特征,因此匹配到的圖像間沒有顏色相似度度量。這就造成比如像蕾絲和印花布料,盡管前者顏色單一,后者顏色豐富,但是當兩種布料上圖案一致時 (比如都有牡丹花),那么在基于SURF特征的匹配中就會呈現(xiàn)很高的相似度(如圖4所示),因而會將相關(guān)布料推送給設(shè)計師。但是在實際應(yīng)用場景中,設(shè)計師并不認為這兩種布料是相似的。此外,當待測圖片在圖片庫中找不到相似的圖案時,設(shè)計師往往希望推送給他們的是在空間分布或顏色上相近的布料圖像。

圖3 動態(tài)設(shè)定Hessian行列式閾值流程圖

圖4 形狀相似布料的不同類型的圖像

針對上述問題,本文提出了基于K-Means聚類的顏色種類提取和顏色直方圖的顏色特征提取方法,結(jié)合布料圖像形狀特征,最終實現(xiàn)布料圖像匹配。由于HSV顏色空間比較符合人眼的視覺特性,所以本文的顏色特征提取基于HSV顏色空間。

3.2 基于K-Means的顏色聚類

給定一幅圖像P,尺寸大小為M×N,其每個像素xi(i=1,2,…,M×N)在HSV顏色空間具有H、S、V 3個分量?；贙-Means的顏色聚類的流程如下:

初始化:設(shè)定聚類數(shù)K;

Step 1 對于P來說,從中任取K個點Ck(k=1,2,…,K)作為初始聚類中心;

Step 2 分別計算圖像中其他數(shù)據(jù)點到質(zhì)心Ck(k=1,2,…,K)的歐式距離,并將其歸類到與其距離最近的質(zhì)心類;

Step4 聚類結(jié)束,得到最終聚類中心Ck*;

Step5 根據(jù)聚類中心點及HSV顏色參照表,得到每幅圖像的顏色種類數(shù)。

3.3C_AWtSurf圖像匹配算法

C_AWtSurf算法首先采用K-Means算法在HSV顏色空間進行顏色聚類,提取布料圖像的顏色種類,將與待匹配布料圖像顏色種類數(shù)差別較大的布料圖像予以剔除。對于剔除后的圖像,計算兩幅圖像的HSV空間顏色直方圖,把圖像間顏色直方圖的歐氏距離作為度量兩幅圖像顏色相似度的依據(jù)。

算法描述如下:

Step1 待測圖像和圖像庫中的目標圖像通過小波變換得到其低頻圖像Q和T;

Step2 對圖像Q和T在HSV空間進行顏色聚類及顏色直方圖計算,得到圖像Q和T的顏色種類數(shù)Nq和Nt及其HSV顏色直方圖Histq和Histt,其中Histq={hq(0),hq(1),…,hq(BIN)},Histt={ht(0),ht(1),…,ht(BIN)},BIN為劃分的顏色區(qū)間數(shù);

Step3 若Nq-Nt>1,則判定兩幅圖像不匹配;否則,計算Histq和Histt的歐氏距離Vc來表征圖像之間的顏色相似度:

(8)

算法流程如圖5所示。

圖5 基于顏色聚類的圖像匹配流程圖

3.4 融合形狀和顏色特征的圖像匹配度

對設(shè)計師而言,希望匹配到的圖像既圖案相似又顏色相近,以圖案相似為主,顏色相近為輔。因此算法考慮優(yōu)先輸出形狀和顏色均較相似的圖像;而當顏色不相似時,則輸出形狀相似度較高的圖像,以減少視覺干擾。

假設(shè)Score表示融合顏色特征和形狀特征后的相似度值,Vc表示顏色特征匹配度,Vs表示形狀特征匹配度,則設(shè)定相似度閾值Similarity。定義當兩幅圖像顏色不相似時(Vc< Similarity),Score=Vs;當兩幅圖像顏色相似時(Vc≥Similarity),Score=wcVc+wsVs,其中wc、ws分別為顏色和形狀的權(quán)重。

4 實驗數(shù)據(jù)及分析

4.1 實驗數(shù)據(jù)與環(huán)境描述

實驗中的布料圖像來自于某服裝公司,選取891張樣本,其中包括蕾絲、豹紋、波點、方格、條紋、幾何、花、千鳥格共8類,如圖6所示,每種類型的圖片數(shù)量如表1所示。

表1 布料庫描述

圖6 布料圖像類型示例圖

實驗的操作系統(tǒng)為Windows7,開發(fā)環(huán)境為Visual Studio2010,圖像處理開源庫為OpenCV2.4.11,CPU 1.7 GHz,內(nèi)存8 GB。

4.2 布料圖像匹配的評價機制

由于本應(yīng)用主要是為服裝設(shè)計師挑選布料提供參考,因此采用主觀評價法對算法輸出結(jié)果進行評價。根據(jù)調(diào)研,設(shè)計評價指標為:{布料類型,圖案的空間分布,形狀,顏色},劃分評分等級為:{完全相同,比較相似,一般相似,較大不同,完全不同},兩幅圖像在這4個方面完全匹配時得1分。評分機制如表2所示。

表2 主觀評分機制

4.3 實驗結(jié)果及分析

4.3.1 實驗1 本實驗主要是為了確定AWtSurf算法中的兩個參數(shù):組數(shù)(nOctaves)與層數(shù)(nOctaveLayers)。當采用不同的組數(shù)和層數(shù)時,提取到的不同類型布料圖像的特征點數(shù)如表3所示。

表3 不同組數(shù)和層數(shù)時提取的SURF特征點數(shù)

由表3可知,當固定SURF參數(shù)中的Hessian行列式閾值和層數(shù)時,組數(shù)分別取1、3、5,當組數(shù)大于3后,提取的圖像特征點數(shù)不再變化。當固定SURF參數(shù)中的Hessian行列式閾值和組數(shù)時(此時組數(shù)設(shè)定為3),層數(shù)分別取3、5、7,當層數(shù)大于5后,提取圖像特征點數(shù)的增量趨緩,層數(shù)為5時提取到的圖像特征點數(shù)是層數(shù)為7時提取到的圖像特征點數(shù)的91.5%。綜合考慮算法的有效性,實驗中將組數(shù)設(shè)定為3,層數(shù)設(shè)定為5。

4.3.2 實驗2 為了驗證本文算法的有效性,實驗比較了SIFT、SURF、WtSift、WtSurf、AWtSurf和C_AWtSurf算法。其中,AWtSurf和C_AWtSurf采用自適應(yīng)動態(tài)調(diào)節(jié)Hessian行列式閾值的算法,更新步長m為10,特征點閾值為40。經(jīng)過實驗比較,相似度閾值Similarity=0.8,顏色權(quán)重wc=0.2,形狀權(quán)重ws=0.8(由于篇幅限制,不同參數(shù)的匹配評分結(jié)果不再一一列出)。對于C_AWtSurf算法,匹配速度和評價得分結(jié)果如表4、5及圖7、8所示。

從表5、表6可以看出,在匹配準確率上,對于蕾絲、波點、條紋、幾何類型的布料圖像,C_AWtSurf算法效果最好；對于豹紋、千鳥格類型的布料圖像,WtSift算法效果最好；對于方格、花類型的布料圖像,SURF算法效果最好。綜合來看,C_AWtSurf算法匹配準確度最高。在時間上,C_AWtSurf速度最快,是SIFT算法的11.3倍,是SURF算法的4.6倍;綜上分析可知,C_AWtSurf算法匹配準確率最高、匹配速度最快。

表4 不同算法下布料圖像的匹配評分

表5 不同算法下布料圖像的匹配時間

圖7 不同算法下布料圖像的匹配評分

圖8 不同算法下布料圖像的匹配時間

為了更加直觀地觀測實驗結(jié)果。圖9給出了部分匹配結(jié)果。由于篇幅原因,這里僅給出了3種類型布料中匹配度較高的前5張。

圖9 匹配結(jié)果實例

每種類型布料圖像的第1張為待匹配布料圖像,后續(xù)5張為匹配推送結(jié)果。第2張為匹配出的待測布料在圖庫中的原圖,后續(xù)為與待測布料顏色或者形狀相似的圖片。結(jié)果表明,C_AWtSurf算法不僅能夠準確地找出相同布料,同時能夠推送相似圖像,既滿足了設(shè)計者在布料庫中精準尋找布料的需求,又可以啟發(fā)其設(shè)計靈感。

5 結(jié) 論

為了輔助服裝設(shè)計師選取布料、啟發(fā)設(shè)計靈感,針對不同類型的布料圖像,提出了基于小波變換的自適應(yīng)SURF特征提取方法和基于K-Means聚類的圖像顏色提取方法。通過融合圖像的形狀和顏色特征,使得匹配結(jié)果更加符合人的視覺特性。實驗結(jié)果驗證了AWtSurf算法和C_AWtSurf算法的有效性。

[1]吳強,侯樹艷,李旭雯.融合圖像灰度信息與邊緣特征的快速匹配算法[J].信號處理,2013(2):268-273.

[2]HAUAGGE D C.Image matching using local symmetry features[C]//IEEE Conference on Computer Vision and Pattern Recognition.USA:IEEE,2012:206-213.

[3]CHIU L C,CHANG T S,CHEN J Y,etal.Fast SIFT design for real-time visual feature extraction[J].IEEE Transactions on Image Processing,2013,22(8):3158-3167.

[4]PANG Y,LI W,YUAN Y,etal.Fully affine invariant SURF for image matching[J].Neurocomputing,2012,85(3):6-10.

[5]LI Zhong,XIN Binchao,CHEN Yueyue.An efficient parallel PCA-SIFT algorithm for multi-core processor[J].Journal of National University of Defense Technology,2012,34(4):103-107.

[6]WANG B,LI Y,LU Q,etal. Image registration algorithm based on modified GLOH descriptor for infrared images and electro-optical images[J].Recent Advances in Computer Science and Information Engineering,2012,5:365-370.

[7]OJI R.An automatic algorithm for object recognition and detection based on ASIFT key points[J].Signal & Image Processing,2012,3(5):29-39.

[8]FENG Qi,XU Weihong,ZHANG Xuping.Research of image matching based on improved SURF algorithm[J].Telkomnika Indonesian Journal of Electrical Engineering,2014,12(2):1395-1402.

[9]AGARWAL S,VERMA A K,SINGH P.Content based image retrieval using discrete wavelet transform and edge histogram descriptor[C]//2013 International Conference on IEEE Information Systems and Computer Networks.USA:IEEE,2013:19-23.

[10]CHENG L,LI M,LIU Y,etal.Remote sensing image matching by integrating affine invariant feature extraction and RANSAC[J].Computers & Electrical Engineering,2012,38(4):1023-1032.

A Fabric Image Matching Algorithm Based on Improved SURF and K-Means Clustering

ZHANG Xue-qin, LIU Yuan-yuan, CAO Yi-chen, ZHANG Peng-fei

(School of Information Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)

Computer intelligent image processing technology can provide an effective aid for dress designer.By extracting the SURF features,the image shape of the cloth can be recognized.However,due to the high feature dimension and the grayscale based feature extraction method of SURF,there exist shortcomings,e.g,slow image matching speed and the matching result is not enough to match the characteristics of human visual.Hence,this paper proposes an adaptive SURF feature extraction algorithm based on wavelet transform and an image color analysis method based on K-Means clustering.By fusing the shape and color feature of the image,the matching speed is accelerated and the matching results are made more accord with the human visual perception.Experiments via 8 different kinds of fabric images show the effectiveness of the proposed algorithm.

fabric image matching; SURF feature; wavelet transform; K-Means clustering

1006-3080(2017)01-0105-08

10.14135/j.cnki.1006-3080.2017.01.017

2016-05-16

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

張雪芹(1972-),女,博士,副教授,主要從事網(wǎng)絡(luò)安全、模式識別的研究。E-mail:zxq@ecust.edu.cn

TP391.41

A