【正文】 模型的文件名或URL地址：而使用服務(wù)器上的三維模型實(shí)例檢索時(shí)，用戶可以通過縮略圖瀏覽的方式在界面上交互選取。(3)使用用戶交互繪制的三維草圖，如Igarashi等人設(shè)計(jì)的三維草圖繪制工具Teddy（備注21）。(4)基于文本關(guān)鍵字的檢索界面。此外，檢索界面還負(fù)責(zé)將檢索結(jié)果以可視化的方式顯示給用戶，以進(jìn)行瀏覽或下一步的檢索過程。如Elad等人（備注18）提出基于學(xué)習(xí)的檢索機(jī)制以自動(dòng)適應(yīng)不同用戶的檢索要求和偏好，在檢索結(jié)果顯示時(shí)提供了一個(gè)標(biāo)記“相關(guān)和“不相關(guān)”，兩種評價(jià)的用戶反饋界面。則進(jìn)一步對用戶評價(jià)界面加以細(xì)化，提供了調(diào)節(jié)“相關(guān)和“不相關(guān)”程度的反饋界面。其中，加拿大國家研究院的Paquet等人開發(fā)的三維模型檢索系統(tǒng)Nefertiti是第一個(gè)通用的三維模型檢索系統(tǒng)，所提取的特征主要包括形狀和顏色兩種。(如圖2．2所示)：／／shape．cs．princeton．edu／search．html圖2．2普林斯頓大學(xué)的三維模型系統(tǒng)(2)美國卡耐基：／／amp．ece．cmu．edu／projects／3DmodelRetrieval(3)德國萊比錫大學(xué)CGIP(Computer Graphics and Image Processing)實(shí)驗(yàn)室的Saupe和Vranic等人開發(fā)的基于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é)果更符合用戶的要求。(如圖2．3所示)httD：／／merkur01．inf．uni—konstanz．de／CCCC圖2．3萊比錫大學(xué)的三維模型檢索系統(tǒng)(4)IBM日本東京研究院的“三維web環(huán)境研究項(xiàng)目中的三維幾何形狀檢索和分析系統(tǒng)，該系統(tǒng)的開發(fā)目的是對三維模型庫進(jìn)行知識(shí)管理。：／／3d—search．iti．gr／default．php?page=3dsearch(6)荷蘭Utrecht大學(xué)的GIVE(Geometry Imagined Virtual Environment)實(shí)驗(yàn)室研制開發(fā)的三維形狀搜索引擎，主要基于高斯曲率等形狀特征實(shí)現(xiàn)基于模型形狀的檢索。：／／．nime．a(chǎn)c．jp／motofumi／Ogden(8)美國布朗大學(xué)的LEMS(Laboratory for Engineering Man／Machine System)實(shí)驗(yàn)室開發(fā)的三維模型檢索系統(tǒng)，以二維圖像為輸入方式，在三維模型庫中檢索出相似的三維物體模型。：／／．1ems．brown．edu／vision／researchAreas／3DRecog／overview．html(10)臺(tái)灣大學(xué)通訊與多媒體實(shí)驗(yàn)室研制的三維模型檢索系統(tǒng)，該系統(tǒng)使用MPEG一7標(biāo)準(zhǔn)的三維形狀描述符和多視圖描述符對模型特征進(jìn)行描述，基于web平臺(tái)進(jìn)行三維模型檢索。如德國慕尼黑大學(xué)Ankerst等人研制的三維蛋白質(zhì)分子模型檢索系統(tǒng)：／／．dbs．informatik．unimuenchen．de／Forschung／Similarity／Demos／protein以及蘇格蘭Heriot—watt大學(xué)開發(fā)的于web的CAD模型搜索引擎ShapeSifter等。由于種種原因，這個(gè)領(lǐng)域直到近兩年才引起足夠的重視，并得到了飛速發(fā)展。通過概述，指出了目前存在的主要問題以及進(jìn)一步研究的重點(diǎn)和必要性。第三章三維模型特征提取的研究3．1三維模型預(yù)處理3．1．1模型規(guī)范化處理對三維模型規(guī)范化的目的是使所有的模型滿足(1)平移不變性：(2)旋轉(zhuǎn)不變性：(3)縮放不變性。本文使用了主成分分析法PCA(Principle Component Analysis)對三維模型進(jìn)行規(guī)范化處理。計(jì)算三維模型重心的公式如下。 (2)旋轉(zhuǎn)不變?yōu)榱吮ＷC旋轉(zhuǎn)不變性，首先使用公式計(jì)算三維模型的相關(guān)矩陣M，M是個(gè)3木3的矩陣。求出特征根，以降序排列3個(gè)特征根。使用旋轉(zhuǎn)矩陣R變換三維模型，計(jì)算出新的點(diǎn)集 (3)縮放變換為了統(tǒng)一三維模型的大小，保證縮放不變，需要計(jì)算大小變換因子來變換三維模型。將這些變換應(yīng)用到原三維模型的頂點(diǎn)集合P完成規(guī)范化預(yù)處理。塊的信息類別用D來標(biāo)識(shí)，塊還包含了下一塊的相對位置信息。如，4A 5C組成的整型數(shù)，表明5C是高位字節(jié)，4A是低位字節(jié)：對于長整型數(shù)。下面描述塊的具體定義。每個(gè)塊實(shí)際上是一個(gè)層次結(jié)構(gòu)，不同類型的塊，其層次結(jié)構(gòu)也不相同。B．CTS和TD0文件格式CTS和TDO都是我所特有的三維模型文件格式。TDO數(shù)據(jù)結(jié)構(gòu)：‘／／關(guān)于：Ic．TDO文件讀寫的信息。Struct tagTDOFILEHEADER{／／文件標(biāo)志字符串，必須是，”3D0bject”，不區(qū)分大小寫。除非對文件格式有較大修改，否則必須為1。UINT m_nFi1eHeaderSize：／／本數(shù)據(jù)文件的狀態(tài)：0=原始：1=己進(jìn)行法蘭克福校正；2=己進(jìn)行分區(qū)切分。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ù)。Int m_nTriangleLayerNum：／／此數(shù)據(jù)的最大最小坐標(biāo)：double\[0]=x；double\[1]=y；double\[2]=z。Int m_nReVersedl：Int m_nReversed2：doublem_dReVersedl：doublem_dReVersed2：}；CTS數(shù)據(jù)CTS存儲(chǔ)的是由空間點(diǎn)組成的等值線據(jù)。此外，由于三維模型可能存在缺陷或噪音，而無法滿足算法特征提取的要求時(shí)，我們也是通過對C3D0bject類進(jìn)行標(biāo)準(zhǔn)化來實(shí)現(xiàn)的。計(jì)算機(jī)圖形學(xué)中通常采用三角面片的網(wǎng)格來表示一個(gè)三維物體，所以該類中一個(gè)重要的數(shù)據(jù)就是三角面片的集合。在給出模型表示的數(shù)據(jù)結(jié)構(gòu)之前，先給出和三角形面片組成的網(wǎng)格有關(guān)的幾個(gè)定義。它唯一確定了一個(gè)空間點(diǎn)。點(diǎn)的相關(guān)三角形表：是指和該點(diǎn)相關(guān)所有的三角形構(gòu)成的集合。三角形的法向量：空間三角形的法向量定義為從空間原點(diǎn)出發(fā)和該三角形所在平面垂直并指向該平面的單位向量。如圖3．2所示，在空間網(wǎng)格中，頂點(diǎn)A相關(guān)三角形有a，b，c，d，e，f它的度為6。圖3．2頂點(diǎn)和其相關(guān)的三角形示意圖從上面的例子．可以看出來，在三角形網(wǎng)格中絕大多數(shù)頂點(diǎn)的度都是大于1的。如果用這種方法來表示含有上萬個(gè)三角面片的空間網(wǎng)格，那么勢必需要大量的存儲(chǔ)空間。系統(tǒng)中采用索引的方式來表示三維空間網(wǎng)格模型。這樣網(wǎng)格上的每一個(gè)頂點(diǎn)都有一個(gè)唯一的編號(hào)，該編號(hào)也唯一確定了網(wǎng)格中的一個(gè)頂點(diǎn)，這個(gè)編號(hào)稱為索引號(hào)。每一個(gè)空間頂點(diǎn)的所有相關(guān)三角形構(gòu)成其相關(guān)三角形表，它和該頂點(diǎn)一一對應(yīng)。圖3．3三維網(wǎng)格索引法表示示意圖采用索引的方式來表示空間網(wǎng)格不僅可以節(jié)省大量存儲(chǔ)空間，而且對與模型的編輯和修改也帶來了很大的方便：這種存儲(chǔ)方式每個(gè)頂點(diǎn)只需要保存一次，當(dāng)用戶編輯該頂點(diǎn)的時(shí)候，如平移，那么只需要修改一次頂點(diǎn)信息，其索引值不變，所以和該頂點(diǎn)相關(guān)的三角形數(shù)據(jù)不發(fā)生任何變化，這也保持了數(shù)據(jù)的完整性。如果用戶刪除了某個(gè)頂點(diǎn)，則可以很方便的找到所有和該頂點(diǎn)相關(guān)的三角形，然后全部刪除這些相關(guān)的三角形，也便于計(jì)算各個(gè)頂點(diǎn)的法向量等。3．2三維模型特征提取技術(shù)的研究對一個(gè)三維模型進(jìn)行參數(shù)化是一個(gè)很復(fù)雜的問題，同時(shí)由于三維表面有任意的拓?fù)?，使得一些在二維圖像被使用的方法(如傅里葉變換)無法直接應(yīng)用在三維領(lǐng)域。對這些模型進(jìn)行有意義的幾何特征和形狀信號(hào)的計(jì)算是很困難的，因此尋找出有意義的特征成了研究人員首先考慮的問題。（備注1）3D模型檢索方法可大致的分為3類：基于外形的低層方法；基于結(jié)構(gòu)的高層方法：基于視角的方法。在3D模型表述系統(tǒng)中，基于外形的下層方法描述通常3D模型的幾何屬性，空間屬性，形狀分布范圍。Zhang和Chen例提出了通過網(wǎng)格描述，來有效計(jì)算面積、體積、對稱軸傅立葉變幻系數(shù)的方法。這種方法，需要擺好標(biāo)準(zhǔn)化的姿勢用于旋轉(zhuǎn)。首先對三維模型進(jìn)行規(guī)范化和體素化處理，然后對體素單元進(jìn)行離散的傅立葉變換。vranic的測試表明，傅立葉變換檢索技術(shù)具有較好檢索效率，但是計(jì)算速度較慢。文中使用了具有二階消失矩的DAU4小波。先對三維模型進(jìn)行PCA和體素化處理，然后再在三個(gè)軸向上進(jìn)行小波變換，得到小波系數(shù)。首先，3D模型通過與其相交的不同半徑的同心圓來分解成一系列圓形函數(shù)的聚集。在每個(gè)半徑圓上，每個(gè)頻率部分的范數(shù)和組成了形狀的表述。Novotni和Klein拉引對3D模型運(yùn)用查涅克矩。三維查涅克矩是一個(gè)通過半徑和頻率的二維直方圖索引。球面調(diào)和分析又稱單位球面上的二維傅立葉變換。(p，矽)(球面調(diào)和函數(shù))定義如下：其中是規(guī)一化常數(shù)。所有度為，的球面調(diào)和函數(shù)組成球面上一個(gè)2L+1維大小的旋轉(zhuǎn)不變子空問，任意定義在球面上的連續(xù)信號(hào)在子空間上的投影與信號(hào)的旋轉(zhuǎn)操作無關(guān)。但是，由于球面函數(shù)之間相互獨(dú)立，旋轉(zhuǎn)某些半徑分量下的球面函數(shù)，并不影響計(jì)算結(jié)果，而此時(shí)，物體的外在形狀卻發(fā)生改變。定義一組三維空間正交基函數(shù)，稱為三維ZerIlike函數(shù)：其中，是球面調(diào)和函數(shù)，是徑向函數(shù)，所有徑向下標(biāo)為n，度為l的Zemike函數(shù)張成三維空間上一個(gè)2l+1維大小的旋轉(zhuǎn)不變子空間。將小波變換應(yīng)用到三維檢索中最主要的困難仍然在于三維模型的表示。在簡單的應(yīng)用中，可以選用光滑的、具有有限消失矩的一維小波，例如，DAU4小波與Haar小波等，分別沿三個(gè)坐標(biāo)軸進(jìn)行變換。這種對應(yīng)圖的傅立葉變換已被用于檢索或相似性比較。在GD2表述法中，3D模型首先分解為三維像素格，相比于隨機(jī)點(diǎn)，這種隨機(jī)采樣操作只在多邊形表面的像素格內(nèi)。SSD描述了三維表面的全部點(diǎn)曲率的直方圖。3．2．2基于結(jié)構(gòu)的特征提取方法：基于形狀的方法之考慮三維模型的幾何、拓?fù)鋵傩?。Hilaga等人（備注38）用多分解Reeb圖來描述三維模型的概略結(jié)構(gòu)。Hilaga等人所用的Reeb圖是基于完整的測疑距離所定義的商函數(shù)，利用測地距離由i維物體的形狀計(jì)算出多分辨率Reeb圖，然后給出了拓?fù)鋱D相似度的定義，并依此進(jìn)行模型相似度的計(jì)算。為在某一層次上構(gòu)造Reeb圖，物體由連續(xù)函數(shù)分為若干區(qū)域，一個(gè)Reeb圖的節(jié)點(diǎn)表示一個(gè)特殊區(qū)域的連通部分，如果物體的兩個(gè)連通部分是相鄰接的，則對應(yīng)的節(jié)點(diǎn)相連。圖3．6多分辨率Reeb圖基于骨架信息能很好地進(jìn)行細(xì)節(jié)層次的控制，可以實(shí)現(xiàn)多層次的三維模型表示。(如圖3．6所示)這種方法利用了物體的全局和局部的性質(zhì)，但是，對于三維物體來講，應(yīng)用連續(xù)的測地線函數(shù)進(jìn)行離散的過程中，Reeb圖結(jié)構(gòu)依賴于間隔的大小，圖的節(jié)點(diǎn)沒有直接的物理含義，對邊界比較敏感，特別是增加了計(jì)算耗費(fèi)，不利于實(shí)時(shí)處理。用MRG來測量兩個(gè)三維模型之間的距離的主要優(yōu)點(diǎn)是，它對于圖形變形很穩(wěn)定。因此，一系列二維圖像被用于索引相似的3D模型。幾種方法給基于視角的三維模型檢索提供了幫助。其中，曲率和輪廓空間被用來描述每個(gè)“剪影。每個(gè)剪影由二值圖像表示。當(dāng)一個(gè)三維模型運(yùn)動(dòng)或變形，則描述該三維模型的二維剪影必須足夠多。(如圖3．8所示) 圖3．8運(yùn)用頻域轉(zhuǎn)換描述每個(gè)二維圖像3．2．4其他提取方法：除了形狀特征以外，還可以利用三維模型的表面屬性，包括顏色、反射系數(shù)和紋理等進(jìn)行檢索。Suzuki等人認(rèn)為，材質(zhì)顏色在很大程度上影響著三維模型的外觀屬性，對于三維模型的顏色而言，其復(fù)雜之處在于要考慮光照模型的影響，如環(huán)境光、漫射光、反光系數(shù)以及透明系數(shù)等等。以此為基礎(chǔ)，Suzuki等人提出一種基于用戶輸入的交互式三維模型顏色檢索方法，將每一種材質(zhì)顏色表示為光照模型中若干個(gè)光照參數(shù)的綜合值，基于一個(gè)有用戶主觀評價(jià)生成的顏色訓(xùn)練集，使用多元回歸分析方法對光照模型進(jìn)行預(yù)測。但由于三維模型表面屬性的多樣性和復(fù)雜性，表面顏色屬性特征提取的研究至今并未得到充分發(fā)展。總體來看，基于外形的方法速度較快，對模型的內(nèi)部構(gòu)造描述較好，但對細(xì)節(jié)表述不夠具體；基于結(jié)構(gòu)的方法對模型的整體框架描述較好，尤其適合運(yùn)動(dòng)的物體，但計(jì)算很費(fèi)時(shí)，并且它對于3D模型的精細(xì)部分非常敏感；基于視角的方法原理清晰，更符合人類判別三維物體相似性的基本原理，速度也較快，可是對物體內(nèi)部的構(gòu)造描述不夠，不適用于較精密的三維模型識(shí)別領(lǐng)域。隨后又詳盡的討論了現(xiàn)今種種的基于內(nèi)容的三維模型特征提取方法。三維模型檢索所使用的特征，主要包括通過變換提取物體整體或局部形狀特征以及對模型進(jìn)行幾何運(yùn)算提取的形狀特征。迄今為止，還沒有任何一種表示方式可以完全符合人類對形狀的識(shí)別和理解能力。如何得到既能快速簡單地進(jìn)行提取和比較，又能十分有效地分辨相似的和不相似的三維模型的特征描述，是三維模型檢索研究中的關(guān)鍵和難點(diǎn)。因此，本文在下面的章節(jié)中，設(shè)想提出一種基于不同視角進(jìn)行特征識(shí)別的三維模型檢索新方法。其中基于二維投影的三維模型特征識(shí)別的根本原理為：如果兩個(gè)三維物體多個(gè)視角的二維投影看起來相似，那么它們在三維上也是相似的。4．1模型預(yù)處理首先，畫一個(gè)簡單的包圍3D模型的邊界框(如圖4．1a)，將邊界框分成2L