陳金廣, 曹春梅, 任冰青, 馬麗麗

(西安工程大學(xué) 計算機科學(xué)學(xué)院, 陜西 西安 710048)

研究與技術(shù)

特征提取與匹配算法在民族服飾圖案上的應(yīng)用研究

陳金廣, 曹春梅, 任冰青, 馬麗麗

(西安工程大學(xué) 計算機科學(xué)學(xué)院, 陜西 西安 710048)

服飾圖案包含某些象征意義,是傳統(tǒng)服飾文化研究中的重要元素。將圖像處理技術(shù)應(yīng)用于民族服飾圖案的特征提取時,尺度不變特征變換(SIFT)算法和快速魯棒性尺度不變(SURF)算法是兩類較典型的特征提取算法,它們在圖像旋轉(zhuǎn)、尺度變化、噪聲干擾情況下具有較好的適應(yīng)性。文章選取清代宮廷服飾中具有代表性的圖案作為實驗對象,用SIFT和SURF算法分別對該圖像進行特征提取,用最優(yōu)節(jié)點優(yōu)先(BBF)算法確定特征點匹配點對,計算兩種算法的正確匹配率和時間復(fù)雜度。實驗結(jié)果表明,兩種算法在服飾圖案發(fā)生旋轉(zhuǎn)、尺度變化、噪聲干擾情況下均保持較高的特征匹配率,對從事網(wǎng)絡(luò)中海量服飾圖像數(shù)據(jù)自動化分類和檢索方面的研究人員具有一定參考價值。

服飾圖案; SIFT; SURF; 特征提取; 圖像處理; 民族服飾; 圖案分類

隨著經(jīng)濟的快速發(fā)展,人們的物質(zhì)文化水平有了很大提高,對服飾的要求越來越高,因為它不僅反映一個人的心理、性格、地位,而且是時代環(huán)境的真實寫照[1]。民族文化具有很高的研究價值,而很多文化就體現(xiàn)在民族服飾圖案上。民族服飾圖案一般含有大量花紋,大部分都是以手工刺繡的方式制作的,大多含有祈福納祥的美好含義[2-4]。服飾圖案一般由好幾個紋理樣本構(gòu)成,紋理是單元按照一定準則重復(fù)出現(xiàn)的模式。因此,可以將紋理作為圖像的特征進行描述,然后通過紋理對圖像分類。

由于計算機技術(shù)的興起,網(wǎng)絡(luò)中存有大量的民族服飾圖案,這些圖案種類繁多,且往往未經(jīng)歸類。對網(wǎng)絡(luò)中某一方面圖像的檢索和下載問題,可以采用網(wǎng)絡(luò)爬蟲等技術(shù)輕易獲得,也就是說網(wǎng)絡(luò)中民族服飾圖案的獲取問題易于解決。然而當(dāng)獲取大量民族服飾圖案之后,如何對圖案進行分類是面臨的難點。如果通過人工的方法,設(shè)計師只能通過肉眼或借助一些圖像處理軟件來觀察民族服飾圖案并進行分類,這種處理方式效率很低。而采用自動化的方式進行分類,由計算機處理數(shù)據(jù),這種處理方式能夠大大提高處理效率。而圖像分類的關(guān)鍵是特征提取,特征提取的好壞直接決定分類效果,因此民族服飾圖案的特征提取方法是本文關(guān)注的重點。

在圖像特征提取研究方面,值得關(guān)注的是Lowe提出的尺度不變特征變換(scale invariant feature transform, SIFT)算法[5]。當(dāng)兩幅圖像之間出現(xiàn)旋轉(zhuǎn)、尺度變化、平移的情況時,該算法能較好地實現(xiàn)圖像的匹配。目前SIFT算法應(yīng)用廣泛,如偽影檢測[6]、視頻馬賽克[7]、圖像配準[8-9]等,還有在原始算法中加入Harris算法[10],使算法能得到更多的特征點,提高準確性。2008年,Bay等[11]提出了快速魯棒性尺度不變特征提取(speeded up robust features, SURF)算法。該算法借鑒了SIFT算法中簡化近似的思想,采用了Hessian矩陣的行列式值(determinant of hessian, DoH)近似、積分圖像的思想,在運算速度上比SIFT算法快很多。SURF算法自問世以來,得到廣泛的關(guān)注。類似于SIFT算法,該算法被應(yīng)用于很多方面,如視頻拷貝檢測[12]、隱現(xiàn)檢測[13]、場景匹配[14]、圖像馬賽克[15]和目標跟蹤[16]。目前還有其他特征提取方法,如二值化魯棒尺度不變特征提取(binary robust invariant scalable keypionts, BRISK)算法、ORB(oriented FAST and rotated BRIEF)算法和FREAK(fast retina keypoint)算法。每種方法都有自己的優(yōu)勢,比如BRISK算法擅長于模糊圖像的匹配,ORB算法進行相同圖像的匹配時速度較快,而FREAK算法對光照不敏感。

民族服飾圖案每次呈現(xiàn)時并不是一成不變的。拍攝角度不同,圖案會發(fā)生旋轉(zhuǎn);拍攝距離不同,圖案尺寸大小會發(fā)生改變;污漬程度不同,圖案中噪聲類型和強弱會發(fā)生變化。這些都會對民族服飾圖案的特征提取產(chǎn)生一定影響?？紤]到SIFT和SURF算法對圖像的旋轉(zhuǎn)、尺寸變化、噪聲的不敏感性,本文針對SIFT和SURF算法進行研究,通過理論分析和實驗驗證,判斷特征提取算法在民族服飾圖案特征提取中的效果。

1 SIFT和SURF特征提取算法

1.1 SIFT特征提取算法

由于不同尺度下的尺度空間L(x,y,σ)可由二維圖像I(x,y)和高斯核G(x,y,σ)卷積得到:

L(x,y,σ)=G(x,y,σ)×I(x,y)

(1)

則尺度空間中差分高斯DOG算子由下式求得:

D(x,y,σ)=(G(x,y,kσ)-G(x,y,σ))×I(x,y) =L(x,y,kσ)-L(x,y,σ)

(2)

式中:k為兩個相鄰尺度間的比例因子。

接下來確定圖像的特征點,即求局部極值。每個像素和周圍26個像素(同一層的周圍8個像素,上、下層對應(yīng)位置各9個像素)進行比較。若被檢測點的DOG值大于或小于此26個像素點,則該點為極值點,即為圖像在此尺度下的一個特征點。

由于對比度較低的特征點對噪聲較敏感,而位于邊緣上的特征點難以準確定位,所以應(yīng)剔除這兩類特征點。將原圖像的SIFT候選特征點放入集合X0,從中篩選出的穩(wěn)定點放入集合X。

剔除對比度低的特征點的方法是對候選特征點x的DOG函數(shù)表達式進行泰勒級數(shù)展開:

(3)

式中:Δx是候選特征點x的偏移量。

(4)

在剔除邊緣上的特征點時用到了Hessian矩陣:

(5)

式中:Dxx,Dxy,Dyy為候選點鄰域?qū)?yīng)位置的像素差分。

假設(shè)H的最小特征值是β,最大特征值是α。則H的跡和行列式的值為:

Tr(H)=Dxx+Dyy=α+β

(6)

Det(H)=DxxDyy-(Dxy)2=αβ

(7)

(8)

因為邊緣方向上的主曲率值大,但是曲率小,所以邊緣上的特征點的主曲率比值較大,而主曲率比值與γ成正比。設(shè)定閾值為Tγ,則剔除公式為:

(9)

為了使算子具有旋轉(zhuǎn)不變性,需要確定特征點的方向。點L(x,y)的梯度的模m(x,y)與方向θ(x,y)可以由下式得到:

(10)

利用直方圖的方式統(tǒng)計每個特征點的鄰域像素的梯度分布。該特征點處鄰域梯度的主方向由最大峰值確定,即為該特征點的主方向。若存在能量為主峰值的80%的峰值,則該方向是該特征點的輔方向。這樣一個特征點就可能具有多個方向,即一個主方向,多于一個的輔方向,使用多個方向可以增強匹配的魯棒性。

接下來以特征點為中心取大小為8×8的窗口,在每個4×4的小塊上計算8個方向的梯度方向直方圖,每個梯度方向的累加就可形成一個種子點。實際應(yīng)用中,每個特征點使用4×4個種子點描述,最終形成128(4×4×8)維的特征描述向量。

最后采用最優(yōu)節(jié)點優(yōu)先算法(best-bin-first, BBF)對特征點進行匹配。其基本思想是:計算模板圖像中的特征點與檢測圖像中所有特征點之間的歐氏距離,找出其中最小和次小距離。若最小距離和次小距離的比值小于一個閾值hratio,則該最近鄰點為匹配特征點。在特征點的匹配方面可以利用隨機采樣一致性(random sample consensus, RANSAC)算法提高正確匹配率。

1.2 SURF特征提取算法

SURF算法利用Hessian矩陣進行特征點檢測。設(shè)X(x,y)為圖像中一個點,在點X處,尺度為σ的Hessian矩陣H(X,σ)定義為:

(11)

為了將模板與圖像的卷積轉(zhuǎn)化成盒子濾波(Box Filter),需要將高斯二階微分模板簡化為由幾個矩形區(qū)域組成的模板。

若σ=1.2,設(shè)定模板尺寸為9×9,用Dxx、Dyy和Dxy表示簡化后的模板與圖像卷積的結(jié)果。則Hessian矩陣的行列式如下:

Det(H)=DxxDyy-(0.9Dxy)2

(12)

式(12)表示圖像中位于點X處的特征點。對圖像中每個像素點進行同樣的操作,就得到了該尺寸下特征點檢測的響應(yīng)圖像。為了提高檢測速度,采用積分圖像。積分圖像是指某一矩形區(qū)域的像素和。積分圖像中任意一點(i,j)的值ii(i,j)為原圖像左上角到(i,j)相應(yīng)的對角線區(qū)域灰度值的總和:

(13)

式中:p(i′,j′)表示原圖像中點(i′,j′)的灰度值。

為了獲得不同尺度的特征點,建立圖像的尺度空間金字塔。保持圖像大小不變,用不同尺寸的盒子濾波模板與積分圖像卷積來得到尺度空間。本文先使用9×9的模板濾波,然后逐步加大模板尺寸進行濾波。濾波過程中時間復(fù)雜度不隨模板尺寸的增加而增加。尺度空間有若干組,每組代表逐步加大的模板對同一圖像進行濾波的響應(yīng)圖。相鄰兩層之間的尺度變化由響應(yīng)長度l0決定,l0是盒子濾波模板尺寸的1/3。在本文中,l0=9×1/3=3。下一層的響應(yīng)長度至少在l0上加2,則下一層的l0=5,模板尺寸就是15,以此類推。

確定特征點的過程與SIFT算法一樣,即將經(jīng)過Hessian矩陣處理過的每個像素點與其三維領(lǐng)域的26個點比較大小,是極值就保留下來,再去掉那些對比度低和邊緣上的點。為了保證旋轉(zhuǎn)不變性,要給每個特征點分配一個主方向。所以以特征點為中心,6s為半徑,對該圓形區(qū)域內(nèi)的圖像進行Haar小波響應(yīng)運算,其中s是特征點的尺度。Haar小波的響應(yīng)值用σ=2s的高斯加權(quán)函數(shù)進行高斯加權(quán)。將特征點作為張角為π/3的扇形窗口的頂點,將該窗口圍繞頂點以步長0.2弧度順時針旋轉(zhuǎn)一周,對Haar小波響應(yīng)值dx、dy進行累加,得到一個矢量(mω,θω):

(14)

