Бесплатный автореферат и диссертация по наукам о земле на тему

Исследование и разработка методов сжатия геоданных для передачи по каналам связи в глобальные сети

ВАК РФ 25.00.35, Геоинформатика

Автореферат диссертации по теме "Исследование и разработка методов сжатия геоданных для передачи по каналам связи в глобальные сети"

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

Букин Роман Николаевич

Исследование и разработка методов сжатия геоданных для передачи по каналам связи в глобальные сети

Специальность 25.00.35 - "Геоинформатика"

Автореферат

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

Москва - 2004 1

Работа выполнена в Московском государственном университете геодезии и картографии

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

доцент Гаврилова В.В.

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

профессор Майоров А.А.,

кандидат технических наук, доцент Цибулькин Л.М.

Ведущая организация: Таганрогский Государственный

Радиотехнический Университет

Защита состоится ¿С декс.Гря 2004 года, В I-"часов назаседании диссертационного совета' Д 212.143.03 при Московском государственном университете геодезии и картографии по адресу: 105064 Москва, Гороховский пер., д. 4, ауд. 321.

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

Автореферат разослан «_»_2004 г.

Ученый секретарь диссертационного совета

lU.ii.jC*___ Климков Ю.М.

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

Актуальность работы

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

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

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

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

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

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

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

Цель диссертационной работы

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

Задачи работы

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

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

2. Исследование эффективности современных методов сжатия применительно к различным фрагментам аэрокосмических снимков.

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

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

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

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

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

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

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

2. разработан метод сжатия аэрокосмических изображений на основе дискретного преобразования Крестенсона-Леви и последующего адаптивного арифметического кодирования.

3. выполнена программная реализация разработанного метода сжатия.

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

Апробация работы

По теме диссертации были сделаны доклады на УП-й Международной научно-технической конференции ОЕОШРОСАО 2003 (Вена, Австрия, 2003) и Международной научно-технической конференции, посвященной 225-летию МИИГАиК (Москва, 2004).

Публикации

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

Объем и структура работы

Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа изложена на 158 страницах, включая 12 рисунков, 10 таблиц и 6 графиков и 1 приложение. Список

используемой литературы включает 98 наименований, в том числе 46 на иностранном языке.

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

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

Алгоритм Коэффициенты сжатия Симметричность по времени Потери Размерность

Групповое кодирование 1/32 1/2 2/1 1 Нет 1D

Метод LZW 1/1001/47/5 1.2-3 Нет 1D

Метод Хаффмана 1/8 2/3 1/1 1-1.5 Нет 1D

Lossless JPEG 1/20 1/2 1/1 ~1 Нет 2D

Рекурсивное Сжатие 2-20 раз 1.5 Да 2D

Метод JPEG 2-200 раз ~1 Да 2D

Фрактальный метод 2-2000 раз 1000-10000 Да 2D

Таблица 1. Основные характеристики методов сжатия.

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

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

На основе проведенного в главе анализа сделаны следующие выводы:

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

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

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

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

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

В предположении изотропности (равенство коэффициентов межстрочной и межстолбцовой корреляции свойств

непрерывного изображения и одинаковых шагов дискретизации модель дискретного изображения матрицы после нормализации имеет

вид:

где Е(Х)- математическое ожидание, Б(Х) - дисперсия, г - коэффициент межэлементной корреляции.

Прямое и обратное ДПКЛ в двумерном случае (когда X, У представляют собой матрицы из N строк и М столбцов) определены соответственно:

функций Крестенсона-Леви, определенная на промежутке ХЕ[0,1 ) В нумерации Пэли, а

Математические ожидания и среднеквадратичные значения модулей элементов матрицы Y, полученной из матрицы исходного изображения X в результате ДПКЛ:

тц =£М=0- =е2{рЛ1,р\р')=о2к{р")-af {pr} где

Р 0 m=0

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

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

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

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

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

статистического

кодирования

полученных

спектральных

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

дискретном преобразовании Y = —!—W(„)-Х. Матрица W(„)

представляется в виде произведения слабо заполненных матриц

меньшей размерности: W(n) = -w'2' -...■ W<JT1) • W,'"' , где

О

(на диагонали матрицы

V

размерности находятся матриц размера

р^хр"'1, остальные элементы матрицы - нулевые). Матрица

={6/*} а,к=0,1,...,р"-1) и имеет следующую структуру:

и _S14P] .„ЛЯ, °j,k ~ jmoûp"' Я

где q=exp(-2m/p), SJ

1, при m = j О, при mïj

. (символ Кронекера).

ъ ¡0>

шшш шы

ЩШг

г

И"

■^-■тгг.г;

•Е

1» 0.0)

10.9,1 )

го о и

10.1.01

[0 1.11

ю 1.21

11 0.0)

11.0.11

|| 0.11

II 1.01

11.1.11

|| 1.21

|| 2.01

II 2.11

Л» ' <

г, - V

..у Ч

.,»..• V.."

м

Рисунок I. Рекурсивный принцип построения алгоритма ДПКЛ с неполным вычислением (указаны только самые крупные блоки) У = У-^р"

Условные обозначения: - блоки, содержащие только

вещественные элементы

- вычисление и действительных и мнимых компонент

• невычисляемые блоки

• вычисление только действительных компонент

«»я;

еиие:

• а * Ь * с

• а * Ь^ *-счг 9 + Ь<1 ' » су

неполно« *ы числен ие: а • Пел а + Ь* с « Нев^НсД + Нес

»—У а + Ь<1*счг с-Кес а <> Ьу' * сц ••

Рисунок 2. Граф 9-ти точечного ДПКЛ с неполным вычислением ^=ехр(-2ти/3))

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

В предлагаемом методе сжатия спектр ДПКЛ каждого фрагмента обрабатывается более сложным способом, в основе которого лежит алгоритм адаптивного арифметического кодирования.

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

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

Рисунок 3. СХема разработанною метода сжатия геоизображений.

1. Разбиение исходного изображения на матрицы-фрагменты размера 9x9 пикселов; формирование потока матриц-фрагментов осуществляется «считыванием по зигзагу» (рисунок 4).

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

Зигзагообразное считывание целесообразно применять для того, чтобы по возможности исключить резкие скачки постоянной составляющей яркости в потоке матриц-фрагментов и тем самым повысить эффективность использования дифференциальной импульсно-кодовой модуляции (ДИКМ) для постоянной составляющей спектра Д11КЛ (первый элемент при считывании).

' 2. Вычисление ДПКЛ по алгоритму с неполным вычислением в базисе Переход в базис позволяет значительно

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

3. Перевод в ортогональный комплексный базис (1,-/) и квантование.

4. Адаптивное арифметическое кодирование полученного потока данных.

Обратный процесс восстановления изображения имеет вид:

1. Декодирование полученного из файла потока данных.

2. Перевод в базис с масштабированием (коэффициент масштабирования хранится в заголовке файла).

3. Вычисление "ненормированного" ОДГОСЛ по алгоритму с неполным вычислением в базисе

4. Формирование восстановленного изображения зигзагообразной записью фрагментов.

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

предлагаемый метод сжатия выигрывает по данному параметру у метода JPEG (таблицы 2 и 3).

Вычисление дискретного преобразования Квантование спектров Удаление нулей (нулевых областей) Статистическое кодирование Всего

Метод JPEG =22 »11 незначительна незначительно »33

Схема с ДПКЛ »9 »12 незначительно «б »27

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

Статистическое декодирование Восстановление нулей (нулевых областей) Деквантова-ние спектров Вычисление обратного преобразования Всего

Метод JPEG незначительно незначительно »6 »24 »30

Схема с ДПКЛ »10 незначительно »7 »11 »28

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

Глава 4. Экспериментальные исследования эффективности сжатия аэрокосмических изображений при применении разработанного метода сжатия на основе дискретного преобразования Крестенсона-Леви

В четвертой главе производится выбор фрагментов аэрокосмических снимков на основе визуальных признаков, причем исследования статистических параметров данных фрагментов показали соответствие предложенной классификации и диапазонам значений выборочного среднеквадратичного отклонения значений цветов пикселов изображений. По результатам данной классификации выделяются классы фрагментов аэрокосмических снимков, условно получивших названия: «Город» (области антропогенного типа, характеризуется высоким количеством мелких деталей и линий, и малым количеством сильных контрастных переходов, рисунок 5), «Лес» (лесные массивы - достаточно плавные цветовые переходы, практически отсутствуют мелкие детали и контрастные цветовые переходы, рисунок 6), «Река» (очень частые и высокие контрастные цветовые переходы, рисунок 7).

Рисунок 5. Фрагмент «Город №2» Рисунок б.Фрагмент «Лес №2» Рисунок 7.Фрагмент «Река№1»

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

На основе проведенных исследований сделаны выводы о том, что: • Использование современных методов сжатия изображений без потери информации для геоизображений малоэффективно по причине низкого коэффициента сжатия - в среднем 1.1 - 1.4 от объема исходного изображения.

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

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

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

0.080 0.070 0.060 (о 0.050 4 s 0.040 4 2 0.030 0.020 0.010 0.000

Коэффиценты RMS

у I* ■> 'э * % "к .У

Изображения

а jpg (2)

■ jpg (6) □ jpg (11)

График 2. Коэффициенты среднеквадратичного отклонения значений пикселов (RMS) для методов JPG с параметрами сжатия 2, б и 11 по 12 бальной шкале качества.

— Прямое сжатие

— SEM М=2, Е=6 —SEM М=4, Е=4

— SEM М=6, Е=2

— LPC

— CMZ&SEM4+4

N'V'bNN'V'bfcN'V'bb ^ ^ ^/////////

График 3. Коэффициенты сжатия фрагментов аэрокосмических изображений после предобработки методами разделения мантисс и экспонент (SEM) с различными параметрами длины мантиссы и экспоненты, методом линейно-предсказывающего кодирования (LPC) и методом замены наиболее часто встречающихся символов на наименьшие значения с последующим применением метода разделения мантисс и экспонент с параметрами Е-4 и М=4 (CMZ & SEM 4+4).

Далее в главе описаны результаты проведенных автором экспериментов по обработке фрагментов геоизображений при использовании разработанного метода сжатия на основе дискретного преобразования Крестенсона-Леви и метода JPEG (график 4), сравнивается качество восстановленных изображений. Для проведения экспериментальных данных были зафиксированы два значения шага квантования, условно названных «высокое качество» и «низкое качество». По результатам сравнения нового метода со стандартом JPEG делается вывод о том, что для обработки аэрокосмических снимков предложенная схема выигрывает у метода JPEG в коэффициенте сжатия при схожих значениях потери информации.

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

Заключение

Выполненные в ходе работы исследования позволяют сформулировать следующие основные результаты:

1. Использование современных методов сжатия изображений без потери информации для геоизображений малоэффективно по причине низкого коэффициента сжатия - в среднем 1.1 - 1.4 от объема исходного изображения.

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

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

4. Наилучших результатов новый разработанный метод сжатия достигает на изображениях с низким выборочным среднеквадратичным отклонением значений цветов пикселов. В большей степени этому условию соответствуют изображения лесных массивов и некоторые изображения антропогенных территорий. На данных изображениях преимущество разработанного метода сжатия над методом JPEG достигает от 10 до 25%, от объема сжатого изображения. На изображениях с максимальными значениями выборочного среднеквадратичного отклонения (им наиболее всего соответствуют изображения рек) предлагаемый метод сжатия также дает результаты, превосходящие результаты работы метода JPEG на несколько процентов. Максимальные значения коэффициентов сжатия нового разработанного метода, достигнутые в результате проведенных экспериментальных исследований, составили 6, при сжатия с достаточно высоким уровнем качества, и 10 при среднем уровне качества. Средние

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

Список опубликованных работ по теме диссертации

1. Букин Р.Н., Журкин И.Г. Алгоритмы сжатия растровых изображений и соответствующие им графические форматы. Тенденции развития. //Деп. В ОНТИ ЦНИИГАиК, 19.11.2002, №780-гд, 2002.

2. Букин Р.Н., Гаврилова В.В. Исследования эффективности современных методов сжатия геоданных для передачи по каналам связи в глобальные сети. // VII Международная научно-практическая конференция GEOINFOCAD 2003, Вена, Австрия, тез. докл., М: МИИГАиК, 2003, - Стр.42-45.

3. Букин Р.Н., Гаврилова В.В. Исследование методов построения_

новых алгоритмов эффективного кодирования аэрокосмических изображений // Международная научно-практическая конференция, посвященная 225-летию МИИГАиК, тез. докл., М: МИИГАиК, 2004, - стр. 61-71.

4. Букин Р.Н., Гаврилова В.В. Исследования эффективности современных методов сжатия аэрокосмических снимков. // Известия высших учебных заведений. Геодезия и аэрофотосъемка №2 2004, М: МИИГАиК, 2004, - Стр. 96-103.

5. Букин Р.Н., Гаврилова В.В. Исследования эффективности методов предварительного преобразования геоизображений с целью увеличения степени сжатия данных. // Известия высших учебных заведений. Геодезия и аэрофотосъемка №2 2004, М: МИИГАиК, 2004,-Стр. 104-108.

6. Букин Р.Н. Разработка метода сжатия аэрокосмических изображений с использованием дискретного преобразования Крестенсона-Леви // Международная научно-практическая конференция, посвященная 225-летию МИИГАиК, тез. докл., М: МИИГАиК, 2004, - стр. 71-83.

Поди, к печати 17.11.2004 Формат 60x90/16 Бумага офсетная Печ. л. 1,5 Уч.-изд. л. 1,5 Тираж экз.80 Заказ № 205 Цена договорная

МГУГиК

103064, Москва К-64, Гороховский пер., 4

Содержание диссертации, кандидата технических наук, Букин, Роман Николаевич

Введение.

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

1.1 Основные понятия.

1.2 Особенности методов сжатия.

1.3 Методы сжатия без потери информации.

1.3.1 Метод группового кодирования (RLE).

1.3.2 Метод сжатия LZW.

1.3.3 Метод Хаффмана.

1.3.4 Метод Шеннона-Фано.

1.3.5 Арифметический метод.

1.3.6 Метод Loseless JPEG.

1.4 Алгоритмы сжатия с потерями.

1.4.1 Рекурсивное сжатие.

1.4.2 Метод сжатия JPEG.

1.4.3 Фрактальное сжатие.

1.5 Сравнительные характеристики методов сжатия.

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

1.6.1 Формат GIF.

1.6.2 Формат PNG.

1.6.3 Формат TIFF.

1.6.4 Формат Adobe Photoshop Document.

1.6.5 Формат BMP.

Выводы.

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

2.1 Модель дискретного изображения.

2.2 Вероятностные оценки спектральных характеристик дискретных преобразований: Фурье, косинусного и Крестенсона-Леви.

2.2.1 Дискретное преобразование Фурье (ДПФ).

2.2.2 Дискретное косинусное преобразование (ДКП).

2.2.3 Дискретное преобразование Крестенсона-Леви (ДПКЛ).

2.3 Свойства избыточности спектров дискретных преобразований Фурье н Крестенсона-Леви вещественных сигналов.

2.4 Теоретические оценки затрат при кодировании изображений с использованием дискретных преобразований: Фурье, косинусного и Крестенсона-Леви.

Выводы.

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

3.1 Общая методика построения методов сжатия растровых изображений.

3.2 Быстрые алгоритмы вычисления дискретного преобразования Крестенсона-Леви.

3.3 Сжатие изображений при помощи квантования и кодирования спектров дискретного преобразования Крестенсона-Леви.

3.4 Алгоритм адаптивного арифметического кодирования данных.

3.5 Оценка временных вычислительных затрат.

Выводы.

Глава 4. Экспериментальные исследования эффективности сжатия аэрокосмических изображений при применении разработанного метода сжатия на основе дискретного преобразования Крестенсона-Леви.

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

4.2 Исследование эффективности современных методов сжатия, применительно к аэрокосмическим снимкам.

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

4.4 Эффективность применения разработанного метода сжатия на основе дискретного преобразования Крестенсона-Леви.

4.5 Зависимость коэффициентов сжатия при применении разработанного метода на основе дискретного преобразования Крестенсона-Леви от статистических параметров изображений.

Выводы.

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

Современное развитие геоинформационных технологий неуклонно ведет к увеличению объемов накапливаемых и обрабатываемых геоданных, передаваемых преимущественно по различным каналам связи. В настоящее время наиболее используемым и перспективным каналом связи является глобальная компьютерная сеть Интернет. В 2003 году исполнилось 35 лет с момента ее зарождения. Идея возникла в конце 50-х годов, когда в США была поставлена задача создать сеть телекоммуникации. И в 1968 году был составлен план развития сети электронно-связанных компьютеров АРПАНЕТ (прообраз Интернета) для оповещения о возможной ядерной атаке, а спустя год вступил в действие первый компьютер, предоставляющий клиентам услуги по телекоммуникации. Через три года сеть охватила уже 34 компьютера, размещенных в разных концах страны, а к 1983 году через АРПАНЕТ были соединены более 400 больших компьютеров. Вскоре АРПАНЕТ разделилась на две сети: несекретную военно-промышленную и научно-исследовательскую. Вместе они назывались АРПАИНТЕРНЕТ и включали несколько тысяч серверов.

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

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

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

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

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

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

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

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

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

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

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

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

2. Исследование эффективности современных методов сжатия применительно к различным фрагментам аэрокосмических снимков.

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

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

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

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

Диссертационная работа состоит из четырех глав.

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

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

В третьей главе рассмотрены существующие быстрые алгоритмы ДПКЛ: алгоритм ДПКЛ с прореживанием по времени, алгоритм ДПКЛ с неполным вычислением. Далее в главе рассматривается предлагаемый в диссертации метод сжатия геоизображений на основе ДПКЛ. Из метода сжатия H>EG была заимствована общая схема метода, заключающаяся в разбиении исходного изображения на фрагменты, выполнении с каждым фрагментом дискретного преобразования, квантовании и статистического кодирования полученных спектральных коэффициентов. На этапе дискретного преобразования фрагментов изображения вместо дискретного косинусного преобразования (ДКП) в исходном методе .IPEG, предлагается применить ДПКЛ (алгоритм с неполным вычислением), что влечет коренные изменения в алгоритмах и способах реализации квантования и статистического кодирования спектров. В предлагаемом методе сжатия спектр ДПКЛ каждого фрагмента обрабатывается более сложным способом, в основе которого лежит алгоритм адаптивного арифметического кодирования. Данное изменение в сторону усложнения способа обработки спектра ДПКЛ оказалось возможным, благодаря значительному выигрышу во времени вычислений, который дает на этапе выполнения преобразования применение алгоритма ДПКЛ с неполным вычислением вместо быстрого алгоритма ДКП. Теоретическая оценка вычислительных затрат на сжатие-восстановление геоизображений позволяет сделать вывод, что предлагаемый метод сжатия выигрывает по данному параметру у метода JPEG.

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

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

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

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

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

• разработанный метод сжатия аэрокосмических изображений на основе дискретного преобразования Крестенсона-Леви и последующего адаптивного арифметического кодирования

• программная реализация разработанного метода сжатия.

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

Основные результаты, изложенные в диссертации, опубликованы в 6 работах автора [3-8].

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Общий объем работы составляет 158 страниц текста. Список литературы содержит 98 наименований, из них 46 иностранная литература.

Заключение Диссертация по теме "Геоинформатика", Букин, Роман Николаевич

Выводы

На основе изложенного в данного главе, можно сделать следующие выводы:

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

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

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

• Наилучших результатов новый разработанный метод сжатия достигает на изображениях с низким выборочным среднеквадратичным отклонением значений цветов пикселов. В нашей классификации, этому условию соответствуют изображения из группы «лес» и некоторые изображения класса «город». На данных изображениях преимущество разработанного метода сжатия над методом .FPEG достигает от 10 до 25%, от объема сжатого изображения. На изображениях класса «реки» с максимальными значениями выборочного среднеквадратичного отклонения предлагаемый метод сжатия дает результаты, превосходящие результаты работы метода n*EG, в среднем, на 2-3%.

Максимальные значения коэффициентов сжатия нового разработанного метода, достигнутые в результате проведенных исследований, составили 6,06 при сжатии с достаточно высоким уровнем качества и 10,08 при среднем уровне качества. Средние значения коэффициентов сжатия составили 3,87 и 6,1 соответственно, что является достаточно высокими показателями.

Заключение

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

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

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

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

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

Проведенные экспериментальные исследования показали:

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

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

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

• Наилучших результатов новый разработанный метод сжатия достигает на изображениях с низким выборочным среднеквадратичным отклонением значений цветов пикселов. В большей степени этому условию соответствуют изображения лесных массивов и некоторые изображения антропогенных территорий. На данных изображениях преимущество разработанного метода сжатия над методом JPEG достигает от 10 до 25%, от объема сжатого изображения. На изображениях с максимальными значениями выборочного среднеквадратичного отклонения (им наиболее всего соответствуют изображения рек) предлагаемый метод сжатия также дает результаты, превосходящие результаты работы метода JPEG, в среднем, на несколько процентов.

Максимальные значения коэффициентов сжатия нового разработанного метода, достигнутые в результате проведенных экспериментальных исследований, составили 6, при сжатия с достаточно высоким уровнем качества, и 10 при среднем уровне качества. Средние значения коэффициентов сжатия составили 3,87 и 6,1 соответственно, что является высокими показателями сжатия и позволяет существенно понизить время на передачу данных геоизображений по каналам связи в глобальные сети.

Библиография Диссертация по наукам о земле, кандидата технических наук, Букин, Роман Николаевич, Москва

1. Абламейко С.В., Лагуновский Д.М. Обработка изображений: технология, методы, применение. - Минск: Ин-т техн. кибернетики НАН Беларуси, 1999.

2. Бондаренко В.А., Дольников В.Л. Фрактальное сжатие изображений по Барнсли-Слоану // Автоматика и телемеханика. -1994.-№5.-С. 12-20.

3. Букин Р.Н., Журкин И.Г. Алгоритмы сжатия растровых изображений и соответствующие им графические форматы. Тенденции развития. // Деп. В ОНТИ ЩШИГАиК, 19.11.2002, №780-гд, 2002.

4. Букин Р.Н., Гаврилова В.В. Исследование методов построения новых алгоритмов эффективного кодирования аэрокосмических изображений // Международная научно-техническая конференция, посвященная 225-летию МИИГАиК, тез. докл., М: МИИГАиК, 2004,-стр. 61-71.

5. Букин Р.Н., Гаврилова В.В. Исследования эффективности современных методов сжатия аэрокосмических снимков. // Известия вузов. Геодезия и аэрофотосъемка №2 2004, М: МИИГАиК, 2004, Стр. 96-103.

6. Букин Р.Н., Гаврилова В.В. Исследования эффективности методов предварительного преобразования геоизображений с целью увеличения степени сжатия данных. // Известия вузов. Геодезия и аэрофотосъемка №2 2004, М: МИИГАиК, 2004, Стр. 104-108.

7. Букин Р.Н. Разработка метода сжатия аэрокосмических изображений с использованием дискретного преобразования Крестенсона-Леви // Международная научно-техническая конференция, посвященная 225-летию МИИГАиК, тез. докл., М: МИИГАиК, 2004, стр. 71-83.

8. Буяновский Г. Ассоциативное кодирование // Монитор, 1994 №8. с. 10-22.

9. Ю.Ватолин Д. Сжатие статических изображений // Открытые системы сегодня. Номер 8 (29) Апрель 1995.11 .Ватолин Д., MPEG стандарт ISO на видео в системах мультимедиа, «Открытые системы», №3, 1999.

10. Ватолин Д., Тенденции развития алгоритмов сжатия статических растровых изображений, «Открытые системы», №2, 2001.

11. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. -М.: Диалог-МИФИ, 2002. 384 с.

12. Вельч Т., Технология высокоэффективного сжатия данных. «1ЕЕЕ Компьютинг», №6, 1993.

13. Венцель Е.С. Теория вероятностей: Учеб. для вузов. 5-е изд. стер. - М.:Высш. шк., 1998. - 576 е.: ил.

14. Виттен И., Нил Р., Клири Д., Арифметическое кодирование при сжатии данных. «Communication of the АСМ», №6, 1997.

15. Гмурман В. Е., Теория вероятностей и математическая статистика. Учеб. пособие для вузов. Изд. 7-е, стер. М.: Высш. шк., 1999. -479 е.: ил.

16. Голд Б., Рейдер Ч. Цифровая обработка сигналов: Пер. с англ. М.: Сов. радио, 1973. - 368 с.

17. Голубов Б.И., Ефимов А.В., Скворцов В.А. Ряды и преобразования Уолша: Теория и применения. М.: Наука, 1987. - 344 с.

18. Горлов С.К., Корыстин А.В., Родин В.А. Об одной реализации метода сжатия отображений с помощью нелинейной аппроксимации сумм Фурье-Хаара // Теор. функций и прибл.: Тр. 7-й Саратов, зим. шк. (1994 г.). Ч. 2.- Саратов: Изд.-во СГУ, 1995.

19. Джайн А.К. Сжатие видеоинформации: Обзор // ТИИЭР. -1981. -Т.69. №3. - С. 71-117.

20. Дубров A.M., Мхитарян B.C., Трошин Л.И., Многомерные статистические методы: Учебник. М.: Финансы и статистика, 1998.-352 е.: ил.

21. Климов А.С. Форматы графических файлов // С.-Петербург, Изд. "ДиаСофт" 1995.

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

23. Кунт М., Икономопулос А., Кошер М. Методы кодирования изображений второго поколения // ТИИЭР. 1985. -Т.73. - №4. - С. 59-86.

24. Лисовец Ю.П., Поспелов А.С. Мультипликативные голографические преобразования для обработки изображений // Методы цифровой обработки изображений: Сб. науч. тр. МИЭТ. -М.: МИЭТ, 1982 С. 100-109.

25. Маккол Р., Мартин Г. Сжатие цветных изображений используя кластерный анализ и гистограммы. Технологии электроники и коммуникаций, №2, 1989.

26. Мастрюков Д. Алгоритмы сжатия информации. Часть 2. Арифметическое кодирование // Монитор. 1994. -№1. - С. 20-26.

27. Новиков И.Я., Стечкин С.Б. Основы конструкции всплесков. Фундаментальная и прикладная математика. 1997. 3, 4 с. 999-1028.

28. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток: Пер. с англ. М.: Радио и связь, 1985. - 248 с.

29. Пеев Е., Боянов К., Белчева О. Методи и средства за компрессия на изображения. Автоматика и информатика.-1994.-28, №3.-с.3-14.

30. Применения цифровой обработки сигналов: Пер. с англ. Под ред. Э.Оппенгейма. М: Мир, 1980. - 552 с.

31. Прэтт У. Цифровая обработка изображений: Пер. с англ. М.: Мир, 1982. Кн. 1 и 2. - 312 и 480 с.

32. Прэтт У., Кэйн Д., Эндрюс X. Кодирование изображений посредством преобразования Адамара. ТИИЭР. 1969. - Т. 5 7. -№1. - С. 66-77.

33. Разработка теории и алгоритмов по объектно-ориентированному кодированию аэрокосмических и картографических изображений. МИИГАиК, 1999.

34. Разработка теории, алгоритмов и архитектуры цифровых систем распознавания аэрокосмических и геодезических объектов местности. МИИГАиК, 1999.

35. Романов В.Ю. Популярные форматы файлов для хранения графических изображений на IBM PC.- М.:Унитех, 1992.

36. Сван Т . Форматы файлов Windows // М. "Бином", 1995.

37. Смит Б., Роув JI. Алгоритмы обработки сжимаемых изображений. Компьютерная графика. №9 1998.

38. Трахтман В.А. Спектральный анализ в базисе функций Виленкина-Крестенсона // Радиотехника и электроника. 1975. - Т. 20. - №1. - С.130-138.

39. Тюрин Ю.Н., Макаров А.А. Анализ данных на компьютере / Под ред. В.Э. Фигурнова. 3-е изд., перераб. и доп. - М.: ИНФРА-М, 2003. - 544 е., ил.

40. Умняшкин С.В. Особенности использования дискретного преобразования Крестенсона-Леви при обработке вещественных массивов // Микроэлектроника и информатика: Тез. докл. межвуз. науч.-тех. конф. 12-14 апр. 1995 г. М.: МГИЭТ (ТУ). - С. 188-189.

41. Умняшкин С.В. Оценка дисперсии элементов спектра дискретного косинусного преобразования марковского процесса первого порядка // Междунар. конф. по теор. прибл. функ., поев, памяти проф. П.П.Коровкина (Калуга, 26-29 июня 1996 г.).- Т.2.- С. 217218.

42. Уоллонс Г. «Стандарт графического сжатия n>EG». Communication of ACM, №4, 2000.

43. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. М.: Триумф, 2003. 320 с.

44. Фишер Й., «Фрактальное сжатия изображений», Сиггарх, 95.

45. Хармут X. Теория секвентного анализа. Основы и применения: Пер. с англ. М.: Мир, 1980. - 574 с.

46. Шавенько Н.К., Мощиль В.И. Основы теории кодирования и передачи информации. Учебное пособие М.: Изд. МИИГАиК, 1999.-47 с.

47. Яблонский С.В. Введение в дискретную математику. // М. "Наука", 1986. Раздел "Теория кодирования".

48. Ярославский Л.П. Цифровая обработка сигналов в оптике и голографии. Введение в цифровую оптику. М.: Радио и связь. -1987.-296 с.

49. Aberg J., Shtarkov Yu.M., Smeets B.J.M. Multialphabet coding with separate alphabet description, // Proc. of Compression and Complexity of Sequences 97, Positano, Salerno, Italy, IEEE Сотр. Soc. Press, 1998. P. 56-65.

50. Adams M. D., The JPEG-2000 Still Image Compression Standard , ISCMEC JTC 1/SC 29/WG 1 N 2412, Sept 2001.

51. Anderson J.B., Huang T.S. Piecewise Fourier transformation for picture bandwidth compression // IEEE Trans. Commun. -1972.- V. COM-20 №3. - P.488-491.

52. Antoni M. et al. Image coding using wavelet transform // IEEE Trans. Image Proc. 1992. -V.l. -№>2. - P. 205-220.

53. Arnavut Z., Magliveras S.S. Block sorting and data compression // Proc. IEEE Data Compression Conference, Snowbird, Utah. 1997. -P. 181-190.

54. Beaumont J.M. Image data compression using fractal techniques // ВТ Technological Journal. 1991. - V. 9 - №4. - P. 92-109.

55. Brent R.P. A linear algorithm for data compression // Aust. Computer J. 1987. - Vol. 19, N2. - P. 64-68.

56. Buhman J., Kunel H Vector quantization with complexity costs // IEEE Trans, on Information Theory. 1993. -V.39. - №4. - P. 11331145.

57. Burrows M., Wheeler D.J. A block-sorting lossless data compression algorithm. Palo Alto, 1994. - (Tech. Rep. / DEC Systems Research Center, N 124).

58. Cho N., Lee S. Fast algorithm and implementation of 2-D discrete cosine transform // IEEE Trans. Circuits and Systems. 1991. -V.38. -P.297-305.

59. Connell J.B. A Huffman-Shannon-Fano code // Proc. IEEE. 1973. -Vol. 61,N7.-P. 1046-1047.

60. Cosman P.C. et al. Using vector quantization for image processing // Proc. IEEE. 1993. - V.81. -№9. p. 1326-1341.

61. Cooley J.W., Tukey J.W. An algorithm for machine computation of complex Fourier series // Mach. Comput. 1965. - V. 19. - P. 297-301.

62. Digital image processing / Collect.: Chellappa R. Los Alamitos (Ca) et al.: IEEE computer soc. press, 1992. - IX, 801 p.

63. Dreizhen H. Comments on 'Data compression using static Huffman code-decode tables' // Communs. ACM. 1996. - Vol.29, N 2. - P. 149150.

64. Efimov A.V. Multiplicative function systems and their applications in discrete information processing // Approximation and function spaces/ Banach center publications. 1989. - V.22. - P. 111-117.

65. Eliott D.F., Rao K.R. Fast transforms: algorithms, analyses, applications. London: Academic Press inc., 1982. - 488 p.

66. Gopinath R.A., Burrus C.S. On cosine-modulated wavelet orthogonal bases // IEEE Trans. Image Proc. 1995. -V.4. -№2. - P. 162-177.

67. Gray R.M. Vector Quantization // IEEE ASSP Magazine. April 1984. - P. 4-29.

68. Hauque M.A. A two-dimensional fast cosine transform // IEEE Trans. ASSP. -1985. V. 33. - №6. - P.1532-1538.

69. Huffman D.A., "A method for the construction of minimum redundancy codes." In processing. IRE vol.40, 1962, P. 1098-1101.

70. Hung A.C. Image compression: the emerging standard for color images //IEEE Computing Futures. 1989. - Inagural issue. - P. 20-29.

71. Huang C.-M. et al. Fast full search equivalent encoding algorithms for image compression using vector quantization // IEEE Trans. Image Proc. 1992. -V.l. -№3. - P. 413-416.

72. Jacquin A., "Fractal image coding based on a theory of iterated contractive image transformations", Visual Comm. and Image Processing, v. SPIE-1360,1990.

73. Kurosaki M., Waki H. A JPEG-compliant colorimage compression/decompresssion LSI // Mitshubisi Elec. Adv. -1994. -V.68, Sept.-P.17-18.

74. Karkkainen J., Sanders P. Simple linear work suffix array construction. In 30th International Colloquium on Automata, Languages and Programming, number 2719 in LNCS,P 943-955, 2003.

75. Kim E.H., Modestino J.W. Adaptive entropy coded subband coding of images // IEEE Trans. Image Proc. 1992. -V.l. -№1. - P. 31-48.

76. Kossentini F., Chung W.C., Smith M. Subband image coding using entropy-constrained residual vector quantization // Information Processing and Management. 1994. -V.30. -№6. - P. 887-896.

77. Kim T. Side match overall match vector quantizers for images // IEEE Trans. Image Proc. 1992. -V.l. -№2. - P. 170-185.

78. Lee B.G. FCT A fast cosine transform // Proc. IEEE ICASSP. -1984. -P. 28A3.1-28A3.4.

79. Lewis A.S. Knowles G. Image Compression using the 2-D wavelet transform // IEEE Trans. Image Proc. 1992. -V.l. -№2. - P. 244-250.

80. Marcellin M. W., Gormish M. J., Bilgin A. and Boliek M. P., An Overview of JPEG-2000, in Proc. of2000 Data Compression Conference, pp. 523-541, Snowbird, Utah, March 2000.

81. Marcellin M. W., Bilgin A., JPEG2000: Highly Scalable Image Compression, in Proc. of 2001 International Conference on Information Technology: Coding and Computing (ITCC2001), pp. 268-272, Las Vegas, Nevada, April 2001.

82. MofFat A. Implementing the PPM Data Compression Scheme, // IEEE Trans. Commun. 1990. V. 38. P. 1917-1921.

83. Nasrabadi N.M., King R.A. Image coding using vector quantization: A review // IEEE Trans, on Communication. 1988. - V. 36. - №8. - P. 957-971.

84. Ngan K.N., Koh H.C. Predictive classified vector quantization // IEEE Trans. Image Proc. 1992. -V.l. -№3. - P. 269-280.

85. Perkins M.G. A comparison of the Hartley, Cas-Cas, Fourier, and discrete cosine transforms for image coding // IEEE Trans. Commun. -1988. V.36. - №6. - P.758-761.

86. Pratt W.K., Andrews H.C. Application of Fourier-Hadamard transformation to bandwidth compression // Picture bandwidth compression / Ed.: Huang T.S., Tretiak O.J. New York: Gordong and Breach, 1972.-P. 515-554.

87. Pratt W.K., Chen W.H., Welch L.R. Slant transform image coding // IEEE Trans. Commun. -1974. -V. COM-22. P.1075-1093.

88. Ramachandran K., Vetteri M Best wavelet packet bases in a rate-distortion sense // IEEE Trans. Image Proc. 1993. -V.2. -№2. - P. 160175.

89. Rao K.R., Yip P. Discrete cosine transform algorithms, advantages, applications. - London: Academic Press inc., 1990.

90. Senoo Т., Giord В. Vector quantization for entropy coding of image subbands //IEEE Trans. Image Proc. 1992. -V.l. -№4. - P. 526-532.

91. Storer J.A. Data compression: Methods and theory. Rockville (Md): Computer science press, 1988. - X, 413 p.

92. Taubman D., Zakhor A. Orientation adaptive subband coding of images // IEEE Trans. Image Proc. 1994. -V.3. -№4. - P. 421-437.

93. Witten I., Neal R.M., Cleaiy J.G. Arithmetic coding for data compression // Comm. ACM. 1987. - V.30. - №6.

94. Woods J.W. Subband image coding of images // IEEE Trans, on ASSP. -1986. -V.34. -№5. P. 1278-1288.