28

Размещено на http://www.allbest.ru/

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук

Двухэтапные методы и алгоритмы сжатия цифровых изображений на основе дискретных преобразований Уолша

Специальность: 05.13.18 - Математическое моделирование,

численные методы и комплексы программ

Васильева Марина Юрьевна

Казань - 2010

Работа выполнена в Институте проблем информатики АН РТ и в Казанском государственном технологическом университете

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

Исмагилов Ильяс Идрисович

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

Захаров Вячеслав Михайлович

доктор технических наук, профессор

Столов Евгений Львович

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

университет

Защита состоится "25" июня 2010 г. в часов на заседании диссертационного совета Д 212.079.01 в Казанском государственном техническом университете им.А.Н. Туполева по адресу: 420111, г. Казань, ул.К. Маркса, 10, зал заседаний ученого совета.

С диссертацией можно ознакомиться в научной библиотеке Казанского государственного технического университета им.А.Н. Туполева. Автореферат диссертации размещен на сайте Казанского государственного технического университета им.А.Н. Туполева www.kai.ru.

Автореферат разослан " " 2010 г.

Ученый секретарь диссертационного совета

доктор физ. - мат. наук, профессор П.Г. Данилаев

Общая характеристика работы

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

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

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

Значительный вклад в решение проблем обработки изображений с использованием дискретных ортогональных преобразований внесли как отечественные, так и зарубежные ученые: Л.П. Ярославский, Н.Н. Красильников, А.М. Трахтман, С.В. Умняшкин, Д.С. Ватолин, В.В. Сергеев, У. Прэтт, Н. Ахмед, К.Р. Рао, Д. Селомон, Р.С. Гонсалес, Д.А. Хаффман и др. Интерес исследователей к дискретным ортогональным преобразованиям связан со следующими причинами: большой набор систем базисных функций позволяет выбрать наиболее рациональную систему для решения конкретной задачи; появление задач цифровой обработки сигналов, решаемых наиболее эффективно с использованием новых дискретных базисов; успехи в области создания средств вычислительной техники на многозначной элементной базе и использованием нетрадиционных арифметик.

Среди алгоритмов с преобразованием фактическим стандартом является алгоритм JPEG (Joint Photographic Experts Group), поддерживаемый многочисленными программными и аппаратными системами цифровой обработки, хранения и передачи изображений. Однако этот алгоритм имеет низкую скорость работы и сложен в аппаратной реализации.

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

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

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

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

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

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

· анализа известных методов сжатия цифровых изображений и подходов к оценке их эффективности;

· построения новых фиксированных способов упорядочения дискретных функций Уолша (ДФУ) и быстрых алгоритмов преобразований по ним;

сжатие изображение цифровое дискретное преобразование

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

· разработки алгоритмов СИ на основе ДПУ, реализующих двухэтапный метод;

· оценки эффективности предложенных методов и алгоритмов СИ;

· программной реализации предложенных алгоритмов СИ и выработки рекомендаций по их применению для решения различных практических задач.

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

Научная новизна. В диссертационной работе получены следующие новые научные результаты:

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

2. Предложен двухэтапный метод к СИ на основе ДПУ, в котором предусматривается дополнительная обработка элементов двумерного спектра экстраполяционными методами.

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

4. Обоснована возможность использования двухэтапных алгоритмов СИ для прогрессивного сжатия изображений и предложен метод прогрессивной передачи трансформант Уолша.

Достоверность результатов работы. Положения диссертационной работы получены при использовании строгого математического аппарата, а также согласованности полученных новых результатов с известными. Достоверность научных результатов подтверждена данными компьютерного экспериментального исследования в программной среде Matlab 6.5 и разработанной в интегрированной среде Borland C++ 2005 программы кодирования/декодирования "Image Compressor JPGW".

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

Реализация и внедрение результатов работы. Основные положения работы использованы при выполнении прикладной научно-исследовательской работы АН РТ "Разработка методов решения задач управления развитием систем цифровой обработки информации и совершенствование их алгоритмических средств" (Институт проблем информатики АН РТ, 2006-2008 гг.).

Теоретические и практические результаты диссертационной работы используются в научных исследованиях и разработках ООО "КЭР-Инжиниринг", а также внедрены в учебный процесс по дисциплине "Цифровые методы анализа" на кафедре систем автоматизации и управления технологическими процессами Казанского государственного технологического университета.

На основании результатов диссертационной работы разработана программа по кодированию/декодированию изображений "Image Compressor JPGW", защищенная авторским свидетельством о государственной регистрации программы для ЭВМ № 2009615236.

Апробация работы. Основные положения и результаты диссертационного исследования докладывались и обсуждались на следующих научных конференциях и семинарах: международная научно-практическая конференция “Инфокоммуникационные технологии глобального информационного общества” (Казань, 2004, 2005, 2007-2009 гг.); межвузовская научно-практическая конференция “Современная торговля: теория, методология и практика” (Казань, 2005-2007 гг.); III-я республиканская научно-техническая конференция “Автоматика и приборостроение" (Казань, 2006 г.); 5-я международная конференция "Авиация и космонавтика-2006" (Москва, 2006 г.); всероссийская научно-техническая конференция “Современные инновационные технологии и оборудование” (Тула, 2006 г.); II-я международная научно-техническая конференция “Тинчуринские чтения” (Казань, 2007 г.); всероссийская научная конференция “Информационные технологии в науке, образовании и производстве” (Казань, 2007 г.); международная конференция студентов, аспирантов и молодых ученых "Ломоносов" (Москва, 2008 г.); международная молодежная научная конференция “Туполевские чтения” (Казань, 2008 г.); международная научно-практическая конференция “Радиолокация, навигация и связь”, (Воронеж, 2009 г.); всероссийская конференция “Проведение научных исследований в области обработки, хранения, передачи и защиты информации” (Ульяновск, 2009 г.); республиканский научный семинар "Методы моделирования" при КГТУ им.А.Н. Туполева, (Казань, 2009 г.).

Публикации. По теме диссертации опубликовано 21 научная работа, включая 4 статьи и 17 тезисов докладов, в том числе 1 статья в журнале, рекомендованном ВАК. Получено 1 авторское свидетельство на программу для ЭВМ.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка (157 наименований). Работа содержит 153 страницы машинописного текста, 40 рисунков и 19 таблиц.

Содержание работы

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

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

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

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

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

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

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

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

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

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

Совершенствование JPEG-подобных алгоритмов СИ на основе ДПУ возможно по следующим направлением:

1. Синтез и исследование возможности использования в СИ новых упорядочений систем ДФУ.

2. Разработка новых алгоритмов кодирования коэффициентов преобразования (трансформант) изображения.

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

4. Разработка алгоритмов гибридного кодирования.

В работе сделан вывод о возможном повышении показателей СИ при использовании двухэтапного подхода к СИ на основе ДПУ и при введении новых способов упорядочения ДФУ.

Во второй главе приведены основные характеристики и свойства ДФУ и их упорядочений (Уолша-Качмажа, Уолша-Пэли, Уолша-Адамара). Предложен новый метод построения фиксированных упорядочений ДФУ на основе свойств их конечно-разностных представлений.

Предлагаемый метод упорядочения систем ДФУ размерности , n - целое число больше 1, заключается в следующем:

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

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

Очевидно, что множество определяет перестановку функций Уолша в системе

.

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

В работе проведены исследования свойств и получены соотношения для формирования перестановочной последовательности для построения разностно-упорядоченной системы функций Уолша на основе систем Уолша-Пэли и Уолша-Адамара.

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

,

где , ;

, - подвекторы, определяемые рекуррентными соотношениями:

.

На основе полученного вектора значений перестановочной последовательности разностно-упорядоченную систему ДФУ описать следующим образом:

,

где - соответственно i-е функции Уолша-Пэли.

- матрица перестановок, элементы которой формируются так:

Установлены следующие свойства преобразований по введенным упорядочениям систем функций Уолша-Пэли:

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

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

Свойство 3. Спектры дискретных степенных полиномов низких порядков в базисах разностно-упорядоченных ДФУ характеризуются большей степенью локализации ненулевых компонент в их начальных участках.

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

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

В работе предлагаются быстрые алгоритмы одномерных и двумерных преобразований в разностно-упорядоченных системах ДФУ. Двумерные преобразования реализованы как на основе быстрых одномерных алгоритмов ДПУ построчно-столбцовым способом, так и путем вытягивания строк двумерного массива в одномерный. При втором варианте выигрыш достигается на уровне организаций вычислений (отсутствие операций транспонирования, работа с одномерным массивом).

Третья глава посвящается разработке двухэтапного метода к СИ на основе ДПУ, в котором предусматривается дополнительная обработка элементов двумерного спектра экстраполяционными методами, и разработке соответствующих JPEG-подобных алгоритмов СИ.

В основу двухэтапного метода положено следующее свойство разложения дискретных степенных функций k-го порядка (k=1,2.,n) по одномерным ДФУ размерности N: в пределах групп коэффициентов преобразования k-го и (k-1) - го дифференциальных порядков между коэффициентами наблюдаются двоичные зависимости.

Указанное свойство разложения дискретных степенных функций k-го порядка (k=1,2.,n) по ДФУ k-го ранга упорядоченным по Пэли, размерности :

,

где - коэффициенты разложения; - номер разряда двоичного кода номера ДФУ, содержащий 1.

Из этого свойства следует, что по первым элементам групп коэффициентов Уолша k-го и (k-1) - го дифференциальных порядков их двоичным масштабированием могут быть получены остальные элементы этих групп:

(1)

. (2)

Учет этих соотношений в случае разложения полиноминальных сигналов невысоких порядков (k=1,2) по двумерным ДФУ размерности NхN позволяет передавать или сохранять соответственно три и шесть коэффициентов Уолша (нулевой коэффициент и соответственно первые коэффициенты групп коэффициентов первого и второго дифференциальных порядков). По ним можно точно восстановить исходный полиномиальный сигнал, восстанавливая остальные коэффициенты по формулам (1,2).

Для точного восстановления полиномиальных сигналов более высоких порядков (k>2) и произвольных исходных сигналов необходимо знать первые коэффициенты (трансформанты-представители) групп коэффициентов и погрешности аппроксимации остальных коэффициентов по ним:

где - двоичные веса, .

Отметим, что это свойство при оперировании дифференциальными порядками коэффициентов преобразования имеет место при любом упорядочении ДФУ в системе.

В основе предлагаемого метода к СИ лежит двухэтапная обработка блоков размером 8х8 исходного изображения, которая заключается в следующем:

1. Вычисляется двумерный спектр Уолша.

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

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

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

г) д) е) г) д) е)
Рис.1. Разложение двумерного полиномиального сигнала k-го (k=) порядка при N=8 в базисе разностно-упорядоченных ДФУ по дифференциальным порядкам : а) d=1, б) d=2, в) d=3, г) d=4, д) d=5, е) d=0,6

Алгоритм включает в себя следующие шаги:

1. Преобразование цифрового изображения из цветовой системы RGB в цветовую систему YСbCr.

2. Субдискретизация цветовых компонент изображения Cb, Cr. Укрупнение пикселов делается в соотношении [2: 1] по горизонтали и вертикали - так называемое укрупнение 2h2v. Эта операции не применяется для компоненты яркости Y.

3. Вычисление двумерного прямого дискретного ортогонального преобразования компонент изображения, разбитых на блоки размером 8x8 пикселей. Для компоненты яркости Y выполняется ДКП. Для компонент цветности Cb, Cr выполняется ДПУ.

4. Экстраполяция трансформант Уолша и вычисление ошибок предсказания трансформант, охваченных парциальными процедурами экстраполяции.

5. Квантование спектра ДКП и полученных значащих трансформант и ошибок предсказания трансформант Уолша, охваченных экстраполяционными процедурами.

6. Перевод матрицы размерности 8х8 в 64-элементный вектор при помощи "зигзаг"-сканирования. Вычитание нулевых трансформант соседних блоков.

7. Обратимая упаковка векторов с помощью алгоритма группового кодирования RLE64.

8. Сжатие полученных векторов методом Хаффмана.

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

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

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

1. Изображение делится на блоки X размером 8x8, затем блоки обрабатываются каждым алгоритмом.

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

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

Предложена реализация двухэтапного алгоритма СИ с многопотоковым кодированием трансформант Уолша. Основные изменения в структуру JPEG-подобного алгоритма СИ с экстраполяцией трансформант Уолша вносятся при обработке спектров блоков цветовых компонент. Обработка спектров блоков размера 8х8 проводится в два этапа:

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

2. На втором этапе полученные потоки независимо кодируются алгоритмами RLE и Хаффмана.

В алгоритме используется разностно-упорядоченая система ДФУ, это упрощает запись в различные выходные потоки групп трансформант Уолша определенных дифференциальных порядков.

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

В работе обоснована возможность использования двухэтапных алгоритмов СИ для прогрессивного сжатия и предложен метод прогрессивной передачи трансформант, полученных путем преобразования в двумерном базисе разностно-упорядоченных ДФУ.

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

а) б)

Рис. 2. Организация передачи данных: а) ДКП, б) разностно-упорядоченные ДФУ

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

Проведена оценка вычислительной сложности алгоритма JPEG и JPEG-подобных алгоритмов реализующих традиционный и двухэтапный методы к СИ. При анализе вычислительной сложности алгоритмов СИ придерживались модели вычислений:

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

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

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

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

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

1. Изображение делится на блоки размерности 8x8 и определяются относительные частоты p_i, i=, появления блоков, описываемых двумерными дискретными степенными полиномами. При этом величины p_i, i=, определяются как относительные частоты появления блоков, описываемых полиномами i-го (i=) порядка, а p₇ - как относительная частота появления блоков, описываемых полиномами i-го (i=) порядка.

2. Рассчитывается коэффициент выигрыша в сжатии по числу координат разложения.

Максимальный порядок двумерного степенного полинома, описывающего блок изображения размерности 8х8, равен 14, а максимальный дифференциальный порядок двумерных ДФУ - 6. Коэффициент выигрыша по сжатию по числу координат разложения представлен в виде соотношения КС традиционного и предложенного алгоритмов при нулевой погрешности восстановления изображений.

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

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

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

В работе проведен анализ разработанных алгоритмов сжатия с преобразованием по следующим известным системам упорядочений ДФУ: Уолша-Качмажа, Уолша-Пэли, Уолша-Адамара. Исследованы также алгоритмы СИ на основе построенных разностно-упорядоченых ДФУ.

Для выбора наиболее эффективного алгоритма СИ был разработан программный экспериментальный комплекс, реализованный в среде Matlab. В данной среде алгоритмы были реализованы с графическим интерфейсом на встроенном языке программирования Matlab.

Тестовый материал был представлен выборкой из стандартного тестового набора Waterloo Bragzone (Calgary Corpus), составленного из цветных изображений в 24 битовом формате BMP. При анализе были использованы следующие показатели СИ: КС по битам, пиковое отношение сигнал/шум (PSNR). Осуществлялась также визуальная оценка качества восстановленного изображения.

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

1. Двухэтапный алгоритм СИ с упорядочением ДФУ по Качмажу с частичной экстраполяцией с однопоточным кодированием (рис.3).

Используемый алгоритм характеризуется хорошими скоростными свойствами. При высоком качестве восстановленного изображения выигрывает по КС от 1 до 6 % у алгоритма СИ на основе ДПУ, использующего традиционный подход к сжатию. При среднем качестве восстановленного изображения показывает схожий КС с алгоритмом JPEG.

Рис.3. Структура кодера JPEG-подобного двухэтапного алгоритма СИ на основе ДПУ с однопоточным кодированием (ОПТ - ошибки преобразования трансформант, Т - таблицы)

2. Двухэтапный алгоритм на основе преобразований в разностно-упорядоченных ДФУ с многопоточным кодированием (рис.4).

