Параллельно-рекурсивные КИХ-фильтры для обработки изображений Текст научной статьи по специальности «Математика»
Рассматривается класс цифровых фильтров с конечной импульсной характеристикой, обеспечивающих снижение вычислительной сложности обработки изображений за счет параллельно-рекурсивной реализации. Строится общий вид фильтров, приводятся примеры базисных функций для разложения их импульсных характеристик, даются оценки вычислительной сложности обработки одномерных и двумерных сигналов.
Похожие темы научных работ по математике , автор научной работы — Сергеев В. В.
Текст научной работы на тему «Параллельно-рекурсивные КИХ-фильтры для обработки изображений»
ПАРАЛЛЕЛЬНО-РЕКУРСИВНЫЕ КИХ-ФИЛЬТРЫ ДЛЯ ОБРАБОТКИ ИЗОБРАЖЕНИЙ
В основу многих процедур цифровой фильтрации и анализа изображений положена операция линейной обработки «скользящим окном», которая заключается в преобразовании дискретизированного двумерного сигнала КИХ-фильтром - линейной системой с постоянными параметрами, имеющей конечную (ограниченную по протяженности) импульсную характеристику [1.2]. Как известно, значения сигнала на выходе КИХ-фильтра являются результатом цифровой свертки входного сигнала с импульсной характеристикой фильтра и могут быть вычислены взвешенным суммированием отсчетов входного сигнала в пределах окна обработки. Однако такое вычисление свертки С так называемая прямая реализация КИХ-фильтра) имеет практический смысл лишь для малых размеров окна, т. е. короткой импульсной характеристики, поскольку обьем вычислений здесь пропорционален числу ненулевых отсчетов последней. Для больших окон (в задачах восстановления сильно расфокусированных изображений, обнаружения пространственно протяженных объектов и т. д. ) прямое вычисление свертки оказывается чрезмерно трудоемким. Разработанные многочисленные алгоритмы быстрой свертки для КИХ-фильтров общего вида [3] также далеко не всегда решают проблему вычислительной сложности. В этом контексте представляется удивительным, что до сих пор в обработке изображений не находят широкого применения алгоритмы, воплощающие прозрачную идею параллельной рекурсивной реализации КИХ-фильтров [4, 5]. Такие алгоритмы способны резко (на порядок и более) сократить необходимый объем вычислений при сохранении высокого качества обработки двумерного сигнала [б].
Следует заметить, что подход к рекурсивному построению цифровых линейных фильтров с конечной импульсной характеристикой сложился достаточно давно. Именно он реализуется известными структурами КИХ-фильтров в форме с частотной выборкой [1]. Рекурсивные КИХ-фильтры иногда применяются при скользящем спектральном анализе сигналов [7, 8]. Но только в работе [4] (и позже в [5]) обоснована, наконец, возможность и целесообразность использования данного подхода для решения широкого класса задач обработки одно- и многомерных сигналов.
Вместе с тем и в [4, 5] не раскрываются все аспекты синтеза параллельно-рекурсивных КИХ-фильтров. Выглядит неоправданно суженным класс рассматриваемых базисов разложения импульсных характеристик (правда, впоследствии этот недостаток отчасти устранен в работе [9]). Принятый аппроксимационный принцип расчета параметров фильтров (с анализом точности представления «требуемой» импульсной характеристики) не всегда хорошо согласуется с критериями эффективности . конкретных процедур обработки
изображений. Отсутствуют количественные данные, демонстрирующие выигрыш от параллельно-рекурсивной реализации КИХ-фильтров в различных практических ситуациях.
Предлагаемый цикл статей представляет собой попытку восполнения имеющихся пробелов в вопросах расчета и обоснования применимости параллельно-рекурсивных КИХ-фильтров при обработке изображений «скользящим окном». Ниже описывается общая структура рассматриваемых фильтров, обсуждается проблема выбора рекурсивно реализуемых базисов для их импульсных характеристик. В статье [10] решается задача расчета фильтров для некоторых типовых процедур обработки сигналов. В [6] приводятся оценки эффективности этих процедур в сопоставлении с аналогичными оценками для прямой реализации КИХ-фильтров. Статья [11] содержит описание и некоторые результаты исследования одного из вариантов аппаратной реализации двумерного параллельно-рекурсивного КИХ-фильтра для обработки изображений.
Рассмотрим сначала более простой и наглядный случай одномерных сигналов. Преобразование КИХ-фильтром бесконечной последовательности отсчетов входного сигнала х(п) в выходную последовательность у(п) описывается соотношением свертки
где h(m) - импульсная характеристика фильтра, равная нулю вне интервала [М, M+N-1]; величина М задает положение окна обработки относительно формируемого выходного отсчета, а N - размер окна. В общем случае на значения импульсной характеристики в пределах окна не налагается никаких ограничений. Однако мы, преследуя цель ускоренного вычисления свертки (1), сузим класс КИХ-фильтров и будем рассматривать только те из них, которые представляются в виде К параллельно соединенных звеньев (при К « N) и следовательно, для которых