Преобразование Уолша - Адамара

Введение

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

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

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

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

 

1 ОБЗОР И МАТЕМАТИЧЕСКИЕ  МЕТОДЫ КОДИРОВАНИЯ С ДИСКРЕТНЫМ ПРЕОБРАЗОВАНИЕМ УОЛША-АДАМАРА

 

1.1 Методика кодирования с преобразованием

Основная идея метода кодирования  с преобразованием заключается  в использовании так называемых «обобщенных представлений» сигнала.

Процедура кодирования с преобразованием заключается в следующем.

На этапе компрессии данных (кодирования):

1) каждый блок отсчетов подвергается некоторому преобразованию, в результате которого формируются обобщенные координаты сообщений;

2) осуществляется кодирование обобщенных координат с целью сокращения избыточности данных (достижения эффекта сжатия).

На этапе восстановления (декодирования):

1) декодируются обобщенные координаты;

2) вычисляется обратное преобразование, то есть по декодированным значениям обобщенных координат вычисляются сами отсчеты сигнала.

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

Основной недостаток метода — его  относительная сложность, как на этапе компрессии, так и на этапе  восстановления.

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

Очевидно, что при разработке процедуры  кодирования с преобразованием  приходится решать две основные задачи:

1) выбор вида преобразования для получения обобщенных координат;

2) выбор метода обработки (кодирования) обобщенных координат.

 

1.2 Дискретное преобразование Уолша-Адамара

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

1)Преобразование должно быть обратимым, то есть позволять переходить от обобщенных координат обратно к отсчетам.

2) В результате преобразования основной объем информации о сигнале должен быть сконцентрирован по возможности в меньшем числе обобщенных координат (это обеспечит наибольший эффект сжатия).

3) Преобразование (прямое и обратное) должно достаточно просто вычисляться.

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

Для заданного блока NхN пикселов Р_xy (здесь N должно быть степенью двойки, N=2ⁿ ), его двумерное прямое и обратное преобразования Уолша-Адамара (они обозначаются WHT и IWHT, соответственно) определяются с помощью следующих уравнений (1.1 , 1.2):

	(1.1)

 

	(1.2)

 

 

где H(u,v) - это результат преобразования ( то есть коэффициенты DHT), величина b_i(u) равна биту i в двоичном представлении целого числа u, а p_i(u) определяется с помощью b_j(u) из следующих рекуррентных соотношений (1.3):

p0(u)=bn-1(u), p1(u)=bn-1(u)+bn-2(u), p2(u)= bn-2(u)+bn-3(u), … pn-1(u)=b1(u)+b0(u).	(1.3)

 

Рисунок 1 – упорядоченные ядра WHT при N=4

Рассмотрим, например, u=6=110₂. Нулевой, первый и второй биты, равны соответственно 0,1,1 поэтому b₀(6)=0, b₁(6)=1 и b₂(6)=1. Величины g(x,y,u,v) и h(x,y,u,v) называют ядрами ( или базисными изображениями ) WHT. Их матрицы совпадают. Элементами матрицы служат числа +1 и -1, которые умножаются на 1/N. В результате, преобразование WHT состоит из умножения пикселов на +1 или —1, сложения и деления суммы на N. Но поскольку N=2ⁿ , деление можно делать, сдвигая разряды чисел вправо на n чисел.

Ядра WHT изображены в графической форме на рис.1 при N=4, где белый цвет означает +1, а черный -1 ( для наглядности множитель 1/N опущен ). Строки и столбцы в блоках занумерованы значениями u и v от 0 до 3, соответственно. Число смен знаков в строке или в столбце матрицы называется частотностью строки или столбца. Строки и столбцы на этом рисунке упорядочены по возрастанию частотности. Некоторые авторы предпочитают изображать ядра неупорядоченно, так, как это было определено Уолшем и Адамаром.

Сжатие изображения с  помощью WHT делается также как и для DCT, с заменой уравнений преобразований  ДКТ на уравнения Уолша-Адамара (1.1 , 1.2).

На рис.2 изображены 64 базисных изображения WHT. Рассмотрен случай N = 8. Каждое базисное изображение - это таблица пикселов размера 8x8.

