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

Р Г Б ОД

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

. 2 7 ОКТ 1993

ГОЛЬЦОВ Александр Геннадьевич

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

Специальность 05.13.13 — Вычислительные машины,

комплексы, системы и сети

АВТОРЕФЕРАТ

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

Москва— 1998

Работа выполнена в Московском энергетическом институте (Техническом Университете)

Научный руководитель к.т.н., доцент Готовский Ю. В. Официальные оппоненты:

д.т.н., профессор МЭИ (ТУ) Климанов Вячеслав Петрович к.т.н., доцент Коробов Александр Евгеньевич

Ведущая организация АООТ "Взлет" Минрадиопрома РФ

Защита состоится 20 ноября 1998 г. в 18.00 часов в аудитории Г-310 на заседании диссертационного Совета К-053.16.09 в Московском энергетическом институте (Техническом Университете)

Отзывы в двух экземплярах, заверенные печатью, направлять по адресу:

111250 Москва, Красноказарменная 14, Ученый Совет МЭИ (ТУ)

С диссертацией можно ознакомиться в библиотеке МЭИ (ТУ) по адресу: Москва, Красноказарменная 13а.

Автореферат разослан октября 1998 г. Ученый секретарь диссертационного совета К-053.16.09

к.т.н., доцент А.Н. Дорошенко

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

АКТУАЛЬНОСТЬ РАБОТЫ. В настоящее время в связи с массовым распространением средств MultiMedia и развитием сети Internet задача повышения эффективности алгоритмов цифровой обработки и сжатия изображений особенно актуальна.

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

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

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

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

ЦЕЛЬЮ ДИССЕРТАЦИОННОЙ РАБОТЫ является разработка и исследование нового метода для сжатия информации полутоновых изображений, позволяющего производить быстрое восстановление изображения.

В соответствии с целью исследования в диссертационной работе были поставлены и решены следующие ЗАДАЧИ:

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

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

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

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

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

6. Исследование особенностей разработанного метода сжатия и сравнение его эффективности с существующими методами.

ОБЪЕКТОМ ИССЛЕДОВАНИЯ диссертационной работы являются цифровые представления полутоновых изображений, методы для их сжатия, потери, вносимые при сжатии и восстановлении и методы количественной оценки искажений.

МЕТОДЫ ИССЛЕДОВАНИЯ. Основные результаты диссертационной работы получены с использованием аппарата обратимых унитарных линейных преобразований, теории информации и кодирования, кластерного анализа, теории вычислительных систем, численных методов регрессионного анализа, статистического анализа изображений и метода экспертных оценок, примененного для оценки качества изображений.

ТЕОРЕТИЧЕСКОЙ И МЕТОДОЛОГИЧЕСКОЙ ОСНОВОЙ диссертационного исследования явились работы зарубежных и отечественных специалистов в области обработки изображений, теории информации, кластерного анализа, вычислительной техники, телевидения, физиологии и медицины.

НА ЗАЩИТУ ВЫНОСЯТСЯ следующие основные результаты диссертационного исследования:

- разработанный и реализованный метод итеративной векторной аппроксимации (ИВА) для сжатия с потерями монохромных и цветных полутоновых изображений, обеспечивающий быстрое восстановление;

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

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

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

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

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

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

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

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

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

ПРАКТИЧЕСКОЕ ЗНАЧЕНИЕ РАБОТЫ. Разработанный метод сжатия может быть применен для сжатия статических полутоновых изображений при поставке их конечному пользователю на носителе или посредством каналов связи. В последнем случае при малой пропускной способности канала связи специфика метода сжатия позволяет реализовать функцию быстрого просмотра всего изображения с постепенным улучшением его качества. Высокая скорость процесса распаковки и его простота также позволяют применять разработанный метод как составную часть методов сжатия цифрового видео.

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

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Предложенный в рамках данной диссертационной работы метод ИВА реализован в виде пакета программ на языке Паскаль для машин 1ВМ РС АТ.

Метод ИВА применен в составе прикладного программного обеспечения фирмы "ИМЕДИС" (аппаратно-программный комплекс "ЭКСПЕРТ-ФОЛЛЬ") для компактного хранения изображений частей тела человека, то есть как метод сжатия неподвижных изображений общего назначения.

ПУБЛИКАЦИИ. По материалам диссертационного исследования опубликованы 3 работы. Делались доклады на международных конференциях "Информационные средства и технологии" в 1996 и 1997 гг.

СТРУКТУРА И ОБЪЕМ РАБОТЫ. Диссертация состоит из введения, пяти разделов, заключения, списка литературы и четырех приложений. Объем основной работы — 171 страница машинописного текста; работа содержит 36 рисунков и 11 таблиц. ,

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

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

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

Проанализированы существующие методы сжатия информации: кодирование повторов, дифференциальное кодирование, энтропийное кодирование (Хаффмена, Шеннона-Фено и арифметическое кодирование), кодирование подстрок (алгоритмы семейства LZ), кодирование с

Ввод

Исходный образ

0

Ц и Компен-

Ф сация

о погреш-

в ностей

а

Цифровая обработка

Преобразование

Вывод

С Передача по р

ж —" линиям связи —>■ с п

а т 1 ' г 1 а к

с — Хранение —>■ в к а

Зрительное восприятие человеком

I

Ой I

Рис.1 Общая схема цифровой обработки полутоновых изображений

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

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

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

ВО ВТОРОМ РАЗДЕЛЕ в общем виде сформулирован метод сжатия ИВА, базирующийся на принципе словарного сжатия. Дана формулировка метода для монохромных и цветных полутоновых изображений. Сжатие цифрового растрового представления изображения предложенным методом происходит следующим образом (рис. 2):

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

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

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

(/-1)-ый образ разности

б) Принцип работы декодера

Рис. 2 Общая схема предлагаемого метода сжатия

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

4) По образу разности вычисляется количественная мера различия между приближаемым и аппроксимирующим образами: Если различия достаточно малы, то выполняется п.5, в противном случае действия пп. ] - 4 выполняются для аппроксимации полученного образа разности.

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

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

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

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

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

- при сохранении данных эталонных доменов выбрасываются четные строки и столбцы в составляющих цветности.

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

к =

1 ^

Тд2М0/У + /И /4]• К2 м0,.[

'т 1 = 1

И

Ч7Г Е^!1 Н.»+—I 41 ■ I «/,] ■ ]1о§2 мо;[

•¿ч* /»1

2С„

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

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

ТРЕТИЙ РАЗДЕЛ посвящен выбору количественного критерия, позволяющего на основании данных образа разности выносить решение о достаточно качественной аппроксимации исходного изображения.

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

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

а) Для монохромных изображений (12 итераций по 32 эталонных домена)

■е-

-е-

Размер доменов

б) Для цветных изображений (12 итераций по 32 эталонных домена) рис. 3 Зависимость коэффициента сжатия от размера доменов

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

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

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

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

1. Искажения не заметны или заметны только при внимательном рассмотрении при

£1 < 0.03-8хг + 0.076-4 + 3.375

2. Качество изображения при возможных искажениях остается хорошим при

ег < 0.016-4* + 0.359-4 + 2.833

3. Качество изображения остается удовлетворительным при

£5<0.019-42 +0.358-4+ 3.618

Здесь £\, Ег, « — среднеквадратическая ошибка представления изображения для достижения качества приближения не хуже заданного,

18.0

16.0 ' 14.0 I-12.0 10.0 8.0 6.0 4.0 2.0 0.0 0.0

♦¿Г

5.0

10.0 Активность

15.0

20.0

а) "Минимально приемлемое" качество приближения

14.0 12.0 10.0 8.0 6.0 4.0 2.0 0.0

► ♦

♦ ♦

♦ ♦♦ 1

! : !

0.0

5.0 10.0

Активность

15.0

20.0

б) Искажения заметны, но качество хорошее

о. \о Ш о

О) X с£ ш а. О

14.0 12.0

10.0 8.0 6.0 4.0 2.0 0.0

0.0

♦ ♦ ♦

*Х*

5.0

10.0

Активность

15.0

20.0

в) Искажения практически не заметны

о?

Рис. 4 Экспериментальные данные, на основании которых предложен критерий для оценки искажений

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

1

5>|-*.*)'

N

где N — количество пикселов в изображении, лг,- и х] — соответствующие пикселы исходного и искаженного изображений;

8.= —-— УI*/ -хшI,

где N— количество пикселов в изображении, х1 и лг,-+1 — последовательные пикселы исходного изображения на пути обхода зигзагом Б длиной N пикселов.

ЧЕТВЕРТЫЙ РАЗДЕЛ посвящен вопросам практической реализации разработанного метода итеративной векторной аппроксимации.

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

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

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

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

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

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

В ПЯТОМ РАЗДЕЛЕ проводится сравнение разработанного метода ИВА со стандартом JPEG по следующим параметрам: время восстановления, время упаковки, ресурсоемкость кодера и декодера, коэффициент сжатия и качество восстановленного изображения (стандарт JPEG или сходные принципы используются в настоящий момент во всех предполагаемых областях применения метода ИВА). Получены данные, свидетельствующие о том, что разработанный метод сжатия при сходном качестве восстановленного изображения и коэффициенте сжатия обеспечивает более быстрое восстановление, чем оптимизированный по быстродействию алгоритм JPEG, и это выигрыш в 2.5 - 3 раза. Выявлено также, что разработанный метод в силу регулярности алгоритма восста-

новления (просто сложение байтовых величин) поддается лучшему, че\ JPEG, ускорению при использовании векторных вычислений на процес сорах Pentium с технологией ММХ. На рис.5 представлены результать сравнения коэффициентов сжатия для различных изображений, дости гаемых при помощи сжатия по JPEG и разработанного метода сжатш при условии наличия малозаметных потерь.

На основании полученных данных делается вывод о возможных областях применения разработанного метода сжатия:

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

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

- в качестве метода для сжатия опорных кадров при сжатии цифрового видео.

В ЗАКЛЮЧЕНИИ перечислены основные результаты проведенных исследований и даны обобщающие выводы.

В ПРИЛОЖЕНИЯХ приведен список терминов, использованных в работе, использованные тестовые изображения и тексты программ на языке Паскаль, реализующих разработанный метод сжатия и пояснительная информация к ним.

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

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

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

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

а) монохромное изображение, домены 8x8

б) монохромное изображение, домены 4x4

Рис. 5 Сравнение результатов сжатия по JPEG "со средними

потерями" и алгоритма ИВА при качестве изображения 1

-го-

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

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

- Предложенный метод сжатия реализован в виде пакета програк-на языке Паскаль для IBM PC AT.

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

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

Основные положения диссертации опубликованы в работах:

1. Гольцов А.Г. Применение методики рекурсивного векторного разбиения для сжатия графической информации // Международная конференция "Информационные средства и технологии" , 1996 г.: тезисы докладов. — т.З, М., 1996. — стр. 179-184.

2. Гольцов А.Г. Метод последовательной векторной аппроксимации для сжатия полутоновых графических образов // Международная конференция "Информационные средства и технологии", 1997 г.: тезисы докладов. —т.З, М., 1997. — стр. 176-182.

3. Гольцов А.Г. Частотный подход к сравнению полутоновых графических образов // Международная конференция "Информационные средства и технологии", 1997 г.: тезисы докладов.—т.З, М., 1997. — стр. 170-175.

МОСКОВСКИМ ЭНЕРГЕТИЧЕСКИМ ИНСТИТУТ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

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

ГОЛЬЦОВ Александр Геннадьевич

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

Специальность 05.13.13 — Вычислительные машины,

комплексы, системы и сети

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

Научный руководитель кандидат технических наук Готовский Ю.В.

Москва 1998

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ....................................................................................................4

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

ГРАФИЧЕСКОЙ ИНФОРМАЦИИ. ПОСТАНОВКА ЗАДАЧИ... 11

1.1. Цифровая обработка графической информации. Место задачи сжатия..........................................................................................11

1.2. Обзор существующих подходов к сжатию графической информации................................................................................. 15

1.3. Критерии качества алгоритмов сжатия......................................41

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

1.5. Выводы по разделу 1....................................................................46

2. ОБЩИЙ ПОДХОД К РЕШЕНИЮ ЗАДАЧИ СЖАТИЯ.....................49

2.1. Формулировка базового алгоритма для сжатия монохромных изображений..................................................................................49

2.2. Обобщение алгорима сжатия для работы с цветными

изображениями..........................................................................57

2.3. Оценка параметров предлагаемого метода сжатия....................62

2.4. Выводы по разделу 2....................................................................68

3. РАЗРАБОТКА КОЛИЧЕСТВЕННОГО КРИТЕРИЯ ДЛЯ ОЦЕНКИ

ИСКАЖЕНИЙ...................................................................................71

3.1. Особенности зрительного восприятия человека, допустимость искажений......................................................................................71

3.2. Используемые критерии качества...............................................82

3.3. Анализ экспериментальных данных и выбор количественного критерия.........................................................................................86

3.4. Выводы по разделу 3....................................................................96

4. РЕАЛИЗАЦИЯ АЛГОРИТМА СЖАТИЯ............................................98

4.1. Разработка алгоритма формирования словаря монохромных доменов..........................................................................................98

4.2. Алгоритм формирования словаря для цветных доменов.........109

4.3. Разработка метода дополнительного сжатия без потерь на завершающем этапе работы алгоритма......................................111

4.4. Разработка способа борьбы с искажениями

из-за переполнения.......................................................................120

4.5. Разработка способа борьбы с искажениями на границах доменов.........................................................................................126

4.6. Выбор значений коэффициентов и величин, влияющих на

качество работы алгоритма.........................................................128

4.7. Выводы по разделу 4...................................................................133

5. ОБЛАСТЬ ПРИМЕНЕНИЯ РАЗРАБОТАННОГО

МЕТОДА СЖАТИЯ.........................................................................136

5.1. Сравнение результатов работы разработанного алгоритма со стандартом JPEG.........................................................................136

5.2. Область применения...................................................................153

5.3 Выводы по разделу 5...................................................................155

ЗАКЛЮЧЕНИЕ..........................................................................................157

ЛИТЕРАТУРА............................................................................................164

ПРИЛОЖЕНИЯ.........................................................................................172

ВВЕДЕНИЕ

Актуальность работы. Современные аппаратные и программные средства компьютеров способны обеспечить цифровое представление (ввод, хранение, обработку и воспроизведение) цветных изображений телевизионного и фотографического качества (полутоновой графической информации). В настояще время в связи с массовым распространением средств МиШМесНа задача повышения эффективности алгоритмов цифровой обработки изображений особенно актуальна, о чем свидетельствует множество публикаций, посвященных этому вопросу [1 - 23, 25, 31 - 34, 36 - 42, 44].

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

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

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

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

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

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

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

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

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

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

- разработать алгоритмы, реализующие предлагаемый метод сжатия;

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

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

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

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

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

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

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

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

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

Практическая ценность. Разработанный метод упаковки может применяться для сжатия статических образов (фотографий) или как составная часть процесса сжатия цифрового видео. В частности, он в ряде случаев может заменить алгоритм JPEG, применяемый в цифровом видео стандарта MPEG для сжатия "опорных кадров" [18]. При использовании данного метода для сжатия фотографических изображений может быть достигнут эффект последовательного восстановления образа с изначально низким качеством изображения и дальнейшим улучшением качества по мере поступления данных, что может оказаться полезным, например, при работе в компьютерной сети с использованием медленного канала передачи данных для быстрого ознакомительного просмотра графических данных, локализованных на удаленном сервере.

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

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

Аппробация работы и публикации. Результаты работы докладывались на двух научно-технических конференциях. По теме диссертационной работы опубликовано 3 статьи [28 - 30]. Реализующий разработанный метод пакет программ успешно используется в составе коммерческих программных продуктов.

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

Основной текст содержит 171 страницу, в том числе 8 страниц — список использованной литературы, 36 рисунков и 11 таблиц,. Приложения к диссертации выполнены на 74 страницах.

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

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

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

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

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

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

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

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

1. АНАЛИЗ СУЩЕСТВУЮЩИХ ПОДХОДОВ К СЖАТИЮ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ. ПОСТАНОВКА ЗАДАЧИ

1.1. Цифровая обработка графической информации и место задачи сжатия

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

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

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

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

Исходный образ

Цифровая обработка

Преобразование

с

ж

а

т

н

е

Передача по линиям связи

Хранение

Зрительное восприятие человеком

Преобразование в формат устройства вывода

р

а

с

п

а

к

о

в

к

а

Вывод

[

к л

!

£

Воспроизведенный образ

Рис.1.1 Общая схема цифровой обработки полутоновых изображений

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

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

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