2006年--外文翻譯--局部形狀匹配與相似性分析中的突出幾何特征（譯文）

1、<p>　　1.3萬漢字，7600單詞，4萬英文字符</p><p>　　出處：Gal R, Cohen-Or D. Salient geometric features for partial shape matching and similarity[J]. ACM Transactions on Graphics (TOG), 2006, 25(1): 130-150.</p>&l

2、t;p>　　局部形狀匹配與相似性分析中的突出幾何特征</p><p>　　拉恩賈勒，丹尼爾科恩</p><p><b>　　特拉維夫大學(xué)</b></p><p>　　這篇文章介紹了一個平面三角網(wǎng)格的局部匹配方法。這個方法適用于不同的拓撲與數(shù)字但卻大體相似的的平面區(qū)域。我們介紹了一種全新的局部平面描述元，它能有效的表現(xiàn)出局部平面區(qū)域的幾何形

3、狀。這種描述元是獨立于潛在的三角劃分而定義的，而且它能形成一種兼容性描述方法用于不同三角劃分平面的匹配。為了處理匹配大網(wǎng)格的組合復(fù)雜度問題，我們說明了突出集合特征的抽象概念并提出了一種方法去實現(xiàn)它。一個突出幾何特征就是一個非平凡局部圖形的復(fù)合高階特征。本文給出了一些相對較少量的突出幾何特征，這些特征能在各種不同的應(yīng)用下很好地展現(xiàn)一個平面。匹配突出幾何特征是基于指出旋轉(zhuǎn)不變特征值和通過幾何哈希法來加速投票進程。文章給出了這種方法在不同應(yīng)用

4、條件下的有效性，比如計算自相似性，校對，與從屬相似性。</p><p>　　論文類別與項目描述：I.3.5[計算機圖形學(xué)]：計算幾何與目標(biāo)建模</p><p><b>　　概述：算法</b></p><p>　　關(guān)鍵詞：局部匹配，突出特征，相似度，幾何變換</p><p><b>　　簡介</b>&

5、lt;/p><p>　　在眾多領(lǐng)域的大量幾何應(yīng)用中匹配是一個基本任務(wù)，比如計算機視覺，機器人學(xué)，分子生物學(xué)和其他的[Veltkamp與Hagedoorn 2001].近來，隨著三維模型廣泛用途的出現(xiàn)，在三維圖形檢索技術(shù)上的投資提高了。截至目前，相似度在整個模型之間進行測量的全局匹配是研究熱點[Tangelder 與Veltkamp 2004]。局部匹配適用于匹配從屬部分與區(qū)域。進行匹配的部分不是預(yù)定義的，它可以是任何

6、從屬圖形或者更大的圖，而且可以是任何方向性的和任何比例的。局部匹配相對全局匹配是一個更加艱難的問題，因為局部匹配中搜索并且定義從屬部分優(yōu)先于衡量相似度。</p><p>　　在這篇文章里，我們主要研究了三角網(wǎng)格平面的局部匹配。一般來說，定義一種度量標(biāo)準(zhǔn)來表示人對相似度的感知是很困難的。雖然相似度的度量已經(jīng)給定，但是匹配不同表現(xiàn)方式的形狀也是一個難題。此外，為了讓局部匹配更加實用化而有一些更大的組合復(fù)雜的問題需要克

7、服。舉個例子，圖一中的四朵荷花是一座佛像模型的一部分，要匹配它們就要求對超過含有1M個三角形的佛像模型進行廣泛搜索。可以看到這四朵花的形狀不完整而且各不相同；同時，這些花也處在不同的方向，而且它們的范圍也是不規(guī)則的。</p><p>　　為了解決這些問題，我們在平面內(nèi)定義了一個“局部平面描述元”稀疏集。這些描述元能表示出平面的局部區(qū)域，并獨立于潛在的三角劃分而定義，而且它能形成一種兼容性描述方法用于不同三角劃分平

8、面的匹配。因為描述元的數(shù)量是遠小于頂點的數(shù)量的，所以描述元能減小平面表示時的組合復(fù)雜度。只要能夠仔細地定義這些描述元，就能讓它們的描述能力充分有效。然而，對又大又復(fù)雜的平面進行局部匹配時這些描述元的數(shù)量還是顯得比較多了。因此，我們定義了“突出幾何特征”來形成復(fù)合的高階描述元。一個突出幾何特征，簡而言之，突出特征，它是由一組能夠局部描述一個平面的非平凡區(qū)域的描述元組成的。</p><p>　　一個平面的突出特征就能

9、很好的代表這個平面而且能給叢書圖形非全局相似度測量打下很好的基礎(chǔ)。突出特征匹配能夠適應(yīng)一些硬性要求，比如在一個平面或者一系列平面中尋找相似的部分。比如，在圖一中，佛像模型中的四朵荷花能夠由自相似性檢測而發(fā)現(xiàn)，這就是在同一平面中非平凡從屬部分去匹配另一個從屬部分。</p><p>　　在本文中，我們做了一下的研究：</p><p>　　局部匹配。我們解決了三角網(wǎng)格的局部匹配問題。這個方法是在

10、最近三維模型的匹配結(jié)果上得到啟發(fā)的。</p><p>　　局部平面描述元。我們介紹了一種新的能將平面區(qū)域編碼的平面描述元。這些描述元獨立于潛在的三角劃分而定義，而且它能形成一種兼容性描述方法用于不同三角劃分平面的匹配。</p><p>　　突出幾何特征。我們介紹了突出幾何特征的抽象概念并且提出了一種方法來組織。一個突出幾何特征是一個能夠展現(xiàn)局部形狀的復(fù)合高階特征。對于每一個突出特征我們將一

11、定數(shù)量的角度和規(guī)模不同的不變量組織起來，從而加速匹配過程和相似度的計算。</p><p>　　應(yīng)用。我們給出了一些幾何應(yīng)用，其中部分匹配都是至關(guān)重要的。我們將此方法應(yīng)用到各種大而復(fù)雜的網(wǎng)格中來顯示出它的效果。</p><p>　　圖 1 左圖：快活佛模型的曲率分析和局部表面描述元。藍色表示地曲率值的部分紅色表示高曲率值部分。右圖：四朵蓮花的自相似性，這是由我們的局部匹配技術(shù)檢測到的。<

12、;/p><p><b>　　背景介紹</b></p><p>　　在眾多的研究領(lǐng)域中，相似度和圖形匹配問題都被擴展性研究了，比如計算機視覺，機器人學(xué)，分子生物學(xué)和其他的[Veltkamp與Hagedoorn 2001]。其中大部分研究重點在二維圖形的匹配上。幾何結(jié)構(gòu)已知后，三維模型的研究似乎變得更簡單了，而且也沒有熱河遮擋或者外部的干擾比如光照和反射。另一方面，三維模型缺

13、少簡單的參數(shù)化，這樣登記和特征匹配就變得更為苦難了。</p><p>　　在計算機圖形學(xué)中，三維圖像的匹配主要是為了圖像檢索而進步。近期，在使用網(wǎng)絡(luò)搜索引擎的情況下，三維模型的檢索新方法也被發(fā)現(xiàn)了，這個方法是基于幾何特性的而不是本文所說[Elad et al. 2001; Vranic et al. 2001;Iyer et al. 2003; Shilane et al. 2004; Min 2004]。然而，

14、在二維遮擋匹配中至關(guān)重要的部分匹配方法，在三維圖形檢索中卻沒有引起很多注意[Tangelder andVeltkamp 2004]。</p><p>　　大多數(shù)技術(shù)的目標(biāo)是通過圖形的整體幾何結(jié)構(gòu)來檢索到相似的模型。換言之，相似度是由三維模型的全局特性得來的，比如不變矩[Elad et al. 2001; Cybenko et al. 1997]，傅里葉描述元[Vranic et al. 2001; Saupe a

15、nd Vranic 2001;Ohbuchi et al. 2003b]，直方圖與形狀分布[Osada et al. 2001; Ohbuchi et al. 2003a]以及基于諧波的表示[Funkhouser et al. 2003; Kazhdan et al. 2003]。</p><p>　　這些方法首先要通過一些整體相似變換（旋轉(zhuǎn)+統(tǒng)一規(guī)模）對模型進行排列使其標(biāo)準(zhǔn)化，然后在模型之間建立對應(yīng)關(guān)系。這種全

16、局校準(zhǔn)方法不因細節(jié)改變而改變，而且會很容易造成相似的局部特征對錯誤地排列，進而導(dǎo)致不適當(dāng)?shù)娜窒嗨贫扔嬎?。這促使Kazhdan等人去控制各向異性的影響來補償這種全局方法的錯誤校準(zhǔn)。在這方面，我們所介紹的局部匹配方法能夠被用于校準(zhǔn)兩個全局相似度較低的模型。使用本文介紹的方法后，我們科準(zhǔn)確的匹配有聯(lián)系的突出特征再由局部匹配建立一個全局校準(zhǔn)（如圖二）。</p><p>　　基于圖的方法需要依靠三維模型拓撲是一個很重要的

17、圖形特性這一事實。拓撲結(jié)構(gòu)是一種關(guān)系型數(shù)據(jù)結(jié)構(gòu)比如圖表[Hilaga et al. 2001; Chenand Ouhyoung 2002; Sundar et al. 2003]?；趫D的表示法促進了含有相同拓撲結(jié)構(gòu)的從屬部分進行局部匹配。</p><p>　　作者給出了基于兩個模型圖形描述元之間的平方距離總和的三維匹配方法。這種方法還允許模型不同部分的各種權(quán)重（重要）使用原始模型的形狀描述符，從而使得整體的一

18、部分匹配。這種方法依賴于在三維中模型的排列會讓匹配的部分相互靠近的假設(shè)。</p><p>　　一種部分—整體的匹配方法在恒等變換中可以被看成部分匹配。對于一般的部分匹配，我們會傾向于在任意剛體運動變換或者有時候在標(biāo)尺變換中匹配部分。我們也可以考慮更大范圍的變換，比如仿射和透視變換。在本文中，我們創(chuàng)造了一種局部匹配方法，它可以支持被稱為相似性變幻的剛性變換和等分標(biāo)度。我們的方法不會全局匹配圖形，一個會取消匹配可能性

19、的因素，比如一個有很大基座的雕像的手和沒有幾座的雕像的手，這是不會影響匹配的。</p><p>　　在對由深度掃描得到的深度圖像而構(gòu)成的三維物體進行識別和標(biāo)記中，局部匹配是基礎(chǔ)方法[Frome et al. 2004]。在這些應(yīng)用中的查詢時總是視點相關(guān)和分辨率相關(guān)的。通常情況下，這些技術(shù)是基于匹配局部描述符的，就比如旋轉(zhuǎn)圖像和圖形上下文[Johnson and Hebert 1999; Huber et al.

20、2004]。不像那些描述符，在我們的研究中所創(chuàng)造的平面描述符是與比例不相關(guān)的，而且就他們被構(gòu)建的能高效率的去盡可能大的表示網(wǎng)格區(qū)域的意義而言，他們是能適應(yīng)的。我們會在第九部分更深度詳細的說明這些方法。</p><p>　　關(guān)于圖像空間的“興趣”點或者說突出特征進行抽取已經(jīng)被廣泛的研究了[Marr 1982]。對有興趣的表面特征或者突出特征的定義使我們研究的重點。正如我們下面說明的，我們對有趣部分的定義是主要基于表

21、面的曲率。Shum et al. [1996]認識到了表面曲率作為一種三維圖像匹配方法的重要性（請查閱Zaharia and Preteux [2001]）。</p><p><b>　　2.1突出幾何特征</b></p><p>　　人類感知和識別與描述圖形的能力已經(jīng)是一個被廣泛研究的課題。事實上，這不只是一個任務(wù)，而是很多個：顏色，陰影，構(gòu)圖，運動，材質(zhì)和上下文都

22、在研究過程中經(jīng)常被用到，這還是在不考慮文化背景和人際交往的情況下。在計算機圖形學(xué)和建模中一個中心問題就是對“圖形”這個概念的理解。我們在這里使用了圖形的常規(guī)定義，這個定義在Dryden and Mardia [1998]：“當(dāng)位置，比例尺與旋轉(zhuǎn)效果從物體過濾掉后留下來的所有幾何信息”。</p><p>　　通過描述圖像的一部分來描述圖形會幫助人類視覺對圖形的識別這一觀點是被廣泛認同的[Hebb 1949]。在二維

23、情況下，它會幫助解決遮擋問題，在三維情況下，有助于處理非剛性的個體。一個關(guān)鍵性的問題是“哪一部分可以代表？”在我們的研究中，我們是這樣定義的，按照計算規(guī)則，一個物體的突出特征應(yīng)該是封裝了這個物體的性質(zhì)從而可用于第一條索引[Hoffman and Singh 1997]。通過“部分的突出”這個詞，我們想表達的是我們致力于通過物體的少數(shù)的部分來得到物體的圖形。他們的突出特征在某種程度上項索引一樣有效。</p><p>

24、;　　我們的方法是建立在Hoffman and Singh提出的視覺部分的突出性理論上的。按照他們的理論，一個部分的突出性是它跟整個物體相關(guān)聯(lián)的尺寸，對于整個物體的突出程度，邊界線的明顯程度三個變量的函數(shù)。在這篇文章中，我們致力于發(fā)現(xiàn)一種定量的表示來讓這些方法可以直接用于網(wǎng)格。這個的重點在于計算邊界線的明顯程度。我們認為它是曲率值的函數(shù)。我們認為部分突出性取決于至少兩個因素：跟整體相關(guān)的尺寸，曲率的變化和強度的數(shù)量。在第五部分中我們說明

25、了定義突出幾何特征的計算方法。</p><p>　　圖 2。匹配不同姿勢的男人模型和女人模型。盡管他們之間有著明顯的區(qū)別，但是我們算法的匹配結(jié)果（左下）比全局PCA校準(zhǔn)的結(jié)果（右下）要更好。</p><p><b>　　綜述</b></p><p>　　給定一個三維網(wǎng)格，我們分析它的幾何特性并且定義一個局部圖形描述符的網(wǎng)格化稀疏矩陣。然后我們從

26、網(wǎng)格中提取出感興趣的和突出特征部分。將這些特征做好索引并且存儲在一個模型數(shù)據(jù)庫中，這樣就可以被局部匹配很容易的檢索到。對子部分進行匹配要將他們放在同一種坐標(biāo)系中。一種比較天真的實現(xiàn)方法是將所有的模型存儲在由各自的頂點和相鄰模型定義的所有可能的坐標(biāo)系中。然后對于一個給定的查詢，我們會嘗試所有由查詢體的頂點定義的方向和比例。這種方法會導(dǎo)致組合爆炸式的嘗試，而這遠遠超出了我們的計算能力，特別是對于那些包含了數(shù)千個甚至更多頂點的模型。</

27、p><p>　　為了解決這些組合障礙，我們提出了以下的方法：</p><p>　　采用圖形描述符的稀疏集來表示給定的網(wǎng)格。每個描述符代表一個有很好二次匹配的局部區(qū)域。</p><p>　　定義一個突出幾何特征的小集合并且做好索引。這些突出特征代表了給定圖形的感興趣的部分。</p><p>　　預(yù)計算一個在旋轉(zhuǎn)和比例變換中能進行快速的局部匹配的幾何

28、哈希表。</p><p>　　在第4-6部分我們描述了一些方法，這些方法可以：</p><p><b>　　分析模型的表面；</b></p><p>　　定義局部圖形描述符；</p><p>　　定義突出幾何特征并且存儲索引向量；</p><p>　　通過使用索引和幾何哈希來查詢模型數(shù)據(jù)庫進行局部

29、匹配。、</p><p>　　然后在第七部分我們討論了我們的方法的表現(xiàn)。在第八部分我們給出了一些基于我們的局部匹配算法的應(yīng)用和結(jié)果。在第九部分我們闡明了我們的幾何哈希法和直方圖法的聯(lián)系，最后我們在第十部分進行了總結(jié)并且展望了未來的工作。</p><p>　　在介紹之前，我們看一下圖3，它展現(xiàn)了局部匹配的本質(zhì)。圖3給出了模型a和b中三個部分的匹配?？梢宰⒁獾竭@兩個模型只有很少部分能真正的匹配

30、。這個例子強調(diào)了局部匹配不只是給定模型的子部分匹配，而且相匹配的部分不是預(yù)先定義的。</p><p><b>　　局部表面描述符</b></p><p>　　局部表面描述符是表面上的一個點P，它與跟p相鄰的接近于表面的二次曲面補丁相關(guān)聯(lián)。關(guān)鍵點在于描述符的小集合可以表示一個圖形，如果每個描述符可以有效的表示它周圍的局部表面。這種表示也適用于圖形的幾何特性。平滑的區(qū)域被

31、少數(shù)相關(guān)聯(lián)的描述符表示，因為每個二次補丁可以在局部近似于一個大的區(qū)域。稍微不平滑的區(qū)域則需要更大數(shù)量的相關(guān)的描述符來表示。在圖5中可以看出在吸盤和更平滑的區(qū)域的描述符的密度。作為一個分析局部表面的方法，我們將曲率值與每個描述符相聯(lián)系。在下文中，我們介紹了二次適應(yīng)策略和構(gòu)建有效描述符集合的算法。</p><p>　　圖 3。局部匹配。鷹模型（b）的三個部分被疊加在進行了標(biāo)高變形的框架上。這三個副本有著不同的尺寸和方

32、向。這只鷹的三個部分通過應(yīng)用局部匹配與完整的鷹模型相匹配（c）-（e）。注意到被匹配的一對的重疊只是部分的。該匹配是通過將局部形狀描述符三元組對變換成一個共同的坐標(biāo)系來實現(xiàn)的。這里采用黃色來表示局部的形狀描述符。</p><p>　　4.1二次適應(yīng)與曲率估計</p><p>　　按照Douros and Buxton [2002]提出的方法，通過一個解析的可以很好地近似于表面的二次補丁，這

33、個表面可以局部地近似于每個頂點。對于每個二次補丁，一個代表性的點會被選擇并且這個補丁在這一點的不同特性會被解析計算。</p><p>　　對于一個隱式曲面F(x, y, z) = 0,我們使用一個有九個因子的二次補丁。這樣一個表面的適配是很容易去表達為可以當(dāng)作特征問題來解決的最小二乘法。這樣就可以允許這個方法不用考慮下墊面的方向從而用于三維中任何一種類型的點云。</p><p>　　對于每

34、個網(wǎng)格的頂點v，我們給定一個隱式曲面，它在這個隱式曲面上的投影我們定義為v’，在v點的曲率張量和曲率派生通過在v’點的解析計算來估計[Ohtake et al. 2004]。為了增強魯棒性，我們測試了一系列在每個頂點的相鄰尺寸，而且選擇了具有中等曲率的二次補丁。雖然有更快的技術(shù)去估算離散曲率[Alliez et al. 2003; Rusinkiewicz 2004]，但是由于這些曲率計算是離線的，我們實現(xiàn)了一種更具魯棒性的二次適應(yīng)技術(shù)

35、。圖4給出了局部二次適應(yīng)和曲率估計示意圖。</p><p><b>　　4.2緊湊表示法</b></p><p>　　為了產(chǎn)生一種既有效也比較小的局部表面描述符集，我們定義了一種局部表面補丁并將它跟表示這個補丁的描述符聯(lián)系起來。我們運用區(qū)域增長技術(shù)來迭代定義這些局部補丁。我們根據(jù)這些網(wǎng)格頂點的絕對高斯曲率來將它們進行降序排列，而且對于每一個頂點，我們擴展一個最有可能的

36、二次補丁來適應(yīng)它的相鄰點。所有在局部補丁中的頂點都會被這個排列中除去，而且這個迭代過程會繼續(xù)頂一下一個補丁。在每一步中我們在被選中的能夠觸及規(guī)定的錯誤閾值的頂點的周圍定義了最可能區(qū)域，在這方面，我們算法是貪婪的。我們在所有這些例子中使用了每個模型邊界框?qū)蔷€長度的0.1%。我們利用適應(yīng)表面的適應(yīng)點的代數(shù)距離的平方和來計算二次適應(yīng)的值。代數(shù)距離比歐幾里德記錄更容易判定盡管它沒那么有魯棒性但確實是一種定量的有效方法。</p>

37、<p>　　當(dāng)一個補丁被定義了，我們在它的集合中選擇一個代表性的點，并且將這個點與補丁中的最高曲率相關(guān)聯(lián)。圖5展示了在章魚觸角模型上的結(jié)果。還記得局部表面描述符的主要目標(biāo)是定義一個獨立于給定模型的曲面圖的表示方法。因此，我們隨機（不均勻地）抽樣了一些表面，然后利用這些樣本來進行二次適應(yīng)。圖6給出了兩個不同細分曲面的曲率計算例子。我們可以發(fā)現(xiàn)不同細分曲面曲率示意圖和局部表面描述符的分布是相似的。</p><p

38、>　　圖 4。二次適應(yīng)的例子。紅色的點是由主軸線（綠色）定義的網(wǎng)格上的小樣本。這個網(wǎng)格是根據(jù)高斯曲率的不同來配色的。</p><p>　　圖 5。章魚模型上觸角的吸盤。（a）粗體的原始花紋與二次補丁。（b）局部描述符在黃色點位置?？梢宰⒁獾剿麄兊姆植济芏仁桥c表面形狀相適應(yīng)的。</p><p><b>　　計算突出幾何特征</b></p><p

39、>　　嚴格意義上，一個突出的幾何特征是其具有一個非平凡形狀的表面的區(qū)域。我們通過聚集一組描述符是足夠有趣的是，在這個意義上，它們具有相對于它們的環(huán)境中高曲率的突出幾何特征，并具有高方差曲率值。的突出幾何特征是一個自由參數(shù)h、規(guī)模的函數(shù)，這由球體邊界的顯著特征的半徑限定。</p><p>　　對于每個描述符中，我們通過從它的區(qū)域逐漸增加生長圍繞它的描述符的一個描述符集，以最大限度地提高當(dāng)前的顯著性級，這將簡單

40、地定義。當(dāng)額外描述符的貢獻是微不足道的時候該過程停止。我們對所有的描述符執(zhí)行此過程，同時允許一定程度的集之間的重疊（在我們的實現(xiàn)中，我們允許高達20％的重疊）。</p><p>　　集F的顯著性級由d ∈ F描述符組成，它是一個有以下4個方面功能的函數(shù)：</p><p>　　Area(d)，其中，區(qū)域（d）是具有相對于球體大小為d相關(guān)聯(lián)的補丁的面積;</p><p>

41、;　　Curv(d)，其中，曲率d 是跟d關(guān)聯(lián)的曲率；</p><p>　　N(F) ——在集中局部最小（S）或最大（多個）的曲率的個數(shù)；與</p><p>　　Var（F）——在集中曲率的變化。</p><p>　　顯著性級S可以定義為這四個方面的線性組合。然而，憑借經(jīng)驗我們發(fā)現(xiàn)以下表達式更有效：</p><p>　　S =d∈FW1 Ar

42、ea(d)Curv(d)3 + W2 N(F)Var(F).</p><p><b>　　（1）</b></p><p>　　第一項Area(d)Curv(d)3通過結(jié)合其相對大小和曲率表示該區(qū)域的突出性。Curv(d)可以是高斯曲率或最大曲率分量。圖7顯示了泰國女性雕像的兩個曲率示意圖，完全沒有顯著差異。需要注意的是在有大面積與CAD模型零高斯曲率的情況下一個最大的

43、曲率可以是一個更好的選擇。如圖8所示，第二項N(F)Var(F)表示群集的興趣度的程度，并增加了對群集的突出性。我們對W1和W2使用0.5的權(quán)重。突出的部分的定義對用于定義它們的啟發(fā)式的方法不是太敏感，因為我們對某些特定部分不感興趣，而是對產(chǎn)生了若干的能很好地表征該模型的突出特征感興趣（參見圖9）。應(yīng)當(dāng)強調(diào)的是，在本文中使用的公式（1）中所使用的常量不需要人工調(diào)整，以及所有的實施例和實驗使用相同的表達式。</p><

44、p>　　換句話說，我們定義一個模型的區(qū)域突出幾何特征與模型的其他部分相比是突出而且有趣的。頂級群集定義了給定形狀的突出幾何特征。突出幾何特征的一些結(jié)果示于圖9中，我們只提取最顯著的特征，而不是那些等級中的前10％或那些符合一些預(yù)定的閾值的特征。</p><p>　　圖 6。由相同模型的不同紋路計算得到的曲率分布圖。藍色是低曲率部分，紅色是高曲率部分。</p><p>　　圖 7。通過

45、泰國模型的三個女人雕像進行的曲率分析。這幅圖像是用高斯曲率得到的結(jié)果（左）與最大的曲率（右）。其中較小的差異顯示了突出集合特征的定義對分析是很敏感的因素。</p><p>　　圖 8。左圖顯示了由曲率配色的局部表面描述符。在右圖中，顯著性等級從藍色到綠色表明。補丁是由包含它的突出集合特征的顯著性等級來配色的。</p><p><b>　　索引化與幾何哈希法</b>&l

46、t;/p><p>　　該模型具有代表性的突出特征的定義和線下提取并存儲在轉(zhuǎn)動和尺度不變的數(shù)據(jù)庫。各突出特征都與一個矢量索引（簽名）相關(guān)聯(lián)，并插入一個幾何哈希表。索引向量被用作幾何簽名，它允許快速訪問具有一般相似的形狀的部件。為了有效率，我們使用轉(zhuǎn)動和尺度不變的幾何簽名。然而，單獨的簽名是不足以辨別的，而且不能提供匹配他們實際的轉(zhuǎn)型。通過采用幾何哈希[Lamdan and Wolfson1988]最匹配的形狀的顯式變換

