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

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

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

Табл. 1.18. Время передачи факсов.

Табл. 1.19. Восемь эталонных документов.

Для того чтобы сгенерировать коды Group 3, было сосчитано распределение последовательностей черных и белых пелов в восьми эталонных документах, которые содержали типичные тексты с изображениями, которые обычно посылают по факсу. Потом использовался алгоритм Хаффмана для построения префиксных кодов переменной длины, которые кодировали серии черных и белых пелов. (Эти 8 текстов описаны в табл. 1.19, они здесь не опубликованы, так как на них распространяется авторское право ITU-T. Их можно скачать из [funet. 91].) Было обнаружено, что чаще всего встречаются серии из 2, 3 и 4 черных пелов, поэтому им были присвоены самые короткие коды (табл. 1.20). Потом шли серии из 2-7 белых пелов, которым были присвоены несколько более длинные коды. Большинство же остальных длин серий встречались реже, и им были назначены длинные, 12-битные коды. Таким образом, в стандарте Group 3 была использована комбинация кодирования RLE и метода Хаффмана.

Табл. 1.20 (а). Коды Group 3 и 4 для факсов.

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

Поскольку длина серии одинаковых пелов может быть большой, алгоритм Хаффмана был модифицирован. Сначала коды были приписаны остаткам - сериям длины от 1 до 63 пелов (они показаны в табл. 1.20а). Другие коды были даны сериям, длины которых кратны 64 (они приведены в табл. 1.20b). Таким образом, Group 3 это модифицированные коды Хаффмана (коды МН). Каждый код соответствует либо короткой остаточной серии длины до 64, либо длинной серии, кратной 64. Вот некоторые примеры:

Табл. 1.20 (b). Коды Group 3 и 4 для факсов.

1. Серия из 12 белых пелов кодируется как 001000.

2. Серия из 76 белых пелов () кодируется как 11011|001000 (без вертикальной черты).

3. Серия из 140 белых пелов () получает код 10010|001000.

4. Код 64 черных пелов () равен 00000011111|0000110111.

5. Код 2561 черных пелов () - 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.

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

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

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

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

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

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

98% всей статистики выдумана.
- Неизвестный