尚福華，于志東，周亞東，解紅濤

(東北石油大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江大慶163318)

隨著計(jì)算機(jī)科學(xué)的不斷進(jìn)步，3D技術(shù)逐步發(fā)展起來.三維模型作為繼一維的文本信息、二維的圖像信息之后的又一虛擬媒體信息，增加了信息量和信息的復(fù)雜度，同時(shí)也加大了人們對于信息檢索工具的依賴，而這些檢索工具的復(fù)雜性和規(guī)模性也日益增強(qiáng).伴隨著三維建模軟件和三維掃描技術(shù)的不斷成熟，三維模型的生成越來越容易.同時(shí)電子娛樂、工業(yè)設(shè)計(jì)、虛擬現(xiàn)實(shí)等領(lǐng)域也積累了越來越多的三維模型，這些三維模型通過互聯(lián)網(wǎng)廣泛傳播，形成了許多三維模型庫.在這些模型庫中一部分是針對特定領(lǐng)域的，比如說美國國家癌癥研究所的NCIDIS3D模型庫，該三維模型庫包含了40萬個(gè)三維模型;美國MDL的化學(xué)品三維模型庫ACD－3DMDL有30萬個(gè)模型;美國普林斯頓大學(xué)和通用模型庫有6萬個(gè)模型[1－2]，是規(guī)模比較大的模型庫.

隨著模型數(shù)量的不斷激增，現(xiàn)有搜索引擎已經(jīng)難以有效地進(jìn)行三維模型的檢索.十分需要一種三維模型檢索方法，基于內(nèi)容(content－based 3D model retrieval)的三維模型檢索方式應(yīng)運(yùn)而生.該技術(shù)不僅可用在三維數(shù)據(jù)庫中瀏覽和檢索三維場景或三維模型[3]，也可用于三維物體形狀分析和三維物體的自動(dòng)識別與分類[4].近幾年來無數(shù)的學(xué)者對于三維模型的檢索方式進(jìn)行了許多的創(chuàng)新和改進(jìn)，但是大多都是針對普林斯頓大學(xué)的模型庫為實(shí)驗(yàn)數(shù)據(jù)，缺乏實(shí)際中應(yīng)用到的小型、專業(yè)模型庫作為實(shí)驗(yàn)的模型庫.針對大慶油田鉆井模型庫模型數(shù)量相對較少、相似性高等特點(diǎn)，本文提出了通過特征融合技術(shù)將法向面和視圖特征融合為一體，增強(qiáng)對模型的描述能力，從而實(shí)現(xiàn)快速而又準(zhǔn)確的進(jìn)行三維模型檢索.實(shí)驗(yàn)表明該方法在小型專業(yè)模型庫上能夠提高模型檢索的速度和準(zhǔn)確度.小.

1 VM特征融合

特征融合(Feature Combination)由德國CCCC小組提出.研究表明基于多特征融合的模型檢索方式，比使用單個(gè)模型特征的檢索效果要好很多[5].因此，很多研究人員一方面在尋找高效的特征提取方式進(jìn)行高效的模型檢索，一方面在考慮融合現(xiàn)有的特征提取方法[6].這兩方面互為補(bǔ)充，在沒有找到更好的特征提取方式之前，將兩者結(jié)合進(jìn)行三維模型檢索的方式仍然是一個(gè)很好的選擇.

特征融合的過程主要分為3步:首先模型標(biāo)準(zhǔn)化，然后對模型分別抽取各個(gè)指定的特征向量，最后融合特征值.

VM即View(視圖)和Mesh(面)大寫首字母.當(dāng)提取面特征向量時(shí)，提取的是面的朝向和面在模型各個(gè)朝向上面的分布密集程度兩個(gè)特征.對于面的特征提取方式，由于模型本身數(shù)據(jù)存儲方式?jīng)]有將面的上述兩個(gè)特征作為一個(gè)屬性存放，而是通過法線進(jìn)行表現(xiàn)，其實(shí)這兩個(gè)屬性中面的朝向就是法線的特征表現(xiàn)，不同朝向上面的密集程度是面的屬性.為了方便計(jì)算表達(dá)，本文將這兩個(gè)特征屬性作為一個(gè)特征M(mesh，面)來表示.

