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

Коплович Дмитрий Михайлович

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

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

Автореферат

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

1 2 МАЙ 2011

Москва, 2011

4845139

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

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

доктор физико-математических наук, профессор Умняшкин С. В.

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

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

Ъ

доктор физико-математических наук, профессор Рычагов М. Н.

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

Федеральное государственное унитарное предприятие «Научно-производственное объединение им. С. А. Лавочкина»

Защита состоится «Д4 » ¡¿¿¿Ьк- 2011г. в часов 30 минут на заседании диссертационного совета Д 212.134.02 при Московском государственном институте электронной техники (техническом университете) по адресу: 124498, г. Москва, Зеленоград, проезд 4806, д. 5.

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

Автореферат разослан « -в » ЩДХ 2011 г.

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

Общая характеристика работы Актуальность проблемы

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

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

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

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

Стандарт ISCWEC 10918-1

Стандарт ISO/IEC 15444-1

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

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

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

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

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

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

- исследование существующих подходов к сжатию цифровых изображений в области дискретных декоррелирующих преобразований;

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

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

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

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

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

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

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

Научная новизна диссертации

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

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

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

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

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

- Модифицированный алгоритм компрессии цифровых изображений на основе контекстного кодирования коэффициентов ДВП позволяет сократить битовые затраты на кодирование изображения на 3-11 % по сравнению со стандартным методом JPEG-2000.

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

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

Основные результаты диссертационной работы докладывались и обсуждались на 11-й, 12-й, 13-й и 14-й Всероссийских; межвузовских научно-технических конференциях студентов и аспирантов «Микроэлектроника и информатика» (Москва, МИЭТ, 2004, 2005, 2006 и 2007 гг.), на Всероссийской научно-технической конференции «Информационно-телекоммуникационные технологии» (Сочи, 2004 г.), 8-й и 11-й Международных конференциях «Цифровая обработка сигналов и ее применение» (Москва, 2006 и 2009 гг.) а также на 3-й и 4-й Российско-Баварских конференциях по биомедицинской инженерии (Германия, Эрланген, 2007 г.; Москва, МИЭТ, 2008 г.).

Публикации

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

языке. Без соавторов опубликованы три работы. Получено два свидетельства о государственной регистрации программы для ЭВМ. Структура и объем диссертации

Диссертация изложена на 150 страницах (из них 7— приложения), состоит из пяти глав и трех приложений, содержит 52 рисунка и 22 таблицы. Список литературы насчитывает 132 источника.

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

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

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

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

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

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

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

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

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

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

Поскольку ДКП обычно вычисляется для блоков размера 8x8 пикселов, применение ВК ко всему 64-элементному вектору (развернутому блоку) коэффициентов не является целесообразным. Данную проблему для методов сжатия изображений на основе ДКП можно разрешить с помощью специального алгоритма3, который разделяет вектор коэффициентов У на несколько векторов (кластеров) Основная идея алгоритма заключается в минимизации суммарной априорной неопределенности Н кластеров, характеризующей битовые затраты на кодирование вектора У:

при этом для каждого из кластеров У^ априорная неопределенность не должна превосходить заданного ограничения:

#(у«)<Ятах, к = \,...,м.

3 Умняшкин С. В. О кластеризации коррелированных данных. // Информационные технологии в инновационных проектах. Материалы докладов. — Ижевск, ИжГТУ, 1999, —С. 59-65.

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

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

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

Ниже приведены примеры разбиения АС-коэффициентов ДКП-блока на 3 кластера (ОС-коэффициенты обрабатывается отдельно), полученные для коэффициентов (табл. 1) и их модулей (табл. 2).

Табл. 1. Разбиение ДКП-блока Табл. 2. Разбиение ДКП-блока

на кластеры с использованием на кластеры с использованием

самих коэффициентов модулей коэффициентов

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

Другим серьезным недостатком ВК является отсутствие алгоритма построения универсальной оптимальной кодовой книги. Классические алгоритмы построения векторного квантователя ЫЮ и ЕСУ<3 основаны на задании, некоторой начальной кодовой книги С0 и ее последующем итерационном обновлении с помощью обучающей последовательности векторов а0,..., 'Лм_х для нахождения минимума целевой функции.

0323232 3 13 13 12 12 2 12 12 12 1 12 12 12 12

2 3 2 1 2 1 2 1 13 13 12 12

3 3 3 3 2 1 2 1 33333333

0 3 3 3 3 3 3 3 3-2111111 3 2 111111 3 2 111111 3 2 2 1 1 1 1 1 3 2 2 2 2 1 2 2 3 2222222 32222222

В качестве целевой функции в ЫЮ выступает средняя ошибка векторного' квантования:

