1、一種3D模型的配準(zhǔn)算法PaulJ.Besl,Member,IEEE,andNeilD.McKay摘要本篇文章描述精確和有效計(jì)算包含自由形態(tài)曲線和自由形態(tài)平面的3D模型的通用、獨(dú)立表示的方法。該方法基于ICP算法處理“全六自由度”需要一個(gè)給定的點(diǎn)的幾何實(shí)體發(fā)現(xiàn)最近點(diǎn)的程序。ICP算法總是對(duì)均方差度量的局部最小值單調(diào)收斂，實(shí)驗(yàn)表明在第一次迭代中收斂的比例加快。因此，通過(guò)測(cè)試每一次最初的配準(zhǔn)為一個(gè)復(fù)雜模型的詳細(xì)數(shù)據(jù)給出一個(gè)適當(dāng)?shù)某跏夹D(zhuǎn)和轉(zhuǎn)化能最小化“全六自由度”距離度量的均方差（錯(cuò)譯）例如，一個(gè)已知的“model"模型和一個(gè)“data"模型代表著一個(gè)模型（考慮到復(fù)雜模型）的主要

2、部分通過(guò)一個(gè)最初變換還有一個(gè)相對(duì)較小的一系列旋轉(zhuǎn)能在幾分鐘內(nèi)配準(zhǔn)。這個(gè)算法的一個(gè)主要應(yīng)用就是在模型檢查之前使用一個(gè)理想的幾何模型記錄讀出數(shù)據(jù)。這個(gè)方法適用于決定基本問(wèn)題上，比如不同幾何體表達(dá)式的全等還有估算一致性不確定的點(diǎn)集的軌跡。實(shí)驗(yàn)的結(jié)果證明了這個(gè)配準(zhǔn)算法在點(diǎn)集、曲線和曲面上的性能。自由形態(tài)曲線配準(zhǔn)、自由形態(tài)曲面配準(zhǔn)、運(yùn)動(dòng)估計(jì)、位姿估算、四元數(shù)、3D配準(zhǔn)1介紹自由形態(tài)曲線、曲面、點(diǎn)集的全局和部分模型匹配度量在“幾何建模與計(jì)算機(jī)視覺(jué)”中已經(jīng)被描述出來(lái)，試圖在計(jì)算機(jī)視覺(jué)中形式化和統(tǒng)一這個(gè)關(guān)鍵問(wèn)題的描述：在一個(gè)傳感器坐標(biāo)系中已知3D數(shù)據(jù)，描述了一個(gè)可能和模型形狀一致的數(shù)據(jù)模型，已知模型坐標(biāo)系中的

3、模型形狀，估算最理想的旋轉(zhuǎn)變換，對(duì)齊或者配準(zhǔn)模型形狀和數(shù)據(jù)模型，最小化兩個(gè)形狀的距離，經(jīng)由一個(gè)均方差度量最終決定等價(jià)模型。許多應(yīng)用主要關(guān)注一下幾個(gè)問(wèn)題：一個(gè)深度圖像的分割區(qū)域和在一個(gè)CAD模型中的B樣條曲面子集匹配嗎？本文為自由曲面匹配問(wèn)題（該問(wèn)題已經(jīng)在“幾何建模與計(jì)算機(jī)視覺(jué)”中定義，“自由形態(tài)曲面匹配問(wèn)題”作為一個(gè)特例）提供了一個(gè)簡(jiǎn)單的、一般的、統(tǒng)一的方法，這個(gè)解決方法已經(jīng)推及到n維度已經(jīng)為以下問(wèn)題提供了解決方案:1）無(wú)一致性的點(diǎn)集匹配問(wèn)題；2）自由形態(tài)曲線匹配問(wèn)題。該算法要求無(wú)提取特征，無(wú)曲線或平面派生，還有無(wú)3-D數(shù)據(jù)預(yù)處理（除了統(tǒng)計(jì)數(shù)據(jù)異常的排除）。此次提出的方法主要應(yīng)用于在模型檢查前

