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

48441П

ЛАПТЕВА ВАЛЕНТИНА ВЛАДИМИРОВНА

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

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва, 2011

9 1 '.П-1 '-11" ¿и 11

4844171

Диссертационная работа выполнена на кафедр; Высшей математики №1 Московского государственного института электронной техники (технического университета).

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

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

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

Умняшкин Сергей Владимирович

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

Терещенко Сергей Андреевич

кандидат физико-математических наук Посыпкин Михаил Анатольевич

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

Научно-производственное предприятие «ОПТЭКС»

Защита состоится «X6» йщКЖА 2011 года в^ часов^минут на заседании диссертационного совета Д 212.134.02 при Московском государственном институте электронной техники (техническом университете) по адресу: 124498, Москва, Зеленоград, проезд 4806, д. 5. МИЭТ.

С диссертацией можно ознакомиться в библиотеке МИЭТ.

Автореферат разослан « » \JAJj 2011 г.

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

/

ЯШ*

7

Гуреев А. В.

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

Актуальность проблемы

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

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

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

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

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

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

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

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

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

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

• статистическое кодирование проквантованных значений для снижения кодовой избыточности.

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

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

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

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

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

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

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

1 Умняшкин C.B. О модификации дискретного косинусного преобразования // Изв. Тул. гос. ун-та. Сер. Математика. Механика. Информатика. Тула: ТулГУ, 1998. Т. 4. Вып. 1. С. 143-147.

Цель диссертационной работы

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

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

1. Впервые к сжатию цифровых изображений было применено ДПКП.

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

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

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

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

Основные задачи

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

2) Определение статистических свойств спектров ДПКП изображений.

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

4) Разработка алгоритмов сжатия и их программной реализации.

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

Методы исследования и достоверность результатов

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

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

Личный вклад автора

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

Научные положения, выносимые на защиту

1. Предложенный метод сжатия цифровых изображений на основе ДПКП позволяет выполнять сжатие цифровых изображений с вычислительными затратами, меньшими в среднем на 30%, чем вычислительные затраты метода JPEG.

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

3. Разработанный алгоритм оптимизации параметров предложенного метода сжатия на основе ДПКП повышает качество восстановленного изображения в среднем на 0,2 дБ при одинаковых битовых затратах.

Внедрение

Программная реализация предлагаемого метода сжатия изображений на основе ДПКП внедрена в качестве компонента штатной системы фотоконтроля огневых испытаний в ОАО «НПО Энергомаш имени академика В. П. Глушко», о чем был составлен акт внедрения.

Апробация работы

Результаты работы докладывались на международной научно-технической конференции «Цифровая обработка сигналов и ее применение» (Москва, ИПУ РАН, 2009 г.), международной конференции-по механике и современным прикладным программным системам (Украина, Алушта, МАЙ, 2007 г.), трех всероссийских межвузовских научно-технических конференциях студентов и аспирантов «Микроэлектроника и информатика» (Москва, МЙЭТ, 2005,

2006 и 2010 г.), научно-практическом семинаре молодых ученых и специалистов предприятий космической отрасли «Основные направления и формы использования инновационных разработок при создании ракетно-космической техники» (Королев, ИПК Машприбор,

2007 г.).

Публикации

По теме диссертационной работы опубликовано 10 научных работ, из них 4 работы - в изданиях из списка ВАК («Цифровая обработка сигналов», «Известия вузов. Электроника», «Труды ОАО НПО Энергомаш имени академика В. П. Глушко»). Без соавторов опубликовано 6 работ.

Структура и объем диссертации

Диссертационная работа состоит из введения, 4 глав, заключения, списка литературы и 9 приложений. Работа изложена на 154 страницах, включая 14 страниц приложений, и содержит 25 рисунков, 26 таблиц. Список литературы включает 97 источников.

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

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

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

В качестве меры расхождения исходного изображения |ху| и восстановленного изображения |х,у| используется величина средне-

квадратичной ошибки (СКО) и отношения пикового значения сигнала к шуму (PSNR, peak signal-to-noise ratio): , Л/-1ЛМ 2

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

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

{-(T + L)q; ...; ~(T + \)q; -Tq; Tq; (741)?;-...; (74¿-I)?}, (1) где значение параметра 7* >0,5 (значение 7 = 0,5 соответствует равномерному квантованию), q - шаг квантования. Уровни квантования располагаются в серединах интервалов между порогами. Такой метод квантования позволяет увеличить количество нулевых элементов в потоке данных, в результате меньшее количество элементов будет подвергнуто дальнейшему статистическому кодированию, что ведет к снижению вычислительной сложности алгоритма.

При реализации статистического кодирования во многих методах сжатия используется многомодельное кодирование с контекстным прогнозированием моделей. Для этого задается несколько моделей кодированиями для текущего кодируемого символа нужная модель выбирается в соответствии с некоторым рассчитанным значением прогноза. В качестве прогноза можно использовать величину регрессии кодируемого символа V на символы контекста Yi,Y2,...,Y/], обеспечивающую наименьшее среднеквадратичное отклонение от Y:

