一種基于Reeb圖的3維肢體分割算法

關(guān) 華，郭 立，李 文

（中國科學(xué)技術(shù)大學(xué) 電子科學(xué)與技術(shù)系，安徽 合肥 230027）

0 引言

人體行為分析與識別已成為計算機視覺領(lǐng)域的一個熱點問題，其廣泛應(yīng)用于計算機動畫、安全通訊[1]、公共安全[2]等。人體行為分析與識別的一個難點之一就是如何完成重構(gòu)人體模型的肢體分割，即如何將重構(gòu)人體模型分割成一個個有意義的肢體部位，如頭、胳膊、腿等。

近些年，國內(nèi)外針對肢體分割提出了各種不同的算法。Sangho Park等人采用高斯馬爾科夫模型（GMM，Gaussian Markov Model）模型完成像素的顏色信息描述，然后利用馬爾科夫隨機場來分割肢體[3]，此方法較依賴模型本身；Cheung等使用EM算法來完成3維肢體分割，其利用前幀的結(jié)果來完成后面幀行為主體的3維肢體分割，因而容易造成累計誤差[4]；Jun-Wei Hsieh等人采用三角形剖面和輪廓曲率的方式來完成三維肢體的分割[5]，此方法有時會造成誤分割；谷軍霞等人采用了一種半監(jiān)督聚類的方法來完成 3維肢體的分割，該方法需要一定的人際交互[6]；曹丹華等人采用了基于最小負曲率點搜索的方式來完成人體模型的肢體分割[7]，此方法是在2維圖像上進行的；Reeb圖在行為分析與識別方面有較好的應(yīng)用[8]。

這里基于 Reeb圖來完成對重構(gòu)人體模型的三維肢體肢體分割，其能較好的對3維人體模型進行肢體分割，分割質(zhì)量較好，并且基于 Reeb圖的概念，計算復(fù)雜度較低，同時避免了人機交互的過程。文中算法如圖1所示。

圖1 基于Reeb圖的3維肢體分割流程

圖1中首先得到重構(gòu)模型的Reeb圖，計算重構(gòu)模型各點的測地距離，構(gòu)造Morse函數(shù)，然后根據(jù)Morse函數(shù)提取重構(gòu)模型的Reeb圖；得到Reeb圖后，對Reeb圖進行分割，完成Reeb圖的肢體分割圖；最后，計算重構(gòu)模型和Reeb圖各點的映射關(guān)系，反映射從而實現(xiàn)重構(gòu)模型的肢體分割。

1 Reeb圖及相關(guān)概念

1946年數(shù)學(xué)家George Reeb提出了一種描述拓撲結(jié)構(gòu)的方式[8]，這就是 Reeb圖。假設(shè)一個流形 M，在其上定義一個標量函數(shù)f，M上的點根據(jù)函數(shù)f得到一個值，那么處在同一水平線且在同一個連通域的點在Reeb圖上對應(yīng)同一個點。圖2所以唯一Reeb圖示例。

圖2 Ree圖示例：左邊為流形，右邊為相應(yīng)Reeb圖

定義1（Reeb圖）：假設(shè)有一流形網(wǎng)格M，f是定義在該網(wǎng)格上的函數(shù)，圖形R是網(wǎng)格M通過函數(shù)f得到的圖形，f∶M→R。有兩個點x,y∈M，若f-1(t) =x =y，即f(x) =f(y)=t，且x和y屬于同一連通域，那么在圖形R中，點x和y映射同一個點，那么圖形R是流形網(wǎng)格M在函數(shù)f上生成的Reeb圖。

定義2（測地距離）：測地線是連接曲面上給定兩點間的最短路徑。文中采用的測地距離，約定為三維模型上兩點間的表面最短距離，即通過表面各點連接的最短長度和。

定義3（Morse函數(shù)）：定義在流形M上的一個連續(xù)光滑函數(shù)f，流形邊緣?M若滿足 f (? M)=0，且f只有有限個退化臨界點（最大值、最小值和鞍點），那么函數(shù)f則為Morse函數(shù)。

2 Reeb圖的計算

圖3所示為文中使用的Reeb圖計算示意。左邊為重構(gòu)三角網(wǎng)格的三角形，圖3(a)為三角形，v0、v2、v3為三角形的3個頂點，e1、e3、e4為三角形的3條邊，圖3(b)為該三角形生成的Reeb圖，n0、n2、n3為三個頂點生成的Reeb節(jié)點，而弧 α0，α2分別由邊 e1、e4和邊 e3、e4上的點加權(quán)生成的Reeb弧；圖3(c)為在原三角形上增加一個新三角形，且加了新頂點v1和新邊e0、e2，圖3(d)為新增加三角形后計算得到的Reeb圖，其中新生成節(jié)點n1，原有兩天弧α0，α2需要和新邊e0、e2重新加權(quán)計算，并且新加弧α1，該弧由邊e1、e2、e4加權(quán)計算得到。然后再增加新三角形，按照上面所述計算新的 Reeb圖，直到所有的三角形增加完畢，這樣就計算得到最終的Reeb圖。

圖3 Reeb圖計算示意

此方法得到的Reeb圖可能存在多余節(jié)點，如圖4(a)加粗線所示，這不僅造成了存儲浪費，且在下部的 Reeb圖的肢體分割中造成誤差，因而需要對這種弧和節(jié)點進行修改，刪除該節(jié)點，形成新弧，修改得到的新弧如圖4(b)所示。

圖4 濾波示意圖

3 人體模型的肢體分割

3.1 關(guān)鍵節(jié)點的建立

