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

ВВЕДЕНИЕ.

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

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

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

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

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

1.5. Выводы.

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

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

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

2.2. Параллельные алгоритмы для кодирования с помощью обобщенных 49 интервальных преобразований в модели PRAM.

2.2.1. Параллельный алгоритм для кодирования с помощью 50 частичного интервального преобразования и кодов Голомба.

2.2.2. Итеративный параллельный алгоритм для кодирования с 52 помощью полного интервального преобразования и кодов

Голомба.

2.2.3. Однопроходный параллельный алгоритм для кодирования с 54 помощью полного интервального преобразования и кодов

Голомба.

2.3. Параллельные алгоритмы для кодирования с помощью обобщенных 58 интервальных преобразований в моделях, близких к реальным встраиваемым системам.

2.3.1. Разделяющее интервальное преобразование.

2.3.2. Кодирование с помощью интервальных преобразований для 61 встраиваемых систем.

2.4. Выводы.

ГЛАВА 3. КОДИРОВАНИЕ ИСТОЧНИКА С НЕИЗВЕСТНОЙ 66 СТАТИСТИКОЙ С ПОМОЩЬЮ ОБОБЩЕННЫХ ИНТЕРВАЛЬНЫХ ПРЕОБРАЗОВАНИЙ.

3.1. Флаговое интервальное преобразование.

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

3.1.2. Флаговое кодирование целых чисел.

3.2. Оценка длины кода флагового интервального преобразования.

3.3. Тестирование флагового интервального преобразования на реальных 76 данных.

3.4. Выводы.

ГЛАВА 4. ЭФФЕКТИВНОЕ СЖАТИЕ ИЗОБРАЖЕНИЙ С 82 ИСПОЛЬЗОВАНИЕМ ОБОБЩЕННЫХ ИНТЕРВАЛЬНЫХ ПРЕОБРАЗОВАНИЙ.

4.1. Эффективный алгоритм сжатия изображений без потерь качества JPEG 83 LOCO-I.

4.2. Модификация алгоритма JPEG LOCO-I.

4.3. Анализ алгоритма M-JPEG LOCO-I.

4.3. Результаты работы M-JPEG LOCO-I.

4.4. Выводы.

Актуальность темы.

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

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

Наиболее распространенными методами сжатия данных без потерь качества в практике международных стандартов [34,35,36,37,38,39,40] являются следующие три метода: метод арифметического кодирования, кодирование по Хаффману и кодирование длин серий. В данной работе предлагается новый метод обобщенных интервальных преобразований, основанный на кодировании длин серий, позволяющий значительно более гибко и полно использовать вычислительные возможности современных ЭВМ, чем исходный метод, и дающий возможность более эффективно осуществлять сжатие данных.

Кодирование длин серий было предложено еще К. Шенноном в его основополагающей работе [54], и впоследствии получило широкое распространение в теоретических исследованиях и практических разработках. Если есть последовательность из "0" и "1", причем "0" встречается чаще чем "1", то можно кодировать длины интервалов между последовательными вхождениями "1". Иначе говоря, можно кодировать длины серий из последовательно стоящих "0", поэтому метод получил название кодирования длин серий. Свою популярность этот метод заслужил, во-первых, благодаря своей алгоритмической простоте, и, во-вторых, благодаря малой избыточности в случае, когда вероятность "0" много больше вероятности "1". Однако, у кодирования длин серий есть и определенные недостатки, например, одним из недостатков этого метода, отмеченный еще К. Шенноном, является большая избыточность, когда вероятности "0" и "1" близки. Другим принципиальным недостатком метода кодирования длин серий является то, что этот метод не определен для алфавитов мощности большей чем 2.

Свое развитие метод кодирования длин серий получил в большом количестве теоретических и экспериментальных работ [1-7,17,20,33,43,48,49,60-62,64], патентов и международных стандартов [34,35,39,40]. Особо следует отметить работы С. Голомба [27], Р. Галлагера и Д. Ван Ворхиса [23], которые предложили и обосновали эффективный метод кодирования длин серий. Адаптивное кодирование с помощью кодов Голомба рассматривались в работах Г. Лангдона [43]. Более общий случай с мультисимвольными алфавитами интервальных преобразований изучал П.Елиас [20].

В течение 1997-2001гг. вышел целый ряд независимых публикаций в журналах, в трудах конференций и в специализированных интернет-конференциях, в которых был предложен новый класс мультисимвольных интервальных преобразований, обозначая тем самым новый этап в исследованиях интервальных преобразований. Так, в работе 3. Арнавута и С. Магливераса [15] строится новый класс интервальных преобразований, названный авторами "inversion frequencies", для обработки данных перед арифметическим кодированием для универсального сжимающего алгоритма Барроуза -Веллера [16]. Этот же класс интервальных преобразований был независимо предложен А. Кадачем [7] и автором диссертации [3]. Во всех вышеперечисленных работах по новому классу интервальных преобразований излагаются интересные и имеющие практическую значимость экспериментальные результаты по применению этого метода, однако исследования с точки зрения математической теории кодирования источника не приводятся. В этом смысле представляется актуальным произвести подобные исследования, и уточнить наилучшие условия и параметры использования этого класса интервальных преобразований.

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

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

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

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

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

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

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

- анализ алгоритмов кодирования с помощью обобщенных интервальных преобразований;

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

- разработка программного макета для новых алгоритмов кодирования с помощью обобщенных интервальных;

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

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

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

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

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

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

- разработан новый метод кодирования источника без памяти с помощью обобщенных интервальных преобразований, основанный на кодировании длин серий, и обобщающий конструкцию интервальных преобразований "inversion frequencies";

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

- разработаны новые параллельные алгоритмы для метода кодирования с помощью обобщенных интервальных преобразований;

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

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

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

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

1) новый метод кодирования источника с помощью обобщенных интервальных преобразований;

2) теоремы о стоимости и избыточности кодирования с помощью частичных и полных интервальных преобразований;

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

4) новый алгоритм сжатия данных автотестов для встраиваемых систем с использованием обобщенных интервальных преобразований и оценка длины кода этого метода компрессии;

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

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

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

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

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

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

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

- тезисы доклада "Новый алгоритм сжатия для встраиваемых систем", (Труды Всероссийской научно-техническая конференции "Новые материалы и технологии", Москва, МАТИ-РГТУ, 2002. - С.33-34)

- тезисы доклада "Эффективное сжатие картографических изображений без потерь качества" (Труды 6-ой международной конференции "Распознавание образов и анализ изображений", В. Новгород, 2002. - С. 85-87);

- тезисы доклада "Сжатие изображений методом преобразования сортировки" (Сборник трудов конференции "Теоретические и прикладные проблемы информационных технологий", Москва, изд. ВМиК МГУ, 2001. - С. 127-134);

- тезисы доклада "Улучшение кодирования искусственных изображений для алгоритма JPEG LOCO" (Материалы VIII международной конференции "Региональная информатика", Санкт-Петербург, 2002. - С. 97-98);

- статья "Применение интервальных преобразований для параллельных алгоритмов компрессии" (Информационные технологии и вычислительные системы, Москва, 2002, вып.2. - С.57-66);

- статья "Флаговое преобразование обратных частот" (Информационные технологии, Москва, изд. Новые технологии, 2002, №.11. - С. ] 9-25);

Апробация.

Результаты работы докладывались на 6-ой международной конференции "Распознавание образов и анализ изображений", (РОАИ-6, В. Новгород, 2002 г.), на Всероссийской научно-технической конференции "Новые материалы и технологии" (НМТ-2002, Москва, 2002 г.), на VIII международной конференции "Региональная информатика 2002" (РИ-VIII, Санкт-Петербург, 2002 г.), на конференции "Теоретические и прикладные проблемы информационных технологий" (Москва, 2001), а также докладывались и обсуждались на научных и технических семинарах ЗАО "МЦСТ", ИМВС РАН, Механико - Математического факультета и факультета Вычислительной Математики и Кибернетики МГУ им. Ломоносова.

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

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

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

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

