高级边缘检测

强度变化的原因

在计算机视觉中，边缘是图像中像素强度发生变化的地方。强度变化可能由以下原因引起：

  1. 几何事件

    • 表面方向（边界）不连续
    • 深度不连续
    • 颜色和纹理不连续

  2. 非几何事件

    • 照明变化
    • 镜面反射
    • 阴影
    • 互反射

边缘检测的目标

边缘检测的目标是从场景的图像中生成场景的线条“绘图”。

为什么边缘检测有用？

从图像的边缘中可以提取重要的特征（如角点、直线、曲线）。这些特征可用于更高级别的计算机视觉算法（如识别）。

边缘描述符（Edge Descriptors）

边缘描述符主要包括以下三个方面：

  1. 边缘方向（Edge direction）： 边缘方向是垂直于强度变化最大方向的方向，也就是边缘法线（edge normal）的方向。

  2. 边缘强度（Edge strength）： 边缘强度与沿法线方向的局部图像对比度相关。换句话说，边缘强度表示边缘的清晰度。

  3. 边缘位置（Edge position）： 边缘位置是边缘所处的图像位置。

因此，当我们进行边缘检测时，我们希望找到这些边缘，并了解它们的方向、强度及位置。

边缘检测的主要步骤

边缘检测通常包含以下四个步骤：

  1. 平滑（Smoothing）： 在不破坏真实边缘的情况下，尽可能地抑制噪声。这通常通过使用平滑滤波器（例如高斯滤波器）实现。

  2. 增强（Enhancement）： 应用差分（differentiation）来增强边缘质量（即锐化边缘）。增强可以突出边缘，使得它们更容易被检测。

  3. 阈值化（Thresholding）： 确定哪些边缘像素应该被视为噪声而丢弃，哪些应该保留。这可以通过设置阈值来实现，只有边缘幅度大于阈值的像素才会被保留。

  4. 定位（Localization）： 确定准确的边缘位置。对于某些应用，可能需要亚像素分辨率，以更好地估计边缘位置。亚像素分辨率意味着在像素之间估计边缘位置的精度要高于像素间距。

如何使用导数进行边缘检测

通常，在边缘检测中，我们可以通过以下两种方法之一来检测位于边缘上的点：

  1. 检测一阶导数的局部极大值或极小值。一阶导数的极值点通常对应于边缘的位置。
  2. 检测二阶导数的零交叉点。二阶导数的零交叉点也可以表示边缘位置。

然而，在实际应用中，我们需要注意噪声对导数的影响。噪声可能导致误判边缘位置。因此，在进行边缘检测之前，我们需要对图像进行平滑处理。

将平滑与差分结合进行边缘检测

在边缘检测中，我们通常先对图像进行平滑处理，然后再进行差分。这可以通过以下公式实现：

$$ \frac{\partial}{\partial x}(h * f) = \left(\frac{\partial}{\partial x} h\right) * f $$

这里：

  • $\frac{\partial}{\partial x}$ 表示对 x 轴方向求导数；
  • $h$ 是平滑算子（例如高斯核）；
  • $f$ 是输入图像；
  • $*$ 表示卷积操作。

这个公式的优点是它将平滑处理和求导合并成一个操作，从而减少了计算量。在实际应用中，我们可以先求平滑算子的导数（如高斯核的导数），然后将其与原始图像进行卷积以得到边缘梯度。

平滑处理和求导的合并是基于卷积运算的性质。卷积运算具有结合性（associativity）和分布性（distributivity）这两个关键性质，使得我们能够将平滑和求导合并为一个操作。

结合性意味着卷积运算可以按照任意顺序进行，不影响最终结果。换句话说：

$$ (a * b) * c = a * (b * c) $$

分布性意味着卷积运算可以分配到加法运算，即：

$$ a * (b + c) = (a * b) + (a * c) $$

给定这些性质，我们可以将平滑处理和求导合并为一个操作。从数学上讲，当我们对已进行平滑处理的图像求导时，可以先对平滑算子求导，然后再将结果与原始图像进行卷积。这是因为：

