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

Файлы состоят из символов и, возможно, «невидимых» кодов управления печатью. Каждый символ в кодах ASCII представляется 1 байтом.

Алгоритм Лемпеля—Зива. LZW (Lemple-Zif-Welch)

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

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

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

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

При применении этого алгоритма к загрузочным файлам (*.exe, *.com), результат — 10-20%, так как избыточность кода, создаваемого компиляторами меньше избыточности текста на естественном языке.

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

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

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

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

Алгоритм RLE (Run Length Encoding) «сжатие последовательности одинаковых символов»

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

RLE дает хороший результат для графических адаптеров с 1 или 2 бита на (CGA), либо при раздельном хранении цветовых плоскостей (EGA, VGA — 16-ти цветовые режимы). Степень сжатия зависит от графического адаптера и самого изображения («гладкие» картинки сжимаются сильнее). Для CGA и EGA коэффициент сжатия больше 2. RLE работает плохо для режима 8 бит/ .

Достоинства: простота, скорость декодирования.

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

1. Сжатие графической информации с потерями (JPEG).

Они содержат большое количество информации (24 бит/ (цв) и 8 бит/ (ч-б)) и могут весить до нескольких Мб памяти (25 Мб при сканировании цветного изображения (10 т/мм)). Характер информации постоянно меняется вдоль линии сканирования.

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

¾ мелкие детали,

¾ изменения оттенков,

¾ абсолютная яркость.

Например, абсолютная яркость: никакая точка телевизора не может быть чернее, чем серый цвет выключенного телевизора. Видимый нами иссиня-черный цвет — не более, чем иллюзия, которая возникает из-за соседства с ним контрастных ярких тонов.

Также можно заметить, что на большой площади изображения изменение цвета и интенсивности часто незначительны (небо). Сжатие по методу RLE позволяет уменьшить размеры файлов в 2-3 раза. Но это не решает полностью проблему, нужны более высокие степени сжатия.

Сжатие изображения по стандарту JPEG

(Joint Photografic Experts Group — объединенная группа экспертов по обработке фотографий). Обеспечивает уменьшение размера файла в 25-100 раз. Разработан Международной организацией по стандартизации (ISO). Такое сжатие достигается за счет сжатия с потерями. Достаточно сложен с вычислительной точки зрения, так как занимает много процессорного времени.

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

1 этап. Кодирование изображения по алгоритму JPEG начинается с преобразования цветового пространства из RGB в YUV. Канал Y содержит информацию о яркости, U и V — о цвете. Система зрения человека особенно чувствительна к Y компоненте и менее чувствительна к U и V.

Y-компонента — это цветные изображение, показанное на черно-белом телевизоре.

U-компонента — информация о синем цвете.

V-компонента — информация о красном цвете.

Поэтому Y-компонента будет сжиматься в меньшей степени, чем U и V.

2 этап (необязательный). Прореживание. Отбрасывается U и V — компоненты строк или столбцов с определенными номерами. Например, при прореживании с коэффициентами 2:1:1 будет отбрасываться информация о цвете для каждой 2-ой строки и каждого 2-го столбца, в результате чего будет потерено 75% данных цветности. Коэффициента 1:1:1 — прореживания нет. На Y-компоненту прореживание не отражается.

3 этап — «Дискретное косинусное преобразование» — удивительная математическая операция.

Рис. 16.1

ДКП выполняется отдельно для Y, U и V-компонент. Изображение разбивается на блоки размером 8´8 . Такой участок с большой вероятностью содержит близкого цвета. При ДКП информация о 64 преобразовывается в матрицу из 64 коэффициентов, которые характеризуют «энергию» исходных . Максимальные значения коэффициентов концентрируются в левом верхнем углу матрицы 8´8, минимальные — в правом нижнем. Первый коэффициент передает подавляющую часто «энергии», а количество «энергии», представляемой остальными коэффициентами, быстро убывает. Таким образом большая часть информации исходной матрицы 8´8 представляется первым элементом матрицы, преобразованной по ДКП. На этом этапе происходит некоторая потеря информации, связанная с принципиальной невозможностью точного обратного преобразования. Однако, она незначительна по сравнению с потерями на следующем этапе.

4 этап. Квантование. Применяется для сокращения разрядности коэффициентов. Здесь происходит значительная потеря информации. Отбрасываются малые изменения коэффициентов. Поэтому после восстановления изображения получаются уже другие значения . (Для U и V компонентов квантование более грубое).

5 этап.— Полученные данные сжимаются по RLE, LZW-алгоритму или алгоритму Хаффмана для достижения еще большей компрессии. Помимо применяемого кодирования наиболее часто встречающихся символов, последние нули в конце строки могут быть заменены символом «конец блока», а так как все блоки имеют одинаковый размер, всегда известно сколько нулей было опущено.

При восстановлении изображения шаги выполняются в обратном порядке.

Изображения, в которых соседние мало отличаются друг от друга, лучше поддаются сжатию. Однако чем меньше размер выходного файла, тем меньше степень "аккуратности" при работе программы-конвертора и, соответственно, ниже качество выходного изображения. Обычно в программах, позволяющих сохранять растровые данные, есть возможность некоторого компромисса между объемом выходного файла и качеством изображения. При лучшем качестве объем выходного файла в 3-5 раз меньше исходного незапакованного. При качестве похуже - меньше исходника в десятки раз, но, как правило, при этом качество изображения уже не позволяет использовать его где-либо. Данный формат предназначен для хранения в основном фотографических изображений с большим количеством оттенков и цветовых переходов и почти не подходит для хранения однотонных изображений типа кадров из мультфильмов, скриншотов (сжатие будет слишком низким или качество картинки достигнет критической отметки). Этот метод сжатия графических данных используется в файлах формата PDF, PostScript (для включенных объектов), собственно в JPEG и других.

6 этап. Сглаживание в процессе восстановления изображения. Из-зи потери информации на границах между блоками (8´8 ) могут возникать разрывы. Поэтому необходимо сглаживание.

Новый стандарт JPEG 2000

В его разработке приняли участие Международная организация по стандартизации (International Organization for Standardization), Международный союз телекоммуникаций (International Telecommunications Union), компании Agfa, Canon, Fujifilm, Hewlett-Packard, Kodak, LuraTech, Motorola, Ricoh, Sony и другие. Позволяет сжимать изображения в 200 раз без заметной для невооруженного глаза потери качества. Основным отличием JPEG2000 от предыдущей версии этого формата является использование алгоритма волнового преобразования (изображение описывается с помощью математических выражений как непрерывный поток) вместо преобразования Фурье, что и предотвращает появление характерных блоков. Умеет также без ущерба модифицировать (масштабировать, редактировать) рисунок, сохраненный в этом формате. Алгоритм волнового преобразования позволяет просматривать и распечатывать одно и то же изображение при различных (заданных пользователем) значениях разрешения и с требуемой степенью детализации. Благодаря этой особенности JPEG2000 быстро найдет свое место в Сети, поскольку обеспечит возможность загружать картинку с разными значениями разрешения в зависимости от пропускной способности конкретного канала связи. Да и тот факт, что пользователи Интернета смогут получать изображения высокого качества, немаловажен. Еще одно значимое преимущество JPEG2000 - возможность управлять 256-цветовыми каналами, а в результате получать качественные цветные изображения. Специалисты обещают, что в общем случае новый формат будет как минимум на 30% эффективнее, чем JPEG. И еще один плюс - новый стандарт является открытым.

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

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

Изменение цветовой модели графического файла можно объяснить на примере. Файлы в цветовом пространстве CMYK больше аналогичных в пространстве RGB на 33% (так как в CMYK имеется дополнительный четвертый черный канал). Если не планируешь печатать файлы или ты уверен в том, что сможешь корректно провести цветоделение (переход в субтрактивную модель CMYK) позже, можешь хранить рабочие файлы в RGB.

Изменение разрешения растрового файла используется для уменьшения избыточности файла. Файл с разрешением 600 точек на дюйм больше своего аналога разрешением в 300 точек в четыре раза (!), а качество печати при повышенном разрешении не всегда будет выше. Так что если разрешение избыточно, можешь его понизить, только надо помнить, что после такого назад дороги не будет (процесс является необратимым) и никакая последующая интерполяция не восстановит потерянные пикселы. Так что при задании необходимого разрешения необходимо быть внимательным. Следует учесть, что параметр разрешения контуров, применительно к векторной графике, не имеет отношения к объему выходного файла (это уже другое разрешение и другое понятие), но влияет на аккуратность "прорисовки" вектора при его растеризации в устройстве, где производится печать. Так что уменьшение этого параметра для векторной графики не уменьшит объем файлов, а только ухудшит качество печати.

Ресемплирование, или изменение глубины цвета растрового изображения, - изменение начальной глубины цвета файла. Некоторые оцифровывающие устройства выдают растровую информацию с глубиной цвета, превышающей достаточное для печати значение 8 бит на канал. Это иногда оправданно, так как большее значение бит на канал позволяет задавать большее число градаций цвета, что важно, например, при сильной, "кардинальной" цветокоррекции - сильном осветлении или затенении отдельных участков. Однако в большинстве случаев для хранения растровых данных в различных цветовых моделях с лихвой хватит глубины цвета 8 бит на канал. Кроме того, один из стандартов сжатия для RGB-изображений подразумевает использование разного количества бит для разных цветовых составляющих (обычно наибольшее количество бит используется для зеленого канала). Также большинство фильтров Adobe Photoshop рассчитано на работу с изображениями с глубиной цвета в 8 бит (с изображением, использующим нестандартную глубину цвета, становится практически невозможно работать, так как большинство фильтров рассчитаны на значение глубины цвета именно в 8 бит).