Арифметическое сжатие

Схема сжатия LZW

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

Групповое кодирование

Сжатие изображений

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

Один из самых простых методов сжатия - групповое кодирование или групповое сжатие. Другое название - "сжатие методом RLE" (run-length encoding). Идея состоит в том, что вместо повторяющихся пикселов хранится информация о цвете точки и количестве повторений. Представление данных имеет варианты: может сначала идти запись о цвете, потом о количестве, может - наоборот. Это порождает проблемы воспроизведения. Для большинства растровых файлов, особенно для фотореалистических сжатие RLE не эффективно, т.к. количество повторяющихся пикселов мало. Возникает даже лишняя трата ресурсов.

Кодирование методом Хаффмана (Huffman) - общая схема сжатия. Подход создан в 1952 г. для текстовых файлов. Имеется множество вариантов. Основная идея - присвоение двоичного кода каждому уникальному элементу, причем длина этих кодов различна. Для наиболее часто повторяющихся элементов используются более короткие коды. Присвоения хранятся в таблице перекодировки, которая загружается в декодирующую программу перед самими кодами. Существуют различные алгоритмы построения кодов. Степень сжатия оценивается как 8: 1. Для файлов с длинными последовательностями схема Хаффмана работает не очень хорошо. Здесь лучше групповое сжатие. Т.к. для построения кодов нужна статистика, обычно используют 2 прохода. Сначала создается статистическая модель, затем выполняется собственно сжатие (кодирование). Т.к. работа с кодами переменной длины требует много времени, кодирование и декодирование длительны.

Метод назван по первым буквам фамилий разработчиков: Lempel, Ziv, Welch. Разработка 1984 г. Сначала метод предназначался для аппаратной реализации. Как и алгоритм Хаффмана, алгоритм LZW имеет несколько вариантов. Идея - поиск повторяющихся пиксельных узоров и их кодирование. Кодовая таблица создается не перед кодированием, а в процессе кодирования, что делает алгоритм адаптивным. Рассмотрим последовательность "ababaaacaaaad". Пусть каждая буква кодируется в изображении 2-битной величиной. Начальная кодовая таблица кодирует каждый атомарный объект: a - 00, b - 01, c - 10, d - 11. Затем алгоритм переходит к поиску последовательностей. Он может распознать только 1-буквенные последовательности. Первая 2-буквенной последовательности не распознается и подлежит кодированию. Т.к. длина кода исчерпана, ее увеличивают на 1: a - 000, b - 001, c - 010, d - 011, ab - 100. Следующее 2-буквенное сочетание распознается. Для каждой буквы было 2-битное описание. На последовательность требуется 2 * 2 = 4 бита. При замене последовательности 3-битным кодом экономим 1 бит на каждом появлении последовательности. Типичный коэффициент сжатия для метода 3: 1. Изображения с повторяющимися цветными узорами сжимаются до 10: 1. Отсканированные фотографии и изображения, не содержащие узоров, сжимаются плохо.

Подобно алгоритму Хаффмана при арифметическом сжатии используются короткие коды для часто повторяющихся участков, более длинные коды - для редко повторяющихся. Подобно LZW сжимаются последовательности. Идея: состоит в том, что каждая последовательность пикселов отображается в диапазон чисел между 0 и 1. Эта область затем представляется как двоичная дробь переменной точности. Учитываются вероятностные характеристики изображения. Существует несколько алгоритмов арифметического сжатия. В зависимости от характеристик исходного файла и точности используемой статистической модели можно достичь сжатия 100:1.

Дата добавления: 2014-01-11