【文章內(nèi)容簡介】 數(shù)學表達式為。當達到我們設定的某個范圍值下限時，我們就可以讓ICP算法停止迭代退出了。當然實際配準中，我們很大的可能性是不可能使配準誤差達到它理論上的最小值，因為這可能需要難以忍受的等待時間或者根本就不存在這樣一個最小值。所以我們往往采取均方誤差達到設定范圍下限和迭代步驟達到指定的循環(huán)次數(shù)這兩個指標，來決定是否停止迭代。當ICP算法循環(huán)退出后，那么返回得到最終的剛體變換和點集對應關系，通過這兩個量我們就可以把兩幅剛性圖像配準了。 算法求解對第一步求解，有kd樹、基于Delaunay(德勞內(nèi) )三角化的最近點搜索算法等。很多研究和實驗結果一致表明，kd樹適合于高維點集的點搜索，而基于Delaunay三角化的最近點搜索算法則更適合于低維點集的點搜索。鑒于簡單起見，本文采用的是Delaunay三角化。對第二步求解，有SVD(奇異值分解，Singular Value Deposition)、四元組、正交矩陣、雙四元祖方法，本文采用的是SVD1）Delaunay三角化求解點集對應關系如何把一個散點集合剖分成不均勻的三角形網(wǎng)格，這就是散點集的三角剖分問題。將二維(三維)空間中任意分布的散亂點用直線段連接起來，形成的空間上既不重疊又無間隙的緊鄰的三角形(四面體)集，每個三角形(四面體)的頂點即為原始散亂點。也就是說，在二維情況下得到的是三角形網(wǎng)格，在三維情況下得到的是四面體網(wǎng)格。在已有的多種三角剖分的優(yōu)化規(guī)則中，目前公認的具有最好幾何拓撲性質(zhì)的剖分就是符合Delaunay規(guī)則的三角剖分。Delaunay剖分必須滿足兩個基本準則，其一是空圓特性，即在Delaunay三角形網(wǎng)中任一個三角形的外接圓范圍內(nèi)不會有其它點存在。其二是最大化最小角特性，即在散點集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角最大。局部變換法和Watson算法是離散點集Delaunay三角剖分的常用算法，算法過程中逐點添加、局部優(yōu)化是三角網(wǎng)格生成速度的重要影響因素。根據(jù)Delaunay三角剖分原理，可以構造出各種適合該網(wǎng)格形狀的搜索策略。對于ICP算法中式的求解，首先將模型點集進行Delaunay三角剖分，然后采用三角劃分搜索策略找到形狀點集在模型點集中的對應點。該搜索策略大幅度提高了點集對應關系求解的速度和精度。2）SVD方法求解剛體變換SVD方法相當比較簡單，而且具有較好的擴展性，所以本文采用奇異值分解Singular Value Deposition的方法解決第二步中剛體變換求解。定理（1）：給定任意兩個維對應點集和，當時，目標函數(shù)取得最小值。設 ， 那么式最小化目標函數(shù)為：要使目標函數(shù)最小，則： 令，化簡目標函數(shù)得：最小化目標函數(shù)，即最小化 實驗結果 圖a1 模型圖像 圖a2 待配準圖像 圖a3 配準結果 圖b1 模型圖像 圖b2 待配準圖像 圖b3 配準結果 上面所示的實驗結果圖中，因為為了簡單起見均采用的是黑白圖，而且僅僅是提取了圖片中圖像物體的外部輪廓線條特征來作配準的標準。其中模型圖像和待配準圖像之間僅僅是一個旋轉和平移的效果，并涉及其它復雜的圖像變換，這也正是剛體變換所需要的前提。在配準結果圖中，需要說明的是紅色線是待配準圖像的輪廓，綠色線是模型圖像的輪廓，程序結果并沒有很好的展示配準后兩者相重疊的輪廓部分。 從上面的配準結果來看，IPC算法的配準效果還蠻不錯的。 本章小結本章首先提出了圖像點集配準問題的概念，接著在數(shù)學上建立點集配準的模型，隨后又闡述了在眾多的剛體配準研究中最為矚目的由Besl和Mckay提出的ICP算法，并且詳盡地論述了算法運作流程和算法每步中問題的解決方法。本章最后給出了利用ICP算法在matlab上所做的簡單圖像配準實驗結果。3 基于迭代最近點的部分配準算法前面第二章描述了ICP剛體配準問題并建立了它的數(shù)學模型，且給出求解ICP剛體配準問題的具體方法和原理，接下來本章將在上面的基礎上進一步研究基于ICP（即迭代最近點）的剛體部分配準問題。因為傳統(tǒng)的ICP算法是建立在假設兩個待配準點集中所有點都是有其相對應關系的前提下的，它并未考慮到實際中存在的復雜情況，如障礙物遮擋，拍攝角度狹窄及傳感器噪聲等因素所造成的點集部分數(shù)據(jù)丟失或存在大量離群點情況下圖像點集的配準。所以本章針對這一問題，會在傳統(tǒng)ICP算法基礎上，將引入重疊百分比的概念，然后建立關于空間變換的新目標函數(shù)，因而與前面ICP算法不同的是在配準過程中，將同時更新三個未知量，即點集重疊百分比，空間變換和點間對應關系。很明顯相對傳統(tǒng)的ICP算法新增了重疊百分比這個變量，所以算法也相應變得更為復雜，更具挑戰(zhàn)性。在內(nèi)容安排方面，本章首先給出點集剛體部分配準問題的描述及解決方案，接著提出本文的第一個創(chuàng)新點，一種能夠自動計算點集重疊百分比的快速魯棒的剛體配準算法，然后詳盡闡述算法的基本思想原理和算法解決問題的步驟流程，最后就是給出實驗結果，并根據(jù)結果一些數(shù)學品質(zhì)考察此算法的性能。 剛體部分配準問題傳統(tǒng)ICP算法假設形狀點集P中每一點都能在模型點集中找到與之相對應的點，即假定了兩個待配準點集之間存在完整的對應關系。然而在現(xiàn)實環(huán)境中圖像配準問題中，由于攝相機拍攝角度，障礙物遮擋，傳感器噪聲以及圖像處理過程噪聲等因素的影響，因而存在這樣一種情況：點集P中僅有部分點能夠在點集M找到相對應的點，即兩個點集之間僅存在部分對應的關系，而且很可能P中能找到對應點的點集是非常小的一部分。在這種情況下，傳統(tǒng)的ICP算法就無法保證配準結果的魯棒性，無法得到較為精確的配準結果，而且非匹配點集所占比例越大則往往得到錯誤配準結果的幾率更大。如果按照點集對應關系來分類，則通常認為點集部分配準問題可以分為兩大類：一類是具有點集中部分數(shù)據(jù)丟失或點集中含有大量離群點的點集配準，而另一類是具有形狀噪聲的點集配準問題。第一類往往是由于攝像機兩次拍攝角度不同，或者兩次采集圖像時障礙物遮擋情況不一，再或者是采集設備自身缺陷等原因而造成的。它主要表現(xiàn)為兩個點集之間僅有一部分點集是能夠?qū)饋淼模渌糠謩t完全相異，并且這些非對應點存在方式跟外界環(huán)境和對象物體形狀本身有關，因而無法精確估計非對應點的分布和幾何位置。具有形狀噪聲的點集一般是由于外界環(huán)境的干擾和采集設備本身的限制產(chǎn)生的。所謂形狀噪聲，它是指圖像點集位置與真實精確的位置相異但差別卻很小，僅僅是一個小小的擾動而已，而且噪聲往往服從某些概率分布，如高斯分布。所以對于此類經(jīng)常采用概率的方法進行建模匹配。本章即后面的地圖拼接僅涉及到第一類點集部分配準問題，所以對于第二類點集部分配準在本文中將不會再被提及和探討。圖給出二維情況下缺失數(shù)據(jù)點集實例。其中紅色表示模型點集，藍色表示形狀點集，綠色和天藍色分別表示兩個點集中多余或者缺失的部分。仔細觀察31中的兩幅圖可以看出，形狀點集中的綠色部分在模型點集中無法找到相對應的部分，而模型點集中天藍色部分在形狀點集中也無法對應起來。這就是本文所涉及的剛體點集部分配準問題。圖31 缺失數(shù)據(jù)點集如何解決上述具有部分數(shù)據(jù)缺失的點集配準問題呢？大家都會想到的很簡單的考慮是先要排除待配準點集中彼此多余或者缺失的部分，僅留下能夠相對應起來的部分，否則不大可能得到可靠的配準結果。然而宏觀的想法是很簡單的，但具體到如何有效排除點集中的非對應點集部分則是一個較為復雜難辦的問題。所以這是本章要解決的一個艱巨重要的關鍵問題。在前面，本文緒論中范范而談了幾種處理部分對應點集的配準方法，即閾值方法，概率方法，幾何方法等，然而這些方法都依賴于待配準點集的形狀，或知道了噪聲點服從某個已知出名的概率分布函數(shù)，而我們面對的情況是未知待配準點集圖像形狀和未知噪聲概率分布函數(shù)這一更為嚴峻的情景，它往往是具有較大面積數(shù)據(jù)缺失的情況。所以前面談到的方法對本文所研究的問題無法適用，我們將采用一個新的方法。分析具有缺失數(shù)據(jù)的點集配準問題，可以發(fā)現(xiàn)兩個待配準點集之間的重疊百分比是一個重要的衡量標準。如果能計算兩個點集之間的重疊百分比，那么就可以很輕易地排除點集中的非對應點。換而言之，對于具有缺失數(shù)據(jù)的點集配準問題，不僅要確定兩個點集的對應關系和全局的幾何變換，而且還要確定點集的重疊百分比。 模型建立如何確定兩個點集之間重疊百分比?r是建立具有部分數(shù)據(jù)缺失的點集剛體部分配準數(shù)學模型的一個至關重要的問題。在本文中，該百分比?r的最優(yōu)值是由配準誤差來確定。作為一個直觀，圖 32給出了在一般大量配準情景中，點集重疊百分比?r與均方根誤差（Root Mean Square，RMS）的關系。從圖 32可以看出，配準誤差是重疊百分比r的一個簡單的單調(diào)遞增函數(shù)，開始重疊百分比?r比很小時配準誤差幾乎為零，因為形狀點集中能夠建立對應關系的點個數(shù)此時極少故幾乎不存在任何誤差，然而當重疊百分比達到某個值時配準誤差開始突增，根據(jù)大量實驗表明此時的?。接下要做的是尋找最優(yōu)的?r值，所謂最優(yōu)的重疊百分比，是指在該百分比值下能夠求得最優(yōu)的空間變換，即形狀點集中那部分能夠建立對應的點集能夠最佳的與模型點集中相對應的部分點集能夠在幾何空間上達到一致。理論和實驗一致證明了，最優(yōu)的重疊百分比?r并非像大家想像的那樣理所當然的對應具有最小配準誤差時的值，而是對應配準誤差突增時的值，即?圖 Error! No text of specified style in document.2 配準誤差與重疊百分比與傳統(tǒng)ICP配準算法相比較，因為傳統(tǒng)ICP配準算法假設了形狀點集和模型點集間具有完整完全的點對應，故當均方誤差達到最小時所求得空間變換也是點集配準過程中最優(yōu)的變換，再經(jīng)過多次迭代后配準誤差更小，空間變換更優(yōu)，最終配準結果趨于最佳。而對于具有部分數(shù)據(jù)缺失的點集部分配準問題，最優(yōu)空間變換的求解要復雜得多，它不像傳統(tǒng)ICP配準算法那樣僅僅取決與一個配準誤差量，它還依賴與重疊百分比?r。所以說重疊百分比??是很重要的，最基本的要求是該百分比??能盡可能多地包括兩個點集中能夠相對應的部分，而且還要盡可能排除所有離群點。從重疊百分比??的大小考慮：1）重疊百分比很小。點集之間能夠作對應點個數(shù)很少，按照配準均方差的度量方式計算誤差將會很小，但是此時配準算法所能夠利用的點集信息很少，因而導致配準結果并不盡人意，雖然此時配準誤差幾乎為零。2）重疊百分比很大。點集之間能夠作對應點個數(shù)很多，按照配準均方差的度量方式計算誤差將會比較大，作為補償?shù)氖谴藭r配準算法所能夠利用的點集信息很大。但是如果重疊百分比?r取值過大，又會產(chǎn)生在匹配過程中引入大量不能作對應的點的問題，而這些異常點會提供錯誤的信息，錯誤引導配準的進行方向，其結果是配準不魯棒。綜上述，最優(yōu)的重疊百分比r應該是兩矛盾方面的中庸之道。如何講呢？最優(yōu)的重疊百分?r一方面要使配準誤差相對較小，而另一方面又要盡可能多地利用待配準點集中能夠作對應的點，而這兩方面又是相互矛盾對立的。最優(yōu)重疊百分比?r使得點集配準在誤差取得極小值的情況下又盡量多地利用了待配準點集的信息。為了使下面的算法和傳統(tǒng)ICP算法相一致，即更為直觀的在配準誤差達到最小時，配準效果也達到最佳，而不是前面分析的在誤差突變時刻，本文借用正則化的思想來解決這個問題。既然配準誤差是關于重疊百分比的遞增函數(shù)，而最優(yōu)重疊百分比出現(xiàn)在誤差突增的時刻。因此可以給該誤差除以一個連續(xù)遞增的懲罰因子，得到一個新的目標函數(shù)。如果懲罰因子選擇合適，所得新的目標函數(shù)就是一個凸函數(shù)，而該凸函數(shù)的最小值點就是最優(yōu)重疊百分比對應的取值點。下面給出新目標函數(shù)的數(shù)學表達：給定Rm維空間中的形狀點集S和模型點集M，設表示兩個點集的重疊百分比，表示形狀點集中與模型點集相對應的部分點集。新的目標函數(shù)定義為關于重疊百分比和調(diào)控參數(shù)的函數(shù)： 點集配準均方誤差:懲罰函數(shù):則目標函數(shù)又可以表示為： 如下圖所示，藍色點線是配準誤差函數(shù)，綠色點線是懲罰函數(shù)，而紅色點線則是目標函數(shù)。很明顯可以看出該目標函數(shù)是一個上凸函數(shù)，而函數(shù)的最小值點的橫坐標就是最優(yōu)重疊百分比r的取值。根據(jù)上述分析，目標函數(shù)的最小值點所對應得到的重疊百分比就是要求解的最優(yōu)重疊百分比。圖 Error! No text of specified style in document.3 如前面闡述傳統(tǒng)ICP算法流程一樣，這里給出本文中被稱作帶重疊百分比部分點ICP算法的流程圖。與前面經(jīng)典ICP算法顯著的不同是，該算法在每步迭代中除了要計算求解點集的對應關系和空間變換外，還要計算點集重疊百分比r。簡要具體流程如圖 34所示：圖 Error! No text of specified style in document.4 算法流程圖算法開始的第一步，假設形狀點集和模型點集是完全重疊的，即令，調(diào)控參數(shù)=。然后以后每步迭代中調(diào)控參數(shù)從遞減到。對于第步的，在迭代過程中最小化目標函數(shù)，計算出該步最優(yōu)的剛體變換和，然后賦值傳遞給第步。算法的內(nèi)循環(huán)迭代流程類似于傳統(tǒng)ICP算法，但是循環(huán)體內(nèi)增加了求解點集重疊百分比的步驟，具體流程為：1)根據(jù)步的剛體變換，計算點集和的對應關系 2)求目標函數(shù)的最小值的過程中確定第步的最優(yōu)重疊百分比r 3)根據(jù)上步求得的對應點集和和重疊百分比，求解第步中最優(yōu)子集： 4)通過求關于子集度量函數(shù)的最小化值計算第步的空間變換 5）更新和: 配準過程中，只有當取值能夠搜索出最優(yōu)的裁剪度時，才能計算出準確的剛體變換，這時點集配準會趨于穩(wěn)定狀態(tài)。進入穩(wěn)定狀態(tài)后，會隨著的減小而增大。配準循環(huán)結束后，算法讓從開始往遞增方向搜索，因為在穩(wěn)定狀態(tài)（配準結果正確）下是遞減的，因此第一個使目標函數(shù)遞增的 就是待求的最優(yōu)參數(shù)。該點對應的是最優(yōu)的目標函數(shù)，而其對應的裁剪度和剛體變換也是最優(yōu)的配準結果。為了驗證帶重疊百分比的點集部分配準算法的魯棒性和收斂性，本文根據(jù)上面闡述的算法寫了matlab程序作了圖像配準仿真實驗。下面是實驗結果所展示的效