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

Сжатие без потерь Групповое сжатие Кодирование методом Хаффмана Схема сжатия LZW Арифметическое сжатие

Групповое сжатие Серии повторяющихся величин заменяются единственной величиной и количеством Например: abbbbbbccdddttddd => 1a6b2c3d2t3d Этот алгоритм просто реализуется и хорошо работает с длинными сериями повторяющихся величин. Например: для изображений с большими областями постоянной яркости или цвета

Одна из популярных реализаций группового сжатия – PackBits, используемая для bitmap данных на Apple Macintosh. Предполагая 8-битные данные, PackBits кодирует регулярные величины двумя битами. Для повторяющихся величин первый байт содержит n, (от (-127) до (-1)) количество повторений (-n+1). Второй байт содержит повторяющуюся величину: Неповторяющиеся величины обозначаются однобайтовым кодом m (от 0 до 127), он представляет длину последовательности минус 1 (abcde m=4). Далее сама последовательность Групповое кодирование используется в таких форматах, как MacPaint, TIFF, GEM, PCX, FLI

Кодирование методом Хоффмана (1952) Данные заменяются более эффективными кодами Этот подход, созданный для текстовых файлов, породил множество вариантов Основная схема – присвоение двоичного кода каждой уникальной величине, причем длина этих кодов различна Более короткие коды не используются для более часто появляющихся величин

Значение кодов хранятся в таблице перекодировки Например: abbbcccddeeeeeeeeef Частота, с которой повторяются уникальные величины a:1 b:3 c:3 d:2 e:9 f:1

Для формирования минимального кода используется двоичное дерево. Алгоритм объединяет вместе элементы, появляющиеся наименее часто; затем пара рассматривается как один элемент и их частоты объединяются. Это повторяется до тех пор, пока все элементы не объединяются в пары Наиболее редко используемые значения a и f, так что они становятся первой парой; a - присваивается нулевая ветвь, а f - первая. Это означает, что 0 и 1 будут младшими битами кодов для а и f. Более старшие биты будут получены из дерева по мере того, как оно будет построено. Затем частоты этих первых двух суммируются 1+1=2. Поскольку частота (этих а и f) = 2, объединяем пару с d у которой частота тоже 2. Исходной паре присваивается нулевая ветвь дерева, а - ветвь 1. Таким образом код для а заканчивается на 00, f - 01; d - заканчивается на 1 и будет на один бит короче по сравнению с кодами для а и f

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

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

Например: ababaaacaaaad Для простоты: каждая буква - два бита (всего четыре буквы). Начальная кодовая таблица: а:00, b:01, c:10, d:11. LZW ищет самую длинную последовательность. Он находит а и распознает, затем проверяет ab и не распознает. Тогда он заводит код для этой величины. а(000) и делает новый элемент для величин, которые не распознает a:000, b 001, c:010, d:011, ab:100 Шифратор затем берет последнюю величину b и проверяет последовательность со следующей величиной. ba - не распознается. Заводится код для ba. Теперь время для хорошего этапа. Шифратор и дешифратор могут определить следующий элемент ab. Трехбитный код заменяет два двух битных Типичные коэффициенты сжатия при LZW от 1:1 до 3:1, хотя некоторые изображения сжимаются 10:1. Изображение с шумом плохо сжимаются. LZW используется в gif и tiff

Арифметическое сжатие Арифметическое сжатие, подобно кодированию Хаффману, использует более короткие коды для часто появляющихся участков и более длинные для редко появляющихся. Это более эффективный алгоритм, хотя он (подобно LZW) сжимает последовательность величин, а не сами величины. Арифметическое сжатие близко подходит к теоретическим пределом для алгоритмов сжатия без потерь Возьмем для примера, множество значений пикселей представленных буквами. Предположим, что каждый пиксель в 1900-пикселовом изображение имеет одну из шести величин, и они появляются с частотами: a:100, b:300, c:300, d:200, f:100

a:100, b:300, c:300, е:900 d:200, f:100 Один из способов определения состояния этой последовательности задание вероятностей с которой появляются эти пиксели P(a)= P(b)= P(c)= P(d)= P(e)= P(f)= Серия пикселей, например eb, будет иметь вероятность P(e) x P(b)

