人脸关键点对齐

题目分析

本题要求实现二维灰度图像的仿射变换（前向映射）。给定一个仿射矩阵 $M$ ，对源图像中的每个像素 $(x, y)$ 计算其在目标图像中的新坐标 $(x', y')$ ：

$ $x' = ax + by + t_x$ $

$ $y' = cx + dy + t_y$ $

如果新坐标在目标图像范围内，则将像素值写入目标图像；超出范围的丢弃；未被覆盖的位置保持为 0。

思路

这是一道模拟题，按照题意直接实现即可：

读取输入：依次读取图像矩阵、仿射矩阵和输出尺寸。
前向映射：遍历源图像的每个像素 $(x, y)$ ，其中 $x$ 是列坐标， $y$ 是行坐标。通过仿射矩阵计算目标坐标 $(x', y')$ ，四舍五入取整后判断是否在目标范围内。
输出结果：将目标图像按行展开，用空格分隔输出。

需要注意坐标系的对应关系：图像的行对应 $y$ 坐标，列对应 $x$ 坐标。

代码

import sys

def main():
    data = sys.stdin.read().split('\n')
    ptr = 0

    first_line = data[ptr].split()
    ptr += 1
    a = int(first_line[0])  # 图像行数
    m = int(first_line[1])  # 仿射矩阵行数（固定为2）
    o = int(first_line[2])  # 输出尺寸行数（固定为1）

    # 读取图像矩阵
    img = []
    for i in range(a):
        row = list(map(int, data[ptr].split()))
        img.append(row)
        ptr += 1

    h_in = a
    w_in = len(img[0]) if img else 0

    # 读取仿射矩阵（2行3列）
    M = []
    for i in range(m):
        row = list(map(float, data[ptr].split()))
        M.append(row)
        ptr += 1

    a_val, b_val, tx = M[0][0], M[0][1], M[0][2]
    c_val, d_val, ty = M[1][0], M[1][1], M[1][2]

    # 读取输出尺寸
    out_line = data[ptr].split()
    out_height = int(out_line[0])
    out_width = int(out_line[1])

    # 初始化目标图像
    out_img = [[0] * out_width for _ in range(out_height)]

    # 前向映射
    for y in range(h_in):
        for x in range(w_in):
            xp = int(round(a_val * x + b_val * y + tx))
            yp = int(round(c_val * x + d_val * y + ty))
            if 0 <= xp < out_width and 0 <= yp < out_height:
                out_img[yp][xp] = img[y][x]

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

main()

复杂度分析

时间复杂度： $O(H_{in} \times W_{in} + H_{out} \times W_{out})$ ，其中前者是遍历源图像像素做映射，后者是输出目标图像。
空间复杂度： $O(H_{out} \times W_{out})$ ，用于存储目标图像。