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

0 引言

三維拓撲結構信息能準確而精煉的描述三維模型的形狀特性，其在模型的變形、簡化、曲面重建、形狀分析、模型匹配與檢索、壓縮傳輸和行為分析[1]等許多領域有廣泛的應用和重要的作用。

目前，中軸線（骨架）法、Reeb圖法是描述三維模型的拓撲結構的主要方法。中軸線（骨架）法從三維模型的骨架角度來表達三維模型的拓撲結構特征。2006年,Dey T K等給出了一種網(wǎng)格模型的骨架提取方法[2]；2008年，Kin-Chung Au等構造普拉斯矩陣，通過對網(wǎng)格模型微分域的操作進行幾何收縮來提取模型骨架[3]；2011年，He Zhiyin等提出的基于表面及切向屬性的點模型骨架提取方法，通過控制表面屬性和切向屬性來控制模型的幾何收縮，從而盡可能的保持模型的表面特性逼近骨架[4]。此類型方法在模型分辨率較高的條件下可以得到較好的提取效果，但是其缺點是對邊界噪聲敏感，對模型的分辨率要求較高，迭代計算復雜度高。

Reeb圖法從三維模型連通區(qū)域的角度來表達三維模型的拓撲結構特征，是一種重要的三維模型拓撲結構描述方式。該方法通過將函數(shù)值相同且在同一連通分量上的點聚類來提取拓撲結構特征。Reeb圖在計算機圖形學的許多領域都有重要應用。2004年，Tony Tung等人將Reeb圖應用于3D網(wǎng)格模型檢索[5]；2008年，S.Biasotti等人將Reeb圖應用于形狀分析[6]。

Reeb圖的計算方法主要有：Shinagawa等人應用高度函數(shù)法，根據(jù)等高線生成Reeb圖[7]，該方法函數(shù)定義簡單，計算方便，但是缺點是聯(lián)通關系計算復雜，所得的 Reeb圖有時處于模型體外；K.Cole-McLaughlin等人利用映射得到Morse函數(shù)，并尋找關鍵點，最終確定Reeb圖[8]，該方法存在連接計算困難，且所得的Reeb圖也有可能處于模型體外。針對上述問題，使用測地距離構建Morse函數(shù)，然后根據(jù)網(wǎng)格的三角面關系提取Reeb圖，計算復雜度低，且能確保提取的Reeb圖位于模型體內(nèi)。

隨著多核計算機的迅速發(fā)展，基于多核的并行算法設計逐漸成為研究熱點[9-11]。目前，基于Reeb圖的3D拓撲信息提取的并行實現(xiàn)方法的研究鮮有報道。三維拓撲信息的提取數(shù)據(jù)量大，計算復雜，不利于進一步應用，針對該問題，提出了在雙核處理器上Reeb圖法提取拓撲信息的并行實現(xiàn)方法，以加快提取速度。通過分析Reeb圖提取過程的內(nèi)在并行性，并行實現(xiàn)Reeb圖提取。實驗結果表明，該方法能夠有效的加快Reeb圖提取的速度，加速比達到1.70。

1 提取Reeb圖的原理

提取Reeb圖的流程如圖1所示，首先讀取三角形網(wǎng)格文件的網(wǎng)格數(shù)據(jù)，得到頂點坐標和三角形關系；然后設定基準點，計算其他點到基準點的測地距離，并依此構建Morse函數(shù)；利用Morse函數(shù)值和網(wǎng)格頂點的三角面關系，提取得到初始的Reeb圖；最后進行濾波，去除冗余信息，得到最終的 Reeb圖。

圖1 Reeb圖提取流程

1.1 使用測地距離構建Morse函數(shù)

測地線是指曲面上待測兩點間的最短路徑。對于三角形網(wǎng)格模型，約定測地線是模型表面兩點的最短路徑，兩點經(jīng)過曲面各點連接的長度即為兩點間的測地距離。計算測地距離前需要標定基準點，根據(jù)三維模型拓撲結構的不同，通常采用的基準點標定方法有最高點法、空間距離最遠點法和質心法。

Morse函數(shù)[12]是定義在流型M上的一個光滑函數(shù)，該函數(shù)僅有孤立可數(shù)的非退化臨界點（極值點和鞍點）。Morse理論可有效用于特征提取。

1.2 Reeb圖及計算方法

Reeb圖是描述三維模型拓撲結構的一種重要方式。Reeb圖的定義最早由數(shù)學家George Reeb給出。對于流形網(wǎng)格M，假設f是定義在該網(wǎng)格上的光滑連續(xù)函數(shù)，并將 M 映射成一個新的圖形 R，即f:M→R。對于點x,y∈M，若f-1(t)= x= y 及f(x) = f(y) = t ，在圖形R中，x和y映射同一個點，那么圖形R是網(wǎng)格M通過函數(shù)f生成的Reeb圖。圖2為一個Reeb圖示例。

圖2 Reeb圖示例

Reeb圖法描述三維拓撲結構的計算方法是：首先，使用測地距離構造Morse函數(shù)，并定義為網(wǎng)格模型的連續(xù)函數(shù)f；網(wǎng)格頂點中，函數(shù)值相同且在同一連通分量上的點被映射為Reeb圖上的一個點；根據(jù)網(wǎng)格模型的三角面關系，得到Reeb圖上各節(jié)點的鄰接關系，最終得到Reeb圖。

1.3 冗余濾波

初始的Reeb圖可能存在冗余信息，不夠精煉。圖3(a)中粗線條部分表示存在冗余信息的弧，將冗余弧合并后得到新的Reeb圖3(b)，圖3(b)中新生成的節(jié)點仍然存在冗余，可以刪除，最終得到如圖3(c)所示Reeb圖。

圖3 濾波示意

2 算法的并行實現(xiàn)

并行實現(xiàn)方式有任務分解和數(shù)據(jù)分解。任務分解是將算法中相互獨立的任務模塊并發(fā)的執(zhí)行，由于算法的各個任務模塊有嚴格的串行順序，所以不滿足任務分解的條件。數(shù)據(jù)分解是將待處理數(shù)據(jù)集進行分組，可通過派生線程完成數(shù)據(jù)并行處理，是一種比較普遍的并行實現(xiàn)方式。

Reeb圖提取的關鍵部分在于Morse函數(shù)的構造和Reeb圖計算。使用測地距離構造Morse函數(shù)首先需要讀取網(wǎng)格文件建立三維目標的頂點、邊和三角面的數(shù)據(jù)結構，并建立三者之間的相互關系，其中頂點數(shù)據(jù)結構主要保存頂點的空間坐標，邊數(shù)據(jù)結構保存邊的兩個頂點的索引以及邊的長度，而面數(shù)據(jù)結構則是存儲網(wǎng)格的三角面，通過保存三角面的三個頂點來存儲。這個過程存在大量的查找、賦值以及空間距離計算等操作，耗時較大。Reeb圖計算時，需要將網(wǎng)格模型的所有三角形根據(jù)三角面關系，通過三角形頂點和邊的加權計算，最終得到Reeb圖的節(jié)點和弧，耗時較大。為加快Reeb圖提取速度，對上述兩個部分進行并行優(yōu)化。

2.1 構造Morse函數(shù)的并行實現(xiàn)

構造 Morse函數(shù)包括數(shù)據(jù)結構的建立和使用Dijkstra算法計算測地距離。由于邊的長度已經(jīng)在建立數(shù)據(jù)結構時得到，測地距離的計算耗時較小，且由于存在相關性不能并行處理，因此僅對數(shù)據(jù)結構的建立進行并行優(yōu)化。

網(wǎng)格文件（如.obj和.off）中包括頂點信息和三角面信息，其中三角面信息由頂點索引確定，在建立頂點數(shù)據(jù)結構后，網(wǎng)格中每個三角形的面信息和邊信息都由相應的頂點確定，不同三角形之間的處理是獨立的；因此，根據(jù)網(wǎng)格文件中三角面的數(shù)目，將面信息和邊信息的數(shù)據(jù)結構建立等分成兩部分，放到不同的核上處理。如圖4所示，假設三維模型有 1000個頂點信息、2000個面信息，平均分為2組用2個核執(zhí)行。

圖4 頂點、邊和面數(shù)據(jù)結構建立并行示意

2.2 Reeb圖計算的并行實現(xiàn)

