Находите ограничивающую рамку разницы между двумя изображениями? - PullRequest
Новая
       69

Находите ограничивающую рамку разницы между двумя изображениями?

0 голосов
/ 11 марта 2012

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

Edit: изображения будут снимками экрана. Я хочу найти минимальную ограничивающую рамку для измененной области, поскольку в «за пределами этой рамки ничего не изменилось».

1 Ответ

1 голос
/ 11 марта 2012

Если вам нужен только один ограничивающий прямоугольник, вы, безусловно, можете сделать это лучше, чем «грубая сила» (всегда проверяя все пиксели, 2 * w * h операции), по крайней мере, если есть различия между изображениями. Просто найдите 4 первых пикселя строки / столбца, начиная с 4 разных границ. Псевдокод: 

bounding_box_y1 = -1;
loop y = 1..h {
 loop x = 1..w {
   if image1(x,y) != image2(x,y) {
     bounding_box_y1 = y
     exit loops
   }
 }
}

Приведенный выше псевдокод проходит по строкам изображения, начиная с верхней строки, пока не находит другой пиксель, возвращая bounding_box_y1. Просто добавьте еще 3 цикла (строки, начинающиеся снизу => bounding_box_y2, столбцы, начинающиеся слева => bounding_box_x1, столбцы, начинающиеся справа => bounding_box_x2), и вы получите координаты ограничивающего прямоугольника.

Этот алгоритм по-прежнему выполняет 2 * w * h операций для идентичных изображений (обратите внимание, что в этом случае bounding_box_y1 останется -1, и вы можете пропустить дополнительные 3 цикла), но будет намного быстрее, если есть различия на изображениях (в лучшем случае проверяются только 4 угловых пикселя).

РЕДАКТИРОВАТЬ: После того, как я увидел, что ваш вопрос отредактирован, у меня появилась идея другого подхода: если вы сравниваете изображение несколько раз с другими изображениями, вы можете сохранить дополнительную информацию контрольной суммы, например, Хранение контрольных сумм 16x16 пиксельных областей потребует некоторого дополнительного пространства для хранения, но сравнение контрольных сумм вместо пикселей намного быстрее и дает «оценочную» оценочную коробку - вы можете либо использовать ее напрямую, если можете жить с ней, либо уточнить ее впоследствии. В любом случае это будет намного быстрее, чем описанный выше подход, особенно для наихудших сценариев. Тем не менее, это зависит от ваших настроек и является компромиссом между размером и скоростью.

...