Review of Course Computer Vision Lecture 6:Line Detection

为期末考试复习做个准备。

总文章地址。

Lecture 6: Line Detection

不使用边缘检测的原因: 时间复杂度的影响，固定形状的检测 (尤其是线性) 的时间复杂度往往优于未知形状的检测。

Hough transform

Hough transform 可以检测所有已知方程的曲线，即解高次方程的参数 (本质上是坐标系的转换)，不过接下来我们主要讨论直线检测。

思路: 一个主要的想法就是坐标系的转换，考虑有一条直线是 $y=ax+b$，此时将 $(x,y)$ 坐标系转换成 $(a,b)$ 坐标系，即 $b=-ax+y$。那么若 $(x_i,y_i)$ 在 $y=ax+b$ 上，则在 $(a,b)$ 坐标系上，$(x,y)$ 对应的直线能经过 $(a,b)$ 这个点。

根据这个想法，我们能给出一个做法，即对所有 $(x_i,y_i)$，考虑在 $(a,b)$ 坐标系上求直线交点。

离散空间内求交点就是考虑将平面划分成若干个小正方形，求小正方形经过的次数。

然后将超过阈值的格点认为是直线，可以发现这样检测的时间复杂度是线性的。

另一种办法就是使用极坐标系，即
$$
x=\rho \cos\theta, y=\rho\sin\theta\implies x\cos\theta+y\sin\theta=\rho.
$$
转换成极坐标的好处在于统一了直线时 $a\to \infty$ 的情况，也就是 $x=p$ 这样的直线。

但转换成极坐标系 $(\theta,\rho)$ 后，不再是直线求交点，而是 $x_i\cos\theta+y_i\sin\theta=\rho$ 这样的曲线求交点，但不改变思路，仍然是数离散方格即可，此时 $\theta\in [0,2\pi]$，那么求交就是容易的了。

Hough transform 的优势如下：

1. 概念简单。
2. 实施方便。
3. 容易处理丢失和被遮掩的数据。
4. 可以解决所有固定曲线的问题，不仅仅是直线。

劣势如下：

1. 曲线参数变多时，计算变得复杂。
2. 每次只能检测一种固定曲线。
3. 由于每次检测的是直线，但实际上图像中很多时候都是线段，甚至有线段共线的情况，这些都无法检测。

RANSAC

RANSAC, Random Sample Consensus，随机采样一致算法。

RANSAC 做了几个基本的假设：

1. 模型数据由局内点 (inliers) 构成，比如模型是直线，局内点就是直线上的点。
2. 局外点 (outliers) 是不能适应该模型的数据。
3. 其余数据都是噪声。

局外点产生的原因有：噪声的极值；对数据的错误假设；测量的错误等。

我们要避免使用这些非局内点来构造模型，具体思路是反复迭代，步骤如下：

1. 随机选择一个初始数据集来当作模型的数据。
2. 通过数据集计算模型参数。
3. 计算其他数据与当前模型的距离并找到其他局内点。
4. 如果当前数据集足够大，计算当前模型内的误差大小，判断误差是否在可接受范围。
5. 重复上述若干轮。

始终保留足够大的数据集作为最终结果。

接下来我们拿该算法去求直线。

假定 $w$ 为局内点与总点数的比例，初始选择 $n$ 个点，迭代 $k$ 轮，则 $k$ 次采样中至少有一轮是正确的概率为 $1-(1-w^n)^k$。

具体实现中，$n$ 可以多次改变。

RANSAC 优势：

1. 通用，泛化，适合各种模型。
2. 容易计算正确的概率。

劣势：

1. 只能处理预先估计 $w$ 的情况的数据，不然算法成本太大。
2. 现实中 $w$ 可能非常小（可能需要选择随机子集来解决）。