非剛性三維形狀匹配中基于譜分析的形狀描述符綜述?

張 丹 , 武仲科 , 王醒策 , 呂辰雷 , 劉香圓 , 周明全

1(北京師范大學(xué) 信息科學(xué)與技術(shù)學(xué)院,北京 100875)

2(北京師范大學(xué) 虛擬現(xiàn)實(shí)與可視化技術(shù)研究所,北京 100875)

非剛性三維形狀匹配是圖形學(xué)中的重要問(wèn)題,是形狀識(shí)別[1]、形狀檢索[2]、形狀配準(zhǔn)[3]、形狀分割[4]等工作的研究基礎(chǔ).同時(shí),非剛性形狀匹配也為三維可視化[5]、生物計(jì)算[6]、人臉識(shí)別[7]、醫(yī)學(xué)圖像處理[8]等應(yīng)用領(lǐng)域提供了堅(jiān)實(shí)的理論依據(jù).在上述研究中,非剛性三維形狀檢索與非剛性三維形狀匹配是兩個(gè)非常相似卻不相同的研究問(wèn)題.非剛性三維形狀檢索的主要思想是:首先,將非剛性三維形狀庫(kù)中的所有形狀映射到特征空間中,計(jì)算所有形狀的特征值并添加索引;其次,根據(jù)用戶的需求設(shè)置檢索閾值,并選擇合適的相似度計(jì)算方法;最后,提取出滿足閾值的形狀,并按照相似度降序輸出形狀[9].而非剛性三維形狀匹配研究的是形狀相似性問(wèn)題:同樣將待匹配的形狀映射到特征空間中,選擇形狀的局部特征、全局特征或者兩者的結(jié)合代替待匹配的形狀;然后選擇某種代價(jià)函數(shù)或者距離函數(shù)度量特征,并將特征之間的度量值作為非剛性三維形狀匹配度.可將其概括為兩個(gè)關(guān)鍵步驟:(1) 提取形狀上有效的形狀描述符;(2) 選擇合適的相似度度量.

本文綜述了非剛性三維形狀匹配中基于譜分析的形狀描述符.對(duì)于剛性三維形狀匹配,目前已有大量的研究成果[10?12],其中,迭代最近點(diǎn)匹配算法(iterative closest point,簡(jiǎn)稱ICP)[13]是最常用的三維形狀匹配算法.ICP將形狀上采樣點(diǎn)的空間位置作為形狀描述符,通過(guò)多次迭代最小化源形狀和目標(biāo)形狀采樣點(diǎn)之間的空間距離,實(shí)現(xiàn)剛性三維形狀匹配.然而,ICP 采用人為設(shè)置的迭代次數(shù)作為迭代終止條件,導(dǎo)致算法容易陷入局部最優(yōu).此外,對(duì)于有拓?fù)湓肼暤男螤?僅用空間位置作為形狀描述符,無(wú)法實(shí)現(xiàn)非剛性三維形狀的高精度匹配.因此,研究者需提取更加有效的形狀描述符用于三維形狀匹配.形狀描述符是一種描述形狀語(yǔ)義信息和幾何信息的方法,有時(shí)候也被稱為某種算子,研究者通過(guò)選擇合適的形狀描述符,可以實(shí)現(xiàn)非剛性三維形狀的高效匹配.常用的形狀描述符一般包括4 類:基于形狀表面特征的描述符、基于形狀統(tǒng)計(jì)特征的描述符、基于形狀拓?fù)涞拿枋龇约盎谧V分析的形狀描述符,本文重點(diǎn)綜述了基于譜分析的形狀描述符.

第1 類形狀描述符致力于描述形狀表面的特征及其在全局歐氏變換下的不變性.尺度不變特征變換(scale invariant feature transform,簡(jiǎn)稱SIFT)描述符[14]是其中應(yīng)用最廣的描述符,SIFT 于1999 年由Lowe 等人提出,被用于檢測(cè)和描述圖像中的局部特征,并在2005 年由Mikolajczy 等人證明其具有很強(qiáng)的魯棒性[15].之后,許多研究者也在此研究的基礎(chǔ)上引入隱馬爾可夫模型、核判別分析及測(cè)地線圓環(huán)等方法對(duì)其進(jìn)行不斷改進(jìn),提高了SIFT的實(shí)時(shí)性及魯棒性[16?18].形狀上下文(shape context)[19]描述了形狀表面上圖像中的線條,同時(shí)存儲(chǔ)每個(gè)點(diǎn)相對(duì)其他點(diǎn)位置的分布,并給出形狀上點(diǎn)的局部上下文信息,在一定的圖像區(qū)域內(nèi)將點(diǎn)云分布轉(zhuǎn)化為二維自旋圖,執(zhí)行三維形狀的表面匹配.為了分析有特殊鉸鏈和關(guān)節(jié)的三維分子形狀,Feng 等人提出了一種基于節(jié)點(diǎn)感知的三維形狀描述符[20],該描述符由形狀邊界上任意點(diǎn)的局部形狀半徑變化的信息編碼定義,用于描述有關(guān)節(jié)的三維形狀.積分不變量(integral invariant)[21,22]描述符通過(guò)對(duì)稱組對(duì)原始形狀進(jìn)行重建,用積分不變量作為形狀的特征,該描述符可作為定義形狀之間其他距離的基礎(chǔ).梯度方向直方圖(mesh HOGs)[23]由離散網(wǎng)格上頂點(diǎn)的幾何特征定義,例如曲率、測(cè)地線積分等,該描述符描述了形狀上的紋理特征而非幾何特征.與此類似的還有Tombari等人提出的一種局部描述符——CSHOT 描述符[24],該描述符通過(guò)匹配形狀的特征點(diǎn)獲得點(diǎn)對(duì)點(diǎn)的對(duì)應(yīng),主要用于三維形狀表面匹配、目標(biāo)識(shí)別等.

第2 類形狀描述符基于對(duì)形狀統(tǒng)計(jì)特征的描述,主要描述形狀的全局屬性.Osada 等人[25]在2002 年提出了形狀分布(shape distribution,簡(jiǎn)稱SD)描述符,其算法步驟為:(1) 在形狀上選擇合適的歐式度量函數(shù),如D1 距離(測(cè)量形狀上某個(gè)中心點(diǎn)到其他任意點(diǎn)的距離)、D2 距離(測(cè)量形狀上任意兩點(diǎn)間的距離)以及D3 距離(測(cè)量形狀上任意3 點(diǎn)組成區(qū)域面積的平方根)等,圖1 為Osada 的文章中提到的5 種距離;(2) 計(jì)算形狀上所有采樣點(diǎn)對(duì)間度量函數(shù)的分布直方圖;(3) 將該直方圖作為形狀的線性形狀描述符,并用于形狀分析.該方法基于統(tǒng)計(jì)分析思想、易于理解且具有很強(qiáng)的普適性,然而SD 方法中的提到的5 種距離只適合描述剛性物體的屬性,當(dāng)物體發(fā)生非剛性變化時(shí),例如等距變換,其值會(huì)隨之變化.等距變換是指形狀保持曲面上任意兩點(diǎn)間曲線長(zhǎng)度不變的變換,例如一個(gè)人彎曲胳膊后,胳膊上任意兩點(diǎn)長(zhǎng)度不變,形狀發(fā)生等距變換后的不變性稱為等距不變性.基于上述研究,Mahmoudi 等人[26]使用基于D1 距離改進(jìn)的測(cè)地距離分布直方圖作為新的形狀描述符.測(cè)地距離是歐式空間中的直線段在黎曼流形上的推廣,具有等距不變性,測(cè)地距離定義了曲面上兩點(diǎn)間的最短距離[27].測(cè)地距離不僅具有局部最短性,還含有其他豐富的幾何信息,但當(dāng)兩點(diǎn)間的曲面部分發(fā)生缺失或者有縫隙時(shí),測(cè)地距離會(huì)因?yàn)槁?lián)通路徑不能通過(guò)而發(fā)生改變,對(duì)拓?fù)渥兓敯粜圆蛔?此后,其他的工作也對(duì)此進(jìn)行了改進(jìn),但始終無(wú)法克服測(cè)地距離對(duì)拓?fù)渥兓拿舾行訹28].基于形狀統(tǒng)計(jì)特征的形狀描述符繼承了統(tǒng)計(jì)學(xué)中統(tǒng)計(jì)量的穩(wěn)定性,在描述性狀特征時(shí)魯棒性較高,很適用于分子形狀比較(molecular shape comparison,簡(jiǎn)稱MSC)或者三維關(guān)節(jié)變形形狀.Liu 等人使用內(nèi)部距離形狀簽名(inner distance shape signature,簡(jiǎn)稱IDSS)描述了三維分子形狀,并計(jì)算了IDSS 直方圖之間的度量作為三維分子形狀間的相似度[29].在此基礎(chǔ)上,Liu 等人基于可見(jiàn)性圖提出一種新的內(nèi)積距離計(jì)算方法,計(jì)算了有關(guān)節(jié)的三維體模型的內(nèi)部距離,其對(duì)關(guān)節(jié)變形形狀發(fā)生拓?fù)渥兓敯?能夠很好地描述三維關(guān)節(jié)變形形狀[30].

Fig.1 Five distances defined in shape distribution圖1 形狀分布中定義的5 種距離

第3 類描述符基于對(duì)形狀拓?fù)浣Y(jié)構(gòu)的特征提取,該類描述符將三維形狀匹配問(wèn)題轉(zhuǎn)換成其拓?fù)浣Y(jié)構(gòu)匹配問(wèn)題,應(yīng)用兩個(gè)形狀拓?fù)浣Y(jié)構(gòu)的匹配結(jié)果作為形狀的匹配結(jié)果.三維形狀的拓?fù)浣Y(jié)構(gòu)精確地描述了形狀的全局和局部幾何形態(tài)特征,并且保留了形狀的層次結(jié)構(gòu).具有代表性的兩類描述符分別是基于Reeb 圖理論的描述符和基于形狀的骨架線理論的描述符,圖2 為兩個(gè)不同形狀的Reeb 圖和骨架線圖示.

Fig.2 Diagram of Reeb graph and skeleton with different shapes圖2 不同形狀Reeb 圖與骨架線圖示

Reeb 在1946 年基于形狀的拓?fù)浣Y(jié)構(gòu)提出了Reeb 圖的概念,其具體步驟為:首先,在三維形狀的頂點(diǎn)上定義連續(xù)光滑函數(shù)f:M→R;其次,根據(jù)形狀的頂點(diǎn)坐標(biāo)計(jì)算頂點(diǎn)處的函數(shù)值,并將頂點(diǎn)進(jìn)行分類;最后,根據(jù)頂點(diǎn)分類結(jié)果將形狀M映射為Reeb 圖R,函數(shù)值相同且位于同一連通區(qū)域的頂點(diǎn)在Reeb 圖中映射為一個(gè)節(jié)點(diǎn).Reeb 圖能夠很好地刻畫(huà)形狀的拓?fù)浣Y(jié)構(gòu),且能起到降維的作用.定義合適的函數(shù)f是Reeb 圖算法的關(guān)鍵,常用的函數(shù)f有高度函數(shù)和Morse 函數(shù).Shinagawa 等人[31]采用高度函數(shù)、權(quán)重函數(shù)和形狀上孔的數(shù)量等先驗(yàn)知識(shí)自動(dòng)地生成三維形狀的Reeb 圖.Hilaga 等人[32]通過(guò)測(cè)地距離、測(cè)地線定義了Morse 函數(shù),并基于此提出了多分辨率Reeb算法(MRG),Bespalov 等人[33]在此研究上改進(jìn)了MRG 算法,并用于CAD 模型匹配.Biaso 等人[34]基于Morse 函數(shù),提出了擴(kuò)展Reeb 圖算法(extend reeb graph,簡(jiǎn)稱ERG),該算法刻畫(huà)了形狀上臨界點(diǎn)之間的拓?fù)潢P(guān)系,但該算法對(duì)形狀發(fā)生拓?fù)渥兓瘯r(shí)魯棒性較差.Tierny J 等人[35]基于特征點(diǎn)的思想構(gòu)造Reeb 圖,其通過(guò)特征提取算法提取形狀的特征點(diǎn),并通過(guò)圖構(gòu)造方法生成Reeb 圖,并應(yīng)用Reeb 圖進(jìn)行部分形狀檢索.骨架線,也被稱為三維形狀的中軸,是刻畫(huà)三維形狀拓?fù)浣Y(jié)構(gòu)的另一個(gè)重要方法,不但能用線段很好地描述模型的結(jié)構(gòu)信息,而且能高效地保存形狀,提高形狀空間存儲(chǔ)率和形狀檢索率.Sundar 等人[36]使用拓?fù)浼?xì)化算法提取了形狀的骨架線.Cao 等人[37]提出了一種基于拉普拉斯壓縮的骨架線提取算法,該算法可快速提取點(diǎn)云模型的骨架線.Sfikas 等人[38]基于形狀的拓?fù)湫畔⒑凸残螏缀翁卣?提出了一種非剛性三維形狀檢索方法,該算法具有穩(wěn)健又高效的檢索精度和計(jì)算速度.

以上3 類形狀描述符大多應(yīng)用于描述剛性形狀,對(duì)于形狀發(fā)生等距、拓?fù)涞确莿傂宰兓霍敯?因此不適用于非剛性三維形狀匹配.近年來(lái),應(yīng)用基于譜分析的形狀描述符進(jìn)行非剛性三維形狀匹配成為了一個(gè)新的研究熱點(diǎn),部分研究工作[39?44]表明,基于譜分析的形狀描述符對(duì)非剛性形狀的拓?fù)湓肼曈休^好的魯棒性,同時(shí)具有等距不變性.譜分析源于黎曼流形表面上的拉普拉斯-貝爾塔拉米(Laplace-Beltrami,簡(jiǎn)稱LB)算子[45,46],LB 算子是一個(gè)著名的內(nèi)蘊(yùn)算子,它被分解為特征值和特征向量的組合,研究者常常將LB 算子的特征值稱為“譜”.為了研究方便,研究者將三維非剛性形狀定義為黎曼流形,通過(guò)LB 算子描述形狀特征,將形狀用“譜”的方法表示.這種在譜空間中進(jìn)行形狀分析的方法被稱為譜分析[47].譜分析源于形狀的內(nèi)蘊(yùn)屬性,該方法提供了一種自然的方式進(jìn)行非剛性三維形狀匹配.

譜分析包括譜形狀描述符及誘導(dǎo)出的譜距離,常用的譜形狀描述符包括形狀DNA(shapeDNA)[48]、全局點(diǎn)簽名(global point signature,簡(jiǎn)稱GPS)[49]、熱核簽名(heat kernel signature,簡(jiǎn)稱HKS)[50]、雙調(diào)合簽名(biharmonic signature,簡(jiǎn)稱BS)[51]、波動(dòng)核簽名(wave kernel signature,簡(jiǎn)稱WKS)[52]等.在一個(gè)形狀表面上,由譜形狀描述符誘導(dǎo)出的譜距離[53]是一種較好的度量結(jié)構(gòu),具有等距不變性以及對(duì)拓?fù)渥兓聂敯粜?常用的譜距離包括交換時(shí)間距離(commute-time distance,簡(jiǎn)稱CD)[54]、熱擴(kuò)散距離(heat diffusion distance,簡(jiǎn)稱HDD)[55]、雙調(diào)和距離(biharmonic distance,簡(jiǎn)稱BD)[56]及波核距離(wave kernel distance,簡(jiǎn)稱WKD)[57].使用譜形狀描述符進(jìn)行三維非剛性形狀匹配時(shí),需要選擇數(shù)量一致的采樣點(diǎn),為了避免非剛性形狀匹配時(shí)采樣點(diǎn)的選擇問(wèn)題,基于SD 方法,Bronstein 等人提出使用譜距離分布函數(shù)作為一種新的形狀描述符[58,59].譜距離分布函數(shù)將一對(duì)形狀的相似性轉(zhuǎn)化為其形狀上譜距離分布函數(shù)的相似性,同時(shí)兼具SD 方法和譜形狀描述符的優(yōu)點(diǎn),能描述形狀的全局統(tǒng)計(jì)屬性.Cao 等人也應(yīng)用譜距離分布函數(shù)進(jìn)行了三維非剛性形狀分類,并比較了幾種譜距離分布函數(shù)的性能[60].因此,基于現(xiàn)有研究方法,本文對(duì)基于譜分析的譜形狀描述符和譜距離分布函數(shù)用于三維非剛性形狀匹配進(jìn)行了詳細(xì)的研究.

本文第1 節(jié)給出基于譜分析的三維非剛性形狀匹配的一般框架、LB 算子的詳細(xì)介紹及離散化計(jì)算.第2節(jié)首先詳細(xì)介紹了幾種譜形狀描述符:shapeDNA,GPS,HKS,BS,WKS,給出了譜形狀描述符的推導(dǎo)過(guò)程及其在離散網(wǎng)格上的計(jì)算方法;其次,總結(jié)與分析了這幾種形狀描述符在非剛性三維形狀匹配中的表現(xiàn)和特性.第3 節(jié)給出譜距離的定義和形式化表達(dá),同時(shí)給出不同譜距離在三角網(wǎng)格上的離散計(jì)算方法以及譜距離分布函數(shù)的計(jì)算方式.第4 節(jié)是實(shí)驗(yàn)驗(yàn)證部分,實(shí)驗(yàn)中使用不同譜形狀描述符和譜距離分布函數(shù)進(jìn)行非剛性三維形狀匹配,觀察不同譜形狀描述符參數(shù)變化對(duì)匹配效果的影響,同時(shí)驗(yàn)證了第2 節(jié)提出的預(yù)測(cè)的有效性,并做出合理分析.

現(xiàn)有的形狀描述符研究工作[9,61?66]對(duì)于譜分析的總結(jié)和介紹相對(duì)較少,大多數(shù)研究工作只是從理論上研究了譜形狀描述符或譜距離分布函數(shù),很少有文章系統(tǒng)地對(duì)于兩類形狀描述符進(jìn)行理論分析和實(shí)驗(yàn)驗(yàn)證.本文基于現(xiàn)有的研究成果,彌補(bǔ)了表1 中工作的不足,主要貢獻(xiàn)如下.

(1) 提供應(yīng)用基于譜分析的形狀描述符進(jìn)行三維非剛性形狀匹配的框架,并給出該方法的原理分析和數(shù)值計(jì)算;

(2) 系統(tǒng)地對(duì)比不同形狀描述符的數(shù)學(xué)定義及算法特性;從計(jì)算精度、魯棒性、時(shí)間復(fù)雜度等多方面比較其各自優(yōu)缺點(diǎn);并且在非剛性三維形狀標(biāo)準(zhǔn)庫(kù)中進(jìn)行了兩類描述符的實(shí)驗(yàn)比較;

(3) 給出不同譜形狀描述符和譜距離分布函數(shù)的最優(yōu)使用場(chǎng)景,討論了譜分析應(yīng)用于非剛性三維形狀匹配中存在的問(wèn)題以及未來(lái)的發(fā)展趨勢(shì),對(duì)譜分析進(jìn)行推廣,為研究者選擇基于譜分析的形狀描述符提供參考.

Table 1 Several studies about summary and analysis of spectral analysis表1 譜分析的主要文章綜述與分析

1 基于譜分析的非剛性三維形狀匹配框架

本文首先對(duì)基于譜分析的非剛性三維形狀匹配的框架進(jìn)行介紹.在數(shù)學(xué)中,譜分析是一個(gè)廣義的方法,它將一個(gè)矩陣的特征向量和特征值理論擴(kuò)展到一個(gè)含有更廣泛運(yùn)算符結(jié)構(gòu)的譜空間中.在形狀匹配中,譜分析是指將形狀上的LB 算子離散化表示為L(zhǎng)B 矩陣,對(duì)LB 矩陣進(jìn)行譜分解得到LB 算子的特征向量和特征值.利用LB算子的特征值和特征向量,可以定義出不同的譜形狀描述符及其誘導(dǎo)出的不同的譜距離.通過(guò)計(jì)算一對(duì)形狀上的譜形狀描述符離散值或譜距離分布函數(shù)值,研究者可以對(duì)比一對(duì)形狀的局部或整體對(duì)應(yīng)關(guān)系,得到一對(duì)形狀的非剛性匹配結(jié)果.本節(jié)首先給出非剛性匹配譜分析的一般框架,其次給出LB 算子的定義及離散化計(jì)算及譜分解形式.

1.1 非剛性匹配譜分析框架

LB 算子的特征值與特征向量常常被用來(lái)描述模型的形狀特性.利用譜形狀描述符和譜距離可以很好地進(jìn)行非剛性形狀匹配,本文給出基于譜分析的非剛性三維形狀匹配的一般框架如圖3 所示.三維非剛性形狀匹配的具體流程如下.

· 第1 步:輸入一對(duì)3D 非剛性形狀(點(diǎn)云模型、三角片模型等).

· 第2 步:計(jì)算形狀上每個(gè)采樣點(diǎn)的LB 算子值,并將其進(jìn)行譜分解,由LB 算子特征值和特征向量定義不同的形狀描述符,譜形狀描述符可以誘導(dǎo)出譜距離.

· 第3 步:對(duì)譜形狀描述符和譜距離分布函數(shù)進(jìn)行離散化求值,得到譜形狀描述符矩陣和譜距離分布函數(shù)矩陣.

· 第4 步:應(yīng)用方差或其他度量方法計(jì)算一對(duì)形狀間譜形狀描述符或譜距離分布函數(shù)數(shù)值,并選擇合適的度量函數(shù)進(jìn)行形狀匹配,形狀匹配結(jié)果可以應(yīng)用于形狀檢索、形狀分類、形狀對(duì)應(yīng)等.

整個(gè)匹配過(guò)程中,形狀描述符的選擇是重要步驟,通過(guò)選擇合適的形狀描述符,研究者就可找到一對(duì)形狀間的局部或整體匹配關(guān)系.

Fig.3 Non-rigid shape matching framework using spectral analysis圖3 非剛性形狀匹配譜分析框架

1.2 拉普拉斯-貝爾塔拉米算子

作為譜分析中的重要算子,拉普拉斯-貝爾塔拉米算子是Laplace 算子黎曼流形上的推廣.Laplace 算子是歐氏空間中作用于光滑函數(shù)f的二階微分算子,描述為f的梯度的散度[67].任意二階可微函數(shù)的Laplace 算子定義為

根據(jù)黎曼流形梯度和散度的定義,若g為流形上的度量張量,G為矩陣{gij}的行列式,則函數(shù)f的LB 算子在局部坐標(biāo)系中定義為[68]

在非剛性三維形狀匹配中,研究者需要計(jì)算離散網(wǎng)格上每個(gè)頂點(diǎn)的LB 算子值.網(wǎng)格上某頂點(diǎn)vi周圍三角形面片示意圖如圖4 所示.

在離散數(shù)學(xué)中,有限維離散LB 算子通常稱為離散LB 矩陣,是對(duì)連續(xù)LB 算子的一種逼近.在頂點(diǎn)數(shù)為n的三角網(wǎng)格上定義函數(shù)f,則該函數(shù)在網(wǎng)格頂點(diǎn)vi處的離散LB 算子可以定義為[69]

等式(3)中,當(dāng)計(jì)算點(diǎn)vi的LB 算子時(shí),考慮網(wǎng)格中的所有頂點(diǎn).對(duì)于網(wǎng)格上某頂點(diǎn)vi,若僅對(duì)其周圍三角形面片能量求和,然后計(jì)算其偏導(dǎo)數(shù)并合并同類項(xiàng),得到該點(diǎn)對(duì)應(yīng)離散LB 算子的值:

其中,αj和βj分別表示連接vi和vj的邊eij兩側(cè)的對(duì)角,Neigh(vi)表示與頂點(diǎn)vi相鄰的頂點(diǎn)的集合.在完備有界的緊致流形上定義的LB 算子,具有對(duì)稱性和非負(fù)性.若將LB 算子進(jìn)行譜分解(或稱特征分解)為特征值和特征向量的矩陣乘積形式,可得到流形上的LB 譜,即LB 算子的特征值和特征向量表達(dá)式:

λ0≥λ1≥…≥λn是LB 算子的非負(fù)特征值序列,λi是第i個(gè)特征值,φi是第i個(gè)特征值對(duì)應(yīng)的特征向量.如果在封閉區(qū)域使用Neumann 邊界條件[70],第1 個(gè)特征值為0,一般將最小的非零特征值定義為λ1.由于LB 算子是半正定算子,所以λn≥0.LB 算子可以解析地計(jì)算一些形狀幾何量(例如矩形、圓柱、圓盤或球面等).如果一些形狀,例如動(dòng)物、植物等,變換其形體姿態(tài),例如在其關(guān)節(jié)處只有輕微的拉伸,這種情況被稱為近似等距變化,LB 算子同樣對(duì)近似等距變化魯棒.

Fig.4 Diagram of a vertex vion a triangular mesh圖4 網(wǎng)格上某頂點(diǎn)vi 的三角面片圖示

2 譜形狀描述符

由LB 算子的特征值和特征向量以定義不同的譜形狀描述符,例如上文提到的shapeDNA,GPS,HKS,BS 和WKS,本節(jié)對(duì)幾種譜形狀描述符的詳細(xì)定義以及離散計(jì)算方法進(jìn)行介紹.

2.1 ShapeDNA

ShapeDNA 是Reuter 等人在2005 年通過(guò)提取黎曼流形表面的LB 算子的特征值序列進(jìn)行非剛性形狀檢索,它的主要優(yōu)點(diǎn)是易于表示形狀,計(jì)算簡(jiǎn)單[48,71].ShapeDNA 是全局描述符,不能用于局部形狀分析.Reuter 等人對(duì)LB 算子特征值序列的數(shù)目進(jìn)行了研究,當(dāng)特征值序列數(shù)目等于500 時(shí)算法收斂,在工程應(yīng)用中,數(shù)目取值一般為50～100.基于LB 算子的定義,形狀M上某點(diǎn)x的shapeDNAx可被計(jì)算為

g是被定義在形狀M上的度量,n為特征值序列的編號(hào),shapeDNA 為非負(fù)值.ShapeDNA 很好地描述了形狀的內(nèi)蘊(yùn)屬性,不依賴形狀的參數(shù)化表示.形狀上,所有采樣點(diǎn)的shapeDNA 組成了shapeDNA 矩陣,確定n的取值后,可以唯一確定該形狀的shapeDNA 矩陣,但相似形狀的shapeDNA 矩陣非常近似,因此,其對(duì)于相似形狀的區(qū)分度較差.

2.2 全局點(diǎn)簽名算子

由于同類相似形狀的shapeDNA 值很近似,為了提高shapeDNA 對(duì)同類形狀的區(qū)分度,Rustamov 等人在其基礎(chǔ)上定義了一種新的譜形狀描述符——全局點(diǎn)簽名.如果將形狀內(nèi)在的對(duì)稱性轉(zhuǎn)化為特征空間,將非剛性形狀的特征空間映射到一個(gè)無(wú)限維空間——全局點(diǎn)嵌入域(global point signature embedding dominant),那么在該無(wú)限維空間中,可以定義M上的每點(diǎn)x的GPS(x)可定義為

和shapeDNAx一樣,GPS(x)描述形狀的全局特征.形狀上每個(gè)點(diǎn)的GPS(x)都表示一個(gè)向量,一個(gè)形狀上所有采樣點(diǎn)的GPSM表示為一個(gè)m×n的矩陣,其中,m為形狀上采樣點(diǎn)的數(shù)量,n為L(zhǎng)B 算子特征值數(shù)量,如等式(8)所示.

由上述定義可知,一個(gè)形狀的GPS 矩陣維數(shù)很高.研究者需要根據(jù)應(yīng)用選擇合適的特征值數(shù)量n,以避免較高的計(jì)算量.

2.3 熱核簽名算子

根據(jù)熱擴(kuò)散理論,假定在形狀上每點(diǎn)有初始熱源μ0(x),并隨時(shí)間t在形狀M表面上進(jìn)行熱量擴(kuò)散.在一定時(shí)刻,形狀表面上達(dá)到熱平衡狀態(tài).在這個(gè)過(guò)程中,定義熱核ht(x,y)為t時(shí)刻從x點(diǎn)到y(tǒng)點(diǎn)轉(zhuǎn)移所需的熱量,表示熱量從一個(gè)點(diǎn)傳遞到另一個(gè)點(diǎn)的可能性.等式(9)為形狀上的熱擴(kuò)散偏微分方程,描述了形狀表面上溫度隨時(shí)間變化狀態(tài).

其中,μ(x,t)是形狀M上時(shí)間t對(duì)應(yīng)的熱量分布函數(shù),Δ是LB 算子.該方程的解為

同樣,對(duì)熱核進(jìn)行譜分解:

熱核能完全表征一個(gè)形狀表面的幾何信息,如果將熱核限制在時(shí)間域內(nèi),可得到一個(gè)簡(jiǎn)潔的形狀描述符——熱核簽名:

HKS 具有多尺度特性,能通過(guò)調(diào)節(jié)時(shí)間t改變其描述的是形狀的局部特征或者全局特征.形狀M在不同時(shí)間尺度下HKS 值分布可表示為

其中,每一列代表形狀在不同時(shí)間t下的HKS 值分布.圖5 給出了在較小t時(shí)刻下,3 個(gè)形狀的熱核簽名示意圖.可以從圖中看出,當(dāng)t很小時(shí),熱核簽名描述了形狀的局部特征[44].

Fig.5 Diagram of heat kernel function for a small fixed t on the hand,Homer,and trim-star圖5 較小t 值下手掌、人偶及五角星的熱核簽名圖示

基于HKS,Bronstein 等人對(duì)HKS 進(jìn)行改進(jìn),提出了具有比例不變性熱核簽名(scale-invariant heat kernel signature,簡(jiǎn)稱SIHKS)[72].該描述符采用對(duì)數(shù)采樣以及傅里葉變換,消除了一對(duì)形狀縮放前后的縮放倍數(shù),在原有的HKS 上增加了縮放比例不變的特性.其具體過(guò)程如下.

· 首先,設(shè)縮放系數(shù)為β,對(duì)于形狀M,其發(fā)生縮放后的形狀為M′=βM.參照HKS 定義,縮放后的特征值和特征向量滿足λ′=β2λ,φ′=βφ,則縮放后,形狀M′上某點(diǎn)x處HKS(x)的譜分解形式可寫為

· 最后,對(duì)h取對(duì)數(shù),消除β2的影響:,則.接著對(duì)hτ˙進(jìn)行傅里葉變換,使時(shí)域的平移變換轉(zhuǎn)移到復(fù)數(shù)域:

對(duì)等式(15)兩邊取傅里葉模后得到等式(16):

文獻(xiàn)[72]從理論上證明了形狀縮放前后的的熱核簽名僅有時(shí)間軸上的偏移,SIHKS 具有尺度變換不變性.圖6 為原始馬和縮放變化后,馬的縮放不變熱核簽名圖示.

Fig.6 Scale-invariant heat kernel signature for the initial and scaled shape圖6 原始形狀和縮放變化后形狀的縮放不變熱核簽名圖示

2.4 雙調(diào)和算子

為了同時(shí)兼顧形狀的局部特性和全局特性,在HKS 和GPS 的基礎(chǔ)上,將LB 算子的特征值和特征向量進(jìn)行另一種組合,在形狀M上的某點(diǎn)x定義另一種譜形狀描述符,即雙調(diào)和簽名:

與GPS 類似,形狀上的每個(gè)點(diǎn)的BS(x)都表示一個(gè)n維向量.一個(gè)形狀的BSM表示為一個(gè)m×n的矩陣,其中,m為形狀上點(diǎn)的數(shù)量,n為L(zhǎng)B 算子譜分解數(shù)量.

BS 通過(guò)正則化拉普拉斯算子的特征值,很好地平衡了形狀的局部特征和全局特征.BS 算子來(lái)源于雙調(diào)和微分方程,該算子在形式上與GPS 非常相像,但是性能卻有很大提升,分母由LB 算子的特征值的平方根變?yōu)長(zhǎng)B算子的特征值,大大加快了描述符的歸一化.與GPS 一樣,當(dāng)我們選用BS 表示形狀時(shí),需要根據(jù)應(yīng)用場(chǎng)景選擇合適的譜分解數(shù)量n,以避免較高的計(jì)算量.

2.5 波核簽名

對(duì)于形狀上的每個(gè)點(diǎn),通過(guò)測(cè)量不同能量級(jí)的量子粒子的平均概率分布,文獻(xiàn)[52]定義了一種新的形狀描述符——波核簽名,形狀表面上的量子粒子的演化由波函數(shù)控制.通過(guò)求解Schr?dinger 方程可得:

波函數(shù)的形式表達(dá)類似于熱核函數(shù),但意義卻截然不同:熱核函數(shù)表示是熱量耗散,波動(dòng)函數(shù)表示了能量的振蕩.其中,x是形狀上任意一點(diǎn),Δ是LB 算子,i 是虛數(shù),LB 算子和i 的乘積確保能量經(jīng)過(guò)不同頻率振蕩后不會(huì)衰減.通過(guò)及譜分解理論可得,波函數(shù)φ(x,t)的譜分解形式為

其中,fk(t)為t時(shí)刻粒子的第k個(gè)頻率,φk(x)為第k個(gè)頻率對(duì)應(yīng)的特征向量,可計(jì)算如下:

當(dāng)t=0 時(shí),表示期望值為E,頻率λk的概率分布.Laplace 譜沒(méi)有重復(fù)值,結(jié)合公式(20)及公式(21)可得:

|φ(x,t)|2為點(diǎn)x處粒子的概率分布.由于時(shí)間參數(shù)t對(duì)概率分布沒(méi)有直接影響,若只考慮能量參數(shù),將WKS 算子定義為點(diǎn)x處能量為E的一個(gè)粒子可被測(cè)量到平均概率:

由上述可知,WKS 采用帶通濾波器,因此可以很好地分離形狀,如圖7 所示.

公式(24)中,WKS 的表達(dá)式具有一般性,可以通過(guò)選擇不同能量概率分布函數(shù)fE(λk)得到不同的WKS.選擇對(duì)數(shù)正態(tài)分布函數(shù)作為能量概率分布函數(shù),則WKS 可寫為

eN為能量規(guī)模參數(shù),eN=log(E),λk為L(zhǎng)B 算子第k個(gè)特征向量,σ為正態(tài)分布的方差,Ce為正則化WKS 函數(shù).在實(shí)驗(yàn)中,本文采用與文獻(xiàn)[52]一樣的參數(shù)設(shè)置,則形狀的WKS 在不同能量規(guī)模下分布為

其中,WKSM(eN)形狀第m個(gè)頂點(diǎn)在能量規(guī)模為N下的WKS 值,每列代表不同能量規(guī)模下形狀M每點(diǎn)的WKS值.當(dāng)我們選用WKS 表示形狀時(shí),需要根據(jù)應(yīng)用選擇合適的能量規(guī)模eN,以突出WKS 的優(yōu)勢(shì).

Fig.7 Wave kernel signature on a dog圖7 狗的波動(dòng)核簽名圖示

2.6 譜形狀描述符比較

在譜形狀描述符中,shapeDNA 的研究時(shí)間最早,因此整體性性能相對(duì)較差,但其為之后譜形狀描述符的發(fā)展奠定了基礎(chǔ).每點(diǎn)的shapeDNA 由LB 算子的前n個(gè)特征值確定,忽略了LB 算子的特征向量的作用,shapeDNA最大的優(yōu)點(diǎn)是易于理解,計(jì)算簡(jiǎn)單.但對(duì)局部特征的描述能力較弱,不適合相似形狀的快速區(qū)分.

GPS 由LB 算子的前n個(gè)特征向量比上特征值得到.從定義上看,GPS 更加注重低頻相關(guān)的信息,但對(duì)于形狀發(fā)生非剛性形變(變化較小)時(shí),形狀上一點(diǎn)的GPS 值也會(huì)完全改變,增加額外的算法復(fù)雜度,性能并不好.總體來(lái)說(shuō),GPS 能夠很好地反映形狀上所有采樣點(diǎn)的上下文信息,但對(duì)局部特征的描述能力較弱,適合非剛性形狀的粗糙匹配,不適用于局部匹配.

HKS 定義了點(diǎn)x處的局部和全局屬性.由于形狀上的熱擴(kuò)散本質(zhì)近似布朗運(yùn)動(dòng),因此有較強(qiáng)的魯棒性以弱化局部噪聲的影響.作為低通濾波器的集合,HKS 主要由低頻傳輸,能夠很好地描述形狀的局部幾何信息.當(dāng)時(shí)間t比較短時(shí),形狀上每個(gè)點(diǎn)的HKS 值與該點(diǎn)的高斯曲率直接相關(guān),具有很強(qiáng)的信息存儲(chǔ)性.但HKS 過(guò)于強(qiáng)調(diào)低頻信息,會(huì)過(guò)濾掉一些高頻率信息,損害精確定位特征的能力.因此相比較其他3 種算子,HKS 表征形狀時(shí)不能很好地分離不同頻率區(qū)域.此外,由于HKS 對(duì)時(shí)間參數(shù)敏感,所以在某個(gè)時(shí)刻下,不能同時(shí)表征形狀的局部屬性和全局屬性.SIHKS 擁有HKS 所有的優(yōu)點(diǎn),還具有縮放不變性,但是其理解相對(duì)較難且計(jì)算復(fù)雜.

BS 平衡了大尺度距離(反映全局特性)和小尺度距離(反映局部特性),具有多尺度特性.它不依賴于時(shí)間參數(shù),克服了HKS 依賴時(shí)間參數(shù)重的缺點(diǎn),同時(shí)克服了GPS 沒(méi)有多尺度特性的缺點(diǎn).然而,由于BS 具有調(diào)和性質(zhì),單獨(dú)表征形狀的局部及全局屬性性能較差.

WKS 同樣對(duì)時(shí)間參數(shù)自由,其最大優(yōu)點(diǎn)是采用帶通濾波器能清楚地分離形狀上的不同頻率集合,且允許訪問(wèn)高頻率信息,從而增加算子的精確匹配能力.此外,WKS 通過(guò)選擇不同的能量規(guī)模而具有多尺度特性,若選擇能量級(jí)別較高的量子粒子,波長(zhǎng)越短,其分布越靠近形狀上的點(diǎn),此時(shí)反映形狀的局部特性;反之,能量級(jí)別較低的量子粒子反映形狀的全局特性.所以在匹配時(shí),研究者應(yīng)該根據(jù)應(yīng)用場(chǎng)景選擇一個(gè)合適的能量規(guī)模.

幾種譜形狀描述符在不同變換下魯棒性等級(jí)見(jiàn)表2.

Table 2 Robustness levels of several spectral shape descriptors under different transformations表2 幾種譜形狀描述符在不同變換下魯棒性等級(jí)

3 譜距離分布函數(shù)

譜距離(shape spectral distance distribution)源于譜分析,譜距離由形狀表面上定義的譜形狀描述符誘導(dǎo)得到,包括熱擴(kuò)散距離、交換時(shí)間距離、雙調(diào)和距離等.若在形狀M上定義度量空間,則由譜形狀描述符誘導(dǎo)出的譜距離可定義為[62]

其中,φ(λi)為不同譜形狀描述符使用的濾波器.在三角面片上,譜距離的離散化形式為[63]

其中,p,q為三角面片上的頂點(diǎn),分別代表頂點(diǎn)p和q上LB 算子第i個(gè)特征向量.前文中提到的另一類基于譜分析的形狀描述符就是譜距離分布函數(shù),基于SD 方法的研究,Brostein 等人通過(guò)統(tǒng)計(jì)形狀上任意兩點(diǎn)間的譜距離,構(gòu)造了譜距離分布函數(shù)最為一種新的形狀描述符.假定形狀M上任意兩點(diǎn)的譜距離為d(x,y),若δ是距離閾值,μ是定義在M中的范數(shù)矩陣,χ是指示函數(shù),則譜距離頻率直方圖可以計(jì)算為

在概率論與統(tǒng)計(jì)學(xué)中,概率密度函數(shù)(probability density function,簡(jiǎn)稱PDF)是一個(gè)實(shí)值隨機(jī)變量,用于描述多隨機(jī)變量的分布,再由公式(29)可得譜距離分布函數(shù)可計(jì)算為

