基變換的三維模型提取技術(shù),包括代碼和

基于小波變換的

三維模型特征提取技術(shù)學(xué)士學(xué)位論文答辯答辯人：指導(dǎo)教師：周光有金喜子2008年6月內(nèi)容提要本課題的主要工作和創(chuàng)新點本課題研究內(nèi)容三維模型特征提取方法小波加速計算過程綜合實驗演示參考文獻(xiàn)致謝1.本課題的主要工作及創(chuàng)新點1.1主要工作分析了光線投射算法的缺陷，提出了基于三維小波變換的光線投射算法。將小波變換引入到體素表示的三維模型中，分別實現(xiàn)了表面體素小波變換和實體體素小波變換。采用了L2和L1兩種相似性度量方式進(jìn)行匹配。實現(xiàn)了進(jìn)行特征評價的可視化實驗平臺。1.2創(chuàng)新點本文提出的小波變換特征提取方法，部分解決了文獻(xiàn)[15]存在的球函數(shù)定義二義性問題，在一定程度上解決了文獻(xiàn)[16]存在的球函數(shù)定義的不穩(wěn)定性。本文提出的方法與文獻(xiàn)[15]和文獻(xiàn)[16]相比，在查全率、查準(zhǔn)率、ST、FT等方面有所提高，算法的復(fù)雜度由原來的O(B4)變?yōu)镺(B3log(B))。[15]G.Burel,H.Henocq,Three-dimensionalinvariantsandtheirapplicationtoobjectrecognition,SignalProcessing,1995,45(1),pp.1-22.[16]D.V.Vranic,Animprovementofrotationinvariant3Dshapedescriptorbasedonfunctionsonconcentricspheres,Proc.Int.Conf.onImageProcessing,2003,volume3,pp.757–760.

2.本課題研究的內(nèi)容三維模型的表示方法三角網(wǎng)格法和體素法相似性度量方式和評價L2和L1兩種基于距離的度量方式Precision-Recall

曲線和FT、ST三維模型的規(guī)范化預(yù)處理平移不變縮放不變旋轉(zhuǎn)不變?nèi)S模型特征提取算法球面調(diào)和變換方法光線投射方法小波變換方法（包括三角網(wǎng)格、表面體素和實體體素）綜合實驗及可視化實驗平臺3.三維模型特征提取算法3.1

球面調(diào)和變換算法3.2光線投射算法3.3小波變換算法3.1球面調(diào)和變換算法[12]

將S2Kit從UNIX工作站上向Windows平臺上移植，把相應(yīng)的動態(tài)鏈接庫同開發(fā)環(huán)境結(jié)合起來。

[12]刑玉輝,幾種重要的三維模型特征提取方法實現(xiàn)研究.吉林大學(xué)碩士學(xué)位論文,2006年6月.

3.1球面調(diào)和變換算法

FST_semi_memo(rdata2，idata2,

rcoeffs，icoeffs,

size， seminaive_naive_table， workspace， 1， cutoff)；

rdata2和idata2兩數(shù)組用來存儲函數(shù)輸入也就是球面函數(shù)在各方向的采樣方向的實部和虛部值，對于本文的情況，輸入的球面函數(shù)采樣值均為實數(shù)，這樣idata2輸入為全等于0的數(shù)組首地址。rcoeffs和icoeffs兩個數(shù)組用來存儲函數(shù)的輸出的實部和虛部值，size為截止頻率即B，剩下兩個參數(shù)為系統(tǒng)為了計算而開辟的一塊內(nèi)存間的指針，cutoff默認(rèn)值為截止頻率B

。3.2光線投射算法

G.Burel等在文獻(xiàn)[15]中提出了光線投射方法。光線投射算法沿等經(jīng)度，等緯度方向從模型重心發(fā)射出一組射線：

[15]G.Burel,H.Henocq,“Three-dimensionalinvariantsandtheirapplicationtoobjectrecognition,”SignalProcessing,1995,45(1),pp.1-22.3.2光線投射算法

對于每條向外發(fā)射的射線，記錄它與三維模型表面的最遠(yuǎn)交點與模型重心之間的距離，這樣就可以離散地給出一個球面函數(shù)的定義，采樣點定義在切比雪夫節(jié)點的位置，因此可以直接利用球面調(diào)和變換的方法抽取一組旋轉(zhuǎn)不變量。缺陷：對于較為復(fù)雜的三維模型，每條射線可能與模型表面有多個交點，因此只考慮最遠(yuǎn)交點也會丟失很多幾何信息

3.2光線投射算法

D.V.Vranic在文獻(xiàn)[16]中提出了改進(jìn)的光線投射算法：[16]D.V.Vranic,“Animprovementofrotationinvariant3Dshapedescriptorbasedonfunctionsonconcentricspheres,”Proc.Int.Conf.onImageProcessing,2003,volume3,pp.757–760.3.2光線投射算法

算法的基本思想：以三維模型的重心為球心的最小包圍球剖分成一系列同心球殼，落入每個球殼的射線與模型表面的交點定義一個球坐標(biāo)方程。一般地，對于每條射線，它與模型表面的多個交點同時落入一個球殼的幾率大大降低了，這樣就可以盡可能的減少信息的丟失。對應(yīng)每個球殼的方程的定義：如方向的射線在該球殼內(nèi)與模型表面無交點，則如有交點，則的值定義為落入該球殼內(nèi)的最遠(yuǎn)交點與模型重心的距離。3.2光線投射算法

上面兩種方法都沒有根本上解決球面函數(shù)定義的二義性問題，并且，改進(jìn)的光線投射算法雖然減輕了出現(xiàn)二義性的幾率，但同時帶來了新的不穩(wěn)定性。當(dāng)引入的同心球面數(shù)增大時，三維模型的表面受到噪聲因素影響，在不同的球面之間跳躍的幾率也同樣開始增大，如下圖所示。

左圖中紅色的圓環(huán)代表一個球狀三維模型的表面，我們可以看到，全部的模型表面均分布在最外層球面內(nèi)。這樣經(jīng)過球面調(diào)和變換后，該模型所有的能量均包含在這層球面內(nèi)，其它球面對應(yīng)的能量為零。右圖所示帶有一個突起噪聲的球狀三維模型，可以看出，最外層球面內(nèi)分布的模型表面只占很小一部分，絕大部分模型的表面分布在次外層球面內(nèi)這樣，經(jīng)過球面調(diào)和變換后最外層球面只包含了很小一部分能量，模型的絕大部分能量

3.2光線投射算法

包含在次外層球面內(nèi)。由于我們用來度量兩個三維模型形狀差異度的度規(guī)是L2范數(shù)，即各層球面之間被認(rèn)為是相對獨立的，每個球面只與其它模型對應(yīng)層數(shù)的球面相比較，因此，形狀匹配的結(jié)果認(rèn)為這兩個模型的形狀差異度很大，這顯然不符合人的直觀感覺。通過上面的分析，本文提出了一種基于小波變換的三維模型特征提取方法。首先利用小波變換來刻畫三維模型的特征信息，并以此定義球坐標(biāo)函數(shù)。然后，將這些球函數(shù)分解成球面調(diào)和變換的序列和，并利用分解的系數(shù)構(gòu)造出一系列旋轉(zhuǎn)不變量，構(gòu)成該算法抽取的模型幾何特征。

3.3小波變換算法

3.3.1小波的分解與重構(gòu)

首先假設(shè)模型被一系列的同心球面包圍，最小包圍球的半徑為M，對于得到的M個切比雪夫采樣序列記為：

，定義：：：：：定義兩個濾波器算子H和G：

則小波分解算子為：設(shè)有M個同心球面構(gòu)成的三維模型能夠被分解成一系列的輪廓球面

和高頻

，則小波的分解示意圖為：小波的重構(gòu)與分解類似，只是過程相反。

設(shè)表示第層球面的半徑，，該球面上的切比雪夫采樣點為:

