2011江苏高考数学试卷
三维检索中的网格模型分割算法
随着万维网的发展，在三维VRML1数据库中寻一个与给定物体形状相似的模型的应用需求正变得越来越广泛，比如：计算生物学、CAD、电子商务等等。形状描述子和基于特征的表示是实体造型领域中基本的研究问题，它们使对物体的识别和处理变得容易。因为形状相似的模型有着相似的分割，所以基于分割的形状描述子可以用于形状匹配。 2002年毕斯乔夫[37]提出从三维模型分割得到的椭球集合中得到的某种统计信息（比如椭球半径的平均方差或者标准方差，以及它们的比率）。由于这些信息在不同的形状修改中都保持不变，因此可以作为一种检索特征。但是这个想法没有得到严格的理论或者实验证明。 2002年，扎克伯吉[65]在一个拥有388个VRML三维网格模型的数据库上进行检索。首先他们将三维网格模型分割为数目不多的有意义的分割片。然后评价每一个分割片形状，确定它们之间的关系。为每个分割片建立属性图，看作是与原模型关联的索引。当在数据库中检索与给定网格模型相似的物体时，只是
去比较属性图相似的程度。
该方法检索结果的精确性较差；分割片属性图比较采用图同构的匹配，计算量较大，且是一个很困难的问题；从实验结果看，分割效果显然还不够有意义，出现飞机、灯座等模型被检索为与猫相似的结果；区分坐、立等姿态不同的人体模型效果显然也很差（如图19）。
2003年戴伊[9]基于网格模型的拓扑信息，给出名为“动力学系统”的形状特征描述方法，并模拟连续形状给出了离散网格模型形状特征的定义。实验表明，该算法十分有效地分割二维及三维形状特征。
目前，基于几何以及拓扑信息的中轴线或骨架等形状描述子也得到了广泛的研究，如基于水平集[55]、拓扑持续性[69]、Shock图[15]、Reeb 图[54]和中轴线[56]等方法。这些形状描述可以从
孙晓鹏
中国科学院计算技术研究所
认知心理学、心理物理学认为：人类对形状的识别过程部分地基于分割，复杂形状往往被看作是若干简单元素的组合。同时，在视觉识别过程中，显著形状特征以很高的
优势屏蔽了其它不显著特征。为了获取形状的显著特征，首先必须进行分割。
1 Virtual Reality Modeling Language，虚拟现实建模语言，一种在WWW中描述虚拟现实（VR）的工
具，用来描述三维物体及其行为。其基本目标是建立互联网上的交互式三维多媒体，具有三维性、交互性、动态性、实时性等特征，能够在互联网或局域网上快速传递。该语言于1998年1月被正式批准为国际标准（ISO/IEC14772-1:1997），是第一个用HTML发布的国际标准。
（接上期）
离散的体数据、以及边界表示数据（网格模型）中抽取出来。对于后者，目前还没有什么算法能得到精确、有效的结果[39]。但相信依据拓扑信息进行分割得到的分布式形状描述子也是一种值得尝试的三维模型检索思路。
几何压缩传输中的网格模型分割
健壮的网格模型压缩传输方法，必须保证即使部分形状信息丢失，剩下的部分至少能够得到一个逼近原始物体的重构，即，逼近的质量下降梯度，要大大滞后于信息丢失梯度。
无论是层次结构的、或者是过程表示的多边形网格模型，它们的缺陷是：必须保证严格的拓扑信息一
致性。顶点和面片之间的交叉引用导致即使在传输中丢失了1%的网格数据，也将无法从99%的剩余信息里重建网格模型的任何一部分。对此可以考虑引入高度的冗余信息，即使传输中丢失一定额度的数据，接收方依然可以重构模型大部分。
问题的关键是将几何体分割为相互独立的大块信息，这样接收方可以在不依赖相关索引信息的情况下，重构流形的邻域关系。
为了避免接收方从点云重构模型的算法变得复杂，早期的健壮传输方法总假设至少整体拓扑信息可以无损地传送。一旦知道了粗糙的
形状信息，接收方可以插入一些附加点生成逼近网格模型。
2002年，毕斯乔夫[37,72]的工作把网格模型分割为若干个椭球，每个椭球独立地、定义自己的几何信息。由于椭球的互相重叠，冗余信息由此产生。因此如果只有很少的椭球丢失，网格模型的拓扑信息和整体形状不会产生大的变化。冗余信息不会使存储需求增加，因为每个椭球和三角网格中每个顶点一样，只需要9个存储纯量。其传送过程如下：首先种子点采样生成椭球集合；传送优化选择的椭球子集；
接收方抽取等值面重构逼近网格模型；以陆续到来的原始网格顶点替换临时网格模型的顶点（如图20）。
1996年，托比（Taubin）[46]首先在三维网格模型几何压缩处理中应用傅立叶变换：由任意拓扑结构的网络顶点邻接矩阵及其顶点价数，得到网格Laplacian矩阵的定义及由其特征向量构成的空间的正交基底，相对应的特征值即为频率。三维网格顶点的坐标向量在该空间的投影即为该网格模型的几何光谱。
2000年，卡尼尔（K a r n i ）和考斯曼（Gotsman）[47]将几何网格分割片光谱推广到压缩问题上。光谱直接应用于定义几何网格的拓扑信息时，会产生伪频率信息。而且对于大规模的网格，由于在网格顶点数目多于1,000时，
西安pm2.5
Laplacian矩阵特征向量的计算几乎无法进行。
图19 三维网格模型的分割检索
图20 基于椭球分割的三维网格模型压缩传输
因此该工作在最小割边前提下，首先将网格模型分割为有限数目的、各片顶点数目接近的分割片。该方法有微小的压缩损失，且在分割片边界出现人工算法痕迹。然后利用Tutte投影，将由于各分割片拓扑不同而各异的网格分割片基函数，统一为规整的6度网格分割片基函数，提高了计算效率。由于分割方法的限制，该算法只适用于没有尖锐边缘特征的光顺网格模型。2003年艾尔夫斯（Alface）[38]
提出了光谱表示交叠方法：扩张分割片，使分割片之间产生交叠。该工作（如图21）明显地改进了在分割片边界上的人工算法痕迹。
高质量的网格压缩传送的前提是良好的网格分割。
纹理贴图中的网格模型分割
如果网格模型的离散化足够精细，比如细分网格，那么直接对顶点进行纹理绘制就足够了。否则就要把网格模型分割为一组与圆盘同胚的、便于进行参数化的分割片；再对每片非折叠的分割片参数化；最后分割片在纹理空间里拼接起来。
面向纹理的分割算法一般要求满足两个条件：第一，分割片的不连续边界不能出现人工算法痕迹；第二，分割片与圆盘同胚、而且不引入太大的变形就可以参数化。但不要求有意义的分割结果。
2001年，桑达[35]基于半边折叠的渐近网格算法[70]，使用区域增长法对网格模型进行分
割。首先网格模型的每一个面片都被看作是独立的分割片。然后每个分割片与其邻接分割片组对、合并。在最小合并计算量优先合并的原则下，循环执行分割片对的合并操作，并更新其他待合并分割片的计算量。当计算量超出用户指定的阈值时，停止合并操作。分割片之间的边界为逼近角点间直线段的最短路径，从而减轻了锯齿情况（如图22）。
2002年，利维[39]给出的算法将网格模型分割为具有自然形状的分割片，但仍然没有得到有意义的分割结果。为了与圆盘同胚，该文自
动寻位于网格模型高曲率区域的特征曲线，避免在平坦区域内产生分割片边界，并增长分割片使他们在特征曲线上相交，尽量获得尺寸较大的分割片。
网格模型分割局部性会改善纹理映射、网格参数化的扭曲效果。
动画与几何变形中的网格模型分割
影视动画制作中，多个对象间的几何变形特技可以基于网格模型分割的局部区域预处理来实现。如建立动画区域对应关系，对多个模型进行“一致”分割，然后在多个模型的对应分割片之间做变形，将提高动画制作的精度和真实性；且每个无拓扑信息的面片模型都可用来建立分割片对应；模型间的“一致”分割有利于保持模型的总体特征。目前多数的自动对应算法精度较低。手工交互指定对应关系的效率又太低。
1996年，克里希纳默西[25]
的工作从高密
图21 基于分割的三维模型光谱压缩
图22 面向纹理贴图的三维模型分割
度、非规整、任意拓扑结构的多边形网格出发，手工指定分割边界，构造张量积样条曲面片的动画模型。首先在多边形网格的二维投影空间交互选择一个顶点序列，然后自动地将顶点序列关联到网格上最近的顶点上；对于序列中前后两个顶点，计算在网格曲面上连接它们的最短路径；对该路径在面片内部进行双三次B样条曲面拟合、光顺、重新采样，得到分割片在两个顶点之间的边界曲线。计算量的付出依然是非常昂贵的。
1999年，格雷戈里等[30]在两个输入的多面体表面网格上，交互选择多面体顶点，作为一个对应链的端点。对应链上其他顶点通过计算曲面上端点对之间最短路径上的顶点来确定，得到由这些顶点和边构成的多面体表面网格的连通子图。然后，算法将每一个多面体表面网格分割为相同数目的分割片，每个分割片都与圆盘同胚。最后在分割片之间建立映射、重构、局部加细完成对应关系的建立；最后插值实现两个多面体之间的变形（如图23）。
2002年，史拉夫曼[45]的工作不再限制输入网格必须是零亏格、或者是二维流形的。算法通过迭代，局部优化面片的归属来改进某些全局函数，因此与图像分割K－均值聚类方法相近。分割片的最终数目可以由用户预先指定，从而避免了过度分割，且适用于动画制作的需求。分割过程的关键在于确认给定的两个面片是否属于同一个分割片。史拉夫曼提出新的网格模型分割方法和新的柱状分割片投影算法，降低了工作量、提高了精度。其分割结果是非层次（如图24）。
中国妇幼卫生监测网基于分割的变形对于保持模型的局部特征有着重要的意义。局部投影算法能够产生精细的对应区域，且能自动产生有意义的分割片。
模型简化中的网格模型分割
网格模型简化指把给定的一个有较多面片的网格模型，处理为另一个保持原始模型形状特征的、但具有较少面片数目和较大简化/变形比的新模型。
三维网格模型分割显然可以被看作是一种网格简化。基本思想是在简化中增加一个预处理过程，先按模型显著特征将其分割为若干分割片，然后在每个分割片内应用简化算法，由此保持了模型的显著特征，如特征边、特征尖锐以及其他精细的细节。比如把曲率变化剧烈的区域作为分割边界，将曲率变化平缓的区域
图23 动画制作中的交互分割
图24 变形中的聚类分割男子做前列腺电切术后死亡
我的钱包我做主超市各自分割开来，就是基于曲率阈值的网格简化方法。在去除过度分割后，网格分割片数目被限制在指定的范围内。
2001年，嘉兰迪[71]基于顶点收缩的简化，提出一种基于层次关系的面片聚类算法（如图25）。其目标是针对非常复杂的、计算量非常大的网格，或者稠密点云，为求交、碰撞检测、绘制、曲面简化等工作的应用提供层次关系树，以提高计算速度。与其他工作不同之处是该工作是基于面片对的。其优点是合并的过程中产生了聚类的层次结构二叉树；同时避免了指定种子面片。对于面片对的收缩，是在网格的对偶图上以顶点对收缩的形式进行的，原始网格的几何信息、拓扑信息没有任何变化。算法输入网格为三角网，其对偶图结点度数均为3。随着收缩进行，对偶图结点的度数发生变化。该工作给出了在求交、碰撞检测、曲面简化、多分辨率辐射度计算等方面的应用。这些应用的共同特点是使用曲面的区域总体性质、而不是曲面的精确几何信息。
CAD中的分割与编辑
三维模型的逆向工程在近年来成为一个新的研究热点，它表明了传统CAD造型技术提出了融合离散网格模型方法的愿望。
从多幅深度图像重建CAD模型的工作是一个逆向工程。这个过程中需要对点云、深度图
像等数据进行特征抽取和分割，要求相应算法必须能够保证一定的精度。分割后网格模型应该具有较好的、适合参数化的外形和轮廓，以便于使用传统CAD方法进行处理（如图26）。
现存三维模型有时并不适合特定的应用，这样修改、编辑现有的三维模型也是一个非常重要的工作。
在三维模型分割工作的基础上，可以实现分区剪切、复制、粘贴、修正等三维模型编辑工作（如图27）。
结论及对未来工作的展望
从目前国内外研究及应用来看，与数字图像处理、视频分析、计算机视觉和模式识别领
域中的分割工作一样，三维模型分割是数字几
图25 三维网格模型简化中的谱系聚类分割
图26 工厂扫描点云重建中的分割
图27 三维模型分割在模型编辑中的应用
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议