WAVELET-АНАЛИЗ ИЗОБРАЖЕНИЙ
Оптический
журнал, т.68, №3, 49-59 (2001)
Е.И.Толкова, к.ф.-м.н.,
Нижегородский госуниверситет им.Н.И.Лобачевского,
Нижний Новгород, Россия
Обычно двумерное вейвлет-преобразование представляет собой произведение
преобразований по строкам и столбцам изображения и порождает крестообразные
либо вытянутые вдоль икс или игрек базисные функции. В настоящей работе
предложена «шахматная» схема вейвлет-преобразования изображений, базис которой
образован функциями с высокой степенью изотропии. В силу этого, если на
изображении пребладают изотропные элементы («пятна»), в разложении по шахматной
схеме можно ожидать большего числа малых коэффициентов. Заметим, что пятенная
структура может создаваться в самом процессе вейвлет-анализа, при построении
уменьшенной версии изображения. В наших экспериментах по сжатию данных,
использование предложенной схемы преобразования на последних этапах анализа
позволило заметно уменьшить ошибку, связанную с отбрасыванием малых
коэффициентов разложения.
1. Введение
Существуют две большие группы задач цифровой обработки изображений:
анализ признаков и сжатие данных – для
решения которых используются спектральные преобразования. В классической
монографии Прэтта «Цифровая обработка изображений», изданной в 1978 году,
описаны восемь видов преобразований избражений (Фурье, синусное, косинусное,
Адамара, Хаара и другие), среди которых отсутствует само понятие
вейвлет-преобразования, хотя преобразование Хаара является его частным случаем [1].
Сегодня большая часть задач цифровой обработки изображений решается именно при
помощи вейвлет-анализа. Вейвлет-анализ используется для сжатия изображений, в
компьютерной графике, для распознавания образов и построения моделей восприятия
зрительной информации [2,3].
Широкое использование
вейвлет-анализа связано с тем, что базис такого преобразования: разные
масштабные версии и сдвиги импульсов двух типов (скэйлинг-функции и вейвлета) -
более отвечает природе сигнала, чем периодические функции, поскольку сигнал
(изображение) есть именно набор элементов разного положения и размера. Кроме
того, вейвлет-анализ оставляет большую свободу в конкретном выборе этих
импульсов.
По аналогии с традиционными спектральными преобразованиями, двумерные
вейвлет-преобразования выполняются как последовательность одномерных
преобразований над строками и столбцами изображения. Если 
и 
- скэйлинг функция и вейвлет одномерного преобразования, то
двумерный базис в простейшем случае будет образован сдвигами и растяжениями
вдоль координатных осей одной скэйлинг-функции 
и трех вейвлетов
.
Для
более сложной структуры разложения, отвечающей использованию вейвлет-пакетов,
набор базисных функций шире, но все они образованы произведениями базисных
функций одномерного преобразования, взятыми от 
и от 
. Эти базисные функции имеют крестообразный характер, а на
плоскости появляются четыре выделенных направления вдоль горизонтали, вертикали
и обеих диагоналей [3].
Для анализа структуры, не имеющей выделенных направлений, такие функции не
являются оптимальными, например, в смысле представления сигнала с заданной
точностью наименьшим числом вейвлет-коэффициентов. В настоящей работе построено
семейство плоских вейвлетов, обладающих более высокой степенью симметрии (см.
рис.1), которые мы будем называть шахматными вейвлетами. Базис разложения по
шахматным вейвлетам в простейшем случае образован версиями одной
скэйлинг-функции и двух вейвлетов, пример которых приведен на рис.1 слева. На
рис.1 справа показаны базисные функции 
двумерного
вейвлет-преобразования, выполненного как комбинация одномерных преобразований.
Отсутствующая функция 
отличается от 
только поворотом на 900.
Оба семейства вейвлетов построены по схеме лифтинга с интерполяцией первого
порядка (см.п.2,3).
Новое семейство вейвлетов построено на основе известной одномерной схемы
лифтинга [4-6], кратко описанной в п.2, обобщенной на случай двумерного
сигнала, как описано в п.3. В п.4 рассмотрено построение операторов
предсказания для обобщенной схемы лифтинга. В п.5 рассмотрено расположение
полос анализа на плоскости пространственных частот для предлагаемой схемы преобразования.
Наконец, результаты эксперимента по сжатию ряда изображений с использованием
разных систем вейвлетов описаны в п.6.
Рис.1. Основные типы базисных функций
вейвлет-синтеза для шахматной схемы (слева) и для линейной схемы (справа;
отсутствующая четвертая функция отличается от третьей поворотом на 90
градусов).
2. Вэйвлет преобразование по схеме лифтинга
Первым шагом прямого вейвлет преобразования одномерного сигнала по схеме
лифтинга [4] является разделение по каналам отсчетов сигнала с четными (верхний
канал) и нечетными номерами (нижний канал) (рис.2. Схема лифтинга. Блок
анализа.). Вторым шагом является вычисление разности между
нечетно-нумерованными отсчетами и их оценкой (предсказанием) по соседним
отсчетам с четными номерами:
,
(1)
где 
- оператор
предсказания 
-го отсчета. Выход нижнего канала 
представляет собой
вейвлет коэффициенты соответствующего уровня разложения. Последним шагом
лифтинга вычисляется выход верхнего канала 
, представляющий сигнал с вдвое меньшим
пространственным/временным разрешением. На этом шаге четно-нумерованные отсчеты
корректируются по коэффициентам так, чтобы сохранялось
среднее значение сигнала:
,
(2)
так чтобы
,
(3)
где 
- оператор коррекции -го элемента сигнала в верхнем канале по выходу нижнего
канала.
Один уровень обратного
вейвлет преобразования представляет собой те же шаги, пройденные в обратном
порядке (рис.2. Схема лифтинга. Блок синтеза.), т.е. восстановление
четно-нумерованных отсчетов вышележащего уровня:
,
(4)
нечетно-нумерованных отсчетов:
,
(5)
и их объединение в единый
сигнал.
Если в нижнем канале блока синтеза сигнал отсутствует, блок синтеза
производит интерполяцию сигнала, поступившего в верхний канал. В соответствии с (4) и (5), сигнал 
удлиняется вдвое
вставкой промежуточных отсчетов, найденных как 
. Таким образом, основой для построения оператора
предсказания являются всевозможные интерполяционные схемы [4,5]. Например,
сплайн-интерполяция первого порядка описывается оператором предсказания
,
(6)
а сплайн-интерполяция второго
порядка – оператором
. (7)
Оператор замещения,
определенный из условия (3), в обоих случаях имеет вид
.
(8)
Схема лифтинга приводит к семейству биортогональных вейвлетов, для которых
и коэффициенты разложения, и результат синтеза определяются базисом блока
синтеза [6]. Важным достоинством биортогональных вейвлетов является то
обстоятельство, что базис блока синтеза образован симметричными и гладкими
функциями.
Рис.2. Схема лифтинга. Блок анализа и блок синтеза.
3. Обобщение схемы лифтинга для двумерного
сигнала
Традиционно вейвлет преобразование двумерных сигналов (изображений)
производится как последовательность одномерных преобразований: по строкам и по
столбцам. Один уровень вейвлет-анализа, осуществленного по такой схеме,
преобразует изображение размером 
к изображению размером
вдвое меньшего
пространственного разрешения по обеим координатам и трем группам
вейвлет-коэффициентов по 
отсчетов в каждой,
смысл которых будет подробнее рассмотрен в п.5. Базисные функции такого
преобразования образованы произведениями базисных функций одномерных
преобразований по направлениям и .
В настоящей работе на основе схемы лифтинга предложена схема анализа
изображений, не являющаяся комбинацией линейных преобразований. Выделим на
двумерной сетке две вложенных решетки: решетке Р1 будут принадлежать
позиции 
с четными суммами номеров
строки и столбца 
, решетке Р2 - позиции с нечетными суммами . Если каждому элементу изображения сопоставить клетку
шахматной доски, первая решетка будет образована черными клетками, вторая –
белыми (см.рис.3).
Первый этап анализа выполним в точности по схеме (1)-(2) (рис.2), где
отсчеты изображения, принадлежащие решетке Р1, направляются в верхний канал, а
отсчеты решетки Р2 – в нижний канал. Для изображения размером , выход нижнего канала дает 
вейвлет-коэффициентов
соответствующего уровня разложения, а выход верхнего канала представляет собой
сглаженную версию изображения, заданную отсчетами первой
решетки, расположенными на плоскости в шахматном порядке (рис.3).
Рис.3. Распределение отсчетов
изображения по каналам лифтинга в шахматной схеме преобразования: закрашенные
позиции принадлежат решетке Р1, белые – решетке Р2, позиции со светлой
закраской– сетке С1, с темной закраской – сетке С2. Окружности объединяют
группы отсчетов на Р1 (сплошная линия) и на С1 (штриховая линия), участвующих в
предсказании центрального элемента.
Над этой версией изображения произведем второй этап анализа. Выделим на
решетке Р1 две вложенных сетки: сетка С1, содержащая строки с четными номерами
(позиции под светло-серыми квадратами на рис.3), и сетка С2, содержащая строки
с нечетными номерами (позиции под темно-серыми квадратами на рис.3). Первая
сетка представляет собой прямоугольную решетку с шагом 2 по горизонтали и
вертикали с началом в точке 
, вторая – прямоугольную решетку тех же размеров с началом в
точке 
. Второй этап анализа производим по той же схеме, направляя
элементы сетки С1 в верхний канал, сетки С2 – в нижний канал блока анализа. На
втором этапе анализа выходом верхнего канала является изображение размером , заданное на сетке С1, то есть, как и для комбинации
линейных преобразований по горизонтали и вертикали, изображение вдвое меньшего пространственного разрешения
по обеим координатам. Выходом нижнего канала является группа вейвлет-коэффициентов.
Один уровень синтеза представляет собой те же шаги, пройденные в обратном
порядке.
Далее нашу схему преобразования двумерных сигналов будем называть шахматной
схемой, а традиционную – линейной схемой.
4. Построение операторов
предсказания для шахматной схемы анализа изображений
На обоих этапах анализа мы используем одну и ту же схему интерполяции
элементов сигнала в верхнем канале для предсказания элементов сигнала,
направляемых в нижний канал, однако эта схема применяется к разным окрестностям
предсказываемой/корректируемой точки: на втором этапе окрестность оказывается
повернута на 450 и растянута в 
раз.
Рассмотрим общий подход к построению операторов предсказания на двумерной
решетке. Выделим на решетке Р1 группы отсчетов, равноудаленных от
предсказываемой позиции решетки Р2, т.е.
принадлежащих окружностям с центром в точке . Так, первая группа содержит 4 позиции 
, 
относительно центра ; вторая группа объединяет 8 позиций 
, 
, 
, 
относительно . Эти группы отсчетов участвуют в предсказании на первом этапе
анализа. Аналогично, выделим на сетке С1 группы отсчетов, равноудаленных от
предсказываемой позиции сетки С2. Эти группы
отсчетов участвуют в предсказании на втором этапе анализа. Группы одного номера
на решетке Р1 и на сетке С1 содержат одинаковое количество отсчетов, но их
положение трансформируется: если на решетке Р1 М-ой группе отсчетов принадлежит
точка с координатами 
относительно центра , то на сетке С1 М-ая группа содержит позицию 
относительно центра.
Действие операторов предсказания и коррекции применительно к группам
отсчетов одно и то же на обоих этапах анализа.
Порядком предсказания будем называть число ближайших к отсчету групп, участвующих в
предсказании. Из соображений симметрии ясно, что отсчеты одной группы участвуют
в предсказании с одним и тем же весовым коэффициентом, т.е. своим средним
значением. Тогда оператор предсказания М-го порядка имеет вид:
,
(9)
где 
- среднее по k-той группе отсчетов, на первом этапе анализа
взятых на решетке Р1, а на втором – на сетке С1. Очевидно, если все отсчеты
изображения равны константе, результатом предсказания должна быть та же
константа, откуда
.
(10)
Учитывая (9) и (10), получаем оператор предсказания
первого порядка:
(11)
и оператор предсказания второго порядка:
. (12)
Лучшие
частотные свойства фильтров вейвлет-синтеза (см.п.5) достигаются при 
.
Оператор коррекции, удовлетворяющий (3), одинаков для операторов 
и 
:
,
(13)
где
корректируемая точка на первом этапе анализа принадлежит решетке Р1, а на
втором - сетке С1; соответственно, группа коэффициентов 
берется на решетке Р2
или на сетке С2.
5. Частотная интерпретация шахматной схемы
вейвлет-преобразования изображения
Каждая группа коэффициентов разложения двумерного сигнала есть результат
пропускания этого сигнала через полосовой фильтр, вырезающий определенную
область на плоскости пространственных частот 
, и последующего прореживания.
Однако, линейная схема преобразования изображений и шахматная схема
различаются по способу разбиения частотной плоскости полосовыми фильтрами.
В линейной схеме, два этапа вейвлет-анализа (по строкам и по столбцам)
преобразуют изображение размером N*N
к четырем матрицам размером (N/2)*(N/2),
каждая из которых есть результат фильтрации входного изображения (с последующим
прореживанием по обоим направлениям) одним из четырех фильтров: нижних
пространственных частот по обеим кординатам (НН), верхних частот по обеим
кординатам (ВВ), фильтрами нижних частот по одному направлению и верхних - по
другому (НВ, ВН).
В шахматной схеме первый этап анализа преобразуют изображение к двум
матрицам половинного размера в результате фильтрации (с последующим
прореживанием в шахматном порядке) фильтрами нижних и верхних пространственных
частот. На втором этапе анализа изображение на выходе НЧ фильтра поворачивается
на 450 и подвергается той же операции. Таким образом, в шахматной
схеме представлены не четыре, а только три типа фильтров: нижних нижних (НН),
верхних нижних (НВ) и верхних (В) пространственных частот по обеим кординатам,
дающих после прореживания на выходе, соответственно, ¼, ¼ и
½ часть общего числа вейвлет-коэффициентов одного уровня разложения.
На рис.4 схематически представлено разбиение частотной плоскости полосовыми
фильтрами анализа/синтеза для линейной и шахматной схем.
Рис.4.
Расположение полос анализа/синтеза на частотной плоскости слева – для линейной
схемы, справа – для шахматной схемы.
6. Аппроксимация изображений
вейвлетами, построенными по линейной и по шахматной схеме, в приложении к
задачам сжатия.
Наиболее значимые на сегодняшний
день методы сжатия изображений, такие как JPEG или EZW,
основаны на преобразовании изображения к системе коэффициентов, представляющих
определенные полосы пространственных частот исходного изображения. Сжатие
происходит за счет отбрасывания информации о части спектральных коэффициентов
(грубое квантование, пороговое отбрасывание), или, другими словами, за счет
аппроксимации изображения неполным набором базисных функций [1,3,7].
Мы проводили сравнение линейной и шахматной схем для целей сжатия по
следующему принципу: тестовое изображение раскладывалось по обеим системам
вейвлетов, затем в обоих разложениях было оставлено одно и то же число
наибольших коэффициентов и выполнено обратное преобразование. Мерой ошибки был
квадрат разности восстановленного и исходного изображений:
.
(14)
При построении сравниваемых
систем вейвлетов использовался один и тот же порядок интерполяции
(предсказания), например, предсказание первого порядка на прямой, определяемое
оператором (6), и предсказание первого порядка на плоскости, определяемое
оператором (11). При этом сравниваемые системы имеют базисные функции примерно
равные по ширине (см. рис.1).
Как и следовало ожидать, результат сравнения существенно зависит от вида
тестового изображения. Если на изображении преобладают линии (контуры), меньшую
ошибку сжатия (14) дает преобразование по линейной схеме. Если рисунок
образован «пятнами», лучший результат дает преобразование по шахматной схеме.
Однако уменьшение ошибки сжатия при использовании шахматной схемы для всех
тестовых изображений оказалось очень невелико и составило единицы или доли
процента.
Заметим, что пятенная структура, лучше
передаваемая более симметричными функциями шахматной схемы, может создаваться в
самом процессе вейвлет-анализа, при построении уменьшенной версии изображения.
Действительно, мы получили наибольший выигрыш (до 15% по критерию (14) при
представлении тех же изображений 1/8 частью вейвлет-коэффициентов), когда
использовали для преобразования одного и того же изображения обе схемы,
применяя на разных этапах анализа (и, соотвественно, синтеза) разные схемы
преобразования. При этом на первых этапах анализа использовалась линейная схема
преобразования, а на последних этапах - шахматная.
ЛИТЕРАТУРА
1.У.Прэтт.
Цифровая обработка изображений. Т.1, 312 с. М., Мир, 1982.
2.
Филимонов Р.П. Иконика на рубеже веков. Состояние и перспективы. Оптический
журнал, 1999, т.66, №6, с.5-26.
3.
Л.Левкович-Маслюк, А.Переберин. Введение в вейвлет-анализ. ГрафиКон'98, Москва, сентябрь 1998.
4. Sweldens W. The
lifting scheme: A custom-design construction of biorthogonal wavelets. Journal of Applied and Computational Harmonic
Analysis. 1996, V.3, N2, P.186-200.
5. Sweldens W.,
Schroder P. Building your own wavelets at home. In Wavelets in Computer
Graphics, pp. 15-87. ACM SIGGRAPH Course Notes, 1996.
6.
7.
Shapiro J.M. Embedded image coding using zerotrees of wavelets
coefficients. IEEE Trans. Signal
Processing, Dec. 1993, Vol. 41, pp. 3445-3462.