图像重叠

标签: 数组 矩阵

难度: Medium

给你两个图像 img1 和 img2 ，两个图像的大小都是 n x n ，用大小相同的二进制正方形矩阵表示。二进制矩阵仅由若干 0 和若干 1 组成。

转换 其中一个图像，将所有的 1 向左，右，上，或下滑动任何数量的单位；然后把它放在另一个图像的上面。该转换的 重叠 是指两个图像 都 具有 1 的位置的数目。

请注意，转换 不包括 向任何方向旋转。越过矩阵边界的 1 都将被清除。

最大可能的重叠数量是多少？

示例 1：

输入：img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
输出：3
解释：将 img1 向右移动 1 个单位，再向下移动 1 个单位。

两个图像都具有 1 的位置的数目是 3（用红色标识）。

示例 2：

输入：img1 = [[1]], img2 = [[1]]
输出：1

示例 3：

输入：img1 = [[0]], img2 = [[0]]
输出：0

提示：

  • n == img1.length == img1[i].length
  • n == img2.length == img2[i].length
  • 1 <= n <= 30
  • img1[i][j] 为 0 或 1
  • img2[i][j] 为 0 或 1

Submission

运行时间: 80 ms

内存: 36.1 MB

import numpy as np


class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        N = len(img1)
        N2 = 1 << (N.bit_length() + 1)
        img1_fft = np.fft.fft2(np.array(img1), (N2, N2))
        img2_fft = np.fft.fft2(np.array(img2)[::-1, ::-1], (N2, N2))
        img1_fft *= img2_fft
        conv = np.fft.ifft2(img1_fft)
        return int(np.round(np.max(conv)))

Explain

该题解使用了快速傅立叶变换(FFT)来计算两个图像的最大重叠区域。首先，将输入的两个图像img1和img2转换为NumPy数组。然后，将img2进行翻转（上下和左右翻转）。接着，对两个图像进行FFT变换，并将其转换结果相乘，这样做可以通过卷积定理来计算图像重叠的所有可能的平移。之后，使用逆FFT(ifft2)从频域变换回空间域，得到的矩阵包含所有平移配置下的重叠数。最后，通过求矩阵中的最大值得到最大重叠数。

时间复杂度: O(N^2 log N)

空间复杂度: O(N^2)

import numpy as np


class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        N = len(img1)  # 获取输入图像的边长
        N2 = 1 << (N.bit_length() + 1)  # 计算FFT的尺寸
        img1_fft = np.fft.fft2(np.array(img1), (N2, N2))  # 对img1进行FFT
        img2_fft = np.fft.fft2(np.array(img2)[::-1, ::-1], (N2, N2))  # 翻转img2并进行FFT
        img1_fft *= img2_fft  # 频域内的元素相乘（卷积）
        conv = np.fft.ifft2(img1_fft)  # 逆FFT，从频域变换回空间域
        return int(np.round(np.max(conv)))  # 寻找重叠最多的情况

Explore

使用快速傅立叶变换(FFT)而不是直接计算所有可能的平移的原因在于效率问题。如果直接计算，对于每种可能的平移配置，我们都需要对整个图像进行遍历计算重叠区域的像素数，这种方法的时间复杂度为O(N^4)，其中N是图像的尺寸。而FFT可以在O(N^2 log N)时间内完成，通过将图像转化到频域进行乘法操作后再逆变换回来，可以快速得到所有平移配置下的重叠值。因此，FFT方法在时间效率上远优于直接枚举平移。

在代码中将图像img2进行上下和左右翻转的原因是为了利用FFT计算卷积。卷积操作在数学上等价于将其中一个函数翻转并滑动，计算与另一个函数的重叠积分。在图像处理中，这意味着我们可以通过翻转img2后，使用FFT计算两图像的卷积，从而得到所有可能的平移下img1和img2的重叠值。这样处理可以将图像重叠问题转换为卷积问题，便于使用FFT来高效解决。

FFT变换对输入矩阵的大小通常有特殊要求，特别是为了获得最佳性能，输入矩阵的维度最好是2的幂次。这是因为FFT算法在处理2的幂次大小的数据时最为高效。在题解中，将图像扩展到N2 x N2的大小（N2是大于图像尺寸N的最小2的幂次），这样做是为了保证FFT运行时的高效性，并确保有足够的空间进行无缠绕的卷积，避免边界超出问题。

FFT变换和卷积的关系是FFT可以将卷积操作从时域（或空间域）转换到频域进行。根据卷积定理，两个信号的卷积在时域的计算可以转换为这两个信号的频域表示形式的逐点乘积，之后再通过逆FFT转换回时域。在此题解中，通过计算img1和已经翻转的img2的FFT，然后将得到的频域表示进行逐点乘积，最后通过逆FFT得到所有平移下的重叠值矩阵。通过查找这个矩阵中的最大值，我们可以找到img1和img2的最大重叠数。这种方法充分利用了FFT在频域内简化计算的优势。