4、使用幾何模型從移動(dòng)的精確裝置中記錄數(shù)位化資料。當(dāng)使用高精確無(wú)觸點(diǎn)的測(cè)量設(shè)備在一個(gè)淺深度區(qū)域檢查模型時(shí)，不同的感測(cè)點(diǎn)所得的數(shù)據(jù)并沒(méi)有太大的變化。因此，出于簡(jiǎn)化的目的還有存在基于與檢測(cè)應(yīng)用相關(guān)的大量數(shù)據(jù)，在大量數(shù)據(jù)之中的不相等的點(diǎn)集并不在考慮之中。相似的排除異常值被視為進(jìn)程的一個(gè)步驟，同樣的，同樣的這個(gè)步驟可能會(huì)是一個(gè)最好的手段，也可能不會(huì)被處理。在檢測(cè)應(yīng)用的環(huán)境中，假定一個(gè)有能夠排除明顯誤差的感應(yīng)器、高精準(zhǔn)、無(wú)觸點(diǎn)的檢測(cè)設(shè)備，沒(méi)有產(chǎn)生不良數(shù)據(jù)，數(shù)據(jù)合理。這個(gè)模型配準(zhǔn)算法可以通過(guò)下列幾個(gè)幾何數(shù)據(jù)表達(dá)式應(yīng)用：1）點(diǎn)集；2）線段集（折線）；3）隱性曲線：；4）參數(shù)曲線：；5）三角形集合；6）隱性曲面：

5、；7）參數(shù)曲面：這些包含了大多數(shù)應(yīng)用將要利用一個(gè)方法匹配3D模型，其它的表達(dá)式通過(guò)一個(gè)估算已知模型到已知數(shù)字化點(diǎn)的最近點(diǎn)的程序處理。本文結(jié)構(gòu)如下：首先回顧數(shù)個(gè)相關(guān)的論文；接下來(lái)會(huì)提及計(jì)算包含上文的集合表達(dá)式的一個(gè)模型到一個(gè)已知點(diǎn)的最近點(diǎn)的數(shù)學(xué)初步；然后介紹迭代最近點(diǎn)算法，一個(gè)證明關(guān)于其單調(diào)收斂性質(zhì)的定理。初次配準(zhǔn)的問(wèn)題會(huì)在接下來(lái)提到。最后，從提供的點(diǎn)集、曲線、曲面集展示迭代最近點(diǎn)算法的性能。2文獻(xiàn)回顧相關(guān)的一些工作已經(jīng)被發(fā)表在3D自由形態(tài)模型的配準(zhǔn)領(lǐng)域。目前有關(guān)于整體形狀匹配或者配準(zhǔn)的大部分的文獻(xiàn)資料局限于特定的類型或者形狀，也就是說(shuō)1)多面模型；2)分段-二次曲面模型；3) 一致性已知的點(diǎn)集

6、；讀者可能會(huì)查閱1985年以前的相關(guān)資料。為而來(lái)的其它最近的相關(guān)采集工作在下文中不會(huì)介紹，讀者請(qǐng)閱讀以下文章(引用)。從歷史的觀點(diǎn)上來(lái)說(shuō)，使用3D數(shù)據(jù)匹配自由形態(tài)模型的工作早已經(jīng)被Faugeras還有他在法國(guó)國(guó)家信息與自動(dòng)化研究所(簡(jiǎn)稱INRIA)的團(tuán)隊(duì)完成，早在1980年，他們就有效的匹配了法國(guó)雷諾公司的汽車配件。這個(gè)工作使得在計(jì)算機(jī)視覺(jué)團(tuán)隊(duì)中為3D點(diǎn)集的一致性使用四元數(shù)進(jìn)行最小二乘法配準(zhǔn)變得非常普及。選擇性的使用SVD算法在這個(gè)時(shí)間范圍內(nèi)并不被世人所周知。這個(gè)工作的初始限制就是它依賴在自由形態(tài)模型中合理的大型2D區(qū)域中可能的存在。1985年，Schwartz和Sharir對(duì)沒(méi)有抽取特征的自

7、由形態(tài)空間曲線匹配問(wèn)題開(kāi)發(fā)了一個(gè)解決方法。他們使用一個(gè)非四元數(shù)近似處理最小二乘法旋轉(zhuǎn)矩陣。這個(gè)方法適用于處理質(zhì)量合理的曲線數(shù)據(jù)，但是不適用面對(duì)有噪聲的曲線數(shù)據(jù)，因?yàn)檫@個(gè)方法對(duì)曲線使用弧長(zhǎng)抽樣法獲得一致點(diǎn)集。Haralicketal.發(fā)表了3D點(diǎn)集位置估算問(wèn)題使用魯棒性方法結(jié)合最小二乘法SVD配準(zhǔn)方法，提供了一個(gè)魯棒性統(tǒng)計(jì)量，選擇性的最小二乘法或SVD點(diǎn)集進(jìn)行匹配。這個(gè)算法能夠處理統(tǒng)計(jì)的離群值而且只要標(biāo)準(zhǔn)正交矩陣的行列式為正就能夠理論上被四元數(shù)算法取代。一個(gè)最近的會(huì)議議程里就包涵這個(gè)領(lǐng)域的貢獻(xiàn)。Horn根據(jù)Faugera的最小二乘法四元數(shù)匹配提出了一個(gè)選擇性使用4x4矩陣最大特征值代替最小特征值

8、的構(gòu)想。Horn和Brou也發(fā)展了擴(kuò)展高斯圖像EGI方法允許曲線匹配還有基于曲面正常直方圖的非凸模型的受限制集合的匹配。以上都是一些專家的研究。簡(jiǎn)單介紹，不必深究。3數(shù)學(xué)初步在這一部分，描述了在不同的幾何表達(dá)式上計(jì)算一個(gè)已知點(diǎn)的最近點(diǎn)的方法。首先，內(nèi)容包括基礎(chǔ)幾何實(shí)體、參數(shù)實(shí)體、隱性實(shí)體。讀者可能需要查閱Mortenson的相關(guān)知識(shí)以擴(kuò)充知識(shí)框架。歐式距離：，設(shè)A是點(diǎn)集中的一個(gè)點(diǎn)表示為;點(diǎn)到點(diǎn)A的歐氏距離就是：(1)A的最近點(diǎn)滿足公式。設(shè)L為連接點(diǎn)與點(diǎn)的線段。點(diǎn)到線段L的歐式距離為：(2)，&，這個(gè)要求直接進(jìn)行閉型計(jì)算。設(shè)L屬于線段集合表示為，再令。點(diǎn)到線段集L的歐氏距離為：(3)我們

9、第一步先創(chuàng)造一個(gè)計(jì)算從一個(gè)點(diǎn)到一(14)曲線要求僅計(jì)算和。對(duì)每位實(shí)體，牛頓在線段集L上的最近點(diǎn)滿足等式令t是被三個(gè)點(diǎn)、定義的三角形。點(diǎn)和三角形t的歐式距離為：，&，&，(4)要求直接進(jìn)行閉型計(jì)算。令T是三角形集合的一個(gè)元素表示為，T=,i=1.。點(diǎn)和三角形集T的歐式距離為：(5)在三角形集合T上的最近點(diǎn)滿足等式A. 點(diǎn)對(duì)參數(shù)實(shí)體的距離在這部分，一條參數(shù)曲線和一個(gè)參數(shù)曲面被視為一個(gè)單獨(dú)的參數(shù)實(shí)體，當(dāng)時(shí)代替參數(shù)曲線，當(dāng)時(shí)應(yīng)該代替參數(shù)曲面(R表示為實(shí)線)。曲線的評(píng)估區(qū)域是一個(gè)區(qū)間，但是這個(gè)評(píng)估區(qū)域?qū)τ谇婵梢允窃谄矫嫔系囊粋€(gè)任意的閉合區(qū)域。對(duì)于更多的參數(shù)實(shí)體的信息，例如，Bezier

10、和B抽樣曲線/曲面，可以參考其他的文章。從一個(gè)給定的點(diǎn)到一個(gè)參數(shù)實(shí)體E的距離為(6)對(duì)于距離的估算不是閉型是相對(duì)涉及。下面介紹一個(gè)對(duì)計(jì)算點(diǎn)對(duì)曲線還有點(diǎn)對(duì)曲面距離的方法。一旦對(duì)單獨(dú)實(shí)體的距離度量，參數(shù)實(shí)體的集合直接進(jìn)行閉型運(yùn)算。令F屬于參數(shù)實(shí)體集合表示為，再令；i=1.。點(diǎn)到這個(gè)參數(shù)實(shí)體F的距離為：(7)最近點(diǎn)在參數(shù)實(shí)體集合F上，滿足等式個(gè)參數(shù)實(shí)體(線段或三角形)的距離的單行體幾何學(xué)近似值。對(duì)一個(gè)參數(shù)空間曲線C=，能夠計(jì)算一個(gè)多段線L(C,)比如分段線性近似值絕不脫離空間曲線預(yù)先設(shè)立的距離，通過(guò)相應(yīng)的參數(shù)曲線的論證值u標(biāo)記多線段的每一點(diǎn)，這能夠獲得一個(gè)估值，這個(gè)值就是線段集合的最近點(diǎn)的論證值。相

