誰かが「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% 程度であるので、あまり乗り気ではありません。少なくとも短期的には他のことをしたいですね。

Trackback

4 comments untill now

  1. JPEG-LSの式ですが、topleftが最大または最小のときmedianとは違った結果になります。topleftの反対側の値が選択されるかんじで。

  2. 梅澤 威志 @ 2012-01-30 15:48

    いえ、同じです。

    まず、式は 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 の式と同じ結果です。

    うーん普通のテキストで書くと読みづらい。

  3. すみません、predict median を median(a,b,c)と思いこんでました。
    解説までしてもらって、つまらない結果で申し訳ないです。

  4. 梅澤 威志 @ 2012-02-02 13:47

    ああやっぱり 🙂

Add your comment now