CV Note 4 - Motion and Hough Transform Basics

动态视觉（Motion）

动态视觉主要关注摄像头和物体的运动。在这方面，有四种可能的组合：

1. 静止的摄像头，静止的物体
2. 静止的摄像头，运动的物体
3. 运动的摄像头，静止的物体
4. 运动的摄像头，运动的物体

在计算机视觉中，我们需要检测图像中发生的变化和引起这些变化的物体的运动。这需要使用一些技术，例如边界检测、运动估计和光流计算等。

现在，我们将讨论如何检测图像中的变化。我们可以通过测量图像在不同时间点的像素强度来确定图像发生变化的位置。但是，由于图像中的噪声，我们需要考虑更为稳健的方法来检测这些变化。

为了消除噪声，我们可以使用 4 或 8 连通性的概念。两个像素是 4 邻居，如果它们共享一个公共边界；两个像素是 8 邻居，如果它们至少共享一个公共角。我们可以基于这些概念来确定像素是否属于更大的结构，从而消除噪声。

公共角

共享一个公共角是指两个像素通过一个角点相互连接，即它们在对角线方向上相邻。在之前的 3x3 像素网格的例子中，像素 E 和像素 A 共享一个公共角。

1
2
3

A B C
D E F
G H I

4 或 8 连通性（4 or 8 Connectedness）

4 连通性和 8 连通性是图像处理领域中定义像素之间连接关系的概念，它们主要用于描述邻近像素的相互关系。

1. 4 连通性：两个像素是 4 邻居，如果它们共享一个公共边界。也就是说，它们垂直或水平方向上相邻。以下是一个示例：

1
2
3

A B C
D E F
G H I

在这个 3x3 的像素网格中，像素 E 的 4 邻居是 B、D、F 和 H。它们在垂直或水平方向上紧挨着 E。

2. 8 连通性：两个像素是 8 邻居，如果它们至少共享一个公共角。也就是说，它们可以是垂直、水平或对角方向上相邻。在同样的 3x3 像素网格中：

1
2
3

A B C
D E F
G H I

像素 E 的 8 邻居包括了 4 邻居 B、D、F 和 H，还包括了对角方向上的邻居 A、C、G 和 I。

我们可以根据 4 连通性和 8 连通性的定义，将像素分组为连通分量，以消除噪声、检测物体边界等。

4 连通性和 8 连通性在过滤噪声方面的作用

在图像处理中，噪声通常是指图像中因拍摄设备、传感器或压缩等外部因素引入的随机像素值波动。噪声像素通常与其邻近像素没有明显的相似性和连接关系，因此它们在图像中往往是孤立的或局部分布的。我们可以利用 4 连通性和 8 连通性来找出那些与周围像素存在较强连接关系的像素区域，从而消除孤立的噪声点。

具体操作步骤如下：

1. 首先，使用某种方法（如差分）来检测图像中的变化区域。
2. 然后，通过 4 连通性或 8 连通性寻找那些具有较强连接关系的像素区域。这些区域很可能是真实物体的边界或轮廓，因为它们的像素之间存在紧密的连接。
3. 对于那些没有紧密连接关系的像素点，将它们视为噪声，并从图像中移除。

光圈问题（Aperture Problem）

光圈问题（Aperture Problem）是运动估计和光流计算中遇到的一个挑战。它源于局部运动信息不足以确定物体的完全运动。换句话说，当我们只观察图像的一个局部区域时，我们无法准确地推断出物体在这个区域内的真实运动。

让我们举一个光圈问题的例子。假设我们有一个在摄像头视野内移动的图像纹理（例如，一个带有垂直黑白线条的矩形）。当我们观察局部的线条时，我们可以看到线条在水平方向上移动，但我们无法确定线条在垂直方向的移动情况。这是因为在这个局部区域内，我们只能观察到水平方向的运动信息，而垂直方向的运动信息被丢失了。

在上面的例子中，我们提到了一个带有垂直黑白线条的矩形移动的场景。

