I'm searching for an algorithm to efficiently determine the optimal translation of one 2D image onto another (limited to x and y axes, without rotation). The goal is to find the maximum common pixel, where pixels are considered black on a white background and vice versa. The foreground-to-background ratio is significantly skewed towards the background.
Example:
Here, the best translation is [-171, 97].
I've already implemented an algorithm that compares all pixels and iterates through translations by incrementing x and y. However, this approach is time-consuming. To address this, I've attempted to speed up the process by focusing only on the translation of white pixels to other white pixels in the second image. Although it works, it's still slow.
Below is the code snippet of my current algorithm (arrayImage is only contains 0 and 1, it's a binary image).
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;
}
I don't speak Java, but I think you want a "phase correlation", which you can do with scikit-image in Python as follows:
Output
For your two images, it outputs the following in around 1 second:
I guess you could either "shell out" to Python with some type of
exec()
orsystem()
function, or find a Java implementation of the phase correlation technique.There is also an OpenCV implementation available, which may have Java bindings. It is noticeably faster than the method above and gets the result in well under 1 second:
Output
Here's what I get if I plot one image in green, then the second image in red shifted by the calculated amount.
I used a "hardmix" blending mode, so the yellow parts are where red and green coincide. For my own reference, this was my blend command with ImageMagick: