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

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

?

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

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

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

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

關(guān)鍵詞：三維動畫模型；交互式分割；三維模型對齊；圖割

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

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

1算法概述

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

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

2算法細節(jié)

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

(1)

2.1MDS和局部特征相結(jié)合的外部點提取

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

S(V)=min∑i

(2)

式中di，j為任意兩個頂點之間的歐氏距離.上述函數(shù)是用歐氏距離來逼近測地距離.圖2給出了兩個不同姿態(tài)的馬模型經(jīng)過MDS變換的結(jié)果.可以發(fā)現(xiàn)兩個馬模型的姿態(tài)已經(jīng)變得一致.

圖2　不同姿態(tài)通過MDS變換得到的結(jié)果Fig.2　The MDS results in different pose models

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

(3)

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

(4)

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

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

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

(5)

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

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

2.2粗分割

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

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

(6)

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

2.3邊界優(yōu)化

粗分割結(jié)果可以得到三維網(wǎng)格結(jié)構(gòu)，然而分割邊界質(zhì)量較差.因此，我們需要優(yōu)化來消除鋸齒邊.通常一個好的分割應(yīng)盡可能地通過凹形區(qū)域.凹區(qū)域可以用曲率特征來判斷.在這里，采用圖割來優(yōu)化邊界.

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

2.3.1構(gòu)建模糊區(qū)域

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

(7)

式中α設(shè)定為0.2.

2.3.2定義圖的邊代價

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

(8)

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

(9)

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

2.3.3求解路徑

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

圖4　優(yōu)化前后對比Fig.4　Comparison of unrefined and refined segmentation

3實驗分析

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

3.1穩(wěn)定性分析

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

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

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

3.2比較分析

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

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

4結(jié)論

針對三維動畫序列提出通過用少量戶交互來解決分割一致性問題，通過三維數(shù)據(jù)對齊完成用戶標記點的映射.用戶只需對第一幀進行交互就可以完成對整個序列的分割，因此用戶可以接受這種交互.通過實驗分析表明：算法能夠適用于不同類型的動畫網(wǎng)格序列，而且明顯要優(yōu)于已有分割方法.在后續(xù)研究中，有很多可以改進的地方.比如，Kaplansky等提出了更為有效的邊界優(yōu)化算法[18]，可用于邊界優(yōu)化.此外，筆者采用MDS這樣的全局對齊得到外點，無法適用于具有遮擋關(guān)系的局部數(shù)據(jù)，模型匹配技術(shù)得到了廣泛的研究[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].浙江工業(yè)大學(xué)學(xué)報,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].浙江工業(yè)大學(xué)學(xué)報,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].浙江工業(yè)大學(xué)學(xué)報,2013,41(5)：539-544.

(責(zé)任編輯：陳石平)

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—)，浙江文成人，教授，博士，研究方向為計算機圖形學(xué)，E-mail：panx@zjut.edu.cn.

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

收稿日期：2014-12-08