где Ь — размер кодовой книги, £>(аи, с'к)= |аи -с^|| — ошибка кван-

II IIЕ

тования обучающего вектора ат с помощью кодового вектора с^, / — номер итерации.

Алгоритм ЕСУ(3 является 1Ф-оптимизированной версией ЬВв и роль целевой функции в нем исполняет ШЭ-критерий

/ = £>'+АД1', (1)

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

Здесь я[ят, с'к}= — 1оц2 Ук — битовые затраты на кодирование индекса к, Ук — частота использования кодового вектора с'к для представления векторов то обучающей последовательности. Параметр я в (1) задает баланс между степенью сжатия и величиной вносимой при квантовании ошибки.

Алгоритмы 1ЛЮ и ЕСУСЗ обладают рядом недостатков, затрудняющих их практическое использование. Во-первых, они сходятся к локальному, а не глобальному минимуму целевой функции; во-вторых, скорость их работы невелика; в-третьих, результирующая кодовая книга

сильно зависит от начальной кодовой книги С0.

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

„/г г- ' N |х+=(*о

Iх -\х0~е> Х1 ~£>—>хп-1~£) где е — шаг разделения. После разделения запускается алгоритм ЫЮ или ЕСУС) с увеличенной начальной кодовой книгой, а по завершении его работы вновь происходит разделение кодовой книги. Процесс повторяется до тех пор, пока кодовая книга не достигнет необходимого размера.

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

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

Новый метод формирования начальной кодовой книги похож на обычное разделение, описанное выше, но имеет два существенных отличия. Во-первых, за одну итерацию разделяются не все векторы, а лишь один из них (перебор идет по очереди), после чего два новых вектора заносятся в текущую кодовую книгу, а старый вектор удаляется из нее. Далее запускается алгоритм ECVQ с текущей кодовой книгой в качестве начальной и в процессе его работы вычисляется суммарное значение RD-функции j' (1). На следующем шаге j'+i сравнивается со значением j' на прошлой итерации. Если j'+l > j', то кодовая книга возвращается к своему предыдущему состоянию и алгоритм переходит на следующую итерацию. Таким образом, добавление новых векторов в кодовую книгу происходит только в том случае, если оно обеспечивает уменьшение суммарного значения RD-функции.

Во-вторых, при разделении вектора шаг производится в случайном направлении, т. е.:

г jx+ =x + ô = (x0 +<V->*«-i +¿»-1) ■ |х = х-8 = (х0 -(50,хп_х -o„_i) где ô = £-s/|s||, s —вектор, компоненты которого sk имеют нормальное распределение sk ~ N{mk, ак ). Для упрощения можно использовать одинаковые параметры для каждой компоненты: тй = ml -... = тп_{ и а0 =а1 = ... = сгп_х. Таким образом, в отличие от стандартного алгоритма разделения, данный алгоритм не выделяет какое-то фиксированное направление для расщепления вектора, что повышает вероятность приближения построенной кодовой книги к оптимальной.

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

Первый этап (подготовительный): • Шаг 1. Выполняется блочное ДКП «обучающего» изображения.

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

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

Шаг 4. Для каждого множества векторов с помощью модифицированного алгоритма LBG, описанного выше, строится «универсальная» кодовая книга, которая используется как начальная кодовая книга для алгоритма адаптивного векторного квантования на втором этапе.

Конец первого этапа.

Второй этап (сэ/сатие изобраэюения):

Шаги 1-3. Выполняются аналогично первому этапу, но не над обучающим, а над сжимаемым изображением.

Шаг 4. Каждое множество векторов подвергается адаптивному векторному квантованию с помощью алгоритма GTR4: решение о векторном квантовании или скалярном квантовании с занесением кодируемого вектора в кодовую книгу принимается на основе RD-критерия. Начальной кодовой книгой для алгоритма GTR служит «универсальная» кодовая книга, построенная на первом этапе.

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

Конец.

Процедура построения «универсальных» кодовых книг на подготовительном этапе предъявляет значительно более высокие требования к вычислительным ресурсам по сравнению с классическим алгоритмом LBG (ECVQ), но так как ее нужно проводить всего один раз при «настройке» метода на целый класс изображений, это требование не является критичным. Скорость работы предложенного метода сжатия сравнима со скоростью работы стандартного JPEG.

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

4 Fowler E., Ahalt S. C. Adaptive vector quantization using generalized threshold replenishment // Proceedings of the IEEE Data Compression Conference, J. A. Storer and M. Cohn, Eds., Snowbird, UT, March 1997, pp. 317-326.

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

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

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

В основу предложенного алгоритма лег алгоритм ББС)5, идея которого заключается в определении на основе М>критерия ветвей дерева вейвлет-коэффициентов, которые можно «подрезать» (обнулить) без значительного ущерба для качества восстановленного изображения. В улучшенной версии6 этого алгоритма (далее — «базовый алгоритм») применялось контекстное кодирование проквантованных коэффициентов. Для текущего коэффициента вычислялась прогнозная величина в ^ как взвешенная сумма абсолютных величин проквантованных вейвлет-коэффициентов:

="-Еяе/(/)а<» Н^-Е^/'яН' (2)

где /(/) — множество индексов некоторых соседних для Wj коэффициентов в текущем саббэнде, Р(ц) — множество индексов соседних к

5 Xiong Z., Ramchandran К., Orchard М. Т. Space-frequency Quantization for Wavelet Image Coding. IEEE Transactions on Image Processing, 1998, vol. 7, issue 6, pp. 892-898.

Умняшкин С. В. Вейвлет-компрессия цифровых изображений с прогнозированием статистических моделей // Известия вузов. Электроника. — № 5. — 2001, —С. 86-94.

коэффициенту-родителю коэффициентов в родительском саббэнде, ат ,

Рт, ¡л , т] — веса. В зависимости от значения sJ■ выбиралась одна из

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

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

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

1 Й§ щ 1 1

1 - 1

г- л и,4

¡И — кодируемый коэффициент Рис. 1. Формы контекста и весовые коэффициенты ат и ¡Зт ) применяемые для вычисления прогнозной величины (2) в предлагаемой модификации Во-вторых, в базовом алгоритме положительные и отрицательные вейвлет-коэффициенты кодируются совместно. Это решение является эффективным с точки зрения простоты реализации, но неоптимальным для получения максимально высокой степени сжатия изображения. Раздельное кодирование знаков и модулей вейвлет-коэффициентов улучшает результаты, так как знаки коэффициентов коррелированы и длина алфавита для моделей коэффициентов уменьшается примерно вдвое.

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

Корреляция между знаками учитывается, как и в случае с модулями коэффициентов, с помощью контекстного кодирования, однако основная идея в данном случае проще. Поскольку у модели для знаков алфавит состоит всего из трех символов, модель для кодирования знака очередного коэффициента определяется по ранее закодированным знакам трех соседних с ним коэффициентов (сверху, слева и сверху слева): для каждой возможной комбинации соседних знаков используется своя модель арифметического кодера. Таким образом, всего для знаков необходимо З3 = 27 моделей. Короткий алфавит также позволяет моделям быстро адаптироваться к статистике для конкретного изображения, поэтому модели для знаков можно инициализировать равномерным распределением.

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

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

Параметр Я вычисляется адаптивно по средней амплитуде коэффициентов, попавших в модель:

я=

где {хк}пк=1 —символы, попавшие в данную модель.

Другой предложенный в главе 4 метод сжатия изображений также частично использует схему модифицированного 8РС> с построением контекстного прогноза по соседним и родительским коэффициентам, но вместо вычислительно сложной процедуры оптимизации топологии дерева вейвлбт-коэффициентов в нем применяется контекстное адаптивное векторное квантование блоков коэффициентов, что позволило при незначительном ухудшении качества сжатия существенно повысить скорость работы. Данный метод так же, как и метод, предложенный в главе 3, разбит на два этапа: подготовительный и основной.

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

Блоки имеют разный размер: на нижних (высокочастотных) уровнях разложения применяются блоки размера 16x16, а на верхних (низкочастотных) — 1 х1, то есть выполняется только скалярное квантование.

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

Контекстный векторный квантователь в данном методе работает следующим образом. Для энергии текущего кодируемого блока хк по соседним блокам и блокам из родительского саббэнда (см. рис. 2) строится значение контекстного прогноза:

Ж, щ щ

V V5

л

Блоки из родительского саббэнда

Кодируемый блок "

Соседние блоки из текущего саббэнда

4.

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

где ef — энергия соседнего с хк блока; Е- — энергия блока из родительского саббэнда; wf, Щ, к, у — весовые коэффициенты, определяемые эмпирически.

Из общей кодовой книги с выбирается некоторое сравнительно небольшое подмножество кодовых векторов (контекстная кодовая книга)

по признаку близости их энергии, т. е. величины е = е[х) = ||х||^ к величине контекстного прогноза:

С = je е С| ЦсЦ^ е • (l - л); • (l + а)]|,

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

Способ контекстного скалярного кодирования ДВП-коэффициентов целиком позаимствован из предыдущего предложенного алгоритма.

В пятой главе приведены результаты численного моделирования алгоритмов, разработанных на основе предложенных методов. Проводится их сравнение со стандартным кодеком JPEG (версия JPEG с кодером Хаффмана и версия с арифметическим кодером) и JPEG-2000 на семи стандартных тестовых изображениях. Мерой качества служит PSNR (ПОСШ, пиковое отношение сигнала к шуму).

Результаты кодирования двух тестовых изображений методом на основе. ДКП и ВК (глава 3) приведены на рис. 3. Для их получения использовалось разбиение АС-коэффициентов на 11 кластеров, построенное по модулям ДКП-коэффициентов. В среднем предложенный метод показал результаты по битовым затратам при фиксированном качестве на 6-22 % лучше, чем стандартный JPEG с арифметическим кодированием.

Предложенный в главе 4 модифицированный алгоритм с вейвлет-фильтрами 9/7 дает результаты на 0,1-0,3 дБ лучше базового алгоритма и на 0,3-0,8 дБ лучше стандартного JPEG-2000 (см. рис. 4). При фиксированном качестве выигрыш по битовым затратам составляет 3-11 % по сравнению с JPEG-2000. Применение других фильтров7 для вейвлет-преобразования позволяет дополнительно улучшить результаты: на изображении Lena наблюдается улучшение еще на 0,1 дБ, а на изобра-

7 Wei D., Pai H.-T., Bovik A. C. Antisymmetric Biorthogonal Coiflets for Image Coding. Proceedings of IEEE International Conference on Image Processing, Chicago, IL, Oct. 1998, vol. 2, pp. 282-286.

жении Barbara — на 0,4 дБ. Таким образом, с альтернативным набором филыров улучшение по сравнению с JPEG-2000 составляет 0,4-0,9 дБ.

34

32

ш 30 -о

ûî

z 28

w

о.

Изображение Goldhill

Изображение Barbara

26 24

........ —-

А* Г /•• ;

—— Предложенный метод

30

m -о

Z 25 w

CL

20

■ Предложенный метод JPEG Хаффман JPEG арифм.

0.2 0.4 0.6 0.8 Ьрр

0.2 0.4 0.6 0.8 1 Ьрр

Рис. 3. Сравнение разработанного алгоритма на основе векторного квантования коэффициентов ДКП с JPEG

Изображение Goldhill

Изображение Lena

40 38

ш и

си

- 36

23

■ Предложенный метод JPEG-2000

0.2 0.4

0.6 Ьрр

0.8

1

v>

cl 34

32 30

-Предложенный метод ----- JPEG-2000

0.2 0.4

0.6 Ьрр

0.8

Рис. 4. Сравнение разработанного алгоритма на основе контекстного кодирования коэффициентов ДВП с №ЕС-2000

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

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

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

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

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

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

- Модифицированный алгоритм сжатия изображений на основе алгоритма SFQ, использующий контекстное кодирование коэффициентов ДВП. Контекстное кодирование основано на вычислении по родительским и соседним ДВП-коэффициентам прогноза для текущего коэффициента. Предложенная модификация заключается в использовании различных форм контекстов для разных.типов саббэн-дов, раздельном кодировании знаков и модулей вейвлет-коэффициентов, а также предварительной инициализации моделей арифметического кодера. Численное моделирование показало, что предложенная модификация SFQ превосходит стандартный JPEG-2000 на 0,3-0,8 дБ по PSNR (3-11 % по битовым затратам при фиксированном уровне качества).

- Новый метод сжатия изображений на основе контекстного векторного квантования и контекстного скалярного кодирования коэффициентов ДВП. Метод частично использует схему модифицированного БРС? с построением контекстного прогноза по соседним и родительским коэффициентам, но вместо применяемой в БРС) вычислительно сложной процедуры оптимизации топологии дерева . ДВП-коэффициентов и подрезания его «незначимых» ветвей для кодирования фоновых областей в нем используется контекстное адаптивное ВК. За счет незначительного ухудшения качества сжатия скорость работы данного метода по сравнению с модификацией БРС) увеличилась более чем на порядок. Несмотря на свою простоту, метод показывает результаты, аналогичные стандартному 1РЕС-2000.

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

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

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

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

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

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

1. Коплович Д. М. Применение векторного квантования в задаче кодирования коэффициентов дискретного косинусного преобразования (тезисы доклада) // Микроэлектроника и информатика — 2004. 11-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. — М.: МИЭТ, 2004. — С. 181.

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

3. Коплович Д. М., Покровский А. С. Модификация алгоритма сжатия цифровой видеопоследовательности в реальном времени // Микроэлектроника и информатика — 2006. 13-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. — М.: МИЭТ, 2006. —С. 157.

4. Коплович Д. М. Алгоритм сжатия изображений на основе контекстного квантования в области дискретного вейвлет-преобразования // Микроэлектроника и информатика — 2007. 14-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. — М.: МИЭТ, 2007. — С. 150.

5. Коплович Д. М., Умняшкин C.B. Модифицированный метод компрессии изображений на основе кодирования древовидных структур коэффициентов вейвлет-преобразования // Труды Российского научно-технического общества радиотехники, электроники и связи имени А.С.Попова. Серия: цифровая обработка сигналов и ее применения. — Выпуск: XI-2. — М.: Рос.НТОРЭС им. А. С. Попова, 2009. — С. 436^39.

6. Умняшкин С. В., Коплович Д. М. Применение адаптивного векторного квантования в задаче кодирования коэффициентов дискретного

косинусного преобразования // Информационно-телекоммуникационные технологии. Всероссийская научно-техническая конференция: Тезисы докладов.— М.: Изд-во МЭИ,

2004. —С. 32-33.

7. Умняшкин С. В., Коплович Д. М. Метод компрессии изображений на основе векторного квантования коэффициентов в области дискретных преобразований // Известия вузов. Электроника. — №4—5. —

2005. —С. 149-155.

8. Умняшкин С. В., Коплович Д. М. Метод компрессии изображений на основе векторного квантования в области дискретных преобразований // Доклады 8-й Международной конференции «Цифровая обработка сигналов и ее применение», 29-31 марта 2006 г. — М.: Изд-во РНТОРЭС им. А.С.Попова. — С. 366-368.

9. Умняшкин С. В., Коплович Д. М., Черкасов И. В. Об использовании контекстного векторного квантования в области дискретных вейвлет-преобразований для компрессии изображений // Цифровая обработка сигналов. — № 2. — 2006. — С. 11-14.

10. Умняшкин С. В., Коплович Д. М., Черкасов И. В., Александров А. А. Алгоритм сжатия изображений на основе контекстного скалярно-векторного квантования в области дискретного вейвлет-преобразования II Известия вузов. Электроника. — №6. — 2006. — С. 86-88.

11. Umnyashkin S. V., Koplovich D. М., Pokrovsky A. S., and Alexandrov A.A. Image Compression Algorithm Based on Encoding of Tree-Arranged Wavelet Coefficients. Proceedings of 3rd Russian-Bavarian Conference on Biomedical Engineering. Erlangen, July 2/3, 2007, pp.121-126.

12. Umnyashkin S. V., Koplovich D. M., Pokrovsky A. S. A Modification of Image Compression Algorithm based on Encoding of Tree-Arranged Wavelet Coefficients. Proceedings of 4th Russian-Bavarian Conference on Biomedical Engineering. Moscow, MIET, July 8/9, 2008, pp.83-86.

13. Умняшкин С. В., Покровский А. А., Коплович Д. М., Александров А. А. Программа для сжатия цифровых изображений на основе кодирования древовидных структур вейвлет-коэффициентов с прогнозированием статистических моделей. Свидетельство о государственной регистрации программы для ЭВМ № 2008610704. — 2008.

14. Умняшкин С. В., Покровский А. А., Коплович Д. М. Кодек цифровых изображений на основе дискретного вейвлет-преобразования с прогнозированием статистических моделей и многомодельным кодированием знаков и модулей коэффициентов преобразования. Свидетельство о государственной регистрации программы для ЭВМ №2010610838.-2010.

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

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

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

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

Используемые сокращения.

Введение.б

Глава 1. Сжатие изображений: понятия, проблемы, возможные решения.

§ 1.1. Дискретные и цифровые изображения.

§ 1.2. Идеи методов сжатия изображений.

§ 1.3. Межэлементная избыточность.

1.3.1. Дифференциальные методы.

1.3.2. Декоррелирующие преобразования.

§ 1.4. Визуальная избыточность: квантование.

1.4.1. Скалярный квантователь.

1.4.2. Векторный квантователь.

§ 1.5. Кодовая избыточность.

1.5.1. Коды Хаффмана.

1.5.2. Арифметическое кодирование.

§ 1.6. Критерий качества изображения.

§ 1.7. JPEG как пример метода компрессии в области преобразования.

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

Глава 2. Векторное квантование в области дискретных преобразований.

§ 2.1. Проблема построения векторного квантователя.

§ 2.2. Оптимальный векторный квантователь и его свойства.

§ 2.3. Алгоритм LBG (практическая реализация векторного квантователя).

2.3.1. Недостатки алгоритма LBG.

§ 2.4. Адаптивное векторное квантование.

§ 2.5. Трудности применения векторного квантования.

§ 2.6. Алгоритм кластеризации коррелированных данных.

§ 2.7. Тестирование алгоритма кластеризации.

§ 2.8. Выводы.

Глава 3. Сжатие изображений на основе векторного квантования коэффициентов ДКП.

§ 3.1. Краткий обзор существующих подходов.

§ 3.2. Корреляция между коэффициентами ДКП.

§ 3.3. ШЭ-оптимизация алгоритма кодирования.

§ 3.4. Задание начальной кодовой книги алгоритма ЬВф.

§ 3.5. Общая схема метода сжатия изображений.

3.5.1. Построение кодовых книг по обучающей последовательности векторов.

3.5.2. Сжатие изображения.

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

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

В 60-е годы XX века необходимость сжатия изображений, хранящихся в цифровом представлении, стала очевидной: в то время запоминающие устройства (как оперативные, так и постоянные) обладали малой емкостью, высокой стоимостью и большими габаритами. Появление эффективного инструмента не заставило себя ждать — в 1965 году вышла статья Дж. Кули и Дж. Тьюки [53], в которой был предложен алгоритм быстрого преобразования Фурье.

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

В качестве подходящих для сжатия изображений рассматривались различные преобразования: Карунена — Лоэва, Адамара, Хаара и др. В конечном счете для изображений стали применять дискретное косинусное преобразование (ДКП), которое по эффективности обработки для марковской статистической модели близко к оптимальному преобразованию Карунена — Лоэва, но, в отличие от него, имеет быстрый алгоритм вычисления и не требует расчета статистических характеристик преобразуемого двумерного сигнала. Именно ДКП используется в методе JPEG, выпущенном в 1992 г. и утвержденном в качестве стандарта ISO 10918-1 [70] в 1994 г.

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

В 2000 году был принят новый стандарт для .сжатия изображений JPEG-2000 (ISO/IEC 15444), использующий ДВП [74]. Сжатые с его помощью изображения обладают лучшим качеством по сравнению с JPEG, а на низких битовых скоростях — существенно лучшим, однако этот стандарт так и не смог вытеснить свою предыдущую версию по причине значительной сложности реализации и повышенных требований к производительности оборудования, которые в большинстве случаев не оправдывались некоторым увеличением качества сжатия и функциональными улучшениями — поддержкой «вложенного» кодирования, прозрачности, ROI (region of interest, «область интереса»), устойчивостью к ошибкам. Лишь в некоторых отраслевых применениях, подробнее о которых рассказано в § 4.2, стандарту JPEG-2000 и другим основанным на вейвлет-преобразовании методам удалось завоевать рынок.

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

Одним из инструментов, используемых в различных схемах сжатия данных, является векторное квантование (ВК) — обобщение повсеместно применяемого скалярного квантования на случай, когда кодируемые данные являются многомерными. Известно, что при определенных условиях векторный квантователь может дать более высокую эффективность сжатия данных по сравнению со скалярным [63, 99]. Однако существуют ограничения (см. § 1.4.2), которые затрудняют практическое применение ВК, поэтому данный метод не используется широко. В настоящее время ВК нашлось нишевое применение в аудиокодеках, таких как TwinVQ, Ogg Vorbis, Dolby DTS, а также в семействе голосовых CELP-кодеков и, в частности, в стандартном кодеке ITU (МСЭ) G.729, который применяется в VoIP-приложениях. Кроме того, векторное квантование использовалось в ранних видеокодеках (Cinepak, Indeo).

В литературе были предложены методы сжатия изображений с применением векторного квантования [42, 58, 64, 98, 109, 125], однако стандартных и широко применяемых методов на его основе не существует. Возможности этого вида квантования до сих пор остаются во многом нераскрытыми.

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

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

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

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

- исследование существующих подходов к сжатию цифровых изображений в области дискретных декоррелирующих преобразований;

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

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

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

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

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

Программная реализация предложенных в работе методов была использована в системе видеонаблюдения «Focus».

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на 11-й, 12-й, 13-й и 14-й Всероссийских межвузовских научно-технических конференциях студентов и аспирантов «Микроэлектроника и информатика» (Москва, МИЭТ, 2004, 2005, 2006 и 2007 гг.), на Всероссийской научно-технической конференции «Информационно-телекоммуникационные технологии» (Сочи, 2004 г.), 8-й и 11-й Международных конференциях «Цифровая обработка сигналов и ее применение» (Москва, 2006 и 2009 гг.) а также на 3-й и 4-й Российско-Баварских конференциях по биомедицинской инженерии (Германия, Эрланген, 2007 г.; Москва, МИЭТ, 2008 г.).

Публикации. По теме диссертации опубликовано четырнадцать работ [5-9, 3137, 119, 120], среди которых три статьи [32, 34, 35] в ведущих рецензируемых научных журналах, четыре доклада [9, 33, 119, 120] в трудах международных конференций (из них два [119, 120] — на английском языке), а также две программы для ЭВМ [36, 37], зарегистрированные в установленном порядке (см. прил. 3).

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

- предложенный метод компрессии цифровых изображений на основе адаптивного векторного квантования коэффициентов ДКП позволяет сократить битовые затраты на кодирование изображения на 6-22 % по сравнению со стандартным методом JPEG;

- модифицированный алгоритм компрессии цифровых изображений на основе контекстного кодирования коэффициентов ДВП позволяет сократить битовые затраты на кодирование изображения на 3-11 % по сравнению со стандартным методом JPEG-2000;

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

Структура диссертации. Диссертация изложена на 150 страницах, состоит из пяти глав и трех приложений, содержит 52 рисунка и 22 таблицы.

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

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

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

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

В пятой главе приведены результаты численного моделирования алгоритмов, разработанных на основе предложенных методов. Проводится их сравнение со стандартным кодеком JPEG (используется версия JPEG с кодером Хаффмана, а также версия с арифметическим кодером) и JPEG-2000 на различных тестовых изображениях.

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

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

Выводы

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

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

Немаловажным достоинством предложенного метода сжатия изображений является его способность адаптироваться к конкретным классам изображений. Для этого достаточно «натренировать» алгоритм, построив с помощью описанной в §3.5.1 процедуры соответствующие кодовые книги по набору типовых изображений. Пользователь может выбирать при работе с кодеком класс изображения, которое ему требуется сжать, что существенно повысит эффективность кодирования. Такой подход эффективен для специализированных баз данных, хранящих однотипные изображения (фотографии в личных делах, биометрические данные, медицинские изображения, аэрофотосъемка и спутниковая съемка), а также в устройствах, передающих такие изображения. Его эффективность для таких применений подтверждается сравнением рисунков 41 и 42, на которых наглядно показана разница в выигрыше между кодовыми книгами, построенными с участием изображения, подвергаемого сжатию, и кодовыми книгами, построенными по другим изображениям.

§ 5.2. Модифицированный алгоритм сжатия изображений на основе контекстного кодирования коэффициентов ДВП

В экспериментах использовалось 5-уровневое ДВП с теми же фильтрами (9/7 и [124]), что и в работе [29], реализованными с помощью лифтинг-схемы [54]. В качестве тестовых изображений были взяты Lena, Barbara и Goldhill. Для определения вносимых алгоритмом потерь в качестве изображения применялась метрика PSNR. Результаты численного моделирования в сравнении со стандартным алгоритмом JPEG-2000 приведены ниже.

Ьрр

Рис. 43. Сравнение модифицированного алгоритма (фильтры 9/7) и стандартного JPEG-2000. Изображение Lena

Ьрр

Рис. 44. Сравнение модифицированного алгоритма (фильтры 9/7) и стандартного JPEG-2000. Изображение Barbara bpp

Рис. 45. Сравнение модифицированного алгоритма (фильтры 9/7) и стандартного JPEG-2000. Изображение Goldhill

Предложенная модификация с фильтрами 9/7 дает результаты на 0,1-0,3 дБ лучше алгоритма [29] и на 0,3-0,8 дБ лучше стандартного JPEG-2000. При фиксированном качестве выигрыш по битовым затратам составляет 3-11 % по сравнению с JPEG-2000.

В приведенных результатах для сжатия по методу JPEG-2000 была использована программа ACDSee Pro, версия 8.1.

Заключение и общие выводы

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

- Новый метод сжатия изображений на основе адаптивного векторного квантования коэффициентов ДКП. Для того чтобы обойти недостатки векторного квантования — слишком большую (63 компонента) размерность вектора и неэффективность стандартного алгоритма построения кодовой книги по обучающей последовательности векторов, — применены оригинальные решения, одно из которых (алгоритм кластеризации коррелированных данных) использовано на практике впервые, а второе решение (условное разделение векторов при инициализации с шагом в случайном направлении) предложено автором. Указанные решения позволяют использовать имеющиеся статистические связи между коэффициентами как внутри блока ДКП, так и между блоками, за счет чего повышается эффективность сжатия. В связи с невозможностью построения универсальной кодовой книги использован алгоритм ее адаптации к конкретным входным данным. Проведено численное моделирование созданного алгоритма. На тестовых изображениях выигрыш относительно JPEG с арифметическим кодированием при фиксированном уровне качества составил от 6 до 22 %.

-Модифицированный алгоритм сжатия изображений на основе алгоритма SFQ, использующий контекстное кодирование коэффициентов ДВП. Контекстное моделирование основано на функции прогноза значения вейвлет-коэффициента, которая строится по родительским и соседним с ним коэффициентам. Предложенная модификация заключается в использовании различных форм контекстов для разных типов саббэндов, раздельном кодировании знаков и модулей вейвлет-коэффициентов (причем для знаков тоже применено контекстное кодирование), а также инициализации моделей арифметического кодера экспоненциальным распределением, параметр которого зависит от данных, содержащихся в конкретной модели. Это позволило более полно использовать статистические связи коэффициентов ДВП друг с другом: численное моделирование показало, что предложенная модификация 8БС) превосходит стандартный 1РЕС-2000 на 0,3-0,8 дБ по Р8№1 (311 % по битовым затратам при фиксированном уровне качества).

- Новый метод сжатия изображений на основе контекстного векторного квантования и контекстного скалярного кодирования коэффициентов ДВП. Метод частично использует схему модифицированного 8Б<3 с построением контекстного прогноза по соседним и родительским коэффициентам, но вместо применяемой в ЭБС) вычислительно сложной процедуры оптимизации топологии дерева вейвлет-коэффициентов и подрезания его «незначимых» ветвей для кодирования фоновых областей в нем используется контекстное адаптивное векторное квантование блоков коэффициентов. Реализованный алгоритм, несмотря на свою простоту, показывает результаты, аналогичные стандартному 1РЕв-2000. Таким образом, за счет незначительного ухудшения качества сжатия скорость работы данного метода по сравнению с модификацией ББС) (§ 4.9) увеличилась более чем на порядок.

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

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

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

- применение алгоритмов ускоренного поиска векторов в кодовой книге (см. § 2.5) позволит дополнительно увеличить производительность алгоритмов, основанных на ВК, что сделает ее сравнимой с производительностью алгоритмов, использующих обычное скалярное квантование;

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

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

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

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

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

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

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

