基于轮廓与SIFT特征组合的商标图像检索

向雷，肖诗斌，2，林春雨，2，吕学强，2

1.北京信息科技大学中文信息处理研究中心，北京 100101

2.北京拓尔思信息技术股份有限公司，北京 100101

基于轮廓与SIFT特征组合的商标图像检索

向雷1，肖诗斌1，2，林春雨1，2，吕学强1，2

1.北京信息科技大学中文信息处理研究中心，北京 100101

2.北京拓尔思信息技术股份有限公司，北京 100101

1 引言

商标图像的自动检索对于保护注册商标的合法权益具有重要的意义。在对新的商标图像进行注册时，需要查询已有的商标库中是否存在重复或类似的商标图像，从而决定其是否具有注册资格[1]。近年来，由于注册商标的数目不断增加，人工检索的方式已经难以胜任大量商标的相似性比较。因此，为了加强商标的管理，建立一种准确高效的商标自动检索系统具有非常重要的意义。

商标检索的方法可分为基于类目检索商标、基于文本检索商标、基于内容检索商标。随着商标数目的不断增长，前两种检索的弊端逐渐显露，而近年来发展的基于内容的检索方法突破了前两种方法的局限。基于内容的检索方法包括颜色特征、纹理特征和形状特征。对于商标图像来说，颜色信息只能作为辅助特征，不能作为判断两幅图像是否相似的准则。另外，由于商标一般比较简单，纹理信息较少，因而对于它们的检索，形状特征显得尤为重要。

对于形状的表示和描述是基于形状的商标图像检索的核心问题，现有的对形状的描述方法大体可以分为基于轮廓和基于区域两大类。以轮廓为基础的特征提取方面，Freeman[2]等人提出用链码来描述商标图像的形状特征；Iivarinen[3]在前人的基础上又提出链码直方图的特征表示方法；姚玉荣[4]等人利用小波变换提取图像边缘，然后用边界矩对图像的边缘进行描述，具有较好的平移、尺度和旋转不变性。以区域为基础的特征提取方面，马跃先[5]等提出了利用7个不变矩特征进行图像检索的方法，满足图像的平移、尺度和旋转不变性；孙兴华[6]等提出了利用子图像特征进行商标检索，先对商标图像进行子图像分割和抽取，然后提出子图像特征进行检索；Guo[7]等提出在四叉树分解子块上进行形状特征提取，使检索精度有了进一步的提高。

大部分性状描述方法都是把形状作为一个整体来考虑。在这些方法中，图像的相似度都是通过直接计算直方图或者特征向量的距离而得到的。这样做可以从整体上分析形状的特点，计算比较简单，但是对于局部的描述并不充分。有些商标图像可能是另一些商标图像的形变，这些商标图像整体相似度可能有差异，但在某些局部相似度仍然很高。因此在进行形状分析时，不但要考虑全局的相似性，还要考虑局部的相似性。为了提高检索的精度，提出了一种基于轮廓和SIFT特征的商标图像检索方法。

2 SIFT特征提取

SIFT算法的本质就是从图像中提取SIFT关键点的过程。它的提取算法包块3个关键步骤[8]：尺度空间极值检测；关键点方向参数的确定；特征向量描述。

2.1 尺度空间极值点检测

为了检测尺度空间的极值，首先必须建立适当的尺度空间。图1为Gaussian金字塔和DoG尺度空间的建立过程（左边表示的是Gaussian尺度空间，右边表示的是DoG尺度空间）。

图1 （a）Gaussian和DoG尺度空间的建立过程

图1 （b）局部极值点检测

DoG尺度空间是利用高斯差分（DoG）来建立的，DoG算子定义如式（1）：

为了检测局部极值点，需要比较DoG尺度空间图像中的每一个像素与它邻近26个像素（上一个尺度空间图像的9个像素点，同尺度空间图像的8个点，下一个尺度空间图像的9个像素点）的值，如图1中图（b）所示。若一个像素(x，y)是局部极值点，则它必须是与邻近的26个像素中比较后得出的极值点。所有这样得到的局部极值点，就是算法所需的SIFT候选的关键点的集合。

2.2 关键点方向参数确定

在获得了比较稳定和具有抗噪能力的特征点后，为了能让特征点具有旋转不变性，应该计算这些特征点的主方向，让特征描述子在这个主方向上生成，这样就可以消除因为旋转而产生的不一致性了。对每个特征点来说，先要计算高斯滤波后的商标图像在该特征点邻域内（一般为该特征点尺度的1.5倍）所有点的梯度模值和梯度方向，这里可以使用差分运算来近似梯度的求导运算，如式（2）和式（3）所示[9]：

实际计算时，在高斯空间内特征点的领域内采样，创建梯度方向直方图。直方图每10°为一个格子（bin），共36个格子。然后将领域内的每个采样点按梯度方向归入适当的bin，以梯度模作为贡献的权重。最后选择直方图的主峰值作为特征点的主方向，选取量值达主峰值80%以上的局部峰值作为辅助方向。这样，一个特征点可能会被指定具有多个方向，可以增强匹配的鲁棒性。

2.3 特征向量描述

接下来需要为每个检测到的特征点生成SIFT特征描述子，具体步骤如下[10]：

（1）首先以特征点为中心取16×16的邻域作为采样窗口。

（2）将采样窗口中各像素点的根据坐标按高斯加权归入4×4的位置网格（每个格子即为描述子的一维），窗口中所有点对同一网格的贡献之和作为描述子在该维的值。

（3）将采样点与特征点的相对方向按高斯加权后归入包含8个格子（bin）的方向直方图（每个格子同样作为描述子的一维），所有点对同一格子的贡献之和作为描述子在该维的值。这里注意创建方向直方图使用的是采样点和特征点的相对方向，从而可以使SIFT特征具有旋转不变性。

（4）由（2）、（3）即获得4×4×8共128维的SIFT描述子。

如图2描述了一个8×8的窗口采样的情形。

图2 关键点特征向量描述

3 轮廓特征提取

对商标图像的轮廓特征提取可以分为三步：

（1）对商标图像进行轮廓提取；

（2）对轮廓的点集进行采样，并将采样点作为商标图像的轮廓特征点集；

（3）对该特征点集进行特征描述，并将对特征点集的描述作为商标图像的全局轮廓特征描述。

3.1 轮廓提取

提取图像轮廓即对图像进行边缘提取，而提取图像边缘又首先要通过边缘检测算法计算图像的边缘值。常用的边缘检测算法大多是以原始图像的灰度值为基础，通过考察图像的每个像素的某个领域内灰度的变化，利用一阶或二阶导数的规律来检测边缘。

Sobel算子是边缘检测中最常用的算子之一，它首先进行领域平均或加权平均，然后进行一阶微分处理，检测出边缘点。通常用式（4）中的两个卷积核h1和h2，分别对图像进行水平和垂直边缘的检测[11]：

如果h1响应的是x，h2响应是y，则可得出幅值：其方向是arctan()，运算结果是一副边缘幅度图像。如图3为进行Sobel算子的轮廓提取效果图。

3.3 参考点特征描述

图3 Sobel算子轮廓提取效果图

3.2 轮廓分解

3.2.1 分解起始点求取

分解起始点要求通过规则算法得到轮廓上的某一固定点。下面给出计算轮廓起始点的规则算法[11]：

（1）计算图像的中心点坐标。通过阶矩计算图像的中心点坐标(ˉ，ˉ)，计算公式如式（5）：

（2）计算图像的主方向轴斜率K。对于图像而言，无论其做何角度的旋转，主方向轴都是唯一的。图像的主方向轴与水平方向的夹角β可以根据图像的中心矩计算得到，如式（6）：

（3）通过主方向轴与水平方向的夹角得到主方向轴的斜率k，如式（7）：

（4）计算主方向轴。通过中心点位置和主方向轴斜率可以得到主方向轴y=Kx+B，如式（8）：

（5）得到轮廓分解起始点。将主方向轴与轮廓的交点集中，与中心点距离最近的点作为轮廓分解的起始点。

3.2.2 参考点求取

