Алгоритм стиснення відео 'pixel behaviour check'
Дмитро Сахань
Якщо
ви вмієте програмно оперувати відеоданими і маєте вільний час,
пропоную вам закодувати PBC-алгоритм стиснення відеопотоку. Відразу скажу, що
алгоритм новий і ніким не випробуваний (для довідки: статті вже майже два
року). З цієї ж причини не можу стверджувати, що він краще або гірше MPEG4 або
DivX-алгоритмів. Мій алгоритм використовує підхід до кодування відео, відмінний
від MPEG, і ефективний тільки для кодування послідовності відеокадрів.
Основні особливості MPEG
Для
Спершу хочу коротко пояснити основну ідею MPEG-алгоритму (DivX є однією
з версій MPEG4). Шифрація відеоданих в MPEG в своїй основі використовує
алгоритми шифрування специфікації JPEG. Додатково в MPEG використовуються
алгоритми компенсації руху, I-кадри і т.д. і т.п. Але розглянемо, як в JPEG
кодується статичний кадр зображення.
Спочатку
всі колірний простір кадру перетвориться з RGB в YCbCr. Необхідність
цього перетворення полягає в тому, що око більше чутливий до яскравості
кольору, ніж до його відтінку. Y - це величина яскравості кольору, а Cb і Cr - колірні
величини, що визначають відтінок і насичення кольору (вони визначають кількість
синьою і червоною складових у кольорі). Уже на цьому етапі відбуваються втрати в
інформації, тому що формули перетворення RGB в YCbCr і назад не дозволяють
точно (значення в значення) зберегти деякі кольори. Як ви помітите у
Надалі, JPEG-алгоритм розрахований на максимальну втрату надлишкової
інформації. Цим-то і досягається високий ступінь стиснення.
Потім
проводиться дискретизація зображення. Це ще один спосіб втратити інформацію,
але вже у великих обсягах. Ідея в тому, що яскравість (Y) береться для кожного
пікселя зображення, а цветоразность (Cb, Cr) - як середнє значення блоку 2x2
пікселів. Взагалі-то в стандарті JPEG для Y, Cb і Cr визначено за два
коефіцієнта дискретизації: по горизонталі і по вертикалі. Тому хоч
яскравість, хоч цветоразность при бажанні можна брати як середнє значення будь-якого
за розмірами блоку (хоч 10x10 пікселів). У кінцевому підсумку це позначиться на
як зашифрованого зображення. Великі значення дискретизації - перший
крок до отримання "зубчастого" зображення.
Після
цього проводиться дискретне косінусоідальное перетворення (DCT) зображення,
яке ділиться на блоки 8x8 пікселів, і до кожного блоку застосовується
DCT-перетворення. Мета цього в тому, щоб отримати по 64 амплітуди частотного
простору для кожного з блоків 8x8 пікселів. Потім 64 амплітуди
зигзагоподібно переставляються в блоці, щоб отримати вектор з 64
коефіцієнтами, відсортований критеріями просторової частоти.
Тепер
кожен вектор з 64 коефіцієнтів квантів за допомогою заздалегідь заданих таблиць
квантування. Це потрібно для того, щоб видалити високі частоти, які
являють собою високу деталізацію даного блоку зображення. У результаті
квантування вектор містить велику кількість розташованих підряд нулів. Ну
і весь вектор кодується вже з допомогою самого звичайного RLE-алгоритму (Run
Length Encoding). У висновку до отриманого набору байт застосовується
кодування Хаффмана, що дозволяє записати байти довжини RLE-кодування з
самими мінімальними витратами біт.
Алгоритм
MPEG через певну кількість кадрів завжди створює I-кадр, який
кодується подібно JPEG. В кадрах між I-кадрами закодована компенсація
руху блоків зображення. Як бачите, MPEG має досить складний алгоритм.
Алгоритм "Pixel Behaviour Check"
Алгоритм
має назву "Контроль поведінки пікселя". Основна ідея в тому, що
ми розглядаємо кожен піксель як об'єкт, що має поведінку. І кодування
ведеться не щодо поточного кадру, а крізь кадри. Як ніби кадри
розташовані один над іншим, а ми дивимося крізь них і реєструємо поведінка
кожного пікселя. Поведінка пікселя має три стани: залишається незмінним,
починає зростати або зменшуватися. Піксель залишається незмінним, коли на
Протягом декількох кадрів значення його кольору не змінюється. Піксель зростає,
коли значення його кольору з кадру в кадр продовжує збільшуватися. Піксель
зменшується, коли значення його кольору постійно зменшується.
В
цьому алгоритмі відсутня необхідність в алгоритмах компенсації руху.
Втрати в закодованому зображенні присутні, але вони малозначні,
тому непомітні. Також немає ефекту "зубчатість" зображення. Чи не
менш важлива простота роботи алгоритму. Тепер перейду до його опису. Для
зручності буду відразу оперувати даними у вигляді структур. Почнемо з заголовка
відеопотоку.
type PBCvideoHeader = record
Width: Word;// ширина кадру відеофільму
Height:
Word;// висота кадру відеофільму
FrameCount:
DWord;// кількість кадрів в відеофільмі
FrameRate:
Byte;// швидкість кадрів (кадрів в секунду)
Properties:
Byte;// властивості кодування
StartRCr:
Byte;// початкове заповнення площини червоного кольору/Cr
StartGY:
Byte;// .............................. зеленого кольору/Y
StartBCb:
Byte;// .............................. синього кольору/Cb
end;
Думаю,
з полями Width і Height все зрозуміло - в них зберігаються висота і ширина кадру в
пікселях. Поле FrameCount містить загальну кількість кадрів в відеопотоці, а
поле FrameRate - швидкість проходження кадрів, що вимірюється в кадрах на секунду.
Поле Properties містить відомості про особливості кодування відео. Річ у
те, що алгоритм підтримує як RGB-простір, так і YCbCr. Крім цього
передача змін пікселя може бути як у вигляді прямих значень, так і з
допомогою процентних відносин (пізніше поясню, що означає "прямі
значення ", а що" процентні відносини "). Ці відомості
вказуються у двох молодших бітах поля Properties. Решта біти поля
зарезервовані для подальших модифікацій і повинні бути встановлені в нуль.
Поле
Properties (побітне)
біти
8 .. 3 = зарезервовані і повинні бути рівні 0
біт
2 (RatioType) = 0 - зміни пікселя задані у вигляді прямих значень
1
- Зміни пікселя задані за допомогою процентних відносин
біт
1 (ColorSpace) = 0 - використовується колірний простір RGB
1
- Використовується колірний простір YCbCr
Поля
StartRCr, StartGY і StartBCb містять початкові значення, якими заповнені
відповідні кольорові площині опорного кадру (нижче описано, що це за
кадр). Як ви розумієте, поле StartRCr містить або значення червоного кольору,
якщо в полі Properties (його бітом ColorSpace) вибране колірний простір
RGB, або значення червоної цветоразності, якщо вибрати колірний простір
YCbCr. Відповідно, поле StartGY - значення зеленого кольору у RGB або яскравість
в YCbCr, а поле StartBCb - синій колір в RGB чи синю цветоразность в YCbCr.
Одразу зауважу, що початкові значення в залежності від біта RatioType поля
Properties задаються або прямими значеннями, або процентними відносинами.
Опорний
кадр - це кадр, від пікселів якого виконується кодування чи декодування
відеоряду. Іншими словами, опорний кадр - це своєрідний колір фону першим
кадру відеоряду. Всі пікселі опорного кадру заповнені одним і тим же кольором.
Цей кадр вводиться спеціально перед початком відео, щоб ефективно почати
кодування перших кадрів. Надалі опорний кадр не використовується. Але як ви
бачите, значення фону задається для кожної колірної площині окремо, тому що
кодування пікселів здійснюється не за їх загального кольору, а по кожній колірної
площині. А в кожній площині фонове значення може бути своїм. Таким
чином, у кодіровщік повинна бути присутнім функція, що забезпечує пошук
максимально повторюваних значень у відповідних площинах першого кадру
відео (саме відео, а не опорного кадру) і занесення цих значень у поля
StartRCr, StartGY і StartBCb. Отриманим RGB-або YCbCr-значенням заповнюються
всі пікселі опорного кадру.
Відразу
за заголовком відеопотоку слід масив закодованих наборів поводжень. Мета
використання цього масиву: максимально підвищити ступінь стиснення відео.
Уявімо, що у відео існує сцена, де промінь світла від ліхтарика висвітлює
об'єкти у затемненій кімнаті. Луч рухається через весь кадр зліва-направо.
Спочатку об'єкти в лівій частині кадру потроху виходять з темряви, потім
стають чітко видно, потім поступово йдуть у темряву. Далі об'єкти
середній частині кадру, а потім і правій частині. Незважаючи на різні колірні
відтінки об'єктів кімнати, моделі поведінки багатьох пікселів на екрані мають
подібні риси (однакові пропорції наростання або зменшення освітленості і
тощо). Закодований у якому-небудь елементі масиву даний набір поводжень
(наростання/спадання освітлення) можна при кодуванні пікселя просто вказати
індекс цього елемента масиву. Незалежно від кольору пікселя, буде максимально
точно змодельоване його поведінка на екрані в усіх схожих сценах відео.
type PBCvideoBehaviours = record
ItemCount: Word;
Behaviours: array of
PBCvideoBehaviourSet;
end;
type PBCvideoBehaviourSet = record
Count: Byte;
Behaviour: array of Byte;
end;
Масив
поведінки складається з поля ItemCount (кількість елементів у масиві =
кількість наборів поводжень в масиві) і самих елементів масиву. Цей масив
не може бути більше ніж 8192 елементів, що пояснюється способом зберігання
інформації у поле індексу (розглядається нижче) при кодуванні поведінки
пікселя. Кожен елемент масиву складається з поля Count (кількість
закодованих поводжень в даному наборі) і байтового масиву з закодованими
поведінками. У будь-який елемент масиву можна закодувати набір максимум з 256
поводжень (0 = 1 поведінку, 1 = 2 поведінки і так далі). Поведінки в наборі
кодуються так само, як вони кодуються для пікселів. Кодування поводжень для
пікселів розглядається нижче.
З
моменту створення опорного кадру можна починати кодування відеоряду.
Закодований потік представляє собою послідовний набір поводжень
пікселів відео. Для кожного пікселя послідовно кодуються поведінки по
всім його колірною площинах. Будь-яка поведінка в закодованому потоці задається
у вигляді структури з двох/трьох полів. Нижче для наочності я привів структури
поводжень. Коли колірна площину пікселя не змінюється, поведінка кодується
двома полями структури PBCvideoIdentical. При зміні колірної площині
пікселя поведінка кодується трьома полями структури PBCvideoChanged. Окрема
структура PBCvideoEncoded з двома полями використовується, коли поведінка колірної
площині пікселя кодується певною послідовністю поводжень, описаної
в масиві наборів поводжень. Типи полів структури наведені росіянами
назвами, а нижче поясню, як працює кожен з цих типів.
type PBCvideoIdentical = record
Code: 2_біта;
Repeat: код_повторов;
end;
type PBCvideoChanged = record
Code: 2_біта;
Repeat: код_повторов;
Extent: Byte;
end;
type PBCvideoEncoded = record
Code: 2_біта;
Index:
код_індекса;
end;
Поле
Code містить двухбітний код поведінки колірної площині пікселя. Всього можна
задати чотири коду для поведінки: 00 - не змінюється, 01 - збільшується, 10 --
зменшується і 11 - закодований у масиві поводжень. Поле коду поведінки
ідентично для всіх трьох зазначених структур поведінки.
Поле
Repeat містить в собі кількість кадрів, які повторюється заданий
поведінка колірної площині пікселя. Поведінка повторюється хоча б один кадр,
але для ефективності використання поля Repeat кількість кадрів повторення
перед збереженням у цьому полі переводиться в діапазон від 0 до N-1, а не від 1 до
N. Це досягається вирахуванням 1 з кількості кадрів, де 0 тепер буде
означати 1 кадр, 1 означатиме 2 кадру і так далі. Поле Repeat може мати
довжину 6 біт або 14 біт. Це компромісне рішення дозволяє утримувати біти
структури в межах байти або слова (щоб не ускладнювати програмування,
коли байт може містити біти різних структур) і витрачати мінімум біт як
для невеликих значень повторів, так і для великих. Фактично поля Code і
Repeat займають разом один або два байти, де старші два біти завжди
належать полю Code. Я опишу механізм одержання значення з поля Repeat, і
ви зрозумієте, як воно там зберігається.
1.
Взяти поточний байт
2.
Старші два біти належать полю Code
3.
Якщо 6-ий у байтах дорівнює 0, тоді молодші 5 байтах містять значення
4.
Інакше взяти наступний байт, який є молодшим байтом для поточного байти
5.
Молодші 13 біт отриманого слова містять значення
До
витягнутого значенням необхідно додати 1, щоб отримати реальну кількість
повторень. При повторах від 1 до 32 використовуються всього 6 біт (разом з полем
Code - один байт), а понад 32 і до 8192 - 14 біт (з полем Code - два байти).
Якщо кількість повторів перевищує 8192, тоді в одному поведінці кодується
максимально можливу кількість повторів, а в наступному поведінці - залишилася
частина повторів.
В
поле Extent зберігається величина зміни колірної площині пікселя, яка в
залежно від біта RatioType поля Properties задана або прямим значенням,
або процентним відношенням. У результаті ми отримуємо, що структура
PBCvideoIdentical може займати в байтове поданні один або два байти, а
структура PBCvideoChanged - два чи три байти.
Пряме
значення - це число, обчислена як різниця між поточним і попереднім
значеннями колірної площині пікселя. Пряме значення завжди позитивне
число і обчислюється як різниця за модулем. Потрібно зауважити, що різниця
обчислюється між крайніми точками діапазону зміни, коли значення колірної
площині пікселя закінчило збільшуватися або зменшуватися. Нижче я навів
малюнок у вигляді графіка поведінки колірної площині пікселя. Червоними
рисками виділені місця, де один код поведінки змінює інший, а в поведінці
кодується кількість кадрів повторення і різниця зміни, або тільки
кількість кадрів повторення за відсутності змін. Для наочності
світло-зеленим кольором виділені поведінки, коли колірна площину пікселя
залишається незмінною.
Процентне
ставлення - це та ж сама різниця між значеннями колірної площині
пікселі, але виражена в діапазоні від 1 до 100 відсотків. Якщо прямі значення
приводять до мінімуму втрат в кольорі, то процентні відносини в обмін на
невеликі втрати добре справляються з так званим кольоровим шумом, коли колір
пікселя нестабільний і "скаче" з мізерними змінами навколо
реального кольору.
І
останнє поле Index за способом зберігання інформації схоже з 6/14-бітним полем
Repeat. У полі Index зберігається індекс закодованого в масиві поводжень цілого
набору поводжень для даної колірної площині пікселя. Спосіб зберігання
інформації в полі Index вказує, що в масиві поводжень може бути не більше
8192 наборів поводжень. Кодування за допомогою закодованих наборів поводжень
значно збільшує ступінь стиснення, тому що багато ділянок поводжень
пікселів мають подібні моделі поведінки. Кодувальник може і не використовувати
кодування поводжень через масив поводжень, але тоді він не повинен
використовувати поведінки з кодом 11 (коли поле Code = 11) і масив поведінки залишити
порожнім. Зауважу, що структура PBCvideoEncoded в точності повторює структуру
PBCvideoIdentical, тільки замість поля Repeat використовується поле Index.
Впровадження даних в відеопотік
Щоб
ви могли впроваджувати в відеопотік власні дані, передбачений спеціальний
код. Можливо, ви хочете паралельно в відеопотоці кодувати звук або запровадити
на якихось ділянках потоку інші методи кодування. Може, вам знадобиться
впровадити в потік власні мітки, текст або ще що-небудь. Для цих цілей
використовується код на основі структури PBCvideoIdentical, де поле Repeat
містить максимальну кількість повторів. Виходить, що при поводженні
кольоровій площині пікселя, коли вона не змінюється протягом декількох
кадрів (поле Code = 00), максимально можна вказати 8191 повтор, а не 8192 як у
інших структурах. Якщо ж у структурі PBCvideoIdentical кількість повторів
одно 8192, тоді ця структура позначає спеціальний код впровадження інших
даних у відеопотік.
За
таким кодом завжди має слідувати DWord-поле розміру блоку впроваджених даних.
Декодер, прочитавши код впровадження даних (зміст PBCvideoIdentical = 3FFFh),
читає наступне DWord-поле, по якому дізнається, через скільки байт після
DWord-поля слід продовження відеопотоку. Декодер знає розмір блоку
впроваджених даних, знає адресу (або зсув) цього блоку, і може викликати
деяку спеціальну функцію, що обробляє ваші впроваджені дані. Потім
декодер на основі розміру блоку впроваджених даних визначає адреса (зміщення)
продовження даних відеопотоку.
Зверніть
увагу, що в масиві поводжень спеціальний код впровадження даних не
використовується, тому що в масив не впроваджуються ні?? акіе інші дані. Декодер
повинен просто ігнорувати цей код, якщо він якимось чином зустрінеться в
масиві поводжень.
Робота декодера
Щоб
вам було зрозуміліше, розглянемо крок за кроком роботу декодера. Не варто вважати
описані мною методи реалізації декодера і його структури істинно вірними. Я
лише прагнув простіше пояснити принцип декодування, не особливо вдаючись в питання
якості реалізації декодера. Ви самі в змозі визначити, як максимально
якісно написати його начинку. Якщо є бажання, можете завантажити вихідні коди
приклад PBC Player'а тут (205 Кбайт). Вихідні тексти написані в Delphi, а
програмний код (стиль програмування) не гарантує високу
продуктивність і безпомилковість реалізації.
Нам
знадобиться опорний кадр. Спроектуємо його структуру так, щоб зберігати в ньому
відомості не тільки для декодування першого кадру, а й кожного наступного.
Опорний кадр буде являти собою динамічний масив з даними про поведінку
всіх пікселів зображення. У кожному пікселі є по три колірних площині,
тому кількість елементів у цьому масиві буде так само ШИРИНА * ВИСОТА * 3.
Тепер опишемо масив, елементи якого будуть представлені структурою
ColorPlane. Я навмисно додав префікс "cp" до імен полів цієї
структури, щоб ви не плутали їх з подібними полями структур PBCvideoIdentical,
PBCvideoChanged і PBCvideoEncoded.
type
ColorPlane = record
cpIndex:
Word;// індекс закодованого набору поводжень
cpBehaviour:
Byte;// індекс поточного поведінки, що виконується з набору
cpCode:
Byte;// код виконуваного поведінки
cpRepeat:
Word;// кількість кадрів повторення поведінки
cpCurrent:
Double;// поточне значення колірної площині пікселя
cpExtent:
Double;// величина зміни площини за один кадр
end;
//
глобальні змінні
var
Frame:
array of ColorPlane;// опорний кадр
Відзначу,
що структура ColorPlane в такому вигляді не дозволить використовувати кодування
наборів поводжень через інші набори, коли один набір на якомусь своєму
ділянці може посилатися на матеріали, іншого набору. У наборах поводжень
допустимо використовувати поведінки з кодом 11 (закодований у масиві поводжень),
а отже, можна реалізувати високу вкладеність наборів поводжень. Це може
допомогти сильніше стискати відео. Наведу приклад, де зациклені один на одного
набори призводять до ефективного стиснення.
Припустимо,
у нас є відеофрагмент в 1000 кадрів. Нехай він складається з однієї точки. У
кожному непарній кадрі точка має чорний колір, а в кожному парному - білий. І ось
так 1000 кадрів вона постійно "моргає". У закодованому потоці
виявиться всього два елементи (набору поводжень) в масиві поводжень, причому
кожен набір поводжень буде складатися всього з двох поводжень, де друга
поведінка завжди буде посилатися на інший набір поводжень (другий поведінка
першого набору - на другий набір, друге поведінка другого набору - на першій
набір). І буде ще одне поведінку в загальному відеопотоці (потік після масиву
поводжень), яке посилається на один з наборів поводжень. Декодер, прочитавши
поведінка із загального відеопотоку, за посиланням потрапляє на один з наборів та
починає обслуговувати його поведінки. У першому поведінці набору зазначено, що
точка має білий колір один кадр, а другий поведінка набору відсилає декодер на
другий набір. У другому наборі перше поведінка вказує, що точка має
чорний колір один кадр, а другий поведінка відсилає декодер на перший набір. І
так в циклі декодер отрісовиваєт 1000 кадрів відеофрагменту, більше нічого не
читаючи з відеопотоку.
Приклад
не зовсім вдалий, хоча пояснює суть організації вкладеності наборів
поводжень. Але ж вкладеність може бути і з поверненням, коли один набір
посилається на інший набір, але за своєю посиланням містить ще продовження
поводжень (посилання всередині набору, або кілька посилань в наборі). Ось це і не
дозволить використовувати вказане вміст структури ColorPlane, тому що в ній
не передбачено контроль вкладеності наборів. А тепер повернемося до роботи
декодера, і пізніше поясню, чому поля cpCurrent і cpExtent в структурі
ColorPlane задані типами з плаваючою точкою.
Першим
справою декодер читає заголовок відеопотоку. Отримавши ширину і висоту кадру
відеофільму (поля Width і Height структури PBCvideoHeader), декодер
встановлює розмір масиву опорного кадру за формулою Width * Height * 3.
Значення полів StartRCr, StartGY і StartBCb заносяться до поля cpCurrent
відповідних елементів масиву опорного кадру. Декодеру потрібно відразу
заповнити колірні площині опорного кадру відповідними початковими
значеннями. Перші три елементи масиву належать першому пікселю (його
координати = 0,0), наступні три елементи - другий пікселю (0,1), наступні --
третій, і так далі. Тому в поле cpCurrent першого елемента масиву
заноситься значення поля StartRCr, у другий елемент масиву - значення поля
StartGY, в третій елемент - значення поля StartBCb, в четвертий елемент - знову
поле StartRCr, п'ятого - поле StartGY, і так далі. Всі інші поля елементів
масиву обнуляються. Зауважу, що поле cpIndex обнуляється значенням 0FFFFh.
Декодер використовує це поле, щоб з'ясувати, чи обслуговується в даний
момент для даної колірної площині пікселя поведінку з відеопотоку або воно
береться з масиву поводжень. Індекс набору поводжень може лежати тільки в
межах від 0 до 8191 (всього виходить 8192 набору поводжень), а значення
0FFFFh знаходиться за межами масиву, тому декодер легко визначає, що
поточне поводження взято не з масиву поводжень, а прямо з відеопотоку. Для
наочності наведу фрагмент програми.
//
глобальні змінні
var
Header:
PBCvideoHeader;// заголовок відеопотоку
Behaviours: PBCvideoBehaviours;// масив поводжень
Frame: array of ColorPlane;// опорний кадр
FrameNum: DWord;// номер поточного кадру
procedure InitFrame;
var
W: Word;// ширина
H:
Word;// висота
I:
DWord;// індекс площини в масиві опорного кадру
begin
//
читаємо заголовок відеопотоку з деякого файлу
BlockRead (F1, Header, SizeOf (Header));
//
встановлюємо розмір масиву опорного кадру
I
: = Header.Width * Header.Height * 3;
SetLength (Frame,
I);
//
спочатку обнулив інші поля елементів масиву опорного кадру
//
(поле cpIndex Обнуляємо значенням 0FFFFh)
repeat
Dec (I);
Frame [I]. cpIndex: = $ FFFF;
Frame [I]. cpBehaviour: = 0;
Frame [I]. cpCode: = 0;
Frame [I]. cpRepeat: = 0;
Frame [I]. cpExtent: = 0;
until I = 0;
// тепер занесемо значення полів StartRCr, StartGY і StartBCb
//
у відповідні кольорові площині опорного кадру
for H: = 1 to Header.Height do begin
for W: = 1 to Header.Width do begin
//
обчислюємо у змінній I індекс елемента масиву
//
опорного кадру, з якого розташовані підряд
//
три колірних площині пікселя з координатами W і H
// (де W = X, H = Y)
I: = (H-1) * Header.Width * 3 +
(W-1) * 3;
//
а тепер заносимо в три площини пікселя
//
початкові колірні значення
Frame [I]. cpCurrent
: = Header.StartRCr;
Frame [I 1]. cpCurrent: =
Header.StartGY;
Frame [I 2]. cpCurrent: =
Header.StartBCb;
end;
end;
//
читаємо масив поводжень з файлу в змінну Behaviours
ReadBehavioursData (F1,
Behaviours);
//
скидаємо внутрішній лічильник декодувати кадрів,
//
а по ньому будемо визначати, що відеопотік закінчився
FrameNum
: = 0;
end;
За
декодер заголовком повинен прочитати з відеопотоку масив поводжень. Це
звичайний масив і декодер повинен "скласти" його де-небудь у себе в
пам'яті, щоб мати до нього швидкий доступ в разі кодування поведінки
кольоровій площині пікселя набором поводжень з масиву. Наприкінці наведеного
фрагмента коду зазначений виклик нібито вже написаної процедури ReadBehavioursData,
яка завантажує масив поводжень з файлу в змінну з ім'ям Behaviours.
Ця змінна містить в собі кількість елементів у масиві (полі ItemCount)
і масив Behaviours з елементами, що представляють собою набори поводжень. У
кожного набору є поле Count (кількість поводжень в наборі) і поле Behaviour
з набором цих поводжень. Відзначу, що в наборі поводжень завжди є хоча б
одне поведінку, тому полі Count зі значення 0 означає одне поведінку, з
значенням 1 - два поведінки, і так далі до 255, що позначає 256 поводжень.
За
масивом поводжень йде набір відомостей про поведінку конкретних колірних
площин пікселів зображення - загальний потік відео. Декодер витягує ці
відомості, спираючись на дані елементів масиву опорного кадру. Якщо в деякому
елементі масиву поле cpIndex одно 0FFFFh (поведінка колірної площині
пікселя було взято прямо з відеопотоку) і поле cpRepeat дорівнює нулю (повтори
поведінки закінчилися), значить, зараз в відеопотоці знаходяться дані про
наступному поведінці поточної колірної площині пікселя, і ці дані потрібно
витягти і занести в поточний елемент масиву. Якщо ж це не так, і поле
cpRepeat не дорівнює нулю (ще залишилися повтори поведінки), тоді потрібно в поточному
елементі масиву зменшити на 1 поле cpRepeat і, залежно від поля cpCode
(00, 01 або 10), або залишити без зміни, або збільшити або зменшити поле
cpCurrent на величину поля cpExtent.
Образно
кажучи, декодування кожного кадру починається з того, що декодер проходить
послідовно всі елементи масиву опорного кадру - від першого до останнього
елемента (фактично проходить по всіх колірних площин пікселів відеокадру).
Якщо в полі cpRepeat залишилися повтори, тоді зменшити поле cpRepeat на 1, а до
полю cpCurrent додати чи відняти (в залежності від значення поля cpCode)
значення поля cpExtent. Нове значення поля cpCurrent і буде тим, що
заноситься у відповідну колірну площину пікселя реального кадру на
екрані. Але перед цим значення поля повинно бути ще оброблено, про що буде
розказано нижче.
//
глобальні змінні
var
Header:
PBCvideoHeader;// заголовок відеопотоку
Behaviours: PBCvideoBehaviours;// масив поводжень
Frame: array of ColorPlane;// опорний кадр
procedure
CreateNextFrame;
var
I:
DWord;// індекс площини в масиві опорного кадру
L:
DWord;// кількість елементів у масиві опорного кадру
C:
Byte;// код щойно прочитаного поведінки
R:
Word;// кількість повторів поведінки
E:
Byte;// величина зміни площині за весь період поведінки
begin
L: = Length (Frame);
I: = 0;
while
I
//
якщо ще залишилися повтори для поточної колірної площині,
//
тоді обчислити значення колірної площині для
// поточного кадру
if Frame [I]. cpRepeat 0 then
begin
Dec (Frame [I]. cpRepeat);
//
при поводженні 00 колірна площину не змінюється,
//
тому в структурі CASE не використовується перевірка на 00,
//
а код 11 завжди замінюється реальною поведінкою з набору поводжень,
//
тому його перевірка теж не потрібна
case Frame [I]. cpCode of
01: Frame [I]. cpCurrent: =
Frame [I]. CpCurrent + Frame [I]. CpExtent;
10: Frame [I]. cpCurrent: =
Frame [I]. CpCurrent - Frame [I]. CpExtent;
end;
end
else begin
//
цей фрагмент дивіться нижче, де розглядається, що відбувається,
//
якщо в полі cpRepeat не залишилося повторів
end;
Inc (I);
end;
end;
Коли
ж у полі cpRepeat не залишилося повторів, декодер повинен проаналізувати поле
cpIndex. Якщо там не вказаний індекс обслуговується набору поводжень колірної
площині пікселя (cpIndex = 0FFFFh), тоді потрібно взяти наступне поведінка
прямо з відеопотоку і занести його дані в поточний елемент масиву опорного
кадру. Як вже було сказано раніше, декодер повинен вміти обслуговувати спеціальний
код впровадження інших даних у відео, і продовжувати декодування відео
після впровадженого блоку даних. Зауважте, що в елементах опорного кадру
зберігаються коди реальних поводжень, щоб знати, що насправді
відбувається з колірною площиною пікселя. Тому при зустрічі коду
"закодований у масиві поводжень" (cpCode = 11), декодер повинен
витягти перший поведінка із заданого набору і використовувати код цього
поведінки. Описаний мною фрагмент коду підтримує безповоротну вкладеність
наборів поводжень, але з поворотною не впорається.
Отже,
Допишемо відсутній фрагмент процедури CreateNextFrame. Для простоти вважаємо,
що у нас вже написана процедура ReadBehaviour, що читає з потоку одне
поведінка по описаним вище правилам (дивіться опис вмісту структур
PBCvideoIdentical, PBCvideoChanged і PBCvideoEncoded). Також вважаємо, що у нас
вже є процедура читання N-го поведінки із заданого набору в масиві
поводжень - GetBehaviour.
if Frame [I]. cpIndex = $ FFFF then
begin
//
читаємо з відеопотоку поведінка для поточної
//
кольоровій площині пікселя
//
в змінну C повертається код поведінки
//
в R - кількість повторів поведінки або індекс,
//
якщо поведінка задано в масиві поводжень
//
(у цьому випадку змінна C = 11)
//
в E - величина зміни площині за весь період поведінки
//
або 0, якщо C = 00 або C = 11
ReadBehaviour (C,
R, E);
//
за допомогою циклу робимо обслуговування можливих
//
впроваджених у відеопотік блоків даних
while
(C = 00) and (R = 8192) do begin
//
тут повинен бути виклик вашій функції обробки
//
запровадженого в відеопотік блоку даних
//
а потім продовжуємо читати з потоку поведінка
//
для поточної колірної площині пікселя
ReadBehaviour (C,
R, E);
end;
//
Якщо поведінка закодовано в масиві набором поводжень,
//
тоді необхідно прочитати перший поведінку з набору
//
і використовувати його дані, так як в опорному кадрі
//
використовуються тільки коди реальних поводжень.
//
Наступним циклом забезпечується вибір першого поведінки
//
при кодуванні за допомогою набору, а також він забезпечує
//
підтримку безвозратной вкладеності наборів поводжень.
while C = 11 do begin
Frame [I]. cpIndex: = R;
Frame [I]. cpBehaviour: = 0;
// читаємо поведінку з індексом Frame [I]. cpBehaviour = 0
//
з набору поводжень з індексом Frame [I]. cpIndex,
//
а результат читання повертається в змінні C, R і E
GetBehaviour (Frame [I]. cpIndex,
Frame [I]. CpBehaviour, C, R, E);
end;
//
у полі cpExtent заноситься величина зміни колірної
//
площині за один кадр повтору, а не за весь його період
Frame [I]. cpCode: = C;
Frame [I]. cpRepeat: = R;
Frame [I]. cpExtent: = E/R;
//
а тепер нам залишилося обчислити поле cpCurrent для прочитаного
// поведінки
Dec (Frame [I]. cpRepeat);
case Frame [I]. cpCode of
01: Frame [I]. cpCurrent: =
Frame [I]. CpCurrent + Frame [I]. CpExtent;
10: Frame [I]. cpCurrent: =
Frame [I]. CpCurrent - Frame [I]. CpExtent;
end;
end
else begin
//
цей фрагмент наведено нижче і описує, що відбувається,
//
коли поле cpIndex містить індекс обслуговується набору поводжень
end;
Тепер
настав час пояснити, чому поля cpCurrent і cpExtent задані типами з
плаваючою точкою. Справа в тому, що в полі cpExtent елемента масиву опорного
кадру зберігається величина зміни колірної площині за один кадр повтору, а не
за весь його період. Коли величина зміни за весь період ділиться на
кількість повторів, залишаються дробові частини. Відкидати дробові частини не можна,
тому що динаміка зміни колірної площині може бути різна. З кадру в
кадр поле cpCurrent змінюється на величину поля cpExtent. Уявіть, що за
100 кадрів колірна площину пікселя змінилася всього на 1 відсоток. Розділивши 1
на 100 кадрів і округливши результат, ми отримаємо 0. У результаті точка на
Протягом 100 кадрів не зміниться на 1 відсоток, адже ми будемо додавати до поля
cpCurrent нульове значення поля cpExtent. А от якщо ми будемо додавати з
дробовими частинами, крапка за 100 кадрів плавно досягне зміни в 1 відсоток.
Округлення до цілого числа виконується тільки в момент виведення колірних
площин пікселя у реальний кадр на екрані, але всередині опорного кадру все
обчислення робляться виключно з дрібними частинами.
І
знову повернемося до програмного коду декодера. Нам залишилося розглянути частина
коду, коли в полі cpRepeat не залишилося повторів, а в полі cpIndex вказано
індекс обслуговується набору поводжень колірної площині. У цьому випадку потрібно
взяти наступне поведінка з обслуговується набору та занести його дані в
поточний елемент масиву опорного кадру. Якщо ж у наборі пройдено всі поведінки
(виконане поведінка була останнім у наборі), тоді потрібно взяти наступне
поведінка прямо з відеопотоку і вже його дані занести в поточний елемент
масиву опорного кадру. Ще раз згадаємо, що при читанні з відеопотоку декодер
повинен вміти обслуговувати спеціальний код впровадження інших даних у відеопотік.
//
обчислюємо індекс наступного поведінки в наборі
Inc (Frame [I]. cpBehaviour);
//
якщо в наборі ще не закінчилися поведінки, тоді
//
читаємо наступне поведінка з набору, інакше
//
скидаємо cpIndex в 0FFFFh і читаємо поведінка із загального відеопотоку
if (Frame [I]. cpBehaviour 0)
and
(Frame [I]. cpBehaviour = Header.FrameCount
then Halt;
end;
Якщо
з наведеного коду прибрати всі коментарі, можна помітити, що програмний
код декодера невеликий. До того ж алгоритм декодування виявляється простим і
швидким. До речі, програмний код декодера можна оптимізувати ще в більш
компактний, так як перестановкою перевірки поля cpIndex спочатку на реальний
індекс (а не на 0FFFFh) можна домогтися виключення однакових фрагментів коду, які читають
поведінка із загального відеопо?? ока або набору поводжень з масиву поводжень. Але
це вже ви самі вирішуйте, як вам буде зручніше.
За рахунок чого відбувається стиснення
В
Як приклад я взяв з фільму "Шостий день" поведінка червоної
кольорової площини довільного пікселя в центральній частині кадру. Всього взято
100 кадрів, що дорівнює 4 секундам фільму при швидкості 25 кадрів за секунду.
Спеціально вибрав фрагмент фільму, де розвивається динамічний дію. Через
кадр швидко проїжджає машина, а за нею з'являється нова сцена з вертольотом. А
тепер подивимося, як вела себе колірна площина R протягом 100 кадрів.
185,
193, 194, 194, 192, 197, 197, 207, 207, 204, 204, 201, 201, 197, 200, 197, 208,
210, 208, 206, 209, 209, 216, 216, 216, 215, 214, 214, 214, 214, 214, 214, 217,
217, 216, 216, 215, 216, 079, 030, 028, 009, 047, 021, 008, 017, 060, 025, 024,
018, 013, 015, 015, 017, 017, 017, 017, 017, 017, 016, 016, 016, 012, 011, 015,
015, 015, 014, 005, 006, 008, 008, 008, 008, 008, 004, 011, 012, 012, 012, 012,
012, 012, 012, 012, 012, 012, 012, 012, 012, 007, 007, 006, 053, 054, 058, 053,
052, 050, 047
Тут
вказані безпосередні значення червоній кольоровій площині пікселя для
кожного з 100 витягнутих кадрів. Значення кольорової площини завжди лежить в
межах одного байта, а значить, змінюється лише від 0 до 255. Як ви можете
помітити, в малих значеннях додані провідні нулі. Я зробив це для того,
щоб вирівняти значення для їх зручного перегляду при будь-якому розмірі текстового
вікна.
Можна
відразу зауважити, що в наборі байт зустрічається дуже мало суміжних повторень
одного і того ж стану колірної площині, щоб кодувати цей фрагмент
будь-яким аналогом RLE-алгоритму. Але ж ми розглядаємо фрагмент 100 представлених
байт як остаточний і готовий до стиснення, тому не знаходимо, що цей набір
байт придатний для ефективного RLE-стиснення. Кодувальник ж не цікавий сам
набір байт, оскільки йому важлива тільки різниця між кожними суміжними байтами.
І тепер подивіться, як за допомогою різниць набір байт починає перетворюватися на
ефективний для RLE-алгоритму блок. Потрібно відзначити, що кодіровщік завжди бере
різницю за модулем між кожними суміжними байтами.
000,
008, 001, 000, 002, 005, 000, 010, 000, 003, 000, 003, 000, 004, 003, 003, 011,
002, 002, 002, 003, 000, 007, 000, 000, 001, 001, 000, 000, 000, 000, 000, 003,
000, 001, 000, 001, 001, 137, 049, 002, 019, 038, 026, 013, 009, 043, 035, 001,
006, 005, 002, 000, 002, 000, 000, 000, 000, 000, 001, 000, 000, 004, 001, 004,
000, 000, 001, 009, 001, 002, 000, 000, 000, 000, 004, 007, 001, 000, 000, 000,
000, 000, 000, 000, 000, 000, 000, 000, 000, 005, 000, 001, 047, 001, 004, 005,
001, 002, 003
що вийшов,
набір складається з 100 різниць і виглядає вже легше для візуального сприйняття.
Хоча ще нічого особливого не сталося. Той же самий набір байт, але виражений
через різниці між суміжними байтами. Зауважте, у ньому стало ще менше
повторюваних суміжних та однакових за значенням байт. Тому для RLE-алгоритму
новий набір байтів ще не ефективний, хіба що вміст його байт займає в
бітове поданні набагато менше місця.
Зверніть
увагу, що в першому кадрі першого набору знаходилося значення 185, а в наборі
різниць знаходиться різниця 0. У цей момент передбачалося, що ми кодуємо 100
кадрів не з середини фільму, а як ніби вони у нас будуть початком окремого
закодованого фрагмента. Припустимо, червона колірна площину опорного кадру
була заповнена значенням 185, п
