автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Метод сжатия цифровых изображений на основе блочных клеточных автоматов

На правах рукописи

Евсютин Олег Олегович

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

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 3 ДЕК 2012

Томск - 2012

005056945

Работа выполнена на кафедре комплексной информационной

безопасности электронно-вычислительных систем Томского государственного университета систем управления и радиоэлектроники (ТУСУР)

Научный руководитель: доктор технических наук, профессор

Шелупанов Александр Александрович (Томский государственный университет систем управления и радиоэлектроники)

Официальные оппоненты: доктор технических наук, профессор

Матросова Анжела Юрьевна (Национальный исследовательский Томский государственный университет)

доктор технических наук, профессор Марков Николай Григорьевич (Национальный исследовательский Томский политехнический университет)

Ведущая организация: Алтайский государственный университет

Защита состоится 27 декабря 2012 г. в 12:00 на заседании диссертационного совета Д 212.267.08 при Национальном исследовательском Томском государственном университете по адресу: 634050, г. Томск, пр. Ленина, 36, корп. 2, ауд. 102.

Отзывы на автореферат, заверенные гербовой печатью организации, просим направлять по адресу: 634050, г. Томск, пр. Ленина, 36, ученому секретарю ТГУ Буровой Н. Ю.

С диссертацией можно ознакомиться в Научной библиотеке Национального исследовательского Томского государственного университета по адресу: 634050, г. Томск, пр. Ленина, 34а.

Автореферат разослан 26 ноября 2012 г

Ученый секретарь

диссертационного совета Д 212.267.08 доктор технических наук, профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы.

Сжатие данных является одной из актуальных проблем в области современных информационных технологий. Производительность вычислительной техники постоянно растет, и несмотря на повышение емкости и доступности носителей информации, а также пропускной способности телекоммуникационных линий, их возможности не успевают за ростом потоков данных, требующих обработки. При этом особую значимость приобретает проблема сжатия цифровых изображений, представляющих собой один из наиболее распространенных в настоящее время типов данных.

Сжатие цифровых изображений основывается на устранении присущей им пространственной избыточности, проявляющейся в виде близости друг другу значений соседних пикселей на локальных участках изображения.

Существуют различные подходы к декорреляции элементов цифрового изображения, обладающие своими достоинствами и недостатками. Так, например, декорреляция с предсказанием значений пикселей широко используется в методах сжатия без потерь информации, применение которых актуально для отдельных специализированных приложений, но в общем случае малоэффективно. В свою очередь, фрактальное сжатие изображений, основанное на поиске самоподобных участков, позволяет достичь самых высоких степеней сжатия, но требует чрезмерных вычислительных затрат.

В основе наиболее распространенных современных методов сжатия цифровых изображений с потерями лежат ортогональные декорре-лирующие преобразования, осуществляющие разделение элементов данных на составляющие, содержащие основную информацию об изображении, и определяющие малозначимые детали. Сжатие происходит за счет удаления составляющих второго типа из преобразованных элементов данных с последующим энтропийным кодированием оставшихся элементов.

К самым известным ортогональным преобразованиям, которые используются в методах сжатия цифровых изображений, относятся преобразование Карунена—Лоэва, преобразование Уолша—Адамара, дискретное косинусное преобразование, являющееся частным случаем дискретного преобразования Фурье, семейство дискретных вейвлетных преобразований. На основе отдельных представителей данного класса преобразований построены такие известные методы сжатия, как JPEG, JPEG 2000, SPIHT, QTCQ, EZW, ICER, JPEG XR, WebP.

Фундаментальные основы обработки и сжатия цифровых изображений были заложены в работах N. Ahmed, K.R. Rao, I. Daubechies, R.C. Gonzalez, M.W. Marcellin. В России наибольший вклад в данную область внесли Д.С. Ватолин, И.И. Исмагилов, H.H. Пономаренко, C.B. Умняшкин.

Основная проблема, связанная со сжатием цифровых изображений с потерями, заключается в появлении на восстанавливаемых после сжатия изображениях разного рода искажений — так называемых артефактов сжатия. При этом каждому из известных методов сжатия присущи свои собственные артефакты, характер которых зависит от используемого математического аппарата.

Поэтому актуальными являются исследования, направленные как на улучшение существующих методов сжатия цифровых изображений, так и на разработку новых с привлечением не использовавшегося ранее в данной области математического аппарата.

В настоящее время известны работы, в которых для решения задачи сжатия цифровых изображений был задействован математический аппарат нейронных сетей, модифицированное дискретное косинусное преобразование, иерархическая сеточная интерполяция.

Большой интерес в этом отношении представляет математический аппарат теории клеточных автоматов.

Создателями данной теории были J. von Neumann и К. Zuse. На ее дальнейшее развитие значительное влияние оказали работы E.F. Codd,

A. Ilachinski, T. Toffoli, J.L. Schiff, S. Wolfram, a также В.З. Аладьева,

B.Б. Кудрявцева, A.C. Подколзина. В частности, N. Margolus ввел такое расширение классической модели клеточных автоматов как блочные клеточные автоматы (клеточные автоматы на разбиении).

Математический аппарат теории клеточных автоматов ранее уже использовался для сжатия цифровых изображений, однако его использование ограничивалось решением некоторых частных задач в рамках существующих методов. С. Shaw, S. Das и B.K. Sikdar предложили основанный на клеточных автоматах способ энтропийного кодирования элементов цифрового изображения после дискретного вейвлетного преобразования. О. Lafe был разработан метод сжатия, построенный на основе декоррелирующего преобразования, использующего в качестве базисных векторов состояния развития классического клеточного автомата первого порядка с окрестностью Мура-фон Неймана. Здесь под порядком клеточного автомата подразумевается значение f"log2|A|"j , где А — это алфавит внутренних состояний, определяющий множество возможных значений каждой из клеток решетки автомата. Недостатком клеточных автоматов первого порядка в контексте решаемой задачи яв-

ляется получение малого количества декоррелирующих преобразований, которые не отличаются разнообразием свойств и, кроме того, являясь частным случаем преобразования Уолша-Адамара, не обладают какими-либо дополнительными свойствами, отсутствующими у известных преобразований.

В настоящей работе предлагается расширить класс декоррелирующих преобразований, получаемых с помощью динамики клеточного автомата, за счет использования клеточных автоматов более, чем первого порядка, что открывает перспективы построения аппроксимаций более сложных преобразований.

Цель работы.

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

Задачи исследования.

Для достижения поставленной цели были решены следующие задачи:

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

2. Построение математической модели сжатия цифровых изображений на основе клеточных автоматов более, чем первого порядка.

3. Разработка метода поиска субоптимальных базисов декоррелирующих преобразований, использующего для порождения базисных векторов динамику блочных клеточных автоматов.

4. Получение подсемейств ортогональных базисов для блочных клеточных автоматов 2-го и 3-го порядков, определяющих декоррели-рующие преобразования с равным количеством низко- и высокочастотных составляющих, аппроксимирующие дискретное вейвлетное преобразование.

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

6. Разработка программного обеспечения для построения и исследования базисов ортогональных декоррелирующих клеточных преобразований, а также экспериментальное исследование разработанного метода сжатия и его сравнение с имеющимися аналогами.

Объект и предмет исследования.

Объектом исследования являются полутоновые цифровые изображения. Предметом исследования является метод сжатия цифровых изображений указанного типа на основе блочных клеточных автоматов.

Методы исследования.

В диссертационной работе использовались методы теории клеточных автоматов, теории информации, линейной алгебры и вычисли-

тельного эксперимента. При разработке программного комплекса использовались методы объектно-ориентированного программирования.

Достоверность результатов.

Достоверность полученных результатов подтверждается строгостью использованных математических методов, согласованностью с полученными ранее результатами других авторов и серией практических экспериментов по сжатию выборки стандартных тестовых изображений.

Научная новизна.

1. Впервые построена математическая модель сжатия цифровых изображений на основе клеточных автоматов более, чем первого порядка, что позволяет расширить класс получаемых декоррелирующих преобразований, дополнив его аппроксимациями дискретного вейвлетного преобразования.

2. На основе построенной математической модели разработан метод поиска субоптимальных базисов декоррелирующих клеточных преобразований, использующий для порождения базисных векторов блочные клеточные автоматы, свойства которых позволяют избежать проблем неконструируемых состояний и циклических историй развития неопределенной длины, и позволяющий находить базисы, декоррелирую-щие преобразования на основе которых обеспечивают наименьшую ошибку восстановления для заданных тестовых наборов дискретных функций.

3. Впервые с помощью блочных клеточных автоматов 2-го и 3-го порядков получены подсемейства ортогональных базисов, определяющих декоррелирующие преобразования с равным количеством низко- и высокочастотных составляющих, что позволяет строить более эффективные алгоритмы сжатия за счет замены вещественных операций целочисленными.

4. На основе разработанной математической модели и найденных субоптимальных базисов создан новый метод сжатия полутоновых цифровых изображений, использующий для декорреляции элементов данных впервые полученные аппроксимации дискретного вейвлетного преобразования, что позволяет создавать более быстродействующие алгоритмы сжатия цифровых изображений по сравнению с вейвлетными преобразованиями.

Теоретическая значимость

1. Полученные результаты имеют более широкое применение, нежели для сжатия изображений, и могут быть использованы для аппроксимации произвольных преобразований дискретных функций.

2. Применение полученных результатов открывает перспективы создания алгоритмов обработки цифровых изображений, столь же эффективных, что и построенные на основе дискретного вейвлетного пре-

образования, и в то же время столь же быстродействующих, что и основанные на дискретном преобразовании Фурье, за счет замены вещественных операций целочисленными.

Практическая ценность.

1. Разработанный метод сжатия цифровых изображений, основанный на использовании целочисленных операций над элементами данных вместо вещественных, позволяет при сравнимом качестве обеспечить большую на 15—25 % скорость преобразований в случае программной реализации и многократно большую скорость в случае аппаратной реализации по сравнению с методами, построенными на основе вейв-летных преобразований.

2. Созданный в работе программный комплекс может использоваться для построения и исследования базисов произвольных ортогональных клеточных преобразований, в том числе декоррелирующих.

Внедрение результатов.

Разработанный метод сжатия цифровых изображений на основе клеточных автоматов использован в НПФ «Информационные системы безопасности» при разработке перспективных технологий сжатия и обработки изображений. Созданный на основе разработанного метода сжатия программный модуль для сжатия фотоизображений внедрен в деятельность организации НПФ «Аист».

Результаты диссертационной работы использовались при выполнении проекта «Фундаментальные основы клеточных автоматов для решения задач кодирования информации» (грант РФФИ № 12-01-31378 мол_а).

Результаты диссертационной работы использовались при выполнении проекта «Разработка Web-ориентированных геоинформационных технологий формирования и мониторинга электронного генерального плана инженерной инфраструктуры», реализуемого в рамках мероприятия 2.4 федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 годы» (государственный контракт № 07.524.11.4013 от 03 ноября 2011 г.).

Результаты диссертационной работы использовались при выполнении проекта № 7.701.2011 (проект 1/12) «Разработка и исследование методов и технологий информационной безопасности в технических и высокопроизводительных вычислительных системах».

Результаты диссертационной работы используются в учебном процессе Томского государственного университета систем управления и радиоэлектроники при изучении дисциплин «Теоретические основы компьютерной безопасности» и «Специальные главы математики».

Апробация результатов.

Материалы работы докладывались и обсуждались на следующих конференциях и семинарах: Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых «Научная сессия ТУ-СУР» (Томск, 2010-2012); 54-ой научной конференции МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе» (Москва, 2011); VII Международной научно-практической конференции «Электронные средства и системы управления» (Томск, 2011); IX Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования» (Томск, 2012); XIII Всероссийской научно-практической конференции «Проблемы информационной безопасности государства, общества и личности» (Новосибирск, 2012); научно-техническом семинаре «Интеллектуальные системы моделирования, проектирования и управления» (Томск, 2009-2012).

Основные защищаемые положения.

1. Математическая модель сжатия цифровых изображений на основе клеточных автоматов более, чем первого порядка, расширяющая класс получаемых декоррелирующих преобразований.

2. Метод поиска субоптимальных базисов декоррелирующих клеточных преобразований, использующий для порождения базисных векторов динамику блочных клеточных автоматов.

3. Подсемейства ортогональных базисов для блочных клеточных автоматов 2-го и 3-го порядков, определяющих декоррелирующие преобразования с равным количеством низко- и высокочастотных составляющих.

4. Метод сжатия полутоновых цифровых изображений, основанный на аппроксимациях дискретного вейвлетного преобразования, полученных с помощью динамики блочных клеточных автоматов.

Публикации.

По результатам выполненных исследований опубликовано 12 работ, в том числе 5 в журналах, рекомендованных ВАК.

Структура и объем работы.

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 107 наименований и четырех приложений. Основная часть работы содержит 143 страницы, в том числе 29 рисунков и 12 таблиц.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертационной работы, определены цель и задачи исследования, показаны научная новизна и практическая ценность работы, изложены научные положения, выносимые на защиту.

В первой главе произведен обзор проблемы исследования.

Цифровое изображение представляет собой матрицу элементы которой, называемые пикселями, принимают значения из некоторого отрезка ряда целых чисел и при этом, в случае наиболее распространенных полутоновых и непрерывно-тоновых цифровых изображений, обладают пространственной избыточностью, проявляющейся в виде близости этих значений друг другу на локальных участках.

На рис. 1 представлена обобщенная модель сжатия цифровых изображений с потерями, построенная в результате проведенного анализа литературных источников.

Базис

Параметры квантования

О

декоррелирующего преобразования С

F' G G'

Рис. 1. Обобщенная модель сжатия цифровых изображений Потери информации приводят к восстановлению изображений после сжатия с некоторой ошибкой. Для измерения расхождения между исходным и восстановленным после сжатия изображениями используется пиковое отношение сигнал/шум, обозначаемое PSNR (peak signal to noise ratio) и вычисляемое по формуле

max (/(*,;;))_

PSNR = 20 log,,

I—

I тп х=оу=о

Восстановленное изображение тем ближе к исходному, чем больше значение PSNR.

В диссертационной работе предлагается использовать математический аппарат теории клеточных автоматов для построения базисов декоррелирующих преобразований, служащих для устранения пространственной избыточности из элементов цифровых изображений.

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

Декоррелирующим клеточным преобразованием (ДКлП) назовем построенное с использованием динамики клеточного автомата к -го порядка преобразование элементов цифрового изображения к виду, когда между ними отсутствует пространственная избыточность. Основу такого преобразования составляет ортогональный базис С = (с^)^',^,.

На рис. 2 представлена построенная в работе модель сжатия цифровых изображений на основе клеточных автоматов, являющаяся расширением обобщенной модели сжатия цифровых изображений.

Параметры алгоритмов построения и выбора

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

Для построения отдельно взятого ортогонального базиса выбирается клеточный автомат с алфавитом внутренних состояний А, задается множество базисных коэффициентов В, такое, что |А| = |в|, и вводится отображение к: А —» В. Затем задается начальное состояние решетки клеточного автомата и рассматривается соответствующая история развития. N состояний данной истории развития, выбираемых таким образом, чтобы выполнялось требование попарной взаимной ортогональности после применения введенного отображения, составят базис ДКлП.

Ниже приведено краткое описание соответствующего алгоритма.

