Характеристика стандарта GIF

Проблема сжатия рисунков приобрела особую важность по мере развития сначала локальных, а затем и глобальных сетей ЭВМ. В июне 1987 года компания CompuServe Incorporated опубликовала описание стандарта GIF (Graphics interchange Format — формат графического обмена). Для сжатия рисунков в нем применяется модифицированный алгоритм LZW (Lempei-ziv-weich), используемый в распространенных архиваторах текстовых данных. На сегодняшний день это наилучший способ сжатия растровых рисунков, подготовленных с использованием палитры цветов.
Алгоритмы LZW и RLE различаются принципиально. Главный недостаток RLE заключается в самой идее подсчитывать число подряд расположенных совпадающих кодов. Способ LZW избавлен от этого недостатка. При сжатии запоминаются и используются все последовательности встречающихся в рисунке точек, независимо от совпадения или различия их цветов. В выходной файл записываются не байты, а цепочки битов переменной длины, коды которых соответствуют кодам отдельных точек или их комбинаций.

Предположим, что размер кодов точек рисунка равен к, а их значения изменяются от 0 до N-I, где N = 2):. Например, если в рисунке используются все 256 цветов, то к= 8, а N = 256. Первоначально для хранения цепочек отводится к+1 разряд. Если код цепочки меньше N, то это просто код одной точки. Коды N и N+I имеют специачьное назначение. Комбинации точек кодируются, начиная от значения ы+2. Какой комбинации соответствует тот или иной код цепочки (если он больше чем N+I) можно узнать только из таблицы цепочек.

Первоначально таблица цепочек пуста, в процессе сжатия в нее записываются все новые (отсутствующие в таблице) комбинации точек. Если таблица окажется полностью заполненной, то размер цепочек увеличивается на I разряд и увеличивается пространство, отведенное для таблицы. Предельно допустимый размер цепочки составляет 12 разрядов. Если этого окажется недостаточно (вероятность такого события мала), то в выходной файл записывается специальный признак новой таблицы (код N), таблица цепочек очищается, выбирается размер цепочки, равный к+i, и продолжается процесс сжатия с формированием новой таблицы.

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

Для сравнения приведем размеры файла, хранящегося в трех стандартах:

ciouds.bmp 307514 файл не упакован, 640x480 точек
ciouds.pcx 300527 файл упакован по способу RLE
ciouds.gif 159287 файл упакован по способу LZW

Файл ciouds.bmp (облака.bmp) выбран по двум причинам. Во-первых, это одна из стандартных заставок Windows 9X и вы можете увидеть хранящийся в нем рисунок. Во-вторых, этот рисунок трудно сжимаемый, и применение способа RLE не дает ощутимых результатов. Тем не менее стандарт GIF сокращает размер файла почти в два раза, причем это не лучший результат. Сжатие файла выполнено с помощью графического редактора PhotoFinish фирмы ZSoft. Этот редактор (как и любой другой) при упаковке не изменяет количество цветов. В рисунке "Облака" используется 65 цветов. Если пожертвовать одним из них, то размер кода точки сократится с 7-ми до 6-ти разрядов, а размер файла в формате GIF сократится почти в 4 раза. Однако для анализа и сокращения количества цветов нужна специальная программа.

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

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

Содержание раздела