Факультет ВМиК МГУ / Курс Машинная графика-2 / Алгоритмы сжатия изображений

Московский Государственный Университет им. М.В. Ломоносова Факультет Вычислительной Математики и Кибернетики

Д.С. Ватолин

Алгоритмы Сжатия изображений

Методические материалы к

спецкурсу ВМиК МГУ “Машинная графика-2” под руководством Ю.М. Баяковского

УДК 681.3

Ватолин Д.С. Алгоритмы сжатия изображений. Методическое пособие.

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

Рецензенты:

Баяковский Ю.М., к.ф.-м.н.

Кумсков М.И., д.ф.-м.н.

Издательский отдел факультета Вычислительной Математики и Кибернетики МГУ им. М.В.Ломоносова (лицензия ЛР ¹040777 от 23.07.96), 1999 г.— 76 с.

Печатается по решению Редакционно-Издательского Совета факультета Вычислительной Математики и Кибернетики Московского Государственного Университета им. М.В. Ломоносова

ISBN 5-89407-041-4 Ó Издательский отдел факультета Вычислительной Математики и Кибернетики МГУ им. М.В. Ломоносова, 1999 г.

Предисловие

Спецкурс “Машинная графика-2” читается на факультете ВМиК МГУ уже более 10лет. Являясь логическим продолжением общего курса “Машинная графика”, спецкурс более углубленно и детально рассматривает многие аспекты этой интересной области.

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

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

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

Сейчас в стадии подготовки находится гипертекстовый вариант этого пособия, который будет выложен на сайте нашего курса по адресуhttp://graphics.cs.msu.su/courses.

Ю.М. Баяковский 13.11.98

Содержание

Общие положения алгоритмов сжатия изображений 4

Введение 4

Классы изображений 4

Классы приложений 5

Критерии сравнения алгоритмов 8

Контрольные вопросы к разделу 9

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

Алгоритм RLE 9

Алгоритм LZW 12

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

JBIG 23

Lossless JPEG 23

Заключение 23

Контрольные вопросы к разделу 24

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

Проблемы алгоритмов архивации с потерями 24

Алгоритм JPEG 25

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

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

Заключение 38

Контрольные вопросы к разделу 39

Различия между форматом и алгоритмом 39

Указатель терминов 40

Литература 41

Литература по алгоритмам сжатия 41

Литература по форматам изображений 42

Приложение. Таблицы сравнения алгоритмов 43

Архивация двуцветного изображения 43

Архивация 16-цветного изображения 44

Архивация изображения в градациях серого 44

Архивация полноцветного изображения 46

Последнее изменение: 26.5.1999 08:40:00 PM(Версия 1 с 04.11.1998 13:08:00) Напечатан: 1.3.2017

С автором можно связаться по адресу [e-mail]

Общие положения алгоритмов сжатия изображений Введение

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

1. Изображения (как и видео) занимают намного больше места в памяти, чем текст. Так скромная, не очень качественная иллюстрация на обложке книги размером 500x800 точек занимает1.2Мб — столько же, сколько художественная книга из 400 страниц (60 знаков в строке, 42 строки на странице). В качестве примера можно рассмотреть также, сколько тысяч страниц текста мы сможем поместить наCD-ROM, и как мало там поместится качественных несжатых фотографий. Эта особенность изображенийопределяет актуальность алгоритмов архивацииграфики.

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

3. Мы можем легко заметить, что изображение в отличие, например, от текста обладает избыточностью в 2-х измерениях. Т.е. как правило, соседние точки, как по горизонтали, так и по вертикали в изображении близки по цвету. Кроме того, мы можем использовать подобие между цветовыми плоскостями R, G иBв наших алгоритмах, что дает возможность создать еще более эффективные алгоритмы. Таким образом,при создании алгоритма компрессии графики мы используем особенности структуры изображения.

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

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

4. Какие критерии мы можем предложить для сравнения различных алгоритмов?

5. Какие классы изображений существуют?

6. Какие классы приложений, использующие алгоритмы компрессии графики, существуют, и какие требования они предъявляют к алгоритмам?

Рассмотрим эти вопросы подробнее.

Классы изображений

Статические растровые изображения, представляют собой двумерный массив чисел. Элементы этого массива называют пикселами(от английскогоpixel — picture element). Все изображения можно подразделить на две группы — с палитрой и без нее. У изображений с палитрой в пикселе хранится число — индекс в некотором одномерном векторе цветов, называемомпалитрой.Чаще всего встречаются палитры из 16 и 256 цветов.

Изображения без палитры бывают в какой-либо системе цветопредставления и в градациях серого(grayscale). Для последних значение каждого пиксела интерпретируется как яркость соответствующей точки. Встречаются изображения с 2, 16 и 256 уровнями серого. Одна из интересных практических задач заключается в приведении цветного или черно-белого изображения к двум градациям яркости, например, для печати на лазерном принтере. При использовании некойсистемы цветопредставлениякаждый пиксел представляет собой запись (структуру), полями которой являются компоненты цвета. Самой распространенной являетсясистема RGB, в которой цвет представлен значениями интенсивности красной (R), зеленой (G) и синей (B) компонент. Существуют и другие системы цветопредставления, такие, как CMYK, CIE XYZccir60-1 и т.п. Ниже мы увидим, как используются цветовые модели при сжатии изображений с потерями.

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

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

7. Класс 1. Изображения с небольшим количеством цветов(4-16) и большими областями, заполненными одним цветом. Плавные переходы цветов отсутствуют. Примеры: деловая графика — гистограммы, диаграммы, графики и т.п.

8. Класс 2. Изображения, с плавными переходами цветов, построенные на компьютере. Примеры: графика презентаций, эскизные модели в САПР, изображения, построенные по методу Гуро.

9. Класс 3. Фотореалистичные изображения.Пример: отсканированные фотографии.

10. Класс 4. Фотореалистичные изображения с наложением деловой графики. Пример: реклама.

Развивая данную классификацию, в качестве отдельных классов могут быть предложены некачественно отсканированные в 256 градаций серого цвета страницы книг или растровые изображения топографических карт. (Заметим, что этот класс не тождественен классу 4). Формально являясь 8- или 24-битными, они несут даже не растровую, а чисто векторную информацию. Отдельные классы могут образовывать и совсем специфичные изображения: рентгеновские снимки или фотографии в профиль и фас из электронного досье.

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

Итог:Нет смысла говорить о том, что какой-то алгоритм сжатия лучше другого, если мы не обозначили классы изображений, на которых сравниваются наши алгоритмы.