論文基于二維投影的三維模型檢索方法研究

1、摘要3D數(shù)據(jù)獲取技術(shù)、圖形硬件、三維數(shù)據(jù)模型和可視化技術(shù)的發(fā)展，致使3D模型的增多。三維掃描技術(shù)與造型工具的日益普及，擴(kuò)展了可供使用的三維模型數(shù)據(jù)庫：互聯(lián)網(wǎng)絡(luò)的擴(kuò)張?jiān)鰪?qiáng)了人們獲取分散存儲(chǔ)的三維模型的能力，并為有效傳播高質(zhì)量模型創(chuàng)造了條件，因此研究一種自動(dòng)的、對(duì)用戶友好的三維模型的檢索技術(shù)成為一個(gè)重要的課題。對(duì)于基于內(nèi)容的3D模型檢索系統(tǒng)，最根本的問題是選取恰當(dāng)?shù)奶卣鱽韰^(qū)別不同的形狀，以用來有效的索引相似的文件數(shù)據(jù)。3D模型檢索方法可大致的分為3類：基于外形的低層方法；基于結(jié)構(gòu)的高層方法；基于視角的方法?；谕庑蔚牡蛯臃椒▏L試通過幾何和拓?fù)涞膶傩悦枋?D模型的形狀，外形可以是由單獨(dú)向量組成的一些

2、外形參數(shù)的固定數(shù)值或一系列外形參數(shù)的分布范圍；基于結(jié)構(gòu)的高層方法嘗試把3D模型分解成一系列關(guān)鍵部分，并提煉出這些部分的幾何關(guān)系；基于視角的方法通過一系列從不同角度的二維投影來得出三維模型的外觀。在對(duì)已有三維模型檢索技術(shù)的進(jìn)行系統(tǒng)研究的基礎(chǔ)上，本篇論文提出了一種基于二維投影的三維模型檢索方法，用以3D模型檢索。此方法是以常量去轉(zhuǎn)化并評(píng)價(jià)3D模型，并且它對(duì)于旋轉(zhuǎn)是穩(wěn)定的。實(shí)驗(yàn)數(shù)據(jù)顯示，對(duì)于一些類型的三維模型，提出的基于二維投影的方法有著良好的查全率和查準(zhǔn)率，是行之有效的方法之一。關(guān)鍵詞：三維模型檢索；基于二維投影；特征提??；相似度計(jì)算第一章緒論11研究的背景及意義我們處在一個(gè)三維世界里，一切被我們

3、感知的物體都以三維的形式存在，人類的視覺不僅能夠感知二維平面的信息，且具有立體三維的特性。與二維圖像相比，三維的模型所提供的視覺感知細(xì)節(jié)更多、更豐富，能夠給人們帶來更加詳細(xì)的信息。三維模型的研究成為了一個(gè)熱點(diǎn)話題，是因?yàn)椋?1)隨著三維數(shù)據(jù)獲取，如數(shù)字?jǐn)z像機(jī)、掃描儀、核磁共振和3D激光掃描儀設(shè)備的功能越來越強(qiáng)，使用越來越方便，技術(shù)手段不斷進(jìn)步和成熟，使三維信息獲取和表達(dá)變得越來越容易；(2)眾多三維建模軟件和工具(如3DMax，AutoCAD，Poser，Core3D等)使得三維模型的設(shè)計(jì)變得簡(jiǎn)單；(3)三維模型建模的專業(yè)需求越來越強(qiáng)，分子工程、地貌氣象分析、工業(yè)產(chǎn)品設(shè)計(jì)、醫(yī)學(xué)建模、虛擬軍事行

4、動(dòng)等，都廣泛使用了三維技術(shù)。構(gòu)建數(shù)字化模型，可幫助科研人員更加直觀、精確地處理各自領(lǐng)域問題；(4)在娛樂領(lǐng)域，游戲、電影產(chǎn)業(yè)的發(fā)展，使人們已經(jīng)不滿足于二維畫面，傳統(tǒng)的制作方法已經(jīng)成為歷史，精美絢麗的三維動(dòng)畫隨處可見。而三維建模本身，也成為了一門藝術(shù)門派；(5)計(jì)算機(jī)圖形學(xué)技術(shù)發(fā)展迅速，三維圖形處理硬件和CPU的速度已足夠快，而且價(jià)格便宜，使得三維數(shù)據(jù)能在微機(jī)上快速處理和顯示；(6)蓬勃發(fā)展的互聯(lián)網(wǎng)技術(shù)也使人們對(duì)信息共享和處理的方式發(fā)生了根本性的改變，網(wǎng)絡(luò)已經(jīng)成為人們獲取信息的重要途徑?；ヂ?lián)網(wǎng)的普及，使三維模型被更廣泛地轉(zhuǎn)播和共享。(7)各軟件，各版本的三維數(shù)據(jù)兼容化、共享化趨勢(shì)，加速了模型的標(biāo)

5、準(zhǔn)化進(jìn)程。三維模型已成為繼聲音、圖像和視頻之后的第四種多媒體數(shù)據(jù)類型。目前有數(shù)以兆計(jì)的三維模型存在，而且每天都有大量的三維模型產(chǎn)生和傳播，可以預(yù)見，在不久的將來，人們可以像使用二維圖像一樣使用三維模型。因此，為了從浩如煙海的信息中快速準(zhǔn)確地找到需要的內(nèi)容，人們存在著對(duì)三維模型進(jìn)行檢索的迫切需求。12三維模型檢索系統(tǒng)的發(fā)展作為新興的領(lǐng)域，三維檢索有重要的學(xué)術(shù)意義及應(yīng)用價(jià)值。如，目前在我國(guó)，知識(shí)產(chǎn)權(quán)保護(hù)工作越來越受到重視，而知識(shí)產(chǎn)權(quán)保護(hù)的相關(guān)工作量也越來越大。在各種專利尤其是外觀設(shè)計(jì)的申請(qǐng)的核準(zhǔn)、審查和批復(fù)的過程中，都需要對(duì)各種三維模型進(jìn)行比較。在工業(yè)設(shè)計(jì)過程中，三維數(shù)據(jù)可以完全提供產(chǎn)品的幾何信息

6、，為了實(shí)現(xiàn)給料、加工、質(zhì)檢的自動(dòng)化，需要反復(fù)快速地檢索、匹配標(biāo)準(zhǔn)零件模型庫，在一個(gè)大型數(shù)據(jù)庫中找到適合的三維模型。數(shù)字化地球戰(zhàn)略的推行，數(shù)字農(nóng)業(yè)，生態(tài)環(huán)境保護(hù)，風(fēng)險(xiǎn)預(yù)警，路徑規(guī)劃應(yīng)用中需要檢索海量的三維模型標(biāo)本。分子生物學(xué)基因技術(shù)中，蛋白質(zhì)三維結(jié)構(gòu)與功能的關(guān)系，是當(dāng)前的重大科學(xué)問題，蛋變質(zhì)三維結(jié)構(gòu)相似性比較則是探索生命科學(xué)奧秘的重要手段，從計(jì)算機(jī)圖形和視覺的角度來審視蛋白質(zhì)三維空間結(jié)構(gòu)的相似性檢索，有著廣闊的應(yīng)用前景?；ヂ?lián)網(wǎng)上也出現(xiàn)了大量的三維模型庫，許多網(wǎng)站也將三維模型作為一種數(shù)字化商品提供給使用者。相對(duì)于二維多媒體信息的獲取，三維模型的建模更加復(fù)雜。顯然，搜索、共享大量的三維模型數(shù)據(jù)；在現(xiàn)

