Смысл метода Хаффмана заключается в замене данных более эффективными кода­ми. Более короткие коды используются для замены более часто появляющихся вели­чии. Например в выражении abbbeceddeeeeeeeeef есть шесть уникальных величин, с частотами появления: а:1, b:3, c:3, d:2, e:9, f:l. Для образования минимального кода используется двоичное дерево. Алгоритм объединяет в пары элементы, появляющиеся наименее часто, затем пара объединяется в один элемент, а их частоты объединяются. Это действие повторяется до тех пор, пока элементы не объединятся в пары. В данном примере надо объединить а и f – это первая пара, а присваивается нулевая ветвь, a f – 1-я. Это означает, что 0 и 1 будут младшими битами кодов для а и f соответственно. Более старшие биты будут получены из дерена по мере его построения.

Суммирование частот дает в итоге 2. Теперь самая низкая частота – 2, поэтому пара а и f, объединяется с d (которая тоже имеет частоту 2). Исходной паре присваиваеся нулевая ветвь, а d – ветвь 1. Таким образом, код для а заканчивается на 00; для f на 01, d заканчивается на 1 и будет на один бит короче по сравнению с кодами для а и f.

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

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

Алгоритм сжатия JPEG(JointPhotographicExpertsGroup) (читается ['jei'peg]) позволяет регулировать соотношение между степенью сжатия файла и качеством изображения. Применя­емые методы сжатия основаны на удалении «избыточной» информации.

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

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

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

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

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

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

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

Форматы графических файлов

В компьютерной графике применяют по меньшей мере три десятка форматов файлов для хранения изображений. Но лишь часть из них стала стандартом «де-факто» и применяется в подавляющем большинстве программ.

Краткая информация об основных графических форматах файлов приведена в таблице.

Типы графических файлов