对齐与图像变换

发表于 2026-03-14 Waline：阅读次数：本文字数： 5.1k 阅读时长 ≈ 19 分钟

前两章解决了「在哪里」和「长什么样」的问题——我们有了一组匹配的关键点对 $\{(\bm{x}_i, \bm{x}_i')\}$ ，每对点描述的是两张图像中同一个物理位置。但匹配本身并不是终点，真正有用的是从这些匹配中推算出两张图像之间的几何变换：一张图片经过怎样的旋转、缩放或透视变形才能与另一张对齐？这就是对齐（Alignment）问题——也是全景拼接、三维重建、增强现实等应用的核心。

拟合与对齐

在深入对齐方法之前，有必要区分两个相关但不同的概念：

拟合 vs 对齐

拟合（Fitting）：给定一组数据点，找到最佳拟合模型的参数。例如给定一组边缘点，找到最佳的直线方程。数据点之间没有配对关系。

对齐（Alignment）：给定两组已匹配的点对，找到将一组点映射到另一组的变换参数。例如给定两张图中的对应关键点，找到最佳的仿射变换矩阵。

两者的数学工具大量重合——都需要从数据中估计参数。所以本章先从直线拟合开始，建立最小二乘等核心方法，再将它们应用于对齐问题。

参数化变换（Parametric Warping）是对齐的基本框架：变换 $T$ 是一台「坐标转换机器」， $\bm{p}' = T(\bm{p})$ 。「参数化」意味着 $T$ 对所有点都一样（全局的），可以用少量参数完整描述。对于线性变换， $T$ 就是一个矩阵。

设计对齐系统时需要回答两个问题：

拟合度量：如何衡量变换的好坏？度量应反映应用目标，并对噪声和异常值具有鲁棒性
优化方法：如何高效搜索最佳参数？需要避免局部最优

全局方法：最小二乘

普通最小二乘直线拟合

最经典的拟合问题：给定 $n$ 个数据点 $(x_1, y_1), \ldots, (x_n, y_n)$ ，找到直线 $y = mx + b$ 使得拟合误差最小。

将误差定义为各点到直线的纵向距离之和：

$E = \sum_{i=1}^{n} (y_i - mx_i - b)^2$

这可以写成矩阵形式 $E = \|\bm{A}\bm{p} - \bm{y}\|^2$ ，其中：

$\bm{A} = \begin{bmatrix} x_1 & 1 \\ \vdots & \vdots \\ x_n & 1 \end{bmatrix}, \quad \bm{p} = \begin{bmatrix} m \\ b \end{bmatrix}, \quad \bm{y} = \begin{bmatrix} y_1 \\ \vdots \\ y_n \end{bmatrix}$

对 $\bm{p}$ 求导并令其为零：

$\frac{\d E}{\d \bm{p}} = 2\bm{A}^{\intercal}\bm{A}\bm{p} - 2\bm{A}^{\intercal}\bm{y} = \bm{0} \implies \bm{p} = (\bm{A}^{\intercal}\bm{A})^{-1}\bm{A}^{\intercal}\bm{y}$

$(\bm{A}^{\intercal}\bm{A})^{-1}\bm{A}^{\intercal}$ 被称为伪逆（Pseudo-inverse）。在 NumPy 中一行搞定：p = np.linalg.lstsq(A, y)。

普通最小二乘的缺陷

纵向距离有一个致命问题：不具有旋转不变性。对于接近垂直的直线，纵向距离会趋向无穷——这意味着完全相同的数据，只是坐标轴旋转了一下，拟合结果就截然不同。对于垂直线，这种方法甚至直接失效。

全最小二乘

解决方案是用垂直距离（即点到直线的真实几何距离）代替纵向距离。将直线表示为 $ax + by + c = 0$ ，并约束 $a^2 + b^2 = 1$ （使 $(a, b)$ 为单位法向量），则点 $(x_i, y_i)$ 到直线的距离恰好是 $|ax_i + by_i + c|$ 。

目标变为最小化垂直距离的平方和：

$E = \sum_{i=1}^{n} (ax_i + by_i + c)^2$

求解分两步。首先对 $c$ 求导：

$\frac{\pd E}{\pd c} = \sum_{i=1}^{n} 2(ax_i + by_i + c) = 0 \implies c = -a\bar{x} - b\bar{y}$

其中 $\bar{x}, \bar{y}$ 是数据点的均值。将 $c$ 代入后，误差变为：

$E = \sum_{i=1}^{n} \bigl(a(x_i - \bar{x}) + b(y_i - \bar{y})\bigr)^2 = \bm{p}^{\intercal}\bm{A}^{\intercal}\bm{A}\bm{p}$

其中 $\bm{A}$ 的每行是 $(x_i - \bar{x},\; y_i - \bar{y})$ ， $\bm{p} = (a, b)^{\intercal}$ 。加上约束 $\bm{p}^{\intercal}\bm{p} = 1$ ，问题变为：

$\min_{\bm{p}} \frac{\bm{p}^{\intercal}\bm{A}^{\intercal}\bm{A}\bm{p}}{\bm{p}^{\intercal}\bm{p}}$

这就是瑞利商（Rayleigh Quotient）最小化问题，其解是 $\bm{A}^{\intercal}\bm{A}$ 的最小特征值对应的特征向量。

直觉上：特征向量给出了数据分布的主轴方向。最大特征值对应的特征向量是数据散布最大的方向（即直线的方向），最小特征值对应的特征向量是数据散布最小的方向（即直线的法线方向）。

两种基本优化模式

整个对齐与拟合领域的数学归结为两类优化问题，值得单独记住：

问题	求解方式
$\min \\|\bm{A}\bm{x} - \bm{b}\\|^2$ （超定方程的最小二乘解）	$\bm{x} = (\bm{A}^{\intercal}\bm{A})^{-1}\bm{A}^{\intercal}\bm{b}$
$\min \bm{x}^{\intercal}\bm{A}^{\intercal}\bm{A}\bm{x}$ s.t. $\bm{x}^{\intercal}\bm{x} = 1$ （齐次方程的非平凡最小二乘解）	$\bm{A}^{\intercal}\bm{A}$ 最小特征值对应的特征向量

第一种是「 $\bm{A}\bm{x} = \bm{b}$ 无精确解，求最接近的」；第二种是「 $\bm{A}\bm{x} = \bm{0}$ 只有平凡解，求最接近零的单位向量」。后面计算仿射变换、单应性等参数时会反复用到这两种模式。

最小二乘的优势与局限

最小二乘的优势在于：目标函数清晰明确（最小化残差平方和），优化过程简单（有封闭解，无需迭代）。但它也有几个重要缺陷：

对异常值敏感：一个错误匹配或噪声点就可能严重扭曲结果——因为平方误差会放大离群点的影响
无法处理多模型：如果数据中包含多条直线或多个运动物体，LS 只能找到一个「折中」的解
优化目标可能不正确：最小化几何距离的平方和不一定是应用真正需要的

其他全局方法与搜索策略

除了普通最小二乘，全局方法还包括鲁棒最小二乘（Robust Least Squares，使用对异常值不那么敏感的损失函数，如 Huber 损失或 Tukey 损失）和迭代最近点（Iterative Closest Point, ICP，在两组点云之间交替进行匹配和变换估计，常用于 3D 配准）。参数搜索方面，还有一些迭代式方法：线搜索（逐个参数调优，类似坐标下降）、网格搜索（在参数空间均匀采样）和梯度下降。这些方法在参数空间维度较高或目标函数非凸时更为实用。

假设-检验方法

最小二乘的问题根源在于：它试图让所有数据点都满足同一个模型。但现实中的匹配点往往包含大量错误匹配（异常值），直接用 LS 会被这些错误拖垮。

假设-检验（Hypothesize-and-Test）框架采用不同的策略：

提出假设：用某种方式生成候选参数
评分：用一致点（距离小于阈值的点）的数量来评价参数的好坏
选择：取得分最高的参数
精化：用所有一致点重新做 LS 拟合，得到更精确的结果

两种经典的假设生成方式是 Hough 变换和 RANSAC。

Hough 变换

Hough 变换的核心思想是一个优雅的对偶关系：图像空间中的一条直线对应参数空间中的一个点，图像空间中的一个点对应参数空间中的一条线（或曲线）。

从图像空间到参数空间

用 $y = mx + b$ 参数化直线。图像空间中一条确定的直线 $y = m_0 x + b_0$ 对应 $(m, b)$ 空间中的一个点 $(m_0, b_0)$ 。反过来，图像空间中的一个点 $(x_0, y_0)$ 满足所有使 $y_0 = mx_0 + b$ 成立的直线，即 $b = -x_0 m + y_0$ ——这是 $(m, b)$ 空间中的一条直线。

如果图像中多个点共线，那么它们在参数空间中对应的多条直线会交于同一个点——这个交点就是那条共线的参数。Hough 变换就是利用这个性质：让每个数据点在参数空间中「投票」，然后找票数最多的位置。

极坐标参数化

$(m, b)$ 参数化有一个实际问题： $m$ 可以取无穷大（垂直线），导致参数空间无界。解决方案是用极坐标参数化：

$x\cos\theta + y\sin\theta = d$

其中 $d$ 是原点到直线的垂直距离， $\theta$ 是垂线与 $x$ 轴的夹角。两个参数都有界： $\theta \in [0°, 180°)$ ， $d$ 的范围取决于图像大小。在这种参数化下，图像空间中的一个点映射到 $(\theta, d)$ 空间中的一条正弦曲线。

算法

初始化累加器数组 $H[d, \theta] = 0$
对每个边缘点 $(x, y)$ ：对 $\theta$ 从 $0$ 到 $180°$ 遍历（按某个量化步长），计算 $d = x\cos\theta + y\sin\theta$ ，令 $H[d, \theta] \mathrel{+}= 1$
找到 $H$ 中的峰值——每个峰值对应一条检测到的直线

import numpy as np

def hough_lines(edges, d_res=1, theta_res=np.pi/180):
    h, w = edges.shape
    diag = int(np.sqrt(h**2 + w**2))
    thetas = np.arange(0, np.pi, theta_res)
    ds = np.arange(-diag, diag, d_res)
    H = np.zeros((len(ds), len(thetas)), dtype=int)

    ys, xs = np.nonzero(edges)  # 边缘点坐标
    for t_idx, theta in enumerate(thetas):
        d = xs * np.cos(theta) + ys * np.sin(theta)
        d_idx = np.round((d + diag) / d_res).astype(int)
        for di in d_idx:
            if 0 <= di < len(ds):
                H[di, t_idx] += 1
    return H, ds, thetas

实际应用中的流程是：Image → Canny 边缘检测 → Hough 投票 → 找峰值 → 恢复直线参数。

Hough 变换的优缺点

优点	缺点
每个点独立处理，天然抗遮挡和间断	搜索复杂度随参数维度指数增长
对噪声有一定鲁棒性（噪声点不会一致投票到同一个 bin）	非目标形状可能产生虚假峰值
单次扫描可检测多个实例	网格量化的选择很棘手——太粗会丢失精度，太细会分散投票

Hough 变换适合检测直线、圆等参数维度低的简单几何形状。对于参数更多的模型（如仿射变换有 6 个参数），参数空间太大，Hough 变换就不实用了。

RANSAC

RANSAC（RANdom SAmple Consensus）采取完全不同的策略：与其让每个点投票，不如随机抽取最少数量的点来确定模型，然后看有多少其他点同意这个模型。

核心直觉：如果随机选到的点恰好都是内点（inlier），那么由它们确定的模型会得到大量其他内点的支持；如果不幸选到了异常值，那么计算出的模型会非常离谱，几乎没有其他点会支持它。

算法

flowchart TD
    A[随机采样最小点集] --> B[由这些点计算变换参数]
    B --> C[统计所有点中的内点数量]
    C --> D{已达到 k 次迭代？}
    D -->|否| A
    D -->|是| E[选择内点数最多的参数]
    E --> F[用全部内点重新做 LS 拟合]

    classDef step fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef decision fill:#fff3e0,stroke:#ef6c00,stroke-width:2px
    classDef result fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px

    class A,B,C step
    class D decision
    class E,F result

以直线拟合为例：每次随机选 2 个点（确定一条直线的最小数量），计算直线方程，然后数有多少其他点到这条线的距离小于阈值 $\epsilon$ ——这些就是内点。重复多次，保留内点最多的那条线。

需要多少次采样？

设 $w$ 是数据中内点的比例， $n$ 是确定模型所需的最小点数， $k$ 是采样次数。一次采样中 $n$ 个点全部是内点的概率为 $w^n$ 。 $k$ 次采样全部失败（即没有一次全部选中内点）的概率为 $(1 - w^n)^k$ 。要求成功概率至少为 $p$ ：

$1 - (1 - w^n)^k \ge p \implies k \ge \frac{\log(1 - p)}{\log(1 - w^n)}$

下表给出 $p = 0.99$ 时所需的采样次数 $k$ ：

最小点数 $n$	5% 异常值	10%	20%	25%	30%	40%	50%
2	2	3	5	6	7	11	17
3	3	4	7	9	11	19	35
4	3	5	9	13	17	34	72
5	4	6	12	17	26	57	146
6	4	7	16	24	37	97	293
7	4	8	20	33	54	163	588
8	5	9	26	44	78	272	1177

可以看到：异常值比例越高、模型参数越多，所需采样次数越多，但增长是可控的。即使 50% 的点都是异常值，拟合直线（ $n = 2$ ）只需 17 次采样就能以 99% 的概率成功。

RANSAC 之后的精化

RANSAC 本身只用最小点集拟合——2 个点确定的直线精度有限。找到最佳内点集后，应该用全部内点重新做最小二乘拟合，获得更精确的参数。而且，用新参数重新划分内点/外点后，内点集可能会变化，所以可以交替进行「拟合 → 重新分类 → 拟合」直到收敛。

RANSAC 的优缺点

优点	缺点
对异常值极其鲁棒	计算时间随异常值比例和参数维度增长
比 Hough 变换能处理更多参数	不擅长一次检测多个模型
参数（阈值 $\epsilon$ 、迭代次数 $k$ ）较容易选择	需要知道内点阈值 $\epsilon$

RANSAC 的典型应用

RANSAC 在计算机视觉中最常见的两个应用是：计算单应性矩阵（Homography，用于图像拼接）和估计基础矩阵（Fundamental Matrix，关联两个视角）。这两个问题的特点是匹配点中异常值比例很高（特征匹配不可避免地包含错误匹配），而 RANSAC 恰好擅长处理这种情况。

Hough 变换 vs RANSAC

维度	Hough 变换	RANSAC
核心思想	投票（每个点对所有一致参数投票）	抽样（随机选最小集合，看有多少支持）
多模型	天然支持（多个峰值）	需要迭代移除已找到的模型
参数维度	低维（2-3 参数）有效	高维也可用
复杂度	随参数维度指数增长	随异常值比例增长
异常值处理	通过投票分散	通过随机采样规避

图像变换

有了拟合方法，下一步是理解我们要拟合的是什么——图像之间有哪些常见的几何变换？

2D 线性变换

缩放（Scaling）将坐标乘以标量。均匀缩放 $s_x = s_y$ ，非均匀缩放 $s_x \ne s_y$ ：

$\begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} s_x & 0 \\ 0 & s_y \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}$

