ГЛАВА 4 ВЕЙВЛЕТНЫЕ МЕТОДЫ

Во введении уже отмечалось, что методы сжатия, основанные на свойствах вейвлетов, используют довольно глубокие математические результаты. Это обстоятельство бросает определенный вызов как автору, так и читателю. Целью этой главы является представление основ теории вейвлетных преобразований (с минимумом дополнительных математических сведений) и ее приложений к задачам сжатия данных. Глава начинается с изложения последовательности шагов, состоящих из вычисления средних (полусумм) и полуразностей, которые преобразовывают одномерный массив исходных данных к виду, удобному для сжатия. Затем этот метод обобщается на двумерные массивы данных, что позволяет применять эти результаты к сжатию оцифрованных изображений. Рассмотренная последовательность трансформаций массива данных является простейшим примером поддиапазонного преобразования. Будет показано, что она идентична преобразованию Хаара, определенному в § 3.5.7.

В § 4.2.1 устанавливается связь преобразования Хаара с умножением матриц. Это проложит путь к введению в § 4.4 понятия банка фильтров. В § 4.3 излагаются некоторые дополнительные математические результаты, знакомство с которыми можно опустить при первом чтении. В этом параграфе обсуждается операция дискретной свертки и ее применение к под диапазонным преобразованиям. За этим материалом следует § 4.6, в котором излагается дискретное вейвлетное преобразование (DWT, descrete wavelet transform). Глава заканчивается описанием метода сжатия SPIHT, основанного на вейвлетном преобразовании.

Перед тем как углубиться в различные детали следует ответить на часто задаваемый вопрос: «А почему здесь используется именно термин «вейвлет» (wavelet это слово можно перевести как «маленькая волна» или «всплеск»)?» Эта глава не содержит полного ответа на этот вопрос, но рис. 4.14 и 4.34 дают некоторое интуитивное объяснение.

4.1. Вычисление средних и полуразностей

Мы начнем с одномерного массива данных, состоящего из  элементов. В принципе, этими элементами могут быть соседние пикселы изображения или последовательные звуковые фрагменты. Для простоты предположим, что число  равняется степени двойки. (Это будет предполагаться на протяжении всей главы, но в этом нет ограничения общности. Если длина  имеет другие делители, то можно просто удлинить массив, добавив в конце нули или повторив последний элемент нужное число раз. После декомпрессии, добавленные элементы просто удаляются.) Примером будет служить массив чисел (1, 2, 3, 4, 5, 6, 7, 8). Сначала вычислим четыре средние величины , ,  и . Ясно, что знания этих четырех полусумм не достаточно для восстановления всего массива, поэтому мы еще вычислим четыре полуразности , ,   и , которые будем называть коэффициентами деталей. Мы будем равноправно использовать термины «полуразность» и «деталь». Средние числа можно представлять себе крупномасштабным разрешением исходного образа, а детали необходимы для восстановления мелких подробностей или поправок. Если исходные данные коррелированы, то крупномасштабное разрешение повторит исходный образ, а детали будут малыми.

Массив (3/2, 7/2, 11/2, 15/2, -1/2, -1/2, -1/2, -1/2), состоящий из четырех полусумм и четырех полуразностей, можно использовать для восстановления исходного массива чисел. Новый массив также состоит из восьми чисел, но его последние четыре компоненты, полуразности, имеют тенденцию уменьшаться, что хорошо для сжатия. Воодушевленные этим обстоятельством, повторим нашу процедуру применительно к четырем первым (крупным) компонентам нашего нового массива. Они преобразуются в два средних и в две полуразности. Остальные четыре компонента оставим без изменений. Получим массив (10/4, 26/4, -4/4, -4/4, -1/2, -1/2, -1/2, -1/2). Следующая и последняя итерация нашего процесса преобразует первые две компоненты этого массива в одно среднее (которое, на самом деле, равно среднему значению всех 8 элементов исходного массива) и одну полуразность. В итоге получим массив чисел (36/8, -16/8, -4/4, -4/4, -1/2, -1/2, -1/2, -1/2), который называется вейвлетным преобразованием Хаара исходного массива данных.

Из-за взятия полу разностей вейвлетное преобразование приводит к уменьшению знамений исходных пикселов, поэтому их будет легче сжать с помощью квантования и кодирования длинами серий (RLE), методом Хаффмана, или, быть может, иным подходящим способом (см. [Salomon 2000]). Сжатие с потерей части информации достигается, как обычно, с помощью квантования или простого удаления наименьших полуразностей (заменой их на нули).

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

.

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

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

.

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

Две процедуры на рис. 4.1 иллюстрируют, как вычисляется нормализованное вейвлетное преобразование массива из  компонентов ( равно степени 2). Обратное преобразование, которое восстанавливает исходный массив, показано в двух процедурах на рис. 4.2.

Рис. 4.1. Вычисление нормализованного вейвлетного преобразования (псевдокод).

Рис. 4.2. Обратное нормализованного вейвлетного преобразования (псевдокод).

Эти процедуры, на первый взгляд, отличаются от взятия средних и полу разностей, которые обсуждались выше, поскольку происходит деление на , а не на 2. Первая процедура начинается делением всего массива на , а вторая делает обратное. Окончательный результат, тем не менее, совпадает с массивом, указанным выше. Начиная с массива (1, 2, 3, 4, 5, 6, 7, 8), получаем после трех итераций процедуры NWTcalc следующие массивы

,

,

,

.