由粗到精的三維等距模型對(duì)應(yīng)關(guān)系計(jì)算

楊 軍，史紀(jì)東

(蘭州交通大學(xué) 電子與信息工程學(xué)院，蘭州 730070)

0 引 言

在2個(gè)或多個(gè)模型間，或者相鄰視頻幀之間建立正確的對(duì)應(yīng)關(guān)系是一項(xiàng)非常重要的基礎(chǔ)性研究工作[1]。對(duì)應(yīng)關(guān)系在計(jì)算機(jī)圖形學(xué)和計(jì)算機(jī)視覺(jué)等領(lǐng)域有廣泛的應(yīng)用，例如模型插值[2]，模型屬性遷移[3]，模型注冊(cè)[4]，場(chǎng)景識(shí)別[5]，模型匹配[6]，統(tǒng)計(jì)模型分析[7]等。

由于三維模型是通過(guò)大量的三角網(wǎng)格在空間拼接構(gòu)建而成，因此，計(jì)算源模型與目標(biāo)模型間對(duì)應(yīng)關(guān)系的過(guò)程，就可以描述為一種組合優(yōu)化問(wèn)題。也就是說(shuō)，計(jì)算源模型與目標(biāo)模型間的最優(yōu)對(duì)應(yīng)關(guān)系，就是在所有可能存在的對(duì)應(yīng)關(guān)系集合中尋找到一組誤差最小，匹配結(jié)果最理想的對(duì)應(yīng)關(guān)系。在計(jì)算三維模型對(duì)應(yīng)關(guān)系的過(guò)程中，等距是一個(gè)非常重要的屬性，即模型在發(fā)生剛性變換(如旋轉(zhuǎn)、平移和反射等)或非剛性變換(如扭曲、拉伸、縮放和折疊等)之后，模型上任意兩點(diǎn)間的距離度量仍保持等距不變。但由于建模過(guò)程中存在的缺陷以及幾何計(jì)算中存在的離散化誤差，即使是針對(duì)不同姿態(tài)下的同一剛體模型，也不能保證兩點(diǎn)間的距離度量保持完全等距不變。

由于現(xiàn)實(shí)世界中大多數(shù)的形變是等距的，而且具有相似語(yǔ)義屬性的模型具有相似的度量結(jié)構(gòu)，因此，在對(duì)應(yīng)關(guān)系的研究工作中，有很多基于模型等距屬性的研究方法。合理地利用模型的等距屬性，可以簡(jiǎn)化對(duì)應(yīng)關(guān)系的計(jì)算。文獻(xiàn)[8]將測(cè)地卷積神經(jīng)網(wǎng)絡(luò)(geodesic convolutional neural networks，GCNN)應(yīng)用到模型間對(duì)應(yīng)關(guān)系的計(jì)算中。當(dāng)模型發(fā)生等距變形時(shí)，通過(guò)定義一個(gè)基于極坐標(biāo)的測(cè)地距離函數(shù)，實(shí)現(xiàn)對(duì)模型特征信息的提取，進(jìn)而利用網(wǎng)絡(luò)結(jié)構(gòu)中的每一層對(duì)提取的信息進(jìn)行訓(xùn)練，并通過(guò)濾波器系數(shù)對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化，輸出最后的模型間的對(duì)應(yīng)關(guān)系。然而，對(duì)于表面存在紋理特征的模型，該網(wǎng)絡(luò)結(jié)構(gòu)并不能通過(guò)訓(xùn)練得到理想的特征描述符。文獻(xiàn)[9]將計(jì)算三維模型間對(duì)應(yīng)關(guān)系的問(wèn)題轉(zhuǎn)化為計(jì)算三維網(wǎng)格模型上最優(yōu)路徑的問(wèn)題。通過(guò)動(dòng)態(tài)規(guī)劃算法不斷減小等距誤差，并利用完全匹配算法得到稠密對(duì)應(yīng)關(guān)系。然而，由于初始采樣階段的采樣點(diǎn)數(shù)量不足，缺少可以表征三維模型全局特征信息的描述符，從而導(dǎo)致后期匹配出現(xiàn)對(duì)稱翻轉(zhuǎn)問(wèn)題，降低了計(jì)算對(duì)應(yīng)關(guān)系的準(zhǔn)確率。本文旨在構(gòu)建2個(gè)等距模型間的稠密對(duì)應(yīng)關(guān)系，然而在利用由粗到精匹配算法計(jì)算模型間稠密對(duì)應(yīng)關(guān)系的過(guò)程中，單純依靠測(cè)地距離度量進(jìn)行計(jì)算，容易受模型自身對(duì)稱性的影響而產(chǎn)生錯(cuò)誤的對(duì)應(yīng)關(guān)系，從而在初始匹配階段不能得到理想的稀疏對(duì)應(yīng)關(guān)系。本文首先通過(guò)引入初始譜植入匹配算法，將模型植入到譜域空間來(lái)分析，并計(jì)算得到模型間準(zhǔn)確的稀疏對(duì)應(yīng)關(guān)系；然后使用空間一致采樣法并結(jié)合二分圖匹配算法，通過(guò)由粗到精的匹配優(yōu)化過(guò)程迭代獲取每一層的對(duì)應(yīng)關(guān)系，即將稀疏對(duì)應(yīng)關(guān)系擴(kuò)展至稠密對(duì)應(yīng)關(guān)系。

1 相關(guān)研究工作

由于對(duì)應(yīng)關(guān)系的應(yīng)用非常廣泛，三維模型間對(duì)應(yīng)關(guān)系的研究成為了國(guó)內(nèi)外研究的熱點(diǎn)。在眾多的對(duì)應(yīng)關(guān)系計(jì)算方法中，譜植入是一類比較高效的方法，它將模型從一個(gè)空間植入到另一個(gè)空間中進(jìn)行分析，如莫比烏斯(M?bius)植入方法、擴(kuò)展的多維尺度分析法、譜分析方法以及基于拉普拉斯算子的方法等。

基于莫比烏斯植入的研究方法[10-12]在復(fù)平面通過(guò)保角植入方法將給定的模型植入到正則坐標(biāo)框架中，使用相鄰最近點(diǎn)近似估計(jì)M?bius變換后的等距誤差，但是這類植入方法只適用于完整的(沒(méi)有缺失部件或空洞)三維模型間的對(duì)應(yīng)關(guān)系計(jì)算，并在計(jì)算過(guò)程中對(duì)某些變量的獲取方式普遍存在近似估計(jì)的問(wèn)題。為了消除在植入過(guò)程中由于近似估計(jì)某些變量而導(dǎo)致錯(cuò)誤對(duì)應(yīng)關(guān)系的問(wèn)題，Aflalo等[13]提出了基于譜空間的擴(kuò)展多維尺度分析法(spectral generalized multidimensional scaling，S-GMDS)。利用S-GMDS算法避免了傳統(tǒng)植入過(guò)程中存在的非凸性情況，更好地提取了三維模型的結(jié)構(gòu)特征信息，實(shí)現(xiàn)了三維模型的準(zhǔn)確譜植入，計(jì)算得到了理想的對(duì)應(yīng)關(guān)系。然而，該算法仍存在2個(gè)缺點(diǎn)：①當(dāng)源模型與目標(biāo)模型的尺度不一致時(shí)，該算法缺少尺度比例參數(shù)，無(wú)法計(jì)算得到模型間正確的對(duì)應(yīng)關(guān)系；②由于S-GMDS算法是基于測(cè)地距離度量的計(jì)算。因此，當(dāng)三維模型表面出現(xiàn)拓?fù)湓肼晻r(shí)，需要引入擴(kuò)散距離度量或者通勤時(shí)間距離度量對(duì)測(cè)地距離度量進(jìn)行替換，以增強(qiáng)S-GMDS算法在部分模型(即模型存在缺失部件或空洞等)與完整模型之間的對(duì)應(yīng)關(guān)系計(jì)算的健壯性。文獻(xiàn)[14]提出了基于極點(diǎn)譜植入初始化的貪婪優(yōu)化算法。通過(guò)基于高斯曲率的最遠(yuǎn)點(diǎn)采樣算法獲得采樣點(diǎn)，利用基于全局度量(測(cè)地距離)的貪婪優(yōu)化算法進(jìn)行迭代優(yōu)化，從而構(gòu)建出三維等距模型間的稀疏對(duì)應(yīng)關(guān)系。但是該算法構(gòu)建對(duì)應(yīng)關(guān)系時(shí)也會(huì)受到模型自身對(duì)稱性的影響。2016年，楊軍等[15]提出了一種基于熱核描述符與波核描述符的融合特征描述符。通過(guò)計(jì)算三維模型的Laplace算子獲得模型的特征向量和特征值，將所得到的特征值和特征向量作為基參數(shù)，分別計(jì)算源模型與目標(biāo)模型的熱核簽名和波核簽名，并將熱核簽名與波核簽名融合為一個(gè)新的特征描述符，最終通過(guò)最小值匹配算法得到源模型和目標(biāo)模型之間的對(duì)應(yīng)關(guān)系。與單一使用熱核簽名或波核簽名特征描述符相比，得到了更加準(zhǔn)確的對(duì)應(yīng)關(guān)系。但是，針對(duì)存在缺失部件或空洞的模型，該算法不能構(gòu)建出準(zhǔn)確的對(duì)應(yīng)關(guān)系。

此外，利用模型的局部信息構(gòu)建模型間的對(duì)應(yīng)關(guān)系，也是一種廣為應(yīng)用的計(jì)算方法。特別是當(dāng)模型發(fā)生非等距變換的時(shí)候，模型局部信息是一個(gè)很重要的屬性，例如模型上每個(gè)頂點(diǎn)的高斯曲率。然而，當(dāng)模型局部幾何結(jié)構(gòu)發(fā)生比較大改變的時(shí)候，單純利用模型的局部幾何信息來(lái)計(jì)算對(duì)應(yīng)關(guān)系，往往得不到理想的結(jié)果。文獻(xiàn)[16]研究在2個(gè)三維非等距模型間，構(gòu)建源模型與目標(biāo)模型上相同部件之間的對(duì)應(yīng)關(guān)系。使用了特征函數(shù)分別對(duì)源模型與目標(biāo)模型建立親和度矩陣，利用親和度矩陣分別定義源模型與目標(biāo)模型上2個(gè)相同部件的穩(wěn)定性參數(shù)，并利用該參數(shù)計(jì)算源模型與目標(biāo)模型相同部件之間的對(duì)應(yīng)關(guān)系。然而，特征函數(shù)計(jì)算出的匹配效果依賴于2個(gè)閾值參數(shù)，如何獲取最優(yōu)的閾值參數(shù)，算法還需要進(jìn)一步改進(jìn)。文獻(xiàn)[17]利用照相機(jī)從不同角度對(duì)三維模型進(jìn)行拍照，得到多角度多尺度的二維視圖數(shù)據(jù)，利用深度卷積網(wǎng)絡(luò)對(duì)二維視圖數(shù)據(jù)進(jìn)行訓(xùn)練，從而得到三維模型的局部特征描述符，根據(jù)局部特征描述符實(shí)現(xiàn)對(duì)模型間對(duì)應(yīng)關(guān)系的計(jì)算。然而，該算法在計(jì)算部分模型與整體模型間對(duì)應(yīng)關(guān)系時(shí)，對(duì)于殘缺部件較多的部分模型，不能得到良好的模型間對(duì)應(yīng)關(guān)系。

