Способы сжатия растровых графических изображений

Методы сжатия графических изображений

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

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

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

Ø кодирование длин серий;

Ø метод Хаффмана;

Кодирование длин серий (Run Length Encoding )

Как известно, все документы (графика, тексты, программы и т. п.) хранятся в компьютере в виде файлов — организованных записей. Изображения хранятся в файлах специальных графических форматов, которых сейчас насчитывается более десятка. Основой для разложения изображения на множество элементов является пиксель. Основа файла — это описание цветов всех пикселей. Описание цвета пикселя (три / четыре числа) является кодом цвета в соответствии с той или иной цветовой моделью. Указание на цветовую модель также включается в файл. Кроме того, записывается размер изображения в пикселях.

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

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

Заменим для простоты значения цвета буквами. Если в документе, скажем, имеется такая последовательность «АААААВВВВВВВСССССС», ее можно сжать таким образом: 5А7В6С. В результате вместо 18 символов в документе достаточно хранить всего 6.

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

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

Если система выводит ошибку, возможно программа, считывающая файл ожидает появление данных в ином порядке, чем программа, сохраняющая этот файл на диске. Требуется преобразование в иной формат

Метод RLE включается в некоторые графические форматы, например:

Ø BMP (для 16 и 256 по желанию);

Ø TGA (по желанию);

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

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

Заменим также для простоты значения цвета буквами. Например, в следующей последовательности букв ААСАААВАВАВВАВСАСВСАСААССС заметно, что чаще всего встречается символ А (12 раз), затем символ С (9 раз) и, наконец, символ В (5 раз). Следовательно, символ А можно заменять кодом 0, символ С — кодом 1, а символ В — кодом 00. И так далее, если элементов для кодирования больше. В результате, если считать, что каждый символ в нашем примере кодируется 1 битом, то для передачи строки потребуется 208 битов, а в сжатом виде объем информации составит только 31 бит.

Алгоритм LZW

Алгоритм, названный в честь своих создателей Лемпеля, Зива и Велча (Lempel, Ziv и Welch), не требует вычисления вероятностей встречаемости символов или кодов. Основная идея состоит в замене совокупности байтов в исходном файле ссылкой на предыдущее появление той же совокупности.

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

Например, если сжимают байтовые данные (текст), то строк в таблице окажется 256 (от «0» до «255»). Для кода очистки и кода конца информации используются коды 256 и 257. Если используется 10-битный код, то под коды для строк остаются значения в диапазоне от 258 до 1023. Новые строки формируют таблицу последовательно, т. е. можно считать индекс строки ее кодом.

Пусть сжимается последовательность символов АВВСВВВ. Сначала в сжатый документ сохраняется код удаления [256], затем считывается символ «А» и проверяется, существует ли в таблице строка «А». Поскольку при инициализации в таблицу сохраняются все строки длиной в один символ, то строка «А», конечно, существует в таблице.

Далее считывается следующий символ «В» и проверяется, существует ли в таблице строка «АВ». Такая строка в таблице пока отсутствует, поэтому с первым свободным кодом [258] в таблицу вносится строка «АВ», а в документе сохраняется код [А]. Последовательность «АВ» в таблице отсутствует, поэтому в таблицу добавляется код [258] для сочетания «АВ», а в документе сохраняется код [А].

Далее рассматривается последовательность «ВВ», которая отсутствует в таблице, в таблицу заносится код [259] для символов «ВВ», а в документе сохраняется код [В].

Считывается символ «С» и проверяется наличие символов «ВС» в таблице, поскольку такая последовательность отсутствует, то в таблицу заносится кед [260] для последовательности «ВС», а в документ — код [В].

Снова добавляется из исходного файла символ «В» и теперь уже проверяется сочетание «СВ», которое тоже отсутствует. В таблицу записывается код [261] для «СВ», а в документ — код [С].

Затем считывается символ «В» и строка «ВВ», наконец, имеется в таблице, поэтому считывается следующий символ и рассматривается последовательность «ВВВ», которая, конечно, в таблице отсутствует. В таблицу заносится код [262] для «ВВВ», а в документ (внимание!) — код [259].

В результате в документе окажется следующая последовательность кодов [256][А][В][В][С][259], что короче исходной последовательности. К сожалению, последовательность слишком короткая, а алгоритм достатчно сложен, чтобы выгода оказалась реальной. При значительном объеме коэффициент сжатия может достигать несколько сот единиц.

Особенностью рассматриваемого алгоритма LZW является то, что для выполнения обратного процесса («распаковки») нет необходимости сохранять таблицу в документе (алгоритм позволяет восстановить таблицу строк только из сохраненных в документе кодов).

Этот метод гораздо совершеннее RLE для областей с переходами цветов, однако кодировка в него требует больше системных ресурсов.

