автореферат диссертации по радиотехнике и связи, 05.12.04, диссертация на тему:Разработка методов сжатия без потерь для серий изображений

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

ХРЕКИН Константин Евгеньевич

РАЗРАБОТКА МЕТОДОВ СЖАТИЯ БЕЗ ПОТЕРЬ ДЛЯ СЕРИЙ ИЗОБРАЖЕНИЙ

Специальность 05.12.04 Радиотехника, в том числе системы и устройства телевидения

АВТОРЕФЕРАТ

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

Москва - 2006

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

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

БОРИСОВ Виктор Алексеевич

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

СИЗОВ Виктор Петрович

кандидат технических наук, доцент СЕНИН Александр Иванович

Ведущая организация: ФГУП "РНИИ КП" (г. Москва)

Защита состоится 12 октября 2006 г. в 17 час. 00 мин. на заседании диссертационного совета Д 212.157.05 при Московском энергетическом институте (техническом университете) по адресу: 111250, Москва, Красноказарменная ул., д. 17, в ауд. А-402.

Отзывы в двух экземплярах, заверенные печатью, просим направлять по адресу: 111250, Москва, Красноказарменная ул., д. 14, Ученый совет МЭИ (ТУ).

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

Автореферат разослан // сентября 2006 г.

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

диссертационного совета Д 212.157.03' кандидат технических наук, доцент С

Т.И. КУРОЧКИНА

Общая характеристика работы Актуальность работы

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

Задача сжатия видеопоследовательностей без потерь, сопряженная с компактным представлением отдельных кадров, восходит к истокам проблематики кодирования источника, пионерский вклад в исследование которой внесли российские и зарубежные ученые Р.Галлагер, М.Вайнбергер, Ш.Ву, Г.Лэнгдон, Р.Райс, В.Ф.Бабкин, Ю.М.Штарьков и др. Необходимо отметить также фундаментальные работы в области теоретико-информационных методов кодирования источника ученых новосибирской школы Р.Е.Кричевского, Б.Я.Рябко, В.К.Трофимова и др. Практические методы сжимающего кодирования изображений разрабатывались в Институте проблем передачи информации РАН Д.С.Лебедевым и

1 MPEG (Moving Picture Experts Groiml - рабочая группа, которая совместно с международной организацией по стандартизации (International Standards Organization, ISO/IEC) разрабатывает стандарты кодирования цифровых аудио и видео потоков.

2 MPEG1 - стандарт сжатия видеоизображений (ISO/IEC 11172-2)

3 MPEG2 - стандарт сжатия видеоизображений (ISO/IEC 13818-2)

4 MPEG4 - стандарт сжатия видеоизображений (ISO/IEC 14496)

5 Н.264 - стандарт сжатия видеоизображений (ISO/IEC 14496-10/MPEG-4 AVC)

Л.П.Ярославским. Большой вклад в теорию и практику сжатия видеоизображений внесли В.П.Дворкович, Б.Д.Кудряшов, Д.С.Ватолин и др.

В настоящий момент существует целый ряд стандартов и методов, позволяющих сжимать без потерь как черно-белые полутоновые, так и цветные статические изображения. Среди них стандарты сжатия JPEG (ISO/TEC 10918) в режиме сжатия без потерь, JPEG-LS (КОЛЕС 14495), JPEG2000 (ISO/IEC 15444), нестандартизованные схемы сжатия изображений CALIC,FELICS и т.д.

Следует заметить, что на текущий момент при наличии стандартов группы MPEG, а также упомянутых выше стандартов и методов сжатия статических изображений, не определены стандарты сжатия без потерь, ориентированные на эффективное сжатие видеоизображений. Тем не менее, существует целый ряд практических реализаций, позволяющих кодировать видеоизображения без потерь, например: HuffYUV6, CorePNG7, Alparysoft Codec8, CamStudio Codec9, PICVideo Lossless JPEG10 и др., построенные с использованием простых внутрикадровых предсказателей, не учитывающие достаточно высокую межкадровую корреляцию, что в конечном счёте приводит к невысокой эффективности кодеков. Характерный средний коэффициент сжатия, обеспечиваемый перечисленными кодеками, на серии тестовых видеопоследовательностей составляет от 1,5 до 2,3. Отдельно стоит отметить метод сжатия видеоизображений без потерь, использованный в MSU Lossless Video Codec11, разработанный Д.Ватолиным и Д.Поповым, использующий предсказатель с контекстным моделированием в сочетании с простой схемой компенсации движения, позволяющий получить на серии тестовых видеопоследовательностей12 средний коэффициент сжатия 4,49,

6 http://ncuron2.net/www.math.bcrkelev.edu/bcnrB/

' http://corepnfr.coreccidec.org/

8 http://www.alparvsoft.com/products.php

9 http://www.free-codecs.com/downioad/CamStudio_Lossless Codec.htm

10 http://www.pegasusim3ging.com/picvideolossless.htm

11 http://www.compression.ru/video/ls-codec/

1! см.. например, http://media.xiph.org/video/derf/

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

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

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

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

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

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

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

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

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

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

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

программно и исследованы на персональном компьютере с использованием представительных наборов тестовых видеопоследовательностей.

Научная новизна диссертационной работы заключается в следующем:

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

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

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

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

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

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

Практическая ценность результатов

1. Разработанный алгоритм сжатия без потерь для серий изображений реализован в виде набора Win32-пpилoжeний, которые могут быть использованы для эффективного неискажающего сжатия мастер-копий видеофильмов.

2. Разработанные методы могут применяться для эффективного сжатия многоспектральных изображений ДЗЗ, что подтверждается исследованием, проведённым на сериях реальных изображений, полученных с использованием космической съёмочной системы ДЗЗ МСЮК.

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

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

Апробация и внедрение результатов работы

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

Предложенный автором и описанный в диссертационной работе адаптивный контекстно-зависимый предсказатель был использован при разработке и моделировании программно-алгоритмического обеспечения сжатия видеоданных комплекса ДЗЗ среднего разрешения «Метеор-М», проведённой AHO "Космос - Наука и техника" по заказу ФГУП НЛП ВНИИЭМ (Договор № 02/01-2005 от 11.01.05), а также в программе сжатия без потерь и с ограниченными потерями полутоновых черно-белых и многокомпонентных цветных изображений с большим числом уровней квантования (8-16 бит на компоненту), предложенной к реализации в рамках федеральной целевой научно-технической программы "Исследования и разработки по приоритетным направлениям развития науки и техники" на 20022006г. Программа зарегистрирована в ВНТИЦ под регистрационным номером 50200500007.

Основные положения и результаты диссертационной работы докладывались на 11-й Всероссийской конференции «Математические методы распознавания образов ММРО-11», первой и третьей Всероссийских конференциях «Современные проблемы дистанционного зондирования Земли из космоса» в 2003

и 2005 годах, на семинаре Инстщуга космических исследований (ИКИ) РАН "Современные и перспективные разработки и технологии в космическом приборостроении" в 2004 году и опубликованы в сборниках докладов.

Результаты, полученные в рамках ФЦНТП "Исследования и разработки по приоритетным направлениям развития науки и техники" на 2002-2006 г., Блок 2 - "Поисково-прикладные исследования и разработки", раздел "Информационные технологии", Тема № 32 "Модели и алгоритмы кодирования и сжатия информации", зарегистрированы во ВНТИЦ и оформлены в виде научно-технических отчетов по теме "Разработка алгоритмов и программных средств неискажающего сжатия и сжатия с ограниченными потерями многокомпонентных изображений" за 2002, 2003 и 2004 годы, регистрационные номера 0220.0 406458, 0220.0 406457, 0220.0 406459. Отчет за 2004 год был отмечен премией на конкурсе научных работ ИКИ РАН в номинации "Лучшие научно-технические отчёты"

Публикации

В целом в печатных изданиях было опубликовано 5 работ, 2 из которых - тезисы докладов на научно-технических конференциях, 2 доклада на научно-технической конференции и семинаре, одна статья в тематическом сборнике • «Современные проблемы дистанционного зондирования Земли из космоса» и три научно-технических отчета, зарегистрированных в ВНТИЦ.

Основные положения, выносимые на защиту

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

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

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

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

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

Структура и объём работы

Диссертация состоит го введения, четырех глав, заключения, списка литературы и трёх приложений, всего содержит 136 страниц машинописного текста, 56 рисунков, 20 таблиц. Список литературы включает 70 наименований.

Краткое содержание работы

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

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

Рис. 1

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

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

Проводится классификация предсказателей, описываются наиболее известные из них, такие как Paeth, предложенный A.W. Paeth, DARC (Differential Adaptive Run Coding), разработанный фирмой KODAK, MED (Median Edge Detection), предложенный MWeinberger (HP Labs) и вошедший в стандарт сжатия без потерь JPEG-LS, GAP (Gradient-Adjusted Predictor), предложенный X.Wu и использованный в схеме сжатия CALIC (Context-based Adaptive Lossless Image Coding). Анализируются существующие методы учета межкомпонентной зависимости при построении предиктивных схем сжатия многоспектральных изображений, а также описываются методы, применяемые в стандартах искажающего сжатия видеопоследовательностей группы MPEG.

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

Названия тестовых видеопоследовательностей

Рис.2

Кодек MSU Lossless Video Codec v.0.5.8 показал наилучшую эффективность среди тестируемых, за счет использования предсказателя с контекстным моделированием в сочетании со схемой компенсации движения и арифметическим кодированием, но при этом оказался самым медленным.

На серии тестовых изображений средний коэффициент сжатия составил 4,499. Средняя скорость кодирования - 0,882 МБайт/с. Все тесты проводились на компьютере, оснащённом процессором AMD Thunderbird 750 МГц и 512 МБайт оперативной памяти.

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

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

Рис.3

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

p = a-n+P-w+y-ne+ô-w\№£-nw+Ç-nwwïr)-nn+e-tine+ i-nnw+K-nne. (1) Весовые коэффициенты a,...jc подбирались экспериментально на представительной серии тестовых 8-битовых изображений.

На основании накопленной информации об ошибках предсказания в том или ином классе контекстов в процессе работы предсказателя вычисляется дополнительная поправка Д как функция накопленных ошибок в соответствующем классе контекстов, что позволяет учитывать недавние ошибки с большим весом, а ошибки на более ранних стадиях предсказания — с меньшим:

Д = Й, .в+ /?, -Д; а, > /?,, (2)

где с^и/j,— весовые коэффициенты, е — ошибка, соответствующая определенному классу контекстов на предыдущем этапе предсказания, ад — поправка для того же класса контекстов, но вычисленная по результатам коррекции на предыдущих этапах предсказания. Окончательное предсказываемое значение Р' вычисляется как

рЧР + Л- (3)

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

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

2. Число классов контекстов увеличено до 2048.

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

Предложенный и описанный в диссертационной работе адаптивный конгексшо-зависимый предсказатель, использованный в составе кодека LLIC (Lossless Image Codec), в котором для статистического кодирования ошибок предсказания был применён разработанный И. Книжным адаптивный статистический кодер на принципе Голомба, позволил на серии тестовых изображений получить в среднем на 2% больший коэффициент сжатия, чем при использовании предсказателя-прототипа.

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

Предыдущий кадр I Текущий кадр

Предсказываемый текущий пиксел (/я )

Смежный контекст в найденном смещенном блоке 8x8 на предыдущем кадре

Пиксел, смежный с предсказываемым на предыдущем кадре ( I у )

Рис.4

Контекст предсказываемого пиксела

Для каждого блока текущего кадра производится поиск соответствующего ему (наиболее похожего) блока на предыдущем кадре в некоторой окрестности MxN. Критерием отбора служит минимум суммы квадратов разностей интенсивностей пикселов (MSE- mean squared error), входящих в блоки ткп на текущем и предыдущем кадрах, позволяющий минимизировать среднеквадратические отличия блоков. Таким образом осуществляется поиск для всех блоков в. текущем кадре. При использовании в качестве критерия поиска минимума MSE для блоков с резко выраженными

контурами значения суммы в формуле вычисления MSE принимают достаточно большие значения и, следовательно, пороговое значение для нахождения таких блоков должно быть соизмеримо с вычисленными суммами. Блоки с небольшими перепадами яркости (малоконтрастные) могут находиться неправильно, поскольку сумма для них будет заведомо ниже порога. Чтобы отсеять неправильно найденные блоки, автором предложен следующий приём: для найденного блока вычисляется величина динамического диапазона интенсивности пикселов. Если эта величина меньше установленного порогового значения, то блок признается малоконтрастным, и для него происходит пересчёт значений интенсивности пикселов по следующей формуле:

/,= (/ 2-/ . )(/~/miJ, (4)

V max min /

где I - исходная яркость пиксела, /ШШ1 , 7min - максимальная и минимальная яркости по найденному и искомому блокам.

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

Далее, для более точного определения соответствия контекста предсказываемого пиксела на текущем кадре и смежного с ним контекста, но уже на скомпенсированном кадре, в соответствии с (5) вычисляется

коэффициент корреляции Kzy (п — число пикселов в контексте, I У: и 17< -интенсивности пикселов соответствующих контекстов):

(5)

L 1-1 i=i

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

на скомпенсированном кадре с вычислением линейных коэффициентов регрессии в соответствии с (6):

¿1 _ 1-1_1=1 ¡=1 е _ _М (О}

«±1\~<±1Л?

(=1 .1=1

Предсказанное значение интенсивности текущего пиксела I, вычисляется как

= (I ег (?)

где 1у- значение интенсивности пиксела, смежного с предсказываемым

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

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

Р>(.гх,1у)-Щу,1у)Щх,1х) ' 1*(1х,1у)~Р(1у,1уЖ1х,1х) ' (8)

п V 1-1 '=1 ) '-1 '»1 1*1

Предсказанное значение интенсивности текущего пиксела 1 рассчитывается как

= а + Ъ .1, + с, (9)

где / - значение интенсивности пиксела, смежного с предсказываемым на скомпенсированном предыдущем кадре, 1Х - значение интенсивности пиксела, смежного с предсказываемым на скомпенсированном кадре, предшествующем предыдущему.

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

Для оценки эффективности разработанного адаптивного контекстно-зависимого предсказателя и методов учета межкадровой зависимости на языке С были написаны модельная программа и библиотека кодеков LLVC (Lossless Video Codec). Тестирование проводилось на 12 представительных тестовых видеопоследовательностях с размером кадра от 176x144 пикселов (QCIF) до 352x288 пикселов (CIF) и числом кадров от 150 до 1000.

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

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

О 0,2 0,4 0,в О,В 1 OS 10 15 20

Пороговый уровень коэффициента Количество пикселов

корреляции

Рис.5 Рис.6

При этом показано, что максимум коэффициента сжатия достигается при значениях порога коэффициента корреляции в диапазоне 0,5 — 0,6 и при использовании контекста из 12 пикселов для вычисления коэффициентов

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

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

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

На рис. 7 и 8 представлены результаты работы трех разработанных кодеков в сравнении с кодеком MSU Lossless Video Codec v.0.5.8.

5 7

I о I 5

! 4

S з

2 1

0

3.5

® -a s Э

I 2,5

2

II 1,5 й £ 1

I 0,5

В 0

д 1

1

I

1

л ^ ;

А __ * I

.А* *

'4 я . -А* 1 1

1 I

- 1- ■ :

-LLVC-3 —LLVC-1 -MSU -LLVC-2

Названия тестовых видеопоследовательностей

Рис. 7

✓ У

i

gn '-.Tii

В®!

LI.VC-2 Названия кодеков

Рис. 8

Средний коэффициент сжатия на' серии тестовых видеопоследовательностей для кодека УС-2 составил 4,854, что на 7,89% лучше результатов,

продемонстрированных кодеком МБи, при этом по скорости кодирования разработанный кодек выифывает более чем на 70%.

Разработанный подход к сжатию без потерь на основе адаптивного контекстно-зависимого предсказателя с использованием методов корреляционного анализа также показал хорошие результаты при сжатии многоспектральных изображений в задачах ДЗЗ. Тестирование проводилось на изображениях, полученных космической съёмочной системой МСЮК13, сгруппированных в пять последовательностей по пять изображений в каждой.

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

В заключении кратко сформулированы основные результаты диссертационной работы:

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

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

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

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

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

- данные с системы ДЗЗ МООГЗ представлены для тестирования алгоритмов сжатия ИТЦ СканЭкс

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

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

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

Публикации

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

2. Бабкин В.Ф., Книжный И.М., Хрекин К.Е. Сжатие многоспектральных изображений для задач дистанционного зондирования Земли из космоса // Современные проблемы дистанционного зондирования Земли из космоса. Сборник научных статей. - М.: Полиграф сервис, 2004. - С. 23-28.

3. Бабкин В.Ф., Книжный И.М., Хрекин К.Е. Сжатие без потерь или с ограниченными потерями статических полутоновых изображений //Докл. 11 Всеросс. конф. «Математические методы распознавания образов ММРО-11» 23-29 ноября 2003г., Пущино. — М.: ВЦ РАН, 2003. - С. 44-49.

4. Бабкин В.Ф., Василейский A.C., Книжный И.М., Хрекин К.Е. Методы сжатия на борту КА видеоинформации, получаемой многозональными сканирующими съемочными устройствами //Тез. докл. III Всеросс. конф. «Современные проблемы дистанционного зондирования Земли из космоса» 14-17 ноября 2005г. - М.: ИКИ РАН, 2005. -С. 75.

5. Хрекин К.Е. Применение корреляционного подхода в сочетании с методами компенсации движения при сжатии последовательностей изображений без потерь //Тез. докл. .III Всеросс. конф. «Современные проблемы дистанционного зондирования Земли из космоса» 14-17 ноября 2005г. - М.: ИКИ РАН, 2005. - С. 291.

Подписано в печать 6.09* 06Тир. (00 П.л. Полиграфический центр МЭИ (ТУ) Красноказарменная ул., д. 13

Введение.

Глава 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), что позволит более точно вести предсказание кодируемого кадра последовательности.

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) и цветоразностными компонентами (СЬ, Сг).