Первая страница / Теория / Сжатие данных /

Факсимильное сжатие

Голосование: 5, 1

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

ITU-T — это одно из подразделений Международного Союза Телекоммуникаций (International Telecommunications Union, ITU), которое располагается в Женеве (Швейцария) [2]. Эта организация издает рекомендации по стандартам, работающим в модемах. Несмотря на то, что у этой авторитетной организации нет никаких властных полномочий, ее рекомендации обычно принимаются и используются производителями по всему миру. До марта 1993 года, ITU-T была известна как Консультативный Комитет по Международной Телефонии и Телеграфии (Comité Consultatif International Télégraphique et Téléphonique), поэтому до сих пор можно встретить использование сокращения CCITT.

Первые разработанные в ITU-T стандарты называются Т2 (известный также как Group 1) и ТЗ (Group 2). Теперь они устарели и заменены алгоритмами Т4 (Group 3) и Т6 (Group 4). В настоящее время Group 3 используется в факс-машинах, разработанных для сетей PSTN (Public Switched Telephone Network). Эти аппараты работают на скорости 9600 бод. Алгоритм Group 4 разработан для эксплуатации в цифровых сетях, таких как ISDN. Они обычно работают на скорости 64К бод. Оба метода обеспечивают фактор сжатия 10:1 и выше, сокращая время передачи страницы типичного документа до минуты в первом случае, и до нескольких секунд во втором. Данные алгоритмы предполагают обработку ошибок на более низком уровне. Рекомендации T4 и T6 позволяет пересылать не только чёрно-белые изображения, но с оттенками серого и цветные.

CCITT T.4 и T.6 спецификации описывают различные требования к аппаратуре, включая разрешение сканирования и печати, допуск на размеры, временные ограничения… Процесс кодирования и декодирования может быть реализован как программно, так и на аппаратном уровне.

Group 3 и Group 4 кодируют документ по строчкам,  одну за другой, переводя каждую строку в последовательность черных и белых точек, называемых пелами (от pel, Picture ELement). Горизонтальное разрешение всегда составляет 8.05 пелов на миллиметр (примерно 205 пелов на дюйм). Таким образом, строка стандартной длины 8.5 дюймов конвертируется в 1728 пелов. Стандарт Т4, однако, предписывает сканирование строки длиной около 8.2 дюймов, что производит 1664 пела. (Все величины приводятся с точностью ±1%.)

Вертикальное разрешение составляет 3.85 линий на миллиметр (стандартная мода) или 7.7 линий на миллиметр (тонкая мода). Во многих факс-машинах имеется также сверх тонкая мода, при которой сканируется 15.4 линий на миллиметр. В табл. 1. приведен пример для страницы высотой в 10 дюймов (254 мм), и показано общее число пелов на страницу и типичное время передачи для всех трех мод без компрессии. Время очень большое, что показывает, насколько важно сжатие при пересылке факсов.

Табл. 1. Время передачи факсов.
Число линий Число пелов в линии Число пелов на странице Время (сек) Время (мин)
978 1664 1.670М 170 2.82
1956 1664 3.255М 339 5.65
3912 1664 6.510М 678 11.3

Различие между двумя стандартами заключается в том, что в Group 3 строчки кодируются независимо друг от друга, в то время как в Group 4, каждая строка кодируется в зависимости от предыдущей. Интересно отметить, что при любом способе кодирования, степень сжатия, приблизительно, линейно зависит от разрешения, с которым сканировалось изображение. Это происходит из-за того, что размер сжатого документа, есть функция от числа сканируемых линий.

Степень сжатия, достигаемая при использовании Group 3, конечно зависит от вида сканируемого документа. В некоторых случаях, длина закодированного изображения может оказаться больше исходного. Но, как правило, при обычном печатном тексте, степень сжатия достигает 10:1.

Степень сжатия при использовании Group 4 в некоторых случаях лучше, чем Group 3, достигая 25:1. Поэтому большинство аппаратов сейчас используют Group 4, благодаря улучшению оборудования и программного обеспечения, способного обеспечить быстрый процесс компрессии и декомпрессии.

Одномерное кодирование

В одномерном кодировании используется модифицированный код Хаффмана, суть которого заключается в использовании комбинации кодирования RLE и метода Хаффмана (см. статью [4] и визуализатор [5]). Для этого было сосчитано распределение последовательностей черных и белых пелов в восьми эталонных документах, которые содержали типичные тексты с изображениями, которые обычно посылают по факсу. Потом использовался алгоритм Хаффмана для построения префиксных кодов переменной длины, которые кодировали серии черных и белых пелов. (Эти 8 текстов описаны в табл. 2. Они доступны по ссылке [3].)

Табл. 2. Восемь эталонных документов.
Изображение: Описание:
1 Типичное деловое письмо на английском
2 Рисунок электрической цепи (от руки)
3 Печатная форма, заполненная на машинке на французском
4 Плотно напечатанный отчет на французском
5 Техническая статья с иллюстрациями на французском
6 График с напечатанными подписями на французском
7 Плотный документ
8 Рукописная записка белым по черному на английском

Было обнаружено, что чаще всего встречаются серии из 2, 3 и 4 черных пелов, поэтому, им были присвоены самые короткие коды (табл. 3). Потом шли серии из 2-7 белых пелов, которым были присвоены несколько более длинные коды. Большинство же остальных длин серии встречались реже, и им были назначены длинные, 12-битные коды.

Табл. 3. Коды Group 3 и 4 для факсов.
Длина серии Белые код Чёрные коды Длина серии Белые коды Чёрные коды
0 00110101 0000110111 32 00011011 000001101010
1 000111 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

Интересно отметить, что строке из 1664 белых пелов был присвоен короткий код 011000. Дело в том, что при сканировании часто попадаются пустые строки, которым соответствует это число пелов.

Поскольку длина серии одинаковых пелов может быть большой, алгоритм Хаффмана был модифицирован. Сначала коды были приписаны остаткам — сериям длины от 1 до 63 пелов (они показаны в табл. 3). Другие коды были даны сериям, длины которых кратны 64 (они приведены в табл. 4).

Табл. 4. Коды Group 3 и 4 для факсов.
Длина серии Белые коды Чёрные коды Длина серии Белые коды Чёрные коды
64 11011 0000001111 1344 011011010 0000001010011
128 10010 000011001000 1408 011011011 0000001010100
192 010111 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
640 01100111 0000001001010 1920 00000001101
704 011001100 0000001001011 1984 000000010010
768 011001101 0000001001100 2048 000000010011
832 011010010 0000001001101 2112 000000010100
896 011010011 0000001110010 2176 000000010101
960 011010100 0000001110011 2240 000000010110
1024 011010101 0000001110100 2304 000000010111
1088 011010110 0000001110101 2368 000000011100
1152 011010111 0000001110110 2432 000000011101
1216 011011000 0000001110111 2496 000000011110
1280 011011001 0000001010010 2560 000000011111

Таким образом, Group 3 — это модифицированные коды Хаффмана (коды МН). Каждый код соответствует либо короткой остаточной серии длины до 64, либо длинной серии, кратной 64. Вот некоторые примеры:

  1. Серия из 12 белых пелов кодируется как 001000.
  2. Серия из 76 белых пелов (=64+12) кодируется как 11011|001000 (без вертикальной черты).
  3. Серия из 140 белых пелов (=128+12) получает код 10010|001000.
  4. Код 64 черных пелов (=64+0) равен 0000001111|0000110111.
  5. Код 2561 черных пелов (=2560+1) — 000000011111|010.

Дотошный читатель заметит, что разные коды были также присвоены пустым сериям белых и черных пелов. Эти коды необходимы для того, чтобы обозначить серии, длины которых равны 64, 128 или любому числу, кратному 64. Он также может заметить, что серии длины 2561 быть не может, так как в строке длины 8.5 дюймов помещается только 1728 пелов, поэтому коды для более длинных серии не нужны. Однако, могут быть (или появиться в будущем) факс-машины для широкой бумаги, поэтому коды Group 3 были созданы с учетом этой возможности.

Каждая строка пелов кодируется отдельно, заканчиваясь специальным 12-битным EOL-кодом 000000000001. К каждой строке также добавляется слева один белый пел. Это делается для того, чтобы избежать неопределенности в декодировании при получении конца.

Прочитав код EOL для предыдущей строки, приемник знает, что новая строка начнется с одного белого пела и игнорирует первого из них. Примеры:

  1. Строка из 14 пелов

                               

    Кодируется сериями lw 3b 2w 2b 7w EOL, и ей присваивается следующий двоичный код: 000111|10|0111|11|1111|000000000001. Декодер игнорирует одиночный белый пел в начале.

  2. Строке

                               

    ставится в соответствие серия 3w 5b 5w 2b EOL, и она получает следующий двоичный код: 1000|0011|1100|11|000000000001.

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

Коды Group 3 не могут исправлять ошибки, но они могут обнаружить многие из них. Дело в том, что по природе кодов Хаффмана, даже один плохо переданный бит вынудит приемник потерять синхронизацию и породить последовательность неправильных пелов. Поэтому последовательные строки следует кодировать независимо друг от друга. Если декодер обнаруживает ошибку, он пропускает биты, разыскивая EOL. При таком методе одиночная ошибка может испортить не более одной строки. Если декодер не может долгое время обнаружить EOL, он предполагает высокую зашумленность канала и прерывает процесс, сообщая об этом передатчику. Поскольку длины кодов лежат в диапазоне от 2 до 12, то приемник обнаруживает ошибку, если он не в состоянии выявить правильный код, прочитав 12 бит.

