摘  要： 針對局部信息識別的重要性，在骨架提取的基礎(chǔ)上，提出了一種新的三維模型局部檢索方法。該算法在基于骨架樹進行圖結(jié)構(gòu)匹配的初步篩選后，融入空間結(jié)構(gòu)特征和幾何細節(jié)特征，進行局部相似度的計算。大量實驗證明，本方法對于模型的局部匹配有很好的魯棒性和高效性。
關(guān)鍵詞： 圖結(jié)構(gòu)；空間結(jié)構(gòu)特征；幾何細節(jié)；局部檢索

　隨著計算機建模和動畫技術(shù)的發(fā)展，三維模型在人類人生活中的地位越來越重要，而對三維模型檢索技術(shù)的研究也一直是熱點之一。相對于模型的整體匹配，局部信息的識別也往往是常用的方法之一。例如，人區(qū)分某種動物時，往往通過動物的局部信息就能加以區(qū)分（如長頸鹿的脖子、海豚的頭部等）。關(guān)于三維模型局部算法的研究，目前主要有幾下幾種：萬麗莉等[1]提出了一種基于空間部件分布的方法，該算法是將模型先分割成一系列的部件，然后分別提取子部分的特征，該算法雖然計算速度快，但是依賴于模型分割，且對局部細節(jié)特征描述較少。SHILANE P[2]等提了一種基于模型顯著幾何區(qū)域特征對模型進行檢索，該算法的核心是對模型表面進行采樣，然后根據(jù)對4種不同尺度對為半徑的球型區(qū)域進行分析，得到球面調(diào)和描述子，將檢索結(jié)果用DCG方法評價，最后實現(xiàn)局部匹配。該算法雖然效果較好，但是時間復(fù)雜度極高，在實際檢索中是不現(xiàn)實的。Spin-image[3]是在模型表面隨機采樣，然后將每個頂點得到的Spin-image作為局部特征描述符。另外，Chen L B[4]依據(jù)Smith-Waterman算法進行局部檢索，SHALOM S[5]利用SDF的方法進行局部匹配。鑒于上述方法，本文提出了一種融合空間特征結(jié)構(gòu)的三維模型局部匹配算法，實驗證明該方法具有較高的準確率和較好的魯棒性。
1 算法步驟
　本文算法的流程如圖1所示。

1.1 骨架提取及映射后的骨架樹
　傳統(tǒng)的Reeb圖是一維的圖結(jié)構(gòu)，它能夠很好地反映模型的拓撲結(jié)構(gòu)，但是卻不能很好地描述模型局部細節(jié)特征。本文采用參考文獻[6]的方法，在MRG算法的基礎(chǔ)上改進了基本點的選擇和函數(shù)的計算，并且通過結(jié)合模型表面離散曲率和增加關(guān)節(jié)特征點的方法，進一步優(yōu)化了模型的骨架，有效地突出模型的關(guān)節(jié)特征點，進一步加強了模型檢索的準確率。

