Поиск объекта на изображении при помощи перцептивного хэша

В те времена, когда я еще верил, что программируя для себя на обеденном перерыве или после работы, можно создать свой стартап, у меня был один проект. И проект требовал такого алгоритма поиска объекта на изображении, чтобы и обучить его было быстро на новый объект, и чтобы он много вычислительных ресурсов не потреблял. Почитав статьи про перцептивный хэш (раз статья и два), я решил, а почему бы не использовать его для ограничения количества исследуемых областей изображения? И начал строить свой велосипед, вместо того чтобы использовать признаки Хаара. использовать перцептивный хэш, как фильтр областей изображения, чтобы после фильтра оставались лишь те участки, где вероятнее всего находится искомый объект. В конце статьи есть ссылка на код на C++ с использованием библиотеки OpenCV.

Что в итоге получилось?

На данном видео можно посмотреть работу алгоритма поиска объекта на изображении в действии. Синяя ограничительная рамка используется для выделения объекта на видео, когда проигрывание видео остановлено. При этом можно запомнить внешний вид объекта. Обучение алгоритма происходит моментально. Так же размеры синей ограничительной рамки влияют на максимальные и минимальные размеры окна поиска объекта на изображении. Красная ограничительная рамка выделяет на изображении участок, где скорее всего расположен искомый объект. Алгоритм работает следующим образом:

• Подготавливаем изображение к обработке (создаем интегральное изображение)
• Вычисляем перцептивный хэш участка изображения
• Проверяем флаг элемента массива с номером, равный перцептивному хэшу
• Если перцептивный хэш проходит проверку, сравниваем участок изображения с заранее подготовленными патчами

На последнем пункте возникают проблемы, так как перцептивный хэш ограничивает участок изображения не точно, и просто сранивать найденный участок изображения с изображением объекта нельзя, при малейшем сдвиге получится большая разница. Правильнее было бы найти ключевые точки на двух изображениях и провести сравнение по ним. К тому же обычный перебор патчей во время сравнения двух изображений замедляет работу алгоритма, и тем не менее полученный результат можно было бы назвать «реалтаймом».

На видео с пандой показана работа «фильтра» на основе перцептивного хэша. Красные ограничительные рамки обозначают участки изображения, где хэш совпадает с хэшем искомого объекта (или находится в пределах заданного расстояния Хэмминга). Увы, данный способ фильтрации плохо справляется с небольшими объектами на видео. Зато алгоритм хорошо себя показывает при работе с большими объектами, как например поиск лица на изображении с веб камеры ноутбука.

Особенности использования перцептивного хэша в данном алгоритме

Если мы имеем бесконечную достаточно большую память компьютера, чтобы каждое изображение можно было представить как индекс массива, то тогда сравнение двух изображений можно было бы делать за оно условие if, а в самом массиве можно было бы хранить флаг, обозначающий принадлежность данного изображения к искомому объекту.

Такой подход вполне реально применить к перцептивному хэшу.

Так как изображение, это индекс массива, то не нужно будет тратить время на поиск хэша в массиве, достаточно будет проверить условие, что данный элемент массива (хэш) принадлежит к искомому классу объектов. Посчитать хэш не затратно по времени, если исходное изображение предварительно подготовить (получить из него интегральное изображение).

Обычно для перцептивного хэша используется размер изображения 8 х 8 пикселей, или 64 бита данных. Однако, 64 бита данных имеют так много возможных комбинаций, что массив будет занимать (1.71E11 x размер ячейки) памяти. Другое дело, если взять картинку размером 5 х 5 пикселей, что будет соответствовать 2E25 = 33554432 или минимум 32 мегабайт памяти, что вполне приемлемо.

Шум вместо расстояния Хэмминга

Так как в данном алгоритме перцептивный хэш изображения искомого объекта это индекс массива, то вместо расстояния Хэмминга для оценки соответствия перцептивного хэша искомому можно заранее заполнить массив флагами, т.е. добавить шум на расстояние Хэмминга. Это сократит количество вычислений.

→ Проект на github здесь