Дискретные вейвлет-преобразования

Дискретные вейвлет-преобразования

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

Первое ДВП было придумано венгерским математиком Альфредом Хааром. Для входного сигнала, представленного массивом 2n чисел, вейвлет-преобразование Хаара просто группирует элементы по 2 и образует от них суммы и разности. Группировка сумм проводится рекурсивно (в случае чётной длины последовательности сумм) для образования следующего уровня разложения. В итоге получается 2n-1 разность и 1 общая сумма.

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

Самый распространенный набор дискретных вейвлет-преобразований был сформулирован бельгийским математиком Ингрид Добеши (Ingrid Daubechies) в 1988 году. Он основан на использовании рекуррентных соотношений для вычисления всё более точных выборок неявно заданной функции материнского вейвлета, с удвоением разрешения при переходе к следующему уровню (масштабу). В своей основополагающей работе Добеши выводит семейство вейвлетов, первый из которых является вейвлетом Хаара. С тех пор интерес к этой области быстро возрос, что привело к созданию многочисленных потомков исходного семейства вейвлетов Добеши.

Другие формы дискретного вейвлет-преобразования включают непрореженное вейвлет-преобразование (где не выполняется прореживания сигналов), преобразование Ньюлэнда (где ортонормированный базис вейвлетов выводится из специальным образом построенных фильтров типа «top-hat» в частотной области). Пакетные вейвлет-преобразования также связаны с ДВП. Другая форма ДВП — комплексное вейвлет-преобразование.

У дискретного вейвлет-преобразования много приложений в естественных науках, инженерном деле, математике (включая прикладную). Наиболее широко ДВП используется в кодировании сигналов, где свойства преобразования используются для уменьшения избыточности в представлении дискретных сигналов, часто — как первый этап в компрессии данных.

Содержание

Определение

Один уровень преобразования

ДВП сигнала x получают применением набора фильтров. Сначала сигнал пропускается через низкочастотный (low-pass) фильтр с импульсным откликом g, и получается свёртка:

y[n] = (x * g)[n] = \sum\limits_{k =  - \infty }^\infty {x[k] g[n - k]}

Одновременно сигнал раскладывается с помощью высокочастотного (high-pass) фильтра h. В результате получаются детализирующие коэффициенты (после ВЧ-фильтра) и коэффициенты аппроксимации (после НЧ-фильтра). Эти два фильтра связаны между собой и называются квадратурными зеркальными фильтрами (QMF).

Так как половина частотного диапазона сигнала была отфильтрована, то, согласно теореме Котельникова, отсчёты сигналов можно проредить в 2 раза:

y_{\mathrm{low}} [n] = \sum\limits_{k =  - \infty }^\infty  {x[k] g[2n - k]}
y_{\mathrm{high}} [n] = \sum\limits_{k =  - \infty }^\infty  {x[k] h[2n - k]}

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

Схема разложения сигнала в ДВП[1]

С помощью оператора прореживания \downarrow

(y \downarrow k)[n] = y[k n]

вышеупомянутые суммы можно записать короче:

y_{\mathrm{low}} = (x*g)\downarrow 2
y_{\mathrm{high}} = (x*h)\downarrow 2

Вычисление полной свёртки x * g с последующим прореживанием — это излишняя трата вычислительных ресурсов.

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

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

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

Трехуровневый банк (гребёнка) фильтров

На каждом уровне вышеприведённой диаграммы сигнал раскладывается на низкие и высокие частоты. В силу двукратного прореживания, длина сигнала должна быть кратна 2n, где n — число уровней разложения.

Например, для сигнала из 32 отсчётов с частотным диапазоном от 0 до fn трёхуровневое разложение даст 4 выходных сигнала в разных масштабах:

Уровень Частоты Длина сигнала
3 0fn / 8 4
fn / 8fn / 4 4
2 fn / 4fn / 2 8
1 fn / 2fn 16
Представление ДВП в частотной области

Пример программы

Ниже приведён пример ДВП-разложения (один уровень), показывающий простоту его вычисления.

Это вейвлет Хаара (Haar wavelet), написанный на

    public static int[] invoke(int[] input){
        //WARNING: This will destroy the contents of the input array
        //This function assumes input.length=2^n, n>1
        int[] output = new int[input.length];
 
        for(int length = input.length >> 1; ; length >>= 1){
        //length=2^n, WITH DECREASING n
            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];
                output[i] = sum;
                output[length+i] = difference;
            }
            if (length == 1) 
                return output;
 
            //Swap arrays to do next iteration
            System.arraycopy(output, 0, input, 0, length<<1);
        }
    }

Примечания

См. также

Ссылки

  • Реализация на Си для быстрого лифтинга дискретного биортогонального CDF 9/7 вейвлета, используемого в алгоритме сжатия изображений JPEG-2000.

Литература



Wikimedia Foundation. 2010.

Смотреть что такое "Дискретные вейвлет-преобразования" в других словарях:

  • Вейвлет-разложение — В численном и функциональном анализе дискретные вейвлет преобразования (ДВП) относятся к вейвлет преобразованиям, в которых вейвлеты представлены дискретными сигналами (выборками). Первое ДВП было придумано венгерским математиком Альфредом Хааром …   Википедия

  • Вейвлет Хаара — один из первых и наиболее простых вейвлетов. Он был предложен венгерским математиком Альфредом Хааром в 1909 году. Вейвлеты Хаара ортогональны, обладают компактным н …   Википедия

  • Вейвлет Койфлет — порядка 1 К вейвлет функциям с компактным носителем относятся вейвлеты Добеши, койфлеты и симмлеты. Метод построения вейвлет функций с компактным носителем принадлежит Ингр …   Википедия

  • Дискретное вейвлет-преобразование — Пример 1 го уровня дискретного вейвлет преобразования изображения. Вверху оригинальное полноцветное изображение, в середине вейвлет преобразование, сделанное по горизонтали исходного изображения (только канал яркости), внизу вейвлет… …   Википедия

  • Mathcad — Mathcad …   Википедия

  • Ogg — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отред …   Википедия

  • Tarkin — Tarkin  экспериментальный видеокодек, разрабатываемый в рамках фонда Xiph.Org, использует для обработки видео дискретные вейвлет преобразования. Работа над Tarkin приостановлена в феврале 2000 года и теперь основным видеокодеком,… …   Википедия

  • Xiph Ogg — Ogg Расширение файла: .ogv, .oga, .ogx, .ogg Тип незарегистрирован), audio/ogg ( Сигнатура файла: OggS Разработчик: Тип формата: Мультимедиа контейнер Может содержать: Theora, FLAC, Ogg (читается «ог»)  открытый стандарт формата мультимедиа… …   Википедия

  • ГОСТ Р 52210-2004: Телевидение вещательное цифровое. Термины и определения — Терминология ГОСТ Р 52210 2004: Телевидение вещательное цифровое. Термины и определения оригинал документа: 90 (телевизионный) демультиплексор: Устройство, предназначенное для разделения объединенных потоков данных цифрового телевизионного… …   Словарь-справочник терминов нормативно-технической документации

  • Вейвлеты Добеши — Вейвлет Добеши порядка 2 Вейвлеты Добеши (англ. Daubechies Wavelet)  семейство ортогональных вейвлетов с компактным носителем, вычисляемым итерационным путем. Названы в честь математика из США, первой построившей данное семейство,… …   Википедия

Книги



Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»