任帅，张翌翀

面向手绘草图检索的边界点选择算法

任帅，张翌翀

尽管通过文本进行图像检索已经被广泛应用，但有些时候仍很难用文本来描述复杂图片的结构信息。而在基于手绘草图的图片检索中，可基于绘制草图来检索与其相关的图片，这对于用户非常有吸引力。提出一种新的边界点选择算法对边界点进行筛选和优化。通过在局部区域中对边界点进行筛选，保留了主要边界的信息，并将该方法应用于3种不同的草图检索算法中。通过在两个公开数据集上的实验，结果表明所提出的方法可同时提高检索的准确率和时间效率。

手绘草图检索；边界提取；轮廓提取；图片检索

0 引言

随着网络多媒体的发展，越来越多的搜索引擎如Google、Baidu、Tineye等已开始提供基于内容的图片检索功能。用户可以选择上传一幅图片，然后由服务器返回与之相似的图片集合，但有些情况下用户可能无法提供检索用的图片，如可让用户通过自行绘制一些草图来进行图片检索，将极大增加搜索的灵活性。

手绘草图检索(Sketch-based Image Retrieval)的目的在于通过用户提供的草图，检索出与之相关的图片[1～3]。尽管这一问题在上世纪90年代就已开始被研究，其中仍然存在两个主要的问题：(1)如何准确衡量一张草图与一张图片之间的相似程度；及(2)如何构建高效的检索架构。这两个问题通常相互制约，具有高准确率的算法往往耗费非常大的时间开销，而提高检索速度的同时往往则会牺牲一定的准确率。对于第一个问题，目前主要的方法是基于特征的匹配和基于边界点的匹配方法。而对于第二个问题，目前主要是通过建立反向索引及通过对特征进行聚类以减少搜索量等方式来进行优化。

与常规的基于内容的图片检索相比，草图本身缺乏颜色信息（通常仅由黑白的二值图片构成），因此边界（轮廓）信息常作为主要特征被应用于草图检索当中[4][5]。常见的基于边界特征的描述符有边缘直方图描述符(Edge Histogram Descriptor)、方向梯度直方图(Histogram of Oriented Gradient)等。由于草图中边界点以外地方的信息通常缺失，在Hu等的工作中利用草图初始的边界信息对草图其他部分的梯度分布进行估算，然后再使用HOG方法来提取特征进行匹配计算，该方法可以在一定程度上弥补信息的缺失，但其准确率依赖于对未知信息的估算[6]。不同于基于特征的方法，Shotton等使用一种基于边界点之间的匹配方法，其主要思路是在两幅图片之间为每个边界点寻找方向一致同时距离最为接近的点，这些点的距离之和的平均值构成了最终的匹配结果[7]。以上两种方法的侧重点均为匹配的准确率而非效率。

为提高手绘草图检索的效率，Etiz等在其工作中使用视觉词袋(Bag of Visual Word)的方法，基于K均值算法对已有特征进行聚类，从而降低检索时需计算的特征数量（主要是因为检索时只需要计算与各聚类中心的距离）[1]。该方法虽然可在一定程度上提高检索的效率，但检索的准确率依赖于所使用的特征及聚类的结果好坏，另一方面视觉词袋方法很难直接应用于基于边界点的匹配方法之中。Cao等人提出一种基于反向索引的方法，将每一个边界点视为一个三元组其中前两项为位置信息，最后一项为梯度信息，通过构建反向索引极大降低检索的复杂度，但该方法中储存索引信息需要占用大量的内存空间[2]。

不同于上述诸多方法，本文所提出方法重点关注初始边界点的选择对于手绘草图检索的影响。通过针对图片的边界点进行筛选和优化，保留那些在视觉上更为显著的边界点，同时应用该方法于 3种不同的草图检索算法中并在两个公开数据集上进行测试。实验结果表明，所提出方法对于基于手绘草图的图像检索具有很强的适用性，可在一定程度上同时提高检索的准确率并降低计算代价。

1 边界点选择算法

在本文中，使用匹配代价(Matching Cost)来描述两幅图片之间的相似程度。通常而言，匹配代价越低则两幅图片愈发相似。基于手绘草图的图片检索算法往往包含预处理、计算匹配代价、生成最终结果等步骤，其框架如图1所示：

图1、基于手绘草图的图像检索基本框架

对于边界提取，常见的算法有卡尼算法(Canny)、索贝尔算法(Sobel)等，很多基于草图的检索算法直接使用上述算法返回的结果。一般情况下，通过适当的选择算法，对初始得到的边界点进行筛选，仅保留那些对于计算结果影响显著的点，则就可以在一定程度上降低各草图检索的计算量。因此，在所提出基于手绘草图的图像检索基本框架中，在预处理阶段特别考虑边界点选择这一步骤。

