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

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

ВАСИЛЬЕВА МАРИНА ЮРЬЕВНА

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

УОЛША

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

АВТОРЕФЕРАТ

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

004605494

Казань-2010

004605494

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

Научный руководитель:

доктор технических наук, профессор Исмагилов Ильяс Идрисович

Официальные оппоненты:

доктор технических наук, профессор Захаров Вячеслав Михайлович

доктор технических наук, профессор Столов Евгений Львович

Ведущая организация:

Марийский государственный технический университет

Защита состоится «25» июня 2010 г. в_часов на заседании диссертационного

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

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

Автореферат разослан «_»_2010 г.

Ученый секретарь диссертационного совета доктор физ.-мат. наук, профессор

П.Г. Данилаев

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

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

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

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

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

Среди алгоритмов с преобразованием фактическим стандартом является алгоритм JPEG (Joint Photographie Experts Group), поддерживаемый

N

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные положения и результаты диссертационного исследования докладывались и обсуждались на следующих научных конференциях и семинарах: международная научно-практическая конференция "Инфокоммуникационные технологии глобального информационного общества" (Казань, 2004, 2005, 2007-2009 гг.); межвузовская научно-практическая конференция "Современная торговля: теория, методология и практика" (Казань, 2005-2007 гг.); III-я республиканская научно-техническая конференция "Автоматика и приборостроение" (Казань, 2006 г.); 5-я международная конференция «Авиация и космонавтика-2006» (Москва, 2006 г.); всероссийская научно-техническая конференция "Современные инновационные технологии и оборудование" (Тула, 2006 г.); И-я международная научно-техническая конференция "Тинчуринские чтения" (Казань, 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 =2" п- целое число больше 1, заключается в следующем:

1. Строится разбиение множества порядковых номеров функций Уолша исходной системы I = {0,1,...,А' -1} на (и+1) подмножеств, каждое из которых включает номера функций с одинаковыми дифференциальными порядками. Под дифференциальным порядком будем подразумевать порядок операторов конечной разности, формирующих эту функцию.

2. Затем сформированные подмножества располагают в порядке увеличения дифференциальных порядков соответствующих функций, то есть в итоге получаем множество J = {.Г0,«Г,,...,.!„}.

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

_ ГО 1 ... N - 11 [Уо )\ •■■ }

Полученная в результате этой перестановки разностно-упорядоченная система ДФУ будет характеризоваться тем, что функции в ней располагаются группами в порядке возрастания их дифференциальных порядков. Для вектора перестановочной последовательности будем придерживаться обозначения Р„ =(А>, А.---,Луч), где а =Л'г' = 0.ЛГ-1.

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

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

р _ /р(0) р(1) р(2) р(»)ч

1 II И 'Хп ' 1 II >-•->*» />

где Р,(0) = (0), Г,от = (2' -1), / = Щ;

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

р№>_[(2'-1), / = *,_

' ~ [(Р/-?> 2'"1 + ),1 = к + \,п, (= к,п.

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

рМ„(/) = ра1„Ы, ' = 0,^-1,

где ра1д, (/) - соответственно /-е фикции Уолша-Пэли.

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

= Г1, если ] = р,, ® (0, в остальных случаях.

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

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

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

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

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

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

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

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

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

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

Nk

F(2"' +2"' + ... + 2") = (-1/

где (2Л +2"' + ... + 2"' ) - коэффициенты разложения; (/ = 1,&) - номер разряда двоичного кода номера ДФУ, содержащий 1.

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

F(2" + 2*1 + ...+ 2"')= F(2° + 21 + ...+ 2i-I)2"[(,+2+-+i"1H/,'+"2+-/")]> (1)

F(2" + 2* +...+ 2"» ) = F( 2° + 2'...+ 2*-2)2"[(,+а+-**"гНл*А+-"*-,Я .(2)

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

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

где 2 1 - '' - двоичные веса, г = \,к-2.

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

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

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

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

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

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

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

I 2 4

; 1

2

4

1 2 4

1: 2 4

2 4 8

4 8 16

1

2

4

1 2 А

2 4 8

4 8 16

.1 2 4

2 4 8

4 8 16

Д)

е)

1

2

4

1 2 4

2 4 8

4 S 16

1, 2 А

2

4

1 2 4

г) д) е)

Рис. 1. Разложение двумерного полиномиального сигнала к-то (кг 0~6 ) порядка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

M

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

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

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

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

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

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

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

трансформант, полученных путем преобразования в двумерном базисе разностно-упорядоченных ДФУ.

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

а) б)

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

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

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

С(а) = ц^ Ad + fixMu + fi^_Sh2, где Ad,Mu,Sh2- соответственно число целочисленных операций сложения, умножения на константы и двоичного сдвига на требуемое количество двоичных разрядов; , Цх, M- , - веса соответствующих операций.

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

соответствующих операций ¿i+=l,/jx=l,fj+_=l и =!,/их = =1

(характеристики процессора Pentium 4 при работе с внутренними регистрами).

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

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

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

1. Изображение делится на блоки размерности 8x8 и определяются

относительные частоты р„ i=0j, появления блоков, описываемых двумерными

дискретными степенными полиномами. При этом величиныг=0,6, определяются как относительные частоты появления блоков, описываемых полиномами г'-го (/-

0^6) порядка, а р; - как относительная частота появления блоков, описываемых полиномами /-го (г= 7,14 ) порядка.

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

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

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

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

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

В работе проведен анализ разработанных алгоритмов сжатия с преобразованием по следующим известным системам упорядочений ДФУ: Уолша-

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

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

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

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

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

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

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

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

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

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

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

В работе проведена программная реализация выбранных алгоритмов -разработана программа кодирования/декодирования «Image Compressor JPGW», которая представляет собой приложение для операционной среды Windows, разработанное в интегрированной среде Borland С++ 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. Исмагилов И.И., Васильева М.Ю. Об одном подходе к совершенствованию алгоритмов сжатия изображений на основе преобразований Уолша II Тезисы докладов 3-й межд. научно-практ. конф. «Инфокоммуникационные технологии глобального информационного общества». - Казань, 2005. - С. 91-92.

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

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

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

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

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

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

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

13. Васильева M JO. Алгоритм сжатия цифровых изображений с преобразованием в базисе разностно-упорядоченных функций Уолша с многопотоковым кодированием // Материалы всерос. научн. конф. «Информационные технологии в науке, образовании и производстве». - Казань,

2007. - С. 273-274.

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

15. Васильева М.Ю. Закисв A.A. Алгоритм сжатия изображений с экстраполяцией трансформант и оценка его вычислительной сложности // Материалы докладов XV межд. конф. студентов, аспирантов и молодых ученых «Ломоносов» / отв. ред. И.А. Алешковский, П.Н. Костылев, А.И. Андреев. - М.,

2008. - 1 электрон, опт. диск (CD-ROM); 12 см. - [http://www.lomonosov-msu.ru/2008].

16. Васильева М.Ю. Алгоритм сжатия изображений на основе преобразований Уолша и оценка его вычислительной сложности. // XVI Туполевские чтения: межд. молодеж. научн. конф. - Казань, 2008. - Том III. - С. 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.

Издательство КГАУ/420015 г.Каэань, ул.К.Маркса, д.65 Лицензия на издательскую деятельность код 221 ИД №06342 от 28.11.2001 г. Отпечатано и типографии КГАУ 420015 г.Кэташ., ул.К.Маркса. д.65. Казанский гоеудпрсии-пный аграрный уппнерсптст

Формат 60x84/1 б Тираж 100. Печать офсетная. Усл.п.л. 1,00.

Подписано к печати ^ 05.20ТОГ. Заказ 54.

СОКРАЩЕНИЯ.

ВВЕДЕНИЕ.

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

1.1. Основные классы изображений.

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

1.2.1. Сжатие без потерь.

1.2.2. Сжатие с потерями.

1.2.3. Стандарты сжатия цифровых изображений.

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

1.4. Постановка задач на исследование.

Выводы.

ГЛАВА 2. ПОСТРОЕНИЕ И ИССЛЕДОВАНИЕ СВОЙСТВ РАЗНОСТНО-УПОРЯДОЧЕННЫХ СИСТЕМ ДИСКРЕТНЫХ ФУНКЦИЙ УОЛША.

2.1. Краткий обзор дискретных функций Уолша и их упорядочений.

2.2. Синтез разностно-упорядоченной системы дискретных функций Уолша.

2.3. Свойства разностно-упорядоченных систем дискретных функций Уолша.

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

Выводы.

ГЛАВА 3. РАЗРАБОТКА ДВУХЭТАПНЫХ АЛГОРИТМОВ СЖАТИЯ ИЗОБРАЖЕНИЙ НА ОСНОВЕ ДИСКРЕТНЫХ ПРЕОБРАЗОВАНИЙ

УОЛША.

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

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

3.3. Комбинированный алгоритм сжатия изображений на основе дискретных преобразований Уолша.

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

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

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

Выводы.

ГЛАВА 4. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ДВУХЭТАПНЫХ АЛГОРИТМОВ СЖАТИЯ И ИХ ПРАКТИЧЕСКОГО ПРИМЕНЕНИЯ.

4.1. Исследование эффективности методов сжатия и качества восстановленных изображений.

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

4.1.2. Результаты исследования эффективности алгоритмов на тестовых изображениях.

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

4.2.1. Назначение и структура кодер-декодера.

4.2.2. Интерфейс программы.

4.3. Решение практических задач сжатия изображений.

Выводы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выводы

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

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

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

4. Приведено описание двух алгоритмов, реализованных в виде прикладной программы кодирования/декодирования «JPGW Image Compressor» работающей в среде Windows и защищенной авторским свидетельством:

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

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

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

ЗАКЛЮЧЕНИЕ

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

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. Агаян, С.С. Сложность и параллельные алгоритмы дискретных ортогональных преобразований / С.С. Агаян, Д.В. Геворкян // Кибернетика и вычислительная техника. 1988. - Вып.4. - С.146-215.

2. Агаян, С.С. Успехи и проблемы быстрых ортогональных преобразований и их реализация на ЭВМ (для обработки сигналов-изображений) / С.С. Агаян // Распознавание, классификация, прогноз. Математические методы и их применение. 1992. - Вып.З. - С. 124169.

3. Айзенберг, И. Н. Двухэтапный трансформационный метод кодирования изображений / И.Н. Айзенберг, Л.П. Ярославский // Компьютерная оптика. 1991. - № 9. - С. 48-56.

4. Айзенберг, Н.Н. Нейросети на многозадачных нейроэлементах: обучение, обработка и распознавание изображений / Н.Н. Айзенберг, И.Н. Айзенберг, Г.А. Кривошеев // Компьютерная оптика. 1995. — Т. 14-15.-С. 179-186.

5. Анализ эффективности применения искусственных нейронных сетей для решения задач распознавания, сжатия и прогнозирования / А.А. Талалаев, И.П. Тищенко, В.П. Фраленко, В.М. Хачумов // Искусственный интеллект и принятие решений. 2008. -№ 2. - С.24-33.

6. Ахмед, Н. Ортогональные преобразования при обработке цифровых сигналов / Н. Ахмед, К.Р. Рао. М.: Связь, 1980. - 248 с.

7. Баврина, А.Ю. "Метод иерархической компрессии видеоданных / А.Ю. Баврина, М.В. Гашников, В.В. Сергеев // Матем. моделирование и краев, задачи: труды всероссийской научной конференции. Часть 2. -Самара, 2004. - С. 26-29.

8. Бекренев, В. А. Разработка и моделирование алгоритмов сжатия полутоновых изображений на базе нейронных сетей / В.А. Бекренев,

9. С.С. Бухтояров, П.С. Звонарев // Перспективные технологии в средствах передачи информации ПТСПИ'2005: материалы 6 Межд. науч.-техн. конф. - Владимир, 2005. - С. 119-122.

10. Бекчанова, Ш.Б. Синтез быстродействующих спецпроцессоров Хаара на основе матричной диаграммы / Ш.Б. Бекчанова, Зайниддинов Х.Н. // Молодёжь в развитии науки и техники: тезисы докл. НТК. — Ташкент, 2002. С.78.

11. Бондарев, О.Ю. Применение камер глобального наблюдения СА-ZOOM PTZ на объектах ядерной энергетики / О.Ю. Бондарев, В.Р. Козлов // Контроль. Диагностика. 2005. - №8. - С. 21-22.

12. Будадин, О.Н. Технология комплексного теплового неразрушающего контроля зданий и строительных сооружений / О.Н. Будадин, Т.Е. Троицкий-Марков // Контроль. Диагностика. 2005. - №3. - С. 23-24.

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

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

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

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

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

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

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

20. Ватолин, Д. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео / Д. Ватолин, А. Ратушняк и др. М.: Диалог1. МИФИ, 2002.-384 с.

21. Ватолин, Д.С. Фрактальное сжатие изображение / Д.С. Ватолин // Computer World-Россия. 1996. -№ 6. -С. 21-28.

22. Галушкин, А.И. Нейроматематика (проблемы развития) / А.И. Галушкин. М.: Радиотехника, 2003. - 40 с.

23. Гашников, М.В. . Контроль степени сжатия при иерархической компрессии изображений / М.В. Гашников, Н.И. Глумов, В.В. Сергеев // Компьютерная оптика. 2004. - № 26. - С. 110-112.

24. Голубов, Б.И. Ряды и преобразования Уолша: Теория и применения / Б.И. Голубов, А.В. Ефимов, В.А. Скворцов. М.: Наука, 1987. - 344с.

25. Гольцов, А.Г. Разработка и исследование метода для сжатия полутоновых изображений, обеспечивающего быстрое восстановление: Дис. канд. тех. наук: 05.13.13 / А.Г. Гольцов. -Москва, 1998.- 141 с.

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

27. Горлов, С.К. Об одной реализации метода сжатия отображений с помощью нелинейной аппроксимации сумм Фурье-Хаара / С.К. Горлов, А.В. Корыстин, В.А. Родин // Теор. функций и прибл.: труды 7-й Саратов, зимней школы. Саратов, 1995. - Ч. 2.

28. Гришин, М.В. Методы сжатия цифровых изображений на основе дискретных вейвлет преобразований: Дис. канд. тех. наук: 05.13.13 / М.В. Гришин. СПб., 2005. - 153 с.

29. Дагман, Э.Е. Быстрые дискретные ортогональные преобразования / Э.Е. Дагман, Г.А. Кухарев. Новосибирск: Наука, 1983. - 230 с.

30. Ефимов, В.М. Оценка эффективности некоторых алгоритмов сокращения избыточности информации при абсолютной точности воспроизведения / В.М. Ефимов, Ю.Н. Золотухин, А.Н. Колесников // Автометрия. 1991. - № 6. - С. 50-55.

31. Задирака, В.К. Оптимальный способ зонного кодирования сиспользованием Слэнт-преобразования / В.К. Задирака, В.Н. Евтушенко // Кибернетика и системный анализ. 1994. - №4. — С. 5660.

32. Залманзон, J1.A. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях / JI.A. Залманзон. -М.: Наука, 1989.-496 с.

33. Зарипов, Т.Н. Ускоренные алгоритмы спектральных преобразований решающих диаграмм / Т.И. Зарипов, Р.Х. Латыпов // Исследования по информатике / ИЛИ АН РТ. 2003. - вып. 10. - С. 19-36.

34. Зимин Д.И. Технология определения восстанавливающего фильтра и обработки цветных изображений / Д.И. Зимин, В.А. Фурсов // Компьютерная оптика. -2005. вып. 27. - С. 170-173.

35. Ильин, В.П.Параллельные алгоритмы для больших задач: проблемы и технологии. / В.П. Ильин // Автометрия. 2007. - т. 43, № 2. - С. 3-21

36. Исмагилов, И.И. Дискретные преобразования в базисах Уолша-подобных функций: Основы теории и применения в цифровой обработке сигналов / И.И. Исмагилов. Казань: Отечество, 2003. -130 с.

37. Исмагилов, И.И. Об одном подходе к упорядочению систем дискретных функций Уолша / И.И. Исмагилов // Известия вузов. Радиоэлектроника. 2006. - Т. 49, N 1. - С. 65-72.

38. Исмагилов, И.И. Синтез и анализ Хааро-подобных дискретных базисов кусочно-полиномиальных функций / И.И. Исмагилов, Е.А. Суреев // Исследования по информатике / ИЛИ АН РТ. 2003. - вып. 8. - С. 3340.

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

40. Казарян, M.JI. Сжатие сигналов посредством дискретных ортогональных преобразований с регуляризацией: Дис. канд. физ.-мат. наук: Е13.05 / M.JI. Казарян. Ереван, 1995. - 77 с.

41. Карагодин, М.А. Алгоритм сжатия изображений на основе функций Уолша / М.А. Карагодин, А.Н. Осокин // Информационные системы и технологии: материалы межд. конф. ИСТ'2003. Новосибирск, 2003.1. Т. 2.-С. 126-130.

42. Карнеев, Д.В. Тепловизорная техника на службе охраны / Д.В. Карнеев, И.В. Богданов // Энергетик. 2005. - №12. - С. 42-43.

43. Кашкаров, В. Организация параллельных вычислений в алгоритмах БПФ на процессоре NM6403 / В. Кашкаров, С. Мушкаев // Цифровая обработка сигналов. 2001. - № 1.

44. Кашкаров, В. Организация параллельных вычислений преобразования Адамара на процессоре NM6403 (JI1879BM1) // Цифровая обработка сигналов. 2001. - № 3.

45. Кирушев, В.А. Быстрый алгоритм сжатия изображений / В.А. Кирушев // Вестник молодых ученых. Сер. прикладная математика и механика. 1997.-вып. 1.-С. 4-10

46. Копенков, В.Н. Эффективные алгоритмы локального дискретного вейвлет-преобразования с базисом Хаара// Компьютерная оптика. -2008.-№32.-С. 78-84.

47. Коршунова, Н.П. Повышение эффективности применения методов сжатия цифровых изображений: Дис. канд. тех. наук: 05.13.11 / Н.П. Коршунова. Тула, 2004. - 156 с.

48. Кочетков, М.Е. Многопотоковая реализация алгоритма арифметического кодирования / М.Е. Кочетков, С.В. Умняшкин. М.: МГИЭТ(ТУ), 1998.-21 с.

49. Красильников, Н.Н. Теория передачи и восприятия изображений / Н.Н. Красильников. М.: Радио и связь, 1986. - 248 с.

50. Кузьмин, С. Упаковка динамограммы в 50 байт / С. Кузьмин // Современные технологии автоматизации. 2004. — Режим доступа: http://www.cta.ru/online/onlineprogr-digital.htm.

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

52. Мастркжов, Д. Алгоритмы сжатия информации. Часть 2. Арифметическое кодирование / Д. Мастрюков // Монитор. 1994. — №1. - С. 20-26.

53. Миано, Дж. Форматы и алгоритмы сжатия изображений в действии: учеб. пособие / Дж. Миано. М.: Издательство Триумф, 2003. - 336 с.

54. Мюррей, Д.Д. Энциклопедия форматов графических файлов: пер. с англ. / Д.Д. Мюррей, У.Ван. Райнер. Киев: BHV, 1997, - 535 с.

55. Назаров, JI. Е. Нейросетевой фрактальный и JPEG алгоритмы сжатия изображения / Л. Е. Назаров, 3. Т. Назарова // Информационные технологии. М., 2001. -№1. - С.2-9.

56. Наместников, С.М. Разработка и моделирование алгоритмов сжатия изображений на основе неразделимых преобразований: Дис. канд. тех. наук: 05.13.13 / С.М. Наместников. Ульяновск, 2004. - 131 с.

57. Никитин, О.Р., Экспериментальное исследование методов сжатия медицинских изображений / О.Р. Никитин, Архипов Е.А., Пасечник

58. A.С., Аль-Хомза Наджи // Журнал «Биомедицинская радиоэлектроника». 2004. - №3. - С. 21-27.

59. Никифоров, А.Ф. Классические ортогональные полиномы дискретной переменной / А.Ф. Никифоров, С.К. Суслов, В.Б. Уваров. М.: Наука, 1985.-89 с.

60. Новиков, B.C. Исследование методов сокращения избыточности изображений посредством ортогонального преобразования Адамара для цифровых систем телевидения: Автореф. дис. канд. техн. наук. /1. B.C. Новиков. Л., 1979.

61. Пакет прикладных программ по цифровой обработке изобра-жений / П. Звонарев, А. Приоров, Е. Саутов, В. Хрящев // Доклады 7-й Межд. конф. «Цифровая обработка сигналов и ее применение». М., 2005. — Т.2.-С. 307-309.

62. Пеев, Е. Методи и средства за компрессия на изображения / Е. Пеев, К. Боянов, О. Белчева // Автоматика и информатика. 1994. - 28, №3.1. С. 3-14.

63. Печников, В.В. Тепловой контроль электрооборудования и требования, предъявляемые к аппаратуре /В.В. Печников // Энергетик. -2007. — №1. — С. 46-47.

64. Попов, С.А. Оценка точности изображения при сжатии графических файлов / С.А. Попов // Вестник НовГУ. Естественные и технические науки. 1998.-№ 10.-С. 11-14.

65. Попов, С.Б. Концепция распределенного хранения и параллельной обработки крупноформатных изображений / С.Б. Попов // Компьютерная оптика. 2007. - № 31. - С. 77-85.

66. Поспелов, А.С. Некоторые математические задачи и алгоритмы цифровой обработки информации с использованием дискретных преобразований: Дис. докт. физ.-мат. наук. / А.С. Поспелов. М., 1992. -398 с.

67. Проектирование специализированных информационно-вычислительных систем: учеб. пособие по спец. ЭВМ и АСУ / Ю.М. Смирнов, Г.Н. Воробьев, Е.С. Потапов, В.В. Сюзев. М.: Высшая школа, 1984.-359 с.

68. Прэтт, У. Цифровая обработка изображений: в 2 т. / У. Прэтт. М.: Мир, 1982.-312 и 480 с.

69. Птачек, М. Цифровое телевидение. Теория и техника: пер. с чешек. / М. Птачек; под ред. Л.С.Виленчика. М.: Радио и связь, 1990. - 528 с.

70. Ричардсон, Ян. Видеокодирование. Н.264 и MPEG-4 стандарты нового поколения / Ян. Ричардсон. - М.: Техносфера РИЦ, 2005. — 368 с.

71. Романов, В. Ю. Популярные форматы файлов для хранения графических изображений на IBM PC / В.Ю. Романов. М.: Радио и связь, 1992.-140 с.

72. Садыхов, Р.Х. Методы и средства обработки сигналов в дискретных базисах / Р.Х. Садыхов, П.М. Чеголин, В.П. Шмерко. Минск: Наукаи техника, 1987. 296 с.

73. Сайт Waterloo BragZone (тестовые наборы изображений). Режим доступа: http://links.uwaterloo.ca/oldwebsite/bragzone.base.html.

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

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

76. Сергеев, В.В. Метод контроля максимальной ошибки компрессии / В.В. Сергеев, Е.И. Тимбай // Компьютерная оптика. — 2007. № 3, т. 31.-С. 83-85.

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

78. Соболев, Д.В. Быстрые алгоритмы дискретного ортогонального преобразования, реализуемого в системах счисления с иррациональным основанием / Д.В. Соболев // Компьютерная оптика. -1999.-№19.-С. 174-179.

79. Сойфер, В.А. Методы компьютерной обработки изображений / В.А. Сойфер. М.: Физматлит, 2003. - 784 с.

80. Столов, E.JI. Обобщенное преобразование Адамара и его применение для сжатия изображений / E.JI. Столов // Исследования по информатике / ИЛИ АН РТ. 2000. - вып. 2. - С. 77-84.

81. Столов, E.JI. Параллельный алгоритм для отыскания водяных знаков в изображении / E.JI. Столов // Вестник Казанского государственного технического университета. 2006. - № 3. - С. 31-42.

82. Сысоев, А.Ф. Алгоритм и подпрограмма для вычисления дискретного преобразования Уолша / А.Ф. Сысоев, Н.Н. Кирсанова // Численный анализ на Фортране / МГУ. 1974. - вып. 9.

83. Тагиров, P.P. Опыт применения параллельных процессоров для потоковой обработки изображений / P.P. Тагиров // Исследования по информатике / ИЛИ АН РТ. 2003. - вып. 10. - С. 133-140.

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

85. Умняшкин, С.В. Анализ эффективности применения ортогональных преобразований для кодирования дискретных сигналов с коррелированными отсчетами / С.В. Умняшкин // Цифровая обработка сигналов.-№4.-2008.-С. 15-18.

86. Умняшкин, С.В. Быстрый алгоритм вычисления дискретного преобразования Крестенсона-Леви для обработки вещественных массивов / С.В. Умняшкин. М.: МГИЭТ (ТУ), 1995. - 19 с. - Деп. в ВИНИТИ 05.12.95, № 3212-В95.

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

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

89. Умняшкин, С.В. Применение дискретного преобразования Крестенсона-Леви в цифровой обработке изображений: Дис. канд. тех. наук: 05.13.01 / С.В. Умняшкин. Москва, 1997. - 196 с.

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

91. Хорошевский, В. Г. Алгоритмы распределения ветвей параллельных программ по процессорным ядрам вычислительных систем / В.Г. Хорошевский, М.Г. Курносов // Автометрия. 2008. - № 2, т. 44. - С. 56-67.

92. Шеннон, К. Работы по теории информации и кибернетике: пер. с анг. / К. Шеннон; под ред. P.JI. Добрушина и О.Б. Лупанова. М.: Иностранная литература, 1963. - 106 с.

93. Ярославский, Л.П. Введение в цифровую обработку изображений / Л.П. Ярославский. -М.: Сов. Радио, 1979. -312 с.

94. A Fast Precise Implementation of 8x8 Discrete Cosine Transform Using the Streaming SIMD Extensions and Intel® MMX™ Instructions, Intel Application Note. AP-922. 1999. Режим доступа: http://www.cs.cmu.edu/~barbic/cs-740/ap922.pdf.

95. Ahmed, N. Discrete Cosine Transform / N. Ahmed, T. Natarajan, K.R. Rao // IEEE Transactions Computers. 1974. - Vol. C-23. - P. 90-93.

96. Ahmed, N. Walsh functions and Hadamard transform. Applications of Walsh functions / N. Ahmed, K.R. Rao // Proceeding of Walsh functions simposium. Washington, 1972.

97. Antonini, M. Image Coding Using Wavelet Transform / M. Antonini, M. Barlaud, P. Mathieu, I. Daubechies // IEEE Transactions on Image Processing. 1992. - Vol. 1, №2. - P. 205-220.

98. Atzori, L. Error recovery in JPEG2000 image transmission / L. Atzori, S. Corona, D.D. Giusto // IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '01). 2001. - Vol. 3. - P. 17331736.

99. Aubert, G., Kornprobst P. Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations / G. Aubert, P. Kornprobst // Springer Verlag. 2002.

100. Balasubramanian, R. A fast algorithm for coherency identification and dynamic equivalencing of power systems / R. Balasubramanian, S.C.

101. Tripathy, Shivanna // Proceedings of XVI Annual Convention and Exhibition of the IEEE In India. (ACE '90). 1990. - P. 71-75.

102. Beaumont, J.M. Image data compression using fractal techniques / J.M. Beaumont // ВТ Technological Journal. 1991. - Vol. 9, № 4. - P. 92-109.

103. Bogdan, A. Multiscale (Inter/Intra-Frame) Fractal video coding / A. Bogdan // In IEEE International Conference on Image Processing (ICIP '1994). -1994.-P. 1-5.

104. Cho, N. Fast algorithm and implementation of 2-D discrete cosine transform / N. Cho, S. Lee // IEEE Transactions Circuits and Systems. 1991. - Vol. 38.-P. 297-305.

105. Dedera, L. A parallel approach to image decoding in the fractal image block coding scheme / L. Dedera, J. Chmurny // Neural Network World. 1998. -Vol. 8, №4.-P. 365-374.

106. Enomoto, H. Orthogonal transform coding system for television signals / H. Enomoto, K. Shibata // IEEE Transactions Electromagnetic Compatibility. Special issue on Walsh functions. 1971. - Vol. EMC-13, №3. - P,11-17.

107. Fishe, Y.R. Fractal image compression. Theory and Application / Y.R. Fishe. London: Springer-Verlag. - 1995. - P. 341.

108. Gastpar, M. On compression using the distributed Karhunen-Loeve transform / M. Gastpar, P.L. Dragotti, M. Vetterli // IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '04). -2004.-Vol.3.-P. iii-901 -4.

109. Gonzaga, A. Wavelet-based Bayesian analysis of generalized long-memory process / A. Gonzaga, A. Kawanaka // IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '05). 2005. - Vol. 4. -P. iv/309- iv/312.

110. Gray, R.M. Vector Quantization / R.M. Gray // IEEE ASSP Magazine. -1984.-P. 4-29.

111. Habibi, A. Image coding by linear transformation and block quantization / A. Habibi, P.A. Wintz // IEEE Transactions Communications Technology.1971.-Vol. COM-19, № 1. P.50-63.

112. Huffman, D.A. A method for the construction of minimum-redundancy codes / D.A. Huffinan II Proceedings of the I.R.E. -1952. Vol. 40, № 9. -P.1098-1102.

113. Jacquin, A. Fractal image coding based on a theory of iterated contractive image transformations / A. Jacquin // Visual Communications and Image Processing. 1990. - Vol. SPIE-1360.

114. Jaquin, A.E. Image coding based on a fractal theory of iterated contractive image transformations / A.E. Jaquin // IEEE Transanctions Image Processing. 1992.-Vol. 1, № 1.-P. 18-30.

115. Karagodin, M.A. Image compression by means of Walsh transform / M.A. Karagodin, A.N. Osokin // The 8th International Scientific and Practical Conference of Students, Post-graduetes and Young Scientist. Tomsk University, 2002. - P. 173-175.

116. Kuklinski, W.S. Fast Walsh transform data-compression algorithm: E.c.g. applications / W.S. Kuklinski //Medical and Biological Engineering and Computing. 1983. - Vol. 21, № 4. - P. 465-472.

117. Li, N. Three-level parallel high speed architecture for EBCOT in JPEG2000 / N. Li, M. Bayoumi // IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '05). 2005. - Vol. 5. - P. v/5-v/8.

118. Linde, Y. An Algorithm for Vector Quantization Designs / Y. Linde, A. Buzo, R. Gray // IEEE Transactions On Communications. — 1980. Vol.28.-P. 84-94

119. Nasrabadi N.M. Image coding using vector quantization: A review / N.M. Nasrabadi, R.A. King // IEEE Transactions on Communication. 1988. -Vol. 36, №8.-P. 957-971.

120. Oraintara, S. Integer fast Fourier transform / S. Oraintara, Y.J. Chen, T.Q. Nguyen // IEEE Transactions on Signal Processing. — 2002. Vol. 50, № 3. -P. 607-618.

121. Pennebaker, W.B. An overview of the basic principles of the Q-coder adaptive binary arithmetic coder. IBM / W.B. Pennebaker, J.L. Mitchell, G.G. Langdon, R.B. Arps // Journal of research and development. 1988. -Vol. 32, №6.-P. 771-726.

122. Pennebaker, W.B. JPEG Still Image Data Compression Standard / W.B. Pennebaker, J.L. Mitchell. New York: Van Nostrand Reinhold, 1993. -638 p.

123. Pratt, W.K. Application of Fourier-Hadamard transformation to bandwidth compression / W.K. Pratt, H.C. Andrews // Picture bandwidth compression / Ed.: Huang T.S., Tretiak O.J.-New York, 1972.-P. 515-554.

124. Pratt, W.K. Slant transform image coding / Pratt W.K., Chen W.H., Welch L.R. // IEEE Transactions Communications. 1974. - Vol. C-22. - P. 1075-1093.

125. Pyramidal lattice vectior quantization for multiscale image coding / M. Barlaud et al. // IEEE Transanctions Image Processing. 1994. - Vol. 3, № 4.-P. 367-381.

126. Rao, K.R. Image data processing by Hadamard-Haar transform / K.R. Rao, M.A Narasimhan, K. Revuluri // IEEE Transactions Computers. — 1975. -Vol. C-23, № 9. P. 888-896.

127. Rout, S. Color image compression: multiwavelets vs. scalar wavelets / S. Rout, A.E. Bell // IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '02). 2002. - Vol. 4. - P. IV-3501-V-3504.

128. Smith, B. Algorithm for manipulating compressed images / B. Smith, L. Rowe // Computer Graphics and applications. -1993.

129. Saupe, D. The Futility of Square Isometrics In Fractal Image Compression / D. Saupe // IEEE International Conference of Image Processing. 1996. — Vol. 1, № 3. - P. 60-67.

130. Senoo, T. Vector quantization for entropy coding of image subbands / T. Senoo, B. Giord // IEEE Transanctions Image Processing. 1992. - Vol. 1, №4.-P. 526-532.

131. Sobelman, G.E. Computer algebra and fast algorithms / G.E. Sobelman // IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP-92). 1992. - Vol. 4. - P. 89-92.

132. Storer, J.A. Data compression: Methods and theory / J.A. Storer. -Rockville (Md): Computer science press, 1988. 413 p.

133. Vetterli, M. Wavelets and Subband Coding / M. Vetterli, J. Kovacevic .New Jersey: Prentice ITall, 1995. 327 p.

134. Vonesch, C. Generalized Biorthogonal Daubechies Wavelets / C. Vonesch, T. Blu, M. Unser // SPIE Optics and Photonics 2005 Conference on Mathematical Methods: Wavelet XI. San Diego, 2005. - Vol. 5914. - P. 59141X-1/59141X-6.

135. Wallace, G.K. Overview of the JPEG (ISO/CCITT) still image compression: image processing algorithms and techniques / G.K. Wallace, H. Enomoto, K. Shibata // Proceedings of the SPIE. 1990. - V.1244. - P. 220-233.

136. Wallace, G.K. The JPEG algorithm for image compression standard / G.K. Wallace // Communications of the ACM. 1991. - Vol. 34, № 4. - P. 3044.

137. Witten, I.H. Arithmetic coding for data compression / I.H. Witten, R.M.

138. Neal, J.G. Cleary // CommunicaticWof the ACM. 1987. - Vol. 30, № 6. -P. 520-540.

139. Wong, W. C. Partial Correction of Transmission Errors in Walsh Transform Image without recourse to Error Correction Coding / W. C. Wong, R. Steele // Electronic Letters. 1978. - Vol. 14, № 10. - P. 298-300.

140. Xu, C. Bit-plane and pass dual parallel architecture for coefficient bit modeling in JPEG2000 / C. Xu, Y. Han, Y. Zhang // Asia and South Pacific Design Automation Conference. SESSION: Poster session IV. Shanghai, 2005.-P. 1284-1287.

141. Yuen, C. Walsh Functions and Gray Code / C. Yuen // IEEE Transactions on Electromagnetic Compatibility. 1971. - Vol. EMC-13, №3. - 68-73.

142. Zeng, Y. Integer DCTs and fast algorithms / Y. Zeng, L. Cheng, G. Bi, A.C. Kot // IEEE Transactions on Signal Process. 2001. - Vol. 49, №. 11. - P. 2774-2782.