Метод LZW включается в некоторые графические форматы, например: TIFF ; GIF .

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

JPEG (Joint Photographic Experts Group)

Исследователями визуального восприятия человека отмечено, что далеко не вся информация требуется для того, чтобы адекватно воспринимать цветное изображение. Для реализации этого закона были разработаны алгоритмы с потерей информации, которые обеспечивают выбор уровня компрессии с уровнем качества изображения (рис. 1). Тем самым достигается компромисс между размером и качеством изображений.

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

Рис. 1. Компромисс между качеством и уровнем компрессии

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

Замечание: RGB-изображение конвертируется в пространство YUV (иногда называемое также YcrCb), основанное на характеристиках яркости (составляющая Y) и цветности (составляющие U и V).

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

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

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

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

Источник

Изображения: форматы и сжатие (1/3)

На что при загрузке сайта расходуется больше трафика? Чаще всего это картинки, и их суммарный «вес» частенько в несколько раз больше, чем у разметки, скриптов и стилей. В файлах изображений распространенных форматов растровые данные хранятся в сжатом виде, и это значительно лучше, чем несжатый BMP. А если хочется ещё лучше? Ведь в достаточно крупных проектах каждый байт на счету (например, в TradingView, чего уж там скромничать).

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

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

Средневековье

Восьмидесятые годы прошлого столетия стали временем становления растровой графики. Графика как таковая применялась и раньше, но теперь она стала гораздо более доступна, и не в последнюю очередь на неё повлияла игровая индустрия. Atari 2600 позволяла рисовать нечто более изысканное, чем белый прямоугольник. А Commodore 64 обладал видеопамятью, с настоящими пикселями, и работать с ним было удобнее, чем «переключи цвет не позже 31415-го такта».

Нарисовать на экране Мону Лизу, выставляя пиксели вручную по хитрому алгоритму, трудновато. Да и не нужно, потому что из видеопамяти выдернуть кусок данных и сохранить его в файл, а потом из файла вставить. Такой дамп памяти в Бейсике делался командой BSAVE , а сам формат назывался в честь неё BSAVE’d. Редактировать изображения стало намного удобней, и расцвели пышным цветом простенькие графредакторы, большей частью неотличимые друг от друга.

Но некоторые из редакторов переросли детский возраст и стали весьма удобным и полезным инструментом. Так в 1984 появился PCPaint, в котором можно было рисовать при помощи мыши. Помимо очевидных удобств пользовательсого интерфейса PCPaint давал еще одно преимущество. Дело в том, что дамп BSAVE не включал данных о размере изображения, глубине цвета и палитре, и если видеорежимов было немного (да и цветное изображение вменяемо показывалось в черно-белом режиме) то для палитры приходилось использовать отдельный файлик PAL. В формате PIC редактора PCPaint содержались и палитра, и дамп BSAVE. Это маленький шаг для программиста и гигантский скачок для всего человества. Что-то вроде «а давайте придумаем формат MKV, в котором субтитры можно будет хранить внутри, и чтобы не нужно было их в нужную папочку класть».

Но еще одна проблема оставалась нерешенной: на PC есть BSAVE и на Apple есть BSAVE , но они генерируют файлы разного формата. Это и не удивтельно, внутреннее представление картинки в памяти различалось. Существовали транскодеры, но стало понятно, что долго эта вендор-зависимая кутерьма не продержится. В 1984 компания Truevision представила формат TARGA, более известный как TGA. А в следующем 1985 году свет увидела рисовалка PC Paintbrush. Хотя PC Paintbrush и продавалась хуже, её формат PCX, переносимый и достаточно простой, прожил дольше, чем PIC.

И в TGA, и в PCX данные о размере изображения и палитре хранились в явном виде, без сильной привязки к железу. Это стало возможным, потому как пиксельные данные перестали зависеть о конкретной платформы и представляли из себя просто сканлайны: слева направо, сверху вниз.

Но была ещё одна важная особенность у этих двух форматов, растровые данные в них хранились в сжатом виде. Применяемый алгоритм RLE не был верхом эффективности, но это было уже весьма неплохо.

RLE (Run length encoding) достаточно простой алгоритм, но он хорошо показывает, как работает сжатие данных. Сжать данные без потерь означает, избавиться от избыточности в них. Для этого берем набор данных, находим в них цепочки повторяющихся значений и заменяем их на нечто более компактное.

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

Скорее всего, Вы уже пользуетесь им. Посмотрим на строку « AAAAAAAAAAAABBBAAAAAAAAA ». Если нам придется продиктовать её по телефону, то это будет звучать как «двенадцать заглавных букв A, три заглавные B, девять заглавных A». Если записать это, получится « 12 A 3 B 9 A », а чтобы не было разночтений, то « 9 A 3 A 3 B 9 A ». Гораздо компактнее.

