Столкнулся с задачей поиска одинаковых изображений. Как и во всём новом, получил избыток смежной, не нужной мне информации, множество английской литературы и прочего.
Итак, мне хотелось бы получить наводку на достаточно качественный и быстрый алгоритм, который, однако, не является из ряда вон сложным. То есть, к абсолютному качеству и большому функционалу не стремлюсь (мне это не нужно), но алгоритм должен соответствовать таким условиям:
Находит не просто похожие, а идентичные объекты, причём под идентичными подразумевается не почти-копия изображения как такового, а скорее отображение точно такого же предмета (near-duplicates): он может повернуться, наклониться, сдвинуться вбок, стать темнее/ярче, покрыться сторонними деталями и тому подобное, но это с большой вероятностью один и тот же предмет;
То есть, следует работать не только с низкими частотами, которые, грубо говоря, определяют структуру, ведь тут важны более-менее однозначно характеризующие объект детали, которые теряются, если переходить к низким частотам;
Алгоритм работает куда меньше секунды, желательно настолько быстро, чтобы успевать сравнивать хотя бы пару десятков изображений с такой же парой десятков, то есть, качественность важна, но скорость - важнее;
Исходные картинки сами по себе обычно не очень большие, а их количество, думаю, будет сравнительно небольшим, предположительно, в рамках нескольких сотен;
Исходные картинки - чёрно-белые и безо всякой дополнительной обработки, разве что кроме нормализации; то есть, учитывать, что алгоритм должен уметь искать какие-то хорошенько и по-разному обработанные, но одинаковые по содержанию, изображения, нет необходимости;
Огромным плюсом будет существование не смутного описания алгоритма, а чего-либо конкретного, в оптимуме - псевдокод, в идеале - код.
Да, прошу направления, какой алгоритм раскапывать, это не требование в духе "сделайте за меня всё", это - "более знающие, пожалуйста, сделайте оптимальную выборку, чтобы я мог нормально сориентироваться, так как я сейчас дезориентирован".
Ответ
Из комментариев к вопросу стало понятно, что в целом суть задачи сводится к вычислению межкадровой разницы и поиску соответствия локальных изменений отдельных единиц интереса во времени. Проще говоря, если в кадре смещается несколько объектов, то необходимо различать, какое из смещений к каковому объекту относится.
Детектор движения
Как только речь заходит о межкадровой разнице, то в качестве решения сразу всплывает детектор движения. В составе фреймворка OpenCV имеется прекрасный пример, демонстрирующий возможности этого инструмента, да и Youtube переполнен соответствующими роликами. В том числе с вычислением вектора движения и связанных компонент, что составляют части целого объекта.
Однако у детектора движения имеются два очевидно слабых момента. Первый заключается в том, что если съёмка ведётся на улице, то фактор изменения фона (облачность в солнечный день или сильный ветер камеру на столбе трясёт) приводит к тому, что относительно малые пиксельные изменения объектов теряются на фоне более глобальных изменений во всём кадре. И это практически никогда не удаётся победить.
Второй момент - это прекращение движения объекта. Полное, либо просто существенное снижение скорости. И если автомобили на скоростной трассе редко стремятся остановиться, то те же самые автомобили на оживлённом перекрёстке будут соблюдать правила дорожного движения. Пешеходы же, так вообще могут следовать одним только им известной логике, нарушая порой даже самые лояльные законы перемещения в пространстве. Получасовое преодоление бордюра на карачках - это одна из самых безобидных картин, которую будет вынужден понять и принять цифровой разум алгоритма.
Исходя из обозначенных моментов, можно сделать вывод, что детектор движения - это вполне себе подходящее решение, но только лишь при наличии одного условия: скорость смещения объектов интереса должна быть всегда существенно выше, нежели чем скорость изменения фона. Если это правило не соблюдается, то функционал детектора движения необходимо дополнить обработчиками исключительных ситуаций, в которых объект интереса может начать терять в скорости, либо полностью остановиться.
Таким обработчиком исключительной ситуации может являться использование так называемых особенных точек (feature points) на той части изображения, которая содержит медленно изменяемый объект. Как только детектор движения начнёт фиксировать резкое уменьшение количества пикселей (значение подбирается эмпирически), изменившихся между двумя кадрами, то в дело вступают особенные точки, которые и будут следить за местоположением объекта до начала возобновления фазы его активного движения.
Особенные точки изображения в противовес детектору движения в целом неинвариантны к быстрому изменению объекта в естественной среде, но в то же время позволяют относительно легко его обнаруживать от кадра к кадру, если тот не претерпевает существенных изменений.
Оптический поток
Вычисление оптического потока является альтернативой вышеуказанному подходу. В какой-то мере это решение - компромисс использованию особенных точек и детектора движения.
С одной стороны, вычисление оптического потока становится чрезвычайно затруднительно, если объект интереса смещается очень быстро при некоей стандартной скорости кадрового захвата, но в то же самое время неплохо себя чувствует на средних и малых скоростях движения. В случае же полной неподвижности объекта может проявиться погрешность в детекции его местоположения. Эти нюансы индивидуальны для каждого алгоритма вычисления оптического потока.
Например алгоритм Лукаса-Канаде, производящий вычисление сдвига объекта по предварительно отобранным точкам, может запросто потерять этот самый объект просто по той причине, что у того большое количество пикселей в некоторой позиции и её окрестностях имеют близкое значение. Это вполне себе может произойти, если рассматривать в качестве объекта интереса автомобиль, крыша, двери и прочие части которого имеют близкие по цвету области и не выражены какими-либо особенностями. Но в связи с тем, что точек для сравнения число ограниченное (значительно меньше, нежели чем пикселей в интересующей области), то сам процесс поиска производится на высокой скорости с минимальными затратами вычислительных ресурсов.
В противовес - алгоритм Фарнебека, производящий вычисление оптического потока для всех пикселей заданной области изображения. С ним обычно наблюдается более точный результат, но и существенное потребление вычислительных ресурсов.
Вместо заключения
В ответе неспроста упоминается детектор движения как часть некоего комплексного решения. Несмотря на его ограничения, в целом он имеет одно значительное преимущество, которое зачастую становится принципиальным в отдельных задачах - детектор движения позволяет определять границы объектов. Ни оптический поток, ни особенные точки таковой информации не дают, а значит разделение рядом расположенных объектов будет весьма затруднительно.
Комментариев нет:
Отправить комментарий