Проблема, возникающая при этом задании в том, что вероятности не уникальны P(b)=P(c) x P(eb) = P(ec) Однако, если вероятность рассматривать как длину, то величину b можно представить сегментом от 0,0526 до 0,2105. Длина этого сегмента вероятность P(b). Величина c имеет ту же вероятность, что и b, но в другом диапазоне от 0,2105 до 0,3684. Теперь можно представить однозначно любую величину числом, любым, но принадлежащим выбранному диапазону. Например, 0,25 указывает величину c. В данном случае достаточно двух цифр Для е от до можно выбрать 0.5 Более широкий диапазон, больше вероятность, следовательно, меньше знаков

Для представления последовательности из двух символов, необходимо разбить интервал для первого символа Для eb от до Для кодирования достаточно 0,50

Так же как и код Хаффмана, арифметическое кодирование эффективно представляет изображения с более часто появляющимися последовательностями пикселей (более вероятные величины) с помощью меньшего количества бит Арифметическое сжатие может эффективно уменьшать размер файла в зависимости от распределения интенсивности и от точности используемой статистической модели. Иногда сжатие бывает 100:1

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

JPEG (Объединенная Группа Экспертов по Фотографии Международной Организации По Стандартизации (ISO) Joint Photographic Experts Group ) JPEG это сокращение используется как для обозначения формата представления графических данных, так и для алгоритма сжатия Владельцем патента 4,698,672 является фирма Compression Labs Патент был выдан 6 октября 1987 года и описывает технологию компрессии данных, применяющуюся, в частности, в широко распространенном формате JPEG

Впоследствии права на методику сжатия данных перешли компании Forgent Networks, купившей Compression Labs в 1997 году. Около двух лет назад Forgent Networks подала иски против 30 компаний, обвинив их в незаконном использовании технологий, защищённых патентом. Ответчикам было предложено выплатить компенсации и приобрести соответствующие лицензии. Лицензирование методики Compression Labs принесло Forgent Networks порядка 105 миллионов долларов США.

Однако выплачивать отчисления согласились далеко не все, и, например, Sun Microsystems и Google подали против Forgent Networks встречные иски Кроме того, против Forgent Networks выступила некоммерческая организация PUBPAT, способствующая открытию защищенных технологий. Активисты PUBPAT потребовали USPTO пересмотреть патент за номером 4,698,672, мотивирую это тем, что Forgent Networks использует его исключительно с целью наживы Управление США по патентам и торговым маркам (USPTO) в мае 2006 г. признало недействительным патент за номером 4,698,672 признало недействительным

Алгоритм JPEG начинает с разделения информации на цвет (chroma) и яркость (luminance), чтобы использовать преимущество того, что человеческий глаз допускает уменьшение пространственного разрешения для цвета. Используется систему цветопередачи YCbCr. На этой системе остановились потому, что эта система используется PAL и стандартами телевидения SECAM Затем JPEG использует Дискретное Косинусоидальное преобразование (ДКП) для под изображений размером N x N

Дискретное косинусное преобразование ДКП – наиболее широко используемое преобразование при сжатии изображения Человеческий глаз менее чувствителен к высоким компонентам частоты изображения, представленного более высокими коэффициентами ДКП. Больший коэффициент квантования обычно применяется к этим более высоким компонентам Недостатки: Появление блочных артефактов при высоком сжатии Излом острых граней. Случайное размытие в острых граней Большие требования к вычислительным мощностям

JPEG Алгоритм JPEG можно разделить на несколько этапов: 0. Подготовка 1. ДКП (Дискретно Косинусоидальное Преобразование) 2. Квантование 3. Вторичное сжатие

JPEG На первом шаге с помощью формулы дискретного косинусоидального преобразования фуры (DCT) производится преобразование блока 8 х 8 с информацией о пикселах в матрицу 8x8 амплитудных значений, отражающих различные частоты в изображении На втором шаге значения матрицы амплитуд делятся на значения матрицы квантования, которая смещена так, чтобы отфильтровать амплитуды, незначительно влияющие на общий вид изображения На третьем и последнем шаге квантованная матрица амплитуд сжимается с использованием алгоритма сжатия без потерь

Этап 0. Подготовка Чувствительность человеческого глаза к яркостному Y-компоненту и цветностным компонентам Cb и Cr неодинакова, поэтому вполне допустимо прореживание (интерливинг) Cb и Cr компонентов, когда для группы из четырех соседних пикселов (2x2) вычисляются Y - компоненты, а Cb и Cr используются общие (схема 4:1:1) Более того, пре- и постфильтрация в плоскостях Cb и Cr позволяет использовать прореживание по схеме 16:1:1 без сколько-нибудь значительной потери качества Схема 4:1:1 позволяет сократить выходной поток вдвое (вместо 12 байтов для четырех соседних пикселов достаточно шести) Схема 16:1:1 обеспечивает сокращение потока в 2,67 раза