47、被確定。</p><p>　　在我們的實現(xiàn)中，我們使用了如公式1表示的四種形式用來定義顯著性級，作為相似性不變矢量索引。要知道其他闡述指數(shù)，如歸一化的時刻，也是可以使用的。但是，實現(xiàn)使用突出項索引加強了我們?yōu)轱@著特征的效率要求。</p><p>　　我們使用幾何哈希從模型數(shù)據(jù)庫加速部分匹配的檢索。簡單地說，幾何哈希是一種在剛體變換和可能統(tǒng)一縮放的情況下加速部分匹配的機制。該方法從一大套的變

48、換由投票方案來確定最好的改造。該方法將該轉(zhuǎn)換空間量化成6維表。給定兩個對象A和B，對A點和B點上三元組，三元組之間的變換是=通過計算和表決被記錄在表中的相應(yīng)的單元。得票最多的條目定義匹配變換。為了避免對所有的窮舉搜索，幾何哈希將線下編碼所有在一個大的哈希表的候補變換，這樣一來，給定尺寸的查詢模型時|Q|，不管多少模型被編碼在哈希表中，需要查詢哈希表僅用于的變換。在預(yù)先計算的哈希表除去搜索在每個模型三元組。</p><

49、p>　　圖 9 。通過分析表面自動定義了突出集合特征（橙色）。單獨的個體是紅色的。</p><p>　　在我們的實現(xiàn)中，我們使用的突出幾何特征作為對象和局部表面描述符作為用于定義在哈希表中的三元組和得票點。哈希表中包含數(shù)據(jù)庫中的所有模型的所有突出幾何特征。通常情況下，每一個突出特征是由約20-30個局部表面描述符組成。我們定義候選轉(zhuǎn)換從一個小鄰域內(nèi)取點的三元組之間（最多兩個環(huán)），因此通常需要對準(zhǔn)測試的數(shù)量以

50、|Q|為順序，而不是。</p><p>　　表 1 大模型和小模型的一些數(shù)據(jù)</p><p>　　通過組合索引和幾何哈希，我們成功在查詢和存儲在散列表中的顯著特征之間找到局部匹配。該指數(shù)是用來在投票階段，迅速否決突出特征。如下所述，匹配給定的兩個顯著特征的轉(zhuǎn)化是關(guān)于各種匹配和相似性應(yīng)用程序的基礎(chǔ)。</p><p><b>　　考慮時間與存儲因素</b

51、></p><p>　　我們所提出的方法使執(zhí)行大多數(shù)在離線模式下所必需的部分匹配的工作可行，允許快速查詢時間。表I顯示出了我們的預(yù)處理步驟中所需的時間和存儲空間的例子。</p><p>　　在核心部分，部分匹配問題需要大量的計算進行搜索和比較。我們使用了相當(dāng)耗時的表面分析來創(chuàng)建一個稀疏和自適應(yīng)組描述符。為了索引我們的構(gòu)造顯著的幾何特征，我們使用幾何哈希。索引幾何哈希的主要優(yōu)點是它允許

52、對于我們的應(yīng)用是重要的一個尺度獨立機制。在簡單的情況下，如果沒有規(guī)模是必要的，可以考慮實施的其它方法用于索引的突出幾何特征，如旋轉(zhuǎn)圖像和形狀上下文[Johnson and Hebert 1999; Huber et al. 2004]。</p><p>　　某些應(yīng)用程序或方案可能需要一個更有效的預(yù)處理過程。正如我們上面提到的，有估計離散曲率和二次系數(shù)[Petitjean 2002; Alliez et al. 2

53、003; Rusinkiewicz 2004]。這些方法可以加快離散曲率估計的優(yōu)質(zhì)模型，但對于不規(guī)則鑲嵌模型不太可靠。</p><p>　　此外，還有關(guān)于無論是在時間和空間上，如何提高幾何散列的效率的很多工作需要完成。[Wolfson and Rigoutsos 1997]。</p><p><b>　　應(yīng)用與結(jié)果</b></p><p>　　

54、部分匹配，在一般情況下，是作為各種幾何應(yīng)用的基本工具。特別地，對許多應(yīng)用進行表面處理。我們在這里描述的三個應(yīng)用程序，到目前為止我們已經(jīng)嘗試了：自相似性，形狀排列，和分部檢索。</p><p>　　圖 10。自相似性。章魚模型的除腳上吸盤有相似的形狀。但是它們的尺寸在模型中是變化的。</p><p>　　圖 11。大象（左上）的對稱性分析。三只大象的相似區(qū)域被據(jù)檢測到了并且配色。</p

55、><p><b>　　8.1自相似性</b></p><p>　　圖10給出了尋找自相似的結(jié)果。表面通過識別一個普通的特征對該表面特征進行分析。我們的想法是自動識別具有許多在給定的表面發(fā)生類似情況的突出特征。在此圖中，對章魚模型的觸手吸盤進行標(biāo)識（見圖5這些吸盤的近景）。我們注意到，該吸盤具有相對大的多種尺寸。圖1是另一種自相似性應(yīng)用程序的結(jié)果，通過它我們了解到四蓮花佛模

56、型的存在，表1表明申請查詢佛和章魚模型的一些統(tǒng)計數(shù)據(jù)比另外兩個兩個較小的模型要大。</p><p>　　在上述例子中，在旋轉(zhuǎn)和均勻尺度變換的情況下所有的顯著特征的副本都被搜索了。該算法第首先對給定表面的突出特征進行排序，然后，對于每k個具有最大突出度等級的突出特征，我們進行搜索來局部匹配。圖11顯示了應(yīng)用于從斯坦福3D掃描庫泰雕像的巨大模型的一部分的自相似性分析。圖12所示，該模型中由10M個多邊形組成，這超出了

57、我們的系統(tǒng)的容量。在我們的實驗中，我們處理的僅僅是它的一部分：圖7中所示的三個女子，和圖12的三個象。這個雕像具有粗糙的三通對稱性，但手工雕像的三個部分并不匹配，因為他們是不完美的副本。我們應(yīng)用我們的自相似性分析并且對于每個匹配我們逐漸增長區(qū)域從而形成兼容部分。只要它們匹配到一些誤差容限區(qū)域就會增長。這種三通對稱性分析的結(jié)果示于圖11。</p><p>　　圖 12。斯坦福大學(xué)三維掃描倉庫的泰國雕像。這個模型由1

58、0M個多邊形組成，有著粗糙的三通對稱性。</p><p><b>　　8.2 形狀校準(zhǔn)</b></p><p>　　大多數(shù)的全局匹配方法首先確定一個剛體變換和均勻的規(guī)模，這就在測量它們之間的距離之前讓兩個模型盡可能接近。這通常是通過主要成分分析（PCA）施加到整個模型來實現(xiàn)的。當(dāng)形狀圖形不匹配甚至在一個明顯的鏡像區(qū)域時，這樣的全局分析是容易出錯的。圖2顯示了一個男人和

