Метод сжатия цифровых изображений на основе блочных клеточных автоматов

• Автор: Евсютин, Олег Олегович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Томск
• Количество страниц: 174 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ МЕТОДОВ СЖАТИЯ ЦИФРОВЫХ ИЗОБРАЖЕНИЙ

1.1 Особенности цифровых изображений как типа данных

1.2 Математическая модель сжатия цифровых изображений.

1.3 Существующие методы сжатия цифровых изображений.

1.3.1 Простейшие методы.

1.3.2 Метод сжатия на основе дискретного косинусного преобразования

1.3.3 Метод сжатия на основе дискретного вейвлетного преобразования .

1.4 Сравнительная оценка методов сжатия цифровых изображений

1.5 Сжатие цифровых изображений с помощью математического аппарата теории клеточных автоматов
1.5.1 Математическая модель клеточного автомата.
1.5.2 Подходы к использованию клеточных автоматов для решения задачи сжатия цифровых изображений.
1.6 Выводы
ГЛАВА 2. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ СЖАТИЯ ЦИФРОВЫХ ИЗОБРАЖЕНИЙ НА ОСНОВЕ КЛЕТОЧНЫХ АВТОМАТОВ.
2.1 Декоррелирующие клеточные преобразования
2.2 Модель сжатия цифровых изображений на основе декоррелирующего клеточного преобразования.
2.3 Алгоритмы построения и выбора базисов декоррелирующих клеточных преобразований
2.3.1 Блочные клеточные автоматы
2.3.2 Выбор множества коэффициентов, определяющих базис декоррелирующего преобразования.
2.3.3 Алгоритмы построения базисов декоррслирующих клеточных преобразований с использованием блочных клеточных автоматов.
2.3.3.1 Простейший алгоритм построения базиса декоррелирующего преобразования из истории развития клеточного автомата с заданным начальным состоянием.
2.3.3.2 Улучшенный алгоритм построения базиса декоррелирующего преобразования из истории развития клеточного автомата с заданным начальным состоянием.
2.3.4 Алгоритмы выбора базисов декоррелирующих клеточных преобразований.
2.3.4.1 Алгоритм выбора базисов по количеству низкочастотных составляющих.
2.3.4.2 Алгоритм выбора базисов по расположению частотных составляющих.
2.3.4.3 Алгоритм выбора базисов по разбросу значений частотных составляющих.
2.3.4.4 Объединенный алгоритм выбора базисов
2.4. Выводы
ГЛАВА 3. ПРОГРАММНЫЙ КОМПЛЕКС ДЛЯ ПОСТРОЕНИЯ И ИССЛЕДОВАНИЯ БАЗИСОВ ДЕКОРРЕЛИРУЮЩИХ КЛЕТОЧНЫХ ПРЕОБРАЗОВАНИЙ И СЖАТИЯ ЦИФРОВЫХ ИЗОБРАЖЕНИЙ НА ИХ ОСНОВЕ.
3.1 Состав и структура программного комплекса САТСотргеББЮп
3.2 Программное средство САТВаБевСгеаПг, предназначенное для построения и выбора ортогональных базисов декоррелирующих клеточных преобразований.
3.2.1 Алгоритм работы программного средства
3.2.2 Формат файлов для хранения базисов декоррелирующих клеточных преобразований
3.3 Программное средство САТВазезКеБеагсЬ, предназначенное для исследования базисов декоррелирующих клеточных преобразований
3.3.1 Преобразование простых функций, моделирующих последовательности пикселей цифровых изображений
3.3.2 Преобразование цифровых изображений.
3.3.3 Схемы квантования преобразованных элементов данных
3.3.4 Посгроение ортогональных базисов с помощью кронексровского произведения
3.3.5 Изменение частотного спектра декоррелирующего клеточного преобразования
3.3.6 Методика выбора базисов декоррелирующих клеточных преобразований по искажениям, проявляющимся в восстанавливаемых после преобразования данных.
3.4 Выводы.
ГЛАВА 4. РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДА СЖАТИЯ ЦИФРОВЫХ ИЗОБРАЖЕНИЙ НА ОСНОВЕ БЛОЧНЫХ КЛЕТОЧНЫХ АВТОМАТОВ
4.1 Построение семейств базисов декоррелирующих клеточных преобразований.
4.1.1 Построение базисов декоррелирующих клеточных преобразований с помощью динамики блочных клеточных автоматов.
4.1.2 Построение базисов декоррелирующих клеточных преобразований с помощью кронекеровского произведения.
4.2 Исследование искажений, возникающих в результате квантования, для построенных семейств базисов с помощью тестового набора простых изображений
4.3 Метод сжатия цифровых изображений на основе декоррелирующих клеточных преобразований.
4.3.1 Предварительная обработка изображения
4.3.2 Квантование преобразованных элементов данных.
4.3.3 Энтропийное кодирование квантованных элементов данных
4.4 Программное средство САТСобес
4.4.1 Основные функциональные возможности.
4.4.2 Формат представления сжатых данных
4.5 Сравнительная оценка эффективности разработанного метода сжатия цифровых изображений на основе клеточных автоматов.
4.6 Выводы.
ЗАКЛЮЧЕНИЕ.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
Приложение 1.
Приложение 2.
Приложение 3.
Приложение 4.
ВВЕДЕНИЕ
Актуальность


