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

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

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

0 引言

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

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

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

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

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

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

1946年數(shù)學(xué)家George Reeb提出了一種描述拓?fù)浣Y(jié)構(gòu)的方式[8]，這就是 Reeb圖。假設(shè)一個(gè)流形 M，在其上定義一個(gè)標(biāo)量函數(shù)f，M上的點(diǎn)根據(jù)函數(shù)f得到一個(gè)值，那么處在同一水平線且在同一個(gè)連通域的點(diǎn)在Reeb圖上對(duì)應(yīng)同一個(gè)點(diǎn)。圖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。有兩個(gè)點(diǎn)x,y∈M，若f-1(t) =x =y，即f(x) =f(y)=t，且x和y屬于同一連通域，那么在圖形R中，點(diǎn)x和y映射同一個(gè)點(diǎn)，那么圖形R是流形網(wǎng)格M在函數(shù)f上生成的Reeb圖。

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

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

2 Reeb圖的計(jì)算

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

圖3 Reeb圖計(jì)算示意

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

圖4 濾波示意圖

3 人體模型的肢體分割

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

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

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

3.2 Reeb圖的分割

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

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

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

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

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

3.3 模型的3維肢體分割

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

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

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

4 實(shí)驗(yàn)結(jié)果

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

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

圖6 人體模型的三維肢體分割實(shí)驗(yàn)效果

5 結(jié)語

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

[1] 陳保林. GSM手機(jī)在移動(dòng)網(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] 曹丹華, 湯金寬, 吳裕斌. 基于最小負(fù)曲率點(diǎn)搜索的快速人體肢體提取算法[J]. 華中科技大學(xué)學(xué)報(bào):自然科學(xué)版, 2007, 35 (05) :16-18.

[7] 谷軍霞, 丁曉青, 王生進(jìn). 基于半監(jiān)督聚類的3維肢體分割算法[J].中國圖象圖形學(xué)報(bào), 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.