11、似的，對(duì)一個(gè)參數(shù)曲面,一個(gè)能計(jì)算三角形集合T(S,)，這個(gè)分段三角形的近似值絕不脫離曲面預(yù)先設(shè)立的距離。通過(guò)相應(yīng)的參數(shù)曲面論證值(U,V)標(biāo)記每一個(gè)三角形的頂點(diǎn)，能獲得一個(gè)估值(，即三角形集的最近點(diǎn)估值。作為這些曲線和曲面的程序的結(jié)果，假定一個(gè)有效的初值能致的值非常接近參數(shù)實(shí)體最近點(diǎn)。當(dāng)一個(gè)可信賴的開(kāi)始的點(diǎn)是可用的時(shí)候，點(diǎn)對(duì)參數(shù)實(shí)體的距離問(wèn)題對(duì)使用一個(gè)純牛頓的最小值方法來(lái)說(shuō)是理想的。標(biāo)量的客觀功能最小化為(8)令為向量不同傾斜度操作數(shù)。當(dāng)f=0時(shí)最小值產(chǎn)生。當(dāng)這個(gè)參數(shù)實(shí)體是曲面時(shí)，2D傾斜度向量為，2D海塞矩陣為：(9)當(dāng)客觀功能的局部派生為以下：(10)(11)(12)(13)校正公式為：(

12、15)當(dāng)使用初始點(diǎn)選擇方法描述以上基于一個(gè)理性小值的單一方法時(shí)，牛頓計(jì)算最近點(diǎn)在迭代一至五下分成三次的一般收斂方法。這個(gè)計(jì)算牛頓方法在對(duì)比尋找最好初始點(diǎn)時(shí)費(fèi)時(shí)較少。B. 點(diǎn)對(duì)隱性實(shí)體的距離一個(gè)定義為空集(可能向量值多元)的隱性參數(shù)實(shí)體滿足。從一個(gè)給定點(diǎn)到一個(gè)隱性實(shí)體的距離I為(16)計(jì)算距離的估值不是閉型的，是相對(duì)涉及。下面是一個(gè)對(duì)計(jì)算點(diǎn)對(duì)曲線還有點(diǎn)對(duì)曲面距離方法的概述。一旦實(shí)施對(duì)獨(dú)立實(shí)體的距離度量那么隱性實(shí)體的集合直接進(jìn)行閉型運(yùn)算。令J屬于參數(shù)實(shí)體集合表示為,J=,k=1。點(diǎn)到一個(gè)隱性實(shí)體集合J的距離為(17)在隱性實(shí)體上的最近點(diǎn)滿足等式我們第一步先通過(guò)計(jì)算從一個(gè)點(diǎn)到一個(gè)隱性實(shí)體的距離為完成

13、參數(shù)實(shí)體創(chuàng)造一個(gè)單行體幾何學(xué)近似值(線段或三角形)。計(jì)算點(diǎn)到線集合或者是點(diǎn)到三角形集合的距離產(chǎn)生一個(gè)近似最近點(diǎn)，這個(gè)近似值能被用來(lái)計(jì)算精確距離。參數(shù)實(shí)體達(dá)到無(wú)約束的最優(yōu)化就足夠了，隱性實(shí)體距離問(wèn)題與其完全不同。為了尋找在一個(gè)定義為的隱性實(shí)體上的最近點(diǎn)，一定要解決在最小化二次的客觀功能項(xiàng)目、一個(gè)非線性受約束最小化方面受約束的最優(yōu)化問(wèn)題,(18)一個(gè)解決這個(gè)問(wèn)題的方法是去構(gòu)建增強(qiáng)的拉格朗日乘數(shù)法系統(tǒng)方程式：+=0(19)當(dāng)，經(jīng)由數(shù)字方法解決這個(gè)系統(tǒng)非線性方程式。方程式還有未知的非線性系統(tǒng)的數(shù)字為三個(gè)2D曲線、四個(gè)曲面、還有五個(gè)定義好的參數(shù)空間曲線。連續(xù)方法能用來(lái)解決此類代數(shù)實(shí)體問(wèn)題(甚至是沒(méi)有好的

14、初始點(diǎn))，但是一個(gè)好的初始點(diǎn)會(huì)允許使用更快的方法，比如多維的牛頓尋根方法。從數(shù)字的觀點(diǎn)，參數(shù)方法更容易解決。從應(yīng)用的觀點(diǎn)，沒(méi)有工業(yè)CAD系統(tǒng)存儲(chǔ)在隱性結(jié)構(gòu)下的自由形態(tài)曲線或曲面。因?yàn)檫@個(gè)原因用我們的工具系統(tǒng)或者經(jīng)由特殊數(shù)學(xué)事件或經(jīng)由參數(shù)架構(gòu)處理隱性曲面的利益。當(dāng)然，如果這里有一個(gè)必要去處理在隱形架構(gòu)中自由形態(tài)隱性實(shí)體的申請(qǐng)，以上算法能夠?qū)崿F(xiàn)。Taubin使用一個(gè)近似距離算法，該算法蘊(yùn)含了為曲面和2D曲線簡(jiǎn)單升級(jí)的公式。當(dāng)g接近為零時(shí)：(20)此方法僅在起始點(diǎn)為、方向?yàn)榈臒o(wú)限線與隱性實(shí)體交叉在一點(diǎn)，而這一點(diǎn)向量與無(wú)限線同向時(shí)精確。在一般情況下并不正確，這個(gè)近似值通常更遠(yuǎn)離隱性實(shí)體的點(diǎn)。因此，如果

15、需要精確結(jié)果的話不能使用其結(jié)果。C相對(duì)點(diǎn)集配準(zhǔn)所有的最近點(diǎn)(距離最小)算法都提到擴(kuò)展到N維。一個(gè)更必要的程序就是評(píng)估產(chǎn)生的最小二乘旋轉(zhuǎn)與變換。對(duì)我們的目的來(lái)說(shuō)，在2D和3D中，只要不要求映射，四元數(shù)算法比SVD方法更好。SVD方法，基于兩點(diǎn)分布的互協(xié)方差矩陣，容易推廣至n維，當(dāng)維度大于3為時(shí)，此算法可能會(huì)成為我們的選擇。Horn的解決方法如下盡管等價(jià)于Faugeras方法。我們簡(jiǎn)要的陳述一下SVD互協(xié)方差矩陣的重要作用。組成四元數(shù)的是四個(gè)向量要求，。在本部分的末尾，你會(huì)發(fā)現(xiàn)，可以由一個(gè)單元旋轉(zhuǎn)四元數(shù)產(chǎn)生一個(gè)3的旋轉(zhuǎn)矩陣令為一個(gè)變換向量。完成配準(zhǔn)狀態(tài)的向量被表示為。令P=為測(cè)試數(shù)據(jù)點(diǎn)集，與一個(gè)模

16、型點(diǎn)集X=對(duì)齊，當(dāng)還有每個(gè)點(diǎn)和與之對(duì)應(yīng)的點(diǎn)有相同的指數(shù)。均方差客觀的功能的最小化為3是3x3單獨(dú)矩陣。與特征向量單元相應(yīng)的是最大化特征向量矩陣Q(上式)被選為理想的旋轉(zhuǎn)。理想的變換向量為:It=總-岡和亦(26)最小二乘四元數(shù)運(yùn)算是O(Np)表示為：(27)QP.X)他)誌兔-鳳爾-刑®(P)是被用變換之后t-1dms是最小二乘法點(diǎn)匹配誤差。符號(hào)來(lái)表示點(diǎn)集P在通過(guò)配準(zhǔn)向量(23)單；點(diǎn)被三角形集合還有線段集合作為起始點(diǎn)與被測(cè)試的點(diǎn)集P的質(zhì)量的重心還有相對(duì)的點(diǎn)集X的質(zhì)心由下列公式給出:點(diǎn)集P與X的互協(xié)方差矩陣為:環(huán)=*莎-掰i-制=+臉卜就，4'日(24)反對(duì)稱矩陣Aij=(.

17、)的循環(huán)部分被用來(lái)構(gòu)建列向量。這個(gè)向量接下來(lái)被用于構(gòu)建對(duì)稱4x4矩陣Q:的形式。4迭代最近點(diǎn)算法(ICPAlgorithm)既然已經(jīng)概述了從一個(gè)給定的點(diǎn)計(jì)算幾何形狀最近點(diǎn)的方法還有計(jì)算最小二乘法配準(zhǔn)向量，ICP算法能夠依照一個(gè)抽象的幾何體X(內(nèi)部表達(dá)式必須精確描述算法，但是并不是討論的中心)描述下來(lái)。因此，被很好的應(yīng)用于一下幾個(gè)部分：1、點(diǎn)集；2、線段集；3、參數(shù)曲線集；4、隱性曲線集；5、三角形集；6、參數(shù)曲面集；7、隱性曲面集。在算法的描述中，一個(gè)data模型P移動(dòng)到對(duì)齊的model模型X中。data還有model模型可能被表示在任何允許的形式中。對(duì)于我們的目的來(lái)說(shuō)，如果data模型沒(méi)有在

18、點(diǎn)集形式中的話，那么此模型必須被分解為點(diǎn)集。幸運(yùn)的是，這個(gè)很簡(jiǎn)末尾點(diǎn)使用，如果data模型在曲面或者曲線形式中，那么則使用三角形/線段的起始點(diǎn)和末尾點(diǎn)(上面提到)的近似值。點(diǎn)的數(shù)量在data模型中被表示為Np。令Nx為model模型包含的點(diǎn)、線段、或者三角形的數(shù)量。如上文說(shuō)到，曲線與曲面最近點(diǎn)估算實(shí)現(xiàn)了我們的系統(tǒng)要求一個(gè)線或三角形框架去產(chǎn)出牛頓迭代的初始參數(shù)值，因此Nx的數(shù)量仍然與這些平滑實(shí)體相關(guān)但是根據(jù)估值的精確性有所不同。單獨(dú)數(shù)據(jù)點(diǎn)與model模型x之間的距離度量d被描述為=mn|j：-p|.(28)在X中的最近點(diǎn)產(chǎn)生的最小距離表示為，致d(,)=d(,X),y屬于X,(以上除X皆為向量)

19、。標(biāo)記計(jì)算最近點(diǎn)為O(Nx)最壞事件與期望事件log(Nx).當(dāng)最近點(diǎn)計(jì)算(從p到X)被表示為每一個(gè)在P中的點(diǎn)時(shí)，程序是最壞事件O(NpNx)。令Y表示最近點(diǎn)的結(jié)果集，然后令C為最近點(diǎn)操作數(shù)：Y=C(P,X)(29)給結(jié)果一個(gè)相關(guān)的點(diǎn)集Y,最小二乘法配準(zhǔn)為計(jì)算以上描述的:(,d)=Q(P,Y)(30)Data模型點(diǎn)集的位置經(jīng)由P=校正。A.ICP算法聲明c) 應(yīng)用配準(zhǔn)：Pk+1=(P0)(消耗：O(Np)。d) 當(dāng)變化在方差誤差下降到一個(gè)預(yù)先設(shè)定的臨界值>0時(shí)終止迭代，指定迭代期望精確值為：dk-dk+1<如果期望的是一個(gè)無(wú)窮小量臨界值，能用替代，當(dāng)model模型的協(xié)方差軌跡的平方

20、根表明了這個(gè)model模型的大致尺寸時(shí)。B.收斂定理ICP算法的收斂定理現(xiàn)在開(kāi)始證明。大意如下：1、最小二乘法配準(zhǔn)每次迭代一般會(huì)減少相應(yīng)的獨(dú)立點(diǎn)之間的平均距離；2、最近點(diǎn)決定一般減少每個(gè)獨(dú)立點(diǎn)的距離。當(dāng)然，這個(gè)獨(dú)立距離的縮小減少了平均距離因?yàn)檎龜?shù)集合的平均值更小了。在下面的證明中，我們提供一個(gè)更詳盡的解釋。定理：考慮到均方差距離的客觀功能，迭代最近點(diǎn)算法對(duì)一個(gè)局部最小值也單調(diào)收斂。證明：給定P_k=(P0)還有X，計(jì)算最近點(diǎn)集Y_k=作為上面規(guī)定的內(nèi)部的幾何表達(dá)式X。均方差誤差e_k被下式給出：坯=亍£|角:-除(31操作數(shù)Q被用于得到還有：ICP算法陳述如下: 點(diǎn)集P同Np點(diǎn)從da

21、ta模型和model模型X(Nx支持原始幾何圖形：點(diǎn)、線、三角形)中獲取。 迭代是通過(guò)設(shè)置P0=P,=，k=0初始化。配準(zhǔn)向量被定義為與初始數(shù)據(jù)集P0相關(guān)，為了使得最后的配準(zhǔn)代表完全變換。步驟1、2、3、4被應(yīng)用，直到公差r收斂。計(jì)算需要的每個(gè)操作數(shù)已經(jīng)在方括號(hào)中給出。a) 計(jì)算最近點(diǎn)Yk=C(Pk,X)(消耗：O(NpNx)最壞事件，O(NpLogNx)平均)b) 計(jì)算配準(zhǔn)：(,dk)=Q(P0,Yk)(消耗：O(Np)仁f£life-R麗恤-制2(32)D_k<=e_k;假定d_k>e_k如果確實(shí)是這樣，那么在點(diǎn)集的恒等式變換可以產(chǎn)生一個(gè)比最小二乘法配準(zhǔn)更小的均方差誤

22、差，這個(gè)對(duì)于這個(gè)事件來(lái)說(shuō)是不可能的。接下來(lái)令最小二乘配準(zhǔn)被用于點(diǎn)集P_0，(37)產(chǎn)生點(diǎn)集Pk+1。如果與早先的點(diǎn)集Y_k相關(guān)的被保持，那么均方差誤差依舊是d_k，如下式：再令為一個(gè)足夠小的角度臨界值。如果弘<皿(ind弘-i<別(36)foreachi=l.An(34)然而，在隨后的最近點(diǎn)操作數(shù)應(yīng)用中，獲取了一個(gè)新的點(diǎn)集Y_k+1：Y_k+1=C(P_k+1,X)。很明顯：因?yàn)樵谕ㄟ^(guò)變換還有在一些與相關(guān)的新的距離不變之前點(diǎn)是最近點(diǎn)。如果到的距離比的更遠(yuǎn)，那么會(huì)直接否定C最近點(diǎn)操作數(shù)的基礎(chǔ)操作數(shù)。因此，均方差誤差e_k還有的d_k必須服從下列關(guān)系：BLSLANDMETflUDFOR

23、RHGlSlRATIONOFIDSHAPkS那么這里有一個(gè)為最近三個(gè)配準(zhǔn)狀態(tài)向量最好的方向隊(duì)列：，令d_k,d_k-1,d_k-2為關(guān)聯(lián)的均方差誤差，再令v_k,v_k-1,v_k-2，為關(guān)聯(lián)近似值弧長(zhǎng)論證值：UnetirTheMe曲瓠ICTAl腳uthi"0<心+：<fit.i<4<for汕1kFig-LConsistenrdirectionalloaccelerationof(heICPalgflrtthm-當(dāng)然，只要均方差誤差不能為負(fù)，更低的約束就會(huì)產(chǎn)生。因?yàn)榫讲钫`差序列不再增長(zhǎng)還有約束下降，上面描述的算法對(duì)最小值來(lái)說(shuō)一定單調(diào)收斂。實(shí)驗(yàn)中，我們發(fā)現(xiàn)在第

24、一次迭代中的快速收斂因?yàn)榻咏植孔钚≈刀鴾p緩。甚至在減緩的節(jié)奏上，一些地方在30和50次迭代的時(shí)候產(chǎn)生了精確的結(jié)果：d_k0.1%的model模型。在下一部分使用一個(gè)簡(jiǎn)易的附加操作數(shù)能精確收斂。C. 一個(gè)精確的ICP算法精確的ICP算法在基礎(chǔ)線段搜索方法上使用一個(gè)較小的變動(dòng)多元無(wú)約束極小值。作為迭代最近點(diǎn)算法程序，一個(gè)配準(zhǔn)向量的序數(shù)被推廣為,這些表示了為了局部理想模型匹配進(jìn)行的恒等式變換在配準(zhǔn)狀態(tài)空間的軌跡?？紤]到不同向量序數(shù)被下式定義：Pla-ncRepre&cnas7-DSpiCi.!Lint-arlupduie舟nhoMIJjxLik觀察上面的形勢(shì)圖fig.1。接下來(lái)，用一個(gè)線性

