田楓， 孫寧， 劉賢梅

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

0 引言

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

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

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

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

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

1.1 三維模型語義標(biāo)注流程

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

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

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

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

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

(4) 選取近鄰模型標(biāo)簽進(jìn)行標(biāo)注。通過近鄰?fù)镀彼惴ㄓ?jì)算三維模型相似近鄰中標(biāo)簽出現(xiàn)頻率，通過構(gòu)建近鄰中的標(biāo)簽子空間來實(shí)現(xiàn)三維模型的多標(biāo)簽標(biāo)注。

1.2 三維模型特征提取

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

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

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

D3(面積)D4(體積)

圖2 五種分布方式示例圖

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

圖3 D2特征提取流程圖

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

三角面片

點(diǎn)集(n=100)

點(diǎn)集(n=1 000)

(1)

(2)

其中X、Y、Z分別為三角形面片上的三個(gè)頂點(diǎn)的坐標(biāo)。

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

(3)

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

1.3 三維模型相似度度量

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

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

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

(4)

1.4 基于近鄰標(biāo)簽傳遞的三維模型語義標(biāo)注

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

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

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

(5)

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

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

2 實(shí)驗(yàn)及結(jié)果

2.1 實(shí)驗(yàn)設(shè)置與評價(jià)準(zhǔn)則

(1) 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)數(shù)據(jù)集主要來自于PSB中的1 814個(gè)模型，為了測試本文所提方法對標(biāo)注信息的自動(dòng)標(biāo)注效果，數(shù)據(jù)集分為兩個(gè)部分，一部分?jǐn)?shù)據(jù)通過標(biāo)注員進(jìn)行手工多語義標(biāo)注，另一部分為待標(biāo)注的測試數(shù)據(jù)集。

(2) 評價(jià)準(zhǔn)則

2.2 實(shí)驗(yàn)結(jié)果

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

圖5 部分自動(dòng)標(biāo)注效果圖

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

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

3 總結(jié)

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

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

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

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

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