Адресно-позиционное кодирование (АПК)

2. Адресно-позиционное кодирование (АПК)

При кодировании штриховых изображений возможны новые значения двух типов: переход из белого в черное и переход из черного в белое. Координата элемента с новым значением яркости (КНЗ) отсчитывается относительно начала строки изображения (рис. 2).

Рис. 2 Кодирование двухградационного факсимильного сигнала по методу АПК

Для безошибочного восстановления изображения по сжатым данным необходимо в начале кодограммы строки указать признак (код) ее начала и значение яркости первого элемента строки:

/код начала строки/ /код первого элемента/ /КНЗ/ /КНЗ/ ………. /КНЗ/.

При равномерном кодировании длина кода будет определяться из условия, что элемент с новым значением яркости находится в конце строки. Таким образом, длина двоичного кода k=log₂N, где N – число элементов изображения на строке. Коэффициент сжатия k_сж при равномерном кодировании новых значений можно вычислить, зная вероятность Р_зн появления таких элементов:

k_сж=N/(m_н+m_я+NP_нзlog₂N),

где m_{н –} длина кода начала строки, m_я – длина кода яркости первого элемента.

При АПК нельзя достичь высоких коэффициентов сжатия, если насыщенность изображения деталями высока, поэтому его целесообразно применять при кодировании изображений, для которых вероятность новых значений не превышает 0,2–0,3.

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

 

3. Описание алгоритма программы сжатия и восстановления изображения по методу адресно-позиционного кодирования

Описание алгоритма программы сжатия

Программа написана на языке программирования Паскаль, начинается с раздела описания констант, переменных и процедур, используемых в программе.

Во втором блоке на экран выводится сообщение «введите 7 цифр значения яркости элементов строки».

В третьем блоке сброс переменой l в ноль и переменной f, содержащей информацию на передачу.

В четвертом блоке описывается цикл от 1 до 7 для обработки массива исходных данных.

В пятом блоке определяется координата нового значения, в процедуре to_binary переводится в двоичную форму и добавляется к f – переменную на передачу.

В шестом блоке к переменной f добавляется код начала строки – служебная комбинация из одиннадцати единиц.

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

Описание алгоритма подпрограммы to_binary

Процедура to_binary переводит значение переменной l в двоичную форму, которое добавляется к переменной на передачу данных – f.

В первом блоке схемы представлен заголовок процедуры.

Во втором блоке описываются локальные переменные типа Word для хранения промежуточных данных.

В третьем блоке происходят начальные установки для перевода переменной l в двоичную форму.

В четвертом блоке происходит сравнение переменной S и переменной K, соответствующей 2ⁿ, где n изменяется от 10 до 0. При условии, что S >= K выполняется шестой блок, где добавляется единица к переменной f и изменяется содержимое переменной S, в противном случае выполняется пятый блок, где осуществляется добавление нуля к переменой f на передачу данных. В седьмом блоке происходит деление на два переменной К, т.е. переход к следующей степени.

При выполнении условия i = 12 выполнение подпрограммы завершается.

Описание алгоритма восстановления изображения по Адресно-позиционному методу

Во втором блоке описывается цикл от 1 до 7 для вывода на экран массива значений, полученных после восстановления закодированных данных, переменная i является счетчиком массива b для хранения восстановленных значений.

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

В четвертом блоке описывается цикл от 1 до11 для перевода принятых значений из двоичной системы в десятичную. При этом, если значение строки ‘е’ =1, то n присваивается значение n+k, иначе – переход к седьмому блоку, в седьмом блоке происходит деление на два переменной k, т.е. переход к следующей степени.

В восьмом блоке добавляется 1 к переменной j, и если j=1, то возвращаемся к 4 блоку, если нет, то переходим к 9.

В девятом блоке b[i] присваивается значение переменной n, в 10 блоке текущее значение массива b[i] выводится на экран, переменной j присваивается значение на 1 большее. В 11 блоке происходит сравнение переменной i с числом 8, при выполнении условия происходит возврат ко второму блоку, иначе – конец.

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

4. Программа, реализующая сжатие и восстановление изображения по методу

 

Адресно-позиционного кодирования

Programm Coding-Decoding;

Uses Crt;

Var

f, e: string;

i, j, l, k, n: word;

b, a: array [1..7] of word;

Procedure to_binary;

Var k, i, s: word;

Begin

k:= 1024;

s:= l;

for i:= 1 to 11 do

Begin

if s>=k then Begin

f:= f + '1';

s:= s – k;

end;

else f:= f + '0';

k:= (k/2);

end;

End;

BEGIN

{–сжатие–}

Writeln (' Введите 7 цифр значения яркости элементов строки ');

Readln (a[1], a[2], a[3], a[4], a[5], a[6], a[7]);

f:= «; {начальное значение строки f}

l:= 0;

for i:= 1 to 7 do

Begin

l:= l + a[i];

to_binary;

end;

f:= '11111111111' +f;

Writeln ('Содержимое буфера', f);

{–восстанавление–}

e:=f;

For i:=1 to7 do Begin

b[i]:=0;

e:= Delete (e, 1,11);

k:= 1024;

n:= 0;

For j:= 1 to 11 do

Begin

if e[j] = '1' then n:= n + k;

k:= (k/2);

end;

b[i]:=n;

Writeln ('b = ', b[i]);

End;

END.

 

5. Пример сжатия двухградационного черно-белого изображения по методу АПК

В соответствии с заданием на курсовое проектирование приводится пример сжатия двух строк

	Цвет белый	Цвет черный	Цвет белый	Цвет черный	Цвет белый	Цвет черный	Цвет белый
Число пикселей	600	70	591	79	582	88	0
Число пикселей	0	72	598	81	589	90	580

При вводе данных чисел в программу получим код:

1 строка:

11111111111 01001011000 01010011110 10011101101 10100111100 11110000010 11111011010 11111011010

2 строка:

11111111111 00000000000 00001001000 01010011110 01011101111 10100111100 10110010110 11111011010

В данном примере последовательность 11111011010 следует в конце каждой линии.

Для оценки степени сжатия вычисляется коэффициент сжатия, вычисляемый по формуле

где, N – число элементов на тестовом изображении.

Nсж – число двоичных разрядов для представления сжатого изображения с учетом служебных комбинаций.

= (2010 + 2010)/(88 + 88) =23

Данный код обеспечивает сжатие данных в двадцать три раза. Достоинством Адресно – позиционного кодирования является его низкая чувствительность к ошибкам. Поражение ошибкой кода координаты нового значения приводит к искажению небольшой группы элементов строки до следующего нового значения яркости. Недостатком является небольшой коэффициент сжатия по сравнению с методом КДС.

Литература

 

1.   Зуев Е.А. Программирование на языке Turbo Paskal 6.0 7.0 – М.: Радио и связь, 1993

2.   Орловский Е.Л. Передача факсимильных изображений. – М.: Связь, 1980.

3.   Щелованов Л.Н. Системы факсимильной связи. Учебное пособие/ ЛЭИС. – Л., 1991.