Алгоритм сжатия файлов следующих форматов bmp gif jpeg

Обновлено: 07.07.2024

Типичное изображение, полученное цифровой фотокамерой, имеет разрешение порядка 3000x2000 , т.е. около 6 мегапикселей; для передачи цвета обычно используется 24 бита на пиксель. Таким образом, объем исходных данных составляет порядка 17 мегабайт . Для профессиональных устройств ввода изображений размер получаемого растра может быть значительно больше, а глубина цвета - достигать 48 бит на пиксель ( "Современные аппаратные средства растровой графики" ). Соответственно, размер одного изображения может быть больше 200 мегабайт . Поэтому весьма актуальными являются алгоритмы сжатия изображений, или, иными словами, алгоритмы, которые позволяют уменьшить объем данных, представляющих изображение.

Существуют два основных класса алгоритмов:

A называется алгоритмом сжатия без потерь (англ. lossless compression ), если существует алгоритм A -1 (обратный к A ) такой, что для любого изображения I A(I) = I₁ и A -1 (I₁) = I . Изображение I задано как множество значений атрибутов пикселей; после применения к I алгоритма A получаем набор данных I₁ . Сжатие без потерь применяется в таких графических форматах представления изображений, как: GIF, PCX , PNG, TGA , TIFF 1 Вообще говоря, данный формат также поддерживает сжатие с потерями. , множество собственных форматов от производителей цифровых фотокамер, и т.д.);
A называется алгоритмом сжатия c потерями (англ. lossy compression ), если он не обеспечивает возможность точного восстановления исходного изображения. Парный к A алгоритм, обеспечивающий примерное восстановление, будем обозначать как A * : для изображения I A(I) = I₁ , A * (I₁) = I₂ и при этом полученное восстановленное изображение I₂ не обязательно точно совпадает с I . Пара A, A * подбирается так, чтобы обеспечить большие коэффициенты сжатия и тем не менее сохранить визуальное качество, т.е. добиться минимальной разницы в восприятии между I и I₂ . Сжатие с потерями применяется в следующих графических форматах: JPEG, JPEG2000 и т.д.

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

13.2. Несуществование идеального алгоритма

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

Утверждение 13.2.1. Не существует алгоритма, сжимающего без потерь любой набор данных.

Существует 2 N последовательностей размера N битов _^" />
(будем рассматривать бит как минимальный носитель информации). Пусть найдется алгоритм A такой, что , где |I| - объем данных (длина последовательности). Пусть M = max M_k , тогда M < N . Существует 2 1 + 2 2 + . + 2 M последовательностей длины, меньшей или равной M . Но 2 1 +2 2 +. +2 M = 2 M+1 -2 < 2 N . Противоречие.

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

13.3. Алгоритмы кодирования длины повторения (RLE)

Этот тип алгоритмов (алгоритмы кодирования длины повторения 2 В литературе часто встречается и другое название - групповое кодирование. ( RLE 3 англ. Run Length Encoding )) базируется на простейшем принципе: будем заменять повторяющиеся группы элементов исходной последовательности на пару (количество, элемент), либо только на количество.

RLE - битовый уровень

Будем рассматривать исходные данные на уровне последовательности битов; например, представляющих черно-белое изображение. Подряд обычно идет несколько 0 или 1 , и можно помнить лишь количество идущих подряд одинаковых цифр. Т.е. последовательности 0000 11111 000 11111111111 соответствует набор чисел количеств повторений 4 5 3 11 . Возникает следующий нюанс: числа, обозначающие количество повторений, также надо кодировать битами. Можно считать, что каждое число повторений изменяется от 0 до 7 (т.е. можно закодировать ровно тремя битами), тогда последовательности 11111111111 можно сопоставить числа 7 0 4 , т.е. 7 единиц, 0 нулей, 4 единицы. Для примера, последовательность, состоящая из 21 единицы, 21 нуля, 3 единиц и 7 нулей закодируется так: 111 000 111 000 111 111 000 111 000 111 011 111 , т.е. из исходной последовательности, которая имеет длину 51 бит, получили последовательность длиной 36 бит.

