機(jī)器視覺(jué)之ICP算法和RANSAC算法

臨時(shí)研究了下機(jī)器視覺(jué)兩個(gè)基本算法的算法原理 ，可能有理解錯(cuò)誤的地方，希望發(fā)現(xiàn)了告訴我一下

主要是了解思想，就不寫具體的計(jì)算公式之類的了

（一） ICP算法（Iterative Closest Point迭代最近點(diǎn)）

ICP（Iterative Closest Point迭代最近點(diǎn)）算法是一種點(diǎn)集對(duì)點(diǎn)集配準(zhǔn)方法，如下圖1

如下圖，假設(shè)PR（紅色塊）和RB（藍(lán)色塊）是兩個(gè)點(diǎn)集，該算法就是計(jì)算怎么把PB平移旋轉(zhuǎn)，使PB和PR盡量重疊，建立模型的

ICP是改進(jìn)自對(duì)應(yīng)點(diǎn)集配準(zhǔn)算法的

對(duì)應(yīng)點(diǎn)集配準(zhǔn)算法是假設(shè)一個(gè)理想狀況，將一個(gè)模型點(diǎn)云數(shù)據(jù)X（如上圖的PB）利用四元數(shù)旋轉(zhuǎn)，并平移得到點(diǎn)云P（類似于上圖的PR）。而對(duì)應(yīng)點(diǎn)集配準(zhǔn)算法主要就是怎么計(jì)算出qR和qT的，知道這兩個(gè)就可以匹配點(diǎn)云了。

但是對(duì)應(yīng)點(diǎn)集配準(zhǔn)算法的前提條件是計(jì)算中的點(diǎn)云數(shù)據(jù)PB和PR的元素一一對(duì)應(yīng)，這個(gè)條件在現(xiàn)實(shí)里因誤差等問(wèn)題，不太可能實(shí)線，所以就有了ICP算法。

ICP算法是從源點(diǎn)云上的（PB）每個(gè)點(diǎn) 先計(jì)算出目標(biāo)點(diǎn)云（PR）的每個(gè)點(diǎn)的距離，使每個(gè)點(diǎn)和目標(biāo)云的最近點(diǎn)匹配，（記得這種映射方式叫滿射吧）這樣滿足了對(duì)應(yīng)點(diǎn)集配準(zhǔn)算法的前提條件、每個(gè)點(diǎn)都有了對(duì)應(yīng)的映射點(diǎn)，則可以按照對(duì)應(yīng)點(diǎn)集配準(zhǔn)算法計(jì)算，但因?yàn)檫@個(gè)是假設(shè)，所以需要重復(fù)迭代運(yùn)行上述過(guò)程，直到均方差誤差小于某個(gè)閥值。也就是說(shuō) 每次迭代，整個(gè)模型是靠近一點(diǎn)，每次都重新找最近點(diǎn)，然后再根據(jù)對(duì)應(yīng)點(diǎn)集批準(zhǔn)算法算一次，比較均方差誤差，如果不滿足就繼續(xù)迭代。

（二）RANSAC算法（RANdom SAmple Consensus隨機(jī)抽樣一致）

它可以從一組包含“局外點(diǎn)”的觀測(cè)數(shù)據(jù)集中，通過(guò)迭代方式估計(jì)數(shù)學(xué)模型的參數(shù)。它是一種不確定的算法——它有一定的概率得出一個(gè)合理的結(jié)果；為了提高概率必須提高迭代次數(shù)。該算法最早由Fischler和Bolles于1981年提出。

光看文字還是太抽象了，我們?cè)儆脠D描述

RANSAC的基本假設(shè)是：
（1）數(shù)據(jù)由“局內(nèi)點(diǎn)”組成，例如：數(shù)據(jù)的分布可以用一些模型參數(shù)來(lái)解釋；
（2）“局外點(diǎn)”是不能適應(yīng)該模型的數(shù)據(jù)；
（3）除此之外的數(shù)據(jù)屬于噪聲。

而下圖二里面、藍(lán)色部分為局內(nèi)點(diǎn)，而紅色部分就是局外點(diǎn)，而這個(gè)算法要算出的就是藍(lán)色部分那個(gè)模型的參數(shù)

RANSAC算法的輸入是一組觀測(cè)數(shù)據(jù)，一個(gè)可以解釋或者適應(yīng)于觀測(cè)數(shù)據(jù)的參數(shù)化模型，一些可信的參數(shù)。

在上圖二中 左半部分灰色的點(diǎn)為觀測(cè)數(shù)據(jù)，一個(gè)可以解釋或者適應(yīng)于觀測(cè)數(shù)據(jù)的參數(shù)化模型 我們可以在這個(gè)圖定義為一條直線，如y=kx + b；

一些可信的參數(shù)指的就是指定的局內(nèi)點(diǎn)范圍。而k，和b就是我們需要用RANSAC算法求出來(lái)的

RANSAC通過(guò)反復(fù)選擇數(shù)據(jù)中的一組隨機(jī)子集來(lái)達(dá)成目標(biāo)。被選取的子集被假設(shè)為局內(nèi)點(diǎn)，并用下述方法進(jìn)行驗(yàn)證：

　　1.有一個(gè)模型適應(yīng)于假設(shè)的局內(nèi)點(diǎn)，即所有的未知參數(shù)都能從假設(shè)的局內(nèi)點(diǎn)計(jì)算得出。
　　2.用1中得到的模型去測(cè)試所有的其它數(shù)據(jù)，如果某個(gè)點(diǎn)適用于估計(jì)的模型，認(rèn)為它也是局內(nèi)點(diǎn)。
3.如果有足夠多的點(diǎn)被歸類為假設(shè)的局內(nèi)點(diǎn)，那么估計(jì)的模型就足夠合理。
4.然后，用所有假設(shè)的局內(nèi)點(diǎn)去重新估計(jì)模型，因?yàn)樗鼉H僅被初始的假設(shè)局內(nèi)點(diǎn)估計(jì)過(guò)。
5.最后，通過(guò)估計(jì)局內(nèi)點(diǎn)與模型的錯(cuò)誤率來(lái)評(píng)估模型。

這個(gè)過(guò)程被重復(fù)執(zhí)行固定的次數(shù)，每次產(chǎn)生的模型要么因?yàn)榫謨?nèi)點(diǎn)太少而被舍棄，要么因?yàn)楸痊F(xiàn)有的模型更好而被選用。

這個(gè)算法用圖二的例子說(shuō)明就是先隨機(jī)找到內(nèi)點(diǎn)，計(jì)算k1和b1，再用這個(gè)模型算其他內(nèi)點(diǎn)是不是也滿足y=k1x+b2，評(píng)估模型

再跟后面的兩個(gè)隨機(jī)的內(nèi)點(diǎn)算出來(lái)的k2和b2比較模型評(píng)估值，不停迭代最后找到最優(yōu)點(diǎn)

我再用圖一的模型說(shuō)明一下RANSAC算法

RANSAC算法的輸入是一組觀測(cè)數(shù)據(jù)，一個(gè)可以解釋或者適應(yīng)于觀測(cè)數(shù)據(jù)的參數(shù)化模型，一些可信的參數(shù)。

模型對(duì)應(yīng)的是空間中一個(gè)點(diǎn)云數(shù)據(jù)到另外一個(gè)點(diǎn)云數(shù)據(jù)的旋轉(zhuǎn)以及平移。