СПОСОБ БЫСТРОГО ВЫБОРА РЕЖИМА ПРОСТРАНСТВЕННОГО ПРЕДСКАЗАНИЯ В СИСТЕМЕ КОДИРОВАНИЯ HEVC Российский патент 2015 года по МПК H04N19/159 H04N19/593 

ОБЛАСТЬ ТЕХНИКИ

Изобретение относится к кодированию и декодированию цифровых видеоданных.

УРОВЕНЬ ТЕХНИКИ

В основе алгоритмов компрессии видеоданных HEVC лежит несколько простых идей. Если взять некоторую часть изображения, то с большой вероятностью вблизи этого участка в данном кадре или в соседних кадрах окажется участок, содержащий похожее, мало отличающееся по значениям интенсивности пикселей, изображение. Таким образом, для передачи информации об изображении в текущем участке достаточно передать только его отличие от ранее закодированного похожего участка. Процесс поиска похожих участков среди ранее закодированных изображений называют предсказанием (от англ. prediction). Набор разностных значений, определяющих отличие текущего участка от найденного предсказания, называют остатком (от англ. residual). Можно выделить два основных типа предсказания. В первом из них значения Prediction представляют собой набор линейных комбинаций пикселей, примыкающих к текущему участку изображения слева и сверху. Такое предсказание называют пространственным (от англ. Intra Prediction). Во втором - в качестве предсказания используются линейные комбинации пикселей похожих участков изображений ранее закодированных кадров (эти кадры называют ссылочными - от англ. Reference). Такое предсказание называют временным (от англ. Inter Prediction). Для восстановления изображения текущего участка, закодированного с временным предсказанием, при декодировании необходима информация не только об остатке (Residual), но и о номере кадра, на котором находится похожий участок, и координатах этого участка.

На следующем этапе кодирования полученные при предсказании значения Residual подвергаются двумерному косинус-преобразованию Фурье с последующим квантованием. Затем полученный набор квантованных спектральных коэффициентов, сопровождаемый информацией, необходимой для выполнения предсказаний при декодировании, подвергается энтропийному кодированию.

Основной структурной единицей в HEVC является блок кодирования (CU - сокр. от англ. coding unit). Внутри каждого такого блока выбираются области - блоки предсказания (PU - сокр. от англ. prediction unit). Разбиение видеокадра на CU производится адаптивно, так что есть возможность подстраивать границы CU под границы объектов на изображении, а вложенные CU образуют квадродерево.

В пределах каждой CU выбираются области для вычисления предсказания - Prediction Unit (PU). При пространственном предсказании область CU может совпадать с PU (режим 2N×2N) или может быть разбита на 4 квадратных PU вдвое меньшего размера (режим N×N). Стандартом определены минимально и максимально возможные размеры PU - 4×4 и 32×32 соответственно.

Пространственное предсказание выполняется в HEVC одним из 35 способов. При этом используются значения пикселей-«соседей», примыкающих к границе кодируемой PU слева и сверху. Способы пространственного предсказания в HEVC можно условно разделить на две неравные группы. К первой группе относятся два способа - Planar и DC. В режиме Planar значения, используемые в качестве предсказания, лежат на плоскости, наклон которой в вертикальном и горизонтальном направлениях определяется по пикселям-«соседям». Этот режим предназначен для предсказания областей PU с линейным изменением значений пикселей в каком-либо направлении. В режиме DC в качестве предсказания всех пикселей из PU используется одно значение, равное среднему арифметическому пикселям-«соседям». Назначение этого режима не требует пояснений.

Режимы второй группы называют угловыми. При вычислении значения, используемого в качестве предсказания, во всех 33-х угловых режимах пиксели-«соседи» сдвигаются в заданном (одном из 33-х) направлении. Если положение предсказываемого пикселя попадает между сдвинутыми копиями пикселей-«соседей», для расчета предсказания используется линейная интерполяция. Точность оценки положения предсказываемого пикселя между сдвинутыми пикселями-«соседями» задана равной 1/32 межпиксельного интервала.

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

