基于手绘草图骨架特征的三维目标检索方法

赵雪青，师 昕，陈惠娟

(1.西安工程大学 服装设计智能化陕西省重点实验室，陕西 西安 710048；2.新型网络智能信息服务国家地方联合工程研究中心，陕西 西安 710048；3.西安工程大学 计算机科学学院，陕西 西安 710048)

0 引 言

人类生活的三维世界，三维模型数据是继声音、图像、视频之后的第四代多媒体数据，能够更加逼真生动地展现三维物体，广泛应用于各个领域，如智能制造、虚拟设计、生物医学、影视特效等[1]。目前，人们已经能够运用各种有效的方法和手段,大量地采集和创建各种类型的三维目标模型数据。为了更好地组织分布在各地的三维目标模型数据,更好地访问和利用海量三维目标模型数据中包含的有用信息,三维目标检索是一种重要且有效的方式[2]。

自20世纪Cliffs[3]提出“信息检索”这一概念以来，针对三维目标检索问题的研究迅速展开，一般有两类：一类是基于文本语义的三维目标检索方法[4]。该类方法从文本语义标注入手，通过检索已标注的文本信息获取三维目标，由于简单的文本很难精确描述三维目标的具体特征，文本存在一定的二义性，且文本的标注需要手工完成，因此，该类方法难以取得较好的检索性能。另一类是基于内容的三维目标检索方法[5-6]，该类方法无需人工干预，从三维目标数据本身入手，提取出三维目标的底层特征，如三维目标的颜色、纹理、形状及立体结构关系等。由于大多数的三维目标数据文件中只有其几何属性与外观属性，而缺少高级的语义特征描述。因此，如何有效地描述三维目标的特征信息是三维目标检索的关键问题。

近年来，基于手绘草图的三维目标检索方法越来越受到学者们的重视[7]，草图相比于图像和文本信息，能够更加有效地表达三维目标的形状信息，因此，基于用户输入的草图检索相对应的三维目标具有重要的实际意义[8]。骨架草图是符号系统的一种特殊表达形式，由于具有创造性思维表达的灵活性、抽象思维的外化性和逻辑思想描述的自由性等优点，骨架草图成为感知用户界面不可或缺的一部分，同时具有语义、语法和模糊的特征，能够满足人们横向和纵向的思维活动[9]。Chen等通过勾画线条和添加关键字的方法来合成图像，根据关键词在图像库中搜索到相关图像[10]。Cao等提出一种描述手绘草图轮廓的局部特征，使用倒排索引结构进行检索，该特征和倒排索引结构分别解决手绘草图在百万级图像库上检索的准确性和实时性问题[11]。Eitz等提出一种手绘草图检索系统的评价标准，该标准能够较客观地评价手绘草图检索系统的准确性[12]。这些系统大多是基于图像底层特征进行检索，包括颜色、纹理、形状的通用性。但是这些检索系统使用的特征与人类视觉特性还有一定的差距，而且在检索过程中不能充分考虑三维目标的位置和空间关系等特征，故检索精度不高，效率也较低。

对此，文中提出一种基于骨架特征的目标检索方法，利用有向梯度直方图(histogram of oriented gradients，HOG)较好的边缘特性及较强的鲁棒性进行特征描述，同时鉴于支持向量机(support vector machine，SVM)具有良好的二分性及简单易用的特点，使用该方法实现三维目标的分类检索。

1 算法描述

基于骨架特征的目标检索算法，首先将三维目标多视角模型转化为二维图片，对其进行三维模型数据的绘制、收集及分类处理。按绘制图像细节特征的复杂程度将其分为三类，如图1(a)所示，把每一类的骨架图像分成多个部分，选择最能区分图像的某一部分作为初始检测区域，提取其HOG特征；再选取含不同数量的正负样本用分类器算法进行训练，采用SVM进行分类；最后使用第一类骨架图片与第二类和第三类的图片进行互检索。三维目标检索过程如图1(b)所示。

图1 数据集分类及三维目标检索过程

1.1 骨架特征

骨架作为物体抽象化表达之一，包含它的拓扑结构[13]。如图2(a)所示，一副完整的骨架图通常包括端点，接合点，连接点和骨架枝。有如下定义来准确地表达骨架特征[14]：

定义1：若一个骨架点在骨架上只存在于一个骨架点与其相邻，则该骨架点被称为一个骨架端点；若一个骨架点存在三个或更多的相邻点，则称其为骨架接合点；若一个骨架点既不是端点也不是接合点，则称其为骨架连接点，通常任意两个连通的骨架点之间的一段连接点组合称为骨架枝。

图2 骨架表示及手绘Spider1骨架图HOG特征图

1.2 HOG特征

