【正文】 97a]。 。 究其原因，是不在溝槽的樣本僅對確定剛體變換的六個部分之中的三個起到作用（一個 translation 和兩個旋轉(zhuǎn)）。這一戰(zhàn)略動機(jī)為了是觀察某些類型的場景下的情況（如： 我們的“下切面”數(shù)據(jù)集），這種模型的細(xì)小特征對確定正確 配準(zhǔn)來說是至關(guān)重要的場景。對于每一個階段，我們在語言上總結(jié)了這些變種，并在我們的測試場景中比較了他們的性能。 我們使用綜合數(shù)據(jù)進(jìn)行比較的動機(jī)是使我們知道完全正確的轉(zhuǎn)換，并可以評估 ICP 算法相對于這一正確路線的性能。 “波”的 場景（圖 la）是最容易出現(xiàn)的 ICP 變種情況，因為它包含了相對平穩(wěn)的粗尺度幾何元素。我們挑選這個算法，是因為它 在生產(chǎn)環(huán)境已得到廣泛使用 Levoy00]，對含有多種表面特征的掃描數(shù)據(jù)十分強勁。 作為比較的一部分，我們提出均勻空間定向抽樣的概念，并表明它在涉及稀疏，細(xì)微 表面特征的場景中 能夠提高收斂性。 3. 適當(dāng)加權(quán)對應(yīng)點對。 ICP 變種算法分類 ICP（迭代最近點，雖然迭代對應(yīng)點也許是一個更好的擴(kuò)展縮寫）算法已成為以純幾何圖形，或者有時加上 顏色，網(wǎng)格的三維模型配準(zhǔn)的主要方法。 3） 研究具有形狀噪聲的剛體點集 部分 配準(zhǔn)問題，提出一種精確的配準(zhǔn)算法。該算法目前是最好的用于解決此類配準(zhǔn)問題的算法，在收斂速度和魯棒性指標(biāo)上。 與此 相反 ， 剛體 點集的 部分 配準(zhǔn)問題 則 是 現(xiàn)在圖像配準(zhǔn)領(lǐng)域 一個難點和熱點 ，因而 本文 也毫不猶豫地將其列為了闡述 的 重點。值得注意的是由于截圖效果不好的原因，看上去兩幅圖似乎是經(jīng)過了伸縮變換，但實際情況是僅僅只有旋轉(zhuǎn)平移和裁剪。算法的內(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)。 0 . 5 0 . 5 5 0 . 6 0 . 6 5 0 . 7 0 . 7 5 0 . 8 0 . 8 5 0 . 9 0 . 9 5 102468101214161820重疊百分比誤差 誤差懲罰函數(shù)新的目標(biāo)函數(shù) 圖 錯誤 !文檔中沒有指定樣式的文字。 為了 使下面的算法和傳統(tǒng) ICP 算法相一致，即更為直觀的在配準(zhǔn)誤差達(dá)到最小時，配準(zhǔn)效果也達(dá)到最佳，而不是前面分析的在誤差突變時刻， 本文 借用正則化的思想來 解決 這個問題。從重疊百分比 ?的大小 考慮： 1） 重疊百分比很小。 2 給出 了在一般大量 配準(zhǔn) 情景中 ，點集重疊百分比 r 與 均 方 根 誤 差 （ Root Mean Square ， RMS ） 的 關(guān) 系 。 在前面，本文緒論中范范而談了幾種 處理 部分對應(yīng)點集的配準(zhǔn) 方法， 即 閾值方法，概率方法，幾何方法等，然而這些方法都依賴于待配準(zhǔn)點集的形狀，或 知道了噪聲點服從某個已知出名的 概率分布 函數(shù) ， 而我們面對的情況是未知待配準(zhǔn) 點集 圖像形狀和未知噪聲概率分布函數(shù)這一更為嚴(yán)峻的情景，它往往是具有較大面積數(shù) 據(jù)缺失的情況。本章 即后面的地圖拼接僅涉及到 第一類點集 部分 配準(zhǔn)問題， 所以對于第二類 點集 部分 配準(zhǔn) 在本文 中將不會再被提及和探討。然而在 現(xiàn)實環(huán)境中圖像配準(zhǔn)問題中，由于 攝 相機(jī)拍攝角度 ， 障礙物遮擋， 傳感器噪聲以及圖像處理過程噪聲等因素的影響， 因而存在這樣一種情況： 點集 P 中 僅有部分點能夠在點集 M 找到相對應(yīng)的點 ， 即 兩個點 集之間僅存在部分對應(yīng)的關(guān)系 ，而且很可能 P 中能找到對應(yīng)點的點集是非常小的一部分。 本章小結(jié) 本章 首先提出了圖像點集配準(zhǔn)問題的概念，接著在數(shù)學(xué)上 建立點集配準(zhǔn) 的 模型 ，隨后又闡述了 在眾多的剛體配準(zhǔn)研究 中最為矚目的由 Besl 和 Mckay 提出的 ICP 算法 ，并且詳盡地論 述了算法運作流程和算法每步中問題的解決方法。 2） SVD 方法 求解 剛體變換 SVD 方法 相當(dāng)比較 簡單，而且具有較好的擴(kuò)展性，所以 本文采用 奇異值分解 Singular Value Deposition 的方法解決第二步中剛體變換求解。也就是說，在二維情況下得到的是三角形網(wǎng)格，在三維情況下得到的是四面體網(wǎng)格。當(dāng)然實際配準(zhǔn)中，我們很大的可能性是不可能使配準(zhǔn)誤差 k? 達(dá)到它理論上的最小值，因為這可能需要難以忍受的等待時間或者根本就不存在這樣一個最小值。 ICP配準(zhǔn)算法通過交替迭代的方式來分別求解這兩個未知變量，算法流程如 圖 錯誤 !文檔中沒有指定樣式的文字。 1 點集配 準(zhǔn)示意圖 給定 R 空間中的兩個點集： S形狀點集 M模型點集 故配準(zhǔn)問題實際上是解決上述兩個未知量，即最優(yōu)的空間變換 T 和確定形狀點集到模型點集的對應(yīng)關(guān)系 C。在任何力的作用下，體積和形狀都不發(fā)生改變的物體叫做剛體。談到何謂剛體配準(zhǔn)，首先我們要從點集配準(zhǔn)的概念開始，因為點集配準(zhǔn)是圖像配準(zhǔn)的一項關(guān)鍵技術(shù)，它是從計算機(jī)視覺、模式識別和圖像處理的各個領(lǐng)域中抽象出來的一類重要的基礎(chǔ)問題。 本章首先提出了具有部分?jǐn)?shù)據(jù)丟失的點集部分配準(zhǔn)問題，然后建立基本的數(shù)學(xué)求解模型。而上面研究的剛體部分迭代最盡點算法剛好可以應(yīng)用這個問題中來，于是本文中應(yīng)用了這個算法，然后在 matlab上寫程序?qū)崿F(xiàn)算法，模擬測試了兩張地圖的拼接過程和最終結(jié)果。為了解決這個問題，針對部分區(qū)域能夠重疊情況，我們提出了一個新的目標(biāo)函數(shù)，函數(shù)式中引入了重疊百分比 r。盡管這些方法能夠一定程度上提高具有異常點的點集配準(zhǔn)的魯棒性，但是往往需要正確的初始化條件，否則在出現(xiàn)大量缺失數(shù)據(jù)時候，很容易陷入局部極值點，從而導(dǎo)致錯誤的 配準(zhǔn) 結(jié)果 。 3） 閾值度量方法 針對提高 ICP算法魯棒性這一問題，很多學(xué)者采用閾值度量方法在迭代過程中排除異常點的干擾，從而提高點集匹配的精度。為了進(jìn)一步改進(jìn)此算法，Yonghuai Liu又將剛體移動的幾何規(guī)律與點集最鄰近約束條件相結(jié)合，通過選擇正確的匹配點對， 再次提高 ICP算法的精度和魯棒性。李智等提出了基于輪廓相似性度量方式的圖像配準(zhǔn)方法，它適用于輪廓特征比較豐富的圖像配準(zhǔn)。 直到二十世紀(jì) 九十年代初， 圖像配準(zhǔn)領(lǐng)域中的一個里程碑式的剛體配準(zhǔn)算法被提出，它就是大名鼎鼎的剛體 迭代最近點算 ，英文 Iterative Closet Point（ 簡稱 ICP） 。該問題被提出后得到美國軍方大力的支持和贊助，在經(jīng)過而后長達(dá)二十多年的研究，最終科學(xué)家們在潘興 2式中程導(dǎo)彈及戰(zhàn)斧式巡航導(dǎo)彈上完美的應(yīng)用了圖像配準(zhǔn)技術(shù)，使彈著點平均圓半徑誤差達(dá)到小于 10米左右的精確度，可謂是導(dǎo)彈命中率上至高的一個飛躍。 而本文將圖像配準(zhǔn)技術(shù)應(yīng)用于地圖拼接問題中，僅僅是一次牛刀小試。圖像特征 地 提取在過去的幾十年已經(jīng)發(fā)展非常成熟，而最常用的特征 提取方式是 物體的邊緣輪廓，角點，曲面交線， 曲率不連續(xù)點等 ， 在所有 這些 特征中，點是 最為基礎(chǔ)的 ， 它 同時 也 是曲線，曲面 ，立體 等 復(fù)雜特征的表示基礎(chǔ)。 . 對于 通常意義上圖像 配準(zhǔn)技術(shù)， 我么 可以 簡單地 把它 總結(jié)為 以下 4點選擇的組合 體： 本 文 從介紹 剛體 配準(zhǔn) 問題出發(fā)，著重闡述基于迭代最近點算法的剛體部分配準(zhǔn)問題 ，最后 將此算法應(yīng)用到地圖拼接實例中 。對本文的研究做出重要貢獻(xiàn)的個人和集體，均已在文中以明確方式標(biāo)明。盡我所知，除文中特別加以標(biāo)注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過的研究成果，也不包含我為獲得 及其它教育機(jī)構(gòu)的學(xué)位或?qū)W歷而使用過的材料。本人授權(quán) 大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。 而傳統(tǒng)意義上的 匹配就是在一幅 比較大的 圖像中搜尋 與目標(biāo)圖像相同的部分 ， 在 已知該圖中 具有 要找的目標(biāo) 圖像的情況下 。搜索策略 近年來 伴隨著 逆向工程技術(shù) 和三維掃描技術(shù) 的飛速 發(fā)展 ， 三維圖像配準(zhǔn)問題已是一個不得 不妥善解決的難題。 圖像配準(zhǔn)技術(shù)在很多領(lǐng)域都有著廣泛的應(yīng)用，因此，今年來，它已成為圖像處理技術(shù)研究的重點課題。 直到 70年代初， FFT進(jìn)行互相關(guān)圖像檢測計算的圖像配準(zhǔn)技術(shù)，以提高配準(zhǔn)過程的收斂速度性能； 值相似性度量的圖像配準(zhǔn)技術(shù)，它比使用 FFT計算互相關(guān)相似度量進(jìn)行圖像檢測技算的圖像配準(zhǔn)方法更具高的性能； ； 等對圖像配準(zhǔn)的相似性度量和預(yù)處理方法進(jìn)行了比較分析； 型的動態(tài)程序設(shè)計方法用于幾何畸變較大的圖像配準(zhǔn)； Flussr針對變形圖像間的匹配又提出了一個自適應(yīng)映射方法，自動地對兩幅遙感圖像進(jìn)行分割，使得分割后兩幅圖像中相應(yīng)子塊間的相似性度很大，從這些子塊的空間位置關(guān)系來對原來的兩幅圖像進(jìn)行匹配。在 ICP算法被提出后 的二十年內(nèi)，大量學(xué)者從 收斂 速度和收斂性 方面 對 ICP算法做了大量的 理論 研究和 實驗論證，因此更多的針對更為復(fù)雜現(xiàn)實情景中圖像配準(zhǔn)的變種 ICP 算法被提出 。 點集的部分配準(zhǔn)問題主要涉及兩類：一是待配準(zhǔn)點集和目標(biāo)點集間存在部分?jǐn)?shù)據(jù)丟失，即僅能夠作部分點集的對應(yīng)；另一是在各種各樣的噪聲干擾下產(chǎn)生了較大量的 離群點，不穩(wěn)定幾何點，多余點 的情景。Zin223。 Zhang則結(jié)合高斯概率分布規(guī)律，通過設(shè)定閾值 來排除噪聲 點。 本文的研究內(nèi)容 點集 剛體 配準(zhǔn) 作 為 圖像配準(zhǔn)的 一項基礎(chǔ)而 關(guān)鍵的 技術(shù) ， 它 是 計算機(jī)圖形學(xué) ，機(jī)器視覺和圖像分析領(lǐng)域的一個關(guān)鍵問題 和研究重點。這種新的算法使用盡可能多的點 對，以求產(chǎn)生兩個點集之間更可靠和準(zhǔn)確的 配準(zhǔn) 結(jié)果。 第二章， 剛體迭代最近點算法。最后實驗結(jié)果和分析是在二維剛體情景中進(jìn)行的，對不同圖像情景在配準(zhǔn)算法參數(shù)和循環(huán)次數(shù)已經(jīng)配準(zhǔn)時間上進(jìn)行了列表展示和分析比較。對在不同時間、不同視角、不同成像模式等不同條件下獲得的兩幅圖像（包括二維平面圖像和三維深度圖像）進(jìn)行配準(zhǔn)，就是要確定如何來度量或者說是考察兩幅圖像在空間上位置的差異，這可以是一個數(shù)學(xué)函數(shù)，在本文中我們姑且稱其為相似性度量函數(shù)。 在數(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。 ICP算法 的目標(biāo)是尋找一個剛體變換， 即旋轉(zhuǎn)矩陣 R 和平移向量 t ，使得 給定形狀點集和模型點集中的點能夠在 Euclidean歐式距離空間上對應(yīng)起來。 1可以看出， 經(jīng)典的 ICP算法首先由人為估計給定 一個初始的 空間變換 ，并且這個初始值要求應(yīng)當(dāng)粗略正確。 算法求解 對第一步求解，有 kd 樹、基于 Delaunay(德勞內(nèi) )三角化的最近點搜索算法等 。 其二是 最大化最小角特性 ，即 在散點集可能形成的三角剖分中， Delaunay 三角剖分所形成的三角形的最小角最大。 11i k i k???s R s t ， 那么式最小化目標(biāo)函數(shù)為： 39。 因為 傳統(tǒng)的 ICP 算法 是建立在 假設(shè)兩個待配準(zhǔn)點集 中所有點都是有其相對應(yīng)關(guān)系的前提下的 ， 它 并未 考慮到實際中存在的復(fù)雜情況，如障礙物 遮擋，拍攝角度 狹窄 及傳感器噪聲等 因素所造成的點集 部分 數(shù)據(jù) 丟失或存在大量離群點情況下圖像點集的配準(zhǔn) 。 第一類 往往是由于 攝像機(jī)兩次 拍 攝角度不同，或者兩次采集圖像時障礙物遮擋情況不一，再或者是采集設(shè)備自身缺陷等原因而造成的 。 仔細(xì)觀察 31 中的兩