Сжатие цифровых изображений (500,00 руб.)

Стр.2

Стр.122

Стр.123

Стр.124

УДК 004.932:004.032.26:519.713 ББК 32.811 С33 Р е ц е н з е н т : доктор физ.-мат. наук, профессор Ав т о р ы: О. О. Евсютин, А. А. Шелупанов, С. К. Росошек, Р. В. Мещеряков С33 Сжатие цифровых изображений. – М.: Горячая линия – Телеком, 2013. – 124 с.: ил. ISBN 978-5-9912-0357-9. На основе математического аппарата теории клеточных автоматов для решения задач сжатия цифровых изображений изложен подход, основанный на использовании динамики клеточного автомата для построения ортогональных базисов декоррелирующих преобразований, устраняющих пространственную избыточность из элементов данных. Представлены математическая модель сжатия цифровых изображений на основе клеточных автоматов более чем первого порядка и эффективные алгоритмы построения и выбора базисов декоррелирующих клеточных преобразований. Изложен эффективный метод сжатия цифровых изображений и проведено сравнение с методами JPEG и JPEG 2000. Применение полученных авторами результатов открывает перспективы создания алгоритмов обработки цифровых изображений, столь же эффективных, что и построенные на основе дискретного вейвлетного преобразования, и в то же время столь же быстродействующих, что и основанные на дискретном преобразовании Фурье, за счет замены вещественных операций целочисленными. Для инженеров и научных работников, аспирантов и студентов вузов интересующихся проблемами сжатия цифровых изображений. ББК 32.811 Адрес издательства в Интернет WWW.TECHBOOK.RU Научное издание Евсютин Олег Олегович Шелупанов Александр Александрович Росошек Семен Константинович Мещеряков Роман Валерьевич СЖАТИЕ ЦИФРОВЫХ ИЗОБРАЖЕНИЙ Редактор Ю. Н. Чернышов Компьютерная верстка Ю. Н. Чернышова Обложка художника О. В. Карповой Подписано в печать 01.09.2013. Формат 60×88/16. Уч. изд. л. 7,75. Тираж 500 экз. ООО «Научно-техническое издательство «Горячая линия – Телеком» ISBN 978-5-9912-0357-9 © Коллектив авторов, 2013 © Издательство «Горячая линия – Телеком», 2013 С. С. Б о нд а рчук М о но гр а ф ия

Стр.2

Оглавление Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Глава 1. Анализ методов сжатия цифровых изображений. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 6 1.1. Особенности цифровых изображений как типа данных 6 1.2. Математическая модель сжатия цифровых изображений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3. Существующие методы сжатия цифровых изображений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.1. Простейшие методы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.2. Метод сжатия JPEG на основе дискретного косинусного преобразования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3.3. Метод сжатия JPEG 2000 на основе дискретного вейвлетного преобразования. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.4. Сравнительная оценка методов сжатия цифровых изображений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.5. Сжатие цифровых изображений с помощью математического аппарата теории клеточных автоматов . . . . . . . 23 1.5.1. Математическая модель клеточного автомата . . . . . 24 1.5.2. Подходы к использованию клеточных автоматов для решения задачи сжатия цифровых изображений. . . . . . . . . . 25 1.6. Выводы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Глава 2. Математическая модель сжатия цифровых изображений на основе клеточных автоматов . . . . 29 2.1. Декоррелирующие клеточные преобразования . . . . . . . 29 2.2. Модель сжатия цифровых изображений на основе декоррелирующего клеточного преобразования . . . . . . . . . 30 2.3. Алгоритмы построения и выбора базисов декоррелирующих клеточных преобразований . . . . . . . . . . . . . . . . . . . . . 31 2.3.1. Блочные клеточные автоматы. . . . . . . . . . . . . . . . . . . . . . 31 2.3.2. Выбор множества коэффициентов, определяющих базис декоррелирующего преобразования . . . . . . . . . . . . . . . . 33 2.3.3. Алгоритмы построения базисов декоррелирующих клеточных преобразований с использованием блочных клеточных автоматов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 9

Стр.122

Оглавление 123 2.3.3.1. Простейший алгоритм построения базиса декоррелирующего преобразования из истории развития клеточного автомата с заданным начальным состоянием . 35 2.3.3.2. Улучшенный алгоритм построения базиса декоррелирующего преобразования из истории развития клеточного автомата с заданным начальным состоянием 37 2.3.4. Алгоритмы выбора базисов декоррелирующих клеточных преобразований . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.3.4.1. Алгоритм выбора базисов по количеству низкочастотных составляющих . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.3.4.2. Алгоритм выбора базисов по расположению частотных составляющих . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.3.4.3. Алгоритм выбора базисов по разбросу значений частотных составляющих . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.3.4.4. Объединенный алгоритм выбора базисов . . . . . . 45 2.4. Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 Глава 3. Программный комплекс для построения и исследования базисов декоррелирующих клеточных преобразований и сжатия цифровых изображений на их основе . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.1. Состав и структура программного комплекса CATCompression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2. Программное средство CATBasesCreating, предназначенное для построения и выбора ортогональных базисов декоррелирующих клеточных преобразований . . . 49 3.2.1. Алгоритм работы программного средства . . . . . . . . . . 49 3.2.2. Формат файлов для хранения базисов декоррелирующих клеточных преобразований. . . . . . . . . . . . . . . . . . . . . . . . . 53 3.3. Программное средство CATBasesResearch, предназначенное для исследования базисов декоррелирующих клеточных преобразований. . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.3.1. Преобразование простых функций, моделирующих последовательности пикселей цифровых изображений . . . . 55 3.3.2. Преобразование цифровых изображений . . . . . . . . . . . 58 3.3.3. Схемы квантования преобразованных элементов данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.3.4. Построение ортогональных базисов с помощью кронекеровского произведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.3.5. Изменение частотного спектра декоррелирующего клеточного преобразования. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.3.6. Методика выбора базисов декоррелирующих клеточных преобразований по искажениям, проявляющимся в восстанавливаемых после преобразования данных . . . . . . 68 3.4. Выводы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

Стр.123

124 Оглавление Глава 4. Разработка и исследование метода сжатия цифровых изображений на основе блочных клеточных автоматов. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.1. Построение семейств базисов декоррелирующих клеточных преобразований . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.1.1. Построение базисов декоррелирующих клеточных преобразований с помощью динамики блочных клеточных автоматов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.1.2. Построение базисов декоррелирующих клеточных преобразований с помощью кронекеровского произведения 78 4.2. Исследование искажений, возникающих в результате квантования, для построенных семейств базисов с помощью тестового набора простых изображений . . . . . . . 80 4.3. Метод сжатия цифровых изображений на основе декоррелирующих клеточных преобразований . . . . . . . . . . 85 4.3.1. Предварительная обработка изображения . . . . . . . . . . 85 4.3.2. Квантование преобразованных элементов данных . . 85 4.3.3. Энтропийное кодирование квантованных элементов данных. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.4. Программное средство CATCodec . . . . . . . . . . . . . . . . . . . . . 89 4.4.1. Основные функциональные возможности . . . . . . . . . . 89 4.4.2. Формат представления сжатых данных. . . . . . . . . . . . . 90 4.5. Сравнительная оценка эффективности разработанного метода сжатия цифровых изображений на основе клеточных автоматов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 4.6. Выводы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 Литература. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Приложение 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Приложение 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Приложение 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

Стр.124