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

Размещено на http://www.allbest.ru/

Военный институт телекоммуникации и информатизации НТУУ «КПИ»

МЕТОД ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНОГО ПОРЯДКА КОНТЕКСТА АЛГОРИТМА ррм

к.т.н., Дядык Д.Ф., к.т.н.,

доцент Стрюк А.Ю., Заика Ю.Л.

Аннотация

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

Ключевые слова: сжатие данных, степень сжатия, контекстное моделирование, контекст

Вступление

Основными параметрами алгоритма РРМ являются: порядок максимального контекста и оценка вероятности ухода на контекстную модель меньшего порядка. В данном подразделе рассмотрена проблема выбора максимального порядка контекста и предложен метод определения максимального порядка контекста алгоритма РРМ [1].

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

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

Целью статьи является разработка метода аналитического определения максимального порядка контекста для алгоритмов контекстного моделирования.

Основная часть

Рассмотрим ансамбли сообщений 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 Оценка степени сжатия данных для разных порядков контекста

Выводы

В работе предложен метод определения аналитическим путем порядка максимального контекста для алгоритма контекстного моделирования РРМ. Данный метод позволит на этапе разработки методов сжатия изображений аналитически определить максимальный порядок контекста для алгоритма контекстного моделирования РРМ.

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

Полученные результаты показывают увеличение степени сжатия на 39-41 %, при использовании разработанного метода.

Литература

1. Ватолин Д., Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео / А. Ратушняк, М. Смирнов, В. Юкин. М.: ДИАЛОГ-МИФИ, 2002. 384 с. www.compression.ru/book/.

2. Миано Д. Форматы и алгоритмы сжатия изображений в действии. М.: Триумф, 2003.

3. Ватолин Д.С. Алгоритмы сжатия изображений. Лаборатория компьютерной графики МГУ: http: // graphics. cs.msu.su / library / our publications / fractal / index.htm.

4. Яне Б. Мир цифровой обработки изображений, М.: Техносфера, 2007. 584 с.

5. Стрюк А.Ю., Резуненко А.А. Метод сжатия видеоданных с использованием вейвлет-преобразования // Мат. 3-ей Междунар. научно-техн. конф. «Проблемы информатики и моделирования». Харьков: НТУ «ХПИ», 2003. С. 24.

6. Howard P.G., Witter J.S. Error modeling for hierarchical lossless image compression // Proc. IEEE Data Compression Conference, Snowbird, Utah, 1992. P. 269-278.

7. Шкарин Д. Повышение эффективности алгоритма PPM // Проблемы передачи информации, 34(3), с.2-54, 2001.

8. Memon N., Wu X. Recent Developments in Context-Based Predictive Techniques for Lossless Image Compression // The Computer Journak, Vol. 40, No. 2/3, 1997. www.compression.ru/download/articles/i_lless/memon_xu_1997cj_context_pdf.rar.

9. В.И. Шульгин. Основы теории передачи информации. Ч. I. Харьков: Нац. аэрокосм. ун-т « Харьк. авиац. ин-т », 2003. с. 102.

10. Дядик Д.Ф. Выбор порядка контекста при разработке метода сжатия изображений / О.Ю. Стрюк // Інформаційні технології та комп'ютерна інженерія., 2007, №1 (8), с. 197-204.

11. Maarten J. Second generation wavelets and applications / Patrick O. // Springer-Verlag London Limited, 2005. 138 p.

Размещено на Allbest.ru