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

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

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

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

　本文依據(jù)三維模型提取的骨架及骨架點(diǎn)的空間結(jié)構(gòu)特征提出了一種新的三維模型局部檢索算法，實(shí)驗(yàn)證明該方法能夠有效地找到與目標(biāo)部分相似的子部分，無(wú)論是對(duì)于不同模型的局部還是同種模型進(jìn)行變形后的子部分，都能根據(jù)本文算法精確地進(jìn)行檢索。
參考文獻(xiàn)
[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].中國(guó)圖象圖形學(xué)報(bào)，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].青島：中國(guó)石油大學(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骨架樹(shù)的三維模型檢索算法[J].計(jì)算機(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.