Разработка методов сжатия без потерь для серий изображений тема диссертации и автореферата по ВАК РФ 05.12.04, кандидат технических наук Хрекин, Константин Евгеньевич

• Хрекин, Константин Евгеньевич
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Хрекин, Константин Евгеньевич

Введение.

Глава 1. Сжатие серий изображений (видеопоследовательностей) без потерь.

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

1.2. Базовые понятия и определения.

1.3. Обзор подходов к сжатию изображений без потерь.

1.3.1. Общая схема алгоритмов сжатия без потерь.

1.3.2. Линейное предиктивное кодирование.

1.3.3. Нелинейное предиктивное кодирование.

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

1.4. Алгоритмы сжатия изображений без потерь.

1.4.1. Алгоритм FELICS.

1.4.2. Алгоритм LOCO-1.

1.4.3. Алгоритм CALIC.

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

1.6. Форматы видеопоследовательностей.

1.7. Методы сжатия подвижных изображений с потерями.

1.7.1. История создания стандартов видеосжатия.

1.7.2. Motion JPEG.

1.7.3. Стандарты MPEG-1, MPEG-2 и MPEG-4.

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

1.9. Выводы по главе 1.

Глава 2. Адаптивный контекстно-зависимый предсказатель. щ 2.1. Описание разработанного предсказателя.

2.2. Исследование разработанного адаптивного контекстнозависимого предсказателя.

2.3. Оценка эффективности разработанного адаптивного контекстно-зависимого предсказателя.

2.4. Выводы по главе 2.

Глава 3. Коррелированность кадров в видеопоследовательностях.

3.1. Структура алгоритма межкадровой декорреляции.

3.2. Метод компенсации движения.

3.3. Вычисление коэффициента корреляции и коэффициентов регрессии смежных контекстов двух соседних кадров.

3.4. Вычисление коэффициентов корреляции и коэффициентов регрессии смежных контекстов трёх соседних кадров.

3.5. Выводы по главе 3.

Глава 4. Анализ эффективности разработанного метода сжатия без потерь серий изображений.

4.1. Оценка эффективности адаптивного контекстно-зависимого предсказателя при ' независимом сжатии кадров видеопоследовательностей.

4.2. Оценка зависимости коэффициента сжатия от задаваемого порога для коэффициента корреляции между смежными контекстами на двух соседних кадрах.

4.3. Оценка влияния количества пикселов в контексте на эффективность корреляционного подхода.

4.4. Оценка влияния процедуры компенсации движения на эффективность корреляционного подхода.

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

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

4.7. Выводы по главе 4.

Введение диссертации (часть автореферата) на тему «Разработка методов сжатия без потерь для серий изображений»

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

Для корректной передачи цвета требуется 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, в котором реализован метод сжатия без потерь для видеоизображений, разработанный Д.Ватолиным и Д.Поповым, использующий предсказатель с контекстным моделированием в

1 http://neuron2.net/www.math.berkelev.edu/benrg/

2 http://corepng.corecodec.org/

3 http://vvvvvv.alparvsoft.com/products.php

4 http://vvvvvv.free-codecs.com/download/CamStudio Lossless Codec.htm

3 http://wwvv.pegasusimaging.com/picvideolossless.htm

6 http://www.compression.ru/video/ls-codec/ совокупности с простой схемой компенсации движения, что позволило получить на серии тестовых видеопоследовательностей коэффициент сжатия 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. Применение корреляционного анализа контекстов двух и трех кадров для увеличения эффективности работы контекстно-зависимого адаптивного предсказателя с целью повышения коэффициента сжатия.

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

Вторая глава посвящена описанию разработанного адаптивного контекстно-зависимого предсказателя и оценке его эффективности.

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

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

Заключение диссертации по теме «Радиотехника, в том числе системы и устройства телевидения», Хрекин, Константин Евгеньевич

4.7. Выводы по главе 4

В четвёртой главе приведены результаты моделирования разработанных автором методов для сжатия серий изображений без потерь. Разработанные методы реализованы на языке С в виде модельной программы LLVC и библиотеки кодеков.

В кодеке LLVC-1 реализован метод, в котором последовательность кадров рассматривается как набор независимых изображений, сжимаемых с использованием разработанного автором адаптивного контекстно-зависимого предсказателя. Средний коэффициент сжатия на тестовых последовательностях составил 3,882 при скорости кодирования 2,887 МБайт/с. Это наилучший результат по коэффициенту сжатия среди тестируемых наиболее распространенных кодеков (табл. 3), не использующих для сжатия зависимость между кадрами последовательности. Полученная скорость кодирования позволяет уже сейчас сжимать без потерь видеопоследовательности с размером кадра формата CIF в реальном масштабе времени на современном оборудовании.

В кодеке LLVC-2 реализована схема, использующая корреляционный подход для учёта межкадровой зависимости между текущим и предыдущим кадрами в сочетании с процедурой компенсации движения. В результате исследования разработанного автором метода выявлены зависимости эффективности сжатия от порогового уровня коэффициента корреляции смежных контекстов и от количества пикселов, образующих контекст. Максимум среднего коэффициента сжатия достигается при значениях порога Т, лежащего в диапазоне [0,5; 0,6], и при 12 пикселах контекста. Было установлено, что применение компенсации движения в сочетании с процедурой межкадровой декорреляции позволяет увеличить коэффициент сжатия в среднем на 9,25%.

Средний коэффициент сжатия на серии тестовых последовательностей для кодека LLVC-2 составил 4,854, что на 7,89% лучше результатов, продемонстрированных кодеком MSU, при этом по скорости кодирования разработанный кодек выигрывает более чем на 70%.

В кодеке LLVC-3 реализована схема, использующая корреляционный подход для учёта межкадровой зависимости между текущим и двумя предыдущими кадрами в сочетании с процедурой компенсации движения. По результатам экспериментов применение такой схемы позволяет дополнительно увеличить коэффициент сжатия в среднем на 1,87% по сравнению с использованием одного предыдущего кадра, но при этом сложность вычислений возрастает практически вдвое.

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

Заключение

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

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

Для сравнительной оценки эффективности разработанного предсказателя реализован кодек LLIC(C) на основе предсказателя (прототипа), использованного в схеме CALIC, и кодек LLIC, в котором применен разработанный автором предсказатель. Для сопоставимости результатов сжатия в обоих кодеках использовался один и тот же статистический кодер. Сравнение проводилось на представительной серии тестовых изображений. Кодек LLIC продемонстрировал в среднем на ~2% больший коэффициент сжатия в сравнении с кодеком LLIC(C), проигрывая по скорости всего -4%. Полученный выигрыш демонстрирует эффективность предложенных модификаций предсказателя.

Следует заметить, что значительно более сложные в вычислительном отношении кодеры, например, BMF при тех же условиях тестирования обеспечивает в среднем на ~6% больший коэффициент сжатия при скорости кодирования, в 3,5 раза меньшей, чем разработанный кодек.

Основные отличительные особенности разработанного предсказателя:

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

2. Число контекстов при классификации увеличено до 2047.

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

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

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

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

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

Разработанные автором методы сжатия серий изображений без потерь методы реализованы на языке С в виде модельной программы LLVC и библиотеки кодеков.

В кодеке LLVC-1 реализован метод, в котором последовательность кадров рассматривается как набор независимых изображений, сжимаемых с использованием разработанного автором адаптивного контекстно-зависимого предсказателя. Средний коэффициент сжатия на тестовых последовательностях составил 3,882 при скорости кодирования 2,887МБайт/с. Это наилучший результат по коэффициенту сжатия среди тестируемых наиболее распространенных кодеков, не использующих для сжатия зависимость между кадрами последовательности. Полученная скорость кодирования позволяет уже сейчас сжимать без потерь видеопоследовательности с размером кадра формата CIF в реальном масштабе времени на современном оборудовании.

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

