﻿ 基于流形排序的三维模型检索方法
 文章快速检索 高级检索
 山东大学学报(工学版)  2017, Vol. 47 Issue (4): 19-24  DOI: 10.6040/j.issn.1672-3961.0.2016.382 0

### 引用本文

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.

### 文章历史

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 相关知识 1.1 词袋模型

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)

(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)

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

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

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

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

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

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

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

2.2.1 提取SIFT特征

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

2.2.3 获取词频向量特征

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

 $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)

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

 $\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中的节点权重

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

2.3.3 聚合特征

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

 $\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)

2.4 相似度计算

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

3 试验 3.1 试验环境和数据

3.2 评价标准

3.3 试验参数

3.4 试验结果

(1) PSB模型库

 图 5 6种检索方法的整体P-R曲线 Figure 5 P-R curve of the six methods for PSB

(2) SHREC2012GTB模型库

 图 6 6种检索方法的整体P-R曲线 Figure 6 P-R curve of the six methods for SHREC2012GTB

4 结论

 [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.