譜距離分布函數(shù)作為一種線性形狀描述符,繼承了譜距離的特征,具有以下特點(diǎn).

(1) 采樣不變性:對(duì)于形狀M,如果對(duì)M的三角網(wǎng)格模型的頂點(diǎn)進(jìn)行采樣,包括上采樣和下采樣,則采樣前后的形狀的譜距離分布函數(shù)保持不變.

(2) 等距不變性:由于LB 算子是形狀的內(nèi)蘊(yùn)算子,所以等距形狀中任意兩點(diǎn)的譜距離具有等距不變形.因此,等距形變前后,形狀的譜距離分布函數(shù)理論上保持不變.但是在下文中,我們給出了不同譜距離的譜分解計(jì)算形式,在實(shí)際應(yīng)用中,一般取前100 個(gè)特征值和特征向量.因此在實(shí)際的實(shí)驗(yàn)中,等距形狀的譜距離分布函數(shù)與原始形狀的譜距離分布函數(shù)值相似.

(3) 拓?fù)漪敯粜?相對(duì)測(cè)地距離分布,譜距離分布對(duì)拓?fù)渥兓拿舾行暂^低,譜距離分布函數(shù)具有較強(qiáng)的拓?fù)漪敯粜?

(4) 無(wú)需預(yù)處理:相對(duì)于譜形狀描述符,應(yīng)用譜距離分布進(jìn)行三維非剛性形狀匹配時(shí),不需要尋找數(shù)量相同的采樣點(diǎn),也不需要配準(zhǔn)采樣點(diǎn).

下文就詳細(xì)對(duì)這4 種譜距離進(jìn)行介紹.

3.1 交換時(shí)間距離

根據(jù)第2.3 節(jié),在GPS 域中的內(nèi)積可定義交換時(shí)間距離:

G(x,y)是兩個(gè)無(wú)限維向量的內(nèi)積,交換時(shí)間距離可寫為

交換時(shí)間距離反映了連接一對(duì)點(diǎn)之間隨機(jī)游走的平均時(shí)間.通過(guò)譜分解,交換時(shí)間距離可以表達(dá)為

其離散化形式為

熱擴(kuò)散距離和交換時(shí)間距離的關(guān)系為

熱擴(kuò)散距離反映了形狀表面上兩個(gè)點(diǎn)在時(shí)間t內(nèi)的路徑連通性,而交換時(shí)間距離是一對(duì)點(diǎn)之間在平均時(shí)間t內(nèi)隨機(jī)游走的擴(kuò)散長(zhǎng)度之和.

3.2 熱擴(kuò)散距離

熱擴(kuò)散距離由擴(kuò)散核導(dǎo)出,并應(yīng)用于降維和數(shù)據(jù)參數(shù)化等問(wèn)題.擴(kuò)散距離描述了形狀M上點(diǎn)x與點(diǎn)y之間在時(shí)刻t時(shí)的連通率.將形狀M上的隨機(jī)運(yùn)動(dòng)看作是布朗運(yùn)動(dòng),在這種情況下,擴(kuò)散距離是對(duì)形狀M上時(shí)間t時(shí)兩點(diǎn)間的布朗運(yùn)動(dòng)的平均,更直觀上的理解為兩個(gè)熱核之間的信息交互.所以形狀上的兩點(diǎn)x和y之間的擴(kuò)散距離可以由下面的等式定義[39,51,73].

根據(jù)熱核的譜分解形式以及熱擴(kuò)散理論,熱擴(kuò)散距離(也稱熱核距離)表示為

為了不失一般性,特征值從1 開(kāi)始,離散化形式為

熱擴(kuò)散距離反映了擴(kuò)散時(shí)間t內(nèi)兩點(diǎn)間的熱流連通性.由于該距離是定義在形狀表面的距離,所以是一個(gè)內(nèi)蘊(yùn)距離,當(dāng)擴(kuò)散時(shí)間t的取值很小時(shí),此時(shí)熱量擴(kuò)散范圍較小,該距離只能描述形狀的局部特性;當(dāng)t的取值較大時(shí),該距離可以描述形狀的全局屬性,最后熱量擴(kuò)散直至達(dá)到熱平衡狀態(tài).但t取值并不是越大越好,合適的t取值[60]為1/λj,λj為第LB 算子的第1 個(gè)非零特征值.

3.3 雙調(diào)和距離

類似GPS 映射,雙調(diào)和映射定義了一個(gè)無(wú)限維的雙調(diào)和空間.

雙調(diào)和域中的內(nèi)積可定義雙調(diào)和距離[40]:

B(x,y)是兩個(gè)無(wú)限維向量的內(nèi)積,雙調(diào)和距離可表示為

通過(guò)譜分解,雙調(diào)和距離可寫為

離散形式可寫為

3.4 波核距離

文獻(xiàn)[66]用L2范式定義波核距離,類似于熱核距離,波核距離的譜分解形式為

離散化形式為

4 實(shí)驗(yàn)與分析

為了對(duì)幾種譜形狀描述符和譜距離分布函數(shù)進(jìn)行對(duì)比,本文在64 位32G 內(nèi)存,win10 系統(tǒng)的Matlab2015 上進(jìn)行了實(shí)驗(yàn)上進(jìn)行了實(shí)驗(yàn)(注:由于shapeDNA 最早被研究,性能較差,因此在本文不加入比較).評(píng)估這種方法所使用的是TOSCA 2010(tools for surface comparison and analysis)數(shù)據(jù)集(高分辨率,http://tosca.cs.technion.ac.il/data/toscahires-mat.zip)[74]、SHREC 2011 數(shù)據(jù)集(魯棒性,http://tosca.cs.technion.ac.il/book/shrec_robustness2010.html)[75]和 SHREC 2015 數(shù)據(jù)集(標(biāo)準(zhǔn)型,http://www.cs.cf.ac.uk/shaperetrieval/shrec15/SHREC15.zip).TOSCA 2010 數(shù)據(jù)集為非剛性形變的形狀匹配提供了大量高清三維形狀,圖8 為部分TOS CA2010 庫(kù)中形狀.TOSCA 2010 數(shù)據(jù)庫(kù)共包含80 個(gè)對(duì)象,包括11 只貓、9 只狗、3 只狼、8 匹馬、6 人馬、4 只大猩猩、12 個(gè)女性人物、2 個(gè)不同的男性形象,典型的頂點(diǎn)計(jì)數(shù)大約是50 000,數(shù)據(jù)庫(kù)適用于非剛性形狀分析.SHREC 2011 包含13 類形狀的的各種變化形狀,變化分為12 類,包括等距變化及在等距變化上加入洞、縮放、噪聲、下采樣等變化,每種變化共有5 個(gè)強(qiáng)度,圖9 為部分SHREC 2011 庫(kù)中形狀.

Fig.8 Part of the shapes of TOSCA 2010 database圖8 TOSCA 2010 數(shù)據(jù)庫(kù)中的部分形狀

Fig.9 Part of the shapes of SHREC 2011 database圖9 SHREC 2011 數(shù)據(jù)庫(kù)中的部分形狀

SHREC 2015 數(shù)據(jù)庫(kù)由SHREC 2011[76]和SHREC 2014[77]中的部分形狀組合而成,包含10 類形狀,每類形狀包含了基礎(chǔ)形狀的等距變化、近似等距變化、拓?fù)渥兓凹佣吹确莿傂宰兓?共計(jì)100 個(gè)形狀,為非剛性三維形狀檢索提供標(biāo)準(zhǔn)形式,圖10 為SHREC 2015 中的部分形狀.

Fig.10 Part of the shapes of SHREC 2015 database圖10 SHREC 2015 數(shù)據(jù)庫(kù)中的部分形狀

4.1 譜形狀描述符參數(shù)比較

HKS 具有多尺度特性,由時(shí)間參數(shù)t決定該點(diǎn)描述的是形狀的的局部或全局屬性.圖11 中選取不同時(shí)刻應(yīng)用HKS 進(jìn)行一組形狀等距對(duì)應(yīng),顏色由黃到藍(lán)代表HKS 值由大到小,當(dāng)t=0.5 時(shí),此時(shí)熱量剛開(kāi)始擴(kuò)散,只能描述行david 足部的局部幾何信息,此時(shí),HKS 值與足部的高斯曲率值直接相關(guān);當(dāng)t=1 時(shí),熱量擴(kuò)散到形狀的大部分區(qū)域;當(dāng)t=3.0 時(shí),熱量擴(kuò)散到形狀整個(gè)表面,此時(shí),HKS 描述形狀的全局幾何信息.

Fig.11 Non-rigid shape matching using heat kernel signature under different time t (shape:david 1 & david 10)圖11 在不同時(shí)間t 下應(yīng)用熱核簽名進(jìn)行一組非剛性形狀匹配(shape:david 1 & david 10)

WKS 對(duì)時(shí)間參數(shù)自由,圖12 中選取不同能量級(jí)下進(jìn)行一組非剛性形狀匹配.當(dāng)能量級(jí)下的數(shù)量增大時(shí),WKS 能更精確地表達(dá)形狀的局部特征,但其數(shù)量并不是越大越好,過(guò)大的能量級(jí)會(huì)增加導(dǎo)致WKS 無(wú)法刻畫(huà)形狀的全局特性,間接增加更多計(jì)算誤差;如圖12 所示,本文選取e100作為合適的能量規(guī)模.

Fig.12 Non-rigid shape matching using wave kernel signature under different energy scale eN(shape:david 1 & david 10)圖12 在不同能量級(jí)(eN)下應(yīng)用波動(dòng)核簽名進(jìn)行一組非剛性形狀對(duì)應(yīng)(shape:david 1 & david 10)

圖13 基于庫(kù)SHREC 2010 驗(yàn)證了表1 每種譜形狀描述符在不同等距變化下的魯棒性.可以看出,GPS 和WKS 總體魯棒性較高.

Fig.13 Compared with GPS,HKS,BS,WKS robustness in isometric,sampling,cave,noise and topological changes (t=3.0,λNum=100,e100)圖13 對(duì)比GPS、HKS、BS、WKS 在等距、采樣、加洞、噪聲及拓?fù)渥兓卖敯粜?t=3.0,λNum=100,e100)

4.2 譜形狀描述符用于三維非剛性形狀匹配比較

從圖14 中可以看出,GPS 作為一個(gè)全局形狀描述符,對(duì)cat 0 和cat 1 足部和腿部的細(xì)節(jié)描述不夠,不能應(yīng)用到局部匹配中,但是能夠分清cat 0 和cat 1 前足和后足.

Fig.14 Non-rigid shape matching using GPS,HKS,BS,WKS (shape:cat 0 & cat 1,t=3.0,λNum=100,e100)圖14 應(yīng)用GPS、HKS、BS、WKS 進(jìn)行非剛性形狀匹配(shape:cat 0 & cat 1,t=3.0,λNum=100,e100)

而當(dāng)時(shí)間參數(shù)足夠大時(shí),HKS 能表征cat 0 與cat 1 的局部幾何信息和全局幾何信息,但由于HKS 使用的都是一些低通濾波器,形狀的高頻率信息被抑制,不能精確地表示形狀,相比GPS,HKS 能分清cat 的腿部和身體,但沒(méi)有辦法區(qū)分貓的前足和后足;BS 表現(xiàn)最佳,cat 1 相對(duì)cat 0 尾巴發(fā)生較大扭曲,此時(shí),cat 0 和cat 1 為近似等距變化,BS 能夠明確地描述尾部的近似等距變化且匹配度高;同時(shí),WKS 在貓的尾部匹配度同樣較高,且相比HKS,WKS 使用帶通濾波器,減少低頻的影響,在圖中能夠清楚地分離出形狀的頻帶區(qū)域,具有優(yōu)越的特征定位,且能區(qū)分貓的四足,適合高精度的匹配,但算法時(shí)間復(fù)雜度較高.

通過(guò)10 次實(shí)驗(yàn)求取平均值,幾個(gè)形狀描述符耗費(fèi)時(shí)間如表3 所示,應(yīng)用4 種譜形狀描述符進(jìn)行非剛性三維形狀匹配的空間復(fù)雜度為O(n),n為三維形狀上采樣點(diǎn)的個(gè)數(shù).由于GPS 和BS 都是高維向量,因此其耗費(fèi)時(shí)間要多于HKS;同時(shí),WKS 采用帶通濾波器分離形狀上的不同頻率集合,對(duì)于形狀的細(xì)節(jié)刻畫(huà)較多,因此時(shí)間耗費(fèi)相對(duì)最高.為了比較應(yīng)用不同譜形狀描述符進(jìn)行非剛性三維形狀匹配的匹配度,實(shí)驗(yàn)中,我們計(jì)算一對(duì)形狀上采樣點(diǎn)的譜形狀描述符的相關(guān)系數(shù)R=corr2(A,B)作為三維非剛性形狀匹配的匹配度(即一對(duì)形狀的相似度),結(jié)果如表4 所示,WKS 和BS 都對(duì)參數(shù)自由,BS 能夠調(diào)和地描述形狀的全局和局部屬性,WKS 能夠在描述形狀全局屬性的同時(shí)刻畫(huà)形狀的細(xì)節(jié).因此,應(yīng)用WKS 和BS 的形狀匹配相對(duì)較高.

Table 3 Time-consuming of non-rigid shape matching using spectral shape descriptors表3 應(yīng)用譜形狀描述符進(jìn)行非剛性形狀匹配所耗費(fèi)時(shí)間

Table 4 Non-rigid shape matching using spectral shape descriptors表4 應(yīng)用譜形狀描述符進(jìn)行非剛性形狀匹配

4.3 譜距離分布用于三維非剛性形狀匹配比較

有效的譜距離分布函數(shù)可以區(qū)分不同類別的形狀,且對(duì)于形狀發(fā)生非剛性變化,譜距離概率分布趨勢(shì)差別較小,故可以通過(guò)匹配形狀的譜距離分布,進(jìn)行三維非剛性形狀匹配[78].圖 15 是計(jì)算一對(duì)形狀(選用最TOSCA 2010 中最復(fù)雜的centuar0 和centuar1)的4 種譜距離分布:CD,HDD,BD,WKD,給出譜距離概率分布(注:由于整體分布趨勢(shì)接近,無(wú)法看出差別,故同時(shí)給出分布概率小于等于0.1 的分布圖作比較),可以很直觀地從圖15中看出,centuar0和centuar1的WKD概率分布趨勢(shì)一致.說(shuō)明WKD具有良好的精確匹配性,通過(guò)圖中centuar0和centua1 的WKS 值對(duì)應(yīng),可以發(fā)現(xiàn):應(yīng)用WKD 概率分布能夠區(qū)分半人馬的胳膊、4 條腿;與上述相同,BD 概率分布同樣趨勢(shì)一致,但在區(qū)分本人馬的前腿和后腿時(shí)區(qū)分度不大,只能分清前腿和后腿;CD 概率分布略有差別,由于GPS 對(duì)局部細(xì)節(jié)表述不夠,導(dǎo)致CD 值有差異,圖中的半人馬僅能區(qū)分胳膊和腿部;HDD 概率分布總體走勢(shì)一致,但差異較大,無(wú)法區(qū)分半人馬的胳膊和腿,但同樣的,對(duì)于局部細(xì)節(jié)刻畫(huà)清楚.

通過(guò)10 次實(shí)驗(yàn)求取平均值,幾個(gè)譜距離分布函數(shù)的耗費(fèi)時(shí)間見(jiàn)表5.應(yīng)用4 種譜形狀描述符進(jìn)行非剛性三維形狀匹配的空間復(fù)雜度為O(n2),n為三維形狀上采樣點(diǎn)的個(gè)數(shù).為了比較非剛性形狀應(yīng)用不同譜形狀分布函數(shù)進(jìn)行匹配的匹配度,實(shí)驗(yàn)中,為了直接得到一對(duì)形狀的匹配度,我們同樣計(jì)算一對(duì)形狀的譜形狀距離分布函數(shù)的相關(guān)系數(shù)作為三維非剛性形狀匹配的匹配度(即一對(duì)形狀的相似度),結(jié)果見(jiàn)表6.相比應(yīng)用譜形狀描述符進(jìn)行形狀匹配,應(yīng)用譜距離分布進(jìn)行形狀匹配時(shí),所有形狀的匹配度都有提升.原因在于:應(yīng)用譜距離分布進(jìn)行形狀匹配時(shí)不考慮形狀的局部細(xì)節(jié)匹配,得到的是一對(duì)形狀的全局匹配結(jié)果.因此,相比于譜形狀描述符,譜距離分布函數(shù)在進(jìn)行三維非剛性形狀匹配時(shí)無(wú)需尋找一對(duì)形狀的對(duì)應(yīng)點(diǎn),穩(wěn)定性更強(qiáng),更適用于非剛性形狀整體匹配.

Fig.15 Distribution function of four spectral distances for non-rigid shapes using matching(shape:centaur 0 & centua 1)圖15 4 種譜距離分布函數(shù)進(jìn)行非剛性形狀匹配(shape:centaur 0 & centua 1)

Table 5 Time-consuming of non-rigid shape matching using the distribution function of four spectral distances表5 應(yīng)用4 種譜距離分布函數(shù)進(jìn)行非剛性形狀匹配所耗費(fèi)時(shí)間

Table 6 Non-rigid shape matching using the distribution function of four spectral distances表6 應(yīng)用4 種譜距離分布函數(shù)進(jìn)行非剛性形狀匹配

結(jié)合表3 和表5 我們可以看出,應(yīng)用譜形狀描述符進(jìn)行形狀匹配時(shí)的時(shí)間復(fù)雜度和空間復(fù)雜度要比應(yīng)用譜距離分布函數(shù)的時(shí)間復(fù)雜度低,因?yàn)橛?jì)算形狀上任意兩點(diǎn)的譜距離會(huì)耗費(fèi)較多的時(shí)間和占用較多的空間.同時(shí),結(jié)合表4 和表6 我們可以看出,應(yīng)用譜形狀描述符進(jìn)行形狀匹配時(shí),隨著形狀大小的增加,形狀的匹配度會(huì)略微降低;反之,應(yīng)用譜距離分布函數(shù)進(jìn)行形狀匹配時(shí),隨著形狀大小的增加,形狀的匹配度會(huì)略微增高.因?yàn)楫?dāng)形狀增大時(shí),形狀的三角網(wǎng)格面片數(shù)也會(huì)增加,導(dǎo)致采樣點(diǎn)的譜形狀描述符的計(jì)算量大大增加,降低形狀匹配度;反之,形狀的三角網(wǎng)格面片數(shù)增加,會(huì)增大譜距離分布函數(shù)的樣本量,更能反映形狀的全局屬性,進(jìn)一步提高形狀的匹配度.

圖16 為基于SHREC 2015,應(yīng)用4 種譜距離分布函數(shù)進(jìn)行非剛性匹配的形狀相似性熱力圖.為了區(qū)分不同類形狀的差異性,本文采用最常用的歐氏距離計(jì)算一對(duì)形狀的相似性.

Fig.16 Thermodynamic diagram of non-rigid 3D shape matching using four spectral distances based on SHREC 2015 database圖16 基于SHREC 2015 數(shù)據(jù)庫(kù),應(yīng)用4 種譜距離進(jìn)行非剛性三維形狀匹配的熱力圖

如圖16 所示(其中,每連續(xù)10 個(gè)編號(hào)表示一類形狀,1～10 為centaur;11～20 為ants;21～30 為gorilla;31～40 為Male 0;41～50 為female-thin;51～60 為male 13;61～70 為gdog;71～80 為male16;81～90 為plies;91～100 為malebodybuilder).在4 種譜距離分布函數(shù)中:CD 描述了形狀的全局屬性,因此匹配結(jié)果較為集中;HDD 描述了形狀的局部屬性,且相對(duì)于其他3 種譜距離分布函數(shù)的匹配性能較差,原因在于HDD 對(duì)于時(shí)間參數(shù)和噪聲非常敏感,在實(shí)際實(shí)驗(yàn)中很難尋找到最優(yōu)的時(shí)間參數(shù);BD 調(diào)和地描述了形狀的局部和全局屬性,且不依賴于時(shí)間參數(shù)t;WKD 既能描述形狀的局部屬性,又能描述形狀的全局屬性,同時(shí),相對(duì)于其他3 種譜距離分布函數(shù),WKD 能夠精準(zhǔn)地描述不同類的形狀,對(duì)于male0,male13 和male16 的區(qū)分度更大.

表7 為應(yīng)用圖16 的結(jié)果進(jìn)行不同類非剛性三維形狀檢索的查準(zhǔn)率,表中結(jié)果與圖16 結(jié)果相一致.

Table 7 Precision ratio of 3D Non-rigid shape retrieval using the distribution function of four spectral distances based on SHREC 2015 database表7 基于SHREC 2015 數(shù)據(jù)庫(kù),應(yīng)用4 種譜距離分布函數(shù)進(jìn)行非剛性三維形狀檢索查準(zhǔn)率

4.4 問(wèn)題與展望

通過(guò)實(shí)驗(yàn)比較了不同譜形狀描述符和譜距離分布函數(shù)進(jìn)行非剛性三維形狀匹配的性能,可以發(fā)現(xiàn)利用基于譜分析的形狀描述符進(jìn)行非剛性形狀匹配效果較好.在4 類譜形狀描述符中,WKS 和WKD 整體匹配表現(xiàn)性能最優(yōu),適用于精細(xì)匹配,但時(shí)間復(fù)雜度較高,不適用于大規(guī)模形狀的快速匹配;BS 和BD 性能次之,能同時(shí)調(diào)和地表示形狀的局部及全局信息,但過(guò)于強(qiáng)調(diào)函數(shù)同時(shí)描述形狀的局部和全局性質(zhì),也會(huì)弱化形狀的真實(shí)全局和局部特性;HKS 和HDD 對(duì)時(shí)間參數(shù)敏感,所以僅憑某時(shí)刻t下HKS 值進(jìn)行形狀的非剛性匹配性能較差,若能比較形狀上每個(gè)點(diǎn)或部分特征點(diǎn)的一段時(shí)間序列下的HKS 值,則能提高匹配性能,且HKS 適用于部分匹配;GPS和CDD 整體匹配度較低,適用于快速匹配和粗匹配,但不適用部分匹配.同時(shí),使用4 種譜距離分布函數(shù)進(jìn)行三維非剛性形狀匹配時(shí),無(wú)法得到形狀部分匹配結(jié)果,只能得到一對(duì)形狀的全局匹配結(jié)果,其時(shí)間復(fù)雜度和空間復(fù)雜度也比譜形狀描述符復(fù)雜度高.在未來(lái)的研究工作中,針對(duì)不同變化類型的形狀(如一些近似等距變化或大變形形狀)及不同的應(yīng)用場(chǎng)景,應(yīng)結(jié)合幾種描述符的優(yōu)點(diǎn),考慮同時(shí)使用多個(gè)描述符的權(quán)重組合或其他改進(jìn),提升非剛性三維形狀匹配度.

5 總結(jié)

本文給出基于譜分析的形狀描述符進(jìn)行非剛性三維形狀匹配的方法流程,詳細(xì)介紹了幾種譜形狀描述符和譜距離分布函數(shù),并在以下幾方面對(duì)比了不同形狀描述符的性能:(1) 局部及全局屬性;(2) 有無(wú)參數(shù)及參數(shù)選擇;(3) 時(shí)間復(fù)雜度;(4) 最優(yōu)匹配度;(5) 適用匹配場(chǎng)景;(6) 整體表現(xiàn)性能.通過(guò)實(shí)驗(yàn),證明了本文預(yù)估的正確性.譜分析是一個(gè)易于理解、普適且魯棒的分析方法,基于譜分析的形狀描述符在非剛性三維形狀整體匹配中表現(xiàn)出了優(yōu)異的性能,我們希望提升基于譜分析的形狀描述符在非剛性形狀匹配中重要的理論意義及并推動(dòng)其在工程應(yīng)用價(jià)值的發(fā)展.同時(shí),在未來(lái)的工作中,我們會(huì)對(duì)基于譜分析的形狀描述符進(jìn)行非剛性三維形狀局部匹配進(jìn)行進(jìn)一步研究.