三維模型的形狀描述子研究畢業(yè)論文

1、申10紳母我*大孝學(xué)士學(xué)位論文三維模型的形狀描述子研究作者姓名:學(xué)科專業(yè)：計算數(shù)學(xué)專業(yè)導(dǎo)師姓名:教授 完成時間：二o 年五月university of science and technology of chinaa dissertation for bachelor's degreestudy on shape descriptors for3d modelsauthor name:speciality:computational mathematicssupervisor:finished time:每次來到一個新地方，都會有一個過程來逐漸熟悉周圍環(huán)境和周圍的人。我 們往往會在這個

2、過程中慢慢蛻變并成長?？拼笠彩沁@樣一個新的地方，不同的是 這里發(fā)生的一切可能是我人生中最為重要、對我影響最深的。在完成畢業(yè)論文之 際，希望可以表達(dá)對科大和科大人的感謝。首先要感謝的是劉利剛教授，教授將我?guī)肓擞嬎銠C(jī)圖形的世界，不僅傳 授給我術(shù)-計算機(jī)圖形學(xué)的基本能力如：3d能力和編程能力，更是傳授給我了 道-不拖延、做事嚴(yán)謹(jǐn)。很榮幸能在大學(xué)二年級就遇到劉老師，劉老師治學(xué)嚴(yán)謹(jǐn)、 待人和善，將是影響我一生的啟蒙老師。衷心感謝他多年來給予我的悉心教導(dǎo)和 巨大幫助。其次需要感謝的是實(shí)驗(yàn)室的師兄們，他們向我提供了巨大的幫助，和他們在 一起的日子，不僅提高了自己的學(xué)術(shù)能力，更是獲得了美好的友誼。其中博士師

3、 兄單文和研究生師兄陳巖在我的畢設(shè)過程中幫助甚大，單文師兄對我的畢業(yè)論 文提供了指導(dǎo)性的幫助。每周和二位師兄的討論對自己畢業(yè)設(shè)計的理解和學(xué)識 的增長都會有所提升。實(shí)驗(yàn)室的師兄師姐在我進(jìn)行畢設(shè)過程中都提供了大量的 幫助和指導(dǎo)，在此也表示感謝。同時需要感謝每一位科大的老師和科大的同學(xué)，他們在我成長的階段都或 多或少給我提供了一些幫助，在此深表謝意。最后感謝科人為我提供這么濃厚的學(xué)術(shù)氛圍和完善的研究平臺，訃我四年 的成長巨大。摘要3abstract5第一章緒論71引言71.2課題研究的意義81.3相關(guān)工作81.3.1 統(tǒng)計81.3.2圖像描述子81.3.3文本描述子91.3.4三維模型形狀描述子91

4、.4本文的工作101.5本文的結(jié)構(gòu)11第二章 shape distribution discriptor 122.1 shape distribution122.2實(shí)驗(yàn)結(jié)果與分析12第三章 light field descriptor 153light field descriptor153.2 3d網(wǎng)格投影成二維圖形163.3圖像描述子173.3fourier descriptor173.3.2 zemike descriptor183.4 fourier 聯(lián)合 zemike193.5實(shí)驗(yàn)結(jié)果和討論203.5.1 matlab 聯(lián)合 mini database20352基于qt平臺的c+語言

5、的界面化三維模型檢索程序20第四章 shapegoogle234hks目錄234.1.1熱傳導(dǎo)方程234.1.2 熱核244.3 hks254.2 bag of feature264.2.1文本匹配274.2.2 bag of feature274.2.3 結(jié)果284.2.4 spatially-sensitive bag of feature284.2.5 bof & ss-bof294.3方法比較29第五章 總結(jié)與展望315研究內(nèi)容總結(jié)315.2展望31參考文獻(xiàn)32隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，人們對于檢索技術(shù)的需求也fi益急切。從以普通文 字檢索技術(shù)如搜索引擎，到一維的聲咅檢索技術(shù)如聽咅

6、識曲，再到二維的圖像檢 索技術(shù)如百度識圖谷歌識圖技術(shù)，檢索技術(shù)扎根于我們生活的方方面面，更影響 著我們的生活方式和工作效率。英特爾ceo科再奇提到：2015年將是另外一個 分水嶺，是從2d時代演進(jìn)到3d時代。與此同時，近年來3d模型數(shù)據(jù)庫發(fā)展迅 猛，數(shù)量級直逼圖像，因而對于3d模型的檢索技術(shù)的研究勢在必行。3d模型檢索的一大方向是通過將模型簡化成相應(yīng)的形狀描述子，從而將對 于3d模型的比較轉(zhuǎn)化為對于形狀描述子的比較。三維模型匹配的大致流程可以用以下步驟描述：data:模型sresult:模型s對應(yīng)的描述子1 initialization;2根據(jù)模型計算模型的feature;(這一步在有些情況可

7、以不需要)3根據(jù)模型的feature計算模型的descriptor;算法01:計算描述子流程本文主要研究并實(shí)現(xiàn)了三類形狀描述子，他們的出發(fā)點(diǎn)各不相同。sdd(shape distribution descriptor)采用了統(tǒng)計的方法，通過將模型簡化成 概率分布并比較相應(yīng)的概率分布圖達(dá)到對于模型的比較；lfd(light field descriptor) 采用的是二維圖像比較的方法，通過對于模型不同視角的采樣得到一 組二維圖像，通過計算基于shape輪廓的fourier描述了和基于shape的zernike 矩，從而達(dá)到對于三維模型的比較；shapegoogle方法采用了基于hk(heat

8、ker- nel)/hks(heat kernel signature)的feature以及文木檢索和圖像檢索的常用的 bof(bag of feature)/ss-bof(spatially sensitive bag of feature )得到相應(yīng)的描述 子再定義描述子和之間的距離即可達(dá)到對于模型的比較。模型之間的相似性比較方法很多。和我們熟知的多媒體數(shù)據(jù)檢索一樣，模 型的檢索同樣可以有基于文本和基于內(nèi)容兩種不同的方法。google的3d ware- house 上的大量模型都擁有大量的tag,我們基于tag的語義信息自然也可以得 到模型的相似程度。然而，這樣得到的結(jié)果往往不符合預(yù)期，達(dá)

9、不到我們在文木 檢索中的體驗(yàn)。此時基于內(nèi)容的模型匹配可以得到更加符合我們認(rèn)知的結(jié)果。本 文提到的三種方法均是基于內(nèi)容的模型匹配。關(guān)鍵詞：三維網(wǎng)格描述子光場描述子熱核熱核簽名bag of feature spatillay sensitive bag of feature 形狀描述子 googleshape 非剛性變換abstractalong with the amazing development of internet technique, the demand for retrieval technology is growing much quickly. from simple te

10、xt retrieval, like search engine, to one-dimensional sound retrieval and two-dimensional image retrieval , retrieval technique is cha inseparable part in people" s daily life. moreover, retrieval technique is always cha nging our work style and improving work efficiency at the same time, the ce

11、o of intel has mentioned that year 2015 isa watershed, as it witnessed the evolution from 2d techniques to 3d techniques recently, the amount of 3d models grows so fast that has been nearly close to the amout of 2d images therefore, the research of 3d models retrieval technique is necessary.an impor

12、tant method of 3d retrieval technique is to simplify the 3d models to shape descriptors in this way, the 3d models can be compared by comparing the shape descriptors instead.data: model sresult: the descriptor correspond to model s1 initialization;2 calculate modeps feature by model;(this step is no

13、t necessary)3 calculate descriptor by feature;算法 0.2: the step of calculating descriptorin this paper, we focus on three kind of descriptors which are based on different starting-point.sdd(shape distribution descriptor) is based on statistical theory, by which every 3d model is simplified as a pdf(p

14、robabilities distribution function). therefore the similarity between two models can be measured by the similarity of the two correspond pdfs. lfd(light field descriptor) is based on 2-dimensional images' method. by projecting into 2-dimcnsional space, 3d model is converted to a set of image. so

15、, for the benefits of the fully research of the similarity on images we can easily calculate the similarity between two 3d model. the method-shapegoogle, which combining hk(heat kemel)/hks(heat kernel signature) and bof(bag of feature)/ss-bof(spatially sensitive bag of feature) which is common in te

16、xt retrieval , obtains a robust result on non-rigid models.there are many kinds of method on comparing the similiarity between models. like the muti-media data retrieval,which is well known to us, the method of retrieval can be divided into two directions:one is based on text, another is based on co

17、ntent. the availablity of large datasets of 3d models with tags such as google 3d warehouse makes the method based on text feasible.however, the result based on such method can't meet our expectations and the same experience on text searching now, the method based on content can provide a better

18、 result and the three method mention in this paper are all based on content.key words: 3dmesh,descriptor, light field descriptor, heat kernel, heat kernel signature, bag of feature, spatially-sensitive bag of feature,googleshape, shape descriptor, non-rigid第一章緒論1-1引言一方面隨著三維數(shù)據(jù)生成和采集的能力的提升，另一方面得益于人們對于

19、三維數(shù)據(jù)的興趣，三維數(shù)據(jù)的發(fā)展日新月異。如此海量三維數(shù)據(jù)的存在，對于三 維數(shù)據(jù)的操縱能力需求自然非常急切。而決定三維模型的相似性是模型的識別, 檢索，聚類，分類的基礎(chǔ)。如果可以定義兩個模型之間的度量，即可確定模型間 的相似性。但是如何建立一個這樣的度量呢？如何找到可以表征模型的木征信息的屬 性呢？文本檢索，圖像檢索技術(shù)技術(shù)的日益完善，無疑為三維數(shù)據(jù)的檢索技術(shù)提 供了強(qiáng)大的技術(shù)積累。借鑒這些思想，我們總能從中舉一反三，得到應(yīng)用于三維 模型的合適的方法。相關(guān)示例可見圖1.12?(幾w)n(p“)(a) 2d laplace 方法(b)3d laplace 方法(c) 2d圖像壓縮(d)3d網(wǎng)格壓縮

