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

Размещено на http://www.allbest.ru/

ОГЛАВЛЕНИЕ

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

2. Сжатие информации

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

3.1 Алгоритм RLE

3.2 Алгоритм LZW

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

3.4 Алгоритм Хаффмана с фиксированной таблицей CCITT GROUP 3

3.5 Алгоритм сжатия Шеннона - Фано

3.6 Алгоритм JBEG

3.7 Заключение

4. Алгоритмы архивации с потерями

4.1 Алгоритм JPEG

4.2 Фрактальный алгоритм

4.3 Рекурсивный (волновой) алгоритм

Заключение

Приложение

Литература

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

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

Способы кодирования графической информации

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

· В растровой (пиксельной) графике (bitmaped images, scanned images, raster images) базовым элементом изображения является точка. Изображение представляет собой совокупность дискретных элементов, которые различаются только цветом (тоном) и взаимным расположением. Для растровых изображений особую важность имеет понятие разрешения, выражающее количество точек, приходящихся на единицу длины. Одним из недостатков растровой графики является пикселизация изображений при их увеличении.

· В векторной графике (vector drawing, vector illustration) базовым элементом изображения является - линия. Линия описывается математически как единый объект, и поэтому объем данных для отображения объекта средствами векторной графики существенно меньше, чем растровой. Изображение представляет собой линейно-контурное изображение, которое состоит из независимого описания границ векторных объектов и их заполнения ("заливок").

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

2. Сжатие информации

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

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

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

Сжатие без потерь

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

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

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

3.1 Алгоритм RLE

Первый вариант алгоритма

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

В данном алгоритме признаком счетчика (counter) служат единицы в двух верхних битах считанного файла:

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

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

Второй вариант алгоритма

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

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

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

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

Характеристики алгоритма RLE:

Коэффициенты компрессии: Первый вариант: 32, 2, 0,5.

Второй вариант: 64. 3. 128/129. (Лучший, средний, худший коэффициенты)

Класс изображений: Ориентирован алгоритм на изображения с небольшим количеством цветов: деловую и научную графику.

Симметричность: Примерно единица.

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

3.2 Алгоритм LZW

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

Алгоритм LZ

Существует довольно большое семейство LZ-подобных алгоритмов, различающихся, например, методом поиска повторяющихся цепочек. Один из достаточно простых вариантов этого алгоритма, например, предполагает, что во входной потоке идет либо пара <счетчик, смещение относительно текущей позиции>, либо просто <счетчик> "пропускаемых” байт b сами значения байтов (как во втором варианте алгоритма RLE). При paзapxивации для пары <счетчик, смещение> копируются <счетчик> байт из выходного массива, полученного в результате разархивации на <смешение> байт раньше, а <счетчик> значений "пропускаемых" байт просто копируются в выходной массив из входного потока. Данный алгоритм является несимметричным по времени, поскольку требует полного перебора буфера при поиске одинаковых подстрок. В результате сложно задать большой буфер из-за резкого возрастания времени компрессии. Однако потенциально построение алгоритма, в котором на <счетчик> и на <смещение> будет выделено по 2 байта (старший бит старшего байта счетчика признак - повтора строки / копирования потока) даст нам возможность сжимать все повторяющиеся подстроки размером до 32Кб в буфере размером 64Кб.

При этом мы получим увеличение размера файла в худшем случае на 32770 / 32768 (в двух байтах записано, что нужно переписать в выходной поток следующие 2 байт), что совсем неплохо. Максимальный коэффициент сжатия составит в пределе 8192 pазa. В пределе, поскольку максимальное сжатие мы получаем превращая 32Кб буфера в 4 байта, а буфер такого размера мы накопим не сразу. Однако, минимальная подстрока, для которой нам выгодно проводить сжатие должна состоять в общем случае минимум из 5 байт, что и определяет малую ценность данного алгоритма. К достоинствам LZ можно отнести чрезвычайную простоту алгоритма декомпрессии.

Алгоритм LZW

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

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

Пример:

Пусть мы сжимаем последовательность 45. 55. 55. 151. 55. 55. 55. Тогда, согласно изложенному выше алгоритму, помещаем в выходной поток сначала код очистки <256>, потом добавим к изначально пустой строке "45" и проверим, есть ли строка "45" в таблице. Поскольку при инициализации занесли в таблицу все строки из одного символа, то строка "45" есть в таблице. Далее: читаем следующий символ 55 из входного потока и проверяем, есть ли строка "45, 55" в таблице. Такой строки в таблице пока нет -> заносим в таблицу строку "45, 55" (с первым свободным кодом 258) и записываем в поток код < 45>. Можно коротко представить архивацию так