Максимум среднего коэффициента сжатия достигается при значениях порога Т, лежащего в диапазоне [0,5; 0,6], и при 12 пикселах контекста. Было установлено, что применение компенсации движения в сочетании с процедурой межкадровой декорреляции позволяет увеличить коэффициент сжатия в среднем на 9,25%.

Средний коэффициент сжатия на серии тестовых последовательностей для кодека LLVC-2 составил 4,854, что на 7,89% лучше результатов, продемонстрированных кодеком MSU, при этом по скорости кодирования разработанный кодек выигрывает более чем на 70%.

В кодеке LLVC-3 реализована схема, использующая корреляционный подход для учёта межкадровой зависимости между текущим и двумя предыдущими кадрами в сочетании с процедурой компенсации движения. По результатам экспериментов применение такой схемы позволяет дополнительно увеличить коэффициент сжатия в среднем на 1,87% по сравнению с использованием одного предыдущего кадра, но при этом сложность вычислений возрастает практически вдвое.

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Хрекин, Константин Евгеньевич, 2006 год

1. 1.O/IEC JTC1/SC 29 11172 (MPEG-1 Video), Information Technology -

2. Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to about 1.5 Mbits/s: Video, 1993.

3. ISO/IEC JTC1/SC 29 13818 ITU-T H.262 (MPEG-2 Video), Information

4. Technology Generic Coding of Moving Pictures and Associated Audio Information: Video, 1995.

5. ISO/IEC JTC1/SC 29 14496 (MPEG-4 Video), Information Technology &

6. Coding of Audio-visual Object: Visual, October 1997.

7. ISO/IEC 10918 Coding of Digital Continuous Tone Still Picture Images1. JPEG).

8. ISO/IEC 14495, ITU T.87, Information technology Lossless and nearlossless compression of continuous-tone still images, 1999.

9. ISO/IEC 15444:2000, Information technology JPEG 2000 image codingsystem.

10. Wu X., Memon N., Context-Based, Adaptive, Lossless Image Coding

11. EE Transactions on Communications, 1997, Vol.45, № 4, pp. 437444.

12. Howard, P.G., Vitter, J.S., Fast and Efficient Lossless Image

13. Compression, //Data Compression Conference, 1993, DCC '93, 30 March 2 April 1993 pp. 351-360.

14. ISO/IEC 15948:2004, Information technology Computer graphics andimage processing Portable Network Graphics (PNG).

15. A mathematical theory of communication //BELL SYSTEM TECN. J., N3 1948, pp. 379-423, N4 1948, pp. 623-656.

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

17. Kenneth M. Dawson-Howe Lossless Image Compression using a Simple Prediction Method. //International Journal of Imaging Systems and Technology, Vol.7, No.3, Fall 1996, pp.227-230.

18. Бредихин Д. Ю. Сжатие графики без потерь качества. http://www.compression.ru/download/revill.html

19. Memon N., Wu X. Recent Developments in Context-Based Predictive Techniques for Lossless Image Compression // The Computer Journal, Vol. 40, No. 2/3, 1997, pp.127-136.

20. Pennebaker W.B., Mitchell J.L. JPEG: Still Image Data Compression Standard. //New York: Van Nostrand-Reinhold, 1993.

21. Paeth, A.W., Image File Compression Made Easy, //in Graphics Gems II, James Arvo, editor. Academic Press, San Diego, 1991. ISBN 0-12064480-0.

22. Gandhi В., Honsinger C., Rabbani M., and Smith C., Differential Adaptive Run Coding (DARC), //1995, ISO Working Document ISO/IEC JTC1/SC29/WG1 N204.

23. Martucci S. A., Reversible compression of HDTV images using median adaptive prediction and arithmetic coding //in Proc. IEEE Intern'l Symp. on Circuits and Syst., IEEE Press, 1990, pp. 1310-1313.

24. Meyer В., Tischer P., Glicbawls grey level image compression by adaptive weighted least squares, //in Proc. IEEE Data Compression Conference, Snowbird, Utah, Mar. 2001.

25. Guang Deng, Hua Ye. Lossless image compression using adaptive predictor combination, symbol mapping and context filtering //Department of Electronic Engineering, La Trobe University, Bundoora.

26. Hua Ye, Guang Deng and John C. Devlin, A weighted least squares method for adaptive prediction in lossless image compression

27. Department of Electronic Engineering, La Trobe University Bundoora, Victoria 3083, Australia.http://www.ee.latrobe.edu.au/~dennis/publication pdf files/pcs2003.pdf

28. Speck, D. Proposal for next generation lossless compression of continuous-tone still. pictures: activity level classification model (ALCM), 1995, ISO Working Document ISO/IEC JTC1/SC29/WG1 N198.

29. Howard P. G., The design and analysis of efficient data compression systems, PhD thesis, Department of Computer Science, Brown University, 1993.

30. Golomb S. W., Run-length encodings, //IEEE Trans. Inform. Theory, vol. IT-12, 1966, pp. 399-401.

31. Rice, R. F. Some Practical Universal Noiseless Coding Techniques. Technical Report 79-22, Jet Propulsion Laboratory, California Institute of Technology, Pasadena, CA. THE COMPUTER JOURNAL, 1979, Vol. 40, No. 2/3, 1997.

32. Weinberger M. J., Seroussi G. and Sapiro G., The LOCO-I Lossless Image Compression Algorithm: Principles and Standardization into JPEG-LS, //IEEE Transactions on Image Processing, Vol. 9, No. 8, August 2000, pp. 1309-1324.

33. Weinberger M. J., Seroussi G., and Sapiro G., LOCO-I: A low complexity lossless image compression algorithm. //ISO/IEC JTC1/SC29/WG1 document N203, July 1995.

34. Carpentieri В., Weinberger M. J., Seroussi G., Lossless compression of continuous-tone images Proceedings of the IEEE Vol. 88, Issue 11, Nov 2000 pp. 1797- 1809.

35. Weinberger M. J., Seroussi G., and Sapiro G., Effects of resets and number of contexts on the baseline //ISO/IEC JTC1/SC29/WG1 document N386, June 1996.

36. Weinberger M. J., Rissanen J., and Arps R. В., Applications of universal context modeling to lossless compression of gray-scale images //IEEE Trans. Image Processing, vol. 5, Apr. 1996, pp. 575-586.

37. Wu X., Efficient and effective lossless compression of continuous-tone images via context selection and quantization //IEEE Trans. Image Processing, IP-6, 1997. pp. 656-664.

38. Wu X., An algorithmic study on lossless image compression, // in Proc.1996 Data Compression Conference, Snowbird, Utah, USA, Mar., 1996, pp. 150-159.

39. Moffat A., Neal R., Witten I.H., Arithmetic Coding Revisited, //Proc. IEEE Data Compression Conference, Snowbird, Utah, March 1995, pp. 202-211.

40. Fenwick P.M., A New Data Structure for Cumulative Probability Tables, // Software-Practice and Experience, March 1994, 24(3): pp. 327-336.

41. Rodriguez L. S., Fast piecewise linear predictors for lossless compression of hyperspectral imagery, //PhD thesis in Electrical Engineering University of Puerto Rico MAYAGUEZ CAMPUS 2003.www.grad.uprm.edu/tesis/rodriguezdelrio.pdf

42. Wu X., and Memon N., Context-Based Lossless Interband Compression-Extending CALIC. //IEEE Transactions on Image Processing, Vol. 9, No. 6, June 2000, pp. 994-1001.

43. ISO/IEC 15938, Information technology multimedia content description interface (MPEG-7), 2002.

44. ISO/IEC 21000, Information technology multimedia framework (MPEG-21), 2003.

45. Wallace G.K. The JPEG Still-Picture Compression Standard, // Communications of the ACM, vol. 34, no. 4, April 1991, pp. 30-44.

46. Huffman D., A method for the construction of minimum redundancy codes, Proc. IRE, vol. 40, 1952, pp. 1098-1101.

47. Knuth D. E., Dynamic Huffman coding, J. Algorithms, vol. 6, 1985 pp. 163-180.

48. Welch Т., A Technique for High Performance Data Compression IEEE Computer June 1984, Vol. 17, No. 6, pp. 8-19.

49. Ziv J., Lempel A., A Universal Algorithm for Sequential Data Compression // IEEE Transactions on Information Theory, Vol. IT-23, No. 3, May 1977, pp.337-343.

50. Ziv J., Lempel A., Compression of Individual Sequences via Variable-Rate Coding // IEEE Transactions on Information Theory, Vol. IT-24, No. 5, Sept. 1978, pp.530-536.

51. Ichiro Matsuda, Hirofumi Mori and Susumu Itoh, "Design of a Minimum-Rate Predictor and its Application to Lossless Image Coding", Signal Processing X, Theories and Applications, (Proceedings of EUSIPCO-2000), Vol.11,, Sep. 2000, pp.1205-1208.

52. Meyer В., and Tischer P., TMW A new method for lossless image compression, //in Proc. of the 1997 International Picture Coding Symposium (PCS97), (Berlin, Germany), Sept. 1997.

53. Meyer В., and Tischer P., TMW an object oriented image modeling framework, //in Proc. IEEE Data Compression Conference, Snowbird, Utah, Mar. 2001.

54. Gallager R.G., Van Voorhis D.C. Optimal Source Codes for Geometrically Distributed Integer Alphabets // IEEE Trans, on Inform. Theory, 1975, № 3, pp. 228-230.

55. Koga Т., Iinuma К., Hirano A., Iijima Y., Ishiguro Т., Motion Compensated Interframe Coding for Video Conferencing, //Proc. National Telecommunications Conference, New Orleans, LA. November 1981, pp. G5.3.1-G5.3.5.

56. Jain J. R., Jain A.K., Displacement Measurement and its Application in Interframe Image Coding, //IEEE Trans. Commun., vol. 29, December 1981, pp. 1799-1808.

57. Puri A., Hang H.M., Schilling D.L., An Efficient Block Matching Algorithm for Motion Compensated Coding, //Proc. IEEE International Conference on acoustics, Speech and Signal Processing, 1987, pp. 1063-1066.

58. Po L. M. and Cheung С. K., A new center-biased orthogonal search algorithm for fast block motion estimation, //Proceeding of IEEE TENCON' 96, vol. 2, Nov. 1996, pp. 874-877.

59. Chanbari M., The Cross-Search Algorithm for Motion Estimation, //IEEE Trans. Communication, vol. 38, pp. 950-953, July 1990.

60. Po L. M., Ma W.C., A New Center-biased Search Algorithm for Block Motion Estimation, //Proc. IEEE International Conference on Image Processing, Washington, DC, October 1995.

61. Po L. M., Ma W.C., A Novel Four-Step Search Algorithm for Fast Block Motion Estimation, //IEEE Trans. Circuits and Systems for Video Technology, vol.6, no.3, June 1996, pp. 313-317.

62. Liu L. К., Feig E., A ,block:based gradient search algorithm for block motion estimation in video coding, //IEEE Trans. Circuits and Systems for video Technology, August 1996, vol. 6, no. 4, pp. 419-422.

63. Загайнов И. Г., Повышение эффективности методов компенсации движения для кодирования подвижных изображений, //диссертация на соискание ученой степени кандидата технических наук, УДК 621.397.2.037.37

64. Cheung С.К., Ро L.M., Normalized Partial Distortion Search Algorithm for Block Motion Estimation //IEEE Trans. No. 3, April 2000, pp. 417122.

65. Cheung C.K., Po L.M., A New Fast Block Motion Estimation Algorithm Using Normalized Partial Distortion Measure //International Workshop on Multimedia Data Storage, Retrieval, Integration and Applications, January 2000, pp. 34-39.

