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

Информационные технологии Вестник Нижегородского университета им. H.H. Лобачевского,2014, № 4 (1), с. 495-501

УДК 004.9

КОДИРОВАНИЕ ИНДЕКСИРОВАННЫХ ИЗОБРАЖЕНИЙ С ИСПОЛЬЗОВАНИЕМ КОНТЕКСТНОГО МОДЕЛИРОВАНИЯ

© 2014 г. А.В. Борусяк, Ю.Г. Васин

НИИ прикладной математики и кибернетики Нижегородского госуниверситета им. Н.И. Лобачевского

sw-bor@yandex.ru

Поступила в редакцию 06.07.2014

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

Ключевые слова: сжатие, индексированные изображения, контекстное моделирование.

Введение

В настоящее время в связи с развитием информационных технологий, интернет-технологий, технологий передачи больших объемов графической информации и создания удаленных баз данных большое значение придается разработке эффективных моделей и алгоритмов сжатия данных. На данный момент универсальные алгоритмы сжатия хорошо изучены и создано множество эффективных программ на их базе. Но, в то же время, для многих областей остается актуальной разработка специализированных алгоритмов, ориентированных на конкретный тип данных [1—11]. Такие алгоритмы часто обладают значительным преимуществом, так как учитывают внутреннюю структуру и специфику сжимаемых данных. Одной из таких областей является сжатие индексированных растровых изображений (ИРИ).

Среди различных подходов к сжатию ИРИ важную роль играют методы и алгоритмы статистического кодирования с контекстным моделированием. При этом лидирующие позиции занимает алгоритм Prediction by Partial Matching (PPM) [1].

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

тропийного кодирования (алгоритм Хаффмана, арифметическое кодирование и т.п.) [1].

В данной работе рассматривается дальнейшее развитие моделей и методов статистического кодирования с контекстным моделированием [12, 13] для алгоритма сжатия ИРИ с учетом специфики этих данных.

Модели и методы контекстного

моделирования для эффективного сжатия индексированных изображений

Представим исходную растровую графическую информацию в виде двумерной матрицы А, где каждый элемент 5 = е (0,...,V) е А

соответствует одному пикселю изображения. Здесь I - строка,у - столбец, V е 1,...,255 - количество цветов изображения. Под сжатием данных будем понимать процедуру перекодирования данных, производимую с целью уменьшения их объёма. В результате работы алгоритма сжатия исходной информации А требуется получить новый набор данных, имеющий меньший (по сравнению с исходным изображением) объем. Для достижения поставленной цели используются методы статистического кодирования с контекстным моделированием. Под контекстным моделированием понимается оценка вероятности Р(?\С(Я)) появления символа 5 в зависимости от предшествующего ему контекста С (Я). Под символом понимается минимальный элемент входных данных (пиксель), вероятность которого оценивается при кодировании. Под контекстом С(Я) порядка Я подразумевается определенный набор из уже закодированных символов, которые предшествуют текущему кодируемому символу, где порядок Я является величиной контекста -

количеством символов, из которых состоит контекст. В данной работе рассматривается двумерный контекст c0,...,cRе C(R), где c„=ai-tj-i, t и I-

параметры, определяющие форму и размер контекста. В предложенном алгоритме контекст меньшего порядка n является набором из 0 < n < N первых элементов контекста максимального порядка C(N), N=max(R). В качестве контекстной модели используется вероятность появления пикселя _P(s|C(n)) определенного цвета (каждому цвету соответствует число от 0 до F-1), а также вероятность появления символа ухода P(esc|C(n)) в данном контексте [1, 12].

При вычислении этих вероятностей можно предположить, что при увеличении длины используемого контекста сжатие данных будет улучшаться, но при использовании контекстных моделей больших порядков статистика не успевает накапливаться. На практике более широкое распространение получило использование для оценки вероятности контекстов разных длин. Техника объединения оценок вероятностей, соответствующих отдельным активным контекстам, в одну оценку называется смешиванием (blending). Известно несколько способов выполнения смешивания. В работе использован модифицированный метод неявного взвешивания [12].

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

Для оценки вероятности ухода предложен следующий способ. Изначально частота символа ухода равна 0. При каждом новом встречаемом пикселе частота символа ухода увеличивается на единицу. Когда величина частоты символа ухода становится равной количеству раз-

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

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

