В 1 988, Mallat произвел быстрый алгоритм разложения и реконструкции вейвлета [1]. Алгоритм Mallat для дискретного вейвлета преобразовывает (DWT) является, на самом деле, классической схемой в сообществе обработки сигналов, известном как двухканальный кодер поддиапазона, использующий сопряженные квадратурные фильтры или квадратурные фильтры зеркала (QMFs).
Алгоритм разложения запускается с s сигнала, затем вычисляет координаты A 1 и D 1, и затем те из A 2 и D 2, и так далее.
Алгоритм реконструкции, названный обратным дискретным вейвлетом преобразовывает (IDWT), начинает с координат AJ и DJ, затем вычисляет координаты AJ –1, и затем использование координат AJ –1 и DJ –1 вычисляет те из AJ –2 и так далее.
Этот раздел обращается к следующим темам:
Для ортогонального вейвлета, в среде мультиразрешения, мы начинаем с масштабирующейся функции φ и функции вейвлета ψ. Одно из основных отношений является отношением двойной шкалы (уравнение расширения или уравнение улучшения):
Все фильтры, используемые в DWT и IDWT, глубоко связаны с последовательностью
(wn) n∊Z
Очевидно, если φ сжато поддержан, последовательность (wn) конечна и может быть просмотрена как фильтр. Фильтр W, который называется масштабирующимся (ненормированным) фильтром,
Конечная импульсная характеристика (FIR)
Из длины 2N
Из суммы 1
Из нормы
Из нормы 1
Фильтр lowpass
Например, для db3
масштабирование фильтра,
load db3 db3 db3 = 0.2352 0.5706 0.3252 -0.0955 -0.0604 0.0249 sum(db3) ans = 1.0000 norm(db3) ans = 0.7071
От фильтра W мы задаем четыре КИХ-фильтра, длины 2N и нормы 1, организованный можно следующим образом.
Фильтры | Lowpass | Высокая передача |
---|---|---|
Разложение | Lo_D | Hi_D |
Реконструкция | Lo_R | Hi_R |
Четыре фильтра вычисляются с помощью следующей схемы.
где qmf
таково, что Hi_R и Lo_R являются квадратурными фильтрами зеркала (т.е. Hi_R (k) = (–1) k Lo_R (2N + 1 – k)) для k = 1, 2..., 2N.
Обратите внимание на то, что wrev
инвертирует коэффициенты фильтра. Таким образом, Hi_D и Lo_D являются также квадратурными фильтрами зеркала. Расчет этих фильтров выполняется с помощью orthfilt
. Затем мы иллюстрируем эти свойства с db6
вейвлет.
Загрузите экстремальный фильтр масштабирования фазы Добечиса и постройте коэффициенты.
load db6; subplot(421); stem(db6,'markerfacecolor',[0 0 1]); title('Original scaling filter');
Используйте orthfilt
возвратить анализ (разложение) и синтез (реконструкция) фильтры.
Получите дискретные преобразования Фурье (DFT) lowpass и highpass аналитических фильтров. Постройте модуль ДПФ.
LoDFT = fft(Lo_D,64); HiDFT = fft(Hi_D,64); freq = -pi+(2*pi)/64:(2*pi)/64:pi; subplot(427); plot(freq,fftshift(abs(LoDFT))); set(gca,'xlim',[-pi,pi]); xlabel('Radians/sample'); title('DFT Modulus - Lowpass Filter') subplot(428); plot(freq,fftshift(abs(HiDFT))); set(gca,'xlim',[-pi,pi]); xlabel('Radians/sample'); title('Highpass Filter');
Учитывая s сигнала длины N, DWT состоит из этапов log2N самое большее. Начиная с s, первый шаг производит два набора коэффициентов: коэффициенты приближения cA 1 и коэффициенты детали cD 1. Эти векторы получены путем свертки к s с Lo_D фильтра lowpass для приближения, и с фильтром высоких частот Hi_D для детали, сопровождаемой двухместной децимацией.
Более точно первый шаг
Длина каждого фильтра равна 2L. Результатом свертки к длине сигнал N с длиной 2L фильтр является N +2L–1. Поэтому сигналы F и G имеют длину N + 2L – 1. После субдискретизации 2, векторы коэффициентов cA 1 и cD 1 имеет длину
Следующий шаг разделяет коэффициенты приближения cA 1 в двух частях с помощью той же схемы, заменяя s cA 1 и производя cA 2 и cD 2, и так далее.
Так разложение вейвлета s сигнала, анализируемого на уровне, j имеет следующую структуру: [cAj, cDj..., cD 1].
Эта структура содержит для J = 3 терминальные узлы следующего дерева.
С другой стороны, запуская с cA j и cD j, IDWT восстанавливает cA j –1, инвертируя шаг разложения путем вставки нулей и свертки к результатам с фильтрами реконструкции.
Для изображений подобный алгоритм возможен для двумерных вейвлетов и масштабирующихся функций, полученных из 1D вейвлетов tensorial продуктом.
Этот вид 2D DWT приводит к разложению коэффициентов приближения на уровне j в четырех компонентах: приближение на уровне j + 1 и детали в трех ориентациях (горизонталь, вертикальная, и диагональная).
Следующие графики описывают основные шаги разложения и реконструкции для изображений.
Так, для J = 2, 2D дерево вейвлета имеет следующую форму.
Наконец, давайте упомянем, что для биоортогональных вейвлетов те же алгоритмы содержат, но фильтры разложения с одной стороны и фильтры реконструкции, с другой стороны, получены из двух отличных функций масштабирования, сопоставленных с двумя исследованиями мультиразрешения в дуальности.
В этом случае фильтры для разложения и реконструкции, в целом, различных нечетных длин. Эта ситуация происходит, например, для “сплайнов” биоортогональные вейвлеты, используемые в тулбоксе. Дополнением нуля четыре фильтра могут быть расширены таким способом, которым у них будет та же ровная длина.
Предыдущий абзац описывает алгоритмы, спроектированные для сигналов конечной длины или изображений. Чтобы изучить объяснение, мы должны рассмотреть сигналы бесконечной длины. Методы для расширения данного сигнала конечной длины описаны в Краевых эффектах.
Давайте обозначим h = Lo_R и g = Hi_R и давайте фокусироваться на 1D случае.
Мы сначала выравниваем по ширине, как пойти от уровня j, чтобы выровнять j +1 для вектора приближения. Это - основной шаг алгоритма разложения для расчета приближений. Детали вычисляются таким же образом с помощью фильтра g вместо фильтра h.
Позвольте (Ak (j)) k ∊Z быть координатами векторного Aj:
и Ak (j +1) координаты векторного Aj +1:
Ak (j +1) вычисляется с помощью формулы
Эта формула напоминает формулу свертки.
Расчет очень прост.
Давайте зададим
Последовательностью F (j +1) является отфильтрованный выход последовательности A (j) фильтром .
Мы получаем
Ak (j +1) = F 2k (j +1)
Мы должны принять даже значения индекса F. Это прореживает.
Последовательность A (j +1) является прореженной версией последовательности F (j +1).
Инициализация выполняется с помощью Ak (0) = s (k), где s (k) является значением сигналов во время k.
Существует несколько причин этого неожиданного результата, все из которых соединяются с ситуацией с мультиразрешением и с несколькими свойств функций φj,k и ψj,k.
Давайте теперь опишем некоторых из них.
Семейство формируется из ортонормированных функций. Как следствие для любого j, семейства ортонормировано.
Двойное индексируемое семейство
ортонормировано.
Для любого j, являются ортогональными к .
Между двумя последовательными шкалами у нас есть основное отношение, названное отношением двойной шкалы.
Отношение двойной шкалы для | |
---|---|
|
|
Это отношение вводит фильтр h алгоритма . Для получения дополнительной информации смотрите Фильтры, Используемые, чтобы Вычислить DWT и IDWT.
Мы проверяем что:
Координата φj+1,0 на φj,k is hk и не зависит от j.
Координата φj+1, n на φj,k равен .
Эти отношения предоставляют ингредиенты для алгоритма.
До сих пор мы использовали фильтр h. Фильтр высоких частот g используется в двойном отношении шкал, соединяющем функции φ и ψ. Между двумя последовательными шкалами у нас есть следующее фундаментальное отношение двойной шкалы.
Отношение двойной шкалы между и | |
---|---|
|
|
После шага разложения мы выравниваем по ширине теперь алгоритм реконструкции путем создания его. Давайте упростим обозначение. При запуске с A 1 и D 1, давайте изучим A 0 = A 1 + Dj 1. Процедура является тем же самым, чтобы вычислить A = Aj +1 + Dj +1.
Давайте зададим αn, δn,
Давайте оценим координаты как
Мы будем фокусировать наше исследование первой суммы вторая сумма обработан подобным образом.
Вычисления легко организованы, если мы отмечаем, что (взятие k = 0 в предыдущих формулах, делает вещи более простыми),
Если мы преобразовываем последовательность в новую последовательность заданный
..., α–1, 0, α0, 0, α1, 0, α2, 0... который является точно
Затем
и следовательно
С тех пор
шаги реконструкции:
Замените α и δ последовательности сверхдискретизированными версиями α ˜ и вставка нулей.
Фильтр по h и g соответственно.
Суммируйте полученные последовательности.
Объекты | Описание | |
---|---|---|
Сигнал в исходное время | s Ak, 0 ≤ k ≤ j Dk, 1 ≤ k ≤ j | Исходный сигнал Приближение на уровне k Детализируйте на уровне k |
Коэффициенты в связанное со шкалой время | cAk, 1 ≤ k ≤ j cDk, 1 ≤ k ≤ j [cAj, cDj..., cD 1] | Коэффициенты приближения на уровне k Детализируйте коэффициенты на уровне k Разложение вейвлета на уровне j, j ≥ 1 |
Цель | Входной параметр | Вывод | Файл |
---|---|---|---|
Одноуровневое разложение | s | cA 1, cD 1 | dwt |
Одноуровневое разложение | cAj | cAj +1, cDj +1 | dwt |
Разложение | s | [cAj, cDj..., cD 1] | wavedec |
Цель | Входной параметр | Вывод | Файл |
---|---|---|---|
Одноуровневая реконструкция | cA 1, cD 1 | s или A 0 | idwt |
Одноуровневая реконструкция | cAj +1, cDj +1 | cAj | idwt |
Полная реконструкция | [cAj, cDj..., cD 1] | s или A 0 | waverec |
Выборочная реконструкция | [cAj, cDj..., cD 1] | Al, Dm | wrcoef |
Цель | Входной параметр | Вывод | Файл |
---|---|---|---|
Экстракция коэффициентов детали | [cAj, cDj..., cD 1] | cDk, 1 ≤ k ≤ j | detcoef |
Экстракция коэффициентов приближения | [cAj, cDj..., cD 1] | cAk, 0 ≤ k ≤ j | appcoef |
Пересостав структуры разложения | [cAj, cDj..., cD 1] | [cAk, cDk..., cD 1] 1 ≤ k ≤ j | upwlev |
Чтобы проиллюстрировать режим командной строки для 1D возможностей, смотрите, что 1D Анализ Использует Командную строку..
Объекты | Описание | |
---|---|---|
Отобразите в исходном разрешении | s | Оригинальное изображение |
A 0 | Приближение на уровне 0 | |
Ak, 1 ≤ k ≤ j | Приближение на уровне k | |
Dk, 1 ≤ k ≤ j | Детали на уровне k | |
Коэффициенты в связанном со шкалой разрешении | cAk, 1 ≤ k ≤ j | Коэффициенты приближения на уровне k |
cDk, 1 ≤ k ≤ j | Детализируйте коэффициенты на уровне k | |
[cAj, cDj..., cD 1] | Разложение вейвлета на уровне j |
Dk обозначает , горизонталь, вертикальные, и диагональные детали на уровне k.
То же самое содержит для cDk, который обозначает .
2D файлы совпадают с теми для 1D случая, но с 2
добавленный на конце команды.
Например, idwt
становится idwt2
. Для получения дополнительной информации смотрите 1D Возможности Вейвлета.
Чтобы проиллюстрировать режим командной строки для 2D возможностей, смотрите Анализ изображения Вейвлета и Сжатие..
[1] Mallat, S. G. “Теория для Разложения Сигнала Мультиразрешения: Представление Вейвлета”, Транзакции IEEE согласно Анализу Шаблона и Искусственному интеллекту. Издание 11, Выпуск 7, июль 1989, стр 674–693.