Декодирование JPEG для чайников. JPEG, JPEG2000, JPEG-LS. Сжатие изображений с потерями и без
JPEG - один из новых и достаточно мощных алгоритмов. Практически он является стандартом де-факто для полноцветных изображений . Оперирует алгоритм областями 8x8, на которых яркость и цвет меняются сравнительно плавно. Вследствие этого при разложении матрицы такой, области в двойной ряд по косинусам (см. формулы ниже) значимыми охазываютоя только первые коэффициенты..Таким образом, сжатие в JPEG осуществяяе ется за счет плавности изменения цветов в изображении.
Алгоритм разработан группой экспертов в области фотографии специально для сжатия 24-битовых изображений. JPEG - Joint Photographic Expert Group- подразделение в рамках ISO - Международной организации по стандартизации. Название алгоритма читается как ["jei"peg]. В целом алгоритм основан на дискретном косинусоидальном преобразовании (в дальнейшем - ДКП), применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов. Для получения исходного изображения применяется обратное преобразование.
ДКП раскладывает изображение по амплитудам некоторых частот. Таким образом, при преобразовании мы получаем матрицу, в которой многие коэффициенты либо близки, либо равны нулю. Кроме того, благодаря несовершенству человеческого зрения можно аппроксимировать коэффициенты более грубо без заметной потери качества изображения.
Для этого используется квантование коэффициентов (quantization). В самом простом случае- это арифметический побитовый сдвиг вправо. При этом преобразовании теряется часть информации, но может достигаться большая степень сжатия.
Как работает алгоритм
Итак, рассмотрим алгоритм подробнее (рис. 2.1). Пусть мы сжимаем 24-битовое изображение.
Шаг 1. Переводим изображение из цветового пространства RGB, с компонентами, отвечающими за красную (Red), зеленую (Green) и синюю (Blue) составляющие цвета точки, в цветовое пространство YCrCb (иногда называют YUV).
В нем Y - яркостная составляющая, а Сг, Со - компоненты, отвечающие за цвет (хроматический красный и хроматический синий). За счет того, что человеческий глаз менее чувствителен к цвету, чем к яркости, появляется возможность архивировать массивы для Сг и Со компонент с большими по терями и, соответственно, большими степенями сжатия, Подобное преобра зование уже давно используется в телевидении. На сигналы, отвечающие за цвет, там выделяется более узкая полоса частот. Упрощенно перевод из цветового пространства RGB в цветовое пространство YCrCb можно представить с помощью матрицы перехода:
Шаг 2. Разбиваем исходное изображение на матрицы 8x8. Формируем из каждой 3 рабочие матрицы ДКП - по 8 бит отдельно для каждой компоненты. При больших степенях сжатия этот шаг может выполняться чуть сложнее. Изображение делится по компоненте Y, как и в первом случае, а для компонент Сг и СЬ матрицы набираются через строчку и через столбец. То есть из исходной матрицы размером 16x16 получается только одна рабочая матрица ДКП. При этом, как нетрудно заметить, мы теряем 3/4 полезной информации о цветовых составляющих изображения и получаем сразу сжатие в 2 раза. Мы можем поступать так благодаря работе в пространстве YCrCb. На результирующем RGB-изображении, как показала практика, это сказывается несильно.
Шаг 3. В упрощенном виде ДКП при п=8 можно представить так:
nu,v] = ^Hc(i,u)xC(j,v)y r Y)
Yq
= IntegerRound На этом шаге осуществляется управление степенью сжатия и происходят самые большие потери. Понятно, что, задавая МК с большими коэффициентами, мы получим больше нулей и, следовательно, большую степень сжатия. С квантованием связаны и специфические эффекты алгоритма. При больших значениях коэффициента gamma потери в низких частотах могут быть настолько велики, что изображение распадется на квадраты 8x8. Потери в высоких частотах могут проявиться в так называемом эффекте Гиббса,
когда вокруг контуров с резким переходом цвета образуется своеобразный "нимб". Шаг
5. Переводим матрицу 8x8 в 64-элементный вектор при помощи "зиг-заг"-сканирования, т. е. берем элементы с индексами (0,0), (0,1), (1,0), (2,0)... Таким образом, в начале вектора мы получаем коэффициенты матрицы, соответствующие низким частотам, а в конце - высоким. Шаг 6.
Свертываем вектор с помощью алгоритма группового кодирования. При этом получаем пары типа <пропустить, число>, где "пропустить" является счетчиком пропускаемых нулей, а "число" - значение, которое необходимо поставить в следующую ячейку. Так, вектор 42 3000-2 00001 ... будет свернут в пары (0,42) (0,3) (3,-2) (4,1).... Шаг
7. Свертываем получившиеся пары кодированием по Хаффману с фиксированной таблицей. Процесс восстановления изображения в этом алгоритме полностью симметричен. Метод позволяет сжимать некоторые изображения в 10-15 раз без серьезных потерь. Существенными положительными сторонами алгоритма является то, что: ■ задается степень сжатия; ■ выходное цветное изображение может иметь 24 бита на точку. Отрицательными сторонами алгоритма является то, что: ■ При повышении степени сжатия изображение распадается на отдельные квадраты (8x8). Это связано с тем, что происходят большие потери в низких частотах при квантовании и восстановить исходные данные становится невозможно. ■ Проявляется эффект Гиббса- ореолы по границам резких переходов цветов. Как уже говорилось, стандартизован JPEG относительно недавно -в 1991 г. Но уже тогда существовали алгоритмы, сжимающие сильнее при меньших потерях качества. Дело в том, что действия разработчиков стандарта были ограничены мощностью существовавшей на тот момент техники. То есть даже на ПК алгоритм должен был работать меньше минуты на среднем изображении, а его аппаратная реализация должна быть относительно простой и дешевой. Алгоритм должен был быть симметричным (время разархивации примерно равно времени архивации). Выполнение последнего требования сделало возможным появление таких устройств, как цифровые фотоаппараты, снимающие 24-битовые фотографии на 8-256 Мб флеш-карту." Йвтом эта карта вставляется в разъём на вашем ноутбуке и соответствующая программа позволяет считать изображения. Не правда Ня,
если бы алгоритм был несимметричен, было бы неприятно долго ждать, пока аппарат "перезарядится" - сожмет изображение. Не очень приятным свойством JPEG является также то,
что нередко горизонтальные и вертикальные полосы на дисплее абсолютно не видны и могут проявиться только при печати в виде муарового узора. Он возникает при наложении наклонного растра печати на горизонтальные и вертикальные полосы изображения. Из-за этих сюрпризов JPEG не рекомендуется активно
использовать в полиграфии, задавая высокие коэффициенты матрицы квантования. Однако при архивации изображений, предназначенных для просмотра человеком, он на данный момент незаменим. Широкое
применение JPEG долгое время сдерживалось, пожалуй, лишь тем, что он оперирует 24-битовыми изображениями. Поэтому для того, чтобы с приемлемым качеством посмотреть картинку на обычном мониторе в 256-цветной палитре, требовалось применение соответствующих алгоритмов и, следовательно, определенное время. В приложениях, ориентированных на придирчивого пользователя, таких, например, как игры, подобные задержки неприемлемы. Кроме того, если имеющиеся у вас изображения, допустим, в 8-битовом формате GIF перевести в 24-битовый JPEG, а потом обратно в GIF для просмотра, то потеря качества произойдет дважды при обоих преобразованиях. Тем не менее выигрыш в размерах архивов зачастую настолько велик (в 3-20 раз), а потери качества настолько малы, что хранение изображений в JPEG оказывается очень эффективным. Несколько слов необходимо сказать о модификациях этого алгоритма. Хотя JPEG и является стандартом ISO, формат его файлов не был зафиксирован. Пользуясь этим, производители создают свои, несовместимые между собой форматы и, следовательно, могут изменить алгоритм. Так, внутренние таблицы алгоритма, рекомендованные ISO, заменяются ими на свои собственные. Кроме того, легкая неразбериха присутствует при задании степени потерь. Например, при тестировании выясняется, что "отличное" качество, "100%" и "10 баллов" дают существенно различающиеся картинки. При этом, кстати, "100%" качества не означает сжатия без потерь. Встречаются также варианты JPEG для специфических приложений. Как стандарт ISO JPEG начинает все шире использоваться при обмене изображениями в компьютерных сетях. Поддерживается алгоритм JPEG в форматах Quick Time, PostScript Level 2, Tiff 6.0 и на данный момент занимает видное место в системах мультимедиа. Характеристики алгоритма JPEG: o ! ш. ,. Степень сжатия:
2-200 (задается здльзователем). ,ц, :_,. . Класс изображений:
полноцветные 2jj.битовые изображения или изо-| бражения в градациях серого без резких переходов цве^о&,(фотографии). Симметричность:
1. Характерные особенности:
в некоторых случаях алгоритм создает! "ореол" вокруг резких горизонтальных и вертикальных границ в изображении (эффект Гиббса). Кроме того, при высокой степени сжатия изо-! бражение распадается на блоки 8x8 пикселов. Для эффективного сжатия данных необходимо прежде всего оценить характер вашего изображения. JPEG сжимает графические данные, опираясь на то, что видит человеческий глаз. Поэтому, чтобы помочь понять, как и что делает JPEG, я хотел бы дать вам общее представление о зрительном восприятии человека. Сжатие JPEG происходит в несколько этапов. Цель - преобразовать графические данные таким образом, чтобы незначимая визуальная информация легко идентифицировалась и отбрасывалась. Такое сжатие "с потерями" отличается от большинства других подходов, используемых при работе с графическими форматами, которые стараются сохранить в неприкосновенности каждый бит изображения. Цветовая модель
Первый шаг JPEG - выбор подходящего способа представления цветов. Цвета обычно задаются в трехмерной системе координат. Хорошо известная большинству программистов система описывает цвет, как комбинацию красного, зеленого и синего (RGB). К несчастью, с точки зрения возможности сжатия, это не лучший способ описания цвета. Проблема заключается в том, что все три компонента: красный, зеленый и синий - равнозначны. Однако переход к другой системе цветопередачи позволяет выделить некоторую более важную информацию. Профессионалы используют две цветовые модели: HSL (Hue-Saturation-Lightness) и HSV (Hue-Saturation-Value). Интуитивно понятно, что яркостная компонента (Lightness) модели HSL и яркостная компонента (Value) модели HSV каждая по-своему определяют соотношение света и тени. Насыщенность (saturation) определяет уровень "чистого" цвета. Ненасыщенные цвета часто неформально называют "грязными" (greyish). Оттенок (Hue) - это то, что мы воспринимаем, как цвет предмета, например красный или серовато-зеленый. Здесь важно отметить удивительный факт: человеческое зрение более чувствительно к изменению освещенности, а не цвета как такового! Различные реализации алгоритма сжатия JPEG используют различные цветовые системы. Используемая форматом JFIF система цветопередачи YCbCr во многом схожа со схемой, разработанной много лет назад для цветного телевидения. Прореживание
Основная причина преобразования одной цветовой модели в другую заключается в необходимости выявления менее существенной для просмотра информации изображения. JPEG уменьшает количество информации о цвете. В то время как яркостная компонента передается с полным разрешением, цветоразностностные компоненты используют в два раза меньший диапазон значений. В результате этого простого шага объем данных уменьшается на треть. С помощью прореживания (subsampling) регулируются цвета изображения цветного телевизора. Обычно в телевидение черно-белое изображение и информация о цвете передаются по отдельности. Причем информация о цвете передается в менее строгом виде, чем информация о яркости изображения. Дискретное косинусное преобразование (DCT)
Каждая компонента цвета обрабатывается отдельно, как если бы они были не одним цветным, а тремя полутоновыми изображениями. Если вы посмотрите на детальное изображение с большого расстояния, то вы различите лишь общий тон картины. Например, "главным образом синий" или "преимущественно красный". Чем ближе вы будете подходить к изображению, тем больше деталей сможете различить. Для эмуляции этого эффекта JPEG использует один математический прием, называемый дискретным косинусным преобразованием (DCT). DCT преобразует информацию о пикселах в информацию об изменении пикселов. Первое, что может дать DCT - усредненный цвет области. Затем он все больше и больше уточняет детали. Как в случае удаленного изображения, усредненное значение цвета представляет собой очень важную информацию об области изображения. Ваш глаз менее чувствителен к скорости изменения цвета, поэтому она не так важна. Преобразовав информацию о цвете подобным образом, мы выделяем ту информацию, которой можно пожертвовать. Считается, что потери обусловливаются именно этим этапом. Если вы с помощью DCT закодируете изображение и затем с помощью функции обратного DCT восстановите его, то вы не получите абсолютно такой же набор бит. Однако эта ошибка - ошибка округления. Она возникает при выполнении арифметических действий и обычно не очень велика. Поэтому я предпочитаю думать об этапе DCT, как о действии, происходящем "в основном без потерь". Для больших изображений обсчет DCT и обратного DCT весьма времяемкий процесс. Чтобы сократить время расчетов, JPEG разбивает изображение на мозаику размером восемь на восемь пикселов. Каждая из мозаик обрабатывается отдельно, что существенно сокращает необходимое для DCT время расчета. Проблема, возникающая при таком подходе, состоит в том, что после квантования (о котором пойдет речь в следующем разделе) границы этих квадратиков могут не совпадать и потому становятся видимыми при задании низкого значения параметра качества. Квантование
Разработчиков JPEG прежде всего интересовали изображения фотографического качества (photographic, contnuous tone). Как правило, эти полутоновые изображения характеризуются мягкими переходами от одного цвета к другому. Для таких изображений низкочастотная (медленно изменяющаяся) компонента DCT важнее высокочастотной (быстро меняющаяся). Термин квантование (quantization) означает просто "округление". JPEG отбрасывает некоторую графическую информацию за счет округления каждого члена DCT с различными весовыми коэффициентами, опираясь при этом на различные факторы. Высокочастотная компонента округляется сильнее низкочастотной. Например, низкочастотная компонента, которая хранит среднюю величину яркости, может быть округлена до значения, кратного трем, в то время как высокочастотная компонента может быть округлена до значения, кратного ста! Операция квантования объясняет, почему сжатие JPEG в случае четких контуров приводит к образованию "дрожащих" линий. Контуры определяются высокочастотной (быстро меняющейся) пространственной компонентой. (На первый взгляд может показаться, что вы должны получить размытый контур, однако вспомните, что C в сокращении DCT обозначает косинус.) Обычно цветовые плоскости квантуются гораздо грубее плоскостей яркости. Здесь правильный выбор цветовой модели помогает выявлять ту информацию, которую можно отбросить. Сжатие
До сих пор, за исключением того случая, когда рассматривалась частота выборки из двух цветовых каналов, никакого сжатия не происходило. Все рассмотренные выше шаги - преобразование цветовых моделей, DCT и квантование - оставляли размер данных без изменений. Наконец мы добрались до последнего шага, во время которого с помощью стандартной техники сжатия без потерь действительно будет уменьшен размер данных. Данные, разложенные по полочкам в ходе предыдущих шагов, могут быть сжаты более эффективно, чем необработанное сырье, которое представляют собой графические данные RGB. Причем ни один из сделанных шагов не был лишним, каждое изменение данных было направлено на то, чтобы более эффективно сжать окончательный вариант. Изменение цветовой модели позволило проредить информацию каналов и затем более энергично их квантовать. DCT дало возможность выделить высокочастотную пространственную компоненту. Высокочастотная компонента обычно имеет небольшие значения, в результате чего выходные данные на этапе DCT содержат несоразмерно много маленьких значений, облегчающих процесс сжатия. В процессе квантования большая часть высокочастотной составляющей обнуляется, а остальная принимает конкретные значения. Сокращение числа различных значений также облегчает процесс сжатия данных. Стандарт JPEG предоставляет два различных метода сжатия без потерь, которые могут быть использованы на последнем этапе. Сжатие Хаффмана (Huffman compression - это давно известный незапатентованный, легко программируемый алгоритм. В отличие от него более новый алгоритм арифметического кодирования (arithmetic coding) является объектом многочисленных патентов. (Поэтому не удивительно, что многие программы сжатия JPEG поддерживают только сжатие Хаффмана.) При декодировании изображений JPEG необходимо совершить все эти шаги в обратном порядке. Поток данных вначале распаковывается, затем каждый блок 8ґ8 подвергается обратному DCT и наконец изображение конвертируется в соответствующую цветовую модель (обычно это RGB). Отметим, что информация, которая была обдуманно отброшена с помощью прореживания и квантования, никогда не восстанавливается. Однако если все было сделано корректно, потеря информации не вызовет никакого видимого ухудшения изображения. Легко подсчитать, что несжатое полноцветное изображение, размером 2000*1000 пикселов будет иметь размер около 6 мегабайт. Если говорить об изображениях, получаемых с профессиональных камер или сканеров высокого разрешения, то их размер может быть ещё больше. Не смотря на быстрый рост ёмкости устройств хранения, по-прежнему весьма актуальными остаются различные алгоритмы сжатия изображений. Эта таблица есть, как и на стороне того, кто сжимает информацию, так и на стороне того, кто распаковывает. Сейчас мы рассмотрим процесс сжатия. В таблице представлен процесс заполнения словаря. Легко подсчитать, что полученный сжатый код занимает 105 бит, а исходный текст (при условии, что на кодирование одного символа мы тратим 4 бита) занимает 116 бит.
Все существующие алгоритмы можно разделить на два больших класса:
Когда мы говорим о сжатии без потерь, мы имеем в виду, что существует алгоритм, обратный алгоритму сжатия, позволяющий точно восстановить исходное изображение. Для алгоритмов сжатия с потерями обратного алгоритма не существует. Существует алгоритм, восстанавливающий изображение не обязательно точно совпадающее с исходным. Алгоритмы сжатия и восстановления подбираются так, чтобы добиться высокой степени сжатия и при этом сохранить визуальное качество изображения.Алгоритмы сжатия без потерь
Алгоритм RLE
Все алгоритмы серии RLE основаны на очень простой идее: повторяющиеся группы элементов заменяются на пару (количество повторов, повторяющийся элемент). Рассмотрим этот алгоритм на примере последовательности бит. В этой последовательности будут чередовать группы нулей и единиц. Причём в группах зачастую будет более одного элемента. Тогда последовательности 11111 000000 11111111 00 будет соответствовать следующий набор чисел 5 6 8 2. Эти числа обозначают количество повторений (отсчёт начинается с единиц), но эти числа тоже необходимо кодировать. Будем считать, что число повторений лежит в пределах от 0 до 7 (т.е. нам хватит 3 бит для кодирования числа повторов). Тогда рассмотренная выше последовательность кодируется следующей последовательностью чисел 5 6 7 0 1 2. Легко подсчитать, что для кодирования исходной последовательности требуется 21 бит, а в сжатом по методу RLE виде эта последовательность занимает 18 бит.
Хоть этот алгоритм и очень прост, но эффективность его сравнительно низка. Более того, в некоторых случаях применение этого алгоритма приводит не к уменьшению, а к увеличению длины последовательности. Для примера рассмотрим следующую последовательность 111 0000 11111111 00. Соответствующая ей RL-последовательность выглядит так: 3 4 7 0 1 2. Длина исходной последовательности – 17 бит, длина сжатой последовательности – 18 бит.
Этот алгоритм наиболее эффективен для чёрно-белых изображений. Также он часто используется, как один из промежуточных этапов сжатия более сложных алгоритмов.Словарные алгоритмы
Идея, лежащая в основе словарных алгоритмов, заключается в том, что происходит кодирование цепочек элементов исходной последовательности. При этом кодировании используется специальный словарь, который получается на основе исходной последовательности.
Существует целое семейство словарных алгоритмов, но мы рассмотрим наиболее распространённый алгоритм LZW, названный в честь его разработчиков Лепеля, Зива и Уэлча.
Словарь в этом алгоритме представляет собой таблицу, которая заполняется цепочками кодирования по мере работы алгоритма. При декодировании сжатого кода словарь восстанавливается автоматически, поэтому нет необходимости передавать словарь вместе с сжатым кодом.
Словарь инициализируется всеми одноэлементными цепочками, т.е. первые строки словаря представляют собой алфавит, в котором мы производим кодирование. При сжатии происходит поиск наиболее длинной цепочки уже записанной в словарь. Каждый раз, когда встречается цепочка, ещё не записанная в словарь, она добавляется туда, при этом выводится сжатый код, соответствующий уже записанной в словаре цепочки. В теории на размер словаря не накладывается никаких ограничений, но на практике есть смысл этот размер ограничивать, так как со временем начинаются встречаться цепочки, которые больше в тексте не встречаются. Кроме того, при увеличении размеры таблицы вдвое мы должны выделять лишний бит для хранения сжатых кодов. Для того чтобы не допускать таких ситуаций, вводится специальный код, символизирующий инициализацию таблицы всеми одноэлементными цепочками.
Рассмотрим пример сжатия алгоритмом. Будем сжимать строку кукушкакукушонкукупилакапюшон. Предположим, что словарь будет вмещать 32 позиции, а значит, каждый его код будет занимать 5 бит. Изначально словарь заполнен следующим образом:
По сути, процесс декодирования сводится к прямой расшифровке кодов, при этом важно, чтобы таблица была инициализирована также, как и при кодировании. Теперь рассмотрим алгоритм декодирования.
Строку, добавленную в словарь на i-ом шаге мы можем полностью определить только на i+1. Очевидно, что i-ая строка должна заканчиваться на первый символ i+1 строки. Т.о. мы только что разобрались, как можно восстанавливать словарь. Некоторый интерес представляет ситуация, когда кодируется последовательность вида cScSc, где c - это один символ, а S - строка, причём слово cS уже есть в словаре. На первый взгляд может показаться, что декодер не сможет разрешить такую ситуацию, но на самом деле все строки такого типа всегда должны заканчиваться на тот же символ, на который они начинаются.Алгоритмы статистического кодирования
Алгоритмы этой серии ставят наиболее частым элементам последовательностей наиболее короткий сжатый код. Т.е. последовательности одинаковой длины кодируются сжатыми кодами различной длины. Причём, чем чаще встречается последовательность, тем короче, соответствующий ей сжатый код.Алгоритм Хаффмана
Алгоритм Хаффмана позволяет строить префиксные коды. Можно рассматривать префиксные коды как пути на двоичном дереве: прохождение от узла к его левому сыну соответствует 0 в коде, а к правому сыну – 1. Если мы пометим листья дерева кодируемыми символами, то получим представление префиксного кода в виде двоичного дерева.
Опишем алгоритм построения дерева Хаффмана и получения кодов Хаффмана.
С помощью этого алгоритма мы можем получить коды Хаффмана для заданного алфавита с учётом частоты появления символов.Арифметическое кодирование
Алгоритмы арифметического кодирования кодируют цепочки элементов в дробь. При этом учитывается распределение частот элементов. На данный момент алгоритмы арифметического кодирования защищены патентами, поэтому мы рассмотрим только основную идею.
Пусть наш алфавит состоит из N символов a1,…,aN, а частоты их появления p1,…,pN соответственно. Разобьем полуинтервал
где DC diff = DC текущее - DC предыдущее
Смотрим AC:
Так как график очень похож на график для разностей DC, то принцип тот же: [код Хаффмана для длины AC (в битах)]. Но не совсем! Так как на графике шкала логарифмическая, то не сразу заметно, что нулевых значений примерно в 10 раз больше, чем значения 2 - следующего по частоте. Это понятно - не все пережили квантование. Вернемся к матрице значений, полученной на этапе квантования (используя матрицу квантования FastStone, 90%).
Так как встречается много групп подряд идущих нулей, то появляется идея - записывать только количество нулей в группе. Такой алгоритм сжатия называется RLE (Run-length encoding, кодирование повторами). Осталось выяснить направление обхода «подряд идущих» - кто за кем? Выписать слева направо и сверху вниз - не очень эффективно, так как ненулевые коэффициенты концентрируются около левого верхнего угла, а чем ближе к правому нижнему - тем больше нулей.
Поэтому, в JPEG используется порядок, называемый «Zig-zag», он показан на левом рисунке. Такой способ хорошо выделяет группы нулей. На правом рисунке - альтернативный способ обхода, не относящийся к JPEG, зато с любопытным названием (пруф). Он может использоваться в MPEG при сжатии видео с чересстрочной разверткой. Выбор алгоритма обхода не влияет на качество изображения, но может увеличить количество кодируемых групп нулей, что в итоге может отразиться на размере файла.
Модифицируем нашу запись. Для каждого ненулевого AC - коэффициента:
[Количество нулей перед AC][код Хаффмана для длины AC (в битах)]
Думаю, что вы сразу скажете - количество нулей тоже отлично закодируется Хаффманом! Это очень близкий и неплохой ответ. Но можно немного оптимизировать. Представьте, что имеем некоторый коэффициент AC, перед которым было 7 нулей (разумеется, если выписывать в зигзагообразном порядке). Эти нули - дух значений, которые не выдержали квантования. Скорее всего, наш коэффициент тоже сильно потрепало и он стал маленьким, а, значит, его длина - короткой. Значит, количество нулей перед AC и длина AC - зависимые величины. Поэтому записывают так:
[код Хаффмана для (Количество нулей перед AC, длина AC (в битах)]
Алгоритм кодирования остается тем же: те пары (количество нулей перед AC, длина AC), которые встречаются часто, получат короткие коды и наоборот.
Строим гистограмму зависимости количества по этим парам и дерево Хаффмана.
Длинный «горный хребет» подтверждает наше предположение.
Особенности реализации в JPEG:
Такая пара занимает 1 байт: 4 бита на количество нулей и 4 бита на длину AC. 4 бита - это значения от 0 до 15. Для длины AC хватит с избытком, но ведь нулей может быть больше 15? Тогда используется больше пар. Например, для 20 нулей: (15, 0)(5, AC). То есть, 16-й ноль кодируется как ненулевой коэффициент. Так как ближе к концу блока всегда полно нулей, то после последнего ненулевого коэффициента используется пара (0,0). Если она встретится при декодировании, значит оставшиеся значения равны 0.
Выяснили, что каждый блок закодирован хранится в файле так:
[код Хаффмана для длины DC diff ]
[код Хаффмана для (количество нулей перед AC 1 , длина AC 1 ]
…
[код Хаффмана для (количество нулей перед AC n , длина AC n ]
Где AC i - ненулевые AC коэффициенты.
Цветное изображение
Способ представления цветного изображения зависит от выбранной цветовой модели. Простое решение - использовать RGB и кодировать каждый цветовой канал изображения по отдельности. Тогда кодирование не будет отличаться от кодирования серого изображения, только работы в 3 раза больше. Но сжатие изображения можно увеличить, если вспомнить, что глаз более чувствительнее к изменению яркости, чем цвета. Это значит, что цвет можно хранить с бОльшими потерями, чем яркость. У RGB нет отдельного канала яркости. Она зависит от суммы значений каждого канала. Поэтому, RGB-куб (это представление всех возможных значений) просто «ставят» на диагональ - чем выше, тем ярче. Но на этом не ограничиваются - куб немного поджимают с боков, и получается скорее параллелепипед, но это лишь для учета особенностей глаза. Например, он более восприимчив к зеленому, чем синему. Так появилась модель YCbCr.
(Изображение с Intel.com)
Y - компонента яркости, Cb и Cr являются синей и красной цветоразностными компонентами. Поэтому, если хотят сильнее сжать изображение, то RGB переводят в YCbCr, и каналы Cb и Cr прореживают. То есть разбивают на небольшие блоки, например 2x2, 4x2, 1x2, и усредняют все значения одного блока. Или, другими словами, уменьшают размер изображения для этого канала в 2 или 4 раза по вертикали и/или горизонтали.
Каждый блок 8x8 кодируется (DCT + Хаффман), и закодированные последовательности записываются в таком порядке:
Любопытно, что спецификация JPEG не ограничивает в выборе модели, то есть реализация кодировщика может как угодно разделить изображение по цветовым компонентам (каналам) и каждый будет сохранен по отдельности. Мне известно об использовании Grayscale (1 канал), YCbCr (3), RGB (3), YCbCrK (4), CMYK (4). Первые три поддерживаются почти всеми, а вот с последними 4-канальными бывают проблемы. FastStone, GIMP поддерживают их корректно, а штатные программы Windows, paint.net корректно извлекают всю информацию, но потом выбрасывают 4 черный канал, поэтому (Antelle сказал, что не выбрасывают, читайте его комментарии) показывают более светлое изображение. Слева - классический YCbCr JPEG, справа CMYK JPEG:
Если они различаются по цветам, или видна только одна картинка, то, скорее всего, у вас IE (любой версии) (UPD. в комментариях говорят «или Safari»). Можете попробовать открыть статью в разных браузерах.
И еще кое-что
В двух словах о дополнительных возможностях.Progressive mode
Разложим полученные таблицы коэффициентов DCT на сумму таблиц (примерно так (DC, -19, -22, 2, 1) = (DC, 0, 0, 0, 0) + (0, -20, -20, 0, 0) + (0, 1, -2, 2, 1)). Сначала закодируем все первые слагаемые (как мы уже научились: Хаффман и обход зигзагом), затем вторые и т. д. Такой трюк полезен при медленном интернете, так как сперва загружаются только DC коэффициенты, по которым строится грубая картинка c «пикселями» 8x8. Затем округленные AC коэффициенты, позволяющие уточнить рисунок. Затем грубые поправки к ним, затем более точные. Ну и так далее. Коэффициенты округляются, так как на ранних этапах загрузки точность не столь важна, зато округление положительно сказывается на длине кодов, так как для каждого этапа используется своя таблица Хаффмана.Lossless mode
Сжатие без потерь. DCT нет. Используется предсказание 4-й точки по трем соседним. Ошибки предсказания кодируются Хаффманом. По-моему, используется чуть чаще, чем никогда.Hierarhical mode
По изображению создается несколько слоев с разными разрешениями. Первый грубый слой кодируется как обычно, а затем только разница (уточнение изображения) между слоями (прикидывается вейвлетом Хаара). Для кодирования используется DCT или Lossless. По-моему, используется чуть реже, чем никогда.Арифметическое кодирование
Алгоритм Хаффмана создает оптимальные коды по весу символов, но это верно только для фиксированного соответствия символов с кодами. Арифметическое не имеет такой жесткой привязки, что позволяет использовать коды как бы с дробным числом бит. Утверждается, что оно уменьшает размер файла в среднем на 10% по сравнению с Хаффманом. Не распространено из-за проблем с патентом, поддерживается не всеми.Я надеюсь, что теперь вам понятен алгоритм JPEG интуитивно. Спасибо за прочтение!
UPD
vanwin предложил указать использованное ПО. С удовольствием сообщаю, что все доступны и бесплатны:
- Python + NumPy + Matplotlib + PIL(Pillow) . Основной инструмент. Нашелся по выдаче «Matlab free alternative». Рекомендую! Даже если вам не знаком Python, то уже через пару часов научитесь производить расчеты и строить красивые графики.
- JpegSnoop . Показывает подробную информацию о jpeg-файле.
- yEd . Редактор графов.
- Inkscape . Делал в нем иллюстрации, такие как пример алгоритма Хаффмана. Прочитал несколько уроков, оказалось очень здорово.
- Daum Equation Editor . Искал визуальный редактор формул, так как с Latex-ом не очень дружу. Daum Equation - плагин к Хрому, мне показался очень удобен. Помимо мышкотыкания, можно редактировать Latex.
- FastStone . Думаю, его представлять не надо.
- PicPick . Бесплатная альтернатива SnagIt. Сидит в трее, скриншотит что скажут куда скажут. Плюс всякие плюшки, типа линейки, пипетки, угломера и пр.
Теги: Добавить метки
Легко подсчитать, что несжатое полноцветное изображение, размером 2000*1000 пикселов будет иметь размер около 6 мегабайт. Если говорить об изображениях, получаемых с профессиональных камер или сканеров высокого разрешения, то их размер может быть ещё больше. Не смотря на быстрый рост ёмкости устройств хранения, по-прежнему весьма актуальными остаются различные алгоритмы сжатия изображений.
Все существующие алгоритмы можно разделить на два больших класса:
- Алгоритмы сжатия без потерь;
- Алгоритмы сжатия с потерями.
Алгоритмы сжатия без потерь
Алгоритм RLE
Все алгоритмы серии RLE основаны на очень простой идее: повторяющиеся группы элементов заменяются на пару (количество повторов, повторяющийся элемент). Рассмотрим этот алгоритм на примере последовательности бит. В этой последовательности будут чередовать группы нулей и единиц. Причём в группах зачастую будет более одного элемента. Тогда последовательности 11111 000000 11111111 00 будет соответствовать следующий набор чисел 5 6 8 2. Эти числа обозначают количество повторений (отсчёт начинается с единиц), но эти числа тоже необходимо кодировать. Будем считать, что число повторений лежит в пределах от 0 до 7 (т.е. нам хватит 3 бит для кодирования числа повторов). Тогда рассмотренная выше последовательность кодируется следующей последовательностью чисел 5 6 7 0 1 2. Легко подсчитать, что для кодирования исходной последовательности требуется 21 бит, а в сжатом по методу RLE виде эта последовательность занимает 18 бит.Хоть этот алгоритм и очень прост, но эффективность его сравнительно низка. Более того, в некоторых случаях применение этого алгоритма приводит не к уменьшению, а к увеличению длины последовательности. Для примера рассмотрим следующую последовательность 111 0000 11111111 00. Соответствующая ей RL-последовательность выглядит так: 3 4 7 0 1 2. Длина исходной последовательности – 17 бит, длина сжатой последовательности – 18 бит.
Этот алгоритм наиболее эффективен для чёрно-белых изображений. Также он часто используется, как один из промежуточных этапов сжатия более сложных алгоритмов.
Словарные алгоритмы
Идея, лежащая в основе словарных алгоритмов, заключается в том, что происходит кодирование цепочек элементов исходной последовательности. При этом кодировании используется специальный словарь, который получается на основе исходной последовательности.Существует целое семейство словарных алгоритмов, но мы рассмотрим наиболее распространённый алгоритм LZW, названный в честь его разработчиков Лепеля, Зива и Уэлча.
Словарь в этом алгоритме представляет собой таблицу, которая заполняется цепочками кодирования по мере работы алгоритма. При декодировании сжатого кода словарь восстанавливается автоматически, поэтому нет необходимости передавать словарь вместе с сжатым кодом.
Словарь инициализируется всеми одноэлементными цепочками, т.е. первые строки словаря представляют собой алфавит, в котором мы производим кодирование. При сжатии происходит поиск наиболее длинной цепочки уже записанной в словарь. Каждый раз, когда встречается цепочка, ещё не записанная в словарь, она добавляется туда, при этом выводится сжатый код, соответствующий уже записанной в словаре цепочки. В теории на размер словаря не накладывается никаких ограничений, но на практике есть смысл этот размер ограничивать, так как со временем начинаются встречаться цепочки, которые больше в тексте не встречаются. Кроме того, при увеличении размеры таблицы вдвое мы должны выделять лишний бит для хранения сжатых кодов. Для того чтобы не допускать таких ситуаций, вводится специальный код, символизирующий инициализацию таблицы всеми одноэлементными цепочками.
Рассмотрим пример сжатия алгоритмом. Будем сжимать строку кукушкакукушонкукупилакапюшон. Предположим, что словарь будет вмещать 32 позиции, а значит, каждый его код будет занимать 5 бит. Изначально словарь заполнен следующим образом:
Эта таблица есть, как и на стороне того, кто сжимает информацию, так и на стороне того, кто распаковывает. Сейчас мы рассмотрим процесс сжатия.
В таблице представлен процесс заполнения словаря. Легко подсчитать, что полученный сжатый код занимает 105 бит, а исходный текст (при условии, что на кодирование одного символа мы тратим 4 бита) занимает 116 бит.
По сути, процесс декодирования сводится к прямой расшифровке кодов, при этом важно, чтобы таблица была инициализирована также, как и при кодировании. Теперь рассмотрим алгоритм декодирования.
Строку, добавленную в словарь на i-ом шаге мы можем полностью определить только на i+1. Очевидно, что i-ая строка должна заканчиваться на первый символ i+1 строки. Т.о. мы только что разобрались, как можно восстанавливать словарь. Некоторый интерес представляет ситуация, когда кодируется последовательность вида cScSc, где c - это один символ, а S - строка, причём слово cS уже есть в словаре. На первый взгляд может показаться, что декодер не сможет разрешить такую ситуацию, но на самом деле все строки такого типа всегда должны заканчиваться на тот же символ, на который они начинаются.
Алгоритмы статистического кодирования
Алгоритмы этой серии ставят наиболее частым элементам последовательностей наиболее короткий сжатый код. Т.е. последовательности одинаковой длины кодируются сжатыми кодами различной длины. Причём, чем чаще встречается последовательность, тем короче, соответствующий ей сжатый код.Алгоритм Хаффмана
Алгоритм Хаффмана позволяет строить префиксные коды. Можно рассматривать префиксные коды как пути на двоичном дереве: прохождение от узла к его левому сыну соответствует 0 в коде, а к правому сыну – 1. Если мы пометим листья дерева кодируемыми символами, то получим представление префиксного кода в виде двоичного дерева.Опишем алгоритм построения дерева Хаффмана и получения кодов Хаффмана.
- Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который равен частоте появления символа
- Выбираются два свободных узла дерева с наименьшими весами
- Создается их родитель с весом, равным их суммарному весу
- Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка
- Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой - бит 0
- Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.
Арифметическое кодирование
Алгоритмы арифметического кодирования кодируют цепочки элементов в дробь. При этом учитывается распределение частот элементов. На данный момент алгоритмы арифметического кодирования защищены патентами, поэтому мы рассмотрим только основную идею.Пусть наш алфавит состоит из N символов a1,…,aN, а частоты их появления p1,…,pN соответственно. Разобьем полуинтервал }