随着计算机图形学和数字媒体的高速发展, 三维模型的应用越来越广泛。由于创建逼真度较高的三维模型需要耗费大量的时间和精力, 有时候只需要对已有的三维模型进行局部修改就能使用, 因此如何从已有的三维模型库中迅速地、准确地检索出与要求相同或相似的三维模型已成为目前研究热点。根据提取特征的不同, 可以将这些方法分为3类:基于几何的检索方法、基于视图的检索方法和基于多特征融合的检索方法。基于几何的检索方法通过提取三维模型的几何特征进行检索, 如OSADA Robert等人提出的Shape Distributions算法[1]。基于视图的检索方法则利用三维模型的视图特征进行检索, 如CHEN Dingyun等人提出的Light Field算法[2]。近年来广泛使用基于多特征融合的检索方法, 恰当多的特征融合能使得三维模型的描述更具体, 较传统的基于单一特征的方法有着更好的检索结果, 如LI Bo等人提出的ZFDR算法[3], 融合了4种不同的特征。
基于特征融合的三维模型检索方法应该同时关注三维模型整体信息与局部信息, 并且特征数量不宜超过4个[3]。本研究提出一种融合整体与局部信息的三维模型检索方法, 此方法属于基于特征融合的检索方法。通过旋转三维模型得到不同方向的二维投影视图, 分别利用Canny算子提取边缘特征和基于SIFT特征的词袋模型提取词频向量特征, 边缘特征用于描述三维模型的整体信息, 词频向量特征用于描述三维模型的局部信息, 将这两种特征通过权值进行有效地融合, 得到一个新的特征用于表示三维模型。试验表明, 提出方法能够有效地提高检索结果的准确率。
1 相关知识 1.1 Canny算子Canny算子是CANNY J于1986年提出的一个多级边缘检测算法[4]。该算子的目标是找到一个最优的边缘检测算法, 且图像边缘检测必须满足2个条件:一是能有效地抑制噪声, 二是必须尽量精确地确定边缘的位置。
Canny算子根据对信噪比与定位乘积进行测度, 得到最优化逼近算子, 主要包括4个步骤:(1) 用高斯滤波器平滑图像; (2) 用一阶偏导的有限差分来计算梯度的幅值和方向; (3) 对梯度幅值进行非极大值抑制; (4) 用双阈值算法检测和连接边缘。
1.2 词袋模型词袋模型(bag-of-feature, BoF)是当下一种十分流行的用于视觉分类的模型, 其思想源于文本词袋模型(bag-of-words, BoW)。该模型将图像看作为文档, 即若干个“视觉词汇”的组合, 并且这些视觉词汇之间也是没有顺序的。与文本文档不同的是, 图像中的词汇不是现成的, 需要运用相应的特征提取方法从图像中提取出来。通常, 需要3个步骤:(1) 特征检测; (2) 特征表示; (3) 生成词典。
所用到的特征可以是任意一种特征, 如SIFT特征等。词典生成后, 就可以利用词频向量来对图像进行描述。
1.3 尺度不变特征变换算法尺度不变特征变换(scale-invariant feature transform, SIFT)算法由LOWE D G于1999年提出[5], 它是一种提取局部特征的算法, 对旋转、尺度缩放、亮度变化具有不变性, 对视角变化、仿射变换、噪声也具有一定的鲁棒性, 信息量丰富, 适用于在数据量庞大的特征库中进行快速、准确的匹配。SIFT特征提取的过程有以下几个步骤:(1) 尺度空间的生成; (2) 检测尺度空间极值点; (3) 精确定位极值点; (4) 为每个关键点制定方向参数; (5) 生成特征点描述子。LOWE D G建议采用特征点所在尺度空间内4×4的窗口中计算的8个方向的梯度信息作为特征点描述子[5], 即一个128维的向量。
2 融合整体和局部信息的三维模型检索方法本研究通过旋转三维模型得到34张不同方向的二维投影视图, 分别利用Canny算子提取了边缘特征和基于SIFT特征的词袋模型提取词频向量特征。边缘特征能够较好反映三维模型的整体信息, 而词频向量特征能够较好反映三维模型的局部信息, 分别将这两种特征进行相似度计算, 再进行加权求和, 得到能更好描述三维模型的新特征。方法框架图见图 1。
|
图 1 方法框架图 Figure 1 The frame of the method |
对人类而言, 描述一个物体最有效的方法就是描述其不同方向的视图。在描述一个三维模型时, 从不同角度看过去的视图有可能完全不同。因此, 如果仅仅用一个方向的视图, 是不能够准确地描述出一个三维模型的。所用到的视图越多, 越能准确地描述出一个三维模型。获取一个三维模型的投影的方法有许多, 例如光场投影方法(light field)[2]和包围盒投影方法(cube-based)[3]。与其他方法不同的是, 本文方法让三维模型分别围绕x、y、z轴旋转, 每次旋转30°, 从而获得不同方向的视图。一个钢琴模型的投影示例见图 2。
|
图 2 钢琴模型的二维投影示例图 Figure 2 The projected images of a piano |
利用Canny算子提取二维投影的边缘特征, 边缘检测示例见图 3。其中的白色轮廓即为Canny算子所检测到的边缘。将Canny算子处理后的结果作为原图像的边缘特征。文中, 对于每个三维模型, 其34张二维投影经过Canny算子处理后获得34个边缘特征fc, 将这34个边缘特征用于表示三维模型, 得到三维模型的边缘特征FC, 所得的FC为一个34维的向量, 计算过程:
| $ {\boldsymbol{F}_C} = [{f_{{c_1}}},{\rm{ }}{f_{{c_2}}}, \ldots ,{\rm{ }}{f_{{c_{34}}}}]。 $ | (1) |
|
图 3 边缘检测示例图 Figure 3 Edge detection of a piano |
提取二维投影的SIFT特征用于构造视觉词典, 获取词频向量特征。
2.3.1 提取SIFT特征利用SIFT算法, 检测二维投影的关键点, 得到二维投影的SIFT特征。SIFT算法可以从每张二维投影中检测到多个特征点, 每个点的特征为一个128维的向量。特征点检测示例见图 4。
|
图 4 SIFT特征示例图 Figure 4 The SIFT of a piano |
针对相似的SIFT特征点, 应该将它们视为同一个视觉词汇。利用k-means聚类算法对SIFT特征进行聚类, 构建词典, 得到k个相似的簇, 每一个簇代表一个视觉词汇。
2.3.3 获取词频向量特征得到视觉词典后, 将二维视图的SIFT特征与词典进行比较, 通过统计词典中每个视觉词汇在二维投影中出现的次数, 即可得到二维视图的词频向量。词频统计示例见图 5, 文中, 对于每个三维模型, 分别将其34张投影的SIFT特征与构造好的词典进行匹配, 计算出对应的词频向量, 所得向量即为词频向量特征fb, 将这34个词频向量特征用于表示三维模型, 得到三维模型的词频向量特征
| $ {\boldsymbol{F}_B} = [{f_{{b_1}}},{\rm{ }}{f_{{b_2}}}, \ldots ,{\rm{ }}{f_{{b_{34}}}}]。 $ | (2) |
|
图 5 词频向量对应的直方图 Figure 5 The bar of a word frequency vector |
根据三维模型的特征值, 可以计算任意两个三维模型mi和mj的相似度。设mi和mj的特征分别为Fi和Fj, 且Fi=(a0, a1, …, an), Fj=(b0, b1, …, bn)。利用欧式距离计算三维模型mi和mj的相似度
| $ d({m_i},{m_j}) = \sqrt {\sum\limits_{r = 0}^n {{{({a_r} - {b_r})}^2}} }。 $ | (3) |
式中:ar和br分别为Fi和Fj中对应的项。
式(3)计算所得距离越大, 模型间的相似度越低, 反之, 相似度越高。
2.5 特征融合对于一个模型, 将两个不同的特征计算所的相似度进行加权相加, 得到新的相似度
| $ D({m_i},{m_j}) = \left\{ {\begin{array}{*{20}{c}} {{w_C}\cdot{d_C} + {w_B}\cdot{d_B},}&{i \ne j,}\\ {0,}&{i = j,} \end{array}} \right. $ | (4) |
式中: wC和wB分别为用于融合边缘特征下相似度的权值和词频向量特征下相似度的权值, 0 < wC, wB < 1且wC+wB=1; dC和dB则分别表示在边缘特征和词频向量特征下的相似度。同理, 式(4)计算所得值越大, 模型间的相似度越低, 反之, 相似度越高。同一个模型的相似度为0。
3 试验 3.1 试验环境和数据试验硬件环境为Acer Veriton D4300 Intel (R) Core (TM) i5-3470 CPU @ 3.20 GHz, 4 GB内存; 软件环境为32位的Windows7, MatlabR2010b, Visual Studio 2013。
数据采用PSB模型库[6]和SHREC2012GTB模型库[7]中的三维模型。PSB模型库包总共包含1 814个模型, 并且被分为两组, 第一组是包含131个类的测试数据集, 第二组为包含129个类的训练数据集, 且每组数据集都包含907个模型。本研究利用训练数据集来生成词典。SHREC2012GTB模型库中总共包含了1 200个模型, 其中有60个类, 每个类有20个模型。
3.2 评价标准试验中, 为了客观地比较不同算法间的差异, 本研究采用Nearest Neighbor (NN)、First Tire (FT)、Second Tire (ST)、E-Measure (E)和Precision-Recall (P-R)曲线图[6]对检索结果进行评价。其中, NN表示返回的第一个模型属于目标类的比例, FT表示返回的的前C-1(C为目标类模型的数量)个模型属于目标类的比例, ST表示返回的前2(C-1)个模型属于目标类的比例, E是综合查全率和查准率的指标, 且这4个指标的值越大, 代表结果越好。P-R曲线图则能体现总体检索效率。
3.3 试验结果(1) PSB模型库
在计算三维模型的词频向量特征时, 针对模型库中训练模型的所有二维投影, 随机抽取一半作为训练样本, 将它们的SIFT特征用于构建视觉词典。经过多次试验比较, 当词汇数目为1 000即执行k=1 000的k-means算法时, 试验能取得较好的结果。在进行特征融合时, 通过多次试验比较, 在wC和wB分别取0.25和0.75时能取得较好的结果。
选取算法Spherical Harmonic Descriptor (SHD)[8]、Gaussian Euclidean Distance Transform算法(GEDT)[8]、Spherical Extent Function算法(EXT)[8]、Shape Histogram算法(SECSHEL)[9]和Shape Distributions算法(SD)[1]进行对比试验。
对PSB模型库中模型进行检索的示例见表 1, 这里只取前6个返回结果作对比。各个检索方法对应的NN、FT、ST和E值见表 2, 这4项指标通过文献[6]所提供PSB_Util工具包中的psbTable.exe获得。各个检索方法的P-R曲线图见图 6, 横坐标R代表Recall, 纵坐标P代表Precision, 可以通过文献[6]提供的PSB_Util工具包中的psbPlot.exe计算并利用Matlab绘制曲线图得到。
|
表 1 PSB模型库检索结果示例图 Table 1 Retrieval results for PSB |
|
|
表 2 6种检索方法的定量比较 Table 2 Quantitative comparison of the six methods |
|
图 6 6种检索方法的整体P-R曲线 Figure 6 P-R curve of the six methods for PSB |
(2) SHREC2012GTB模型库
在计算三维模型的词频向量特征时, 针对模型库中模型的所有二维投影, 随机抽取一半作为训练样本, 将它们的SIFT特征用于构建视觉词典。经过多次试验比较, 当词汇数目为1 000即执行k=1 000的k-means算法时, 试验能取得较好的结果。在进行特征融合时, 通过多次试验比较, wC和wB分别为0.4和0.6时能取得较好的结果。
选取bag-of-features算法(BoF)[10-13]、3DSP-L2_1000_Chi2算法(3DSP)[7, 14]和LSD-sum算法(LSD)[7, 15]进行对比试验。
对SHRE2012GTB模型库中模型进行检索的示例见表 3, 同样地, 这里只取前6个返回结果作对比。各个检索方法对应的NN、FT、ST和E值见表 4, 整体P-R曲线图见图 7。
|
|
表 3 SHREC2012GTB模型库检索结果示例图 Table 3 Retrieval results for SHREC2012GTB |
|
|
表 4 4种检索方法的定量比较 Table 4 Quantitative comparison of the four methods |
|
图 7 4种检索方法的整体P-R曲线 Figure 7 P-R curve of the four methods for SHREC2012GTB |
从试验结果可以看出, 针对两个不同的三维模型库, 提出的三维模型检索方法的检索结果都具有较高的准确率, 并且在整体性能上也优于其他方法。
4 结论为了提高三维模型检索结果的准确率, 本研究分别通过Canny算子提取了能够较好反映三维模型整体信息的边缘特征和通过SIFT特征构造的词袋模型提取了能较好反映三维模型的局部信息的词频向量特征, 并分别利用这两种特征进行相似度计算, 再加权求和, 得到能更好描述三维模型的新特征。试验表明, 所提出的三维模型检索方法能有效地提高检索结果的准确率。
| [1] | 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 |
| [2] | 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 |
| [3] | 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 |
| [4] | CANNY John. A computational approach to edge detection[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 1986, 6 : 679-698 |
| [5] | LOWE D 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 |
| [6] | 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 |
| [7] | 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 |
| [8] | SAUPE Dietmar, VRANIC Dejan V. 3D model retrieval with spherical harmonics and moments[J]. Lecture Notes in Computer Science, 2001 : 392-397 |
| [9] | PAN Xiang, YOU Qian, LIU Zhi, et al. 3D shape retrieval by poisson histogram[J]. Pattern Recognition Letters, 2011, 32 (6) : 787-794 DOI:10.1016/j.patrec.2011.01.003 |
| [10] | DING Ke, WANG Wei, LIU Yunhui. 3D model retrieval using bag-of-view-words[J]. Multimedia Tools & Applications, 2014, 72 (3) : 2701-2722 |
| [11] | CHEN Qiang, YU Yongmei. 3D CAD model retrieval based on feature fusion[J]. Advanced Materials Research, 2013, 765 : 316-319 |
| [12] | 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 |
| [13] | GAO Yue, DAI Qionghai. View-based 3D object retrieval: challenges and approaches[J]. IEEE Multime-dia, 2014, 21 (3) : 52-57 DOI:10.1109/MMUL.2014.20 |
| [14] |
张开兴, 张树生, 刘贤喜. 三维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 |
| [15] |
郑赢, 周明全, 耿国华, 等. 多特征动态融合的三维模型检索方法[J].
计算机科学, 2010, 37 (7) : 260-263 ZHENG Ying, ZHOU Mingquan, GENG Guohua, et al. 3D model retrieval on multi-feature dynamic integration[J]. Computer Science, 2010, 37 (7) : 260-263 |