Быстрый поиск паттерна в BMP изображении...

← →
ForumReader (2009-04-25 14:19) [0]

Приветствую.

Может кто направит на путь истинный: есть задача - найти в bmp изображении (любого размера) заранее известный паттерн размером, скажем, 20х20 пикселов. Даже используя специализированные графические библиотеки с быстрым доступом к данным внутри BMP (GR32 и ей подобные) скорость оставляет желать много лучшего :(

Правда я и ищу по-тупому - при совпадении первого пикселя по цвету, сравниваю второй с данными из паттерна и так далее. Но это очень долго...

Я чувствую, что есть красивый и быстрый способ, хоть направление подскажите, пожалуйста :(

← →
Sapersky (2009-04-26 10:08) [1]

Могу предложить не изящный способ, а скорее "костыль", но работать должно: создаём уменьшенные копии паттерна и картинки, проверяем сначала их, если совпало, тестируем полноразмерную копию в том же месте.

← →
Pavia © (2009-04-26 14:42) [2]

> заранее известный паттерн

А четкое сравнение или нет? Т.шаблон имеет точно такиеже цвета что и в картинке на которой ищем или нет?

> Правда я и ищу по-тупому - при совпадении первого пикселя
> по цвету, сравниваю второй с данными из паттерна и так далее.
> Но это очень долго...

Это не долго, если при несовпадении пикселей делать выход из цикла.

← →
ForumReader (2009-04-26 15:00) [3]

> А четкое сравнение или нет? Т.шаблон имеет точно такиеже
> цвета что и в картинке на которой ищем или нет?

Мы ищем точное соответствие. И нужно знать - оно либо есть, либо его нет.

> Это не долго, если при несовпадении пикселей делать выход
> из цикла.

ммм... ну как сказать... понятное дело, что при несовпадении пиксела из паттерна я делаю выход из цикла сравнения и бегу дальше по бмпшке. Но все равно это... ну... не красиво, что ли :( Дожно быть более красивое решение, я уверен...

гуглить 2D pattern matching.
Многие алгоритмы развиты на базе известных одномерных алгоритмов (поиска подстрок)
Точные названия алгоритмов не подскажу, некоторые фамилии - Takaoka, Regnier, Polcar

Кроме того, двумерная кросс-корреляция может помочь (в том числе и при неточном соответствии)

Быстрый поиск паттерна в BMP изображении... Найти похожие ветки