基于特征提取的三維模型檢索技術(shù)研究

俞曉妮

沈陽(yáng)職業(yè)技術(shù)學(xué)院，遼寧沈陽(yáng)110045

0 引言

隨著信息技術(shù)的發(fā)展，計(jì)算機(jī)信息檢索的對(duì)象己經(jīng)從文本、聲音、圖像和視頻等多媒體數(shù)據(jù)類(lèi)型，擴(kuò)展到真實(shí)豐富的三維模型。三維模型廣泛應(yīng)用于機(jī)械產(chǎn)品設(shè)計(jì)、建筑工業(yè)設(shè)計(jì)、虛擬現(xiàn)實(shí)、3D 游戲、影視動(dòng)畫(huà)等領(lǐng)域。對(duì)三維模型檢索技術(shù)的研究不僅有重要的理論意義和實(shí)用價(jià)值。

三維模型檢索系統(tǒng)可以分為通用領(lǐng)域和專(zhuān)業(yè)領(lǐng)域的三維模型檢索系統(tǒng)。目前己經(jīng)出現(xiàn)了基于WEB 的通用領(lǐng)域的三維模型檢索系統(tǒng)，用戶可以通過(guò)網(wǎng)絡(luò)使用這些檢索系統(tǒng)來(lái)檢索自己需要的模型，但檢索還有一定的局限性。近年來(lái)專(zhuān)業(yè)領(lǐng)域的三維模型檢索系統(tǒng)得到了廣泛的應(yīng)用，比如生物分子、機(jī)械零件、地形匹配等。這些檢索與通用領(lǐng)域的三維模型檢索系統(tǒng)具有較大的相似性，但也具有自身的特點(diǎn)。通常而言，專(zhuān)業(yè)領(lǐng)域的三維模型檢索系統(tǒng)可以利用專(zhuān)業(yè)領(lǐng)域模型的特點(diǎn)、需求等信息，快速地檢索出所需模型。具有如下特點(diǎn)：1）專(zhuān)業(yè)領(lǐng)域信息強(qiáng)。在各自的領(lǐng)域可能需求的精確性不高，這樣可以縮短檢索的時(shí)間;2）模型結(jié)構(gòu)復(fù)雜度較低，也比較有規(guī)則，如機(jī)械零件模型、工程動(dòng)畫(huà)中的常見(jiàn)模型等，這樣在特征提取方面較容易實(shí)現(xiàn)。

1 三維模型檢索簡(jiǎn)介

近些年來(lái)，針對(duì)文本信息的檢索技術(shù)日臻完善，針對(duì)二維圖像以及影視資料的檢索技術(shù)迅速投入應(yīng)用，Google 和百度等著名搜索引擎的出現(xiàn)已經(jīng)改變了人們查找信息的固有方式。相比文字和二維影像的檢索，對(duì)于三維模型的檢索更具有其復(fù)雜性和特殊性。盡管也有數(shù)量不多的機(jī)構(gòu)提供模型檢索服務(wù)，然而無(wú)論是從檢索的效率還是結(jié)果的準(zhǔn)確性等因素上來(lái)考慮，現(xiàn)有的模型檢索技術(shù)距離高質(zhì)量的商用水平仍有很大的提升空間。廣闊的應(yīng)用前景吸引了世界各地的研究人員投入大量的時(shí)間和精力從事模型檢索相關(guān)領(lǐng)域的研究和推廣，并逐漸形成了相對(duì)統(tǒng)一的三維模型檢索的系統(tǒng)架構(gòu)。如圖1 所示。

圖1 三維模型檢索系統(tǒng)架構(gòu)

一個(gè)完整的三維模型搜索引擎通常包括離線和在線兩個(gè)并行的部分，分為數(shù)據(jù)獲取、數(shù)據(jù)分析與檢索匹配三大模塊。

離線部分由數(shù)據(jù)的獲取和數(shù)據(jù)的分析組成，具體的流程包括：

1）通過(guò)“網(wǎng)絡(luò)爬行器”等途徑獲取三維模型；

2）提取三維模型的特征；

3）根據(jù)特征建立索引等。

在線部分即檢索匹配，具體的流程包括：

1）用戶通過(guò)交互界面選擇查詢(xún)方式提交查詢(xún)；

