基于譜變換的非剛性模型局部匹配

韓麗 徐圣斯 樸京鈺

摘? 要： 面向海量復雜的非剛性三維模型的匹配與檢索需求，提出了基于譜變換的局部匹配方法，有效提高了局部檢索的性能，為進一步實現三維模型的形狀編輯、修補以及創新合成奠定了堅實的基礎。首先，基于離散拉普拉斯映射方法，通過ICP配準方法有效分析二維譜圖，提取最優的譜特征表示;其次，構建譜特征的形狀描述算子，計算譜空間的幾何變換參數;進而，引入區域查詢實現基于譜變換的區域配準;最終，通過區域搜索與相似性度量實現高效的非剛性模型局部匹配。實驗結果表明，本方法不僅能夠有效識別同一類非剛性模型的局部結構，而且對于不完整的模型匹配具有較強的魯棒性，具有更優的局部檢索性能。

關鍵詞： 譜變換;局部匹配;非剛性模型;區域配準

中圖分類號： TP391.41? ? 文獻標識碼： A? ? DOI：10.3969/j.issn.1003-6970.2020.10.006

本文著錄格式：韓麗，徐圣斯，樸京鈺. 基于譜變換的非剛性模型局部匹配[J]. 軟件，2020，41（10）：2226

【Abstract】： Aiming at the requirements of shape matching and shape retrieval of massive non-rigid 3D shapes， a novel partial matching method based on spectral transformation was proposed， it effectively improved the performance of shape retrieval and provided a solid foundation for further shape editing， mending and innovative synthesis of 3D models. First， the optimal two-dimensional spectral feature representation of non-rigid 3D shape is extracted based on the spectrum theory. Secondly， we construct shape context description of the spectral features and calculate the geometric transformation parameters of two spectral graphs; Furthermore， a region query is introduced to implement local region registration based on spectral transformation; Finally， partial matching of non-rigid shapes is achieved through local region searching and similarity estimation. Experimental results show that our method not only effectively improves the efficiency of model matching， but also can effectively identify the structural features of the same type of shape， and at the same time has strong robustness for matching between incomplete shapes.

【Key words】： Spectral transformation; Partial matching; Non-rigid shape; Region registration

0? 引言

隨著三維模型獲取以及建模技術的發展，針對海量、異構三維模型的形狀分析、配準、檢索等應用研究日益廣泛。尤其，三維模型的局部匹配與檢索在實現快速的大規模場景重構[1]、三維模型恢復、三維創新設計[2]等應用中具有重要意義[3]。

Paul J. Besl等[4]最先提出了迭代最近點算法（ICP），估計匹配最近點的最優剛性變換，實現不同三維形狀之間的配準，對三維點集、線段集和網絡實體模型均適用，但時間復雜度較高，且不能達到全局最優解。Ferreira等[5]利用層次分割樹將網格模型迭代地分為子部件，然后再進行相似性匹配。Wessel等[6]提出用圖元（圓柱、圓環、球等）對模型局部做匹配。這類基于子部件的局部匹配方法需要解決模型部件分割問題，由于要設置多個閾值而失去健壯性。Stephen等[7-8]提出了利用模型拓撲結構的檢索方法，但拓撲結構提取算法一般對噪聲敏感，所以難以獲得穩定的部件分割結果。

Funkhouser等和Shilane等[9-10]提出了優先隊列比較法。該方法在模型上生成大量采樣點，然后提取采樣點周圍的形狀特征，構建一個優先級隊列以選取形狀區別力強的向量來計算相似度。其方法雖不需要對模型做部件分割，但是特征提取和區分度排序的計算量較大，因此該方法也難以應用于檢索結構復雜的非剛性模型。

