Метод определения максимального порядка алгоритма РРМ

Рассмотрим ансамбли сообщений S1={s1} и S2={s2} и их произведение S1хS2={(s1, s2), p (s1,s2)}. Для любого определённого можно построить условное распределение вероятностей p (s1/s2) на множестве S1 и для каждого подсчитать собственную информацию [2, 3, 4]:

бит.

Данное значение информации называют условной собственной информацией сообщения s1 при фиксированном s2.

Усреднив условную информацию по, получим условную энтропию S1 при фиксированном .

бит/символ.

Полученное значение энтропии является случайной величиной, поскольку зависит от случайной переменной s2. Для получения неслучайной информационной характеристики пары вероятностных ансамблей, усредним данную энтропию по всем значениям s2. Получим формулу, определяющую условную энтропию ансамбля S1 при фиксированном ансамбле S2 (1). бит/символ. (1).

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

(2).

Это свойство наглядно показывает значение условной энтропии и использование зависимости контекста символов при кодировании источника. Аналогично формуле (3.1), которая определяет условную энтропию, учитывая зависимость двух соседних символов или другими словами контекст 1-го порядка, можно определить формулу определения условной энтропии для контекста 2-го порядка и больших порядков:

бит/символ. (3).

Согласно свойству (2) энтропия при увеличении порядка учитываемого контекста не возрастает, что свидетельствует о теоретическом увеличении степени сжатия данных при увеличении порядка контекстной модели [5].

Под порядком контекстной модели понимается максимальный размер учитываемого контекста D. Основная особенность метода — кодирование нового (в текущем контексте сd, размера d? D) символа si в одном из внутренних узлов контекстного дерева. При этом для описания этого узла используются специальные символы ухода esc. Условные вероятности, используемые для кодирования в узле с символов и символа ухода esc, представляют в виде (4) и (5).

(4).

(5).

где — номер кодируемого символа в потоке;

— контекст порядка ;

tn (s|cd) — накопленная частота символа s в контексте cd;

tn (esc|cd) — накопленная частота esc в контексте cd;

Tn (cd) — частота появления контекста.

Оценка вероятности ухода определялась согласно классического метода РРМА, по выражению (6).

(6).

где, cf (сd) — накопленная частота появления контекста cd.

Таким образом, кодовая условная вероятность любого символа представляется в виде выражения (7) [6].

(7).

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

С целью упрощения модели РРМ была проведена соответственная инициализация контекстной модели 0-го порядка — установлены значения счётчиков всех символов в 1. Это позволило исключить из общей модели контекст -1-го порядка.

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

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

На начальном этапе работы алгоритма частота появления символа ухода будет значительной, так как частота появления символов в данном контексте tn (s|cd) = 0. Но с постепенным накоплением статистики в данном контексте влияние символа ухода на коэффициент сжатия уменьшается. Поэтому учёт символа ухода при вычислении условной энтропии является обязательным.

Влияние символа ухода esc на степень сжатия увеличивается при увеличении максимального порядка контекста, так как накопление статистики в контекстах больших порядков происходит достаточно медленно, а кодирование всего контекстного дерева приводит согласно выражению (7), к значительным потерям степени сжатия, вплоть до увеличения размера исходных данных. Поэтому возникает задача выбора оптимального порядка контекстной модели D при разработке алгоритма сжатия данных. Актуальность задачи проявляется на рассматриваемом типе данных — изображениях, так как методы контекстного моделирования, в классическом виде, широкого применения в алгоритмах сжатия изображений не нашли.

Вычисление условной энтропии контекстной модели алгоритма необходимо проводить с учётом всех порядков контекстов i=0.D. На первом этапе определяется условная энтропия модели максимального порядка HD (S1|S2…SD). К полученному значению добавляются значения условной энтропии моделей меньших порядков с учётом коэффициента k, который характеризует частоту оценки символа в контексте данного порядка (9) [6, 7].

(9).

где cum — общее количество кодированных символов.

Таким образом, условная энтропия всей контекстной модели с максимальным порядком контекста D определяется согласно выражения (3.10) [10, 11].

бит/символ, (10).

где kD = 1.

Определение максимального порядка контекста алгоритма РРМ производится путём нахождения максимального порядка контекста, для которого значение энтропии контекстного дерева будет минимальной:

контекст алгоритм энтропия моделирование.

порядок D,.

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

Рис. 1 Оценка степени сжатия данных для разных порядков контекста