Архаичные алгоритмы сжатия видео эпохи FMV-игр
Но была и проблема: типичное игровое разрешение того времени — 320 на 200 точек при палитре из 256 цветов, что даёт нам 64 килобайта на кадр или полтора мегабайта на 25 кадров, при скорости чтения с компакт диска в 150 килобайт в секунду. Т.е. видео надо было жать и жать довольно сильно, а сжав, потом надо суметь декодировать, ведь мы помним, компы были слабенькие и декодирование, например, MPEG им было вообще не по силам. Тем не менее производители видео игр успешно решили проблему недостаточной производительности породив заодно множество видео-кодеков и игровых видео-форматов, некоторые из которых могли проигрываться аж 286-м (прописью: двести восемьдесят шестым) процессором.
Так началась эпоха FMV игр (Full Motion Video Games). Я думаю, многие помнят её ярких представителей: Crime Patrol от American Laser Games, Lost Eden, Cyberia, Novastorm и даже Command & Conquer, в который многие играли только ради видеовставок между миссиями. В те времена выглядело это очень круто. Вау! Вау! Ну, а мне было интересно, как же они закодировали это видео, в книжках о мультимедиа приводили то же описание проблемы, что и я выше, но ничего внятного о методах сжатия не писали, видимо, авторы в этом мало понимали и пересказывали какие-то сомнительные слухи.
На самом деле, всё оказалось очень просто, методов было всего три штуки и все очень простые.
Но перед тем как мы перейдём к самим методам, были ещё повсеместно использовавшиеся ухищрения. Во-первых, конечно, ни о каких 25 кадрах в секунду не могло быть и речи. Все поголовно резали fps, вплоть до 10 кадров в секунду (интерактивные тиры Americal Laser Games). 12, 14, 15 fps — типичные фрэйм рэйты. Во-вторых, конечно же, разрешение картинки резали почти всегда, ведь если с каждой стороны от кадра отрезать по 10 пикселей (по 3%), то это даст ~15% выигрыша. Ну, а если разрешение понизить до 256 на 144 точек, как это сделали разработчики Novastorm, то выигрыш составит практически половину.
И так, смотрите, если взять 256 на 144 точи и 14 кадров в секунду, то это даст нам пол мегабайта несжатого видео вместо полутoра мегабайт, что обнадеживает.
1. Грубая сила и невежество (RLE, LZ)
Был такой формат BFI, что расшифровывалось разработчиками как «Brute Force & Ignorance». К этой группе относятся различные облегченные вариации по мотивам RLE и LZ алгоритмов. Это может показаться удивительным, но зачастую этого было достаточно, ну, а если например в динамичной сцене сжатия не хватало, то всегда можно начать пропускать кадры, или же ещё сильнее понизить разрешение картинки в два, а то и в четыре раза (MM). Видео в тирах American Lazer Games, играх серии Wing Commander, игре Lost Eden и других играх студии Cryo закодированы именно так.
Обратите внимание на характерные для Lossy RLE горизонтальные полосы.
2. Векторное квантование (VQ)
Идея простая: возьмем скажем восемь идущих друг за другом кадров и нарежем их все на блоки по 4×2 пикселя, при разрешении картинки в 320 на 156 пикслей это даст нам 50 тысяч 24-х мерных векторов (8 пикселей в блоке, три цветовых компонента у каждого пикселя). Идущие друг за другом кадры весьма вероятно имеют много общего, поэтому среди этих векторов окажется множество близких друг к другу. Далее делим эти вектора на 4096 групп, для каждой группы вычисляем центроид. Из центроидов формируем codebook, ну, а кадры записываем в файл в виде цепочек 12-и битных ссылок на codebook. Вместе это нам даёт примерно 13 килобайт на кадр, что в принципе по силам для двухскоростного сидирома.
Примерно такой подход использовался в ранних играх серии Command & Conquer.
Декодирование, очевидно, очень быстрое и дешёвое, но вот качественно закодировать видео данным методом очень непросто. Не у всех, кто использовал VQ, это получилось хорошо. Вот полюбуйтесь на скриншоты игры Creature Shock.
3. Block Truncation Coding (BTC)
Тут опять всё просто, ничего сложного в 90-х не применяли. Чтобы сохранить 256-и цветное изображение нам надо по байту на каждый пиксель. А давайте уменьшим количество цветов, допустим, до двух, теперь на пиксель нужно по биту, мы получили восьмикратное сжатие и картинку кошмарного качества. Что можно с этим сделать? Просто применим данный подход не ко всему изображению целиком, а к небольшим блокам, ведь с большой вероятностью все цвета в рамках достаточно маленького блока близки друг другу. Режем картинку на блоки, скажем, 4 на 4 пикселя и для каждого из них сохраняем два цвета (его персональную палитру) и ещё 16 бит ссылок на эти цвета. Всего 4 байта на блок из 16-и пикселей, т.е. получили 4-х кратное сжатие. Но если вдруг окажется, что двух цветов для данного блока мало, то мы можем сохранить и четыре цвета — это даст нам двукратное сжатие. А можно разделить блок на 4 блока меньшего размера и для каждого из них вычислить по два цвета.
Этот метод был очень популярен, он прост и быстр в кодировании и декодировании, обеспечивает разумное качество, легко реализуем. В игре Novastorm используются блоки 8 на 8, которые могут иметь палитру из 2, 4, 8 цветов. В известной игре Z тоже используется нарезка на блоки по 8 на 8 пикселей и деление их на части при необходимости (JV). В Cyberia — комбинированный подход: используется как деление на меньшие блоки так и палитры разного размера (C93, M95).
Оригинальный BTC, про который можно прочитать в википедии, разработан для сжатия полутоновых изображений, цвета вычисляются таким образом чтоб сохранить среднее, и стандартное отклонение яркости в блоке. Должен заметить, что такой подход даст результаты ужасающего качества. Правильная палитра должна минимизировать сумму квадратов отклонений — вот тогда получается красиво.
Конечно, все использовали межкадровое сжатие в самом его примитивном виде зачастую даже без предсказания движения. Ни о какой коррекции яркости в палитризованых видео не могло быть и речи, поэтому на сценах с затемнением визуально падала частота кадров. Это очень было заметно в роликах самой первой Need For Speed, а я-то думал, что у меня проблемы с моим 4-х скоростным сидиромом. Даже пытался вернуть его в магазин.
Кадр из игры Rebel Assault. Блочность, характерные для VQ повторы блоков. Блоки 4 на 4, преимущественно двухцветные, скорее всего codebook дополнительно закодирован с помощью BTC.
Как только позволили вычислительные мощности, все начали использовать кодеки на основе дискретного косинусного преобразования, а потом и вовсе перешли к видеовставкам на игровом движке, эпоха FMV игр завершилась.
Есть люди, которые исследуют старые видео форматы, реверсинженерят кодеки, бережно собирают и сохраняют эти знания. Очень рекомендую посетить их сайт wiki.multimedia.cx. Масса информации для всех интересующихся вопросами сжатия аудио и видео, в том числе и о современных кодеках.
В статье использованы скриншоты с сайта mobygames.com.
