Читать в оригинале

<< ПредыдущаяОглавлениеСледующая >>


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 мм), и показано общее число пелов на страницу и типичное время передачи для всех трех мод без компрессии. Время очень большое, что показывает, насколько важно сжатие при пересылке факсов.

Число линий

Число пелов в линии

Число пелов на странице

Время (сек)

Время (мин)

978

1664

1.670M

170

2.82

1956

1664

3.255M

339

5.65

3912

1664

6.510M

678

11.3

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

Изображение

Описание

1

Типичное деловое письмо на английском

2

Рисунок электрической цепи (от руки)

3

Печатная форма, заполненная на машинке на французском

4

Плотно напечатанный отчет на французском

5

Техническая статья с иллюстрациями на французском

6

График с напечатанными подписями на французском

7

Плотный документ

8

Рукописная записка белым по черному на английском

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

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

Длина

серии

Белые

коды

Черные

коды

Длина

серии

Белые

коды

Черные

коды

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

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

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

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

Длина

серии

Белые

коды

Черные

коды

Длина

серии

Белые

коды

Черные

коды

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

148

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

 

Табл. 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. Декодер игнорирует одиночный белый пел в начале.

image1

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

image2

Заметим, что коды из табл. 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% всей статистики выдумана.
- Неизвестный



<< ПредыдущаяОглавлениеСледующая >>