Векторное квантование, применяемое в двух методах из трех, используется для кодирования коэффициентов в «чистом» виде, в то время как более обоснованным, как продемонстрировано в § 3.2 (для ДКП) и § 4.6 (для ДВП), является раздельное кодирование модулей коэффициентов и знаков.

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

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

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

1. Винберг Э. Б. Курс алгебры. — М.: Изд-во «Факториал», 1999. — 528 с.

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

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

4. Коплович Е. А., Умняшкин С. В. Контекстное кодирование коэффициентов дискретного косинусного преобразования с учетом межблочной корреляции // Известия вузов. Электроника. — № 6. — 2004. — С. 78-83.

5. Кочетков М.Е., Умняшкин C.B. Многопотоковая реализация алгоритма арифметического кодирования. — М.: МГИЭТ (ТУ), 1998. — 21 с. Депонировано в ВИНИТИ 25.12.98 № 3884-В98.

6. Красильников H. Н. Цифровая обработка изображений. — М.: Вузовская книга, 2001. —320 с.

7. Лебедев Д. С., Гармаш В. А. О возможности увеличения скорости передачи телеграфных сообщений. — М.: Электросвязь, 1958. —№ 1. — С. 68-69.

8. Лесин В. В., Лисовец Ю. П. Основы методов оптимизации: Учеб. пособие.— М.: Изд-во МАИ, 1998. — 344 с.

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

10. Материалы сайта www.ijg.org

11. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток: Пер. с. англ. — М.: Радио и связь, 1985. — 248 е., ил.

12. ПраттУ. Цифровая обработка изображений, т. 1, 2. —М.: Мир, 1982.

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

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

15. Методы компьютерной обработки изображений. Под ред. В. А. Сойфера. — 2-е изд., испр. — М.: ФИЗМАТЛИТ, 2003. — 784 с.

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

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

18. Тернер Д. Вероятность, статистика и исследование операций. Под ред. А. А. Рывкина. — М.: Статистика, 1976. — 431 с.

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

20. Умняшкин С. В. О кластеризации коррелированных данных. // Информационные технологии в инновационных проектах. Международная конференция (г. Ижевск, 20-22 апреля 1999г.): Материалы докладов. — Ижевск, ИжГТУ,1999.— С. 59-65.

21. Умняшкин С. В. Математические методы и алгоритмы цифровой компрессии изображений с использованием ортогональных преобразований // Дисс. на со-иск. уч. степ, д-ра физ.-мат. наук. — М., 2002. — 382 с.

22. Умняшкин С. В. Теоретические основы цифровой обработки и представления сигналов: учеб. пособие. — М.: ИД «Форум»: ИНФРА-М, 2008. — 304 с.

23. Умняшкин С. В. Вейвлет-компрессия цифровых изображений с прогнозированием статистических моделей // Известия вузов. Электроника. — № 5. — 2001. —С. 86-94.

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

25. Умняшкин С. В., Коплович Д. М. Метод компрессии изображений на основе векторного квантования коэффициентов в области дискретных преобразований // Известия вузов. Электроника. — № 4-5. — 2005. — С. 149-155.

26. Умняшкин С. В., Коплович Д. М., Черкасов И. В. Об использовании контекстного векторного квантования в области дискретных вейвлет-преобразований для компрессии изображений // Цифровая обработка сигналов. — №2.-2006. —С. 11-14.

27. Умняшкин С. В., Коплович Д. М., Черкасов И. В., Александров А. А. Алгоритм сжатия изображений на основе контекстного скалярно-векгорного квантования в области дискретного вейвлет-преобразования // Известия вузов. Электроника. — № 6. — 2006. — С. 86-88.

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

29. Azimifar S.-Z. Image Models for Wavelet Domain Statistics. Ph. D. thesis in Systems Design Engineering, Waterloo, Ontario, Canada, 2005.

30. Berger T. Rate Distortion Theory. Endlewood Cliffs, NJ: Prentice Hall, 1971.

31. Borer T., Davies T., Suraparaju A. Dirac video compression. BBC R&D White Paper WHP124, 2005.

32. Boudraa A.-O., Kanafani Q., Beghdadi A., Zergainoh A. Vector quantization for image compression based on fuzzy clustering. Proceedings of the Fifth International Symposium on Signal Processing and Its Applications, vol. 2, pp. 835-837, 1999.

33. Bradley J. N. Storage and retrieval of large digital images. U. S. Patent 5710835.

34. Bradley J. N., Brislawn C. M. The wavelet/scalar quantization compression standard for digital fingerprint images. IEEE International Symposium on Circuits and Systems, 1994, vol. 3, pp. 205-208.

35. Burrows M., Wheeler D. A block sorting lossless data compression algorithm. SRC Research Report 124, Digital Equipment Corporation, 1994.

36. Chadha N. I., Cuhadar A., Card H. Scalable parallel wavelet transforms for image processing. Electrical and Computer Engineering, 2002. IEEE CCECE 2002. Canadian Conference on. — 2002, pp. 851-856.

37. Cham W.-K. Development of integer cosine transforms by the principle of dyadic symmetry // Communications, Speech and Vision, IEEE Proceedings, Volume 136, Issue 4, Aug 1989. — Page(s): 276-282.

38. Cheng Po-Yuen, Li Jin, Jay Kuo C.-C. Rate control for an embedded wavelet video coder. IEEE Transactions on Circuits and Systems for Video Technology, Aug. 1997, vol. 7, issue 4, pp. 696-702.

39. Ching Yang Wang, Shih Jac Liao, Long Wen Chang. Wavelet Image Coding using variable Blocksize Vector Quantization with Optimal Quadtree Segmentation. ELSEVIER, Journal of Signal Processing: Image Communication, Vol. 15, 2000, pp. 879-890.

40. Chou P. A., Lookabaugh T., Gray R. M. Entropy-constrained vector quantization // IEEE Transactions on ASSP, vol.37, No.l, January 1989, pp. 31-^2.

41. Cohen A., Daubechies I., Feauveau J.-C. Biorthogonal bases of compactly supported wavelets // Comm. Pure and Appl. Math., vol. 45, pp. 485-560, 1992.

42. Comaniciu D., Grisel R. Image coding using transform vector quantization with training set synthesis. Signal Processing — Image and Video Coding beyond Standards, vol. 82, issue 11, Nov. 2002, pp. 1649-1663.

43. Cooley J. W., Tukey J. W. An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19, pp. 297-301, 1965.

44. Daubechies I., Sweldens W. Factoring wavelet transform into lifting steps // Y. Fourier Anal. Appl., 1998, vol. 4, pp. 247-269.

45. Deever A., Hemami S. S. What's your sign?: efficient sign coding forembedded wavelet image coding. Data Compression Conference, 2000. Proceedings, pp. 273282. — 2000.

