Алгоритм адаптации видеопотока

Алгоритм адаптации видеопотока

Содержание

Введение

1. Обзор существующих решений

2. Организация видеоданных

2.1 Стандарт H.264. Общие сведения

2.2 Группа кадров

2.3 Методы восстановления видеоряда при потерях в канале передачи данных

2.4 Битовая скорость данных

3. Алгоритм адаптации потока видеоданных

3.1 Клиент-серверная архитектура

3.2 Задачи и ограничения алгоритма

3.3 Протокол взаимодействия

3.4 Общий вид алгоритма

3.5 Уровни скорости передачи данных источника

3.6 Робастная оценка потерь. Допустимые потери

4. Помехоустойчивое кодирование

4.1 Существующие решения

4.2 Метод наложения избыточности

4.3 Внедрение помехоустойчивого кодирования в алгоритм адаптации видеопотока

Заключение

Список литературы

Введение

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

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

К чему же с практической точки зрения сводится разработка алгоритма адаптации видеопотока в канале передачи данных, позволяющая частично или полностью решить данную проблему? Видеоданные перед отправкой в сеть разбиваются на пакеты и от источника отправляются к приемнику. Даже из-за одного потерянного пакета качество видеоряда ухудшается настолько, что пользователь не может воспринимать информацию, при условии, что отключены стандартные методы восстановления видеоряда при потерях в канале передачи данных. Современные технологии могут позволить до 0,5 - 1 % потерь. Одним из следствий из теоремы Шеннона [2] является тот факт, что при бесконечно большом запасе времени для передачи данных (пакета), мы можем гарантировать передачу данных с вероятностью близкой к единице, при условии, что вероятность потерь так же близка к единице. Но одной из особенностей «задачи видеоконференции» является ограничение по времени кодирующего устройства до 40 - 60 мс, а в облачных сервисах - до 15 мс, а так же отсутствие буферизации данных. Это означает, что каждые T мс кодирующее устройство генерирует группу пакетов видеоданных, которые незамедлительно должны отправиться к приемнику. Но если мы имеем такие жесткие ограничения, то какой допустимый максимальный процент потерь пакетов мы можем позволить при передаче видеоданных в сетевом канале?

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

1. Обзор существующих решений

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

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

Анализ патентов, готовых решений в этой области проводился в несколько этапов:

. ручной поиск патентов с использованием инструмента Google Search Patent;

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

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

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

Результаты 1-го и 2-го этапов сводились к патентам в области «облачных» технологий, которые носят более общий характер, например работа «Quality of service management system and method of forward error correction» Atul Apte [4].

Результаты 3-го и 4-го этапов оказались малоприменимы из-за ряда вводимых ограничений на алгоритм адаптации потока видеоданных (подробнее см. гл. 4.2). Так, например, в ходе работы К.В. Шинкаренко, А.М. Корикова, «Помехоустойчивое кодирование данных мультимедиа данных в компьютерных сетях» [5] удалось уменьшить буферизацию данных до параметра k = 100 - 1000 пакетов (для сравнения в кодах Лаби и их модификациях значение k достигает 10000), что составляет буферизацию от 1,5 - 2 с и является неприемлемым для «облачных» сервисов.

2. Организация видеоданных

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

Первый параметр - формат пикселя. Пиксель - наименьший логический элемент двумерного цифрового изображения. Если мы говорим о единице видеоряда - кадре, то он состоит из пикселей, которые могут быть представлены некоторым количеством бит информации. Способ представления, глубина цвета (возможность представления большего количества оттенков) полностью зависят от формата пикселя. Формат пикселя - это структура данных о цвете, и способ их интерпретации. Для несжатого (исходного или восстановленного кадра) наиболее распространенный формат - RGB (от англ. Red Green Blue). В данной цветовой модели один пиксель состоит из трех каналов. При смешении основных цветов получаются новые цвета, так, например, при смешении синего и красного мы получаем пурпурный цвет. Широкое распространение в вычислительной технике и способах представления данных получили форматы семейства RGB - ARGB (от англ. Alpha, составляющая, характеризующая степень прозрачности пикселя), RGB32 (в данном случае цифра 32 указывает на количество отведенных бит для интерпретации одного пикселя) и другие. Количество бит, отведенное под представление одного пикселя, характеризует такую величину, как глубина цвета. Чем эта величина больше, тем изображение лучше воспринимается человеческим глазом. Существуют и качественно другие форматы, например, формат YUV, в котором цвет представляется как 3 компоненты - яркость (Y) и две цветоразностных (U, V).

Говоря о передачи видеоданных или изображений, следует упомянуть формат YCbCr семейства форматов YUV. Известно, что органы зрения человека менее чувствительны к цвету предметов, чем к их яркости (светимости). В цветовом пространстве RGB все три цвета считаются одинакового важными и обычно сохраняются с одинаковой глубиной цвета (количеством отводимых бит на канал). Формат YCbCr позволяет интерпретировать точно такие же данные более эффективно (т.е. меньшим количеством бит), отделив яркость от цветовой информации и представив ее с большим разрешением, нежели цветовую составляющую. Это позволяет сократить объем информации для представления хроматических компонент без заметного ухудшения качества передачи цветовых оттенков изображения. Использование большего разрешения для компоненты яркости по сравнению с хроматическим и компонентами является простым, но весьма эффективным приемом при сжатии изображений.

Второй параметр - размер кадра, или разрешение. Разрешение характеризуется количеством пикселей, отводимых под ширину и высоту изображения. Соответственно, чем больше величина произведения ширины, высоты и глубины цвета, тем больше данных необходимо сжать. Величины разрешений для различных стандартов телевещания следующие: 640х480, 720х480, 720х576, 1280х720, 1920х1080.

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

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

Основная проблема, с которой сталкиваются сервисы, транслирующие видеоданные в интернете - большой размер передаваемой информации. Так, например 30 с видео в разрешении 720p (1280х720, прогрессивная развертка) в несжатом формате занимало бы место на диске равное примерно 30 Гб информации. Очевидно, что столь огромный объем данных передать в любом телекоммуникационном канале в условиях современного состояния технологий связи невозможно. С целью сокращения объема данных, передаваемых в сети, записываемых на носители, были изобретены стандарты сжатия видеоданных и изображений.

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

В общем случае процесс передачи сжатых данных можно представить следующим образом. Источник изображения генерирует несжатый поток данных. Это означает, что каждый кадр сразу же уходит на вход кодирующего устройства (след. пункт), или же помещается в общий для источника изображения и кодирующего устройства буфер обмена данными. В качестве источника изображения может выступать как декодирующее устройство, например, если мы говорим о процессе перекодирования данных из модного формата в другой [6] (англ. transcoding), данные, полученные от видеокамеры в реальном времени, так и данные, полученные захватом с целевой поверхности приложения (или рабочего стола, если мы говорим об удаленном доступе) операционной системы.

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

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

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

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

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

На сегодняшний день самым распространенным стандартом видеосжатия является стандарт AVC/H.264 [6]. В рамках данной дипломной работы использовались потоки видеоданных, сжатых по стандарту H264. В данной главе будут рассмотрены составляющие стандарта, которые влияют на разработанный алгоритм адаптации потока видеоданных. Так же, поскольку представленный в данной дипломной работе алгоритм адаптации потока видеоданных изменяет входные параметры кодирующего устройства (см. гл. 4), в рамках главы 3 рассмотрено только описание кодирующего устройства, а так же структуры данных и механизмов борьбы с потерями данных. Ответная реакция декодирующего устройства заключается в изменении параметров инициализации и не рассматривается в данной дипломной работе.

.1 Стандарт H.264. Общие сведения

В 2003 году группой экспертов по видеокодированию (Video Coding Experts Group, VCEG) - рабочей группой международного союза по телекоммуникациям (International Telecommunication Union, ITU-T) была инициирована разработка стандарта H264, который был нацелен на эффективное и надежное сжатие видеоданных. Ключевыми признаками стандарта являются следующие элементы: эффективность сжатия (обеспечивающая значительное улучшение показателя сжатия данных по сравнению с другими стандартами), эффективность передачи данных (с множеством встроенных деталей, поддерживающих надежную и устойчивую передачу по различным каналам и сетям) и ориентированность на популярных приложениях видеосжатия.

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

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

Видеокодек - программа, алгоритм, реализующий процесс сжатия (кодирования), и восстановления (декодирования) данных в рамках одного или нескольких стандартов видеосжатия. Иначе: видеокодек - это объединение кодирующего алгоритма и декодирующего в одно программное решение. Если рассматривать копии видео данных на входе (кодирующее устройство) и выходе (декодирующее устройство) кодека для одного кадра, то процесс сжатия данных является процессом сжатия данных без потерь тогда, когда эти копии полностью совпадают, иначе - процессом сжатия данных с потерями. Качество переданной информации в последнем случае определяется битовой разностью двух видеокопий так, что чем больше разность копий, тем больше отличие исходного кадра от восстановленного. Важно отметить, что качество переданной информации обратно пропорционально зависит от степени сжатия, а значит, при большем коэффициенте сжатия генерируется менее качественный видеоряд. В рамках данной главы говоря о видеокодеке, будем говорить о видеокодеке стандарта H.264.

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

Кодирующее устройство состоит из трех основных функциональных единиц:

-временная модель;

-пространственная модель;

-энтропийный кодер.

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

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

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

Рис. 1. Последовательность единиц данных NAL

Стандарт H.264 делает различие между модулем кодирования видео VLC (англ. Video Layer Coding) и абстрактным сетевым модулем NAL (англ. Network Abstract Layer). Выходом процесса кодирования и служат данные типа VLC - последовательность битов, представляющая закодированные видеоданные, которые преобразуются в единицы NAL перед передачей или хранением. Каждая единица NAL состоит из байтовой последовательность данных RBSP (англ. Raw Bytes Sequence Payload), т.е. из цифровой информации, соответствующей закодированной информации, а так же из заголовка, содержащего сведения об этой последовательности данных. Закодированная видеопоследовательность представлена в виде ряда единиц NAL (рис. 1), который можно переслать по сети пакетной передачи данных или по каналу связи битовых потоков, а также сохранить в файле. Целью раздельной спецификации модулей VCL и NAL является разграничение процесса видеокодирования (VCL) и подготовки данных к их транспортировки или хранению (NAL).

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

В стандарте H.264 определены три профиля, каждый из которых поддерживает определенный набор функций кодирования, например, таких, как методы кодирования на основе P-слоев и I-слоев (это будет рассмотрено ниже), контекстное арифметической энтропийное кодирование CABAC (англ. Context-Based Adaptive Arithmetic Coding), избыточные слои, группы слоев, взвешенный прогноз и другие [6]. Эти наборы функций обозначают, что требуется от кодера и декодера, от видеокодека в целом, для его подчинения выбранному профилю - базовому, расширенному, или основному. При этом пределы производительности кодеков конкретного профиля определяются множеством факторов, которые накладывают ограничения на такие параметры кодирования, как скорость отбора и обработки частей кадра, размер кадра, битовая скорость кодирования и объем требуемой памяти. Потенциальными сферами применения базового профиля являются видеотелефония, организация видеоконференций и беспроводных коммуникаций, а так же решение любой задачи близкой к задаче транспортировки потока видеоданных с минимальными задержками на кодирование-декодирование и транспортировку в сети (англ. Low-latency streaming). Основной профиль применим для телевизионного вещания (разрешены задержки порядка 2 - 5 минут, означающие допустимую буферизацию данных) и хранения видеоданных, а расширенный - в потоковом вещании видеоданных. Хотя эти профили и являются определенными в стандартах, производители видеокодеков в своих продуктах реализуют значительно большее количество доступных профилей, включающих в себя различные наборы методов и инструментов кодирования в рамках стандарта H.264. Количество профилей для видеокодека стандарта H.264 на сегодняшний день доходит до 12 - 16 профилей (например открытая библиотека x264 для языка С++).

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

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

При попадании на вход кодирующего устройства исходный (т.е. несжатый) кадр в первую очередь проходит конвертацию цветового пространства в YCbCr. Далее кадр разбивается на некоторое количество прямоугольных блоков, или далее по тексту макроблоков, размером Ia на Ib, где Iа и Ib - соответственно ширина и высота макроблока, а Ix (x = a,b) может принимать значения 2, 4, 8, 16, определяемые реализацией кодирующего устройства. До сжатия энтропийным кодером (не путать с кодером, который является часть видеокодека, энтропийный кодер - часть кодирующего устройства стандарта H.264), битовая последовательность данных формата H.264 так же остается сегментированной по макроблокам. Макроблок - минимальная единица, которой оперирует кодирующее устройство, при этом на выходе кодирующего устройства кадр качественнее и большего размера тогда, когда Ix меньшее из возможных значений.

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

Слой (англ. Slice) - это некоторая область на кодируемом снимке, в рамках которой макроблоки могут иметь ссылки друг на друга, либо на макроблоки из других кадров. Алгоритм кодирования минимизирует возможность распространения ссылок между макроблоками, принадлежащим разным слоям одного кадра. Наиболее часто используемые кодирующими устройствами способы разделения кадра на слои: перемешивание (рис. 2), рассеивание (рис. 3), передний план и задний план (рис. 4).

Рис. 2. Способ разделения кадра на слои - перемешивание. Цифрами обозначены различные слои.

Рис. 3. Способ разделения кадра на слои - рассеивание. Цифрами обозначены различные слои.

Рис. 4. Способ разделения кадра на слои - передний план и задний план. Цифрами обозначены различные слои.

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

Кодирующее устройство H.264 может использовать один или два списка снимков в качестве ссылок для формирования прогноза компенсации движения при кодировании макроблоков или их частей. Порядок и способы формирования этих списков в данной дипломной работе не будут рассмотрены [7]. Это позволяет кодирующему устройству искать лучшую «схожесть» частей текущего макроблока в более широком множестве снимков по сравнению с использованием, например, только одного предыдущего снимка. Таким образом, и кодирующее и декодирующее устройство строят по несколько одинаковых списков ссылочных кадров, которые используются при кодировании или декодировании нового.

Тип кадра (см. далее) определяет типы используемых слоев, а тип используемого слоя, определяет типы макроблоков и способы нахождения ссылок для них. В стандарте H.264 определены несколько типов слоев.- слой (от англ. слова intra). Содержит только макроблоки I типа, которые прогнозируются по ранее закодированным данным того же слоя. Область применения - все профили.- слой (от англ. cлова predicted). Может содержать макроблоки I типа, а так же макроблоки P типа. Макроблоки P типа полностью или частично ссылаются на ранее закодированные кадры. Область применения - все профили.- слой (от англ. сочетания bi - predictive). Может содержать макроблоки I типа, а так же макроблоки B типа. Макроблоки B типа являются полной аналогией макроблоков P типа, за тем отличием, что имеют ссылки на будущие кадры. Область применения - расширенный и основной профили.и SI - слои (от англ. switch P/I). Данные слои позволяют осуществлять переключение между кодируемыми потоками. Область применения - расширенный профиль.

Кадр кодируется в один или несколько слоев, в каждом из которых содержится целое число макроблоков - от одного до полного числа макроблоков на снимке (случай, когда кадр разбит только на один слой). Как видно из описания выше, базовый профиль, используемый в данной дипломной работе, поддерживает закодированные последовательности, в которые входят слои P и I типа. Кадры I типа, могут содержать слои I типа, а кадры P типа - слои типа P. Поскольку базовый профиль стандарта использует только P (ссылки на прошлые закодированные) и I (ссылки внутри кадра) слои кодирующее и декодирующее устройства при работе в режиме базового профиля имеют лишь ссылки на ранее закодированные кадры. Эти кадры хранятся в буфере декодированных списков DPB (от англ. Decoded Picture Buffer) как кодирующим устройством, так и декодирующим.

Какой же представляется последовательность закодированных кадров на выходе кодирующего устройства? Первый кадр видеопотока всегда является кадром I типа. Остальные кадры, в зависимости специфики выполняемой задачи, могут быть как кадрами P типа, так и I типа. Если два кадра I типа имеют номера n и k, при сквозной нумерации кадров видеопотока, при условии, что n < k, то группой кадров (англ. GOP - Group Of Picture) назовем все кадры c номерами fx, которые удовлетворяют следующему условию n ≤ fx < k. Подобный видеоряд изображен на рисунке 5.

Рис. 5. Группа кадров. Стрелками обозначены ссылки между кадрами.

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

.3 Методы восстановления видеоряда при потерях в канале передачи данных

Кодирующее устройство на выходе формирует битовый поток, состоящий из последовательности единиц NAL (минимум одна единица NAL, а максимум зависит от конкретной реализации кодирующего устройства). NAL объекты сегментируются на пакеты размером MTU (англ. maximum transmission unit - максимальный размер данный, который может быть передан без фрагментации в рамках протокола транспортного уровня модели OSI [7]) и далее отправляются по сетевому каналу на принимающее устройство. Если один или несколько пакетов будут потеряны в процессе передачи данных по сети, то декодирующие устройство неверно интерпретирует часть информации, и как следствие восстановит текущий кадр с заметными для человеческого глаза искажениями. Следующие кадры будут декодированы с большим количеством искажений, за счет наличия ссылок «здоровых» макроблоков на «зараженные». Распространение искажений, вызванные потерями частей битового потока, носят так называемый лавинный характер и способны со временем занять все кадровое пространство. Какие средства стандарта H.264, помимо использования нескольких слоев, призваны уменьшить распространение потерь?

Первый из них IDR кадр (от англ. Instantaneous Decoder Refresh) - кадр, который состоит из слоев I типа и содержит команду для декодирующего устройства, после получения которой, декодирующее устройство «очищает» ссылочный буфер, т.е. помечает все кадры этого буфера как «неиспользуемые для ссылок». При генерации IDR кадра кодирующее устройство проводит аналогичный процесс. Группа кадров для битового потока, содержащего IDR снимки, представлена на рисунке 6.

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

Следующие два способа, призванные исправить уже полученные искажения в восстановленном битовом потоке - Intra Refresh (от англ. Refresh - обновление) и Invalidate Reference (перевод: «объявить ссылку недействительной»). Во многих реализациях видеокодеков и библиотек видеосжатия эти методы являются взаимоисключающими.

Intra Refresh (обновление) - особая команда для кодирующего устройства, после получения которой количество следующих кадров равное периоду обновления, будут иметь уникальные для периода обновления макроблоки, прогнозируемые в рамках одного кадра (т.е. без ссылок на предыдущие кадры - прогнозируемые в моде Intra). Понятие период обновление определяется как количество кадров, за которое проходит обновление. Каждый кадр кодируется одинаковым количеством макроблоков. Если все макроблоки пронумеровать от 0 до n, то в период обновления каждый макроблок будет закодирован в моде Intra и при том только один раз. Данный процесс схематично изображен на рисунке 7.

Рис. 6. Группа кадров с IDR снимками. Стрелками обозначены ссылки между кадрами.

Рис. 7. Метод обновления (Intra Refresh). Стрелками обозначены ссылки между кадрами. А - область кадра, обновленная макроблоками мода Intra в рамках периода обновления.

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

Рис. 8. Метод удаления ссылок (Invalidate Reference) для ликвидации искажения восстановленного видеоряда. Стрелками обозначены ссылки между кадрами

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

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

2.4 Битовая скорость данных

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

Рис. 9. Вариации битовой скорости. Иллюстрирующий график

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

Переменную скорость данных, производимых кодирующим устройством, можно «сгладить» с помощью их буферизации до передачи с использованием специального буфера типа FIFO (от англ. First In/ First Out, «первым вошел - первым вышел»). Суть данного метода такова, что этот буфер освобождается с постоянной битовой скоростью, которая соответствует скорости транспортировки, в то время как заполняется с переменной битовой скоростью данных, генерируемых кодирующим устройством. Точно такой же буфер типа FIFO помещается на входе декодирующего устройства. Он заполняется с фиксированной скоростью транспортировки данных, а освобождается с переменной скоростью, так как декодирующее устройство извлекает некоторое количество бит для декодирования следующего кадра, а число извлеченных бит меняется от кадра к кадру.

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

3. Алгоритм адаптации потока видеоданных

Кодирующее устройство генерирует поток видеоданных с переменной битовой скоростью. Как уже было рассмотрено в главе 2.4, это ведет к увеличению мгновенного интервала между кадрами, что с точки зрения человеческого восприятия выглядит как торможение видео и затем немедленное его ускорение на стороне декодирующего устройства. Если битовая скорость превышает пропускную способность канала, то высока вероятность потери пакетов, составляющих объект NAL, что влечет к искажению видеоряда на стороне декодирующего устройства. В случае если мгновенная битовая скорость меньше пропускной способности канала, вероятность потерь остается не нулевой для некоторых протоколов транспортного уровня, в частности, например, UDP (от англ. User Datagram Protocol). Единичная ошибка восстановления макроблока любого кадра (из-за потери пакетов) через какое-то время может привести к искажению всего пространства кадра. Это происходит за счет того, что макроблоки новых кадров, ссылаются на неверный, искажения растут, этот процесс носит «лавинный» характер.

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

3.1 Клиент-серверная архитектура

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

Рис. 10. Клиент-серверная архитектура. Обозначения: М.З.В - модуль захвата видео, М.К.У - модуль кодирующего устройства, М.Д.У - модуль декодирующего устройства, М.А.В - модуль алгоритма адаптации видео, М.Т. - транспортный модуль, М.В. - модуль видеоплеера. RGB, H.264 - форматы передаваемых данных

В случае облачного сервиса клиент (рис. 10) - это программа, которая имеет транспортный модуль, модуль декодирующего устройства стандарта H.264, а так же модуль видеоплеера, который проигрывает восстановленные кадры в реальном времени.

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

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

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

Модуль захвата видео производит поток исходных несжатых данных - кадров формата семейства RGB. Это может быть приложение с реализованной функцией захвата видео из модуля рендеринга (от англ. Rendering - изображать), который призван создавать определенное количество кадров в секунду и генерировать ссылки на эти кадры для DWM модуля (от англ. Desktop Windows Manager - объект операционной системы Windows, призванный формировать изображение рабочего стола), если мы говорим о семействе операционных систем Windows.

Задача серверного транспортного модуля - принять битовый поток сжатого кадра, сегментировать его на пакеты и отправить клиенту по сети. Так же транспортный модуль принимает отчеты от клиента о пропускной способности канала, состоянии сети (наличие перестановок, дублирований пакетов и т.п.), состоянии видеопотока, а также внеочередные команды декодирующего устройства. Эту информацию он передает модулю адаптации видеопотока.

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

В рассмотренной выше схеме присутствует канал обратной связи, через который осуществляется прием и передача отчетов от клиента к серверу и внеочередных команд декодирующего устройства. Его отсутствие накладывает существенное ограничение на используемые механизмы стандарта H.264 для борьбы с искажениями восстановленных кадров - IDR кадр, механизм удаления ссылок требуют сообщений от декодирующего устройства кодирующему. Иначе, если канала обратной связи нет, мы вынуждены перегружать канал лишней битовой скоростью за счет постоянного использования Intra Refresh с уменьшенным периодом, ведь мы не можем судить о наличии и характере потерь пакетов.

3.2 Задачи и ограничения алгоритма

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

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

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

Наличие ненулевой вероятности потерь пакета UDP. Тем не менее, если пиковая битовая скорость значительно меньше пропускной способности канала, вероятность потерять UDP пакет отнюдь ненулевая. Отчасти это вызвано ошибками в коммутационном оборудовании, программным обеспечением на стороне клиента и т.п. В этом случае мы рискуем всем кадровым пространством видеоряда и при появлении потерь должны своевременно на это реагировать с помощью механизмов H.264 а так же эффективных упреждающих сторонних мер (подробнее об этом в гл.5 посвященной избыточности данных).

Отсутствие буферизации данных, как на стороне получателя, так и на стороне отправителя. О проблемах, вызванных буферизацией данных, шла речь в гл. 2.4. В облачных технологиях ощутимые для человеческого восприятия задержки составляют до 30 - 50 мс, а в видеоконференциях - до 100 мс. Так же следует пояснить, что некоторая буферизация присутствует, но по сравнению с известными технологиями такими, как IPTV, где значение буферизации составляет от 1 - 2 мин [5], в облачных технологиях буферизация не может превосходить значения одного кадрового интервала. Данное ограничение существенно препятствует использованию избыточности данных (подробнее об избыточности данных - глава 5).

.3 Протокол взаимодействия

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

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

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

Уникальный идентификатор группы пакетов (или NAL объекта, сокр. УИГП). Данный параметр определяет порядковый номер NAL объекта, который необходим для определения принадлежности NAL объекта тому или иному кадру.

Уникальный идентификатор пакета данных (сокр. УИПД). Данный параметр определяет порядковые номера пакетов данных, передаваемых по сети. Этот параметр необходим для выявления кадра с искаженными макроблоками на стороне клиента. Детектируя потерю пакета (факт того, что пакет за отведенное на ожидание всей группы пакетов время не был доставлен по сети транспортному модулю клиента), транспортный модуль клиента формирует отчет, в котором указываются конкретные номера потерянных пакетов. Вместе с тем, как сжатый битовый поток поступает на вход декодирующего устройства, на сервер отправляется отчет, содержащий данные о потерях. На сервере по уникальному идентификатору потерянных пакетов удается восстановить уникальный идентификатор группы пакетов, а так же уникальный идентификатор кадра, что позволяет использовать механизм удаления ссылок стандарта H.264, а значит, последующие кадры не будут ссылаться на искаженный, что предупредит лавинный рост искажений в видеоряде. Информация, определяющая принадлежность пакета NAL объекту и кадру хранится на сервере определенное количество времени в виде связей УИК - УИГП - УИПД.

Временные метки кадра (англ. timestamp). Данный параметр служит для контроля сетевых задержек. Во время отправки битового потока текущего кадра на клиент транспортный модуль сервера маркирует данные определенной временной меткой - время T1. Этот же процесс происходит при получении отчета по этому кадру от клиента - время T2. Если рассматривать разности T2 - T1 для нескольких кадров, можно судить об относительном росте задержек в сети, проводя аналогию с битовым весом кадра (т.е. количеством бит, которое текущий кадр занимает), отчет по которому был получен.

Данные о частоте кадров на кодирующем и декодирующем устройстве (англ. FPS - frame per second - количество кадров в секунду). Эта информация формируется схожим способом с вышеописанным. Единственное, что следует отметить, эти данные запаздывают на 1 кадр, так как декодирующее устройство в момент получения нового битого потока для кадра номером N имеет данные о частоте кадров по N-1 итерации. Соответственно в отчете под номером N отправляются данные о частоте кадров на момент декодирования N-1 кадра. Эта информация так же анализируется на сервере. По сведениям о частоте кадров на сервере и клиенте можно судить о производительности и загрузки вычислительных ресурсов этих машин. Так, если серверная частота кадров постоянна, а частота кадров клиента носит переменный характер, при отсутствии флуктуаций по сетевым задержкам, то алгоритм может судить о нехватке вычислительных мощностей на клиентской машине и адаптировать видеопоток.

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

.4 Общий вид алгоритма

Ранее, в главе 3.3, были рассмотрены данные, которыми оперирует алгоритм адаптации видеопотока. Представленный в этой дипломной работе алгоритм обрабатывает указанную информацию, за исключением данных о частоте кадров, а так же временных меток. Связано это с тем, что основной информацией в принятии решения об изменении параметров видеопотока является информация о потерянных пакетах в процессе передачи данных по сети. Изменение параметров видеопотока лишь малозначительно способно повлиять на частоту воспроизводимых кадров на стороне клиента и на задержки во время передачи данных по сети. Тем не менее, для адаптации видеопотока на основе информации о частоте кадров, можно использовать описанные ниже манипуляции с битовой скоростью потока сжатых кадров, а так же переключением соотношения качество - производительность, которое определенно выбранной реализацией кодирующего устройства (данный параметр носит название «пресет», от англ. Preset, что означает «предустановка»).

Ранее мы определили понятие битовой скорости (гл. 2.4), рассмотрели место алгоритма адаптации видеопотока в архитектуре сервера и так же способ передачи данных и их тип (гл. 4.1). Так же, был рассмотрен стандарт H.264 (гл. 3), который отчасти определил способ передачи данных и специфику работы кодирующих и декодирующего устройств. Отдельно стоит упомянуть о методах восстановления и предупреждения искажений восстановленного видеоряда на стороне клиента, рассмотренных в гл. 2.2 и 2.3. Перейдем к описанию общего вида алгоритма адаптации видеопотока во время передачи данных по сети изображенного на рис. 11.

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

Рис. 11. Общий вид алгоритма адаптации видеопотока. Принятые сокращения: У.Б.С - уровень битовой скорости, В.К.Д.У - внеочередные команды декодирующего устройства

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

Если данный метод считает потери одиночными (т.е. допустимыми), вызванными не постоянным несоответствием пропускной способности канала битовой скорости, то происходит коррекция видеоряда на стороне кодирующего устройства. При этом модуль алгоритма адаптации видеопотока использует механизм удаления ссылок стандарта H.264, сообщая кодирующему устройству УИК (см. гл. 2.3) кадров с искаженными макроблоками и подавая соответствующую команду. Механизм удаления ссылок при наличии обратного канала связи между кодирующим и декодирующим устройством более эффективен, чем метод обновления видеоряда, т.к. при использовании последнего существует вероятность возврата искажения (данный процесс рассмотрен в главе 2.3).

Рис. 12. Пороговое значение битовой скорости. Иллюстрирующий график

Кодирующее устройство не способно генерировать каждый сжатый кадр с одинаковой битовой скоростью. Размер сжатого кадра изменяется в некоторых пределах, в зависимости от настроек кодирующего устройства. Так, параметр кодирующего устройства, отвечающий за верхний предел битовой скорости (англ. Peak bitrate) ограничивает возможное значение битовой скорости сверху (рис. 12). Тем не менее, если кодирующее устройство не способно сгенерировать битовый поток указанного размера, возможны превышения данного порога. Данный факт зависит от реализации кодирующего устройства и проверяется для каждого из них вручную.

При изменении У.Б.С. начинается так называемый период проверки уровня на устойчивость. Суть данного этапа сводится к проверке на соответствие текущему У.Б.С. пропускной способности канала. Если алгоритм адаптации увеличил значение уровня, то о текущей пропускной способности канала следует судить по наличию недопустимых потерь. При большом количестве потерянных пакетов следует возврат на предыдущий уровень, а данный маркируется как несоответствующий текущей пропускной способности канала. Если алгоритм адаптации уменьшил значение уровня ввиду большого количества потерь, то так же неизвестно, соответствует ли данный уровень текущей пропускной способности канала. Одной из целью использования проверки уровня на устойчивость является предупреждение ложного повышение значения битовой скорости. Это связано с тем, что при изменении параметра верхний предел битовой скорости кодирующему устройству требуется некоторое время для изменения размера сжатых данных. Рекомендуемое значение данного параметра - 15 - 20 с.

3.5 Уровни скорости передачи данных источника

Параметрами алгоритма адаптации являются максимальные и минимальные значения уровней битовой скорости, а так же шаг изменения уровня битовой скорости. Данные уровни определяют диапазон возможных принимаемых значений параметра «пороговая величина битовой скорости» кодирующего устройства. Они должны зависеть от характера видеопотока и назначаются управляющим модулем. Так, например, для видеопотока в разрешении 1280х720 и частоте кадров в 30 кадр/с, оптимальным окажется диапазон уровней битовой скорости в 3000 - 11000 Кбит (3 - 11 Мбит).

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

Рис. 13. Карта уровней битовой скорости для диапазона скоростей 3000 - 11000 Кбит/с, шаг - 1000 Кбит/с. Представленные значения в Кбит/с

Алгоритм адаптации различает значения уровня битовой скорости и актуальной битовой скорости. Как было рассмотрено в гл. 2.4, кодирующее устройство при заданном уровне битовой скорости V способно сгенерировать кадр с размером 0 - V Кбит. Актуальной битовой скоростью назовем сумму размеров всех кадров, сгенерированных кодирующим устройством за время T, отнесенную к количеству данных кадров. Очевидно, что актуальная битовая скорость может сильно отличаться от заданного порогового значения. Например, статичная картинка (черный экран, мало движения) в сжатом виде будет занимать около 5 - 10 % от возможного максимального размера кадра. Если актуальная битовая скорость далека от максимальной, это означает, что канал передачи данных не испытывает нагрузки, и судить об устойчивости того или иного уровня не стоит. Рассмотрим иллюстрирующий пример. Пусть у алгоритма имеется карта уровней битовой скорости, представленная на рис. 13, а текущее значение битовой скорости - 7000 Кбит/с. При этом видеоряд имеет статичную картинку, которая в сжатом варианте составляет около 10% от возможного максимального значения. Пусть канал передачи данных способен пропустить без потерь видеопоток, сжатый с битовой скоростью в 6 Кбит/с. Тогда в данном случае канал передачи данных загружен меньше, чем наполовину. Спустя некоторое время данный уровень считается устойчивым, а пороговое значение, согласно алгоритму, повышается до 8000 Кбит/с. Если при этом произойдет изменений характера видеоряда, появится движение, множество мелких объектов, то мгновенная битовая скорость поднимется до 7000 - 8000 Кбит/с, т.е. предельно близко к пороговому значению. Т.к. канал передачи данных не способен пропустить столько информации в единицу времени, возникнут потери пакетов, и как следствие ухудшение качества видеоряда на стороне клиента. Данный процесс носит название «ложного повышения уровня битовой скорости». Хотелось бы отметить, что возможное максимальное значение размера сжатого кадра и битовая скорость - разные характеристики видеопотока, т.к. битовая скорость - сумма размеров сжатых кадров, отнесенная к единице времени, а возможное максимальное значение кадра диктуется значением битовой скорости и зависит от реализации кодирующего устройства.

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

Va = Vp * Pa,

где Va - минимальное значение актуальной битовой скорости, Vp - текущий уровень битовой скорости, Pa - граница актуальной битовой скорости принимает значения в диапазоне (0,1]. Данный способ эффективно устраняет ложные повышения уровня битовой скорости. Рекомендуемое значение Pa = 0.75 - 0.85.

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

Vn = Vo * (1 - Lr ) - H

где Vo - значение текущего уровня битовой скорости, Vn - значение нового уровня битовой скорости, Lr - степень потерянных пакетов принимает значения в диапазоне (0, 1], H - шаг изменения уровня битовой скорости. Если значение Vn оказалось меньше, чем минимальное значение уровня битовой скорости (см. рис. 13), то Vn принимает значение минимального уровня. Если Vn = Vo, то в случае Lr != 0, происходит отключение клиента, а пропускная способность сетевого канала считается недопустимой для передачи видеопотока.

.6 Робастная оценка потерь. Допустимые потери

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

Алгоритм адаптации в качестве входных данных получает отчеты о потерянных пакетах для каждого кадра. На основе этой информации, модуль оценки потерь делает заключение о характере потерь. Так, допустимыми потерями называют такие потери, искажение от которых удается ликвидировать используемыми алгоритмом способами (в частности механизмами стандарта H.264). Недопустимыми потерями назовем такие потери, искажение от которых существенно влияет на качество воспринимаемого видеоряда. Информацией, которой располагает модуль оценки потерь, является номера кадров, номера пакетов в текущем видеопотоке, а так же временная метка, означающая время появления сжатого кадра на выходе кодирующего устройства. С точки зрения статистической обработки данных значения 1 и 0 (1 - пакет потерян, 0 - доставлен) для каждого отправленного пакета составляют статистическую выборку. Результатом статической обработки данных является решение о допустимости потерь на каждой итерации алгоритма (как только приходит новый отчет).

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

Помимо подхода исключения значений с сильным отклонением из текущей выборки, при обработке статистических данных используют робастные методы. Под робастностью понимают «нечувствительность к малым отклонениям от предположений» [8]. Существуют методы, которые игнорируют сильные отклонения от среднего при обработке данных, например робастные эстиматоры (от англ. Robust estimators) [9], а так же медиана [8]. Метод медианы напоминает расчет среднего значения для упорядоченной по возрастанию (убыванию) статистической выборки с игнорированием определенного количества значений слева и справа. Полной медианой при количестве значений в выборке N+1 будем называть медиану, в которой количество игнорируемых значений слева и справа одинаково и равно N/2. Смещенной полной медианой при количестве значений в выборке NL+NR+1 будем называть полную медиану, в которой количество игнорируемых значений слева равно NL, а справа - NR.

Рис. 14. Формат данных модуля оценки потерь

видеоряд битовый серверный

Ответом на два выше поставленных вопроса является модуль оценки потерь алгоритма адаптации, который оперирует данными указанного на рис. 14 формата. Номер кадра определяет порядковый номер сжатого кадра в текущем видеопотоке. Поле «количество потерянных пакетов» содержит информацию о том, сколько пакетов, представляющих информацию данного кадра, было потеряно в процессе передачи данных по сетевому каналу. Эти данные помещаются во временный буфер, который упорядочен по возрастанию по полю «количество потерянных пакетов». Длина этого буфера L определена двумя параметрами: F - целевая частота кадров кодирующего устройства, T - время оценки потерь, как L = F * T. Значение T показывает время за которое модуль оценки потерь собирает информацию. В случае, когда в буфере не хватает места для новой информации (т.е. когда кодирующее устройство работает дольше T), модуль оценки потерь удаляет информацию по самому младшему кадру (согласно его номеру) и помещает на освободившееся место информацию по новому кадру, при этом данные остаются упорядоченными по полю «количество потерянных пакетов».

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

Pr = 1 - Nr / L,

где Pr - правая граница смещенной медианы, Nr - порядковый номер медианы в текущей выборки значений, L - длина этой выборки. Если данные на месте Nr содержат ненулевое значения поля «количество потерянных пакетов», происходит расчет текущей степени потерь Y за последние L кадров, как

Y = K / M,

где K - количество потерянных пакетов за последние L кадров, M - количество отправленных пакетов за последние L кадров. При этом, если значение Y > Yq, где Yq - допустимая степень потерь пакетов, то на данной итерации характер потерь определяется как недопустимый. Это неравенство математически определяет допустимость потерь. Значения Y и Yq принадлежат диапазону [0,1]. Схема буфера изображена на рисунке 15.

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

Рис. 15. Буфер оценки потерь. Принятые сокращения: Ax - поле номера кадра, Bx - поле количества потерь пакетов для данного кадра, Pr - правая граница смещенной медианы, Nr - порядковый номер медианы, L - длина статистической выборки

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

-целевая частота кадров F = 30 кадр/с;

-время оценки потерь T = 5 с;

-правая граница смещенной медианы Pr1 = 0.08;

-допустимая степень потерь пакетов Yq1 = 0.11;

-правая граница смещенной медианы Pr2 = 0.16;

-допустимая степень потерь пакетов Yq2 = 0.015.

4. Помехоустойчивое кодирование

Механизмы коррекции ошибок стандарта H.264 эффективно противодействуют искажениям кадра, вызванными потерями пакетов. Данный процесс происходит с запаздыванием и, если один потерянный пакет и соответствующие искажения в макроблоках кадра человеческий глаз может не уловить, то несколько искаженных макроблоков (пусть и исправленных со временем) в нескольких подряд идущих кадрах существенно влияют на качество восстановленного видеоряда. Тем не менее, существуют способы упреждающей коррекции ошибок, которые вызваны потерями пакетов процесса передачи данных по сети. «Упреждающий» означает, что на уровне транспортного модуля клиента происходит частичное восстановление данных на основе избыточной информации, передаваемой вместе с битовым потоком текущего кадра. Дополнительная информация «съедает» часть пропускной способности канала, а значит, видеоряд становится менее качественным, так как кодирующее устройство работает с меньшим уровнем битовой скорости. Но вместе с этим на стороне клиента происходит значительное уменьшение случаев появления искажений, что положительно сказывается на качестве воспринимаемого видеоряда.

В основе помехоустойчивого кодирования лежит идея добавления дополнительной проверочной информации к уже существующей. На передающей стороне используется специальное кодирующее устройство для внесения избыточности (сокр. «кодер», не путать с кодирующим устройством стандарта H.264, которое в данной дипломной работе именуется «кодирующее устройство»), а на принимающей специальное декодирующее устройство для восстановления данных по избыточным - декодер. Определим избыточность данных как количество дополнительных единиц данных k, для исходных единиц данных I, а степень избыточности p кода определена формулой p = k / (k+i). В теории информации единицей данных принято считать бит. В нашем случае единицей данных является пакет транспортного протокола. Кодер и декодер соответственно являются частями транспортных модулей сервера и клиента.

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

.1 Существующие решения

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

Преобразование Лаби. Этот метод был создан М. Лаби (Michael Luby) в 1998 г [11]. Своё название он получил от англ. «Laby transform» - LT code. Алгоритм кодирования основан на алгоритме фонтанного кода.

Фонтанный код является несистематическим. В каждый из кодовых символов с вероятностью 0.5 входит каждый из K исходных символов. Сложением бит по модулю 2 (операцией XOR) всех входящих исходных символов вычисляются значения k бит кодового символа. В результате кодер генерирует случайный код, в среднем используя K/2 операций XOR для вычисления одного кодового символа. Эта величина, называемая стоимостью кодирования, оказывается сравнимой с K, и поэтому её следует считать большой.

Алгоритм кодирования можно сформулировать следующим образом:

-выбирается степень di кодового символа как значение случайной величины d с равномерным распределением ρ(d)=1/K, d=1,2,…K;

-из K номеров с вероятностью 1/K выбираются di номеров исходных пакетов, а операцией XOR над битами этих исходных символов формируется кодовый символ xi;

-в среднем степень каждого проверочного узла графа оказывается равной K/2.

Для декодирования кода требуется использование алгоритма максимального правдоподобия (МП) [12]. Анализ показывает, что процесс завершается по K' кодовым символам с вероятностью 1 - δ, где δ < 2-O, O = K '- K [13]. К примеру, для K=104 имеем δ < 10-6 при K' = K+20, что примерно соответствует К.

Преобразование Лаби аналогично использованию фонтанного кода, однако имеет иное распределение p(d). В основе нахождения ρ(d) и алгоритма декодирования лежит следующая вероятностная задача. Есть сообщение (книга) из K исходных символов (страниц). Из этого множества с вероятностью 1/K производится K' случайных выборок символов (страниц). В результате формируется множество из K' кодовых символов (случайно выдернутых страниц). Чему должно быть равно K' для того, чтобы с вероятностью 1 - δ каждый из всех K исходных символов (страниц) оказался хоть один раз среди K' кодовых символов (кодовых страниц)? Ответ K'~=K ln(K/δ) [13] при достаточно большом K. Имея такое число кодовых символов (случайно выдернутых из книги страниц), можно реконструировать исходное сообщение (книгу) с вероятностью 1-δ. Алгоритм реконструкции предельно быстрый и использует лишь информацию о нумерации символов (страниц). Основанный на этом алгоритм Лаби на практике работает тем ближе к теоретическим результатам, чем больше значение K. В работах Лаби данный параметр K = 104 [11], что делает преобразование Лаби полностью непригодным для использования в алгоритме адаптации видеопотока.

Код Раптор представляет собой кодовую конструкцию с внутренним LT кодом. В качестве внешнего кода можно использоваться любой блоковый код (c фиксированной скоростью). Разработка и исследование кода принадлежит A. Shokrollahi [14]. Анализ конструкции показывает, что исходное сообщение может быть реконструировано с вероятностью 1-δ по K'=K(1+ε) символам, где ε - небольшое положительное число. Стоимость декодирования оказывается порядка ln(1/ε) операций XOR. Для декодирования сообщения требуется порядка K*ln(1/ε) операций XOR. На сегодняшний день код является, достаточно эффективной аппроксимацией идеального фонтанного кода. Тем не менее, требуется провести ряд исследований на эффективность применения Раптор кода в алгоритме адаптации видеопотока.

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

.2 Метод наложения избыточности

Альтернативой коду Раптора может служить достаточно простой метод наложения избыточности. Перед его созданием был проведен анализ 2100 сессий, содержащих информацию о текущем уровне битовой скорости, размерах каждого кадра, а так же порядковых номеров потерянных пакетов. Адаптация видеопотока происходила согласно описанному в главе 4 алгоритму. В исследовании приняли участие около 100 клиентов, представляющие различные типы сетей различных сетевых провайдеров стран СНГ. Цель этого исследования, проводимого на базе российского облачного сервиса, ответить на вопрос - какая часть пакетов из кадра теряется, а так же - как располагаются потерянные кадры, в порядке следования, или прерывисто?

Для этого введем понятие группы потерянных пакетов, которая определяется как некоторое количество упорядоченных по возрастанию в порядке следования в видеопотоке пакетов, причем порядковые номера любых соседних пакетов отличаются на 1. Если всего таких групп N, то величиной Z - вероятность потери только одной группы пакетов только в одном кадре - назовем Z = U / N, где U - количество групп потерянных пакетов, которые принадлежат одному кадру, содержащему лишь одну группу потерянных пакетов. Следует отметить, что кадр может содержать и две и три группы потерянных пакетов. Так, если кадр определяется номерами пакетов A и B, то группа потерянных пакетов, которая принадлежит этому кадру, имеет номера в диапазоне (A, B), при том любые два соседних номера такой группы отличаются на 1.

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

Рис. 16. Соответствие вероятности и удельного веса группы потерянных пакетов

Для ответа на второй вопрос, был построен график, представленный на рис. 16. Удельный вес группы потерянных пакетов обозначает часть потерянных пакетов от всех пакетов данного кадра и определяется как

C = NL / NF * K,

где NL - количество пакетов в группе потерянных пакетов, а NF - количество пакетов в кадре, K = 10 - расчетный коэффициент. При построении этого графика учитывались только те кадры, которые содержали одну группу потерянных пакетов. Значение вероятности показывает то, насколько часто среди всех рассмотренных кадров встретилась группа потерянных пакетов с конкретным удельным весом. Анализируя площадь под графиком, можно сделать вывод (вся площадь под график составляет 1), что до 60% случаев потерянных пакетов генерируются группами потерянных пакетов с удельным весом до 4. При этом следует отметить, что так называемый «хвост» графика справа вызван спецификой работы алгоритма адаптации видеопотока и содержит информацию о большинстве случаях адаптации битовой скорости кодирующего устройства стандарта H.264 под пропускную способность канала передачи данных.

Рис. 17. Процесс внедрения избыточности. Принятые сокращения: P - степень избыточности, N - количество пакетов в кадре, N| - количество пакетов в выходной группе кадров, G - количество групп избыточности, gx - группа избыточности

На основе информации, полученной в процессе исследования, был разработан следующий метод наложения избыточности, который, наряду с кодами Раптора, носит рекомендательный характер. Пусть текущий кадр состоит из N пакетов, а требуемая избыточность данных P называется степенью избыточности. Определим число групп избыточности как G = N * p, при этом G > 0 и G - целочисленное (округление в большую сторону), что означает если N мало настолько, что G = 0, то G = 1. Определим группы избыточности gx, где х изменяется от 1 до G и представляет значения номера группы. Отнесем каждый пакет с номером i (изменяется от 1 до N) к группе gx так, что каждая группа содержит одинаковое количество пакетов. Данное требование не выполняется тогда, когда N не кратно G. В этом случае последняя группа содержит меньшее количество пакетов. Создадим избыточные данные для каждой группы с помощью операции XOR для всех пакетов группы. Результат этой операции так же помещается в свою группу. Все полученные пакеты перед отправкой перемешиваются таким образом, что пакеты из одной группы находятся на возможно большом расстоянии друг от друга. Под расстоянием между пакетами одной группы будем понимать количество пакетов между ними. Данный процесс схематически изображен на рис. 17. В качестве дополнительной меры рекомендуется добавить добавочную группу данных, в которую входят все пакеты. Результат оператора XOR - добавочный избыточный пакет поместить в конце выходной группы пакетов.

.3 Внедрение помехоустойчивого кодирования в алгоритм адаптации видеопотока

Рассмотренный в главе 4 алгоритм адаптации оперирует понятием уровня битовой скорости. Причем наилучшее качество видеопотока в заданных условиях достигается тогда, когда алгоритм обеспечивает максимально возможную битовую скорость сжатых данных меньшую, чем пропускная способность канала. Любые добавочные данные, в том числе и избыточные, «съедают» часть пропускной способности, взамен обеспечивая сжатый поток лучшей устойчивостью в случаях понижения пропускной способности канала и потерь пакетов. Рассмотренный метод наложения избыточности, при заданном параметре P (степень избыточности), по факту генерирует больше избыточных данных, что связано со спецификой метода. Допустим уровень битовой скорости D = 4000 Кбит/с, а P = 0.2. Исследования не реальном видеоряде показывают, что на выходе кодера образуется видеопоток с битовой скоростью DF = 4934 Кбит/с, и по факту P| = 0.2335. Это является существенным недостатком рассмотренного метода внедрения избыточности, который, так или иначе, влияет на процесс внедрения метода в алгоритм адаптации видеопотока.

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

Рис. 18. Иллюстрирующий пример работы алгоритма. Цифрами и буквами обозначены: T - период ожидания проверки У.Б.С. на устойчивость; 1 - уменьшение П.С.К.; 2 - детектирование потерь и уменьшение У.Б.С., начало периода ожидания; 3 - увеличение П.С.К.; 4 - окончание периода проверки У.Б.С. на устойчивость, увеличение У.Б.С; У.Б.С. - уровень битовой скорости; П.С.К. - пропускная способность канала

Пусть на начальном этапе уровень битовой скорости адаптирован под пропускную способность канала, отчего видеоряд представлен на стороне клиента в лучшем качестве. Далее происходит уменьшение пропускной способности канала (1), ввиду чего образуются недопустимые потери пакетов, детектируемые модулем оценки потерь. С момента 1 до момента 2 (адаптация уровня битовой скорости под изменившуюся пропускную способность канала) конечный видеоряд содержит искажения, что значительно ухудшает воспринимаемое качество изображения. После адаптации происходит период проверки уровня на устойчивость, за счет которого видеоряд восстанавливается после искажений. Далее алгоритм проверяет пропускную способность канала, увеличивая уровень битовой скорости и реагируя на сообщения от модуля оценки потерь - 4. Если возникшие потери являются допустимыми (т.е. пропускная способность вернула прежнее значение - 3), то новый уровень битовой скорости проверяется на устойчивость, что далее, в примере, происходит с неудовлетворительным исходом. В правой части графика схематически изображен процесс адаптации уровня битовой скорости для генерации лучшего качества видеопотока. Каждый раз, когда линия пропускной способности канала меньше линии уровня битовой скорости возникают искажения, и ухудшается качество видеоряда, что является существенным минусом данного подхода.

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

Рис. 19. Иллюстрирующий пример работы алгоритма с избыточностью данных.

Цифрами и буквами обозначены: S - пропускная способность канала, пакет/кадр; D - У.Б.С., пакет/кадр; DF - У.Б.С. с избыточностью, пакет/кадр; R - уровень избыточности данных, пакет/кадр; 1 - при окончании времени ожидания DF ↑ при D = const (R↑); 2 - во время ожидания проверки У.Б.С. на устойчивость DF , D = const (R = const); 3 - У.Б.С. признан устойчивым DF = const, D↑ (R↓); У.Б.С. - уровень битовой скорости

Уровень избыточности R определим как R = DF - D, где DF - уровень битовой скорости видеопотока с избыточностью, а D - уровень битовой скорости видеопотока, при этом всегда DF ≥ D. Пусть S - пропускная способность канала, а в начальных условиях S > DF. Чем R больше, тем меньше вероятность того, что при потерях пакетов возникнут искажения видеоряда на стороне клиента. Так, в случае с изменением S до такой степени, что S < DF (кадр 3, рис 19), модуль оценки потерь детектирует потери пакетов, и далее происходит уменьшение уровня битовой скорости D (при R = const, DF↓). Если R достаточно велик, то искажения видеоряда на стороне клиента будут минимизированы, либо отсутствовать. Следуя принципу «подушки безопасности», алгоритм адаптации повышает уровень избыточности R в случаях, когда неизвестна пропускная способность канала - перед возможным повышением D, а так же в период ожидания проверки уровня на устойчивость. В случае 1, после понижения D (R = const) начинается проверка уровня битовой скорости на устойчивость, перед окончанием которой, за время T1 ≤ T, где T - время ожидания, следует повышение R (D = const). Увеличивая размер «подушки безопасности» в данный момент, мы понижаем вероятность возникновения искажений видеоряда на стороне клиента в дальнейшем, при повышении D при R = const. В случае 2 иллюстрируется пример повышения R в период проверки уровня на устойчивость, по окончанию которого, в момент 3, при DF = const, D↑, R↓ - алгоритм уменьшает уровень избыточности взамен роста качества видеопотока, т.к. текущий уровень признан устойчивым. Таким образом, работа алгоритма адаптации с использованием избыточности данных базируется на нескольких правилах:

¾всегда присутствует уровень избыточности R = DF - D, уменьшающий вероятность искажения видеоряда на стороне клиента при наличии потерь пакетов;

¾по окончанию периода ожидания - D↑ при DF = const, R↓.

Заключение

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

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

Список литературы

1. Монахов Д.Н., Монахов Н.В., Прончев Г.Б., Кузьменков Д.А. Облачные Технологии. Теория и практика; МАКС Пресс Москва, МГУ, 2013, - 128с.

. C. E. SHANNON. A Mathematical Theory of Communication, "The Bell System Technical Journal", Vol. 27, pp. 379-423, 623-656, July, October, 1948.

3. Росс Эшби У. Глава 6. Черный ящик, Введение в кибернетику (An Introduction to Cybernetics). Издательство иностранной литературы, 1959. С. 127-169. - 432 с.

. Atul Apte, Quality of service management system and method of forward error correction US 20140286440 A1

5. К.В. Шинкаренко, А.М. Кориков, «Помехоустойчивое кодирование данных мультимедиа данных в компьютерных сетях», УДК 621.313.684

6. ISO/IEC 14496-10:2014 // ISO/IEC MPEG-4 Part 10

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

. Конахович Г.Ф., Чуприн В.М. Сети передачи пакетных данных; МК-Пресс, 2006, - 272с.

9. Хьюбер П. Робастность в статистике. - М.: Мир, 1984. - 303 с.

. Хиценко, В.Е. Робастные методы оценивания : учеб. пособие / В.Е. Хиценко .- Новосибирск : Изд-во НГТУ, 2008 .- ISBN 978-5-7782-1093-6

. Орлов А. И. Экспертные оценки. Учебное пособие. М.: ИВСТЭ, 2002

12. Luby M. LT Codes // Proc. of the 43rd Annual IEEE Symp. on Foundations of Computer Science (FOCS). - 2002. - P. 271-282.

13. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования - методы, алгоритмы, применение; Москва: Техносфера, 2005, - 320с.

14. David J.C. MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press. 2003

15. Shokrollahi. Raptor Codes. 2003.