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

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

003483

УДК 004.627 + 004.932 + 621.397.12

ПЕТРОВ Александр Васильевич

ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА СЖАТИЯ ПОЛУТОНОВЫХ ИЗОБРАЖЕНИЙ НА ОСНОВЕ АДАПТИВНОГО И МНОГОСТУПЕНЧАТОГО РЕШЕТЧАТОГО ВЕКТОРНОГО КВАНТОВАНИЯ

Специальности:

05.13.01 - Системный анализ, управление и обработка информации (в науке и технике); 05.12.13 - Системы, сети и устройства телекоммуникаций

П 9 НОЯ 2СС9

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

Ижевск-2009

003483782

Работа выполнена на кафедре «Интеллектуальные информационные технологии» в ГОУ ВПО «Ижевский государственный технический университет» (ГОУ ВПО «ИжГТУ», г. Ижевск).

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

заслуженный изобретатель Российской Федерации, доктор технических наук, профессор Лялин В.Е.

Официальные оппоненты: доктор технических наук Цым А.Ю.

(ФГУП «Центральный научно-исследовательский институт связи», г. Москва);

кандидат технических наук, доцент Левицкая Л.Н. (ГОУ ВПО «ИжГТУ», г. Ижевск).

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

ГОУ ВПО «Вятский государственный университет» (ГОУ ВПО «ВятГУ», г. Киров).

Защита состоится 26 ноября 2009 г. в_часов

на заседании диссертационного совета Д 212.065.06 в ИжГТУ по адресу: 426069, г. Ижевск, ул. Студенческая, 7.

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

С диссертацией мЪжно ознакомиться в библиотеке института. С авторефератом можно ознакомиться на официальном сайте ИжГТУ: www.istu.ru.

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

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

В.Н. Сяктерев

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

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

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

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

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

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

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

Область исследования. Диссертационная работа выполнена в соответствии с пунктами 4 - «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации», 5 - «Разработка специального математического и программного обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации», 12 - «Визуализация, трансформация и анализ информации на основе компьютерных методов обработки информации» специальности 05.13.01 - «Системный анализ, управление и обработка информации (в науке и технике)» и пунктами 2 - «Исследование процессов генерации, представления, передачи, хранения и отображения аналоговой, цифровой, видео-, аудио- и мультимедиаинформации; разработка рекомендаций по совершенствованию и созданию новых соответствующих алгоритмов и процедур», 12 - «Разработка методов эффективного использования сетей, систем и устройств телекоммуникаций в различных отраслях народного хозяйства (связь)» специальности 05.12.13 - «Системы, сети и устройства телекоммуникаций».

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

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

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

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

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

- уточнить классификацию алгоритмов адаптивного ВК (АВК) на основе

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- классификация алгоритмов АВК на основе критерия битрейт-искажение (R-D), результаты их сравнения между собой;

- онлайновый алгоритм АВК субполос ДВП (АСВК) с возможностью контроля битрейта кодирования, а также качества изображения;

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

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

- алгоритм адаптивной обработки порогового значения (АОП) для поиска значимых коэффициентов в субполосе и аппроксимация пороговой функции;

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

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

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

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

- уточнена 'классификация алгоритмов метода АВК на основе критерия битрейт-искажение (R-D); выполнено аналитическое сравнение алгоритмов и отмечены достоинства и недостатки алгоритмов;

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

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

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

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

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

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

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

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

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

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

для повышения коммуникативных возможностей в телекоммуникационных системах в ЗАО «Ресурсинвест».

Полученные результаты использованы в учебном процессе ГОУ ВПО «ИжГТУ» при изучении дисциплин «Компьютерная трафика», «Интерактивные графические системы», «Кодирование и цифровая обработка информации».

Апробация работы. Основные положения и результаты диссертации докладывались на российских и международных научно-технических конференциях и симпозиумах, а конкретно на: Российской научно-технической конференции «Приборостроение в XXI веке. Интеграция науки, образования и производства» (Ижевск, 2006); Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы» (Таганрог, 2007); Международной научно-технической конференции «Информационные технологии в инновационных проектах» (Ижевск, 2007); 34-й и 35-й Международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе» (Украина, Крым, Ялта-Гурзуф, 2007, 2008); Международном симпозиуме «Надежность и качество» (Пенза, 2008); IX Международной научно-технической конференции «Искусственный интеллект — 2008. Интеллектуальные системы - 2008» (пос. Кацивели, АР Крым, Украина, 2008).

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

Структура диссертационной работы. Диссертация содержит введение, 4 главы и заключение, изложенные на 152 стр. машинописного текста. В работу включены 40 рис., 5 табл., список литературы из 126 наименований. В приложении представлен акт об использовании результатов работы.

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

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

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

I Пэозмвтоы

т 1__| этого предложен вейв-

ш Преобразование Квантование Энтропийное

кодирование

ф(,у) лет-кодер в качестве основы для разработки

„ , „ эффективных методик

rue. I. Система сжатия с потерями на основе преобразования „ _

1 v 1 сжатия изображении. Он

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

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

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

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

Во второй главе изложены метод ВК, основные определения и свойства системы ВК, рассмотрены варианты применения и способы адаптации его к сжатию изображений. Также уточнена классификация алгоритмов метода АВК по критерию R-D (битрейт-искажение).

Размер данных в результате применения метода ВК уменьшается, когда происходит сжатие с потерями. В этом случае важным становится достижение компромисса между качеством сжатых данных, определяемого степенью искажения (distortion), и размером сжатых данных, определяемого степенью сжатия (битрейтом, bit rate). Теоретически эта задача решена для основного класса данных (источников) с помощью Шенноновской информационной теории сжатия данных с потерями, известной как TiD-теория. Она утверждает, что только с помощью метода ВК можно достичь оптимального показателя R-D, что подтверждают ее асимптотические теоремы об оптимальном кодировании, которые предлагают два подхода к неадаптивному ВК стационарных и эргодических случайных процессов.

В первом из подходов рассматривается множество векторных квантователей, кодирующих со средним искажением не более предопределенного максимума Dmax: R(D„„)<R' < Л(£)„„)+ £Г (для Vff); во втором подходе аналогично есть множество векторных квантователей со средним битрейтом не больше Rmax'• < D(Rи) + 8 (для Уд). Здесь R - битрейт, D- искажение.

В работе приведена формальная схема ВК, описывающая его основные определения и свойства в кратких терминах и обозначениях. Системы ВК основываются на КК С~{с(),..., слг-i} из NZ-мерных векторов с, eRL, индексном множестве /={0,..., Л-1} и кодах переменной длины - множество v, получающееся из N кодовых слов. Связь между этими множествами описывается векторным кодером а, векторным декодером /? и взаимно однозначным индексным кодером у:

- a :Rl —>1: отображение вектора в индекс;

- Р: / -> С: отображение индекса в вектор КК;

- у: I v: отображение индекса в слово кодера переменной длины.

