Алгоритм стиснення відео: рецептори як кодувальники

Дмитро Сахань

З моменту опублікування алгоритму стиснення відео Pixel Behaviour Check пройшло вже більше півроку (станом на січень 2003 року). Спочатку я навіть написав де-не-який код для декодера цього формату. Але незабаром проблеми штучного інтелекту поглинули мою увагу повністю. Життя закрутилася, примушуючи вирішувати зовсім інші питання, і повела в сторону від відеосжатія. На жаль, щоб довести ідею до працюючого комерційного продукту, потрібно приділити їй дуже багато часу. На цей час уже не вистачало, а ідея залишилася чекати кращих часів.

Тоді я якось випустив з уваги, що треба було зробити доступними мої исходники декодера. По собі знаю: бажання попрацювати з будь-якою ідеєю вбиває необхідність писати пробну програму, без якої неможливо перевірити ідею на ділі. Як правило, доводиться витратити багато часу на написання взаємодії блоків програми, перш ніж справа дійде до перевірки самої ідеї. Тому я викладаю исходники декодера. Чи можете завантажити їх тут у вигляді RAR-архіву (205,5 Кбайт). Исходники нормально задокументовані, так що не складе великих труднощів у них розібратися. У вихідні коди не ставилася як така мета: написати оптимальний за швидкодією код. Як ви виверне код декодера, що з цього вийде -- це вже ваш особистий питання. Подальший же розмова про це алгоритмі піде зовсім в іншому ракурсі.

Занурюючись в безодню штучного розуму, я все більше дивувався тим обставинам, що роботі живого організму взагалі чужі ті принципи, якими ми керуємося в комп'ютерному світі. Намагаючись знайти сполучні нитки між незвичайним пристроєм частин живого організму та їх функціями, мені вдалося зробити дуже незвичайну знахідку. Ось про неї як раз і піде мова, тому що вона дозволяє по-іншому поглянути на стиснення відео. Кого цікавить більш детальна інформація про це, читайте статтю ось тут, правда, зі зрозумілих причин, там більше ухил у сторону штучного інтелекту, ніж у бік стиснення відео. А ми повертаємося до нашої теми.

Незвичайне рішення звичайної проблеми

Для Спершу хочу коротко ознайомити вас із суттю вищезгаданої статті. Під час розглядування зображення наші очі здійснюють мікрорухи, не помітні ні сторонньому спостерігачеві, ні нам особисто. У середньому частота таких рухів - близько 100 разів на секунду. Величина зміщення зображення по сітківці ока під час мікрорухи мізерно мала - в межах 1-2 сусідніх рецепторів. Тобто видиме зображення як би тремтить на сітківці в межах сусідніх пікселів (рецепторів). Всі ці мікрорухи забезпечують утримання на рецепторах сітківки контурів всіх об'єктів у видимому зображенні. Причому рецептори дуже вдало перетворюють зображення, і в мозок поступає вже закодоване відео.

Якщо ви цікавилися особливістю сучасних алгоритмів кодування відео, то могли звернути увагу, що MPEG і йому подібні модифікації намагаються виділити контури рухаються об'єктів в сцені, щоб закодувати тільки їх і тим самим знизити обсяг відеопотоку. Взагалі в історії стискаючих алгоритмів простежується изживание математичних методів стиснення. Поступово математичні алгоритми досягли тієї межі, після якого блок даних не можна більше стиснути, не втративши інформації. На зміну їм з'явилися JPEG і MPEG. Тут вже стиск досягалося за рахунок втрат надлишкової інформації. В остаточному підсумку в MPEG додалася ще й компенсація руху, коли відслідковуються контури зміщається об'єктів, щоб в наступному кадрі пересунути об'єкти в нове положення без повторного кодування їх вмісту (яке всередині їх контурів). Але біда MPEG полягала в тому, що контури відстежувалися у вигляді цілих блоків (квадратиків), бо відслідковувати реальні контури надто складно. Мабуть, ви бачили, як при невпевненого прийому кабельного каналу на екрані телевізора зображення починає виводитися скачуть квадратиками.

Над проблемою виділення контурів працювало багато фахівців. Десь близько півроку тому в Інтернеті з'явилося повідомлення, що фахівці однієї американської компанії розробили більш якісний алгоритм стиснення, заснований на досить просунутою математики виділення контурів. Як тоді заявлялося, контури виділяються дуже близько до реальних, так що в нового алгоритму немає особливих проблем з квадратиками. Але серйозна математика, природно, вимагає серйозної продуктивності комп'ютера.

І от коли порівнювати все це з принципами пристрої живого організму, виявляється, що досить лише слідувати цим принципам і ніякої складної математики не потрібно взагалі. Імітуємо мікрорухи очі, і ось отримали контурне зображення.

Кумедне виходить зображення. Це не негатив, хоча дуже схоже. Можна помітити, як контури об'єктів (пелюстки, маточка) пофарбовані різними кольорами, а всередині контурів знаходиться чорний колір. Ось за таким зображення можна відновити все, що було в оригіналі, включаючи тональну забарвлення об'єктів. Для цього лише потрібно знати, в який бік імітувалося мікрорухи очі.

А ось на цьому зображенні подивіться на колір неба за статуєю. Він не однорідний, а переходить від світлого тону у плечей статуї в темний тон над її головою. На контурному зображенні ви не помітите в цих місцях ніяких тональних переходів, хоча вони там є. Зрозуміло, на темному тлі легко прийняти слабкий перехід за його повна відсутність. Надалі я поясню, що мав на увазі, кажучи: "не помітите в цих місцях ніяких тунельних переходів".

Будь-який націлений на видалення надлишкової інформації алгоритм іноді змушений видаляти важливу інформацію. Питання тільки в тому, наскільки сильні втрати. Обов'язково є місця, де алгоритм справляється вдало, і є місця, де відбуваються великі втрати. Дуже проблематично знайти прийнятне рішення. Наприклад, візьмемо той же приклад з кольором неба за статуєю. При зменшенні обсягу відеопотоку MPEG-алгоритм починає зрізати частотний діапазон тунельних переходів неба, в внаслідок чого небо імітується викладеними поруч квадратиками з близькими квітами.

Викинути максимум, нічого не викидаючи

Якщо ми подивимося на рішення природи, яке вона реалізувала в рецепторах сітківки очі, то взагалі не побачимо жодного видалення інформації. У контурному зображенні статуї дійсно немає ніякого тонального переходу неба, тому що перехід у такому зображенні закодований, і просто так розглядати його не вдасться. Поясню це на прикладі. Припустимо, у нас є зображення з зростаючим кольором.

Візьмемо з зображення одну горизонтальну лінію. У ній 256 зелених пікселів. Байтові значення пікселів розрізняються на 1. Самий лівий піксель має значення 0, самий правий - 255. У підсумку маємо 256 зростаючих за значеннями байт.

Так от після мікрорухи очі і наступного перетворення цієї лінії рецепторами сітківки, лінія перетвориться на набір 256 байт з одних одиниць (або -1, Якщо мікрорухи очі було в інший бік). Тобто з лінії зникне наочний для нас тональний перехід. А відбувається це тому, що рецептори тримають на своїх виходах різницю між попереднім і знову баченим зображенням. В око потрапляє зображення лінії, потім відбувається мікрорухи, тепер в око потрапляє зміщена лінія, і тільки після цього рецептори видають в мозок інформацію. І кожен рецептор сигналізує про те, що його "піксель" відрізняється на 1 за значенням від поруч стоїть "пікселя".

Як можна здогадатися, лінія з зростаючого зеленого кольору перетворилася в лінію з суцільним кольором зі значенням 1. І тільки знаючи про мікрорухи, можна сказати, що ця суцільна лінія позначає лінію із зростаючим кольором. За цим же причин у контурному зображенні статуї ми не побачимо ніяких тональних переходів неба, а лише одні одинички (двійки, трійки чи наскільки там сильно змінювався перехід). Чорний фон зображення, що нагадує про негатив, на самому справі означає, що в цих місцях знаходиться колір, що належить деякому об'єкту в сцені. Колір об'єкту закодований різницею тонального переходу в контурі об'єкта. До речі, не варто забувати, що в об'єкта може бути безліч внутрішніх подоб'ектов, що мають свої контури.

Нова послідовність операцій

Тепер повернемося до MPEG-алгоритму. Всі його видалення надлишкової інформації зводиться до того, щоб привести блок (квадратик) зображення до максимального змісту однакових за значенням байт. Звичайно, 256 нулів, одиничок, двійок або трійок стиснути найпростіше. На цьому засновані всі алгоритми стиснення відео, тільки кожен з них прокладає свій шлях, щоб перетворити блок даних в набір однакових байт. Ясна річ, не кожен шлях приводить до гарних результатів.

В зв'язку з цим робота алгоритмів стиснення відео наступного покоління, як мені здається, має виглядати наступним чином. Спочатку кадр зображення перетвориться ось таким "рецепторним" чином. Це відразу знімає надлишкову інформацію (подивіться на розміри і кількість чорних областей у контурних зображеннях). Істотний плюс - зняття надлишкової інформації взагалі не означає її втрату. Природа не дарма придумувала настільки витончені та не завжди зрозумілі "фокуси" з живими організмами. Чому ж нам не скористатися її принципами. Другий плюс - "рецепторні" перетворення настільки просто реалізується, що імітація рецепторного поля не представляє складнощів на програмному рівні.

Але є і свій мінус. А він полягає в тому, що нам зараз відома тільки маленька знахідка з рецепторами. Усього лише крапля в морі секретів природи. Можливо, незабаром ми зможемо проникнути в її секрети глибше (мається на увазі спосіб обробки відеоряду), але поки інші перетворення доведеться виконувати стандартними математичними засобами. Тому за "рецепторним" перетворенням найімовірніше повинні виконуватися самі звичайні операції з вже відомих алгоритмів стиснення. У принципі, очищене від надлишкової інформації зображення можна ще раз "очистити" вже операціями MPEG-стиснення, хоча, на мою думку, це вже зайве. Якщо вже вдалося позбутися від надлишку, не втративши при цьому інформацію, тоді навіщо втрачати її далі. Зате компенсація руху з MPEG підійде сюди якраз до речі. Правда, її б трохи модифікувати, щоб вже чітко виділені контури об'єктів не зіпсувати.

Що стосується алгоритму Pixel Behaviour Check

Далі розмова піде для тих, хто захоче повозитися з доведенням ідеї. У мене зовсім немає часу займатися і питаннями штучного розуму, і алгоритмом стиснення. "Рецепторні" перетворення відкриває нові можливості в стисненні, тому його просто необхідно використовувати в PBC-алгоритмі. Основна фішка алгоритму - стиснення за рахунок контролю поведінки пікселів відеокадрів. Напрямок контролю - вздовж кадрів, а не вздовж ліній одиночного кадру, як у звичайних алгоритмах. Думаю, така думка вже давно обговорювалася, просто ніхто не пропонував більш-менш підходяще її втілення. Загалом-то, компенсація руху з MPEG трохи схожа по суті, але там ведеться спостереження за рухомими об'єктами. Тут же контролюється поведінка кожного пікселя кадру, не звертаючи уваги на рухаються об'єкти. Цілком реально об'єднати компенсацію руху з контролем поведінки решти пікселів.

Звичайно, структури даних в алгоритмі може бути доведеться трохи підправити. По-перше, в числі перших кроків має йти "рецепторні" перетворення відеокадру. З цих причин можуть відпасти через непотрібність YCbCr-перетворення та перекладів в процентні відносини, хоча структури спроектовані так, що до них можна просто "наростити" нове перетворення, взагалі не чіпаючи структури.

По-друге, коди поводжень пікселів можна перебудувати так, щоб стало можливим кодувати поведінка пікселів не тільки через масив поводжень, але і за допомогою додаткових алгоритмів. Якщо підключати ще й компенсацію рухів, тоді для неї також виділяється окремий код. При бажанні коди поводжень можна перебудувати, не вдаючись до зміни структур даних. Наприклад, в моїх початкових кодах декодера ви можете подивитися, як я виділив певні коди для перезавантаження масиву поводжень, для титрів і тому подібного. Ви можете вчинити точно таким же чином. Ну, тут не мені вас вчити.

По-третє, в декодері потрібно буде написати зовсім інше "рецепторні" перетворення. Воно не складне, головне - наперед знати, в який бік виконувалася імітація мікрорухи очі. Дуже навіть можливо, щоб напрям мікрорухи могло мінятися по ходу кодування відео. Але це вже зокрема.

Відносно исходников декодера можу сказати, що я використовував найпростіший варіант читання байт з відеофайлу. З цієї причини швидкість витягання інформації з відеопотоку невисока. Краще всього створити буфер в пам'яті, куди спочатку читається великий блок файлу, потім витягуючи байти безпосередньо з пам'яті. У міру спустошення буфера виконується підвантаження блоків файлу в пам'ять. Для цього в исходники доведеться переписати процедуру читання з файлу.

Коли я експериментував з декодером, то помітив, що сам алгоритм декодування дуже простий і не вимагає серйозної продуктивності, хоча спочатку мені здавалося, що алгоритм сильно навантажить процесор. Оперувати многопіксельним відеопотоків при декодуванні виявилося справою нескладним. Зовсім інша справа було при кодуванні. Я накидав каркас кодувальника на швидку руку (відразу попереджу: исходники кодувальника у зв'язку з великим періодом часу зберігання були втрачені, так що робочі вихідні коди, на жаль, немає можливості надати). Через це він кодувати відео просто з черепашачою швидкістю, до того ж з нього як з дірявої бочки почали сипатися помилки. А потім життя закружляв: проблеми, питання, рішення і так далі. І кодіровщік випав з мого поля зору, так і залишившись недопрацьованим.

Сподіваюся, ви будете більш щасливі. А зі свого боку мені залишається тільки побажати вам удачі і достатнього часу.

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

Для підготовки даної роботи були використані матеріали з сайту http://www.sciteclibrary.ru