Используемый алгоритм характеризуется оптимальными соотношениями скорости и эффективности сжатия. При высоком качестве полученных изображений показывает схожие КС с алгоритмом JPEG и выигрывает по КС от 6 до 24% у алгоритма СИ на основе ДПУ, использующего традиционный подход к сжатию. При среднем качестве восстановленного изображения отмечается увеличение метрики PSNR на 0,6 dB по сравнению с алгоритмом JPEG.

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

Рис.4. Структура кодера JPEG-подобного двухэтапного алгоритма СИ на основе ДПУ с многопоточным кодированием (ЗТ - значащие трансформанты, ВПД - выходные потоки данных)

В работе проведена программная реализация выбранных алгоритмов - разработана программа кодирования/декодирования "Image Compressor JPGW", которая представляет собой приложение для операционной среды Windows, разработанное в интегрированной среде Borland C++ 2005 и позволяет кодировать и декодировать изображения при различной степени сжатия.

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

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

Результаты работы по созданию алгоритмического и программного обеспечения для сжатия изображений используются в научной и конструкторской деятельности ООО "КЭР-Инжиниринг" по следующим направлениям:

· создание эффективных архивов тепловизионных изображений объектов контроля, требующих использования средств их сжатого представления;

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

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

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

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

Основные результаты работы

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

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

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

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

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

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

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

· при среднем качестве восстановленного изображения увеличение метрики PSNR в среднем от 0,3 до 0,8 dB по сравнению с алгоритмом JPEG при гораздо меньших требованиях к аппаратным ресурсам.

7. Разработана программа "Image Compressor JPGW", которая позволяет кодировать и декодировать изображения при различной степени сжатия в двух режимах: однопоточном и многопоточном. Получены экспериментальные результаты, подтверждающие эффективность разработанных методов и средств при решении задач сжатия изображений, возникающих в системах видеонаблюдения, тепловизионного контроля энергетических объектов и теплотехнического состояния зданий.

Список работ, опубликованных по теме диссертации

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

1. Исмагилов И.И., Васильева М.Ю. Сжатие цифровых изображений с использованием преобразований Уолша: алгоритмы и сравнительный анализ их эффективности // Известия высших учебных заведений. Проблемы энергетики. - Казань, 2008. - № 9-10. - С.91-99.

В других журналах и материалах научных конференций:

2. Исмагилов И.И., Васильева М.Ю. Синтез и анализ разностно-упорядоченной системы дискретных функций Уолша // Тезисы докладов 2-й межд. научно-практ. конф. "Инфокоммуникационные технологии глобального информационного общества". - Казань, 2004. - С.149.

3. Исмагилов И.И., Васильева М.Ю. Разностно-упорядоченные системы дискретных функций Уолша // Сборник трудов 2-й межд. науч. - практ. конф. "Инфокоммуникационные технологии глобального информационного общества". - Казань, 2004. - С.298-302.

4. Васильева М.Ю. JPEG-подобные алгоритмы сжатия цифровых изображений и направления их совершенствования // Материалы межвуз. научно-практ. конф. "Современная торговля: теория и практика". - Казань: Отечество, 2005. - С.60-61.

5. Исмагилов И.И., Васильева М.Ю. Об одном подходе к совершенствованию алгоритмов сжатия изображений на основе преобразований Уолша // Тезисы докладов 3-й межд. научно-практ. конф. "Инфокоммуникационные технологии глобального информационного общества". - Казань, 2005. - С.91-92.

6. Васильева М.Ю. Прогрессивная передача изображений с использованием алгоритмов сжатия на основе преобразований Уолша // Материалы межвуз. научно-практ. конф. "Современная торговля: теория и практика". - Казань, 2006. - С. 202.

7. Васильева М.Ю. Оптимизация алгоритмов сжатия изображений на основе преобразований Уолша // Материалы III респ. научно-техн. конф. "Автоматика и приборостроение". - Казань, 2006. - С.84-85.

8. Васильева М.Ю. Двухэтапный подход к сжатию изображений в JPEG-подобных алгоритмах // Тезисы докладов 5-й межд. конф. "Авиация и космонавтика-2006". - М., 2006. - С.184.

9. Исмагилов И.И., Васильева М.Ю. Оценка эффективности двухэтапных алгоритмов сжатия изображений на основе преобразований Уолша // Сборник "Исследования по информатике" / ИПИ АН РТ. - Казань, 2006. - вып.11. - С.95-102.

10. Васильева М.Ю. Алгоритм сжатия изображений на основе преобразований Уолша с экстраполяцией трансформант // Всерос. науч. - техн. конф. "Современные инновационные технологии и оборудование" / под общей ред. чл. - корр. РАН В.П. Мешалкина. - Тула, 2006. - С.37-39.

11. Васильева М.Ю. Сжатие изображений с использованием комбинированного алгоритма на основе преобразований Уолша // Материалы I-й межвуз. научно-практ. конф. "Современная торговля: теория, методология, практика". - Казань, 2007. - С.253-254.

12. Васильева М.Ю. Исследование эффективности двухэтапных алгоритмов сжатия изображений на основе преобразований в различных упорядочениях систем функций Уолша // Материалы докладов II молодеж. межд. науч. конф. "Тинчуринские чтения". - Казань, 2007. - С.140-141.

13. Васильева М.Ю. Алгоритм сжатия цифровых изображений с преобразованием в базисе разностно-упорядоченных функций Уолша с многопотоковым кодированием // Материалы всерос. научн. конф. "Информационные технологии в науке, образовании и производстве". - Казань, 2007. - С.273-274.

14. Исмагилов И.И., Васильева М.Ю. Многопоточное кодирование трансформант Уолша в JPEG-подобных алгоритмах сжатия изображений // Тезисы докладов 5-й межд. научно-практ. конф. "Инфокоммуникационные технологии глобального информационного общества". - Казань, 2007. - С.123-124.

15. Васильева М.Ю. Закиев А.А. Алгоритм сжатия изображений с экстраполяцией трансформант и оценка его вычислительной сложности // Материалы докладов XV межд. конф. студентов, аспирантов и молодых ученых "Ломоносов" / отв. ред. И.А. Алешковский, П.Н. Костылев, А.И. Андреев. - М., 2008. - 1 электрон. опт. диск (CD-ROM); 12 см. - [http://www.lomonosov-msu.ru/2008].

16. Васильева М.Ю. Алгоритм сжатия изображений на основе преобразований Уолша и оценка его вычислительной сложности. // XVI Туполевские чтения: межд. молодеж. научн. конф. - Казань, 2008. - Том III. - C.12-13.

17. Васильева М.Ю. Прогрессивная передача изображений с использованием алгоритмов сжатия на основе преобразований по разностно-упорядоченным дискретным функциям Уолша // Тезисы докладов 6-й межд. научно-практ. конф. "Инфокоммуникационные технологии глобального информационного общества". - Казань, 2008. - С.116-117.

18. Васильева М.Ю. Сравнительная оценка вычислительной сложности алгоритма сжатия изображений с преобразованием Уолша и алгоритма JPEG // Сборник докладов межд. научно-техн. конф. "Радиолокация, навигация, связь" RLNC-2009. - Воронеж, 2009. - Т.1. - С. 193-201.

19. Васильева М.Ю. Алгоритмическое обеспечение и программная реализация кодера-декодера сжатия цифровых изображений на основе дискретных преобразований Уолша // Тезисы докладов 7-й межд. научно-практ. конф. "Инфокоммуникационные технологии глобального информационного общества". - Казань, 2009. - Режим доступа: http://iktgio. mcrt.ru/rus/info. php? id=9372.

20. Васильева М.Ю. Сжатие цифровых изображений с использованием двухэтапных JPEG-подобных алгоритмов сжатия на основе дискретных преобразований Уолша // Труды всерос. конф. “Проведение научных исследований в области обработки, хранения, передачи и защиты информации”. - Ульяновск, 2009. - С.212-214.

Авторское свидетельство на программу для ЭВМ:

21. Свидетельство об официальной регистрации программы для ЭВМ 2009615236. "JPGW Image Compressor" / Исмагилов И.И., Васильева М.Ю. - Заявка № 2009614007; Дата поступления 23.07.2009; Зарегистрировано в Реестре баз данных 22.09.2009.

Размещено на Allbest.ru

...