近年來，譜分析的方法被廣泛應用于非剛性三維模型的檢索與匹配。其利用拉普拉斯算子將三維模型映射到譜特征空間，揭示了模型的內蘊屬性，能夠有效提高非剛性模型的匹配精度。例如，Lipman等[11]基于譜方法實現全局內蘊的檢測;Sahillioglu等[12]在譜域構造初始化匹配，并采用貪婪算法結合等距性優化匹配結果;Sun等[13]基于模型表面熱擴散方程提出了熱核特征（HKS：Heat Kernel Signature）表示及形狀分析方法;Aubry等[14]將波動方程引入模型，提出波核特征（WKS：Wave Kernel Signature）的形狀分析方法。

然而，目前的譜分析方法主要基于構建的局部描述符或全局點特征表示實現整體形狀分析與檢索，對于局部匹配的研究還不是十分廣泛。

本文提出了一種基于譜變換的非剛性三維模型局部匹配算法。我們通過將非剛性三維模型映射到譜特征空間，提取穩定的二維譜特征表示;基于譜空間變換來實現模型的譜圖配準。進而，引入區域查詢與相似性度量，實現基于譜變換的局部區域匹配。該算法無需對模型進行分割，避免了三維模型中的大量點云計算，一系列實驗驗證了算法的高效性與穩定性。

1? 基于譜變換的局部匹配

本方法主要由三步驟組成：首先，通過拉普拉斯映射提取最優的二維譜特征描述;其次，采用Shape-Context方法[15]，實現二維譜圖的局部輪廓匹配，并基于區域查詢點計算譜圖的幾何變換參數，建立局部區域的譜對應;最終，通過局部區域優化實現非剛性模型的局部匹配。

1.1? 最優二維譜特征表示

基于拉普拉斯映射的譜嵌入將高維數據嵌入到低維空間，有效保持模型的內蘊形狀特性（等距不變性、拓撲不變性），不僅使計算更有效，而且對物體的姿態變化與局部形變不敏感，可有效用于非剛性模型的匹配與分類。

設無向帶權圖G=（V，E）表示網格模型M，其中，vi∈V代表模型頂點，eij∈E表示圖中任意頂點vi和vj的連接邊。頂點之間的相似性可由兩點之間的測地線距離表示Wij∈[0，1]：

模型的譜特征表示中，特征維數越高，其形狀描述能力越強，但同時也帶來了計算時間和存儲空間的更大開銷。前k個特征基有效揭示了模型的內蘊結構特征，被廣泛應用于形狀匹配與檢索中[16]。然而，特征基分布存在扭曲、次序翻轉等若干問題，給形狀匹配帶來了極大的困難。本文進一步提出了最優二維譜嵌入表示方法，通過低維的譜空間變換，實現高效的非剛性模型局部形狀匹配。

我們提取模型的前k=4個特征向量，利用兩兩特征基構建二維譜圖候選集;進而，基于ICP（Iterative Closest Point）方法[4]進行譜圖相似性分析，建立穩定的二維譜特征表示。

其中，為兩個模型對應的二維譜特征基，R 和t為旋轉、平移幾何變換，通過公式5，迭代最近距離點集，求解四元轉換矩陣R和t，最終，通過判斷閾值內的匹配對數，有效獲取候選譜圖的形狀相似度。

圖1（a）為兩個不同姿態螞蟻模型的二維譜圖候選集（1-2、1-3、1-4、2-3、2-4和3-4），通過ICP迭代匹配算法衡量譜圖之間的形狀相似性。如圖1（b）所示，其中，由2-3特征基構建的二維譜圖的匹配精度最高（紅框內所示）。通過實驗統計分析，我們發現由2-3特征基構造的二維譜圖在非剛性變換模型中具有更強的穩定性。因此我們將其作為模型的最優二維譜特征表示。

1.2? 基于譜變換的局部區域匹配方法

利用穩定的二維譜特征表示，我們進一步提出了基于譜變換的形狀匹配方法。通過建立譜圖的輪廓配準與區域查詢，有效獲取譜空間的幾何變換參數;進而，基于區域幾何變換與相似性度量，實現高效的非剛性模型局部形狀匹配。

1.2.1? 局部譜圖輪廓配準