66. Бабкин В.Ф., Книжный И.М., Хрекин К.Е. Сжатие многоспектральных изображений без потерь или с ограниченными потерями. //Семинар "Современные и перспективные разработки и технологии в космическом приборостроении": Докл. — М., ИКИ РАН, 2004. С. 87-94.

67. Alparysoft Codec кодек, разработанный компанией Alparysoft,позволяющий сжимать видеоданные без потерь.

68. ALCM (Activity Level Classification Model) адаптивный алгоритмпредсказания.

69. CALIC (Context-based Adaptive Lossless Image Coding) алгоритм сжатия изображений без потерь.

70. CIF (Common Intermediate Format) формат представления оцифрованных изображений.

71. CorePNG кодек, позволяющий сжимать видеоданные без потерь, на основе формата PNG.

72. CamStudio Codec кодек, разработанный компанией CamStudio, позволяющий сжимать видеоданные без потерь.

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

74. FILICS (Fast, Efficient, Lossless Image Compression System) быстраяэффективная система сжатия изображений без потерь.

75. Н.264 стандарт кодирования мультимедиа.

76. HuffYUV кодек, обеспечивающий сжатие видеопоследовательностей без потерь.

77. C (International Electrotechnical Commission) международная электротехническая комиссия, занимающаяся вопросами стандартизации. ISO (International Standards Organisation) - международная организация по стандартизации.

78. U (International Telecommunication Union) международный союз телекоммуникаций.

79. JPEG (Joint Photographic Experts Group) объединенная группа экспертов по фотографии, комитет в ISO (обозначает также стандарт кодирования изображений).

80. JPEG2000 стандарт кодирования изображений.

81. JPEG-LS стандарт кодирования изображений.

82. JTC1 (Joint Technical Committee 1) объединенный технический комитет №1.

83. МАЕ (Mean Absolute Error) критерий средне-абсолютных отличий.

84. MPEG (Motion Picture Experts Group) объединенная группа экспертов подвижущимся изображениям, комитет при ISO/IEC.

85. MSE (Minimal Square Error) критерий среднеквадратических отличий.

86. CO-I (LOw Complexity Lossless Compression) алгоритм сжатия безпотерь для полутоновых изображений.

87. L-3D простейший предсказатель, использующий корреляцию текущего и предыдущего изображений.

88. CO-2B простой предсказатель, использующий корреляцию текущего и предыдущего изображений.

89. CO-3D простой предсказатель, использующий корреляцию текущего и предыдущего изображений.

90. CO-SI простой предсказатель использующий корреляцию текущего и предыдущего изображений.

91. MotionJPEG (MJPEG) стандарт кодирования мультимедиа.

92. MPEG-1 стандарт кодирования мультимедиа.

93. MPEG-2 стандарт кодирования мультимедиа.

94. MPEG-4 стандарт кодирования мультимедиа.

95. MPEG-7 стандарт описания содержания объектов мультимедиа.

96. MPEG-21 стандарт описания содержания объектов мультимедиа.

97. PNG (Portable Network Graphics) сетевой формат графических файлов.

98. PICVideo Lossless JPEG кодек, разработанный компанией PICVideo,позволяющий сжимать видеоданные без потерь, на основе стандарта JPEG.

99. QCIF (Quarter Common Intermediate Format) четвертной общийпромежуточный формат,' который используется для представлениянесжатых) видеоданных.4CIF формат представления оцифрованных изображений.

100. RGB (Red/Green/Blue) цветовое пространство с компонентами красный/зелёный/синий.

101. SIF (Standard Interchange Format) формат представления оцифрованных изображений.

102. SPM (Simple Prediction Method) простой предиктивный метод.

103. Sub-QCIF формат представления оцифрованных изображений.

104. TSS (3SS) (Three-step search) 3-х шаговый алгоритм поиска векторовсмещения макроблоков.

105. VO (Video Object) видеообъект.

106. VOP (Video Object Plane) плоскость видеообъекта.

107. YCbCr цветовое пространство с яркостной (Y) и цветоразностными компонентами (СЬ, Сг).