基于NSCT边缘直方图的草图检索

陈 曦，肖 建

长沙理工大学 计算机与通信工程学院，长沙 410114

1 前言

随着图像数据的海量增长，常见的基于文本的图像检索方式已经很难满足需要，基于内容的图像检索技术变得至关重要。大家提出各种不同的基于内容的图像检索方式进行研究，包括基于例图、彩色简图、草图、或者这些的组合。草图（如图1所示）、例图、彩色简图更快捷更方便地描述用户所需要的场景。用户无法获取例图时，可以画出任意图形的草图。此外，触屏设备的快速增长使得应用草图更加便利。基于草图的图像检索是通过用户手绘的草图在图像库中匹配相似图像，以下简称草图检索。

草图检索中草图只有一些简单的轮廓形状信息，图像则含有丰富的颜色、纹理、形状信息，草图和图像间的信息不对称使得我们不能使用传统的描述符来描述这两者的特征。形状特征是草图与图像联系到一起的主要特征，本文主要研究基于边缘的形状特征描述方法，并将其与边缘直方图方法比较。

图1 草图

2 前期工作

2.1 边缘检测

草图主要是用线条来描绘图像形状，从普通的图像中提取线条称为边缘检测。边缘检测的研究也促进了用线条画来检索图像的发展。经典的边缘检测算子包括 Canny、Roberts、Sobel、Prewitt等，大都是利用图像梯度的极大值或二阶导数过零点值来检测图像边缘[1]，又或者利用微分算子跟图像卷积来获取边缘。经典算子抗噪性差，具有一定的局限性。近年涌现了许多新的边缘检测方法，主要是与遗传算法、神经网络、灰色理论、分形理论、小波理论等相结合的检测方法。

手绘草图的尺度、位置的不确定性，使得我们更加关注小波及类似小波的多尺度边缘检测。多尺度边缘检测[2-3]，将图像进行小波或类似小波的多尺度分解，并对各尺度进行相应的图像梯度幅值极大值检测，选取适当的阈值，再将各尺度的图进行融合得到边缘图像。多尺度边缘检测能够有效地抑制噪声，同时又能够满足草图的不确定性，应用到草图检索中能够有效提升检索效果。

2.2 草图检索

早期的图像检索系统QBIC[4]和Visual Seek[5]中就提到了粗线条的草图检索。2009年推出的一个草图检索系统MindFinder[6]，不仅可以在形状结构上检索，而且可以在语义和色调上满足用户的需求。

文献[7]提出了一种GF-HOG算子，将图像和草图均变换到梯度域，提取多尺度下的边缘梯度直方图作为特征向量，并利用视觉词袋模型进行检索。文献[8]提出一种基于方向梯度计算边缘特征点的方法，同时提出了一种评价大规模草图检索系统的标准程序。随着边缘检测等相关研究的不断发展，许多研究机构够都关注到草图检索，并提出了各种算子及检索方法[9-12]，在这里就不一一列出。

本文提出了一种基于NSCT边缘直方图的图像检索方法。首先，经过NSCT变换进行图像分解，得到图像的高频方向子带和低频子带。选择NSCT变换是因为它具有多尺度特性和平移不变性，能够很好适应草图的多样性。其次，对变换后各子带图像进行边缘检测及边缘直方图提取。变换后的方向子带中包含方向信息，边缘检测能够有效地检测该方向的轮廓形状，边缘直方图表达了5种边缘子图的空间分布，有效地表达了图像目标的形状信息。最终，进行相似度匹配获取检索结果。本文算法充分利用了图像的轮廓形状信息，通过将NSCT边缘检测跟边缘直方图相结合并应用到草图检索中，有效地提高了检索性能。

3 基于NSCT边缘直方图的图像检索

3.1 NSCT变换

Nonsubsampled Contourlet变换[13]是一种超完备变换。它是由非降采样金字塔滤波器（Nonsubsampled Pyramid（NSP））和非降采样方向滤波器组（Nonsubsampled Directional Filter Bank（NSDFB））构成，且具有可变多尺度多方向、多分辨率和平移不变特性。

非降采样金字塔滤波器（NSP），由多个不进行上下采样的非降采样滤波器级联组成，如图2所示。NSP减少了采样，获得平移不变性。非降采样滤波变换是可以重构的，NSP的设计容易实现，也易于重构。非降采样方向滤波器组（NSDFB），通过去除传统的方向滤波器组的下采样操作，保留其重采样算子，使其自身具备平移不变性，结构如图3所示。

图2 非降采样金字塔滤波器Nonsubsampled Pyramid（NSP）

图3 非降采样方向滤波器组Nonsubsampled Directional Filter Bank（NSDFB）

图像的NSCT变换包含2级分解，首先图像通过NSP进行多尺度分解，接下来将NSP得到的结果由NSDFB进行多方向分解。NSP进行塔形分解，得到的是图像的高频和低频两部分。NSDFB处理的是图像的高频部分，进行方向分解得到多方向的高频子带。有效的NSCT系数代表了各个方向上的边缘，集合所有方向子带的有效系数则可以代表整个图像的边缘。

3.2 NSCT边缘直方图

边缘直方图[14]是通过统计图像的各边缘子图空间分布构成的。边缘直方图描述符表达了5种类型的边缘子图像，包括无方向边缘跟水平、垂直、对角和反对角边缘。在文献[15]中就已经将边缘直方图直接应用到草图检索中，它是将图像分割成互不重叠的图像块并统计每个图像块的边缘信息。针对NSCT变换系数的特点，利用NSCT变换后的子带图像进行边缘提取得到了高频方向子带和低频子带的边缘图，这些边缘图中包含了NSCT变换下的多尺度和多方向信息，边缘直方图可以有效地利用这些信息。NSCT边缘直方图是在NSCT变换的基础上，获取各子带各边缘子图，根据5种边缘算子（图4）对每个子图进行计算得到对应的边缘类型得到子图边缘直方图，最终将边缘直方图归一化。

图4 5种边缘算子

计算NSCT边缘直方图的步骤如下：

步骤3边缘提取。高频子带根据系数分类保留强弱边缘并抑制噪声，根据式（1）与

计算；低频子带用Canny算子进行边缘检测，得到低频边缘图像。

步骤4提取边缘直方图。对所有子带的边缘图像按4×4分为16块并提取边缘直方图，将各子带的边缘直方图进行归一化串联，并将其再次归一化得到图像的NSCT边缘直方图。

本文算法不考虑将各子带图像融合成边缘图。低频子图像体现了图像的整体轮廓，这里采用Canny算子提取低频边缘，Canny能够有效地检测弱边缘，低频边缘子图是图像边缘全面描述的依据。高频各方向子带图像经过边缘检测，体现出更多的边缘轮廓细节，包含了更多的方向信息。直接使用这些子带的边缘图进行全局的边缘直方图统计，有效地利用了NSCT变换的优势并减少特征维度。对于草图而言，它本身即是一个边缘图，提取特征时将不经过步骤3直接进入步骤4。图像和草图的方向边缘直方图一旦准备好，接下来就是要找一个很好的直方图相似性度量。使用欧式距离：

这个相似度量用于本文方法，用来比较图像和草图的方向边缘直方图。

直方图度量匹配步骤如下：

步骤1利用式（4）用D(H1,H2)计算草图和图像库中相关图像的方向直方图的相似度量。

步骤2取出所有图像中直方图相似度量最小的距离。

步骤3最常见的评价标准是，查准率和查全率。

4 实验

本文实验使用的是文献[8]中给出的草图检索标准数据库包含草图和各类图像。数据库中包含31幅草图，与草图相关的图像31类共计1 240幅图像，作为实验图像数据库。使用草图作为查询图，第一幅图像为检索草图，检索结果图像根据相似度值大小，从左至右从上到下一次排列。

图5 检索结果图

实验时将NSCT边缘直方图与边缘直方图[15]、SIFT算子[7]、GF-HOG 算子[7，9]相比较。实验中，NSCT变换分解层数为3层，高频方向为8、16。边缘直方图、SIFT算子、GF-HOG算子、8方向的NSCT边缘直方图、16方向NSCT边缘直方图特征维度分别为80、128、3 780、2 000、3 920。实验采用最常见的查准率（6）和查全率（7）进行算法比较。综合多次查询，得到平均查准率、查全率，比较结果如图6、图7、表1、表2所示。

从实验结果可以看出，在草图检索中NSCT边缘直方图优于边缘直方图、SIFT算子，对边缘直方图的改进是有效的，NSCT边缘直方图可以有效地表达图像的形状特征。采用8方向NSCT边缘直方图效果有所提高，但相比较于GF-HOG算子还是有差距的，这跟NSCT变换的方向细化程度存在一定关系的。当NSCT变换方向增加时特征维数增加，NSCT变换的复杂度也会有所增加，同时从实验数据可以看到16方向NSCT边缘直方图的检索效果有了更好的提升，优于GF-HOG算子，是有效的。本文算法传承了边缘直方图算法的优点，同时具有平移、旋转和尺度不变性，融入了NSCT变换的多尺度多方向特性，形状描述更准确。

表1 查准率

表2 查全率

图6 查准率曲线

图7 查全率曲线

5 结束语

本文提出了一种基于NSCT边缘直方图的草图检索方法，利用NSCT边缘检测后得到的所有子带，提取边缘直方图。这种方法充分利用NSCT变换和边缘直方图的特性，有效地利用了图像的边缘信息，一定程度上解决了草图与图像间的不对称。通过实验表明该算法是有效的，但对于轮廓模糊的数据库图像检索效果是有待继续改进。

[1]Carpinterin A，Cornetti P，Kolwanker K M.Calcaulation of tensile and flexural strength of disorded materials using fractional calculus[J].Chaos，Solitons and Fractals，2004，21（3）：623-632.

[2]Ren Xiaofeng.Multi-scale improves boundary detection in naturalimages[C]//European Conference on Computer Vision，2008.

[3]尚政国，赵春晖，孙岩，等.非降采样Contourlet图像边缘检测算法[J].光电子·激光，2009（4）：525-529.

[4]Ashley J，Flickner M，Hafner J L，et al.The query by image content（QBIC）system[C]//SIGMOD Conference，1995.

[5]Smith J R，Chang S F.Visualseek：a fully automated content-based image query system[C]//ACM Multimedia，New York，NY，USA，1996：87-98.

[6]Cao Y，Wang H，Wang C，et al.MindFinder：interactive sketchbased image searchon millions of images[C]//Proceedings of the 18th ACM International Conferenceon Multimedia，Florence，Italy，2010：1605-1608.

[7]Hu R，Barnard M，Collomosse J.Gradient field descriptor for sketch basedretrieval and localization[C]//IEEE International Conference on Image Processing（ICIP），2010.

[8]Eitz M，Hildebrand K，Boubekeur T，et al.Sketch based image retrieval：Benchmarkand bag-of-features descriptors[J].IEEE Transactions on Visualization and Computer Graphics，2011，17（11）.

[9]Rui Hu，Wang Tinghuai，Collomosse J.A bag-of-regions approach to sketch-based image retrieval[C]//IEEE International Conference on Image Processing（ICIP），2011.

[10]Abdolah C，Naghdy G，Merlins A.Sketch-based image retrieval using angular partitioning[C]//Proceedings of the 3rd IEEE International Symposium on Signal Processing and Information Technology，IEEE，2003.

[11]Cao Y，Wang C，Zhang L，et al.Edgel index for large-scale sketch-based image search[C]//Proc of the 24th IEEE Conference on Computer Vision and Pattern Recognition，Colorado USA：Springs，2011：761-768.

[12]Konstantinos B，Izquierdo E.Large scale sketch based image retrieval using patch hashing[J].Advances in Visual Computing.Berlin Heidelberg：Springer，2012：210-219.

[13]Cunha A L，Zhou J，Do M N，The nonsubsampled contourlet transform：theory，design and applications[J].IEEE Transactions on Image Processing，2006，15（10）：3089-3101.

[14]Sikora T.The MPEG-7 visual standard for content description-an Overview[J].IEEE Transactions on Circuits and Systems for Video Technology，2001，11（6）：696-702.

[15]Eitz M，Hildebrand K，Boubekeur T，et al.An evaluation of descriptors for large-scale image retrieval from sketched feature lines[J].Computers& Graphics，2010，34（5）：482-498.