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

        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.