59、一個女人之間的模型的校準(zhǔn)。該實例表明，雖然兩種模式都在它們的幾何形狀和姿勢明顯的差異，通過其突出的幾何特征部分匹配，是可以將他們匹配的部分校準(zhǔn)的。</p><p>　　圖13顯示了另一個例子，其中相同的模型出現(xiàn)在兩個不同的姿勢。后者的例子強調(diào)，全局的PCA無法正確校準(zhǔn)它們，而部分匹配可以盡可能的校準(zhǔn)。我們的對準(zhǔn)是基于發(fā)現(xiàn)滿足大多數(shù)的突出特征變化大多數(shù)方案。</p><p>　　我們的定位算

60、法首先搜索各個模型突出特征之間的匹配。然后為每個這樣的匹配，相關(guān)的變換得到了一個級數(shù)，它反映了突出特征成功校準(zhǔn)的數(shù)量。最成功的變換是得票的，并應(yīng)用于把兩個給定的模型盡可能地接近。得票的變換定義兩個模型之間的對應(yīng)關(guān)系。一旦這一對定義，相應(yīng)的特征可以在最小二乘意義上更加接近。</p><p>　　圖 13。基于PCA（右）和局部匹配（左）的模型校準(zhǔn)。</p><p>　　圖 14?？蚣苄螤顧z索

61、的概述。給定模型的數(shù)據(jù)庫（a），我們分析每個模型的幾何性質(zhì)和定義其目的稀疏表示與局部形狀描述符（b）。然后，我們從每個模型（C）提取有趣和突出的幾何特征，這些特征被索引并存儲在可被有效地用于查詢部分匹配的模型數(shù)據(jù)庫中（d）。上述步驟可離線進行。當(dāng)網(wǎng)上給出的查詢模式（E），我們以同樣的方式分析它，確定局部表面描述符（f）和突出幾何特征（g）。對于每一個突出幾何特征，我們查詢模型數(shù)據(jù)庫的匹配特征的列表（h）。通過這些匹配，我們得到有較大的匹

62、配模型（i）。</p><p><b>　　8.3局部形狀檢索</b></p><p>　　局部形狀檢索允許這可能是不相似于較大形狀的子部分被查詢檢索到。我們的部分形狀檢索的框架概述示于圖14。</p><p>　　圖15示出檢索人的手的一個例子。這種機制對例子進行有效的建模至關(guān)重要[Funkhouser et al. 2004]，因為它在一個

63、較大的不同形狀的一部分旋轉(zhuǎn)和均勻縮放轉(zhuǎn)換發(fā)現(xiàn)相似的形狀。例如，看圖16，其中該查詢是植物。檢索到的模型不一定是全局相似（例如，一些植物高大一些短而寬），但他們有足夠的部分相似之處。注意，圖16不是最佳的匹配，而是在前72個匹配中的前5個樣本。</p><p>　　有趣的結(jié)果顯示于圖3和圖17，這是不能由全局匹配技術(shù)來實現(xiàn)。在圖17中的兩個例子表明了檢索形狀的語義是與查詢對象不同的情況;然而，子部件的幾何形狀與查詢

64、對象的幾何形狀類似。</p><p>　　為了評估我們的局部匹配方法的表現(xiàn)，我們給普林斯頓形狀基準(zhǔn)（PSB）模型數(shù)據(jù)庫提交了報告[Shilane et al.2004]。我們只用自然的模型，其中包括如人手，人腳，人臉，動物四肢等不同種類，表二顯示了我們的結(jié)果概要通過利用[Shilane et al. 2004]：</p><p>　　最近的鄰居：相同等級的查詢的最靠近的百分比；</p

65、><p>　　第一層與第二層：模型中的查詢的類出現(xiàn)的前k個匹配中的百分比，其中K取決于查詢類的大?。慌c</p><p>　　電子測量：精度和召回檢索結(jié)果固定數(shù)量的綜合衡量。</p><p>　　Figure 15。粗糙人手（a）的成功匹配實例（（b）和（c））與兩個假陽性匹配（d）和（e）。</p><p>　　Figure 16。用設(shè)備模型的查

66、詢得到的相似性檢索的結(jié)果。檢索到的模型不一定是全局相似，但包含部分相似之處。注意，該圖中不是顯示8個最佳匹配，而是在前72個匹配中的前5個樣本。</p><p>　　更多的區(qū)分方法請查閱Shilane et al. [2004]。</p><p>　　Figure 17． 局部匹配。潛水艇（黃色部分）與企業(yè)號（左）的兩個部分和城堡（右）的四座塔相匹配。</p><p&g

67、t;　　表 2 對PSBD實驗的概要與精度召回測量</p><p>　　我們的實驗在有2 GB的內(nèi)存P4-3.0 GHz上進行。我們所用的“顯著性等級”（公式（1））作為指標(biāo)。然而，應(yīng)該強調(diào)的是，大多數(shù)的模型中對PSB數(shù)據(jù)庫具有粗糙三角劃分（參見圖15的（a））。在這種情況下，顯著性等級太粗糙，并且可針對類似粗糙的形狀有很大不同。為了避免這種情況，對粗糙模型，我們直接使用幾何哈希表中的局部表面描述符。然而，相對于

68、全局匹配我們的精密召回成績是相當(dāng)不錯 [Shilane et al. 2004]。應(yīng)當(dāng)指出，許多的成功依賴于類別的定義。例如，人的手被很好的定義，而其他類別，像動物肢體或人臉，更難定義。</p><p><b>　　基于直方圖的描述符</b></p><p>　　在對由深度掃描得到的深度圖像而構(gòu)成的三維物體進行識別和標(biāo)記中，局部匹配是基礎(chǔ)方法[Johnson and

69、Hebert 1999; Huber and Hebert 2003;Frome et al. 2004]。在這些應(yīng)用中，查詢場景通常與視圖依賴性和分辨率有關(guān)，而且數(shù)據(jù)往往是有噪聲和不完整的。</p><p>　　圖 18。星型圖案上計算旋轉(zhuǎn)的不同規(guī)模的類似形狀的圖像。該圖顯示，在對其中人類感知不同規(guī)模的相似的形狀位置4旋轉(zhuǎn)圖像?？梢钥闯龅氖?，雖然自旋圖像是相似的，當(dāng)上計算的形狀具有類似的規(guī)模（左圖），它們是不同

70、的不同規(guī)模（右圖）的類似的形狀。</p><p>　　用純粹的局部描述符處理部分匹配，如表面曲率，在噪音的存在下不太穩(wěn)定。因此，穩(wěn)定點的描述依靠局部區(qū)域的支持。例如，旋轉(zhuǎn)圖像[Johnson and Hebert 1999]和形狀上下文[Frome et al. 2004]因為給出了給定的點的局部鄰域的公知的量化表示而被人們熟知。</p><p>　　這些描述符作為輸入的點云P和一個基礎(chǔ)點

71、p，以及使用點的分布在周圍的頁記載的小支撐捕捉場景的區(qū)域形狀為p。支撐區(qū)域被離散成小方塊，一個直方圖表示包含在每個方塊內(nèi)的點的數(shù)量。這些直方圖，可直接使用作為局部描述符，或可通過附加的變換，如球形諧波表示進一步增強。</p><p>　　這些局部描述符可以作為我們局部表面描述符的替代者。然而，這些描述符不會擴展不變，他們不是適應(yīng)的幾何形狀，我們將在下面解釋。</p><p>　　圖 19。

72、在規(guī)模1.0在不同尺度計算大約在同一分自旋圖像和自旋圖像之間的L2距離。該圖顯示了旋圖像簽名規(guī)模的靈敏度。</p><p>　　以直方圖為基礎(chǔ)的描述[Johnson and Hebert 1999; Huber and Hebert 2003; Frome et al.2004]不是比例不變的。例如，在圖18中，我們給出了4張自旋圖像在被人類感知為有相似比例的相似圖形的位置?？梢钥闯龅氖?，雖然自旋圖像是相似以上形

73、狀具有類似比例（左圖片），它們是不同比例（右側(cè)圖像）的類似的形狀。旋圖像的敏感性刻度顯示在圖19中。在應(yīng)用中，一些比例標(biāo)準(zhǔn)化是不適用的，因為匹配實例不是先驗已知的。</p><p>　　圖 20．星星模型（a）由18個三種不同的尺度星星組成。一個中等規(guī)模的星星作為查詢。使用旋圖像和我們的方法的結(jié)果分別顯示于（b）和（c）中，這個例子說明了一個事實，我們的方法是尺度獨立的。</p><p>

74、　　在我們的方法中，我們使用幾何哈希匹配突出特征。這本質(zhì)上是一個尺度不變的方法，如可在圖3和圖20，可以看出為了說明自旋圖像描述符之間的差，在我們的描述中，我們采用的自旋圖像描述符不同的設(shè)置。我們將在表面的自旋數(shù)的圖像分布開，并為每個自旋圖像描述符計算其最佳的匹配，而不是一個單一的匹配。然后，我們采用了投票策略，通過計算獲取最相應(yīng)的描述符之間的匹配的轉(zhuǎn)換（見圖20）。</p><p>　　圖 21．該圖顯示了描述

75、符的數(shù)目和正確匹配的數(shù)目之間的權(quán)衡。可以看出，我們的方法只需要少量的描述符，從而成功地找到所有的部分匹配。</p><p>　　另一個有趣的問題是效率和匹配的保真度之間的權(quán)衡。一個密集旋轉(zhuǎn)圖像很可能不會錯過最佳匹配。然而，越詳盡的方法將是越消耗資源的。在我們的方法中，一組描述符的稀疏集通過相對于所定義的表面分析，如第4部分所述圖21顯示出描述符的數(shù)目和正確匹配的數(shù)量之間的折衷?？梢钥闯觯覀兊姆椒ㄖ恍枰倭康拿枋?/p>

76、符，從而成功地找到所有的局部匹配。</p><p>　　圖 22。四個登記合成掃描。每次掃描的表面都具有封閉在一個正常的錐體法線。用我們的方法發(fā)現(xiàn)了重疊區(qū)域的匹配。</p><p>　　應(yīng)當(dāng)注意的是，在我們的方法中，要求的表面的分析描述符的選擇是耗時的，也是通過離線計算的。不同于以直方圖為基礎(chǔ)的技術(shù)，我們耗費計算時間來創(chuàng)建一個具有良好的辨別力的稀疏和自適應(yīng)組描述符。</p>

77、<p>　　總結(jié)與未來工作的展望</p><p>　　在這篇文章中，我們已經(jīng)描述了三角形網(wǎng)格的局部匹配的方法。該方法概括為形狀檢索開發(fā)的最近全局幾何匹配技術(shù)。我們所使用的方法是基于表面的分析，定義一組稀疏的局部表面描述符去捕獲原始網(wǎng)格的幾何形狀的本質(zhì)。描述符的稀疏性允許我們處理復(fù)雜的網(wǎng)格，和沒有顯著細節(jié)的大區(qū)域。我們的方法是專門用來處理細網(wǎng)格，因為它采用離散表示分析了表面曲率。當(dāng)網(wǎng)格比較粗糙，局部曲率太

78、粗糙而不能傳達顯重要的信息進行分析。當(dāng)局部描述符的保真度，也就是突出特征的效率，直接取決于網(wǎng)格的質(zhì)量和曲率分析。我們相信，這兩個地方的表面描述符和突出特征對網(wǎng)格處理發(fā)揮著相當(dāng)重要的作用，要進行更多的研究，肯定需要研究其他方法。</p><p>　　當(dāng)局部描述符是一組無連接點。這允許我們處理非流型物體或點集。然而，要研究局部匹配到點匹配的擴展，更多的工作是需要做的。</p><p>　　圖

79、23．通過稀疏樣本的模型自身復(fù)制匹配部件來重構(gòu)CAD模型的一部分。</p><p>　　我們已經(jīng)提出了許多基于表面的局部匹配的應(yīng)用程序。然而，這些都是我們已經(jīng)試驗的應(yīng)用;另外，我們希望尋求其他可能的方向：</p><p>　　表面登記。兩片表面局部匹配是登記和兩個表面拼接成一個連貫的較大的表面的一個重要步驟。這可以適用于深度掃描儀和一個由多位掃描重建的完整形狀。圖22顯示了使用我們的方法的

80、四次對龍的掃描而形成一個連貫的形狀的龍模型的合成實例。需要注意的是表面登記方案通常不需要尺度不變匹配，所以更簡單的索引方法可以考慮，這樣可以減少幾何哈希的預(yù)處理時間。</p><p>　　表面重建。另一個應(yīng)用從稀疏和噪聲的樣品表面的重建。圖23示出了一塊CAD模型的由從給定的模型自身復(fù)制匹配部件棋盤采樣區(qū)域重建。</p><p>　　表面風(fēng)格。兩個表面，其可以是全局相異，可以共享類似密切相

81、關(guān)的幾何特征。這個形狀的樣式可通過其幾何特征的自相似性被定義。這可能會導(dǎo)致基于共同特征的分類處理。</p><p>　　對象對應(yīng)。應(yīng)用的一個重要的擴展是，如我們已經(jīng)表明的，定義交叉網(wǎng)眼部分的對應(yīng)關(guān)系。特性的對應(yīng)關(guān)系也可以考慮的特征的幾何位置來定義多個全局相似性量度。對應(yīng)，在一般情況下，可以適用于許多應(yīng)用，例如，對象空間變形。</p><p><b>　　致謝</b>&

82、lt;/p><p>　　我們感謝帕特里克閔珍貴的意見。感謝斯坦福大學(xué)提供的快活佛和泰國雕像，與馬克·保利提供的章魚圖像。</p><p><b>　　參考文獻：</b></p><p>　　ALLIEZ, P., COHEN-STEINER, D., DEVILLERS, O., LEVY, B., AND DESBRUN, M. 200

83、3. Anisotropic polygonal remeshing. ACM Trans.</p><p>　　Graph. 22, 3, 485–493.</p><p>　　CHEN, D.-Y. AND OUHYOUNG, M. 2002. A 3D object retrieval system based on multi-resolution REEB graph. In P

84、roceedings of</p><p>　　the Computer Graphics Workshop (Taiwan). 16–20.</p><p>　　CYBENKO, G., BHASIN, A., AND COHEN, K. D. 1997. Pattern recognition of 3D CAD objects. Smart Eng. Syst. Des. 1, 1–

85、13.</p><p>　　DOUROS, I. AND BUXTON, B. F. 2002. Three-dimensional surface curvature estimation using quadric surface patches. Proceedings</p><p>　　of Scanning 2002.</p><p>　　DRYDEN,

86、 I. AND MARDIA, K. 1998. Statistical Shape Analysis. John Wiley and Sons.</p><p>　　ELAD, M., TAL, A., AND AR, S. 2001. Content based retrieval of VRML objects: An iterative and interactive approach. In</p

87、><p>　　Proceedings of the Sixth Eurographics Workshop on Multimedia 2001. Springer-Verlag New York, NY, 107–118.</p><p>　　FROME, A., HUBER, D., KOLLURI, R., BULOW, T., AND MALIK, J. 2004. Recognizi

88、ng objects in range data using regional point</p><p>　　descriptors. In Proceedings of the European Conference on Computer Vision (ECCV).</p><p>　　FUNKHOUSER, T., KAZHDAN, M., SHILANE, P., MIN, P

89、., KIEFER, W., TAL, A., RUSINKIEWICZ, S., AND DOBKIN, D. 2004. Modeling by</p><p>　　Example . ACM Trans. Graph. 23, 3, 652–663.</p><p>　　FUNKHOUSER, T., MIN, P., KAZHDAN, M., CHEN, J., HALDERMAN

90、, A., DOBKIN, D., AND JACOBS, D. 2003. A search engine for 3D models. ACM Trans. Graph. 22, 1, 83–105.</p><p>　　HEBB, D. O. 1949. The Organization of Behavior. John Wiley, New York, NY.</p><p>　

91、　HILAGA, M., SHINAGAWA, Y., KOHMURA, T., AND KUNII, T. L. 2001. Topology matching for fully automatic similarity estimation of</p><p>　　3D shapes. In Proceedings of SIGGRAPH 2001 (Los Angeles, CA). 203–212.&

92、lt;/p><p>　　HOFFMAN, D. D. AND SINGH, M. 1997. Salience of visual parts. In Cognition 63, 1, 29–78.</p><p>　　HUBER, D. AND HEBERT, M. 2003. Fully automatic registration of multiple 3D data sets. Im

93、age Vis. Comput. 21, 7 (July),</p><p><b>　　637–650.</b></p><p>　　HUBER, D., KAPURIA, A., DONAMUKKALA, R. R., AND HEBERT, M. 2004. Parts-based 3-D object classification. In Proceeding

94、s of the</p><p>　　IEEE Conference on Computer Vision and Pattern Recognition (CVPR 04).</p><p>　　IYER, N., KALYANARAMAN, Y., LOU, K., JAYANTI, S., AND RAMANI, K. 2003. A reconfigurable 3D engine

95、ering shape search system</p><p>　　part i: Shape representation. In Proceedings of ASME DETC 03: Computers and Information in Engineering (CIE) Conference</p><p>　　(Chicago, IL).</p><

96、p>　　JOHNSON, A. E. AND HEBERT, M. 1999. Using spin images for efficient object recognition in cluttered 3D scenes. IEEE Trans.</p><p>　　Pattern Anal. Mach. Intell. 21, 5, 433–449. ACM Transactions on Grap

97、hics, Vol. 25, No. 1, January 2006. 150 ? R. Gal and D. Cohen-Or</p><p>　　KAZHDAN, M., FUNKHOUSER, T., AND RUSINKIEWICZ, S. 2003. Rotation invariant spherical harmonic representation of 3D shape</p>&

98、lt;p>　　descriptors. In Proceedings of the Symposium on Geometry Processing.</p><p>　　KAZHDAN, M., FUNKHOUSER, T., AND RUSINKIEWICZ, S. 2004. Shape matching and anisotropy. ACM Trans. Graph. 23, 3, 623–629

99、.</p><p>　　LAMDAN, Y. AND WOLFSON, H. J. 1988. Geometric hashing: A general and efficient model-based recognition scheme. In Proceedings of the International Conference on Computer Vision. 238–249.</p>

100、<p>　　MARR, D. 1982. Vision: A Computational Investigation into the Human Representation and Processing of Visual Information.</p><p>　　W. H. Freeman, San Francisco, CA.</p><p>　　MIN, P.

101、2004. A 3D model search engine. dissertation. Department of Computer Science, Princeton University, Princeton, NJ.</p><p>　　OHBUCHI, R., MINAMITANI, T., AND TAKEI, T. 2003a. Shape-similarity search of 3D mod

102、els by using enhanced shape functions. In</p><p>　　Proceedings of the Theory and Practice of Computer Graphics 2003. IEEE Computer Society Press, Los Alamitos, CA, 97.</p><p>　　OHBUCHI, R., NAKA

103、ZAWA, M., AND TAKEI, T. 2003b. Retrieving 3D shapes based on their appearance. In Proceedings of the 5th</p><p>　　ACM SIGMM International Workshop on Multimedia Information Retrieval. ACM Press, New York, NY

104、, 39–45.</p><p>　　OHTAKE, Y., BELYAEV, A., AND SEIDEL, H.-P. 2004. Ridge-valley lines on meshes via implicit surface fitting. ACM Trans.</p><p>　　Graph. 23, 3, 609–612.</p><p>　　OSA