"45"" -- есть в таблице:

"45. 55" -- нет. Добавляем в таблицу <258>"45. 55" В поток<45>:

"55.55" -- нет. В таблицу <259>"55. 55" В поток: <55>.

"55.151" -- нет. В таблицу: <260>”55. 151". В поток: <55>;

"151. 55" --нет В таблицу: <261>”151.55". В поток: <151>;

"55. 55" -- сеть в таблице:

"55. 55. 55" -- нет. В таблицу: "55. 55. 55" <262>. В поток: <259>;

Последовательность кодов для данного примера, попадающих в выходной поток: <256>. <45>. <55>. <55>. <151>. <259>.

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

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

Код этой строки добавляется в таблицу.

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

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

Характеристики алгоритма LZW:

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

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

Симметричность: Почти симметричен, при условии оптимальной реализации операции поиска строки в таблице.

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

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

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

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

Рис. 1. Кодовое дерево Хаффмана

Средняя длина кодового слова вычисляется как взвешенная вероятностная сумма длин всех кодовых слов:

L_cp = p₁L₁ + p₂L₂ + ... + p_nL_n,

где p₁,..., p_n -- вероятности кодовых слов;
L₁,..., L_n -- длины кодовых слов.

Клод Шеннон в 40-х годах XX века в своей «Математической теории связи» показал, что средняя длина кодового слова не может быть меньше, чем энтропия множества кодируемых элементов, которая вычисляется по формуле:

Н = p₁log(1/p₁) + p₂log(l/p₂) + ... + p_nlog(l/ p_n)

Средняя длина кодового слова, обеспечиваемая кодом Хаффмана, приближается к энтропии при очень больших объемах сообщений. При этом длина кодового слова, имеющего вероятность р, приближается к log (l/p). В случае кодирования двоичными символами основание логарифмов в приведенных выше формулах равно 2.

Если не учитывать вероятности (т. е. считать их равными), то для кодирования n элементов с помощью нулей и единиц потребуется log(n) битов на каждый элемент. Точнее говоря, в качестве длины слова следует взять ближайшее большее целое для этого числа. Так, например, для кодирования 6 элементов потребуются слова длиной 3 (log(6) = 2,585). При этом все слова будут иметь одинаковую длину. Если же учесть вероятности, то для рассмотренного выше примера средняя длина кодового слова будет равна 2,5 (0,5x2 + 0,5x3). При кодировании достаточно больших сообщений это дает экономию около 17%.

Код Хаффмана реализует обратимое и максимальное сжатие данных (обратимость означает, что имеется возможность полного восстановления исходного сообщения). Максимальность сжатия понимается в следующем смысле. Если источник сообщений генерирует символы с фиксированным распределением вероятностей, то при кодировании сообщений, длина которых стремится к бесконечности, достигается средняя длина кодового слова, равная энтропии. Следует заметить, что для одного и того же распределения вероятностей можно построить, вообще говоря, несколько кодов Хаффмана, но все они дают одинаковые результаты.

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

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

таблицей применяется в качестве последнего этапа архивации в JPEG и в алгоритме CCITT Group 3.

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

Коэффициенты компрессии: 8, 1.5, 1 (Лучший, средний, худший коэффициенты)

Класс изображений: Практически не применяется к изображениям в чистом виде. Обычно используется как один из этапов компрессии в более сложных схемах.

Симметричность: 2 (за счет того, что требует двух проходов по массиву сжимаемых данных).

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

3.4 Алгоритм Хаффмана с фиксированной таблицей CCITT Group 3

Близкая модификация алгоритма используется при сжатии черно-белых изображений (один бит на пиксель). Полное название данного алгоритма CCITT Group 3. Это означает, что данный алгоритм был предложен третьей группой по стандартизации Международного Консультационного Комитета по Телеграфии и Телефону (Consultative Committee International Telegraph and Telephone). Последовательности подряд идущих черных и белых точек в нем заменяются числом, равным их количеству. А этот ряд уже, в свою очередь, сжимается по Хаффману с фиксированной таблицей.

Определение: Набор идущих подряд точек изображения одного цвета называется серией. Длина этого набора точек называется длиной серии.

В таблице приведенной ниже заданы два вида кодов:

Коды завершения серий - заданы с 0 до 63 с шагом 1.

Составные (дополнительные) коды - заданы с 64 до 2560 с шагом 64.

Каждая строка изображения сжимается независимо. Считаем, что в изображении существенно преобладает белый цвет, и все строки изображения начинаются с белой точки. Если строка начинается с черной точки, то считаем, что строка начинается белой серией длины 0. Например, последовательность длин серий 0, 3, 556, 10, ... означает, что в этой строке изображения идут сначала 3 черных точки, затем 556 белых, затем 10 черных и т.д.

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

Поскольку черные и белые серии чередуются, то реально код для белой и код для черной серии будут работать попеременно.

В терминах регулярных выражений мы получим для каждой строки нашего изображения (достаточно длинной, начинающейся с белой точки) выходной битовый поток вида:

((<Б-2560>)*[<Б-сст.>]<Б-зв.>(<Ч-2560>)*[<Ч-сст.>]<Ч-зв.>)⁺

[(<Б-2560>)*[<Б-сст.>]<Б-зв.>]

Где ()* - повтор 0 или более раз. ()⁺- повтор 1 или более раз. [] - включение 1 или 0 раз.

Для приведенного ранее примера: 0, 3, 556. 10... алгоритм сформирует следующий код:

<Б-0><Ч-3><Б-512><Б-44><Ч-10>. или, согласно таблице, 00110101 10 01100101 00101101 0000100 (разные коды в потоке выделены для удобства). Этот код обладает свойством префиксных кодов и легко может быть свернут обратно в последовательность длин серий. Легко подсчитать, что для приведенной строки в 569 бит получили код, длиной в 33 бита, т.е. коэффициент сжатия составляет примерно 17 раз.

Этот алгоритм реализован в формате TIFF.

Характеристики алгоритма CCITT Group 3

Коэффициенты компрессии: лучший коэффициент стремится в пределе к 213.(3), средний 2, в худшем случае увеличивает файл в 5 раз.

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

Характерные особенности: Данный алгоритм чрезвычайно прост в реализации, быстр и может быть легко реализован аппаратно.

3.5 Алгоритм сжатия -- Шеннона-Фано

Алгоритм сжатия -- Шеннона-Фано, основан на тех же идеях, но не гарантирует максимального сжатия, как алгоритм Хаффмана. Код Шеннона-Фано строится с помощью дерева. Однако построение этого дерева начинается от корня. Все множество кодируемых элементов соответствует корню дерева (вершине первого уровня). Оно разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Эти подмножества соответствуют двум вершинам второго уровня, которые соединяются с корнем. Далее каждое из этих подмножеств разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Им соответствуют вершины третьего уровня. Если подмножество содержит единственный элемент, то ему соответствует концевая вершина кодового дерева; такое подмножество разбиению не подлежит. Подобным образом поступаем до тех пор, пока не получим все концевые вершины. Ветви кодового дерева размечаем символами 1 и 0, как в случае кода Хаффмана.



Рис. 2. Кодовое дерево Шеннона-Фано

При построении кода Шеннона-Фано разбиение множества элементов может быть произведено, несколькими способами. Выбор разбиения на уровне n может ухудшить варианты разбиения на следующем уровне (n+1) и привести к неоптимальности кода в целом. Другими словами, оптимальное поведение на каждом шаге пути еще не гарантирует оптимальности всей совокупности действий. Поэтому код Шеннона-Фано не является оптимальным в общем смысле, хотя и дает оптимальные результаты при некоторых распределениях вероятностей. Для одного и того же распределения вероятностей можно построить, несколько кодов Шеннона-Фано, и все они могут дать различные результаты. Если построить все возможные коды Шеннона-Фано для данного распределения вероятностей, то среди них будут находиться и все коды Хаффмана, т. е. оптимальные коды.

3.6 Алгоритм JBIG

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

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

Lossless JPEG

Этот алгоритм, разработан группой экспертов в области фотографии (Joint Photographic Expert Group). В отличие от JBIG, Lossless JPEG ориентирован на полноцветные 24-битные или 8-битные в градациях серого изображения без палитры. Он представляет собой специальную реализацию JPEG без потерь. Коэффициенты сжатия: 20, 2, 1. Lossless JPEG рекомендуется применять в тех приложениях, где необходимо побитовое соответствие исходного и декомпрессированного изображений.

3.7 Заключение

графический информация кодирование сжатие алгоритм

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

4. Алгоритмы архивации с потерями

4.1 Алгоритм JPEG

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

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

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

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

Работа алгоритма.

Пусть сжимается 24-битное изображение.

Шаг I.

Переводим изображение из цветового пространства RGB, с компонентами, отвечающими за красную (Red), зеленую (Green) и синюю (Blue) составляющие цвета точки, в цветовое пространство YCrCb (иногда называют YUV).

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

Упрощенно перевод из цветового пространства RGB в цветовое пространство YCrCb можно представить так:

Обратное преобразование осуществляется умножением вектора YUV на обратную матрицу:

Шаг 2.

Разбиваем исходное изображение на матрицы 8х8. Формируем из каждой три рабочие матрицы ДКП - по 8 бит отдельно для каждой компоненты. При больших коэффициентах сжатия этот шаг может выполняться чуть сложнее. Изображение делится по компоненте Y - как и в первом случае, а для компонент Сr и Сb матрицы набираются через строчку и через столбец. Т.е. из исходной матрицы размером 16x16 получается только одна рабочая матрица ДКП. При том, как нетрудно заметить, мы теряем 3/4 полезной информации о цветовых составляющих изображения и получаем сразу сжатие в два раза. Мы можем поступать так, благодаря работе в пространстве YCrCb. На результирующем RGB изображении, как показала практика, это сказывается не сильно.

Шаг 3.

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

В упрощенном виде то преобразование можно представить так:

,

где

;

Шаг 4.

Проводим квантование. В принципе это просто деление рабочей матрицы на матрицу квантования поэлементно. Для каждой компоненты (Y, U и V), в общем случае, задается своя матрица квантования (далее МК).



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

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

С квантованием связаны и специфические эффекты алгоритма. При больших значениях коэффициента gamma, - потери в нижних частотах могут быть настолько велики, что изображение распадется на квадраты 8x8. Потери в высоких частотах могут проявиться в так называемом "эффекте Гиббса”, когда вокруг контуров с резким переходом цвета образуется своеобразный "нимб"

Шаг 5.

Переводим матрицу 8x8 в 64-элементный вектор при помощи зигзагообразного сканирования, т.е. выбираем элементы с индексами (0.0). (0.1). (1.0). (2.0)...

Таким образом, в начале вектора мы получаем коэффициенты матрицы, соответствующие низким частотам, а в конце - высоким.

Шаг 6.

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

Так, вектор [42 3 0 0 0 -2 0 0 0 0 1] будет свернут в пары (0, 42) (0, 3) (3, -2) (4, 1)

Шаг 7.

Свертываем поучившиеся пары кодированием по Хаффману с фиксированной таблицей.

Процесс восстановления изображения в этом алгоритме полностью симметричен. Метод позволяет сжимать некоторые изображения в 10-15 раз без серьезных потерь.

Конвейер операций, используемый в алгоритме JPEG.

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

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

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

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

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

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

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

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

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

Широкое применение JPEG долгое время сдерживалось, пожалуй, лишь тем, что он оперирует 24-битными изображениями. Поэтому для того, чтобы с приемлемым качеством посмотреть картинку на обычном мониторе в 256-цветной палитре, требовалось применение соответствующих алгоритмов и, следовательно, определенное время. В приложениях, ориентированных на придирчивого пользователя, таких, например, как игры, подобные задержки неприемлемы. Кроме того, если имеющиеся у вас изображения, допустим, в 8-битном формате GIF перевести в 24-битный JPEG, а потом обратно в GIF для просмотра, то потеря качества произойдет дважды при обоих преобразованиях. Тем не менее, выигрыш в размерах архивов зачастую настолько велик (в 3-20 раз!), а потери качества настолько малы, что хранение изображений в JPEG оказывается очень эффективным.

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

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

Характеристики алгоритма JPFG:

Коэффициенты компрессии: 2-200 (Задаётся пользователем).

Класс изображений: Полноцветные 24-битные изображения, или изображения в градациях серого без резких переходов цветов (фотографии).

Симметричность: 1.

Характерные особенности: В некоторых случаях, алгоритм создает "ореол" вокруг pезкиx горизонтальных и вертикальных границ в изображении (эффект Гиббса). Кроме того, при высокой степени сжатия изображение распадается на блоки 8х8 пикселей.

