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

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

Хусаинов Наиль Шавкятович

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ СЖАТИЯ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ С ИСПОЛЬЗОВАНИЕМ ДЕЛЬТА-ПРЕОБРАЗОВАНИЙ ВТОРОГО ПОРЯДКА

Специальности: 05.13.14 - Системы обработки информации и управления 05.13.17 — Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Таганрог-1998

Работа выполнена в Таганрогском государственном радиотехническом университете

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

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

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

доктор технических наук, профессор Макаревич О.Б., г.Таганрог кандидат технических наук, старший научный сотрудник Аграновский A.B., г.Ростов-на-Дону

Ведущая организация: НИИ связи, гЛаганрог

Защита состоится 3 декабря 1998г. в 14-20 часов на. заседании диссертационного совета Д 063.13.01 в Таганрогском государственном радиотехническом университете по адресу: г.Таганрог, пер.Некрасовский, 44, ауд. Д-406.

Отзывы на автореферат просьба направлять по адресу: 347928, г.Таганрог, ГСП-17А, пер.Некрасовский, 44, Совет университета.

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

Автореферат разослан 3 ноября 1998г.

Ученый секретарь совета

Чефранов А.Г.

ВВЕДЕНИЕ

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

Актуальность разработки нового метода кодирования, ориентированного не только на достижение достаточно высоких степеней сжатия, но и на высокое быстродействие алгоритма обработки изображений, а, впоследствии, и видеопоследовательностей, объясняется высокой трудоемкостью существующих методов сжатия видеоинформации. Известные методики кодирования с потерями позволяют достигать степени сжатия порядка Ю-15 раз для статических и более 30 раз для динамических изображений при достаточно хорошем для визуального восприятия качестве «картинки». Однако в большинстве из них уменьшение потерь достигается за счет использования трудоемких алгоритмов перевода и последующей обработки изображения в частотной области (например, дискретно-косинусного преобразования). Вследствие этого весьма проблематичным является даже простое воспроизведение цифровой видеопоследовательности в реальном (или близком к реальному) масштабе времени без соответствующей аппаратной поддержки.

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

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

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

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

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

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

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

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

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

- разработка программной модели кодирующего устройства;

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

устройства;

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

Научные результаты работы: -разработан модифицированный алгоритм дельта-преобразований второго порядка со сглаживанием;

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

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

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

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

- методика коррекции ошибок кодирования;

методика комплексного кодирования/декодирования изображения. Практическую ценность представляют:

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

;)лгор:п~м оптимизированных дельта-преобразований второго порядка с компандированием;

методика коррехции ошибок для обеспечения требуемой точности гсодирования;

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

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

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

программный пакет Сяоттия/Босстзнозления изображений; оценки и рекомендации гго выбору наиболее оптимальных значений параметров кодирования изображений. Данная работа представляет перспективный. интерес для решения комплексной проблемы сжатия аудиовизуальной информации с возможностью ее быстрой программной распаковки, превышающей быстродействие известных алгоритмов восстановления на основе преобразований в 2,5-3 раза, что может позволить выполнять восстановление видеоинформации без использования специальных дорогостоящих аппаратных средств декодирования, а также повысить качественные характеристики систем воспроизведения динамических изображений.

б

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

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

Реализация и внедрение результатов работы. Работа выполнялась в рамках госбюджетной НИР № 12454 «Разработка алгоритмов и программных моделей для сжатия информации и цифрового управления нелинейными объектами на основе оптимизированных дельта-преобразований второго порядка»; значительная часть результатов данной работы изложена в отчетах по НИР. Некоторые результаты работы были использованы в проекте № 576369 (шифр «РОБОТ-97») «ТеоретнчЗЬ&ге основы и методы построения интеллектуальных систем управления автономных роботов» Межвузовской научно-технической программы «Робототехнические системы», а также внедрены в рамках работ ЮРКЦ «Земля» по реализации федеральной целевой программы «Создание автоматизированной системы ведения государственного земельного кадастра». Часть результатов работы использовалась в учебном процессе при подготовке курса «Цифровое управление, сжатие и параллельная обработка информации на основе алгоритмов оптимизированных дельта-преобразований».

