Содержание к диссертации
Введение 5
1. Анализ методов сжатия изображений с потерями v 12
1.1. Основные принципы сжатия изображений с потерями 13
Устранение избыточности сигнала. Основные этапы сжатия 13
Классы искажений и способы их устранения 15
Подходы к оценке качества и степени сжатия изображений 17
RD-теория и оптимизация схем сжатия на ее основе 23
1.2. Современные технологии сжатия изображений с потерями 27
Классификация методов сжатия с потерями 27
Основные схемы сжатия с потерями 31
Недостатки современных алгоритмов сжатия. Постановка задачи. 33
1.3. Основные результаты и выводы 34
2. Исследование методов компрессии цифровых изображений на основе
адаптивных преобразовании 36
2.1. Адаптивные методы сжатия статических изображений 36
Применение спектральных преобразований 36
Адаптивное квантование сигнала 37
Статистические методы сжатия и их сравнительный анализ 41
2.2. Сжатие на основе адаптивной сегментации 47
Сжатие на основе выделения растровых областей 49
Сжатие на основе векторной сегментации 51
Недостатки алгоритмов сжатия на основе адаптивной сегментации. Постановка задачи 53
2.3. Основные результаты и выводы 55
3. Развитие методов сжатия изображений с применением алгоритмов
векторной сегментации 56
3.1. Использование квадродеревьев для адаптивной сегментации в
алгоритмах компрессии 57
Сжатие изображений на основе простых квадродеревьев 57
Оптимизация квадродерева методом усечения веток на основе функции цены Лагранжа.... 60
3.2. Обработка и кодирование локальных областей, полученных в
результате сегментации 63
Использование критерия однородности 63
Критерий для оценки выраженности текстуры локальной области 65
Аппроксимация сегментов изображения на основе бимлетного и веджлетного базисов 67
Геометрическая аппроксимация в трехмерном пространстве 68
3.3. Древовидные структуры в методах сегментации на основе
последовательного разделения областей 71
Сегментация на основе kd-деревев 71
Сегментация на основе построения BSP-деревьев 73
Сегментация на основе обобщенных квадродеревьев 75
3.4. JPEG-подобная схема компрессии с адаптивной сегментацией на
основе построения kd-дерева 75
3.5. Метод сжатия изображений на основе пространственной
декомпозиции сигнала 81
Декомпозиция и сжатие сигнала в трехмерном пространстве 82
Применение декомпозиции в горизонтальном направлении 84
Пример практической реализации и результаты экспериментов.... 86
3.6. Основные результаты и выводы 88
4. Исследование и разработка методов сжатия на основе адаптивного
квантования 89
4.1. Энтропийные функции оценки степени сжатия изображения 91
4.1.1. Применение канонических подходов вычисления энтропии 91
Определение энтропийной функции для схем сжатия, включающих кодирование длин серий 92
Энтропия квантованных значений 93
4.2. Методы RD-оптимизации таблиц квантования 94
Однонаправленная оптимизация. Метод Ву-Гершо 94
Двунаправленная оптимизация. Метод Фунга-Паркера 97
Схема RD-OPT 99
Генерация векторов квантования на основе весового критерия 101
Адаптивное квантование на основе весового критерия в схемах
сжатия с векторной сегментацией 113
4.5. Основные результаты и выводы 115
Заключение 116
Список литературы 117
Введение к работе
Проблема передачи и хранения информации, представленной в цифровом виде, является одной из самых важных в вычислительной технике. Для получения компактного представления данных используются различные технологии сжатия. Их применение позволяет получить значительный выигрыш в ресурсах при эксплуатации носителей информации и повысить эффективность передачи данных по каналам связи.
На сегодняшний день наибольший объем данных соответствует изображениям, видеоданным и звуку. Как показывает практика, применение методов сжатия без потерь не приводит к существенному сокращению их информационного представления, поэтому актуальной задачей становится исследование методов сжатия с потерями, ориентированных на конкретные типы данных. Подобные методы сжатия должны использовать индивидуальные особенности сжимаемого сигнала, включать в себя адаптивные механизмы его обработки и учитывать особенности восприятия соответствующей информации человеком.
За последние десятилетия значительное развитие получили системы хранения и обработки цифровых изображений. На данный момент уже существуют хранилища данных, насчитывающие сотни миллионов оцифрованных изображений. Такие базы данных используются в самых разнообразных областях, например, в медицине (рентгеновские снимки), криминалистике (отпечатки пальцев), в сервисах для хранения фотографий в сети Интернет. Вследствие этого, затрачиваются значительные усилия на разработку новых технологий, позволяющих повысить эффективность сжатия цифровых изображений. Для этого широко применяется адаптивная обработка сигнала, в частности, с использованием адаптивной сегментации. Этой проблеме посвящена данная диссертационная работа.
Стоит также отметить, что задача сжатия изображения решается и при сжатии видеоданных на этапе устранения пространственной избыточности
опорных І-кадров. Наряду с этим, задача сегментации решается и при устранении временной зависимости — на этапе построения векторов движения [16].
Цель работы — исследование существующих и разработка новых методов сжатия цифровых изображений, использующих адаптивные преобразования — сегментацию на основе иерархической декомпозиции сигнала и процедуру адаптивного квантования, а также поиск возможных путей повышения эффективности применения этих методов.
Выбранное направление работы основано на анализе современных методов сжатия изображений с потерями. На сегодняшний день, в связи с развитием средств вычислительной техники, становится возможной реализация комплексных схем сжатия, требующих большого объема вычислений. Так, если первые методы сжатия опирались на простые, легко реализуемые преобразования, то современные алгоритмы сжатия включают в себя составную адаптивную обработку сжимаемого изображения с применением совокупности приемов кодирования разного типа.
Задачи исследования. В рамках диссертационного исследования решались следующие задачи:
Анализ основных типов адаптивных преобразований, используемых в схемах сжатия с потерями.
Повышение эффективности существующих схем сжатия, использующих адаптивную сегментацию на основе декомпозиции сигнала за счет использования новых подходов к локализации сегментов.
Повышение эффективности схем сжатия, включающих процедуру квантования спектральных коэффициентов за счет адаптивного выбора шага квантования для каждой спектральной позиции.
Программная реализация алгоритмов сжатия на основе предложенных подходов.
Методы исследования. Диссертационное исследование включает в себя теоретические и экспериментальные методы. К теоретическим методам
относятся методы теории информации, теории вероятностей. В рамках методов теории информации отдельно выделяется RD-теория и анализ методов сжатия данных на ее основе. Экспериментальное исследование включает программную реализацию ряда схем сжатия с последующим сравнением результатов работы реализованных алгоритмов с существующими схемами сжатия.
Программная реализация алгоритмов осуществляется в среде Microsoft Visual Studio 2005 (C++) и в среде MatLab.
Научная новизна работы:
Предложен метод иерархической декомпозиции изображения, позволяющий создавать улучшенные модификации уже существующих схем, использующих адаптивную сегментацию изображений, а также синтезировать новые.
Усовершенствована схема сжатия, базирующаяся на иерархической декомпозиции изображения и геометрической аппроксимации сигнала билинейными поверхностями.
Разработана схема сжатия на основе рекурсивного разбиения изображения с использованием kd-дерева для представления структуры сегментации.
Разработан метод адаптивной генерации матриц квантования спектральных коэффициентов с использованием весового критерия, основанный на адаптивном выборе шага квантования.
Разработан метод адаптивного квантования спектральных коэффициентов на основе весового критерия, пригодный для схем сжатия с адаптивной сегментацией на области с неодинаковыми линейными размерами.
Практическая ценность результатов работы заключается в следующем: 1. Применение метода иерархической декомпозиции изображения позволяет улучшить результаты сжатия на основе адаптивной векторной сегментации. Так, для схемы, основанной на геометрической
аппроксимации сигнала билинейными поверхностями, коэффициент сжатия увеличивается, в среднем, на 3-6 %.
Использование компрессора на основе последовательного рекурсивного разбиения изображения с применением kd-дерева позволяет достичь более высокой степени сжатия, чем при использовании аналогичных схем без адаптивной сегментации. Коэффициент сжатия при использовании схемы с дискретным косинусным преобразованием, в среднем, выше на 10 %, чем при использовании схемы JPEG.
Метод адаптивной генерации матриц квантования на основе весового критерия позволяет модифицировать компрессоры ряда схем сжатия без необходимости вносить изменения в декомпрессор. Например, изменение схемы JPEG по указанному методу приводит к увеличению коэффициента сжатия до 30 %.
Внедрение результатов работы. Основные результаты работы внедрены в учебном процессе СПбГУ ИТМО, а также в Ленинградском отраслевом научно-исследовательском институте связи (ФГУП ЛОНИИС).
Апробация результатов работы. Результаты выполненных исследований были представлены на IV-й межвузовской конференции молодых ученых, XXXVII-й научной и учебно-методической конференции СПбГУ ИТМО, V-й всероссийской межвузовской конференции молодых ученых, XXXVIII-й научной и учебно-методической конференции СПбГУ ИТМО, всероссийской научно-технической конференции «Прогрессивные технологии в машино- и приборостроении - 2008», VI-й всероссийской межвузовской конференции молодых ученых.
Публикации. Основные результаты диссертационного исследования опубликованы в девяти статьях [8-12,14,20,21] и тезисах [13] общим объемом 40 страниц.
Структура диссертационной работы выглядит следующим образом. Работа состоит из введения основной части и заключения. Основная часть включает в себя 4 раздела.
В разделе 1 анализируются общие вопросы сжатия изображений с потерями. Дается введение в теорию сжатия изображений, обозначаются основные задачи сжатия и характеризуются главные этапы процесса компрессии. Приводится классификация искажений, появляющихся в результате необратимого сжатия. Приводится классификация метрик искажения, используемых для оценки привнесенной сжатием ошибки. Затрагивается вопрос оптимизации схем сжатия на основе RD-теории, приводятся теоретические сведения, необходимые для построения RD-оптимальных схем сжатия.