如图2所示：

图2、不同分辨率下的图片以及对应的边界信息示例

第一排从左至右分别为同一张图片在不同分辨率下的显示效果，第二排则是在对应的分辨率下较为显著的边界点通过观察发现，随着图片的分辨率逐渐变小，图片中一些边界点逐渐消失变的无法识别，而图片主要的边界部分却仍可以被人眼识别。由此，对于基于手绘草图的图像检索结果而言，这些显著的边界点应该对检索结果产生更大的影响。

1.1 边界提取

为得到边界点在不同分辨率下的显著程度，这里使用Liu等提出的方法进行计算[6]。该方法将图片I映射到不同的尺度t当中，如公式(1)：。

1.2LocalSelect边界点选择

如前所述，具有低尺度的边界点通常是那些视觉上不显著的边界点，则可设定一个全局额阈值来对图片中的边界点进行筛选。有关选择函数GlobaalSelect的定义，如公式(3)：

图3 针对不同取值方法所得到的边界点

为解决上述问题，不同于对于所有边界点采取同一个阈值，而是在一个局部区域中选择合适的阈值进行边界点筛选。对于图片p中的每一个边界点i，建立其局部区域的尺度直方图，如公式(4)：

基于上述处理，通过为每一个边界点单独计算阈值，相比于GlobalSelect中的全部移除，而保留部分处于低尺度的点。图3给出分别使用GlobalSelect和LocalSelect方法进行边界点选择的示例，其中分别取8和0.6，两种方法均移除27％左右的边界点，分别对应右侧的第二列与第三列（剩余的边界点使用白色标识），在右侧第一列中使用不同的亮度标识初始时所有边界点的尺度如图4所示：

图3、原始边界以及分别应用边界选择方法得到的结果

在图3(a)和(c)中，由于海平面附近的边界点的尺度很低，GlobalSelect方法将其移除掉，而LocalSelect方法则保留大部分海平面附近的边界点；在图3(b)中，两种方法均保留所有边界点。LocalSelect可以理解为“如果点i在其所处区域中相比其他点不是非常显著，则可以移除它”，如果某一局部区域内大部分点都处于低尺度，LocalSelect方法会保留这些点，以避免破坏图片中主要的边界结构。

2 对匹配代价计算过程的影响

由于LocalSelect对初始的边界点进行了筛选和优化，那么会在一定程度上影响匹配代价的计算。本节中我们讨论LocalSelect方法对于三类不同类别（基于特征、基于边界点、基于区域信息）的手绘草图检索算法匹配代价计算过程的影响。

2.1 集成LocalSelect的 Tensor算法

Eitz在其工作中使用Tensor描述子，其主要思想是为尝试用一个向量来描述一块区域中梯度的主要方向，该向量称之为该区域的结构向量(Structure Tensor)[3]。对图片中某一个点i，假设所求的向量为，其中为单位向量，则应该尽可能与点i所在区域中每一个点j的梯度平行，此时最大，可根据公式(7)构建如下方程求解.如公式（7）：

值得注意的是，在之前的计算中对于每个边界点都给予不同的尺度，则为利用这一信息引入加权系数w，重新定义的如公式(8)：

2.2 Edgel Index算法

不同于基于特征的方法，Edgel Index是一个基于边界点匹配的算法（在原文中被称为EI-2）[2]，主要使用OCM(Orient Chamfer Matching)方法,其基本思想为首先根据梯度方向将图片中所有的边界点划分为若干个区间，对于图p中的点i，在图q中寻找距离点i最近的点j，并且点i和点j处于同一个区间。其中，点i的匹配代价即i与j之间的欧氏距离，定义如公式(9)：

2.3 Adaptive Weighting算法

在之前的研究工作中，我们构建了自适应加权(Adaptive Weighting)算法，其主要思想在于点与点之间的匹配代价应考虑其邻近节点间的相似程度。在计算完初始匹配的匹配代价后，点i新的匹配代价定义如公式(10)：

3 实验结果与分析

为验证 LocalSelect边界点选择方法的有效性，分别将其应用于Tensor、Edgel Index和Adaptive Weighting算法之中。在所有试验中，图片均被缩放至同一尺寸，使用17x17大小的来构建，的取值范围是{0, 0.4, 0.6}，其中取 0值表示不使用边界点选择算法。

首先，测试LocalSelect方法对于一些基本形状的物体检索结果的影响，选用Caltech101测试集（大多为背景简单的图片）中的316张图片（主题分别为 barrel、butterfly、yin_yang、lamp与cup），并且绘制与之相关的6张草图，所使用的草图具体如图所示：

图5 针对Caltech101数据集所使用的草图示例

各算法前10个结果的平均查准率以及应用边界选择后所剩余的边界点数量如表1所示：

表1、各算法针对不同取值时前10个结果的平均查准率

表1、各算法针对不同取值时前10个结果的平均查准率

?

对于面向基本形状手绘草图的图像检索，在应用LocalSelect边界点选择方法后，随着增大其平均查准率均有不同程度的提高，在减少近三分一边界点数量的情况下，仍可增加一定平均查准率。

为进一步测试本文所构建的方法在更加复杂数据集上的效果，使用5,000张来自Eitz提供的图片以及31张手绘草图[1]。对于每个算法，计算其前 20个结果的平均查准率均值(Mean Average Percision＠20)，其相关实验结果如图所示。

图6 各算法针对不同取值时前20个结果的平均查准率均值

4 总结

在本文中，针对于基于手绘草图的图像检索，提出一种新的边界点选择方法，该方法可减少手绘草图检索算法中所需考虑的边界点数量。实验结果表明我们所构建的边界点选择方法不但降低草图检索算法的计算量，还在一定程度上增加其检索的准率。在未来研究工作中，我们将尝试构建一个可以实际应用的具有较高检索准确率和检索效率的手绘草图检索系统。

[1] M. Eitz, K. Hildebrand, T. Boubekeur, and M. Alexa.Sketch-based image retrieval: Benchmark andbag-of-features descriptors. IEEE Transactions onVisualization and Computer Graphics,17(11):1624-1636, Nov.2011.

[2] Y. Cao, C. Wang, L. Zhang, and L. Zhang. Edgel indexfor large-scale sketch-based image search. In Proceedingsof the 2011 IEEE Conference on Computer Vision andPattern Recognition, CVPR '11, pages 761-768,2011.

[3] M. Eitz, K. Hildebrand, T. Boubekeur, and M. Alexa. A descriptor for large scale image retrieval based on sketched feature lines. In Proceedings of the 6thEurographics Symposium on Sketch-Based Interfacesand Modeling, pages 29-36, 2009.

[4] R. Datta, D. Joshi, J. Li, and J. Z. Wang. Imageretrieval:Ideas, inuences, and trends of the new age.ACM Comput.Surv., 40(2):5:1-5:60, May 2008.

[5] Eitz M., Hays J., and Alexa M.. How do humanssketch objects? ACM Trans. Graph. (Proc.SIGGRAPH),31(4):44:1-44:10, 2012.

[6] Hu R. and Collomosse J.. A performance evaluation ofgradient field hog descriptor for sketch based imageretrieval. Comput. Vis. Image Underst.,117(7):790-806,July 2013.

[7] Shotton J., Blake A., and Cipolla R.. Multiscalecategorical object recognition using contour fragments.IEEE Trans. Pattern Anal. Mach. Intell.,30(7):1270-1281, July 2008.

[8] Liu X.M., Wang C., Yao H., and Zhang L.. The scale of edges. In IEEE Conference on ComputerVision and Pattern Recognition, pages 462–469, 2012.

Edge Point Selection for Sketch-based Image Retrieval

Ren Shuai，Zhang Yichong
(School of Computer Science, Shanghai Key Laboratory of Intelligent Information Processing,Fudan University, Shanghai 201203, China)

Although text-based approaches have already been used in Content-Based Image Retrieval, sometimes it is still very hard to represent an image structure precisely by keywords. Thus it would be an attractive pattern if the image user could draw a sketch and then use it to retrieve relevant images. In this paper, a novel local region-based edge point selection method is proposed and applied to three different Sketch-based Image Retrieval algorithms. The experiments on two public image datasets show that the proposed method could both increase the accuracy and efficiency of sketch-based image retrieval.

Sketch; Boundary; Contour; Image Retrieval

TP391.3

：A

1007-757X(2014)04-0034-04

2014.04.02)

科技支撑计划项目（2012BAH59F04）、上海市科委项目（12dz1500203，12511504902）

任 帅，复旦大学计算机科学技术学院，上海市智能信息处理重点实验室，硕士研究生，研究方向：图像识别及计算机处理，上海，201203

张翌翀，复旦大学计算机科学技术学院，上海市智能信息处理重点实验室，博士研究生，研究方向：计算机图像识别和处理技术，上海，201203