当我们只关注局部区域（如一个小窗口）时，窗口内的线条在水平方向上的移动是明显的，因为我们可以观察到黑白线条之间的相对位置发生了变化。然而，在这个局部区域内，我们无法观察到线条在垂直方向上的移动，因为在垂直方向上，线条的排列和间距是均匀的，如果矩形沿着垂直方向移动，黑白线条的相对位置在局部区域内看起来仍然保持不变。

这就是光圈问题所描述的现象。由于我们仅观察局部区域，导致我们无法准确地获取物体在所有方向上的运动信息。在这个例子中，我们可以观察到水平方向的运动信息，但垂直方向的运动信息被丢失了。

为了解决光圈问题，我们可以采取以下一些方法：

1. 使用更大的区域来观察物体运动。这样，我们可以获得更多的局部运动信息，从而更好地推断物体的真实运动。
2. 使用全局约束或先验知识。我们可以根据物体的运动特性或场景结构，引入全局约束或先验知识来帮助确定物体的运动。
3. 提取特征点并进行匹配。通过提取图像中的特征点（如角点），并将它们在不同时间点的图像中进行匹配，我们可以估计这些特征点的运动，从而获得物体的运动信息，也就是Motion Correspondence中提到的方法，比如角点检测器（Corner Detector）或 Moravec 操作符（Moravec Operator）。

运动的对应关系（Motion Correspondence）

在计算机视觉中，我们需要估计物体在图像中的运动。为了实现这一目标，我们可以从两张不同时间点的图像中提取特征点，然后将这些特征点进行匹配。特征点是图像中具有较高局部变化性的点，它们在不同视角和光照条件下仍然相对容易识别。

为了提取特征点，我们可以使用一些特征检测算法，如角点检测器（Corner Detector）或 Moravec 操作符（Moravec Operator）。这些算法能够找到图像中的角点或其他对应点，然后我们可以使用这些点来估计物体的运动。

运动对应关系的主要步骤如下：

1. 在每张图像中提取感兴趣点（Interest Points）。
2. 将第一张图像中的每个特征点与第二张图像中一定距离范围内的所有特征点进行配对。
3. 对于每个可能的匹配，计算两个特征点之间的相似度。
4. 根据相似度计算每个匹配的可能性。
5. 根据附近匹配的情况，调整每个点的匹配概率。

运动对应关系的匹配过程主要遵循以下三个原则：

1. 离散性（Discreteness）：衡量单个点的独特性。
2. 相似性（Similarity）：衡量两个点之间的相似程度。
3. 一致性（Consistency）：衡量一个匹配与附近匹配之间的一致性。

Moravec 操作符（Moravec Operator）

Moravec 操作符（Moravec Operator）是一种角点检测算法，用于在图像中找到感兴趣的特征点。该操作符的主要思想是在图像中找到在各个方向上都具有较大强度变化的点，这样的点通常位于角点处。Moravec 操作符可能对孤立像素点也非常敏感，可能将它们误判为角点。

Moravec 操作符的具体操作步骤如下：

1. 在图像上选择一个点（例如，坐标为 (x, y) 的像素点）。
2. 放置一个小方形窗口（通常是 3x3、5x5 或 7x7 像素大小）以包含此点。窗口中心为当前像素点。
3. 将该窗口在八个主要方向（水平、垂直和四个对角线方向）上分别平移一个像素。
4. 计算窗口内各个像素的强度变化，即原始窗口与平移后窗口像素值之差的平方和。
5. 对于每个方向，将强度变化求和。然后取这八个方向上的最小值作为当前点（x, y）的 Moravec 响应值。

重复上述步骤以计算图像中每个点的 Moravec 响应值。接下来，我们可以通过以下步骤筛选出感兴趣的特征点：

1. 在 Moravec 响应值矩阵中找到局部最大值，也就是在其邻域内具有最大响应值的点。
2. 根据阈值将这些局部最大值作为特征点。

以下是一个简单的例子：

假设我们有一个简单的 5x5 像素图像，我们想要找到图像中的角点。使用 Moravec 操作符和 3x3 窗口，我们可以计算每个点的响应值，并找到局部最大值。然后我们可以根据阈值筛选出角点。

计算相似度（Calculating the degree of similarity）

为了计算两个图像中对应特征点之间的相似度，我们需要测量它们在像素值上的差异。给定第一张图像中的一个特征区域 i(t) 和第二张图像中的一个特征区域 j(t+1)，我们可以计算它们之间的相似度 sij。计算方法是将两个区域内像素值的差异求和。

在这个过程中，我们关注两幅图像的特征区域 i(t) 和 j(t+1)，我们希望建立这两个区域之间的对应关系。

1. 计算相似度

首先，我们要计算两个区域之间的相似度。相似度衡量了这两个区域在像素值上的差异。这可以通过计算两个区域内像素值的差异之和来实现。

设区域 i(t) 和 j(t+1) 分别有 M 个像素，其中 i(t) 的像素值用 $I_i$ 表示，j(t+1) 的像素值用 $J_j$ 表示。两个区域之间的相似度 sij 可以计算为：

$s_{ij} = \sum_{m=1}^{M} (I_{i,m} - J_{j,m})^2$

其中，$I_{i,m}$ 是区域 i(t) 中第 m 个像素的值，$J_{j,m}$ 是区域 j(t+1) 中第 m 个像素的值。

2. 计算权重

接下来，我们需要计算所有可能匹配的权重。权重由相似度 sij 和一个调节参数 α 决定。

$w_{ij} = \frac{1}{1 + \alpha s_{ij}}$

α 是一个调节权重与相似度之间关系的参数。这个参数可以根据实际情况进行调整，以控制相似度对权重的影响。

3. 计算匹配可能性

现在我们已经得到了所有可能匹配的权重，接下来我们需要将这些权重转换为匹配的概率分布。为了实现这一点，我们首先计算所有权重的总和：

$W_{total} = \sum_{k} w_{ik}$

然后，我们可以计算每个匹配的概率：

$p_{ij} = \frac{w_{ij}}{W_{total}}$

这样，我们得到了一个概率分布，反映了不同匹配的可能性。

4. 调整匹配可能性

在计算出初始匹配概率后，我们需要根据附近特征点的匹配概率对当前特征点的匹配概率进行调整。这可以通过将当前特征点的概率与其邻居特征点的概率进行加权平均或其他方法来实现。这一步骤有助于使结果更具一致性，从而提高运动估计的准确性。

根据上述步骤，我们可以计算出两幅图像中特征点之间的匹配概率。这些概率有助于我们找到图像中对应特征点的最佳匹配，进而估计物体的运动。

好的，让我们通过一个简单的例子来说明整个计算过程。假设我们有两幅图像，图片1和图片2。在这两幅图像中，我们选取了两个特征区域 i(t) 和 j(t+1)。为了简化计算过程，我们的特征区域只包含 4 个像素。

图片1中的特征区域i(t)像素值如下：

1

I1 = 10, I2 = 25, I3 = 50, I4 = 30

图片2中的特征区域j(t+1)像素值如下：

1

J1 = 11, J2 = 23, J3 = 52, J4 = 28

举例说明

假设我们有两幅图像：图像1和图像2。我们从两幅图像中各选取了一个特征区域：i(t) 来自图像1，j(t+1) 来自图像2。为了简化计算过程，我们的特征区域只包含 4 个像素。特征区域 i(t) 和 j(t+1) 的像素值如下：

图像1中的特征区域 i(t) 像素值：

1
2
3
4

I1 = 10
I2 = 25
I3 = 50
I4 = 30

图像2中的特征区域 j(t+1) 像素值：

1
2
3
4

J1 = 11
J2 = 23
J3 = 52
J4 = 28

步骤1: 计算相似度

我们将计算两个特征区域之间的相似度。相似度衡量了两个区域在像素值上的差异。采用之前提到的公式，我们有：

$s_{ij} = \sum_{m=1}^{4} (I_{i,m} - J_{j,m})^2$

将 i(t) 和 j(t+1) 的像素值代入公式中，我们得到：

$s_{ij} = (10 - 11)^2 + (25 - 23)^2 + (50 - 52)^2 + (30 - 28)^2 = 1 + 4 + 4 + 4 = 13$

步骤2: 计算权重

接下来，我们需要计算权重。假设调节参数 α = 0.5，我们有：

$w_{ij} = \frac{1}{1 + 0.5 \times 13} = \frac{1}{1 + 6.5} = \frac{1}{7.5}$

