Опрос

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

Новички

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

Алгоритм Хаффмана

Алгоритм Хаффмана с фиксированной таблицей CCITT Group 3

Классический алгоритм Хаффмана был рассмотрен в разд. 1 данной кни­ги. Он практически не применяется к изображениям в чистом виде, а ис­пользуется как один из этапов компрессии в более сложных схемах.

Близкая модификация алгоритма используется при сжатии черно-белых изображений (1 бит на пиксел). Полное название данного алгоритма CCITT Group 3. Это означает, что данный алгоритм был предложен третьей груп­пой по стандартизации Международного консультационного комитета по телеграфии и телефонии (Consultative Committee International Telegraph and Telephone). Последовательности подряд идущ«*: Черных и белых точек в нем заменяются числом, равным их количеству. А этот ряд уже, в свою оче­редь, сжимается по Хаффману с фиксированной таблицей.

Определение. Набор идущих подряд точек изображения одного цвета называется серией. Длина этого набора точек называется длиной серии.

В таблицах, приведенных ниже (табл. 1.1 и 1.2), заданы два вида кодов:

коды завершения серий - заданы с 0 до 63 с шагом 1;

составные (дополнительные) коды - заданы с 64 до 2560 с шагом 64.

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

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

Алгоритм компрессии выглядит так:

for (по всем строкам изображения) {

Преобразуем строку в набор длин серий; for(по всем сериям) { if(серия белая) { L= длина серии;

while(L > 2623) { // 2623=2560+63 L=L-2560;

ЗаписатьБелыйКодДля(2560); }

if(L > 63) {

Ь2=МаксимальныйСостКодМеньшеЪ(L) ; L=L-L2;

ЗаписатьБелыйКодДля(L2); } ЗаписатьБелыйКодДля(L) ;

//Это всегда код завершения }

else {

[Код, аналогичный белой серии,

с той разницей, что записываются черные коды] ) }

// Окончание строки изображения }

Поскольку черные и белые серии чередуются, то реально код для белой и код для черной серии будут работать попеременно.

В терминах регулярных выражений мы получим для каждой строки на­шего изображения (достаточно длинной, начинающейся с белой точки) вы­ходной битовый поток вида:

((<Б-2560>)*[<Б-сст.>]<Б-зв>(<Ч-2560>)*[<Ч-сст>]<Ч-зв.>)+

[(<Б-2560>)*[<Б-сст>]<Б-зв>]

где ()* - повтор 0 или более раз; ()*•- повтор 1 или более раз; [] - включение 1 или 0 раз.

Для приведенного ранее примера: 0, 3, 556, 10... алгоритм сформирует следующий код: <Б-0хЧ-ЗхБ-512хБ-44хЧ-10>, или, согласно таблице, 001101011001100101001011 №0000100 (разные коды в потоке выделены для удобства). Этот код обладает свойством префиксных кодов и легко может быть свернут обратно в последовательность длин серий. Легко подсчитать, что для приведенной строки в 569 бит мы получили код длиной в 33 бита, т. е. степень сжатия составляет примерно 17 раз.

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

Заметим, что единственное "сложное" выражение в нашем алгоритме: Ь2=МаксимальныйДопКодМеньшеЦЬ) - на практике работает очень про­сто: L2=(L»6)*64, где » - побитовый сдвиг L влево на 6 бит (можно сде­лать то же самое за одну побитовую операцию & - логическое И).

сЭч Упражнение. Дана строка изображения, записанная в виде длин серий - 442, 2, 56, 3, 23, 3,104,1, 94.1, 231, размером 120 байт ((442+2+..+231)/8). Подсчи­тать степень сжатия этой отроки алгоритмом CCITT Group 3.

Табл. 1.1 и 1.2 построены с помощью классического алгоритма Хаффма-на (отдельно для длин черных и белых серий). Значения вероятностей появ­ления для конкретных длин серий были получены путем анализа большого количества факсимильных изображений.

Таблица 1.1. Коды завершения

Длина серии

Код белой подстроки

Код черной подстроки

Длина серии

Код белой подстроки

Код черной подстроки

0

00110101

0000110111

32

00011011

000001101010

1

00111

010

33

00010010

000001101011

2

0111

11

34

00010011

000011010010

3

1000

10

35

00010100

000011010011

4

1011

011

36

00010101

000011010100

5

1100

ООП

37

00010110

000011010101

6

1110

0010

38

00010111

000011010110

7

1111

00011

39

00101000

000011010111

8

10011

000101

40

00101001

000001101100

9

10100

000100

41

00101010

000001101101

10

00111

0000100

42

00101011

000011011010

11

01000

0000101

43

00101100

000011011011

12

001000

0000111

44

00101101

000001010100

13

000011

00000100

45

00000100

000001010101

14

110100

00000111

46

00000101

000001010110

15

110101

000011000

47

00001010

000001010111

16

101010

0000010111

48

00001011

000001100100

17

101011

0000011000

49

01010010

000001100101

18

0100111

0000001000

50

01010011

000001010010

19

0001100

00001100111

51

01010100

000001010011

20

0001000

00001101000

52

01010101

000000100100

21

0010111

00001101100

53

00100100

000000110111

22

0000011

00000110111

54

00100101

000000111000

23

0000100

00000101000

55

01011000

000000100111

24

0101000

00000010111

56

01011001

000000101000

25

0101011

00000011000

57

01011010

000001011000

26

0010011

000011001010

58

01011011

000001011001

27

0100100

000011001011

59

01001010

000000101011

28

0011000

000011001100

60

01001011

000000101100

29

00000010

000011001101

61

00110010

000001011010

30

00000011

000001101000

62

00110011

000001100110

31

00011010

000001101001

63

00110100

000001100111

Таблица 1.2. Составные коды

Длина серии

Код белой подстроки

Код черной подстроки

Длина серии

Код белой подстроки

Код черной подстроки

64

11011

0000001111

1344

011011010

0000001010011

128

10010

000011001000

1408

011011011

0000001010100

192

01011

000011001001

1472

010011000

0000001010101

256

0110111

000001011011

1536

010011001

0000001011010

320

00110110

000000110011

1600

010011010

0000001011011

384

00110111

000000110100

1664

011000

0000001100100

448

01100100

000000110101

1728

010011011

0000001100101

512

01100101

0000001101100

1792

00000001000

совп. с белой

576

01101000

0000001101101

1856

00000001100

-II-

640

01100111

0000001001010

1920

00000001101

-II-

704

011001100

0000001001011

1984

000000010010

-II-

768

011001101

0000001001100

2048

000000010011

-II-

832

011010010

0000001001101

2112

000000010100

-II-

896

011010011

0000001II00I0

2176

000000010101

-II-

960

011010100

0000001110011

2240

000000010110

-II-

1024

011010101

0000001110100

2304

000000010111

-II-

1088

011010110

0000001110101

2368

000000011100

-II-

1152

011010111

0000001110110

2432

000000011101

-II-

1216

011011000

0000001110111

2496

000000011110

-II-

1280

011011001

0000001010010

2560

000000011111

-II-

Если в одном столбце встретятся два числа с одинаковым префиксом, то это опечатка.

Этот алгоритм реализован в формате TIFF.

Характеристики алгоритма CCITT Group 3

Степени сжатия: лучшая стремится в пределе к 213.(3), средняя 2, в худшем случае увеличивает файл в 5 раз.

Класс изображений: двуцветные черно-белые изображения, в кото­рых преобладают большие пространства, заполненные белым цветом (рис. 1.1 и 1.2).

Симметричность: близка к единице.

Характерные особенности: данный алгоритм чрезвычайно прост в реализации, быстр и может быть легко реализован аппаратно.