cs131課程筆記（3）

07-06

cs131課程筆記（3）

Lecture_06 RANSAC 和Harris角點

1.RANSAC(RANdom Sample Consensus)演算法步驟：

循環：

1）隨機選取一組能確定模型的點並計算模型參數。

2）找到這個模型對應的內點（inliers）。

3）如果內點個數足夠大，重新計算所有點的最小二乘誤差。

4）保留最大內點模型

簡單說RANSAC就是隨機取點擬合模型，然後取與模型相近點數最多的那個模型。

2.假設內點個數佔總點數個數的比例是 $w$ ，模型需要 $n$ 個點去確定（比如直線需要2個點），一共採樣 $k$ 次。則採樣一次的 $n$ 個點都是內點的概率為 $w^n$ （這時模型擬合的結果一定是正確的），採樣 $k$ 次每次都採樣到離群點的概率為 $left(1-w^n ight)^k$ ，要求採樣 $k$ 次後採樣到正確模型的概率為 $p$ ，則 $left(1-w^n ight)^k<1-p$ ， $k>frac{ln(1-p)}{ln(1-w^n)}$

例如，擬合一條二次曲線，每次採樣需要3個點，離群點比例為 $50\%$ 。要求採樣 $k$ 次後正確概率大於 $99\%$ ，則 $left(1-w^n ight)^k<0.01$ ， $k>35$ 。

3.初始的擬合將數據分為內點和離群點，改進初始的擬合辦法為用最小二乘再次擬合所有的內點，然後將內點離群點重新分類後再次擬合。重複這個過程。

4.RANSAC的優點：適用性廣；實現簡單。缺點：對離群點比例有要求，不能太高，但實際問題總是有很高的離群點比例。

解決辦法：霍夫變換可以結果高比例離群點的問題。

5.局部特徵可以增加以下幾點的魯棒性：1）遮擋，2）關節，3）類內變換。

6.提取的特徵需要1）準確且可以重複（對平移旋轉尺度變化不變，對放射變換魯棒，對光照變化，雜訊，模糊，量化魯棒）2）局部性，這樣可以不怕遮擋和位置變換（clutter）3）數目要有保證，4）獨特性，5）高效。

7.現存的特徵檢測器：

8.角點是可重複的並且獨特的（有明顯梯度變化），並且沿任意方向平移角點所在的窗口會造成像素強度發生較大變化。

9.Harris角點檢測器： $E(u,v)=sum_{x,y}w(x,y)left[ I(x+u,y+v)-I(x,y) ight]^2$ ， $w(x,y)$ 為1或者高斯窗。

$egin{equation} egin{aligned} sumleft[ I(x+u,y+v)-I(x,y) ight]^2&=sumleft[ I(x,y)+uI_x(x,y)+vI_y(x,y)-I(x,y) ight]^2\ &={sum}u^2I^2_x+2uvI_xI_y+v^2I^2_y\ &={sum}egin{pmatrix}u&vend{pmatrix}egin{pmatrix}I^2_x&I_xI_y\I_xI_y&I^2_yend{pmatrix}egin{pmatrix}u\vend{pmatrix}\ &=egin{pmatrix}u&vend{pmatrix}{sum}egin{pmatrix}I^2_x&I_xI_y\I_xI_y&I^2_yend{pmatrix}egin{pmatrix}u\vend{pmatrix}\ &=egin{pmatrix}u&vend{pmatrix}Megin{pmatrix}u\vend{pmatrix} end{aligned} end{equation}$