Чтобы оценить искажение между исходным вектором х=(х(0\ ...,x(L~l>)' и

.., введем величину искажения с!(х,х):

'(*«"-*«)*. (1)

10

квантованным ()(х)=х=(х{0\ ¿{х,х) = \х-х^

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

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

Значения вейвлет-коэффициентов

Рис. 2. Гист ограмма кейвлет-коэффиниентов 2-г о уровня преобразования 1Ш «/.«-«я»

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

Системы АВК определяются КК С, состоящей из М, векторов с размерностью Ь,, индексным множе-

с дополн. С

информация"

Источник

Кодер

Декодер

1.ТОАЛ

хЧС

Результат

Рис. 3. Система АВК

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

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

- алгоритмы, ограниченные искажением (ОИ);

- алгоритмы, ограниченные битреитом (ОБ);

- алгоритмы на основе критерия битрейт-искажение (К-В).

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

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

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

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

Из экспериментов установлено, что эффективнее применять нефиксированные КК для возможности их постепенного «разрастания» в процессе обработки. При построении КК для каждой субполосы задавался максимально возможный объем (количество векторов) КК, равный jVim=32. При адаптации КК в процессе кодирования субполосы допускалось ее расширение до Лгмакс=64 векторов, после чего добавление нового вектора в КК осуществлялось одновременно с удалением дольше других неиспользуемых по правилу LRU- оно лучшим образом подходит для обновления КК, т.к. учитывает именно локальные статистические особенности данных при адаптивной обработке. Исследования показали, что увеличение значений Л'иач и JVMaKC приводит к некоторому повышению качества восстановленного изображения, однако влечет за собой повышение битовых затрат и замедлению обработки.

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

Представим систему обозначений, чтобы описать процедуру АСВК. Пусть N - количество субполос; а, - векторный кодер; Д - векторный декодер; у, - индексный кодер переменной длины; См(и), С,(и) - старая и новая КК соответственно для п-ой субполосы; с, - кодовое слово с индексом i е I; pf\n) - вероятность для кодового слова с, е С, (п); Sn - размер КК для и-ой субполосы; D„(Sn) - искажение и-ой субполосы с КК размера Sn; R„(Sn) - число бит (битрейт) для кодирования и-ой субполосы с КК размера Sn; L,vl F,- изучаемый и забываемый наборы; Кц - целевой битрейт; R{R\,..., Лу) - текущий битрейт.

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

своевременно «смотреть вперед». Онлайновый алгоритм АСВК адаптирует свою КК за один цикл.

Предполагается, что вероятность р\'\ (п) известна для каждого вектора КК с. е€,_,(«). Начинается всё с оценки индексного кодера у,. Затем определяется векторный кодер а, . На следующем шаге вычисляются затраты на обновление КК. Если они чувствительны с точки зрения оценки R-D, то КК обновляется; иначе вектор квантуется посредством текущей КК, а также он двигается к началу КК.

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

0. Заданы: векторный декодер Д_,; вероятности р\'\{п) для каждого кодового слова ct е См(и); параметр R-D Л = 0.

1. Для п= 1, ..., Жустановка S„=NHa4 и С,.1(и)=центроид (центр распределения) векторов и-ой субполосы.

2. Расчет индексного кодера уп коды переменной длины которого приблизительно удовлетворяют выражению \у,{с,)\ = -log2 р\'\.

3. Определение для S„ а,(х) = argminte/ [¿/(х,/?/^) + Я • J и искажения DJSn) = d(a,(xl),xl) для каждой субполосы п.

4. Расчет изменения /fD-функции в случае изменения КК:

Ad = -d(at(xt),x,), Ar = yl(xl), AJ = Ad + Л-Аг;

5. Если AJ < 0, тогда:

Если Sn<NmKC, установка Sn:=Sn+l; L, = {х,} и Ft - {Д., (N -1)};

обновление КК, С,(и) становится новой КК;

.....-

Отправка декодеру флага, сигнализирующего обновление КК. Вычисление Dn(Sn).

6. Иначе:

отправка декодеру флага, сигнализирующего неизменность КК и установка С, (я) С,_, (п);

7. Расчет нового векторного декодера: пусть j = a,(xt), тогда

i=о; /?'}> i>j;

Я

■(о _

C-l) >

8. Вычисление р, (п) для всех с- е С,(и).

9. Вычисление текущего битрейта,..., 5Л-).

10. Если Я>ЯЧ, то завершение работы, иначе переход к пункту 4.

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

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

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

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

Из результатов экспериментов установлено, что при битрейте меньше 0,5 Ьрр решетчатое квантование совпадает со скалярным, при увеличении степени сжатия решетчатый квантователь обеспечивает выигрыш более 10% от общей производительности.

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

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

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

тгатгг»г\т-> ?/лпо»«т1 Глпл»4^п ТТо1/лттлпЧФ1 итлЛпом/'оттна тсАттопотитла дч^лч'ии кчиДшпи ^ ^Сд,*!^^ 1Vи) 1>и 111IVч»<

ни

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

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

Из анализа козффици-

Рис. 4. Структура кодера па основе методики МРВК

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

Таким образом, вектор, который состоит из коэффициентов субполосы,

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

р = М.к) у у уг(. А ф

" \Т А Г ¿-¡¿-¿--К- VУ '

больше, чем порог Т, определяемый экспериментальным выражением

Г = ^у^хпороговый_парамстр| , (3)

где Хк - вектор в субполосе к с разрешением Л^; и{к) является перцептуаль-ным весовым фактором (перцептуальное взвешивание); сп> - среднее пиксельное значение входного изображения. Исследование и>(к) в работе не проводилось (было принято за 1 для простоты реализации алгоритмов), однако известно, что для методов на основе систем человеческого зрения он может сыграть большую роль. «Пороговый_параметр», который может иметь значения от 1 до 1000, выбирается, принимая во внимание планируемое значение битрейта.

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

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

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

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

3. Третья стадия (уровневая оптимизация пороговых значений) оптимизирует пороговые значения для каждой субполосы на каждом уровне ДВП:

Пороговый_параметр=(^^ где /=1, 2,3,... (уровни ДВП). к ау )

На этой стадии алгоритм оптимизирует пороговое значение, увеличивая или понижая «пороговый_параметр».

Проведенные экспериментальные исследования подтвердили положительный эффект АОП для ПИ (рис. 5).

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

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

PSNR, дБ

0.5

MPBKT=const ■

-MPBKT=adapl

а)

6)

Рис. 5. Эффект АОП для ПИ: a) «Lena» и б) «Barbara» Известно, что ошибка квантования |е| <q/2. Поэтому выбирается:

a/==(2*/me/?i)/p. (4)

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

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

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

0.1 008 t

1- е ш

ОМ £. г .¿я

