Вейвлет-преобразование: 4.4. Банк фильтров

4.4. Банк фильтров

Матричное определение преобразования Хаара будет использовано в этом параграфе для введения понятия банка фильтров [Strang, Nguyen 96]. Будет показано, что преобразование Хаара можно интерпретировать как банк, состоящий из двух фильтров: один пропускает низкие частоты, а другой высокие. Будет дано объяснение термину «фильтр», а также показано, как простая идея банка фильтров ложится в основу концепции поддиапазонных преобразований [Simoncelli и др. 90]. Конечно, преобразование Хаара является простейшим вейвлетным преобразованием, которое здесь употребляется для иллюстрации новых идей. Однако, его использование в качестве банка фильтров не очень эффективно. В конкретных приложениях используются более сложные множества фильтров, однако общая идея остается без изменений.

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

Заметим, что пределы суммирования зависят от выбора последовательностей и . Независимой переменной является время , поэтому удобно считать, что входная и выходная последовательности заданы при всех временах . Итак, используется обозначения

причем центральное значение «» задает входной символ в нулевой момент времени , величины и определяют входные символы при и , а, кроме того, и . На практике входная последовательность всегда является конечной, поэтому считается, что бесконечный вектор имеет лишь конечное число ненулевых компонентов.

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

На рис 4.18 показана основная идея банка фильтров. Там изображен банк анализа, состоящий из двух фильтров: низкочастотного и высокочастотного . Низкочастотный фильтр использует свертку для удаления из сигнала высокочастотной составляющей. Он пропускает низкие частоты. А высокочастотный фильтр делает все наоборот. Он удаляет из сигнала высокие частоты. Вместе они разделяют входной сигнал на поддиапазоны частот.

Рис. 4.18. Банк фильтров из двух каналов.

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

Пример: Легко построить банк фильтров, в котором низкочастотный фильтр вычисляет средние значения, а высокочастотный фильтр вычисляет полуразности, то есть, делается преобразование Хаара входного сигнала. Коэффициенты низкочастотного фильтра равны , а коэффициенты высокочастотного фильтра равны и . Применяем эти фильтры к одномерной входной последовательности

и получаем последовательность средних чисел

и последовательность полуразностей

После децимации (прореживания) первая последовательность сокращается до (239.5, 175.5, 111, 47.5), а вторая приобретает следующий вид: (15.5, 16.5, 16, 15.5). Затем эти две последовательности объединяются в одну: (239.5, 175.5, 111, 47.5, 15.5, 16.5, 16, 15.5), совпадающую с последовательностью, которая получается из уравнения (4.1).

Восстановление исходной последовательности делается с помощью банка синтеза, который отличается от банка анализа. Фильтр синтеза низких частот использует два коэффициента фильтра 1 и 1 для вычисления четырех восстановленных значений , , и , а фильтр синтеза высоких частот с помощью коэффициентов -1 и 1 восстанавливает значения , , и . Затем эти восемь значений перемежаются для получения окончательной реконструкции исходной последовательности.

__________________________________________________

Банки фильтров позволяют взглянуть на преобразование Хаара с общих позиций. Они же дают возможность построить другие, более изощренные вейвлетные преобразования. Эта техника обсуждается в § 4.5.

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

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

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

Обратная процедура состоит в добавлении нулей на место отброшенных членов. Она преобразовывает этот вектор в форму

Децимация означает потерю данных. Обратная процедура не может компенсировать эту потерю, поскольку она лишь добавляет нули. Для того, чтобы достигнуть полного восстановления исходного сигнала , необходимо конструировать фильтры так, чтобы они могли компенсировать эти потери. Первое свойство, которое часто применяется при проектировании фильтров - это свойство ортогональности. Банк анализа преобразования Хаара состоит из коэффициентов низкочастотного фильтра и из коэффициентов высокочастотного фильтра. Скалярное произведение этих двух векторов . То есть, они ортогональны. Аналогично, банк синтеза состоит из двух ортогональных векторов коэффициентов фильтров и .

На рис. 4.19 показано множество ортогональных фильтров размера 4. Эти фильтры ортогональны, поскольку скалярное произведение векторов их коэффициентов равно нулю:

Заметьте, что фильтры и (как и фильтры и ) очень похожи. Конечно, еще необходимо выбрать подходящие значения для коэффициентов фильтров и . Детальное обсуждения этого вопроса выходит за рамки настоящей книги, но в § 4.5 иллюстрируются некоторые методы и правила, которые позволяют на практике определить коэффициенты фильтров. Примером служит фильтр Добеши (Daubechies) D4. Его коэффициенты приведены в уравнении (4.12).

Рис. 4.19. Ортогональный банк фильтров с 4 коэффициентами.

Если с помощью этого фильтра вручную посчитать несколько примеров, то будет видно, что реконструированный сигнал идентичен исходному входному сигналу, но отстает от него на три отсчета по времени.

Банк фильтров может быть биортогональным, менее ограничительным типом фильтров. На рис. 4.20 показан пример такого фильтра, который полностью восстанавливает исходный сигнал. Обратите внимание на схожесть фильтров и , а также фильтров и .

Рис. 4.20. Биортогональный банк фильтров с полным восстановлением.

Нам уже известно из § 4.2, что выходы фильтра низких частот обычно пропускают через фильтры анализа несколько раз, при этом образуются все более короткие выходные сигналы. Эту рекурсивную процедуру можно изобразить в виде дерева (рис. 4.21). Поскольку каждый узел этого дерева вдвое сокращает число выходных символов своего предшественника, то это дерево называется логарифмическим. На рис. 4.21 показано, как масштабирующая функция и вейвлетная функция получаются в пределе из логарифмического дерева. Здесь обнаруживается связь дискретного вейвлетного преобразования (использующего банк фильтров) и континуального (непрерывного) вейвлетного преобразования (CWT, [Salomon 2000]).

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

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

Рис. 4.21. Масштабирующая и вейвлетная функции как предел логарифмического дерева.

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

Заключение. В этом параграфе рассматривались банки фильтров, которые будет полезно сравнить с преобразованием изображений из § 3.5. В обоих случаях обсуждаются преобразования, но это два разных типа преобразований. Каждое преобразование § 3.5 основано на некотором ортогональном базисе функций (или ортогональном базисе изображений), и они вычисляются с помощью взятия скалярного произведения входного сигнала со всеми базисными функциями. Результатом является множество коэффициентов преобразования, которые в дальнейшем сжимаются или без потери информации (с помощью метода RLE или иного энтропийного кодирования), или методом, допускающим потерю данных (тогда кодированию предшествует этап квантования преобразованных данных).

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

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

Рис. 4.22. Общий банк фильтров.

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

На рис. 4.22 изображена общая схема банка фильтров, включающая частотных фильтров и 3 стадии процесса преобразования. Обратите внимание, что выход частотного фильтра каждой стадии направляется на вход следующей стадии для дальнейшего разделения, а комбинированный выход банка синтеза 3-ей и 2-ой стадий посылается наверх обратного фильтра банка синтеза предшествующей стадии.