Поиск изображения на картинке с помощью java?

то, что я хочу, анализирует входные данные с экрана в виде изображений. Я хочу, чтобы можно было идентифицировать часть изображения в увеличенном изображении и получить его координаты в большей картине. Пример:

нужно было бы найти в

И результатом будет верхний правый угол изображения в большом изображении и в нижней левой части части на большой картинке. Как вы можете видеть, белая часть изображения не имеет значения, мне в основном нужна только зеленая рамка. Есть ли библиотека, которая может сделать что-то подобное для меня? Время выполнения не является проблемой.

То, что я хочу сделать, это просто генерировать несколько случайных координат пикселей и распознавать цвет на большой картинке в этом положении, чтобы быстрее распознать зеленый квадрат. И как бы это снизило производительность, если белый ящик посередине прозрачен?

Вопрос был задан несколько раз на SO, как кажется без единого ответа. Я нашел, что нашел решение на http://werner.yellowcouch.org/Papers/subimg/index.html. К сожалению, на С++ и я ничего не понимаю. Было бы неплохо иметь реализацию Java на SO.

Ответ 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 также может быть полезна:

Если скорость действительно важна, я считаю, что лучшим подходом будет реализация с использованием кросс-корреляционных или функциональных дескрипторов, использующих внешнюю библиотеку.

Ответ 2

Вы хотите найти блок изображения по маске/границам.

Это можно сделать без внешней библиотеки. На низком уровне каждое изображение представляет собой матрицу чисел, ваша маска также является матрицей чисел. Вы можете просто линейно сканировать большую матрицу и найти область, которая следует правилам, определенным вашей маской.

Пример:

Большая матрица:

1 0 1 1 1 1 
0 1 0 1 0 0
0 0 0 1 1 1
0 1 1 0 0 0

Mask:

1 1 1
1 0 0
1 1 1

Применяет этот алгоритм, который вы обнаруживаете согласованный блок в большой матрице в верхнем правом углу, который дает вам начальные/конечные матричные индексы, и вы можете рассчитать эти значения в пикселях.

В реальной задаче у вас не будет набора номера [0, 1], но гораздо большего - byte например ([0, 256]). Чтобы алгоритм работал лучше, соответствие означает не точное сопоставление чисел, но возможно с некоторыми отклонениями + -5 или что-то вроде этого.