旋转（Rotation）绕原点旋转角度 $\theta$ ：

$\begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}$

这个公式可以从极坐标推导得出。设 $x = r\cos\phi$ ， $y = r\sin\phi$ ，旋转后 $x' = r\cos(\phi + \theta)$ ， $y' = r\sin(\phi + \theta)$ 。用和角公式展开：

$\begin{aligned} x' &= r\cos\phi\cos\theta - r\sin\phi\sin\theta = x\cos\theta - y\sin\theta \\ y' &= r\sin\phi\cos\theta + r\cos\phi\sin\theta = x\sin\theta + y\cos\theta \end{aligned}$

注意虽然 $\sin\theta$ 和 $\cos\theta$ 是 $\theta$ 的非线性函数，但 $x'$ 和 $y'$ 仍然是 $x, y$ 的线性组合——所以旋转是线性变换。旋转矩阵 $\bm{R}$ 的逆就是其转置： $\bm{R}^{-1} = \bm{R}^{\intercal}$ 。

剪切（Shearing）沿一个轴方向按另一个轴的坐标比例位移：

$\begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} 1 & \text{sh}_x \\ \text{sh}_y & 1 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}$

镜像（Mirror）沿某个轴翻转，例如关于 $y$ 轴镜像是 $x' = -x,\; y' = y$ 。

所有能用 $2 \times 2$ 矩阵表示的变换都是缩放、旋转、剪切和镜像的组合——它们统称为线性变换（Linear Transformation）。

$\begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} a & b \\ c & d \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}$

但是有一个重要的变换无法用 $2 \times 2$ 矩阵表示——平移。 $x' = x + t_x$ 不是 $x, y$ 的线性组合（有常数项），所以不能写成矩阵乘法的形式。

齐次坐标

为了将平移也纳入矩阵乘法的统一框架，引入齐次坐标（Homogeneous Coordinates）：在原始坐标后面添加一个额外的维度 $w$ ：

$\begin{bmatrix} x \\ y \end{bmatrix} \to \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}$

从齐次坐标转回普通坐标时，除以 $w$ ： $(wx, wy, w) \to (x, y)$ 。有了这个额外维度，平移就可以表示为 $3 \times 3$ 矩阵了：

$\begin{bmatrix} x' \\ y' \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ 1 \end{bmatrix} = \begin{bmatrix} x + t_x \\ y + t_y \\ 1 \end{bmatrix}$

类似地，所有基本 2D 变换都可以写成 $3 \times 3$ 齐次矩阵：

$\underbrace{\begin{bmatrix} 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1 \end{bmatrix}}_{\text{平移}} \quad \underbrace{\begin{bmatrix} s_x & 0 & 0 \\ 0 & s_y & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{\text{缩放}} \quad \underbrace{\begin{bmatrix} \cos\theta & -\sin\theta & 0 \\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{\text{旋转}} \quad \underbrace{\begin{bmatrix} 1 & \text{sh}_x & 0 \\ \text{sh}_y & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{\text{剪切}}$

齐次坐标的好处不仅仅是统一记法——更重要的是变换的复合变成了矩阵乘法。先旋转再平移？只需 $\bm{T} \cdot \bm{R}$ 。这使得多步变换可以预先合并为一个矩阵，只对每个像素做一次乘法。

变换的层次

2D 变换形成一个清晰的层次结构，每一层在上一层的基础上增加新的自由度：

变换	矩阵形式	DOF	保持的性质
平移	$\begin{bmatrix} \bm{I} & \bm{t} \\ \bm{0} & 1 \end{bmatrix}$	2	方向、长度、面积
刚体（欧氏）	$\begin{bmatrix} \bm{R} & \bm{t} \\ \bm{0} & 1 \end{bmatrix}$	3	长度、面积、角度
相似	$\begin{bmatrix} s\bm{R} & \bm{t} \\ \bm{0} & 1 \end{bmatrix}$	4	角度、长度比
仿射	$\begin{bmatrix} \bm{A}_{2\times 2} & \bm{t} \\ \bm{0} & 1 \end{bmatrix}$	6	平行线、面积比
射影（单应性）	$\begin{bmatrix} \bm{H}_{3\times 3} \end{bmatrix}$	8	直线

从上到下，变换越来越灵活（DOF 越多），但保持的几何性质越来越少。

仿射变换

仿射变换（Affine Transformation）是线性变换 + 平移，有 6 个自由度：

$\begin{bmatrix} x' \\ y' \\ 1 \end{bmatrix} = \begin{bmatrix} a & b & c \\ d & e & f \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}$

仿射变换的关键性质：

直线映射为直线
平行线保持平行
面积比保持不变
对复合封闭

仿射变换可以描述缩放、旋转、剪切和平移的任意组合。它是第 9 章中仿射归一化所使用的变换模型。由于有 6 个参数，至少需要 3 对匹配点（每对提供 2 个方程）来唯一确定一个仿射变换。

射影变换（单应性）

射影变换（Projective Transformation），也称单应性（Homography），是最一般的 2D 线性变换：

$\begin{bmatrix} wx' \\ wy' \\ w \end{bmatrix} = \begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix} \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}$

注意输出的 $w$ 不再恒为 1——需要做除法 $(x', y') = (wx'/w, wy'/w)$ 才能得到实际坐标。这个除法引入了非线性，是射影变换能表达透视效果的关键。

由于矩阵整体乘以一个标量不改变结果（ $(wx', wy', w)$ 和 $(\lambda wx', \lambda wy', \lambda w)$ 代表同一个点），9 个矩阵元素只有 8 个自由度。因此至少需要 4 对匹配点来确定一个单应性。

射影变换的性质：

直线映射为直线
平行线不一定保持平行
面积比不保持
对复合封闭
可建模基变换（change of basis）

单应性的几何意义

单应性描述的是从同一个投影中心出发，两个不同投影平面之间的映射。想象你站在同一个位置，透过两个不同朝向的窗户看同一个场景——两个窗户上看到的图像之间的关系就是单应性。这正是全景拼接的几何基础：相机绕光心旋转时，不同朝向拍摄的图像之间满足单应性关系。

对齐实例

求解平移

最简单的对齐问题：两张图之间只有平移。给定匹配点对 $(\bm{x}_i^A, \bm{x}_i^B)$ ，求平移向量 $(t_x, t_y)$ 使得 $\bm{x}_i^B = \bm{x}_i^A + \bm{t}$ 。