Кодирование индексированных изображений

497

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

C целью повышения точности оценок символов в КМ высоких порядков был развит метод наследования информации. Очевидно, что распределения частот символов в родительских и дочерних КМ схожи. Тогда при появлении в дочерней контекстной модели порядка h (КМ(й)) нового символа s целесообразно инициализировать его счетчик fs\h) некоторой величиной f 0(s\h), зависящей от информации о данном символе в родительской КМ(да) (или нескольких контекстных моделях-предках), где fs\r) является накопленной частотой символа s в текущей КМ(г), f(r) - накопленная частота всех символов в текущей КМ(г) включая символ ухода (esc). При использовании КМ(ш) в случае, если получена оценка символа s, величина f0 (s | h) задается в виде f 0(s|h) =

=_f (s|m) f (h)__

f

j *o

На завершающем этапе при кодировании символа s в КМ(h) получаем вероятность

f

P(s | h) =-. Данная вероятность переда-

f

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

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

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

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

Оптимизация временной сложности алгоритма

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

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

Изначально в алгоритме использовалась структура ЛУЬ-дерева для хранения контекстных моделей. Поскольку алгоритм постоянно использует дерево моделей в своих операциях, реализация дерева моделей может существенно повлиять на скорость работы алгоритма. Ввиду этого было решено рассмотреть и другие варианты хранения дерева моделей. Были реализованы структуры В-дерева и Бр1ау-дерева, после чего было произведено сравнение скорости работы на этих структурах. Экспериментальная апробация показала, что В-дерево наиболее эффективно, и оно было принято в качестве основной структуры хранения дерева контекстных моделей.

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

Таблица 1

Сравнение времени кодирования файла artificial.bmp (3072^2048, глубина цвета 8 бит, _количество цветов 256) в зависимости от количества потоков_

Количество потоков Время PC1

1 7.94 93.657 13.301

2 6.563 11.141 13.173

4 4.671 16.187 13.041

8 4.494 29.656 12.766

16 4.323 27.515 12.344

32 4.349 41.593 11.742

64 4.022 25.688 10.963

Таблица 2

Сравнение времени кодирования файла 21008n.bmp (12358x16563, глубина цвета 8 бит, _количество цветов 12) в зависимости от количества потоков_

Количество потоков Время PC1

1 52.658 78.203 213.207

2 31.676 46.109 214.016

4 27.446 38.469 215.567

8 27.075 38.359 214.371

16 26.257 37.468 213.63

32 25.507 36.484 211.582

64 24.979 35.781 207.875

Для увеличения производительности обновление процентного индикатора процесса кодирования (декодирования) производится не каждый раз при переходе на новую строку изображения, а только раз в А/100 таких переходов, где И - высота обрабатываемого изображения.

Рассмотренные выше подходы позволили существенно (в 1.5-2 раза) уменьшить время кодирования. Также был снижен необходимый объем оперативной памяти, что позволяет избегать ее переполнения при кодировании сильно зашумленных или случайных изображений.

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

С целью дальнейшего увеличения скорости сжатия была реализована возможность распараллеливания процесса кодирования графических файлов. Для этого изображение разбивалось на п частей. Примем вертикальный размер (высоту) изображения за Н, горизонтальный размер (ширину) за Ж. На данный момент изображение разбивается следующим образом: если количество частей равно четырем, изображение делится по линиям, соединяющим середины его противоположных сторон. В результате этого образуются четыре прямоугольные области Р1, Р2, Р3, Р4 с координатами ((х1„у1), (х2„у2)) диаметрально-противоположных вершин Р1=((0,0), (Я72Н/2)), Р2=((Ж/2,0), (Ж,Н/2)), Р3=((0Н/2), (Я72Н)), Р4=((Я72Н/2),(ЖН)). В

случае, когда пф4, вертикальные стороны изображения делятся на п-1 равных частей высотой Hin и одну высотой (H-H/n*(n-1)). В результате образуется п—1 прямоугольная область P[i] (i = 0, п -1) с координатами Pi = ((0,(H/n)xi), (W,(H/n)x(i+1))) и одна прямоугольная область P[n] = ((0,(H/n)x(n-1)), (WH)). После разбиения изображения каждая его часть сжимается как отдельное изображение в отдельном потоке. При этом для каждой части изображения создается свой экземпляр кодировщика, и результат кодирования записывается в отдельный для каждого изображения буфер в оперативной памяти. После сжатия всех частей изображения буферы выходного потока каждого изображения последовательно записываются в выходной файл на жестком диске. Данный подход позволяет задействовать возможности современных компьютеров, равномерно распределяя нагрузку на ядра процессора, незначительно снижая эффективность сжатия. При реализации расчетов на четырехъядерном PC1 (процессор - Core i5-3230M 2.6 GHz) и на двухъядерном PC2 (процессор - Core 2 Duo E7400 2.8 GHz) были получены результаты, представленные в табл. 1 и табл. 2.

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

Квдмрвнавме мвдексмрвнаввых мзвбражевмй

499

пользуемых потоков. Данный коэффициент зависит от количества потоков, но не зависит от компьютера, на котором производится кодирование, поэтому для обоих компьютеров коэффициенты совпадают. Из экспериментов видно, что при использовании двухъядерных и четырехъядерных компьютеров оптимально использовать 4 потока для кодирования.

Мультиплатформенность

В настоящее время в мире получили большое развитие операционные системы, отличные от Windows. Большое количество устройств использует операционные системы на основе Linux, такие, как Android, также много пользователей операционной системы фирмы Apple. Ввиду этого важна возможность создания нескольких версий одной программы для разных операционных систем. Для включения свойства кроссплатформенности был осуществлен перенос программы в мультиплатформенную среду разработки Qt 4.8.3. Это позволило увеличить производительность, сделать структуру программы более гибкой и добавило приложению свойство мультиплатформенности.

Особенности реализации

алгоритма кодирования

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

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

Используются контекстные модели 8, 5, 2, 1 и нулевого порядков. В контекстной модели нулевого порядка счетчики пикселей при инициализации равновероятны и равны единице. Так как вычислять заново контексты меньших порядков неэффективно, то они вычисляются для первых n<N байт контекста максимального порядка длины N.

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

Результаты

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

Для проверки эффективности алгоритма были осуществлены эксперименты на 2 тестовых наборах изображений и проведено сравнение с наиболее распространенными универсальными и специализированными алгоритмами сжатия изображений: JPEG-LS [7], PNG [8], 7z, rar. Первый тестовый набор включает в себя 6 индексированных 256-цветных изображений различного типа: 1 - тестовое черно-белое изображение из набора artificial, 2 - тестовое черно-белое изображение из набора boats, 3 - индексированное цветное изображение chair, 4 - полутоновое изображение из набора goanna, 5 -спутниковый снимок, 6 - цветное индексированное изображение peppers. Второй набор тестовых изображений является копией первого набора с редуцированным до 8 количеством цветов.

Результаты экспериментов приведены в таблицах 3 и 4.

В столбцах таблиц 3 и 4 приведены Ксж для различных алгоритмов, строки соответствуют различным тестовым данным.

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

Программе требуется в среднем 50-500 Мб оперативной памяти при сжатии изображения размером до 6 Mpix, а скорость кодирования/декодирования примерно равна 0.5 Мегапикселей в секунду на компьютере с процессором Core 2 Duo 2.8 Мгц при использовании 2 потоков.

Таблица 3

Сравнение алгоритмов по коэффициенту сжатия _на тестовом наборе ^ 1 (256 цветов)__

№ изображения IPC JLS PNG rar 7z

1 13.31 10.01 9.07 9.34 11.63

2 1.62 2.01 1.83 1.58 1.59

3 4.84 3.50 3.06 4.17 4.16

4 1.23 1.51 1.36 1.21 1.34

5 3.17 2.62 2.57 2.96 2.78

6 2.17 1.59 1.28 1.77 1.97

Таблица 4

Сравнение алгоритмов по коэффициенту сжатия _на тестовом наборе 2 (8 цветов)__

№ изображения IPC PNG JPEG-LS rar 7z

1 11.095 6.34 5.74 7.22 8.50

2 20.390 10.86 9.24 14.69 14.38

3 8.808 6.73 4.29 7.17 6.65

4 4.208 2.93 2.30 3.65 3.45

5 5.465 4.72 3.36 4.78 4.47

6 9.722 4.92 3.99 6.99 6.36

7 20.591 13.77 7.84 13.84 13.81

Работа выполнена при финансовой поддержке РФФИ (проекты № 13-07-00521, № 13-07-12211).

Список литературы

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

2. Сэломон Д. Сжатие данных, изображений и звука. М.: Техносфера, 2006.

3. Марков А. А. Введение в теорию кодирования. М.: Наука, 1982.

4. Лидовский В.В. Теория информации: Учебное пособие. М.: Компания Спутник +, 2004. С. 111.

5. Савич У. Программирование на C++. СПб.: Питер, 2004.

6. Интернет-ресурс: www.compression.ru.

7. Спецификация tiff: http://cs.mipt.ru/docs/comp/ eng/develop/ formats/tiff/main.pdf.

8. Спецификация PNG: http://www.w3.org/TR/ PNG/.

9. Спецификация DJVU: http://www.celartem.com/ product/ doc/specs/sdjvuspec.djvu.

10. Vasin Yu.G. and Zherzdev S.V. Information Techniques for Hierarchical Image Coding // Pattern Recognition and Image Analysis. 2003. V. 13. №. 3. Р. 539-548.

11. Жерздев С.В. Сжатие изображений в извещениях мореплавателям // Технологии Microsoft в теории и практике программирования. Материалы конференции. Н.Новгород: Изд-во ННГУ, 2007. С. 328.

12. Borusyak A.V., Vasin Yu.V., Zherzdev S.V. Compression of Binary Graphics Using Context Simulation // Pattern Recognition and Image Analysis, 2013. V. 23. № 2. Р. 207-210.

13. Borusyak A.V., Vasin Yu.V., Zherzdev S.V. Optimizing the computational complexity of the algorithm for adaptive compression of binary raster images // The 11-th International Conference «Pattern Recognition and Image Analysis: new information technologies». Samara, 2014. Р. 170-172.

ENCODING INDEXED IMAGES WITH THE USE OF CONTEXTUAL SIMULATION

A.V. Borusyak, Yu.G. Vasin

The compression problem of indexed bitmap images is considered on the basis of statistical encoding with the use of contextual simulation. Development trends for models and methods of contextual simulation for an efficient algorithm of compression of indexed graphic information are considered. An efficient algorithm for encoding indexed images has been developed, including optimization and parallelization of calculations.

Keywords: compression, indexed images, contextual simulation.

KodupoBaHue móeKcupoBambix u3o6paw:eHuü

501

References

1. Vatolin D., Ratushnyak A., Smirnov M., Yurkin V. Metody szhatiya dannyh. Ustrojstvo arhivatorov, szhatie izobrazhenij i video. M.: DIALOG-MIFI, 2003.

2. Sehlomon D. Szhatie dannyh, izobrazhenij i zvu-ka. M.: Tekhnosfera, 2006.

3. Markov A.A. Vvedenie v teoriyu kodirovaniya. M.: Nauka, 1982.

4. Lidovskij V.V. Teoriya informacii: Uchebnoe posobie. M.: Kompaniya Sputnik +, 2004. S. 111.

5. Savich U. Programmirovanie na C++. SPb.: Piter, 2004.

6. Internet-resurs www.compression.ru.

7. Specifikaciya tiff http://cs.mipt.ru/docs/comp/ eng/develop/ formats/tiff/main.pdf.

8. Specifikaciya PNG http://www.w3.org/TR/ PNG/.

9. Specifikaciya DJVU http://www.celartem.com/ product/ doc/specs/sdjvuspec.djvu.

10. Vasin Yu.G. and Zherzdev S.V. Information Techniques for Hierarchical Image Coding // Pattern Recognition and Image Analysis. 2003. V. 13. №. 3. Р. 539-548.

11. Zherzdev S.V. Szhatie izobrazhenij v izvesh-cheniyah moreplavatelyam // Tekhnologii Microsoft v teorii i praktike programmirovaniya. Materialy konfer-encii. N. Novgorod: Izd-vo NNGU, 2007. S. 328.

12. Borusyak A.V., Vasin Yu.V., Zherzdev S.V. Compression of Binary Graphics Using Context Simulation // Pattern Recognition and Image Analysis, 2013. V. 23. № 2. Р. 207-210.

13. Borusyak A.V., Vasin Yu.V., Zherzdev S.V. Optimizing the computational complexity of the algorithm for adaptive compression of binary raster images // The 11-th International Conference «Pattern Recognition and Image Analysis: new information technologies». Samara, 2014. Р. 170-172.