一种三维拓扑信息提取的并行实现方法﹡

王成彰， 郭 立， 刘 鹏， 于 昊

0 引言

三维拓扑结构信息能准确而精炼的描述三维模型的形状特性，其在模型的变形、简化、曲面重建、形状分析、模型匹配与检索、压缩传输和行为分析[1]等许多领域有广泛的应用和重要的作用。

目前，中轴线（骨架）法、Reeb图法是描述三维模型的拓扑结构的主要方法。中轴线（骨架）法从三维模型的骨架角度来表达三维模型的拓扑结构特征。2006年,Dey T K等给出了一种网格模型的骨架提取方法[2]；2008年，Kin-Chung Au等构造普拉斯矩阵，通过对网格模型微分域的操作进行几何收缩来提取模型骨架[3]；2011年，He Zhiyin等提出的基于表面及切向属性的点模型骨架提取方法，通过控制表面属性和切向属性来控制模型的几何收缩，从而尽可能的保持模型的表面特性逼近骨架[4]。此类型方法在模型分辨率较高的条件下可以得到较好的提取效果，但是其缺点是对边界噪声敏感，对模型的分辨率要求较高，迭代计算复杂度高。

Reeb图法从三维模型连通区域的角度来表达三维模型的拓扑结构特征，是一种重要的三维模型拓扑结构描述方式。该方法通过将函数值相同且在同一连通分量上的点聚类来提取拓扑结构特征。Reeb图在计算机图形学的许多领域都有重要应用。2004年，Tony Tung等人将Reeb图应用于3D网格模型检索[5]；2008年，S.Biasotti等人将Reeb图应用于形状分析[6]。

Reeb图的计算方法主要有：Shinagawa等人应用高度函数法，根据等高线生成Reeb图[7]，该方法函数定义简单，计算方便，但是缺点是联通关系计算复杂，所得的 Reeb图有时处于模型体外；K.Cole-McLaughlin等人利用映射得到Morse函数，并寻找关键点，最终确定Reeb图[8]，该方法存在连接计算困难，且所得的Reeb图也有可能处于模型体外。针对上述问题，使用测地距离构建Morse函数，然后根据网格的三角面关系提取Reeb图，计算复杂度低，且能确保提取的Reeb图位于模型体内。

随着多核计算机的迅速发展，基于多核的并行算法设计逐渐成为研究热点[9-11]。目前，基于Reeb图的3D拓扑信息提取的并行实现方法的研究鲜有报道。三维拓扑信息的提取数据量大，计算复杂，不利于进一步应用，针对该问题，提出了在双核处理器上Reeb图法提取拓扑信息的并行实现方法，以加快提取速度。通过分析Reeb图提取过程的内在并行性，并行实现Reeb图提取。实验结果表明，该方法能够有效的加快Reeb图提取的速度，加速比达到1.70。

1 提取Reeb图的原理

提取Reeb图的流程如图1所示，首先读取三角形网格文件的网格数据，得到顶点坐标和三角形关系；然后设定基准点，计算其他点到基准点的测地距离，并依此构建Morse函数；利用Morse函数值和网格顶点的三角面关系，提取得到初始的Reeb图；最后进行滤波，去除冗余信息，得到最终的 Reeb图。

图1 Reeb图提取流程

1.1 使用测地距离构建Morse函数

测地线是指曲面上待测两点间的最短路径。对于三角形网格模型，约定测地线是模型表面两点的最短路径，两点经过曲面各点连接的长度即为两点间的测地距离。计算测地距离前需要标定基准点，根据三维模型拓扑结构的不同，通常采用的基准点标定方法有最高点法、空间距离最远点法和质心法。

Morse函数[12]是定义在流型M上的一个光滑函数，该函数仅有孤立可数的非退化临界点（极值点和鞍点）。Morse理论可有效用于特征提取。

1.2 Reeb图及计算方法

Reeb图是描述三维模型拓扑结构的一种重要方式。Reeb图的定义最早由数学家George Reeb给出。对于流形网格M，假设f是定义在该网格上的光滑连续函数，并将 M 映射成一个新的图形 R，即f:M→R。对于点x,y∈M，若f-1(t)= x= y 及f(x) = f(y) = t ，在图形R中，x和y映射同一个点，那么图形R是网格M通过函数f生成的Reeb图。图2为一个Reeb图示例。

图2 Reeb图示例

Reeb图法描述三维拓扑结构的计算方法是：首先，使用测地距离构造Morse函数，并定义为网格模型的连续函数f；网格顶点中，函数值相同且在同一连通分量上的点被映射为Reeb图上的一个点；根据网格模型的三角面关系，得到Reeb图上各节点的邻接关系，最终得到Reeb图。

1.3 冗余滤波

初始的Reeb图可能存在冗余信息，不够精炼。图3(a)中粗线条部分表示存在冗余信息的弧，将冗余弧合并后得到新的Reeb图3(b)，图3(b)中新生成的节点仍然存在冗余，可以删除，最终得到如图3(c)所示Reeb图。

图3 滤波示意

2 算法的并行实现

并行实现方式有任务分解和数据分解。任务分解是将算法中相互独立的任务模块并发的执行，由于算法的各个任务模块有严格的串行顺序，所以不满足任务分解的条件。数据分解是将待处理数据集进行分组，可通过派生线程完成数据并行处理，是一种比较普遍的并行实现方式。

Reeb图提取的关键部分在于Morse函数的构造和Reeb图计算。使用测地距离构造Morse函数首先需要读取网格文件建立三维目标的顶点、边和三角面的数据结构，并建立三者之间的相互关系，其中顶点数据结构主要保存顶点的空间坐标，边数据结构保存边的两个顶点的索引以及边的长度，而面数据结构则是存储网格的三角面，通过保存三角面的三个顶点来存储。这个过程存在大量的查找、赋值以及空间距离计算等操作，耗时较大。Reeb图计算时，需要将网格模型的所有三角形根据三角面关系，通过三角形顶点和边的加权计算，最终得到Reeb图的节点和弧，耗时较大。为加快Reeb图提取速度，对上述两个部分进行并行优化。

2.1 构造Morse函数的并行实现

构造 Morse函数包括数据结构的建立和使用Dijkstra算法计算测地距离。由于边的长度已经在建立数据结构时得到，测地距离的计算耗时较小，且由于存在相关性不能并行处理，因此仅对数据结构的建立进行并行优化。

网格文件（如.obj和.off）中包括顶点信息和三角面信息，其中三角面信息由顶点索引确定，在建立顶点数据结构后，网格中每个三角形的面信息和边信息都由相应的顶点确定，不同三角形之间的处理是独立的；因此，根据网格文件中三角面的数目，将面信息和边信息的数据结构建立等分成两部分，放到不同的核上处理。如图4所示，假设三维模型有 1000个顶点信息、2000个面信息，平均分为2组用2个核执行。

图4 顶点、边和面数据结构建立并行示意

2.2 Reeb图计算的并行实现

图5 描述了Reeb图提取的具体计算过程， 左边是网格数据，右边是生成的Reeb图。网格数据包含顶点、边和面信息；Reeb图结构包含节点和弧，节点存储计算得到的Reeb图节点的空间坐标信息，弧是由一系列坐标点组成，该系列坐标点的起始点和终点是Reeb图的节点。图5(a)、图5（b）中，Reeb图中的 n0、 n2、 n3是通过三角形中相应顶点v0、 v2、 v3生成的 。图中α0→(e1,e4)表示弧α0是由边e1、 e4计算得到。图5(c)中，新输入一个由顶点v1和两条边 e0、 e2组成的新三角形，则由v1与α0加权计算得到一个新节点 n1，其相应的弧也发生改变，如图5(d)中所示，新输入的边0e会对弧0α产生影响。按照上述计算过程，将网格中的所有三角形进行加权计算提取Reeb图。

图5 Reeb图计算示意

不同三角形之间的计算存在相关性，但是每个三角形仅与相邻三角形有关，且三角形的计算顺序不影响算法结果。为了实现Reeb计算的并行化，首先将所有三角面数据根据顶点到源点的测地距离进行排序；然后将全部三角面按顶点的权重大小切割成两个部分，分别放到不同的线程上进行Reeb计算，得到两个子Reeb图，再将子Reeb图连接合并。由于两个部分在切割处附件的三角形是有相关性的，合并后的Reeb图在切割处可能会存在错位和冗余，滤波之后可得到最终的Reeb图。解决方案如图6所示。

图6 Reeb计算并行示意

3 实验结果与分析

实验平台为双核处理器(Intel(R) Core™2 Duo CPU)，主频为1.73 GHz，操作系统为Windows XP SP3。编程用C++实现，在Visual Studio 2005上进行编译。表1为实验数据。

Reeb图提取的加速比如表2所示，对Reeb图提取过程的并行实现，加快了提取速度，加速比可达1.70。从表中可以看到，由于顶点数目与三角面数目的不同，不同实验对象的加速比稍有差别，但都达到了比较满意的加速效果，由于存在一些串行模块，数据量越大加速效果越好。并行模块的加速比没有达到双核平台的理论加速比 2.0，其原因是线程的创建和销毁，以及线程间的同步等额外开销增加了算法的时间开销。另一个制约加速比的因素是双核负载不均衡，降低了并行执行的效果。在构造Morse函数的模块中，建立三角面数据结构需要查找相应顶点信息，由于查找路径的长度不同，两个核所承载的计算量有差别。在Reeb图计算的过程中，增加了对数据的排序和对子Reeb计算结果的合并过程，增加了额外的时间开销，且同样存在负载不均匀的额问题，所以并行效果较差。

表1 实验数据包

表2 算法加速比 ms

Reeb图提取的结果如图 7所示，图 7(a)、图7(e)为网格模型，图7(b)、图7(f)为传统算法提取得到的Reeb图；图7(c)、图7(g)为并行计算但没有连接子Reeb图并滤波的结果，可以看到图形的中间部分存在错位和冗余节点；图7(d)、图7(h)是连接和滤波后的并行提取结果，与图 7(b)、图 7(f)没有明显差别。从实验结果可知，Reeb图提取和并行加速的结果是另人满意的。

图7 Reeb图提取效果对比

4 结语

提出了一种三维拓扑信息提取的并行实现方法。利用目标的三维网格提供的顶点信息，通过顶点的测地距离构建Morse函数，并通过网格的三角面关系提取Reeb图，得到目标的拓扑结构描述。通过对关键模块的并行实现，加快了拓扑信息提取的速度。实验结果表明，经过并行化，加速比达到了 1.7。下一步工作是将Reeb图用于人体等目标的异常行为检测。

[1] 关华,郭立,李文.一种基于 Reeb图的三维肢体分割算法[J].通信技术,2011,44(11): 63-65.

[2] DEY T K,SUN J. Defining and Computing Curve Skeletons with Medial Geodesic Function[C]// Proc of the 4th Eurographics Symp on Geometry Processing.New York; ACM, 2006: 143-152.

[3] AU O K C, TAI C L, CHU H K, et al. Skeleton Extraction by Mesh Contraction[J]. ACM Trans on Graphics: Proc of SIGGRAPH 2008, 2008, 27(03):1-10.

[4] 何志莹,梁晓辉,赵沁平. 基于表面及切向属性的点模型骨架提取方法[J].计算机研究与发展,2012, 49(07):1377-1387.

[5] TUNG T,SCHMITT F. Augmented Reeb Graphs for Content-based Retrieval of 3D Mesh Models[C]//Proceedings of the Shape Modeling International.Genova: IEEE, 2004: 157-166.

[6] BIASOTTI S,GIORGI D,SPAGNUOLO M,et al. Reeb Graphs for Shape Analysis and Applications[J].Theoretical Computer Science,2008, 392(1-3):5-22.

[7] SHINAGAWA Y,KUNII T.Constructing a Reeb Graph Automatically from Cross Sections[J]. IEEE Computer Graphics and Applications, 1991, 11(06):44–51.

[8] COLE-MCLAUGHLIN K,EDELSBRUNNER H,HARER J, et al.Loops in Reeb Graphs of 2-manifolds [C]//Proceedings of the 19th Annual Symposium on Computational Geometry.New York;ACM,2003:344-350.

[9] 范文,吕治国.H.264并行视频编码的分配机制的研究[J].通信技术,2010,43(08):244-246.

[10] 徐洁,周利斌.基于多核防火墙的防病毒引擎设计与实现[J].信息安全与通信保密,2010(02): 95-99.

[11] 王智民,杨聪毅.基于多核的安全网关设计与实现[J].信息安全与通信保密,2009(06):101-104.

[12] 薛红娟, 顾耀林. 拓扑分析在海洋特征提取中的应用[J].计算机工程, 2009, 35(03):262-265.