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

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

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

3、提??；相似度計(jì)算第一章緒論1.1研究的背景及意義我們處在一個(gè)三維世界里，一切被我們感知的物體都以三維的形式存在，人類的視覺不僅能夠感知二維平面的信息，且具有立體三維的特性。與二維圖像相比，三維的模型所提供的視覺感知細(xì)節(jié)更多、更豐富，能夠給人們帶來更加詳細(xì)的信息。5PCzVD7HxA三維模型的研究成為了一個(gè)熱點(diǎn)話題，是因?yàn)椋?1隨著三維數(shù)據(jù)獲取，如數(shù)字?jǐn)z像機(jī)、掃描儀、核磁共振和3D激光掃描儀設(shè)備的功能越來越強(qiáng)，使用越來越方便，技術(shù)手段不斷進(jìn)步和成熟，使三維信息獲取和表達(dá)變得越來越容易；jLBHrnAlLg(2眾多三維建模軟件和工具(如3DMax,AutoCAD,Poser,Core3D等使得三維

4、模型的設(shè)計(jì)變得簡單；XHAQX74J0X(3三維模型建模的專業(yè)需求越來越強(qiáng)，分子工程、地貌氣象分析、工業(yè)產(chǎn)品設(shè)計(jì)、醫(yī)學(xué)建模、虛擬軍事行動等，都廣泛使用了三維技術(shù)。構(gòu)建數(shù)字化模型，可幫助科研人員更加直觀、精確地處理各自領(lǐng)域問題；LDAYtRyKfE(4在娛樂領(lǐng)域，游戲、電影產(chǎn)業(yè)的發(fā)展，使人們已經(jīng)不滿足于二維畫面，傳統(tǒng)的制作方法已經(jīng)成為歷史，精美絢麗的三維動畫隨處可見。而三維建模本身，也成為了一門藝術(shù)門派；Zzz6ZB2Ltk(5計(jì)算機(jī)圖形學(xué)技術(shù)發(fā)展迅速，三維圖形處理硬件和CPU的速度已足夠快，而且價(jià)格便宜，使得三維數(shù)據(jù)能在微機(jī)上快速處理和顯示；dvzfvkwMI1(6蓬勃發(fā)展的互聯(lián)網(wǎng)技術(shù)也使人們

5、對信息共享和處理的方式發(fā)生了根本性的改變，網(wǎng)絡(luò)已經(jīng)成為人們獲取信息的重要途徑?；ヂ?lián)網(wǎng)的普及，使三維模型被更廣泛地轉(zhuǎn)播和共享。rqyn14ZNXI(7各軟件，各版本的三維數(shù)據(jù)兼容化、共享化趨勢，加速了模型的標(biāo)準(zhǔn)化進(jìn)程。三維模型已成為繼聲音、圖像和視頻之后的第四種多媒體數(shù)據(jù)類型。目前有數(shù)以兆計(jì)的三維模型存在，而且每天都有大量的三維模型產(chǎn)生和傳播，可以預(yù)見，在不久的將來，人們可以像使用二維圖像一樣使用三維模型。EmxvxOtOco因此，為了從浩如煙海的信息中快速準(zhǔn)確地找到需要的內(nèi)容，人們存在著對三維模型進(jìn)行檢索的迫切需求。12三維模型檢索系統(tǒng)的發(fā)展作為新興的領(lǐng)域，三維檢索有重要的學(xué)術(shù)意義及應(yīng)用價(jià)值。

6、如，目前在我國，知識產(chǎn)權(quán)保護(hù)工作越來越受到重視，而知識產(chǎn)權(quán)保護(hù)的相關(guān)工作量也越來越大。在各種專利尤其是外觀設(shè)計(jì)的申請的核準(zhǔn)、審查和批復(fù)的過程中，都需要對各種三維模型進(jìn)行比較。SixE2yXPq5在工業(yè)設(shè)計(jì)過程中，三維數(shù)據(jù)可以完全提供產(chǎn)品的幾何信息，為了實(shí)現(xiàn)給料、加工、質(zhì)檢的自動化，需要反復(fù)快速地檢索、匹配標(biāo)準(zhǔn)零件模型庫，在一個(gè)大型數(shù)據(jù)庫中找到適合的三維模型。6ewMyirQFL數(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é)奧秘的重要

7、手段，從計(jì)算機(jī)圖形和視覺的角度來審視蛋白質(zhì)三維空間結(jié)構(gòu)的相似性檢索，有著廣闊的應(yīng)用前景?；ヂ?lián)網(wǎng)上也出現(xiàn)了大量的三維模型庫，許多網(wǎng)站也將三維模型作為一種數(shù)字化商品提供給使用者。相對于二維多媒體信息的獲取，三維模型的建模更加復(fù)雜。顯然，搜索、共享大量的三維模型數(shù)據(jù)；在現(xiàn)有的模型基礎(chǔ)上進(jìn)行分類、比較、改進(jìn)；把互聯(lián)網(wǎng)，數(shù)據(jù)庫技術(shù)與三維模型建模技術(shù)相結(jié)合顯然更加節(jié)約成本。kavU42VRUs如今，人們的問題已經(jīng)由“如何建造模型”轉(zhuǎn)換為“如何檢索所需要的現(xiàn)有模型”。要在一個(gè)大型數(shù)據(jù)庫中找到適合的多媒體信息，檢索是一種必要的技術(shù)手段。三維模型檢索的思想起源于三維模型識別，三維模型匹配以及基于內(nèi)容的模型檢索。

8、y6v3ALoS89在基于內(nèi)容的三維模型檢索領(lǐng)域，國外開展得比較早19971998年，加拿大國家研究院（NationalResearchCouncil的Paquet等最早對基于內(nèi)容的三維模型檢索技術(shù)進(jìn)行了理論和算法的研究H1。自1999年以后，美國，德國，日本等國的研究人員相繼投身于這個(gè)研究，如美國的普林斯頓大學(xué)（PrincetonUniversity、華盛頓大學(xué)（WashingtonUniversity、布朗大學(xué)（BrownUniversity、卡耐基梅隆大學(xué)（CarbegieMellonUniversity,德國的慕尼黑大學(xué)（MunichUniversity、波恩大學(xué)（BonnUniver

9、sity，日本的IBM東京研究所，陸續(xù)提出了一些基于內(nèi)容的領(lǐng)域三維模型檢索系統(tǒng)，使三維模型檢索成為比較活躍的研究領(lǐng)域。但是，總的來說，目前對三維模型檢索同其他的多媒體數(shù)據(jù)檢索系統(tǒng)一樣，可以分為基于文本的檢索和基于內(nèi)容的檢索。M2ub6vSTnP大多數(shù)的商用多媒體檢索系統(tǒng)使用基于文本的關(guān)鍵詞搜索來幫助用戶尋找想得到的多媒體文件信息。為了促進(jìn)搜索的準(zhǔn)確性，多媒體數(shù)據(jù)庫的管理人員需OYujCfmUCw主要憑經(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,wW

10、W.baiducom檢索系統(tǒng)。然而，當(dāng)文件名不知所云（如abed,bmp,ni0001avi，或毫無特點(diǎn)（如backgro川ld.wav時(shí)，這種方法顯然無效，因此，開發(fā)基于多媒體數(shù)據(jù)內(nèi)容自動而有效的檢索系統(tǒng)已經(jīng)成為一個(gè)重要的需求。eUts8ZQVRd基于形狀的三維模型檢索是指直接根據(jù)描述對象的形狀特征進(jìn)行檢索，它能從數(shù)據(jù)庫中查找到具有指定特征或含有特定內(nèi)容的三維數(shù)據(jù)。面對日漸迫切的需要，已經(jīng)有一些網(wǎng)站提供對三維模型的檢索與下載服務(wù)，但由于主要應(yīng)用的是文本關(guān)鍵字檢索和目錄瀏覽等手段，難以對復(fù)雜的模型進(jìn)行充分描述，在這種情況下，對于三維模型進(jìn)行有效檢索方面的研究越來越受到人們的重視，很多研究機(jī)構(gòu)開

11、始對基于內(nèi)容的三維模型檢索系統(tǒng)進(jìn)行研究，并取得了一定的進(jìn)展。目前已經(jīng)開發(fā)出一些實(shí)驗(yàn)性的三維模型檢索系統(tǒng)。sQsAEJkW5T!3論文組成部分介紹在下面章節(jié)，在第二章對三維模型檢索技術(shù)的形成與發(fā)展做了概述。在第三章討論了目前較常用的一些三維模型特征提取技術(shù)。在第四章，介紹了提出的一種三維模型特征提取方法，此方法稱為基于二維投影的三維模型檢索方法，并對實(shí)驗(yàn)結(jié)果做出了分析比較。GMsIasNXkA第二章三維模型檢索技術(shù)概述2.1二維圖像檢索物體之間形狀相似性的比較，可以追溯到早期基于形狀的圖像檢索：提取圖像中感興趣物體的輪廓或區(qū)域，采用不同方法描述其形狀特征，將問題簡化為形狀特征的比較。借助于計(jì)算機(jī)

12、視覺技術(shù)，人們TlrRGchYzg可以定義多種二維形狀表示方法和相似性度量。二維形狀表示大致分為三類：特征向量法、變換形狀方法與關(guān)系方法。具體選擇哪一種表示方法取決于應(yīng)用的要求，如目標(biāo)形狀的特征點(diǎn)，是否允許遮擋與形變的存在，噪聲強(qiáng)弱，以及索引難易程度等。7EqZcWLZNX上述形狀描述方法無法直接擴(kuò)展應(yīng)用在三維模型上，主要原因是他們要求為連續(xù)曲線（或平面上區(qū)域的邊界存在標(biāo)準(zhǔn)參數(shù)化表示。對于任意三維曲面，需要根據(jù)具體應(yīng)用，恢復(fù)成一致曲面或流形曲面，得到相應(yīng)曲面的參數(shù)，這樣才能采取擴(kuò)展的三維形狀描述。在重建過程中，需要引入人工干預(yù)，以消除模型二義性。lzq7IGfO2E基于形狀的圖像檢索系統(tǒng)用多維

13、特征空間距離來衡量形狀相似性。在特征維數(shù)不是很高的前提下，用索引結(jié)構(gòu)組織特征向量，將加速數(shù)據(jù)庫的訪問。但是，由于人類的感知相似性并不等價(jià)于物體的拓?fù)湎嗨菩?，單一特征無法完整描述物體的形狀。因而需要提取多種形狀特征，給出盡可能詳盡的表示。為了滿足創(chuàng)建索引結(jié)構(gòu)的要求，需要將多特征進(jìn)行降維處理。zvpgeqJ1hk2.2三維模型檢索如何在浩如煙海的三維模型數(shù)據(jù)庫和網(wǎng)格中快速有效的搜索有用的、同主題的模型，構(gòu)成了三維模型檢索的主要目標(biāo)。與二維圖像相比，三維模型有其獨(dú)特的性質(zhì)。首先，三維模型空間中一個(gè)簡單的物體，即可以用多邊形面片、也可以用點(diǎn)、線和體素，還可以由基元物體的幾何操作和布爾操作表示。任意的三

14、維曲面不存在類似二維空間上弧長公式的直接參數(shù)化方法，因此無法對物體空間定義規(guī)則NrpoJac3v1的、標(biāo)準(zhǔn)的類似二維圖像的采樣方式。這種內(nèi)在的不規(guī)則采樣和三維表面存在任意的拓?fù)潢P(guān)系，使得經(jīng)典的信號處理技術(shù)，無法直接擴(kuò)展應(yīng)用到三維。1nowfTG4KI其次，空間維數(shù)大小直接影響模型特征對應(yīng)、參數(shù)匹配，分類其構(gòu)造，優(yōu)化路徑搜索等問題，其復(fù)雜度與處理時(shí)間隨之顯著增加?？赡艿哪Ｐ屯嘶F(xiàn)象使得常用的幾何形狀特征，如面積、體積、曲率等難以計(jì)算。fjnFLDa5Zo另一方面，三維模型檢索與相機(jī)配置、光源設(shè)置和場景語義無關(guān)，且不包含反射、陰影、遮擋、透射等效果，不需要考慮環(huán)境光照條件、相機(jī)參數(shù)、鏡頭校準(zhǔn)、自遮

15、擋等現(xiàn)象，極大地簡化了匹配相似物體的過程，或因?yàn)橥队暗降孛孀優(yōu)閮蓚€(gè)人，或者由于周圍場景的迷惑性而憑空消失。tfnNhnE6e5綜上所述，三維模型特征的選取，需要考慮以下三個(gè)方面：第一，特征要能夠反映物體的內(nèi)在基本特性。第二，三維模型在空間中的位置、朝向和大小是任意的，因此，所提取的特征應(yīng)該與模型的平移、旋轉(zhuǎn)、放縮等剛體變換無關(guān)。第三，即便對于退化的三維模型，特征也必須是確定的。HbmVN777sL2.2.1三維模型檢索系統(tǒng)基于內(nèi)容的三維模型目前對模型匹配的研究主要集中在對三維模型的空間幾何形狀的相似性度量，有少數(shù)關(guān)于拓?fù)湎嗨菩云ヅ涞难芯?，基于紋理或材質(zhì)等屬性的相似性研究國內(nèi)外尚比較少見?；趦?nèi)

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

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

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

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

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

21、理想的查詢接口在檢索系統(tǒng)中非常重要。WwghWvVhPE(6檢索性能的判斷對于三維模型的檢索性能的判斷，主要從查全、查準(zhǔn)、時(shí)間、資源消費(fèi)等幾個(gè)方面來衡量。目前的研究主要是用查全率和查準(zhǔn)率兩個(gè)參數(shù)來對檢索性能進(jìn)行評判。asfpsfpi4k總之，如何提取模型的特征是三維模型檢索首先需要解決的關(guān)鍵技術(shù)，也是目前研究比較多的一個(gè)方面。2.2.2三維模型預(yù)處理要真正實(shí)現(xiàn)基于內(nèi)容的三維模型檢索，非常關(guān)鍵的一點(diǎn)就是要求所提取的三維模型特征描述具有針對平移、旋轉(zhuǎn)、尺度大小以及方位變換的不變性和魯棒性。ooeyYZTjjl目前，實(shí)現(xiàn)特征描述不變性的方法主要有三種(1使用主成分分析印方法對三維模型坐標(biāo)進(jìn)行標(biāo)準(zhǔn)化，

22、計(jì)算其標(biāo)準(zhǔn)化的坐標(biāo)框架.然后，在此標(biāo)準(zhǔn)化坐標(biāo)系內(nèi)提取相應(yīng)的特征：BkeGulnkxl(2將所有待比較的三維模型兩兩之間進(jìn)行坐標(biāo)對齊。這種方法由于極為費(fèi)時(shí)而很少被采用；(3定義并提取本身具有不變特性的特征描述。但實(shí)際上，這些特征描述所具有的不變性往往是不全面的，例如，Suzuki等人提出的形狀特征只對繞坐標(biāo)軸90度的變換保持不變性01。提出的反射對稱特征描述只具有平移和尺度不變性1。而且，大多數(shù)這類特征的計(jì)算有時(shí)也需要在一個(gè)歸一化的坐標(biāo)系內(nèi)完成。因此，為了進(jìn)一步提高檢索的準(zhǔn)確性，往往也需要進(jìn)行模型坐標(biāo)標(biāo)準(zhǔn)化。PgdO0sRIMo2.2.3三維模型特征提取3D模型檢索技術(shù)的關(guān)鍵是提取特征，在提取特

23、征時(shí)有如下一些基本要求：(1平移不變在平移變換前后，3D模型的特征要保證不變；(2旋轉(zhuǎn)不變在旋轉(zhuǎn)變換前后，3D模型的特征要保證不變；(3縮放不變在縮放變換前后，3D模型的特征要保證不變；(4對噪聲具有魯棒性(噪聲包括模型裂縫、插入三角面片、移去三角面片等。在有噪聲的情況下,3D模型的特征要保證相似；3cdXwckm15(5對重采樣和簡化具有魯棒性，在重采樣和簡化變換前后，3D模型的特征要保證相似。從計(jì)算機(jī)圖形學(xué)發(fā)展的初期開始，多邊形網(wǎng)格就是通用的三維模型的表示方法。盡管后來出現(xiàn)了更多的描述方法，但由于多邊形具有形狀簡單、便于計(jì)算和處理等特點(diǎn)，使得三維模型檢索的研究者們更多以多邊形網(wǎng)格模型作為研

24、究對象。目前，三維模型特征提取方法主要分為三大類：基于外形的h8c52WOngM低層方法；基于結(jié)構(gòu)的高層方法；基于視角的方法。在下章中，將詳細(xì)討論特征提取方面的研究。2.2.4相似性度量模式識別、分類、聚類、檢索等常常被應(yīng)用在計(jì)算機(jī)視覺、機(jī)械工程、分子生物學(xué)等領(lǐng)域，特征提取和相似性度量是完成這些任務(wù)的關(guān)鍵技術(shù)保證。如前所述，好的特征提取方法可以保證得到精確的形狀描述符，它是模型檢索的關(guān)鍵前提，相似性度量則是使得精確的形狀描述得到正確應(yīng)用的進(jìn)步保證。v4bdyGious相似性度量的任務(wù)就是在多維特征空間中，計(jì)算用戶的三維模型查詢請求與三維模型庫中的模型之問的相似性距離，距離越小，說明兩個(gè)模型的相

25、似性程度越高，反之，距離越大，說明匹配或度量的兩個(gè)模型之間的相似程度越小，最終系統(tǒng)根據(jù)相似性度量的距離大小返回查詢結(jié)果，從而實(shí)現(xiàn)基于內(nèi)容的模型檢索，或者通過構(gòu)建特定的分類器，得出模型之間的相似程度。因此，選擇合適的相似性度量方法是對進(jìn)行精確匹配的進(jìn)一步保證。J0bm4qMpJ9相對于三維檢索形狀算子的研究而言，相似度比較方法在圖像檢索領(lǐng)域已有了比較成熟的研究。在基于內(nèi)容的三維模型檢索系統(tǒng)中，針對不同形式的特征空間，有時(shí)需要采用不同的適合的度量函數(shù)。目前在基于內(nèi)容的三維模型檢索中，主要借鑒了基于內(nèi)容的二維圖像檢索中所采用的一些距離度量算法，以下作一個(gè)簡單的介紹。XVauA9grYP設(shè)U為特征空間

26、，乙少為特征向量，并且有zU,yU度量函數(shù)為/(x，力，理想的度量函數(shù)必須易于計(jì)算，符合人類的形狀感知，并滿足以下特征：正定性(possessiveness>bR9C6TJscwVx,yU,d(x,y>>0對稱性Vx,yU,d(x,y>=d(y,x>自反性VxU,d(x,x>=0嚴(yán)格的正定Vx,yU,x豐y=>d(x,y>>0三角不等式Vx,y,zU,d(x,y><ad(x,z>+bd(z,y>+c常用于三維模型檢索領(lǐng)域的主要有Euclidean距離、Manhattan距離、馬氏距離以及Hausdorff距離等。pN

27、9LBDdtrd設(shè)三維模型的特征空間為U=Rn,任意兩個(gè)三維模型的特征向量X,Y,分別表示為：X=x1,X2,.,xn,Y=y1,y?,.,y*,上述常用的經(jīng)典的距離公式分別為：(1>歐幾里德距離丼-V(xi-yif七該距離適用于任何維數(shù)的特征空間，而且計(jì)算簡單，在很多文獻(xiàn)中都被使用。但是這個(gè)距離的計(jì)算有一個(gè)前提，它假設(shè)了在同一特征空間的兩個(gè)特征分量Xi,Xj彼此是獨(dú)立的，這就可能導(dǎo)致錯(cuò)誤的或者不夠準(zhǔn)確的匹配。為了彌補(bǔ)傳統(tǒng)的歐幾里德距離的缺陷，Ankerst提出了一種經(jīng)過改進(jìn)的度量方法，用一個(gè)相似矩陣A表示特征空間各個(gè)分量的相關(guān)性，如下述公式所示：DJ8T7nHuGT力二偽仙*以&quo

28、t;腫)2T)(2>Manhattan距離比立斗-耳丨i.1(3>Hausdorff距離Hausdorff距離通常用來比較不同大小的兩個(gè)點(diǎn)集之間的相似性，其定義為:D(xfy)=maxmind(xi,yjslijsn其中，表示兩個(gè)特征點(diǎn)集中任意兩點(diǎn)之間的距離，如Euclidean距離等，max(>為取最大值函數(shù)，min(>為取最小值函數(shù)。QF81D7bvUA(4>馬氏距離(MahalanobisDistance>馬氏距離首先根據(jù)已有的特征向量集合估計(jì)出協(xié)方差矩陣，然后定義如下的對稱距離：其中，A是根據(jù)已有的特征矢量集估計(jì)出來的NXN的相似矩陣。2.2.5相關(guān)

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

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

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

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

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

34、搜索引擎，提供了二維草圖和三維草圖的繪制界面，并具有規(guī)模最大的三維模型數(shù)據(jù)庫，其中包括31000個(gè)通用的三維模型以及多個(gè)專業(yè)的三維模型子庫。（如圖2.2所示jW1viftGw9http:/shape,/search,htmlT»*r44li+暮-W*-3DModelSearchEngirt白M10/31#和*V"辛Mfr*'*JisiJLsre碼1*”產(chǎn)站列.掣鼻_jFWH|-.曰«厲itlidHSi曰*41iI,-#吞4-«EEWid車祈i«ulir-eMi3*JiIJWT*V*#!*2"圖2

35、.2普林斯頓大學(xué)的三維模型系統(tǒng)(2美國卡耐基梅隆大學(xué)AMP(AdvancedMultimediaProcessing實(shí)驗(yàn)室開發(fā)的三維模型檢索系統(tǒng)，同時(shí)結(jié)合了底層形狀特征和語義特征進(jìn)行檢索，并提供了用戶相關(guān)反饋的功能。xSODOYWHLP/projects/3DmodelRetrieval(3德國萊比錫大學(xué)CGIP(ComputerGraphicsandlmageProcessing實(shí)驗(yàn)室的Saupe和Vranic等人開發(fā)的基于VRML模型庫的在線三維模型檢索系統(tǒng)LOZMkIqIOwCCCC(ContentbasedC1assificationof3Dm

36、odelsbyCapturingspatialCharacteristics，允許用戶任意選擇三維坐標(biāo)軸X,Y或Z進(jìn)行模型坐標(biāo)的標(biāo)準(zhǔn)ZKZUQsUJed化，這樣能使檢索結(jié)果更符合用戶的要求。該系統(tǒng)基于Web平臺設(shè)計(jì)，用戶界面友好。(如圖2.3所示httD:/merkur01.inf.unikonstanz.de/CCCC圖2.3萊比錫大學(xué)的三維模型檢索系統(tǒng)(4IBM日本東京研究院的“三維web環(huán)境”研究工程中的三維幾何形狀檢索和分析系統(tǒng)，該系統(tǒng)的開發(fā)目的是對三維模型庫進(jìn)行知識管理。(5希臘ITI學(xué)院信息處理實(shí)驗(yàn)室開發(fā)的基于VRML模型數(shù)據(jù)庫的三維模型檢索系統(tǒng)，除了可以在三維模型庫中進(jìn)行檢索外，

37、還提供了對三維模型進(jìn)行兩兩比較的用戶界面和功能。http:/3dsearch,iti.gr/default.php?page=3dsearch(6荷蘭Utrecht大學(xué)的GIVE(GeometrylmaginedVirtualEnvironment實(shí)驗(yàn)室研制開發(fā)的三維形狀搜索引擎，主要基于高斯曲率等形狀特征實(shí)現(xiàn)基于模型形狀的檢索。rCYbSWRLIAhttp:/www.cs.uu.nl/centers/give/imaging/3Drecog/3Dmatching.htmlFyXjoFM(7日本多媒體教育學(xué)院的Suzuki等人開發(fā)的基于web的多邊形模型檢索系統(tǒng)ogdenIV,該系統(tǒng)同時(shí)使用模

38、型的形狀和顏色特征對VRML模型數(shù)據(jù)庫實(shí)現(xiàn)檢索，以建立三維的網(wǎng)絡(luò)教案環(huán)境。TuWrUpPObXhttp:/www.nime.ac.jp/motofumi/Ogden(8美國布朗大學(xué)的LEMS(LaboratoryforEngineeringMan/MachineSystem實(shí)驗(yàn)室開發(fā)的三維模型檢索系統(tǒng)，以二維圖像為輸入方式，在三維模型庫中檢索出相似的三維物體模型。7qWAq9jPqE/vision/researchAreas/3DRecog/overview.htmlllVIWTNQFk(9德國波恩大學(xué)Klein和Novotni等人開發(fā)的數(shù)字圖書

39、館系統(tǒng)RoDA，該系統(tǒng)不對模型進(jìn)行特征提取，而是通過計(jì)算不同模型之間的體積測定誤差(V01umetricError以及補(bǔ)償輪廓(OffsetHull進(jìn)行檢索。yhUQsDgRT1/vision/researchAreas/3DRecog/overview.htmlMduZYnKS8I(10臺灣大學(xué)通訊與多媒體實(shí)驗(yàn)室研制的三維模型檢索系統(tǒng)，該系統(tǒng)使用MPEG7標(biāo)準(zhǔn)的三維形狀描述符和多視圖描述符對模型特征進(jìn)行描述，基于web平臺進(jìn)行三維模型檢索。(如圖2.4所示09T7t6eTnohttp:/3.tw/dynamic此外，

40、還有一些用于專業(yè)領(lǐng)域的檢索系統(tǒng)。如德國慕尼黑大學(xué)Ankerst等人研制的三維蛋白質(zhì)分子模型檢索系統(tǒng)e5TfZQIUB5rmatik.unimuenchen.de/Forschung/Similarity/Demos/proteins1SovAcvqm以及蘇格蘭Heriotwatt大學(xué)開發(fā)的于web的CAD模型搜索引擎ShapeSifter等。http:/www.shapesearchnet/ecm/index.html圖2.4中國臺灣大學(xué)的三維模型檢索系統(tǒng)2.3本章小結(jié)三維模型檢索被廣泛應(yīng)用于數(shù)字化圖書館、數(shù)字機(jī)和處理、分子生物學(xué)、機(jī)械工程、醫(yī)學(xué)圖像和圖形編

41、輯等各個(gè)領(lǐng)域，以構(gòu)建面向三維模型的專業(yè)化搜索引擎為目標(biāo)，有三維模型的獲取、特征分析、查詢處理和匹配以及用戶界面四個(gè)部分組成。GXRw1kFW5s由于種種原因，這個(gè)領(lǐng)域直到近兩年才引起足夠的重視，并得到了飛速發(fā)展。本章就是對三維模型檢索研究領(lǐng)域的歷史和現(xiàn)狀作一個(gè)的概述。通過概述，指出了目前存在的主要問題以及進(jìn)一步研究的重點(diǎn)和必要性。UTREx49Xj9在模型數(shù)據(jù)庫中，強(qiáng)壯的模型特征表達(dá)和識別是最根本的問題，此外，我們還需要很好的相似性距離度量方法，接下來的章節(jié)就是對這兩個(gè)問題進(jìn)行深入的研究。8PQN3NDYyP第三章三維模型特征提取的研究3.1三維模型預(yù)處理3.1.1模型規(guī)范化處理對三維模型規(guī)范

42、化的目的是使所有的模型滿足（1平移不變性：（2旋轉(zhuǎn)不變性：（3縮放不變性。也就是對于任何三維模型不管進(jìn)行了什么樣的平移變換，旋轉(zhuǎn)變換，縮放變換，只要對其進(jìn)行規(guī)范化預(yù)處理后，那么最終的大小，原點(diǎn)坐標(biāo)，方向都一樣，因此不影響特征的提取。本文使用了主成分個(gè)人資料整理僅限學(xué)習(xí)使用分析法PCA（PrincipleComponentAnalysis對三維模型進(jìn)行規(guī)范化處理。mLPVzx7ZNw（1平移不變?yōu)榱吮ＷC平移不變，首先求出三維模型的重心，將三維模型的重心作為三維模型的新坐標(biāo)原點(diǎn)，將三維模型平移到新的坐標(biāo)原點(diǎn)。計(jì)算三維模型重心的公式AHP35hB02d如下。NNEpmSpm=斗七一仙"）這

43、里w為三角形的面積，P為點(diǎn)的集合，求出c是三維模型的重心，將三維模型的坐標(biāo)原點(diǎn)移動到c點(diǎn)，形成的點(diǎn)集合如下。NDOcB141gT（2旋轉(zhuǎn)不變?yōu)榱吮ＷC旋轉(zhuǎn)不變性，首先使用公式計(jì)算三維模型的相關(guān)矩陣M,M是個(gè)3木3的矩陣。七一8"）T矩陣M是實(shí)對稱矩陣，因此特征根是3個(gè)不同的正實(shí)數(shù)。求出特征根，以降序排列3個(gè)特征根。然后求出3個(gè)特征根對應(yīng)的特征向量，將每個(gè)特征向量變?yōu)閱挝幌蛄?，最?個(gè)特征向量組成旋轉(zhuǎn)矩陣R，R同樣是3牢3的矩陣。使用旋轉(zhuǎn)矩陣R變換三維模型，計(jì)算出新的點(diǎn)集1zOk7Ly2vA（3縮放變換為了統(tǒng)一三維模型的大小，保證縮放不變，需要計(jì)算大小變換因子W）來變換三維模型。其中，N

44、N£久也刃亦叫"111/31刀舛也ElP,yI個(gè)人資料整理僅限學(xué)習(xí)使用31/31NN£久也>1-N-'£ip卅_i-is最后得到了平移變換響亮c、旋轉(zhuǎn)變換矩陣R、大小變換因子S。將這些變換應(yīng)用到原三維模型的頂點(diǎn)集合P完成規(guī)范化預(yù)處理。3.1.2三維模型的存儲方法（1三維文件格式介紹A.3DS數(shù)據(jù)結(jié)構(gòu)：3DS文件由許多塊組成，每個(gè)塊首先描述其信息類別，即塊是如何組成的。塊的信息類別用D來標(biāo)識，塊還包含了下一塊的相對位置信息。fuNsDv23Kh3DS二進(jìn)制文件中的數(shù)據(jù)是按低位在前、高位在后的方式組織的。如，4A5C組成的整型數(shù)，表明5C是高位

45、字節(jié)，4A是低位字節(jié)：對于長整型數(shù)。如：4A5C3B8F表明5C4A是高位字節(jié)，3B8F是低位字節(jié)。tqMB9ew4YX下面描述塊的具體定義。塊的前面兩項(xiàng)信息分別是：塊的ID和塊的長度（也即下一塊相對于該塊的字節(jié)偏移量，塊的ID是一個(gè)整型數(shù)，而塊的長度是一個(gè)長整型數(shù)。每個(gè)塊實(shí)際上是一個(gè)層次結(jié)構(gòu)，不同類型的塊，其層次結(jié)構(gòu)也不相同。HmMJFY05dE3DS文件有一個(gè)基本塊，其ID是4D4D，每一個(gè)3DS文件開頭都是有這樣一個(gè)塊構(gòu)成的。B.CTS和TD0文件格式CT圖像經(jīng)過三維重構(gòu)而來的,ViLRaIt6skCTS和TDO都是我所特有的三維模型文件格式。這些數(shù)據(jù)是有二維之所以要對這些格式支持，是因

46、為三維檢索在醫(yī)學(xué)上有很大的應(yīng)用前景。TDO數(shù)據(jù)結(jié)構(gòu)：/關(guān)于：lc.TDO文件讀寫的信息。/文件后綴TDO的是”ThreeDimensional0bject”的簡寫形式。StructtagTDOFILEHEADER/文件標(biāo)志字符串，必須是，”3D0bject”，不區(qū)分大小寫。Charm_chSymbol9:/文件版本號，當(dāng)前為1。除非對文件格式有較大修改，否則必須為1。UINTm_nVersion:/文件頭的大小，以字節(jié)（Byte為單位。UINTm_nFi1eHeaderSize:/本數(shù)據(jù)文件的狀態(tài)：0=原始：1=己進(jìn)行法蘭克福校正；2=己進(jìn)行分區(qū)切分。BYTEm_nState;/點(diǎn)數(shù)據(jù)層數(shù)：一

47、1=非分層數(shù)據(jù)（例如從DXF文件轉(zhuǎn)換的數(shù)據(jù)，在文件頭后有數(shù)據(jù)點(diǎn)序列；（=0=分層數(shù)據(jù)的層數(shù)，在文件頭后有若干層數(shù)據(jù)點(diǎn)序列。Intm_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ù)。一般情況下，對于分層數(shù)據(jù)應(yīng)有m_nTriangleLayerNum=（mnPointLayerNum-1的關(guān)系。Intm_nTriangleLayerNum:/此數(shù)據(jù)的最大最小坐標(biāo)：double0=x；double1=y;double2=z。9eK0GsX7HiDoublem_szMax

48、3:Doublem_szMin3:/保留字。Intm_nReVersedl:lntm_nReversed2:doublem_dReVersedl:doublem_dReVersed2:；CTS數(shù)據(jù)CTS存儲的是由空間點(diǎn)組成的等值線據(jù)。文件由兩部分組成：第一部分是文件頭信息：StructCTSFILEHEADERUINTnLayerTotal/內(nèi)層和外層層數(shù)的最大值UINTnDataHeight/圖象的數(shù)據(jù)高度UINTnDataWidth/圖象的數(shù)據(jù)寬度doublefFactorX/數(shù)據(jù)在X方向上的比例因子doublefFactorY/數(shù)據(jù)在Y方向上的比例因子doublefFactorZ/數(shù)據(jù)在

49、Z方向上的比例因子第二部分是文件的數(shù)據(jù)信息其內(nèi)容如下：層號第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)一存儲由于要使不同格式的三維模型能夠進(jìn)行統(tǒng)一的檢索，所以我們在模型輸入后統(tǒng)一使用C3Dobject類來對其進(jìn)行操作。此外，由于三維模型可能存在缺陷或噪音，而無法滿足算法特征提取的要求時(shí)，我們也是通過對C3D0bject類進(jìn)行標(biāo)準(zhǔn)化來實(shí)現(xiàn)的。naK8ccr8VIC3DObject類代表了三維物體模型。計(jì)算機(jī)圖形學(xué)中通常采用三角面片的

50、網(wǎng)格來表示一個(gè)三維物體，所以該類中一個(gè)重要的數(shù)據(jù)就是三角面片的集合。在對三維模型的編輯過程中，對構(gòu)成模型的三角面片信息進(jìn)行遍歷和搜索是一個(gè)常用的操作。在給出模型表示的數(shù)據(jù)結(jié)構(gòu)之前，先給出和三角形面片組成的網(wǎng)格有關(guān)的幾個(gè)定義。B6JgIVV9ao點(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ù)。三角形的法向量：空間三角形的法向量定義為從空間原點(diǎn)出發(fā)和該三角形所在平面垂直并指向該平

51、面的單位向量。點(diǎn)的法向量：空間中一點(diǎn)的法向量定義為和該點(diǎn)相關(guān)的所有三角形的法向量的平均法向量。如圖3.2所示，在空間網(wǎng)格中，頂點(diǎn)A相關(guān)三角形有a,b，c,d,e，f它的度為6。頂點(diǎn)A的法向量就為三角形a,b,c,d,e,f六個(gè)三角形的法向量的平均法向量。圖3.2頂點(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)格，那么勢必需要大量的存儲空間。顯然這種把空間一個(gè)點(diǎn)重復(fù)多次保存是完全沒有必要的。系統(tǒng)中采用索引

52、的方式來表示三維空間網(wǎng)格模型。P2lpeFpap5索引方法表示空間三角面片網(wǎng)格的思想如下：把所有構(gòu)成空間三角面片網(wǎng)格的頂點(diǎn)形成一個(gè)集合，并依次對所有頂點(diǎn)從0開始編號，依次類推。這樣網(wǎng)格上的每一個(gè)頂點(diǎn)都有一個(gè)唯一的編號，該編號也唯一確定了網(wǎng)格中的一個(gè)頂點(diǎn)，這個(gè)編號稱為索引號?？臻g三角面片的表示用構(gòu)成該三角形的三個(gè)頂點(diǎn)的編號來表示，即用三個(gè)整數(shù)來表示一個(gè)空間三角形，這三個(gè)整數(shù)為構(gòu)成該空間三角形三個(gè)頂點(diǎn)的索引號。每一個(gè)空間頂點(diǎn)的所有相關(guān)三角形構(gòu)成其相關(guān)三角形表，它和該頂點(diǎn)一一對應(yīng)。如圖3.3所示。3YlxKpScDMv.,n圖3.3三維網(wǎng)格索引法表示示意圖采用索引的方式來表示空間網(wǎng)格不僅可以節(jié)省大量

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

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

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

56、于旋轉(zhuǎn)。WHF4OmOgAw三維傅立葉變換特征是利用傅立葉變換公式將三維模型分解成不同的頻率表示，然后利用其中一些頻率系數(shù)形成的三維模型特征。首先對三維模型進(jìn)行規(guī)范化和體素化處理，然后對體素單元進(jìn)行離散的傅立葉變換。aDFdk6hhPd設(shè)V是三維模型的體素，進(jìn)行離散的傅立葉變換，把V變換到頻域空間，計(jì)算特征向量之間的絕對值距離和歐氏距離作為相似度，檢索時(shí)可以使用不同分辨率的特征向量檢索，即可以選擇三組特征向量中任何一組進(jìn)行檢索。vranic的測試表明，傅立葉變換檢索技術(shù)具有較好檢索效率，但是計(jì)算速度較慢。ozEIQQLi4T三維小波特征小波變換同樣也可以用于描述三維模型的特征，Paquet等人在檢索中使用了小波變換。文中使用了具有二階消失矩的DAU4小波。這種小波的變換矩陣W如公式所示，CvDtmAfjiA將W作用到模型的三個(gè)軸向就得到小波系數(shù)。先對三維模型進(jìn)行PCA和體素化處理，然后再在三個(gè)軸向上進(jìn)行小波變換，得到小波系數(shù)。一種改進(jìn)的，不需要擺好姿勢的基于球形調(diào)和的形狀描述法被FunkhouserQrDCRkJkxh等人（備注28,27提出。首先，3D模型通過與其相交的不同半徑的同心圓來分解成一