Возьмем теперь другую строку, « 0KXQsNCx0YDQsNGF0LDQsdGA », и попытаемся её так сжать. Получится « 1 0 1 K 1 X …», стоп-стоп-стоп! Строка получается вдвое длиннее, чем исходная, это же ни разу не сжатие. Модифицируем алгоритм и добавим к цифрам буквы: буква A означает, что следующий символ пишется «как есть»; если B, то два; если C, то три, и так далее. Выходит « X 0KXQsNCx0YDQsNGF0LDQsdGA ». Итого, в лучшем случае мы получаем сжатие в 350%, а худшем случае мы теряем только 4%.

Разумеется, в реальных условиях кодируются обычно байты, а не буквы латинского алфавита, и длины последовательностей кодируются значениями от 0 до 255. Плюс к тому, обычно бессмысленные значения длин серий игнорируются: в нашем примере 1 и A делают одно и тоже, а 0 вообще смысла не имеет. Но это детали, суть остается одна и та же.

Энтропия

Как бы ни хотелось избежать теории, эта вещь слишком важная, чтобы её игнорировать. Вы заметили, что не все последовательности получается сжать? Строки AAAAAAAAAAAABBBAAAAAAAAA и 0KXQsNCx0YDQsNGF0LDQsdGA одной длины, 24 символа, но во второй эти символы более хаотичны, и её сжать труднее.

Мера такой хаотичности — информационная энтропия, определяется она как количество информации в сообщении.

Мало энтропии	Больше	Еще больше

Само наличие информационной энтропии говорит о том, что данные можно сжать только до определенной длины. Дальше никак, магия в процессе не задействована. И если верить Клоду Шеннону, фильм «Клик» до килобайта не сжимается.

Чтобы проиллюстрировать это, обратимся к тому, что на первый взгляд не имеет отношения к IT.

Судоку слева содержит 81 цифру и уже решен. Тот, что посередине, содержит меньше информации, 26 цифр, но решив его, можно восстановить все исходные 81.

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

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

• Изображение может иметь размеры до 65536×65536. Палитра до 256 цветов, либо 24-битный цвет без палитры. Заголовок всегда размером 128 байт, содержит размер изображения, количество цветов и палитру до 16 цветов по одному байту на канал. Естественно, 256-цветовая палитра в такой заголовок не влезет, и если она есть, она дописывается в конец файла и имеет размер 769 байт (1 байт сигнатуры и 256×3 байт данных). Есть ещё поле для палитры CGA, но она более не поддерживается.
• «Сырой» поток данных состоит из сканлайнов — горизонтальных линий в один писель. Внутри каждого сканлайна может быть до 4 битовых плоскостей: R, G, B, A. Все плоскости пишутся последовательно: RRRRGGGGBBBBAAAA . Плоскости состоят из строго чётного количества байтов, и при необходимости к сырым данным дописываются заполнители, чтобы это условие выполнялось. Такие данные-заполнители при декодировании игнорируются.
• Сжатие «сырых» растровых данных производится построчно, при помощи RLE. «Построчно» означает, что серия RLE не может выходить за пределы битовой плоскости.
• В RLE байтовые значения от 192 до 255 кодируют количество повторений символа от 0 до 63 раз соответственно. Остальные значения — литеральные, если ни встречаются на том месте, где ожидается количество повторений, считается, что они повторяются один раз.

PCX на практике

Теперь давайте на примере разберем этот шмат технических данных. Возьмем для примера такую вот картинку (17×8, для удобства увеличена в 8 раз):

Определимся с палитрой. В изображении три разных цвета, поэтому нам подходят палитры из 4, 16 и 256 цветов, а также Truecolor. В 4-цветовой палитре у нас будет в одном байте 4 значения (8 бит байта поделить на 2 бита номера в палитре); в 16-цветовой — 2 пикселя на байт; в 256-цветовой — пиксель на байт (плюс 769 байт дополнительной палитры); в Truecolor — три байта на пиксель. Выбор очевиден, 4 цвета.

Цвета расположим, например, так:

Теперь выписываем битовые значения первой строки, начиная со старших битов. Листинг в четверичной системе, разделители — границы байтов.

0000 0000 0000 0000 0

Получается 4,25 байта. RLE с дробными байтами не работает, добиваем до пяти.

0000 0000 0000 0000 0 000

В документации сказано, что в сканлайне должно быть чётное количество байт. Делать нечего, добиваем ещё.

0000 0000 0000 0000 0 000 0000

То же самое проделываем с остальными строками, получаем:

0000 0000 0000 0000 0 000 0000
0111 1111 1111 1111 0 000 0000
0121 2121 2121 2121 0 000 0000
0212 1212 1212 1212 0 000 0000
0222 2222 2222 2222 0 000 0000
0202 0202 0202 0202 0 000 0000
0020 2020 2020 2020 0 000 0000
0000 0000 0000 0000 0 000 0000

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

