无核翻转的卷积计算

题目分析

给定一个 的核矩阵（ 为奇数）和一张 的灰度图，要求进行无核翻转的相关运算（cross-correlation）。在图像四周用 0 进行充分填充（same padding），使得输出尺寸与原图一致，然后对每个像素位置 ，将核与其邻域逐元素相乘后求和，得到输出像素值。

与卷积不同，相关运算不翻转核——核的左上角元素直接对齐到邻域的左上角。

思路

零填充 + 暴力枚举

这是一道图像处理中的基础相关运算模拟题。关键在于正确理解 same padding 和无翻转这两个要求。

算法步骤：

1. 零填充：在原图四周各填充 （整除）圈零，构造一个 的填充矩阵。原图的 位置对应到填充矩阵的
2. 遍历每个输出像素：对输出矩阵的每个位置 ，枚举核矩阵的所有 个元素 ，将 与 相乘并累加
3. 输出结果矩阵

以样例为例验证： 核矩阵 ，只有左上角 为 1，其余为 0。对于输出位置 ，计算时核的 对齐到填充矩阵的 ，即原图的 ，结果为 1。对于 ，核的 对齐到填充矩阵的 ，该位置是零填充区域，结果为 0。与预期输出一致。

复杂度

• 时间复杂度：，对每个输出像素遍历整个核
• 空间复杂度：，存储填充后的矩阵

代码

import sys
input = sys.stdin.readline

def main():
    m, n = map(int, input().split())
    kernel = []
    for _ in range(m):
        kernel.append(list(map(int, input().split())))
    image = []
    for _ in range(n):
        image.append(list(map(int, input().split())))

    pad = m // 2
    P = n + 2 * pad
    # 构造零填充矩阵
    padded = [[0] * P for _ in range(P)]
    for i in range(n):
        for j in range(n):
            padded[i + pad][j + pad] = image[i][j]

    # 相关运算（无核翻转）
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            s = 0
            for ki in range(m):
                for kj in range(m):
                    s += kernel[ki][kj] * padded[i + ki][j + kj]
            result[i][j] = s

    out = []
    for row in result:
        out.append(' '.join(map(str, row)))
    sys.stdout.write('\n'.join(out) + '\n')

main()