Рисунок 2 – базисные изображения  для WHT размером 8х8

 

 

 

 

1.3 Матрица Уолша-Адамара

Матрица Адамара может быть сформирована рекурсивным методом с помощью построения блочных матриц по следующей общей формуле (1.4):

 

	(1.4)

Также может быть сформирована матрица Уолша-Адамара длиной 2ⁿ. К примеру, в нашем случае необходимо сформировать матрицу 8х8. Сформируем такую матрицу из матриц 4х4 (1.5). Матрица 8х8 приведена в (1.6):

 

1     1     1     1 W4=      1    -1     1    -1              1     1    -1    -1              1    -1    -1     1	(1.5)

 

1     1     1     1     1     1     1     1                      1    -1     1    -1     1    -1     1    -1                      1     1    -1    -1     1     1    -1    -1    W==          1    -1    -1     1     1    -1    -1     1                     1     1     1     1    -1    -1    -1    -1                     1    -1     1    -1    -1     1    -1     1                     1     1    -1    -1    -1    -1     1     1                      1    -1    -1     1    -1     1     1    -1

(1.6)

 

 

1.4 Энтропийное кодирование по Хаффману

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

В нашем случае дополнительно используется кодирование коэффициентов преобразования по Хаффману в составе кодирования с дискретным преобразованием.

 

2 РАЗРАБОТКА АЛГОРИТМА  И КОДЕКА ПРОГРАММЫ НА ОСНОВЕ  КОДИРОВАНИЯ С ДИСКРЕТНЫМ ПРЕОБРАЗОВАНИЕМ  И ЭНТРОПИЙНОГО КОДИРОВАНИЯ КОЭФФИЦИЕНТОВ  ПРЕОБРАЗОВАНИЯ

 

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

2.1 Загрузка изображения  в листинг программы

Загрузка исследуемого изображения  камерамена (рис.2.1) в пакете MATLAB осуществляется с помощью функции imread.

f1=imread('cameraman.tif');

2.2 Вывод изображения

Функция imshow позволяет показать изображение в окне figure. В окне figure также можно выводить различные изображения, гистограммы, графики и т.д1.

imshow(f1);

Рисунок 2.1 - камерамен

2.3 Разбиение исходного  изображения на блоки

Исходное изображение  делится на блоки размером 8х8 пикселей. Функция imcrop «вырывает» блоки размером 8х8 пикселей из исходного изображения, т.к. кодирование с преобразованием предполагает работу с блоками изображения, а не с целым исходным изображением. Всего будет 32 блока по x координате и 32 блока по y координате, а в общем изображение состоит из 1024 блоков или 32².

 

Nblock=8;

Nblock2=Nblock^2;

 

SF=size(size(f1));

if SF(2)==3

    f=f1(:,:,1);

    dummy=1;

end;

if SF(2)==2

    f=f1;

    dummy=2;

end;

 

[M0,N0]=size(f);

Mcrop=M0/Nblock   %number of blocks in Y

Mb=floor(Mcrop)

Ncrop=N0/Nblock   %number of blocks in X

Nb=floor(Ncrop)

 

width0=Nblock*Nb-1;

height0=Nblock*Mb-1;

rect0=[1, 1, width0, height0];

f=imcrop(f,rect0);

 

[M,N]=size(f);

 

2.4 Выбор преобразования

Преобразование Уолша-Адамара в пакете MATLAB можно задать при помощи функции hadamard. Эта функция представляет собой матрицу преобразования. Размер матрицы указывается в скобках.

 

Tvariant=3  %Welch-Hadamard

 

 

if Tvariant ==3

   

    T=1/4*hadamard (8);

end;

 

2.5 Кодирование – декодирование с преобразованием

2.5.1 Регулировка  степени сжатия

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

Mcrop=M/Nblock   %number of blocks in Y

Ncrop=N/Nblock   %number of blocks in X

width=Nblock-1;

height=Nblock-1;

block=zeros(Nblock);

Tblock=zeros(Nblock);

 

dCR =.25;        %step in Compression Ratio

 

