基于最優最小生成樹的三維模型形狀優化方法

韓麗 劉書寧 于冰 徐圣斯 唐棣

摘 要：針對海量、異構、復雜的三維模型高效形狀分析需求，提出基于最優最小生成樹的三維模型形狀優化方法。首先基于三維模型的初始最小生成樹（3D-MST）構造模型的結構描述;其次通過拓撲結構與幾何形狀檢測并結合雙邊濾波與熵權值分布進行局部優化，獲得模型的優化MST表示;最終基于優化的Laplacian譜特征，結合薄板樣條函數（TPS），實現模型的形狀分析與相似性檢測。實驗結果表明，所提方法不僅有效地保留了模型的形狀特征，而且可高效地實現復雜模型的稀疏優化表示，能進一步提高幾何處理與形狀檢索的高效性和增強魯棒性。

關鍵詞：最小生成樹; 體積; 雙邊濾波; 熵權值; 譜嵌入

中圖分類號： TP391.41

文獻標志碼：A

文章編號：1001-9081（2019）03-0858-06

Abstract： For the efficient shape analysis of massive， heterogeneous and complex 3D models， an optimization method for 3D model shape based on optimal minimum spanning tree was proposed. Firstly， a model description based on 3D model Minimum Spanning Tree （3D-MST） was constructed. Secondly， local optimization was realized by topology and geometry detection and combination of bilateral filtering and entropy weight distribution， obtaining optimized MST representation of the model. Finally， the shape analysis and similarity detection of the model were realized by optimized Laplacian spectral characteristics and Thin Plate Spline （TPS）. The experimental results show that the proposed method not only effectively preserves shape features of the model， but also effectively realizes sparse optimization representation of the complex model， improving the efficiency and robustness of geometric processing and shape retrieval.

Key words： Minimum Spanning Tree （MST）; volume; bilateral filtering; entropy weight; spectral embedding

0 引言

隨著三維掃描、三維重建技術的發展，三維模型已經廣泛應用于建筑、醫療、教育、影視娛樂等各行各業，尤其隨著互聯網及大數據技術的發展，三維模型的數據量與復雜度更是顯著提高，基于三維模型優化的形狀分析方法更顯得尤為重要。

三維模型形狀分析的關鍵在于特征描述符的選擇，通過對比特征描述符獲得模型的相似性。目前常用的三維模型形狀特征描述符有基于幾何特征統計直方圖的方法、基于骨架拓撲結構的方法、基于視覺相似投影的方法以及基于譜分析的方法。其中，基于幾何特征統計直方圖的方法是通過計算模型頂點和網格的幾何信息分布特征來分析三維模型，如Osada等[1]提出了一種形狀分布（Shape Distribution， SD）直方圖算法，選擇恰當的形狀函數度量模型，如通過計算頂點間的歐氏距離獲得模型的形狀分布直方圖; Pickup等[2]提出基于模型表面積的分布直方圖（Surface Area， SA）。該類方法能有效描述模型的全局特征，但是忽略了模型的局部特征。李海生等[3]針對局部細節特征提出一種基于模型內二面角的分布直方圖的特征描述方法，但該方法在噪聲干擾、網格簡化時，魯棒性較差。基于骨架拓撲結構的方法是通過簡化算法獲取模型的拓撲結構，有效去除模型的冗余信息，提供更直觀、簡潔的形狀描述，被廣泛應用于模型的形狀匹配與檢索，如Reeb圖[4]、中軸線法[5]。這類方法雖然對擾動噪聲具有魯棒性，能夠表現出模型的整體特征，但是缺乏對細節的描述，并且計算量大。為此，王飛等[6]針對局部細節特征的不足，提出一種拓撲與形狀特征相結合的三維模型描述方法。該方法雖然能較好地提取模型的局部特征形狀，但是對于高精度的模型還需深入研究。 基于視覺相似方法是通過比較多視角下三維模型的二維圖像進行匹配。如文獻[7]利用馬爾可夫鏈（Markov Chain， MC）模擬同一物體多視角的統計特性來進行模型的相似性分析;文獻[8]提出一種多視角與圖方法結合的多視角權重匹配方法，具有較好的效果，但是該類方法不具有旋轉、縮放的特性，且計算量大。

近年來，譜分析的方法廣泛應用于三維模型的檢索與匹配[9-12]。基于譜分析的方法是利用拉普拉斯算子將三維模型映射到譜特征空間，不僅能較好地保持模型的內蘊屬性，具有等距不變性，并且能夠有效提高非剛性模型的匹配精度。例如，Lipman等[9]基于譜方法實現全局內蘊的檢測;Sahillioglu等[10]在譜域構造初始化匹配，采用貪婪算法結合等距性優化匹配結果;Sun等[11]基于模型表面熱擴散提出熱核特征（Heat Kernel Signature， HKS）;Aubry等[12]將波動方程引入模型，提出波核特征（Wave Kernel Signature， WKS）的形狀分析方法。譜特征由于具有較強的穩定性與抗噪性，被進一步應用于模型對稱性檢測、形狀配準、深度學習中。文獻[13]使用選舉和譜分析方法提出一種模型局部內蘊對稱檢測算法;文獻[14]基于熱核分布識別精度不突出問題，提出熱模態特征，提高了模型的檢索精度。

然而，針對既能突出模型的局部細節，又能反映模型的整體特征的高效分析算法仍需進一步研究。本文提出一種兼顧模型全局結構與局部幾何細節的模型形狀分析與匹配算法，通過拓撲結構與幾何形狀檢測，并結合圖像中雙邊濾波的思想與熵權值分布實現三維模型最小生成樹（Three-dimensional model Minimum Spanning Tree， 3D-MST）的優化，構造模型的稀疏表示;進而獲得優化的3D-MST譜特征;最終基于薄板樣條函數（Thin Plate Spline， TPS），實現模型的形狀分析與相似性檢測，本文方法有效提高了模型優化表示與形狀分析效率。

1 相關理論

1.1 三維模型最小生成樹

最小生成樹（Minimum Spanning Tree， MST）是一個優化的數學模型，可有效描述模型的拓撲結構，被廣泛用于網絡設計[15]和數據挖掘[16]等領域。其經典算法有Prim算法和Kruskal算法。Prim以任意頂點出發，逐次加入生成樹點集中最近的模型頂點，適用于邊稠密的最小生成樹。而Kruskal算法算法適用于邊稀疏的最小生成樹。為了有效保持復雜模型的形狀結構，本文采用Prim算法構建初始的三維最小生成樹（3D-MST）。

圖1為虎的原始網格模型、三維模型最小生成樹以及基于本文算法優化后的三維模型最小生成樹。

1.2 幾何形狀特征

穩定有效的形狀特征描述是形狀分析的至關重要因素。最常用的形狀描述符有高斯曲率（Gaussian Curvature， GC）[17]、可視化體積[18] 、形狀直徑（Shape Diameter Function， SDF）[19]、平均測地線距離（Average Geodesic Distance， AGD）[20]、形狀分布（SD）[1]等。

本文基于普林斯頓評價標準[21]，論證分析了GC、SDF、AGD、D2（基于距離的函數，采樣任意兩個頂點之間的距離）等特征在TOSCA數據庫上實現非剛性三維模型檢索的穩定性。評價結果如表1及圖2所示。其中：

1）最鄰近準確度（Nearest Neighbor， NN）：表示在檢索結果最接近檢索模型的數目M與返回模型數目N的比值，NN值越大表示檢索效果越好。

2）第一層級（First-Tier， FT）和第二層級（Second-Tier， ST）：FT為當K=C-1時的查全率，ST表示當K=2×（C-1）時的查全率。其中：C表示數據集中所有相關模型總數量，K表示檢索返回的相關模型數量。

3）E度量（E Measure， EM）其值表示為：

4）折扣積累收益（Discounted Cumulative Gain， DCG ），考慮了結果所在的位置，位置越靠前準確越高則權重越大，如果第i個模型為正確的檢索結果則為1，否則為0，這個結果通過除以最優的排序結果得到最終DCG，計算公式如下：

其中k表示模型庫中模型的數量。

以上的5種評價指標其理想值均為1， 其值越大表明檢索效果越好。P-R曲線反映了查準率（P）與查全率（R）之間的函數關系，曲線越高表明特征檢索效果越好。由表1和圖2可見，可視化體積[18]相對于其他特征具有更高的區分性、穩定性，因此本文引入模型的可視化體積[18]以及熵權值分布，有效優化模型的形狀表示。

2 三維模型MST優化表示

為獲取穩定的形狀檢測，減少噪聲的影響，本文從局部雙邊濾波到整體信息熵優化，高效實現模型的最優表示。

2.1 基于雙邊濾波的局部優化

雙邊濾波是一種非線性濾波的方法，廣泛應用于圖像處理中[22]，可以達到保邊去噪的效果。濾波器由兩個測量函數構成：一個幾何空間的距離測量，決定濾波系數d;另一個是像素灰度的特征測量，決定濾波系數r。像素的輸出值依賴于鄰域的像素值的加權組合。

本文基于圖像雙邊濾波思想與信息熵理論，通過測地線距離度量幾何空間差異，采用體積特征度量模型的特征差異，與三維模型MST相結合構造模型的優化表示。

距離濾波系數為：

圖3為victoria模型濾波前后的局部頂點的體積特征對比折線圖，可見濾波后的體積特征，不僅保持模型的整體形狀特征，而且有效實現模型的平滑過渡。

2.2 基于信息熵的全局優化

熵本身是熱力學概念，用來表達分子狀態雜亂程度的一個物理量。美國信息論創始人香農引入信息熵用來表示信息量，信息熵越大表示信息量越小，反之信息量越大。近年來信息熵被廣泛引用于圖形圖像的檢索與特征選擇[23]。但信息熵強調整體模型的特征分布，忽略了模型的局部信息。本文引入局部濾波的形狀特征，結合信息熵分布，實現全局的模型優化表示。

若d≤γ，則保留父節點，刪除其子節點;若d>γ，則兩節點均保留。

圖4分別表示victoria模型的最小生成樹、模型的特征點分布以及最優最小生成樹。模型的特征點不但降低了模型的密度，而且可以提高模型的檢索效率。

圖5為本文方法在不同模型上的優化結果， 從左到右依次為優化30%、50%、70%的MST。

圖7為不同模型在不同優化率下的熵權分布情況。由折線圖可以看出，對于同類模型雖然優化率不同，但模型的熵權概率分布相似（如站和抬腿），表明了體積的熵權值，具有穩定的形狀描述能力，能夠在不同優化率下很好地保留模型的形狀特征，對噪聲具有較強的魯棒性，能夠有效地識別不同種類模型（如人體模型與狼模型）。

3 基于譜圖的形狀匹配

3.1 模型特征點的譜嵌入

拉普拉斯映射的譜嵌入將高維數據嵌入到低維空間，可以有效保持模型的內蘊特征。本文基于最優最小生成樹建立拉普拉斯矩陣，計算模型的譜特征 [24-25]，并結合TPS配準方法，實現模型的形狀配準與分析。

如圖8表示，其中第一列為初始模型，第二列為模型的拉普拉斯譜域，第三列為實現MST優化后的稀疏譜圖。所示，稀疏表示的譜圖有效保持原有模型的整體結構特征。

綜上所述，完整的最優最小生成樹的模型相似性度量算法步驟如下：

輸入： 待匹配的模型X，Y;

輸出： 模型的譜域配準率sim（X，Y）。

步驟1 提取模型的初始MST;

步驟2 提取模型的內部可視化體積并使用雙邊濾波進行優化;

步驟3 計算模型的熵權值;

步驟4 利用熵權分布及初始MST獲取模型特征點;

步驟5 獲取特征點的最優MST并提取其譜域;

步驟6 利用TPS獲取模型的配準率sim（X，Y）。

如圖9表示不同模型間的配準結果。

4 實驗結果與分析

本文實驗在TOSCA三角網格數據庫（簡稱TOSCA數據庫）上進行測試，所有實驗都在平臺為Pentium 3.2GHz CPU， 8GB內存Windows7操作系統的PC上完成的，并使用VC++6.0和OpenGL2.0圖形庫作為可視化開發環境。

本文算法主要由四階段組成，1）原始模型最小生成樹的生成;2）基于雙邊濾波的局部特征優化;3）基于熵權值分布的整體3D-MST優化;4）基于譜圖的模型匹配。

為了驗證本文模型優化方法的穩定性，將本文方法與文獻[25]方法和CPD[27]在TOSCA數據庫進行實驗對比。該數據中包含12個類，148個模型非剛性模型，盡管該數據庫規模較小，但是選取的模型的不同姿勢具有代表性。該模型數據庫中的部分模型如圖10所示。

圖11（a）、（b）、（c）為本文方法、文獻[25]方法與CPD方法的譜域配準實驗結果，圖11（d）為稀疏譜域配準點在空域中模型形狀匹配結果顯示。

圖12表示基于三種不同方法，以貓模型為待檢索樣本，在數據庫中獲得的三維模型檢索結果。

可見本文方法對于同類模型不僅配準率穩定，而且模型頂點優化率高、更為高效（如表2所示），對于不同類模型更能進行有效的區分。因此運用本文方法不僅實現模型的優化稀疏表示以及形狀檢測，更有效提高模型的檢索效率。

如圖13所示，不同優化率下，同類模型之間具有較高的匹配度。當優化率為80%以下時，稀疏后的模型能夠保留穩定的形狀信息，具有較高的模型識別度和匹配度，但是當優化率大于80%時，由于剩下的形狀信息較少，配準率急速下降。因此，實驗中為了有效保留形狀信息，本文約束模型的優化率取為80%。

圖14為相關方法的P-R曲線，可見，本文方法對于同類模型不僅配準穩定與精準，對于不同類模型更能進行有效的區分。

5 結語

針對三維模型的高效形狀分析與檢索需求，提出了一種三維模型最小生成樹優化表示算法。通過內部可視化體積獲取模型頂點的熵權分布，運用熵權值對模型MST自下而上進行三維模型的優化，最終得到三維模型的MST優化表示。

為了驗證優化模型的形狀穩定性，本文提取優化模型的譜特征，運用TPS方法，進行模型的配準與相似性分析，實驗結果進一步驗證了本文方法有效保持模型的形狀特征，實現了復雜模型的稀疏優化表示，為進一步的模型幾何處理以及檢索等應用奠定了基礎。本文方法使用了TPS非剛性配準算法，在大規模線性求解方面效率較低，容易產生不穩定的解，在建立點對點的對應關系時可能會出現配準誤差。在接下來的工作中，將基于現有的研究與理論進一步提高模型的配準效率。

參考文獻 （References）

[1] OSADA R， FUNKHOUSER T， CHAZELLE B， et al. Shape distributions [J]. ACM Transactions on Graphics， 2002， 21（4）： 807-832.

[2] PICKUP D， SUN X， ROSIN P L， et al. Shape retrieval of non-rigid 3D human models [C] // 3DOR '14： Proceedings of the 7th Eurographics Workshop on 3D Object Retrieval. Aire-la-Ville， Switzerland： Eurographics Association， 2014： 101-110.

[3] 李海生，孫莉，吳曉群，等.基于模型內二面角分布直方圖的非剛性三維模型檢索[J].計算機輔助設計與圖形學學報，2017，29（6）：1128-1134.（LI H S， SUN L， WU X Q， et al. Non-rigid 3D shape retrieval based on inner dihedral angle histogram [J]. Journal of Computer-Aided Design and Computer Graphics， 2017， 29（6）： 1128-1134.）

[4] HILAGA M， SHINAGAWA Y， KOHMURA T， et al. Topology matching for fully automatic similarity estimation of 3D shapes [C]// SIGGRAPH '01： Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques. New York： ACM， 2001： 203-212.

[5] DU H， QIN H. Medial axis extraction and shape manipulation of solid objects using parabolic PDEs [C]// SM '04 Proceedings of the 9th ACM Symposium on Solid Modeling and Applications. Aire-la-Ville， Switzerland： Eurographics Association， 2004： 25-35.

[6] 王飛，張樹生，白曉亮，等.拓撲和形狀特征相結合的三維模型檢索[J].計算機輔助設計與圖形學學報， 2008， 20（1）： 99-103.（WANG F， ZHANG S S， BAI X L， et al. 3D model retrieval based on both the topology and shape features [J]. Journal of Computer-Aided Design and Computer Graphics， 2008， 20（1）： 99-103.）

[7] LI F， DAI Q， XU W， et al. Statistical modeling and many-to-many matching for view-based 3D object retrieval [J]. Signal Processing Image Communication， 2010， 25（1）：18-27.

[8] GAO Y， DAI Q， WANG M， et al. 3D model retrieval using weighted bipartite graph matching [J]. Signal Processing： Image Communication， 2011， 26（1）： 39-47.

[9] LIPMAN Y， CHEN X， DAUBECHIES I， et al. Symmetry factored embedding and distance[J]. ACM Transactions on Graphics， 2010， 29（4）： Article No. 103.

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

[11] 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.

[12] AUBRY M， SCHLICKEWEI U， CREMERS D. The wave kernel signature： a quantum mechanical approach to shape analysis [C]// Proceedings of the 2011 IEEE International Conference on Computer Vision Workshops. Washington， DC： IEEE Computer Society， 2011： 1626-1633.

[13] 姜巍，徐凱，程志全，等.一種通用的局部內蘊對稱檢測算法[J].計算機輔助設計與圖形學學報，2013，25（7）：974-979.（JIANG W， XU K， CHENG Z Q. et al. A generalized algorithm for partial intrinsic symmetry detection [J]. Journal of Computer-Aided Design and Computer Graphics， 2013， 25（7）： 974-979.）

[14] 匡振中，李宗民，田偉偉，等.熱模態特征與非剛體模型檢索[J].計算機輔助設計與圖形學學報，2015，27（8）：1426-1433.（KUANG Z Z， LI Z M， TIAN W W， et al. Modal feat feature and non-rigid 3D model retrieval [J]. Journal of Computer-Aided Design and Computer Graphics， 2015， 27（8）： 1426-1433.）

[15] LAU L C， NAOR J S， SALAVATIPOUR M R， et al. Survivable network design with degree or order constraints [J]. SIAM Journal on Computing， 2017， 39（3）：1062-1087.

[16] 朱利，邱媛媛，于帥，等.一種基于快速k-近鄰的最小生成樹離群檢測方法[J].計算機學報，2017，40（12）：2856-2870.（ZHU L， QIU Y Y， YU S， et al. A fast kNN-based MST outlier detection method [J]. Chinese Journal of Computers， 2017， 40（12）： 2856-2870.）

[17] GAL R， COHEN-OR D. Salient geometric features for partial shape matching and similarity [J]. ACM Transactions on Graphics， 2006， 25（1）： 130-150.

[18] HAN L， HU J Y， LI L. Volume-based skeleton extraction [J]. ICIC Express Letters， 2014， 8（3）： 859-865.

韓麗， 胡江月. 體積分布的三維模型形狀分析方法[J]. 計算機工程與應用， 2015， 51（23）：195-198.（HAN L， HU J Y. Shape analysis method of 3D models based on volumetric distribution [J]. Computer Engineering and Applications， 2015， 51（23）： 195-198.）

[19] SHAPIRA L， SHAMIR A， COHEN-OR D. Consistent mesh partitioning and skeletonisation using the shape diameter function [J]. Visual Computer， 2008， 24（4）： 249-459.

[20] SHAPIRA L， SHALOM S， SHAMIR A， et al. Contextual part analogies in 3D objects [J]. International Journal of Computer Vision， 2010， 89（2/3）： 309-326.

[21] SHILANE P， MIN P， KAZHDAN M， et al. The Princeton shape benchmark [C]// SMI '04Proceedings of the 2004 Shape Modeling Applications. Washington， DC： IEEE Computer Society， 2004： 167-178.

[22] YANG Q. A non-local cost aggregation method for stereo matching [C]// CVPR '12 Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2012： 1402-1409.

[23] AFSAL S， RAFEEQ A K， JOTHYKUMAR J， et al. A novel approach for palm print recognition using entropy information features [C]// Proceedings of the 2016 International Conference on Wireless Communications， Signal Processing and Networking. Piscataway， NJ： IEEE， 2016.

AFSAL S， RAFEEQ A K， JOTHYKUMAR J， et al. A novel approach for palm print recognition using entropy information features [EB/OL]. [2018-07-12]. https：//ieeexplore.ieee.org/document/7566374/.

[24] 王年，周梅菊，張江，等.基于最小生成樹的LAPLACE譜圖像匹配算法[J].系統仿真學報，2009，21（17）：5481-5485.（WANG N， ZHOU M J， ZHANG J， et al. Laplacian spectrum image matching algorithm based on minimum spanning tree [J]. Journal of System Simulation， 2009，21（17）： 5481-5485.）

[25] 韓麗，顏震，徐建國，等.基于顯著特征譜嵌入的三維模型相似性分析[J].模式識別與人工智能，2015，28（12）：1119-1126.（HAN L， YAN Z， XU J G， et al. Three-dimensional model similarity analysis based on salient features spectral embedding [J]. Pattern Recognition and Artificial Intelligence， 2015， 28（12）： 1119-1126.）

[26] CHUI H， RANGARAJAN A. A new point matching algorithm for non-rigid registration[J]. Computer Vision and Image Understanding， 2003， 89（2）：114-141.

[27] MYRONENKO A， SONG X. Point set registration： coherent point drift [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2010， 32（12）： 2262-2275.