Некоторые кодеки отображают полноразмерное видео YUV на шкалу RGB с 255 значениями вместо 235. Разработчики кодеков делают это, чтобы обеспечить попадание графики, созданной компьютером, в допустимый для NTSC диапазон. Однако побочный результат такого преобразования состоит в том, что все сигналы, превышающие 100 IRE, срезаются при повторном сжатии; это часто приводит к зрительному затемнению таких сегментов (спецэффектов, титров и стыков) Гораздо более правильное решение для кодека отображать значения непосредственно (без масштабирования), как указано в стандарте ITU-R.BT601. При этом значение 235/235/235 RGB отображается на 100 IRE и наоборот, что оставляет нетронутым рабочий диапазон сигнала и не затемняет яркие сцены. Конечно, при этом режиссеры и авторы должны научиться использовать допустимые цвета, но это неизбежно, если они хотят работать с видео Все аппаратные кодеки Pinnacle Systems, DPS в настоящее время при преобразовании YUV - RGB выполняют масштабирование до 255

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

Этап 1. ДКП Если двумерное ДКП применяется к блокам NхN пикселей, то матрица коэффициентов квантования описывается следующим выражением: где

Этап 1. ДКП Следует создать ДКП матрицу (матрицу коэффициентов квантования), используя следующие выражения: если i=0 DCT[i,j] = 1/sqr(N), если i > 0 DCT[i,j] = sqr(2/N)*cos[(2j+1)*i*3.14/2N], N = 8, 0 < i < 7, 0 < j < 7

Этап 1. ДКП При N = 8, 0 < i < 7, 0 < j < 7 имеем: | | | | | | DCT = | | | | | | | | | |

Этап 1. ДКП Нужно сжать следующий фрагмент изображения: | | | | | | IMG = | | | | | | | | | |

Градации яркости распределены от 0 до 255. Среднее значение 128. Для того, чтобы среднее значение было 0, вычтем 128 | | | | | | IMG = | | | | | | | | | |

Посчитаем промежуточную матрицу: TMP = IMG умножаем на транспонируемую DCT Оставляем только целые числа | | | | | | TMP = | | | | | | | | | |

Результирующая матрица коэффициентов RES = TMP*DCT | | | | | | RES = | | | | | | | | | |

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

Этап 2. Квантование На этом этапе мы посчитаем матрицу квантования, используя этот псевдокод: for(i=0;i

Этап 2. Квантование для q = 2 имеем матрицу квантования: | | | | | | Q = | | | | | | | | | |

Этап 2. Квантование Каждое число в матрице квантования разделим на число в соответствующей позиции в матрице RES, в результате получим матрицу целых коэффициентов: | | | | | | A = | | | | | | | | | | Здесь довольно много нулей

Можно получить наиболее длинную последовательность нулей, если для нумерации использовать следующий алгоритм: | 1 | 2 | 6 | 7 | 15 | 16 | 28 | 29 | | 3 | 5 | 8 | 14 | 17 | 27 | 30 | 43 | | 4 | 9 | 13 | 18 | 26 | 31 | 42 | 44 | | 10 | 12 | 19 | 25 | 32 | 41 | 45 | 54 | | 11 | 20 | 24 | 33 | 40 | 46 | 53 | 55 | | 21 | 23 | 34 | 39 | 47 | 52 | 56 | 61 | | 22 | 35 | 38 | 48 | 51 | 57 | 60 | 62 | | 36 | 37 | 49 | 50 | 58 | 59 | 63 | 64 |

Получилась последовательность:

Для большего сжатия можно перед первым этапом JPEG провести субдискретизацию, или другими словами уменьшить частоту изображения Идея очень проста: к примеру у нас есть следующая последовательность (Cb или Cr) если будем использовать субдискретизацию 4:1:1, результирующая последовательность будет: а если использовать 4:2: Для восстановления последовательности нужно интерполировать результирующие значения

Этап 3. Вторичное сжатие На этом этапе можно применить следующие алгоритмы a) 7bit RLE b) LZW с кодом переменной длины c) Адаптированное кодирование Хаффмана

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