Компенсация движения: найти предсказание и передать остаток

Если вычисляешь SAD, адрес предсказания и цену SAD+λR, а также объясняешь дробный вектор, переходи к «Теперь сам».

Как думаешь, одинаковые позиции дают самый маленький остаток

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

I-кадр кодируется без межкадровых опор. P-кадр разрешает предсказание из ранее декодированного опорного кадра, которым может быть I или P. Опора - уже восстановленные данные, а не обязательно исходный кадр камеры. Буквенные типы и порядок опор подробнее разберём в уроке про граф кадров.

Новый открывшийся фон при этом может вообще не иметь хорошего соответствия. Поэтому кодировщику нужен и независимый, intra-режим блока. Даже внутри предсказанного P-кадра часть блоков может быть закодирована независимо: тип кадра не означает, что каждый его пиксел обязан использовать один режим.

На что это похоже

Вместо повторной отправки страницы ты сообщаешь: «возьми прежнюю таблицу, сдвинь на одну колонку, затем исправь эти клетки». Экономия появится, если адрес и правки дешевле новой страницы. Если таблица совсем другая, такое описание может оказаться длиннее независимой записи.

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

Механизм: вектор, ошибка и остаток

Пусть текущий блок расположен в x,y. Определим предсказание как выборку из опорного кадра P(i,j)=ref(x+dx+i,y+dy+j). Вектор (dx,dy) указывает от текущего положения к источнику в опоре. Если объект переместился вправо на один пиксел, его прежний адрес левее, и подходящий dx в таком соглашении равен −1. У другого формата знак может быть определён иначе.

Остаток E=current−P. Если его передать точно, сложение P+E вернёт текущий блок. В кодировании с потерями передают приближение остатка: преобразование, квантование и энтропийные коды. Маленькая амплитуда остатка часто даёт больше нулей и более короткие описания, но сама по себе не определяет конечный размер потока.

Для сравнения кандидатов используют, например, SAD, сумму модулей разностей: Σ|current−P|, или сумму квадратов. В учебной цене J=SAD+λR величина R - заданная цена параметров в битах, λ≥0 задаёт обмен между ошибкой и битами. Полный кодировщик оценивает также остаток и режим; наша модель с готовой ценой вектора не является полным оптимизатором конечного искажения и битрейта.

Правило

Передавай выбранное предсказание и остаток, учитывая стоимость обоих. Задай направление вектора, набор допустимых позиций, правила границ и интерполяции. Полный поиск даёт минимум только в выбранном наборе кандидатов и для выбранной функции цены. Быстрый эвристический поиск может пропустить этот минимум.

Для блока из B пикселов, целочисленного радиуса r и сетки целых смещений от −r до r включительно по каждой оси полный поиск проверяет до (2r+1)² положений и требует O(B·(2r+1)²) сравнений. По всей картинке это может быть существенно дороже одного преобразования блоков. Иерархический поиск сначала смотрит уменьшенные изображения, затем уточняет позицию; он сокращает работу, но грубый уровень способен потерять важный небольшой объект.

Разбор: полпиксела лучше целого

В опорной строке [4,10,16,22], текущий блок [13,19]. Ни одна соседняя целая пара не совпадает с блоком: лучшая SAD равна 6. Между соседними отсчётами можно построить значения [7,13,19] линейной интерполяцией. Источник с дробной координатой 1,5 даёт [13,19] и SAD=0. Передаётся дробный вектор, а не добавленные в исходный кадр настоящие пикселы.

def sad(a, b):
    return sum(abs(x - y) for x, y in zip(a, b))


reference = [4, 10, 16, 22]
target = [13, 19]
for start in range(len(reference) - len(target) + 1):
    predicted = reference[start:start + len(target)]
    print("целая позиция", start, "SAD", sad(target, predicted))
half = [(a + b) / 2 for a, b in zip(reference, reference[1:])]
print("полупиксельные значения:", half)
print("предсказание с позиции 1,5:", half[1:3],
      "SAD", sad(target, half[1:3]))
errors, bits = [0, 3, 8], [10, 1, 1]
for weight in [0, 2, 10]:
    costs = [d + weight * r for d, r in zip(errors, bits)]
    best = min(range(3), key=lambda i: (costs[i], i))
    print("lambda", weight, "цены", costs, "выбран", best)
frame = [[0, 0, 10, 10], [0, 0, 10, 10],
         [20, 20, 30, 30], [20, 20, 30, 30]]
block = [20, 20, 20, 20]
candidates = []
for y in range(3):
    for x in range(3):
        pred = [frame[y + i][x + j] for i in range(2)
                for j in range(2)]
        candidates.append((sad(block, pred), y, x))
print("лучший блок SAD,y,x:", min(candidates))

целая позиция 0 SAD 18
целая позиция 1 SAD 6
целая позиция 2 SAD 6
полупиксельные значения: [7.0, 13.0, 19.0]
предсказание с позиции 1,5: [13.0, 19.0] SAD 0.0
lambda 0 цены [0, 3, 8] выбран 0
lambda 2 цены [20, 5, 10] выбран 1
lambda 10 цены [100, 13, 18] выбран 1
лучший блок SAD,y,x: (0, 2, 0)

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

Разбор: самый точный кандидат не самый дешёвый

Три кандидата имеют SAD [0,3,8] и цену вектора [10,1,1] битов. При λ=0 выигрывает первый. При λ=2 цены равны [20,5,10], выигрывает второй. Ошибка предсказания немного выросла, зато адрес стоит значительно меньше. При λ=10 второй остаётся лучшим с ценой 13.

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

Последний пример программы перебирает положения блока 2×2 в кадре 4×4. Кортеж (0,2,0) означает SAD=0, верхняя строка источника y=2, колонка x=0. Это адрес источника в опоре, а не готовый вектор: для текущего блока с верхним левым углом (x,y)=(1,1) получим (dx,dy)=(0−1,2−1)=(−1,1). Если текущие координаты другие, адрес источника останется тем же, а вектор изменится. Порядок координат явно напечатан в подписи. Повторяющийся узор может дать несколько равных минимумов; наше упражнение выбирает первый в построчном порядке.

Что ломается без этого

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

В простой классической модели цветного видео макроблок 16×16 по яркости при 4:2:0 содержит четыре яркостных блока 8×8 и по одному блоку цветности. Это организация рассматриваемых старых схем, а не универсальный размер для всех стандартов. Деление на блоки движения и блоки преобразования в других кодировщиках может быть устроено иначе.

Зачем это в работе

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

Теперь сам

Текущий блок [10,20,30,40], предсказание [12,18,31,37]. Найди SAD. Если цена вектора 4 бита и λ=3, чему равно J? Что ещё пришлось бы учесть для решения между intra- и inter-режимом?