7、有的模型基礎(chǔ)上進(jìn)行分類、比較、改進(jìn)；把互聯(lián)網(wǎng)，數(shù)據(jù)庫技術(shù)與三維模型建模技術(shù)相結(jié)合顯然更加節(jié)約成本。如今，人們的問題已經(jīng)由“如何建造模型”轉(zhuǎn)換為“如何檢索所需要的現(xiàn)有模型"。要在一個(gè)大型數(shù)據(jù)庫中找到適合的多媒體信息，檢索是一種必要的技術(shù)手段。三維模型檢索的思想起源于三維模型識(shí)別，三維模型匹配以及基于內(nèi)容的模型檢索。在基于內(nèi)容的三維模型檢索領(lǐng)域，國(guó)外開展得比較早19971998年，加拿大國(guó)家研究院(National Research Council)的Paquet等最早對(duì)基于內(nèi)容的三維模型檢索技術(shù)進(jìn)行了理論和算法的研究H1。自1999年以后，美國(guó)，德國(guó)，日本等國(guó)的研究人員相繼投身于這個(gè)研

8、究，如美國(guó)的普林斯頓大學(xué)(Princeton University)、華盛頓大學(xué)(Washington University)、布朗大學(xué)(Brown University)、卡耐基·梅隆大學(xué)(Carbegie Mellon University)，德國(guó)的慕尼黑大學(xué)(Munich University)、波恩大學(xué)(Bonn University)，日本的IBM東京研究所，陸續(xù)提出了一些基于內(nèi)容的領(lǐng)域三維模型檢索系統(tǒng)，使三維模型檢索成為比較活躍的研究領(lǐng)域。但是，總的來說，目前對(duì)三維模型檢索同其他的多媒體數(shù)據(jù)檢索系統(tǒng)一樣，可以分為基于文本的檢索和基于內(nèi)容的檢索。大多數(shù)的商用多媒體檢索系統(tǒng)使

9、用基于文本的關(guān)鍵詞搜索來幫助用戶尋找想得到的多媒體文件信息。為了促進(jìn)搜索的準(zhǔn)確性，多媒體數(shù)據(jù)庫的管理人員需主要憑經(jīng)驗(yàn)給多媒體數(shù)據(jù)注釋易挑選的關(guān)鍵詞。如果數(shù)據(jù)庫非常龐大，則費(fèi)時(shí)費(fèi)力卻難以完成任務(wù)。此外，恰當(dāng)?shù)年P(guān)鍵詞因人而異。通常最普遍的方法是從文件名、標(biāo)題、上下文中提取關(guān)鍵詞(如WwWgo091ecom，wWWbaiducom檢索系統(tǒng))。然而，當(dāng)文件名不知所云(如abcdbmp，ni0001avi)，或毫無特點(diǎn)(如backgroldwav)時(shí)，這種方法顯然無效，因此，開發(fā)基于多媒體數(shù)據(jù)內(nèi)容自動(dòng)而有效的檢索系統(tǒng)已經(jīng)成為一個(gè)重要的需求?；谛螤畹娜S模型檢索是指直接根據(jù)描述對(duì)象的形狀特征進(jìn)行檢索，它

10、能從數(shù)據(jù)庫中查找到具有指定特征或含有特定內(nèi)容的三維數(shù)據(jù)。面對(duì)日漸迫切的需要，已經(jīng)有一些網(wǎng)站提供對(duì)三維模型的檢索與下載服務(wù)，但由于主要應(yīng)用的是文本關(guān)鍵字檢索和目錄瀏覽等手段，難以對(duì)復(fù)雜的模型進(jìn)行充分描述，在這種情況下，對(duì)于三維模型進(jìn)行有效檢索方面的研究越來越受到人們的重視，很多研究機(jī)構(gòu)開始對(duì)基于內(nèi)容的三維模型檢索系統(tǒng)進(jìn)行研究，并取得了一定的進(jìn)展。目前已經(jīng)開發(fā)出一些實(shí)驗(yàn)性的三維模型檢索系統(tǒng)。13論文組成部分介紹在下面章節(jié)，在第二章對(duì)三維模型檢索技術(shù)的形成與發(fā)展做了概述。在第三章討論了目前較常用的一些三維模型特征提取技術(shù)。在第四章，介紹了提出的一種三維模型特征提取方法，此方法稱為基于二維投影的三維模

11、型檢索方法，并對(duì)實(shí)驗(yàn)結(jié)果做出了分析比較。第二章三維模型檢索技術(shù)概述21二維圖像檢索物體之間形狀相似性的比較，可以追溯到早期基于形狀的圖像檢索：提取圖像中感興趣物體的輪廓或區(qū)域，采用不同方法描述其形狀特征，將問題簡(jiǎn)化為形狀特征的比較。借助于計(jì)算機(jī)視覺技術(shù)，人們可以定義多種二維形狀表示方法和相似性度量。二維形狀表示大致分為三類：特征向量法、變換形狀方法與關(guān)系方法。具體選擇哪一種表示方法取決于應(yīng)用的要求，如目標(biāo)形狀的特征點(diǎn)，是否允許遮擋與形變的存在，噪聲強(qiáng)弱，以及索引難易程度等。上述形狀描述方法無法直接擴(kuò)展應(yīng)用在三維模型上，主要原因是他們要求為連續(xù)曲線(或平面上區(qū)域的邊界)存在標(biāo)準(zhǔn)參數(shù)化表示。對(duì)于任

12、意三維曲面，需要根據(jù)具體應(yīng)用，恢復(fù)成一致曲面或流形曲面，得到相應(yīng)曲面的參數(shù)，這樣才能采取擴(kuò)展的三維形狀描述。在重建過程中，需要引入人工干預(yù)，以消除模型二義性?；谛螤畹膱D像檢索系統(tǒng)用多維特征空間距離來衡量形狀相似性。在特征維數(shù)不是很高的前提下，用索引結(jié)構(gòu)組織特征向量，將加速數(shù)據(jù)庫的訪問。但是，由于人類的感知相似性并不等價(jià)于物體的拓?fù)湎嗨菩?，單一特征無法完整描述物體的形狀。因而需要提取多種形狀特征，給出盡可能詳盡的表示。為了滿足創(chuàng)建索引結(jié)構(gòu)的要求，需要將多特征進(jìn)行降維處理。22三維模型檢索如何在浩如煙海的三維模型數(shù)據(jù)庫和網(wǎng)格中快速有效的搜索有用的、同主題的模型，構(gòu)成了三維模型檢索的主要目標(biāo)。與二

13、維圖像相比，三維模型有其獨(dú)特的性質(zhì)。首先，三維模型空間中一個(gè)簡(jiǎn)單的物體，即可以用多邊形面片、也可以用點(diǎn)、線和體素，還可以由基元物體的幾何操作和布爾操作表示。任意的三維曲面不存在類似二維空間上弧長(zhǎng)公式的直接參數(shù)化方法，因此無法對(duì)物體空間定義規(guī)則的、標(biāo)準(zhǔn)的類似二維圖像的采樣方式。這種內(nèi)在的不規(guī)則采樣和三維表面存在任意的拓?fù)潢P(guān)系，使得經(jīng)典的信號(hào)處理技術(shù)，無法直接擴(kuò)展應(yīng)用到三維。其次，空間維數(shù)大小直接影響模型特征對(duì)應(yīng)、參數(shù)匹配，分類其構(gòu)造，優(yōu)化路徑搜索等問題，其復(fù)雜度與處理時(shí)間隨之顯著增加?？赡艿哪Ｐ屯嘶F(xiàn)象使得常用的幾何形狀特征，如面積、體積、曲率等難以計(jì)算。另一方面，三維模型檢索與相機(jī)配置、光源設(shè)

14、置和場(chǎng)景語義無關(guān)，且不包含反射、陰影、遮擋、透射等效果，不需要考慮環(huán)境光照條件、相機(jī)參數(shù)、鏡頭校準(zhǔn)、自遮擋等現(xiàn)象，極大地簡(jiǎn)化了匹配相似物體的過程，或因?yàn)橥队暗降孛孀優(yōu)閮蓚€(gè)人，或者由于周圍場(chǎng)景的迷惑性而憑空消失。綜上所述，三維模型特征的選取，需要考慮以下三個(gè)方面：第一，特征要能夠反映物體的內(nèi)在基本特性。第二，三維模型在空間中的位置、朝向和大小是任意的，因此，所提取的特征應(yīng)該與模型的平移、旋轉(zhuǎn)、放縮等剛體變換無關(guān)。第三，即便對(duì)于退化的三維模型，特征也必須是確定的。221三維模型檢索系統(tǒng)基于內(nèi)容的三維模型目前對(duì)模型匹配的研究主要集中在對(duì)三維模型的空間幾何形狀的相似性度量，有少數(shù)關(guān)于拓?fù)湎嗨菩云ヅ涞难?/p>

15、究，基于紋理或材質(zhì)等屬性的相似性研究國(guó)內(nèi)外尚比較少見?；趦?nèi)容的三維模型檢索主要分為兩部分：一是離線處理，二是在線處理，如圖21所示。離線部分主要是對(duì)三維模型數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行特征提取，建立特征描述符和相應(yīng)的特征數(shù)據(jù)庫，并建立合適的索引結(jié)構(gòu)。在線部分主要是用戶在線提交查詢意圖并進(jìn)行特征提取、相似性度量和索引、查詢結(jié)果可視化等。圖21基于內(nèi)容的三維模型檢索系統(tǒng)框架以下對(duì)三維模型檢索系統(tǒng)中涉及到的幾個(gè)關(guān)鍵技術(shù)作簡(jiǎn)單的介紹：三維模型檢索首先從模型數(shù)據(jù)中自動(dòng)計(jì)算并提取三維模型的特征，如形狀空間關(guān)系、材質(zhì)的顏色及紋理等，建立三維模型的多維信息索引，然后在多維特征空間中計(jì)算待查詢模型與目標(biāo)模型之間的相似程

16、度，實(shí)現(xiàn)對(duì)三維模型數(shù)據(jù)庫的瀏覽和檢索畸，。三維模型檢索系統(tǒng)就是試圖利用反映三維模型視覺特征的內(nèi)容信息自動(dòng)建立特征索引，達(dá)到檢索三維模型的目的。三維模型檢索技術(shù)通過對(duì)視覺特征的相似性匹配來查找用戶所要求的三維模型，這更貼近于人們?cè)诂F(xiàn)實(shí)生活中靠直覺印象使用信息的方式。因此，一個(gè)完整的模型檢索系統(tǒng)包括如下幾個(gè)方面：(1)三維模型的特征提取由于絕大多數(shù)的三維模型是用于可視化，因此表達(dá)三維模型的文件中往往只包含模型的幾何屬性(頂點(diǎn)坐標(biāo)、法向矢量、拓?fù)溥B接等)和外觀屬性(頂點(diǎn)顏色、紋理等)，很少有適合自動(dòng)匹配的高級(jí)語義特征的描述。如何合理地描述三維模型(即特征提取)成為三維模型檢索課題首先要解決的問題，它

17、也是三維模型檢索的難點(diǎn)。一個(gè)理想的特征描述符必須滿足以下幾點(diǎn)：易于表達(dá)和計(jì)算；不占用太多的存儲(chǔ)空間；適合進(jìn)行相似性匹配；具有幾何不變性，即對(duì)模型的平移、旋轉(zhuǎn)、縮放等具有不變性；具有拓?fù)洳蛔冃裕聪嗤Ｐ陀卸鄠€(gè)拓?fù)浔硎緯r(shí)，特征描述符應(yīng)是穩(wěn)定；對(duì)模型的退化魯棒；對(duì)噪音不敏感；該特征必須具有唯一性，即不同類型的模型對(duì)應(yīng)的特征表示應(yīng)該不相同。(2)相似性度量檢索的目的是找出與所給模型相似的模型集合，因而對(duì)提取得到的特征如何進(jìn)行相似性匹配是檢索課題中要解決的第二個(gè)問題，選擇的度量方法必須適合匹配計(jì)算。當(dāng)前的研究中所采用的相似性匹配方法主要借鑒了基于內(nèi)容檢索的一些相似距離度量。(3)模型分類由于三維模型資

18、源龐大，因此需要建立一個(gè)分類數(shù)據(jù)庫以便提高模型查找效率，該分類數(shù)據(jù)庫必須適合用高級(jí)語義描述。當(dāng)然，對(duì)這個(gè)問題與相似性度量方法的研究有交叉的地方。(4)搜索方法的研究盡管有了分類作基礎(chǔ)，在三維模型檢索系統(tǒng)中，模型的檢索轉(zhuǎn)化成了對(duì)高維特征矢量數(shù)據(jù)庫的檢索問題，因此，特征數(shù)據(jù)庫中索引結(jié)構(gòu)的設(shè)計(jì)對(duì)提高檢索效率非常重要，好的索引機(jī)制可以幫助檢索系統(tǒng)在時(shí)間和存儲(chǔ)空間上同時(shí)得到提高。面對(duì)仍然龐大的數(shù)據(jù)庫，如何快速、有效地查找出相似的模型，在人工智能和數(shù)據(jù)庫領(lǐng)域中仍然是一個(gè)值得探討的問題。(5)查詢接口的設(shè)計(jì)。作為一個(gè)成熟的檢索系統(tǒng)，應(yīng)該擁有良好的交互性能，提供給用戶方便的查詢手段。通常，查詢輸入可以通過文本

19、與模型相結(jié)合的方法進(jìn)行。對(duì)于查詢模型的輸入主要有兩種途徑：將已知的模型作為查詢輸入，通知系統(tǒng)檢索出相似的模型，該方法的檢索結(jié)果比較理想，但是要求用戶必須預(yù)先擁有某種模型的范例，因此實(shí)際使用中不夠靈活，有一定的局限性：提供給用戶一個(gè)繪圖接口允許用戶繪制所需查詢模型的二維視圖，由系統(tǒng)根據(jù)視圖自動(dòng)生成三維模型。對(duì)于普通用戶而言，準(zhǔn)確地繪制一個(gè)拓?fù)鋸?fù)雜、有洞或有許多分支的模型是比較困難的。實(shí)驗(yàn)表明，目前該系統(tǒng)在這方面的性能不是非常理想。顯然，查詢接口的設(shè)計(jì)也直接影響了系統(tǒng)的檢索性能，因此設(shè)計(jì)一個(gè)理想的查詢接口在檢索系統(tǒng)中非常重要。(6)檢索性能的判斷對(duì)于三維模型的檢索性能的判斷，主要從查全、查準(zhǔn)、時(shí)間

20、、資源消費(fèi)等幾個(gè)方面來衡量。目前的研究主要是用查全率和查準(zhǔn)率兩個(gè)參數(shù)來對(duì)檢索性能進(jìn)行評(píng)判?？傊绾翁崛∧Ｐ偷奶卣魇侨S模型檢索首先需要解決的關(guān)鍵技術(shù)，也是目前研究比較多的一個(gè)方面。222三維模型預(yù)處理要真正實(shí)現(xiàn)基于內(nèi)容的三維模型檢索，非常關(guān)鍵的一點(diǎn)就是要求所提取的三維模型特征描述具有針對(duì)平移、旋轉(zhuǎn)、尺度大小以及方位變換的不變性和魯棒性。目前，實(shí)現(xiàn)特征描述不變性的方法主要有三種(1)使用主成分分析印方法對(duì)三維模型坐標(biāo)進(jìn)行標(biāo)準(zhǔn)化，計(jì)算其標(biāo)準(zhǔn)化的坐標(biāo)框架然后，在此標(biāo)準(zhǔn)化坐標(biāo)系內(nèi)提取相應(yīng)的特征：(2)將所有待比較的三維模型兩兩之間進(jìn)行坐標(biāo)對(duì)齊。這種方法由于極為費(fèi)時(shí)而很少被采用；(3)定義并提取本身具

21、有不變特性的特征描述。但實(shí)際上，這些特征描述所具有的不變性往往是不全面的，例如，Suzuki等人提出的形狀特征只對(duì)繞坐標(biāo)軸90度的變換保持不變性¨01。提出的反射對(duì)稱特征描述只具有平移和尺度不變性1。而且，大多數(shù)這類特征的計(jì)算有時(shí)也需要在一個(gè)歸一化的坐標(biāo)系內(nèi)完成。因此，為了進(jìn)一步提高檢索的準(zhǔn)確性，往往也需要進(jìn)行模型坐標(biāo)標(biāo)準(zhǔn)化。223三維模型特征提取3D模型檢索技術(shù)的關(guān)鍵是提取特征，在提取特征時(shí)有如下一些基本要求：(1)平移不變?cè)谄揭谱儞Q前后，3D模型的特征要保證不變；(2)旋轉(zhuǎn)不變?cè)谛D(zhuǎn)變換前后，3D模型的特征要保證不變；(3)縮放不變?cè)诳s放變換前后，3D模型的特征要保證不變；(4)

22、對(duì)噪聲具有魯棒性(噪聲包括模型裂縫、插入三角面片、移去三角面片等)。在有噪聲的情況下，3D模型的特征要保證相似；(5)對(duì)重采樣和簡(jiǎn)化具有魯棒性，在重采樣和簡(jiǎn)化變換前后，3D模型的特征要保證相似。從計(jì)算機(jī)圖形學(xué)發(fā)展的初期開始，多邊形網(wǎng)格就是通用的三維模型的表示方法。盡管后來出現(xiàn)了更多的描述方法，但由于多邊形具有形狀簡(jiǎn)單、便于計(jì)算和處理等特點(diǎn)，使得三維模型檢索的研究者們更多以多邊形網(wǎng)格模型作為研究對(duì)象。目前，三維模型特征提取方法主要分為三大類：基于外形的低層方法；基于結(jié)構(gòu)的高層方法；基于視角的方法。在下章中，將詳細(xì)討論特征提取方面的研究。224相似性度量模式識(shí)別、分類、聚類、檢索等常常被應(yīng)用在計(jì)算

23、機(jī)視覺、機(jī)械工程、分子生物學(xué)等領(lǐng)域，特征提取和相似性度量是完成這些任務(wù)的關(guān)鍵技術(shù)保證。如前所述，好的特征提取方法可以保證得到精確的形狀描述符，它是模型檢索的關(guān)鍵前提，相似性度量則是使得精確的形狀描述得到正確應(yīng)用的進(jìn)一步保證。相似性度量的任務(wù)就是在多維特征空間中，計(jì)算用戶的三維模型查詢請(qǐng)求與三維模型庫中的模型之問的相似性距離，距離越小，說明兩個(gè)模型的相似性程度越高，反之，距離越大，說明匹配或度量的兩個(gè)模型之間的相似程度越小，最終系統(tǒng)根據(jù)相似性度量的距離大小返回查詢結(jié)果，從而實(shí)現(xiàn)基于內(nèi)容的模型檢索，或者通過構(gòu)建特定的分類器，得出模型之間的相似程度。因此，選擇合適的相似性度量方法是對(duì)進(jìn)行精確匹配的進(jìn)

