【正文】 其他三個部分（在平面內(nèi)的兩個 translations，一個旋轉(zhuǎn)）完全取決于切口出的樣本。 隨機抽樣策略在這些特性上，往往只會選擇到少數(shù)樣本，這將導致無法確定正確剛體變換的某些部分。 點的選擇 我們首先通過檢查點對的選擇對 ICP 的收斂性的影響。在整個本文中，我們將使用度量是兩個網(wǎng)格中對應點的實際距離的最小二乘平方根。 兩幅網(wǎng)格圖像具有獨立的添加高斯噪聲，離群，輟學。 此外，為了確保變種之間的公平比較，我們作如下假設： 選擇源點的數(shù)量始終是 2,000 元。 最后，我們測試了這種經(jīng)過高收斂速度優(yōu)化的變種結(jié)合算法。 4. 排斥某些點對，在單獨尋找每對點對或考慮整個點對集的基礎(chǔ)上。 該算法被廣泛用于定位三維掃描儀的輸出，通常典型是那種一次只能從一個方向掃描物體的掃描儀。 針對圖像中出現(xiàn)形狀噪聲或者邊緣擾動等點集配準問題 ，本文并沒有提出 一種 配準算法。 3） 將算法成功的應用到地圖拼接中，并獲得的理想的拼接效果，進而進一步證明了算法的正確性和精確性。 這里所謂的 點集部分 配準問題可以分為兩大類：一類 是具有 點集中部分 數(shù)據(jù) 丟失或點集中含有大量 離群點的點集配準，而另一類是具有形狀噪聲的點集配準問題。 下圖是最終的匹配結(jié)果，其中藍色線勾勒的是上面缺失馬頭的圖像，紅色線條勾勒的是上面缺失馬尾部分的圖像，而中央的綠色線條勾勒的是兩幅圖像共有的部分 ，即點集部分配準算法最終配準成功的點集。進入穩(wěn)定狀態(tài)后， ( , )r?Y 會隨著 ? 的減小而增大。 3 迭代最近點部分配準算法 帶重疊百分比的 部分點 ICP 算法 如前面闡述 傳統(tǒng) ICP 算法 流程一樣，這里給出本文中被稱作帶重疊百分比部分點 ICP算法 的 流程圖。既 然配準誤差是關(guān)于重疊百分比的遞增函數(shù)，而最優(yōu)重疊百分比出現(xiàn)在誤差突增的時刻。點集之間能夠作 對應點 個數(shù)很 少， 按照配準 均方差 的度量方式計算誤差將會很 小，但是 此時 配準算法所能夠 利用的點集信息 很少，因而導致配準結(jié)果 并不盡人意，雖然此時配準誤差幾乎為零 。從 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ù)據(jù)點集配準誤差與重疊百分比關(guān)系 圖 錯誤 !文檔中沒有指定樣式的文字。所以前面談到的方法對本文所研究的問題無法適用，我們將采用一個新的方法。 圖 給出二維情況下缺失數(shù)據(jù)點集實例。 在這種情況下，傳統(tǒng)的 ICP 算法就無法保證配準結(jié)果的魯棒性， 無法得到較為精確的配準結(jié)果，而且非匹配點集 所占比例越大則往往得到錯誤配準 結(jié)果 的幾率更大 。 本章 最后 給出 了利用 ICP 算法在matlab 上所做的簡單圖像配準實驗結(jié)果 。 定理（ 1） ： 給定任意兩個 m 維對應點集 1{}Nii?q 和 1{}Nii?n ，當1111NNiiiiNN??????t n q時，目標函數(shù) 221( ) || ||NiiiF ?? ? ??t q t n取得最小值。 在已有的 多種三角剖分的優(yōu)化規(guī)則 中 ，目前公認的具有最好幾何拓撲性質(zhì)的剖分就是符合 Delaunay 規(guī)則的三角剖分。所以我們往往采取均方誤差達到設定范圍下限和 迭代步驟達到指定的循環(huán)次數(shù) 這兩個指標，來決定是否停止迭代。 1所示： 圖 錯誤 !文檔中沒有指定樣式的文字。 現(xiàn)階段剛體配準問題的研究工作中，最為典型的是 ICP 算法，它有效地解決了點集的剛體配準問題，更為非剛體配準算法研究奠定了理論基礎(chǔ)。以上是物理學上對剛體所下的定義，那顧名思義剛體配準就是剛性圖像間的配準，它主要包括旋轉(zhuǎn)和平移變換。 點集配準。接著在此基礎(chǔ)上，本章詳細的闡述了一種采用重疊百分比的變種 ICP 配準算法，此算法可完美解決點集部分配準問題。 本文的組織結(jié)構(gòu) ： 第一章， 緒論。由此也產(chǎn)生了一種新型的魯棒迭代最接近點（ ICP）算法。 在上面介紹到 的 所有用于解決 點集剛體 部分配準問題的方法中 ，大多數(shù) 算法都存在對參數(shù)過于依賴弊端性，而且通常情況下需要待配準點集提供額外信息。 Emanuele Trucco在 ICP算法中引入線性回歸的和中值最小化的方法，在求解空間變換的過程中排除離群點的影響，從而得到更魯棒的空間變化。這類方法的幾何約束條件經(jīng)常需要根據(jù)具體的點集形狀而定，因此適應性不是很強 。郭海濤等提出了一種將遺傳算法（ Geic Algorithm,簡稱 GA）用于圖像配準的算法。它 的提出 ，才標志 點集剛體配準問題 已成為一個歷史 。 進入八十年代后，隨著科學技術(shù)的發(fā)展，圖像點集配準技術(shù)的研究深入到了更為廣大的領(lǐng)域，如遙感圖像處理，模式識別 ，自動導航，醫(yī)學診斷，計算機視覺。但另一方面從應用后結(jié)果分析來看，也充分證明了圖像配準技術(shù)的強大力量和廣泛的應用價值。因此 二維 圖像 配準問題歸根到底可歸結(jié)到二維點集 配準 這個更為簡單直接明了的 問題了，它 是圖像處理 中最為基礎(chǔ)的一個問題 。特征空間 所謂 圖像配準就是將不同傳感器 不同時間、 或不同 氣 候、 亮 度、攝像角度 下 獲取的兩幅或多幅 網(wǎng)格 圖像進行匹配 ，以求達到幾何空間上一致的過程。本人完全意識到本聲明的法律后果由本人承擔。 基于迭代最近點算法的地圖拼接方法研究 畢業(yè)設計（論文）原創(chuàng)性聲明和使用授權(quán)說明 原創(chuàng)性聲明 本人鄭重承諾：所呈交的畢業(yè)設計（論文），是我個人在指導教師的指導下進行的研究工作及取得的成果。 作者簽名： 日期： 年 月 日 學位論文版權(quán)使用授權(quán)書 本學位論文作者完全了解學校有關(guān)保留、使用學位論文的規(guī)定，同意學校保留并向國家有關(guān)部門或機構(gòu)送交 論文的復印件和電子版，允許論文被查閱和借閱。如今，圖像配準技術(shù) 已經(jīng)被廣泛地應用于 各個領(lǐng)域，較為常見的領(lǐng)域有： 計算機視覺、圖像處理 、遙感數(shù)據(jù)分析 等。搜索空間 對于三維圖像配準問題，現(xiàn)在已經(jīng)是如火如荼。 圖像配準的應用領(lǐng)域概括起來主要有如下 4個方面： （ 1） 醫(yī)學圖像分析：腫瘤檢測，白內(nèi)障檢測， CT,MRI,PET圖像結(jié)構(gòu)信息融合，數(shù)字剪輯血管照造影術(shù) (DSA)等； （ 2） 遙感數(shù)據(jù)分析：分類，定位和識別多譜段的場景信息，自然資源監(jiān)控，核生長監(jiān)控，市區(qū)增長監(jiān)控等； （ 3） 模式識別：目標物運動跟蹤，序列圖像分析，特征識別，簽名檢測等； （ 4） 計算機視覺 ：目標定位，自動質(zhì)量檢測等。各個領(lǐng)域所研究的配準技術(shù)都針對各自特殊具體的應用環(huán)境，并結(jié)合自身領(lǐng)域的相關(guān)技術(shù)，而更為抽象統(tǒng)一的圖像點集配準技術(shù)理論并未在科學的層次上被提出和理論建立。 由于 ICP算法 具有 不需要提取點集的特征，不需要對數(shù)據(jù)進行預處理，具有 收斂速度快而 精度高的優(yōu)點，因此 它理所當然的成為了 眾多領(lǐng)域為人所熟知的圖像配準算法 。王小睿等提出并實現(xiàn)了一種自動圖像配準算法，用于圖像的高精度配準，但實際上它是一種使用互相關(guān)函數(shù)作為相似性度量的半自動圖像配準算法；熊興華等提出了將遺傳算法和最小二乘算法結(jié)合用于圖像的子像素級配準 算法 在部分對應點集 配準問題 被提出后很長一段時間內(nèi) ，如何提高算法的精度 成為了廣大研究者共同以追尋的目標 ， 由此而產(chǎn)生的各種優(yōu)秀的部分配準算法大多數(shù) 都是以 經(jīng)典的 ICP算法為基礎(chǔ)， 然后 通過 引入現(xiàn)代科學的 優(yōu)化策略來 實現(xiàn)的 。 2） 概率 方法 通過建立概率模型來約束配準過程，進而提高算法的魯棒性也是一類常見的方法。Dalley通過計算 Schultz距離來設置閾值大小，排除點集中的噪聲點。這些算法在實際問題解決中往往會出現(xiàn)配準精度不高，效率低下等缺點，簡而言之結(jié)果并不盡如人意 。 在此算法中， 通過 每步不斷求解剛體變換，對應關(guān)系， 重疊百分比，最終解決剛體部分配準問題。 本章首先介紹圖像點集配準的研究背景和意義，然后對點集配準問題進行描述并且分析其難點，接著介紹點集 配準的研究現(xiàn)狀，最后給出本文的研究內(nèi)容和組織結(jié)構(gòu)。闡述過程中并給出了該算法的簡要流程和具體步驟，以及每一步中要求解的數(shù)學表達式，更深一步的本文還對算法進行了理論上層次較高的算法分析。所謂點集配準就是尋求兩個圖像點集之間的一種幾何變換，通過變換后能夠使得一個圖像點集中的每個點與 另一個圖像點集中的每個對應點能夠達到空間上最佳的匹配。所以本文中所涉及的變換 T 僅限于旋轉(zhuǎn)和平移，而不包括其他變換，如相似變換、伸縮變換、仿射變換、投影變換和彈性變換等。 ICP 算法 ICP (Iterative Closest Point) 算法最早是由 Besl 和 McKay于 1992 年提出來的一個配準算法，它用于解決兩個點集之間的剛體配準問題。 1 ICP 算法流程 從 圖 錯誤 !文檔中沒有指定樣式的文字。當 ICP 算法 循環(huán) 退出后， 那么返回 得到最終的剛體變換 和點集對應關(guān)系，通過這兩個量我們就可以把兩幅剛性圖像配準了。 Delaunay 剖分必須滿足兩個基本準則，其一是 空圓特性 ，即在 Delaunay 三角形網(wǎng)中任一 個 三角形的外接圓范圍內(nèi)不會有其它點存在。 設 39。 3 基于迭代最近點的部分配準算法 前面 第二章 描述了 ICP 剛體配準 問題并建立了它的數(shù)學 模型 ， 且給出 求解 ICP 剛體配準問題的 具體 方法和原理 ， 接下來 本章 將 在 上面的 基礎(chǔ)上進一步研究基于 ICP（即迭代最近點） 的剛體 部分 配準問題。 如果按照 點集對應關(guān)系 來分類，則通常認為 點集部分 配準問題可以分為兩大類：一類是具有 點集中部分 數(shù)據(jù) 丟失或點集中含有大量 離群點的點集配準，而另一類是具有形狀噪聲的點集配準問題。 其中紅色表示模型點集，藍色表示形狀點集，綠色和天 藍色分別表示兩個點集中多余或者缺失的部分。分析 具有缺失數(shù)據(jù)的點集配準問題，可以發(fā)現(xiàn) 兩個待配準點集之間的重疊百分比是一個重要的衡量標準。 2 可以看出，配準 誤差 是 重疊百分比 r 的 一個簡單的單調(diào)遞增函數(shù) ， 開始重疊百分比 r比很小時配準誤差幾乎為零，因為形狀點集中能夠建立對應關(guān)系的點個數(shù)此時極少 故幾乎不存在 任何誤差，然而當重疊百分比達到某個值時配準誤差開始突增，根據(jù)大量實驗表明此時的 r值在 之間 。2） 重疊百分比 很大。因此可以給該誤差除以一個連續(xù)遞增的懲罰因子，得到一個新的目標函數(shù)。與前面經(jīng)典 ICP 算法顯著的不同是，該算法在 每步迭代中 除了要 計算 求解點集的對應關(guān)系和空間變換 外 ，還要計算點集重疊百分比 r。配準循環(huán)結(jié)束后，算法讓 ? 從 min? 開始往遞增方向搜索，因為在穩(wěn)定狀態(tài)（配準結(jié)果正確）下( , )r?Y 是遞減的，因此第一個使目標函數(shù) ( , )r?Y 遞增的 *? 就是待求的最優(yōu)參數(shù)。從實驗結(jié)果顯示來看，帶重疊百分比的點集部分配準算法對于這類簡單的黑白圖像的配準是理想完美的，從而可見算法的正確性和精確性。 本文 僅對上述第一 類 點集部分配準 問題分別進行了描述和 提出了一種高效的變種 ICP算法， 并且實驗來 驗證了 所提算法的有效性和魯棒性。 雖然本文剛體配準的一般模型，經(jīng)典 ICP 算法和帶重疊百分比的部分點 ICP 算法進行探討，但還有很多地方有待深入的探索，今后進一步的研究工作將集中在如下幾方面： 1）本文提出的目標函數(shù)及算法都采用的是基于歐氏距離下的最小平方距離度量，這種度量方式固然簡單之間，很適合與剛體圖像配準 。首先 可以 從理論上分析采用概率模型來處理該類配準問題可行性 ， 假設兩個待配準點集之間對應關(guān)系服從高斯概率分布，可以通過建立高斯概率模型來計算各個對應點的權(quán)重，對應點距離越小權(quán)重越大，反之亦然。 ICP 算法以兩幅網(wǎng)格圖像和對其初始相對剛體變換的猜測開始， 然后迭代改進變換反復產(chǎn)生對應網(wǎng)格點對，最后使 誤差度量最小。 5. 指定基于點對的誤差度量。 2 比較方法 我們的目標是比較幾種 ICP 備變種收斂特征。 由于我們會考慮的網(wǎng)格有 10 萬個樣本，如果源點從兩個網(wǎng)格 中選擇，那么每個網(wǎng)格的采樣率是 1％；如果源點從一個網(wǎng)格中選擇，那么每個網(wǎng)格的采樣率是 2％ . 所有我們使用的網(wǎng)格都是簡單 視角范圍內(nèi)的圖像，而不是普通不規(guī)則的網(wǎng)格圖像，因為這會產(chǎn)生 “最近點”和“投影點”變種之間的比較（見 節(jié)）。 “分形景觀”測試現(xiàn)場（圖 1 B）包含了各級細節(jié)特征。 使用這樣的“ ground truth”誤差度量保證了關(guān)于 ICP 算法性能更為客觀的比較，相對通過算法自身來計算誤差指標。 以下策略被提出： 始終使 用所有可用點 [Besl 92]。 這樣，一個可以提高機率的方法是有足夠的約束存在以確定轉(zhuǎn)化的所有組成部分，根據(jù)在角度空間的標準位置來 bucket 點 ,那么整個 bucket 過程中盡可能是均勻樣品 . 普通空間采樣是一個用表面特性配準的非常簡單的例子，它具有較低的計算成本代價，但比傳統(tǒng)基于特征的方法具有較低的魯棒性 [Faugeras 86， Stein 92, Johnson