Содержание к диссертации
Введение
1. Современные методы сжатия растровых изображений и соответствующие им графические форматы 13
1.1 Основные понятая 14
1.2 Особенности методов сжатии 17
1.3 Методы сжатия без потери информации 18
1.3.1 Метод группового кодирования (RLE) 18
1.3.2 Метод сжатия LZW 18
1.3.3 Метод Хаффмана 19
1.3.4 Метод Шеннона-Фано, 20
1.3.5 Арифметический метод 22
1.3.6 Метод Loseless J PEG 23
1.4 Алгоритмы сжатия с потерями, 24
1.4.1 Рекурсивное сжатие 24
1.4.2 Метод сжатия JPEG 25
1.4.3 Фрактальное сжатие 32
1.5 Сравнительные характеристики методов сжатия 33
1.6 Форматы графических файлов 35
1.6.1 ФорматвШ 36
1.6.2 Формат P^G 37
1.6.3 Формат TIFF 38
1.6.4 Формат Adobe Photoshop Document 38
1.6.5 Формат BMP 39
2. Сравнение дискретных преобразований по способности сжатия информации при обработке геоизображений 41
2.1 Модель дискретного изображен вя 42
2.2 Вероятностные оценки спектральных характеристик дискретных преобразований; Фурье, косинусного и Крестенсона-Леви 46
2.2.1 Дискретное преобразование Фурье (ДПФ) 46
2.2.2 Дискретное косинусное преобразование (ДКП) 48
2.2.3 Дискретное преобразование Крестенсона-Леви (ДПКЛ) 50
2.3 Свойства избыточности спектров дискретных преобразований Фурье и Крестенсона-Леви вещественных сигналов 53
2.4 Теоретические оценки затрат при кодировании изображений с использованием дискретных преобразований: Фурье, косинусного н Крестенсона-Леви 55
3. Разработка метода сжатия аэрокосмических изображений с применением дискретного преобразования Крестенсона-Леви. 63
3.1 Общая методика построения методов сжатия растровых изображений 63
3.2 Быстрые алгоритмы вычисления дискретного преобразования Крестенсона-Леви 72
3.3 Сжатие изображении при помощи квантования и кодирования спектров дискретного преобразования Крестенсона-Леви 86
3.4 Алгоритм адаптивного арифметического кодирования данных 92
3.5 Оценка временных вычислительных затрат 93
4. Экспериментальные исследования эффективности сжатия аэрокосмических изображений при применении разработанного метода сжатия на основе дискретного преобразования Крестенсона-Леви 105
4.1 Выделение классов изображений объектов аэрокосмических снимков на основе вероятностных характеристик. 105
4.2 Исследование эффективности современных методов сжатия, применительно к аэрокосмическим снимкам , 107
4.3 Исследование эффективности методов предварительного преобразования геоизображений с целью увеличения степени сжатия данных. 114
4.4 Эффективность применения разработанного метода сжатия на основе дискретного преобразования Крестенсона-Леви 117
4.5 Зависимость коэффициентов сжатия при применении разработанного метода на основе дискретного преобразования Крестенсона-Леви от статистических параметров изображений 120
Выводы 122
Заключение ...124
- Методы сжатия без потери информации
- Форматы графических файлов
- Вероятностные оценки спектральных характеристик дискретных преобразований; Фурье, косинусного и Крестенсона-Леви
- Исследование эффективности современных методов сжатия, применительно к аэрокосмическим снимкам
Введение к работе
Современное развитие геоинформационных технологий неуклонно ведет к увеличению объемов накапливаемых и обрабатываемых геоданных, передаваемых преимущественно по различным каналам связи, В настоящее время наиболее используемым и перспективным каналом связи является глобальная компьютерная сеть Интернет. В 2003 году исполнилось 35 лет с момента ее зарождения. Идея возникла в конце 50-х годов, когда в США была поставлена задача создать сеть телекоммуникации. И в 1968 году был составлен план развития сети электронно-связанных компьютеров АРПАНЕТ (прообраз Интернета) для оповещения о возможной ядерной атаке, а спустя год вступил в действие первый компьютер, предоставляющий клиентам услуги по телекоммуникации. Через три года сеть охватила уже 34 компьютера, размещенных в разных концах страны, а к 1983 году через АРПАНЕТ были соединены более 400 больших компьютеров. Вскоре АРПАНЕТ разделилась на две сети: несекретную военно-промышленную и научно-исследовательскую. Вместе они назывались АРПАИНТЕРНЕТ и включали несколько тысяч серверов.
В начале 90-х годов Интернет превратился в самую разветвленную и мощную планетарную компьютерную сеть (ее называют информационной супермагистралью) и стал основным каналом международного общения, универсальным средством передачи научной и учебной информации. Тысячи компьютеров образуют локальные сети, они соединяются в региональные, а те, в свою очередь, составляют сегменты глобальной сети, к которой можно подключить каждый компьютер.
С помощью Интернета сегодня широко реализуются услуги электронной почты, обеспечивается доступ к массивам цифровой информации, расположенной в самых дальних точках планеты, к научным документам, в том числе картам, аэро- и космическим снимкам, к электронным каталогам, учебникам и библиотекам.
Геоизображения, размещенные в Интернете, включают, прежде всего, статичные карты и атласы, а также аэро- и космические снимки, поступающие в цифровой записи. Число таких изображений чрезвычайно велико, например, только государственная картографическая служба США разместила в Интернете сотни тысяч документов.
Особую группу составляют анимации, то есть движущиеся мультипликационные геоизображения, картографические фильмы, мультимедийные картины. В Интернете представлены анимации самого разного вида - от простых электронных карт до трехмерных блок-диаграмм, пейзажных карт с меняющейся перспективой и панорам, которые показывают территорию, словно с высоты птичьего полета и даже моделируют ее облет.
Наконец, в компьютерной сети размещены блоки карт, снимков и иных геоизображений, входящих в географические информационные системы (ГИС). С ними можно манипулировать: сопоставлять между собой, накладывать друг на друга, определять по ним взаимосвязи явлений, использовать для оценки и районирования территории и решения других научно-практических или учебных задач.
Основной массив в Интернете образуют оперативные карты, создаваемые в режиме реального времени. Они отражают актуальную справочную информацию. Подсчитано, что наибольшее место в Интернете занимают карты погоды и опасных атмосферных явлений (ураганов, циклонов). Вторые по частоте встречаемости - планы городов и дорожные карты. Другие геоизображения ориентированы на специализированное применение в научных и практических целях (например, карты динамики окружающей среды или спутниковые снимки, фиксирующие состояние сельскохозяйственных посевов). Популярны карты транспорта и навигации, картосхемы текущих событий, политических конфликтов, горячих точек, карты национальных парков, предназначенные для туризма, отдыха и путешествий.
Развитие современных технологий влечет за собой рост объемов устройств для хранения геоданных и пропускной способности линий связи. Однако количество требуемой геоинформации растет еще быстрее. У этой проблемы есть три решения. Первое решение — ограничение количества информации - абсолютно не приемлемо: например, для аэрокосмических снимков это означает уменьшение разрешения или ограничение цветовой палитры, что приведет к потере мелких деталей и может сделать изображения непригодными к дальнейшей работе. Второе решение - увеличение объема носителей информации и пропускной способности каналов связи - связано с развитием соответствующих технологий, которые, в свою очередь, связаны с определенными материальными затратами, причем весьма значительными. Третье же решение - использование различных методов сжатия аэрокосмических изображений, которые составляют основной объем геоинформации. Это решение позволяет в несколько раз сократить требования к объему устройств хранения геоданных и пропускной способности каналов связи без дополнительных издержек (за исключением издержек на реализацию самих методов сжатия). Условиями его применимости является возможность установки специального программного обеспечения как вблизи источника, так и вблизи приемника информации. Как правило, это условие удовлетворяется.
В связи с этим, целью диссертационной работы являлись исследование и разработка методов сжатия аэрокосмических снимков для передачи по каналам связи в глобальные сети.
Новизна поставленной задачи вытекает из того, что на данный момент не существует единого и общедоступного метода сжатия геоинформации, применение которого давало бы стабильно высокий уровень сжатия исходного изображения при заданном коэффициенте потери информации. Это связано в первую очередь с тем, что задача передачи геоизображений по каналам Интернет отличается сверхбольшими объемами самих изображений, что делает применение методов сжатия без потерь малоэффективным по причине низкого коэффициента сжатия (максимум, до 1.5), а применение методов сжатия с потерями может сделать геоизображение непригодным для дальнейшего использования.
Актуальность задачи обусловлена исключительной важностью возможности быстрой и надежной передачи геоданных по различным каналам связи для развития Геоинформационных систем в Интернете. Кроме того, уменьшение временных затрат на передачу геоизображений, которое и достигается понижением объема передаваемых данных и повышением их скорости обработки, может значительно повысить эффективность работы не только ведомственных, производственных, научных и учебных организаций, но и различных служб спасения и контроля обстановки, а там каждая выигранная секунда, возможно, позволит спасти множество жизней и предотвратить катастрофу.
Для достижения поставленной цели в работе решались следующие задачи:
Изучение и анализ существующих на настоящий момент методов сжатия растровых изображений и соответствующих им графических форматов файлов, которые в настоящее время наиболее часто используются для передачи изображений по каналам Интернет.
Исследование эффективности современных методов сжатия применительно к различным фрагментам аэрокосмических снимков.
Исследование эффективности методов дифференциальной импульсно-кодовой модуляции и других методов предварительного преобразования геоизображений с целью увеличения степени сжатия данных.
Разработка метода сжатия геоданных, основанного на применении дискретного преобразования Крестенсона-Леви и последующем адаптивном арифметическом кодировании.
Разработка программы, реализующей разработанный метод сжатия аэрокосмических снимков.
6. Исследование эффективности предложенного метода сжатия геоданных для различных групп объектов аэрокосмических изображений, Выработка рекомендаций по использованию предложенного метода сжатия геоданных.
Диссертационная работа состоит из четырех глав.
В первой главе рассматриваются, описанные в отечественной и зарубежной литературе, методы сжатия статических растровых изображений, а также соответствующие им графические форматы. Вначале определены основные понятия, связанные с рассмотрением методов сжатия изображений. Для каждого рассматриваемого метода описывается его алгоритм, классы изображений, на которые он ориентирован и коэффициенты сжатия: минимальный, максимальный и средний. Особое внимание уделено методу JPEG, который на сегодняшний день является наиболее универсальным и широко используемым в глобальной сети Интернет. Проведенный анализ позволяет сделать выводы о перспективах использования рассмотренных методов сжатия применительно к геоизображениям, а также, в последующих главах взять схему метода JPEG, как прототип для разработки нового метода сжатия геоизображений.
Во второй главе рассматриваются дискретные преобразования Фурье (ДПФ), косинусное (ДКП) и Крестенсона-Леви (ДИКЛ) и проведен анализ их способности сжатия при обработке геоизображений. На основе проведенного анализа, делается вывод, что создание метода сжатия геоизображений с использованием дискретного преобразования Крестенсона-Леви обосновано, поскольку проигрыш по способности к сжатию у ДПКЛ к дискретному косинусному преобразованию составляет в среднем 5-10%, но при этом число вычислительных операций, необходимых для реализации сжатия геоизображений на основе ДПКЛ, может быть намного меньше, чем в случае применения ДКП. Выигрыш в скорости обработки на этапе дискретного преобразования позволяет на последующем этапе статистического кодирования применить более сложный и ресурсоемкий метод адаптивного кодирования, который позволит значительно увеличить эффективность метода сжатия геоизображений.
В третьей главе рассмотрены существующие быстрые алгоритмы ДПКЛ: алгоритм ДПКЛ с прореживанием по времени, алгоритм ДПКЛ с неполным вычислением. Далее в главе рассматривается предлагаемый в диссертации метод сжатия геоизображений на основе ДПКЛ. Из метода сжатия JPEG была заимствована общая схема метода, заключающаяся в разбиении исходного изображения на фрагменты, выполнении с каждым фрагментом дискретного преобразования, квантовании и статистического кодирования полученных спектральных коэффициентов. На этапе дискретного преобразования фрагментов изображения вместо дискретного косинусного преобразования (ДКП) в исходном методе Л'ЕО, предлагается применить ДПКЛ (алгоритм с неполным вычислением), что влечет коренные изменения в алгоритмах и способах реализации квантования и статистического кодирования спектров. В предлагаемом методе сжатия спектр ДПКЛ каждого фрагмента обрабатывается более сложным способом, в основе которого лежит алгоритм адаптивного арифметического кодирования. Данное изменение в сторону усложнения способа обработки спектра ДПКЛ оказалось возможным, благодаря значительному выигрышу во времени вычислений, который дает на этапе выполнения преобразования применение алгоритма ДПКЛ с неполным вычислением вместо быстрого алгоритма ДКП. Теоретическая оценка вычислительных затрат на сжатие-восстановление геоизображений позволяет сделать вывод, что предлагаемый метод сжатия выигрывает по данному параметру у метода JPEG.
В четвертой, заключительной главе описаны проведенные автором исследования: определение эффективности существующих методов сжатия, применительно к аэрокосмическим снимкам и эффективности методов предварительного преобразования геоизображений с целью увеличения степени сжатия графических данных. На основе проведенных исследований сделаны выводы о том, что максимальная степень сжатия при использовании существующих методов достигается при использовании метода сжатия JPEG.
Далее описаны результаты проведенного автором исследования эффективности применения разработанного метода сжатия на основе дискретного преобразования Крестенсона-Леви. Результаты обработки фрагментов геоизображений при использовании предлагаемого метода сжатия сравнивались с результатами работы наиболее используемого в настоящее время метода сжатия JPEG, как по коэффициенту сжатия, так и по качеству восстановленных изображений. По результатам сравнения нового метода со стандартом JPEG делается вывод о том, что для обработки аэрокосмических снимков разработанный метод сжатия геоизображений выигрывает у метода JPEG в коэффициенте сжатия аэрокосмических снимков при схожих значениях потери информации.
Далее исследуется зависимость значений коэффициента сжатия геоизображений, при использовании нового разработанного метода, от статистических характеристик изображений. Результаты исследования позволяют сделать вывод о зависимости коэффициента сжатия изображения и выборочного среднеквадратичного отклонения значений цвета его пикселов, что позволяет выделить изображения, на которых достигается максимальная степень сжатия разработанного метода. На защиту диссертации выносятся: результаты исследований эффективности применения существующих методов сжатия изображений, а также методов предобработки изображений для сжатия геоизображений. разработанный метод сжатия аэрокосмических изображений на основе дискретного преобразования Крестенсона-Леви и последующего адаптивного арифметического кодирования программная реализация разработанного метода сжатия, исследование эффективности предлагаемого метода сжатия геоизображений, рекомендации по использованию разработанного метода для различных групп геоизображений.
Основные результаты, изложенные в диссертации, опубликованы в 6 работах автора [3-8].
Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Общий объем работы составляет 158 страниц текста. Список литературы содержит 98 наименований, из них 46 иностранная литература.
Методы сжатия без потери информации
Групповое кодирование - Run Length Encoding (RLE) - один из самых ранних и самых простых методов архивации графики [13, 25]. Изображение в нем (как и в нескольких методах, описанных далее) вытягивается в цепочку байт по строкам растра. Само сжатие в методе RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Замена их на пары "счетчик, значение" в большинстве случаев уменьшает объем данных. Коэффициенты сжатия варьируются от 1/64 до 2/1. Данный метод применяется в форматах PCX, TIFF, BMP. Ориентирован метод на изображения с небольшим количеством цветов - деловую и научную графику. Симметричность примерно равна единице. К положительным сторонам метода RLE можно отнести только то, что он не требует дополнительной памяти при архивации и разархивации, а также быстро работает. Интересная особенность метода группового кодирования состоит в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения. 1.3.2 Метод сжатия LZW. Методы сжатия семейства LZW (Lempel-Ziv-Welch) сжимают данные путем поиска одинаковых последовательностей (цепочек) во всем файле [13, 39]. Выявленные цепочки сохраняются в таблице, и им присваиваются более короткие маркеры (ключи). Так, если в изображении имеются наборы из нескольких пикселей, повторяющиеся 50 раз, метод сжатия LZW выявляет это, присваивает данному набору отдельное число, и затем сохраняет эти данные 50 раз в виде этого числа. Метод LZW, так же как и метод RLE, лучше действует на участках однородных, свободных от шума цветов изображения. При этом он действует гораздо лучше, чем метод RLE, при сжатии произвольных графических данных, но процесс кодирования и распаковки происходит медленнее.
Существует довольно большое семейство LZW-подобных методов, различающихся алгоритмом поиска повторяющихся цепочек [13]. Коэффициенты сжатия данного метода: 1/1000, 1/4, 7/5. Коэффициент 1/1000 достигается только на одноцветных изображениях размером больше 4 Мб. Ориентировано LZW-семейство методов сжатия на 8-битные изображения. Характерной особенностью данного метода является его высокая степень симметричности при сжатии и восстановлении изображений. Ситуация, когда изображение увеличивается в объеме - встречается крайне редко. Метод LZW универсален - именно его варианты используются в обычных архиваторах. Метод LZW реализован в форматах GIF, TIFF и TGA. 1.3.3 Метод Хаффмана Данный метод был разработан в 1952 году и используется как составная часть и других схем сжатия, таких как LZW, Дефляция, JPEG [13,39,40,46]. Метод сжатие Хаффмана - статистический метод сжатия, который уменьшает среднюю длину кодового слова для символов алфавита. Код Хаффмана может быть построен по следующему алгоритму: 1. Выписываются в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте; 2. Последовательно объединяются два символа с наименьшими вероятностями появления в новый составной символ, вероятность появления которого полагается равной сумме вероятностей составляющих его символов; в конце концов, строится дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него; 3. Прослеживается путь к каждому листу дерева, помечая направление к каждому узлу (например, направо - 1, налево - 0). Метод Хаффмана используется в большинстве архиваторов. 1.3.4 Метод Шеннона-Фано Родственным методом для кодирования Хаффмана является кодирование Шеннона-Фано [13], которое осуществляется следующим образом: 1. Все множество символов делится на два подмножества так, чтобы сумма вероятностей появления символов одного подмножества была примерно равна сумме вероятностей появления символов другого. Для левого подмножества каждому символу приписывается "0", для правого - "1". 2. Повторяется шаг (1) до тех пор, пока все подмножества не будут состоять из одного элемента. Методы Хаффмана и Шеннона-Фано берут только частоту появления одинаковых байт в изображении и сопоставляют символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И напротив - встречающимся редко - цепочку большей длины. Для сбора статистики требуется два прохода по изображению. Коэффициенты сжатия методов Хаффмана и Шеннона-Фано следующие: лучший - 8, средний — 1.5, худший - 1.
Данные методы практически не применяются к изображениям в чистом виде. Обычно они используются как один из этапов компрессии в более сложных схемах. В описанных выше методах, в файл производиться запись таблицы соответствия кодируемых символов и кодирующих цепочек. На практике же, обычно используются их разновидности. Так, в некоторых случаях резонно либо использовать постоянную таблицу, либо строить ее адаптивно, т.е. в процессе архивации/разархивации. Эти приемы избавляют от двух проходов по изображению и необходимости хранения таблицы вместе с файлом. Кодирование с фиксированной таблицей применяется в качестве последнего этапа архивации в рассматриваемом ниже методе JPEG.
Форматы графических файлов
Все графические компьютерные данные можно разделить на две большие ветви: растровую и векторную. При этом большинство векторных форматов могут так же содержать внедренные в файл растровые объекты или ссылку на растровый файл. Сложность при передаче данных из одного векторного формата в другой заключается в использовании программами различных алгоритмов, разной математики при построении векторных и описании растровых объектов. Растровый файл представляет из себя прямоугольную матрицу (bitmap), разделенную на маленькие квадраты - пиксели (pixel - picture element). Растровые файлы можно разделить на два типа: предназначенные для вывода на экран и для печати. Растровые форматы, предназначенные исключительно для вывода на экран, имеют только экранное разрешение, то есть один пиксель в файле соответствует одному экранному пикселю. На печать они выводятся так же с экранным расширением. Растровые файлы, предназначенные для до-печатной подготовки изданий, имеют, подобно большинству векторных форматов, параметр Print Size - печатный размер. С ним связано понятие печатного разрешения, которое представляет из себя соотношение количества пикселей на один квадратный дюйм страницы (ppi - pixels per inch или dpi - dots per inch, - термин не совсем верный, но часто употребляемый). Печатное разрешение может быть от 130 dpi (для газеты) до 300 или 600 (высококачественная печать). Растровые форматы так же отличаются друг от друга способностью нести дополнительную информацию: различные цветовые модели, вектора, Альфа-каналы или каналы платковых (spot) цветов, слои различных типов, интерлиньяж (черезстрочная подгрузка), анимация, возможности сжатия и т.д.
В контексте задачи обработки аэрокосмической геоинформации, нас интересуют растровые графические форматы, так как геоинформационные изображения в большинстве своем представляют из себя именно растровые изображения. 1.6.1 Формат GIF Независящий от аппаратного обеспечения графический формат GIF (CompuServe Graphics Interchange Format) [39, 40] был разработан для передачи растровых изображений по сетям. Формат GIF использует LZW-компрессию, что позволяет неплохо сжимать файлы, в которых много однородных заливок (логотипы, надписи, схемы), а также записывать изображение «через строчку» (Interlaced), благодаря чему, имея только часть файла, можно увидеть изображение целиком, но с меньшим разрешением. Кроме того, файл формата GIF может содержать не одну, а несколько растровых картинок, которые браузеры могут подгружать одну за другой с указанной в файле частотой. Так достигается иллюзия движения (GIF-анимация),
Формат PNG Формат PNG (Portable Network Graphics) [39] - еще один формат Всемирной Сети, разработанный относительно недавно и призванный заменить собой устаревший GIF. Он использует сжатие без потерь Deflate, сходное с методом LZW. Сжатые индексированные файлы PNG, как правило, меньше аналогичных файлов формата GIF, a RGB PNG — меньше соответствующего файла в формате TIFF. Глубина цвета в файлах PNG может быть любой, вплоть до 48 бит. Кроме того, используется двумерных interlacing (причем, не только строк, но и столбцов), который, так же как и в формате GIF слегка увеличивает размер файла. В отличие от файлов формата GIF, где прозрачность либо есть, либо нет, формат PNG поддерживает также полупрозрачные пиксели (то есть, в диапазоне прозрачности от 0 до 99%) за счет Альфа-канала с 256 градациями серого цвета. В файл формата PNG записывается информация и о гамма-коррекции, которая представляет собой некоторое число, характеризующее яркость свечения монитора от напряжения на электродах кинескопа. Это число, считанное из файла, позволяет ввести поправку яркости при отображении. Нужно оно для того, чтобы картинка, созданная на компьютерах семейства Macintosh выглядела одинаково и на обычных персональных компьютерах и на рабочих станциях Silicon Graphics. Таким образом, эта особенность помогает реализации основной идеи Интернет - одинакового отображения информации независимо от аппаратуры пользователя. Формат PNG поддерживается в Microsoft Internet Explorer, начиная с 4-ой версии для Windows, и с версии 4.5 для компьютеров Macintosh. Фирма Netscape добавила поддержку PNG для своего Интернет-браузера в версиях, начиная с 4.0.4 для обеих платформ. Тем не менее, до сих пор не реализована поддержка таких важных функций формата, как плавно переходящая прозрачность и гамма-коррекция. 1.6.3 Формат TEFF Аппарата о независимый формат TIFF (Tagged Image File Format) [39, 40], на сегодняшний день является одним из самых распространенных и надежных, его поддерживают практически все программы на PC и Macintosh, так или иначе связанные с графикой. TIFF является лучшим выбором при импорте растровой графики в векторные программы и издательские системы. Ему доступен весь диапазон цветовых моделей и дополнительных цветов Pantone. TIFF может сохранять различные контуры, Альфа-каналы и другие дополнительные данные. В формате TIFF может быть использована LZW-компрессия. 1.6.4 Формат Adobe Photoshop Document Внутренний формат популярного растрового редактора Photoshop [40] в последнее время стал поддерживаться все большим количеством программ. Он позволяет записывать изображения со многими слоями, их масками, дополнительными Альфа-каналами и каналами простых цветов, контурами и другой информацией. В версии 3.0 появляются слои, контуры и RLE-компрессия, в четвертой версии улучшается алгоритм, и файлы становятся еще меньше. Начиная с пятой версии, реализован принципиально другой подход к управлению цветом, основанный на профилях для сканеров, мониторов и принтеров Международного консорциума по цвету (International Color Consortium, ICC). 1.6.5 Формат BMPФормат BMP (Windows Device Independent Bitmap) [40] - родной формат Windows. Он поддерживается всеми графическими редакторами, работающими под управлением операционной системы. Применяется он для хранения растровых изображений, предназначенных для использования в Windows и, по сути, больше ни на что не пригоден. Формат способен хранить как индексированный (до 256 цветов), так и RGB-цвет (16.700.000 оттенков). Возможно применение сжатия по принципу RLE, но делать это не рекомендуется, так как тогда он станет «непонятен» для большинства программ. Существует разновидность формата BMP для операционной системы OS/2.
Вероятностные оценки спектральных характеристик дискретных преобразований; Фурье, косинусного и Крестенсона-Леви
Положим, что матрица X описывается моделью (2.5). Для этого случая найдем математические ожидания т ,/ и среднеквадратичные значения модулей о р/ спектральных характеристик ytj для дискретного преобразования Фурье (ДПФ), дискретного косинусного преобразования (ДКП) и дискретного преобразования Крестенсона-Леви (ДПКЛ). 2.2.1 Дискретное преобразование Фурье (ДПФ) ДПФ вектора Х = (х0,х1,...,л:л,_1)г называется вектор Y = {y0,yl,...tyN_l)T , элементы которого находятся по следующей формуле [35]: 47 1 (-2л-г А Тогда обратное ДПФ (ОДПФ) следует записать [35]: (2.9) 1 (2я-і .,л =0 \ N у=0Д,...ЛГ-1. (2.10) Пара ДПФ-ОДПФ в двумерном случае (когда X, Y представляют собой матрицы из N строк и М столбцов) определяется соответственно [35]: і (-2Я-І .,№ (-2я-і ; N / = 0Д Af-1, fMN % Ч ЛГ = 0Л,...ЛГ-1, (2.11) \Л/-] х1ш.= 1 лм 2л- -і пЪУкг (ІЯ-І /и/ (2.12) j = 0,l,...JV-l т = 0,1,...,Л/-1. Определим математические ожидания и среднеквадратичные значения модулей элементов матрицы Y, полученной из матрицы X (2.5) в результате ДПФ (2.11). )-73E7Se4 N -т/ = 0. ЧІЛ і, м «І [і=ЕІУкґУкМ ХЇ,ещ к(у-тІТЕ MN p & \ N У Jf) И 4 (2x-i,, Л u-H 48 = r\(N)- TJ(M), (2.13) где 1 N-\N-\ (О тт.і \m-!\ (2.14) Выражение (2.14) для rj = T?(N) можем переписать в следующем виде: при 0 р 1 70 = 1 + р 2р(р -і) \-р N(l-p)2 N, при р -1 ТА = і-р2 p -ifc +ij p) і-2р-с +р2 (і-гр- + р2)2 ck=cos{l7tkjN\ k \,...,N-\ (2.15) 2.2.2 Дискретное косинусное преобразование (ДКП) ДКП в одномерном случае определяется [35]: Ук = "IN Щ cos(jv + Щ (2.16) k = 0,\,...,N-l, а обратное ДКП (ОДКП): -т« ykcos (5И (2.17) j = QX.,.,N-\, 49 где :(k) = 1. Л-, при к = 0 1, при к 0 Двумерные ДКП, ОДКП определим соответственно [35]: Укі = 4Ш J VMVO ( М )5 ч ттО +v\ X ;,» cos[ тті+1) /=о V ;m=0 Af A = 0,l,...fJV-l, / = 0,1,...,M-1, ZcMcos —(j +1)11 «(О Ук,іcos( (m + ІН Jfc = 0,l,...,tf-1, / = 0,l,...,Af-l, (2.18) (2.19) c(k) определяются так же, как и в (2.16), (2.17). ДКП имеет вещественную природу, тк,1=Е(Уи)= (2.20) N сг Ч )= Ч«їоо{ 0 + і))іЦ ( + і))-РМ. (2-21) :(k) = Уф при = 0 1 , при к 0 Равенства (2.20), (2.21) выводятся аналогично тому, как это было проделано для ДПФ при получении формул (2.13), (2.14). Преобразовать выражение (2.21) можно к следующему виду: 1 + p 2p{pN-l) al=\ \-p N(l-pf при 0 р 1 N, при p = 1 1-p2 24-l)V-l)(c,+lXp-l) l-2p-ck+p2 N(l-2p-ck+p2J ck = cos(nk/N\ к -1,..., N -1 (2.22) 2.2.3 Дискретное преобразование Крестенсона-Леви (ДПКЛ) Для того, чтобы ввести в рассмотрение дискретное преобразование Крестенсона-Леви, дадим предварительно ряд определений. Пусть р - простое число, р 2. Для произвольного числа х 0 обозначим: хк = x_t = х-рк[то6р\ x/pk ]\modp), целые числа х (0 х±ь р-1, А=1,2,...) назовем коэффициентамир-ичного разложения. Для числа лг можно записать: 00 00 = [ ] + {х} = X jt Рк Х + 1 /У, =i І=І (2.23) где первая сумма, соответствующая целой части числа х, для любого конкретного числа х конечна. Вторая сумма, соответствующая дробной части числа JC, вообще говоря, бесконечна. Используя /?-ичное представление чисел (2.23), систему функций Крестенсопа-Леви [42] (или Виленкина-Крестенсона) можно определить на промежутке я є [ОД) в нумерации Пэли следующим образом: , ч " (2т Л (2т!& ) Хт\х) = ПЄХР Хк -т-к\ = ЄХР LXk т-к п - ,х т=0Д,.„ где число / находится из условия: т р -1. При/э=2 получим в (2.24) частный случай системы функций Крестенсона-Леви - систему Уолша [42]. Так как величина S = хк -т_к в определении (2.24) является ic=l целым неотрицательным числом и (х)=ехр ґ2т к Р ) = ехр 1т К. Р (Smodp) , то функции системы (2,24) могут принимать лишь р возможных (комплексных) значений из множества ехр —к і КР )}к=0 ДПКЛ вектора Х = [х0,х],...,х . f назовем вектор Y = [уо,У], У -_i/) элементы которого получены по формуле (пеЫ): Ук = 1 x,-Zktt/pH) (2.25) рп ы fc = 0,l /7Я —1. Тогда обратное ДПКЛ (ОДПКЛ) может быть записано в виде: 1 &1 / = ±ук-Хі(к/Р"\ ip" =o (2.26) / = 0,l,...,p"-l. Следует указать на тот факт, что, положив р=2, получим в (2.25) и (2.26) дискретное преобразование Уолша (прямое и обратное преобразования Уолша имеют одинаковый вид). Положив и=1, получим в (2.25) ДПФ (2.9), а в (2.26) - ОДПФ (2.10) размерности N=p [65].
Для числа строк N p" и числа столбцов М=рг (п,геН) прямое и обратное двумерные ДПКЛ определим соответственно: » % №%Ш\ (2.27) k = 0X. ,p"-U / = 0,1,..„у-1, 1 1 Xm,j txSklpn)tyk;Xj{llpr\ 4р ГтУ & » " (2,28) m = 0,l,... n-l, j = Q,\,...,pr-l. Введем для неотрицательных чисел у, z операцию сложения по модулю р и обратную ей операцию вычитания по модулю р соответственно: y2 ±v_k-pk- ±vjp\ Уг = ±и_к-рк-]+±ик/рк, к-I =1 А=] =1 где коэффициенты р-ичного разложения для к=1,2,... [У± -г±м+Р, при y±k z±k Число к будем называть р-ично обратным числу к, если кк =0 (или k =0&k), Рассмотрим теперь некоторые вероятностные оценки для элементов двумерного дискретного спектра ДПКЛ (2.27)» полученного из матрицы (2.5). Легко видеть, что: Для математического ожидания квадрата модуля спектральной характеристикиук( имеем: j2kJ = 2{р,кХр\рг)= г1{Р") -а2{рг\ (2.29) 1=1{ра)=\РЪТк{11рпКрЬМ-Хк{1р"\ (2-30) р /=0 от=0 Формулы (2,29), (2.30) выводятся аналогично (2.13), (2.14). Для частного случая р=3, N=3 =9 (см. определение системы функций Крестенсона-Леви (2.24)) выражение (2.30) принимает вид: г =4І igkJm- -Jl) t Тяк-Хт- -и) Р1тЧІ (2.31) где q = exp(- 2mj3). 2.3 Свойства избыточности
Исследование эффективности современных методов сжатия, применительно к аэрокосмическим снимкам
В рамках решения данной задачи было проведено исследование существующих на данный момент методов сжатия статических растровых изображений на предмет их эффективности для сжатия аэрокосмических снимков. В исследовании рассматривались как методы сжатия растровых изображений без потерь - LZW-компрессия (графические форматы TIFF и GIF), групповое кодирование (RLE - PCX, BMP), метод Deflate (PNG), так и с потерями (JPEG с различными параметрами качества изображения: 2, 6 и 11 по 12-бальной шкале). Целью исследования было определить не столько коэффициенты сжатия того или иного класса изображений данным алгоритмом, сколько оправданность алгоритма в целом, применительно к данному классу изображений. Особенно, это относится к методам сжатия с потерями, которые дают заведомо более высокие результаты по сжатию изображения, чем методы без потерь, но при этом цена таких результатов может быть неоправданно высока - потеря сверх важной информации, делающая дальнейшее применение данного изображения (фрагмента изображения) бесполезным.
Одна из серьезных проблем при обработке графических изображений заключается в том, что до сих пор не найден адекватный критерий оценки потерь качества изображения. А теряется оно постоянно - при оцифровке, при переводе в ограниченную палитру цветов, при переводе в другую систему цветопредставления, и, что особенно важно, при архивации с потерями. Можно привести пример простого критерия: среднеквадратичное отклонение значений пикселов (Ьг мера, или root mean square - RMS): RMS(xfy) = Vi г , где Xy - элементы пг матрицы исходного изображений, а у у - сжатого. По данному критерию изображение будет сильно испорчено при понижении яркости всего на 5% (глаз этого не заметит - у разных мониторов настройка яркости варьируется гораздо сильнее). В то же время изображения со "снегом" - резким изменением цвета отдельных точек, слабыми полосами или "муаром" будут признаны "почти не изменившимися". Другой критерий потери качества изображения - «критерий максимального отклонения»: МО(х,у)-тгк.хи — у& Этот критерий крайне чувствителен к расхождению значений отдельных пикселов. То есть во всем изображении может существенно измениться значение только Ї пиксела (что практически незаметно для глаза), однако, согласно этой мере, изображение будет сильно испорчено.
Мера, которая в настоящий момент наиболее используется на практике, называется «мерой отношения сигнала к шуму» (picko-pick signalo-noise ration - PSNR): PSNR(x, у) = 10 lg- 255V i=\J=\ Данная мера, по сути, аналогична среднеквадратичному отклонению, однако пользоваться ей несколько удобнее за счет логарифмического масштаба шкалы. Ей присущи те же недостатки, что
Кроме того, стоит отметить, что потери информации могут возникнуть не только у методов сжатия с потерей информации, но и у методов сжатия без потерь, что связано с изменением палитры цветов при переходе в другой графический формат. В ходе исследования были получены результаты, характерно представленные в таблице 4.1 и графике 4.1 Понятие потери информации применяется только в тех случаях, когда эта потеря имеет место. Так как методы сжатия LZW, RLE, GIF, PCX, PNG - являются методами без потери информации, то коэффициенты RMS и МО для них тождественно равны нулю, а коэффициент PSNR - бесконечно велик. Ниже приведены коэффициенты потери информации для результатов работы метода JPEG с различными параметрами сжатия. Результатами проведенного исследования стали следующие выводы: Использование методов LZW и RLE, применительно к графическим форматам GIF и PCX, для аэрокосмических снимков -не оправдано, так как коэффициенты сжатия различных фрагментов изображения близки к 1, причем очень часто ниже единицы (то есть изображение увеличивается в объеме). Использование метода LZW, совместно с форматом TIFF дает в лучшем случае сокращение объема лишь на 10%, а иногда даже увеличивает объем. Использование данного метода возможно лишь в сочетании с другими методами сжатия. Метод Deflate (формат PNG) показывают достаточно стабильный результат в районе 1.2 - 1.4 от объема исходного изображения. Для аэрокосмических снимков, которые характеризуются огромными объемами (сотни, а то и тысячи мегабайт) этого явно недостаточно. Необходимы дальнейшие более подробные исследования комбинаций данного метода с другими алгоритмами сжатия. Метод сжатия с потерей информации JPEG дает наиболее высокие результаты сжатия изображения, однако, при низком качестве изображения (JPEG с коэффициентом качества 2 по 12-бальной шкале), максимальное отклонение цвета пиксела после сжатия от исходного изображения составило почти треть всей палитры! То есть применение данного метода сжатия с низким параметром качества оправдано только тогда, когда мы это действительно можем себе позволить (например, информация передается только для зрительного восприятия без дальнейшей программной обработки). Основной вывод проведенного исследования заключается в том, что ни один из представленных методов сжатия без потерь не дает существенного уменьшения объема аэрокосмических снимков, и лишь при использовании метода сжатия с потерями JPEG можно добиться высоких коэффициентов сжатия (до 12.5).
