Методы сжатия изображения

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Реферат на тему:

«Методы сжатия изображений» 
 
 
 
 
 

Выполнил:  
 
 
 
 
 
 
 
 
 
 
 

Абакан 2006 

Введение

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

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

 

Методы  сжатия без потерь

Энтропийное кодирование

    В методах энтропийного сжатия длина  кода переменна и обратно пропорциональна  вероятности кодируемого символа. Количество информации I (бит), передаваемой при кодировании символа s с вероятностью p(s), определяется так:

I = log₂ (1/p(s)). 

     Энтропия  как мера количества информации, содержащейся в кодированном сообщении, характеризует вероятность появления символов. Если появление символа маловероятно, то количество информации, передаваемой этим символом, велико. Напротив, если символ встречается часто, то его новое появление не несет большого количества информации. Энтропия H (бит/символ) характеризует среднее количество информации на символ, или среднюю длину кода: 
 

H = ∑ p(s) log₂ (1/p(s)).

       ^s

 
       Энтропия дает теоретический предел значения фактора сжатия кодами переменной длины. Для иллюстрации алгоритмов энтропийного кодирования воспользуемся примером кодирования сообщения о состоянии погоды, определяемого четырьмя двухбитовыми символами «ясно» = 00, «облачно» = 01, «дождь» = 10 и «снег» = 11. Очевидно, что если все состояния погоды равновероятны (р(s) = 1/4), то H = 2 бит/символ и сжатие невозможно. Если же вероятности появления символов различаются (табл. 1), что характерно для климата большинства среднеевропейских стран, то при кодировании любого сообщения, состоящего из символов данного алфавита, энтропия определяется следующим образом:

R = 3/4 Ч 0,415 + 1/8 Ч 3,000 + 1/16 Ч 4,000 + 1/16 Ч 4,000 = 1,186 бит/символ

Таблица 1. Вероятности символов, характеризующих состояние 

         Длина кода, в отличие от количества информации, выражается целыми числами. Поэтому фактор сжатия в данном случае оценивается величиной:

       R = 3/4 * 1 + 1/8 * 2 + 1/16 * 3 + 1/16 * 3 = 1,375 бит/символ.

       Это составляет 86 % от предельного значения H. Решающее влияние на эффективность энтропийного кодирования оказывает адекватный выбор вероятностей появления символов. Так, длина кодированного сообщения о состоянии зимой, в котором преобладают символы «снег», может оказаться в 1,5 раза нее исходного сообщения.

Группировка символов алфавита позволяет существенно увеличить эффективность энтропийного кодирования. Пусть кодируются не сами состояния погоды, а их изменения, причем вероятность повторения события равна 3/4, а вероятность любого изменения равна 1/12. Тогда возможные комбинации символов изменения состояния следует дополнить новыми композитными символами, вероятности появления независимых событий для которых перечислены в таблице 2.

Таблица 2. Вероятности появления независимых событий для композитных символов 

 

     Здесь энтропия и фактор сжатия соответственно оцениваются так:

H = 9/16 * 0,830 + 3 * 1/12 * 3,585 + 3 * 1/16 *4,000 = 2.113 бит/композитный символ;

R = 9/16 Ч 1 + 3 Ч 1/12 Ч 3 + 3 Ч 1/16 Ч 4 = 2,145 бит/композитный символ

Это составляет 98,5 % от предельного значения H. Отметим, что на 4 композитных символа данного алфавита приходится по два исходных символа изменения состояния, поэтому H = 1,208, а фактический фактор сжатия R = 1,226 в пересчете на исходный символ.

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

Энтропийное кодирование используется всеми  известными архиваторами текстовых файлов, а также на завершающей стадии сжатия изображений в стандартах JPEG и МРEG, векторного квантования и волнового преобразования.

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

     Арифметическое  кодирование не связано ограничением на значения вероятностей, а фактор сжатия на 5-10 % больше, чем кода Хаффмана. Каждому символу ставится в соответствие интервал от 0 до 1, равный его вероятности, причем одна из границ принадлежит интервалу. Чем меньше вероятность символа, тем короче интервал его представления, хотя число бит, определяющих длину интервала, увеличивается. Поскольку длина кода символа приближается к количеству информации, то при большом числе символов средняя длина кода стремится к энтропийному пределу. При кодировании достаточно длинного сообщения длина интервала P стремится к величине Р = р(s1) * р(s2) * ... * р(sп), а число бит для его представления приближается к -log₂(Р). 
 

QT: кодирование квадродерева

     Кодирование квадродерева дает хорошие результаты при сжатии таких специфических изображений, как тематические карты классификации или снимки звездного неба. Построение квадродерева сводится к рекурсивному процессу разбиения бинарного сечения изображения на 4 квадранта. Этот процесс иллюстрирован па примере карты состояния погоды размером 8 * 8 бит, состоящей всего из двух символов «ясно» = 0 и «снег» = 1 (табл.3).

Таблица 3: Кодирование квадродерева 

 

     Текущий квадрант, содержащий только нулевые (белые) символы бинарного сечения, считается листом квадродерева и отмечается элементом кода Хаффмана 0. Неоднородный квадрант отмечается элементом 1 и разбивается далее — до уровня отдельных символов. Кодирование квадродерева выполняется в направлении от корня: «ясно 4x4» - 0; «ясно 2x2» - 10; «ясно 1x1» - 110; «снег 1x1» - 111, При этом фактор сжатия

     R = 64 / (2 * 1 + 5 * 2 + 12 * 3) = 1,33.  
 
 
 

     Методы  сжатия с потерями

JPEG: кодирование неподвижных изображений

     JPEG обеспечивает высокую степень сжатия изображений без заметных видимых потерь информации, используя известные ограничения зрения — цветовые изменения деталей различаются хуже, нежели перепады контраста. Однако малые погрешности, внесенные при сжатии, могут влиять на результат обработки, даже если визуально они совершенно незаметны. В основу сжатия и декомпрессии положены, соответственно, прямое  и инверсное дискретное косинусное преобразование блоков данных размером 8x8 элементов. Стандарт JРЕС имеет несколько модификаций:           

     1) Последовательное однопроходное кодирование исходного изображения -элемент за элементом, строка за строкой. Этот базовый вариант нашел наиболее широкое распространение и имеет множество программных и аппаратных реализаций.

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

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

     4) Иерархическое кодирование — строится «пирамида» изображений с пространственными разрешениями 1:1, 1:2, 1:4,.., по отношению к исходному изображению. Изображение более высокого разрешения определяется как разность с предыдущим уровнем пирамиды.

     Алгоритм  сжатия начинается с преобразования трехцветного RGB-изображения в цветовое пространство с координатами YUV . Яркостная составляющая изображения : Y = 0.3; R + 0.6; G+ 0.1 B

передается  со значительно меньшими потерями, нежели две цветоразностные составляющие изображения:

U=B-Y, V = R-Y.

     Для монохромных изображений этот шаг  опускается.

Над каждым блоком 8x8 элементов каждой их составляющих У, U и V исходного изображения f(х,у) производится двумерное преобразование, давая по 64 коэффициента пространственно-частотного спектра F(u,v):

                                      _{7       7}

      F(u,v)=C(u)*C(v) 

                       4            ^{x=0   y=0}                                       16                                    16 
 

     Каждое  значение F(u, v) делится на соответствующий коэффициент таблицы квантования Q(u, v) и округляется до ближайшего целого, давая матрицу FQ(u,v). Именно квантование является источником потерь информации при заданной величине параметра «качество» Q: чем выше частота, тем больше коэффициент ее квантования и, следовательно, хуже точность ее восстановления. Для интервала Q [50,100] коэффициенты таблиц квантования пересчитываются по формуле:

Q(u, v)= Q(u, v)*(200-2*Q)/100,

то есть при Q = 75 коэффициенты уменьшаются вдвое, а при Q = 100 обращаются в 1 и JPEG не вносит потерь на стадии квантования. Для интервала Q [1,50] коэффициенты таблиц квантования пересчитываются по формуле:

Q(u, v)= Q(u, v)*(50/Q),

то есть при Q = 25 коэффициенты увеличиваются вдвое, а при Q = 50 не изменяются.

     Яркостная и цветоразностные составляющие квантуются по разным таблицам, причем передается только каждая четвертая квантованная частота цветоразностей. Разработанный для цифрового телевизионного стандарта CCIR-601 набор таблиц квантования хорошо зарекомендовал себя для большого числа тестовых изображений и был принят в стандарте JPEG. Несимметричность стандартной таблицы квантования яркостной составляющей (табл. 4) объясняется разной чувствительностью глаза к изменениям контраста в вертикальном и горизонтальном направлениях.