Алгоритм Хаффмана

Растровые данные файла TIFF могут сжиматься с использованием любого из нескольких методов, поэтому для чтения файлов TIFF должны быть средства рас­паковки RLE, LZW и несколько других.

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

GIF

Формат GIF (Graphics Interchange Format), появившийся в 1987 году, является очень старым, но по-прежнему популярен в Интернете. От других графических форматов его отличает использование режима индексированных цветов (не более 256). Но это не мешает GIF быть любимым форматом веб-мастеров, которые применяют его для создания и оформления веб-страниц. Главной причиной этого является использование небольших по размеру файлов.

Файл формата GIF начинается с заголовка, содержащего код, который говорит о том, что это именно GIF-файл; далее следует номер версии GIF и другая инфор­мация. Если файл хранит одно изображение, то за заголовком обычно располагается общая таблица цветов, определяющая цвета изображения. Если в файле хранится несколько изображений (формат GIF, аналогично TIFF, позволяет кодировать в одном файле два и более изображений), то вместо общей таблицы цветов каждое изображение сопровождается своей собственной таблицей цветов.

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

Очень популярны анимированные GIF-файлы. Например, собачки, смешно ма­шущие ушами, или крокодил, раскрывающий свою зубатую пасть.

Основные достоинства формата GIF заключаются в широком распространении этого формата и его компактности. Но в изображениях, хранящихся в виде GIF- файла, не может быть использовано более 256 цветов.

PSD

PSD (Photoshop Document) является «родным» форматом Adobe Photoshop. Он может хранить информацию по слоям. Этот формат поддерживает глубину цвета вплоть до 16 бит на канал (48 бит на пиксель для цветных изображений и 16 бит на пиксель для черно-белых). Кроме того, хранится информация об альфа-каналах, слоях, контурах, прозрачности, векторных надписях и т. д.

Формат PSD используется для хранения изображений, содержащих специфи­ческие, свойственные только Adobe Photoshop, элементы. PSD-файлы могут быть открыты во многих популярных программах просмотра графических файлов.

PDF

Формат PDF (Portable Document Format) в свое гремя был разработан компанией Adobe. Он применяется для описания документов. Для создания, редактирова­ния и просмотра PDF-файлов используются специальные программы (например Acrobat Reader). Этот формат весьма широко применяется в процессе допечатной подготовки.

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

JPEG

Формат JPEG (Joint Photographic Experts Group) является наиболее попу­лярным среди профессионалов и любителей цифровой фотографии. Это легко объяснимо, поскольку именно данный формат обеспечивает минимальные размеры файлов при возможности сохранения 24-битных полноцветных изображений.

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

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

Основные сведения о сжатии изображений

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

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

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

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

Алгоритмы сжатия файлов без потерь

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

Алгоритм Хаффмана

Символы заменяются кодовыми последовательностями разной длины. Чем чаще используется символ, тем короче код (например буквы «а», «е», «и», «с» - 3 бита, «щ», «х», «э», «ю» - 8 бит). Могут использоваться готовые кодовые таблицы или строиться новые на основе статистического анализа конкретного файла. Гаран­тируется возможность декодирования, хотя кодовые последовательности имеют разную длину. Степень сжатия — до 50 %.

Алгоритм Лемпеля-Зива (LZW)

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

Данный алгоритм основан на сведении к минимуму избыточности. Вместо кодирования каждого символа кодируются часто встречающиеся последовательности символов (например, слова «который», «также»). Имена же собственные, встреча­ющиеся один раз, не кодируются.

Программа алгоритма просматривает файл с текстом или байтами графиче­ской информации и выполняет статистический анализ для построения кодовой таблицы.

Если заменить 60-70 % текста символами, длина которых меньше половины от первоначальной, можно добиться сжатия примерно 50 %.

При применении этого алгоритма к загрузочным файлам (EXE, СОМ) резуль­тат составляет 10-20 %, так как избыточность кода, создаваемого компиляторами, меньше избыточности текста на естественном языке.

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

Графические контурные файлы архивируются хорошо, так как обладают боль­шой избыточностью (фон).

Полутоновые и цветные изображения тоже можно архивировать, но с меньшим успехом.

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

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

Алгоритм RLE (Run Length Encoding)

Изображение рассматривается как последовательность байтов. Одинаковые байты кодируются парой: первый байт (count) является счетчиком одинаковых байтов, а второй — байтом из кодируемой последовательности. Для отличия счетчика два его старших бита устанавливаются равными единице. Это позволяет кодировать последовательности длиной не более 63. Байты изображения со значениями больше 191 кодируются двумя байтами.

Достоинствами метода являются простота и скорость декодирования.

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