連鎖のひとつの段 — 何が入り、何が出て、後段で何が壊れるか
この段はエンコード処理のどこに位置するか
動画エンコーダは単一のアルゴリズムではなく、順序の決まった 8 つの段です。その順序は恣意的ではありません。どの段も、直前の段が仕事を可能にしてくれたからこそ存在します。このツールはそのうちの 1 つを扱います。下の連鎖から残りの 7 つに移動できます。
動き推定シミュレーター — 各ブロックがどこへ動いたかを見つけ、ブロックの代わりに差分を符号化する
- 入ってくるもの
- P または B フレームと、その参照フレーム。
- 出ていくもの
- ブロックごとの動きベクトルと残差 — 予測が外した分そのもの。
- 次の段が前提とすること
- 量子化が受け取るのは残差で、絵ではありません。残差はほぼ全域でゼロに近く、だからこそ量子化が安く済みます。
- ここで壊れるもの
- 一致が悪いと、間違った絵ではなく高価な絵ができます。残差が持つエネルギーが増え、同じ量子化設定でもより多くのビットを吐きます。この段が変えるのは出力の大きさで、設定ではありません。
全プロセスの詳細解説
-
1ブロックあたり225個の位置から導出される探索ウィンドウ 5 ステップ
全探索動き予測では、1 ブロックあたり 225 箇所、合計 14 400 箇所の位置を検証します。そこから探索ウィンドウを算出し、高速探索によって何が得られるかを考えてみましょう。
-
225 は完全平方数であり、それがヒントになります。探索は 15 × 15 の変位候補からなる正方形のウィンドウで行われ、これは各方向に −7 〜 +7 ピクセルを意味します。
-
合計数を 1 ブロックあたりの処理数で割ることで、フレームが何個のブロックに分割されたかが求まります。
-
計算コストは探索半径の 2 乗に応じて増大するため、ウィンドウを広げるとコストは急速に高くなります。半径 7 では 225 箇所、半径 15 では 961 箇所、半径 31 では 3969 箇所のコストがかかります。
-
この 2 乗の増加関係こそが、高速探索法が存在する理由です。3 ステップ探索法は 9 点をサンプリングして位置を絞り込み、それを繰り返すため、225 箇所の代わりに 27 箇所で済みます。
-
コストは 8 倍安くなりますが、完全な等価ではありません。局所的最小値に向かって降下するため、誤差曲面に複数のくぼみがある場合、真の最良マッチを見過ごしてしまう可能性があります。
解答
ツールには、ブロック当たり225.0点、合計14400点を探索したと表示されます。ここに、実用的な動画符号化が抱えるトレードオフが凝縮されています。全探索は最適解を得られる一方、計算量が探索半径の二乗に比例するため、実際のエンコーダーは例外なくヒューリスティックを採用し、ときには劣る動きベクトルを選ぶことを受け入れています。誤った選択がもたらす負担の一端は、残差エネルギー（MSE）の行で確かめられます。不適切なベクトルほど残差が大きくなり、符号化すべきデータも増えます。高速動き探索は、ただ時間を節約するための近似ではありません。動きベクトルが不完全なために増えるビット数は、その計算資源を別の箇所に振り向けて節約できるビット数より少ない、という見込みに賭ける手法です。
-
参考文献 (2)
- Block matching and motion vectors as the standard uses them: T. Wiegand, G. J. Sullivan, G. Bjontegaard and A. Luthra, "Overview of the H.264/AVC video coding standard." IEEE Transactions on Circuits and Systems for Video Technology 13(7), 560–576, 2003.
- The diamond search this tool implements alongside full search: S. Zhu and K.-K. Ma, "A new diamond search algorithm for fast block-matching motion estimation." IEEE Transactions on Image Processing 9(2), 287–290, 2000.