SAD, SATD（メモ）

このページの全ては誤っているかもしれません。x264関連の記事に関してを読んでください。

この記事はメモです。質も量も不足しており、参考にするには荒すぎます。書きかけたはいいが留めておく場所がないので暫定で掲載しています。

SAD, SATD（メモ）

SADやSATDはx264のchangelogでも頻出の用語だ。これらは動き補償を行う動画エンコーダーでは基礎的な技法の一つで、主に動き探索に使用される。たまには解説をしてみることにしよう。

例えばあるピクセルの値が5だとして、補完元（参照先）となる似たピクセルを探したい。ここでは比較対象のピクセルが2つ、それぞれ10と2という値だとする。差が小さいほうがより「似ている」ことになるので、まずはそれぞれ差を求めるべく引き算してみると、5-10=-5と5-2=3という値が得られる(differences)。-5は3よりも低い値だが、ここで言う、差が「小さい」は「ゼロに近い」の意味なので、絶対値(absolute)に直して考える。するとabs(-5)=5>abs(3)=3なので、後者の3の計算の元になった、値2のほうが似たピクセルであるとわかる。この差分をブロック（典型的には16x16のマクロブロック）内の全てに対して求め、差分絶対値の合計(sum)を求めると、ブロック単位でどの程度似ているかの比較判断基準に使える値となる（もちろん小さいほうが良い）。

SATDというのはSADの単なる引き算による差分絶対値合計で比較基準値の算定を終わるのではなく、さらに一工夫がしてある方式だ。具体的には、アダマール変換等を用い、後々DCT等が行われた際の周波数ドメイン（最終的にCABACやCAVLC等のエントロピー符号化の対象となるもの）での差分に近しい基準値を得ようとする。

実用上は、例えばx264ではsubmeで動き探索（とか、ブロックのモード決定）にSAD/SATDのいずれが使われるかが決まる。比較対象（探索順）を決めるのがmeで、比較方法（とサブピクセル(fullpel/hpel/qpel)比較精度その他）を決めるのがsubmeだ。比較対象の選定が悪いといくら比較方法・精度が高くても無駄足になるので、meをあまり軽くしてsubmeを重くするのは効率が悪い。その意味でsubmeは、正にmeのsubなのだと言える。

実際の補完元（参照先）の選定には移動距離(mv)の符号化コスト（所謂mvcost）が考慮されたり、高submeではSATD以上の符号化効率を求めるRDOが使用されるので、ここで書いたほど単純な処理ではない。また、比較的低いsubmeからSATDは使用されるので、動き探索のために純粋なPCM値に対するSADのみを使うという状況は限られる。

蛇足だが、SADの結果がゼロであるブロックが所謂DirectMBであり、mvcostもゼロ（mvにも予測があるため単純に「動いていない」とは限らない）なブロックがスキップブロックだ。