【正文】 ? ?R t q q n R q n n 最小化目標函數(shù)，即最小化1sN Tiii???n Rq 實驗結(jié)果 圖 a1 模型圖像 圖 a2 待配準圖像 圖 a3 配準結(jié)果 圖 b1 模型圖像 圖 b2 待配準圖像 圖 b3 配準結(jié)果 上面所示的實驗結(jié)果圖中，因為為了簡單起見均采用的是黑白圖，而且僅僅是提取了圖片中圖像物體的外部輪廓 線條特征來作配準的標準。 所以本章針對這一問題，會在傳統(tǒng) ICP 算法基礎(chǔ)上，將引入重疊百分比的概念，然后建立關(guān)于空間變換的新目標函數(shù)，因而與前面 ICP 算法不同的是在 配準過程中 ，將 同時更新 三個未知量，即 點集重疊百分比 ， 空間變換 和點間對應(yīng)關(guān)系。它 主要表現(xiàn)為兩個點集之間 僅有一部分點集是能夠?qū)?yīng)起來的，而其他部分則完全相異 ， 并且 這些非對應(yīng)點存在方式跟外界環(huán)境和 對象物體 形狀 本身有關(guān)，因而 無法 精確 估計 非對應(yīng)點的 分布和幾何位置。 這就是本文所涉及的剛體點集部分配準問題。 換而言之，對于具有缺失數(shù)據(jù)的點集配準問題，不僅要確定兩個點集的對應(yīng)關(guān)系和全局的幾何變換，而且還要確定點集的重疊百分比 。理論和實驗 一致 證明 了 ，最優(yōu)的重疊百分比 r并非 像大家想像的那樣理所當然的 對應(yīng) 具有最小 配準誤差 時的值 ，而是 對應(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ù)據(jù)點集配準誤差與重疊百分比關(guān)系 圖 錯誤 !文檔中沒有指定樣式的文字。但是如果重疊百分比 r取值過大， 又 會 產(chǎn)生 在匹配過程中引入 大量不能作 對應(yīng) 的 點 的問題 ，而這些異常 點會提供錯誤的信息， 錯誤引導(dǎo)配準的進行方向 ， 其結(jié)果是 配準不魯棒。 下面 給出新目標函數(shù)的數(shù)學(xué)表達： 給定 Rm 維 空間中的 形狀點集 S 和 模型點集 M，設(shè) r 表示兩個點集的重疊百分比， rS表 示 形狀點集中與模型點集相對應(yīng)的部分點集。 4 所示： 圖 錯誤 !文檔中沒有指定樣式的文字。 實驗結(jié)果分析 為了 驗證帶重疊百分比的點集部分配準 算法 的魯棒性和收斂性， 本文根據(jù)上面闡述的算法寫了 matlab 程序作了圖像配準仿真實驗 。本章首先分析點集重疊百分比和配準誤差之間的關(guān)系，指出通過建立新目標函數(shù)來處理具有缺失數(shù)據(jù)點集配準問題的可行性。 雖然本文對圖像點集配準算法做了一些研究工作， 但是在整個圖像配準領(lǐng)域上來講僅僅是冰山一角。 因此， 采用不同度量方式 的 圖像 配準算法是今后研究的一個重點。 算法 同樣是一個迭代過程 ， 其中采用 EM估計和手動遞減相結(jié)合的方式更新每步 高斯概率模型的方差 。在本文中，我們假設(shè)一個粗略的初始對齊始終可以得到。 在本文中 ,我們將著眼于這六類中的每個變種，審查它們對 ICP 算法性能的影響。 將作為我們基準選擇的算法是實質(zhì)上是 [普莉 99]，包含有以下特點： 兩個網(wǎng)格點隨機抽樣 匹配選定的每個點在最接近的樣本在 45 度的來源有一個正常的其他網(wǎng)正常。 僅用于幾何形狀配準，而不是顏色或強度。 這是一個困難的場景，對 ICP 來講，大部分變種得不到正確的收斂路線，甚至在初始位置給定相對較小的旋轉(zhuǎn)情況下。 雖然一個單一的運行結(jié)果顯然不能被視為一個算法在所有情況下性能的代表，但我們試圖顯示了典型的捕捉了在各種場景中具有顯著性能差異的結(jié)果。 隨機抽樣（每步迭代中選擇不同的點樣本） [Masuda 96]。 正如我們可以看到的那樣，它們的收斂性能是相似的。 這樣，再 加上噪聲和平面部分圖像失真的事實淹沒了從凹槽采樣點對的效果， accounts for均勻隨機抽樣無法收斂到正確的配準。然從“切平面”場景的結(jié)果看，卻有些不同（圖 3）。 上述方案中的每個都可以選擇只從一幅網(wǎng)格中選擇點，也可以選擇從兩個網(wǎng)格中選擇源點 [戈丁 94]。 所有報出的運行時間為一個在 550 兆赫奔騰 111 Xeon 處理器上的 C++運行時。 雖然這些場面肯定不涵蓋所有可能的掃描對象類，但它們是許多掃描應(yīng)用中的代表。 雖然我們將不會使用的顏色或強度比較變種，但在使用這些數(shù)據(jù)時這是明顯的優(yōu)勢，因為它可以提供幾個幾何特征領(lǐng)域里的必要約束。 點到平面的誤差度量。 這種實時 ICP 算法的可用性可能使大量的新應(yīng)用在基于模型的跟蹤和三維掃描方面產(chǎn)生。 我們可以以算法六個階段作用來歸類這些變種： 1. 在一幅或兩幅網(wǎng)格圖像中選擇其中部分點集。 附：論文翻譯 ICP 算法的高 效變種 西蒙 Rusinkiewicz 馬克 Levoy 斯坦福大學(xué) 摘要 在當被稱為相對姿態(tài)的初始估計是知道的情況下， ICP（迭代最近點）算法被廣泛用于三維模型的幾何對準 . 許多 ICP 算法的變種已經(jīng)被提出，在算法的各個階段從點的選擇和匹配方面著手以求達到最小化策略。由于本文提出的算法并沒有限制其應(yīng)用對象，所以這些算法都具有很好的通用性。但本文作出貢獻總結(jié)起來在于下面三個方面： 1） 詳盡闡述了 ICP算法的基本思想和原理，這對與理解后面本文提出的算法起到鋪墊作用， 因為本文提出的算法正是基于經(jīng)典 ICP算法的變種。最后，本章通過二維點集配準實驗進一步驗證 了 算法的 正確性和精確性 ，實驗結(jié)果顯示在保證配準時間效率的前提下，配準結(jié)果 的效果不隨待配準 點集 及模型點集形狀和 缺失數(shù)據(jù) 位置 的影響。本文中所有的代碼都是用 來完成的 。 然后以后每步迭代中 調(diào)控參數(shù) ? 從 max? 遞減到 min? 。 很明顯可以看出該目標函數(shù)是 一個 上 凸函數(shù)， 而 函數(shù)的最 小值點的橫坐標就是最優(yōu)重疊百分比 r 的取值。如何講呢？ 最優(yōu)的重疊百分 r一方面要使配準誤差相對較小，而另一方面又要盡可能多地利用待配準點集中能夠作 對應(yīng)的點，而這兩方面又是相互矛盾對立的。而對于具有 部分 數(shù)據(jù) 缺失 的點集 部分 配準問題，最優(yōu)空間變換 的求解要復(fù)雜得多，它不像傳統(tǒng) ICP配準算法那樣僅僅取決與一個配準誤差量，它還依賴與重疊百分比 r。在本文 中， 該百分比 r的最優(yōu)值 是由 配準誤差來確定。 然而宏觀的想法是很簡單的，但具體到 如何有效排除點集中的非對應(yīng)點 集部分則是一個較為復(fù)雜難辦的問題。所謂形狀噪聲， 它是指圖像點集位置 與真實精確的位置相異但差別卻很小，僅僅是一個小小的擾動而已 ，而 且 噪聲往往服從某些概率分布， 如高斯分布。在內(nèi)容安排方面，本章首先給出 點集剛體 部分配準 問題 的 描述及解決方案，接著 提出本文的第一個 創(chuàng)新點， 一種能夠自動計算點集重疊百分比的快速魯棒的剛體配準算法 ， 然后詳盡 闡述 算法 的基本 思想 原理和算法解決問題的步驟流程， 最后 就是給出 實驗結(jié)果 ，并根據(jù)結(jié)果一些數(shù)學(xué)品質(zhì)考察此算法的性能。在配準結(jié)果圖中，需要說明的是 紅色 線是待配準圖像的輪廓， 綠色 線 是 模型圖像的輪廓，程序結(jié)果并沒有很好的展示配準后兩者相重疊的輪廓部分。對于 ICP 算法中式的求解，首先將模型點集 M進行 Delaunay 三角剖分，然后采用三角劃分搜索策略找到形狀點集 S 在模型點集 M 中的對應(yīng)點。對第二步求解，有 SVD(奇異值分解， Singular Value Deposition)、四元組、正交矩陣、雙四元祖方法，本 文 采用的是 SVD 1） Delaunay 三角化 求解 點集 對應(yīng)關(guān)系 如何把一個散點集合剖分成不均勻的三角 形網(wǎng)格，這就是散點集的三角剖分問題 。這就是所謂的兩個點集 間的均方誤差（ Mean Square Error，MSE） ，數(shù)學(xué)表達式為 2( ) 21 || ( ) ||skNk k i k c ii? ?? ? ?? R s t m。 Np 形狀點集中點的個數(shù)。對于兩組點集，進行配準的 LS準則函數(shù)為： 綜上述，剛體配準是圖像配準中的一種，它最終目的是通過尋找一個空間變換 T，即 R和 t,使得經(jīng)過該空間變換后兩幅圖像間相似性度量 J 最小，這也就達到了兩幅圖像中的點 在空間幾何上的一致。由于本文僅涉及 Euclidean距離，本文后面僅簡要闡述了一下 Euclieadn距離度量。在該章中對全文進行總結(jié)，并 對下一步的工作進行展望。本章最后還展示了應(yīng)用剛體迭代最近點算法，在 matlab 上配準兩幅簡單線條的黑白圖片的實驗結(jié)果，并對實驗結(jié)果進行了初略分析，對結(jié)果中的不足提出疑問。由于攝像機在不同時刻，不同位置 角度進行攝像時，大多數(shù)情況下得到的地圖圖像將是不同的，然所謂的不同也不是完全的不同，它們可能存在某部分區(qū)域相同的情況。 本文的具體研究內(nèi)容如下 ： 1)研究僅有部分區(qū)域重疊的剛性圖像的配準問題，提出一種快速魯棒的剛體配準算法。 Chen提出DARCES方法，該方法通過自動選取控制點的方式完成粗匹配，然后進一步細化，完成精匹配。 Bjom Jensen在 ICP算法中引入概率距離矩陣，該距離矩陣同時考慮到傳感器噪音和待匹配目標位置的不確定性，從而可以有效排除 異常點。 Rusinkiewicz和 ， 保證兩個配準點集之間平移誤差最小，進一步提高算法的精度。 相對于全局點集的 配準研究 的 比較成熟， 解決方法多且較簡單，相反 ，部分對應(yīng)點集的配準問題還是一個難點 熱點問題，因此也是本文研究的重點 。例如 ， Schwartz和 Sharir通過弧長抽樣完成 了 曲線 圖像 的配準 問題 ， 但是 由于該方法受噪聲 影響很大 而往往結(jié)果不盡如人意； Taubin提出 了一種 不需要 提取 圖像 特征就可以完成三維曲線和曲面的姿態(tài)估計 的配準算法 ，但該算法 在 過于復(fù)雜的曲面上 圖像（ 如地形數(shù)據(jù)或者人臉數(shù)據(jù)等 ）上無能為力 。而本文所闡述到的剛體配準問題則是其他非剛體配準問題研究的基礎(chǔ)和前提，所以 在過去幾十年里，人們對于剛體點集配準做了許多探索 ，取得了很大成就。 因而 ，將多個深度圖像數(shù)據(jù)配準后建立三維的幾何模型并進行后期處理已經(jīng)成為當前一個重要的研究課題 。 在 較為簡單 二維圖像配準過程中，圖像特征一般被表示成點 或 線等 幾何特征 ，然后通過 某個算法策略來 計算這些幾何特征 （通常是兩個點集） 之間最優(yōu) 的 空間變換， 從而 使得圖像能在空間 幾何 上對應(yīng)起來 ，這就達到了最終的配準 。 目前 ，在最為傳統(tǒng)的 ICP算法的基礎(chǔ)上 已經(jīng) 發(fā)展出了許多處理各種不同種類數(shù)據(jù)和問題的變種算法 ， 大概上 按照圖像 分類 的不同 ，圖像配準問題 可分為三類： 第一類：獲取圖像 時間和位置不一致 ，造成圖像之間 具有較為明顯 的錯位 。點特征作為圖像最為簡單和常用的特征形式，被廣泛地應(yīng)用于圖像配準過程中， 因此 圖像點集配準 是 一項基礎(chǔ)且非常重要的研究課題。 作者簽名： 日 期： 學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨立進行研究所取得的研究成果。 作 者 簽 名： 日 期： 指導(dǎo)教師簽名： 日 期： 使用授權(quán)說明 本人完全了解 大學(xué)關(guān)于收集、保存、使用畢業(yè)設(shè)計（論文）的規(guī)定，即：按照學(xué)校要求提交畢業(yè)設(shè)計（論文）的印刷本和電子版本；學(xué)校有權(quán)保存畢業(yè)設(shè)計（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)；學(xué)?？梢圆捎糜坝?、縮印、數(shù)字化或其它復(fù)制手段保存論文；在不以贏利為目的前提下，學(xué)?？梢怨颊撐牡牟糠只蛉績?nèi)容。 作者簽名： 日期： 年 月 日 導(dǎo)師簽名： 日期： 年 月 日 指導(dǎo)教師評閱書 指導(dǎo)教師評價： 一、撰寫（設(shè)計）過程 學(xué)生在論文（設(shè)計）過程中的治學(xué)態(tài)度、工作精神 □ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格 學(xué)生掌握專業(yè)知識、技能的扎實程度 □ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格 學(xué)生綜合運用所學(xué)知識和專業(yè)技能分析和解決問題的能力 □ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格 研究方法的科學(xué)性；技術(shù)線路的可行性；設(shè)計方案的合理性 □ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格 完成畢業(yè)論文（設(shè)計）期間的出勤情況 □ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格 二、論文（設(shè)計）質(zhì)量 論文（設(shè)計）的整體結(jié)構(gòu)是否符合撰寫規(guī)范？ □ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格 是否完成指定的論文