В начале каждой страницы передается код EOL, а в конце страницы ставится 6 кодов EOL. Поскольку все строки кодируются независимо, эта схема называется схемой одномерного кодирования. Коэффициент сжатия зависит от передаваемого изображения. Если оно состоит из крупных соприкасающихся белых и черных областей (текст, таблицы или графики), то он будет сильно сжат. А изображения, в которых присутствует много коротких серий могут вызвать отрицательное сжатие. Это может случиться при передаче полутоновых изображений, например, фотографий. Такие изображения при сканировании порождают множество коротких пелов длины 1 или 2.

Поскольку стандарт Т4 основан на длинных сериях, он может давать плохое сжатие, если все серии будут короткими. Экстремальный случай — это, когда все пелы имеют длину 1. Белый пел имеет код 000111, а черный — 010. Поэтому при кодировании двух последовательных разноцветных пелов требуется 9 бит, тогда как без кодирования можно обойтись двумя битами (01 или 10). Значит, коэффициент сжатия равен 9/2=4.5 (сжатый файл будет в 4.5 раза длиннее исходного).

Стандарт Т4 допускает добавление нулевых бит между кодом данных и кодом EOL. Это делается, если необходимо сделать паузу, например, в связи с тем, что число передаваемых битов кодирующих целую строку должно делиться на 8.

Пример. Двоичная строка 000111|10|0111|11|1111|000000000001 становится немного длиннее 000111|10|0111|11|1111|00|000000000001 после добавления 2 нулей, чтобы общая длина строки была 32 бит (=8x4). Декодер обнаружит это добавление перед одиннадцатью нулями кода EOL.

Двумерное кодирование

Двумерное кодирование было разработано, чтобы преодолеть недостатки одномерного кодирования при сжатии изображений, содержащих серые области. Этот метод является опционным дополнением к Group 3 и используется только при работе в цифровых сетях. Если факс-машина поддерживает двумерное кодирование, то за кодом EOL следует еще один бит, указывающий на метод кодирования следующей строки. Если он равен 1, то будет использоваться одномерное кодирование, а 0 указывает на двумерную схему.

Метод двумерного кодирования также называется MMR (modified modified READ, то есть, дважды модифицированный READ, a READ расшифровывается как relative element adress designate — обозначение относительного адреса элемента). Такое странное словосочетание объясняется тем, что этот алгоритм является модификацией одномерной схемы, которая, в свою очередь, получена модификацией оригинального метода Хаффмана. Метод работает, сравнивая текущую отсканированную строку, называемую кодируемой, со строкой, отсканированной на предыдущем проходе, которая называется справочной строкой. При этом будет сжиматься разность этих строк. Алгоритм исходит из логичного предположения, что две соседние строки обычно отличаются всего несколькими пелами. При этом предполагается, что документ начинается строкой белых пелов, которая служит начальной справочной строкой. После кодирования первая строка становится справочной, а вторая строка — кодируемой. Как и при одномерном кодировании предполагается, что строка начинается белым пелом, который игнорируется приемником.

Метод двумерного кодирования менее надежен, чем одномерный метод, поскольку ошибка в декодировании некоторой строки вызовет ошибки при декодировании последующих строк, и эта волна ошибок может распространиться до конца по всему документу. Вот почему стандарт Т4 (Group 3) включает требование, что после строки, закодированной одномерным методом, следует не более К−1 строк, закодированных двумерной схемой. Для стандартного разрешения К = 2, а для тонкого К = 4. Стандарт Т6 не содержит этого требования и использует только двумерное кодирование.

Рис. 1. Пять конфигураций мод.

(a)

Строки: b1 b2
справочная→
кодируемая→
a0               a1 a2  
            b1 b2              

Кодируется длина b1b2серии. Новая a0 становится старой b2.

(b1)

Строки: b1 b2
справочная→
кодируемая→
a0           a1         a2
a1 b2

(b2)

Строки: b1 b2
справочная→
кодируемая→
a0 a1 a2
a1 b1

Кодируется длина a1b1 серии. Новая a0 становится старой a1.

(c1)

Строки: b1 b2
справочная→
кодируемая→
a0 a1 a2
a0 a1 a1 a2

(c2)

Строки: b1 b2
справочная→
кодируемая→
a0 a1 a2
a0 a1 a1 a2

Кодируются длины a0a1 (белой) и a1a2 (черной) серий. Новая а0 становится старой а2.

Примечания

  1. a0 — первый пел нового кода; он может быть черным или белым.
  2. a1 — первый пел другого цвета справа от а0.
  3. a2 — первый пел другого цвета справа от а1.
  4. b1 — первый пел справочной строки другого цвета справа от а0.
  5. b2 — первый пел справочной строки другого цвета справа от b1.