权重是一个衡量特征区域之间相似性的值。权重值越大，相似度越高。

计算权重的意义一以及参数赋值规范

直接使用步骤1中的相似度值 sij 也可以衡量特征区域之间的相似性。但是，使用权重 w_ij 有两个优点：

1. 调整参数：权重计算中使用了一个调节参数α，这个参数可以根据实际情况进行调整，以控制相似度对权重的影响。这使得我们可以根据具体场景和应用来优化匹配结果。

2. 归一化：权重的计算将相似度值转换为一个介于0和1之间的数值，这有助于后续计算匹配概率时进行归一化处理，从而使得匹配概率的结果更具可比性。

所以，计算权重可以提高特征点匹配的准确性和可比性。α参数应该在相同的比较里保持一致，从而确保存在可比性。

步骤3: 计算匹配可能性（Match Likelihood）

我们假设只有两个可能的匹配。权重分别为：

1
2

w1 = 1 / 7.5
w2 = 1 / (1 + 0.5 * 5) = 1 / 3.5

当然，在这里w2的值是一个编造的值，实际上应该重复第一步的计算。然后，我们计算所有权重的总和，目的是将所有的权重归一化，从而便于比较：

$W_{total} = 1/7.5 + 1/3.5 = 0.4$

然后，我们计算每个匹配的概率，判断哪个 j(t+1) 区域和特征区域 i(t) 相似度最高：

$p_1 = \frac{w_1}{W_{total}} = \frac{1/7.5}{0.4} = 0.2/0.4 = 0.5$ $p_2 = \frac{w_2}{W_{total}} = \frac{1/3.5}{0.4} = 0.2/0.4 = 0.5$

概率表示不同匹配的可能性，概率越高，匹配越可能。基于此，我们可以建立对应关系，估计物体的运动。

匹配的定义

匹配的意思是所有可能的特征区域，比如刚刚j(t+1)是一个匹配，在实际应用中，我们需要在图像2中搜索与图像1中特征区域 i(t) 相似的多个区域，并计算它们的权重和匹配概率。

4. 调整匹配可能性（Adjusting Probabilities）

这个例子我们假设没有邻居特征点，因此不需要对匹配概率进行调整。实际上，附近的特征点通常具有相似的运动，因为它们可能属于同一个物体或者处于相似的深度。因此，考虑邻居特征点的匹配概率对当前特征点的匹配概率进行调整，有助于提高特征点匹配和运动估计的准确性。

对于这个例子来说，最终的匹配概率如下：

1
2

p1 = 0.5
p2 = 0.5

在这个例子中，特征区域 i(t) 和 j(t+1) 之间的匹配概率是相等的。

调整匹配可能性的实际应用

假设在两幅连续的图像中（图像1和图像2），我们正在分析一个特征点 A。为了估计特征点 A 在图像2中的运动，我们需要找到其对应的匹配点 A’。同时，特征点 A 在图像1中还有一些邻居特征点，如 B、C、D 等。这些邻居特征点同样在图像2中具有对应的匹配点 B’、C’、D’ 等。

在理想情况下，物体的运动应该是连续且平滑的，所以特征点 A 及其邻居特征点 B、C、D 在图像2中的运动可能相似。因此，我们可以利用这些邻居特征点的匹配概率来调整特征点 A 的匹配概率。

以特征点 A 为例，假设我们已经计算了各个匹配概率。然后，我们观察邻居特征点 B、C、D 的匹配概率分布。如果它们的匹配概率与 A 的匹配概率具有相似的分布，这表明我们找到的匹配点可能是正确的。否则，我们可能需要重新检查 A 的匹配概率并进行调整，以使其更接近邻居特征点的匹配概率分布。

通过将特征点 A 的匹配概率与邻居特征点的匹配概率进行加权平均或其他方法进行调整，我们可以使结果更具一致性，从而提高运动估计的准确性。

霍夫变换（Hough Transform）

空间中的点

1.1 笛卡尔坐标系（Cartesian Coordinate System）与极坐标系（Polar Coordinate System）

在二维平面上，我们有两种常见的坐标系来描述一个点的位置：笛卡尔坐标系和极坐标系。

