#P4277. 第2题-人脸关键点对齐
-
1000ms
Tried: 259
Accepted: 26
Difficulty: 3
所属公司 :
华为
时间 :2025年10月23日-AI方向(留学生)
-
算法标签>几何变换图像处理
第2题-人脸关键点对齐
解题思路
-
算法:对给定图像做二维仿射变换。仿射模型为 x′=ax+by+tx,y′=cx+dy+ty。 为避免“空洞”,采用逆映射 + 最近邻插值:对每个输出像素 (x′,y′),先减去平移,再乘线性部分的逆矩阵,得到源坐标 (x,y)。若 (x,y) 在原图范围内,则取最近邻像素;否则置 0。
-
核心实现:
- 从矩阵 M=[acbdtxty] 取出 a,b,c,d,tx,ty。
- 计算线性部分的逆:

- 枚举输出图像尺寸 H×W 的每个像素 (x′,y′),

取 (round(x),round(y)) 作为最近邻位置,越界则填 0。
-
坐标约定:x 为列、y 为行,左上角为 (0,0)。
-
输入输出: 第一行给出行数:
a m o_lines。接着a行是图像 A;随后m行是 2×3 的变换矩阵 M;最后一行是输出尺寸H W。 输出按行优先展平成一行空格分隔的数列。
复杂度分析
- 时间复杂度:枚举全部输出像素,O(H×W)。
- 空间复杂度:保存输出图像,O(H×W)(除输入外)。
代码实现
Python
# 题面功能封装在函数里;主函数做输入输出(ACM 风格)
from typing import List
import sys
import math
def affine_transform(A: List[List[int]], M: List[List[float]], H: int, W: int) -> List[List[int]]:
# 解析仿射参数
a, b, tx = M[0]
c, d, ty = M[1]
# 线性部分行列式
det = a * d - b * c
hA, wA = len(A), len(A[0]) if A else 0
# 输出初始化为 0
O = [[0 for _ in range(W)] for _ in range(H)]
if abs(det) < 1e-12 or hA == 0 or wA == 0:
return O
# 预计算逆矩阵
inv00 = d / det
inv01 = -b / det
inv10 = -c / det
inv11 = a / det
for y2 in range(H): # y'
for x2 in range(W): # x'
# 去掉平移再乘逆矩阵 -> 源坐标 (x, y)
dx = x2 - tx
dy = y2 - ty
x = inv00 * dx + inv01 * dy
y = inv10 * dx + inv11 * dy
xi = int(round(x))
yi = int(round(y))
if 0 <= yi < hA and 0 <= xi < wA:
O[y2][x2] = A[yi][xi]
return O
def main():
data = sys.stdin.read().strip().split()
it = iter(data)
a = int(next(it)); m = int(next(it)); _ = int(next(it)) # O 占 1 行
A = []
if __name__ == "__main__":
import sys
lines = sys.stdin.read().strip().splitlines()
if not lines:
sys.exit(0)
a, m, _ = map(int, lines[0].split())
idx = 1
A = [list(map(int, lines[idx+i].split())) for i in range(a)]
idx += a
M = [list(map(float, lines[idx].split())), list(map(float, lines[idx+1].split()))]
idx += m
H, W = map(int, lines[idx].split())
O = affine_transform(A, M, H, W)
# 按行优先展平输出
out = []
for r in O:
out.extend(map(str, r))
print(" ".join(out))
Java
// 类名固定为 Main;主方法处理输入输出,功能写在外部静态函数里
import java.io.*;
import java.util.*;
public class Main {
// 仿射变换,最近邻
static int[][] affineTransform(int[][] A, double[][] M, int H, int W) {
int hA = A.length;
int wA = hA > 0 ? A[0].length : 0;
int[][] O = new int[H][W];
double a = M[0][0], b = M[0][1], tx = M[0][2];
double c = M[1][0], d = M[1][1], ty = M[1][2];
double det = a * d - b * c;
if (Math.abs(det) < 1e-12 || hA == 0 || wA == 0) return O;
// 线性部分逆矩阵
double inv00 = d / det, inv01 = -b / det;
double inv10 = -c / det, inv11 = a / det;
for (int y2 = 0; y2 < H; y2++) {
for (int x2 = 0; x2 < W; x2++) {
double dx = x2 - tx;
double dy = y2 - ty;
double x = inv00 * dx + inv01 * dy;
double y = inv10 * dx + inv11 * dy;
int xi = (int)Math.round(x);
int yi = (int)Math.round(y);
if (0 <= yi && yi < hA && 0 <= xi && xi < wA) {
O[y2][x2] = A[yi][xi];
} // 越界保持 0
}
}
return O;
}
public static void main(String[] args) throws Exception {
// 读取整段文本后逐行解析,避免 Scanner 过慢
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
List<String> lines = new ArrayList<>();
String s;
while ((s = br.readLine()) != null && s.length() > 0) lines.add(s);
if (lines.isEmpty()) return;
String[] t0 = lines.get(0).trim().split("\\s+");
int a = Integer.parseInt(t0[0]);
int m = Integer.parseInt(t0[1]); // 题目中 m=2
// o_lines = Integer.parseInt(t0[2]); // 未用
int idx = 1;
int[][] A = new int[a][];
for (int i = 0; i < a; i++) {
String[] ts = lines.get(idx++).trim().split("\\s+");
A[i] = new int[ts.length];
for (int j = 0; j < ts.length; j++) A[i][j] = Integer.parseInt(ts[j]);
}
double[][] M = new double[2][3];
for (int i = 0; i < 2; i++) {
String[] ts = lines.get(idx++).trim().split("\\s+");
for (int j = 0; j < 3; j++) M[i][j] = Double.parseDouble(ts[j]);
}
String[] ts = lines.get(idx).trim().split("\\s+");
int H = Integer.parseInt(ts[0]);
int W = Integer.parseInt(ts[1]);
int[][] O = affineTransform(A, M, H, W);
// 展平输出
StringBuilder out = new StringBuilder();
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (out.length() > 0) out.append(' ');
out.append(O[i][j]);
}
}
System.out.println(out.toString());
}
}
C++
// 主函数读入,功能放在独立函数;ACM 风格
#include <bits/stdc++.h>
using namespace std;
// 仿射变换:逆映射 + 最近邻
vector<vector<int>> affine_transform(const vector<vector<int>>& A,
const array<array<double,3>,2>& M,
int H, int W) {
int hA = (int)A.size();
int wA = hA ? (int)A[0].size() : 0;
vector<vector<int>> O(H, vector<int>(W, 0));
double a = M[0][0], b = M[0][1], tx = M[0][2];
double c = M[1][0], d = M[1][1], ty = M[1][2];
double det = a * d - b * c;
if (fabs(det) < 1e-12 || hA == 0 || wA == 0) return O;
// 线性部分逆矩阵
double inv00 = d / det, inv01 = -b / det;
double inv10 = -c / det, inv11 = a / det;
for (int y2 = 0; y2 < H; ++y2) {
for (int x2 = 0; x2 < W; ++x2) {
double dx = x2 - tx;
double dy = y2 - ty;
double x = inv00 * dx + inv01 * dy;
double y = inv10 * dx + inv11 * dy;
int xi = (int)llround(x); // 最近邻
int yi = (int)llround(y);
if (0 <= yi && yi < hA && 0 <= xi && xi < wA) {
O[y2][x2] = A[yi][xi];
}
}
}
return O;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, m, o;
if (!(cin >> a >> m >> o)) return 0;
// 读入图像 A(a 行)
vector<vector<int>> A(a);
cin.clear();
cin.seekg(0, ios::beg);
// 读整段
vector<string> lines;
string s;
while (getline(cin, s)) if(!s.empty()) lines.push_back(s);
if (lines.empty()) return 0;
{
stringstream ss(lines[0]);
ss >> a >> m >> o;
}
int idx = 1;
A.clear(); A.reserve(a);
for (int i = 0; i < a; ++i) {
stringstream ss(lines[idx++]);
vector<int> row; int v;
while (ss >> v) row.push_back(v);
A.push_back(row);
}
array<array<double,3>,2> M;
for (int i = 0; i < 2; ++i) {
stringstream ss(lines[idx++]);
for (int j = 0; j < 3; ++j) ss >> M[i][j];
}
int H, W;
{
stringstream ss(lines[idx]);
ss >> H >> W;
}
auto O = affine_transform(A, M, H, W);
// 展平输出
bool first = true;
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
if (!first) cout << ' ';
first = false;
cout << O[i][j];
}
}
cout << '\n';
return 0;
}
题目内容
人脸关键点对齐是人脸识别算法过程中非常重要的一步,其方法是基于检测人脸关键点及模板人脸关键点获得变换矩阵 M ,使得最小二乘意义下把原图的关键点贴到模板关键点位置,其基本原理是对图像得仿射变换。现在你将实现一个图像的仿射变换函数,该函数接收一个二维图像矩阵 A 、一个变换矩阵 M 和输出图像的尺寸 0 ,返回变换后的图像。
变换公式为,其中 x,y 为原坐标, x′,y′ 为变换后的坐标, a,b,c,d 是线性变换部分的系数, tx,ty 是平移向量: x′=a×x+b×y+tx
y′=c×x+d×y+ty
如果变换后的坐标超出原图像范围,则不赋值(保留为 0 )。
输入描述
输入图像 A :一个二维列表,表示输入图像,每个元素是一个像素值。
交换矩阵 M :一个二维列表,格式如下:
[[a,b,tx],[c,d,ty]]
输出图像的尺寸 height,width
输入第一行分别为 A、M 列表的长度 a,m 以及输出列表 O 所占用的行,接下来的 a 行为输入图像 A ,然后 m 行是输入变换矩阵,最后一行是输出图像的大小
输出描述
返回一个二维列表,表示变换后的图像
样例1
输入
3 2 1
10 20 30
40 50 60
70 80 90
0 1 0
-1 0 2
3 3
输出
30 60 90 20 50 80 10 40 70
说明
第一行 3 2 1 表示:
从第二行起接下来的三行是图像 A 的输入,然后下面两行是变换矩阵的输入,最后一行是输出图像的高度及宽度
输出图像矩阵为 [[30,60,90],[20,50,80],[10,40,70] ,
展开后最终的输出为 30 60 90 20 50 80 10 40 70
样例2
输入
3 2 1
10 20 30
40 50 60
70 80 90
-1 0 2
0 1 0
3 4
输出
30 20 10 0 60 50 40 0 90 80 70 0
提示
1.如果变换矩阵的线性部分 (a,b,c,d) 不可逆,则返回一个全 0 的图像