各個分量的小波系數(shù)為：

各個分量的尺度系數(shù)為：3.3光線投射小波變換算法step1．對模型作平移變換，使其重心與坐標(biāo)參考系原點重合。step2．對模型作縮放變換，使其最小外包圍球的半徑為M。step3．沿等經(jīng)度，等緯度方向從模型重心發(fā)射出一組射線:

step4．將模型最小外包圍球的半徑等分成個小區(qū)間,。

對于從模型的重心出發(fā)，沿方向向外投射的射線,若該射線在區(qū)間內(nèi)與模型表面無交點,則的值定義為0,否則,的值定義為落入該區(qū)間內(nèi)的最遠(yuǎn)交點與模型重心的距離。step5.對于所得到的射線的個離散值,進(jìn)行離散小波變(DWT)(利用上文介紹的小波分解與重構(gòu)方法):

3.3光線投射小波變換算法

其中,和分別是離散尺度函數(shù)和小波函數(shù)。step6．令，這樣，對于每個切比雪夫采樣方向的射線，我們均獲得了個值：因此，我們可以定義個離散表示的球面函數(shù)：

3.3光線投射小波變換算法step7．對每個球面函數(shù)進(jìn)行球面調(diào)和變換，將其分解成頻率由低到高的球面調(diào)和函數(shù)的序列和：

step8．由于球面調(diào)和函數(shù)相對于旋轉(zhuǎn)其范數(shù)不改變,因此對每個球坐標(biāo)函數(shù),定義L個球面調(diào)和函數(shù)的L2范數(shù)：3.3光線投射小波變換算法step9．組成3D模型的特征向量矩陣,矩陣元素值表示球面調(diào)和函數(shù)的范數(shù),其中,表示第個球坐標(biāo)函數(shù),表示第個球面調(diào)和函數(shù)。表面體素小波變換算法實體體素小波變換算法上面兩種算法涉及到三角網(wǎng)格向體素轉(zhuǎn)化的算法、種子填充算法、領(lǐng)域判斷、灌水式填充思想等，在本文的研究中文獻(xiàn)[12]的作者和AMP實驗室提供了大量源代碼和參考資料，本人只在此基礎(chǔ)上引入小波變換的方法。4小波變換加速計算過程第一步：對方向進(jìn)行切比雪夫采樣，得到采樣點序列第二步：Legendre連帶多項式的迭代計算[4]：

由

的對稱性，對

有第三步：計算1.對積分的離散化。設(shè)

[23]崔麗,N維廣義擬實數(shù)進(jìn)制小波_小波矩理論及其應(yīng)用,吉林大學(xué)博士學(xué)位論文,2002年2月.

則離散化后的結(jié)果為：2.對

積分的離散化。由知其離散化后的結(jié)果為：3.

對

積分的離散化，最后得到

知其離散化的結(jié)果為：第四步：計算特征描述符加速計算的具體體現(xiàn)：第三步的1，可以用一維快速傅立葉變換加速，這樣可以使計算量從原來的降低到第三步的2，利用的對稱性，可以將算法的計算量減半。。當(dāng)為偶數(shù)時，

當(dāng)為奇數(shù)時，第三步的3，對一維信號

可以用小波分析中的Mallat算法

加以提升。5.綜合實驗演示

本系統(tǒng)是在IntelPentium42.40GHzCPU、256MB內(nèi)存級別的PC機上設(shè)計實現(xiàn)的，具體的軟件環(huán)境如下：

操作系統(tǒng)：MicrosoftWindowsXPSP2

開發(fā)平臺：MicrosoftVisualStudio.Net2003

圖形接口：SiliconGraphics’OpenGLLibraryforWindows

計算接口：Matlab6.5

輔助軟件：S2kit，Gnuplot

實驗?zāi)Ｐ蛶欤篜rincetonShapeBenchmark5.1可視化實驗平臺顯示模塊檢索實驗?zāi)K特征提取模塊模型文件特征值文件OpenGL接口Gnuplot接口S2kit接口Matlab6.5接口5.2可視化實驗平臺顯示模塊顯示模塊模型顯示標(biāo)準(zhǔn)化過程方法可視化

面片顯示平移變換旋轉(zhuǎn)變換縮放變換射線法渲染顯示體素顯示5.3可視化實驗平臺特征提取讀取參數(shù)分配存儲空間球面調(diào)和變換小波變換載入模型創(chuàng)建輸出文件并寫入文件頭取off文件輸出特征值結(jié)束5.4可視化實驗平臺檢索評價模塊5.5

文獻(xiàn)[2]的實驗結(jié)果圖5.1固定球面數(shù)的射線方法圖5.2固定帶寬的多層球面射線方法5.5

本文的實驗結(jié)果圖5.3固定球面數(shù)的Harr小波變換方法圖5.4固定帶寬的Harr小波變換方法5.5

本文的實驗結(jié)果圖5.5多種方法的對比圖5.6體素表示的Harr小波變換方法5.5

本文的實驗結(jié)果圖5.7表面體素與實體體素的對比圖5.8兩種相似性度量方法的對比5.5

本文的實驗結(jié)果圖5.9兩種度量方式的對比圖5.10測試庫與訓(xùn)練庫的對比6.參考文獻(xiàn)

[1]周繼來,三維模型檢索技術(shù)及實現(xiàn)。西北大學(xué)博士學(xué)位論文,2005年5月.[2]崔晨旸,石教英.三維模型檢索中的特征提取技術(shù)綜述.計算機輔助設(shè)計與圖形學(xué)報.2004年7月.vol16.882~889.[3]楊育彬,林琿,朱慶.基于內(nèi)容的三維模型檢索綜述.計算機學(xué)報.2004年10月.第27卷第10期．1297-1310.[4]鄭伯川,彭維等.3D模型檢索技術(shù)綜述.計算機輔助設(shè)計與圖形學(xué)學(xué)報.Vol.16,No.7,July2004.pp873-881.[5]YangYuBin.Researchandapplicationsonthekeytechniquesofcontent-basedimageretrieval[Ph.D.dissertation].DepartmentofComputerScience,NanjingUniversity,Nanjing,2003(inChinese).[6]MallatS.MultiresolutionapproximationsandwaveletorthonormalbasesofL2(R).Trans.Amer.Math.Soc,1989,9;69~87.[7]MallatS.Atheoryformultiresolutionsignalposition;Thewaveletrepresentation.IEEETransonPAMI,1989,7,11(7);764~693.[8]ChuiC.KandWangJ.ZAcardinalsplineapproachtowavelets.Proc.Amer.Math.Coc.,1991,11(3);785~794.[9]WickerhauserMV.Adaptedwaveletanalysisfromtheorytosoftware.IEEEPress,TheInstituteofElectricalandElectronicsEngineers,Inc.NewYork,1994.[10]CoifmanR.andWickerhauserM.Entropybasedalgorithmsforbestbasisselection.IEEETrans.OnIT,1992,38(2);715~717.[11]FunkhouserT.MinP.,KazhdanM.etal..Asearchenginefor3dmodels.ACMTransactionsonGraphics,2003,22(1):83～105.[12]刑玉輝,幾種重要的三維模型特征提取方法實現(xiàn)研究.吉林大學(xué)碩士學(xué)位論文,2006年6月.[13]D.M.Healy,D.Rockmore,P.Kostelec,andS.Moore.FFTsforthe2-sphere-Improvementsandvariations,AdvancesinAppliedMathematics,(toappear).Preprintandcorrespondingsoftware,SpharmonicKit,areavailableat.[14].FFTW快速傅立葉變換軟件包.6.參考文獻(xiàn)

[15]G..Burel,H.Henocq,“Three-dimensionalinvariantsandtheirapplicationtoobjectrecognition,”SignalProcessing,1995,45(1),pp.1-22.[16]D.V.Vranic,“Animprovementofrotationinvariant3Dshapedes