2）根據(jù)查詢(xún)方式進(jìn)入相應(yīng)的特征提取模塊提取相應(yīng)的特征；

3）進(jìn)入匹配模塊和索引模塊，返回特征最相近的結(jié)果。

這三個(gè)功能模塊都在模型檢索系統(tǒng)中發(fā)揮著重要作用，算法設(shè)計(jì)的優(yōu)劣關(guān)乎系統(tǒng)整體的檢索性能、精確度和有效性。作為檢索三維模型文件的界面要能夠易于普通用戶快速地學(xué)習(xí)和使用，使得用戶在短暫的時(shí)間內(nèi)能夠充分表達(dá)清楚自己的檢索訴求。檢索系統(tǒng)在獲得用戶提供的特征描述后，要能迅速?gòu)闹刑崛∮行畔⒉⑴c數(shù)據(jù)庫(kù)中現(xiàn)存的特征進(jìn)行比對(duì)。

模型檢索系統(tǒng)應(yīng)該對(duì)相關(guān)的模型提取出相近的特征描述，同時(shí)能夠有效地區(qū)分不相關(guān)的模型。在交互系統(tǒng)中，特征提取和匹配的計(jì)算過(guò)程應(yīng)在較短的時(shí)間內(nèi)完成，不應(yīng)使用戶感到明顯的延遲。尋求更高效準(zhǔn)確的特征描述和匹配算法一直是科研人員不斷追求的目標(biāo)和研究的重點(diǎn)。隨著三維模型文件數(shù)量的急劇擴(kuò)張，從超大容量的數(shù)據(jù)庫(kù)中快速地提取出查詢(xún)結(jié)果也已成為模型檢索中函待解決的問(wèn)題。因此如何建立高效的索引結(jié)構(gòu)以滿足用戶對(duì)檢索效率日益提高的需求也逐漸引起了學(xué)術(shù)界與產(chǎn)業(yè)界的高度重視。

三維模型檢索系統(tǒng)研究盡管取得了一定的進(jìn)展，但還處于初期階段，很多技術(shù)穩(wěn)定性還不夠，三維模型檢索技術(shù)還有待于進(jìn)一步的研究。三維模型檢索系統(tǒng)發(fā)展趨勢(shì)主要集中在以下幾個(gè)方面：

1）現(xiàn)有檢索技術(shù)一般針對(duì)整體特征進(jìn)行檢索，未來(lái)的檢索技術(shù)應(yīng)該具備整體和局部檢索的功能，不僅能從同類(lèi)物體中檢索對(duì)象，還要能從異類(lèi)物體中檢索對(duì)象;不僅能從幾何特征檢索，還可根據(jù)物體的顏色，材質(zhì)，粗糙度等屬性進(jìn)行檢索；

2）從檢索效果來(lái)看，現(xiàn)有技術(shù)還不能滿足用戶的需要，開(kāi)發(fā)與三維模型輸入格式無(wú)關(guān)、與模型局部坐標(biāo)系無(wú)關(guān)的檢索技術(shù)成為一個(gè)重要的研究方向；

3）建立一個(gè)合理的、權(quán)威的、統(tǒng)一的評(píng)價(jià)體系；

4）現(xiàn)有檢索界面不能滿足某些人群的需要，開(kāi)發(fā)適合通用、專(zhuān)業(yè)領(lǐng)域的界面成為一個(gè)重要研究方向。

2 三維模型特征提取方法比較

2.1 基于輪廓形狀的特征提取

計(jì)算并比較三維模型的輪廓特征，從而獲得三維模型的幾何相似性，是基于輪廓形狀的幾何特征提取算法實(shí)現(xiàn)的思想。其中，三維模型輪廓特征主要包括了頂點(diǎn)以及網(wǎng)格的分布特征。

Osada 提出了通過(guò)隨機(jī)采樣來(lái)獲得三維模型的幾何特征的形狀分布方法。對(duì)于從三維模型表面上隨即采樣到的兩個(gè)點(diǎn)，可得到它們之間的歐氏距離(DZ 距離)，統(tǒng)計(jì)通過(guò)以上方法而得到的大量的歐氏距離，可獲得三維模型的形狀分布曲線。

