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

Коплович Евгения Александровна

Разработка алгоритмов стабилизации и компрессии

изображений для систем видеонаблюдения мобильных

робототехнических комплексов

Специальность 05.13.11 — «Математическое и программное

обеспечение вычислительных машин, комплексов

и компьютерных сетей»

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

Москва, 2008

Работа выполнена на кафедре «Высшей математики № 1»

Московского государственного института электронной техники (технического университета).

Научный руководитель: доктор физико-математических наук, профессор Умняшкин С. В.

Официальные оппоненты: доктор физико-математических наук, профессор Рычагов М. Н.

кандидат физико-математических наук Посыпкин М. А.

Ведущая организация: государственное унитарное предприятие г. Москвы научно-производственный центр «Электронные вычислительноинформационные системы»

Защита состоится «_» 2009 г. в _ часов _ минут на заседании диссертационного совета Д 212.134.02 при Московском государственном институте электронной техники (техническом университете) по адресу: 124498, Москва, проезд 4806, д. 5, МИЭТ.

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

Автореферат разослан «_» 200 г.

Ученый секретарь диссертационного совета, доктор технических наук Гуреев А. В.

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

Актуальность проблемы Перспективным направлением автоматизации в различных областях человеческой деятельности является создание мобильных робототехнических комплексов (МРК), которые способны функционировать в экстремальных и опасных для жизни человека условиях.

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

Ограниченная пропускная способность каналов связи не позволяет передавать без компрессии значительные объемы видеоданных. Выбор того или иного метода сжатия видеоинформации определяется как обеспечиваемыми характеристиками компрессии, так и вычислительной сложностью реализации. Часто останавливаются на простейших алгоритмах, подразумевающих независимую покадровую обработку поступающего видеопотока. Распространенные стандарты видеокодирования, такие как MPEG-2 и MPEG-41, позволяют добиться лучшего соотношения качество/степень сжатия, однако они более требовательны к вычислительным ресурсам. Данные стандарты видеокомпрессии основаны на дискретном косинусном преобразовании (ДКП), что при малых битовых затратах приводит к появлению на восстановленных видеоизображениях характерных блочных искажений. Кроме того, они не позволяют изменять битовую скорость передаваемого закодированного потока в режиме реального времени.

Специалисты в области прикладной теории передачи данных уделяют повышенное внимание разработке новых алгоритмов компрессии видеоинформации на базе дискретного вейвлет-преобразования (ДВП).

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

В связи с вышесказанным актуальными являются как исследования, позволяющие повысить эффективность известных методов компрессии статических и динамических изображений, основанных на ДКП, так и Стандарты ISO/IEC 13818-2 и ISO/IEC 14496- разработка новых алгоритмов кодирования, которые могут быть успешно использованы в системах видеонаблюдения реального времени.

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

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

Основные задачи

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

исследование существующих подходов к сжатию динамических и статических изображений на основе различных декоррелирующих преобразований и анализ методов стабилизации видеоизображений;

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

синтез алгоритма определения сдвига источника видеосигнала на основе блочного ДКП;

разработка метода масштабируемого кодирования векторов перемещения блоков видеокадра;

разработка алгоритма видеокомпрессии на основе иерархического кодирования коэффициентов ДВП и блочной компенсации движения в пространственной области для систем видеонаблюдения МРК, обладающих высокими вычислительными ресурсами;

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

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

Методы исследования В процессе работы над диссертацией в качестве методов исследования использовались методы линейной алгебры, теории вероятностей и математической статистики, теории цифровой обработки и кодирования данных. Экспериментальные исследования проводились с помощью численного моделирования на персональном компьютере в средах разработки Microsoft Visual Studio и MATLAB.

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

Личный вклад автора Все предложенные в работе алгоритмы, за исключением алгоритма видеокомпрессии, были реализованы и экспериментально проанализированы лично автором. Аппаратно-программная реализация алгоритма видеокомпрессии на основе ДВП проводилась коллективом исследователей при непосредственном участии автора.

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

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

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

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

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

Результаты диссертационного исследования были использованы в ряде НИР, проводимых в МИЭТ. Разработанные алгоритмы видеокомпрессии внедрены в макетных образцах систем видеонаблюдения в НИИ вычислительных средств и систем управления (ВСиСУ) МИЭТ.

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

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

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

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