46. El-Sharkawy M. A., White C. A., Gundrum H. Subband image compression using wavelet transform and vector quantization. IEEE 39th Midwest symposium on Circuits and Systems, 18-21 August 1996, vol. 2, pp. 659-662.

47. Elias P. Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory, Volume 21, Issue 2, pp. 194-203. — 1975.

48. Feng Wu, Xiaoyan Sun. Image Compression by Visual Pattern Vector Quantization (VPVQ). Proceedings of Data Compression Conference, pp. 123-131,2008.

49. Fowler E., Ahalt S. C. Adaptive vector quantization using generalized threshold replenishment // Proceedings of the IEEE Data Compression Conference, J. A. Storer and M. Cohn, Eds., Snowbird, UT, March 1997, pp. 317-326.

50. Gersho A., Gray R. M. Vector Quantization and Signal Compression. Kluwer Academic Publishers, Norwell, MA, 1992. — 760 p.

51. Goldberg M., Boucher P., Shlien S. Image compression using adaptive vector quantization. IEEE Transactions on Communications, vol. 34, no. 2, pp. 180-187, Feb. 1986.

52. Golomb S. Run-length encodings. IEEE Transactions on Information Theory, Volume 12, Issue 3, pp. 399-401. — 1966.

53. Gray R. M. Vector Quantization // IEEE ASSP Magazine — April 1984, pp. 4-29.

54. Hong Wang, Ling Lu, Da-Shun Que, Xun Luo. Image compression based on wavelet transform and vector quantization. Proceedings of 2002 International Conference on Machine Learning and Cybernetics, vol. 4, pp. 1778-1780, 2002.

55. Hsien-Chung Wei, Pao-Chin Tsai, Jia-Shung Wang. Three-sided side match finite-state vector quantization. IEEE Transactions on Circuits and Systems for Video Technology, Volume 10, Issue 1, pp. 51-58. — 2000.

56. Huang C.-M., Bi Q., Stiles G., Harris R. Fast full search equivalent encoding algorithms for image compression using vector quantization. IEEE Transactions on Image Processing, 1(3):413-416, July 1992.

57. Huang S. S.; Jia-Shung Wang. Finite-state residual vector quantizer for image coding. Proc. of Visual Communications and Image Processing, Vol. 2094, pp. 880-889. — 1993.

58. Huffman D. A. A method for the construction of minimum-redundancy codes // Proceedings of the I.R.E., September 1952, pp. 1098-1102.

59. Ichiro Matsuda, Yukio Nomoto, Kei Wakabayashi and Susumu Itoh. Lossless Re-encoding of JPEG images using block-adaptive intra prediction. Proc. of the 16th European Signal Processing Conference. — 2008.

60. ISO/IEC 10918-1. Information technology— Digital compression and coding of continuous-tone still images: Requirements and guidelines. 1994.

61. ISO/IEC 13818-2. Information technology — Generic coding of moving pictures and associated audio information: Video. 2000.

62. ISO/IEC 14496-2. Information technology — Coding of Audio-Visual Objects — Part 2: Visual (MPEG-4 Video). 2004.

63. ISO/IEC 14495-1. Information technology — Lossless and near-lossless compression of continuous-tone still images. 1999.

64. ISO/IEC 15444-1. Information technology — JPEG 2000 image coding system: Core coding system. 2004.

65. ISO/IEC 15444-3. Information technology — JPEG 2000 image coding system: Motion JPEG 2000. 2007.

66. ISO/IEC 29199-2. JPEG XR image coding system. Part 2: Image coding specification. 2009.

67. ITU-R Recommendation BT.500-11. Methodology for the subjective assessment of the quality of television pictures. — ITU-R, 2002. — 48 p.

68. ITU-T Ree. H.264. Advanced video coding for generic audiovisual services, 2005.

69. Jafarkhani H., Farvardin N. Adaptive image coding using spectral classification. IEEE Transactions on Image Processing, April 1998, vol. 7, pp. 605-610.

70. Jinhua Yu. Advantages of uniform scalar dead-zone quantization in image coding system. International Conference on Communications, Circuits and Systems, vol. 2, pp. 805-808,2004.

71. Jung H.-M. Apparatus for encoding an image signal using vector quantization technique. U. S. Patent 5742342. — 1998.

72. Karlekar J., Desai U. B. SPIHT video coder // TENCON '98. 1998 IEEE Region 10 International Conference on Global Connectivity in Energy, Computer, Communication and Control, Volume 1, 17-19 Dec. 1998. — Page(s): 45^18 vol.1.

73. Karunasekera S. A., Kingsbury N. G. A distortion measure for blocking artifacts in images based on human visual sensitivity. IEEE Transactions on Image Processing, June 1995, Volume 4, Issue 6, pp. 713-724.

74. Kautz W. Fibonacci codes for synchronization control. IEEE Transactions on Information Theory, Volume 11, Issue 2, pp. 284-292. — 1965.

75. Khalifa O. O. Fast Algorithm for VQ-based wavelet coding system. IEEE Transactions on Image Processing, Vol. 1, No. 2, April 1992, pp. 205-220.

76. Knuth D. E. Dynamic Huffman Coding. Journal of Algorithms, Volume 6, pp. 163180.— 1983.

77. Kyoung Won Lim, Kang Wook Chun, Jong Beom Ra. Improvement on image transform coding by reducing interblock correlation. IEEE Transactions on Image Processing, 1995. —Pp. 1146-1150.

78. Lewis A. S., Knowles G. Image compression using the 2-D wavelet transform. IEEE Transactions on Image Processing, April 1992, vol. 1, issue 2, pp. 244-250.

79. Linde Y., Buzo A., Gray R. An Algorithm for Vector Quantizer Design. IEEE Transactions on Communications, vol. 28, pp. 84-94, 1980.

80. Liu J., Moulin P. Information-Theoretic Analysis of Interscale and Intrascale Dependencies Between Image Wavelet Coefficients. IEEE Transactions on Image Processing, 2001, vol. 10, issue 11, pp. 1647-1658.

81. Ma Siwei, Fan Xiaopeng, Gao Wen. Low Complexity Integer Transform and High Definition Coding // Applications of digital image processing. Conference No27, Denver CO, ETATS-UNIS (02/08/2004) 2004, vol. 5558 (2), pp. P2.547-554.

82. Malvar H. S. Low-Complexity length-4 transform and quantization with 16-bit arithmetic//ITU-T SG16, Sept. 2001, Doc. VCEG-N44.

83. Marpe D., Gycon H. L. Very low bit-rate video coding using wavelet-based techniques //Circuits and Systems for Video Technology, IEEE Transactions on, Volume9, Issue I, Feb. 1999. — Page(s): 85-94.

84. Martin G. N. N;.Range encoding: an algorithm for removing redundancy from a digitised message. Presented to the Video & Data Recording Conference, Southampton; July 24-27, 1979.

85. Martucci S. A., Sodagar I., Chiang T., Ya-Qin Zhang. A zerotree wavelet video coder // Circuits and Systems for Video Technology, IEEE Transactions on, Volume 7, Issue 1, Feb. 1997.—Page(s): 109-118.

86. Nasrabadi N. M., Feng Y. Image compression using address-vector quantization. IEEE Transactions on Communications.VoK 38, no. 12, pp. 2166-2173. Dec. 1990;

87. Nasrabadi N. M., King R. A. Image coding using vector quantization: A review // IEEE Trans. On Communication. — 1988. — V. 36. — № 8. - P. 957-971.

88. Nelson M., Gailly J.-E. The Data Compression Book (Second Edition). New York: M&T Books, 1995. — 541 p.

89. Ngan K. N., Koh H. C. Predictive classified vector quantization. IEEE Transactions on Image Processing, July 1992, vol. 1, pp. 269-280.

90. Nixon S. W. Transformation and selective inverse transformation of large digital images. U. S. Patent 6201897.

91. Pennebaker W. B., Mitchell J: L. JPEG Still Image Data Compression Standard. New York: Van Nostrand Reinhold, 1992.

92. Ponomarenko N., Egiazarian K., Lukin V. and Astola J. Additional Lossless Compression of JPEG Images, Proc. of the 4th Intl. Symposium on Image and Signal Processing and Analysis (ISPA 2005), Zagreb, Croatia, pp. 117-120, September 15-17, 2005.

93. Princen J. P., Johnson A. W., Bradley A. B. Subband/transform coding using filter bank designs based on time domain aliasing cancellation. IEEE Proc. Intl. Conf. on Acoustics, Speech, and Signal Processing (ICASSP), 1987, vol. 12, pp. 2161-2164.

94. Qiu G., Varley M. R., Terrell T. J., Image coding based on visual vector quantization. IEEE International Conference on Image Processing and its applications, pp. 301-305, July 1995.

95. Rao K. R., Yip P. Discrete Cosine Transform: Algorithms, Advantages, Applications. — Academic Press, Boston. — 1990).

96. Ramamurthi B., Gersho A. Classified vector quantization of images. IEEE Transactions on Communication, 1986, Vol. COMM-34, No. 11, pp. 1105-1115.

97. Rinaldo R., Calvagno G. Hybrid vector quantization for multiresolution image coding // IEEE Trans. Image Processing, vol. 6, pp. 753-758, May 1997.

98. Riskin E. A., Lookabaugh T., Chou P. A., Gray R. M. Variable rate vector quantization for medical image compression. IEEE Transactions on Medical Imaging, vol. 9, no. 3, pp. Sep. 1992.

99. 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, vol. 6, pp. 243-250, June 1996.

100. Schelkens P., Skodras A., Ebrahimi T. The JPEG2000 Suite. John Wiley and Sons, 2009.

101. Shapiro J. M. Embedded image coding using zerotrees of wavelet coefficients. IEEE Transactions on Signal Processing, 1993, vol. 41, issue 12, pp. 3445-3462.

102. Stirner M. and Seelmann G. Improved Redundancy Reduction for JPEG Files. Proc. of Picture Coding Symposium, Lisbon, Portugal, November 7-9, 2007.

103. Strom J. Dead Zone Quantization in Wavelet Image Compression. Report for ECE 253 a, May 1996, University of California, San Diego.

104. Taubman D. High performance scalable image compression with EBCOT. IEEE Transactions on Image Processing, 2000, vol. 9, issue 7, pp. 1158-1170.

105. Tu C., Tran T. D. Context-based entropy coding of block transform coefficients for image compression. IEEE Transactions on Image Processing. Volume 11, Issue 11, pp. 1271-1283. —2002.

106. Ueffing C. Wavelet based ECW image compression. Photogrammetric Week 2001, pp. 299-306, Institute for Photogrammetry, University of Stuttgart.

107. Umnyashkin S. V., Koplovich D. M., Pokrovsky A. S., and Alexandrov A.A. Image Compression Algorithm Based on Encoding of Tree-Arranged Wavelet Coefficients.

108. Proceedings of 3rd Russian-Bavarian Conference on Biomedical Engineering. Erlangen, July 2/3,2007, pp. 121-126.

109. Vitter J. S. Design and Analysis of Dynamic Huffman Codes. Journal of the Association for Computing Machinery, Vol. 34, No. 4, pp. 825-845. — 1987.

110. Wallace G. K. The JPEG still-picture compression standard // Communications of the ACM, vol.34, pp. 30-40, April 1991.

111. Wang Z., Bovik A. C., Sheikh H. R. and Simoncelli E. P. Image quality assessment: From error visibility to structural similarity // IEEE Transactions on Image Processing, vol. 13, no. 4, pp. 600-612, Apr. 2004.

112. Wei D., Pai H.-T., Bovik A. C. Antisymmetric Biorthogonal Coiflets for Image Coding. Proceedings of IEEE International Conference on Image Processing, Chicago, IL, Oct. 1998, vol. 2, pp. 282-286.

113. Weiping Li, Ya-Qin Zhang. Vector-based signal processing and quantization for image and video compression. Proceedings of the IEEE, vol. 83, no. 2, pp 317-335, 1995.

114. Wen J., Villasenor J. Reversible variable length codes for efficient and robust image and video coding. Proc. of Data Compression Conference, pp. 471-480. —1998.

115. Witten R. M., Neal J. G. Cleary. Arithmetic coding for data compression // Communications of the ACM, vol.30, no.6, pp. 520-540, June 1987.

116. Xiaohui Xue, Wen Gao. Context-based statistical model for DCT-based image coder. Proceedings of Picture Coding Symposium — 99. Oregon State Univ. 21-23 April 1999, pp.383-385. Corvallis, OR, USA.

117. Xiong Z., Ramchandran K., Orchard M. T. Space-frequency Quantization for Wavelet Image Coding. IEEE Transactions on Image Processing, 1998, vol. 7, issue 6, pp. 892-898.

118. Yamanaka O., Yamaguchi T., Maeda J., Suzuki Y. Image compression using wavelet transform and vector quantization with variable block size. IEEE Conference on Soft Computing in Industrial Applications, 25-27 June 2008, pp. 359-364.

119. Yonghong Zeng, Lizhi Cheng, Guoan Bi, Kot A. C. Integer DCTs and fast algorithms // Signal Processing, IEEE Transactions on, Volume 49, Issue 11, Nov 2001. — Page(s): 2774-2782.

120. Zheng W. X., Quan Z. Y. Image sequence coding using wavelet transform // Digital Signal Processing Workshop Proceedings, 1996., IEEE, Sept. 1996.— Page(s): 97-100.