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