Помощь студентам в учебе
Математические методы и алгоритмы цифровой компрессии изображений с использованием ортогональных преобразований
|
Общая характеристика работы
Содержание работы
Основные выводы и заключение
Список основных работ по теме диссертации
Содержание работы
Основные выводы и заключение
Список основных работ по теме диссертации
Актуальность темы. Хранение и передача изображений при непосредственном цифровом представлении в виде матрицы пикселей (точек изображения) вызывает необходимость обработки колоссальных объемов данных. Однако непосредственное представление изображения является неэффективным: вследствие значительной коррелированности элементов матрицы независимое кодирование пикселей порождает избыточные коды. Поэтому особую актуальность среди прочих задач цифровой обработки изображений приобретает задача сжатия изображений, которая заключается в поиске путей реализации эффективного кодирования визуальных данных.
Цель работы. Сложность алгоритмов, используемых для компрессии изображений, неуклонно растет - сказанное касается не только объема вычислений, но и идейных основ построения алгоритмов, большинство которых основано на использовании дискретных ортогональных преобразований для предварительной обработки данных. Вместе с тем, задача сжатия изображений ставится практикой, что требует при ее решении постоянного внимания к возможностям реальной аппаратуры. Целью работы являлись исследование теоретических вопросов эффективного кодирования изображений с использованием ортогональных преобразований, а также разработка соответствующих алгоритмов сжатия, пригодных для практического применения на базе универсальных вычислительных средств общего назначения.
Направление исследований. Проведенные в диссертационной работе исследования включали в себя рассмотрение следующих вопросов:
1. Исследование и разработка методов теоретического анализа и синтеза дискретных преобразований для схем компрессии коррелированных данных;
2. Разработка новых быстрых алгоритмов вычисления дискретного преобразования Крестенсона-Леви (ДПКЛ) и алгоритма сжатия полутоновых изображений, основанного на статистическом кодировании спектров ДПКЛ;
3. Исследование специфики и формализация общей схемы компрессии, использующей поблочную обработку фрагментов изображения при помощи ортогонального преобразования с последующим квантованием и статистическим кодированием коэффициентов-трансформант;
4. Разработка алгоритмов вейвлет-компрессии изображений и изучение возможностей фрактального кодирования в области вейвлет-спектра;
5. Разработка алгоритма сжатия видеопоследовательностей (динамических изображений), пригодного для использования в виде программной реализации на базе универсальных вычислительных средств общего назначения (мультимедийных персональных компьютеров).
Методы исследования. В качестве основного теоретического инструмента исследований использовались методы математического и функционального анализа, линейной алгебры, теории вероятностей и математической статистики, теории информации. Значительную часть исследований представляли собой также компьютерные эксперименты по обработке реальных неподвижных и динамических изображений, направленные на получение необходимых статистических данных и определение характеристик итоговых алгоритмов сжатия. Проведенные эксперименты подтвердили верность теоретических решений и эффективность предложенных алгоритмов компрессии.
Научная новизна. В результате выполнения диссертационной работы получены новые методы анализа эффективности ортогональных преобразований, предназначенных для сжатия коррелированных данных; специально для сжатия данных введено в рассмотрение (впервые построено) дискретное псевдокосинусное преобразование (ДПКП). Разработаны новые быстрые алгоритмы вычисления ДПКЛ, на базе которого впервые получена схема компрессии статических изображений, имеющая аналогичные методу JPEG характеристики. Для обработки неподвижных и динамических изображений предложены как новые алгоритмы, так и общие теоретические подходы, формализующие процедуры анализа и синтеза схем компрессии цифровых изображений на основе дискретных ортогональных преобразований.
На защиту диссертации выносятся следующие основные результаты:
• Метод оценки декоррелирующей эффективности ортогональных преобразований и основанные на нем алгоритмы кластеризации коррелированных данных;
• ДПКП и быстрый алгоритм его вычисления;
• Новый быстрый алгоритм ДПКЛ и его модификация - алгоритм с неполным вычислением; алгоритм совмещенных вычислений ДПКЛ для обработки вещественных массивов в базисе (1,ехр(-2тп/3));
• Метод компрессии изображений, основанный на специальном способе арифметического кодирования спектров ДПКЛ блоков изображения;
• Детерминированные и вероятностные оценки коэффициентов дискретного косинусного преобразования (ДКП);
• Алгоритм контекстного кодирования спектров ДКП изображений;
• Общая схема компрессии изображений на основе адаптивного векторного квантования в области ортогональных преобразований;
• Алгоритмы вейвлет-компрессии статических изображений;
• Алгоритм поиска перемещенных блоков изображения;
• Экспериментальная методика построения разбиения спектров на области независимого кодирования;
• Алгоритм видеокомпрессии.
Практическая ценность. В целом содержание работы носит прикладную направленность, поэтому полученные теоретические результаты также служат достижению целей, связанных с разработкой конкретных алгоритмов и схем компрессии цифровых изображений. Применение полученных алгоритмов сжатия изображений возможно для широкого класса систем хранения и передачи визуальной информации, прежде всего, в мультимедийных и сетевых компьютерных приложениях. Разработанные алгоритмы, как подтверждают эксперименты, обладают высокими характеристиками по скорости, качеству обработки и сжатию данных, которые соответствуют современному мировому уровню.
Реализация результатов работы. Теоретические результаты работы и алгоритмы сжатия видеоизображений внедрены в ГУ НПК «Технологический Центр» МИЭТ (http://www.tcen.ru) и использованы в научно-производственной деятельности НПП «Технология» (Москва) [29,30].
Апробация работы. Основные результаты работы докладывались и обсуждались на следующих научных конференциях и совещаниях:
1. VII саратовская зимняя школа по теории функций и приближений (СГУ, январь 1994 г.) [1].
2. Междунар. конференция по теории функций и приближений, посвященная 90-летию акад. С.М.Никольского (Москва, МИ РАН, май 1995 г.) [2].
3. Всероссийские научно-технические конференции “Электроника и информатика” (Москва, МИЭТ, 1995-2000 г.) [3,6,22].
4. Междунар. конференция по теории приближения функций, посвященная памяти проф. П.П.Коровкина (Калуга, КГПУ, 26-29 июня 1996 г.) [4].
5. Международные конференции «Методы оптимизации вычислений» (Киев, 1997, 2001 г.) [7,26].
6. Международная конференция «Проблемы математического образования», поев. 75-летию чл.-корр. РАН проф. Л.Д.Кудрявцева (1998 г.) [9].
7. Международная конференция «Теория приближений и гармонический анализ» (Тула, 26-29 мая 1998 г.) [10].
8. Международная конференция «Информационные технологии в инновационных проектах» (Ижевск, 20-22 апреля 1999 г.) [13].
9. VII Международная конференция «Математика. Экономика. Экология. Образование» - Международный симпозиум «Рады Фурье и их приложения» (Новороссийск, 1999 г.) [13,14].
10. VII Международная конференция «Математика. Компьютер. Образование» (Дубна, ОИЯИ, 24-29 янв. 2000 г.) [17].
11. Международная конференция, посвященная 80-летию со дня рождения С.Б.Стечкина (Екатеринбург, 28 февраля - 3 марта 2000 г.) [18].
В целом содержание работы обсуждалось на научном семинаре лаборатории информационных технологий в Объединенном институте ядерных ис-следований (г .Дубна, декабрь 2001 года).
Публикации. Основное содержание диссертации отражено в 30 работах.
Структура и объем диссертации. Диссертационная работа содержит 382 страницы (из которых 26 страниц - приложения) и состоит из введения, шести глав, заключения и 6 приложений. Библиографический список включает в себя 178 наименований. В приложениях приведены численные результаты ряда экспериментов по обработке изображений, а также справочная информация и копии документов об использовании результатов диссертационной работы.
Цель работы. Сложность алгоритмов, используемых для компрессии изображений, неуклонно растет - сказанное касается не только объема вычислений, но и идейных основ построения алгоритмов, большинство которых основано на использовании дискретных ортогональных преобразований для предварительной обработки данных. Вместе с тем, задача сжатия изображений ставится практикой, что требует при ее решении постоянного внимания к возможностям реальной аппаратуры. Целью работы являлись исследование теоретических вопросов эффективного кодирования изображений с использованием ортогональных преобразований, а также разработка соответствующих алгоритмов сжатия, пригодных для практического применения на базе универсальных вычислительных средств общего назначения.
Направление исследований. Проведенные в диссертационной работе исследования включали в себя рассмотрение следующих вопросов:
1. Исследование и разработка методов теоретического анализа и синтеза дискретных преобразований для схем компрессии коррелированных данных;
2. Разработка новых быстрых алгоритмов вычисления дискретного преобразования Крестенсона-Леви (ДПКЛ) и алгоритма сжатия полутоновых изображений, основанного на статистическом кодировании спектров ДПКЛ;
3. Исследование специфики и формализация общей схемы компрессии, использующей поблочную обработку фрагментов изображения при помощи ортогонального преобразования с последующим квантованием и статистическим кодированием коэффициентов-трансформант;
4. Разработка алгоритмов вейвлет-компрессии изображений и изучение возможностей фрактального кодирования в области вейвлет-спектра;
5. Разработка алгоритма сжатия видеопоследовательностей (динамических изображений), пригодного для использования в виде программной реализации на базе универсальных вычислительных средств общего назначения (мультимедийных персональных компьютеров).
Методы исследования. В качестве основного теоретического инструмента исследований использовались методы математического и функционального анализа, линейной алгебры, теории вероятностей и математической статистики, теории информации. Значительную часть исследований представляли собой также компьютерные эксперименты по обработке реальных неподвижных и динамических изображений, направленные на получение необходимых статистических данных и определение характеристик итоговых алгоритмов сжатия. Проведенные эксперименты подтвердили верность теоретических решений и эффективность предложенных алгоритмов компрессии.
Научная новизна. В результате выполнения диссертационной работы получены новые методы анализа эффективности ортогональных преобразований, предназначенных для сжатия коррелированных данных; специально для сжатия данных введено в рассмотрение (впервые построено) дискретное псевдокосинусное преобразование (ДПКП). Разработаны новые быстрые алгоритмы вычисления ДПКЛ, на базе которого впервые получена схема компрессии статических изображений, имеющая аналогичные методу JPEG характеристики. Для обработки неподвижных и динамических изображений предложены как новые алгоритмы, так и общие теоретические подходы, формализующие процедуры анализа и синтеза схем компрессии цифровых изображений на основе дискретных ортогональных преобразований.
На защиту диссертации выносятся следующие основные результаты:
• Метод оценки декоррелирующей эффективности ортогональных преобразований и основанные на нем алгоритмы кластеризации коррелированных данных;
• ДПКП и быстрый алгоритм его вычисления;
• Новый быстрый алгоритм ДПКЛ и его модификация - алгоритм с неполным вычислением; алгоритм совмещенных вычислений ДПКЛ для обработки вещественных массивов в базисе (1,ехр(-2тп/3));
• Метод компрессии изображений, основанный на специальном способе арифметического кодирования спектров ДПКЛ блоков изображения;
• Детерминированные и вероятностные оценки коэффициентов дискретного косинусного преобразования (ДКП);
• Алгоритм контекстного кодирования спектров ДКП изображений;
• Общая схема компрессии изображений на основе адаптивного векторного квантования в области ортогональных преобразований;
• Алгоритмы вейвлет-компрессии статических изображений;
• Алгоритм поиска перемещенных блоков изображения;
• Экспериментальная методика построения разбиения спектров на области независимого кодирования;
• Алгоритм видеокомпрессии.
Практическая ценность. В целом содержание работы носит прикладную направленность, поэтому полученные теоретические результаты также служат достижению целей, связанных с разработкой конкретных алгоритмов и схем компрессии цифровых изображений. Применение полученных алгоритмов сжатия изображений возможно для широкого класса систем хранения и передачи визуальной информации, прежде всего, в мультимедийных и сетевых компьютерных приложениях. Разработанные алгоритмы, как подтверждают эксперименты, обладают высокими характеристиками по скорости, качеству обработки и сжатию данных, которые соответствуют современному мировому уровню.
Реализация результатов работы. Теоретические результаты работы и алгоритмы сжатия видеоизображений внедрены в ГУ НПК «Технологический Центр» МИЭТ (http://www.tcen.ru) и использованы в научно-производственной деятельности НПП «Технология» (Москва) [29,30].
Апробация работы. Основные результаты работы докладывались и обсуждались на следующих научных конференциях и совещаниях:
1. VII саратовская зимняя школа по теории функций и приближений (СГУ, январь 1994 г.) [1].
2. Междунар. конференция по теории функций и приближений, посвященная 90-летию акад. С.М.Никольского (Москва, МИ РАН, май 1995 г.) [2].
3. Всероссийские научно-технические конференции “Электроника и информатика” (Москва, МИЭТ, 1995-2000 г.) [3,6,22].
4. Междунар. конференция по теории приближения функций, посвященная памяти проф. П.П.Коровкина (Калуга, КГПУ, 26-29 июня 1996 г.) [4].
5. Международные конференции «Методы оптимизации вычислений» (Киев, 1997, 2001 г.) [7,26].
6. Международная конференция «Проблемы математического образования», поев. 75-летию чл.-корр. РАН проф. Л.Д.Кудрявцева (1998 г.) [9].
7. Международная конференция «Теория приближений и гармонический анализ» (Тула, 26-29 мая 1998 г.) [10].
8. Международная конференция «Информационные технологии в инновационных проектах» (Ижевск, 20-22 апреля 1999 г.) [13].
9. VII Международная конференция «Математика. Экономика. Экология. Образование» - Международный симпозиум «Рады Фурье и их приложения» (Новороссийск, 1999 г.) [13,14].
10. VII Международная конференция «Математика. Компьютер. Образование» (Дубна, ОИЯИ, 24-29 янв. 2000 г.) [17].
11. Международная конференция, посвященная 80-летию со дня рождения С.Б.Стечкина (Екатеринбург, 28 февраля - 3 марта 2000 г.) [18].
В целом содержание работы обсуждалось на научном семинаре лаборатории информационных технологий в Объединенном институте ядерных ис-следований (г .Дубна, декабрь 2001 года).
Публикации. Основное содержание диссертации отражено в 30 работах.
Структура и объем диссертации. Диссертационная работа содержит 382 страницы (из которых 26 страниц - приложения) и состоит из введения, шести глав, заключения и 6 приложений. Библиографический список включает в себя 178 наименований. В приложениях приведены численные результаты ряда экспериментов по обработке изображений, а также справочная информация и копии документов об использовании результатов диссертационной работы.
В представленной диссертационной работе исследованы различные аспекты применения дискретных ортогональных преобразований для цифровой компрессии изображений, как со стороны сугубо формального теоретического анализа, так и со стороны тех требований и ограничений, которые практика налагает на конкретные вычислительные схемы и алгоритмы. В целом содержание работы носит прикладную направленность, поэтому большинство теоретических результатов подкреплено вычислительными экспериментами, результаты которых, в свою очередь, не только служили иллюстрацией или проверкой теории, но часто давали толчок и представляли собой исходный материал для дальнейших изысканий. По результатам проведенных в диссертационной работе исследований можно сделать следующие выводы.
1. Ортогональные преобразования являются основным инструментом, используемым для декорреляции данных при компрессии изображений. В случае, когда математическая модель дискретного сигнала задается ковариационной матрицей, для анализа эффективности декоррелирующей обработки целесообразно применение предложенного в работе критерия средней избыточной энтропии.
2. Специально для сжатия коррелированных данных получено и впервые введено в рассмотрение дискретное псевдокосинусное преобразование (ДПКП). В схеме компрессии, предполагающей наличие этапа скалярного квантования коэффициентов преобразование, среди рассмотренных быстрых преобразований, реализация которых сводится только к операциям сложения-вычитания (Уолша, Хаара, псевдокосинусное), ДПКП дает наилучшие результаты декорреляции для дискретного сигнала, описываемого марковской моделью.
3. С использованием полученных быстрых алгоритмов ДПКЛ, учитывающих специфику обработки вещественных массивов, предложенная схема компрессии изображений на основе арифметического кодирования коэффици-ентов ДПКЛ достигает характеристик, которые по качеству обработки и вычислительной сложности близки к варианту JPEG на основе ДКП.
4. При использовании статистического кодирования коэффициентов ДКП по методу JPEG наличие «скачков» дискретного сигнала наименее желательно в центральной области фрагментов обработки.
5. Высокую эффективность применения в различных схемах и алгоритмах сжатия данных имеет метод многомодельного (многопотокового) арифметического кодирования, а одним из ключевых моментов в разработке схем компрессии является определение правил для выбора текущей модели кодирования по контексту уже обработанных данных. Так, применение в схеме JPEG предложенного в главе 4 алгоритма многомодельного контекстного арифметического кодирования коэффициентов ДКП повышает эффективность сжатия данных на 10%.
6. При сжатии изображений с использованием многомодельного кодирования древовидных структур вейвлет-спектров правило выбора моделей следует строить по комбинированному контексту, который учитывает как окружение самого вейвлет-коэффициента в саббэнде, так н окружение коэффициента-«родителя». Полученный на этой основе новый эффективный алгоритм компрессии цифровых изображений с потерями, который разработан по результатам изучения статистических свойств спектров дискретных вейвлет-преобразований, показывает высокие характеристики сжатия при сложности реализации, приемлемой для широкого круга приложений.
7. Для устранения межкадровой (временной) избыточности видеоданных наиболее предпочтительным для практического применения среди исследованных алгоритмов блочной компенсации перемещений следует признать предложенный гибридный алгоритм направленного поиска, при котором малые перемещения ищутся точно и тщательно, а значительные перемещения - более грубо.
8. При использовании предложенного алгоритма видеокомпрессии, который был разработан на основе ЯО-оптимизационного подхода с учетом требований и специфики программной реализации, достигается сжатие и восстановление видео в реальном масштабе времени на базе современных персональных компьютеров, при высоком качестве обработки.
В целом, в диссертационной работе получены новые научные результаты, теоретические положения которых позволили в значительной степени раз-вить и формализовать процедуры анализа и синтеза схем компрессии цифровых изображений, основанных на использовании дискретных ортогональных преобразований. Выработанные подходы и рекомендации привели к построению конкретных схем и алгоритмов компрессии, многие из которых были реализованы программно и экспериментально подтвердили эффективность своего применения.
1. Ортогональные преобразования являются основным инструментом, используемым для декорреляции данных при компрессии изображений. В случае, когда математическая модель дискретного сигнала задается ковариационной матрицей, для анализа эффективности декоррелирующей обработки целесообразно применение предложенного в работе критерия средней избыточной энтропии.
2. Специально для сжатия коррелированных данных получено и впервые введено в рассмотрение дискретное псевдокосинусное преобразование (ДПКП). В схеме компрессии, предполагающей наличие этапа скалярного квантования коэффициентов преобразование, среди рассмотренных быстрых преобразований, реализация которых сводится только к операциям сложения-вычитания (Уолша, Хаара, псевдокосинусное), ДПКП дает наилучшие результаты декорреляции для дискретного сигнала, описываемого марковской моделью.
3. С использованием полученных быстрых алгоритмов ДПКЛ, учитывающих специфику обработки вещественных массивов, предложенная схема компрессии изображений на основе арифметического кодирования коэффици-ентов ДПКЛ достигает характеристик, которые по качеству обработки и вычислительной сложности близки к варианту JPEG на основе ДКП.
4. При использовании статистического кодирования коэффициентов ДКП по методу JPEG наличие «скачков» дискретного сигнала наименее желательно в центральной области фрагментов обработки.
5. Высокую эффективность применения в различных схемах и алгоритмах сжатия данных имеет метод многомодельного (многопотокового) арифметического кодирования, а одним из ключевых моментов в разработке схем компрессии является определение правил для выбора текущей модели кодирования по контексту уже обработанных данных. Так, применение в схеме JPEG предложенного в главе 4 алгоритма многомодельного контекстного арифметического кодирования коэффициентов ДКП повышает эффективность сжатия данных на 10%.
6. При сжатии изображений с использованием многомодельного кодирования древовидных структур вейвлет-спектров правило выбора моделей следует строить по комбинированному контексту, который учитывает как окружение самого вейвлет-коэффициента в саббэнде, так н окружение коэффициента-«родителя». Полученный на этой основе новый эффективный алгоритм компрессии цифровых изображений с потерями, который разработан по результатам изучения статистических свойств спектров дискретных вейвлет-преобразований, показывает высокие характеристики сжатия при сложности реализации, приемлемой для широкого круга приложений.
7. Для устранения межкадровой (временной) избыточности видеоданных наиболее предпочтительным для практического применения среди исследованных алгоритмов блочной компенсации перемещений следует признать предложенный гибридный алгоритм направленного поиска, при котором малые перемещения ищутся точно и тщательно, а значительные перемещения - более грубо.
8. При использовании предложенного алгоритма видеокомпрессии, который был разработан на основе ЯО-оптимизационного подхода с учетом требований и специфики программной реализации, достигается сжатие и восстановление видео в реальном масштабе времени на базе современных персональных компьютеров, при высоком качестве обработки.
В целом, в диссертационной работе получены новые научные результаты, теоретические положения которых позволили в значительной степени раз-вить и формализовать процедуры анализа и синтеза схем компрессии цифровых изображений, основанных на использовании дискретных ортогональных преобразований. Выработанные подходы и рекомендации привели к построению конкретных схем и алгоритмов компрессии, многие из которых были реализованы программно и экспериментально подтвердили эффективность своего применения.