« ディジタル神話 | メイン | デジタルトキワ荘とSNS »
2008年05月22日
吉里吉里 ムービー拡張日誌2:: JPEGの圧縮方法とハフマン復号化の高速化
Tweet @jin1016をフォローJPEG は、主に DCT、ハフマン符号、ゼロランレングスで出来ている。
JPEG でハフマン符号化を行うのは値そのものではなく、その値を表すのに必要なビット数。
ビット数のハフマン符号化行った後、その最低限必要なビット数で表した値を記録する。
値を直接符号化すると、パターンが多く符号が長くなってしまうが、ビット数であれば 10 までの値を符号化すればいいので短くて済む。
ハフマン符号化 ( エンコード ) は、ある値を別の値に置き換える作業。
これでなぜ圧縮できるかというと、出現頻度の高い値に短い符号を、低い値に長い符号を割り当てるため。
つまり、「あ」はいっぱいあるから 01 にしよう、「ん」はほとんどないから 00000000001 にしようという具合に値を置き換えていく。
こうすると、データの偏りが大きければ大きいほど圧縮される。
ランレングスは、同じ値が連続でつながっていた場合、その値が何個つながっているかを保存することで圧縮する方法。
つまり、「あああああああい」となっていたら、「あ 7 い 1 」というように保存する。
こうすれば元のデータより圧縮される。
ただ、連続していない場合は、データが増える。
JPEG では、ゼロの値についてのみランレングスで圧縮を行う。
なぜゼロかというと、離散コサイン変換 ( DCT ) を行い、量子化を行ったデータにゼロが多く含まれるから。
離散コサイン変換とは、周波数領域に変換する作業。
画像を離散コサイン変換し、高周波領域を削って元に戻しても、劣化があまりわからないことを利用して、圧縮する。
削るのは割り算で行う。
劣化がわかり辛い高周波領域ほど大きな値で割る。
割り算は整数で演算するので、小数点以下はなくなる。
圧縮率を大きくするということは、大きな値で割ることなので、ゼロが多くなる。
JPEG では、この割る作業を量子化と言っている。
元に戻す時は掛け算を行う。
当然小数点以下は失われているので劣化していて、元の値には戻らない。
ハフマン復号化 ( デコード ) は、ハフマン符号化で変更した値を元に戻す作業。
対応表に従って元に戻せばいいんだけど、符号値は可変長なので、まじめにやると1ビット読み込んで比較してなかったらもう1ビット読んで…… とちまちま比較していかないとならない。
圧縮率が高い = 短い符号が多いということなので、高圧縮のデータは数回読めば比較は終了する。
でも、そうでない場合は時間がかかる。
一般的な高速化方法はテーブルを使うこと。
まず最大長のハフマン符号ビット数分読み込んで、その値をインデックスとしてテーブルを引く。
テーブルには値とその符号のビット数を記録しておけば、すぐにわかる。
読み込みすぎた分は元に戻す。( 実際には、最初は参照し、ビット数がわかったらそのビット数分捨てるような作り。参照では読込み位置のポインタは進めない )
ただ、最大長のハフマン符号が大きい時はテーブルが大きくなってしまう。
JPEG では、16 ビットまであるので 65536 個のテーブルになってしまう。
64KB なのでメモリ容量的にはそれほど大きくはないが、テーブルが大きいと遅くなってしまう。
SIMD 拡張版 IJG JPEG library では、ある長さでテーブルを切っている。
つまり、先頭数ビット分のテーブルのみ持ち、持っている長さ分読み込んでテーブルを引く。
テーブルを引くと、その長さ以下の符号なのか、その長さでは足りない符号かわかる。
もし、足りなければそれ以降は1ビットずつ読み込んで比較していく。
ただ、長い符号はあまり出てこないはずなので、結果的にはほとんどテーブルを引くだけで済ませられると思われる。
ハフマン復号化はこの方法を使おうと思う。
もっと高速化できる方法があればいいんだけど……
投稿者 Takenori : 2008年05月22日 12:27
comments powered by Disqus