МП о J4-!!( К . ... ■ \ ________ ,

-100 ~ -55 0 50 100

Значения вейвлет-коэффициентов

Рис. б. Гистограмма диагональных вейвлет-коэффициентов 2-го уровня ПИ «Lena»

Рис. 7. Развертка решетки Число ступеней

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

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

изменения коэффициентов и в /-ой субполосе.

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

<7 ИхМ

£ Т

где N х М- разрешение изображения, / -уровень ДВП.

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

Как упоминалось, КК «разрастается» до N^¿=64. Тогда на каждой стадии РВК, применяя сферический ^-квантователь с КК радиуса т=4, для четырехмерных векторов доступно 256 узлов решетки (кодовых слова) с КК из 4 уровней. Тогда индекс каждого кодового слова представляется 8 битами. Если на какой-то отдельной стадии РВК получается N кодовых слов, а всего М стадий, то итоговый размер КК будет равен Мх N. Алгоритма методики МРВК и его блок-схема работы для обработки всех высокочастотных субполос приведены в диссертации.

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

-=8..32,

Рис. 8. Определение оптимального значения отношения Ыц

(5)

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

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

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

На основе предложенных алгоритмов создана программная модель кодирования ПИ в среде Matlab, обеспечивающая выполнение всех необходимых процедур обработки ПИ и оценки качества и степени сжатия. Она позволяет осуществлять: выбор ортогональных вейвлетов для преобразования; определение параметров АВК и МРВК; задание значений в таблице квантования; вывод на экран гистограмм распределения вейвлет-коэффициентов на произвольном шаге преобразования; вывод на экран восстановленного изображения; постепенный просмотр «грубой» копии изображения в процессе загрузки файла (прогрессивная передача); определение искажения (PSNR) и битрейта.

Для тестирования алгоритмов сжатия использовались следующие широко распространенные в научной литературе для экспериментальных исследований ПИ с разрешением 512x512 точек: «Lena» - низкочастотное; «Barbara» - высокочастотное; «.Goldhilh - содержит области как высоких, так и низких частот. В данной работе они разбивались на 4 вейвлет-уровня. Для сокращения субполос использовались блоки разных размеров: 2 х 2 - на первом, втором и третьем

Значимые векторы

РВК-1

РВК-2

РВК-М

М-ступснчатая КК

КК, Индекс

1011 34

0101 13

кк; Индекс

0001 1

010-1 14

ккм Индекс

«км 2

1000 7

Рис. 9. Процесс обработки отдельной субполосы с помощью методики МРВК

уровнях и 1 х 1 - для четвертого.

В качестве инструмента вейвлет-преобразования были выбраны биорто-гональныс вейвлеты (9,7) как наиболее хорошо изученные и удобные в вычислительном плане. Отмечено, что глубина разложения определяет «масштаб» отсеиваемых деталей: чем больше эта величина, тем более «крупные» изменения сигнала будут отброшены. Исследования показали, что при достаточно больших значениях глубины (порядка 6-9) выполняется не только очистка сигнала от шума, но и его сглаживание («обрезаются» пики сигнала).

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

Результаты сжатия для тестовых изображений с помощью алгоритма ,1РЕ02000 и предложенной в работе методики МРВК приведены на рис. 11.

Рис. 10. Определение оптимального значения числа уровней ДВП

б) г) е)

Рис. 11. Куски ПИ «Lena» и «Barbara»(масштаб 2:1): а, б - исходного; в, г - сжатого по алгоритму JPEG2000 (битрейт=0,1 Ьрр)\ д, е - сжатого по методике МРВК (битрейт=0,1 Ьрр).

Визуальное сравнение (экспертное оценивание) восстановленных ПИ «Lena» и «Barbara» на уровне битрейта 0,1 Ьрр (сжатие в 80 раз) показывает, что для низкочастотного ПИ «Lena», как минимум, результат применения методики МРВК алгоритма не хуже, чем для алгоритма JPEG2000. Однако высокочастотное ПИ «Barbara» после метода МРВК выглядит четче и менее расплывчато - за счет применения АОП субполос. Помимо этого, хорошее качество обеспечивается использованием метода РВК, где в результате четкой структуры (решетки) и конкретного расположения кодовых слов отводится больше зарезервированных бит определенной субполосы для сохранения деталей (границ) изображения. Таким образом, методика МРВК особенно эффективна для сжатия высокочастотных ПИ, кодирование которых для традиционных методов является сложной задачей.

В ходе экспериментальных исследований было использовано также около десятка фотографических ПИ с различной текстурой. Проведено сравнение с другими работами: с кодером изображения VSPECK и алгоритмами международных стандартов JPEG и JPEG2000. В табл. 1-3 показаны результаты сравнения на уровнях битрейта 0.25, 0.50,1.00 и 2.00 Ьрр для тестовых ПИ.

Таблица 1

Сравнительные характеристики для ПИ «Lena»_

Rate, Ьрр PSNR, дБ

JPEG JPEG2000 VSPECK MPBK

0,25 30,41 34,13 34,57 35,18

0,50 34,75 37,33 37,40 37,70

1,00 37,80 40,43 40,25 40,60

2,00 41,05 44,93 - 44,73

Таблица 2 Сравнительные характеристики для ПИ «Goldhill»

Rate, Ьрр PSNR, дБ

JPEG jpEGim VSPECK MPBK

0,25 26,33 30,95 31,22 31,68

0,50 29,00 33,20 33,53 33,88

1,00 33.21 36,60 36.56 37,12

2,00 37,67 40,10 - 40,15

Таблица 3 Сравнительные характеристики для ПИ «Barbara»

Rate, Ьрр PSNR, дБ

JPEG /№62000 VSPECK MPBK

0,25 ' 24,40 28,27 . 28,51 29,95

0,50 28.95 32,20 32.32 33,02

1,00 33,10 36,59 36,49 37,05

2,00 37,20 41,02 - 41,35

Для оценки быстродействия предложенной методики сравнивались временные затраты на ее работу и алгоритма №ЕС2000 в среде МайаЪ. В среднем на 10 % методика МРВК уступала (из-за нескольких ступеней квантования). Это можно считать незначительным фактом, т.к. время работы алгоритма ЗРЕС2000 в современных устройствах и компьютерах достаточно мало.

Для оценки качества восстановленных изображений на выходе рассматриваемых алгоритмов использовалась величина пикового отношения сигнала к шуму (PSNR), измеряемая в децибелах: PSNR = 10Ioglc (255г / MSÈ), где MSE -

среднеквадратическая ошибка.

Показатели методики МРВК превосходят VSPECK для всех трех тестовых изображений и лучше, чем JPEG, JPEG2000 по качеству восстановленного изображения на всем рассматриваемом диапазоне степеней сжатия.

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

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

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

ЗАКЛЮЧЕНИЕ

В результате проведенного исследования получены следующие выводы.

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

2. Уточнена классификация алгоритмов метода АВК по критерию битрейт-искажение (R-D). Всего выделено три класса алгоритмов АВК: ОИ, ОБ и алгоритмы на основе критерия R-D. Отмечено, что алгоритмы третьего класса по сравнению с другими двумя позволяют добиваться наилучших результатов, особенно для кодирования с низким битрейтом. Онлайновые алгоритмы этого класса являются самыми быстрыми, т.к. адаптирует кодовую книгу за один цикл. Показано, что алгоритмы, ограниченные битрейтом, несравнимо сложны, в отличие от алгоритмов двух других категорий.

3. Разработан онлайновый алгоритм АСВК. Он позволяет пользователю выбирать нужные приоритеты в сжатии изображения, осуществляя контроль

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

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

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

6. Разработан вычислительно эффективный алгоритм методики МРВК, который основан на масштабировании значений ошибок квантования значимых вейвлет-коэффициентов перед квантованием и после их восстановления. Результаты экспериментов показали, что при битрейте больше 0,5 Ърр решетчатое квантование совпадает со скалярным, при увеличении степени сжатия решетчатый квантователь обеспечивает выигрыш более 10 % от общей производительности.

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

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

9. Выполнены экспериментальные исследования разработанных методик сжатия ПИ и новых алгоритмических решений, сокращающие используемые вычислительные ресурсы, а также ошибки квантования. Результаты моделирования показали, что предложенная методика МРВК с алгоритмом АОП превосходит такие алгоритмы как JPEG, JPEG2000, VSPECK и многие другие методы

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

К специальности 05.13.01 - «Системный анализ, управление и обработка информации» относятся пп. 1, 2, 4, 5, 7. К специальности 05.12.13 - «Системы, сети и устройства телекоммуникаций» относятся пп. 3, 6, 8, 9.

НАУЧНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Мурынов А.И., Петров A.B., Самохвалов A.B. Дискретные представления и методы кодирования графических изображений для интеллектуальных телекоммуникационных систем // Вестник Московской Академии рынка труда и информационных технологий, 2006. -№ 22 (44). - С. 105-113.

2. Петров A.B., Данилов М.В. Обоснование для проведения интерпретации временных рядов дискретным вейвлет-преобразованием // Информационные технологии в науке, образовании, телекоммуникации и бизнесе: Материалы 34-й Междунар. конф. - Украина, Крым, Ялта-Гурзуф: Прилож. к журн. «Открытое образование», 2007. - С. 168-170.

3. Мурынов А.И., Петров A.B., Самохвалов A.B. Распознавание структурных элементов изображения на дискретном растре // Ж. АН Украины «Искусственный интеллект» - № 4. - Донецк: Изд-во Наука i ocsiTa, 2007. - С. 317-327.

4. Мурынов А.И., Петров A.B., Самохвалов A.B. Обнаружение и распознавание структурных элементов изображений на основе центроидного преобразования // Многопроцессорные вычислительные и управляющие системы: Материалы Междунар. науч.-техн. конф. - Таганрог: Изд-во ТТИ ЮФУ, 2007. - Т. 2. - С. 187-191.

5. Петров A.B. Использование вейвлет-преобразований для сжатия цифровых цветных изображений // Информационные технологии в науке, образовании, телекоммуникации и бизнесе. Труды 35-й юбилейной междунар. конф. - Украина, Крым, Ялта-Гурзуф: Прилож. к журн. «Открытое образование», 2008. - С. 151-153.

6. Петров A.B. Направления развития стандарта JPEG2000 с помощью объектно-ориентированного сжатия изображений // Информационные технологии в науке, образовании, телекоммуникации и бизнесе. Труды 35-й юбилейной междунар. конф. - Украина, Крым, Ялта-Гурзуф: Прилож. к журн. «Открытое образование», 2008. - С. 153-155.

7. Петров А.В, Объектное кодирование как дополнительный этап сжатия цифровых изображений // Надежность и качество. Труды международного симпозиума: В 2-х томах / Под ред. Н.К. Юркова. - Пенза: Изд-во Пенз. гос. ун-та, 2008.-Т. 1.-С. 240-243.

8. Петров A.B. Двумерный и трехмерный алгоритмы кодирования цифровых цветных изображений // Надежность и качество. Труды международного симпозиума: В 2-х томах / Под ред. Н.К. Юркова. - Пенза: Изд-во Пенз. гос. унта, 2008.-Т. 1.-С. 243-246.

9. Уфимкин А.Я., Петров A.B. Использование центроидного преобразования и цепных кодов для кодирования графических изображений // Надежность

и качество. Труды международного симпозиума: В 2-х томах / Под ред. Н.К. Юркова. - Пенза: Изд-во Пенз. гос. ун-та, 2008. - Т. 1. - С. 253-256.

10. Петров A.B., Самохвалов A.B. Обобщенный алгоритм обучения Хебба при решении задачи кодирования изображений // Ж. АН Украины «Искусственный интеллект» - № 4. - Донецк: Изд-во Наука i освгга, 2008 - С. 412-417.

11. Петров A.B., Самохвалов A.B. Кодирование изображений на основе адаптивного анализа главных компонентов И Искусственный интеллект. Интеллектуальные системы: Материалы IX Междунар. науч.-техн. конф. - Донецк: ИПИИ «Наука i освка», 2008. - Т. 2. - С. 70-73.

12. Петров A.B. Метод кодирования цифровых изображений на основе векторного квантования в области вейвлет-преобразований // Информационные технологии в науке, образовании, телекоммуникации и бизнесе. Материалы 35-й междунар. конф. - Украина, Крым, Ялта-Гурзуф: Прилож. к журн. «Открытое образование», 2008. - С. 175-176.

13. Петров A.B., Кузнецов А.Г. Сжатый способ представления контуров изображения // Информационные технологии в науке, образовании, телекоммуникации и бизнесе. Материалы 35-й междунар. конф. - Украина, Крым, Ялта-Гурзуф: Прилож. к журн. «Открытое образование», 2008. — С. 177-178.

14. Петров A.B. Компьютерное моделирование при решении задачи кодирования изображений // Всстник Ижевского государственного технического университета, 2008. - № 4 (40).С. 117-119.

1-5. Петров A.B. Структура кодера изображений на основе метода многоступенчатого решетчатого векторного квантования // Вестник Ижевского государственного технического университета, 2009.-№2(42).-С. 105-107.

Лицензия ЛР № 020764 от 29.04.98

Подписано в печать 21.10.2009. Формат 60x84 1/16. Отпечатано на ризографе. Уч.-изд. л. 1,73. Усл. печ. л. 1,39 Тираж 100 экз. Заказ №984/2

A.B. Петров

Издательство Института экономики УрО РАН 620014, г. Екатеринбург, ул. Московская - 29

Введение

Список сокращений

Глава 1. АНАЛИЗ СУЩЕСТВУЮЩИХ ПОДХОДОВ К СЖАТИЮ

ПОЛУТОНОВЫХ ИЗОБРАЖЕНИЙ В ОБЛАСТИ ДИСКРЕТНЫХ В ЕЙ В J IE Г-ПРЕОБ РАЮ ВА И И Й

1.1. Теоретические аспекты сжатия изображений

1.1.1. Избыточность данных

1.1.2. Оценка качества сжатия изображений

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

1.1.4. Классы изображений

1.1.5. Требования приложений к алгоритмам компрессии

1.1.6. Методы сжатия файлов растровой графической информации

1.2. Обзор международного стандарта JPEG

1.3. Свойства методов сжатия на основе преобразования

1.4. Применение дискретного вейвлет-преобразования для сжатия изображений

1.5. В ейвлет-кодер изображений

1.5.1. Учет внутри- и межполосных зависимостей между вейвлет-коэффициентами

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

1.5.2.1. Ограниченное энтропией векторное квантование

1.5.2.2. Структурированные методы векторного квантования

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

1.5.4. Распределение бит

1.6. Обзор схем сжатия изображений на основе дискретного вейвлет-преобразования и векторного квантования 47 1.6.1. Решетчатое квантование

1.7. Постановка задачи и выводы по главе

Глава 2. АДАПТИВНОЕ ВЕКТОРНОЕ КВАНТОВАНИЕ В СХЕМЕ

СЖАТИЯ ПОЛУТОНОВЫХ ИЗОБРАЖЕНИЙ В ОБЛАСТИ ДИСКРЕТНЫХ ВЕЙВ ЛЕТ-ПРЕОБРАЗОВАНИЙ

2.1. Постановка задачи

2.2. Применение векторного квантования в общей схеме сжатия изображений

2.3. Оптимальный векторный квантователь

2.4. Проектирование кодовой книги

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

2.6. Алгоритмы адаптивного векторного квантования и их сравнение

2.7. Онлайновый алгоритм адаптивного субполосного векторного квантования

2.8. Полученные результаты и выводы

Глава 3. МЕТОД МНОГОСТУПЕНЧАТОГО РЕШЕТЧАТОГО

ВЕКТОРНОГО КВАНТОВАНИЯ НА ОСНОВЕ СХЕМЫ

АДАПТИВНОЙ ОБРАБОТКИ ПОРОГОВОГО ЗНАЧЕНИЯ

3.1. Решетчатое векторное квантование

3.1.1. Выбор типа решетки

3.1.2. Алгоритмы квантования

3.1.3. Формирование кодовой книги решетчатого квантователя

3.1.4. Ошибки квантования

3.2. Метод многоступенчатого решетчатого векторного квантования в схеме сжатия изображений 92 3.2.1. Структура кодера и декодера изображений на основе методики МРВК

3.2.2. Пороговая функция

3.2.3. Алгоритм адаптивной обработки порога для субполосы

3.2.4. Алгоритм методики МРВК

3.3. Сжатие индексов решетчатой кодовой книги

3.3.1. Кодирование Голомба

3.3.2. Сжатие списка индексов

3.4. Полученные результаты и выводы

Глава 4. СХЕМЫ МЕТОДОВ И АЛГОРИТМОВ, ПРОГРАММНАЯ

РЕАЛИЗАЦИЯ И РЕЗУЛЬТАТЫ МОДЕЛИРОВАНИЯ И

СРАВНЕНИЯ

4.1. Программная реализация методов и алгоритмов

4.2. Результаты моделирования

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

4.2.2. Эффект адаптивной обработки порогового значения

4.2.3. Анализ сложности и быстродействия

4.3. Развитие методов сжатия изображений в области дискретных вейвлет-преобразований

4.3.1. Пути развития предложенных методов

4.3.2. Применение скалярного квантования и анализа главных компонент

4.3.3. Кодовый подход к векторному квантованию

4.3.4. Оптимизация Rate-Distortion

4.4. Полученные результаты и выводы 133 Заключение 135 Литература 138 Приложение (акт об использовании результатов диссертационной работы)

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

Дискретное вейвлет-преобразование (ДВП) и векторное квантования (ВК) являются двумя мощными и эффективными инструментами, применяемыми для сжатия изображений. В последние 10-15 лет было написано много работ и статей о них, были приложены огромные усилия объединить их для получения еще более эффективных методов [40, 41, 47-50, 52, 60-64, 84, 87, 104-106, 119, 123-125]. На сегодняшний день предложено немало алгоритмов и методов сжатия изображений в области ДВП, действует основанный на ДВП международный стандарт JPEG2000 [33, 121, 126].

Квантование данных является хорошо изученной задачей [51, 56, 57, 60, 61, 71, 73, 78, 109, 110]. В то же время вопрос минимизации объема сжатых квантованных данных при заданной допустимой ошибке квантования, известный еще как проблема распределения бит [8, 107], в общем виде не имеет решения (существуют решения для частных случаев [60, 61, 112, 119]). Кроме того, применение на практике метода ВК встречает ряд проблем. Статистические характеристики данных должны быть известны заранее и не изменяться, по возможности, во время сжатия, а фотографические изображения обычно обладают нестационарной статистикой. Также теоретически оптимальный квантователь может быть получен с нереальными условиями — произвольные значения (в достаточной мере большие) размерности и количества векторов представления [67-70, 89, 107]. Наконец, ВК - достаточно сложный и трудоемкий метод, хоть и очень эффективный. Поэтому на практике необходимо применять дополнительные меры. Помимо этого, многие исследования направлены на развитие процессов генерации кодовых книг [4, 40, 41, 60, 67-70, 75, 122].

Увеличение степени сжатия изображений методами на основе ДВП приводит к росту значений ошибок восстановления вейвлет-коэффициентов и визуальному ухудшению восстановленных изображений. При использовании традиционных алгоритмов мелкие детали (границы) частично теряются при высоких степенях сжатия - наблюдаются размытости целых областей в изображении [7, 10, 15, 42, 105, 106, 121, 125]. Сохранение этих деталей является важным при сжатии фотографических изображений.

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

В общем виде решение задачи сжатия цветных фотографических изображений можно свести к решению задачи эффективного сжатия полутоновых {grayscale) изображений (ПИ) - изображений с глубиной цвета 8 бит на пиксел. Это следует из того, что изображение с цветовой схемой RGB первоначально представляется в виде комбинации яркостной и двух цветовых составляющих [7, 9, 10, 12, 44, 45].

Область исследования. Диссертационная работа выполнена в соответствии с пунктами 4 — «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации», 5 - «Разработка специального математического и программного обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации», 12- «Визуализация, трансформация и анализ информации на основе компьютерных методов обработки информации» паспорта специальности 05.13.01 — «Системный анализ, управление и обработка информации (в науке и технике)» и пунктами 2 — «Исследование процессов генерации, представления, передачи, хранения и отображения аналоговой, цифровой, видео-, аудио- и мультимедиаинформации; разработка рекомендаций по совершенствованию и созданию новых соответствующих алгоритмов и процедур», 12 — «Разработка методов эффективного использования сетей, систем и устройств телекоммуникаций в различных отраслях народного хозяйства (связь)» паспорта специальности 05.12.13 — «Системы, сети и устройства телекоммуникаций».

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

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

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

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

- провести анализ существующих систем и методов сжатия ПИ на базе ВК в области ДВП с определением возможности их модификации и создания новых, способных к адаптации в процессе обработки и позволяющие ограничить допустимые потери и обеспечить требуемые показатели качества; выполнить синтез схемы трансформационного кодирования ПИ, обладающей малой ресурсоёмкостью и относительно невысокой вычислительной сложностью; уточнить классификацию алгоритмов адаптивного ВК (АВК) на основе критерия битрейт-искажение (R-D) с выделением сильных и слабых сторон для разработки простого и надежного алгоритма, соответствующего поставленным задачам, позволяющего выбирать нужные приоритеты в сжатии изображения; исследовать и применить структурированный метод решетчатого ВК (РВК) для уменьшения сложности вычислений, отказавшись от трудоемкого полного поиска при формировании кодовых книг;

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

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

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

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

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

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

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

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

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

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

- классификация алгоритмов АВК на основе критерия битрейт-искажение (R-D), результаты их сравнения между собой;

- онлайновый алгоритм АВК субполос ДВП (АСВК) с возможностью контроля битрейта кодирования, а также качества изображения;

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

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

- алгоритм адаптивной обработки порогового значения (АОП) для поиска значимых коэффициентов в субполосе и аппроксимация пороговой функции;

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

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

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов работы.

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

Полученные результаты использованы в учебном процессе ГОУ ВПО «ИжГТУ» при изучении дисциплин «Компьютерная графика», «Интерактивные графические системы», «Кодирование и цифровая обработка информации».

Апробация работы. Основные положения и результаты диссертации докладывались на российских и международных научно-технических конференциях и симпозиумах, а конкретно на: Российской научно-технической конференции «Приборостроение в XXI веке. Интеграция науки, образования и производства» (Ижевск, 2006); Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы» (Таганрог, 2007); Международной научно-технической конференции «Информационные технологии в инновационных проектах» (Ижевск, 2007); 34-й и 35-й Международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе» (Украина, Крым, Ялта-Гурзуф, 2007, 2008); Международном симпозиуме «Надежность и качество» (Пенза, 2008); IX Международной научно-технической конференции «Искусственный интеллект — 2008. Интеллектуальные системы - 2008» (пос. Кацивели, АР Крым, Украина, 2008).

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

Структура диссертационной работы. Диссертация содержит введение, 4 главы и заключение, изложенные на 152 стр. машинописного текста. В работу включены 40 рис., 5 табл., список литературы из 126 наименований. В приложении представлен акт об использовании результатов работы.

ЗАКЛЮЧЕНИЕ

В результате проведенного исследования получены следующие выводы.

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

2. Уточнена классификация алгоритмов метода АВК по критерию битрейт-искажение (R-D). Всего выделено три класса алгоритмов АВК: ОИ, ОБ и алгоритмы на основе критерия R-D. Отмечено, что алгоритмы третьего класса по сравнению с другими двумя позволяют добиваться наилучших результатов, особенно для кодирования с низким битрейтом. Онлайновые алгоритмы этого класса являются самыми быстрыми, т.к. адаптирует кодовую книгу за один цикл. Показано, что алгоритмы, ограниченные битрейтом, несравнимо сложны, в отличие от алгоритмов двух других категорий.

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

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

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

6. Разработан вычислительно эффективный алгоритм методики МРВК, который основан на масштабировании значений ошибок квантования значимых вейвлет-коэффициентов перед квантованием и после их восстановления. Результаты экспериментов показали, что при битрейте больше 0,5 Ърр решетчатое квантование совпадает со скалярным, при увеличении степени сжатия решетчатый квантователь обеспечивает выигрыш более 10 % от общей производительности.

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

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

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

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

2. Ануфриев И.Е., Смирнов А.Б., Смирнова Е.Н. MATLAB 7. Наиболее полное руководство в подлиннике. Изд-во: БХВ-Петербург, 2005. — 1104 с.

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

4. Белоголовый А.В. Сжатие изображений с использованием LDPC-кодов // Вопросы передачи и защиты информации: Сборник статей / Под ред. проф. Е.А. Крука. СПб.: ГУАП, 2006. - 225 с.

5. Блаттер К. Вейвлет анализ. Основы теории. М.: Техносфера, 2004.280 с.

6. Быков Р.Е., Фрайер Р. Цифровое преобразование изображений. Изд-во: Горячая линия-Телеком, 2003. - 228 с.

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

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

9. Гашников С. Методы компьютерной обработки изображений. М.: ФИЗМАТЛИТ, 2004. - 784 с.

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

11. Гонсалес Р., Вудс Р., Эддинс С. Цифровая обработка изображений в среде MATLAB. М: Техносфера, 2006. - 616 с.

12. Грузман И.С., Киричук B.C. и др. Цифровая обработка изображений в информационных системах. Изд-во НГТУ, 2003. - 352 с.

13. Дащенко А.Ф., Кириллов В.Х. и др. MATLAB в инженерных и научных расчетах. Одесса: Астропринт, 2003. - 214 с.

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

15. Жизняков A.JL, Вакунов Н.В. Вейвлет-преобразование в обработке и анализе изображений. М.: ГНЦ РФ - ВНИИгеосистем, 2004. - 102 с.

16. Лурье И., Косиков А. Теория и практика цифровой обработки изображений. М. Научный Мир, 2003. - 176 с.

17. Ляшенков С.А., Сергеев А.В. К вопросу об использовании кодового квантования для сжатия изображений // Труды Научной конференции по радиофизике, ННГУ, 2005.

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

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

20. Петров А.В. Двумерный и трехмерный алгоритмы кодирования цифровых цветных изображений // Надежность и качество. Труды международного симпозиума: В 2-х томах / Под ред. Н.К. Юркова. — Пенза: Изд-во Пенз. гос. унта, 2008.-Т. 1.-С. 243-246.

21. Петров А.В. Компьютерное моделирование при решении задачи кодирования изображений // Вестник Ижевского государственного технического университета, 2008. № 4 (40). - С. 117-119.

22. Петров А.В. Структура кодера изображений на основе метода многоступенчатого решетчатого векторного квантования // Вестник Ижевского государственного технического университета, 2009. № 2 (42). - С. 105-107.

23. Петров А.В., Самохвалов А.В. Обобщенный алгоритм обучения Хебба при решении задачи кодирования изображений // Ж. АН Украины «Искусственный интеллект» № 4. - Донецк: Изд-во Наука i осв1та, 2008 - С. 412-417.

24. Петров А.В., Уфимкин А.Я. Математический аппарат вейвлетов для обработки и сжатия цифровых цветных изображений // Вестник Московской Академии рынка труда и информационных технологий. 2005. - №9(21). — С. 124-131.

25. Петров А.В., Уфимкин А.Я. Теоретические и практические аспекты цифрового сжатия изображений // Вестник Московской Академии рынка труда и информационных технологий. 2005. — № 9 (21). - С. 95-98.

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

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

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

29. Семенюк В.В. Обзор стандарта JPEG2000 // Специально для www.compression.ru, 2002.

30. Сергеев А.В., Дубков К.С. Кодовое сжатие изображений. Основные подходы // Труды Научной конференции по радиофизике, ННГУ, 2005.

31. Смоленцев Н.К. Основы теории вейвлетов. Вейвлеты в MATLAB. — Изд-во: ДМК-Пресс, 2005. 304 с.

32. Соболев Н. Общая теория изображений. М.: Архитектура-С, 2004. —672 с.

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

34. Тарантино К. Цифровая фотография. Компьютерная обработка изображений. М.: Омега, 2005. - 142 с.

35. Терехов С.А. Вейвлеты и нейронные сети. Лекция для школы-семинара «Современные проблемы нейроинформатики». МИФИ, Москва, 2006 г.

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

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

38. Хайкин С. Нейронные сети: полный курс. 2-е изд., испр.: Пер. с англ. - М.: ООО «И.Д. Вильяме», 2006. - 1104 с.

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

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

41. Acharya Т., Ray Ajoy К. Image Processing Principles and Application. -John Wiley&Sons, Inc. Hoboken, New Jersey, 2005. 428 c.

