【正文】 缺失的情況。 然而宏觀的想法是很簡(jiǎn)單的，但具體到 如何有效排除點(diǎn)集中的非對(duì)應(yīng)點(diǎn) 集部分則是一個(gè)較為復(fù)雜難辦的問(wèn)題。 這就是本文所涉及的剛體點(diǎn)集部分配準(zhǔn)問(wèn)題。 其中紅色表示模型點(diǎn)集，藍(lán)色表示形狀點(diǎn)集，綠色和天 藍(lán)色分別表示兩個(gè)點(diǎn)集中多余或者缺失的部分。本章 即后面的地圖拼接僅涉及到 第一類點(diǎn)集 部分 配準(zhǔn)問(wèn)題， 所以對(duì)于第二類 點(diǎn)集 部分 配準(zhǔn) 在本文 中將不會(huì)再被提及和探討。所謂形狀噪聲， 它是指圖像點(diǎn)集位置 與真實(shí)精確的位置相異但差別卻很小，僅僅是一個(gè)小小的擾動(dòng)而已 ，而 且 噪聲往往服從某些概率分布， 如高斯分布。它 主要表現(xiàn)為兩個(gè)點(diǎn)集之間 僅有一部分點(diǎn)集是能夠?qū)?yīng)起來(lái)的，而其他部分則完全相異 ， 并且 這些非對(duì)應(yīng)點(diǎn)存在方式跟外界環(huán)境和 對(duì)象物體 形狀 本身有關(guān)，因而 無(wú)法 精確 估計(jì) 非對(duì)應(yīng)點(diǎn)的 分布和幾何位置。 如果按照 點(diǎn)集對(duì)應(yīng)關(guān)系 來(lái)分類，則通常認(rèn)為 點(diǎn)集部分 配準(zhǔn)問(wèn)題可以分為兩大類：一類是具有 點(diǎn)集中部分 數(shù)據(jù) 丟失或點(diǎn)集中含有大量 離群點(diǎn)的點(diǎn)集配準(zhǔn)，而另一類是具有形狀噪聲的點(diǎn)集配準(zhǔn)問(wèn)題。然而在 現(xiàn)實(shí)環(huán)境中圖像配準(zhǔn)問(wèn)題中，由于 攝 相機(jī)拍攝角度 ， 障礙物遮擋， 傳感器噪聲以及圖像處理過(guò)程噪聲等因素的影響， 因而存在這樣一種情況： 點(diǎn)集 P 中 僅有部分點(diǎn)能夠在點(diǎn)集 M 找到相對(duì)應(yīng)的點(diǎn) ， 即 兩個(gè)點(diǎn) 集之間僅存在部分對(duì)應(yīng)的關(guān)系 ，而且很可能 P 中能找到對(duì)應(yīng)點(diǎn)的點(diǎn)集是非常小的一部分。在內(nèi)容安排方面，本章首先給出 點(diǎn)集剛體 部分配準(zhǔn) 問(wèn)題 的 描述及解決方案，接著 提出本文的第一個(gè) 創(chuàng)新點(diǎn)， 一種能夠自動(dòng)計(jì)算點(diǎn)集重疊百分比的快速魯棒的剛體配準(zhǔn)算法 ， 然后詳盡 闡述 算法 的基本 思想 原理和算法解決問(wèn)題的步驟流程， 最后 就是給出 實(shí)驗(yàn)結(jié)果 ，并根據(jù)結(jié)果一些數(shù)學(xué)品質(zhì)考察此算法的性能。 所以本章針對(duì)這一問(wèn)題，會(huì)在傳統(tǒng) ICP 算法基礎(chǔ)上，將引入重疊百分比的概念，然后建立關(guān)于空間變換的新目標(biāo)函數(shù)，因而與前面 ICP 算法不同的是在 配準(zhǔn)過(guò)程中 ，將 同時(shí)更新 三個(gè)未知量，即 點(diǎn)集重疊百分比 ， 空間變換 和點(diǎn)間對(duì)應(yīng)關(guān)系。 3 基于迭代最近點(diǎn)的部分配準(zhǔn)算法 前面 第二章 描述了 ICP 剛體配準(zhǔn) 問(wèn)題并建立了它的數(shù)學(xué) 模型 ， 且給出 求解 ICP 剛體配準(zhǔn)問(wèn)題的 具體 方法和原理 ， 接下來(lái) 本章 將 在 上面的 基礎(chǔ)上進(jìn)一步研究基于 ICP（即迭代最近點(diǎn)） 的剛體 部分 配準(zhǔn)問(wèn)題。 本章小結(jié) 本章 首先提出了圖像點(diǎn)集配準(zhǔn)問(wèn)題的概念，接著在數(shù)學(xué)上 建立點(diǎn)集配準(zhǔn) 的 模型 ，隨后又闡述了 在眾多的剛體配準(zhǔn)研究 中最為矚目的由 Besl 和 Mckay 提出的 ICP 算法 ，并且詳盡地論 述了算法運(yùn)作流程和算法每步中問(wèn)題的解決方法。在配準(zhǔn)結(jié)果圖中，需要說(shuō)明的是 紅色 線是待配準(zhǔn)圖像的輪廓， 綠色 線 是 模型圖像的輪廓，程序結(jié)果并沒有很好的展示配準(zhǔ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)單起見均采用的是黑白圖，而且僅僅是提取了圖片中圖像物體的外部輪廓 線條特征來(lái)作配準(zhǔn)的標(biāo)準(zhǔn)。 設(shè) 39。 2） SVD 方法 求解 剛體變換 SVD 方法 相當(dāng)比較 簡(jiǎn)單，而且具有較好的擴(kuò)展性，所以 本文采用 奇異值分解 Singular Value Deposition 的方法解決第二步中剛體變換求解。對(duì)于 ICP 算法中式的求解，首先將模型點(diǎn)集 M進(jìn)行 Delaunay 三角剖分，然后采用三角劃分搜索策略找到形狀點(diǎn)集 S 在模型點(diǎn)集 M 中的對(duì)應(yīng)點(diǎn)。局部變換法和 Watson 算法是離散點(diǎn)集 Delaunay 三角剖分的常用算法，算法過(guò)程中逐點(diǎn)添加、局部?jī)?yōu)化是三角網(wǎng)格生成速度的重要影響因素。 Delaunay 剖分必須滿足兩個(gè)基本準(zhǔn)則，其一是 空?qǐng)A特性 ，即在 Delaunay 三角形網(wǎng)中任一 個(gè) 三角形的外接圓范圍內(nèi)不會(huì)有其它點(diǎn)存在。也就是說(shuō)，在二維情況下得到的是三角形網(wǎng)格，在三維情況下得到的是四面體網(wǎng)格。對(duì)第二步求解，有 SVD(奇異值分解， Singular Value Deposition)、四元組、正交矩陣、雙四元祖方法，本 文 采用的是 SVD 1） Delaunay 三角化 求解 點(diǎn)集 對(duì)應(yīng)關(guān)系 如何把一個(gè)散點(diǎn)集合剖分成不均勻的三角 形網(wǎng)格，這就是散點(diǎn)集的三角剖分問(wèn)題 。 很多研究和實(shí)驗(yàn)結(jié)果 一致表明 ， kd 樹適合于高維點(diǎn)集的點(diǎn)搜索，而基于 Delaunay 三角化的最近點(diǎn)搜索算法 則 更適 合于低維點(diǎn)集的點(diǎn)搜索。當(dāng) ICP 算法 循環(huán) 退出后， 那么返回 得到最終的剛體變換 和點(diǎn)集對(duì)應(yīng)關(guān)系，通過(guò)這兩個(gè)量我們就可以把兩幅剛性圖像配準(zhǔn)了。當(dāng)然實(shí)際配準(zhǔn)中，我們很大的可能性是不可能使配準(zhǔn)誤差 k? 達(dá)到它理論上的最小值，因?yàn)檫@可能需要難以忍受的等待時(shí)間或者根本就不存在這樣一個(gè)最小值。這就是所謂的兩個(gè)點(diǎn)集 間的均方誤差（ Mean Square Error，MSE） ，數(shù)學(xué)表達(dá)式為 2( ) 21 || ( ) ||skNk k i k c ii? ?? ? ?? R s t m。然后 ICP算法 正如它的名字一樣 通過(guò)反復(fù)迭代 ，不斷改進(jìn)空間變換和對(duì)應(yīng)關(guān)系最終以求達(dá)到最優(yōu)的配準(zhǔn)效果。 1 ICP 算法流程 從 圖 錯(cuò)誤 !文檔中沒有指定樣式的文字。 ICP配準(zhǔn)算法通過(guò)交替迭代的方式來(lái)分別求解這兩個(gè)未知變量，算法流程如 圖 錯(cuò)誤 !文檔中沒有指定樣式的文字。 Np 形狀點(diǎn)集中點(diǎn)的個(gè)數(shù)。在經(jīng)典的 ICP算法中，相似性度量 J 采用了上述闡述到的最小平方（ Least Square， LS）距離。 ICP 算法 ICP (Iterative Closest Point) 算法最早是由 Besl 和 McKay于 1992 年提出來(lái)的一個(gè)配準(zhǔn)算法，它用于解決兩個(gè)點(diǎn)集之間的剛體配準(zhǔn)問(wèn)題。 1 點(diǎn)集配 準(zhǔn)示意圖 給定 R 空間中的兩個(gè)點(diǎn)集： S形狀點(diǎn)集 M模型點(diǎn)集 故配準(zhǔn)問(wèn)題實(shí)際上是解決上述兩個(gè)未知量，即最優(yōu)的空間變換 T 和確定形狀點(diǎn)集到模型點(diǎn)集的對(duì)應(yīng)關(guān)系 C。對(duì)于兩組點(diǎn)集，進(jìn)行配準(zhǔn)的 LS準(zhǔn)則函數(shù)為： 綜上述，剛體配準(zhǔn)是圖像配準(zhǔn)中的一種，它最終目的是通過(guò)尋找一個(gè)空間變換 T，即 R和 t,使得經(jīng)過(guò)該空間變換后兩幅圖像間相似性度量 J 最小，這也就達(dá)到了兩幅圖像中的點(diǎn) 在空間幾何上的一致。 點(diǎn)到點(diǎn)的距離又稱為 2 范數(shù)距離，它表示 Rm空間中兩個(gè)點(diǎn) x{x1 ,x2 ,..,xi ,... } 和y{ y1 ,y2 ,..,yi ,... }之間的真實(shí)距離： 由于 Euclidean計(jì)算 比較簡(jiǎn)單，因而它是最為常見和常用的距離，大多數(shù)點(diǎn)集配準(zhǔn)問(wèn)題都采用它來(lái)定義空間中點(diǎn)對(duì)的距離。所以本文中所涉及的變換 T 僅限于旋轉(zhuǎn)和平移，而不包括其他變換，如相似變換、伸縮變換、仿射變換、投影變換和彈性變換等。在任何力的作用下，體積和形狀都不發(fā)生改變的物體叫做剛體。由于本文僅涉及 Euclidean距離，本文后面僅簡(jiǎn)要闡述了一下 Euclieadn距離度量。相似性度量函數(shù)目前已有多種，它 一般都是某個(gè)距離的函數(shù) 。所謂點(diǎn)集配準(zhǔn)就是尋求兩個(gè)圖像點(diǎn)集之間的一種幾何變換，通過(guò)變換后能夠使得一個(gè)圖像點(diǎn)集中的每個(gè)點(diǎn)與 另一個(gè)圖像點(diǎn)集中的每個(gè)對(duì)應(yīng)點(diǎn)能夠達(dá)到空間上最佳的匹配。談到何謂剛體配準(zhǔn)，首先我們要從點(diǎn)集配準(zhǔn)的概念開始，因?yàn)辄c(diǎn)集配準(zhǔn)是圖像配準(zhǔn)的一項(xiàng)關(guān)鍵技術(shù)，它是從計(jì)算機(jī)視覺、模式識(shí)別和圖像處理的各個(gè)領(lǐng)域中抽象出來(lái)的一類重要的基礎(chǔ)問(wèn)題。在該章中對(duì)全文進(jìn)行總結(jié)，并 對(duì)下一步的工作進(jìn)行展望。 第四章， 基于迭代最近點(diǎn)的地圖拼接方法。闡述過(guò)程中并給出了該算法的簡(jiǎn)要流程和具體步驟，以及每一步中要求解的數(shù)學(xué)表達(dá)式，更深一步的本文還對(duì)算法進(jìn)行了理論上層次較高的算法分析。 本章首先提出了具有部分?jǐn)?shù)據(jù)丟失的點(diǎn)集部分配準(zhǔn)問(wèn)題，然后建立基本的數(shù)學(xué)求解模型。本章最后還展示了應(yīng)用剛體迭代最近點(diǎn)算法，在 matlab 上配準(zhǔn)兩幅簡(jiǎn)單線條的黑白圖片的實(shí)驗(yàn)結(jié)果，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了初略分析，對(duì)結(jié)果中的不足提出疑問(wèn)。本章首先給出了點(diǎn)集配準(zhǔn)的概念，然后在此概念上闡述了剛體變換和相似性度量，接著給出了剛體配準(zhǔn)的數(shù)學(xué)模型和流程框圖。 本章首先介紹圖像點(diǎn)集配準(zhǔn)的研究背景和意義，然后對(duì)點(diǎn)集配準(zhǔn)問(wèn)題進(jìn)行描述并且分析其難點(diǎn)，接著介紹點(diǎn)集 配準(zhǔn)的研究現(xiàn)狀，最后給出本文的研究?jī)?nèi)容和組織結(jié)構(gòu)。而上面研究的剛體部分迭代最盡點(diǎn)算法剛好可以應(yīng)用這個(gè)問(wèn)題中來(lái)，于是本文中應(yīng)用了這個(gè)算法，然后在 matlab上寫程序?qū)崿F(xiàn)算法，模擬測(cè)試了兩張地圖的拼接過(guò)程和最終結(jié)果。由于攝像機(jī)在不同時(shí)刻，不同位置 角度進(jìn)行攝像時(shí)，大多數(shù)情況下得到的地圖圖像將是不同的，然所謂的不同也不是完全的不同，它們可能存在某部分區(qū)域相同的情況。實(shí)驗(yàn)結(jié)果表明， 此 算法是比傳統(tǒng)的ICP 和 目前 國(guó)內(nèi)最先進(jìn)的算法更為可靠和高效。 在此算法中， 通過(guò) 每步不斷求解剛體變換，對(duì)應(yīng)關(guān)系， 重疊百分比，最終解決剛體部分配準(zhǔn)問(wèn)題。為了解決這個(gè)問(wèn)題，針對(duì)部分區(qū)域能夠重疊情況，我們提出了一個(gè)新的目標(biāo)函數(shù)，函數(shù)式中引入了重疊百分比 r。 本文的具體研究?jī)?nèi)容如下 ： 1)研究?jī)H有部分區(qū)域重疊的剛性圖像的配準(zhǔn)問(wèn)題，提出一種快速魯棒的剛體配準(zhǔn)算法。因此， 本文對(duì) 點(diǎn)集 剛體配準(zhǔn)問(wèn)題 ，進(jìn)一步點(diǎn)集部分剛體配準(zhǔn)問(wèn)題，都 進(jìn)行了 概念和算法原理方面的詳盡闡述 ，分析 了 點(diǎn)集剛體配準(zhǔn) 普遍存在存在的缺陷和 難點(diǎn) 。這些算法在實(shí)際問(wèn)題解決中往往會(huì)出現(xiàn)配準(zhǔn)精度不高，效率低下等缺點(diǎn)，簡(jiǎn)而言之結(jié)果并不盡如人意 。盡管這些方法能夠一定程度上提高具有異常點(diǎn)的點(diǎn)集配準(zhǔn)的魯棒性，但是往往需要正確的初始化條件，否則在出現(xiàn)大量缺失數(shù)據(jù)時(shí)候，很容易陷入局部極值點(diǎn)，從而導(dǎo)致錯(cuò)誤的 配準(zhǔn) 結(jié)果 。 Chen提出DARCES方法，該方法通過(guò)自動(dòng)選取控制點(diǎn)的方式完成粗匹配，然后進(jìn)一步細(xì)化，完成精匹配。該類方法的缺點(diǎn)在于閾值或距離度量不好確定，配準(zhǔn)算法往往受到點(diǎn)集形狀的影響，導(dǎo)致收斂性不 好。Dalley通過(guò)計(jì)算 Schultz距離來(lái)設(shè)置閾值大小，排除點(diǎn)集中的噪聲點(diǎn)。 3） 閾值度量方法 針對(duì)提高 ICP算法魯棒性這一問(wèn)題，很多學(xué)者采用閾值度量方法在迭代過(guò)程中排除異常點(diǎn)的干擾，從而提高點(diǎn)集匹配的精度。 Bjom Jensen在 ICP算法中引入概率距離矩陣，該距離矩陣同時(shí)考慮到傳感器噪音和待匹配目標(biāo)位置的不確定性，從而可以有效排除 異常點(diǎn)。er將對(duì)應(yīng)點(diǎn)集的距離看做一種概率分布，計(jì)算其標(biāo)準(zhǔn)方差，迭代過(guò)程中排除距離大于該方差的點(diǎn)對(duì)。 2） 概率 方法 通過(guò)建立概率模型來(lái)約束配準(zhǔn)過(guò)程，進(jìn)而提高算法的魯棒性也是一類常見的方法。為了進(jìn)一步改進(jìn)此算法，Yonghuai Liu又將剛體移動(dòng)的幾何規(guī)律與點(diǎn)集最鄰近約束條件相結(jié)合，通過(guò)選擇正確的匹配點(diǎn)對(duì)， 再次提高 ICP算法的精度和魯棒性。 Rusinkiewicz和 ， 保證兩個(gè)配準(zhǔn)點(diǎn)集之間平移誤差最小，進(jìn)一步提高算法的精度?，F(xiàn)在對(duì)部分配準(zhǔn)問(wèn)題的解決方法主要有： 1） 幾何 方法 所謂幾何方法，是指采用幾何約束 條件來(lái)排除點(diǎn)集配準(zhǔn)中的噪聲點(diǎn)和大量無(wú)信息點(diǎn)對(duì)的方法。王小睿等提出并實(shí)現(xiàn)了一種自動(dòng)圖像配準(zhǔn)算法，用于圖像的高精度配準(zhǔn)，但實(shí)際上它是一種使用互相關(guān)函數(shù)作為相似性度量的半自動(dòng)圖像配準(zhǔn)算法；熊興華等提出了將遺傳算法和最小二乘算法結(jié)合用于圖像的子像素級(jí)配準(zhǔn) 算法 在部分對(duì)應(yīng)點(diǎn)集 配準(zhǔn)問(wèn)題 被提出后很長(zhǎng)一段時(shí)間內(nèi) ，如何提高算法的精度 成為了廣大研究者共同以追尋的目標(biāo) ， 由此而產(chǎn)生的各種優(yōu)秀的部分配準(zhǔn)算法大多數(shù) 都是以 經(jīng)典的 ICP算法為基礎(chǔ)， 然后 通過(guò) 引入現(xiàn)代科學(xué)的 優(yōu)化策略來(lái) 實(shí)現(xiàn)的 。李智等提出了基于輪廓相似性度量方式的圖像配準(zhǔn)方法，它適用于輪廓特征比較豐富的圖像配準(zhǔn)。 相對(duì)于全局點(diǎn)集的 配準(zhǔn)研究 的 比較成熟， 解決方法多且較簡(jiǎn)單，相反 ，部分對(duì)應(yīng)點(diǎn)集的配準(zhǔn)問(wèn)題還是一個(gè)難點(diǎn) 熱點(diǎn)問(wèn)題，因此也是本文研究的重點(diǎn) 。 這 其中 的例子數(shù)不勝數(shù)，例如， Fitzgibbon 采用LevenbergMarquardt算法 加快 ICP的收斂速度； Jost和 Hugli用了一種由粗到精的搜索策略加快 了 ICP算法 收斂 速度 ； Ezra等分析了 ICP算法的收斂速度 問(wèn)題， 證明 了 剛體配準(zhǔn) 的 時(shí)間復(fù)雜度與點(diǎn)集 中點(diǎn)的 個(gè)數(shù) 間的 相關(guān) 性 ；更 多學(xué)者研究 了 ICP算法局部收斂性，