2値算術符号による画像情報の圧縮符号化
半 田 志 郎Binary Arithmetic Coding of Images Shiro HANDA
ー̲ J h ei ma g eha sahu gea mo un to fda t a.Soahu gea mo un to fme mor yd e vi c ei s n e c e s s a r yf o rs t o r a ge . Ⅰ nt hi sp a p e r ,wep r o pos eano ve la ppr o a c ht oda t ac ompr e s s i on o fi ma ge s .Us ua l l ymul t i ･ l e ve lda t as uc hasi ma gei se nc ode dbymul t i ･ l e ve le nc o de r whi c hha sve r yc o mp l e xs c he me .Wede c o mpo s e damul t i ･ l e v e lou t c o mee mi t t e df r o m t h es o u r c ei n t obi n a r yl e t t e r s . The nt h ed a t aofbi na r yl e t t e r si se n c o de dd i r e c t l ybyt he bi na r ya r i t hme t i ce n c o d e rwhi c hi sve r ypo we r f ulf o rc ompr e s s i ono fda t a. Anada p t i v e s c be mef o rd a t awi t hunkn o wns t a t i s t i c sa ndMa r ko f fmod e lc o °i n gs c he mef o rr e mov‑
i n gr e du n da n c ybyc o 汀e l a t i o nbe t we e nn e i ghbo r i n gp i xe l si sc o ns i d e r e d . Wes howt he p e r f o m a nc ef o rva r i o ust y pe so fi ma ge .
1 . ま え が さ
画像信号は膨大なデータ量を持 ってお り,そのまま記憶す ると膨大な記憶容量を必要 とす る.更に高精細 な画像が求め られる今 日では,扱 うべ き画像のデータ量 は,記憶装置の大容 量化の進歩にもまして増加の一途を辿 っている.
一方,画像信号は一般的に隣接す る画素 の輝度 に類似性が高 く,周波数スペク トルが低域 に集中しているなど,データ量の割合には情報量が少ない とい う見方もできる. このよ うな 統計量を利用 して画像を符号化す る方法には,大別 して
2
つの方法がある.一方は画像信号 を歪みな く再現することが可能な無歪み符号化法であ り,他方は人間の視覚効果を利用 して 目立たない程度の歪みを許す有歪み符号化法である.テレビ会議等の一過性の画像 の場合 に は後者の方法が適用 されるが,データべ‑ス等に格納す る写真 データの様 に,再生 した後 じ っくり吟味す るとい うような用途 には無歪みの符号化法が使われる.本論文では,無歪み符号化法を
2
倍算術符号 を用いて実現す る.算術符号 は可逆性,漸近 的最良性が保証 されているなどの特長 を持っ強力な符号である.更 に,入力データの確率パ ラメータを求めるモデル化部 とそのモデルに基づ く符号化部が明確 に分離可能であ るとい う 大 きな特長がある.画像データを符号化する場合,通常 は一つのデータを単位 として符号化す る(1). ところが 算術符号(2)の使用を前提 とした場合,画像 のよ うに多値 の情報源 (通常
2 5 6
倍以上程度 の値 を取 る)を扱 う算術符号 は,符号化過程において多 くの演算を必要 とし,アルゴ リズ ムも複'本研究の一部は,浅間テクノポt)ス,長野県テクノ‑イラソド開発機構の援助による.
= 電気工学科 助教授
1 2 半 田 志 郎
維 となる･また,同一の演算器 を用いる場合には
･ 2
値算術符号化 と比べ,アルファベ ット の個数分だけ区間の分割が必要 となるため,結果 として演算精度が低下 した ことにな り,圧 縮率の低下をもた らす と考えられる.以上の認識 に立 って,本論文では
2
億算術符号 による画像の高能率符号化法を検討 し,更 に実際の画像データに対 してその性能を検討 している.まず,多値情報源を2
値 の成分を持 つベク トル として表現 し,それ と同時にその確率分布 を2
倍情報源の確率分布 を用いて表現 す る. この分解 した確率分布 により,多値情報源が効率 よく符号化できることを示 し, さら に情報源が定常エルゴ‑ ド的 と考 えられ るならば,分解によるロスなしに2
値算術符号で容 易に符号化で きることを示す.次 に画像信号を多重のマル コフ情報源でモデル化 して,画素 間の相関を取 り除 く方法を示す.その際,情報源を記述するパ ラメータが多 くな りす ぎ,符 号化効率が低下 してしま うとい う問題を状態の縮退 とい う考 え方を用いて解決 している.2.
算 術 符 号一般 に圧縮符号化 とは,生起確率の大 きな系列 に短い符号語を,生起確率の小 さな系列 に 長い符号語を割 り当てることによって,平均の符号長 (送 るべ き符号の平均の長 さ)を最小 にしようとす る方法である.算術符号 もこの様 な考え方に則 った方法であるが,符号化が四 則演算 と,数の大小比較 によって行われるため,その名が付けられている. ここでは簡単の ため
, 2
値〈
0,1)のデータ系列を2
値 のデータ列 に符号化す る方法を示す ことにす る.一例 として
,0, 1
の生起確率が1 / 3, 2 / 3
のデータ列の符号化 を考 える.まず区間[ 0 , 1
)を 図1
のように0, 1
の生起確率に従 って2
つの区間 に分割す る (多値情報源の場合 には,多値 数の数だけの区間に分割す る).初めのデータが 0であれは下側, 1
であれは上側 を選ぶ.この時
, 0
に割 り当て られた区間[ 0, 1 / 3 )
は先頭 が 0のデータ列 の累積確率 を示 し,[ 1 / 3 , 1
) は先頭が1
のデータ列の累積確率を示す ことになる.次 に,選 ばれた区間を再 び生起 確率に従 って分割 し,次の入力データに従 って区間を選ぶ.以下同様 にして区間を選択 して ゆ く.図1
は入力データが｢ 1 1 0
｣の場合 の例である. この時,最終的に どの区間が選 ばれ入力データ
1
l n
I ) 5 ′ 9 1 / 3
⇒ 1 : : ; 7
図
1
算術符号の原理たかを伝送すれば,受信側で も同様の分割方法 によりどの区間が選 ばれているかが分かるの で,一意 に復号化が可能である. この区間を示すためには,その区間内の数値の代表値 を小 数点以下
‑l og 2 ♪( 11 0 )
ビッ ト以上の最小の長 さの2
進数で表わせ ばよい ことが,シ ャノン の第‑定理か ら容易に分かる.また, この事か ら平均符号長が情報源のエン トロピーに漸近 す る事 も分かる. ここで,I ) ( 1 1 0 )
は系列｢ 1 1 0
｣の生起確率であ り,斑1
でいえは最終的に 選 ばれた区間の幅 に等 しい.容易に分かるように,生起確率の高い系列 ほど選ばれる区間の 幅が大 きくな り,短い符号語 が割 り当てられる.また, このアルゴ リズムにおいて,区間の 幅は符号化が進むにつれて狭 くな り,精度 の高い演算が必要なように思われるが,浮動小数 点演算の考え方を用いれば固定精度の演算で十分である. さらに区間の分割 は送信側 と受信 側で同期 していれば変更 して もかまわないので,適応的符号化 は容易である.3.
多値情報源の符号化3.1
確率分布の分解表現多値情報源Ⅹか らの出力系列
X
.tが2
n個の値を取 り得 るもの とす ると,X
.･はX . ･ ‑ (
xE, 0 , X.
1,1,‑ , X. , . n̲1 )
(1) とベク トルで表現できる. ここで,
x .･.Jは 0または1
のみの値 をとるものとす る.この様 に表現 した ビット列 は,多値情報源Ⅹが定常的であるならば,明 らかに ブロック定 常 とな り,各 ビットはそれぞれ異なった確率分布 を持つ ことになる.また,文字 の コー ド表 現 の様 な場合 には, ビット位置による重要度の様 なものはないが,画像情報 のように輝度 レ ベルを表 した数値 の場合 には,上位 ビットほど重要な意味を持 っているので,符号化 におい て もそのような構造を保持 したまま取 り扱 うことが望 ましい.
X
Lの出現確率♪( X. ･ )
はこのベ ク トル表記に対応 して,b(X , ･ ) ‑ ♪( x
E,0 , X.
1,1,･･ ･ , X, . n̲1 )
‑ b( x, A . o ) b( x, . , . I xE . 0 ) b( x( , 2I x
,I.. , x, ･ ,
1)
･･ . b( xt J̲ 1l
x,I . 0 , X
,I. 1 ,
･･ ･ , X, ･ . n̲2 )
(2) となる. ここで,b(･ト)は条件付確率を示す. この表現 によると,X
,.の符号化 はb( X, ･ ) 自
身を用いて多値で行 う必要はな く, 2
倍情報の条件付確率分布を用いて, 2
倍算術符号で行 えばよい. また, この分解 によってエン トロピー (符号化 の限界 を示す)の変化 はないの で,分解 によるロスは無い. また,情報源 を記述す るパ ラメータの数が不変であ ることも, 容易に確かめ られ る.例 えば,情報源X E が2 5 6( n ‑ 8)
値 の値 を取 り得 るもの とす る と,上 の分解 で, P( xz ･ .
.)
の記述 に1
つ,b( x. I . ,I x, . , . )
に2
つ,以下4,8
,･･････ ,1 2 8
,合計 で255
個 の パ ラメータとな り,256
倍情報源を記述す るのと同一である.次に情報源をマルコフ情報源によってモデル化す る場合には,ある時点での出力は以前 の 出力系列 に依存す ることになる.す なわち,以前の出力系列 によって決 まる状 態 S,.によっ て現在 の出力
X
,･が左右 され る.従 って,出現確率 も条件付 き確率b( X
l･lS.･)を用いて示 さ れ る. これ も式( 2 )
と同様 にして,1 4 半 田 志 郎
b( X, l S, A ) ‑ b( x
,･. . ,
x.･,I,･･･ , X . ･ , n ̲ I J S, . )
‑ b( xL , ｡I S I ･ )b(
x.･. 1 l x
,･,0 , S. I ) p( x. ･ , 2F x
zl.0 , X
,･, 1 , SL ) ･ ･ ･ b( xL , A ̲ 1 J x
,A.0 , x
.I
,1,･･ ･ , X. I . n
̲2 , S
,･)(
3) と分解す ることによって,2
値算術符号で容易に符号化で きることが分かる. この場合 も, 情報源を記述す るパ ラメータ数は,多値情報源をそのまま記述す るのと同一である.3.2
適応的符号化一般 に, これか ら符号化 しようとす る情報源の確率分布が既知であることは稀である.そ のような場合 にも効率 よく符号化を行 うため,次の
2
つの方法が考えられ る.(1)静的符号化法 確率分布 を調べ直 して, これ を受信側へ送 った後 に符号化を行 う方
法.
( 2 )
適応的符号化法 データが入って くる度に確率分布 を更新 して,常 にその時点で推定 できる最良の確率分布 を用いて符号化を行 う方法.情報源が定常エル ゴー ド的であれば,上記の
2
つの方法 は理論的に同一の符号化効率 を達 成す ることが知 られているが(3),(1)の方法は情報源を一度先読み して確率分布 を求める必要 があるため,現実的には,データの2度読み といった操作が必要 とな り,符号化速度 の点で も不利である. また,設定 したモデルのパ ラメータをすべて受信側へ送 らなければならない ので(4),モデル設定 の難 しさも直接効いて くることになる.す なわち,大 きなモデルは情報 源 をよくモデル化す るがそのパ ラメータを表示す るのに多大の情報量が必要になる. これに 比べ,(2)の方法 はデータの 2度読みの必要 もな く, また多少大 きなモデルを設定 しても,パ ラメータ推定 においてモデルの使用 しない部分には到達 しない といった簡単な自動調整機構 が作用す るので,それほどモデル設定の難 しさが効いてこない とい う利点があ る.そ こで, 本論文でもこの適応的符号化法を用いることにす る.図 2
に示す深 さ nの木を考 える.右の枝 は入力情報の 1,左の枝 は 0に対応 し,各校 には カウンターが一つずつ付いている. この木を用いて符号化を行 う.符号化法 :
[1] x,,に対 して式(1)の分解 によってx ,･Jを得 る.
[2]
ポインタをr oo t
に移 し (k‑ 0),i‑0とす る.0 く 一
一････.■ー1
0 (root)図
2
符号化の木[3]
x .･,,･をポインタkで示 され る2
つ の枝 のカウン ト値ch( 0), ch( 1
)に よって算術符号化 す る.[4]
cA( x , ･ .,A)‑ Ch( x. 1 , , ･ ) + 1
[5]
x ,I,,･が 0な ら左下, 1
な ら右下 の ノー ドにポインタを移す.[6]j‑ n
‑1
な ら終了. そ うでなけれ,j‑i+1
として[3
]へ以上 の符号化 において,木 が一段深 くなることは,一つ条件 が多 く付いた ことを意味 し, 式
( 2 )
の確率分布 の分解表現 とよ く対応 しているのが分か る. さらFF･,数値情報 の よ うに上位 ビッ トと下位 ビッ ト亭重みが違 う場合 も,木構造 の根 に近 い重要 な部分 ほ ど多 く通過 す るの で,確率分布 の唆昧性 がな くな り,従 って真の確率分布 に近 い確率 で符号化 で きる. また, 各 ノー ドkでの算術符号化 においては,♪k( 0)‑ ch ( 0)+
1ch(
0)+ch(1)+ 2bh( 1 ) = 1lbh ( 0 )
として符号化 を行 ってい る. これ は,連続 の法則
( Th el o w o fs u c c e s s i o n)
と呼 ばれ(5),C々( 0)+cA( 1
)回の観測 の後 に,次 の出力 が 0また は1
で あ る確率 の期待値 が上式 で与 え ら れ ることに基づいている.す なわ ち,真 の確率分布 の最良 の予測 になってい る.4.
画 像 の モ デ ル画像 は隣接す る画素間 の相関が強いので, これを利用す るとさらに圧縮率の向上 が期待 で きる. この よ うな相 関 を確率過程 としてモデル化す るの に, マル コフモデル が よ く使 わ れ る. ところが,画像 は
2
次元情報 であ るため, モデル化 の仕方 に よって圧縮率 が大 き く異 な る.本論文で は,次 の3
種類 のマル コフモデルを検討す る.モデル
1:1
次元 マル コフモデル画素Y ,･.Jが左直前 の画素Y ,･,j̲1に依存 してい る.
表 1 実験に用いた画像デ‑メ
図
3
スタンダー ドサンプリングファイル 内 容
C Ompr e S S gi r l
女性上半身像2 2. 3 5%
c o upl e
男女二人全身像3 0. 31 %
ae r i al
航空写真0. 0 0 %
moon
月面写真7. 0 6 %
c he s t
胸部 レン トゲン写真3 2. 1 1 %
f a c s
ファックス原稿写真4 3. 9 9 %
gi r 1 2
女性上半身像1 5. 4 2 %
a r e a
航空写真1 0. 6 5 %
ba r ba r a
縞模様の服の女性像1. 2 4 %
mandr i l
l マン トヒヒ顔面像0. 0 0 %
1 6 半 田 志 郎
モデル2:2
次元マル コフモデル画素Yl･J,が左直前の画素Y ,･J̲1と真上 の画素Y,I̲lJ.に依存 している.
モデル 3 :スタンダー ドサンプ リング 2重マル コフモデル
画像を図
3
に示す曲線の順番にサンプ リングした場合,ある時点での画素値 がその直 前の2
画素に依存する.以上のマル コフ情報源モデルを適用す る場合 には
,3. 2
節で示 した符号化 の木 を状態の数 だけ用意 し,各状態で別々の木 を用いて符号化を行 う. ところが,画像のように多値( 2 5 6 )
の値を取 る情報源をこのようなモデルで符号化す ると,符号化 の木 の数 はモデル1
で2 5 6
, モデル2, 3
で65 5 3 6
と非常 に多 くな り,■その結果各符号化の木 におけるカウンタの値 は希 薄 とな り過 ぎて,確率分布の推定が暖味にな り,圧縮率が低下 してしま う.そ こで,本論文 では状態 として参照データの上位数 ビットのみを用いることにす る. これは,本来 のマル コフモデルに対 して,状態縮退 したモデルを用いていることになる.
5.
符号化実験及び考察電子計算機上 に前章 までに述べた符号化器を作成 し,符号化 シ ミュレーシ ョンを行 った.
表
1
に資料 として用いたデータの大 きさ と種類 を示 してい る.画像 データは,SI DBA
とI SO
の標準画像か ら選 んだ様々の画像である.gi r l 〜f ac s
が2 56×2 56 ,gi r
12
以降が51 2×51 2
の白黒画像である.また,輝度 は8
ビットで表 されている.符号化性能の評価 は,次式の圧 縮率を用いて行 う.圧縮率 ‑半
( 6 )
ここで
,
Sは原画像のデ‑タ皿,
Cは圧縮後のデータ丘であ る.すなわち,符号化によるデ ータの減少の割合を示 しているので,大 きいほど良好な圧縮が行われていることを示 している.
図
4
は本論文で提案 しているビット中位の符号化 とバイ ト中位 (サンプル単位)の符号化 の圧縮率を比較 した ものである.なお,符号化 はモデル1
である.状態数 ([2
]のように 示 している)が少ない場合には,それ程大 きな迎いは見 られないが,状態数が増 えて くると ビット単位符号化の方が良好 な圧縮率が得 られている. これは,バイ ト単位符号化では2 56
倍の うちのい くつ とい う形で確率分布が取 られるが, ビット中位符号化では符号化の木か ら 分かるように,上位 ビットか ら2
つの うちのどちらか とい う形で確率分布が取 られ るので, 特に状態数が多い ときに確率分布 の暖昧性が少な くなっているか らと考 えられる.図
5
にモデル1
における状態の ビット数 と圧縮率の関係を示 している.最大の圧縮率を示 す状態のビ ット数があることに気がつ く. これは,状態の ビット数があま りに小 さい と,モ デル自身が的確 に表現できなくて圧縮率が低下 してしまい,あま り大 きい と今度 はモデルを 妃述す るパ ラメータがきちんと表現できな くなってしま うことにある.すなわち,モデル自 身の規校があま りにも大 きくなると,表現すべ きパ ラメータ数が非常に多 くな り,データ数 が追付かな くなってしま うためである.モデル1
の場合 は,直前の画素の上位4
ビッ トか ら6
ビットな状腿 とみて符号化を行 うのが最 もよい.yj2
にモデル2. 3
の圧縮率を示 している.表2
において,[ 5, 2]
とあるのは,左直前および真上 の画素 の参照す る ビッ ト数 を並べ て示 してい る.モデル
3
において も,直前 お よび その前 の参照画素 のビット数を並べ て示 してい る.モデル
2
においては,一部 の画像 を除いて,左直前 の画素 の ビッ トを多 く参照す るモデル の方 が高い圧縮率が得 られ てい る. これは,画像 の入力装置 にも依存す ると思わ れ るが, ほ とん どの画像 で横方向の相関が多少大 き くなる傾 向があ るため と考 えられ る.モデル ･
1,2,3
を比較す ると,画像 に よって最適 なモデル及 びパ ラメータが異 な ってい る. これ は,画像 の縦横 の相関係数の違い及 びその大 きさの違 い等 に影響 され る為 と考 え ら れ る.表 1に
,UNI X
の標 準圧 縮方式 として提供 され てい るc ompr e s s( LZW
符号 化法(6)) コ マン ドの圧縮率 が示 されてい る.LZW
法 は,文字 の連続 パ ターンを符号化す る方法 であ る ため,相 関の高いデータに対 しては非常に強力 のはずであ る.本論文で提案 した方法 は,敬0. 6 0. 5 0. 4
芸 臥3 出 0. 2 8. 1
0
【 C I 】 【 1 】 【 2 】 【 3 】 【 4 】 【 5 ] 【 6 】 【 7】 【 8 ]
状 態 の ビッ ト数口 g l r l :
B +g i r l ; 1 0b a r b a:
e Ab a r b a:
1 Xf a o s :
a Vf a e s : 1 図 4
ビット単位符号化とバイ ト単位符号化の比較l e ] 【 1 】
【2】【 3 】 亡 4 ] 【 5 】 【 d]
[7コ【 8 】
状 態 の ビッ ト数口
暮 I r l
+a e r l z L I
O TtXn▲ f z L O
S X暮 l r 1 2
Vb z L r t Wa
図5
状態のビット数 と圧縮率の関係1 8 半 田 志 郎
表
2
各モデルに対する圧縮率[ 4, 2 ]p . [ 4, 4] [ 4, 6 ] [ 5, 2 ] [ 5, 4] [ 5, 6 ] [ 6, 2 ] [ 6, 4] [ 6, 6 ] gi r l 43. 6 8 % 4 3. 5 0% 4 2. 0 2% 4 5. 2 0 % 4 4. 27% 41. 6 4% 4 5. 1 8% 4 3. 6 4% 4 0. 0 6 % coupl e 4 2. 3 4 % 4 2. 00% 4 2. 5 5 % 4 5. 0 5% 4 4. 09% 4 3. 0 ̲ 7% 4 6. 3 7% 4 5. 0 6% 4 2. 6 3 % aら r ial 2 3. 8 0 % 2 3. 1 6% 21. 3 5 % 2 4. 0 7 % 2 3. 06% 2 0. 7 8% 2 3. 6 2% 2 2. 2 4% 1 9. 51 % moon 30. 7 0 % 31. 41 % 3 0. 7 2 % 3 1. 2 8 % 31. 5 8% 30. 38 % 31. 1 2 % 31. 1 0 % 2 9二 3 6 % c he s t 43. 9 3% 41. 32% 3 6. 7 0 % 4 2. 82 % 3 9. 43% 34. 0 8% 41. 2 2% 37. 1 1 % 31. 2 2%
f ac s 51. 2 8 % 5 2. 31 % 5 3. 8 6 % 5 1. 7 6% 5 2. 7 4% 5 4. 0 2% 5 4. 3 7% 55. 0 5% 5 5. 01 % gi r 1 2 3 6. 1 6% 37. 60% 3 8. 5 2% 3 8. 3 8% 39. 0 6% 3 9. 0 9% 3 9. 0 2% 3 9. 3 9% 3 8. 9 4 % ar e a 2 9. 2 8% 2 9; 5 9% 2 8. 8 8% 2 9. 9 5% 2 9. 9 4% 2 8. 71 % 2 9. 8 2% 2 9. 5 4% 27. 9 4 % bar bar a 23. 8 3% 2 5. 1 2% 2 6. 1 5 % 2 5. 2 2 % 2 6. 29% 26. 4 7% 2 5. 5 3% 26. 41 % 2 6. 2 8%‑
mandr i l l 21. 4 8% 21. 67 % 2 0. 7 1 % 2 1. 6 9 % 21. 62% 2 0. 31 % 21. 4 3% 21. 0 9% 1 9. 47 %
[ 4, 2 ] [ 4. 4] [ 4, 6 ] [ 5, 2 ] [ 5, 4] [ 5, 6] [ 6, 2 ] [ 6, 4 ] [ 6, 6 ] gi r l 4 3. 6 0 % 4 3. 6 8% 4 2. 9 9% 4 5. 1 5 % 4 4. 6 0% 4 2. 64% 4 5. 2 2% 44. 2 0% 41. 3 3 % coupl e 4 3. 0 5% 4 3. 0 2% 4 4. 4 4% 4 6. 01 % 4 5. 36% 44. 8 5% 4 7. 4 9% 4 6. 5 7% 4 4. 5 3 % ae r i al 2 2. 1 3% 21. 6 8% 2 0. 3 4% 2 2. 3 9 % 21. 63% 1 9. 8 9% 21. 9 7 % 2 0. 9 8% 1 8. 91 % moo n 31. 6 4 % 3 2. 1 1 % 31. 54 % 3 2. 4 4 % 3 2. 4 9% 31. 3 9% 3 2. 3 9 % 3 2. 1 6% 3 0. 50 % c he s t 43. 6 7 % 41. 4 3% 3 7. 1 5 % 4 2. 7 0% 3 9. 7 0% 3 4. 6 8% 41. 2 8% 37. 6 3% 31. 9 4 % f ac s 51. 1 7 % 5 2. 1 5% 5 4. 1 7 % 5 1. 5 8 % 52. 5 0% 5 4. 2 3% 5 4. 1 1 % 54. 7 8% 5 4. 9 6 % gi r 1 2 36. 0 9 % 37. 4 4% 3 8. 2 9 % 3 8. 3 4 % 3 8. 9 5% 38. 9 2% 3 8. 9 7% 3 9. 3 0% 3 8. 81 % ar ea 2 8. 6 8 % 2 8. 85% 2 8. 1 3% 2 9. 2 9 % 2 9. 1 6% 27. 9 3% 2 9. 1 3% 2 8. 7 6% 27. 1 7 % bar bar a 2 6. 6 3 % 27. 60% 2 8. 3 5% 2 8. 2 8 % 2 9. 00% 2 8. 8 7% 2 8. 7 7 % 2 9. 2 8 % 2 8. 7 6 % mandr i l l 1 9. 3 5 % 1 9. 54 ̲ % 1 8. 6 3 % 1 9. 51 % 1 9. 45% 1 8. 2 6% 1 9. 2 4 % 1 8. 9 4% 1 7. 5 0 %
サ1/プルのマル コフ性 を利 用 しているLにす ぎないが,LZW法 と比較 して1
0
か ら30%高 い圧
縮率が得 られている. この理由 として,本方式 は ビッ ト単位で圧縮 を行 うため,バイ ト単位 の情報 の内部 (ビッ トの連 な り) に存在す る冗長性を もよく取 り除いていると考 えられ る.す なわち,バ イ ト単位符号化 では,文字 は全 く別々の記号 として扱われ,文字 の連 な り,荏 率 の偏 りの度合いが圧縮率 を決め るが, ビッ ト単位符号化では,それ らに加 えて ピッ トの連 な りにおける相関 も圧縮率 を高め る方向に作用 し七い る.
6.
む す び画像情報を
2
億算術符号で効率 よく,容易 に符号化す る方法 を示 した. まず,一般論 として多値情報源を ビットのベク トルで表現 し,それ と同時 に多値出力の確率分布 を条件付 き確 率で表現す ることによって
,2
倍算術符号での符号化が可能 となることを示 した.そ して, 画像を2,3
のマル コフ情報源でモデル化 し, これを用いて実際の画像 データを符号化 し た.その結果; ビット単位符号化法 はバ イ ト単位の符号化法 と比べ,符 にモデルが複雑 な と ころで大 きな改善効果があることが明 らかとなった.また,高い圧縮率が得 られることで知 られているUNI X
のcompr es s
コマソ ド( LZW
法) と比較 しても,本方式 は約1 0
か ら30%
高い圧縮率を示す ことが明か となった.
今後の課題 としては,画像 によって圧縮率の最 も良い符号化 モデルが異 なることか ら,画 素単位で自動的にモデルを選択する機構 を取 り入れ,何時で も最適 な圧縮率が達成で きるよ
うにす る事が考えられる
( 7 ) .
参 考 文 献
( 1 )
笠原,田崎,小倉 :情報理論,昭晃堂 (昭6 0 ‑1 0 ) .
( 2 )∫.Ri s s a ne nandG.G.La ngdo n, J r: " Ar i t hme t i cCo °i ng,
"I BM ∫ .Re s .DEVELOP, γ ol . 2 3 , pp.
1 4 9 ‑ 1 6 2( Ma r c h1 9 7 9 ) .
( 3 )J .Ri s s a ne nandG.G.La ngdo n,J r: " Un i ve r s a lMo de l i n gandCo°i n g, 〟I EEETr a ms .∫ nf o r m.
The o r y, γ ol .
IT‑ 2 7
,1 ,pp. 1 2 ‑ 2 3( J am1 9 8 1 ) .
(4) 半田,田中 :…‑フマン符号の符号帳の記述に関する一考察",電子情報通信学会論文誌
A , Vo l . J 7 0 ･ A,No. 9 ,p p. 1 5 01 ‑ 1 5 0 3( 1 9 8 7 ‑ 1 0 )
( 5 )A.Papo ul i s: Py 1 0 b a b i l i b , .Ro nd o m Van ' a b l e s ,a ndSt o c h a s i i cPr o c e s s
es ,Mc Gr awHi l l ( 1 9 8 4 ) . ( 6 )T.A.We l c h: " ATe c hni q uef orHi g h･ Pe r f o m a c eDat aCo mpr e s s i o n,
"I EEEComput e r ,pp.
8 ‑ 1 9( J une1 9 8 4 ) .
(7)上田,田中,半田 :"算術符号を用いた適応的デ‑タ圧縮の一方式",電子情報通信学会論文誌