r1(Y) = M(Y\YuY2,...,Yn) = al + fjakYk, (2)

ы

[7 Л2"

а = (<ar0,I ,...,ar„) = argmmA/

V / ае А

а вА

где А - множество допустимых значения вектора параметров

К. k=1 )

a = (ar0,or,

Алгоритмы сжатия и восстановления изображений характеризуется рядом параметров, которые могут быть найдены как решение задачи RD-оптимизации. Пусть и - вектор параметров метода сжатия/восстановления F, переводящего вектор исходных данных х в вектор восстановленных данных y = f(x,u). Необходимо-найти такие

значения параметров u* = которые для данного вектора х

и битовых затратах /?(и), не превосходящих заданной величины Rb, обеспечивали бы минимум меры D(u) расхождения исходного и восстановленного вектора данных:

£>(u*) = min£>(u),

4 ' ueU

Я(и)<Л6,

где U - множество допустимых значений вектора параметров и.

Значение и*, обеспечивающее при некотором неотрицательном значении Л минимум функции Лагранжа

j(u*) = min{j(u)=D(u) + A/?(u)} (3)

будет являться решением поставленной задачи при Rb = /?(и*). В этом случае параметр Л позволяет задавать соотношение качества и степени сжатия изображения: при Я -» +0 задача сводится к поиску параметров алгоритма, обеспечивающих меньшую ошибку восстановления по мере D, а при Л->со- меньшие битовые затраты.

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

Восьмиточечное ДПКП определяется матрицей W = DC, где

D_dia fj__!__|__I__1__L_ J__L"

iag U>/2 ' 2V5 ' 2V2 ' ' 1-h' 2л/5 ' 2V2 ' 2S J'

1 1 1 1 0 0 0 0' 1 0 0 0 1 0 0 0"

2 1 -1 -2 0 0 0 0 0 1 0 0 0 1 0 0

1 -1 -1 1 0 0 0 0 0 0 1 0 0 0 1 0

1 -2 2 -1 0 0 0 0 0 0 0 1 0 0 0 1

0 0 0 0 1 1 1 1 1 0 0 0 -I 0 0 0

0 0 0 0 2 1 -1 -2 0 1 0 0 0 -1 0 0

0 0 0 0 I -1 -I I 0 0 1 0 0 0 -1 0

0 0 0 0 I -2 2 -1 _ 0 0 0 1 0 0 0 -1_

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

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

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

бектора, результата преобразования, К - ковариационная матрица исходного вектора. Минимальное значение, равное нулю, величина средней избыточной энтропии принимает для преобразования Карунена-Лоэва, для остальных преобразований А И > 0 .

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

где N - размерность преобразования, сг| - дисперсии компонент

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

f i' N~] „ / (N-1 ^ 1/лЛ

G = 101g w! ГК

u=0 J /

Минимальное значение коэффициента эффективности кодирования

достигается при Oq = of =... = , то есть в случае равномерного

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

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

величине S = сг^ . Таким образом, несмотря на различия в подходах

к=о

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

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

Третья глава посвящена разработке этапов скалярного квантования, арифметического кодирования и RD-оптимизации для

метода сжатия на базе ДПКП. Обработка изображения производится по блокам размера 8 х 8 отсчетов.

В качестве метода скалярного квантования коэффициентов ДПКП было предложено использовать квантование с нулевой зоной с порогами, указанными в соотношении (1). При сжатии тестовых изображений с различными значениями параметра Т, было установлено, что наибольшая эффективность метода достигается при значении параметра Т-0,6. Отметим, что указанное значение , оказалось универсальным для всех исследованных изображений.

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

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

Отметим, что постоянные составляющие блоков (коэффициенты с индексом (0,0)) в среднем имеют значения, значительно превосходящие значения остальных коэффициентов блоков. Для их кодирования предлагается использовать двумерную дифференциальную импульсно-кодовую модуляцию (ДИКМ), результат которой кодировать с помощью отдельной статистической модели.

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

Модули переменных составляющих будут кодироваться с

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

0 2 5 0 0 2 6

1 5 5 7 6 6 6 7

2 5 5 7 6 6 6 7

5 7 7 7 6 7 7 7

1 3 3 3 2 2 4 4

1 3 3 7 2 4 4 7

2 3 3 7 4 4 4 7

Л О 7 7 7 4 7 7 7

Рисунок 1. Расположение областей в блоке коэффициентов ДПКП

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

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

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

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

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

проквантованного коэффициента ДПКП номер модели определяется на основании соотношения величины прогноза с пороговым значением по следующему правилу:

•2г, Ргоё(№/,)|)<^

(5)

2г + 1, Рго6(|$3|)>/г.

Здесь г - номер области, в которой содержится коэффициент (/,у — координаты блока, / - индекс коэффициента в блоке), /г - порог выбора модели, соответствующий области с номером г.

В качестве прогноза Р^^у-']1 используется линейная регрессия

(2) модуля кодируемого коэффициента на модули коэффициента контекста, включающего наиболее коррелированные коэффициенты спектра ДПКП (рис. 2).

Mode]

М-

Л(/)

//,7-1

(ДО .

-^/-1,7

ш

ян

л(/)

^,-1,7+1

О] Кодируемый коэффициент

£ Коэффициент контекста

Кодируемый блок (/', у)

Рисунок 2. Структура контекста для прогнозирования моделей кодирования переменных составляющих спектра ДПКП

Коэффициент а0 из формулы (2) для удобства расчетов можно опустить, что приведет лишь к сдвигу порогов на эту величину в правиле (5). На основании обработки нескольких тестовых изображений были получены следующие оценки остальных коэффициентов регрессии: a¡ » 0,37, а2 « 0,22, аъ « 0,04, ог4 « 0,18 . Для упрощения вычисления прогноза и с учетом того, что оцененная корреляция модуля кодируемого коэффициента с модулями коэффициентов из блоков сверху и слева от текущего блока больше, чем с модулями коэффициентов из «диагональных» блоков, положим щ = а2 = 1/3, а3=а4 = 1/6. В результате функция-прогноз примет вид:

Рг°8 (И51) = И-U |+ 2ИЗ-11+ И'Ь-i |+И'Ь+i |) •

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

В качестве порогов для выбора моделей кодирования в правиле (5) при заданном значении шага квантования q можно использовать пороги, найденные как решение задачи минимизации битовых затрат на сжатое представление изображения. Такая постановка задачи оправдана в том смысле, что в результате изменения порогов будет меняться количество бит, необходимых для кодирования спектра ДПКП изображения, а мера расхождения исходного и восстановленного изображений не изменится. По результатам обработки тестовых изображений для различных значений шага квантования q были найдены оптимальные пороги {í,.} и

установлено, что их значения достаточно хорошо можно описать следующей формулой:

tr ~ crjq, г = 0,1,...,7,

где {с,.} - постоянные масштабные коэффициенты, определенные на

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

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

исходного изображения.

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

блоков к = Дш-Ки-))» определяющий то, какие

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

Сформулируем задачу [Ш-оптимизацки для метода на базе ДПКП. Необходимо найти такой вектор ключей блоков * * \

^О.О'^-ОЬ—>кт-\,п-\ I и такую величину шага квантования

которые бы обеспечивали минимум функции J(k,q), задаваемой формулой (4):

У(к*,^*) = гпт(У(к,9) = 0(к,(7) + Я/г(к,?)). (6)

Здесь /? - битовые затраты на сжатое представление изображения, В -среднеквадратичная ошибка восстановления, равная, в силу ортогональности ДПКП, среднеквадратичной ошибке квантования.

Для сокращения объема вычислений решение задачи (б) будем искать, проводя последовательную минимизацию:

7(к*,д*) = тттт(./(к,д) = Л(к,<7) + /1/г(к,<7)). (7)

д к

При исследовании решений задачи (7) было установлено, что связь между значением оптимального шага квантования ц* и параметра Л может быть приближенно описана соотношением:

<7*«Сл/А,

где С - некоторая общая для различных изображений константа. По методу наименьших квадратов было найдено значение константы С »3,21. Приближенная связь между оптимальным значением шага квантования д* и параметром Л позволяет сократить интервал поиска

оптимального значения шага квантования.

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

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

Рассмотрим вариант сокращенного перебора ключей, при котором поиск происходит по ключам, полученным из базового путем последовательного обнуления единичных бит, начиная со старших разрядов. Так, если число ненулевых битов в ключе блока равно t, то вместо 2' возможного количества вариантов обнуления областей (то есть различных ключей) достаточно рассмотреть / вариантов. Таким образом, по всем блокам накапливается значительно сокращение количества рассматриваемых вариантов ключей, при этом, как показали исследования, эффективность сжатия практически не изменяется (в среднем, снижается на 0,05 дБ).

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

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

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

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

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

Таблица 1. Отличия модификаций метода сжатия на базе ДПКП

Модификация Квантование с нулевой зоной Контекстное прогнозирование RD- оптимизация

1.0 - - -

1.1 + - -

1.2 - + -

1.3 + ' + -

2.0 + + +

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

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

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

60 50 40 30 20 10

0 10 20 30 40 50 60 70 80 90 100 110 120

Рисунок 3. Оценка зависимости среднего количества коэффициентов в блоке, подвергающихся арифметическому кодированию, от шага квантования. 1 - метод на базе ДПКП с равномерным квантованием, 2 - метод на базе ДПКП с квантованием с нулевой зоной, 3 - JPEG

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

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

Результирующие графики оценок вычислительной сложности методов для одного блока, учитывающие сложность выполнения преобразования и сложность арифметического кодирования, приведены на рис. 4 и 5. Оценка рассчитывалась для процессора Intel Pentium 4 со значениями rç = 8, г2 = 23 .

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

2 - метод на базе ДПКП с равномерным квантованием,

3 - метод на базе ДПКП с квантованием с нулевой зоной

Рисунок 5. Количество эквивалентных сложению операций в зависимости от шага квантования для алгоритмов восстановления, 1 - JPEG, 2 - метод на базе ДПКП с равномерным квантованием, 3 - метод на базе ДПКП с квантованием с нулевой зоной

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

Вычислительная сложность этапа RD-оптимизации зависит от обрабатываемого изображения и величины параметра Л. Для метода без RD-оптимизации (модификации 1.3) время как сжатия, так и восстановления составляет в среднем около 0,3 с. Для тестового изображения Lena было установлено, что время обработки для модификации 2.0 с RD-оптимизацией, использующей сокращенный перебор ключей, в среднем в 8,5 раз превосходит время обработки для модификации 1.3. Вычисления выполнялись на компьютере с процессором Intel Pentium 4.

Предложенный метод на базе ДПКП, включающий RD-оптимизацию, сравнивался с методом JPEG, использующим арифметическое кодирование, по эффективности сжатия тестовых изображений. На рис. 6 и 7 представлены графики зависимости качества изображения, оцениваемого по величине отношения пикового сигнала к шуму от степени сжатия, выраженной в битах на пиксель изображения. Наилучшие результаты сжатия разработанный метод показывает при обработке мелкодетальных, «высокочастотных» изображений, таких как «Barbara», а также при сжатии с битовыми затратами, большими в среднем 0,5 бит на пиксель изображения.

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

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

Рисунок 6. Зависимости величины PSNR в дБ от битовых затрат в Ьрр для изображения «Barbara», 1 - модификация 2.0 разработанного метода на основе ДПКП, 2 - метод JPEG

Рисунок 7. Зависимости величины PSNR в дБ от битовых затрат в Ьрр для изображения «Goidhill» , 1 - модификация 2.0 разработанного метода на основе ДПКП, 2 - метод JPEG

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

5) Разработано программное обеспечение, реализующее предложенный метод.

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

7) Предложенный метод сжатия на основе ДПКП внедрен в качестве компонента системы хранения информации по огневым испытаниям в ОАО «НПО Энергомаш имени академика В. П. Глушко».

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

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

1. Ковалев В. И., Курина В. В. Методы обработки телеметрической информации на основе ортогональных преобразований // Труды ОАО НПО Энергомаш имени академика В. П. Глушко. - № 27. - Москва : НПО Энергомаш, 2010. - С. 254-280.

2. Курина В. В. Метод сжатия изображений на основе дискретного псевдокосинусного преобразования // Микроэлектроника и информатика - 2010. 17-я Всеросс. межвуз. науч.-тех. конф-я студ. и аспир.: Тезисы докладов. - Москва: МИЭТ, 2010. - С. 147.

3. Курина В. В. Оценка эффективности применения дискретного псевдокосинусного преобразования для сжатия изображений // Известия вузов. Электроника.-2010.-№2.-С. 78-80.

4. Курина В. В. Параметры статистического кодирования в задаче вейвлет-компрессии изображений // Микроэлектроника и информатика - 2006. 13-я Всеросс. межвуз. науч.-тех. конф-я студ. и аспир. : Тезисы докладов. - Москва: МИЭТ, 2006. - С. 162.

5. Курина В. В. Разработка и внедрение метода сжатия цифровых фотоизображений применительно к созданию базы данных по испытаниям мощных ЖРД // Основные направления и формы использования инновационных разработок при создании ракетно-космической техники : Науч.-практ. сем. молодых уч. и специалистов предпр. косм, отрасли : Сборник материалов. - г. Королев ; ИПК Машприбор, 2007. - С. 67.

6. Курина В. В. Разработка метода вейвлет-сжатия цифровых изображений с контекстным статистическим кодированием применительно к созданию базы данных по испытаниям ЖРД // Материалы XV Междунар. конф. по механике и соврем, прикладным прогр. системам (ВМСППС'2007). - Москва : Вузовская книга, 2007. -С. 326.

7. Курина В. В. Учет корреляции знака при вейвлет-кодировании изображений // Микроэлектроника и информатика-2005. 12-я Всеросс. межвуз. науч.-тех. конф-я студ. и аспир. : Тезисы докладов. - Москва : МИЭТ, 2005. - С. 179.

8. Курина В. В., Кучев А. С. Разработка методики сжатия изображений для базы данных по испытаниям // Труды ОАО НПО Энергомаш имени академика В. П. Глушко. - № 24. - Москва : НПО Энергомаш, 2006. -С. 279-291.

