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