外文翻譯--一種用于非剛性點(diǎn)定位的新匹配算法（譯文）

1、中文 中文 13500 字出處： 出處：Chui H, Rangarajan A. A new point matching algorithm for non-rigid registration[J]. Computer Vision & Image Understanding, 2003, 89(2–3):114-141.一種用于非剛性點(diǎn)定位的新匹配算法 一種用于非剛性點(diǎn)定位的新匹配算法Chui H, Rangaraja

2、n A *美國(guó)加利福尼亞州森尼維爾市 R2 科技區(qū)，郵編 94087*美國(guó)佛羅里達(dá)大學(xué)計(jì)算機(jī)與信息科學(xué)與工程系蓋恩斯維爾實(shí)驗(yàn)室， 電話 32611-612 2002 年 3 月 5 日收到；2002 年 10 月 15 日收錄摘要： 摘要：基于特征的非剛性定位方法經(jīng)常遇到匹配問(wèn)題。無(wú)論使用的是點(diǎn)，線，曲線還是表面參數(shù)化，基于特征的非剛性匹配都需要我們自動(dòng)求解兩組特征之間的匹配關(guān)系。此外，可能有許多特征只存在于一組內(nèi)，

3、而另一組沒(méi)有對(duì)應(yīng)的特征。這個(gè)暴露出的問(wèn)題使這個(gè)已經(jīng)很困難的匹配問(wèn)題更加復(fù)雜化。我們考慮把這種基于特征的非剛性定位看作一個(gè)非剛性點(diǎn)匹配問(wèn)題。仔細(xì)審查了這個(gè)問(wèn) 題，并深入了解了以前為剛性點(diǎn)匹配（RPM）設(shè)計(jì)的兩種方法，我們?yōu)榉莿傂渣c(diǎn)匹配提出了一種新的框架。我們認(rèn)為它是一種普遍適用的框架，因?yàn)樗灰蕾?lài)于任何特定形式的空間分布。我們還開(kāi)發(fā)了一種算法：TPS-RPM 算法。TPS-RPM 算法使用薄板樣條（TPS）進(jìn)行非剛性空間分布的參數(shù)化和對(duì)準(zhǔn)

4、的軟分配。在一系列精心設(shè)計(jì)的合成實(shí)驗(yàn)中，TPS-RPM 算法的性能得到充分證明和驗(yàn)證。在每個(gè)實(shí)驗(yàn)中，還提供了與流行的迭代最近點(diǎn)（ICP）算法的比較。最后，將算法應(yīng)用于大腦映射中所需的皮質(zhì)解剖結(jié)構(gòu)的非剛性匹配問(wèn)題。在有了一些初步成果的同時(shí)，它們清楚地表明了我們提供的方法在現(xiàn)實(shí)生活里涉及基于特征的非剛 性定位的適用性。1. 1. 介紹 介紹 在計(jì)算機(jī)視覺(jué)和醫(yī)學(xué)影像領(lǐng)域經(jīng)常出現(xiàn)基于特征的定位問(wèn)題。由于兩個(gè)圖 像中的顯著結(jié)構(gòu)表現(xiàn)為緊湊的幾何實(shí)體

5、（例如，點(diǎn)，曲線和曲面），所以定位問(wèn)題是在兩組特征之間找出最佳的或次優(yōu)空間變換/映射。位置特征是點(diǎn)特征中 最簡(jiǎn)單的形式。它通常作為其他更復(fù)雜圖形（如曲線，曲面）的基礎(chǔ)。在這個(gè)角度上，它也被認(rèn)為是所有特征中最基本的形式。然而，單獨(dú)使用基于點(diǎn)特征 的定位可能是相當(dāng)不利的。一個(gè)常見(jiàn)的因素是來(lái)自圖像采集和特征提取過(guò)程中產(chǎn)生的噪聲。噪聲的存在意味著所得到的特征點(diǎn)不能精確匹配。另一個(gè)因素是異常值的存在－許多點(diǎn) 特征可能只存在于一個(gè)點(diǎn)集合中，而不存在

6、于另一個(gè)點(diǎn)集合中（同源性），因 此需要在匹配過(guò)程中被濾除。最后，地理變換可能需要引入高維非剛性映射，以便考慮點(diǎn)集的變化。因此，一種綜合點(diǎn)特征定位算法需要解決所有這些問(wèn) 題。它需要能夠解決兩個(gè)點(diǎn)集之間的匹配關(guān)系，濾除異常值，并確定一種比較好的非剛性變換，使得一個(gè)點(diǎn)集能夠映射到另一個(gè)點(diǎn)集上。 在現(xiàn)實(shí)世界中，許多場(chǎng)合都會(huì)應(yīng)用到非剛性點(diǎn)定位。例如 OCR 中的手寫(xiě)字符的模板匹配，卡通動(dòng)畫(huà)中的關(guān)鍵幀之間整體平滑中間插值框架，跟蹤運(yùn)動(dòng)中 的人體運(yùn)動(dòng)

7、，恢復(fù)動(dòng)態(tài)心臟的圖像分析并定位人腦 MRI 腦圖中的圖像，所有這 些涉及緊密相關(guān)但不同物體或形狀之間的最佳變換。這是一個(gè)普遍存在的問(wèn)溢出。 必須采取一些措施來(lái)修改空間匹配關(guān)系的搜索?，F(xiàn)有三種主要的方法來(lái) 實(shí)現(xiàn)這個(gè)目標(biāo)。第一種是基于密集特征的方法，嘗試將特征點(diǎn)分組到更高級(jí)別的結(jié)構(gòu)中， 例如線，曲線或曲面，使得對(duì)象參數(shù)化。然后，對(duì)象可以變形到指定的形式[28,33]。換句話說(shuō)，曲線或曲面是最先從圖像中提取的特征[14,28,40,41]。

8、在配置步驟中經(jīng)常使用參數(shù)化坐標(biāo)幀，從而降低匹配問(wèn)題的難度。在曲線匹配案例中可以清楚地看到該方法的優(yōu)點(diǎn)和缺點(diǎn)。利用現(xiàn)有的額外的曲線排序信息，可以大幅減少匹配空間，使得匹配問(wèn)題變得更加容易。另一方面來(lái)說(shuō)，對(duì) 這些額外信息的要求限制了這些方法的使用。這些方法只有在要匹配的曲線相 當(dāng)平滑的情況下才能有效。此外，在匹配之前的曲線擬合步驟預(yù)先優(yōu)化了特征提取。當(dāng)數(shù)據(jù)有噪聲或者解決復(fù)雜圖形時(shí)，曲線擬合和特征提取都會(huì)變得相當(dāng) 困難。這些方法大多數(shù)都不能處

9、理復(fù)雜曲線或局部閉塞的曲線。第二種類(lèi)型的方法適用于更加稀疏分布的點(diǎn)集?；舅枷胧?，當(dāng)特定形狀的點(diǎn)集是非剛性形變時(shí)，在不同位置的不同點(diǎn)可以根據(jù)其運(yùn)動(dòng)方式被賦予不同的屬性。這些運(yùn)動(dòng)屬性用于區(qū)分這些點(diǎn)并確定它們的匹配關(guān)系。在[12,34,35]之后，[33]中的模態(tài)匹配方法使用從高斯集合中的其他點(diǎn)集中的點(diǎn)特征之間的距離構(gòu)建的質(zhì)量和剛度矩陣。獲得的模態(tài)形狀向量作為用上述矩陣定義的解耦 動(dòng)態(tài)平衡方程的特征向量。通過(guò)比較每個(gè)點(diǎn)在本征模式中的相對(duì)參與

10、來(lái)計(jì)算匹配程度。這些算法的一個(gè)主要限制是它們不能容忍異常值。異常值可能會(huì)嚴(yán)重影響變形模式，從而使計(jì)算出的匹配關(guān)系無(wú)效。只通過(guò)比較本征模式可獲得的 匹配關(guān)系的準(zhǔn)確性也可能受到限制。第三種方法將點(diǎn)匹配重鑄為不精確的加權(quán)匹配[36]。其中每組中的點(diǎn)之間的空間關(guān)系用于限制對(duì)匹配關(guān)系的查詢(xún)。在[13]中，通過(guò) Delaunay 三角測(cè)量建立圖表，考慮了這些點(diǎn)之間的相互關(guān)系。使用期望最大化（EM）算法來(lái)解決圖像匹配優(yōu)化問(wèn)題。然而，空間映射僅限用于仿

11、射或投影。正如我們將看到的， 我們?cè)谶@項(xiàng)工作中的做法與[13]有很多相似之處。在[1]中，可分解圖都是為可變形模板匹配，手工設(shè)計(jì)的，并通過(guò)動(dòng)態(tài)編程最簡(jiǎn)化。在[27]中，使用最大集團(tuán)方法來(lái)匹配相對(duì)的 sulcal 圖。在其他情況下，可變形模型和圖形之間沒(méi)有直 接的關(guān)系。圖形定義同樣是一個(gè)常見(jiàn)的問(wèn)題，因?yàn)橄嗷リP(guān)系，屬性和鏈接類(lèi)型信息可能是非常脆弱并緊密相關(guān)的。事實(shí)上，[1,27]中的圖形是手工設(shè)計(jì)的。 2.3. 2.3. 同時(shí)解決通信和轉(zhuǎn)換

12、問(wèn)題的方法 同時(shí)解決通信和轉(zhuǎn)換問(wèn)題的方法 如果可以的情況下，單獨(dú)解決匹配關(guān)系或形變似乎就已經(jīng)相當(dāng)困難了。注意到，在給出匹配關(guān)系的情況下估計(jì)非剛性變換要容易得多。另一方面，合理 的空間變革的相關(guān)知識(shí)在尋找匹配關(guān)系方面也有相當(dāng)大的幫助。這個(gè)發(fā)現(xiàn)指出 了解決點(diǎn)匹配問(wèn)題的另一種方式——匹配和轉(zhuǎn)換的交替估計(jì)。迭代最近點(diǎn)（ICP）算法[5]是這些方法中最簡(jiǎn)單的。利用最鄰近關(guān)系置換為在每一步分配一個(gè)二進(jìn)制匹配關(guān)系。然后將這種匹配關(guān)系的估計(jì)用于細(xì)化變

13、換，反之亦然。這是一個(gè)非常簡(jiǎn)單和快速的算法，保證收斂到局部最小值。假 設(shè)有足夠的初始數(shù)據(jù)，它可以用作剛性轉(zhuǎn)換的全局匹配工具。不幸的是，這種假設(shè)在非剛性變換的情況下不再有效，特別是當(dāng)變形較大時(shí)。ICP 粗略的分配 函數(shù)會(huì)產(chǎn)生大量的本地最小值，通常不保證匹配關(guān)系是一對(duì)一的。它的運(yùn)行會(huì)快速生成一些異常值，甚至?xí)砑右恍敯艨刂芠9,31]。認(rèn)識(shí)到將匹配關(guān)系視為嚴(yán)格二進(jìn)制變量會(huì)產(chǎn)生這些缺點(diǎn)，其他方法放寬了 這一限制，并引入了“模糊”匹配關(guān)系的概