一种基于改进SURF和K-Means聚类的布料图像匹配算法

张雪芹, 刘远远, 曹逸尘, 张鹏飞

(华东理工大学信息科学与工程学院,上海 200237)

一种基于改进SURF和K-Means聚类的布料图像匹配算法

张雪芹, 刘远远, 曹逸尘, 张鹏飞

(华东理工大学信息科学与工程学院,上海 200237)

计算机图像智能处理技术为服装设计师开展设计、启发灵感提供了方便和可能。通过提取布料图像的SURF特征可以实现布料图像形状分析,但由于SURF特征维数高、特征提取是基于灰度图进行,因此存在匹配速度慢、匹配结果不够符合人眼视觉特点的问题。本文提出了基于小波变换的自适应SURF特征提取算法和基于K-Means聚类的布料图像颜色分析方法。通过融合图像形状特征、颜色特征,加快了布料图像匹配速度,使布料图像的匹配结果更加符合人眼视觉感受。在8种不同类型布料图像上的实验验证了该算法的有效性。

布料图像匹配; SURF特征; 小波变换; K-Means聚类

近年来,图像处理技术越来越多地运用到纺织领域中,如织物外观性能的测试、织物的密度测定等。对于服装设计师而言,当他们根据已知的布料图案(比如来自于街拍或时装发布会的模特照片)选取服装设计布料时有两种需求:一是希望在布料库中找到近乎相同的布料;二是希望在布料库中找到图案类别、图案空间分布或颜色相近的布料,以启发其设计灵感。若靠人工从成千上万的布料图像库中找到相关图片是极其耗时和困难的。计算机图像的智能分析技术为该应用提供了可能。

常见的图像匹配方法有两种:基于灰度的图像匹配和基于特征的图像匹配。基于灰度的图像匹配[1]根据全局最优化像素间的相似度来度量两幅图像的匹配度,如平均绝对差 (MAD)、序贯相似性检测 (SSAD)、归一化灰度组合相关 (NIC)和去均值归一化互相关 (NNPROD)等。基于特征的图像匹配[2]根据提取的图像特征点来实现图像之间的匹配,如Forstner、Harris、Moravec、SIFT、SURF等。

Lowe等[3]提出将SIFT算法应用于图像配准、图像拼接、人脸识别等领域,但计算量较大、算法较复杂以及花费时间长。Bay等[4]提出的SURF算法在速度上较SIFT算法有明显的优势,但是正确率低、误匹配点多。针对上述问题,Yanke等[5]提出了PCA-SIFT算法，采用主成分分析法实现对特征描述符的降维;Mikolajczyk等[6]提出了GLOH(Gradient Location Orientation Histog-ram)算法进一步增强了特征描述符的独特性;Morel等[7]提出ASIFT(Affine-SIFT)抗仿射SIFT变换用于实现全仿射不变性。

针对辅助服装设计师选取布料、启发设计灵感这一目的,在分析布料图像特点的基础上,本文提出了基于小波变换的自适应SURF特征提取方法和基于K-Means聚类的布料图像颜色提取方法,通过融合图像的形状和颜色特征实现图像间的匹配,提高了布料图像匹配速度,并使匹配结果更符合人眼视觉特性。该算法与SIFT、SURF等算法相比在匹配速度和正确率上都有较好的改善。

1 算法简介

1.1 SURF算法

SURF算法是Bay等[8]提出的基于特征的图像匹配算法。其主要思想是:采用离散化和裁剪的DOH(Determinant of Hessian)来获取特征点,用 Harr小波模板提取特征,并采用积分图像来加速计算DOH和Haar模板响应。SURF算法主要包含特征点检测和特征描述子两个部分。

1.1.1 特征点检测

(1) 积分图像。积分图像可以快速实现方框卷积滤波的功能。设X=(x,y)表示图像I上的某一像素点,则其积分图像I(X)定义为

(1)

如图1所示,以A、B、C、D为顶点的矩形区域像素值的和为S=I(D)-I(B)-I(C)+I(A)。

图1 积分图像示意图

引入积分图后,矩形区域内像素值的计算与图像的坐标值无关,只需根据矩形的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的立体邻域内进行非极大值抑制,只有当该局部极值点比上一尺度、下一尺度及本尺度周围的26个邻域值都大或者都小时,该局部极值点成为特征点。

1.1.2 特征描述子

(1) 确定特征点主方向。以特征点为圆心,6s(s为特征点尺度)为半径画圆,计算圆内的所有像素点在x和y方向上的Haar小波响应。然后,以特征点为圆心,以60°范围的扇形区域为窗口,对整个圆形区域进行遍历,以扇形区域内的所有像素点的Haar小波响应之和作为新的矢量，遍历一周,选择最大矢量的方向作为该特征点的主方向。

1.2 小波变换

1.2.1 概述Mallat等[9]提出了多分辨率图像分解的小波表示。小波变换的基本思想:将基本小波经过伸缩和平移,分解成一系列具有不同空间分辨率、不同频率及不同方向特性的子带信号,实现对信号时间、频率的局部化分析。由于图像为二维离散信号,这里应用到的小波变换为二维离散小波变换。

1.2.2 二维小波函数 令φ(x)为一维尺度函数,ψ(x)为一维小波函数,则其小波基的离散化形式为

(4)

式中:m为伸缩因子;n为平移因子。对于二维空间来说,其尺度函数为

(5)

小波函数为

(6)

式中:n1、n2分别为x和y方向的平移因子;上标H、V、D分别代表水平、垂直和对角斜线方向。

1.2.3 二维图像的离散小波分解 对于一幅图像I(x,y)来说,设其原始图像的尺度为1。在每个层次的变换中,图像都被分成4个大小为原图1/4的子频带信号。则对于第j层(j = 0,1…,K,K为设定变换的层次数),其4个子频带信号可表示为

(7)

式中:IjL(x,y),IjH(x,y),IjV(x,y),IjD(x,y)分别表示图像I(x,y)在分辨率j上的低频分量,以及在水平、垂直和对角3个方向的高频分量。

1.3RANSAC算法

RANSAC算法[10]常用于剔除基于特征图像匹配中的误匹配的特征点。RANSAC算法的具体步骤如下:

假设数据集合S是由n对匹配点组成的,由于本文中使用的是仿射变换模型,所以至少需要3对匹配点数据方可求出模型。

初始化:误差阈值Def_T,预设阈值Pre_T;

(1) 从数据集合S中随机选取3对不共线的初始匹配点,利用最小二乘法得到其初始的变换矩阵H;

(2) 对其余的n-3对匹配点,分别计算其与模型之间的距离,若小于误差阈值Def_T,则认为该特征点为匹配对的内点(Inliers),否则为外点(Outliers),统计内点个数num;

(3) 重复步骤(1)、步骤(2),当num的值不再变化且大于预设阈值Pre_T时,对应的内点集合即为最大内点域,此时的变换矩阵H为最优模型矩阵。

2 基于小波变换和SURF的图像匹配

2.1WtSurf图像匹配算法

SURF算法能够较好地提取图像的形状特征,实现图像与图像间的形状匹配。但是由于其特征维数较高,因此存在匹配速度慢的问题。针对以上问题,本文提出了基于小波变换和SURF的图像匹配算法(WtSurf)。

WtSurf算法首先对图像进行小波分解获得其低频分量,然后提取低频图像的SURF特征,最后通过交叉过滤法和RANSAC算法剔除误匹配特征点,以匹配到的特征点对数占待测图片特征点数的比例作为图像间相似度的判据。由于经过RANSAC算法进一步筛选匹配对后,会使得某些图片的匹配对数过少,所以算法最终采用保留交叉匹配的结果,对经RANSAC算法筛选保留的匹配对,通过加大判别权重来综合计算图像间的相似度。

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

图2 WtSurf算法流程图

算法步骤如下:

Step 1 待测图像和图像库中的目标图像通过小波变换分别得到其低频图像Q和T;

Step 2 分别提取图像Q和T的SURF特征,得到特征点集Q={q1,q2,…,qn1}和T={t1,t2,…,tn2},按图像遍历顺序分别为两个特征点集中的特征点建立索引号,其中,n1和n2分别为待测图像和目标图像的特征点数;

Step3 对特征点集Q和T做交叉匹配。即,双向计算Q中所有特征点和T中所有特征点的欧式距离。如果Q中某个特征点qx与T中某个特征点ty彼此为最近点,且索引号相同,则保留该特征点对。经过交叉匹配分别得到匹配的特征点集Q*={q1*,q2*,…,qm1*}和T*={t1*,t2*,…,tm1*},其中,m1为双向匹配得到的特征点对数;

Step4 用RANSAC算法进一步剔除特征点集Q*和T*的误匹配特征点组,得到FQ={fq1,fq2,…,fqm2}和FT={ft1,ft2,…,ftm2},其中,m2为最终匹配得到的特征点对数;

Step5 计算Vs=k1×m1/n1+k2×m2/n1,把Vs的值作为度量图像间形状的相似度的依据,其中,k1、k2为权值。

2.2 自适应WtSurf图像匹配算法(AWtSurf)

SURF算法的可调参数主要有组数(nOctaves)、层数(nOctaveLayer)和Hessian行列式阈值(Hessian threshold)。其中,组数和层数决定了方框滤波模板的大小,即从哪些尺度空间中提取特征点,Hessian行列式阈值的大小表征图像中对应位置特征的强弱程度。综合考虑图像的特点及应用场景选择组数、层数和Hessian行列式的阈值,可使算法有更好的效率和稳定性。

实验发现,由于布料图像的千差万别,固定的Hessian行列式阈值很难满足所有布料图像特征提取的需求。比如当采用算法默认的Hessian行列式阈值100时,对于波点类型的布料图像,易出现因提取到的特征点数过少而导致匹配失败。但是简单地降低Hessian行列式阈值,对于像蕾丝、花类型的布料图像来说,不仅不会提高布料图像的匹配能力,反而增加了布料图像匹配时间。因此,本文提出在实验确定组数和层数的基础上,在WtSurf算法的Step 2,采取动态设定Hessian行列式阈值方法提取特征点集。其流程如图3所示。

3 基于颜色聚类和特征的图像匹配

3.1 概述

基于SURF算法可以实现图像间的形状特征的匹配,但是由于SURF算法是基于灰度图像提取形状特征,因此匹配到的图像间没有颜色相似度度量。这就造成比如像蕾丝和印花布料,尽管前者颜色单一,后者颜色丰富,但是当两种布料上图案一致时 (比如都有牡丹花),那么在基于SURF特征的匹配中就会呈现很高的相似度(如图4所示),因而会将相关布料推送给设计师。但是在实际应用场景中,设计师并不认为这两种布料是相似的。此外,当待测图片在图片库中找不到相似的图案时,设计师往往希望推送给他们的是在空间分布或颜色上相近的布料图像。

图3 动态设定Hessian行列式阈值流程图

图4 形状相似布料的不同类型的图像

针对上述问题,本文提出了基于K-Means聚类的颜色种类提取和颜色直方图的颜色特征提取方法,结合布料图像形状特征,最终实现布料图像匹配。由于HSV颜色空间比较符合人眼的视觉特性,所以本文的颜色特征提取基于HSV颜色空间。

3.2 基于K-Means的颜色聚类

给定一幅图像P,尺寸大小为M×N,其每个像素xi(i=1,2,…,M×N)在HSV颜色空间具有H、S、V 3个分量。基于K-Means的颜色聚类的流程如下:

初始化:设定聚类数K;

Step 1 对于P来说,从中任取K个点Ck(k=1,2,…,K)作为初始聚类中心;

Step 2 分别计算图像中其他数据点到质心Ck(k=1,2,…,K)的欧式距离,并将其归类到与其距离最近的质心类;

Step4 聚类结束,得到最终聚类中心Ck*;

Step5 根据聚类中心点及HSV颜色参照表,得到每幅图像的颜色种类数。

3.3C_AWtSurf图像匹配算法

C_AWtSurf算法首先采用K-Means算法在HSV颜色空间进行颜色聚类,提取布料图像的颜色种类,将与待匹配布料图像颜色种类数差别较大的布料图像予以剔除。对于剔除后的图像,计算两幅图像的HSV空间颜色直方图,把图像间颜色直方图的欧氏距离作为度量两幅图像颜色相似度的依据。

算法描述如下:

Step1 待测图像和图像库中的目标图像通过小波变换得到其低频图像Q和T;

Step2 对图像Q和T在HSV空间进行颜色聚类及颜色直方图计算,得到图像Q和T的颜色种类数Nq和Nt及其HSV颜色直方图Histq和Histt,其中Histq={hq(0),hq(1),…,hq(BIN)},Histt={ht(0),ht(1),…,ht(BIN)},BIN为划分的颜色区间数;

Step3 若Nq-Nt>1,则判定两幅图像不匹配;否则,计算Histq和Histt的欧氏距离Vc来表征图像之间的颜色相似度:

(8)

算法流程如图5所示。

图5 基于颜色聚类的图像匹配流程图

3.4 融合形状和颜色特征的图像匹配度

对设计师而言,希望匹配到的图像既图案相似又颜色相近,以图案相似为主,颜色相近为辅。因此算法考虑优先输出形状和颜色均较相似的图像;而当颜色不相似时,则输出形状相似度较高的图像,以减少视觉干扰。

假设Score表示融合颜色特征和形状特征后的相似度值,Vc表示颜色特征匹配度,Vs表示形状特征匹配度,则设定相似度阈值Similarity。定义当两幅图像颜色不相似时(Vc< Similarity),Score=Vs;当两幅图像颜色相似时(Vc≥Similarity),Score=wcVc+wsVs,其中wc、ws分别为颜色和形状的权重。

4 实验数据及分析

4.1 实验数据与环境描述

实验中的布料图像来自于某服装公司,选取891张样本,其中包括蕾丝、豹纹、波点、方格、条纹、几何、花、千鸟格共8类,如图6所示,每种类型的图片数量如表1所示。

表1 布料库描述

图6 布料图像类型示例图

实验的操作系统为Windows7,开发环境为Visual Studio2010,图像处理开源库为OpenCV2.4.11,CPU 1.7 GHz,内存8 GB。

4.2 布料图像匹配的评价机制

由于本应用主要是为服装设计师挑选布料提供参考,因此采用主观评价法对算法输出结果进行评价。根据调研,设计评价指标为:{布料类型,图案的空间分布,形状,颜色},划分评分等级为:{完全相同,比较相似,一般相似,较大不同,完全不同},两幅图像在这4个方面完全匹配时得1分。评分机制如表2所示。

表2 主观评分机制

4.3 实验结果及分析

4.3.1 实验1 本实验主要是为了确定AWtSurf算法中的两个参数:组数(nOctaves)与层数(nOctaveLayers)。当采用不同的组数和层数时,提取到的不同类型布料图像的特征点数如表3所示。

表3 不同组数和层数时提取的SURF特征点数

由表3可知,当固定SURF参数中的Hessian行列式阈值和层数时,组数分别取1、3、5,当组数大于3后,提取的图像特征点数不再变化。当固定SURF参数中的Hessian行列式阈值和组数时(此时组数设定为3),层数分别取3、5、7,当层数大于5后,提取图像特征点数的增量趋缓,层数为5时提取到的图像特征点数是层数为7时提取到的图像特征点数的91.5%。综合考虑算法的有效性,实验中将组数设定为3,层数设定为5。

4.3.2 实验2 为了验证本文算法的有效性,实验比较了SIFT、SURF、WtSift、WtSurf、AWtSurf和C_AWtSurf算法。其中,AWtSurf和C_AWtSurf采用自适应动态调节Hessian行列式阈值的算法,更新步长m为10,特征点阈值为40。经过实验比较,相似度阈值Similarity=0.8,颜色权重wc=0.2,形状权重ws=0.8(由于篇幅限制,不同参数的匹配评分结果不再一一列出)。对于C_AWtSurf算法,匹配速度和评价得分结果如表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 不同算法下布料图像的匹配时间

为了更加直观地观测实验结果。图9给出了部分匹配结果。由于篇幅原因,这里仅给出了3种类型布料中匹配度较高的前5张。

图9 匹配结果实例

每种类型布料图像的第1张为待匹配布料图像,后续5张为匹配推送结果。第2张为匹配出的待测布料在图库中的原图,后续为与待测布料颜色或者形状相似的图片。结果表明,C_AWtSurf算法不仅能够准确地找出相同布料,同时能够推送相似图像,既满足了设计者在布料库中精准寻找布料的需求,又可以启发其设计灵感。

5 结 论

为了辅助服装设计师选取布料、启发设计灵感,针对不同类型的布料图像,提出了基于小波变换的自适应SURF特征提取方法和基于K-Means聚类的图像颜色提取方法。通过融合图像的形状和颜色特征,使得匹配结果更加符合人的视觉特性。实验结果验证了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

国家自然科学基金(61371150)

张雪芹(1972-),女,博士,副教授,主要从事网络安全、模式识别的研究。E-mail:zxq@ecust.edu.cn

TP391.41

A