形狀分布直方圖算法可以簡(jiǎn)要概述為：首先使用幾何函數(shù)來(lái)計(jì)算三維模型頂點(diǎn)的形狀特征，從而獲得形狀特征分布直方圖，然后比較直方圖的相似距離以獲得三維模型的幾何相似性。

2.2 基于拓?fù)湫螤畹奶卣魈崛?/h3>

通過(guò)比較三維模型的拓?fù)浣Y(jié)構(gòu)來(lái)獲得三維模型相似性，這是基于拓?fù)湫螤畹娜S模型相似性比較算法的核心思想。其中，最常使用的拓?fù)浣Y(jié)構(gòu)信息包括三維模型的分支與連通性等。模型的Reeb 圖是從連通區(qū)域的角度來(lái)計(jì)算三維模型的拓?fù)浣Y(jié)構(gòu)。在該方法中首先將三維模型投影到二值圖像，從而作出二值圖像的Reeb 圖，然后計(jì)算Reeb 圖的基本元素，包括圓環(huán)的個(gè)數(shù)Nuln(R)、向上分支個(gè)數(shù)Num 口B)、向下分支個(gè)數(shù)Num 側(cè)B)、每個(gè)分支的枝權(quán)數(shù)量Sum。最后，根據(jù)Reeb 圖的這些基本元素，計(jì)算出Reeb 圖的特征，

采用基于多分辨率Reeb 圖的骨架提取方法，不僅可以描述三維模型的特征，同時(shí)還具備了描述模型的空間拓?fù)潢P(guān)系的能力。對(duì)于局部匹配乃至全局匹配該方法都是較為適用的。

在描述三維模型拓?fù)浣Y(jié)構(gòu)的方法中，除了Reeb 圖以外，還有中軸線方法。從三維模型骨架的角度來(lái)計(jì)算三維模型的拓?fù)浣Y(jié)構(gòu)是中軸線方法的思路。

2.3 基于視覺(jué)形狀的特征提取

在基于視覺(jué)的三維模型相似性比較算法中，通過(guò)比較三維模型在各個(gè)方向的視覺(jué)圖像的形狀相似性可以獲得三維模型的相似性。

基于視覺(jué)相似的特征提取方法的提出是基于這樣一個(gè)事實(shí)：從任意視角來(lái)觀察兩個(gè)相似的物體，它們都應(yīng)該具有相似性。通過(guò)比較三維模型在多個(gè)方向的視覺(jué)圖像的形狀相似性來(lái)獲得三維模型的相似性是基于視覺(jué)形狀的特征提取方法的基本思想。在該方法中，首先將三維模型投影到二維視圖上，再?gòu)牟煌Ｐ蛯?duì)應(yīng)的二維視圖提取特征進(jìn)行相似性匹配計(jì)算。在這種算法中，基于二維輪廓圖的比較和基于視覺(jué)相似的檢索技術(shù)是較為典型的例子。

Lomer 在預(yù)處理階段，采用以一組二進(jìn)制表達(dá)的二維圖像來(lái)對(duì)三維模型的特征進(jìn)行描述的方法，然后在對(duì)應(yīng)的二維圖像之間進(jìn)行后續(xù)的相似性匹配計(jì)算，并且應(yīng)用了圖像檢索中關(guān)于特征提取的方法。

在基于透視投影的三維模型幾何相似性比較算法中，先將三維模型用正二十面體包圍，而后選取若干個(gè)視點(diǎn)對(duì)三維模型進(jìn)行投影，由此可以畫(huà)出二值圖像的Reeb 圖，再通過(guò)計(jì)算Reeb 圖的特征從而求出投影圖像的拓?fù)湎嗨凭嚯x，最后可得到三維模型的相似距離。

基于3D 模型的ZD 輪廓圖的比較方法中，從三維模型正視、俯視和側(cè)視三個(gè)固定方向提取出模型的輪廓圖，首先找到這樣一個(gè)圓，該圓恰好包括了輪廓圖，將該圓等分成固定數(shù)量的圓環(huán)，構(gòu)成圓環(huán)函數(shù)，然后對(duì)每個(gè)圓環(huán)進(jìn)一步分解，使其由一系列三角函數(shù)的和構(gòu)成;根據(jù)旋轉(zhuǎn)不變頻率的振幅，可計(jì)算出每個(gè)圓環(huán)的特征向量，最后，利用所有的圓環(huán)特征向量構(gòu)成模型輪廓圖的二維特征向量。

3 三維模型檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

3.1 系統(tǒng)硬件和軟件配置

本系統(tǒng)采用了普林斯頓大學(xué)的標(biāo)準(zhǔn)三維模型數(shù)據(jù)庫(kù)，特征計(jì)算使用了OFF 文件，三維模型的顯示使用了 FLT 文件。

機(jī)器配置 ：2.0 Intel P4、512 RAM、Geforce4 顯卡。

開(kāi)發(fā)工具 ：Visual studio 2003、Open Scene Graph 2.4。

3.2 三維模型數(shù)據(jù)庫(kù)的獲取及文件組織結(jié)構(gòu)

普林斯頓大學(xué)的三維形狀檢索和分析研究小組構(gòu)建了一個(gè)三維標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)用于檢索性能測(cè)試。這些三維模型被轉(zhuǎn)化成為統(tǒng)一的文件形式。經(jīng)過(guò)篩選和手工分類(lèi)，從中選擇出比較有代表性的1814 個(gè)三維模型用于構(gòu)造標(biāo)準(zhǔn)三維模型數(shù)據(jù)庫(kù)。

這些模型被分為兩個(gè)集合，稱(chēng)為訓(xùn)練集(Training)和測(cè)試集(Testing)，其中訓(xùn)練集和測(cè)試集中各包括 907 個(gè)三維模型。訓(xùn)練集用于算法不穩(wěn)定時(shí)測(cè)試算法，測(cè)試集是算法穩(wěn)定時(shí)與不同算法進(jìn)行比較時(shí)采用的集合。為了對(duì)不同算法試驗(yàn)使用一個(gè)統(tǒng)一的數(shù)據(jù)庫(kù)，以便于對(duì)不同算法的檢索效果進(jìn)行比較。本檢索系統(tǒng)采用的三維模型庫(kù)是從普林斯頓大學(xué)形狀分析實(shí)驗(yàn)室網(wǎng)站上下載的標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)。

本系統(tǒng)的數(shù)據(jù)庫(kù)共有1110 個(gè)模型，分為 64 類(lèi)，每個(gè)類(lèi)別中從0 開(kāi)始順序編號(hào)。三維模型是以文件的形式存放，對(duì)于每個(gè)三維模型一共包含 4 個(gè)文件：三維模型文件(.off)、三維模型的描述文件(.txt)、三維模型的二維縮略圖文件(.jpg)、用于三維顯示的文件(.flt)，將其分別存放在不同的目錄中。

3.3 三維模型檢索系統(tǒng)結(jié)構(gòu)設(shè)計(jì)

三維模型檢索系統(tǒng)主要包括用戶檢索界面、特征提取、特征匹配、特征向量數(shù)據(jù)庫(kù)以及三維模型文件的二維和三維展示的管理，如圖所示。用戶使用檢索界面進(jìn)行三維模型檢索，在檢索界面中，本系統(tǒng)采用的是示例查詢(xún)模式，在用戶選中一個(gè)示例模型后，該模型的相應(yīng)信息被自動(dòng)傳送到特征匹配模塊，特征匹配模塊將接收到的三維模型與三維模型特征向量和索引數(shù)據(jù)庫(kù)中的特征信息進(jìn)行匹配，從而得出檢索的結(jié)果，并將結(jié)果返回到用戶檢索界面，供用戶挑選需要的三維模型。特征匹配模塊主要是圓環(huán)分割的方法和圖像矩的方法。特征匹配模塊將接收到的三維模型與三維模型特征向量和索引數(shù)據(jù)庫(kù)中的特征信息進(jìn)行匹配，從而得出檢索的結(jié)果，并將結(jié)果返回到用戶檢索界面。特征提取模塊主要是實(shí)現(xiàn)在正交主平面的基礎(chǔ)上進(jìn)行特征提取的方法，從三維模型庫(kù)中提取三維模型的圓環(huán)分割信息和矩信息，并將這些特征信息保存到三維模型特征向量和索引數(shù)據(jù)庫(kù)中。如圖2 所示。

3.4 三維模型檢索系統(tǒng)界面的設(shè)計(jì)

在檢索系統(tǒng)界面中，左側(cè)顯示模型的分類(lèi)樹(shù)形結(jié)構(gòu)，右側(cè)為顯示模型的三維窗口。根據(jù)數(shù)據(jù)的組織形式，用戶從“類(lèi)別”中選擇用于匹配的索引三維模型種類(lèi)，然后從“模型”下拉菜單中選擇需要查找的三維模型。選完之后索引三維模型就會(huì)在右側(cè)三維顯示，用戶可以與其交互。

為了使模型的顯示更加直觀，系統(tǒng)對(duì)模型進(jìn)行了三維展示。首先將OFF 文件通過(guò)軟件 Deep Exploration 將模型轉(zhuǎn)換為 flt 格式 ，然后用開(kāi)源的 Open Scene Graph 和 Visual studio 2003 編寫(xiě) ActiveX 控件用于模型的三維展示。

在檢索界面的左側(cè)樹(shù)形目錄中顯示了所有的 64 個(gè)分類(lèi)的模型文件名，點(diǎn)擊樹(shù)形目錄中的任意模型文件名稱(chēng)，在右側(cè)的 ActiveX 控件窗口中可以方便的從各個(gè)角度瀏覽三維模型。通過(guò)鼠標(biāo)的操作實(shí)現(xiàn)對(duì)模型的旋轉(zhuǎn)、平移、縮放操作，并在模型的下方顯示模型文件的名稱(chēng)和大小信息。

圖2 三維模型檢索系統(tǒng)示意圖

3.5 三維模型檢索結(jié)果顯示設(shè)計(jì)

三維模型檢索系統(tǒng)采用了示例查詢(xún)的檢索方式。用戶可以通過(guò)樹(shù)型目錄在三維控件中瀏覽系統(tǒng)提供的所有的三維模型，并且從瀏覽的三維模型中選擇一個(gè)三維模型進(jìn)行檢索。當(dāng)檢索一個(gè)模型時(shí)，在瀏覽界面中瀏覽三維模型確定檢索目標(biāo)，然后將檢索結(jié)果在結(jié)果界面中顯示。具體過(guò)程是用戶點(diǎn)擊檢索按鈕，系統(tǒng)就會(huì)首先對(duì)模型進(jìn)行預(yù)處理，然后自動(dòng)計(jì)算用戶選擇的三維模型的特征向量，最后根據(jù)計(jì)算出的特征向量搜尋特征向量數(shù)據(jù)庫(kù)，計(jì)算模型之間的特征距離，按照距離由小到大的順序在檢索結(jié)果顯示界面中列出最佳匹配模型的縮略圖。用戶可以點(diǎn)擊縮略圖，在右側(cè)的三維顯示窗口中從各個(gè)角度觀看所選中的三維模型，并在下側(cè)顯示模型的大小信息，用戶可以點(diǎn)擊模型的二維縮略圖，然后點(diǎn)擊 Download 按鈕來(lái)下載所需要的模型。

4 結(jié)論

本文設(shè)計(jì)的三維模型檢索系統(tǒng)，主要從三維模型檢索系統(tǒng)的文件組織形式、系統(tǒng)的結(jié)構(gòu)、界面的設(shè)計(jì)、模型的三維展示等方面進(jìn)行了介紹，對(duì)提出的特征提取方法進(jìn)行了實(shí)驗(yàn)驗(yàn)證。檢索系統(tǒng)通過(guò)示例三維展示的方式進(jìn)行三維模型檢索，即用戶通過(guò)選擇數(shù)據(jù)庫(kù)中存在的三維模型進(jìn)行三維瀏覽然后查詢(xún)。系統(tǒng)中的三維模型、三維模型的二維縮略圖以及三維模型信息采用文件方式存放，依靠操作系統(tǒng)的文件管理功能進(jìn)行管理。此三維模型檢索系統(tǒng)的具有簡(jiǎn)單易操作的特點(diǎn)，檢索結(jié)果雖然還有不足的地方，但總的來(lái)看還是比較理想的，為進(jìn)一步研究建立了很好的實(shí)驗(yàn)平臺(tái)。