仿射变换与反向映射

人脸关键点对齐是人脸识别中的关键步骤，核心操作是仿射变换。题目给定一个 $H_A \times W_A$ 的二维图像矩阵 $A$、一个变换矩阵 $M$ 和输出图像的尺寸 $O_h \times O_w$，要求返回变换后的图像。

3 2 1
10 20 30
40 50 60
70 80 90
0 1 0
-1 0 2
3 3

观察这个变换矩阵的效果——$x' = y$，$y' = -x + 2$。这实际上是一个顺时针旋转 90° 再加上平移。原图的列变成了新图的行，而且顺序反转。

实现图像变换时，一个直觉的想法是：遍历原图的每个像素，算出它变换后的位置，然后赋值。这就是正向映射。

正确的做法是反向映射：遍历输出图像的每个像素 $(x', y')$，反向求解"它应该取原图中哪个位置的值？"

将正向变换展开为方程组：

移项得：

这是一个 $2 \times 2$ 线性方程组，用 克拉默法则直接求解——将系数矩阵的第 $j$ 列替换为右端向量，所得行列式除以系数行列式即为 $x_j$。设行列式 $\Delta = ad - bc$：

求出 $(x, y)$ 后，判断是否在原图范围内（$0 \le x < W$ 且 $0 \le y < H$）。如果在范围内，取 $A[y][x]$ 作为输出像素值；否则输出像素为 $0$。

import sys

def solve():
    data = sys.stdin.read().split()
    idx = 0

    a_rows = int(data[idx]); idx += 1
    m_rows = int(data[idx]); idx += 1
    _o_rows = int(data[idx]); idx += 1

    # 读取图像矩阵 A
    A = []
    for _ in range(a_rows):
        row = list(map(int, data[idx:idx + m_rows])) if m_rows > 0 else []
        # 实际上 A 的列数需要从数据推断
        A.append(row)
        idx += a_rows  # 这不对，需要按实际列数读取

    # 上面的读取逻辑需要修正 —— 重新设计
    pass

# 正确的读取逻辑如下：
def solve_correct():
    data = sys.stdin.read().split()
    idx = 0

    a_rows = int(data[idx]); idx += 1
    m_rows = int(data[idx]); idx += 1
    _o_info = int(data[idx]); idx += 1

    # 读取图像 A（a_rows 行，列数从数据推断）
    # A 的列数 = 后续剩余数据中能读出的列数
    # 但列数并未直接给出，需要用后续解析来确定
    A = []
    for _ in range(a_rows):
        # 每行的元素个数需要推断——但题目数据中每行元素个数一致
        # 读取第一个元素后，在后续 m_rows 行后找到输出尺寸行
        pass

    # 实际上，题目输入格式更简洁：所有数字用空格分隔
    # 第一行: a_rows m_rows 1（最后一项表示输出占几行，通常为1）
    # 接下来 a_rows 行: A 的每行
    # 接下来 m_rows 行: M 的每行
    # 最后 1 行: O_h O_w

上面展示了输入解析的复杂性。实际竞赛中，更清晰的做法是按行读取：

import sys

def main():
    it = iter(sys.stdin.read().strip().split('\n'))
    first = next(it).split()
    a_rows, m_rows, o_rows = int(first[0]), int(first[1]), int(first[2])

    # 读取图像 A
    A = []
    for _ in range(a_rows):
        A.append(list(map(int, next(it).split())))

    # 读取变换矩阵 M
    M = []
    for _ in range(m_rows):
        M.append(list(map(int, next(it).split())))

    # 读取输出尺寸
    last = next(it).split()
    o_h, o_w = int(last[0]), int(last[1])

    a, b, tx = M[0]
    c, d, ty = M[1]

    # 计算行列式
    det = a * d - b * c

    H_A = len(A)
    W_A = len(A[0]) if A else 0

    # 初始化输出
    output = [[0] * o_w for _ in range(o_h)]

    if det == 0:
        # 不可逆，返回全零
        result = []
        for row in output:
            result.extend(row)
        print(' '.join(map(str, result)))
        return

    # 反向映射：遍历输出图像的每个像素
    for oy in range(o_h):
        for ox in range(o_w):
            # 逆变换: 求原图坐标 (sx, sy)
            dx = ox - tx
            dy = oy - ty
            sx = (d * dx - b * dy) / det
            sy = (-c * dx + a * dy) / det

            # 最近邻插值（取整）
            ix = int(sx)
            iy = int(sy)

            # 边界检查
            if 0 <= ix < W_A and 0 <= iy < H_A:
                output[oy][ox] = A[iy][ix]

    # 按行展开输出
    result = []
    for row in output:
        result.extend(row)
    print(' '.join(map(str, result)))

