Классический алгоритм Хаффмана

КОНСПЕКТ ЛЕКЦИЙ

По дисциплине «Компьютерная геометрия и графика»

Лекция 6

Тема 7 -  Форматы и стандарты компьютерной графики

Графические форматы

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

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

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

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

Рассмотрим наиболее распространенные форматы файлов растровой графики (табл.6.1).

Файлы с расширениями BMP, TIF, GIF, PCX и JPG содержат растровые графические изображения. Расширение в имени файла говорит о том, в каком формате хранится информация. Размещение информации в этих форматах отличается друг от друга как по содержанию, так и по структуре данных.

Формат файла BMP (сокращенно от BitMaP) - это формат растровой графики для операционной системы Windows, поскольку он наиболее близко соответствует внутреннему формату Windows, в котором эта система хранит свои растровые массивы. Для имени файла, представленного в BMP - формате, чаще всего используется расширение BMP, хотя некоторые файлы имеют расширение RLE, означающее run length encoding (кодирование длины серий). Расширение RLE имени файла обычно указывает на то, что произведено сжатие растровой информации файла одним из двух способов сжатия RLE, которые допустимы для файлов BMP - формата.

Таблица 6.1 Параметры форматов растровой графики

В файлах BMP информация о цвете каждого пиксела кодируется 1, 4, 8, 16 или 24 бит (бит/пиксел). Числом бит/пиксел, называемым также глубиной представления цвета, определяется максимальное число цветов в изображении. Изображение при глубине 1 бит/пиксел может иметь всего два цвета, а при глубине 24 бит/пиксел - более 16 млн. различных цветов.

Рассмотрим структуру файла BMP. В табл.1.2 показаны: последовательность, наименование и размер записываемой в файл информации.

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

Таблица 3.2 Размещение информации в файле BMP

Это описание пиксела не представляет значений цветов RGB, а служит указателем для входа в таблицу цветов файла.

Например, если в качестве первого значения цвета RGB в таблице цветов файла BMP хранится R/G/B=255/0/0, то значению пиксела 0 в растровом массиве будет поставлен в соответствие ярко-красный цвет.

Значения пикселов хранятся в порядке их расположения слева направо, начиная (как правило) с нижней строки изображения. Например, в 256-цветном BMP-файле первый байт данных растрового массива представляет собой индекс для цвета пиксела, находящегося в нижнем левом углу изображения; второй байт представляет индекс для цвета соседнего справа пиксела и т. д. Если число байт в каждой строке нечетно, то к каждой строке добавляется дополнительный байт, чтобы выровнять данные растрового массива по 16-бит границам.

Не все файлы BMP имеют одинаковую структуру. Например, файлы BMP с глубиной 16 и 24 бит/пиксел не имеют таблиц цветов; в этих файлах значения пикселов растрового массива непосредственно характеризуют значения цветов RGB. Также могут различаться внутренние форматы хранения отдельных разделов файла. Например, информация растрового массива в некоторых 16 и 256-цветных BMP-файлах может сжиматься посредством алгоритма RLE, который заменяет последовательности идентичных пикселов изображения на лексемы, определяющие число пикселов в последовательности и их цвет. В Windows допускается работа с BMP -файлами стиля OS/2, в которых используются различные форматы информационного заголовка растрового массива и таблицы цветов.

PCX стал первым стандартным форматом графических файлов для хранения файлов растровой графики в компьютерах IBM PC. На этот формат, применявшийся в программе Paintbrush фирмы ZSoft, в начале 80-х гг. фирмой Microsoft была приобретена лицензия, и затем он распространялся вместе с изделиями Microsoft. В дальнейшем формат был преобразован в Windows Paintbrush и начал распространяться с Windows. Хотя область применения этого популярного формата сокращается, файлы формата PCX, которые легко узнать по расширению PCX, все еще широко распространены сегодня.

Файлы PCX разделены на следующие три части: заголовок PCX, данные растрового массива и факультативная таблица цветов. 128-байт заголовок PCX содержит несколько полей, в том числе поля размера изображения и числа бит для кодирования информации о цвете каждого пиксела. Информация растрового массива сжимается с использованием простого метода сжатия RLE; факультативная таблица цветов в конце файла содержит 256 значений цветов RGB, определяющих цвета изображения. Формат PCX первоначально был разработан для адаптеров CGA- и EGA-дисплеев и в дальнейшем был модифицирован для использования в адаптерах VGA и адаптерах истинных цветов. Кодирование цвета каждого пиксела в современных изображениях PCX может производиться с глубиной 1, 4, 8 или 24 бит.

TIFF (Tagged Image File Format, формат файлов изображения, снабженных тегами) - один из самых сложных. Файлы TIFF имеют расширение TIFF. Каждый файл начинается 8-байт заголовком файла изображения (IFH), важнейший элемент которого - каталог файла изображения (Image File Directory, IFD) - служит указателем к структуре данных. IFD представляет собой таблицу для идентификации одной или нескольких порций данных переменной длины, называемых тегами; теги хранят информацию об изображении. В спецификации формата файлов TIFF определено более 70 различных типов тегов. Например, тег одного типа хранит информацию о ширине изображения в пикселах, другого - информацию о его высоте. В теге третьего типа хранится таблица цветов (при необходимости), а тег четвертого типа содержит сами данные растрового массива. Изображение, закодированное в файле TIFF, полностью определяется его тегами, и этот формат файла легко расширяется, поскольку для придания файлу дополнительных свойств достаточно лишь определить дополнительные типы тегов.

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

