正確にはデコード時に行う逆演算の高速化ですが。
Predict Median というのは、以下の式によって予測値（と残差）を計算するものです。
V:実際の値 P:予測値
P(x,y) = median(V(x-1,y), V(x,y-1), V(x-1,y)+V(x,y-1)-V(x-1,y-1))
Predict Median では、あるピクセルの残差の計算は他のピクセルの計算に依存しないので SIMD 化は自明です。普通はベタッと並んでいるピクセルをメモリアドレス順にまとめて処理することになります。
一方、逆演算では他のピクセル（左、上、左上）の計算に依存するため、同じようにメモリアドレス順にまとめて処理することはできません。しかし、斜め方向に並んだピクセル群（下の画像の赤いピクセル）は互いに依存しないので、同時に計算することができます。ただし、斜めに並んでいると SIMD レジスタにロードして計算できないので、並び替えて計算します。並び替えた状態では、各ピクセルはそれより上の方にあるピクセルのみに依存することになります。このアルゴリズムは diagonal algorithm と呼ばれるようです（diagonal=斜めの,対角の）。
このアルゴリズムは昔から知られている（私も２年ぐらい前に聞いた）わけですが、Ut Video Codec Suite の ULxx には適用できません。Predict Median を実装する際に「手抜き」をして、左端のピクセルの予測値の計算が前のラインの右端のピクセルに依存するようにしてしまったためです。新しいフォーマットを導入することになったら、この点はうまく改善したいところです。
なお、別の簡単なフレーム内予測方式である Predict Left も逆演算は左のピクセルの計算に依存しますが、左端が右端に依存しないなら似た方法で高速化できます。ただ、元々計算が単純なため、エントロピー符号の復号時についでにやってしまうことで高速化した方が効率的です。ULxx でも実際にそちらの方法を採用しています。ULxx の Predict Left では Predict Median と同様に左端が右端に依存しているという都合もあるのですが。
no comment untill now