10.5. ЭФФЕКТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ ФАКСИМИЛЬНЫХ СООБЩЕНИЙ

Существующие методы сокращения избыточности можно условно разбить на две группы.

Первая группа методов позволяет так закодировать сообщения, что в отсутствие ошибок в канале связи декодирование позволяет точно восстановить переданное сообщение Это — методы кодирования с сохранением информации, или неискажающие методы эффективного кодирования.

Вторая группа методов отличается тем, что в процессе эффективного кодирования сообщения в него вносятся определенные неустранимые искажения, которые считаются допустимыми Даже в отсутствие ошибок канала связи декодированное сообщение отличается от истинного передаваемого сообщения. Эти методы «без сохранения информации» называют искажающими методами кодирования.

Большинство неискажающих методов кодирования основаны на представлении источника сообщений (изображений) как статистического источника. Поэтому данные методы иногда называют методами статистического кодирования. Основой для их построения служат положения теории информации и теории эффективного кодирования. На этой базе были разработаны эффективные методы кодирования двухградационных изображений и построена соответствующая цифровая факсимильная аппаратура общего назначения для передачи в основном документальной информации. Методы обладают высокой эффективностью при отсутствии ошибок в канале связи. Для повышения помехоустойчивости в данном случае используют традиционные методы защиты от ошибок, принятые в системах ПД.

Следует отметить, что при использовании методов неискажающего кодирования задачи сокращения избыточности и повышения помехоустойчивости, как правило, решаются независимо друг от друга: сначала устраняется собственная избыточность источника, что приводит к сжатию объема сообщения, а потом для повышения помехоустойчивости, учитывая возможные ошибки канала связи, вносится искусственная избыточность в передаваемый сигнал для борьбы с ошибками.

Практически, подобные методы кодирования работоспособны в каналах с низкой вероятностью ошибки (10-5 и ниже).

Искажающие методы кодирования развиты значительно меньше. В огличие от регулярных статистических методов кодирования они носят в основном эвристический характер, при их построении используется нестатистическое описание источника изображений и учитываются свойства зрительного восприятия. Особенностью этих методов является также то, что они не универсальны и строятся для каждого класса изображений отдельно. Искажающие методы кодирования значительно меньше чувствительны к ошибкам и могут использоваться в каналах с вероятностью ошибки

Статистические методы кодирования.

Основой для использования этих методов является представление источников факсимильных сообщений в виде серий — черных и белых отрезков строк развертки. Рассмотрим идею метода нестатистического кодирования длин серий КДС. Допустим, что длины серий черного лежат в пределах от 0 до 8, а длнны серий белого в пределах от 0 до 30. Пусть эти серии чередуются. Каждую длину серии можно представить в виде двоичного числа. Например, серия черного длиной в 7 элементов будет представлена как 111 (число 7 в двоичной системе счисления), а серия белого из 25 элементов будет представлена в виде соответствующей двоичной кодовой комбинации 1101 (число 25). В канал будут передаваться не сами серии, а их двоичные номера.

Например, серия белого из 25 элементов и серия черного из 7 элементов будет передана как набор из кодовых комбинаций:

Легко определить, во сколько раз в данном случае сокращается объем передаваемой информации:

Декодирование сигнала происходит однозначно, если условиться, что первой кодовой комбинацией всегда будет кодовая комбинация белого отрезка, и белые, и черные отрезки всегда чередуются. Такие коды практически применяются при передаче факсимильных изображений метеокарт. Средние длины серий белого и серий черного определяются, исходя из статистики длин серий для данного вида изображений. Так, серии черного кодируются трехбитовыми кодовыми словами, и все серии белого — шестибитовыми кодовыми словами. Если на изображении встречаются длины серий, отличающиеся от «стандартных», они кодируются специальным образом, с тем, чтобы можно было однозначно декодировать сигнал. Подробно с этим кодом и его разновидностями можно познакомиться в [10.3].

Более эффективным способом кодирования длин серий является использование кода Хафмена (см. разд. 5). Напомним, что сущностью кода Хафмена является реализация основной идеи эффективного кодирования: длина кодовой комбинации сообщения обратно пропорциональна вероятности его появления. Выше было показано, что распределение длин серий носит неравномерный характер, поэтому применение кода Хафмена должно обеспечить максимальное сжатие исходного объема источника, поскольку принцип кодирования предписывает более короткие кодовые слова часто встречающимся длинам серий.

Этот код с некоторыми модификациями был предложен в качестве международного стандарта для построения факсимильной аппаратуры III группы общего назначения (см. разд. 10.8), работающей в канале ТЧ. Код получил название модифицированного кода Хафмена (МКХ) [10.2]. Главная цель стандарта заключалась в обеспечении передачи типичных документов формата цифровым способом по телефонному каналу в среднем за 1 мин.

В цифровой форме при нормированных значениях разрешающей способности 7,7 лин./мм и 3,85 стр./мм документ содержит 1188 строк по 1728 элементов в каждой строке. Непосредственная передача такого объема информации в канале ТЧ заняла бы 12 мин. Однако код Хафмена позволяет существенно сократить это время передачи.

Используя статистику длин (отрезков) белого и черного, можно построить два кода Хафмена: для серий белого и для серий черного. Очевидно, что в каждом коде число кодовых слов равно 1728.

Такой объем существенно усложняет реализацию кода Хафмена, поэтому этот код был модифицирован. Модификация заключается в том, что все кодовые слова в серии разбиваются на две группы: кодовые слова для основных серий длиной где N — целое число, и дополнительные слова (концевые) для серий длиной элементов. Очевидно, что каждую серию можно представить этими группами, что позволяет уменьшить общее число кодовых слов и упростить реализацию.

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

Рассмотренный код МКХ является одномерным кодом. Естественно, что большей эффективности можно достичь, применяя кодирование нескольких строк развертки. Одним из вариантов двумерного кода является код READ, который рекомендован для использования в факсимильной аппаратуре III группы [10.2]. В этом коде используется сочетание одной из разновидностей КДС и кода МКХ. Кодирование следующей строки данным кодом осуществляется с учетом предшествующей или последующей строк. В среднем этот код позволяет увеличить эффективность сжатия на

Существуют двумерные коды, использующие для сжатия информацию в нескольких строках развертки. Так, в целях сокращения объема информации при передаче изображений газетных полос, передаваемых с высокой разрешающей способностью (0 ... 60 лин./мм), применяется кодирование с предсказанием. Предсказание следующего элемента происходит по 12 окрестным элементам. Ошибка предсказания кодируется кодом Хафмена. Такой способ кодирования позволяет получить высокий коэффициент сжатия (до В Советском Союзе принят в качестве ГОСТ на цифровую аппаратуру III группы двумерный код, который называется планарным [10.4]. Данный код используется в цифровой аппаратуре передачи метеокарт. При этом кодировании сжатию подвергаются фрагменты изображения размером 8X8 элементов, на которые разбивается все передаваемое изображение. Идея кодирования состоит в следующем.

Рассмотрим фрагмент изображения 8X8 и разобьем его на четыре равные части (рис. 10.9). В данном примере квадраты I, II, III содержат черные элементы, а квадрат IV не содержит черных элементов. Квадраты 4X4, содержащие черные элементы, обозначим 1, а не содержащие черных элементов, через 0.

Запишем условные обозначения квадратов 4X4 в порядке их нумерации: 1110.

Рис. 10.9. Принцип планарного кодирования

Рис. 10 10. Разбиение растрового изображения на субрастры:

1 - растровые точки; 2 — субрастры

Если бы фрагмент 8X8 был бы весь белым (черным), то были бы записаны либо 0, либо 1.

Каждый квадрат 4X4, имеющий в своем составе черные элементы, снова разобьем на четыре части, образуя квадраты размером элементов. Если в этих квадратах имеются черные элементы, то обозначим соответственно их через 1. Для нашего примера имеем:

Те квадраты, которые содержат черные элементы, опять разобьем на группы из четырех квадратов, но уже размером 1X1 элемент и проделаем ту же операцию. В результате получим иерархию уровней описания, на самом младшем уровне кодирования фактически не происходит. Кодовое описание фрагмента будет выглядеть следующим образом:

В данном примере массив из 64 бит сжимается в 2 раза. Очевидно, что подобный способ кодирования будет тем эффективнее, чем реже встречаются черные элементы изображения. Поскольку синоптические карты в основном состоят из редких тонких линий, то такое кодирование обеспечивает сжатие в 5 раз.

Методы эффективного статистического кодирования обладают следующими особенностями.

1. Неравномерность длин кодовых комбинаций. Однако в канал кодовые комбинации должны поступать равномерно.

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

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

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

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

Учитывая вышесказанное, можно поставить задачу построения эффективного кода с заданным критерием верности воспроизведения копии. Подобные методы кодирования относятся к кодированию с искажениями. Искажения вносятся в изображение в процессе его кодирования и не могут быть устранены в процессе декодирования. Достоинством такого подхода являются возможность построения равномерных кодов и обеспечение высокой помехоустойчивости за счет свойств самого кода.

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

Поскольку алгоритм является равномерным, то любое искажение одного кодового слова не может привести к нарушению декодирования других кодовых слов, и помехоустойчивость будет выше, чем при использовании «неискажающих» алгоритмов.

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

В качестве примера рассмотрим задачу сжатия изображений иллюстраций газетных полос. Как известно, полутоновые иллюстрации в газете выполняются растровым способом: воспроизведение полутонов происходит за счет изменения площади регулярно расположенных растровых точек. Расстояние между точками не изменяется. Белое поле растрового изображения состоит из самых маленьких точек (в аппаратуре «Газета-3» их размер 30 мкм). Эти точки совершенно незаметны, если рассматривать изображение на нормальном для чюния расстоянии (около 30 см). Поскольку глаз не в состоянии различить отдельные точки, то все точечное изображение воспринимается как белое. При большем диаметре точек структура будет восприниматься как серое поле и при максимальном диаметре точек — как черное. Таким образом, информацию о полутоне несет только площадь растровой точки, причем показано [10.5], что ее форма не влияет на качество восприятия изображения.

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

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

Эффективность такого способа передачи растрового изображения можно оцепить следующим образом.

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

Растровое изображение можно составить из площадок — субрастров, каждый из которых содержит одну растровую точку. Варианты форм субрастров показаны на рис. 10.10. Дискретизация факсимильного сигнала приводит к квантованию площади растровой точки. Зная линиатуру растра и разрешающую способность анализируемого устройства, можно определить число уровней квантования.

где — площадь субрастра, равная — площадь элемента изображения, равная ; — разрешающая способность

Очевидно, что число уровней квантования полутонового изображения характеризуется числом площадок элементов изображения, составляющих один субрастр. Для (параметры аппаратуры «Газета-3») имеем Известно, что для качественного воспроизведения полутонового изображения вполне достаточно иметь уровня яркости. Для передачи такого числа уровней двоичным кодом необходимо иметь длину кодовой комбинации . В рассматриваемом примере . Таким образом, вместо поэлементной передачи бит необходимо передать только 7 бит, что обеспечивает сжатие объема передаваемой информации более чем в 11 раз.

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

Рассмотренный способ эффективного кодирования растрового изображения с некоторыми модификациями используется в разрабатываемой аппаратуре передачи газет «Газета-3».