- PVSM.RU - https://www.pvsm.ru -
В 90-е сложилась интересная ситуация: вычислительные мощности компьютеров были недостаточны для расчета хоть сколько-нибудь реалистичной графики и в тоже время компакт-диски предоставляли возможность записать огромный для тех времен объем информации. В общем, идея лежала на поверхности: неплохо бы улучшить качество игровой картинки за счёт видео контента и есть куда этот контент записать.
Но была и проблема: типичное игровое разрешение того времени — 320 на 200 точек при палитре из 256 цветов, что даёт нам 64 килобайта на кадр или полтора мегабайта на 25 кадров, при скорости чтения с компакт диска в 150 килобайт в секунду. Т.е. видео надо было жать и жать довольно сильно, а сжав, потом надо суметь декодировать, ведь мы помним, компы были слабенькие и декодирование, например, MPEG им было вообще не по силам. Тем не менее производители видео игр успешно решили проблему недостаточной производительности породив заодно множество видео-кодеков и игровых видео-форматов [1], некоторые из которых могли проигрываться аж 286-м (прописью: двести восемьдесят шестым) процессором.
Так началась эпоха FMV игр [2] (Full Motion Video Games). Я думаю, многие помнят её ярких представителей: Crime Patrol [3] от American Laser Games, Lost Eden [4], Cyberia [5], Novastorm [6] и даже Command & Conquer [7], в который многие играли только ради видеовставок между миссиями. В те времена выглядело это очень круто. Вау! Вау! Ну а мне было интересно, как же они закодировали это видео, в книжках о мультимедиа приводили то же описание проблемы, что и я выше, но ничего внятного о методах сжатия не писали, видимо, авторы в этом мало понимали и пересказывали какие-то сомнительные слухи.
На самом деле, всё оказалось очень просто, методов было всего три штуки и все очень простые.
Но перед тем как мы перейдём к самим методам, были ещё повсеместно использовавшиеся ухищрения. Во-первых, конечно, ни о каких 25 кадрах в секунду не могло быть и речи. Все поголовно резали fps, вплоть до 10 кадров в секунду (интерактивные тиры Americal Laser Games). 12, 14, 15 fps — типичные фрэйм рэйты. Во-вторых, конечно же, разрешение картинки резали почти всегда, ведь если с каждой стороны от кадра отрезать по 10 пикселей (по 3%), то это даст ~15% выигрыша. Ну а если разрешение понизить до 256 на 144 точек, как это сделали разработчики Novastorm, то выигрыш составит практически половину.
И так, смотрите, если взять 256 на 144 точи и 14 кадров в секунду, то это даст нам пол мегабайта несжатого видео вместо полутoра мегабайт, что обнадеживает.
Был такой формат BFI [8], что расшифровывалось разработчиками как «Brute Force & Ignorance». К этой группе относятся различные облегченные вариации по мотивам RLE и LZ алгоритмов. Это может показаться удивительным, но зачастую этого было достаточно, ну а если например в динамичной сцене сжатия не хватало, то всегда можно начать пропускать кадры, или же ещё сильнее понизить разрешение картинки в два, а то и в четыре раза (MM [9]). Видео в тирах American Lazer Games, играх серии Wing Commander, игре Lost Eden и других играх студии Cryo закодированы именно так.
[10]
Обратите внимание на характерные для Lossy RLE горизонтальные полосы.
Идея простая: возьмем скажем восемь идущих друг за другом кадров и нарежем их все на блоки по 4x2 пикселя, при разрешении картинки в 320 на 156 пикслей это даст нам 50 тысяч 24-х мерных векторов (8 пикселей в блоке, три цветовых компонента у каждого пикселя). Идущие друг за другом кадры весьма вероятно имеют много общего, поэтому среди этих векторов окажется множество близких друг к другу. Далее делим эти вектора на 4096 групп, для каждой группы вычисляем центроид. Из центроидов формируем codebook, ну а кадры записываем в файл в виде цепочек 12-и битных ссылок на codebook. Вместе это нам даёт примерно 13 килобайт на кадр, что в принципе по силам для двухскоростного сидирома.
Примерно такой подход использовался [11] в ранних играх серии Command & Conquer.
Декодирование, очевидно, очень быстрое и дешёвое, но вот качественно закодировать видео данным методом очень непросто. Не у всех, кто использовал VQ, это получилось хорошо. Вот полюбуйтесь на скриншоты [12] игры Creature Shock.
Тут опять всё просто, ничего сложного в 90-х не применяли. Чтобы сохранить 256-и цветное изображение нам надо по байту на каждый пиксель. А давайте уменьшим количество цветов, допустим, до двух, теперь на пиксель нужно по биту, мы получили восьмикратное сжатие и картинку кошмарного качества. Что можно с этим сделать? Просто применим данный подход не ко всему изображению целиком, а к небольшим блокам, ведь с большой вероятностью все цвета в рамках достаточно маленького блока близки друг другу. Режем картинку на блоки, скажем, 4 на 4 пикселя и для каждого из них сохраняем два цвета (его персональную палитру) и ещё 16 бит ссылок на эти цвета. Всего 4 байта на блок из 16-и пикселей, т.е. получили 4-х кратное сжатие. Но если вдруг окажется, что двух цветов для данного блока мало, то мы можем сохранить и четыре цвета — это даст нам двукратное сжатие. А можно разделить блок на 4 блока меньшего размера и для каждого из них вычислить по два цвета.
Этот метод был очень популярен, он прост и быстр в кодировании и декодировании, обеспечивает разумное качество, легко реализуем. В игре Novastorm используются блоки 8 на 8, которые могут иметь палитру из 2, 4, 8 цветов. В известной игре Z [13] тоже используется нарезка на блоки по 8 на 8 пикселей и деление их на части при необходимости (JV [14]). В Cyberia — комбинированный подход: используется как деление на меньшие блоки так и палитры разного размера (C93 [15], M95 [16]).
Оригинальный BTC, про который можно прочитать [17] в википедии, разработан для сжатия полутоновых изображений, цвета вычисляются таким образом чтоб сохранить среднее, и стандартное отклонение яркости в блоке. Должен заметить, что такой подход даст результаты ужасающего качества. Правильная палитра должна минимизировать сумму квадратов отклонений — вот тогда получается красиво.
Конечно, все использовали межкадровое сжатие в самом его примитивном виде зачастую даже без предсказания движения. Ни о какой коррекции яркости в палитризованых видео не могло быть и речи, поэтому на сценах с затемнением визуально падала частота кадров. Это очень было заметно в роликах самой первой Need For Speed [18], а я-то думал, что у меня проблемы с моим 4-х скоростным сидиромом. Даже пытался вернуть его в магазин.
[19]
Кадр из игры Rebel Assault. Блочность, характерные для VQ повторы блоков. Блоки 4 на 4, преимущественно двухцветные, скорее всего codebook дополнительно закодирован с помощью BTC.
Как только позволили вычислительные мощности, все начали использовать кодеки на основе дискретного косинусного преобразования, а потом и вовсе перешли к видеовставкам на игровом движке, эпоха FMV игр завершилась.
Есть люди, которые исследуют старые видео форматы, реверсинженерят кодеки, бережно собирают и сохраняют эти знания. Очень рекомендую посетить их сайт wiki.multimedia.cx [20]. Масса информации для всех интересующихся вопросами сжатия аудио и видео, в том числе и о современных кодеках.
В статье использованы скриншоты с сайта mobygames.com [21].
Автор: yannmar
Источник [22]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/252084
Ссылки в тексте:
[1] игровых видео-форматов: https://wiki.multimedia.cx/index.php/Category:Game_Formats
[2] FMV игр: https://ru.wikipedia.org/wiki/FMV
[3] Crime Patrol: http://www.mobygames.com/game/crime-patrol
[4] Lost Eden: http://www.mobygames.com/game/lost-eden
[5] Cyberia: http://www.mobygames.com/game/cyberia
[6] Novastorm: http://www.mobygames.com/game/novastorm
[7] Command & Conquer: http://www.mobygames.com/game/command-conquer
[8] BFI: https://wiki.multimedia.cx/index.php/BFI
[9] MM: https://wiki.multimedia.cx/index.php/American_Laser_Games_MM
[10] Image: http://www.mobygames.com/game/dos/mad-dog-mccree/screenshots/gameShotId,2185/
[11] использовался: https://wiki.multimedia.cx/index.php/VQA
[12] скриншоты: http://www.mobygames.com/game/creature-shock/screenshots
[13] Z: http://www.mobygames.com/game/z
[14] JV: https://wiki.multimedia.cx/index.php/JV
[15] C93: https://wiki.multimedia.cx/index.php/C93
[16] M95: https://wiki.multimedia.cx/index.php/M95
[17] прочитать: https://en.wikipedia.org/wiki/Block_Truncation_Coding
[18] Need For Speed: http://www.mobygames.com/game/need-for-speed
[19] Image: http://www.mobygames.com/game/dos/star-wars-rebel-assault/screenshots/gameShotId,23998/
[20] wiki.multimedia.cx: http://wiki.multimedia.cx
[21] mobygames.com: http://mobygames.com
[22] Источник: https://habrahabr.ru/post/325968/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.