【正文】 以標(biāo)注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過的研究成果，也不包含我為獲得 及其它教育機構(gòu)的學(xué)位或?qū)W歷而使用過的材料。對本研究提供過幫助和做出過貢獻(xiàn)的個人或集體，均已在文中作了明確的說明并表示了謝意。對本文的研究做出重要貢獻(xiàn)的個人和集體，均已在文中以明確方式標(biāo)明。 涉密論文按學(xué)校規(guī)定處理。 本 文 從介紹 剛體 配準(zhǔn) 問題出發(fā)，著重闡述基于迭代最近點算法的剛體部分配準(zhǔn)問題 ，最后 將此算法應(yīng)用到地圖拼接實例中 。 通過 某種 算法 策略就 可以在圖 中 找到 目標(biāo) 圖像 ，確定其 空間位置。 . 對于 通常意義上圖像 配準(zhǔn)技術(shù)， 我么 可以 簡單地 把它 總結(jié)為 以下 4點選擇的組合 體： 相似度測量 特征空間指的是從圖像中提取出來的用來匹配的信息；搜索空間則是指用來校準(zhǔn)圖像的圖像變換集；搜索策略決定如何在這個空間中選擇下一 個變換，如何測試并搜索出最優(yōu)的變換；相似度測量則決定了每一個配準(zhǔn)測試中的相關(guān)特性 .在圖像配準(zhǔn)中，特征空間、相似度測量、搜索空間以及搜索策略等的選擇都會影響到最后配準(zhǔn)的精確度 。圖像特征 地 提取在過去的幾十年已經(jīng)發(fā)展非常成熟，而最常用的特征 提取方式是 物體的邊緣輪廓，角點，曲面交線， 曲率不連續(xù)點等 ， 在所有 這些 特征中，點是 最為基礎(chǔ)的 ， 它 同時 也 是曲線，曲面 ，立體 等 復(fù)雜特征的表示基礎(chǔ)。如今的三維掃描技術(shù)已經(jīng)相當(dāng)發(fā)達(dá)，它 可以深入到任何復(fù)雜的現(xiàn)場環(huán)境 中 進(jìn)行掃描 工作 ， 然后 直接將 掃描得到的 各種大型的、復(fù)雜的、不規(guī)則、非標(biāo)準(zhǔn)實景三維數(shù)據(jù)完整 無誤 的 存入 到電腦中，進(jìn)而快速重構(gòu)出目標(biāo) 物體 的三維模型 。 而本文將圖像配準(zhǔn)技術(shù)應(yīng)用于地圖拼接問題中，僅僅是一次牛刀小試。 國內(nèi)外研究現(xiàn)狀 點集 配準(zhǔn)問題 最初產(chǎn)生于 計算機視覺， 計算機圖形學(xué) 和圖像處理領(lǐng)域。該問題被提出后得到美國軍方大力的支持和贊助，在經(jīng)過而后長達(dá)二十多年的研究，最終科學(xué)家們在潘興 2式中程導(dǎo)彈及戰(zhàn)斧式巡航導(dǎo)彈上完美的應(yīng)用了圖像配準(zhǔn)技術(shù)，使彈著點平均圓半徑誤差達(dá)到小于 10米左右的精確度，可謂是導(dǎo)彈命中率上至高的一個飛躍。 在 二十世紀(jì)八十年代初期，當(dāng)時 圖像配準(zhǔn)問題的 研究方向 主要 為 最基本的 全局剛體配準(zhǔn)算法，并且往往只針對某些特定形狀的點集進(jìn)行研究 工作 。 直到二十世紀(jì) 九十年代初， 圖像配準(zhǔn)領(lǐng)域中的一個里程碑式的剛體配準(zhǔn)算法被提出，它就是大名鼎鼎的剛體 迭代最近點算 ，英文 Iterative Closet Point（ 簡稱 ICP） 。 這 其中 的例子數(shù)不勝數(shù)，例如， Fitzgibbon 采用LevenbergMarquardt算法 加快 ICP的收斂速度； Jost和 Hugli用了一種由粗到精的搜索策略加快 了 ICP算法 收斂 速度 ； Ezra等分析了 ICP算法的收斂速度 問題， 證明 了 剛體配準(zhǔn) 的 時間復(fù)雜度與點集 中點的 個數(shù) 間的 相關(guān) 性 ；更 多學(xué)者研究 了 ICP算法局部收斂性， 并傾心于擴大算法收斂域 的問題 。李智等提出了基于輪廓相似性度量方式的圖像配準(zhǔn)方法，它適用于輪廓特征比較豐富的圖像配準(zhǔn)?，F(xiàn)在對部分配準(zhǔn)問題的解決方法主要有： 1） 幾何 方法 所謂幾何方法，是指采用幾何約束 條件來排除點集配準(zhǔn)中的噪聲點和大量無信息點對的方法。為了進(jìn)一步改進(jìn)此算法，Yonghuai Liu又將剛體移動的幾何規(guī)律與點集最鄰近約束條件相結(jié)合，通過選擇正確的匹配點對， 再次提高 ICP算法的精度和魯棒性。er將對應(yīng)點集的距離看做一種概率分布，計算其標(biāo)準(zhǔn)方差，迭代過程中排除距離大于該方差的點對。 3） 閾值度量方法 針對提高 ICP算法魯棒性這一問題，很多學(xué)者采用閾值度量方法在迭代過程中排除異常點的干擾，從而提高點集匹配的精度。該類方法的缺點在于閾值或距離度量不好確定，配準(zhǔn)算法往往受到點集形狀的影響，導(dǎo)致收斂性不 好。盡管這些方法能夠一定程度上提高具有異常點的點集配準(zhǔn)的魯棒性，但是往往需要正確的初始化條件，否則在出現(xiàn)大量缺失數(shù)據(jù)時候，很容易陷入局部極值點，從而導(dǎo)致錯誤的 配準(zhǔn) 結(jié)果 。因此， 本文對 點集 剛體配準(zhǔn)問題 ，進(jìn)一步點集部分剛體配準(zhǔn)問題，都 進(jìn)行了 概念和算法原理方面的詳盡闡述 ，分析 了 點集剛體配準(zhǔn) 普遍存在存在的缺陷和 難點 。為了解決這個問題，針對部分區(qū)域能夠重疊情況，我們提出了一個新的目標(biāo)函數(shù)，函數(shù)式中引入了重疊百分比 r。實驗結(jié)果表明， 此 算法是比傳統(tǒng)的ICP 和 目前 國內(nèi)最先進(jìn)的算法更為可靠和高效。而上面研究的剛體部分迭代最盡點算法剛好可以應(yīng)用這個問題中來，于是本文中應(yīng)用了這個算法，然后在 matlab上寫程序?qū)崿F(xiàn)算法，模擬測試了兩張地圖的拼接過程和最終結(jié)果。本章首先給出了點集配準(zhǔn)的概念，然后在此概念上闡述了剛體變換和相似性度量，接著給出了剛體配準(zhǔn)的數(shù)學(xué)模型和流程框圖。 本章首先提出了具有部分?jǐn)?shù)據(jù)丟失的點集部分配準(zhǔn)問題，然后建立基本的數(shù)學(xué)求解模型。 第四章， 基于迭代最近點的地圖拼接方法。談到何謂剛體配準(zhǔn)，首先我們要從點集配準(zhǔn)的概念開始，因為點集配準(zhǔn)是圖像配準(zhǔn)的一項關(guān)鍵技術(shù)，它是從計算機視覺、模式識別和圖像處理的各個領(lǐng)域中抽象出來的一類重要的基礎(chǔ)問題。相似性度量函數(shù)目前已有多種，它 一般都是某個距離的函數(shù) 。在任何力的作用下，體積和形狀都不發(fā)生改變的物體叫做剛體。 點到點的距離又稱為 2 范數(shù)距離，它表示 Rm空間中兩個點 x{x1 ,x2 ,..,xi ,... } 和y{ y1 ,y2 ,..,yi ,... }之間的真實距離： 由于 Euclidean計算 比較簡單，因而它是最為常見和常用的距離，大多數(shù)點集配準(zhǔn)問題都采用它來定義空間中點對的距離。 1 點集配 準(zhǔn)示意圖 給定 R 空間中的兩個點集： S形狀點集 M模型點集 故配準(zhǔn)問題實際上是解決上述兩個未知量，即最優(yōu)的空間變換 T 和確定形狀點集到模型點集的對應(yīng)關(guān)系 C。在經(jīng)典的 ICP算法中，相似性度量 J 采用了上述闡述到的最小平方（ Least Square， LS）距離。 ICP配準(zhǔn)算法通過交替迭代的方式來分別求解這兩個未知變量，算法流程如 圖 錯誤 !文檔中沒有指定樣式的文字。然后 ICP算法 正如它的名字一樣 通過反復(fù)迭代 ，不斷改進(jìn)空間變換和對應(yīng)關(guān)系最終以求達(dá)到最優(yōu)的配準(zhǔn)效果。當(dāng)然實際配準(zhǔn)中，我們很大的可能性是不可能使配準(zhǔn)誤差 k? 達(dá)到它理論上的最小值，因為這可能需要難以忍受的等待時間或者根本就不存在這樣一個最小值。 很多研究和實驗結(jié)果 一致表明 ， kd 樹適合于高維點集的點搜索，而基于 Delaunay 三角化的最近點搜索算法 則 更適 合于低維點集的點搜索。也就是說，在二維情況下得到的是三角形網(wǎng)格，在三維情況下得到的是四面體網(wǎng)格。局部變換法和 Watson 算法是離散點集 Delaunay 三角剖分的常用算法，算法過程中逐點添加、局部優(yōu)化是三角網(wǎng)格生成速度的重要影響因素。 2） SVD 方法 求解 剛體變換 SVD 方法 相當(dāng)比較 簡單，而且具有較好的擴展性，所以 本文采用 奇異值分解 Singular Value Deposition 的方法解決第二步中剛體變換求解。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 實驗結(jié)果 圖 a1 模型圖像 圖 a2 待配準(zhǔn)圖像 圖 a3 配準(zhǔn)結(jié)果 圖 b1 模型圖像 圖 b2 待配準(zhǔn)圖像 圖 b3 配準(zhǔn)結(jié)果 上面所示的實驗結(jié)果圖中，因為為了簡單起見均采用的是黑白圖，而且僅僅是提取了圖片中圖像物體的外部輪廓 線條特征來作配準(zhǔn)的標(biāo)準(zhǔn)。 本章小結(jié) 本章 首先提出了圖像點集配準(zhǔn)問題的概念，接著在數(shù)學(xué)上 建立點集配準(zhǔn) 的 模型 ，隨后又闡述了 在眾多的剛體配準(zhǔn)研究 中最為矚目的由 Besl 和 Mckay 提出的 ICP 算法 ，并且詳盡地論 述了算法運作流程和算法每步中問題的解決方法。 所以本章針對這一問題，會在傳統(tǒng) ICP 算法基礎(chǔ)上，將引入重疊百分比的概念，然后建立關(guān)于空間變換的新目標(biāo)函數(shù)，因而與前面 ICP 算法不同的是在 配準(zhǔn)過程中 ，將 同時更新 三個未知量，即 點集重疊百分比 ， 空間變換 和點間對應(yīng)關(guān)系。然而在 現(xiàn)實環(huán)境中圖像配準(zhǔn)問題中，由于 攝 相機拍攝角度 ， 障礙物遮擋， 傳感器噪聲以及圖像處理過程噪聲等因素的影響， 因而存在這樣一種情況： 點集 P 中 僅有部分點能夠在點集 M 找到相對應(yīng)的點 ， 即 兩個點 集之間僅存在部分對應(yīng)的關(guān)系 ，而且很可能 P 中能找到對應(yīng)點的點集是非常小的一部分。它 主要表現(xiàn)為兩個點集之間 僅有一部分點集是能夠?qū)?yīng)起來的，而其他部分則完全相異 ， 并且 這些非對應(yīng)點存在方式跟外界環(huán)境和 對象物體 形狀 本身有關(guān)，因而 無法 精確 估計 非對應(yīng)點的 分布和幾何位置。本章 即后面的地圖拼接僅涉及到 第一類點集 部分 配準(zhǔn)問題， 所以對于第二類 點集 部分 配準(zhǔn) 在本文 中將不會再被提及和探討。 這就是本文所涉及的剛體點集部分配準(zhǔn)問題。 在前面，本文緒論中范范而談了幾種 處理 部分對應(yīng)點集的配準(zhǔn) 方法， 即 閾值方法，概率方法，幾何方法等，然而這些方法都依賴于待配準(zhǔn)點集的形狀，或 知道了噪聲點服從某個已知出名的 概率分布 函數(shù) ， 而我們面對的情況是未知待配準(zhǔn) 點集 圖像形狀和未知噪聲概率分布函數(shù)這一更為嚴(yán)峻的情景，它往往是具有較大面積數(shù) 據(jù)缺失的情況。 換而言之，對于具有缺失數(shù)據(jù)的點集配準(zhǔn)問題，不僅要確定兩個點集的對應(yīng)關(guān)系和全局的幾何變換，而且還要確定點集的重疊百分比 。 2 給出 了在一般大量 配準(zhǔn) 情景中 ，點集重疊百分比 r 與 均 方 根 誤 差 （ Root Mean Square ， RMS ） 的 關(guān) 系 。理論和實驗 一致 證明 了 ，最優(yōu)的重疊百分比 r并非 像大家想像的那樣理所當(dāng)然的 對應(yīng) 具有最小 配準(zhǔn)誤差 時的值 ，而是 對應(yīng)配準(zhǔn) 誤差突增 時的值 ，即 ?在 值之間 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ù)點集配準(zhǔn)誤差與重疊百分比關(guān)系 圖 錯誤 !文檔中沒有指定樣式的文字。從重疊百分比 ?的大小 考慮： 1） 重疊百分比很小。但是如果重疊百分比 r取值過大， 又 會 產(chǎn)生 在匹配過程中引入 大量不能作 對應(yīng) 的 點 的問題 ，而這些異常 點會提供錯誤的信息， 錯誤引導(dǎo)配準(zhǔn)的進(jìn)行方向 ， 其結(jié)果是 配準(zhǔn)不魯棒。 為了 使下面的算法和傳統(tǒng) ICP 算法相一致，即更為直觀的在配準(zhǔn)誤差達(dá)到最小時，配準(zhǔn)效果也達(dá)到最佳，而不是前面分析的在誤差突變時刻， 本文 借用正則化的思想來 解決 這個問題。 下面 給出新目標(biāo)函數(shù)的數(shù)學(xué)表達(dá)： 給定 Rm 維 空間中的 形狀點集 S 和 模型點集 M，設(shè) r 表示兩個點集的重疊百分比， rS表 示 形狀點集中與模型點集相對應(yīng)的部分點集。 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ù) 圖 錯誤 !文檔中沒有指定樣式的文字。 4 所示： 圖 錯誤 !文檔中沒有指定樣式的文字。算法的內(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