一種基于模型分割的三維人體骨架提取方法

甘凌云　侯　進,2*

1(西南交通大學信息科學與技術學院　四川 成都 611756)2(南京大學計算機軟件新技術國家重點實驗室　江蘇 南京 210093)

?

一種基于模型分割的三維人體骨架提取方法

甘凌云1侯進1,2*

1(西南交通大學信息科學與技術學院四川 成都 611756)2(南京大學計算機軟件新技術國家重點實驗室江蘇 南京 210093)

針對當前三維骨架提取方法復雜度較高、提取結果不夠準確，以及專門針對人體模型的方法較少等問題，提出一種基于模型分割的三維人體骨架提取方法。首先，根據模型頂點與末端特征點的最小測地距離將模型分割；然后由歸一化的測地距離函數確定模型各頂點所屬拓撲層次；接著在模型分割的基礎上依據拓撲層次提取出原始骨架點；最后經過微調，將各骨架點按照拓撲關系連接得到較為精確的人體骨架。實驗結果表明，該方法有效降低了骨架提取算法的復雜度，且對不同姿勢的人體模型均可獲得較為準確的提取結果。

骨架提取模型分割測地距離拓撲層次

0　引　言

虛擬人作為人類在虛擬世界中的化身[1]，自然成為模擬人類行為的最好工具。而當前眾多領域例如行為識別[2]、影視制作、游戲及動畫的大量研究都是基于骨架進行的。骨架作為三維對象幾何和拓撲結構的簡化表示[3]，不僅保留了模型的原始形態特征，而且減少了冗余信息，壓縮了存儲空間，經常被用在形狀分析[4]、曲面重建[5]、骨骼動畫[6]、模型檢索[7]等研究當中。這一切使得對虛擬人和骨架的相關研究相互依賴、共同發展，所以如何從三維人體模型中提取出有效的骨架信息，成為近年來專家學者們潛心研究的重要內容。

一方面，一些三維掃描設備可以直接提取出主要關節的大概位置[8]，但得到的結果往往無法達到準確和全面的效果。另一方面，研究人員針對骨架所具有的特點，也紛紛在不同理論的基礎上提出了相應的骨架提取方法。例如，Au等[3]人通過全局位置約束使得模型收縮，直到得到一副零體積的骨骼線。徐超等[9]采用基于距離變換的方法，通過局部比較快速確定候選骨架點，再經過一定的規則約束生長出骨架。Jiang等[10]人使用基于Voronoi圖計算的方法使骨架圖收縮，并通過表面聚類確保收縮過程中的均勻性。但是，這些方法多是從通用的模型中提取出骨架信息，所以有些并不適用于人體結構，而且容易受到模型姿態等因素的影響。關華等[11]基于三角簡化的方法得到人體模型的Reeb圖，再通過計算Reeb圖上各節點的曲率來添加關節點，最終實現模型的骨架提取。吳偉和等人[12]以特征點為起點計算模型等測地線的中心線，再根據人體測量學知識確定關節點的近似位置。他們雖然針對人體模型提取出了較為準確的骨架結構，但是計算過程較為復雜，在實現上有一定的難度。劉輝[13]采用測地距離計算簡化模型的特征點，再根據特征點劃分頂點分支并刪除多余骨架點生成最終骨架。該方法有效降低了算法復雜度，但存在提取骨架不夠精細的問題。

鑒于基于Reeb圖的方法對于模型的旋轉、平移具有很強的魯棒性，且有較強的抗噪性能，相對于其他方法也更加簡單易行，非常適用于像虛擬人這樣對稱且具有規則拓撲結構的對象。本文在Reeb圖的啟發之下，以模型分割為基礎，通過綜合分析人體模型的特征點域以及拓撲層次結構來確定骨架點，從而提取出滿足人體結構特點的骨架。實驗結果與對比表明，本文方法不僅簡單易行，而且對于不同姿勢的人體模型都能得到較為精確的提取效果。

1　算法概述

圖1　算法過程示意圖

本文借鑒Reeb圖的思想，在模型分割的基礎上對三維虛擬人三角網格模型進行骨架提取。在模型分割階段，利用各頂點到人體末端特征點的測地距離計算特征點域。然后利用歸一化的測地距離函數計算出每一頂點的分類函數值，為下一步提取骨架點提供重要的拓撲層次信息。接下來綜合分析以上兩步得到的結果，通過算法獲得原始骨架點。最后對個別骨架點進行調整，并根據模型的拓撲結構連接相應節點完成最終的提取工作。整個方法計算復雜度低、提取結果較為精準，適用于不同姿勢的人體模型，具有很好的可推廣性。其具體算法過程如圖1所示。

2　模型分割

2.1特征點的提取

圖2　特征點所在最小區域示意圖

一般將三維網格模型中局部突出的點作為特征點，它反映了整個模型的空間結構以及分支情況。本文分別將目標特征點所在的最小區域單獨命名，在將模型整體導出后，以頂點索引特征為判斷依據搜索出目標特征點。

假如目標特征點所在的最小區域是由圖2的形式構成，四邊形BCDE(當然也可能為其他多邊形)為模型內部不封閉的部分。如果頂點A、B、C、D、E的索引號依次為0、1、2、3、4，那么△ABC、△ACD、△ADE和△ABE的構成索引對就如表1所示。

表1　三角形及其索引對

由表1可以明顯看出，具有局部突出特征的點A在構成每個索引對中均作出貢獻。所以只要遍歷目標特征點所在最小區域的全部三角形，找出在每個三角形中均有出現的索引，即可確定該索引所代表的頂點為目標特征點，其三維坐標等信息也就繼而得知了。本文以此方法分別提取出位于人體頭頂、左指尖、右指尖、左腳尖和右腳尖的5個頂點作為特征點參與后續計算。

2.2基于特征點的結構分割

2.2.1特征點域

本文模型滿足下式:

D={vn|f(vn)=g(vfp),n∈(0,N)}

(1)

其頂點集合稱為對應特征點的特征點域。其中，vn為模型的第n個頂點 ，vfp為某一特征點；f、g分別是以vn和vfp為變量的函數，N為模型的總頂點數。

根據以上定義可知，特征點域即為具有某種相同函數特征的頂點集合，處在相同域內的頂點與對應特征點之間存在某種特殊聯系。而正是由于特征點有著描述模型局部特征的功能，所以在以特征點為參照得到的頂點集合內部也將有著相類似的某種聯系。這樣以特征點為依據對模型進行劃分，將為后續的骨架提取提供重要的模型結構信息。

2.2.2特征點域的計算

鑒于特征點常位于極值部位，很容易使人聯想到將模型頂點與特征點間的距離作為分割依據。然而由于三維模型的空間特殊性，若直接使用歐式距離，很多時候并不能得到正確的分割結果，所以考慮采用各頂點到相應特征點的測地距離作為劃分標準。

測地距離是指沿表面兩點之間最短路徑的長度，通常可用迪科斯徹(Dijkstra)算法來近似計算。與歐式距離相比，測地距離兼顧了曲面上兩點之間的幾何連通性，因此可獲得更加合理的分割效果。

Dijkstra算法的主要思想如下：

(1) 選擇一個基準點b，令集合S={b}，T={模型剩余點}，T中頂點vi(xi,yi,zi)若可直達b(xb,yb,zb)，則距離g(vi)=dis(b,vi)，否則g(vi)=+∞；

(2) 判斷T是否為空，是則轉至步驟(4)，否則從T中選取一個與b有最小距離的頂點vj，并將此點加入S；

(3) 若T中頂點vk到b的距離大于途經vj再至b的距離，即：

g(vk)>g(vj)+dis(vj,vk)

(2)

則更新：

g(vk)=g(vj)+dis(vj,vk)

(3)

同時轉至步驟(2)；

(4) 此時所有頂點都包含在S內，它們與b之間的距離g(vi)即為所求最短路徑。

其中：

(4)

(5)

以各特征點為基準點，采用Dijkstra算法求得模型頂點與各特征點之間的最短路徑，將與各特征點有最小測地距離的頂點分別聚合，即可得到各特征點域。相同域的頂點與相應特征點在幾何表面都有著最為快捷的到達方式。這種到達方式將三維模型分割成與特征點數目相同的幾個部分，構成模型局部獨立的幾大分支，而準確的分支信息將成為確定骨架點的一大依據。

3　人體模型拓撲結構分析

3.1Reeb圖

Reeb圖是三維模型拓撲結構的一種重要描述方式，由定義在一個任意維度對象上的連續標量函數確定[14]，是數學家Georges Reeb為分析流形拓撲結構而首先提出，常被用于計算幾何、計算機圖形學等科研領域。

Reeb圖的定義：假設有一流形M，f是定義在M上一個連續而光滑的函數，R是M經由f生成，即f:M→R。對于xi,xj∈M，如果f(xi)=f(xj)，那么R是M在f的映射下生成的Reeb圖。

