田楓， 孫寧， 劉賢梅

(東北石油大學 計算機與信息技術(shù)學院， 大慶 163318)

0 引言

近年來，隨著計算機圖形學的發(fā)展以及三維模型獲取技術(shù)、圖形硬件技術(shù)的提高，數(shù)字幾何模型已成為繼聲音、數(shù)字圖像和數(shù)字視頻之后的第4種多媒體數(shù)據(jù)類型[1]。作為數(shù)字幾何模型主要組成部分的三維模型在工業(yè)、醫(yī)療、建筑、游戲等領(lǐng)域的應用范圍十分廣泛，由于三維模型本身信息量較大的特性使得在建模過程中往往需要耗費一定的人力物力成本，如何高效的檢索并重復利用三維模型成為目前的主要研究方向。因此，提高三維模型標注的準確性與高效性作為實現(xiàn)高效檢索模型的一個重要前提逐漸成為目前的主要研究方向。

三維模型語義標注指的是通過識別三維模型內(nèi)部特征等的方式給未知模型添加能描述該模型語義內(nèi)容關(guān)鍵詞的方法。如普林斯頓大學、臺灣大學，國內(nèi)如中科院計算所、浙江大學等都對相關(guān)領(lǐng)域進行了研究[2-4]。檢索方式主要分為基于文本的檢索和基于內(nèi)容的檢索[5-6]。除此之外許多學者還提出了基于語義相關(guān)性的標注方式，利用三維模型之間的語義相關(guān)性作為標注依據(jù)，將用戶形狀檢索過程中的反饋信息作為模型語義的參考內(nèi)容[7]。這種方法僅考慮了模型的語義信息，并沒有考慮三維模型之間的底層特征相似度，導致標注結(jié)果并不十分理想。因此，能夠更好描述三維模型底層特征的方式逐漸成為目前采用更多的一種方式。

1 基于內(nèi)容檢索的三維模型標注方法

三維模型標注與三維模型檢索是可以相互轉(zhuǎn)化相互影響的，在利用模型標注來解決模型檢索的同時，我們也可以利用模型檢索來解決模型標注的問題。

基于內(nèi)容的三維模型標注方法是從三維數(shù)據(jù)內(nèi)容出發(fā)，利用算法從模型中自動提取出能描述其外觀的特征信息，并用一種緊湊的數(shù)據(jù)結(jié)構(gòu)(特征描述符)來表達這種特征。利用特征描述符之間的內(nèi)在聯(lián)系來表達三維模型之間的特征相似性，并將具有相似性較高的三維模型及其標簽作為傳播目標的一種標注方法。其中，特征描述符提取及特征相似度比對是三維模型檢索與標注的核心部分。

1.1 三維模型語義標注流程

在三維模型內(nèi)容檢索過程中，檢索出的結(jié)果模型與待匹配的模型間具有一定的相關(guān)性，這種相關(guān)是具有傳遞性的。因此，可以在傳統(tǒng)的三維模型語義標注方法的基礎(chǔ)上，加入模型相關(guān)基數(shù)度量方法，通過模型間內(nèi)容特征的比對及相似程度的測算，將近鄰模型的已知標簽傳播給未知模型，最終完成三維模型的標注,如圖1所示。

具體實現(xiàn)過程如下：

(1) 建立三維模型樣本庫。將三維模型、模型略縮圖及其標簽存入樣本庫。

(2) 抽取三維模型特征描述符。通過提取與保存特征描述符來進行三維模型的內(nèi)容特征存取與相似度的比對。本文主要利用計算三維模型的D2分布特征及相關(guān)特征描述符來提取三維模型內(nèi)容特征。

(3) 計算三維模型相似度距離。利用EMD距離計算三維模型間的特征相似度。

(4) 選取近鄰模型標簽進行標注。通過近鄰投票算法計算三維模型相似近鄰中標簽出現(xiàn)頻率，通過構(gòu)建近鄰中的標簽子空間來實現(xiàn)三維模型的多標簽標注。

1.2 三維模型特征提取

三維模型標注的關(guān)鍵在于如何提取特征描述符(Feature Descriptor)，該描述符是模型內(nèi)在特征的抽象描述，一般要求其與模型的旋轉(zhuǎn)、平移、縮放無關(guān)。研究發(fā)現(xiàn)三維模型的形狀分布特性是目前描述三維模型外部特征的一種較為簡單高效的特征描述方式。以其為代表的主要有Osada提出的形狀分布方法[8]、Suzuki提出的點密度方法以及Kazhdan提出的體素化方法等[9]。

Osada等提出的以形狀分布作為特征的形狀分布計算方法。分別是: 三個頂點構(gòu)成的角度、頂點到中心的距離、任意兩個頂點之間的距離、任意三個頂點組成三角片的面積和任意四個頂點組成四面體的體積等函數(shù),如圖2所示。

通過對A3分布、D1分布、D2分布、D3分布、D4分布做了大量的實驗，分析結(jié)果證明，認為任意兩個頂點之間的距離作為幾何函數(shù)的效果最好[10]。同時，D2分布函數(shù)對模型的描述能力優(yōu)于其它四種形狀函數(shù)，尤其是對一些較為簡單的三維模型，其區(qū)別能力較強且計算簡單。

D3(面積)D4(體積)

圖2 五種分布方式示例圖

因此，本文使用D2分布統(tǒng)計(D2)作為三維模型的基本特征描述符，提取出表現(xiàn)三維模型形狀特征的特征向量。簡要概述D2算法流程：首先打開一個三維模型，對模型進行離散化處理后在其表面生成離散點。然后根據(jù)模型表面的三角面片數(shù)及其面積計算并隨機選取離散點，然后再計算三角面中隨機點對之間的距離，最后進行D2距離的統(tǒng)計和表征,如圖3所示。

圖3 D2特征提取流程圖

由于三維模型主要是由許多三角面片渲染而成。因此我們的目標是在三維模型表面上的網(wǎng)格上生成一個隨機均勻分布的點集。如果一個點在某個子區(qū)域中分布的概率與該子區(qū)域的面積成正比，則該分布是均勻分布的。因此我們可以通過計算三維模型每個面的面積來計算每個面所需隨機生成的點數(shù),如圖4所示。

三角面片

點集(n=100)

點集(n=1 000)

(1)

(2)

其中X、Y、Z分別為三角形面片上的三個頂點的坐標。

形成采樣點后將其平均分為兩個集合形成點對，通過歐氏距離公式(3)計算點對間的距離di并統(tǒng)計距離分布結(jié)果,如式(3)。

(3)

通過計算點對間的距離D(di),i=0,…,n，最后按照最大距離歸一化到64維的D2分布統(tǒng)計中形成D2分布特征向量θ(di),i=64。

1.3 三維模型相似度度量

基于特征描述符，模型之間相似程度的衡量可以轉(zhuǎn)化為對其相應特征描述符的比對。本文采用EMD(Earth Mover’s Distance)來計算描述符的相似度。

EMD距離可以理解為從一種分布變換為另一種分布的最小代價，它最早被 Peleg、Warman和Rom介紹應用于計算視覺問題[10]。給定兩個分布，定義一個兩分布之間相似性的量化測量標準，使之最大可能地近似視覺感知上的相似性。

通過提取三維模型的D2分布特征向量θ(di)來計算三維模型之間的特征相似性，設(shè)三維模型A的特征為feaA(θi)，三維模型B的特征為feaB(θi)，那么我們可以計算三維模型之間的EMD距離如公式(4)。

(4)

1.4 基于近鄰標簽傳遞的三維模型語義標注

在大量三維模型數(shù)據(jù)中，如果樣本三維模型之間的形狀或視覺特征是相似的，那么它所包含的語義也是存在一定相關(guān)性的，因此我們可以利用三維模型底層特征的相似性來描述和傳遞它們之間的高層語義。

通過之前的工作我們已經(jīng)獲得了三維模型的D2分布特征及其相似性比對方法，借助檢索三維模型的內(nèi)容特征，我們可以通過內(nèi)容檢索對已有標簽的三維模型進行模型特征及標簽的獲取，通過相似模型及其所含標簽出現(xiàn)頻率對其進行排序，出現(xiàn)頻率高的標簽與三維模型間的相似度較高。因此本節(jié)基于這種理論提出了一種基于內(nèi)容檢索的三維模型標注方法。

首先選取三維模型x的K個形狀特征相似的近鄰，然后提取三維模型TOP-K個近鄰的n個標簽，統(tǒng)計全部標簽出現(xiàn)頻率后對其進行排序，這樣三維模型x對于標簽n的相關(guān)度就可以表示為sim(x,ni)，相關(guān)度求解公式可以按照式(5)來計算。通過上述方法，最終可以將出現(xiàn)頻次較高的標簽作為三維模型高相關(guān)度的標簽傳遞給對應的未知模型如式(5)。

(5)

其中countneighborhood(ni)表示三維模型x的k近鄰中具有標簽ni的樣本數(shù)，count(ni)為數(shù)據(jù)集中具有標簽ni的模型數(shù)，p(n,x)為模型x具有標簽w的概率。

通過計算出的三維模型與標簽相似程度，我們就可以對未知模型進行近鄰選取與標簽標注，例如假設(shè)我們需對模型標注K個標簽，那么我們就可以選取標簽相似度在TOP-K個位置的標注詞作為該模型的語義標簽。

2 實驗及結(jié)果

2.1 實驗設(shè)置與評價準則

(1) 實驗設(shè)置

實驗數(shù)據(jù)集主要來自于PSB中的1 814個模型，為了測試本文所提方法對標注信息的自動標注效果，數(shù)據(jù)集分為兩個部分，一部分數(shù)據(jù)通過標注員進行手工多語義標注，另一部分為待標注的測試數(shù)據(jù)集。

(2) 評價準則

2.2 實驗結(jié)果

本次實驗是在VS2010上進行開發(fā)，利用Oracle數(shù)據(jù)庫進行模型及特征的存儲。通過單個模型標注、多個模型批量自動標注等方法進行模型標注后，再對標注準確程度進行核對。本文方法自動標注的部分結(jié)果,如圖5所示。

圖5 部分自動標注效果圖

為了比較本文所提方法與其他三維模型標注方法的標注效率，圖2分別列出了幾種標注方式下的平均標簽準確率、平均標簽召回率。這幾種檢索方式包括：歐氏距離度量方法、一個比較典型的監(jiān)督分類學習方法(SVM 算法+歐氏距離)[11]以及本文所提到的方法(D2分布算法+EMD距離),如圖。

由圖可見，本文所提方法在少量標簽信息時表現(xiàn)了較好的標注準確率。從上圖可知，本文的方法在檢索標簽數(shù)量q為3的時候的標注召回率效果最好，這也體現(xiàn)了標簽個數(shù)在3個的時候能夠更加全面準確的描述三維模型的語義。除此之外本文還計算了基于內(nèi)容檢索三維模型的平均三維模型準確率、平均三維模型召回率，根據(jù)三維模型檢索TOP-K近鄰進行了準確率與召回率的統(tǒng)計,如圖7所示。

3 總結(jié)

本文提出了一種基于內(nèi)容檢索的三維模型標注方法。首先，結(jié)合模型的形狀分布特征匹配出形狀相似的模型，計算出樣本模型中的相似模型及其標簽并提取出TOPK的相似模型標簽，然后，通過模型與標簽間的近鄰投票方法計算出模型標簽間的相關(guān)基數(shù)，確定樣本標簽中相關(guān)程度較高的標簽，組成近鄰標簽集；最后，結(jié)合標簽集確定待標注模型的標簽。通過對三維模型自動語義標注的準確性實驗，有效的驗證本文提出方法的準確性與魯棒性。

(a) 平均標簽準確率(輸出標簽數(shù)量q區(qū)間為1-4)

(b) 平均標簽召回率(輸出標簽數(shù)量q區(qū)間為1-4)

(c) 平均標簽F1值折線圖

圖7 平均三維模型準確率召回率及F1(輸出三維模型數(shù)量q區(qū)間為1-4)