構(gòu)建模型間的對(duì)應(yīng)關(guān)系，還可以通過(guò)所計(jì)算的對(duì)應(yīng)關(guān)系的稀疏度進(jìn)行分類，有稀疏對(duì)應(yīng)關(guān)系和稠密對(duì)應(yīng)關(guān)系。Yusuf Sahillioglu等[18]利用EM算法，根據(jù)測(cè)地距離獲取初始采樣點(diǎn)，對(duì)模型進(jìn)行譜植入操作并對(duì)齊，得到初始對(duì)應(yīng)關(guān)系，最后利用貪婪優(yōu)化算法對(duì)初始匹配結(jié)果進(jìn)行優(yōu)化，但該算法只能實(shí)現(xiàn)稀疏的對(duì)應(yīng)關(guān)系計(jì)算。文獻(xiàn)[19]在歐式空間使用測(cè)地距離計(jì)算三維等距模型的稀疏對(duì)應(yīng)關(guān)系，通過(guò)由粗到精的迭代采樣算法(coarse-to-fine，CtoF)和組合匹配算法，將源模型與目標(biāo)模型之間的稀疏對(duì)應(yīng)關(guān)系擴(kuò)展到稠密對(duì)應(yīng)關(guān)系。但是使用測(cè)地距離描述符計(jì)算對(duì)應(yīng)關(guān)系，不能充分地描述模型上各個(gè)部分的更多細(xì)節(jié)特征，因此，在初期稀疏匹配階段和后期稠密匹配階段會(huì)出現(xiàn)對(duì)稱反轉(zhuǎn)的問(wèn)題，從而導(dǎo)致匹配錯(cuò)誤。

為了能夠獲取分布更為一致的采樣點(diǎn)，提高對(duì)應(yīng)關(guān)系的計(jì)算準(zhǔn)確率。本文在文獻(xiàn)[18-19]的基礎(chǔ)上提出了一種基于初始譜植入計(jì)算三維等距模型稠密對(duì)應(yīng)關(guān)系的方法。主要?jiǎng)?chuàng)新點(diǎn)和貢獻(xiàn)：①在獲取采樣點(diǎn)的過(guò)程中，計(jì)算所有頂點(diǎn)的高斯曲率并進(jìn)行排序，利用基于曲率的均勻一致采樣策略(curvature-oriented evenly-spaced sampling，COES)對(duì)源模型與目標(biāo)模型采樣，這樣獲取的采樣點(diǎn)更具代表性，能更好地反映模型的突出特征；②在初始匹配階段，提出了以初始譜植入構(gòu)建模型間稀疏對(duì)應(yīng)關(guān)系的方法，避免了由于三維模型自身固有的對(duì)稱性而導(dǎo)致錯(cuò)誤的對(duì)應(yīng)關(guān)系，減小了對(duì)應(yīng)關(guān)系的等距誤差，使稠密對(duì)應(yīng)關(guān)系的正確率得到明顯改善。

2 EM框架

在計(jì)算2個(gè)模型間對(duì)應(yīng)關(guān)系的過(guò)程中，當(dāng)完成采樣工作以后，需要對(duì)源模型與目標(biāo)模型上的采樣點(diǎn)進(jìn)行匹配，如何在不同的組合排列中尋找到最理想的一組對(duì)應(yīng)關(guān)系，是一個(gè)十分關(guān)鍵的問(wèn)題。本文將等距誤差作為計(jì)算對(duì)應(yīng)關(guān)系的依據(jù)，即等距誤差最小化。

計(jì)算等距誤差最小值的問(wèn)題可以描述為計(jì)算似然概率的最大值問(wèn)題，即

§|X,Q)

(1)

(1)式中：X=(S,T)表示基本輸入數(shù)據(jù)，S和T分別為源模型與目標(biāo)模型上的采樣點(diǎn)集合；Q是一個(gè)矩陣，用qij表示矩陣Q中的元素，表示從源模型上的采樣點(diǎn)si到目標(biāo)模型上對(duì)應(yīng)的采樣點(diǎn)tj的匹配概率，因此qij之和為1；§表示源模型與目標(biāo)模型之間的一組對(duì)應(yīng)關(guān)系。由于本文的研究?jī)?nèi)容是計(jì)算2個(gè)等距模型之間的稠密對(duì)應(yīng)關(guān)系，因此，對(duì)于源模型中的每個(gè)采樣點(diǎn)，通過(guò)計(jì)算都會(huì)與目標(biāo)模型中相應(yīng)的采樣點(diǎn)對(duì)應(yīng)起來(lái)。

