Skip to content

Image Matching and motion estimation

Main components of feature matching:

  • Detetion: Identify the interest points
  • Description: Extract vector feature descriptor surrounding each interest point
  • Matching: Determine correspondence between descriptors in two view

Detection

We look for image regions that are unique. Measure the uniqueness of a region:

If Shifting the window in any direction causes a big change, it is unique -> corners

  • Compute the distribution of gradients in the region
  • Use principal component analysis

Corner detetion

  • 角点定义：图像中在两个或多个方向上灰度变化剧烈的点（如物体拐角、纹理交叉点）。与边缘（单方向变化大）和平坦区域（变化小）不同，角点具有独特的局部结构，对旋转、光照变化有一定稳定性。

  • Compute covariance matrix at each point alt text

  • Compute eigenvalues alt text
  • Classify points using eigenvalues of H: alt text

Harris detector

  1. Compute derivatives at each pixel
  2. Compute covariance matrix H in a Gaussian window around each pixel
  3. Compute corner response function f
  4. Threshold f
  5. Find local maxima of response function (nonmaximum suppression)

Harris corner detector computes the following response function

\[ f=\frac{\lambda_1 \lambda_2}{\lambda_1+\lambda_2} = \frac{determinant(H)}{trace(H)} \]

哈里斯角点检测器

哈里斯检测器基于局部窗口内的灰度变化来识别角点，通过计算响应函数并阈值化实现。

核心步骤
  1. 计算梯度：使用Sobel等算子求图像水平方向 \(I_x\) 和垂直方向 \(I_y\) 的梯度。
  2. 构建结构张量：对每个像素，计算其邻域（窗口）内梯度的二阶矩矩阵： [ M = \sum_{x,y} w(x,y) \begin{bmatrix} I_x^2 & I_x I_y \ I_x I_y & I_y^2 \end{bmatrix} ] 其中 \(w(x,y)\) 是窗口函数（通常为高斯权重）。
  3. 计算响应函数：避免直接计算矩阵 \(M\) 的特征值 \(\lambda_1, \lambda_2\)，使用哈里斯响应： [ R = \det(M) - k \cdot (\text{trace}(M))^2 ] 其中 \(\det(M) = \lambda_1 \lambda_2\)，\(\text{trace}(M) = \lambda_1 + \lambda_2\)，\(k\) 为经验常数（通常0.04~0.06）。
  4. \(R > 0\) 且较大 → 角点
  5. \(R < 0\) 且绝对值较大 → 边缘
  6. \(|R|\) 较小 → 平坦区域
  7. 非极大值抑制：在局部邻域内保留响应最大的点，剔除其余点，得到精确角点位置。

Invariance properties of Harris detector

  • Photometric transformation(intensity change):
    • invariant to intensity shift: \(I\rightarrow I+b\)
    • variant to intensity scaling: \(I\rightarrow aI\)
  • Image translation(平移): invariant
  • Image rotation: invariant
  • Scaling: not invariant
    • Solution: Automatic scale selection

Blob detector

Blobs are have large second derivatives in image intensity

  • Compute Laplacian of image
  • Find maxima and minima of Laplacian

Laplacian filter:

alt text

  • Laplacian is sensitive to noise
  • Usually using Lapacian of Guassian(LoG) filter
    • Smooth image with a Gaussian filter
    • Compute laplacian

LoG can be approximated by Difference of two Gaussians (DoG):

  1. Filter the image with two Gaussians
  2. Compute the difference of two filtered images

Description

We know how to detect good points. Next question: How to match them?

  • Extract a descriptor for each point
  • find similar descriptors between the two images

SIFT descriptor

SIFT(Scale Invariant Feature Transform)

Histogram of oriented gradients：

  • Captures important texture information
  • Robust to small translations / affine deformations

Orientation Normalization:

  • Compute orientation histogram
  • Select dominant orientation
  • Normalize: rotate to fixed orientation

计算步骤：

  1. 确定特征区域：根据关键点的位置、特征尺度和主方向，确定一个围绕该点的邻域区域。
  2. 划分子区域：将该邻域划分为4×4=16个子区域。
  3. 计算梯度方向直方图：在每个子区域内，计算每个像素的梯度幅值和方向（相对于关键点主方向旋转不变），将方向（0-360°）量化为8个方向区间，构建8-bin的梯度方向直方图，并用梯度幅值和高斯权重进行加权累加。
  4. 形成描述向量：将16个子区域的8维直方图串联，形成一个128维的特征向量（16×8=128）。
  5. 归一化处理：对向量进行归一化，以增强对光照变化的鲁棒性；同时进行阈值截断（如限制每个元素不大于0.2）后再归一化，以减弱非线性光照的影响。

Lowe’s SIFT algorithm

  • Run DoG detector
    • Find maxima in location/scale space
  • Find dominate orientation
  • For each (x,y,scale,orientation), create descriptor

Properties of SIFT

Extraordinarily robust matching technique

  • Can handle changes in viewpoint
    • Theoretically invariant to scale and rotation (why?)
  • Can handle significant changes in illumination
    • Sometimes even day vs. night (below)
  • Fast and efficient—can run in real time
  • Lots of code available

Matching

Given a feature in I1, how to find the best match in I2?

  1. Define distance function that compares two descriptors
  2. Test all the features in I2, find the one with min distance

Ratio test