1.1 模型標(biāo)準(zhǔn)化

基于內(nèi)容的模型特征提取大多數(shù)是需要預(yù)處理將模型標(biāo)準(zhǔn)化的，如圖1中兩個(gè)相似的杯子模型，卻有著不同的坐標(biāo)軸;可能還有的情況是有相似外形的模型即便有著相一致的坐標(biāo)軸但是大小卻相差很多;或者在世界坐標(biāo)系中所處位置也不相同，如圖2所示.這些情況下需要進(jìn)行標(biāo)準(zhǔn)化處理，使相同的或者相近的模型具有相同的大小和朝向，使得特征提取受模型大小、朝向等影響因素降到最

1.2 抽取特征向量

模型在標(biāo)準(zhǔn)化之后，就可以進(jìn)行特征提取了.為了能夠全面的表達(dá)模型的特征、性質(zhì)，提取的特征之間需要互補(bǔ)，最大化的表達(dá)模型的屬性.

在對三維模型進(jìn)行特征抽取前，需要對模型進(jìn)行規(guī)范化，以保證模型在平移、旋轉(zhuǎn)、縮放的情況下，保持本身特征的不變性.首先計(jì)算模型的主軸，將模型的質(zhì)心放在坐標(biāo)系原點(diǎn)處，采用PCA(Principal Component Analysis)或CPCA(Continuous PCA)的方法確定主軸，再將三維模型表面的各個(gè)點(diǎn)到坐標(biāo)系原點(diǎn)距離的平均值調(diào)整為“1”，使三維模型具有相同的大小.最后，對該模型分別提取基于視圖、法向量、面的特征向量.

1.3 融合特征值

對模型抽取基于視圖(View)、法向量(Normal vector)和面(Mesh)的特征向量后，融合抽取出來的特征值.其中法向和面的特征緊密相連，可以將兩者歸結(jié)為面的特征.特征值的構(gòu)成過程中，并不是將選擇的幾個(gè)特征值簡單的連接在一起就形成特征值的，而是通過對各個(gè)特征值識別能力的分析來分配在特征值中三種特征值分別占多少維.

2 VM特征值計(jì)算

計(jì)算三維模型基于視圖的特征值方法為:通過模型的外包圍正方體，獲取在X、Y、Z三個(gè)軸向上的投影，獲取輪廓圖像，對于每個(gè)面進(jìn)行采樣的深度線序列.

計(jì)算三維模型基于法向面的特征值方法為:提取模型基于法向和面的特征向量，通過從模型表面中每個(gè)三角面得出的法向量與外包圍十二面體相交的點(diǎn)，判定在每個(gè)外包圍二十面體索引面的交點(diǎn)所在的法線和交點(diǎn)數(shù)，進(jìn)而判斷不同朝向上模型面的分布密集程度.即m=(m1……mN)，其中 m1+……+mN=M.

對三維模型進(jìn)行規(guī)范化之后，提取出基于視圖和法向面的特征，再通過這兩種特征向量融合成模型的VM特征值c=(v|n).特征值維數(shù)為C=V+M.VM特征值的形成不是簡單的把視圖和法向面兩種特征值累計(jì)在一起，而是根據(jù)不同特征值對于模型的識別能力，決定最后哪一種特征值在VM特征值中占有多少比例(或者說是多少維).由于基于視圖的特征值要比基于法線的有效，因此基于法線的特征值的維數(shù)就要比基于視圖的特征值要少，也就是M＜V.在特征值的選取過程中，每一種特征值都是使用固定維數(shù)的，本文基于視圖的特征提取采用了180維，也就是每個(gè)視圖上對比60條深度序列線，每條深度線有60個(gè)采樣點(diǎn).基于法向面的特征提取使用了80維(采用了外包圍球面數(shù)為80的正多面體)，所以最后的VM融合特征值為180+80=260維特征值.對于這種提取維數(shù)的合理性通過對比實(shí)驗(yàn)加以證明.

3 VM對比實(shí)驗(yàn)及分析

實(shí)驗(yàn)中使用的三維模型來自大慶油田鉆井三公司鉆井仿真三維模型庫，該庫為小型、專業(yè)模型庫，總計(jì)四個(gè)類別共1 023個(gè)模型，每個(gè)模型包含著大量的點(diǎn)和面，模型的數(shù)據(jù)格式為off.采用該模型庫中所有模型為試驗(yàn)樣本.對該模型庫使用不同的三維模型特征提取方法，對比基于視圖的和基于法向面檢索方式的檢索效果.最后使用基于特征融合檢索方法進(jìn)行實(shí)驗(yàn)對比，使用Recall/Precision(查全/查準(zhǔn)率)表現(xiàn)檢索對比效果.經(jīng)過多次輸入實(shí)例模型(牙輪轉(zhuǎn)頭、大絞車、固井膠塞、大鉤、轉(zhuǎn)盤等)進(jìn)行檢索.

3.1 確定特征值之間比例

對于確定兩個(gè)特征維數(shù)值總量和兩者之間比例，先通過實(shí)驗(yàn)確定維數(shù)總和顯然是不合適的，因?yàn)闊o論在何種比例下維數(shù)總和越大檢索效果越好，不同比例下最佳維數(shù)值也不一樣.兩種特征提取方式融合后在不同的特征維數(shù)比例下其檢索性能曲線是不一樣的.但是在兩者維數(shù)總和一定的情形下，檢索效果并不隨著兩者比例值的增加而提高，而是有個(gè)最大值，這個(gè)最大值就是我們要尋找的.

通過實(shí)驗(yàn)對比基于視圖的模型檢索方式和基于法向面的檢索方式，可知基于視圖的模型檢索方式檢索效果優(yōu)于基于法向面的檢索方式的檢索效果，因此基于視圖的特征提取方式在特征融合中所占的比例就應(yīng)該大一些.所以實(shí)驗(yàn)數(shù)據(jù)中只有一個(gè)比例是小于1的，在實(shí)驗(yàn)中兩種特征值VM(視圖，法向面)比例從0.5增加到3，如圖3所示.結(jié)果表明在兩者比例為9∶4的時(shí)候檢索效果最好.

圖3 不同視圖和法線比例的檢索效果對比

對于VM各自維數(shù)最佳組合是需要經(jīng)過不斷試驗(yàn)進(jìn)行驗(yàn)證的，也會隨著模型庫的變動(dòng)而發(fā)生變化，所以只能通過不斷試驗(yàn)和不斷增進(jìn)對模型庫本身模型信息的了解，才能夠根據(jù)經(jīng)驗(yàn)及實(shí)驗(yàn)得到一個(gè)比較合適的比例，也可以在檢索界面設(shè)置兩者維數(shù)的比例，根據(jù)檢索結(jié)果不斷地進(jìn)行修改，使其趨近一個(gè)合理的比率.

3.2 確定特征值維數(shù)總量

在確定VM比例為9∶4的情況下進(jìn)行試驗(yàn)求得維數(shù)最佳數(shù)量總和.實(shí)驗(yàn)是通過不斷增加維數(shù)來確定最合適數(shù)量的.從圖4中可以看出當(dāng)VM維數(shù)各自增加到180、80后，再增加的時(shí)候檢索效果已經(jīng)相差無幾，所以為保證檢索的快速性，這里采用了V=180，M=80的260的維數(shù)總和.

圖4 不同特征數(shù)量檢索效果對比

