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

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

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

□03458544

УПРАВЛЕНИЕ ПАРАМЕТРАМИ АЛГОРИТМА СЖАТИЯ ВИДЕОИНФОРМАЦИИ ПРИ ПЕРЕДАЧЕ ДАННЫХ В СИСТЕМАХ МОБИЛЬНОЙ СВЯЗИ

Специальность: 05.13.01 «Системный анализ, управление и обработка информации (в технике и технологиях)»

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

Санкт-Петербург 2008

003458544

Работа выполнена на кафедре безопасности информационных систем Государственного образовательного учреждения высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмпческого приборостроения» (ГУАП).

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

кандидат технических наук, доцент Тюрликов Андрей Михайлович Официальные оппоненты:

доктор технических наук, профессор Краслльников Николай Николаевич кандидат технических паук, доцент Украинский Олег Владимирович

Ведущая организация:

ФГУП «Лепниградский отраслевой научно-исследовательский институт связи»

Защита состоится «12_> ( 2009 г. в I * час. на заседании

диссертационного совета Д212.233.02 при Государственном образовательном учреждении высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения» по адресу: 190000, г. Санкт-Петербург, ул. Большая Морская, д.67.

С диссертацией можно ознакомиться в библиотеке ГУАП. Автореферат разослан «Я.» 2008 г.

Ученый секретарь диссертационного совета ^.А. Осипов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В области разработки алгоритмов сжатия и передачи видеоданных в системах мобильной связи можно выделить два основных направления исследований: передача по низкоскоростным каналам связи на большие расстояния (например, в системах цифрового телевизионного вещания DVB-H, технологии передачи данных EGPRS для мобильных сетей GSM, технологии WiMAX н др.) и передача видеоданных высокого разрешения с малой задержкой по высокоскоростным каналам связи на небольшие расстояния (например, в системах, основанных на технологии WiFi, UWB и др.). Для первого направления характерна задача разработки алгоритмов, направленных на дальнейшее увеличение степени сжатия передаваемых видеоданных. Для второго направления характерна задача разработки алгоритмов, учитывающих ограничения на вычислительную сложность и объем памяти мобильных устройств.

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

Для достижения поставленной цели были исследованы следующие задачи:

1. Задача повышения эффективности адаптивного арифметического кодирования при сжатии видеоинформации.

2. Задача устранения межкадровой (временной) избыточности видеоинформации для случая передачи по каналам связи с низкой пропускной способностью.

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

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

Объектом исследования является система сжатия и передачи видеои нформации.

Предметом исследования являются методы управления параметрами алгоритма сжатия видеоинформации.

Методологическую и теоретическую основу исследования составили научные труды отечественных и зарубежных ученых как в области теории информации (В.Д. Колесник, Б.Д. Кудряшов, P.E. Кричевский, Б.Я. Рябко, В.К. Трофимов, Ю.М. Штарьков, Р. Галлагер, Т. Лейтон, Г. Лэнгдон, Р. Ривест и др.), так и в области обработки и сжатия видеинформации (H.H. Красильников, И. Добеши, А. Катсаггелос, Д. Марпе, Г. Шустер и др.).

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

Для получения практических результатов были использованы открытые для общего использования кодеки, поддерживающие стандарты сжатия видеоинформации MPEG-2, H.264/AVC и JPEG2ООО. Реализация предложенных алгоритмов была, осуществлена на языке программирования Си в среде Microsoft Visual Studio 2005.

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

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

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

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

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

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

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

Апробация результатов исследования. Основные результаты диссертационной работы докладывались на семинарах кафедры информационных систем и кафедры безопасности информационных систем СПГУАП, а также на следующих научно-технических конференциях: 8я, 9я и 10я научная сессия СПГУАП, «2006 IEEE 10th International Symposium on Consumer Electronics», «XI International Symposium on Problems of Redundancy in Information and Control Systems», «15-я Международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах

телекоммуникаций», «The 15-th International Conference on Communications», «The 11th International Symposium on Wireless Personal Multimedia Communications».

Внедрение результатов исследования. Результаты диссертационной работы используются в учебном процессе кафедры безопасности информационных систем СПГУАП. Разработанный алгоритм управления скоростью кодирования видеоинформации с учетом ограничения на объем памяти кодирующего и декодирующего устройств был использован в рамках проекта «Беспроводной экран» в ЗАО «Интел А/О».

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

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

1. Алгоритм «виртуального скользящего окна» для повышения эффективности адаптивного арифметического кодирования при сжатии видеоинформации.

2. Модифицированный алгоритм «иерархической оценки движения» для устранения межкадровой (временной) избыточности видеоинформации.

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

Структура и объем работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка литературы и четырех приложений. Работа содержит 172 страницы машинописного текста, включая 55 рисунков. Список литературы содержит 82 источника.

СОДЕРЖАНИЕ РАБОТЫ

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

В первом разделе приводится структурная схема кодера видеоинформации.

Основными характеристиками кодера видеоинформации являются скорость кодирования (количество бит, формируемых кодером в единицу времени) и уровень искажения восстановленной видеопоследовательности относительно исходной. В качестве мер искажения в диссертационной работе используются среднеквадратическая ошибка и пиковое отношение сигнал/шум (Peak signal-to-noise ratio, PSNR).

Кодер видеоинформации выполняет следующие основные операции:

1. Устранение статистической избыточности источника видеоинформации.

2. Квантование.

3. Статистическое сжатие без потерь.

4. Управление скоростью кодирования источника видеоинформации в соответствии с заданным критерием искамсения.

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

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

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

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

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

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

Для статистического сжатия без потерь в современных стандартах сжатия видеоинформации (например, Н.264/АУС и ЛРЕС2000) используется контекстный адаптивный двоичный арифметический кодер. Перед арифметическим кодированием недвоичные данные сначала преобразуется в двоичную последовательность, которая при помощи контекстного моделирования разбивается на множество двоичных подпоследовательностей. Затем оценивается вероятность появления единицы в двоичной подпоследовательности, соответствующей каждому контексту.

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

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

Описанные выше свойства могут быть достигнуты при использовании конструкции «скользящего окна», в котором вероятность появления очередного символа а>+1 источника определяется в результате анализа содержимого окна, то есть последовательности символов х^и'+их^у+ь --ч^«, где IV > 1 - длина окна. После кодирования очередного символа содержимое окна сдвигается на одну позицию, новый символ х/+1 заносится в освободившуюся ячейку, а последний символ удаляется. Оценка вероятности появления единицы на выходе

двоичного источника при использовании «скользящего окна» определяется при помощи оценки Кричевского-Трофимова: р(+) = "¡у^2, где п} - число единиц в окне. Основным недостатком данного подхода является необходимость хранения в памяти кодера и декодера IV последних символов для каждого контекста.

Для устранения данного недостатка может быть использована аппроксимация «скользящего окна», при которой в памяти кодера и декодера хранится только число символов в окне, которое вычисляется по некоторому правилу. Одно из таких правил, названное «мнимым скользящим окном», предложено Б.Я. Рябко. Согласно этому правилу, после кодирования символа из окна удаляется не последний, а случайный символ \Ц и число единиц в окне п}+] = п} — у'1 + хи где у* £ {0,1} - случайная величина, которая принимает значение, равное единице с вероятностью ^ и нулю с вероятностью 1 — Аналогичным образом генерируется случайная величина у'1 после декодирования символа 2.'г. Причем для однозначного декодирования значения генерируемых случайных величин должны совпадать у(е = то есть на стороне кодера и декодера должна использоваться специальным образом сформированная псевдослучайная последовательность, что усложняет реализацию алгоритма.

В диссертационной работе показано, как можно избежать генерирования случайной величины. Для этого случайная величина г/( заменяется ее математическим ожиданием. При этом правило пересчета числа единиц в окне изменяется следующим образом: п}+1 = (1 — ^)п} + х^

При таком подходе возникают операции с вещественными числами. Умножив обе части полученного равенства на множитель с можно перейти к целочисленной реализации правила пересчета, которое в диссертационной работе названо «виртуальным скользящим окном». Согласно данному правилу число единиц .5'(+1 в окне из сИ7 ячеек после кодирования очередного символа Х{ пересчитывается по следующему правилу:

, при х1 — 1

(1)

=

Оценка вероятности появления единицы для «виртуального скользящего окна» рг+1 = ¡-¡т. Параметр алгоритма с и начальное значение «о выбирается согласно следующему утверждению.

Утверждение. Для того, чтобы минимальные и максимальные оценки вероятностей для «скользящего окна» и «виртуального скользящего ота» совпадали, необходимо и достаточно, чтобы параметр с = \¥ — 1 — ^ и перед кодированиелг символа 2:1 последовательности х\,хг, ...,хп начальное значение «о € {Ц- — 1, ..., е1У — у + 1}.И При IV » 1, можно считать, что

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

Использование алгоритма «виртуального скользящего окна» позволяет уменьшить скорость кодирования на 0.5-1.5% при фиксированном уровне искажения по сравнению с табличными алгоритмами оценки вероятности, входящими в стандарт Н.264/АУС и ЛРЕС2000. При этом алгоритм «виртуального скользящего окна» может быть реализован как без использования таблиц, так и без операций умножения и деления (при IV = 2!, где г -неотрицательное целое число).

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

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

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

Наиболее распространенный алгоритм блоковой оценки движения упрощенно может быть описан следующим образом. Для каждого блока ¿>п в текущем (кодируемом) кадре с номером п выполняется поиск блока в предыдущем (базовом) кадре с номером к, соответствующий минимуму следующей целевой

функции

•7(У) = Ых,у)~4(х + "х,у + уу)1 (2)

где V = и,/) - вектор движения, < г и |и!;| < г, г - радиус поиска, 3п(х>У) - значение яркости пиксела с координатами г и у в кодируемом кадре, вЦх + ьх,у + Ну) - значение яркости пиксела с координатами х + г>х и у + в базовом кадре. Затем, путем вычитания соответствующих значений яркостей и цветностей пикселов блоков 5„ и формируется разностный блок, который кодируется вместе с вектором движения.

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

П(У) = ^) + А(9).г(У), (3)

где г(у) - битовые затраты на вектор движения, Л(^) - множитель, зависящий от шага квантования ц. При последовательной минимизации (3) вектор движения, найденный для текущего блока, влияет на выбор вектора движения для следующего блока. Это связано с тем, что обычно кодируется не абсолютное значение компонент вектора ух и иу, а разность компонент вектора для текущего блока и вектора для предыдущего блока. Поэтому такая минимизация в общем случае не приводит к минимизации битовых затрат как на векторы движения, так и на разностные блоки для всего кадра.