24、一步保證。相對(duì)于三維檢索形狀算子的研究而言，相似度比較方法在圖像檢索領(lǐng)域已有了比較成熟的研究。在基于內(nèi)容的三維模型檢索系統(tǒng)中，針對(duì)不同形式的特征空間，有時(shí)需要采用不同的適合的度量函數(shù)。目前在基于內(nèi)容的三維模型檢索中，主要借鑒了基于內(nèi)容的二維圖像檢索中所采用的一些距離度量算法，以下作一個(gè)簡(jiǎn)單的介紹。設(shè)U為特征空間，z，少為特征向量，并且有zU，yU度量函數(shù)為(x，力，理想的度量函數(shù)必須易于計(jì)算，符合人類的形狀感知，并滿足以下特征：正定性(possessiveness)Vx，yU，d(x，y)0·對(duì)稱性Vx，yU，d(x，y)=d(y，x)·自反性VxU，d(x，x)=0

25、83;嚴(yán)格的正定Vx，yU，xy=>d(x，y)>0·三角不等式Vx，y，zU，d(x，y)a·d(x，z)+b·d(z，y)+c常用于三維模型檢索領(lǐng)域的主要有Euclidean距離、Manhattan距離、馬氏距離以及Hausdorff距離等。設(shè)三維模型的特征空間為U=Rn，任意兩個(gè)三維模型的特征向量X，Y，分別表示為：X=x1，x2，xn，Y =y1，y2，yn，上述常用的經(jīng)典的距離公式分別為：(1)歐幾里德距離該距離適用于任何維數(shù)的特征空間，而且計(jì)算簡(jiǎn)單，在很多文獻(xiàn)中都被使用。但是這個(gè)距離的計(jì)算有一個(gè)前提，它假設(shè)了在同一特征空間的兩個(gè)特征分量xi

26、，xj彼此是獨(dú)立的，這就可能導(dǎo)致錯(cuò)誤的或者不夠準(zhǔn)確的匹配。為了彌補(bǔ)傳統(tǒng)的歐幾里德距離的缺陷，Ankerst提出了一種經(jīng)過改進(jìn)的度量方法，用一個(gè)相似矩陣A表示特征空間各個(gè)分量的相關(guān)性，如下述公式所示： (2)Manhattan距離(3)Hausdorff距離Hausdorff距離通常用來比較不同大小的兩個(gè)點(diǎn)集之間的相似性，其定義為：其中，表示兩個(gè)特征點(diǎn)集中任意兩點(diǎn)之間的距離，如Euclidean距離等，max()為取最大值函數(shù)，min()為取最小值函數(shù)。(4)馬氏距離(Mahalanobis Distance)馬氏距離首先根據(jù)已有的特征向量集合估計(jì)出協(xié)方差矩陣，然后定義如下的對(duì)稱距離：其中，A是

27、根據(jù)已有的特征矢量集估計(jì)出來的N×N的相似矩陣。225相關(guān)反饋相關(guān)反饋是檢索研究中的熱點(diǎn)之一。由于沒有一種形狀特征能夠完整地描述模型的特性，也沒有一種相似度量可以很好地模擬人的視覺感知，已有的分類器只能在給定樣本的情況下給出最佳分類結(jié)果,因此，如何讓系統(tǒng)在各種檢索條件下都能夠給出較好的結(jié)果，是一般的檢索系統(tǒng)需要考慮的問題。相關(guān)反饋利用機(jī)器學(xué)習(xí)理論，在系統(tǒng)與用戶的交互過程中，主動(dòng)學(xué)習(xí)用戶的判斷，使系統(tǒng)逐步走向穩(wěn)定與準(zhǔn)確。Chen等人用主動(dòng)學(xué)習(xí)(Active Learning)與隱藏標(biāo)注(Hidden Annotations)相結(jié)合的技術(shù)，由用戶對(duì)系統(tǒng)選擇的具有最大知識(shí)獲取的模型進(jìn)行標(biāo)注

28、。經(jīng)過一段時(shí)間的學(xué)習(xí)，系統(tǒng)展現(xiàn)了良好的可擴(kuò)展性。文獻(xiàn)(18)礎(chǔ)允許用戶對(duì)檢索結(jié)果做出評(píng)價(jià)，用類似支持向量的思想，將問題歸結(jié)為一個(gè)具有線性約束的最小二次優(yōu)化，縮短用戶指定為相關(guān)的模型之間的距離，同時(shí)增加不相關(guān)模型的空間距離。與相似度比較類似，相關(guān)反饋也不是三維模型檢索領(lǐng)域所獨(dú)有的。在圖像檢索中，它被用于縮小高層語義與底層特征之間的差異，以及彌補(bǔ)人類視覺感知的主觀性。（備注19）226界面設(shè)計(jì)由于三維模型中所包含的內(nèi)容信息比圖像等二維媒體更加豐富，因此，基于內(nèi)容的三維模型檢索系統(tǒng)一般具有多種檢索方式（備注20），主要有：(1)直接提供三維模型實(shí)例作為檢索請(qǐng)求，該模型可以是用戶上載至檢索服務(wù)器的新模

29、型文件，也可以是某次檢索結(jié)果集中的任一幅三維模型使用文件上載方式時(shí)，用戶只需直接提交三維模型的文件名或URL地址：而使用服務(wù)器上的三維模型實(shí)例檢索時(shí)，用戶可以通過縮略圖瀏覽的方式在界面上交互選取。(2)使用用戶交互繪制的二維形狀草圖，如Min等人設(shè)計(jì)了一個(gè)基于用戶交互的二維草圖繪制界面，由用戶繪制n個(gè)不同角度的二維草圖作為查詢請(qǐng)求在檢索時(shí)則使用三維模型在不同視角下的二維投影分別進(jìn)行相似性匹配。(3)使用用戶交互繪制的三維草圖，如Igarashi等人設(shè)計(jì)的三維草圖繪制工具Teddy（備注21）。但相對(duì)于二維草圖繪制而言，三維草圖的繪制難度較大，限制較多，而且只能繪制相對(duì)簡(jiǎn)單的三維模型。(4)基于

30、文本關(guān)鍵字的檢索界面。其中，文本關(guān)鍵字可分為兩類：一類是不具有語義屬性的文本，如模型文件名稱等附加信息：另一類是語義關(guān)鍵字，可以通過直接輸入語義文本或者目錄瀏覽的方式提交檢索請(qǐng)求。此外，檢索界面還負(fù)責(zé)將檢索結(jié)果以可視化的方式顯示給用戶，以進(jìn)行瀏覽或下一步的檢索過程。一些三維檢索系統(tǒng)中還引入了用戶相關(guān)反饋的機(jī)制，為用戶提供一個(gè)交互式的評(píng)價(jià)界面，作為引入用戶主觀評(píng)價(jià)的手段，以提高檢索精度，并實(shí)現(xiàn)個(gè)性化的、結(jié)合用戶主觀性認(rèn)知的檢索。如Elad等人（備注18）提出基于學(xué)習(xí)的檢索機(jī)制以自動(dòng)適應(yīng)不同用戶的檢索要求和偏好，在檢索結(jié)果顯示時(shí)提供了一個(gè)標(biāo)記“相關(guān)"和“不相關(guān)”，兩種評(píng)價(jià)的用戶反饋界面。

31、而Zhang等人（備注22）。則進(jìn)一步對(duì)用戶評(píng)價(jià)界面加以細(xì)化，提供了調(diào)節(jié)“相關(guān)"和“不相關(guān)”程度的反饋界面。227已有系統(tǒng)在基于內(nèi)容的三維模型檢索領(lǐng)域，目前己經(jīng)實(shí)現(xiàn)并發(fā)布了一些進(jìn)行理論和算法研究的原型系統(tǒng)以及架構(gòu)于web平臺(tái)上的搜索引擎等。其中，加拿大國(guó)家研究院的Paquet等人開發(fā)的三維模型檢索系統(tǒng)Nefertiti是第一個(gè)通用的三維模型檢索系統(tǒng)，所提取的特征主要包括形狀和顏色兩種。目前，比較典型的通用三維模型檢索系統(tǒng)和搜索引擎主要有：(1)美國(guó)普林斯頓大學(xué)形狀檢索與分析實(shí)驗(yàn)室開發(fā)的三維模型搜索引擎，提供了二維草圖和三維草圖的繪制界面，并具有規(guī)模最大的三維模型數(shù)據(jù)庫，其中包括310

32、00個(gè)通用的三維模型以及多個(gè)專業(yè)的三維模型子庫。(如圖22所示)http：shapecsprincetonedusearchhtml圖22普林斯頓大學(xué)的三維模型系統(tǒng)(2)美國(guó)卡耐基·梅隆大學(xué)AMP(Advanced Multimedia Processing)實(shí)驗(yàn)室開發(fā)的三維模型檢索系統(tǒng)，同時(shí)結(jié)合了底層形狀特征和語義特征進(jìn)行檢索，并提供了用戶相關(guān)反饋的功能。http：ampececmueduprojects3DmodelRetrieval(3)德國(guó)萊比錫大學(xué)CGIP(Computer Graphics and Image Processing)實(shí)驗(yàn)室的Saupe和Vranic等人開發(fā)

33、的基于VRML模型庫的在線三維模型檢索系統(tǒng)CCCC(Content based C1assification of 3D models by Capturing spatial Characteristics)，允許用戶任意選擇三維坐標(biāo)軸X，Y或Z進(jìn)行模型坐標(biāo)的標(biāo)準(zhǔn)化，這樣能使檢索結(jié)果更符合用戶的要求。該系統(tǒng)基于Web平臺(tái)設(shè)計(jì)，用戶界面友好。(如圖23所示)httD：merkur01infunikonstanzdeCCCC圖23萊比錫大學(xué)的三維模型檢索系統(tǒng)(4)IBM日本東京研究院的“三維web環(huán)境"研究項(xiàng)目中的三維幾何形狀檢索和分析系統(tǒng)，該系統(tǒng)的開發(fā)目的是對(duì)三維模型庫進(jìn)行知識(shí)管理。

34、http：wwwtrlibmcomprojects3dwebSimSearchehtm(5)希臘ITI學(xué)院信息處理實(shí)驗(yàn)室開發(fā)的基于VRML模型數(shù)據(jù)庫的三維模型檢索系統(tǒng)，除了可以在三維模型庫中進(jìn)行檢索外，還提供了對(duì)三維模型進(jìn)行兩兩比較的用戶界面和功能。http：3dsearchitigrdefaultphp?page=3dsearch(6)荷蘭Utrecht大學(xué)的GIVE(Geometry Imagined Virtual Environment)實(shí)驗(yàn)室研制開發(fā)的三維形狀搜索引擎，主要基于高斯曲率等形狀特征實(shí)現(xiàn)基于模型形狀的檢索。http：wwwcsuunlcentersgiveimaging3

35、Drecog3Dmatchinghtml(7)日本多媒體教育學(xué)院的Suzuki等人開發(fā)的基于web的多邊形模型檢索系統(tǒng)ogden IV，該系統(tǒng)同時(shí)使用模型的形狀和顏色特征對(duì)VRML模型數(shù)據(jù)庫實(shí)現(xiàn)檢索，以建立三維的網(wǎng)絡(luò)教學(xué)環(huán)境。http：wwwnimeacjpmotofumiOgden(8)美國(guó)布朗大學(xué)的LEMS(Laboratory for Engineering ManMachine System)實(shí)驗(yàn)室開發(fā)的三維模型檢索系統(tǒng)，以二維圖像為輸入方式，在三維模型庫中檢索出相似的三維物體模型。http：www1emsbrowneduvisionresearchAreas3DRecogovervi

36、ewhtml(9)德國(guó)波恩大學(xué)Klein和Novotni等人開發(fā)的數(shù)字圖書館系統(tǒng)RoDA，該系統(tǒng)不對(duì)模型進(jìn)行特征提取，而是通過計(jì)算不同模型之間的體積測(cè)定誤差(V01umetric Error)以及補(bǔ)償輪廓(Offset Hull)進(jìn)行檢索。http：www1emsbrowneduvisionresearchAreas3DRecogoverviewhtml(10)臺(tái)灣大學(xué)通訊與多媒體實(shí)驗(yàn)室研制的三維模型檢索系統(tǒng)，該系統(tǒng)使用MPEG一7標(biāo)準(zhǔn)的三維形狀描述符和多視圖描述符對(duì)模型特征進(jìn)行描述，基于web平臺(tái)進(jìn)行三維模型檢索。(如圖24所示)http：3dcsientuedutwdynamic此外，還有

37、一些用于專業(yè)領(lǐng)域的檢索系統(tǒng)。如德國(guó)慕尼黑大學(xué)Ankerst等人研制的三維蛋白質(zhì)分子模型檢索系統(tǒng)http：wwwdbsinformatikunimuenchendeForschungSimilarityDemosprotein以及蘇格蘭Heriotwatt大學(xué)開發(fā)的于web的CAD模型搜索引擎ShapeSifter等。http：wwwshapesearchnetecmindexhtml圖24中國(guó)臺(tái)灣大學(xué)的三維模型檢索系統(tǒng)23本章小結(jié)三維模型檢索被廣泛應(yīng)用于數(shù)字化圖書館、數(shù)字機(jī)和處理、分子生物學(xué)、機(jī)械工程、醫(yī)學(xué)圖像和圖形編輯等各個(gè)領(lǐng)域，以構(gòu)建面向三維模型的專業(yè)化搜索引擎為目標(biāo)，有三維模型的獲取、特

38、征分析、查詢處理和匹配以及用戶界面四個(gè)部分組成。由于種種原因，這個(gè)領(lǐng)域直到近兩年才引起足夠的重視，并得到了飛速發(fā)展。本章就是對(duì)三維模型檢索研究領(lǐng)域的歷史和現(xiàn)狀作一個(gè)的概述。通過概述，指出了目前存在的主要問題以及進(jìn)一步研究的重點(diǎn)和必要性。在模型數(shù)據(jù)庫中，強(qiáng)壯的模型特征表達(dá)和識(shí)別是最根本的問題，此外，我們還需要很好的相似性距離度量方法，接下來的章節(jié)就是對(duì)這兩個(gè)問題進(jìn)行深入的研究。第三章三維模型特征提取的研究31三維模型預(yù)處理311模型規(guī)范化處理對(duì)三維模型規(guī)范化的目的是使所有的模型滿足(1)平移不變性：(2)旋轉(zhuǎn)不變性：(3)縮放不變性。也就是對(duì)于任何三維模型不管進(jìn)行了什么樣的平移變換，旋轉(zhuǎn)變換，縮

39、放變換，只要對(duì)其進(jìn)行規(guī)范化預(yù)處理后，那么最終的大小，原點(diǎn)坐標(biāo)，方向都一樣，因此不影響特征的提取。本文使用了主成分分析法PCA(Principle Component Analysis)對(duì)三維模型進(jìn)行規(guī)范化處理。(1)平移不變?yōu)榱吮ＷC平移不變，首先求出三維模型的重心，將三維模型的重心作為三維模型的新坐標(biāo)原點(diǎn)，將三維模型平移到新的坐標(biāo)原點(diǎn)。計(jì)算三維模型重心的公式如下。這里w為三角形的面積，P為點(diǎn)的集合，求出c是三維模型的重心，將三維模型的坐標(biāo)原點(diǎn)移動(dòng)到c點(diǎn)，形成的點(diǎn)集合如下。 (2)旋轉(zhuǎn)不變?yōu)榱吮ＷC旋轉(zhuǎn)不變性，首先使用公式計(jì)算三維模型的相關(guān)矩陣M，M是個(gè)3木3的矩陣。矩陣M是實(shí)對(duì)稱矩陣，因此特征根

40、是3個(gè)不同的正實(shí)數(shù)。求出特征根，以降序排列3個(gè)特征根。然后求出3個(gè)特征根對(duì)應(yīng)的特征向量，將每個(gè)特征向量變?yōu)閱挝幌蛄?，最?個(gè)特征向量組成旋轉(zhuǎn)矩陣R，R同樣是3牢3的矩陣。使用旋轉(zhuǎn)矩陣R變換三維模型，計(jì)算出新的點(diǎn)集 (3)縮放變換為了統(tǒng)一三維模型的大小，保證縮放不變，需要計(jì)算大小變換因子來變換三維模型。其中，最后得到了平移變換響亮c、旋轉(zhuǎn)變換矩陣R、大小變換因子s。將這些變換應(yīng)用到原三維模型的頂點(diǎn)集合P完成規(guī)范化預(yù)處理。312三維模型的存儲(chǔ)方法(1)三維文件格式介紹A3DS數(shù)據(jù)結(jié)構(gòu)：3DS文件由許多塊組成，每個(gè)塊首先描述其信息類別，即塊是如何組成的。塊的信息類別用D來標(biāo)識(shí)，塊還包含了下一塊的相對(duì)

41、位置信息。3DS二進(jìn)制文件中的數(shù)據(jù)是按低位在前、高位在后的方式組織的。如，4A 5C組成的整型數(shù)，表明5C是高位字節(jié)，4A是低位字節(jié)：對(duì)于長(zhǎng)整型數(shù)。如：4A 5C 3B 8F表明5C 4A是高位字節(jié)，3B 8F是低位字節(jié)。下面描述塊的具體定義。塊的前面兩項(xiàng)信息分別是：塊的ID和塊的長(zhǎng)度(也即下一塊相對(duì)于該塊的字節(jié)偏移量)，塊的ID是一個(gè)整型數(shù)，而塊的長(zhǎng)度是一個(gè)長(zhǎng)整型數(shù)。每個(gè)塊實(shí)際上是一個(gè)層次結(jié)構(gòu)，不同類型的塊，其層次結(jié)構(gòu)也不相同。3DS文件有一個(gè)基本塊，其ID是4D4D，每一個(gè)3DS文件開頭都是有這樣一個(gè)塊構(gòu)成的。BCTS和TD0文件格式CTS和TDO都是我所特有的三維模型文件格式。這些數(shù)據(jù)是

42、有二維CT圖像經(jīng)過三維重構(gòu)而來的，之所以要對(duì)這些格式支持，是因?yàn)槿S檢索在醫(yī)學(xué)上有很大的應(yīng)用前景。TDO數(shù)據(jù)結(jié)構(gòu)：關(guān)于：IcTDO文件讀寫的信息。文件后綴TDO的是”ThreeDimensional 0bject”的簡(jiǎn)寫形式。Struct tagTDOFILEHEADER文件標(biāo)志字符串，必須是，”3D0bject”，不區(qū)分大小寫。Char m _chSymbol 9：文件版本號(hào)，當(dāng)前為1。除非對(duì)文件格式有較大修改，否則必須為1。UINTm_nVersion：文件頭的大小，以字節(jié)(Byte)為單位。UINT m_nFi1eHeaderSize：本數(shù)據(jù)文件的狀態(tài)：0=原始：1=己進(jìn)行法蘭克福校正；

43、2=己進(jìn)行分區(qū)切分。BYTE m_nState；點(diǎn)數(shù)據(jù)層數(shù)：一1=非分層數(shù)據(jù)(例如從DXF文件轉(zhuǎn)換的數(shù)據(jù))，在文件頭后有數(shù)據(jù)點(diǎn)序列；(>=0)=分層數(shù)據(jù)的層數(shù)，在文件頭后有若干層數(shù)據(jù)點(diǎn)序列。Int m_nPointLayerNum；三角形數(shù)據(jù)層數(shù)：一1=非分層數(shù)據(jù)(例如從DXF文件轉(zhuǎn)換的數(shù)據(jù))，在數(shù)據(jù)點(diǎn)序列后有三角形數(shù)據(jù)；(>=O)=分層數(shù)據(jù)的層數(shù)，在數(shù)據(jù)點(diǎn)序列后有若干層三角形數(shù)據(jù)。一般情況下，對(duì)于分層數(shù)據(jù)應(yīng)有m_nTriangleLayerNum=(m nPointLayerNum-1)的關(guān)系。Int m_nTriangleLayerNum：此數(shù)據(jù)的最大最小坐標(biāo)：double0=

44、x；double1=y；double2=z。Double m_szMax 3：Double m_szMin 3：保留字。Int m_nReVersedl：Int m_nReversed2：doublem_dReVersedl：doublem_dReVersed2：；CTS數(shù)據(jù)CTS存儲(chǔ)的是由空間點(diǎn)組成的等值線據(jù)。文件由兩部分組成：第一部分是文件頭信息：Struct CTSFILEHEADERUINT nLayerTotal 內(nèi)層和外層層數(shù)的最大值UINT nDataHeight 圖象的數(shù)據(jù)高度UINT nDataWidth 圖象的數(shù)據(jù)寬度double fFactorX 數(shù)據(jù)在X方向上的比例因子

45、double fFactorY 數(shù)據(jù)在Y方向上的比例因子double fFactorZ 數(shù)據(jù)在Z方向上的比例因子第二部分是文件的數(shù)據(jù)信息其內(nèi)容如下：層號(hào)第n層顱骨等值線個(gè)數(shù)，(INT型)第m條內(nèi)等值線點(diǎn)數(shù)，(INT型)空間點(diǎn)數(shù)據(jù)(X，Y，Z)(double型)第n層皮膚等值線個(gè)數(shù)，第m條內(nèi)等值線點(diǎn)數(shù)，(UINT型)空間點(diǎn)數(shù)據(jù)(X，Y，Z)(double型)(2)多文件格式的統(tǒng)一存儲(chǔ)由于要使不同格式的三維模型能夠進(jìn)行統(tǒng)一的檢索，所以我們?cè)谀Ｐ洼斎牒蠼y(tǒng)一使用C3Dobject類來對(duì)其進(jìn)行操作。此外，由于三維模型可能存在缺陷或噪音，而無法滿足算法特征提取的要求時(shí)，我們也是通過對(duì)C3D0bject類進(jìn)

46、行標(biāo)準(zhǔn)化來實(shí)現(xiàn)的。C3DObject類代表了三維物體模型。計(jì)算機(jī)圖形學(xué)中通常采用三角面片的網(wǎng)格來表示一個(gè)三維物體，所以該類中一個(gè)重要的數(shù)據(jù)就是三角面片的集合。在對(duì)三維模型的編輯過程中，對(duì)構(gòu)成模型的三角面片信息進(jìn)行遍歷和搜索是一個(gè)常用的操作。在給出模型表示的數(shù)據(jù)結(jié)構(gòu)之前，先給出和三角形面片組成的網(wǎng)格有關(guān)的幾個(gè)定義。點(diǎn)的索引：一個(gè)點(diǎn)的索引是指該點(diǎn)在頂點(diǎn)數(shù)組中的索引，它是一個(gè)整數(shù)。它唯一確定了一個(gè)空間點(diǎn)。點(diǎn)的相關(guān)三角形：如果該點(diǎn)為某個(gè)空間三角形的一個(gè)頂點(diǎn)，我們就說該三角形是該點(diǎn)的相關(guān)三角形。點(diǎn)的相關(guān)三角形表：是指和該點(diǎn)相關(guān)所有的三角形構(gòu)成的集合。點(diǎn)的度：是指和該點(diǎn)相關(guān)的三角形的個(gè)數(shù)。三角形的法向量：

47、空間三角形的法向量定義為從空間原點(diǎn)出發(fā)和該三角形所在平面垂直并指向該平面的單位向量。點(diǎn)的法向量：空間中一點(diǎn)的法向量定義為和該點(diǎn)相關(guān)的所有三角形的法向量的平均法向量。如圖32所示，在空間網(wǎng)格中，頂點(diǎn)A相關(guān)三角形有a，b，c，d，e，f它的度為6。頂點(diǎn)A的法向量就為三角形a，b，c，d，e，f六個(gè)三角形的法向量的平均法向量。圖32頂點(diǎn)和其相關(guān)的三角形示意圖從上面的例子可以看出來，在三角形網(wǎng)格中絕大多數(shù)頂點(diǎn)的度都是大于1的。如果每個(gè)三角形用其三個(gè)頂點(diǎn)來表示，每個(gè)頂點(diǎn)用三個(gè)坐標(biāo)來表示，那么上圖中A頂點(diǎn)的坐標(biāo)就要被重復(fù)保存6次。如果用這種方法來表示含有上萬個(gè)三角面片的空間網(wǎng)格，那么勢(shì)必需要大量的存儲(chǔ)空間

48、。顯然這種把空間一個(gè)點(diǎn)重復(fù)多次保存是完全沒有必要的。系統(tǒng)中采用索引的方式來表示三維空間網(wǎng)格模型。索引方法表示空間三角面片網(wǎng)格的思想如下：把所有構(gòu)成空間三角面片網(wǎng)格的頂點(diǎn)形成一個(gè)集合，并依次對(duì)所有頂點(diǎn)從0開始編號(hào)，依次類推。這樣網(wǎng)格上的每一個(gè)頂點(diǎn)都有一個(gè)唯一的編號(hào)，該編號(hào)也唯一確定了網(wǎng)格中的一個(gè)頂點(diǎn)，這個(gè)編號(hào)稱為索引號(hào)?？臻g三角面片的表示用構(gòu)成該三角形的三個(gè)頂點(diǎn)的編號(hào)來表示，即用三個(gè)整數(shù)來表示一個(gè)空間三角形，這三個(gè)整數(shù)為構(gòu)成該空間三角形三個(gè)頂點(diǎn)的索引號(hào)。每一個(gè)空間頂點(diǎn)的所有相關(guān)三角形構(gòu)成其相關(guān)三角形表，它和該頂點(diǎn)一一對(duì)應(yīng)。如圖33所示。圖33三維網(wǎng)格索引法表示示意圖采用索引的方式來表示空間網(wǎng)格不

49、僅可以節(jié)省大量存儲(chǔ)空間，而且對(duì)與模型的編輯和修改也帶來了很大的方便：這種存儲(chǔ)方式每個(gè)頂點(diǎn)只需要保存一次，當(dāng)用戶編輯該頂點(diǎn)的時(shí)候，如平移，那么只需要修改一次頂點(diǎn)信息，其索引值不變，所以和該頂點(diǎn)相關(guān)的三角形數(shù)據(jù)不發(fā)生任何變化，這也保持了數(shù)據(jù)的完整性。這種存儲(chǔ)方式對(duì)于查找給定頂點(diǎn)的所有相關(guān)三角形是很方便的。如果用戶刪除了某個(gè)頂點(diǎn)，則可以很方便的找到所有和該頂點(diǎn)相關(guān)的三角形，然后全部刪除這些相關(guān)的三角形，也便于計(jì)算各個(gè)頂點(diǎn)的法向量等。同時(shí)，在三維網(wǎng)格簡(jiǎn)化的時(shí)候，需要統(tǒng)計(jì)頂點(diǎn)的相關(guān)三角形，這種存儲(chǔ)方式也給三維網(wǎng)格簡(jiǎn)化帶來了便利。32三維模型特征提取技術(shù)的研究對(duì)一個(gè)三維模型進(jìn)行參數(shù)化是一個(gè)很復(fù)雜的問題，同

50、時(shí)由于三維表面有任意的拓?fù)?，使得一些在二維圖像被使用的方法(如傅里葉變換)無法直接應(yīng)用在三維領(lǐng)域。很多模型雖然滿足了視覺效果，但是大多數(shù)是退化的、不完整的。對(duì)這些模型進(jìn)行有意義的幾何特征和形狀信號(hào)的計(jì)算是很困難的，因此尋找出有意義的特征成了研究人員首先考慮的問題?？梢哉f，對(duì)于基于內(nèi)容的3D模型檢索系統(tǒng)，最根本的問題是選取恰當(dāng)?shù)奶卣鱽韰^(qū)別不同的形狀，以用來有效的索引相似的文件數(shù)據(jù)。（備注1）3D模型檢索方法可大致的分為3類：基于外形的低層方法；基于結(jié)構(gòu)的高層方法：基于視角的方法。321基于外形的方法基于外形的方法嘗試通過幾何和拓?fù)涞膶傩悦枋?D模型的形狀，外形可以是由單獨(dú)向量組成的一些外形參數(shù)的

51、固定數(shù)值或系列外形參數(shù)的分布范圍：基于結(jié)構(gòu)的高層方法嘗試把3D模型分解成一系列關(guān)鍵部分，并提煉出這些部分的幾何關(guān)系；基于視角的方法通過系列從不同角度的二維射影來得出三維模型的外觀。在3D模型表述系統(tǒng)中，基于外形的下層方法描述通常3D模型的幾何屬性，空間屬性，形狀分布范圍。兩個(gè)模型的相似處可通過比較外形來測(cè)量。Zhang和Chen例提出了通過網(wǎng)格描述，來有效計(jì)算面積、體積、對(duì)稱軸傅立葉變幻系數(shù)的方法。Paquet等人乜鍆使用對(duì)稱軸來描述三維物體的對(duì)稱性基于套鎖來描述形狀信心的細(xì)微細(xì)節(jié)，并用小波變換來描述不透明度分布。這種方法，需要擺好標(biāo)準(zhǔn)化的姿勢(shì)用于旋轉(zhuǎn)。三維傅立葉變換特征是利用傅立葉變換公式將

52、三維模型分解成不同的頻率表示，然后利用其中一些頻率系數(shù)形成的三維模型特征。首先對(duì)三維模型進(jìn)行規(guī)范化和體素化處理，然后對(duì)體素單元進(jìn)行離散的傅立葉變換。設(shè)V是三維模型的體素，進(jìn)行離散的傅立葉變換，把V變換到頻域空間，計(jì)算特征向量之間的絕對(duì)值距離和歐氏距離作為相似度，檢索時(shí)可以使用不同分辨率的特征向量檢索，即可以選擇三組特征向量中任何一組進(jìn)行檢索。vranic的測(cè)試表明，傅立葉變換檢索技術(shù)具有較好檢索效率，但是計(jì)算速度較慢。三維小波特征小波變換同樣也可以用于描述三維模型的特征，Paquet等人在檢索中使用了小波變換。文中使用了具有二階消失矩的DAU4小波。這種小波的變換矩陣w如公式所示，將W作用到模

53、型的三個(gè)軸向就得到小波系數(shù)。先對(duì)三維模型進(jìn)行PCA和體素化處理，然后再在三個(gè)軸向上進(jìn)行小波變換，得到小波系數(shù)。一種改進(jìn)的，不需要擺好姿勢(shì)的基于球形調(diào)和的形狀描述法被Funkhouser等人(備注28,27)提出。首先，3D模型通過與其相交的不同半徑的同心圓來分解成一系列圓形函數(shù)的聚集。每個(gè)圓形函數(shù)被分解為一系列不同頻率的諧波。在每個(gè)半徑圓上，每個(gè)頻率部分的范數(shù)和組成了形狀的表述。這種表述是旋轉(zhuǎn)常量，原因是，旋轉(zhuǎn)一個(gè)圓狀函數(shù)不改變每個(gè)頻率部分的能量。Novotni和Klein拉引對(duì)3D模型運(yùn)用查涅克矩。無疑，這是基于圓形諧波表述法的延伸。三維查涅克矩是一個(gè)通過半徑和頻率的二維直方圖索引。三維查涅

54、克矩的好處在于它旋轉(zhuǎn)常量并且對(duì)幾何的、拓?fù)涞耐鈦砦锊幻舾小Ｇ蛎嬲{(diào)和分析又稱單位球面上的二維傅立葉變換。它的正交基函數(shù)Z。(p，矽)(球面調(diào)和函數(shù))定義如下：其中是規(guī)一化常數(shù)。是度為l，次為m的聯(lián)合拉格朗日多項(xiàng)式球面調(diào)和函數(shù)源自球面上的拉普拉斯方程，它們構(gòu)成了球面上連續(xù)函數(shù)空間的一組完備單位正交基。所有度為，的球面調(diào)和函數(shù)組成球面上一個(gè)2L+1維大小的旋轉(zhuǎn)不變子空問，任意定義在球面上的連續(xù)信號(hào)在子空間上的投影與信號(hào)的旋轉(zhuǎn)操作無關(guān)。將三維模型與一系列同心球求交，其中球心與物體中心重合，球面調(diào)和分析便能夠直接應(yīng)用于在不同半徑下計(jì)算得到的球面函數(shù)網(wǎng)。但是，由于球面函數(shù)之間相互獨(dú)立，旋轉(zhuǎn)某些半徑分量下的

55、球面函數(shù)，并不影響計(jì)算結(jié)果，而此時(shí)，物體的外在形狀卻發(fā)生改變。(如圖34所示)圖34度為0，1，2，3的球面圖調(diào)和函數(shù)三維查涅克矩描述符則能夠很好地克服球面函數(shù)獨(dú)立性所帶來的問題。定義一組三維空間正交基函數(shù)，稱為三維ZerIlike函數(shù)：其中，是球面調(diào)和函數(shù)，是徑向函數(shù)，所有徑向下標(biāo)為n，度為l的Zemike函數(shù)張成三維空間上一個(gè)2l+1維大小的旋轉(zhuǎn)不變子空間。小波變換是傅立葉變換一個(gè)自然的擴(kuò)展，它具有良好的時(shí)間空間分辨率，適合層次化的表示與比較。將小波變換應(yīng)用到三維檢索中最主要的困難仍然在于三維模型的表示。當(dāng)然，高維小波的構(gòu)造本身便是一個(gè)難點(diǎn)，它們通常不具備一維小波那樣良好的性質(zhì)。在簡(jiǎn)單的應(yīng)

56、用中，可以選用光滑的、具有有限消失矩的一維小波，例如，DAU4小波與Haar小波等，分別沿三個(gè)坐標(biāo)軸進(jìn)行變換。Yu等人(備注29)表面穿透對(duì)應(yīng)圖，使得光線從球中心穿過表面的數(shù)值是可計(jì)算的。這種對(duì)應(yīng)圖的傅立葉變換已被用于檢索或相似性比較。Shih等人（備注36）提出一種新的，被稱為網(wǎng)格D2的表述法，來減輕上述問題。在GD2表述法中，3D模型首先分解為三維像素格，相比于隨機(jī)點(diǎn)，這種隨機(jī)采樣操作只在多邊形表面的像素格內(nèi)。這種輪廓范圍表述法（備注37）被用于3D模型檢索的MPEG7標(biāo)準(zhǔn)。SSD描述了三維表面的全部點(diǎn)曲率的直方圖。SSD的優(yōu)點(diǎn)是不用事先對(duì)準(zhǔn)三維物體就便可以比較兩個(gè)3D模型，并且對(duì)于成棋盤

57、形布置得三維多邊形模型，是很穩(wěn)定的。322基于結(jié)構(gòu)的特征提取方法：基于形狀的方法之考慮三維模型的幾何、拓?fù)鋵傩?。而高層基于結(jié)構(gòu)的方法，描述的是模型各部分問的關(guān)系。Hilaga等人（備注38）用多分解Reeb圖來描述三維模型的概略結(jié)構(gòu)。(如圖35所示) 圖35三維模型和對(duì)應(yīng)的Reeb圖精確地說，Reeb圖被定義為圖的商數(shù)空間和商數(shù)函數(shù)。Hilaga等人所用的Reeb圖是基于完整的測(cè)疑距離所定義的商函數(shù)，利用測(cè)地距離由i維物體的形狀計(jì)算出多分辨率Reeb圖，然后給出了拓?fù)鋱D相似度的定義，并依此進(jìn)行模型相似度的計(jì)算。多分辨率Reeb圖的基本思想是在物體細(xì)節(jié)的各個(gè)層次上建立一系列Reeb圖。為在某一層次上構(gòu)造Reeb圖，