• 笛卡尔坐标系：每个点的位置由其与横轴（x 轴）和纵轴（y 轴）的距离表示。例如，点 P(3, 4) 表示一个点，其横坐标为 3，纵坐标为 4。

• 极坐标系：每个点的位置由其与原点（极点）的距离（ρ）和与水平轴（x 轴）的夹角（θ）表示。例如，点 P’(5, 60°) 表示一个点，其与原点的距离为 5，与 x 轴的夹角为 60°。

1.2 从笛卡尔坐标系到极坐标系的转换

对于一个给定的点，我们可以通过以下公式将其从笛卡尔坐标系转换为极坐标系：

ρ = √(x² + y²) θ = arctan(y/x)

例如，对于点 P(3, 4)，我们可以计算其极坐标为 P’(5, arctan(4/3))，约为 P’(5, 53.13°)。

空间中的直线

2.1 如何确定一条直线

在二维平面上，我们通常使用斜率和截距的形式（y = mx + b）来表示一条直线。但是，在极坐标系中，我们使用距离（ρ）和夹角（θ）来表示直线。在极坐标系中，同一条直线的表示形式为：

ρ = x * cos(θ) + y * sin(θ)

其中，ρ 是直线到原点的距离，θ 是直线与 x 轴的夹角。

2.2 极坐标系中表示直线的参数

在极坐标系中，我们可以通过参数空间（ρ, θ）来表示直线。参数空间是一个二维平面，其中每个点（ρ, θ）都对应于原始图像中的一条直线。例如，在参数空间中，点 (10, 45°) 对应于原始图像中到原点距离为 10 且与 x 轴夹角为 45° 的直线。

霍夫变换的基本概念

3.1 参数空间（Parameter Space）

参数空间是一个二维平面，用于表示直线的参数。在霍夫变换中，我们将图像中的点从笛卡尔坐标系转换到参数空间。在参数空间中，每个点（ρ, θ）对应于原始图像中的一条直线，这条直线与原点的距离为ρ，与 x 轴的夹角为θ。

3.2 从图像空间到参数空间的映射

霍夫变换的过程中，我们要将图像中的点从笛卡尔坐标系映射到参数空间。对于图像中的每个非零像素点（即边缘点），我们将其从笛卡尔坐标系转换为极坐标系。然后，在参数空间中累积每个点的极坐标值。

霍夫变换的具体步骤

4.1 边缘检测

首先，我们需要对图像进行边缘检测，以找到图像中可能存在的直线。常用的边缘检测方法有 Canny 边缘检测、Sobel 操作符等。边缘检测的结果是一个二值化的图像，其中非零像素点表示边缘。

4.2 极坐标转换

接下来，我们需要将边缘图像中的每个非零像素点（即边缘点）从笛卡尔坐标系转换为极坐标系。这里我们使用以下公式进行转换：

ρ = x * cos(θ) + y * sin(θ)

对每个边缘点计算所有可能的θ值，相应地得到ρ值。

4.3 构建参数空间

在构建参数空间时，我们需要创建一个二维数组（矩阵），其中行表示不同的角度（θ），列表示不同的距离（ρ）。将矩阵的所有元素初始化为零。

4.4 累积投票

在霍夫变换中，投票（Voting）的过程是将边缘点从原始图像（笛卡尔坐标系）映射到霍夫空间（ρ, θ）。对于每个边缘点（x, y），我们计算所有可能的θ值，然后得到相应的ρ值。接下来，我们在参数空间（ρ, θ）的相应位置增加计数。投票的意义在于，多个边缘点共同投票来支持一条直线。当很多边缘点在同一个（ρ, θ）位置上累积投票时，意味着原始图像中可能存在一条通过这些点的直线。

4.5 阈值筛选与结果提取

在投票完成后，我们会得到一个参数空间（ρ, θ）的计数矩阵。在这个矩阵中，较高的计数值表示更多的边缘点支持此位置对应的直线。

根据阈值找到参数空间中的局部最大值，意味着在参数空间中寻找那些计数值大于或等于阈值的点。这些点对应于原始图像中可能存在的直线。

