RANSAC Fitting

54 阅读 0 评论 36 点赞

我是靠谱客的博主现实星月，最近开发中收集的这篇文章主要介绍RANSAC Fitting，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

本系列文章由 @YhL_Leo 出品，转载请注明出处。
文章链接： http://blog.csdn.net/yhl_leo/article/details/73294793

RANSAC 算法是一种常用的估计模型参数的方法，相关的算法介绍网上有很多，这里不再累述，主要介绍如何利用RANSAC 方法进行 2D 直线以及 3D 平面拟合。

Source code (python version): Github/yhlleo/RANSAC-fit

1 拟合模型

之所以要自己去实现算法，主要是由于可以直接使用的代码程序和函数库，对于直线以及平面方程一般使用：

lines: $y = ax + b$
planes: $z = ax + by + c$

这样不通用的表达方式，对于自然情景中的很多线性回归问题，一般没什么问题，但是对于一些简单的应用情景，比如本文提到的直线、平面拟合问题，就不具有绝对的通用性，比如斜率不存在的line : $x=n, nin mathbb{R}$ ，上述的直线方程就无法拟合，同理平面拟合也存在类似问题。因此，采用下面的方法更具有一般性：

lines: $ax + by + c = 0$
planes: $ax + by + cz + d = 0$

对于 2D 直线采用两点式方程，给定直线上任意不同两点 $mathbf{p}(x_1, y_1), mathbf{q}(x_2, y_2)$ ，则有：

y - y 1 y 2 - y 1 = x - x 1 x 2 - x 1

$frac{y - y_1}{y_2 - y_1} = frac{x - x_1}{x_2 - x_1}$

展开为点积式：

(y - y 1) (x 2 - x 1) = (x - x 1) (y 2 - y 1)

$(y - y_1)(x_2 - x_1) = (x - x_1)(y_2 - y_1)$

进而可以得到：

a = y 2 - y 1, b = x 1 - x 2, c = x 2 y 1 - x 1 y 2

$a = y_2 - y_1, b = x_1 - x_2, c = x_2 y_1 - x_1 y_2$

在对直线进行归一化处理：

a = a a 2 + b 2 - - - - - - \sqrt, b = b a 2 + b 2 - - - - - - \sqrt, c = c a 2 + b 2 - - - - - - \sqrt

$a = frac{a}{sqrt{a^2+b^2}}, b = frac{b}{sqrt{a^2+b^2}},c = frac{c}{sqrt{a^2+b^2}}$

同时，如果 $a neq 0$ ，令 $a > 0$ , 否则令 $b>0$ 。

3D 平面则采用三点式直线方程，给定平面上任意不共线的三点 ${mathbf{p}_i(x_i, y_i) , i=1, 2,3. }$ ，则有：

∣ ∣ ∣ ∣ ∣ x - x 1 x 2 - x 1 x 3 - x 1 y - y 1 y 2 - y 1 y 3 - y 1 z - z 1 z 2 - z 1 z 3 - z 1 ∣ ∣ ∣ ∣ ∣ = 0

$left| begin{matrix} x - x_1& y - y_1& z - z_1 \ x_2 - x_1& y_2 - y_1& z_2 - z_1 \ x_3 - x_1& y_3 - y_1& z_3 - z_1 \ end{matrix}right| = 0$

对等式左边行列式按照第一行，进行行展开可得：

(x - x 1) ∣ ∣ ∣ y 2 - y 1 y 3 - y 1 z 2 - z 1 z 3 - z 1 ∣ ∣ ∣ + (y - y 1) ∣ ∣ ∣ z 2 - z 1 z 3 - z 1 x 2 - z 1 x 3 - z 1 ∣ ∣ ∣ + (z - z 1) ∣ ∣ ∣ x 2 - z 1 x 3 - z 1 y 2 - y 1 y 3 - y 1 ∣ ∣ ∣ = 0

$(x - x_1)left| begin{matrix} y_2 - y_1& z_2 - z_1 \ y_3 - y_1& z_3 - z_1 \ end{matrix}right| + (y - y_1) left| begin{matrix} z_2 - z_1& x_2 - z_1 \ z_3 - z_1& x_3 - z_1 \ end{matrix}right| + (z - z_1) left| begin{matrix} x_2 - z_1& y_2 - y_1 \ x_3 - z_1& y_3 - y_1 \ end{matrix}right| = 0$

进而可得：

a = (y 2 - y 1) (z 3 - z 1) - (z 2 - z 1) (y 3 - y 1)

$a = (y_2-y_1)(z_3-z_1) - (z_2-z_1)(y_3-y_1)$

b = (z 2 - z 1) (x 3 - x 1) - (x 2 - x 1) (z 3 - z 1)

$b = (z_2-z_1)(x_3-x_1) - (x_2-x_1)(z_3-z_1)$

c = (x 2 - x 1) (y 3 - y 1) - (y 2 - y 1) (x 3 - x 1)

$c = (x_2-x_1)(y_3-y_1) - (y_2-y_1)(x_3-x_1)$

d = - a x 1 - b y 1 - c z 1

$d = -a x_1 - b y_1 - c z_1$

同样进行归一化处理：

a = a N, b = b N, c = c N, d = d N, N = a 2 + b 2 + c 2 - - - - - - - - - \sqrt

$a = frac{a}{mathcal{N}}, b =frac{b}{mathcal{N}}, c =frac{c}{mathcal{N}}, d =frac{d}{mathcal{N}}, mathcal{N} = sqrt{a^2 + b^2 + c^2}$

拟合过程中，判断inlier 和 outlier的判别函数，分别采用点到直线、平面的距离公式：

point to line: $d =| a x_0 + b y_0 + c |$
point to plane: $d = |a x_0 + b y_0 + c z_0 + d|$

注：因为对直线和平面都已经进行了归一化处理，所以计算距离部分的分母都略去。

迭代过程如图：

flowchart

2 优化拟合模型

通过简单的迭代获得的模型，可以满足inliers 数量最大，但是并不一定最优，可以根据inliers的特征值以及特征向量进行优化，这里把测试的结果图展示如下：

2d-line

2d-line2

3d-plane

3d-plane2

References:
- https://en.wikipedia.org/wiki/Random_sample_consensus
- Robust linear model estimation using RANSAC
- Performance Evaluation of RANSAC Family