突出幾何特征在局部匹配和相似性測(cè)定中的應(yīng)用研究論文.doc

突出幾何特征在局部匹配和相似性測(cè)定中的應(yīng)用研究ran gal and daniel cohen-or特拉維夫大學(xué) 這篇文章介紹了一個(gè)關(guān)于用三角網(wǎng)格模型表示的表面的局部匹配方法，我們的方法針對(duì)的是那些數(shù)字上和拓?fù)渖喜灰恢?，但是大致相同的表面區(qū)域。我們介紹新的局部表面描述可以有效地表示表面的局部區(qū)域的幾何形狀，描述方法被獨(dú)立地定義為基本三角，并且形成一個(gè)兼容的允許表面通過(guò)不同三角匹配的表示。為了應(yīng)對(duì)大網(wǎng)格的局部匹配的結(jié)合復(fù)雜度，我們介紹關(guān)于突出幾何特征的概念并且提出一個(gè)方法去構(gòu)建他們。一個(gè)突出幾何特征是不平滑局部形狀的復(fù)合高級(jí)特征。我們展示了一些相關(guān)的突出幾何特征能夠很好地描述了表面給各種各樣的相似性應(yīng)用。匹配突出幾何特征是基于建立旋轉(zhuǎn)不變量特征的索引并且一個(gè)通過(guò)幾何哈希散列加速的投票系統(tǒng)。我們用一些應(yīng)用來(lái)證明我們方法的有效率性，如同計(jì)算自相似性，校準(zhǔn)，子部分的相似性。分類和主題描述：i.3.5計(jì)算機(jī)圖形：計(jì)算幾何和對(duì)象建模通用術(shù)語(yǔ)：算法附加關(guān)鍵詞和短語(yǔ)：部分匹配，形狀檢索，突出特點(diǎn)，相似性，幾何變換1引言 在諸多需要用到大量幾何應(yīng)用的領(lǐng)域中，比如計(jì)算機(jī)視覺(jué)、機(jī)器人科學(xué)、分子生物學(xué)等，匹配是一項(xiàng)基礎(chǔ)性的工作。近來(lái)，由于3d建模技術(shù)廣闊的應(yīng)用前景，關(guān)于3d圖形檢索技術(shù)的研究已經(jīng)愈演愈烈?，F(xiàn)在，研究方向主要集中在全局匹配上，即在所有的模型間計(jì)算并測(cè)定相似性。局部匹配是一項(xiàng)匹配整體的一個(gè)元件或一定范圍的工作。 被匹配的部分沒(méi)有預(yù)定義，因此可以是任何一個(gè)更大形狀的一部分，匹配的方向和規(guī)模都沒(méi)有限制。為了測(cè)量相似性，局部匹配需要提前搜索并預(yù)定義匹配元件，因此在操作中比整體匹配更困難。在這篇文章中，我們將主要關(guān)注以三角網(wǎng)絡(luò)法為代表的表面局部匹配技術(shù)。 一般來(lái)說(shuō)，定義一個(gè)關(guān)于人對(duì)于相似性覺(jué)知的測(cè)量標(biāo)準(zhǔn)還是很困難的。即使有現(xiàn)成的相似度測(cè)量方法，在眾多具有不同表象的形狀里匹配到目標(biāo)也是一件有挑戰(zhàn)的事情。更何況在通往使局部匹配具備足夠可操作性的道路上有很多巨大的錯(cuò)綜復(fù)雜的障礙要跨越。例如，圖1中的4朵荷花是佛像的一部分。匹配這些佛像需要搜索超過(guò)1m個(gè)關(guān)于佛像的三角模型。我們注意到這些蓮花都是殘缺不均勻的，而且處于不同的方位，它們的程度也是事先不知道的。為了解決這個(gè)問(wèn)題，我們通過(guò)圖形的表面特征定義一個(gè)稀疏本地表面描述器群組.這些描述器代表了局部范圍內(nèi)的圖形表面特征，這些本地的與潛在的三角測(cè)量模型獨(dú)立定義，如此便建立了一個(gè)可通過(guò)潛在的不同的三角測(cè)量模型測(cè)量不同范圍間相似性的兼容的表示。由于描述器的數(shù)量明顯比之前少很多，因而大大減少了表面特征表述的組合復(fù)雜性。通過(guò)合理的設(shè)置描述器，能使這些描述器的描述能力十分的高效。然而，為了高效的實(shí)現(xiàn)對(duì)面積大，復(fù)雜程度高的表面進(jìn)行局部匹配，這些描述器的數(shù)量依然顯得龐大因而我們定義突出的幾何特征這個(gè)概念以用來(lái)建立高水平的復(fù)合描述器。 突出的幾何特征簡(jiǎn)而言之就是突出特征，由一簇描述表面重要范圍的描述器組成。這些突出特征很好的定義了表面的典型特性，為圖形的元件之間進(jìn)行非整體的相似性測(cè)量打下了基礎(chǔ)。突出特征匹配能夠適應(yīng)很多棘手的應(yīng)用，比如在簡(jiǎn)單的一個(gè)或幾個(gè)表面找到相似的部分。仍舊以荷花的圖形為例，在圖1中，四朵荷花通過(guò)自相似性匹配被找到，也就是重要元件和其他元件在相同表面進(jìn)行匹配。在本篇論文中，我們主要做如下研究：局部匹配：通過(guò)三角網(wǎng)絡(luò)法解決局部匹配的問(wèn)題，這種方法擴(kuò)展了3d模型整體匹配的結(jié)果。本地表面描述器：介紹一種新型的本地表面描述器，該描述器能夠更有效的編碼表面的模塊兒。它們與底層的三角獨(dú)立，形成了一個(gè)稀疏兼容的允許不同表面匹配的表現(xiàn)。突出幾何特征：我們介紹突出幾何特征的概念并給出一種構(gòu)建它們的方法。突出幾何特征是一種高度復(fù)合的特征，這些特征定義了本地局部圖形。我們把每個(gè)突出特征用若干轉(zhuǎn)動(dòng)和尺度不變的指數(shù)表征，以加快匹配和相似度測(cè)定。應(yīng)用：介紹一些以局部匹配為主的幾何應(yīng)用。在一些多變龐大且復(fù)雜的網(wǎng)絡(luò)中論證我們的方法的高效性。2背景圖形相似和匹配的問(wèn)題已經(jīng)在很多領(lǐng)域被廣泛研究，諸如計(jì)算機(jī)視覺(jué)，機(jī)器人科學(xué)，分子生物學(xué)等。其中大部分都只是關(guān)注2d圖形的匹配問(wèn)題。幾何學(xué)的方法被引入以后，3d模型匹配似乎更簡(jiǎn)單，而且還沒(méi)有類似光照和反射的外部阻塞和破壞效應(yīng)。 在計(jì)算機(jī)圖像領(lǐng)域，發(fā)展3d圖形匹配主要是為了圖形檢索。在網(wǎng)頁(yè)搜索引擎技術(shù)的支撐下，基于幾何屬性而不是文本的3d模型圖形匹配的新方法得到了快速發(fā)展。然而有阻塞的局部匹配的方法雖然在2d圖形匹配領(lǐng)域占據(jù)了至關(guān)重要的地位，但還沒(méi)有在3d圖形匹配領(lǐng)域得到足夠的關(guān)注。大部分技術(shù)都注重基于所有幾何圖形檢索相似模型。換句話說(shuō)也就是相似性是基于3d模型整體的特性，比如相同的時(shí)間變量，傅里葉描述器，柱狀圖和圖形分布情況，諧波為主表征。這些方法都依賴于全局相似變換（旋轉(zhuǎn)+均勻縮放）首次對(duì)準(zhǔn)和標(biāo)準(zhǔn)化模型的能力，這種全局相似變換把模型標(biāo)準(zhǔn)化并在原始模型和標(biāo)準(zhǔn)化之后的模型之間建立對(duì)應(yīng)關(guān)系。這種全局對(duì)準(zhǔn)的方法不能區(qū)分?jǐn)?shù)據(jù)間的不同，很容易引起局部特征的沒(méi)有對(duì)準(zhǔn)。因而是一種不合適的全局相似測(cè)量。這啟示了kazhdan通過(guò)控制異向性的作用來(lái)抵消上述方法的未對(duì)準(zhǔn)的影響。這方面來(lái)講，我們介紹的局部匹配技術(shù)可以用來(lái)對(duì)準(zhǔn)兩個(gè)幾乎沒(méi)有全局相似性的模型。過(guò)局部匹配的方法，我們可以明確地匹配符合的突出特征，從局部匹配中建立全局對(duì)準(zhǔn).基于圖形的方法依賴于3d模型的拓?fù)浣Y(jié)構(gòu)是圖形的一個(gè)重要的形態(tài)特征。拓?fù)浣Y(jié)構(gòu)通常表示為有關(guān)系的數(shù)據(jù)結(jié)構(gòu)，如圖：基于圖形的表示法促進(jìn)了具有相似拓?fù)浣Y(jié)構(gòu)的元件間的局部匹配。在funckhouse中，作者為3d模型匹配提供了一種基于兩個(gè)圖形之間描述器群組的距離平方和的方案。這種方法允許不同權(quán)重的局部使用原始的模型描述器群組，因而可使局部整體的匹配方案成立。這些方案都依賴于所有的模型按照使匹配局部在3d空間中相互更加靠近的方式排列的假設(shè)。局部代替整體的匹配方式可以歸類到基于id轉(zhuǎn)換的局部匹配。一般的局部匹配都致力于在任何剛性運(yùn)動(dòng)轉(zhuǎn)換下實(shí)現(xiàn)局部匹配，有時(shí)候甚至在大規(guī)模轉(zhuǎn)換下也能有很好的效果。 同樣也可以考慮一種更加廣泛的轉(zhuǎn)換方式比如仿射或透視等。 在這篇文章中我們發(fā)展了一種支持剛性轉(zhuǎn)換和統(tǒng)一縮放的局部圖形匹配方法，被稱作相似變換。我們的方法不在全局上對(duì)齊圖形，從而否定了匹配的實(shí)現(xiàn)可能，例如把有一個(gè)巨大底座的雕像的手轉(zhuǎn)換到?jīng)]有底座的雕像的手。局部匹配是從掃描儀中得到深度圖像的3d實(shí)體識(shí)別和登記的基礎(chǔ)性模塊兒。在這種應(yīng)用場(chǎng)景中，檢索依賴于視圖和分辨率。通常這些技術(shù)基于匹配局部描述器群組，比如旋轉(zhuǎn)圖形和圖形背景。不同于這些局部描述器群組，我們研究的表面描述器群組能很好的被構(gòu)建，用來(lái)高效的盡可能大的表示網(wǎng)格區(qū)域，具有不受規(guī)模限制和適應(yīng)性強(qiáng)的特點(diǎn)。我們將在第9章節(jié)進(jìn)一步闡述這些方法。圖像空間中的“有趣”點(diǎn)和突出特征的抽取已經(jīng)得到廣泛研究。有趣表面特征或者叫突出特征的定義使我們工作的中心。正如我們下面將要闡述的，我們對(duì)有趣部分的定義著重基于表面曲率。shum認(rèn)識(shí)到了用表面曲率方法去匹配3d圖形的重要性。2 顯著的幾何特性 人類感知以及識(shí)別和解釋形狀的能力是一個(gè)廣泛研究的課題。確實(shí)，它不只是一項(xiàng)任務(wù)，而是許多項(xiàng)（任務(wù)的集合）：顏色、陰影、形狀、運(yùn)動(dòng)、紋理和環(huán)境因素在過(guò)程中一般都將被用到，與文化背景和個(gè)人關(guān)聯(lián)不大。在計(jì)算機(jī)圖形和建模中的核心問(wèn)題就是理解“形狀”的概念。為了實(shí)現(xiàn)目標(biāo)，我們使用dryden和mardia1998作的關(guān)于形狀的正式定義：把位置、規(guī)模和旋轉(zhuǎn)效應(yīng)（歐幾里得變換）從物體中濾出后，剩下的就是物體的全部幾何信息。 有一個(gè)共識(shí)就是根據(jù)部分來(lái)代表整個(gè)形狀可能有助于用人類的視角來(lái)認(rèn)識(shí)過(guò)程hebb 1949。在二維空間，它可以用于處理閉塞問(wèn)題，在三維空間，它可以用于處理非剛性體。一個(gè)關(guān)鍵的問(wèn)題是：哪些部分（需要處理）？在我們的研究中，我們定義，由通用計(jì)算規(guī)則的方式，一個(gè)物品的突出部分，即壓縮了足夠多特征的部分，將被用于第一級(jí)搜索中hoffman and singh 1997。關(guān)于物體的“部分顯著性”，我們目標(biāo)是用一小部分特征來(lái)捕捉物體的形狀。其顯著性，在某種程度上，是用有效性作為指標(biāo)來(lái)決定。 我們的方法是建立在hoffman和singh1997提出的視覺(jué)部分顯著性理論之上的。根據(jù)他們的理論，一個(gè)部件的顯著性是它尺寸的函數(shù)，相對(duì)于整個(gè)物體，與其突出的程度和邊界的強(qiáng)度有關(guān)。在這項(xiàng)工作中，我們的目標(biāo)是開(kāi)發(fā)能應(yīng)用于網(wǎng)格的方法的定量定義。重點(diǎn)就是對(duì)“邊界強(qiáng)度”的計(jì)算。我們的方法是使用曲率值的函數(shù)。我們建議，一個(gè)物體的顯著性部分取決于（至少）兩個(gè)因素：它相對(duì)于整個(gè)物體的大小以及曲率變化和強(qiáng)度的數(shù)量。在第五部分我們將描述確定顯著性幾何特征的計(jì)算方法。3.概述 給定一個(gè)三維表格，我們分析它的幾何特性并確定用部分形狀描述的網(wǎng)格稀疏表示。然后我們從網(wǎng)格中提取有趣并顯著的幾何特征。這些特征被索引并存儲(chǔ)在可被有效地用于查詢部分匹配模式的數(shù)據(jù)庫(kù)。匹配子部分需要轉(zhuǎn)換成一個(gè)共同的坐標(biāo)系。一個(gè)很自然的實(shí)現(xiàn)方式是存儲(chǔ)所有模型在由每個(gè)頂點(diǎn)以及其鄰域確定的所有可能坐標(biāo)系中。然后，對(duì)于給定的查詢，我們將測(cè)試由查詢的頂點(diǎn)所確定的所有可能的方位和定標(biāo)。這種方法會(huì)導(dǎo)致測(cè)試中“組合爆炸”，這遠(yuǎn)遠(yuǎn)超出了我們的計(jì)算能力，尤其是（計(jì)算）那些含有上千個(gè)或更多頂點(diǎn)的模型。為了克服這些組合障礙，我們提出了三種方法：用一組形狀的稀疏描述符表示給定的網(wǎng)孔。每個(gè)描述符表示具有良好的二次擬合的局部區(qū)域。確定一小套顯著性的幾何特征并索引它們。顯著的特征表示一個(gè)給定的形狀的令人關(guān)注的部分。預(yù)先計(jì)算幾何哈希表，使得在旋轉(zhuǎn)和縮放變換下能夠快速地部分匹配。在四至六節(jié)，我們提出以下的方法分析模型的表面；定義局部的形狀描述符；定義顯著性特征并存儲(chǔ)索引的矢量；使用索引和集合散列法查詢部分匹配的模型數(shù)據(jù)庫(kù)。然后在第七節(jié)我們將討論我們方法的性能問(wèn)題。在第八節(jié)在我們展示了一些基于我們的部分匹配算法的應(yīng)用程序和結(jié)果。在第九節(jié)，我們將說(shuō)明幾何散列法和基于直方圖方法之間的關(guān)系，然后在第十節(jié)我們得出結(jié)論，并討論未來(lái)的工作。在我們繼續(xù)之前，我們參考圖3，它充分說(shuō)明了部分匹配的精髓之處。該圖顯示了模型（a）和（b）三部分的匹配。值得注意的是，這兩個(gè)模型只有一小部分實(shí)際匹配。這個(gè)例子強(qiáng)調(diào)了一個(gè)事實(shí)，即部分匹配多于給定模型的子部分的匹配，并且該匹配部分預(yù)先并不確定。3.局部的表面描述符 一個(gè)局部的表面描述符是一個(gè)點(diǎn)p，它在表面上或者是在p點(diǎn)附近的與其相關(guān)聯(lián)的二次斑點(diǎn)的近似表面上。關(guān)鍵點(diǎn)是，只要每個(gè)描述符有效地代表它周圍的局部表面區(qū)域，那么一小部分的描述符就可以表示形狀。這種表示適用于幾何形狀。平滑區(qū)域由相對(duì)較少數(shù)量的描述符所表示，因?yàn)槊恳粋€(gè)二次曲面斑點(diǎn)可以在局部近似于一個(gè)大的區(qū)域。高頻的不平滑的區(qū)域需要相對(duì)大量的描述符。注意圖5（b）中在鷹嘴附近和在光滑區(qū)域的局部形狀描述符的密度。作為一種分析局部表面的手段，我們將曲率值與每個(gè)描述符相關(guān)聯(lián)。接下來(lái)，我們通過(guò)描述二次曲面擬合方案和算法來(lái)構(gòu)造一組有效的描述符。圖片3 部分匹配。老鷹模型（b）的三個(gè)部分通過(guò)高度變形疊加在一個(gè)結(jié)構(gòu)上應(yīng)用于圖（a）中。這三個(gè)副本有不同的尺度和方向。通過(guò)應(yīng)用部分匹配（c）-（e），老鷹的這三個(gè)部分與整個(gè)老鷹模型相匹配。請(qǐng)注意，每一對(duì)匹配之間只有部分重疊。該匹配是通過(guò)在一個(gè)共同的坐標(biāo)系中對(duì)三組局部形狀描述符的變換實(shí)現(xiàn)的。用小黃球來(lái)說(shuō)明局部的形狀描述符。4.1 二次擬合和曲率估計(jì) 使用douros和buxton2002提出的方法，表面通過(guò)可分析的二次曲面斑點(diǎn)很好地由每個(gè)頂點(diǎn)近似表示。對(duì)于每個(gè)二次曲面斑點(diǎn)，選擇可以代表的點(diǎn)然后計(jì)算分析斑點(diǎn)的在該點(diǎn)的微分屬性。對(duì)于可表示為f（x，y，z）= 0的隱函數(shù)的表面，我們使用一個(gè)有九個(gè)系數(shù)的二次方程。這種表面的擬合容易用公式表示為用于解決特征值問(wèn)題的最小二乘法。這使得該方法可以工作在3d模型的任何類型的點(diǎn)云上，而不管底層表面的取向。需要注意的是這樣的表示并不需要單獨(dú)指出任何坐標(biāo)軸。對(duì)于網(wǎng)格的每個(gè)頂點(diǎn)v，我們挑選適合的隱式表面，并且其投影在隱式表面上被表示為v。在v上的曲率張量和曲率倒數(shù)由在v上計(jì)算分析（的數(shù)據(jù)）來(lái)估計(jì) ohtake et al. 2004。為了增加魯棒性，我們測(cè)量了各頂點(diǎn)附近的尺寸，并選擇具有平均曲率的二次方程。盡管有更快的技術(shù)來(lái)估計(jì)離散曲率 alliez et al. 2003; rusinkiewicz 2004，但由于這些曲率計(jì)算是離線的，我們實(shí)現(xiàn)了一般更強(qiáng)大的一個(gè)二次曲面擬合技術(shù)。圖4展示了局部二次曲面匹配和所估計(jì)的曲率圖。4.2 簡(jiǎn)潔的表示 為了產(chǎn)生一組相當(dāng)小的，但有效的局部表面描述符，我們定義一個(gè)局部表面斑點(diǎn)，并將其與表示該斑點(diǎn)的描述符相關(guān)聯(lián)。我們采用區(qū)域發(fā)展的技術(shù)來(lái)反復(fù)定義局部斑點(diǎn)。我們根據(jù)絕對(duì)高斯曲率排列對(duì)網(wǎng)格頂點(diǎn)進(jìn)行降序排序，并為每個(gè)頂點(diǎn)，在它的附近近似為最大可能的“二次曲面斑點(diǎn)”。所有包括在所述局部斑塊中的頂點(diǎn)，之后將從排序列表中刪除，并且繼續(xù)迭代過(guò)程以定義下一個(gè)斑點(diǎn)。我們的方法是貪婪的，即在每一個(gè)步驟中，我們限定所選頂點(diǎn)附近滿足預(yù)定的錯(cuò)誤閾值的最大可能的區(qū)域。所有本文中示出的例子，我們使用的模型邊界框的對(duì)角線長(zhǎng)度為10-4。我們測(cè)量擬合點(diǎn)到裝配表面距離的平方代數(shù)之和的二次曲面擬合的質(zhì)量。代數(shù)距離比歐幾里德距離更容易評(píng)估，雖然它不太可靠，但它是測(cè)量質(zhì)量的有效措施。 一旦斑點(diǎn)被確定，我們選取它的質(zhì)量中心作為代表點(diǎn)，并與橫跨斑點(diǎn)的最高曲率相關(guān)聯(lián)。圖5顯示的章魚(yú)模型的觸手的結(jié)果?；叵胍幌?，局部表面描述符的主要目標(biāo)之一是細(xì)分表示一個(gè)獨(dú)立的給定模型。因此，我們隨機(jī)（不一定一致地）在表面取樣osada et al. 2001; elad et al. 2001, 并使用這些隨機(jī)樣本進(jìn)行二次曲面擬合。以圖6作為用于計(jì)算兩個(gè)不同的細(xì)分曲率的一個(gè)例子?？梢钥闯?，盡管有不同的細(xì)分，曲率地圖和局部表面描述符的分布是相似的。圖片4 二次曲面擬合示例。紅色的點(diǎn)是由主軸（藍(lán)色）確定的網(wǎng)格上的樣點(diǎn)。這個(gè)網(wǎng)格是由高斯曲率著色的。圖片5 章魚(yú)觸手吸盤示例。（a）原始細(xì)分和加粗的二次曲面斑點(diǎn)。（b）黃色點(diǎn)表示局部表面描述符。需要注意的是它們的密度與表面形狀相適應(yīng)。圖6：曲率地圖上計(jì)算有不同的鑲嵌相同的模型。藍(lán)色是低曲率和紅色的高。5.計(jì)算機(jī)的顯著幾何特性 嚴(yán)格意義上，一個(gè)突出的幾何特征的圖像具有一個(gè)非平凡形狀的表面的區(qū)域。我們歸類一組描述相符的幾何特性得到有趣發(fā)現(xiàn)，它們具有相對(duì)于其它具有高曲率的幾何特征，并具有高方差曲率值。顯著幾何特征是一個(gè)自由參數(shù)h的函數(shù)，它由球體邊界的顯著特征的半徑限定。 對(duì)于每個(gè)描述符，我們從最大當(dāng)前顯著等級(jí)逐步添加描述符并圍繞它產(chǎn)生一個(gè)描述符集群，當(dāng)添加描述符不足時(shí)該過(guò)程停止。我們?cè)试S集群之間某種程度上重疊的所有的描述符執(zhí)行此過(guò)程（在我們的實(shí)驗(yàn)中允許高達(dá)20的重疊）。描述符的顯著性等級(jí)集合f包含d f，具有以下四個(gè)方面功能:df區(qū)（d）中，其中，area（d）是補(bǔ)丁具有d相關(guān)聯(lián)的球體尺寸區(qū)域df curv（d）中，在那里curv（d）是與d相關(guān)聯(lián)的曲率n（f）的數(shù)目的最?。╯）或最大（多個(gè)）曲率集群中var（f）的集群中曲率變化。顯著度s級(jí)可以定義為這四個(gè)方面的線性組合。然而，經(jīng)驗(yàn)上我們發(fā)現(xiàn)以下表達(dá)式更有效： 第一項(xiàng)area（d）curv（d）3通過(guò)結(jié)合其相對(duì)大小和曲率表示該區(qū)域的顯著性。curv（d）可以是高斯曲率或最大曲率分量，圖7展示出了從泰國(guó)雕像的婦女的2曲率圖，無(wú)顯著差異。需要注意的是當(dāng)零高斯曲率大面積cad模型時(shí)，一個(gè)最大的曲率是一個(gè)更好的選擇。第二項(xiàng)n（f）var（f）表示對(duì)簇的興趣程度，并添加到集群的顯著性，如圖8所示。我們對(duì)w1和w2使用0.5的權(quán)重。顯著部分的定義相對(duì)于啟發(fā)式并不是完全相關(guān)聯(lián)，因?yàn)槲覀儗?duì)特定部分不感興趣，而是在產(chǎn)生了一些特征的模型以及顯著特征（參見(jiàn)圖9）。應(yīng)當(dāng)強(qiáng)調(diào)的是，采用的常量公式（1）無(wú)需手動(dòng)調(diào)整，本文中使用的所有示例和實(shí)驗(yàn)使用相同的表達(dá)。換句話說(shuō)，我們定義一個(gè)顯著的幾何特征作為該模型的一個(gè)區(qū)域，該區(qū)域相比該模型的其他部分更加顯著而有趣。頂端分級(jí)簇定義了給定形狀的顯著幾何特征。顯著幾何特征的一些結(jié)果示于圖9，其中我們只提取最顯著的特征，無(wú)論是那些等級(jí)在排名前10，或那些符合規(guī)定的閾值。圖7：曲率分析了來(lái)自泰國(guó)的雕像三女。這些圖像是利用高斯曲率（左）與最大曲率（右）。這些微小的差別表明，顯著特征的定義是不敏感的分析。圖8：左側(cè)圖像顯示了由曲率著色的局部表面描述符。在右邊的圖像中，顯著性等級(jí)是可視化的規(guī)模，從藍(lán)色到紅色顯示。補(bǔ)丁是根據(jù)其中顯著特征的顯著級(jí)著色的。圖9：顯著幾何特征（橙色）是通過(guò)分析表面自動(dòng)定義的。單個(gè)部分為紅色。6索引和幾何散列 模型的顯著特征在一個(gè)旋轉(zhuǎn)和尺寸不變的數(shù)據(jù)庫(kù)進(jìn)行定義，離線提取以及存儲(chǔ)。各顯著特征都與一個(gè)矢量索引（簽名）相關(guān)聯(lián)并插入到一個(gè)幾何哈希表。指數(shù)的矢量被用作幾何簽名并且允許快速訪問(wèn)到有具有相似形狀的部分。為了更加有效，我們使用旋轉(zhuǎn)和尺寸不變幾何簽名。然而只有簽名不足以完全識(shí)別而且不會(huì)提供符合他們的實(shí)際轉(zhuǎn)換。通過(guò)采用幾何散列拉姆丹和歐勝1988最匹配的形狀改造被確定。 在我們的實(shí)現(xiàn)中，我們使用了四個(gè)術(shù)語(yǔ)來(lái)定義的顯著級(jí)，如表達(dá)由方程1中，作為相似性不變矢量索引。請(qǐng)注意，其他闡述指數(shù)，如歸矩也同樣可以用來(lái)適用。然而在執(zhí)行索引時(shí)我們加強(qiáng)了對(duì)顯著特征效率的要求。我們利用幾何散列來(lái)加速模型數(shù)據(jù)庫(kù)中的部分匹配的檢索。簡(jiǎn)單地說(shuō)，幾何哈希是加速剛體變換和部分匹配的機(jī)制，是一個(gè)統(tǒng)一的尺度。該方法利用投票計(jì)劃的方式選取一大組轉(zhuǎn)換中的最佳變換。這些方法量化變換空間成六維表。鑒于兩個(gè)對(duì)象，a和b，對(duì)于a中的三個(gè)元與b中的三個(gè)元轉(zhuǎn)換，其轉(zhuǎn)換過(guò)程是經(jīng)過(guò)計(jì)算并將其中表決過(guò)程保存。得票最多條目進(jìn)行對(duì)齊改造。為了避免窮舉搜索所有的轉(zhuǎn)換，幾何散列編碼離線提取所有候選轉(zhuǎn)換在一個(gè)大的哈希表中，這樣一來(lái)給定尺寸的查詢模型| q |時(shí)，都需要查詢哈希表，不管多少模型被編碼在哈希表中。這些經(jīng)過(guò)預(yù)先計(jì)算的哈希表省卻了在每個(gè)模型三個(gè)元的搜索過(guò)程。 我們的實(shí)現(xiàn)方式是用顯著幾何特征和其表面描述為研究對(duì)象定義在散列表中的三個(gè)元和表決點(diǎn)。哈希表中包含數(shù)據(jù)庫(kù)中的所有模型的所有顯著幾何特征。通常情況下，每一個(gè)顯著的特點(diǎn)包括20-30個(gè)局部表面描述符。我們從一個(gè)小鄰域（最多兩個(gè)環(huán)）中取三個(gè)元定義候補(bǔ)變換，這樣一來(lái)對(duì)準(zhǔn)測(cè)試通常數(shù)所需的只是| q |，而不是。通過(guò)結(jié)合索引和幾何散列，我們成功地找到與查詢和存儲(chǔ)之間相匹配的在散列表中的顯著特征。該指數(shù)是用來(lái)快速拒絕在投票階段的顯著特點(diǎn)。匹配給定的兩個(gè)顯著特征的轉(zhuǎn)型是關(guān)于各種匹配和相似性應(yīng)用程序，如下所述。表1：統(tǒng)計(jì)數(shù)據(jù)的一些大，小型號(hào)7時(shí)間和存儲(chǔ)的注意事項(xiàng) 提出的方法使執(zhí)行大部分的工作所必需的脫機(jī)部分匹配模式允許快速查詢時(shí)間。表i作為例子示出了預(yù)處理的一步我們所需的時(shí)間和存儲(chǔ)空間。在其核心，部分匹配問(wèn)題需要大量的計(jì)算進(jìn)行搜索和比較。我們使用了更加耗時(shí)的表面分析來(lái)創(chuàng)建一個(gè)稀疏和自適應(yīng)的描述符。為了我們的指數(shù)構(gòu)造顯著的幾何特征，我們使用幾何散列。索引幾何散列的主要優(yōu)點(diǎn)是，它允許一個(gè)尺度獨(dú)立機(jī)制這在我們的應(yīng)用程序中是非常重要的。對(duì)于簡(jiǎn)單的情況下，如果是不需要的規(guī)模，可以考慮實(shí)施其他用于索引的顯著幾何特征，如旋圖像和形狀內(nèi)容的方法johnson and hebert 1999; huber et al. 2004.。 某些應(yīng)用程序或方案可能需要一個(gè)更有效的預(yù)處理步驟。正如我們上面提到的，有快速方法去估計(jì)離散曲率和二次系數(shù)petitjean 2002; alliez et al. 2003; rusinkiewicz 2004。這些方法可以加快對(duì)規(guī)則模型的離散曲率估計(jì)，但是對(duì)于不規(guī)則鑲嵌模型不太可靠。 此外，關(guān)于如何提高幾何散列的效率，無(wú)論在時(shí)間和空間上的要求還有很多的工作要做。8應(yīng)用和結(jié)果 部分匹配，在一般情況下，可以作為各種幾何應(yīng)用的基本工具。特別是，需要進(jìn)行眾多表面處理時(shí)。我們?cè)谶@里論述我們已經(jīng)嘗試過(guò)的三個(gè)應(yīng)用程序：自相似性，形狀排列，和分部檢索。8.1 自相似性 圖10 圖11 圖10顯示了自相似性搜索的結(jié)果。通過(guò)定義表面的一個(gè)顯著特征來(lái)分析表面。方法是自動(dòng)辨認(rèn)有大量相似情況的表面的顯著特征。在圖中,章魚(yú)的觸手上的吸盤模型被識(shí)別（更仔細(xì)的特征參加圖5）。注意到吸盤有相對(duì)較大的各種尺寸。圖1是另一個(gè)自相似性應(yīng)用的結(jié)果,通過(guò)這個(gè)我們了解到佛像模型上四個(gè)蓮花的存在方式。表1展示了查詢章魚(yú)和佛像兩個(gè)大模型和另兩個(gè)小模型的統(tǒng)計(jì)數(shù)據(jù)。在上面的例子中,我們發(fā)現(xiàn)是對(duì)所有特征的復(fù)制進(jìn)行旋轉(zhuǎn)和統(tǒng)一的尺度轉(zhuǎn)換。該算法首先將表面的相似特征分類排序，然后為每一個(gè)具有最大相似等級(jí)的相似特征進(jìn)行部分匹配。圖11顯示了自相似分析在斯坦福三維掃描存儲(chǔ)庫(kù)中泰國(guó)雕塑的大型模型上的部分應(yīng)用。這個(gè)模型中,如圖12所示, 圖12包含10米的多邊形,這超出了我們的系統(tǒng)的能力。在我們的實(shí)驗(yàn)中,我們只處理它的部分:如圖7所示的三個(gè)女人,如圖12所示的三個(gè)大象。雕像有一個(gè)粗略的三相對(duì)稱,但因?yàn)樗麄儾⒉煌昝赖母北?，這三個(gè)部分的手工制作的雕像并不匹配。我們應(yīng)用我們的自相似分析并且對(duì)于每一個(gè)匹配發(fā)展出一個(gè)更大的區(qū)域來(lái)形成兼容部分。只要符合一定的誤差，該區(qū)域就能得到發(fā)展。這三相對(duì)稱性分析結(jié)果如圖11所示。8.2形狀對(duì)齊 大多數(shù)全局匹配方法首先確定剛體變換和統(tǒng)一的規(guī)模,盡可能使兩個(gè)模型一起,測(cè)量他們之間的距離。這通常是通過(guò)一個(gè)主成分分析(pca)應(yīng)用于整個(gè)模型。當(dāng)圖形在一個(gè)細(xì)微的地方有差異，這樣一個(gè)全局分析就容易出錯(cuò)。圖2顯示了一男一女之間的對(duì)齊模型。算例表明，雖然兩個(gè)模型在幾何形態(tài)和構(gòu)成明顯的差異，但通過(guò)他們的突出幾何特征的部分匹配，是可能使它們?cè)谄ヅ涞牡胤綄?duì)齊的。在圖13所示的另一個(gè)例子中， 圖13 圖14相同的模型表現(xiàn)出兩種不同的姿勢(shì)。后者的例子強(qiáng)調(diào)全局pca對(duì)齊未能正確地對(duì)齊,而部分匹配盡可能正確地對(duì)齊。我們的對(duì)準(zhǔn)是基于大多數(shù)能夠滿足主要特征轉(zhuǎn)換的方案提出的。 我們的對(duì)齊算法首先搜索每一個(gè)模型的主要特征對(duì)之間的匹配。然后對(duì)于每一個(gè)這樣的匹配，相關(guān)的轉(zhuǎn)換獲得一個(gè)評(píng)級(jí)來(lái)反映成功對(duì)齊的數(shù)量。最成功的轉(zhuǎn)換被選出并用來(lái)使兩個(gè)給定的模型盡可能的相近。被選擇的轉(zhuǎn)換定義兩個(gè)模型之間的對(duì)應(yīng)關(guān)系。一旦這種對(duì)應(yīng)關(guān)系被定義，相應(yīng)的特征可以在最小二乘意義上更加接近。8.3 部分形狀檢索 應(yīng)用局部形狀檢索允許部分和查詢不同的較大的形狀來(lái)檢索。對(duì)于局部形狀檢索的框架概述如圖14所示。 圖15圖15顯示了一個(gè)檢索人手的例子。這樣的一個(gè)機(jī)制對(duì)有效建模來(lái)說(shuō)是至關(guān)重要的，因?yàn)樗l(fā)現(xiàn)旋轉(zhuǎn)和統(tǒng)一的尺度轉(zhuǎn)換下的相似形狀可以作為更大的不同形狀的一部分，例如圖16中的植物所示。 圖16檢索的模型不一定要全局相似（例如，植物有高有矮），但需要足夠的局部相似。如圖16所示，它并不是最好的匹配，而是前5個(gè)和前72個(gè)匹配中的一些樣本。 圖17 從圖3和圖17可以發(fā)現(xiàn)有趣的結(jié)果，即它們不能通過(guò)全局匹配技術(shù)來(lái)實(shí)現(xiàn)。在圖17顯示的情況下，被檢索的圖形的現(xiàn)實(shí)意義和查詢對(duì)象是不同的，盡管如此，子部分在幾何上是和查詢對(duì)象相同的。 為了評(píng)估我的部分匹配方法的性能，我們的報(bào)告對(duì)精密召回的實(shí)驗(yàn)進(jìn)行了普林斯頓形狀基準(zhǔn)（psb）模型數(shù)據(jù)庫(kù)。我們只使用分類包括類如人手，人腳，人臉，動(dòng)物的四肢等自然模型。表二顯示了根據(jù)以下內(nèi)容作出的評(píng)估結(jié)論的總結(jié)：最近鄰：屬于相同等級(jí)查詢的最貼切匹配的百分比；第一層與第二層：查詢的類出現(xiàn)在top k匹配模型的比例，其中k取決于查詢類的大??；措施：對(duì)檢索結(jié)果的固定數(shù)量的精度和召回的混合測(cè)量。在判別方法的更多細(xì)節(jié)，參見(jiàn)shilane等人2004。 我們的實(shí)驗(yàn)是在p4-3.0 ghz 2 gb的內(nèi)存下進(jìn)行的。我們用“顯著等級(jí)”（方程（1）為指標(biāo)。然而，應(yīng)該強(qiáng)調(diào)的是，在psb數(shù)據(jù)庫(kù)最模型有一個(gè)粗略的三角（見(jiàn)，例如，圖15（a）。在這種情況下，顯著性等級(jí)過(guò)于粗糙，并且和相似的粗略圖形有相當(dāng)大的差別。為了避免這種情況,對(duì)于粗糙的模型,我們直接使用幾何哈希表中的局部表面描述符。盡管如此，我們的精密召回分?jǐn)?shù)相對(duì)于全局匹配實(shí)現(xiàn)典型的結(jié)果相當(dāng)不錯(cuò)。應(yīng)該指出的是，大部分的成功取決于類的定義。例如，人類的雙手是良好定義的，而其他類，如動(dòng)物的肢體或人的面孔，很難界定。圖10 自相似性。在章魚(yú)的觸手吸盤模型具有相似的形狀。注意，它們的大小各不相同的模型。圖11大象的對(duì)稱性分析（左上）。在三頭大象類似區(qū)域檢測(cè)和上色。圖12斯坦福的3d掃描庫(kù)中泰國(guó)雕像。模型包含10m多邊形，具有粗糙的三相對(duì)稱性。圖13基于全局主成分分析（pca）模型對(duì)齊（右）和部分匹配（左）。圖14形狀檢索的框架概述。給定一個(gè)數(shù)據(jù)庫(kù)模型（a）；我們分析了每個(gè)圖形的幾何特性，并定義一個(gè)局部形狀描述符嚙合特性的稀疏表示（b）；然后我們從每個(gè)模型提取有趣的和顯著的幾何特征（c）；這些特征被編入索引并存儲(chǔ)在模型數(shù)據(jù)庫(kù)，可以有效地查詢部分匹配（d）；上述步驟離線執(zhí)行。當(dāng)給定一個(gè)在線查詢模型（e）；我們以同樣的方式分析它，確定表面局部描述符（f）和突出的幾何特征（g）；對(duì)每個(gè)顯著幾何特征，我們查詢模型數(shù)據(jù)庫(kù)來(lái)找到一系列匹配特征（h）。使用這些匹配我們返回具有更多匹配特征的模型。圖15兩個(gè)例子（b）和（c）的粗糙人手成功匹配（一），和兩個(gè)假陽(yáng)性匹配（d）和（e）。圖16一種植物模型相似性查詢的檢索結(jié)果。圖17部分匹配。潛艇（橙色）相匹配的兩部分（左）和城堡的四塔（右）。表ii普林斯頓形狀基準(zhǔn)數(shù)據(jù)庫(kù)和精度召回措施實(shí)驗(yàn)總結(jié)9.基于柱狀圖的描述符 局部匹配在從全距掃描儀生成的深度圖像或者點(diǎn)云圖中識(shí)別與記錄3d物體（johnson and hebert 1999; huber and hebert 2003; frome et al. 2004）里扮演著一個(gè)重要的角色。在這些應(yīng)用中，查詢圖像通常是依賴于視圖和分辨率（視覺(jué)相關(guān)和分辨率相關(guān)）的，而且數(shù)據(jù)經(jīng)常嘈雜而不完整。 用純局部描述方法處理局部匹配，像是表面曲率，在噪音存在的時(shí)候是相對(duì)不穩(wěn)定的。因此，穩(wěn)定的點(diǎn)描述需要依靠局部附近的支持。舉例說(shuō)明，旋轉(zhuǎn)圖片johnson and hebert 1999和形狀常數(shù)frome et al. 2004是有名的量化的對(duì)一個(gè)給出的點(diǎn)的局部附近的表示。 這些描述符作為輸入的點(diǎn)云p和基準(zhǔn)點(diǎn)p，并且通過(guò)p點(diǎn)周圍小范圍的其他點(diǎn)的分布捕捉p點(diǎn)局部的圖像形狀。支持的區(qū)域被離散為容器，我們還可以定義一個(gè)柱狀圖用來(lái)統(tǒng)計(jì)每個(gè)容器中包含的點(diǎn)的數(shù)量。這些柱狀圖可以被直接用來(lái)當(dāng)作局部描述或者之后通過(guò)額外的轉(zhuǎn)變?cè)鰪?qiáng)，比如球面諧波表示。 圖18第十八張圖 通過(guò)計(jì)算得到的相同形狀不同比例的星星模型的旋轉(zhuǎn)圖像。這張圖顯示了在這個(gè)位置的四個(gè)人們感覺(jué)形狀相同但是比例不同的旋轉(zhuǎn)星星圖片。從中可以看出，即使旋轉(zhuǎn)圖像在相同比例計(jì)算形狀時(shí)是相似的（左圖），它們?cè)诓煌壤嗤螤钍遣煌模ㄓ覉D）。 圖19第十九張圖 這個(gè)l2距離表示的是計(jì)算出來(lái)的在正常大小的旋轉(zhuǎn)圖像和其他比例時(shí)之間同一點(diǎn)的距離。這個(gè)曲線圖表示了旋轉(zhuǎn)圖像特征對(duì)比例大小的敏感度。 這些局部描述可以成為我們局部表面描述的替代物，然而這些描述并不是尺度不變的而且它們對(duì)幾何學(xué)并不適用，這點(diǎn)我們會(huì)稍后解釋。 基于柱狀圖的描述johnson and hebert 1999; huber and hebert 2003; frome et al.2004 不是尺度不變的。舉例來(lái)說(shuō)，在圖18中，我們提到指定位置中的四個(gè)人們感覺(jué)形狀相同但是比例不同的旋轉(zhuǎn)星星圖片。從中可以看出，即使旋轉(zhuǎn)圖像在相同比例計(jì)算形狀時(shí)是相似的（左圖），它們?cè)诓煌壤嗤螤钍遣煌模ㄓ覉D），旋轉(zhuǎn)圖像對(duì)比例的敏感度已經(jīng)在圖19中顯示出來(lái)了。運(yùn)用某些比例標(biāo)準(zhǔn)化并不適用，因?yàn)槠ヅ涞睦硬](méi)有先驗(yàn)性。第二十張圖星星模型中總共包含18個(gè)3種不同比例的星星。中等比例的星星被用來(lái)當(dāng)作疑問(wèn)。使用旋轉(zhuǎn)模型和我們理論的結(jié)果在b和c圖中分別顯示。這個(gè)例子表明了我們的方法是與比例無(wú)關(guān)的。第二十一張圖 這個(gè)圖像顯示了描述數(shù)量和正確匹配數(shù)量之間的平衡。從中可以看出，我們的方法僅僅需要為數(shù)不多的描述就能成功地找到所有的局部匹配。 在我們的方法中，我們用幾何哈希散列去匹配突出特征，這個(gè)方法本質(zhì)上是一個(gè)尺度無(wú)關(guān)的方法，如同可以在圖3和20中可以看到的一樣。為了說(shuō)明旋轉(zhuǎn)圖片描述和我們描述之間的不同，我們?cè)诓煌瑘?chǎng)景中使用旋轉(zhuǎn)圖片描述。我們分發(fā)一些旋轉(zhuǎn)圖片在表面上，而且對(duì)每個(gè)旋轉(zhuǎn)圖片描述我們都計(jì)算了它的最佳匹配而不僅僅是一個(gè)匹配。然后我們通過(guò)計(jì)算在相應(yīng)描述中得到最多匹