每个边缘点都有一组（ρ, θ）参数。但要注意，每个边缘点可以对应多组（ρ, θ）参数，因为有许多不同角度的直线可以通过同一个点。这也是为什么我们对每个边缘点计算所有可能的θ值，然后得到相应的ρ值。

现在，让我们回顾一下投票的过程和意义：

当我们在参数空间中为每个边缘点的（ρ, θ）组合投票时，意味着我们在累积支持某条直线的证据。如果很多边缘点对同一个（ρ, θ）位置累积投票，那么这意味着原始图像中可能存在一条通过这些点的直线，因为这些边缘点共同支持了（ρ, θ）所代表的直线。

在霍夫变换中，投票的目的是找出哪些直线参数（ρ, θ）得到了足够多的支持。当投票完成后，我们会在参数空间中寻找局部最大值，这些局部最大值表示原始图像中可能存在的直线。

映射回笛卡尔坐标系，得到直线在原始图像中的表示，是指我们需要将参数空间中的局部最大值（ρ, θ）转换回原始图像中的直线方程。具体地说，我们可以使用以下公式将极坐标系下的参数（ρ, θ）转换为笛卡尔坐标系下的直线方程：

x * cos(θ) + y * sin(θ) = ρ

这个方程表示原始图像中通过边缘点的直线。

霍夫变换的应用

霍夫变换不仅可以检测直线，还可以扩展到检测其他几何形状，如圆和椭圆。下面是一些常见的应用：

5.1 直线检测

利用霍夫变换检测直线是最基本的应用。我们已经讨论了如何将图像中的点从笛卡尔坐标系转换到参数空间（ρ, θ），以及如何在参数空间中进行投票以找到可能存在的直线。这种方法在很多计算机视觉任务中都非常有用，例如车道线检测、建筑物轮廓提取等。对于直线变换，我们需要压制非局部的最大值。单个线段没有被隔离。

5.2 圆检测

霍夫变换也可以用于检测圆。在这种情况下，参数空间不再是二维的（ρ, θ），而是三维的（a, b, r），其中 a 和 b 分别是圆心的 x 和 y 坐标，r 是圆的半径。对于图像中的每个边缘点，我们计算所有可能的圆心和半径，并在参数空间中进行投票。与直线检测类似，我们根据阈值筛选局部最大值，并将其映射回原始图像以提取圆。

5.3 椭圆检测

霍夫变换还可以扩展到检测椭圆。在这种情况下，参数空间是五维的（a, b, r1, r2, θ），其中 a 和 b 是椭圆中心的 x 和 y 坐标，r1 和 r2 分别是椭圆的长半轴和短半轴，θ 是椭圆的旋转角度。与直线和圆检测类似，我们在参数空间中进行投票，根据阈值筛选局部最大值，并将其映射回原始图像以提取椭圆。

5.4 其他形状检测

霍夫变换原理可以进一步扩展到检测其他几何形状，如多边形、曲线等。对于这些形状，我们需要定义适当的参数空间以表示其特征，然后进行投票和局部最大值筛选。但针对某些特定的形状或者纹理，霍夫变换依然无法适用。但霍夫变换可以让边缘变为单条线，这对优化图像边缘也是有益处的。

霍夫空间（Hough Space）

霍夫空间（Hough Space）是用于表示几何形状参数的多维空间。在霍夫变换中，我们将图像中的点（例如边缘点）从笛卡尔坐标系映射到霍夫空间。在霍夫空间中，每个点对应于原始图像中的一个几何形状（如直线、圆等）。

不同的几何形状对应的霍夫空间是不同的：

对于直线检测，霍夫空间是二维的，参数为（ρ, θ），其中ρ是直线到原点的距离，θ是直线与x轴的夹角。 对于圆检测，霍夫空间是三维的，参数为（a, b, r），其中a和b分别是圆心的x和y坐标，r是圆的半径。 对于椭圆检测，霍夫空间是五维的，参数为（a, b, r1, r2, θ），其中a和b是椭圆中心的x和y坐标，r1和r2分别是椭圆的长半轴和短半轴，θ是椭圆的旋转角度。 在霍夫变换的过程中，我们会在霍夫空间中累积投票以找到可能存在的几何形状。计算投票时，我们会对每个图像中的点计算其在霍夫空间的参数，并在相应的位置增加计数。

累积投票过程中所提到的参数空间就是霍夫空间。在霍夫变换中，我们将图像中的点从笛卡尔坐标系映射到霍夫空间（即参数空间），以便在该空间中累积投票以找到可能存在的几何形状。

霍夫空间的维度取决于我们要检测的几何形状。如前面所述，对于直线检测，霍夫空间是二维的（ρ, θ）；对于圆检测，霍夫空间是三维的（a, b, r）；对于椭圆检测，霍夫空间是五维的（a, b, r1, r2, θ）。

在累积投票过程中，我们会在霍夫空间中的相应位置为每个原始图像中的点（例如边缘点）增加计数。这样，我们可以在霍夫空间中找到局部最大值，这些局部最大值表示原始图像中可能存在的几何形状。

Exercise Sheet

(a) Feature detection as used for objection recognition and tracking needs to be robust to different types of invariance.

(i) Explain how the following types of invariance can be achieved (state all applicable algorithms):

i. Illumination [2 marks]

Illumination invariance can be achieved by using algorithms that are less sensitive to changes in lighting conditions. Common techniques include:

1. Histogram normalization: using normalisation, the feature vector is divided by its modal length.

2. Difference-based methods (e.g. SIFT): calculate the difference between adjacent pixels, which reduces the effect of illumination changes on features.

ii. Scale [2 marks]

Scale invariance can be achieved by representing the image at multiple scales and detecting features across these scales. Common techniques include:

1. Pyramids

2. Scale-Invariant Feature Transform (SIFT): It detects and describes local features in images at multiple scales using Difference of Gaussian (DoG) function.

iii. Rotation [2 marks]

Rotation invariance can be achieved by using algorithms that are insensitive to the orientation changes of the features. Common techniques include:

1. SIFT: The algorithm is also rotation invariant, as it assigns an orientation to the local features based on the dominant gradient directions.

(ii) Corner detection is frequently used in motion detection and image registration.

i. Explain why a corner is a better feature as compared to edges. [2 marks]

Corners are considered better features than edges because they provide more distinctive and stable information about the image structure. Corners are points where two edges meet, and they respond to changes in the image in multiple directions. This makes them less sensitive to noise, more robust to occlusion, and easily distinguishable compared to edges.

ii. Explain and outline how Moravec operator can be used for corner detection. [8 marks]

Moravec operator is a corner detection method that measures the local intensity changes in an image. The steps involved in the Moravec operator are:

1. Compute the local intensity change: For each pixel (x, y) in the image, calculate the squared intensity difference (E) with its neighbors in horizontal (u) and vertical (v) directions across a predefined window.

2. Compute the minimum E value: For each pixel (x,y), find the minimum E value over all directions (u,v).

3. Non-maximum suppression: Identify the local maxima of the minimum E values in a neighbourhood, and set all other values to zero.

4. Thresholding: Apply a threshold value to the resulting image to obtain the corner points.

(iii) Motion Correspondence can be used to match features in one image with those in another, to estimate motion. State and explain the THREE principles of motion correspondence. Specifically, state how an algorithm is designed to ensure features adhere to these principles. [4 marks]

Discreteness: Each feature in one image should have a unique match in the other image. SIFT generates unique descriptors for features, ensuring a one-to-one correspondence between matched features. This is achieved through the keypoint localization process, where SIFT identifies extrema in the Difference of Gaussian (DoG) space and refines their location to sub-pixel accuracy.

Similarity: Matched features should have similar appearances in both images. SIFT descriptors capture the local intensity pattern around a feature, making sure that the matched features have similar appearances despite changes in scale or rotation. This is done by calculating gradient magnitudes and orientations in the feature’s local neighborhood and creating a histogram of gradient directions, which forms the descriptor.

Consistency: The geometric transformation between matched features should be consistent across all feature pairs. In combination with SIFT, algorithms like RANSAC (Random Sample Consensus) are used to estimate the geometric transformation between the two images by iteratively selecting random subsets of SIFT-matched features and finding the transformation that maximizes the number of inliers (consistent matches). This ensures that the matched features follow a consistent geometric transformation, making the overall motion estimation more robust and accurate.