4.2 Фрактальный алгоритм

Идея метода

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

Построение изображения IFS (процесс декомпрессии).

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

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

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

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

пересекаются

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

контрастность

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

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



Рисунок. Машина Барнсли

Расставляя линзы и меняя их характеристики, можно управлять получаемым изображением. Одна итерация работы Машины заключается в том, что по исходному изображению с помощью проектирования строится новое, после чего новое берется в качестве исходного. Утверждается, что в процессе итераций мы получим изображение, которое перестанет изменяться. Оно будет зависеть только от расположения и характеристик линз, и не будет зависеть от исходной картинки. Это изображение называется "неподвижной точкой" или аттракторам данной IFS. Соответствующая теория гарантирует наличие ровно одной неподвижной точки для каждой IFS.

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

Наиболее известны два изображения, полученных с помощью IFS "треугольник Серпинского" и "папоротник Барнсли" "Треугольник Серпинского" задается тремя, а "папоротник Барнсли" четырьмя аффинными преобразованиями (или, в нашей терминологии, "линзами"). Каждое преобразование кодируется буквально считанными байтами, в то время как изображение, построенное с их помощью, может занимать и несколько мегабайт.

Папоротник Барнсли; задается 4 преобразованиями.

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

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

Алгоритм декомпрессии изображений

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

В качестве начального может быть взято абсолютно любое изображение (например, абсолютно черное), поскольку соответствующий математический аппарат гарантирует нам сходимость последовательности изображений, получаемых в ходе итераций IFS к неподвижному, изображению (близкому к исходному). Обычно для этого достаточно 16 итераций.

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

Потери и способы их регулирования

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

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

4.3 Рекурсивный (волновой) алгоритм

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

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

Так два числа а_2i и а_2i+1 всегда можно представить в виде:

b¹_i = ( а_2i + а_2i+1 )/2

и

b²_i = ( а_2i - а_2i+1 )/2 .

Аналогично последовательность а_i может быть попарно переведена в последовательность b¹²_i .

Например: пусть мы сжимаем строку из 8 значений яркости пикселей ( а_i ) (220. 211. 212. 218. 217. 214. 210, 202). Мы получим следующие последовательности b¹_i и b²_i : (215.5, 215, 215.5, 206) и (4.5, -3, 0.5, 4). Заметим, что значения b²_i достаточно близки к 0. Повторим операцию, рассматривая b¹_i , как а_i. Данное действие выполняется как бы рекурсивно, откуда и название алгоритма. Мы получим из (215.5, 215, 215.5, 206): (215.25, 210.75) (0.25, 4.75) Полученные коэффициенты, округлив до целых и сжав, например, с помощью алгоритма Хаффмана с фиксированными таблицами, мы можем поместить в файл.

Мы применяли преобразование к цепочке только два раза. Реально можно позволить себе применение wavelet - преобразования 4-6 раз. Более того, дополнительное сжатие можно получить, используя таблицы алгоритма Хаффмана с неравномерным шагом (т.е. придется сохранять код Хаффмана для ближайшего в таблице значения). Эти приемы позволяют достичь заметных коэффициентов сжатия.

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

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

Заключение

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

Алгоритм	Особенности изображения, за счет которых происходит сжатие
RLE	Подряд идущие одинаковые цвета: 222222215 15 15
LZW	Одинаковые подцепочки: 2 3 15 40 2 3 15 40
Хаффмана	Разная частота появления цвета: 22322432224
ССТТТ-3	Преобладание белого цвета в изображении, большие области, заполненные одним цветом
Рекурсивный	Плавные переходы цветов и отсутствие резких границ
JPEG	Отсутствие резких границ
Фрактальный	Подобие между элементами изображения

Алгоритм	К - ты сжатия	Симметричность по времени	На что ориентирован	Потери	Размерность
RLE	32, 2, 0.5	1	3,4-х битные	Нет	1D
LZW	1000,4,5/7	1.2-3	1 - 8 битные	Heт	1D
Хаффмана	8, 1.5, 1	1-1.5	8 битные	Нет	1D
ССТТТ-3	213(3),5,	~1	1- битные	Нет	1D
	0.25
JBIG	2-30 раз	~1	1- битные	Нет	2D
Lossless JPEG	2 раза	~1	24 - бит. сер.	Нет	2D
Рекурсивное сжатие	2-200 раз	1.5	24 - битные, серые	Да	2D
JPEG	2-200 раз	~1	24 - битные, сер.	Да	2D
Фрактальный	2-2000 раз	1000-10000	24 - бит. сер.	Да	2.5D

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

ориентация на фотореалистичные изображения с 16 миллионами цветов (24 бита);

использование сжатия с потерями, возможность за счет потерь регулировать качество изображений:

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

появление существенно несимметричных алгоритмов:

увеличивающаяся степень сжатия изображений.

Приложение

Основные графические форматы

Применяются, в основном, следующие форматы графических файлов: GIF, JPEG, PNG и SWF. Файлы форматов GIF, JPEG nPNG предназначены для компактного хранения растровой графики, а SWF-файлы -- для векторной статической и анимационной графики, а также звука. В настоящее время SWF является единственным форматом векторной графики, которую можно встроить в Web-сайт.

Файлы форматов JPEG, GIF и PNG очень популярны и могут быть открыты для просмотра большинством графических программ. SWF-файлы можно просматривать в современных Web-браузерах, а также с помощью специального Flash-плеера, который поставляется вместе с пакетами Flash и FreeHand.

Формат GIF

Формат GIF (Graphics Interchange Format -- формат графического обмена) использует алгоритм сжатия без потерь LZW и предназначен для сохранения растровых изображений с количеством цветов не более 256.

В настоящее время существуют две версии формата -- GIF87a и GIF89a. Имена файлов этих форматов имеют расширение gif. Первая версия была разработана в 1987 г., а вторая -- в 1989 г. Формат GIF89a позволяет сохранять прозрачность (transparency, альфа-канал) пикселей и поддерживает анимацию. Кроме того, формат GIF допускает чересстрочную (interlaced) запись графической информации, чтобы загрузка в браузер выглядела как постепенное повышение четкости изображения. Это достигается записью в файл сначала каждой 8-й, затем каждой 4-й и т. д. строк пикселей изображения. Таким образом, еще до окончательной загрузки файла можно увидеть его постепенно проявляющееся содержание. Чересстрочная запись несколько увеличивает размер файла, но дает интересный визуальный эффект.

В формате GIF89a можно сохранить не только одно, а несколько изображений, которые браузер показывает друг за другом с заданными частотой и временем задержки. В результате возникает эффект анимации -- движущейся картинки. Анимационные GIF-файлы можно просматривать с эффектом движения и Web-браузерах, Проводнике Windows, а также в некоторых программах просмотра, например, ACDSee.

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

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

Формат PNG

Формат PNG (Portable Network Graphics -- переносимая графика для сети) был разработан с целью заменить формат GIF и JPEG. Формат PNG должен был преодолеть недостатки GIF, связанные с ограничением количества цветов. Файлы этого формата имеют расширение png.

Формат PNG позволяет сохранять изображения с глубиной цвета 24 и даже 48 бит, он также позволяет включать каналы масок для управления градиентной прозрачностью, но не поддерживает слои. PNG сжимает изображения практически без потери качества. Используемый алгоритм сжатия Deflate близок к LZW. Файлы PNG обычно имеют больший размер, чем GIF- и JPEG-файлы с аналогичными изображениями. Этот формат целесообразно использовать для сохранения небольших многоцветных изображений с мелкими деталями.

Формат JPEG

Формат JPEG (Joint Photographic Experts Group -- объединенная группа экспертов по фотографии) предназначен для компактного хранения растровых многоцветных изображений с фотографическим качеством. Он был разработан в1995 г., файлы этого формата имеют расширение jpg, jpe или jpeg.

В отличие от GIF, в формате JPEG используется алгоритм сжатия с потерями информации, благодаря чему достигается очень большая степень сжатия (от единиц до сотен раз).

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

Существуют разновидности формата JPEG:

· Baseline Standart (стандартная базовая линия) -- основной формат;

· Baseline Optimized (оптимизированная базовая линия) с немного более эффективным алгоритмом сжатия;

· Progressive (прогрессивный, постепенный), поддерживающий чересстрочный режим отображения, при котором загрузка в браузер выглядит как постепенное повышение четкости картинки.

Формат JPEG не поддерживает индексированные цвета и прозрачность пикселей (альфа-канал) и допускает внедрение ICC-профилей.

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

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