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

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

Метод двумерного кодирования также называется MMR (modified modified READ, то есть, дважды модифицированный READ, a READ расшифровывается как relative element address designate - обозначение относительного адреса элемента).

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

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

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

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

1. Проходная мода. Это случай, когда  находится слева от , а  - слева от  (рис. 1.21а). Эта мода не включает случай, когда  находится над . Когда эта мода установлена, то блок  кодируется с помощью кодов табл. 1.22 и передается. Указатель  устанавливается под , а четыре величины , ,  и  обновляются.

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

Табл. 1.22. Двумерные коды для метода Group 4.

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

В начале сканирования указатель  устанавливается на воображаемый белый пел слева от кодируемой строки, а указатель  указывает на первый черный пел. (Поскольку  указывает на воображаемый пел, то длина первой белой серии равна .) Указатель  устанавливается на следующий первый белый пел. Указатели  и  указывают на начало первой и второй серии справочной строки, соответственно.

Рис. 1.23. Пример двумерного кодирования.

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

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

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

Статистика здравого смысла говорит, что каждый
 американец из четырех - сумасшедший. Подумайте о троих
ваших лучших друзьях: если они ОК, то это вы.
- Рита Мае Браун