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

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

ЖЕРЗДЕВ Сергей Владимирович

РАЗРАБОТКА АЛГОРИТМОВ АДАПТИВНОГО СЖАТИЯ ВИДЕОИНФОРМАЦИИ НА ОСНОВЕ ИЕРАРХИЧЕСКИХ СТРУКТУР ДЛЯ ЗАДАЧ ОПЕРАТИВНОГО ОТОБРАЖЕНИЯ

Специальность: 05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Нижний Новгород. 2004

Работа выполнена в НИИ прикладной математики и кибернетики при Нижегородском государственном университете им. Н. И. Лобачевского.

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

профессор Ю.Г. Васин Официальные оппоненты: доктор технических наук,

профессор А.П. Немирко доктор технических наук, профессор В.И. Швецов Ведущая организация: Научный совет по комплексной

проблеме "Кибернетика" РАН (г. Москва)

Защита состоится » _2005 г. ъ/? *часов на засе-

дании диссертационного совета Д 212.166.13 Нижегородского государственного университета им. Н. И. Лобачесвкого по адресу: 603950, г. Нижний Новгород, пр. Гагарина, 23.

С диссертацией можно ознакомиться в научной библиотеке Нижегородского государственного университета им. Н. И. Лобачесвкого.

Автореферат разослан Л 2005 г.

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

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

кандидат физ.-мат наук, доцент ¿Ф _ * В.П. Савельев

з

Общая характеристика работы

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

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

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

Таким образом.

большие требования возникают

СИ БД ПОТЕКА

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В настоящее время разработано и реализовано большое число методов адаптивного сжатия видеоинформации: методы дифференциального кодирования, кодирование с преобразованием, фрактальные, аппроксимационные методы, иерархические и другие. Значительный вклад в развитие методов адаптивного сжатия внесли работы российских ученых А.С.Лебедева, Н.Н.Красильникова, Ю.М.Штарькова, В.А.Виттих, Ю.Г.Васина, В.В.Александрова, В.В.Сергеева и других, а также зарубежных ученых Дж.О.Лимба (Л.О.Limb), У.Претта (W.K.Pratt), Р.Грэхема (R.Graham), М.Куттта (M.Kunt), П.Берта (P.Burt), С.М.Кортмана (C.M.Kortman) и других.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПДЦ, проведено сравнительное исследование эффективности различных статистических моделей (статических и адаптивных) при кодировании видеоинформации различной природы.

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация полученных результатов Разработанная технология внедрена:

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

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

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

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

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

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

Результаты диссертационной работы докладывались и обсуждались на IV международной конференции "Связь 2001" (Владимир),

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

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

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы. Объем основного текста работы — 113 машинописных страниц. Список литературы включает 104 наименования.

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

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

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

• Позиционное и структурное представление данных

• Интерполяционное и статистическое моделирование

• Кодирование

Приведены основные требования, предъявляемые к технологии сжатия графических данных при решении задач ГИС и при передаче графической информации по каналам глобальных вычислительных сетей. Сделан вывод о необходимости развития технологий сжатия растровых изображений без потерь или с контролируемым по Чебы-шевской метрике уровнем искажений. Предложено строить технологию сжатия на основе иерархических структур и локальных однородных хорошо приспособленных базисных функций (ЛОХПБФ).

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

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

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

Для этого строится иерархическая последовательность изображений Рк, 0 < к < 2Ь. Положим Р2Ь = Р, т.е.

(1) рЦ 1<г,3<2Ь + 1

Изображения вышележащих уровней иерархии определим следующим образом

(2) р2*+1 = Р2г—1,] 1 1 < * < 2* + 1. 1 < 3 < + 1, 0 < к < Ь

(3) р2гк = р^, 1 < г < 2fc + 1, 1 < 3 < 2к + 1, 0 < к < Ь

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

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

Будем обозначать узел с номером г на уровне к двоичного дерева Л^, где 1 < к < 2Ь,1 < г < 2к~1. Тогда узел /V/ является корнем двоичного дерева, а сыновьями узла являются узлы и Л^г+1. При этом соответствие узлов двоичного дерева и отсчетов можно определить следующей рекурсивной конструкцией:

(4)

' к ' ЧеТНО' Ь>1 = 2 ^г ■ ' (Ра^'^М?) ' к " нечетн°> аг = 2

в остальных случаях

(5) «¿1) = (2,2)

(6) <<#_„ ЬЦХ) = <2(а^1-1),бГ1), 1<к<Ь

(7) <«#,#> = <2(в»"1-1)>^-1 + 1>, 1<к<Ь

(8) ¡Я?,1) = (а?,2(Ь?-1)),1<к<£,

О) = (<? + 1,2(^-1)), 1<к<Ь

,2к-1

2к—1

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

В другой интерпретации каждому узлу Л^ дерева соответствует некоторая прямоугольная область исходного изображения причем дочерним узлам и соответствуют области Л^А и £>2г+1 соответственно, полученные разбиением области пополам. Т.е. двоичное дерево задает рекурсивное разбиение исходного изображения

(10) $ =

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

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

Кроме перехода от дерева отсчетов к разностному дереву интерполяционное моделирование используется и при построении усеченного двоичного дерева (УДД). Таким образом, выявленные локальные

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

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

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

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

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

УДЦ.

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

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

Приведена методика для компрессии полноцветых изображений в различных цветовых пространствах (RGB, CMYK, YUV и др.).

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

• Унифицированная обработка как полутоновых, так и полноцветных изображений.

• Независимость алгоритма от количества цветовых слоев (размерности цветового пространства) в исходном изображении.

• Возможность независимого определения для каждого цветового слоя допустимой погрешности интерполяции и уровня детализации.

• Возможность независимого восстановления любого цветового слоя.

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

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

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

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

Предложен алгоритм построения статистической модели с маскировкой. При этом строится контекстно-независимая модель ¿?о, а для кодирования на каждом шаге по данным модели Ео и интерполированному значению х строится врёменная модель Ет(х). Модель Ет(х) является копией модели Ец, в которой зануляются (маскируются) счетчики для тех значений погрешности интерполяции, которые не могут быть получены для интерполированного значения х.

Так, например, при глубине представления отсчета Ь = 8 и текущем интерполированном значении отсчета р* ■ = 253 для значения ошибки интерполяции строго выполняется условие 6 [—253,2]. Оценка вероятности остальных значений в адекватной модели должна быть принята равной нулю.

В общем случае оценка вероятности символа щ из алфавита источника А в модели Ет(х) имеет вид

( п , и )р{аиЕ0), —х < а» < 26 — 1 — ж (11) р(аг,Ет{х)) = <

I 0, в остальных случаях

Такая модель обеспечивает несколько лучшие результаты, чем контекстно-независимая, и при этом требует гораздо меньших вычислительных ресурсов, чем контекстно-зависимая степени 1. Показано, что общее время работы модели Ет при кодировании и декодировании не превысит 0(к^ |Л|) и реализация модели Ет не требует дополнительных расходов памяти по сравнению с реализацией модели Ео.

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

<12> ^ = [к (13) М*; = тос! 256

При этом старшая часть А^ кодируется с применением адаптивной статистической модели^ а в отношении младшей ц^ принимается гипотеза о равномерном распределении вероятностей при А^ ф 0 или используется собственная адаптивная статистическая модель при

А*, = 0.

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

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

Для этого предлагается рассматривать в качестве контекста не само значение индексов существенных отсчетов, а их классы. Число таких классов ограничим некоторой величиной 7УСС и будем строить эти классы следующим образом. Если число различных индексов в изображении не превышает величины /Усс, каждый класс будет содержать строго один индекс. В противном случае первые Исс — 1

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

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

Для случая применения арифметического кодирования разработаны методы эффективной реализации адаптивных статистических моделей данных на основе алгоритма Рябко-Фионова1 с применением иерархических структур данных. Предложенные подходы позволили расширить область применения алгоритма на входные алфавиты относительно небольшой мощности. Практическая реализация показала преимущество в производительности от 1.2 до 5 раз по сравнению с использованием классического алгоритма при мощности входного алфавита порядка 26... 29.

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

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

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

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

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

Рис. 1. Схема иерархического сжатия

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

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

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

Рассмотренные методы были реализованы в виде библиотеки классов на языке С++. Библиотека содержит классы, которые реализуют алгоритмы кодирования/декодирования изображений различной природы и обеспечивают следующие возможности.

• Единый программный интерфейс для работы со всеми классами данных (кодирование/декодирование как изображений с

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

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

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

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

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

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

Рассмотрим эффективность предложенной библиотеки (FBTR) на примере сжатия полутонового аэрофотоснимка местности, закодированного с различными уровнями допустимой погрешности по сравнению с другими методами сжатия изображеиий. Исходная матрица имеет размеры 8192 х 8192 пиксель, объем 67 108 864 байт, значения отсчетов рассматриваются как целочисленные в диапазоне [0,255]. Для сравнения в таблице 1 представлены объемы файлов в форматах JPEG и PNG.

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

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

£ 0 2 4 10 20

PNG 40 063 210 — — — —

JPEG — 39 010 088 33 664 010 24 300 845 12 604 326

FBTR 36 162 352 17 805 144 12 645 194 5 353 198 1 644 523

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

Было проведено и сравнение предложенного алгоритма и алгоритмов JPEG и JPEG2000 применительно к фотографическим изображениям на примере общепринятого тестового изображения "Lena image".

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

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

Результаты для кодирования без потерь изображений с индексированием цвета рассмотрим на примере картографического изображения в разрешении 423 dpi (межточечный интервал 60 микрон). Характеристики исходного изображения: размер в пикселях — 5900 х 7251, размер атрибута пикселя в битах — 8, размер дампа

20 18 16 14 12 10 8 6 4 2 О

50

45

40

35 30 25

20 2 4 6 8 10 12 14 16 18 20

Рис. 2. Зависимость коэффициента сжатия от абсолютной ошибки и зависимость Р£>К11(с1Ь) от коэффициента сжатия для полутонового изображения

изображения в байтах — 42 780 900. Объемы выходных данных для различных форматов приведены в таблице 2.

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

FBTI

JPËG2000

JPEG

10 20 30 40 50 60

FBTR

ТАБЛИЦА 2. Эффективность различных алгоритмов при кодировании изображения с механизмом индексации цвета

Формат С1Р Р^ ГВТ11

Объем файла 6 503 903 5 579 535 3 670 506

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Список публикаций по теме диссертации

1. Васин Ю.Г., Жерздев C.B.

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

2. Васин Ю.Г., Жерздев C.B.

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

3. Васин Ю.Г., Жерздев C.B.

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

4. Васин Ю.Г., Жерздев C.B.

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

5. Жерздев C.B.

Практическая реализация адаптивной статистической модели с

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

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

7. Васин Ю.Г., Жерздев С.В.

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

8. Васин Ю.Г., Жерздев С.В.

Учебная программа по технологии организации мультимедийных данных ГИС // Труды 7-й конференции "Методы и средства обработки сложной графической информации". Н.Новгород, 2003. С.32-33.

9. Vasin Ju.G., Zherzdev S.V.

Interpolation in the hierarchical coding of images // 6-th International conference "Pattern recognition and image analysis: new information technologies". Velikiy Novgorod, 2002. pp.230-233

10. Vasin Ju.G., Zherzdev S.V.

Interpolation in the Hierarchical Coding of Images // Pattern Recognition and Image Analysis, Vol.13, No.l, 2003. pp.179-181

11. Vasin Yu.G., Zherzdev S.V.

Information Techniques for Hierarchical Image Coding // Pattern Recognition and Image Analysis, Vol.13, No.3, 2003. pp.539-548.

»-19 63

РНБ Русский фонд

2005-4 47315

Подписано в печать 21.01.05. Формат 60 х 84 '/16. Бумага офсетная. Печать офсетная. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 24.

Нижегородский государственный технический университет. Типография НГТУ. 603600, Нижний Новгород, ул. Минина, 24.

Аннотация

Вводенис

В.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. Программное обеспечение

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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