Алгоритмы сжатия изображений


Алгоритм Хаффмана - часть 3


/p>


 

Изображение, для которого очень выгодно применение алгоритма CCITT-3. (Большие области заполнены одним цветом).

Изображение, для которого менее выгодно применение алгоритма CCITT-3. (Меньше областей, заполненных одним цветом. Много коротких “черных” и “белых” серий).

 

Заметим, что единственное “сложное” выражение в нашем алгоритме: L2=МаксимальныйДопКодМеньшеL(L)

— на практике работает очень просто: 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.

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

Таблица кодов завершения:


 

Длина 


серии

Код белой 


подстроки

Код черной 


подстроки

  Длина 


серии

Код белой 


подстроки

Код черной 


подстроки

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 0011   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
<


- Начало -  - Назад -  - Вперед -