Согласованный фильтр 2D: поиск соответствия в изображении

Согласованную фильтрацию можно рассматривать как во временной, так и в частотной области.

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

Еще нагляднее физический смысл проявляет себя в частотной области: согласованный фильтр «доворачивает» спектральные составляющие сигнала ровно настолько, чтобы они складывались синфазным образом, достигая максимального выходного эффекта. Чтобы доворот происходил в направлении компенсации, используется комплексно-сопряженное значение передаточной функции фильтра.

Часто реализацию согласованного фильтра выполняют в частотной области, используя наработанные библиотеки быстрого преобразования Фурье (БПФ).

Вот пожалуй и все, что хотелось бы сказать про согласованный фильтр (СФ). Поехали дальше.

От времени к пространству

Что скажете, если мы займемся фильтрацией пространственных данных? Это немного непривычно, поскольку мы обычно связываем сигнал с изменениями во времени. С другой стороны, когда смотрим на график этого сигнала то видим только рисунок, и ничего более. И фактически работаем с этим рисунком. Только это будет одномерная обработка, где ось времени будет просто абстрактной осью x.

С двумерными изображениями физический смысл ускользает. Как представить этот сигнал изменяющимся во времени, когда он содержит уже две «псевдовременные» оси? Поэтому нам лучше оторваться от привязки ко времени и воспринимать сигнал тем, чем он является — 2D изображением. Что интересно, для многомерных сигналов также существует понятие пространственных частот, и это активно используется при изучении работы объемных антенных решеток.

Маджонг: найти кубик

Чтобы наше повествование не выглядело слишком солидным и серьезным, выберем в качестве входного сигнала изображение россыпи кубиков Маджонг:

Исходная сцена для поиска кубика, соответствующего шаблону

Поставим себе задачу: найти в этой россыпи определенный кубик, например такой:

Шаблон для поиска

Как вы догадались, этот кубик, который я буду использовать в качестве шаблона, просто скопирован из исходной сцены — россыпи. Вот кстати, можно сразу немного поиграть в Маджонг: найдите этот шаблон на сцене!

При этом будем считать, что окружающие кубик куски — это тоже часть шаблона. Не будем обрезать его до идеального, ведь лучшее — враг хорошего )

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

Теперь пришло время дать правильные названия всем действующим лицам и участникам.

Кто есть кто

Итак, наша сцена — это смесь сигнала и помехи. Сигнал — кубик, который мы заприметили (надеюсь что вы уже увидели его на сцене), все остальное — это помеховый фон.

Наша задача: найти этот кубик на сцене с помощью 2D согласованного фильтра, и не только найти, но и сразу определить его местоположение. Структура СФ будет определяться шаблоном для поиска — этим же кубиком, который на этот раз сам по себе.

Поскольку в этой задаче нет никакого времени, попробуем обозначить шаги ее решения в частотной области. СФ работает следующим образом:

В результате, компоненты сцены соответствующие шаблону попадут на выход фильтра, а те компоненты которым нет соответствия будут подавлены. Все достаточно просто.

Перед фильтрацией необходимо найти пространственные спектры сцены и нашего опорного кубика:

Запускаем интерпретатор Питона (да, это был именно он) и смотрим на результаты.

Результат работы согласованного фильтра 2D

Я добавил в программу небольшой вспомогательный код, чтобы отмечать зеленой рамкой на сцене месторасположение максимального отклика на выходе СФ. На рисунке сцена (сигнал+шум) расположена слева, отклик согласованного фильтра — справа. Белый цвет соответствует максимальному отклику.

Результат работы согласованного фильтра 2D для поиска шаблона

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

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

Результат работы согласованного фильтра 2D со сценой, содержащей два шаблона

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

Может возникнуть такой вопрос: если помеха отфильтрована, почему на выходе СФ мы не наблюдаем чистый сигнал? Вот такой он, согласованный фильтр: использует всю информацию о сигнале, и на выходе ее уже не остается. Только уровни, которые только и остается что сравнивать. Если бы на выходе мы наблюдали признаки формы сигнала, это означало бы, что СФ не использовал эту информацию в обработке.

Также открою маленький секрет: выход СФ есть не что иное, как двумерная корреляционная функция сцены и шаблона.

Эта статья — аэродром подскока, который мы используем позже, когда начнем распознавать маркеры системы автоматической визуальной посадки беспилотников. Эта игрушка будет посильней Маджонга!