一種三維拓撲信息提取的并行實現方法﹡

王成彰， 郭 立， 劉 鵬， 于 昊

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.