Содержание к диссертации
Введение
ГЛАВА 1. Методы, алгоритмы и форматы представления для сжатия данных 9
1.1 Статистические методы сжатия 9
1.2 Словарные методы сжатия 12
1.3 Контекстное моделирование 13
1.4 Методы с преобразованием 15
1.5 Рекурсивный (волновой) алгоритм 15
1.6 Фрактальный алгоритм 16
1.7 Алгоритм JPEG 17
1.8 Иерархический метод адаптивного сжатия 18
1.9 Форматы сжатия изображений 18
Выводы по первой главе 23
ГЛАВА 2. Развитие и разработка моделей и методов контекстного моделирования для эффективного сжатия растровых изображений 24
2.1 Алгоритм сжатия растровых изображений на базе единой методологии контекстного моделирования и статистического кодирования 24
2.2 Развитие и поиск структуры представления контекстных моделей в оперативной памяти 34
2.3 Развитие структуры хранения и поиска контекстных моделей 39
Выводы по второй главе 41
ГЛАВА 3. Модели и методы контекстного моделирования для эффективного сжатия индексированных и полноцветных изображений 42
3.1 Бинарные изображения 42
3.2 Алгоритм сжатия бинарных растровых изображений без потерь 46
3.3 Модификации алгоритма PCTB 52
3.4 Индексированные изображения 57
3.5 Контекстное моделирование для сжатия индексированных растровых изображений 60
3.6 Методы в предлагаемом алгоритме IPC 65
3.7 Полноцветные изображения 67
Выводы по третьей главе 75
ГЛАВА 4. Программный комплекс сжатия растровых изображений 77
4.1 Описание программного комплекса 77
4.2 Описание классов контекстной модели 81
4.3 Распараллеливание алгоритмов кодирования 82
4.4 Экспериментальные апробации алгоритма PCTB 86
4.5 Результаты тестирования алгоритма IPC 90
4.6 Экспериментальные апробации алгоритма FPC 92
4.7 Зависимость основных параметров сжатия от величины контекста 94
4.8 Описание формата выходного файла 95
4.9 Мультиплатформенность 97
4.10 Особенности реализации 97
Выводы по четвертой главе 99
Заключение 100
Список литературы 102
- Рекурсивный (волновой) алгоритм
- Развитие и поиск структуры представления контекстных моделей в оперативной памяти
- Алгоритм сжатия бинарных растровых изображений без потерь
- Результаты тестирования алгоритма IPC
Введение к работе
Актуальность работы.
Актуальность интегрированных решений проблем обработки
разнородной тематической графической информации (ГИ) обусловлена возрастающим потоком значительных объемов данных о дистанционном зондировании Земли (ДЗЗ), поступающих с космических аппаратов (спутников), аэрофотосъемки и других источников, требующих одновременной обработки для решения различных задач. Организация интегрированной инфраструктуры больших объемов пространственно-распределенных данных (ПРД) невозможна без разработки новых эффективных моделей, методов и алгоритмов принятия решений в задачах анализа, хранения и передачи данных, в частности методов адаптивного сжатия.
В настоящее время разработано большое количество универсальных и
специализированных алгоритмов сжатия. Значительный вклад в развитие
методов адаптивного сжатия внесли работы российских ученых А.С.Лебедева,
Н.Н.Красильникова, Ю.М.Штарькова, В.А.Виттиха, Ю.Г.Васина,
С.В.Жерздева, В.В.Александрова, В.В.Сергеева и других, а также зарубежных ученых Дж.О.Лимба (J.O.Limb), У.Претта (W.K.Pratt), Р.Грэхема (R.Graham), М.Кунта (M.Kunt), П.Берта (P.Burt), С.М.Кортмена (C.M.Kortman) и других.
Однако при обработке разнородных тематических данных эффективность адаптивного сжатия существенно отличается для разных типов ГИ. Приходится использовать для сжатия разные программные комплексы, которые значительно отличаются как по алгоритмам, так и по интерфейсам. На изучение и сопровождение каждой программы требуется определенные материальные ресурсы. Это приводит к необходимости создания единого программного комплекса, который включал бы в себя все необходимые средства для эффективного сжатия изображений различных типов, обладая при этом единым интерфейсом для всех выполняемых задач.
В связи с вышеуказанным актуальной задачей является разработка
методов, алгоритмов и программного обеспечения (ПО) адаптивного сжатия на
единой методологической основе большеформатных растровых изображений
широкого спектра, разнородной информации о пространственно-
распределенных объектах, графической и текстовой информации.
Объектом исследования являются модели и методы адаптивного сжатия широкого спектра большеформатных растровых изображений графической и текстовой информации.
Предметом исследования являются графические модели описания и структуры представления контекстных моделей разных порядков, алгоритмы
адаптивного сжатия большеформатных изображений на базе методов контекстного моделирования и статистического кодирования, способы уменьшения емкостной и вычислительной сложности разработанных алгоритмов
Цель исследования – разработка и развитие моделей описания, алгоритмов и интегрированного программного обеспечения для адаптивного сжатия широкого спектра разнообразных растровых изображений на основе методов контекстного моделирования и статистического кодирования.
Для достижения поставленной цели требуется проведение анализа существующих методов и алгоритмов адаптивного сжатия растровых изображений, а также прикладных задач и методов их реализации и решение следующих задач:
-
Разработка и исследование методов и алгоритмов адаптивного сжатия без потерь (lossless) широкого спектра растровых бинарных, полутоновых, индексированных, полноцветных и текстовых изображений.
-
Разработка графических моделей описания и структур представления для хранения и эффективного поиска контекстных моделей разного порядка.
-
Разработка и создание универсального интегрированного ПО, реализующего разработанные алгоритмы, структуры и методы адаптивного сжатия.
-
Экспериментальные исследования разработанных методов и алгоритмов с целью анализа эффективности разработанных методов и алгоритмов адаптивного сжатия большеформатных растровых изображения.
Научная новизна состоит в следующем:
-
Разработан алгоритм сжатия без потерь бинарных растровых изображений с использованием контекстного моделирования и статистического кодирования. Алгоритм отличается введением двумерного контекста определенной формы, а также разработанными методом ухода на контексты меньших порядков (КМеП), модифицированным методом наследования информации (НИ), способами вычисления контекста максимального порядка (КМП) и КмеП, а также высоким коэффициентом сжатия (Ксж).
-
Разработан алгоритм сжатия без потерь индексированных растровых
изображений с использованием контекстного моделирования и статистического
кодирования. Алгоритм отличается введением двумерного контекста из
индексированных пикселей определенной формы, использованием
специальных структур для хранения контекстных моделей (КМ) и ключа КМ с
возможностью адаптации параметров алгоритма под количество реально
использованных цветов, способами вычисления КМП и КмеП, а также высоким коэффициентом сжатия (Ксж).
-
Разработан алгоритм сжатия без потерь полноцветных растровых изображений с использованием контекстного моделирования и статистического кодирования. Алгоритм отличается введением контекста определенной формы с учетом взаимосвязей между пикселями как по горизонтали, так и по вертикали, а также между цветовыми каналами. Алгоритм отличается разработанными методом ухода на КМеП, способами вычисления КМП и КмеП, а также высоким коэффициентом сжатия (Ксж).
-
Разработаны графические модели описания и структуры представления двумерных контекстных моделей (ДКМ) разных порядков, а также способы их формирования, позволяющие учитывать взаимосвязь между отсчетами, включая межканальные корреляционные связи RGB, организовать эффективное хранение, поиск и обработку формируемых ДКМ.
-
Получены результаты экспериментальных исследований разработанных методов и алгоритмов, подтвердивших их эффективность.
Методы исследования. В работе используются методы дискретной математики, теории графов, теории вероятностей и статистического анализа, теории информации, математической логики, теории цифровой обработки сигналов и изображений, математического моделирования.
Практическая ценность. В основу диссертационной работы положены результаты, полученные автором в ходе научно-исследовательских работ, проводимых по плану Госзадания Минобрнауки №2084 в НИИПМК ННГУ и центре информатики и интеллектуальных информационных технологий ИИТММ ННГУ, а также в рамках ОКР «Модернизация» с ООО «Транзас». Работа выполнена при финансовой поддержке РФФИ (Проекты №. 13-07-00521-А, №. 13-07-12211, № 16-07-01214, №11-07-12049 ОФИ-М, №13-07-97036), а также при финансовой поддержке РНФ проект №16-11-00068.
Разработано интегрированное ПО, реализующее разработанные модели, алгоритмы адаптивного сжатия. Особенности ПО: мультиплатформенность, возможность распараллеливания, единый интерфейс, сжатие файла в блочном режиме, единый формат выходного архивного файла для изображений различной цветности. Проведены исследования по оптимизации временной и емкостной сложности алгоритмического обеспечения.
Результаты диссертационной работы внедрены в ЦКП 280 главного
управления океанографии и навигации Министерства обороны РФ в составе
программно-аппаратного комплекса «Векторизация ПГС» при создании
мировой коллекции электронных планшетов гидрографической съемки морского дна, внедрены в центре информатики и интеллектуальных информационных технологий ИИТММ ННГУ им. Н.И. Лобачевского при обработке большеформатных навигационных документов (топографические и морские навигационные карты, поэтажные планы зданий и сооружений) в системе ГИС «Терра», в учебном процессе института информационных технологий, математики и механики ННГУ им. Лобачевского.
Апробация полученных результатов. Результаты диссертационной работы докладывались и обсуждались в рамках следующих конференций: на 8-м Открытом российско-немецком семинаре «Распознавание образов и понимание изображений» (Россия, г. Нижний Новгород, 2011 г.); на 9-м Открытом российско-немецком семинаре «Распознавание образов и понимание изображений» (Германия, г. Кобленц, 2014 г.); на 11 международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (Россия, Самара, 2013); на Международной Конференции и молодежной школе «Информационные технологии и нанотехнологии» (Россия, Самара, 2015); на 26-ой Международной конференции и школе-семинаре по компьютерной графике, обработке изображений и машинному зрению, системам визуализации и виртуального окружения Графикон 2016 (Россия, Нижний Новгород, 2016).
Основные положения, выносимые на защиту:
-
Алгоритм сжатия бинарных растровых изображений с использованием контекстного моделирования и статистического кодирования.
-
Алгоритм сжатия индексированных растровых изображений с использованием контекстного моделирования и статистического кодирования.
-
Алгоритм сжатия полноцветных растровых изображений с использованием контекстного моделирования и статистического кодирования.
-
Графические модели описания и структуры представления двумерных контекстных моделей (ДКМ) разных порядков, а также способы их формирования, позволяющие учитывать взаимосвязь между отсчетами, а также межканальные корреляционные связи RGB, организовать эффективное хранение, поиск и обработку формируемых ДКМ.
5. Результаты экспериментальных исследований разработанных методов.
Публикации. Основные результаты исследований опубликованы в 8
научных работах, 3 из которых опубликованы в изданиях, рекомендованных
ВАК Минобрнауки России. Получено 2 свидетельства о регистрации
электронного ресурса на разработанное программное обеспечение.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы. Общий объем текста диссертации - 99 страниц, включая 23 рисунка и 23 таблицы, библиографический список из 114 наименований, приложение.
Рекурсивный (волновой) алгоритм
Идея алгоритма заключается в сохранении в файл разницы – числа между средними значениями соседних блоков в изображении, которая обычно принимает значения, близкие к 0.
В отличие от JPEG и фрактального алгоритма данный метод не оперирует блоками, например, 8х8 пикселей. За счет того, что коэффициенты сохраняются независимо, отсутствует эффект дробления изображения на «мозаичные» квадраты.
Алгоритм относится к алгоритмам сжатия с потерями и предназначен для сжатия полноцветных 24 битных изображений или изображений в градациях серого без резких переходов цветов (фотографий).
Фрактальная архивация используется для сжатия изображений и основана на том, что изображение представляется в более компактной форме с помощью коэффициентов системы итерируемых функций (Iterated Function System, далее по тексту как IFS). IFS представляет собой набор трехмерных аффинных преобразований, переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (координата х, координата у, яркость). Система интегрируемых функций задает фрактал или самоподобный математический объект. Фактически, фрактальная компрессия – это поиск самоподобных областей в изображении и определение для них параметров аффинных преобразований.
В худшем случае, если не будет применяться оптимизирующий алгоритм, потребуется перебор и сравнение всех возможных фрагментов изображения разного размера. Даже для небольших изображений при учете дискретности получается очень большое число перебираемых вариантов. Причем, даже резкое сужение классов преобразований, например, за счет масштабирования в определенное количество раз, не дает заметного выигрыша во времени. Кроме того, при этом теряется качество изображения. Большинство исследований в области фрактальной компрессии сейчас направлены на уменьшение времени архивации, необходимого для получения качественного изображения. Достоинством алгоритма является высокая степень сжатия [1, 34, 46, 76, 83, 99, 110]. Алгоритм относится к алгоритмам сжатия с потерями и предназначен для сжатия полноцветных 24 битных изображений или изображений в градациях серого без резких переходов цветов (фотографий).
JPEG – один из самых широко используемых алгоритмов сжатия изображений. Практически, он является стандартом «де-факто» для полноцветных изображений. Данный алгоритм при кодировании разбивает изображение на области 8х8, на которых яркость и цвет меняются сравнительно плавно. Данные области раскладываются в двойной ряд по косинусам и в результате, значимыми оказываются только первые коэффициенты. Сжатие в JPEG осуществляется за счет плавности изменения цветов в изображении.
Алгоритм разработан группой экспертов в области фотографии специально для сжатия 24-битных изображений. JPEG – Joint Photographic Expert Group – подразделение в рамках ISO – Международной организации по стандартизации. В целом алгоритм основан на дискретном косинусоидальном преобразовании, применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов. Для получения исходного изображения применяется обратное преобразование.
Данный алгоритм является алгоритмом сжатия с потерями и предназначен для сжатия полноцветных 24 битных изображений или изображений в градациях серого без резких переходов цветов (фотографий). Стандартизован JPEG в 1991 году. Одним из преимуществ данного алгоритма является малая требовательность к вычислительным ресурсам и, как следствие, возможность оперативной работы на маломощных устройствах. Данное свойство дополняется свойством симметричности работы алгоритма, что позволяет использовать данный алгоритм в фотоаппаратах и камерах телефонов.
К недостаткам данного алгоритма можно отнести плохое качество печати при использовании больших коэффициентов сжатия. В некоторых случаях, алгоритм создает «ореол» вокруг резких горизонтальных и вертикальных границ в изображении (эффект Гиббса). Кроме того, при высокой степени сжатия изображение распадается на блоки 8х8 пикселей.
Как стандарт ISO JPEG начинает все шире использоваться при обмене изображениями в компьютерных сетях. На данный момент алгоритм JPEG используется повсеместно и занимает видное место в системах мультимедиа.
Метод и алгоритмы основаны на иерархической интерполяции на базе локальных однородных хорошо приспосабливаемых сглаживающих и восстанавливающих функций с процедурами квантования и статистического кодирования ошибок на каждом уровне иерархии. При этом сжатый массив представляется в виде иерархической структуры – бинарного дерева. Так, для изображений в памяти хранится двумерный массив отсчетов k-ого уровня (исходного изображения, прореженного в 2k раз по каждой из координат) и набор ошибок интерполяции, позволяющих получить массивы отсчетов уровней k-1,k 2,…., прореженные соответственно в 2k-1,2k-2,… раз, вплоть до 0-го уровня – полностью исходного изображения. Алгоритмы обладают высоким коэффициентом сжатия, обладают низкой вычислительной и емкостной сложностью [62, 64, 65, 66, 68, 69-73].
Развитие и поиск структуры представления контекстных моделей в оперативной памяти
Предлагаемый алгоритм отличается способом формирования контекстов порядков, меньших максимального. Подробное описание способа формирования контекста меньшего порядка описано в разделе 3.3.
При использовании КМ нескольких порядков способ оценивания вероятности появления нового значения пикселя в контексте и последующего ухода на КМеП значительно влияет на размер выходного файла. Оценка значения счетчика символа ухода в предлагаемом алгоритме вычисляется следующим образом. Изначально значение счетчика символа ухода равен 2. При каждом новом встречаемом значении пикселя значение счетчика символа ухода уменьшается на единицу. В результате этого, когда после какого-либо контекста уже встретились оба вида значения пикселя, значение счетчика символа ухода равно нулю и не влияет на кодирование, поскольку в этом случае новый вид значения пикселя после данного контекста появиться не может и символ ухода больше не нужен. Если же после какого-либо контекста один вид значения пикселя не встречается, то сначала значения счетчиков уже встреченного значения пикселя и символа ухода будут равны, но при каждом кодировании уже встреченного значения пикселя вероятность символа ухода будет постепенно уменьшаться за счет того, что значение счетчика встреченного значения пикселя будет расти, а значение счетчика символа ухода будет оставаться неизменным. Счетчик символа ухода в контекстной модели нулевого порядка изначально равен нулю и не изменяется, так как в модели данного порядка все счетчики встречаемости оценены ненулевыми значениями с самого начала. Для контекста C(R) значение счетчика символа ухода f(escC(R)) определяется формулой (2). Данный способ оценки значения счетчика символа ухода позволил добиться значительного увеличения Ксж за счет зануления счетчика встречаемости символа ухода после того, как все значения пикселя уже встретились в данном контексте, и увеличить скорость кодирования. По способу оценки данный метод похож на метод оценки вероятности символа ухода С [73], одно из основных отличий в том, что когда оба значения пикселя встретились после данного контекста, значение счетчика становится равно нулю. Также, при программной реализации такой способ оценки позволяет ускорить алгоритм за счет того, что счетчик уменьшается на единицу при каждом новом встреченном виде значения пикселя. Благодаря этому счетчик зануляется автоматически и нет необходимости проводить проверку встретились ли все значения пикселя. f (esc) 2; (С(Д)) = 0 1; f(C(R)) Ф 0, /(0 C(R)) = 0 u /(1 C(R)) = 0 (2) 0; f(C(R)) Ф 0, /(0 C(R)) Ф 0, /(1 C(R)) Ф где f(0C(R)) – значение счетчика встречаемости пикселя со значением 0 в текущей КМ, f(1C(R)) – значение счетчика встречаемости пикселя со значением 1 в текущей КМ, f(C(R)) - общая сумма значений счетчиков встречаемости значений пикселей в текущей КМ, без учета счетчика символа ухода.
Используются контекстные модели 30, 11, 4, 0 порядков.
Отличие предлагаемого способа МПВС основывается на предположении, что если в данной модели встречалось только одно значение пикселя, то используемый коэффициент должен быть выше, чем когда встретились оба значения пикселя. Экспериментально были подобраны следующие значения коэффициента «ca»: 4 – в случае, когда в модели встретилось только одно значение пикселя и 1,375 - в случае, когда встретились оба значения пикселя. Значения коэффициента «са» вычисляется по формуле 3. \4,f(esc) 0 са = (3) [1,375, f(esc) = О Используемый способ exclusion отличается тем, что благодаря содержанию в алфавите всего двух возможных значений пикселя, в выходную последовательность при уходе кодируется только значение символа ухода, после чего кодирование текущего значения пикселя завершается. Этого достаточно для декодера, чтобы восстановить, что раз одно значение пикселя в данной модели уже встречался и при этом был закодирован символ ухода, то текущее значение пикселя есть то, который еще не встречалось в данной модели.
При применении стандартного метода наследовании информации к предметной области черно-белых изображений было замечено, что на более зашумленных изображениях с более случайными данными данный метод давал отрицательный результат, вместо положительного. Новизна предлагаемого метода заключается во введении специального коэффициента Т. Данный коэффициент снижает воздействие метода НИ при обработке изображений с высокой степенью шумов в изображениях.
Пусть, в результате серии уходов мы спустились с КМ(і?) на КМ(R-m), где значение af . пикселя было успешно оценено. Тогда начальное значение f(aJoh \C(R)) в КМ(Д) вычисляется, исходя из формулы 4 f(aj , \C(R-m) f(C(R)) /(а? , I C(R)) = Jo т ... 0,Jo f(C(R - m)) + f(C(R)) - 2 + /(esc C(R)) - f(aJoJo \ C(R -k))+ f{a\ Jo C(j)) v 0 j R где T = (1 - min(/(e C(R - m)) I max(/(e C(R - m))),e є {0,1} Данный метод позволил увеличить Ксж на 2-5% при незначительных потерях в производительности.
В самом простом случае контекст меньшего порядка R N вычисляется полностью заново, формируясь из R взятий значений пикселей из изображения. Но операция взятия значения пикселя из изображения является довольно трудоемкой, поэтому для увеличения быстродействия алгоритма рационально использовать часть информации из КМП для вычисления значений контекстов меньших порядков. Изначально порядок следования пикселей в контексте в предлагаемом алгоритме был задан таким образом, чтобы можно было с помощью одной операции битового сдвига получить контекст любого меньшего порядка. Такой эффект достигался за счет того, что пиксели КМП нумеровались в соответствии с близостью к текущему пикселю. Соответствующее расположение пикселей отражено на рисунке 11. Однако, операция вычисления нового контекста максимального порядка выполняется гораздо чаще, чем операция вычисления контекста меньшего порядка. В связи с этим было решено оптимизировать функцию вычисления нового контекста максимального порядка. Для решения этой задачи порядок следования пикселей контекста был изменен с фиксированного, заданного программистом, на последовательный построчный, от самого левого пикселя контекста, находящегося на одной линии с кодируемым пикселем, до самого правого, находящегося максимально далеко по вертикали от кодируемого пикселя. Такая структура образования контекста позволила вычислять новый контекст за два шага, используя информацию из предыдущего контекста. На первом шаге осуществляется битовый сдвиг значения предыдущего контекста. На втором шаге по одному обновляются значения крайних правых пикселей КМП с номерами 4, 13, 20, 26, 30. В результате, число операций обращения к изображению сократилось с величины всего контекста до величины контекста в высоту. При переходе на новую строку изображения реализовано последовательное вычисление значений только тех пикселей контекста, которые не выходят за границы изображения [57, 60].
Алгоритм сжатия бинарных растровых изображений без потерь
Алгоритм декодирования заключается в следующем. Сначала модель приводится в исходное состояние. Используется три отдельных ключа текущего контекста для каждого из каналов. Используется три независимых леса деревьев КМ для каждого из цветовых каналов. Текущее значение ключей контекста заполняется нулевыми значениями. В контекстных моделях нулевого уровня значения счетчиков каждого возможного значения пикселя приравниваются единице. Считываются размеры закодированного изображения, с помощью которых в памяти компьютера создается пустое изображение для последовательного отображения на нем восстанавливаемых пикселей. Запускается цикл. В цикле совершаются следующие действия:
1. Вычисляются координаты текущего пикселя. Происходит последовательное формирование контекстов Cont1, Cont2, Cont3 максимального порядка для цветовых каналов красного, зеленого и синего цветов Сформированные значения КМП принимаются в качестве текущих контекстов для каждого из цветовых каналов. Далее последовательно осуществляются пункты 2-5 для каждого из значений разниц цветовых компонент каждого из цветовых каналов.
2. Сначала производится проверка, встречался ли уже текущий контекст ранее. Проверка производится путем поиска контекстной модели по значению ключа текущего контекста в дереве контекстных моделей. При этом, как и в случае с кодированием, для контекстов каждого порядка в оперативной памяти хранится отдельное дерево контекстных моделей. Если контекст встретился первый раз, то для него создается новая КМ. При создании новой КМ ее значения счетчиков встречаемости инициализируются нулями, кроме символа ухода. Производится процедура масштабирования счетчика последнего встреченного символа, при которой счетчик встречаемости последнего встреченного значения пикселя умножается на коэффициент ca.
3. Из закодированного файла с помощью арифметического кодера извлекается закодированное значение накопленного счетчика встречаемости и происходит поиск значения пикселя, соответствующего извлеченному значению в текущей КМ. Поиск происходит последовательным перебором всех возможных значений пикселей с прибавлением значения счетчика встречаемости для каждого значения пикселя во временную переменную CurFr. Как только значение CurFr станет равным или большим значения извлеченного арифметическим кодером, перебор прекращается. Значение счетчика встречаемости, на котором остановлен перебор, соответствует значению пикселя, который был закодирован. Если перебраны все значения, но переменная CurFr не стала больше или равна извлеченному значению, тогда делается вывод, что был закодирован символ ухода.
4. Если извлеченному значению соответствует значение разницы цветовой компоненты, то он отмечается на изображении.
5. Если извлеченному значению соответствует символ ухода, то вычисляется контекст меньшего порядка, который делается текущим. Происходит возврат к пункту 2.
6. Модель обновляется в соответствии с декодированными значениями. Процедура обновления соответствует процедуре обновления из пункта 5 общего алгоритма кодирования.
7. Если все пиксели сжимаемого изображения обработаны, то декодер завершает свою работу.
Реализована возможность использовать вместо значения цветовой компоненты разницу между значениями цветовой компоненты текущего и предыдущего пикселей. Также реализована возможность составлять контекст, используя в качестве значений разницу между значениями цветовых компонент текущего и предыдущего пикселей. Проведены эксперименты по сравнению сжатия полноцветных файлов в трех режимах:
1. Без использования взаимосвязи между разными цветовыми каналами. Для контекста канала R используются значения цветовой компоненты только канала R. Для контекста канала G используются значения только из канала G. Для контекста канала B используются значения только из канала B.
2. С частичным использованием взаимосвязи между цветовыми каналами RGB. Для контекста канала R используются значения цветовой компоненты только канала R. Для канала G используются значения из каналов R и G. Для контекста канала B используются значения из каналов R, G и B.
3. С полным использованием взаимосвязи между цветовыми каналами RGB. Для контекстов каналов R, G, B используются значения цветовых компонент каналов R, G, B.
В результате экспериментальных апробаций было установлено, что подход второй подход с использованием разницы между текущим и предыдущим пикселями только в качестве значения пикселя оказался наиболее эффективным. Третий подход увеличил коэффициент сжатия незначительно, при этом значительно увеличив вычислительную нагрузку. Второй подход показал незначительное увеличение времени кодирования при значительном увеличении степени сжатия до 7% на тестовом наборе данных. Показано, что подход с использованием разницы цветовых компонент в качестве значений оказался особенно эффективным при использовании свойства взаимосвязи между цветовыми каналами. Данный эффект объясняется тем, что в случае если значение одной цветовой компоненты при переходе от одного пикселя к другому изменяется незначительно, то скорее всего и значения других цветовых компонент будут тоже изменяться незначительно. Если же идет резкая смена значений одной цветовой компоненты (например, на границе объекта) тогда, у другого цветового канала, скорее всего также будут более большие разницы между значением цветовой компоненты текущего и предыдущего пикселей.
Результаты тестирования алгоритма IPC
Для проверки эффективности алгоритма были проведены эксперименты на наборе тестовых изображений и проведено сравнение с наиболее распространенными универсальными и специализированными алгоритмами сжатия изображений: JpegLS, PNG, 7z, rar, PPMс. Тестовый набор включает в себя 3 полноцветных изображения из набора[40]: artificial.bmp – тестовое полноцветное изображение из набора [40] (размер 3072x2048 пикселей, объем 18 907 136 байт), big_tree.bmp – тестовое полноцветное изображение из набора [40] (размер 6088x4550 пикселей, объем 83 132 416 байт), bridge.bmp – тестовое полноцветное изображение из набора [40] (размер 2749x4049 пикселей, объем 33 423 360 байт), 30057А.bmp – полноцветный сканированный снимок карты (размер 8063x7721 пикселей, объем 186 810 368 байт), 31015Б.bmp – полноцветный сканированный снимок карты (размер 8459x7775 пикселей, объем 197 361 664 байт), 31131В.bmp – полноцветный сканированный снимок карты (размер 8387x7829 пикселей, объем 197 033 984 байт). Результаты экспериментальных апробаций приведены в таблице
Сравнение алгоритма FPC с другими алгоритмами по времени сжатия представлено в таблице 17. На рисунке 22 представлен фрагмент исходного изображения и фрагмент восстановленного после сжатия алгоритмом FPC изображения, что показывает, что сжатие происходит без потерь.
Одним из способов ускорения работы программ является выявление «горячих точек программы» или, другими словами, тех мест в коде программы, на которые тратится наибольшее количество ресурсов компьютера. Благодаря проведенным исследованиям с помощью профайлера, было выявлено, что большую часть процессорного времени и ОП расходуется на функции вычисления нового КМП и поиск КМ в дереве КМ. Данные функции уже были оптимизированы по вычислениям, как это было описано выше. Однако, было замечено, что на работу данных функции оказывает сильное влияние размер КМП. Следовательно, размер КМП влияет не только на степень сжатия, но также и на скорость работы алгоритма и количество потребляемой оперативной памяти. Было сделано предположение, что при уменьшении размера КМП до определенного уровня Ксж уменьшится не существенно, но при этом скорость сжатия значительно увеличится. В виду этого, были проведены эксперименты по выявлению зависимости Ксж, времени сжатия и размера потребляемой оперативной памяти от величины КМП. Результаты данного эксперимента приведены в таблице 18. Как видно из проведенных экспериментов, при уменьшении размера контекста до 15 коэффициент сжатия падает незначительно, при этом наблюдается значительное уменьшение времени, необходимого для сжатия и уменьшение количества потребляемой оперативной памяти. Снижение величины КМП меньше 15 приводит к более значительному уменьшению коэффициента сжатия и менее значительно уменьшает потребляемую ОП и время, затрачиваемое на сжатие. В таблицах 18-20 строки соответствуют номеру сжимаемого файла, а столбцы соответствуют размеру контекста максимального порядка. При этом, снижение величины КМП ниже 20 практически не влияет на уровень потребляемой оперативной памяти.
Для подробного описания выходного файла необходимо ввести структуру SizeBM, хранящую в себе два значения height и width – высоту и ширину прямоугольной области соответственно. Данная структура занимает в памяти 8 байт.
Закодированный файл состоит из двух основных частей – заголовка файла и основной части файла. Заголовок файла содержит описание общих для всех файлов архива параметров, а также размеров и имен изображений и состоит из следующих полей: Количество изображений в файле (kol) – целое, 4 байта.
Массив из kol элементов пар значений Height, Width – высоты и ширины для каждого изображения - 8 байт kol.
Имена всех изображений в архиве, разделенные знаком , где означает окочание имени очередного файла. Имена файлов могут иметь произвольный размер от 1 до 256 байт.
Количество потоков SubImageCount, используемых при сжатии. Также данный параметр означает, количество частей, на которое разделяется изображение. 1 байт.
Массив PositionsOfImages из kol-1 элементов типа int по 4 байта, каждый элемент которого обозначает смещение в файле, по которому начинается сжатое изображение. Для первого изображение по умолчанию используется смещение равное 0, относительно конца заголовка файла.
Массив из kol (SubImage-1) элементов типа int по 4 байта, каждый элемент которого обозначает смещение в файле, по которому начинается сжатый блок изображения. Для первой части изображения по умолчанию используется смещение равное 0, относительно начала изображения.
Следующая часть заголовочного файла есть только при сжатии бинарных изображений в файлах архивов PCTB алгоритма. После основной части заголовка архива идет два массива LeftTopMas и RightBottomMas, содержащих в себе по kol элементов типа SizeBM. Данные массивы используются для хранения координат прямоугольной области изображения, в которой есть пиксели отличные от белого цвета. Такие координаты получается в результате вычисления белых рамок изображений. Основная часть файла состоит из набора в kol штук подряд идущих описаний сжатых изображений, где kol – количество сжатых изображений в архивном файле. Каждое описание сжатого изображения состоит из трех основных частей. ColorTableSize – количество цветов в изображении, размером 4 байта. Данный параметр отсутствует при сжатии полноцветных изображений алгоритмом FPC.