Идея этого метода используется при передаче факсов.

RLE - байтовый уровень

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

Будем разбивать входной поток на байты (буквы) и кодировать повторяющиеся буквы парой (количество, буква).

Т.е. AABBBCDAA кодируем (2A) (3B) (1C) (1D) (2A) . Однако могут встречаться длинные отрезки данных, где ничего не повторяется, а мы кодируем каждую букву парой (цифра, буква).

Пусть у нас есть фиксированное число (буква) M (от 0 до 255 ). Тогда одиночную букву можно закодировать ею самою, - выход = S , а если букв несколько или , то выход = CS , где C > M , а C - M - количество идущих подряд букв S . Для примера приведем только алгоритм декодирования.

Листинг 13.1. Алгоритм декодирования RLE - байтовый уровень

Число M обычно равно 127 . Чаще используется модификация этого алгоритма, где признаком счетчика служит наличие единиц в 2 старших битах считываемого символа. Остальные 6 битов суть значение счетчика.

Такая модификация данного алгоритма используется в формате PCX . Однако модификации данного алгоритма редко используются сами по себе, т.к. подкласс последовательностей, на которых данный алгоритм эффективен, относительно узок. Модификации алгоритма используются как одна из стадий конвейера сжатия (например в формате JPEG, "Сжатие изображений с потерями" ).

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

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

Оценки методов сжатия:

степень сжатия – отношение объема сжатого файла к объему исходного файла;
точность восстановления – среднеквадратичное отклонение значений пикселей сжатого изображения от оригинала;
скорость компрессии и декомпрессии – суммарное время сжатия и восстановления;
симметричность – отношение времени сжатия ко времени восстановления.

Все существующие алгоритмы можно разделить на два больших класса:

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

Алгоритмы на основе статистических характеристик ставят наиболее частым элементам последовательностей наиболее короткий сжатый код

Алгоритмы серии RLE (англ. run-length encoding или кодирование повторов) основаны на очень простой идее: повторяющиеся группы элементов заменяются на числа повторов. Пример: последовательности из 21 бит (11111 000000 11111111 00) соответствует набор чисел 5 6 8 2. Этот набор при 3-х битном кодировании каждого числа (от 0 до 7) может быть представлен последовательностью из 18 бит 5 6 7 0 1 2 (101 110 111 000 001 010).

Алгоритм Шенона-Фано:

Символы первичного алфавита m₁ выписывают по убыванию вероятностей.
Символы полученного алфавита делят на две части, суммарные вероятности символов которых максимально близки друг другу.
В префиксном коде для первой части алфавита присваивается двоичная цифра «0», второй части — «1».
Полученные части рекурсивно делятся и их частям назначаются соответствующие двоичные цифры в префиксном коде.

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

Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который равен частоте появления символа.
Выбираются два свободных узла дерева с наименьшими весами.
Создается их родитель с весом, равным их суммарному весу.
Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.
Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.
Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Алгоритм арифметического кодирования:

Рассмотрим в качестве примера строку abacaba :

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

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

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

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

Здесь под символом подразумевается некий повторяющийся элемент исходной строки — это может быть как печатный знак (character), так и любая битовая последовательность. Под кодом подразумевается не ASCII или UTF-8 код символа, а кодирующая последовательность битов.

Рассмотрим пример сжатия этим алгоритмом. Будем сжимать строку кукушкакукушонкукупилакапюшон. Исходный словарь заполнен следующим образом:

Процесс сжатия отражен в следующей таблице:

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

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

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

Метод JPEG включает три последовательных этапа:

Предварительная обработка изображения.
Спектральное преобразование данных.
Квантование спектра и сжатие данных.

На 1-м этапе выполняются:

переход к цветоразностной модели;
разделение изображения на блоки;
«прореживание» блоков цветовых составляющих.

Формируются блоки размером 8×8 пикселов, которые обрабатываются при сжатии независимо друг от друга.

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

Формально при этом коэффициенты Pxy исходной матрицы P преобразуется в коэффициенты dij матрицы D согласно приведенной на рисунке формуле.

Смысл преобразования заключается в том, что коэффициенты dij отражают «амплитуду колебаний» яркости пикселей. Например, если все пиксели блока имеют одинаковую яркость, то максимальными будет коэффициент d11 , а остальные dij = 0.

На третьем этапе выполняется собственно огрубление коэффициентов с потерями информации и сжатие данных блоков.

Первоначально все коэффициенты матрицы D делятся с отбрасыванием дробной части на некоторые установленные делители. В примере такой делитель принят равным 8. В реальном алгоритме JPEG делители увеличиваются с возрастанием частот (на рисунке приведен фрагмент реальной матрицы делителей, в котором отображены первые 16 значений из 63).

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

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

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

Чем больше степень сжатия, тем большими задаются делители. В практическом алгоритме они увеличиваются в направлении правого нижнего угла матрицы D. В результате этой операции строка из 64 коэффициентов матрицы содержит длинные последовательности «0» и удобна для окончательного сжатия. Такое сжатие выполняется с использованием метода RLE для цепочек нулей и кодирования по Хаффмену остальных коэффициентов. В результате, как правило, объем исходного графического файла сокращается в 10-20 раз. Возможно задавать и большую степень сжатия, учитывая требования к качеству восстановленного изображения.

Более детально особенности обработки уже знакомого нам блока изображения отражены на рисунке.

Вам известна разница между JPEG, GIF, PNG и другими графическими форматами? Когда нужно использовать тот или иной формат, или какой лучше всего подойдет для сохранения фотографий? Ниже вы найдете ответы на все эти вопросы.

Алгоритмы сжатия данных с потерями / без потерь

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

Формат файлов, содержащий необработанную информацию, поступающую напрямую с матрицы полупрофессиональной и профессиональной фотокамер. Эти файлы не обрабатываются процессором камеры и содержат всю отснятую информацию в «сыром» виде. Размер таких файлов может превышать 25 МБ. Файлы RAW отлично подойдут для редактирования, однако из-за большого размера хранить их не слишком удобно.

.JPEG (JPG)

Это, пожалуй, самый распространенный графический формат. Обычно он используется для публикации в интернете фотографий и изображений с текстом. JPEG является TrueColor-форматом, то есть может хранить изображения с глубиной цвета 24 бит/пиксель. Данный формат может отображать более 16 млн цветов.

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

JPEG с высоким качеством (100). Размер 113 КБ

JPEG со средним качеством (50). Размер 59 КБ

JPEG с низким качеством (20). Размер 27 КБ

Формат GIF (Graphics Interchange Format) не радует глубиной цвета (8 бит). Он может хранить сжатые без потери данных изображения в формате не более 256 цветов. Одной из особенностей GIF является поддержка анимации.

ПО ТЕМЕ:

Данный формат был разработан в качестве замены GIF. Расшифровывается PNG как Portable Network Graphics. В отличии от GIF, у PNG есть поддержка градаций прозрачности за счет дополнительного альфа-канала. Обычно на прозрачность указывает шахматный фон, как видно из расположенного ниже изображения.

Внешне файлы в формате PNG практически не отличаются от JPG-изображений. PNG сжимает данные без потерь. Если для вас важна прозрачность, лучше выбирать именно этот формат.

Данная аббревиатура расшифровывается как Tagged Image File Format. Это высококачественный формат, использующийся для хранения изображений с большой глубиной цвета. Файлы TIFF могут храниться как в сжатом, так и в распакованном виде. Большим достоинством формата остается поддержка практически любого алгоритма сжатия.

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

Формат BMP (bitmap) один из первых графических форматов и в настоящее время не слишком популярен. BMP хранит изображения с глубиной цвета до 64 бит. Данный формат поддерживает прозрачность, однако он не читается некотороми приложениями Microsoft. Иными словами, файлы BMP лучше конвертировать в другие форматы.

Так какой же формат следует использовать?

