基于几何内容的三维模型比较与检索算法研究

基于几何内容的三维模型比较与检索算法研究Researchon3DModelSimilarityMeasureandRetrieval姓名：刘一指导教师：查红彬教授北京大学学士学位论文1基于几何内容的三维模型比较与检索算法研究Researchon3DModelSimilarityMeasureandRetrieval摘要随着三维建模技术的日益成熟和计算机软硬件技术的飞速发展，三维模型的数量在最近的十年中有了飞跃性的增长。充分利用已有的三维模型数据资源，可以大大减轻设计新模型的工作量，同时也可以促进三维数据的流通和在各领域的应用。这就需要提出有效的方法，根据几何内容对三维模型进行分类和检索。基于内容检索的关键问题是如何将三维模型的特征进行量化，并在此基础上进行相似度的定义。由于三维模型作相似变换后，仍被视为是同一个模型，因此抽取具有相似变换不变性的几何特征是十分必要的。相似变换可以分解成三种基本的变换－平移变换，尺度变换和旋转变换。对模型的位置和尺寸进行归一的方法相对简单，相对来讲旋转自由度的归一则具有较差的稳定性。因此，人们期望定义的物体形状描述算子具有自身的旋转不变性。为了不依赖坐标系的选择，我们利用快速球面调和变换，将三维几何信息分解到SO(3)变换下的一系列不变子空间中，从而获得所提取特征的旋转不变性。作为和Fujitsu公司的横向合作项目，论文作者和普建涛博士后共同开发了基于几何内容进行三维模型检索的原型系统，在深入研究已有算法的基础上，提出了几个新算法，并验证了有效性。本文共分五个章节。第一章介绍三维网格模型的概念和基本应用。第二章介绍三维模型检索系统的流程与用户界面设计框架。第三章介绍基于随机过程的三维几何特征提取方法。第四章介绍球面调和变换的概念和若干以检索为目的的快速球参数化方法，并对作者提出的新算法进行详细讨论。第五章对实验结果进行总结并展望今后工作。关键词：数字几何处理、三维模型检索、球面调和变换KeyWords:DigitalGeometryProcessing,3DModelRetrieval,SphericalHarmonicTransform北京大学学士学位论文2第一章三维模型和数字几何处理的概念与应用1.1三维网格模型的概念和应用我们生活在一个三维的世界中，传统的照相技术只能获得三维物体的二维影像，而无法精确的记录物体的三维几何特征。类似于二维数码图像可以看作利用离散像素来逼近物体在照相机胶片上的投影，三维模型的一种最基本的表示形式是利用大量多边形来逼近真实三维物体的几何。除此之外，三维模型还有其他多种表示形式，如利用诸如长方体等基本体素进行布尔运算来构造复杂三维几何体的CSG表示形式；用非均匀有理B样条（NURBS）等基于Bernstein基函数的样条曲面表示形式；利用二值化的三维数组对模型几何特征进行描述的体素化表示形式等等。在各种三维模型的表示形式中，多边形表示形式无疑是最直观，最简单的一种，因此其他三维几何表示形式往往需要预先转换到这种最基本的表示形式，以获得统一的处理。本文的各种算法也均建立在三维模型的多边形表示形式基础之上。值得指出的一点是，最常见的三维模型数据格式VRML等，并没有给出模型表面流形的定义。构成三维模型的大量多边形并没有紧密拼接，而是形成多边形汤（polygon-soup）的无组织散乱分布，在很大程度上不方便利用已有的信号处理方法对这种表示形式的三维模型进行处理。由于填充三维模型表面的大量“漏洞”是一个开放性难题，因此，人们希望在建模过程中尽可能保证组成三维模型表面的多边形紧致（water-tight）拼接，从而形成可定义流形的多边形网格结构，这就是三维网格模型的基本概念。除几何要素之外，真实物体的表面还有色彩，纹理，反射性质BRDF等多种光学属性。对于一般的三维网格模型，每个顶点一般不仅仅记录它的三维几何坐标，还包括上述各种其他属性。这种对应关系一般由从二维平面区域到三维模型表面的纹理映射来定义。三维模型的人机交互通常离不开计算机真实感绘制，以获得三维模型的逼真形象。绘制过程的基本步骤是，根据Cook-Torrance或北京大学学士学位论文3Blinn-Phong等光照模型对真实光学物理过程进行近似，设置虚拟照相机的参数，经过取景变换，视域四棱锥裁减，可视面消隐和光栅化四个步骤，利用光线跟踪算法计算屏幕绘制区域每一象素的颜色和亮度。由于绘制的实时性要求很高，因此目前主流显卡均支持这一过程的硬件加速。这主要表现在计算被跟踪光线与模型表面的求交过程，通常采用的策略是层次包围盒算法和基于八叉树的空间剖分算法。由于几何光学只是真实物理过程的近似，因此采用传统光照明模型进行绘制常常会产生超真实感的绘制效果。考虑到光线本质上是一定频域范围内的电磁波，光学过程和热辐射过程实质上是完全一致的，利用热工学中的辐射度求解算法可以进一步提高绘制的质量，获得更接近真实世界的绘制效果，并可生成干涉，衍射等反映波动性的光学效果。本文只涉及三维几何信息处理的讨论，并不涉及模型的光照明属性和绘制研究，因此具体细节不加详述。在计算机辅助设计（CAD）和计算机辅助制造（CAM）领域，利用数字图像来表示待加工的机械零件，只能给人们提供一个外观结构的显示，但并不包含足够的可供加工的几何信息。而用三维模型来表示机械零件的几何结构，就可以完全记录零件的几何信息，使得自动来料加工成为可能。类似地，三维模型在建筑设计，艺术设计，工业工程，家居装修等需要大量处理三维几何信息的领域，都有着广泛的应用前景。在科学技术领域，以分子生物学为代表的基因技术将成为21世纪的领头羊，基础研究的热点从基于PCR技术的基因测序，利用限制性内切酶进行基因重组等传统基因技术，逐渐转向了以结构基因组学为代表的后分子生物学时代。结构基因组学关注的问题是，从基因序列到具有活性的蛋白质产生，往往肽链要经过多次切割，重组，才能最终形成具有特定空间形态的蛋白质三维结构，从而具有生物活性。一般来说，酶在同靶分子作用时的动态三维结构最终决定了它在催化反应中的功能，一旦蛋白质由于受热或受到重金属离子影响而破坏了特定的三维空间结构，其特定的功能也就丧失，尽管氨基酸序列并没有发生变化。因此，测定蛋白质的三维结构，对探索生命过程最根本问题是十分有意义的。目前常用的测定蛋白质三维结构的技术手段包括对蛋白质进行纯化、结晶基础上利用X射线衍射学对晶体空间结构进行测定，还包括在液相中测定空间结北京大学学士学位论文4构的核磁共振等方法。利用这些方法测定的数据形成了蛋白质结构数据库，如何在数据库中进行检索，如何根据已有的知识，根据结构预测蛋白质的功能，如何根据结构功能的关系设计新药就成了生物信息学研究的内容。从上面我们可以看到，三维几何建模技术，特别是对大分子空间结构的描述，在生命科学基础研究领域，同样具有良好的应用前景。在医学方面，CT和核磁共振是常用的人体疾病探测手段，并在此基础上发展了交互式外科技术。外科医生可以在三维显示系统的引导下，进行胸内，颅内各种复杂条件下的手术。颅内手术包括利用γ刀对脑体内部肿瘤进行切除，胸内常见的包括冠状动脉搭桥术等高难度手术。目前特别受到关注的研究热点是利用三维交互式技术来进行药品成瘾戒断术，即通过交互式手段，精确定位兴奋灶并利用高频电磁场破坏患者的成瘾性神经反馈回路。这些应用均促进了三维几何结构的描述，可视化技术和人机交互等三维视觉计算领域的研究。三维建模在文物保护中也发挥着重要的作用。前面已经提到，三维模型的特点是可完整反映真实物体的三维几何。因此，对于一些珍贵的三维模型，由于年代久远面临着风化，碎裂，受潮变形等危险。建立它们精确的三维模型有备无患是十分必要的。北京大学视觉听觉国家重点实验室利用激光扫描技术，重建了北京人头盖骨的三维模型，在文物保护领域做出了良好的示范性作用。1.2基于三维网格模型的数字几何处理前面提到，三维网格模型表示形式存在流形的定义，因此它与数字几何处理紧密相连。信号处理的前提是要定义具有一致性的参数化空间。二维数字图像的数据结构从本质上来看是二维数组，因此其自身即对应着明显的参数化空间，可直接进行信号处理。而三维网格模型并没有一个明显的参数空间与之对应，因此参数化问题就成为三维数字几何处理中的一个最基本的问题。将三维网格模型映射到二维参数空间，从而可轻松利用JPEG等标准的二维图像压缩方法对三维模型进行压缩存储，称为几何图像方法。特别地，对于三维模型逐渐变形的三维动画序列，利用参数化的方法就可以将其对应成一段视频序北京大学学士学位论文5列，称为几何视频。这样，定义在二维空间的诸多信号处理方法都可以用来处理三维几何，极大了丰富了人们对三维模型的操作。利用渐进式网格简化的方法，按照某种最优化策略，例如二次误差度规，对初始三维网格模型的边进行逐次收缩，可以将复杂的三维模型简化到较低的分辨率层次上。这一过程是可逆的，通过相反的点分裂过程，又可以逐步增加较低分辨率模型的细节层次，使其复原。这种多分辨率尺度控制是对三维网格模型进行数字几何处理的一个关键操作，作为基础，有着广泛的应用。例如，根据视点移动，始终保持视点周围具有最高的分辨率细节，延远离视点方向，网格的分辨率连续地下降，从而形成一种动态的连续多分辨率表示形式。这种形式方便了对大数据量三维网格根据使用者的兴趣进行渐进传输，此外，这种动态的多分辨率表示形式也有利于开展与人的认知相关的生理心理学实验。利用上面的网格可逆的渐进方法，可以将任一亏格为零的三维网格模型简化为最低的分辨率，即一个四面体。由于任何四面体的凸包都是自身，因此从该四面体的重心向它的四个顶点发出射线，就可以唯一地将这个四面体映到以其重心为球心的单位球上。此时逐步进行点分裂操作，按照调和映射或保角映射关系将新增将的顶点放置在球面上，直至完全恢复原物体的拓扑结构为止，这样就完成了对亏格为零的网格模型进行球参数化[1]。这样，利用球面上已有的信号处理方法，例如球面调和函数分解，球面小波变换等可将原三维模型转化到频域，在频域可进行我们熟知的卷积，滤波等操作，经过相反的过程，这些操作的结果最终体现在原三维网格模型上，这就构成了对三维网格模型进行信号处理的一般理论框架，当然这个过程也同时量化了三维网格模型的几何特征。上述过程是具有一般性的理论框架，在实际处理过程中，三位网格的拓扑关系常常会出现错误，并且，亏格非零的三维模型并不少见，因此，在很大程度上还需要针对具体问题设计具体的算法。另一个基本的问题是，如何除去三维模型表面的噪声，是模型的表面更为光顺，同时尽可能的保持其主要几何特征。一般地，对局部网格进行具有平滑意义的拉普拉斯变换是网格光顺化的一个很好的选择。问题在于，这种变换常常会导致三维模型表面的收缩。为此，人们提出了保体积的拉普拉斯变换等方法，对三维网格的光顺化有着更好的视觉效果。北京大学学士学位论文6此外，作为三维数字几何处理的前期工作－三维建模也在研究中处于一个十分重要的地位。典型的方法包括，基于NURBS曲面的CAD软件建模方法，基于激光点阵测距技术的建模方法和基于图像的建模方法。对于真实世界的三维物体建模，一般采用后两种方法，由于基于图像的建模方法精度较低，对光照等条件要求较高，我组目前一般不采用。目前常用的方法是利用激光扫描仪进行建模。激光扫描仪的原理十分简单：记录发出和收回激光束的时间差，根据光速测量仪器和物体表面的距离。类似于电视的电子束扫描原理，从扫描仪发出的激光向物体的表面逐行扫描，进而生成一系列深度距离数值。由于遮挡关系，从单一视点发出的扫描线一般不能覆盖整个模型表面，因此，需要将几个不同视点的深度数据整合，去除重叠区域，从而形成包含整个物体表面的三维点阵数据。最后利用ICP算法构造点与点之间的连接关系，生成三维网格模型。由于建网的复杂性，在很多情况下，直接用点云数据来表示真实物体的三维几何，并采取各种有效的点绘制算法，但目前研究的主流还是集中在三维网格模型的表示上，本文不涉及点云几何数据处理的讨论。1.3三维模型检索的概念与特点随着三维网格模型在各行各业的大量应用，如何根