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

Цифровое изображение при хранении занимает большие объемы памяти. Так растровое изображение размером 1024 на 1024 пикселов с глубиной цвета 24 бит занимает 3 Мб. Понятно, что хранение и передача изображений в таком виде является весьма трудоёмкой задачей. Поэтому задача представления изображений в компактной форме (сжатие данных) является весьма актуальной. При этом должны быть разработаны алгоритмы как для кодирования, так и для декодирования (восстановления) изображений.

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

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

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

Груповое сжатие

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

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

Существует много схем группового сжатия, одну из которых можно проиллюстрировать следующим образом:

Входной поток данных:
17 8 54 0 0 0 97 5 16 0 45 23 0 0 0 0 0 3 67 0 0 8

Поток данных после кодирования:
17 8 54 0 3 97 5 16 0 1 45 23 0 5 3 67 0 2 8

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

Входные данные: 1,2,3,4,2,2,2,2,4

Данные после кодирования: 1,2,3,4,2,&3,4.

Принцип: Последовательности повторяющихся значений цвета заменяются его значением и количеством повторений.

Форматы: BMP, TIFF, GIF

Коэффициент сжатия: 2

Метод Хафмана

Этот метод назван в честь его разработчика (1950). Алгоритм основан на том предположении, что некоторые значения сигнала встречаются чаще других. Если проанализировать гистограммы изображений, то можно в этом убедиться. Этот факт можно использовать для сжатия изображений. Использовать для хранения значений интенсивности, которые встречаются чаще, меньшее число бит чем на само значение. Главная проблема в том, чтобы отделять одно значение от другого. Ведь на разные значения отводится разное количество бит. Метод сжатия Хафмана можно проиллюстрировать следующим образом:

Входной поток данных: C E G A D F B E A

Поток данных после кодирования: 0010 0001 000011 1 0011 000010 01 0001 1)

Группировка по байтам: (0010 0001) (000011 1 0) (011 00001) (0 01 00 1 0 1)

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

Этот метод иногда используется в усложненной форме, когда кодируется не одно значение, а последовательности значений. Другая модификация метода – подвергнуть коды Хафмана групповому сжатию.

Форматы: TIFF, GIF

Коэффициент сжатия: 3

Метод LZW

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

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

Входной поток данных: 123 145 201 4 119 89 243 245 59 11 206 145 201 4 243 245

Поток данных после кодирования: 123 256 119 89 257 59 11 206 256 257

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

Форматы: TIFF, GIF

Коэффициент сжатия: 5

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

Метод JPEG

Среди методов сжатия с потерями следует выделить семейство JPEG, разработанное организацией Joint Photographers Experts Group. Метод основан на частотных представлениях изображения и следующих предположениях. Если к сигналу применить интегральное преобразование (Фурье например), то в результате в частотном представлении основную информации несут низкие частоты. Высокие частоты описывают шум и несущественные детали. Удаление 50% высокочастотной информации повлечет за собой удаление 5% полезной информации содержащейся в изображении.

JPEG-сжатие начинается с разбиения изображения на квадратные области размером 8 на 8 пикселов (64 пиксела - 64 байта). Эти области обрабатываются независимо. После преобразования в каждой группе остается от 2 до 20 байт. При восстановлении сигнала должна быть выполнена аппроксимация и восстановлена исходная область 8 на 8 пикселов.

Для сжатого представления сигнала могут использоваться различные преобразования. Наиболее адекватный (качественные) результат дает преобразование Karhunen-Loeve, но оно сложно и трудоемко в реализации. Преобразование Фурье просто, но не дает желаемого результата при восстановлении. Наиболее пригодным оказалось дискретное косинусное преобразование (Discrete Cosine Transform, DCT). При использовании DCT не нужно работать с комплексными числами (исходный сигнал и его спектр вещественные).

В результате преобразования выборки 8 на 8 получаем выборку спектра 8 на 8. При этом низкие частоты содержатся в верхнем левом углу спектра, а высокие в правом нижнем. Высокие частоты можно обнулить и не хранить.

Если представить спектр в виде следующей последовательности:

то можно её закодировать с использование группового сжатия. На последнем этапе сжатия используется кодирование методом Хафмана для более эффективного сжатия конечных данных.

Принцип: Используется методика сжатия с потерями. Хранится не информация о цвете пикселов, а коэффициенты разложения по некоторому базису.

Форматы: JPEG

Коэффициент сжатия: в зависимости от качества от 10 до 1000.

Положительными сторонами алгоритма JPEG является то, что пользователь может управлять соотношением размер/качество, задавая степень сжатия. Выходное цветное изображение может глубину цвета 24 бита на точку. С помощью алгоритма JPEG достигаются большие коэффициенты сжатия при визуально высоком качестве изображения. Отрицательными сторонами алгоритма является то, что при повышении степени сжатия изображение распадается на отдельные квадратные области (размером 8x8). Это связано с тем, что происходят большие потери в низких частотах при квантовании, и восстановить исходные данные становится невозможно. Кроме того может проявляться так называемый эффект Гиббса – ореолы по границам резких переходов цветов. Кроме того, так как это алгоритм сжатия с потерями, изображения обработанные с его применением практически неприменимы для анализа и дальнейшей обработки.