Тема № 2 Форматы графических файлов

Страница 6

2.4 Алгоритм сжатия LZW

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

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

Алгоритм Lempel-Ziv и Welch (LZW) преобразует серию значений данных в серию кодов, которые могут быть самими значениями или кодами, описывающими серию значений. Если использовать аналогию с текстовыми символами, то выходные коды состоят из символов и кодов, которые описывают цепочки символов.

LZW-алгоритм, использованный в GIF,алгоритмически соответствует стандартному алгоритмуLZW со следующими отличиями:

1. Определен специальный код очистки, который сбрасывает все параметры сжатия/раскрытия и таблицы в исходное состояние. Значение этого кода равно 2**<код размера>. Например, если код размера равен 4 (изображение имеет 4 бита на пиксел), код очистки равен 16 (двоичное 10000). Код очистки может появляться в любом месте потока данных и, следовательно, требуется, чтобы LZW-алгоритм обрабатывал последующие коды так, как будто бы начался новый поток данных. Кодировщик должен выводить код очистки в качестве первого кода в каждом потоке данных изображения.

2. Определен код конца информации, который явно указывает на конец потока данных изображения. Если встретится такой код, LZW-обработка прекращается. Этот код должен быть последним кодом, формируемым кодировщиком для изображения. Значение этого кода равно <Код_очистки>+1.

3. Значение первого доступного кода сжатия равно <Код_очистки>+2.

4. Выходные коды имеют переменную длину, начиная от <код_размера>+1 битов на код, до 12 битов на код. Тем самым максимальное значение кода определяется равным 4095 (шестнадцатеричное FFF). Как только значение LZW-кода может превысить текущую длину кода, длина кода увеличивается на единицу. Паковщик и распаковщик этих кодов должны изменяться, чтобы соответствовать новой длине кода.

1. Построение 8-битных байтов

Поскольку LZW-сжатие, используемое для GIF, создает серию кодов переменной длины от 3 до 12 символов каждый, эти коды должны быть переформированы в серию 8-битный байтов. Это обеспечивает дополнительное сжатие изображения. Коды формируются в поток битов так, как если бы они паковались справа налево, и затем выбираются по 8 битов для вывода. Рассматриваемый массив 8-битных символов при упаковке кодов длиной по 5 битов должен быть похож на следующий пример:

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

2. Упаковка байтов

Как только байты созданы, они группируются в блоки для вывода, причем каждому блоку предшествует байт-счетчик со значением от 0 до 255. Блок с нулевым байтом-счетчиком заканчивает поток данных для данного изображения. Эти блоки являются тем, что выводится на самом деле в формате GIF. Такой формат блока обеспечивает дополнительную эффективность за счет того, что позволяет декодировщику считывать данные по мере необходимости, читая сначала байт-счетчик, а затем пропуская сами данные об изображении.

3. Обработка нескольких изображений

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

1. Не делать пауз между изображениями. Каждое обрабатывается сразу же, как только будет распознано декодировщиком.

2. Каждое изображение переписывает любое другое изображение уже находящееся внутри его окна. Экран очищается только в начале и в конце обработки GIF-изображений.