Из предшествующего уровня техники известен способ выбора одного из 35 режимов предсказания при кодировании, реализованных в кодере [HEVC Test Model НМ v. 11.0 [Электронный ресурс]. - Режим доступа: https://hevc.hhi.fraunhofer.de/svn/svn_HEVCSoftware/tags/HM-11.0/], в котором осуществляется перебор всех возможных для каждого кодируемого блока вариантов предсказания. В этом случае выполняется полный цикл кодирования-декодирования каждого блока, что позволяет провести т.н. Rate-Distortion Optimization (RDO). В процессе RDO из всех возможных режимов выбирается тот, который обеспечивает наибольшую степень сжатия видеоданных кодируемого блока (наименьший rate) при наименьшем уровне искажений, вносимых в эти данные в процессе кодирования (наименьший уровень Distortion).

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

Известен также способ, называемый быстрым, [Zhao, L.; Zhang, L.; Ma, S.; Zhao, D. Fast mode decision algorithm for intra prediction in HEVC. Visual Communications and Image Processing (VCIP). IEEE, 2011, pp. 1-4], который реализуется в два этапа. На первом этапе выполняется предсказание кодируемого блока всеми возможными способами и формируется укороченный список режимов-кандидатов. Выбор из сформированного списка наилучшего режима осуществляется в процессе RDO на втором этапе. Отбор режимов-кандидатов на этапе формирования списка может осуществляться по различным критериям, определяемым настройками кодирующей системы. В качестве такого критерия может выступать минимальное значение суммы абсолютных разностей пикселей предсказания и оригинала (SAD или Sum of Absolute Differences), минимальное значение суммы квадратов разностей пикселей предсказания и оригинала (SSE или Sum of Sqared Errors) или минимальное значение суммы модулей коэффициентов преобразования Адамара разностей пикселей предсказания и оригинала (SATD или Sum of Absolute Transformed Differences).

Недостатком этого способа является то, что для построения списка режимов-кандидатов необходимо выполнить предсказание кодируемой области всеми 35 способами. Быстрый способ опять основан на полном переборе всех 35 режимов предсказания для каждой кодируемой области. Некоторое ускорение здесь достигается не за счет уменьшения количества перебираемых режимов предсказания, а за счет упрощения процедуры оценки качества предсказания в каждом из режимов. На основе таких упрощенных процедур оценивания качества строится сокращенный список режимов-кандидатов, для которых уже проводится полная RDO-оценка качества предсказания, полностью аналогичная той, что используется в первом способе.

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

Технический результат, который решается с помощью предложенного решения, состоит в снижении объемов вычислений при поиске оптимального режима кодирования блока, что позволяет ускорить процесс кодирования в целом за счет предварительного отбора режимов предсказания, построения списка режимов-кандидатов.

Технический результат достигается тем, что в способе быстрого выбора режима пространственного предсказания в системе кодирования HEVC, заключающемся в построении укороченного списка режимов-кандидатов пространственного предсказания длиной не более шести позиций, основанном на анализе высокочастотных горизонтальной и вертикальной составляющих стационарного вейвлет преобразования Хаара кодируемой области изображения, согласно предложенному решению: - массив значений высокочастотной горизонтальной составляющей преобразования Хаара получается путем вычитания из значения каждого пикселя кодируемой области значения соседнего слева пикселя;

- массив значений высокочастотной вертикальной составляющей преобразования Хаара получается путем вычитания из значения каждого пикселя кодируемой области значения соседнего сверху пикселя;

- режим Planar включают в список режимов-кандидатов, если все абсолютные значения горизонтальных и вертикальных высокочастотных составляющих меньше шага квантования при кодировании;

- режим DC включают в список режимов-кандидатов, если среднеквадратическое отклонение значений горизонтальных и вертикальных высокочастотных составляющих меньше шага квантования,

- два угловых режима предсказания, соответствующие взаимному смещению точек пересечения линии минимальных значений модуля градиента, проходящей через точку максимума массива вертикальных высокочастотных составляющих, с вертикальными границами массива высокочастотных составляющих включают в список режимов-кандидатов,

-два угловых режима предсказания, соответствующие взаимному смещению точек пересечения линии минимальных значений модуля градиента, проходящей через точку максимума массива горизонтальных высокочастотных составляющих, с горизонтальными границами массива высокочастотных составляющих включают в список режимов-кандидатов,

- окончательный выбор режима предсказания для кодируемой области изображения из построенного списка режимов-кандидатов осуществляют на основе стандартной RDO (rate-distortion optimization) оценки.

СПОСОБ ОСУЩЕСТВЛЯЕТСЯ СЛЕДУЮЩИМ ОБРАЗОМ

Для построения списка режимов-кандидатов проводят анализ модуля высокочастотных горизонтальной и вертикальной составляющих (подробностей) стационарного вейвлет преобразования Хаара (СВПХ) изображения кодируемой области.

Для получения горизонтальных и вертикальных подробностей СВПХ формируются массивы hC(x,y), х=-1,0,…,nТ-1, y=1,0,…,nТ-1 и νC(x,y), х=-1,0,…nТ-1, y=-1,0,…,nT-1. Значения элементов этих массивов при x=0,…, nТ-1, y=0,…,nТ-1 равны значениям интенсивности пикселов кодируемой PU. Значения hc(-1,y),y=-1,…nT равны значениям интенсивности пикселей-«соседей», примыкающих к области PU слева, a hc(x,-1),x=0,…,nΤ-1 равны значениям интенсивности пикселей-«соседей», примыкающих к PU сверху. Аналогично, значения νC(x,-1),х=-1,…,nΤ-1 равны значениям интенсивности пикселей-соседей», примыкающих к области PU сверху, а νC(-1,y),y=0,…,nТ-1 - значениям интенсивности пикселей-«соседей», примыкающих к PU слева. За nT обозначен размер кодируемой PU. Горизонтальные и вертикальные подробности H и V формируются как:

H(x,y)=|hC(x,y)-hC(x-1,y)|, x=0,…,nT-1, y=0,…,nT.

V(x,y)=|νC(x,y)-νC(x,y-1)|, x=0,…,nΤ, y=0,…,nT-1.

Процесс построения списка режимов-кандидатов состоит из четырех этапов. На первом этапе принимается решение о включении в список режима Planar. Этот режим включается в список, если:

,

где: qStep - шаг квантования.

На втором этапе проверяется режим DC. Этот режим включается в список, если выполняется условие:

На третьем этапе выбираются угловые режимы-кандидаты по значениям в массиве вертикальных подробностей V(x,y). Для этого определяется позиция y_max, x_max максимального элемента массива V(x,y). Текущая позиция y_cr устанавливается равной y_max, x_cr - равной x_max. Итеративно для каждого следующего столбца с номером x_cr=х_cr+1 новое значение y_cr устанавливается равным номеру максимального элемента в данном столбце из диапазона [y_cr-2, y_cr+2,].

Обновление позиции продолжается, пока x_cr≤nT и 0<y_cr<nT-1. Точки x_cr, y_cr в процессе итераций проходят по линии минимального градиента значений V(x,y) справа от максимального элемента этого массива. Аналогичный итеративный процесс позволяет проследить линию наименьшего градиента значений V(x,y) слева от позиции x_max, y_max. Начинается этот процесс с установки текущей позиции y_cl равной y_max, х_сl - равной x_max. Итеративно для каждого следующего столбца с номером х_с=x_cl-1 новое значение y_сl устанавливается равным номеру максимального элемента в данном столбце из диапазона [y_cl-2, y_cl+2]. Обновление позиции х_сl, y_сl продолжается, пока х_сl≥0 и 0<у_cr<nТ-1.

Если обе позиции y_cr и y_cl попали на одну и ту же границу блока, результаты такого поиска некорректны. В таком случае поиск выполняется вверх и вниз в соответствии с алгоритмом четвертого этапа, применяемого к подробностям V(x,y).

Взаимное расположение найденных двух точек x_cl, y_cl и x_cr, y_cr задают направление, по которому определяется параметр режимов углового предсказания IntraPredAngle и номер режима предсказания. Определяются значения переменных следующими выражениями:

.

Если dir=1, то IntraPredAngle1=-α_i, IntraPredAngle2=-α_i+1,

где α∈{-32, -26, -21, -17, -13, -9, -5, -2, 0, 2, 5, 9, 13, 17, 21, 26, 32} и α_i≤tgphi<α_i+1, а номера соответствующих режимов предсказания лежат в диапазоне 2-17.

Если dir=1, то IntraPredAngle1=-α_i, IntraPredAngle2=-α_i+1,

где α∈{-32, -26, -21, -17, -13_, -9, -5, -2, 0_, 2, 5, 9, 13, 17, 21, 26, 32} и α_i≤tgphi<α_i+1, номера соответствующих режимов предсказания лежат в диапазоне 18-34.

Четвертый этап аналогичен третьему, но режимы-кандидаты выбираются на основе анализа значений массива горизонтальных подробностей H(x,y). Для этого определяется позиция y_max, x_max максимального элемента массива Н(x,y) Текущая позиция y_cr устанавливается равной y_max, x_cr - равной x_max. Итеративно для каждой следующей строки с номером y_cr=y_cr+1, новое значение x_cr устанавливается равным номеру максимального элемента в данной строке из диапазона [x_cr-2, x_cr+2]. Обновление позиции продолжается, пока y_cr≤nT и 0<x_cr<nT-1. Точки x_cr, y_cr в процессе итераций проходят по линии минимального градиента значений H(x,y) ниже положения максимального элемента этого массива. Аналогичный итеративный процесс позволяет проследить линию наименьшего градиента значений H(x,y) над позицей x_max, y_max. Начинается этот процесс с установки текущей позиции y_cl равной y_max, x_cl - равной x_max. Итеративно для каждой следующей строки с номером y_cl=y_cl-1, новое значение х_cl устанавливается равным номеру максимального элемента в данной строке из диапазона [x_cl-2, x_cl+2]. Обновление позиции х_сl, y_cl продолжаетсяе пока y_cl≥0 и 0<x_cl<nT-1.

Если обе позиции х_cr и х_сl попали на одну и ту же границу блока, результаты такого поиска некорректны. В таком случае поиск выполняется влево и вправо в соответствии с алгоритмом третьего этапа, применяемого к массиву значений горизонтальных подробностей H(x,y).

Взаимное расположение найденных двух точек x_cl, y_cl и x_cr, y_cr задают направление, по которому определяется параметр режимов углового предсказания IntraPredAngle и номер режима предсказания. Определим значения переменных следующими выражениями:

.

Если dir=0, то IntraPredAngle1=α_i, IntraPredAngle2=α_i+1,

где α∈{-32, -26, -21, -17, -13, -9, -5, -2, 0, 2, 5, 9, 13, 17, 21, 26, 32} и α_i≤tgphi<α_i+1, а номера соответствующих режимов предсказания лежат в диапазоне 2-17.

Если dir=1, то IntraPredAngle1=-α_i, IntraPredAngle2=-α_i+1,

где α∈{-32, -26, -21, -17, -13, -9, -5, -2, 0, 2, 5, 9, 13, 17, 21, 26, 32} и α_i≤tgphi<α_i+1, а номера соответствующих режимов предсказания лежат в диапазоне 18-34.

Таким образом, предложенный способ позволяет формировать список режимов-кандидатов, качество предсказаний которых оценивается на заключительном этапе по стандартной процедуре RDO. Длина списка ограничена сверху шестью позициями. Формирование списка не требует проведения самой процедуры предсказания, что приводит к существенному сокращению объема вычислений при выполнении пространственного предсказания значений пикселей кодируемого блока.

Изобретение относится к технологиям кодирования и декодирования цифровых видеоданных. Техническим результатом является ускорение процесса кодирования за счет снижения объемов вычислений при поиске оптимального режима кодирования блока. Предложен способ быстрого выбора режима пространственного предсказания в системе кодирования HEVC. Для построения списка режимов-кандидатов проводят анализ модуля высокочастотных горизонтальной и вертикальной составляющих стационарного вейвлет преобразования Хаара изображения кодируемой области. Процесс построения списка режимов-кандидатов состоит из четырех этапов. На первом и втором этапах принимаются решения о включении в список режима Planar и режима DC. На третьем этапе выбираются угловые режимы-кандидаты по значениям в массиве вертикальных подробностей, а на четвертом этапе режимы-кандидаты выбираются на основе анализа значений массива горизонтальных подробностей.

Способ быстрого выбора режима пространственного предсказания в системе кодирования HEVC, заключающийся в построении укороченного списка режимов-кандидатов пространственного предсказания длиной не более шести позиций, основанный на анализе высокочастотных горизонтальной и вертикальной составляющих стационарного вейвлет преобразования Хаара кодируемой области изображения, при этом массив значений высокочастотной горизонтальной составляющей преобразования Хаара получается путем вычитания из значения каждого пикселя кодируемой области значения соседнего слева пикселя, при этом массив значений высокочастотной вертикальной составляющей преобразования Хаара получается путем вычитания из значения каждого пикселя кодируемой области значения соседнего сверху пикселя, при этом режим Planar включают в список режимов-кандидатов, если все абсолютные значения горизонтальных и вертикальных высокочастотных составляющих меньше шага квантования при кодировании, при этом режим DC включают в список режимов-кандидатов, если среднеквадратическое отклонение значений горизонтальных и вертикальных высокочастотных составляющих меньше шага квантования, при этом два угловых режима предсказания, соответствующие взаимному смещению точек пересечения линии минимальных значений модуля градиента, проходящей через точку максимума массива вертикальных высокочастотных составляющих, с вертикальными границами массива высокочастотных составляющих включают в список режимов-кандидатов, при этом два угловых режима предсказания, соответствующие взаимному смещению точек пересечения линии минимальных значений модуля градиента, проходящей через точку максимума массива горизонтальных высокочастотных составляющих, с горизонтальными границами массива высокочастотных составляющих включают в список режимов-кандидатов, при этом окончательный выбор режима предсказания для кодируемой области изображения из построенного списка режимов-кандидатов осуществляют на основе стандартной RDO (rate-distortion optimization) оценки.