В ряде работ для ускорения поиска векторов движения предлагется использовать «иерархическую оценку движения» при которой кодируемый и базовый кадры сначала уменьшаются в два раза по высоте и ширине (см. рис. 1). Полученные кадры снова уменьшаются и так далее. Данная процедура выполняется Ь раз, где Ь - параметр алгоритма. В результате формируются £ 4- 1 уровней иерархии, которые нумеруются числами от 0 до ¿, причем исходные (кодируемый и базовый) кадры соответствуют нулевому уровню. Полученные на всех уровнях изображения разбиваются на блоки одинакового размера (например, 16 х 16 пикселов). В результате такого деления каждому блоку на уровне / соответствуют четыре блока на уровне I - 1 и так далее. Затем выполняется поиск вектора движения х{Ь,г,]) для блока с координатами (г,на уровне ¿. Найденный вектор используется при поиске четырех векторов на уровне ¿-1л так далее до нулевого уровня. Множество векторов движения {у(0,г,17')}1 соответствующее нулевому уровню иерархии, используется для формирования разностных блоков. При этом не используются все «промежуточные» векторы движения, найденные на остальных уровнях иерархии.

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

Поиск на уровне 1

Поиск на уровне О

*

—

■■■

Базовый кадр Кодируемый кадр

Рисунок 1 - Иерархическая оценка движения

блоков на нулевом уровне иерархии и так далее, вектор движения может быть использован при формировании 4Ь соответствующих блоков на нулевом уровне иерархии. Совокупность из 41 блоков на нулевом уровне иерархии, которая соответствует одному блоку на уровне иерархии £ называется сегментом. Таким образом, для каждого сегмента кадра возникает множество вариантов разбиения на блоки переменного размера, причем каждому блоку соответствует один вектор движения (см. пример разбиения на рис. 2, а).

Для передачи вида разбиения сегмента используется иерархическое дерево разбиения (см. рис. 2, б) узел которого £(Л, 1,]) принимает значение «О» в случае, если блок {г,з) на уровне I не разбивается и «1», если блок разбивается на четыре блока. Иерархическое дерево кодируется, начиная с корневой вершины. При этом если значение текущего узла равно «О», то дочерние узлы не кодируются.

Векторы движения предлагается кодировать в соответствии с деревом разбиения. Если узел дерева ЩЛ,]) = 1, то кодируется разность между вектором — 1,2 ■ г, 2 - найденным на уровне / — 1, и удвоенным вектором У(М|.7)! найденным на уровне I.

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

Использование предложенного алгоритма для стандарта МРЕС-2 позволяет уменьшить скорость кодирования на 5-40% при фиксированном уровне искажения по сравнению с алгоритмами оценки движения, использующими целевые функции (2) и (3). При этом максимальный выигрыш по сжатию достигается в диапазоне низких скоростей кодирования (см. рис. 3).

/ / я / У

t ч "м \

f \ i i \

.................

Иерархическое дерево разбиения I.

оо оо оо оо оооо оо

а) б)

Рисунок 2 - Иерархическое разбиение сегмента

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

Обозначим за г]' и битовые затраты и уровень искажения на сегмент г соответственно, при использовании шага квантования (¡¡. Обозначим за д = {<7,} вектор, компонента которого означает, что для сегмента г используется шаг квантования д,. Тогда суммарные битовые затраты на кадр составят г(с|) = р'') где N - количество сегментов в кадре. Аналогично, уровень искажения на кадр ¿¡(я) = . Тогда при оценке движения с ограничением количества

бит на кадр необходимо найти вектор q* так, чтобы

d(q*) = min d{q), qe{q)

при условии, что r(q") < r„

(4)

Решение данной задачи может быть получено при помощи метода «лагранжевых релаксаций», предложенного Г. Шустером и А. Катсаггелосом.

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

40 39 38 37 36 35

«container*

33

! ч"

36

35

34

30 29 23 27 26 25

29

27

О 100 200 300 400 500 600 700 800 900 1000

Скорость кодирования, кбит/сек

О 100 200 300 40« 500 600 700 >00 900 1000

Скорость кодирования, кбит/сек

Рисунок з - Сравнительные результаты для MPEG-2

Для передачи видеоданных с одинаковым уровнем искажения предлагается общий ресурс канала связи распределять между видеоисточниками по минимаксному критерию искажения. Пусть имеются 5 видеоисточников. Обозначим за q¡) и г(з,ц1) уровень искажения и битовые затраты на кадр с номером г видеоисточника с номером в при использовании множества шагов квантования qi для сегментов в кадре. Поделим каждую видеопоследовательность на группы из М кадров. Группа кадров с номером ] состоит из номеров кадров = У ■ М,..., + 1) • М — 1}.

Тогда для каждого кадра г, входящего в группу кадров с номером ] источника а у необходимо выбрать множество шагов квантования q* так, чтобы

где / - число кадров в секунду для каждого видеоисточника, с - скорость канала связи.

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

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

Высокая скорость канала связи позволяет осуществлять передачу видеопоследовательностей большого разрешения. При большом разрешении (например, 1920x1080) объем памяти как кодирующего, так и декодирующего устройств оказывается много меньше количества бит, необходимого для хранения одного кадра видеопоследовательности. В этих условиях на

минимизировать max d(s, q,:)

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

Для формулирования требований к алгоритму управления скоростью кодирования в диссертационной работе вводится следующая модель системы передачи. Время передачи по каналу разделено на окна. Все окна имеют одинаковую длительность, равную времени передачи одного пакета. Окна пронумерованы целыми неотрицательными числами, окну с номером í соответствует интервал времени + 1). Далее для краткости изложения окно с номером < называется окном Источник видеоинформации через одинаковые интервалы времени подает на вход кодера очередной сегмент видеокадра. Кодер работает в реальном масштабе времени, поэтому на момент окончания окна 4 в «сглаживающий» буфер передатчика помещается сжатый сегмент размером г4 бит. Из буфера передатчика данные передаются приемнику по каналу связи с постоянной скоростью с. В зависимости от количества бит в буфере передатчика алгоритм управления скоростью кодирования формирует параметры сжатия для следующего сегмента.

