基于骨架線約束的非剛性三維模型匹配

王 凌 燕

(山西傳媒學院傳媒工程系 山西 晉中 030619)

0 引 言

隨著計算機圖形學與虛擬現(xiàn)實技術的發(fā)展，基于三維模型數(shù)據(jù)的分析與應用變得越來越重要。相比于傳統(tǒng)的二維圖像數(shù)據(jù)，三維模型數(shù)據(jù)擁有完善的幾何信息，與現(xiàn)實世界數(shù)據(jù)對象的表示形式保持一致，使其能夠用來進行各種精確的模擬計算與實驗分析。通過使用方便的三維掃描設備(Kinect，支持3D結構光技術的手機)與模型處理軟件的支持，獲取大規(guī)模三維模型數(shù)據(jù)的成本被大大降低，使得對三維數(shù)據(jù)分析的工程化應用變?yōu)榭赡堋榱四軌驅崿F(xiàn)基于大規(guī)模三維數(shù)據(jù)的相關工程應用，對于三維模型數(shù)據(jù)的存儲、匹配以及對應等相關研究問題被提出，并越來越受到研究者的重視。

三維模型匹配作為三維模型數(shù)據(jù)分析的一個重要問題，其具有重要的研究價值。對于大規(guī)模三維模型數(shù)據(jù)集，通過建立不同模型數(shù)據(jù)之間的匹配度，能夠對三維模型數(shù)據(jù)進行識別與分類，得到用于模型數(shù)據(jù)管理的參考信息，指導對模型數(shù)據(jù)的檢索、標注以及交互等。建立三維模型匹配方法，需要注意以下幾個核心問題：原始數(shù)據(jù)的表示形式；基于原始數(shù)據(jù)的特征選擇；基于選擇特征的分析方法。對于三維模型數(shù)據(jù)來說，由于其獲取設備以及處理方法的多樣性，其表示形式往往不同。通常三維數(shù)據(jù)的表示形式包括深度圖、點云、體素以及三角網(wǎng)格數(shù)據(jù)等。對于不同的三維數(shù)據(jù)表示形式，需要建立與之對應的特征表示?；谌S模型數(shù)據(jù)提出的特征表示，需要滿足在一定變化條件下的不變性，如平移、旋轉、縮放以及滿足對象不變的非剛性變換。對三維模型數(shù)據(jù)的特征建立對應的分析方法，最終能夠得到三維模型數(shù)據(jù)的匹配結果。

本文提出一種基于骨架線約束的非剛性三維模型匹配方法?；谌S網(wǎng)格數(shù)據(jù)提取對應的骨架線。通過利用三維模型骨架線的近似等距約束性質，建立模型到骨架線的距離特征。距離特征對應骨架線的距離分布，能夠被組織成一條特征曲線。通過計算不同三維模型數(shù)據(jù)特征曲線間的Frechet距離，最終得到三維模型的匹配結果。

1 相關工作

按照對三維模型形變敏感程度以及所建立的幾何特征的作用范圍，匹配方法可分為如下幾類：剛性三維模型匹配，非剛性三維模型匹配，基于局部幾何特征的三維模型匹配以及基于全局幾何特征的三維模型匹配。

剛性三維模型匹配方法針對形變小、幾何特征穩(wěn)定的三維模型進行特征提取并得到基于特征分析的匹配結果。一些方法針對標準的三維模型CAD數(shù)據(jù)建立匹配方法。Zhang等[1]針對CAD模型的局部異構性，建立基于邊界表示的局部模型匹配方法。Tao等[2]基于類似的思想，提出對模型局部區(qū)域進行編碼并分析的方法，建立模型的局部匹配結果。一些方法基于骨架線約束建立剛性三維模型匹配。Cornea等[3]提出基于骨架曲線的一系列算法，將其用于三維模型的分類與匹配。Goes等[4]利用骨架線與網(wǎng)格曲面的對應關系，對曲面進行分塊，并建立局部特征匹配。

非剛性三維模型匹配方法針對形變較大的模型，提出形變魯棒性要求較高的幾何特征建立匹配算法。其中比較有代表性的方法是基于曲面熱核特征的模型匹配方法。Sun等[5]率先提出基于熱核對三維物體網(wǎng)格曲面的幾何特征表示。Fang等[6]提出一種基于熱核計算的特征描述子，用來描述三維模型的幾何特征。李海生等[7]對熱核特征進行改進,通過簡化三維模型的網(wǎng)格表示，降低對三維模型熱核特征計算的時間開銷。為三維模型建立統(tǒng)一的表示形式是解決非剛性模型匹配的另一個重要思路。Lian等[8]利用測地距離與多維尺度壓縮算法建立三維模型的近似等距標準形式，得到三維模型的非剛性形狀匹配結果。Ovsjanikov等[9]針對特定類別的非剛性形變三維模型建立標準表示形式，以支持對非對應的三維模型進行檢索與匹配。左向梅等[10]通過結合多種形狀描述特征，建立對三維網(wǎng)格曲面的形狀特征描述。其他諸如基于拓撲結構分析[11]、ShapeDNA[12]、Reeb圖[13-14]等三維模型集合特征建立非剛性模型匹配，均有廣泛的研究與應用。對于大部分非剛性三維模型匹配方法，為了建立對非剛性變換的魯棒特征，往往采用全局幾何特征描述方法，來得到匹配結果。因此，該類方法也可對三維模型全局的幾何特征建立描述，可以被同時歸類為基于全局幾何特征的分析方法。

基于局部幾何特征建立三維模型匹配，為三維模型建立局部特征描述符，并建立針對三維模型局部區(qū)域的匹配結果。孫瀚等[15]通過分析三維模型點云中特征點的對應關系，建立基于深度學習描述子的特征點聚類，獲得模型匹配結果。周繼來等[16]利用形狀指數(shù)特征，得到對歷史文物模型數(shù)據(jù)的形狀特征表示以及匹配方法。李闖等[17]建立對三維模型點云的平均自旋圖變換，得到對模型的旋轉不變表示形式，進而建立對三維模型的形狀特征描述。一些方法通過結合三維數(shù)據(jù)的多個投影圖像與圖像分析算法，得到模型匹配結果。劉鋼等[18]對三維模型的多個投影圖像建立稀疏自編碼，利用深度學習網(wǎng)絡模型進行訓練，最終得到模型匹配結果。白靜等[19]通過對三維模型映像進行基于二維圖像的卷積神經(jīng)網(wǎng)絡訓練，得到模型匹配結果。

基于剛性三維模型的匹配方法，算法實現(xiàn)簡單，幾何特征描述直觀，但適應性差，對非剛性形變敏感?；诜莿傂匀S模型或基于全局幾何特征描述的模型匹配方法，適用性強，對特殊的模型形變魯棒，結果準確，但是算法復雜，對模型數(shù)據(jù)本身的質量有較高的要求?；诰植繋缀翁卣髅枋龅姆椒?，特征提取方便，方便利用學習方法建立特征分析框架，但由于局部幾何特征具有顯著的離散特性，算法的復雜度通常較高，且不能有效地描述三維模型的全局幾何特征。本文提出的基于骨架線約束的模型匹配方法，結合骨架線與模型的對應關系以及局部骨架線距離特征描述，建立對非剛性三維模型的匹配方法，降低了算法的實現(xiàn)難度。

2 骨架線提取與標定

為了建立對三維模型的骨架線約束以及骨架距離特征描述，首先需要對三維模型進行骨架線提取。三維模型的骨架線作為描述模型主體結構的重要數(shù)據(jù)，能夠在一定程度上表示三維模型的拓撲結構特性、尺度、模型數(shù)據(jù)分布等重要幾何信息。對于三維模型的骨架線提取算法，已有諸多的研究工作[20-23]。本文使用文獻[20]提供的相關工具，建立對三維模型網(wǎng)格曲面數(shù)據(jù)的骨架線提取方法，并得到骨架線中特征點的連接結構。圖1所示為對三維模型的骨架線提取結果。

圖1 提取三維模型的骨架線

基于已經(jīng)獲取的骨架線，需要對骨架線中特征點距離分布進行預計算，以得到一個用于提取骨架線距離特征的標定點，方便后續(xù)的計算。在傳統(tǒng)的基于曲面全局幾何特征分析的方法中，標定點的選擇滿足對全局幾何特征分析所得到的唯一值，如平均測地距離中心[24]和曲率中心[25]。該類標定點需要對曲面進行諸如拉普拉斯算子以及曲率分布的全局計算，其結果受到模型曲面質量的影響。對于骨架線來說，其上的特征點對應模型的曲面區(qū)域，對骨架線的特征點進行距離統(tǒng)計，并按照定義找到標定點，其計算過程不受模型曲面網(wǎng)格質量的影響，且計算開銷較小。

為了找到骨架線上的標定點，首先需要對骨架線上的特征點進行分類。按照特征點的連接關系可以分為三類：端點、連點、節(jié)點。端點即只有一條邊與之相連的骨架線上的特征點，可以被理解為骨架線的“末端”；連點即有兩條邊與之相連的特征點，可以被理解為骨架線路徑上正常的連接點；節(jié)點為有多余兩條邊與之相連的特征點。依據(jù)骨架線的幾何性質，對應節(jié)點的位置表示三維模型數(shù)據(jù)分段的區(qū)域，如圖2所示。因此，骨架線中作為節(jié)點的特征點具有最重要的幾何意義，表示模型的不同區(qū)域的分割位置?；诠羌芫€特征點的連接關系以及特征點的分類，給出標定點的定義，如下式所示：

(1)

式中：sb為骨架線上的標定點；Gs為骨架線上的特征點集合S與特征點連接關系E組成的圖結構；D為基于Gs的骨架線特征點之間的最短路徑搜索距離。sb滿足其全局的最短路徑搜索距離最短，即可被認為是骨架線上的重心。由于對應三維模型的骨架線，滿足近似等距特征，在不改變三維模型拓撲信息的前提下，模型的非剛性變化不會對骨架線上的最短路徑搜索結果產(chǎn)生影響。因此，sb的選取對非剛性形變具有魯棒性。圖3給出了對不同三維模型的標定點定位結果。結合骨架線上具有不同分類的特征點與標定點，實現(xiàn)了對骨架線標定，以方便接下來對骨架距離特征的提取與分析。在骨架線上的每一個特征點到骨架線上的標定點都會有一個基于Gs的最短路徑，我們稱該路徑為骨架線特征點的測地坐標。

圖2 按照骨架線節(jié)點對三維模型的分段結果

圖3 提取三維模型骨架線上的標定點

3 骨架距離特征分析

通過對骨架線的標定，骨架線的不同分段以及骨架中心能夠被標識?；跇硕ǖ墓羌芫€，提出對三維模型幾何特征描述的骨架距離特征及其分析方法。通過測地坐標，能夠對三維模型進行基于骨架線的對應。通過分析對應好的骨架線特征點與三維模型曲面的距離，得到骨架距離特征曲線。利用Frechet曲線度量，實現(xiàn)對不同三維模型骨架距離特征曲線的度量，并最終得到三維模型的匹配結果。

3.1 骨架距離特征提取

對于三維模型來說，每一個在模型網(wǎng)格曲面上的頂點都會在骨架線上有一個對應的特征點。反之，每一個骨架線上的特征點，都會對應一個模型網(wǎng)格曲面的頂點集合。假設將骨架線看成一條連續(xù)的骨架曲線，骨架曲線上的一點對應一個模型曲面的頂點集合。根據(jù)骨架線與模型網(wǎng)格的關系，這組頂點集合能夠首尾連接成一個圓環(huán)。對于骨架曲線上的點，定義一個半徑距離，按照該半徑距離生成的圓，能夠實現(xiàn)對頂點圓環(huán)的最優(yōu)擬合。以骨架線上的標定點出發(fā)，向骨架線的其他特征點搜索，按照特定的距離步長提取骨架上的特征點，并計算其對應的到模型的擬合半徑距離。通過該方法，得到骨架線上的每個特征點的二維數(shù)據(jù)，包括其到骨架線標定點的距離以及半徑距離。該二維數(shù)據(jù)被稱為骨架距離特征，如下式所示：

(2)

式中：F表示骨架距離特征，αi表示骨架線特征點的測地坐標，βi表示骨架線特征點到三維模型網(wǎng)格曲面頂點的擬合半徑距離。對應骨架線特征點si的模型網(wǎng)格頂點數(shù)為k，對應頂點集合{vj|j=1,2,…,k}。函數(shù)dis表示頂點集合的點到擬合圓Q(si)的距離，通過計算最小值，得到Q(si)的最優(yōu)解，并將其對應擬合圓的半徑賦值給βi?；谝呀?jīng)獲得的骨架距離特征F，三維模型能夠表示為按照骨架線測地坐標以及半徑距離組成的一條骨架距離特征曲線。基于骨架線的近似等距約束可知，相同類別三維模型的非剛性形變，對距離特征不會產(chǎn)生顯著的影響。然而，基于式(2)建立的骨架距離特征，由于未對三維模型尺度進行歸一化，其特征表示會受到縮放作用的影響。為了消除縮放作用的影響，需要對測地坐標與半徑距離進行歸一化，如下式所示：

(3)

式中：FR表示經(jīng)過歸一化之后的骨架距離特征。按照測地坐標的最大最小值，以及半徑距離的最大最小值，對每一個骨架特征點對應的測地坐標與半徑距離進行歸一化，使得骨架距離特征曲線的二維坐標被同時映射在一個[0,1]×[0,1]的區(qū)域中。圖4展示了同類三維模型在非剛性形變下的骨架距離特征曲線。橫坐標表示測地坐標，由0到1，縱坐標表示對應的半徑距離。對于三維模型按照測地坐標產(chǎn)生的分叉情況，其對應的半徑距離取最大值。可以看到，相同類別的三維模型，其骨架距離特征曲線具有極高的相似度。

圖4 同類三維模型非剛性變換下的骨架距離特征曲線

3.2 骨架距離特征曲線的Frechet距離

針對三維模型骨架距離特征曲線，通過對曲線的相似度進行度量，能夠得到與之對應的三維模型的匹配結果。針對曲線相似度度量，這里選擇建立曲線的Frechet的距離來實現(xiàn)。Frechet距離可以被理解為兩組曲線的最短距離。對于曲線的離散形式，F(xiàn)rechet距離可以被理解為兩個離散點集合的最短距離，由集合中的每一個離散點到另外一個集合的最短路徑之和構成。相比于計算曲線對應點的歐氏距離，F(xiàn)rechet距離能夠更好地反映曲線的相似程度。由于三維模型在非剛性變換下，局部的骨架線距離可能會產(chǎn)生小的伸縮。按照測地坐標建立的骨架距離特征存在一定的誤差。使用Frechet距離能夠對該誤差進行修正，進而獲得更加準確的曲線度量結果。式(4)給出了基于骨架距離特征的Frechet距離計算方法。FR1與FR2為兩個三維模型的骨架距離特征表示。距離函數(shù)d為骨架距離特征曲線上的一點到另外一條曲線的最短距離。Frechet距離取兩個模型到對方距離的最小值。基于骨架距離特征曲線的Frechet距離，能夠得到三維模型匹配的最終結果。

DFrechet(FR1,FR2)=

FR1={(υi1,ωi1)},FR2={(υi2,ωi2)}

(4)

4 實驗分析

為了驗證基于骨架距離特征以及對特征曲線的Frechet距離計算的三維模型匹配方法的有效性，提出對三維模型公共庫SHREC的模型匹配實驗。三維模型公共庫SHREC共包括50類，大約1 200個掃描數(shù)據(jù)。通過對模型庫的匹配準確度、缺失網(wǎng)格數(shù)據(jù)魯棒性驗證以及算法運算速度對比三個方面來考察本文方法的性能。程序設計軟件平臺基于微軟VS2017+OpenGL+CGAL擴展包進行開發(fā)，硬件平臺為I7- 6700，4核，3.7 GHz，內存8 GB，顯卡Quadro P600，2 GB顯存。

4.1 基于SHREC的模型匹配實驗

從SHREC公共數(shù)據(jù)庫中的每一個類別內隨機選擇10個數(shù)據(jù)作為訓練集。輸入測試三維模型，計算其到訓練集中，每一個類別下三維模型的骨架距離特征曲線的Frechet距離并求和。取距離和的最小值的訓練集類別為輸入三維模型的匹配結果。表1展示了部分非剛性三維模型的Frechet距離矩陣，可以看到，同類的三維模型，其Frechet距離和顯著小于其他類別的三維模型。為了進一步說明本文方法的三維模型匹配性能，選擇基于熱核特征的三維模型匹配方法[10]與基于平均自旋圖的匹配方法[17]進行對比。由于SHREC上模型本身的類別存在關聯(lián)關系，建立對類別劃分的子集來比較不同方法的匹配準確度，能夠得到更加準確的評價結果。這里劃分SHREC為兩個不同的子集，即動物子集與物品子集。這里的動物子集包括蛇、狗、鱷魚等屬于動物類別的三維模型。動物模型的非剛性形變更加顯著。屬于物品子集的模型，其非剛性形變受到的約束更大?；诓煌腟HREC模型子集，驗證不同模型匹配方法的模型識別準確度，能夠更好地比較對不同非剛性變化的模型匹配問題的性能。表2展示了不同方法在SHREC測試數(shù)據(jù)子集上的模型匹配精確度。圖5展示了不同方法在SHREC數(shù)據(jù)庫上的受試者曲線圖(ROC)結果。由實驗結果可知，本文方法對非剛性三維模型匹配問題能夠得到比較精確的結果。

圖5 在SHREC測試數(shù)據(jù)集上，不同模型匹配方法的ROC曲線結果圖

表1 基于骨架距離特征曲線Frechet距離的不同類別三維模型匹配結果對比

表2 不同方法在SHREC曲面網(wǎng)格缺失測試數(shù)據(jù)集的識別準確度 %

4.2 基于SHREC缺失網(wǎng)格數(shù)據(jù)模型匹配實驗

對于帶有缺失網(wǎng)格的三維模型進行匹配，是模型匹配算法需要考慮的問題。經(jīng)過三維掃描設備獲取的模型數(shù)據(jù)，由于受到設備參數(shù)，掃描場景限制以及空間噪聲等多種因素影響，其曲面網(wǎng)格可能會帶有孔洞與噪聲等，進而破壞模型網(wǎng)格曲面的完備性，如圖6所示。因此，對帶有孔洞或噪聲信息的三維模型數(shù)據(jù)，其對應的匹配方法應具有對該類情況的魯棒性。由于骨架距離特征不需要對模型網(wǎng)格進行特征分析，僅僅是通過骨架與網(wǎng)格之間的對應關系，建立統(tǒng)計意義上的距離特征，因此特征本身對模型上的孔洞與局部區(qū)域的網(wǎng)格缺失具有一定的魯棒性?；赟HREC數(shù)據(jù)庫，通過對每一個類別下隨機選擇3到5個模型，隨機選擇網(wǎng)格曲面的一些區(qū)域，進行網(wǎng)格裁切以產(chǎn)生孔洞，以建立一個帶有孔洞的SHREC測試數(shù)據(jù)集。基于該測試數(shù)據(jù)集，建立本文方法與基于熱核特征方法的驗證，以得到模型匹配結果。由對比結果可知，本文方法對缺失數(shù)據(jù)具有較好的魯棒性。

圖6 帶有孔洞與局部缺失的三維模型以及其網(wǎng)格曲面

4.3 基于SHREC數(shù)據(jù)模型匹配的時間開銷

對于模型匹配算法來說，其在大規(guī)模三維模型數(shù)據(jù)庫進行匹配的時間開銷，在工程應用中是十分重要的性能指標?；诠羌芫嚯x特征的模型匹配方法，在時間開銷上具有顯著的優(yōu)勢。其原因在于，一個三維模型的骨架距離特征，被表示為一條特征曲線。對于三維模型的匹配問題被轉換為特征曲線的Frechet度量求解，通過簡單的線性計算，能夠得到匹配結果。對于三維模型庫的所有模型進行骨架線提取，并獲取骨架距離特征后，對應的模型匹配問題被轉換為特征曲線的匹配問題。表3展示了本文的模型匹配方法與基于熱核特征的匹配方法，在單對模型匹配平均時間開銷以及基于不同樣本量的單個模型匹配任務時間開銷的對比結果?？梢钥闯?，本文方法在時間開銷上具有顯著優(yōu)勢。

表3 不同方法在SHREC測試數(shù)據(jù)集的時間開銷對比 s

5 結 語

本文提出一種基于骨架線約束的非剛性三維模型匹配算法?；诠羌芫€與三維模型網(wǎng)格曲面的關系，建立骨架距離特征曲線。利用Frechet度量得到骨架距離特征曲線的相似度，用以表示三維模型的匹配度。由實驗可知，該方法對具有非剛性變換的三維模型，能夠得到比較精確的匹配結果，即對非剛性變換具備較強的魯棒性。由于骨架距離特征點的提取不受網(wǎng)格曲面質量的影響，匹配方法對具有網(wǎng)格缺失的三維模型匹配同樣具有較好的魯棒性。骨架距離特征的提取與Frechet度量均能夠在線性時間完成，所以匹配算法在時間開銷上同樣具備顯著的優(yōu)勢。在未來的工作中，希望能夠融合骨架線自身的拓撲信息，指導帶有拓撲連接約束的骨架距離特征，進一步提高模型匹配算法在精確度與時間開銷兩方面的性能。