На чем основан алгоритм jpeg

Алгоритм сжатия JPEG

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

Алгоритм JPEG включает четыре основных этапа:

1) Предварительная подготовка изображения;

2) Дискретное косинусное преобразование;

4) Вторичное сжатие.

На 1-м этапе цветное RGB-изображение разделяется на три цветовых плоскости (красную, зеленую и синюю). Затем каждая плоскость разбивается на квадратные участки размером 8×8 пикселей и далее кодируется отдельно.

Примечание. Для достижения лучшего сжатия изображение может переводиться (хотя и не обязательно) в другую цветовую модель – YUV, где Y – яркость, U и V – цветоразностные компоненты:

(4)

После этого матрицы, соответствующие плоскостям U и V подвергаются прореживанию (субдискретизации) путем выбрасывания каждой второй строки и столбца. Это и позволяет получить дополнительный эффект сжатия при использовании цветовой модели YUV.

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

Пусть матрица блока изображения обозначается IMG =[8х8]. Проведём её нормализацию, вычитая из каждого её элемента 128. Дискретное косинусное преобразование осуществляется по формуле

(5)

где

(6)

На этапе квантования сначала вычисляется матрица квантования по следующей формуле

, (7)

где q – коэффициент качества, регулирующий степень сжатия.

Затем каждое число в матрице RES нужно разделить на соответствующий элемент в матрице Q. В результате получится некоторая матрица A, у всех элементов которой необходимо отбросить дробные части. В итоге матрица A будет содержать много нулевых элементов, преимущественно в правой нижней части.

На этапе вторичного сжатия элементы матрицы А пакуются максимально компактным образом. Для достижения максимального эффекта сжатия применяется предварительное Z-упорядочивание элементов матрицы A(8×8) в линейный вектор A(64×1), выполняемое по следующей схеме:

| 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 |

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

Код для DC коэффициента состоит из полей РАЗМЕР (число бит, необходимых для представления значения) и ЗНАЧЕНИЕ (биты самого значения).

Код для AC коэффициента состоит из полей ПРОПУСК (количество предшествующих нулевых AC коэффициентов), РАЗМЕР (число бит, необходимых для представления значения) и ЗНАЧЕНИЕ (биты самого значения).

Поле ЗНАЧЕНИЕ для обоих типов коэффициентов кодируется идентичным способом в соответствии с табл.1.

Для DC коэффициента поле РАЗМЕР кодируется в соответствии с табл. 2.

Для АC коэффициента поля ПРОПУСК и РАЗМЕР рассматриваются как один составной символ вида (ПРОПУСК, РАЗМЕР), который кодируется в соответствии с табл. 3. Причем символ (0,0) называется признаком конца блока и означает, что с текущего места и до конца вектор содержит только нулевые AC коэффициенты.

Таблица 1. Кодирование поля ЗНАЧЕНИЕ в DC и AC коэффициентах

Таблица 2. Коды Хаффмана для поля РАЗМЕР в DC коэффициентах

Таблица 3. Коды Хаффмана для составного символа в AC коэффициентах

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

Блок 8×8 (фрагмент) исходного изображения (размер 64*8=512 бит)

Матрица DCT коэффициентов

Матрица квантованных DCT коэффициентов

Кодовая последовательность в десятичном виде

Кодовая последовательность в двоичном виде с учетом кодов Хаффмана

(011)(11) (11011)(01) (00)(0) (00)(0) (00)(0) (11100)(0) (1010)

Результирующая битовая последовательность (31 бит)

Коэффициент сжатия

Контрольные вопросы

4. В каких случаях коэффициент сжатия оказывается меньше единицы?

7. Чем объясняется высокая степень сжатия, которую обеспечивает алгоритм JPEG?

Источник

Как устроено сжатие с потерями

Благодаря этому у нас есть стримы и ютуб.

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

Часто сжатия без потерь недостаточно. Сегодня поговорим о сжатии с потерями.

Чем отличается от сжатия без потерь

При таком сжатии мы теряем часть информации. Но смысл алгоритмов сжатия в том, чтобы мы этого не замечали: сжатие должно происходить так, чтобы всё важное передалось, а неважное — нет.

Можно представить, что мы говорим с человеком по телефону. Его голос немного искажён, может прерываться или немного сбоить. Но если мы смогли понять собеседника, то нам достаточно такого качества. При этом мы можем не расслышать какие-то нюансы, не ощутить всю глубину баса или не оценить все оттенки интонаций, но это нам и неважно. Разговор по телефону — это пример передачи информации с использованием сжатия с потерями.

Сжатие фотографий

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

Из Википедии: Цветное изображение и его компоненты Y, CB и CR

