階層式三維形狀環特征提取方法

左向梅，賈麗姣，韓鵬程

(1.中國飛行試驗研究院試驗機設計改裝研究部，西安710089; 2.西北工業大學航空學院，西安710072)

(*通信作者電子郵箱88.zxm@163.com)

0 引言

隨著信息技術的快速發展，三維模型因為其豐富的形狀、顏色、紋理等信息，在多媒體、圖形學、虛擬現實、設計、娛樂、工業制造等領域得到了越來越廣泛的應用。大量的三維模型數據庫可以從網絡上輕松獲得。除此之外，隨著RGB-D設備的出現，用戶可以更加方便快捷地獲得相關三維模型數據，這也大大增加了三維模型的數量。因此，為了有效地對現有三維模型進行管理和再利用，需要高效準確的圖形檢索、分類的方法來處理這些海量三維數據。

對于三維圖形的分類和檢索，大部分的解決方案都是設計出優秀的具有高分類精度的三維形狀特征。三維形狀特征很好地描述了三維模型的相關屬性包括顏色、紋理、形狀特性等，用于有效地區分或者歸類不同的三維模型。三維模型特征分為全局和局部特征，全局特征主要是通過對三維模型的整體形狀進行分析研究，獲取其形狀表達;局部特征將著眼于三維模型的局部形狀，利用局部網格來獲取顯著的局部特征。局部特征提取和檢索是近些年來的研究熱點，目前大量用于描述三維模型的局部特征被提出，例如:平均測地線距離(Average Geodesic Distance，AGD)［1］、尺度不變的熱核描述子 (Scale-Invariant Heat Kernel Signature，SI-HKS)［2］、形狀直徑函數 (Shape Diameter Function，SDF)［3］等，盡管這些特征在三維模型檢索匹配［4］、模型對齊［5］、對稱性檢測［6］中取得較好的應用效果，但是實際應用中還有待提升。主要原因有兩點:第一，這些特征都是基于專業的設計人員通過復雜的數學模型構建出來的，需要相關領域很強的先驗知識。例如尺度不變的熱核描述子是利用Laplace-Beltrami算子在三維形狀表面上通過熱擴散方程導出的，對于非專業領域的特征設計人員很難利用相關特性設計出優秀的特征描述子。第二，人工設計的特征大部分只能抽象三維模型上某一方面的屬性，例如平均測地線距離(AGD)只收集三維形狀上頂點與頂點的距離，形狀直徑函數(SDF)只收集三維形狀上不同部分的直徑信息，而三維形狀含有復雜的三維拓撲結構以及豐富的幾何信息，很多信息在特征提取完之后嚴重丟失，從而影響了圖形的檢索效率。為了降低對設計人員的技術門檻需求，更充足地收集圖形信息來提高特征表達能力，本文提出了一種融合三維形狀拓撲連接信息的階層式特征提取框架，讓其自動學習提取三維模型的相關屬性，其主要思想是以三維模型底層特征為基礎，結合三維模型的拓撲結構以及機器學習方法進一步提取模型的中層特征以及高層特征。

1 階層式環特征提取方法

本文方法主要分為三個步驟:首先，輸入三維模型數據，根據平均測地線距離、尺度不變的熱核描述符、形狀直徑函數等基礎描述符構建三維形狀的底層描述符。其次，結合三維形狀的結構化信息建立等測地線的環區域模型來編碼特征點的鄰近區域，從而得到該點的中層特征表達。最后，結合稀疏編碼的方法進一步探索各特征維度之間的信息，以及解決中層特征表達存在的相關問題，引入平移不變的編碼方式和傅里葉變換操作，進一步求得三維模型的高層特征:平移不變的環特征(Shift Invariant Ring Feature，SI-RF)。該特征具有較強的分辨力和魯棒性。本文方法流程如圖1所示。

圖1 提取平移不變的環特征的流程Fig.1 Flow chart of extracting shift invariant ring feature

1.1 圖形底層特征提取

本文的研究中，主要將平均測地線距離(AGD)、尺度不變的熱核描述子(SI-HKS)、形狀直徑函數(SDF)這些典型的局部特征進行組合，得到三維模型的底層特征，并以此為基礎產生三維模型的中層特征。

平均測地線距離(AGD)被Hilaga等［1］提出用于三維模型的圖形匹配。用g(xi，xj)描述在一個三維形狀X上兩頂點xi和xj之間的測地線距離，該值能保留有效的三維模型屬性，在圖形的檢索和分類中應用廣泛。該特征有以下三個特點:第一，該值描述了任意一點到模型上其他所有點的距離。第二，它的局部極大值與包含在模型中的幾何特征的描述相一致。第三，它是尺度不變的，并且可以用來從區分不同的形狀。

熱核描述符(Heat Kernel Signature，HKS)是利用Laplace-Beltrami算子在三維形狀表面上通過熱擴散方程導出的，具有豐富的局部幾何信息和多尺度特征。然而，HKS的局限性在于它對形狀的尺度敏感，例如當形狀變大時，HKS所描述的區域在同一時間范圍內變小。為了解決這個問題，Bronstein等［2］提出了尺度不變的熱核描述子(SI-HKS)，在圖形檢索匹配中取得了非常好的應用效果。

形狀直徑函數(SDF)是基于體積的標量函數，用來測量三維形狀上不同部分的直徑。SDF值是通過發射30條光線在30度的小圓錐內與相反的邊界側相交，并平均加權這些射線長度計算得到的。該值在同一模型的同一部分相鄰區域保持相似，并且能夠應對三維形狀的鉸接式變形。

考慮到這些特征既包含了三維形狀的本質屬性［7］也包含了三維形狀的基本幾何屬性，本文將尺度不變的熱核描述子(SIHKS)前6個頻域分量和平均測地線距離(AGD)以及形狀直徑函數(SDF)拼接在一起形成三維形狀的底層特征:

式(1)所求得的三維形狀的底層特征維度fm=8。對于SI-HKS，時間尺度設為［1，20］，時間間隔設置為 0.2，本征函數的數量為100，對數時間基設為α=2。對于AGD描述子的參數n設為1。由于底層特征包含不同的基礎三維形狀特征，所以每種不同類型的特征模型構建方式不同，因此底層特征的每一個維度的值具有不同的值域和尺度，為了保證每一種基礎特征所包含的信息不被忽視和過度重視，所有維度的值根據對應維度的最大最小值被線性歸一化到［－1，1］，計算式定義如下:

式中i∈［1，2，…，8］，表示底層特征的每一個維度。

因為該底層三維特征由多個基礎三維特征拼接而成，所以包含豐富的三維形狀屬性，可直接用于三維形狀的相關應用。但是該特征在應用中并不能取得非常好的效果，原因有兩點:首先，該底層特征由多種基礎特征拼接，盡管這種方式盡可能地不丟失三維信息，但是冗余信息過多，對于一般的分類器來說，并不能得到較好的分類結果。其次，三維形狀有著豐富而復雜的結構信息，比如坐標、紋理、顏色、拓撲結構信息等，該底層特征中包含的信息缺少顯性的空間結構信息。為了進一步提高提取特征的分辨力，本文在該底層特征的基礎上，結合特有的三維形狀拓撲結構提取三維形狀的中層特征。

1.2 圖形中層特征提取

對于一個三維形狀，僅靠頂點的特征描述值是不能提供足夠的有區分度的信息，特別是對低級別描述符;而相鄰的頂點及其鄰域的拓撲連接屬性卻包含了更多的信息。因此，提取高區分度的形狀特征最直接有效的方法就是編碼頂點的局部周圍區域。考慮到圖形具有豐富的拓撲結構，本文基于圖形的底層特征，提出了一種對三維形狀局部拓撲連接關系進行建模的中層特征構建方案:基于環的中層特征編碼。

1.2.1 三維圖形預處理

