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

Министерство путей сообщения РФ Московский государственный университет путей сообщения (МИИТ)

'ДК 621.391 (2010) На правах рукописи

По Туан Ань

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

05.13.17. Теоретические основы информатики

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

Научный руководитель: доцонт Поволоцкий Ф.Б.

Москва 1996 г.

Работа выполнена в Московском государственном университете пу сообщения (МИИТо).

Научный руководитель - кандидат технических наук,

доцант Ф.Б. Ловолоцкий.

Официальные оппоненты - доктор техничэских наук,

профессор A.D. Шилейко; доктор физико-математических наук Нгуен Минь Хай.

Ведущая организация - Научко-иссладоаательский институт железнодорожной астоматизеции (НИИЖА).

Защита состоится « ^ фИм?• 1597г. п _час. на засада!

специализированного совета К 114.05.10 в Московском государствен! университете путей сообщения по адресу:

101475, ГСП, Москва А-55, ул. Образцова, 1S. Телефон совета 281-61-01.

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

Автореферат разослан

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

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

диссертационного совета Ю.А. Хохлов

Общая характеристика работы

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

Рассмотрим цифровое изображение как матрицу пикселов размером N х N. Для монохромного изображения каждый пиксел имеет 256 градаций яркости и поэтому представляется одним байтом. Для цветного изображения каждый пиксел представляется 3 байтами, каждый из которых является градацией яркости одного Из трех основных цветов - красный, синий и голубой.

Для хранения цветного изображения размером 640x480 требуется 921600 байтов. Для передачи видео сигнала (30 кадров о секунду) конечное оборудование и канал должны обладать пропускной способностью 2^1 мегабит в секунду. Это значение существенно превышает способность традиционных каналов связи. С обработкой такого потока информации в реальном времени не справиться и конечное вычислительно« оборудование.

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

Цель м задачи исследования

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

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

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

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

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

- Выбор и реализации подходящего механизма для устранения этой избыточности;

- Комбинирование существующих методов с разработанным алгоритмом и полная его реализация,

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

Новизна

В диссертации впервые:

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

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

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

Научная значимость

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

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

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

Апробации

Основные положения диссертации были доложены и получили одобрение на научно-технической конференции молодых ученых и аспирантов МИИТа "Неделя науки" в 1995 году и на заседаниях кафедры "Математическое обеспечение АСУ" в 1395-1996 годах.

Положения, которые пыносятсп на защиту

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

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

- Разработка метода обучения набора нейронных сетей.

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

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

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

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

- Элементы теории гильбертовых пространств;

- Элементы кластерного анализа;

- Теория паралельно-распределенной обработки и нейронных сетей.

Ссстаз к структура диссертации

Диссертация состоит из введения, 6 глав, заключения и списка кс,пользованной литературы. Содержание работы изложено на 105 страниц машинного текста и содержит 57 рисунков и 7 таблиц Список использованной литературы включает 25 наименований.

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

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

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

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

= -----,<!В,

. К*"*,)' ()

¡-1

где К- число отсчетов дискретного сигнала х (или число пикселов в исходном изображении), 255 является максимально возможным значением отсчетов (или число градаций яркости пикселов), х - вс&стэновлонный сигнал после сжатия сигнала х. РЗМгЧ измеряется о децибелах.

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

-7В данной работа применяется методика разложения на разные мпс|0т:'г,:0 компоненты, так как она хорошо приспособлена к человеческой система гроя-.-я. Излагается суть метода лапласовой пирамиды и его усовершенстсосамио -преобразование малых волн (ПМВ - wavelet transform). Затем раскрывается номзна работы - развитие ПМВ в направление прогнозирования деталей на разных уроомях разрешения.

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

