Поиск наилучшего соответствия растрового изображения из набора

Question

У меня есть набор A маленьких растровых изображений одинаковых размеров, скажем, 8x8.Один бит на позицию.Набор состоит из пары сотен таких растровых изображений.

Далее у меня есть бесконечный поток миллионов растровых изображений ... и для каждого из них мне нужно найти растровое изображение из набора A, которое соответствуетЛучший.Я, вероятно, не найду идеальную пару.Хорошим совпадением является тот, который выглядит похожим, как картина.Т.е. битовая карта со всеми установленными «самыми левыми» битами является плохим совпадением для битовой карты со всеми установленными самыми правыми битами.Установлено одинаковое количество битов, но их позиция также должна быть принята во внимание.Растровое изображение, смещенное на один шаг вправо, не имеет точно совпадающих битов, но оно будет выглядеть очень похоже на оригинал, так что это будет довольно хорошее совпадение.Сдвиньте его еще немного, и он больше не будет соответствовать так хорошо.

Так ... это может быть приближением, это может быть нечетко.Скорость предпочтительнее совершенства.Я посмотрел на алгоритм индекса SSIM, который измеряет сходство между изображениями, но я думаю, что это излишне, и мне, вероятно, нужно что-то более специализированное.

Если я могу сделать предварительный расчет, а затем просто использовать какие-то таблицы поиска,отлично подходит для работы, но я не уверен, как бы я это сделал.В этом случае хеширование будет бесполезным ...

Любая помощь будет принята с благодарностью!

Answer 1

Прямая мера сходства между двумя двоичными изображениями - это расстояние Хэмминга (т.е. каждая пара соответствующих пикселей получает одинаковый вес).Это неявно учитывает их геометрическое расположение, но не справляется со сдвигами.

Чтобы справиться со сдвигами, я полагаю, что вы не можете избежать явного смещения, тогда как сравнение.Если вы ограничиваетесь сдвигами на ± 1, это подразумевает в общей сложности 9 сравнений вместо 1. Работа с поворотами или масштабированием кажется дорогой / бессмысленной для таких крошечных изображений.

Чтобы ускорить поиск, вы можетеПодумайте о грубом подходе: формируйте уменьшенные изображения, добавляя пиксели в блоках 2x2, чтобы получить 4x4, затем 2x2 и даже 1x1 сокращения.Эти thumnails больше не будут двоичными, но общее количество битов будет уменьшаться.Идентичные изображения будут иметь идентичные сокращения, а похожие или смещенные изображения будут иметь аналогичные сокращения.

Теперь вы можете организовать базу данных изображений в виде дерева таким образом, чтобы каждое изображение с полным разрешением указывало на его уменьшение и т. Д. Рекурсивно.Затем, чтобы сопоставить данное изображение, сформируйте миниатюру 1x1, выберите ближайший совпадение (я) в базе данных и продолжайте работу с потомками, постепенно увеличивая сокращение.