Алгоритмы cжатия изображений (Image Compression Algorithms)

Автор: | 25.07.2018

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

  • избыточность – группы одинаковых символов;
  • предсказуемость – часто повторяющиеся одинаковые комбинации символов;
  • необязательность – данные, мало влияющие на человеческое восприятие.

Оценки методов сжатия:

  • степень сжатия – отношение объема сжатого файла к объему исходного файла;
  • точность восстановления – среднеквадратичное отклонение значений пикселей сжатого изображения от оригинала;
  • скорость компрессии и декомпрессии – суммарное время сжатия и восстановления;
  • симметричность – отношение времени сжатия ко времени восстановления.

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

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

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

Алгоритмы на основе статистических характеристик ставят наиболее частым элементам последовательностей наиболее короткий сжатый код

Алгоритмы серии RLE (англ. run-length encoding или кодирование повторов) основаны на очень простой идее: повторяющиеся группы элементов заменяются на числа повторов.  Пример: последовательности из 21 бит (11111 000000 11111111 00) соответствует набор чисел 5 6 8 2. Этот набор при 3-х битном кодировании каждого числа (от 0 до 7) может быть  представлен последовательностью из 18 бит  5 6 7 0 1 2 (101 110 111 000 001 010).

Алгоритм Шенона-Фано:

  1. Символы первичного алфавита m1 выписывают по убыванию вероятностей.
  2. Символы полученного алфавита делят на две части, суммарные вероятности символов которых максимально близки друг другу.
  3. В префиксном коде для первой части алфавита присваивается двоичная цифра «0», второй части — «1».
  4. Полученные части рекурсивно делятся и их частям назначаются соответствующие двоичные цифры в префиксном коде.

Алгоритм Хаффмана:

  1. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который равен частоте появления символа.
  2. Выбираются два свободных узла дерева с наименьшими весами.
  3. Создается их родитель с весом, равным их суммарному весу.
  4. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.
  5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.
  6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Алгоритм арифметического кодирования:

Рассмотрим в качестве примера строку abacaba:

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

  1. Считываем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Разделим этот отрезок на части, пропорциональные частотам встречаемости символов.
  2. Повторим пункт (1) до конца входного потока.
  3. Выберем любое число в пределах получившегося отрезка, которое и будет результатом арифметического кодирования

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

 

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

Здесь под символом подразумевается некий повторяющийся элемент исходной строки — это может быть как печатный знак (character), так и любая битовая последовательность. Под кодом подразумевается не ASCII или UTF-8 код символа, а кодирующая последовательность битов.

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

Процесс сжатия отражен в следующей таблице:

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

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

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

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

Метод JPEG включает три последовательных этапа:

  1. Предварительная обработка изображения.
  2. Спектральное преобразование данных.
  3. Квантование спектра и сжатие данных.

На 1-м этапе выполняются:

  • переход к цветоразностной модели;
  • разделение изображения на блоки;
  • «прореживание» блоков цветовых составляющих.

Переход к цветоразностной модели означает преобразование значений базовых цветовых составляющих R G B к тройке составляющих Y U V, где Y — яркость, U — хроматические красный, V — хроматические синий.

Формируются блоки размером 8×8 пикселов, которые обрабатываются при сжатии независимо друг от друга.

Четверки соседних блоков объединяются в макроблоки 16х16. Для цветовых составляющих U и V выполняется «прореживание», когда четверки соседних пикселей усредняются. В результате 4 блока составляющих U и V преобразуются в 1. При этом яркостная составляющая Y, как наиболее важная, остается без изменений, а каждому блоку из 4 пикселей (2х2) яркостного канала Y ставятся в соответствие усреднённые значения U и V.

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

Формально при этом коэффициенты Pxy исходной матрицы P преобразуется в коэффициенты dij матрицы D согласно приведенной на рисунке формуле.

Смысл преобразования заключается в том, что коэффициенты dij отражают «амплитуду колебаний» яркости пикселей. Например, если все пиксели блока имеют одинаковую яркость, то максимальными будет коэффициент d11 , а остальные dij = 0.

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

Порядок следования коэффициентов dij в соответствии с увеличением частоты («змейкой» от левого верхнего к нижнему правому углу) показан на рисунке.

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

Первоначально все коэффициенты матрицы D делятся с отбрасыванием дробной части на некоторые установленные делители. В примере такой делитель принят равным 8. В реальном алгоритме JPEG делители увеличиваются с возрастанием частот (на рисунке приведен фрагмент реальной матрицы делителей, в котором отображены первые 16 значений из 63).

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

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

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

Чем больше степень сжатия, тем большими задаются делители. В практическом алгоритме они увеличиваются в направлении правого нижнего угла матрицы D. В результате этой операции строка из 64 коэффициентов матрицы содержит длинные последовательности «0» и удобна для окончательного сжатия. Такое сжатие выполняется с использованием метода RLE для цепочек нулей и кодирования по Хаффмену остальных коэффициентов. В результате, как правило, объем исходного графического файла сокращается в 10-20 раз. Возможно задавать и большую степень сжатия, учитывая требования к качеству восстановленного изображения.

Более детально особенности обработки уже знакомого нам блока изображения отражены на рисунке.

 

Полезные ссылки:

 

 

 

Автор: Николай Свирневский