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

• Автор: Браиловский, Илья Владимирович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 102 с. : ил

СОДЕРЖАНИЕ.
ВВЕДЕНИЕ.

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

1.1. Предварительные определения и сведения.

1.2. Частичные интервальные преобразования.

1.3. Полные интервальные преобразования.

1.4. Оптимальные интервальные преобразования.

1.5. Выводы.

ГЛАВА 2. ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ ОБОБЩЕННОГО

ИНТЕРВАЛЬНОГО КОДИРОВАНИЯ.

2.1. Кодирование с помощью обобщенных интервальных преобразований и кодов Голомба

2.2. Параллельные алгоритмы для кодирования с помощью обобщенных интервальных преобразований в модели .
2.2.1. Параллельный алгоритм для кодирования с помощью частичного интервального преобразования и кодов Голомба.
2.2.2. Итеративный параллельный алгоритм для кодирования с помощью полного интервального преобразования и кодов
Г оломба.
2.2.3. Однопроходный параллельный алгоритм для кодирования с помощью полного интервального преобразования и кодов
Голомба.
2.3. Параллельные алгоритмы для кодирования с помощью обобщенных
интервальных преобразований в моделях, близких к реальным
встраиваемым системам.
2.3.1. Разделяющее интервальное преобразование.
2.3.2. Кодирование с помощью интервальных преобразований для встраиваемых систем.
2.4. Выводы.
ГЛАВА 3. КОДИРОВАНИЕ ИСТОЧНИКА С НЕИЗВЕСТНОЙ
СТАТИСТИКОЙ С ПОМОЩЬЮ ОБОБЩЕННЫХ ИНТЕРВАЛЬНЫХ ПРЕОБРАЗОВАНИЙ.
3.1. Флаговое интервальное преобразование.
3.1.1. Побуквенные интервальные преобразования.
3.1.2. Флаговое кодирование целых чисел.
3.2. Оценка длины кода флагового интервального преобразования.
3.3. Тестирование флагового интервальною преобразования на реальных данных.
3.4. Выводы.
ГЛАВА 4. ЭФФЕКТИВНОЕ СЖАТИЕ ИЗОБРАЖЕНИЙ С
ИСПОЛЬЗОВАНИЕМ ОБОБЩЕННЫХ ИНТЕРВАЛЬНЫХ ПРЕОБРАЗОВАНИЙ.
4.1. Эффективный алгоритм сжатия изображений без потерь качества I.
4.2. Модификация алгоритма 1.
4.3. Анализ алгоритма Г.
4.3. Результаты работы I.
4.4. Выводы.
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Если есть последовательность из “0” и “1”, причем “(Г встречается чаше чем “1”, то можно кодировать длины интервалов между последовательными вхождениями “I”. Иначе говоря, можно кодировать длины серий из последовательно стоящих “0”, поэтому метод получил название кодирования дтин серий. Свою популярность этот метод заслужил, во-первых, благодаря своей алгоритмической простоте, и, во-вторых, благодаря малой избыточности в случае, когда вероятность “0” много больше вероятности “1". Однако, у кодирования дтин серий есть и определенные недостатки, например, одним из недостатков этого метода, отмеченный еще К. Шенноном, является большая избыточность, когда вероятности "0" и “I” близки. Другим принципиальным недостатком метода кодирования дтин серий является то, что этот метод не определен дтя алфавитов мощности большей чем 2. Свое развитие метод кодирования дтин серий получил в большом количестве теоретических и экспериментальных работ -7,,,,,,,-,], патентов и международных стандартов [,,,]. Особо следует отметить работы С. Голомба [], Р. Галлагера и Д. Ван Ворхиса [], которые предложили и обосновали эффективный метод кодирования дтин серий. Адаптивное кодирование с помощью кодов Голомба рассматривались в работах Г. Лангдона []. Более общий случай с мультисимвольными алфавитами интервальных преобразований изучал П. Елиас []. В течение -гг. Так, в работе 3. Арнавуга и С. Магливераса [] строится новый класс интервальных преобразований, названный авторами “inversion frequencies”, для обработки данных перед арифметическим кодированием для универсального сжимающего алгоритма Барроуза -Веллера []. Этот же класс интервальных преобразований был независимо предложен А. Кадачем ] и автором диссертации [3J. Во всех вышеперечисленных работах по новому классу интервальных преобразований излагаются интересные и имеющие практическую значимость зкепер и ментальные результаты по применению этого метода, однако исследования с точки зрения математической теории кодирования источника не приводятся. В этом смысле представляется актуальным произвести подобные исследования, и уточнить нал лучшие условия и параметры использования этого класса интервальных преобразований. Цель исследования. Целью диссертационной работы является разработка и исследование новых методов кодирования с помощью обобщенных интервальных преобразований, изучение важных с точки зрения современных прикладных вычислительных систем эффективных алгоритмов сжатия данных с использованием разработанных методов. Методы исследования. В работе использовались методы исследования из областей математического анализа, теории вероятностей, теории случайных процессов, вычислительной математики, теории кодирования источника. Графики функций вычислялись с помощью программ на языке “С” с использованием плавающей арифметики удвоенной точности. Алгоритмы сжатия данных реализовались на стандарте языка “С”, тексты программ легко переносимы на платформы, поддерживающие компиляцию языка “С”. Эффективность работы алгоритмов и конечная степень сжатия данных проверялась на сгандартных тестовых наборах, и сравнивалась со степенями сжатия, получаемыми с использованием известных алгоритмов компрессии. Промежуточные вычисления для табличного представления степеней сжатия файлов с использованием различных алгоритмов компрессии производились с помощью скриптовых языков “C-shell” и “Perl”. Научная новизна работы. Настоящая работа содержит обобщение классических и разработку новых методов кодирования источника, в ней систематизируется подход к целому ряду алгоритмов компрессии. На основе теоретических результатов, полученных в настоящей работе, можно оценивать эффективность практического применения интервального преобразования для улучшения существующих многофазовых алгоритмов сжатия данных, подобных, например, сжатию видео данных в рамках серии стандартов MPEG или сжатию неподвижных изображений в рамках серии стандартов . PEG. В работе предлагается ряд новых параллельных алгоритмов и методов. Основные результаты, выносимые на защиту.