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

1、<p>　　1.3萬(wàn)漢字，7600單詞，4萬(wàn)英文字符</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>　　這篇文章介紹了一個(gè)平面三角網(wǎng)格的局部匹配方法。這個(gè)方法適用于不同的拓?fù)渑c數(shù)字但卻大體相似的的平面區(qū)域。我們介紹了一種全新的局部平面描述元，它能有效的表現(xiàn)出局部平面區(qū)域的幾何形

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

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

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

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

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

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

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

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

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

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

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

14、在二維遮擋匹配中至關(guān)重要的部分匹配方法，在三維圖形檢索中卻沒(méi)有引起很多注意[Tangelder andVeltkamp 2004]。</p><p>　　大多數(shù)技術(shù)的目標(biāo)是通過(guò)圖形的整體幾何結(jié)構(gòu)來(lái)檢索到相似的模型。換言之，相似度是由三維模型的全局特性得來(lái)的，比如不變矩[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>　　這些方法首先要通過(guò)一些整體相似變換（旋轉(zhuǎn)+統(tǒng)一規(guī)模）對(duì)模型進(jìn)行排列使其標(biāo)準(zhǔn)化，然后在模型之間建立對(duì)應(yīng)關(guān)系。這種全

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

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

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

19、的因素，比如一個(gè)有很大基座的雕像的手和沒(méi)有幾座的雕像的手，這是不會(huì)影響匹配的。</p><p>　　在對(duì)由深度掃描得到的深度圖像而構(gòu)成的三維物體進(jìn)行識(shí)別和標(biāo)記中，局部匹配是基礎(chǔ)方法[Frome et al. 2004]。在這些應(yīng)用中的查詢時(shí)總是視點(diǎn)相關(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)的。我們會(huì)在第九部分更深度詳細(xì)的說(shuō)明這些方法。</p><p>　　關(guān)于圖像空間的“興趣”點(diǎn)或者說(shuō)突出特征進(jìn)行抽取已經(jīng)被廣泛的研究了[Marr 1982]。對(duì)有興趣的表面特征或者突出特征的定義使我們研究的重點(diǎn)。正如我們下面說(shuō)明的，我們對(duì)有趣部分的定義是主要基于表

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

38、>　　圖 4。二次適應(yīng)的例子。紅色的點(diǎn)是由主軸線（綠色）定義的網(wǎng)格上的小樣本。這個(gè)網(wǎng)格是根據(jù)高斯曲率的不同來(lái)配色的。</p><p>　　圖 5。章魚(yú)模型上觸角的吸盤。（a）粗體的原始花紋與二次補(bǔ)丁。（b）局部描述符在黃色點(diǎn)位置。可以注意到他們的分布密度是與表面形狀相適應(yīng)的。</p><p><b>　　計(jì)算突出幾何特征</b></p><p

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

57、我們的系統(tǒng)的容量。在我們的實(shí)驗(yàn)中，我們處理的僅僅是它的一部分：圖7中所示的三個(gè)女子，和圖12的三個(gè)象。這個(gè)雕像具有粗糙的三通對(duì)稱性，但手工雕像的三個(gè)部分并不匹配，因?yàn)樗麄兪遣煌昝赖母北?。我們?yīng)用我們的自相似性分析并且對(duì)于每個(gè)匹配我們逐漸增長(zhǎng)區(qū)域從而形成兼容部分。只要它們匹配到一些誤差容限區(qū)域就會(huì)增長(zhǎng)。這種三通對(duì)稱性分析的結(jié)果示于圖11。</p><p>　　圖 12。斯坦福大學(xué)三維掃描倉(cāng)庫(kù)的泰國(guó)雕像。這個(gè)模型由1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

72、在規(guī)模1.0在不同尺度計(jì)算大約在同一分自旋圖像和自旋圖像之間的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)化是不適用的，因?yàn)槠ヅ鋵?shí)例不是先驗(yàn)已知的。</p><p>　　圖 20．星星模型（a）由18個(gè)三種不同的尺度星星組成。一個(gè)中等規(guī)模的星星作為查詢。使用旋圖像和我們的方法的結(jié)果分別顯示于（b）和（c）中，這個(gè)例子說(shuō)明了一個(gè)事實(shí)，我們的方法是尺度獨(dú)立的。</p><p>

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

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

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

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

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

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

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

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

82、lt;/p><p>　　我們感謝帕特里克閔珍貴的意見(jiàn)。感謝斯坦福大學(xué)提供的快活佛和泰國(guó)雕像，與馬克·保利提供的章魚(yú)圖像。</p><p><b>　　參考文獻(xiàn)：</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