Тема лекции 15. Сжатие данных в ЦСС.




 

Факсимильная передача — это процесс передачи двухмерного образа как последо­вательности последовательных строчных разверток. В действительности наиболее рас­пространенными образами являются документы, содержащие текст и цифры. Поло­жение строчной развертки и положение вдоль развертки квантуются в пространствен­ные расположения, которые определяют двухмерную координатную сетку элементов картинки, называемых пикселями. Ширина стандартного документа МККТТ опреде­ляется равной 8,27 дюймов (20,7 см), а длина— 11,7 дюймов (29,2 см), почти 8,5 дюймов на 11,0 дюймов. Пространственное квантование для нормального разрешения составляет 1728 пикселей/строку и 1188 строк/документ. Стандарт также определяет квантование с высоким разрешением с теми же 1728 пикселями/строку, но с 2376 строками/документ. Общее число отдельных пикселей для факсимильной передачи с нормальным разрешением составляет 2 052 864, и оно удваивается для высокого раз­решения. Для сравнения, число пикселей в стандарте NTSC (National Television Standarts Committee — Национальный комитет по телевизионным стандартам) коммерче­ского телевидения составляет 480 х 460, или 307 200. Таким образом, факсимильное изображение имеет разрешение в 6,7 или 13,4 раза больше разрешения стандартного телевизионного образа.

Относительная яркость или затемненность развернутого образа в каждом положе­нии на строке развертки квантуется в два уровня: Ч (черный) и Б (белый). Таким образом, сигнал, наблюдаемый на протяжении линии развертки, — это двухуровневая
модель, представляющая элементы Ч и Б. Легко видеть, что горизонтальная развертка
данной страницы будет представлять последовательность, состоящую из длинных
групп уровней Ч и Б. Стандарт МККТТ схемы группового кодирования для сжатия
отрезков Ч и Б уровней базируется на модифицированном коде Хаффмана переменной длины, который приведен в табл. 13.1. Определяются два типа шаблонов, группы
Б и Ч. Каждый отрезок описывается кодовыми словами деления. Первое деление, названное созданное кодовое слово, определяет группы с длинами, кратными 64. Второе
деление, именуемое оконечное кодовое слово, определяет длину оставшейся группы.
Каждая серия из знаков Ч (или. Б), длиной от 0 до 63, обозначает единственное кодо­вое слово Хаффмана, как и каждая группа длины 64 х К, где К= 1, 2, …, 27. Также кодом определен уникальный символ конца строки (end of line — EOL), который указывает, что дальше не следуют черные пиксели. Следовательно, должна начаться сле­дующая строка, что подобно возврату каретки пишущей машинки [23].

 

Коды Лемпеля-Зива (ZIP)

 

Основной сложностью при использовании кода Хаффмана является то, что вероятно­сти символов должны быть известны или оценены и как кодер, так и декодер должны знать дерево кодирования. Если дерево строится из необычного для кодера алфавита, ка­нал, связывающий кодер и декодер, должен также отправлять кодирующее дерево как за­головок сжатого файла. Эти служебные издержки уменьшат эффективность сжатия, реали­зованную с помощью построения и применения дерева к алфавиту источника. Алгоритм Лемпеля-Зива (Lempel-Ziv) и его многочисленные разновидности используют текст сам по себе для итеративного построения синтаксически выделенной последовательности кодовых слов переменной длины, которые образуют кодовый словарь.

Код предполагает, что существующий словарь содержит уже закодированные сегменты последовательности символов алфавита. Данные кодируются с помощью просмотра существующего словаря для согласования со следующим коротким сегментом кодируемой последовательности. Если согласование найдено, код следует такой философии: поскольку получатель уже имеет этот сегмент кода в своей памяти, нет необходимости пересылать его, требуется только определить адрес, чтобы найти сегмент. Код ссылается на расположение последовательности сегмента и затем дополняет сле­дующий символ в последовательности, чтобы образовать новую позицию в словаре кода. Код начинается с пустого словаря, так что первые элементы являются позиция­ми, которые не ссылаются на более ранние. В одной форме словаря рекуррентно формируется выполняемая последовательность адресов и сегмент символов алфавита, содержащийся в ней. Закодированные данные состоят из пакета <адрес словаря, следующий знак данных>, а каждый новый входной элемент словаря образован как пакет, содержащий адрес того словаря, за которым следует следующий символ.

Рассмотрим пример такой технологии кодирования.

Закодируйте последовательность символов[а b а а b а b b b b b b b а b b b b а]

Закодированные <0,а>, <0,b>, <1,а>, <2,а>, <2,b>, <5,b>, <5,а>, <6,b>, <4,- >
пакеты:

Адрес: 1 2 3 4 5 6 7 8

Содержимое: а b аа bа bb bbb bbа bbbb

Начальный пакет <0,а> показывает нулевой адрес, потому что в словаре еще нет ни одной позиции. В этом пакете знак "а" является первым в последовательности дан­ных, и он приписан к адресу 1. Следующий пакет <0,b> содержит второй знак данных b, который еще не был в словаре (следовательно, адресное значение есть 0); b припи­сывается адресу 2. Пакет <1,а> представляет кодирование следующих двух знаков "аа" с помощью вызова адреса 1 для первого и присоединения к этому адресу следующего знака "а". Пара знаков "аа" приписывается адресу 3. Пакет <2,а> представляет коди­рование следующих двух знаков данных "bа" с помощью вызова адреса 2 для знака "b" и присоединения к этому адресу следующего знака "а". Пара знаков данных "bа" приписывается адресу 4 и т.д. Отметим, как завершается групповое кодирование. Восьмой пакет составлен из адреса 6, содержащего три знака "b", за которыми следует другой знак "b". В этом примере закодированные данные могут быть описаны с по­мощью трехбитового адреса с последующим битом 0 или 1 для определения присое­диненного знака. В закодированной последовательности существует последователь­ность из 9 символов для общего содержимого в 36 бит для кодирования данных, со­держащих 20 знаков. Как во многих схемах сжатия, эффективность кодирования не достигается для коротких последовательностей, как в этом примере, и имеется только для длинных последовательностей.

В другой форме алгоритма Лемпеля-Зива закодированные данные представлены как три словесных пакета вида <число знаков сзади, длина, следующий знак. Здесь концепция адреса не используется. Наоборот, имеются ссылки на предшествующие последовательности данных, а также допускаются рекуррентные ссылки на параметр длины. Это показано в следующем примере, представленном как позиция <1,7,а>.

Закодируйте последовательность символов [аbааbаbbbbbbbаbbbbbа]

Закодированные <0,0,а>, <0,0,b>, <2,1,а>, <3,2,b>, <1,7,а>, <6,5,а>

пакеты:.

Содержимое: а b аа bаb bbbbbbbа bbbbbа

Текущий текст: а аЬ аbаа а ааbаb аbааbаbbbbbbbbа вся

последовательность



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-15 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: