【正文】 | | | |kkr r k irr k i k c ir ???? ?? ? ??S S S S sSS R s t m 4)通過 求 關于子集krS度量函數(shù) 的 最小化 值 計算第 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 配準過程中，只有當 ? 取值能夠搜索出最優(yōu)的裁剪度 r 時，才能計算出準確的剛體變換，這時點集配準會趨于穩(wěn)定狀態(tài)。 實驗結果分析 為了 驗證帶重疊百分比的點集部分配準 算法 的魯棒性和收斂性， 本文根據(jù)上面闡述的算法寫了 matlab 程序作了圖像配準仿真實驗 。值得注意的是由于截圖效果不好的原因，看上去兩幅圖似乎是經過了伸縮變換，但實際情況是僅僅只有旋轉平移和裁剪。本章首先分析點集重疊百分比和配準誤差之間的關系，指出通過建立新目標函數(shù)來處理具有缺失數(shù)據(jù)點集配準問題的可行性。 與此 相反 ， 剛體 點集的 部分 配準問題 則 是 現(xiàn)在圖像配準領域 一個難點和熱點 ，因而 本文 也毫不猶豫地將其列為了闡述 的 重點。 雖然本文對圖像點集配準算法做了一些研究工作， 但是在整個圖像配準領域上來講僅僅是冰山一角。該算法目前是最好的用于解決此類配準問題的算法，在收斂速度和魯棒性指標上。 因此， 采用不同度量方式 的 圖像 配準算法是今后研究的一個重點。 3） 研究具有形狀噪聲的剛體點集 部分 配準問題，提出一種精確的配準算法。 算法 同樣是一個迭代過程 ， 其中采用 EM估計和手動遞減相結合的方式更新每步 高斯概率模型的方差 。 ICP 變種算法分類 ICP（迭代最近點，雖然迭代對應點也許是一個更好的擴展縮寫）算法已成為以純幾何圖形，或者有時加上 顏色，網格的三維模型配準的主要方法。在本文中，我們假設一個粗略的初始對齊始終可以得到。 3. 適當加權對應點對。 在本文中 ,我們將著眼于這六類中的每個變種，審查它們對 ICP 算法性能的影響。 作為比較的一部分，我們提出均勻空間定向抽樣的概念，并表明它在涉及稀疏，細微 表面特征的場景中 能夠提高收斂性。 將作為我們基準選擇的算法是實質上是 [普莉 99]，包含有以下特點： 兩個網格點隨機抽樣 匹配選定的每個點在最接近的樣本在 45 度的來源有一個正常的其他網正常。我們挑選這個算法，是因為它 在生產環(huán)境已得到廣泛使用 Levoy00]，對含有多種表面特征的掃描數(shù)據(jù)十分強勁。 僅用于幾何形狀配準，而不是顏色或強度。 “波”的 場景（圖 la）是最容易出現(xiàn)的 ICP 變種情況，因為它包含了相對平穩(wěn)的粗尺度幾何元素。 這是一個困難的場景，對 ICP 來講，大部分變種得不到正確的收斂路線，甚至在初始位置給定相對較小的旋轉情況下。 我們使用綜合數(shù)據(jù)進行比較的動機是使我們知道完全正確的轉換，并可以評估 ICP 算法相對于這一正確路線的性能。 雖然一個單一的運行結果顯然不能被視為一個算法在所有情況下性能的代表，但我們試圖顯示了典型的捕捉了在各種場景中具有顯著性能差異的結果。對于每一個階段，我們在語言上總結了這些變種，并在我們的測試場景中比較了他們的性能。 隨機抽樣（每步迭代中選擇不同的點樣本） [Masuda 96]。這一戰(zhàn)略動機為了是觀察某些類型的場景下的情況（如： 我們的“下切面”數(shù)據(jù)集），這種模型的細小特征對確定正確 配準來說是至關重要的場景。 正如我們可以看到的那樣，它們的收斂性能是相似的。 究其原因，是不在溝槽的樣本僅對確定剛體變換的六個部分之中的三個起到作用（一個 translation 和兩個旋轉）。 這樣，再 加上噪聲和平面部分圖像失真的事實淹沒了從凹槽采樣點對的效果， accounts for均勻隨機抽樣無法收斂到正確的配準。 。然從“切平面”場景的結果看，卻有些不同（圖 3）。 這樣，一個可以提高機率的方法是有足夠的約束存在以確定轉化的所有組成部分，根據(jù)在角度空間的標準位置來 bucket 點 ,那么整個 bucket 過程中盡可能是均勻樣品 . 普通空間采樣是一個用表面特性配準的非常簡單的例子，它具有較低的計算成本代價，但比傳統(tǒng)基于特征的方法具有較低的魯棒性 [Faugeras 86， Stein 92, Johnson 97a]。 上述方案中的每個都可以選擇只從一幅網格中選擇點，也可以選擇從兩個網格中選擇源點 [戈丁 94]。 以下策略被提出： 始終使 用所有可用點 [Besl 92]。 所有報出的運行時間為一個在 550 兆赫奔騰 111 Xeon 處理器上的 C++運行時。 使用這樣的“ ground truth”誤差度量保證了關于 ICP 算法性能更為客觀的比較，相對通過算法自身來計算誤差指標。 雖然這些場面肯定不涵蓋所有可能的掃描對象類，但它們是許多掃描應用中的代表。 “分形景觀”測試現(xiàn)場（圖 1 B）包含了各級細節(jié)特征。 雖然我們將不會使用的顏色或強度比較變種，但在使用這些數(shù)據(jù)時這是明顯的優(yōu)勢，因為它可以提供幾個幾何特征領域里的必要約束。 由于我們會考慮的網格有 10 萬個樣本，如果源點從兩個網格 中選擇，那么每個網格的采樣率是 1％；如果源點從一個網格中選擇，那么每個網格的采樣率是 2％ . 所有我們使用的網格都是簡單 視角范圍內的圖像，而不是普通不規(guī)則的網格圖像，因為這會產生 “最近點”和“投影點”變種之間的比較（見 節(jié)）。 點到平面的誤差度量。 2 比較方法 我們的目標是比較幾種 ICP 備變種收斂特征。 這種實時 ICP 算法的可用性可能使大量的新應用在基于模型的跟蹤和三維掃描方面產生。 5. 指定基于點對的誤差度量。 我們可以以算法六個階段作用來歸類這些變種： 1. 在一幅或兩幅網格圖像中選擇其中部分點集。 ICP 算法以兩幅網格圖像和對其初始相對剛體變換的猜測開始， 然后迭代改進變換反復產生對應網格點對，最后使 誤差度量最小。 附：論文翻譯 ICP 算法的高 效變種 西蒙 Rusinkiewicz 馬克 Levoy 斯坦福大學 摘要 在當被稱為相對姿態(tài)的初始估計是知道的情況下， ICP（迭代最近點）算法被廣泛用于三維模型的幾何對準 . 許多 ICP 算法的變種已經被提出，在算法的各個階段從點的選擇和匹配方面著手以求達到最小化策略。首先 可以 從理論上分析采用概率模型來處理該類配準問題可行性 ， 假設兩個待配準點集之間對應關系服從高斯概率分布，可以通過建立高斯概率模型來計算各個對應點的權重，對應點距離越小權重越大，反之亦然。由于本文提出的算法并沒有限制其應用對象，所以這些算法都具有很好的通用性。 雖然本文剛體配準的一般模型，經典 ICP 算法和帶重疊百分比的部分點 ICP 算法進行探討，但還有很多地方有待深入的探索，今后進一步的研究工作將集中在如下幾方面： 1）本文提出的目標函數(shù)及算法都采用的是基于歐氏距離下的最小平方距離度量，這種度量方式固然簡單之間，很適合與剛體圖像配準 。但本文作出貢獻總結起來在于下面三個方面： 1） 詳盡闡述了 ICP算法的基本思想和原理，這對與理解后面本文提出的算法起到鋪墊作用， 因為本文提出的算法正是基于經典 ICP算法的變種。 本文 僅對上述第一 類 點集部分配準 問題分別進行了描述和 提出了一種高效的變種 ICP算法， 并且實驗來 驗證了 所提算法的有效性和魯棒性。最后，本章通過二維點集配準實驗進一步驗證 了 算法的 正確性和精確性 ，實驗結果顯示在保證配準時間效率的前提下，配準結果 的效果不隨待配準 點集 及模型點集形狀和 缺失數(shù)據(jù) 位置 的影響。從實驗結果顯示來看，帶重疊百分比的點集部分配準算法對于這類簡單的黑白圖像的配準是理想完美的，從而可見算法的正確性和精確性。本文中所有的代碼都是用 來完成的 。配準循環(huán)結束后，算法讓 ? 從 min? 開始往遞增方向搜索，因為在穩(wěn)定狀態(tài)（配準結果正確）下( , )r?Y 是遞減的，因此第一個使目標函數(shù) ( , )r?Y 遞增的 *? 就是待求的最優(yōu)參數(shù)。 然后以后每步迭代中 調控參數(shù) ? 從 max? 遞減到 min? 。與前面經典 ICP 算法顯著的不同是，該算法在 每步迭代中 除了要 計算 求解點集的對應關系和空間變換 外 ，還要計算點集重疊百分比 r。 很明顯可以看出該目標函數(shù)是 一個 上 凸函數(shù)， 而 函數(shù)的最 小值點的橫坐標就是最優(yōu)重疊百分比 r 的取值。因此可以給該誤差除以一個連續(xù)遞增的懲罰因子，得到一個新的目標函數(shù)。如何講呢？ 最優(yōu)的重疊百分 r一方面要使配準誤差相對較小，而另一方面又要盡可能多地利用待配準點集中能夠作 對應的點，而這兩方面又是相互矛盾對立的。2） 重疊百分比 很大。而對于具有 部分 數(shù)據(jù) 缺失 的點集 部分 配準問題，最優(yōu)空間變換 的求解要復雜得多，它不像傳統(tǒng) ICP配準算法那樣僅僅取決與一個配準誤差量，它還依賴與重疊百分比 r。 2 可以看出，配準 誤差 是 重疊百分比 r 的 一個簡單的單調遞增函數(shù) ， 開始重疊百分比 r比很小時配準誤差幾乎為零，因為形狀點集中能夠建立對應關系的點個數(shù)此時極少 故幾乎不存在 任何誤差，然而當重疊百分比達到某個值時配準誤差開始突增，根據(jù)大量實驗表明此時的 r值在 之間 。在本文 中， 該百分比 r的最優(yōu)值 是由 配準誤差來確定。分析 具有缺失數(shù)據(jù)的點集配準問題，可以發(fā)現(xiàn) 兩個待配準點集之間的重疊百分比是一個重要的衡量標準。 然而宏觀的想法是很簡單的，但具體到 如何有效排除點集中的非對應點 集部分則是一個較為復雜難辦的問題。 其中紅色表示模型點集，藍色表示形狀點集，綠色和天 藍色分別表示兩個點集中多余或者缺失的部分。所謂形狀噪聲， 它是指圖像點集位置 與真實精確的位置相異但差別卻很小，僅僅是一個小小的擾動而已 ，而 且 噪聲往往服從某些概率分布， 如高斯分布。 如果按照 點集對應關系 來分類，則通常認為 點集部分 配準問題可以分為兩大類：一類是具有 點集中部分 數(shù)據(jù) 丟失或點集中含有大量 離群點的點集配準，而另一類是具有形狀噪聲的點集配準問題。在內容安排方面，本章首先給出 點集剛體 部分配準 問題 的 描述及解決方案，接著 提出本文的第一個 創(chuàng)新點， 一種能夠自動計算點集重疊百分比的快速魯棒的剛體配準算法 ， 然后詳盡 闡述 算法 的基本 思想 原理和算法解決問題的步驟流程， 最后 就是給出 實驗結果 ，并根據(jù)結果一些數(shù)學品質考察此算法的性能。 3 基于迭代最近點的部分配準算法 前面 第二章 描述了 ICP 剛體配準 問題并建立了它的數(shù)學 模型 ， 且給出 求解 ICP 剛體配準問題的 具體 方法和原理 ， 接下來 本章 將 在 上面的 基礎上進一步研究基于 ICP（即迭代最近點） 的剛體 部分 配準問題。在配準結果圖中，需要說明的是 紅色 線是待配準圖像的輪廓， 綠色 線 是 模型圖像的輪廓，程序結果并沒有很好的展示配準后兩者相重疊的輪廓部分。 設 39。對于 ICP 算法中式的求解，首先將模型點集 M進行 Delaunay 三角剖分，然后采用三角劃分搜索策略找到形狀點集 S 在模型點集 M 中的對應點。 Delaunay 剖分必須滿足兩個基本準則，其一是 空圓特性 ，即在 Delaunay 三角形網中任一 個 三角形的外接圓范圍內不會有其它點存在。對第二步求解，有 SVD(奇異值分解， Singular Value Deposition)、四元組、正交矩陣、雙四元祖方法，本 文 采用的是 SVD 1） Delaunay 三角化 求解 點集 對應關系 如何把一個散點集合剖分成不均勻的三角 形網格，這就是散點集的三角剖分問題 。當 ICP 算法 循環(huán) 退出后， 那么返回 得到最終的剛體變換 和點集對應關系，通過這兩個量我們就可以把兩幅剛性圖像配準了。這就是所謂的兩個點集 間的均方誤差（ Mean Square Error，MSE） ，數(shù)學表達式為 2( ) 21 || ( ) ||skNk k i k c ii? ?? ? ?? R s t m。 1 ICP 算法流程 從 圖 錯誤 !文檔中沒有指定樣式的文字。 Np 形狀點集中點的個數(shù)。 ICP 算法 ICP (Iterative Closest Point) 算法最早是由 Besl 和 McKay于 1992 年提出來的一個配準算法，它用于解決兩個點集之間的剛體配準問題。對于兩組點集，進行配準的 LS準則函數(shù)為： 綜上述，剛體配準是圖像配準中的一種，它最終目的是通過尋找一個空間變換 T，即 R和 t,使得經過該空間變換后兩幅圖像間相似性度量 J 最小，這也就達到了兩幅圖像中的點 在空間幾何上的一致。所以本文中所涉及的變換 T 僅限于旋轉和平移，而不包括其他變換，如相似變換、伸縮變換、仿射變換、投影變換和彈性變換等。由于本文僅涉及 Euclidean距離，本文后面僅簡要闡述了一下 Eucli