对于图像A中的每一个特征描述子（如SIFT的128维向量）：

  1. 在图像B中找出与其欧氏距离最近的描述子（最近邻），记距离为 d1。
  2. 在图像B中找出与其欧氏距离第二近的描述子（次近邻），记距离为 d2。
  3. 计算比率：r = d1 / d2。
  4. 设定一个阈值 T（通常为 0.7 或 0.8），如果 r < T，则接受该匹配；否则拒绝。

问题：Ambiguous matches have large ratio scores

Mutual nearest neighbor

Another strategy: find mutual nearest neighbors

  • f2 is the nearest neighbor of f1 in I2
  • f1 is the nearest neighbor of f2 in I1

Motion estimation

estimation problems:

  • Feature-tracking
    • Extract feature (interest) points and “track” them over multiple frames
    • Output: displacement of sparse points
  • optical flow
    • Recover image motion at each pixel
    • Output: dense displacement field (optical flow)

Key assumptions of Lucas-Kanade:

  • small motion: points do not move very far
  • brightness constancy: same point looks the same in every frame
  • spatial coherence: points move like their neighbour

alt text

核心定义

Lucas-Kanade 方法 是一种用于估计稀疏光流的差分方法。其核心目标是：给定两幅时间上连续的图像（例如视频的相邻帧），找到图像中一组特征点（如角点）在帧间的运动位移向量（即光流）。

它是一种局部、基于梯度的优化方法。

核心思想与两个基本假设

该方法建立在两个关键的物理/数学假设之上：

  1. 亮度恒定假设：一个点的像素亮度在帧间短时间运动期间保持不变。

    • 数学表达：I(x, y, t) = I(x+u, y+v, t+1)
    • 其中 (u, v) 是我们要找的位移向量（光流）。

  2. 小运动/局部平滑假设：一个点的运动与其邻域内其他点的运动一致（或变化缓慢）。这使得我们可以利用一个局部窗口 W（如 5x5 或 7x7）内的多个像素来共同求解一个统一的 (u, v)。

工作原理与推导

  1. 由假设1建立方程：对亮度恒定方程进行一阶泰勒展开（假设运动 (u, v) 很小）： [ I(x+u, y+v, t+1) \approx I(x,y,t) + I_x \cdot u + I_y \cdot v + I_t ] 其中 I_x, I_y 是图像在 (x, y) 处的空间梯度，I_t 是时间梯度（即两帧间的灰度变化）。结合亮度恒定假设，得到： [ I_x \cdot u + I_y \cdot v + I_t \approx 0 ] 这个方程被称为光流约束方程。它只有一个方程，却包含两个未知数 (u, v)，是病态问题（一个点本身无法确定其运动方向，即“孔径问题”）。

  2. 利用假设2求解：为了解决孔径问题，Lucas-Kanade 假设在一个小的局部窗口 W 内，所有像素共享同一个 (u, v)。于是，对于窗口内的 n 个像素，我们得到一个超定方程组： [ \begin{bmatrix} I_x(p_1) & I_y(p_1) \ I_x(p_2) & I_y(p_2) \ \vdots & \vdots \ I_x(p_n) & I_y(p_n) \end{bmatrix} \begin{bmatrix} u \ v \end{bmatrix} = - \begin{bmatrix} I_t(p_1) \ I_t(p_2) \ \vdots \ I_t(p_n) \end{bmatrix} ] 简写为：A * d = b，其中 d = [u, v]^T。

  3. 最小二乘求解：通过求解最小二乘问题 A^T A d = A^T b 来得到最优的 (u, v)： [ d = (A^T A)^{-1} A^T b ] 其中，A^T A 是一个 2x2 的矩阵，它实质上是窗口内梯度结构张量的求和： [ A^T A = \begin{bmatrix} \sum I_x^2 & \sum I_x I_y \ \sum I_x I_y & \sum I_y^2 \end{bmatrix} ] 这个矩阵的可逆性（即其特征值的大小）决定了该点光流估计的可靠性。当两个特征值都很大时（即角点区域），估计最可靠；当一个特征值很大，另一个很小时（即边缘），沿边缘方向的运动不确定（孔径问题依然存在）；当两个特征值都很小时（即平坦区域），无法估计运动。

要点总结

方面 Lucas-Kanade 方法
目标 估计两幅图像间一组稀疏特征点的位移向量（光流）。
两大基石假设 1. 亮度恒定。
2. 局部运动一致（在小窗口内）。
核心方程 光流约束方程：I_x*u + I_y*v + I_t = 0。
如何求解 在一个局部窗口内建立超定方程组，通过最小二乘法求解，关键矩阵为梯度结构张量 A^T A。
关键改进 图像金字塔：用于处理大位移运动，实现由粗到精的估计。
主要输出 每个被跟踪特征点的位移 (u, v)。
典型应用 稀疏特征点跟踪、视频稳定、运动分析。

一句话总结：Lucas-Kanade 是一种基于亮度恒定和局部平滑假设，利用局部窗口梯度信息通过最小二乘法求解稀疏光流的高效算法，是许多运动估计任务的基石。

  • 孔径问题：孔径问题是LK方法因依赖局部窗口信息而固有的局限，表现为在边缘等区域无法唯一确定真实的运动方向，只能感知到垂直于图像结构的运动分量。

Errors in Lukas-Kanade

potential causes of errors in this procedure:

  • Suppose \(A^TA\) is easily invertible
  • Suppose there is not much noise in the image
  • Assumptions are violated:
    • Brightness constancy is not satisfied
    • The motion is not small
    • A point does not move like its neighbors

Comments