1.3 空間結(jié)構(gòu)特征的表示與幾何信息的計算
　通過對圖結(jié)構(gòu)的初級篩選，可以得到幾個有著相同或相似結(jié)構(gòu)的子樹。由于圖結(jié)構(gòu)僅代表著拓撲連接結(jié)構(gòu)，僅靠這種特征并不能準確地得出模型的相似度。比如兩個模型的頭部拓撲連接圖相同，但是在空間中它們的空間結(jié)構(gòu)卻很不一樣。骨架樹是二維的圖，而骨架是具有空間結(jié)構(gòu)的三維連接結(jié)構(gòu)，任意兩個子節(jié)點之間的夾角可以表示模型在空間的結(jié)構(gòu)不同，因此在此基礎(chǔ)上融入了空間結(jié)構(gòu)特征。
　在骨架提取的過程中，可以知道各個骨架節(jié)點的坐標，以子樹部分的父節(jié)點作為原點建立空間坐標系，由于知道其子節(jié)點在空間中的位置，因此兩個子節(jié)點之間的夾角很容易得出。在子樹部分中，加入子節(jié)點之間的夾角特征不僅能夠表示其子節(jié)點在空間的連接結(jié)構(gòu)，還能夠體現(xiàn)子節(jié)點與父節(jié)點在空間的空間結(jié)構(gòu)。將兩個子節(jié)點矢量的空間夾角作為模型的空間結(jié)構(gòu)特征：BuildSpatialFeature（）；讀取父節(jié)點S0與其子節(jié)點的空間坐標S1（x1，y1，z1），S2（x2，y2，z2），…，Sn（xn，yn，zn）；利用空間矢量求出父節(jié)點與所有子節(jié)點構(gòu)成的矢量（V1，V2，…，Vn）夾角。
　若3點不在一條直線上則：
　getAngleByCoordinate：
　angle（S1）=getAngleByCoordinate（V1V2，V1V3，…，V1Vi）；
　否則：
　angle（S1）=0//所選3個點在同一直線上
　在拓撲連接和空間結(jié)構(gòu)的基礎(chǔ)上融入了能夠體現(xiàn)局部細節(jié)特征的局部突起特征Saliency[7]。對于任意骨架節(jié)點都能用式（2）計算出其幾何細節(jié)特征：
　Saliency=w1Area（Sn）Cure（Sn）3+w2N（Sn）Var（Sn）（2）
　其中，Area（Sn）為骨架節(jié)點Sn對應(yīng)的連通區(qū)域的面積與模型總面積的比例；Cure（Sn）是骨架節(jié)點Sn對應(yīng)的連通區(qū)域的網(wǎng)格點的標準化之后曲率的平均值；N（Sn）是骨架節(jié)點Sn對應(yīng)的區(qū)域曲率極大值或極小值點的個數(shù)；Var（Sn）是骨架節(jié)點Sn對應(yīng)的區(qū)域曲率的方差；在實驗過程中，將w1和w2都賦予0.5。
由于局部細節(jié)特征對根節(jié)點的影響較小，因此本文由內(nèi)向外分別賦予各個節(jié)點由小到大的權(quán)值。這樣，每個骨架節(jié)點Sn都具有拓撲特征Tf（包括出入度和子節(jié)點間的空間的角度）及Gf幾何特征（saliency）：Sn（Tf（deg，angle），Gf（saliency）），將其作為特征向量進行相似度匹配。
1.4 局部相似度的計算
　匹配過程中，采用EMD（Earth Mover′s Distance）距離的方法對模型局部進行相似度的計算。EMD算法一般用于對兩個分布相似性進行度量，EMD的計算是基于對運輸問題的解決，這是一個雙邊網(wǎng)絡(luò)流問題，可以表示為以下線性規(guī)劃問題：假設(shè)I為供應(yīng)商集合，J為消費者集合，Cij為從供應(yīng)商i∈I對消費者j∈J供給的代價。圖4所示是3個供應(yīng)商和2個消費者的示例[11]。

　本文依據(jù)三維模型提取的骨架及骨架點的空間結(jié)構(gòu)特征提出了一種新的三維模型局部檢索算法，實驗證明該方法能夠有效地找到與目標部分相似的子部分，無論是對于不同模型的局部還是同種模型進行變形后的子部分，都能根據(jù)本文算法精確地進行檢索。
參考文獻
[1] Wan L L， Zhao Q P， Hao A M. A method of 3D model retrieval by the spatial distributions of components[J]. Journal of Software， 2007，18（11）：2902-2913.
[2] SHILANE P， FUNKHOUSER T. Selecting distinctive 3D shape descriptors for similarity retrieval[A]. Shape Modeling and Applications[C]. SMI， 2006.
[3] JOHNSON A E， HEBERT M. Using spin images for efficient object recognition in cluttered 3D scenes[J]. IEEE Transactions on pattern analysis and Matchine Intelligence， 1999，21（5）.
[4] CHEN L B， FERIS R S， TURK M. Efficient partial shape matching using Smith-Waterman algorithm[C]. Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition（CVPR）， Anchorage， AK， USA， 2008：1-6.
[5] SHALOM S， SHAMIR L S A， et al. Part analogies in sets of objects[A]. Eurographics Workshop on 3D Object Retrieval， 2008.
[6] 韓麗，楚秉智.關(guān)節(jié)特征約束的3維模型骨架提取算法[J].中國圖象圖形學(xué)報，2011，16（4）：660-665.
[7] GAL R， COHEN-OR D. Salient geometric features for partial shape matching and similarity[J].ACM Trans.Graph.， 2006，25（1）：130-150.
[8] 張曉東.三維模型的形狀特征提取方法研究[D].青島：中國石油大學(xué)（華東），2010.
[9] HILAGA M， SHINAGAWA Y， KOMURA T， et al. Topology  matching for fully automatic similarity estimation of 3D shapes[C]. Computer Graphics Proceedings Annual Conference Series， ACM SIG- GRAPH Los Angeles， California， 2001：203-212.
[10] 韓麗，張黎娜，楚秉智.一種MRG骨架樹的三維模型檢索算法[J].計算機工程與應(yīng)用，2011，47（31）：167-170.
[11] RUBNER Y， TOMASI C， GUIBAS L J. A metric for distributions with applications to image databases[C].Proceedings of the 1998 IEEE International Conference on Computer Vision，1998.