автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Новые эффективные методы энтропийного кодирования медиаданных

На правах рукописи

003448В24

Плоткин Дмитрий Арнольдович

НОВЫЕ ЭФФЕКТИВНЫЕ МЕТОДЫ ЭНТРОПИЙНОГО КОДИРОВАНИЯ МЕДИАДАННЫХ

05 13 11 - "Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей"

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва - 2008

1 6 О КТ 2008

003448624

Работа выполнена на кафедре Автоматизации Систем Вычислительных Комплексов на факультете Вычислительной Математики и Кибернетики Московского Государственного Университета им М В Ломоносова

Научный руководитель кандидат физико-математических наук

Браиловский Илья Владимирович

Официальные оппоненты. доктор технических наук, Жданов

Владимир Сергеевич

кандидат технических наук, Логинов Вадим Евгеньевич

Ведущая организация Институт точной механики и вычислительной

техники

Л* м*

Защита состоится г уя _Н)йн на заседании

диссертационного совета Д 409^09 01 при ОАО «Институт электронных управтяющих машин им И С Брука» по адресу 119334, Москва, ул Вавилова 24

С диссертацией можно ознакомиться в библиотеке Института электронных управляющих машин им И С. Брука

Автореферат разослан <У ,»

,008 г

Ученый секретарь диссертационного совета

к т н , профессор

Красовский В Е

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В основе всех методов сжатия лежит простая идея, если представлять часто используемые элементы короткими кодами, а редко используемые - длинными кодами, то для хранения блока данных требуется меньший объем памяти, чем, если бы все элементы представлялись кодами одинаковой длины Связь между кодами и вероятностями установлена в классической теореме Шеннона о кодировании источника элемент s, с вероятностью появления p(s,) выгоднее всего представлять log p(s,) битами Если распределение вероятностей не изменяется со временем, и вероятности появления символов независимы, то средняя длина кодов будет равняться энтропии этого источника H - -^Г p(st ) logp(^) Одними из самых

I

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

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

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

• исследование и определение оптимальных параметров сжатия с помощью бинарных интервальных преобразований, а также дифференциация параметров в зависимости от типа сжимаемых данных,

• разработка новых универсальных эффективных алгоритмов сжатия на основе бинарного интервального преобрзования,

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

• разработка эффективного метода сжатия статических изображений на основе JPEG Baseline и бинарных интервальных преобразований,

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

Методы исследования. В работе использовались программы на языке «С» Алгоритм бинарного интервального преобразования, новый метод универсального кодирования данных, новых метод сжатия статических изображений на основе бинарного интервального преобразования и JPEG Baseline реализовывались на стандарте языка «С» Тексты программ являются кроссплатформенными и легко переносимы на любые платформы, поддерживающие компиляцию языка «С» Эффективность работы алгоритмов и конечная степень сжатия проверялась на стандартных тестовых наборах Calgary Corpus и Waterloo Repertoire Сравнение проводилось с известными алгоритмами сжатия данных и статических изображений Промежуточные вычисления, анализ статистических данных и перевод их в известные форматы проводился с использованием скриптового языка Perl

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

• разработан новый универсальный метод сжатия данных на основе бинарного интервального преобразования с использованием метода стопки книг и преобразования Барроуза-Виллера,

• проведено исследование, в результате которого получены оптимальные параметры метода бинарного интервального преобразования,

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

• проведена разработка, анализ и реализация нового эффективного метода сжатия статических изображений, основанного на алгоритме бинарных интервальных преобразований и JPEG Baseline,

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

Основные результаты, выносимые на защиту. На защиту выносятся следующие основные результаты, полученные автором в процессе проведения исследований

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

2) указаны оптимальные параметры метода бинарных интервальных преобразований для медиаданных,

3) новый эффективный метод сжатия статических изображений с использованием бинарных интервальных преобразований и алгоритма JPEG Baseline,

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

Практическая ценность. Практическая значимость диссертационной работы состоит в следующем:

1) разработан и исследован новый универсальный алгоритм сжатия данных, основанный на бинарных интервальных преобразованиях Найдены

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

2) на основе метода бинарных интревальных преобразований и JPEG Baseline разработан, исследован и реализован новый эффективный метод сжатия статических изображений, позволяющий получать степень сжатия лучше, чем JPEG Baseline, обладая при этом сопоставимой производительностью,

3) результаты диссертационной работы были включены в официальный курс лекций «Алгоритмические основы цифровой обработки сигналов и изображений», который читается в Московском физико-техническом институте ( МФТИ ) на кафедре «Микропроцессорные технологии»

Публикация результатов исследований По теме диссертации опубликованы десять печатных работ

Апробация работы. Результаты диссертационной работы докладывались на 14-й Международной конференции по компьютерной графике Graphicon'04 (МГУ им MB Ломоносова, Москва 2004 год), на 18-й Международной конференции по компьютерной графике Graphicon'08 (МГУ им MB Ломоносова, Москва 2008 год), на 22-ой международной молодежной научной конференции «Гагаринские чтения» (МАТИ, Москва 2006 год), на 9-ом научно-практическом семинаре «Новые информационные технологии в автоматизированных системах» (МИЭМ, Москва 2006 год), а также докладывались и обсуждались на научных и технических семинарах факультета Вычислительной Математики и Кибернетики МГУ им M В Ломоносова

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и списка таблиц и рисунков Диссертация содержит 105 страниц машинописного текста, 40 рисунков, 8 таблиц, список литературы из 56 наименования

СОДЕРЖАНИЕ РАБОТЫ Во введении рассматриваются научная новизна работы, актуальность, приводится содержание диссертационной работы по главам, определены цели и задачи диссертационной работы

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

Метод бинарных интервальных преобразований занимает особое положение среди известных энтропийных методов сжатия данных, таких как алгоритм Хаффмана и арифметическое кодирование, объединяя в себе преимущества обоих методов Разработанный Браиловским И В в 2003 году он обладает хорошими показателями сжатия данных, при этом имеет малую алгоритмическую сложность В диссертационной работе показано, что при использовании оптимальных параметров метода по степени сжатия алгоритм бинарных интервальных преобразований занимает промежуточное положение между кодированием по Хаффману и арифметическим кодированием, показывая результаты сжатия лучше, чем метод Хаффмана, однако, обладая меньшей алгоритмической сложностью, чем арифметическое кодирование

Метод бинарных интервальных преобразований предоставляет большие возможности по варьированию параметров, определяющих степень сжатия информации Главная сложность заключается в том, что теоретически неизвестно, каким образом должны определяться оптимальные параметры В связи с тем, что теоретическая задача поиска оптимальных параметров является NP-полной, необходимо было находить параметры экспериментальным путем с использованием практической реализации Параметрами являются мощность алфавита и порядок следования «обобщенных» букв при кодировании

В диссертационной работе было разработано два варианта реализации метода бинарных интервальных пребразований - многопроходный и однопроходный варианты С многопроходным вариантом можно ознакомится в разделе 12 4 1 диссертационной работы

Однопроходный вариант (подробнее с ним можно ознакомится в разделе 1 2 4 2 диссертационной работы) Шаг 1. Инициализация Происходит инициализация всех структур Шаг 2 Алгоритм работы метода АсЫЬейег

Если метод обрабатывает кодируемую букву, являющуюся текущей в процессе обработки, то выполняются следующие действия

1 в массив интервалов заносится значение интервала равное разнице между текущим значением интервала для данной буквы и предыдущим значением интервала для данной буквы,

2 значение предыдущего интервала заменяется на текущее,

3 Если текущая буква не состоит из одних нулей или одних единиц, то в массив букв заносится значение этой буквы, а счетчик количества интервалов увеличивается на 1

Если кодируемая буква не является текущей в процессе обработки, то при условии, что кодируемая буква меньше в лексикографичеком порядке, чем текущая, то счетчик количества интервалов для текущей буквы инкрементируется на 1

Шаг 3. Проход по всем данным

Для всего входного потока выполняется цикл по всем типам буквы, в котором для каждого типа буквы, вызывается метод АёсИхйег с соответствующими параметрами, отвечающими, за тип текущей буквы и за флаг, является ли кодируемая буква текущей

Шаг 4 Запись в выходной поток

После осуществления полной обработки входного потока на шагах 2 и 3, выполняется запись всей информации в выходной поток отдельно для каждой буквы в соответствии с определенным порядком кодирования «обобщенных» букв При этом в процессе записи в выходной поток значения интервалов кодируются с помощью чисел Голомбо, а «обобщенные» буквы пишутся закодированными в зависимости от мощности алфавита либо с помощью алгоритма Хаффмана, либо их битовое представление Декодирование осуществляется в обратном порядке и

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

Во второй главе рассматриваются коды Райса-Голомбо для кодирования целых чисел, производится анализ и нахождение оптимальных параметров метода бинарных интервальных преобразований, а также сравнительный анализ с алгоритмом Хаффмана и арифметическим кодированием

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

Серией вычислительных экспериментов показано, что мощность алфавита, равная четырем, является оптимальным параметром, поскольку, обладая производительностью, сравнимой с методом Хаффмана, а соответственно, лучше чем у арифметического кодирования, метод бинарных интервальных преобразований показывает результаты аналогичные ему При использовании алфавита такой мощности необходимо было выявить наиболее часто встречаемые буквы, и если таковые имеются, то применить кодирование по Хаффману для сжатия самих «обобщенных» букв Также стоит заметить, что применять кодирование по Хаффману необходимо было для каждого типа «обобщенной» буквы в отдельности, а не для всех сразу, иначе не будет достигнут необходимый эффект сжатия

На рис 1 показано процентное соотношение «обобщенных» букв всех типов в основных видах файлов Видно, что в текстовых файлах чаще встречаются буквы, содержащие одну или две единицы В файлах бинарного формата, а в особенности в файле изображения pic, заметно преобладают нули

100 30 80 70 60 50 40 30 20 10 О

i£L

BL L

Jl L......,

<s£ -р* ¿P .с? # 0-v' .о» л6 ^

,<£> .-<5° .-O^ „15* „•?> .--> »V

Этекс! □ бинарный файл M pic

Рис. Г. Распределение букв в различных типах файлов, по оси X - типы букв, по оси Y - вероятность появления буквы.

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

100 90 80 70 60 50 40 30 20 10 0

2 3 4 5

Втекст □ бинарный файл Mpic

-------------_------

в !Г И 1 1п

! !п_ □ _ L - sQ-.......m________

Рис. 2. Частота появления буквы среди букв одного типа в различных типах файлов, по оси X - количество единиц в буквы, по оси У - вероятность появления буквы.

В результате исследований было показано, что существует заметное преобладание частоты встречаемости некоторых букв над другими Это эмпирически найденное свойство файлов было использовано для улучшения сжатия При таком распределении вероятностей наиболее разумным стало использование метода Хаффмана, который представляет часто встречающиеся символы наименьшим числом бит В данном случае буквы, имеющие большие вероятности, кодировались всего одним битом вместо четырех Данное свойство справедливо для всех мощностей алфавита больше 2-х При алфавита мощностью два кодирование любой буквы занимает всего один бит - буква «01» кодируется «0», а «10» - «1» Остальные буквы кодировать не нужно, в связи с особенностью алгоритма бинарных интервальных преобразований

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

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

• использование кодирования по Хаффману (вместо обычной записи буквы) улучшает показатели сжатия,

• файлы цифровой природы необходимо кодировать таким порядком букв, в котором нули кодируются последними,

• текстовые файлы необходимо кодировать таким порядком букв, в котором нули и единицы кодируются первыми

Аналогичные исследования проводились для алфавитов мощности 2, 8, 16 и 24. Порядок тестирования на наборе Calgary Corpus остался таким же, как при анализе алфавита мощности 4. Для каждой мощности алфавита проводилось большие объемы исследовательской работы, анализировались процентные соотношения частот появления различных букв для различных типов файлов, а также проводились замеры производительности работы нового алгоритма с целью дальнейшего сравнения с известными методами сжатия данных.

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

^dsl * о

Определение. Скоростью кодирования называется отношение , °,

src

где LdSI- размер сжатого файла, a Lsrc - размер исходного файла.

2

geo

objl

obj2

paperl рарег2

pic

3 Бинарное интервальное преобразование □ Кодирование по Хаффману ■ Арифметическое кодирование

Рис.3. Сравнение степени сжатия бинарного интервального преобразования, кодирования по Хаффману и арифметическое кодирование.

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

geo objl obj2 paperl paper2 pic

Ш Бинарное интервальное преобразование □ Кодирование по Хаффману ■ Арифметическое кодирование

Рис.4. Сравнение производительности (в процентах) бинарного интервального преобразования, кодирования по Хаффману и арифметическое кодирование.

Исходя из результатов сравнения, можно сделать вывод - метод бинарных интервальных преобразований показал очень хорошие результаты сжатия для медиаданных, в частности изображении, при различных мощностях алфавита (подробнее можно ознакомиться в главе 2.3 диссертационной работы). На различных типах файлов достигается скорость кодирования, близкая к результатам лучших известных на сегодня методов сжатия информации. Средняя скорость кодирования БИП 4.43, на арифметическом кодировании - 4.3В, на кодировании по Хаффману - 4.55. Алгоритм БИП по скорости кодирования расположился между арифметическим кодированием и кодированием по Хаффману.

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

В третьей главе предложен новый универсальный метод кодирования данных, основанный на методе бинарных интервальных преобразований, использующий дополнительные средства подготовки данных для статического кодирования Рассматриваются методы стопки книг и преобразование Барроуза-Виллера, а также проводится сравнительный анализ нового универсального кодирования с алгоритмами zip и bzip2

Существует ряд стандартных приемов, позволяющих улучшить показатели алгоритмов сжатия данных Такими способами являются метод «стопки книг» или, иначе, Move То Front (MTF) и преобразование Барроуза-Виллера Преобразование Барроуза-Виллера не сжимает данные, иногда даже происходит некоторое их увеличение, но эффект при последующем сжатии энтропийным кодировщиком оказывается сущуственным

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

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

Без методов (и нтервалы/буквы) Метод стопки книг Преобразование Барроуза-Виллера MTF + BWT

Текст 51%/48% 59% / 40% 56% / 43% 78%/21%

Бинарный файл 62%/37% 62% / 37% 64%/35% 75% / 24%

Pic 87% /' 12% 86% /' i3% 92% / 7% 88% /11%

Таблица 1. Процентное содержание данных в закодированном файле при применении МТИ и Вит.

Таким образом, применение описанных выше методов совместно с бинарными интервальными преобразованиями позволило улучшить показатели сжатия в несколько раз. В диссертационной работе был проведен сравнительный анализ универсального метода сжатия данных и с алгоритмами zip и bzip2. Результаты представлены на рис. 5.

5---------------------—-----------

4--

BBWT+MTF+БИП О ZIP ItttipZ

Рис. 5. Сравнение универсального кодирования с алгоритмами zip и bzip2

Средняя скорость универсального кодирования с использованием бинарного интервального преобразования 2.14, zip - 2.61, на bzip2 - 2.16. Таким образом,

универсальный метод показал результаты сжатия лучше, чем алгоритмы zip и bzip2 при сравнимой или лучшей производительности

В главе четыре представлен новый эффективный метод сжатия статических изображений, основанный на бинарном интервальном преобразовании и JPEG Baseline, показаны разработанные методы улучшения сжатия нового алгоритма, проведены сравнительные анализы нового метода с JPEG Baseline и с другими методами, построенными по аналогичной схеме Сравнение проводилось по степени сжатия, а также производительности алгоритмов

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

Рис 6 Схема работы JPEG baseline

На первых шагах работы алгоритма JPEG исходное изображение уже разбито на макроблоки размером 8x8 пикселей (рис б ) Данные, находящиеся в этих матрицах после Дискретного косинусного преобразования и квантования, считывались «зигзаг» сканированием и направлялись на вход энтропийного кодека Если применять бинарное интервальное преобразование вместо кодирования переменной длины, то положительный эффект от такой замены заметен только на маленьком количестве файлов Поэтому для улучшения характеристик сжатия нового метода был предложен новый способ формирования выходного потока (рис 7) После считывания данных из матрицы, они делились на две последовательности по принципу ноль/не ноль В первой последовательности единичный бит ставился вместо ненулевого числа, а нулевой бит - вместо нуля Во вторую же последовательность записывались все ненулевые числа Первая

последовательность отправлялась на вход энкодера программы, а вторая кодирвалась с помощью таблиц кодов переменной длины

Рис 7. Схема работы JPEG baseline + BIT

Например, из матрицы было считано «12, 0, 3, 4, 0, 0, 0, 0, 5, 0, 8, 0, 0, 1, О» Тогда сформируется две последовательности следующего вида

• Первая «101100001010010» - итого 15 бит

• Вторая. «12, 3,4, 5, 8,1»-6 чисел

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

Следующим шагом в совершенствовании нового алгоритма сжатия статических изображений стал подбор таблиц АС и ОС в зависимости от информации, обрабатываемой кодером (рис 7) Таблицы АС и ЭС стали использоваться для коэффициентов АС и БС соответственно Помимо этого был предложен новый способ получения собственных таблиц для коэффициентов АС и ОС Вся область значений была разбита на 12 интервалов (от -2048 до 2048), для которых считались частоты появления Значения элементов макроблоков не могут быть по модулю больше 2048 Это связано с особенностями дискретного

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

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

Рис. 8. Превосходство сжатия (%) для JPEG_BIT над JPEG Baseline

JPEG-JPEG_BIT JPEG

В результате проведенных исследований на тестовом наборе изображений Waterloo Repertoire были показаны результаты сжатия, превосходящие JPEG Baseline до 15%. При этом производительность нового алгоритма сжатия изображений сопоставима с производительностью стандартного JPEG Baseline. На рис. 8 и 9 показаны сравнения нового алгоритма сжатия данных, основанного на бинарных интервальных преобразованиях, с JPEG Baseline.

zelda washsat peppers mountain mandrill library lena gc'dhill frog france boat barb

■ JPEG BIT OJPEG

50

100

150

200

250

Рис. 9. Сравнение производительности (мс) JPEG_BIT над JPEG Baseline

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ В результате выполнения диссертационной работы получены следующие основные результаты:

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

0303030338061111

состоящих только из нулей, для текстовых - буквы, состоящие только из единиц или только из нулей, должны кодироваться первыми

2) Получен универсальный метод с использованием метода стопки книг и бинарного интервального преобразования Показано, что его использование позволяет улучшить показатели сжатия до скорости кодирования, равной 2 8

3) Предложен метод и разработана программная реализация для него -композиция метода "стопки книг", преобразования Барроуза-Виллера и метода бинарного интервального преобразования Показано, что в зависимости от параметра N длины "обобщенной" буквы индекс скорости кодирования бинарного интервального преобразования может быть от 3,8 бит при N=2 до 2 14 бит при N=24 на стандартном тестовом наборе Calgary Corpus

4) Проведено сравнение метода Бинарных интервальных преобразований с арифметическим кодированием и кодированием по Хаффману Средняя скорость кодирования БИП 4 43, на арифметическом кодировании - 4 38, на кодировании по Хаффману - 4 55 Алгоритм БИП по скорости сжатия расположился между арифметическим кодированием и кодированием по Хаффману