9. Курина В. В., Умняшкин С. В. Алгоритм сжатия изображений на основе дискретного псевдокосинусного преобразования // Труды Российского научно-технического общества радиотехники, электроники и связи имени А. С. Попова. Серия : Цифровая обработка сигналов и ее применение. - Выпуск Х1-2. - Москва : ООО «Инсвязьиздат», 2009. -С. 433-435.

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

Подписано в печать

Заказ № . Уч.-изд. л. . Тираж ЮО экз. Формат 60x84 1/16.

Отпечатано в типографии МИЭТ.

124498, Москва, Зеленоград, проезд 4806, д. 5, МИЭТ.

Введение

Глава 1. Обзор методов сжатия изображений и постановка задачи диссертационного исследования.

1.1. Математическая модель изображения.

1.2. Основные положения методов сжатия изображений.

1.2.1. Методы сжатия аналоговых сигналов.

1.2.1.1. Импульсно-кодовая модуляция.

1.2.1.2. Дифференциальная импульсно-кодовая модуляция.

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

1.2.3. Ортогональные преобразования.

1.2.4. Квантование.

1.2.5. Статистическое кодирование.

1.2.5.1. Описание процесса кодирования.

1.2.5.2. Прогнозирование модели кодирования на основе контекста.

1.2.5.3. Обзор алгоритмов статистического кодирования.

1.2.6. Задача RD-оптимизации.

1.3. Метод JPEG.

1.4. Метод JPEG 2000.

1.5. Постановка задачи диссертационного исследования

Глава 2. Выбор ортогонального преобразования для сжатия изображений

2.1. Дискретное косинусное преобразование и его модификации.

2.1.1. Определение и свойства.

2.1.2. Обзор быстрых алгоритмов ДКП.

2.1.3. Обзор преобразований, основанных на ДКП.

2.2. Обзор дискретных преобразований, применяемых в ЦОИ.

2.2.1. Дискретное преобразование Карунена-Лоэва.

2.2.2. Дискретное преобразование Хаара.

2.2.3. Дискретное преобразование Уолша-Адамара.

2.2.4. Наклонное преобразование.

2.3. Дискретное псевдокосинусное преобразование.

2.4. Сравнение дискретных преобразований по декоррелирующей эффективности.

2.4.1. Средняя избыточная энтропия.

2.4.2. Критерий остаточной корреляции.

2.4.3. Коэффициент эффективности кодирования.

2.4.4. Численные результаты сравнения дискретных преобразований по декоррелирующей эффективности.

Выводы и заключение

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

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

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

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

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

5) Разработано программное обеспечение, реализующее предложенный метод.

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

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

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

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

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

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

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

Еще одним перспективным направлением развития метода является внедрение квантования с различными дискретами, соответствующими разным обобщенным частотам спектра ДПКП.

Программное обеспечение, реализующее разработанный метод сжатия на базе ДПКП в модификации 2.0, было использовано в ОАО «НПО Энергомаш» для организации хранения изображений жидкостных ракетных двигателей и его узлов, которые выполняют при штатном фотоконтроле до и после проведения огневых испытаний [17, 19]. Акт внедрения результатов диссертационной работы приведен в Приложении 9.

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

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

3. Грузман И. С., Киричук В. С., Косых В. 77. и др. Цифровая обработка изображений в информационных системах. Новосибирск : Изд-во НГТУ, 2002. - 352 с.

4. Дмитриев В. И. Прикладная теория информации : Учеб. для студ. вузов. М. : Высш. шк, 1989. - 320 с.

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

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

7. Захаров М. В. Об одной реализации арифметического кода Электронный ресурс. URL: http://www.maxime.net.ru/doc/mfarc.ps.gz.

8. Калиткин Н. Н. Численные методы. М. : Наука, 1978 - 512 с.

9. Ковалев В. И., Курина В. В. Методы обработки телеметрической информации на основе ортогональных преобразований // Труды ОАО НПО Энергомаш имени академика В. П. Глушко. № 27. - Москва : НПО Энергомаш, 2010. -С.254—280.

10. Кочетков М. Е., Умняшкин С. В. О сравнении критериев для оценки эффективности декоррелирующих преобразований. М. : МГИЭТ (ТУ), 1998. -34 с. - Депонировано в ВИНИТИ 13.04.98 № 1069-В98.

11. Курина В. В. Метод сжатия изображений на основе дискретного псевдокосинусного преобразования // Микроэлектроника и информатика -2010. 17-я Всеросс. межвуз. науч.-тех. конф-я студ. и аспир. : Тезисы докладов. -Москва : МИЭТ, 2010. С. 147.

12. Курина В. В. Оценка эффективности применения дискретного псевдокосинусного преобразования для сжатия изображений // Известия вузов. Электроника. -2010. -№ 2. С. 78-80.

13. Курина В. В. Параметры статистического кодирования в задаче вейвлет-компрессии изображений // Микроэлектроника и информатика 2006. 13-я Всеросс. межвуз. науч.-тех. конф-я студ. и аспир. : Тезисы докладов. - Москва : МИЭТ, 2006.-С. 162.

14. Курина В. В. Учет корреляции знака при вейвлет-кодировании изображений // Микроэлектроника и информатика 2005. 12-я Всеросс. межвуз. науч.-тех. конф-я студ. и аспир. : Тезисы докладов. - Москва : МИЭТ, 2005. — С. 179.

15. Курина В. В., Кучев А. С. Разработка методики сжатия изображений для базы данных по испытаниям // Труды ОАО НПО Энергомаш имени академика В. П. Глушко. № 24. - Москва : НПО Энергомаш, 2006. - С. 279-291.

16. Прэтт У. Цифровая обработка изображений : Пер. с англ. М. : Мир, 1982. -Кн. 1-312 с.

17. Розанов Ю. А. Случайные процессы. -М.: Наука, 1971. -288 с.

18. Семенюк В. В. Обзор стандарта JPEG 2000 Электронный ресурс. СПб, 2002. -URL: http://compression.ru/download/articles/jpeg/semenjuk2001jpeg2000.pdf.

19. Семенюк В. В. Экономное кодирование дискретной информации Электронный ресурс. СПб. : СПбГИТМО (ТУ). - 2001. - URL:compression.ru/download/articles/revuniv/semenyuk2001economencoding.pdf

20. Стрелков Ф. В., Умняшкин С. В. Контекстное кодирование коэффициентов дискретного косинусного преобразования (ДКП) в JPEG-подобной схеме компрессии // Цифровая обработка сигналов. 2003. - № 2. - С. 5-10.

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

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

23. Умняшкин С. В. Математические основы цифровой обработки и кодирования сигналов : Учебное пособие. -М. : МИЭТ, 2004. 176 с.

24. Умняшкин С. В. О модификации дискретного косинусного преобразования // Изв. Тул. гос. ун-та. Сер. Математика. Механика. Информатика. Тула : ТулГУ, 1998.-Т. 4.-Вып. 1.-С. 143-147.

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

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

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

28. Хэмминг Р. В. Теория кодирования и теория информации : Пер. с англ. — М. : Радио и связь, 1983. 176 с.

29. Чуй. Ч. Введение в вейвлеты. Москва : Мир, 2001. - 412 с.

30. Adams М. D. The JasPer Project home page Электронный ресурс. 1999 . -URL: http://www.ece.uvic.ca/~mdadams/jasper/.

31. Advanced video coding for generic audiovisual services // ITU-T Recommendation H.264. 2007 (ISO/1EC 14496-10. Information Technology. Coding of AudioVisual Objects. Part 10: Advanced Video Coding).

32. Andrews H. C., Hunt B. R. Digital image restoration. Englewood Cliffs (NJ) : Prentice Hall, 1977. - 238 p.

33. Arai Y., Agui Т., Nakajima M. A fast dct-sq scheme for images // Trans. IEICE. -Nov. 1988.-Vol. E-71. No. 11.-P. 1095.

34. Berger T. Rate distortion theory: a mathematical basis for data compression. Englewood Cliffs NJ : Prentice-Hall, 1971. 311 p.

35. Center for Image Processing Research Электронный ресурс. -URL: http://www.cipr^i.edu/resource/stills/miscl .html.

36. Chan S. С., Ho K. L. A new two-dimensional fast cosine transform algorithm // IEEE Trans, on Signal Processing. Feb. 1991. - Vol. 39. - No. 2. - P. 481-485.

37. Chen W.-H., Smith C., Fralick S. A fast computational algorithm for the discrete cosine transform I I IEEE Trans. Com. Sept. 1977. - Vol. 25. - No. 9. - P. 10041011.

38. Costantini R. et al. A low-complexity video coder based on the discrete Walsh Hadamar transform // Proc. European signal processing conference (Tampere, Finland, September 5-8). 2000. - P. 1217-1221.

39. Cutler C. C. Differential quantization of communication signals. Patent 2-605-361. -July 1952.

40. Davis G., Nosratinia A. Wavelet-based image coding: an overview // Applied and computational control, signals and circuits. 1998. - Vol. 1. - No. 1. - P. 205-269.

41. Deever A., Hemami S. S. What's your sign?: Efficient sign coding for embedded wavelet image coding // Proc. IEEE Data Compression Conf. (Snowbird, UT, 28-30 March 2000). 2000. - P. 273-282.

42. Digital compression and coding of continuous-tone still images. Requirements and guidelines // ITU-T Recommendation T.81. September 1992. (ISO/IEC IS 10918-1. JPEG Part 1).