大量實(shí)驗(yàn)表明，期望最大化方法(expectation maximization，EM)可以較好地應(yīng)用于計(jì)算似然函數(shù)最大化的問(wèn)題。本文實(shí)驗(yàn)中，分別用§(k)與Q(k)保存§與Q在每一次迭代計(jì)算中的結(jié)果。從Q(0)開(kāi)始，通過(guò)E步與M步可以計(jì)算出每一次迭代得到的矩陣Q(k)與對(duì)應(yīng)關(guān)系§(k)，直至Q(k)與§(k)的計(jì)算結(jié)果趨于收斂。E步和M步的計(jì)算如下

E-step：

Q(k)=E(Q|X,§(k-1))

(2)

M-step：

(3)

利用Gibbs分布函數(shù)可以計(jì)算出源模型上采樣點(diǎn)si與目標(biāo)模型上采樣點(diǎn)tj之間對(duì)應(yīng)關(guān)系的概率，即等距誤差為

(4)

(4)式中：β是用來(lái)表示采樣點(diǎn)離散程度的常數(shù)；Ti是歸一化的常量；diso(si,tj)表示si與tj的等距誤差，計(jì)算公式為

§(k-1))=

(5)

利用(5)式的計(jì)算結(jié)果，代入Gibbs分布函數(shù)，即(4)式，可得

(6)

根據(jù)計(jì)算得出的每一組對(duì)應(yīng)關(guān)系的概率qij，將計(jì)算結(jié)果代入(3)式，計(jì)算似然函數(shù)最大值

(7)

結(jié)合(6)式和(7)式即可得到對(duì)應(yīng)關(guān)系

(8)

要想獲得最理想的對(duì)應(yīng)關(guān)系，就必須在所有可能存在的對(duì)應(yīng)關(guān)系集合中尋找到一組等距誤差最小的對(duì)應(yīng)關(guān)系。(7)式為似然函數(shù)，(8)式由(7)式推導(dǎo)得出，計(jì)算(7)式的最大值問(wèn)題就轉(zhuǎn)化為計(jì)算(8)式的最大值問(wèn)題。由于(8)式中第一項(xiàng)為常量，對(duì)計(jì)算最大值沒(méi)有影響，因此，舍棄第一項(xiàng)。第二項(xiàng)是負(fù)值，要想計(jì)算(8)式的最大值，也就是求出負(fù)號(hào)后邊那一部分的最小值，即計(jì)算得到似然函數(shù)最大值，也就計(jì)算得出了等距誤差值最小值。從而由(8)式推導(dǎo)得出(9)式。因此，計(jì)算得到模型間一組等距誤差最小的對(duì)應(yīng)關(guān)系，即計(jì)算得出似然函數(shù)最大期望值。

(9)

從初始階段Q(0)開(kāi)始， EM算法根據(jù)每次計(jì)算得到的結(jié)果§(k-1)，迭代k次，利用(10)式計(jì)算等距誤差的最小值，即可得到初始匹配階段最理想的對(duì)應(yīng)關(guān)系§(k)。

(10)

3 COES采樣

基于曲率的均勻一致采樣策略COES是一種依據(jù)三維模型各頂點(diǎn)高斯曲率數(shù)值大小進(jìn)行均勻采樣的方法。該方法首先計(jì)算模型的表面積，然后計(jì)算采樣半徑r，最后根據(jù)模型上各頂點(diǎn)的高斯曲率并結(jié)合半徑r進(jìn)行采樣。半徑r的計(jì)算公式為

(11)

(11)式中：A表示模型的表面積；r(k))表示第k層的采樣半徑；A(k-1)表示第k-1層中根據(jù)最大半徑計(jì)算得到的采樣區(qū)域的面積。COES采樣方法的具體步驟如下。

步驟1計(jì)算模型上每一個(gè)頂點(diǎn)的高斯曲率，并且記錄每一個(gè)頂點(diǎn)的索引值。

步驟2根據(jù)三維網(wǎng)格模型的點(diǎn)、線、面基本數(shù)據(jù)信息，計(jì)算模型上每個(gè)三角網(wǎng)格的面積，并進(jìn)行求和運(yùn)算以得出三維網(wǎng)格模型的表面積。

步驟3根據(jù)(11)式計(jì)算采樣半徑。

步驟4利用插入排序算法對(duì)各頂點(diǎn)高斯曲率值按從大到小進(jìn)行排序，與此同時(shí)，更新頂點(diǎn)的索引值排序。將高斯曲率值最大的頂點(diǎn)作為初始采樣點(diǎn)s1，并將頂點(diǎn)狀態(tài)設(shè)置為已訪問(wèn)，然后結(jié)合半徑r開(kāi)始采樣。以s1為起始點(diǎn)，遍歷與其相鄰的所有頂點(diǎn)，當(dāng)發(fā)現(xiàn)存在未被訪問(wèn)的頂點(diǎn)時(shí)，將其作為新的起始點(diǎn)，并設(shè)置其狀態(tài)為已訪問(wèn)，然后開(kāi)始遍歷該新起始點(diǎn)的所有鄰接點(diǎn)，這樣又會(huì)得到新的起始點(diǎn)。在遍歷的過(guò)程中，從上一個(gè)起始點(diǎn)到確定新的起始點(diǎn)，是一個(gè)由內(nèi)向外不斷發(fā)散的動(dòng)作。在此過(guò)程中，將遍歷過(guò)的兩兩頂點(diǎn)之間的路徑長(zhǎng)度進(jìn)行累加，并與半徑r進(jìn)行比較，當(dāng)該路徑長(zhǎng)度大于等于半徑r時(shí)，停止該路徑的計(jì)算，從s1開(kāi)始探索新的路徑。直至以采樣點(diǎn)s1為圓心，長(zhǎng)度r為半徑的圓內(nèi)所有的頂點(diǎn)都已訪問(wèn)，即完成了圍繞該采樣點(diǎn)的計(jì)算任務(wù)。

步驟5從排序好的頂點(diǎn)列表中從上至下選取第2個(gè)未被訪問(wèn)的頂點(diǎn)作為第2個(gè)采樣點(diǎn)，結(jié)合采樣半徑r繼續(xù)進(jìn)行采樣。以此類推，直至三維模型上所有頂點(diǎn)都已訪問(wèn)，即完成M個(gè)采樣點(diǎn)的選取。根據(jù)大量實(shí)驗(yàn)測(cè)定，M的取值與三維模型的表面積相關(guān)聯(lián)，一般在4～6，本文設(shè)定M=5。圖1是利用不同采樣半徑得到的COES采樣結(jié)果。對(duì)于不用的采樣點(diǎn)，包括落在以r為半徑的圓內(nèi)的其余頂點(diǎn)，使用不同的顏色進(jìn)行標(biāo)記。其中，圖1a的采樣半徑為r=1.842 17E-005，圖1b采樣半徑為r=3.223 8E-005。

圖1 不同采樣半徑下的COES采樣結(jié)果Fig.1 COES results under different sampling radius

在文獻(xiàn)[20]中，對(duì)于第2個(gè)采樣點(diǎn)的選取，不是按照從上至下將未訪問(wèn)的第2個(gè)頂點(diǎn)作為下一個(gè)采樣點(diǎn)，而是采用了隨機(jī)選擇的策略。按照該策略進(jìn)行采樣，源模型與目標(biāo)模型上的采樣點(diǎn)就會(huì)隨機(jī)分布于模型上的表面上，不同采樣策略下的COES采樣結(jié)果如圖2所示。圖2a是根據(jù)文獻(xiàn)[20]得到的采樣點(diǎn)結(jié)果，可以明顯地看出，采樣點(diǎn)分別分布于猩猩模型的腹部，背部，手臂關(guān)節(jié)處，只有一個(gè)采樣點(diǎn)分布在猩猩模型的手指上，因此，采用這種采樣點(diǎn)獲取方法會(huì)降低對(duì)應(yīng)關(guān)系匹配的正確率。而本文選取采樣點(diǎn)策略的優(yōu)勢(shì)是，將高斯曲率數(shù)值大小作為采樣依據(jù)，在源模型與目標(biāo)模型上盡可能得到分布一致的采樣點(diǎn)，從而有利于提高對(duì)應(yīng)關(guān)系計(jì)算的正確率。圖2b是根據(jù)本文算法得到的實(shí)驗(yàn)效果，可以看出，在猩猩模型的左爪與右爪的指尖上分別獲得一個(gè)采樣點(diǎn)，還有一個(gè)位于猩猩的腳趾上，其余2個(gè)也都位于特征明顯的部位，因此，本文的采樣點(diǎn)獲取策略可以在模型上得到更具有代表性的采樣點(diǎn)，從而可以提高對(duì)應(yīng)關(guān)系計(jì)算的正確率。

4 初始匹配

在由粗到精的對(duì)應(yīng)關(guān)系計(jì)算過(guò)程中，初始階段的對(duì)應(yīng)關(guān)系匹配效果對(duì)后期的多層匹配具有重要的意義。由于三維模型自身固有的對(duì)稱性，往往會(huì)導(dǎo)致初始階段的匹配效果不佳，進(jìn)而影響后期的多層匹配，致使計(jì)算出的對(duì)應(yīng)關(guān)系存在較多錯(cuò)誤。因此，如何在初始階段計(jì)算得到較好的稀疏對(duì)應(yīng)關(guān)系，是本文研究的重點(diǎn)內(nèi)容。

初始匹配的計(jì)算步驟如下。

步驟1使用Dijkstra算法計(jì)算任意2個(gè)采樣點(diǎn)之間的測(cè)地距離g(si,tj)，并計(jì)算出Uij作為測(cè)地親和度矩陣的元素。

Uij=exp(-g2(i,j)/2σ2)

(12)

(12)式中，σ表示模型表面上最大的測(cè)地距離長(zhǎng)度。

步驟2利用計(jì)算出的測(cè)地親和度矩陣，通過(guò)多維尺度分析法(multi-dimensional scaling，MDS)將源模型與目標(biāo)模型上的采樣點(diǎn)集合分別植入到H維空間中。

步驟3在植入的過(guò)程中，盡管對(duì)源模型和目標(biāo)模型都進(jìn)行了相同的植入變換運(yùn)算，但是由于植入過(guò)程中存在可能任意翻轉(zhuǎn)的情況，從而會(huì)導(dǎo)致在植入空間出現(xiàn)采樣點(diǎn)分布不一致的情況，因此，需要進(jìn)行2H次對(duì)齊計(jì)算，才能獲取最優(yōu)的對(duì)齊結(jié)果Cm。

(13)

(13)式中：ti表示在植入空間中目標(biāo)模型上的采樣點(diǎn)；|sm|表示在植入空間中源模型上采樣點(diǎn)的個(gè)數(shù)，其中，m表示在植入空間中源模型上每個(gè)采樣點(diǎn)的鄰接點(diǎn)個(gè)數(shù)。

步驟4由于在植入空間中，模型上任意2點(diǎn)間的歐氏距離近似等于原始三維空間中的測(cè)地距離，因此，可將測(cè)地距離作為歐氏距離的近似值，在植入空間中計(jì)算得到相應(yīng)采樣點(diǎn)的等距誤差，從而減少時(shí)間消耗。

(14)

步驟5利用二分圖匹配算法得到初始階段的對(duì)應(yīng)關(guān)系。

圖3為利用本文的初始譜植入算法構(gòu)建的猩猩模型間的初始稀疏對(duì)應(yīng)關(guān)系，用黑色實(shí)線表示。

圖3 猩猩模型初始匹配階段的稀疏對(duì)應(yīng)關(guān)系Fig.3 Initial sparse correspondence between gorilla pairs

5 稠密對(duì)應(yīng)關(guān)系計(jì)算

構(gòu)建2個(gè)模型間的稠密對(duì)應(yīng)關(guān)系，是以初始匹配階段構(gòu)建的稀疏對(duì)應(yīng)關(guān)系為基礎(chǔ)。本文計(jì)算稠密對(duì)應(yīng)關(guān)系采用分層迭代的思想，每一層包含采樣、對(duì)應(yīng)關(guān)系計(jì)算、優(yōu)化等3個(gè)步驟。其中，層數(shù)參數(shù)通過(guò)手動(dòng)進(jìn)行設(shè)置。具體計(jì)算步驟如下。

步驟1計(jì)算采樣點(diǎn)。根據(jù)初始匹配階段的采樣點(diǎn)依次計(jì)算出源模型上M個(gè)(目標(biāo)模型上為M′個(gè))采樣點(diǎn)的圓面積，利用最大面積的數(shù)值更新采樣半徑r，并保存面積最大的采樣點(diǎn)si，tj(1≤i≤M，1≤j≤M′)的索引值。從采樣點(diǎn)si，tj開(kāi)始，結(jié)合半徑r，分別計(jì)算出圍繞si，tj的M和M′個(gè)新的采樣點(diǎn)。以此類推，計(jì)算出其余新的采樣點(diǎn)。

步驟2計(jì)算對(duì)應(yīng)關(guān)系。分別計(jì)算以si，tj采樣點(diǎn)為中心，以r為半徑的圓內(nèi)的M個(gè)和M′個(gè)新的采樣點(diǎn)的對(duì)應(yīng)關(guān)系。在計(jì)算的過(guò)程中，使用組合排列的思想，針對(duì)每一個(gè)圓內(nèi)的采樣點(diǎn)進(jìn)行匹配。將源模型的M個(gè)基點(diǎn)排成一列，目標(biāo)模型上的M′個(gè)基點(diǎn)排成一列，它們之間共有C(M,M′)M!種組合方式。分別計(jì)算源模型上的第1個(gè)采樣點(diǎn)到目標(biāo)模型上的所有采樣點(diǎn)的等距誤差，將等距誤差數(shù)值最小的對(duì)應(yīng)關(guān)系保存下來(lái)。繼續(xù)計(jì)算源模型的第2個(gè)頂點(diǎn)到目標(biāo)模型上的所有采樣點(diǎn)的等距誤差，仍然將等距誤差數(shù)值最小的對(duì)應(yīng)關(guān)系保存下來(lái)。以此類推，即可從C(M,M′)M!種組合方式中計(jì)算出一組對(duì)應(yīng)關(guān)系。至此，以si，tj采樣點(diǎn)為中心的對(duì)應(yīng)關(guān)系計(jì)算完畢，繼續(xù)計(jì)算剩余采樣點(diǎn)中的新的對(duì)應(yīng)關(guān)系。

步驟3修正并進(jìn)行優(yōu)化。因?yàn)椴襟E2計(jì)算得到的結(jié)果并不完全正確，對(duì)于其中存在錯(cuò)誤的對(duì)應(yīng)關(guān)系，需要對(duì)其進(jìn)行修正。文中首先對(duì)該層次計(jì)算得到的所有的對(duì)應(yīng)關(guān)系重新排列，然后使用貪婪優(yōu)化算法進(jìn)行修正以達(dá)到優(yōu)化的目的。對(duì)于(si,tj)，如果存在diso(si,tm)

