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

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.一種用于非剛性點定位的新匹配算法 一種用于非剛性點定位的新匹配算法Chui H, Rangaraja

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

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

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

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

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

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

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

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

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

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

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

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