Сжатие и растяжение изображения

Содержание статьи

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

Легко подсчитать, что несжатое полноцветное изображение, размером 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 соответственно. Разобьем полуинтервал [0;1) на N непересекающихся полуинтервалов. Каждый полуинтервал соответствует элементам ai, при этом длина полуинтервала пропорциональна частоте pi.
Кодирующая дробь строится следующим образом: строится система вложенных интервалов так, чтобы каждый последующий полуинтервал занимал в предыдущем место, соответствующее положению элемента в исходном разбиении. После того, как все интервалы вложены друг в друга можно взять любое число из получившегося полуинтервала. Запись этого числа в двоичном коде и будет представлять собой сжатый код.
Декодирование – расшифровка дроби по известному распределению вероятностей. Очевидно, что для декодирования необходимо хранить таблицу частот.
Арифметическое кодирование чрезвычайно эффективно. Коды, получаемые с его помощью, приближаются к теоретическому пределу. Это позволяет утверждать, что по мере истечения сроков патентов, арифметическое кодирование будет становиться всё более и более популярным.

Алгоритмы сжатия с потерями

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

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

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

Перевод в цветовое пространство YCbCr

В цветовой модели YCbCr мы представляем изображение в виде яркостной компоненты (Y) и двух цветоразностных компонент (Cb,Cr). Человеческий глаз более восприимчив к яркости, а не к цвету, поэтому алгоритм JPEG вносит по возможности минимальные изменения в яркостную компоненту (Y), а в цветоразностные компоненты могут вноситься значительные изменения. Перевод осуществляется по следующей формуле:

Выбор Kr и Kb зависит от оборудования. Обычно берётся Kb=0.114;Kr=0.299. В последнее время также используется Kb=0.0722;Kr=0.2126, что лучше отражает характеристики современных устройств отображения.

Субдискретизация компонент цветности

После перевода в цветовое пространство YCbCr выполняется дискретизация. Возможен один из трёх способов дискретизации:
4

:4:4 – отсутствует субдискретизация;
4:2:2 – компоненты цветности меняются через одну по горизонтали;
4:2:0 – компоненты цветности меняются через одну строку по горизонтали, при этом по вертикали они меняются через строку.

При использовании второго или третьего способа мы избавляется от 1/3 или 1/2 информации соответственно. Очевидно, что чем больше информации мы теряем, тем сильнее будут искажения в итоговом изображении.

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

Изображение разбивается на компоненты 8*8 пикселов, к каждой компоненте применятся ДКП. Это приводит к уплотнению энергии в коде. Преобразования применяются к компонентам независимо.

Квантование

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

Зигзаг-обход матриц

Зигзаг-обход матрицы – это специальное направление обхода, представленное на рисунке:

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

RLE- кодировние

Используется особый вид RLE-кодирования: выводятся пары чисел, причём первое число в паре кодирует количество нулей, а второе – значение после последовательности нулей. Т.е. код для последовательности 0 0 15 42 0 0 0 44 будет следующим (2;15)(0;42)(3;44).

Кодирование методом Хаффмана

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

Фрактальное сжатие

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

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

Этапы восстановления изображения:

Создание двух изображений одинакового размера A и B. Размер и содержание областей не имеют значения.
Изображение B делится на домены так же, как и на первой стадии процесса сжатия. Для каждого домена области B проводится соответствующее аффинное преобразование ранговых областей изображения A, описанное коэффициентами из сжатого файла. Результат помещается в область B. После преобразования получается совершенно новое изображение.
Преобразование данных из области B в область A. Этот шаг повторяет шаг 3, только изображения A и B поменялись местами.
Шаги 3 и 4 повторяются до тех пор, пока изображения A и B не станут неразличимыми.

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

Источник

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

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

Метод кодирования длин серий

Наиболее простым для понимания алгоритмом является разработанный в 1950-х годах алгоритм кодирования длин серий. Основная идея алгоритма заключается в представлении каждой строки бинарного изображения в виде последовательности длин непрерывных групп чёрных и белых пикселей. Например, вторая строка изображения, приведённого на Рис. 1, будет выглядеть следующим образом: 2,3,2. Но в процессе декодирования возникнет неоднозначность, т.к. непонятно, какую серию: чёрную или белую кодирует первое число. Для решения этой проблемы существует два очевидных метода: либо для каждой строки предварительно указывать значение первого пиксела, либо договориться, что для каждой строки сначала указывается длина последовательности белых пикселов (при этом она может быть равна нулю).

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

Метод кодирования контуров

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

Прежде всего надо отметить, что описание каждого объекта должно быть заключено в специальные сообщения (теги) начала и конца объекта. Первый и самый простой способ – указывать координаты начальной и конечной точки контура на каждой строке. Изображение на Рис. 2 будет закодировано следующим образом:

<НАЧАЛО>
  СТР. 2 4-8
  СТР. 3 3-8
  СТР. 4 3-8
<КОНЕЦ>
<НАЧАЛО>
  СТР. 6 2-8
  СТР. 7 2-9
  СТР. 8 2-9
  СТР. 9 2-9
<КОНЕЦ>

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

<НАЧАЛО>
  СТР. 2 4,8
  СТР. 3 -1,0
  СТР. 4 0,0
<КОНЕЦ>
<НАЧАЛО>
  СТР. 6 2,8
  СТР. 7 0,1
  СТР. 8 0,0
  СТР. 9 0,0
<КОНЕЦ>

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

Кодирование областей постоянства

Заканчивая разговор о сжатии двоичных изображений, необходимо упомянуть о ещё одном методе – кодировании областей постоянства. В этом методе изображение разбивается на прямоугольник n1*n2 пикселов. Все полученные прямоугольники делятся на три группы: полностью белые, полностью чёрные и смешанные. Самая распространённая категория кодируется однобитовым кодовым словом, а остальные две категории получают коды из двух бит. При этом код смешанной области служит меткой, после которой идёт n1*n2 бит, описывающих прямоугольник. Если разбить хорошо известное изображение с Рис. 2 на квадраты 2*2 пиксела, то получится пять белых квадратов, шесть чёрных и 13 смешанных. Договоримся 0 обозначать метку смешанного квадрата, 11 – метку белого квадрата, а 10 – метку чёрного квадрата, единичный белый пиксел будем кодировать 1, а чёрный, соответственно, 0. Тогда всё изображение будет закодировано следующим образом (жирным выделены метки):

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

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

Кодирование битовых плоскостей

Первым способом, который мы рассмотрим, будет способ, известный как кодирование битовых плоскостей. Рассмотрим произвольное изображение с n уровнями яркости. Очевидно, что эти уровни могут быть представлены с помощью log2n бит. Метод разложения на битовые плоскости заключается в разделении одного изображения с n уровнями яркости на log2n бинарных изображений. При этом i-ое изображение получается путём выделения i-ых битов из каждого пиксела исходного изображения. В Табл. 1 показано разложение исходного изображения по битовым плоскостям.

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

Довольно очевидным недостатком данного подхода является эффект многократного переноса разрядов при незначительном изменении яркости. Например, при изменении яркости со 127 на 128 произойдёт изменение значений всех двоичных разрядов (0111111→10000000), что вызовет изменение всех битовых плоскостей.

Чтобы снизить негативные последствия от многократных переносов, на практике часто используются специальные коды, например коды Грея, в которых два соседних элемента различаются только в одном разряде. Для перевода n-битного числа в код Грея необходимо выполнить операцию побитового исключающего ИЛИ с этим же числом, сдвинутым на один бит вправо. Обратное преобразование из кода Грея можно осуществить, выполняя побитовую операцию исключающего ИЛИ для всех сдвигов исходного числа, не равных нулю. Алгоритмы преобразования в код Грея и из него приведены в Листинг 1.

function BinToGray(BinValue: byte): byte;
begin
  BinToGray := BinValue xor (BinValue shr 1);
end;

function GrayToBin(GrayValue: byte): byte;
var
  BinValue: integer;
begin
  BinValue := 0;
  while GrayValue > 0 do
  begin
    BinValue := BinValue xor GrayValue;
    GrayValue := GrayValue shr 1;
  end;
  GrayToBin := BinValue;
end;

Легко убедиться, что после преобразования в код Грея при смене яркости со 127 на 128 меняется только один двоичный разряд:

Битовые плоскости, полученные с помощью кода Грея, более монотонны и в общем случае лучше поддаются сжатию. В Табл. 2 показаны битовые плоскости, полученные из исходного изображения, и изображения, преобразованного в код Грея:

Кодирование с предсказанием

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

При этом способе кодирования очень важно, чтобы и при кодировании, и при декодировании использовался один и тот же предсказатель. В общем случае предсказатель может использовать любые характеристики изображения, но на практике предсказанное значение чаще всего вычисляется как линейная комбинация яркостей соседей: pk=∑i=1Mαi*pk-i. В этой формуле M – число соседей, участвующих в предсказании (порядок предсказания), индексы p — номера пикселей в порядке их просмотра. Можно заметить, что при M=1 кодирование с предсказанием превращается в рассмотренное ранее дельта кодирование (правда, вместо разницы координат теперь кодируется разность яркостей).

Тут необходимо немного обсудить порядок просмотра пикселей. До этого момента мы предполагали, что пикселы просматриваются слева направо и сверху вниз, т.е. в порядке обхода строками(Табл. 3):

Но очевидно, что результат предсказания яркости пятого пиксела на основе четвёртого (при обходе строками) будет очень далёк от истинного результата. Поэтому на практике часто используют другие порядки обхода, например, обход строками с разворотом, змейкой, полосами, полосами с разворотом, и т.д. Некоторые из перечисленных вариантов обхода приведены в Табл. 4

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

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

type
  TPredictionEncodedImg = array of array of integer;
function DeltaEncoding: TPredictionEncodedImg;
var
  r: TPredictionEncodedImg;
  i, j: word;
begin
  SetLength(r, GSI.N + 1);
  for i := 1 to GSI.N do
  begin
    SetLength(r[i], GSI.M + 1);
    r[i, 1] := GSI.i[i, 1];
  end;
  for i := 1 to GSI.N do
    for j := 2 to GSI.M do
      r[i, j] := GSI.i[i, j] — GSI.i[i, j — 1];
  DeltaEncoding := r;
end;

В Табл. 5 представлен результат работы данного алгоритма. Белым цветом показаны пикселы, предсказанные точно, а ошибки отмечены цветом, причём положительное значение ошибки отображается красным цветом, а отрицательное – зелёным. Интенсивность цвета соответствует модулю величины ошибки.

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

Источник