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

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

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

Для корректной передачи цвета требуется 16 миллионов оттенков (8 бит на каждую из трех цветовых компонент). Таким образом, для описания изображения на экране, содержащего 576 линий по 720 пикселов, требуется -1,0 Мбайт. Учитывая, что частота смены кадров (25 раз в секунду) и продолжительность среднего фильма ~ 1,5 часа, получим -160 000 Мбайт. Чтобы записать такой фильм на 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 г. Программа зарегистрирована во ВНТИЦ под регистрационным номером 50 200 500 007.

Основные положения и результаты диссертационной работы докладывались на 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© на основе предсказателя (прототипа), использованного в схеме CALIC, и кодек LLIC, в котором применен разработанный автором предсказатель. Для сопоставимости результатов сжатия в обоих кодеках использовался один и тот же статистический кодер. Сравнение проводилось на представительной серии тестовых изображений. Кодек LLIC продемонстрировал в среднем на ~2% больший коэффициент сжатия в сравнении с кодеком LLIC©, проигрывая по скорости всего -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), что позволит более точно вести предсказание кодируемого кадра последовательности.