采用等角度划分方法来对轮廓进行分解，该方法从分解起始点开始，每隔相同角度画一条过中心点坐标的方向轴，方向轴与轮廓的交点就成为一个采样点。提取的是商标图像最外层轮廓，因此当方向轴与轮廓有多个交点时，选取距离中心点距离最远的点作为采样点。这样如果将[0，360°]的范围划分为m个区间，所选取的采样点的个数即为m。本文将360°区间划分为20个等级，即选取的采样点个数m=20。

在对商标图像进行轮廓点集的采样后，对这些采样点进行特征描述。因为孤立地考虑单个采样点是没有意义的，较为普遍的做法是考虑以该采样点为中心的一段弧线段，对其进行特征描述。设轮廓点个数为n，采样点数目为m，以采样点d为中心，n/m为长度选取轮廓上的弧线段L，则可以将L作为采样点d对应的弧线段，因此对L的特征描述就可以作为采样点d的特征描述。

在采样点和弧线段之间可以建立一个向量集合，这个向量集合可以详细地描述弧线段L。为了能使获得的特征便于比较，同时具有不变性，采用Fourier变换来处理这个向量集合。

从采样点d到弧线段L的每个点引一个向量v=(x，y)，将向量v=(x，y)表示为复数形式为v=x+jy，这样便可以得到包含N/M个向量的向量集V(k)=xk+jyk。因为Fourier变换处理的是周期函数，为了使V(k)满足周期性，将V(k)中的值取反取一边，得到新的向量集V(k)=xk+jyk，对V(k)进行Fourier变换，如式（9）所示：

复系数a(u)为弧线段L的Fourier形状描述子。由于信号量的能量主要集中在低频部分，所以只需取前面p个系数即可较好地反映被描述弧线段的整体形状了，本文取p=12，即一个特征点用12维的傅里叶描述符来表示。

4 特征匹配与相似性度量

根据第2章和3章中的特征提取，可以得到的商标图像的轮廓特征向量GF和SIFT特征向量LF。在得到商标图像的轮廓特征向量GF和SIFT特征向量LF后，就可以通过对GF和LF进行多特征融合技术来得到所需要的组合特征MF。

使用D来表示两幅商标图像之间组合特征MF的距离大小，如果D1表示商标图像轮廓特征向量之间的距离大小，D2表示商标图像SIFT特征向量之间的距离大小，则融合轮廓特征向量GF和SIFT特征向量LF的计算表达，如式（10）所示：

从商标图像组合特征公式中可以看出，w1、w2分别表示商标图像全局特征和局部特征的权值大小，对于w1、w2的设定将采用用户反馈的方式来进行最优化。下面就用户反馈最优化权值w1、w2进行算法描述：

（1）初始设定权值{ω1，ω2}的大小。

（2）得到用户对第一次检索结果中最满意的前m幅图片，并分别计算每幅图片与待查询图片的轮廓特征距离D1(i)i=1，2，…，m，SIFT特征距离D2(i)i=1，2，…，m。

（3）分别计算上面轮廓特征距离，以及SIFT特征距离的平均值-D1和-D2。如果-Di平均距离越大，则表示特征i对于用户体验来说相对不是很重要，可以降低它的权值大小。

图4 商标库截图

（4）组合特征距离公式中，距离越小，图像越相似。因此，如果哪个特征不重要，那么应该分配较小的权值，因此权值{ω1，ω2}可由式（11）进行修正：

（5）用户根据修改的权值，进行下一次的检索，循环第（2）步，直到用户满意为止。

5 实验设计与结果分析

5.1 实验设计

查准率和查全率都是信息检索中标准的性能评价方法，能够很好地说明系统的性能。查准率定义为检索返回的相关图像与检索返回的所有图像的比率；查全率定义为检索返回的相关图像与图像库中所有图像的比率。查准率用于测量系统排出无关图像的能力，查全率用于测量检索相关图像的能力。查准率和查全率结合起来，描述了系统的检索成功率[12]。

查准率定义如式（12）：

为了对本文的组合特征进行有效性验证，共选取了10幅商标图像（分别表示为I1，I2，…，I10）作为目标图像进行检索，图像库为1 000幅商标（搜集了福布斯2010世界500强以及中国最具价值500企业的商标图像，如图4），返回50张结果图像。