42. Akbari A.S. and Soraghan J. Adaptive joint subband vector quantisation codec for handheld videophone applications // Electronics Letters, vol. 39, no. 14, pp. 1044-1046, 2003.

43. Antonini M., Barlaud M., Mathieu P. Image Coding Using Wavelet Transform // IEEE Trans. Image Proc., 1992. № 2. - pp. 205-220.

44. Barlaud M., Sole P., Gaidon Т., Antonini M. and Mathieu P. Pyramidal lattice vector quantization for multiscale image coding // IEEE Transactions on Image Processing, vol. 3, no. 4, pp. 367-381, 1994.

45. Bayazit U., Pearlman W.A. Variable-Length Constrained Storage Tree-Structured Vector Quantization // IEEE Trans. Image Processing, Mar. 1999. -Vol. 8, № 3. pp. 321-331.

46. Berger T. Rate Distortion Theory: A Mathematical Basis for Data Compression // Prentice-Hall, Englewood Cliffs, NJ, 1971.

47. Bradley J.N., Brislawn C.M. Wavelet transform-vector quantization compression of supercomputer ocean models // Data Compression Conference, May 1993.-pp. 224-233.

48. Chan T.F., Shen J. Image Processing and analysis: variational, PDE, wavelet, and stochastic methods. 2005. - 402 c.

49. Chandra A. and Chakrabarty K. System-on-a-chip testdata compression and decompression architectures based on Golomb codes // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 20, no. 3, pp. 355-368, 2001.

50. Chao C.C. and Gray R.M. Image compression with a vector speck algorithm // in Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP '06), vol. 2, pp. 445-448, Toulouse, France, May 2006.

51. Chou P.A., Lookabaugh Т., Gray R.M. Entropy-constrained vector quantization // IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 37, No. 1, January 1989, pp. 31-42.

52. Conway J.H. and Sloane N.J.A. Voronoi region of lattices, second moments of polytopes, and quantization // IEEE Trans, on Information Theory, vol. IT-28, Mar. 1982, pp. 211-226.

53. Conway J.H. and Sloane N.J.A. Fast quantizing and decoding algorithms for lattice quantizers and codes // IEEE Transactions on Information Theory, vol. 28, no. 2, pp. 227-232, 1982.

54. Conway J.H. and Sloane N.J.A. Sphere-Packings, Lattices, and Groups. -Springer, New York, NY, USA, 1988.

55. Cosman P.C., Gray R.M. and Vetterli M. Vector quantization of image subbands: A survey // IEEE Transactions on Image Processing, vol. 5, no. 2, pp. 202225. February, 1996.

56. Cosman P.C., Oehler K.L. and other. Using vector quantization for image processing // Proc. of the IEEE. Sept. 1993. - Vol. 81, № 9. - pp. 1326-1341.

57. Davis G. and Nosratinia A. Wavelet-based image coding: an overview // Applid and Computational Control, Signals, and Circuits, vol. 1, pp. 205-269, 1998.

58. Davis G., Chawla S. Image coding using optimized significance tree quantization // Proc. Data Compression Conference, 1997. pp. 387-396.

59. Esakkirajan S., Veerakumar Т., Senthil Murugan V. and Navaneethan P. Image Compression Using Hybrid Vector Quantization // International Journal of Signal Processing, Winter 2008. pp. 59-66.

60. Fisher Y. Fractal image compression // New York: Springer-Verlag, 1995.

61. Fowler J.E. A Survey of Adaptive Vector Quantization Part I: A Unifying Structure // IPS Laboratory Technical Report TR-97-01, 1997.

62. Fowler J.E. Adaptive Vector Quantization for the Coding of Nonstationary Sources // PhD thesis, Graduate School of The Ohio State University, 1996.

63. Fowler J.E. Generalized Threshold Replenishment: An Adaptive Vector

64. Quantization Algorithm for the Coding of Nonstationary Sources // IEEE Transactions on Image Processing, 7. -pp 1410-1424, October 1998.

65. Fowler J.E., Ahalt S.C. A Survey of Adaptive Vector Quantization -Part II: Classification and Comparison of Algorithms // IPS Laboratory Technical Report TR-97-02, 1997.

66. Fowler J.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.

67. Fox B. Discrete Optimization via Marginal Analysis // Management Science, vol. 13, no. 3, Nov, 1965.

68. Gallager R.G. Low-density parity-check codes // IEEE Trans, on Inform. Theory. Jan. 1968. - Vol. IT&8. - pp. 21-28.

69. Gallager R.G. Information Theory and Reliable Communication. John Wiley&Sons, 1968.-608 p.

70. Garey M.R., Johnson D.S., Witsenhausen H.S. The complexity of the generalized Lloyd-Max problem // IEEE Trans. Inform. Theory, 1982. Vol. 28, № 2. -pp. 255-256.

71. Gersho A., Ramakrishnan S., Rose K. Constrained-storage vector quantization with a universal codebook // IEEE Transactions on Image Processing 7(6), 1998.-pp. 785-793.

72. Gersho A. and Yano M. Adaptive vector quantization by progressive code-vector replacement // In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, pp. 133-136, May 1985.

73. Gersho A. On the structure of vector quantizers // IEEE Transactions on Information Theory 28(2), 1982. pp. 157-166.

74. Gersho A.A. and Gray R.M. Vector Quantization and Signal Compression // Kluwer Academic, New York, NY, USA, 1992.

75. Gibson J.D. and Sayood K. Lattice quantization // in Advances in Electronics and Electron Physics, P. Hawkes, Ed., vol. 72, chapter 3, Academic Press, San1. Diego, Calif, USA, 1988.

76. Goldberg M. and Sun H. Frame adaptive vector quantization for image sequence coding // IEEE Transactions on Communications, 629-635, May 1988.

77. Goldberg M. and Sun H. Image sequence coding using vector quantization // IEEE Transactions on Communications, vol. COM-34, pp. 703-710, July 1986.

78. Golomb S.W. Run-length encodings // IEEE Transactions on Information Theory, vol. 12, no. 3, pp. 399-401, 1966.

79. Gray R.M. Fundamentals of Vector Quantization // Invited Paper, Proceedings Tencon 87, pp. 1262-1271, 1987, IEEE, Region 10 Conference, August 25-28, Seoul, Korea.

80. Hung A.C., Tsern E.K., Meng Т.Н. Error-resilient pyramid vector quantization for image compression // IEEE Trans, on Image. Process, Oct. 1998. Vol. 7. -P. 1373-1386.

81. Hunt B.R., Lipsman R.L., Rosenberg J.M. Matlab R2007 с нуля! M.: Лучшие книги, 2008. - 352 с.

82. Jeong D.G. and Gibson J.D. Lattice vector quantization for image coding // Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP'89), vol. 3, pp. 1743-1746, Glasgow, UK, May 1989.

83. Kim W.H., Hu Y.H. and Nguyen T.Q. Wavelet-Based image coder with entropy-constrained lattice vector quantizer (ECLVQ) // IEEE Trans. Circuit and Sys-tems-II: Analog and Digital Signal Signal Processing, vol. 45, no. 8, pp. 1015-1030, August 1998.

84. Kohonen T. Self-Organization and Associative Memory // Berlin: Springer-Verlag, 1988.

