Содержание к диссертации
Введение
ГЛАВА 1. Анализ методов сжатия изображений. Базовые понятия и определения. Постановка задачи 13
1.1. Основные характеристики и классы статических цифровых изображений 13
1.2. Требования, предъявляемые к алгоритмам сжатия изображений в задачах ДЗЗ. Постановка задачи 16
1.3. Критерии точности восстановления изображений 19
1.4. Обзор существующих подходов 21
1.4.1. Усеченное блочное кодирование 24
1.4.2. Статистические методы сжатия данных 29
1.4.2.1. Код Хаффмена 29
1.4.2.2. Арифметический код 35
1.4.2.3. Код Голомба 39
1.4.3. Стандартизованные методы сжатия статических изображений . 44
1.4.3.1. Стандарт сжатия JPEG 44
1.4.3.2. Стандарт сжатия JPEG-LS 50
1.5. Выводы по разделу ;. 55
ГЛАВА 2. Сжатие изображений на основе модифицированного метода усеченного блочного кодирования 56
2.1. Выбор пороговых уровней при сжатии изображений методом УБК... 57
2.2. Сокращённая передача уровней квантования при сжатии изображений методом УБК 61
2.3. Использование пре- и постфильтрации при сжатии изображений методом УБК 64
2.4. Сравнительный анализ эффективности использования предложенной модификации метода УБК 72
2.5. Выводы по разделу 75
ГЛАВА 3. Адаптивный код Голомба и его использование при сжатии изображений 77
3.1. Практическая реализация адаптивного кода Голомба 78
3.2. Избыточность адаптивного кодаГоломба 81
3.3. Особенности использования АКГ при сжатии изображений в трансформационных схемах кодирования на основе ДКП 85
3.3.1. Анализ распределения коэффициентов ДКП 85
3.3.2. Алгоритм раздельного сжимающего кодирования коэффициентов АС 88
3.3.3. Использование предсказателя при сжатии коэффициентов АС 90
3.3.4. Кодирование коэффициентов DC 92
3.3.5. Оценка параметра кода Голомба при кодировании коэффициентов ДКП 93
3.3.6. Результаты применения АКГ при сжатии изображений с использованием ДКП 97
3.4. Использования АКГ при сжатии изображений в схемах кодирования без искажений с предсказанием 102
3.4.1. Распределение ошибки предсказания 103
3.4.2. Оценка параметра кода Голомба при кодировании ошибки предсказания 105
3.4.3. Результаты применения АКГ при сжатии изображений в схеме кодирования с использованием адаптивного предсказателя 108
3.5. Выводы по разделу 110
ГЛАВА 4. Особенности практической реализации методов сжатия изображений с постоянной скоростью сжимающего кодирования 112
4.1. Модифицированный метод сжатия изображений на основе ДКП... 112
4.2. Результаты практического применения схемы сжатия на основе ДКП с постоянной скоростью сжимающего кодирования 120
4.3. Метод сжатия изображений на основе предсказателя с постоянной скоростью сжимающего кодирования 122
4.4. Оценка эффективности применения модифицированной схемы сжатия на основе предсказателя с постоянной скоростью сжимающего кодирования 126
4.5. Информационные требования предлагаемых модификаций схем сжатия 128
4.6. Влияние искажений при передаче на возможность восстановления изображений, сжатых с постоянной скоростью сжимающего кодирования 131
4.7. Выводы по разделу 135
Заключение 136
Список использованных сокращений 139
Литература 141
Приложение А. Использованные тестовые изображения 148
- Требования, предъявляемые к алгоритмам сжатия изображений в задачах ДЗЗ. Постановка задачи
- Сравнительный анализ эффективности использования предложенной модификации метода УБК
- Результаты применения АКГ при сжатии изображений в схеме кодирования с использованием адаптивного предсказателя
- Влияние искажений при передаче на возможность восстановления изображений, сжатых с постоянной скоростью сжимающего кодирования
Введение к работе
Актуальность темы
Необходимость сжатий на борту космических аппаратов видеоданных, получаемых в задачах дистанционного зондирования Земли (ДЗЗ), обусловлена ростом генерируемых современными космическими системами ДЗЗ информационных потоков (до нескольких сотен МБайт/с), связанным с увеличением как пространственного, так и спектрального разрешения съёмочной аппаратуры при сохранении широкой полосы обзора, и сравнительно невысокой пропускной способностью радиоканалов при передаче данных на наземные приемные станции.
В большинстве современных систем дистанционного зондирования Земли из космоса в' качестве основного используется режим непосредственной передачи, ограничивающий возможность применения буферизации для выравнивания потока кодируемых данных. Необходимость согласования потока сжатых видеоданных с пропускной способностью радиоканала при передаче на наземные приемные станции диктует требование обеспечения кодером постоянной скорости сжимающего кодирования, а специфика бортовой реализации накладывает ограничения на вычислительную сложность применяемых алгоритмов.
Известные в настоящее время методы сжатия не удовлетворяют в полной мере сформулированным выше требованиям, что делает актуальными разработку и исследование методов сжатия изображений, получаемых при дистанционном зондировании Земли.
Актуальность названных задач подчеркивается в целом ряде научно-технических программ, в числе которых, в частности федеральная целевая научно-техническая программа «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 г., в рамках которой (Блок 2 - «Поисково-прикладные исследования и разработки», раздел «Информационные технологии», Тема № 32 «Модели и алгоритмы
кодирования и сжатия информации») были получены основные результаты, представленные в настоящей диссертационной работе.
В диссертационной работе развиваются выполненные ведущими российскими и зарубежными специалистами исследования по проблематике кодирования источника, пионерский вклад в которые внесли Р. Галлагер, С. Голомб, М. Вайнбергер, Ш. By, Г. Лэнгдон, Р. Райе, В,Ф. Бабкин, Ю.М. Штарьков и др.
Необходимо отметить также фундаментальные работы ученых новосибирской школы в области теоретико-информационных методов кодирования источника, авторами которых являются Р.Е. Кричевский, Б.Я. Рябко, В.К. Трофимов.
Практические методы сжимающего кодирования изображений разрабатывались в Институте проблем передачи информации РАН работами ДС. Лебедева и Л.П. Ярославского. Представленные подходы могут рассматриваться как составляющая часть работ, опубликованных ранее.
Применительно к задачам' дистанционного зондирования Земли из космоса теория и практика сжатия изображений разрабатывалась и успешно применялась многими специалистами, в числе которых И.Б. Фоменко (Зеленоград), В.В. Сергеев, Н.И. Глумов, М.А. Чичева (Самара) и др.
Цель диссертационной работы состоит в разработке и исследовании методов сжатия изображений для задач дистанционного зондирования Земли, обеспечивающих постоянство скорости сжимающего кодирования и предназначенных для реализации на базе бортовых вычислительных комплексов ограниченной технической оснащённости.
В рамках проводимого исследования решались следующие задачи:
Анализ существующих подходов и методов сжатия с целью определения возможности их модификации для использования в бортовых системах сжатия изображений.
Синтез на основе метода усечённого блочного кодирования алгоритмов сжатия изображений, обладающих малой вычислительной сложностью и обеспечивающих постоянство скорости сжимающего
7 кодирования при значительном сокращении, по сравнению с известными реализациями, уровня вносимых в процессе кодирования искажений,
3. Построение и исследование улучшенной адаптивной схемы
статистического сжатия на основе кода Голомба в качестве эффективной
альтернативы динамическому хаффменовскому и арифметическому кодированию.
Разработка схемы трансформационного кодирования изображений на базе двумерного дискретного косинус-преобразования, обеспечивающей постоянство средней скорости сжимающего кодирования и обладающей малой ресурсоёмкостью и невысокой вычислительной сложностью.
Разработка схемы сжатия изображений на основе адаптивного контекстного предсказателя с уровнем потерь, гарантированно не превосходящим заданного, также обеспечивающей постоянство средней скорости сжимающего кодирования.
Методы исследования
Для проведения исследований в рамках диссертационной работы использовались методы прикладной теории информации, теории кодирования источника, математической статистики. Экспериментальные исследования строились на основе программной реализации алгоритмов с последующей оценкой полученных результатов, включающей сравнение с доступными по публикациями в специальной литературе экспериментальными данными.
Научная новизна диссертационной работы
В диссертационной работе получены следующие новые научные результаты:
Предложена модификация метода усечённого блочного кодирования (УБК) [45], базирующаяся на эффективной процедуре выбора пороговых уровней при квантовании, обеспечивающая близкий к минимальному уровень искажений. Среднеквадратическая ошибка при использовании предложенной процедуры выбора отличается от минимально-возможной для метода УБК в среднем на 4%.
Разработана оригинальная методика использования согласованных процедур пре- и постфильтрации, позволяющая в среднем более чем вдвое сократить среднеквадратическую ошибку при сжатии изображений методом УБК.
Предложен метод сокращённой передачи уровней квантования кодируемых блоков при сжатии изображений методом УБК, позволяющий при четырёх и более уровнях квантования использовать в 1.5-2 раза меньший размер блока с сохранением прежнего коэффициента сжатия и уровня искажений.
Разработана улучшенная однопроходная адаптивная схема статистического сжатия на основе кода Голомба (АКТ) [28].
Получена теоретическая оценка избыточности АКТ как функции числа отсчётов, по которому определяется параметр кода Голомба.
Построена схема сжатия изображений на основе двумерного дискретного косинус-преобразования (ДКП) с использованием АКТ для кодирования коэффициентов ДКП, обеспечивающая значительно (в среднем - в 2.5 раза) более высокую производительность кодера и одновременно на 5% большую степень сжатия изображений, чем JPEG [63] с арифметическим кодированием.
Предложена эффективная методика оценки параметра кода Голомба по взвешенному среднему с коррекцией при сжатии изображений с использованием адаптивного контекстно-зависимого предсказателя.
Разработана методика сжатия изображений на основе ДКД обеспечивающая постоянство средней скорости сжимающего кодирования.
Разработана методика сжатия изображений на основе адаптивного контекстно-зависимого предсказателя, также обеспечивающая постоянную среднюю скорость сжимающего кодирования, с уровнем потерь, гарантированно не превосходящим заданного.
Практическая ценность результатов
Разработано семейство алгоритмов сжатия изображений, обеспечивающих постоянство скорости сжимающего кодирования, ориентированных на использование в бортовых вычислительных комплексах ограниченной технической оснащённости, в том числе построенных на базе сигнальных процессоров и ПЛИС.
Предложенные в ходе выполнения диссертационной работы алгоритмы сжатия реализованы в виде набора библиотечных программных модулей, написанных на языке Си, а также в виде самостоятельных
9 консольных Win32-пpилoжeний, позволяющих сжимать и восстанавливать изображения с заданными коэффициентами сжатия.
Алгоритмы, предложенные и описанные автором в диссертационной работе, были использованы при разработке проекта бортовой системы сжатия видеоданных, получаемых от комплекса дистанционного зондирования Земли среднего разрешения космического аппарата «МЕТЕОР-М».
Применение предложенного автором метода сжимающего кодирования при разработке проекта «Солнечный парус» позволило реализовать возможность сжатия изображений с использованием бортового вычислительного устройства малой производительности,
Разработанная простая адаптивная схема статистического сжатия на основе кода Голомба, не требующая применения кодовых таблиц и вычислений с плавающей точкой, используется в программе сжатая без потерь и с ограниченными потерями полутоновых черно-белых и многокомпонентных цветных изображений с большим числом уровней квантования (8-16 бит на компоненту), зарегистрированной в ВНТИЦ под региарационным номером 50200500007.
Апробация и внедрение результатов работы
Алгоритмы, предложенные и описанные автором в диссертационной работе, были использованы при разработке проекта обеспечивающей постоянную скорость сжимающего кодирования бортовой системы сжатия видеоданных, получаемых от комплекса дистанционного зондирования Земли среднего разрешения космического аппарата "МЕТЕОР-М", а также в программе сжатия без потерь и с ограниченными потерями полутоновых черно-белых и многокомпонентных цветных изображений с большим числом уровней квантования (8-16 бит на компоненту), подготовленной к реализации в рамках федеральной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 г. в сотрудничестве с Институтом проблем передачи информации РАН.
Применение предложенного автором метода сжимающего кодирования на основе ДКП и АКТ при разработке проекта «Солнечный парус» позволило реализовать возможность сжатия изображений с использованием бортового вычислительного устройства малой производительности.
Основные положения и результаты диссертационной работы докладывались на I и III Всероссийских открытых конференциях «Современные проблемы дистанционного зондирования Земли из космоса» в 2003 и 2005 годах, на 11-й Всероссийской конференции «Математические методы распознавания образов ММРО-11», на семинаре Института космических исследований РАН «Современные и перспективные разработки и технологии в космическом приборостроении» в 2004 году.
Подготовленные в рамках федеральной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 г., Блок 2 - «Поисково-прикладные исследования и разработки», раздел «Информационные технологии», Тема № 32 <(Модели и алгоритмы кодирования и сжатия информации» научно-технические отчеты по теме «Разработка алгоритмов и программных средств неискажающего сжатия и сжатия с ограниченными потерями многокомпонентных изображений» зарегистрированы во ВНТИЦ за 2002-2004 г. Отчет за 2004 г. был отмечен премией на конкурсе научных работ ИКИ РАН в номинации «Научно-технические отчёты».
Публикации
По теме диссертации опубликовано шесть работ. На защиту выносятся следующие положения:
Модифицированный метод усечённого блочного кодирования с альтернативным алгоритмом выбора пороговых уровней при квантовании и согласованными процедурами пре- и постфильтрации кодируемых изображений.
Разработанная автором оригинальная реализация адаптивного кода Голомба и её использование в схемах сжатия изображений на основе предсказателя и дискретного косинус-преобразования.
3. Алгоритмы сжатия изображений с постоянной скоростью сжимающего кодирования на основе адаптивного контекстно-зависимого предсказателя и дискретного косинус-преобразования.
Струетура работы
В первой главе даются базовые понятия и определения. Вводятся понятия класса изображений, искажающего и неискажающего сжатия, рассматриваются объективные и субъективные критерии точности восстановления изображений, формулируются основные требования к алгоритмам сжатия видеоданных в задачах ДЭЗ.
Применительно к сформулированным требованиям рассматриваются стандартизованные подходы и наиболее известные алгоритмы сжатия, определяется потенциальная возможность их бортовой реализации с точки зрения эффективности сжимающего кодирования, вычислительной сложности и ресурсоёмкое. Здесь же описываются распространённые статистические методы сжатия (коды Хаффмена, Голомба, арифметический код), ориентированные на совместное использование как с трансформационными методами кодирования, так и с. методами, построенными на основе предсказателей. Приводятся оценки избыточности схем статистического сжатия в случае известной статистики источника, рассматриваются особенности реализации адаптивных схем кодирования источников с неизвестными статистическими свойствами.
Во второй главе описывается предложенная автором модификация метода усечённого блочного кодирования (УБК), базирующаяся на эффективной процедуре выбора пороговых уровней при квантовании, а также на использовании согласованных процедур пре- и постфильтрации, что позволяет в среднем более чем вдвое уменьшить среднеквадратическую ошибку при сжатии изображений методом УБК. Рассматривается также метод сокращённой передачи уровней квантования кодируемых блоков, позволяющий при четырёх и более уровнях квантования использовать в 1.5-2 раза меньший размер блока с сохранением прежнего коэффициента сжатия и уровня искажений,
12 В третьей главе описана предложенная автором простая адаптивная схема статистического сжатия на основе кода Голомба (АКГ), получена теоретическая оценка избыточности АКГ как функция числа отсчётов, по которому определяется параметр кода Голомба. Рассмотрены разработанные практические реализации сжимающих кодеров на базе ДКП и адаптивного предсказателя, построенные с использованием АКГ.
В четвёртой главе рассмотрены модифицированные схемы сжатия изображений на основе двумерного дискретного косинус-преобразования и адаптивного контекстно-зависимого предсказателя, позволяющие обеспечить постоянство скорости сжимающего кодирования, приведены оценки алгоритмической сложности предложенных схем сжатия, а также результаты их практического использования,
Требования, предъявляемые к алгоритмам сжатия изображений в задачах ДЗЗ. Постановка задачи
При дистанционном зондировании Земли из космоса установленная на борту КА съемочная аппаратура генерирует поток видеоданных, который затем должен быть транслирован по радиоканалу на наземные приемные станции, зарегистрирован и передан потребителям. Если информативность съёмочной аппаратуры превышает пропускную способность канала связи, передача всего генерируемого информационного потока потребителю оказывается невозможной, однако, как было отмечено выше, получаемые изображения обладают значительной информационной избыточностью, что дает возможность их представления в более компактной форме посредством сжимающего кодирования.
Выделяют психовизуальную, определяемую особенностями человеческого восприятия, и статистическую избыточность, которую в свою очередь подразделяют на межэлементную, в основе которой высокая степень коррелированное соседних пикселов, и частотную (кодовую), связанную с локальной или глобальной неравномерностью распределения яркостей изображения [1]. Сжимающий кодер характеризуется обеспечиваемыми им коэффициентом сжатия (или скоростью сжимающего кодирования), битовой скоростью на выходе и производительностью. Отношение объема данных на входе кодера к объему сжатых данных называется коэффициентом сжатия (ЛГ ). Следует отметить, что коэффициент сжатия определяется используемыми алгоритмами и особенностями сжимаемых видеоданных и в общем случае не является постоянным. Эффективность кодера может быть охарактеризована также скоростью сжимающего кодирования, определяемой как количество кодовых бит, приходящихся на кодируемый символ источника. Кодер, имеющий больший коэффициент сжатия, обеспечивает меньшую скорость сжимающего кодирования.
Под информационной (битовой) скоростью на выходе кодера понимают величину потока данных, поступающих с выхода кодера в единицу времени, которая измеряется в случае двоичных данных в битах в секунду (бит/сек., англ. bps). Под производительностью кодера понимают максимальную величину потока видеоданных, поступающих на вход кодера, которую он способен обработать (сжать) в единицу времени (также измеряемую обычно в бит/сек.).
Сжатые видеоданные (изображения) транслируются затем по радиоканалу на наземные приемные станции, где происходит их регистрация. Для обеспечения возможности передачи генерируемого потока видеоданных по радиоканалу и рационального использования радиоканала информационная скорость на выходе кодера должна быть согласована с пропускной способностью канала
Перед использованием полученных видеоданных необходимо осуществить их восстановление. Эта процедура выполняется либо аппаратным декодером, либо реализуется с использованием вычислительных устройств приемной станции.
В случае записи потока видеоданных на бортовое запоминающее устройство для последующей их трансляции сжатие целесообразно осуществлять до поступления информации в накопитель, т.к. при этом обеспечивается более компактное хранение и, следовательно, возрастает информационная емкость накопителя.
В зависимости от обеспечиваемой точности восстановления выделяют два типа сжатия исходных данных - с потерями и без потерь, Если восстановленное изображение в точности совпадает с исходным, то говорят о сжатии "без потерь" или о неискажающем сжатии. Если восстановленное изображение отличается от исходного, то сжатие называется искажающим или "с потерями". При разработке методов сжатия получаемых при ДЗЗ видеоданных необходимо учитывать ряд специфических, часто противоречивых, требований и ограничений: 1. Высокая скорость генерирования исходной видеоинформации съемочными устройствами ДЗЗ и необходимость сжатия видеоданных в реальном времени для обеспечения согласованности выходного потока кодера и радиоканала накладывает ограничения на вычислительную сложность применяемых методов сжатия, исключая, в частности, использование многопроходных схем. 2. Необходимость реализации сжатия бортовыми вычислительными средствами КА определяет жесткие требования к объему используемой кодером памяти. Кроме того, массово-габаритные, энергетические и технологические ограничения делают нежелательным, а зачастую и невозможным использование выравнивающих выходной поток буферных запоминающих устройств большой емкости и ограничивают допустимый объем оперативного буфера несколькими строками генерируемых съемочной аппаратурой изображений. 3. Необходимость согласования потока сжатых видеоданных с пропускной способностью радиоканала при передаче на наземные приемные станции диктует требование обеспечения кодером постоянной скорости сжимающего кодирования (коэффициента сжатия) в пределах оперативного буфера, который теоретически может быть получен только при использовании методов сжатия с потерями. 4. Получаемые при ДЗЗ видеоданные подвергаются последующей сложной обработке для решения разнообразных прикладных задач в интересах множества научных, хозяйственных и оборонных отраслей. В отсутствии практической возможности сжатия видеоданных без потерь с требуемым постоянным коэффициентом сжатия компромиссное решение может заключаться в организации сжатия видеоданных с ограниченными потерями, не превышающими заданного уровня (по абсолютной величине либо по предельно-допустимому значению отношения сигнал/шум). 5. Недопустимым является появление в восстановленных видеоданных артефактов, нарушающих геометрическую структуру изображений и затрудняющих последующую интерпретацию результатов обработки. 6. В случаях, когда наибольшим препятствием к использованию восстановленных с потерями видеоданных является не сам факт наличия искажений, а невозможность оценки достоверности получаемых результатов обработки, передаваемые потребителям восстановленные видеоданные должны шпровождаться информацией о максимальной ошибке, обусловленной проведенным сжатием. 7. В случае трансляции несжатых видеоданных ДЗЗ их возможные искажения в радиоканале не являются критичными, так как отдельные ошибочно принятые биты приводят к искажениям значений яркости только отдельных пикселов, а отдельные пропущенные биты ведут к сбою синхронизации и потере отдельных строк в принятых изображениях. При использовании сжатия следствием искажения даже единичного бита может явиться существенное необратимое повреждение всего восстанавливаемого изображения или, по крайней мере, той его части, которая следует после сбойного пиксела Поэтому используемые для сжатия видеоданных ДЗЗ алгоритмы должны оперировать отдельными блоками строк изображений и обеспечивать нераспространение искажений, вызываемых сбоями при передаче отдельных битов внутри блока, за его пределы.
Таким образом, кодер, ориентированный на бортовую реализацию в системах сжатия видеоданных, получаемых при дистанционном зондировании Земли из космоса, должен удовлетворять перечисленным выше требованиям. Однако, возможные области применения такого кодера, очевидно, задачами ДЗЗ не ограничиваются.
Сравнительный анализ эффективности использования предложенной модификации метода УБК
Для определения контекста вычисленные значения локальных градиентов di, d2, di квантуются до значений qj, q2 Цъ таким образом, что каждое #, (/=1,2,3) может принимать (2Д + 1) значений из диапазона [-R,R] (общее число различных qh очевидно, составляет 2Л+1). В отличие от стандартизованной упрощённой версии кодера, оперирующей для определения контекста тремя локальными градиентами, кодер LOCO использует также градиент d4, который квантуется грубее, при этом общее число квантованных значений равно (2Г+1), где T R. Набор квантованных локальных градиентов q}, q2, q3, q4 определяет номер контекста, число которых есть (2Г+1)х(2# + I)3. Для R =4, Т=\ общее число контекстов составляет 2187. Дня сокращения числа контекстов используется следующий приём: если qt О, то знаки всех qt инвертируются. Поскольку при этом qi принимает только положительные значения (0, 1, ..., R), число контекстов сокращается вдвое. Таким образом, число контекстов есть ((2Г+1)х(2й +1)3+1)/2, что при R=4, Т=\ составляет 1094. При использовании стандартизованной версии кодера число контекстов равно 365. Для каждого определённого таким образом контекста считаются сумма ошибок предсказания Err и их число Z, что позволяет вычислить поправку для текущего пиксела.
При кодировании в режиме near lossless с ошибкой, не превосходящей по абсолютной величине заданного порога N, ошибка предсказания Err квантуется. Квантованное значение вычисляется как
При декодировании с использованием квантованных ошибок предсказания восстановленные значения пикселов, используемые для вычисления ошибки предсказания для последующих пикселов, очевидно, будут отличаться от оригинальных, что сделает декодирование невозможным. Чтобы избежать этого, кодер деквантует ErrQ, восстанавливает по предсказанному исходное значение пиксела (с ошибкой, не превосходящей по абсолютной величине N) и заменяет им оригинальный пиксел. При кодировании последующих пикселов кодер будет использовать модифицированное таким образом значение для вычисления ошибок предсказания.
Ошибка предсказания, вычисляемая как разность между исходным значением интенсивности пиксела и предсказанным с коррекцией значением, в целочисленном представлении, как показано в частности, в [25,43,44], имеет распределение, близкое - к двустороннему геометрическому, что позволяет использовать для её статистического кодирования построенный на принципе Голомба [23] кодер (см. раздел 1.4.2.3). Стандарт JPEG-LS предусматривает использование т.н. кодера Голомба-Райса [38]. LOCO допускает также использование арифметического кодирования для сжатия ошибки предсказания, но в стандарт эта опция включена не была.
Заметим, что код Голомба определён для неотрицательных величин, тогда как ошибка предсказания, имеющая двустороннее распределение, может принимать также и отрицательные значения. Поэтому перед статистическим кодированием значение Err преобразуется в соответствии с правилом: 6. Для повышения устойчивости кодированных данных к возможным повреждениям при передаче и хранении стандарт предусматривает разбиение кодируемых данных на порции (рестарт-интервалы) таким образом, что кодирование данных в пределах каждой ведётся независимо и без ссылок на данные из других порций, однако, использование механизма рестарт-интервалов приводит к снижению эффективности сжатия. Величина рестарт-интервала может быть задана при кодировании. Сравнение эффективности сжатия с использованием кодера JPEG lossless mode и JPEG-LS демонстрирует заметное превосходство последнего (типичные коэффициенты сжатия без искажений при использовании JPEG-LS - 1.8-2.5). С точки зрения производительности JPEG-LS-кодер незначительно уступает JPEG-кодеру в режиме сжатия с потерями с использованием статического кода Хаффмена для сжатия квантованных коэффициентов ДКП. К недостаткам JPEG-LS с точки зрения возможности его использования для сжатия изображений. ДЗЗ следует прежде всего отнести низкую устойчивость кодированных данных к возможным искажениям при передаче, что, впрочем, характерно для всех методов сжатия, использующих предсказатели. Сравнение JPEG-LS с другими методами сжатия без потерь и с ограниченными потерями (CALIC, DaRT и др.) показывает его относительно невысокую эффективность, что, очевидно, связано со стремлением разработчиков обеспечить максимальное быстродействие кодера в ущерб эффективности. 1. В разделе были сформулированы основные требования, предъявляемые к алгоритмам сжатия изображений, получаемых при дистанционном зондировании Земли. Были рассмотрены основные методы, алгоритмы и подходы к сжатию изображений с точки зрения возможности их бортовой реализации. 2. Анализ наиболее распространённых методов сжатия, построенных как на основе предсказателя, так и использующих частотные преобразования, показал, что непосредственное использование их для сжимающего кодирования изображений в задачах ДЗЗ невозможно. Однако, модификации рассмотренных методов, обеспечивающие постоянство коэффициента сжатия, могли бы рассматриваться в качестве преимущественных кандидатов на бортовую реализацию для сжатия изображений в задачах ДЗЗ. 3. Сравнительный анализ статистических методов кодирования с точки зрения возможности их использования в бортовых схемах сжатия изображений позволил выявить ряд серьёзных недостатков, свойственных получившим широкое распространение хаффменовскому и арифметическому кодированию, связанных как с недостаточной эффективностью их статических реализаций, так и с высокой вычислительной сложностью адаптивных подходов. В то же время, простая адаптивная модификация кода Голомба позволила бы строить эффективные схемы сжатия, пригодные для бортовой реализации. 4. Использование метода УБК для сжимающего кодирования изображений, получаемых при дистанционном зондировании Земли, возможно лишь при условии значительного сокращения привносимых при сжатии искажений.
Результаты применения АКГ при сжатии изображений в схеме кодирования с использованием адаптивного предсказателя
Для кодирования коэффициентов DC стандарт JPEG предусматривает использование простейшего ДИКМ-предсказателя: вместо ВСц кодируется ошибка предсказания, т.е. разность DCy - DCy.;, где DCy.] - коэффициент Fo,o, соответствующий блоку 8x8 изображения, расположенному слева от текущего. Для статистического кодирования полученных разностей, как и для АС, используется либо хаффменовское, либо арифметическое кодирование.
Заметно большей эффективностью при кодировании DC обладает предложенный автором подход, базирующийся на использовании MED-предсказателя (1.24) в сочетании с АКТ, выигрыш от применения которого по сравнению со схемой, использующей стандартный предсказатель ДИКМ, составляет в среднем на серии тестовых изображений от 0.5 до 3.2% (в зависимости от требуемой степени сжатия), причём большей степени сжатия соответствует и больший эффект от применения MED-предсказателя. Заметим, что для кодирования ошибки предсказания DC, как и для кодирования АС, эффективным оказывается раздельное кодирование отличных от нуля ошибок предсказания и нулевых серий с независимой оценкой параметра кода Голомба.
Дополнительного выигрыша можно добиться использованием для сжатия DC адаптивных контекстно-зависимых предсказателей, применяемых в ориентированных на неискажающее сжатие схемах, реализующих стандарт JPEG-LS, а также в кодерах DaRT, CALIC и др. Такой подход, в частности, был предложен в [36]. Однако, для практического применения в большинстве случаев это решение представляется неоправданно громоздким, Эксперименты показали, что выигрыш в сжатии изображений, обеспечиваемый таким подходом по сравнению с использованием MED-предсказателя, составляет 0,1-0.8%, что явно неадекватно усложнению процедуры кодирования.
В табл. 3.6 приведены размеры (в байтах) упакованных массивов DC для серии тестовых чёрно-белых полутоновых изображений (стандартный тестовый набор JPEG, тот же, что и в [36]) при сжатии с параметрами качества Q = 70, 85 и 100 с использованием простейшего предсказателя ДИКМ, ,МЕ -предсказателя и, кодера DaRT, обладающего большей эффективностью, нежели используемый в стандарте JPEG-LS. В нижней строке таблицы указан суммарный эффект (сокращение объёма упакованного набора тестовых файлов) от использования соответствующего способа сжатия DC (в %).
В разделе 3.1 настоящей работы отмечалось, что оценка параметра / кода Голомба с использованием скользящего окна из некоторого количества закодированных ранее символов в наиболее простом одномерном случае сводится к двум операциям сложения и одному сдвигу. При использовании раздельного кодирования коэффициентов ДКП (см. 3.3.2) при сжатии серий равных нулю коэффициентов (или ошибок предсказания) использование такой «одномерной» оценки (рис. 3.1) представляется единственно возможной. В то же время, для сжатия отличных от нуля коэффициентов более эффективной, как продемонстрировали проведённые автором эксперименты (табл. 3.8, 3.9), является оценка / по локальному двумерному окружению (рис. 3.7) кодируемого коэффициента, что, впрочем, вполне предсказуемо (см. рис. 3.6).
Оценка параметра кодирования / по содержимому скользящего окна, несмотря на меньшую точность, может оказаться предпочтительной в тех случаях, когда для повышения устойчивости кодированных данных к возможным искажениям в канале связи или для минимизации объёма рабочего буфера кодера используется сегментация изображения. При использовании ДКП с размером блока 8x8 каждый сегмент изображения должен, очевидно, состоять не менее, чем из 8 пиксельных строк. При вычислении оценки / по локальному двумерному окружению используются также коэффициенты ДКП, соответствующие пиксельным блокам из расположенных выше 8 (16, 24 и т.д.) строк изображения, что увеличивает размер минимальной порции кодируемых данных. При этом оценка параметра / по двумерному окружению для коэффициентов ДКП из первых 8 строк такой порции, очевидно, оказывается невозможной, Эксперименты показали, что надёжность оценки параметра / по скользящему окну с использованием (3.4) может быть повышена, если использовать вместо суммы значений к уже закодированных коэффициентов ДКП 2-і ai их взвешенную сумму 2-і wi ai (условие нормировки - 2-, wi = к) с весами, обратно пропорциональными расстоянию до соответствующего коэффициента ДКП. На практике выбор набора весовых коэффициентов представляет собой компромисс между эффективностью и вычислительной сложностью. Так, например, случае к = 11 использование простого набора весовых коэффициентов W = {4, 2, 1, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5} обеспечивает в среднем на серии тестовых изображений коэффициент сжатия на 0.01% меньший, чем значительно более сложный в вычислительном отношении набор W = {3.643, 1.821, 1.214, 0.911, 0.729, 0.607, 0.520, 0.455, 0.404, 0.364, 0.331). Тот же- приём эффективен и в случае двумерной оценки параметра / (см. рис. 3.10, 3.11), но положительный эффект при этом оказывается менее выраженным.
Влияние искажений при передаче на возможность восстановления изображений, сжатых с постоянной скоростью сжимающего кодирования
Забегая вперёд, заметим, что использование приведённой в таблице последовательности размещения вместо стандартного зигзага JPEG позволило экспериментальному кодеру при фиксированном коэффициенте сжатия получить на 0.1-0,3 dB большее отношение сигнал/шум,
После размещения в рабочем буфере каждый коэффициент рассматривается как принадлежащий к одной из четырех групп. Образующие первую группу наиболее значимые коэффициенты ДКП непосредственно кодируются с использованием разработанной автором и описанной в Главе 3 диссертационной работы модификации адаптивного кода Голомба.
Коэффициенты второй группы кодируются с предварительным сдвигом на один двоичный разряд вправо, а содержимое младших (потерянных при сдвиге) разрядов объединяется в байты и помещается в дополнительный буфер коррекции.
Образующие третью и четвертую группы коэффициенты кодируются с предварительным сдвигом соответственно на 2 и 3 бита, а их оставшиеся незакодированными младшие разряды также записываются в массив коррекции, сначала старшие разряды, затем - младшие. На рис. 4.2 образующие каждую группу коэффициенты выделены одинаковыми оттенками серого (для одного из возможных вариантов деления коэффициентов на группы).
Общая структурная схема модифицированного кодера на основе ДКП приведена на рис. 4.3. В целом она напоминает структурную схему JPEG-кодера, с тем, однако, отличием, что вместо квантователя здесь используется блок сепаратора, обеспечивающего разделение кодируемых данных на регулярную и корректирующую составляющие.
Сжатые с использованием АКТ коэффициенты ДКП (регулярная составляющая кодированных данных) размещаются в выходном буфере, размер которого определяется заданным коэффициентом сжатия. В оставшуюся незаполненной часть буфера записывается содержимое массива коррекции, причем непосредственно, без использования статистического кодирования, которое в случае близкого к равномерному распределению кодируемых данных малоэффективно. Исследование показало, что, например, энтропия корректирующей компоненты коэффициентов четвёртой группы составляет в среднем по серии тестовых изображений 2.8-2.9 бита, в то время как для их равномерного кодирования требуется, очевидно, 3 бита на компоненту. С учётом удельного веса корректирующей составляющей в общем массиве кодированных данных потери при этом составляют в среднем не более 2%.
В описанной в разделе 3.3 схеме сжимающего кодирования на основе косинус-преобразования для повышения коэффициента сжатия использовалось предсказание шести коэффициентов ДКП (DC, AC0i, АСю, ACQ2, AC2Q И AC Л) no DC блоков 8x8 из локальной окрестности кодируемого блока. В рассматриваемой модификации схемы ссылки на DC блоков, находящихся за пределами кодируемой полосы из 8 строк изображения, очевидно, недопустимы, поэтому использование предсказания возможно лишь для ACQI и АСо2 (в соответствии с (3.13а) и (3.13с)), a DC кодируемого блока предсказывается по DC предыдущего блока 8x8 без использования MED-предсказателя, что отрицательно сказывается на эффективности сжатия по сравнению с описанной в разделе 3.3 схемой. При кодировании с постоянной скоростью сжимающего кодирования снижение эффективности сжатия приводит к уменьшению точности восстановления сжатого изображения.
В разделе 3.3.5 отмечалось, что при использовании статистического сжатия на основе АКГ наиболее эффективной оказывается оценка параметра кода Голомба по локальному двумерному окружению отличных от нуля кодируемых коэффициентов ДКП, а при кодировании серий нулевых коэффициентов - оценка по содержимому скользящего окна. В рассматриваемой модификации схемы сжатия двумерное окружение коэффициента оказывается недоступным, поэтому оценка параметра кода Голомба в обоих случаях производится однотипно, с использованием скользящего окна из 22 предшествующих кодируемому отсчётов (см. рис. 3.1) в соответствии с (3.4).
Разбиение массива коэффициентов на группы осуществляется таким образом, чтобы регулярная составляющая кодируемых данных при заданном коэффициенте сжатия гарантированно разместилась в выходном буфере (экспериментальное определение размеров и границ групп проводилось по результатам моделирования с использованием представительных серий типичных изображений ДЗЗ). Следует заметить, что результатом крайне маловероятного переполнения выходного буфер даже в случае полной потери массива коэффициентов F7? будет лишь незначительное повышение уровня искажений текущей полосы из 8 строк изображения. Так, например, для использованного при построении табл. 4.1 изображения LSTM1 такая потеря означает снижение уровня PSNR восстановленного изображения (на 1.077 dB) и приводит к незначительному расширению диапазона ошибок. При этом в диапазоне [-1,1] оказывается 99.83% ошибок, а в диапазоне [-3,3] - 99.996%.
При необходимости обеспечения работоспособности кодера в широком диапазоне коэффициентов сжатия Ксж может быть использовано несколько вариантов разбиения, каждый из которых соответствует своему поддиапазону Ксж. Заметим, что при заданном Ксж разбиение массива коэффициентов на группы для всех кодируемых восьмистрочных блоков изображения в простейшем случае осуществляется блоком сепаратора единообразно.
Альтернативой такому статическому сепаратору может служить адаптивная схема, динамически меняющая правила разбиения в зависимости от степени заполнения выходного буфера регулярной составляющей кодируемых данных. Более простое (полуадаптивное) решение состоит в том, что правило разбиения для кодирования текущего восьмистрочного блока выбирается по результатам кодирования предыдущего блока. Простота такого подхода делает его более привлекательным для бортовой реализации алгоритма сжатия.
Если в выходном буфере оказывается возможным размещение не только регулярной, но и корректирующей составляющей, ошибка восстановления изображения определяется точностью реализации процедур прямого и обратного косинус-преобразования (и, как было отмечено выше, необходимостью целочисленного представления коэффициентов ДКП). Чем выше заданный коэффициент сжатия, тем выше вероятность того, что в выходной буфер попадёт лишь часть массива коррекции, следствием чего станет снижение точности восстановления декодируемого восьмистрочного блока (см. рис. 4.4). В связи с этим при заполнении выходного буфера целесообразно сразу же вслед за регулярной составляющей кодируемых данных разместить соответствующую центральной области изображения часть корректирующего массива. Такой подход, очевидно, согласуется со свойствами используемого при съёмке объектива камеры, обеспечивающего большее пространственное разрешение для центральной части изображения.
