Review of Course Computer Vision Lecture 5:Edge Detection
为期末考试复习做个准备。
Lecture 5: Edge Detection
目标: 识别突然的变化。
产生原因: 物体表面的不连续，形状变化 (surface normal discontinuity), 物体与背景即深度的差异 (depth discontinuity), 表面颜色不连续 (surface color discontinuity), 光照强度不连续 (Illumination discontinuity).
检测思路: 求导，离散图像则改为差分。
离散求导的三种方式:
- Backward: $\frac{\mathrm{d}f}{\mathrm{d}x}=f(x)-f(x-1)$.
- Forward: $\frac{\mathrm{d}f}{\mathrm{d}x}=f(x+1)-f(x)$.
- Central: $\frac{\mathrm{d}f}{\mathrm{d}x}=\frac{f(x+1)-f(x-1)}{2}$.
可以类似地改写成求导向量的形式，如 $[1,0,-1]$ 等。
对于二维情况，只需要把求导向量改写成矩阵形式即可。
简单边缘检测器
边缘特征化: 边缘在像素密度函数突然变化的点。
边缘强度 (Edge Strength) 可以被梯度大小表示。
但检测存在噪声，我们很难简单地检测出边缘。
可以发现，从图中我们很明显可以发现边缘应该在大的那个转折点，但求导后却有若干个。解决办法是 smoothing 图像。
$g$ 为 $\sigma=50$ 的高斯滤波器，可以发现在与 $f$ 卷积后很好地去除了噪声的影响。
同时这里关于卷积有个小定理，即 $\frac{\partial}{\partial x}(f\ast g)=f\ast \frac{\partial g}{\partial x}$，所以实际上边缘检测可以等价于拿着求导过的高斯滤波器去卷积操作。
由此我们可以得到一些关于卷积核求导后的图像。
但过大的卷积核会严重模糊边缘，而过小的会让噪声影响较大。为了平衡二者，思路是使用多个 scales 去检测边缘。
另一种滤波器是考虑二阶导，即拉普拉斯滤波器。离散求二阶导使用类似 $[1,-2,1]$ 向量即可。而在用它作滤波器时，一般结合高斯滤波器，即设高斯函数为 $G$，我们就使用 $\nabla^2 G$ 作为滤波器来使用。此时检测边缘则是考虑二阶导为零，也就是 zero crossings。此时比一阶导更为精确，但同时更不便利。
设计一个合适的检测器需要以下三个条件: Good detection (the optimal detector must minimize the probability of false positives (detecting spurious edges caused by noise))，Good localization (the edges detected must be as close as possible to the true edges)，Single response (that is, minimize the number of local maxima around the true edge)。
Sobel edge detector
Sobel operator 是两个 $3\times 3$ 的核去执行卷积并近似得到导数，其本质是 smooth 和求导的结合。
$$
\mathbf{G}_x=\begin{pmatrix}+1 & 0 & -1\\ +2 & 0 & -2\\ +1 & 0 & -1\end{pmatrix}=\begin{pmatrix}1\\2\\1\end{pmatrix}\begin{pmatrix}+1 & 0 & -1 \end{pmatrix},\\
\mathbf{G}_y=\begin{pmatrix}+1 & +2 & +1\\ 0 & 0 & 0\\ -1 & -2 & -1\end{pmatrix}=\begin{pmatrix}1\\0\\-1\end{pmatrix}\begin{pmatrix}1 & 2 & 1 \end{pmatrix}.
$$
这样的操作减少了噪声的影响。
基于卷积的边缘检测缺点: Poor Localization (由于是相邻像素同时影响，导致很难接近最近的边)；只能维护垂直和水平，不容易察觉到斜边缘；没有充分利用边缘的梯度方向；最后输出的边缘二值图，只是简单地利用阈值进行处理，显然如果阈值过大，则会损失很多边缘信息；如果阈值过小，则会有很多噪声。
类似于 Sobel 的算子还有：
同时 Sobel 算子可以拓展得更大，利用二项式系数即可 (更改平滑算子，从 $(1,1)$ 到 $(1,2,1)$ 到 $(1,3,3,1),\cdots$，差分算子是 $n-2$ 阶系数的差分，即 $(1,-1)$ 到 $(1,0,-1)$ 到 $(1,1,-1,-1)$ 到 $(1,2,0,-2,-1),\cdots$)。
Canny edge detector
其特点是解决了基于卷积的几种边缘检测的缺点，大致步骤如下：
- Suppress Noise：利用某种卷积核 (如 Sobel 等) 来模糊图像以减少噪声的影响。
- Compute gradient magnitude and direction：利用 $\mathbf{G}_x$ 和 $\mathbf{G}_y$ 分别求出梯度后，再利用 $L=\sqrt{\mathbf{G}_x^2+\mathbf{G}_y^2}$ 以及 $\theta=\arctan(\frac{\mathbf{G}_y}{\mathbf{G}_x})$ 来算出梯度大小和方向。
- Apply Non-Maximum Suppression：非极大值抑制，对于每一个点，如果它的梯度大小不大于它梯度方向上相邻的两个点，则不认为这个点在边缘上。
- Use hysteresis and connectivity analysis to detect edges：设定两个阈值，分别称为高阈值和低阈值。以下规则来确定是否为边缘：若大于高阈值则被确认为阈值；若低于低阈值则被去除；否则只有这些点能按某一路径与确定边缘点相连时，才可以作为边缘点被接受，组成这一路径的所有点的边缘强度都比低阈值要大。大致思路就是延长边缘线，这样就能找出轮廓。
在 Canny 中，若使用高斯类卷积核，此时的参数 $\sigma$ 影响 (卷积核大小改变) 如下图。
