题解 | #无核翻转的卷积计算#

题目链接

无核翻转的卷积计算

题目描述

给定一个奇数尺寸的核矩阵（kernel） $m \times m$ (其中 $m \ge 1$ ) 和一张 $n \times n$ 的灰度图像。要求实现一个二维相关（correlation）运算。

具体步骤如下：

首先在原始图像的四周用 $0$ 进行填充（zero-padding），使得运算后的输出图像尺寸与原图尺寸 $n \times n$ 保持一致。
然后，对于输出图像的每一个像素位置 $(i, j)$ ，将其值计算为核矩阵与输入图像对应邻域的逐元素乘积之和。
运算方式为“相关”，即核的左上角元素对齐到邻域的左上角元素，不需要像“卷积”那样对核进行 $180$ 度翻转。

输入描述：

第一行包含两个整数 $m$ 和 $n$ ，分别表示核矩阵的尺寸和图像的尺寸。
接下来 $m$ 行，每行 $m$ 个整数，表示核矩阵。
再接下来 $n$ 行，每行 $n$ 个整数，表示原始图像矩阵。

输出描述：

输出一个 $n \times n$ 的矩阵，表示运算结果。

解题思路

本题要求实现一个带零填充的二维相关运算。核心思路是先构建一个填充后的图像，然后在该图像上滑动核矩阵进行计算。

计算填充量 (Padding) 为了使输出尺寸与输入尺寸 $n \times n$ 相同，我们需要在原图的上下左右都添加一定数量的 $0$ 。这个填充量 $pad$ 可以通过公式推导得出。对于步长为 $1$ 的卷积/相关，输出尺寸 $n_{out} = n_{in} - m + 2 \cdot pad + 1$ 。我们希望 $n_{out} = n_{in} = n$ ，所以 $n = n - m + 2 \cdot pad + 1$ ，解得 $pad = (m - 1) / 2$ 。因为题目保证 $m$ 是奇数，所以 $pad$ 一定是整数。
构建填充后的图像 创建一个新的、更大的二维数组 padded_image，尺寸为 $(n + 2 \cdot pad) \times (n + 2 \cdot pad)$ 。然后将原始图像复制到这个新数组的中心位置。
执行相关运算 创建一个 $n \times n$ 的结果矩阵 result。通过四层嵌套循环来完成计算：
- 外两层循环遍历结果矩阵的每个像素位置 $(i, j)$ ，其中 $0 \le i < n, 0 \le j < n$ 。
- 内两层循环遍历 $m \times m$ 的核矩阵，设其坐标为 $(ki, kj)$ ，其中 $0 \le ki < m, 0 \le kj < m$ 。
- 对于每个输出点 $(i, j)$ ，其值是 $m \times m$ 个乘积的总和。核中的点 kernel[ki][kj] 应该与填充后图像中的点 padded_image[i + ki][j + kj] 相乘。
- 将这些乘积累加到 result[i][j] 中。
输出结果 遍历并打印结果矩阵 result。

这种“先填充、再计算”的方法可以避免在内层循环中进行繁琐的边界条件判断，使代码更简洁清晰。

代码

cpp
java
python

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int m, n;
    cin >> m >> n;

    vector<vector<int>> kernel(m, vector<int>(m));
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> kernel[i][j];
        }
    }

    vector<vector<int>> image(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> image[i][j];
        }
    }

    // 计算填充量
    int pad = (m - 1) / 2;
    int padded_size = n + 2 * pad;
    vector<vector<int>> padded_image(padded_size, vector<int>(padded_size, 0));

    // 将原图复制到填充图的中心
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            padded_image[i + pad][j + pad] = image[i][j];
        }
    }

    vector<vector<int>> result(n, vector<int>(n, 0));

    // 执行相关运算
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            long long sum = 0; // 使用 long long 防止乘积累加溢出
            for (int ki = 0; ki < m; ++ki) {
                for (int kj = 0; kj < m; ++kj) {
                    sum += (long long)kernel[ki][kj] * padded_image[i + ki][j + kj];
                }
            }
            result[i][j] = sum;
        }
    }

    // 输出结果
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << result[i][j] << (j == n - 1 ? "" : " ");
        }
        cout << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();

        int[][] kernel = new int[m][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                kernel[i][j] = sc.nextInt();
            }
        }

        int[][] image = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                image[i][j] = sc.nextInt();
            }
        }

        // 计算填充量
        int pad = (m - 1) / 2;
        int paddedSize = n + 2 * pad;
        int[][] paddedImage = new int[paddedSize][paddedSize];

        // 将原图复制到填充图的中心, paddedImage 默认初始化为0
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                paddedImage[i + pad][j + pad] = image[i][j];
            }
        }

        int[][] result = new int[n][n];

        // 执行相关运算
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                long sum = 0; // 使用 long 防止溢出
                for (int ki = 0; ki < m; ki++) {
                    for (int kj = 0; kj < m; kj++) {
                        sum += (long) kernel[ki][kj] * paddedImage[i + ki][j + kj];
                    }
                }
                result[i][j] = (int) sum;
            }
        }

        // 输出结果
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(result[i][j] + (j == n - 1 ? "" : " "));
            }
            System.out.println();
        }
    }
}

# 读取 m 和 n
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 - 1) // 2
padded_size = n + 2 * pad

# 创建并填充 padded_image
padded_image = [[0] * padded_size for _ in range(padded_size)]
for i in range(n):
    for j in range(n):
        padded_image[i + pad][j + pad] = image[i][j]

# 创建结果矩阵
result = [[0] * n for _ in range(n)]

# 执行相关运算
for i in range(n):
    for j in range(n):
        current_sum = 0
        for ki in range(m):
            for kj in range(m):
                current_sum += kernel[ki][kj] * padded_image[i + ki][j + kj]
        result[i][j] = current_sum

# 输出结果
for i in range(n):
    print(*result[i])

算法及复杂度

算法：二维相关运算，通过零填充（Zero-Padding）来保持输出尺寸。
时间复杂度： $O(n^2 \cdot m^2)$ 。其中 $n \times n$ 是输出图像的尺寸， $m \times m$ 是核的尺寸。对于输出图像中的每个像素，都需要进行 $m \times m$ 次乘法和加法操作。
空间复杂度： $O((n+m)^2)$ 。需要额外的空间来存储填充后的图像，其尺寸大约为 $(n+m) \times (n+m)$ ，这是空间占用的主要部分。同时还需要存储原始图像、核以及结果图像，空间复杂度为 $O(n^2 + m^2)$ 。综合来看，由填充图像主导。