Ответ 1
Проблема трудно ответить вообще, потому что люди часто имеют разные требования к тому, что считается совпадением изображения. Некоторые люди могут захотеть найти изображение, которое может иметь другой размер или ориентацию, чем шаблонный образ, который они предоставляют, и в этом случае необходим масштабный или поворотно-инвариантный подход. Существуют различные варианты, такие как поиск похожих текстур, функций или фигур, но я сосредоточусь на подходах, которые ищут только пиксели того же цвета, которые находятся в том же положении, что и изображение шаблона. Это кажется наиболее подходящим для вашего примера, который, кажется, относится к категории соответствие шаблону.
Возможные подходы
В этом случае проблема тесно связана с концепциями обработки сигналов cross-correlation и convolution, который часто реализуется с помощью FFT, поскольку он очень быстрый (его в имя!). Это то, что было использовано в подходе connected to, а FFTW библиотека может быть полезна при попытке такой реализации, поскольку она имеет оболочки для Java. Использование кросс-корреляции работает достаточно хорошо, как показано в этом вопросе, а также знаменитый waldo вопрос.
Другой вариант - не использовать все пиксели для сравнения, а скорее только функции, которые легче найти и, скорее всего, будут уникальными. Для этого потребуется дескриптор функции, например SIFT, SURF или один из многих других. Вам нужно будет найти все функции в обоих изображениях, а затем искать функции, которые имеют аналогичные позиции по сравнению с изображениями в шаблоне. С помощью этого подхода я предлагаю вам использовать JavaCV.
Предполагаемый подход к угадыванию, который вы упомянули, должен работать быстро, когда это возможно, но, к сожалению, он обычно не применим, поскольку он будет полезен только при определенных комбинациях изображений, которые будут близки к правильному местоположению.
Если вы не используете внешнюю библиотеку, самым простым методом в Java будет то, что я бы назвал методом грубой силы, хотя он немного медленный. Подход грубой силы просто включает поиск всего изображения для субрегиона, который наилучшим образом соответствует изображению, которое вы ищете. Я объясню этот подход дальше. Сначала вам нужно определить, как определить сходство между двумя изображениями одинакового размера. Это можно сделать, суммируя различия между цветами пикселей, которые требуют определения разницы между значениями RGB.
Сходство с цветом
Один из способов определения разницы между двумя значениями RGB - использовать эвклидовое расстояние:
sqrt( (r1-r2)^2 + (g1-g2)^2 + (b1-b2)^2 )
Существуют разные цветовые пространства, чем RGB, которые могут быть использованы, но поскольку ваш суб-образ, скорее всего, почти идентичен (а не просто визуально подобен), это должно работать нормально. Если у вас есть цветовое пространство ARGB, и вы не хотите, чтобы полупрозрачные пиксели влияли на ваши результаты так же, вы можете использовать:
a1 * a2 * sqrt( (r1-r2)^2 + (g1-g2)^2 + (b1-b2)^2 )
который даст меньшее значение, если цвета имеют прозрачность (при условии, что a1 и a2 находятся между 0 и 1). Я бы предложил использовать прозрачность вместо белых областей и использовать формат файла PNG, поскольку он не использует сжатие с потерями, которое тонко искажает цвета на изображении.
Сравнение изображений
Чтобы сравнить изображения одинакового размера, вы можете суммировать разницу между их отдельными пикселями. Эта сумма является мерой разницы, и вы можете искать регион в изображении с наименьшей разницей. Это становится сложнее, если вы даже не знаете, содержит ли изображение суб-изображение, но это будет указано лучшим совпадением с высокой разницей. Если вы хотите, вы также можете нормализовать разностную меру, чтобы лежать между 0 и 1, разделив ее на размер суб-изображения и максимально возможную разницу RGB (sqrt (3) с эвклидовым расстоянием и значениями RGB от 0 до 1). Тогда Zero будет идентичным, и все, что близко к одному, будет как можно более различным.
Внештатная реализация
Вот простая реализация, использующая подход грубой силы для поиска изображения. С примерами изображений он нашел местоположение (139,55) в верхнем левом углу области с наилучшим соответствием (что выглядит правильно). Для работы на моем ПК потребовалось около 10-15 секунд, и нормализованная разница в местоположении составила около 0,57.
/**
* Finds the a region in one image that best matches another, smaller, image.
*/
public static int[] findSubimage(BufferedImage im1, BufferedImage im2){
int w1 = im1.getWidth(); int h1 = im1.getHeight();
int w2 = im2.getWidth(); int h2 = im2.getHeight();
assert(w2 <= w1 && h2 <= h1);
// will keep track of best position found
int bestX = 0; int bestY = 0; double lowestDiff = Double.POSITIVE_INFINITY;
// brute-force search through whole image (slow...)
for(int x = 0;x < w1-w2;x++){
for(int y = 0;y < h1-h2;y++){
double comp = compareImages(im1.getSubimage(x,y,w2,h2),im2);
if(comp < lowestDiff){
bestX = x; bestY = y; lowestDiff = comp;
}
}
}
// output similarity measure from 0 to 1, with 0 being identical
System.out.println(lowestDiff);
// return best location
return new int[]{bestX,bestY};
}
/**
* Determines how different two identically sized regions are.
*/
public static double compareImages(BufferedImage im1, BufferedImage im2){
assert(im1.getHeight() == im2.getHeight() && im1.getWidth() == im2.getWidth());
double variation = 0.0;
for(int x = 0;x < im1.getWidth();x++){
for(int y = 0;y < im1.getHeight();y++){
variation += compareARGB(im1.getRGB(x,y),im2.getRGB(x,y))/Math.sqrt(3);
}
}
return variation/(im1.getWidth()*im1.getHeight());
}
/**
* Calculates the difference between two ARGB colours (BufferedImage.TYPE_INT_ARGB).
*/
public static double compareARGB(int rgb1, int rgb2){
double r1 = ((rgb1 >> 16) & 0xFF)/255.0; double r2 = ((rgb2 >> 16) & 0xFF)/255.0;
double g1 = ((rgb1 >> 8) & 0xFF)/255.0; double g2 = ((rgb2 >> 8) & 0xFF)/255.0;
double b1 = (rgb1 & 0xFF)/255.0; double b2 = (rgb2 & 0xFF)/255.0;
double a1 = ((rgb1 >> 24) & 0xFF)/255.0; double a2 = ((rgb2 >> 24) & 0xFF)/255.0;
// if there is transparency, the alpha values will make difference smaller
return a1*a2*Math.sqrt((r1-r2)*(r1-r2) + (g1-g2)*(g1-g2) + (b1-b2)*(b1-b2));
}
Я не смотрел, но, возможно, одна из этих библиотек обработки изображений Java также может быть полезна:
Если скорость действительно важна, я считаю, что лучшим подходом будет реализация с использованием кросс-корреляционных или функциональных дескрипторов, использующих внешнюю библиотеку.