FIT（情報科学技術フォーラム）2002

J-73
レートを最小とする予測器と算術符号を用いた画像の可逆符号化
Lossless Image Coding Using Minimum-Rate Predictors and Arithmetic Code白井規之∗

松田

Noriyuki SHIRAI一朗∗

伊東Ichiro MATSUDA

1. はじめに

Susumu ITOH

上式より，符号化対象領域 R において予測誤差 e の符号化に必要なビット数を，以下の情報量 I(R) で見積も我々は先に，レートを最小とする予測器を用いた画像データの可逆符号化方式を提案した [1]．この方式では，コンテクストモデリングに基づいた適応的なエントロピー符号化を前提として予測誤差の情報量を定式化し，ることができる．
X¡¢
log2 P (e) · ∆e
I(R) = −p0 ∈R

その値が最小となるように予測器を最適化することで高=−い符号化効率を実現している．しかし，エントロピー符log2 ² X e2(3)2 p ∈ σn20Rしている．このような重み付き 2 乗誤差の最小化により，2. レートを最小とする予測器の設計 [1]

領域 R に関する符号化レートを最小とする予測器 (予測画素 pk の輝度値を S(pk ) と表記したとき，注目画素係数 ak の組) が設計できる．実際には，画像を 8 × 8 画

p0 に関して線形予測を実行した際の予測誤差信号 e は次式で表せる．

素のブロック単位で M 通りのクラスに分類し，クラス毎の予測器の設計とクラスの更新を交互に繰り返すことで，ブロック単位の適応予測に適した予測器 (M 種類)(1)を求めている．なお，予測器の種類 M と予測次数 K の

k=1

値は画像サイズに応じて適切に設定している [3]．

但し，K は予測次数，ak は符号化済みの参照画素 pk (k =3. コンテクストモデリングと予測誤差の符号化

1, 2, · · · , K) に関する予測の重み (予測係数) である．K =20 次の場合の画素配置の例を図 1 に示す．本方式では符号化済み近傍画素の予測誤差を用いたコンテクストモデ
リング (後述) によって注目画素を 16 通りのグループのいずれかに分類し，対応するグループの確率モデルに応じた適応的なエントロピー符号化を実行している．ここで，グループ毎に観測された予測誤差信号 e の確率密度関数 P (e) が分散 σn2 (n = 0, 1, · · · , 15) のガウス関数で本方式では予測誤差 e の量子化代表値を，|e| が小さい順に割り当てられた非負の整数値 E (量子化インデックス) で表現し，この E に対してエントロピー符号化を適用している．可逆符号化では量子化ステップ幅が ∆e = 1となるため，8bit 精度の画像では E の値も 0 ∼ 255 の整数値となる [4]．また，予測誤差の絶対値 |e| とインデックス E の間には E ≈ 2 · |e| の関係がほぼ成立する．従って，各グループの e の確率密度関数が (2) 式のガウス関数で表せるとき，インデックス E の生起頻度も以下の片(2)側ガウス分布に従うと考えられる．
¶µE2Pn (E) = αn · exp − 28σnp(4)但し，αn は確率の和を 1 とするための係数である．文献pppppppppppppppppp[1] では，(4) 式と 16 通りの σn2 の値に基づいて，上記のインデックス E に対する可変長符号 Vn (n = 0, 1, · · · , 15)pを設計している．但し，各 σn2 の値は可変長符号 Vn の理論的な平均符号長が 2.0∼7.5 bits/sample の間で等間隔となるように前もって設定している．また，符号化済みの図 1 画素配置 (K = 20)∗+散 σn2 の逆数で重み付けされた予測誤差の 2 乗和に比例ンジコーダ [2] を導入し，上記問題の解決を図る．

モデル化できるものと仮定する．
¶µ1e2
P (e) = p· exp − 22σn2πσn2!

存しない定数であり，第 2 項は各グループに対応した分変長符号の代わりに多値算術符号化方式の一種であるレak · S(pk )

log2

∆e
p2πσn2自然対数の底を表している．上式の右辺第 1 項は e に依号化効率が大きく低下する場合があった．本稿では，可e = S(p0 ) −Ã

但し，∆e は予測誤差 e に対する量子化ステップ幅，² は報量が 1bit/pel 以下となるような単純な画像において符KXXp0 ∈R

号化部に画素単位の可変長符号を採用していたため，情p晋∗

近傍画素における E の和をしきい値 Th 1 , Th 2 , · · · , Th 15を用いて 16 レベルに量子化することで各画素のコンテ

東京理科大学 理工学部 電気電子情報工学科

347

FIT（情報科学技術フォーラム）2002

は文献 [5] の方式，
「JPEG-LS」は可逆符号化の国際標準1.0方式 [6] をそれぞれ表している．同表より，「Arith.」は実測値
P0 (E)「Huff.」に比較して平均で 0.072 bits/pel 低い符号化レートを達成している．特に，CG 画像である「Shapes」については符号量を 40% 以上削減することができた．これは，予測誤差が 0 に集中する領域において適切なモデリ0.5ングと符号化効率の改善が実現されたためであると考えられる．また「Arith.」を他の符号化方式と比較すると，「TMW」に比較して 0.009 bits/pel, 「JPEG-LS」に比較して 0.308 bits/pel それぞれ低い平均符号化レートを達成していることが確認できる．なお，図 2 からわかる
0.005

ように，画像によっては予測誤差の確率モデルがガウス

10E
図 2 E の頻度分布の例 (Shapes)関数で近似できない場合があり，これが本方式の符号化性能を低下させる一因となっている．今後は，一般化ガウス関数等を用いた適切な確率モデル [7] の導入やコン

クストモデリング (グループ分類) を実現しており，これテクストモデリングの高精度化について検討を加え，更により各グループに対応した可変長符号 Vn を画素単位なる性能向上を図る予定である．に適応選択することが可能となる．図 2 は，上記のコン

表 1 符号化レートの比較 (bits/pel)

テクストモデリングによって分散最小のグループ (n=0)

ImageAirplane
BaboonBalloon
Barb
Barb2
CameraCoupleGoldhill
Lena
Lennagrey
Noisesquare
Peppers
ShapesAverageに分類された画素について求めた E の頻度分布の例を示している．ここで使用した Shapes は単純なオブジェクトで構成された CG 画像であり，平坦部で E = 0 となる頻度が極めて高くなることから，想定した確率モデルP0 (E) との間に大きなミスマッチが生じていることがわ
かる．
4. 算術符号化の導入
上記の問題を解決するためには実際の頻度分布に応じた適切な σn2 の値を設定する必要があるが，1bit/sample以下のビット割り当てが原理的に不可能な可変長符号を用いた場合，σn2 の値が極端に小さいグループでは符号Arith.
3.643
5.708
2.641
3.888
4.282
4.071
3.495
4.256
4.323
3.941
5.386
4.251
0.994
3.914

Huff.
3.661
5.727
2.653
3.911
4.323
4.093
3.525
4.291
4.348
3.961
5.365
4.272
1.689
3.986

TMW
3.601
5.738
2.649
4.084
4.378
4.098
3.446
4.266
4.300
3.908
5.542
4.251
0.740
3.923

JPEG-LS
3.817
6.037
2.904
4.691
4.686
4.314
3.699
4.477
4.607
4.238
5.683
4.513
1.214
4.222の効率が大きく低下してしまう．そこで，本稿では情報[2] は実装が容易であり，また比較的高速な多値算術符号【参考文献】[1] 松田, 森, 前田, 伊東: 可逆符号化のためのレートを最小とする予測器の設計と評価, 信学論 (D-II), Vol.J85-D-II,NO.3, pp.448-456, Mar. 2002.

として最近注目を集めている方式である．本方式では，[2] http://www.compressconsult.com/rangecoder/

源の拡大を行うことなく柔軟なビット割り当てが可能な算術符号化の導入を図る．本稿で使用するレンジコーダ[3] 白井, 松田, 伊東: 画素/ブロック適応予測を用いた画像の可逆符号化, 信学技報, IE2001-233, Vol.101, No.722,
pp.9-16, Mar. 2002.

可変長符号の場合と同様なコンテクストモデリングを採用し，グループ毎に (4) 式で与えられる確率モデルとレンジコーダを用いて量子化インデックス E の値を符号[4] 谷口, 上倉, 伊東, 宇都宮: 高階調画像の可変長符号選択形可逆予測符号化方式, 信学論 (B), Vol.J70-B, No.6, pp.654663, Jun.1987.

化している．なお，(4) における σn2 の値は，各グループの理論的なエントロピーが 0.1∼7.0 bits/sample の間で[5] B. Meyer and P. Tischer: TMW ― a New Method for
Lossless Image Compression, Proc. of PCS’97，pp.533538, Sep. 1997.

等間隔となるように設定した．

5. 特性評価とまとめ[6] ISO/ITE 14495-1, Information Technology ― Losslessand Near-lossless Compression of Continuous-Tone Still
Images ― baseline, 1998.

計算機シミュレーションより求めた各方式の符号化レートを表 1 に示す．但し，「Arith.」は算術符号 (レンジコーダ) をベースとした方式，「Huff.」は可変長符号 (ハフマン符号) を用いる従来の方式 [1] である．また，
「TMW」

348

[7] 松田, 本橋, 伊東: 対象画像毎に予測器と可変長符号を反復最適化する可逆符号化, 第 1 回情報科学技術フォーラム(FIT) 講演予稿集, Sep. 2002.