0000 0000 0000 0000 0 000 0000
0111 1111 1111 1111 0 000 0000
0121 2121 2121 2121 0 000 0000
0212 1212 1212 1212 0 000 0000
0222 2222 2222 2222 0 000 0000
0202 0202 0202 0202 0 000 0000
0020 2020 2020 2020 0 000 0000
0000 0000 0000 0000 0 000 0000

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

0000 0000 0000 0000 0 000 0000
0111 1111 1111 1111 0 000 0000
0121 2121 2121 2121 0 000 0000
0212 1212 1212 1212 0 000 0000
0222 2222 2222 2222 0 000 0000
0202 0202 0202 0202 0 202 0202
0020 2020 2020 2020 0 000 0000
0000 0000 0000 0000 0 000 0000

Закодируем получившееся в RLE. Пожалуй, будет удобней перейти к более привычному шестнадцатеричному виду:

00 00 00 00 00 00
15 55 55 55 00 00
19 99 99 99 00 00
26 66 66 66 00 00
2A AA AA AA 00 00
22 22 22 22 22 22
08 88 88 88 00 00
00 00 00 00 00 00

Кодируем первую строку. 6 байт 0x00 . Повтору 6 раз соответсвует значение 192 + 6 = 198 или C6 . После него пишем, какое же значение мы собираемся повторять 6 раз, получается 0xC6 0x00 . Первый сканлайн готов.

Далее три одинаковых байта становятся 0xC3 0x55 .

И в конце строки два нулевых байта, которые можно представить двумя способами: в лоб, 0x00 0x00 , или более хитро, 0xC2 0x00 . И так и сяк два байта. На девушек произвести впечатление хитрым приёмом вряд ли получится, а других причин делать вещи заковыристее, чем требуется, нету, поэтому берем просто 0x00 0x00 .

Продолжая подобным образом, получим:

Осталось дописать сверху 128-байтный заголовок и готово! А чтобы полюбоваться на получившееся, можно запустить этот скрипт. Он на node.js, но уверен, на Ваш любимый язык переписать не составит никакого труда.

PCX на практике 2: палитра

Возьмем теперь другое изображение и снова переведем его в PCX, пытаясь максимально сжать. На этот раз картинка поменьше, 7×5.

Это НЛО. Знаю, что не очень похоже.

Перво-наперво, выберем глубину цвета: 2 бита. Это четыре цвета, как раз, сколько нам и нужно. Определяем палитру, например, так:

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

Сырые данные	Сжатые данные
0F C0 3A B0 FF FF D9 9C 3F F0	0F C1 C0 3A B0 C2 FF C1 D9 9C 3F C1 F0

Упс! Сжатые данные получились больше по размеру, чем исходные. Это потому, что значения от 0xC0 до 0xFF — это маркеры количества повторений, и их нельзя записать просто так. Вместо 0xC0 пришлось подставить C1 C0 , вместо 0xF0 — 0xC1 0xF0 и так далее.

В случае 0xFF 0xFF нам повезло — там мы драгоценных байт не потеряли. Но в целом выходит унылая картина: теперь RLE вместо того, чтобы помогать, только мешает.

В сторону безысходность, посмотрим, что с этим можно сделать. Маркерами являются байты с двумя старшими битами равными единице, 11XXXXXX. Данные пишутся последовательно, начиная со старшего бита. Зачит, при двухбитной глубине цвета на то, будет ли байт маркером или нет, влияют пиксели по смещению 4×n. А именно, пиксели цвета под номером 3 (в нашем случае, темно-серый).

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

Порядок цветов в палитре мы определяем сами, поэтому выберем в качестве цвета номер 3 тот, который меньше всего встречается по смещению 4×n. Синий — лучший кандидат, он не встречается на таких местах вообще ни разу. Переопределяем палитру и делаем вторую попытку.

Сырые данные	Сжатые данные
0A 80 25 60 AA AA B7 78 2A A0	0A 80 25 60 AA AA B7 78 2A A0

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

Итого

Еще раз вкратце техники, помогающие уменьшить вес PCX:

• Выбор минимально возможной глубины цвета (размера палитры);
• Оптимизация мусорных данных;
• Удаление бессмысленных данных (серии длиной 0);
• Оптимизация палитры.

Продолжение следует

Ну вот, пожалуй, и всё. Про TGA я рассказывать не буду, он хоть и отличается от PCX, но сходств гораздо больше, чем отличий. А других прямо уж примечательных графических форматов того времени и не было.

Кроме, конечно же, формата GIF компании CompuServe. В нем мы и покопаемся в следующий раз.

Источник