43. Dimitrov V., Wahid K. Multiplierless DCT algorithm for image compression applications // Information theories & applications. Vol. 11. - P. 162-169.

44. Duhamel P., Guillemot C. Polynomial transform computation of the 2-D DCT // IEEE International Conference on Acoustics, Speech, and Signal Processing. Apr. 1990.-Vol. 3.-P. 1515-1518.

45. Eliott D. F., Rao K. R. Fast transforms: algorithms, analyses, applications. London : Academic Press, 1982. 488 p.

46. Fano R. M. Technical N65. The Research Laboratory of Electronics, MIT. - Mar. 17, 1949.

47. Feig E., Winograd S. Fast algorithms for the discrete cosine transform // IEEE Trans, on Signal Processing. Sept. 1992. - Vol. 40. - No. 9. - P. 2174-2193.

48. Feig E., Winograd S. On the multiplicative complexity of discrete cosine transform // IEEE trans, on information theory. July 1992. - Vol. 38. - No. 4. - P. 1387-1391.

49. Fog A. Instruction tables: Lists of instruction latencies, throughputs and microoperation breakdowns for Intel, AMD and VIA CPUs 3jieicrpoHH£>m pecypc.

50. URL: http://www.agner.org/optimize/instructiontables.pdf.

51. Haar A. Zur Theorie der Orthogonal Funktionen-System. Inaugural Disertation // Math. Annalen. 1955. - No. 5. - P. 17-31.

52. Hadamar J. Resolution d'une question realative aux determinants // Bulletin des Sciences Mathématiques. 1893. - Ser. 2 - No. 17. - P. 240-246.

53. Hallapuro A., Karczewicz M. Low complexity transform and quantization Part 1: Basic implementation // ISO/IEC JTC1/SC29/WG11 and ITU-T SG16 Q.6 Document JVT-B038. - January 2001.

54. Howard P. G., Vitter J. S. Design and analysis of fast text compression based on quasi-arithmetic coding // Proc. Data Compression Conference (Snowbird, Utah, March 1993). 1993. - P. 98-107.

55. Huffman D. A. A method for the construction of minimum redundancy codes // Proc. I.R.E.- 1952.-Vol. 4D. No. 9.-P. 1098-1101.

56. Independent JPEG group Электронный ресурс. URL: http://www.ijg.org.

57. Jayant N., Noll P. Digital coding of waveforms: principles and applications to speech and video // Englewood Cliffs NJ : Prentice-Hall, 1984. 688 p.

58. JPEG 2000 Image coding system: core coding system // ITU-T Recommendation T.800. August, 2002 (ISO/IEC IS 15444-1, JPEG 2000 Part 1. - December, 2000).

59. Katto J., Yasudo Y. Performance evaluation of subband coding and optimization its filter coefficients // SPIE Proc. Visual Communication and Image Processing (Boston, MA).-Nov. 1991.-Vol. 1605.-P. 95-106.

60. Lee B. G. A new algorithm to compute discrete cosine transform // IEEE Trans, on Acoustics, Speech and Signal Processing. Dec. 1984. - Vol. 32. - No. 6. - P. 12431245.

61. Lengwehasatit K., Ortega A. DCT computation with minimal average number of operations // Proc. of Visual Communication and Image Processing (VCIP '97, San Jose, CA). Feb. 1997. - Vol. SPIE-3024. - P. 71-82.

62. Liang Jie, Tran T. D. Fast multiplierless approximations of the DCT with the lifting scheme // IEEE Transactions on Signal Processing. 2001. - Volume 49. - No. 12. -P. 3032-3044.

63. Loeffler C., Lightenberg A., Moschytz G. Practical fast Id dct algorithms with 11 multiplications // Proc. IEEE ICASSP. Feb. 1989. - Vol. 2. - P. 988-991.

64. Mallat } S. A theory for multiresolution signal decomposition: the wavelet representation // IEEE Transactions on Pattern Analysis and Machine Intelligence. -July 1989.-Vol. 11. No. 7-P. 674-693.

65. Marcellin M. W., Gormish M. J., Bilgin A., Boliek M. An overview of JPEG-2000 // Proc. of the Conference on Data Compression (Snowbird, Utah, March 2000). -2000.-P. 523-541.

66. Marpe D., Wiegand T. A highly efficient multiplication-free binary arithmetic coder and its application in video coding // Proceedings of IEEE International Conference on Image Processing (ICIP 2003). Sept. 2003. - Volume 2. - P. II - 263-6 vol.3.

67. Martin G. N. N. Range encoding: an algorithm for removing redundancy from digitized message. March 1979 (presented to Video & Data Recording Conference, Southampton, UK, July 24-27 1979).

68. Merhav N. Multiplication-free approximate algorithms for compressed domain linear operations on images // IEEE Transactions on Image Processing. Feb 1999. -Volume 8. - Issue 2. - P. 247-254.

69. MPEG-1. Coding of moving pictures and associated audio for digital storage media at up to about 1,5 Mbit/s // ISO/IEC JTC1/SC29/WG11 N MPEG 96. June 1996.

70. MPEG-2. Generic coding of moving pictures and associated audio information // ISO/IEC JTC1/SC29/WG11 N MPEG 00. October 2000.

71. Pao I-Ming, Sun Ming-Ting. Approximation of calculation for forward discrete cosine transform // IEEE Transactions on Circuits and Systems for Video Technology. June 1998.-Vol. 8.-No. 3.-P. 264-268.

72. Pearl J. On coding and filtering stationary signals by discrete Fourier transforms // IEEE Trans. Inf. Theory. 1973. - Vol. 19. - No. 2. - P. 229-232.

73. Pennebaker W. B., Mitchell J. L. JPEG still image data compression standard. NY : Springer, 1992. 650 p.

74. Pennebaker W. B., Mitchell J. L., Langdon G. G., Arps R. B. An overview of the basic principles of the Q-coder adaptive binary arithmetic coder // IBM Journal of Research and Development. -Nov. 1988. Vol. 32. - No. 6. - P. 717-726.

75. Pratt W. K., Andrews H. C., Kane J. Hadamar transform image coding // Proc. IEEE. -January 1969.-Vol. 57.-No. 1.-P. 58-68.

76. Rabbani M., Joshi R. An overview of the JPEG 2000 still image compression standard // Signal processing: Image communication. January 2002. - Vol. 17. -No. l.-P. 3^18.

77. Rao K. R., Yip P. Discrete cosine transform: algorithms, advantages, applications. -New York : Academic Press, 1990. 512 p.

78. Rieder P., Götze J., Sauer M., Nossek J. A. Orthogonal approximation of the discrete cosine transform // Proc. of European Conference on Circuit Theory and Design (Istanbul, Turkey). 1995. - P. 1003-1006.

79. Rissanen J. J. Generalized Kraft inequality and arithmetic coding // IBM Journal of Research and Development. May 1976. - Vol. 20. - No. 3. - P. 198-203 (first published as IBM Research Report RJ-1591, June 1975).

80. Rissanen J. J., Mohiuddin K. M. A multiplication-free multialphabet arithmetic code // IEEE Transactions on Communications. February 1989. - Vol. 37. - No. 2. -P. 93-98.

81. Said A., Pearlman W. A. A new, fast and efficient image codec based on set partitioning in hierarchical trees // IEEE Transactions on circuits and systems for video technology. June 1996. - Vol. 6. - No. 3. - P. 243-250.

82. Schindler M. Range encoder homepage 3jieKipoHHE.iH pecypc. Oct. 1999. -URL: http://www.compressconsult.com/rangecoder/.

83. Shannon C. E. A mathematical theory of communication // Bell System Technical Journal. Vol. 27. - No. 3. -July 1948. - P. 379-423; No. 4. - October, 1948. - P. 623-656.

84. Shapiro. J. M. Embedded image coding using zerotrees of wavelet coefficients // IEEE Transactions on Signal Processing. Dec. 1993. - Vol. 41. No. 12 - P. 34453462.

85. Strang G., Nguyen T. Wavelets and filter banks. Massachusetts : Wellesley-Cambridge Press, 1997. - 440 p.

86. The USC-SIPI Image Database Электронный ресурс. -URL: http://sipi.usc.edu/database/index.html.

87. Todd S., Langdon G.G., Rissanen J. Parameter reduction and context selection for compression of gray-scale images // IBM Journal of Research and Development. -Mar. 1985.-Vol. 29.-No. 2.-P. 188-193.

88. URL: http://sylvana.net/jpeg-ari/jpeg-ari.zip.

89. Video Coding for Low Bitrate Communication // ITU-T Recommendation H.263. -1996.

90. Wallace G. K. The JPEG still picture compression standard // Communications of the ACM. April 1991. - Volume 34. - Number 4. - P. 30^14.

91. Wang. Z. Fast algorithm for the discrete W transform and for the discrete Fourier transform // IEEE Trans, on Acoustics, Speech and Signal Processing. Aug. 1984. -Vol. 32.-No. 4.-P. 803-816.

92. Wang Z., BovikA. C., Sheikh H. R., Simoncelli E. P. Image quality assessment: from error visibility to structural similarity // IEEE Transactions on Image Processing. -Apr. 2004. Vol. 13. - No. 4. - P. 600-612.

93. Witten I. H., Neal R. M., Cleary J. G. Arithmetic coding for data compression // Communication of the ACM. June 1987. - Volume 30. - Number 6. - P. 520 -540.

94. Xiong Z., Ramchandran K., Orchard M. Wavelet packets image coding using space-frequency quantization // IEEE Trans, on Image Proc. 1998. -Vol. 7. - No. 6. - P. 892-898.