圖4表示第k-1層的對(duì)應(yīng)關(guān)系計(jì)算過(guò)程。由圖4可知，在分別以si，tj為圓心的陰影區(qū)域內(nèi)，計(jì)算得到源模型上M個(gè)(目標(biāo)模型上為M′個(gè))采樣點(diǎn)，然后使用組合匹配算法計(jì)算M與M′個(gè)采樣點(diǎn)之間的對(duì)應(yīng)關(guān)系，待該層所有采樣點(diǎn)對(duì)應(yīng)關(guān)系計(jì)算完畢，使用貪婪優(yōu)化算法對(duì)其進(jìn)行優(yōu)化。圖5表示第k層的對(duì)應(yīng)關(guān)系計(jì)算過(guò)程。從k-1層到k層，首先更新采樣半徑；其次利用更新后的半徑，計(jì)算得到以si，tj以及在第k-1層已經(jīng)存在的采樣點(diǎn)(圖4中黑色實(shí)心圓采樣點(diǎn))為圓心的區(qū)域內(nèi)的第k層的采樣點(diǎn)(圖5中方形采樣點(diǎn))；然后使用組合匹配算法分別計(jì)算源模型與目標(biāo)模型間每一個(gè)圓內(nèi)的采樣點(diǎn)的對(duì)應(yīng)關(guān)系；最后使用貪婪優(yōu)化算法對(duì)其進(jìn)行優(yōu)化。全部層數(shù)計(jì)算結(jié)束后，即得到了源模型與目標(biāo)模型間的稠密對(duì)應(yīng)關(guān)系。通過(guò)這種方法，將全局問(wèn)題轉(zhuǎn)化為局部問(wèn)題，分層次求解，不僅保證了對(duì)應(yīng)關(guān)系計(jì)算的準(zhǔn)確率，而且提高了計(jì)算的效率。

圖4 計(jì)算第k-1層對(duì)應(yīng)關(guān)系Fig.4 Calculation of the k-1th level shape correspondences

6 實(shí)驗(yàn)結(jié)果與分析

本算法在Microsoft visual studio 2012下，結(jié)合圖形用戶接口程序OpenGl編程實(shí)現(xiàn)。選擇TOSCA模型庫(kù)中的三維網(wǎng)格模型對(duì)文中算法進(jìn)行了驗(yàn)證，并與文獻(xiàn)[19]的方法進(jìn)行了對(duì)比。針對(duì)具有相同頂點(diǎn)數(shù)和三角網(wǎng)格數(shù)的同一類模型，構(gòu)建點(diǎn)點(diǎn)匹配關(guān)系來(lái)衡量上述2種算法的對(duì)應(yīng)關(guān)系計(jì)算結(jié)果的正確性。

圖5 計(jì)算第k層對(duì)應(yīng)關(guān)系Fig.5 Calculation of the kth level shape correspondences

分別利用基于測(cè)地距離度量的算法[13]和基于譜植入的算法(本文算法)構(gòu)建了TOSCA模型庫(kù)中貓模型、猩猩模型、人體模型和跳芭蕾的女演員模型的初始匹配階段的稀疏對(duì)應(yīng)關(guān)系，分別如圖6～圖9所示。在初始匹配階段，根據(jù)COES算法分別在源模型與目標(biāo)模型上獲得5個(gè)初始采樣點(diǎn)。圖6～圖9中，實(shí)線表示采樣點(diǎn)間正確的對(duì)應(yīng)關(guān)系，虛線表示采樣點(diǎn)之間錯(cuò)誤的對(duì)應(yīng)關(guān)系?？梢钥闯?，由于三維模型自身的對(duì)稱性，導(dǎo)致使用測(cè)地距離度量進(jìn)行初始對(duì)應(yīng)關(guān)系計(jì)算時(shí)產(chǎn)生了錯(cuò)誤的對(duì)應(yīng)關(guān)系。在圖6a的貓模型中，源模型的右后腿上的采樣點(diǎn)對(duì)應(yīng)到了目標(biāo)模型的左后腿上；在圖7a的猩猩模型中，源模型右爪上第2個(gè)指尖上的采樣點(diǎn)對(duì)應(yīng)到了目標(biāo)模型的右爪上第3個(gè)指尖上；在圖9a的跳芭蕾的女演員模型中，源模型胳膊上的采樣點(diǎn)對(duì)應(yīng)到了目標(biāo)模型頭部的采樣點(diǎn)。而本文算法通過(guò)初始譜植入算法，并結(jié)合測(cè)地距離，在M維植入空間中構(gòu)建初始稀疏對(duì)應(yīng)關(guān)系?？梢钥闯觯舅惴ㄝ^好地解決了在初始匹配階段由于模型自身對(duì)稱性影響對(duì)應(yīng)關(guān)系計(jì)算的問(wèn)題，構(gòu)建出了完全正確的初始稀疏對(duì)應(yīng)關(guān)系，如圖6b，7b，8b和9b所示。

圖6 構(gòu)建貓模型的初始對(duì)應(yīng)關(guān)系比較Fig.6 Comparison of initial correspondences between cat pairs

圖7 構(gòu)建猩猩模型的初始對(duì)應(yīng)關(guān)系比較Fig.7 Comparison of initial correspondences between gorilla pairs

圖8 構(gòu)建人體模型的初始對(duì)應(yīng)關(guān)系比較Fig.8 Comparison of initial correspondences between human pairs

圖9 構(gòu)建跳芭蕾的女演員模型的初始對(duì)應(yīng)關(guān)系比較Fig.9 Comparison of initial correspondences between ballerina pairs

