Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Матричная форма

В основе преобразования Хаара лежит вычисление средних и разностей. Оказывается, .что эти операции можно легко выразить с помощью умножений соответствующих матриц (см. [Mulcahy 96] и [Mulcahy 97]). Для примера рассмотрим верхнюю строку простого изображения размера 8 х 8 из рис. 4.8. Каждый, кто немного знаком с операциями над матрицами, легко построит матрицу, которая при умножении на некоторый вектор дает другой вектор, состоящий из четырех полусумм и четырех полуразностей элементов этого вектора. Обозначим эту матрицу Ai. Ее произведение на вектор рассматриваемого примера (верхняя строка матрицы на рис. 4.8) равно (239.5,175.5,111.0,47.5,15.5,16.5,16.0,15.5). Это видно из уравнения (4.1). Аналогично, матрицы А 2 и Аз производят, соответственно, второй и третий шаг преобразования. Его результат показан в формуле.

Вместо того, чтобы вычислять средние и разности строк, можно построить матрицы Ai, A2 и Аз, перемножить их, получить матрицу

/ 239.5 \


/ 207.5 \


/ 207.5 \

/

175.5


79.25


79.25


111.0


32.0


32.0


47.5


31.75


31.75


15.5

15.5

, А2

15.5

~ 1

16.5


16.5


16.5


16.0


16.0


16.0


\ 15.5 )


^ 15.5 )


V 15.5 )

\

W = A1A2A3,

а затем применить ее к вектору I:

,

/255\


/143.38 4


224


64.125


192


32.0


159


31.75


127


15.5


95


16.5


63


16.0


V 32 У


V 15.5 /

В этом заключается только половина работы. Для того, чтобы сделать полное преобразование, необходимо применить W к строкам произведения WI, или, что то же самое, умножим W на (WI) . Результат для удобства тоже транспонируем. Полное преобразование (см. строку timg=w*img*w, рис. 4.12) равно

itr = (w (wi)T) = wiwT.

Для обратного преобразования справедлива формула

w-'(w-ii?;)T = w-i(itr(w-i)T).

В этом месте становится важным нормализованное преобразование Хаара (упомянутое на стр. 216). Вместо вычисления средних (выражений (di + di+\) /2) и разностей (выражений (di — d?;+i) /2) лучше вычислять величины (di + c/j+i) /у/2 и (di di+\) /\/2. Это приводит к ортогональной матрицы W, а хорошо известно, что обращение такой матрицы сводится к ее транспонированию. Следовательно, обратное преобразование запишется в простом виде WTItrW (см. строку cimg=full(w,*sparse(dimg)*w на рис. 4.12).

Между процедурами прямого и обратного преобразования некоторые коэффициенты могут быть квантованы или отброшены. Кроме того, для лучшего сжатия, матрицу Itr можно кодировать по методу RLE и/или по методу Хаффмана.

Функция individ(n) на рис. 4.12 начинается с матрицы преобразования Хаара размера 2x2 (заметим, что вместо знаменателя 2 взято число \/2), затем использует эту матрицу для построения необходимого числа матриц А7;. Функция harmatt(dim) формирует окончательную матрицу Хаара для изображения, состоящего из dim строк и dim столбцов.

Пример: Программа Matlab на рис. 4.15 вычисляет W в виде произведения трех матриц Ai, A2 и Аз, после чего делает преобразования изображения размера 8 х 8 из рис. 4.8. Результатом становится матрица 8x8, состоящая из коэффициентов преобразования, в которой верхний левый коэффициент 131.375 равен среднему всех 64 пикселов исходного изображения.

al=[l/2 1/2 0 0 0 0 0 0; 0 0 1/2 1/2 0 0 0 0;

О 0 0 0 1/2 1/2 0 0; 0 0 0 0 0 0 1/2 1/2;

1/2 -1/2 0 0 0 0 0 0; 0 0 1/2 -1/2 0 0 0 0;

0 0 0 0 1/2 -1/2 0 0; О О О О О О 1/2 -1/2]; У. al*[255; 224; 192; 159; 127; 95; 63; 32]; а2=[1/2 1/2 0 0 0 0 0 0; 0 0 1/2 1/2 О О О О;

1/2 -1/2 О О О О О О; О О 1/2 -1/2 0 0 0 0;

0000100 0; 0000010 0;

00000010; 0000000 1]; аЗ=[1/2 1/2000000; 1/2 -1/2 000000;

0010000 0; 0001000 0;

0000100 0; 0000010 0;

00000010; 0000000 1]; w=a3*a2*al; dim=8;

fid=fopen(,8x8>,'r'); img^freadCfid,[dim,dim])'; fclose(fid); w*img*w' У, Результат преобразования

131.375 4.250 -7.875 -0.125 -0.25 -15.5 0 -0.25

О 0 0 00000

О 0 0 00000

О 0 0 00000

12.000 59.875 39.875 31.875 15.75 32.0 16 15.75

12.000 59.875 39.875 31.875 15.75 32.0 16 15.75

12.000 59.875 39.875 31.875 15.75 32.0 16 15.75

12.000 59.875 39.875 31.875 15.75 32.0 16 15.75

Рис. 4.15. Программа и результат матричного вейвлетного преобразования WIWT.