爱华网最近几天一直在学习几何单元的分割和拟合。到今天算是有了点感受。
直线的拟合是几何基元的拟合基础部分。平常我们表示平面上一条直线用
y=ux+v
此时，u-v平面上每个点（u，v）都可以唯一对应一条x-y平面上的一条直线。
对于直线y=ux+v可以转换成v=y-ux，可见，这条直线上每个点都对应着u-v平面上的一条直线，这些直线会相交于（u，v）点，利用这个性质可以检测共线点。实际上，上述的变化被称为Hough变换。
对于实际的应用中，由于y=ux+v并不是能表示所有的直线（如u=∞时，x=c直线无法表示）。此时，有一种直线的黑塞范式
αr+βc+γ=0
令α²+β²=1（拉格朗日算子），则点（r，c）到该直线的举例可直接用αr+βc+γ得到。
通过一些列的点（ri，ci），i=1，……n来拟合一条直线，可以通过最小二乘法得到，即对这些点到直线的举例的平方和进行最小化。
ε²=∑（αr+βc+γ）²
约束条件（α²+β²=1）。
以上这种方法对于大的离群值不足够鲁棒。这里离群值就是指与正确拟合出来直线偏差很大的点，鲁棒指这个你和方法对这些允许偏差之外的可行性，比如如果拟合算法对离群值的影响可以见到最小甚至消除离群值的影响，此时算法的鲁棒性就好。而最小平方拟合对于大的离群值明显不够鲁棒，因为离群点对拟合直线的影响和一般点对拟合直线的影响是相同的，从而会引起拟合直线的不准确。为了减少这些远离点（离群点）的影响，可以为每个点引入权重ωi，最小化过程变为
ε²=∑ωi*（αr+βc+γ）²-λ*（α²+β²-1）*n
引入权重ωi之后，又有新的问题出现了，那就是怎么定义这权重呢？（每个点的权重该如何定义）。这里的解决方法是使用多次迭代。
用多次迭代来拟合直线，第一次迭代中使用权重ωi=1.，i=1，……n，即执行一个标准的直线拟合先拟合出一条近似直线，并通过此计算出点到线的距离δi。应用权重函数ω（δ）来定义后续的迭代权重。
权重函数也有很多种，最常用的有两种：Huber权重函数和Tukey权重函数。
权重函数就是定义削波值来定义那些点会被视为离群值，由此可以削弱离群值的权重。利用这种方法，迭代中的初始拟合直线仍然是标准的最小平方和拟合，给出的结果是被离群值干扰的，所以权重函数不仅会削弱离群值，也可能丢掉一些正常值。对此，还需要有其他的鲁棒拟合方法。RANSAC（therandom sampleconsensus）算法就是这样一组算法。
RANSAC算法的核心就是通过随机选择最少数量的点（直线为两点）来构造一个解（拟合），然后检查存在多少与此解相一致的点。如此不断重复，直到点的一致率达到一定的 值（如99%），选择一直点数量最大的解作为拟合结果。
通过对直线拟合的学习，圆和椭圆的拟合基本也是类似的思路。
以上基本就是直线拟合的基本思想，看到一些算法，特别记录下来。今后有点学习经验就打算写在博客里~