首先，我們采用Alpha-Shape算法提取二維譜圖輪廓點集（如圖2（a，b）所示），依據形狀上下文（Shape-Context）算法[15]構建譜圖之間的局部輪廓對應，如圖2c，藍點是局部模型的譜圖輪廓點，紅點是完整模型譜圖輪廓點。

我們以輪廓點為中心建立同心圓，以圓心為中心按照，12個方向，將空間分為60個區域（60個bin）。根據輪廓點在bin中的分布，利用直方圖表示其上下文形狀信息。

設和分別為源模型與目標模型的最優二維譜圖上的輪廓點。采用代價矩陣 計算形狀相似度：

分別表示和歸一化后的形狀直方圖的第k級，k為形狀直方圖的量化等級。的值越小，說明兩點之間越相似;反之，兩者之間相差越大。通過公式6可獲得兩個譜圖上所有輪廓點的匹配點對。

1.2.2? 基于譜變換的區域配準

為了有效獲得模型的區域匹配，我們在二維譜圖中引入區域查詢點，有效建立譜圖空間的幾何變換，并運用均值聚類及譜變換高效實現譜圖局部區域的配準。

首先，建立源模型譜圖的包圍盒（BoundingBox），均勻放置m×m個查詢點，確定輪廓內有效查詢點集。進而，為每個有效查詢點依據半徑r進行鄰域搜索，提取該查詢點所對應的輪廓點集。其次，根據源模型的輪廓點及已經建立的與目標模型的配準點對，計算譜圖的幾何變換：

搜索區域內所有輪廓點，構建變換空間Φ：，采用Mean-shift算法獲得變換空間Φ的中心變換參數，確定為當前查詢點Si的幾何變換參數。通過查詢點Si以及幾何變換參數，我們獲得目標模型的區域匹配點。

進而，所有的查詢點及其變換參數，即可得到目標譜圖區域中的對應點集合Fs。

圖3（a）左圖中的綠色點為譜圖輪廓內的區域查詢點，通過設置每個查詢點的搜索區域（如黑色圓所示），確定搜索區域的輪廓點。進而，通過輪廓點集及譜配準點對，計算變換空間，通過聚類獲得變換空間的中心參數，作為查詢點變換參數，從而獲得目標模型的內部區域點，如圖3（a）右圖所示。

圖3（b）為人馬的上半身局部模型及其完整模型的二維譜圖表示，依據輪廓對應以及譜圖變換，獲得的有效局部匹配區域，如圖中黃色為局部模型的譜圖，藍色區域為完整模型中對應的局部區域。圖3（c）為從譜域到空域的轉換，非剛性模型在空域中局部區域的提取。

最終，依據所確定的源模型與目標模型所對應的譜圖區域，我們通過區域搜索與特征相似性度量，實現空域中模型的局部結構匹配。

Hausdorff距離是描述兩組點集之間相似程度的一種量度，計算時首先要計算兩組點集之間的有向Hausdorff距離，有向的Hausdorff距離被定義為：

其中d（x， y）表示點集X與點集Y間的馬氏距離（公式10）。公式10中，是源模型的點集，是目標模型中對應的局部區域的點集，S是和的協方差矩陣。

如圖4為兩組非剛性模型的局部匹配實驗結果。

本文的算法主要步驟可歸納如下：

輸入：源模型M1和目標模型M2

輸出：局部區域匹配點對D（M1，M2）

Step1：最優二維譜圖提取：通過拉普拉斯映射及ICP方法，提取模型的最優二維譜圖表示（P，Q）。

Step2：譜圖輪廓配準：通過輪廓提取與形狀上下文算法得到模型的譜圖輪廓點集與配準點對C。

Step3：譜變換：設置源模型的查詢點集Si，計算鄰域內輪廓點的幾何變換空間，通過Mean-shift獲得中心變換點集參數。

Step4：譜圖區域配準：通過譜變換函數，計算目標模型的對應區域點集，

Step5：模型局部匹配：采用區域搜素與相似性特征度量，計算模型的區域匹配點對D。

2? 實驗及結果分析