5) Проведено сравнение универсального метода кодирования, являющегося композицией преобразования Барроуза-Виллера, метода стопки книг и метода Бинарных интервальных преобразований, с zip и bzip2 Средняя скорость универсального кодирования 2 14, zip - 2 61, на bzip2 - 2 16 Универсальный метод показал результаты сжатия лучше, чем алгоритмы zip и bzip2

6) Разработан и исследован новый эффективный алгоритм сжатия статических изображений, основанный на бинарных интервальных преобразованиях и JPEG Baseline Разработаны схемы объединения данных алгоритмов в единый модуль, позволяющие достичь максимально возможной степени сжатия изображения

7) Разработаны решения, позволяющие увеличить степень сжатия нового алгоритма Проведен сравнительный анализ разработанного алгоритма

сжатия с известными алгоритмами сжатия, исследованы и проанализированы возможности и степень влияния каждого решения в отдельности

8) Разработана программная реализация нового эффективного метода сжатия статических изображений и проведена апробация реализованного алгоритма Для тестирования использовался тестовый набор изображений Waterloo Repertoire По входящим в этот набор изображениям новый метод сжатия статических изображений превзошел JPEG Baseline на 15%, сохраняя при этом производительность на уровне оригинального алгоритма компрессии

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Brailovsky I, Kravtsunov Е, Plotkm D A new low complexity entropy coding method //14th International Conference of Computer Graphics and Vision Moscow State University, 2004

2 Brailovsky I, Kravtsunov E , Plotkm D "Modified JPEG algorithm with Binary Interval Transform coding with improved compression ratio", 18th International Conference of Computer Graphics and Vision Moscow State University, 2008,

3 Плоткин ДА «Оптимизация параметров в методе бинарных интервальных преобразований», Информационные технологии, Москва 2006, вып II. -С 66-71,

4 Плоткин Д А «Новый метод сжатия изображений, построенный на основе JPEG Baseline и метода бинарных интервальных преобразований» Информационные технологии, Москва 2008, вып 5 - С 34-37,

5 Плоткин ДА «Исследование оптимальных параметров и программная реализация метода бинарных интервальных преобразований», 3-я Международная конференция по информационным и телекоммуникационным технологиям в интеллектуальных системах, Мальйорка, Испания, 2005,

6 Плоткин Д А «Эффективное сжатие данных с помощью бинарного интервального кодирования», сборник тезисов лучших дипломных работ 2005 года, Москва, МГУ им М В Ломоносова 2005,

7 Плоткин ДА «Оптимальные параметры метода бинарных интервальных преобразований и новый универсальный метод сжатия данных», сборник

научных трудов «Информационные, сетевые и телекоммуникационные технологии», Москва 2005 - С 272-275,

8 Плоткин ДА «Поиск оптимальных значений для параметров в методе бинарного интервального преобразования», 22-ая международная молодежноая научная конференция «Гагаринские чтения», МАТИ, Москва 2006,

9 Plotkin D A «Researches of compression algorithm for static images based on Binary Interval Transformation method», 5-th international conference "Information and Telecommunication Technologies in Intelligent Systems", Mallorca, Spain 2007,

10 Плоткин Д А «Развитие метода бинарных интервальных преобразований при сжатии статических изображений», материалы девятого научно-практического семинара «Новые информационнные технологии в автоматизированных системах», Москва 2006 - С 61-67

51

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01 12 99 г Подписано к печати Об 10 2008 г Формат 60x90 1/16 Услпечл 1,25 Тираж 100 экз Заказ 546 Тел 939-3890 Тел/Факс 939-3891 119992, ГСГ1-2, Москва, Ленинские горы, МГУ им MB Ломоносова, 2-й учебный корпус, 627 к

ВВЕДЕНИЕ.

1 ГЛАВА. БИНАРНОЕ ИНТЕРВАЛЬНОЕ ПРЕОБРАЗОВАНИЕ.

1.1 Определения.

1.2 Основные подходы к кодированию.

1.2.1 Кодирование длин серий.

1.2.2 Кодирование по Хаффману.

1.2.3 Арифметическое кодирование.

1.2.4 Бинарное интервальное преобразование.

1.2.4.1 Многопроходный вариант реализации.

1.2.4.2 Однопроходный вариант реализации.

1.3 Выводы.

2 ГЛАВА. АДАПТИВНОЕ ИНТЕРВАЛЬНОЕ ПРЕОБРАЗОВАНИЕ.

2.1 Коды Райса-Голомбо.

2.2 Оптимальный порядок букв при кодировании БИП для различных мощностей алфавита.

2.3 Сравнение БИП с кодированием по Хаффману и арифметическим кодированием.

2.4 Выводы.

3 ГЛАВА. УНИВЕРСАЛЬНОЕ КОДИРОВАНИЕ С ИСПОЛЬЗОВАНИЕМ ПРЕОБРАЗОВАНИЯ БАРРОУЗА-ВИЛЛЕРА И МЕТОДА СТОПКИ КНИГ.

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

3.2 Метод стопки книг.

3.3 Преобразоние Барроуза-Виллера.

3.4 Универсальное кодирование.

3.4.1 Универсальное кодирование с использованием Метода Стопки Книг

3.4.2 Универсальное кодирование с использованием преобразования Барроуза-Виллера.

3.4.3 Универсальное кодирование с использованием преобразования Барроуза-Виллера и метода стопки книг.

3.5 Сравнение универсального кодирования с алгоритмами сжатия zip и bzip2.

3.6 Выводы.

4 ГЛАВА. КОДИРОВАНИЕ СТАТИЧЕСКИХ ИЗОБРАЖЕНИЙ.

4.1 Обзор сжатия изображений.

4.2 Описание JPEG Baseline.

4.3 Алгоритм для сжатия изображений на основе JPEG Baseline и БИП.

4.4 Методы улучшения сжатия.

4.4.1 Пути объединения JPEG и БИП.

4.4.2 Подбор АС и DC таблиц.

4.4.3 Построение собственных таблиц.

4.5 Выводы.

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

В основе всех методов сжатия лежит простая идея: если представлять часто используемые элементы короткими кодами, а редко используемые - длинными кодами, то для хранения блока данных требуется меньший объем памяти, чем, если бы все элементы представлялись кодами одинаковой длины. Связь между кодами и вероятностями установлена в классической теореме Шеннона [1] о кодировании источника: элемент si с вероятностью появления p(si) выгоднее всего представлять log p(si) битами. Если распределение вероятностей не изменяется со временем, и вероятности появления символов независимы, то средняя длина кодов будет вычисляться, как

Я = -]>>(*,). logpfo) энтропия источника. Методами энтропийного кодирования являются канонический алгоритм Хаффмана и арифметическое кодирование.

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

Цель исследования.

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

• исследование и определение оптимальных параметров сжатия с помощью бинарных интервальных преобразований, а также дифференциация параметров в зависимости от типа сжимаемых данных;

• разработка новых универсальных эффективных алгоритмов сжатия на основе бинарного интервального преобразования;

• проведение сравнительного анализа бинарного интервального преобразования, а также универсального алгоритма сжатия, построенного на его основе и известных алгоритмов сжатия данных;

• разработка эффективного метода сжатия статических изображений на основе JPEG Baseline и бинарных интервальных преобразований;

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

Методы исследования.

В работе использовались программы на языке «С». Алгоритм бинарного интервального преобразования, новый метод универсального кодирования данных, новых метод сжатия статических изображений на основе бинарного интервального преобразования и JPEG Baseline реализовывались на стандарте языка «С». Тексты программ являются кроссплатформенными и легко переносимы на любые платформы, поддерживающие компиляцию языка «С». Эффективность работы алгоритмов и конечная степень сжатия проверялась на стандартных тестовых наборах Calgary Corpus и Waterloo Repertoire. Сравнение проводилось с известными алгоритмами сжатия данных и статических изображений. Промежуточные вычисления, анализ статистических данных и перевод их в известные форматы проводился с использованием скриптового языка Perl.

Научная новизна работы.

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

Таким образом, научная новизна в диссертационной работе состоит в следующем:

• разработан новый универсальный метод сжатия данных на основе бинарного интервального преобразования с использованием метода стопки книг и преобразования Барроуза-Виллера;

• проведено исследование, в результате которого получены оптимальные параметры метода бинарного интервального преобразования;

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

• проведена разработка, анализ и реализация нового эффективного метода сжатия статических изображений, основанного на алгоритме бинарных интервальных преобразований и JPEG Baseline;

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

Основные результаты, выносимые на защиту.

На защиту выносятся следующие основные результаты, полученные автором в процессе проведения исследований:

1) нахождение оптимальных параметров метода бинарных интервальных преобразований;

2) новый универсальный метод кодирования данных, в основе которого лежит бинарное интервальное преобразование;

3) новый эффективный метод сжатия статических изображений с использованием бинарных интервальных преобразований и алгоритма JPEG Baseline;

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

Практическая ценность.

В процессе проведения исследований автором получены следующие практические результаты:

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

2) на основе метода бинарных интервальных преобразований и JPEG Baseline разработан, исследован и реализован новый эффективный метод сжатия статических изображений, позволяющий получать степень сжатия лучше, чем JPEG Baseline, обладая при этом сопоставимой производительностью.

Публикация результатов исследований.

По теме диссертации опубликованы десять печатных работ:

• тезисы доклада "A new low complexity entropy coding method", 14th International Conference of Computer Graphics and Vision. Moscow State University, 2004; тезисы доклада "Modified JPEG algorithm with Binary Interval Transform coding with improved compression ratio", 18th International Conference of Computer Graphics and Vision. Moscow State University, 2008; статья «Оптимизация параметров в методе бинарных интервальных преобразований» (Информационные технологии, Москва 2006, вып. 11. -С.66-71); статья «Новый метод сжатия изображений, построенный на основе JPEG Baseline и метода бинарных интервальных преобразований» (Информационные технологии, Москва 2008, вып. 5. - С.34-37); тезисы доклада «Исследование оптимальных параметров и программная реализация метода бинарных интервальных преобразований», 3-я Международная конференция по информационным и телекоммуникационным технологиям в интеллектуальных системах, Мальйорка, Испания, 2005; тезисы доклада «Эффективное сжатие данных с помощью бинарного интервального кодирования», сборник тезисов лучших дипломных работ 2005 года, Москва, МГУ им. М.В. Ломоносова 2005; статья «Оптимальные параметры метода бинарных интервальных преобразований и новый универсальный метод сжатия данных» (сборник научных трудов «Информационные, сетевые и телекоммуникационные технологии», Москва 2005 - С.272-275); тезисы доклада «Поиск оптимальных значений для параметров в методе бинарного интервального преобразования», 22-ая международная молодежная научная конференция «Гагаринские чтения», МАТИ, Москва 2006; тезисы доклада «Researches of compression algorithm for static images based on Binary Interval Transformation method», 5-th international conference "Information and Telecommunication Technologies in Intelligent Systems", Mallorca, Spain 2007;

• статья «Развитие метода бинарных интервальных преобразований при сжатии статических изображений» (материалы девятого научно-практического семинара «Новые информационные технологии в автоматизированных системах», Москва 2006 - С.61-67).

Апробация.

Результаты работы докладывались на 14-й Международной конференции по компьютерной графике Graphicon'04 (МГУ им. М.В. Ломоносова, Москва 2004 год), на 18-й Международной конференции по компьютерной графике Graphicon'08 (МГУ им. М.В. Ломоносова, Москва 2008 год), на 22-ой международной молодежной научной конференции «Гагаринские чтения» (МАТИ, Москва 2006 год), на 9-ом научно-практическом семинаре «Новые информационные технологии в автоматизированных системах» (МИЭМ, Москва 2006 год), а также докладывались и обсуждались на научных и технических семинарах факультета Вычислительной Математики и Кибернетики МГУ им. М.В. Ломоносова.

Краткое содержание работы.

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

В разделе 1.1 даются определения, а также сведения из теории кодирования, необходимые для детального рассмотрения теоретических основ бинарного интервального преобразования.

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

В разделе 1.3 делаются выводы, кратко повторяющие главные результаты, полученные в главе 1.

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

В разделе 2.1 вводятся необходимые сведения о методах представления целых чисел с минимальной избыточностью - коды Голомбо. Рассматриваются адаптивные коды Голомбо, а также преимущества алгоритмов, использующие их, по сравнению с обычными кодами Голомбо.

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

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

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

В главе 3 вводятся определения метода стопки книг и преобразования Барроуза-Виллера. Проводится анализ необходимости применения дополнительных методов подготовки данных перед использованием энтропийного кодера, а также вводится новый универсальный метод кодирования и производится его сравнение с алгоритмами zip и bzip2.

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

Раздел 3.2 посвящен описанию метода стопки книг.

Раздел 3.4 посвящен описанию преобразованию Барроуза-Виллера.

Раздел 3.4 содержит описание универсального кодирования с применением метода стопки книг, преобразования Барроуза-Виллера, а также их совместного использования. Проводится анализ и делаются выводы об оптимальных параметрах, которые необходимо использовать для получения наилучших характеристик алгоритма. Делается вывод о возможности применения данных методов совместно с Бинарными интервальными преобразованиями.

В разделе 3.5 производится сравнение универсального кодирования, ' основанного на методе бинарных интервальных преобразований, методе стопки книг и преобразовании Барроуза-Виллера с известными алгоритмами сжатия с zip и bzip2.

В разделе 3.6 делаются выводы об основных результатах, описанных в главе 3.

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

Раздел 4.1 посвящен требованиям, предъявляемым к методам сжатия статических изображений, рассматривается кодировщик Q-кодер, а также основанный на нем метод сжатия изображений JBIG. Производится сравнение JBIG и метода сжатия изображений на основе бинарных интервальных преобразований.

В разделе 4.2 подробно рассматривается и анализируется алгоритм JPEG Baseline, который впоследствии будет использоваться в новом методе сжатия статических изображений.

Раздел 4.3 посвящен описанию разработанного в рамках диссертационной работы нового метода сжатия статических изображений, основанного на алгоритме бинарных интервальных преобразований и методе JPEG Baseline

Раздел 4.4 полностью посвящен различным способам улучшения сжатия нового метода кодирования. Рассмотрены возможные пути объединения JPEG Baseline и метода бинарных интервальных преобразований. Проводится анализ использования различных таблиц для кодирования данных, а также сравнительный анализ полученных результатов при использовании различных средств улучшения сжатия. Рассматривается способ построения собственных таблиц коэффициентов и анализируется производительность нового метода сжатия статических изображений в сравнении с JPEG Baseline.

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

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

1.3 Выводы.

1) Проведен анализ энтропийных алгоритмов сжатия данных -кодирования по Хаффману, арифметического кодирования и бинарного интервального преобразования, определены преимущества и недостатки каждого из алгоритмов, на основе теоретического исследования.

2) Предложены два различных метода реализации алгоритма бинарных интервальных преобразований - многопроходный и однопроходный варианты. Рассмотрены достоинства каждого из вариантов.

2 ГЛАВА. АДАПТИВНОЕ ИНТЕРВАЛЬНОЕ ПРЕОБРАЗОВАНИЕ

2.1 Коды Райса-Голомбо

Коды Райса-Голомбо являются префиксными кодами, позволяющими представлять целые числа минимальным количеством бит [18, 19]. Таким образом, использование кодов Райса-Голомбо в битовом потоке данных является оптимальным решением проблемы представления целого числа, минимально возможным количеством бит.

Предположим, что мы хотим написать код для целого 0, пусть к > 1 - тоже целое число, называемое числом Голомбо. Оно будет использоваться, как параметр для построения этого кода. Рассмотрим два числа ni=[n/k] - результат целочисленного деления п на к, и

Пг= n mod к - остаток от деления п на к. Тогда кодом Голомбо называется запись, состоящая из трех частей:

1. запишем подряд ni единиц, т.е. ni в унарной системе счисления

2. справа от единиц запишем один разделительный ноль

3. справа от нуля запишем пг в обычной бинарной системе счисления, используя для этого [log2 к J двоичных разрядов, если п2 < 2'-Iog2*+I-' - к и [log2 £j+1 в противном случае.

Например, если п = 5, к = 2, то гн = [5/2] = 2 и п2 = [5 mod 2] = 2, и тогда кодом Голомбо будет запись 1101

Выше был рассмотрен общий случай общих кодов Голомбо, однако, в диссертационной работе будет использоваться частный случай данных кодов. Особенностью данного частного случая будет использование числа К равного степени двойки. Преимущество данной версии кодов Голомбо заключается в том, что используется в качестве основного значения степень двойки, что является наилучшим решением с точки зрения вычислительной техники при выполнении операций умножения и деления. Рассмотрим также адаптивную версию кодов Райса-Голомбо, которая необходима при использовании большого количества неизвестных данных, заранее неизвестного диапазона. Предположим, у нас существует последовательность чисел, которую необходимо закодировать с помощью кодов Голомбо [19, 20], при этом значения из этой последовательности могут принимать различные значения. Тогда алгоритм кодирования последовательности будет следующим:

Шаг 1. Инициализация.

На данном шаге вычисляется число Голомбо с заранее определенными параметрами, а также осуществляется кодирование первого значения из последовательности с использованием полчученного числа Голомбо.

Шаг 2. Модификация числа Голомбо.

На этом шаге нам необходимо произвести вычисление и адаптацию нового числа Голомбо для кодирования следующего значения из последовательности чисел. Если предыдущее закодированное значение меньше 2К"1 , то декрементируем значение числа Голомбо К на 1, иначе сравниваем закодированное предыдущее значение с 2К+1. Если значение получается больше, то инкрементируем число Голомбо К на 1. Если оба описанных выше условия не выполняются, то число Голомбо не меняется. Шаг 3. Кодирование значения.

Берем следующее значение из последовательности и кодируем его с использованием числа Голомбо, полученного на шаге 2. Если последовательность не закончилась, то переходим на шаг 2.

2.2 Оптимальный порядок букв при кодировании БИП для различных мощностей алфавита (N=2, 4, 8, 16)

Интервальное бинарное кодирование предоставляет большие возможности по варьированию параметров, определяющих степень сжатия информации [21]. Главная сложность заключается в том, что теоретически неизвестно, каким образом должны подбираться параметры. Эта задача является очень трудной, поэтому, для определения оптимальных параметров необходима практическая реализация. Параметрами являются мощность алфавита и порядок следования «обобщенных» букв при кодировании. Если мощность алфавита N, то необходимо перебрать N! различных порядков следования букв. В этом заключалась главная сложность.

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

Тестирование проводилось на стандартном наборе Calgary Corpus [22]. Он содержит 18 файлов различной структуры, позволяющие в полной мере протестировать программу сжатия данных. При общем анализе и исследовании параметров стоит отдельно остановиться на файлах.

Имя файла Содержимое Размер (байт)

1. Book2 Книга. Текст без форматирования. 610856

2. Geo Геофизические данные (двоичный файл) 1024001. News Новости. 3771091. Obj1 Объектный файл 21504

3. Obj2 Объектный файл 246814

4. Paperl Технический документ 53161

5. Paper2 Технический документ 82199

6. РарегЗ Технический документ 46526

7. Paper4 Технический документ 13286

8. Paper5 Технический документ 11954

9. Рарегб Технический документ 38105

10. Pic Черно-белая факсимильная картинка 513216

11. Progc Код программы на С 39611

12. Progl Код программы на Lisp 71646

13. Progp Код программы на Pascal 49379

14. Trans transcript of terminal session 93695