Апробация работы Основные результаты диссертационной работы докладывались и обсуждались на 11-й, 12-й, 13-й и 14-й Всероссийских межвузовских научно-технических конференциях студентов и аспирантов «Микроэлектроника и информатика» (Москва, МИЭТ, 2004–2007 гг.), а также на 4-й Российско-Баварской конференции по биомедицинской инженерии (Москва, МИЭТ, 2008 г.).

Публикации По теме диссертации опубликовано девять работ (среди них три статьи в ведущих рецензируемых журналах и одна статья в трудах международной конференции); результаты исследований отражены также в пяти отчетах о НИР. Без соавторов опубликовано пять работ.

Структура и объем диссертации Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и четырех приложений. Она изложена на 146 страницах (из них 14 — приложения), содержит 63 рисунка и 7 таблиц. Список литературы включает 149 источников.

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

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

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

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

При синтезе методов компрессии видеоинформации для телевизионной системы МРК необходимо принимать во внимание характеристики установленных на нем аппаратных элементов. Существенные ограничения на вычислительные ресурсы не позволяют применять сложные алгоритмы с компенсацией движения, поэтому в таких случаях оправдано использование методов независимой обработки видеокадров на базе ДКП, в частности, метода Motion JPEG, в котором каждый кадр сжимается алгоритмом JPEG2. В связи с этим одной из задач диссертационного исследования является разработка метода контекстного кодирования коэффициентов ДКП, повышающего эффективность сжатия статичеСтандарт ISO/IEC 10918- ских изображений в JPEG-подобной схеме компрессии. Кроме того, использование найденных в процессе сжатия видеокадра коэффициентов ДКП для определения его сдвига, вызванного движением видеоисточника, даст возможность выполнять стабилизацию изображения с относительно небольшими вычислительными затратами.

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

Таким образом, диссертационное исследование посвящено синтезу методов кодирования видеоинформации, которые могут применяться как в условиях ограниченных вычислительных ресурсов МРК, так и при использовании высокопроизводительных (в том числе параллельных) вычислительных структур.

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

Предложенный в работе метод контекстного кодирования коэффициентов ДКП позволяет увеличить степень сжатия в JPEG-подобной схеме компрессии. Подготовка изображения к кодированию осуществляется аналогично классическому алгоритму JPEG: исходное изображение размера M L пикселов разбивается на блоки A m, l = aim,jl, m = 0, 1,..., M 8 1, l = 0, 1,..., L 8 1, каждый из которых обрабатывается с помощью двумерного ДКП: Y m, l = ДКП ( A m,l ). Блоки коэффициентов ДКП квантуются некоторой целочисленной матрицей Z m, l = z 0, l, K, z 63, l в порядке зигзага.

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

Под контекстом кодируемого символа si, обозначаемым C (si ), понимается некоторый набор ранее обработанных (закодированных или декодированных) символов: C (si ) = s j1,...., s jr, j1,..., jr < i, где r > 0 — конечное число, определяющее порядок контекстной модели.

Контекстным прогнозом символа S i называется случайная величина U i, представляющая собой функцию f от элементов контекста. Реализация данной величины — значение прогноза u i = f (C ( si )) — используется при выборе статистической модели для кодирования символа.

Пусть Z m, l = z 0, l,K, z 63, l — коэффициенты ДКП, промасштабироm m ванные в результате деления без округления на элементы матрицы квантования Q и соответствующие блоку с координатами (m, l ).

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

При построении контекстного прогноза помимо коэффициентов из обрабатываемого блока используются коэффициенты двух соседних блоков изображения, т. е. анализируется корреляционная зависимость величины Z k, k = 1, K, 63, от множества «факторов» Wk, под которыми понимаются перепады постоянной составляющей и модули ранее обработанных коэффициентов верхнего и левого блоков, а также перепады постоянной составляющей и коэффициенты, предшествующие Z k в кодируемом блоке.

Контекст формируют факторы из множества Wk, наиболее коррелированные с величиной Z k. Для каждого значения k выбираются r (k ) элементов Cik Wk, i = 1, K, r (k ), таких, что модули соответствующих В качестве функции прогноза случайной величины Z k используется линейная регрессия Z k на C ( Z k ), т. е. функция условного математического ожидания которая ищется в виде линейной функции от переменных c1, K, crk(k ) :

Параметры ki для (1) традиционно находятся по методу наименьших квадратов решением системы линейных уравнений:

где горизонтальная черта обозначает выборочное среднее, cov — выборочную оценку ковариации.

Для всех коэффициентов ДКП число символов в контекстной модели было одним и тем же, r (k ) = R, и подбиралось экспериментально.

индексов ненулевых элементов вектора Z m, l, nk, l 0 — длина непреm рывной серии нулей, непосредственно следующих за проквантованным коэффициентом z k = round z k 0, сжимаются с помощью многоm, l m, l модельного арифметического кодера. Выбор статистической модели производится на основе прогноза (1), в котором контекст составляется по величинам проквантованных коэффициентов ДКП. Множество возможных значений прогноза разбивается на интервалы, определяемые набором порогов t1, t 2, K, t M, каждому из интервалов ставится в соответствие некоторая модель, описывающая частоты появления символов и в процессе кодирования адаптирующаяся к статистике обрабатываемых данных.

Поскольку для кодирования ненулевых коэффициентов и длин нулевых серий применяются различные статистические модели, используются два разных набора порогов: t1z, t 2, K, t M z — для ненулевых коэфz z фициентов, t1, t 2, K, t M n — для длин нулевых серий.

Эффективность предложенного алгоритма сжатия изображений оценивалась с помощью семи стандартных тестовых полутоновых изображений размера 512512 пикселов. Для кодирования ненулевых коэффициентов и длин нулевых серий использовалось по 4 модели, отдельная модель применялась для обработки постоянной составляющей ДКП-блока, т. е. всего использовалось 9 моделей.

В табл. 1 приведены результаты сжатия некоторых тестовых изображений при фиксированном качестве, критерием для которого являлось пиковое соотношение сигнал/шум (PSNR). Под выигрышем в сжатии понимается процент уменьшения длины файла при использовании предложенного контекстного кодирования по сравнению с размером JPEG-файла. Файлы JPEG были получены с использованием свободно распространяемой библиотеки от Independent JPEG Group.

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

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

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