Апробация результатов работы. Основные результаты работы докладывались и обсуждались на: Всероссийской научной конференции студентов и аспирантов «Радиоэлектроника, микроэлектроника, системы связи и управления» (Таганрог, 1997); конференции преподавателей и сотрудников ТРТУ (ТРТУ, 1997); Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Биотехнические, информационные и экологические системы» (Рязань, 1997); XXIV Всероссийской молодежной научной конференции «Гагаринские чтения» (1998); IV Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника н системы управления» (Таганрог, 1998).

Публикации. По итогам работы выпущены 6 публикаций.

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

СОДЕРЖАНИЕ

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

положения, выносимые :ш защиту. Кратко рассмотрено содержание разделов диссертации

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

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

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

Алгоритмы сжатия информации могут быть разбиты на методы, предполагающие сжатие без потерь п методы сжатия с потерями. Как следует из приведенного з работе обзора методов кодирования, большинство алгоритмов первой группы для сжатия информации используют статистичестспе избыточности, содержащиеся в обрабатываемых данных Однако з больсгавстзз случазз применение ^слйко даштых метедси для кодирования видеоинформации к практических целях имеет существенные ограничения: низкая предельная величина коэффициента сжатия, из превьпгающая энтропии источника- ттогагпеп повышения коэффициента сэкзтяя ¡триводкт х увелачешпо сложности кодирующего к ,';йкс.д'.ру;ол?его устройств и снижению кх -погг.мд?п^дшсст!Г зочяоеть кодирования в больптнстЕ« случаев

ЯВЛ8СТС9 И^бытомнся ДЛП ЦПуалКЮГО .«ОСОРЯЯТШ.

С тсдоаетелг-но. 71». зцдге&афермации более

¿.¡птлотсг^сльньши являются методы скатил с потерями. В этом слугае

1 ПрэттУ. Цифровая обработка кхбрззашй: Пер. с англ.. -М.:Мнр, 1532.

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

Одним из наиболее распространенных методов сжатия, позволяющих реализовать как определенные аспекты статистического, так и психофизического кодирования, является сжатие на основе кодирования с преобразованием, предполагающее перевод и последующую обработку сигнала в частотной области. Однако сложность реализации дажз алгоритмов быстрого дискретно-косинусного преобразования (ДКП) составляет 2ЛГ21оопераций сложения и умножения (где ШЫ - размер матрицы преобразования), т.е. до 10-12 операций сложения и умножения на 1 элемент изображения. А комбинированное применение данных алгоритмов с другими методиками кодирования приводит к недопустимо низкой для многих приложений скорости кодирования и, главное, декодирования изображений, что вынуждает либо снижать качественные характеристики изображений (уменьшать разрешающую способность, цветовую глубину, снижать частоту кадров), либо использовать аппаратные средств для их декомпрессии. Недостатки такого подхода очевидны.

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

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

2 Кравченко ГШ Основы теории оптимизированных дельта-преобразований второго порядка Цифровое управление, сжатие и параллельная обработка информации: Монография, Таганрог: йзд-во ТРТУ, 1997.

Рис < Чгргктер аосзденяя демодулированной функции, подученной на основе различных алгоритмов дельта-преобразозаний: v - неходкая функция строки изображения;

- Г(1) - алгоритм дзтьта-модудявдга первого порядка;

- ?(2) - алгоритм дельта-модуляции второго порядка с управлением по знаку ошибки;

- Г(2о) - алгоритм дельта-преобразования второго порядка Крутько

- F- предлагаемый модифицированный алгоритм де^тз-преобраэоЕагш: со сглаживанием на основе алгоритма оптимизированных дельта • преобразований второго порядка Кравченко П П.

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

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

Для уменьшения влияния высокочастотной составляющей исходного сигнала в работе предложен модифицированный агсгоритм дельта-преобразований второго порядка со сглаживанием. Сглаживание выполняется при реализации алгоритма модуляции с использованием усредненного значения приращений модулируемой функции на интервале [г. i-' П]

Модуляция: г,-У,- у,; У

Fi = 2, + 1.5Уг, + (0.5Уг,2/с - 0.Шс^^Уг,); (1)

Д^-аЁЛ^,);

демодуляция:

Ум = У, + УК*.,; с ¿с; О0,

где у, = - значение модулируемой функции на /-ом шаге в момент времени /„ /=1,2,...; = /0+'У/; V/ - постоянный шаг дельта-модуляции; -значение демодулированной функции на /-ом шаге; г, - погрешность дельта-модуляции на /-ом шаге; Уг, - приращение погрешности; У2У,+1 -вторая разность демодулированной функции (квант модуляции); -первая разность демодулированной функции; я§п(х) е {-1;+1}, причем е1^(0)=+1 или

Пример преобразования строки изображения с использованием алгоритма (1) приведен на рис. 1 (кривая У).

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

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

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

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

Модуляция: г, - к:

Чу,а* = <у«*-у,)!'г, _______________ __

V.-. - УГ, - Уу,: -------

/•; • г, + 1.5Уг, + (0.5- 0 Шс^^Уг,),

- -Е1£п(/',), (2)

демодуляция.

к"т (с Д^), если Ая-! - А: = . ~ Д,.я

УГ

й-1

I с, Д^ь кяаче,

^ Гм = Г, + УГ„;; ^ гаг; ¿>0; А >1 где - элемент массива коэффициентов «усиления» значений кванта модуляции» причем к-\£т!к?„-ч> 1; т - длина последовательности квантов модуляции одного знака, необходимая для увеличения значения У2}**! на коэффициент 1ст.

В алгоритме (2) значение второй разности У2}*,« может изменяться ке только по знаку, но и по модулю. Следствием этого является увеличение максимальной скорости изменения демодулированион функции.

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

-на пологом участке модулируемой функции у: (при частых избиениях энака кванта модуляции) изменения значений второй разности будут незначительны и, следовательно, скорость изменения демодулирсвагазой функции будет соответствовать скорости изменения К, для алгоритма (1), при скачке модулируемой функции у, (знак кванта модуляции не изменяется на интервале [/ /-¡-/я}} значение агорой разности на (¿+/л+1)-ом шаге будет масштабировано в - раз, что приведет к росту скорости изменения VI* и

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

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

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

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

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

Зона объединяет определенное количество соседних блоков в направлении обхода изображения. Для обеспечения заданного качества в пределах зоны выполняется анализ ошибок, вызванных погрешностью аппроксимации исходных пикселов дельта-последовательностью, и определяются те столбцы блоков, которые вносят наибольший вклад в суммарную ошибку зоны. Для этого вычисляется текущая средняя ошибка зоны и сравнивается с величиной заданной предельной средней ошибки зоны 5""". Затем выполняется последовательное подавление ошибок в упорядоченном массиве суммарных ошибок, которое заключается в установке флага необходимости введения корректирующего значения для столбца блока, суммарная ошибка которого должна быть подавлена. Этот процесс выполняется,пока 2*°"* > 8ю".

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

значение в столбце может быть закодировано г(1)-бэтамн; -длинное приращение ошибки (код 2), когда наибольшее абсолютное значение в столбце может быть закодировано г(2)-бнтами, причем Н2)>*1);

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

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

С учетом квантования размер Л который будет занимать корректирующее значение а выходном потоке, может быть определен как = tiT^-q, где q - количество младших разрядов корректирующего значения, отбрасываемых при квантовании, а ¥* - огтоеделенный -пш кодирования столбца.

Декодер выполняет обратную последовательность действий.

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

Для уменьшения объема закодированных данных может использоваться независимое дополнительное кодирования по Хаффмену корректирующих значений каждого типа, трупп тнпов строк и форматов столбцов, однако повышение коэффициента сжатия при кодировании по Хаффмену (на 1520%) достигается за счет значительного увеличения трудоемкости, в частности; алгоритмов декодирования (без использования кодирования по Хаффмену основная трудоемкость восстановления элемента изображения составляет от 2 до 4 операций целочисленного сложения).

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

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

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

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

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

-даны рекомендации по выбору наиболее оптимальных значений параметров используемых алгоритмов дельта-преобразований при цветовой глубине каждой из цветовых компонент, равной 8-разрядам (общая цветовая палитра изображения -16,7 млн. цветов); -изменение коэффициента сжатия прямо пропорционально изменениям значений предельных средних ошибок зоны S""" и подобия S04* (обратно пропорционально верности кодирования);

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

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

- применение предварительной низкочастотной фильтрации изображения стандартными фильтрами позволяет существенно повысить как соотношение сигнал/шум с исходным отфильтрованным изображением (в среднем на 12 - 15%), так и коэффициента сжатия (до 16-20 раз);

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

Рис.2. Повышение производительности алгоритма восстановления изображения (в %) при снижении качества кодирования изображения (в %) по разработанному методу и алгоритму JPEG.

О

О -6% -10% -15% с/ш

Отказ от трудоемких операций перевода и обработки изображения в частотной области, которые лежат в основе большинства международных стандартов, несколько снижает количественные показатели эффективности кодирования изображений по предложенному метолу, в частности, по сравнению с пакетом JPEG (показатель коэффициента сжатия по предложенному методу в среднем ниже, чем у JPEG, в 1.4 раза, при разнице в соотношении сигнал/шум в среднем, порядка 1.7дБ). Однако, преимущество в производительности разработанного алгоритма декодирования изображений примерно в 2.7 раза в сравнении с алгоритмом JPEG в сочетании с его достаточно высокими показателями по качеству кодирования (по субъективным оценкам, практически не уступающем JPEG), и степени сжатия (в среднем, коэффициент сжатия составляет около 9-14 pat без предварительной фильтрации) позволяют не только сделать вывод о возможности его применения для кодирования неподвижных растровых изображений со сжатием, но и говорить о перспективности его использования в области кодирования и быстрого программного восстановления видеопоследовательностей.

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

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

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

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

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

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

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

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

1. Кравченко П.П., Хусаинов Н.Ш. Сжатие растровых изображений с потерями на основе алгоритмов оптимизированных дельта-преобразований второго порядка //Компьютерные технологии в инженерной и управленческой деятельности. - 1998. - ч.2.

2. Кравченко П.П., Хусаинов Н.Ш. Сжатие растровых изображений на основе алгоритма оптимизированных дельта-преобразований второго порядка //Синтез алгоритмов сложных систем. -1997. - № 9.

3. Кравченко П.П., Хусаинов'Н.Ш. Сжатие графических изображений на основе алгоритмов оптимизированных дельта-преобразований второго порядка //Известия ТРТУ: - 1998. - № 3.

4. Хусаинов Н.Ш. Метод сжатия графических изображений на основе алгоритмов дельта-преобразований второго порядка: Тез. докл. Всероссийской научной конференции студентов и аспирантов «Радиоэлектроника, микроэлектроника, системы связи и управления». - -Таганрог.: Изд-во ТРТУ, 1997.

5. Хусаинов Н.Ш., Кравченко П.П. Использование алгоритмов дельта-преобразований второго порядка для сжатия графических изображений: Тез. докл. Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Биотехнические, медицинские и экологические системы и комплексы». - Рязань, 1997.

6. Хусаинов Н.Ш. Использование алгоритмов дельта-преобразований второго порядка для кодирований графических изображений со сжатием: Тез. докл. IV Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления». - Таганрог, 1998. .

В работах, выполненных в соавторстве, вклад автора диссертации состоит в разработке модифицированного алгоритма дельта-преобразований со сглаживанием [1]; в разработке методики аппроксимации изображения с использованием предложенных модифицированных алгоритмов [2-3]; в разработке комплексной методики кодирования и декодирования изображений [5].

Тип.ТРТУ Зак.№ Тираж 100 экз.



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

РОССИЙСКОЙ ФЕДЕРАЦИИ

ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ СЖАТИЯ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ С ИСПОЛЬЗОВАНИЕМ ДЕЛЬТА-ПРЕОБРАЗОВАНИЙ ВТОРОГО ПОРЯДКА

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

05.13.14 - «Системы обработки информации и управления» 05.13.17 - «Теоретические основы информатики»

На правах рукописи УДК 681.3.01

Хусаинов Наиль Шавкятович

Диссертация

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

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

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

Таганрог - 1998

г

Содержание

Введение........................................................................................ 5

1. Аналитический обзор существующих методов и подходов к кодированию изображений.................................................................................17

1.1. Особенности психовизуального восприятия цвета. Цветовые пространства..........................................................................18

1.2. Меры верности воспроизведения изображений................................22

1.3. Предварительная обработка изображений......................................26

1.4. Признаки изображений..............................................................28

1.5. Обзор некоторых методов кодирования........................................30

1.6. Стандарт кодирования изображений JPEG.....................................41

1.7. Проблемы, связанные с практическим использованием существующих методов кодирования с потерями................................................45

1.8. Выводы..................................................................................48

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

2.1. Постановка задачи дельта-преобразования второго порядка...............50

2.2. Базовый алгоритм двоичного дельта-преобразования на основе вторых разностей..............................................................................53

2.3. Модифицированный алгоритм двоичного дельта-преобразования со сглаживанием........................................................................57

2.4. Модифицированный алгоритм двоичного дельта-преобразования с компандированием.................................................................62

2.5. Выводы................................................................................69

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

порядка......................................................................................72

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

3.2. Цветовая модель. Поддискретизация............................................77

3.3. Формирование столбца начальных условий....................................79

3.4. Порядок обхода изображения.....................................................80

3.5. Алгоритм формирования блока...................................................80

3.6. Алгоритм формирования зоны и введения корректирующих значений...............................................................................82

3.7. Кодирование корректирующих значений.......................................84

3.8. Квантование корректирующих значений........................................85

3.9. Конкатенация блоков................................................................86

3.10. Дополнительные методы повышения степени сжатия......................88

3.11. Оценка ошибки кодирования изображения....................................88

3.12. Оценка степени сжатия изображения...........................................90

3.13. Структура выходного потока (файла) кодера.................................95

3.13.1. Заголовок файла.............................................................96

3.13.2. Таблицы Хаффмена.........................................................97

3.13.3. Начальный столбец.........................................................98

3.13.4. Видеоданные.................................................................99

3.14. Программная реализация процедуры быстрого восстановления изображений.........................................................................100

3.15. Выводы...............................................................................101

4. Экспериментальные исследования характеристик разработанного метода кодирования изображения на основе алгоритмов оптимизированных дельта-преобразований второго порядка............................................103

4.1. Оценка влияния сокращения разрешающей способности цветовых компонент на эффективность кодирования...................................105

4.2. Анализ влияния параметров алгоритмов дельта-модуляции со сглаживанием и с компандированием на качество кодирования и степень сжатия изображений....................................................108

4.3. Анализ влияния параметров, обеспечивающих требуемую точность кодирования, на степень сжатия и верность воспроизведения изображений.......................................................................114

4.4. Анализ влияния дополнительных средств повышения эффективности кодирования на изменение коэффициента сжатия и верности воспроизведения изображений.................................................119

4.5. Сравнительная оценка степени сжатия, верности воспроизведения и быстродействия алгоритмов декодирования по разработанному методу и алгоритму JPEG.......................................................122

4.6. Выводы.............................................................................126

Заключение................................................................................129

Список литературы.......................................................................131

к

Приложения.............................................................................. 136

1. Листинг процедур быстрого восстановления блока...........137

2. Примеры работы алгоритмов кодирования и декодирования изображений...........................................................151