三維形狀通常由成千上萬的頂點和拓撲結構組成;但是，任一個三維形狀上頂點的特性類似于它的鄰域頂點。另外，在構建局部中層特征時使用全部三維形狀上的頂點會大大降低計算效率，浪費過多的計算機資源和時間。因此，在此工作中，選取三維網格上的部分點作為特征點用于模型的構建和訓練。本文采用最遠點采樣(Farthest Point Sampling，FPS)［8］的策略對三維網格進行均勻采樣。

本文利用最遠距離采樣的方法對數據庫中所有的模型進行統一降采樣預處理，得到三維形狀頂點子集V={vi∈X，i=1，2，…，Ns}，式中:X為三維網格，Ns為用戶設置的期望得到的采樣點數。初始采樣點v1∈X是隨機選取的。圖2是最遠點采樣的示意圖:左側為三維網格圖，中間為點云圖(頂點數5228)，右側為最遠點采樣后的點云圖(頂點數2000)。

圖2 最遠點采樣的示意圖Fig.2 Schematic diagram of farthest point sampling

1.2.2 基于環的中層特征編碼

對三維形狀進行局部編碼最直接的方式是依據特征點鄰域的拓撲連接結構創建該特征點鄰域的n個環。然而，由于每個三角網格的邊緣具有不同的長度，在該環上的頂點相對于中心特征點具有不同的測量距離。為了克服該缺點，利用基于測地線的方式創建等測地線的環。

1)等測地線環提取。

針對一個三角網格X上的特征點vi，本文通過快速修復方法(Fast Marching Method，FMM)［9］計算該特征點到三角網格上其他頂點之間的測地線距離。然后隨著漸漸增加特征點vi到周邊鄰域的測地線距離d1＜d2＜… ＜dNr計算Nr個不同層次的測地線函數，Nr表示環的數量。由于每個環上的采樣點數是不同的，在每個環上使用線性插值來生成相同數目的采樣點數Ns，并且使這些采樣點在環上等距隔開。每個環上的點具有一致的方向(順時針或逆時針相同)，形式為Ri=［，…］∈ RNs×3(其中 i表示第幾個測地線環，表示該測地線環上的采樣點)。局部等測地線環被定義成R=［R1;R2;…;RNr］∈ RNs×Nr×3，該測地線環被用來表示特征點vi的局部區域。這種等測地線環具有兩個好處:它們對于三維形狀的等距變形很魯棒，除此之外它們有相同的特征維度，有效地克服了受三維形狀復雜多變的拓撲結構影響，導致特征點鄰域頂點組成的環不具有相同維度的問題，因此可普遍應用于三維形狀檢索、對稱檢測等應用。一些三維模型的等測地線環的示意圖如圖3所示。在本文中，設置環的采樣點數Ns=80，環的個數 Nr=4。

圖3 部分三維模型的等測地線環示意圖Fig.3 Schematic diagram of isometric geodesic rings of some three-dimensional models

2)三維形狀的環特征描述符。

將1.1節計算的頂點底層特征代入到等測地線環上的頂點，形成等測地線環特征F(vi)∈RNs×Nr×fm，形式定義如下:

式中:vi是三角網格上的特征點;Ns是環上點的個數;Nr是環的個數。因為三角網格的頂點具有足夠的密度，所以網格上一個面上的點的特征值差別不大。根據這樣的事實，線性插值的方法被用來插值鄰域頂點的特征值去形成等測地線環特征。用 Fl∈ RNs×Nr表示該中層特征的一個維度，l∈ {1，2，…，fm}是該中層特征的下標索引。

1.3 圖形高層特征提取

1.2 節提出的這種編碼局部區域信息的特征描述符:基于等測地線環的特征F(vi)，有效地融合了三維形狀的結構化信息，大大增強了特征的區分力。但是這種特征依然存在以下問題:1)該特征由多個等測地線環上的點拼接而成，隨著環的增加以及環上采樣點的增加，該特征的維度將會非常大，信息冗余過多，不能高效地應用;特別是將該高維度的特征應用于分類器，很容易造成分類器失效，此時常常需要對高維度的特征進行降維操作，如使用主成分分析法對特征降維。2)因為本文是用圓環上采樣得到的點來表示局部區域，所以沒有辦法確定環上哪個點是起始點，如圖4所示。不同的點作為起始點會得到不同的結果，這顯然不利于特征的統一使用。

為了解決以上問題，本文對這種融和局部拓撲連接關系的中層特征作進一步學習，提煉出三維形狀的高層特征。

圖4 環不同起始點示意圖Fig.4 Schematic diagram of different start points on rings

1.3.1 稀疏編碼

因為一個特征點的最初底層描述符被封裝入一個固定維數的數組，所以關于中層特征表達的詞典可以有效地通過稀疏編碼方法獲知。然而對于不同的特征點，很難統一等測地線環上的起點，這可能會降低基函數的表達能力。為解決這一問題，本文引入平移不變的稀疏編碼(Shift-Invariant Sparse Coding，SISC)算法［10］來學習基于等測地線環的中層表達的基。SISC允許每個基函數在不同的測地線環上的不同位置被復制，因此學習的基對輸入數據的位置偏移不敏感。SISC是傳統稀疏編碼的延伸擴展，其中，關于特征分解公式中的傳統乘法運算被卷積運算代替，該特征的一個維度分解可以用如式(4)表示:

式中:aj∈Rq×Nr是關于等測地線環中層特征的基，它與中層特征Fl相比有較低的特征維度(q≤Ns)，因為環的個數要比環上采樣點的數少得多。基于輸入的中層特征Fl和基aj，基的不同圓形偏移量所對應的不同系數表達向量sj∈RNs－q+1。所以最優化問題是根據輸入中層特征學習合適的基A={a1，a2，…，aNb} 和系數 sj，優化函數描述為:

式中:‖aj‖≤1，1≤j≤Nb。該目標優化函數是一個聯合優化問題，即同時優化基A={a1，a2，…，aNb}和系數sj，并且通常是非凸函數。然而，當其中一個變量被固定，則該問題可以被視作一個凸優化問題。具體地說就是當A被固定，s能夠被看作一個凸優化問題得到解決。反之亦然。兩個子問題被反復交替并迭代求解，以獲得最佳的A={A1，A2，…，Afm}。當目標函數收斂后，稀疏系數s可以通過學習得到的基A和輸入的數據Fl得到，并且將其作為特征點的高層特征描述。

1.3.2 平移不變的環特征提取

高層特征是根據一系列不同形狀的特征點學習得到的，每個特征維度的表達為sl。在產生等測地線環的過程中，每個環的起始點的方向是統一的;但是對于不同的特征點，它們是不連貫的，這將會導致轉動歧義。為了使得該高層三維特征具有本質屬性，本文引入傅里葉變換來實現高層特征的旋轉不變性、這樣可以有效解決等測地線環不同的排列順序引起的不連貫問題。最后，底層特征f(xi)每個維度對應的三維高層特征可以描述成θl=|f{sl}|，則底層特征所有維度對應的高層平移不變的環特征描述為 θ = ［θ1，θ2，…，θfm］。

2 實驗與結果分析

為了驗證本文提出的平移不變的環特征(SI-RF)的有效性，以及對產生這種高層特征過程的重要參數進行討論和說明，本文主要進行了形狀對應和形狀檢索這兩類實驗。在形狀對應實驗中，主要采用Water tight dataset、TOSCA dataset和SCAPE dataset等三個數據庫［11］，這些數據庫含有豐富的三維形狀，并且具有形狀對應基準可用來計算SI-RF在三維模型上的對應準確率。在三維模型檢索實驗中，本文主要使用McGill shape benchmark［12］數據集進行驗證，該數據集包含457個模型，其中鉸鏈形式的模型含有10個類別，總共255個模型，每個類別有20～30個模型。

2.1 三維模型對應實驗

2.1.1 最優參數設置

根據產生SI-RF高層三維特征的過程可以發現等測地線環的半徑會影響特征的性能，所以，首先用Water tight dataset數據庫模型來進行三維形狀對應實驗，找出最合適的測地線距離dNr(即圓形區域的最大半徑)。本實驗中，設置最大等測地線環的半徑dNr的范圍為三維形狀上最大頂點之間距離的1% ～15%。本文采用兩種形狀對應方法:1)原始對應方法，即在兩個三維模型上將最小的特征距離差所在的頂點作為對應點對。2)譜對應方法［13］，在考慮特征距離的基礎上加上其他形式的約束，如能量等。所有模型的對應平均準確率用來作為實驗的評估基準。隨著選擇不同大小的測地線距離，對應實驗的結果如圖5所示。

圖5 不同測地線半徑下的對應準確率Fig.5 Corresponding accuracy of different geodesic radius

圖5 中，橫軸代表的是最大等測地線半徑dNr占三維模型上頂點之間最長測地線距離的比例;縱軸代表的是所有模型的平均對應準確率。從圖5中可以看出，如果比例過小，即區域范圍選擇得過小，對應準確率較低;比例低于0.08時，對應準確率是呈上升趨勢;但是，當比例高于0.08時，準確率呈下降趨勢。因此，本文將三維模型上最長測地線距離的0.08倍作為特征點的最大等測地線半徑，并將其應用于本文相關的實驗。

其次，對應的準確率同樣受到基的個數的影響，所以選擇合適的基的個數Nb同樣至關重要。第二個對應實驗，本文分別將基的數目 Nb設置為 20、40、60、80、100、120、140、160，并根據其對應的準確率選擇最佳的基個數，同樣用兩種對應方法進行對比實驗，結果如圖6所示。從圖6中可以看出，隨著基的個數增加，對應準確率呈現上升趨勢，因為基的個數越多，其表達能力越豐富，所以能夠產生有區分力的高層三維形狀特征。雖然基個數越多越好，但是會導致計算效率降低，影響產生高層特征的效率。而且從圖6中可以看出，當基的個數達到一定值后，其對應準確率增長得較為緩慢。因此，確定基個數為80，并將其用于后續的相關實驗。

圖6 不同基的個數的對應準確率Fig.6 Correspondence accuracy with different number of bases

2.1.2 對應實驗驗證

尺度不變的熱核描述符(SI-HKS)和平移不變的環特征(SI-RF)在兩種對應方法下的檢測準確率結果如表1所示。本文選擇了具有典型性的三組模型:人、螞蟻、熊。從表1可以看出，本文提出的SI-RF特征具有更好的區分能力，能夠獲得更高的對應準確率。

表1 SI-HKS與SI-RF對應的檢測準確率 %Tab.1 Corresponding detection accuracy of SI-HKS and SI-RF %

為了進一步驗證平移不變的環特征(SI-RF)的性能，本文在TOSCA數據庫上進行了對應實驗。對于每個模型，通過最遠點采樣方法對模型進行降采樣，設置每個模型采樣后的點數為1000。將源物體上的頂點投射到目標物體上，在該實驗中定義基準對應點到通過算法匹配得到的對應點之間的測地線距離為測地線誤差，因為有些特征點在三維形狀上很接近，特征具有極大的相似性，很難作出有效區分，所以，只要通過算法匹配得到的對應點與基準對應點之間的測地線范圍小于一定值，即可認為該點對匹配成功。針對TOSCA數據庫，本文得出不同測地線誤差范圍情況下模型對應實驗的準確率如圖7所示。

圖7 SI-HKS與SI-RF在不同測地線誤差范圍下的匹配正確率Fig.7 Matching accuracy of SI-HKS and SI-RF under different geodesic error ranges

從圖7中可以看出，SI-RF比SI-HKS具有更高的匹配正確率，當可以允許的測地線誤差距離設置為三維形狀上頂點之間最大測地線距離的0.15時，SI-RF可以達到90%的準確率，而SI-HKS只有64.5%。

2.2 三維模型檢索實驗

除了模型對應實驗以外，本文進行模型檢索實驗來進一步驗證該三維高層特征(SI-RF)能否適用于圖形的相似性檢測。借鑒Shape Google的思想［14］在Mcgill數據庫上進行驗證。首先，利用最遠點采樣的方法對數據庫中每個模型進行降采樣預處理，每個模型的采樣點設置為1500。然后根據底層特征構建三維形狀的中層特征:基于等測地線環的局部區域編碼。接著利用稀疏編碼進一步抽象提取每個特征點對應的高層特征:平移不變的環特征(SI-RF)。因為在模型檢索實驗中需要用模型的全局特征進行描述，借鑒Shape Google的思想將平移不變的環特征編碼產生三維形狀的全局特征(Global SI-RF)。對于SI-HKS，本文利用同樣的思路產生相應的全局描述符(Global SI-HKS)。

本文采用6個標準評估指標［15］來評價提出的高層三維特征在模型檢索應用中的表現，它們分別是:精密召回曲線(precision-recall curve)、最近鄰(Nearest Neighbor，NN)、一階(First Tier，FT)、二階(Second Tier，ST)、E 測量(E-measure，E)和貼現累計收益(Discounted Cumulative Gain，DCG)。本文除了將全局SI-RF跟全局SI-HKS進行對比，還與其他先進的特征描述符包括形狀諧波描述符(Shape Harmonic Descriptor，SHD)［16］、光 場 描 述 符 (Light-Field Descriptor，LFD)、關聯矩陣特征值描述符(EigenValue Descriptor of affinity matric，EVD)［17］和測地線距離 －屬性關系圖(Earth Movers Distance-Attributed Relation Graph ，EMD-ARG)［18］進行比較。各特征描述符的檢索精確率如圖8所示。

圖8 多種特征描述符檢索精確率對比Fig.8 Recall-precision curve comparison of multiple feature descriptors

從圖8中可以看出，本文設計的三維高層特征:平移不變的環特征(SI-RF)比其他特征取得了更高的檢索準確率。除此之外，EMD-ARG、SI-HKS和SI-RF在不同評估指標下的值如表2所示。從表2中可以看出，本文提出的SI-RF各項評估指標都比另外兩種特征描述符取得較高的數值，特別是在DCG指標上比SI-HKS提高了7.2個百分點，這充分表明了該設計框架的有效性，通過稀疏編碼結合中層結構化編碼能夠進一步提高底層特征的區分能力。

表2 多種特征描述符關于標準檢索評估指標的對比 %Tab.2 Comparison of multiple feature descriptors for standard retrieval and evaluation indicators %

3 結語

一個良好的特征應該是階層式的，除了底層基礎屬性如紋理、角度、方向等，還應該具有三維形狀拓撲結構信息，基于該思想本文提出了一種階層式的三維形狀環特征提取框架，其基本思路是從構建圖形的底層特征開始，逐步根據三維形狀局部拓撲連接關系構建三維形狀的中層特征以及高層特征。首先，根據底層基本特征和三維形狀的表面物理結構構建等測地線環，并用其作為特征點的中層表達;然后，利用平移不變的稀疏編碼(SISC)進一步提取基于環的高層三維特征。該設計框架不僅將稀疏編碼技術巧妙地應用于三維形狀分析，還通過構建中層結構化特征的方法增強了稀疏編碼的應用性能。本文將該特征應用于三維形狀對應、檢索等實驗，相比其他相關的特征取得更高的檢索準確率和更好的匹配效果。

雖然本文提出的三維形狀局部特征具有更好的性能，但是仍然存在一些需改進的地方:首先，使用等測地線環來表示特征點的局部區域，這種方法的計算效率低。其次，在提取等測地線環的時候需要將三角網格展開，但是因為三角網格的復雜性，存在部分網格不能很好地被展開的問題。因此，在以后的研究中，我們將研究更好的局部區域提取技術來改善本文方法。