4.3. Поддиапазонные преобразования

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

Дискретное скалярное произведение двух векторов  и  задается формулой

.

В начале § 3.5 рассматривалось преобразование вида , где  - исходные данные, a  - некоторые весовые коэффициенты.

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

Слово «свертка» означает совместное сворачивание величин или функций. Дискретная свертка двух векторов  и , которая также является вектором, обозначается . Компоненты свертки вычисляются по формулам

.            (4.3)

(Операцию свертки можно также определить для функций, но для наших потребностей сжатия данных достаточно будет дискретной свертки). Заметим, что пределы суммирования в формуле (4.3) не указаны точно. Они зависят от размерности векторов  и . Примерами могут служить формулы (4.9).

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

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

Из этого определения в частности следует, что , или в более общем виде:  для любого вещественного числа .

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

Полезно иметь некоторую общую формулу для представления линейных систем. Оказывается, что представление вида

                                 (4.4)

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

,

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

.                    (4.5)

Вычтем (4.4) из этого уравнения:

.

Это равенство должно выполняться для любого входного сигнала . Поэтому выражение в квадратных скобках должно равняться нулю. Следовательно,  при всех . Значит, функция  не изменится, если добавить любое число  к ее аргументам, то есть она остается постоянной, если разность аргументов - константа, а сама функция  зависит только от разности своих аргументов. Тогда ее можно записать в виде , а уравнение (4.4) примет следующий простой вид:

.                  (4.6)

Рис. 4.16. Свертка функции  и .

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

Свертка имеет несколько важных свойств. Она удовлетворяет свойствам коммутативности, ассоциативности и дистрибутивности по сложению, то есть, имеют место следующие тождества:

,

,

.                 (4.7)

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

.              (4.8)

Если длины последовательностей  и  равны, соответственно,  и , то  имеет длину .

Пример: Даны две последовательности  (шесть элементов) и  (пять элементов). Уравнения (4.8) задают свертку  из 10 элементов:

.                         (4.9)

Простейшим примером использования свертки является сглаживание или очищение сигналов от шума. Здесь становится ясным, как можно использовать свертку в фильтрах. Имея зашумленный сигнал  (рис. 4.17), выберем прямоугольный импульс в качестве компоненты  свертки:

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

Рис. 4.17. Применение свертки при «очищении» функции от шума.

«О нет, - сказал Жорж, - это больше чем деньги.»

Он обхватил голову ладонями и постарался припомнить что-нибудь еще, кроме денег. Серое вещество в его голове было полно конволюций и извилин, его барабанные перепонки были туго натянуты. Сквозь них проходили только звуки очень высокой частоты.
- Поль Скотт, «Клещи»