Методы сжатия данных: назначения, показатели эффективности, классификация.

Степень эффективности сжатия характеризуется коэффициентом сжатия, который показывет отношение объема исходных данных к объёму сжатых данных:

Если K >1, то сжатие считается эффективным.

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

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

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

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

Все алгоритмы сжатия по соотношению времени на кодирование данных и на их распаковку делятся на симметричные и несимметричные.

Симметричные алгоритмы сжатия требуют одинаковое время на кодирование и распаковку данных. Несимметричные алгоритмы сжатия тратят больше времени на кодирование данных, чем на их распаковку.

В настоящее время разработано большое количество различных алгоритмов сжатия изображений: от самых простых (коэффициент сжатия k=1,1¸2) до самых изощрённых, обеспечивающих k³30. Стоит отметить, что более сложные схемы сжатия часто используют комбинацию более простых алгоритмов для достижения максимального эффекта.

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

Алгоритм RLE

Все алгоритмы серии RLE основаны на очень простой идее: повторяющиеся группы элементов заменяются на пару (количество повторов, повторяющийся элемент)

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

Алгоритмы сжатия с потерями

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

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

JPEG на данный момент один из самых распространенных способов сжатия изображений с потерями. Опишем основные шаги, лежащие в основе этого алгоритма. Будем считать, что на вход алгоритма сжатия поступает изображение с глубиной цвета 24 бита на пиксел (изображение представлено в цветовой модели RGB).

Кодирование методом Хаффмана

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

Фрактальное сжатие

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

1. Разделение изображения на неперекрывающиеся области (домены). Набор доменов должен покрывать всё изображение полностью.

2. Выбор ранговых областей. Ранговые области могут перекрываться и не покрывать целиком всё изображение.

3. Фрактальное преобразование: для каждого домена подбирается такая ранговая область, которая после аффинного преобразования наиболее точно аппроксимирует домен.

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

Этапы восстановления изображения:

1. Создание двух изображений одинакового размера A и B. Размер и содержание областей не имеют значения.

2. Изображение B делится на домены так же, как и на первой стадии процесса сжатия. Для каждого домена области B проводится соответствующее аффинное преобразование ранговых областей изображения A, описанное коэффициентами из сжатого файла. Результат помещается в область B. После преобразования получается совершенно новое изображение.

3. Преобразование данных из области B в область A. Этот шаг повторяет шаг 3, только изображения A и B поменялись местами.

4. Шаги 3 и 4 повторяются до тех пор, пока изображения A и B не станут неразличимыми.

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