В разделе 1.3 дается определение нового типа обобщенных интервальных преобразований - полных интервальных преобразований, дается определение кодирования с помощью полных интервальных преобразований. В этом разделе доказывается Теорема 1.2 о стоимости и избыточности кодирования с помощью полных интервальных преобразований, которая позволяет выразить стоимость и избыточность этого кодирования через вероятности, приписанные узлам дерева полного интервального преобразования, и стоимость и избыточность кодирования геометрически распределенных целых чисел. В разделе 1.3 также дается определение класса побуквенных полных интервальных преобразований, который совпадает с классом интервальных преобразований "inversion frequencies" (по терминологии 3. Арнавутаи С. Магливераса [15]), и показывается, что с помощью побуквенных полных интервальных преобразований можно построить кодирование источника со сколь угодно малой избыточностью.

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

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

Глава 2 посвящена параллельным алгоритмам выполнения кодирования с помощью обобщенных интервальных преобразований для модели PRAM и для некоторой специализированной модели PRAM для встраиваемых систем.

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

В разделе 2.2 строятся новые параллельные алгоритмы для кодирования с помощью обобщенных интервальных преобразований и кодов Голомба в случае общей модели PRAM. В подразделе 2.2.1 излагается новый параллельный алгоритм для кодирования с помощью частичных интервальных преобразований и оценивается сложность этого алгоритма в рамках модели PRAM. В подразделе 2.2.2 приводится параллельный алгоритм для кодирования с помощью полных интервальных преобразований, использующий алгоритм из подраздела 2.2.1 и оценивается сложность этого алгоритма. В подразделе 2.2.3 приводится новый параллельный алгоритм для кодирования с помощью полных интервальных преобразований, уже не использующий алгоритм для кодирования с помощью частичных интервальных преобразований и оценивается сложность этого алгоритма. Для всех вышеперечисленных алгоритмов показано, что время работы каждого алгоритма в рамках модели PRAM будет 0(log2 N) при использовании O(N) процессоров.

В разделе 2.3 рассматривается некоторая специализированная модель PRAM систем параллельных вычислений, приближенная к встраиваемым системам. В подразделе 2.3.1 описывается оригинальная конструкция разделяющего интервального преобразования, а в подразделе 2.3.2 приводится анализ сложности систем параллельного сжатия данных для описанной специализированной модели PRAM с использованием разделяющего интервального преобразования и частичного интервального преобразования.

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

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

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

В разделе 3.2 доказывается Теорема 3.1 об оценке длины кода флагового интервального кодирования, которая дает удобный инструментарий для наглядного представления о размере сжатого файла без выполнения самого сжатия. Эта оценка выражает длину кода флагового интервального кодирования через частоты букв кодируемого сообщения и длину флаговой битовой последовательности.

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

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

Глава 4 посвящена изучению сжатия изображений без потерь качества с использованием обобщенных интервальных преобразований.

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

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

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

В разделе 4.4 приводятся результаты работы модифицированного алгоритма сжатия изображений, использующего частичное интервальное преобразование в сравнении с результатами оригинального алгоритма JPEG LOCO-I на стандартном тестовом наборе Waterloo Repertoire. По входящим в этот набор искусственным изображениям наш модифицированный метод JPEG-LS превзошел оригинальный на 10%.

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

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

4.4. ВЫВОДЫ.

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

2) Показывается, что предлагаемый метод кодирования имеет избыточность, близкую к исходной для алгоритма JPEG-LS, в случае известной статистики последовательности ошибок, и имеет порядок скорости сходимости (адаптации) О

Г 1 ^ бит, где N - длина последовательности ошибок, в случае неизвестной

Jn ,

V" статистики.

3) Разработана программная реализация предлагаемой модификации алгоритма JPEG LOCO-I и проведена апробация реализованного алгоритма. Для тестирования использовался известный тестовый набор изображений Waterloo Repertoire. По входящим в этот набор искусственным изображениям наш модифицированный метод JPEG-LS превзошел оригинальный на 10%. На фотореалистичных изображениях новый алгоритм уступил (около 0.7%), однако по сумме всех файлов немного опередил JPEG-LS - на 0.5%.

ЗАКЛЮЧЕНИЕ.

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

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

R(f,S)=pA](R(fl,Sl)+R(f3,SseoJpXl))) + pA2R(f2,S2)

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

R(f,A,S)= £ Pjd)R(fgeom,^^) которое показывает, что избыточность такого кодирования зависит только от кодового дерева и избыточности кодирования геометрически распределенных целых чисел.

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

R{fn,S) = 0(.)/n) где п - длина укрупненного слова.

3) Разработаны новые алгоритмы для параллельного исполнения кодирования с помощью частичных и полных интервальных преобразований и кодов Голомба для модели PRAM. Для каждого из этих алгоритмов получена следующая точная по порядку оценка времени работы при использовании O(N) процессоров:

T(N)=0( log2AQ

4) Предложен новый алгоритм кодирования источников без памяти с неизвестной статистикой (метод флагового интервального преобразования, ФИП), который является суперпозицией побуквенных интервальных преобразований и флагового кодирования целых чисел с фиксированной длиной флаговой битовой последовательности. Доказывается, что для источника с неизвестной статистикой длина L F( / ; кода ФИП удовлетворяет следующим неравенствам:

4.10 ё(/>)>Я<Чпл<1Рг 1

1=1

-1 log

•-1 /

Эти неравенства позволяют оценивать длину кода ФИП без выполнения самого сжатия.

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

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

4N бит, где N - длина последовательности ошибок.

7) Разработана программная реализация предлагаемой модификации алгоритма JPEG LOCO-I и проведена апробация реализованного алгоритма. Для тестирования использовался известный тестовый набор изображений Waterloo Repertoire. По входящим в этот набор искусственным изображениям наш модифицированный метод JPEG-LS превзошел оригинальный на 10%.

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

1. Браиловский И.В. Новый алгоритм сжатия для встраиваемых систем // Труды Всероссийской научно-техническая конференции "Новые материалы и технологии", Москва, МАТИ-РГТУ, 2002. - С.33-34.

2. Браиловский И.В. Применение интервальных преобразований для параллельных алгоритмов компрессии // Информационные технологии и вычислительные системы, Москва, 2002, вып.2. С.57-66.

3. Браиловский И.В. Сжатие изображений методом преобразования сортировки // Сборник трудов конференции "Теоретические и прикладные проблемы информационных технологий", Москва, изд. ВМиК МГУ, 2001. С.127-134.

4. Браиловский И.В. Улучшение кодирования искусственных изображений для алгоритма JPEG LOCO // Материалы VIII международной конференции "Региональная информатика", Санкт-Петербург, 2002. С. 97-98.

5. Браиловский И.В. Флаговое преобразование обратных частот // Информационные технологии, Москва, изд. Новые технологии, 2002, №. 11. С. 19-25.

6. Браиловский И.В. Эффективное сжатие картографических изображений без потерь качества // Труды 6-ой международной конференции "Распознавание образов и анализ изображений", В. Новгород, 2002. С. 85-87.

7. Кадач А. Эффективные алгоритмы неискажающего сжатия текстовой информации. Диссертация на соискание степени кандидата физико-математических наук, Сибирское отделение РАН. Новосибирск, 1997.

8. Кнут Д. Искусство программирования для ЭВМ, том 3: Пер. с англ. М.: Мир, 1978.

9. Колмогоров А.Н. Три подхода к определению понятия количества информации // Проблемы передачи информации, 1965, Т.1, №1. С.3-11.

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

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

12. Феллер В. Введение в теорию вероятностей и ее приложения, том 1 : Пер. с англ. М.: Мир, 1967.

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

14. Ширяев А.Н. Вероятность М.:, Наука,1980.

15. Arnavut Z., Magliveras S. S. Block Sorting and Compression // Proc. IEEE Data Compression Conference, Snowbird, Utah, 1997.

16. Burrows M., Wheeler D. J. A Block-sorting Lossless Data Compression Algorithm // Digital Systems Research Center, Research report 124, 1994.

17. Chandra A., Chakrabarty K. Efficient test data compression and decompression for system-on-a-chip using internal scan chains and Golomb coding // Proc. Design Automation and Test in Europe (DATE) Conference, Munich, 2001. P. 145-149.

18. Chevion D., Karnin E.D. and Walach E. High efficiency, Multiplication free Approximation to Arithmetic Coding // Proc. IEEE Data Compression Conference, Snowbird, Utah, 1991. P.43-52.

19. Competitive parallel processing for compression of data // NASA Tech. Briefs, Feb. 1990, 14, 2. P.32-33.

20. Elias P. Interval and Recency Rank Source Coding: two on-line adaptive variable length schemes // IEEE Transactions on Information Theory, 1987,vol. JT-33, №.1. -P.3-10.

21. Elias P. Universal codeword sets and representations of the integers // IEEE Transactions on Information Theory, 1975, vol. IT-21, № 2. P. 194-203.

22. Fortune S., Wyllie J. Parallelism in random access machine // Proc. Tenth Annual ACM Symposium on Theory of Computing, 1978. P. 114-118.

23. Gallager R., Van Voorhis D. Optimal source codes for geometrically distributed integer alphabets // IEEE Transactions on Information Theory, 1975, vol. IT-21, № 3. -P. 228-230.

24. Gibbons A.M., Rytter W. Efficient Parallel Algorithms.- Cambridge: Cambridge University Press, 1988.

25. Giess G., Mayer A., Evers H., Meinzer H. Medical Image Processing and Visualization on Heterogeneous Clusters of Symmetric Multiprocessors // 12th International Parallel Processing Symposium, 1998.

26. Goldschlager L.M. A unified approach to models of synchronous parallel machines // Proc. Tenth Annual ACM Symposium on Theory of Computing, 1978. P.89-94.

27. Golomb S. W. Run length encoding // IEEE Transactions on Information Theory, 1966, vol. IT-12, №7. P.399-401.

28. Gonzales-Smith M.E., Storer J. A. Parallel algorithms for data compression // J. ACM, Apr. 1985, vol. 2. P. 344-373.

29. Henriques S., Ranganathan N. A parallel architecture for data compression II Proc. Second IEEE Symposium on Parallel and Distributed Processing, Dallas, Texas, 1990.

30. Howard P.G., Vitter J.S. Análisis of Arithmetic Coding for Data Compression // Proc. IEEE Data Compression Conference, Snowbird, Utah, 1991. P. 3-11.

31. Howard P.G., Vitter J.S. Parallel lossless image compression using Huffman and arithmetic coding compression // Proc. IEEE Data Compression Conference, Snowbird, Utah, 1992. P. 299-308.

32. Howard P.G., Witter J.S. Error modeling for hierarchical lossless image compression // Proc. IEEE Data Compression Conference, Snowbird, Utah, 1992. P.269-278.

33. Howard P.G., Witter J.S. Fast and efficient lossless image compression// Proc. IEEE Data Compression Conference, Snowbird, Utah, 1993. P. 351-360.

34. ISO/EEC 10918-1,2,3, JPEG (Digital compression and coding of continuous-tone still images). IS, 1994,1995,1997.

35. ISO/IEC 11544, Coded representation of picture and audio information Progressive bi-level image compression. - IS, 1993.

36. ISO/IEC 14495-1,2, JPEG-LS Lossless and near-lossless compression of continuous-tone still images. IS, 1999.

37. ISO/IEC 14496-2, MPEG4 Coding of audio-visual objects-Part 2: Visual. IS, 2001.

38. ISO/IEC 15444-1, JPEG2000 JPEG 2000 image coding system. IS, 2000.

39. ITU-T, SERIES T, T.4, Standardization of Group 3 facsimile terminals for document transmission. IS, 1999.

40. ITU-T, SERIES T, T.6, Facsimile coding schemes and coding control functions for group 4 facsimile apparatus. IS, 1988.

41. Knuth D.E. Dynamic Huffman Coding //J. Algorithms, June 1985, v.6. P. 163-1 80.

42. Langdon G.G, Jr. Probabilistic and Q-Coder Algorithms for Binary Source Adaptation // Proc. IEEE Data Compression Conference, Snowbird, Utah, 1991. P. 13-22.

43. Langdon G.G., Jr. An Adaptive Run-length Coding Algorithm // IBM Technical Disclosure Bulletin, Dec 1983, Vol. 26, No. 7B.

44. Leighton F.T. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Sun Mateo, CA: Morgan Kaufman Publishers, 1992.

45. Nelson M., Gailly J.-L. The data compression book. N.Y.: M&T Books, 1996

46. Netravali A., Limb J.O. Picture Coding: A Review // Proc. IEEE, 1980, Vol.68. -P.366-406.

47. Pasco R. Source Coding algorithm for fast data compression, Ph.D. thesis, Dept. Electric Eng. Stanford University, CA.- 1976.

48. Rice R. F. Some Practical Universal Noiseless Coding Techniques // JPL Publication 79-22, Jet Propulsion Laboratory, Pasadena, CA, Mar. 1979.

49. Rice R. F. Some Practical Universal Noiseless Coding Techniques // JPL Publication 91—3, Jet Propulsion Laboratory, Pasadena, CA, Nov. 1991.

50. Rissanen J. Generalized Kraft inequality and arithmetic coding II IBM Jr. Res. Develop.,, 1976, vol. 20. P. 198-203.

51. Rissanen J., Langdon G.G. Arithmetic Coding// IBM Jr. Res. Develop., 1979, vol. 23 (2). P. 149-162.

52. Rubin F. Arithmetic stream coding using fixed precision registers // IEEE Transactions on Information Theory, 1979, vol. 25, N0.6. P.672-675.

53. Ryabko,B. Fionov,A. Fast and Space-Efficient Adaptive Arithmetic Coding // Cryptography and Coding, 7th IMA International Conference, Cirencester, UK, Dec. 1999, LNCS 1746. P.270 -279.

54. Shannon C. A mathematical theory of communication // Bell System Technical Journal, 1948, v.27. P.379-423 and P.623-656.

55. StaufferL. M., Hirschberg D. S. Parallel Text Compression //report 91-44, University of California, Irvin, Jan. 1993, Technical report 91-44.

56. Storer J.A., Data Compression Methods and Theory. Computer Science Press, 1988.

57. Teng S.-H. The construction of Huffman-equivalent prefix code in NC // ACM SIGACTMay 1987, J. 18, 4. P. 54-61.

58. Todd S., Landgdon, G. G., Jr., and Rissanen J. Parameter reduction and context selection for compression of the gray-scale images // IBM Jr. Res. Develop., March 1985, vol. 29 (2). P.188-193.

59. Wang M. Almost Asymptotically Optimal Flag Encoding of the Integers // IEEE Transactions on Information Theory, Mar. 1988, vol. IT-34. P.324 - 326.

60. Weinberger M.J., G. Seroussi On adaptive strategies for an extended family of Golomb-type codes // Proc. Data Compression Conference, 1997. P. 131-140.

61. Weinberger M.J., Seroussi G., Sapiro G. The LOCO-I Lossless Image Compression Algorithm: Principles and Standardization into JPEG-LS // IEEE Transactions on Image Processing, 2000, Vol.9.

62. Weinberger M.J., Seroussi G., Sapiro G., Ordentlich E. JPEG-LS with limited-length code words// ISO/IEC JTC1/SC29/WG1 document N538, July 1997.

63. Yamamoto H., Ochi H. A New Asymptotically Optimal Code for the Positive Integers, // IEEE Transactions on Information Theory, Sep. 1991, vol. 37, №5. -P. 1420- 1429.

64. Zobel J., Moffat A. Adding compression to full-text retrieval system // Software -Practice and Experience, 1995, 25(8). P. 891-903.1. СПИСОК ИЛЛЮСТРАЦИЙ.

65. Рис. 1.1. Кодовое дерево для кодирования длин серий. 23

66. Рис. 1.2. Бинарное дерево полного интервального преобразования. 29

67. Рис. 1.3. Разбиение бинарного дерева полного интервального 30преобразования на два поддерева.

68. Рис. 1.4. Бинарное дерево побуквенного полного интервального кодирования. 32

69. Рис. 2.1. Бинарное дерево для интервального кодирования двоичных 43источников.

70. Рис. 2.2. Избыточность интервального кодирования при малых значениях 48порядка и.

71. Рис. 2.3. Минимум избыточности при использовании интервального 48кодирования малого порядка (и=1,2,4,8).

72. Рис. 3.1. Сравнение размеров текстовых и двоичных файлов, сжатых разными 78 алгоритмами.

73. Рис. 3.2. Сравнение размеров файлов изображений, сжатых разными 78алгоритмами.

74. Рис. 4.1. Взаиморасположение опорных точек изображения для предсказания 84 текущего значения яркости

75. Рис. 4.2. Сравнение размеров искусственных изображений, сжатых разными 93 алгоритмами.

76. Рис. 4.3. Сравнение размеров фотореалистичных изображений, сжатых разными 93 алгоритмами.