一種改進(jìn)的三維形狀非剛性對(duì)準(zhǔn)方法

左向梅，韓鵬程

（西北工業(yè)大學(xué)航空學(xué)院，陜西 西安710072）

0 引言

計(jì)算機(jī)視覺(jué)在自動(dòng)化生產(chǎn)的裝配線上得到了很好的應(yīng)用，能夠用于識(shí)別零部件，在產(chǎn)品檢驗(yàn)方面有著成功的應(yīng)用。真實(shí)準(zhǔn)確的數(shù)字化重建現(xiàn)實(shí)生活中的物體，是計(jì)算機(jī)視覺(jué)研究領(lǐng)域的一個(gè)重要問(wèn)題，而物體的對(duì)準(zhǔn)是在計(jì)算機(jī)中實(shí)現(xiàn)物體重建的一個(gè)重要步驟。三維形狀對(duì)準(zhǔn)的目的就是找到2個(gè)或者多個(gè)三維形狀的頂點(diǎn)之間準(zhǔn)確的對(duì)應(yīng)關(guān)系，通過(guò)減小對(duì)應(yīng)頂點(diǎn)之間的距離使物體發(fā)生形變。然而，在現(xiàn)實(shí)生活中存在著大量的非剛性物體，當(dāng)這些非剛性物體發(fā)生非剛性形變時(shí)，許多基于三維形狀剛性形變對(duì)準(zhǔn)的重建假設(shè)和方法已經(jīng)不再適用，非剛性形變物體的對(duì)準(zhǔn)已經(jīng)成為一個(gè)急需解決的技術(shù)問(wèn)題。

剛性對(duì)準(zhǔn)只需要根據(jù)一些對(duì)應(yīng)關(guān)系就可以定義一個(gè)候選剛性變換來(lái)進(jìn)行假設(shè)測(cè)試，非剛性情況下還需要變形和對(duì)準(zhǔn)信息，因?yàn)樗鼪](méi)有足夠的先驗(yàn)假設(shè)，經(jīng)常需要很多更加可靠的對(duì)應(yīng)來(lái)定義變換。此外，非剛性對(duì)準(zhǔn)還需要考慮變形，因此，相比于剛性對(duì)準(zhǔn)，非剛性對(duì)準(zhǔn)更加困難。

為了克服現(xiàn)有對(duì)準(zhǔn)方法性能差，易產(chǎn)生畸變，對(duì)三維形狀完整性要求高，適用范圍小，對(duì)準(zhǔn)精度低的問(wèn)題［1－3］，提出了基于相關(guān)點(diǎn)漂移和動(dòng)態(tài)形變圖相結(jié)合的三維形狀非剛性形變的自動(dòng)對(duì)準(zhǔn)方法。

1 相關(guān)點(diǎn)漂移

相關(guān)點(diǎn)漂移（CPD）［2］是一種基于概率的點(diǎn)集非剛性配準(zhǔn)算法，該算法被視為基于速度場(chǎng)運(yùn)動(dòng)一致性約束的最大似然估計(jì)問(wèn)題。在CPD算法中，一個(gè)點(diǎn)集作為高斯混合模型的內(nèi)核，另一個(gè)點(diǎn)集作為高斯混合模型的數(shù)據(jù)，采用確定性退火的EM算法［4－5］對(duì)最大似然估計(jì)進(jìn)行優(yōu)化，從而找到2個(gè)點(diǎn)集的對(duì)應(yīng)關(guān)系與非剛性變換，即內(nèi)核點(diǎn)集向數(shù)據(jù)點(diǎn)集配準(zhǔn)。這種方法可以估計(jì)復(fù)雜的非線性和非剛性變換，而且在含有噪聲和溢出點(diǎn)的情況下有較強(qiáng)的魯棒性。