Результаты диссертационной работы используются в учебном процессе Томского государственного университета систем управления и радиоэлектроники при изучении дисциплин Теоретические основы компьютерной безопасности и Специальные главы математики. Апробация результатов. Новосибирск, научнотехническом семинаре Интеллектуальные системы моделирования, проектирования и управления Томск, . Основные защищаемые положения. Математическая модель сжатия цифровых изображений на основе клеточных автоматов более, чем первого порядка, расширяющая класс получаемых декоррелирующих преобразований. Метод поиска субоптимальных базисов декоррелирующих клеточных преобразований, использующий для порождения базисных векторов динамику блочных клеточных автоматов. Подсемейства ортогональных базисов для блочных клеточных автоматов 2го и 3го порядков, определяющих дскоррслирующие преобразования с равным количеством низко и высокочастотных составляющих. Метод сжатия полутоновых цифровых изображений, основанный на аппроксимациях дискретного вейвлетного преобразования, полученных с помощью динамики блочных клеточных автоматов. Публикации. По результатам выполненных исследований опубликовано работ, в том числе 5 в журналах, рекомендованных ВАК. Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 7 наименований и четырех приложений. Основная часть работы содержит 3 страницы, в том числе рисунков и таблиц. ГЛАВА 1. Цифровое изображение представляет собой прямоугольную матрицу, элементы которой, называемые пикселями, принимают значения из некоторого отрезка ряда целых чисел. Указанный отрезок начинается с нуля, поскольку в общем случае значение пикселя определяет его яркость, и отрицательные значения яркости не рассматриваются. Мощность множества возможных значений пикселя Ь, то есть количество различных уровней яркости, для удобства аппаратной и программной реализации всегда принимается равной некоторой степени двойки, чтобы каждый пиксель мог быть представлен целым числом битов. Также изображение можно описать как дискретную функцию двух переменных х,у с областью определения Е О,. О 0,1. Ь , ,, . В зависимости от величины наличия цвета у пикселей, а также особенностей содержимого, различают несколько основных типов цифровых изображений. Простейшими являются монохромные бинарные цифровые изображения. Каждый пиксель таких изображений кодируется одним битом, что дает только два цвета черный и белый . Двуцветные изображения в настоящее время распространены не очень широко и используются, например, в факсимильной связи, а также в некоторых специальных приложениях . Чаще всего пиксели таких изображений кодируются одним байтом, тогда говорят о 8битовых изображениях с 6 радациями серого цвета. Также для представления пикселей используют 4 или битов, что соответствует или 6 уровням яркости. Пиксели изображений указанных типов не обладают цветом как таковым, а только яркостью, поэтому далее в рассматриваемой классификации стоят цветные цифровые изображения, которые представляются с иомощыо определенной цветовой модели. Наиболее известной является модель, когда цвет каждого пикселя определяется тремя независимыми компонентами красного , зеленого и синего цветов. Также существуют и другие модели, такие как , I, и т. Обычно каждая цветовая компонента кодируется одним байтом, тогда говорят о разрядных цветных изображениях, естественно, для них задача сжатия является наиболее актуальной. Дальнейшая классификация относится уже к цветным изображениям, которые делятся на непрерывнотоновые и дискретнотоновые. Главной особенностью непрерывнотоновых изображений являются плавные цветовые переходы и отсутствие резких границ, наличие которых, в свою очередь, является особенностью дискретнотоновых изображений. И если к первым относятся, прежде всего, оцифрованные изображения окружающей действительности, то ко вторым компьютерная графика. В отдельную категорию выделяются изображения, характерные для мультипликации. Их особенностями является наличие резких границ между объектами и однотонное заполнение внутри границ. Однако их можно считать разновидностью дискретнотоновых изображений.