Национальная академия наук Украины
Національна академія наук України
Інститут кібернетики імені В.М. Глушкова
ОКСЮК Олег Олександрович
УДК 681.3.06
ОПТИМІЗАЦІЯ РОЗКЛАДУ ПЕРЕДАЧІ ПАКЕТІВ ПОТОКОВОГО ВІДЕО ПО МЕРЕЖІ З ВТРАТАМИ ДАНИХ
05.13.06 – автоматизовані системи управління та прогресивні
інформаційні технології
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
Київ – 2007
Дисертацією є рукопис.
Робота виконана в Інституті кібернетики імені В.М. Глушкова НАН України.
Науковий керівник: доктор технічних наук, професор,
член-кореспондент НАН України
Боюн Віталій Петрович,
Інститут кібернетики ім. В.М. Глушкова НАН України,
завідувач відділу управляючих машин і систем.
Офіційні опоненти: доктор технічних наук, професор
Лучук Андрій Михайлович,
Державний університет
інформаційно-комунікаційних технологій,
кафедра інформаційних технологій,
кандидат технічних наук
Алішов Надір Ісмаіл-огли,
Інститут кібернетики ім. В.М. Глушкова НАН України,
провідний науковий співробітник.
Захист відбудеться «3» жовтня 2007р. о 14 годині на засіданні спеціалізованої вченої ради Д.26.194.03 при Інституті кібернетики ім. В.М. Глушкова НАН України за адресою:
03680, МСП, Київ-187, проспект Академіка Глушкова, 40.
З дисертацією можна ознайомитися в науково-технічному архіві інституту.
Автореферат розісланий «21» серпня 2007р.
Учений секретар
спеціалізованої вченої ради _________________ РОМАНОВ В.О.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Відео являє собою важливий засіб зберігання і передачі даних вже більше ста років. З появою комп'ютерів відео стали зберігати й передавати не тільки в аналоговому, але й у цифровому форматі. Нині йде поступове витіснення аналогового відео цифровим. Основні дві проблеми в області цифрового відео – це способи стиснення й способи передачі відеоінформації. Способи стиснення цифрового відео були предметом багатьох досліджень наприкінці 80-х і на початку 90-х років. У цей час з'явилася можливість зберігати відео на CD і DVD дисках. Наприкінці 90-х років різке збільшення популярності Інтернету і збільшення пропускної здатності мереж дали поштовх розвитку області передачі потокового відео, яке є способом безперервної передачі цифрового відео з можливістю одночасного відтворення на приймачі.
Потокове відео має очевидні переваги в порівнянні з локально збереженим цифровим відео, оскільки воно дозволяє відразу або, майже відразу, починати програвати відео, а не чекати повної передачі даних, крім того, дозволяє заощаджувати дисковий простір, оскільки відеозображення не обов'язково зберігати локально. Порівняно з традиційним телебаченням, потокове відео має такі переваги: інтерактивність, персоніфікацію, більше можливостей вибору, якість. Але потокове відео має й ряд технічних проблем, зокрема, низька та погано передбачувана пропускна здатність мережі, що іноді змінюється, втрата частини інформації, варіювання часу затримки доставки пакетів у мережі.
З кожним роком усе підсилюється тенденція конвергенції телекомунікаційних і комп'ютерних мереж і створення мультисервісної мережі нового покоління (Next Generatіon Network, NGN). Використання цифрових мереж для одночасної передачі даних, голосу, відеозображення зробило актуальним розробку нових методів забезпечення необхідної якості обслуговування (Qualіty of Servіce, QoS). Методи QoS покликані вирішити деякі проблеми, актуальні, в тому числі, й для потокового відео, такі, як рівень затримок для чутливого до них трафіку, гарантована середня швидкість для трафіку.
Одним з факторів, що стримують масовість використання потокового відео є обмеження й недосконалості методів групової адресації (multіcast) у мережі Інтернет. Адже технології групової адресації дозволяють поширювати інформацію відразу до великої аудиторії і, в першу чергу, призначені для передачі медіаінформації, у тому числі, потокового відео. Нині технології групової адресації активно розвивають та удосконалюють, що сприяє різко зростаючому за останні роки інтересу до використання потокового відео в застосуваннях із груповою адресацією.
Передача потокового відео актуальна у тому числі і для загальнодержавних та корпоративних автоматизованих комп'ютерних систем і мереж. Зокрема системи передачі потокового відео могли б бути успішно впроваджені, як додатковий засіб передачі інформації у деяких установах України, таких як Академія наук, різні міністерства, вузи і т. д., а також в системах дистанційної освіти.
За останнє десятиріччя здійснено багато досліджень у даній області. Основна задача даних досліджень – складання розкладу передачі пакетів потокового відео так, щоб в умовах даних обмежень мережі отримати максимальну якість відтвореного відеозображення. Але на сьогодні не існує однозначного рішення цього завдання, оскільки рішення залежить від багатьох факторів, таких як спосіб кодування цифрового відео, різних характеристик мережі. Крім того реалізоване рішення має працювати в режимі реального часу на сучасних комп'ютерних системах.
Таким чином, задача складання оптимального розкладу передачі пакетів потокового відео є актуальною сьогодні й не буде закрита в найближчі роки. Галузь передачі потокового відео – порівняно нова й активно розвивається близько 10 останніх років, а завдання, якому присвячена дисертаційна робота, як наукова задача й як інформаційна технологія знаходиться на підйомі, завдяки великому інтересу до цієї галузі в комерційних колах, серед комп'ютерних компаній, у науковому співтоваристві. Більше того, можна сказати, що завдяки розвитку нових технологій і мереж передачі даних у найближчий час очікується зростання інтересу до потокового відео й стрімкий ріст його використання.
Зв'язок роботи з науковими програмами, планами, темами. Основні результати даного дисертаційного дослідження отримані в Інституті кібернетики ім. В.М. Глушкова НАН України в рамках таких наукових тем:
- ВФ-200.06 «Системи реального часу. Цифрова обробка сигналів та зображень, геоінформаційні комплекси, мережі комп’ютерів, агент-технології пошуку інформації», (2005р., № держреєстрації 0101U000076);
- ВФ-200.07 «Розробка принципів побудови інтелектуальних відеосистем з адаптацією параметрів зчитування відео даних та механізмами уваги і слідкування на базі інтелектуальних відеокамер», (2006 р., № держреєстрації 0102U003206).
Мета і завдання дослідження. Основною метою дисертаційної роботи є дослідження та розроблення методів і алгоритмів підвищення надійності та достовірності інформаційних систем передачі потокового відео за рахунок оптимізації розкладу пакетів відеозображення переданого по симплексному каналу мережі із втратами даних.
Поставлена мета окреслила наступне коло завдань:
- аналіз існуючих методів і систем передачі аудіовізуальних даних по мережі із втратами даних і відсутнім зворотнім каналом зв'язку. Обґрунтування необхідності розробки нового методу прямої корекції помилок (ПКП) для вирішення поставленої задачі;
- розробка нового методу складання оптимального розкладу передачі аудіовізуальних даних по симплексному каналу мережі із втратами даних. Метод має характеризуватися змінним коефіцієнтом надлишковості для кожного елемента даних відеопослідовності, бути сумісним з усіма розповсюдженими на сьогоднішній день алгоритмами компресії відеозображення, мати низьку складність обчислень і забезпечувати передачу даних у режимі реального часу на сучасних комп'ютерах;
- розробка алгоритму мінімізації варіювання якості переданого відеозображення;
- розробка критеріїв та методів розбивки відеопослідовності на пакети, причому їх розмір має бути оптимальним з погляду якості переданого відеозображення;
- адаптування розроблених методів та алгоритмів для випадків обмеженого розміру вікна передачі даних і високого варіювання часу доставки пакетів;
- створення інформаційної технології, що реалізує розроблений метод. Проведення та аналіз експериментів з метою порівняння методу з альтернативними методами захисту від помилок під час передачі потокового відеозображення.
Об'єкт дослідження – процес передачі аудіовізуальних даних по мережі із втратами даних.
Предмет дослідження – методи та алгоритми оптимізації розкладу передачі пакетів потокового відео по мережі із втратами даних.
Методи дослідження. В основу проведених досліджень покладені ідеї й методи математичного моделювання, динамічного програмування, безумовної оптимізації, теорії ймовірностей, теорії графів.
Наукова новизна отриманих результатів. Розроблений новий метод розв'язання задачі складання оптимального розкладу аудіовізуальних даних по симплексному каналу мережі із втратами даних. Метод відрізняється від уже існуючих насамперед тим, що уперше запропоновано використовувати ПКП зі змінним коефіцієнтом надлишковості для кожного елемента даних відеопослідовності. Теоретично й експериментально показана висока ефективність такого підходу.
За рахунок використання методу спуску удосконалений спосіб коректування множника Лагранжа за умов мінливої пропускної здатності мережі та бітової швидкості програвання відеозображення. Запропоновано використовувати буферизацію для зменшення варіювання якості відеозображення за умов досить великого вікна передачі даних.
Уперше отримано критерії поліпшення якості відеозображення під час об'єднання неповних пакетів. На основі отриманих критеріїв розроблений алгоритм об'єднання неповних пакетів.
Обґрунтованість і достовірність наукових положень, висновків і рекомендацій. Оптимальність, з погляду якості переданого відеозображення, запропонованого методу складання розкладу передачі пакетів потокового відео доведена аналітично.
Теоретичне обґрунтування підтверджене експериментально. Під час проведення експериментів використовувалися як об'єктивні, так і суб'єктивні (із залученням експертів) методи виміру якості відеозображення.
Крім того, вірогідність наукових положень, висновки й практичні рекомендації, наведені в дисертації, підтверджені дослідами при виконанні ряду проектів по впровадженню передачі потокового відео.
Практичне значення отриманих результатів. При використанні запропонованого методу складання оптимального розкладу аудіовізуальних даних по симплексному каналу мережі із втратами даних у режимі реального часу якість переданого відеозображення на 0.7 – 1.4 дБ. вища, ніж при використанні інших методів захисту від помилок при передачі потокового відео. Метод може використовуватися з усіма розповсюдженими на сьогоднішній день алгоритмами компресії відеозображення.
На основі запропонованих алгоритмів стало можливим будувати нові й поліпшувати існуючі блоки захисту від помилок в інформаційних технологіях передачі потокового відео, тим самим підвищуючи надійність та достовірність комп'ютерних систем, зокрема, систем управління та дистанційного навчання.
Вірогідність наукових положень, висновки й практичні рекомендації, які містяться в дисертації, підтверджені при виконанні науково-технічних проектів:
- система передачі відео на вимогу, розроблена компанією Uniphone (США) і упроваджена в компанії Cisco Systems (США);
- система дистанційного навчання, розроблена науково-виробничим підприємством «АСТЕС» науково-виробничої корпорації «Київський інститут автоматики», про що свідчать акти впровадження, приведені в додатку до дисертаційної роботи.
Особистий внесок здобувача. Основні результати дисертаційної роботи отримані автором особисто. У роботах, виконаних у співавторстві, автору належать такі результати: [1] – розробка алгоритмів методу перебору з поверненням і адаптації до дерева залежностей; [3] – побудова аналітичної моделі задачі й проведення експерименту.
Апробація результатів дисертації. Основні результати роботи доповідались і обговорювались на наукових конференціях: ІІІ Міжнародна наукова конференція “Інтелектуальні системи прийняття рішень і прикладні аспекти інформаційних технологій”, Євпаторія, 14-18 травня 2007 р.; VІІ Міжнародна наукова конференція студентів і молодих учених "Політ", Київ, 12-13 квітня 2007 р.; V Міжнародна науково-практична конференція по програмуванню УКРПРОГ'2006, Київ, 23-25 травня 2006 р.; VІ Міжнародна наукова конференція студентів і молодих учених "Політ", Київ, 11-12 квітня 2006 р.; XLVІІІ Наукова конференція МФТІ, Москва – Долгопрудний, 25-26 листопада 2005 р.; XLVІІ Наукова конференція МФТІ, Москва – Долгопрудний, 26-27 листопада 2004 р.
Результати дисертаційної роботи також доповідались, і обговорювались та отримали позитивну оцінку на семінарах Інституту кібернетики ім. В.М. Глушкова НАН України.
Публікації. За темою дисертації опубліковано десять робіт, чотири статті опубліковано в наукових фахових виданнях.
Структура та обсяг дисертації. Робота складається із вступу, чотирьох розділів, висновків, списку використаних джерел із 116 найменувань. Повний обсяг роботи 166 сторінок, із них основний текст 146 сторінок. Дисертація містить 45 рисунків і 12 таблиць.
ЗМІСТ РОБОТИ
У вступі проаналізовано стан наукової задачі, обґрунтовано актуальність дисертаційної роботи, показано зв'язок обраного напрямку з науковими темами, сформульовано основну мету та задачі дослідження. Також викладено застосовані методи дослідження, наведена коротка анотація нових наукових положень здобувача в галузі потокового відео, наведені дані про апробацію й впровадження результатів роботи.
Перший розділ присвячений огляду основних етапів, питань і завдань, які виникають при передачі потокового відео. Виділена задача складання оптимального розкладу пакетів по мережі із втратами даних, систематизовані основні напрямки її рішення і розглянуті існуючі роботи, присвячені рішенню даної задачі за умов відсутності зворотнього каналу зв'язку.
У роботі описані основні етапи розвитку області передачі потокового відео. Показано, що область передачі потокового відео порівняно нова. Перші системи передачі потокового відео з’явились на початку 90-х років, а активно область почала розвиватися лише в кінці 90-х років. Розглянуті основні проблеми, які актуальні на сьогоднішній день: низька, змінна й погано передбачувана пропускна здатність мережі; втрата частини інформації; варіювання часу доставки пакетів у мережі. Розглянуті типові застосування передачі потокового відео й визначені їхні основні особливості. Дана робота присвячена питанню втрати частини інформації в умовах симплексного каналу зв'язку, що дозволяє передавати інформацію тільки в одному напрямку.
Cистематизовані існуючі напрямки в області потокового відео по мережі із втратами даних і виділено два рівні здійснення захисту від помилок: рівень каналу зв'язку й рівень кодування даних. Основні підходи захисту від помилок на рівні каналу зв'язку – це повторні передачі, пряма корекція помилок (ПКП) і диверсифікованість каналу зв'язку, а на рівні кодування даних – це маскування помилок і стійкі до помилок способи відеокодування. У роботі коротко викладені суть, основні переваги й недоліки кожного підходу. Показано що ПКП є найбільш загальним підходом захисту від помилок при передачі відеозображення по симплексному каналу зв'язку, водночас цей підхід може застосовуватися разом з будь-яким іншим підходом.
У роботі зібрано, коротко викладено й проаналізовано більше 20 основних робіт різних авторів, які присвячені ПКП при передачі потокового відео по симплексному каналу мережі із втратами даних. Показано, що в усіх існуючих роботах коефіцієнт надлишковості або постійний для всього відеозображення, або змінно-дискретний, тобто постійний для кожного рівня відеозображення при масштабуванні у просторі чи часі. Крім того, у деяких роботах будується досить трудомістке рішення, яке важко застосовувати без істотних спрощень у режимі реального часу. Показано, що необхідний новий метод застосування ПКП, не прив'язаний до способу кодування відеозображення, зі змінним коефіцієнтом надлишковості для всіх елементів даних відеозображення, що має низьку складність обчислень та забезпечує передачу даних у режимі реального часу на сучасних комп'ютерах.
У другому розділі сформульована аналітична модель задачі, побудовані алгоритми її рішення. Наводяться умови застосування й обмеження методу.
У роботі використовуються як об'єктивна, так і суб'єктивна техніка оцінки якості одержуваного на приймачі відеозображення. Для об'єктивної оцінки якості обрано метод пікового відношення сигналу до шуму (PSNR) між вхідним сигналом і сигналом на виході системи, що визначається через середньоквадратичне відхилення (MSE) і вимірюється в децибелах:
, , (1)
де r – кількість біт у пікселі; A, B – розміри відеозображення в пікселях; p(x, y), р'(x, y) – колір пікселя з координатами (x, y) у відтвореному й оригінальному відеозображеннях.
Для більшості сучасних алгоритмів кодування аудіовізуальних даних результатом кодування є набір елементів даних, залежності між якими виражаються у вигляді орієнтованого ациклічного графа. Елементи даних групуються в незалежні один від одного блоки даних, які незалежні один від одного, тобто жоден елемент даних одного блоку не залежить від жодного елемента даних іншого блоку. Таким чином, кожний блок даних має окреме дерево залежностей між елементами даних і може бути використаний без декодування попередніх блоків даних. При цьому з прикладної точки зору елемент даних є неподільним, тобто якщо згубилася частина елемента даних, то весь елемент не може бути використаний. Кожний елемент даних характеризується двома основними параметрами: розміром b в байтах і значимістю d в децибелах – погіршенням якості одержуваного відеозображення при неможливості декодувати елемент даних.
У сучасних мережах передачі даних, у тому числі й мережі Інтернет, дані передаються пакетами з обмеженим розміром. Максимальний розмір пакета залежить від характеристики мережі канального рівня й визначається параметром MTU. Елементи даних, розмір яких більший ніж максимально припустимий розмір, будемо розбивати на пакети.
Вікном передачі елемента даних будемо називати інтервал часу, коли припустима передача всіх пакетів елемента даних. Залежно від типу програми, розмір вікна може сильно варіюватися. Мережа із втратами даних характеризується розподілом ймовірності доставки пакета за часом. Показано, що у випадку досить великого вікна передачі даних ймовірність втрати пакета можна апроксимувати константою е.
Для зменшення ймовірності втрати елемента даних пропонується використовувати метод прямої корекції помилок (ПКП), суть якого в тому, що при пересиланні k пакетів (далі інформаційних пакетів) однакового розміру відправляється n–k надлишкових пакетів того ж розміру. При втраті не більше ніж n–k будь-яких пакетів (не обов'язково надлишкових) завжди можна відновити всі k інформаційних пакетів, але при втраті n–k+1 пакетів й більше інформаційні пакети відновити неможливо. При проведенні експерименту використовувався метод Ріда – Соломона як реалізація ПКП.
У загальному випадку оптимальний розклад передачі пакетів – це розклад, що дає мінімальні втрати якості, обумовлені тим, що частка пакетів не передається або губиться. Введемо поняття ефективної значимості Di і-го елемента даних як очікуване поліпшення якості всього відтвореного відеозображення у випадку передачі елемента даних, розбитого на ki пакетів і передачі ni-ki надлишкових пакетів.
Задачу пошуку оптимальної множини переданих пакетів можна сформулювати, як задачу знаходження вектора кількості пакетів для передачі елементів даних, що дає оптимальну якість відеозображення
, (2)
при обмеженні розміру переданих даних, що рівносильне обмеженню кількості переданих пакетів
(3)
і цілочислового невід’ємного вектора :
. (4)
Задача (2)–(4) є задачею нелінійного цілочислового програмування. Оскільки функція мети (2) несепарабельна, то класичні методи динамічного програмування не застосовні для її рішення.
У роботі задача (2)–(4) апроксимується задачею пошуку максимального значення Лагранжіана:
. (5)
Множник л динамічно коректується залежно від розміру віртуального буфера на стороні відправника.
В основі побудови рішення лежить той факт, що елемент даних завідомо не може бути декодований на приймачі, якщо в розклад передачі пакетів не був доданий хоча б один з елементів даних від якого він залежить. Будемо ітеративно додавати в розклад елементи даних, рухаючись від кореня в глиб дерева залежностей. На першому кроці ітерації в розклад додаються всі основні пакети кореня дерева залежностей між елементами даних. Кожний наступний крок ітерації проходить у три етапи.
Етап 1. Ціль першого етапу така:
- додавання ще не доданих у розклад елементів даних по одному, так, щоб щораз збільшувати значення Лагранжіана (5);
- при цьому для кожного елемента даних, що додається в розклад, знайдемо кількість надлишкових пакетів, для якого збільшення Лагранжіана (5) максимальне.
Наведемо алгоритм пошуку елементів даних, які додаються в розклад на першому кроці ітерації, й визначення кількості надлишкових пакетів для кожного елемента даних. Позначимо S – множину елементів даних вже доданих в розклад.
1. Будуємо множину елементів даних А, кожний елемент якої задовільняє умовам:
- елемент даних ще не доданий у розклад ;
- усі елементи даних, від яких залежить даний елемент даних, уже додані в розклад .
2. Для кожного елемента даних з множини A знайдемо значення аргументу xi', для якого значення функції
(6)
набуває максимуму і відповідне йому значення функції зміни значення Лагранжіана:
. (7)
Виведена формула знаходження ефективної значимості
. (8)
Символом позначено ймовірність відновлення і–го елемента даних, що складається з ki інформаційних і xi-ki надлишкових пакетів, формулу обчислення якої можна одержати, просумувавши значення ймовірностей доставки ki, ki+1, …, xi пакетів:
. (9)
3. Виберемо підмножину A* елементів даних множини A, для яких M додатнє. Це і є шукана множина елементів даних, що додаються в розклад на першому кроці ітерації.
4. Якщо підмножина A* непуста, то для кожного елемента даних із множини A* послідовно збільшуючи xi, починаючи з xi', знайдемо xi'', для якого справедливе
, (10)
де
. (11)
Тоді xi”- ki – кількість надлишкових пакетів для i-го елемента даних.
У роботі показано, що наведений алгоритм відповідає поставленим цілям, що випливає з наступних двох тверджень, доведених у роботі.
Твердження 1. Якщо існує xi , таке, що M додатнє, то для xi’, для якого функція Fi набуває максимального значення, значення функції M так само додатнє. При цьому максимальне значення M досягається для xi більшого або рівного xi’.
Твердження 2. Якщо для xi’’ більшого або рівного xi’ виконуються умови (10), то для нього досягається максимальне значення функції M.
Якщо підмножина A* порожня, то переходимо до другого етапу кроку ітерації, у противному випадку другий етап пропускаємо й переходимо відразу до третього етапу.
Етап 2. На даному етапі виконується пошук у глибину з обмеженою глибиною за множиною елементів даних, ще не доданих у розклад, так щоб сумарне значення Лагранжіана всіх елементів даних було позитивне. Таким чином, якщо на першому етапі кроку ітерації не вдається знайти елемент даних ще не належний до розкладу, то на другому етапі такий елемент даних може бути, проте, включений у розклад, у випадку, якщо в його нащадків значення Лагранжіана позитивне.
Будемо шукати пошуком у глибину множину B елементів даних, яка відповідає таким властивостям:
- кількість елементів даних множини B не більша глибини пошуку N ;
- усі елементи даних множини B ще не додані в розклад передачі пакетів ;
- множина B є пронумерованим списком і елементи даних множини B пронумеровані так, що ніякий елемент даних не залежить від жодного елемента даних наступного за ним ;
- для будь-якого елемента даних множини B справедливе твердження: “Всі елементи даних, від яких залежить елемент даних множини B або належать множині B, або вже додані в розклад передачі пакетів” ;
- для множини B сума змін значень Лагранжіана додатня .
Значення функції обчислюємо так само як і на першому етапі, при цьому вважаємо що всі попередні елементи даних множини B вже додані в розклад. Пошук закінчується після знаходження першої множини, що задовольняє цим умовам. У цьому випадку для кожного елемента даних із множини B послідовно додаємо в розклад xi’ пакетів і вважаємо, що другий етап кроку ітерації закінчений. У випадку, коли на першому або на другому етапі в розклад додана непуста множина пакетів, то переходимо до третього етапу, інакше складання розкладу пакетів для блоку даних закінчується.
Розглянуті питання оптимізації другого етапу кроку ітерації в основі яких лежить розміщення елементів даних першого рівня в порядку зменшення ймовірності знаходження множини В, а так само, виключення тих елементів даних першого рівня, для яких множину В завідомо не буде знайдено.
Етап 3. На цьому етапі значення Лагранжіана (5) збільшується шляхом коректування кількості надлишкових пакетів для деяких, уже доданих у розклад елементів даних. Розглядається множина C елементів даних, кожний з яких задовольняє умовам:
- елемент даних уже доданий в розклад: ;
- принаймні один елемент даних, залежний від даного, вже доданий в розклад:
.
На даному етапі послідовно обчислюємо приріст Лагранжіана для кожного елемента даних з множини C і числа пакетів xi, xi+1 і т.д. доти, доки не буде знайдена кількість пакетів, що задовольняє умовам (10). Якщо це число xi“ більше xi, то в розклад додається xi“- xi надлишкових пакетів для i-го елемента даних. Приріст Лагранжіана обчислюється за формулою
. (12)
Розглянуті питання оптимізації третього етапу кроку ітерації, в основі яких лежить алгоритм хешування значення ймовірності доставки пакетів, уже доданих у розклад.
Запропонований алгоритм коректування множника Лагранжа в задачі (5) при реалізації методу за умов мінливої пропускної здатності мережі й бітової швидкості відеозображення. На кожному кроці ітерації методу складання розкладу передачі пакетів, множник коректується методом спуску. Для оцінки початкового значення множника наступного блоку даних будемо змінювати множник Лагранжа щодо попереднього блоку даних пропорційно зміні бітової швидкості відеозображення й обернено пропорційно зміні пропускної здатності мережі.
Для зменшення варіювання якості відеозображення запропоновано використовувати метод буферизації, що можливо тільки у випадку існування досить великого вікна передачі пакетів. В основі методу лежить передача відеозображення “про запас” на проміжках з надлишком пропускної здатності так, щоб використати ці дані на проміжках з дефіцитом пропускної здатності. Показано, що введення буферизації є найбільш ефективним у випадку, коли середня пропускна здатність мережі на 0–30 % перевищує середню бітову швидкість відеозображення. Знайдений розмір буфера для ефективного використання буферизації, рівний 10–30 секундам програвання відеозображення.
Обґрунтовані умови застосовності й основні обмеження методу:
1. Основне припущення зроблене в роботі щодо способу відеокодування – це наявність залежності у вигляді орієнтованого ациклічного графа між елементами даних відеопослідовності, а так само існування інтра-кодування, тобто можливість розбиття відеопослідовності на послідовність незалежних ациклічних графів. Це припущення набагато слабкіше, ніж припущення зроблене в більшості робіт, присвячених використанню методики ПКП зі змінним коефіцієнтом надлишковості для різних частин відеозображення. Показано, що практично завжди таке обмеження припустиме і, що метод може бути використаний з усіма розповсюдженими на сьогоднішній день алгоритмами компресії відеозображення.
2. У роботі зроблено два припущення щодо розміру вікна передачі даних. По-перше, у момент складання розкладу для блоку даних блок має бути повністю закодований, що важливо у випадку коли кодування й передача відеозображення виконуються в режимі реального часу. По-друге, передбачається, що розподіл ймовірності втрати пакета не залежить від часу відправлення пакета, що справедливо тільки для досить великого розміру вікна.
3. У роботі передбачається, що мережа характеризується втратами частини даних, а так само відсутнім зворотним каналом зв'язку. Ще одне припущення зроблене щодо характеру втрат, а саме, передбачається, що губляться окремі пакети, а не біти інформації.
Третій розділ присвячений особливостям реалізації методу, зокрема у випадках, коли припущення 2 і 3, зроблені у другому розділі не вірні, а так само, дослідженню способів застосовності методу разом з іншими методами захисту від помилок.
Розглянуте питання об'єднання неповних пакетів. Якщо розмір елемента даних не ділиться націло на максимально припустимий розмір пакета, то при розбитті елемента даних на пакети останній пакет буде меншого розміру, ніж решта пакетів. Будемо називати такий пакет неповним. Отримані критерії поліпшення якості відеозображення при об'єднанні неповних пакетів i-го елемента даних, що містить ki інформаційних і ni-ki надлишкових пакетів й j-го елемента даних що містить kj інформаційних і nj-kj надлишкових пакетів і їх асоціювання з j-м елементом даних у тому розумінні, що надлишкові пакети для об'єднаного будуть додаватися в рамках елемента даних. Тут розрізняють три випадки. У випадку, коли i-й елемент даних є нащадком j-го, таке об'єднання завжди збільшує значення Лагранжіана і об'єднані неповні пакети завжди слід асоціювати з j-м елементом даних. Для випадку комутації пакетів довільного, але не більшого ніж заданий, розміру критерієм поліпшення якості відеозображення є виконання нерівності
, (13)
а для випадку комутації пакетів однакового розміру –
, (14)
де – різниця ймовірностей відновлення всіх пакетів i-го елемента даних після й до об'єднання його неповного пакета з неповним пакетом j-го елемента даних, яка виражається формулою
. (15)
Критерієм вибору елемента даних для асоціювання двох об'єднаних неповних пакетів, у випадку, коли вони не залежать один від одного, є знаходження максимального з двох значень:
. (16)
Будемо зберігати список P усіх доданих у розклад елементів даних з ненульовим розміром залишку неповного пакета, відсортованих за розміром залишку в неповному пакеті в порядку зростання. Тоді схема роботи алгоритму об'єднання неповних пакетів, при додаванні у розклад після першого або другого етапу кроку ітерації нового елемента даних a з непустим неповним пакетом розміру w, виглядає так:
1. Знайдемо елемент даних b серед множини елементів даних, від яких залежить елемент даних a, з мінімальним розміром залишку неповного пакета, більшим або рівним w.
2. Якщо елемент даних b існує, об'єднаємо його неповний пакет з неповним пакетом елемента даних a і проасоціюємо об'єднаний пакет з елементом даних b. Виходимо із циклу й закінчуємо пошук.
3. Якщо елемент даних b не існує, знайдемо елемент даних c з мінімальним розміром залишку неповного пакета більшим або рівним w.
4. Якщо елемент даних c не існує, не об'єднуємо неповний пакет елемента даних a ні з яким іншим неповним пакетом і додаємо його в список P. Виходимо із циклу й закінчуємо пошук.
5. Якщо елемент даних c існує, але не задовольняє умові доцільності об'єднання (13) або (14), позначаємо с наступний елемент даних зі списку P і повертаємося до кроку 4.
6. Якщо елемент даних c існує й задовольняє умові доцільності об'єднання (13) або (14), об'єднаємо його неповний пакет з неповним пакетом елемента даних a і проасоціюємо його з елементом даних, знайденим з умови (16). Виходимо із циклу й закінчуємо пошук.
У роботі розглянуто питання існування елементів даних належних декільком деревам, що актуальне для деяких алгоритмів кодування. Запропоновано додавати в розклад передачі такі елементи даних у два етапи: перший – проходить при складанні розкладу першого блоку даних, другий – при складанні розкладу другого блоку даних.
Розглянутий випадок, коли припущення зроблене в розділі 2 про те, що розподіл ймовірності втрати пакета не залежить від часу відправлення пакета, не справедливо. Тоді деякі пакети доставляються на приймач пізніше моменту часу, коли вони мають бути декодовані. Експериментально показано, що це можливо за умов не досить великого розміру вікна передачі даних або високого варіювання часу доставки пакетів. У цьому випадку запропоновано використовувати підхід, аналогічний підходу, описаному в роботі Ву, коли спочатку будується розклад передачі пакетів без врахування їхнього часу декодування, а потім коректується перестановками. Метод Ву адаптується для розглянутого в роботі завдання, зокрема, пропонується спосіб застосування методу у випадку довільного алгоритму кодування відеозображення, водночас, як у роботі Ву передбачається, що відео закодоване алгоритмом MPEG-2. Для цього замість перестановок тільки I-кадрів і P-кадрів (як було запропоновано в роботі Ву), послідовно розглядаються всі можливі елементи даних.
Розглянуті можливості використання спільного застосування методу ПКП й методів ретрансмісії. Якщо розширити підхід запропонований у роботі Чоу і Міао, розширивши його з методами ПКП, то ймовірність втрати елемента даних можна зменшити.
У четвертому розділі наведені метод проведення експерименту і його результати.
Була виміряна якість відеозображення, переданого запропонованим у роботі способом, об'єктивним (PSNR) і суб'єктивним методами, а так само був проведений ряд експериментів, що досліджують ефективність використання буферизації й об'єднання неповних пакетів.
Експериментально доведено, що при реалізації з глибиною пошуку 4–6 та використанням етапу 3, метод забезпечує передачу даних в режимі реального часу. При цьому якість переданого відеозображення на 0.7–1.4 дБ. вища, ніж при використанні постійного коефіцієнта надлишковості для кожного рівня багаторівневого відеозображення (рис. 1).
Рис. 1. Залежність якості відеозображення від алгоритму складання розкладу:
Пост. – ПКП з постійним коефіцієнтом надлишковості для всього відеозображення; Рівн. – ПКП з постійним коефіцієнтом надлишковості для кожного рівня відеозображення; 1-10 – метод, запропонований у дисертаційній роботі з відповідною глибиною пошуку
Суб'єктивна оцінка якості відеозображення з залученням 20 експертів підтвердила результати експерименту (рис. 2).
Рис. 2. Отримане відеозображения для різних алгоритмів складання розкладу
а – передача без втрат, тобто відеозображення на відправнику; b – метод, запропонований у дисертаційній роботі з глибиною пошуку 5; c – ПКП з постійним коефіцієнтом надлишковості для кожного рівня відеозображення; d – ПКП з постійним коефіцієнтом надлишковості для всього відеозображення
ВИСНОВКИ
У дисертаційній роботі наведено теоретичне узагальнення і нове розв’язання наукового завдання оптимізації розкладу передачі пакетів потокового відео по мережі із втратами даних, що базується на застосуванні ПКП зі змінним коефіцієнтом надлишковості для кожного елемента даних відеопослідовності.
Найважливіші наукові й практичні результати дисертаційної роботи такі:
1. Досліджені основні методи і алгоритми підвищення надійності та достовірності систем передачі потокового відео та розроблена їх класифікація. Обґрунтоване використання методу прямої корекції помилок (ПКП) для рішення задачі оптимізації розкладу передачі пакетів потокового відео по мережі із втратами у випадку симплексного каналу зв'язку. Показана необхідність створення нового методу ПКП зі змінним коефіцієнтом надлишковості, не прив'язаного до способу кодування відеозображення, що має низьку складність обчислень і забезпечує передачу даних у режимі реального часу на сучасних комп'ютерах.
2. Розроблений новий метод складання оптимального розкладу аудіовізуальних даних під час передачі по симплексному каналу мережі із втратами даних. В основі методу лежать ПКП зі змінним коефіцієнтом надлишковості для кожного елемента даних відеопослідовності, ітеративний алгоритм пошуку по дереву залежностей між елементами даних відеопослідовності, алгоритм знаходження оптимальної кількості надлишкових пакетів шляхом їхнього послідовного збільшення. Метод може використовуватись з усіма розповсюдженими на сьогоднішній день алгоритмами компресії відеозображення. Розроблений метод має низьку складність обчислень і забезпечує передачу даних у режимі реального часу на сучасних комп'ютерах, водночас він може бути адаптований для систем із широким спектром обчислювальної потужності.
3. Для зменшення варіювання якості відеозображення запропоновано використовувати метод буферизації. Показано, що введення буферизації є найбільш ефективним у випадку, коли середня пропускна здатність мережі на 0–30 % перевищує середню бітову швидкість відеозображення.
4. Отримані критерії поліпшення якості відеозображення при об'єднанні неповних пакетів. Розроблений алгоритм об'єднання неповних пакетів. Експериментально підтверджена доцільність об'єднання неповних пакетів для відеозображень із низкою бітовою швидкістю.
5. У випадках не досить великого розміру вікна передачі даних і високого варіювання часу доставки пакетів, запропоновано використовувати метод Ву перестановок пакетів і наведено особливості його використання для розглянутої задачі.
6. Розроблена інформаційна технологія, що реалізує передачу аудіовізуальної інформації запропонованим методом. Проведений ряд експериментів, що показує високу ефективність методу. Експериментально доведено, що за умов роботи в режимі реального часу якість переданого відеозображення на 0.7–1.4 дБ. вище, ніж при використанні постійного коефіцієнта надлишковості для кожного рівня багаторівневого відеозображення.
Рекомендації щодо використання отриманих результатів. Розроблені методи можуть успішно використовуватися в різних системах передачі потокового відео, таких як дистанційне навчання, відео на вимогу, інтерактивна реклама, телебачення підприємства, системи спостереження. Розроблена інформаційна технологія може бути інтегрована із технологіями обробки відеозображення, наприклад, у системах спостереження; із технологіями побудови мультимедійного контенту, наприклад, у системах інтерактивної медіа реклами. Технологія може застосовуватися як в мережі Інтернет, так і в корпоративних мережах.
Перспективи розвитку. Основні зусилля подальших досліджень по вдосконаленню моделі й технології мають бути спрямовані, насамперед, в інтегрування запропонованого методу з іншими методами захисту від помилок при передачі потокового відео, у першу чергу, на рівні кодування відео. Зокрема, при інтегруванні з методом маскування помилок можна поліпшити рішення розглянутої задачі, якщо в аналітичній моделі врахувати поліпшення якості відеозображення за рахунок маскування помилок. Перспективним є так само й інтегрування методу з методами, заснованими на диверсифікованості каналів зв'язку. Основною проблемою тут є висока складність задачі в загальному випадку. Але для окремих випадків, коли заздалегідь відомі кількість і характеристики каналів зв'язку, результати даної роботи можуть бути поліпшені. У роботі коротко розглянуті можливості комплексного застосування ПКП з методами ретрансмісії. Необхідне аналітичне рішення задачі, а також більш точний опис умов, коли саме доцільний комплексний підхід.
Важливим є відмова від деревоподібної структури закодованого відеозображення. Зокрема, доцільно розглянути нові алгоритми кодування, в основі яких лежать методи MSC і MDE.
При програмній реалізації методу важливим є розподіл його роботи між декількома процесорами. Таким чином, використавши багатопроцесорні апаратні системи, можна збільшити глибину пошуку, тим самим, поліпшити якість відтвореного відеозображення.
ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ ОПУБЛІКОВАНІ В ТАКИХ ПРАЦЯХ:
1. Оксюк О.А, Оксюк О.А. Методы оптимизации качества потоковых видеоизображений при передаче по сети Интернет // Проблеми програмування. – 2006. – Спецвипуск УКРПРОГ. – С. 211–215.
2. Оксюк О.А. Оптимизация передачи потокового видео по сети с пропускной способностью, близкой к скорости битового потока видеоизображения // Комп’ютерні засоби, мережі та системи. – 2006. – № 5. – С. 86–92.
3. Оксюк О.А., Петрухин В.А. Оптимизация передачи по сети с ограниченной и меняющейся пропускной способностью потоковых видеоизображений // Комп’ютерна математика. – 2006. – № 1. – С. 152–159.
4. Оксюк О.А. Проблемы передачи потокового видео по симплексному каналу сети с потерями данных // Реєстрація, зберігання і обробка даних. – 2007. – № 2. – С. 69–76.
5. Оксюк О.А. Составление расписания передачи пакетов потокового видео при широковещании в сети Интернет // Исследовано в России, 2007 – С. 944–953. http://zhurnal.ape.relarn.ru/articles/2007/091.pdf
6. Оксюк О.А. Проблемы передачи потокового видео по симплексному каналу сети с потерями данных // Матеріали ІІІ Міжнародної наукової конференції “Інтелектуальні системи прийняття рішень і прикладні аспекти інформаційних технологій”. – Євпаторія, 2007 – 2. – С. 202–205.
7. Оксюк О.А. Составление расписания передачи пакетов потокового видео при широковещании в сети с потерями данных // Матеріали VІІ Міжнародної наукової конференції студентів і молодих учених "Політ". – Київ, 2007. – С. 59.
8. Оксюк О.А. Оптимизация расписания пакетов при передаче потоковых мультимедийных данных // Матеріали
