Пространственное (Intra) предсказание в HEVC

Пространственное (Intra) предсказание в HEVC

ГЛАВА 3

Video_compression_book

Пространственное предсказание (Intra). Обработка изображения в HEVC. Процедура пространственного предсказания: четыре этапа. Алгоритмы расчета значений пикселов внутри кодируемого блока.

 

 

Системы видеокодирования стандарта HEVC относятся к так называемым блочным гибридным кодекам. Блочность здесь означает, что каждый видеокадр во время кодирования разбивается на блоки, к которым и применяются алгоритмы видеокомпрессии. Что означает слово гибридный? Сжатие видеоданных при кодировании происходит во многом за счет устранения избыточности информации в последовательности видеоизображений. Очевидно, что изображения в соседних по времени видеокадрах с высокой вероятностью оказываются похожими друг на друга. При устранении временной избыточности для каждого кодируемого блока в текущем кадре ищется наиболее похожее изображение в ранее закодированных кадрах. Найденное изображение рассматривается как некоторая оценка (предсказание) кодируемого участка видеокадра. Результат предсказания вычитается из значений пикселов текущего блока. Разностный сигнал при «удачном» предсказании содержит значительно меньше информации, чем исходное изображение, что и обеспечивает эффективное сжатие. Но это только один из вариантов устранения избыточности. В HEVC предусмотрен и другой вариант, в котором для предсказания используются значения пикселов того же самого видеокадра, к которому относится кодируемый блок. Такое предсказание называют пространственным или внутрикадровым (Intra). Именно о наличии двух вариантов устранения временной или пространственной избыточности видеоизображений говорит слово гибридный.  Заметим также, что эффективность Intra-предсказания во многом определяет эффективность всей системы кодирования в целом. Рассмотрим более детально основные идеи методов и алгоритмов Intra-предсказания, предоставляемых стандартом HEVC.

Обработка изображения в HEVC-системе, как уже было сказано, осуществляется поблочно. Разбиение видеокадра на блоки производится адаптивно, то есть подстраивается под характер изображения. Прежде всего изображение слева-направо и сверху-вниз разбивается на одинаковые квадратные блоки, назывемые LCU (от англ. Largest Coding Unit). Размер LCU является параметром настройки кодирующей системы и задается перед кодированием. Этот размер может принимать значения 8x8, 16x16, 32x32 и 64x64. Каждый блок LCU может быть разбит на 4 квадратных подблока CU, каждый из которых, в свою очередь, может быть также разбит. Таким образом, LCU является корнем квадродерева. Минимальный размер CU или глубина квадродерева также является задаваемым параметром настройки кодирующей системы и может принимать значения 8x8, 16x16, 32x32, 64x64. Пространственное Intra-предсказание в HEVC выполняется для блоков квадратной формы, называемых PU (от англ. Prediction Unit). Размер PU совпадает с размером CU с двумя исключениями. Во-первых, размер PU не может превышать 32x32. Таким образом, CU с размером 64x64 содержит внутри себя 4 PU с размерами 32x32. Во-вторых, CU нижнего уровня квадродерева, имеющие минимально разрешенный размер, также могут быть разбиты на 4 квадратных PU с вдвое меньшими размерами. В результате набор разрешенных в HEVC размеров PU состоит из следующих значений: 4x4, 8x8, 16x16, 32x32. Пример разбиения изображения на блоки CU и PU приведен на рис. 1. Более толстой сплошной линией выделены границы LCU. Границы подблоков CU отмечены тонкой сплошной линией. Пунктиром обозначены границы PU в тех случаях, когда CU содержит 4 PU. Здесь же цифрами внутри блоков указан порядок перебора PU при кодировании.

Video3.1

Рис.1. Границы LCU, CU и PU (жирные сплошные линии, тонкие сплошные линии и пунктирные линии соответственно), а также порядок перебора блоков при кодировании (цифры внутри блоков)

При пространственном предсказании значений пикселов внутри текущего кодируемого блока в HEVC используются значения пикселов блоков, соседних с кодируемым. Эти пикселы называют референсными. Расположение референсных пикселов относительно кодируемого блока иллюстрируется на рис. 2. На этом рисунке текущий кодируемый блок помечен буквой C (его размер в этом примере составляют 8x8 отсчетов). Буквами A, B, D, E, F отмечены блоки, содержащие референсные пикселы. Их расположение отмечено серым цветом. Отметим, что далеко не всегда все референсные пикселы доступны для использования при предсказании. Очевидно, что для блоков с номерами 0, 1, 2, 8 на рис. 1 пикселы из блоков D, A, B недоступны, т. к. блоки с этими номерами находятся в самом верху видеокадра. Но это не единственный вариант, когда референсные пикселы считаются недоступными. Стандартом разрешено использовать для предсказания только те референсные пикселы, которые относятся к уже закодированным блокам. Такое ограничение позволяет после кодирования каждого блока произвести его декодирование и уже декодированные пикселы использовать в качестве референсных. Таким образом обеспечивается идентичность результатов предсказания в кодирующей и декодирующей системах. Для примера рассмотрим доступность референсных пикселов для блока с номером 17 на рис. 1. При предсказании этого блока доступными оказываются только пикселы из блоков A, D, E. Остальные блоки, окружающие блок номер 17 при заданном порядке обхода еще не подвергались процедуре кодирования и, как следствие, не могут использоваться при предсказании.

Video3.2

Рис.2. Расположение референсных пикселов относительно кодируемого блока

Всего в HEVC предусмотрено 35 различных вариантов расчета значений отсчетов в кодируемой области по значениям референсных пикселов при пространственном предсказании. Эти варианты называют режимами предсказания (Prediction modes). Каждый режим идентифицируется своим номером в диапазоне от 0 до 34.

В целом, в процедуре пространственного предсказания можно выделить четыре этапа. Те или иные из этих этапов не выполняются для некоторых режимов предсказания и размеров кодируемого блока. Первый этап заключается в генерации значений недоступных референсных пикселов, и он выполняется всегда, когда недоступные отсчеты есть. Сама генерация очень проста. Все недоступные значения приравниваются значению первого доступного отсчета. Так, например, если недоступны блоки D, A, B (рис. 2), то значения всех референсных пикселов из этих блоков устанавливаются равными значению самого верхнего референсного отсчета из блока E. Если недоступен блок B, то вся линейка значений отсчетов этого блока устанавливается равной значению самого правого референсного пиксела из блока A. Этап генерации для вертикальной линейки недоступных референсных отсчетов выполняется симметрично. Наконец, в том случае, когда ни один из блоков A, B, D, E, F недоступен, значения всех референсных отсчетов устанавливаются равными половине от максимально возможного значения. То есть, если кодируется видео, в котором отсчеты представляются 8-разрядными числами, то в этом случае всем референсным пикселам присваивается значение 127.

На втором этапе предсказания последовательность референсных отсчетов, перебираемых сначала снизу-вверх (то есть начиная с нижнего отсчета в блоке F и заканчивая отсчетом в блоке D), а затем слева-направо (то есть начиная с левого отсчета в блоке A и заканчивая самым правым отсчетом в блоке B), подвергается фильтрации. Направление перебора отсчетов при фильтрации отмечено на рис. 2 стрелками. Тип фильтра определяется размерами кодируемого блока. Для некоторых номеров режимов предсказания этот этап не выполняется. Кроме того, не выполняется фильтрация и при предсказании блоков размером 4x4.

На третьем этапе производится собственно расчет значений пикселов внутри кодируемого блока. Так как алгоритмы расчета сильно различаются для разных режимов предсказания, рассмотрим их более детально. Для рассмотрения нам понадобятся элементарные знания по математике (в частности тригонометрия).

Введем обозначения. За N обозначим размер кодируемого блока. Предсказываемые значения будем обозначать formula, где под x и y будем понимать координаты предсказываемого пиксела внутри кодируемого блока. Левый верхний отсчет в блоке имеет координаты (0,0). Правый нижний – formula. Последовательность референсных отсчетов, находящихся над кодируемым блоком (в блоках D, A, B на рис. 2), обозначим за formula, где координата x может принимать значения -1, 0, 1, … 2N-1. Столбец же референсных отсчетов, находящихся слева от кодируемого блока обозначим formula, где координата y также может меняться в диапазоне от -1 до 2N-1. Введенные обозначения иллюстрируются на рис. 3.

Video3.3

Рис.3. Обозначения, используемые при описании режимов Intra предсказания

Как уже было сказано, каждый режим предсказания однозначно идентифицируется своим номером. Пойдем последовательно по возрастанию номеров.

Режим с номером 0.

Это так называемый DC режим. При использовании этого режима всем отсчетам formula присваивается одно и то же значение formula, которое рассчитывается как среднее арифметическое референсных отсчетов:

formula,

где за formula  обозначена операция взятия целой части числа.

Режим с номером 1.

Его также называют Planar. В этом режиме каждое значение formula получается как среднее арифметическое двух чисел formula и formula. Эти числа рассчитывают как результат линейной интерполяции в горизонтальном (formula) и вертикальном (formula) направлениях. Процессы интерполяции иллюстрируются на рис. 4.

Video3.4

Рис.4. Интерполяция в горизонтальном и вертикальном направлениях

При вычислении интерполяция в горизонтальном направлении производится между значением  и отстоящим от него на N+1 отсчетов значением . Значение получается в результате интерполяции между значением  и значением , также отстоящим от верхней строки референсных пикселей на N+1 отсчет в вертикальном направлении.
Математически расчет значений в этом режиме можно описать следующим образом:

formula

где

formula

а

formula

Остальные режимы предсказания с номерами от 2 до 34 называют угловыми. В этих режимах значения референсных отсчетов в заданном направлении расставляются внутри кодируемого блока. В том случае, когда позиция предсказываемого пиксела formula попадает между референсными отсчетами, в качестве предсказания используется интерполированное значение. Среди этих режимов можно выделить две симметричные группы. Для режимов с номерами от 2 до 17 расстановка референсных значений производится в направлениях слева-направо. Для режимов с номерами от 18 до 34 такая расстановка ведется сверху-вниз. Соответствие между номерами режимов и направлением расстановки референсных отсчетов иллюстрируется на рис. 5.

Video3.5

Рис.5. Номера угловых режимов предсказания и соответствующие им направления расстановки референсных отсчетов внутри кодируемого блока

Угловые режимы предсказания с номерами 18-34.

Для этих режимов угол formula, задаваемый номером режима предсказания и определяющий направление расстановки, отсчитывается от вертикального направления (рис. 6). Номерам режимов с 18 по 25 соответствуют отрицательные значения угла formula, номерам с 27 по 34 – положительные.

Video3.6

Рис.6. Угловое предсказание в вертикальном направлении

Рассмотрим расчет значения formula, ориентируясь на рис. 6. Очевидно, что координата проекции точки formula на горизонтальную ось, содержащую референсные отсчеты (на рис. 6 обозначены за formula, но об этом позже), в направлении, задаваемом углом formula, может быть определена как:

formula

В том случае, когда значение formula совпадает с координатой одного из референсных отсчетов, значение formula присваивается formula. Это происходит всегда, когда координата проекции formula является целым числом. Если formula не является целым, то в качестве formula принимается результат линейной интерполяции между значениями референсных отсчетов formula и formula, являющихся соседями точки с координатой formula. Весовые множители при линейной интерполяции для значений formula и formula, т.е. величина formula и formula, рассчитываются с точностью в formula пиксела*. Все вычисления производятся в целых числах. Для реализации целочисленной арифметики при сохранении заданной точности весовые множители умножаются на 32 перед вычислениями. После проведения расчетов интерполированное значение делится на 32, округляется до ближайшего целого и присваивается formula. Для ускорения расчетов округленные значения formula для всех значений углов formula занесены в таблицу (в < arel="nofollow" href="https://www.itu.int/rec/T-REC-H.265">стандарте величина formula названа intraPredAngle, а ее значения содержатся в таблице 8.4).

*Примечание. Линейная интерполяция.

Обратим внимание еще на один момент, связанный с угловыми предсказаниями в вертикальном направлении. При отрицательных углах (как раз такой случай изображен на рис. 6) для предсказания необходимо использование референсных отсчетов из вертикального столбца formula. Для упрощения их использования и вводится вспомогательный массив formula, значения которого использовались в предыдущих рассуждениях. Необходимость возникает в тех случаях, когда координата проекции formula имеет отрицательное значения. Номера референсных отсчетов formula из столбца formula, которые используются в этом случае определяются величиной угла formula, точнее величиной formula:

formula

Вычисление значений formula производится с использованием целочисленной арифметики с точностью до formula отсчета. Для ускорения вычислений округленные значения formula для всех возможных углов (режимов углового предсказания) рассчитаны заранее и занесены в таблицу (в стандарте величина formula названа invAngle, а ее значения содержатся в таблице 8.5). Таким образом, перед проведением предсказания при отрицательных углах необходимо рассчитать все возможные значения formula и занести величины formula в массив formula для отрицательных значений formula. При положительных formula значения formula совпадают со значениями formula.

Угловое предсказание в горизонтальном направлении (режимы с номерами 2 – 17) осуществляется аналогично. Угол  в этом случае отсчитывается от горизонтального направления. При этом режимы предсказания с номерами 2 – 9 соответствуют положительным значениям угла formula, а у режимов с номерами 11 – 17 значения formula отрицательны. Можно даже использовать описанную выше процедуру для предсказания в вертикальных направлениях. Для этого необходимо поменять местами formula иformula, а после расчета квадратной матрицы всех значений formula провести ее транспонирование.

Как уже было сказано, процедуру пространственного предсказания условно можно разделить на 4 этапа, из которых 3 мы уже рассмотрели. На четвертом этапе предсказанные значения formula подвергаются дополнительной постфильтрации. Фильтрация четвертого этапа используется только для 3 из 35 режимов предсказания. Это режимы с номерами 0 (DC), 10 (в этом режиме референсные отсчеты, находящиеся слева от кодируемого блока расставляются внутри блока в горизонтальном направлении слева-направо), 26 (в этом режиме референсные отсчеты дублируются внутри блока сверху-вниз). При предсказании с этими режимами на границе блока может возникать резкий перепад между референсными отсчетами и предсказанными значениями. Для режима DC такой перепад может возникать как на левой, так и на верхне границах. Как следствие, процедуре фильтрации подвергаются отсчеты, находящиеся на этих границах. При использовании 10 режима перепад возможен только на верхней границе блока. Соответственно и фильтруются только граничные отсчеты сверху. При использовании режима 26 можно ожидать перепад на левой границе блока, отсчеты которой и подвергаются сглаживанию.

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

formula

Из этого уравнения легко получить:

formula

В случае интерполяции между двумя соседними точками дискретной последовательности отсчетов расстояние между соседними отсчетами равно 1. С учетом этого, обозначив за formula величину formula, получим:

formula

 

29 ноября 2018

Читать другие статьи:

Глава 1. Просто о видеокодировании

Глава 2. Межкадровое (Inter) предсказание в HEVC

Глава 4. Компенсация движения в HEVC

Глава 5. Постпроцессинг в HEVC

Глава 6. Контекстно-адаптивное двоичное арифметическое кодирование. Часть 1

Глава 7. Контекстно-адаптивное двоичное арифметическое кодирование. Часть 2

Глава 8. Контекстно-адаптивное двоичное арифметическое кодирование. Часть 3

Глава 9. Контекстно-адаптивное двоичное арифметическое кодирование. Часть 4

Глава 10. Контекстно-адаптивное двоичное арифметическое кодирование. Часть 5

 

Автор:

Олег Пономарев - 16 лет занимается вопросами видео кодирования и цифровой обработки сигналов, специалист в области распространения радиоволн, статистической радиофизики, доцент кафедры радиофизики НИ ТГУ, кандидат физико-математический наук. Руководитель исследовательской лаборатории Elecard.

 

Инструмент для детального анализа этапов кодирования видеопоследовательности - Elecard StreamEye

Инструмент для сравнения параметров видео, закодированного разными энкодерами