20、圖1.1 2d到3d的一些平推結(jié)果注：圖(a),(b)源自 sigcourse-spectral mesh processing,圖(c),(d)為自己生成1.2課題研究的意義隨著科技的發(fā)展，3維數(shù)據(jù)的大量涌現(xiàn)，我們迫切需要對于3維數(shù)據(jù)的操控 能力。而對于三維數(shù)據(jù)而言。模型描述子自然是對于模型操縱的關(guān)鍵所在。形狀 描述子不但廣泛的應(yīng)用于模型的識別，檢索，聚類，分類，同時也會加深對于三 維數(shù)據(jù)的理解。本課題研究的三類形狀描述子，分別是來自三種不同的方向。他 們均是該方向杰出的思想，可以給我們一些啟發(fā)和指引。1.3相關(guān)工作1.3.1統(tǒng)計統(tǒng)計學(xué)是一門很古老的科學(xué)，它起源于研究社會經(jīng)濟(jì)問題。隨著數(shù)據(jù)樣

21、本的 數(shù)量急劇上升，統(tǒng)計的能力如虎添翼。采用統(tǒng)計的手段，我們通過獲取物體/事物的統(tǒng)計信息作為該物體/事物的屬 性，借助于這些手段我們可以做很多應(yīng)用。近年來，無論是人工智能，還是機(jī)器 學(xué)習(xí)，或多或少都在關(guān)注統(tǒng)計手段的應(yīng)用。而統(tǒng)計成功應(yīng)用讓科硏工作者嘗到了 很多甜頭，也促使科研工作者繼續(xù)扎根于統(tǒng)計的應(yīng)用。1.3.2圖像描述子在進(jìn)入形狀檢索之前，先討論相對成熟的圖像檢索技術(shù)，并從圖像檢索技術(shù) 中獲取啟發(fā)，可以發(fā)展出一系列平行于2d圖像檢索技術(shù)的3d形狀檢索技術(shù)。上世紀(jì)70年代出現(xiàn)的早期圖像檢索技術(shù)是基于文本的檢索方法(text-based image retrieval),這種方法是對每幅圖像進(jìn)行人

22、工標(biāo)注，從而將圖像檢索轉(zhuǎn)換為 文本檢索的過程。一方面，然而隨著數(shù)碼設(shè)備和智能手機(jī)的普及，多媒體數(shù)據(jù)庫 快速膨脹，基于人工標(biāo)注的耗時、昂貴；另一方面，人工標(biāo)注具有主觀歧義性, 為后來檢索應(yīng)用的普及造成極大的不便。為了解決上述兩個問題，90年代初研 究者又提岀新的基丁內(nèi)容的圖像檢索(content based image retrieval ,cbir)方 法，這種新方法是利用圖像的視覺特征進(jìn)行檢索的。常用的圖像視覺特征有顏 色、紋理、形狀以及空間分布等信息，通過這些底層特征集的某種合適距離判斷 圖像之間的相似性，然后根據(jù)這種相似性給出檢索結(jié)果。近年來，基于內(nèi)容的圖 像檢索系統(tǒng)得到了迅猛發(fā)展，大部

23、分系統(tǒng)都是基于范例的查詢。對于基于形狀的圖像檢索過程，2d圖像的基于特征的構(gòu)造分為：特征提取 和特征表述兩個層面。這其中的特征提取過程主要目的是尋求帶有重要信息的 穩(wěn)定點(diǎn)或者穩(wěn)定區(qū)域。如i,在2004年，sift方法利用線性scale-space來獲取 出現(xiàn)圖像的多重解上的特征點(diǎn)，同時也保證了 scale不變性1, mser方法 通過提取圖像屮最小變化區(qū)域來生成圖進(jìn)行分析。2008年，2也提出了選取 圖像中所有點(diǎn)或者特征的樣本點(diǎn)來作為特征提取。在特征提取結(jié)束后，就是如何進(jìn)行特征描述。2004年i提出了對應(yīng)與sift 的128維的基于點(diǎn)周圍圖像梯度方向柱狀圖向量化方法，并擁有旋轉(zhuǎn)不變的特 性。2

24、006年，3,提出了 64維的向量方法。z后，為了壓縮特征表示的大小，4 改善了由5提出的通過特征表示獲取的向量表示了進(jìn)行建立vocabulary。即便 如此，仍然會有一些不變的情況，比如兩篇文章中，“atthe”等詞匯的頻率很 高，無法說明這兩篇文章具有很人的相似性，也就是說這樣的特征表示是需要被 忽略的.amores提出了基于空間關(guān)聯(lián)的方法克服了這一問題。1 -3.3文本描述子文本描述子首推bag of word（詞袋法），通過統(tǒng)計的手段得到文本的統(tǒng)計信 息，通過對于統(tǒng)計信息的對比得到文本z間的相似性。由于詞袋法僅僅考慮到了 單詞出現(xiàn)的頻率，很多時候沒有意義。反而，如果考慮到詞組的出現(xiàn)頻率

25、，可以 更好的代表文本，得到文本間的相似性。文本檢索比較的手段已經(jīng)趨于完善，這 里不再贅述。1.3.4三維模型形狀描述子3d模型檢索技術(shù)的主要過程分為三步：形狀提取，特征描述，特征提取。而 對于檢索技術(shù)的評價會基于以下兒個方面：表1.1評價方面isometrytopologyholesscalelocal scalesamplingnoisepartialmixed同時一個好的檢索技術(shù)，需要對于模型的存儲方式不敏感，即：無論3d 模型是以點(diǎn)云形式存儲，述是以3d網(wǎng)格形式存儲都可以統(tǒng)一的進(jìn)行處理。而 對于3d模型檢索大致可以分為三個類型：可以看出基于形狀檢索的3d模型檢索和基于2d的圖像檢索有著

26、極其類似 的地方，似乎就是在對于2d圖像形狀檢索的一個平推，但實(shí)際上的困難是非常 之大的。在這個過程中，涌現(xiàn)出了很多杰出的思想.圖1.2是各類檢索方法的分表1.2檢索類型星于形狀檢索基于拓?fù)浣Y(jié)構(gòu)檢索慕于圖像比較檢索支圖geometry basedweighted point seta deformation based圖1.2形狀檢索的各類分支6更為詳細(xì)的背景可以參考6以及71.4本文的工作隨著統(tǒng)計技術(shù)在最近幾年到幾十年的迅猛發(fā)展，人們對于統(tǒng)計技術(shù)的運(yùn)用 越來越得心應(yīng)手。文字，圖像的統(tǒng)計信息已經(jīng)逐漸用來代表模型進(jìn)行模型間的比 較。自然三維模型的統(tǒng)計信息也有強(qiáng)大的模型表示能力。模型相似性比較的核

27、心 步驟是將模型轉(zhuǎn)化為相應(yīng)的描述子，通過對于模型相應(yīng)描述子的比較得到定量 的相似性關(guān)系。木文首先從統(tǒng)計手段入手,介紹并實(shí)現(xiàn)了基于8shape distribution descriptor 的方法，該方法和傳統(tǒng)的方法不同，通過定義三維網(wǎng)格的一個距離函數(shù)，并對于 給定模型具體計算統(tǒng)計該距離的分布。然后提出了基于9light field descriptor 通過將三維模型投影到二維平面，將三維模型之間的相似性的計算轉(zhuǎn)化為二維 模型間的相似性比較。最后一種通過計算模型每個點(diǎn)的feature,將模型轉(zhuǎn)化為 feature 的集合，利用文字相似性中的 bag of feature 和spatially

28、-sensitive bag of feature手段對于模型的相似性進(jìn)行計算。參考了 10和11.論文的結(jié)尾對于三種描述子做了一些對比和一些展望性的工作。1.5本文的結(jié)構(gòu)第一章緒論部分，交代了三維形狀描述子研究的一些背景知識和研究該課 題的意義。從基本的統(tǒng)計知識，到圖像描述子，文本描述子的發(fā)展，為后文的三 種方法做了一些拋磚引玉的工作。第二章至第四章分別介紹sdd描述子，lfd描述子以及shapegoogle描 述子，從理論出發(fā)并給出了一些實(shí)驗(yàn)的結(jié)果。第四章的最后給出了更多的結(jié)果和兒類方法的結(jié)果比較。第五章做了一些總結(jié)和展望。提岀了工作的一些優(yōu)缺點(diǎn)，并對未來進(jìn)一步的 研究給了一些參考性的方向

29、，同時也有一些實(shí)踐過程中涌出的新想法。第二章 shape distribution discriptor2.1 shape distribution我們可以定義一個模型上的shape函數(shù)，比如，隨機(jī)一點(diǎn)和一固定點(diǎn)之間的 距離d,隨機(jī)兩點(diǎn)之間的距離d,三隨機(jī)點(diǎn)確定的角度a,.如果兩個模型很相 似，并且我采樣的數(shù)目足夠大，我們對于shape函數(shù)做統(tǒng)計，他們的分布會盡可 能的一致。(當(dāng)然，這個過程是不可逆的，我們不能斷言：即便一采樣的數(shù)目足 夠大，他可以唯一對應(yīng)一個模型。但是只要我們可以把相似的模型找岀來，這個 結(jié)果已經(jīng)夠用了。即便是成熟的互聯(lián)網(wǎng)搜索也不可能完全準(zhǔn)確，也只是盡量提供 大量的備選選項)

30、。shape distribution 的流程如下：i建立一個模型上的shape函數(shù)fshape2建立隨機(jī)選取的點(diǎn)對,不妨記為db),i=,2,.n隨機(jī)點(diǎn)對的過程如下：事實(shí)上我們只要有產(chǎn)生一個隨機(jī)點(diǎn)的過程即可。如果 肓接對于模型頂點(diǎn)隨機(jī)選取，測試的結(jié)果證明這樣選的并不好。我們這里采用 新的隨機(jī)點(diǎn)方法：首先隨機(jī)選取模型上的三角形，記三角形的三個頂點(diǎn)分別為 a,b,c通過函數(shù)(1 -幣)昇+ 77(1 -r2)s+ (r0r2c(2.1)其中門，均為0 1的隨機(jī)數(shù)。3計算上述的隨機(jī)點(diǎn)對間的距離，為了保持scale不變性，將距離除去隨機(jī) 點(diǎn)對距離的最人值。對所得的距離做頻率統(tǒng)計，統(tǒng)計的橫坐標(biāo)為區(qū)間段

31、。我們得 到了一組v維的向量sd, v是所分區(qū)間的個數(shù)。4確定兩者之間的距禺差da,b= 11sda sdb 112sd的距離越近，表示模型的差異性越小。2.2實(shí)驗(yàn)結(jié)果與分析實(shí)驗(yàn)采用了來自groundtruthdatabasc四類物體，結(jié)果如2.1所示(b)(d)圖2.1幾類對比結(jié)果注：圖（a）為6個球體，圖（b）為四把劍，圖（c）為四張床，圖（d）為4扇門上述測試的數(shù)據(jù)按照繪圖的順序依次排列，結(jié)果如圖2.2所示球類o oo ooo劍h =n 床1 1門1 1圖2.2測試數(shù)據(jù)集注：編號順序與上述繪圖順序一致通過sd之間的對比以及模型之間的對比，我們有如下的結(jié)論：1 一類模型如果差異不大，他們的

32、sd的分布會盡可能的相似。2即使是一類的模型，他們的結(jié)構(gòu)也千差萬別，如圖1所示，由于goodsocr.obj球體內(nèi)部出現(xiàn)了八個點(diǎn)決定的正方體網(wǎng)格，因而出現(xiàn)了兩個奇異的值。3 sd的模型相似性比較僅僅是粗略的，不具有精細(xì)的辨識度。4實(shí)驗(yàn)過程做了大量的結(jié)果，結(jié)果證明sd描述子是切實(shí)可行的，并且效 率很高。第三章 light field descriptor3.1 light field descriptor兩個模型如果相似度很高，經(jīng)過一個旋轉(zhuǎn)加平移會盡可能重合，而此時對 于兩個模型球面投影得到的圖像的相似度也很高。這樣我們便可以實(shí)現(xiàn)2d表示 3d的效果。這樣的想法很直觀，同時也借助了 2d圖像檢索

33、技術(shù)的成熟性。然 而由于我們無法直接建立一個好的旋轉(zhuǎn)使得兩個模型發(fā)牛旋轉(zhuǎn)重合。此時我們 可以通過簡單的離散方法，使用12面體去逼近投影曲面，僅存儲下模型在12面 體每個頂點(diǎn)的投影圖像。這就是light field descriptor的主要思想。給定模型a, b,固定一個12面體(有20個頂點(diǎn)，固定20個頂點(diǎn)的序號), 分別對模型a, b進(jìn)行投影操作得到兩組投影圖像集合，其屮圖像的序號與投影 點(diǎn)的序號。模型a, bz間的距離可以定義為：a的投影圖像序列和b的圖像序列的旋轉(zhuǎn)群圖像距離和的最小值。(其屮圖 像距離會在后面提到)。用數(shù)學(xué)語言表達(dá)如(5.1)式所示dab = mind(ia,k, ib

34、,j, i = 1,.s(3.1)ik=引理31正十二面體的旋轉(zhuǎn)對稱群為5證明 正十二面體的旋轉(zhuǎn)對稱變換可以分成以下幾類：一是繞著六條對面 中心連接構(gòu)成的對稱軸旋轉(zhuǎn)72°, 144°, 216°, 288° (一共6><4=24種)，二是繞著 十條對角線旋轉(zhuǎn)120°, 240° (一共10x2=20種)，三是繞著對棱中心練成的對稱 軸旋轉(zhuǎn)180° (一共15種)，加上恒等變化，就是一共有旋轉(zhuǎn)變換24+20+15+1=60 種。也就是說 |sd(d)| =60= a5sd(d) =60= a5,并且有 24 個 5

35、循環(huán)，20 個3循環(huán)，15個2型置換，以及1個恒等變換，所以sd(d) f因而上述的旋轉(zhuǎn)群大小s=60.當(dāng)然，上述的結(jié)果還是過于粗糙，我們可以對觀測的角度進(jìn)行隨機(jī)選?。航o 定n個觀測角度(給十二面n個隨機(jī)的旋轉(zhuǎn))，可以得到n xn個(a,b)的組合對， 而其中在對角線上的n個組合對是相同的(a,b在世界坐標(biāo)系下的位置不變，從15相同方向?qū)τ谖矬w進(jìn)行觀測投射到平面的結(jié)果也相同)得到(nx(nl) +1)x60 種組合.這樣一來，我們斷言可以和大程度上逼近球面，若采用n=1o,我們有以 下的角度誤差，如(5.2)式所示180 360= 5460(3.2) x x %可以得到偏移量x=3.4

36、6;,顯然這樣的精度已經(jīng)足夠，如果結(jié)果精度要求 很高，可以適當(dāng)提高n的人小。此時兩模型之間的差異可以用下式(5.3)衡量。(3.3)*da,b = minda,b(lj, lj,j, k = ,.n圖3.1多視角組合結(jié)果3.2 3d網(wǎng)格投影成二維圖形這里使用opengl,通過glulookat函數(shù)設(shè)定攝像機(jī)的角度,然后通過glread- pixel得到二維圖像。圖3.2投影示意圖93.3圖像描述子根據(jù)上述的分析，一旦我們建立兩投影圖像z間的距離，模型相似性的問題 就迎刃而解了。這里采用 了 zernike moment descriptor(region shape descriptor)和

37、fourier dcscriptor(contour shape descriptor). region shape 描述子在意的是 shape 內(nèi)部的特征而忽略邊界，contour shape descriptor關(guān)注的是shape的輪廓，而忽 略shape內(nèi)部。因而兩種方法都無法對于所有情況提供一種理想的比較結(jié)果。但 是一旦可以結(jié)合兩種方法，我們會得到更加理想的結(jié)果。3.3.1 fourier descriptorfourier描述子是通過對于圖像的signature fourier變換得到的。我們常 用的shape signature 右 complex coordinate, curv

38、ature function, cumulative angular function 和 centroid functiono 在文章 zhang2008 屮證明了 centroid function 比 其他的簽名具有更好的表現(xiàn)。記shape的邊界坐標(biāo)為(x(jy),t = 0,2,.n 1,其中n為邊界點(diǎn)的數(shù)目。v心)=(x(z) - xcy +- )2(3.4)其中h和為centroid的橫縱坐標(biāo)。(3.5)c =寺回曲)t=0(3.6)r=o對r(z)做fourier變換有:廠en , = 0, 1, .n 1(3.7)由于centriod distance的平移不變性，可知道具有平

39、移不變性。為了使 得算子具有旋轉(zhuǎn)不變性，我們通過對于算子取模即|.scale不變性可以通過 除以|的|得到。（幾種不變性的細(xì)節(jié)證明在后面會提到）。同時根據(jù)的性質(zhì)，為了 減少數(shù)據(jù)冗余，我們最后取：(3.8)/=（hj,氏l，.卜噸1）|如|如 |他|此時這就是我們的fourier算子。對于三維的 shape 而言，在文章（zhang and luan integrated approach to shape based image retrieval）已經(jīng)證明 60 個 fourier descriptor 已經(jīng)可以充分 代表這個模型了。因而我們采用12面體已經(jīng)足夠精細(xì)。3.3.2 zernik

40、e descriptor一組定義在單位圓上的zemike多項式(3.9)仏s，&) = rnm其中m <= n,且rnms)=0,n m)/2(-1 )，( n -1)!z-0pnf (n _ m(n meven),(30) odd)對于一張圖像函數(shù).廠（x,刃（我們在做投影的時候是放在單位球中投影的，得 到圖像的范圍也自然處于單位圓中，這里無需再做歸一化），圖像的zemike矩定 義如下：刃+ 1zw= ./（兀尹）7訶（3）“詢（31）71y不難知是一組標(biāo)準(zhǔn)正交基。有了這么一組止交基，我們便可以和逆傅里葉變換一樣重建圖像：nn=0 m(3.12)圖3.3 zemike重建注：

41、結(jié)果源自 stephen yoo michael vorobyov 課程n取得越大，逼近的效果越好，下而一個例子：圖(a)是原圖，(b) (f)分別是n=5, 15, 25, 35, 45 的重建結(jié)果。為了獲取旋轉(zhuǎn)不變性，只需要取最終的z= |z|實(shí)際應(yīng)用中采用了前35個zemike矩。更多的性質(zhì)在文章12都有所提到，這里不再贅述。3.4 fourier 聯(lián)合 zemike現(xiàn)在我們有了 f -:/n)和z = ztz2, .z肌，只需要取聯(lián)合的描述子d = (q/i, af2f afn,企1,"習(xí)，爐力)，調(diào)節(jié)a, 0的大小可以適當(dāng)改善結(jié)果。具體 可以參考zhang2008最后兩張圖

42、像的相似性可以用下列式子來衡量：diab = i dadb 112上述數(shù)值越小，表示二者越接近。3.5實(shí)驗(yàn)結(jié)果和討論3.5.1 matlab 聯(lián)合 mini database圖3.4為對于6個模型的lfd的比結(jié)果.ooo1016461711562140408639160460911558140368635461746090813510679579411562115588135061287659140401403610679612808353863986355794765983530圖3.4小數(shù)據(jù)庫示例注：兩者之間的數(shù)值越大，代表模型間的差別越顯著我們對于一個大小為50的數(shù)據(jù)庫（數(shù)據(jù)庫模見圖3.

43、5）做了一些測試，下 面是對于一組6個模型的實(shí)驗(yàn)結(jié)果，見圖3.6從結(jié)果來看，lfd對于模型的相似度識別十分準(zhǔn)確，實(shí)驗(yàn)的結(jié)果十分符合 人為判斷的結(jié)果。3.5.2基于qt平臺的c+語言的界面化三維模型檢索程序程序測試結(jié)果圖3.5數(shù)據(jù)庫的縮略圖ho0of 1()mm 1(b>i iw»a(c)oo卜17磚4)aeoe(<*)m(f)圖3.6基于lfd的matlab實(shí)現(xiàn)的一些檢索結(jié)果圖3.7檢索程序示意圖注：基于qt平臺實(shí)現(xiàn)的三維模型檢索程序，工具欄提供了一些基本的讀文件, 操作文件的按鈕，左半部分是顯示讀入文件窗口，右半部分上方為為檢索結(jié) 果顯示窗口，右半部分下方顯示當(dāng)前使用的

44、數(shù)據(jù)庫的目錄(al(b)圖3.8結(jié)果展示注：此數(shù)據(jù)庫為完全groundtruth databse的約2000個模型，debug版木的匹 配時間在5s左右第四章 shapegoogle通過 shape distribution descriptor 我們可以得到某類物體的 shape function 的大致分布；而lfd給出了模型之間較為精細(xì)的差異，雖然對于噪聲，scale等 等具有較好的魯棒性，但是對于拓?fù)洳蛔兊l(fā)牛了非剛性變換(保持測地距離不 變)的情況卻束手無策.同時,shape disctribution和lfd都是global的方法。很難對于一個模型局部 做出比較。此時基于hks的兩

45、種方法做到了 muti-scale(local/global),也對非剛 性變換魯棒。原文可以參考10和11以及13.shape-dna是較早將laplace beltrami算子作為模型的不變量，hks的思想或多或少受到了 shape dna的 啟發(fā)，因而可以事先查看有關(guān)shape dna的相關(guān)工作144.1 hks4.1.1細(xì)專導(dǎo)方程(4.1)dudt其屮u(x, t)表示t時刻在位置x處熱量的大小。在我們熟悉的7?"空間，熱傳導(dǎo)方程的基本解有如下形式:x2(兀，/)=(兀丘們宀°)(4.2)0,(x g rn, / <0)對于一般的流形空間m,記此時的熱傳導(dǎo)方程

46、為:(4.3)dugu= dt如果記f(x)為t=0吋刻熱量在流形上的分布，hs 為t吋刻熱量的分布。此吋&稱為熱算子。不難證明皿和am存在以下的關(guān)系(4.4)證明 直接使用代入法，已知兩=嚴(yán) 對于上述式子進(jìn)行泰勒展開有：infihs = £1=0由上式可分別得到下列兩式(4.5)= -屮 =。/!inf£ i/!從上述兩式立得hq)= 詈4.1.2熱核4.1.2.1 定義(4.6)(4.7)對于7t空間，熱核的定義在上部分已經(jīng)提到。對于一般的流形情況，熱核k心,尹）滿足以下條件：6心x,尹)dt-> q,x,y e m(4.8)(4.9)limy e mto