HOG特征使用梯度或边缘的方向密度分布来表示局部目标的形状，其本质为统计图像边缘的梯度信息。文中的HOG特征提取过程如下：首先，对图像的颜色空间进行归一化，将检测窗口划分成大小相同的单元格，在每个单元格中分别提取相应的梯度直方图信息；然后将相邻的单元格组合成相互有重叠的块，统计整个块的直方图特征，并对每个块内的直方图进行归一化；最后对整个窗口收集所有块的HOG特征，并以特征向量的形式表示整个目标窗口的HOG。文中选用一维中心对称的高斯模板[-1,0,1]计算图像梯度以及方向，梯度模板水平和垂直方向的梯度计算公式分别为：

(1)

其中，Gx(x,y)、Gy(x,y)和H(x,y)分别表示输入图像像素点(x,y)处的水平方向梯度、垂直方向梯度和像素值。

像素点(x,y)处的梯度幅值和梯度方向分别为：

(2)

(3)

采用无符号的范围来限定梯度方向的范围：

(4)

计算单元格内梯度直方图时，选择每单元格8×8像素的2×2的单元格，分9个方向统计每个单元格的梯度信息，从而边缘信息可以用一个九维向量表示。在对特征向量进行归一化时，根据实验对比分析可以得出，采用L2-norm作为归一化函数，可以得到较好的目标检索效果。其定义如式5：

(5)

其中，ε是一个非常小的数，目的是防止分母出现0的情况。

通过以上步骤，以手绘草图骨架图Spider1为例进行HOG特征提取，其结果如图2(b)所示。

1.3 SVM

SVM旨在用于分类和回归分析，可以分析数据，识别模式[15]。其目标在某维度的样本空间求解一个距离间隔最大的超平面，该平面能够将所有样本有效分开，并且寻找与该超平面互相平行的两个最近邻平面，其中该组平面具有最大的距离间隔。对于多值分类问题，支持向量机需要把多值分类问题转化为多个二值分类问题，继而进行二值分类。文中将SVM通过输入标记好的训练样本，生成一个样本空间中最优化的分隔超平面。超平面表达式定义如下：

f(x)=β0+βTx

(6)

其中，β是权重向量，β0是偏置，|β0+βTx|=1为最优超平面，x为离超平面最近的训练样本，即为支持向量。

点x与超平面(β，β0)的距离为:

(7)

由上述最优超平面的表示，可求得训练样本中的支持向量与超平面的距离为:

(8)

由此可以得到间隔的大小，所以，两倍于支持向量与超平面的距离为:

(9)

最后，最大化margin等价于在一定约束下最小化函数L(β)，如式10约束条件隐含超平面正确分类所有的训练样本xi:

(10)

针对文中图像样本数据划分问题，采用高斯核函数把在低维空间中不可分的数据映射到高维空间，高斯函数取值范围固定为(0,1)，进一步减少支持向量机分类的难度。

2 实验设计及结果

2.1 测试数据

采用Etiz提供的数据库[9]，使用“骨架”一词来表示抽象的象形图。在Etiz数据集的基础上，使用Photoshop绘制及手绘方法扩展数据集，首先从Etiz数据集中选择20类对象，这些类别代表了大部分的事物特征，获得一个约3 000张图片的数据集。其次从最基本的骨架图片到具有复杂细节的数据集将每个类别的草图分成三类，如图1(a)所示，从而建立一个比较完整的测试数据集。

2.2 实验说明

基于上文搜集的数据库，以Matlab2017b为测试平台完成仿真实验，并使用查全率评价体系评估检索效果。查全率(recall ratio)[16]是衡量某一检索系统从总体数据集中成功检索出相关信息的一项指标，能够代表检索系统为用户查出相关图像的能力大小。查全率越高，即表示检索出相关图像的能力越强。查全率可以表示为：

(11)

其中，A为测试数据集中和查询数据相关的集合；B是检索返回的数据集；p为一次查询结果；r为一次查询中不相关的数据；q为数据集中和查询图像相关但是却没有查询到的结果。

2.3 实验结果

实验分为两组进行，利用第一类的骨架图片分别与第二类和第三类图片进行互检索，检索正确率结果见图3，互检索时间结果见图4。

2.4 实验分析

实验结果表明，该方法对于基于骨架的三维目标检索具有较好的性能，如图3中spider类，正确率达到80%，90%；bicycle类，正确率达到90%，95%；每类图形的个数不同，类别包含图形越多，检索出的正确率就越高，且对于一些实物(如bed，bicycle)的检索率会比动物(如cat，cow)的检索率要高一些。分析其原因，可能由于动物细节相对于实物较多，不论骨架绘制还是特征提取都有困难，因此对检索正确率有消极影响。

(a)第一类与第二类互检索正确率对比

(b)第一类与第三类互检索正确率对比 图3 互检索正确率对比

(a)第一类与第二类互检索时间对比

(b)第一类与第三类互检索时间对比 图4 检索时间对比

3 结束语

文中在前人研究的基础上拓展了3D骨架特征的数据库，并提出了一种基于骨架特征的目标检索方法，通过HOG特征提取边缘梯度方向特征，使用SVM训练分类。实验结果表明，该方法对于基于骨架图像的三维目标检索具有一定的效果，在检索时间上具有一定的优势。在未来的研究中将从检测的各个环节入手，改进算法，以期进一步提高检测速度。