融合傅里叶描述子和尺度不变特征转换特征的商标检索

フ 要:针对传统商标检索算法中全局特征容易造成误检，而局部特征SIFT对轮廓描述能力不强及算法复杂度高的问题，提出了一种融合图像全局特征和局部特征的商标检索算法。其中全局特征反应了图像的整体信息，这些信息可用来较快地建立候选图像库，而局部特征则可以更准确地与候选图像进行匹配。首先提取图像的傅里叶描述子进行初步检索，并按相似度排序，然后在此结果集的基础上对候选图像通过提取SIFT特征进行精确匹配。实验结果表明，该方法既保持了SIFT特征较高的查全率和查准率，优于傅里叶描述子单一特征，而且检索速度比SIFT单一特征显著提高，能很好地应用于商标图像检索系统中。

ス丶词:基于内容的图像检索；商标；傅里叶描述子；尺度不变特征转换；全局特征；局部特征

ブ型挤掷嗪: TP391.41 文献标志码:A

Abstract: Traditional trademark image retrieval algorithm only using global feature easily make mistaken retrieval, and Scale Invariant Feature Transform (SIFT) features have limited descriptive ability for image contour and high algorithm complexity. According to the problem above, a new retrieval algorithm for trademark was proposed which combined the global feature and the local feature of images. The global feature reflects the overall information of the image that can help to build the candidate image database quickly, while the local feature can be matched with the candidate images more accurately. Firstly, extract Fourier Descriptor (FD) of the retrieved image and sort them according to similarity. And then, based on this result, the candidate images were matched accurately through extracting the SIFT features. The experimental results show that this method not only keeps high recallprecision of SIFT features and is superior to the method based on the single FDs feature, but also compared to the single SIFT features it effectively improves retrieval speed. This method can be well applied in the trademark image retrieval system.

Key words: ContentBased Image Retrieval (CBIR);trademark;Fourier Descriptors (FD); Scale Invariant Feature Transform (SIFT); global feature; local feature

0 引言

形状是商标的显著特征，对于商标图像主要以形状特征作为相似性判断的标准。在基于形状检索的研究中有两种思路：一种是全局匹配，强调对整体图像的形状、轮廓特征分析；另一种是局部匹配，强调对商标图像内部对象的个体特征分析［1］。近年来，已提出了许多不同的利用形状特征的商标图像检索方法，如：Qi等人［2］用相邻边缘与质心外接圆半径直方图及特征点距左上角距离直方图来描述形状特征；操峰等人［3］利用改进的小波模极大值结合不变矩法，借助类似信号奇异性检测的模极大值线搜索的思想使图像边缘定位更精确、抗噪性更出色；郭丽等人［4］提出了一种子图像形状和空间结构的多级商标图像检索算法；Wei等人［5］结合商标全局特征及内部结构取得了较好检索效果。文献［2-3］是基于全局特征的方法，此类方法的问题是仅能识别具有相似轮廓的图像，而忽略了内部结构，可能造成误检；文献［4］将图像划分为单元子图像弥补了全局特征的缺点，同时考虑了形状特征和子图像的空间位置，但常常受图像分割效果和单元子图像的空间位置变化的影响，而造成误检。

由于尺度不变特征转换(Scale Invariant Feature Transform,SIFT)特征［6］对图像局部信息具有良好的描述性能，近年来被广泛应用于图像匹配中。林传力等人［7］ 、刘瑞等人［8］利用SIFT描述子进行商标检索，结果表明对于相似的图像或子图像该方法具有良好的识别能力，对尺度、镜像、旋转等具有很好的不变性，表现出很强的抗遮挡和噪声的能力。然而，该方法不足之处在于：一是对图像的轮廓描述能力不够强，二是SIFT描述子是一种高维向量，文献［7］中每个特征点用128维向量表示，同时每幅图像又可产生大量的SIFT特征点。因此，迭代匹配处理导致大量计算时间和相对大量的存储空间去存储局部描述符。

针对上述不足，本文通过融合图像的全局特征和局部特征提出一种快速而准确的商标检索算法，首先提取全局特征傅里叶描述子［9］进行初步检索，对检索结果进行相似度排序，然后在此基础上通过提取SIFT特征来进一步准确匹配。实验表明本文的方法可快速准确地进行商标检索，克服了局部描述符的缺点。

1 傅里叶描述子

1.1 傅里叶描述子的提取

傅里叶描述子的基本思想是：设物体的形状是一条封闭曲线，沿边界曲线上一个动点s(k)=[x(k),y(k)]是一个以形状边界周长为周期的函数。这个周期函数可以展开成傅里叶级数。傅里叶级数中的一系列系数a(u)е苯佑氡呓缜线形状有关，称为傅里叶描述子，其计算公式为：

a(u)=∑K-1k=0(x(k)+jy(k))e-j2πuk/K;u=0,1,…,K-1(1)

傅里叶描述子是物体形状边界曲线的傅里叶变换系数，它是物体边界曲线信号的频域分析结果。根据傅里叶变换的性质，傅里叶描述子与形状尺度、方向和曲线起始点s0в泄亍R元a(1)为基准进行归一化处理，得到归一化后的傅里叶描述子：

d(u)=a(u)a(1);u=1,2,…,K-1(2)

归一化后的傅里叶描述子d(u)Ь哂谐叨取⑿转和平移的不变性［10］。

1.2 傅里叶描述子相似度度量

本文采用欧氏距离计算归一化傅里叶描述子之间的形状差异：

dE=∑Mu=2di(u)-dj(u)2(3)

由于形状的能量大多集中在低频部分，傅里叶变换的高频分量一般很小且容易受到高频噪声的干扰，一般只使用归一化描述子的低频分量计算物体形状的相似差异(根据经验，取M=12)，dE越大，物体的形状差异越大。

2 SIFT特征

2.1 构建尺度空间，检测极值点，获得尺度不变性

尺度空间理论的主要思想是利用高斯核对原始图像进行尺度变换，获得图像多尺度下的尺度空间表示序列，再对这些序列进行尺度空间特征提取。

二维高斯核定义为：

G(x,y,σ)=12πσ2e-(x2+y2)/2σ2(4)

对于图像I(x,y)，在不同尺度下的尺度空间表示为L(x,y,σ)，它可由图像I(x,y)与高斯核的卷积得到，其中，σ是尺度因子。オ

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

为了提高在尺度空间检测稳定特征点的效率，Lowe提出了利用高斯差值(Difference of Gaussian，DoG)方程同图像的卷积求取尺度空间极值，用D(x,y,σ)表示，即用固定的系数k相乘的相邻的两个尺度的差值计算：

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

L(x,y,kσ)-L(x,y,σ)(6)

其中k是常数，文献［6］取k=2。オ

在实际的尺度不变特征点提取中，SIFT 算法将图像金字塔引入了尺度空间，图像金字塔的构建如图1所示。首先采用不同尺度因子的高斯核对图像进行卷积以得到图像的不同尺度空间，将这一组图像作为金字塔图像的第一阶(octave)。接着对其中的2倍尺度图像(相对于该阶第一幅图像的2倍尺度)以2 倍像素距离进行下采样来得到金字塔图像第二阶的第一幅图像，对该图像采用不同尺度因子的高斯核进行卷积，以获得金字塔图像第二阶的一组图像。依此类推，从而获得了高斯金字塔图像。每一阶相邻的高斯图像相减，就得到了高斯差分图像，即 DoG 图像。对 DoG 尺度空间每个点与相邻尺度和相邻位置的点逐个进行比较，得到的局部极值位置即为特征点所处的位置和对应的尺度。

为了寻找尺度空间的极值点，DoG 尺度空间中中间层的每个像素点都需要跟同一层的相邻8个像素点以及它上一层和下一层的9个相邻像素点总共26个相邻像素点进行比较，以确保在尺度空间和二维图像空间都检测到局部极值，如图2所示，标记为叉号的像素若比相邻26个像素的 DoG值都大或都小，则该点将作为一个局部极值点，所有这样的局部极值点就构成了候选特征点的集合。

2.2 特征点过滤并进行精确定位

极值检测得到的所有候选特征点需通过以下两步检验才能确定是稳定特征点：一是它必须与周围的像素有明显的差异，不能是低对比度的点；二是它不能是边缘点。

1)低对比度的点。

通过拟和三维二次方程可以找出低对比度的点。使用Taylor极数将尺度空间方程D(x,y,σ)д箍：

D(X)=D+DTXX+12XT氮2DX2X(7)

其中：D是DoG计算的结果；X是候选特征点之一。由D和X可以找到一个偏移量：オ

=-氮2D-1X2DX(8)

把式(8)代入式(7)中，得

D()=D+12DTX(9)

如果D()≥0.03，г虮A舾锰卣鞯悖否则该点是低对比度的点，要丢弃。

2)边缘处的点。

去除不稳定的边缘响应点：利用一个2×2的Hessian矩阵，记作H，Ъ扑阒髑率。而HУ奶卣髦涤氇DУ闹髑率成正比，我们可以借助Harris和Stephens提出的方法，只需求其特征值之比，而不需要求出其特征值。设Е,β分别是H的最大和最小特征值，r为它们的比值，即r=α/β。オ

H=DxxDxyDxyDyy(10)

Tr(H)=Dxx+Dyy=+β

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

Tr(H)2Det(H)=(α+β)2αβ=(rβ+β)2rβ2=(r+1)2r (11)オ

若ИTr(H)2Det(H)

2.3 为特征点分配方向值

利用特征点邻域像素的梯度方向分布特性为每个特征点指定方向参数，从而使算子具备旋转不变性。(x,y)ТΦ奶荻戎岛头较蚍直鹞：

m(x,y)=[(L(x+1,y)-L(x-1,y))2+

(L(x,y+1)-L(x,y-1))2]1/2

θ(x,y)=tan-1((L(x,y+1)-L(x,y-1))(L(x+1,y)-L(x-1,y))) (12)

在以特征点为中心的邻域窗口内采样，并用梯度方向直方图来统计邻域像素的梯度方向。梯度直方图的范围是0°~360°，其中每10°一个柱，总共36个柱。梯度方向直方图的峰值则代表了该特征点处邻域梯度的主方向，即作为该特征点的主方向。在梯度方向直方图中，当存在另一个相当于主峰值80%能量的峰值时，则将这个方向认为是该特征点的辅方向。一个特征点可能会被指定具有多个方向(一个主方向，一个以上辅方向)，这可以增强匹配的鲁棒性。

2.4 生成特征描述子

将坐标轴旋转为特征点的方向，以保证旋转不变性；再以特征点为中心取8×8的窗口(特征点所在的行和列不取)。在图3中，中央黑点为当前特征点的位置，每个小格代表特征点邻域所在尺度空间的一个像素，箭头方向代表该像素的梯度方向，箭头长度代表梯度模值，图中圈内代表高斯加权的范围(越靠近特征点的像素，梯度方向信息贡献越大)。然后在每4×4的图像小块上计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，形成一个种子点，如图4所示。此图中一个特征点由2×2共4个种子点组成，每个种子点有8个方向向量信息，可产生2×2×8共32个数据，形成32维的SIFT特征向量即特征描述符。

实际计算过程中，为了增强匹配的稳健性，Lowe建议对每个特征点使用4×4共16个种子点来描述，每个种子点有8个方向向量信息，这样对于一个特征点就可以产生4×4×8共128个数据，最终形成128维的SIFT特征向量即特征描述符。

2.5 匹配SIFT特征点

以两个特征点描述符之间的欧氏距离作为特征点匹配的相似度准则。假设特征点对p和qУ奶卣髅枋龇分别为Desp和Desq，г蚱渑肥暇嗬攵ㄒ逦：

d=∑i=0…127(Desp(i)-Desq(i))2(13)

将最近邻距离d1в氪谓邻d2У谋嚷屎驮は壬瓒ǖ你兄当冉弦匀范ㄊ欠衿ヅ涞教卣鞯恪＊

3 检索算法

算法的基本思想是：对参考图像分别提取傅里叶描述子和SIFT特征存入数据库中，如图5虚线以上所示。在进行商标检索时，将待检商标分别提取傅里叶描述子和SIFT特征，首先用傅里叶描述子与商标库中的傅里叶描述子进行比较，相似性度量并排序，形成候选商标图像集，然后对候选商标以SIFT特征进行精确匹配，进行相似性度量并排序，返回检索结果，其过程如图5虚线以下所示。

详细检索步骤如下：

步骤1 设检索图像为A，提取检索商标A的傅里叶描述子及SIFT特征；オ

步骤2 ЫA的傅里叶描述子向量与商标库中的每一商标傅里叶描述子向量进行相似性度量；オ

步骤3 将两幅商标的欧氏距离按从小到大排序，形成候选商标集；

步骤4 Т雍蜓∩瘫昙中取一商标为B，B的SIFT特征点集合为Fb，вKDTree为FbУ娜部元素建立索引；

步骤5 根据欧氏距离，使用最优节点优先(BestBinFirst,BBF)搜索算法得到Faе忻扛鲈素kiгKDTree中的近似kЫ邻(k取2)，设返回的2个最近邻特征点为f1, f2；オ

步骤6 根据d1/d2确定f1是否是kiУ挠行匹配；

步骤7 对所有kiе馗瓷鲜龉程，并统计在Fbе衅ヅ涞降乃有特征点的个数N；オ

步骤8 重复步骤4~7，商标A与候选商标集中的每幅图像计算匹配的特征点个数N；オ

