三維動(dòng)態(tài)模型的非剛性注冊(cè)技術(shù)綜述

摘要：三維動(dòng)態(tài)模型表示了物理世界中隨時(shí)問(wèn)演變的動(dòng)態(tài)對(duì)象，通過(guò)非剛性注冊(cè)匹配掃描獲取或手工合成的離散幀序列是生成三維動(dòng)態(tài)模型的核心問(wèn)題，是當(dāng)前學(xué)術(shù)界和產(chǎn)業(yè)界關(guān)注的新焦點(diǎn)。如何注冊(cè)三維動(dòng)態(tài)模型是極富挑戰(zhàn)性的工作，因?yàn)樗送耆豢椩谝黄鸬膶?duì)應(yīng)關(guān)系計(jì)算和非剛性變換等具有非線性性質(zhì)的問(wèn)題的求解，此外，輸入的幀數(shù)據(jù)通常不完美，因此解決非剛性注冊(cè)問(wèn)題的難度很大。文章概述了三維動(dòng)態(tài)模型非剛性注冊(cè)的原理、屬性和應(yīng)用，系統(tǒng)地介紹了這一領(lǐng)域的工作成果并進(jìn)行了分類(lèi)，分析了典型算法的優(yōu)缺點(diǎn)，最后展望了這一技術(shù)的發(fā)展前景。

關(guān)鍵詞：三維動(dòng)態(tài)模型；非剛性注冊(cè)；對(duì)應(yīng)關(guān)系計(jì)算；非剛性變換

0、引 言

三維動(dòng)態(tài)模型表示了隨時(shí)間演化的動(dòng)態(tài)對(duì)象，也被稱(chēng)為時(shí)空模型或時(shí)變模型一。該演化不但包括旋轉(zhuǎn)和平移等剛性運(yùn)動(dòng)，還包括了非剛性變形。基于動(dòng)態(tài)對(duì)象的內(nèi)在結(jié)構(gòu)，三維動(dòng)態(tài)模型可進(jìn)一步劃分為關(guān)節(jié)模型和可變形的(deformable)模型。關(guān)節(jié)模型由若干具有層次結(jié)構(gòu)的獨(dú)立部分組成，每個(gè)獨(dú)立部分具有相同(或非常相近)的剛性變換；在可變形的模型中，每個(gè)頂點(diǎn)進(jìn)行了局部的剛性變換。因此，對(duì)于整個(gè)三維動(dòng)態(tài)模型而言，涉及的變換為非剛性變換。該變換過(guò)程是自然的，不但不能有畸變，更要與真實(shí)的動(dòng)態(tài)對(duì)象的演化過(guò)程相近似。三維空間上的非剛性變換本質(zhì)上是一個(gè)復(fù)雜的非線性的問(wèn)題，因?yàn)樵撟儞Q中的基本要素一局部旋轉(zhuǎn)一求解本身就是非線性的。

1、內(nèi)涵與應(yīng)用前景

在計(jì)算機(jī)世界中，三維動(dòng)態(tài)模型離散化為連接關(guān)系保持不變的幀序列(見(jiàn)圖1(a)和(c))，各幀記錄著當(dāng)前時(shí)刻模型的拓?fù)浜徒Y(jié)構(gòu)信息。目前，建立三維動(dòng)態(tài)模型的數(shù)據(jù)主要有兩種技術(shù)途徑：一種是通過(guò)掃描設(shè)備獲取(圖1(a))；另一種是通過(guò)手工合成。掃描設(shè)備從實(shí)物出發(fā)，將不同時(shí)刻的采樣數(shù)據(jù)生成不斷變化的三維點(diǎn)云/網(wǎng)格序列。手工合成則借助于非剛性變形技術(shù)或關(guān)鍵幀技術(shù)手工編輯生成自然、逼真的動(dòng)態(tài)序列幀。

在計(jì)算機(jī)世界中表示和應(yīng)用三維動(dòng)態(tài)模型，必須注冊(cè)掃描獲取或手工合成的離散幀，完成各幀模型的精確匹配(圖(b))，即建立不同時(shí)刻不同坐標(biāo)系下各幀上頂點(diǎn)間的對(duì)應(yīng)關(guān)系(圖1(e))，并同時(shí)恢復(fù)出各頂點(diǎn)自然的非剛性變換過(guò)程(圖1(d))。因?yàn)榍蠼獾淖儞Q是非剛性的，故三維動(dòng)態(tài)模型的注冊(cè)稱(chēng)為非剛性注冊(cè)。它可以表述為：在一致對(duì)應(yīng)關(guān)系和自然的非剛性變換的約束下，對(duì)以對(duì)應(yīng)關(guān)系和非剛性變換為變量的性能指標(biāo)函數(shù)求取極值，完成幀序列的精確匹配。

非剛性注冊(cè)是重建三維動(dòng)態(tài)模型過(guò)程的根本，它也是對(duì)三維動(dòng)態(tài)模型作進(jìn)一步處理的基礎(chǔ)。非剛性注冊(cè)必須解決諸多完全交織在一起的、很難的且往往是病態(tài)的問(wèn)題。一方面，上述掃描獲取或手工合成的生成方法均不能顯式地提供各幀中頂點(diǎn)間的對(duì)應(yīng)關(guān)系。眾所周知，求解頂點(diǎn)之間的對(duì)應(yīng)關(guān)系是—個(gè)典型的NP問(wèn)題。這是因?yàn)椋词菇o定兩個(gè)相等的頂點(diǎn)集合，建立對(duì)應(yīng)關(guān)系的計(jì)算復(fù)雜度也是O(nI)(n為頂點(diǎn)數(shù)目)；但通常，相鄰幀的頂點(diǎn)數(shù)目往往是不同的。從而，非剛性注冊(cè)處理的是局部映射問(wèn)題。另一方面，正如前文所述，如何求解自然的非剛性變換也是個(gè)復(fù)雜的非線性問(wèn)題。

圖1中的左圖為具有噪聲和洞隙的開(kāi)放haoTorsO：(a)初始狀態(tài)，源和目標(biāo)幀模型，(b)注冊(cè)后的結(jié)果；右圖為封閉的dancer：(c)注冊(cè)前的狀態(tài)，(d)注冊(cè)過(guò)程中的非剛性變換過(guò)程，(e)對(duì)應(yīng)關(guān)系(采樣了221對(duì))。

各幀模型通常不是完美的，往往具有噪聲和缺失數(shù)據(jù)。這是因?yàn)椋趻呙柽^(guò)程中，由于遮擋問(wèn)題，每幀中都有部分的表面沒(méi)有采樣信息，產(chǎn)生空洞甚至間隙，導(dǎo)致了持久性的數(shù)據(jù)缺失；此外，當(dāng)前的掃描系統(tǒng)分辨率通常較低并且伴隨著固有的噪聲。而目前的掃描技術(shù)還沒(méi)有有效的硬件手段來(lái)解決這些問(wèn)題。因此，非剛性注冊(cè)還需要根據(jù)時(shí)空相關(guān)性推斷出各幀的缺失數(shù)據(jù)并降噪，提升三維動(dòng)態(tài)模型的質(zhì)量。

除了噪聲和洞隙外，非剛性注冊(cè)還必須充分考慮輸入數(shù)據(jù)的其他實(shí)際情況，如內(nèi)在結(jié)構(gòu)(關(guān)節(jié)模型或可變形的模型)、閉合程度、虧格(genus)變換、重疊區(qū)域范圍等等。在拓?fù)浞矫妫枰紤]模型閉合程度，即模型是開(kāi)放的外形部分(openpartial shapes，如圖1(a))，還是封閉的整體(closed whole，如圖1(c))；如果模型的虧格發(fā)生了改變，那么情況將更加復(fù)雜；重疊區(qū)域也影響了非剛性注冊(cè)的難度，輸入數(shù)據(jù)重疊區(qū)域越小，非剛性變換的尺度越大，注冊(cè)難度越高。事實(shí)上，處理輸入數(shù)據(jù)的范圍和能力體現(xiàn)了非剛性注冊(cè)算法的適應(yīng)性和魯棒性。

當(dāng)前，三維動(dòng)態(tài)模型的非剛性注冊(cè)問(wèn)題倍受學(xué)術(shù)界和產(chǎn)業(yè)界的關(guān)注。這是因?yàn)槿S動(dòng)態(tài)模型真實(shí)模擬動(dòng)態(tài)對(duì)象的方式使其成為一個(gè)強(qiáng)有力的工具。它的最直接的應(yīng)用領(lǐng)域是動(dòng)畫(huà)和影視制作方面。計(jì)算機(jī)上生成絢麗多彩的連續(xù)的虛擬真實(shí)畫(huà)面，給人們提供了一個(gè)充分展示個(gè)人想象力和藝術(shù)才能的新天地。在《貝奧武夫》、《變形金剛》和《阿凡達(dá)》等優(yōu)秀電影中，我們可以充分領(lǐng)略到三維動(dòng)態(tài)模型的魅力。三維動(dòng)態(tài)模型的非剛性注冊(cè)技術(shù)可極大地提高動(dòng)畫(huà)和影視制作水平和效率：在顯著降低成本的前提下，使制作過(guò)程更為直觀，效果更為生動(dòng)。此外，在人體工程學(xué)研究、模擬訓(xùn)練、生物力學(xué)、機(jī)器人學(xué)研究等使用和處理三維動(dòng)態(tài)模型的領(lǐng)域，非剛性注冊(cè)技術(shù)也是解決相關(guān)問(wèn)題的基礎(chǔ)。

2、國(guó)內(nèi)外研究概況、水平和發(fā)展趨勢(shì)

三維動(dòng)態(tài)模型的非剛性注冊(cè)的相關(guān)研究尚處于探索階段，是當(dāng)前國(guó)際前沿關(guān)注的新興問(wèn)題。從本質(zhì)上說(shuō)，非剛性注冊(cè)是一個(gè)典型的系統(tǒng)性問(wèn)題，需要綜合考慮多方面的因素：外形表示方法、非剛性變換和注冊(cè)策略。此外，某些先驗(yàn)知識(shí)往往被既有算法所借助以降低非剛性注冊(cè)的難度。以下從上述四個(gè)方面對(duì)國(guó)內(nèi)外研究概況、水平和發(fā)展趨勢(shì)進(jìn)行綜述。

2.1外形表示

外形表示是非剛性注冊(cè)面臨的首要選擇問(wèn)題。當(dāng)前，已有基于點(diǎn)云、參數(shù)、體和隱式表示的注冊(cè)算法。每種表示方法均具有自身的優(yōu)勢(shì)和不足。

由于掃描獲取設(shè)備直接生成了點(diǎn)云，手工合成的模型也具有頂點(diǎn)，故點(diǎn)云是最直接的選擇。但基于點(diǎn)云進(jìn)行非剛性注冊(cè)時(shí)，不同幀間對(duì)應(yīng)頂點(diǎn)位置即是采樣頂點(diǎn)，故注冊(cè)的結(jié)果與點(diǎn)云的采樣精度和分布情況有緊密的關(guān)系。不難想象，低分辨率、噪聲很大或點(diǎn)云分布不均勻等等因素均會(huì)導(dǎo)致不正確的結(jié)果。

由于參數(shù)表示有助于建立對(duì)應(yīng)關(guān)系，故也被應(yīng)用到非剛性注冊(cè)中。但是，參數(shù)表示很難表示拓?fù)浣Y(jié)構(gòu)比較復(fù)雜的形體，故應(yīng)用該類(lèi)算法處理的模型往往是容易參數(shù)化的開(kāi)放模型。

體表示方法。可以有效地處理近似封閉的完整模型，和點(diǎn)云和參數(shù)表示相比，體方法具有更高的穩(wěn)定性，受噪聲影響較小，并能夠一定程度上處理虧格變化。但它在處理殘缺模型時(shí)會(huì)遇到很大困難，因?yàn)楹茈y定義出殘缺部分的內(nèi)外劃分邊界位置；對(duì)于開(kāi)放模型，體方法更加不適合。

隱式方法對(duì)采樣精度和分布也不敏感，是非剛性注冊(cè)的另一種方式。隱式方法又可以進(jìn)一步劃分為無(wú)符號(hào)、帶符號(hào)和向量三種。帶符號(hào)和向量的隱式方式已經(jīng)在二維圖像注冊(cè)領(lǐng)域得到廣泛的應(yīng)用，但在三維非剛性注冊(cè)領(lǐng)域還很少見(jiàn)到這方面的算法。和體方法一樣，隱式方法在獲得穩(wěn)定性的同時(shí)，也喪失了一定的局部精確度。

2.2非剛性變換

目前，非剛性迭代最近點(diǎn)(iterative closed point，ICP)類(lèi)算法是求解非剛性注冊(cè)中使用最多的方法。該類(lèi)算法完全基于空間近似啟發(fā)式地確定頂點(diǎn)對(duì)應(yīng)關(guān)系，在每個(gè)迭代步上引入了非剛性變換，從而求得光滑的變換過(guò)程。但該算法的適應(yīng)范圍有局限，例如，對(duì)于非小尺度的變換，若不借助其他對(duì)應(yīng)關(guān)系，非剛性ICP算法往往收斂于局部最優(yōu)解，錯(cuò)誤地匹配模型。而且，該類(lèi)算法對(duì)模型的質(zhì)量要求較高，對(duì)噪聲和缺失數(shù)據(jù)也非常敏感，而且非常耗時(shí)。

此外，為了保持變換的自然性，研究人員采用盡可能剛性的變形模型表示并求解非剛性變換。在求解過(guò)程中，等距屬性是最基本的準(zhǔn)則。等距準(zhǔn)則不但要被變換過(guò)程所滿(mǎn)足，也是對(duì)輸入數(shù)據(jù)的基本要求。

對(duì)關(guān)節(jié)模型，研究人員手工或自動(dòng)地將模型進(jìn)行聚類(lèi)分解；對(duì)具有顯著骨架特性且近似閉合的模型，則可以訴諸于骨架來(lái)降低非剛性注冊(cè)的難度。