$$ \frac{\partial}{\partial x}(h * f) = \left(\frac{\partial}{\partial x} h\right) * f $$

在这个公式中，我们首先对平滑算子 $h$ 求导，然后将导数与原始图像 $f$ 进行卷积。这种方法可以减少计算量，使得边缘检测更加高效。

Prewitt 算子

Prewitt 算子是一种基于导数的边缘检测算子。它使用以下两个矩阵来分别计算图像在x轴和y轴方向的梯度：

1
2
3
4
5
6
7

M_x = [ -1  0  1
        -1  0  1
        -1  0  1 ]

M_y = [ -1 -1 -1
         0  0  0
         1  1  1 ]

Sobel 算子

Sobel 算子与 Prewitt 算子类似，但在计算梯度时更加注重中心像素。它使用以下两个矩阵来分别计算图像在x轴和y轴方向的梯度：

1
2
3
4
5
6
7

M_x = [ -1  0  1
        -2  0  2
        -1  0  1 ]

M_y = [ -1 -2 -1
         0  0  0
         1  2  1 ]

通过应用这些算子，我们可以得到边缘的梯度幅值和方向。

根据梯度幅值和方向实现边缘检测

整个过程分为以下几个步骤：

  1. 先对输入图像进行平滑处理（用高斯滤波器）：$\hat{f}(x, y) = f(x, y) * G(x, y)$
  2. 计算平滑后的图像在x轴方向的梯度：$\hat{f}_x = \hat{f}(x, y) * M_x(x, y) \rightarrow \frac{\partial f}{\partial x}$
  3. 计算平滑后的图像在y轴方向的梯度：$\hat{f}_y = \hat{f}(x, y) * M_y(x, y) \rightarrow \frac{\partial f}{\partial y}$
  4. 计算梯度幅值：$magn(x, y) = |\hat{f}_x| + |\hat{f}_y|$（这里我们采用近似计算，避免平方根运算的开销）
  5. 计算梯度方向：$dir(x, y) = \tan^{-1}(\hat{f}_y / \hat{f}_x)$
  6. 如果梯度幅值大于某个阈值（$magn(x, y) > T$），则认为该点可能是边缘点。

这样我们就可以得到图像中的边缘。

噪声抑制与定位之间的权衡（Noise suppression-localization tradeoff）

平滑处理取决于滤波器的尺寸（例如，对于高斯滤波器，取决于σ）。较大的滤波器尺寸会减少噪声，但会降低定位精度（即增加边缘位置的不确定性），反之亦然。

阈值选择（Choice of threshold）

阈值的选择对边缘检测结果具有显著影响。较低的阈值可能会导致虚假边缘被检测，而较高的阈值可能会导致真实边缘无法被检测到。

最优边缘检测的标准

在边缘检测中，我们通常关注以下三个方面：

  1. 好的检测（Good detection）：

    • 降低虚假正例（假边缘）的概率。
    • 降低虚假负例（漏检真实边缘）的概率。

  2. 好的定位（Good localization）：

    • 检测到的边缘必须尽可能接近真实边缘的位置。

  3. 单一响应（Single response）：

    • 在真实边缘周围，最小化局部极大值的数量。

Canny 边缘检测

Canny 边缘检测器是一种在计算机视觉中广泛使用的边缘检测算法。Canny 证明了高斯函数的一阶导数在最大化信噪比和定位精度的乘积方面具有很好的近似效果。

Canny 边缘检测的算法分为以下几个步骤：

计算图像的梯度（水平和垂直方向）：

  • 使用高斯函数的一阶导数与图像进行卷积，分别计算水平方向梯度（$f_x$）和垂直方向梯度（$f_y$）。

计算梯度幅值和方向：

  • 梯度幅值：$magn(x, y) = \sqrt{f_x^2 + f_y^2}$
  • 梯度方向：$dir(x, y) = \tan^{-1}(f_y / f_x)$

应用非极大值抑制（Non-maximum suppression）：

非极大值抑制的目的是消除边缘附近的多余响应，以得到较细的边缘。具体实现过程如下：

  1. 对于图像中的每个像素点 (i, j)，计算其梯度方向（已经在之前的步骤中计算出来）。根据梯度方向，我们可以判断出梯度最大值应该在该像素点的哪两个相邻像素点之间。例如，如果梯度方向接近水平，那么我们应该检查左侧和右侧的相邻像素点。

  2. 检查当前像素点的梯度幅值是否大于相邻像素点的梯度幅值。如果是，则继续下一步；否则，将当前像素点的梯度幅值设置为零（即抑制该像素点）。

  3. 如果当前像素点的梯度幅值大于相邻像素点的梯度幅值，那么我们认为它是局部极大值点，并保留其梯度幅值。

通过以上步骤，我们可以消除非极大值点，保留边缘上的主要部分，从而得到较细的边缘。这些细边缘将用于后续的双阈值法（Hysteresis thresholding）进一步筛选边缘像素。

应用双阈值法（Hysteresis thresholding）进行边缘连接：

  1. 使用两个阈值（一个低阈值和一个高阈值）对梯度幅值进行阈值化处理。
  2. 如果梯度幅值大于高阈值，则认为是明显的边缘。
  3. 如果梯度幅值处于低阈值和高阈值之间，则视为可能的边缘，但需根据其邻域上下文来判断（例如，如果邻近像素为明显的边缘，则将其视为边缘）
  4. 边缘连接（Edge Linking）是一种将图像中相邻的边缘片段连接起来形成完整边缘的方法。在边缘检测过程中，可能会出现一些不连续的边缘片段，而边缘连接的目的是将这些不连续的边缘片段连接起来，形成具有连续性的完整边缘。

在 Canny 边缘检测器中，边缘连接是通过双阈值法（Hysteresis thresholding）实现的。具体步骤如下：

  1. 使用两个阈值：一个低阈值和一个高阈值。
  2. 如果像素点的梯度幅值大于高阈值，则认为它是一个明显的边缘点。
  3. 如果像素点的梯度幅值在低阈值和高阈值之间，则需要根据相邻像素点的梯度幅值情况判断该像素点是否属于边缘。如果相邻像素点是明显的边缘点（即梯度幅值大于高阈值），则认为当前像素点也属于边缘，并将其与相邻的边缘点连接起来形成完整的边缘。

通过以上步骤，我们可以得到具有较强鲁棒性的边缘检测结果。

尺度不变特征变换（Scale Invariant Feature Transform - SIFT）。

SIFT 是一种广泛应用于计算机视觉领域的特征提取和匹配方法。我们已经学习到，边缘检测可以用来提取图像中的边缘特征，而 SIFT 则可以提取更复杂的局部特征，这些特征对于图像的尺度、旋转和亮度变化具有不变性。

尺度不变特征变换（SIFT）的主要步骤如下：

  1. 尺度空间极值检测（Scale-space extrema detection）
  2. 关键点定位（Keypoint localization）
  3. 方向分配（Orientation assignment）
  4. 关键点描述（Keypoint descriptor）

SIFT 特征提取的各个步骤

  1. 尺度空间极值检测（Scale-space extrema detection）：

    • 目标：检测具有尺度不变性的特征点。
    • 方法：使用高斯差分（Difference of Gaussian, 简称 DoG）金字塔在不同尺度空间中检测极值点。
    • DoG 金字塔是通过在不同尺度的高斯金字塔上进行相邻尺度之间的差分计算得到的。

  2. 关键点定位（Keypoint localization）：

    • 目标：在尺度空间中精确定位关键点。
    • 方法：利用二阶导数的零交叉点（对高斯差分函数进行泰勒展开）对关键点进行精确定位，并通过细微的尺度变化来移除不稳定的关键点。

  3. 方向分配（Orientation assignment）：

    • 目标：为每个关键点分配一个或多个主导方向，使特征具有旋转不变性。
    • 方法：计算关键点附近像素的梯度直方图，并选取直方图中最大值和次大值（大于最大值的80%）作为关键点的主导方向。

  4. 关键点描述（Keypoint descriptor）：

    • 目标：为每个关键点生成独特而具有区分性的特征描述符。
    • 方法：将关键点附近的像素区域分割成若干小区域，计算每个小区域内的梯度直方图，然后将这些直方图串联起来形成关键点的描述符。

为什么在计算机视觉任务中需要进行特征匹配

特征匹配在计算机视觉中的应用场景有很多，例如：

  1. 目标识别（Object recognition）：通过比较图像之间的匹配特征，可以识别出图像中的物体或场景。

  2. 宽基线匹配（Wide baseline matching）：在两幅具有较大视差的图像之间，通过估计基本矩阵（fundamental matrix）及匹配的关键点来进行宽基线匹配。

  3. 跟踪（Tracking）：在视频序列中，通过跟踪图像中的特征点来了解物体的运动轨迹。

如何实现各种不变性

我们希望特征具有以下不变性：

  1. 光照不变性（Illumination invariance）
  2. 尺度不变性（Scale invariance）
  3. 旋转不变性（Rotation invariance）
  4. 仿射不变性（Affine invariance）
  5. 完全透视不变性（Full perspective invariance）

下面详细讲解如何实现这些不变性：

光照不变性

实现光照不变性的方法有两种：

  1. 易于实现的方法：使用归一化处理，将特征向量除以其模长。

  2. 基于差值的方法（如 SIFT）：计算相邻像素间的差值，这样可以减小光照变化对特征的影响。

尺度不变性

尺度不变性是指我们希望特征在图像尺寸发生变化时仍然能被正确识别。为了实现这个目标，我们需要在不同尺度的图像上分别提取特征，并对比这些特征以找出相似的部分。这就是“在每个尺度的图像上运行过滤器”的意义。

  1. 金字塔（Pyramids）：

    • 将图像的宽度和高度分别除以2。
    • 每个像素取4个相邻像素的平均值（或高斯模糊）。
    • 不断重复这个过程，直到图像变得非常小。
    • 在每个尺度的图像上运行过滤器，希望结果具有鲁棒性。

  2. 尺度空间（如 SIFT 中的 DoG 方法）：

    • 使用高斯金字塔填补金字塔的间隙。
    • 类似线性缩放，但计算量更小。
    • 在这些图像的差分中提取特征。
    • 如果特征在 DoG 方法中重复出现，则认为该特征具有尺度不变性，我们应该保留它。

具体实现方法如下：

  1. 首先，创建一个图像金字塔（Pyramid）或尺度空间（Scale-space）。如之前所提，可以使用金字塔方法或 SIFT 中的 DoG 方法来实现。这个过程会生成一系列不同尺寸的图像。

  2. 然后，在每个尺寸的图像上运行特征提取算法（例如边缘检测、关键点检测等），以得到该尺寸下的特征。

  3. 最后，对比不同尺寸下提取到的特征。如果某个特征在多个尺度下都能被检测到，并且在这些尺度下的位置和方向相对稳定，那么我们可以认为这个特征具有尺度不变性。

通过这种方法，我们可以在不同尺度的图像上提取到具有尺度不变性的特征，这些特征对于图像匹配、目标识别等任务非常有用。

旋转不变性

旋转不变性指的是在图像旋转时，特征描述子仍然保持一致，从而能够正确匹配特征。在 SIFT 算法中，主要是通过下面的方式实现旋转不变性：

  1. 首先，我们需要为每个关键点分配一个或多个主导方向。在之前的步骤中，我们已经计算了关键点附近像素的梯度直方图，并选取直方图中最大值和次大值（大于最大值的80%）作为关键点的主导方向。

  2. 然后，我们将关键点的描述子相对于其主导方向进行旋转。这意味着，即使图像旋转，描述子中的信息也会相应旋转，从而保持一致。具体操作是，在计算关键点描述子时，将关键点附近的像素区域按照主导方向旋转，然后再计算旋转后的区域内的梯度直方图。

这样处理的目的是在图像旋转时，虽然关键点的主导方向发生了变化，但描述子也会随之旋转，使得描述子在旋转之前和之后仍然保持相似。这就实现了旋转不变性。

举个例子，假设我们在两幅图像中分别找到一个关键点，图像A的关键点主导方向朝右，图像B的关键点主导方向朝上。因为图像旋转，这两个关键点实际上是同一个关键点。在计算描述子时，我们分别根据这两个关键点的主导方向调整描述子的方向。这样，在比较两个描述子时，它们之间的差异会变小，从而能够正确匹配这两个关键点。

关键点描述子（Keypoint descriptor）

关键点描述子（Keypoint descriptor）是用来表示关键点周围区域特征的一个向量。它的目的是为了在不同图像中找到相似的关键点（即特征匹配）。

在 SIFT 算法中，关键点描述子是通过以下方式计算的：

  1. 首先，我们需要将关键点附近的像素区域分割成若干小区域。例如，将一个16x16像素的区域分割成16个4x4像素的小区域。

  2. 然后，我们计算每个小区域内的梯度直方图。梯度直方图是用来表示区域内各个方向梯度幅值的分布情况。在 SIFT 算法中，通常使用8个方向的梯度直方图。

  3. 接下来，我们将每个小区域的梯度直方图串联起来。例如，对于刚才提到的16个4x4像素的小区域，每个小区域有8个方向的梯度直方图，串联起来将得到一个128维的向量（16小区域 x 8方向 = 128维）。

这个128维的向量就是关键点的描述子。通过比较两个图像中关键点描述子之间的距离（例如欧氏距离），我们可以找到相似的关键点，从而实现特征匹配。

举个例子，比如我们在两幅图像中分别找到了一个关键点，这两个关键点周围的区域有相似的纹理结构。那么，这两个关键点的描述子向量可能非常接近。

Exercise Sheet

For edge detection using intensity images, we often approximate the gradient of the intensity using Masks.

(a) What is the advantage of Sobel operator over Roberts operator when used for edge detection? [4]

(a) The advantage of the Sobel operator over the Roberts operator when used for edge detection is that the Sobel operator is less sensitive to noise while still providing a good approximation of the gradient. Sobel operator calculates the gradient in both horizontal and vertical directions using 3x3 masks, which helps in smoothing the effect of noise, whereas the Roberts operator uses 2x2 masks and is more sensitive to noise. [4]

(b) Why are second order edge detectors better at finding edges than first order detectors?[2]

(b) Second-order edge detectors are better at finding edges than first-order detectors because they are less sensitive to noise and can identify edges more accurately. First-order detectors rely on gradient magnitude, whereas second-order detectors rely on the zero-crossing of the Laplacian, which provide more clear edge position. [2]

(c) Describe how the computational speed of applying a 2D Gaussian filter to an image raster can be improved.[2]

(c) The computational speed of applying a 2D Gaussian filter to an image raster can be improved by separating the 2D filter into two 1D filters (one horizontal and one vertical) and applying them sequentially. This reduces the number of computations, as the complexity goes from O(n^2) for a 2D filter to O(2n) for two 1D filters. [2]

(d) Convolve the Image Raster with the Mask shown below. You will only need to find the output corresponding to the sixteen highlighted central elements of the original image raster. [10]

Mask

1
2
3

1 2 1
0 0 0
-1 -2 -1

Image Raster

1
2
3
4
5
6

0 0 0 0 0 1
0 0 0 0 1 1
0 0 0 1 1 1
0 0 1 1 1 1
0 1 1 1 1 1
1 1 1 1 1 1

Highlighted Part

1
2
3
4

0 0 0 1
0 0 1 1
0 1 1 1
1 1 1 1

(d) To convolve the Image Raster with the Mask, we will perform the following calculations for the sixteen highlighted central elements of the original image raster:

New Image Raster (only the highlighted part is displayed):

1
2
3
4

0 -1 -3 -3
-1 -3 -3 -1
-3 -3 -1 0
-3 -1 0 0

(e) What feature in the image raster does this mask in part (d) detect? [2]

The mask in part (d) detects horizontal edges in the image raster. It is a Sobel operator, which calculates the gradient in the vertical direction and emphasizes the areas of rapid intensity change. This is because the mask computes the vertical gradient (vertical differences in intensity) while smoothing the result in the horizontal direction. [2]