最大的Haar響應(yīng)累加值所對應(yīng)的方向就是主方向,即:θ=θω|max|{mω}。

確定完主方向之后,以特征點為中心,按主方向選取尺寸為20s×20s的正方形區(qū)域,該區(qū)域中是4×4個子區(qū)域,每個子區(qū)域中含有5s×5s個像素,使用σ=2s的Haar小波對子區(qū)域圖像進行響應(yīng)值計算,得到dx、dy。然后對dx、dy進行高斯加權(quán)(σ=3.3s),每個子塊的矢量:

(15)

因此,特征描述算子由4×4×4=64維特征矢量組成。之后的特征匹配算法仍然使用BBF算法。

2 結(jié)果及分析

本文實驗環(huán)境為Intel(R) Core(TM) i5 CPU,2GB內(nèi)存。用MATLAB R2013a實現(xiàn)此算法。采用的圖案是一幅清代宮廷服飾圖像中的一個圖案,如圖1所示。對該圖分別采用SIFT、SURF算法提取特征點。為了比較這兩種算法的性能,本文分別從尺寸變化、抗噪和旋轉(zhuǎn)三個方面進行研究。圖1是用于實驗的原圖,該圖是清代道光年間三藍盤金龍馬面繡片中的一部分,此繡片取自于清朝婦女的裙擺。清代宮廷服飾中以龍為最尊,而且盤金繡起源于蘇繡,用料最貴,所以只有清代的皇族、顯貴們才會穿戴這些服飾,用來顯示自己的高貴地位。以手工刺繡的方式制作的圖案具有代表性,將這種圖案選為實驗對象,可以使實驗結(jié)果不失一般性。

圖1 原 圖Fig.1 Original image

實驗過程中圖像特征點的匹配用到閾值hratio,hratio取值在0.4～0.6為最佳,當(dāng)hratio=0.4時,能得到準確度較高的匹配;當(dāng)hratio=0.6時,能得到較多的匹配點數(shù)目;當(dāng)hratio=0.5時,準確率和匹配點數(shù)比較適中。

圖2和圖3為使用SIFT和SURF算法分別對兩幅尺寸不同的民族服飾圖案進行匹配的結(jié)果,右圖尺寸是左圖的2倍。hratio取0.6。SURF算法在應(yīng)用時,要對左圖進行擴圍,達到右圖的尺寸;由這兩幅圖可以看出,SIFT算法匹配的點對數(shù)比SUFR算法多,SURF算法中的誤匹配點對數(shù)要多于SIFT算法。

圖2 不同尺寸圖像SIFT算法匹配Fig.2 Matching figure of images with differentsizes based on SIFT

圖3 不同尺寸圖像SURF算法匹配Fig.3 Matching figure of images with differentsizes based on SURF

SIFT和SURF算法分別對兩幅不同尺寸的民族服飾圖案進行匹配后的實驗結(jié)果見表1。由表1可以看出,SIFT算法提取的特征點數(shù)比SURF算法多;SIFT算法的正確匹配率高于SURF算法,尺寸變化對SURF算法影響較大;SIFT算法總的時間復(fù)雜度要大于SURF算法。

表1 尺寸改變后服飾圖案的匹配結(jié)果對比

SIFT和SURF算法分別對加了噪聲的民族服飾圖案和原圖進行匹配,右圖加的是均值為0、方差為0.03的高斯白噪聲。hratio取0.5。得到結(jié)果如圖4和圖5所示。由圖4和圖5可以看出,SURF算法中的誤匹配點對數(shù)要多于SIFT算法。

圖4 加噪聲圖像SIFT算法匹配Fig.4 Matching figure of additive noise images based on SIFT

圖5 加噪聲圖像SURF算法匹配Fig.5 Matching figure of additive noise images based on SURF

SIFT和SURF算法分別對加了噪聲的民族服飾圖案和原圖進行匹配后的實驗結(jié)果見表2。由表2可以看出,SIFT算法提取的特征點數(shù)比SURF算法多;SIFT算法的正確匹配率比SURF算法高,噪聲對SURF算法影響更大;SIFT算法總的時間復(fù)雜度要大于SURF算法。

表2 添加噪聲后服飾圖案的匹配結(jié)果對比

分別使用SIFT和SURF算法對旋轉(zhuǎn)的民族服飾圖案和原圖進行匹配,右圖是將左圖逆時針旋轉(zhuǎn)5°,并縮小為原來尺寸的92%。hratio取0.2。得到結(jié)果如圖6和圖7所示。由圖6和圖7可以看出,SURF算法中的誤匹配點對數(shù)要多于SIFT算法。

圖6 旋轉(zhuǎn)圖像SIFT算法匹配Fig.6 Matching figure of rotating images based on SIFT

圖7 旋轉(zhuǎn)圖像SURF算法匹配Fig.7 Matching figure of rotating images based on SURF

SIFT和SURF算法分別對旋轉(zhuǎn)的民族服飾圖案和原圖進行匹配后的實驗結(jié)果見表3。由表3可以看出,SIFT算法提取的特征點數(shù)比SURF算法多;SIFT算法的正確匹配率比SURF算法高,旋轉(zhuǎn)對SURF算法影響更大;SIFT算法總的時間復(fù)雜度要大于SURF算法。

表3 圖像旋轉(zhuǎn)后服飾圖案的匹配結(jié)果對比

總的來說,對民族服飾圖案的特征提取及匹配,在相同條件下,SIFT算法提取的特征點數(shù)多,正確匹配率較高,但是SURF算法的時間復(fù)雜度比SIFT算法低。SIFT算法利用高斯金字塔的思想,獲得128維的描述子,所含信息量高于SURF算法,所以獲得較高的正確匹配率。SURF算法利用方框濾波和積分圖像降低了運算時間,所以時間復(fù)雜度低于SIFT算法。因此,兩種算法各具特點,都可以有效應(yīng)用到民族服飾圖案分類過程中。

3 結(jié) 論

本文將SIFT和SURF算法分別應(yīng)用在尺寸變化、噪聲干擾和圖像旋轉(zhuǎn)情況下的民族服飾圖案特征提取上,對兩幅圖像中的特征點數(shù)、匹配點對數(shù)、正確匹配點對數(shù)和運算時間進行對比。SIFT算法正確匹配率比SURF算法高,但SURF算法的時間復(fù)雜度較低?？傊?兩種算法都能有效獲得民族服飾圖案中的特征。研究表明,SIFT和SURF算法可以提取民族服飾圖案特征,并將這些特征應(yīng)用到民族服飾圖案的自動化分類研究中。民族服飾圖案的特征提取是服飾圖像分類的前提,較多特征點匹配上的圖像可以歸為一類存儲,便于同類服飾的尋找。

[1]胡敬萍.中國少數(shù)民族的服飾文化[J].廣西民族研究,2001(1):62-68. HU Jingping. The costume culture of Chinese minority[J]. Study of Ethnics in Guangxi,2001(1):62-68.

[2]劉曉杰,張立平.少數(shù)民族服飾圖案紋樣的特色[J].文藝研究,2009(7):147-149. LIU Xiaojie, ZHANG Liping. The characteristic of minority costume pattern[J]. Literature & Art Studies,2009(7):147-149.

[3]戴成萍.從民族服飾圖案看中國的吉祥文化[J].大連大學(xué)學(xué)報,2006,27(5):83-86. DAI Chengping. Study Chinese auspicious culture from national costume pattern[J]. Journal of Dalian University,2006,27(5):83-86.

[4]宋湲,徐東.中國民族服飾的符號特征分析[J].紡織學(xué)報,2007,28(4):100-103. SONG Yuan, XU Dong, Analysis of symbolic signs of Chinese nationality trappings[J]. Journal of Textile Research,2007,28(4):100-103.

[5]LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision,2004,60(2):91-110.

[6]ZHANG L, HE X M. Fake shadow detection based on SIFT features matching[C]//Information Engineering(ICIE), 2010 WASE International Conference on Alaska: IEEE,2010(1):216-220.

[7]YANG J, PEI Y J, LI B, et al. Multivideo mosaic based on SIFT algorithm[C]//Computer Science and Network Technology(ICCSNT), 2011 International Conference on Alaska: IEEE,2011(3):1497-1501.

[8]CAO Y D, ZHANG H G, GAO Y Y, et al. An efficient duplicate image detection method based on affine-SIFT feature[C]//Broadband Network and Multimedia Technology(IC-BNMT), 2010 3rd IEEE International Conference on Alaska: IEEE,2010:794-797.

[9]LIU J X, QIU Y H. Application of SIFT feature extraction algorithm on the image registration[C]//Electronic Measurement & Instruments(ICEMI), 2011 10th International Conference on Alaska: IEEE,2011(3):177-180.

[10]LIU R A, ZHANG J S, WANG L, et al. Application of the extraction of the image feature points by improved SIFT Algorithm[C]//Communications Workshops(ICC), 2013 IEEE International Conference on Alaska: IEEE,2013:946-949.

[11]BAY H, TUYTELAARS T, VAN G L. Surf: Speeded up Robust Features[M]//Computer Vision-ECCV 2006. Springer Berlin Heidelberg: ECCV,2006:404-417.

[12]ASHA S, SREERAJ M. F-SURF feature descriptor for video copy detection[C]//Advances in Computing and Communications(ICACC), 2014 4th International Conference on Alaska: IEEE,2014:93-96.

[13]WANG Y Q, YANG Y, REN T W, et al. A Motion-insensitive dissolve detection method with SURF[C]//Image and Graphics, 2009. ICIG’09. 5th International Conference on Alaska: IEEE,2009:451-456.

[14]SU J, XU Q S, ZHU J H. A scene matching algorithm based on SURF feature[C]//Image Analysis and Signal Processing(IASP), 2010 International Conference on Alaska: IEEE,2010:434-437.

[15]HONG J X, LIN W, ZHANG H, et al. Image mosaic based on SURF feature matching[C]//Information Science and Engineering(ICISE), 2009 1st International Conference on Alaska: IEEE,2009:1287-1290.

[16]ZHOU Z H, OU X W, XU J. SURF feature detection method used in object tracking[C]//Machine Learning and Cybernetics(ICMLC), 2013 International Conference on Alaska: IEEE,2013:1865-1868.

Research on Application of Feature Extraction and Matching Algorithms in Chinese Costume Patterns

CHEN Jinguang, CAO Chunmei, REN Bingqing, MA Lili

(School of Computer Science, Xi’an Polytechnic University, Xi’an 710048, China)

Dress patterns contain some symbolic meanings and are important elements in the research on traditional dress culture. This paper applies image processing technology to feature extraction of folk costume patterns. SIFT and SURF algorithms are two typical feature extraction algorithms and have good adaptability under the condition of image rotation, scale change and noise jamming. With a representative pattern in palace dress in Qing dynasty as experimental object, this paper conducts feature extraction of this image respectively with SIFT and SURF algorithms, determines matching point pair of feature points with best-bin-first (BBF) algorithm and calculates correct matching rate and time complexity of the two algorithms. The experimental result shows that both algorithms have high feature matching rate under the condition of dress image rotation, scale change and additive noise jamming. This conclusion has certain reference value for researchers engaged in automated classification and retrieval of mass garment image data online.

costume pattern; scale invariant feature transform; speeded up robust features; feature extraction; image processing; folk costume; pattern classification

doi.org/10.3969/j.issn.1001-7003.2015.05.007

2014-10-30;

2015-02-08

國家自然科學(xué)基金項目(61201118);“好運來創(chuàng)新研發(fā)基金”資助項目(HYL201405)

TS941.19

A

1001-7003(2015)05-0036-06 引用頁碼: 051107