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