Формат файлов растровой графики GIF (Graphics Interchange Format - формат обмена графическими данными, разработан компанией CompuServe. Обычно для имени файлов GIF используется расширение GIF.

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

Формат файла JPEG (Joint Photographic Experts Group - Объединенная экспертная группа по фотографии) был разработан компанией C-Cube Microsystems как эффективный метод хранения изображений с большой глубиной цвета, например, получаемых при сканировании фотографий с многочисленными едва уловимыми (а иногда и неуловимыми) оттенками цвета. Самое большое отличие формата JPEG от других рассмотренных здесь форматов состоит в том, что в JPEG используется алгоритм сжатия с потерями и без потерь информации. Алгоритм сжатия без потерь так сохраняет информацию об изображении, что распакованное изображение в точности соответствует оригиналу. При сжатии с потерями приносится в жертву часть информации об изображении, чтобы достичь большего коэффициента сжатия. Распакованное изображение JPEG редко соответствует оригиналу абсолютно точно, но очень часто эти различия столь незначительны, что их едва можно (если вообще можно) обнаружить.

Compression of the maps

Существуют два вида сжатия изображений: без потерь (сжатие и восстановление изображений не меняет качество изображения) и с потерями (сжатие и восстановление изображений приводит к снижению качества изображения).

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

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

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

Алгоритм LZ

Существует довольно большое семейство LZ-подобных алгоритмов, различающихся, например, методом поиска повторяющихся цепочек. Один из достаточно простых вариантов этого алгоритма, например, предполагает, что во входном потоке идет либо пара (счетчик, смещение относительно текущей позиции), либо просто счетчик “пропускаемых” байт и сами значения байтов (как во втором варианте алгоритма RLE). При разархивации для пары (счетчик, смещение) копируются счетчик байт из выходного массива, полученного в результате разархивации, на смещение байт раньше, а счетчик (т.е. число равное счетчику) значений “пропускаемых” байт просто копируются в выходной массив из входного потока.

Данный алгоритм является несимметричным по времени, поскольку требует полного перебора буфера при поиске одинаковых подстрок. В результате сложно задать большой буфер из-за резкого возрастания времени компрессии. Однако потенциально построение алгоритма, в котором на счетчик и на смещение будет выделено по 2 байта (старший бит старшего байта счетчика — признак повтора строки / копирования потока), даст возможность сжимать все повторяющиеся подстроки размером до 32Кб в буфере размером 64Кб.

К достоинствам LZ можно отнести чрезвычайную простоту алгоритма декомпрессии.

Алгоритм LZW

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

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

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

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

Характеристики алгоритма LZW: Коэффициенты компрессии: Примерно 1000, 4, 5/7 (Лучший, средний, худший коэффициенты). Сжатие в 1000 раз достигается только на одноцветных изображениях размером кратным примерно 7 Мб.

Ориентирован LZW на 8-битные изображения, построенные на компьютере. Сжимает за счет одинаковых подцепочек в потоке.

LZW универсален — именно его варианты используются в обычных архиваторах.

Классический алгоритм Хаффмана

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

Этот алгоритм реализован в формате TIFF. Коэффициенты компрессии: лучший коэффициент стремится в пределе к 213, средний 2, в худшем случае увеличивает файл в 5 раз. Класс изображений: Двуцветные черно-белые изображения, в которых преобладают большие пространства, заполненные белым цветом. Симметричность: Близка к 1. Характерные особенности: Данный алгоритм чрезвычайно прост в реализации, быстр и может быть легко реализован аппаратно.

The graphic standards

Графический стандарт OpenGL (открытая графическая библиотека) был разработан и утвержден в 1992 году девятью ведущими фирмами мира, среди которых Digital Equipment Corporation, Evans & Sutherland, Hewlett-Packard Co., IBM Corp., Intel Corp., Intergraph Corp., Silicon Graphics Inc., Sun Microsystems Inc. and Microsoft Inc, разрабатывающих аппаратные и программные средства компьютерной графики.

В основу стандарта была положена библиотека IRIS GL, разработанная Silicon Graphics. Это достаточно простая в изучении и использовании графическая система (она включает в себя три библиотеки: Opengl 32.lib, qlu 32.ab и glaux.lib), обладающая при этом широкими возможностями.

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

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

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

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

Основные возможности, которые OpenGL предоставляет разработчикам таковы:

- Геометрические примитивы (точки, линии и многоугольники);

- Растровые примитивы (битовые массивы и прямоугольники пикселов);

- Работа с цветом;

- Видовые и модельные преобразования;

- Удаление невидимых линий и поверхностей;

- Прозрачность;

- Использование В-сплайнов для рисования линий и поверхностей;

- Наложение текстуры;

- Применение освещения;

- Использование плавного сопряжения цветов, устранения ступенчатости, «тумана» и других «атмосферных» эффектов;

- Использование списков изображений.

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