Пример 2D дискретного вейвлет-преобразования, используемого в JPEG2000 . Исходное изображение подвергается высокочастотной фильтрации, в результате чего получаются три больших изображения, каждое из которых описывает локальные изменения яркости (деталей) исходного изображения. Затем оно подвергается низкочастотной фильтрации и уменьшению масштаба, что дает приближенное изображение; это изображение подвергается высокочастотной фильтрации для получения трех изображений с меньшими деталями и низкочастотной фильтрации для получения изображения окончательного приближения в левом верхнем углу. [ нужны разъяснения ]
В численном и функциональном анализе дискретное вейвлет -преобразование ( DWT ) — это любое вейвлет-преобразование , для которого вейвлеты дискретно выбираются. Как и в случае с другими вейвлет-преобразованиями, его ключевым преимуществом перед преобразованиями Фурье является временное разрешение: оно фиксирует как частоту , так и информацию о местоположении (местоположение во времени).
Примеры
Вейвлеты Хаара
Первый ДВП был изобретен венгерским математиком Альфредом Хааром . Для входных данных, представленных списком чисел , можно рассматривать вейвлет-преобразование Хаара для объединения входных значений в пары, сохранения разницы и передачи суммы. Этот процесс повторяется рекурсивно, объединяя суммы в пары для доказательства следующего масштаба, что приводит к разностям и окончательной сумме.
Вейвлеты Добеши
Наиболее часто используемый набор дискретных вейвлет-преобразований был сформулирован бельгийским математиком Ингрид Добеши в 1988 году. Эта формулировка основана на использовании рекуррентных соотношений для генерации все более точных дискретных выборок неявной материнской вейвлет-функции; каждое разрешение вдвое больше предыдущего масштаба. В своей основополагающей статье Добеши выводит семейство вейвлетов , первым из которых является вейвлет Хаара. С тех пор интерес к этой области резко возрос, и было разработано множество вариаций оригинальных вейвлетов Добеши. [1] [2] [3]
Комплексное вейвлет-преобразование двойного дерева (DCWT)
Комплексное вейвлет-преобразование с двойным деревом ( WT) — это относительно недавнее усовершенствование дискретного вейвлет-преобразования (DWT) с важными дополнительными свойствами: оно практически не сдвигается и избирательно по направлению в двух и более измерениях. Это достигается с коэффициентом избыточности всего , что существенно ниже, чем у непрореженного DWT. Многомерное (MD) WT с двойным деревом является неразделимым, но основано на эффективном в вычислительном отношении отделимом банке фильтров (FB). [4]
ДВП Хаара иллюстрирует желательные свойства вейвлетов в целом. Во-первых, это можно выполнить в операциях; во-вторых, он фиксирует не только понятие частотного содержания входных данных, исследуя его в разных масштабах, но и временное содержание, то есть время, в которое эти частоты встречаются. В совокупности эти два свойства делают быстрое вейвлет-преобразование (БПФ) альтернативой обычному быстрому преобразованию Фурье (БПФ).
Проблемы со временем
Из-за операторов изменения скорости в банке фильтров дискретный WT не является инвариантным во времени, но на самом деле очень чувствителен к выравниванию сигнала во времени. Чтобы решить проблему вейвлет-преобразований, изменяющихся во времени, Маллат и Чжун предложили новый алгоритм вейвлет-представления сигнала, который инвариантен к временным сдвигам. [10] Согласно этому алгоритму, который называется TI-DWT, в двоичной последовательности 2^j (jεZ) выбирается только параметр масштаба, а для каждого момента времени рассчитывается вейвлет-преобразование. [11] [12]
Приложения
Дискретное вейвлет-преобразование имеет огромное количество применений в науке, технике, математике и информатике. В частности, он используется для кодирования сигнала, чтобы представить дискретный сигнал в более избыточной форме, часто в качестве предварительного условия для сжатия данных . Практическое применение также можно найти при обработке сигналов ускорения для анализа походки, [13] [14] обработке изображений, [15] [16] в цифровой связи и многих других. [17] [18] [19]
Показано, что дискретное вейвлет-преобразование (дискретное по масштабу и сдвигу и непрерывное по времени) успешно реализуется в качестве банка аналоговых фильтров при обработке биомедицинских сигналов для создания маломощных кардиостимуляторов, а также в сверхширокополосной (СШП) беспроводной связи. [20]
Пример обработки изображений
Изображение с гауссовским шумомИзображение с удаленным гауссовским шумом
Вейвлеты часто используются для шумоподавления двумерных сигналов, таких как изображения. В следующем примере представлены три шага по удалению нежелательного белого гауссовского шума из показанного зашумленного изображения. Matlab использовался для импорта и фильтрации изображения.
Первым шагом является выбор типа вейвлета и уровня N разложения. В этом случае были выбраны биортогональные вейвлеты 3,5 с уровнем N, равным 10. Биортогональные вейвлеты обычно используются при обработке изображений для обнаружения и фильтрации белого гауссовского шума [21] из-за их высокого контраста значений интенсивности соседних пикселей. Используя эти вейвлеты, на двумерном изображении выполняется вейвлет-преобразование .
Следующим шагом после декомпозиции файла изображения является определение пороговых значений для каждого уровня от 1 до N. Стратегия Бирже-Массара [22] является довольно распространенным методом выбора этих порогов. С помощью этого процесса создаются индивидуальные пороги для N = 10 уровней. Применение этих порогов является основной частью фактической фильтрации сигнала.
Последний шаг — восстановить изображение по измененным уровням. Это достигается с помощью обратного вейвлет-преобразования. Полученное изображение с удаленным белым гауссовским шумом показано под исходным изображением. При фильтрации любой формы данных важно количественно оценить соотношение сигнал/шум результата. [ нужна цитата ] В этом случае SNR зашумленного изображения по сравнению с оригиналом составил 30,4958%, а SNR изображения с шумоподавлением - 32,5525%. Результатом улучшения вейвлет-фильтрации является увеличение отношения сигнал/шум на 2,0567%. [23]
Важно отметить, что выбор других вейвлетов, уровней и стратегий определения порогов может привести к различным типам фильтрации. В этом примере для удаления был выбран белый гауссов шум. Хотя при другом пороге его с таким же успехом можно было бы усилить.
Чтобы проиллюстрировать различия и сходства между дискретным вейвлет-преобразованием и дискретным преобразованием Фурье , рассмотрим DWT и DFT следующей последовательности: (1,0,0,0), единичный импульс .
Синусоидальные волны различаются только частотой. Первый не совершает ни одного цикла, второй выполняет один полный цикл, третий выполняет два цикла, а четвертый выполняет три цикла (что эквивалентно завершению одного цикла в противоположном направлении). Различия в фазе можно представить путем умножения данного базисного вектора на комплексную константу.
Вейвлеты, напротив, имеют как частоту, так и местоположение. Как и прежде, первый выполняет ноль циклов, а второй — один цикл. Однако третий и четвертый имеют одинаковую частоту, вдвое превышающую частоту первого. Они различаются не по частоте, а по расположению : третий ненулевой для первых двух элементов, а четвертый ненулевой для вторых двух элементов.
DWT демонстрирует локализацию: член (1,1,1,1) дает среднее значение сигнала, (1,1,–1,–1) помещает сигнал в левую часть области, а (1 ,–1,0,0) помещает его в левую часть левой части, а усечение на любом этапе дает уменьшенную версию сигнала:
Функция sinc , показывающая артефакты во временной области ( недолет и звон ) усечения ряда Фурье.
ДПФ, напротив, выражает последовательность посредством интерференции волн различных частот - таким образом, усечение ряда дает версию ряда с фильтрацией нижних частот :
Примечательно, что среднее приближение (2-членное) отличается. С точки зрения частотной области это лучшее приближение, но с точки зрения временной области у него есть недостатки – наблюдается занижение уровня – одно из значений отрицательное, хотя исходный ряд везде неотрицательен – и звон , где правая часть не равно нулю, в отличие от вейвлет-преобразования. С другой стороны, приближение Фурье правильно показывает пик, и все точки находятся в пределах своего правильного значения, хотя все точки имеют ошибку. Вейвлет-аппроксимация, напротив, помещает пик в левую половину, но не имеет пика в первой точке, и, хотя она абсолютно правильна для половины значений (отражает местоположение), она имеет ошибку для других значений.
Это иллюстрирует виды компромиссов между этими преобразованиями и то, как в некоторых отношениях DWT обеспечивает предпочтительное поведение, особенно для моделирования переходных процессов.
Сигнал также одновременно разлагается с помощью фильтра верхних частот . Выходные данные дают коэффициенты детализации (из фильтра верхних частот) и коэффициенты аппроксимации (из фильтра нижних частот). Важно, что два фильтра связаны друг с другом и известны как квадратурный зеркальный фильтр .
Блок-схема анализа фильтров
Однако, поскольку половина частот сигнала теперь удалена, половину выборок можно отбросить в соответствии с правилом Найквиста. Выходной сигнал фильтра нижних частот на диаграмме выше затем субдискретизируется на 2 и далее обрабатывается, снова пропуская его через новый фильтр нижних частот и фильтр верхних частот с половиной частоты среза предыдущего. то есть:
Это разложение вдвое уменьшило временное разрешение, поскольку только половина выходного сигнала каждого фильтра характеризует сигнал. Однако каждый выход имеет половину полосы частот входа, поэтому разрешение по частоте удвоено.
приведенное выше суммирование можно записать более кратко.
Однако вычисление полной свертки с последующей понижающей дискретизацией приведет к потере времени вычислений.
Схема подъема — это оптимизация, в которой эти два вычисления чередуются.
Каскадирование и банки фильтров
Это разложение повторяется для дальнейшего увеличения разрешения по частоте, а коэффициенты аппроксимации разлагаются с помощью фильтров верхних и нижних частот, а затем подвергаются понижающей дискретизации. Это представлено в виде двоичного дерева с узлами, представляющими подпространство с различной частотно-временной локализацией. Дерево известно как банк фильтров .
Трехуровневый банк фильтров.
На каждом уровне на приведенной выше диаграмме сигнал разлагается на низкие и высокие частоты. Из-за процесса разложения входной сигнал должен быть кратен числу уровней.
Например, создается сигнал с 32 выборками, частотным диапазоном от 0 до 3 уровнями разложения, 4 выходными шкалами:
Представление DWT в частотной области
Связь с материнским вейвлетом
Реализация набора фильтров вейвлетов может быть интерпретирована как вычисление вейвлет-коэффициентов дискретного набора дочерних вейвлетов для данного материнского вейвлета . В случае дискретного вейвлет-преобразования материнский вейвлет сдвигается и масштабируется на степени двойки.
где параметр масштаба и параметр сдвига, оба из которых являются целыми числами.
Напомним, что вейвлет-коэффициент сигнала — это проекция на вейвлет, и пусть это сигнал длины . В случае дочернего вейвлета в дискретном семействе, указанном выше,
Теперь зафиксируйте определенный масштаб, так что это функция только . В свете приведенного выше уравнения его можно рассматривать как свертку с расширенной, отраженной и нормализованной версией исходного вейвлета, , дискретизированного в точках . Но именно это и дают коэффициенты детализации на уровне дискретного вейвлет-преобразования. Следовательно, для соответствующего выбора и детальные коэффициенты банка фильтров точно соответствуют вейвлет-коэффициенту дискретного набора дочерних вейвлетов для данного материнского вейвлета .
В качестве примера рассмотрим дискретный вейвлет Хаара , материнским вейвлетом которого является . Тогда расширенная, отраженная и нормализованная версия этого вейвлета будет , который действительно является фильтром разложения верхних частот для дискретного вейвлет-преобразования Хаара.
Временная сложность
Реализация набора фильтров дискретного вейвлет-преобразования в некоторых случаях требует только O( N ) по сравнению с O( N log N ) для быстрого преобразования Фурье .
Обратите внимание, что если и оба имеют постоянную длину (т.е. их длина не зависит от N), то и каждый занимает время O( N ) . Банк вейвлет-фильтров выполняет каждую из этих двух сверток O( N ) , затем разделяет сигнал на две ветви размером N/2. Но он только рекурсивно разделяет верхнюю ветвь, свернутую с (в отличие от БПФ, которое рекурсивно разделяет как верхнюю, так и нижнюю ветви). Это приводит к следующему рекуррентному соотношению
что приводит к времени O( N ) для всей операции, как можно показать путем разложения приведенного выше соотношения в геометрический ряд .
Например, дискретное вейвлет-преобразование Хаара является линейным, поскольку в этом случае и имеют постоянную длину 2.
Локальность вейвлетов в сочетании со сложностью O( N ) гарантирует, что преобразование можно вычислить онлайн (на потоковой основе). Это свойство резко контрастирует с БПФ, которое требует одновременного доступа ко всему сигналу. Это также применимо к многомасштабному преобразованию, а также к многомерным преобразованиям (например, 2-D DWT). [24]
Другие преобразования
Алгоритм Adam7 , используемый для чересстрочной развертки в формате Portable Network Graphics (PNG), представляет собой многомасштабную модель данных, похожую на DWT с вейвлетами Хаара . В отличие от DWT, он имеет определенный масштаб — он начинается с блока 8×8 и осуществляет субдискретизацию изображения, а не децимацию ( фильтрация нижних частот , затем субдискретизация). Таким образом, он предлагает худшее частотное поведение, демонстрируя артефакты ( пикселизацию ) на ранних стадиях, в обмен на более простую реализацию.
Мультипликативное (или геометрическое) дискретное вейвлет-преобразование [25] — это вариант, который применяется к модели наблюдения, включающей взаимодействие положительной регулярной функции и мультипликативного независимого положительного шума с . Обозначим , вейвлет-преобразование. Поскольку , то стандартное (аддитивное) дискретное вейвлет-преобразование таково, что коэффициенты детализации вообще нельзя считать разреженными из-за вклада в последнее выражение. В мультипликативной структуре вейвлет-преобразование таково, что Это «вложение» вейвлетов в мультипликативную алгебру включает в себя обобщенные мультипликативные приближения и операторы детализации: Например, в случае вейвлетов Хаара, тогда до коэффициента нормализации стандартные приближения ( среднее арифметическое ) и детали ( арифметические разности ) при использовании становятся соответственно средними геометрическими приближениями и геометрическими разностями (деталями) .
Пример кода
В своей простейшей форме DWT вычислить очень легко.
public static int [] DiscreteHaarWaveletTransform ( int [] input ) { // Эта функция предполагает, что input.length=2^n, n>1 int [] output = new int [ input . длина ] ;for ( int length = input . length / 2 ; ; length = length / 2 ) { // length — текущая длина рабочей области выходного массива. // длина начинается с половины размера массива, и каждая итерация уменьшается вдвое, пока не станет равна 1. for ( int i = 0 ; i < length ; ++ i ) { int sum = input [ i * 2 ] + input [ i * 2 + 1 ] ; int разница = ввод [ i * 2 ] - ввод [ i * 2 + 1 ] ; выход [ я ] = сумма ; вывод [ длина + я ] = разница ; } if ( length == 1 ) { возврат вывода ; }//Поменять местами массивы для следующей итерации System . arraycopy ( выход , 0 , ввод , 0 , длина ); } }
Полный код Java для 1-D и 2-D DWT с использованием вейвлетов Haar , Daubechies , Coiflet и Legendre доступен в проекте с открытым исходным кодом: JWave. Кроме того, здесь можно найти быструю реализацию дискретного биортогонального вейвлет-преобразования CDF 9/7 на языке C , используемого в стандарте сжатия изображений JPEG 2000 (архивировано 5 марта 2012 г.).
Пример приведенного выше кода
Пример вычисления дискретных вейвлет-коэффициентов Хаара для звукового сигнала, когда кто-то говорит: «Я люблю вейвлеты». Исходная форма сигнала показана синим цветом вверху слева, а вейвлет-коэффициенты показаны черным цветом вверху справа. Внизу показаны три увеличенные области вейвлет-коэффициентов для разных диапазонов.
На этом рисунке показан пример применения приведенного выше кода для вычисления вейвлет-коэффициентов Хаара на звуковом сигнале. В этом примере показаны два ключевых свойства вейвлет-преобразования:
Естественные сигналы часто имеют некоторую степень сглаженности, что делает их разреженными в области вейвлетов. В этом примере в вейвлет-области гораздо меньше значимых компонентов, чем во временной области, и большинство значимых компонентов относятся к более грубым коэффициентам слева. Следовательно, естественные сигналы сжимаемы в вейвлет-области.
Вейвлет-преобразование представляет собой полосовое представление сигнала с множественным разрешением. Это можно увидеть непосредственно из определения набора фильтров дискретного вейвлет-преобразования, данного в этой статье. Для сигнала длины коэффициенты в диапазоне представляют версию исходного сигнала, находящегося в полосе пропускания . Вот почему увеличение этих диапазонов вейвлет-коэффициентов выглядит так похоже по структуре на исходный сигнал. Диапазоны, расположенные ближе к левому краю (большие в приведенных выше обозначениях), представляют собой более грубое представление сигнала, а диапазоны справа представляют более мелкие детали.
^ А.Н. Акансу, Р.А. Хаддад и Х. Чаглар, Биномиальное QMF-вейвлет-преобразование с идеальной реконструкцией, Proc. SPIE Визуальные коммуникации и обработка изображений, стр. 609–618, том. 1360, Лозанна, сентябрь 1990 г.
^ Акансу, Али Н.; Хаддад, Ричард А. (1992), Разложение сигнала с несколькими разрешениями: преобразования, поддиапазоны и вейвлеты, Бостон, Массачусетс: Academic Press, ISBN 978-0-12-047141-6
^ А.Н. Акансу, Банки фильтров и вейвлеты в обработке сигналов: критический обзор, Proc. Видеокоммуникации SPIE и PACS для медицинских приложений (приглашенный доклад), стр. 330-341, том. 1977, Берлин, октябрь 1993.
^ Селесник, И.В.; Баранюк, Р.Г.; Кингсбери, Северная Каролина, 2005, Комплексное вейвлет-преобразование с двойным деревом.
^ Салливан, Гэри (8–12 декабря 2003 г.). «Общие характеристики и соображения по проектированию временного поддиапазонного видеокодирования». МСЭ-Т . Группа экспертов по видеокодированию . Проверено 13 сентября 2019 г.
^ Галль, Дидье Ле; Табатабай, Али Дж. (1988). «Поддиапазонное кодирование цифровых изображений с использованием симметричных фильтров с коротким ядром и методов арифметического кодирования». ICASSP-88., Международная конференция по акустике, речи и обработке сигналов . С. 761–764 т.2. дои : 10.1109/ICASSP.1988.196696. S2CID 109186495.
^ Али Наси Акансу , Эффективная структура вейвлета QMF (биномиальные вейвлеты Добеши-QMF), Proc. 1-й симпозиум NJIT по вейвлетам, апрель 1990 г.
^ Саид, А.; Перлман, Вашингтон (1996). «Новый, быстрый и эффективный кодек изображений, основанный на секционировании наборов в иерархических деревьях». Транзакции IEEE по схемам и системам видеотехнологий . 6 (3): 243–250. дои : 10.1109/76.499834. ISSN 1051-8215 . Проверено 18 октября 2019 г.
^ С. Маллат, Вейвлет-тур по обработке сигналов, 2-е изд. Сан-Диего, Калифорния: Академик, 1999.
^ С. Г. Маллат и С. Чжун, «Характеристика сигналов от многомасштабных границ», IEEE Trans. Паттерн Анал. Мах. Интел., вып. 14, нет. 7, стр. 710–732, июль 1992 г.
^ Инс, Кираньяз, Габбуж, 2009, Универсальная и надежная система для автоматизированной классификации сигналов ЭКГ для конкретного пациента.
^ «Новый метод оценки длины шага с помощью сетевых акселерометров тела», IEEE BioWireless 2011 , стр. 79–82.
^ Насир, В.; Круто, Дж.; Сассани, Ф. (октябрь 2019 г.). «Интеллектуальный мониторинг обработки с использованием звукового сигнала, обработанного вейвлет-методом, и самоорганизующейся нейронной сети». Письма IEEE по робототехнике и автоматизации . 4 (4): 3449–3456. дои : 10.1109/LRA.2019.2926666. ISSN 2377-3766. S2CID 198474004.
^ Бротон, С. Аллен. «Методы обработки изображений на основе вейвлетов». www.rose-hulman.edu . Проверено 2 мая 2017 г.
^ Акансу, Али Н.; Смит, Марк Дж. Т. (31 октября 1995 г.). Поддиапазонные и вейвлет-преобразования: проектирование и применение . Академическое издательство Клювер. ISBN0792396456.
^ Акансу, Али Н.; Медли, Майкл Дж. (6 декабря 2010 г.). Вейвлетные, поддиапазонные и блочные преобразования в средствах связи и мультимедиа . Академическое издательство Клювер. ISBN978-1441950864.
^ А.Н. Акансу, П. Дюамель, К. Лин и М. де Курвиль Ортогональные трансмультиплексоры в коммуникации: обзор, IEEE Trans. Об обработке сигналов, специальный выпуск по теории и применениям наборов фильтров и вейвлетов. Том. 46, № 4, стр. 979–995, апрель 1998 г.
^ А. Н. Акансу, В. А. Сердейн и И. В. Селесник, Вейвлет-преобразования при обработке сигналов: обзор новых приложений, Физическая связь, Elsevier, том. 3, выпуск 1, стр. 1–18, март 2010 г.
^ Прагада, С.; Сивасвами, Дж. (1 декабря 2008 г.). «Подавление шума изображения с использованием согласованных биортогональных вейвлетов». 2008 Шестая индийская конференция по компьютерному зрению, обработке графических изображений : 25–32. дои : 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). «Вейвлет-преобразование в реальном времени для бесконечных полос изображений». Журнал обработки изображений в реальном времени . 18 (3). Спрингер: 585–591. дои : 10.1007/s11554-020-00995-8. S2CID 220396648 . Проверено 9 июля 2020 г.
^ Атто, Абдуррахман М.; Труве, Эммануэль; Николя, Жан-Мари; Ле, Ту Транг (2016). «Вейвлет-операторы и мультипликативные модели наблюдений — применение к анализу временных рядов изображений SAR» (PDF) . Транзакции IEEE по геонаукам и дистанционному зондированию . 54 (11): 6606–6624. Бибкод : 2016ITGRS..54.6606A. дои : 10.1109/TGRS.2016.2587626. S2CID 1860049.
[1]
Внешние ссылки
Стэнфордская WaveLab в Matlab
libdwt, кроссплатформенная библиотека DWT, написанная на C.
Краткое введение в вейвлеты Рене Пушингера
^ Прасад, Ахилеш; Маан, Джитендрасингх; Верма, Сандип Кумар (2021). «Вейвлет-преобразования, связанные с индексным преобразованием Уиттекера». Математические методы в прикладных науках . 44 (13): 10734–10752. Бибкод : 2021MMAS...4410734P. дои : 10.1002/ммма.7440. ISSN 1099-1476. S2CID 235556542.