f0=f;

varnoise=[0, 0.00005, 0.0001, 0.0005, 0.001, 0.005, 0.01, 0.05, 0.1, 0.5]

 

for nn = 1:10;

%    f = imnoise(f0,'gaussian',0,varnoise(nn));  % 0.1; 0.01;0.001

%    f = imnoise(f0,'salt & pepper',varnoise(nn));

    CR = 1+(nn-1)*dCR;      % COMPRESSION

%    CR = 1;                % NOISE ROBUSTNESS

    CompressRatio(nn)=CR;

    K = ceil(Nblock2/CR)

   

    Tf=zeros(M,N);  % TRANSFORMED (ENCODED) IMAGE

 

    Rf=zeros(M,N);  % RESTORED (DECODED) IMAGE

2.5.2 Блочное кодирование

Здесь происходит двумерное преобразования блоков изображений при помощи преобразования Уолша-Адамара. В результате преобразования происходит переход от уровней яркостей изображения к его обобщенному пространственному спектру.

BLOCK IMAGE encoding

    for m=1:Mcrop;

        m0=m-1;

        for n=1:Ncrop;

            n0=n-1;

            xmin=1+n0*Nblock;                % face blocks ~ #14...15

            ymin=1+m0*Nblock;                % face blocks ~ # 7...8

            rect=[xmin, ymin, width, height];

            block=imcrop(f,rect);

            Tblock=T*(T*double(block))';  % 2D Transform

           

            Tblock1=uint8(Tblock);

            sig=reshape(Tblock1,8*8,1);

        end;

    end;

            a=sig

 

2.5.3 Кодирование  - декодирование коэффициентов преобразования  по Хаффману

2.5.3.1 Построение гистограммы распределения

Строится гистограмма  распределения коэффициентов преобразования (рис.2.2). Гистограмма необходима для  построения словаря Хаффмана.

Рисунок 2.2 – гистограмма  коэффициентов преобразования

haffman encoding-decoding

 

NN=2^8;

% Create probability of coef

for n=1:NN;

    n0=n-1;

    symbols(n)=n0;       % 'symbol' is just a series 0,1,...,255 

    [an0,x]=find(a==n0); % an0=1 if a(x)=n0  

    frequence(n)=sum(an0);

end;

ss=sum(frequence);

frequence=frequence/ss; % 'prob' in huffmandict = frequence

 

%Plot coef appearance distribution

plot(symbols,frequence,'r')

grid on

axis tight

title('Probability of pixel code')

xlabel('8bit pixel code')

2.5.3.2 Построение словаря Хаффмана

Словарь Хаффмана позволяет  закодировать коэффициенты преобразования кодами разной длины в зависимости  от частоты появления в матрице преобразования. В MATLAB функция huffmandict позволяет построить словарь.

Create Huffman code dictionary for the image

[dict,avglen]=huffmandict(symbols,frequence);

 

% Show the Huffman code dictionary for the image

for n=1:NN;

    y=size(dict{n,2});

    sy(n)=y(2);

end;

symax=max(sy)

 

% Ajust the fprintf function in accordance with SYMAX to print the dictionary

