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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Кто есть кто

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

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

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

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

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

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

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

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

Согласованный фильтр 2D, 2D Matched Filter

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

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

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

Согласованный фильтр 2D, 2D Matched Filter

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

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

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

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

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

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">