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

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

（一） ICP算法（Iterative Closest Point迭代最近點）

ICP（Iterative Closest Point迭代最近點）算法是一種點集對點集配準方法，如下圖1

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

（圖1）

ICP是改進自對應(yīng)點集配準算法的

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

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

ICP算法是從源點云上的（PB）每個點 先計算出目標點云（PR）的每個點的距離，使每個點和目標云的最近點匹配，（記得這種映射方式叫滿射吧）

這樣滿足了對應(yīng)點集配準算法的前提條件、每個點都有了對應(yīng)的映射點，則可以按照對應(yīng)點集配準算法計算，但因為這個是假設(shè)，所以需要重復(fù)迭代運行上述過程，直到均方差誤差小于某個閥值。

也就是說 每次迭代，整個模型是靠近一點，每次都重新找最近點，然后再根據(jù)對應(yīng)點集批準算法算一次，比較均方差誤差，如果不滿足就繼續(xù)迭代

（二）RANSAC算法（RANdom SAmple Consensus隨機抽樣一致）

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

光看文字還是太抽象了，我們再用圖描述

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

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

（圖二）

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

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

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

RANSAC通過反復(fù)選擇數(shù)據(jù)中的一組隨機子集來達成目標。被選取的子集被假設(shè)為局內(nèi)點，并用下述方法進行驗證：

　　1.有一個模型適應(yīng)于假設(shè)的局內(nèi)點，即所有的未知參數(shù)都能從假設(shè)的局內(nèi)點計算得出。
　　2.用1中得到的模型去測試所有的其它數(shù)據(jù)，如果某個點適用于估計的模型，認為它也是局內(nèi)點。
     3.如果有足夠多的點被歸類為假設(shè)的局內(nèi)點，那么估計的模型就足夠合理。
     4.然后，用所有假設(shè)的局內(nèi)點去重新估計模型，因為它僅僅被初始的假設(shè)局內(nèi)點估計過。
     5.最后，通過估計局內(nèi)點與模型的錯誤率來評估模型。
這個過程被重復(fù)執(zhí)行固定的次數(shù)，每次產(chǎn)生的模型要么因為局內(nèi)點太少而被舍棄，要么因為比現(xiàn)有的模型更好而被選用。

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

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

我再用圖一的模型說明一下RANSAC算法

（圖1）

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

其中觀測數(shù)據(jù)就是PB，一個可以解釋或者適應(yīng)于觀測數(shù)據(jù)的參數(shù)化模型是 四元數(shù)旋轉(zhuǎn)，并平移