Алгоритм сжатия изображения jpeg

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное

учреждение высшего образования

 «ТВЕРСКОЙ  ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

Математический факультет

Кафедра компьютерной безопасности и математических методов управления

 

 

 

Реферат по дисциплине

 «Теория кодирования, сжатия и восстановления информации»

на тему «Алгоритм сжатия изображения jpeg».

 

 

 

Выполнила: студентка М-45 группы математического факультета Специальности Компьютерная безопасность Сайко Алина Владиславовна Проверила: доцент кафедры КБиММУ Семыкина Наталья Александровна

 

 

 

 

 

Тверь, 2017 г.

 

Оглавление

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

• алгоритм без потери
• алгоритм с потерей.

Мы рассмотрим алгоритм сжатия изображений JPEG:

JPEG (англ. Joint Photographic Experts Group) — один из популярных растровых графических форматов, применяемый для хранения фотоизображений и подобных им изображений.

Файлы, содержащие данные JPEG, обычно имеют расширения (суффиксы) .jpg, .jfif, .jpe или .jpeg. Однако из них .jpg является самым популярным на всех платформах.

Алгоритм JPEG позволяет сжимать изображение как с потерями, так и без потерь. Поддерживаются изображения с линейным размером не более 65535 × 65535 пикселей.

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

Область применения.

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

Формат JPEG в режиме сжатия с потерями малопригоден для сжатия чертежей, текстовой и знаковой графики, где резкий контраст между соседними пикселями приводит к появлению заметных артефактов. Такие изображения целесообразно сохранять в форматах без потерь, таких как JPEG-LS, TIFF, GIF, PNG или использовать режим сжатия Lossless JPEG.

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

JPEG не должен использоваться  и в тех случаях, когда недопустимы  даже минимальные потери, например, при сжатии астрономических или  медицинских изображений. В таких  случаях может быть рекомендован  предусмотренный стандартом JPEG режим  сжатия Lossless JPEG (который, однако, не поддерживается большинством популярных кодеков) или стандарт сжатия JPEG-LS.

 

Описание.

В 1986 году подгруппой ССIТТ были начаты исследования методов сжатия цветных и полутоновых данных для факсимильной связи. Применяемые при этом методы сжатия цветных данных очень напоминали те, которые исследовались группой JPEG. Поэтому было принято решение объединить ресурсы этих групп для совместной работы над единым стандартом.

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

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

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

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

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

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

 

Процесс сжатия.

Процесс сжатия по схеме JPEG включает ряд этапов (рис. 1):

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

 

Рассмотрим вкратце особенности каждого из перечисленных этапов. При этом хотелось бы обратить внимание на то, что декодирование JPEG осуществляется в обратном порядке.

 

 

 

Преобразование изображения в оптимальное цветовое пространство.

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

В случае применения цветового пространства яркость/цветность, например, такого, как YUV или YCbCr, достигается лучшая степень сжатия. Компонента Y представляет собой интенсивность, а U(Cb) и V(Cr) – цветность (хроматический красный, хроматический синий). Эта модель может быть переведена в RGB посредством преобразования без какой-либо коррекции насыщенности. Для полутоновых изображений (в градациях серого) используется только одна составляющая Y.

Упрощенно, перевод из цветового пространства RGB в цветовое пространство YCrCb можно представить таким образом:

Y = 0.299R + 0.587G + 0.114B

Cr = 0.5R - 0.4184G - 0.0813B + 128

Cb = 0.1687R - 0.3313G + 0.5B + 128

Обратное преобразование осуществляется так:

R = Y + 1.402Cb

G = Y - 0.34414Cr - 0.71414Cb – 128

B = Y + 1.772Cr - 128.

 

 

Субдискретизация компонентов цветности.

Большая часть визуальной информации, к которой наиболее чувствительны глаза человека, состоит из высокочастотных, полутоновых компонентов яркости (Y) цветового пространства YCbCr. Две других составляющих цветности (Сb и Сr) содержат высокочастотную цветовую информацию, к которой глаз человека менее чувствителен. Следовательно, определенная ее часть может быть отброшена и, тем самым, можно уменьшить количество учитываемых пикселей для каналов цветности.

Например, в изображении размером 1000x1000 пикселей можно использовать яркости всех 1000x1000 пикселей, но только 500х500 пикселей для каждого компонента цветности. При таком представлении каждый пиксел цветности будет охватывать ту же область, что и блок 2х2 пиксела (для яркости). В результате мы сохраним для каждого блока 2х2 всего 6 пиксельных значений (4 значения яркости и по 1 значению для каждого из двух каналов цветности) вместо того, чтобы использовать 12 значений при обычном описании. Практика показала, что уменьшение объема данных на 50% почти незаметно отражается на качестве большинства изображений.

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

 

 

 

Сегментация изображения.

Сегментация изображения применяется с целью деления его на две и более частей (подизображений). Это облегчает буферизацию данных изображения в памяти ПЭВМ, ускоряет их произвольную выборку с диска, и позволяет хранить изображения размером свыше 64х64 кб. JPEG поддерживает три типа сегментации изображений:

• Простую:

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

• Пирамидальную:

изображение также делится на сегменты, а каждый из них, в свою очередь, — на еще более мелкие сегменты. При этом используются различные уровни разрешения. Моделью такого процесса является сегментированная пирамида изображения JPEG (JPEG Tiled Image Pyramid, JTIP), отражающая процедуру создания пирамидального JPEG-изображения с несколькими уровнями разрешения.

• Комбинированную:

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

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

 

На следующем этапе, в зависимости от выбранного уровня качества, отбрасывается определенная часть чисел, представляющих тонкие детали.

Таким образом, чем выше уровень компрессии, тем больше данных отбрасывается и тем ниже качество изображения. Используя JPEG можно получить файл в 1-500 раз меньше, чем формат несжатых изображений ВМР.

 

 

 

Дискретное косинусное преобразование.

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

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

Это преобразование можно представить так:

Выражение для обратного преобразования матрицы «гармоник», применяемое при распаковке изображения записывается в виде:

По определению дискретного косинусного преобразования для его реализации требуется два вложенных цикла, и тело циклов будет выполняться n*n раз для каждого элемента матрицы дискретного косинусного преобразования.

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

 

где y - матрица исходного изображения, X - матрица постоянных коэффициентов косинусного преобразования размера n*n, значения элементов которой вычисляются по формуле

- транспонированная матрица X.

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