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

TL;DR

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

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

Переупорядочение, сканирование и 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-сканирование старше любого видеокодека, существующего на рынке сегодня. Первое опубликованное описание – статья Вэнь-Хсин Чена и Уильяма Прэтта 1977 года «Scene Adaptive Coder», в которой они объединили DCT, скалярное квантование и коды Хаффмана для коэффициентов преобразования. Чена и Прэтт заметили, что на естественных изображениях после применения DCT и квантования энергия сосредоточена около DC-коэффициента, а зигзаг-обход максимизирует длины серий нулей и минимизирует количество кодовых слов Хаффмана, которые придётся прочитать декодеру.

Через восемь лет JPEG-комитет использовал тот же паттерн сканирования для 8×8-блоков, ссылаясь на работы Чена 1977 и 1984 годов. Видеостандарт H.261 (1988) применил аналогичный паттерн для своей 8×8-DCT. MPEG-1 (1993) унаследовал этот подход. MPEG-2 (1995) добавил альтернативный скан для чересстрочного контента. H.264 / AVC (2003) использовал зигзагообразный порядок для прогрессивных 4×4- и 8×8-блоков и «field scan» для чересстрочного видео. HEVC (2013) заменил зигзаг диагональным обходом по 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. Для чересстрочного контента H.264 применяет «сканирование по полям» – сначала по столбцам. У чересстрочных полей иная статистика вертикальных и горизонтальных частот, и обход по столбцам эффективнее упаковывает нули.

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

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 кодовых слова. Коэффициент сжатия уже на этой стадии составляет примерно ×20 – ещё до обработки данных энтропийным кодером.

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

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

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

Асимметрия правила и делает его эффективным. Реально разреженный блок – с одним-двумя ненулевыми коэффициентами – кодируется как одна-две пары символов плюс 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-блок: энкодер передаёт позицию последнего ненулевого коэффициента, декодер читает данные только до этой позиции, а остальные около тысячи ячеек пропускаются целиком.

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

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

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

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

AV1, выпущенный AOMedia в 2018 году, развил идею блочного сканирования. В отличие от HEVC, предлагающего три паттерна, AV1 хранит таблицы сканирования для каждой поддерживаемой формы трансформации: квадратные 4×4, 8×8, 16×16, 32×32, 64×64, прямоугольные, такие как 4×8 и 16×32, а также одномерные трансформы. Для 2D-блоков 4×4 используется зигзагообразное сканирование; для одномерных вертикальных трансформаций – сканирование по столбцам; для горизонтальных – по строкам; для больших двумерных блоков – диагональный обход.

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

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

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

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

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

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

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

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

Это одна из причин, по которой новые кодеки передают явную позицию последнего значимого коэффициента. В 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-блока – это разница между сессией отладки, закрытой за вечер, и той, что тянется неделями.

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

• Переупорядочение преобразует 2D-блок трансформации в одномерный список, в котором ненулевые коэффициенты идут вперёд, а нули – в конец.
• Классический зигзаговый обход проходит по диагоналям блока 8×8 и впервые был описан Ченом и Праттом в 1977 году.
• Кодирование длин серий упаковывает список в пары (run, level) и добавляет символ EOB; разрежённый блок 8×8 занимает около 15–20 бит.
• HEVC заменил глобальный зигзаговый обход диагональным сканированием по подблокам 4×4 и явно указывает позицию последнего ненулевого коэффициента.
• AV1 хранит шаблон сканирования для каждой формы трансформации и кодирует коэффициенты в обратном порядке; VVC связывает сканирование с зависимой квантовацией.
• Каждый новый кодек экономит биты на передаче нулей, но увеличивает вычислительную нагрузку на декодер при обработке одного блока.

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

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