【正文】 配的信息；搜索空間則是指用來校準(zhǔn)圖像的圖像變換集；搜索策略決定如何在這個空間中選擇下一 個變換，如何測試并搜索出最優(yōu)的變換；相似度測量則決定了每一個配準(zhǔn)測試中的相關(guān)特性 .在圖像配準(zhǔn)中，特征空間、相似度測量、搜索空間以及搜索策略等的選擇都會影響到最后配準(zhǔn)的精確度 。 涉密論文按學(xué)校規(guī)定處理。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫的成果作品。為了配準(zhǔn)這類 圖像，可以采用空域的方法來去除這些差別 . 第二類：獲取圖像 環(huán)境條件 的不同，這主要是由于光照或者天氣條件不同而造成的 差別 ，這樣 圖像在亮度 或局部 上有所區(qū)別， 但 也有 可能 在空域中產(chǎn)生 細(xì)微 差別，例如透視變形 . 第三類：圖像的差別是由于目標(biāo)的運動，生長或者其他景物的變化而引起的 . 第二類和第三類圖像 之間 差別并不是 能夠 直接通過 圖像 配準(zhǔn) 可以完全 消除的， 所以 這給圖像配準(zhǔn)帶來了 極大的挑戰(zhàn)。 由上，圖像配準(zhǔn)技術(shù)在二維或者三維圖像處理中的廣泛的應(yīng)用基礎(chǔ)，可以看出它重 要性和發(fā)展前景 。八十年代的點集 剛體 配準(zhǔn)的 算法，總結(jié)起來都是 集中于對已知對應(yīng)關(guān)系的點 集 求解 最佳 剛體變換，并且都是以歐氏空間中的最小平方準(zhǔn)則作為相似性度量函數(shù) 的 。 Yonghuai Liu通過分析剛體移動的特性，引入幾何約束條件來去除 ICP算法中錯誤的匹配點。 RodriguezLosada在細(xì)匹配之前，過濾掉和粗匹配結(jié)果差異過大的點對。為了從多個相機拍攝得到的地圖圖像拼接起來以得到一張大的信息量更多的圖像，就需要一種技術(shù)能夠?qū)⑦@些圖像拼接起來。 2 剛體迭代最近點算法 剛體配準(zhǔn)問題 剛體配準(zhǔn)是圖像配準(zhǔn)問題中一類最為基礎(chǔ)和簡單的，很多其他的復(fù)雜高級的配準(zhǔn)問題的解決之道都是在其基礎(chǔ)上研究發(fā)展而得到的，所以對剛體配準(zhǔn)問題的理解在本文后面的工作中至關(guān)重要。 圖 錯誤 !文檔中沒有指定樣式的文字。當(dāng) k? 達(dá)到 我們設(shè)定的某個范圍值下 限時，我們就可以讓 ICP 算法停止迭代退出了。該搜索策略大幅度提高了點集對應(yīng)關(guān)系求解的速度和精度。 剛體部分配準(zhǔn)問題 問題描述 傳統(tǒng) ICP 算法假設(shè)形狀點集 P 中每一點都能在模型點集 M 中找到與之 相 對應(yīng)的點，即 假定了 兩個待配準(zhǔn)點集之間存在 完整的對應(yīng) 關(guān)系。所以這 是本章要解決的一個 艱巨重要的 關(guān)鍵問題。 所以說重疊百分比 ?是很重要的 ， 最基本的 要求 是 該百分比 ?能盡可能多 地包括兩個點集 中能夠相 對應(yīng)的部分，而且還要盡可能排除所有離群點 。 根據(jù)上述分析， 目標(biāo)函數(shù)的 最小值點所對應(yīng)得 到的 重疊百分比就是要求解的最優(yōu)重疊百分比 ，此值在下圖中為 。 上面兩圖是將作為配準(zhǔn)的原始材料，可以明顯的看出兩幅圖中都有各自缺失的部分，左邊的圖缺失了馬尾部分，右邊的圖缺失了馬頭的部分 。 2） 提出了用于解決因部分?jǐn)?shù)據(jù)丟 失情況下剛體部分配準(zhǔn)問題的算法，帶重疊百分比的部分點 ICP算法。 我們列舉和分類了很多這些變種算法，并且估計出了它們按照正確路徑收斂的速度 . 為了提高小近 GAT 網(wǎng)格的收斂功能，如 inscribed sugaces，我們引入一個新的基于均勻采樣的空間法線的變種 我們最終提出一種結(jié)合了其它變種 ICP 算法而具有 高收斂速度的算法 . 我們將展示一個能夠在幾十毫秒范圍內(nèi)配準(zhǔn)兩副圖像的實例，以此證明了我們的初始猜測是很好的 . 算法的這種潛在能力，能夠被應(yīng)用到 3D 實時模型的采集和基于模型的跟蹤應(yīng)用環(huán)境中。 在本文中，我們首先提出用于進行比較 ICP 變種的方法，并介紹一些在本文中使用的測試場景 接下來，我們總結(jié)了上述六大類中每種類型的幾種 ICP 變種，并比較了其收斂性能。 測試場景 我們使用三個綜合生成的場景，以評估的變種。 3 ICP 變種的比較 我們現(xiàn)在審查在節(jié) 1 中列出的每個階段的 ICP 變種。對這組數(shù)據(jù)集，只有正態(tài)空間采樣是能夠收斂的。 讓我們在“波”的場景中來比較均勻子采樣，隨 機采樣，普通空間采樣的性能（圖 2）。我們只呈現(xiàn)一個為每個測試變種運行的結(jié) 果。 曲面的法線計算只是基于四個近鄰范圍內(nèi)的網(wǎng)格。 6. 最大限度地減少誤差度量。 最后， 在該思想的基礎(chǔ)上 可 引入一種基于 EM估計 ， 更新概率模型的帶噪 省點集 的剛體配準(zhǔn)算法。最后，文章將所提 算法成功應(yīng)用于 一個小小的簡單的實際應(yīng)用，二維平面地圖的拼接 。該點對應(yīng)的 *( , )r?Ψ 是最優(yōu)的目標(biāo)函數(shù)，而其對應(yīng)的裁剪度 *r 和剛 體變換也是最優(yōu)的配準(zhǔn)結(jié)果。 如果懲罰因子選擇合適，所得新的目標(biāo)函數(shù)就是 一個凸函數(shù)，而該凸函數(shù)的最小值點就是最優(yōu)重疊百分比對應(yīng)的取值點。 接下要做的是尋找最優(yōu)的r 值 ， 所謂最優(yōu)的重疊百分比，是指在該百分比值下 能夠 求得 最優(yōu) 的空間變換 ，即形狀點集中那部分能夠建立對應(yīng)的點集能夠最佳的與模型點集中相對應(yīng)的部分點集能夠在幾何空間上達(dá)到一致 。 仔細(xì)觀察 31 中的兩幅圖 可以看出，形狀點集中 的綠色部分在模型點集中無法找到相對應(yīng)的部分，而模型點集中天藍(lán)色部分在形狀點集中也無法對應(yīng)起來 。 因為 傳統(tǒng)的 ICP 算法 是建立在 假設(shè)兩個待配準(zhǔn)點集 中所有點都是有其相對應(yīng)關(guān)系的前提下的 ， 它 并未 考慮到實際中存在的復(fù)雜情況，如障礙物 遮擋，拍攝角度 狹窄 及傳感器噪聲等 因素所造成的點集 部分 數(shù)據(jù) 丟失或存在大量離群點情況下圖像點集的配準(zhǔn) 。 其二是 最大化最小角特性 ，即 在散點集可能形成的三角剖分中， Delaunay 三角剖分所形成的三角形的最小角最大。 1可以看出， 經(jīng)典的 ICP算法首先由人為估計給定 一個初始的 空間變換 ，并且這個初始值要求應(yīng)當(dāng)粗略正確。 在數(shù)學(xué)上建立剛體變換的模型相當(dāng)簡單： 給定 Rm 維 空間中的 形狀點集 S 和 模型點集 M，假設(shè) 存在任意兩點 ?xS和 ?yM ，那么剛體變換 的數(shù)學(xué)表達(dá)式 為： ??y R x t X —— 原始點集 Y —— 變換后點集 R —— m x m 維的旋轉(zhuǎn)矩陣， R 滿足 如下約束 ： t —— m 維的平移向量 圖像點集配準(zhǔn)中一個重要的量 —— 相似性度量 J。最后實驗結(jié)果和分析是在二維剛體情景中進行的，對不同圖像情景在配準(zhǔn)算法參數(shù)和循環(huán)次數(shù)已經(jīng)配準(zhǔn)時間上進行了列表展示和分析比較。這種新的算法使用盡可能多的點 對，以求產(chǎn)生兩個點集之間更可靠和準(zhǔn)確的 配準(zhǔn) 結(jié)果。 Zhang則結(jié)合高斯概率分布規(guī)律，通過設(shè)定閾值 來排除噪聲 點。 點集的部分配準(zhǔn)問題主要涉及兩類：一是待配準(zhǔn)點集和目標(biāo)點集間存在部分?jǐn)?shù)據(jù)丟失，即僅能夠作部分點集的對應(yīng)；另一是在各種各樣的噪聲干擾下產(chǎn)生了較大量的 離群點，不穩(wěn)定幾何點，多余點 的情景。 直到 70年代初， FFT進行互相關(guān)圖像檢測計算的圖像配準(zhǔn)技術(shù)，以提高配準(zhǔn)過程的收斂速度性能； 值相似性度量的圖像配準(zhǔn)技術(shù)，它比使用 FFT計算互相關(guān)相似度量進行圖像檢測技算的圖像配準(zhǔn)方法更具高的性能； ； 等對圖像配準(zhǔn)的相似性度量和預(yù)處理方法進行了比較分析； 型的動態(tài)程序設(shè)計方法用于幾何畸變較大的圖像配準(zhǔn)； Flussr針對變形圖像間的匹配又提出了一個自適應(yīng)映射方法，自動地對兩幅遙感圖像進行分割，使得分割后兩幅圖像中相應(yīng)子塊間的相似性度很大，從這些子塊的空間位置關(guān)系來對原來的兩幅圖像進行匹配。 近年來 伴隨著 逆向工程技術(shù) 和三維掃描技術(shù) 的飛速 發(fā)展 ， 三維圖像配準(zhǔn)問題已是一個不得 不妥善解決的難題。 而傳統(tǒng)意義上的 匹配就是在一幅 比較大的 圖像中搜尋 與目標(biāo)圖像相同的部分 ， 在 已知該圖中 具有 要找的目標(biāo) 圖像的情況下 。盡我所知，除文中特別加以標(biāo)注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過的研究成果，也不包含我為獲得 及其它教育機構(gòu)的學(xué)位或?qū)W歷而使用過的材料。 本 文 從介紹 剛體 配準(zhǔn) 問題出發(fā)，著重闡述基于迭代最近點算法的剛體部分配準(zhǔn)問題 ，最后 將此算法應(yīng)用到地圖拼接實例中 。圖像特征 地 提取在過去的幾十年已經(jīng)發(fā)展非常成熟，而最常用的特征 提取方式是 物體的邊緣輪廓，角點，曲面交線， 曲率不連續(xù)點等 ， 在所有 這些 特征中，點是 最為基礎(chǔ)的 ， 它 同時 也 是曲線，曲面 ，立體 等 復(fù)雜特征的表示基礎(chǔ)。該問題被提出后得到美國軍方大力的支持和贊助，在經(jīng)過而后長達(dá)二十多年的研究，最終科學(xué)家們在潘興 2式中程導(dǎo)彈及戰(zhàn)斧式巡航導(dǎo)彈上完美的應(yīng)用了圖像配準(zhǔn)技術(shù)，使彈著點平均圓半徑誤差達(dá)到小于 10米左右的精確度，可謂是導(dǎo)彈命中率上至高的一個飛躍。李智等提出了基于輪廓相似性度量方式的圖像配準(zhǔn)方法，它適用于輪廓特征比較豐富的圖像配準(zhǔn)。 3） 閾值度量方法 針對提高 ICP算法魯棒性這一問題，很多學(xué)者采用閾值度量方法在迭代過程中排除異常點的干擾，從而提高點集匹配的精度。為了解決這個問題，針對部分區(qū)域能夠重疊情況，我們提出了一個新的目標(biāo)函數(shù)，函數(shù)式中引入了重疊百分比 r。 本章首先提出了具有部分?jǐn)?shù)據(jù)丟失的點集部分配準(zhǔn)問題，然后建立基本的數(shù)學(xué)求解模型。在任何力的作用下，體積和形狀都不發(fā)生改變的物體叫做剛體。 ICP配準(zhǔn)算法通過交替迭代的方式來分別求解這兩個未知變量，算法流程如 圖 錯誤 !文檔中沒有指定樣式的文字。也就是說，在二維情況下得到的是三角形網(wǎng)格，在三維情況下得到的是四面體網(wǎng)格。 本章小結(jié) 本章 首先提出了圖像點集配準(zhǔn)問題的概念，接著在數(shù)學(xué)上 建立點集配準(zhǔn) 的 模型 ，隨后又闡述了 在眾多的剛體配準(zhǔn)研究 中最為矚目的由 Besl 和 Mckay 提出的 ICP 算法 ，并且詳盡地論 述了算法運作流程和算法每步中問題的解決方法。本章 即后面的地圖拼接僅涉及到 第一類點集 部分 配準(zhǔn)問題， 所以對于第二類 點集 部分 配準(zhǔn) 在本文 中將不會再被提及和探討。 2 給出 了在一般大量 配準(zhǔn) 情景中 ，點集重疊百分比 r 與 均 方 根 誤 差 （ Root Mean Square ， RMS ） 的 關(guān) 系 。 為了 使下面的算法和傳統(tǒng) ICP 算法相一致，即更為直觀的在配準(zhǔn)誤差達(dá)到最小時，配準(zhǔn)效果也達(dá)到最佳，而不是前面分析的在誤差突變時刻， 本文 借用正則化的思想來 解決 這個問題。算法的內(nèi)循環(huán)迭代流程類似于傳統(tǒng) ICP 算法，但是循環(huán)體內(nèi)增加了求解點集重疊百分比的步驟，具體流程為： 1)根據(jù) ( 1)k? 步的剛體變換 11( , )kk??Rt ，計算點集 S 和 M 的對應(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ù) 上步求得的 對應(yīng)點集 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ù) 的 最小化 值 計算第 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 時，才能計算出準(zhǔn)確的剛體變換，這時點集配準(zhǔn)會趨于穩(wěn)定狀態(tài)。 與此 相反 ， 剛體 點集的 部分 配準(zhǔn)問題 則 是 現(xiàn)在圖像配準(zhǔn)領(lǐng)域 一個難點和熱點 ，因而 本文 也毫不猶豫地將其列為了闡述 的 重點。 3） 研究具有形狀噪聲的剛體點集 部分 配準(zhǔn)問題，提出一種精確的配準(zhǔn)算法。 3. 適當(dāng)加權(quán)對應(yīng)點對。我們挑選這個算法，是因為它 在生產(chǎn)環(huán)境已得到廣泛使用 Levoy00]，對含有多種表面特征的掃描數(shù)據(jù)十分強勁。 我們使用綜合數(shù)據(jù)進行比較的動機是使我們知道完全正確的轉(zhuǎn)換，并可以評估 ICP 算法相對于這一正確路線的性能。這一戰(zhàn)略動機為了是觀察某些類型的場景下的情況（如： 我們的“下切面”數(shù)據(jù)集），這種模型的細(xì)小特征對確定正確 配準(zhǔn)來說是至關(guān)重要的場景。 。 以下策略被提出： 始終使 用所有可用點 [Besl 92]。 “分形景觀”測試現(xiàn)場（圖 1 B）包含了各級細(xì)節(jié)特征。 2 比較方法 我們的目標(biāo)是比較幾種 ICP 備變種收斂特征。 ICP 算法以兩幅網(wǎng)格圖像和對其初始相對剛體變換的猜測開始， 然后迭代改進變換反復(fù)產(chǎn)生對應(yīng)網(wǎng)格點對，最后使 誤差度量最小。 雖然本文剛體配準(zhǔn)的一般模型，經(jīng)典 ICP 算法和帶重疊百分比的部分點 ICP 算法進行探討，但還有