7. Дополнительные сведения о методах сжатия сообщений
Курс “Теория информации и кодирования”

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

Универсальный прогнозный метод сжатия без потерь. Алгоритм PPM
Универсальный сортировочный метод сжатия без потерь. Алгоритм BZip2
Стандарт сжатия изображений с потерями JPEG-2000
Реализация сжатия видео. Метод MPEG

7.1 Универсальный прогнозный метод сжатия без потерь. Алгоритм PPM

Описание подхода
Метод основан на прогнозировании вероятностей последующих знаков на основе предыстории, а также их кодировании с помощью таблицы Хаффмена, которая постоянно корректируется по мере изменения статистики. Особенности алгоритма иллюстрирует рис.7.1:
  • по мере обработки знаков сообщений накапливаются оценки их условных вероятностей на различную глубину. В описании метода использован термин “контекст глубины Ki”. В частности, контексту K0 соответствуют безусловные вероятности знаков, контексту K1 – условные вероятности на глубину 1 знак, К2 — на глубину 2 знака и т.д.
  • кодер предсказывает вероятности появления разных знаков в следующей позиции с учетом разных контекстов. При этом “старшим” контекстам с более глубокой памяти присваиваются большие веса, как более информативным. Например, предсказанная вероятность знака может рассчитываться по формуле P = 0,1*P0 + 0,3*P1 + 0,6*P2, где P0, P1 и P2 вероятности появления знаков соответсвенно в контекстах K0, K1 и K2. В современных архиваторах используются контексты вплоть до уровней 5-6;
  • исходя из предсказанных вероятностей знаков кодер корректирует таблицу Хаффмена. Опираясь на обновленную таблицу, выполняется статистическое кодирование фактически поступающего знака. Если бы прогноз был идеальным, то каждый поступающий знак кодировался бы максимально коротко. На самом деле прогноз статистический и он сбывается далеко не всегда, но в среднем такой метод дает выигрыш;
  • сжатый код представляет собой последовательность битов, которая корректно декодируется благодаря правилу префиксности и синхронному изменению таблиц Хаффмена. Напомним, что синхронизация достигается за счет использования общих правил изменения таблиц на стороне кодера и декодера. В целом прогнозный метод сжатия обеспечивает максимальную степень сжатия для текстов — это и есть целесообразная сфера его использования.

Пример применения прогнозного способа
На рис.7.2 отображен ключевой этап метода — прогноз вероятностей знаков в очередной позиции:
  • в примере из 23 знаков фразы обработано 16 и прогнозируется значение 17-го знака. При этом условно предполагается использования алфавита из 100 символов. Так что помимо 7 уже появлявшихся видов знаков могут появиться еще 93. Метод предусматривает начальную инициализацию счетчиков всех знаков 1, что учитывается при подсчете вероятностей;
  • исходя из подсчета безусловных вероятностей (контекст К0) наиболее ожидаемо появление буквы «o». С учетом предшествующей буквы (в контексте К1 это тоже «o») скорее всего может появиться “с” и также вероятна “й”. А вот в контексте К2 наиболее вероятно появление “й” (ранее фиксировалась цепочка “сой”). Учет значимости контекстов дает наибольшую вероятность букве “й” (благодаря контексту К2) и высоко оценивает и вероятность “с” (благодаря К1). Другие знаки имеют значительно меньшие вероятности (на рисунке они показаны для ранее встречавшихся “о” и “к”, но алгоритм предусматривает их подсчет для всех знаков используемого алфавита);
  • по результатам полного набора прогнозных вероятностей алгоритм строит таблицу Хаффмена. Когда появляется реальный следующий знак текста (в данном случае “й”), он будет закодирован оптимально, поскольку именно его алгоритм считал наиболее вероятным. Если бы оценки вероятностей получились несколько иными (например, наиболее вероятным получилось бы “с”, а “й” занял вторую позицию), кодирование все равно было бы неплохим, поскольку “й” находится в верхушке списка.

Контрольные вопросы:
1) Опишите действие метода прогнозного сжатия, опираясь на рис.7.1.
2) Поясните понятие “глубина контекста” применительно к данному методу. Почему более глубокие контексты считаются более значимыми.
3) Поясните пример действия метода, исходя из рис.7.2.
4) Какова оптимальная область применения метода и почему.


7.2 Универсальный сортировочный метод сжатия без потерь. Алгоритм BZip2

Описание подхода
Сортировочный метод предусматривает преобразование контекста в форму, наиболее удобную для статистического сжатия. Такое преобразование выполняется в рамках блоков сообщения. Одной из наиболее популярных реализаций метода является алгоритм bzip2, структуру которого характеризует (рис.7.3):
  • на первом этапе обработка блока включает его преобразование по Барроузу-Уиллеру. В результате одинаковые знаки, которые были рассредоточены по всему блоку, группируются в однородные цепочки;
  • на втором этапе по отношению к результатам предыдущего может выполняться преобразование MTF (move-to-front), которое еще называют сортировкой по методу «стопки книг». Здесь часто встречающиеся знаки получают меньшие номера. К тому же все знаки однородной цепочки кроме первого заменяются нулями. В результате в блоке образуется большое количество одинаковых знаков (нулей), что очень удобно для статистического сжатия. Альтернативой MTF в других реализациях метода может быть сжатие однородных цепочек знаков по алгоритму RLE;
  • наконец, на последнем этапе выполняется статистичекое сжатие — например, по методу Хаффмена.

Пример выполнения преобразования Барроуза-Уиллера
Пример выполнения BWT показан на рисунке 7.4.
Преобразование включает три этапа:
  • на первом очередной блок сообщений разворачивается в квадратную матрицу, каждая строка которой получена циклическим сдвигом предыдущей;
  • на втором этапе строки матрицы сортируются - например, по возрастанию кода знаков;
  • на третьем шаге в качестве результата используется последний столбец матрицы, а также номер позиции, в которой находилась исходная строка после сортировки (последнее необходимо для восстановления исходного вида блока).

Как видно в примере, здесь выделяются повторяющиеся элементы текста: за буквой “У” часто следуют “-K”, за “-” повторяются “КУ”, а вслед за “K” - сочетание “У-”. В результате преобразования знаки “У”, “-” и “K” сосредотачиваются в однородные цепочки. Разумеется, в реальных сообщениях разнообразие знаков в блоках гораздо выше, однако и сами блоки обычно включают сотни знаков, так что эффект от перегруппировки существенен. Еще раз подчеркнем, что он тем больше, чем чаще встречаются повторяющиеся группы символов.

Важнейшей особенностью BWT является его обратимость. Полное описание алгоритма восстановления достаточно громоздко, так что мы ограничимся ссылкой на источник [...], где данный подход описан подробно.

Пример выполнения преобразования MTF
На рис.7.5 показано выполнение MTF для результатов предыдущего этапа:
  • первоначально все знаки получают исходные номера (в нашем примере для наглядности используем номера только четырех имеющихся в блоке знаков);
  • при появлении очередной знак блока кодируется своим текущим номером (в примере буква «У» заменяется на 3). После этого его код становится минимальным, а коды всех остальных знаков увеличиваются на «1» (последующие буквы «У» кодируются как «0», а знак «-» при первом появлении имеет номер «1». В дальнейшем эта процедура повторяется до конца блока).

Как видно, в результате такого преобразования неоднородность распределения вероятностей знаков существенно возросла (прежде всего за счет частого использования «0»). В результате статистическое кодирование по Хаффмену дает большее сжатие, чем до применения MTF.

Контрольные вопросы
1) Опишите этапность сортировочного сжатия в рамках алгоритма bzip2, опираясь на рис.7.3.
2) Охарактеризуйте действие преобразования Барроуза-Уиллера на блок данных, опираясь на пример рис.7.4.
3) Какие данные необходимы для восстановления исходного вида блока с помощью преобразования Барроуза-Уиллера.
4) Опишите выполнение преобразования MTF, опираясь на рис.7.5. Почему именно средняя длина кода при кодировании по Хаффмену значительно уменьшается в результате использования MTF.


7.3 Стандарт сжатия изображений с потерями JPEG-2000

Идея метода
Стандарт JPEG-2000 разрабатывался с целью преодоления недостатков JPEG. В частности, он должен был обеспечить существенное повышение степени сжатия без мозаичности изображений, а также возможность сжатия без потерь.
Идея метода - сжатие за счет усреднения характеристик соседних пикселей с постепенным уменьшением кода всего изображения (рис.7.6). При этом:
  • на каждом шаге за счет усреднение яркостей соседних пикселей основное изображение уменьшается в 4 раза. Одновременно сохраняются отличия исходных пикселей от усредненного, что позволяет в дальнейшем восcтановить изображение (на рис.7.6 эти отличия отображены подобно теням на барельефе);
  • сохраняемые отличия исходных пикселей от усредненного сами по себе относительно малы, что позволяет кодировать их более экономично. Кроме того “диагональная” часть изображения вообще не несет информации (это наглядно видно на рис.7.6), так что ее можно не сохранять. Получаемая таким образом экономия позволяет в принципе сжимать изображение без потерь;
  • описанная процедура выполняется несколько раз итеративно (на каждом шаге результаты предыдущего используются в качестве исходных данных). При этом мы как бы движемся от более высокочастотных составляющих спектра (различия в соседних пикселях) к низкочастотным (плавные изменения фона). Такое преобразование называют “вейвлетным” (wavelet - «волночка») или полностью — дискретным вейвлетным преобразованием ДВП;
  • вейвлетное преобразование автоматически разделяет обработку плавных («низкочастотных») изменений изображения, которые важны для восприятия, от мелких “высокочастотных” деталей, которыми можно пожертвовать Первые проявляются при усреднении яркостей соседних пикселей, а вторые — за счет вычисления их разности. Это еще часто называют низкочастотным и высокочастотным фильтрами. Важно, что такая фильтрация ведется для всего изображения, что позволяет сделать все его изменения плавными;
  • на каждом шаге преобразования отличия пикселей от среднего (высокочастотные составляющие) могут огрубляться за счет квантования, что позволяет существенно сжимать их код, но приводит к потере качества. Визуально такое сжатие проявляется как размывание изображения. При больших степенях сжатия оно воспринимается глазом более лояльно по сравнению с мозаичностью JPEG, что позволяет существенно увеличить степень сжатия (вплоть до 1:50).

Общая структура алгоритма JPEG-2000
В целом в алгоритме выделяются те же основные этапы, что и в JPEG – предварительная обработка, спектральное (здесь вейвлетное) преобразование и кодирование (квантование с последующим сжатием) — рис.7.7. При этом:
  • на этапе предварительной обработки, как и в JPEG, выполняется переход к цветоразностной модели YUV и прореживание цветовых составляющих. Важное отличие состоит в том, что здесь не происходит разбиение на маленькие блоки 8х8. Изображение может обрабатываться либо полностью, либо (с учетом ограничений по используемой памяти) разбивается на крупные квадратные зоны тайлы (tile - «плитка»), для каждого из которых обработка ведется независимо;
  • дальнейшая обработка выполняется по шагам-итерациям (обычно от 4 до 8), число которых алгоритм определяет с учетом требуемой степени сжатия. При этом последовательное «углубление» обработки реализуется только для его низкочастотной части (основного изображения), а код мелких деталей, которые выделяются высокочастотной фильтрацией, постепенно накапливается в сжатом виде. Ниже мы более подробно рассмотрим внутреннее устройство шага такой итерации.

Особенности обработки для одного шага преобразования
Этапы обработки внутри каждой итерации показаны на рис.7.8:
  • очередной шаг вейвлетного преобразования включает вычисление среднего значения для четверки cоседних пикселей, а также вычисление полуразностей по строке, столбцу и диагонали. Эта операция выполняется для всех четверок пикселей внутри основной части изображения (LL);
  • квантование (огрубление) полученных значений выполняется только для полуразностей по строкам и столбцам (HL и LH), при этом диагональные элементы НН не хранятся. Разумеется в режиме сжатия без потерь огрубление не используется;
  • при кодировании обычно первоначально выделяются блоки размером 32х32 пикселя. Это удобно для стандартизации их обработки, но также способствует помехоустойчивости алгоритма, поскольку возможные искажения при передаче или хранении влияют только на небольшую часть изображения. Для “подготовительного” кодирования используется достаточно изощренный алгоритм, обеспечивающий увеличение количества нулей (здесь мы не станем рассматривать его детально). На конечном этапе применяется арифметическое кодирование.

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

Важным достоинством JPEG-2000 является возможность выбирать режимы сжатия для разных зон изображения, а также помехоустойчивость. Кроме того гораздо лучше сжимает изображения, созданные в компьютерных редакторах, и изображения документов. Снижение качества изображения проявляется в его сглаживании («замыливании»), а при сильном сжатии — также в появлении ряби в окрестностях резких границ.
Главным недостатком метода является низкая скорость сжатия.

Контрольные вопросы
1. Расскажите об идее метода сжатия в JPEG-2000, опираясь на рис.7.6.
2. Расскажите о структуре алгоритма JPEG-2000, используя рис.7.7.
3. Охарактеризуйте особенности этапа подготовки изображения в JPEG-2000.
4. Как реализуется в алгоритме вейвлетное преобразование. Какие преимущества дает его применение.
5. Каковы особенности этапов огрубления и кодирования в JPEG-2000.
6. В чем состоят преимущества и недостатки JPEG-2000 относительно JPEG.


7.4 Фрактальное сжатие изображений

Идея и область применения метода
Многие изображения содержат похожие друг на друга элементы, которые отличаюся лишь расположением, масштабом, углами поворота, растяжением и т.п. Ярким примером здесь может служить ветка папоротника, где листья похожи не только друг на друга, но и на всю ветку в целом. О таких элементах говорят, что они обладают свойством “самоподобия”. Принципиально важно, что для них может быть получено компактное математическое описание на основе вариации параметров одного единственного объекта-прототипа, который называют фракталом (рис.7.9).
Идея данного метода сжатия состоит в том, чтобы заменить исходное изображение, на построенное с использованием фракталов. Поскольку их математическое описание компактно (подобно описанию элементов векторной графики), степень сжатия может быть очень высокой (в сотни раз). При этом:
  • математический аппарат для формирования сложных изображений из фракталов достаточно прост. Классическим примером здесь часто служит та же ветка папоротника, построенная таким методом (этот пример связан с именем первооткрывателя метода и его часто называют «папоротником Барнсли»);
  • в силу простоты математических преобразований скорость построения изображения по его фрактальному описанию высока (c позиций сжатия данных такая операция соотвествует декодированию. Вместе с тем, обратную задачу, которая включает нахождение похожих (“самоподобных”) элементов и определение соответствующих параметров фракталов для в исходного изображения, решить гораздо сложнее. На практике такое решение, которое отвечает кодированию изображения, требует немалого времени;
  • исходя из упомянутых особенностей фрактального сжатия становится понятной область его применения. Во-первых, такой метод может использоваться для сжатия с потерями (точное воспроизведение изображение таким способом в общем случае очевидно невозможно). Во-вторых, он может быть эффективным, когда время воспроизведения критично, а время сжатия, напротив, слабо ограничено (Примером здесь могут быть изображения, которые часто запрашиваются пользователями с серверов). Наконец, в-третьих, фрактальное сжатие хорошо приспособлено именно для изображений природных объектов (например, фотографий высокого разрешения).

Основы математики фракталов: аффинные преобразования
В основе математического аппарата фрактального сжатия лежит использование математических “аффинных” преобразований (рис.7.10):
  • аффинные преобразования (АП) включают перемещения объекта на плоскости и его повороты (движения), а также его растяжения и сжатия относительно точки (масштабирование) и относительно прямых (равномерное растяжение-сжатие на плоскости);
  • важным свойством аффинных преобразований является сохранение некоторых свойств фигур. В частности, при АП прямые переходят в прямые, сохраняется наличие кривизны и параллельность линий, отношения длин отрезков на прямой и соотношения площадей;
  • для фрактальных преобразований широко используются так называемые сжимающие АП, которые сближают точки изображения. В частности, их применяют в итеративном режиме (когда результаты предыдущего шага преобразования используются в качестве исходных данных последующего). Простым примером сжимающего преобразования может быть процедура yк+1=0,5yк. К использованию сжимающих АП мы вернемся в дальнейшем.

Основы математики фракталов: системы итерированных функций
Для построения изображений на основе аффинных преобразований используются так называемые «системы итерированных функций» (СИФ) — рис.7.11:
  • в частности, на рис.7.11а показано последовательное построение так называемого «треугольника Серпинского». Здесь середины сторон равностороннего треугольника соединяются между собой, а из четырех образовавшихся меньших треугольников «внутренний» удаляется. Эта процедура повторяется итеративно для каждого образующегося треугольника. По мере продолжения итераций, фигура изменяется все меньше, то есть стремится к некоторому устойчивому изображению;
  • на рис.7.11б отображена СИФ, которая приводит к таким результатам. Каждая из трех функций f1, f2 и f3 уменьшают масштаб исходного треугольника и сдаигают результат в соответсвующую позицию - левый угол для f1, правый для f2 и верхний для f3 (цвета здесь использованы для наглядности). Как видно, преобразование выполняется с помощью простых функций, а его настройки определяются всего 18-ю числовыми коэффициентами;
  • наконец, на рис.7.11в показано использование той же СИФ в случае, когда исходной фигурой будет не треугольник, а квадрат. Интересно и важно, что в результате последовательности итераций независимо от исходного «материала» получается та же самая фигура (по мере уменьшения размера элементов визуальные различия постепенно нивелируются). Это означает, что получаемое изображение полностью определяется параметрами СИФ.

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

Понятие об алгоритме фрактального сжатия
Итак, фрактальное сжатие должно обеспечить выявление в изображении самоподобных участков изображения (фракталов) и определение параметров соответствующих СИФ, которые бы размещали фракталы в нужных позициях и ракурсах. Принципы построения популярной версии такого алгоритма иллюстрирует рис.7.12:
  • первоначально все изображение делится на множество непересекающихся квадратных элементов — квантов (термин range также буквально переводят как “ранговая область”). Из них в дальнейшем формируется минимальный набор необходимых фракталов. Полученную сетку называют еще панелью выбора;
  • формируется пул (набор) всевозможных пересекающихся блоков изображения (доменов — domain), состоящих из четверок соседних квантов;
  • для каждого кванта по очереди “примеряются” различные доменные блоки и при их совпадении с достаточной точностью определяются параметры преобразования, которые позволяют заместить им данный участок изображения;
  • этапами «примерки» фрактала к содержимому конкретного домена могут быть:
  • идентификация домена (подходит ли он в качестве кандидата на представление данным фракталом,
  • коррекция фона и огрубление — своебразная калибровка характеристик домена под фрактал. Здесь определяются параметры необходимых преобразований;
  • оценка «погрешности» аппроксимации, с учетом которой принимается решение, будет ли фрактал при сформированных параметрах использоваться в данном домене.

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

Контрольные вопросы
1. Охарактеризуйте идею и область применения фрактального сжатия изображений.
2. Пользуясь рис.7.10, поясните особенности аффинных преобразований изображений. Как такие преобразования используются во фрактальном сжатии.
3. На примере, показанном на рис.7.11, поясните использование систем итерированных функций (СИФ) для посторения сложных изображений из фракталов.
4. Дайте общую характеристику алгоритма фрактального сжатия изображений.
5. Опираясь на рис.7.12, поясните этапы «примерки» фрактала, содержащегося в обрабатываемом кванте изображения, к содержимому очередного домена.


О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2013 • Теория информации и кодирования
UP