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

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

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

Метод назван по первым буквам фамилий разработчиков: 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.

Сжатие с потерями

Сжатие с потерями используется в телевизионной рекламе, компьютерных играх, анимации. Здесь некоторый аспект исходных данных теряется (отбрасывается). Отбрасывается то, что, например, по телевидению не воспринимается глазом. В основном отбрасывается информация о цветовых оттенках. В критичных приложениях, например, в медицине, метод не используется. Наиболее распространен алгоритм сжатия JPEG. Этот формат придуман Объединенной группой экспертов по фотографии (Joint Photographic Experts Group), файлы в DOS имеют расширение .jpg. Метод лучше всего работает с изображениями фотографического качества. Алгоритм начинается с разделения информации на цвет и яркость. Анализируются группы пикселов (например, квадраты 9х9 пикселов) и определяется разница между ними. Фиксируется информация не о пикселах как единицах изображения, а о динамике изменения их цвета и яркости. Для получения этой информации используется специальный математический аппарат. Сжатие с потерями приводит к тому, что резкие линии выглядят слегка размытыми, в областях однотонной окраски появляются переливы. Т.к. эти эффекты присутствуют и на реальных фотографиях, указанный эффект не заметен. Размеры сжатого файла могут составлять менее 5% исходного.

40. Основные графические форматы, их сравнительный анализ и область применения.

Можно насчитать около 50 различных графических форматов. Рассмотрим только наиболее известные.

PCX

Формат растровый, один из самых старых и распространенных, хотя и не признанный в качестве официального стандарта. Первоначально использовался в программе Paintbrush фирмы Zsoft. Расширение в DOS - *.pcx. Поддерживается почти всеми программами растровой графики. Имеет много версий (около 5). Поэтому современная версия для 24-разрядного цветового режима не воспринимается старыми программами. Существуют версии для 1-2-4-8-24-битового цвета. Изображения могут быть монохромными, с палитрами цветов или с полными 24-битовыми цветами RGB. Оттенки серого не воспроизводятся, шкалы для отображения оттенков серого в формате нет. Формат аппаратно зависим (EGA, VGA). В основном новые версии выпускались в связи с появлением новых адаптеров. Используется сжатие методом RLE (групповое сжатие). За счет этого размер файла уменьшается на 40-70% для 16 и менее цветов, на 10-30% для 256 цветов. Сжатие используется всегда.

Файл формата PCX содержит 3 части: заголовок, растровые данные и (в более поздних версиях) палитру с количеством цветов до 256. В заголовке 128 байт. Там записаны номер версии, информация о разрешении (в dpi) отпечатанного или отсканированного изображения, информация о размерах (в пикселах), числе байтов на строку развертки, количестве битов на пиксел и количестве цветовых плоскостей. В заголовке может быть информация о наличии палитры и код, указывающий на то, какая палитра используется. В ранних версиях для 4-и 16-цветных изображений информация о палитре была в заголовке. Это порождает несовместимость.

Формат целесообразно применять для нефотореалистических изображений (фотореалистические изображения плохо сжимаются). Основное достоинство - широкая распространенность. Ограничения и недостатки:

· цветовая палитра до 256 цветов;

· не поддерживаются изображения с оттенками серого;

· не поддерживаются цвета CMYK и другие системы цветов, отличные от RGB;

· размер изображения до 64000 64000 пикселов;

· многообразие вариантов порождает проблемы считывания (воспроизведения);

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

· формат поддерживается только на PC-платформе, не поддерживается на Macintosh и в UNIX. Это самый распространенный PC-формат.

GIF

Формат растровый. GIF - Graphics Image Format. Он был предложен для сети Compuserve, по которой обмениваются различной информацией, в том числе в большом объеме - графическими файлами. Расширение для DOS - *.gif. Понимается почти всеми растровыми редакторами, большинством издательских пакетов, векторными редакторами, поддерживающими растровые объекты. Для сжатия используется алгоритм LZW.

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

Файл формата GIF состоит из последовательности блоков. Блок заголовка (6 байт) хранит тип файла (GIF) и версию (87а или 89а). Блок дескриптора логического экрана (LSD - logical screen device) описывает область устройства (дисплей или принтер) для вывода следующего за ним изображения (или изображений - файлы GIF могут хранить несколько изображений, идущих последовательно как слайды). Указывается в пикселах ширина и высота логического экрана для вывода изображений, цвет фона (цвет логического экрана), будет ли для вывода изображения использована глобальная (единая для всех изображений) таблица цветов, коэффициент прямоугольности (ширина и высота) пикселов начального изображения. Блок дескриптора изображения задает размеры изображения и его позицию на логическом экране (относительно левого верхнего угла) и информирует, будет ли использоваться локальная таблица цветов. Таких блоков может быть 1 или более. Файл содержит по крайней мере 1 таблицу цветов. Она может быть глобальной (единственной) и/или локальной (несколько таблиц). После всей служебной информации следует сжатый методом LZW блок данных изображения. Завершает файл блок концевика, который носит только индикаторный характер. Последняя версия (89а) имеет расширения, позволяющие добавлять к рисунку текст аннотации. Причем можно сделать аннотацию как отображаемую на экране, так и не отображаемую. Этот блок размещается (если он есть) перед данными.

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

· 24-битный цвет поддерживает только до 256 цветов;

· отсутствует возможность сохранения градаций серого;

· не поддерживается система цветов CMYK;

· размер изображения - до 64К 64К пикселов.

TIFF

Формат растровый. TIFF (Tagged Image File Format) дословно переводится как формат файла помеченного изображения. Формат является результатом объединения усилий компаний Aldus и Microsoft, направленных на преодоление трудностей переноса графических файлов между IBM-совместимыми компьютерами и Macintosh. Формат работает также в UNIX-системах. Появление TIFF положило также конец некоторому беспорядку в области программного обеспечения для сканеров.

Существует 5 типов TIFF-файлов: B - черно-белые иллюстрации, F - изображения для факсов, G - полутоновые изображения (каждая точка может быть любой степени серого от 0% - белый цвет, до 100% - черный), P - цветные изображения, использующие собственную цветовую палитру, R - фотореалистические изображения в RGB-представлении. Имеются "диалекты" формата, что создает трудности его понимания различными программами. Сейчас используются версии 5.0 и 6.0. Расширение для DOS - *.tif.

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

Формат очень удобен, но файлы велики. Например, файл формата А4 в цветовой модели CMYK (собственная цветовая палитра!) с разрешением 300 dpi занимает около 40 М. А это обычные параметры высококачественной печати. Достоинством являются надежность, большие возможности. Это лучший растровый формат обмена между Macintosh и PC. С той или иной степенью детализации он "понимается" множеством программ. Можно использовать различные методы сжатия. Метод сжатия указывается в одном из полей. Можно работать с оттенками серого. Универсальность формата порождает его основной недостаток: неупорядоченность структуры и вытекающую из этого несовместимость.

JPEG

Joint Photographic Expert Group (JPEG) - формат объединенной группы экспертов по фотографии. Это объединение действует под эгидой ISO (ведущей международной организации стандартов) и CCITT (организации стандартов в области телефонии, радио, телевидения и т.д.). Формат дает наилучшее сжатие для фотографических (растровых) изображений. Расширение для DOS - *.jpg или *.jif (JPEG+TIFF). Последняя версия - 1991 г. Формат еще не устоялся, есть ранние, не совместимые с другими реализации. JPEG “понимается” рядом графических редакторов. Это не столько формат, сколько метод сжатия. Он реализован программно на PC, Macintosh и аппаратно (это наиболее эффективно, есть специальные чипы). Программное сжатие работает гораздо медленнее аппаратного. Возможно сжатие до десятых долей исходного файла (до 100:1). Такой результат получается за счет сжатия с потерями. Но теряется то, что для глаза незаметно. Существует формат JPEG+TIFF (TIFF 6.0), допускающий сжатие JPEG. Имеется также формат JFIF. Это вариации JPEG.

Рассмотрим основные этапы сжатия. Большинство реализаций JPEG сначала преобразуют систему цветов RGB в YUV (Y - яркость, U и V - характеристики цвета). Т.к. человеческий глаз больше воспринимает изменение яркости, нежели изменение цвета, программа сжатия больше внимания уделяет данным о яркости. На одну выборку цвета делается от 2 до 4 выборок яркости. Это источник экономии. Далее выполняется дискретное преобразование массива данных об интенсивности в массив данных о частоте изменения интенсивности. После ряда частотных преобразований используется модифицированное кодирование методом Хаффмана.

DXF

DXF - Drawing Interchange Format. Это формат обмена рисунками AutoCAD фирмы AutoDesk. Формат векторный. “Понимается” большинством САПР, Corel Draw, издательскими системами. Стандарт "де факто" для обмена чертежами. Позволяет отобразить от черно-белого до 16 млн. цветов. В основном для PC, есть реализации на Macintosh, UNIX. Основа - язык графических метафайлов. Это означает, что хранится не само изображение, а его описание. AutoCAD использует плавающую арифметику. Это позволяет выполнять очень точные вычисления. Но большинство векторных редакторов применяет только целочисленную арифметику. Это порождает потерю информации, искажение рисунка. Степень искажения зависит от вида работы.

Формат имеет 2 формы: ASCII и бинарную. Бинарная форма появилась в версии 10. Цифровые коды и данные хранятся не в ASCII, а в двоичном виде. При этом размер файла уменьшается примерно на 25%, скорость чтения увеличивается в 5 раз, но теряется возможность визуальной расшифровки формата.

Объекты в файле DXF задаются парами величин: кодами групп и следующими за ними значениями групп. Коды указывают цель использования значений. Данные внутри файла разделены на 4 секции. Секция заголовка содержит общую информацию: цвет, толщина линий по умолчанию, размеры рисунка и т.д. Эти сведения обычно игнорируются системами, отличными от САПР (векторными редакторами, издательскими системами и др.). Секция таблиц содержит данные о координатных системах и слоях объектов. Они тоже, в основном, используются САПР. В секции блоков векторные объекты группируются по именам. Секция элементов содержит описания всех геометрических объектов. Это самая большая часть файла. Примеры элементов: POINT, LINE, CIRCLE, 3DFACE, TEXT и др. Описываются объекты числовыми и ASCII или двоичными кодами. Сначала указывается код элемента, потом код слоя, цвет и др. характеристики, затем - параметры элемента.

Достоинства: распространенность, широкая цветовая палитра, возможность описания трехмерных изображений. Недостатки: неэффективность хранения данных, ASCII-форма медленно читается. Полная реализация стандарта очень сложна, особенно для трехмерных изображений.

Поиск по сайту: