基于曲率特征的三維模型對稱性檢測技術

摘 要： 針對三維模型上對稱性提取效率不高的問題，在此提出了一種改進的對稱性檢測方法，該方法通過分析和計算三維模型上曲面的曲率特征，得到模型表面上凸起或者凹陷的褶皺線，再將褶皺線作為分析檢測曲面對稱性的依據，結合變換空間聚類的方法，計算得到模型整體的對稱變換。實驗結果表明，該方法通過以簡單的褶皺線來描述和刻畫模型上的復雜曲面，不但能夠得到正確的對稱變換，還能夠大幅減少算法的計算量，加速提取過程。

關鍵詞： 三維模型處理； 幾何建模； 對稱性檢測； 三維模型曲率特征； 聚類方法

中圖分類號： TN964?34 文獻標識碼： A 文章編號： 1004?373X（2013）08?0089?04

隨著CAD及網絡技術的快速發展，三維模型的創建和應用越來越廣泛，人們每天都在不斷地通過手工或3D掃描儀來構建產生虛擬的現實場景及物體，并把它們使用在不同的應用中，例如建筑設計，游戲娛樂，醫學分析等。這些三維模型本身大部分都具有對稱性的特征，比如建筑，人體，飛機，家具等，這些物體的整體或者部分符合各種各樣的對稱關系，如直升飛機螺旋槳葉片之間符合45°的旋轉關系，汽車車輪之間符合位移關系，大部分的建筑物符合關于中軸對稱的反射關系。對稱性檢測技術就是用來探測這些對稱性關系，從而使得人們能夠利用這些對稱性信息到不同的應用上，例如加速模型編輯過程，模型壓縮等。

1 相關工作

近年來，國內外對于對稱性檢測已經有了不少的研究，大體上分為2種，一種是針對計算模型的內部的（Intrinsic）對稱性；另有一種是針對外部的（Extrinsic）對稱性。內部的對稱性是指模型本身固有的變換特征，并且這種特征不隨模型的姿態改變。像Xu等人提出的針對三維模型內部的反射對稱變換的探測算法[1]。能夠檢測出模型上固有的，與模型本身的姿態無關的反射變換，通過在曲面上采樣一些點對，使用投票策略來得到一個平滑的標量場，以此來衡量和估算模型上的點是模型固有反射對稱軸（Intrinsic Reflectional Symmetry Axis，IRSA）的可能性。然后再通過Grass?fire算法來迭代計算最終的IRSA以及與其對應的曲面。這種方法雖然能夠計算與模型姿態無關的對稱性，但是僅僅對反射變換有效，且非常耗時。而相對而言，模型的外部對稱性的定義就較為嚴格，它是指模型上近似符合某種變換的曲面特征。變換種類可以是旋轉、位移和反射。Mitra等人[2]就曾提出了一種既能抽取反射對稱，也能同時抽取旋轉和位移對稱變換的方法，它通過在變換空間中聚類采樣點對，使得顯著的變換被抽取，然后再擴散得到對稱曲面。同樣，Berner和Bokeloh等人[3?4]從另一種角度，使用滑動分析的方法來提取曲面特征，然后提出了一種基于圖（Graph）的匹配算法來獲得對稱性，但是算法整體效率不高。上述的方法雖然各有特點，但是都不高效。為了得到一個較為高效的算法，在此使用曲率作為入手點，分析曲面特征，計算得到曲面上凹陷或凸起的線條位置，稱為褶皺線。再利用基于變換空間聚類的對稱性檢測方法[2]，在褶皺線的基礎上分析曲面特征，抽取對稱性。這樣以“線”代“面”，能極大地減少計算量，提高算法性能，并且能夠提升算法對于相對細小的對稱關系的敏感性。

2 基于曲率特征的褶皺線提取

曲率是模型表面的基本特征之一，它描述了三維曲面的局部特性，一定程度地刻畫和表達了三維曲面，且具有在任何剛性變換下保持不變的特性，因此，在此可以借助這種不變性，來分析和獲得相似曲面間的對稱變換。通過分析曲率的大小，可以得到一些高曲率或者低曲率的區域，稱為特征區域，然后對特征區域進行收縮操作，通過不斷收縮，就能得到一些褶皺線，以褶皺線作為對稱性抽取的依據能夠大大較少計算量，因為大部分的特征不明顯的頂點數據已經被過濾掉。2.1節與2.2節將著重介紹特征區域及褶皺線的計算方法。

2.1 特征區域計算

特征區域是模型上凹陷或者隆起的區域，要獲得大致的特征區域，首先要估算模型上每個點的曲率大小。對于一個輸入的含有N個頂點的三維模型，可以使用文獻[5]提出的方法，計算出模型上任意一點Vi的曲率值[Kimax] （可以根據應用背景選取是最大曲率還是最小曲率，或者兩者皆可，本文以最大曲率為例）。但是得到的曲率值可能會含有高頻的噪聲，從而使曲率相對于實際值偏大或者偏小，這時就需要做一些針對噪聲的處理。通過大量實驗證明，選用均值濾波能夠很好的過濾噪聲。即對于Vi，其修正后的曲率值[Kimax]等于與Vi相鄰的頂點的曲率的平均值。定義集合[F=fi1≤i≤N]表示特征區域，fi與頂點Vi一一對應，且[fi∈0，1]，表示頂點Vi是否被包含在特征區域中。則F中最初的fi可以使用如下公式計算得到：

[fi=1，Kimax>ε0，Kimax≤ε]

式中[ε]為閥值參數，通過實驗發現，當[ε=0.8Kmax，][Kmax=max1≤i≤NKimax]時，能得到較好的效果。特征區域的計算結果如圖1所示。

2.2 褶皺線提取

直觀上講，褶皺線可以近似地看成模型上的棱，角，凹槽的中心位置，它可以在一定程度上表達曲面的特征。通過前面的方法，已經可以得到一個大致特征區域，接下來可以通過不斷地收縮特征區域來最終得到褶皺線。但是，如果僅僅簡單的一層層消去特征區域的外層頂點，有可能破壞整個特征區域的連通性，從而使得到的褶皺線不連續，這樣的不連續的褶皺線并不能很好地保留曲面的特征。因此，為了保證收縮后特征區域的連通性，對于模型上的每一個頂點Vi，定義：

[Ci=k=0ni-1fuik-fui（k+1）modni]

稱Ci為頂點Vi的復雜度，其中ni表示Vi周圍一圈點的個數，[uik]表示這一圈點中第k個頂點的編號。對于在特征區域邊界上的頂點，其復雜度為2，而在特征區域內部的頂點，由于其鄰接的頂點也在特征區域內部，其復雜度為0。當特征區域收縮成線后，線上的頂點的復雜度為4，若該點為若干條線的交點，則其復雜度大于4。注意到如果特征區域收縮成線狀的話，其復雜度會變成4，但是如果簡單的刪掉復雜度等于2的邊界點，卻會造成線狀特征區域在端點處產生退化，因為端點的復雜度也是2。因此，需要定義如下兩個輔助集合：

[O=vk=0nvfuvk=nv]

鄰接頂點都在特征區域上的點都包含在集合O中，如果特征區域收縮成線狀的話，線上必定沒有集合O中的點。通過集合O可以得到其中每一個點的鄰接頂點的并集：

[D=v?p∈O，且v∈up]

因此，線狀的特征區域的端點必然不包含在D中。所以，在收縮的時候，只需不斷地從特征區域上刪除在D中且復雜度等于2的頂點，即可維持特征區域的連通性。因此計算褶皺線的算法步驟為：

（1）計算特征區域上頂點的復雜度以及集合D。

（2）刪除集合D中復雜度為2的邊界頂點，若沒有頂點被刪除，則完成計算，否則跳至步驟（1）。

通過上述步驟，即可得到如圖2所示的褶皺線，圖中黃色的線條即為圖1所示的特征區域通過上述方法得到的褶皺線。

3 對稱性檢測

褶皺線反應了曲面的一些固有的特征，可以利用這種特征來分析曲面間的對稱關系，結合文獻[2]的對稱性檢測方法，通過分析每兩個褶皺線上的點之間的變換，使用類似投票的方法，讓每個點對在變換空間中對其所反映的變換投票，最后票數最多的變換即為模型上顯著的對稱變換。

3.1 配對及變換的計算

與文獻[2]不同，本文使用褶皺線上所有的點作為采樣點，這些點構成了點集P。對于P中任意一個點Pi，它的2個主曲率，即最大曲率值和最小曲率值分別為[ki1]和[ki2]，它們反應了Pi點的局部幾何特征，定義其二維特征向量[Ki=ki1，ki2]，當Pi與[P]中另外一個點Pj（[i≠j]）進行配對時，[Ki]與[Kj]在二維平面空間中的歐氏距離是否在限定的范圍之內，如若符合要求，則計算Pi到Pj的變換矩陣。使用文獻[6]所述的近似最近鄰方法，可以在O（|P|log |P|）的時間內完成上述步驟。任意兩點Pi和Pj的變換矩陣是一個4×4的矩陣，它可以由旋轉矩陣rij和位移向量tij合成得到，因而Pi和Pj之間的變換tij可以表示成一個六元組[Tij=rxij，ryij，rzij，txij，tyij，tzij]，其中[rxij，ryij，rzij]表示旋轉矩陣rij的3個歐拉角，[txij，tyij，tzij]是位移向量tij的3個分量。使用Pi的主曲率方向[ci1]，[ci2]和法向[ni=ci1×ci2]，構造Pi上的局部坐標系[ci1，ci2，ni]，同樣構造Pj上的局部坐標系[cj1，cj2，nj]，這兩個局部坐標系間的變換即為旋轉矩陣rij，然后可計算[tij=Pj-rijPi]。對于反射變換的計算，可以先把Pi反射到以固定平面為軸的鏡面空間中，再計算其變換，本文以x=0為固定軸進行反射。這樣，當每一對Pi和Pj之間的變換Tij都計算出來后，即可得到一個包含了[P2]個點的6維變換空間。

3.2 聚類

對于每一個Tij，都是由兩個局部幾何特征相似的點計算得到的，且Tij是?中的點。如果模型上兩塊曲面上的所有頂點都完美的符合同一個變換，則這些頂點所構成的變換肯定都落在?中的同一個點上。但是實際上，由于曲率估算的誤差，噪聲的影響等因素的存在，這些點對所反映的變換不可能是完全相同的。因此需要使用聚類的方法，來辨別出比較顯著的變換的。由于分類后的類的個數是未知的，所以無法使用需要先驗知識的分類方法，如K?means[7]。因此，采用了文獻[8]中所提出的mean?shift方法，并使用對稱的Epanechnikov核。該方法把空間?中的點分成了若干個類，對于任意一個類Gk，其對應的變換為Tk，即該類的局部密度最大值在空間?中的坐標。

3.3 對稱曲面的驗證

通過聚類，可以得到由若干個點對組成的Gk，且這些點對都近似符合變換Tk。利用這些點對，可以使用雙向擴散的方法，來計算出對稱的曲面。對于Gk中任意一個點對（Pi，Pj），以Pj為參照，保留Pi周圍的一圈頂點中，經過Tk變換后，與Pj的距離小于某一給定閾值的頂點，記這些被保留下來的頂點集合為Si。同樣的，對于Pj，以Si為參照，判斷其周圍一圈頂點，產生集合Sj。不斷地擴大Si和Sj，直至涵蓋了用戶將要操作的感興趣區域為止。上述方法涉及到空間中最近距離的查詢問題，可以維護一個KD樹，這樣每次查詢和新增頂點的操作都可以在O（log |S|）時間內解決。由于聚類出來的變換Tk是近似的，不準確的，所以還需要逐步的求精，在不斷擴散得到Si和Sj的過程中，可以借助迭代最近點對算法[9]（Iterative Closest Points Algorithm）不斷的迭代求精Tk。

4 實驗結果

為了驗證本文改進方法的可行性以及有效性，從算法的運行效果以及運行效率2個方面進行了實驗，并與文獻[2]中的方法進行了對比。實驗數據采用了PSB標準模型庫[10]以及互聯網上的一些模型，分別針對位移變換，旋轉變換，反射變換3種對稱性關系做了提取，得到了模型上的所有對稱變換，其中最顯著的對稱變換所對應的對稱曲面如圖3所示。

第1列為輸入的模型，第2列中紅色區域和黃色區域表示對稱表面。其中上，中，下3行分別對應了旋轉變換，位移變換和反射變換。本文所有試驗均在一臺具有4 GB內存，Intel Core I7 處理器的便攜式計算機上進行。運行環境是Ubuntu 10.10。同時為了驗證本文提出的方法的高效性，實現了一種基于變換空間聚類（Transform Space Clustering，TSC）且未使用任何曲面特征的對稱性檢測算法[2]，簡稱TSC算法，并將該算法與本文中的改進算法進行了對比。實驗記錄了本文算法和TSC算法得到模型上全部對稱變換所用的時間，以及本文算法提取褶皺線的耗時，另外，為了驗證本文所使用的褶皺線特征的有效性，統計了TSC算法為了得到正確結果所需要的最小數目的采樣點，以及本文所使用的采樣點數目，即所有褶皺線上的頂點數目，實驗結果如表1所示。

從表1可以看出，本文算法相比TSC算法，雖然增加了褶皺線提取的耗時，但是褶皺線能夠大幅減少了采樣點數目，使得后續的配對和聚類過程的耗時大幅降低，從而使得算法的整體效率有明顯提升。

5 結 語

本文提出了一種基于曲率特征的對稱變換的提取算法，它使用褶皺線來描述三維模型上的復雜曲面，大大減少了對稱變換提取時所需要處理的頂點數，從而提升了算法效率。它相對于其他的對稱性檢測方法，具有更廣的適用性，更能夠給用戶帶來高效的體驗。

參考文獻

[1] XU Kai， ZHANG Hao， TAGLIASACCHI Andrea， et al. Partial intrinsic reflectional symmetry of 3D shapes[C]// ACM SIGGRAPH Asia 2009 papers， Yokohama， Japan： CM SIGGRAPH， 2009： 16?19.

[2] MITRA Niloy J， GUIBAS Leonidas J， PAULY Mark. Partial and approximate symmetry detection for 3D Geometry [J]. ACM Transactions on Graphics， 2006 25 （3）： 30?36.

[3] BOKELOH M， BERNER A， WAND M， et al. Symmetry detection using feature lines [C]// Comput. Graph. Forum. [S.l.]： CCF， 2009： 697?706.

[4] BERNER A， BOKELOH M， WAND M， et al. A graph?based approach to symmetry detection [J]. Volume Graphics， 2008， 40： 1?8.

[5] COHEN?STEINER D， MORVAN J. Restricted delaunay triangulations and normal cycle [C]// Symposium on Computational Geometry. [S.l.]： SCG， 2003： 312?321.

[6] MOUNT D M. ANN Programming Manual [M]. Maryland： Department of Computer Science， University of Maryland， College Park， 1998.

[7] HARTIGAN J A， WONG M A. A k?means clustering algorithm， applied statistics [M]. [S.l.]： [s.n.]， 1979.

[8] COMANICIU D， MEER P. Mean shift： a robust approach toward feature space analysis [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2002， 24（5）： 603?619.

[9] RUSINKIEWICZ S， LEVOY M. Efficient variants of the ICP algorithm [C]// Proceedings of 2001 Third International Conference on 3?D Digital Imaging and Modeling. Quebec City， Canada： [s.n.]， 2001： 145?152.

[10] SHILANE Philip， MIN Patrick， KAZHDAN Michael， el al. The Princeton shape benchmark [C]// Proceedings of 2004 Digital Object Identifier. Genova： DOI， 2004： 167?178.