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




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


    Предисловие
    Предисловие Спецкурс “Машинная графика-2” читается на факультете ВМиК МГУ уже более 10 лет. Являясь логическим продолжением общего курса “Машинная графика”, спецкурс более углубленно и детально ра...
    Введение
    Введение В течение последних 10 лет в рамках компьютерной графики бурно развивается совершенно новая область — алгоритмы архивации изображений. Появление этой области обусловлено тем, что изображе...
    Классы изображений
    Классы изображений Статические растровые изображения представляют собой двумерный массив чисел. Элементы этого массива называют пикселами (от английского pixel — picture element). Все изображения...
    Пример
    Пример 8 Нет смысла говорить о том, что какой-то конкретный алгоритм компрессии лучше другого, если мы не обозначили класс приложений , для которого мы эти алгоритмы собираемся сравнивать. Требова...
    Критерии сравнения алгоритмов
    Критерии сравнения алгоритмов Заметим, что характеристики алгоритма относительно некоторых требований приложений, сформулированные выше, зависят от конкретных условий, в которые будет поставлен ал...
    Контрольные вопросы к разделу
    Контрольные вопросы к разделу Какие параметры надо определить, прежде чем сравнивать два алгоритма компрессии? Почему некорректно сравнивать временные параметры реализаций алгоритмов компрессии, о...
    Первый вариант алгоритма
    Первый вариант алгоритма Данный алгоритм необычайно прост в реализации. Групповое кодирование — от английского Run Length Encoding (RLE) — один из самых старых и самых простых алгоритмов архивации...
    Упражнение 1
    Упражнение 1 Составьте алгоритм компрессии для первого варианта алгоритма RLE. Алгоритм рассчитан на деловую графику — изображения с большими областями повторяющегося цвета. Ситуация, когда файл у...
    Второй вариант алгоритма
    Второй вариант алгоритма Второй вариант этого алгоритма имеет больший максимальный коэффициент архивации и меньше увеличивает в размерах исходный файл. Алгоритм декомпрессии для него выглядит так:...
    Упражнение 2
    Упражнение 2 Составьте алгоритм компрессии для второго варианта алгоритма RLE. Похожие схемы компрессии использованы в качестве одного из алгоритмов, поддерживаемых форматом TIFF, а также в формат...
    Пример 9 Название алгоритм получил...
    Алгоритм LZ Существует довольно большое семейство LZ-подобных алгоритмов, различающихся, например, методом поиска повторяющихся цепочек. Один из достаточно простых вариантов этого алгоритма, напри...
    Упражнение 3
    Упражнение 3 Предложите другой вариант алгоритма LZ, в котором на пару счетчик, смещение> будет выделено 3 байта, и подсчитайте основные характеристики своего алгоритма. Алгоритм LZW Рассматриваем...
    Пример 10LZW: Коэффициенты компрессии: Пример 11
    Пример 11 1000, 4, 5/7 (Лучший, средний, худший коэффициенты). Сжатие в 1000 раз достигается только на одноцветных изображениях размером кратным примерно 7 Мб. Класс изображений: Ориентирован LZW...
    Классический алгоритм Хаффмана
    Классический алгоритм Хаффмана Один из классических алгоритмов, известных с 60-х годов. Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, ко...
    Определение 1.
    Пусть задан алфавит Y ={ a 1, ..., ar}, состоящий из конечного числа букв. Конечную последовательность символов из Y будем называть словом в алфавите Y , а число n — длиной слова A . Длина слова об...
    Определение 2.
    Рассмотрим соответствие между буквами алфавита Y и некоторыми словами алфавита W : a 1 — B 1, a 2 — B 2, . . . a r — B r Это соответствие называют схемой и обозначают через S . Оно определяет кодир...
    Определение 3
    Определение 3 Пусть слово В имеет вид B=B' B" Тогда слово B' называется началом или префиксом слова B, а B" — концом слова B. При этом пустое слово L и само слово B считаются началами и концами сл...
    Определение 4 Схема S обладает свойством префикса, если для любых
    i и j (1? i , j? r, i? j ) слово B i не является префиксом слова B j....
    Теорема 1. Если схема S
    Теорема 1. Если схема S обладает свойством префикса, то алфавитное кодирование будет взаимно однозначным. Предположим, что задан алфавит Y ={ a 1,..., a r } ( r >1 ) и набор вероятностей p 1 , . ....
    Определение 5 Коды, определяемые схемой S
    l ср= l *, называются кодами с минимальной избыточностью , или кодами Хаффмана. Коды с минимальной избыточностью дают в среднем минимальное увеличение длин слов при соответствующем кодировании. В...
    Пример 12
    Пример 12 Пусть у нас есть 4 буквы в алфавите Y ={ a 1,..., a 4} ( r =4 ), p 1=0.5, p 2=0.24, p 3=0.15, p 4=0.11 . Тогда процесс построения схемы можно представить так: Производя действия, соответ...
    Определение 6:
    Набор идущих подряд точек изображения одного цвета называется серией .Длина этого набора точек называется длиной серии . В таблице, приведенной ниже, заданы два вида кодов: Коды завершения серий —...
    Упражнение 6
    Упражнение 6 Дана строка изображения, записанная в виде длин серий — 442, 2, 56, 3, 23, 3, 104, 1, 94, 1, 231, размером 120 байт ((442+2+..+231)/8). Подсчитать коэффициент компрессии этой строки а...
    JBIG
    JBIG Алгоритм разработан группой экспертов ISO (Joint Bi-level Experts Group) специально для сжатия однобитных черно-белых изображений [5]. Например, факсов или отсканированных документов. В принц...
    Lossless JPEG
    Lossless JPEG Этот алгоритм разработан группой экспертов в области фотографии (Joint Photographic Expert Group). В отличие от JBIG, Lossless JPEG ориентирован на полноцветные 24-битные или 8-битны...
    Заключение
    Заключение Попробуем на этом этапе сделать некоторые обобщения. С одной стороны, приведенные выше алгоритмы достаточно универсальны и покрывают все типы изображений, с другой — у них, по сегодняшн...
    Контрольные вопросы к разделу
    Контрольные вопросы к разделу На какой класс изображений ориентирован алгоритм RLE? Приведите два примера “плохих” изображений для первого варианта алгоритма RLE, для которых файл максимально увел...
    Проблемы алгоритмов архивации с потерями
    Проблемы алгоритмов архивации с потерями Первыми для архивации изображений стали применяться привычные алгоритмы. Те, что использовались и используются в системах резервного копирования, при созда...
    Алгоритм JPEG
    Алгоритм JPEG JPEG — один из самых новых и достаточно мощных алгоритмов. Практически он является стандартом де-факто для полноцветных изображений [1]. Оперирует алгоритм областями 8х8, на которых...
    Шаг 1.
    Шаг 1. Переводим изображение из цветового пространства RGB, с компонентами, отвечающими за красную (Red), зеленую (Green) и синюю (Blue) составляющие цвета точки, в цветовое пространство YCrCb (ин...
    Шаг 2.
    Шаг 2. Разбиваем исходное изображение на матрицы 8х8. Формируем из каждой три рабочие матрицы ДКП — по 8 бит отдельно для каждой компоненты. При больших коэффициентах сжатия этот шаг может выполня...
    Шаг 3.
    Шаг 3. Применяем ДКП к каждой рабочей матрице. При этом мы получаем матрицу, в которой коэффициенты в левом верхнем углу соответствуют низкочастотной составляющей изображения, а в правом нижнем —...
    Шаг 4.
    Шаг 4. Производим квантование. В принципе, это просто деление рабочей матрицы на матрицу квантования поэлементно. Для каждой компоненты (Y, U и V), в общем случае, задается своя матрица квантовани...
    Шаг 6.
    Шаг 6. Свертываем вектор с помощью алгоритма группового кодирования. При этом получаем пары типа (пропустить, число), где “пропустить” является счетчиком пропускаемых нулей, а “число” — значение,...
    Шаг 7.
    Шаг 7. Свертываем получившиеся пары кодированием по Хаффману с фиксированной таблицей. Процесс восстановления изображения в этом алгоритме полностью симметричен. Метод позволяет сжимать некоторые...
    Существенными положительными сторонами алгоритма является то, что:
    Существенными положительными сторонами алгоритма является то, что: Задается степень сжатия. Выходное цветное изображение может иметь 24 бита на точку. Отрицательными сторонами алгоритма является т...
    Идея метода
    Идея метода Фрактальная архивация основана на том, что мы представляем изображение в более компактной форме — с помощью коэффициентов системы итерируемых функций (Iterated Function System — далее...
    Упражнение 7
    Упражнение 7 Из вышесказанного становится понятно, как работает архиватор, и почему ему требуется так много времени. Фактически, фрактальная компрессия — это поиск самоподобных областей в изображе...
    Определение 7
    Определение 7 Преобразование , представимое в виде где a, b, c, d, e, f действительные числа и называется двумерным аффинным преобразованием ....
    Определение 8
    Определение 8 Преобразование , представимое в виде где a, b, c, d, e, f, p, q, r, s, t, u действительные числа и называется трехмерным аффинным преобразованием....
    Определение 9.
    Пусть — преобразование в пространстве Х. Точка такая, что называется неподвижной точкой (аттрактором) преобразования....
    Определение 10.
    Преобразование в метрическом пространстве (Х, d) называется сжимающим, если существует число s: , такое, что Замечание: Формально мы можем использовать любое сжимающее отображение при фрактальной...
    Теорема. (О сжимающем преобразовании)
    Теорема. (О сжимающем преобразовании) Пусть в полном метрическом пространстве (Х, d ). Тогда существует в точности одна неподвижная точка этого преобразования, и для любой точки последовательность...
    Определение 11
    Определение 11 Изображением называется функция S, определенная на единичном квадрате и принимающая значения от 0 до 1 или Пусть трехмерное аффинное преобразование , записано в виде и определено на...
    Определение 12.
    Конечная совокупность W сжимающих трехмерных аффинных преобразований , определенных на областях , таких, что и , называется системой итерируемых функций ( IFS). Системе итерируемых функций однозна...
    Построение алгоритма
    Построение алгоритма Как уже стало очевидным из изложенного выше, основной задачей при компрессии фрактальным алгоритмом является нахождение соответствующих аффинных преобразований. В самом общем...
    Схема алгоритма декомпрессии изображений
    Схема алгоритма декомпрессии изображений Декомпрессия алгоритма фрактального сжатия чрезвычайно проста. Необходимо провести несколько итераций трехмерных аффинных преобразований, коэффициенты кото...
    Оценка потерь и способы их регулирования
    Оценка потерь и способы их регулирования При кратком изложении упрощенного варианта алгоритма были пропущены многие важные вопросы. Например, что делать, если алгоритм не может подобрать для каког...
    Рекурсивный (волновой) алгоритм
    Рекурсивный (волновой) алгоритм Английское название рекурсивного сжатия — wavelet. На русский язык оно переводится как волновое сжатие, и как сжатие с использованием всплесков. Этот вид архивации...
    Упражнение 8
    Упражнение 8 Мы восстановили из файла цепочку (215, 211) (0, 5) (5, -3, 2, 4) (см. пример). Постройте строку из восьми значений яркости пикселов, которую воссоздаст алгоритм волнового сжатия. Алго...
    Результат
    B4 Используя эти формулы, мы для изображения 512х512 пикселов получим после первого преобразования 4 матрицы размером 256х256 элементов: -- В первой, как легко догадаться, будет храниться уменьшен...
    Заключение
    Заключение В заключение рассмотрим таблицы, в которых сводятся воедино параметры различных алгоритмов сжатия изображений, рассмотренных нами выше. Алгоритм Особенности изображения, за счет которых...
    Контрольные вопросы к разделу
    Контрольные вопросы к разделу В чем разница между алгоритмами с потерей информации и без потери информации? Приведите примеры мер потери информации и опишите их недостатки. За счет чего сжимает из...
    Литература по алгоритмам сжатия
    Литература по алгоритмам сжатия [1] G.K.Wallace “The JPEG still picture compression standard” // Communication of ACM. Volume 34. Number 4 April 1991. [2] B.Smith, L.Rowe “Algorithm for manipulati...
    Литература по форматам изображений
    Литература по форматам изображений [17] А.С.Климов “Форматы графических файлов” // НИПФ “ДиаСофт Лтд”, 1995. [18] В.Ю.Романов “Популярные форматы файлов для хранения графических изображений на IBM...
    Архивация двуцветного изображения
    Архивация двуцветного изображения Изображение 1000х1000х2 цвета 125.000 байт То же изображение с внесенными в него помехами Ниже приведена степень компрессии изображений в зависимости от применяем...
    Выводы, которые можно сделать
    5,1 (GIF) 4,7 (TIFF) 5,12 (TIFF) Выводы, которые можно сделать, анализируя данную таблицу: Лучшие результаты показал алгоритм, оптимизированный для этого класса изображений CCITT Group 4 и модифик...
    Архивация 16-цветного изображения
    Архивация 16-цветного изображения Изображение 619х405х16 цвета 125.350 байт Ниже приведена степень компрессии изображений в зависимости от применяемого алгоритма: Алгоритм RLE Алгоритм LZW Первое...
    11 (TIFF-LZW)
    11 (TIFF-LZW) Выводы, которые можно сделать, анализируя данную таблицу: Не смотря на то, что данное изображение относится к классу изображений, на которые ориентирован алгоритм RLE (отвечает крите...
    Архивация изображения в градациях серого
    Архивация изображения в градациях серого Изображение 600х700х256 градаций серого сразу после сканирования. 420.000 байт. (с) А.Андреев . Рисунок к роману Сергея Лукьяненко , "Лабиринт отражений" Н...
    JPEG q=100
    2,4 (JPEG q=100) * Для формата GIF в этом случае можно получить изображение меньшего размера используя дополнительные параметры. Выводы, которые можно сделать анализируя таблицу: Лучшие результаты...
    Архивация полноцветного изображения
    Архивация полноцветного изображения Изображение 320х320хRGB — 307.200 байт Ниже приведена степень компрессии изображений в зависимости от применяемого алгоритма: Алгоритм RLE Алгоритм LZW Алгоритм...
    Выводы, которые можно сделать
    11,5 (JPEG q=100) Выводы, которые можно сделать, анализируя таблицу: Алгоритм JPEG при визуально намного меньших потерях (q=100) сжал изображение в 2 раза сильнее, чем LZW с использованием перевод...
    Архивация полноцветного изображения в 100 раз
    Архивация полноцветного изображения в 100 раз 320х320хRGB — 307.200 байт Сжатие в 100 раз JPEG (3.08Кb)...
    Сжатие в 100 раз
    Сжатие в 100 раз (3.04Кb) фрактальным алгоритмом Сжатие в 100 раз (3.04Кb) wavelet алгоритмом (ИЗОБРАЖЕНИЯ ДЛЯ WWW-варианта лекций ПЕРЕВЕДЕНЫ В JPEG хоть и максимальным качеством, но с потерями) Н...
    Достоинства такого подхода:
    Достоинства такого подхода: Сам код апплета занимает 24Кб и будучи скачан один раз позволяет распаковать любое количество изображений. Т.е. на изображениях большого размера мы получаем выигрыш сра...
    Общие положения алгоритмов сжатия изображений
    Общие положения алгоритмов сжатия изображений Введение Классы изображений Классы приложений Критерии сравнения алгоритмов Контрольные вопросы к разделу...
    Алгоритмы архивации без потерь
    Алгоритмы архивации без потерь Алгоритм RLE Алгоритм LZW Алгоритм Хаффмана JBIG Lossless JPEG Заключение Контрольные вопросы к разделу...
    Алгоритмы архивации с потерями
    Алгоритмы архивации с потерями Проблемы алгоритмов архивации с потерями Алгоритм JPEG Фрактальный алгоритм Рекурсивный (волновой) алгоритм Заключение Контрольные вопросы к разделу...
    Ссылки на ресурсы по сжатию изображений в сети
    Ссылки на ресурсы по сжатию изображений в сети (c) 1999 Ватолин Д.С. (с) 1999 Лаборатория Компьютерной Графики ВМиК МГУ им. М.В. Ломоносова...








Начало    



Книжный магазин