25、近似值還有一個(gè)拋物線插值計(jì)算最近的三個(gè)數(shù)據(jù)點(diǎn)：上式給我們一個(gè)可能的線性校正，基于令交叉線上式定義了一個(gè)在配準(zhǔn)狀態(tài)空間方向。令在兩個(gè)最近的方向之間的7個(gè)空間的角度表示為：在可靠的一邊，我們采集了一個(gè)允許的最大(«)一個(gè)可能的拋物線校正，基于拋物線極值點(diǎn)：BOTAIIDNfig.2.VariousquantjeicsjoltediicRiiuncomilfarfixbssUonaccclerJicdICPalgorithm*值v_max。下列的邏輯式用來(lái)執(zhí)行一個(gè)試圖校正：1) 如果0<v_2<v_1<v_max或者0<v_2<v_max<v_1,當(dāng)在點(diǎn)

26、集上執(zhí)行校正時(shí)使用拋物線校正迭代向量：=+代替一般向量選擇性最小化方法，P_k+1=(P_0)。2) 如果0<v_1<v_2<v_max或者0<v_1<v_max<v_2或者v_2<0&0<v_1<v_max，使用基于線段的校正向量代替一般向量。3) 如果v_1>v_max&&v_2>v_max，使用最大值進(jìn)行允許的校正般的向量。我們已經(jīng)發(fā)現(xiàn)實(shí)驗(yàn)時(shí)適應(yīng)性地設(shè)置v_max=25|提供了一個(gè)好的明智的檢查在校正允許迭代最近點(diǎn)算法用一個(gè)給定的精度移動(dòng)到局部最小值在許多更小的步驟中。對(duì)一個(gè)給定的值進(jìn)行一個(gè)名義上的

27、超過(guò)50次ICP迭代是在15至20此迭代的時(shí)候就精確了。如果校正配準(zhǔn)向量以某種方法超越足夠產(chǎn)生一個(gè)更壞均方誤差的最小值，可能會(huì)有利于用最近兩步使用新的配準(zhǔn)去構(gòu)造一個(gè)新的拋物線并移動(dòng)到適當(dāng)?shù)淖钚≈?。這個(gè)在我們的試驗(yàn)中并不必要。嚴(yán)格的來(lái)說(shuō)，如果建議的校正引起了一個(gè)更差的均方誤差的話，可以直接忽略。為了提供一個(gè)四元數(shù)例子，在一樣的自由形態(tài)曲面匹配測(cè)試中使用基礎(chǔ)而且精確的ICP算法，通過(guò)50次迭代的過(guò)程，記錄比較關(guān)系、配準(zhǔn)值、均方根誤差(RMSroot-mean-square)、最大值誤差、角度變形、還有累積弧長(zhǎng)值?；A(chǔ)ICP算法的結(jié)果已經(jīng)在Fig.2中表示出來(lái)。注意所有的曲線都是平滑的。最重要的特征是cos()繪圖表明所有的校正方向一致除了第一次迭代。與此相反加速的ICP算法顯示出令人滿意跳躍性的表現(xiàn)(圖Fig.3)。另外，注意在第一次和緊接著的第二個(gè)加速過(guò)程，大多數(shù)特性接近他們的最終結(jié)果。加速步驟發(fā)生了當(dāng)V-型下降發(fā)生在cos()圖與迭代次數(shù)相對(duì)抗。D選擇性最小值方法比較用其它的可選項(xiàng)，ICP算法允許我們相對(duì)快速地用7步從一個(gè)給定的開(kāi)始點(diǎn)移動(dòng)到一個(gè)局部最小。每一次迭代要求僅僅一個(gè)最近點(diǎn)