Сканирование кодируемой строки и ее сравнение со справочной строкой делается в трех случаях или модах. Мода определяется при сравнении очередной серии пелов справочной строки [(b1b2) на рис. 1] с текущей серией (a0a1), а также со следующей серией (a1a2) кодируемой строки. Каждая из этих серий может быть белой или черной. Опишем эти три моды.

Проходная мода. Это случай, когда (b1b2) находится слева от (a1a2), а b2 — слева от а1 (рис. 1а). Эта мода не включает случай, когда b2 находится над а1. Когда эта мода установлена, то блок (b1b2) кодируется с помощью кодов табл. 5 и передается. Указатель aо устанавливается под b2, а четыре величины b1, b2, a1 и a2 обновляются.

Вертикальная мода. В этом случае (b1b2) частично перекрывается с (a1a2), но не более чем тремя пелами (рис. 1b1 и 1b2). Если предположить, что соседние строки отличаются не сильно, то это будет самый частый случай. При обнаружении этой моды генерируется один из семи кодов (табл. 5) и посыпается. Производительность двумерной схемы зависит от того, насколько часто имеет место эта мода.

Горизонтальная мода. Серия (b1b2) перекрывается с (а1а2) более чем по трем пелам (рис. 1с1 и 2). При обнаружении этой моды серии (а0а1) и (а1a2) кодируются с помощью табл.5 и передаются. Указатели обновляются как в случаях 1 и 2.

Табл. 5. Двумерные коды для метода Group 4.
Мода Кодируемая серия Содержание Код
Проходная b1b2 P 0001
Горизонтальная a0a1, a1a2 H 001+ код для длины a0a1 и a1a2
Вертикальная a1b1 = 0 V(0) 1
a1b1 = -1 VR(1) 011
a1b1 = -2 VR(2) 000011
a1b1 = -3 VR(3) 0000011
a1b1 = +1 VL(1) 010
a1b1 = +2 VL(2) 000010
a1b1 = +3 VL(3) 0000010
Расширенный     0000001000

В начале сканирования указатель a0 устанавливается на воображаемый белый пел слева от кодируемой строки, а указатель a1 указывает на первый черный пел. (Поскольку а0 указывает на воображаемый пел, то длина первой белой серии равна |a0a1| − 1.) Указатель a2 устанавливается на следующий первый белый пел. Указатели b1 и b2 указывают на начало первой и второй серии справочной строки, соответственно.

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

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

Пример. Рис. 2 изображает, какие моды и какие коды соответствуют двум соседним строкам пелов.

Рис. 2. Пример двумерного кодирования.
 
 
вертикальная мода горизонтальная мода проход вертикальная мода горизонтальная мода …
+1 0 3 белых 4 черных -2 +2 4 белых 7 черных
   
010 1 001 1000 011 0001 000011 000010 001 1011 00011

CCITT T.6

В 1984 году, CCITT разработал спецификацию, определяющую факсимильную схему кодирования, используемую в Group 4 для кодирования черно-белых изображений. Этот стандарт известен как CCITT Recommendation T.6, который спроектировали для безошибочной цифровой передачи по сети. Он предполагает, что ошибки передачи исправляются управляющими процедурами на более низком уровне. Поэтому порча хотя бы одного бита приводит к искажению всего изображения. В сравнении с CCITT T.4 схемы кодирования, эта схема особо восприимчива к ошибкам и менее устойчива.

CCITT T.6 схема кодирования известна как Modified Modified Relative element address designate code (MMR). В ней используется двумерное сжатие. Позицию каждого изменяющегося пела в текущей кодируемой строке кодируют с учетом предыдущей строки. Предыдущая строка для первой, является полностью белая фиктивная строка. Эта схема кодирования такая же, как и двумерное кодирование в Group 3, только первая строка кодируется по-другому, и в Group 3 двумерной схеме кодирования каждая k-ая строка (k = 2 или 4) документа кодировалась одномерной схемой.

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

Для документа формата A4 с разрешением 200dpi при CCITT T.6 схеме кодирования в типичном случае коэффициент сжатия примерно от 15:1 до 20:1. Для 400dpi (8 тестовых документов), сжатие достигает от 30:1 до 40:1.

Источники

  1. Сэломон Д. Сжатие данных, изображений и звука. — М.: Техносфера, 2004.
  2. Internationsl Telecommunications Union.
  3. Набор тестов, используемых для построения префиксных кодов переменной длины.

Материалы на сайте CAT

  1. Кочелаев Д., Вишняков С. Сжатие изображений без потерь (2005)
  2. Рябов А. Построение дерева Хаффмена (2000)
  3. Егоров К. Факсимильное сжатие (2006)

Автор: Егоров К.


Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий