三维图形的表达和分析及其在三维仿真和模型检索中的应用

1、三维图形的表达和分析及其在三维仿真和模型检索中的应用BA 07011022 何其真 计算机学院概述随着计算机软硬件的成熟，三维模型逐渐在电脑游戏、工业辅助设计、医学仿真虚拟手术、模型的检索与识别以及虚拟的教学场景等方面得到了广泛的应用。三维模型在计算机中的存储是点和面的集合，如何从这些信息中提取有效的特征，表达出模型的性质，是当前急需解决的问题。总体来说，三维模型的表达可以分成两个方向：物理性质的表达和几何形状的表达。问题的难点在于物理性质和几何形状的独立性，模型顶点序列的无序性，采样点数量的不统一，没有统一的世界坐标系，模型受旋转、缩放、平移的影响等。模型物理性质的研究，是在给定的外力作用下

2、研究模型的形变情况。目前国内外学者已经提出了一些解决方案，使用不同的模型来解决这个问题。典型的有弹簧模型1，有限元方法2和张量模型3。弹簧模型是基于线性弹性的假设，用虚拟的弹簧来链接各个结点。它的优势在于结构简单易于计算，但是弹簧的弹性系数靠经验指定，缺乏物理力学的基础。有限元方法是分析不规则物体受力形变的有效方法，它把物体划分成许多个有限元，通过分析每个有限元的受力性质来得到整个物体的刚度矩阵。它具有物理性质的支持，在应变小于20%的时候计算是准确的。但是它的缺点在于消耗大量的时间和空间，不能实时计算。张量模型是前两者折衷的一个产物，把物体的刚度矩阵分散到每个节点上，使得结构简单，加快了计算

3、速度，但是需要很长时间的预处理，而且也很难达到实时的要求4。有学者使用统计模型5的方法对仿真整容手术术前和术后的面部形状进行建模，通过术前的形状预测术后的形状6。该方法的计算非常快，但是它没有考虑到颌骨的形变过程，只是假定所有患者所经历的手术是一个完全一致的“标准手术”，而且该方法需要大量的实际样本训练统计模型。可以看出，目前的解决方案不能同时满足准确和高效的要求，而在一些特殊的应用中同时满足这样两个需求是很需要的，比如虚拟整容手术计划，医生需要实时地操作虚拟手术刀，立即得到准确的形变模型，就可以更好地和患者进行沟通和交流，选择最合适的手术方案。所以我们的研究从这个实际的应用入手，试图寻找既高

4、效又准确的形变计算方法。几何形状的表达是为模型检索、识别和语义标定提供依据。提取的特征要有效地表达三维模型的空间整体形状，与采样点的多少、位置、坐标系的选择以及旋转缩放平移无关，且具有鲁棒性，对噪声不敏感。模型的匹配现阶段主要采用传统的文本检索中的匹配方法（余弦模型，语言模型等）。目前国内外的学者采用的特征主要有：1. 全局信息的柱状图7,8, 表达顶点、矩、距离等的统计信息，与旋转缩放平移无关，但是它不能表达局部的几何形状。2. 特征地图9,10 ，把每一个顶点特征（局部信息：曲率，直径等）映射到物体的外接球上，和旋转有关，需要额外的傅立叶变换处理。3. 形状上下文11，一个选定点和 其四周

5、顶点的关系，表达了局部形状特征。旋转图是一种二维的柱状图来表达形状上下文，每个顶点对应一个二维柱状图，表达了这个顶点四周的上下文关系。这是一种非常有效的表达方式，被广泛应用于三维模型检索和识别13,14,15。但是每个顶点对应一幅图像，存储量和计算量都是巨大的。4. 可视化关键字16,为了解决上面的问题，把每个顶点的柱状图聚类，每一个类是一个关键字，几个关键字的组合表达了三维物体。这是一种有效的降维方法，但是聚类之前的预处理也是需要大量的存储和计算。5. 基于投影的表达12。把三维物体投影到若干平面（通常由PCA主轴决定），用几个特征投影来表达三维物体, 受噪声影响较大，不同的投影平面，会得到

6、完全不同的投影。可以看出目前三维图形的特征提取主要还是局限在Topic（主题）级别，即如果两个模型含有相同的Topic，则认为两个模型是相同的，但没有在Context (上下文)的层次上考虑，即没有考虑Topic之间的位置关系。其中的难点在于三维模型缺乏统一的世界坐标系，因此位置关系缺乏一个统一的描述。所以我们的研究尝试找出相应的解决方案。参考文献：1 Gelder, A.V. Approximate simulation of elastic membranes by triangulated spring meshes. J. Graph. Tools, vol.3(2),pp:21-42

7、(1998)2 M Bro-Nielsen, Cotin S. Real-time volumetric deformable models for surgery simulation using finite elements and condensation. Computer Graphics Forum, vol.15(3), pp:57-66 (1996)3 S Cotin, et.al .A hybrid elastic model allowing real-time cutting, deformations and force-feedback for surgery tr

8、aining and simulation. The Visual Computer, 16(88):437-452 (2000)4 W.Mollemans,et. al. Predicting soft-tissue deformations for a maxillofacial surgery planning system: From computational strategies to a complete clinical validation.Medical Image Analysis,vol.11(3)pp:282-301(2007)5 6 S Meller, E Nken

9、ke, W Kalender. Statistical Face Models for the Prediction of Soft-tissue Deformations after Orthognathic Osteotomies. MICCAI, vol. 3750, pp:443-450 (2005)7 Eric Paquet, et al. “Description of shape information for 2-D and 3-D objects,” Signal Processing: Image Communication, vol.16, pp:103-122, 200

10、08 R.Osada, et al., “Matching 3D Models with Shape Distributions,” In Shape Modeling International, May 20019 Meng Yu, et al, “3D Model Retrieval with Morphing-based Geometric and Topological Feature Maps,” Proc. IEEE conf. on Computer Vision and Pattern Recognition(CVPR03), vol.2, pp: 656661,200310

11、 Assfalg, J., Del Bimbo, A., and Pala, P, “Curvature maps for 3D CBR,” Proc. the International Conference on Multimedia and Expo (ICME03), vol.1, pp:301-304, 2003.11 Greg Mori, Serge Belongie, Jitendra Malik, “Shape contexts enable efficient retrieval of similar shapes,” Proc. IEEE Conf. on Computer

12、 Vision and Pattern Recognition (CVPR01), vol.1, pp:723-730, 200112 S Ruiz-Correa, et al. “A New Signature-Based Method for Efficient 3-D Object Recognition,” Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR01), vol.1, pp:769-776, 200113 Jurgen Assfalg, Alberto Del Bimbo, Pietro Pal

13、a, "Content-based Retrieval of 3D Objects using Spin Images", IEEE Transaction on Multimedia, vol. 9(3), pp: 589-599, 200714 Pedro A. de Alarcón, et al. “Spin Images and Neural Networks for Efficient Content-Based Retrieval in 3D Object Databases”, (CIVR02), pp:225-234, 200215 Assfalg

14、, et al. “3D content-based retrieval with spin images”, Proc. of IEEE International Conference on Multimedia and Expo (ICME04), pp: 771-774, 200416 Y. Liu, H. Zha, and H. Qin, “Shape Topics: A Compact Representation and New Algorithms for 3D Partial Shape Retrieval,” (CVPR06), pp.2025-2032, 2006.创新点

15、和可行性分析在本课题的研究中，主要研究以下2个问题。1. 寻找一种高效又准确的三维物体的形变算法。技术路线：1) 使用有限元分析产生大量虚拟样本定义新的统计样本，把加在物体上的外力引进统计样本中2) 从虚拟样本中训练，通过PCA分析得到样本均值和样本变化参数，从而得到统计模型 (Mr-SDM)3) 根据得到的统计模型，从给定的外力，就可以计算出物体的形变。这是已知一个样本中的部分信息，补全剩余信息的问题。通过配准已知的部分信息（外力），即可推算出未知的信息（结点位移，即形变）可行性分析：1) 快速 使用统计模型实时计算，大量的有限元分析时间被转移到离线的训练阶段2) 准确 有限元分析方法保证了物体的材料性质3) 相比其它统计模型, 解决了样本缺乏的问题, 并在统计模型中引入了外力作用, 使模型更加完备创新点：1) 使用有限元的方法为统计模型虚拟出一些样本，解决其小样本的问题2) 在统计模型里 样本的定义中引入外力的信息，以此来刻画模型的物理性质（外力和形变的关系）2. 寻找更好地表达三维模型空间几何形状的特征。技术路线：1) 用对相对角度分布(Relative Angl