Дискретное вейвлет-преобразование - Discrete wavelet transform

Пример двумерного дискретного вейвлет-преобразования, который используется в JPEG2000. Исходное изображение подвергается высокочастотной фильтрации, в результате чего получаются три больших изображения, каждое из которых описывает локальные изменения яркости (деталей) исходного изображения. Затем он подвергается фильтрации нижних частот и масштабируется, давая приближенное изображение; это изображение подвергается высокочастотной фильтрации для получения трех изображений с меньшей детализацией и низкочастотной фильтрации для получения окончательного приближенного изображения в верхнем левом углу.[требуется разъяснение ]

В числовой анализ и функциональный анализ, а дискретное вейвлет-преобразование (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) помещает его в левую часть левой части, а усечение на любом этапе дает субдискретизированную версию сигнала:

В функция sinc, показывая артефакты временной области (недолет и звон ) усечения ряда Фурье.

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

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

Это иллюстрирует виды компромиссов между этими преобразованиями и то, как в некоторых отношениях DWT обеспечивает предпочтительное поведение, особенно для моделирования переходных процессов.

Определение

Один уровень трансформации

DWT сигнала рассчитывается путем пропускания через серию фильтров. Сначала образцы проходят через фильтр нижних частот с импульсивный ответ в результате свертка из двух:

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

Блок-схема анализа фильтров

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

Это разложение уменьшило вдвое временное разрешение, поскольку только половина каждого выходного сигнала фильтра характеризует сигнал. Однако каждый выход имеет половину полосы частот входа, поэтому разрешение по частоте было увеличено вдвое.

С оператор подвыборки

приведенное выше суммирование можно записать более кратко.

Однако вычисление полной свертки с последующим понижением дискретизации приведет к потере времени вычислений.

В Схема подъема оптимизация, в которой эти два вычисления чередуются.

Каскадные и фильтровальные банки

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

3-х уровневый блок фильтров

На каждом уровне на приведенной выше диаграмме сигнал разбивается на низкие и высокие частоты. Из-за процесса разложения входной сигнал должен быть кратным куда количество уровней.

Например, сигнал с 32 отсчетами, диапазон частот от 0 до и 3 уровня декомпозиции, производятся 4 шкалы вывода:

УровеньЧастотыОбразцы
3 к 4
к 4
2 к 8
1 к 16
Представление DWT в частотной области

Отношение к материнскому вейвлету

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

куда параметр масштаба и - параметр сдвига, оба целые числа.

Напомним, что вейвлет-коэффициент сигнала это проекция на вейвлет, и пусть быть сигналом длины . В случае дочернего вейвлета в дискретной семье выше,

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

В качестве примера рассмотрим дискретный Вейвлет Хаара, чей материнский вейвлет . Тогда расширенная, отраженная и нормализованная версия этого вейвлета имеет вид , который действительно является фильтром разложения верхних частот для дискретного вейвлет-преобразования Хаара.

Сложность времени

Реализация набора фильтров дискретного вейвлет-преобразования занимает только 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 г.).

Пример приведенного выше кода

Пример вычисления дискретных вейвлет-коэффициентов Хаара для звукового сигнала человека, говорящего «Я люблю вейвлеты». Исходная форма волны показана синим в верхнем левом углу, а вейвлет-коэффициенты показаны черным в правом верхнем углу. Внизу показаны три увеличенные области вейвлет-коэффициентов для разных диапазонов.

На этом рисунке показан пример применения вышеуказанного кода для вычисления вейвлет-коэффициентов Хаара для звуковой волны. В этом примере выделяются два ключевых свойства вейвлет-преобразования:

  • Естественные сигналы часто имеют некоторую степень плавности, что делает их редкими в области вейвлета. В этом примере значимых компонентов в вейвлет-области гораздо меньше, чем во временной области, и большинство значимых компонентов относятся к более грубым коэффициентам слева. Следовательно, естественные сигналы сжимаются в вейвлетной области.
  • Вейвлет-преобразование представляет собой полосовое представление сигнала с несколькими разрешениями. Это можно увидеть непосредственно из определения набора фильтров дискретного вейвлет-преобразования, данного в этой статье. Для сигнала длины , коэффициенты в диапазоне представляют собой версию исходного сигнала, который находится в полосе пропускания . Вот почему увеличение этих диапазонов вейвлет-коэффициентов выглядит так похоже по структуре на исходный сигнал. Ближе к левому краю (больший в обозначениях выше) являются более грубым представлением сигнала, а диапазоны справа представляют более мелкие детали.

Смотрите также

Рекомендации

  1. ^ А.Н. Акансу, Р.А. Хаддад и Х. Каглар, Биномиальное QMF-вейвлет-преобразование с идеальной реконструкцией, Proc. SPIE Визуальные коммуникации и обработка изображений, стр. 609–618, т. 1360, Лозанна, сентябрь 1990 г.
  2. ^ Акансу, Али Н .; Хаддад, Ричард А. (1992), Разложение сигнала с несколькими разрешениями: преобразования, поддиапазоны и вейвлеты, Бостон, Массачусетс: Academic Press, ISBN  978-0-12-047141-6
  3. ^ Selesnick, I.W .; Баранюк, Р.Г .; Кингсбери, Северная Каролина, 2005, Комплексное вейвлет-преобразование двойного дерева
  4. ^ Салливан, Гэри (8–12 декабря 2003 г.). «Общие характеристики и конструктивные соображения для кодирования видео временного поддиапазона». ITU-T. Группа экспертов по кодированию видео. Получено 13 сентября 2019.
  5. ^ Бовик, Алан С. (2009). Основное руководство по обработке видео. Академическая пресса. п. 355. ISBN  9780080922508.
  6. ^ Галл, Дидье Ле; Табатабай, Али Дж. (1988). «Подполосное кодирование цифровых изображений с использованием симметричных коротких ядерных фильтров и методов арифметического кодирования». ICASSP-88., Международная конференция по акустике, речи и обработке сигналов: 761–764 т.2. Дои:10.1109 / ICASSP.1988.196696. S2CID  109186495.
  7. ^ Али Наси Акансу, Эффективная структура QMF-вейвлета (Биномиальные QMF всплески Добеши), Proc. 1-й симпозиум NJIT по вейвлетам, апрель 1990 г.
  8. ^ Сказал, А .; Перлман, В. А. (1996). «Новый, быстрый и эффективный кодек изображения, основанный на разделении набора в иерархических деревьях». IEEE Transactions по схемам и системам для видеотехнологий. 6 (3): 243–250. Дои:10.1109/76.499834. ISSN  1051-8215. Получено 18 октября 2019.
  9. ^ С. Маллат, Вейвлет-тур по обработке сигналов, 2-е изд. Сан-Диего, Калифорния: Академический, 1999.
  10. ^ С. Г. Маллат и С. Чжун, "Характеристика сигналов от многомасштабных границ", IEEE Trans. Pattern Anal. Мах. Intell., Т. 14, вып. 7. С. 710–732, июль 1992 г.
  11. ^ Инс, Кираняз, Габбудж, 2009 г., Универсальная и надежная система для автоматической классификации сигналов ЭКГ в зависимости от пациента
  12. ^ «Новый метод оценки длины шага с помощью акселерометров сети локализации тела», IEEE BioWireless 2011 г., стр. 79–82
  13. ^ Бротон, С. Аллен. «Вейвлет-методы в обработке изображений». www.rose-hulman.edu. Получено 2017-05-02.
  14. ^ А.Н. Акансу и M.J.T. Смит,Подполосные и вейвлет-преобразования: разработка и применение, Kluwer Academic Publishers, 1995.
  15. ^ А.Н. Акансу и М.Дж. Медли, Вейвлет, поддиапазон и блочные преобразования в коммуникациях и мультимедиа, Kluwer Academic Publishers, 1999.
  16. ^ А.Н. Акансу, П. Дюамель, X. Линь и М. де Курвиль Ортогональные трансмультиплексоры в коммуникации: обзор, IEEE Trans. Об обработке сигналов, специальный выпуск по теории и приложениям банков фильтров и всплесков. Vol. 46, № 4, стр. 979–995, апрель 1998 г.
  17. ^ А.Н. Акансу, В.А.Сердейн и И.В. Селесник, Вейвлет-преобразования при обработке сигналов: обзор новых приложений, Физическая коммуникация, Elsevier, т. 3, выпуск 1, стр. 1–18, март 2010 г.
  18. ^ Pragada, S .; Сивасвами, Дж. (01.12.2008). «Снижение шума изображения с использованием согласованных биортогональных вейвлетов». 2008 Шестая индийская конференция по компьютерному зрению и обработке графических изображений: 25–32. Дои:10.1109 / ICVGIP.2008.95. S2CID  15516486.
  19. ^ "Пороги для вейвлета 1-D с использованием стратегии Бирже-Массарта - MATLAB wdcbm". www.mathworks.com. Получено 2017-05-03.
  20. ^ "как получить SNR для 2 изображений - Ответы MATLAB - MATLAB Central". www.mathworks.com. Получено 2017-05-10.
  21. ^ Барина, Давид (2020). «Вейвлет-преобразование в реальном времени для бесконечных полос изображений». Журнал обработки изображений в реальном времени. Springer. Дои:10.1007 / s11554-020-00995-8. S2CID  220396648. Получено 2020-07-09.

внешняя ссылка