Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



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




Читайте также:
  1. A) Зафиксированное место на диске, в котором зарегистрированы имена других файлов
  2. I. Решение телеграфных уравнений для линии без потерь
  3. Алгоритмы
  4. Алгоритмы внутренней сортировки. Элементарные методы сортировки
  5. Алгоритмы заливки замкнутых областей.
  6. Алгоритмы маршрутизации в сетях.
  7. Алгоритмы прохождения графа.
  8. Алгоритмы разгона и торможения. Сравнительная оценка алгоритмов. Примеры.
  9. Алгоритмы сжатия без потерь - кодирование длин серий (RLE), алгоритм Лемпеля-Зива-Велча (LZW), форматы GIF и PNG.

 

Файлы состоят из символов и, возможно, «невидимых» кодов управления печатью. Каждый символ в кодах 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 бит).

 


Дата добавления: 2015-04-18; просмотров: 21; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.01 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты