Главная > Разное > Обработка изображений и цифровая фильтрация
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

3.3. Краткое содержание и выводы

Рассмотрены четыре метода проектирования двумерных нерекурсивных цифровых фильтров. Первые три — применение функций окна, частотная дискретизация и прямое применение линейного программирования — являются прямыми обобщениями соответствующих методов проектирования одномерных фильтров. Только третий из указанных методов потенциально позволяет проектировать оптимальные фильтры. Четвертый метод — новый алгоритм, который был специально разработан для решения задач проектирования двумерных фильтров. Этот метод превосходит метод прямого применения линейного программирования, поскольку: а) «хорошие» аппроксимации обычно вычисляются быстро, причем эти аппроксимации всегда можно улучшить просто путем вычисления дополнительных итераций; б) наилучшие аппроксимации удается получить даже при чрезвычайно высокой плотности множества точек; в) обеспечивается возможность расчленить объемную задачу линейного программирования на ряд небольших задач. К сожалению, новый алгоритм оказался не таким эффективным с вычислительной точки зрения, как ожидалось.

Один из самых важных и глубоких выводов, сделанных в результате проведенного исследования, состоит в том, что задача проектирования двумерных фильтров в ее общем виде существенно сложнее задачи проектирования одномерных фильтров. Причин для этого много. Наиболее важной, по-видимому, является та, что множество функций, используемых для вычисления аппроксимации, не удовлетворяет условию Хаара (п. 3.1.2). Вследствие этого невозможно написать общую интерполяционную формулу, аналогичную одномерной интерполяционной формуле Лагранжа [27—29, 32]. Более того, поскольку множество функций не удовлетворяет условию Хаара, вопрос об единственности наилучшей аппроксимации становится исключительно сложным [33]; в одномерном случае наилучшая аппроксимация является единственной. Наконец, теорема чередования, которая является одной из важнейших теорем теории одномерной аппроксимации, неприменима к многомерному случаю. Это объясняется тем фактом, что функции двух и более переменных обычно не удовлетворяют условию Хаара,

Двумерная задача труднее одномерной еще и потому, что в двумерном случае обычно приходится иметь дело с большим массивом данных. Поэтому в двумерном случае значительно возрастают требования к объему памяти и время вычислений. В качестве примера рассмотрим задачу вычисления частотной характеристики фильтра. В одномерном случае действует следующее практическое правило: частотную характеристику следует вычислять на множестве точек, число которых в 20 раз превышает число отсчетов импульсной характеристики фильтра. Таким образом, если импульсная характеристика фильтра содержит 100 отсчетов, то частотную характеристику следует вычислять на множестве 2000 точек. Во всех примерах данной работы частотная характеристика фильтров вычислялась на множестве точек, т. е. общее число отсчетов частотной характеристики составляет 65 536.

Существует ряд алгоритмов проектирования одномерных фильтров, основанных на отыскании экстремумов, т. е. локальных максимумов и минимумов функции ошибки. Эта операция также является важнейшей составляющей нового алгоритма, который был специально разработан для проектирования двумерных фильтров. Следует указать, что некоторые явления возникают только в двумерном случае, и они значительно усложняют отыскание экстремумов в сравнении с одномерным случаем. Первое такое явление — наличие гребней в функции ошибки. Это явление, очевидно, не может существовать в одномерном случае. Как отмечается в п. 3.2.4, оно существенно усложняет задачу отыскания экстремумов по сравнению с другими возможными случаями. Второе явление, влияющее на поиск экстремумов, состоит в существовании почти горизонтальных границ (имеются в виду границы полос или границы в функции ошибки. Отыскание локальных максимумов и минимумов на таких границах представляет собой одномерную задачу. Однако в данном случае задача сложнее, чем в одномерном случае, когда уклонение функции ошибки по крайней мере равно максимальному абсолютному значению ошибки на последнем множестве точек с ограничениями. В двумерном случае ошибка вдоль таких границ может сохранять почти постоянное значение. При этом очень трудно отыскать локальные максимумы и минимумы вдоль таких границ.

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

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

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

Сразу же возникает вопрос о том, насколько задача проектирования трехмерного фильтра окажется сложнее задачи проектирования двумерного фильтра. Все теоретические положения в п. 3.1.2, относящиеся к проектированию фильтров, были сформулированы применительно к задаче проектирования двумерных фильтров. Это было сделано исключительно ради удобства изложения. Все полученные результаты, применимые к двумерному случаю, в равной степени применимы к трех-, четырех- и -мерному случаям. Как и в двумерном случае, множество функций, используемое для вычисления аппроксимации, в

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

От автора. Представленная работа была выполнена в Линкольновской лаборатории Массачусетского технологического института и финансировалась министерством военно-воздушных сил. Автор выражает признательность д-ру Голду, д-ру Хофстеттеру, проф. Хуангу, проф. Штёлину, проф. Оппенгейму и проф. Штейглицу за помощь, оказанную ими при выполнении этой работы. Данная глава основана на материалах диссертации «Двумерные нерекурсивные цифровые фильтры», представленной на рассмотрение кафедры электротехники Массачусетского технологического института 4 мая 1973 г. на соискание степени доктора философии.

Литература

(см. скан)

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление