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

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

1^0

Семенюк Владимир Витальевич

ВЕРОЯТНОСТНЫЕ МЕТОДЫ ЭКОНОМНОГО КОДИРОВАНИЯ ВИДЕОИНФОРМАЦИИ

Специальность: 05.13.13 - Телекоммуникационные системы

и компьютерные сети

Автореферат диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2004

Работа выполнена в Санкт-Петербургском государственном университете информационных технологий, механики и оптики

Научный руководитель:

доктор технических наук, профессор Васильев Владимир Николаевич

Официальные оппоненты:

доктор технических наук, профессор Тропченко Александр Ювенальевич

кандидат технических наук Павлова Валерия Анатольевна

Ведущая организация:

ЦНИИ «Электроприбор»

Защита диссертации состоится «2/ » Яакд^.! 2004г. в <ГГ0 на заседании диссертационного совета Д 212.227.05 при Санкт-Петербургском государственном университете информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, ул. Саблинская, д. 14.

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

Автореферат разослан « 2004 г.

Ученый секретарь

диссертационного совета

Поляков Владимир Иванович

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

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

Передача информации является основной областью применения экономного кодирования. На данный момент первоочередная задача -организация эффективного телевизионного и мультимедийного вещания. Как известно, видеоинформация представляет собой наиболее объемный тип информации. С учетом ограниченной пропускной способности цифровых каналов, чтобы гарантировать высокое качество передачи изображений, необходимо обеспечить их достаточно эффективное представление (качество передачи напрямую зависит от объема информации, передаваемого в единицу времени). По этой причине на протяжении уже более 15 лет значительные усилия направляются на разработку технологий эффективного представления изображений. Этой проблеме посвящена и рассматриваемая диссертационная работа.

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

РОС. !' V >НЛЛЬНАЯ

бь- . ■ ЧЕКА

г. ¡( герб)рг

гоо£рк

Задачи исследования. В рамках исследования решались следующие задачи:

1. Подробный анализ существующих методов контекстно-зависимого вероятностного кодирования.

2. Повышение эффективности широко распространенных стандартных схем кодирования JPEG и MPEG за счет использования контекстно-зависимых вероятностных методов.

3. Разработка эффективного алгоритма получения компактных представлений изображений на основе дискретного вейвлет-преобразования с применением методов контекстно-зависимого вероятностного кодирования.

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

1. Создание строгого формального описания контекстно-зависимых вероятностных моделей.

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

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

На защиту выносятся следующие результаты:

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

2. Алгебраическое доказательство оптимальности алгоритма Хаффмана для системы представления информации с произвольным основанием.

3. Формализация контекстно-зависимых вероятностных моделей.

4. Обобщение метода PPM (Prediction by Partial String Matching) - метод вложенных разбиений.

5. Метод получения адаптивной вероятностной оценки на основе статистики появления символов.

6. Алгоритм экономного кодирования коэффициентов дискретного косинусного преобразования.

7. Алгоритм экономного кодирования изображений на основе дискретного вейвлет-преобразования.

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

1. Произведено обобщение неравенства Макмиллана на случай вкладов символов в результирующую длину кода сообщения для случая неразделимого кодирования. Вычислена оптимальная длина вклада.

2. Предложено ранее не фигурировавшее в литературе строгое алгебраическое доказательство оптимальности алгоритма Хаффмана для системы представления информации с произвольным основанием.

3. Предложена строгая формализация контекстно-зависимых моделей.

4. Проведено обобщение метода РРМ

5. Предложен новый метод получения адаптивных вероятностных оценок.

6. Разработан новый высокоэффективный алгоритм экономного кодирования коэффициентов дискретного косинусного преобразования.

7. Разработан новый высокоэффективный алгоритм экономного кодирования изображений на основе дискретного вейвлет-преобразования.

Практическая ценность работы:

1. Разработанный алгоритм экономного кодирования коэффициентов дискретного косинусного преобразования позволяет в среднем на 10% повысить эффективность общепринятых стандартных схем JPEG и MPEG.

2. Разработанный алгоритм экономного кодирования изображений на основе дискретного вейвлет-преобразования является наиболее эффективным алгоритмом в своем классе. При фиксированном размере выходного кода эффективность алгоритма на 0.05-0.2 dB выше эффективности аналогичных решений. Алгоритм может быть успешно применен на практике для получения экономных представлений неподвижных изображений и видеопотоков.

3. Предложенный метод получения адаптивных вероятностных оценок является эффективной заменой методу, наиболее часто используемому на практике. В частности, применение разработанного метода в алгоритме кодирования изображений на основе дискретного вейвлет-преобразования в среднем позволило на 0.5% повысить эффективность кодирования и на 10% увеличить его производительность.

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

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

Апробация результатов работы. Результаты диссертационного исследования были представлены на Х1-й всероссийской научно-методической конференции «Телематика'2004», а также на 1-й конференции молодых ученых Санкт-Петербургского государственного университета информационных технологий, механики и оптики.

Публикации. Основные результаты диссертационного исследования опубликованы в 5 работах общим объемом 137 страниц: 3 статьи [1-3], 1 тезис [4] и 1 монография [5]. Все работы написаны без соавторов.

Структура и объем работы. Диссертационная работа состоит из введения, основной части, содержащей 2 главы, заключения, списка литературы и 3-х приложений. Общий объем работы - 99 страниц. Работа содержит 4 иллюстрации и 3 таблицы. Список литературы включает 68 библиографических источников.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

Используются следующие обозначения: х, — вклад, вносимый символом с Индексом /, х,^, — вклад, вносимый сообщением длины п, состоящим из символов с индексами 11,/2,...,гя, 1,и,2г^,я — длина реального

кода этого сообщения. Для случая стационарной независимой выборки потребовано выполнение следующих свойств:

1. */ь,2.....¡я = +*,2 +... + (аддитивность)

2. |/,1/2 . >(-в ,■ |<А/(п), где М(п) - неотрицательная функция, такая что М(п)/п 0 при п оо.

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

таким образом вкладов (Л' - мощность алфавита сообщений),

удовлетворяет неравенству Макмиллана

N

¿=1

(т - основание системы представления информации). Обобщение неравенства Макмиллана на случай вкладов позволяет вычислить оптимальную длину вклада для символа, появляющегося с вероятностью р:

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

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

/Ч*, = (с).

Значения функции ¥ находятся эмпирически - путем анализа того, как часто те или иные символы появляются в контексте, схожем с текущим. Критерий схожести находится экспериментальным путем. Выбирается ряд наиболее значимых факторов контекста, которые формируют некоторый ¿-мерный факторный вектор. Множество у всевозможных факторных векторов 3 разбивается на непересекающиеся

подмножества З^Зг.Зз.....Контексты, факторные вектора которых

' принадлежат одному и тому же подмножеству, считаются схожими.

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

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

Разбиение множества всевозможных факторных векторов на подмножества может быть осуществлено большим количеством способов. Учет сразу нескольких разбиений позволяет получать более объективные вероятностные оценки. Наиболее естественным решением является введение весов, определяющих значимость вероятностных оценок, получаемых для различных разбиений. Обозначая через а>1, вес, с которым

учитывается оценка вероятности появления символа с индексом i при

использовании 1-го разбиения (г/'^'"^®), можно выписать формулу для обобщенной оценки:

1=1

(L - количество различных разбиений).

Сложность получения обобщенных оценок в общем случае оценивается как 0(LN). Существенного упрощения вычислений можно добиться, если ограничить количество разбиений, учитываемых при получении каждой обобщенной оценки. В работе предлагается эффективный метод такого упрощения, являющийся обобщением подхода, впервые реализованного в методе PPM (Prediction by Partial String Matching). Метод получил название метод вложенных разбиений.

Будем говорить, что разбиение {з,^}^ вложено в разбиение

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

разбиения является подмножеством некоторого подмножества факторных векторов из второго разбиения: Vie[1,7]] 3/efl,^]: 3, , c32j. Пусть

имеется последовательность вложенных разбиений {з^}^ cj^}^, с...

Сначала делается попытка оценить появление символа с использованием первого разбиения - {з^}^. Если объема

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

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