本文方法的實驗平臺為Intel（R）Core（TM）3.2 GHz CPU，8 GB內存的惠普PC，并使用VC++6.0，Matlab圖形可視化軟件開發環境。

實驗中，我們使用標準的非剛性三維模型數據庫SHREC2010、SHREC2011。SHREC2010數據庫中包含10個類，每類中含有20個姿態各異的三維模型，SHREC2011數據庫包含600個非剛性三維模型，分為30類，每類有20種不同姿態模型。

我們分別對本文算法、ICP[4]、文獻[17]、SGC[18]和SHOT[19]進行了綜合分析。圖5顯示了基于SHREC2010數據庫與SHREC2011數據庫的PR曲線結果。

ICP的基本原理是通過就近點之間的最小距離約束模型的配準過程，要求配準ICP的基本原理是通過就近點之間的最小距離約束模型的配準過程，要求配準模型具有較高的相似性，而對于不相似的模型會出現較大誤差。同時，該方法只能實現剛性配準，對于具有不同姿態及局部形變的同類模型會產生較大差異。

文獻[17]的算法使用了融合空間結構特征的方法，通過提取模型優化后的骨架，轉換為骨架樹進行基于圖結構的篩選，并融入空間結構特征與幾何細節，最后利用EMD距離方法實現模型匹配，這一算法可以有效的實現局部匹配，但是總體匹配時間較長。

SGC[18]是對于三維點云的穩定幾何質心特征進行編碼的局部描述符，如圖8中PR曲線可見，其在三維模型局部匹配中具有較好的效果，但是，由于需要從每個體素提取的幾何質心和點密度特征來構造描述符，需要消耗大量時間。

SHOT[19]通過查詢點的空間方向直方圖特征實現局部匹配，對于扭曲比較大的非剛性三維模型，會產生較大的差異，而且對于有噪聲的模型魯棒性比較差。

本文提出了基于譜空間變換的局部匹配方法，將復雜的三維模型通過拉普拉斯算子映射到譜空間，建立最優的二維譜特征表示，其有效保持了模型的內蘊形狀特性。進而，基于譜空間的幾何變換，實現二維譜圖配準。最終通過查詢點及區域搜索，實現局部區域匹配。本方法基于二維譜圖進行區域搜索與匹配，不僅大幅度減少計算時間，而且對于非剛性變換及噪聲模型具有極強的魯棒性。

圖6（a）分別是SHREC2010數據庫中人馬和螞蟻的局部匹配結果，圖6（b）是SHREC2011數據庫中恐龍1和恐龍2的局部匹配結果。可見，本文方法在不同種類的非剛性模型局部匹配中具有極強的穩定性。

表1是ICP算法、SHOT算法、SGC算法以及本文算法在不同模型上的檢索率;圖7為不同方法在不同測地誤差下的配準率。可以看出，本算法的性能明顯優于其他算法。

為了驗證本文算法的魯棒性，本文在實驗中對原模型隨機加入高斯噪聲。如圖7（a）為螞蟻模型以及加入4%，8%，12%的隨機高斯噪聲的模型。圖7（b）為對應模型的最優二維譜圖表示，可見，不同噪聲的螞蟻模型的二維譜圖變化非常小，具有較強的魯棒性。圖7（c）為每個算法對噪聲的魯棒性測試結果。

3? 結語

本文面向非剛性三維模型的局部匹配與檢索的需求，提出高效、穩定的三維模型形狀分析與局部匹配方法。通過基于拉普拉斯映射的譜嵌入，構建最優二維譜特征描述，其不僅實現了有效降維，而且有效保留了模型的統一內蘊結構特征。我們通過二維譜空間進行局部輪廓配準，有效建立譜空間的幾何變換，實現區域的配準與相似性度量。一系列實驗驗證了本方法對于不同姿態及不同種類模型的識別具有較強的穩定性與高效性。在未來的工作中，我們將深度開展模型的協同分割與語義標注的研究，建立高層次的模型結構分割與描述機制，并對殘缺模型修補進行更進一步的研究。

參考文獻

[1]張數， 楊德宏. 數字近景攝影測量的二維影像三維建模的關鍵技術應用[J]. 軟件， 2018， 39（2）： 133-138.

[2]劉尚武， 魏巍， 矯宇鵬. 三維模型的規格化表示與存儲方法研究[J]. 軟件， 2016， 37（4）： 29-31.

[3]李慧霞， 高梓豪. 室內智能移動機器人規則物體識別與抓取[J]. 軟件， 2016， 37（02）： 89-92.

[4]Besl P， Mckay N. A method for registration of 3-d shapes. IEEE Transon PAMI， 1992， 14（2）： 239-256.

[5]Ferreira A， Marini S， Attene M， et al. The saurus based 3D Object Retrieval with Parin whole Matching[J]. Int. J. Comput. Vis. 2009， 89（2/3）： 1405-1573.

[6]Wessel R， Klein R. Learning the compositional structure of manmade objects for 3D shape retrieval[C]//Proceedings of Euro graphics 2010 Workshop on 3D Object Retrieva1. Norrk-oping， Sweden： Springer， 2010： 39-46.

[7]Barequet G， Sharir M. Partial surface matching by using directed footprints[J]. Computational Geometry： Theory and Applications， 1999， 12（1-2）： 45-62.

[8]Barequet G， Sharir M. Partial surface and volume matching in three dimensions[J]. IEEE Transactions on Pattern Analy sis and Machine Intelligence， 1997， 19（9）： 929-948.

[9]Shilane P， Funkhouser T. Selecting distinctive 3D shape descriptors for similarity retrieval[C]//IEEE International Conference on Shape Modeling And Applications. Matsushima， Japan： IEEE Cornputer Society， 2006， ： 108-117.

[10]Shilane P， Funkhouser T. Distinctive Regions of 3D Surfaces[J]. ACM Transactionson Graphics， 2007， 26（2）： 1-15.

[11]Lipman Y， Chen X， Daubechies I， et al. Symmetry factored embeding and distance[J]. ACM Transactions on Graphics， 2010， 29（4）： Article No. 103.

[12]Sahillioglu Y， Yemfz Y. Minimum-distortion isometric shape correspondence using EM algorithm[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2012， 34（11）： 2203-2215.

[13]Sun J， Ovsjanikov M， Guibas L. A concise and provably informative multi-scale signature based on heat diffusion[J]. Computer Graphics Forum， 2009， 28（5）： 1383-1392.

[14]Aubry M， Schlickewei U， Cremers D. The wave kernel signature： a quantum mechanical approach to shape analysis[C]// Computer Vision Workshop. Washington， DC： IEEE Computer Society， 2011： 1626-1633.

[15]Belongies， Malikj. Shape matching and object recognition using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2002， 24： 509-52.

[16]Yusuke Yoshiyasu A， Eiichi Yoshida A， Leonidas Guibas B. Symmetry aware embedding for shape correspondence [J]. National Institute of Advanced Industrial Science and Technology. 2016.

[17]韓麗， 程遠， 融合空間結構特征的三維模型局部檢索方法[J]. 微型機與應用， 2013， 32（15）.

[18]Tang K， Song P， Chen X. Signature of geometric centroids for 3d local shape description and partial shape matching[J]. Asian Conference on Computer Vision， 2016： 311-326.

[19]Tombari F， Salti S， Stefano. Unique signatures of histograms for local surface description[J]. ECCV. 2010： 356-369.

[20]盧超， 黃蔚， 胡國超. 基于圖形數據結構的復雜對象建模設計[J]. 軟件， 2015， 36（12）： 220-223.

[21]張媛媛， 楊洪娟， 朱匯龍. 面向圖像視覺特征檢索的高維索引結構研究[J]. 軟件， 2018， 39（1）： 105-109.

[22]任忠良. 一種基于SIFT特征的快速圖像匹配算法[J]. 軟件， 2015， 36（6）： 53-57.