基于边缘切线流场的多尺度结构张量图像检索算法

Foundation item: Supported by the National Natural Science Foundation of China(61472145)

基于边缘切线流场的多尺度结构张量图像检索算法*

张见威1黄达承1胡振朋1张菁2

(1.华南理工大学 计算机科学与工程学院, 广东 广州 510006； 2.大庆油田有限责任公司 第四采油厂, 黑龙江 大庆 163511)

摘要：为减小基于草图的检索技术中弱边缘的影响并提高特征的平移不变性,提出了一种基于边缘切线流场的多尺度结构张量检索算法.该算法采用边缘切线流场取代梯度场,在显著强边缘上计算结构张量以抑制弱边缘的影响,并在多尺度分区架构下进行结构张量特征的提取以增强特征的平移不变性.实验结果表明,与传统的结构张量方法相比,该算法有效地抑制了弱边缘的影响,避免了使用图像梯度方向描述图像显著边缘方向的不稳定性,增强了特征的平移不变性,提高了检索性能.

关键词：图像检索；线条草图；结构张量；边缘切线流场

收稿日期：2014-10-28

基金项目：* 国家自然科学基金资助项目(61472145)

作者简介：张见威(1969-),女,博士,副教授,主要从事图像和视频处理研究.E-mail: jwzhang@scut.edu.cn

文章编号：1000-565X(2015)05-0107-07

中图分类号：TP391.3

doi:10.3969/j.issn.1000-565X.2015.05.017

基于内容的图像检索(CBIR)技术利用图像自身所蕴涵的丰富视觉特征进行检索,能够有效地避免文本标注的主观歧义性.CBIR可分为基于样图的图像检索和基于草图的图像检索(SBIR).SBIR技术使用简单的没有颜色和纹理的手绘线条图像作为查询的输入,然后在大型图像库中检索与手绘线条图内容相关的图像.草图能更好、更快地描述要搜索的场景和对象,而且草图是检索者对查询图像进行的抽象,这给图像检索技术赋予了高层语义.如何用数学描述草图及图像库的图像,以及如何基于抽象的数学描述来评价图像库的图像与草图的相似性是SBIR技术的难点.

SBIR方法主要分为3大类:基于特征提取的方法、基于边界匹配的方法[1]和基于空间关系的方法[2],基于特征提取的方法是研究的热点,这类方法按照特征提取的策略和特征向量的构造方式可以分为基于全局特征的方法和基于局部特征的方法.许多SBIR方法是基于全局特征的.全局特征是用于捕捉一幅图像的整体特性,它的提取并不需要事先进行对象的提取或图像的分割,可以直接对整幅图像进行提取.例如,一种常用的方法是把一幅图像分成一些子图,计算每个子图的平均特征量,整幅图像以一个向量的形式来描述,向量中每一个分量对应某一个位置的子图.

1基于全局特征的SBIR算法

最早的QBIC系统[3]使用了基于全局特征的形状描述,全局特征包括面积、似圆度、离心率、主轴方向和不变矩等.Chalechale等[4]提出了基于角分区的方法,并采用了傅里叶变换使特征具有旋转不变性.Eitz等[5]对文献[4]方法进行改进,提出了基于角径向分区的方法.Springmann等[6]将ARP描述子与Keysers等[7]提出的图像变形模型相结合,提出了一种ARP描述子的变种.这类方法的问题是当每个角分区数量少时,旋转不变性会被削弱.另外,ARP描述子只简单利用边缘点数量信息,未利用边缘的方向信息.Saavedra等[8]提出了一种基于边界方向直方图的全局描述子(HELO),该描述子应用了生物特征处理中计算指纹方向场的方法.该方法将图像和草图分成k×k个不重叠的方块区域,通过计算每个区域的梯度创建一个有k个分区的角度直方图,采用直方图的L1距离度量相似性.常用的全局描述子还有边缘直方图描述子(EHD)[9-11]、梯度直方图描述子(HOG)等.EHD仅利用了边界方向类型的计数信息,没有考虑边界梯度响应的强度大小,具有该方向边缘响应的全部像素点都被赋予同样的权重.HOG描述子将图像和线条草图划分成k×k个不重叠的方块区域,计算每个分区的所有像素的梯度,进而确定每个分区中最强梯度的方向,该方法舍弃了梯度幅值小的像素点,保留了强梯度像素点,并构建了梯度直方图.HOG描述子也被用于人的行为检测[12].Narayana等[13]使用纹理特征GLCM的能量、反差、熵作为评判草图与图像相似度的特征向量,但纹理特征不适用于线条稀疏的草图,故检索性能不好,此方法只能作为缩窄检索范围的预处理.Eitz等[14]将结构张量作为描述子,取得了较好的检索效果.