85. Kossentini F.F., Smith M.J.T. and Barnes C.F. Necessary conditions for the optimality of variable-rate residual vector quantizers // IEEE Transactions on Information Theory, vol. 41, no. 6, pp. 1903-1914, 1995.

86. Lancini R., Perego F. and Tubaro S. Neural network approach for adaptive vector quantization of images // In Proceedings of the International Conference on

87. Acoustics, Speech, and Signal Processing, (San Francisco, CA), pp. 389-392, March 1992.

88. Lee T.-C. and Peterson A.M. Adaptive Vector Quantization Using a Self-Development Neural Network // IEEE Journal on Selected Areas in Communications, vol. 8, pp. 1458-1471, October 1990.

89. Li J., Gray R.M., Olshen R. Joint Image Compression and Classification with Vector Quantization and Two Dimentional Hidden Markov Model // Data Compression Conference: IEEE Computer Society TCC, 1999. pp. 23-32.

90. Lightstone M. and Mitra S.K. Adaptive Vector Quantization for Image Coding in an Entropy-Constrained Framework // In Proc. of ICIP'94, Austin, TX, November 1994.

91. Lightstone M. and Mitra S.K. Image-Adaptive Vector Quantization in an Entropy-Constrained Framework // IEEE Transactions on Image Processing, 1996.

92. Lin J.-H., Vitter J.S. Nearly Optimal Vector Quantization via Linear Programming // Data Compression Conference: IEEE Computer Society TCC, 1992. -pp 22-31.

93. Linde Y., Buzo A., Gray R.M. An Algorithm for Vector Quantizer Design // IEEE Transactions on Communication, vol. COM-28, No. 1, January 1980, pp. 84-95.

94. Mallat S., Falzon F. Understanding image transform codes // Proc. SPIE Aerospace Conf., Orlando, 1997.

95. Man H., Kossentini F. and Smith M.J.T. A family of efficient and channel error resilient wavelet/subband image coders // IEEE Transactions on Circuits and Systems for Video Technology, vol. 9, no. 1, pp. 95-108, 1999.

96. Mukherjee D. and Mitra S. K. Successive refinement lattice vector quantization // IEEE Transactions on Image Processing, vol. 11, no. 12, pp. 1337-1348, 2002.

97. Nasrabadi N.M. and Feng Y. A Dynamic Finite-State Vector Quantization Scheme // in Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, (Albuquerque, New Mexico), pp. 2261-2264, April 1990.

98. Paul D.B. A 500-800 bps Adaptive Vector Quantization Vocoder Using a

99. Perceptually Motivated Distance Measure // in Conference Record, IEEE Globecom, pp. 1079-1082, 1982.

100. Pearlman W.A., Islam A., Nagaraj N. and Said A. Efficient, low-complexity image coding with a set-partitioning embedded block coder // IEEE Transactions on Circuits and Systems for Video Technology, vol. 14, no. 11, pp. 1219-1235,2004.

101. Raffy P., Antonini M., Barlaud M. Distortion-Rate Models for Entropy-Coded Lattice Vector Quantization // IEEE Transactions on Image Processing, 2000. Vol. 9, № 12. - pp. 2006-2017.

102. Said A. and 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, no. 3, pp. 243-250, 1996.

103. Salleh M.F.M. and Soraghan J. A New Multistage Lattice Vector Quantization with Adaptive Subband Thresholding for Image Compression // EURASIP Journal on Advances in Signal Processing, vol. 2007, Article ID 92928, 11 p., 2007.

104. Salleh M.F.M. and Soraghan J. A new multistage lattice VQ (MLVQ) technique for image compression // in European Signal Processing Conference (EUSIPCO'05), Antalya, Turkey, September 2005.

105. Salomon D. Data compression: The complete reference. 3rd edition, New York: Springer-Verlag, 2004. - 898 p.

106. Senecal J., Duchaineau M. and Joy K.I. Length-limited variable-to-variable length codes for high-performance entropy coding // in Proceedings of Data Compression Conference (DCC'04), pp. 389-398, Snowbird, Utah, USA, March 2004.

107. Shannon C.E. A Mathematical Theory of Communication // Bell System Technical Journal, vol. 27, pp. 379-423, 623-656, July, October 1948.

108. Shannon C.E. Coding theorems for a discrete source with a fidelity criterion // IRE Nat. Conv. Rec., part. 4, 1959, pp. 142-163.

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

110. Shoham Y., Gersho A. Efficient bit allocation for an arbitrary set of quantizers // IEEE Trans. Acoustics, Speech, and Signal Processing, 1988. № 9. -pp. 1445-1453.

111. Sikora T. Trends and perspectives in image and video coding // Proceedings of the IEEE, vol. 93, no. 1, pp. 6-17, 2005.

112. Skodras A.N, Christopoulos C.A. and Ebrahimi T. The JPEG 2000 still image compression standard // IEEE Signal Processing Magazine, vol. 18, no. 5, pp. 36-58, 2001.

113. Sloane N.J.A. Tables of sphere packings and spherical codes // IEEE Transactions on Information Theory, vol. 27, no. 3, pp. 327-338, 1981.

114. Ungerboeck G. Channel Coding with Multilevel/Phase Signal // IEEE Trans. Inform. Theory, vol. IT-28, January, 1982, pp. 55-67.

115. Ungerboeck G. Trellis-coded Modulation with Redundant Signal Sets. Part I and II. // IEEE Communications Magazine, vol. 25, February, 1987, pp. 5-21.

116. Viterbi A.J., et. al. A Pragmatic Approach to Trellis-Coded Modulation // IEEE Communications Magazine, vol. 27, № 7, July, 1989, pp. 11-19.

117. Voukelatos S.P. and Soraghan J. Very low bit-rate color video coding using adaptive subband vector quantization with dynamic bit allocation // IEEE Transactions on Circuits and Systems for Video Technology, vol. 7, no. 2, pp. 424-428, 1997.

118. Wagner M. Video Coding with Adaptive Vector Quantization and Rate Distortion Optimization // Dissertation, 2000. pp. 188.

119. Wallace G.K. The JPEG still picture compression standard // IEEE Trans. Consumer Electron., vol. 38, no. 1, Feb 1992, pp. 18-34.

120. Wang X., Shende S. and Sayood K. Online Compression of Video Sequences Using Adaptive VQ Codebooks // in Proceedings of the IEEE Data Compression Conference, (Snowbird, UT), pp. 185-194, IEEE Computer Society Press, March 1994.

121. Woolf A. and Rogers G. Lattice vector quantization of image wavelet coefficient vectors using a simplified form of entropy coding // in Proc. IEEE Int. Conf.

122. Acoustics, Speech and Signal Processing, vol. 5, Adelaide, Australia, Apr. 1994, pp. 269-272.

123. Yoo Y., Ortega A., Yu B. Progressive classification and adaptive quantization of image subbands // Preprint, 1997.

124. ISO/IEC JTC 1/SC 29/WG 1 N1646R, ISO/IEC FCD 15444-1: Information technology JPEG 2000 image coding system: Core coding system, March 2000. - 190 c. http://www.jpeg.org/public/fcdl5444-l.htm.