圖5 描述了Reeb圖提取的具體計算過程， 左邊是網(wǎng)格數(shù)據(jù)，右邊是生成的Reeb圖。網(wǎng)格數(shù)據(jù)包含頂點、邊和面信息；Reeb圖結構包含節(jié)點和弧，節(jié)點存儲計算得到的Reeb圖節(jié)點的空間坐標信息，弧是由一系列坐標點組成，該系列坐標點的起始點和終點是Reeb圖的節(jié)點。圖5(a)、圖5（b）中，Reeb圖中的 n0、 n2、 n3是通過三角形中相應頂點v0、 v2、 v3生成的 。圖中α0→(e1,e4)表示弧α0是由邊e1、 e4計算得到。圖5(c)中，新輸入一個由頂點v1和兩條邊 e0、 e2組成的新三角形，則由v1與α0加權計算得到一個新節(jié)點 n1，其相應的弧也發(fā)生改變，如圖5(d)中所示，新輸入的邊0e會對弧0α產(chǎn)生影響。按照上述計算過程，將網(wǎng)格中的所有三角形進行加權計算提取Reeb圖。

圖5 Reeb圖計算示意

不同三角形之間的計算存在相關性，但是每個三角形僅與相鄰三角形有關，且三角形的計算順序不影響算法結果。為了實現(xiàn)Reeb計算的并行化，首先將所有三角面數(shù)據(jù)根據(jù)頂點到源點的測地距離進行排序；然后將全部三角面按頂點的權重大小切割成兩個部分，分別放到不同的線程上進行Reeb計算，得到兩個子Reeb圖，再將子Reeb圖連接合并。由于兩個部分在切割處附件的三角形是有相關性的，合并后的Reeb圖在切割處可能會存在錯位和冗余，濾波之后可得到最終的Reeb圖。解決方案如圖6所示。

圖6 Reeb計算并行示意

3 實驗結果與分析

實驗平臺為雙核處理器(Intel(R) Core?2 Duo CPU)，主頻為1.73 GHz，操作系統(tǒng)為Windows XP SP3。編程用C++實現(xiàn)，在Visual Studio 2005上進行編譯。表1為實驗數(shù)據(jù)。

Reeb圖提取的加速比如表2所示，對Reeb圖提取過程的并行實現(xiàn)，加快了提取速度，加速比可達1.70。從表中可以看到，由于頂點數(shù)目與三角面數(shù)目的不同，不同實驗對象的加速比稍有差別，但都達到了比較滿意的加速效果，由于存在一些串行模塊，數(shù)據(jù)量越大加速效果越好。并行模塊的加速比沒有達到雙核平臺的理論加速比 2.0，其原因是線程的創(chuàng)建和銷毀，以及線程間的同步等額外開銷增加了算法的時間開銷。另一個制約加速比的因素是雙核負載不均衡，降低了并行執(zhí)行的效果。在構造Morse函數(shù)的模塊中，建立三角面數(shù)據(jù)結構需要查找相應頂點信息，由于查找路徑的長度不同，兩個核所承載的計算量有差別。在Reeb圖計算的過程中，增加了對數(shù)據(jù)的排序和對子Reeb計算結果的合并過程，增加了額外的時間開銷，且同樣存在負載不均勻的額問題，所以并行效果較差。

表1 實驗數(shù)據(jù)包

表2 算法加速比 ms

Reeb圖提取的結果如圖 7所示，圖 7(a)、圖7(e)為網(wǎng)格模型，圖7(b)、圖7(f)為傳統(tǒng)算法提取得到的Reeb圖；圖7(c)、圖7(g)為并行計算但沒有連接子Reeb圖并濾波的結果，可以看到圖形的中間部分存在錯位和冗余節(jié)點；圖7(d)、圖7(h)是連接和濾波后的并行提取結果，與圖 7(b)、圖 7(f)沒有明顯差別。從實驗結果可知，Reeb圖提取和并行加速的結果是另人滿意的。

圖7 Reeb圖提取效果對比

4 結語

提出了一種三維拓撲信息提取的并行實現(xiàn)方法。利用目標的三維網(wǎng)格提供的頂點信息，通過頂點的測地距離構建Morse函數(shù)，并通過網(wǎng)格的三角面關系提取Reeb圖，得到目標的拓撲結構描述。通過對關鍵模塊的并行實現(xiàn)，加快了拓撲信息提取的速度。實驗結果表明，經(jīng)過并行化，加速比達到了 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].計算機研究與發(fā)展,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] 徐潔,周利斌.基于多核防火墻的防病毒引擎設計與實現(xiàn)[J].信息安全與通信保密,2010(02): 95-99.

[11] 王智民,楊聰毅.基于多核的安全網(wǎng)關設計與實現(xiàn)[J].信息安全與通信保密,2009(06):101-104.

[12] 薛紅娟, 顧耀林. 拓撲分析在海洋特征提取中的應用[J].計算機工程, 2009, 35(03):262-265.