Эти слои нарезаются на квадраты 8 × 8 пикселей и кодируются с помощью особой математики. Её смысл в том, чтобы понять: есть ли в этом квадрате 8 × 8 что-то важное. Если оно есть, то оно кодируется и данные сохраняются. Если квадрат более-менее однородный, то он записывается как однородный, данных мало.

Экономия данных происходит как раз за счёт этой математики: например, если в квадрат 8 × 8 попал кусочек ясного неба, то там достаточно сказать «весь кусок такого-то синего цвета», и тогда нужно хранить немножко данных. А если на квадрат пришёлся какой-то угол или деталь, то данных нужно сохранить больше.

А если у вас картинка нарезана отдельно на яркость и отдельно на цвет, вы экономите ещё больше данных: в слое с яркостью у вас будут все контрастные детали, а в цветовых слоях — плавные цветовые переливы. Плавные переливы легче закодировать, это будет незаметно для глаза.

Сжатие JPEG идеально подходит для фотографий, где размер деталей намного больше, чем размер пикселей.

Возьмём странное изображение винограда на ржавой трубе. Найдите различия между двумя картинками:

Слева — оригинал, справа изображение сжато в 20 раз. Визуально разницу заметить трудно.

Теперь сожмём оригинал в 415 раз: было 10 мегабайт, стало 24 килобайта. При этом мы всё равно понимаем, что на фотографии — виноград с плодами на ржавой трубе. Наш мозг сглаживает эти неровности и узнаёт картинку.

Справа уже видны пиксели и размытость — это побочные явления сильного сжатия.

Хуже всего JPEG подходит для сжатия изображений, в которых есть мелкие детали, острые края и резкие контрасты. Особенно — если изображения мелкие. Тогда алгоритмы JPEG создают слишком много артефактов. Дизайнеры говорят, что картинку зашакалило (от слова «шакал»):

Убейте меня

Сжатие звука

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

Например, человеческое ухо в среднем воспринимает звуки частотой от 20 герц до 20 килогерц. 20 Гц — это супергрудной бас, а 20 КГц — это супертонкий писк. Чтобы закодировать волну с максимальной частотой 20 КГц, на каждую секунду вам нужно 40 тысяч чисел размером 2 байта. Получается, что секунда несжатого звука будет занимать 80 килобайт.

Но содержательная часть человеческого голоса (та, в которой зашита вся информация) заканчивается на 4000 герцах. Если отрезать у голоса всё, что выше 4000 герц, вы запросто различите смысл слов и поймёте интонацию. Пропадёт лишь некоторая «воздушность» звука. Если нет цели сделать суперкрутой звук, то алгоритмам нет смысла кодировать диапазон 4—20 КГц.

Тогда из звука отсекается лишняя информация и кодируется только диапазон до 4 КГц. Для этого кодирования достаточно 16 килобайт в секунду. Это уже экономия в 5 раз!

Самая важная часть голоса вообще болтается в районе 1000—2000 герц. Если отрезать у голоса всё от 2 до 20 КГц, то нам хватит 8 КБ в секунду, а это экономия в 10 раз по сравнению с несжатым файлом.

Сравните три варианта аудио: сначала несжатый вариант, потом сжатый в 6 раз, наконец — в 160 раз:

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

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

Сжатие видео

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

Пример кодирования одной и той же сцены с разной чувствительностью — на видео она отображена в килобитах в секунду. Чувствительность влияет на итоговый размер видеофайла:

Стримы и потоковое видео

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

Размеры кадров в таких видео часто измеряются в «строках» — это те самые числа возле буквы p:

Соответственно, чем выше кадр, тем он шире; тем больше размер изображения; тем больше деталей в него влезает.

Самое низкое качество, которое есть в потоковом видео — 144p. Мутная картинка и пиксели, зато можно смотреть даже с медленным интернетом То же самое видео в формате HD или 1080p — можно прочитать даже мелкие надписи в интерфейсе игры, запущенной на умных часах. Но для этого нужен быстрый интернет/img]

Буква p в 1080p означает progressive — то есть кодируется каждая строка видеофайла. А бывает ещё буква i, которая означает interlaced. Это значит, что в одном кадре кодируются каждые чётные строки, а в следующем — каждые нечётные. Потом их объединяют в одной картинке, и если не знать, куда смотреть, то можно не заметить подвоха.

Межстрочное сжатие будет хорошо видно, если в кадре что-то движется. Вы заметите характерные «полоски» и задвоение изображения:

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

И что нам с этим делать

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

Источник

Сжатие изображений

Цифровое изображение при хранении занимает большие объемы памяти. Так растровое изображение размером 1024 на 1024 пикселов с глубиной цвета 24 бит занимает 3 Мб. Понятно, что хранение и передача изображений в таком виде является весьма трудоёмкой задачей. Поэтому задача представления изображений в компактной форме (сжатие данных) является весьма актуальной. При этом должны быть разработаны алгоритмы как для кодирования, так и для декодирования (восстановления) изображений.

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

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

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

Груповое сжатие

Одним из простейших методов сжатия изображений является алгоритм RLE (Run Length Encoding – кодирование с переменной длиной строки). Основной идеей этого метода является поиск одинаковых пикселов в одной строке. Найденные цепочки одинаковых элементов заменяются на пары (счетчик повторений, значение), что в определенных случаях существенно уменьшает избыточность данных.

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

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

Входной поток данных:
17 8 54 0 0 0 97 5 16 0 45 23 0 0 0 0 0 3 67 0 0 8

Поток данных после кодирования:
17 8 54 0 3 97 5 16 0 1 45 23 0 5 3 67 0 2 8

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

Входные данные: 1,2,3,4,2,2,2,2,4

Данные после кодирования: 1,2,3,4,2,&3,4.

Принцип: Последовательности повторяющихся значений цвета заменяются его значением и количеством повторений.

Форматы: BMP, TIFF, GIF

Коэффициент сжатия: 2

Метод Хафмана

Этот метод назван в честь его разработчика (1950). Алгоритм основан на том предположении, что некоторые значения сигнала встречаются чаще других. Если проанализировать гистограммы изображений, то можно в этом убедиться. Этот факт можно использовать для сжатия изображений. Использовать для хранения значений интенсивности, которые встречаются чаще, меньшее число бит чем на само значение. Главная проблема в том, чтобы отделять одно значение от другого. Ведь на разные значения отводится разное количество бит. Метод сжатия Хафмана можно проиллюстрировать следующим образом:

Входной поток данных: C E G A D F B E A

Поток данных после кодирования: 0010 0001 000011 1 0011 000010 01 0001 1)

Группировка по байтам: (0010 0001) (000011 1 0) (011 00001) (0 01 00 1 0 1)

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

Этот метод иногда используется в усложненной форме, когда кодируется не одно значение, а последовательности значений. Другая модификация метода – подвергнуть коды Хафмана групповому сжатию.

Коэффициент сжатия: 3

Метод LZW

Этот метод назван также в честь его разработчиков (Lempel, Ziv, Welch). Это универсальный метод, пригодный для кодирования любых сигналов. Похож на метод Хафмана, только для кодирования элементов используются коды равной длины, а также используются коды для часто встречающихся последовательностей элементов.

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

Входной поток данных: 123 145 201 4 119 89 243 245 59 11 206 145 201 4 243 245

Поток данных после кодирования: 123 256 119 89 257 59 11 206 256 257

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

Коэффициент сжатия: 5

Метод JPEG

Среди методов сжатия с потерями следует выделить семейство JPEG, разработанное организацией Joint Photographers Experts Group. Метод основан на частотных представлениях изображения и следующих предположениях. Если к сигналу применить интегральное преобразование (Фурье например), то в результате в частотном представлении основную информации несут низкие частоты. Высокие частоты описывают шум и несущественные детали. Удаление 50% высокочастотной информации повлечет за собой удаление 5% полезной информации содержащейся в изображении.

Для сжатого представления сигнала могут использоваться различные преобразования. Наиболее адекватный (качественные) результат дает преобразование Karhunen-Loeve, но оно сложно и трудоемко в реализации. Преобразование Фурье просто, но не дает желаемого результата при восстановлении. Наиболее пригодным оказалось дискретное косинусное преобразование (Discrete Cosine Transform, DCT). При использовании DCT не нужно работать с комплексными числами (исходный сигнал и его спектр вещественные).

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

Если представить спектр в виде следующей последовательности:

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

Принцип: Используется методика сжатия с потерями. Хранится не информация о цвете пикселов, а коэффициенты разложения по некоторому базису.

Коэффициент сжатия: в зависимости от качества от 10 до 1000.

Положительными сторонами алгоритма JPEG является то, что пользователь может управлять соотношением размер/качество, задавая степень сжатия. Выходное цветное изображение может глубину цвета 24 бита на точку. С помощью алгоритма JPEG достигаются большие коэффициенты сжатия при визуально высоком качестве изображения. Отрицательными сторонами алгоритма является то, что при повышении степени сжатия изображение распадается на отдельные квадратные области (размером 8×8). Это связано с тем, что происходят большие потери в низких частотах при квантовании, и восстановить исходные данные становится невозможно. Кроме того может проявляться так называемый эффект Гиббса – ореолы по границам резких переходов цветов. Кроме того, так как это алгоритм сжатия с потерями, изображения обработанные с его применением практически неприменимы для анализа и дальнейшей обработки.

Источник