Обзор графических форматов

      Файлы с расширениями BMP, PCX, GIF, TIF и JPG содержат растровые графические изображения. Расширение в имени файла говорит о том, в каком формате хранится информация. Например, расширение BMP обозначает BMP-файл, поддерживаемый в системах Windows и OS/2 (BMP - сокращение от bitmap, т.е. битовый, растровый); TIF - сокращение от TIFF или Tagged Image File Format. Это только два представителя большого семейства форматов, используемых на персональных компьютерах.

      Каждый из этих форматов по-разному хранит графическую информацию, и каждый из них разрабатывался под конкретные цели. Формат GIF (Graphics Interchange File - файл графического обмена), например, был придуман для того, чтобы уместить как можно больше информации в ограниченном пространстве с целью уменьшить время получения файлов для пользователей сети CompuServe. Формат PCX изначально был придуман для хранения черно-белых графических файлов, создаваемых ранней версией программы раскраски PC Paintbrush для компьютеров IBM PC. Сейчас формат PCX применим и для цветных графических файлов.
 

      Растровый графический файл обычно содержит информацию двух видов: графическую и неграфическую. В графических данных указываются цвета пикселей, неграфические данные содержат другую информацию, необходимую для восстановления изображения, например, его высоту и ширину. (Если изображение содержит 1 миллион пикселей, то как графической программе узнать размеры: рисовать ли ей изображение 500 на 2000 или 1000 на 1000 пикселей?) Неграфическая часть файла может также включать другую информацию, такую как номер версии или сведения об авторских правах. Все зависит от формата и от того, кто (или какой программный пакет) создал этот файл.

      В растровых файлах используется обычно один из двух методов хранения данных о пикселях. В полноцветных изображениях пиксель может принимать любое из более чем 16 миллионов значений, поэтому и цвет пикселя хранится обычно как 24-разрядное значение - по 8 битов на красную, зеленую и синюю компоненты цвета. Если изображение содержит 1 миллион пикселей, то размер файла будет равен 3 миллионам байтов плюс длина неграфических данных. Если же изображение ограничено 256 или менее цветами, то цветовая информация обычно кодируется с использованием палитры. Вместо того чтобы хранить значение цвета пикселя, информация о пикселе указывает на строку в палитре, а она, в свою очередь, содержит цвет. С уменьшением количества битов, требуемых для представления цвета пикселя, уменьшается размер файла (а это во все времена ценное приобретение, поскольку пространство памяти не бывает бесплатным).

      В качестве примера возьмем изображение из миллиона пикселей, содержащее 256 различных цветов. Кодирование цвета каждого пикселя 24-битным значением приводит к расточительной избыточности, потому что некоторые (а возможно и все) из 256-ти цветов повторяются неоднократно. Для хранения используемых цветов лучше выделить в файле 768 байтов под цветовую палитру: 256 полей по 24 бита, каждое поле содержит один из цветов, встречающихся в изображении. Тогда под значение цвета пикселя можно отвести 8 битов, то есть целое число в диапазоне от 0 до 255, указывающее номер цвета в палитре. Теперь для графической части файла достаточно 1.000.768 байтов, против прежних 3.000.000 байтов, которые требуются для хранения этого изображения без использования палитры. И даже с учетом дополнительных байтов из неграфической части файла, мы все-таки получаем уменьшение размера файла почти на две трети.

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

      В каждом формате графические и неграфические данные структурируются по-своему. Избегая обобщений, рассмотрим поближе один из форматов - BMP-формат, широко использующийся в системах Windows и OS/2. В частности, мы рассмотрим BMP-файл, описывающий 256-цветное изображение размером 1000 на 1000 пикселей. (Формат BMP-файла немного различается в зависимости от того, сколько цветов содержит изображение - 2, 16, 256 или 16,7 млн. Форматы BMP в Windows и OS/2 также немного отличаются.) Описание этого файла будет соответствовать варианту BMP для Windows. Файл состоит из четырех основных частей: 14-байтного заголовка файла, 40-байтного информационного заголовка, 1024-байтной цветовой таблицы и миллиона байтов для значений пикселей. (Под цветовую таблицу отводится 1024 байта, а не 768, поскольку в каждое 24-битовое поле таблицы добавлен еще один, неиспользуемый байт.)

      Первые 14 байтов BMP-файла составляют его заголовок. Заголовок файла содержит три значения: буквы BM, которые говорят о том, что графический файл имеет BMP формат, число, означающее размер файла и число, указывающее на то, где находятся растровые данные. Последнее число равно количеству байтов от начала файла. Еще два поля в заголовке файла зарезервированы для будущих нужд и обычно содержат нули.

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

      Цветовая таблица содержит 256 полей по 4 байта. Первый байт в каждом поле отвечает за синюю компоненту цвета, второй за зеленую и третий - за красную. Четвертый байт не используется и обычно устанавливается в 0. Если первые три значения в цветовой таблице -0, 192 и 192, это значит, что нулевой номер соответствует желтому цвету средней интенсивности (смесь зеленого и красного). В цветовой таблице определены все цвета, использующиеся в изображении.

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

      Вывод на экран картинки, хранящейся в BMP-файле, начинается с чтения заголовка файла и информационного заголовка. Программа, таким образом, узнает размеры изображения и количество цветов.

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

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

      Беда растровых файлов в том, что они большие, даже очень большие. Если пренебречь заголовками файла и другими неграфическими данными, его размер пропорционален количеству пикселей в изображении и количеству битов, требуемых для представления каждого пикселя. Полноцветная картинка размером 1024х768 пикселей занимает более двух мегабайт памяти, а одна секунда видеофильма телевизионного качества в растровом виде съедает около тридцати мегабайт. Поэтому жесткий диск можно заполнить мгновенно. Даже компакт-диск, который вмещает около 700 мегабайт данных, не столь велик, чтобы совладать с графическими монстрами, если не попытаться уменьшить их объем.

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

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

      Далее мы рассмотрим следующие распространенные алгоритмы сжатия изображений: 

Алгоритм архивации без потерь RLE

      Существует два варианта алгоритма. Сначала рассмотрим первый вариант.

      Данный алгоритм необычайно прост в реализации. Групповое кодирование (от английского Run Length Encoding (RLE)) - один из самых старых и самых простых алгоритмов архивации графики. Изображение в нем вытягивается в цепочку байт по строкам растра. Само сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Замена их на пары <счетчик повторений, значение> уменьшает избыточность данных.

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

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

      Данный алгоритм реализован в формате PCX.

      Теперь рассмотрим второй вариант алгоритма.

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

      Признаком повтора в данном алгоритме является единица в старшем разряде соответствующего байта.

      Как можно легко подсчитать, в лучшем случае этот алгоритм сжимает файл в 64 раза (а не в 32 раза, как в предыдущем варианте), в худшем увеличивает на 1/128. Средние показатели степени компрессии данного алгоритма находятся на уровне показателей первого варианта.

      Похожая схема компрессии использована в качестве одного из алгоритмов, поддерживаемых форматом TIFF, а также в формате TGA.
 

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

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

      На практике для хранения таблицы используется хэш-таблица. Таблица состоит из 8192 (2¹³) элементов. Каждый элемент содержит <код предыдущей подстроки; добавленный символ; код этой строки>. Ключ для поиска длиной в 20 бит формируется с использованием двух первых элементов, хранимых в таблице как одно число (key). Младшие 12 бит этого числа отданы под код, а следующие 8 бит под значение символа.

      В качестве хэш-функции при этом используется:
 

      Где >> - побитовый сдвиг вправо (key >> 12 - мы получаем значение символа), ^ - логическая операция побитового исключающего ИЛИ, & - логическое побитовое И.

      Таким образом, за считанное количество сравнений, мы получаем искомый код или сообщение, что такого кода в таблице нет.

      Лучший коэффициент, очевидно, будет получен для цепочки одинаковых байт большой длины (т.е. для 8-битного изображения, все точки которого имеют, для определенности, цвет 0). При этом в 258 строку таблицы мы запишем строку "0, 0", в 259 - "0, 0, 0", ... в 4095 - строку из 3809 (=4095-256) нулей. При этом в поток попадет 3810 кодов, включая код очистки. Следовательно, посчитав сумму арифметической прогрессии от 1 до 3809 (т.е. длину сжатой цепочки) и поделив ее на 3810*12/8 (в поток записываются 12-битные коды), мы получим лучший коэффициент компрессии.

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

      LZW реализован в форматах GIF и TIFF.
 

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

      На практике используются его разновидности. Так, в некоторых случаях резонно либо использовать постоянную таблицу, либо строить ее "адаптивно", т.е. в процессе архивации/разархивации. Эти приемы избавляют нас от двух проходов по изображению и необходимости хранения таблицы вместе с файлом. Кодирование с фиксированной таблицей применяется в качестве последнего этапа архивации в JPEG и в некоторых других алгоритмах.
 

      Алгоритм разработан группой экспертов ISO (Joint Bi-level Experts Group) специально для сжатия однобитных черно-белых изображений. Например, факсов или отсканированных документов. В принципе может применяться и к 2-х, и к 4-хбитовым картинкам. При этом алгоритм разбивает их на отдельные битовые плоскости. JBIG позволяет управлять такими параметрами, как порядок разбиения изображения на битовые плоскости, ширина полос в изображении, уровни масштабирования. Последняя возможность позволяет легко ориентироваться в базе больших по размерам изображений, просматривая сначала их уменьшенные копии. Настраивая эти параметры, можно использовать описанный выше эффект "огрубленного изображения" при получении изображения по сети или по любому другому каналу, пропускная способность которого мала по сравнению с возможностями процессора. Распаковываться изображение на экране будет постепенно, как бы медленно "проявляясь". При этом человек начинает анализировать картинку задолго до конца процесса разархивации.

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

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

      Алгоритм разработан группой экспертов в области фотографии специально для сжатия 24-битных изображений. JPEG - Joint Photographic Expert Group - подразделение в рамках ISO - Международной организации по стандартизации. Название алгоритма читается ['jei'peg]. В целом алгоритм основан на дискретном косинусоидальном преобразовании (в дальнейшем ДКП), применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов. Для получения исходного изображения применяется обратное преобразование.

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

      Для этого используется квантование коэффициентов (quantization). В самом простом случае - это арифметический побитовый сдвиг вправо. При этом преобразовании теряется часть информации, но могут достигаться большие коэффициенты сжатия.

      Существенными положительными сторонами алгоритма является то, что:

1) Задается степень сжатия.

2) Выходное цветное изображение может иметь 24 бита на точку.

      Отрицательными сторонами алгоритма является то, что:

1) При повышении степени сжатия изображение распадается на отдельные квадраты (8x8). Это связано с тем, что происходят большие потери в низких частотах при квантовании, и восстановить исходные данные становится невозможно.

2) Проявляется эффект Гиббса - ореолы по границам резких переходов цветов.

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

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

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

      Несколько слов необходимо сказать о модификациях этого алгоритма. Хотя JPEG и является стандартом ISO, формат его файлов не был зафиксирован. Пользуясь этим, производители используют свои, несовместимые между собой форматы, и, следовательно, могут изменить алгоритм. Так, внутренние таблицы алгоритма, рекомендованные ISO, заменяются ими на свои собственные. Кроме того, легкая неразбериха присутствует при задании степени потерь. Например, при тестировании выясняется, что "отличное" качество, "100%" и "10 баллов" дают существенно различающиеся картинки. При этом, кстати, "100%" качества не означает сжатие без потерь. Встречаются также варианты JPEG для специфических приложений.

      Как стандарт ISO JPEG начинает все шире использоваться при обмене изображениями в компьютерных сетях. Поддерживается алгоритм JPEG в форматах Quick Time, PostScript Level 2, Tiff 6.0 и на данный момент занимает видное место в системах мультимедиа.
 

      Фрактальная архивация основана на том, что мы представляем изображение в более компактной форме - с помощью коэффициентов системы итерируемых функций (Iterated Function System - далее по тексту как IFS). Строго говоря, IFS представляет собой набор трехмерных аффинных преобразований, в нашем случае переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (х_координата, у_координата, яркость).

      Наиболее наглядно этот процесс продемонстрировал Барнсли в своей книге "Fractal Image Compression". Там введено понятие Фотокопировальной Машины, состоящей из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран:

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

Области, в которые проецируются изображения, не пересекаются.

Линза может менять яркость и уменьшать контрастность.

Линза может зеркально отражать и поворачивать свой фрагмент изображения.

Линза должна (масштабировать) уменьшать свой фрагмент изображения.

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

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

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

      Английское название рекурсивного сжатия - wavelet. На русский оно также переводится как волновое сжатие, и как сжатие с использованием всплесков. Этот вид архивации известен довольно давно и напрямую исходит из идеи использования когерентности областей. Ориентирован алгоритм на цветные и черно-белые изображения с плавными переходами. Идеален для картинок типа рентгеновских снимков. Коэффициент сжатия задается и варьируется в пределах 5 - 100 раз. При попытке задать больший коэффициент, на резких границах, особенно проходящих по диагонали, проявляется "лестничный эффект" - ступеньки разной яркости, размером в несколько пикселей.

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

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

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