1月
18
誰かが「JPEG-LS を基にした可逆圧縮コーデックを作ろうかなー」と言っているらしい、という話を小耳に挟みました。ちょろっと調べた結果、フレーム内予測アルゴリズムは簡単に取り込めそうだったので、試しに取り込んでみると predict median と比較して最大で 1% 程度の圧縮率の改善が見られました。
さて、JPEG-LS のフレーム内予測アルゴリズムは以下のような式になっています。
a = (left)
b = (top)
c = (topleft)
predicted = min(a, b) if c > max(a, b)
max(a, b) if c < min(a, b)
a + b - c if otherwise
しかしこれをよーく見ると predict median と（表現が違うだけで）全く同じなんですね。predict median は以下の式です。
a = (left) b = (top) c = (topleft) predicted = median(a, b, a + b - c)
ここで、median() は中央値（引数が 3 つなので 2 番目に大きい値）を返す関数です。
じゃあなんで predict median と比較して圧縮率が変化するのかというと、Ut Video Codec Suite における predict median の実装では、上の計算は uint8_t で行っているからです。a + b – c は uint8_t の範囲からはみ出すことがあるので、その場合予測結果がおかしくなります（一般的には不適切な予測結果になる）。ちょっと他の実装を見たところ、Huffyuv では同じ問題が発生し、Lagarith では int に拡張してから計算しているので問題なし、のようです。
int16_t あたりで計算すればこの問題は発生しないのですが、最終的にはアセンブラコードを新規に書かなければならずめんどくさい＆処理量は確実に増えるのに対し、圧縮率の改善は上に書いたとおり 1% 程度であるので、あまり乗り気ではありません。少なくとも短期的には他のことをしたいですね。
JPEG-LSの式ですが、topleftが最大または最小のときmedianとは違った結果になります。topleftの反対側の値が選択されるかんじで。
いえ、同じです。
まず、式は a と b について対称なので、a >= b と仮定しても一般性を失いません。このとき、max(a, b) = a, min(a, b) = b となります。
c > max(a, b) = a の場合、a – c < 0 なので a + b - c < b で、つまり a >= b > a + b – c です。この時 median(a, b, a + b – c) = b = min(a, b) ですが、これは JPEG-LS の式と同じ結果です。c < min(a, b) の場合も同様です。 a = max(a, b) >= c >= min(a, b) = b の場合、a – c >= 0 なので a + b – c >= b で、同様に a + b – c < = a となり、合わせると a >= a + b – c >= b です。この時 median(a, b, a + b – c) = a + b – c ですが、これも JPEG-LS の式と同じ結果です。
うーん普通のテキストで書くと読みづらい。
すみません、predict median を median(a,b,c)と思いこんでました。
解説までしてもらって、つまらない結果で申し訳ないです。
ああやっぱり :-)