通過不斷進(jìn)行實(shí)例模型的檢索可以繪制出如圖5所示的檢索性能曲線.根據(jù)該曲線可以估計(jì)兩者比例和兩者各自維數(shù)值.由圖5看出，隨著每一條檢索曲線維數(shù)不斷的增加，其檢索性能顯示急劇增加后是趨于平穩(wěn)，無論怎樣增加也達(dá)不到100%.因此可以在斜度為30°左右的地方進(jìn)行維數(shù)的確定.而基于特征融合的檢索方式實(shí)質(zhì)上就是將兩種檢索方式附加到一起，但是基于特征融合的檢索方式的最佳檢索狀態(tài)，并不是簡單的將上述兩者最佳狀態(tài)時(shí)的組合簡單附加到一起.如果單一地把兩者維數(shù)組合融合在一起，基于特征融合的檢索方式肯定是比任何一種檢索方式效果都要好.但是只是簡單的將兩者附加到一起會出現(xiàn)疊加上的浪費(fèi)，如果對其中一種檢索方式的維數(shù)大幅度減少，會發(fā)現(xiàn)檢索性能只會有微弱的降低，這樣換來的檢索時(shí)間的縮短卻是十分有意義的.

圖5 檢索性能曲線

3.3 檢索效果對比

將基于特征融合的檢索方式和基于三視圖的、基于法向面的檢索方式進(jìn)行對比(PR曲線和檢索時(shí)間進(jìn)行對比).

1)PR曲線對比

基于特征融合的檢索方式與基于三視圖的、基于法向面的檢索方式的檢索效果對比，結(jié)果如圖6所示.其中基于特征融合的檢索方式PR曲線整體偏于右上方，其次為基于視圖的檢索方式，最后是基于法向面的檢索方式.融合了基于視圖的和法向面的特征提取方式的特征融合檢索方式，明顯要好于前兩種檢索方式.

圖6 檢索效果對比

2)檢索時(shí)間對比

檢索時(shí)間為生成對比序列時(shí)間和匹配時(shí)間，由于實(shí)驗(yàn)使用多次檢索進(jìn)行對比，所以采用的是平均時(shí)間.在檢索時(shí)間上基于特征融合的檢索方式由于使用了兩種對比序列生成方式，也就耗費(fèi)了相對多的序列對比時(shí)間，如表1所示.根據(jù)表中所示的檢索時(shí)間對比，可以看出基于特征融合的檢索時(shí)間處于基于三視圖檢索方式和基于法向面檢索方式之間.

表1 檢索時(shí)間對比

4 結(jié)語

通過以上實(shí)驗(yàn)可以看出，對于一些專業(yè)性較強(qiáng)的小型三維模型庫，基于特征融合的模型檢索效果要好于基于三視圖的和基于法向面的模型檢索方式，雖然基于特征融合的檢索方式相對來說耗費(fèi)了一些時(shí)間，但是相對于其優(yōu)秀的檢索效果，這些時(shí)間的耗費(fèi)是可以忽略的.因此，該模型檢索方式對于一些專業(yè)性較強(qiáng)的小型三維模型庫，在模型檢索的準(zhǔn)確度和效率上具有很大的優(yōu)勢.

[1] MOUSTAKAS K.Masterpiece:physical interaction and 3D content－ based search in VR applications[J].IEEE MultiMedia，2006，13(3):92 －100.

[2] 郭 競，馮 筠，葉豪盛.相對角度直方圖聚類在3維模型檢索中的應(yīng)用[J].中國圖象圖形學(xué)報(bào)，2010(11):67－68.

[3] 高 巖，陳敏剛，王長波.二維動(dòng)畫關(guān)鍵幀的層次約束插值算法[C]//第十五屆全國圖象圖形學(xué)學(xué)術(shù)會議論文集，2010:678－680.

[4] 申 偉，苗振江，萬麗莉.三維模型檢索和逼真顯示功能在可視媒體平臺的實(shí)現(xiàn)[C]//第18屆全國多媒體學(xué)術(shù)會議(NCMT2009)，2009:345－346.

[5] 湯 進(jìn)，陳展展，羅 斌.基于復(fù)雜網(wǎng)絡(luò)和最優(yōu)子序列雙射的形狀描述與匹配[J].電子學(xué)報(bào)，2011(8):56－57.

[6] ATMOSUKARTO I.Feature Feature Combination and Relevance Feedback for 3D Model Retrieval[C]//Proceedings of the 11th International Multimedia Modeling Conference，[S.l.]: [s.n.]，2005:334－339.