得到Reeb圖后，為了對Reeb圖進行分割，需要先在Reeb圖上建立關(guān)鍵節(jié)點。設(shè)定度不為 2的節(jié)點作為關(guān)鍵節(jié)點，如圖5所示，圖5(a)為一系列點組成的3條弧，圖5(b)在三條弧上建立關(guān)鍵節(jié)點后的圖，關(guān)鍵節(jié)點在圖中以黑色加重圓圈標出，容易看出三個端點度為 1，中心點度為 3。通過本方法得到的關(guān)鍵節(jié)點對應(yīng)人體的關(guān)節(jié)節(jié)點。

圖5 關(guān)鍵節(jié)點添加

3.2 Reeb圖的分割

根據(jù)3.1節(jié)的方法在Reeb圖上建立關(guān)鍵節(jié)點后，然后對Reeb圖進行分割。建立一個關(guān)鍵節(jié)點隊列queue，用于存貯度不為 1的關(guān)鍵節(jié)點。然后按下面流程對 Reeb圖進行分割：

①選擇Reeb圖中一個度為1的關(guān)鍵節(jié)點，從該節(jié)點出發(fā)，沿著弧遍歷，直到遇到另一關(guān)鍵節(jié)點，標記該段，將遇到的關(guān)鍵節(jié)點加入隊列queue中，標記該方向。

②從隊列queue中選擇一個關(guān)鍵節(jié)點，選定一個未走的方向遍歷，到下一個關(guān)鍵節(jié)點，進行標記。如果新遇到的關(guān)鍵節(jié)點度不為1，若其不在隊列queue中，把該節(jié)點加入隊列 queue，標記該方向，若已在隊列 queue中，僅標記該方向。

③判定queue中節(jié)點，將所有方向都走的節(jié)點移出隊列。

④判定隊列queue中是否為空，如果沒空繼續(xù)步驟②、步驟③，空則結(jié)束，從而完成了對Reeb圖的分割。

3.3 模型的3維肢體分割

按3.2節(jié)完成對Reeb圖的分割后，下步就對模型進行3維肢體分割，首先建立重構(gòu)網(wǎng)格頂點與 Reeb圖上節(jié)點的映射關(guān)系，其建立方法如下進行：對于人體模型上的一個頂點vi，i = 1, 2, 3,…, N，N為人體模型上的頂點總數(shù)，通過式(1)、式(2)：

建立該頂點與 Reeb圖上節(jié)點的映射。式(1)中 min{}代表取最小值，dis(vi, nj)代表歐式空間距離。式(2)限制y坐標差距，HEIGHT_TH是個閾值，因為 Reeb圖是由一系列處于同于水平線上的點集合成一個點，因而求對應(yīng)關(guān)系時，還應(yīng)受 y坐標的影響，并不是由式(1)得到的全局最小值。

完成模型頂點與Reeb圖上節(jié)點的這種多對1的映射后，3.2節(jié)中已經(jīng)對Reeb圖進行了分割，并且對不同分割部位進行了標記，然后反映射，將模型的各頂點進行相應(yīng)的標記，從而完成對模型的3維肢體分割。

4 實驗結(jié)果

文中算法通過C++語言實現(xiàn)，采用OpenGl進行繪圖，在Visual Studio 2005中編譯通過。實驗結(jié)果如圖6所示。

該實驗中原始數(shù)據(jù)為重構(gòu)好的三維人體網(wǎng)格數(shù)據(jù)，將人體肢體分割成頭部、胸部和四肢六部分，實驗結(jié)果如圖6所示，圖6(a)為試驗中采用的三維人體模型；圖6(b)為在該人體模型上提取的Reeb骨架圖；圖6(c)是Reeb圖的分割效果圖；圖 6(d)則是反映射到人體模型后，最終實現(xiàn)的肢體分割正面視圖，而圖 6(e)則為人體模型肢體分割后的背面視圖。

圖6 人體模型的三維肢體分割實驗效果

5 結(jié)語

這里采用的基于Reeb圖的三維肢體分割算法，不需要人機交互，沒有半監(jiān)督，沒有進行人為的選擇。實驗證明文中采用的算法，能夠較好的對重構(gòu)人體模型進行三維肢體分解。但文中采用的方法也有不足之處，計算人體模型與Reeb圖的對應(yīng)關(guān)系時，有時不能正確建立對應(yīng)關(guān)系，這會對后面的肢體分割造成誤差，需要進一步的研究，從而建立更好的對應(yīng)關(guān)系。三維模型的肢體分割能較好的應(yīng)用于計算機動畫和行為識別等，這也是文中的進一步研究方向。

[1] 陳保林. GSM手機在移動網(wǎng)絡(luò)中小區(qū)重選行為分析[J]. 通信技術(shù),2010,43(07):171-175.

[2] 徐海琛. TETRA數(shù)字集群網(wǎng)安全保障體系[J]. 通信技術(shù),2010,43(07):106-111.

[3] PARK Sangho, AGGARWAL J K. Segmentation and Tracking of Interacting Human Body Parts Under Occlusion and Shadowing[C].USA: IEEE Computer Society, 2002: 105-111.

[4] CHEUNG K, KANADE T, BOUGUET J Y, et al. A Real Time System for Robust 3D Voxel Reconstruction of Human Motions[C].USA:IEEE,2000: 714-720.

[5] WSIEH J W, CHUANG C H, CHEN S Y, et al. Segmentation of Human Body Parts Using Deformable Triangulation[C].USA:IEEE, 2006:355-358.

[6] 曹丹華, 湯金寬, 吳裕斌. 基于最小負曲率點搜索的快速人體肢體提取算法[J]. 華中科技大學(xué)學(xué)報:自然科學(xué)版, 2007, 35 (05) :16-18.

[7] 谷軍霞, 丁曉青, 王生進. 基于半監(jiān)督聚類的3維肢體分割算法[J].中國圖象圖形學(xué)報, 2008,13(03):558-563.

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