for n=1:NN;

    x=dict{n,1};

    y=dict{n,2};

    sy=size(y);

    if sy(2)==1 fprintf('%4d  %10d\n',x,y); end;

    if sy(2)==2 fprintf('%4d  %10d  %3d\n',x,y(1),y(2)); end;

    if sy(2)==3 fprintf('%4d  %10d  %3d   %3d\n',x,y(1),y(2),y(3)); end;

    if sy(2)==4 fprintf('%4d  %10d  %3d   %3d   %3d\n',x,y(1),y(2),y(3),y(4)); end;

    if sy(2)==5 fprintf('%4d  %10d  %3d   %3d   %3d   %3d\n',x,y(1),y(2),y(3),y(4),y(5)); end;

    if sy(2)==6 fprintf('%4d  %10d  %3d   %3d   %3d   %3d   %3d\n',x,y(1),y(2),y(3),y(4),y(5),y(6)); end;

    if sy(2)==7 fprintf('%4d  %10d  %3d   %3d   %3d   %3d   %3d   %3d\n',x,y(1),y(2),y(3),y(4),y(5),y(6),y(7)); end;

    if sy(2)==8 fprintf('%4d  %10d  %3d   %3d   %3d   %3d   %3d   %3d   %3d\n',x,y(1),y(2),y(3),y(4),y(5),y(6),y(7),y(8)); end;

    if sy(2)==9 fprintf('%4d  %10d  %3d   %3d   %3d   %3d   %3d   %3d   %3d  %3d\n',x,y(1),y(2),y(3),y(4),y(5),y(6),y(7),y(8),y(9)); end;

    if sy(2)==10 fprintf('%4d  %10d  %3d   %3d   %3d   %3d   %3d   %3d   %3d  %3d  %3d\n',x,y(1),y(2),y(3),y(4),y(5),y(6),y(7),y(8),y(9),y(10)); end;

    if sy(2)==11 fprintf('%4d  %10d  %3d   %3d   %3d   %3d   %3d   %3d   %3d  %3d  %3d  %3d\n',x,y(1),y(2),y(3),y(4),y(5),y(6),y(7),y(8),y(9),y(10),y(11)); end;

    if sy(2)==12 fprintf('%4d  %10d  %3d   %3d   %3d   %3d   %3d   %3d   %3d  %3d  %3d  %3d  %3d\n',x,y(1),y(2),y(3),y(4),y(5),y(6),y(7),y(8),y(9),y(10),y(11),y(12)); end;

    if sy(2)==13 fprintf('%4d  %10d  %3d   %3d   %3d   %3d   %3d   %3d   %3d  %3d  %3d  %3d  %3d  %3d\n',x,y(1),y(2),y(3),y(4),y(5),y(6),y(7),y(8),y(9),y(10),y(11),y(12),y(13)); end;

    if sy(2)==14 fprintf('%4d  %10d  %3d   %3d   %3d   %3d   %3d   %3d   %3d  %3d  %3d  %3d  %3d  %3d  %3d\n',x,y(1),y(2),y(3),y(4),y(5),y(6),y(7),y(8),y(9),y(10),y(11),y(12),y(13),y(14)); end;

    if sy(2)==15 fprintf('%4d  %10d  %3d   %3d   %3d   %3d   %3d   %3d   %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d\n',x,y(1),y(2),y(3),y(4),y(5),y(6),y(7),y(8),y(9),y(10),y(11),y(12),y(13),y(14),y(15)); end;

    if sy(2)==16 fprintf('%4d  %10d  %3d   %3d   %3d   %3d   %3d   %3d   %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d\n',x,y(1),y(2),y(3),y(4),y(5),y(6),y(7),y(8),y(9),y(10),y(11),y(12),y(13),y(14),y(15),y(16)); end;

    if sy(2)==17 fprintf('%4d  %10d  %3d   %3d   %3d   %3d   %3d   %3d   %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d\n',x,y(1),y(2),y(3),y(4),y(5),y(6),y(7),y(8),y(9),y(10),y(11),y(12),y(13),y(14),y(15),y(16),y(17)); end;

    if sy(2)==18 fprintf('%4d  %10d  %3d   %3d   %3d   %3d   %3d   %3d   %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d\n',x,y(1),y(2),y(3),y(4),y(5),y(6),y(7),y(8),y(9),y(10),y(11),y(12),y(13),y(14),y(15),y(16),y(17),y(18)); end;

    if sy(2)==19 fprintf('%4d  %10d  %3d   %3d   %3d   %3d   %3d   %3d   %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d\n',x,y(1),y(2),y(3),y(4),y(5),y(6),y(7),y(8),y(9),y(10),y(11),y(12),y(13),y(14),y(15),y(16),y(17),y(18),y(19)); end;

    if sy(2)==20 fprintf('%4d  %10d  %3d   %3d   %3d   %3d   %3d   %3d   %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d\n',x,y(1),y(2),y(3),y(4),y(5),y(6),y(7),y(8),y(9),y(10),y(11),y(12),y(13),y(14),y(15),y(16),y(17),y(18),y(19),y(20)); end;

    if sy(2)==21 fprintf('%4d  %10d  %3d   %3d   %3d   %3d   %3d   %3d   %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d\n',x,y(1),y(2),y(3),y(4),y(5),y(6),y(7),y(8),y(9),y(10),y(11),y(12),y(13),y(14),y(15),y(16),y(17),y(18),y(19),y(20),y(21)); end;

    if sy(2)==22 fprintf('%4d  %10d  %3d   %3d   %3d   %3d   %3d   %3d   %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d\n',x,y(1),y(2),y(3),y(4),y(5),y(6),y(7),y(8),y(9),y(10),y(11),y(12),y(13),y(14),y(15),y(16),y(17),y(18),y(19),y(20),y(21),y(22)); end;

    if sy(2)==23 fprintf('%4d  %10d  %3d   %3d   %3d   %3d   %3d   %3d   %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d  %3d\n',x,y(1),y(2),y(3),y(4),y(5),y(6),y(7),y(8),y(9),y(10),y(11),y(12),y(13),y(14),y(15),y(16),y(17),y(18),y(19),y(20),y(21),y(22),y(23)); end;

end;

avglen

 

2.5.3.3 Кодирование – декодирование по Хаффману

Закодировать по Хаффману в MATLAB позволяет функция huffmanenco, зависящая от входного сигнала ( матрицы преобразования ) и словаря. На приемную сторону помимо закодированного сигнала передается словарь и алгоритм кодирования, по которому производится восстановление. Декодировать позволяет функция huffmandeco.

 

hcode = huffmanenco(sig,dict);         % Encode the data.

 

 

dhsig = huffmandeco(hcode,dict);       % Decode the code.

 

dhgreen=reshape(dhsig,8*8,1);

 

2.5.4 Отбрасывание коэффициентов преобразования

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

            TBresh = abs(reshape(dhgreen,8*8,1)); % преобразование матричного блока в вектор

            RTBresh = sort(TBresh,'descend'); %– упорядочивание вектора по v

            Threshold = RTBresh(K);

            for m1=1:Nblock;

                for n1=1:Nblock;

                    coef=Tblock(m1,n1);

                    if abs(coef)<Threshold

                       %coef=0;

                       %Tblock(m1,n1)=coef;

                       Tblock(m1,n1)=0;

                    end; % if

                end; % n1

            end; % m1

 

2.5.5 Декодирование

Декодирование выполняется  с помощью обратного двумерного преобразования Уолша-Адамара.

J=Tblock;

Rblock=T'*(T'*J)';            % 2D Inverse Transform

 

2.5.6 Склеивание из блоков декодированного изображения

Здесь происходит соединение матрицы изображения из субматриц Tblock.

TRANSFORMED (RESTORED) IMAGE CONCATENATION FROM Tblocks (Rblocks)

            if m==1 & n==1 Tf=J; Rf=R; end;

            if m==1 & n>1 Tf=[Tf,J]; Rf=[Rf,R]; end;               % row concat

            if m==2 & n==1 Jrow=J; Rrow=R; end;                    % new row is started

            if m>1 & n>1 Jrow=[Jrow,J]; Rrow=[Rrow,R]; end;        % row concat

            if m>2 & n==1 Tf=[Tf;Jrow]; Jrow=J; Rf=[Rf;Rrow]; Rrow=R; end;

            if m==Mcrop & n==Ncrop Tf=[Tf;Jrow]; Rf=[Rf;Rrow]; end;

 

 

 

 

 

 

 

 

 

 

Результат кодирования камерамена представлен на рисунке 2.3.

Рисунок 2.3 – исходное и  декодированное изображение

Данный результат говорит  о том, что кодек изображения  работает некорректно, т.к. восстановленное  изображение не имеет ничего общего с исходным изображением. Вероятнее  всего ошибка произошла в блоке  склеивания изображений ( п. 2.5.6 ), т.к. восстановленное изображение напоминает блок изображения 8х8.

 

3 ОЦЕНКА ЭФФЕКТИВНОСТИ КОДЕКА ИЗОБРАЖЕНИЯ НА ОСНОВЕ КОДИРОВАНИЯ С ДИСКРЕТНЫМ ПРЕОБРАЗОВАНИЕМ И ЭНТРОПИЙНОГО КОДИРОВАНИЯ КОЭФФИЦИЕНТОВ ПРЕОБРАЗОВАНИЯ

 

Оценка эффективности  кодека выполняется по единой методике и включает получение:

1. зависимости ошибок восстановления от степени сжатия

2. помехоустойчивости к  шумам разного типа в канале передачи (AWGN / IMNOISE) как зависимостей СКО восстановления от ОСШ для этого типа шума

3. быстродействия (числа  операций на пиксель изображения  при кодировании/декодировании и  времени выполнения на типовом РС)

4. объема кода кодека  в терминах числа строк / бит  в формате ASCII

3.1 Средний квадрат ошибки

Зависимость ошибок восстановления от степени сжатия оценивается с  помощью среднего квадрата ошибок на пиксель изображения. Средний квадрат  ошибок показывает отклонение яркости  пикселей исходного изображения  в восстановленном.

Зависимость ошибок восстановления от степени сжатия представлена на рисунке 3.1 для кодека с кодированием с преобразованием Уолша-Адамара без энтропийного кодирования.

Рисунок 3.1 - Зависимость  ошибок восстановления от степени сжатия

Восстановленное изображение  при степени сжатия dCR =.25

Рисунок 3.2 – восстановленное изображение при степени сжатия dCR =.25

Восстановленное изображение  при степени сжатия dCR =1

Рисунок 3.3 – восстановленное  изображение при степени сжатия dCR =1

Восстановленное изображение  при степени сжатия dCR =5

Рисунок 3.4 – восстановленное  изображение при степени сжатия dCR =5

Восстановленное изображение  при степени сжатия dCR =10

Рисунок 3.5 – восстановленное  изображение при степени сжатия dCR =10

Зависимость ошибок восстановления от степени сжатия представлена на рисунке 3.6.

Рисунок 3.6 - Зависимость  ошибок восстановления при dCR =10

 

3.2 Помехоустойчивость

Воздействие шума на исходное и декодированное изображение изображение представленно на риунке 3.7.

f = imnoise(f0,'gaussian',0,varnoise(nn));

Рисунок 3.7 – воздействие  шума при кодировании изображения

Зависимость ошибок восстановления при воздействии шума представлена на рисунке 3.8.

Рисунок 3.8 - зависимость  ошибок восстановления при воздействии  шума

3.3 Быстродействие

Быстродействие на ноутбуке ASUS K50C с параметрами CPU 1.2 GHz, RAM 2 GB составило 39.156 секунд. Быстродействие рассчитывалось при помощи функции tic tac в MATLAB.

Elapsed time is 39.156000 seconds.

3.4 Объём кода  кодека

Длина кода кодека в строках  составила 163 строки. 

Выводы

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

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

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

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

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

Важнейшим параметром работы кодека изображений является его  быстродействие. Было рассчитано время, затрачиваемое кодеком на выполнение операций.

Также была оценена длина  кода кодека в количестве строк.

 

СПИСОК ИСТОЧНИКОВ ИНФОРМАЦИИ

 

1. Методы компьютерной обработки изображений/ под ред. В.А. Сойфера – М.: Физматлит, 2003. – 784 с.
2. Сэломон Д. Сжатие данных, изображений и звука. М.: Техносфера, 2004. – 368 с.
3. Ричардсон Я. Видеокодирование. H.264 и MPEG-4 – стандарты нового поколения. М.: Техносфера, 2005. – 368 с.
4. Гонсалес Р., Вудс Р. Цифровая обработка изображений. М.: Техносфера, 2005. – 1072 с.
5. Гонсалес Р., Вудс Р., Эддинс С. Цифровая обработка изображений в среде MATLAB. М.: Техносфера, 2006. – 616 с.
6. Статкус А.В. Кодирование изображений с преобразованием на основе моментов Рака/ Системи обробки інформації. Зб. наук. Праць. Вип. 5(95) – Х.: ХУПС, 2011, С.113 - 117.