本文在這種思想之下，不同于一般基于Reeb圖的方法那樣對大量等值線提取中心連成曲線骨架線，而是由分類函數f對人體進行拓撲計算，再通過參數控制拓撲層次直接提取骨架點，從而減少了一定的計算量。

3.2分類函數的選取

高度函數、測地距離和調和函數等都常被用來作為f函數。由于測地距離沿網格表面計算兩點間的最短距離，所以在不同姿勢和體態下具有更大的優勢，十分有利于得到準確的分類結果。所以本文在這部分仍然沿用模型分割時特征點域內各頂點與相應特征點間的測地距離函數進行拓撲劃分。同時為便于計算統計，采用歸一化后的測地距離，如下所示：

(6)

其中，g(vi)為vi與對應特征點的測地距離，max{g(vj)}、min{g(vj)}分別為測地距離的最大值與最小值，N為模型頂點數。

3.3拓撲層次的分析

而對于K的取值，如果選擇最小值1，那么整個模型將屬于同一拓撲層次，此時就失去了表達人體拓撲信息的意義。隨著K取值的增大，相應的拓撲層次也將不斷增加，而過多的層次對于描述人體骨架結構也是沒有幫助的，反而會減慢計算速度。所以，是否合理地選擇K的取值，會在很大程度上決定最終實驗效果的好壞。

圖3從左到右、從上至下依次為K=2～7時一個男性人體模型的拓撲層次結構，分別使用不同的深度表示具有同一拓撲特征的頂點集合。由圖可見，隨著K值的不斷增大，拓撲層次也在不斷增多。當K=2時，人體模型各部分只是被粗略地區分，這樣提取出的骨架點將較為稀疏；而K=7時，各部分的劃分又過于細致，這時不僅會增加計算量，而且還可能出現由于劃分過細而提取出孤立點的情況。經反復試驗發現，當K=4時，人體各部分的層次劃分較為合理，提取出的骨架點位置也與真實人體關節較為接近，而此時計算復雜度也相對較低。

圖3　不同K值下的人體拓撲層次

4　人體模型骨架提取

4.1骨架點的求取

為得到能夠反映模型結構特點的骨架點，劉輝[13]使用改進的拓撲結構法遍歷所有網格頂點，以相鄰點與當前點的特征點域情況判斷當前點是否為分支點，進而將同一分支集合內的頂點聚合求得骨架點。改進的拓撲結構法適用于存在孔、洞的模型，避免了處于同一水平集而不同分支內的頂點聚合為同一骨架點的情況。但是由于此種方法只依據特征點域進行分支判斷，所以最終得到的骨架點只存在于模型分支處，不免顯得較為稀疏，可能無法將模型的結構特點作詳盡描述。另外，該方法得到的骨架還有可能出現環路，這時就不得不對骨架進行再次加工。而本文采用綜合分析模型分割結果及拓撲層次的方法，對每一分支內具有相同拓撲層次的頂點聚合，逐層求解的過程避免了環路的發生，得到的骨架點數量更利于反映模型的結構特點，對于人體模型來講具有更為豐富的描述意義。本文求取骨架點的具體算法步驟如下：

(1) 將不同水平集內的頂點按f值分K類存放；

(2) 遍歷其一水平集內的所有頂點，如已處理完畢則轉至(5)，否則將未處理頂點v入棧S；

(3) 取棧頂元素vt，遍歷其鄰點是否與vt在相同的水平集，是則返回(2)，否則繼續；

(4) 將vt添加到vt的骨架點數組，重新遍歷其鄰點，將與vt在同一水平集的鄰點入棧S，轉(3)至棧空；

(5) 對其余水平集重復(2)至(4)；

(6) 遍歷每一骨架點數組中頂點是否具有相同特征點控制域，是則結束，否則繼續；

(7) 將具有不同特征點控制域的骨架點數組分離為新的骨架點數組，至此得到基于模型分割的各部分骨架點數組。

最后，將每一骨架點數組中的頂點作坐標平均，得到所求三維模型的所有骨架點，如式(6)-式(8)所示，此時提取骨架點滿足骨架對于中心性的要求。

(7)

(8)

(9)

式中xvj、yvj、zvj為頂點vj的三維坐標，Ni為第i個骨架點數組中的頂點總數；xi、yi、zi為第i個骨架點的三維坐標，M為骨架點總數。

4.2個別骨架點的調整

圖4　肩、踝骨架點調整前后對比

實驗發現，本文方法對于人體模型肩關節和踝關節附近的骨架點提取效果有時并不十分理想。究其原因是由于肩、踝部的幾何結構不規則所致，所以還需對不夠精確的骨架點進行位置調整。本文以0.01為步長，將提取的原始骨架點沿需要調整的坐標軸方向移動，直至到達合適的位置。圖4即為這兩部分骨架點位置調整前后的對比示意圖。

5　實驗結果及討論

本文實驗是在Windows 7，Intel Core i5-3230M CPU，2.6 GHz，2.88 GB的環境下，利用OpenGL圖形庫，以Visual Studio 2010作為軟件開發平臺進行的。選取的人體模型共有3個，其中2個從Poser8中導出，分別為男性人體模型Nude Man P4 Lo和女性人體模型Nude Woman P4 Lo。另有一自建模型用于檢測骨架驅動效果，進而評價本文方法的實際應用價值。三者皆選頭頂和四肢肢端共計五個頂點為特征點。除人體模型之外，本文也對Poser8中的2個非生命體做了同樣實驗，各實驗模型數據如表2所示。

表2　實驗模型相關數據

圖5和圖6即為對Nude Man P4 Lo進行特征點提取和模型分割的結果。圖6采用不同深度標記模型具有同一分類特征的頂點集合，可以明顯看出整個模型被分為5個部分，正好對應于所選取的5個末端特征點。

圖5　特征點提取結果　圖6　模型分割結果

圖7是文獻[13]中改進拓撲結構法的骨架提取效果。從(a)-(c)的人體模型來看，一方面，提取的分支節點較為稀疏，造成骨架結構十分簡單；另一方面，對于雙手平舉的模型，雖然從正面看來可以取得形象的骨架效果，但是從俯視圖來看就暴露了骨架穿出皮膚的缺點。對于雙手下垂的模型來講，從正面就能看到其骨架并沒有位于模型之內。對于(d)和(e)的非人體模型也同樣或多或少地存在類似現象。

圖7　文獻[13]方法的骨架提取結果

本文方法由于是在模型分割的基礎上按照拓撲層次逐層求取骨架點，所以不會出現骨架在模型以外的情況，具體結果如圖8所示。從人體模型(a)-(c)可見，無論是在骨架點數量還是骨架形態上，本文方法所得結果更適合描述人體的結構特點，具有更為細致的提取效果。

圖8　本文方法的骨架提取結果

表3對文獻[13]與本文方法所提取的骨架點數量進行了比較。從表中亦可以看出，本文方法獲得的骨架點更多、更細致，所以在模型的細節描述上具有更大的優勢。

表3　骨架點提取數量對比

圖9是針對女性模型在不同姿勢下進行骨架提取，因為借鑒了Reeb圖的思想并充分考慮人體拓撲結構特點，所以本文方法同樣受人體姿勢變換的影響較小。實驗結果證明，本文方法不僅對于標準姿態的人體模型能夠提取出形象的骨架，還適用于不同姿勢的三維人體模型，且都能夠得到較為理想的結果。

圖9　女性模型不同姿勢的骨架提取結果

最后，為說明本文方法所得骨架可應用于骨骼動畫，采用頂點混合綁定的方法使得骨骼可以對虛擬人皮膚進行驅動，綁定權重由骨骼投影法作粗略估計。圖10為虛擬人從初始姿勢到邁步狀態的一個動作效果，可見當自建模型的骨架做出一定量運動之后，皮膚也會隨之發生變化。動畫效果充分說明本文提取骨架較為合理，能夠驅動虛擬人產生生動逼真的骨骼動畫，這部分也將是下一步研究的一個重點。

圖10　腿部蒙皮后的動作效果

6　結　語

本文提出一種基于模型分割的三維人體模型骨架提取方法，使得提取結果更加適用于虛擬人三維模型，并且對于不同姿勢都能得到較為精確的提取效果。首先通過計算每個頂點到特征點的最短路徑來劃分特征點域分割模型；然后根據各頂點的分類函數值將三維模型進行拓撲層次的構造；接著依據模型分割結果和拓撲結構提取出更為精確和豐富的骨架點；最后連接具有相鄰關系的節點得到最終提取結果。不同于一般先求取中心骨架線的方法，本文方法更加簡單易行，并且效果顯著。下一步的工作重點在于：(1)對于非人體模型而言，本文方法有可能會出現骨架點提取過于細致的問題，如圖8(e)所示，所以還需對非人形模型骨架點的精簡展開研究；(2)進一步深入探索，使本文骨架提取結果能夠應用于動作識別或者骨骼動畫等。

[1] Hou J, Xu F, Wu L， et al. Avatar-based human communication: a review[J].International Journal of Modelling and Simulation, 2012, 32(4): 273-278.

[2] Du J, Chen D F. 3D action recognition based on limb angle model[C]//2014 4th IEEE International Conference on Information Science and Technology. Shenzhen: IEEE, 2014:304-307.

[3] Au O K C, Tai C L, Chu H K, et al. Skeleton extraction by mesh contraction[J]. ACM Transactions. on Graphics, 2008, 27(3):441-449.

[4] Li Z, Qin S W, Yu Z Y, et al. Skeleton-based shape analysis of protein models[J].Journal of Molecular Graphics and Modelling, 2014, 53:72-81.

[5] Agarawal M, Kumar S, Bala A. Three dimensional object retrieval using a skeleton-based approach[C]//2014 IEEE International Advance Computing Conference. Gurgaon: IEEE, 2014:1147-1151.

[6] Pantuwong N, Sugimoto M. A novel framework for 3D computer animation systems for nonprofessional users using an automatic rigging algorithm[C]//2012 IEEE International Conference on Multimedia and Expo. Melbourne: IEEE, 2012: 896-901.

[7] 韓麗, 程遠. 融合骨架結構與幾何細節的三維模型檢索方法[J]. 計算機應用與軟件, 2013, 30(11):199-201,273.

[8] Wang S X, Qin S F, Guan C Y. Feature-based human model for digital apparel design[J]. IEEE Trans. on Automation Science and Engineering, 2014, 11(2):620-626.

[9] 徐超, 肖瀟, 駱燕,等.基于距離變換的新型骨架提取方法[J]. 儀器儀表學報, 2012, 33(12):2851-2856.

[10] Jiang W, Xu K, Cheng Z Q, et al. Curve skeleton extraction by coupled graph contraction and surface clustering[J]. Graphical Models, 2013, 75(3):137-148.

[11] 關華, 郭立, 李文,等. 一種人體三維Reeb圖計算方法[J]. 計算機工程, 2011,37(19):207-209.

[12] 吳偉和, 郝愛民, 趙永濤,等. 一種人體運動骨骼提取和動畫自動生成方法[J]. 計算機研究與發展, 2012, 49(7):1408-1419.

[13] 劉輝. 基于Reeb圖的三維網格模型骨架提取算法研究[D]. 濟南：山東師范大學, 2013.

[14] Hachani M, Zaid A O, Puech W. Segmentation of 3d dynamic meshes based on Reeb graph approach[C]//2014 Proceedings of the 22nd European Signal Processing Conference. Lisbon: IEEE, 2014: 2175-2179.

A METHOD FOR EXTRACTING 3D HUMAN BODY SKELETON BASED ON MODEL SEGMENTATION

Gan Lingyun1Hou Jin1,2*

1(School of Information Science and Technology, Southwest Jiaotong University, Chengdu 611756,Sichuan，China)2(StateKeyLaboratoryforNovelSoftwareTechnology,NanjingUniversity,Nanjing210093,Jiangsu,China)

Aiming at the problems that current 3D skeleton extraction methods are highly complicated, the extraction results are not accurate enough, and few of them are specifically for human body models, we proposed a model segmentation-based 3D human body skeletons extraction method. First, we divided the model into parts according to the minimum geodesic distances between feature points of its vertices and ends. Secondly, we determined the topological hierarchies of each vertex of the model by the normalised geodesic distance function. Thirdly, based on model segmentation we extracted the original skeleton points according to their topological hierarchies. Finally, after some fine tuning, we connected all the skeleton points according to their topological relations and obtained a quite accurate human skeleton. Experimental results showed that the method reduces the complexity of the skeleton extraction algorithms effectively and gets more accurate extraction result for human body models with different postures.

Skeleton extractionModel segmentationGeodesic distanceTopological hierarchy

2015-04-02。國家自然科學基金面上項目(61371165)；計算機軟件新技術國家重點實驗室開放課題基金項目(KFKT2013B22)；浙江大學CAD&CG國家重點驗室開放課題(A1416)。甘凌云，碩士，主研領域：虛擬現實。侯進，副教授。

TP391.9

A

10.3969/j.issn.1000-386x.2016.09.008