47、莖djd =vf > 0,xj 6 m(4.10)dt十其中去(y)為dirac函數(shù)即:(4.11)對于緊致空間m,熱核可以有以下的顯式表達(dá)式：kqy) =4%(x)0q)n=0其中久rt為dirichlet問題中l(wèi)aplcian算子的特征值0 + 20 = 0 (in m)(42)0 = 0on dm)加為響應(yīng)的特征函數(shù)。不難證明al為緊致且自伴算子，由定理：hibertschmidt定理可知0 <a1<a2<a3< 2nlim 8離散laplace方法可以參考154.1.2.24.1.3 hks由上一部分的證明可以知道熱核函數(shù)具有良好的性質(zhì)，對于等距變換具有

48、較好的魯棒性。然而存儲kt(xf y)需要的空間巨大，不適宜對一般大量的模型的 進(jìn)行操作。同時求解的過程也會消耗大量的時間。事實(shí)上，熱核函數(shù)是信息冗余的。定理4.1當(dāng)laplace一beltrami operators的特征值不重復(fù)出現(xiàn)時,有：t : mn(43)1歲(xj) =tyx,y e m,t>0(4.14)x) =7(x)vx e m,t>q(4.這里我們定義熱核簽名：hks©) = k心,x)由上述定理可知hks包含了 heat kernel的兒乎所有的特性。但是hks 需要存儲的數(shù)據(jù)量卻從二維下降到了一維，從0(用)降到了 o(n).hks&x, x

49、)的 物理意義轉(zhuǎn)化成了，在點(diǎn)x給定單位熱量，經(jīng)過時間t的之后該點(diǎn)散發(fā)的熱量。取時間t=log(1000),計算出每個點(diǎn)的hks并轉(zhuǎn)化成colormap圖4.1結(jié)果:(d)(e)(0圖4.1模型的hks可視化從上述幾個例子可以直觀的看出hks具有以下特點(diǎn)：1. 在頂點(diǎn)與周圍變化大的點(diǎn)hks的值明顯越大，同時也可以作為模型的特 征點(diǎn)。(這個可以和熱傳導(dǎo)方程 u =也聯(lián)系起來，熱傳導(dǎo)方程的右邊表示的dt即是熱量傳播的速度，左邊的laplace算子可以可以離散為該點(diǎn)和周圍點(diǎn)的平均 的偏差。因而頂點(diǎn)和周圍點(diǎn)變化越大，該店熱量散發(fā)的越快，該點(diǎn)的hks的值 越大。)2. 第一組狼的模型由于是保距離的非剛性變

50、換，hks的值得分布兒乎趨于 一致。第二組人的模型：模型1和模型3的hks分布兒乎一致，對于模型2, 由于手和頭相互接觸，不在是等距變換，所以在手和頭的部位的hks和其他 兩組有較大的差別。4.2 bag of feature事實(shí)上，由上述過程可以得到每個點(diǎn)的hks(x,x), 個t*1維的向量。 基于hks的物理性質(zhì)，可以知道每個點(diǎn)的hks大致表征了該點(diǎn)領(lǐng)域的形狀。 如果可以把所有點(diǎn)的hks聯(lián)系起來，我們就可以得到整個模型的形狀了。4.2.1文本匹配文本匹配的典型方法是bag of words,也就是我們熟知的詞袋法。詞袋法的 大致流程如下：1. 對于已有文本的單詞進(jìn)行聚類得到一個單詞表2.

51、 對于每個文本按照單詞表上的單詞進(jìn)行詞頻統(tǒng)計得到每個文本單詞表的 分布3. 比較文木在單詞表上的分布即可確定文木間的相似性4.2.2 bag of feature對于模型，我們現(xiàn)在對于每個模型的每個點(diǎn)有了一個t維的向量hks,不 妨記為p(x),其中t為時間段的數(shù)量，可以類比成文本中的“單詞”。對于所有 模型的上的所有hks進(jìn)行聚類，不妨設(shè)聚類的大小為v,得到了一個大小為v 的”單詞表”，記為p, p2, p3,pv。此時再統(tǒng)計每個模型在“單詞表”上出現(xiàn)的 次數(shù)分布。和文本統(tǒng)計的手段不同的是，對于文本中的單詞表上的單詞，在每個 文本中總是會真是存在的。但對于模型而言，聚類得到的“單詞表”在模型

52、上完 全相同岀現(xiàn)的概率兒乎為0.因而簡單的統(tǒng)計出現(xiàn)的頻數(shù)是沒有意義的。這里我們不妨定義：岔(x) =c(x)e-*w,z= 1,2,3,.?(4.16)記&(x) = (&心)6(兀),&3(兀),(對)，參數(shù)c(x)使得|&(巧|=1.根據(jù)&心) 的定義我們不難觀察出p(x)與卩心)越接近，那么仇(x)的值越大。換言之， 我們可以這么認(rèn)為，0心)即為點(diǎn)x的hks屬于第i類的概率。ii。ii = 1 是為了使得讓x點(diǎn)處的hks在“單詞表”上出現(xiàn)的概率之和為1.如果我們使 得”對于一個頂點(diǎn)數(shù)目為n的模型x每個點(diǎn)“單詞表”上的岀現(xiàn)的概率值i,此 時對于單詞表