步骤9 对匹配的特征点个数NО创哟蟮叫∨判颍返回检索结果。

4 实验结果分析

4.1 系统性能评价

本文采用规格化的RecallPrecision准则［11］作为系统性能评价标准。该准则是在传统的RecallPrecision准则中增加了对返回结果排序的考量，因此，对检索性能的衡量更加精确，可用于评价任何返回有序结果的检索系统。评价结果反映了本次检索的查全率和查准率，结果为1表示最优检索，为0则表示最差检索。其定义如式(14)和式(15)：

Rn=1-∑ni=1Ri-∑ni=1in(N-n)(14)

Pn=1-∑ni=1(lg Ri)-∑ni=1(lg i)lg (N!(N-n)!n!)(15)

其中：Rn，PnХ直鹗遣槿率和查准率；Ri是第iЦ鱿喙赝枷裨诩焖鹘峁中的排序；n是所有相关图像的个数；N是整个商标数据库的规模。

4.2 实验设计与结果分析

本实验是在Intel Pentium D CPU 3.40@GHz，2@GB内存环境下进行的，采用的语言为C++。实验中选用24张商标作为检索图像，对每幅图像分别做了旋转、平移、缩放、加噪、视角、遮挡、加亮、子图像与其无关内容的组合等变换，每张设计了12个基准图像，商标库为2B200张，以返回12幅图像作为检索结果。图6(a)为待检中国石化商标，图6(b)为傅里叶描述子检索结果，图6(c)为SIFT检索结果。在本文算法中先用傅里叶描述子对特征库检索，由于该特征检索性能较差，实验的置信水平如何设置是提高查准率和查全率的关键，本文采用相关反馈技术交互设置置信水平形成候选图像再进行SIFT检索，如图6(d)为傅里叶描述子置信水平设为0.03时检索结果。

傅里叶描述子、SIFT特征与本文算法的平均查准率、查全率和检索时间如表1所示。查全率/查准率(PrecisionRecall，PVR)曲线如图7所示，在不同置信水平下的查询时间如图8所示。

实验表明本文算法查全率、查准率接近SIFT特征，而检索时间显著降低，提高了系统性能。

5 结语

针对商标图像的特点，综合应用图像的全局特征及局部特征，提出了一种融合傅里叶描述子和SIFT特征的商标检索算法。通过融合全局特征，这些特征适当地代表了图像的全局信息，使用局部特征减少了图像的比较数量，因此，减少了处理时间，并且具有非常高的匹配率。今后要考虑结合其他特征改善算法来获取对商标图像更高的匹配率。

げ慰嘉南:

[1] 马玉国,武栓虎,宋宜斌.基于多特征抽取的商标图像检索［J］. 计算机工程与应用,2008,44(18):172-193.

[2] QI HENG, LI KEQIU, SHEN YANMING, et al. An effective solution for trademark image retrieval by combining shape description and feature matching［J］. Pattern Recognition,2010,43(6):2017-2027.

[3] 操峰,陈淑珍,魏丹.一种改进的基于内容的商标图像检索方法［J］.计算机工程,2006,32(16):174-176.

[4] 郭丽,黄元元,杨静宇.基于形状和空间结构的商标图像检索方法［J］.计算机应用与软件，2005,22(1):93-95.

[5] WEI C H, LI YUE, CHAU W Y. Trademark image retrieval using synthetic features for describing global shape and interior structure［J］. Pattern Recognition,2009,42(3) 386-394.

[6] LOWE D G. Distinctive image features from scaleinvariant keypoints［J］. International Journal of Computer Vision, 2004, 20(2): 91-110.

[7] 林传力,赵宇明.基于SIFT特征的商标检索算法［J］. 计算机工程,2008,34(23):275-277.

[8] 刘瑞.基于SIFT特征的商标检索技术研究［D］. 西安:西北大学,2010.

[9] PERSOON E, FU K S. Shape discrimination using Fourier descriptors［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence,1986,8(3):388-397.

[10] ISMAIL I A, RAMADAN M A, EIDANAF T S, et al. An efficient offline signature identification method based on Fourier descriptor and chain codes［J］. International Journal of Computer Science and Network Security,2010,10(5):29-35.

[11] EAKINS J P, SHIELDS K, BORADMAN J M. ARTISAN: A shape retrieval system based on boundary family indexing［J］. Storage and Retrieval for Image and Video Databases,1996,31(4):73-80.

[12] 苏杰，王卫星.基于曲率和熵矩阵特征的商标图像检索［J］.计算机应用，2009,29(2):453-455.