圖10～圖13分別表示貓模型、猩猩模型、人體模型和跳芭蕾的女演員模型在稠密匹配階段產(chǎn)生的稠密對(duì)應(yīng)關(guān)系。在圖10～圖13中，a圖表示基于測(cè)地距離的算法[19]計(jì)算得到的實(shí)驗(yàn)結(jié)果；b圖表示基于初始譜植入算法(本文算法)得到的實(shí)驗(yàn)結(jié)果。在圖10～圖13中，實(shí)線表示采樣點(diǎn)間正確的對(duì)應(yīng)關(guān)系，虛線表示采樣點(diǎn)間錯(cuò)誤的對(duì)應(yīng)關(guān)系。本文在完成初始匹配計(jì)算后，繼續(xù)對(duì)每組模型分層迭代計(jì)算5次，得到最終的稠密對(duì)應(yīng)關(guān)系，每組模型間的對(duì)應(yīng)關(guān)系個(gè)數(shù)在500～700。可以看出，在圖12a構(gòu)建的模型間的對(duì)應(yīng)關(guān)系中，明顯可以看出，存在從源模型右手臂上的采樣點(diǎn)到目標(biāo)模型右腿上的采樣點(diǎn)的錯(cuò)誤的對(duì)應(yīng)關(guān)系，以及在腿部存在因模型對(duì)稱性引起的錯(cuò)誤對(duì)應(yīng)關(guān)系。在圖12b中，雖然在源模型與目標(biāo)模型的腳上存在一處明顯的錯(cuò)誤的對(duì)應(yīng)關(guān)系，但是，較圖12a對(duì)應(yīng)關(guān)系的正確率得到了顯著提升。在圖13a 2個(gè)跳芭蕾女演員模型的對(duì)應(yīng)關(guān)系中，存在多處由源模型右手上的采樣點(diǎn)對(duì)應(yīng)到了目標(biāo)模型的左腳上的采樣點(diǎn)的錯(cuò)誤對(duì)應(yīng)關(guān)系。在圖13b中，這種現(xiàn)象得到了明顯的改善，根據(jù)實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)，圖13b中的錯(cuò)誤對(duì)應(yīng)關(guān)系的數(shù)量較圖13a中的錯(cuò)誤對(duì)應(yīng)關(guān)系數(shù)量減少了1/3。由圖10，圖11的實(shí)驗(yàn)結(jié)果同樣可以看出，本文提出的基于初始譜植入的計(jì)算方法依然優(yōu)于基于測(cè)地距離的計(jì)算方法。

圖10 計(jì)算貓模型的稠密對(duì)應(yīng)關(guān)系比較Fig.10 Comparison of dense correspondences between cat pairs

圖11 計(jì)算猩猩模型的稠密對(duì)應(yīng)關(guān)系比較Fig.11 Comparison of dense correspondences between gorilla pairs

圖12 計(jì)算人體模型的稠密對(duì)應(yīng)關(guān)系比較Fig.12 Comparison of dense correspondences between human pairs

圖13 計(jì)算跳芭蕾的女演員模型的對(duì)應(yīng)關(guān)系比較Fig.13 Comparison of dense correspondences between ballerina pairs

表1為本文算法與文獻(xiàn)[19]算法的等距誤差的比較，分別對(duì)比了初始匹配階段與稠密匹配階段的等距誤差，根據(jù)等距誤差可以衡量模型間對(duì)應(yīng)關(guān)系的正確率?？梢钥闯?，與文獻(xiàn)[19]相比，本文算法在初始匹配階段與稠密匹配階段的等距誤差均有明顯減小，因此，能夠得到更為準(zhǔn)確的對(duì)應(yīng)關(guān)系。

表1 2種方法計(jì)算的模型間等距誤差的比較

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

模型間對(duì)應(yīng)關(guān)系問(wèn)題是計(jì)算機(jī)圖形學(xué)和計(jì)算機(jī)視覺(jué)領(lǐng)域的一個(gè)基本問(wèn)題，更是一個(gè)難點(diǎn)問(wèn)題。本文提出了以初始譜植入構(gòu)建的稀疏匹配為基礎(chǔ)，利用COES采樣方法和組合匹配算法迭代計(jì)算三維等距模型間稠密對(duì)應(yīng)關(guān)系的算法。實(shí)驗(yàn)結(jié)果表明，本文算法與文獻(xiàn)[19]算法相比，在基本沒(méi)有增加時(shí)間開(kāi)銷的基礎(chǔ)上，減小了模型間對(duì)應(yīng)關(guān)系的等距誤差，使對(duì)應(yīng)關(guān)系正確率在一定程度上得到了提高。然而，本文算法仍然存在改進(jìn)的空間。一方面，稠密匹配階段采樣半徑的初始化?？紤]到計(jì)算稠密對(duì)應(yīng)關(guān)系的時(shí)間成本，本算法采用手動(dòng)設(shè)置采樣半徑的方式，因此，如何自動(dòng)獲取最優(yōu)的初始采樣半徑，仍然需要進(jìn)一步探索；另一方面，對(duì)于模型自身的對(duì)稱性，以及模型構(gòu)建過(guò)程中存在的瑕疵等，都會(huì)影響對(duì)應(yīng)關(guān)系計(jì)算結(jié)果的準(zhǔn)確率，因此，仍需要進(jìn)一步探索對(duì)這些不良因素的處理方法。此外，解決更為廣泛的模型間對(duì)應(yīng)關(guān)系問(wèn)題，例如語(yǔ)義相似的模型之間的對(duì)應(yīng)關(guān)系、部分模型(缺少某個(gè)部件或存在空洞等)與完整模型之間的對(duì)應(yīng)關(guān)系等，也是今后要繼續(xù)研究的問(wèn)題。