图像重叠
难度:
标签:
题目描述
给你两个图像 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].lengthn == img2.length == img2[i].length1 <= n <= 30img1[i][j]为0或1img2[i][j]为0或1
代码结果
运行时间: 80 ms, 内存: 36.1 MB
/*
* 思路：
* 使用 Java Stream 流来处理二维数组。利用双重循环，使用流计算所有可能位移下的重叠 1 的最大数量。
*/
import java.util.stream.IntStream;
public class Solution {
public int largestOverlap(int[][] img1, int[][] img2) {
int n = img1.length;
return IntStream.range(-n + 1, n).boxed()
.flatMap(xShift -> IntStream.range(-n + 1, n)
.mapToObj(yShift -> calculateOverlap(img1, img2, xShift, yShift)))
.max(Integer::compareTo)
.orElse(0);
}
private int calculateOverlap(int[][] img1, int[][] img2, int xShift, int yShift) {
int n = img1.length;
return IntStream.range(0, n).boxed()
.flatMap(i -> IntStream.range(0, n)
.mapToObj(j -> new int[]{i, j}))
.mapToInt(p -> {
int i = p[0], j = p[1];
int x2 = i + xShift;
int y2 = j + yShift;
return (x2 >= 0 && x2 < n && y2 >= 0 && y2 < n) ? img1[i][j] & img2[x2][y2] : 0;
}).sum();
}
}
解释
方法:
该题解使用了快速傅立叶变换(FFT)来计算两个图像的最大重叠区域。首先，将输入的两个图像img1和img2转换为NumPy数组。然后，将img2进行翻转（上下和左右翻转）。接着，对两个图像进行FFT变换，并将其转换结果相乘，这样做可以通过卷积定理来计算图像重叠的所有可能的平移。之后，使用逆FFT(ifft2)从频域变换回空间域，得到的矩阵包含所有平移配置下的重叠数。最后，通过求矩阵中的最大值得到最大重叠数。
时间复杂度:
O(N^2 log N)
空间复杂度:
O(N^2)
代码细节讲解
🦆
为什么在处理图像重叠问题时选择使用快速傅立叶变换(FFT)而不是直接计算所有可能的平移？
▷🦆
在代码中，为什么需要将图像img2进行上下和左右翻转？这一操作的数学或算法意义是什么？
▷🦆
FFT变换对于输入矩阵的大小有什么特殊要求？为什么要将图像扩展到N2 x N2的大小？
▷🦆
如何理解FFT变换和卷积的关系，在此题解中如何利用这一性质计算图像重叠？
▷