方法中，將源模型的頂點(diǎn)看作數(shù)據(jù)集Y＝（y1，…，yM）T，將目標(biāo)模型的頂點(diǎn)看作產(chǎn)生數(shù)據(jù)集的高斯混合模型的中心（內(nèi)核點(diǎn)集）X＝（x1，…，xN）T，通過(guò)EM［4－5］算法計(jì)算數(shù)據(jù)集中的點(diǎn)，對(duì)應(yīng)混合高斯模型中心的后驗(yàn)概率，從而確立源三維形狀頂點(diǎn)和目標(biāo)三維形狀之間的對(duì)應(yīng)關(guān)系，利用所得的對(duì)應(yīng)關(guān)系，將2個(gè)三維形狀進(jìn)行非剛性粗對(duì)準(zhǔn)。

GM×M為對(duì)稱(chēng)方陣；W＝WM×D＝（w1，…，wM）T為高斯內(nèi)核矩陣；D為點(diǎn)云集的維數(shù)，取D＝3；N，M分別為源三維形狀頂點(diǎn)和目標(biāo)三維形狀頂點(diǎn)的個(gè)數(shù)；tr為向量的跡；λ為常數(shù)。

具體來(lái)說(shuō)，相關(guān)點(diǎn)漂移算法的步驟為：

a．初始化系數(shù)矩陣W＝0，協(xié)方差σ2，參數(shù)ω（0≤ω≤1），β＞0，λ＞0。

b．構(gòu)建核矩陣GM×M，矩陣元素gij＝G（yi，yj）

c．EM算法優(yōu)化。通過(guò)高斯混合模型聚類(lèi)的EM 算法推導(dǎo)，能得到式（1）的上界［6］，即

G（m，·）表示G的第m 行。最小化Q就相當(dāng)于最小化式（1）的能量函數(shù)。

在E步中，計(jì)算后驗(yàn)概率矩陣P，其元素表達(dá)式為：

后驗(yàn)概率pmn表示了頂點(diǎn)xn和ym之間的對(duì)應(yīng)概率。

在M步中，優(yōu)化求解W，對(duì)式（2）關(guān)于W 求導(dǎo)，得到方程：

1為元素全為1的列向量；d為對(duì)角陣。兩邊同乘以σ2G－1，得到方程的線性系統(tǒng)，即

從式（5）中解出W。

d．重復(fù)步驟c，直至收斂。

當(dāng)算法收斂后，三維形狀點(diǎn)之間的對(duì)應(yīng)關(guān)系由后驗(yàn)概率矩陣給出，相應(yīng)的對(duì)準(zhǔn)后的三維形狀T＝T（Y，W）＝Y(jié)＋GW。

2 形變圖驅(qū)動(dòng)模型對(duì)準(zhǔn)

2．1 構(gòu)建動(dòng)態(tài)形變圖

圖模型本身的形變方式是通過(guò)對(duì)每一個(gè)結(jié)點(diǎn)應(yīng)用對(duì)應(yīng)的仿射變換，因此，對(duì)于結(jié)點(diǎn)自身，有槇gj＝gj＋tj。

對(duì)于原始模型上的任意頂點(diǎn)vi，其形變后的位置槇vi可以通過(guò)圖模型每個(gè)結(jié)點(diǎn)的形變加權(quán)求和得到，也就是將形變圖結(jié)點(diǎn)的變換外推到模型上每個(gè)頂點(diǎn)，即

ωj（vi）是與vi和gj之間距離d（gj，vi）相關(guān)的權(quán)值，ωj（vi）＝max｛0，［1－d2（gj，vi）／r2i］3｝。

該點(diǎn)的法向量也被相似變形：

這里使用邊融合技術(shù)，在指定向下采樣的三維模型面?zhèn)€數(shù)情況下，實(shí)現(xiàn)均勻采樣，從而構(gòu)建出原始三維模型的動(dòng)態(tài)形變圖，用來(lái)驅(qū)動(dòng)三維形狀的對(duì)準(zhǔn)。

使用動(dòng)態(tài)形變圖來(lái)驅(qū)動(dòng)原始三維形狀的非剛性對(duì)準(zhǔn)可以減少變量個(gè)數(shù)，降低運(yùn)算量，縮短運(yùn)算時(shí)間，提高三維形狀非剛性對(duì)準(zhǔn)的效率。手模型與其形變?nèi)鐖D1所示。

圖1 手模型及其形變

2．2 動(dòng)態(tài)形變圖驅(qū)動(dòng)模型對(duì)準(zhǔn)

通過(guò)求解形變圖的變形來(lái)驅(qū)動(dòng)原始模型的變形。在非剛性對(duì)準(zhǔn)中，需要對(duì)圖模型的結(jié)點(diǎn)求解未知的旋轉(zhuǎn)變換和平移變換（Ri，ti）。保留特征的變形場(chǎng)可以通過(guò)使用下面的能量最大化局部剛性得到：

r1，r2，r3為Ri的列向量，上式從正交和單位長(zhǎng)度方面測(cè)量了列向量的偏差。還需要額外的正則項(xiàng)確保變形的光滑性：

Esmooth項(xiàng)描述了每個(gè)節(jié)點(diǎn)與其周?chē)?jié)點(diǎn)形變具有相容性。最小化Esmooth保證了整個(gè)三維形狀在對(duì)準(zhǔn)過(guò)程中表面的光滑性。

引用非剛性ICP算法［6］思想，迭代計(jì)算最近點(diǎn)對(duì)應(yīng)關(guān)系，隨后進(jìn)行修剪和變形步驟。為了避免非線性?xún)?yōu)化中的局部最小化，采用逐漸放松形變模型的正則能量系數(shù)的策略［7］。

尤其是免門(mén)票的方式可以吸引更多的消費(fèi)者，這也代表著當(dāng)前旅游發(fā)展模式的方向，可以擴(kuò)大旅游資源的利用效率，企業(yè)員工、游客、社區(qū)居民可在園區(qū)內(nèi)共享優(yōu)美環(huán)境、共享改革開(kāi)放的成果，這也是全域旅游的目標(biāo)導(dǎo)向之一。

因?yàn)檩斎霐?shù)據(jù)在時(shí)間上具有一致性，所以重復(fù)地在源模型和目標(biāo)模型之間使用最近點(diǎn)對(duì)應(yīng)來(lái)決定最優(yōu)的形變。為了獲得較準(zhǔn)匹配，對(duì)應(yīng)能量由點(diǎn)到點(diǎn)和點(diǎn)到面的度量組成，以避免在特征較少區(qū)域出現(xiàn)的不正確對(duì)應(yīng)：

αpoint＝0．1，αplane＝1，槇vi為原始源模型上的點(diǎn)經(jīng)過(guò)動(dòng)態(tài)形變圖映射后對(duì)應(yīng)的新的坐標(biāo)位置；ci為原始目標(biāo)模型上與槇vi對(duì)應(yīng)的點(diǎn)；C為所有對(duì)應(yīng)點(diǎn)對(duì)組成的集合；Efit描述了需要對(duì)準(zhǔn)的三維模型點(diǎn)與點(diǎn)及點(diǎn)與平面之間的距離。

為了求解（Ri，ti），建立目標(biāo)能量函數(shù)：

初始化時(shí)取高的權(quán)值αsmooth＝50，αrigid＝100，此后通過(guò)最小化式（12），交替地進(jìn)行對(duì)應(yīng)點(diǎn)對(duì)的計(jì)算和形變。

2．3 高斯－牛頓法優(yōu)化目標(biāo)函數(shù)

使用高斯牛頓法最小化目標(biāo)函數(shù)（7），高斯牛頓法源于無(wú)約束優(yōu)化的牛頓算法。非線性最小二乘優(yōu)化問(wèn)題中的目標(biāo)函數(shù)形式比較特殊，可以得到其雅克比矩陣的具體形式，將其代入牛頓法的迭代公式中，就可得到高斯牛頓法。

算法的具體步驟如下：

a．給定初始點(diǎn)x（0），精度σ＞0，置k＝0。

b．計(jì)算f（xk），S（xk）。

f．置x（k＋1）＝x（k）＋x。

g．檢驗(yàn)終止原則，否則令k＝k＋1，轉(zhuǎn)步驟b。

通過(guò)上述優(yōu)化過(guò)程，保證了Ri的單位正交性，使三維模型不會(huì)發(fā)生扭曲畸變；使每個(gè)結(jié)點(diǎn)與其周?chē)Y(jié)點(diǎn)的形變具有相容性，確保這個(gè)三維模型在對(duì)準(zhǔn)工程中表面光滑；不斷縮小需對(duì)準(zhǔn)的點(diǎn)與點(diǎn)及點(diǎn)與平面之間的距離，使三維模型朝著目標(biāo)方向發(fā)生形變，最終完成三維形狀的非剛性對(duì)準(zhǔn)。

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

用多組實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證了方法的有效性，所有實(shí)驗(yàn)均在Inter Core（TM）2 Duo E7500 CPU，2 GB內(nèi)存的Windows XP操作系統(tǒng)上，基于Matlab平臺(tái)進(jìn)行。其中，源模型和目標(biāo)模型均為由Kinect對(duì)人體運(yùn)動(dòng)進(jìn)行拍攝拼接得到的三維模型［8］。

在實(shí)驗(yàn)中，對(duì)于不同模型，CPD的參數(shù)選擇對(duì)于實(shí)驗(yàn)結(jié)果影響較大。如圖2所示，圖2a為源模型與目標(biāo)模型；在圖2b中，β＝2．0，λ＝1．0；在圖2c中，β＝3．0，λ＝1．0。由此可以看出，CPD的β參數(shù)影響對(duì)準(zhǔn)后源模型的光滑性，β越大，光滑性越好。模型描述及實(shí)驗(yàn)結(jié)果如表1所示。

由表1可以看出，對(duì)于中等數(shù)據(jù)和大數(shù)據(jù)模型，算法都能在相對(duì)較短的時(shí)間內(nèi)取得較好的配準(zhǔn)精度。形變圖結(jié)點(diǎn)數(shù)目對(duì)實(shí)驗(yàn)速度和精度有一定影響，點(diǎn)數(shù)越多，時(shí)間越長(zhǎng)，匹配精度越高。

圖2 CPD參數(shù)影響

表1 模型描述及實(shí)驗(yàn)結(jié)果

4 結(jié)束語(yǔ)

提出了三維形狀的非剛性形變自動(dòng)對(duì)準(zhǔn)方法，通過(guò)使用相關(guān)點(diǎn)漂移算法結(jié)合動(dòng)態(tài)形變圖技術(shù)，在不依賴(lài)任何幾何特征的情況下，可以自動(dòng)對(duì)準(zhǔn)發(fā)生非剛性形變的完整或不完整的三維模型。實(shí)驗(yàn)結(jié)果表明，即使對(duì)數(shù)據(jù)缺失比較嚴(yán)重或者形變較大的模型，此方法也能取得較好的效果，具有魯棒性強(qiáng)、對(duì)準(zhǔn)精度高、自動(dòng)化程度高和應(yīng)用范圍廣等優(yōu)點(diǎn)。

［1］ Hou T，Qin H．Robust dense registration of partial nonrigid shapes［J］．IEEE Transactions on Visualization and Computer Graphics，2012，18（8）：1268－1280．

［2］ Myronenko A，Song X．Point set registration：coherent point drift［J］．IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32（12）：2262－2275．

［3］ Fabry T，Smeets D，Vandermeulen D，et al．3D non－rigid point cloud based surface registration based on mean shift［C］．Proceedings 18th International Conference on Computer Graphics，Visualization and Computer Vision，2010．121－128．

［4］ 張祥德，唐青松．確定性退火技術(shù)在點(diǎn)配準(zhǔn)中的應(yīng)用［J］．東北大學(xué)學(xué)報(bào)（自然科學(xué)版），2003，24（11）：1119－1122．

［5］ 王 源，陳亞軍．基于高斯混合模型的EM學(xué)習(xí)算法［J］．山西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2005，19（1）：46－49．

［6］ Allen B，Curless B，Popovi Z．The space of human body shapes：reconstruction and parameterization from range scans［J］．ACM Transactions on Graphics，2003，22（3）：587－594．

［7］ Sumner R W，Schmid J，Pauly M．Embedded deformation for shape manipulation［J］．ACM Transactions on Graphics，2007，26（3）：80－86．

［8］ Vlasic D，Peers P，Baran I，et al．Dynamic shape capture using multi－view photometric stereo［J］．ACM Transactions on Graphics，2009，28（5）：174－185．