значений всех счетчиков на 2. Обозначая через с^ значение счетчика частоты появления символа с индексом г после /-го масштабирования, а через Аир*- количество появлений символа с индексом I во временном интервале между (у'-1)-м и _/'-м масштабированием, можем написать

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

2

В диссертационной работе представлен альтернативный механизм адаптации, который с практической точки зрения более выгоден в сравнении с вышеизложенным механизмом. Предлагается отказаться от использования частотного подхода и работать исключительно с вероятностными оценками. Предположим, что выборка информационного источника некоторым образом поделена на небольшие порции Ди^. Обозначим долю символов с индексом г в каждой из этих порций через АпУ\ Введем параметр адаптации для учета степени влияния статистических особенностей очередной порции информации на вероятностную оценку (/). Адаптивная вероятностная оценка для символа

с индексом г после обработки ;"-й порции информации (г/Л) вычисляется по формуле

ДлР

Г(Л = (1 _ г) гО-П + у

Если положить у = М2 и Ди^^Сщщ/2, данная формула станет тождественной приведенной выше формуле для общепринятого метода получения вероятностных оценок. Таким образом, наиболее часто используемый на практике подход является частным случаем предлагаемого. Однако это совсем не означает, что новый метод получения адаптивных вероятностных оценок ничем не отличается от ранее изложенного метода. Предлагаемый метод свободен от некоторых недостатков, присущих общепринятому методу, и на практике реализуется

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

Вторая глава целиком посвящена методам экономного кодирования видеоинформации.

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

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

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

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

Практические эксперименты показали, что использование предложенного алгоритма позволяет повысить эффективность стандартных схем кодирования JPEG и MPEG в среднем на 10%. При этом не было отмечено заметного снижения скорости обработки информации.

В алгоритме экономного кодирования изображений на основе дискретного вейвлет-преобразования применяется высокоэффективная схема контекстно-зависимого кодирования, основанная на идеологии нуль-деревьев. Коэффициенты кодируются поразрядно, начиная от старших разрядов и заканчивая младшими. Отдельно обрабатываются знаки коэффициентов. При кодировании разрядов (знаков) используются пространственные контекстно-зависимые модели. Факторный вектор контекста для разряда коэффициента (знака) формируется на основе информации об уже обработанных разрядах (знаках) соседних коэффициентов. Порядок кодирования имеет древовидную структуру, что позволяет учесть особенности распределения абсолютных величин коэффициентов (распределение обладает так называемым масштабным подобием). При кодировании всевозможных двоичных значений применяется описанный выше новый метод получения адаптивных вероятностных оценок с множителем.

Было проведено практическое сравнение разработанного алгоритма с существующими аналогами. Сравнивалось пиковое соотношение сигнал-шум при фиксированном размере закодированного изображения. В среднем предложенный алгоритм оказался на 0.05-0.2 db эффективнее существующих решений.

ЗАКЛЮЧЕНИЕ

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

1. Сформулировано и доказано неравенство Макмиллана для случая неразделимых кодов. Вычислена величина оптимального вклада символа в результирующую длину кода сообщения.

2. Алгебраически доказана оптимальность алгоритма Хаффмана для системы представления информации с произвольным основанием.

3. Предложена строгая формализация контекстно-зависимых вероятностных моделей.

4. Осуществлено обобщение метода РРМ.

5. Предложен новый метод получения адаптивной вероятностной оценки на основе статистики появления символов.

6. Разработан новый высокоэффективный алгоритм экономного кодирования коэффициентов дискретного косинусного преобразования.

7. Разработан новый высокоэффективный алгоритм экономного кодирования изображений на основе дискретного вейвлет-преобразования.

2006-4

6773

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

1. Семенюк В. В. Алгоритм экономного кодирования изображений на основе вейвлет-преобразования с применением методов контекстно-зависимого вероятностного моделирования // Диагностика и функциональный контроль качества оптических материалов / Под. ред. д.т.н., проф. Ю. А. Гатчина и д.т.н., проф. В. Л. Ткалич. - СПб: СПбГУ ИТМО, 2004. - С. 99-107.

2. Семенюк В. В. Алгоритм экономного кодирования коэффициентов дискретного косинусного преобразования // Известия вузов. Приборостроение. - 2004. - Т. 47, Вып. 8. - С.24-28.

3. Семенюк В. В. Метод адаптивного кодирования двоичной информационной выборки // Известия вузов. Приборостроение. - 2004. -Т. 47, Вып. 5.-С. 36-41.

4. Семенюк В. В. Применение вероятностного моделирования в методах экономного кодирования видеоинформации // Труды XI Всероссийской научно-методической конференции Телематика'2004. - Санкт-Петербург, Россия, 7-10 июня, 2004. - С. 186-187.

5. Семенюк В. В. Экономное кодирование дискретной информации. -СПб: СПб ГИТМО (ТУ), 2001. - 115 с. - ISBN 5-7577-0076-9.

Тиражирование и брошюровка выполнены в Центре «Университетские телекоммуникации». Санкт-Петербург, Саблинская ул., 14. Тел (812)233-46-69

Тираж 100 экз. |

\ - - * '

Введение

1 Вероятностный подход в теории экономного кодирования

1.1. Информационное описание.

1.2. Вероятностный подход.

1.2.1. Энтропия.

1.2.2. Дешифруемые коды.

1.2.3. Оптимальная длина кода.

1.3. Методы генерации кода.

1.3.1. Префиксное кодирование.

1.3.2. Алгоритм Шеннона

1.3.3. Алгоритм Хаффмана

1.3.4. Статические системы префиксных кодов it 1.3.5. Арифметическое кодирование.

1.4. Контекстно-зависимое моделирование.

1.4.1. Проблема идентификации состояний.

1.4.2. Контекстно-зависимые модели.

1.4.3. Метод вложенных разбиений.

1.5. Получение вероятностных оценок на основе статистического анализа информационной выборки.

1.5.1. Метод получения неадаптивных оценок.

1.5.2. Метод получения адаптивных оценок с использованием скользящего окна

1.5.3. Метод получения адаптивных оценок с периодическим масштабированием значений счетчиков частот появления символов.

1.5.4. Метод получения адаптивных оценок с множителем

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

Передача информации является основной областью применения экономного кодирования. На данный момент первоочередная задача -организация эффективного телевизионного и мультимедийного вещания. Как известно, видеоинформация представляет собой наиболее объемный тип информации. С учетом ограниченной пропускной способности цифровых каналов, чтобы гарантировать высокое качество передачи изображений, необходимо обеспечить их достаточно эффективное представление (качество передачи напрямую зависит от объема информации, передаваемого в единицу времени). Как следствие, на протяжении уже более 15 лет значительные усилия направляются на разработку технологий эффективного представления изображений. Этой проблеме посвящена и данная диссертационная работа.

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

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

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

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

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

Таким образом, сочетание контекстно-зависимого вероятностного моделирования и арифметического кодирования наиболее выгодно с точки зрения эффективности. Данный подход к организации кодирования взят за основу в представленном диссертационном исследовании.

Задачи исследования. В рамках диссертационного исследования решались следующие задачи:

1. Подробный анализ существующих методов контекстно-зависимого вероятностного кодирования.

2. Повышение эффективности широко распространенных стандартных схем кодирования JPEG и MPEG за счет использования контекстно-зависимых вероятностных методов.

3. Разработка эффективного алгоритма получения компактных представлений изображений на основе дискретного вейвлет-преобразования с применением методов контекстно-зависимого вероятностного кодирования.

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

1. Создание строгого формального описания контекстно-зависимых вероятностных моделей.

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

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

На защиту выносятся следующие результаты:

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

2. Алгебраическое доказательство оптимальности алгоритма Хаффма-на для системы представления информации с произвольным основанием.

3. Формализация контекстно-зависимых вероятностных моделей.

4. Обобщение метода PPM (Prediction by Partial String Matching) -метод вложенных разбиений.

5. Метод получения адаптивной вероятностной оценки на основе статистики появления символов.

6. Алгоритм экономного кодирования коэффициентов дискретного косинусного преобразования.

7. Алгоритм экономного кодирования изображений на основе дискретного вейвлет-преобразования.

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

1. Произведено обобщение неравенства Макмиллана на случай вкладов символов в результирующую длину кода сообщения для случая неразделимого кодирования. Вычислена оптимальная длина вклада.

2. Предложено ранее не фигурировавшее в литературе строгое алгебраическое доказательство оптимальности алгоритма Хаффмана для системы представления информации с произвольным основанием.

3. Предложена строгая формализация контекстно-зависимых моделей.

4. Проведено обобщение метода РРМ

5. Предложен новый метод получения адаптивных вероятностных оценок.

6. Разработан новый высокоэффективный алгоритм экономного кодирования коэффициентов дискретного косинусного преобразования.

7. Разработан новый высокоэффективный алгоритм экономного кодирования изображений на основе дискретного вейвлет-преобразования.

Практическая ценность работы:

1. Разработанный алгоритм экономного кодирования коэффициентов дискретного косинусного преобразования позволяет в среднем на 10% повысить эффективность общепринятых стандартных схем JPEG и MPEG.

2. Разработанный алгоритм экономного кодирования изображений на основе дискретного вейвлет-преобразования является наиболее эффективным алгоритмом в своем классе. При фиксированном размере выходного кода эффективность алгоритма на 0.05-0.2 dB выше эффективности аналогичных решений. Алгоритм может быть успешно применен на практике для получения экономных представлений неподвижных изображений и видеопотоков.

3. Предложенный метод получения адаптивных вероятностных оценок является эффективной заменой методу, наиболее часто используемому на практике. В частности, применение разработанного метода в алгоритме кодирования изображений на основе дискретного вейвлет-преобразования в среднем позволило на 0.5% повысить эффективность кодирования и на 10% увеличить его производительность.

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

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

Апробация результатов работы. Результаты диссертационного исследования были представлены на XI-й всероссийской научно-методической конференции «Телематика'2004», а также на 1-й конференции молодых ученых Санкт-Петербургского государственного университета информационных технологий, механики и оптики.

Публикации. Основные результаты диссертационного исследования опубликованы в 5 работах общим объемом 137 страниц: 3 статьи [6, 7, 8], 1 тезис [9] и 1 монография [10]. Все работы написаны без соавторов.

Структура диссертационной работы выглядит следующим образом. Работа состоит из введения, основной части и заключения. Основная часть включает в себя 2 главы.

2.3. Основные результаты и выводы

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

1. Разработан новый высокоэффективный алгоритм экономного кодирования коэффициентов дискретного косинусного преобразования (см. раздел 2.2.2).

2. Разработан новый высокоэффективный алгоритм экономного кодирования изображений на основе дискретного вейвлет-преобразования (см. раздел 2.2.3).

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

Заключение

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

1. Сформулировано и доказано неравенство Макмиллана для случая неразделимых кодов. Вычислена величина оптимального вклада символа в результирующую длину кода сообщения.

2. Алгебраически доказана оптимальность алгоритма Хаффмана для системы представления информации с произвольным основанием.

3. Предложена строгая формализация контекстно-зависимых вероятностных моделей.

4. Осуществлено обобщение метода РРМ.

5. Предложен новый метод получения адаптивной вероятностной оценки на основе статистики появления символов.

6. Разработан новый алгоритм экономного кодирования коэффициентов дискретного косинусного преобразования.

7. Разработан новый алгоритм экономного кодирования изображений на основе дискретного вейвлет-преобразования.

1. Добеши И. Десять лекций по вейвлетам: Пер. с англ. - Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика», 2004.

2. Кричевский Р. Е. Сжатие и поиск информации. М.: Радио и связь, 1989.

3. Левенштейн В. И. Об избыточности и замедлении разделимого кодирования натуральных чисел // Проблемы кибернетики. М., 1968. - Вып. 20. - С. 173 - 179.

4. Рябко Б. Я. Сжатие информации с помощью стопки книг // Проблемы передачи информации. 1980. - Т. 16, Вып. 4. - С. 16 - 21.

5. Рябко Б. Я., Фионов А. Н. Эффективный метод адаптивного арифметического кодирования для источников с большими алфавитами // Проблемы передачи информации. 1999. - Т. 35, Вып. 4. - С. 95 - 108.

6. Семенюк В. В. Алгоритм экономного кодирования коэффициентов дискретного косинусного преобразования // Известия вузов. Приборостроение. 2004. - Т. 47, Вып. 8. - С. 24 - 28.

7. Семенюк В. В. Метод адаптивного кодирования двоичной информационной выборки // Известия вузов. Приборостроение. 2004. -Т. 47, Вып. 5. - С. 36 - 41.

8. Семенюк В. В. Применение вероятностного моделирования в методах экономного кодирования видеоинформации // Труды XI Всероссийской научно-методической конференции Теле-матика'2004. Санкт-Петербург, Россия, 7-10 июня, 2004. -С. 186 - 187.

9. Семенюк В. В. Экономное кодирование дискретной информации.- СПб: СПб ГИТМО (ТУ), 2001. 115 с. - ISBN 5-7577-0076-9.

10. И. Умняшкин С. В. Использование контекстного арифметического кодирования для повышения сжатия данных по схеме JPEG // Известия вузов. Электроника. 2001. - №3. - С. 96 - 98.

11. Хаффмен Д. А. Метод построения кодов с минимальной избыточностью: Пер. с англ. // Кибернетический сборник. М.: ИЛ, 1961. - Вып. 3. - С. 79 - 87.

12. Шеннон К. Математическая теория связи: Пер. с англ. // Работы по теории информации и кибернетике. М.: ИЛ, 1963. -С. 243 - 332.

13. Шкарин Д. А. Повышение эффективности алгоритма РРМ // Проблемы передачи информации. 2001. - Т. 37, Вып. 3. -С. 44 - 54.

14. Antonini М., Barlaud М., Mathieu P., Daubechies I. Image Coding Using Wavelet Transform // IEEE Trans, on Image Processing.- 1992. Vol. 1, N. 2. - P. 205 - 220.

15. Bloom C. Solving the Problems of Context Modeling. -http: / / www.cbloom.com / papers / ppmz.zip.

16. Bunt on S. Semantically Motivated Improvements for PPM Variants // The Computer J. 1997. - Vol. 40, N. 2/3. - P. 76 - 93 .

17. Calderbank R., Daubechies I., Sweldens W., Yeo B. L. Wavelet Transforms That Map Integers to Integers // J. Applied and Computational Harmonic Analysis (ACHA). 1998. - Vol. 5, N. 3. -P. 332 - 369.

18. Chrysafis C., Ortega A. Efficient Context-Based Entropy Coding for Lossy Wavelet image compression // Proc. IEEE Data Compression Conf. Snowbird, Utah, USA, Mar. 25 - 27, 1997. - P. 241 - 250.

19. Cleary J. G., Witt en I. H. Data Compression Using Adaptive Coding and Partial String Matching // IEEE Trans, on Communications. 1984. - Vol. 32, N. 4. - P. 396 - 402.

20. De Prisco R., De Sentis A. On the Redundancy Achieved by Huffman Codes // Information Sciences. 1996. - Vol. 88, N. 1. -P. 131 - 148.

21. Fano R. M. Technical N65. The Research Labaratory of Electronics, MIT, Max. 17, 1949.

22. Gallager R. G. Variations on a Theme by Huffman // IEEE Trans, on Information Theory. 1980. - Vol. 26, N. 1. - P. 15 - 25.

23. Golomb S. W. Run-Length Encoding // IEEE Trans, on Information Theory. 1966. - Vol. 12, N. 4. - P. 399 - 401.

24. Guazzo M. A General Minimum-Redundancy Source-Coding Algorithm // IEEE Trans, on Information Theory. 1980. - Vol. 26, N. 1.- P. 15 25.

25. Howard P. G. Lossless Image Comression / The Design and Analysis of efficient Lossless Data Comperssion Systems: Tech. rept. N CS-93-28.- Dept. of Computer Science, Brown University, Providence, Rhode Island, USA, 1993.

26. Howard P. G. Text Comression / The Design and Analysis of efficient Lossless Data Comperssion Systems: Tech. rept. N CS-93-28. Dept. of Computer Science, Brown University, Providence, Rhode Island, USA, 1993.

27. Howard P. G., Vitter J. S. Practical Implementations of Arithmetic Coding // Storer A. Image and Text Compression. Kluwer Academic Publishers, Massachusetts, USA, 1992. - P. 85 - 112.

28. Howard P. G., Vitter J. S. Arithmetic Coding for Data Compression // Proc. IEEE. 1994. - Vol. 82, N. 6. - P. 857 - 865.

29. Karush J. A Simple Proof of an Inequality of McMillan // IEEE Trans. Information Theory. Apr., 1961. - IT-7. - P. 118.

30. Kraft L. A Device for Quantizing, Grouping and Coding Amplitude Modulated Pulses: MS Thesis. Dept. of Electrical Engineering, MIT, Cambridge, Massachusetts, USA, 1949.

31. Langdon G. A Simple General Binary Source Code // IEEE Trans. Information Theory. Sep., 1982. - IT-28. - P. 800 - 803.

32. LoPresto S. M., Ramchandran K., Orchard M. T. Image Coding Based on Mixture Modeling of Wavelet Coefficients and a Fast Estimation-Quantization Framework // Proc. IEEE Data Compression Conf. Snowbird, Utah, USA, Mar. 25 - 27, 1997. - P. 221 - 230.

33. Marpe D., Cycon H. L. Efficient Pre-coding Techniques for Wavelet-Based Image Compression // Proc. PCS'97 (ITG Fachbericht). -Berlin, Germany, 1997. P. 45 - 50.

34. McMillan B. Two Inequalities Implied by Unique Decipherability // IEEE Trans. Information Theory. Dec., 1956. - IT-2. - P. 115 - 116.

35. Merhav N., Seroussi G., Weinberger M. J. Coding of Sources with Two-Sided Geometric Distributions and Unknown Parameters // IEEE Trans. Information Theory. Jan., 2000. - Vol. 46, N. 1. -P. 229 - 236.

36. Moffat A. M. A Note on the PPM Data Compression Algorithm: Res. rept. 88/7. Dept. of Computer Science, University of Melbourne, Victoria, Australia, 1988.

37. Moffat A. M. Implementing the PPM Data Compression Scheme 11 IEEE Trans, on Communications. 1990. - Vol. 38, N. 11. -P. 1917 - 1921.

38. O'Neal J. B. Predictive Quantizing Differential Pulse Code Modulation for the Transmission of Television Signals // Bell Systems Tech. J. 1966. - N. 5. - P. 689 - 721.

39. Pasco R. Source Coding Algorithms for Fast Data Compression: Ph.D. thesis. Dept.of Electrical Engineering, Stanford University, California, USA, 1976.

40. Pennebaker W. В., Mitchell J. L., Langdon G. G., Arps R. B.

41. An Overview of the Basic Principles of the Q-Coder Adaptive Binary Arithmetic Coder // IBM J. Research and Development. 1988. -Vol. 32, N. 6. - P. 717 - 726.

42. Rice R. F. Some Practical Universal Noiseless Coding Techniques: JPL Publication 79 22. - Jet Propulsion Labaratory, Pasadena, California, USA, Mar., 1979.

43. Rissanen J. J. Generalized Kraft Inequality and Arithmetic Coding // IBM J. Research and Development. 1976. - Vol. 20, N. 3. -P. 198 - 203.

44. Rissanen J. J., Langdon G. G. Arithmetic Coding // IBM J. Research and Development. 1979. - Vol. 23, N. 2. - P. 146 - 162.

45. Rubin F. Arithmetic Stream Coding Using Fixed Precision Registers // IEEE Trans. Information Theory. 1979. - Vol. 25, N. 6. -P. 672 - 675.

46. Rubin F. Experiments in Text File Compression // CACM. 1976. -Vol. 19, N 11. - P. 617 - 623.

47. Said A. and Pearlman W. A. A New Fast and Efficient Image Codec Based on Set Partitioning in Hierachical Trees // IEEE Trans.on Circuits and Systems for Video Technology. 1996. - Vol. 6, N. 3.- P. 243 250.

48. Shapiro J. M. Embedded Image Coding Using Zerotrees of Wavelets Coefficients // IEEE Trans, on Signal Processing. 1993. - Vol. 41, N. 12. - P. 3445 - 3462.

49. Schindler M. A Fast Renormalization for Arithmetic Coding // Proc. IEEE Data Compression Conf. Snowbird, Utah, USA, Mar. 30 -Apr. 1, 1998. - P. 572.

50. Taubman D. High Performance Scalable Image Compression with EBCOT // IEEE Trans, on Image Processing. 2000. - Vol. 9, N. 7. -P. 1170 - 2000.

51. Weinberger M. J., Seroussi G., Sapiro G. The LOCO-I Lossless Image Compression Algorithm: Principles and Standardization into JPEG-LS // IEEE Trans, on Image Processing. 2000. - Vol. 9, N. 8.- P. 1309 1324.

52. Witten I. H., Bell Т. C. The Zero Frequency Problem: Estimating the Probabilities of Novel Events in Adaptive Text Compression // IEEE Trans. Information Theory. 1987. - Vol. 37, N. 6. -P. 1085 - 1094.

53. Witten I. H., Neal R. M., Cleary J. G. Arithmetic Coding for Data Compression // CACM. 1987. - Vol. 30, N 6. - P. 520 - 540.

54. Wu X., Memon N. D. Context-Based, Adaptive, Lossless Image Coding // IEEE Trans, on Communications. 1997. - Vol. 45, N. 4. -P. 437 - 444.

55. Xiong Z., Ramchandran K., Orchard M. T. Space-FYequency Quantization for Wavelet Image Coding // IEEE Trans, on Image Processing. 1997. - Vol. 6, N. 5. - P. 677 - 693.

56. Xiong Z., Ramchandran K., Orchard M. T. Wavelet Packet Image Coding Using Space-Frequency Quantizaion // IEEE Trans, on Image Processing. 1998. - Vol. 7, N. 6. - P. 892 - 698.

57. Yoo Y., Ortega A., Yu B. Image Subband Coding Using Progressive Classification and Adaptive Quantization // IEEE Trans, on Image Processing. 1999. - Vol. 8, N. 12. - P. 1702 - 1715.

58. Zandi A., Allen. J., Schwartz E., Boliek M. CREW: Comression with Reversible Embedded Wavelets // Proc. IEEE Data Compression Conf. Snowbird, Utah, USA, Mar. 28 - 30, 1995. - P. 351 - 360.

59. ISO/IEC / JTC 1/SC 29/WG 10 Information Technology -Digital Compression and Coding of Continuous-Tone Still Images, ISO/IEC 10918.

60. ISO/IEC / JTC 1/SC 29/WG 11 Information Technology -Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to About 1,5 Mbit/s, ISO/IEC 11172.

61. ISO/IEC / JTC 1/SC 29/WG 11 Information Technology -Generic Coding of Moving Pictures and Associated Audio Information, ISO/IEC 13818.

62. ISO/IEC / JTC 1/SC 29/WG 1 Information Technology Lossless and Near-Lossless Compression of Continous-Tone Still Images, ISO/IEC 14495.

63. ISO/IEC / JTC 1/SC 29/WG 11 Information Technology -Coding of Audio-Visual Objects, ISO/IEC 14496.

64. ISO/IEC JTC 1/SC 29/WG 11 and ITU-T SG 16 Q.6 Study of Final Committee Draft of Joint Video Specification, ITU-T Rec. H.264 / ISO/IEC 14496-10 AVC, JVT-F100, Dec., 2002.

65. ISO/IEC / JTC 1/SC 29/WG 1 Information Technology JPEG 2000 Image Coding System, ISO/IEC 15444.

66. ISO/IEC / JTC 1/SC 24/WG 7 Information technology -Computer Graphics and Image Processing Portable Network Graphics (PNG): Functional Specification, ISO/IEC 15948.

67. ITU-T SG 16 Video Codec for Audiovisual Services at px64 kbits, ITU-T Recommendation H.261.

68. ITU-T SG 16 Video coding for low bit rate communication, ITU-T Recommendation H.263.