Подскажите быстрый алгоритм поиска шаблонного изображения в изображении сильно большей размерности.
Желательно если можно регулировать еще точность поиска. Совпадения пиксел в пиксель не обязательно и скорее всего не будет,
т.к. исходные изображения могут быть разного качества.

Пока что нашел эту работу: http://www.wseas.us/e-library/conferences/2010/Harvard/MATH/MATH-091.pdf

Подход целом интересный, но не очень подходит для цветных RGB изображений. А если RGB изображения сводить к ЧБ то
происходит большая потеря данных.

Идеально было бы иметь некую хэш функцию которая могла бы для больших блоков, скажем 100x100 пикселей выдавать некую строку (числовую) и
при этом чтобы эта строка не сильно отличалась при незначительных сдвигах этого блока в большом изображении. Например, при сдвиге блока на
50 пикселей, хэш код так-же изменялся не более чем на 50%. К примеру, взяли блок с кодом "1234567890" сдвинули в лево, получили 6789055555.
Тогда я могу разбить исходный шаблон на эти коды и исходное изображение на эти блоко-коды. Потом можно с учетом возможных сдвигов свести
все к поиску подстроки в строке.

Если кто может, направьте в нужном направлении. Где можно найти соответствующие работы по теме.
Спасибо.

Здравствуйте, C0x, Вы писали:

C0x>Идеально было бы иметь некую хэш функцию которая могла бы для больших блоков, скажем 100x100 пикселей выдавать некую строку (числовую) и
Перцептивные хэш вроде подходит.
C0x>Если кто может, направьте в нужном направлении. Где можно найти соответствующие работы по теме.
C0x>Спасибо.

C0x:

C0x>Подскажите быстрый алгоритм поиска шаблонного изображения в изображении сильно большей размерности.
C0x>Желательно если можно регулировать еще точность поиска. Совпадения пиксел в пиксель не обязательно и скорее всего не будет,
C0x>т.к. исходные изображения могут быть разного качества.

Можно посчитать корреляцию через двумерную свёртку.
Математика хорошо описана в учебниках по ЦОC: использование БПФ и пр.
Хорошо параллелится.

Экстремумы в результирующей матрице соответствия исходной матрицы шаблону.
Причем негатив даже будет ловиться, если данные должным образом нормальизованы.

Подробностей не будет, ибо не помню.

Здравствуйте, C0x, Вы писали:

C0x>Идеально было бы иметь некую хэш функцию которая могла бы для больших блоков, скажем 100x100 пикселей выдавать некую строку (числовую) и
C0x>при этом чтобы эта строка не сильно отличалась при незначительных сдвигах этого блока в большом изображении. Например, при сдвиге блока на
C0x>50 пикселей, хэш код так-же изменялся не более чем на 50%. К примеру, взяли блок с кодом "1234567890" сдвинули в лево, получили 6789055555.
C0x>Тогда я могу разбить исходный шаблон на эти коды и исходное изображение на эти блоко-коды. Потом можно с учетом возможных сдвигов свести
C0x>все к поиску подстроки в строке.

Я не совсем в теме, но через "строки" по хэшу изображения ты всё равно не сможешь искать. Между хешами придётся считать битовое расстояние Хэмминга. Расстояние можно наверное также считать и со сдвигом, но не знаю будет ли сдвиг иметь смысл для всяких "перцептивных" хэшей. Скорее всего нет. Поэтому для сдвига подойдут хэши типа AHash, DHash или Block Hash. Опять же сдвиг ты сможешь посчитать только относительно "разрешения" хэша, что тоже с пракической точки зрения считать такой "сдвиг" не имеет большого смысла.

В конечном итоге возможно имеет смысл выделять features из изображений. Что-то типа такого:
https://trackingjs.com/examples/brief.html

Но это уже далеко не поиск подстроки.