Подожди, я и не говорил про полностью идентичные
Нечёткий поиск - это как раз поиск фрагментов, не сильно отличающихся от образца ("не сильно" определяется некой функцией сравнения, например, расстоянием хэмминга).
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Поиск фрагментов по изображению |
| Автор: JimWeb 14.5.2008, 01:57 |
| Есть изображение среднего размера ~ 800px x 800px, требуется найти на данном изображении все фрагменты изображения, которые приблизительно похожи на выделенный пользователем на изображении фрагмент. Как это лучше реализовать? Простым перебором(т.е проходом по всем пикселам) получилось крайне долго. Попробовал уменьшить изображение и искать на уменьшенном, получилось неточно, потому-что в основном требуется находить небольшие фрагменты. |
| Автор: SoWa 14.5.2008, 05:12 |
| Одно время нам говорили, что это возможно реализовать с помощью автоматов. Но как именно- я сейчас сказать не могу. |
| Автор: JimWeb 14.5.2008, 13:02 |
| Нашел что это можно сделать при помощи: 1. Алгоритма поиска на строках 2. Двумерной корреляции Но примеров или детального описания ни того другого найти не могу, может кто-то знает где их можно посмотреть? |
| Автор: maxdiver 14.5.2008, 13:19 |
| Если с помощью строк, то наверно копать в сторону нечёткого поиска: http://algolist.ru/search/fsearch/index.php |
| Автор: JimWeb 14.5.2008, 16:27 |
| Сенкс, но строки наверно не подойдут, мне важен так же и поиск не полностью идентичных фрагментов. По поводу корреляции, может кто-нибудь примерно алгоритм объяснить? Этот тот же самый перебор, только сравнение идет не попиксельно а сравниваются корреляционные коэффициенты матриц? |
| Автор: maxdiver 14.5.2008, 18:55 |
| JimWeb Подожди, я и не говорил про полностью идентичные Нечёткий поиск - это как раз поиск фрагментов, не сильно отличающихся от образца ("не сильно" определяется некой функцией сравнения, например, расстоянием хэмминга). |
| Автор: JimWeb 19.5.2008, 19:20 |
| maxdiver, ага уже понял, спасибо за идею, только реализации у нечеткого поиска достаточно громоздкие |
| Автор: sergejzr 19.5.2008, 19:56 | ||
Я так понимаю, нашлось больше чем надо и все правильные были в числе нашедшихся? Тогда просто делай двухступенчато. Т.е сперва ищи на уменьшенном, а потом проверяй найденные на оригинале. Возможно стоит посмотреть в сторону вейвлетов... |