Введение

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

Новые аудио/видео разработки в области связи, телевидения, системы мультимедиа стали возможны только благодаря технологиям цифрового кодирования изображений и видео [37]. Теперь сжатие используется повсеместно для хранения больших объемов видеоданных, будь то одиночные изображения, анимация или видео. Неудивительно, что аппаратные средства и программное обеспечение для компрессии и декомпрессии зачастую становятся частью компьютерной платформы (примером в области персональных компьютеров может служить линия компьютеров Macintosh с операционной системой System 7, включающей так называемое "устройство сжатия", которое предлагает несколько разновидностей компрессии и декомпрессии) [63].

в

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

Различных подходов и алгоритмов кодирования изображений сегодня существует едва ли не столько же, сколько и приложений, и их число продолжает расти. Это объясняется тем, что практически каждая схема кодирования изначально разрабатывается дои определенного класса приложений [62, 65]. Если для одних кодеков (КОдер/ДЕКодер) определяющим фактором является степень сжатия, то в основу других положены методики, обеспечивающие максимальную помехоустойчивость или быстродействие. Более эффективный (и, следовательно, более усложненный) алгоритм сжатия требует большей аппаратной мощности и времени, необходимого для декодирования изображения. Фактически все существующие стандарты кодирования разрабатывались и оптимизировались с учетом возможностей СБИС [80].

Всеобщее признание получили кодеки (КОдер/ДЕКодер) JPEG, MPEG, Indeo, QuickTime и др., ставшие промышленными стандартами. Все они для

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

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

Актуальность темы.

С увеличением объемов обрабатываемой графической информации растут требования к алгоритмам видеокодирования. Если в 70-х годах в качестве исследуемого изображения принимались "картинки" в градациях серого цвета с палитрой из 32-64 цветов, то на рубеже 80-х-90-х годов практически все приложения, ориентированные на работу с графикой, поддерживали так называемые цветовые схемы ТгиеСо1ог (палитра из 16,7 млн. цветов). Изображение размером 600x500 элементов с таким цветовым разрешением занимает порядка 900 000 байт. Естественно, что для обеспечения степени сжатия, приемлемой для хранения и передачи изображений и видеопоследовательностей, потребовалось устранение не только статических,

но и субъективных пространственных и временных избыточностей. При этом важно добиться разумного компромисса между степенью сжатия и качеством кодирования. Современные методики кодирования позволяют достигать степени сжатия в среднем порядка 12-15 раз для статических и 30-50 раз для динамических изображений при достаточно хорошем для визуального восприятия качестве "картинки" [31]. Однако вследствие того, что для уменьшения потерь обычно выполняется перевод изображения в частотную область, трудоемкость таких методов очень высока. Даже одно декодирование видеопоследовательности в каждом из таких форматов сжатия без соответствующей аппаратной поддержки является весьма затруднительным.

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

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

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

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

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

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

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

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

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

Объект исследования.

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

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

Цели и задачи работы.

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

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

- разработка модифицированного алгоритма дельта-преобразований второго порядка для работы с интенсивно изменяющимся сигналом (алгоритм дельта-преобразования со сглаживанием);

- разработка модифицированного алгоритма дельта-преобразований второго порядка с компандированием;

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

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

- разработка программной модели кодирующего устройства;

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

- разработка программной модели быстродействующего декодирующего устройства;

¿г

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

Научные результаты работы:

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

- разработан модифицированный алгоритм дельта-преобразований второго порядка с компандированием;

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

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

- предложен алгоритм коррекции ошибок для обеспечения требуемой точности кодирования;

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

- алгоритм дельта-преобразования второго порядка со сглаживанием;

- алгоритм дельта-преобразования второго порядка с компандированием;

- методика коррекции ошибок кодирования;

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

Практическая ценность работы.

Практическую ценность представляют:

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

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

- методика коррекции ошибок для обеспечения требуемой точности кодирования;

- алгоритм кодирования растровых изображений;

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

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

- програ