Методическое пособие «представление графической информации в вычислительной технике» Часть 3




Скачать 117.63 Kb.
НазваниеМетодическое пособие «представление графической информации в вычислительной технике» Часть 3
Дата публикации09.05.2013
Размер117.63 Kb.
ТипМетодическое пособие
vbibl.ru > Информатика > Методическое пособие


МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ИНСТИТУТ

(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

С. О. БОГДАНОВ


МЕТОДИЧЕСКОЕ ПОСОБИЕ


«ПРЕДСТАВЛЕНИЕ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ В ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКЕ»



Часть 3

Сжатие изображений

МОСКВА 1998
Сжатие изображений

Проведем небольшой расчет. Допустим, у нас есть небольшое цветное изображение размером 10 на 12 сантиметров (приблизительно 4 на 5 дюймов), которое мы хотим хранить в компьютере и при необходимости распечатывать с фотографическим качеством, а это означает реальный цвет (true color) и разрешение 300 dpi. Когда изображение будет оцифровано, оно примет размеры 1200 на 1500 пикселей и, поскольку каждый пиксель будет кодироваться тремя байтами, займет 5,2 Мбайт памяти. Если же мы хотим предоставить эту картинку для публикации в книге, журнале или любом другом полноцветном печатном издании, то нам придется сохранить ее в цветовой модели CMYK, а это увеличит ее объем до 6,9 Мбайт.

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

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

Наиболее распространенными на сегодняшний день в области компьютерной графики алгоритмами сжатия статических изображений являются LZW, RLE и JPEG. Рассмотрим их более подробно.
^ Групповое кодирование
Одним из самых простых алгоритмов сжатия является групповое кодирование. В основе алгоритма лежит замена повторяющихся величин (значений пикселей) одной с указанием количества. Например, исходная строка вида abbbbbbbccddddeeddd будет заменена на Ia7b2c4d2e3d. Очевидно, что лучше всего такой алгоритм будет работать с длинными сериями повторяющихся величин. Великолепные результаты он может дать на монохромных изображениях.

Этот алгоритм имеет несколько реализаций. К ним относятся, например, RLE и PackBits. PackBits получил распространение на компьютерах Apple Macintosh. Работая с 8-битными данными, алгоритм производит кодирование с помощью двух байтов. Первый байт содержит число n из диапазона -127...-1 такое, что -n+1 равно числу повторений. Второй байт содержит повторяющуюся величину. Если встречается неповторяющаяся последовательность, то в первом байте будет содержаться значение m из диапазона 0...127, соответствующее уменьшенной на единицу длине этой последовательности, а сама она в неизменном виде будет записана дальше.
^ Метод Хаффмана (CCITT Group 3)
Кодирование методом Хаффмана (Huffman) также основано на поиске повторяющихся сегментов данных. Идея метода состоит в том, чтобы присвоить каждой уникальной величине некоторый двоичный код. Причем длина этих кодов зависит от частоты появления соответствующих величин. Для более часто встречающихся величин используются более короткие коды.

Например, в abbbcccddeeeeeeeeef есть шесть уникальных величин. Частоты их появления соответственно равны:
а:1 b:3 c:3 d:2 e:9 f:l
Для формирования минимального кода для каждого используется двоичное дерево (рис. 11). Алгоритм объединяет вместе элементы, появляющиеся наименее часто. Их частоты складываются, и затем такая пара рассматривается как один элемент. Процесс продолжается до тех пор, пока все элементы не объединятся в пары.

В этом примере наиболее редко встречаются величины а и f, поэтому они становятся первой парой и будут иметь наиболее длинные коды. Младший бит этих кодов будет являться 0 для а и 1 — для f. Старшие биты этих кодов будут получены из дерева по мере его построения.

Затем частоты этих двух величин суммируются, что в итоге дает 2. Поскольку самой низкой частотой теперь является 2 — создаем новую пару, объединяясь с d, также имеющей частоту 2.

Исходной паре присваивается ветвь 0, a d — ветвь 1. Следовательно, код для а будет заканчиваться на 00, для f — на 01, а для dна 1 (и будет короче на 1 разряд). Дерево продолжает строиться аналогичным образом, пока в него не войдут все величины, в том числе наиболее часто встречающиеся.


^ Рис. 11. Двоичное дерево Хаффмана
Алгоритм Хаффмана имеет несколько вариаций и в зависимости от типа изображения может достигать степени сжатия 5:1. Существенным недостатком алгоритма является то, что он нуждается в точной статистике частот встречающихся в исходном файле величин. Без точной статистики результирующий файл может стать больше исходного. Поэтому этот алгоритм часто реализуется в два прохода: первый проход собирает статистику, а второй занимается собственно кодированием. Поскольку кодирование и декодирование требуют значительных вычислительных ресурсов, компрессия и декомпрессия по алгоритму Хаффмана являются достаточно медленными процессами.
LZW
Очень популярным сегодня является алгоритм Лемпела-Зива-Вельча — LZW (Lempel-Ziv & Welch), для подавляющего большинства изображений гарантирующий сжатие в 2 — 3 раза. Он имеет огромное множество модификаций и применяется не только в машинной графике. В отличие от схемы Хаффмана алгоритму LZW не требуется перед кодированием создавать таблицу кодов. Начиная с простой таблицы, алгоритм в ходе работы формирует все более эффективную. Идея алгоритма заключается в поиске повторяющихся последовательностей, и при этом длина кода не зависит от частоты появления соответствующей величины.

LZW начинает с таблицы с одним элементом кода для каждой возможной величины данных; например, 256 элементов для 8-битных данных. Затем алгоритм добавляет в таблицу данные для каждого уникального сочетания величин, которое удается обнаружить.

Рассмотрим последовательность ababaaacaaaad. Пусть каждая буква представляет собой 2-битную величину. Начальная таблица шифратора и дешифратора для данного примера будет выглядеть следующим образом:
а:00 b:01 с: 10 d:ll
LZW ищет самую длинную последовательность, которую может распознать, и сохраняет в таблице объединение ее со следующим символом. В начале алгоритм находит первую величину а и распознает ее. Затем он проверяет последовательность ab и не распознает ее. Тогда он выдает код 000 для а, как распознанной величины, и добавляет новый вход в таблицу для нераспознанной последовательности аb. Таблица шифрования принимает следующий вид:
а:000 b:001 c:010 d:011 ab:100
Шифратор остановился на величине b, он добавляет к ней следующую и обнаруживает, что получившаяся последовательность ba не распознается. Алгоритм выдает код 001 для b, и продолжает шифрование.

Теперь начинается «хороший» этап. Алгоритм ищет, начиная с а, самую длинную распознаваемую последовательность. Такой последовательностью является ab, для которой выдается код 100. Это означает, что 4-битная последовательность оказалась замененной 3-битной. Продолжая перебор, алгоритм будет пополнять таблицу все новыми входами, а это позволит заменять кодами все более длинные последовательности. На рисунке 12 приводится алгоритм кодирования LZW на языке Си. Процедура распаковки данных происходит аналогично, хотя и несколько сложнее (рис. 13).
^ Сжатие с потерями. JPEG
Все схемы, описанные выше, относятся к категории алгоритмов без потерь. Это означает, что данные, будучи сжаты за счет избыточности, могут затем быть восстановлены в первоначальном виде. Избыточность практически никогда не бывает большой, поэтому подобного рода алгоритмы способны обеспечить сжатие в лучшем случае двух-трехкратное сжатие.

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

В связи с бурным ростом в последние годы средств мультимедиа, Internet-технологий, цифрового фото и видео широкое распространение получил алгоритм JPEG (Joint Photographic Experts Group), разработанный Объединенной Группой Экспертов по Фотографии Международной Организации Стандартизации (ISO).
I* — сжатие — */

InitializeStringTable();

Г = пустая строка;

for для каждого символа в файле {

К = GetNextCharacter();

if (Г + К в таблице строк) {

Г = Г + К; /* объединение строк */

} else{

WriteCode(CodeFromString(Г));

AddTableEntry(Г + K);

Г = К;

}

} /* конец цикла */ WriteCode(CodeFromString(Г)); WriteCode(EndOfInformation);

^ Рис. 12. Алгоритм сжатия данных методом LZW

/* — распаковка — */

InitializeTable();

Code = GetNextCode();

WriteString(StringFromCode(Code));

OldCode = Code;

while ((Code=GetNextCode())!=EoiCode) {

if (IsInTable(Code)) {

WriteString(StringFromCode(Code));

AddStringToTable(

StringFromCode(OldCode)+

FirstChar(StringFromCode(Code)));

OldCode = Code;

}

else{

OutString = StringFromCode(OldCode)+

FirstChar(StringFromCode(OldCode));

WriteString(OutString);

AddStringToTable(OutString);

OldCode = Code;

}

}

^ Рис. 13. Алгоритм декомпрессии LZW
Алгоритм JPEG имеет много вариаций, но все они в целом исходят из одной общей схемы. В начале графическая информация разделяется на цветовой (chroma) и яркостной (luminance) каналы, чтобы использовать преимущества того, что человеческий глаз допускает уменьшение разрешение для цвета. Переход к цветовой модели YCbCr происходит по следующим формулам:
Y = 0,299R + 0.587G + 0,114В

Cb = 0,1687R - 0,3313G + 0,5В

Cr = 0,5R - 0,4187G + 0,0813B
После этого получается изображение в градациях серого (Y) и двух каналах информации о различии цветов (Сb и Сr). На этой стадии потерь еще нет, хотя при преобразовании цветовой модели и возникает ошибка округления (цвет всегда кодируется целым числом).

Следующий шаг — применение к каждому из каналов дискретного косинусоидального преобразования (Discrete Cosine Transform, DCT), после чего индивидуальные пиксели перестают существовать. JPEG допускает дискретизацию различных компонент с различной частотой. Поскольку человеческий глаз значительно менее чувствителен к изменениям цвета, нежели к изменениям яркости, то, как правило, используют одну выборку Сb и Сr для каждых четырех выборок Y. Это в два раза уменьшает объем файла (6 выборок вместо 12) практически без потерь качества при восприятии изображения.

JPEG разбивает все изображение на блоки размером 8x8 пикселей. Точки в каждом блоке нумеруются от (0,0) в левом верхнем углу до (7,7) в правом нижнем. К каждому такому блоку применяется двумерное дискретное косинусоидальное преобразование (DCT), которое превра­щает информацию об интенсивности цвета f(x,x), в пространственные частоты F(u,v), указывающие на то, насколько быстро эти интенсивности изменяются для каждой из частот.
,
где

Например, F(l,0) определяет, каково изменение интенсивности по горизонтали (низкая частота) при отсутствии вертикального изменения. F(7,7) определяет степень, на которую интенсивности изменяются наиболее быстро в обоих направлениях (высокая частота). Значение F(0,0) указывает, что интенсивность вообще не изменяется и представляет собой среднее от 64 элементов блока. Эта величина известна как коэффициент DC, остальные значения — коэффициенты AC.

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

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

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

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

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

Непосредственно из этой схемы сжатия появился стандарт MPEG (Motion Picture Experts Group), применяющийся для движущихся изображений. Файл MPEG содержит JPEG-подобные кадры и информацию о «разности» между кадрами. Эта информация позволяет с помощью интерполяции получать недостающие кадры. В настоящий момент существуют специализированные процессоры для кодирования и декодирования информации методами MPEG и JPEG.

Таблица 3. Сравнение алгоритмов сжатия данных

Алгоритм

Принцип сжатия

Потери

Размерность

Сжатие

RLE

Подряд идущие цвета 2 2 2 2 2 2 2 15 15 15

нет

1D

1:1,5 - 1:2

LZW

Одинаковые подцепочки 2 3 15 40 2 3 15 40

нет

ID

1:2 - 1:4

Хаффмана

Разная частота появления цвета 22322432224

нет

ID

1:3 - 1:6

JPEG

Отсутствие резких цветовых границ

есть

2D

1:5 - 1:50

Дополнительные ссылки:

http://www.rasip.fer.hr/research/compress/intro.html



Добавить документ в свой блог или на сайт

Похожие:

Методическое пособие «представление графической информации в вычислительной технике» Часть 3 iconМетодическое пособие «представление графической информации в вычислительной технике» Часть 4
На первый взгляд кажется непонятным, откуда появилось такое разнообразие форматов растровых изображений. Ведь их природа достаточно...

Методическое пособие «представление графической информации в вычислительной технике» Часть 3 iconМетодическое пособие «представление графической информации в вычислительной технике» Часть 2
Изображения, с которыми приходится иметь дело в повседневной жизни, можно разделить на черно-белые и цветные. Примерно то же самое...

Методическое пособие «представление графической информации в вычислительной технике» Часть 3 iconМетодическое пособие «представление графической информации в вычислительной технике» москва 1998
Ввод-вывод, хранение и обработка ее сегодня осуществляются средствами вычислительной техники, но требуются при этом особые подходы...

Методическое пособие «представление графической информации в вычислительной технике» Часть 3 iconПонятие об информации
Информатика и икт: Методическое пособие для учителей. Часть Информационная картина мира

Методическое пособие «представление графической информации в вычислительной технике» Часть 3 iconМетодическое пособие по электронной технике с указаниями и примерами...
Техническая эксплуатация, обслуживание и ремонт электрического и электромеханического оборудования

Методическое пособие «представление графической информации в вычислительной технике» Часть 3 iconУстройство автомобиля часть 2 системы питания двигателей учебно-методическое пособие
Учебно-методическое пособие предназначено для студентов дневного и заочного отделений технолого-экономического факультета нгпу, обучающихся...

Методическое пособие «представление графической информации в вычислительной технике» Часть 3 iconУстройство автомобиля часть 3 электрооборудование автомобиля учебно-методическое пособие
Учебно-методическое пособие предназначено для студентов дневного и заочного отделений технолого-экономического факультета нгпу, обучающихся...

Методическое пособие «представление графической информации в вычислительной технике» Часть 3 iconМетодическое пособие Киселевск 2012
...

Методическое пособие «представление графической информации в вычислительной технике» Часть 3 iconМетодическое пособие для выполнения курсовой работы по дисциплине «декоративное садоводство»
Методическое пособие составили: профессор Мамонов Е. В., доценты: Иванова И. В., Ващенко М. А., Скакова А. Г

Методическое пособие «представление графической информации в вычислительной технике» Часть 3 iconУчебно-методическое пособие специальность 050104 «Безопасность жизнедеятельности»
Учебно-методическое пособие / М. Б. Звонкова, А. В. Неделяева, Ю. В. Егорова, Е. Л. Агеева Н. Новгород: нгпу, 2008. 48 с

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница