Разработка алгоритмов адаптивного сжатия видеоинформации на основе иерархических структур для задач оперативного отображения тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Жерздев, Сергей Владимирович

• Жерздев, Сергей Владимирович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Жерздев, Сергей Владимирович

Аннотация

Вводенис

В.1. Модели представления изображений

В.2. Сжатие растровых изображений

В.З. Основные требования к технологии сжатия

В.4. Цели и задачи

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

B.G. Научная новизна

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

В.8. Апробация полученных результатов

В.9. Содержание работы

Глава 1. Построение иерархической структуры отсчетов

1.1. Построение двоичного дерева отсчетов

1.2. Интерполяция и переход к разностному дереву

1.3. Преобразование структуры двоичного дерева отсчетов к усеченному двоичному дереву (УДЦ)

1.4. Кодирование структуры УДД

Глава 2. Кодирование значений отсчетов

2.1. Статистическое моделирование и кодирование

2.2. Кодирование значений отсчетов и ошибок интерполяции

2.3. Кодирование 16-разрядных значений отсчетов

2.4. Изображения с механизмом индексации цвета G

2.5. Эффективная реализация адаптивной статистической модели

Глава 3. Программное обеспечение

3.1. Общий алгоритм кодирования и декодирования фрагмента изображения

3.2. Общее описание программных подсистем

3.3. Применение утилит и библиотек

3.4. Практическое тестирование. Производительность

Введение диссертации (часть автореферата) на тему «Разработка алгоритмов адаптивного сжатия видеоинформации на основе иерархических структур для задач оперативного отображения»

В настоящее время необходимость графического представления — визуализации — информационных объектов, как отражения тех или иных процессов и явлений реальной действительности, повсеместно проявляется в теоретических исследованиях и инженерных приложениях, в области прикладной математики, в таких областях человеческой деятельности, как автоматическое проектирование (САПР и ЛСНИ), архитектура, издательское макетирование, обработка статической и динамической видеоинформации, геоинформациоииые системы (ГИС). Необходимость подобного представления информации возникает как на этапе ввода исходной информации, так и при получении и анализе численных результатов математического моделирования.

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

Настолько глобальная область применения стала причиной бурного развития аппаратуры ввода/вывода графической информации и, соответственно, теории компьютерной геометрии и машинной графики. Это привело, но сути дела, к появлению неизвестного ранее инструментария, позволившего решать новые задачи интерактивного информационного взаимодействия с пользователем, к созданию новых классов мультимедийных комплексов — от современных операционных систем до глобальных распределенных информационных сетей специального или общего назначения, в том числе сетей Internet,.

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

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

В.1. Модели представления изображений

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

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

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

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

В.1.2. Векторные модели. К векторным относят модели изображений, использующие описание изображения в виде набора графических примитивов, т.е. объектов из заранее определенного множества. Атрибутами графического примитива могут быть параметры аффинного преобразования, задающие положение и размеры объекта, а также цвет и, возможно, другие характеристики. Хотя в названии данного подхода и присутствует термин "векторный", предполагается использование не только кусочно-линейных моделей представления объектов изображения. Например, одним из способов описания графических данных является задание границ объектов всевозможными онлайновыми кривыми или локальными однородными хорошо приспособленными базисными функциями (ЛОХПБФ).

Однако, поскольку большая часть аппаратуры ввода/вывода является растровой, то на этапе ввода и/или при последующем хранении изображений возникает необходимость векторизации или аналитической параметризации исходной матрицы пикселей. На этапе визуализации изображения, в свою очередь, требуется обратное преобразование к растровой модели — растеризация векторной модели, что приводит к значительному снижению производительности выборки графической информации. Такой подход оказывается эффективным только в случае небольшого количества объектов изображения. Кроме того, векторизация изображений является достаточно сложным и ресурсоемким процессом, примыкающим к теории распознавания образов. А векторизация "живого" изображения (например, фотографии) практически невозможна.

В.1.3. Модели синтеза. Синтез изображений по заданной математической модели визуализируемого объекта является практически единственным приемлемым решением в случае динамического изменения характеристик самого объекта или параметров визуализации. Наиболее ярко задачи такого класса проявляются в интерактивных системах виртуальной реальности (тренажеры, игры). Математическая модель таких изображений — наиболее компактная форма представления графических данных. Однако, несмотря на заметное развитие программно-аппаратных средств визуализации моделей, реалистичность создаваемого изображения и скорость его генерации остается для многих задач недостаточной.

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

В первом случае применение растровых моделей обусловлено объективными причинами:

• технология работы большинства устройств ввода/вывода опирается на применение растровой модели;

• характер обрабатываемых изображений (полутоновые и полноцветные изображения с шумами);

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

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

В.2. Сжатие растровых изображений

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

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

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

Объем информации, описывающей изображение может уменьшаться на каждом из этих этапов. Так, в методе RRE-кодирования [29] элементами структурной модели являются не отдельные пиксели, а однотонные прямоугольники пикселей. На практике для определенных классов изображений объем описания такой модели может быть в несколько раз меньше объема исходной матрицы атрибутов пикселей. В методе сжатия на базе ЛОХПБФ [4, 14, 19| на этапе интерполяционного моделирования происходит уменьшение объема структурной модели (двоичного дерева) за счет исключения из пес элементов, восстанавливаемых с заданной погрешностью. Но типичной является ситуация, в которой первые две стадии только формируют "хороший" для кодирования поток, а собственно сжатие происходит на этапе кодирования.

В.2.1. Структурное моделирование. На этом этане осуществляется переход от матрицы атрибутов пикселей к некоторой альтернативной модели изображения. Такая модель может как реорганизовать набор пикселей в некоторую структуру, отражающую их пространственное взаимоположение, так и оперировать другими видами элементов изображения, устраняя содержательную избыточность. Обычно на этом этапе производится редукция размерности путем применения одного из видов развертки пикселей в последовательный поток атрибутов (15].

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

В рамках структурного представления изображения могут быть описаны признаками выделенных и классифицированных объектов изображений. Структурное представление само по себе уже является сжатым изображением и частью решения задач распознавания (24, гл.7]. При структурном представлении данных часто исходят из семантических соображений, которые и диктуют способ представления данных. Структурное представление соответствует векторным моделям изображений и моделям синтеза.

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

Матричное представление данных. Простейшая структурная модель растрового изображения — представление его непосредственно матрицей атрибутов пикселей. Основное достоинство матричного представления — сохранение структуры исходного изображения (пространственной организации и цвета). Иногда такое представление графических данных называют прямым; оно позволяет легко реализовать последовательную и параллельную обработку всего изображения. Поскольку классические алгоритмы кодирования требуют одномерного входного потока, практически всегда матричное представление данных сочетается с редукцией размерности применением того или иного метода развертки 117, 22, 23, 26, 28, 31].

Иерархическое представление данных. Иерархическое представление данных основывается на применении иерархических структур, таких как двоичные деревья, квадродеревья, деревья квадрантов и т.д. При этом изображение представлено иерархическим набором матриц атрибутов пикселей — упорядоченной последовательностью нескольких изображений различного разрешения, сходящихся к исходному [4, 8, 11, 14, 17, 19, 30, 33, 41, 56].

В памяти ЭВМ хранится двумерный массив отсчетов к-го уровня (исходного изображения, прореженного в 2к раз по каждой из координат), и набор ошибок интерполяции, позволяющих получить массивы отсчетов уровней к — 1, к — 2,., прореженные соответственно в 2fc-1, 2fc~2,. раз, вплоть до 0-го уровня — полного изображения. На каждом иерархическом уровне массив отсчетов вместе с ошибками интерполяции используется для получения пропущенных отсчетов следующих, более детальных уровней.

С целью уменьшения поуровневых ошибок интерполяции используют различные интерполирующие функции. В работах [4, 8, 14, 19| предложено в качестве интерполирующих функций использовать локальные однородные хорошо приспособленные сглаживающие ГЛ и восстанавливающие КА функции.

Иерархические методы имеют следующие существенные преимущества:

• высокий коэффициент сжатия;

• управляемая величина ошибки сжатия (без потерь, с контролем максимальной покоординатной погрешности);

• малая вычислительная сложность;

• возможность мультиразрешения (работы на разных уровнях детализации);

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

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

В последнее время большую популярность получают различные виды вей влет (wavelet)-npeo6pa30BaiiHfi [84, 85, 90].

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

Фрактальное coicamue. В основе фрактального сжатия [86, 93, 94] лежит рассмотрение в качестве элементов изображения не отдельных пикселей, а сегментов(блоков) заданной формы и переменного размера и поиск подобия между таковыми элементами изображения. Поиск в изображеЕШи подобных областей и сохранение в выходной поток только коэффициентов преобразований подобия позволяет достичь для некоторых классов изображений фантастических коэффициентов сжатия при сохранении высокого качества изображения.

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

В.2.2. Интерполяционное и статистическое моделирование. Задача этого этапа — уменьшение энтропии описания структурной модели за счет выявления корреляционных связей между элементами структурной модели.

Задачей статистического моделирования является оценка вероятности для каждого символа. Связь между вероятностями и кодами установлена в теореме Шеннона кодирования источника [46|. Различают статическое, полуадаптивное и адаптивное (или динамическое) моделирование.

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

В настоящее время наиболее широко распространено применение различных вариантов технологии PPM (prediction by partial matching) [65, 78], реализующей адаптивную смешанную модель. Существенные усовершенствования метода РРМ были предложены в [35, 36].

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

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

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

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

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

Наиболее известным методом такого рода является групповое кодирование (RLE, RiinLengtli Encoding) [48] — один из самых старых и самых простых алгоритмов архивации графики.

Также следует упомянуть достаточно часто применяемые при сжатии графической информации модели новизны или MTF-методы (move-to-front). Многие авторы разрабатывали варианты этого алгоритма [6, 12, 70]. Модификация этого алгоритма, обеспечивающая контекстно-зависимое моделирование предлагается в (28].

В качестве предварительного этапа перед применением MTF может использоваться преобразование Бэрроуза- Уиллсра (Burrows

Wheeler Transform, BWT) [92, 96]. Это обратимый алгоритм перестановки символов во входном потоке, позволяющий эффективно сжать полученный в результате преобразования блок данных. Обобщением BWT является преобразование Шиндлера (Schindler Transform, ST) N-ro порядка [97].

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

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

Хорошо известным методом статистического кодирования является алгоритм Хаффмана (47]. Однако, в настоящее время он постепенно вытесняется альтернативными алгоритмами. Модификации алгоритма Хаффмана для эффективного его применения совместно с адаптивными статистическими моделями предлагаются в [66, 69, 74, 76].

Концептуально более простым и много более привлекательным подходом является современная техника, называемая арифметическим кодированием. Полное описание и оценка, включая полную реализацию на С, дается в [75]. Различным вопросам реализации арифметического кодирования посвящены многие работы, например [32, 54, 67]. Вопросы практической реализации адаптивных статистических моделей для арифметического кодирования более подробно освещены в разделе 2.5. В некотором роде альтернативой статистическому кодированию можно считать алгоритмы словарного кодирования. Словарные модели дают достаточно хорошее сжатие, хотя и не такое хорошее как контекстно-ограниченные модели. Можно показать, что большинство словарных кодирующих методов могут быть воспроизведены с помощью контекстно-ограниченных моделей [58, 61], поэтому их главным достоинством является не коэффициент сжатия, а экономия машинных ресурсов.

Почти нее практические словарные схемы кодирования принадлежат семье алгоритмов, происходящих из работ Зива и Лемпе-ла |50, 52, 53]. Это семейство алгоритмов обозначается как LZ-сжатие. Сжатие Лемнела-Зива есть общий класс методов адаптивного словарного сжатия. На практике LZ-методы добиваются хорошего сжатия, их важным свойством является очень быстрое декодирование.

В.З. Основные требования к технологии сжатия

Чрезвычайно остро проблема эффективной организации видеоинформации проявляется в задачах геоинформационных систем (ГИС), в силу большого объема и разнородности обрабатываемой информации и высоких требований к оперативности, и при работе в глобальных вычислительных сетях (ГВС), в силу низкой скорости и/или высокой стоимости передачи информации.

Существенной особенностью ГИС по сравнению с другими предметными областями является очень широкое разнообразие типов данных, подлежащих хранению и обработке на различных этапах работы с пространственно-распределенной информацией — сканированные и программно формируемые географические карты, планы, аэрофотоснимки и космические снимки, фотографические изображения объектов, а также матрицы высот, уровней затопления, карты концентрации химических веществ в атмосфере, температурных распределений и других пространственно-распределенных данных. Ко всем этим типам данных предъявляются различные требования по уровню детализации, динамическому диапазону и допустимой точное™ представления. Тем не менее, все они обладают растровой организацией данных и в процессе хранения, передачи и доступа могу т рассматриваться как растровые изображения с различными классами атрибутов пикселей.

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

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

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

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

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

Жесткие требования этих задач объединяются при реализации удаленного доступа к ГИС посредством ГВС (например, работа пользователя через интернет).

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

• высокая степень компрессии;

• высокое качество изображения, что, как правило, означает сжатие без потерь и/или с контролем погрешности но метрике Чебышева;

• целочисленные алгоритмы сжатия/восстановления;

• высокая скорость компрессии, точнее — ограничение снизу па объем обрабатываемых данных в единицу времени;

• высокая скорость декомпрессии, задана минимальная допустимая производительность;

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

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

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

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

В настоящее время разработано и реализовано большое число методов адаптивного сжатия видеоинформации: методы дифференциального кодирования, кодирование с преобразованием, фрактальные, аппроксимационные методы, иерархические и другие. Значительный вклад в развитие методов адаптивного сжатия внесли работы российских ученых А.С.Лебедева, Н.Н.Красильникова, Ю.М.Штарькова, В.А.Вигтих, Ю.Г.Васина, В.В.Александрова, В.В.Сергеева и других, а также зарубежных ученых Дж.О.Лимба (J.О.Limb), У.Претта

W.K.Pratt), Р.Грэхема (R.Graham), М.Кунта (M.Kunt), П.Берта (P.Burt), С.М.Коргмана (C.M.Kortman) и других.

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

В.4. Цели и задачи

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

Для достижения этой цели в диссертации решены следующие задачи:

• Анализ существующих методов и технологий адаптивного сжатия видеоинформации.

• Разработка и исследование единой информационной технологии целочисленного адаптивного сжатия широкого спектра видеоинформации и входящих в нее методов и алгоритмов преобразования данных: интерполяция на базе ЛОХПБФ, иерархические структуры представления видеоинформации, методы статистического кодирования.

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

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

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

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

В.6. Научная новизна

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

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

• Предложены модификации алгоритма построения усеченных двоичных деревьев (УДД) для иерархического представления объектов различной природы (одномерные последовательности, параметрически заданные кривые на плоскости и в пространстве, звук, полутоновые и цветные изображения, в т.ч. с механизмом индексации цвета) на базе ЛОХПБФ.

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

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

• Разработаны методы повышения эффективности представления данных с помощью иерархических структур полных и усеченных двоичных деревьев (ПДЦ, УДД) при сохранении погрешности восстановленных данных в заданных пределах.

• С целью устранения статистической избыточности полученного потока информации разработана методика эффективного кодирования структуры УДД и значений отсчетов в узлах УДД и ПДД. Разработаны алгоритмы кодирования УДД и ПДД, проведено сравнительное исследование эффективности различных статистических моделей (статических и адаптивных) при кодировании видеоинформации различной природы.

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

• Предложен алгоритм построения статистической модели с маскировкой. Такая модель обеспечивает несколько лучшие результаты, чем контекстно-независимая, и при этом требует гораздо меньших вычислительных ресурсов, чем контекстно-зависимая степени 1.

• Предложена составная статистическая модель, которая позволяет использовать адаптивное статистическое моделирование на относительно небольших фрагментах 16-разрядных входных данных.

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

Разработанная технология была реализована в виде соответствующего ПО, при этом

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

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

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

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

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

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

В основу диссертационной работы положены результаты, полученные автором в ходе исследований, проводимых по плану НИОКР Федеральной службы геодезии и картографии России на 1999-2002 год в рамках проведения ОКР "Экран" в НИИ ПМК ННГУ. Работа выполнена при финансовой поддержке РФФИ, грант поддержки ведущих научных школ №00-15-96108 и ФЦП "Интеграция" проект К-03392.

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

В.8. Апробация полученных результатов

Разработанная технология внедрена:

• на предприятиях Федеральной службы России по геодезии и картографии в рамках технологии создания цифровых карг и планов городов всего масштабного ряда;

• в Главном управлении океанографии и навигации МО РФ в составе программно-аппаратного комплекса "Электронная карга" при создании мировой коллекции электронных морских навигационных карт (ЭМНК) в международном обменном формате S-57;

• в НИИ ПМК ННГУ в системе символизации картографического изображения на экранах коллективного и индивидуального пользования (ОКР "Экран") в подсистемах РАСТР и РАСТР-ЭКРАН;

• на предприятии Нижновэнерго(Нижний Новгород) в проблемно-ориентированной ГИС "Кабельные сети";

• в системе ведомственного кадастра Высшей школы в объектно-ориентированной ГИС "Терра";

• на факультете ВМК ННГУ (кафедра ИИСГсо) в учебном процессе.

Результаты диссертационной работы докладывались и обсуждались на IV международной конференции "Связь 2001" (Владимир), па VI конференции "Методы и средства обработки сложной графической информации" (Н.Новгород, 2002), на конференции "Математика и кибернетика 2002" (Н.Новгород), на 12-й Международной конференции по компьютерной графике и машинному зрению ГрафиКон'2002 (Н.Новгород), на 6-й международной конференции "Распознавание образов и анализ изображений. Новые информационные технологии" (Великий Новгород, 2002), на VII-й конференции "Методы и средства обработки сложной графической информации" (П.Новгород, 2003).

Практические результаты и выводы, сделанные при работе по теме диссертации, нашли свое отражение в 11 опубликованных печатных работах.

В.9. Содержание работы

Диссертация состоит из трех глав:

1. Построение иерархической структуры отсчетов.

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

УДА

2. Кодирование значений отсчетов.

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

3. Программное обеспечение

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Жерздев, Сергей Владимирович

Заключение

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

• высокую степень компрессии;

• сжатие без потерь или с контролем погрешности по метрике Чебышева;

• высокую скорость компрессии и декомпрессии;

• оперативный доступ к заданному фрагменту изображения;

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

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

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

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

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

Разработаны алгоритмы кодирования УДЦ и ПДД, проведено сравнительное исследование эффективности различных статистических моделей (статических и адаптивных) при кодировании видеоинформации различной природы. Исследована возможность уменьшения затрат вычислительных ресурсов для некоторых классов задач (например, визуализация графических данных).

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

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

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

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

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

Полученные результаты внедрены в системе символизации картографического изображения "Экран" в подсистемах РАСТР и РАСТР-ЭКРАН; в объектно-ориентированной геоинформационной системе "Терра".

Список литературы диссертационного исследования кандидат технических наук Жерздев, Сергей Владимирович, 2004 год

1. Неймарк Ю.И., Васин Ю.Г.

2. Кодирование больших массивов информации в связи с задачами распознования образов.

3. Изв. вузов. Радиофизика, 1968. С.1081-1085.2. Васин Ю.Г., Савина Т.В.

4. Кодирование ЭКГ неравномерными отсчетами.

5. Сборник "Биологическая и медицинская кибернетика" 4.4. М., 1974. С.73-74.3. Васин Ю.Г.

6. Сжатие исходного описания ЭКГ-сигналов.

7. В кн. "Теория и практика разработки автоматизированных медицинских информационных систем" Труды Республиканской конференции, Киев, 1975. С.69-75.

8. Васин Ю.Г., Бакараева В.П.

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

10. Математическое обеспечение САПР: Межвуз.сб. Горький: ГГУ, 1978, вып.1.5. Стронгин P.P.

11. Численные методы в многоэкстремальных задачах.1. М.: Наука, 1978.6. Рябко Б.Я.

12. Кодирование источника с неизвестными, но упорядоченными вероятностями.

13. Проблемы передачи информации, 1979, Т.14, №2.7. Васин Ю.Г.

14. Хорошо приспособленные базисы и задачи обработки экспериментальной информации: учебное пособие. -Горький: ГГУ, 1979.8. Васин Ю.Г.

15. Оптимизация описания исходных данных в диалоговых системахрешения задач классификации.

16. В кн. "Современное состояние теории исследования операций" М.: Наука, 1979. С.424-450.9. Митчелл О.Р., Дели Э.

17. Усеченное блочное кодирование многоуровневой информации. // ТИИЭР, 1980, т.68, т.10. Ноултон К.

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

19. Нетравали А.Н., Лимб Дж.О. Кодирование изображений: обзор.1. ТИИЭР, 1980, т.68, т.12. Рябко Б.Я.

20. Сжатие информации с помощью стопки книг.

21. Проблемы передачи информации, 1980, Т.16, №4.13. Чукин Ю.В.

22. Стукгуры данных для представления изображений.

23. Зарубежная радиоэлектроника, 1983, №8.14. Васин Ю.Г.

24. Хорошо приспособленные локальные однородные методы обработки графической информации.

25. Автоматизация обработки сложной графической информации: Межвуз.сб. Горький: ГГУ, 1984.

26. Васин Ю.Г., Бакараева В.Г.

27. Адаптивное сжатие изображений с использованием кривой Пеа-но.

28. Труды Всероссийской нонференции "Обработка изображений и дистанционные исследования", Новосибирск: ВЦ СОАН СССР, 1984, с.34-38.

29. Кунт М., Икономонулос А., Кошер М.

30. Методы моделирования изображений второго поколения. // ТИИЭР, 1985, т.73, №4.

31. Александров В.В., Горский Н.Д.

32. Представление и обработка изображений. Рекурсивный подход.1. Л.: Наука, 1985.

33. Мусмаи Х.Г., Пирш П., Граллсрт Х.Й. Достижения в области кодирования изображений. // ТИИЭР, 1985, т.73, №4.19. Васин Ю.Г.

34. Эффективность различных стратегий обработки видеоинформации на базе локальных однородных функций.

35. Методы и средства обработки графической информа-ции:Межвуз.сб. Горький: ГГУ, 1986. С.4-47.20. Кричевский Р.Е.

36. Сжатие и поиск информации. —М.: Радио и связь, 1989.21. Колмогоров А.Н.

37. Три подхода к определению понятия "Количество информации".

38. Новое в жизни, науке, технике. Сер. "Математика, кибернетика". №1, 1991. С.24 -29.22. Романов В.Ю.

39. Популярные форматы файлов для хранения графических изображений на IBM PC.1. М: Унитех, 1992.23. Климов А.С.

40. Форматы графических файлов.

41. К.: НИПФ "ДиаСофт Лтд.", 1995.24. Яншин В.В.

42. Анализ и обработка изображений: принципы и алгоритмы.1. М.: Машиностроение, 1995.25. Зив Дж.

43. Неравенства и алгоритмы универсального сжатия данных.

44. Проблемы передачи информации. 1996. Т.32. Выи.1. С.35-40.26. Кснцл Т.1. Форматы файлов Internet.1. СПб: Питер, 1997.27. Шлихт Г.Ю.

45. Цифровая обработка цветных изображений.1. М.: ЭКОМ, 1997.28. Кудин А.В.

46. Алгоритм PIRH-кодирования технических изображений.

47. Вестник Нижегородского государственного университета. Математическое моделирование и оптимальное управление. Нижний Новгород: Изд-во Нижегородского ун-та, 1998. Выи.1 (18).29. Кудип А.В., Жерздев С.В.

48. Алгоритм RRE-кодирования технических изображений.

49. Вестник Нижегородского университета. Математическое моделирование и оптимальное управление. Н.Новгород: Изд-во НН-ГУ, 1998. Вып.2 (19).

50. Гашников М.В., Глумов Н.И., Сергеев В.В. Информационная технология компрессии изображений в системах оперативного дистанционного зондирования.

51. Известия Самарского научного центра РАН, 1999, JYH, с.99 107.

52. Кудин А.В., Жерздев С.В., Жерздев А.В.

53. Свертка растра пикселов в последовательный образ в алгоритме PIRH-кодирования технических изображений.

54. Вестник Нижегородского университета. Математическое моделирование и оптимальное управление. Н. Новгород: Изд-во ИНГУ, 1999. Вып.1 (20). С.219-225.32. Рябко Б.Я., Фионов А.Н.

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

56. Проблемы передачи информации. 1999. Т.35. Вып.4. С.95-108.

57. Гашников М.В., Глумов Н.И., Мясников В.В., Сергеев В.В., Farbcrov Е.

58. Технология эффективного хранения и оперативного отображения картографической растровой информации.

59. Диссертация на соискание ученой степени кандидата технических наук. Нижний Новгород, 2000.35. Шкарин Д.А.

60. Практическая реализация алгоритма РРМ.материалы сайта http://sochi.net.ru/ maxime/coiripression.sbtinl36. Шкарин Д.А.

61. Повышение эффективности алгоритма РРМ.

62. Проблемы передачи информации. 2001. Т.37. Вып.З. С.44-51.37. Васин Ю.Г., Жерздев С.В.

63. Адаптивное сжатие видеоинформации на базе ЛОХПБФ // Тезисы 4-й международной конференции "Связь 2001". Владимир, 2001.38. Васин Ю.Г., Жерздсв С.В.

64. Программный комплекс для исследования методов эффективного кодирования усеченных двоичных деревьев // Труды 6-й конференции "Методы и средства обработки сложной графической информации". Н.Новгород, 2001. С.31-33.39. Васин Ю.Г., Жерздев С.В.

65. Реализация алгоритмов эффективного кодирования усеченных двоичных деревьев в задаче сжатия изображений // Труды 6-й конференции "Методы и средства обработки сложной графической информации". Н.Новгород, 2001. С.ЗЗ 36.40. Васин Ю.Г., Жерздев С.В.

66. Эффективное кодирование усеченных двоичных деревьев в задаче сжатия изображений

67. Труды 6-й конференции "Методы и средства обработки сложной графической информации". Н.Новгород, 2001. С.36-38.

68. Методы компьютерной обработки изображений / Под ред. В.А.Сойфсра.

69. М.: Физмаглит., 2001, 784 с.42. Жерздев С.В.

70. Практическая реализация адаптивной статистической модели с применением иерархической структуры данных // Материалы докладов конференции "Математика и кибернетика 2002". Н.Новгород, 2002. С.43-45.43. Васин Ю.Г., Жерздев С.В.

71. Технология иерархического кодирования видеоинформации // Тезисы 12-й Международной конференции по компьютерной графике и машинному зрению ГрафиКон'2002. Н.Новгород: Изд-во НГАСУ, 2002. С.326-333.44. Васин Ю.Г., Жерздев С.В.

72. Технология хранения и передачи данных ГНС // Труды 7-й конференции "Методы и средства обработки сложной графической информации". Н.Новгород, 2003. С.30 -31.45. Васин Ю.Г., Жерздев С.В.

73. Учебная программа по технологии организации мультимедийных данных ГИС

74. Труды 7-й конференции "Методы и средства обработки сложной графической информации". Н.Новгород, 2003. С.32-33.46. Shannon С.Е.

75. A mathematical theory of communication. Bell Syst.Tech.J., 27(Jul.l948), pp.398-403.47. Huffman D.A.

76. A method for the construction of minimum redundancy codes. In Proceedings of the Institute of Electrical and Radio Engineers 40, 9(Sept.l952), pp.1098-1101. 18. Golomb S.W.1. RunLength Encodings.

77. EE Trans. Inform. Theory IT, 12(Jul.l966), pp.399-401.49. Gaines B.R.

78. Behavior/structure transformations under uncertainty. Int.J.Man-Mach.Stud. 8,1976. pp.337-365.50. Lcmpel A., Ziv J.

79. On the complexity of finite sequences.

80. EE Trans.Inf.Theory IT-22, l(Jan,1976), pp.75-81.51. Gaines B.R.

81. System identification, approximation and complexity. Int.J.General Syst. 3,1977. pp.145-174.52. Ziv J., Lempel A.

82. A universal algorithm for sequential data compression.

83. EE Transactions on Information Theory, Vol.23, 3(May 1977),pi>.337-343.53. Ziv J., Lcmpel A.

84. Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, Vol.24, 5(Sept.l978), pp. 530-536. 51. Rubin F.

85. Arithmetic stream coding using fixed precision registers. IEEE Trans.Inf.Theory IT-25, 6(Nov.l979), pp.672-675.55. Witten I.H.

86. Approximate, non-deterministic modelling of behavior sequences. Int.J.General Systems 5(Jan.l979), pp.1-12.56. Burt P.J.

87. Tree and Pyramid Structures for Coding Hexagonally Sampled Binary Images.

88. CGIP(14), No. 3, 1980, pp. 271-280.57. Witten I.H.

89. Probabilistic behavior/structure transformations using transitive Moore models.1.t.J.General Syst. 6, 3(Mar.l980), pp. 129-137.

90. Rissanen J.J., Langdon G.G. Universal modeling and coding.

91. A note on the Ziv-Lempcl model for compressing individual sequences.

92. EE Trans.Inf.Theory IT-29, 2(Mar.l983), pp.284-287.

93. Langdon G.G., Rissanen J.J.

94. A doubly-adaptive file compression algorithms.

95. EE Trans.Commun. COM-31, 11 (Nov. 1983), pp. 1253-1255.

96. Ahmed N., Natrajan Т., Rao K.R. Discrete Cosine Transform.

97. EE Trans, on Computers, Vol.C-23, l(Dec.l984), pp.90-93. 61. Cleary J.G., Witten I.H.

98. A comparison of enuinerative and adaptive codes. IEEE Trans. Inf. Theory, IT-30, 2(Mar.l984), pp.306-315.65. Cleary J.G., Witten I.H.

99. Data compression using adaptive coding and partial string matching. IEEE Trans. Commun. COM-32, 4(Apr.l984), pp.396-402.

100. Cormack G.V., Horspool R.N. Algorithms for adaptive Huffman codes. Inf.Process.Lett. 18, 3(Mar.l984), pp.159-166.67. Langdon G.G.

101. An introduction to arithmetic coding. IBM J.Res.Dcv. 28, 2(Mar.l984), pp.135-149.68. Welch T.

102. A Technique for High-Performance Data Compression. IEEE Computer, Vol.17, 6(Jun.l984), pp.8-19.69. Knuth D.E.

103. Dynamic Huffman coding. J.Algorithms 6, 1985. pp. 163-180.

104. Bentley J.L., Sleator D.D., Tarjan R.E., Wei V.K. A locally adaptive data compression scheme. Corrmum. 29, 4(Apr.l986), pp.320-330.71. Cameron R.D.

105. Source encoding using syntactic information source model. LCCR Tech. Rept. 7,1986 Simon Eraser University.

106. Corinack G.V., Horspool R.N.

107. Data compression using dynamic Markov modelling. Comput.J. 30,6(Dec.l987), pp.541-550.73. Llewellyn J.A.

108. Data compression for a source with Markov characteristics. Comput.J. 30,2,1987. pp.149-156.74. Vitter J.S.

109. Design and analysis of dynamic Huffman codes. Л .ACM 34,4(Oct.l987), pp.825-845.

110. Witten I.H., Neal R., Cleary J.G. Arithmetic coding for data compression. Commun.ACM 30,6(Jun.l987), pp.520-540.76. Jones D.W.

111. Application of splay trees to data compression. Commun.ACM 31,8(Aug.l988), pp.996-1007.77. Moffat A.

112. A data structure for arithmetic encoding on large alphabets. In Proceeding of the 11th Australian Computer Science Conference. Brisbane, Australia (Feb.1988), pp.309-317.78. Moffat A.

113. A note on the PPM data compression algorithm.

114. Res.Rept.1988/7, Dept.of Computer Science, Univ.of Melbourne,1. Victoria, Australia.

115. Bell Т., Witten I.H., Cleary J.G. Modeling for text compression.

116. ACM Computing Surveys. Vol.21, No.4(Dec.l989), pp.557-591.80. Jacquin A.

117. Fractal image coding based on a theory of iterated con-tractive image transformations.

118. Visual Comm. and Image Processing, vol.SPIE-1360, 1990.81. Wallace G.K.

119. The JPEG still picture compression standard. Communication of ACM. Vol.34. N.4(Apr.l991)82. Gall D.Le.

120. Mpeg: A video compression standard for multimedia applications. Communications of the ACM, 34(4), 1991.83. Fisher Y.

121. Fractal image compression. SigGraph 92.84. Chui C.

122. An Introduction to Wavelets. Academic press, 1992.85. Daubechies I.

123. Ten Lectures on Wavelets. SI AM, 1992. 8G. Jacquin A.

124. Transactions on Image Processing. IEEE 1, 1992.

125. TIFF Specification, Revision 6.0, Final Aldus Corporation — June 3, 1992.88. Howard P.G., Vittcr J.S.

126. Fast and Efficient Lossless Image Compression.

127. EE Computer Society/NASA/CESDIS Data Compression

128. Conference, Snowbird, Utah, 1993, pp.351-360.

129. Pennebaker W.B., Mitchell J.L.

130. JPEG: Still Image Data Compression Standard. — International Thomson Computer Press, London, UK, 1993.90. Meyer Y.

131. Wavelets: Algorithms and Applications. SIAM, 1993.91. Bogdan A.

132. Multiscale (inter/intra-frame) fractal video coding.

133. Proceedings ICIP-94 (IEEE International Conference on Image

134. Processing), Austin, TX, USA, November 1994, vol.1, pp.760 764.92. Burrows M., Wheeler D.J.

135. A Block-sorting Lossless Data Compression Algorithm.

136. SRC Research Report 124, Digital Systems Research Center, Palo1. Alto, May 1994

137. Fisher Y., Shcn T.P., Rogovin D.

138. A comparison of fractal methods with DCT(JPEG) and wavelets(cpic).

139. SPIE Procedings, Neural and Stochastic Methods in Image and Signal Processing III, vol.230416, San Diego, CA, 1994.94. Fisher Y. editor.

140. Fractal Image Compression. Theory and Application. — Springer-Verlag, 1995.95. Boutell T. editor.

141. PNG (Portable Network Graphics) Specification. Version 1.0 W3C Recommendation, 1996.96. Nelson M.R.

142. Data Compression with the Burrows Wheeler Transform. Dr.Dobbs Journal, Sept.1996, pp.46-50.97. Schindler M.

143. A Fast Block-Sorting Algorithm for Lossless Data Compression. Proc. of Data Compression Conference (DCC97), Snowbird, Utah, Mar.1997, p.469.

144. Randers-Pehrson G. editor.

145. PNG (Portable Network Graphics) Specification. Version 1.2 W3C Recommendation, 1999.99. International Standard1.formation technology — JPEG 2000 image coding system — Part I: Core coding system ISO/IEC, 2000.100. Adams M.D., Kossentini F.

146. JasPer: A software-based JPEG-2000 codec implementation Proc. of IEEE International Conference on Image Processing, Vancouver, ВС, Canada, Oct. 2000.101. Adams M.D.

147. The JPEG-2000 Still Image Compression Standard

148. University of British Columbia, Vancouver, ВС, Canada Sep.2001.

149. Vasin Ju.G., Zherzdev S.V.1.terpolation in the hierarchical coding of images 6-th International conference "Pattern recognition and image analysis: new information technologies". Velikiy Novgorod, 2002. pp.230-233

150. Vasin Ju.G., Zherzdev S.V.1.terpolation in the Hierarchical Coding of Images

151. Pattern Recognition and Image Analysis, Vol.13, No.l, 2003. pp.179181

152. Vasin Yu.G., Zherzdev S.V.1.formation Techniques for Hierarchical linage Coding

153. Pattern Recognition and Image Analysis, Vol.13, No.3, 2003.pp.539—548.1. УТВЕРЖДАЮ»

154. Зам. начальника Главного управления юкеайЭс&афии и навигации МО РФ1. Б.С. Фридман2004 г.1. АКТо внедрении результатов диссертации на соискание ученой степени кандидата технических наук

155. Краткое описание и основные технические характеристики внедряемой продукции, отличительные черты, положительные качества и технико-экономические преимущества.

156. От ГУ «ПИИ ПМКННГУ Министерство образования и науки РФ» Руководг ;ель работ, директор1. Ю.Г. Васин2004 г.

157. От Главного управления океанографии и навигации МО РФ Начальник 280 ЦКП ВМФ капитан первого ранга1. В.Д. Фомченкоn&f^zr^yt? 2004 г.4