基于形狀上下文的形狀匹配和目標(biāo)識別

基于形狀上下文的形狀匹配和目標(biāo)識別摘要：我們提出了一種測量圖形間相似性的新方法，并開發(fā)它來做目標(biāo)識別。在我們的架構(gòu)下，相似性的度量之前：1〕解決兩種形式下點(diǎn)與點(diǎn)的對應(yīng)性2〕利用這種對應(yīng)性來估計一個對齊變換。為了解決對應(yīng)問題，我們?yōu)槊恳粋€點(diǎn)附上一個形狀上下文的描述。一個參考點(diǎn)的形狀上下文能捕捉剩下與之相關(guān)的點(diǎn)的分布情況，從而提供全面的可識別的描述。兩個相似圖形上的對應(yīng)點(diǎn)會有相似的形狀語境，使我們將解決對應(yīng)問題看做最優(yōu)分配問題。給出點(diǎn)與點(diǎn)的對應(yīng)，我們估計最正確匹配兩種形狀的變換，為這個用途，正那么化薄板樣條函數(shù)提供了靈活的圖類轉(zhuǎn)換。兩個形狀間的不同通過對應(yīng)點(diǎn)間的匹配誤差總和與測量對齊變換的大小項一起來計算。我們把最近鄰分類架構(gòu)下的識別當(dāng)作在圖像上查找最大限度相似的存儲原型問題，結(jié)果是輪廓線、商標(biāo)、手寫數(shù)字和線圈數(shù)據(jù)集。關(guān)鍵詞:形狀，目標(biāo)識別，數(shù)字識別，對應(yīng)性問題，MPEG7標(biāo)準(zhǔn)，圖像配準(zhǔn)，變形模板1緒論考慮圖1中的兩個手寫體數(shù)字。視為像素亮度值的向量使用二級標(biāo)準(zhǔn)相比，他們有很大的不同。但是，視為形狀，它們顯得和人類的觀察員類似。我們在本文的目的是實(shí)施形狀相似這一概念，其最終目的是用它作為概念層次識別的根底。我們通過一個三階段的過程來實(shí)現(xiàn)：解決這兩個圖形間的對應(yīng)問題使用對應(yīng)關(guān)系來估算對齊變換用對應(yīng)點(diǎn)之間的匹配誤差的總和，加上測量對齊變換的大小，來計算兩個形狀之間的距離我們的做法的關(guān)鍵是傳統(tǒng)的形狀匹配變形，可至少追溯到達(dá)西湯普森。在他的經(jīng)典作品中，對增長和形式[55]，湯普森指出，相關(guān)但不相同的形狀，往往可以使用簡單的坐標(biāo)變換對齊，如圖2所示的變形。在計算機(jī)視覺文獻(xiàn)，費(fèi)什勒和Elschlager[15]實(shí)施了在質(zhì)量彈簧模型中使用mini-mization能源這一想法。Grenander等[21]在概率設(shè)置中開展了這個想法，Yuille[61]通過使用梯度下降的圖像域下的手工制作的擬合參數(shù)化模型，如眼睛，來開展變形模板概念的另一變體。另一個眾所周知的這一脈的計算方法是由Lades[31]等人通過lastic圖匹配開展而來。我們在這項工作的主要奉獻(xiàn)是發(fā)現(xiàn)形狀之間對應(yīng)關(guān)系的強(qiáng)大和簡單的算法。形狀代表了一系列形狀輪廓〔通常為100左右從邊緣探測器輸出采樣的像素位置〕采樣點(diǎn)。這里沒有什么特別的點(diǎn)，它們不需標(biāo)記或曲率極值等，使用的樣本越多，我們獲得越好的近似的根本形狀。我們引進(jìn)一個形狀描述符，形狀上下文，來描述對于給定一個的點(diǎn)的形狀的其他局部的粗分布。兩個形狀之間的對應(yīng)關(guān)系那么相當(dāng)于為一個形狀上每個采樣點(diǎn)找到其他形狀上的最相似形狀上下文。最大化的相似性和執(zhí)行的獨(dú)立性，導(dǎo)致一個二分圖的匹配〔等效，最優(yōu)分配〕問題。根據(jù)需要，我們可以很容易結(jié)合其他匹配的信息來源，例如在對應(yīng)點(diǎn)的本地外觀的相似性。給出采樣點(diǎn)的對應(yīng)關(guān)系，我們通過估計反響一個形狀到另一個形狀的映射的關(guān)系的對齊變換來延長通信完整的形狀。圖2提供了這個想法的一個經(jīng)典說明。轉(zhuǎn)換可以從許多的家系中挑選，在各種應(yīng)用中，我們已經(jīng)使用了歐氏，仿射和正那么化薄板樣條函數(shù)。對齊形狀，簡單定義，就是形狀相似性的衡量。兩個形狀之間的相異現(xiàn)在用對應(yīng)點(diǎn)之間的匹配誤差的總和，加上一個變形轉(zhuǎn)換的幅度來測量。圖1.兩個手寫體數(shù)字的例子。就像素到像素比擬而言，這兩個圖像是相當(dāng)不同的，但是人類的觀察者看到的形狀是相似的。針對這一差異性措施，我們可以使用最近鄰技術(shù)來進(jìn)行目標(biāo)識別。哲學(xué)上，最鄰近技術(shù)與Rosch[47][48]等人開發(fā)的基于原型的識別有關(guān)。它們具備的優(yōu)勢，向量空間結(jié)構(gòu)不是只需要一個成對相異的措施。我們證明了各種各樣設(shè)置下的目標(biāo)識別。我們處理2D對象，例如，手寫數(shù)字的MNIST數(shù)據(jù)集〔圖8〕，輪廓線〔圖11和13〕，以及使用多個視圖建模的哥倫比亞線圈數(shù)據(jù)集中的3D對象〔圖10〕。這些廣泛使用的基準(zhǔn)和我們的方法原來在其中有數(shù)據(jù)比擬的問題中是領(lǐng)先的。我們還開發(fā)了一種基于視覺復(fù)雜性的為每個對象類選擇其存儲視圖的技術(shù)。作為說明，我們在COIL-20數(shù)據(jù)集中的3D對象中表現(xiàn)了，能夠獲得低至2.5%的錯誤分類誤差，只使用每個目標(biāo)對象的4個視圖的平均〔見圖9和10〕。本文的結(jié)構(gòu)如下：我們在第二局部討論相關(guān)的工作，在第三局部詳細(xì)描述形狀匹配的方法，在第四局部展示變換模型。然后，我們在第五局部討論形狀相似性的度量，并在第六局部引用包括手寫體數(shù)字和3D物體圖片在內(nèi)的一系列數(shù)據(jù)集證明我們提出的方法。我們在第七局部進(jìn)行總結(jié)。2形狀匹配的已有工作數(shù)學(xué)家通常定義形狀為一群變換下的一個等價類。這個定義在視覺分析上下文中是不完全的。這只能告訴我們兩個形狀何時是完全相同的。至于形狀相似或形狀距離理論，我們需要的更多。統(tǒng)計學(xué)上定義的形狀，Bookstein[6]或Kendall[29]，假定對應(yīng)關(guān)系是的，致力于形狀距離的問題。其它關(guān)于形狀對應(yīng)的統(tǒng)計學(xué)方法不需要對應(yīng)關(guān)系，例如，人們可以比擬包括描述符號的特征向量，但是這類技術(shù)經(jīng)常在這個過程中丟棄詳細(xì)的形狀信息。形狀相似性也還在心理學(xué)文獻(xiàn)中被研究過，Goldmeier[20]就是早期的一個例子。關(guān)于計算機(jī)視覺方面的形狀匹配的廣泛調(diào)查能夠在[58][22]中找到。概括地說，有兩種方法：1〕基于特征的，這個包括提取特征的空間安排，如邊緣元素或連接點(diǎn)2〕基于亮度的，這使得更直接的使用像素的亮度。2.1基于特征的方法通過使用輪廓線圖像的邊界，已經(jīng)做了大量關(guān)于形狀相似性的研究。由于輪廓線沒有孔或內(nèi)部標(biāo)記，相關(guān)邊界可以方便的用弧長參數(shù)表示一個單一的封閉曲線來表示。早期的工作中使用傅里葉描述符，例如，[62][43]。Blum的中軸變換，導(dǎo)致試圖捕捉在Kimia，Zucker和Sharvit[53]等合作者的圖形結(jié)構(gòu)骨架中的形狀的局部結(jié)構(gòu)。1D輪廓線曲線的性質(zhì)自然地導(dǎo)致動態(tài)規(guī)劃方法的匹配，例如，[17]，它采用曲線間的編輯距離。對包括一些清晰度和閉塞的幾種變換，該算法是快速和不變的。做為MPEG-7標(biāo)準(zhǔn)的活動的一局部[33]，綜合比擬了不同形狀描述符來比擬的輪廓線，用由于Latecki等[33]和Mokhtarian[39]等領(lǐng)先的方法。圖2.從D'Arcy湯普森的生長形式[55]，有關(guān)坐標(biāo)變換的兩條魚的例子。湯普森觀察到類似的可能與生物形式之間的同源簡單的數(shù)學(xué)變換手段〔即對應(yīng)〕功能。同源功能的例子包括眼中心，背鰭尖端等。輪廓線是從根本上作為一般物體的性質(zhì)描述的限制；他們無視了內(nèi)部的輪廓，很難從真實(shí)的圖像中提取。更有前景的方法是把形狀當(dāng)作一套在二維圖像里的點(diǎn)。從一張圖像上提取這些算不了什么問題，例如，可以只使用一個邊緣檢測器。Hutten-locher等開發(fā)基于Hausdorff距離[23]的方法，這可擴(kuò)展到處理局部匹配和雜波。我們的目的的一個缺點(diǎn)是，該方法不返回對應(yīng)關(guān)系?；诰嚯x變換的方法，如[16]，在實(shí)踐中的精神和行為是相似的。Sclaroff和彭特蘭的工作[50]代表特征向量或基于模式匹配的方法，見[52][51][57]。在這種方法中，圖像中的樣本點(diǎn)轉(zhuǎn)換為有限元彈簧-質(zhì)點(diǎn)模型，對應(yīng)關(guān)系通過比擬振動模式發(fā)現(xiàn)。和我們的做法最密切相關(guān)的是Goldetal.[19]，Chui和Rangarajan[9]的工作，這將在第3.4局部討論。有幾種基于空間結(jié)構(gòu)的一小局部要點(diǎn)或界標(biāo)的方法可以進(jìn)行形狀識別。在幾何哈希[32]中，這些配置用于投票給沒有明確解決對應(yīng)關(guān)系的模型。阿米特[1]等人通過學(xué)習(xí)有判別力的空間配置關(guān)鍵點(diǎn)來訓(xùn)練識別決策樹。Leung[35]等人，Schmid和Mohr[49]此外使用在關(guān)鍵點(diǎn)的灰度級的信息以提供更大的區(qū)分力。應(yīng)該指出，并不是所有的對象都有可分辨的關(guān)鍵點(diǎn)〔例如考慮一個圓〕，單獨(dú)使用關(guān)鍵點(diǎn)犧牲了在對象輪廓平滑局部可利用的形狀信息?；诹炼鹊姆椒ɑ诹炼取不蛲庥^〕的方法提供了一個基于特征的方法的互補(bǔ)。與其側(cè)重于咬合輪廓的形狀或其他提取的特征，這些方法在對象的可見局部直接使用灰度值。人們可以在兩個框架之一使用亮度信息。在第一類中，我們有方法使用灰度值來明確地對應(yīng)關(guān)系/對齊。Yuille[61]提出了一個非常靈活的方法，特定種類變換的不變性可以構(gòu)造成衡量模型的相似性，但當(dāng)通過梯度下降搜尋時，它需要人類設(shè)計的模板和對初始化的敏感性。Lades[31]等人使用彈性圖匹配，這種方法涉及基于高斯衍生以局部描述符形式的幾何和光學(xué)特性。Vetter[59]等人和Cootes[10]等比擬亮度值，但是首次嘗試使用密集的對應(yīng)關(guān)系領(lǐng)域變形到另一個圖像。第二類包括沒有明確找到對應(yīng)關(guān)系的建立分類的方法。這種方法，依賴于一個有足夠的例子的學(xué)習(xí)算法獲得相應(yīng)的不變性。在人臉識別領(lǐng)域，特別是在概率框架下使用，采用主成分分析〔PCA〕[54][56]，獲得了好的效果。Murase和Nayar將這些想法應(yīng)用到3D物體識別。一些作者已經(jīng)在基于外觀的形狀匹配框架下應(yīng)用有判別力的分類方法。3帶形狀上下文的匹配在我們的方法中，我們把一個對象作為一個點(diǎn)集〔可能是無限的〕，我們假設(shè)物體的形狀根本上是由其點(diǎn)的一個有限子集捕獲。實(shí)際上，一個形狀可用其內(nèi)部或外部輪廓采樣點(diǎn)的離散集合來表示。這些可獲得邊緣探測器發(fā)現(xiàn)的邊緣像素的位置，已給我們一套n個點(diǎn)，p={p,…p},p∈R。他們不需要，通常不會對應(yīng)關(guān)鍵點(diǎn)，如極大地曲率或拐點(diǎn)。我們寧愿樣品形狀大致均勻間距的，雖然這也不是關(guān)鍵。圖3a和3b顯示兩個形狀的采樣點(diǎn)。假設(shè)輪廓分段光滑，只要挑選的n足夠大，我們可以如愿得到一個良好的逼近底層的連續(xù)形狀。形狀上下文對于第一個形狀上的每一個點(diǎn)p，我們要在第二個形狀上找到最正確匹配點(diǎn)q，這是一個類似立體的對應(yīng)問題。經(jīng)驗(yàn)也說明，如果使用豐富的局部描述符號，例如，灰度窗口或?yàn)V波器輸出的矢量[27]，而不是僅僅是單個像素的亮度或邊緣的位置，匹配更容易。豐富的描述符減少模棱兩可的匹配。作為一個重要的奉獻(xiàn)，我們提出了一個新的描述符，形狀上下文，可以在形狀匹配中發(fā)揮這樣的作用?？紤]從始發(fā)點(diǎn)到形狀所有其他采樣點(diǎn)的向量。這些向量表達(dá)了相對參考點(diǎn)的整個形狀的配置。顯然，這n-1個向量是一個豐富的描述，因?yàn)閚變大，形狀的表示形式越確切。作為形狀描述符，全套的向量過于詳細(xì)，因?yàn)樵谝粋€類別中形狀和采樣的表示形式可能會有所不同。作為一個更強(qiáng)大、緊湊且有高度判別力的描述符，我們確定相對位置分配。對于形狀上的一個點(diǎn)p，我們計算出余下n-1個點(diǎn)的相對坐標(biāo)粗的直方圖h，.(1)這個直方圖被定義為點(diǎn)p的形狀上下文。我們使用統(tǒng)一的2維對數(shù)極坐標(biāo)箱，使得附近樣本點(diǎn)的位置描述符比更遠(yuǎn)樣本點(diǎn)的位置描述符更為敏感。圖3c就是一個例子。圖3.形狀上下文計算和匹配?！瞐〕和〔b〕采樣兩個形狀的邊緣點(diǎn)?！瞔〕計算形狀上下文的對數(shù)極坐標(biāo)直方圖圖解。我們是有5種logr和12種。〔d〕(e)(f)在〔a〕〔b〕中以○

△標(biāo)記的采樣點(diǎn)的形狀上下文范例。每個形狀上下文是一個以參考點(diǎn)為原點(diǎn)，測量其余點(diǎn)的對數(shù)極坐標(biāo)坐標(biāo)系直方圖?！舶?大值〕注意○和

形狀上下文的視覺相似性，這用于兩個形狀上相對相似點(diǎn)的計算。作為比照，△的形狀上下文完全不同?！瞘〕對應(yīng)使用二分匹配，由直方圖之間的x距離定義本錢?？紤]第一個形狀上的點(diǎn)p和第二個形狀上的點(diǎn)q。設(shè)C=C〔p，q〕表示符合這兩點(diǎn)的本錢。由于形狀上下文作為直方圖代表的分布，很自然地使用x檢驗(yàn)統(tǒng)計：,這里，h(k)和h(k)分別表示p和q的K-bin正那么化直方圖。匹配點(diǎn)的本錢可以包括一個在點(diǎn)p和q基于局部外觀相似性的額外項。當(dāng)我們比擬的形狀來自灰度級圖像而不是線條圖形時，這是特別有用的。例如，可以添加以p和q為中心的小灰度曲線之間的基于歸一化相關(guān)分?jǐn)?shù)的本錢，點(diǎn)p和q處濾波器輸出向量之間的距離，點(diǎn)p和q之間切線方向的不同，以此類推。選擇這個外觀相似項依賴于應(yīng)用，由必要的不變性和魯棒性要求驅(qū)動，例如，不同的照明條件使依賴于灰度的亮度值冒險。二分圖匹配鑒于所有成對的第一個形狀上的點(diǎn)p和第二個形狀上的點(diǎn)q的本錢集，我們想盡量減少匹配的總本錢，(2)受約束的匹配是一對一的匹配，即，是一個排列。這是一個平方配置〔或加權(quán)二部圖匹配〕問題的實(shí)例，使用Hungarian方法[42]可以在時間復(fù)雜度O(n)內(nèi)解決。在我們的實(shí)驗(yàn)中，我們使用更有效地算法[28]。配置問題的輸入是一個包含C條目的平方本錢矩陣，結(jié)果是使式〔2〕最小化的一個排列。為了有強(qiáng)大的離群值處理能力，在匹配本錢恒定的情況下，為每個點(diǎn)添加“虛擬〞點(diǎn)集。在這種情況下，不管有沒有真正匹配的比更小的本錢，一個點(diǎn)將被匹配到一個“虛擬〞。因此可視為一個門檻異常檢測參數(shù)。同樣，當(dāng)兩個形狀上的采樣點(diǎn)數(shù)目不同時，本錢矩陣可通過給點(diǎn)數(shù)目較少的形狀增加虛擬節(jié)點(diǎn)來創(chuàng)造。不變性和魯棒性一個匹配的方法應(yīng)為1〕縮放和平移不變性2〕小幾何變形、閉塞和存在離群值的魯棒性。在些應(yīng)用中，可能要完成旋轉(zhuǎn)不變性，或者甚至全組的仿射變換。我們現(xiàn)在用這些標(biāo)準(zhǔn)來評估形狀上下文匹配。平移不變性是形狀上下文內(nèi)在的定義，因?yàn)樗械臏y量是對對象上的點(diǎn)采取的。為實(shí)現(xiàn)模型的不變性，我們用形狀上n對點(diǎn)之間的平均距離歸一化徑向距離。由于形狀上下文是極為豐富的描述符，他們本質(zhì)上對形狀上的局部小擾動不敏感。雖然我們這里沒有理論保證，小的非線性變換，閉塞和存在離群值的魯棒性在第4.2局部被通過實(shí)驗(yàn)評估。在形狀上下文框架，如果這是應(yīng)用需求的，我們可以提供完整的旋轉(zhuǎn)不變性。取代使用絕對框架計算每個點(diǎn)的形狀上下文，我們可以使用相對框架，基于將每個點(diǎn)的切向量當(dāng)做正x軸。這樣，參照系根據(jù)切線角度轉(zhuǎn)動，結(jié)果是一個完全旋轉(zhuǎn)不變描述符。在附錄A中，我們在實(shí)驗(yàn)上證明了這一點(diǎn)。應(yīng)該強(qiáng)調(diào)，在許多應(yīng)用中，完全的不變性阻礙識別性能，例如，區(qū)分6、9時，旋轉(zhuǎn)不變性將會完全不恰當(dāng)。另一個缺點(diǎn)是，許多點(diǎn)不會有明確界定的或可靠地切線。此外，如果不是在同一坐標(biāo)系測量，許多局部外觀特征將失去區(qū)分力。附加到離群值的魯棒性，可以通過從它的形狀上下文計算中排除估計離群值來獲得。更具體地說，考慮一個被貼上給定迭代的點(diǎn)集。我們提供這些“隱形〞的點(diǎn)，不允許它們?yōu)橹狈綀D做出任何奉獻(xiàn)。但是，我們?nèi)匀环峙浣o他們形狀上下文，考慮到只有周圍內(nèi)層的點(diǎn)，使它們在以后的迭代中有時機(jī)作為內(nèi)層再度出現(xiàn)。相關(guān)工作在這個一般設(shè)置中，關(guān)于形狀對應(yīng)的最綜合的工作是Gold等人[19]和Rangarajan[9]的工作。他們開發(fā)了一個迭代優(yōu)化算法，以確定點(diǎn)對應(yīng)關(guān)系和連帶的底層圖像轉(zhuǎn)換，通常假設(shè)一些通用轉(zhuǎn)換；類，如仿射或薄板樣條。最小化的本錢函數(shù)是第一個形狀上的點(diǎn)和轉(zhuǎn)換的第二個形狀之間的歐式距離的總和。這將產(chǎn)生一個雞和蛋的問題：只有當(dāng)至少有一個形狀的粗校準(zhǔn)，距離才有意義。聯(lián)合估計的對應(yīng)關(guān)系和形狀轉(zhuǎn)換導(dǎo)致一個難的高度非凸優(yōu)化問題，這用確定性退火[19]可以解決。形狀上下文是一個非常有判別力的點(diǎn)描述符，通過將全部形狀信息納入本地描述符來促進(jìn)簡單和可靠地對應(yīng)關(guān)系恢復(fù)。據(jù)我們所知，形狀上再問和其用于2D形狀匹配是新穎的，在過去的工作中關(guān)系最密切的想法是約翰遜和赫伯特[26]在范圍圖像的工作。他們提出了一個表示3D點(diǎn)的致密匹配云，被稱為“自旋圖像〞。自旋圖像是一個2D直方圖，由在一個平面上旋轉(zhuǎn)的對象外表的法線向量和計數(shù)下跌在平面內(nèi)的點(diǎn)個數(shù)組成。由于這個平面的規(guī)模相對較小，由此產(chǎn)生的有特征的符號不如作為用于恢復(fù)對應(yīng)關(guān)系的形狀上下文內(nèi)容豐富。然而這個特性，可能有額外的魯棒性閉塞的權(quán)衡。另一項相關(guān)的工作，Carlsson[8]為表征局部形狀配置，利用了秩序結(jié)構(gòu)的概念。在這項工作中，點(diǎn)和形狀的切線之間的關(guān)系用于恢復(fù)對應(yīng)關(guān)系。4建模轉(zhuǎn)換提供有限的兩個形狀的點(diǎn)之間的對應(yīng)關(guān)系集，就可以得到一個平面轉(zhuǎn)換估計，可以用來將任一點(diǎn)映射到另一個形狀。這個想法由圖2中扭曲的網(wǎng)格線說明，這里指定的對應(yīng)關(guān)系包括少量的標(biāo)記點(diǎn)，如眼中心，背鰭的尖端等，并且T延伸到任意點(diǎn)的對應(yīng)。我們需要從一個適宜的轉(zhuǎn)換家系選擇T。一個標(biāo)準(zhǔn)的選擇是仿射模型，即(3)一些矩陣A和一個平移偏移向量o參數(shù)化所有允許轉(zhuǎn)換集。然后，最小二乘解=(,)可通過以下獲得,(4),(5)其中，P和Q包含P和Q的齊次坐標(biāo)，即.(6)這里，Q代表Q的偽逆。在這個工作中，我們大多使用薄板樣條〔TPS〕模型[14][37]，這通常用于較靈活的坐標(biāo)轉(zhuǎn)換。Bookstein[6]發(fā)現(xiàn)它可以高效模擬生物形式的變化。Powell應(yīng)用TPS模型以恢復(fù)曲線[44]之間的轉(zhuǎn)換。薄板樣條是三次樣條的2D推廣。TPS模型包括作為特殊情況的仿射模型，其正那么化的形式將在下面討論?，F(xiàn)在，我們將提供TPS模型的一些背景資料。我們從一維差值問題開始。讓v表示在平面上相應(yīng)位置p=〔x,y〕的目標(biāo)函數(shù)值，其中i=1,2…,n。特別的，我們將設(shè)置v等于x和y以反過來為每個坐標(biāo)獲取一個連續(xù)的轉(zhuǎn)換。我們假定位置〔x,y〕全都不相同而且不共線。TPS插值函數(shù)f(x,y)最大限度的減少彎曲的能量并且有以下形式：,其中核心函數(shù)U〔r〕被定義為U(r)=rlogr且U(0)=0。為了使f(x,y)的二階導(dǎo)數(shù)平方可積，我們需要and.(7)連同插值條件f(x,y)=v,將生成TPS系數(shù)線性系統(tǒng)：(8)其中，K=U〔〕,P的第i行是〔1，x,y〕，w和v是分別從w和v形成的列矢量，a是含有元素a，a和a的列向量。我們將用L表示這個系統(tǒng)〔n+3〕*(n+3)的矩陣。討論，例如，在[44]，L是奇異地，我們可以.(9)通過反轉(zhuǎn)L找到解決方法。如果我們用A表示左上部L的n*n塊，然后可以表示：4.1正那么化和標(biāo)度行為當(dāng)在指定的值v處有噪聲，不妨通過正那么化放寬確切的插值要求。這通過最小化下式完成.(10)正那么化參數(shù)是一個正標(biāo)量，控制平滑量；=0的極限情況將減少確切的插值。[18][60]說明，在正那么化情況下，我們可以通過用K+I替代K來解決TPS系數(shù)，其中I是n*n的恒等矩陣。值得注意的是，高度正那么化的TPS模型簡并最小二乘仿射模型。為解決數(shù)據(jù)集上的依賴關(guān)系，假設(shè)用〔x,y〕〔x,y〕分別替代〔x,y〕〔x,y〕,積極地常數(shù)。然后，它說明，如果改為，最優(yōu)薄板樣條的參數(shù)w,a和I不受影響。這個簡單的縮放行為說明了正那么化參數(shù)的歸一化定義。讓再次代表該點(diǎn)的規(guī)模，設(shè)置為集中的兩個點(diǎn)之間的平均邊長度的估計。然后，我們可以通過和定義一個獨(dú)立于規(guī)模的正那么化參數(shù)，有簡單的關(guān)系=。我們使用兩個單獨(dú)的TPS函數(shù)來進(jìn)行坐標(biāo)變換建模，〔11〕其中產(chǎn)生的位移場，從第一個圖像的任何位置映射到第二個圖像的插值位置。在許多情況下，對應(yīng)關(guān)系的初步估計包含了一些錯誤，這可能會降低轉(zhuǎn)換估計的質(zhì)量。為了解決這個問題，可以迭代對應(yīng)關(guān)系恢復(fù)和估算的步驟。我們通常使用固定數(shù)量的迭代，通常是三個，但在大規(guī)模的實(shí)驗(yàn)中可能有更精細(xì)的方案。不過，實(shí)驗(yàn)性經(jīng)驗(yàn)說明算法的性能獨(dú)立于詳細(xì)信息。圖4是迭代算法的一個例如。經(jīng)驗(yàn)魯棒性評估為了研究我們提出的方法的魯棒性，我們進(jìn)行了如[9]中所述的合成點(diǎn)匹配實(shí)驗(yàn)。實(shí)驗(yàn)分為三個局部的設(shè)計來衡量變形、噪聲和離群值的魯棒性〔后來的每個測試都包括一個“適度〞變形量〕。在每個測試中，我們用含上述扭曲的模型點(diǎn)集創(chuàng)立一個“目標(biāo)〞點(diǎn)集，見圖5。然后，我們運(yùn)行我們的算法，在模型和目標(biāo)之間找到最正確的翹曲。最后，性能通過計算扭曲模型和目標(biāo)之間的平均距離來量化。結(jié)果如圖6所示。在測試離群值實(shí)驗(yàn)最具挑戰(zhàn)性的局部，我們的方法說明魯棒性甚至到達(dá)了100%的離群值對數(shù)據(jù)的比例水平。在實(shí)踐中，我們將需要只在一個完整的識別系統(tǒng)中探索的閉塞和分割錯誤的魯棒性，但這些實(shí)驗(yàn)至少提供一些指導(dǎo)。計算需求我們實(shí)行定期的奔騰III/500MHz工作站，一個包括3個周期的100個采樣點(diǎn)的形狀上下文的計算、建立全部的匹配矩陣、二分圖匹配、TPS系數(shù)計算和圖像變形的比擬大約需要200毫秒。運(yùn)行時間主要是受控于每個形狀的采樣點(diǎn)數(shù)目，與二次、三次縮放行為之間表現(xiàn)的算法的大多數(shù)組件。一旦形狀大致對齊，整個使用稀疏表示，復(fù)雜性可以接近線性。圖4應(yīng)用于圖1中的匹配過程圖示。第一行：1級迭代，底部行：5級迭代。左列：估計相對于轉(zhuǎn)換模型的對應(yīng)關(guān)系，用切向量顯示。中間列：顯示相對于未轉(zhuǎn)換模型的估計對應(yīng)關(guān)系。右列：基于當(dāng)前對應(yīng)關(guān)系的模型轉(zhuǎn)換結(jié)果，這是下一次迭代的輸入。網(wǎng)格上的IR說明插值的轉(zhuǎn)換，在這里，我們使用一個=1的正那么化的TPS模型。5目標(biāo)識別和原型選擇給定形狀之間的差異性測量，我們即將對其進(jìn)行精確地測量，我們可以繼續(xù)把它應(yīng)用于對象識別的任務(wù)。我們的方法屬于基于原型的識別。在這一框架下，由Rosch[48]等人率先，類別由理想的例子來代表，而不是一套正式的邏輯規(guī)那么。作為一個例子，麻雀可能是鳥類別的原型，不太可能的選擇是企鵝。原型的想法允許軟類別的成員資格，這意味著在一些適當(dāng)定義的相似性空間，一旦移動的遠(yuǎn)離理想例子，與原型的關(guān)聯(lián)便脫落。當(dāng)離原型足夠遠(yuǎn)時，距離就變得毫無意義，但最有可能接近一個不同的原型。作為一個例子，我們可以說好或馬馬虎虎的紅顏色的例子，但當(dāng)顏色變得足夠不同，相異飽和度水平會到達(dá)一些最大水平，而不是無限期的繼續(xù)。基于原型的識別很容易轉(zhuǎn)化為使用多個存儲的試圖的最近鄰方法計算框架。當(dāng)訓(xùn)練集中的例子n趨于無窮大，最近鄰分類器具有1-NN錯誤會聚為一個不大于E的2倍的值的屬性，其中E是貝葉斯風(fēng)險〔對于K-NN，K趨于無窮大，K/n趨于0，錯誤趨于E〕。這是有趣的，因?yàn)樗f明了最近鄰分類器是漸進(jìn)最優(yōu)的，屬性不具有幾種更為復(fù)雜的技術(shù)。當(dāng)然，在實(shí)踐中，重要的是小n的性能，這給了我們一個比擬不同的相似性/距離措施的方法。形狀距離在本節(jié)中，我們進(jìn)行精確地形狀距離的定義，并將其應(yīng)用到幾個實(shí)際問題。我們用正那么化的TPS和三個形狀上下文匹配迭代和TPS重估。匹配后，我們估計形狀距離的加權(quán)和的三個方面：形狀上下文距離，圖像外觀距離和彎曲能量。我們衡量形狀P和Q之間的最正確匹配點(diǎn)對稱形狀上下文匹配的本錢總和的形狀上下文距離，即,(12)其中，T(·)表示TPS形狀轉(zhuǎn)換的測量。[9]，經(jīng)驗(yàn)魯棒性估計的測試數(shù)據(jù)。在第一列顯示模型的點(diǎn)集。2-4列分別顯示目標(biāo)點(diǎn)集的變形，噪聲和離群點(diǎn)測試。圖6.比擬我們的結(jié)果〔□〕與Chui和Rangarajan的結(jié)果〔*〕，分別迭代魚和中文字符的最近點(diǎn)〔○〕。誤差線顯示100個隨機(jī)實(shí)驗(yàn)的錯誤的標(biāo)準(zhǔn)偏差。這里，我們使用了=1.0情況下的5次迭代。在變形和噪聲測試中沒有添加虛擬節(jié)點(diǎn)。在離群值測試中，虛擬節(jié)點(diǎn)被添加到模型點(diǎn)集中，這樣節(jié)點(diǎn)總數(shù)和目標(biāo)是相同的。在這種情況下,的值不影響解決方法。在許多應(yīng)用中有額外的我們的形狀概念不捕獲的外觀信息可用，例如，在灰度圖像中的紋理和顏色信息修補(bǔ)周圍對應(yīng)的點(diǎn)。外觀信息的可靠性往往由于幾何圖像扭曲受損。然而，建立圖像對應(yīng)關(guān)系和恢復(fù)底層2D圖像變換后，扭曲的圖像可以被扭回成一個正常的形式，從而可以糾正牛武的圖像外觀。我們使用D(P,Q)表示外觀本錢，定義為相應(yīng)的圖像點(diǎn)周圍的高斯窗口亮度差異平方的總和，,(13)其中，I和I分別表示對應(yīng)P和Q的灰度級圖像?！鞅硎疽恍┎钍噶科?，G是一個窗口函數(shù)，通常選擇高斯，因此強(qiáng)調(diào)附近的像素。因此，我們總和窗口中相應(yīng)點(diǎn)的平方差，得到加權(quán)灰度級相似性分?jǐn)?shù)。這個分?jǐn)?shù)是薄板樣條變換T已經(jīng)應(yīng)用到最好的變形圖像對齊后計算的。第三項相當(dāng)于需要對齊形狀的變換的“量〞。在TPS情況下，彎曲能量〔9〕是一種固有的措施〔見[5]〕。原型選擇在基于原型的方法中，關(guān)鍵的問題是：我們應(yīng)該存儲哪些例子？不同的類別需要不同的視圖。例如，某些手寫體數(shù)字比其它的有更多的可變性，如，人們通常認(rèn)為4比0有更多的變化。在3D對象的類別中，一個領(lǐng)域只需要一個視圖，例如，需要假設(shè)干視圖以捕捉各種視覺外觀。這個想法與在[30]中討論的“層面〞概念有關(guān)。現(xiàn)在我們將討論如何處理原型選擇問題。在最近鄰分類的文獻(xiàn)中，典范選擇問題就是所謂的編輯。最近鄰的編輯方法的廣泛審查可以在Ripley[46]和Dasarathy[12]發(fā)現(xiàn)。我們已經(jīng)開發(fā)處一種基于形狀距離和K-medoids聚類的新穎的編輯算法。K-medoids可以看作是根據(jù)數(shù)據(jù)點(diǎn)限制原型位置的K-means的變形。首先計算所有可能原型之間的成對相似性矩陣。對于一個給定K原型數(shù)，K-medoids算法迭代兩個步驟：1〕對于一個給定的點(diǎn)〔抽象〕來聚簇一個新原型，集群中的所有元素，通過最小化原型平均距離來選擇2〕給定原型集，然后點(diǎn)被重新分配到最近的原型。更正式的是，c(P)表示形狀P的〔抽象〕集群，例如，一些數(shù)字{1，…，k}表示形狀P，p(c)表示相關(guān)的原型。這樣，我們有一個類映射(14)和一個原型映射.(15)這里，S和S是所有潛在的形狀S的集合的一些子集。通常，S=S=S。K-medoids由迭代兩個步驟進(jìn)行：S類組成原型p(c)為集群中元素的每個類確定一個有代表性的原型圖7.MNIST數(shù)據(jù)集上的手寫體數(shù)字識別。左邊：使用SSD和形狀距離〔SD〕措施的的1-NN分類測試集錯誤。右邊：詳細(xì)的形狀距離的性能曲線，包括結(jié)果，用大小15000和20000的訓(xùn)練集。至于K=1,3,5的最近鄰的結(jié)果顯示在半對數(shù)-x標(biāo)尺上。根本上，通過分配每個形狀PS到最近的原型解決第一項，因此， 〔16〕對于給定的類，在第二項，基于最小平均相異性選擇新的原型，即〔17〕由于這兩個步驟最小化相同的本錢函數(shù)，〔18〕該算法必然收斂到一個〔局部〕最小。與大多數(shù)的聚類方法一樣，k-medoids必須要有一個戰(zhàn)略來選擇k。我們使用一個貪婪的分裂策略選擇原型的數(shù)量，從每個類別一個原型開始。我們基于相關(guān)的整體分類誤差來選擇集群進(jìn)行分裂。這將一直持續(xù)到整體分類誤差低于標(biāo)準(zhǔn)水平。因此，原型是自動分配到不同的對象類，因此，優(yōu)化使用現(xiàn)有的資源。3D對象的一套視圖中的應(yīng)用，并在圖10所示。6案例研究數(shù)字識別在此，我們給出MNIST數(shù)據(jù)集上手寫體數(shù)字的結(jié)果，其中包括60000訓(xùn)練和10000測試數(shù)字[34]。在實(shí)驗(yàn)中，我們使用100個Canny邊緣的采樣點(diǎn)來代表各數(shù)字。當(dāng)計算二分匹配的C時，我們包括了表示局部切線角度差異的一項。具體地說，我們定義匹配本錢為C=〔1-〕C+C，其中C是形狀上下文本錢，C=0.5(1-cos(度量切線角度差異，且=0.1。為了識別，我們使用一個K-NN分類器，其距離函數(shù)為.(19)式〔19〕中的權(quán)重由訓(xùn)練數(shù)據(jù)上的一個3000*3000的子集的leave-one-out過程得到了優(yōu)化。已經(jīng)比擬了MNIST數(shù)據(jù)集上的近30種算法。這時候公布的最低的測試集錯誤率是提升LeNet-4的0.7%，每個訓(xùn)練數(shù)字有大小為60000*10的合成扭曲的訓(xùn)練集。我們使用20000訓(xùn)練例子和3-NN的錯誤率是0.63%。圖8顯示63個錯誤。如前所述，在最近鄰方法的實(shí)際應(yīng)用中最重要的是小n時的性能，這給了我們一個比擬不同相似性/距離措施的方法。圖7〔左〕，形狀距離與SSD〔像素亮度值的平方差的總和〕相比。圖7〔右〕，比擬不同K值的分類率。6.23D目標(biāo)識別我們的下一個實(shí)驗(yàn)涉及來自COIL-20數(shù)據(jù)庫[40]的20種常見的家用物品。每個對象都被放在一個轉(zhuǎn)盤上，并每隔5共拍下72個視圖。我們通過為每個對象選擇一些等距的視圖來準(zhǔn)備訓(xùn)練集，剩下的視圖用于測試。匹配算法和數(shù)字完全相同。回想一下，Canny邊緣檢測器響應(yīng)外部和內(nèi)部的輪廓，因此100個采樣點(diǎn)不局限于輪廓的外部邊界。圖9顯示比擬使用包括如〔19〕所示的距離函數(shù)D的1-NN和直接使用平方差的總和〔SSD〕的性能。由于光照下變化缺乏，SSD在這個簡單的數(shù)據(jù)庫上表現(xiàn)非常好。圖10所示的是原型選擇算法。正如所看到的，視圖主要用于類別變異性高的更復(fù)雜的類別。圖9中標(biāo)記SC-proto的曲線顯示了改善的分類性能，使用這個原型選擇策略而不是等距的觀點(diǎn)。請注意我們獲得了2.4%的錯誤率，平均每個3維對象只有4個2維視圖，多虧了匹配算法的靈活性。圖8.用我們的方法，所有錯誤分類的MNIST測試數(shù)字。每個數(shù)字上面的文本表示真正的標(biāo)簽和分配的標(biāo)簽后的例如數(shù)。圖9.使用COIL-20數(shù)據(jù)集的3D目標(biāo)識別。比擬SSD，形狀距離〔SD〕和與原型視圖相對的以k-medoids為原型的形狀距離〔SD-proto〕的測試集錯誤。對于SSD和SD，我們統(tǒng)一改變了所有對象的原型數(shù)量。對于SD-proto，每個對象的原型數(shù)量取決于對象內(nèi)和對象間的相似性。MPEG7標(biāo)準(zhǔn)的形狀輪廓線數(shù)據(jù)庫圖10.使用5.2局部描述的算法，為COIL數(shù)據(jù)集中的兩個不同的3維對象選擇原型視圖。通過這個方法，視圖的分配取決于一個對象關(guān)于視角的視覺復(fù)雜度。我們的下一個實(shí)驗(yàn)涉及MPEG-7形狀輪廓數(shù)據(jù)庫，特別是核心實(shí)驗(yàn)CE-Shape-1的B局部，衡量基于相似性恢復(fù)[25]的性能。該數(shù)據(jù)庫包括1400個圖形：70個形狀類別，每個類別20個圖像。使用所謂的“靶心測試〞衡量性能，其中每個圖像作為一個查詢，然后在前40個匹配中計數(shù)正確的圖像。圖11.MPEG7數(shù)據(jù)庫中三個不同類別的形狀的例子。由于本實(shí)驗(yàn)涉及復(fù)雜的形狀，樣本數(shù)量從100增加到300。在某些類中，形狀出現(xiàn)了旋轉(zhuǎn)和翻轉(zhuǎn)，我們通過使用一個修改后的距離函數(shù)來解決。參考形狀R和一個查詢形狀Q之間的距離dist(R,Q)定義為，其中，R，R和R表示R的三個方面：不變，垂直翻轉(zhuǎn)和水平翻轉(zhuǎn)。這些變化的地方，但以其它的方式使用MNIST數(shù)字實(shí)驗(yàn)中同樣的方法，我們獲得76.51%的檢索速度。目前公布的最正確性能由Latecki[33]等人實(shí)現(xiàn)，檢索率為76.45%，隨后是Mokhtarian等的75.44%。商標(biāo)檢索商標(biāo)在視覺上往往最好描述它們的形狀信息，而且在許多情況下，形狀提供了唯一的信息來源。自動識別商標(biāo)侵權(quán)是有趣的工業(yè)應(yīng)用，因?yàn)槟壳暗乃囆g(shù)商標(biāo)根據(jù)Vienna編碼大致分類，然后再根據(jù)它們的感知相似性手動分類。即使形狀上下文匹配不提供商標(biāo)相似性問題〔其他潛在的線索是文字和紋理〕的完整解決方案，但它仍可以很好的說明我們的方法捕捉形狀相似性的本質(zhì)的能力。