Количество бит в буфере передатчика Ье({) в окне £ после помещения в буфер очередного сжатого сегмента объемом г( и передачи по каналу связи изменяется следующим образом:

где с - скорость канала связи.

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

где ДТЙ и ДТ4 - время обработки сегмента кодером и декодером соответственно, АТье - время ожидания передачи сегмента в буфере передатчика, ДТл> -время ожидания воспроизведения сегмента в буфере передатчика, АТС - время передачи сегмента по каналу связи. Известно, что если объем буфера на передающей и приемной сторонах В^пах = В?пах = Ь ■ с, и устройство управления функционирует так, что количество бит в буфере передатчика 6"(¿) < В^пах (буфер передатчика не переполняется), то задержка АТ, вносимая при буферизации данных на приемной стороне, постоянна и равна задержке начальной буферизации Ь.

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

Ье{Ь) = шах{0, ЬеЦ - 1) - с} + 77,

(6)

АТ = АТе + ДГье + АТС + АТи + АТЛ,

(7)

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

где <1[ - уровень искажения для сегмента, передаваемого в окне ¿.

Решение данной задачи может быть найдено при помощи гипотетического алгоритма, который в диссертационной работе назван алгоритмом последовательного поиска. Обозначим за О = {(¿ь <¿2, •••} множество всех возможных уровней искажения для всех сегментов, входящих в видеопоследовательность, упорядоченных по возрастанию. При последовательном поиске каждый сегмент сначала кодируется с искажением не выше (¡1, при этом согласно (6) вычисляется количество бит в буфере передатчика. Если произошло переполнение буфера, то вся процедура начинается сначала и все сегменты кодируется с ошибкой не выше ¿2 и так далее, до тех пор пока при некотором ё £ Э не будет происходить переполнение буфера. Для последовательного поиска доказано следующее утверждение.

Утверждение. Не существует последовательности параметров кодирования, не приводящих к переполнению буфера и имеющих максимальное значение уровня искажения меньше чем д., где (1 - максимальное значение искажения, полученное алгоритмом последовательного поиска.Я

Алгоритм последовательного поиска не может быть реализован на практике, так как при передаче в реальном масштабе времени нет возможности начинать передачу заново после переполнения буфера. Поэтому в диссертационной работе предлагается эвристический алгоритм управления скоростью кодирования, который позволяет получить оценку значения (I алгоритма последовательного поиска в процессе работы системы при ограничениях на память и задержку передачи данных (см. рис. 4). Обозначим эту оценку за Оценивать значение й предлагается следующим образом. До тех пор, пока количество бит в буфере не превысит некоторый порог Вц, все сегменты сжимаются с искажением не более ¿(4) (режим заполнения буфера). Превышение порога Вц означает, что поддержание искажения на уровне ¿(1) невозможно для данной пропускной способности канала связи. Поэтому все сегменты кодируются с максимальным, но приемлемым уровнем искажения (1,:т1Лу до тех пор, пока не произойдет опустошение буфера (режим опустошения буфера). После этого оценка уровня искажения й(Ь) увеличивается на величину Ад, где Ад - параметр алгоритма, и система переходит в режим заполнения буфера. Для данного алгоритма доказано следующее утверждение.

Утверждение. Пусть алгоритму последовательного поиска с объемом буфера В соответствует максимальный уровень искажена д. Тогда, при использовании предложенного алгоритма с порогом Вц = В и й{0) < д, для всех окон t выполняется неравенство д.{1) < д + АйМ

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

(8)

¿(Г ■

Начало

птах {0,6е(/-1)-с>+ ксггровже с искажением' </,

'етр!у

тах{0,Ае(< -1)-с}+г, 5 Декодирование с искажением ¿(/)

<?(г)=Л(*)+Д4/ кодирование с искажением <?(/)

Рисунок 4 - Иллюстрация работы алгоритма управления

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

На видеопоследовательностях, содержащих компьютерную графику предложенный алгоритм управления скоростью кодирования позволяет повысить пиковое отношение сигнал/шум па 5-10дБ относительно исходного алгоритма управления, входящего в стандарт №ЕС2000 (см. «^егН» на рис. 5). При этом для видеопоследовательностей, содержащих только естественные (фотографические) изображения, предложенный алгоритм управления показывает схожие результаты с алгоритмом управления, входящим в стандарт ЛРЕС2000 (см. на рис. 5).

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

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

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

«(езИ»

Последовательный поиск "•"Предложенный алгоритм -®-^РЕС2000

_I_|_■_|—1—I—I_■_1_I_■_■

5 10 15 20 25 30 35 40 45 50 55 60

Номер кадра

«{евС»

-л- Последовательный поиск Предложенный алгоритм -®-^РЕС2000

5 10 15 20 25 30 35 40 45 50 55 60

Номер кадра

Рисунок 5 - Сравнение алгоритмов управления

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

5. Предложена методика тестирования алгоритмов управления скоростью кодирования при помощи модели источник/кодер видеоинформации.

1С

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Беляев Е.А., Тюрликов A.M. Оценка вероятности появления символа при адаптивном двоичном арифметическом кодировании в задачах сжатия видеоинформации // Цифровая обработка сигналов. 2007. №3. С.20-24.

2. Беляев Е.А., Тюрликов A.M. Управление скоростью и ошибкой кодирования в системе сжатия и передачи видеоинформации с ограничениями на память передающего и принимающего устройств // Компьютерная оптика. 2007. Т.31. №2. С.69-76.

3. Беляев Е.А., Тюрликов A.M., Уханова А.С. Адаптивное арифметическое кодирование в стандарте JPEG2000 // Информационно-управляющие системы. 2007. №6. С.28-33.

4. Беляев Е.А. Использование «виртуального скользящего окна» при адаптивном арифметическом кодировании // Научная сессия ГУАП. 2006. С.243-246.

5. Belyaev Е., Gilmut.dinov M., Turlikov A. Binary arithmetic coding system with adaptive probability estimation by «virtual sliding window» /'/ 2006 IEEE 10th International Symposium on Consumer Electronics. 2006. P.194-198.

6. Беляев E.A., Чуйков A.B. Модифицированный алгоритм иерархической оценки движения в задачах сжатия видеоинформации // Научная сессия ГУАП. 2007. С.56-60.

7. Belyaev Е., Turlikov A., Ukhanova A. Rate-distortion control in wavelet-based video compression systems with memory restriction //XI International Symposium on Problems of Redundancy in Information and Control Systems. 2007. P.13-17.

8. Беляев Е.А. Определение момента смены сцепы для улучшения алгоритма управления скоростью и ошибкой кодирования в системе сжатия и передачи видеоинформации при ограничении на память // Научная сессия ГУАП. 2008. С.95-98.

9. Беляев Е.А., Дубков К.С., Вычисление вероятности переполнения сглаживающего буфера передатчика для модели сжатия и передачи видеоинформации // Научная сессия ГУАП. 2008. С.99-101.

10. Беляев Е.А., Тюрликов A.M. Управление скоростью и ошибкой кодирования в системе сжатия и передачи видеоинформации в реальном масштабе времени при ограничении на память // 15-я Международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций». 2008. №1. С.72-73.

11. Belyaev Е., Koski Т., Paavola J., Turlikov A., Ukhanova A. Adaptive power saving on the receiver side in digital video broadcasting systems based on progressive video codecs // The 11th International Symposium on Wireless Personal Multimedia Communications. 2008. Lapland, Finland.

12. Belyaev E., Turlikov A., Ukhanova A. Rate-control algorithms testing by using video source model // The 15-th International Conference on Communications. 2008. St.Petersburg, Russia. P.l-5.

Формат 60x84 1\16. Бумага офсетная. _Тираж 100 экз. Заказ № 650._

Редакционно-издательский центр ГУАП 190000, Санкт-Петербург, Б. Морская ул., 67

ВВЕДЕНИЕ •

РАЗДЕЛ 1. Методы сжатия видеоинформации

1.1 Обобщенная схема системы сжатия видеоинформации.

1.2 Сжатие информации без потерь.

1.2.1 Код Хаффмана.

1.2.2 Арифметическое кодирование.

1.3 Сжатие информации с потерями.

1.3.1 Кодирование источников с заданным критерием качества

1.3.2 Равномерное скалярное квантование и функция скорость/искажение

1.4 Устранение пространственной избыточности видеоинформации

1.4.1 Преобразование цветового пространства.

1.4.2 Дискретное косинусное преобразование

1.4.3 Дискретное вейвлетное преобразование

1.5 Устранение временной избыточности видеоинформации

1.5.1 Оценка движения в задача сжатия видеоинформации

1.5.2 «Быстрые» алгоритмы оценки движения

1.5.3 Алгоритмы оценки движения, учитывающие битовые затраты на векторы движения

1.6 Краткая характеристика стандартов сжатия видеоинформации

1.7 Выводы по разделу.

РАЗДЕЛ 2. Управление арифметическим кодером в задачах сжатия видеоинформации

2.1 Арифметическое кодирование в задачах сжатия видеоинформации

2.2 Практическая реализация двоичного арифметического кодирования.

2.3 Контекстное адаптивное двоичное арифметическое кодирование

2.4 Алгоритм адаптивной оценки с периодическим масштабированием счетчиков

2.5 «Скользящее окно» и его аппроксимации.

2.6 Реализация алгоритмов оценки вероятности при помощи конечного автомата.

2.7 Алгоритм «виртуального скользящего окна».

2.7.1 Описание алгоритма и выбор параметров.

2.7.2 Оценка сложности алгоритма и практические результаты

2.8 Алгоритм адаптивного «виртуального скользящего окна»

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

2.8.2 Универсальное кодирование с учетом функции цели.

2.8.3 Кодирование с учетом функции цели для случая «виртуального скользящего окна»

2.9 Выводы по разделу.

РАЗДЕЛ 3. Алгоритмы оценки движения при сжатии на низких битовых скоростях

3.1 Оценка движения для случая передачи видеоданных по низкоскоростным каналам связи.

3.2 Алгоритм «иерархической оценки движения».

3.3 Модифицированный алгоритм «иерархической оценки движения»

3.3.1 Иерархическое разбиение Р-кадра

3.3.2 Кодирование векторов движения Р-кадра.

3.3.3 Оценка движения, разбиение и кодирование векторов движения для В-кадров.

3.4 Модифицированный алгоритм «иерархической оценки движения» с ограничением.

3.4.1 Случай ограничения количества бит или уровня искажения на кадр.

3.4.2 Случай минимаксного ограничения уровня искажения на кадр

3.5 Оценка сложности алгоритма и практические результаты

3.6 Управление скоростью кодирования для группы видеоисточников

3.6.1 Управление скоростью кодирования для одного видеоисточника.

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

3.7 Выводы по разделу.

РАЗДЕЛ 4. Управление скоростью кодирования при ограничениях на объем памяти и задержку

4.1 Особенности систем сжатия и передачи с ограничением на память

4.2 Задержка в системе сжатия и передачи видеоинформации

4.3 Управление скоростью кодирования по минимаксному критерию искажения.

4.3.1 Постановка минимаксной оптимизационной задачи.

4.3.2 Решение минимаксной задачи последовательным поиском

4.3.3 Алгоритм управления скоростью кодирования при ограничении на память.

4.4 Управление скоростью кодирования по минимаксному критерию искажения с учетом «смены сцены».

4.4.1 Постановка расширенной минимаксной оптимизационной задачи

4.4.2 Определение момента «смены сцены»

4.4.3 Алгоритм управления скоростью кодирования при ограничениях на память с учетом «смены сцены»

4.5 Выбор параметров алгоритмов и практические результаты

4.6 Методика тестирования алгоритмов управления при помощи модели источник/кодер видеоинформации.

4.6.1 Недостатки традиционных подходов к тестированию алгоритмов управления скоростью кодирования

4.6.2 Допущения модели источник/кодер видеоинформации

4.6.3 Классификация состояний видеоисточника.

4.6.4 Выбор модели функции скорость/искажение.

4.6.5 Методика тестирования алгоритмов управления

4.7 Выводы по разделу.

Актуальность темы исследования

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

В области разработки алгоритмов сжатия и передачи видеоданных в системах мобильной связи можно выделить два основных направления исследований: передача по низкоскоростным каналам связи на большие расстояния (например, в системах цифрового телевизионного вещания DVB-H, технологии передачи данных EGPRS для мобильных сетей GSM, технологии WiMAX и др.) и передача видеоданных высокого разрешения с малой задержкой по высокоскоростным каналам связи на небольшие расстояния (например, в системах, основанных на технологии WiFi, UWB и др.). Для первого направления характерна задача разработки алгоритмов, направленных на дальнейшее увеличение степени сжатия передаваемых видеоданных. Для второго направления характерна задача разработки алгоритмов, учитывающих ограничения на вычислительную сложность и объем памяти мобильных устройств.

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

Для достижения поставленной цели были исследованы следующие задачи:

1. Задача повышения эффективности адаптивного арифметического кодирования при сжатии видеоинформации.

2. Задача устранения межкадровой (временной) избыточности видеоинформации для случая передачи по каналам связи с низкой пропускной способностью.

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

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

Объектом исследования является система сжатия и передачи видеоинформации.

Предметом исследования являются методы управления параметрами алгоритма сжатия видеоинформации.

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

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

Для получения практических результатов были использованы открытые для общего использования кодеки, поддерживающие стандарты сжатия видеоинформации MPEG-2, H.264/AVC и JPEG200Û. Реализация предложенных алгоритмов была осуществлена на языке программирования Си в среде Microsoft Visual Studio 2005.

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

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

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

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

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

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

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

Алгоритм «виртуального скользящего окна», модифицированный алгоритм «иерархической оценки движения» и алгоритм управления скоростью кодирования для группы видеоисточников могут быть использованы для повышения ээфективнети передачи видеоданных по каналам связи с низкой пропускной способностью. Областью применения данных алгоритмов являются системы цифрового телевизионного вещания для мобильных устройств DVB-H, технология передачи данных EGPRS для мобильных сетей GSM, телекоммуникационная технологии WiMAX и др.

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

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

Основные результаты диссертационной работы докладывались на семинарах кафедры информационных систем и кафедры безопасности информационных систем СПбГУАП, а также на следующих научно-технических конференциях:

• 8я, 9я и 10я научная сессия СПбГУАП (2006 - 2008 гг.);

• «10th IEEE International Symposium on Consumer Electronics», 2006 г.;

• «XI International Symposium on Problems of Redundancy in Information and Control Systems», 2007 г.;

• «15-я Международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», 2008 г.;

• «The 15-th International Conference on Communications», 2008 г.;

• «The llth International Symposium on Wireless Personal Multimedia Communications», 2008 r.

Внедрение результатов исследования Результаты диссертационной работы используются в учебном процессе кафедры безопасности информационных систем СПбГУАП. Разработанный алгоритм управления скоростью кодирования видеоинформации с учетом ограничения на объем памяти кодирующего и декодирующего устройств был использован в рамках проекта «Беспроводной экран» в ЗАО «Интел А/О».

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

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

1. Алгоритм «виртуального скользящего окна» для повышения эффективности адаптивного арифметического кодирования при сжатии видеоинформации.

2. Модифицированный алгоритм «иерархической оценки движения» для устранения межкадровой (временной) избыточности видеоинформации.

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

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

4.7 Выводы по разделу

По материалам раздела могут быть сформулированы следующие выводы:

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

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

3. Практические результаты использования предложенных алгоритмов приведены для открытой реализации стандарта сжатия видеоинформации ^ЕС2000. На тестовых видеопоследовательностях продемонстрирована эффективность алгоритмов, которые позволяют повысить пиковое отношение сигнал/шум передаваемой видеопоследовательности, содержащей фрагменты компьютерной графики, на 5-10 дБ при фиксированной скорости канала и задержке по сравнению с известными алгоритмами. При этом показано, что наиболее эффективен алгоритм управления с детектированием смены сцены;

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

5. Предложена методика тестирования алгоритмов управления при помощи модели источник/кодер видеоинформации.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

5. Рассмотрена задача управления скоростью кодирования для группы видеоисточников по минимаксному критерию искажения.

Предложено решение задачи на основе модифицированного алгоритма «иерархической оценки движения».

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

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

1. Оппенгеим Э. Применение цифровой обработки сигналов.-М.:«Мир», 1980.

2. Красильников H.H., Цифровая обработка изображений.-М.:Вузовская книга, 2001г.

3. Колесник В.Д., Полтырев Г.Ш. Курс теории информации. М., Наука, 1982.

4. Галлагер Р. Теория информации и надежная связь. М., Советское радио, 1974.

5. Гонсалес Р., Вудс Р., Цифровая обработка изображений. М.,Техносфера, 2005.

6. Прокис Д. Цифровая связь М., Радио и связь, 2000.

7. Хаффман Д.А. Построение кодов с минимальной избыточностью // Кибернетический сборник. 1961. №3. С.79-87.

8. Рябко Б.Я. Сжатие данных при помощи «мнимого скользящего окна» // Проблемы передачи информации. 1996. Т.32. №2. С.22-30.

9. Рябко Б.Я. Эффективный метод арифметического кодирования для источников с большими алфавитами // Проблемы передачи информации. 1999. Т.35. №4. С.95-108.

10. Штарьков Ю.М. Функции цели и последовательное оценивание модели источника при универсальном кодировании // Проблемы передачи информации. 1999. Т.35. №3. С.99-111.

11. Семенюк В.В. Метод адаптивного кодирования двоичной информационной выборки / / Известия вузов. Приборостроение. 2004. Т.47. №5. С.36-41.

12. Беляев Е.А. Использование «виртуального скользящего окна» при адаптивном арифметическом кодировании // Научная сессия ГУАП. 2006. Сб. докл. ГУАП, СПб.

13. Беляев Е.А., Тюрликов A.M. Оценка вероятности появления символа при адаптивном двоичном арифметическом кодировании в задачах сжатия видеоинформации // Цифровая обработка сигналов. 2007. №3. С.20-24.к L

14. Беляев Е.А., Тюрликов A.M., Уханова A.C. Адаптивное арифметическое кодирование в стандарте JPEG2000 // Информационно-управляющие системы. 2007. №6. С.28-33.

15. Беляев Е.А., Чуйков A.B. Модифицированный алгоритм иерархической оценки движения в задачах сжатия видеоинформации // Научная сессия ГУАП, 2007. Сб. докл./ ГУАП. СПб. С.56-60.

16. Беляев Е.А., Тюрликов A.M. Алгоритмы оценки движения в задачах сжатия видеоинформации на низких битовых скоростях // Компьютерная оптика Принято к публикации.

17. Беляев Е.А., Тюрликов A.M. Управление скоростью и ошибкой кодирования в системе сжатия и передачи видеоинформации с ограничениями на память передающего и принимающего устройств // Компьютерная оптика. 2007. Т.31. №2. С.69-76.

18. Беляев Е.А. Определение момента смены сцены для улучшения алгоритма управления скоростью и ошибкой кодирования в системе сжатия и передачи видеоинформации при ограничении на память // Научная сессия ГУАП. 2008. 4.1. С.95-98 Сб. докл. ГУАП, СПб.

19. Беляев Е.А., Дубков К.С., Вычисление вероятности переполнения сглаживающего буфера передатчика для модели сжатия и передачи видеоинформации // Научная сессия ГУАП. 2008. 4.1. С.99-101 Сб. докл. ГУАП. СПб.

20. Кудряшов Б.Д. Конспект лекций по теории информации (черновик) http://k51.spb.ru/article.php?art=105&s=2.

21. Belyaev E., Turlikov A., Ukhanova A. Rate-control algorithms testing by using video source model // The 15-th International Conference on Communications. 2008. St.Petersburg, Russia.

22. Digital compression and coding of continuous-tone still images. ITU-T and ISO/IEC JTC 1, ITU-T Recommendation T.81 and ISO/IEC 10918-1, 1992.

23. JPEG 2000 image coding system: Core coding system, itu-t recommendation t.800 and iso/iec 15444-1. ITU-T and ISO/IEC JTC 1, 2000.

24. ATSC Digital Television Standard. ATSC standard A/53A, 2001.

25. Advanced video coding for generic audiovisual services. ITU-T Recommendation H.264 and ISO/IEC 14496-10 (AVC), 2003.

26. ETSI EN 302 304 VI.1.1 (2004-11). Digital video broadcasting (DVB): transmission system for handheld terminals (DVB-H). European Telecommunications Standards Institute, 2004.

27. IEEE Std IEEE 802.16-2004 (Revision of IEEE Std IEEE 802.16 2001). IEEE Standard for Local and metropolitan area networks. Part 16: Air Interface Fixed Broad-band Wireless Access Systems // IEEE. 1, 2004.

28. GSM-05 Series, Digital Cellular Telecommunications System (Phase 2+), 8.4.0 ed. ETSI, May 2000.

29. IEEE P802.11n D1.0 Draft Amendment, March 20061.I.

30. Federal Communications Commission, "Revision of Part 15 of the Commission's rules regarding Ultra-Wideband transmission systems," FCC 02-08, Apr. 2002.

31. Smulders P.F. 60 GHz radio: prospects and future directions // IEEE Benelux Chapter Symposium on Communications in Proceedings of and Vehicular Technology. 2003.

32. H.264/AVC JM Reference Software, http://iphome.hhi.de/suehring/tml/.

33. JPEG-2000 Software, http://www.ece.uvic.ca/ mdadams/jasper/.

34. MPEG-2 TM5 Rate Control and Quantization Control. http://www.mpeg.org/mpeg/.

35. Accame M., De Natale F.G.B., Giusto D.D. Hierarchical motion estimator (HME) for block-based video coders // IEEE Transactions on Consumer Electronics. 1997. №43. P. 1320-1330.

36. Antonini M., Barlaud M., Mathieu P., Daubechies I. Image coding using wavelet transform image processing // IEEE Transactions on Image Processing. 1992. V.l, Is.2. P.205-220.

37. Bottou L., Howard P., Bengio Y. The Z-coder adaptive binary coder // Proc. IEEE Data Compression Conference. 1998. P. 13-22.

38. Ce Zhu, Xiao Lin, Lap-Pui Chau, Keng-Pang Lim, Hock-Ann Ang Choo-Yin Ong A novel hexagon-based search algorithm for fast block motion estimation // 2001 IEEE International Conference on Acoustics, Speech, and Signal Processing. 2001. №3. P.1593-1596.

39. Nam Ik Cho, San Uk Lee Fast algorithm and implementation of 2-d discrete cosine transform // IEEE Transactions on Circuits and Systems. 1991. V.38. P.297-305.

40. Coifman R.R., Wickerhauser M.V. Entropy-based algorithms for best basis selection // IEEE Transactions on Information Theory. 1992. V.38. P.713-718.

41. Duttweiler D.L., Chamzas C. Probability estimation in arithmetic and adaptive-huffman entropy codcrs // IEEE Transactions on Image Processing. 1995. V.4. P.237-246.

42. Eeckhaut H., Schrauwen B., Christiaens M.,Van Campenhout J. Tuning the M-coder to improve dirac's entropy coding // WSEAS transactions 011 Information Science and Applications. 2005. V.2. P. 1563-1571.

43. Howard P.G., Vitter J. S. Pracical implementations of arithmetic coding // Kluwer Academic Publishers. 1992. P.S5-112.

44. Injong Rhee, Graham R.M., Muthukrish-nan S., Packwood R.A. Quadtree-structured variable-size block-matching motion estimation with minimal error // IEEE Tranactions On Circuits And Systems for A;ideo Technology. 2000. V.10. P.42-50.

45. ISO/IEC 13818 (MPEG-2): Generic coding of moving pictures and associated audio information, 1994.

46. Jelinek F. Buffer overflow in variable-length coding of fixed rate sources // IEEE Trans. Inform. Theory. 1968. V.14. P.490-501.

47. Jain J.R., Jain A.K. Displacement measurement and its application in interframe image coding // IEEE Transactions on Communications. 1981. V.29. P.1799-1808.

48. Kossentini F., Lee Y.W., Smith M.J.T, Ward R.K. Predictive RD optimized motion estimation for very low bit-rate video coding // IEEE Journal On Selected Areas in Communications. 1997. V.15. P.1752-1763.

49. Krichevski R. E., Trofimov V. E. The performance of universal encoding // IEEE Trans. Inform. Theory. 1981. V.27. P.199-207.

50. Leighton F.T., Rivest R. Estimating a probability using finite memory // IEEE Trans. Inform. Theory. 1986. V.32. №6. P.733-742.

51. Li Zhu, Schuster G.M., Katsaggelos A.K. Minmax optimal video summarization // IEEE Transactions on Circuits and Systems for Video Technology. 2005. V.15. P.1245-1256.

52. Lloyd S.P. Least square quantization in PCM // IEEE Transactions on Information Theory. 1982. V.28. P.129-137.

53. Lopes F., Ghanbari M. Hierarchical motion estimation with spatial transforms // 2000 International Conference on Image Processing. 2000. V.2. P.558-561.1. 1.

54. Lurng-Kuo, Liu E.F. A block-based gradient descent search algorithm for block motion estimation in video coding // IEEE Transactions on Circuits and Systems for Video Technology. 1996. V.6. P.419-422.

55. Dai M., Loguinov D., Radha H. Rate-distortion modeling of scalable video coders // International Conference on Image Processing. 2004. V.2. P.1093-1096.

56. Dai M., Loguinov D. Analysis and Modeling of MPEG-4 and H.264 MultiLayer Video Traffic // IEEE INFOCOM. 2005.

57. Mallat S. A theory of multiresolution signal decomposition: The wavelet representation // IEEE Transactions on Pattern Anal. Mach. Intell. 1989. V.ll. P. 674-693.

58. Marpe D., Schwarz H., Blattermann G., Heising G., Wiegand T. Context-based adaptive binary arithmetic coding in JVT/H.26L // 2002 International Conference on Image Processing. 2002. P.513-516.

59. Marpe D., Schwarz H., Wiegand T. Context-based adaptive binary arithmetic coding in the H.264/AVC video compression standard // IEEE Transactions on Circuits and Systems for Video Technology. 2003. V.7. P.620-636.

60. Marpe D., Wiegand T. A highly efficient multiplication-free binary arithmetic coder and its application in video coding // 2003 International Conference on Image Processing (ICIP'03). 2003. P.263-266.

61. Max J. Quantizing for minimum distortion // IEEE Transactions on Information Theory. 1960. V.6. P. 16-21.

62. Meron E., Feder M. Finite-memory universal prediction of individual sequences // IEEE Trans. Inform. Theory. 2004. V.50. P. 1506-1523.

63. Cherniavsky N.,Shavit G., Ringenburg M.F., Ladner R.E., Riskin R.E. Multistage: A minmax bit allocation algorithm for video coders // IEEE Transactions on Circuits and Systems for Video Technology. 2007. V.17. P.59-67.

64. Pennebaker W.B., Mitchel J.L., Langdon G.G., Arps R.B. An overview of the basic principles of the q-coder adaptive binary arithmetic coder // IBM J. Research and Development. 1988. V.32. №.6. P.717-726.

65. Reibman A.R., Haskell B.G Constraints on variable bit-rate video for atm networks // IEEE Transactions on Circuits and Systems for Video Technology. 1992. V.2. P.361-372.

66. Lucantoni D.M.,Neuts M.F, Reibman A.R. Methods for performance evaluation of VBR video traffic models // IEEE Transactions on Networking. 1994. V.2. P.176-180.

67. Schuster G.M., Katsaggelos A.K. Rate-Distortion Based Video Compression, Optimal Video Frame Compression, and Object Boundary Encoding, Kluwer Academic Publisher, 1997.

68. Schuster G.M., Katsaggelos A.K. A theory for the optimal bit allocation between displacement vector field and displaced frame difference // IEEE Journal On Selected Areas in Communications. 1997. V.15. P. 1739-1751.

69. Schuster G. M., Katsaggelos A.K. A video compression scheme with optimal bit allocation among segmentation, motion, and residual error // IEEE Transactions On Image Processing. 1997. V.6. P.1487-1502.

70. Schuster G.M., Katsaggelos A.K. An optimal quadtree-based motion estimation and motion-compensated interpolation scheme for video compression // IEEE Transactions On Image Processing. 1998. V.6. P.1505-1523.

71. Siu-Wai Wu, Gersho A. Joint estimation of forward and backward motion vectors for interpolative prediction of video // IEEE Transactions on Image Processing. 1994. V.3. P.684-687.

72. Taubman D. High performance scalable image compression with EBCOT // IEEE Transactions on Image Processing. 2000. V.9. №7. P.1158-1170.

73. Viteribi A., Omura J. A new rate control scheme using a new rate distortion model // Principle of Digital Communication and Coding, New York: McGraw-Hil, 1979.

74. Wiegard T., Girod B. Lagrange multiplier selection in hybrid video coder control // 2001 International Conference on Image Processing. 2001. V.3. P. 542-545.

75. Withers D. The ELS-coder: a rapid entropy coder // Proc. IEEE Data Compression Conference. 1997. P.495.

76. Witten I.C., Neal R.M., Cleary J.G. Arithmetic coding for data compression // Communication of the ACM. 1987. V.30. P.520-540.

77. Zandi A., Langdon G. Adaptation for non-stationary binary sources for data compression // 29th Asilomar Conference on Signals, Systems and Computers. 1996. P.224-228.