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

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

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

3.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). Тем не менее, если кодирующее устройство не способно сгенерировать битовый поток указанного размера, возможны превышения данного порога. Данный факт зависит от реализации кодирующего устройства и проверяется для каждого из них вручную.

Алгоритм адаптации видеопотока оперирует понятием уровня битовой скорости (У.Б.С. рис. 11). Значение текущего У.Б.С. соответствует значению параметра предела битовой скорости кодирующего устройства. Суть адаптации заключается в изменении текущего У.Б.С. к У.Б.С. меньшему, чем пропускная способность канала. Повышение битовой скорости предельно близко к пропускной способности канала использовано с целью достижения лучшего качества при текущих параметрах сети. Все возможные значения У.Б.С. ранжируются в соответствии с максимальным и минимальным параметрами возможной битовой скорости видеопотока в рамках сессии, а так же шагом ранжирования. Эти параметры определены как настройки алгоритма адаптации видеопотока. Подробнее данный процесс рассмотрен в главе 3.5.

При изменении У.Б.С. начинается так называемый период проверки уровня на устойчивость. Суть данного этапа сводится к проверке на соответствие текущему У.Б.С. пропускной способности канала. Если алгоритм адаптации увеличил значение уровня, то о текущей пропускной способности канала следует судить по наличию недопустимых потерь. При большом количестве потерянных пакетов следует возврат на предыдущий уровень, а данный маркируется как несоответствующий текущей пропускной способности канала. Если алгоритм адаптации уменьшил значение уровня ввиду большого количества потерь, то так же неизвестно, соответствует ли данный уровень текущей пропускной способности канала. Одной из целью использования проверки уровня на устойчивость является предупреждение ложного повышение значения битовой скорости. Это связано с тем, что при изменении параметра верхний предел битовой скорости кодирующему устройству требуется некоторое время для изменения размера сжатых данных. Рекомендуемое значение данного параметра - 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 Кбит/с, т.е. предельно близко к пороговому значению. Т.к. канал передачи данных не способен пропустить столько информации в единицу времени, возникнут потери пакетов, и как следствие ухудшение качества видеоряда на стороне клиента. Данный процесс носит название «ложного повышения уровня битовой скорости». Хотелось бы отметить, что возможное максимальное значение размера сжатого кадра и битовая скорость - разные характеристики видеопотока, т.к. битовая скорость - сумма размеров сжатых кадров, отнесенная к единице времени, а возможное максимальное значение кадра диктуется значением битовой скорости и зависит от реализации кодирующего устройства.

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

V_a = V_p * P_a,

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

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

V_n = V_o * (1 - L_r ) - H

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

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

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

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

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

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

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

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

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

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

P_r = 1 - N_r / L,

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

Y = K / M,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- в среднем степень каждого проверочного узла графа оказывается равной 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 = 10⁴ [11], что делает преобразование Лаби полностью непригодным для использования в алгоритме адаптации видеопотока.

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

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

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

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

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

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

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

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

C = N_L / N_F * K,

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



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

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

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

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

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

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

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

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

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

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

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

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

ѕ в период ожидания, а так же перед D^ - R^ при D = const, D_F^;

ѕ по окончанию периода ожидания - D^ при D_F = const, Rv.

Заключение

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

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

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

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

2. 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 с.

4. 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с.

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

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

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

11. Орлов А. И. Экспертные оценки. Учебное пособие. М.: ИВСТЭ, 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.

Размещено на Allbest.ru