Новые эффективные методы энтропийного кодирования медиаданных тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Плоткин, Дмитрий Арнольдович

• Плоткин, Дмитрий Арнольдович
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Плоткин, Дмитрий Арнольдович

ВВЕДЕНИЕ.

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 файлов различной структуры, позволяющие в полной мере протестировать программу сжатия данных. При общем анализе и исследовании параметров стоит отдельно остановиться на файлах.

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

Список литературы диссертационного исследования кандидат технических наук Плоткин, Дмитрий Арнольдович, 2008 год

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