Оптимальным выбором будет формат PNG. Он отлично подойдет для изображений большого размера. Если требуется большая степень сжатия, например, для отправки фото по электронной почте, лучше воспользоваться JPEG. Формат TIFF достаточно сложен для работы и практически не поддерживается в браузерах.

Ниже опубликована сравнительная таблица характеристик различных форматов.

Презентация на тему: " Алгоритмы сжатия изображений. Сжатие – представление информации в более эффективном виде, влекущее за собой уменьшение объема данных (как правило). В." — Транскрипт:

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

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

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

4 Сжатие без потерь RLE (Run Length Encoding) LZW (Lempel, Ziv, Welch) Метод Хаффмана (Huffman)

5 Алгоритм группового кодирования RLE Изображение вытягивается в цепочку байт по строкам растра. Серия повторяющихся величин (значений пиксела) заменяется одной величиной и количеством ее повторений. Abbbbbbbccdddeeee – 1a7b2c3d4e Этот подход хорошо работает с длинными сериями повторяющихся величин, т.е. с изображениями с большими областями постоянной яркости (или цвета). Используется во многих форматах bitmap файлов – TIFF, GEM, PCX и других.

6 Характеристики RLE Худший, средний, лучший коэффициенты сжатия: 32 – 2 – 0.5 Класс изображений: небольшое количество цветов (деловая и научная графика) Симметричность: 1 Особенности алгоритма: не требует дополнительной памяти при архивации и разархивации, быстро работает.

7 Алгоритм LZW Метод назван по первым буквам фамилий его разработчиков: Lempel, Ziv, Welch. Сжатие осуществляется за счет одинаковых цепочек байт (шаблонов). Алгоритм создает таблицу кодов, представляющих повторяющиеся пиксельные «узоры», начиная с простой таблицы и формирует более эффективную таблицу по мере своего продвижения – этот алгоритм является адаптивным. Включен в несколько форматов файлов: GIF, TIFF (с правом выбора). (словарный алгоритм)

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

10 Сжатие с потерями JPEG JPEG 2000 (Wavelet) Фрактальное сжатие

11 Оценка потерь качества Базовая метрика оценки качества сжатия – PSNR (peak-to-peak signal-to-noise ratio) Хорошо работает только на высоком качестве.

12 Алгоритм JPEG Разработан в 1991 г. группой экспертов в области фотографии (Joint Photographic Expert Group – подразделение в рамках ISO) специально для сжатия 24-битных изображений. Основу алгоритма составляет дискретное косинусное преобразование Фурье (DCT) Оперирует блоками 8 х 8, внутри которых яркость и цвет меняются сравнительно плавно.

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

14 Характеристики алгоритма JPEG Степень сжатия: (задается пользователем) Класс изображений: полноцветные 24-битные изображения или изображения в градациях серого без резких переходов цветов (фотографии) Симметричность: 1 Характерные особенности: эффект облачности при высоких степенях сжатия и «ореолы» вокруг резких вертикальных и горизонтальных границ.

15 ПримерJPEG Фотография заката в формате JPEG с уменьшением степени сжатия слева направо

16 Сравнение JPEG и JPEG2000 Большая степень сжатия при том же качестве для высоких степеней сжатия Поддержка кодирования отдельных областей с лучшим качеством DCT заменено на DWT (wavelet-преобразование), что позволило избежать облачности и достичь плавного проявления изображения Вместо кодирования по методу Хаффмана используется более эффективное арифметическое кодирование Поддержка сжатия без потерь Поддержка сжатия 1-битных изображений Поддержка прозрачности при помощи отдельного канала

17 JPEG и JPEG2000 при сжатии в 30 раз

18 Форматы графических файлов BMP (DIB, Device Independent Bitmap) JPEG GIF (Graphics Interchange Format) TIFF (Tag Image File Format) EPS (Encapsulated PostScript) CGM (Computer Graphics Metafile) DXF (Drawing Interchange Format) PNG (Portable Network Graphics)

Читайте также: