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

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

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

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

Саратовский государственный университет имени Н.Г. Чернышевского

Кафедра теоретических основ компьютерной безопасности и криптографии

Контрольная работа

На тему: "Алгоритмы сжатия графической информации"

Выполнил: студент 1 курса

Беззуба Дмитрий Владимирович

Научный руководитель: проф., канд. физ.-мат. наук

В.Н. Салий

Саратов, 2012 год

Типичное изображение, полученное цифровой фотокамерой, имеет разрешение порядка 3000x2000, т.е. около 6 мегапикселей; для передачи цвета обычно используется 24 бита на пиксель. Таким образом, объем исходных данных составляет порядка 17 мегабайт. Для профессиональных устройств ввода изображений размер получаемого растра может быть значительно больше, а глубина цвета - достигать 48 бит на пиксель (см. лекцию 2). Соответственно, размер одного изображения может быть больше 200 мегабайт. Поэтому весьма актуальными являются алгоритмы сжатия изображений, или, иными словами, алгоритмы, которые позволяют уменьшить объем данных, представляющих изображение.

Существуют два основных класса алгоритмов:

1) Алгоритм сжатия без потерь.

Если существует алгоритм A^-1 (обратный к A) такой, что для любого изображения I:

A(I) = I₁

A^-1(I₁) = I

Изображение I задано как множество значений атрибутов пикселей; после применения к I алгоритма A получаем набор данных I₁. Сжатие без потерь применяется в таких графических форматах представления изображений, как: GIF, PCX, PNG, TGA, TIFF.

2) Алгоритм сжатия с потерями.

Такие алгоритмы не обеспечивают возможность точного восстановления исходного изображения. Парный к A алгоритм, обеспечивающий примерное восстановление, будем обозначать как A^*: для изображения I:

алгоритм кодирование данные изображение

A(I) = I₁

A^*(I₁) = I₂

И при этом полученное восстановленное изображение I₂ не обязательно точно совпадает с I. Пара A, A^* подбирается так, чтобы обеспечить большие коэффициенты сжатия и, тем не менее, сохранить визуальное качество, т.е. добиться минимальной разницы в восприятии между I и I₂. Сжатие с потерями применяется в следующих графических форматах: JPEG, JPEG2000 и т.д.

Алгоритмы RLE. Этот тип алгоритмов базируется на простейшем принципе: будем заменять повторяющиеся группы элементов исходной последовательности на пару (количество, элемент), либо только на количество.

Рассмотрим чёрно-белое изображение. Будем рассматривать исходные данные на уровне последовательности битов. Подряд идет несколько 0 или 1, и можно помнить лишь количество идущих подряд одинаковых цифр. Возникает следующий нюанс: числа, обозначающие количество повторений, также надо кодировать битами. Можно считать, что каждое число повторений изменяется от 0 до 7 (т.е. можно закодировать ровно тремя битами). Для примера, последовательность, состоящая из 21 единицы, 21 нуля, 3 единиц и 7 нулей закодируется так:

111 000 111 000 111 111 000 111 000 111 011 111

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

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

ABCABCABCABCDDEFFFFFFFF

1A 1B 1C 1A 1B 1C 1A 1B 1C 1A 1B 1C 2D 1E 8F

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

-12ABCABCABCABC 2D 1E 8F

Такая модификация данного алгоритма используется в формате PCX.

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

LZ77 и LZ78 -- алгоритмы сжатия без потерь, опубликованные в статьях Абрахама Лемпеля и Якоба Зива в 1977 и 1978 годах соответственно.

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

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

Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch, LZW) -- это универсальный алгоритм сжатия данных без потерь, созданный Абрахамом Лемпелем (англ. Abraham Lempel), Якобом Зивом (англ. Jacob Ziv) и Терри Велчем (англ. Terry Welch). Он был опубликован Велчем в 1984 году, в качестве улучшенной реализации алгоритма LZ78, опубликованного Лемпелем и Зивом в 1978 году. Алгоритм разработан так, чтобы его можно было быстро реализовать, но он не обязательно оптимален, поскольку он не проводит никакого анализа входных данных.

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

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

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

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

Литература

http://www.sernam.ru/cod_5.php

http://www.intuit.ru/department/graphics/rastrgraph/13/3.html

http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%BC%D0%BF%D0%B5%D0%BB%D1%8F_%E2%80%94_%D0%97%D0%B8%D0%B2%D0%B0_%E2%80%94_%D0%92%D0%B5%D0%BB%D1%87%D0%B0

http://www.intuit.ru/department/graphics/rastrgraph/13/3.html

Размещено на Allbest.ru