Переупорядочение, zig-zag-сканирование и run-length-кодирование

TL;DR

После квантования у видеокодека остаётся маленькая сетка коэффициентов, в которой почти все ячейки нули, а ненулевые значения собраны в верхнем левом углу. Следующая задача – вытянуть эту сетку в одномерный список так, чтобы нули оказались рядом и энтропийный кодер мог сжать их почти бесплатно. Классическое решение – обход в форме зигзага, придуманный Wen-Hsiung Chen и William Pratt в конце 1970-х и попавший потом в JPEG, H.261, MPEG-2 и H.264. Список упаковывается в пары (run, level) с символом «конец блока» (EOB) в конце. HEVC заменил единый zig-zag диагональным обходом по 4×4-под-блокам и явной передачей позиции последнего ненулевого коэффициента, AV1 выбирает один из нескольких scan-паттернов под форму трансформа, а VVC привязывает скан к dependent quantization. Освойте эту стадию – и вы поймёте, почему «разреженный блок» стоит в битстриме почти ничего.

Почему это важно

Переупорядочение, scan и run-length-кодирование сидят между двумя стадиями, о которых все говорят, – квантованием с одной стороны и энтропийным кодированием с другой, – и решают, дойдут ли биты, сэкономленные при квантовании, до файла. Продакт-менеджер, который понимает, что «32-коэффициентный блок с двумя ненулями» помещается в меньше 20 бит, перестаёт бояться слова «высокий QP» и начинает задавать правильные вопросы про битрейт. Основатель, который умеет объяснить, почему файлы HEVC на 30–50% меньше H.264 при том же качестве – отчасти потому, что HEVC один раз кодирует позицию последнего ненулевого коэффициента, а не идёт мимо каждого нуля, – понимает одно из структурных преимуществ новых кодеков. Стриминг-инженер, способный прочитать hex-дамп MPEG-2-транспортного потока и узнать в нём EOB-символ, отлаживает плохой энкодер за вечер, а не за неделю.

Что вообще делает «переупорядочение»

После квантования каждый блок трансформа – это маленькая двумерная сетка целых чисел: 4×4, 8×8, 16×16 или 32×32. Почти все ячейки в ней нули, а немногие ненулевые сгруппированы в верхнем левом углу. Верхний левый угол хранит низкочастотную энергию (средняя яркость и плавные градиенты) и переживает квантование; правый нижний угол хранит высокочастотную энергию (тонкие текстуры и края) и почти полностью обнуляется.

Энтропийный кодер, который идёт следом, работает с одномерным потоком символов, а не с двумерной сеткой. Энкодер должен выбрать порядок, в котором он будет читать ячейки, записать их в список и передать этот список энтропийному коду. Сам порядок называется scan order; превращение сетки в список – переупорядочением; способ упаковки этого списка под энтропийный кодер, обычно как пары (число ведущих нулей, следующее ненулевое значение), – это run-length-кодирование.

Нажмите, чтобы увеличить

Смысл scan-порядка – поставить выжившие ненулевые коэффициенты в начало списка и собрать все нули в один хвост в конце. Если скан с этим справляется, энтропийный кодер передаёт начало списка обычными кодовыми словами, а весь хвост закрывает одним символом – «концом блока». Если порядок выбран плохо, ненулевые значения разбросаны среди нулей, серии (run-ы) короткие, и битстрим раздувается.

Короткая история – почему zig-zag и откуда он

Zig-zag-сканирование старше любого видеокодека, который сейчас на рынке. Первое опубликованное описание – статья Wen-Hsiung Chen и William Pratt 1977 года «Scene Adaptive Coder», в которой они комбинировали DCT, скалярное квантование и Huffman-коды для коэффициентов трансформа. Chen и Pratt заметили, что на естественных изображениях после DCT и квантования энергия концентрируется около DC-коэффициента, а зигзаг-обход максимизирует длины серий нулей и минимизирует число Huffman-кодовых слов, которое декодеру придётся прочитать.

Через восемь лет JPEG-комитет взял тот же scan-паттерн для 8×8-блоков, цитируя статьи Chen 1977 и 1984 годов. Видеостандарт H.261 (1988) использовал тот же паттерн для своей 8×8-DCT. MPEG-1 (1993) унаследовал его. MPEG-2 (1995) добавил альтернативный скан для interlaced-контента. H.264 / AVC (2003) использовал zig-zag для progressive 4×4- и 8×8-блоков и «field scan» для interlaced. HEVC (2013) заменил zig-zag диагональным обходом по 4×4-под-блокам. AV1 (2018) и VVC (2020) сохранили диагональный обход и добавили скан-паттерны под форму трансформа.

Нажмите, чтобы увеличить

Сквозь все эти изменения базовая интуиция не сдвинулась: идти по сетке в направлении, повторяющем линии равной частоты, потому что вдоль линий равной частоты лежат ячейки с похожей амплитудой, а похожие амплитуды дают длинные серии.

Классический zig-zag – как он обходит 8×8-блок

Классический zig-zag из JPEG / H.261 / MPEG-2 обходит 8×8-блок за 64 шага. Старт – на DC-коэффициенте в левом верхнем углу, шаг направо, потом вниз и налево по диагонали, потом шаг вниз, потом вверх и направо по следующей диагонали, и так далее. Путь похож на одну непрерывную «гармошку» из левого верхнего угла в правый нижний.

Числа ниже показывают порядок обхода 64 ячеек (0 – это DC, 63 – самый высокочастотный AC):

 0   1   5   6  14  15  27  28
 2   4   7  13  16  26  29  42
 3   8  12  17  25  30  41  43
 9  11  18  24  31  40  44  53
10  19  23  32  39  45  52  54
20  22  33  38  46  51  55  60
21  34  37  47  50  56  59  61
35  36  48  49  57  58  62  63

Ключевое свойство: индекс k в этом сканировании в среднем соответствует ячейке примерно на одинаковом расстоянии от DC-угла. Диагонали 8×8-блока лежат вдоль линий равной радиальной частоты, и DCT, применённая к плавному фрагменту естественного изображения, распределяет примерно равную энергию по каждой диагонали. Поэтому если читать 64 ячейки в этом порядке, средняя амплитуда плавно падает от индекса 0 к индексу 63 – и как только энкодер попадает в хвост из нулей, очень маловероятно, что внутри ещё встретится ненулевое значение.

H.264 использует ту же идею на меньшем 4×4-трансформе:

 0   1   5   6
 2   4   7  12
 3   8  11  13
 9  10  14  15

А в режиме 8×8-трансформа (в профиле High) – 64-позиционный скан, очень похожий на JPEG-овский. Для interlaced-контента H.264 хранит «field scan», который сначала идёт по столбцам – у interlaced-полей другая статистика вертикальных и горизонтальных частот, и обход по столбцам пакует нули лучше.

Нажмите, чтобы увеличить

Run-length-кодирование – превращаем список из одних нулей в горсть пар

После того как scan произвёл одномерный список, энкодер пакует его в последовательность пар (run, level). Run – число нулей, идущих перед следующим ненулевым значением; level – само это ненулевое значение. После последнего ненулевого значения энкодер шлёт символ end-of-block (EOB), который говорит декодеру: «всё остальное в этом блоке нули».

Разберём пример. Пусть 8×8-трансформ почти плоского фрагмента после квантования выглядит так:

 12   0   3   0   0   0   0   0
  0   0   0   0   0   0   0   0
 -2   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0

Zig-zag читает значения в порядке 12, 0, 0, -2, 0, 3, 0, 0, … и ещё 56 нулей. Первая ячейка – DC – обычно кодируется отдельно: её предсказывают по DC соседнего блока и шлют разницу. Так что AC-поток начинается со второй позиции. AC-значения в порядке скана:

0, 0, -2, 0, 3, 0, 0, 0, 0, 0, ... (ещё 53 нуля) ... 0

Run-length-кодер пакует это в:

(run=2, level=-2)   # два нуля, потом -2
(run=1, level=3)    # один нуль, потом 3
(EOB)               # дальше всё нули

Три символа покрывают 63 ячейки. Наивный кодер, который шлёт 63 значения по одному, отправил бы как минимум 63 кодовых слова. Коэффициент сжатия только на этой стадии – примерно ×20, ещё до того как энтропийный кодер увидел данные.

DC-коэффициент – число 12 в позиции (0, 0) – обрабатывается отдельно. Его значение почти наверняка близко к DC соседнего блока, поэтому энкодер передаёт разницу (DPCM), а не абсолютное значение. Разница идёт в свою VLC-таблицу, отдельную от AC.

В MPEG-2 каждая пара (run, level) маппится в кодовое слово переменной длины из фиксированной Huffman-таблицы; самые частые пары – (0, 1), (0, -1), (1, 1), (0, 2) – получают кодовые слова длиной в 2–3 бита. Сам EOB – это 2-битный код на самой вероятной позиции. Весь 8×8-блок из примера может уместиться в 15–20 бит битстрима, против 4096 сырых бит для несжатой 8×8×8-битной области.

Нажмите, чтобы увеличить

Асимметрия правила и делает его рабочим. Блок, реально разреженный – один-два ненулевых коэффициента – даёт один-два символа-пары плюс EOB и помещается в дюжину бит. Блок, реально плотный – много ненулевых коэффициентов по всему скану – даёт много пар-символов, и цена растёт. Энкодер платит за то, что шлёт, и квантование решило, что слать.

Почему HEVC выбросил zig-zag

HEVC работает с гораздо большими блоками трансформа, чем H.264 – до 32×32, с прямоугольными вариантами. Глобальный zig-zag по 32×32 шёл бы через 1024 ячейки, причём последний ненулевой коэффициент мог бы оказаться глубоко в хвосте. Правило 1990-х «иди по каждой ячейке, в конце пошли EOB» теряет смысл, когда «каждая ячейка» – это тысяча штук.

Дизайнеры HEVC заменили глобальный обход двумя изменениями. Во-первых, блок трансформа делится на 4×4-под-блоки. Скан идёт по под-блокам диагонально – сверху-справа к низу-слева вдоль каждой диагонали – и внутри каждого под-блока обходит 16 ячеек в том же диагональном направлении. Во-вторых, вместо того чтобы декодер обнаруживал EOB, читая до встречи с символом, энкодер заранее передаёт координаты (x, y) последнего ненулевого коэффициента, и декодер сразу знает, сколько позиций скана ему нужно прочитать.

Вместе эти два изменения означают, что 32×32-блок с ненулевыми значениями только в верхнем левом 8×8-фрагменте стоит примерно столько же, сколько 8×8-блок: энкодер шлёт позицию последнего коэффициента, декодер читает только до неё, а остальные ~1000 ячеек пропускаются оптом.

Второе изменение идёт ещё глубже. Внутри каждого 4×4-под-блока HEVC также передаёт coded_sub_block_flag – «весь этот под-блок нулевой, пропусти его». Энкодер, который агрессивно квантует 16×16-трансформ, часто получает три-четыре полностью нулевых 4×4-под-блока плюс один угловой с парой выживших значений. coded_sub_block_flag превращает каждый нулевой под-блок в один бит.

Нажмите, чтобы увеличить

HEVC также предлагает три scan-паттерна под-блока – diagonal, horizontal, vertical – и выбирает один из них по направлению intra-prediction блока. У блока, предсказанного из столбца сверху, большая часть выжившей энергии – в горизонтальных строках, и horizontal scan пакует нули лучше. У блока, предсказанного из строки слева, паттерн зеркалится. Выигрыш правильного выбора скана против фиксированного небольшой (около 0,5–1,0% битрейта при том же качестве), но он бесплатен на декодере, поэтому HEVC его держит.

AV1 и VVC – scan-паттерны под форму трансформа

AV1, выпущенный AOMedia в 2018-м, развил идею per-block-скана дальше. Если HEVC даёт три паттерна, AV1 хранит scan-таблицы для каждой поддерживаемой формы трансформа – квадратные 4×4, 8×8, 16×16, 32×32, 64×64, прямоугольные вроде 4×8 и 16×32, и одномерные трансформы. Для 4×4 2-D-скан – это zig-zag; для одномерных вертикальных трансформов – column scan; для одномерных горизонтальных – row scan; для больших 2-D-блоков – диагональный обход.

AV1 также разворачивает направление кодирования коэффициентов. Энкодер сначала передаёт позицию последнего ненулевого коэффициента (eob), затем идёт по скану в обратном направлении от этой позиции к DC, кодируя младшие биты амплитуды одним проходом и старшие биты со знаками – вторым. Обратный обход позволяет более поздним коэффициентам (которые в среднем меньше) задавать контекст для более ранних коэффициентов (которые в среднем больше), что подтягивает энтропийное кодирование.

VVC, финализированный в 2020-м, сохраняет HEVC-овский диагональный скан по 4×4-под-блокам и добавляет две хитрости. Во-первых, скан привязан к dependent quantization – trellis-coded-квантователю с двумя состояниями, в котором выбор состояния зависит от чётности предыдущего коэффициента в порядке скана. Контекстная модель для significance-флага текущего коэффициента зависит от его trellis-состояния, от диагональной позиции (сумма d = x + y) и от суммы частично восстановленных соседних коэффициентов в маленьком шаблоне вокруг текущей позиции. Во-вторых, VVC добавляет sign data hiding – трюк, заимствованный из опционального набора HEVC, в котором знак первого ненулевого коэффициента в под-блоке выводится из чётности суммы абсолютных значений в этом под-блоке, экономя один бит на под-блок.

Совокупный эффект на блок маленький – доли процента битрейта – но он суммируется по миллионам блоков в фильме.

Сравнительная таблица

Одна и та же концептуальная стадия живёт в каждом кодеке, но реализация уехала далеко от статьи Chen и Pratt 1977 года.

Паттерн монотонный в одну сторону: каждый новый кодек тратит меньше бит, чтобы пропустить нулевые части блока. Цена – сложность декодера: VVC-декодер, который делает контекстное моделирование по trellis-квантованному 64×64-блоку, делает кратно больше работы на пиксель, чем JPEG-декодер, читающий фиксированную Huffman-таблицу.

Типичная ловушка – EOB, который не пришёл

Один из самых простых способов сломать видеофайл – повредить один бит внутри run-length-кодированного блока. Декодер читает битстрим ячейку за ячейкой, ища EOB; если level разобран неправильно и EOB не приходит, декодер продолжает читать за пределы блока и попадает в начало следующего, где всё смещено. Результат – мазня мусора, которая распространяется до следующего slice-заголовка, где парсер ре-синхронизируется.

Это одна из причин, по которым новые кодеки шлют явную позицию последнего коэффициента. У HEVC last_significant_coeff_x и last_significant_coeff_y – это короткие целые числа в 4–5 бит, закодированные своими контекстными моделями, и они дают жёсткий верхний предел того, сколько блока читает декодер. Битовая ошибка внутри под-блока может испортить несколько коэффициентов, но не уйдёт в следующий блок.

Если вы отлаживаете H.264-стрим, который даёт «блочный мусор от центра кадра до правого края», – ищите потерянный или неправильно разобранный EOB. Если отлаживаете HEVC-стрим, у которого «блочный мусор в одном 16×16-регионе, который не распространяется», – ищите битовую ошибку внутри списка коэффициентов под-блока: сигнал last-coef локализовал повреждение.

Где здесь Фора Софт

Мы строим стриминговые и декодинговые пайплайны под видеоконференции, OTT, видеонаблюдение, e-learning и телемедицину, и читаем много битстримов в продакшене. Когда у клиента H.264-декодер падает на определённом классе кадров, след обычно ведёт к одной из стадий выше – квантователю, который работает слишком жарко для CABAC-контекста, настроенного под более низкие QP, CAVLC-парсеру, который неправильно считает trailing ones, или фрагментированному MP4, в котором флаги под-блоков HEVC-кадра выжили, а (x, y) последнего коэффициента – нет. Понимание битовой грамматики residual-блока – это разница между сессией отладки, которая закрывается за вечер, и той, что закрывается за неделю.

Ключевые выводы

• Переупорядочение разворачивает 2-D-блок трансформа в 1-D-список, где ненулевые коэффициенты впереди, а нули – в хвосте.
• Классический zig-zag обходит диагонали 8×8-блока и впервые описан Chen и Pratt в 1977 году.
• Run-length-кодирование пакует список в пары (run, level) плюс символ EOB; разреженный 8×8-блок стоит примерно 15–20 бит.
• HEVC заменил глобальный zig-zag диагональным сканом по 4×4-под-блокам и явной позицией последнего коэффициента.
• AV1 хранит scan-паттерн под каждую форму трансформа и кодирует коэффициенты в обратном порядке; VVC привязывает скан к dependent quantization.
• Каждый новый кодек тратит меньше бит на «пропусти нули», но больше работы декодера на ячейку.

Что почитать дальше

• Квантование: где теряется качество – стадия, которая и создаёт разреженные блоки, описанные в этой статье.
• Энтропийное кодирование в деталях: CAVLC, CABAC, arithmetic coding – во что (run, level)-пары превращаются в битстриме.
• Transform coding: DCT, ADST, целочисленные преобразования – почему коэффициенты вообще группируются в левом верхнем углу.