53、上的每個單詞進(jìn)行出現(xiàn)概率的統(tǒng)計：心)=込迪(4.17)n'71=1f(x)為一個v*1維的向量，他的第i個分量”單詞表“上的第i個單詞在模 型上出現(xiàn)的概率。f(x)即為模型的”單詞表“分布對于每個模型，對于統(tǒng)一的” 單詞表“，一旦有了”單詞表“分布，我們通過定義f(x)上的度量，即可確定模 型間的相似度。d bof(xf y )=1y)n(4.18)4.2.3結(jié)果我們采用了兩組非剛性變換的模型進(jìn)行了一些測試，測試模型為圖4.2,測試結(jié)果分別為圖4.3和圖4.4(d)(e)(f)«圖4.2測試模型注：a,b,c為一組非剛性變換的海馬系列；d,e,f為一組非剛性變換的狼系列4.2

54、.4 spatially-sensitive bag of feature事實(shí)上對于文本檢索而言，單純的單詞出現(xiàn)的頻率往往還是不夠全而的。事 實(shí)上，很多文木的相似性體現(xiàn)在單詞詞組岀現(xiàn)的頻率上，也就是考慮到文木空間 上的關(guān)系.4.2.4.1 spatially-sensitive bag of feature我們定義r x r維的矩陣fq0，其屮矩陣的每個元素f(i,j)有如卞定義：nfqdx(x), idxyy)=&力(兀歹)xx圖4.3海馬系列的bof結(jié)果圖4.4狼狼系列的bof結(jié)果函數(shù)idx(x)為聚類的分類函數(shù)，將點(diǎn)x映射到x所在的聚類，返冋聚類的id。 這樣我們便統(tǒng)計出了每個單

55、詞詞組在模型中岀現(xiàn)的次數(shù)。4.2.4.2 結(jié)果根據(jù)上述的方法，將計算得到的詞組頻率按數(shù)值映射到rgb空間有如下 結(jié)果，這里使用的模型和上述一致(海馬和狼系列)，結(jié)果見圖4.54.2.5 bof & ss-bof為bof和ss-bof設(shè)置一個權(quán)得到一種聯(lián)合的方法。如果再加入機(jī)器學(xué)習(xí), 通過大量的訓(xùn)練集的訓(xùn)練，可以得到更好的結(jié)果，這-點(diǎn)可以作為后期的工作。4.3方法比較sdd,lfd以及基于shapegoogle的三種描述子均有各自的優(yōu)缺點(diǎn)圖4.5 ss-bof的結(jié)果對于sdd, lfd而言，優(yōu)點(diǎn)在于計算迅速，對于scale,旋轉(zhuǎn)，平移都具有 魯棒性。同時sdd缺點(diǎn)在于過于粗糙，對于不同物體很難做出細(xì)致的區(qū)分。對 于lfd而言，是三維模型retrieval的方法中應(yīng)用最廣也是最為魯棒的。但是兩 種方法的的缺點(diǎn)在于對于非剛性變換束手無策。基于hks的shapegoogle方法 的最大的貢獻(xiàn)，在于找到模型的內(nèi)蘊(yùn)量，即使模型發(fā)生了非剛性變換也可以做出 準(zhǔn)確的判斷。然后計算hks的過程涉及到大型矩陣的分解，因而是速度上仍然 有所欠缺。同時對于非剛性變換的物體，我們不能簡單通過將模型兩點(diǎn)間的最大 距離歸一化得到scale不變性，因而本