最小二乘：只需对所有匹配对取平均—— $t_x = \frac{1}{n}\sum(x_i^B - x_i^A)$ 。但如果有错误匹配就会偏离。

RANSAC：随机选 1 对匹配点计算 $(t_x, t_y)$ ，然后统计有多少其他匹配对与这个平移一致。重复多次取最佳。

Hough 变换：每对匹配点投票到 $(t_x, t_y)$ 空间中对应的位置，找票数最多的 bin。这种方法还能处理多个运动物体（多个峰值）。

全景拼接

全景拼接是对齐的经典应用。基本流程：

从同一位置拍摄一组图像（相机绕光心旋转）
用 SIFT/SURF 等提取关键点并匹配
用 RANSAC 估计相邻图像间的单应性矩阵 $\bm{H}$
用 $\bm{H}$ 将第二张图变换到第一张图的坐标系
在重叠区域混合两张图，生成全景

这整合了本课程的多个主题：边缘和关键点检测（Ch6、Ch8）、描述子匹配（Ch9）、RANSAC 对齐（本章）。

flowchart LR
    A[拍摄图像序列] --> B[关键点检测<br/>与匹配]
    B --> C[RANSAC 估计<br/>单应性 H]
    C --> D[图像变换<br/>与拼接]
    D --> E[重叠区域<br/>混合]

    classDef process fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef result fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px

    class A,B,C,D process
    class E result