【正文】 這表明對(duì)一個(gè)正態(tài)分布的場(chǎng)景來說，精確抽樣策略并不是至關(guān)重要。任何情況下，文中提出的結(jié)果是不典型。 隨著最后一個(gè)例外，我們期望改變?nèi)魏芜@些實(shí)施選擇會(huì)影響 quantitative，而不是定性的，我們測(cè)試中的表現(xiàn)。 雖然我們的主要焦點(diǎn)是在收斂速度，我們還考慮了最終答案的準(zhǔn)確度 和當(dāng)給定“困難”幾何圖形時(shí)， ICP 算法可以得到正確解決方案的能力 . 我們比較表明這種 ICP 變種的組合，是能夠在幾十毫秒內(nèi)對(duì)齊兩幅網(wǎng)格圖像的，其速度明顯快于那些最為常用 的 ICP 算法系統(tǒng)。這種從全局到局部的思想，既保證了配準(zhǔn)的穩(wěn)定性， 又有效處理 了 待配準(zhǔn)點(diǎn)集的形狀噪聲 。還有更多的圖像配準(zhǔn)問題并沒有涉及到，并且也沒有參考比較到其它針對(duì)點(diǎn)集部分配準(zhǔn)算法，因而顯得有些不具說服力，這是本文最為不足的地方，也是知識(shí)所閱甚少的緣故。 下面是實(shí)驗(yàn)結(jié)果所展示的效果和一些統(tǒng)計(jì)圖，本次圖像配準(zhǔn)的實(shí)驗(yàn)誤差 采用 的是 均方根（ Root Mean Square， RMS）誤差 度量 。 新的目標(biāo)函數(shù)定 義為 關(guān)于重疊百分比 r 和調(diào)控參數(shù) ? 的函數(shù)： 2( ) 2, , , ,m in m a x1m in || || . . , de t( ) 1 [ , ] , [ , 1 ] , | | | |riri c ic r STrrerstrr??? ? ???????????RtsSRs t mR R I RS S S S 點(diǎn)集配準(zhǔn)均方誤差 : 2( ) 2( ) || ||ir i c iM S E r ?? ? ??sS R s t m 懲罰函數(shù) : ( , )r e r????? 則 目標(biāo)函數(shù) 又 可以表示 為： ()( , ) ( , )MSE rr r? ???Y 如 下圖所示， 藍(lán)色點(diǎn)線 是 配準(zhǔn)誤差 MSE 函數(shù) ，綠色 點(diǎn)線 是 懲罰函數(shù) (, )r??，而紅色點(diǎn)線則 是 目標(biāo)函數(shù) ( , )r?Y 。 2 配準(zhǔn)誤差與重疊百分比 與 傳統(tǒng) ICP 配準(zhǔn)算法 相比較，因?yàn)閭鹘y(tǒng) ICP 配準(zhǔn)算法 假設(shè) 了 形狀點(diǎn)集和模型點(diǎn)集 間具有完整 完全 的點(diǎn) 對(duì)應(yīng)， 故 當(dāng)均方誤差達(dá)到最小時(shí) 所求得空間變換 也是 點(diǎn)集配準(zhǔn) 過程中最優(yōu)的變換 ，再經(jīng)過多次迭代后配準(zhǔn)誤差更小，空間變換更優(yōu)，最終配準(zhǔn)結(jié)果趨于最佳 。 圖 31 缺失數(shù)據(jù)點(diǎn)集 如何解決上述 具有 部分 數(shù)據(jù)缺失 的點(diǎn)集配準(zhǔn)問題呢？大家都會(huì)想到的很簡(jiǎn)單的考慮是先 要 排除待配準(zhǔn) 點(diǎn)集中 彼此 多余或者缺失的部分， 僅留下能夠相對(duì)應(yīng)起來的部分， 否則 不大可能得到可靠的配準(zhǔn)結(jié)果 。很明顯相對(duì)傳統(tǒng)的 ICP算法新增了重疊百分比這個(gè)變量，所以算法也相應(yīng)變得更為復(fù)雜，更具挑戰(zhàn)性。 根據(jù) Delaunay 三角剖分原理 ，可以構(gòu)造出各種適合該網(wǎng)格形狀的搜索策略。那 ICP算法是如何改進(jìn)每步迭代中的變換量和對(duì)應(yīng)量的呢？下面給出具體的數(shù) 學(xué)表達(dá)式，來闡述 原理 ： 1） 根據(jù) 1k? 步的剛體變換 11( , )kk??Rt 來 確定形狀點(diǎn)集和模型點(diǎn)集間每個(gè)點(diǎn)的對(duì)應(yīng)關(guān)系 21 1 2( ) a r g m i n ( | | ( ) | | ) , 1 , 2 , . . . ,k k i k j sc i i N??? ? ? ?R s t m 2） 計(jì)算兩個(gè)點(diǎn)集 1 1 1{( )} sNk i k i? ? ??R s t 和 ( ) 1{}sk Nc i i?m之間新的剛體變換： T2** 1 1 ( )2, d e t ( ) 1 , 1( , ) a r g m i n ( ( ) )pksNk i k c ii ???? ?? ? ? ??R R I R tR t R R s t t m 3） 更新第 k 步的變換 kR 和 kt ： * * *11 , k k k k??? ? ?R R R t R t t ICP 算法是一個(gè)迭代過程，那么算法在何處停止迭代而退出呢？這就涉及到如何判定圖像點(diǎn)集配準(zhǔn)所達(dá)到的效果程度，很簡(jiǎn)單明了的一種方式是總體上形狀點(diǎn)集中點(diǎn)和模型點(diǎn)集中對(duì)應(yīng)點(diǎn)的 2 維范數(shù)以達(dá)到最小。以點(diǎn)到點(diǎn)的 Euclidean 距離為基礎(chǔ)作相似性度量，最為常見的是兩個(gè)集合之間的最小平方（ Least Square， LS）準(zhǔn)則。 第五章， 結(jié)論與展望。 2）給出基于迭代最近點(diǎn)的部分配準(zhǔn)算法在地圖拼接方法中的應(yīng)用。 4） 由粗到精的方法 另外一些學(xué)者采用由粗到精的策略來提高缺失數(shù)據(jù)點(diǎn)集配準(zhǔn)的魯棒性 。 Atasha Gelfand提出一種保證空間變換穩(wěn)定性的點(diǎn)集提取方法，從而提高 ICP算法的幾何穩(wěn)定性。 隨后 八十年代 末 期 ， 對(duì) 無需提取圖像點(diǎn)集特征而 直 接 進(jìn)行配準(zhǔn)的 圖像配準(zhǔn) 方法 被廣泛的提出和運(yùn)用 ，但 這 還是限于某些特殊 簡(jiǎn)單 的 情景 。 與此 同時(shí)， 三維掃描儀所掃描 的三維 數(shù)據(jù) 或 點(diǎn)云數(shù)據(jù)還可進(jìn)行各種后 期 處理 ， 如測(cè)繪、計(jì)量、分析、仿真、模擬、展示、監(jiān)測(cè)、虛擬現(xiàn)實(shí)等 。 利用 較為簡(jiǎn)單和成熟的 模板匹配可以在一幅圖像中找到 目標(biāo)圖像，例如 抓拍到 的 一張射門的照片， 而 要在該照片中找到足球的位置 ， 這時(shí)就可以采用模板匹配的方法 。 作 者 簽 名： 日 期： 指導(dǎo)教師簽名： 日 期： 使用授權(quán)說明 本人完全了解 大學(xué)關(guān)于收集、保存、使用畢業(yè)設(shè)計(jì)（論文）的規(guī)定，即：按照學(xué)校要求提交畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版本；學(xué)校有權(quán)保存畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)；學(xué)校可以采用影印、縮印、數(shù)字化或其它復(fù)制手段保存論文；在不以贏利為目的前提下，學(xué)?？梢怨颊撐牡牟糠只蛉?jī)?nèi)容。點(diǎn)特征作為圖像最為簡(jiǎn)單和常用的特征形式，被廣泛地應(yīng)用于圖像配準(zhǔn)過程中， 因此 圖像點(diǎn)集配準(zhǔn) 是 一項(xiàng)基礎(chǔ)且非常重要的研究課題。 在 較為簡(jiǎn)單 二維圖像配準(zhǔn)過程中，圖像特征一般被表示成點(diǎn) 或 線等 幾何特征 ，然后通過 某個(gè)算法策略來 計(jì)算這些幾何特征 （通常是兩個(gè)點(diǎn)集） 之間最優(yōu) 的 空間變換， 從而 使得圖像能在空間 幾何 上對(duì)應(yīng)起來 ，這就達(dá)到了最終的配準(zhǔn) 。而本文所闡述到的剛體配準(zhǔn)問題則是其他非剛體配準(zhǔn)問題研究的基礎(chǔ)和前提，所以 在過去幾十年里，人們對(duì)于剛體點(diǎn)集配準(zhǔn)做了許多探索 ，取得了很大成就。 相對(duì)于全局點(diǎn)集的 配準(zhǔn)研究 的 比較成熟， 解決方法多且較簡(jiǎn)單，相反 ，部分對(duì)應(yīng)點(diǎn)集的配準(zhǔn)問題還是一個(gè)難點(diǎn) 熱點(diǎn)問題，因此也是本文研究的重點(diǎn) 。 Bjom Jensen在 ICP算法中引入概率距離矩陣，該距離矩陣同時(shí)考慮到傳感器噪音和待匹配目標(biāo)位置的不確定性，從而可以有效排除 異常點(diǎn)。 本文的具體研究?jī)?nèi)容如下 ： 1)研究?jī)H有部分區(qū)域重疊的剛性圖像的配準(zhǔn)問題，提出一種快速魯棒的剛體配準(zhǔn)算法。本章最后還展示了應(yīng)用剛體迭代最近點(diǎn)算法，在 matlab 上配準(zhǔn)兩幅簡(jiǎn)單線條的黑白圖片的實(shí)驗(yàn)結(jié)果，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了初略分析，對(duì)結(jié)果中的不足提出疑問。由于本文僅涉及 Euclidean距離，本文后面僅簡(jiǎn)要闡述了一下 Euclieadn距離度量。 Np 形狀點(diǎn)集中點(diǎn)的個(gè)數(shù)。對(duì)第二步求解，有 SVD(奇異值分解， Singular Value Deposition)、四元組、正交矩陣、雙四元祖方法，本 文 采用的是 SVD 1） Delaunay 三角化 求解 點(diǎn)集 對(duì)應(yīng)關(guān)系 如何把一個(gè)散點(diǎn)集合剖分成不均勻的三角 形網(wǎng)格，這就是散點(diǎn)集的三角剖分問題 。在配準(zhǔn)結(jié)果圖中，需要說明的是 紅色 線是待配準(zhǔn)圖像的輪廓， 綠色 線 是 模型圖像的輪廓，程序結(jié)果并沒有很好的展示配準(zhǔn)后兩者相重疊的輪廓部分。所謂形狀噪聲， 它是指圖像點(diǎn)集位置 與真實(shí)精確的位置相異但差別卻很小，僅僅是一個(gè)小小的擾動(dòng)而已 ，而 且 噪聲往往服從某些概率分布， 如高斯分布。在本文 中， 該百分比 r的最優(yōu)值 是由 配準(zhǔn)誤差來確定。如何講呢？ 最優(yōu)的重疊百分 r一方面要使配準(zhǔn)誤差相對(duì)較小，而另一方面又要盡可能多地利用待配準(zhǔn)點(diǎn)集中能夠作 對(duì)應(yīng)的點(diǎn)，而這兩方面又是相互矛盾對(duì)立的。 然后以后每步迭代中 調(diào)控參數(shù) ? 從 max? 遞減到 min? 。最后，本章通過二維點(diǎn)集配準(zhǔn)實(shí)驗(yàn)進(jìn)一步驗(yàn)證 了 算法的 正確性和精確性 ，實(shí)驗(yàn)結(jié)果顯示在保證配準(zhǔn)時(shí)間效率的前提下，配準(zhǔn)結(jié)果 的效果不隨待配準(zhǔn) 點(diǎn)集 及模型點(diǎn)集形狀和 缺失數(shù)據(jù) 位置 的影響。由于本文提出的算法并沒有限制其應(yīng)用對(duì)象，所以這些算法都具有很好的通用性。 我們可以以算法六個(gè)階段作用來歸類這些變種： 1. 在一幅或兩幅網(wǎng)格圖像中選擇其中部分點(diǎn)集。 點(diǎn)到平面的誤差度量。 雖然這些場(chǎng)面肯定不涵蓋所有可能的掃描對(duì)象類，但它們是許多掃描應(yīng)用中的代表。 上述方案中的每個(gè)都可以選擇只從一幅網(wǎng)格中選擇點(diǎn)，也可以選擇從兩個(gè)網(wǎng)格中選擇源點(diǎn) [戈丁 94]。 這樣，再 加上噪聲和平面部分圖像失真的事實(shí)淹沒了從凹槽采樣點(diǎn)對(duì)的效果， accounts for均勻隨機(jī)抽樣無法收斂到正確的配準(zhǔn)。 隨機(jī)抽樣（每步迭代中選擇不同的點(diǎn)樣本） [Masuda 96]。 這是一個(gè)困難的場(chǎng)景，對(duì) ICP 來講，大部分變種得不到正確的收斂路線，甚至在初始位置給定相對(duì)較小的旋轉(zhuǎn)情況下。 將作為我們基準(zhǔn)選擇的算法是實(shí)質(zhì)上是 [普莉 99]，包含有以下特點(diǎn)： 兩個(gè)網(wǎng)格點(diǎn)隨機(jī)抽樣 匹配選定的每個(gè)點(diǎn)在最接近的樣本在 45 度的來源有一個(gè)正常的其他網(wǎng)正常。在本文中，我們假設(shè)一個(gè)粗略的初始對(duì)齊始終可以得到。 因此， 采用不同度量方式 的 圖像 配準(zhǔn)算法是今后研究的一個(gè)重點(diǎn)。本章首先分析點(diǎn)集重疊百分比和配準(zhǔn)誤差之間的關(guān)系，指出通過建立新目標(biāo)函數(shù)來處理具有缺失數(shù)據(jù)點(diǎn)集配準(zhǔn)問題的可行性。 4 所示： 圖 錯(cuò)誤 !文檔中沒有指定樣式的文字。但是如果重疊百分比 r取值過大， 又 會(huì) 產(chǎn)生 在匹配過程中引入 大量不能作 對(duì)應(yīng) 的 點(diǎn) 的問題 ，而這些異常 點(diǎn)會(huì)提供錯(cuò)誤的信息， 錯(cuò)誤引導(dǎo)配準(zhǔn)的進(jìn)行方向 ， 其結(jié)果是 配準(zhǔn)不魯棒。 換而言之，對(duì)于具有缺失數(shù)據(jù)的點(diǎn)集配準(zhǔn)問題，不僅要確定兩個(gè)點(diǎn)集的對(duì)應(yīng)關(guān)系和全局的幾何變換，而且還要確定點(diǎn)集的重疊百分比 。它 主要表現(xiàn)為兩個(gè)點(diǎn)集之間 僅有一部分點(diǎn)集是能夠?qū)?yīng)起來的，而其他部分則完全相異 ， 并且 這些非對(duì)應(yīng)點(diǎn)存在方式跟外界環(huán)境和 對(duì)象物體 形狀 本身有關(guān)，因而 無法 精確 估計(jì) 非對(duì)應(yīng)點(diǎn)的 分布和幾何位置。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， 化簡(jiǎn)目標(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 實(shí)驗(yàn)結(jié)果 圖 a1 模型圖像 圖 a2 待配準(zhǔn)圖像 圖 a3 配準(zhǔn)結(jié)果 圖 b1 模型圖像 圖 b2 待配準(zhǔn)圖像 圖 b3 配準(zhǔn)結(jié)果 上面所示的實(shí)驗(yàn)結(jié)果圖中，因?yàn)闉榱撕?jiǎn)單起見均采用的是黑白圖，而且僅僅是提取了圖片中圖像物體的外部輪廓 線條特征來作配準(zhǔn)的標(biāo)準(zhǔn)。 很多研究和實(shí)驗(yàn)結(jié)果 一致表明 ， kd 樹適合于高維點(diǎn)集的點(diǎn)搜索，而基于 Delaunay 三角化的最近點(diǎn)搜索算法 則 更適 合于低維點(diǎn)集的點(diǎn)搜索。在經(jīng)典的 ICP算法中，相似性度量 J 采用了上述闡述到的最小平方（ Least Square， LS）距離。相似性度量函數(shù)目前已有多種，它 一般都是某個(gè)距離的函數(shù) 。本章首先給出了點(diǎn)集配準(zhǔn)的概念，然后在此概念上闡述了剛體變換和相似性度量，接著給出了剛體配準(zhǔn)的數(shù)學(xué)模型和流程框圖。因此， 本文對(duì) 點(diǎn)集 剛體配準(zhǔn)問題 ，進(jìn)一步點(diǎn)集部分剛體配準(zhǔn)問題，都 進(jìn)行了 概念和算法原理方面的詳盡闡述 ，分析 了 點(diǎn)集剛體配準(zhǔn) 普遍存在存在的缺陷和 難點(diǎn) 。er將對(duì)應(yīng)點(diǎn)集的距離看做一種概率分布，計(jì)算其標(biāo)準(zhǔn)方差，迭代過程中排除距離大于該方差的點(diǎn)對(duì)。 這 其中 的例子數(shù)不勝數(shù)，例如， Fitzgibbon 采用LevenbergMarquardt算法 加快 ICP的收斂速度； Jost和 Hugli用了一種由粗到精的搜索策略加快 了 ICP算法 收斂 速度 ； Ezra等分析了 ICP算法的收斂速度 問題， 證明 了 剛體配準(zhǔn) 的 時(shí)間復(fù)雜度與點(diǎn)集 中點(diǎn)的 個(gè)數(shù) 間的 相關(guān) 性 ；更 多學(xué)者研究 了 ICP算法局部收斂性， 并傾心于擴(kuò)大算法收斂域 的問題 。 國(guó)內(nèi)外研究現(xiàn)狀 點(diǎn)集 配準(zhǔn)問題 最初產(chǎn)生于 計(jì)算機(jī)視覺， 計(jì)算機(jī)圖形學(xué) 和圖像處理領(lǐng)域。相似度測(cè)量 特征空間指的是從圖像中提取出來的用來匹