【文章內(nèi)容簡(jiǎn)介】 子模型檢索系統(tǒng)：／／．dbs．informatik．unimuenchen．de／Forschung／Similarity／Demos／protein以及蘇格蘭Heriot—watt大學(xué)開發(fā)的于web的CAD模型搜索引擎ShapeSifter等。：／／．shapesearch．net／ecm／index．html圖2．4中國(guó)臺(tái)灣大學(xué)的三維模型檢索系統(tǒng)2．3本章小結(jié)三維模型檢索被廣泛應(yīng)用于數(shù)字化圖書館、數(shù)字機(jī)和處理、分子生物學(xué)、機(jī)械工程、醫(yī)學(xué)圖像和圖形編輯等各個(gè)領(lǐng)域，以構(gòu)建面向三維模型的專業(yè)化搜索引擎為目標(biāo)，有三維模型的獲取、特征分析、查詢處理和匹配以及用戶界面四個(gè)部分組成。由于種種原因，這個(gè)領(lǐng)域直到近兩年才引起足夠的重視，并得到了飛速發(fā)展。本章就是對(duì)三維模型檢索研究領(lǐng)域的歷史和現(xiàn)狀作一個(gè)的概述。通過概述，指出了目前存在的主要問題以及進(jìn)一步研究的重點(diǎn)和必要性。在模型數(shù)據(jù)庫(kù)中，強(qiáng)壯的模型特征表達(dá)和識(shí)別是最根本的問題，此外，我們還需要很好的相似性距離度量方法，接下來的章節(jié)就是對(duì)這兩個(gè)問題進(jìn)行深入的研究。第三章三維模型特征提取的研究3．1三維模型預(yù)處理3．1．1模型規(guī)范化處理對(duì)三維模型規(guī)范化的目的是使所有的模型滿足(1)平移不變性：(2)旋轉(zhuǎn)不變性：(3)縮放不變性。也就是對(duì)于任何三維模型不管進(jìn)行了什么樣的平移變換，旋轉(zhuǎn)變換，縮放變換，只要對(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ì)稱矩陣，因此特征根是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ù)處理。3．1．2三維模型的存儲(chǔ)方法(1)三維文件格式介紹A．3DS數(shù)據(jù)結(jié)構(gòu)：3DS文件由許多塊組成，每個(gè)塊首先描述其信息類別，即塊是如何組成的。塊的信息類別用D來標(biāo)識(shí)，塊還包含了下一塊的相對(duì)位置信息。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)成的。B．CTS和TD0文件格式CTS和TDO都是我所特有的三維模型文件格式。這些數(shù)據(jù)是有二維CT圖像經(jīng)過三維重構(gòu)而來的，之所以要對(duì)這些格式支持，是因?yàn)槿S檢索在醫(yī)學(xué)上有很大的應(yīng)用前景。TDO數(shù)據(jù)結(jié)構(gòu)：‘／／關(guān)于：Ic．TDO文件讀寫的信息。／／文件后綴TDO的是”Three—Dimensional 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)行法蘭克福校正；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 nPointLayerNum1)的關(guān)系。Int m_nTriangleLayerNum：／／此數(shù)據(jù)的最大最小坐標(biāo)：double\[0]=x；double\[1]=y；double\[2]=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 CTSFILEHEADER{UINT nLayerTotal ／／內(nèi)層和外層層數(shù)的最大值UINT nDataHeight ／／圖象的數(shù)據(jù)高度UINT nDataWidth ／／圖象的數(shù)據(jù)寬度double fFactorX ／／數(shù)據(jù)在X方向上的比例因子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)行操作。此外，由于三維模型可能存在缺陷或噪音，而無(wú)法滿足算法特征提取的要求時(shí)，我們也是通過對(duì)C3D0bject類進(jìn)行標(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ù)。三角形的法向量：空間三角形的法向量定義為從空間原點(diǎn)出發(fā)和該三角形所在平面垂直并指向該平面的單位向量。點(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次。如果用這種方法來表示含有上萬(wàn)個(gè)三角面片的空間網(wǎng)格，那么勢(shì)必需要大量的存儲(chǔ)空間。顯然這種把空間一個(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)。如圖3．3所示。圖3．3三維網(wǎng)格索引法表示示意圖采用索引的方式來表示空間網(wǎng)格不僅可以節(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)化帶來了便利。3．2三維模型特征提取技術(shù)的研究對(duì)一個(gè)三維模型進(jìn)行參數(shù)化是一個(gè)很復(fù)雜的問題，同時(shí)由于三維表面有任意的拓?fù)?，使得一些在二維圖像被使用的方法(如傅里葉變換)無(wú)法直接應(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)的高層方法：基于視角的方法。3．2．1基于外形的方法基于外形的方法嘗試通過幾何和拓?fù)涞膶傩悦枋?D模型的形狀，外形可以是由單獨(dú)向量組成的一些外形參數(shù)的固定數(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)。三維傅立葉變換特征是利用傅立葉變換公式將三維模型分解成不同的頻率表示，然后利用其中一些頻率系數(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作用到模型的三個(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)用查涅克矩。無(wú)疑，這是基于圓形諧波表述法的延伸。三維查涅克矩是一個(gè)通過半徑和頻率的二維直方圖索引。三維查涅克矩的好處在于它旋轉(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ù)空間的一組完備單位正交基