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

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