Дискретное вейвлет-преобразование - Discrete wavelet transform
В числовой анализ и функциональный анализ, а дискретное вейвлет-преобразование (DWT) любой вейвлет-преобразование для чего вейвлеты дискретно отбираются. Как и в случае с другими вейвлет-преобразованиями, у него есть ключевое преимущество перед Преобразования Фурье - временное разрешение: захватывает как частотные и информация о местоположении (местоположение во времени).
Примеры
Вейвлеты Хаара
Первый DWT был изобретен венгерским математиком. Альфред Хаар. Для ввода, представленного списком числа, Вейвлет Хаара Преобразование может рассматриваться как объединение входных значений в пары, сохранение разницы и передача суммы. Этот процесс повторяется рекурсивно, объединяя суммы в пары, чтобы доказать следующую шкалу, что приводит к различия и окончательная сумма.
Вейвлеты Добеши
Наиболее часто используемый набор дискретных вейвлет-преобразований был сформулирован бельгийским математиком. Ингрид Добешис в 1988 году. Эта формулировка основана на использовании повторяющиеся отношения генерировать постепенно более мелкие дискретные выборки неявной материнской вейвлет-функции; каждое разрешение вдвое больше предыдущего масштаба. В своей основополагающей статье Добеши выводит семейство вейвлеты, первым из которых является вейвлет Хаара. С тех пор интерес к этой области резко возрос, и было разработано множество вариаций оригинальных вейвлетов Добеши.[1][2]
Комплексное вейвлет-преобразование двойного дерева (DℂWT)
Комплексное вейвлет-преобразование с двойным деревом (ℂWT) является относительно недавним усовершенствованием дискретного вейвлет-преобразования (DWT) с важными дополнительными свойствами: оно почти инвариантно относительно сдвига и избирательно по направлению в двух и более измерениях. Это достигается с коэффициентом избыточности только , существенно ниже недецимированного DWT. Многомерное (M-D) двойное дерево ℂWT неразделимо, но основано на вычислительно эффективном банке разделяемых фильтров (FB).[3]
Другие
Другие формы дискретного вейвлет-преобразования включают вейвлет ЛеГалла-Табатабаи (LGT) 5/3, разработанный Дидье Ле Галлом и Али Дж. Табатабаи в 1988 году (используемый в JPEG 2000 ),[4][5][6] в Биномиальный QMF разработан Али Наси Акансу в 1990 г.,[7] в установить разделение в иерархических деревьях (SPIHT) алгоритм, разработанный Амиром Саидом совместно с Уильямом А. Перлманом в 1996 году,[8] в не- или недесиммированное вейвлет-преобразование (где понижающая дискретизация опущена), а Преобразование Ньюленда (где ортонормированный основа вейвлетов формируется из правильно построенных цилиндрические фильтры в частотное пространство ). Преобразования вейвлет-пакетов также связаны с дискретным вейвлет-преобразованием. Комплексное вейвлет-преобразование это другая форма.
Характеристики
DWT Хаара иллюстрирует желательные свойства вейвлетов в целом. Во-первых, это можно сделать в операции; во-вторых, он фиксирует не только представление о частотном содержании входных данных, исследуя его в различных масштабах, но также и временное содержание, то есть время, в которое эти частоты встречаются. В совокупности эти два свойства делают Быстрое вейвлет-преобразование (FWT) альтернатива обычному быстрое преобразование Фурье (БПФ).
Проблемы со временем
Благодаря операторам изменения скорости в банке фильтров, дискретный WT не инвариантен во времени, но на самом деле очень чувствителен к выравниванию сигнала во времени. Для решения нестационарной проблемы вейвлет-преобразований Маллат и Чжун предложили новый алгоритм для вейвлет-представления сигнала, который инвариантен к временным сдвигам.[9] В соответствии с этим алгоритмом, который называется TI-DWT, только параметр масштаба выбирается вдоль диадической последовательности 2 ^ j (j∈Z), и вейвлет-преобразование вычисляется для каждого момента времени.[10][11]
Приложения
Дискретное вейвлет-преобразование имеет огромное количество приложений в науке, технике, математике и информатике. В частности, он используется для кодирование сигнала, чтобы представить дискретный сигнал в более избыточной форме, часто как предварительное условие для Сжатие данных. Практическое применение также можно найти в обработке сигналов ускорения для анализа походки,[12] обработка изображений,[13] в цифровых коммуникациях и многое другое.[14][15][16]
Показано, что дискретное вейвлет-преобразование (дискретное по масштабу и сдвигу и непрерывное во времени) успешно реализовано в качестве банка аналоговых фильтров при обработке биомедицинских сигналов для разработки маломощных кардиостимуляторов, а также в сверхширокополосной (СШП) беспроводной связи.[17]
Пример обработки изображений
Вейвлеты часто используются для шумоподавления двухмерных сигналов, например изображений. В следующем примере представлены три шага для удаления нежелательного белого гауссовского шума из показанного зашумленного изображения. Matlab был использован для импорта и фильтрации изображения.
Первый шаг - выбрать тип вейвлета и уровень разложения N. В этом случае биортогональный Было выбрано 3,5 вейвлета с уровнем N, равным 10. Биортогональные вейвлеты обычно используются при обработке изображений для обнаружения и фильтрации белого гауссовского шума.[18] из-за их высокого контраста значений интенсивности соседних пикселей. Используя эти вейвлеты вейвлет-преобразование выполняется на двухмерном изображении.
Следующим шагом после декомпозиции файла изображения является определение пороговых значений для каждого уровня от 1 до стратегии Н. Бирже-Массарта.[19] - довольно распространенный метод выбора этих пороговых значений. С помощью этого процесса устанавливаются индивидуальные пороги для N = 10 уровней. Применение этих пороговых значений составляет большую часть фактической фильтрации сигнала.
Последний шаг - восстановить изображение по измененным уровням. Это достигается с помощью обратного вейвлет-преобразования. Полученное изображение без белого гауссовского шума показано под исходным изображением. При фильтрации любой формы данных важно количественно оценить соотношение сигнал шум результата.[нужна цитата ] В этом случае SNR шумного изображения по сравнению с оригиналом составлял 30,4958%, а SNR шумоподавленного изображения - 32,5525%. В результате улучшение вейвлет-фильтрации дает прирост отношения сигнал / шум 2,0567%.[20]
Важно отметить, что выбор других вейвлетов, уровней и стратегий определения пороговых значений может привести к различным типам фильтрации. В этом примере для удаления был выбран белый гауссовский шум. Хотя с другим порогом его можно было бы так же легко усилить.
Сравнение с преобразованием Фурье
Чтобы проиллюстрировать различия и сходства между дискретным вейвлет-преобразованием с дискретное преобразование Фурье, рассмотрим DWT и DFT следующей последовательности: (1,0,0,0), a единичный импульс.
ДПФ имеет ортогональный базис (Матрица ДПФ ):
в то время как DWT с вейвлетами Хаара для данных длиной 4 имеет ортогональный базис в строках:
(Для упрощения записи используются целые числа, поэтому основания ортогональный но нет ортонормированный.)
Предварительные наблюдения включают:
- Синусоидальные волны различаются только своей частотой. Первый не завершает никаких циклов, второй завершает один полный цикл, третий завершает два цикла, а четвертый завершает три цикла (что эквивалентно завершению одного цикла в противоположном направлении). Различия в фазах можно представить, умножив заданный базисный вектор на комплексную константу.
- Вейвлеты, напротив, имеют и частоту, и местоположение. Как и раньше, первый завершает нулевые циклы, а второй - один цикл. Однако у третьего и четвертого одинаковая частота, в два раза больше, чем у первого. Они отличаются не по частоте, а по место расположения - третий ненулевой по первым двум элементам, а четвертый ненулевой по вторым двум элементам.
Разложение последовательности по этим основаниям дает:
DWT демонстрирует локализацию: член (1,1,1,1) дает среднее значение сигнала, (1,1, –1, –1) помещает сигнал в левую часть домена, а (1 , –1,0,0) помещает его в левую часть левой части, а усечение на любом этапе дает субдискретизированную версию сигнала:
ДПФ, напротив, выражает последовательность интерференцией волн разных частот - таким образом, усечение ряда дает фильтр нижних частот версия серии:
Примечательно, что среднее приближение (2-членное) отличается. С точки зрения частотной области это лучшее приближение, но с точки зрения временной области у него есть недостатки - он демонстрирует недолет - одно из значений отрицательное, хотя исходный ряд везде неотрицательный - и звон, где правая часть не равна нулю, в отличие от вейвлет-преобразования. С другой стороны, приближение Фурье правильно показывает пик, и все точки находятся в пределах их правильного значения, хотя все точки имеют ошибку. Вейвлет-приближение, напротив, помещает пик в левой половине, но не имеет пика в первой точке, и, хотя это точно верно для половины значений (отражающих местоположение), оно имеет ошибку для других значений.
Это иллюстрирует виды компромиссов между этими преобразованиями и то, как в некоторых отношениях DWT обеспечивает предпочтительное поведение, особенно для моделирования переходных процессов.
Определение
Один уровень трансформации
DWT сигнала рассчитывается путем пропускания через серию фильтров. Сначала образцы проходят через фильтр нижних частот с импульсивный ответ в результате свертка из двух:
Сигнал также разлагается одновременно с использованием фильтр высоких частот . Выходы дают детальные коэффициенты (из фильтра высоких частот) и коэффициенты аппроксимации (из фильтра низких частот). Важно, чтобы эти два фильтра были связаны друг с другом и назывались квадратурный зеркальный фильтр.
Однако, поскольку половина частот сигнала теперь удалена, половина отсчетов может быть отброшена в соответствии с правилом Найквиста. Выходной сигнал фильтра нижних частот на диаграмме выше тогда подвыборка на 2 и далее обрабатывается, пропуская его снова через новый фильтр нижних частот и фильтр высоких частот с половиной частоты среза предыдущего, то есть:
Это разложение уменьшило вдвое временное разрешение, поскольку только половина каждого выходного сигнала фильтра характеризует сигнал. Однако каждый выход имеет половину полосы частот входа, поэтому разрешение по частоте было увеличено вдвое.
приведенное выше суммирование можно записать более кратко.
Однако вычисление полной свертки с последующим понижением дискретизации приведет к потере времени вычислений.
В Схема подъема оптимизация, в которой эти два вычисления чередуются.
Каскадные и фильтровальные банки
Это разложение повторяется для дальнейшего увеличения разрешения по частоте, и коэффициенты аппроксимации разлагаются с помощью фильтров верхних и нижних частот, а затем подвергаются понижающей дискретизации. Это представлено в виде двоичного дерева с узлами, представляющими подпространство с другой частотно-временной локализацией. Дерево известно как банк фильтров.
На каждом уровне на приведенной выше диаграмме сигнал разбивается на низкие и высокие частоты. Из-за процесса разложения входной сигнал должен быть кратным куда количество уровней.
Например, сигнал с 32 отсчетами, диапазон частот от 0 до и 3 уровня декомпозиции, производятся 4 шкалы вывода:
Уровень | Частоты | Образцы |
---|---|---|
3 | к | 4 |
к | 4 | |
2 | к | 8 |
1 | к | 16 |
Отношение к материнскому вейвлету
Реализацию набора фильтров вейвлетов можно интерпретировать как вычисление вейвлет-коэффициентов дискретный набор дочерних вейвлетов для данного материнского вейвлета . В случае дискретного вейвлет-преобразования материнский вейвлет сдвигается и масштабируется по степени двойки.
куда параметр масштаба и - параметр сдвига, оба целые числа.
Напомним, что вейвлет-коэффициент сигнала это проекция на вейвлет, и пусть быть сигналом длины . В случае дочернего вейвлета в дискретной семье выше,
Теперь исправим в определенном масштабе, так что является функцией Только. В свете приведенного выше уравнения можно рассматривать как свертка из с расширенной, отраженной и нормализованной версией материнского вейвлета, , отобранные в точках . Но именно это дают коэффициенты детализации на уровне дискретного вейвлет-преобразования. Поэтому при соответствующем выборе и , детальные коэффициенты банка фильтров точно соответствуют вейвлет-коэффициенту дискретного набора дочерних вейвлетов для данного материнского вейвлета .
В качестве примера рассмотрим дискретный Вейвлет Хаара, чей материнский вейвлет . Тогда расширенная, отраженная и нормализованная версия этого вейвлета имеет вид , который действительно является фильтром разложения верхних частот для дискретного вейвлет-преобразования Хаара.
Сложность времени
Реализация набора фильтров дискретного вейвлет-преобразования занимает только O (N) в некоторых случаях по сравнению с O (N бревноN) для быстрое преобразование Фурье.
Обратите внимание, что если и оба имеют постоянную длину (т.е. их длина не зависит от N), то и каждый дубль O (N) время. Банк вейвлет-фильтров выполняет каждое из этих двух O (N) свертки, затем разбивает сигнал на две ветви размером N / 2. Но он только рекурсивно разбивает верхнюю ветвь, свернутую с (в отличие от БПФ, которое рекурсивно разделяет как верхнюю, так и нижнюю ветви). Это приводит к следующему отношение повторения
что приводит к O (N) время на всю операцию, как может быть показано геометрическая серия расширение указанного выше отношения.
Например, дискретный Вейвлет Хаара преобразование линейно, так как в этом случае и имеют постоянную длину 2.
Локальность всплесков вместе с O (N) сложности, гарантирует, что преобразование может быть вычислено онлайн (на потоковой основе). Это свойство резко контрастирует с БПФ, которое требует доступа ко всему сигналу сразу. Это также применимо к многомасштабному преобразованию, а также к многомерному преобразованию (например, 2-D DWT).[21]
Другие трансформации
В Алгоритм Adam7, используется для переплетение в Переносимая сетевая графика (PNG) - это многомасштабная модель данных, аналогичная DWT с Вейвлеты Хаара.
В отличие от DWT, у него особый масштаб - он начинается с блока 8 × 8 и субдискретизация изображение, а не уничтожающий (фильтрация нижних частот, затем понижающая дискретизация). Таким образом, он предлагает худшее частотное поведение, показывая артефакты (пикселизация ) на ранних этапах в обмен на более простую реализацию.
Пример кода
В своей простейшей форме DWT удивительно легко вычислить.
В Вейвлет Хаара в Ява:
общественный статический int[] дискретныйHaarWaveletTransform(int[] Вход) { // Эта функция предполагает, что input.length = 2 ^ n, n> 1 int[] выход = новый int[Вход.длина]; за (int длина = Вход.длина / 2; ; длина = длина / 2) { // длина - текущая длина рабочей области выходного массива. // длина начинается с половины размера массива, и каждая итерация уменьшается вдвое, пока не станет равной 1. за (int я = 0; я < длина; ++я) { int сумма = Вход[я * 2] + Вход[я * 2 + 1]; int разница = Вход[я * 2] - Вход[я * 2 + 1]; выход[я] = сумма; выход[длина + я] = разница; } если (длина == 1) { возвращаться выход; } // Поменять местами массивы для следующей итерации Система.arraycopy(выход, 0, Вход, 0, длина); }}
Полный код Java для 1-D и 2-D DWT с использованием Хаар, Добеши, Coiflet, и Legendre вейвлеты доступны из проекта с открытым исходным кодом: JWave.Кроме того, реализация быстрого лифтинга дискретных биортогональных CDF 9/7 вейвлет-преобразование в C, используемый в JPEG 2000 стандарт сжатия изображений можно найти здесь (архивировано 5 марта 2012 г.).
Пример приведенного выше кода
На этом рисунке показан пример применения вышеуказанного кода для вычисления вейвлет-коэффициентов Хаара для звуковой волны. В этом примере выделяются два ключевых свойства вейвлет-преобразования:
- Естественные сигналы часто имеют некоторую степень плавности, что делает их редкими в области вейвлета. В этом примере значимых компонентов в вейвлет-области гораздо меньше, чем во временной области, и большинство значимых компонентов относятся к более грубым коэффициентам слева. Следовательно, естественные сигналы сжимаются в вейвлетной области.
- Вейвлет-преобразование представляет собой полосовое представление сигнала с несколькими разрешениями. Это можно увидеть непосредственно из определения набора фильтров дискретного вейвлет-преобразования, данного в этой статье. Для сигнала длины , коэффициенты в диапазоне представляют собой версию исходного сигнала, который находится в полосе пропускания . Вот почему увеличение этих диапазонов вейвлет-коэффициентов выглядит так похоже по структуре на исходный сигнал. Ближе к левому краю (больший в обозначениях выше) являются более грубым представлением сигнала, а диапазоны справа представляют более мелкие детали.
Смотрите также
- Дискретное косинусное преобразование (DCT)
- Вейвлет
- Серия вейвлетов
- Вейвлет-сжатие
- Список преобразований, связанных с вейвлетами
Рекомендации
- ^ А.Н. Акансу, Р.А. Хаддад и Х. Каглар, Биномиальное QMF-вейвлет-преобразование с идеальной реконструкцией, Proc. SPIE Визуальные коммуникации и обработка изображений, стр. 609–618, т. 1360, Лозанна, сентябрь 1990 г.
- ^ Акансу, Али Н .; Хаддад, Ричард А. (1992), Разложение сигнала с несколькими разрешениями: преобразования, поддиапазоны и вейвлеты, Бостон, Массачусетс: Academic Press, ISBN 978-0-12-047141-6
- ^ Selesnick, I.W .; Баранюк, Р.Г .; Кингсбери, Северная Каролина, 2005, Комплексное вейвлет-преобразование двойного дерева
- ^ Салливан, Гэри (8–12 декабря 2003 г.). «Общие характеристики и конструктивные соображения для кодирования видео временного поддиапазона». ITU-T. Группа экспертов по кодированию видео. Получено 13 сентября 2019.
- ^ Бовик, Алан С. (2009). Основное руководство по обработке видео. Академическая пресса. п. 355. ISBN 9780080922508.
- ^ Галл, Дидье Ле; Табатабай, Али Дж. (1988). «Подполосное кодирование цифровых изображений с использованием симметричных коротких ядерных фильтров и методов арифметического кодирования». ICASSP-88., Международная конференция по акустике, речи и обработке сигналов: 761–764 т.2. Дои:10.1109 / ICASSP.1988.196696. S2CID 109186495.
- ^ Али Наси Акансу, Эффективная структура QMF-вейвлета (Биномиальные QMF всплески Добеши), Proc. 1-й симпозиум NJIT по вейвлетам, апрель 1990 г.
- ^ Сказал, А .; Перлман, В. А. (1996). «Новый, быстрый и эффективный кодек изображения, основанный на разделении набора в иерархических деревьях». IEEE Transactions по схемам и системам для видеотехнологий. 6 (3): 243–250. Дои:10.1109/76.499834. ISSN 1051-8215. Получено 18 октября 2019.
- ^ С. Маллат, Вейвлет-тур по обработке сигналов, 2-е изд. Сан-Диего, Калифорния: Академический, 1999.
- ^ С. Г. Маллат и С. Чжун, "Характеристика сигналов от многомасштабных границ", IEEE Trans. Pattern Anal. Мах. Intell., Т. 14, вып. 7. С. 710–732, июль 1992 г.
- ^ Инс, Кираняз, Габбудж, 2009 г., Универсальная и надежная система для автоматической классификации сигналов ЭКГ в зависимости от пациента
- ^ «Новый метод оценки длины шага с помощью акселерометров сети локализации тела», IEEE BioWireless 2011 г., стр. 79–82
- ^ Бротон, С. Аллен. «Вейвлет-методы в обработке изображений». www.rose-hulman.edu. Получено 2017-05-02.
- ^ А.Н. Акансу и M.J.T. Смит,Подполосные и вейвлет-преобразования: разработка и применение, Kluwer Academic Publishers, 1995.
- ^ А.Н. Акансу и М.Дж. Медли, Вейвлет, поддиапазон и блочные преобразования в коммуникациях и мультимедиа, Kluwer Academic Publishers, 1999.
- ^ А.Н. Акансу, П. Дюамель, X. Линь и М. де Курвиль Ортогональные трансмультиплексоры в коммуникации: обзор, IEEE Trans. Об обработке сигналов, специальный выпуск по теории и приложениям банков фильтров и всплесков. Vol. 46, № 4, стр. 979–995, апрель 1998 г.
- ^ А.Н. Акансу, В.А.Сердейн и И.В. Селесник, Вейвлет-преобразования при обработке сигналов: обзор новых приложений, Физическая коммуникация, Elsevier, т. 3, выпуск 1, стр. 1–18, март 2010 г.
- ^ Pragada, S .; Сивасвами, Дж. (01.12.2008). «Снижение шума изображения с использованием согласованных биортогональных вейвлетов». 2008 Шестая индийская конференция по компьютерному зрению и обработке графических изображений: 25–32. Дои:10.1109 / ICVGIP.2008.95. S2CID 15516486.
- ^ "Пороги для вейвлета 1-D с использованием стратегии Бирже-Массарта - MATLAB wdcbm". www.mathworks.com. Получено 2017-05-03.
- ^ "как получить SNR для 2 изображений - Ответы MATLAB - MATLAB Central". www.mathworks.com. Получено 2017-05-10.
- ^ Барина, Давид (2020). «Вейвлет-преобразование в реальном времени для бесконечных полос изображений». Журнал обработки изображений в реальном времени. Springer. Дои:10.1007 / s11554-020-00995-8. S2CID 220396648. Получено 2020-07-09.
внешняя ссылка
- Стэнфордский WaveLab в Matlab
- libdwt, кроссплатформенная библиотека DWT, написанная на C
- Краткое введение в вейвлеты Рене Пушингер