В численном анализе и функционального анализа , A дискретное вейвлет - преобразование ( DWT ) является любой вейвлет - преобразование , для которого вейвлетов дискретно пробы. Как и в случае с другими вейвлет-преобразованиями, его ключевым преимуществом перед преобразованиями Фурье является временное разрешение: оно фиксирует как частоту, так и информацию о местоположении (местоположение во времени).
Примеры
Вейвлеты Хаара
Первый DWT был изобретен венгерским математиком Альфредом Хааром . Для ввода, представленного спискомчисел, можно рассматривать вейвлет- преобразование Хаара для объединения входных значений в пары, сохранения разницы и передачи суммы. Этот процесс повторяется рекурсивно, объединяя суммы в пары, чтобы доказать следующую шкалу, что приводит к различия и окончательная сумма.
Вейвлеты Добеши
Наиболее часто используемый набор дискретных вейвлет-преобразований был сформулирован бельгийским математиком Ингрид Добешис в 1988 году. Эта формулировка основана на использовании рекуррентных соотношений для создания постепенно более тонких дискретных выборок неявной материнской вейвлет-функции; каждое разрешение вдвое больше предыдущего. В своей основополагающей статье Добеши выводит семейство вейвлетов , первым из которых является вейвлет Хаара. С тех пор интерес к этой области резко возрос, и было разработано множество вариаций оригинальных вейвлетов Добеши. [1] [2]
Комплексное вейвлет-преобразование двойного дерева (DℂWT)
Комплексное вейвлет-преобразование с двойным деревом (ℂWT) является относительно недавним усовершенствованием дискретного вейвлет-преобразования (DWT) с важными дополнительными свойствами: оно почти инвариантно к сдвигу и избирательно по направлению в двух и более высоких измерениях. Это достигается с коэффициентом избыточности только, существенно ниже недецимитированного DWT. Многомерное (MD) двойное дерево ℂWT неразделимо, но основано на эффективном в вычислительном отношении банке разделяемых фильтров (FB). [3]
Другие
Другие формы дискретного вейвлет - преобразования включают LeGall-Tabatabai (LGT) 5/3 вейвлет , разработанный Didier Le Gall и Ali J. Табатабаи в 1988 году (используется в JPEG 2000 ), [4] [5] [6] биномиальное СУК разработала от Ali Naci Akansu в 1990 году, [7] множество разделов в иерархических деревьев (SPIHT) алгоритм , разработанный Amir Said с William A. Перлман в 1996 году [8] не- или undecimated вейвлет - преобразование (где даунсамплинг опущен), и Ньюленд преобразования (где ортонормирована базис вейвлетов формируется из построенных надлежащим образом шляпообразных фильтров в частотном пространстве ). Преобразования вейвлет-пакетов также связаны с дискретным вейвлет-преобразованием. Еще одна форма - сложное вейвлет-преобразование .
Характеристики
DWT Хаара иллюстрирует желательные свойства вейвлетов в целом. Во-первых, это может быть выполнено воперации; во-вторых, он фиксирует не только представление о частотном содержании входных данных, исследуя его в различных масштабах, но также и временное содержание, то есть время, в которое эти частоты встречаются. В совокупности эти два свойства делают быстрое вейвлет-преобразование (FWT) альтернативой обычному быстрому преобразованию Фурье (FFT).
Проблемы со временем
Благодаря операторам изменения скорости в банке фильтров, дискретный WT не инвариантен во времени, но на самом деле очень чувствителен к выравниванию сигнала во времени. Для решения нестационарной проблемы вейвлет-преобразований Маллат и Чжун предложили новый алгоритм для вейвлет-представления сигнала, который инвариантен к временным сдвигам. [9] В соответствии с этим алгоритмом, который называется TI-DWT, только параметр масштаба выбирается по диадической последовательности 2 ^ j (j∈Z), и вейвлет-преобразование вычисляется для каждого момента времени. [10] [11]
Приложения
Дискретное вейвлет-преобразование имеет огромное количество приложений в науке, технике, математике и информатике. В частности, он используется для кодирования сигналов , чтобы представить дискретный сигнал в более избыточной форме, часто в качестве предварительной обработки для сжатия данных . Практическое применение также можно найти в обработке сигналов ускорений для анализа походки, [12] [13] обработки изображений, [14] [15] в цифровой связи и многих других. [16] [17] [18]
Показано, что дискретное вейвлет-преобразование (дискретное по масштабу и сдвигу и непрерывное во времени) успешно реализовано в качестве банка аналоговых фильтров при обработке биомедицинских сигналов для разработки маломощных кардиостимуляторов, а также в сверхширокополосной (СШП) беспроводной связи. [19]
Пример обработки изображений
Вейвлеты часто используются для шумоподавления двухмерных сигналов, например изображений. В следующем примере представлены три шага для удаления нежелательного белого гауссовского шума из показанного зашумленного изображения. Matlab использовался для импорта и фильтрации изображения.
Первый шаг - выбрать тип вейвлета и уровень разложения N. В этом случае были выбраны 3,5 биортогональных вейвлета с уровнем N, равным 10. Биортогональные вейвлеты обычно используются при обработке изображений для обнаружения и фильтрации белого гауссовского шума [20] из-за их высокой контрастности значений интенсивности соседних пикселей. С помощью этих вейвлетов выполняется вейвлет-преобразование двумерного изображения.
После декомпозиции файла изображения следующим шагом является определение пороговых значений для каждого уровня от 1 до N. Стратегия Бирже-Массарта [21] является довольно распространенным методом выбора этих пороговых значений. С помощью этого процесса устанавливаются индивидуальные пороги для N = 10 уровней. Применение этих пороговых значений составляет большую часть фактической фильтрации сигнала.
Последний шаг - восстановить изображение по измененным уровням. Это достигается с помощью обратного вейвлет-преобразования. Результирующее изображение без белого гауссовского шума показано под исходным изображением. При фильтрации любой формы данных важно количественно оценить отношение сигнал / шум результата. [ необходима цитата ] В этом случае SNR шумного изображения по сравнению с оригиналом составлял 30,4958%, а SNR шумоподавленного изображения - 32,5525%. В результате улучшение вейвлет-фильтрации дает прирост отношения сигнал / шум 2,0567%. [22]
Важно отметить, что выбор других вейвлетов, уровней и стратегий определения пороговых значений может привести к различным типам фильтрации. В этом примере был выбран белый гауссовский шум для удаления. Хотя с другим порогом его можно было бы так же легко усилить.
Чтобы проиллюстрировать различия и сходства между дискретным вейвлет-преобразованием и дискретным преобразованием Фурье , рассмотрим DWT и DFT следующей последовательности: (1,0,0,0), единичный импульс .
ДПФ имеет ортогональный базис ( матрицу ДПФ ):
в то время как 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 log N ) для быстрого преобразования Фурье .
Обратите внимание, что если а также оба имеют постоянную длину (т.е. их длина не зависит от N), то а также каждый занимает O ( N ) раз. Набор вейвлет-фильтров выполняет каждую из этих двух сверток O ( N ) , а затем разделяет сигнал на две ветви размером N / 2. Но он только рекурсивно разбивает верхнюю ветвь, свернутую с(в отличие от БПФ, которое рекурсивно разделяет как верхнюю, так и нижнюю ветви). Это приводит к следующему рекуррентному соотношению
что приводит к времени O ( N ) для всей операции, как может быть показано расширением геометрического ряда вышеупомянутого соотношения.
Например, дискретное вейвлет- преобразование Хаара является линейным, поскольку в этом случае а также имеют постоянную длину 2.
Локальность вейвлетов в сочетании со сложностью O ( N ) гарантирует, что преобразование может быть вычислено онлайн (на потоковой основе). Это свойство резко контрастирует с БПФ, которое требует доступа ко всему сигналу сразу. Это также применимо к многомасштабному преобразованию, а также к многомерному преобразованию (например, 2-D DWT). [23]
Другие преобразования
- Алгоритм Adam7 , используемый для переплетения в Portable Network Graphics формата (PNG), является многомасштабной моделью данных , которая похожа на DWT с вейвлет Хаара . В отличие от DWT, он имеет особый масштаб - он начинается с блока 8 × 8 и субдискретизирует изображение, а не децимирует ( фильтрация нижних частот , затем понижающая дискретизация). Таким образом, он предлагает худшее частотное поведение, демонстрируя артефакты ( пикселирование ) на ранних этапах в обмен на более простую реализацию.
- Мультипликативный (или геометрический) дискретное вейвлет - преобразование [24] представляет собой вариант , который относится к модели наблюдениявовлекающие взаимодействия положительной регулярной функции и мультипликативный независимый положительный шум , с участием . Обозначить, вейвлет-преобразование. С, то стандартное (аддитивное) дискретное вейвлет-преобразование таково, что где детализирующие коэффициенты в целом нельзя считать редкими из-за вклада в последнем выражении. В мультипликативной структуре вейвлет-преобразование таково, чтоЭто `` вложение '' всплесков в мультипликативную алгебру включает обобщенные мультипликативные аппроксимации и детальные операторы: например, в случае вейвлетов Хаара, то с точностью до нормировочного коэффициента, стандарт приближения ( среднее арифметическое )и детали ( арифметические различия )становятся соответственно приближениями к среднему геометрическомуи геометрические различия (подробности) когда используешь .
Пример кода
В своей простейшей форме DWT удивительно легко вычислить.
Вейвлет Хаара в Java :
public static int [] diskteHaarWaveletTransform ( int [] input ) { // Эта функция предполагает, что input.length = 2 ^ n, n> 1 int [] output = new int [ input . длина ] ; для ( INT длина = вход . длина / 2 ; ; длина = длина / 2 ) { // длина текущая длина рабочей площади выходного массива. // длина начинается с половины размера массива, и каждая итерация уменьшается вдвое, пока не станет 1. for ( int i = 0 ; i < length ; ++ i ) { int sum = input [ i * 2 ] + input [ i * 2 + 1 ] ; int difference = input [ i * 2 ] - input [ i * 2 + 1 ] ; вывод [ я ] = сумма ; вывод [ длина + я ] = разница ; } если ( длина == 1 ) { вернуть вывод ; } // Поменять местами массивы для выполнения следующей итерации System . arraycopy ( вывод , 0 , ввод , 0 , длина ); } }
Полный код Java для 1-D и 2-D DWT с использованием вейвлетов Хаара , Добеши , Койфлета и Лежандра доступен в проекте с открытым исходным кодом: 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
- ^ Селезник, И. В.; Баранюк, Р.Г .; Кингсбери, Северная Каролина, 2005, Комплексное вейвлет-преобразование с двойным деревом
- ^ Салливан, Гэри (8–12 декабря 2003 г.). «Общие характеристики и конструктивные соображения для кодирования видео временного поддиапазона» . ITU-T . Группа экспертов по кодированию видео . Проверено 13 сентября 2019 .
- ^ Бовик, Алан С. (2009). Основное руководство по обработке видео . Академическая пресса . п. 355. ISBN 9780080922508.
- ^ Галл, Дидье Ле; Табатабай, Али Дж. (1988). «Подполосное кодирование цифровых изображений с использованием симметричных коротких ядерных фильтров и методов арифметического кодирования». ICASSP-88., Международная конференция по акустике, речи и обработке сигналов : 761–764, том 2. DOI : 10.1109 / ICASSP.1988.196696 . S2CID 109186495 .
- ^ Али Наси Акансу , Эффективная структура QMF-вейвлетов (Binomial-QMF-вейвлеты Добеши), Proc. 1-й симпозиум NJIT по вейвлетам, апрель 1990 г.
- ^ Сказал, А .; Перлман, Вашингтон (1996). «Новый, быстрый и эффективный кодек изображений, основанный на разделении множеств в иерархических деревьях» . IEEE Transactions on Circuits and Systems for Video Technology . 6 (3): 243–250. DOI : 10.1109 / 76.499834 . ISSN 1051-8215 . Проверено 18 октября 2019 .
- ^ С. Маллат, Вейвлет-тур по обработке сигналов, 2-е изд. Сан-Диего, Калифорния: Academic, 1999.
- ^ С.Г. Маллат и С. Чжун, «Характеристика сигналов от многомасштабных краев», IEEE Trans. Pattern Anal. Мах. Intell., Т. 14, вып. 7. С. 710–732, июль 1992 г.
- ^ Ince, Kiranyaz, Gabbouj, 2009, Универсальная и надежная система для автоматизированной классификации сигналов ЭКГ с учетом специфики пациента.
- ^ "Новый метод оценки длины шага с помощью акселерометров сети области тела" , IEEE BioWireless 2011 , стр. 79–82
- ^ Насир, В .; Cool, J .; Сассани, Ф. (октябрь 2019 г.). «Интеллектуальный мониторинг обработки с использованием звукового сигнала, обработанного с помощью вейвлет-метода и самоорганизующейся нейронной сети» . Письма IEEE по робототехнике и автоматизации . 4 (4): 3449–3456. DOI : 10,1109 / LRA.2019.2926666 . ISSN 2377-3766 .
- ^ Бротон, С. Аллен. «Вейвлет-методы в обработке изображений» . www.rose-hulman.edu . Проверено 2 мая 2017 .
- ^ Червяков, Н.И. Ляхов П.А.; Нагорнов, Н.Н. (01.11.2018). «Шум квантования многоуровневых фильтров дискретного вейвлет-преобразования при обработке изображений» . Оптоэлектроника, приборы и обработка данных . 54 (6): 608–616. DOI : 10.3103 / S8756699018060092 . ISSN 1934-7944 .
- ^ Akansu и MJT Смит, поддиапазон и Вейвлет Трансформация: Дизайн и приложения , Kluwer Academic Publishers, 1995.
- ^ Akansu и MJ Medley, Wavelet, поддиапазоны и Блок Трансформация в связи и мультимедиа , Kluwer Academic Publishers, 1999.
- ^ А. Н. Акансу, П. Дюамель, X. Лин и М. де Курвиль Ортогональные трансмультиплексоры в коммуникации: обзор , IEEE Trans. Об обработке сигналов, специальный выпуск по теории и приложениям банков фильтров и всплесков. Vol. 46, № 4, стр. 979–995, апрель 1998 г.
- ^ А. Н. Акансу, В. А. Сердейн и И. В. Селесник, Вейвлет-преобразования в обработке сигналов: обзор новых приложений , физическая коммуникация, Elsevier, vol. 3, выпуск 1, стр. 1–18, март 2010 г.
- ^ Pragada, S .; Сивасвами, Дж. (01.12.2008). «Снижение шума изображения с использованием согласованных биортогональных вейвлетов». 2008 Шестая индийская конференция по компьютерному зрению, обработке графических изображений : 25–32. DOI : 10.1109 / ICVGIP.2008.95 . S2CID 15516486 .
- ^ «Пороги для вейвлета 1-D с использованием стратегии Бирже-Массарта - MATLAB wdcbm» . www.mathworks.com . Проверено 3 мая 2017 .
- ^ «как получить SNR для 2 изображений - Ответы MATLAB - MATLAB Central» . www.mathworks.com . Проверено 10 мая 2017 .
- ^ Барина, Дэвид (2020). «Вейвлет-преобразование в реальном времени для бесконечных полос изображений» . Журнал обработки изображений в реальном времени . Springer. DOI : 10.1007 / s11554-020-00995-8 . S2CID 220396648 . Проверено 9 июля 2020 .
- ^ Атто, Абдуррахман М .; Труве, Эммануэль; Николя, Жан-Мари; Ле, Чу Транг (2016). «Вейвлет-операторы и модели мультипликативных наблюдений - применение для анализа временных рядов РСА-изображений». IEEE Transactions по наукам о Земле и дистанционному зондированию . DOI : 10,1109 / TGRS.2016.2587626 .
Внешние ссылки
- Стэнфордская лаборатория WaveLab в matlab
- libdwt , кроссплатформенная библиотека DWT, написанная на C
- Краткое введение в вейвлеты Рене Пушингера