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

Введение

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

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

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

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

 

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;