Поиск подмножеств изображения между двумя изображениями - PullRequest
Новая
       19

Поиск подмножеств изображения между двумя изображениями

0 голосов
/ 09 сентября 2011

Я работаю над способом обработки аппаратной растровой анимации.В качестве входных данных у меня есть последовательность изображений простого растрового изображения (это не видео, это больше похоже на простые формы, даже если они могут содержать растровые заливки).Я делаю текстурный атлас этой анимации (чтобы его можно было быстро визуализировать с помощью графического процессора), и поскольку в этой последовательности иногда большая часть ее остается неподвижной, а небольшая ее часть анимируется, мне нужен алгоритм, который может найти«общие части» между двумя изображениями, поэтому я могу сэкономить память.

Изображения могут иметь разный размер (например, если объект растет или уменьшается), поэтому мне нужен способ обнаружить самый большойобщая зона между двумя.Я видел этот ответ , и он частично решает мою проблему.Я хотел бы знать, однако, если уже есть лучший алгоритм для моего случая, особенно потому что размеры могут варьироваться, одно изображение не обязательно содержится в другом, но мне нужно найти общие части междудва.

1 Ответ

1 голос
/ 10 сентября 2011

Одна проблема, которую я вижу, состоит в том, что одно изображение может содержаться разными способами в другом, как вы определяете правильный ответ?

Должно ли оно быть в реальном времени?Если нет, то вы можете выполнить простой поиск O (n ^ 4) с помощью фитнес-функции.

Фитнес-функцией может быть ошибка между изображениями (что дает алгоритм ^ 8).

ОБНОВЛЕНИЕ: Неправильный анализ меня извините.Поиск - n ^ 2, а функция пригодности - n ^ 2, что дает n ^ 4.

Весь алгоритм должен выглядеть примерно так: 

w1 = width of image 1
w2 = width of image 2
h1 = height of image 1
h2 = height of image 2

for x = -w1 to w1+w2
  for y = -h1 to h1+h2
    find max fitness(x,y)

fitness(xc,yc){
  m=0
  for each x where image 1 overlaps image 2 displaced by xc
    for each y where image 1 overlaps image 2 displaced by yc
      if (image1[x][y] == image2[x+xc][y+yc])
        m += 1
  return m
}

ОБНОВЛЕНИЕ: Модифицированная функция пригодности длянайдите количество совпадений, а затем попытайтесь найти наибольшее число совпадений.

...