2.3注冊(cè)策略

注冊(cè)策略指的是求解非剛性變換和對(duì)應(yīng)關(guān)系的技術(shù)路線。基于對(duì)應(yīng)關(guān)系的獨(dú)立程度，可將既有的算法分為兩類(lèi)。一類(lèi)是首先在模型間建立對(duì)應(yīng)關(guān)系，而后再利用對(duì)應(yīng)關(guān)系求解非剛性變換。對(duì)應(yīng)關(guān)系可以為預(yù)先指定的標(biāo)記點(diǎn)，也可以通過(guò)計(jì)算來(lái)自動(dòng)建立。目前已有多種計(jì)算對(duì)應(yīng)關(guān)系的方法，如利用模型表面上多尺度的曲率特征顯著點(diǎn)、內(nèi)蘊(yùn)的全局多尺度縮放特征、MSbius空間上的顯著特征、光流特征等等。另一類(lèi)則基于非線性變分技術(shù)，同時(shí)求解非剛性變換的參數(shù)和對(duì)應(yīng)關(guān)系。

2.4借助的先驗(yàn)知識(shí)

非剛性注冊(cè)解決的是NP的局部匹配問(wèn)題，故既有算法往往借助某些先驗(yàn)知識(shí)來(lái)降低問(wèn)題求解的難度。

預(yù)先提供對(duì)應(yīng)關(guān)系(即標(biāo)記點(diǎn))是研究人員最先采用的方案。在已知對(duì)應(yīng)關(guān)系下，非剛性注冊(cè)問(wèn)題簡(jiǎn)化為形變(morphing)問(wèn)題。但實(shí)際上，morphing本身也是一個(gè)非線性的問(wèn)題，也是一個(gè)公認(rèn)的難題。此外，手工設(shè)置標(biāo)記點(diǎn)不但繁瑣而枯燥，而且很多情況下對(duì)模型根本無(wú)法手工設(shè)置標(biāo)記點(diǎn)。

模板提供了很強(qiáng)的幾何先驗(yàn)知識(shí)，它將非剛性注冊(cè)簡(jiǎn)化為局部一整體匹配問(wèn)題，并能有效補(bǔ)洞和降噪。但是，基于模板的算法也有局限，主要不足之處為：①需預(yù)先建立模板(在正常情況下，很難預(yù)先建立模板)；②若建立的模板與真實(shí)對(duì)象外形相差較大，容易出現(xiàn)不匹配現(xiàn)象。

3、結(jié)束語(yǔ)

從計(jì)算機(jī)算法分析的角度看，非剛性注冊(cè)問(wèn)題是一類(lèi)復(fù)雜的最優(yōu)化問(wèn)題，研究才剛剛起步，在概念和技術(shù)途徑上也還沒(méi)有統(tǒng)一和定型，算法的適用性、魯棒性和高效性離實(shí)際應(yīng)用還有很大的距離，尚有很多問(wèn)題亟待解決：①缺乏非剛性注冊(cè)問(wèn)題的理論探討與求解機(jī)理的系統(tǒng)性研究。既有算法均在特定假設(shè)前提下工作，非剛性注冊(cè)的問(wèn)題得到了簡(jiǎn)化，但往往解決的不是真正意義上的局部匹配問(wèn)題；清晰的理論模型和系統(tǒng)化的求解方法體系的建立也無(wú)從說(shuō)起。②缺乏輸入數(shù)據(jù)對(duì)非剛性注冊(cè)的影響的研究。現(xiàn)有研究大多均假定輸入數(shù)據(jù)是近似完美的(無(wú)噪聲和缺失數(shù)據(jù)較少)，重疊區(qū)域是較大的，或是某種特定類(lèi)型的數(shù)據(jù)(或是開(kāi)放的或是閉合的)，拓?fù)浣Y(jié)構(gòu)是不發(fā)生變化的，但現(xiàn)實(shí)的輸入數(shù)據(jù)往往與上述假設(shè)相違背。③缺乏無(wú)先驗(yàn)知識(shí)輔助下的算法研究。標(biāo)記點(diǎn)和模板等先驗(yàn)知識(shí)降低了非剛性注冊(cè)的難度，但也約束了算法的應(yīng)用范圍。

盡管面臨眾多難題，重要的理論價(jià)值和廣闊的應(yīng)用前景是研究非剛性注冊(cè)問(wèn)題的強(qiáng)大動(dòng)力。當(dāng)前，以實(shí)用為目標(biāo)，系統(tǒng)化考慮輸入數(shù)據(jù)的影響，在無(wú)先驗(yàn)知識(shí)前提下，研究精確匹配、適用范圍廣、魯棒性好且高效的非剛性注冊(cè)算法以及分析其系統(tǒng)理論模型與方法體系是非常必要且十分迫切的。