Есть изображение среднего размера ~ 800px x 800px, требуется найти на данном изображении все фрагменты изображения, которые приблизительно похожи на выделенный пользователем на изображении фрагмент. Как это лучше реализовать? Простым перебором(т.е проходом по всем пикселам) получилось крайне долго. 
Попробовал уменьшить изображение и искать на уменьшенном, получилось неточно, потому-что в основном требуется находить небольшие фрагменты.

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

Нашел что это можно сделать при помощи:
1. Алгоритма поиска на строках
2. Двумерной корреляции

Но примеров или детального описания ни того другого найти не могу, может кто-то знает где их можно посмотреть?

Если с помощью строк, то наверно копать в сторону нечёткого поиска:
http://algolist.ru/search/fsearch/index.php

Сенкс, но строки наверно не подойдут, мне важен так же и поиск не полностью идентичных фрагментов.
По поводу корреляции, может кто-нибудь примерно алгоритм объяснить? Этот тот же самый перебор, только сравнение идет не попиксельно а сравниваются корреляционные коэффициенты матриц?

JimWeb
Подожди, я и не говорил про полностью идентичные 
Нечёткий поиск - это как раз поиск фрагментов, не сильно отличающихся от образца ("не сильно" определяется некой функцией сравнения, например, расстоянием хэмминга).

maxdiver, ага уже понял, спасибо за идею, только реализации у нечеткого поиска достаточно громоздкие

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

Возможно стоит посмотреть в сторону вейвлетов...