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

Содержание:
Введение 3
1. Виды графической информации по способу кодировки 4
2 Алгоритмы сжатия данных 6
2.1 Групповое кодирование (RLE) 8
2.2 Алгоритм Хаффмана 11
2.3 Алгоритм Хаффмана с фиксированной таблицей CCITTGroup 3 13
2.4 LZW-сжатие 14
2.4 JPEG (Joint Photographic Experts Group) 15
Заключение 18
Литература 19
 

Далее, этот ряд уже, в свою очередь, сжимается по Хаффману с фиксированной таблицей.Каждая строка изображения сжимается независимо. Считается, что в изображении существенно преобладает белый цвет, и все строки изображения начинаются с белой точки. Для строки, начинающейся с черной точки, считают, что строка начинается белой серией длины 0. На практике в тех случаях, когда в изображении преобладает черный цвет, перед компрессией изображение инвертируется, что записывается в заголовок файла.Достоинства алгоритма в том, что он чрезвычайно прост в реализации, быстр и может быть легко реализован аппаратно.Алгоритм CCITTGroup 3 реализован в формате TIFF.2.4LZW-сжатиеСхема сжатия Лемпела – Зива – Велча(LZW) (по первым буквам фамилий его разработчиков) - одиниз наиболее распространенных в компьютерной графике. Существует довольно большое семейство LZ-подобных алгоритмов, различающихся, например, методом поиска повторяющихся цепочек.Алгоритм LZW позволяет работать с любым типом данных. Он относится к алгоритмам подстановок, основанными на словарях. Этот алгоритм из данных входного потока строит словарь данных (также называемый переводной таблицей или таблицей строк). В таблице инициализируются все 1-символьные строки. Алгоритм сверяет каждый символ данных, и каждую уникальную2х-символьную строку сохраняет в таблице в виде кода, ссылающегося на соответствующий первый символ. При просматривании очередного символа, для него из таблицы находится уже встречавшаяся строка максимальной длины, затем в таблице сохраняется код для этой строки со следующим символом на входе; на выход выдаётся код этой строки, а следующий символ используется в качестве начала следующей строки.При раскодировании требуется только закодированные данные, а по нему воссоздается соответствующая таблица строк непосредственно по закодированным данным.Декодирование LZW-данных осуществляется в порядке, обратном кодированию.Достоинства алгоритма LZW:- нетнеобходимости вычислять вероятности встречаемости символов;- таблицу строкможно восстановить, пользуясь только потоком кодов, поэтому нет необходимости сохранять её вместе со сжатыми;- в исходный графический файл не вносятся искажения, поэтому алгоритм подходит для сжатия растровых данных любого типа.Недостатки:- алгоритм не проводит анализ входных данных поэтому не оптимален.Применяется в форматах GIFи TIFF, включен в стандарт сжатия для модемов V.42bisи PostScriptLevel 2.2.4 JPEG (Joint Photographic Experts Group)Наиболее известным методом компрессии с потерями является JPEG-компрессия. В основе метода лежит особенность человеческого восприятия: глаз может достаточно четко различать яркость объекта и цветовые контрасты, а плавные изменения в светах и тенях различает значительно меньше. Поэтому при записи часть цветовых данных можно опустить, как предполагается, без заметного ущерба для восприятия.Рисунок2 - Компромисс между качеством и уровнем компрессииАлгоритм разрабатывалсяспециально для сжатия 24-битных изображений группой экспертов в области фотографииJPEG - JointPhotographicExpertGroup - подразделение в рамках ISO - Международной организации по стандартизации. В JPEGизображение обрабатывается в несколько этапов. Сначала оно конвертируется в особое цветовое пространство, похожее на цветовую модель CIE Lab, где один канал определяет яркость, а в остальных двух каналах уменьшается разрешение (по методу мозаики).Далее изображение разбивается на области квадратной формы размером 8х8 пикселей. В каждойобластиосуществляются достаточно сложные математические преобразования. Происходит запись двух типов информации — усредненной информации о блоке и информации о его деталях. Дальше, в зависимости от необходимой степени сжатия, удаляется то или иное количество дополнительной информации. Соответственно, у файла меньшего размера, качество будет хуже.Одновременно каждаяобластьподвергается разложению на составляющие цвета и происходит подсчет частоты встречаемости каждого цвета. Это позволяет исключить небольшую часть яркостной характеристики, и довольно значительную часть цветовой. Степень исключения этой информации как раз и определяется установкой требуемого качества.Далее информация о яркости и цвете кодируется так, что остаются только различия между соседними блоками. В результате процессе обработки остаются только последовательности простых чисел, которые далее легко сжимаютсялюбым алгоритмом сжатия без потерь (например, алгоритмом Хаффмана).Достоинства алгоритма LPEG:- можно задать степень сжатия, соответственно подобрать необходимый размер и качество изображения;Недостатки алгоритма:- при высокой степени сжатия происходит распад изображения на отдельные квадраты (8х8), за счет больших потерь в низких частотах при квантовании и что делает невозможным восстановление исходных данных;- по границам резких переходов цветов проявляется заметные ореолы - эффект Гиббса.Алгоритмы сжатия с потерями, в частности алгоритм JPEG, не позволяют полностью восстановить изображение до его исходного состояния, а, следовательно, не рекомендуется сжимать изображения несколько раз.ЗаключениеС первого взгляда кажется логичным, что основным критерием выбора метода сжатия информации должно быть обеспечение высокой сохранности данных и возможность их полного восстановления после распаковки. Поэтому алгоритмы сжатия без потерь (RLE, Хаффмана, LZWи др.) вроде бы вполне должны удовлетворять потребности пользователей по сжатию графической информации. Тем более, что эти алгоритмы достаточно универсальны и покрывают все типы графических файлов. Однако,по сегодняшним меркам у них есть один существенный недостаток, они имеют слишком маленький коэффициент сжатия (примерно 1 к 2). Тогда как алгоритмы сжатия с потерями оперируют с коэффициентами 10-200 раз.Поэтому на современном этапе более актуальным является применение алгоритмов сжатия с потерями, в которых применяются более современные алгоритмы кодированияс использованием идеи так называемых «когерентных областей», заключающиеся в малом изменении цвета и структуры на небольшом участке изображения. Что обеспечивает высокую степень сжатия с потерями, потери практически не различимы человеческим глазом. В общем же случае, выбор алгоритма сжатия графической информации зависит от типа исходного файла, задачи и назначения сжатого изображения, и зависит от каждого конкретного случая. Поэтому для получения компактного графического изображения, рекомендуется попробовать сохранить его в разных форматах и сравнить качество и объем полученных файлов, и выбрать наиболее оптимальный для вашего случая формат. ЛитератураШикин Е.В., Боресков А.В. Компьютерная графика. - М.: Диалог - МИФИ, 1995. – 464 с.Захаров С. С. Учебное пособие по дисциплине «Компьютерная графика». – М.: МГУЭСиИ, 2006. – 52 с.Джеймс Д. Мюррей, Уильям ванРайперЭнциклопедия форматов графических файлов - К.: BHV, 1997.Том Сван Форматы файлов Windows - М.: Binom, 1995.Борзенко А., Федоров А. Мультимедиа для всех. - М.:Компьютер-пресс, 1995.Корриган Д. Компьютерная графика. Секреты и решения - М.:Энтроп, 1995.Мультимедиа/ Под ред. Петренко А.И. - М.: БИНОМ, 1994.