首先，为了验证多特征组合对缩放、平移和旋转不变性，对10幅图像进行了多比例缩放和多角度旋转。这样，每幅图像产生10幅缩放图像和10幅旋转图像。商标图像库则有1 200幅商标图像，将该组实验为设为实验A。

其次，为了验证区域特征对于图像扭曲、遮挡和噪声的支持效果，选取的10幅图像进行扭曲、遮挡和加噪的处理，同样产生10幅扭曲图像和10幅遮挡、噪声效果图像，商标图像库仍为1 200，将该组实验设为实验B。

最后，为了验证组合特征的实用性，找到了一张仿“阿迪达斯”商标的“万达奴”商标（如图5），对“万奴达”商标图像和“阿迪达斯”商标图像分别进行了旋转和缩放处理，目标图像仍为20幅，将该组实验设为实验C。在实验C的基础上，可以进一步的测试用户反馈机制对于实验的提升效果，即在多特征组合的实验中多次通过用户满意度来调整各特征权值，最后达到稳定的效果。

图5 仿“阿迪达斯”商标的“万达奴”商标

5.2 实验结果与分析

（1）实验A实验结果与分析

图6是组合特征对实验A检索结果效果图（“东风日产”商标图像）；表1是10组实验样本各自检索结果的查准率与查全率。

从实验结果中可以看到，结果集基本满足了返回全部正确的基准图像，且都排在最前面。平均查准率和平均查全率分别为0.808和0.778，查准率和查全率都相对较高，说明该组合特征对于图像缩放和旋转有较好的支持。

图6 “东风日产”商标图像旋转性效果图

表1 旋转和伸缩样本查全率和查准率表

（2）实验B实验结果与分析

图7是组合特征对实验B检索结果效果图；表2是10组实验样本各自检索结果的查准率与查全率。

图7 “东风日产”商标图像扭曲性效果图

表2 扭曲样本查全率和查准率表

从实验结果数据统计中可以看到，平均查准率和平均查全率分别为0.584和0.602。相对图像旋转性支持，区域组合特征对于图像的扭曲效果相对较弱，但也基本能够满足人们对于检索结果的满意度。

（3）实验C实验结果与分析

图8是实验C检索结果的效果图，其查准率和查全率分别为0.60和0.59。

0.60的查准率和0.59查全率只能算基本合格，但在结果商标图像集中前几幅结果图像返回了正确的“阿迪达斯”商标，这样实际上已经满足了用户对于检索结果的要求。因为计算机的商标检索应该是辅助作用，只是将被仿商标从海量的商标图像库中提取出来并展示给用户，评判标准通常带有一定的主观性，所以在机器检索之后还应该有一个用户主观评判的过程。

图8 仿“阿迪达斯”商标检索效果图

为了进一步提高检索精度，采用了一般性的用户反馈机制对实验C进行权值调整。根据用户的反馈调整权重值，然后重新计算精度和查全率。图9是经过多次反馈的性能曲线。实验结果表明，当2～3次反馈后检索可以达到一个比较平稳的效果，为别为0.80和0.77。

图9 用户反馈检索效果图

同时为了更好地体现实验效果，加入了横向对比，即用已有的单一特征与组合特征对比，结果如表3所示。从表中可以看出，基于轮廓和SIFT组合特征的商标图像检索的查准率和查全率较其他几种方法有一定的提高。

表3 组合特征与常用形状特征查准率和查全率对比

6 结语

提出了一种基于轮廓和SIFT的组合特征提取和检索商标图像策略。与已有文献中形状的整体描述方法相比，本文的方法不但考虑了形状的局部特性在更加细致的层面上对形状进行了描述，而且对于图像的轮廓有更好的描述。从实验结果可以看出，该方法是一种行之有效的方法，检索精度有所提高，能够达到较理想的检索效果。在今后的工作中，还需要对一些方面进行思考和改进，比如考虑是否有更优的分解方法来对轮廓进行优化分解，对每一类轮廓找到一个最优的分解点数目。

[1]洪凡.商标及商标检索的意义[J].情报探索，1995（4）：6-7.

[2]Freeman H.Computer processing of line-drawing images[J]. Computing Surveys，1974，6（1）：57-97.

[3]Iivarinen J，Peura M，Srel J，et al.Comparison of combined shape descriptors for irregular objects in A F C[C]//Proceedings of the 8th British Machine Vision Conference，1997，2：430-439.

[4]姚玉荣，章毓晋.利用小波和矩进行基于形状的图像检索[J].中国图象图形学报，2000，5（3）：206-208.

[5]马跃先.二值商标图像检索系统[J].山西大学学报：自然科学版，1998，2l（2）：137-143.

[6]孙兴华.商标图像检索中子图像特征融合准则研究[J].南京理工大学学报，2002，26（5）：509-512.

[7]Guo Li，Huang Yuanyuan，Yang Jingyu.Using sub—block image features to retrieve trademark image[J].Journal of Computer-Aided Design&Computer Graphics，2004，16（7）：969-970.

[8]Smyths J R，Chang S F.Transform feature for texture classification and disseminations in large database[C]//Proc of IEEE Int Conf on Image Processing，Austin，Texas，1994.

[9]Rui Y，Huang T S，Mehrotra S.Relevance feedback：a power tool for interactive content-based image retrieval[J].IEEE Trans on Circuits and Systems for Video Technology，1998，8（5）：644-655.

[10]何斌，马天宇.VISua1 C++数字图像处理[M].北京：人民邮电出版社，2001：380-400.

[11]杨晓东，吴玲达，周文.利用轮廓分解和局部描述的二值图像检索[J].小型微型计算机系统，2010（11）：2260-2264.

[12]茹立云，彭潇，苏中，等.基于内容图像检索中的特征性能评价[J].计算机研究与发展，2003，40（11）：1566-1570.

XIANG Lei1,XIAO Shibin1，2,LIN Chunyu1，2,LV Xueqiang1，2

1.Chinese Information Processing Research Center,Beijing Information Science and Technology University,Beijing 100101,China
2.Beijing TRS Information Technology Co.,Ltd.,Beijing 100101,China

For the limitations of the description on single feature trademark image,a method of trademark image retrieval which is based on profile and SIFT characteristics is proposed.In this method,first step is to get profile by making trademark image to binary image,then contour decomposes the image using rule algorithm and does the Fourier transform on set of reference points of the decomposition.The Fourier coefficient is the profile feature of reference point.Then it detects extreme points on scale space of the trademark image,and describes the extreme points with feature which is SIFT characteristics description of trademark image.Finally,SIFT features is combined with profile features as a new feature for feature description of trademark image. Key words：profile feature;SIFT feature;contour extraction;profile decomposition;Fourier transform

针对单一特征对商标图像描述的局限性，提出了一种基于轮廓和SIFT特征组合的商标图像检索方法。该方法对二值化的商标图像进行轮廓提取，采用规则算法对其进行轮廓分解，对分解的参考点集进行Fourier变换，将得到的Fourier系数作为参考点的轮廓特征。针对商标图像的尺度空间进行极值点检测，并对检测到的极值点进行特征描述，该特征描述即为商标图像的SIFT特征描述。最后，SIFT特征与轮廓特征进行特征融合，并将融合后的组合特征作为对商标图像的特征描述。

轮廓特征；SIFT特征；轮廓提取；轮廓分解；Fourier变换

A

TP391

10.3778/j.issn.1002-8331.1112-0552

XIANG Lei,XIAO Shibin,LIN Chunyu,et al.Trademark images retrieval based on SIFT feature and profile feature. Computer Engineering and Applications,2013,49（19）：167-172.

国家自然科学基金（No.60872133）；北京市教委科技发展计划项目（No.KM201110772021）；国家科技支撑计划课题（No.2011BAH11B03）。

向雷（1987—），男，硕士生，主要研究领域为数字图像处理。E-mail：xiangleixu@126.com

2012-01-04

2012-03-23

1002-8331（2013）19-0167-06

CNKI出版日期：2012-05-31http://www.cnki.net/kcms/detail/11.2127.TP.20120531.1542.002.html

book=172,ebook=177