Содержание к диссертации
Введение
Глава 1. Сжатие серий изображений (видеопоследовательностей) без потерь 13
1.1. Постановка задачи 13
1.2. Базовые понятия и определения 14
1.3. Обзор подходов к сжатию изображений без потерь 18
1.3.1. Общая схема алгоритмов сжатия без потерь 18
1.3.2. Линейное предиктивное кодирование 21
1.3.3. Нелинейное предиктивное кодирование 23
1.3.4. Адаптивное кодирование 25
1.4. Алгоритмы сжатия изображений без потерь 27
1.4.1. Алгоритм FELICS 27
1.4.2. Алгоритм LOCO-1 29
1.4.3. Алгоритм CALIC 31
1.5. Алгоритмы предиктивного кодирования серий изображений34
1.6. Форматы видеопоследовательностей 38
1.7. Методы сжатия подвижных изображений с потерями 39
1.7.1. История создания стандартов видеосжатия 39
1.7.2. Motion JPEG 40
1.7.3. Стандарты MPEG-1, MPEG-2 и MPEG-4 40
1.8. Анализ известных программных реализаций (кодеков) для сжатия серии изображений без потерь 46
Глава 2. Адаптивный контекстно-зависимый предсказатель 52
2.1. Описание разработанного предсказателя 52
2.2. Исследование разработанного адаптивного контекстно-зависимого предсказателя 57
2.3. Оценка эффективности разработанного адаптивного контекстно-зависимого предсказателя 64
Глава 3. Коррелированность кадров в видеопоследовательностях 67
3.1. Структура алгоритма межкадровой декорреляции 68
3.2. Метод компенсации движения 70
3.3. Вычисление коэффициента корреляции и коэффициентов регрессии смежных контекстов двух соседних кадров 81
3.4. Вычисление коэффициентов корреляции и коэффициентов регрессии смежных онтекстов трёх соседних кадров 83
3.5. Выводы по главе 3 85
Глава 4. Анализ эффективности разработанного метода сжатия без потерь серий изображений 87
4.1. Оценка эффективности адаптивного контекстно-зависимого предсказателя при ' независимом сжатии кадров видеопоследовательностей 88
4.2. Оценка зависимости коэффициента сжатия от задаваемого порога для коэффициента корреляции между смежными контекстами на двух соседних кадрах 89
4.3. Оценка влияния количества пикселов в контексте на эффективность корреляционного подхода 92
4.4. Оценка влияния процедуры компенсации движения на эффективность корреляционного подхода 98
4.5. Оценка эффективности применения корреляционного подхода с использованием двух предыдущих кадров 100
4.6. Оценка эффективности разработанного подхода для сжатия многоспектральных изображений, получаемых в задачах дистанционного зондирования Земли 101
Заключение 106
Литература Ill
Используемые сокращения 120
Приложения 123
- Обзор подходов к сжатию изображений без потерь
- Алгоритмы предиктивного кодирования серий изображений34
- Исследование разработанного адаптивного контекстно-зависимого предсказателя
- Вычисление коэффициента корреляции и коэффициентов регрессии смежных контекстов двух соседних кадров
Введение к работе
Актуальность темы. Еще совсем недавно вопросы сжатия без потерь мультимедийной информации (статические изображения, видео, аудио и т.д.) представляли интерес для узкого круга специалистов, занимающихся научными исследования в области прикладной теории передачи данных. Объемы цифровых носителей информации и невысокая пропускная способность каналов связи требовали использования методов, обеспечивающих высокую степень сжатия, не гарантирующую точного соответствия оригинальных и восстановленных данных и приводящих порой к значительной потере качества.
Для корректной передачи цвета требуется 16 миллионов оттенков (8 бит на каждую из трех цветовых компонент). Таким образом, для описания изображения на экране, содержащего 576 линий по 720 пикселов, требуется -1,0 Мбайт. Учитывая, что частота смены кадров (25 раз в секунду) и продолжительность среднего фильма 1,5 часа, получим -160000 Мбайт. Чтобы записать такой фильм на CD-ROM объемом 700 Мбайт, потребуется сжатие порядка 200 раз. Но с появлением новых более ёмких носителей изменяются и требования к коэффициенту сжатия. Если посчитать во сколько раз потребуется упаковать такой фильм для записи на DVD диск, а это уже 4,7 ГБайта, то получим коэффициент сжатия равный 33. Учитывая, что уже в ходу двусторонние DVD диски (9,4 ГБайта), то требуемый коэффициент сжатия упадет до 16,6. Несложно представить, экстраполируя тенденцию роста емкости носителей информации, конечно при условии сохранения таких темпов, что очень скоро настанет такой момент, когда потребность в высокой степени сжатия (MPEG1, MPEG2, MPEG4, Н.264 и т. п.) [1,2,3] для хранения видеоинформации перестанет доминировать, ведь емкость носителей будет позволять записывать данные вообще без сжатия. При этом, принимая во внимание значительную избыточность, присущую видеоизображениям, задача компактного представления видеоинформации без потерь выйдет на первый план.
Проблема сжатия последовательностей изображений без потерь также возникает в задачах дистанционного зондирования Земли, когда съемка подстилающей поверхности ведётся сразу во многих спектральных диапазонах, результаты которой можно рассматривать, как последовательности схожих друг с другом изображений (многоспектральные изображения), для которых характерна сильная межкадровая зависимость. При сжатии многоспектральных изображений потери недопустимы, поскольку анализ подобных изображений осуществляется с применением сложного математического аппарата.
Существующие стандарты сжатия видеопоследовательностей, а также стандарты и методы сжатия без потерь статических изображений не позволяют эффективно решить задачу сжатия без потерь последовательности изображений, поскольку первые не предусматривают в принципе сжатия без потерь, а вторые не учитывают при сжатии зависимость между смежными кадрами. В свете сказанного выше, задача разработки новых эффективных методов сжатия без потерь серий изображений является актуальной.
Состояние исследований по проблеме
Задача сжатия видеопоследовательностей без потерь, сопряженная с компактным представлением отдельных кадров, восходит к истокам проблематики кодирования источника, пионерский вклад в исследование которой внесли российские и зарубежные ученые Р.Галлагер, М.Вайнбергер, Ш.Ву, Г.Лэнгдон, Р.Райс, В.Ф.Бабкин, Ю.М.Штарьков и др. Необходимо отметить также фундаментальные работы в области теоретико-информационных методов кодирования источника ученых новосибирской школы Р.Е.Кричевского, Б.Я.Рябко, В.К.Трофимова и др. Практические методы сжимающего кодирования изображений разрабатывались в Институте проблем передачи информации РАН Д.С.Лебедевым и Л.ПЯрославским. Большой вклад в теорию и практику сжатия изображений внесли Б.Д.Кудряшов, В.П.Дворкович, Д.С.Ватолин.
В настоящий момент существует целый ряд стандартов и методов, позволяющих сжимать без потерь как полутоновые, так и цветные статические изображения. Среди них стандарты сжатия JPEG (lossless mode) [4], JPEG-LS [5], JPEG2000 [6], схемы сжатия изображений CALIC [7], FELICS [8], PNG [9] и т.д.
Следует заметить, что на текущий момент при наличии стандартов, таких как MPEG2, MPEG4, Н.264, предназначенных для сжатия видеоизображений, допускающих наличие искажений в восстановленных данных, а также выше упомянутых стандартов и методов сжатия статических изображений, не определены стандарты сжатия без потерь для видеоизображений. Тем не менее, имеется целый ряд практических реализаций (кодеков), позволяющих кодировать видеоизображения без потерь, например: HuffYUV1, CorePNG2, Alparysoft Codec3, CamStudio Codec4, PICVideo Lossless JPEG5 и др., в основе которых лежат простые внутрикадровые предсказатели, не учитывающие достаточно высокую межкадровую корреляцию, что сказывается на эффективности кодеков. Под эффективностью кодека следует понимать обеспечиваемый коэффициент сжатия при кодировании видеоизображений.
Характерный средний коэффициент сжатия на серии тестовых видеопоследовательностей лежит в диапазоне от 1,5 до 2,3. Отдельно стоит отметить кодек MSU Lossless Video Codec6, в котором реализован метод сжатия без потерь для видеоизображений, разработанный Д.Ватолиным и Д.Поповым, использующий предсказатель с контекстным моделированием в
совокупности с простой схемой компенсации движения, что позволило получить на серии тестовых видеопоследовательностей коэффициент сжатия 4,499.
Целью диссертационной работы является разработка и исследование методов сжатия серий изображений (видеопоследовательностей) без потерь, позволяющих достичь более высоких коэффициентов сжатия, чем при использовании существующих подходов, без существенного увеличения вычислительных затрат.
Основные задачи диссертационной работы, определяемые поставленной целью, состоят в следующем:
1. Исследование существующих методов сжатия изображений без потерь.
2. Разработка метода уменьшения избыточности изображений на основе наиболее эффективных из существующих при условии ограниченного использования вычислительных ресурсов.
3. Разработка быстрой схемы компенсации движения позволяющей работать в условиях малой контрастности кадров.
4. Разработка и исследование методов сжатия видеопоследовательностей на основе корреляционного подхода с использованием одного или более предшествующих кадров для повышения эффективности метода сокращения избыточности кодируемых данных.
5. Разработка нового метода сжатия серий изображений без потерь на основе вышеуказанных методов и схемы компенсации движения для повышения степени сжатия.
6. Анализ эффективности разработанного метода сжатия на представительных тестовых видеопоследовательностях в сравнении с существующими реализациями.
7. Применение разработанного метода сжатия для компрессии многозональных (многоспектральных) изображений, получаемых в задачах дистанционного зондирования Земли (ДЗЗ).
Методы исследования.
Для проведения исследований в диссертационной работе использовались методы прикладной теории передачи данных, теории кодирования источника, математической статистики. Все разработанные алгоритмы были реализованы программно и исследованы на персональном компьютере с использованием представительных наборов тестовых
видеопоследовательностей.
Научная новизна диссертационной работы заключается в следующем:
1. Разработан новый метод сжатия без потерь для серий изображений на основе предиктивного подхода и компенсации движения с использованием корреляционного подхода.
2. С использованием разработанного метода реализованы алгоритмы сжатия без потерь для серий изображений, учитывающие при сжатии текущего кадра последовательности корреляционные связи смежных контекстов одного и двух предыдущих кадров.
3. Получены экспериментальные оценки коэффициента сжатия, достигаемого с помощью разработанных алгоритмов на представительных тестовых видеопоследовательностях.
4. Найдена зависимость коэффициента сжатия от задаваемого порогового уровня коэффициента корреляции между смежными контекстами двух соседних кадров.
5. Проведена оценка влияния количества пикселов контекста на эффективность корреляционного анализа.
6. Проведена оценка эффективности корреляционного подхода с использованием смежных контекстов трех соседних кадров в целях повышения коэффициента сжатия.
Практическая ценность результатов:
1. Разработанный алгоритм сжатия без потерь для серий изображений « реализован в виде набора Win32 приложений, которые могут быть
использованы для эффективного сжатия мастер-копий фильмов.
2. Разработанные методы могут применяться для эффективного сжатия многоспектральных изображений ДЗЗ, что подтверждается исследованием, проведённым на сериях реальных изображений, полученных с использованием космической съёмочной системы MODIS.
3. Разработанный адаптивный контекстно-зависимый предсказатель может использоваться в алгоритмах сжатия без потерь полутоновых черно-белых и многокомпонентных цветных изображений в качестве метода эффективного уменьшения избыточности.
4. Предложенная в представленной диссертации концепция построения « алгоритмов сжатия без потерь для серий изображений должна найти
применение в системах телевидения высокой четкости (ТВВЧ), системах дистанционной медицины при использовании трехмерных и многомерных изображений.
Апробация и внедрение результатов работы
Разработанный и описанный в диссертационной работе адаптивный контекстно-зависимый предсказатель был использован при разработке и моделировании программно-алгоритмического обеспечения сжатия видеоданных дистанционного зондирования Земли среднего разрешения, проведённых АНО "Космос - Наука и техника" по заказу ФГУП НПП ВНИИЭМ (Договор № 02/01-2005 от 11.01.05), а также в программе сжатия без потерь и с ограниченными потерями полутоновых черно-белых и многокомпонентных цветных изображений с большим числом уровней квантования (8-16 бит на компоненту), предложенной к реализации в рамках федеральной целевой научно-технической программы "Исследования и
разработки по приоритетным направлениям развития науки и техники" на 2002-2006 г. Программа зарегистрирована во ВНТИЦ под регистрационным номером 50200500007.
Основные положения и результаты диссертационной работы докладывались на 11-й Всероссийской конференции «Математические методы распознавания образов ММРО-11», первой и третьей Всероссийских конференциях «Современные проблемы дистанционного зондирования Земли из космоса» в 2003 и 2005 годах, на семинаре "Современные и перспективные разработки и технологии в космическом приборостроении" в 2004 году и опубликованы в сборниках докладов.
Результаты, полученные в рамках федеральной целевой научно-технической программы "Исследования и разработки по приоритетным направлениям развития науки и техники" на 2002-2006 г., Блок 2 - "Поисково-прикладные исследования и разработки", раздел "Информационные технологии", Тема № 32 "Модели и алгоритмы кодирования и сжатия информации", зарегистрированы во ВНТИЦ и оформлены в научно-технические отчеты по теме "Разработка алгоритмов и программных средств неискажающего сжатия и сжатия с ограниченными потерями многокомпонентных изображений" за 2002, 2003 и 2004 годы. Отчет за 2004 год был отмечен премией на конкурсе научных работ ИКИ РАН - в номинации "Лучшие научно-технические отчёты".
Публикации
В целом в печатных изданиях было опубликовано 5 (пять) работ, в которых изложены основные положения диссертации, в их числе одна статья в тематическом сборнике, два доклада и тезисы к двум докладам. Основные положения, выносимые на защиту.
1. Алгоритм контекстно-зависимого адаптивного предсказания, который характеризуется модернизированным блоком классификации контекстов, введением экспериментально определённого набора
весовых коэффициентов для вычисления предсказываемого значения и усовершенствованным механизмом вычисления поправки.
2. Новый алгоритм сжатия без потерь для серий изображений (видеопоследовательностей), основанный на контекстно-зависимом адаптивном предсказателе, с использованием корреляционного подхода в сочетании с модифицированной иерархической схемой компенсации движения.
3. Результаты оценки влияния на коэффициент сжатия серий изображений (видеопоследовательностей) модифицированной иерархической схемы компенсации движения.
4. Применение корреляционного анализа контекстов двух и трех кадров для увеличения эффективности работы контекстно-зависимого адаптивного предсказателя с целью повышения коэффициента сжатия.
Структура работы. Первая глава содержит постановку задачи сжатия серий изображений без потерь. Приводится обзор и анализ известных методов сжатия без потерь одиночных и серий изображений, а также анализ практических реализаций сжатия без потерь видеоизображений. В данном разделе обсуждаются проблемы, возникающие при переходе от сжатия отдельных изображений к сжатию видеопоследовательностей.
Вторая глава посвящена описанию разработанного адаптивного контекстно-зависимого предсказателя и оценке его эффективности.
В третьей главе приводится описание предлагаемого метода межкадровой декорреляции с использованием корреляционного подхода и модифицированной иерархической компенсации движения для увеличения эффективности адаптивного контекстно-зависимого предсказателя.
Четвертая глава посвящена оценке эффективности разработанного метода сжатия без потерь серий изображений на основе предиктивного подхода с применением предложенной схемы межкадровой декорреляции в сочетании с модифицированной иерархической компенсацией движения.
Обзор подходов к сжатию изображений без потерь
Важнейшим и узловым суждением в стремительно развивающемся современном мире стало понятие информации, осмысление которого дает ключ к пониманию многих теоретико-информационных проблем, а также всевозможных прикладных задач, возникающих перед человечеством. В переводе с латыни слово информация означает разъяснение или изложение. Существует несколько определений понятия информации, например, оно трактуется как сведения, не зависящие от формы их представления, или как знание, позволяющее получившему их совершать целенаправленное действие. Выдающийся американский ученый Клод Шеннон, ставший основоположником новой науки - теории информации, опубликовав в 1948 году монографию "Математическая теория связи" [10], где определил информацию как сообщение, которое уменьшает или устраняет неопределённость в выборе одной возможности из нескольких.
Любое сообщение можно представить в виде последовательности нулей и единиц. Эта идея легла в основу понятия бита, как элементарной единицы информации.
Для оценки информативности источника Х={х, р(х)}, содержащего набор независимых сообщений л: с вероятностью р(х), Шеннон ввел понятие энтропии источника.
Энтропию можно интерпретировать как количественную меру априорной неосведомлённости о том, какое из сообщений будет порождено источником или как средние затраты на представление информации в двоичной форме, причем:здесь и далее подразумевается логарифм по основанию другими словами, энтропия всегда меньше, чем число бит, необходимых для представления информации источника в двоичной форме, а равенство имеет место только в том случае, когда все сообщения источника равновероятны.
Цифровое изображение, представляет собой двумерный массив элементов, состоящий из пикселов8, где каждый пиксел описывается в общем случае несколькими числами, характеризующими интенсивность и цветовую принадлежность (яркость и цвет). Основными характеристиками цифрового изображения являются его размеры (количество строк и столбцов), число компонент, число уровней квантования интенсивности по каждой компоненте (рис. 1).многокомпонентные. Однокомпонентные изображения состоят изсовокупности пикселов, характеризующихся интегральным значением интенсивности в некоторой области спектра электромагнитного излучения. Наиболее распространенным представителем этого класса являются черно-белые полутоновые изображения (англ. grayscale), где каждый пиксел представлен интегральным значением яркости во всем видимом диапазоне спектра. Многокомпонентные изображения для каждого пиксела содержат описания интенсивности в нескольких областях спектра. Системы цветового представления
Обычно для описания цветного изображения используют 3 компоненты, которые представляют собой информацию об интенсивности и цвете отдельных пикселов. Самой распространенной схемой представления является система RGB. RGB - система цветопредставления, в которой цвет характеризуется значениями интенсивности красной (R), зеленой (G) и синей (В) компонент. Многокомпонентные изображения обычно рассматриваются в виде совокупности так называемых цветовых плоскостей, каждая из которых содержит описание соответствующей компоненты в виде отдельного полутонового изображения.
Известно, что органы зрения человека более чувствительны к яркости предметов, чем к их цвету. В представлении RGB все три цвета оказываются одинаково значимыми, поэтому сохраняются обычно с одинаковым разрешением, но яркостную составляющую можно отделить от цветовой информации. В представлении YCbCr информация о цвете содержится только в двух компонентах СЪ и Сг, которые могут быть представлены с меньшим разрешением, что позволяет сократить объем информации, требуемый для описания цвета. Компонента Y представляет собой яркостную составляющую и вычисляется по формуле:где к - соответствующий весовой множитель. Цветовые компоненты представляются разностями между компонентами R,G,BK компонентой Y:
Поскольку сумма (Cb + Сг + Cg) является константой, в цветовом представлении YCbCr используются только две цветовые компоненты СЪ и Сг, так как третью компоненту можно вычислить, зная две другие. Прямое и обратное преобразования из RGB представления в YCbCr осуществляется с помощью следующих формул [11]:
Алгоритмы предиктивного кодирования серий изображений34
Ниже будут рассмотрены алгоритмы, учитывающие существующие связи между изображениями при внутрикадровом предсказании, применяемые для сжатия без потерь многоспектральных изображений. Алгоритм LCL-3D
Алгоритм LCL-3D [36] представляет собой простейший предсказатель, использующий корреляцию текущего и предыдущего изображений. На рис. 14 изображены фрагменты контекстов на текущем и предыдущем изображениях, состоящих всего из трёх пикселов.
Оценка предсказанного значения IРу производится по предыдущему пикселуwy с добавлением разности между значениями пикселов рх и wx в предположении, что разность между значениями пикселов и wy на текущем кадре соизмерима с разностью между значениями пикселов рх и wx на предыдущем.
Этот алгоритм использует уже описанный в алгоритме LOCO-I MED-предсказатель, но работающий в плоскостях текущего и предыдущего изображений. Ниже приведено формальное описание алгоритма LOCO-2B [36] на языке псевдо С. Как и в LOCO-I детектируются вертикальные и горизонтальные границы, но уже сразу на двух изображениях, и производится такая же оценка, если границы определить не удается. Поскольку предыдущее изображение считается уже закодированным,результирующая оценка предсказанного значения Ру вычисляется как суммаоценки 1Р и разности 1Рх-1Рх, которая представляет собой погрешность
Если границы не обнаружены, то в качестве предсказанного значения 1р берётся разность между значением пиксела слева wy на текущем изображении и градиентом в горизонтальном направлении на предыдущем »изображении. Алгоритм LOCO-SI
Алгоритм LOCO-SI [36], как и два вышеупомянутых алгоритма, построен на базе LOCO-I. На первом шаге проверяется схожесть текущего и предыдущего изображения. Вводится пороговое значение Т, характеризующее отличие по абсолютной величине пикселов текущего и предыдущего изображений. Если изображения похожи (разность соответствующих пикселов не превосходит значения порога), то используется простой предсказатель из алгоритма LCL-3D, в противном случае алгоритм использует MED-предсказатель.
На основе метода CALIC, описанного выше, для сжатия многоспектральных (многодиапазонных) изображений теми же авторами была предложена схема, получившая название Extended CALIC [37].
На рис. 15 представлены два фрагмента предыдущего и текущего изображения с обозначением пикселов. Контекст текущего пиксела у включает в себя как пикселы окружения в плоскости текущей спектральной составляющей (уі, Уъ—Ут), так и пикселы ближайшей из уже закодированных
Междиапазонный предсказатель используется, если коэффициент корреляции p(X,Y) 0.5, иначе используется внутридиапазонная схема. Для расчета коэффициента корреляции используется соотношение (18).
В общем случае методы сжатия видеопоследовательностей могут работать с широким разнообразием форматов видеокадров, но на практике часто видеоматериал преобразовывают к одному из базисных форматов перед сжатием и передачей. Ниже в табл. 2 приведено семейство распространенных форматов на основе общего промежуточного формата CIF (Common Intermediate Format), а также формат SIF (Standard Interchange Format). Выбор того или иного формата зависит от приложения, в котором осуществляется сжатие. Например, формат 4CIF используется в телевидении, CIF и QCIF в приложениях, обеспечивающих видеоконференции, SQCIF - в мобильном мультимедиа.
В рамках объединенного технического комитета по информационным технологиям JTC1 Международной организации по стандартизации ISO и Международной электротехнической комиссии IEC в январе 1988 года была образована рабочая группа экспертов по кодированию подвижных изображений для разработки стандартов кодирования изображений и звука.
Группа получила официальное наименование ISO/IEC JTC1/SC29/WG11 (11 рабочая группа 29 подкомитета), но в дальнейшем приобрела мировую известность под названием MPEG - Moving Picture Expert Group. Основные направления работ составили: компрессия, обработка и кодовое представление изображения, звука и их комбинаций. Группа MPEG разработала целую серию стандартов для сжатия движущихся изображений и звука, среди них: MPEG-1 (ISO/IEC 11172) - кодирование изображение и звука при скоростях передачи данных до 1.5Мбит/с, MPEG-2 (ISO/IEC 13818) - обобщенное кодирование изображения и звука "телевизионного качества", MPEG-4 (ISO/IEC 14496) - кодирование аудиовизуальных объектов. MPEG-7 (ISOAEC 15938) [38] и MPEG-21 (ISOAEC 21000) [39] - описание содержания объектов мультимедиа.
Алгоритм сжатия MotionJPEG (MJPEG) представляет собой стандартизированный формат записи потока отдельных кадров, каждый из которых сжат независимо от остальных по алгоритму JPEG [4, 15, 40], в котором реализована схема компрессии изображений с потерей качества на основе дискретного косинус - преобразования. При использовании алгоритма сжатия MJPEG средний коэффициент сжатия видеосигнала составляет около 5, а скорость передачи видео с разрешением 720x576 пикселов - до 5 Мбит/с. Независимое сжатие отдельных кадров обеспечивает простоту и высокую скорость доступа к отдельным кадрам при редактировании закодированного видеоматериала.
Стандарт MPEG-1 [1] был разработан для записи видеоизображений на компакт-диски (Video-CD), как альтернатива формату видеозаписи на кассетах VHS (Video Home System). Максимально возможная скорость цифрового потока (-1,5 Мбит/с) была изначально ограничена однократной скоростью стандартного
Исследование разработанного адаптивного контекстно-зависимого предсказателя
На рис. 25 представлена усреднённая гистограмма распределения ошибки предсказания, получаемая на выходе разработанного автором предсказателя, при кодировании представительной серии тестовых изображений. Гистограмма представляет собой спадающее двустороннее экспоненциальное распределение [31], где значение ошибки предсказания может быть как положительной, так и отрицательной величиной.
Перед статистическим кодированием ошибка подвергаетсямодификации, заключающейся в обратимом преобразовании отрицательных значений в положительные за счет расширения диапазона положительных значений ошибок. Модификация происходит по схеме, представленной на рис. 26, где Error - исходная ошибка, Rm - модифицированная ошибка.
На рис. 27а представлена гистограмма с распределением ошибки предсказания в увеличенном масштабе по горизонтальной оси. Сплошная линия на рис. 27 и 27а соответствует экспоненциальному распределению. Как было отмечено в [31] ошибка предсказания аппроксимируется экспоненциальным распределением (непрерывная линия на рис. 27 и 27а). При использовании целочисленного представления ошибки предсказания экспоненциальное распределение сводится к геометрическому.
В работе [52] было показано, что оптимальным для источника с геометрическим распределением является код Голомба. Поэтому в качестве статистического кодера для кодирования ошибки предсказания был использован код на принципе Голомба, разработанный И. Книжным [53].Для исследования свойств разработанного предсказателя на языке С был реализован кодек LLIC (Lossless Image Codec), тестирование которого проводилось на представительной серии полутоновых тестовых изображений из набора Waterloo .
В табл. 5 приведены результаты работы блока анализа контекстов для каждого из тестируемых изображений, показывающие результативность классификации яркостных изменений контекста вблизи предсказываемого пиксела. Столбец "Общий случай" в таблице 5 означает количество контекстов (в процентном отношении), в результате анализа которых не удалось обнаружить каких-либо закономерностей и в этом случае
Сравнительный анализ результатов показывает, что в разработанном автором предсказателе, как в среднем, так и для каждого изображения в отдельности, осуществляется более эффективное разделение контекстов, о чем свидетельствует меньший процент случаев (46,913%), когда идентифицировать яркостные границы не удалось, против 58,798%) при использовании предсказателя схемы CALIC, ставшего прототипом.
На рис. 28 представлена гистограмма распределения величин корректирующей поправки для предсказанного значения пиксела в схеме CALIC. Из гистограммы (рис. 28) видно, что в 50% случаев коррекция не осуществляется, поскольку реальная величина поправки равна нулю, кроме того, налицо явный дисбаланс между количеством поправок величиной +/-1, который можно интерпретировать, как наличие некоторой систематической погрешности.корректирующей поправки для разработанного предсказателя, из которойследует, что в 65% случаев (100% - 35%) корректирующая поправка не равнанулю, что демонстрирует более эффективную работу механизма коррекциипредсказанного значения пиксела, предложенного автором диссертации.
Рис. 29 На усредненной по серии тестовых изображений гистограмме распределения ошибок (рис. 30) видно, что количество безошибочно предсказанных значений пикселов несколько больше (на 0,4%) для разработанного предсказателя LLIC, причем количество положительных ошибок превосходит число отрицательных заметно больше, нежели в схеме CALIC. Такой перевес в сторону положительных ошибок продуцируется намеренно для получения дискретного распределения ошибки, близкого к геометрическому после процедуры модификации ошибок предсказания.Рис. На рис. 31 и 32 представлены гистограммы ошибок, после процедуры модификации, преобразующей отрицательные ошибки в положительные.отображается величина ошибки, по вертикальной оси - количество ошибок в процентах.
Проведенный анализ полученных результатов показывает, что распределение ошибки предсказания при использовании разработанного автором адаптивного контекстно-зависимого предсказателя лишено "ступенчатости", характерной для распределения ошибки, полученного на выходе предсказателя, использованного в схеме CALIC, что особенно заметно на приведённых гистограммах. Этот факт позволяет более эффективно использовать статистическое сжатие на принципе Голомба для кодирования ошибки предсказания.
В табл. 7 приведены коэффициенты сжатия, полученные в результате тестирования кодека LLIC, на основе разработанного предсказателя в сравнении с другими кодеками, среди которых представлены реализации стандартов JPEG-LS и JPEG2000 (lossless mode), реализации схем сжатия CALIC, ERI, а также популярный архиватор общего назначения RAR. Для оценки эффективности разработанного предсказателя в колонке LLIC(C) приведены результаты работы предсказателя (прототипа), использованного в схеме CALIC. На серии из 15 тестовых изображений кодек LLIC показал в среднем на 2% (1,98%) больший коэффициент сжатия, чем кодек LLIC(C).
Вычисление коэффициента корреляции и коэффициентов регрессии смежных контекстов двух соседних кадров
После процедуры компенсации движения скомпенсированный предыдущий кадр наиболее приближен к текущему, и поскольку предполагается, что предыдущий кадр был закодирован ранее, на него можно ссылаться при предсказании очередного пиксела в текущем кадре. Но в некоторых случаях такая ссылка крайне нежелательна, например, когда на текущем кадре появляется объект, которого вообще не было на предыдущем кадре или существующий объект претерпел значительные изменения. Чтобы избежать нежелательных ссылок на предыдущий кадр автором предлагается использовать корреляционный подход для определения степени сходства контекста предсказания на текущем кадре и смежного с ним контекста на предыдущем кадре.
На рис. 47 изображены текущий и предыдущий кадры. Самая темная область представляет текущий кодируемый пиксел, более светлая область, прилегающая к нему - контекст кодируемого пиксела. Точно такая же область, геометрически соответствующая контексту кодируемого пиксела, но на предыдущем кадре - смежный контекст.
Для определения степени "похожести" двух контекстов на соседних кадрах вычисляется коэффициент корреляции между пикселами z. контекстана текущем кадре и пикселами у, контекста на предыдущем кадре по следующей формуле:контекста на предыдущем кадре, IZ/ - интенсивность пикселов контекста натекущем кадре. Если коэффициент корреляции достаточно высок, то для предсказания текущего пиксела /=1 /=1Предсказанное значение интенсивности текущего пиксела 12 будетвычисляться как ргде /_,, - значение интенсивности пиклела, смежного с предсказываемым на
предыдущем кадре. Количество пикселов контекста, задействованных в вычислениях, может варьироваться от 2 до 10, при этом, чем больше пикселов контекста, тем достовернее вычисленный коэффициент корреляции и сложнее вычисления. Оптимальное количество пикселов было установлено экспериментально и описано в разделе 4.3.
Описанный выше подход можно обобщить применительно к трем последовательно идущим кадрам (рис 48). Текущий кадрПиксел, смежный с предсказываемым на предпредыдущем кадре (хр)Предсказываемый текущий пиксел (zp)
Рис. 49 Kzy - коэффициент корреляции между контекстами текущего и предыдущегокадров. К2Х - коэффициент корреляции между контекстами текущего ипредпредыдущего кадров. Коэффициенты Kzy и Kzx вычисляются всоответствии с (30).
Следует заметить, что при практическом использовании (34) нет необходимости каждый раз заново вычислять промежуточные суммы, поскольку при переходе к предсказанию очередного пиксела частично могут быть использованы результаты вычислений для предыдущего пиксела, что значительно ускоряет процедуру предсказания.
В третьей главе была описана разработанная автором структура алгоритма межкадровой декорреляции на основе корреляционного подхода и модифицированной иерархической схемы компенсации движения, позволяющего учитывать зависимость между последовательно идущими кадрами видеопоследовательности при предсказании пикселов в текущем кадре.
Рассмотрены и проанализированы различные стратегии поиска векторов смещения, направленные на снижение вычислительных затрат в процедуре компенсации движения. Основным недостатком стратегий быстрого поиска является то, что найденный блок часто оказывается не самым "подходящим" блоком с точки зрения использованного критерия поиска, поскольку выбранное первоначальное направление может вовсе и не указывать на "лучший" блок, а выбор первичного направления значительно сужает дальнейшую область поиска. Требования к методу компенсации движения при разработке алгоритма сжатия серий изображений без потерь значительно строже. Это объясняется тем, что точность подбора блоков напрямую связана с ошибкой предсказания, от величины которой в свою очередь зависит коэффициент сжатия. В результате анализа была выбрана иерархическая схема компенсации движения со спиральным обходом области поиска. Спиральный обход более трудоемок по сравнению со стратегиями быстрого поиска, но позволяет гарантированно не пропустить "наилучший" блок из области поиска, а иерархическая схема значительно сокращает вычислительные затраты на поиск блока. Автором диссертации предложен подход, повышающий надёжность работы схемы компенсации движения для малоконтрастных блоков.
Для исследования метода компенсации движения была написана модельная программа (использовался язык программирования С), представляющая собой , п32-приложение с интерфейсом, описанным в к диссертационной работе, и библиотека процедур, реализующих различные стратегии поиска векторов смещения.
Описан корреляционный подход, примененный автором дляопределения степени сходства смежных контекстов двух и трех соседнихкадров в видеопоследовательностях. Автором получены ориентированные наиспользование в схеме межкадровой декорреляции формулы двумернойлинейной регрессии, позволяющие вычислять оценку кодируемого пиксела сиспользованием контекстов двух предыдущих кадроввидеопоследовательности.
