パスワードを忘れた? アカウント作成
269620 journal

ttの日記: いまさらJPEG(その3) 4

日記 by tt
ということで、JPEGの可逆圧縮(ハフマン符号)部分における0xffエスケープの影響を見積もってみる。

まず前提となる話を簡略化して説明。JPEGでは、ご存知のとおり可変長符号を使って「量子化した後のデータ」を記録する。どのようなビット列にどの符号を割り当てるかはかなり自由に選べるが、たいていはハフマン符号にのっとって可変符号の割り当てを行う。ただし、実際にこの符号割り当てを使ってビット列を出力する際に、「8ビット単位で区切ったときに、8ビットすべてが1となる」部分があった場合、つまり、ダンプリストで見て0xffというバイトが発生した場合、その後に0x00を追加することが決められている(JPEGのヘッダ(マーカー)構造を示すための識別子として0xffを使っていて、それと区別できるようにするため)。

このため、理想的なハフマン符号にくらべて、微妙に「最適」な符号割り当てがずれてしまう。

超絶簡略化した例として、シンボルがABCDの4つしかなくて、それぞれの出現頻度が5:4:3:2だったとする。このようなシンボルに対する理想的な可変長符号の割り当て方は「どれも2ビット」「A:0 B:10 C:110 D:111」という割り当て方の二通りがありえる。どちらも平均ビット長は2となる。つまり

シンボル : 出現頻度 : 符号系1   : 符号系2
       A :   5/14   : 00 (2bit) : 0  (1bit)
       B :   4/14   : 01 (2bit) : 10 (2bit)
       C :   3/14   : 10 (2bit) : 110(3bit)
       D :   2/14   : 11 (2bit) : 111(3bit)

符号系1平均長=2(当然)
符号系2平均長=(5*1 + 4*2 + 3*3 + 2*3)/14=28/14=2

見てのとおり平均符号長的には符号系1,2のどちらでも同じく「理想的な符号」である。が、JPEGに限って言えば、エスケープの関係で実際には符号系1の方が有利になる。

符号系1で8bit区切りの位置に8bit連続の1が来るのは、8bit区切り位置から始まってDが4つ続いたとき。だいたい (2/14)^4 ぐらい。

一方、符号系2でこれが起きるのは…多分、区切り位置がそれなりにランダムに分散すると仮定してよいはず(←ここ自信なし)なので、 ((2/14)^3 + (2/14)^2*(3/14) + (2/14)^3*(2+3+4)/14 + (2/14)^4) / 3 = (29/3) / (2/14)^4 ぐらい。

つまり後者の方が29/3倍、エスケープが必要になり、結果、8 * ((29/3) - 1) / (2/14)^4 = 0.02888bit ほど平均符号長は長くなる。 純粋なハフマン符号では2bit/symbolだったので、1.4%程度の違いが出ることになる。

で、適当に乱数を使ってテストしてみたんだけど、ここまで大きな差がでることはなかった。なんでだろう。区切り位置がランダム、ってのが多分間違っているんでしょうね…とはいえ、だいたい0.6%ぐらいの違いは出る模様。

ということで、まとめると、このあたりをうまく使って後1%前後はJPEGファイルを可逆圧縮できるんじゃないかと期待しています。が、私の頭ではこのあたりを綺麗にモデル化してコードに落としこむ自信がありません。総当りか発見的手法による擬似最適解を出すのがやっとかなあ。まあ無限の長さのシンボル列を相手にしていない時点で、最適解という考え方からは外れてしまうのは当然なんだけど…

あと以下検証コード。アレ、こういうのをrubyでこれからは書こうと思ってたのに、またCで書いてしまった…

// ff00出現の影響測定

#include <stdlib.h>
#include <stdio.h>
int main()
{
    int n0, n1, nn0, nn1;
    unsigned int c0, c1;
    int i;

    c0=c1=nn0=nn1=n0=n1=0;
#define TRIAL 10000000
    for (i=0;i<TRIAL;i++) {
    int r = (int)(((double)rand()/RAND_MAX)*14.0);
    if (r < 5) {//r = 0;
        n0 += 2; c0 <<= 2; c0 |= 0;
        n1 += 1; c1 <<= 1; c1 |= 0;
    }
    else if (r < 9) {//r = 1;
        n0 += 2; c0 <<= 2; c0 |= 1;
        n1 += 2; c1 <<= 2; c1 |= 2;
    }
    else if (r < 12) {//r = 2;
        n0 += 2; c0 <<= 2; c0 |= 2;
        n1 += 3; c1 <<= 3; c1 |= 6;
    }
    else {//r = 3;
        n0 += 2; c0 <<= 2; c0 |= 3;
        n1 += 3; c1 <<= 3; c1 |= 7;
    }
    if (n0 >= 8) {
        n0 -= 8;
        nn0 += 8;
        if (((c0 >> n0) & 255) == 255) {
        nn0 += 8;
        }
    }
    if (n1 >= 8) {
        n1 -= 8;
        nn1 += 8;
        if (((c1 >> n1) & 255) == 255) {
        nn1 += 8;
        }
    }
    }
    printf("%d vs %d\n", nn0+n0, nn1+n1);
    return 0;
}

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • 実際にはffの出現しうる符号を生成するとしても、とりあえず、ffを発生しない符号を仮定すると、出力データの8ビットの情報量がどの程度になるでしょうか?

    本来256通りの表現が出来る量が、255通りに減るわけですから、その情報量の比率は

    log(255)/log(256)=0.99929417960…

    と言うわけで、出力データ列に含められる実質的な情報量は0.07%減少します。

    一方、それを考慮しないでffの後に1バイト追加される場合、出力符号ビット列が00~ffまでをほぼ均等確率で出力するとしたならば、出力データは 257/256 倍になります。
    このデータ増加率は約 0.39%です。

    と言うことは、大雑把に言っておおよそ 0.32% しか改善しないってことじゃないでしょうか?

    もし、0.6%改善したとしたら十分立派では?
    (と言うか、局所的な偏りを無視すれば、削減率は必ず約0.39%未満になるのでは?)
    • by tt (2867) on 2010年11月03日 1時04分 (#1852259) 日記
      ああなるほど。もう一つのコメント(taka2さんのコメント)に書いたように、ちと前提条件を間違えていたんですが、 それでも逆に言うと「平均して」0.3%ぐらいは改善できると期待が持てそうです。

      平均情報エントロピーと同じビット数になる符号割り当てができれば、 完璧に「出力符号ビット列が00~ffまでをほぼ均等確率で出力」が出来るのですが、 残念ながらJPEGで使う一次元のハフマン符号では1シンボルに割り当てるビット数を1ビット単位でしか変化させられないので、 これを成り立たせることが出来ません。 無限次元のハフマン符号、算術符号とかレンジコーダー使えば別なんですが…

      たぶん、この辺の関係で改善率をより「大きくできてしまう」(今現在のアルゴリズムだと損している)のではないかと期待しています。

      --
      -- Takehiro TOMINAGA // may the source be with you!
      親コメント
  • by taka2 (14791) on 2010年11月02日 14時31分 (#1852003) ホームページ 日記

    JPEGに関する符号化の効率というのは面白い着目点だと、1からずっと読んでたのですが…

    > 多分、区切り位置がそれなりにランダムに分散すると仮定してよいはず(←ここ自信なし)
    ここ、一様じゃないですね。大雑把に、符号A(1ビット)を出力する確率が高い分、8bit区切り位置ちょうどから符号が始まる可能性は高くなると思います。

    で、ちょっと考えてみたのですが、
    まず、出力長がnビットな符号出力をする確率p(n)は、符号A~Dを出力する確率p(A)~p(D)を用いて
    1ビット出力する確率p(1)=p(A)=5/14
    2ビット出力する確率p(2)=p(1)×p(A)+p(B) = (5×5+4×14)/14^2=81/14^2
    3ビット出力する確率p(3)=p(2)×p(A)+p(1)×p(B)+p(C)+p(D)=(81×5+5×4×14+3×14^2+2×14^2)/14^3=1665/14^3
    4ビット出力する確率p(4)=p(3)×p(A)+p(2)×p(B)+p(1)×(p(C)+p(D))=(1665×5+81×4×14+5×(3+2)×14^2)/14^4=17761/14^4
    5ビット出力する確率p(5)=p(4)×p(A)+p(3)×p(B)+p(2)×(p(C)+p(D))=(17761×5+1665×4×14+81×(3+2)×14^2)/14^5=261425/14^5
    …以下略
    と表されます。

    次に、1バイト出力直後のビットバッファの状態を考えます。
    取り得るパターンは以下の5通り

    a)ビットバッファの長さは0ビット
    b)ビットバッファの長さは1ビット、内容は0 ←直前の出力は「7ビット目から符号B」もしくは「6ビット目から符号C」
    c)ビットバッファの長さは1ビット、内容は1 ←直前の出力は「6ビット目から符号D」
    d)ビットバッファの長さは2ビット、内容は10 ←直前の出力は「7ビット目から符号C」
    e)ビットバッファの長さは2ビット、内容は11 ←直前の出力は「7ビット目から符号D」

    ここで、p(a)~p(e)を基に、次のバイト出力後にa~eの状態になる確率pn(a)~pn(e)を考えると、

    8bit出力(状態aから8bit出力、状態bまたはcから7bit出力、状態dまたはeから6bit出力)した場合に、次状態がaになる
    pn(a) = p(a)×p(8) + (p(b)+p(c))×p(7) + (p(d)+p(e))×p(6)

    7bit出力(状態aから7bit出力 または 状態bまたはcから6bit出力 または 状態dまたはeから5bit出力)した後、符号Bを出力した場合、および
    6bit出力(状態aから6bit出力 または 状態bまたはcから5bit出力 または 状態dまたはeから4bit出力)した後、符号Cを出力した場合に、次状態がbになる
    pn(b) = (p(a)×p(7) + (p(b)+p(c))×p(6) + (p(d)+p(e))×p(5)) ×p(B)
            + (p(a)×p(6) + (p(b)+p(c))×p(5) + (p(d)+p(e))×p(4)) ×p(C)

    6bit出力(状態aから6bit出力 または 状態bまたはcから5bit出力 または 状態dまたはeから4bit出力)した後、符号Dを出力した場合に、次状態がcになる
    pn(c) = (p(a)×p(6) + (p(b)+p(c))×p(5) + (p(d)+p(e))×p(4)) ×p(D)

    7bit出力(状態aから7bit出力 または 状態bまたはcから6bit出力 または 状態dまたはeから5bit出力)した後、符号Cを出力した場合に、次状態がdになる
    pn(d) = (p(a)×p(7) + (p(b)+p(c))×p(6) + (p(d)+p(e))×p(5)) ×p(C)

    7bit出力(状態aから7bit出力 または 状態bまたはcから6bit出力 または 状態dまたはeから5bit出力)した後、符号Dを出力した場合に、次状態がeになる
    pn(e) = (p(a)×p(7) + (p(b)+p(c))×p(6) + (p(d)+p(e))×p(5)) ×p(D)

    この漸化式を解くと… 代数的に解くのが面倒くさいので、適当に計算させてみました。
    p(a)=1,p(b)=p(c)=p(d)=p(e)=0からスタートして5回ほどのループで
    p(a)=0.5,p(b)=0.25,p(c)=0.071428571,p(d)=0.107142857,p(e)=0.071428571 に収束。
    推測ですが、p(a)=1/2,p(b)=1/4,p(c)=1/14,p(d)=3/28,p(e)=1/14 かな?

    このp(a)~p(e)を基に、8bit全部1なバイトを出力する確率を求めると、
    状態aからDDC/DDD を出力、状態cからDDB/DDC/DDDを出力、状態eからDDを出力 した場合に8bit全部1になるので
    p(a)×p(D)×p(D)×(p(C)+p(D)) + p(c)×p(D)×P(D)×(p(B)+p(C)+p(D))+p(e)×p(D)×p(D)
    =(7×2×2×(3+2) + 1×2×2×(4+3+2) + 1×2×2×14)/14^4
    =232/14^4 = (29/2)/(2/14)^4
    となります。つまり、パディングの発生する確率は符号2の方が符号1より29/2倍高い

    あとは、
    > 結果、8 * ((29/3) - 1) / (2/14)^4 = 0.02888bit ほど平均符号長は長くなる。
    この計算が変じゃないでしょうか。
    符号1の「 (2/14)^4 」や符号2の「29/3×(2/14)^4」は、「1バイト=8bitが全部1になる確率」という、バイトあたりの確率です。
    一方、その1バイトには平均して4符号入っているわけですから、
    「1符号あたりの、パディングが発生する確率」は、その1/4です。
    あとは、29/3の代わりに上述の29/2って結果を入れると、

    符号1では、「8×(2/14)^4/4」=0.0008330ビット
    符号2では、「8×(29/2)×(2/14)^4/4」=0.01208ビット
    の差で、平均符号長は0.01125bitほど長くなることになります。
    符号1出力と比べた、符号2出力のデータ量増加率は(2.01208/2.0008330)=+0.562%

    ちなみに、私のとこで実行した場合は
    % ./test
    20007944 vs 20123712
    となりました。
    符号1:実験2.0007944bit(理論値 2.0008330ビット)
    符号2:実験2.0123712bit(理論値 2.01208ビット)
    というわけで、上述の理論値とほぼ一致してるかと思います。

    • by tt (2867) on 2010年11月03日 1時01分 (#1852258) 日記
      うお、すげー。「一様に分布はしないか、そりゃそうだな」というところまで昨日寝る直前に気づいて、どのぐらい偏るか見積もろうと寝床でフェルミ推定しているうちに羊数えている状態になって寝てしまいました。

      なのですが、悲しいお知らせです。

      よーくかんがえるとハフマン値で記録されるのは「量子化されたスペクトラム強度値のビット数(と、ゼロのランレングス長の組み合わせ)」であって、このハフマン値の後に実際のスペクトラム強度値がくるため、そもそもこういう計算ではなりたたないんでした…

      --
      -- Takehiro TOMINAGA // may the source be with you!
      親コメント
typodupeerror

私はプログラマです。1040 formに私の職業としてそう書いています -- Ken Thompson

読み込み中...