Разрешение - это число точек сканирования на одну единицу длины. Для дискретного одномерного сигнала ,А)( представляемого последовательностью отсчетов, его аппроксимация на разрешении г построена как выборочная последовательность отсчетов с шагом о =1/г, Например если:

А,={а,,аг,аз,а4,а5.....) (2)

И и =2, то

A1(J={(a,+a2)/2,(a3+a,)/2.....}. (3)

На самом дела А„3 получается из А, с помощью низкочастотной фильтрации, реально занимающейся локальным усреднением с уменьшенной частотой взятия отсчетов (в данном случае уменьшим интерьал дискретизации в двое). Ясно, что А2 имеет число отсчетов на половину меньшэ. Для ее отображения а исходном размере можно поступить таким образом: включаем отсчеты между существующими, получая новый вектор следующего вида: А„={(а,+а2)/2, (а,+а2+аз+а,)/2, (а3+а<)/2,...}.

Информационная разность между А и Ам определяется как Dvj^-A;,,. (5)

Ясно, что Dv2 имеет такое число отсчетов как А, и из А,,2 и D(/j можно точно восстановить At. С математической точки зрения:

А, (п) = (А, (п) * 0, (п / г)) = j (A,(t)0,(n/r-t))dt, (G)

о

где D- набор отсчзтов сигнала Ai, а 8,(х) называется фильтром, ширина полосы пропускания.частог которого равна r-1/o , в нашем случае:

|г, если х= 0.1.....Ш-1

(7)

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

А,м(п) = (А,*6,(п/г) с г=1/4; (8)

и Онл=Аю-А'у,. (9)

А,« имеет четверть и 0\н имеет половину числа отсчетов по сравнению с А). Если продолжать этот процесс I раз, т.е. если спроецировать А, на семейство

функции 0,(п), построенное при изменении г=2"*, ¡=1.....1 то получается

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

исходный сигнал А». Число отсчетов для представления А,, и серии О, равно:

{(И+М2+Ы/4+....+Ы/21)= 2№ (10)

Описан, ,ое представление (его назыьлот лапласовой пирамидой) требует количество отсчетов вдвое большим по сравнению с исходным сигналом. Это из-за. того, что семейство функций 0,(п / г - 1) в формуле (6) не является ортогональным базисом и поэтому между О, имеется корреляция, т.е. избыточность представления. Часто конструируют 9,(п / г - 0 так, чтобы ее первая производная была непрерывна и при изменении п составлялся ортогональный базис в пространстве 1-2{1Ч) V,. Тогда говорят, что А, получается как проекция А, на пространство V,, а й, -проекция на ортогональное допопнение и, к V, в пространстве (или Ч/,-г= V,® Ц). Другими словами последовательность О, получается как проекции Л, на ортогональный базис пространства и,. Предлагается, что этот Зазис состоит из функций (¡>((п/г-0. Для конструирования и, исходя из V, была построена формула связи между 8 и ч>. Обычно исследователи начинают с 8 (х) как один сплайн, затем ортогонализуют б^п1тЛ).

Заметим из (8) и (9), что для получения А* и 04 вместо применения 0,(п) и (¡>,(п) с г-1/4 к исходному сигналу А1 мы можем применить их к А2 с г=1/2. Таким

збразом, с помощью двух функции 0Дп) и ^Дп) о г-1/2 можно получеть всю гаследоватеяьность декомпозиции.

Прослеживается аналогия описанного процесса с процессом фильтрации в >бработке сигналов, поэтому эти функции 0„г(п) и ©1;г(п) называются функциями >?кяша низкочастотного и высокочастотного фильтров соответственно. Описанная :хема называется декомпозицией на разные уровни разрешения с помощью так «азываемого преобразования малых волн (графики функций & и <р имеют вид лапой волны) или ПМ8.

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

Ниже приведен пример разложения изображения "Lena", которое часто использовать для иллюстрации и тестирования в работах в области кодирования «ображений:

5ис.1. Оригшал woe тобргшеияе "Lena"

ввртикаяьно©

суб изображение

горизонтальное диагональное субизображение субизобрашни©

Рис.2. Иллюстрация разложения изображения Тепа' на одно низкочастотное (низшее разрешение) три высокочастотных (детали на высшем разрешений} суЗизабражевий

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

ГМВ позволяет концентрировать энергию изображения на субиаображени» низкого разрешения Мы используем ПМВ. а не преобразование Фурье (РТ), так ка! ПМВ позволяет не только измерять меру нерегулярности 8 сигнале (величии? частотного компонента), иа и фиксировать местоположение этих нерегуяярностей Иначе говоря, ПМВ дает хорошую локализацию нерегулярности и е пространственном, и в частотном доменах.

1. Декомпозиция исходного изображения на несколько субизображений на разных уровнях разрешения.

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

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

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

вектору, у

Рис.3. Иллюстрация механизма работы векторного квантования

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

В настоящее Бремя разработано большое число алгоритмов векторного квантования. Учитывается'также характеристика распределения коэффициентов ПМ8. Ниже на рис.4 приведена схема сжатия/восстановления на базе прзобраэооания малых волн и векторного квантования его коэффициентов (ПМВ+ВК): , '

ИзоС^д

Рис.4. Схема сжатия-восстановления на основе ПМВ+ВК

3) Ноаизна работы: алгоритм прогнозирования структуры

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

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

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

- Повысить коэффициенты сжатия (так как надо квантовать только значимые коэффициенты, число которых сравнимо малое);

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

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

сохранения матрицы структур. Решение этой задачи является ключевым моментом для данной диссертации.

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

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

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

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

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

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

Рис.5 Предсказание структуры субиэображения высшего разрешения из структур субизображенад следующего низшего разрешения

Для выбора оптимального отображения используем в качестве ошибки предсказания расстояние Хемминга:

>«1

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

Мы называем метод предсказания матриц струк.ур на осново выдвинутой гипотезы векторным предсказанием. Он по основной идее аналогичен известному алгоритму адаптивного предсказания АДИКМ, только имеет дело но с локальными текстурами, а с компонентами текстур на разных уровнях разрешения.

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

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

Рис.6. Принципиальная блок-схема формирования словаря отображений

Максимальное число отображений N определяется экспериментальным путегч?. По мере подачи на систему обучающей последовательности число отображений возрастает, но с убывающей скоростью. 8 рамках обучения 40 фотографий размером 480*360 это число, начиная с 260-ого, возрастает довольно

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

Всем алгоритмам предсказания присуще накопление ошибок, ошиб; предсказания 8 из А при фиксированном предсказании с большой вероятность усиливает ошибку предсказания С из В. Есдо, возникает ошибка, ее мсв» устранить, лиигь перезапустив процесс предсказания.

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

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

Каждый нейрон в сети имеет следующий механизм работы'

Рис.?. Структура нейрона; а,.....а„ - входные сигналы, Ь| - выходной сигнал, щ„ ., щ - веа

связей, 0,- порог

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

Рис.8. График одной из популярных сигмоидальных функций

Каждая применяемая нейронная сеть имеет следующую двухуровневую

организацию:

Входной слоЛ

Метрик преобразования

винщиьй емгор и! илгриф/ структур нюкого разрешение

протоэ^оаашйБ*« иый *ектор иэ матрьшм структур высокого раэреиения

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

Это сеть с прямым вызовом, т.е. сигналы идут только в направление из входного , выходному слою. Нейроны входного слоя предназначены только для подачи сигналов а сеть, т.е. их функции активности Цх)=х Каждый нейрон входного слоя полностью связан со всеми нейронами выходного слоя и наоборот. Матрица структур на более низком уровне раздс тется на векторы (блоки) А размерами п-64, соответственно матрица структур на высшем уровне разделен на векторы В размерами 4*п=256. Эти цифры соответствуют числу нейролоо во входном и выходном слоях сети.

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

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

Следующая схема реализует процесс на рисунке 6:

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

Приводим конкретную реализацию бло<а обучения с обратным распространением ошибок в схеме на рис 10.'С одной стороны, она упрошена по

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

В этом случае вторую пару считаем принадлежащей другому отображению, и поэтому надо подать ее на обучение в другую (или новую) нейронную сеть.

Мы модифицируем алгоритм обратного распространения для обучения одной сети (формирования одного отображения) запоминать новой пары (А", В") векторов, учитывая вышесказанные замечания:

а/ Инициализация: Фиксируется ошибка из предыдущей итерации Р> <^Егг=0. 61 Для каждой пары векторов (А*, В*), запомненных в обучающем наборе сети и новой пары (А", В") выполняются следующие действия:

1) Вызов сети для вычисления значения ¡-го компонента выходного вектора:

где \л/ы - весы связи между И-ым входным и ¡-ым выходным нейронами, ^ порог для ¡-го выходного нейрона, {(х)=(1+е")'' логистическая функция.

Отметим, что входной и выходной векторы бинарны, т.е. а„е{0,1),и f можно извлечь из таблицы, созданной кусочно-линейной интерполяцией. Поэтому для вычисления высшого выражения нужна только операция сложения.

2) Вычисление рассогласования к жду вычисленным и ожидаемым выходами

М, =.«</,,

где И=1,...,п; ¡=1.....4*п.

в/ Вычислить глобальную ошибк" С1оЬа1Егг=гпах(|ь;1> - Ь,|) при всех I и всех плргх (А*,В') и (А",Вк).

<1| = Ь1(1-Ь1КЬ1(1<)-Ъ1),

'де Ь,» - ожидаемое значение ¡-го компонента выходного вектора. 3) Корректировка весов связи и порогов:

гI Если GlobalErr<0.49999 то выходить с положительным ответом.

Иначе если разница GlobalErr - PrevErr < определенного порога (в программе реализации этот порог равен 10'®), то считается, что текущая пара (А1*, Вк) не может быть запомнена и надо еыйти с отрицательным ответом!

/ Присвоить PrevErr= GlobalErr и переходить в шаг б/.

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

Ниже приводим таблицы ошибок предсказания структур субизображений для изображения "Lena". Результаты в таблице 1 получэны после обучения 130 нейронных сетей с помощью 15 тестовых изображений размером 480x360.

Ошибки предсказания для изображения 'Lena* Таблица 1

Уровни Ориентации

разрешения Вертикальная Горизонтальная Диагональная

Уровень а =18.32 а = 18.09 а =20.57

разрешения 0

(самый высокий) Р = 7.82 Р =7.35 Р =5.31

Уровень 1 а = 12.93 а = 13.33 а = 14.66

р = 5.29 Р =5.57 Р =4.72

Уровень 2 а =5.17 а =4.92 а = 5.20

Р =2.54 р =2.11 р =3.54

Уровень 3 а =2.45 а =2.74 а =3.68

0 = 0.72 Р =0.90 р = 1.81 ■

Уровень 4 а =0.83 а =0.63 а = 1.39

р=0.45 р =0.39 р =0.76

После обучения с помощью еще других 25 тестовых изображений число нейронных сетей возрзсло до' 293,-'из которых было, исключено -37; 'сетёй .с наименьшими! размерами обучающихся наборов. В конечном счёте фиксируется

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

Ошибки предскозания "Lena" с помощью 250 нейронных сетей Таблица 2

Уровни Ориентации

разрешения Вертикальная Горизонтальная Диагональная

Уровень а = 5.05 а =2.50 а г, 13.20

разрешения 0

(самый высокий) Р =0.2 Р =0.04 Р =6.0

Уоовонь 1 а =1.1 а =4.7) а = 1 34

р =0 01 Р =0.11 Р = 0.U3

УроЕ нь 2 а = 0.52 а =3.24 а = 1.72

Р =2.53 р =0.40 р =0.06

Уровень 3 а =4.9 а =3.01 а =0 24

р =0.43 р =0.18 р =0.33

Уровень 4 а =0.03 а =0.21 а = 7 04

р = 0.05 р =2.73 Р = 1.10

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

Нижо привод сна схема кодирования - декодирования (рис. 11):

Рис.11. Схема сжатия-восстаноеления изобпажения по разработанному алгоритму ПМВ+векторного продсказания+ВК. ' ■ •

Алгоритм работы блока предсказания в этой схеме приведен на рисунке 12.

Рис 12 Схема функционирования блока предсказания

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

Предлагаемый алгоритм при наборе 20 тестовых изображений дает коэффициенты сжатия в диапазоне от 60:1 до 166:1, т.е. выше по сравнению со стандартом JPEG (на основе ДСП) - от 10:1 до 30:1 и алгоритмом ПМВ+ВК - от 40:1 до 90.1 при одинаковом качестве восстановления (PSRN в пределе 28-30dB). Для цветных изображений коэффициенты сжатия гыше монохромных, так как мы еще учитываем цветовую чувствительность человеческого зрения Для сравнения используются последние опубликованные результаты, а также реализаций стандарта JPEG и алгоритма ПМВ+ВК в пакете Coreî PhotoPair.t 6.0.

Этот алгоритм эмпирический. Он основан на гипотезе, которая теоретически еще не обоснована, поэтому есть возможность, что для некоторых изображений он работает хуже. Его основной недостаток при реализации - больше время сжатия (примерно 20-40 минут, в зависимости-от размера изображения, на персональном компьютере Pentium-;! 00 .'в ср'е^е операционной 'сйстйцы. '"MS-DQS: 640

Ï

3»ломимаТк» M, как основу для предсьвгпни ч матриц мру* тур С.гк!-дуюа^го разре м я_

£

Duxoa

торатионой памяти с реализацией структур нейронный сетей на жестком диске), по равнению с JPEG (несколько секунд) и ПМВ+ВК (ст половины до 2 минут). Это юзнихяст из-за того, что для каждого С лека субизображения нужен полный поиск из вножоства нейронных сетей той, которая оптимально предсказывает его. Сложность 1ычисления при этом поиска - полиномиальная 0(пг), где п - размер изображений. 1роцесс распаковки идет быстрее и ергоним по времони с методом ПМВ+ВК примерно одна минута), но медленнее JPEG (несколько секунд). Процедуру сжатия ложно ускорить если^аппаратно реализовать найроннкэ сети.

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

Заключенно

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

1. На основа анализа современных методоа сжатия цифрог.ых изображений

здолзн зьтаод о том, что асе они по сути имеют дело со статистической

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

случайный процесс первого порядка.

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

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

А. Разработан пакет программ сжатия/оосстанооления изображений на основе мультирезолюциенной декомпозиции, нейронных сетей и векторного квантсоания. По основным характеристикам предложенный алгоритм превосходит алгоритм стандарта JPEG и другие современные алгоритмы на 50-100%. Этот пакет можно

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

Публикации

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

1. Ле Туан Ань. Лодполосное кодирование изображения и искусственная нейронная сеть. М.: МИИТ, Столетний юбилейный выпуск, 1996.

2. Ле Туан Ань. Сжатие цифровых изображений с помощью мультичастотной декомпозиции и прогнозирования текстур на основе нейронных сетей. Сборник трудов под редакцией Шилейко А.В., М.:МИИТ, 1996.

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

Ле Туан Ань

05.13.17. Теоретические основы информатики

Сдано в набор Л 6. /<2.96.

Формат бумаги 60x84/16. Объем 1,6 п.л. Заказ 65/. Тираж 80 экз.

Подписано к печати 26. {¿Жб.

Типография МИИТа. Москва, ул. Образцова, 15.

т они ¿ г

i?o