Опрос

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

Новички

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

Свойства преобразования Хаара

Примеры из этого параграфа иллюстрируют некоторые важные свойства вейвлетного преобразования Хаара, а также общих вейвлетных преобразований. На рис. 4.8 показан высоко коррелированный образ размера 8 х 8 и его преобразование Хаара. Даны числовые значение преобразованных коэффициентов и их графическое представление в виде квадратиков различных серых оттенков. Из-за высокой степени корреляции исходных пикселов, вейвлетные коэффициенты в основном малы по абсолютному значению и многие из них равны нулю.

Замечание. При первом взгляде на рис. 4.8 последнее утверждение кажется ложным. Приведенные коэффициенты вейвлетного преобразования достаточно велики по сравнению с исходными значениями пикселов. Нам известно, что верхний левый элемент матрицы коэффициентов преобразования Хаара должен быть равен среднему значению всех пикселов образа. Поскольку эти пикселы имеют примерно равномерное распределение на интервале [0,255], то это среднее должно быть около 128 (на самом деле, точное значение равно 131.375). А в приведенной таблице это число равно 1051 (что равно 131.375 х 8). Причина заключается в том, что программа, выполнявшая эти вычисления использовала у/2 вместо 2 (см. функцию individ(n) на рис. 4.12).

При дискретном вейвлетном преобразовании большинство получающихся коэффициентов (разностей) отвечают за детали изображения. Детали нижнего уровня представляют мелкие особенности исходного образа. При перемещении на более высокие под диапазонные уровни обнаруживаются более грубые детали данного изображения. Рис. 4.9а поясняет эту концепцию. Показано изображение, равномерно гладкое слева, у которого наблюдается некоторая «шероховатость» справа (то есть, соседние пикселы начинают различаться). На рисунке (Ь) дано графическое представление преобразования Хаара этого образа. Поддиапазоны низкого уровня (отвечающий точным деталям) имеют ненулевые коэффициенты справа, там, где наблюдается «шероховатость» изображения. Поддиапазоны высокого уровня (грубые детали) выглядят похоже, и их коэффициенты также имеют ненулевые коэффициенты слева, поскольку изображение не полностью белое слева.

127

95

63

32

127

159

191

223

127

95

63

32

127

159

191

223

127

95

63

32

127

159

191

223

127

95

63

32

127

159

191

223

51

34.0

-44.5

-0.7

-1.0

-62

0

-1.0

0

0.0

0.0

0.0

0.0

0

0

0.0

0

0.0

0.0

0.0

0.0

0

0

0.0

0

0.0

0.0

0.0

0.0

0

0

0.0

48

239.5

112.8

90.2

31.5

64

32

31.5

48

239.5

112.8

90.2

31.5

64

32

31.5

48

239.5

112.8

90.2

31.5

64

32

31.5

48

239.5

112.8

90.2

31.5

64

32

31.5

Рис. 4.8. Образ 8x8, реконструированный на рис. 4.11 и его преобразование Хаара.

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

255224192159

03264159

255224192159

03264159

255224192159

03264159

255224192159

03264159

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

Это дает хорошее сжатие с частичной потерей информации, которая, однако не отразится на качестве восстановленного образа. Реконструкция образа делается очень быстро при минимальной потери качества. На рис 4.11 показаны три реконструкции исходного образа размера 8 х 8 из рис. 4.8. Они получены с помощью, соответственно, 32, 13 и 5 вейвлетных коэффициентов.

(а)

Рис. 4.9. (а) Образ 128 х 128 пикселов с «шероховатостью» справа. (Ь) Его преобразование.

Рис. 4.10 является аналогичным примером. В части (а) дан двухуровневый черно-белый образ, полностью восстановленный с помощью всего 4% коэффициентов (653 коэффициентов из 128 х 128 показаны на рис. (Ь)).

(а)

(Ь)

Рис. 4.10. Восстановление простого образа 128 х 128 пикселов из 4% его коэффициентов.

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

(с) Рис. 4.11. Три реконструкции образа из 8 х 8 пикселов.

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

В строке «f ilename=,lenal28,; dim=128записаны имя файла с изображением и его размер. Файл, использованный автором, был представлен в «сыром» виде. Он состоял из пикселов различных оттенков серого размера в 1 байт каждый. В файле не было никакого заголовка, не было даже разрешения образа (то есть, числа строк и столбцов). Тем не менее, Matlab читает любые файлы. Образ предполагался квадратным, а параметр dim должен быть степенью 2. Присваивание «thresh =» задает процент коэффициентов, которые следует удалить. Это позволяет легко экспериментировать с вейвлетным сжатием.

Файл «harmatt.m» содержит две функции, которые вычисляют преобразование Хаара в матричной форме (см. § 4.2.1).

(Техническое замечание: файлы Matlab с расширением «.т» могут содержать или последовательность команд, или функции, но не одновременно команды и функции. Однако допускается несколько функций в одном файле, при условии, что только самая верхняя функция будет вызываться извне этого файла. Все остальные функции должны вызываться только из этого файла. В нашем случае функция harmatt(dim) вызывает функцию individ(n).)

Пример: Программа из рис. 4.12 используется для вычисления преобразования Хаара изображения «Lena». Затем это изображение реконструируется три раза с отбрасыванием все большего и большего числа коэффициентов деталей. На рис. 4.13 показаны результаты восстановления исходного изображения с помощью 3277, 1639 и 820 вейвлетных коэффициентов, соответственно. Несмотря на сильное прореживание коэффициентов, обнаруживается слабая потеря качества картинки. Полное число вейвлетных коэффициентов, конечно, равно разрешению образа, то есть, 128 х 128 = 16384.

clear; '/, главная программа

filename='Ienal28'; dim=128;

fid=fopen(filename,'r');

if fid==-l dispCfile not found')

else img-fread(fid,[dim,dim] )'; fclose(fid);

end

thresh=0.0; 7. процент отбрасываемых коэффициентов

figure(l), imagesc(img), colormap(gray), axis off, axis square

w-harmatt (dim) ; У, вычисление матрицы Хаара

tin^wfimg+w'; У, прямое преобразование Хаара

tsort=sort(abs(timg(:)));

tthresh=tsort(floor(max(thresh*dim*dim, 1)));

cim=timg.*(abs(timg) > tthresh);

[i,j,s] -find(cim);

dimg=sparse(i,j,s,dim,dim);

'/• figure (2) показывает оставшиеся коэффициенты преобразования

*/,figure(2), spy(dimg), colormap(gray), axis square

figure(2), image(dimg), colormap(gray), axis square

cimg=full(w,*sparse(dimg)*w); density = nnz(dimg);

disp([num2str(100*thresh) "/, отброшенных коэффициентов.7])

disp([num2str(density) ' оставленных коэффициентов ' ...

num2str(dim) 'x' num2str(dim) '.'])

figureO), imagesc(cimg) , colormap(gray) , axis off, axis square

Файл harmatt.m с двумя функциями

function x = harmatt(dim)

num=log2(dim) ;

p = sparse(eye(dim)); q - p;

i=l;

while i<=dim/2;

q(l:2*i,l:2*i) = sparse(individ(2*i));

p=p*q; i=2*i; end x=sparse(p);

function f=individ(n) x=[l, 1] /sqrt(2); y-Cl.-l] /sqrt(2); while min(size(x)) < n/2

x=[x, zeros(min(size(x)),max(size(x)));...

zeros(min(size(x)),max(size(x))), x]; end while min (size (y)) < n/2

y-[y, zeros(min(size(y)),max(size(y)));...

zeros(min(size(y)),max(size(y))), y] ; end f=[x;y];

Рис. 4.12. Программа для вычисления преобразования Хаара (Matlab).

Использование только 820 коэффициентов соответствует отбрасыванию 95% наименьших из них (заметим однако, что часть коэффициентов сразу равнялось нулю, поэтому, реальная потеря данных будет меньше 95%).

конные прогулки

(с) Рис. 4.13. Три реконструкции образа «Lena» из 128 х 128 пикселов.