動き推定

なんか似たようなことを自力で実装しようとしている人がいたので参考用に書いておく。
H.264ではブロックマッチングでQpelつまり、4分の1画素精度で動き推定を行う。そのための小画素の生成は以下の2段階で行う。

1. 6タップのFIRフィルターを用いて2分の1位置の画素を生成
2. 2タップの平均化フィルタを用いて4分の1位置の画素を生成

ここで6タップのFIRフィルタとは、左右ないしは上下各3つの6つの画素にある係数をかけて合計するフィルタです。例えば"ABCDEF"と画素があり、CD間の2分の1画素を予測する際は、次式のように計算します。

あとはSAD(差分絶対和)やSATD(差分にアダマール変換をしその結果の絶対和)やSSD(差分二乗和)を指標にしてブロックの動きベクトルを推定する。普通に考えたらSSDをメインに使いそうなものだがSADがメインなのは、大抵のCPUは専用命令を持っていてSADは高速に計算できるから。またこのときの探索法にもいろいろあって丸茂さんのサイトの過去ログ(Diary 2005-1)が詳しい。
基本的に動画圧縮で用いられる動き推定はブロックマッチングだが、ブロックマッチングだと拡大縮小や回転は対応できない。ブロックマッチング以外の動き推定法としては勾配法がよく使われている。勾配法は”物体上の点の明るさは移動後も変化しない”という仮定の下では以下の式が成り立つことを利用する。

ここでは位置における時刻における輝度(Y)を表す。これをテイラー展開し整理すると次式が得られる。

もし局所領域内で移動量が等しいと仮定できるなら、その領域内で先の式が最小二乗誤差となるようなを推定すれば良い。つまり、局所領域Rで以下の式が最小となるを求めることとなる。