2025-03-05
现在有一个 Line Detection 的目标，描绘出图像中的那些直线，例如车道线. 先前的 Edge Detection 有一定的噪声，并且像素点的表示是离散的，我们想更加具体地去得到一条 \(y=mx+b\) 的坐标表示.
对于已有的一列点，我们可以通过最小二乘法来做一个 Line Fitting，最小化 \(E=\sum (y_i-mx_i-b)^2\). 其中 \(y_i-mx_i-b\) 称为残余（residual），我们希望每个残余都比较小.
而我们对每个残余取 L2-Norm，加起来得到 Energy. 取不同的 Norm，我们改变了优化问题的 Energy Landscape. 考虑以 \(m,b,E\) 为三个维度，那确实就形成了一个地势图. 取不同的 Norm 我们要考虑是否最小的时候有一个解析解.
Matrix Cookbook：一个记录了大量矩阵微积分公式的开源文档.
但是最小二乘法对于离群点（Outlier）非常的敏感. 离群点会造成非常大的误差. 并且当线垂直的时候就完蛋了.
先解决第二个问题，用 \(ax+by-d=0\) 来表述一条线，残余就变成成了 \((ax_i+by_i-d)\). 也就是说变成了 \(\left(\begin{matrix}x_1\ y_1 \ 1 \\...\\ x_n\ y_n\ 1\end{matrix}\right)\left(\begin{matrix}a \\b\\d\end{matrix}\right)\). 但是你发现当后者等于 \((0\ 0\ 0)^T\) 的时候就直接变成 \(0\) 的平凡解，所以我们要添加一个限制. 比如 \(||h||=1\)（\(h=(a\ b\ d)^T\)）.
于是现在的问题是：在 \(||h||=1\) 的情况下，最小化 \(||Ah||\). 我 们发现实际上对 \(A\) 做 SVD 即可（见 高代笔记-SVD与广义逆）. 考虑 \(Av_i=\lambda_i v_i\)，我们选择最小的 \(\lambda_i\) 对应的单位向量，显然是最优的. 在矩阵的语言下，就是 \(A=UDV^T\)，取 \(V\) 的最后一列作为 \(v_i\).
现在要解决对于噪声的鲁棒性（Robustness）问题. L2-Norm 对于小的噪声的鲁棒性是很好的，但是 有 Outlier 就很恐怖了.
RANSAC: Random Sample Consensus. 用两个点形成一个假设线，因为这样最小化含有 Outlier 的概率. 然后设置一个阈值，统计与这条线距离超过阈值的点数. 找到 Outlier 数最少的（获得最多群众支持的）假设线. 然后再用这个假设线剔除掉 Outlier.
于是 RANSAC 的具体流程就是：随机选择最少的能确定直线/平面/...的点数，解出假设的方程. 计算 Inlier 的数量 ，若数量足够大，计算这个假设的 Least Square（作为 Tie Breaker）. 不断这么找即可. 而我们发现不同的假设之间没有先后关系，可以取并行化地检验.
RANSAC 的超参数：假设的数量，Outlier 的阈值.
RANSAC 的好处在于很 general 且很简单，但是缺点在于维度高的话，生成假设的代价太大，且 Outlier 一多就死了.
当 Outlier 多的时候，有另外一种方法叫 Hough Transform.
现在考虑将直线 \(y=mx+n\) 看成二维平面上的一个点. 那么原来的点 \((x,y)\) 就可以写成 \(y=mx+n\)，即 \(m=\frac{1}{x}(y-n)\) 的直线. 然后这些直线画出来然后做一点 Accumulation 和 Voting.比较粗略. 这个的一个好处在于对数量多一些的 Outlier 不那么敏感了. 但是鲁棒性不是很好.