我正在寻找一种算法来有效地确定一幅2D图像到另一幅图像的最佳平移(限于x和y轴,不旋转).目标是找到最大的公共像素,其中像素在白色背景上被认为是黑色的,反之亦然.前景与背景的比率明显向背景倾斜.
示例:
这里,最好的翻译是[-171,97].
我已经实现了一个算法,它比较所有的像素,并通过递增x和y来迭代转换.然而,这种方法很耗时.为了解决这个问题,我试图通过只关注第二张图像中白色像素到其他白色像素的转换来加快这一过程.虽然它奏效了,但仍然很慢.
下面是我当前算法的代码片段(arrayImage只包含0和1,它是一个二进制图像).
public static int[] findBestTranslation(int[][] arrayImage1, int[][] arrayImage2) {
int[] bestTranslation = new int[2];
int bestSimilarity = Integer.MIN_VALUE;
int img2Length = arrayImage2.length;
int img2Width = arrayImage2[0].length;
List<int[]> whitePixelsImage1 = findWhitePixels(arrayImage1);
List<int[]> whitePixelsImage2 = findWhitePixels(arrayImage2);
boolean[][] checkedOffsets = new boolean[img2Length * 2][img2Width * 2];
int i = 0;
for (int[] pixel1 : whitePixelsImage1) {
System.out.println(i++ + ": " + bestSimilarity);
for (int[] pixel2 : whitePixelsImage2) {
//calculate translation
int xOffset = pixel2[0] - pixel1[0];
int yOffset = pixel2[1] - pixel1[1];
// Check if this offset has been selected before
if (checkedOffsets[xOffset + img2Length][yOffset + img2Width]) {
continue;
} else {
checkedOffsets[xOffset + img2Length][yOffset + img2Width] = true;
}
int similarity = 0;
for (int[] pixelNotTranslated : whitePixelsImage1) {
int xTranslated = pixelNotTranslated[0] + xOffset;
int yTranslated = pixelNotTranslated[1] + yOffset;
if (xTranslated >= 0 && xTranslated < img2Length && yTranslated >= 0 && yTranslated < img2Width) {
similarity += arrayImage2[xTranslated][yTranslated];
}
}
if (similarity > bestSimilarity) {
bestSimilarity = similarity;
bestTranslation[0] = xOffset;
bestTranslation[1] = yOffset;
}
}
}
return bestTranslation;
}