1. Задаются значения параметров обратимого блочного клеточного автомата С А И, А, т, 8,4*), множество базисных коэффициентов В, начальное состояние решетки клеточного автомата С0, значения параметров глубины поиска в истории развития (Л^, (п).

2. Заданное начальное состояние решетки принимается в качестве первого базисного вектора, и запускается процесс развития блочного клеточного автомата.

3. Если достигнута заданная глубина поиска, алгоритм заканчивается неудачей. В противном случае вычисляется очередное состояние развития клеточного автомата и сравнивается с начальным. Совпадение означает, что циклическая история развития клеточного автомата завершилась возвратом к начальному состоянию. В этом случае алгоритм заканчивается неудачей. Если же заданная глубина поиска не достигнута, и цикл не завершен, полученное состояние развития клеточного автомата рассматривается к качестве предполагаемого базисного вектора.

4. Поочередно вычисляется скалярное произведение построенного вектора с каждым из найденных ранее векторов и осуществляется переход к шагу 3 при появлении первого ненулевого значения. В случае отсутствия таких значений рассматриваемый вектор добавляется к уже найденным. Как только их количество станет равным N, алгоритм завершается возвратом ортогонального базиса.

Представленный алгоритм позволяет получать семейства, состоящие из сотен тысяч базисов ДКлП, для различных блочных клеточных автоматов и множеств базисных коэффициентов. С целью выделения базисов, обладающих одинаковыми в контексте задачи сжатия цифровых изображений свойствами, был предложен следующий алгоритм.

1. Выбирается ортогональный базис С; вектор значений, обладающих пространственной избыточностью, Г; коэффициент X, определяющий минимальное отношение значения преобразованного элемента данных к среднему значению элементов вектора Р, при котором указанный элемент считается низкочастотной составляющей; количество низкочастотных составляющих среди преобразованных элементов данных г; двоичная маска, определяющая расположение частотных составляющих, Н; параметр разброса значений низкочастотных составляющих V.

2. Вычисляется среднее значение М элементов вектора Г.

3. К значениям вектора К применяется ДКлП посредством матричного умножения в = РС.

--Я

4. Для каждого значения g¡, /= 1, N , вычисляется лс, = —. Если

М

|дг,|> Я, то g¡ является низкочастотной составляющей.

5. Если количество низкочастотных составляющих равно нулю, то М делится пополам, и осуществляется переход к шагу 4.

6. Количество, расположение и разброс значений выявленных низкочастотных составляющих сравниваются с заданными значениями входных параметров. Если несовпадений не обнаружено, то алгоритм заканчивается возвратом положительного ответа, в противном случае — отрицательного.

В третьей главе представлен программный комплекс, являющийся научно-исследовательским инструментом, предназначенным для автоматизации процессов построения и исследования ортогональных базисов ДКлП, и реализующий сжатие цифровых изображений на их основе.

В состав программного комплекса «САТСотргеББЮп» входит три самостоятельных программных средства, обеспечивающих решение отдельных задач, возникающих при решении общей задачи сжатия цифровых изображений на основе клеточных автоматов.

Программное средство «САТВазеэСгеайгщ» осуществляет построение семейств ортогональных базисов ДКлП и проводит первичный отбор, выделяя подсемейства базисов, обладающих схожими свойствами. Исследование сформированных подсемейств, направленное на выявление отдельных базисов, декоррелирующие преобразования на основе которых обладают наилучшими характеристиками сжатия, осуществляется с помощью программного средства «САТВазезЯезеагсЬ». Программное средство «САТСос1ес» реализует метод сжатия цифровых изображений на основе клеточных автоматов, представленный в четвертой главе диссертации.

Одна из основных возможностей программного средства «САТВавезКеБеагсИ» позволяет выбирать субоптимальные относительно некоторого тестового набора дискретных функций базисы ДКлП по критерию наименьшей ошибки восстановления при равном уровне потерь информации.

Исходя из анализа литературных источников, а также стандартных корпусов тестовых изображений, используемых для исследования методов обработки цифровых изображений и охватывающих изображения всех основных типов в рамках существующих классификаций, в работе сформирован набор из 33 простых двумерных функций, моделирующих отдельные блоки цифровых изображений для исследования артефактов квантования. Примеры изображений из данного набора представлены на рис. 3.

#

а) б) в) г)

Рис. 3. Примеры простых тестовых изображений: а) — плавный цветовой переход; б) — две области с плавным цветовым переходом; в) — объект на фоне плавного цветового перехода; г) — линии на фоне плавного

цветового перехода

1

Методика выбора базисов ДКлП по искажениям, проявляющимся в восстанавливаемых после преобразования данных, определяется следующей последовательностью действий.

1. Построение семейства базисов ДКлП и выбор подсемейства базисов с заданными характеристиками.

2. Выбор тестового набора двумерных функций (простых изображений), моделирующих блоки полутонового изображения.

3. Выбор схемы и степени квантования преобразованных элементов данных.

4. Осуществление декоррелирующих преобразований простых изображений из заданного тестового набора с последующим квантованием преобразованных элементов данных согласно выбранной схеме.

5. Осуществление обратного преобразования и вычисление значения ошибки для каждого ДКлП по каждому простому изображению. Выбор базиса (базисов) с лучшими характеристиками.

В четвертой главе описаны вопросы разработки метода сжатия цифровых изображений на основе клеточных автоматов, основным из которых является получение субоптимальных базисов ДКлП с помощью представленных алгоритмов и методики.

Множество базисов ДКлП, полученных из состояний развития некоторого блочного клеточного автомата для всех возможных начальных состояний решетки с использованием фиксированного множества базисных коэффициентов, назовем семейством базисов ДКлП. Каждое семейство может быть разбито на подсемейства, объединяющее базисы, частотный спектр которых содержит г низкочастотных составляющих, удовлетворяющих заданным значениям определяющего коэффициента X и параметра разброса v.

В результате проведенных экспериментов получены подсемейства базисов ДКлП, аппроксимирующие дискретные вейвлетные преобразования = у ПРИ N = 0 (mod 2)).

Установлено, что для получения ДКлП с малым разбросом значений высокочастотных составляющих коэффициент X должен находиться в интервале [0,15; 0,25].

На основе построенной модели и выбранных субоптимальных базисов был создан метод сжатия цифровых изображений, описываемый следующей последовательностью этапов.

Этап 1. Предварительная обработка изображения.

Этап 2. t -уровневое ДКлП.

Этап 3. Скалярное квантование.

Этап 4. Формирование серий.

Этап 5. Энтропийное кодирование.

Результаты сравнения разработанного метода сжатия цифровых изображений на основе клеточных автоматов (СТС) с методами сжатия цифровых изображения JPEG и JPEG 2000, принятыми в качестве эталонных, проведенного на стандартном тестовом корпусе полутоновых и непрерывно-тоновых цифровых изображений, включающем в себя такие изображения, как «Baboon», «Barbara», «Boats», «Goldhill», «Lenna», «Peppers» и т.д., показали, что метод СТС обеспечивает повышение качества изображений по сравнению с методом JPEG, и приближается к методу JPEG 2000, обеспечивая большую скорость преобразований за счет использования малых целочисленных величин в качестве базисных коэффициентов.

В заключении сформулированы основные научные и практические результаты:

1. Построена математическая модель сжатия цифровых изображений на основе клеточных автоматов более, чем первого порядка, как расширение обобщенной модели сжатия цифровых изображений с потерями.

2. Предложен алгоритм построения базисов ДКлП, отличительными особенностями которого является использование динамики блочных клеточных автоматов.

3. Предложен алгоритм выбора базисов ДКлП, отличительными особенностями которого является ввод таких классификационных признаков при выборе базисов как количество, расположение и разброс значений низкочастотных составляющих среди преобразованных элементов данных.

4. Разработана методика выбора базисов ДКлП по искажениям, проявляющимся в восстанавливаемых после преобразования данных, учитывающая уровень потерь информации, произведенных на этапе квантования.

