用戶約束下的三維動畫模型序列一致性分割

潘　翔，童偉淮，許洪濤，汪志星

(1.浙江工業大學 計算機科學與技術學院，浙江 杭州 310023；2.鄭州市人力資源與社會保障局 數據管理中心，河南 鄭州 450006)

?

用戶約束下的三維動畫模型序列一致性分割

潘翔1，童偉淮1，許洪濤2，汪志星1

(1.浙江工業大學 計算機科學與技術學院，浙江 杭州 310023；2.鄭州市人力資源與社會保障局 數據管理中心，河南 鄭州 450006)

摘要：針對三維動畫模型分割不一致問題，提出基于三維數據對齊技術的三維動畫模型交互式分割算法，得到層次結構一致的分割結果.算法首先對首幀進行交互標記；然后通過主向量分析完成三維模型不同幀之間的對齊，自動把用戶標記映射到其他模型；最后以方向夾角為基礎，設計圖割算法，根據模型關節所具有的曲率特征進行邊界優化，得到滿意的分割結果.實驗結果表明，算法針對人造動畫模型序列和多視圖三維重建動畫序列都能夠得到一致性分割結果，驗證了算法的有效性.最后和已有典型分割方法進行比較分析，可以發現算法能夠有效地提高分割質量.

關鍵詞：三維動畫模型；交互式分割；三維模型對齊；圖割

在計算機視覺和計算機圖形學領域，分割技術得到了廣泛的運用，例如物體識別[1]、三維重建[2]、網格參數化[3]、三維模型檢索[4].因此，三維模型分割已經引起了越來越多研究人員的興趣.

近年來，研究人員針對分割問題展開了大量的研究，使用了一系列特征，如分水嶺[5]、聚類[6]、形狀直徑函數(SDF)[7]和熱核信號(HKS)[8].協同分割結合了多個特征對模型進行分割[9-10].但這類純粹按照幾何的劃分方式，并不能實時滿足用戶需求.因而，研究人員又提出了點交互[11]和草圖交互[12-13]分割策略，通過反饋來提高分割效果[14].然而很少有學者關注模型序列分割，動畫模型序列通常具有大量姿態各異的幀，通過幾何特性或交互式分割都只針對單模型，不能將已有的前驅幀分割知識映射至后續幀，從而造成分割結果不一致.有學者試圖通過監督學習的方法，但這些方法分割結果固定，用戶無法自定義修改，有些訓練時間長，用戶交互性差[1].針對上述問題，提出了面向三維動畫模型序列的一種交互式方法.用戶只需在首幀上指定一些簡單的交互標記就可以得到整個序列一致的分割結果.整個算法采用從粗到精的分割策略.首先，算法通過模型對齊技術得到外部特征點，并得到粗分割結果.然后，采用圖割技術對粗分割進行優化，得到光滑的分割邊界.在實驗中，通過不同的三維動畫模型序列對算法進行驗證發現，對于不同的模型序列，算法都能夠得到一致性分割結果，顯著提高分割質量.

1算法概述

算法是通過用戶交互控制三維動畫模型序列分割結果.通常動畫模型由一個剛性主體部分和一些外在子部分組成.因此，分割任務主要是提取這些子部分.整個算法流程如圖1所示.首先，使用鼠標點擊作為交互，用戶將會在第一個網格的切割邊界附近放置一些標志.然后，算法可以根據網格中的這些標志進行分割輸出.注意各部分可以由兩種標志定義：外在點和連接點.外點在遠離中央的那些部分，連接點位于兩部分連接處.整個算法可以分三個步驟執行；首先，通過多維尺度變換實現模型對齊；其次，根據對齊結果檢測得到模型的特征點；最后，使用一個兩階段策略得到分割結果.第一階段是利用外部點和長度進行粗分割.第二階段是通過圖進行優化分割.

圖1　算法流程圖Fig.1　Flowchart of proposed algorithm

2算法細節

討論如何具體實現上述算法流程.為了簡化描述，給出了一些常見的分割定義.為了不失一般性，假設三維形狀采用三角網格表示.其他的三維形狀表示，如NURBS曲面，元球，細分曲面和體積，可以很容易地轉換成三角形網格.對于一個三維網格，它的頂點集合和面集合分別為V和F，頂點數量分別為Nv和Nf.對于任何兩個頂點vi和vj，其測地距離為gd(vi,vj).類似的，兩個面之間的測地距離為gd(fi,fj).分割任務是根據用戶交互定義，將網格序列分割成相同結構的子部分S1,…,Si,…Sj,…，SK(K為子部分數量).這里每個部分包含一組連接的面.對于每一個部分Sj，它有一個長度Lj.長度是從外點到連接點的測地距離.所有子部分滿足以下條件：

(1)

2.1MDS和局部特征相結合的外部點提取

對于其他未被標記的網格，注意到兩個三維網格在運動過程中具有不同的姿勢，而外部點保持穩定.采用對齊算法提取外部點.首先，使用MDS將兩個網格轉化為規范的姿勢[15].在這里，可以通過頂點之間的測地距離定義MDS變換所需的矩陣.因此，目標函數可以定義為

S(V)=min∑i

(2)

式中di，j為任意兩個頂點之間的歐氏距離.上述函數是用歐氏距離來逼近測地距離.圖2給出了兩個不同姿態的馬模型經過MDS變換的結果.可以發現兩個馬模型的姿態已經變得一致.

圖2　不同姿態通過MDS變換得到的結果Fig.2　The MDS results in different pose models

通過MDS變換后，可以使用主向量分析(PCA)對齊兩個網格.主向量分析構建一個旋轉不變的協方差矩陣.但是，PCA因為二義性會導致錯誤對齊.例如，PCA可能把一匹馬的尾巴對齊到其它馬的頭.這種情況下，可以通過兩個點集的最小歐氏距離來解決.PCA可以在3D空間輸出27種可能的對齊方向.因此，可以計算兩個網格對齊后的歐氏距離.最后，選擇最小距離方向作為最好的對齊結果.兩個點集的歐氏距離計算式為

(3)

式中VA和VB分別為兩個網格變化后的點集.通過上述目標函數，可以在目標網中為源網格的每個頂點找到和它最接近的點.通過最優對齊，在未標記網格上找到相應的外點.這里采用fi,e代表Si的外部點.考慮到對齊的準確性，算法會執行一個后處理.后處理的思想是將檢測到的標志盡可能遠地遠離中心點.中央點計算式為

(4)

在得到中心點以后，采用下式完成外點位置的更新式為

fi,e={fq|minfw∈E∪fcgd(fq,fw),

maxfq∈Fgd(fq,fc)>gd(fi,e,fc)}

(5)

式中E為外部點集.上述方程是最大化其他指定外部點到中心點的最小距離.圖3顯示了一些處理前后結果.在后處理之前，一些通過PCA得到的外點在中間區域.通過優化后，外點的精度大大提高.

圖3　優化前后的外點位置對比Fig.3　Comparison of unrefined and refined positions of external points

2.2粗分割

在檢測到外部點基礎上，粗分割可以結合子部分長度得到.注意到這些不同姿勢的網格有類似的測地距離.因此，對于三維序列的每個網格，其子部分的長度幾乎保持不變.在這種方式中，可以得到一個子部分：

Si={fj|gd(fi,e,fj)

(6)

式中Li為通過標注網格得到的長度.類似的，可以得到其他子部分.

2.3邊界優化

粗分割結果可以得到三維網格結構，然而分割邊界質量較差.因此，我們需要優化來消除鋸齒邊.通常一個好的分割應盡可能地通過凹形區域.凹區域可以用曲率特征來判斷.在這里，采用圖割來優化邊界.

圖割通過最大流算法實現[16]，兩個相鄰的部分之間執行圖割需要三個主要步驟：首先，將切割邊界附件的面片被指定為模糊區域，同時將該區域構建為圖結構，算法的實質就是是重新分配這些面片，最終得到一個光滑邊界；其次，計算圖中邊得權重，筆者根據兩個相鄰面片的夾角定義計算了邊的權重公式，最后，添加虛擬的源點和匯點及邊的代價權重得到最終的路徑，該路徑映射回模型表面即為分割邊界.

2.3.1構建模糊區域

模糊區域包含的面與外點的測地距離小于預定義的閾值α，其面的集合為

(7)

式中α設定為0.2.

2.3.2定義圖的邊代價

用二面片夾角定義邊代價可以使分割邊界具有高度凹性，εij為面fi和fj的二面角，二面角的共同邊代價定義為

(8)

式中：avg(cost(ε))為平均角距離;cost(εij)為歸一化因子，定義為

(9)

式中:當夾角為凹時，因子δ等于1，否則等于0.3.

2.3.3求解路徑

通過兩個虛擬節點，根據外部點和邊成本，該算法能沿著凹邊對圖進行分解.因此，可以從模糊區域求解得到相對光滑的邊界.圖4顯示了優化前后的圖割.優化結果可以準確地找到更為光滑的邊界.

圖4　優化前后對比Fig.4　Comparison of unrefined and refined segmentation

3實驗分析

實驗環境為英特爾?核心TM雙T9300，2.5 GHz和2 G內存，操作系統為Windows XP.在實驗中，通過運行不同類型的三維數據算法來驗證算法的通用性.實驗數據主要包括兩部分，一部分來自于TOSCA數據庫的人造模型，另外一部分來自于真實重構的運動數據.實驗首先對算法的穩定性進行分析，然后把算法和已有典型分割方法進行比較分析，進一步論證算法的有效性.

3.1穩定性分析

首先，在TOSCA數據庫的一些人造模型上驗證了方法的有效性.該數據庫包含了不同序列，包括馬、半人半馬及貓等.每個序列由一些含不同姿態的三維網格組成.對每個序列，我們首先在第一網格上定義交互標記.然后，去執行算法來得到序列中任意一個模型的分割.圖5顯示了不同序列的結果.對于貓，只用了12個標記得到了了分割.然而，對半人馬和馬使用了更多的標記去得到層次分割.

圖5　不同三維動畫序列的分割結果Fig.5　Segmentation results of different model sequences

為了進一步驗證算法的通用性，同時對一個真實重建數據進行實驗.被測試的序列是一個跳舞動作，由多臺攝像機立體構成得到[17].如圖5(d)所示，這個算法能夠得到非常一致的分割結果.因此，算法可以被用于分析不同部位的運動.

3.2比較分析

為了進一步說明算法的有效性，和已有典型分割算法進行比較分析.在已有分割算法中，SDF是一種非常有效的層次分割方法.能夠得到較為一致的分割結果.但SDF算法由于受姿態變化等影響，分割結果仍舊具有明顯的不一致性.而且只根據形狀特征進行分割聚類，也會導致分割結果無法滿足用戶要求.而筆者提出的算法引入了三維數據對齊和用戶少量交互完成用戶交互標記的傳遞，從而能夠快速地完成三維動畫模型一致性分割.圖6左右分別給出了SDF分割結果和筆者算法得到的結果.可以發現：SDF分割結果難以有效地反映出人體層次結構，而且不一致.和SDF算法比較，筆者算法由于考慮了用戶交互，從而使分割結果很好地逼近用戶意圖，保證不同幀分割結果的一致性.而對用戶來說，額外的操作只需要在一個幀上定義標記，用戶應該可以接受.

圖6　一致性結果比較分析Fig.6　Comparison of consistent segmentation results

4結論

針對三維動畫序列提出通過用少量戶交互來解決分割一致性問題，通過三維數據對齊完成用戶標記點的映射.用戶只需對第一幀進行交互就可以完成對整個序列的分割，因此用戶可以接受這種交互.通過實驗分析表明：算法能夠適用于不同類型的動畫網格序列，而且明顯要優于已有分割方法.在后續研究中，有很多可以改進的地方.比如，Kaplansky等提出了更為有效的邊界優化算法[18]，可用于邊界優化.此外，筆者采用MDS這樣的全局對齊得到外點，無法適用于具有遮擋關系的局部數據，模型匹配技術得到了廣泛的研究[19]，因此可以通過局部點的特征匹配來進一步提高分割準確率.

參考文獻：

[1]KALOGERAKIS E, HERTZMANN A, SINGH K. Learning 3D mesh segmentation and labeling[J]. ACM Transactions on Graphics,2010,29(4)：102.

[2]鄭河榮,劉家好,何玲娜.腦血管計算機模型的建立與有限元分析[J].浙江工業大學學報,2014,42(3)：253-256.

[3]KRAEVOY V, SHEFFER A. Cross-parameterization and compatible remeshing of 3D models[J]. ACM Transactions on Graphics,2004,23(3)：861-869.

[4]潘翔,陳敖,周春燕,等.基于視圖特征點分布的三維模型檢索算法[J].浙江工業大學學報,2013,41(6)：641-645.

[5]MANGAN A P, WHITAKER R T. Partitioning 3D surface meshes using watershed segmentation[J]. Visualization and Computer Graphics, IEEE Transactions on,1999,5(4)：308-321.

[6]TAL A, KATZ S. Hierarchical mesh decomposition using fuzzy clustering and cuts[J]. ACM Transactions on Graphics,2003,22(3)：954-961.

[7]SHAPIRA L, SHALOM S, SHAMIR A, et al. Contextual part analogies in 3D objects[J]. International Journal of Computer Vision,2010,89(3)：309-326.

[8]FANG Yi, SUN Mengtian, KIM M, et al. Heat-mapping：a robust approach toward perceptually consistent mesh segmentation[C]//2013 IEEE Conference on Computer Vision and Pattern Recognition. Colorado Springs：IEEE Computer Society,2011：2145-2152.

[9]SIDI O, KAICK O, KLEIMAN Y, et al. Unsupervised co-segmentation of a set of shapes via descriptor-space spectral clustering[J]. ACM Transactions on Graphics,2011,30(6)：126.

[10]HU Ruizhen, FAN Lubin, LIU Ligang. Co-segmentation of 3D shapes via subspace clustering[J]. Computer Graphics Forum,2012,31(5):1703-1713.

[11]ZHENG Youyi, TAI C L, AU O K C. Dot scissor：a single-click interface for mesh segmentation[J]. IEEE Transactions on Visualization and Computer Graphics,2012,18(8)：1304-1312.

[12]MENG Min, FAN Lubin, LIU Ligang. A comparative evaluation of foreground/background sketch-based mesh segmentation algorithms[J]. Computers & Graphics,2011,35(3)：650-660.

[13]ZHENG Youyi, TAI C L. Mesh decomposition with cross-boundary brushes[J]. Computer Graphics Forum,2010,29(2)：527-535.

[14]FAN Lubin, LIC L, LIU Kun. Paint mesh cutting[J]. Computer Graphics Forum,2011,30(2)：603-612.

[15]SILVA V D, TENENBAUM J B. Sparse multidimensional scaling using landmark points[R]. California：Stanford University,2004.

[16]AGATHOS A, PRATIKAKIS I, Perantonis S, et al. Protrusion-oriented 3D mesh segmentation[J]. The Visual Computer,2010,26(1):63-81.

[17]VLASIC D, BARAN I, MATUSIK W, et al. Articulated mesh animation from multi-view silhouettes[J]. ACM Transactions on Graphics,2008,27(3)：97.

[18]KAPLANSKY L, TAL A. Mesh segmentation refinement[J]. Computer Graphics Forum,2009,28(7)：1995-2003.

[19]潘翔,章國棟,周春燕,等.三維可變形物體的三點匹配策略[J].浙江工業大學學報,2013,41(5)：539-544.

(責任編輯：陳石平)

User-constrained consistent segmentation of 3D animated meshes

PAN Xiang1, TONG Weihuai1, XU Hongtao2, WAN Zhixing1

(1.College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China;

2.Data Management Centre, Human Resouces and Social Security of Zhengzhou, Zhengzhou 450006, China)

Abstract:Existing approaches will cause inconsistent segmentations for 3D animated meshes. To address this issue, we propose an algorithm of interactive segmenting 3D animated meshes based on 3D data correspondence and it can obtain highly consistent segmentations with user’s interactions. In this algorithm, the first frame should be annotated interactively. Then the principal component analysis is used to align different frames of animation. Then user’s mark can be automatically mapped to other models. Finally, based on directional angle, the cut algorithm is designed and the boundary is optimized according to the curvature of the joint mode until the segmenting results are satisfied. Experimental results show that the algorithm can effectively segment artificial 3D animation and multi-view reconstruction animation. Furthermore, the proposed algorithm can effectively improve the segmenting quality better than the existing algorithms.

Keywords:3D animated meshes; interactive segmentation; graph cut; 3D mesh correspondence

文章編號：1006-4303(2015)04-0420-05

中圖分類號：TP391

文獻標志碼：A

作者簡介：潘翔(1977—)，浙江文成人，教授，博士，研究方向為計算機圖形學，E-mail：panx@zjut.edu.cn.

基金項目：國家自然科學基金資助項目(6127230)；浙江省文物局基金資助項目(2014014)

收稿日期：2014-12-08