if __name__ == '__main__':
    main()

很多初学者会写出类似下面的正向映射代码。这段代码包含了四个独立的 bug，每一个都会导致答案错误：

a, m, o = map(int, input().split())
A = [[] for _ in range(a)]
M = [[] for _ in range(m)]
for i in range(a):
    A[i] = list(map(int, input().split()))
for i in range(m):
    M[i] = list(map(int, input().split()))
h, w = map(int, input().split())
O = [[0] * w for _ in range(h)]

for i in range(a):
    for j in range(len(A[0])):
        x = M[0][0] * i + M[0][1] * j + M[0][2]   # ① ②
        y = M[1][0] * i + M[1][1] * j + M[1][2]   # ① ②
        if 0 <= x < h and 0 <= y < w:             # ③
            O[x][y] = A[i][j]                     # ② ④

print(O)                                          # ④

用样例 1 验证：$A = \begin{bmatrix} 10 & 20 & 30 \\ 40 & 50 & 60 \\ 70 & 80 & 90 \end{bmatrix}$，$M = \begin{bmatrix} 0 & 1 & 0 \\ -1 & 0 & 2 \end{bmatrix}$，输出 $3 \times 3$。

x = M[0][0] * j + M[0][1] * i + M[0][2]   # j 是列(x)，i 是行(y)
y = M[1][0] * j + M[1][1] * i + M[1][2]

result = []
for row in O:
    result.extend(row)
print(' '.join(map(str, result)))

下面是修正所有 bug 后的正向映射版本（仅当变换是双射时结果正确），供对比理解：

# ⚠️ 正向映射版本（仅当变换为双射时正确，不推荐）
import sys

def forward_mapping():
    it = iter(sys.stdin.read().strip().split('\n'))
    first = next(it).split()
    a_rows, m_rows, o_rows = int(first[0]), int(first[1]), int(first[2])

    A = [list(map(int, next(it).split())) for _ in range(a_rows)]
    M = [list(map(int, next(it).split())) for _ in range(m_rows)]
    last = next(it).split()
    o_h, o_w = int(last[0]), int(last[1])

    a, b, tx = M[0]
    c, d, ty = M[1]

    det = a * d - b * c
    O = [[0] * o_w for _ in range(o_h)]

    if det == 0:
        print(' '.join(str(v) for row in O for v in row))
        return

    H_A, W_A = len(A), len(A[0])
    for i in range(H_A):          # i = 行 = y
        for j in range(W_A):      # j = 列 = x
            col = a * j + b * i + tx   # x' = a*x + b*y + tx，x=j, y=i
            row = c * j + d * i + ty   # y' = c*x + d*y + ty
            if 0 <= col < o_w and 0 <= row < o_h:
                O[row][col] = A[i][j]  # O[行][列] = O[y'][x']

    print(' '.join(str(v) for row in O for v in row))

对比正向映射和反向映射的核心循环，差异一目了然：

更一般的变换还有透视变换（射影变换），有 8 个自由度，不保持平行性，但在人脸对齐场景中仿射变换已经足够。两者在数值方法上的核心差异同样是——都需要通过反向映射 + 逆矩阵来实现像素级的变换。