Исследование эффективности алгоритмов компрессии изображений на основе обобщенных вейвлет-преобразований Хаара

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

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

В работе [3], авторы охарактеризовали неразделимые вейвлет-базисы, представляющие собой многомерные аналоги базиса Хаара. Такой вейвлет базис был определен, как вейвлет базис над L ²( R n ) с компактным носителем, соответствующий кратномасштабному анализу порожденному масштабирующей функцией вида, где x q ( x ) характеристическая функция компактного множества Q образующего интегральное самоподобное покрытие R ⁿ .

Построение таких преобразований, а именно отыскание масштабирующей функции является довольно сложной задачей, что затрудняет использование этого метода. В работах [7, 8] был предложен метод построения таких вейвлет базисов над 2.,2

L ( R ) с использованием систем счислений, основаниями которых являются целые гауссовы числа.

В работе [2] было представлено обобщение метода построения неразделимых двумерных вейвлет-базисов Хаара. Такое обобщение стало возможным после разработки венгерскими математиками Катаем и Ковачем теории, так называемых, канонических систем счисления (КСС) в квадратичных полях [4, 5, 6]. В работе [2] показано, что, для каждой КСС может быть построен неразделимый вейвлет-базис, причем геометрические характеристики носителей этих вейвлетов различны. Такое разнообразие неразделимых вейвлетов привело к задаче исследования эффективности адаптивного выбора наиболее подходящего вейвлет-базиса, для некоторого изображения, либо класса изображений.

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

Канонические системы счисления в квадратичных полях

Пусть Q ( V d ) есть квадратичное поле Q (V d ) = { z = a + b V d ; a , b e q } , d e Z , свободно от квадратов. В работе рассматриваются только мнимые квадратичные поля, т.е. d < - 1.

Если для элемента z = a + b V d " e Q (V d ) норма 2     2

и след - целые числа: Norm ( z ) = a - db e Z, Tr ( z ) = 2 a e Z, то элемент называется целым алгебраическим числом поля Q (V d ). Целое алгебраическое число z = a + bjd называется целым гауссовым числом, если a , b e Z .

В работах [5], [6] введено понятие канонической системы счисления в кольце S (V d ) целых элементов поля Q ( V d ).

Целое алгебраическое число называется основанием канонической системы счисления в кольце целых поля Q( d), если любой целый элемент поля однозначно представим в форме конечной суммы:

k ( z )

z = E Z j ^ , j '= 0

где Z j e D = { 0,i, —, | Norm( a )| - 1 } .

Пара (a, D) называется канонической системой счисления в кольце S( d) целых поля Q( d).

Для представления числа z e S ( 4d ) в КСС ( a , D ) часто используют, так называемую позиционную запись этого числа (адрес числа): ^z = ^{( z}k ( z ) , ^zk ( z ) - 1 - ^z 0 ) а , ^{где z}j ^e D .

Фундаментальной областью T( a , D ) e C КСС

( a , D ) в кольце S (V d )

целых элементов поля

Q ( d )

называется множество комплексных чисел с нулевой целой частью, т.е:

- 1

T( a , D ) = E d j ^ , d j e D . j =-”

Пусть a = (ao, o-) - пара линейно независимых векторов пространства R2 . Линейная оболочка с целыми коэффициентами Г векторов (do, d) назы вается решеткой над R2 с базисом a = (do, di).

Г = | : I = |do + Iidi}, I0.Ii e Z .

Решетки ГS( d) над кольцами целых алгебраи- ческих чисел S( d ) порождаются базисами:

• i)    a = ( (i,0), (0,7 d ) ) , при d = 2,3(mod4);

f Ja

• 2)    a = (—,0), (0, ^d ) , при d = i(mod4),

2        2

V

компоненты I и Ii элементов решетки имеют одинаковую четность.

Обобщенные вейвлет-базисы Хаара

В работе [4] предложен метод построения обобщенных вейвлет-базисов Хаара: Для любой КСС (a, D) в кольце S(Vd) существует КМА, ассоциированный с парой (Г s(^), A), и функция ф = Xt (a, D)

является масштабирующей функцией этого КМА и:

• 1)    функции вейвлет-базиса определяются равенством:

iq

^ = E ^ui + i, j ^ф i,d, ,

j j=i где ui,j - элементы унитарной матрицы U, в которой иi,j = q-i/2, j = i-q , ui, j

( i - i)(2 j - i) n 2 q

где i = 2 — q , j = i — q , d j e D , q = |det A |;

• 2)    коэффициенты фильтра для преобразования с базисом ^ i определяются равенствами:

hj =ui,j, j = i—q, gi = ui, j, i = 2 — q, j = i — q .

Основная идея алгоритмов вейвлет-декомпози-ции, на основе описанных выше базисов, базируется на интерпретации точек двумерной целочисленной решетки (растра изображения) как элементов кольца целых алгебраических чисел квадратичного поля, т.е. осуществляется переход от двумерной целочисленной решетки Г Z к решетке целых алгебраических чисел Г s ( d d ) некоторого квадратичного поля. После такого перехода, двумерная индексация отсчетов исходного сигнала, заменяется одномерной, в силу существования отображения множества целых алгебраических чисел (по сути двумерных точек) на множество адресов этих чисел, что позволяет интерпретировать отсчеты изображения как точки фундаментальной области КСС.

Такой подход предполагает два варианта: исходный сигнал полностью покрывается фундаментальной областью КСС, либо ее фрагментом. В работе [1] предложены и подробно описаны алгоритмы декомпозиции и реконструкции исходного сигнала для двух рассмотренных случаев. Для первого случая предложен алгоритм с полным деревом декомпозиции (FDT), для второго случая - алгоритм с частичным деревом декомпозиции (PDT). На основе предложенных алгоритмов декомпозиции и реконструкции были реализованы алгоритмы компрессии и декомпрессии цифровых изображений. Основная идея этих алгоритмов заключается в наложении фундаментальной области некоторой КСС на исходное изображение и последующей декомпозиции по адресам точек этой фундаментальной области.

Экспериментальные исследования

В этом разделе представлены результаты экспериментов и сравнительный анализ предложенных алгоритмов с алгоритмом компрессии на основе разделимого вейвлет-базиса Хаара. Качество алгоритмов оценивалось по следующим параметрам: пиковое соотношение сигнал/шум ( PSNR ), коэффициент компрессии ( k c ), и визуальное качество восстановленной аппроксимации изображения.

Наиболее показательным экспериментом, демонстрирующим целесообразность адаптивного выбора вейвлет-базиса, является эксперимент на синтезированном изображении «линии». Было сгенерировано тестовое изображение «линии» представленное на рисунке 1. На основе этого изображения было сгенерировано еще 18 тестовых изображений, которые были получены посредством последовательного поворота исходного изображения на угол 5°.

Рис. 1. Тестовые изображения при различных углах поворота и фундаментальные области КСС: у = 45 ° ,

T ( - 1 + i ,{0Д}) (а), ^Y = ^{25 ,} T ( - 1 + i Тз,{0,1,2,3}) ^(б)

Для полученного набора изображений был рассчитан коэффициент компрессии для алгоритмов компрессии FDT( - 1 + i ), FDT ( i V2), FDT( - 1 + i V3") и Haar, при ширине интервала квантования б = 10. Эксперимент показал, что при различных углах поворота структурные особенности изображения согласуются со структурными особенностями фундаментальных областей, что приводит к выигрышу того или иного алгоритма. Подтверждающие этот вывод количественные данные представлены в таблице 1.

Таблица 1. Зависимость k_c от угла поворота изображения «линии»

Y	FDT ( - 1 + i )	FDT( i 2)	FDT ( - 1 + i VS)	Haar
10 °	7.219	8.751	8.644	8.478
25 °	6.261	6.751	7.207	6.244
45 °	6.337	5.829	6.134	5.878

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

Также, целесообразность адаптивного выбора вейвлет-базиса была исследована на классе текстурных изображений. Исследовалась выборка из 130 полутоновых текстурных изображений размером 512 х 512 пикселей, из атласа «Brodatz». По этому множеству изображений были вычислены парамет- ры PSNR и kc для следующих алгоритмов: FDT(-1 + i), FDT(iV2), FDT(-1 + iV3) и Haar, при ширине интервала квантования 5=10. Как показали эксперименты, исходная выборка изображений может быть разбита на 4 класса, в каждом из которых наиболее эффективен только один из алгоритмов, независимо от ширины интервала квантования. Распределение исходной выборки по классам представлено в таблице 1.

Исследования показали, что рассмотренные алгоритмы эффективны в «своих» классах изображений при различных значениях ширины интервала квантования, однако разница эффективности различных алгоритмов уменьшается с ростом ширины интервала квантования. Количественные данные эксперимента, на примере класса K_{FDT ( i 2)} , представлены в таблице 2.

Таблица 2. Распределение исходной выборки по классам

Класс	Число изображений	Процентное соотношение
K Haar	60	46%
KFDT ( - 1 + i )	13	10%
К      r- KFDT ( i 2)	41	32.5%
K         r- KFDT ( - 1 + i V3)	16	11.5%

Таблица 3. Средние значения PSNR и k_c для класса изображений K_{FDT ( i 2)}

б	Haar		FDT( i 2)
	PSNR	kc	PSNR	kc
2	45,3982	1,6258	46,603	1,6414
4	41,37	2,1366	41,7622	2,1666
6	38,389	2,5952	38,5862	2,6786
8	36,3564	3,001	36,394	3,1402
10	35,0026	3,3186	34,9308	3,5082
12	33,6814	3,664	33,8362	3,8328
14	32,6728	3,9614	32,8332	4,143
16	31,772	4,2558	31,9276	4,4528
18	31,0288	4,5294	31,1544	4,757
20	30,3278	4,8106	30,4278	5,0492

На рисунке 2 представлены фрагменты восстановленных аппроксимаций исходного изображения для четырех алгоритмов компрессии. Как видно из представленных иллюстраций, использование обобщенных вейвлетов Хаара в задаче компрессии позволяет повысить визуальное качество восстановленных изображений, за счет того, что артефакты имеют непрямоугольную сложную конфигурацию, и менее заметны для зрительной системы человека.

а

б

в

Рис.2. Исходное изображение (а), восстановленные изображения для алгоритмов Haar (б), FDT ( - 1 + i ) (в),

г

FDT (

3+^7-) (г)

Заключение

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

Работа выполнена в рамках программы фундаментальных научных исследований ОИТВС РАН «Новые физические и структурные решения в инфотелекоммуникациях», проект "Разработка новых методов и алгоритмов кодирования изображений в инфотелекоммуникационных системах реального времени", в рамках российско-американской программы «Фундаментальные исследования и высшее образование» (CRDF Project RUX0-014-SA-06), а также при поддержке Российского фонда фундаментальных исследований (РФФИ), гранты № 07-07-97610-р_офи, 06-01-00722-а.