特征提取与匹配算法在民族服饰图案上的应用研究

陈金广, 曹春梅, 任冰青, 马丽丽

(西安工程大学 计算机科学学院, 陕西 西安 710048)

研究与技术

特征提取与匹配算法在民族服饰图案上的应用研究

陈金广, 曹春梅, 任冰青, 马丽丽

(西安工程大学 计算机科学学院, 陕西 西安 710048)

服饰图案包含某些象征意义,是传统服饰文化研究中的重要元素。将图像处理技术应用于民族服饰图案的特征提取时,尺度不变特征变换(SIFT)算法和快速鲁棒性尺度不变(SURF)算法是两类较典型的特征提取算法,它们在图像旋转、尺度变化、噪声干扰情况下具有较好的适应性。文章选取清代宫廷服饰中具有代表性的图案作为实验对象,用SIFT和SURF算法分别对该图像进行特征提取,用最优节点优先(BBF)算法确定特征点匹配点对,计算两种算法的正确匹配率和时间复杂度。实验结果表明,两种算法在服饰图案发生旋转、尺度变化、噪声干扰情况下均保持较高的特征匹配率,对从事网络中海量服饰图像数据自动化分类和检索方面的研究人员具有一定参考价值。

服饰图案; SIFT; SURF; 特征提取; 图像处理; 民族服饰; 图案分类

随着经济的快速发展,人们的物质文化水平有了很大提高,对服饰的要求越来越高,因为它不仅反映一个人的心理、性格、地位,而且是时代环境的真实写照[1]。民族文化具有很高的研究价值,而很多文化就体现在民族服饰图案上。民族服饰图案一般含有大量花纹,大部分都是以手工刺绣的方式制作的,大多含有祈福纳祥的美好含义[2-4]。服饰图案一般由好几个纹理样本构成,纹理是单元按照一定准则重复出现的模式。因此,可以将纹理作为图像的特征进行描述,然后通过纹理对图像分类。

由于计算机技术的兴起,网络中存有大量的民族服饰图案,这些图案种类繁多,且往往未经归类。对网络中某一方面图像的检索和下载问题,可以采用网络爬虫等技术轻易获得,也就是说网络中民族服饰图案的获取问题易于解决。然而当获取大量民族服饰图案之后,如何对图案进行分类是面临的难点。如果通过人工的方法,设计师只能通过肉眼或借助一些图像处理软件来观察民族服饰图案并进行分类,这种处理方式效率很低。而采用自动化的方式进行分类,由计算机处理数据,这种处理方式能够大大提高处理效率。而图像分类的关键是特征提取,特征提取的好坏直接决定分类效果,因此民族服饰图案的特征提取方法是本文关注的重点。

在图像特征提取研究方面,值得关注的是Lowe提出的尺度不变特征变换(scale invariant feature transform, SIFT)算法[5]。当两幅图像之间出现旋转、尺度变化、平移的情况时,该算法能较好地实现图像的匹配。目前SIFT算法应用广泛,如伪影检测[6]、视频马赛克[7]、图像配准[8-9]等,还有在原始算法中加入Harris算法[10],使算法能得到更多的特征点,提高准确性。2008年,Bay等[11]提出了快速鲁棒性尺度不变特征提取(speeded up robust features, SURF)算法。该算法借鉴了SIFT算法中简化近似的思想,采用了Hessian矩阵的行列式值(determinant of hessian, DoH)近似、积分图像的思想,在运算速度上比SIFT算法快很多。SURF算法自问世以来,得到广泛的关注。类似于SIFT算法,该算法被应用于很多方面,如视频拷贝检测[12]、隐现检测[13]、场景匹配[14]、图像马赛克[15]和目标跟踪[16]。目前还有其他特征提取方法,如二值化鲁棒尺度不变特征提取(binary robust invariant scalable keypionts, BRISK)算法、ORB(oriented FAST and rotated BRIEF)算法和FREAK(fast retina keypoint)算法。每种方法都有自己的优势,比如BRISK算法擅长于模糊图像的匹配,ORB算法进行相同图像的匹配时速度较快,而FREAK算法对光照不敏感。

民族服饰图案每次呈现时并不是一成不变的。拍摄角度不同,图案会发生旋转;拍摄距离不同,图案尺寸大小会发生改变;污渍程度不同,图案中噪声类型和强弱会发生变化。这些都会对民族服饰图案的特征提取产生一定影响。考虑到SIFT和SURF算法对图像的旋转、尺寸变化、噪声的不敏感性,本文针对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个像素,上、下层对应位置各9个像素)进行比较。若被检测点的DOG值大于或小于此26个像素点,则该点为极值点,即为图像在此尺度下的一个特征点。

由于对比度较低的特征点对噪声较敏感,而位于边缘上的特征点难以准确定位,所以应剔除这两类特征点。将原图像的SIFT候选特征点放入集合X0,从中筛选出的稳定点放入集合X。

剔除对比度低的特征点的方法是对候选特征点x的DOG函数表达式进行泰勒级数展开:

(3)

式中:Δx是候选特征点x的偏移量。

(4)

在剔除边缘上的特征点时用到了Hessian矩阵:

(5)

式中:Dxx,Dxy,Dyy为候选点邻域对应位置的像素差分。

假设H的最小特征值是β,最大特征值是α。则H的迹和行列式的值为:

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

(6)

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

(7)

(8)

因为边缘方向上的主曲率值大,但是曲率小,所以边缘上的特征点的主曲率比值较大,而主曲率比值与γ成正比。设定阈值为Tγ,则剔除公式为:

(9)

为了使算子具有旋转不变性,需要确定特征点的方向。点L(x,y)的梯度的模m(x,y)与方向θ(x,y)可以由下式得到:

(10)

利用直方图的方式统计每个特征点的邻域像素的梯度分布。该特征点处邻域梯度的主方向由最大峰值确定,即为该特征点的主方向。若存在能量为主峰值的80%的峰值,则该方向是该特征点的辅方向。这样一个特征点就可能具有多个方向,即一个主方向,多于一个的辅方向,使用多个方向可以增强匹配的鲁棒性。

接下来以特征点为中心取大小为8×8的窗口,在每个4×4的小块上计算8个方向的梯度方向直方图,每个梯度方向的累加就可形成一个种子点。实际应用中,每个特征点使用4×4个种子点描述,最终形成128(4×4×8)维的特征描述向量。

最后采用最优节点优先算法(best-bin-first, BBF)对特征点进行匹配。其基本思想是:计算模板图像中的特征点与检测图像中所有特征点之间的欧氏距离,找出其中最小和次小距离。若最小距离和次小距离的比值小于一个阈值hratio,则该最近邻点为匹配特征点。在特征点的匹配方面可以利用随机采样一致性(random sample consensus, RANSAC)算法提高正确匹配率。

1.2 SURF特征提取算法

SURF算法利用Hessian矩阵进行特征点检测。设X(x,y)为图像中一个点,在点X处,尺度为σ的Hessian矩阵H(X,σ)定义为:

(11)

为了将模板与图像的卷积转化成盒子滤波(Box Filter),需要将高斯二阶微分模板简化为由几个矩形区域组成的模板。

若σ=1.2,设定模板尺寸为9×9,用Dxx、Dyy和Dxy表示简化后的模板与图像卷积的结果。则Hessian矩阵的行列式如下:

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

(12)

式(12)表示图像中位于点X处的特征点。对图像中每个像素点进行同样的操作,就得到了该尺寸下特征点检测的响应图像。为了提高检测速度,采用积分图像。积分图像是指某一矩形区域的像素和。积分图像中任意一点(i,j)的值ii(i,j)为原图像左上角到(i,j)相应的对角线区域灰度值的总和:

(13)

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

为了获得不同尺度的特征点,建立图像的尺度空间金字塔。保持图像大小不变,用不同尺寸的盒子滤波模板与积分图像卷积来得到尺度空间。本文先使用9×9的模板滤波,然后逐步加大模板尺寸进行滤波。滤波过程中时间复杂度不随模板尺寸的增加而增加。尺度空间有若干组,每组代表逐步加大的模板对同一图像进行滤波的响应图。相邻两层之间的尺度变化由响应长度l0决定,l0是盒子滤波模板尺寸的1/3。在本文中,l0=9×1/3=3。下一层的响应长度至少在l0上加2,则下一层的l0=5,模板尺寸就是15,以此类推。

确定特征点的过程与SIFT算法一样,即将经过Hessian矩阵处理过的每个像素点与其三维领域的26个点比较大小,是极值就保留下来,再去掉那些对比度低和边缘上的点。为了保证旋转不变性,要给每个特征点分配一个主方向。所以以特征点为中心,6s为半径,对该圆形区域内的图像进行Haar小波响应运算,其中s是特征点的尺度。Haar小波的响应值用σ=2s的高斯加权函数进行高斯加权。将特征点作为张角为π/3的扇形窗口的顶点,将该窗口围绕顶点以步长0.2弧度顺时针旋转一周,对Haar小波响应值dx、dy进行累加,得到一个矢量(mω,θω):

(14)

最大的Haar响应累加值所对应的方向就是主方向,即:θ=θω|max|{mω}。

确定完主方向之后,以特征点为中心,按主方向选取尺寸为20s×20s的正方形区域,该区域中是4×4个子区域,每个子区域中含有5s×5s个像素,使用σ=2s的Haar小波对子区域图像进行响应值计算,得到dx、dy。然后对dx、dy进行高斯加权(σ=3.3s),每个子块的矢量:

(15)

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

2 结果及分析

本文实验环境为Intel(R) Core(TM) i5 CPU,2GB内存。用MATLAB R2013a实现此算法。采用的图案是一幅清代宫廷服饰图像中的一个图案,如图1所示。对该图分别采用SIFT、SURF算法提取特征点。为了比较这两种算法的性能,本文分别从尺寸变化、抗噪和旋转三个方面进行研究。图1是用于实验的原图,该图是清代道光年间三蓝盘金龙马面绣片中的一部分,此绣片取自于清朝妇女的裙摆。清代宫廷服饰中以龙为最尊,而且盘金绣起源于苏绣,用料最贵,所以只有清代的皇族、显贵们才会穿戴这些服饰,用来显示自己的高贵地位。以手工刺绣的方式制作的图案具有代表性,将这种图案选为实验对象,可以使实验结果不失一般性。

图1 原 图Fig.1 Original image

实验过程中图像特征点的匹配用到阈值hratio,hratio取值在0.4～0.6为最佳,当hratio=0.4时,能得到准确度较高的匹配;当hratio=0.6时,能得到较多的匹配点数目;当hratio=0.5时,准确率和匹配点数比较适中。

图2和图3为使用SIFT和SURF算法分别对两幅尺寸不同的民族服饰图案进行匹配的结果,右图尺寸是左图的2倍。hratio取0.6。SURF算法在应用时,要对左图进行扩围,达到右图的尺寸;由这两幅图可以看出,SIFT算法匹配的点对数比SUFR算法多,SURF算法中的误匹配点对数要多于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算法分别对两幅不同尺寸的民族服饰图案进行匹配后的实验结果见表1。由表1可以看出,SIFT算法提取的特征点数比SURF算法多;SIFT算法的正确匹配率高于SURF算法,尺寸变化对SURF算法影响较大;SIFT算法总的时间复杂度要大于SURF算法。

表1 尺寸改变后服饰图案的匹配结果对比

SIFT和SURF算法分别对加了噪声的民族服饰图案和原图进行匹配,右图加的是均值为0、方差为0.03的高斯白噪声。hratio取0.5。得到结果如图4和图5所示。由图4和图5可以看出,SURF算法中的误匹配点对数要多于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算法分别对加了噪声的民族服饰图案和原图进行匹配后的实验结果见表2。由表2可以看出,SIFT算法提取的特征点数比SURF算法多;SIFT算法的正确匹配率比SURF算法高,噪声对SURF算法影响更大;SIFT算法总的时间复杂度要大于SURF算法。

表2 添加噪声后服饰图案的匹配结果对比

分别使用SIFT和SURF算法对旋转的民族服饰图案和原图进行匹配,右图是将左图逆时针旋转5°,并缩小为原来尺寸的92%。hratio取0.2。得到结果如图6和图7所示。由图6和图7可以看出,SURF算法中的误匹配点对数要多于SIFT算法。

图6 旋转图像SIFT算法匹配Fig.6 Matching figure of rotating images based on SIFT

图7 旋转图像SURF算法匹配Fig.7 Matching figure of rotating images based on SURF

SIFT和SURF算法分别对旋转的民族服饰图案和原图进行匹配后的实验结果见表3。由表3可以看出,SIFT算法提取的特征点数比SURF算法多;SIFT算法的正确匹配率比SURF算法高,旋转对SURF算法影响更大;SIFT算法总的时间复杂度要大于SURF算法。

表3 图像旋转后服饰图案的匹配结果对比

总的来说,对民族服饰图案的特征提取及匹配,在相同条件下,SIFT算法提取的特征点数多,正确匹配率较高,但是SURF算法的时间复杂度比SIFT算法低。SIFT算法利用高斯金字塔的思想,获得128维的描述子,所含信息量高于SURF算法,所以获得较高的正确匹配率。SURF算法利用方框滤波和积分图像降低了运算时间,所以时间复杂度低于SIFT算法。因此,两种算法各具特点,都可以有效应用到民族服饰图案分类过程中。

3 结 论

本文将SIFT和SURF算法分别应用在尺寸变化、噪声干扰和图像旋转情况下的民族服饰图案特征提取上,对两幅图像中的特征点数、匹配点对数、正确匹配点对数和运算时间进行对比。SIFT算法正确匹配率比SURF算法高,但SURF算法的时间复杂度较低。总之,两种算法都能有效获得民族服饰图案中的特征。研究表明,SIFT和SURF算法可以提取民族服饰图案特征,并将这些特征应用到民族服饰图案的自动化分类研究中。民族服饰图案的特征提取是服饰图像分类的前提,较多特征点匹配上的图像可以归为一类存储,便于同类服饰的寻找。

[1]胡敬萍.中国少数民族的服饰文化[J].广西民族研究,2001(1):62-68. HU Jingping. The costume culture of Chinese minority[J]. Study of Ethnics in Guangxi,2001(1):62-68.

[2]刘晓杰,张立平.少数民族服饰图案纹样的特色[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].大连大学学报,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].纺织学报,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

国家自然科学基金项目(61201118);“好运来创新研发基金”资助项目(HYL201405)

TS941.19

A

1001-7003(2015)05-0036-06 引用页码: 051107