文章快速检索     高级检索
  山东大学学报(工学版)  2017, Vol. 47 Issue (4): 19-24  DOI: 10.6040/j.issn.1672-3961.0.2016.382
0

引用本文 

牟春倩, 唐雁, 胡金戈. 基于流形排序的三维模型检索方法[J]. 山东大学学报(工学版), 2017, 47(4): 19-24. DOI: 10.6040/j.issn.1672-3961.0.2016.382.
MOU Chunqian, TANG Yan, HU Jinge. A new 3D model retrieval method based on manifold ranking[J]. Journal of Shandong University (Engineering Science), 2017, 47(4): 19-24. DOI: 10.6040/j.issn.1672-3961.0.2016.382.

基金项目

中央高校基本科研业务费专项资金资助项目(XDJK2015C110);教育部“春晖计划”资助项目(z2011149)

作者简介

牟春倩(1992—), 女, 四川成都人, 硕士研究生, 主要研究方向为三维模型检索.E-mail:mcq0207@email.swu.edu.cn

通讯作者

唐雁(1965—), 女, 重庆人, 教授, 主要研究方向为智能科学.E-mail:ytang@swu.edu.cn

文章历史

收稿日期:2016-10-13
网络出版时间:2017-05-09 14:44:21
基于流形排序的三维模型检索方法
牟春倩, 唐雁, 胡金戈     
西南大学计算机与信息科学学院, 重庆 400715
摘要:针对现有的基于视图的三维模型检索方法大多将二维投影视图特征直接用于表示三维模型, 忽略不同视点下的二维投影视图特征的贡献度的问题, 提出一种基于流形排序的三维模型检索方法, 关注不同二维投影视图特征的贡献度。通过旋转三维模型获得34张不同视点的二维投影视图, 采用基于尺度不变特征变换(scale invariant feature transform, SIFT)特征的词袋模型提取34张二维投影视图的词频向量特征, 利用流形排序将同一个三维模型的34个词频向量特征聚合成一个三维模型特征。试验表明, 基于流形排序的三维模型检索方法能够有效地提高检索结果的准确率。
关键词三维模型检索    二维投影视图    SIFT特征    词袋模型    流形排序    
A new 3D model retrieval method based on manifold ranking
MOU Chunqian, TANG Yan, HU Jinge     
College of Computer and Information Science, Southwest University, Chongqing 400715, China
Abstract: Most existing view-based 3D model retrieval methods used features of 2D projection views to represent a 3D model directly, ignored their contributions to a 3D model. Therefore, a new 3D model retrieval method based on manifold ranking was proposed, which focused on the contributions of 2D projected views features. 2D projected views from 34 different viewpoints obtained through rotation, word frequency vector featuresextracted by bag-of-feature based on scaleinvariant feature transform (SIFT) features, then aggregated 34 word frequency vector features of a 3D model into a 3D model feature. The experimental results showed that our method improved the retrieval accuracy well.
Key words: 3D model retrieval    2D projected view    SIFT feature    bag-of-feature    manifold ranking    
0 引言

随着计算机图形学和数字媒体的高速发展, 三维模型的应用越来越广泛。由于创建逼真度较高的三维模型需要耗费大量的时间和精力, 有时候只需要对已有的三维模型进行局部修改就能使用[1], 因此如何从已有的三维模型库中迅速、准确地检索出与要求相同或相似的三维模型已成为近年来的研究热点[2]。根据提取的特征的不同, 可以将这些方法分为3类:基于几何的检索方法、基于视图的检索方法、基于多特征融合的检索方法[3]。基于几何的检索方法通过提取三维模型的几何特征进行检索, 如OSADA Robert[4]等人提出的Shape Distributions算法和MIRELA Benchen[5]等人提出的Conformal Factor算法等。基于视图的检索方法则利用三维模型的视图特征进行检索, 如CHEN Dingyun[6]等人提出的Light Field算法和OHBUCHI Ryutarou[7]等人提出的基于SIFT特征的三维模型检索算法等。基于多特征融合的检索方法通过融合多种特征进行检索[8], 如LI Bo[9]提出的一种融合4种不同特征的ZFDR算法, 分别融合了泽尔尼克矩特征(Zernike moments feature)、傅里叶描述特征(Fourier descriptor feature)、深度信息特征(depth information feature)和基于射线的特征(ray-based feature)。

基于视图的三维模型检索方法符合人的视觉感知特性, 检索效果较理想, 受到了广泛应用[10-11]。现有的研究成果大多将二维投影视图特征直接用于表示三维模型, 忽略了同一个三维模型的不同二维投影视图特征的贡献度, 在一定程度上降低了三维模型特征的准确性, 影响检索结果。对此, 提出一种基于流形排序[12]的三维模型检索方法, 充分考虑不同二维投影视图特征的贡献度。提出方法通过旋转三维模型得到不同视角的二维投影视图, 采用基于SIFT特征[13]的词袋模型提取二维视图的词频向量特征, 利用流形排序进行特征聚合, 将一个三维模型的多个二维视图特征聚合为一个三维模型特征, 此特征能更准确地表示三维模型。

1 相关知识 1.1 词袋模型

词袋模型(bag-of-feature, BoF)是当下十分流形的用于视觉分类的模型, 其思想源于文本磁带模型(bag-of-words, BoW)[7]。该模型将图像看作为文档, 即若干个“视觉词汇”的组合, 并且这些视觉词汇之间也是没有顺序的。与文本文档不同的是, 图像中的词汇不是现成的, 需要运用相应的特征提取方法从图像中提取出来。通常, 需要3个步骤:(1) 特征检测; (2) 特征表示; (3) 生成词典。

所用到的特征可以是任意一种特征, 词典生成后, 就可以利用词频向量来对图像进行描述。

1.2 SIFT算法

SIFT算法由LOWE D G[13]于1999年提出, 是一种提取局部特征的算法, 对旋转、尺度缩放、亮度变化具有不变性, 对视角变化、仿射变换、噪声也具有一定的鲁棒性, 信息量丰富, 适用于在数据量庞大的特征库中进行快速、准确的匹配。SIFT特征提取的过程有以下几个步骤:(1) 尺度空间的生成; (2) 检测尺度空间极值点; (3) 精确定位极值点, 为每个关键点制定方向参数; (4) 生成特征点描述子。LOWE D G[13]建议采用特征点所在尺度空间内4×4的窗口中计算的8个方向的梯度信息作为特征点描述子, 即一个128维的向量。

1.3 流形排序

ZHOU Dengyong[12]等人首次提出基于流形的排序方法。流形排序的方法可以利用数据集内在的流形结构。给定一个数据集X={x1, …, xq, xq+1, …, xn}⊂Rm, 其中xq为查询数据, 其余的为需要进行排序的数据。令f:XR表示一个排序方程, 其中每个值fi表示数据点xi的排序值。可以将f看作是一个向量:

$\mathit{\boldsymbol{f}} = {[{f_1}, \cdots ,{\rm{ }}{f_n}]^{\rm{T}}}$ (1)

y为一个标签向量, 表示为

$\mathit{\boldsymbol{y}} = {[{y_1}, \cdots ,{\rm{ }}{y_n}]^{\rm{T}}},$ (2)

其中:当xi为查询数据时yi=1;否则yi=0。流形排序算法步骤如下:

(1) 构建一个图G(V, E), 其中节点V为数据集X, 边E的权重表示为相似度矩阵W=[wij]n×n。归一化矩阵W

$\mathit{\boldsymbol{S}} = {\mathit{\boldsymbol{D}}^{ - 1/2}}\mathit{\boldsymbol{W}}{\mathit{\boldsymbol{D}}^{ - 1/2}},$ (3)
$\mathit{\boldsymbol{D}} = {\rm{diag}}\left\{ {{d_{11}}, \cdots ,{\rm{ }}{d_{nn}}} \right\},$ (4)

其中:${d_{ii}} = \sum\limits_j {{w_{ij}}} $

(2) 利用式(5) 进行迭代, 直到收敛:

$\mathit{\boldsymbol{f}}\left( {t + 1} \right) = \alpha \mathit{\boldsymbol{Sf}}\left( t \right) + \left( {1 - \alpha } \right)\mathit{\boldsymbol{y}},$ (5)

其中:α∈[0, 1)。

(3) 令fi*代表数列{fi(t)}的极值, 根据fi*对数据点xi进行排序。

流形排序算法的迭代过程可以直观地理解为建立一个图模型来模拟数据集内在的流形结构, 所有的数据点通过这个图模型来将它们的排序值传播给它的邻接点, 直至收敛到稳定状态为止[14-15]。参数α控制了初始排序值和邻域传播对最终排序值的贡献大小[12]

2 基于流形排序的三维模型检索方法

流形排序算法能够建立一个流形结构用于传播各个二维视图特征之间的相关性, 关注不同二维视图特征的贡献度。本研究通过旋转三维模型得到34张不同视角的二维投影视图, 采用基于SIFT特征的词袋模型提取二维视图的词频向量特征, 再利用流形排序聚合词频向量特征得到三维模型特征。方法框架图见图 1

图 1 方法框架图 Figure 1 The frame of the method
2.1 多视角投影

对人类而言, 描述一个物体最有效的方法就是描述其不同方向的视图。在描述一个三维模型时, 从不同角度看过去的视图有可能完全不同。因此, 如果仅仅用一个方向的视图不能够准确地描述出一个三维模型。用到的视图越多, 越能准确地描述出一个三维模型。获取一个三维模型的投影的方法有许多, 例如光场投影方法(light field)[6]和包围盒投影方法(cube-based)[9]。与其他方法不同的是, 本研究提出方法让三维模型分别围绕xyz轴旋转, 每次旋转30°, 从而获得不同方向的视图。一个钢琴模型的投影示例见图 2

图 2 钢琴模型的二维投影示例图 Figure 2 The projected images of a piano
2.2 提取词频向量特征

SIFT特征对选择、尺度缩放、亮度变化具有不变性, 能较好地表示图像。因此, 提取二维投影视图的SIFT特征用于构造视觉词典, 获取词频向量特征。

2.2.1 提取SIFT特征

利用SIFT算法, 检测二维投影的关键点, 得到二维投影的SIFT特征。SIFT算法可以从每张二维投影中检测到多个特征点, 每个点的特征为一个128维的向量。特征点检测示例见图 3

图 3 SIFT特征示例图 Figure 3 The SIFT feature of a piano
2.2.2 构建视觉词典

针对相似的SIFT特征点, 应该将它们视为同一个视觉词汇。利用k-means聚类算法对SIFT特征进行聚类, 构建词典, 得到k个相似的簇, 每一个簇代表一个视觉词汇。

2.2.3 获取词频向量特征

得到视觉词典后, 将二维视图的SIFT特征与词典进行比较, 通过统计词典中每个视觉词汇在二维投影中出现的次数, 即可得到二维视图的词频向量。词频统计示例见图 4

图 4 词频向量对应的直方图 Figure 4 The bar of a word frequency vector
2.3 流形排序聚合特征 2.3.1 构造流形图P

对于从三维模型库和待检索的三维模型的二维视图中提取的N个词频向量特征X={X1, X2, …, XN}, 将每一个特征视为一个节点, 通过在特征空间中连接相邻的节点来构造大小为N×N的关联矩阵W, 矩阵W为稀疏矩阵。矩阵W中的任一元素W(i, j)代表特征i与特征j的相似度。

$W\left( {i,{\rm{ }}j} \right) = \left\{ \begin{array}{l} {\rm{exp}}\left( { - d\left( {i,{\rm{ }}j} \right)/\sigma } \right),\\ \quad \quad \quad \quad \quad {\rm{if}}\;i \ne j\;{\rm{and}}\;j \in {\rm{KNN}}\left( i \right),\\ 0,{\rm{if}}\;i = j\;{\rm{or}}\;j \notin {\rm{KNN}}\left( i \right), \end{array} \right.$ (6)

其中: KNN(i)代表特征iK个近邻; d(i, j)为归一化处理后的L1距离; σ为距离的尺度参数0<σ<1。

关联矩阵W用于计算矩阵

$\mathit{\boldsymbol{P}} = {\mathit{\boldsymbol{D}}^{ - 12}}\mathit{\boldsymbol{W}}{\mathit{\boldsymbol{D}}^{ - 12}},$ (7)

其中:矩阵D是一个对角矩阵, 其第i个对角元素的值为矩阵Wi行所有元素的和, 计算过程见式(8); P(i, j)表示从特征i到特征j的关联性的转移概率。

$\mathit{\boldsymbol{D}}\left( {i,{\rm{ }}i} \right) = \sum\limits_{j = 1}^{{N_t}} {\mathit{\boldsymbol{W}}\left( {i,{\rm{ }}j} \right)} 。$ (8)
2.3.2 计算流形图P中的节点权重

为了避免特征间的突发性问题, 给流形图P中的突发性节点设定一个较小的权值, 非突发性节点设定一个较大的权值[16]。利用k-means算法将N个特征分为C个簇, 每个簇的权值wc为簇中所有特征的权值, 即流形图P中节点权值:

${w_c} = {\rm{ln}}\left( {1 + {N_M}/\sum\limits_{m \in {M_c}} {{f_{m,{\rm{ }}c}}} } \right),$ (9)

其中:NM为模型库中三维模型的个数, Mc为包含属于簇c的特征的三维模型, fm, c为属于模型m的特征在簇c中的个数。

2.3.3 聚合特征

首先, 为每一个三维模型m构造出标签向量

$\mathit{\boldsymbol{y}} = {\left[ {{y_1},{\rm{ }}{y_2}, \cdots ,{\rm{ }}{y_N}} \right]^{\rm{T}}},$ (10)

其中:对于特征集X, 如果Xi属于模型m的特征, 则yi=wi, wi为节点i的权值, 否则yi=0。

计算得到y后, 通过式(11) 获得三维模型的聚合特征。

$\mathit{\boldsymbol{f}}\left( {T + 1} \right) = \alpha \mathit{\boldsymbol{f}}\left( T \right)\mathit{\boldsymbol{P}} + \left( {1 - \alpha } \right)\mathit{\boldsymbol{y}},$ (11)

其中:T表示迭代次数, 它决定了在流形图上扩散的范围, f(0)=y, α为正则化参数且α∈[0, 1)。

2.4 相似度计算

根据三维模型的特征值, 可以计算任意两个三维模型mimj的相似度。设mimj的特征分别为FiFj, 且Fi=(a0, a1, …, an), Fj=(b0, b1, …, bn)。利用欧式距离计算三维模型mimj的相似度

$d\left( {{m_i},{\rm{ }}{m_j}} \right) = \sqrt {\sum\limits_{r = 0}^n {{{\left( {{a_r} - {b_r}} \right)}^2}} } $ (12)

其中:arbr分别为FiFj中对应的项。式(12) 计算所得距离越大, 模型间的相似度越低, 反之, 相似度越高。

3 试验 3.1 试验环境和数据

试验硬件环境为Acer Veriton D4300 Intel(R) Core(TM)i5-3470 CPU @ 3.20GHz, 4GB内存; 软件环境为32位的Windows7、MatlabR2010b、Vis-ual Studio 2013。

数据采用PSB模型库[17]和SHREC2012GTB模型库[18]中的三维模型。PSB模型库包总共包含了1814个模型, 并且被分为两组, 第一组是包含131个类的测试数据集, 第二组为包含129个类的训练数据集, 且每组数据集都包含907个模型。本研究利用训练数据集来生成词典。SHREC2012GTB模型库中总共包含了1200个模型, 其中有60个类, 每个类有20个模型。

3.2 评价标准

试验中, 为了客观地比较不同算法间的差异, 本研究采用Nearest Neighbor(NN)、First Tire(FT)、Second Tire(ST)、E-Measure(E)和Precision-Recall(P-R)曲线图[19]对检索结果进行评价。其中:NN表示返回的第一个模型属于目标类的比例, FT表示返回的的前C-1(C为目标类模型的数量)个模型属于目标类的比例, ST表示返回的前2(C-1) 个模型属于目标类的比例, E是综合查全率和查准率的指标, 且这4个指标的值越大, 代表结果越好。P-R曲线图则能体现总体检索效率, 曲线越靠右上角代表结果越好。

3.3 试验参数

试验中, 用到的参数分别为构建视觉词典时运行k-means算法的K1、构造流形图P时的尺度参数σ和运行KNN算法的K、计算流形图P中的节点权重时运行k-means算法的K2、聚合特征时的迭代次数T和正则化参数α。试验过程中, 参数的取值决定试验结果。针对不同的数据库, 通过反复调试参数值, 选取具有较好试验结果的值作为本研究方法中的参数值。试验中在两个数据库上的参数设置见表 12

表 1 PSB模型库上的试验参数 Table 1 Parameters for PSB
表 2 SHREC2012GTB模型库上的试验参数 Table 2 Parameters for SHREC2012GTB
3.4 试验结果

(1) PSB模型库

选取Bag-of-View-Words算法(BoVW)[20]、Light Field Descriptor算法(LFD)[6]、Spherical Harmonic Descriptor算法(SHD)[21]、Gaussian Euclidean Distance Transform算法(GEDT)[19]和Spherical Extent Function算法(EXT)[19]进行对比试验。

各个检索方法对应的NN、FT、ST和E见表 3, 这4项指标通过文献[19]所提供PSB_Util工具包中的psbTable.exe获得。各个检索方法的P-R曲线图见图 5, 横坐标R代表Recall, 纵坐标P代表Precision, 可以通过文献[19]提供的PSB_Util工具包中的psbPlot.exe计算并利用Matlab绘制曲线图得到。

图 5 6种检索方法的整体P-R曲线 Figure 5 P-R curve of the six methods for PSB
表 3 6种检索方法的定量比较 Table 3 Quantitative comparison of the six methods for PSB

(2) SHREC2012GTB模型库

选取Bag-of-View-Words算法(BoVW)[20]、ZFDR算法[9]、bag-of-features算法(BoF)[7]、3DSP-L2_1000_Chi2算法(3DSP)[18]和LSD-sum算法(LSD)[18]进行对比试验。

各个检索方法对应的NN、FT、ST和E表 4, 整体P-R曲线图见图 6

表 4 6种检索方法的定量比较 Table 4 Quantitative comparison of the six methodsfor SHREC2012GTB
图 6 6种检索方法的整体P-R曲线 Figure 6 P-R curve of the six methods for SHREC2012GTB

从试验结果可以看出, 针对两个不同的三维模型库, 提出的三维模型检索方法的检索结果都具有较高的准确率, 并且在整体性能上也优于其他方法。

4 结论

现有的基于视图的三维模型检索方法大多将二维投影视图特征直接用于表示三维模型, 忽略不同视点下的二维投影视图特征的贡献度, 影响检索结果的准确率。为了提高三维模型检索结果的准确率, 本研究通过旋转三维模型得到不同视角的二维投影视图, 采用基于SIFT特征的词袋模型提取二维视图的词频向量特征, 再利用流形排序将同一个三维模型的二维投影视图特征聚合成了一个三维模型特征用于表示三维模型。流形排序在聚合二维投影视图特征时, 建立一个流形结构用于传播各个二维视图特征之间的相关性, 通过设定流形图中各节点的权值, 有效避免二维视图特征之间的突发性问题, 并且关注不同视点的二维投影视图特征的贡献度, 使得到的三维模型特征更准确, 能更好地描述三维模型。试验表明, 本研究所提出的三维模型检索方法能有效地提高检索结果的准确率。

参考文献
[1] 张开兴, 张树生, 刘贤喜. 三维CAD模型检索技术研究现状与发展分析[J]. 农业机械学报, 2013, 44(7): 256-263
ZHANG Kaixing, ZHANG Shusheng, LIU Xianxi. Current research and feature development of 3-D CAD model retrieval[J]. Transactions of the Chinese Society for Agricultural Machinery, 2013, 44(7): 256-263 DOI:10.6041/j.issn.1000-1298.2013.07.044
[2] SHIH Jauling, LEE Changhsing, WANG Jiantang. A new 3D model retrieval approach based on the elevation descriptor[J]. Pattern Recognition, 2007, 40(1): 283-295 DOI:10.1016/j.patcog.2006.04.034
[3] CHEN Qiang, YU Yongmei. 3D CAD model retrieval based on feature fusion[J]. Advanced Materials Research, 2013, 765: 316-319
[4] OSADA Robert, FUNKHOUSER Thomas, CHAZELLE Bernard, et al. Shape distributions[J]. Acm Transactions on Graphics, 2002, 21(4): 807-832 DOI:10.1145/571647.571648
[5] MIRELA Benchen, CRAIG Gotsman. Characterizing shape using conformal factors[C]//Eurographics Workshop on 3D Object Retrieval. Crete, Greece: The Eurographics Association, 2008: 1-8.
[6] CHEN Dingyun, TIAN Xiaopei, SHEN Yute, et al. On visual similarity based 3D model retrieval[J]. Computer Graphics Forum, 2003, 22(3): 223-232 DOI:10.1111/cgf.2003.22.issue-3
[7] OHBUCHI Ryutarou, OSADA Kunio, FURUYA Takahiko, et al. Salient local visual features for shape-based 3D model retrieval[C]//Shape Modeling and Applications. New York, USA: IEEE, 2008: 93-102.
[8] 郑赢, 周明全, 耿国华, 等. 多特征动态融合的三维模型检索方法[J]. 计算机科学, 2013, 37(7): 260-263
ZHENG Ying, ZHOU Mingquan, GENG Guohua, et al. 3D model retrieval on multi-feature dynamic integration[J]. Computer Science, 2013, 37(7): 260-263
[9] LI Bo, JOHAN Henry. 3D model retrieval using hybrid features and class information[J]. Multimedia Tools and Applications, 2013, 62(3): 821-846 DOI:10.1007/s11042-011-0873-3
[10] 徐平安, 唐雁, 牟春倩, 等. 融合细节与整体特征的三维模型检索方法[J]. 西南大学学报(自然科学版), 2015(10): 131-137
XU Pingan, TANG Yan, MOU Chunqian, et al. A new 3D model retrieval method combining local and global features[J]. Journal of Southwest University (Natural Science), 2015(10): 131-137
[11] 李朋杰. 面向三维模型检索的特征提取算法研究[D]. 北京: 北京邮电大学计算机学院, 2013L.
LI Pengjie. Research on feature extraction algorithms for 3D model retrieval[D]. Beijing: School of Computer Science, Beijing University of Posts and Telecommunications, 2013. http://d.wanfangdata.com.cn/Thesis/Y2403843
[12] ZHOU Dengyong, WESTON Jason, GRETTON Arthur, et al. Ranking on data manifolds[C]//Annual Conference on Neural Information Processing Systems. Vancouver, Canada: MIT Press, 2003:169-176.
[13] LOWE David G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110 DOI:10.1023/B:VISI.0000029664.99615.94
[14] 杨川. 基于先验融合和流形排序的显著目标检测[D]. 大连: 大连理工大学信息与通信工程学院, 2013Y.
YANG Chuan. Salient object detection based on prior integration and manifold ranking[D]. Dalian: School of Information and Communication Engineering, Dalian University of Technology, 2013. http://d.wanfangdata.com.cn/Thesis/Y2418306
[15] 朱征宇, 汪梅. 基于Manifold Ranking和结合前景背景特征的显著性检测[J]. 计算机应用, 2016, 36(9): 2560-2565
ZHU Zhengyu, WANG Mei. Saliency detection combining foreground and background features based on manifold ranking[J]. Journal of Computer Applications, 2016, 36(9): 2560-2565 DOI:10.11772/j.issn.1001-9081.2016.09.2560
[16] FURUYA Takahiko, OHBUCHI Ryutarou. Diffusion-on-manifold aggregation of local features for shape-based 3D model retrieval[C]//Proceedings of the 5th ACM on International Conference on Multimedia Retrieval. Shanghai: ACM, 2015: 171-178.
[17] SHILANE Philip, MIN Patrick, KAZHDAN Michael, et al. The princeton shape benchmark(Figure 1 and 2)[J]. Proceedings of Shape Modeling International, 2004(6): 167-178
[18] LI Bo, GODIL Afzal, AONO Masaki, et al. SHREC′12 track: generic 3D shape retrieval[J]. Eurographics Conference on 3D Object Retrieval, 2012(5): 119-126
[19] SAUPE Dietmar, VRANIC Dejan V. 3D model retrieval with spherical harmonics and moments[J]. Lecture Notes in Computer Science, 2001(2191): 392-397
[20] DING Ke, WANG Wei, LIU Yunhui. 3D model retrieval using bag-of-view-words[J]. Multimedia Tools & Applications, 2014, 72(3): 2701-2722
[21] KAZHDAN Michael, FUNKHOUSER Thomas, RUSINKIEWICZ Szymon. Rotation invariant spherical harmonic representation of 3D shapedescriptors[C]//Proceedings of the 2003 Eurographics. Aachen, Germany: ACM, 2003:156-164.