EHD、HOG、HELO及结构张量描述子都是通过图像区域中的主要梯度方向来表征图像内容中的线条方向,会不同程度地受到图像中其他纹理梯度的影响,导致提取的方向不能对应用户视觉感知的线条方向.此外,以上算子都不具有平移不变性.为此,文中提出了基于边缘切线流场[15]的多尺度结构张量检索(ETFMSSTR)算法,在边缘切线流场上计算结构张量,并进行多尺度加权,以降低非主要边界的影响,并增强平移不变性.

2ETFMSSTR算法

2.1结构张量特征

相比于ARP、EHD和HOG特征,结构张量特征在检索性能上有很大的提高[14].EHD、HOG和HELO特征是在直方图中统计不同的梯度方向,用直方图分布来描述图像或草图.用户在检索时画的线条是图像主要场景或对象的边缘,而图像强梯度的方向正好垂直于边缘,故匹配草图的线条与图像中主要场景或对象的边缘,需要寻找一个方向来代表分区中的最主要梯度方向,结构张量是以此为出发点的一种特征描述方法.

全局特征提取方法将图像规则地划分成M×N个分区,使用一个张量来描述每个分区Cij的主要梯度方向.令x为一个单位向量,它表示一个分区中的最主要梯度方向,则

(1)

式中,guv为梯度.

将式(1)进行变换可得

(2)

式中,Gij是分区Cij中梯度张量积的和.使用拉普拉斯乘子计算式(2)的最大值,令(xTGijx)=0,可得

(3)

(4)

(5)

草图和图像的全局特征提取方法是一样的,采用Sobel算子计算出每个像素点(u,v)∈Cij在水平和竖直方向上的梯度分量,从而得到梯度guv.草图S和图像I之间的相似度用所有位置对应的分区Cij之间的结构张量的Frobenius距离和来表示,即

(6)

在此基础上,可以对结构张量特征进行优化.因为检索的依据是用户手绘的稀疏草图,并不是所有草图分区都有内容.因此,在检索前先建立一幅二值的区域掩膜,用来标识没有被用户输入的草图覆盖到的分区,这些分区不参与计算,在相似性距离计算中可以忽略.带有掩膜的结构张量特征具有更好的检索性能.由于结构张量的计算是在梯度场中进行的,因此受到图像中弱边缘和纹理的影响,与手绘草图结构张量的相似度度量差别很大.为此,文中引入边缘切线流场[15](ETF)代替原来的梯度场,以抑制弱边界、纹理和噪声对结构张量的影响.

2.2边缘切线流场

边缘切线流场是用于辅助生成自然图像的平滑连贯的线条画版本.ETF是一个平滑的方向场,它能有效地保留图像显著边缘的方向信息,从而获取图像重要的形状信息,同时也抑制图像噪声对图像显著边缘的影响.ETF的产生过程使用了一个非线性的向量模板去平滑由原图像梯度产生的方向场,这个模板能够保留显著的边缘方向,而弱边缘方向将被调整成在其邻域中最显著的边缘方向.同时这个平滑过程亦需保留锐利的边角,避免边缘方向流的回旋效应和防止弱方向被无相关性的强方向的影响.算法的输入为I的梯度图像I、图像梯度幅值、平滑滤波迭代次数Imax,输出为边缘切线流场t.

设要处理的自然图像为I(X),其中X=(x,y)表示图像中像素点的位置,像素点X的边缘切线方向为t(X),可认为t(X)垂直于X位置上原图像的梯度方向g(X)=I.ETF就是用t(X)作为曲线的切线方向,用其初始化ETF的边缘方向流.设t0(X)是ETF中X的边缘切线方向,t0(X)被初始化为I(X)的梯度方向的垂直方向,ti(x)=-I(y)和ti(y)=-I(x)表示在实现中取X的梯度I(X)方向逆时针旋转90°的方向,normalize(ti)表示对ti(X)做归一化处理得到单位向量,并记录原来梯度I(X)的幅值(X).

为了产生一个紧致的、领域对齐的向量场,定义向量平滑模板如下：

wm(X,Y)wd(X,Y)

(7)

式中,Ω(X)表示像素X的一个邻域,φ(X,Y)是一个符号函数,k是向量归一化的项,tcur(Z)是模板滤波前像素点Z位置上的边缘切线的单位向量,ws是空间关系权重,wm是向量幅值权重,wd是方向关系权重.ws、wm的计算式分别为

(8)

(9)

(10)

wm和wd在保留重要边缘特征方面起着重要的作用.符号函数φ(X,Y)是在对向量场进行模板平滑前用于对与tcur(X)的夹角大于90°的tcur(Y)进行方向反转,即

(11)

φ(X,Y)的作用在于引导向量场倾向于紧致对齐的,但同时也避免了回旋的方向流.

2.3ETFMSSTR算法描述

2.3.1边缘切线流场-结构张量

ETF产生的方向场更加平滑,在局部上能比较统一而且能趋向于一致的方向,不会产生局部向量回旋效应.因此,ETF更适用于图像重要的显著边缘信息的提取,边缘切线流场取代结构张量中的梯度场,更能使结构张量在描述主要边缘上发挥作用.为此,文中提出了边缘切线流场-结构张量(ETFST)的全局特征,将ETF与结构张量有机结合.ETFST的数学原理如下.

令x为一个单位向量,表示分区Cij中的最主要梯度方向,t(u,v)表示像素位置(u,v)的ETF流方向,则

(12)

将式(12)进行变换可得

(13)

s.t. xTx=1.

2.3.2多尺度特征提取方式

结构张量特征的特点在于统计出图像分区中最显著线条的方向.如果分区划分得太小,所提取的特征会不同程度地受到分区内其他弱噪声纹理梯度的影响;如果分区划分得过大,不同边缘交织所得到的特征信息对检索不具有意义.另外,以固定分区划分图像,特征的平移不变性有限,一旦草图在画面中的平移量超过了一个分区大小,则导致检索结果可能会完全不同.为此,文中提出了多尺度的特征提取方法.采用不同尺寸规格的分区方法来提取特征,用不同分区方式下计算所得相似度的加权综合作为最终结果,用于评价草图与图像的相似度.多尺度的分区划分方式如图1所示,实线是小尺度的紧密的划分方式,虚线是大尺度的稀疏的划分方式.

图1　多尺度的分区方式

文中将草图S和图像I之间的相似度用不同划分方式下所有位置对应的分区Cij之间的结构张量的Frobenius距离的加权和来表示,即

(14)

式中,wk为第k种区域划分方式对相似度贡献的权重,R为区域划分方式的数量.文中根据经验取wk值.

2.3.3算法流程

ETFMSSTR算法的主要原理是在多尺度分区方式下在ETF向量流场上提取结构张量特征,计算不同分区方式下结构张量的距离,以它们的加权综合作为最终相似度来检索图像.ETFMSSTR算法流程图如图2所示,主要包括以下步骤:

图2　ETFMSSTR算法流程图

(15)

对草图S进行同样的划分.

(2)边缘切线流场的生成.按照ETF生成方法,通过图像I或草图S的梯度图像初始化ETF,使用式(7)的向量平滑模板对图像I或草图S进行迭代滤波,生成最终的边缘切线流场.

F=(T(I,1),T(I,2),…,T(I,R))

(16)

该全局特征向量每个位置的分量对应着图像在第k种区域划分方式下位置(i,j)的子图.

3实验结果与分析

文中使用C++和OpenCV开源库实现了结构张量算法、ETFST算法和ETFMSST算法,3种算法的参数设置如表1所示,其中ETF算法的η=1、平滑模板大小为9、迭代次数为2,wk取经验值.

表1　3种算法的实验参数值

使用文献[16]所收集的31幅用户手绘草图作为ETFMSSTR算法的输入,并在其1240幅测试基准图像中进行检索.部分实验结果如图3(a)所示.使用文献[16]设计的测试基准对结构张量算法、ETFST算法和多尺度ETFMSSTR算法进行测试评分,即收集手绘线条草图,并让志愿者对图像与草图的相似程度进行打分,从而选取一些图像作为测试基准图像,每个草图对应着若干幅有相关度评级的图像;然后利用图像的评级进行计算从而得到评分,3种算法的基准得分分别为0.15171、0.19079、0.19211.可见,ETFST算法的检索性能较结构张量算法有了较大的提高,而ETFMSSTR算法的检索性能又比ETFST算法有稍微的提高.

从图3(a)可以看到:ETFMSSTR算法性能的提高得益于边缘切线流场的3个限制条件、边缘切线流场方向的平滑性和能表达图像的最主要强边缘方向;用结构张量算法得到的检索结果中,具有语义相似性的图像明显比ETFMSSTR算法的结果少.这是因为结构张量只是在梯度方向的基础上进行计算,不能抑制在用户看来是噪声的一些弱纹理梯度,而且梯度方向的描述不鲁棒.

从图3(a)中的用例可以看到,有一些检索结果与草图的语义相关性比较低,如用例5的检索结果中,与“风帆”具有相同语义的结果在前7幅图像中相对其他用例较少,这是由于用例5的草图中线条内容较少,而算法会根据草图的内容产生一个掩膜,这个掩膜在检索运算中排除没有线条内容的区域,这些区域不参与特征计算,因而对于用例5,在图像中参与相似性度量的区域相对较少,只要在这些参与运算的区域内部的主要线条方向与草图对应区域的线条方向相似,该图像即被认为是相关的图像.特别是用例5的第1幅相关图像,图像中间水面的线

图3　ETFMSSTR算法和结构向量算法的部分实验结果

条几乎与草图是一致的,而水面上的石头纹理也具有斜向下的强烈线条,故它被认为与“风帆”草图相似性最高的图像.因此,当用户输入的草图线条极少时,ETFMSSTR算法的检索结果中排名靠前的图像很可能并不具有很强的相关性,这是因为草图线条较少,掩膜排除的草图区域太多,从而图像中只有少量对应区域参与运算，而这些区域刚好与草图的线条相似,并不是因为图像与草图整体相似.这也说明了ETFMSSTR算法缺乏语义性,只要是图像在相同位置具有相同方向的强线条,则可能被认为是相似图像.

全局方法与局部方法各有特点,分别对应不同的应用场景,在现实中都有重要的研究价值.全局方法针对用户希望搜索与位置有一定相关性的场景,而局部方法针对用户希望搜索与所画草图位置和大小不相关的场景.两种方法对用户意图的理解不同,不具有强的可对比性,因此文中选取全局方法作为研究对象,并没有与局部方法在测试基准中进行对比,只是在全局方法的范围内与目前较好的结构张量全局方法进行比较.

4结论

对基于全局特征的检索算法进行两方面的改进,提出了基于边缘切线流场的多尺度结构张量检索算法.该算法在边缘切线流场上计算结构张量,在多尺度分区形式下进行结构张量特征提取,使得相似性度量中大尺度的分区形式具有较高的权重,从而更有效地避免噪声纹理产生的梯度的影响.实验结果表明,该算法有效地避免了使用图像梯度方向来间接描述图像显著边缘方向的不稳定性,使得结构张量能直接在显著的强边缘上进行计算,抑制了弱边缘的影响,并且多尺度的提取方式在一定程度上增强了特征的平移不变性.

基于草图的图像检索已经成为热门的研究领域,如何结合机器学习实现对草图的高层语义理解,这将是今后研究的重点,如果检索算法对图像的语义分类有好的效果,则基于内容的图像检索的性能也会得到提高.

参考文献：

[1]Cao Y,Wang C H,Zhang L Q.Edgel index for large-scale sketch-based image search [C]∥Proceedings of 2011 IEEE Conference on Computer Vision and Pattern Recognition.Colorado Springs:IEEE,2011:761-768.

[2]Sousa P,Fonseca M J.Sketch-based retrieval of drawings using spatial proximity [J].Journal of Visual Languages and Computing,2010,21(2):69-80.

[3]Niblack C W,Barber R,Equitz W,et al.The QBIC project,querying images by content using color,texture and shape [C]∥Proceedings of 1993 Storage and Retrieval for Images and Video Databases.San Jose:International Society for Optical Engineering,1993:173-181.

[4]Chalechale A,Naghdy G,Mertins A.Sketch-based image matching using angular partitioning [J].IEEE Transactions on Systems,Man and Cybernetics,2005,35(1):28-41.

[5]Eitz M,Hildebrand K,Boubekeur T,et al.An evaluation of descriptors for large-scale image retrieval from sketched feature lines [J].Computers and Graphics,2010,34(5):482-498.

[6]Springmann M,Kabary I A,Schuldt H.Image retrieval at memory’s edge:known image search based on user-drawn sketches [C]∥Proceedings of the 19th ACM International Conference on Information and Knowledge Management.New York:ACM,2010:1465-1468.

[7]Keysers D,Deselaers T,Gollan C,et al.Deformation mo-dels for image recognition [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(8):1422-1435.

[8]Saavedra J M,Bustos B.An improved histogram of edge local orientations for sketch-based image retrieval [C]∥Procee-dingsof the 32nd DAGM Symposium.Berlin:Springer,2010:432-441.

[9]Manjunath B,Salembier P,Sikora T.Introduction to MPEG-7:multimedia content description interface [M].New York:John Wiley & Sons Inc,2002.

[10]Chalechale A.Content-based retrieval from image databases using sketched queries [D].New South Wales:School of Electrical,Computer and Telecommunications Engineering,University of Wollongong,2005.

[11]Shih J L,Chen L H.A new system for trademark segmentation and retrieval [J].Image and Vision Computing,2001,19(13):1011-1018.

[12]Dalal N,Triggs B.Histograms of oriented gradients for human detection [C]∥Proceedings of 2005 IEEE Computer Society Conference on Computer Vision and Pattern Re-cognition.Washington D C:IEEE,2005:886-893.

[13]Narayana M,Kulkarni S.Content based image retrieval using sketches [C]∥Proceedings of 2012 International Conference on Advances in Computing.Bangalore:Sprin-ger,2012:1117-1123.

[14]Eitz M,Hildebrand K,Boubekeur T,et al.A descriptor for large scale image retrieval based on sketched feature lines [C]∥Proceedings of EUROGRAPHICS Symposium on Sketch-Based Interfaces and Modeling.New York:ACM,2009:29-36.

[15]Kang H,Lee S,Chui C K.Coherent line drawing [C]∥Proceedings of the 5th International Symposium on Non-Photorealistic Animation and Rendering.New York:ACM,2007:43-50.

[16]Eitz M,Hildebrand K,Boubekeur T,et al.Sketch-based image retrieval:benchmark and bag-of-features descriptors [J].IEEE Transactions on Visualization and Computer Graphics,2011,17(11):1624-1636.

Multi-Scale Structure Tensor Image Retrieval Algorithm

Based on Edge Tangent Flow Field

ZhangJian-wei1HuangDa-cheng1HuZhen-peng1ZhangJing2

(1.School of Computer Science and Engineering,South China University of Technology,Guangzhou 510006,Guangdong,China;

2.No.4 Oil Production Company,Daqing Oil Field Company Ltd.，Daqing 163511,Heilongjiang,China)

Abstract:In order to reduce the effects of weak edges and reinforce the shift invariance in sketch-based image retrieval(SBIR), a multi-scale structure tensor retrieval algorithm on the basis of edge tangent flow field is proposed. In this algorithm, edge tangent flow field is used as a substitute for the gradient map of image, and the structure tensor is calculated directly on remarkable strong edges to suppress the effects of weak edges. Besides, structure tensor feature is extracted in the form of multi-scale partition to enhance the shift invariance. Experimental results indicate that the proposed algorithm is superior to the existing structure tensor method because it helps suppress the effects of weak edges effectively, avoid instable significant edge of image described by image gradient direction, enhance the shift invariance of structure, and, thereby, improve the retrieval efficiency.

Key words: image retrieval;sketch;structure tensor;edge tangent flow field