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

Алгоритм JPEG

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

Алгоритм разработан группой экспертов в области фотографии специально для сжатия 24-битных изображений. JPEG — Joint Photographic Expert Group — подразделение в рамках ISO — Международной организации по стандартизации.

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

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

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

Отрицательными сторонами алгоритма является то, что при повышении степени сжатия изображение распадается на отдельные квадраты (8x8).

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

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

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

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

Литература

1. Артюхин, В.В. Методическое пособие по дисциплине «Компьютерная графика» «Математическое обеспечение и администрирование информационных систем» /В.В.Артюхин; Московский государственный университет экономики, статистики и информатики. – М., 2001. - 56 с.

2. Блинова, Т.А. Компьютерная графика / Т.А.Блинова, В.Н.Порев – К.: Издательство Юниор, СПб.: КОРО­НА принт. К.:Век+, 2006. – 520с

3. Борковский, А. Б. Англо-русский словарь по программированию и информа­тике (с толкованиями) / А. Б. Борковский — М.: Рус. яз., 1989. — 335 с.

4. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. — http://www.comression.ru.

5. Вернер, А. В. Геометрия. Ч. I. Учебное посо­бие / А. В.Вернер, Б. Е.Кантор, С. А.Франгулов — СПб.: Специальная литература, 1997. — 352 с.

6. Вернер, А. В. Геометрия. Ч. II. Учебное посо­бие / А. В.Вернер, Б. Е.Кантор, С. А.Франгулов - СПб.: Специальная литература, 1997. — 320 с.

7. Википедия - свободная энциклопедия - http://ru.wikipedia.org/wiki/

8. Глоссарий.ru – Словарь по естественным наукам -www.glossary.ru

9. Залогова, Л.А. Компьютерная графика. Практикум/ Л.А.Залогова. – 2-е изд. – М.:Лаборатория Базовых Знаний, 2005. – 320с.

10. Кишик, А.Н. Adobe Photoshop 7.0. Эффективный самоучитель / А.Н. Кишик - СПб.: ООО «ДиаСофтЮП», 2003. -368с.

11. Клецель, А. Форматы графических файлов - http://www.list.soft.ru.

12. Корн, Г. Справочник по математике (для научных работников и инженеров) / Г. Корн, Т. Корн - М.: Наука, 1984. - 832 с.

13. Миронов, Д.Ф.Компьютерная графика в дизайне: Учебник для вузо­в/ Д.Ф.Миронов – СПб.:Питер, 2004. – 224с.

14. Майкл Вычислительная геометрия и компьютерная графика на C++: Пер. с англ. / Майкл, Ласло - М.: Бином, 1997. - 304 с.

15. Медицинская энциклопедия [Электронный ресурс] – Малая медицинская энциклопедия, Популярная медицинская эн­циклопедия «Первая медицинская помощь», Энциклопедичес­кий словарь медицинских терминов. (2CD). – Екатеринбург.: Золотой фонд российских энциклопедий, 2004. – 2 электрон­ных оптических диска (CD ROM) – Системные требования: Windows 98/Me/2000/XP; Pentium II 266 МГц; 64 Мб ОЗУ; SVGA 16 бит; 800х600; 4-х CD ROM или DVD дисковод; 250 Мб своб. Места на ЖД; мышь; модем 14,4 Кб/с для доступа в Интернет (желательно).

16. Мусхелишвили, Н. И. Курс аналитической геометрии / Н. И. Мусхелишвили - М.: Высшая школа, 1967. - 656 с.

17. Никулин, Е.А. Компьютерная геометрия и алгоритмы машинной графики / Е.А. Никулин – СПб.: БХВ-Петербург, 2005. – 576 с.

18. Симонович, С.В. Специальная ин­форматика: Учебное пособие / С.В.Симонович, Г.А. Евсеев, А.Г. Алексеев – М.: АСТ-ПРЕСС: Инфорком-Пресс, 2001. – 480с.

19. Страустрап, Б. Язык программирования C++. В 2-х частях/ Б. Страустрап - Киев: ДиаСофт, 1993.

20. Федер, Е. Фракталы / Е.Федер - М.: Мир, 1991. - 254 с.

21. Шикин, А.В. Компьютерная графика. Полиго­нальные модели / А.В.Шикин, А.В.Боресков – М.: ДИАЛОГ-МИФИ, 2005. – 464 с.

Елена Федоровна Попова, канд. техн. наук, доцент кафедры информатики

Компьютерная графика:

Курс лекций

План университета 2007 г.

Лицензия ЛР № 040326 от 19.XII.1997 г.

Подписано в печать Формат бумаги 60х84 1/16

Бумага тип. № 1 Уч. изд. л.

Тираж Заказ №

Издательство Благовещенского государственного

педагогического университета

Типография БГПУ. 675000, Амурская обл., Благовещенск,

ул. Ленина, 104.

[1] Графический примитив (Graphic primitive) - простейший геометрический объект, отображаемый на экране дисплея или на рабочем поле графопостроителя: точка, отрезок прямой, дуга окружности или эллипса, прямоугольник и т.п. (Словарь по естественным наукам. Глоссарий.ру).

[2] От английского three dimensions - три измерения.

[3] Пьер Безье (P.Bezier) – французский математик, который применял математические кривые и поверхности в процессе конструирования кузова автомобиля Рено.

[4] OPI (Open Prepress Interface) - технология, разработанная фирмой Aldus, позволяющая импортировать не оригинальные файлы, а их образы, создавая в программе лишь копию низкого разрешения (эскиз) и ссылку на оригинал. В процессе печати на принтер, эскизы подменяются на оригинальные файлы. Применение OPI, вместо простого внедрения, (embedding) дает возможность экономить ресурсы компьютера (прежде всего, память), заметно повышая его производительность.

[5] От английского two dimensions – два измерения.