Новые эффективные методы энтропийного кодирования медиаданных

• Автор: Плоткин, Дмитрий Арнольдович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 105 с. : ил.

Содержание
ВВЕДЕНИЕ.

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 Сравнение универсального кодирования с алгоритмами сжатия i и i2.
3.6 Выводы
4 ГЛАВА. КОДИРОВАНИЕ СТАТИЧЕСКИХ ИЗОБРАЖЕНИЙ.
4.1 Обзор сжатия изображений
4.2 Описание i
4.3 Алгоритм для сжатия изображений на основе i и БИП
4.4 Методы улучшения сжатия.
4.4.1 Пути объединения и БИП.
4.4.2 Подбор АС и таблиц.
4.4.3 Построение собственных таблиц.
4.5 Выводы
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


В данном случае речь идет не только и не столько о персональных компьютерах, ноутбуках и серверах, а и о мобильной телефонии, цифровом телевидении и многих других устройствах с различной вычислительной способностью и различными каналами связи, по которым необходимо быстро и надежно передавать большое количество информации. Алгоритмы компрессии должны выполняться на любых платформах от серверов до цифровых фотокамер. Вычислительная техника постоянно совершенствуется, поэтому алгоритмы сжатия данных должны также постоянно улучшаться, используя, как можно эффективнее, возможности современной аппаратуры, такие как многопотоковость, технологии вычислений с малой теплоотдачей и многие другие. Таким образом, задача разработки и исследования новых методов сжатия данных является актуальной научной и прикладной задачей. В основе всех методов сжатия лежит простая идея: если представлять часто используемые элементы короткими кодами, а редко используемые - длинными кодами, то для хранения блока данных требуется меньший объем памяти, чем, если бы все элементы представлялись кодами одинаковой длины. Связь между кодами и вероятностями установлена в классической теореме Шеннона [1] о кодировании источника: элемент si с вероятностью появления p(si) выгоднее всего представлять log p(si) битами. Хаффмана и арифметическое кодирование. Методы сжатия могут строить модель источника адаптивно по мере обработки потока данных или использовать фиксированную модель, созданную на основе априорных представлений о природе типовых данных, требующих сжатия. Процесс моделирования может быть либо явным, либо скрытым. Но сжатие всегда достигается за счет устранения статистической избыточности в представлении информации с использованием модели источника. И одним из примеров класса источников, изучаемых в области компрессии, является информация, содержащаяся в медиаданных. Медиаданными являются изображения, аудиозаписи и видеоинформация. В диссертационной работе особый акцент сделан на изображениях. Результаты, полученные на этом типе медиаданных, могут быть проэкстраполированы и применены для видеоизображений в силу того, что сжатие статических изображений лежит в основе сжатия видеоинформации. Разработанные в диссертационной работе методы могут быть подразделены на методы сжатия без потерь и сжатия с потерями. В обоих случаях показаны результаты, улучшающие аналогичные показатели известных методов компрессии данных. Цель исследования. Целью диссертационной работы является разработка и исследование новых эффективных методов кодирования медиаданных с помощью бинарных интервальных преобразований, анализ и нахождение оптимальных параметров данных методов с точки зрения современных вычислительных систем, а также разработка новых методов и применение результатов их работы при сжатии статических изображений. Методы исследования. В работе использовались программы на языке «С». Алгоритм бинарного интервального преобразования, новый метод универсального кодирования данных, новых метод сжатия статических изображений на основе бинарного интервального преобразования и JPEG Baseline реализовывались на стандарте языка «С». Тексты программ являются кроссплатформенными и легко переносимы на любые платформы, поддерживающие компиляцию языка «С». Эффективность работы алгоритмов и конечная степень сжатия проверялась на стандартных тестовых наборах Calgary Corpus и Waterloo Repertoire. Сравнение проводилось с известными алгоритмами сжатия данных и статических изображений. Промежуточные вычисления, анализ статистических данных и перевод их в известные форматы проводился с использованием скриптового языка Perl. Научная новизна работы. Настоящая работа содержит исследование классических и разработку новых методов сжатия данных. В ней проводится сравнительный анализ и показываются преимущества новых методов компрессии над классическими схемами. Основные результаты, выносимые на защиту. Практическая ценность. JPEG Baseline разработан, исследован и реализован новый эффективный метод сжатия статических изображений, позволяющий получать степень сжатия лучше, чем JPEG Baseline, обладая при этом сопоставимой производительностью. Публикация результатов исследований. A new low complexity entropy coding method”, th International Conference of Computer Graphics and Vision.