5. Создан программный комплекс «CATCompression», включающий в себя три самостоятельных программных средства, обеспечивающих решение основных задач, возникающих при разработке метода сжатия цифровых изображений на основе клеточных автоматов: получение ортогональных базисов с заданными свойствами, исследование их характеристик сжатия, непосредственное сжатие цифровых изображений.

6. Впервые с помощью математического аппарата теории клеточных автоматов построены семейства ортогональных базисов для множеств базисных коэффициентов малой мощности, соответствующих алфавитам внутренних состояний блочных клеточных автоматов 2-го и 3-го порядков, и сформированы подсемейства базисов, декоррелирующие

преобразования на основе которых обладают частотным спектром с равным числом низко- и высокочастотных составляющих.

7. Разработан новый метод сжатия цифровых изображений на основе многоуровневого ДКлП и произведено его сравнение с методами JPEG и JPEG 2000, принятыми в качестве эталонных, показавшее, что разработанный метод обеспечивает повышение качества изображения по сравнению с методом JPEG, и приближается к методу JPEG 2000, обеспечивая большую на 15-25 % скорость преобразований за счет использования целочисленных операций над элементами данных вместо вещественных.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ РАБОТЫ

В журналах, рекомендованных ВАК:

1. Евсютин О.О. Использование клеточных автоматов для решения задач преобразования информации / О.О. Евсютин, С.К. Росошек // Доклады ТУ СУ Ра.— 2010. — № 1 (21).— Ч. 1, —С. 173-174.

2. Евсютин О. О. Модели сжатия данных // Промышленные АСУ и контроллеры. — 2012. — №5. — С. 61-65.

3. Евсютин О.О. Приложения клеточных автоматов в области информационной безопасности и обработки данных / О.О. Евсютин, A.A. Шелупанов // Доклады ТУСУРа. — 2012. — № 1 (25). — Ч. 2. — С. 119125.

4. Евсютин О.О. Программный комплекс для построения и исследования декоррелирующих клеточных преобразований и сжатия цифровых изображений на их основе // Доклады ТУСУРа. — 2012. — № 1 (25). — Ч. 2. — С. 220-224.

5. Евсютин О.О. Моделирование в информационной безопасности и обработке данных с использованием математического аппарата дискретных динамических систем / О.О. Евсютин, В.Г. Миронова // Ползу-новский вестник. — 2012. — № 3/2. — С. 222-226.

Другие публикации:

6. Евсютин О.О. Клеточные автоматы в задачах преобразования информации / О.О. Евсютин, С.К. Росошек // Научная сессия ТУСУР-2010: Материалы докладов Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых, Томск, 4-7 мая 2010 г. — Томск: В-Спектр, 2010. — Ч. 3. — С. 114-116.

7. Евсютин О.О. Существующие подходы к сжатию данных различного типа // Научная сессия ТУСУР-2011: Материалы Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых, Томск, 4-6 мая 2011 г. — Томск: В-Спектр, 2011. — Ч. 3. — С. 26-29.

8. Евсютин О.О. Декоррелирующие клеточные преобразования // Труды 54-й научной конференции МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе». Управление и прикладная математика. Том 2. — М: МФТИ, 2011. — С. 69-70.

9. Евсютин О.О. Модели сжатия данных // Электронные средства и системы управления: Материалы докладов Международной научно-практической конференции (10-11 ноября 2011 г.). — Томск: В-Спектр, 2011, —С. 125-132.

10. Евсютин О.О. Приложения теории клеточных автоматов в обработке цифровых изображений // Научная сессия ТУСУР-2012: Материалы Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых, Томск, 16-18 мая 2012 г. — Томск: В-Спектр, 2012. — Ч. 3. — С. 23-25.

11. Евсютин О.О. Критерий выбора базисов декоррелирующих преобразований, получаемых из состояний развития клеточного автомата // Научная сессия ТУСУР-2012: Материалы Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых, Томск, 16-18 мая 2012 г. — Томск: В-Спектр, 2012. — Ч. 3. — С. 67-69.

12. Евсютин О.О. Шифрование и сжатие данных с помощью клеточных автоматов // Технологии Microsoft в теории и практике программирования: сборник трудов IX Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых, г. Томск, 21-22 марта 2012 г. — Томск: изд-во Томского политехнического университета, 2012. — С. 275-277.

Тираж 100 экз. Заказ 1244. Томский государственный университет

систем управления и радиоэлектроники. 634050, г. Томск, пр. Ленина, 40. Тел. (3822) 533018.

ВВЕДЕНИЕ.

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

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

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

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

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

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

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

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 Программное средство «CATCodec».

4.4.1 Основные функциональные возможности.

4.4.2 Формат представления сжатых данных.

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

4.6 Выводы.

Актуальность работы.

Сжатие данных является одной из актуальных проблем в области современных информационных технологий. Производительность вычислительной техники постоянно растет, и несмотря на повышение емкости и доступности носителей информации, а также пропускной способности телекоммуникационных линий, их возможности не успевают за ростом потоков данных, требующих обработки. При этом особую значимость приобретает проблема сжатия цифровых изображений, представляющих собой один из наиболее распространенных в настоящее время типов данных.

Сжатие цифровых изображений основывается на устранении присущей им пространственной избыточности, проявляющейся в виде близости друг другу значений соседних пикселей на локальных участках изображения.

Существуют различные подходы к декорреляции элементов цифрового изображения, обладающие своими достоинствами и недостатками. Так, например, декорреляция с предсказанием значений пикселей широко используется в методах сжатия без потерь информации, применение которых актуально для отдельных специализированных приложений, но в общем случае малоэффективно [16, 65]. В свою очередь, фрактальное сжатие изображений, основанное на поиске самоподобных участков, позволяет достичь самых высоких степеней сжатия, но требует чрезмерных вычислительных затрат [12].

В основе наиболее распространенных современных методов сжатия цифровых изображений с потерями лежат ортогональные декоррелирующие преобразования, осуществляющие разделение элементов данных на составляющие, содержащие основную информацию об изображении, и определяющие малозначимые детали. Сжатие происходит за счет удаления составляющих второго типа из преобразованных элементов данных с последующим энтропийным кодированием оставшихся элементов [10, 65, 81, 84, 100].

К самым известным ортогональным преобразованиям, которые используются в методах сжатия цифровых изображений, относятся преобразование Карунена-Лоэва [82, 95], преобразование Уолша-Адамара [31, 69, 75, 77], дискретное косинусное преобразование [65, 84], являющееся частным случаем дискретного преобразования Фурье, семейство дискретных вейвлетных преобразований [13, 18, 32, 46]. На основе отдельных представителей данного класса преобразований построены такие известные методы сжатия, как JPEG, JPEG 2000, SPIHT, QTCQ, EZW, ICER, JPEGXR, WebP.

Фундаментальные основы обработки и сжатия цифровых изображений были заложены в работах N. Ahmed, K.R. Rao, I. Daubechies, R.C. Gonzalez, M.W. Marcellin. В России наибольший вклад в данную область внесли Д.С. Ватолин, И.И. Исмагилов, H.H. Пономаренко, C.B. Умняшкин [9, 12, 14, 16, 18, 33-35, 53, 54, 70-73, 99].

Основная проблема, связанная со сжатием цифровых изображений с потерями, заключается в появлении на восстанавливаемых после сжатия изображениях разного рода искажений — так называемых артефактов сжатия [67]. При этом каждому из известных методов сжатия присущи свои собственные артефакты, характер которых зависит от используемого математического аппарата.

Поэтому актуальными являются исследования, направленные как на улучшение существующих методов сжатия цифровых изображений, так и на разработку новых с привлечением не использовавшегося ранее в данной области математического аппарата.

В настоящее время известны работы, в которых для решения задачи сжатия цифровых изображений был задействован математический аппарат нейронных сетей [40, 66] модифицированное дискретное косинусное преобразование [53, 73], иерархическая сеточная интерполяция [14].

Большой интерес в этом отношении представляет математический аппарат теории клеточных автоматов.

Создателями данной теории были J. von Neumann и К. Zuse. На ее дальнейшее развитие значительное влияние оказали работы E.F. Codd, А. Ilachinski, Т. Toffoli, J.L. Schiff, S. Wolfram, а также В.З. Аладьева, В.Б. Кудрявцева, A.C. Подколзина [2, 38, 39, 68, 86, 88, 91, 105]. В частности, N. Margolus ввел такое расширение классической модели клеточных автоматов как блочные клеточные автоматы (клеточные автоматы на разбиении) [68].

Математический аппарат теории клеточных автоматов ранее уже использовался для сжатия цифровых изображений, однако его использование ограничивалось решением некоторых частных задач в рамках существующих методов. С. Shaw, S. Das и B.K. Sikdar предложили основанный на клеточных автоматах способ энтропийного кодирования элементов цифрового изображения после дискретного вейвлетного преобразования [102]. О. Lafe был разработан метод сжатия, построенный на основе декоррелирующего преобразования, использующего в качестве базисных векторов состояния развития классического клеточного автомата первого порядка с окрестностью Мура-фон Неймана [98]. Здесь под порядком клеточного автомата подразумевается значение ["log2|A|"| , где А — это алфавит внутренних состояний, определяющий множество возможных значений каждой из клеток решетки автомата. Недостатком клеточных автоматов первого порядка в контексте решаемой задачи является получение малого количества декоррелирующих преобразований, которые не отличаются разнообразием свойств и, кроме того, являясь частным случаем преобразования Уолша-Адамара, не обладают какими-либо дополнительными свойствами, отсутствующими у известных преобразований.

В настоящей работе предлагается расширить класс декоррелирующих преобразований, получаемых с помощью динамики клеточного автомата, за счет использования клеточных автоматов более, чем первого порядка, что открывает перспективы построения аппроксимаций более сложных преобразований.

Цель работы.

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

Задачи исследования.

Для достижения поставленной цели были решены следующие задачи:

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

2. Построение математической модели сжатия цифровых изображений на основе клеточных автоматов более, чем первого порядка.

3. Разработка метода поиска субоптимальных базисов декоррелирующих преобразований, использующего для порождения базисных векторов динамику блочных клеточных автоматов.

4. Получение подсемейств ортогональных базисов для блочных клеточных автоматов 2-го и 3-го порядков, определяющих декоррелирующие преобразования с равным количеством низко- и высокочастотных составляющих, аппроксимирующие дискретное вейвлетное преобразование.

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

6. Разработка программного обеспечения для построения и исследования базисов ортогональных декоррелирующих клеточных преобразований, а также экспериментальное исследование разработанного метода сжатия и его сравнение с имеющимися аналогами.

Объект и предмет исследования.

Объектом исследования являются полутоновые цифровые изображения. Предметом исследования является метод сжатия цифровых изображений указанного типа на основе блочных клеточных автоматов.

Методы исследования.

В диссертационной работе использовались методы теории клеточных автоматов, теории информации, линейной алгебры и вычислительного эксперимента. При разработке программного комплекса использовались методы объектно-ориентированного программирования.

Достоверность результатов.

Достоверность полученных результатов подтверждается строгостью использованных математических методов, согласованностью с полученными ранее результатами других авторов и серией практических экспериментов по сжатию выборки стандартных тестовых изображений.

Научная новизна.

1. Впервые построена математическая модель сжатия цифровых изображений на основе клеточных автоматов более, чем первого порядка, что позволяет расширить класс получаемых декоррелирующих преобразований, дополнив его аппроксимациями дискретного вейвлетного преобразования.

2. На основе построенной математической модели разработан метод поиска субоптимальных базисов декоррелирующих клеточных преобразований, использующий для порождения базисных векторов блочные клеточные автоматы, свойства которых позволяют избежать проблем неконструируемых состояний и циклических историй развития неопределенной длины, . и позволяющий находить базисы, декоррелирующие преобразования на основе которых обеспечивают наименьшую ошибку восстановления для заданных тестовых наборов дискретных функций.

3. Впервые с помощью блочных клеточных автоматов 2-го и 3-го порядков получены подсемейства ортогональных базисов, определяющих декоррелирующие преобразования с равным количеством низко- и высокочастотных составляющих, что позволяет строить более эффективные алгоритмы сжатия за счет замены вещественных операций целочисленными.

4. На основе разработанной математической модели и найденных субоптимальных базисов создан новый метод сжатия полутоновых цифровых изображений, использующий для декорреляции элементов данных впервые полученные аппроксимации дискретного вейвлетного преобразования, что позволяет создавать более быстродействующие алгоритмы сжатия цифровых изображений по сравнению с вейвлетными преобразованиями.

Теоретическая значимость

1. Полученные результаты имеют более широкое применение, нежели для сжатия изображений, и могут быть использованы для аппроксимации произвольных преобразований дискретных функций.

2. Применение полученных результатов открывает перспективы создания алгоритмов обработки цифровых изображений, столь же эффективных, что и построенные на основе дискретного вейвлетного преобразования, и в то же время столь же быстродействующих, что и основанные на дискретном преобразовании Фурье, за счет замены вещественных операций целочисленными.

Практическая ценность.

1. Разработанный метод сжатия цифровых изображений, основанный на использовании целочисленных операций над элементами данных вместо вещественных, позволяет при сравнимом качестве обеспечить большую на 1525 % скорость преобразований в случае программной реализации и многократно большую скорость в случае аппаратной реализации по сравнению с методами, построенными на основе вейвлетных преобразований.

2. Созданный в работе программный комплекс может использоваться для построения и исследования базисов произвольных ортогональных клеточных преобразований, в том числе декоррелирующих.

Внедрение результатов.

Разработанный метод сжатия цифровых изображений на основе клеточных автоматов использован в НПФ «Информационные системы безопасности» при разработке перспективных технологий сжатия и обработки изображений. Созданный на основе разработанного метода сжатия программный модуль для сжатия фотоизображений внедрен в деятельность организации НПФ «Аист».

Результаты диссертационной работы использовались при выполнении проекта «Фундаментальные основы клеточных автоматов для решения задач кодирования информации» (грант РФФИ № 12-01-31378 мола).

Результаты диссертационной работы использовались при выполнении проекта «Разработка Web-ориентированных геоинформационных технологий формирования и мониторинга электронного генерального плана инженерной инфраструктуры», реализуемого в рамках мероприятия 2.4 федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 20072013 годы» (государственный контракт № 07.524.11.4013 от 03 ноября 2011 г.).

Результаты диссертационной работы использовались при выполнении проекта № 7.701.2011 (проект 1/12) «Разработка и исследование методов и технологий информационной безопасности в технических и высокопроизводительных вычислительных системах».

Результаты диссертационной работы используются в учебном процессе Томского государственного университета систем управления и радиоэлектроники при изучении дисциплин «Теоретические основы компьютерной безопасности» и «Специальные главы математики».

Апробация результатов.

Материалы работы докладывались и обсуждались на следующих конференциях и семинарах: Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых «Научная сессия ТУСУР» (Томск, 2010-2012); 54-ой научной конференции МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе» (Москва, 2011); VII Международной научно-практической конференции «Электронные средства и системы управления» (Томск, 2011); IX Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования» (Томск, 2012); XIII Всероссийской научно-практической конференции «Проблемы информационной безопасности государства, общества и личности» (Новосибирск, 2012); научно-техническом семинаре «Интеллектуальные системы моделирования, проектирования и управления» (Томск, 2009-2012).

Основные защищаемые положения.

1. Математическая модель сжатия цифровых изображений на основе клеточных автоматов более, чем первого порядка, расширяющая класс получаемых декоррелирующих преобразований.

2. Метод поиска субоптимальных базисов декоррелирующих клеточных преобразований, использующий для порождения базисных векторов динамику блочных клеточных автоматов.

3. Подсемейства ортогональных базисов для блочных клеточных автоматов 2-го и 3-го порядков, определяющих декоррелирующие преобразования с равным количеством низко- и высокочастотных составляющих.

4. Метод сжатия полутоновых цифровых изображений, основанный на аппроксимациях дискретного вейвлетного преобразования, полученных с помощью динамики блочных клеточных автоматов.

Публикации.

По результатам выполненных исследований опубликовано 12 работ, в том числе 5 в журналах, рекомендованных ВАК.

Структура и объем работы.

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 107 наименований и четырех приложений. Основная часть работы содержит 143 страницы, в том числе 29 рисунков и 12 таблиц.

4.6 Выводы

1. В результате проведенного эксперимента установлено, что коэффициент X, определяющий минимальное отношение значения преобразованного элемента данных к среднему значению элементов исходной последовательности, при котором указанный элемент считается низкочастотной составляющей, должен принимать значение в интервале [0,15; 0,25] для построения базисов декоррелирующих клеточных преобразований с лучшими характеристиками.

2. Построены семейства базисов декоррелирующих клеточных преобразований и сформированы подсемейства базисов, соответствующих декоррелирующим преобразованиям с равным числом низко- и высокочастотных составляющих, аппроксимирующим дискретное вейвлетное преобразование. Установлено, что лучше всего для получения ортогональных базисов декоррелирующих клеточных преобразований подходят симметричные множества базисных коэффициентов.

3. Дополнена разработанная методика выбора базисов декоррелирующих клеточных преобразований по искажениям, проявляющимся в восстанавливаемых после преобразования данных и произведен выбор субоптимальных базисов в построенных семействах согласно данной методике.

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

ЗАКЛЮЧЕНИЕ

1. Проведен обзор литературных источников в области обработки и сжатия цифровых изображений, рассмотрены методы сжатия цифровых изображений с потерями, выявлены характерные особенности, которыми обладают цифровые изображения как тип данных, построена обобщенная модель сжатия цифровых изображений с потерями, рассмотрен математический аппарат, использующийся для сравнительной оценки методов сжатия цифровых изображений по качеству изображений, восстанавливаемых после сжатия.

2. Рассмотрены возможные подходы к использованию математического аппарата теории клеточных автоматов для решения задачи сжатия цифровых изображений и выбран подход, основанный на использовании динамики клеточного автомата для построения ортогональных базисов декоррелирующих преобразований, устраняющих пространственную избыточность из элементов данных.

3. Построена математическая модель сжатия цифровых изображений на основе клеточных автоматов более, чем первого порядка, как расширение обобщенной модели сжатия цифровых изображений с потерями.

4. Предложен алгоритм построения базисов декоррелирующих клеточных преобразований, отличительной особенностью которого является использование динамики блочных клеточных автоматов.

5. Предложен алгоритм выбора базисов декоррелирующих клеточных преобразований, отличительной особенностью которого является ввод таких классификационных признаков при выборе базисов как количество, расположение и разброс значений низкочастотных составляющих среди преобразованных элементов данных.

6. Разработана методика выбора субоптимальных базисов декоррелирующих клеточных преобразований по искажениям, проявляющимся в восстанавливаемых после преобразования данных, учитывающая уровень потерь информации, произведенных на этапе квантования.

7. Создан программный комплекс «CATCompression», включающий в себя три самостоятельных программных средства, обеспечивающих решение основных задач, возникающих при разработке метода сжатия цифровых изображений на основе клеточных автоматов: получение ортогональных базисов с заданными свойствами, исследование их характеристик сжатия, непосредственное сжатие цифровых изображений.

8. Впервые с помощью математического аппарата теории клеточных автоматов построены семейства ортогональных базисов для множеств базисных коэффициентов малой мощности, соответствующих алфавитам внутренних состояний блочных клеточных автоматов 2-го и 3-го порядков, и сформированы подсемейства базисов, декоррелирующие преобразования на основе которых обладают частотным спектром с равным числом низко- и высокочастотных составляющих.

9. Проведено исследование характеристик сжатия построенных ортогональных базисов и выбраны базисы с лучшими характеристиками, ключевыми из которых являются количество нулевых значений среди квантованных элементов данных и корень из среднеквадратической ошибки RMSE.

10. Исследована схема квантования преобразованных элементов данных по уровням декоррелирующего преобразования, схема квантования на основе нуль-дерева и пороговая схема квантования. Установлено, что схема квантования по уровням преобразования приводит к восстановлению цифровых изображений после декоррелирующего клеточного преобразования с наименьшими искажениями.

11. Разработан новый метод сжатия цифровых изображений на основе многоуровневого декоррелирующего клеточного преобразования и произведено его сравнение с методами JPEG и JPEG 2000, принятыми в качестве эталонных, показавшее, что разработанный метод обеспечивает повышения качества изображения по сравнению с методом JPEG, и приближается к методу JPEG 2000, обеспечивая большую на 15-25 % скорость преобразований за счет использования целочисленных операций над элементами данных вместо вещественных.

12. Разработанный метод сжатия цифровых изображений на основе клеточных автоматов использован в НПФ «Информационные системы безопасности» при разработке перспективных технологий сжатия и обработки изображений. Созданный на основе разработанного метода сжатия программный модуль для сжатия фотоизображений внедрен в деятельность организации НПФ «Аист».

1. Айфичер Э. Цифровая обработка сигналов: практический подход / Э. Айфичер, Б. Джервис. — 2-е издание. — М.: Издательский дом «Вильяме», 2004. —992 с.

2. Аладьев В.З. Классические однородные структуры: теория и приложения / В.З. Аладьев, В.К. Бойко, Е.А. Ровба. — Гродно: ГрГУ, 2008. — 486 с.

3. Анисимов Б.В. Распознавание и цифровая обработка изображений: учеб. пособие для студентов вузов / Б.В. Анисимов, В.Д. Курганов, В.К. Злобин. — М.: Высш. шк., 1983. — 295 с.

4. Артюшенко В.М. Цифровое сжатие видеоинформации и звука / В.М. Артюшенко, О.И. Шелухин, М.Ю. Афонин. — М.: Дашков и К°, 2004. — 425 с.

5. Архангельский А .Я. С++ Builder 6. Справочное пособие. Книга 1. Язык С++. — М.: Бином-Пресс, 2002. — 544 с.

6. Архангельский А.Я. С++ Builder 6. Справочное пособие. Книга 2. Классы и компоненты. — М.: Бином-Пресс, 2002. — 526 с.

7. Архангельский А.Я. Программирование в С++ Builder 6. — М.: Бином, 2003. — 1151 с.

8. Астафьев Г.Б. Клеточные автоматы: учебно-методическое пособие / Г.Б. Астафьев, A.A. Короновский, А.Е. Храмов. — Саратов: Изд-во ГосУНЦ «Колледж», 2003. — 24 с.

9. Ахмед Н. Ортогональные преобразования при обработке цифровых сигналов / Н. Ахмед, K.P. Pao. — М.: Связь, 1980. — 248 с.

10. Бутаков Е.А. Обработка изображений на ЭВМ / Е.А. Бутаков, В.И. Островский, И.Л. Фадеев. — М.: Радио и связь, 1987. — 240 с.

11. Быков P.E., Фрайер Р. Цифровое преобразование изображений / P.E. Быков, Р. Фрайер. — М.: Горячая линия-Телеком, 2003. — 228 с.

12. Ватолин Д. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео / Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. — М.: ДИАЛОГ-МИФИ, 2002. — 384 с.

13. Воробьев В.И. Теория и практика вейвлет-преобразования / В.И. Воробьев, В.Г. Трибунов. — СПб.: ВУС, 1999. — 204 с.

14. Гашников М.В. Методы компьютерной обработки изображений / М.В. Гашников, Н.И. Глумов, Н.Ю. Ильясова, В.В. Мясников и др. — М.: ФИЗМАТЛИТ, 2003. — 784 с.

15. Гольденберг Л.М. Цифровая обработка сигналов: справочник / Л.М. Гольденберг, Б.Д. Матюшкин, М.Н. Поляк. — М.: Радио и связь, 1985. — 312 с.

16. Гонсалес Р. Цифровая обработка изображений / Р. Гонсалес, Р. Вудс. — М.: Техносфера, 2005. — 1072 с.

17. Грузман И.С. Цифровая обработка изображений в информационных системах: учебное пособие / И.С. Грузман, B.C. Киричук, В.П. Косых, Г.И. Перетягин, А.А. Спектор. — Новосибирск: Изд-во НГТУ, 2000. — 168 с.

18. Добеши И. Десять лекций по вейвлетам. — Ижевск: НИЦ «Регулярная и хаотичная динамика», 2001. — 464 с.

19. Евсютин О.О. Использование клеточных автоматов для решения задач преобразования информации / О.О. Евсютин, С.К. Росошек // Доклады ТУСУРа. —2010. —№ 1 (21). —Ч. 1. —С. 173-174.

20. Евсютин О.О. Модели сжатия данных // Электронные средства и системы управления: Материалы докладов Международной научно-практической конференции (10-11 ноября 2011 г.). — Томск: В-Спектр, 2011. —С. 125-132.

21. Евсютин О. О. Модели сжатия данных // Промышленные АСУ и контроллеры. — 2012. — № 5. — С. 61-65.

22. Евсютин О.О. Приложения клеточных автоматов в области информационной безопасности и обработки данных / О.О. Евсютин, A.A. Шелупанов // Доклады ТУСУРа. — 2012. — № 1 (25). — Ч. 2. — С. 119-125.

23. Евсютин 0.0. Программный комплекс для построения и исследования декоррелирующих клеточных преобразований и сжатия цифровых изображений на их основе // Доклады ТУСУРа. — 2012. — № 1 (25).1. Ч.2. —С. 220-224.

24. Евсютин О.О. Моделирование в информационной безопасности и обработке данных с использованием математического аппарата дискретных динамических систем / О.О. Евсютин, В.Г. Миронова // Ползуновский вестник.2012. — № 3/2. — С. 222-226.

25. Залманзон JT.А. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. — М.: Наука, 1989. — 496 с.

26. Иванов М.А. Применение вейвлет-преобразований в кодировании изображений // Новые информационные технологии в науке и образовании. — Новосибирск: Ин-т систем информатики им. А.П. Ершова СОР АН, 2003. — С. 157-176.

27. Исмагилов И.И. Модифицированные преобразования Уолша в сжатии цифровых изображений // Исследования по информатике. — 2000. — № 2. —С. 85-90.

28. Исмагилов И.И. Оценка эффективности двухэтапных алгоритмов сжатия изображений на основе преобразований Уолша / И.И. Исмагилов, М.Ю. Васильева // Исследования по информатике. — 2007. — № 11. — С. 95-102.

29. Исмагилов И.И. Алгоритмы реализации дифференцирующе-сглаживающих нерекурсивных цифровых фильтров на основе преобразования Уолша-Адамара / И.И. Исмагилов, А.П. Ефремов // Исследования по информатике. — 2007. — № 12. — С. 104-108.

30. Козлов В.Н. Об одном подходе к сжатию информации при обработке и распознавании изображений // Журнал вычислительной математики и математической физики. — 2002. — Т. 42, № 2. — С. 256-268.

31. Кричевский P.E. Сжатие и поиск информации. — М.: Радио и связь, 1989.— 168 с.

32. Кудрявцев В.Б. Основы теории однородных структур / В.Б. Кудрявцев, A.C. Подколзин, A.A. Болотов. — М.: Наука, 1990. — 296 с.

33. Кудрявцев В.Б. Клеточные автоматы / В.Б. Кудрявцев, A.C. Подколзин // Интеллектуальные системы. — 2006. — Т. 10, вып. 1-4. — С. 657692.

34. Куликов А.И. Сжатие растровых изображений нейронными сетями Цао Ена / А.И. Куликов, Н.В. Михальченко // Труды 11-й международной конференции по компьютерной графике и машинному зрению ГрафиКон-2001, Нижний Новгород, 10-15 сентября 2001 г. — С. 231-236.

35. Кучеренко И.В. О числе обратимых однородных структур // Дискретная математика. — 2003 — Т. 15, вып. 2. — С. 123-127.

36. Кучеренко И.В. Об условиях разрешимости обратимости булевых клеточных автоматов // Интеллектуальные системы. — 2007. — Т. 11, вып. 1-4. — С. 765-768.

37. Лужков Ю.В. Метод адаптивного скалярного квантования в схемах необратимого сжатия изображений // Известия вузов. Приборостроение. — 2009. — Т. 52, № 3. — С. 12-17.

38. Лукин В.В. Анализ эффективности сжатия изображений в соответствии с различными критериями качества / В.В. Лукин, H.H. Пономаренко, С.С. Кривенко // Радиоэлектроника и информатика. — 2007. — №2. —С. 80-85.

39. Макклеллан Дж.Г. Применение теории чисел в цифровой обработке сигналов / Дж.Г. Макклеллан, Ч.М. Рейдер. — М.: Радио и связь, 1983. — 264 с.

40. Малла С. Вэйвлеты в обработке сигналов. — М.: Мир, 2005. — 671 с.

41. Мартышевский Ю.В. Применение фракталов для обработки изображений в телевизионных автоматических системах // Доклады ТУСУРа. — 2006. — № 6. — С. 57-62.

42. Мастрюков Д. Алгоритмы сжатия информации. Часть 7. Сжатие графической информации // Монитор. — 1994. — № 6. — С. 12-17.

43. Миано Дж. Форматы и алгоритмы сжатия изображений в действии.

44. М.: Издательство Триумф, 2003. — 336 с.

45. Наумов JI. Клеточные автоматы. Реализация и эксперименты / JI. Наумов, А. Шалыто // Мир ПК. — 2003. — № 8. — С. 64-78.51.0ппенгейм A.B. Цифровая обработка сигналов / A.B. Оппенгейм, Р.В. Шафер. — М.: Связь, 1979. — 416 с.

46. Павлидис Т. Алгоритмы машинной графики и обработки изображений. —М.: Радио и связь, 1986.

47. Пономаренко H.H. Неравномерное квантование в сжатии изображений // Радиоэлектронные и компьютерные системы. — 2008. — №3(30). —С. 62-65.

48. Пономаренко H.H. Метрика визуального качества изображений для корректного учета искажений яркости и контраста / H.H. Пономаренко, О.И. Еремеев, В.В. Лукин // Радиоэлектронные и компьютерные системы. — 2009.1 (35). —С. 36-41.

49. Потапов В.Н. Обзор методов неискажающего кодирования дискретных источников // Дискретный анализ и исследование операций. — Октябрь-декабрь 1999. — Серия 1, т. 6, № 4. — С. 49-91.

50. Потапов В.Н. Арифметическое кодирование сообщений с использованием случайных последовательностей // Прикладная дискретная математика. — 2008. — № 2 (2). — С. 131-133.

51. Прэтт Э. Цифровая обработка изображений. — Кн. 1. — М.: Мир, 1982. —312 с.

52. Рябко Б.Я. Эффективный метод адаптивного арифметического кодирования для источников с большими алфавитами / Б .Я. Рябко, А.Н. Фионов // Проблемы передачи информации. — 1999. — Т. 35, вып. 4. — С. 95-108.

53. Сато Ю. Обработка сигналов. Первое знакомство. — М.: Додэка, 2002. — 175 с.

54. Семенюк В.В. Экономное кодирование дискретной информации. — СПб.: СПбГИТМО (ТУ), 2001. — 115 с.

55. Семенюк B.B. Обзор стандарта JPEG2000 Электронный ресурс. Режим доступа: http://compression.ru/download/articles/ipeg/semeniuk 2001 ipeg2000.pdf.

56. Симаков A.B. Прогрессивная передача изображений через Интернет // Нелинейные проблемы механики и физики деформируемого твердого тела. — 2004. —Вып. 8. —С. 147-161.

57. Сойфер В.А. Теоретические основы цифровой обработки изображений: учебное пособие / В.А. Сойфер, В.В. Сергеев, С.Б. Попов, В.В. Мясников. — Самара: Самарский государственный университет имени академика С.П. Королева, 2000. — 256 с.

58. Столниц Э. Вейвлеты в компьютерной графике / Э. Столниц, Т. ДеРоуз, Д. Салезин. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2002. — 272 с.

59. Сэломон Д. Сжатие данных, изображений и звука. — М.: Техносфера, 2004. — 368 с.

60. Тимбай Е.И. Применение корректирующего фильтра для повышения качества изображений, сжатых методом JPEG // Компьютерная оптика. — 2011.1. Т. 35, №4. С. 513-518.

61. Тоффоли Т. Машины клеточных автоматов / Т. Тоффоли, Н. Марголус. — М.: Мир, 1991. — 280 с.

62. Трахтман A.M. Основы теории дискретных сигналов на конечных интервалах / A.M. Трахтман, В.А. Трахтман. — М.: «Сов. радио», 1975. — 208 с.

63. Умняшкин C.B. Оптимизация кодирования цифровых изображений по методу JPEG / C.B. Умняшкин, М.В. Космач // Известия вузов. Электроника.2000. —№4-5. —С. 139-141.

64. Умняшкин C.B. Использование контекстного арифметического кодирования для повышения сжатия данных по схеме JPEG // Известия вузов. Электроника. — 2001. — № 3. — С. 96-99.

65. Умняшкин C.B. Контекстное кодирование коэффициентов дискретного косинусного преобразования на основе межблочной корреляции в JPEG-подобной схеме компрессии / C.B. Умняшкин, Е.А. Безуглова // Цифровая обработка сигналов. — 2004. — № 2. — С. 13-17.

66. Умняшкин C.B. Алгоритм сжатия изображений на основе дискретного псевдокосинусного преобразования / C.B. Умняшкин, В.В. Курина // Цифровая обработка сигналов. — 2009. — № 3. — С. 2-7.

67. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. — М.: Издательство Триумф, 2003. — 320 с.

68. Френке JI. Теория сигналов. — М.: «Сов. радио», 1974. — 344 с.

69. Фурман Я.А. Цифровые методы обработки и распознавания бинарных изображений / Я.А. Фурман, А.Н. Юрьев, В.В. Яншин. — Красноярск: Изд-во Краснояр. ун-та, 1992. — 248 с.

70. Холл М. Комбинаторика. — М.: Мир, 1970. — 424 с.

71. Хуанг Т.С. Быстрые алгоритмы в цифровой обработке изображений / Т.С. Хуанг, Дж.-О. Эклунд, Г.Дж. Нуссбаумер, Ш. Зохар, Б.И. Юстуссон, Ш.-Г. Тян. — М.: Радио и связь, 1984. — 224 с.

72. Яне Б. Цифровая обработка изображений. — М.: Техносфера, 2007. — 584 с.

73. Яншин В.В. Обработка изображений на языке Си для IBM PC: алгоритмы и программы / В.В. Яншин, Г.А. Калинин. — М.: Мир, 1994. — 240 с.

74. Ярославский Л.П. Введение в цифровую обработку изображений

75. Acharya Т. Image processing principles and application / T. Acharya, A.K. Ray. — Hoboken, New Jersey: John Wiley & Sons, Inc., 2005. — 428 p.

76. Biswas S. Bézier and splines in image processing and machine vision / S. Biswas, B.C. Lovell. — London: Springer-Verlag, 2008. — 246 p.

77. Britanak V. Discrete cosine and sine transforms / V. Britanak, P.C. Yip, K.P. Rao. — London: Academic Press, 2006. — 349 p.

78. Broughton S.A. Discrete Fourier analysis and wavelets / S.A. Broughton, K. Bryan. — Hoboken, New Jersey: John Wiley & Sons, Inc., 2009. — 337 p.

79. Ceccherini-Silberstein T. Cellular automata and groups / T. Ceccherini-Silberstein, M. Coornaert. — Berlin: Springer-Verlag, 2010. — 439 p.

80. Chan T.F. Image processing and analysis: variational, PDE, wavelet, and stochastic methods. / T.F. Chan, J. Shen. — Philadelphia: SIAM, 2005. — 400 p.

81. Codd E.F. Cellular automata. — London: Academic Press, Inc., 1968. —122 p.

82. Crane R. Simplified approach to image processing: classical and modern techniques in C. — Upper Saddle River, New Jersey: Prentice Hall PTR, 1997. — 317 p.

83. Dwayne P. Image processing in C. — Electronic Edition 1.0, 26 April 2000. — 794 p.

84. Ilachinski A. Cellular automata. A discrete universe. — Singapore: World Scientific, 2001, —808 p.

85. ISO/IEC 10918-1 and ITU-T Recommendation T.81, Information technology — Digital compression and coding of continuous-tone still images — Requirements and guidelines, 1993. — 182 p.

86. ISO/IEC 15444-1 and ITU-T Recommendation T.800, Information technology — JPEG 2000 image coding system, 2002. — 190 p.

87. Jähne B. Digitale Bildverarbeitung. — Berlin: Springer-Verlag, 2002. —618 s.

88. Jain A.K. Fundamentals of digital image processing. — New Jersey: Prentice Hall, 1989. — 565 p.

89. Keinnert J. Design of image processing embedded systems using multidimensional data flow / J. Keinert, J. Teich. — New York: Springer Science+Business Media, 2011. — 311 p.

90. Koschan A. Digital color image processing / A. Koschan, M. Abidi. — Hoboken, New Jersey: John Wiley & Sons, Inc., 2008. — 375 p.

91. Lafe O. Data compression and encryption using cellular automata transforms // Engineering Applications of Artificial Intelligence. — 1997. — Vol. 10, №6. —P. 581-591.

92. Marcelin M. An Overview of JPEG-2000 / M. Marcelin, M. Gormish, A. Bilgin, M. Boliek // IEEE Data Compression Conference. — Snowbird, Utah, March 2000. —P. 523-541.

93. Salomon D. Data compression: the complete reference, 4th Edition. — London: Springer-Verlag, 2007. — 1111 p.

94. Schiff J.L. Cellular automata. A discrete view of the world. — Hoboken, New Jersey: John Wiley & Sons, Inc., 2008. — 252 p.

95. Strutz T. Bilddatenkompression. — Wiesbaden: Vieweg+Teubner, 2009. — 394 s.

96. Velho L. Image processing for computer graphics and vision / L. Velho, A.C. Frery, J. Gomes. — Second edition. — London: Springer-Verlag, 2009. — 4631. P.

97. Voorhees B.H. Computational analysis of one-dimensional cellular automata. — Singapore: World Scientific, 1996. — 275 p.

98. Witten I. Arithmetic coding for data compression / I. Witten, M. Radford, J. Cleary // Communications of the ACM. — June 1987. — Vol. 30, №6. —P. 520-540.

99. Woods J. W. Multidimensional signal, image, and video processing and coding. — Rensselaer Polytechnic Institute, Troy, New York, 2006. — 493 p.