三维模型检索中的特征提取技术研究进展.doc

三维模型检索中的特征提取技术研究进展
摘要：随着激光扫描技术的发展以及计算机性能的提高，三维模型不仅在数目方面快速增长，而且其应用领域也越来越广泛，如工业产品的模型设计、虚拟现实、3D游戏和模拟仿真等。本文针对三维模型检索中的形状特征提取问题进行分析和总结，并提出了形状特征提取后续需要展开的研究方向。
1 引言
作为继声音、图像和视频之后的第四代多媒体数据类型，三维模型是最直观、最具表现力的多媒体信息。随着激光扫描技术的发展以及计算机性能的提高，把现实生活中的几何模型进行数字化变得越来越容易。如斯坦福大学的数字米开朗基罗项目（Digital Michelangelo Project），该项目通过三维扫描硬件和三维重建软件系统能够完成大型雕塑的数字化过程，其最复杂的数字化三维模型包括20 亿个多边形和7000 幅彩色图像。三维模型不仅在数量方面快速增长，而且应用领域也越来越广泛。在工业产品的模型设计、虚拟现实、3D游戏、多媒体教学、影视动画、模拟仿真、分子生物学和三维地理信息系统等各个领域被广泛使用。而且统计发现，用户所需要的往往是一些已经存在或者是类似的三维模型。例如在CAD领域，66%的三维模型都已经在2001年造型存在。据估计，这种重复模型到2005年将会增加到80%。互联网也为三维模型共享提供了更加方便的条件。毫无疑问，今后可重用的三维模型会越来越多。而且随着网络技术的发展，互联网会使用更多的三维模型数据来充实网络内容，正如目前网络上存在大量图片、声音和视频等传统多媒体数据一样。
2 形状特征提取
对于三维模型检索，一个核心问题是形状特征提取。如何提取稳定有效的三维几何特征是开发高性能检索系统的关键。对于特征，我们从直方图(Histogram)， 视图(View)，变换(Transform)，拓扑(Topology)四方面对特征提取进行综述。
2.1 直方图
直方图描述是构造形状特征非常普遍的方法。直方图描述的共同特点是首先计算模型表面的几何信号值，然后定义量化区间数目(bins)，统计落入每个区间的点数目。作为一种全局特征，直方图描述对于局部噪声有比较好的稳定性。图给出了典型的直方图描述。

图1 直方图描述（bins=10）
典型的直方图特征包括扩展高斯图像(Extend Gaussian Image)，形状直方图(Shape Histogram) 等价类(Equivalence Classes), 形状分布(Shape Distribution)， 形状谱(Shape Spectrum)，变形特征(Morphing-based Feature)，反射对称性(Reflective Symmetry Descriptor)等。直方图描述的检索性能在很大程度上取决于所采用的信号能否反映出曲面的几何属性。而所构造的直方图形状特征在旋转，平移以及拉伸下所具有的稳定性也和提取的几何信号有关。在这里，我们把构造的直方图描述是否满足旋转不变性可以分为两类。
2.2 二维视图
二维视图（或侧影轮廓）包含了丰富的信息可以用于三维模型形状描述。这种分析方法，可以把很多二维形状描述符直接应用于三维形状内容的理解。并且，这种方法可以创建二维草图用于三维模型查询。为了尽可能避免三维空间信息的丢失，通常对一个三维模型从多视点进行投影，得到多个二维视图来描述三维形状信息。MPEG-7中的视图描述就从三个主方向提取视图特征，如图所示。

图2 模型三个主方向的投影视图
Cyr等人首先对一个三维模型从不同视点得到大量的视图，采用Shock图定义每个视图的二维形状特征。然后对视图进行聚类分析，选择一些彼此之间存在明显差异的视图作为代表性视图，如图所示。提出如何选择最优视图集合用于三维模型识别。通过分析，每个模型需要5到25幅视图来描述三维形状信息。他们采用的二维形状特征是曲率尺度空间。把该工作应用于三维模型检索，为了加快检索速度，算法采用M-Tree构造索引结构。采用索引结构后，检索效率有很大的提高。

图3 典型视图选择（圆圈内的是代表性视图）
Chen等人考虑两个三维模型如果相似，则从不同视点得到的视图也会相似。因此，对每个三维模型从固定的十个光场进行正交投影，得到大量的二维视图用于三维形状描述。为了能够得到更好的检索性能，对每幅视图，他们集成Zernike矩和傅立叶变换来描述二维形状特征。为了能够加速匹配过程，算法采用一种从粗到精的匹配方法。首先采用少量的特征系数对数据库进行搜索，过滤部分和查询示例很不相似的模型。下一次匹配只需对数据库中的子集合进行搜索，最终得到查询结果。
2.3 变换特征
变换特征是指对模型进行数学变换，把变换系数应用于形状描述。对三维空间上的几何信号分析，球面调和 (Spherical Harmonic)，又称球面傅立叶变换，是一种非常有效的数学工具。和二维空间上的傅立叶变换比较，球面傅立叶变换还可以对三维形状进行多分辨率描述。球面傅立叶变换被广泛用于三维形状特征提取和三维检索。采用球面调和变换系数作为形状特征。典型做法是采用一系列同心球对模型进行分解，然后对落入每个球壳的点进行球面傅立叶变换，根据变换系数在每个频带下的旋转不变性提取旋转不变形状特征。为了能够提高同心球分解的鲁棒性，采用Delta函数对模型在频域空间进行采样。对一些模型的检索实验表明，该采样算法可以有效地提高检索准确率。类似的方法是计算模型视点相关的深度加权表面法向统计分布，对该分布实行球面调和分析，提取模型的深度加权法向映射特征。或是定义三维Zernike矩。
2.4 拓扑结构
拓扑特征给出了三维模型的结构描述，而且结构特征在旋转，细分和变形下都有很好的稳定性。并且其包含了三维模型内在结构的语义特征，是建立三维模型几何特征和高级语义之间映射关系的前提和基础。用于表示CAD模型的CSG结构，就采用一种拓扑结构描述。Reeb图是应用最为广泛的拓扑结构描述。多分辨率Reeb图采用测地距离定义。该方法首先定义一个测地半径，把曲面分割成不同的子曲面，然后根据子曲面的连通性定义模型的多分辨率Reeb图。则采用多分辨率Reeb 图构造了一个三维模型检索系统。Augmented Reeb Graphs是多分辨率Reeb图的一种改进，主要是提取更多的几何特征用于局部属性描述。
拓扑结构也可以采用分支点骨架(Shock Scaffold)或是三维骨架(3D Sketch)来描述。把三维模型骨架应用于模型检索。对经过体素化的模型细化提取模型骨架。定义骨架的Shock图用于相似度计算。图4是三维模型和相应的骨架图。

图4 三维模型和骨架图
3 展望
可以发现，和其他特征相比较，结构特征其包含的信息最具有代表性。因为三维模型的一个显著特点是由一系列“有意义”的子部分(Meaningful part)组成的。但是，已有结构特征的提取只是通过形状稳定性来控制最终得到的分解结果。这种控制策略使得同一模型因为变形，姿态，子部分比例等的变化形成不一致的分解结果，导致同一类模型提取的结构特征具有多态性。因此，如何在结构特征提取过程中集成语义信息，实现结构特征提取的一致性，是后续研究要迫切解决的问题。

参考文献：
[崔晨旸 2004] 崔晨旸, 石教英，3D模型检索中的特征提取技术综述, 计算机辅助设计与图形学学报, 2004, 16(7): 882-889
[孙晓鹏2005] 孙晓鹏，李华，三维网格模型的分割及应用技术综述，计算机辅助设计与图形学学报，2005
[毛祎 2004] 毛祎， 三维模型检索及其应用, 硕士论文, 杭州：浙江大学，2004
[杨育彬 2004] 杨育彬, 林珲, 朱庆, "基于内容的三维模型检索综述," 计算机学报, vol. 27, no. 10, pp. 1297-1310, 2004.
[Bustos 2006] "Content-Based 3D Object Retrieval," IEEE Computer Graphics and Applications, vol. 27, no. 4, pp. 22-27, 2007
[Havemann 2007] S. Havemann and D. W. Fellner, Seven Research Challenges of Generalized 3D Documents, IEEE Computer Graphics and Applications, vol. 27, no. 3, pp. 70-76, 2007
[Iyer 2003] N. Iyer, Y. Kalyanaraman, K. Lou et al, A Reconfigurable, Intelligent 3D Engineering Shape Search System Part I: Shape Representation, ASME DETC Computers and Information in Engineering (CIE) Conference, 2003
[Jain 2007] V Jain, H Zhang, A spectral approach to shape-based retrieval of articulated 3D models , Computer-Aided Design, 2007
[Ohbuchi 2008] R. Ohbuchi, K. Osada, and T. Furuya, Salient local visual featuers for shape-based 3D model retrieval. Internation Conference on Shape Modeling, 2008: p. 93-102
[Veltkamp 2008]Veltkamp, R.C., T. Haar, and B. Frank, SHape REtrieval Contest (SHREC) 2008 IEEE International Conference on Shape Modeling and Applications, 2008: p. 215-216.