Предложенный способ выбора участков изображения позволяет выделять характерные опорные блоки, векторы перемещений y2 y4 y которых можно считать достоверными и y3 y использовать при дальнейшем определении y глобального движения. В роли таких участков выступают блоки размером 88 пикселов. Классификация блоков проводится на основе значений коэффициентов ДКП, со- Рис. 1. Коэффициенты ДКП, ответствующих «средним» частотам (см.

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

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

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

В табл. 2 приведены результаты обработки одной из тестовых последовательностей, включающие:

максимальную ошибку определения сдвига альный и найденный векторы сдвига кадра;

среднее значение ошибки m = mean vf v f Как видно из табл. 2, предложенный алгоритм обеспечивает высокую точность определения сдвига при небольшом количестве анализируемых блоков. Помимо выбора характерных блоков, существенную роль также играет способ определения векторов перемещения, поэтому для их нахождения имеет смысл использовать алгоритм полного перебора. В табл. 3 представлены результаты, полученные при определении сдвига с использованием алгоритма полного перебора, но без выделения характерных блоков. Видно, что даже при большом числе анализируемых блоков (200) не удается достичь такой же точности, как при расчете всего по 30 характерным блокам.

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

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

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

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

На каждом слое для текущего обрабатываемого блока строится прогнозный вектор v pred, который определяется с помощью медианной фильтрации по ранее вычисленным векторам соседних блоков, расположенных в обрабатываемом (для первого слоя) или предыдущих (для второго и третьего) слоях. Область поиска Вектор v pred задает положение области поиска вектора v (см. рис. 2), по которому находится vpred реальное перемещение блока v = v pred + v.

Вектор v определяется минимизацией функции Лагранжа J = Dv + Rv, где Dv — искажение, Текущий блок вносимое ошибкой предсказания блока, Rv — Рис. 2. Поиск вектора количество бит, необходимое для кодирования движения блока вектора v ; — множитель Лагранжа.

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

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

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

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

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

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

Если кадр должен быть закодирован как I-кадр, то над ним выполняется ДВП, после чего коэффициенты обрабатываются алгоритмом SPIHT3. Если же текущий кадр является P-кадром, то сначала с помощью блочной компенсации движения в пространственной области устраняется временная избыточность. Далее на основе найденных векторов перемещения вычисляется разностное изображение, которое также переводится в область ДВП, а коэффициенты кодируются методом SPIHT.

Векторы движения обрабатываются с помощью интервального кодера.

Использование ДВП для обработки разностного кадра, полученного после обычной блочной компенсации, не позволяет добиться хорошей эффективности сжатия из-за высокочастотных «всплесков» коэффициSaid A., Pearlman W. A. A New Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees // IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, pp. 243–250, June 1996.

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

ется блочная компенсация с перекрытием. Идея данного метода за- Окно, наложенное ключается в том, что блочные сглажены с помощью интерполяции прогнозных значений яркости на Соседние блоки основе векторов движения соседних Рис. 4. Использование весового окна блоков. До того, как блок из опорного кадра будет перемещен на новое место в прогнозном кадре, на него накладывается весовое «окно», перекрывающее восемь соседних блоков (см. рис. 4). В результате прогноз для пиксела из текущего блока зависит от значений яркости четырех пикселов: пиксела из текущего и трех соседних блоков.

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

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

Для кодирования разностного изображения, так же, как и для сжатия ключевого кадра, используется алгоритм SPIHT. Важная особенность этого алгоритма заключается в том, что на любом этапе декодирования качество отображаемого в этот момент кадра близко к наилучшему для текущего переданного объема информации. Кроме того, SPIHT генерирует вложенный битовый код и может иметь различные критерии остановки работы: по достижении заданного качества сжатия, по достижении заданного размера сжатого файла, а также «смешанные» критерии.

Кодирование может быть остановлено и при превышении лимита времени, отведенного на обработку кадра.

Возможность контроля ошибки восстановления кадра в процессе кодирования, которую дает использование ортогонального ДВП, позволяет при необходимости использовать в методе SPIHT RD-оптимизацию:

функция Лагранжа J = D + R (здесь D — текущее расхождение между исходным и восстановленным вейвлет-спектрами, R — количество бит, переданное декодеру) может вычисляться как после каждого выведенного в поток бита, так и после кодирования очередного битового слоя. При этом дополнительное ограничение сверху битовых затрат на кодирование I- и P-кадров конкретными значениями позволит не допустить превышения максимально возможной скорости битового потока при работе на каналах связи с малой пропускной способностью.

В конце четвертой главы рассматриваются некоторые аспекты реализации разработанного видеокодера на основе цифровых сигнальных процессоров (ЦСП) на примере медиапроцессора TMS320DM642 производства Texas Instruments (США). Также показано, что основные вычислительные процедуры видеокодера (компенсация межкадрового движения, ДВП, SPIHT) легко поддаются распараллеливанию — при использовании соответствующих вычислительных структур это позволит организовать процесс обработки видеопотока более эффективно.

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

Предложенный алгоритм видеокомпрессии был реализован на языке С в среде разработки Microsoft Visual Studio 2005. Моделирование проводилось на персональном компьютере с процессором Intel Core 2 Duo 2,66 ГГц. Для оптимизации процедуры компенсации движения применялся набор SIMD-расширений SSE3, для построения прогнозного кадра с перекрытием использовалась целочисленная арифметика. Лифтингсхема вычисления ДВП, реализованная в видеокодере, позволила сократить время выполнения преобразования в 1,6 раза. Чтобы ускорить работу алгоритма SPIHT, использовалось специальное дерево значимости вейвлет-коэффициентов, кроме того, все динамические списки были заменены на статические. Для обработки видеоизображений применялось 5-уровневое ДВП в биортогональном базисе CDF 9/7. Критерием качества восстановленных тестовых последовательностей являлись покадровые и усредненные значения PSNR.

На рис. 5 приведены результаты кодирования стандартной тестовой последовательности Tennis (150 кадров размера 352224 пиксела) с использованием модифицированной трехслойной схемы компенсации движения и разного числа слоев векторов. Поиск векторов проводился PSNR, дБ Рис. 5. Кодирование последовательности Из графика видно, что трехслойная схема кодирования позволяет повысить эффективность кодирования: на низких битрейтах оправдано использование только одного слоя; далее, при увеличении доступного битового бюджета, можно переходить к обработке следующих слоев.

На рис. 6 представлены реFlower Garden: 1 ключевой кадр (2.0 bpp), = зультаты кодирования стандартной тестовой последова- тельности Flower Garden ( кадров размера 352224 пиксеPSNR, дБ ла) с использованием базовой рования составила 35 кадров/с.

На этом же рисунке приве- Рис. 6. Кодирование последовательности ден график, полученный для свободно распространяемого видеокодера Xvid версии 1.1.3, соответствующего стандарту MPEG-4. Кодирование производилось с предустановленными настройками, соответствующими режиму Real-time (без Bкадров), и заданием битовой скорости.

При использовании модифицированной трехслойной схемы качество восстановленной последовательности падает незначительно (например, на последовательности Flower Garden — не более чем на 0,1 дБ, на последовательности Tennis — 0,2 дБ), при этом скорость выполнения компенсации движения возрастает почти в 3 раза.

Важно отметить, что в предложенном видеокодере битовая скорость была постоянной, тогда как «скачки» битового потока в Xvid достигали 100 % от среднего битрейта, что является неприемлемым для передачи видеоданных в реальном времени по радиоканалу с ограниченной пропускной способностью. Кроме того, разработанный алгоритм позволяет точно и с минимальными задержками регулировать скорость битового потока — данное свойство является критически важным для надежной работы МРК в условиях изменяющейся радиоэлектронной обстановки.

На рис. 6 также представлен график, полученный при кодировании последовательности Flower Garden с использованием модифицированной трехслойной схемы и применением RD-оптимизации не только при поиске векторов, но и в алгоритме SPIHT (обозначен Мод. RD Wavelet).

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

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

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

Основные результаты и выводы В процессе диссертационного исследования были получены следующие основные результаты.

1. Разработан метод, позволяющий повысить качество сжатия в JPEGподобной схеме компрессии. В основе данного подхода лежит построение контекстного прогноза для модулей коэффициентов ДКП, выполненного над блоками обрабатываемого изображения. В качестве прогноза используется функция линейной регрессии, коэффициенты которой определяются с учетом межблочных статистических связей. На тестовых изображениях средний выигрыш относительно JPEG с арифметическим кодированием при фиксированном уровне качества составил 3 %, максимальный — 7,6 %. Алгоритм может быть использован для независимой покадровой обработки видеопоследовательности или кодирования ключевых кадров в видеокомпрессорах, основанных на использовании косинусных преобразований.

Разработан алгоритм глобальной компенсации движения, использующий для определения смещения кадра векторы движения характерных блоков размером 88 пикселов. Выбор характерных блоков производится на основе анализа коэффициентов ДКП. Проведенное тестирование на реальных видеоданных, полученных при различных погодных условиях, подтвердило эффективность алгоритма — было установлено, что при использовании метода полного перебора для нахождения векторов нулевая ошибка определения сдвига практически всегда достигалась с использованием всего 30 блоков видеокадра размером 1024768 пикселов, т. е. менее 0,3 % от общего числа блоков изображения.

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

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

Приведены рекомендации по его эффективной реализации на ЦСП и параллельных вычислительных структурах.

Проведено компьютерное моделирование разработанного видеокодера, позволившее экспериментально оценить его эффективность.

Полученные характеристики сжатия находятся на уровне, соответствующем алгоритмам семейства MPEG-4: по сравнению с видеокодером Xvid максимальный выигрыш в качестве (по PSNR) составил 1 дБ. При этом выходной поток разработанного кодера в отличие от видеокомпрессоров, основанных на ДКП, имеет постоянную битовую скорость, которая в случае необходимости быстро и точно регулируется. Показано, что при снятии ограничения на постоянство битового потока эффективность сжатия может быть дополнительно повышена за счет использования RD-оптимизации не только при поиске векторов движения, но и при кодировании разностного изображения. Аппаратная реализация синтезированного алгоритма видеокомпрессии позволит успешно использовать его для обработки видеоданных в телевизионной системе МРК.

Результаты, полученные в процессе работы над диссертацией, использовались в ряде научно-исследовательских работ, проводимых в НИИ ВСиСУ МИЭТ, и внедрены в виде алгоритмов обработки видеоданных в макетных образцах специализированных МРК, что подтверждает соответствующий акт внедрения.

Список работ по теме диссертации 1. Безуглова Е. А. Контекстное кодирование коэффициентов дискретного косинусного преобразования с учетом межблочной корреляции // Микроэлектроника и информатика — 2004. 11-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. — М.: МИЭТ, 2004. — С. 166.

2. Умняшкин С. В., Безуглова Е. А. Контекстное кодирование коэффициентов дискретного косинусного преобразования на основе межблочной корреляции в JPEG-подобной схеме компрессии // Цифровая обработка сигналов. — № 3. — 2004. — С. 13–17.

3. Коплович Е. А., Умняшкин С. В. Контекстное кодирование коэффициентов дискретного косинусного преобразования с учетом межблочной корреляции // Известия вузов. Электроника. — № 6. — 2004. — С. 78–83.

4. Системы распознавания образов и сопровождения подвижных объектов в сложных условиях: Отчет о НИР / МИЭТ; руководитель С. В. Умняшкин. — № гос. рег. 01200303723, инв. №02200402631. — М., 2004.

5. Системы распознавания образов и сопровождения подвижных объектов в сложных условиях: Отчет о НИР / МИЭТ; руководитель С. В. Умняшкин. — № гос. рег. 01200303723, инв. № 02200501612. — М., 2005.

6. Коплович Е. А. Алгоритм автоматического обнаружения и сопровождения цели в последовательности видеокадров // Микроэлектроника и информатика — 2005. 12-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. — М.: МИЭТ, 2005. — С. 175.

7. Коплович Е. А. Особенности реализации алгоритма автоматического сопровождения подвижных объектов для бортовой системы видеонаблюдения // Микроэлектроника и информатика — 2006. 13-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. — М.: МИЭТ, 2006. — С. 202.

8. Коплович Е. А. Алгоритм оценки смещения видеокадра на основе выбора характерных блоков с использованием коэффициентов ДКП // Интеллектуальные системы в производстве. — 2006. — № 2(8). — С. 25–30.

9. Коплович Е. А. Использование характерных блоков и поля векторов перемещения для глобальной компенсации движения // Микроэлектроника и информатика — 2007. 14-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. — М.: МИЭТ, 2007. — С. 151.

10. Исследование и разработка методов кодирования и передачи динамически меняющихся изображений в системах дистанционного управления перспективными мобильными робототехническими комплексами в экстремальных условиях применения: Отчет о НИР (промежуточ.) / МИЭТ; руководитель В. А. Бархоткин. № гос. рег.

01200 709860, инв. № 02200700241. — М., 2007.

11. Исследование и разработка методов кодирования и передачи динамически меняющихся изображений в системах дистанционного управления перспективными мобильными робототехническими комплексами в экстремальных условиях применения: Отчет о НИР (промежуточ.) / МИЭТ; руководитель В. А. Бархоткин. № гос. рег.

01200 709860, инв. № 02200700242. — М., 2007.

12. Исследование и разработка методов кодирования и передачи динамически меняющихся изображений в системах дистанционного управления перспективными мобильными робототехническими комплексами в экстремальных условиях применения: Отчет о НИР (промежуточ.) / МИЭТ; руководитель В. А. Бархоткин. № гос. рег.

01200 709860, инв. № 05200800112. — М., 2008.

13. Александров А. А., Коплович Е. А., Умняшкин С. В. Алгоритм видеокомпрессии на основе дискретного вейвлет-преобразования с трехслойной схемой кодирования векторов движения // Известия вузов. Электроника. — № 5. — 2008. — С. 69–73.

14. Umnyashkin S., Koplovich E., Alexandrov A. Layered Motion Compensation for a Low Bit Rate Embedded Wavelet Video Coder // Proceedings of the 4th Russian-Bavarian Conference on Biomedical Engineering. — Moscow: MIET, 2008. — pp. 97–100.

Подписано в печать Заказ №. Уч.-изд. л.. Тираж 100 экз. Формат 6084 1/16.

Отпечатано в типографии ИПК МИЭТ.

124498, Москва, Зеленоград, проезд 4806, д. 5, МИЭТ.