【正文】 這樣，再 加上噪聲和平面部分圖像失真的事實(shí)淹沒了從凹槽采樣點(diǎn)對(duì)的效果， accounts for均勻隨機(jī)抽樣無法收斂到正確的配準(zhǔn)。 。 究其原因，是不在溝槽的樣本僅對(duì)確定剛體變換的六個(gè)部分之中的三個(gè)起到作用（一個(gè) translation 和兩個(gè)旋轉(zhuǎn)）。然從“切平面”場(chǎng)景的結(jié)果看，卻有些不同（圖 3）。 正如我們可以看到的那樣，它們的收斂性能是相似的。 這樣，一個(gè)可以提高機(jī)率的方法是有足夠的約束存在以確定轉(zhuǎn)化的所有組成部分，根據(jù)在角度空間的標(biāo)準(zhǔn)位置來 bucket 點(diǎn) ,那么整個(gè) bucket 過程中盡可能是均勻樣品 . 普通空間采樣是一個(gè)用表面特性配準(zhǔn)的非常簡(jiǎn)單的例子，它具有較低的計(jì)算成本代價(jià)，但比傳統(tǒng)基于特征的方法具有較低的魯棒性 [Faugeras 86， Stein 92, Johnson 97a]。這一戰(zhàn)略動(dòng)機(jī)為了是觀察某些類型的場(chǎng)景下的情況（如： 我們的“下切面”數(shù)據(jù)集），這種模型的細(xì)小特征對(duì)確定正確 配準(zhǔn)來說是至關(guān)重要的場(chǎng)景。 上述方案中的每個(gè)都可以選擇只從一幅網(wǎng)格中選擇點(diǎn)，也可以選擇從兩個(gè)網(wǎng)格中選擇源點(diǎn) [戈丁 94]。 隨機(jī)抽樣（每步迭代中選擇不同的點(diǎn)樣本） [Masuda 96]。 以下策略被提出： 始終使 用所有可用點(diǎn) [Besl 92]。對(duì)于每一個(gè)階段，我們?cè)谡Z(yǔ)言上總結(jié)了這些變種，并在我們的測(cè)試場(chǎng)景中比較了他們的性能。 所有報(bào)出的運(yùn)行時(shí)間為一個(gè)在 550 兆赫奔騰 111 Xeon 處理器上的 C++運(yùn)行時(shí)。 雖然一個(gè)單一的運(yùn)行結(jié)果顯然不能被視為一個(gè)算法在所有情況下性能的代表，但我們?cè)噲D顯示了典型的捕捉了在各種場(chǎng)景中具有顯著性能差異的結(jié)果。 使用這樣的“ ground truth”誤差度量保證了關(guān)于 ICP 算法性能更為客觀的比較，相對(duì)通過算法自身來計(jì)算誤差指標(biāo)。 我們使用綜合數(shù)據(jù)進(jìn)行比較的動(dòng)機(jī)是使我們知道完全正確的轉(zhuǎn)換，并可以評(píng)估 ICP 算法相對(duì)于這一正確路線的性能。 雖然這些場(chǎng)面肯定不涵蓋所有可能的掃描對(duì)象類，但它們是許多掃描應(yīng)用中的代表。 這是一個(gè)困難的場(chǎng)景，對(duì) ICP 來講，大部分變種得不到正確的收斂路線，甚至在初始位置給定相對(duì)較小的旋轉(zhuǎn)情況下。 “分形景觀”測(cè)試現(xiàn)場(chǎng)（圖 1 B）包含了各級(jí)細(xì)節(jié)特征。 “波”的 場(chǎng)景（圖 la）是最容易出現(xiàn)的 ICP 變種情況，因?yàn)樗讼鄬?duì)平穩(wěn)的粗尺度幾何元素。 雖然我們將不會(huì)使用的顏色或強(qiáng)度比較變種，但在使用這些數(shù)據(jù)時(shí)這是明顯的優(yōu)勢(shì)，因?yàn)樗梢蕴峁讉€(gè)幾何特征領(lǐng)域里的必要約束。 僅用于幾何形狀配準(zhǔn)，而不是顏色或強(qiáng)度。 由于我們會(huì)考慮的網(wǎng)格有 10 萬(wàn)個(gè)樣本，如果源點(diǎn)從兩個(gè)網(wǎng)格 中選擇，那么每個(gè)網(wǎng)格的采樣率是 1％；如果源點(diǎn)從一個(gè)網(wǎng)格中選擇，那么每個(gè)網(wǎng)格的采樣率是 2％ . 所有我們使用的網(wǎng)格都是簡(jiǎn)單 視角范圍內(nèi)的圖像，而不是普通不規(guī)則的網(wǎng)格圖像，因?yàn)檫@會(huì)產(chǎn)生 “最近點(diǎn)”和“投影點(diǎn)”變種之間的比較（見 節(jié)）。我們挑選這個(gè)算法，是因?yàn)樗? 在生產(chǎn)環(huán)境已得到廣泛使用 Levoy00]，對(duì)含有多種表面特征的掃描數(shù)據(jù)十分強(qiáng)勁。 點(diǎn)到平面的誤差度量。 將作為我們基準(zhǔn)選擇的算法是實(shí)質(zhì)上是 [普莉 99]，包含有以下特點(diǎn)： 兩個(gè)網(wǎng)格點(diǎn)隨機(jī)抽樣 匹配選定的每個(gè)點(diǎn)在最接近的樣本在 45 度的來源有一個(gè)正常的其他網(wǎng)正常。 2 比較方法 我們的目標(biāo)是比較幾種 ICP 備變種收斂特征。 作為比較的一部分，我們提出均勻空間定向抽樣的概念，并表明它在涉及稀疏，細(xì)微 表面特征的場(chǎng)景中 能夠提高收斂性。 這種實(shí)時(shí) ICP 算法的可用性可能使大量的新應(yīng)用在基于模型的跟蹤和三維掃描方面產(chǎn)生。 在本文中 ,我們將著眼于這六類中的每個(gè)變種，審查它們對(duì) ICP 算法性能的影響。 5. 指定基于點(diǎn)對(duì)的誤差度量。 3. 適當(dāng)加權(quán)對(duì)應(yīng)點(diǎn)對(duì)。 我們可以以算法六個(gè)階段作用來歸類這些變種： 1. 在一幅或兩幅網(wǎng)格圖像中選擇其中部分點(diǎn)集。在本文中，我們假設(shè)一個(gè)粗略的初始對(duì)齊始終可以得到。 ICP 算法以兩幅網(wǎng)格圖像和對(duì)其初始相對(duì)剛體變換的猜測(cè)開始， 然后迭代改進(jìn)變換反復(fù)產(chǎn)生對(duì)應(yīng)網(wǎng)格點(diǎn)對(duì)，最后使 誤差度量最小。 ICP 變種算法分類 ICP（迭代最近點(diǎn)，雖然迭代對(duì)應(yīng)點(diǎn)也許是一個(gè)更好的擴(kuò)展縮寫）算法已成為以純幾何圖形，或者有時(shí)加上 顏色，網(wǎng)格的三維模型配準(zhǔn)的主要方法。 附：論文翻譯 ICP 算法的高 效變種 西蒙 Rusinkiewicz 馬克 Levoy 斯坦福大學(xué) 摘要 在當(dāng)被稱為相對(duì)姿態(tài)的初始估計(jì)是知道的情況下， ICP（迭代最近點(diǎn)）算法被廣泛用于三維模型的幾何對(duì)準(zhǔn) . 許多 ICP 算法的變種已經(jīng)被提出，在算法的各個(gè)階段從點(diǎn)的選擇和匹配方面著手以求達(dá)到最小化策略。 算法 同樣是一個(gè)迭代過程 ， 其中采用 EM估計(jì)和手動(dòng)遞減相結(jié)合的方式更新每步 高斯概率模型的方差 。首先 可以 從理論上分析采用概率模型來處理該類配準(zhǔn)問題可行性 ， 假設(shè)兩個(gè)待配準(zhǔn)點(diǎn)集之間對(duì)應(yīng)關(guān)系服從高斯概率分布，可以通過建立高斯概率模型來計(jì)算各個(gè)對(duì)應(yīng)點(diǎn)的權(quán)重，對(duì)應(yīng)點(diǎn)距離越小權(quán)重越大，反之亦然。 3） 研究具有形狀噪聲的剛體點(diǎn)集 部分 配準(zhǔn)問題，提出一種精確的配準(zhǔn)算法。由于本文提出的算法并沒有限制其應(yīng)用對(duì)象，所以這些算法都具有很好的通用性。 因此， 采用不同度量方式 的 圖像 配準(zhǔn)算法是今后研究的一個(gè)重點(diǎn)。 雖然本文剛體配準(zhǔn)的一般模型，經(jīng)典 ICP 算法和帶重疊百分比的部分點(diǎn) ICP 算法進(jìn)行探討，但還有很多地方有待深入的探索，今后進(jìn)一步的研究工作將集中在如下幾方面： 1）本文提出的目標(biāo)函數(shù)及算法都采用的是基于歐氏距離下的最小平方距離度量，這種度量方式固然簡(jiǎn)單之間，很適合與剛體圖像配準(zhǔn) 。該算法目前是最好的用于解決此類配準(zhǔn)問題的算法，在收斂速度和魯棒性指標(biāo)上。但本文作出貢獻(xiàn)總結(jié)起來在于下面三個(gè)方面： 1） 詳盡闡述了 ICP算法的基本思想和原理，這對(duì)與理解后面本文提出的算法起到鋪墊作用， 因?yàn)楸疚奶岢龅乃惴ㄕ腔诮?jīng)典 ICP算法的變種。 雖然本文對(duì)圖像點(diǎn)集配準(zhǔn)算法做了一些研究工作， 但是在整個(gè)圖像配準(zhǔn)領(lǐng)域上來講僅僅是冰山一角。 本文 僅對(duì)上述第一 類 點(diǎn)集部分配準(zhǔn) 問題分別進(jìn)行了描述和 提出了一種高效的變種 ICP算法， 并且實(shí)驗(yàn)來 驗(yàn)證了 所提算法的有效性和魯棒性。 與此 相反 ， 剛體 點(diǎn)集的 部分 配準(zhǔn)問題 則 是 現(xiàn)在圖像配準(zhǔn)領(lǐng)域 一個(gè)難點(diǎn)和熱點(diǎn) ，因而 本文 也毫不猶豫地將其列為了闡述 的 重點(diǎn)。最后，本章通過二維點(diǎn)集配準(zhǔn)實(shí)驗(yàn)進(jìn)一步驗(yàn)證 了 算法的 正確性和精確性 ，實(shí)驗(yàn)結(jié)果顯示在保證配準(zhǔn)時(shí)間效率的前提下，配準(zhǔn)結(jié)果 的效果不隨待配準(zhǔn) 點(diǎn)集 及模型點(diǎn)集形狀和 缺失數(shù)據(jù) 位置 的影響。本章首先分析點(diǎn)集重疊百分比和配準(zhǔn)誤差之間的關(guān)系，指出通過建立新目標(biāo)函數(shù)來處理具有缺失數(shù)據(jù)點(diǎn)集配準(zhǔn)問題的可行性。從實(shí)驗(yàn)結(jié)果顯示來看，帶重疊百分比的點(diǎn)集部分配準(zhǔn)算法對(duì)于這類簡(jiǎn)單的黑白圖像的配準(zhǔn)是理想完美的，從而可見算法的正確性和精確性。值得注意的是由于截圖效果不好的原因，看上去兩幅圖似乎是經(jīng)過了伸縮變換，但實(shí)際情況是僅僅只有旋轉(zhuǎn)平移和裁剪。本文中所有的代碼都是用 來完成的 。 實(shí)驗(yàn)結(jié)果分析 為了 驗(yàn)證帶重疊百分比的點(diǎn)集部分配準(zhǔn) 算法 的魯棒性和收斂性， 本文根據(jù)上面闡述的算法寫了 matlab 程序作了圖像配準(zhǔn)仿真實(shí)驗(yàn) 。配準(zhǔn)循環(huán)結(jié)束后，算法讓 ? 從 min? 開始往遞增方向搜索，因?yàn)樵诜€(wěn)定狀態(tài)（配準(zhǔn)結(jié)果正確）下( , )r?Y 是遞減的，因此第一個(gè)使目標(biāo)函數(shù) ( , )r?Y 遞增的 *? 就是待求的最優(yōu)參數(shù)。算法的內(nèi)循環(huán)迭代流程類似于傳統(tǒng) ICP 算法，但是循環(huán)體內(nèi)增加了求解點(diǎn)集重疊百分比的步驟，具體流程為： 1)根據(jù) ( 1)k? 步的剛體變換 11( , )kk??Rt ，計(jì)算點(diǎn)集 S 和 M 的對(duì)應(yīng)關(guān)系 21 1 2{ 1 , 2 , , }( ) a r g m i n || ||sk k i k jjNci ???? ? ?R s t m 2)求 目標(biāo)函數(shù) ( , )r?Y 的最小值的過程中確定 第 k 步的最優(yōu)重疊 百分比 r 21 1 ( ) 20 . 5 1a r g m i n | | | | / ( )kirk k i k c irr e r?????? ?? ? ??sS R s t m 3)根據(jù) 上步求得的 對(duì)應(yīng)點(diǎn)集 1 1 1{}sNk i k i? ? ??R s t 和 ( ) 1{}sk Nc i i?m和 重疊 百分比 kr ，求解第 k 步 S 中最優(yōu)子集krS： 21 1 ( ) 2, | | | |a r g m i n | | | |kkr r k irr k i k c ir ???? ?? ? ??S S S S sSS R s t m 4)通過 求 關(guān)于子集krS度量函數(shù) 的 最小化 值 計(jì)算第 k 步 的 空間變換 **T21 1 ( ) 2, d e t ( ) 1 ,( , ) a r g m i n || ( ) ||km ir k k i k c i???? ?? ? ? ??R R I R t sSR t R R s t t m 5） 更新 kR 和 kt : * * *11, k k k k??? ? ?R R R t R t t 配準(zhǔn)過程中，只有當(dāng) ? 取值能夠搜索出最優(yōu)的裁剪度 r 時(shí)，才能計(jì)算出準(zhǔn)確的剛體變換，這時(shí)點(diǎn)集配準(zhǔn)會(huì)趨于穩(wěn)定狀態(tài)。 然后以后每步迭代中 調(diào)控參數(shù) ? 從 max? 遞減到 min? 。 4 所示： 圖 錯(cuò)誤 !文檔中沒有指定樣式的文字。與前面經(jīng)典 ICP 算法顯著的不同是，該算法在 每步迭代中 除了要 計(jì)算 求解點(diǎn)集的對(duì)應(yīng)關(guān)系和空間變換 外 ，還要計(jì)算點(diǎn)集重疊百分比 r。 0 . 5 0 . 5 5 0 . 6 0 . 6 5 0 . 7 0 . 7 5 0 . 8 0 . 8 5 0 . 9 0 . 9 5 102468101214161820重疊百分比誤差 誤差懲罰函數(shù)新的目標(biāo)函數(shù) 圖 錯(cuò)誤 !文檔中沒有指定樣式的文字。 很明顯可以看出該目標(biāo)函數(shù)是 一個(gè) 上 凸函數(shù)， 而 函數(shù)的最 小值點(diǎn)的橫坐標(biāo)就是最優(yōu)重疊百分比 r 的取值。 下面 給出新目標(biāo)函數(shù)的數(shù)學(xué)表達(dá)： 給定 Rm 維 空間中的 形狀點(diǎn)集 S 和 模型點(diǎn)集 M，設(shè) r 表示兩個(gè)點(diǎn)集的重疊百分比， rS表 示 形狀點(diǎn)集中與模型點(diǎn)集相對(duì)應(yīng)的部分點(diǎn)集。因此可以給該誤差除以一個(gè)連續(xù)遞增的懲罰因子，得到一個(gè)新的目標(biāo)函數(shù)。 為了 使下面的算法和傳統(tǒng) ICP 算法相一致，即更為直觀的在配準(zhǔn)誤差達(dá)到最小時(shí)，配準(zhǔn)效果也達(dá)到最佳，而不是前面分析的在誤差突變時(shí)刻， 本文 借用正則化的思想來 解決 這個(gè)問題。如何講呢？ 最優(yōu)的重疊百分 r一方面要使配準(zhǔn)誤差相對(duì)較小，而另一方面又要盡可能多地利用待配準(zhǔn)點(diǎn)集中能夠作 對(duì)應(yīng)的點(diǎn)，而這兩方面又是相互矛盾對(duì)立的。但是如果重疊百分比 r取值過大， 又 會(huì) 產(chǎn)生 在匹配過程中引入 大量不能作 對(duì)應(yīng) 的 點(diǎn) 的問題 ，而這些異常 點(diǎn)會(huì)提供錯(cuò)誤的信息， 錯(cuò)誤引導(dǎo)配準(zhǔn)的進(jìn)行方向 ， 其結(jié)果是 配準(zhǔn)不魯棒。2） 重疊百分比 很大。從重疊百分比 ?的大小 考慮： 1） 重疊百分比很小。而對(duì)于具有 部分 數(shù)據(jù) 缺失 的點(diǎn)集 部分 配準(zhǔn)問題，最優(yōu)空間變換 的求解要復(fù)雜得多，它不像傳統(tǒng) ICP配準(zhǔn)算法那樣僅僅取決與一個(gè)配準(zhǔn)誤差量，它還依賴與重疊百分比 r。理論和實(shí)驗(yàn) 一致 證明 了 ，最優(yōu)的重疊百分比 r并非 像大家想像的那樣理所當(dāng)然的 對(duì)應(yīng) 具有最小 配準(zhǔn)誤差 時(shí)的值 ，而是 對(duì)應(yīng)配準(zhǔn) 誤差突增 時(shí)的值 ，即 ?在 值之間 0 . 5 0 . 5 5 0 . 6 0 . 6 5 0 . 7 0 . 7 5 0 . 8 0 . 8 5 0 . 9 0 . 9 5 102468101214161820重疊百分比誤差缺失數(shù)據(jù)點(diǎn)集配準(zhǔn)誤差與重疊百分比關(guān)系 圖 錯(cuò)誤 !文檔中沒有指定樣式的文字。 2 可以看出，配準(zhǔn) 誤差 是 重疊百分比 r 的 一個(gè)簡(jiǎn)單的單調(diào)遞增函數(shù) ， 開始重疊百分比 r比很小時(shí)配準(zhǔn)誤差幾乎為零，因?yàn)樾螤铧c(diǎn)集中能夠建立對(duì)應(yīng)關(guān)系的點(diǎn)個(gè)數(shù)此時(shí)極少 故幾乎不存在 任何誤差，然而當(dāng)重疊百分比達(dá)到某個(gè)值時(shí)配準(zhǔn)誤差開始突增，根據(jù)大量實(shí)驗(yàn)表明此時(shí)的 r值在 之間 。 2 給出 了在一般大量 配準(zhǔn) 情景中 ，點(diǎn)集重疊百分比 r 與 均 方 根 誤 差 （ Root Mean Square ， RMS ） 的 關(guān) 系 。在本文 中， 該百分比 r的最優(yōu)值 是由 配準(zhǔn)誤差來確定。 換而言之，對(duì)于具有缺失數(shù)據(jù)的點(diǎn)集配準(zhǔn)問題，不僅要確定兩個(gè)點(diǎn)集的對(duì)應(yīng)關(guān)系和全局的幾何變換，而且還要確定點(diǎn)集的重疊百分比 。分析 具有缺失數(shù)據(jù)的點(diǎn)集配準(zhǔn)問題，可以發(fā)現(xiàn) 兩個(gè)待配準(zhǔn)點(diǎn)集之間的重疊百分比是一個(gè)重要的衡量標(biāo)準(zhǔn)。 在前面，本文緒論中范范而談了幾種 處理 部分對(duì)應(yīng)點(diǎn)集的配準(zhǔn) 方法， 即 閾值方法，概率方法，幾何方法等，然而這些方法都依賴于待配準(zhǔn)點(diǎn)集的形狀，或 知道了噪聲點(diǎn)服從某個(gè)已知出名的 概率分布 函數(shù) ， 而我們面對(duì)的情況是未知待配準(zhǔn) 點(diǎn)集 圖像形狀和未知噪聲概率分布函數(shù)這一更為嚴(yán)峻的情景，它往往是具有較大面積數(shù) 據(jù)