【文章內(nèi)容簡介】 idean距離，本文后面僅簡要闡述了一下 Euclieadn距離度量。 剛體 (Rigid body)。在任何力的作用下，體積和形狀都不發(fā)生改變的物體叫做剛體。以上是物理學上對剛體所下的定義，那顧名思義剛體配準就是剛性圖像間的配準，它主要包括旋轉(zhuǎn)和平移變換。所以本文中所涉及的變換 T 僅限于旋轉(zhuǎn)和平移，而不包括其他變換，如相似變換、伸縮變換、仿射變換、投影變換和彈性變換等。 在數(shù)學上建立剛體變換的模型相當簡單： 給定 Rm 維 空間中的 形狀點集 S 和 模型點集 M，假設(shè) 存在任意兩點 ?xS和 ?yM ，那么剛體變換 的數(shù)學表達式 為： ??y R x t X —— 原始點集 Y —— 變換后點集 R —— m x m 維的旋轉(zhuǎn)矩陣， R 滿足 如下約束 ： t —— m 維的平移向量 圖像點集配準中一個重要的量 —— 相似性度量 J。 點到點的距離又稱為 2 范數(shù)距離，它表示 Rm空間中兩個點 x{x1 ,x2 ,..,xi ,... } 和y{ y1 ,y2 ,..,yi ,... }之間的真實距離： 由于 Euclidean計算 比較簡單，因而它是最為常見和常用的距離，大多數(shù)點集配準問題都采用它來定義空間中點對的距離。以點到點的 Euclidean 距離為基礎(chǔ)作相似性度量，最為常見的是兩個集合之間的最小平方（ Least Square， LS）準則。對于兩組點集，進行配準的 LS準則函數(shù)為： 綜上述，剛體配準是圖像配準中的一種，它最終目的是通過尋找一個空間變換 T，即 R和 t,使得經(jīng)過該空間變換后兩幅圖像間相似性度量 J 最小，這也就達到了兩幅圖像中的點 在空間幾何上的一致。 圖 錯誤 !文檔中沒有指定樣式的文字。 1 點集配 準示意圖 給定 R 空間中的兩個點集： S形狀點集 M模型點集 故配準問題實際上是解決上述兩個未知量，即最優(yōu)的空間變換 T 和確定形狀點集到模型點集的對應(yīng)關(guān)系 C。 現(xiàn)階段剛體配準問題的研究工作中，最為典型的是 ICP 算法，它有效地解決了點集的剛體配準問題，更為非剛體配準算法研究奠定了理論基礎(chǔ)。 ICP 算法 ICP (Iterative Closest Point) 算法最早是由 Besl 和 McKay于 1992 年提出來的一個配準算法，它用于解決兩個點集之間的剛體配準問題。 ICP算法 的目標是尋找一個剛體變換， 即旋轉(zhuǎn)矩陣 R 和平移向量 t ，使得 給定形狀點集和模型點集中的點能夠在 Euclidean歐式距離空間上對應(yīng)起來。在經(jīng)典的 ICP算法中，相似性度量 J 采用了上述闡述到的最小平方（ Least Square， LS）距離。對于剛體變換，空間變換 Τ 僅包括旋轉(zhuǎn)變換 R 和平移變換 t ，因此剛體配準問題可表示為： 2( ) 21m in || || . . , de t( ) 1PNi c ic iTst??????R,t, R s t mR R I R C(i) 形狀點集和模型點集間的對應(yīng)關(guān)系。 Np 形狀點集中點的個數(shù)。 剛體配準問題實際上是求使?jié)M足上式的 R， t 和 C(i)，即變換和對應(yīng)關(guān)系。 ICP配準算法通過交替迭代的方式來分別求解這兩個未知變量，算法流程如 圖 錯誤 !文檔中沒有指定樣式的文字。 1所示： 圖 錯誤 !文檔中沒有指定樣式的文字。 1 ICP 算法流程 從 圖 錯誤 !文檔中沒有指定樣式的文字。 1可以看出， 經(jīng)典的 ICP算法首先由人為估計給定 一個初始的 空間變換 ，并且這個初始值要求應(yīng)當粗略正確。然后 ICP算法 正如它的名字一樣 通過反復(fù)迭代 ，不斷改進空間變換和對應(yīng)關(guān)系最終以求達到最優(yōu)的配準效果。那 ICP算法是如何改進每步迭代中的變換量和對應(yīng)量的呢？下面給出具體的數(shù) 學表達式，來闡述 原理 ： 1） 根據(jù) 1k? 步的剛體變換 11( , )kk??Rt 來 確定形狀點集和模型點集間每個點的對應(yīng)關(guān)系 21 1 2( ) a r g m i n ( | | ( ) | | ) , 1 , 2 , . . . ,k k i k j sc i i N??? ? ? ?R s t m 2） 計算兩個點集 1 1 1{( )} sNk i k i? ? ??R s t 和 ( ) 1{}sk Nc i i?m之間新的剛體變換： T2** 1 1 ( )2, d e t ( ) 1 , 1( , ) a r g m i n ( ( ) )pksNk i k c ii ???? ?? ? ? ??R R I R tR t R R s t t m 3） 更新第 k 步的變換 kR 和 kt ： * * *11 , k k k k??? ? ?R R R t R t t ICP 算法是一個迭代過程，那么算法在何處停止迭代而退出呢？這就涉及到如何判定圖像點集配準所達到的效果程度，很簡單明了的一種方式是總體上形狀點集中點和模型點集中對應(yīng)點的 2 維范數(shù)以達到最小。這就是所謂的兩個點集 間的均方誤差（ Mean Square Error，MSE） ，數(shù)學表達式為 2( ) 21 || ( ) ||skNk k i k c ii? ?? ? ?? R s t m。當 k? 達到 我們設(shè)定的某個范圍值下 限時，我們就可以讓 ICP 算法停止迭代退出了。當然實際配準中，我們很大的可能性是不可能使配準誤差 k? 達到它理論上的最小值，因為這可能需要難以忍受的等待時間或者根本就不存在這樣一個最小值。所以我們往往采取均方誤差達到設(shè)定范圍下限和 迭代步驟達到指定的循環(huán)次數(shù) 這兩個指標，來決定是否停止迭代。當 ICP 算法 循環(huán) 退出后， 那么返回 得到最終的剛體變換 和點集對應(yīng)關(guān)系，通過這兩個量我們就可以把兩幅剛性圖像配準了。 算法求解 對第一步求解，有 kd 樹、基于 Delaunay(德勞內(nèi) )三角化的最近點搜索算法等 。 很多研究和實驗結(jié)果 一致表明 ， kd 樹適合于高維點集的點搜索，而基于 Delaunay 三角化的最近點搜索算法 則 更適 合于低維點集的點搜索。 鑒于簡單起見， 本 文 采用的是 Delaunay 三角化。對第二步求解，有 SVD(奇異值分解， Singular Value Deposition)、四元組、正交矩陣、雙四元祖方法，本 文 采用的是 SVD 1） Delaunay 三角化 求解 點集 對應(yīng)關(guān)系 如何把一個散點集合剖分成不均勻的三角 形網(wǎng)格，這就是散點集的三角剖分問題 。 將二維 (三維 )空間中任意分布的散亂點用直線段連接起來，形成的空間上既不重疊又無間隙的緊鄰的三角形 (四面體 )集，每個三角形 (四面體 )的頂點即為原始散亂點。也就是說，在二維情況下得到的是三角形網(wǎng)格，在三維情況下得到的是四面體網(wǎng)格。 在已有的 多種三角剖分的優(yōu)化規(guī)則 中 ，目前公認的具有最好幾何拓撲性質(zhì)的剖分就是符合 Delaunay 規(guī)則的三角剖分。 Delaunay 剖分必須滿足兩個基本準則，其一是 空圓特性 ，即在 Delaunay 三角形網(wǎng)中任一 個 三角形的外接圓范圍內(nèi)不會有其它點存在。 其二是 最大化最小角特性 ，即 在散點集可能形成的三角剖分中， Delaunay 三角剖分所形成的三角形的最小角最大。局部變換法和 Watson 算法是離散點集 Delaunay 三角剖分的常用算法，算法過程中逐點添加、局部優(yōu)化是三角網(wǎng)格生成速度的重要影響因素。 根據(jù) Delaunay 三角剖分原理 ，可以構(gòu)造出各種適合該網(wǎng)格形狀的搜索策略。對于 ICP 算法中式的求解，首先將模型點集 M進行 Delaunay 三角剖分，然后采用三角劃分搜索策略找到形狀點集 S 在模型點集 M 中的對應(yīng)點。該搜索策略大幅度提高了點集對應(yīng)關(guān)系求解的速度和精度。 2） SVD 方法 求解 剛體變換 SVD 方法 相當比較 簡單，而且具有較好的擴展性，所以 本文采用 奇異值分解 Singular Value Deposition 的方法解決第二步中剛體變換求解。 定理（ 1） ： 給定任意兩個 m 維對應(yīng)點集 1{}Nii?q 和 1{}Nii?n ，當1111NNiiiiNN??????t n q時，目標函數(shù) 221( ) || ||NiiiF ?? ? ??t q t n取得最小值。 設(shè) 39。 11i k i k???s R s t ， 那么式最小化目標函數(shù)為： 39。2( ) 21( , ) || ||kNi c iiF ?? ? ??R t R s t m 要使目標函數(shù)最小， 則 ： ()1111sskNNc i iiippNN??????t m R s 令11 sNi i iipN ??? ?q s s，( ) ( )11skkNi c i c iisN ??? ?n m m， 化簡目標函數(shù)得： 1 1 1( , ) 2s s sN N NT T Ti i i i i ii i iF ? ? ?? ? ?? ? ?R t q q n R q n n 最小化目標函數(shù)，即最小化1sN Tiii???n Rq 實驗結(jié)果 圖 a1 模型圖像 圖 a2 待配準圖像 圖 a3 配準結(jié)果 圖 b1 模型圖像 圖 b2 待配準圖像 圖 b3 配準結(jié)果 上面所示的實驗結(jié)果圖中，因為為了簡單起見均采用的是黑白圖，而且僅僅是提取了圖片中圖像物體的外部輪廓 線條特征來作配準的標準。其中模型圖像和待配準圖像之間僅僅是一個旋轉(zhuǎn)和平移的效果，并涉及其它復(fù)雜的圖像變換，這也正是剛體變換所需要的前提。在配準結(jié)果圖中，需要說明的是 紅色 線是待配準圖像的輪廓， 綠色 線 是 模型圖像的輪廓，程序結(jié)果并沒有很好的展示配準后兩者相重疊的輪廓部分。 從上面的配準結(jié)果來看， IPC 算法的配準效果還蠻不錯的。 本章小結(jié) 本章 首先提出了圖像點集配準問題的概念，接著在數(shù)學上 建立點集配準 的 模型 ，隨后又闡述了 在眾多的剛體配準研究 中最為矚目的由 Besl 和 Mckay 提出的 ICP 算法 ，并且詳盡地論 述了算法運作流程和算法每步中問題的解決方法。 本章 最后 給出 了利用 ICP 算法在matlab 上所做的簡單圖像配準實驗結(jié)果 。 3 基于迭代最近點的部分配準算法 前面 第二章 描述了 ICP 剛體配準 問題并建立了它的數(shù)學 模型 ， 且給出 求解 ICP 剛體配準問題的 具體 方法和原理 ， 接下來 本章 將 在 上面的 基礎(chǔ)上進一步研究基于 ICP（即迭代最近點） 的剛體 部分 配準問題。 因為 傳統(tǒng)的 ICP 算法 是建立在 假設(shè)兩個待配準點集 中所有點都是有其相對應(yīng)關(guān)系的前提下的 ， 它 并未 考慮到實際中存在的復(fù)雜情況，如障礙物 遮擋，拍攝角度 狹窄 及傳感器噪聲等 因素所造成的點集 部分 數(shù)據(jù) 丟失或存在大量離群點情況下圖像點集的配準 。 所以本章針對這一問題，會在傳統(tǒng) ICP 算法基礎(chǔ)上，將引入重疊百分比的概念，然后建立關(guān)于空間變換的新目標函數(shù)，因而與前面 ICP 算法不同的是在 配準過程中 ，將 同時更新 三個未知量，即 點集重疊百分比 ， 空間變換 和點間對應(yīng)關(guān)系。很明顯相對傳統(tǒng)的 ICP算法新增了重疊百分比這個變量，所以算法也相應(yīng)變得更為復(fù)雜，更具挑戰(zhàn)性。在內(nèi)容安排方面，本章首先給出 點集剛體 部分配準 問題 的 描述及解決方案，接著 提出本文的第一個 創(chuàng)新點， 一種能夠自動計算點集重疊百分比的快速魯棒的剛體配準算法 ， 然后詳盡 闡述 算法 的基本 思想 原理和算法解決問題的步驟流程， 最后 就是給出 實驗結(jié)果 ，并根據(jù)結(jié)果一些數(shù)學品質(zhì)考察此算法的性能。 剛體部分配準問題 問題描述 傳統(tǒng) ICP 算法假設(shè)形狀點集 P 中每一點都能在模型點集 M 中找到與之 相 對應(yīng)的點，即 假定了 兩個待配準點集之間存在 完整的對應(yīng) 關(guān)系。然而在 現(xiàn)實環(huán)境中圖像配準問題中，由于 攝 相機拍攝角度 ， 障礙物遮擋， 傳感器噪聲以及圖像處理過程噪聲等因素的影響， 因而存在這樣一種情況： 點集 P 中 僅有部分點能夠在點集 M 找到相對應(yīng)的點 ， 即 兩個點 集之間僅存在部分對應(yīng)的關(guān)系 ，而且很可能 P 中能找到對應(yīng)點的點集是非常小的一部分。 在這種情況下，傳統(tǒng)的 ICP 算法就無法保證配準結(jié)果的魯棒性， 無法得到較為精確的配準結(jié)果，而且非匹配點集 所占比例越大則往往得到錯誤配準 結(jié)果 的幾率更大 。 如果按照 點集對應(yīng)關(guān)系 來分類，則通常認為 點集部分 配準問題可以分為兩大類：一類是具有 點集中部分 數(shù)據(jù) 丟失或點集中含有大量 離群點的點集配準，而另一類是具有形狀噪聲的點集配準問題。 第一類 往往是由于 攝像機兩次 拍 攝角度不同，或者兩次采集圖像時障礙物遮擋情況不一，再或者是采集設(shè)備自身缺陷等原因而造成的 。它 主要表現(xiàn)為兩個點集之間 僅有一部分點集是能夠?qū)?yīng)起來的，而其他部分則完全相異 ， 并