動き補償を1から — 動画圧縮の9割はここ

動画のビットの行き先を決めているのは、変換でも量子化でもなく入口の予測です。ブロックマッチングが本当は何を最小化しているのか、なぜ動きベクトルは物体の動きではないのか、P/Bフレームの参照構造とGOPの切れ目が配信でどう事故になるのかを、前提知識なしで1から解きます。

比喩: 写し紙をずらして重ねる

前のフレームが写し紙に描いてある、と思ってください。次を描くとき、絵描きは一から描き直しません。写し紙を細かく切り分け、それぞれを少しずらして重ね、合わなかったところだけ描き足す。

切り分ける単位がブロック、ずらし方が動きベクトル、描き足す分が残差です。動き補償が決めているのは「このブロックの絵をどこから持ってくるか」だけ。合わなかった分は、すべて残差が引き受けます。

だから動き補償の良し悪しは「本当の動きを当てたか」ではなく、残差をどれだけ小さくできたかで測られます。似て非なるこの区別が、この記事の後半でずっと効いてきます。

「9割はここ」の意味

タイトルの9割は、ビット比率の実測ではありません。レバーの所在の話です。

コーデックの中身は、予測 → 残差の周波数変換 → 量子化 → エントロピー符号化という一本道です。後ろの3つは規格でほぼ完全に決められた装置ですが、予測だけは規格が決め方を定めていません。規格が縛るのは、選んだベクトルをどう伝えるか、小数位置の画素をどう作るか、という受け手側の作法だけです。

そして外すと後段は総崩れになります。残差が空に近ければ変換係数はほとんど0になり、外せば元の絵とほとんど同じ大きさになる。同じ規格・同じビットレートなのにエンコーダで画質が違うのは、ほぼここの差です。

全体の流れは動画圧縮を1からに、残差がそのあとどう畳まれるかはJPEGを1からにあります。ここでは入口の予測だけを掘ります。

ブロックマッチング: 「似ている」を数字にする

「いちばん似た絵を探す」には、似ている度合いを数字にしなければいけません。いまも主力なのが SAD（絶対差分和）です。

つまりこの式は、ブロック $B$ の中の画素を1つずつ、いまのフレーム $f_t$ の値と、前のフレーム $f_{t-1}$ を $(m_x, m_y)$ だけずらした位置の値とで引き算し、符号を外して全部足す、と言っているだけです。0に近いほどよく似ている。

二乗誤差ではなく絶対値を使うのには理由があります。掛け算が要らずSIMD命令で一気に処理でき、しかも途中で打ち切れる。和は足すほど増える一方なので、加算の途中でこれまでの最小値を超えた候補は、その場で捨てられます。

探索範囲の広さは、そのまま計算量になります。半径 $S$ 画素をすべて調べる全探索なら候補は $(2S+1)^2$ 個。$S=16$ でも1089点、1点が256画素の引き算なので1ブロックで約27.9万回。1080pには16×16のブロックが8160個あるので、1フレームで約22.8億回です。半径を欲張れない理由は、この二乗にあります。

本当に最小化しているのは、ビット

SADには弱点があります。残差はこのあと周波数変換されるのに、SADは変換後の高さを見ていない。同じ絶対値和でも、のっぺりした残差は少ない係数で済み、細かい縞模様の残差は係数がばらけて高くつきます。そこで、差分にアダマール変換をかけてから絶対値和を取る SATD が使われます。

そして最終的にエンコーダが最小化しているのは、歪みでもビットでもなく、その足し算です。

$D$ はそのブロックの歪み（SADやSATDで測った予測の外れ具合）、$R$ は送るのに必要なビット数（動きベクトル・モード・残差の合計）、$\lambda$ は両者を釣り合わせる天秤の傾きです。つまりこの式は「よく似ている場所」ではなく「安く済む場所」を選べ、と言っています。

ここから、まず引っかかる事実が出てきます。少しSADが大きくても、隣のブロックと同じベクトルならほぼ0ビットで送れる。ベクトルは予測との差で符号化されるからです。結果として、青空や白い壁のようなのっぺりしたブロックのベクトルは、実際の動きと無関係に隣と揃います。動きベクトル場は物体の動きの推定ではなく、「安かったから選ばれた矢印」の集まりです。

$\lambda$ は量子化の粗さに連動します。低ビットレートほど $\lambda$ が大きくなり、天秤はビットを惜しむ側へ倒れる。低画質の動画が大きな四角の塊に見えるのは、その判断の結果です。

速い探索は、谷を下る