基于迭代近點算法的地圖拼接方法研究

基于迭代近點算法的地圖拼接基于迭代最近點算法的地圖拼接方法研究畢業(yè)設計（論文）原創(chuàng)性聲明和使用授權說明原創(chuàng)性聲明而使用過的材料。對本研究提供過幫助和做出過貢獻的個人或集體，使用授權說明本人完全了解大學關于收集、保存、使用畢業(yè)設計（論本學位論文作者完全了解學校有關保留、使用學位論文的規(guī)定，同意學校保留并向國家有關部門或機構送交論文的復印件和電子版，允許論文被查閱和借閱。本人授權大學可以將本學位2、學生掌握專業(yè)知識、技能的扎實程度4、研究方法的科學性；技術線路的可行性；設計方案的合理性二、論文（設計）質量三、論文（設計）水平1、論文（設計）的理論意義或對解決實際問題的指導意義年二、論文（設計）水平1、論文（設計）的理論意義或對解決實際問題的指導意義教研室（或答辯小組）及教學系意見2、對答辯問題的反應、理解、表達情況二、論文（設計）質量）？三、論文（設計）水平1、論文（設計）的理論意義或對解決實際問題的指導意義：（2剛體迭代最近點算法2.2迭代最近點算法2.3實驗結果與分析2.4本章小結3基于迭代最近點的部分配準算法3.1剛體部分配準問題3.2部分對應的迭代最近點算法3.3實驗結果與分析3.4本章小結4基于迭代最近點的地圖拼接方法4.1地圖拼接問題4.3實驗結果與分析5結論與展望二十世紀以來，圖像配準已逐漸成為圖像處因此圖像點集配準是一項基礎且非常重要的研1.1研究背景和意義所謂圖像配準就是將不同傳感器不同時間、配就是在一幅比較大的圖像中搜尋與目標圖像法。目前，在最為傳統(tǒng)的ICP算法的基礎上已經發(fā)展出了許多處理各種不同種類數據和問題的像之間具有較為明顯的錯位。為了配準這類圖像，可以采用空域的方法來去除這些差別.域中產生細微差別，例如透視變形.或者其他景物的變化而引起的.第二類和第三類圖像之間差別并不是能夠直接特征空間指的是從圖像中提取出來的用來匹度測量則決定了每一個配準測試中的相關特性.間以及搜索策略等的選擇都會影響到最后配準的各種各樣的配準方法的特點以及其之間的關在較為簡單二維圖像配準過程中，圖像特征算法策略來計算這些幾何特征（通常是兩個點問題歸根到底可歸結到二維點集配準這個更為將多個深度圖像數據配準后建立三維的幾何模型并進行后期處理已經成為當前一由上，圖像配準技術在二維或者三維圖像處圖像配準的應用領域概括起來主要有如下4個方CT,MRI,PET圖像結構信息融合，數字剪輯血管（3）模式識別：目標物運動跟蹤，序列圖像圖像配準技術在很多領域都有著廣泛的應1.2國內外研究現狀點集配準問題最初產生于計算機視覺，計算配準問題則是其他非剛體配準問題研究的基礎圖像點集剛體配準技術最早出現在上世紀70終科學家們在潘興2式中程導彈及戰(zhàn)斧式巡航導導彈命中率上至高的一個飛躍。進入八十年代研究深入到了更為廣大的領域，如遙感圖像處而更為抽象統(tǒng)一的圖像點集配準技術理論并未計算互相關相似度量進行圖像檢測技算的圖像的互相關技術進行了全面的研究；M.Svedlow等對圖像配準的相似性度量和預處理方法進行了動態(tài)程序設計方法用于幾何畸變較大的圖像配在二十世紀八十年代初期，當時圖像配準問題的研究方向主要為最基本的全局剛體配準算集特征而直接進行配準的圖像配準方法被廣泛一種不需要提取圖像特征就可以完成三維曲線復雜的曲面上圖像（如地形數據或者人臉數據直到二十世紀九十年代初，圖像配準領域中大名鼎鼎的剛體迭代最近點算，英文Iterative它理所當然的成為了眾多領域為人所熟知的圖大量學者從收斂速度和收斂性方面對ICP算法對更為復雜現實情景中圖像配準的變種ICP算法被提出。這其中的例子數不勝數，例如，Fitzgibbon采用Levenberg-Marquardt算法加快析了ICP算法的收斂速度問題，證明了剛體配準部分對應點集的配準問題還是一個難點熱點問相對國外，在國內圖像配準技術起步相對較一種將遺傳算法（GeneticAlgorithm,簡稱GA）但實際上它是一種使用互相關函數作為相似性遺傳算法和最小二乘算法結合用于圖像的子像在部分對應點集配準問題被提出后很長一段分配準算法大多數都是以經典的ICP算法為基礎，然后通過引入現代科學的優(yōu)化策略來實現聲干擾下產生了較大量的離群點，不穩(wěn)定幾何所謂幾何方法，是指采用幾何約束條件來排除點集配準中的噪聲點和大量無信息點對的方性的點集提取方法，從而提高ICP算法的幾何穩(wěn)YonghuaiLiu通過分析剛體移動的特性，引入幾何約束條件來去除ICP算法中錯誤的匹配剛體移動的幾何規(guī)律與點集最鄰近約束條件相結合，通過選擇正確的匹配點對，再次提CP通過建立概率模型來約束配準過程，進而提高算法的魯棒性也是一類常見的方法。Zin?er準方差，迭代過程中排除距離大于該方差的點HaitaoZhang通過提取深度圖像信息，運用矩陣同時考慮到傳感器噪音和待匹配目標位置率的方法配準含形狀噪聲的點集具有較強的魯采用閾值度量方法在迭代過程中排除異常點的干擾，從而提高點集匹配的精度。EmanueleTrucco在ICP算法中引入線性回歸的和中值最另外一些學者采用由粗到精的策略來提高缺匹配，然后進一步細化，完成精匹配。在上面介紹到的所有用于解決點集剛體部分1.3本文研究內容及組織結構點集剛體配準作為圖像配準的一項基礎而關百分比為基礎的剛體部分配準算法應用到了二2）給出基于迭代最近點的部分配準算法在地體部分迭代最盡點算法剛好可以應用這個問題像點集配準的研究背景和意義，然后對點集配準問題進行描述并且分析其難點，接著介紹點集配準的研究現狀，最本章首先給出了點集配準的概念，然后在此概念上闡述了剛體變換和相似性度量，接著給出了剛體配準的數學模型和流程框圖。在此基礎上，本章詳細的闡最近點算法，并給出了該算法流程和每進行了細微詳盡的分析。本章最后還展示了應用剛體迭代最近點算法，在matlab上配準兩幅簡單線條的黑白圖片的實驗結果，并對實驗結果進行了初配準算法。本章首先提出了具有部分數據丟失的點集部分配準問題，然后建立本章詳細的闡述了一種采用重疊百分比決點集部分配準問題。闡述過程中并給出了該算法的簡要流程和具體步驟，以及每一步中要求解的數學表達式，更深一步的本文還對算法進行了理論上層次較高的算法分析。最后實驗結果和分析是在二維剛體情景中進行的，對不同圖像情景在配準算法參數和循環(huán)次數已經配準時間上進行了列表展示和分析比對全文進行總結，并對下一步的工作進2剛體迭代最近點算法剛體配準是圖像配準問題中一類最為基礎和剛體配準問題的理解在本文后面的工作中至關處理的各個領域中抽象出來的一類重要的基礎個圖像點集中的每個點與另一個圖像點集中的就是要確定如何來度量或者說Euclidean距離，本文后面僅簡要闡述了一下給定Rm維空間中的形狀點集S和模型點集M，假設存在任意兩點xS和yM，那么剛體變換的數點到點的距離又稱為2范數距離，它表示Rmii來定義空間中點對的距離。以點到點的S--形狀點集M--模型點集優(yōu)的空間變換T和確定形狀點集到模型點集的2.2迭代最近點算法算法最早是由Besl和McKay于1992年提出來的模型點集中的點能夠在Euclidean歐式距離空間采用了上述闡述到的最小平方（LeastSquare，2R,t,cic(i)TR剛體配準問題實際上是求使?jié)M足上式的R，t和從圖2-2可以看出，經典的ICP算法首先由人值要求應當粗略正確。然后ICP算法正如它的名關系最終以求達到最優(yōu)的配準效果。那ICP算法是如何改進每步迭代中的變換量和對應量的形狀點集和模型點集間每個點的對應關系2k3）更新第k步的變換R和t：*t止迭代而退出呢？這就涉及到如何判定圖像點式是總體上形狀點集中點和模型點集中對應點kk可能性是不可能使配準誤差ε達到它理論上的最取均方誤差達到設定范圍下限和迭代步驟達到代。當ICP算法循環(huán)退出后，那么返回得到最2.2.2算法求解法則更適合于低維點集的點搜索。鑒于簡單起見，本文采用的是Delaunay三角化。對第二步求解，有SVD(奇異值分解，SingularValue如何把一個散點集合剖分成不均勻的三角形維)空間中任意分布的散亂點用直線段連接起角形(四面體)集，每個三角形(四面體)的頂點即認的具有最好幾何拓撲性質的剖分就是符合Delaunay滿足兩個基本準則，其一是空圓特性，即在性，即在散點集可能形成的三角剖分中，大。局部變換法和Watson算法是離散點集kkM進行略找到形狀點集S在模型點集M中的對應點。該搜索策略大幅度提高了點集對應關系求解的速定理（1給定任意兩個m維對應點集{q}N和{n}NΣn-1Σiii=1NiNikkNc(i)NiiiNiic(i)Nc(i)iiiiii2.2.4實驗結果nTRqiii=1圖a-1模型圖像a-1模型圖像圖b-1模型圖像圖b-2待配準圖像圖上面所示的實驗結果圖中，因為為了簡單起見均采用的是黑白圖，而且僅僅是提取了圖片中圖像物體的外部輪廓線條特征來作配準的標準。其中模型圖像和待配準圖像之間僅僅是一個旋轉和平移的效果，并涉及其它復雜的圖像變換，這也正是剛體變換所需要的前提。在配準結果圖中，需要說明的是紅色線是待配2.4本章小結本章首先提出了圖像點集配準問題的概念，了在眾多的剛體配準研究中最為矚目的由Besl和Mckay提出的ICP算法，并且詳盡地論述了3基于迭代最近點的部分配準算法了它的數學模型，且給出求解ICP剛體配準問在假設兩個待配準點集中所有點都是有其相對器噪聲等因素所造成的點集部分數據丟失或存相對傳統(tǒng)的ICP算法新增了重疊百分比這個變3.1剛體部分配準問題在模型點集M中找到與之相對應的點，即假定了點集P中僅有部分點能夠在點集M找到相對應的且很可能P中能找到對應點的點集是非常小的一部分。在這種情況下，傳統(tǒng)的ICP算法就無法如果按照點集對應關系來分類，則通常認為點集中部分數據丟失或點集中含有大量離群點不同，或者兩次采集圖像時障礙物遮擋情況不一，再或者是采集設備自身缺陷等原因而造成且這些非對應點存在方式跟外界環(huán)境和對象物于外界環(huán)境的干擾和采集設備本身的限制產生部分配準在本文中將不會再被提及和探討。綠色和天藍色分別表示兩個點集中多余或者缺形狀點集中的綠色部分在模型點集中無法找到如何解決上述具有部分數據缺失的點集配準問題呢？大家都會想到的很簡單的考慮是先要但具體到如何有效排除點集中的非對應點集部文緒論中范范而談了幾種處理部分對應點集的而我們面對的情況是未知待配準點集圖像形狀和未知噪聲概率分布函數這一更為嚴峻的情景，3.1.2模型建立r如何確定兩個點集之間重疊百分比是建立具r有部分數據缺失的點集剛體部分配準數學模型rrrrrr點集中能夠建立對應關系的點個數此時極少故r優(yōu)的值，所謂最優(yōu)的重疊百分比，是指在該百r中那部分能夠建立對應的點集能夠最佳的與模型點集中相對應的部分點集能夠在幾何空間上r缺失數據點集配準誤差與重疊百分比關系缺失數據點集配準誤差與重疊百分比關系20864200.550.60.650.70.750.80.850.90.951重疊百分比差0.5配準算法相比較，因為傳統(tǒng)ICP配準算法假設了形狀點集和模型點集間具有完該百分比?能盡可能多地包括兩個點集中能夠相2）重疊百分比很大。點集之間能夠作對應點個r用的點集信息很大。但是如果重疊百分比取值r應的點的問題，而這些異常點會提供錯誤的信綜上述，最優(yōu)的重疊百分比r應該是兩矛盾r使得點集配準在誤差取得極小值的情況下又盡也達到最佳，而不是前面分析的在誤差突變時設表示兩個點集的重疊百分比，r表示形狀點r2λrλic(i)2TRλe[λ,λ],re[0.5,1]rr點集配準均方誤差:2ic(i)2ir懲罰函數:sirλrλMSE(r)MSE(r)最小值點所對應得到的重疊百分比就是要求解864200.50.550.60.650.70.750.80.850.90.951重疊百分比誤差懲罰函數差誤該算法在每步迭代中除了要計算求解點集的對r。算法開始的第一步，假設形狀點集和模型點集是完全重疊的，即令r=1，調控參數λ=λ。然后以后每步迭代中調控參數λ從λ遞減到于第n步的λ,在迭代過程中最ma小x化目標min函數 (r,λ)，計算出該步最優(yōu)的剛體變換R和t，然后賦值傳遞給第n+1步。算法的內循環(huán)迭代流程類似1)根據(k1)步的剛體變換(R,t)，計算點集S和M2)求目標函數(r,λ)2sje{1,2,,N}s的最小值的過程中確定第步kkirmkckλrλ)(i)2Ns{m}NskkSS4)通過求關于子集第k步的空間變換krkrrirmkck(i)2S度量函數的最小化值計算krk2RTR=I,det(R)=1,tseS5）更新R和t:*R*t配準過程中，只有當取值能夠搜索出最優(yōu)λ的裁剪度時，才能計算出準確的剛體變換，這r(r,λ)會隨著λ的減小而增大。配準循環(huán)結束后，算法讓λ從λ開始往遞增方向搜索，因為在穩(wěn)定min狀態(tài)（配準結果正確）下(r,λ)是遞減的，因此第一個使目標函數(r,λ)遞增的λ*就是待求的最優(yōu)參數。該點對應的Ψ(r,λ*)是最優(yōu)的目標函數，而其對應的裁剪度r*和剛體變換也是最優(yōu)的配準結3.3實驗結果分析為了驗證帶重疊百分比的點集部分配準算法配準的實驗誤差采用的是均方根（RootMeanSquare，RMS）誤差度量。本文中所有的代碼百分比的點集部分配準算法對于這類簡單的黑針對具有部分數據缺失這一類點集部分配準問題，本章在傳統(tǒng)經典的ICP算法基礎上，提出了一種在目標函數中引入重疊百分比r和懲罰函數兩個量的作用而產生的一種新ICP變種處理具有缺失數據點集配準問題的可行性。然點集配準實驗進一步驗證了算法的正確性和精5總結與展望題分別進行了描述和提出了一種高效的變種ICP雖然本文對圖像點集配準算法做了一些研究山一角。還有更多的圖像配準問題并沒有涉及1）詳盡闡述了ICP算法的基本思想和原理，這因為本文提出的算法正是基于經典ICP算法的2）提出了用于解決因部分數據丟失情況下剛體ICP算法。該算法目前是最好的用于解決此類配3）將算法成功的應用到地圖拼接中，并獲得的雖然本文剛體配準的一般模型，經典ICP算法和帶重疊百分比的部分點ICP算法進行探討，1）本文提出的目標函數及算法都采用的是基于2）目前，本文提出帶重疊百分比的部分點ICP附：論文翻譯在當被稱為相對姿態(tài)的初始估計是知道的情況型的幾何對準.階段從點的選擇和匹配方面著手以求達到最小出了它們按照正確路徑收斂的速度.inscribedsugaces，我們引入一個新的基于均我們最終提出一種結合了其它變種ICP算法而具有高收斂速度的算法.我們將展示一個能夠在幾十毫秒范圍內配準兩好的.典型是那種一次只能從一個方向掃描物體的掃位置，識別和索引表面特征[Faugeras86，斯圖像”表面簽名[約翰遜97A]，計算主軸掃描全方位定位問題[Bergevin96，斯圖達特96，1.在一幅或兩幅網格圖像中選擇其中部分點4.排斥某些點對，在單獨尋找每對點對或考慮在本文中,我們將著眼于這六類中的每個變種，這種實時ICP算法的可用性可能使大量的新應用在基于模型的跟蹤和三維掃描方面產生。將作為我們基準選擇的算法是實質上是[普莉來源有一個正常的其他網正常。在生產環(huán)境已得到廣泛使用Levoy00]，對含有％；2％.所有我們使用的網格都是簡單視角范圍內的“最近點”和“投影點”變種之間的比較（見曲面的法線計算只是基于四個近鄰范圍內的選擇會影響quantitative，而不是定性的，我“切平面”現場（圖IC由在一個“X”形狀雖然這些場面肯定不涵蓋所有可能的掃描對象例如，數字米開朗基羅項目[Levoy00]涉及表面掃描含有低頻特性（例如，線條流暢雕像分我們使用綜合數據進行比較的動機是使我們知用度量是兩個網格中對應點的實際距離的最小雖然一個單一的運行結果顯然不能被視為一個了典型的捕捉了在各種場景中具有顯著性能差變種，并在我們的測試場景中比較了他們的性我們首先通過檢查點對的選擇對ICP的收斂性始終使用所有可用點[Besl92]。可用點均勻子采樣[TurkS94]。隨機抽樣（每步迭代中選擇不同的點樣本）在使用顏色或強度以幫助配準的變種算法中,選擇具有高強度梯度的點[Weik97]。上述方案中的每個都可以選擇只從一幅網格中選擇點，也可以選擇從兩個網格中選擇源點這一戰(zhàn)略動機為了是觀察某些類型的場景下的程中盡可能是均勻樣品.普通空間采樣是一個用表面特性配準的非常簡統(tǒng)基于特征的方法具有較低的魯棒性[Faugeras86，Stein92,Johnson97a]。的六個部分之中的三個起到作用（一個平面內的兩個translations，一個旋轉）完全（圖6尤其是在迭代階段早期當兩個網格仍我們將研究ICP的下一階段是如何尋找點與點查找從源點出發(fā)朝向具有目標表面的源點法距離度量標準[Benjemaa97]，點到線的距離[Dorai98]，或強度相容性[Weik97]或顏色和法線間角度[Pulli99]的相容性指標已被探），首先，讓我們先來看看對“fract