Глава 7. ЦЕЛОЧИСЛЕННОЕ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЕ

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

7.1. Целочисленные вейвлет-преобразования

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

Пример 1. Целочисленное вычисление вейвлет-преобразования (2,2).

Это преобразование эквивалентно вейвлет-преобразованию Хаара, использующему следующие фильтры декомпозиции:

Вычисление ведется следующим образом:

В выражениях (7.2), (7.3) int означает операцию округления. Таким образом, все элементы будут целыми числами. Из (7.1)-(7.3) легко получить алгоритм реконструкции:

Пример 2. Вейвлет-преобразование Лэйзи.

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

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

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

Известно, что значения высокочастотных вейвлет-коэффициентов малы. Это позволяет сохранять точность во время вычисления коэффициентов. Рассмотрим целочисленные вычисления, выполняемые компьютером. Большинство компьютеров использует дополнительный код. Пусть необходимо найти разность двух целых чисел - а и выполнить обратное вычисление Вычисления на компьютере выполняются следующим образом:

и обратная величина находится, как

где индекс означает внутреннее представление, а числа находятся в пределах Если оказывается вне диапазона, его внутреннее представление может не совпадать с внешним значением Например, пусть (100000001). Тогда имеет следующее внутреннее представление: (100000001) при другой стороны, при будет равно

Пример 3. Целочисленное вычисление вейвлет-преобразования (2,6). Данное преобразование эквивалентно использованию следующих фильтров анализа:

Декомпозиция выполняется аналогично примеру 1 с добавлением еще одного шага. Вначале производятся вычисления по формулам Вместо в данных формулах теперь используется обозначение Затем производится изменение высокочастотных коэффициентов по формулам:

Алгоритм реконструкции аналогичен алгоритму декомпозиции. Он выполняется в «обратном» порядке:

и, далее, по формулам с заменой в них на

Пример 4. Целочисленное вычисление вейвлет -преобразования (1,3). Это нелинейное преобразование является разновидностью преобразования, использующего биортогональную пару фильтров: Вычисления начинаются с вейвлета Лэйзи (7.6) с последующим изменением высокочастотных коэффициентов:

Реконструкция выполняется следующим образом:

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

(кликните для просмотра скана)

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