値算術符号による多値情報源の圧縮符号化

2 値算術符号による多値情報源の圧縮符号化

半 田 志 郎

Binary Arithrrtetic Coding for Multi‑Level Information Sources.

Shiro HANDA

I nt hi spa pe r , wepr o pos ean e wc o° i n gs c he mef ormul t i ･ l e ve li nf o r mat i o ns ou r c e s . Amul t i ‑ l e ve lout c omee mi t t e df r om t hes o ur c ei sde c o mpos e di n t obi na r yl e t t e r s .So t he yc a nbee nc ode dbybi na r ya r i t hme t i cc odeus i n gt hec ondi t i o nalpr o ba bi l i t i e si nt o whi c ht hep r o ba bi l i t yofmul t i ･ l e ve lda t ai sal s ode c o mpo s e d.The r e f or et hi sc o°i n g s c he mei sdo neve r ye as i l yw it ho utl os sofe 氏c i e nc y. Wes ho wt hepe r f o r manc eoft hi s c o di n gs c he mef ora c t ua lda t aofi ma ge s ,Cs o ur c e s ,e t c .Fu r t h e r e mo r eanada pt i ve s c he meandmar kof fmo d e lc odi n gs c he mear eal s oc ons i de r e d.

1 . ま え が さ

多情情報源から出力 されるシンボルを符号化す る場合,通常は一つのシンボルを単位 とし て符号化す る ( 1 ) . ところが算術符号( 2 ) の使用を前提 とした場合,多値情報源を扱 う算術符号 は,符号化過程において多 くの演算を必要 とし,アルゴ リズムも複雑 となる. また,同一の 演算器を用いる場合には , 2 値算術符号化 と比べ, アルファベ ットの個数分だけ区間の分割 が必要 となるため,結果 として演算精度が低下 した ことにな り,圧縮率の低下 をもた らす と 考 えられ る.

以上の認識 に立 って,本論文では 2 値算術符号による多値情報源の符号化法,及 びその圧 縮率について検討 している.まず,多情情報源出力を 2 倍の成分を持っベク トルに分解 し, それ と同時に多値情報源の確率分布を 2 値情報源の確率分布 に分解する. これによって,情 報源が定常エルゴ‑ ト的 と考えられるならば,分解 によるロスなしに 2 値算術符号 で容易に 符号化で きることを示す.

2. 多値情報源の符号化 2. 1 確率分布の分解表現

多情情報源 X か らの出力系列 X , . が 2

個の値 を取 り得 るものとすると ,X z ･ は

X. ･ ‑( X

O ,X,

･ ,X

(1

とベク トルで表現できる. ここで ,X , ･ , ･ は 0または 1 のみの値をとるものとす る.

この様 に表現 した ビット列 は,多値情報源 X が定常的であるならば,明 らかにブロック

●電気工学科講師

原稿受付 平成

2

6 月22日

1 0

定常 となるので,各 ビッ トはそれぞれ異 なった確率分布 を持つ ことになる. また,文字 の コ ー ド表現 の様 な場合 には,位置による重要度 の様 なものはないが,例 えば画像情報の ように 輝度 レベルを表 した数値 の様 な場合 には,上位 ビットはど重要 な意味を持 ってい るので,符 号化 においてもそのよ うな構造を保存 したまま取 り扱 うことが望 ま しい.

X. ･ の出現確率 p( X . I )はこのベク トル表記 に従 って, P( Xi ) ‑ P( X , ･ ｡ ,X , ･ l , ‑‑,X, ･ n ̲ 2 ,Ki n ‑I )

‑ p( X

｡

♪( X , ･ lI Xl ･ ｡ )

･ ･ P( X, ･ n

iX z ･ O , X, ･ 1 ,･ ･ ･ ･ ･ ･ ,Xl . n ̲2 ) (2) となる. ここで ,P( ･ l･) は条件付 き確率 を示す. この表現 に よると,X . ･ の符号化 は P

( X. 1 ) 自身を用 いて多値で行 う必要 はな く ,2 値情報 の条件付 き確率分布 を用 いて , 2 倍算 術符号で容易に行 えることになる. また, この分解 によってエン トロピーの変化 はないので, 分解 によるロスは無い.次章で詳 しく述べ るが, ビッ トによって重みに違いのあるよ うな場 合 には,重みの順番 に ビット分解す るのが望ま しい.

この分解 によって情報源を記述す る′ iラメータの数が不変であることは,容易 に確 かめ ら れ る.例 えは,情報源 X が2 56 値 の値 を取 り得 るもの とす ると ,n ‑ 8とな り,上 の分解 で, P( x . 0 ) の記述 に 1 つ,P( x , p l l x , ･ ｡ ) に 2 つ,以下 4, 8 ,･ ･ ･ ･ ･ ･ ,1 2 8 ,合計で2 55 個 のパ ラメ

ータとな り ,25 6 値情報源を記述す るの と同一であ る.

次 に情報源をマル コフ情報源によってモデル化す る場合 には,あ る時点での出力 は以前 の 出力系列 に依存す ることになる.す なわち,以前 の出力系列 によって決 まる状 態 即 こよっ て 現在 の出力 X, ･ が左右 され る.従 って,出現確率 も条件付 き確率 p( X , ･lS. A ) を用いて示 さ

れ る. これ も(2)と同様 にして,

p( X . l lSl ･ ) ‑ P( xz l 0 ,‑ ‑ ,X, n ̲ 1lS, ･ )

‑ p( x z . 0I S , ･ ) p( x z p l lx . 0 ,S L ) ･ ･ ･ ･ ･ ･ P( xm̲ 1 L

. ,X

1 , ‑‑,Xt n ̲ 2 ,S. ) ( 3) と分解す ることによって ,2 倍算術符号で容易 に符号化で きることが分かる.

2. 2 適応的符号化

一般 に, これか ら符号化 しようとす る情報源 の確率分布 が既知であることは稀 であ る.そ の よ うな場合にも効率 よく符号化 を行 うため,次 の 2 つの方法が考 えられ る.

( 1 ) 静的符号化法 :確率分布 を調べ直 して, これを受信側へ送 った後 に符号化 を行 う方法.

( 2 ) 適応的符号化法 :データが入 って くる度 に確率分布 を更新 して,常 にその時点で推定で

きる最良の確率分布 を用いる方法 ･

情報源が定常 エル ゴー ド的であれば,上記 の 2 つの方法 は理論的 に同一の符号化効率 を達

成す ることが知 られているが( 3 ) ,( 1 ) の方法 は情報源 を一度先読み して確率分布 を求め る必要

があ るため,現実的には,データの 2 度読み といった操作が必要 とな り,符号化速度 の点 で

も不利である. また,設定 したモデルの′ iタメータをすべて受信側へ送 らなければな らない

ので, モデル設定の難 しさも直接効いて くることになる. これに比べ( 2) の方法 はデータの 2

度読みの必要 もな く, また多少大 きなモデルを設定 しても,パ ラメータ推定 においてモデル

の使用 しない部分 には到達 しない といった簡単 な自動調整機構 が作用す るので,それ ほどモ

デル設定 の難 しさが効 いて こない とい う利点がある.そ こで,本論文で もこの適応的符号化 法を用いることにす る.

図 1 に示す深 さ nの木 を考 える.右 の枝 は 1 ,左 の枝 は 0に対応す る.各校 には, カ ウ ンタが一つずつ付いている. この木 を用いて符号化 を行 う.

符号化法 :

[1]X tに対 して式( 1 ) の分解 によって x, ･ , . を得 る.

[2 ] ポインタを r o o t に移 し ( k ‑0) ,) I ‑0 とす る.

[3 ]xt ･ j をポインタ k で示 され る 2 つの枝 のカウン ト値 c h ( 0) , c A ( 1) に よって算術符号 化す る.

[ 4] C 々 ( x i , . )‑C k ( x i , ･ ) +1

[5]

z ･ , ･ が 0なら左下 ,1 なら右下 の ノー ドにポインタを移す.

[ 6] ) I ‑n‑ 1 なら終了.そ うでなければ ,) ' ‑) ' + 1 として [ 3 ]‑

以上 の符号化 において,木が一段深 くなることは,一つ条件が多 く付いた ことを意味 し, 式 ( 2 ) の確率分布 の分解表現 とよく対応 している. さらに,数値情報のように上位 ビッ トと下 位 ビットで重みが違 う場合 も,木構造 の根 に近い重要 な部分 ほど多 く通過す るので,確率分 布 の暖昧性がな くな り,従 って真 の確率分布 に近 い確率で符号化で きる. また,各 ノー ド k での算術符号化 においては,

p々 ( 0 )= ^{c A (} 0) + 1 c h ( 0 )+c h (1)+2 I ) A( 1 ) ‑ 1 ‑PA ( 0)

として符号化を行 ってい る. これは,連続の法則 ( Th el o wo fs u c c e s s i o n ) と呼 ばれ( 4 ㌧ c A (o)+c h (1)回の観測の後 に,次 の出力 が 0また は 1 であ る確率 の期待値 が上 式 で与 え ら れ ることに基づいている.す なわち,真 の確率分布 の最良の予測 になってい る.

0 く さ 1

0( r o o t )

図 1 符号化の木

1 2

マル コフ情報源モデルを適用す る場合 (1次 のマル コフ情報源モデルに限 る) には,上記 の木 を状態の数だけ用意 し,各状態で別々の木 を用いて符号化を行 えばよい. この時注意 し なければならないのは,余 り大 きな ( 状態数の多い) モデルを設定 して しま うと,各 カウン タ値 は希薄 とな り過 ぎて,確率分布 の推定が暖味になって しま う.そ こで,本論文で は状態 として直前のデータの上位数 ビットのみを用 いている.

3. 符号化実験および考察

計算機上 に上記の符号化器を作成 し,符号化 シ ミュレーシ ョンを行 った.表 1 に資料 とし て用いたデータの大 きさと種類 を示 している.画像 データは,東大生研 の標準画像 SI DBA か ら選 んだ人物像 ( gi r l .i mg)及 び航空写真 ( a er i al .i mg)である.データは 1 サンプル 8 ビッ トであ り, ラスター走査 の順番 に並 んでい る.画像 のサ イズ は,gi r l .i mgが 2 56×2 56 画素,ae r i al .i mg が51 2×51 2 画素であ る. Cの ソ‑スプログ ラムは,本方式 を実現す るた めに作成 した ソースのアスキーファイルである.実行形式 ファイルは, ワークステ‑シ ョソ ( SONY NEWS NWS‑ 38 6 0)上 の本 プログ ラムの実行 ファイル と漢字 emac s とい うエデ ィタの実行 ファイルである.

図

にバイ ト単位 で符号化を行 った場合の圧縮率 を示 している. また,図

に本論文で提 案 した方式によるビット単位の符号化法 の圧縮率を示 してい る.なお,圧縮率 は次式で定義

している.す なわち,符号化 によって減少 した割合 を示 している.

圧縮率 ‑ 元 のファイルのバイ ト数 一圧縮後の ファイルのバイ ト数

元の ファイルのバイ ト数 (6)

画像 データと実行形式 ファイルに対 しては, それほど大 きな違いはみ られ ない. しか し, gi r l .i mgにおいては,. バ イ ト単位符号化では状態 の数が多 くなる と,圧縮率 の低下 が顕著 となるが, ビッ ト単位符号化ではそれほ ど低下 しない. これ は,先 に述べたモデルの設定 の 難 しさが顕著に影響 したよい例 である. このことは,他 のファイルについて も同様であ り, バイ ト単位符号化では最適 な圧縮率 を与 える状 態の ビッ ト数が, ファイル ごとにまちまちで あるのに対 して, ビット単位符号化では,状態 の ビット数がほぼ 8 の所で最大 となってい る.

C 言語 の ソースファイルに対 しては,顕著 な違いがみ られ る.バ イ ト単位符号化で は,状 態の ビット数が

か ら

で圧縮率 は最大 とな り,それ以上大 きくな らない. しか し, ビッ ト 単位符号化では , 8 で最大 とな り, さらに大 き くしても (2 バイ ト以上 のマル コフ性 を考慮

表 1 実験に用いたファイルの大きさと種類

フ ァ イ ル サ イ ズ 種 類 c o mpr e s s の耳桁率 gi r l .i mg 6 5, 5 3 6 画像デ‑タ 0. 2 6 3 5 2▲

ae r i al .i mg 2 6 2, 1 4 4 画像データ 0. 1 0 6 5 0

bi Li o.C .1, 4 1 7

言語 ソー. スコ⊥ ド 0. 3 3 9 4 5

ma r i t h.C 4, 8 7 . 9

言語 ソ‑スコー ド 0. 4 1 3 2 0

ma r i t h 5 2, 7 3 2 実行形式 0. 4 3 0 1 4

8 . 6 0 . 5 浄 0 . 4 輩 也 0 . 3

0 . 2 0 . 1

̲N‑ ‑‑, ‑J < . ‑' ‑●' X. 一一 ‑ ‑ 〜 . ‑. ‑. X‑ ‑‑ ‑ 六一一‑守 早‑ ‑ ‑ ‑ ‑ . ‑一 宇一 一 一 一 一 一 一 . 〇 一

○ ̲ ̲ . ̲ ̲ .̲ :‑ 二:三. ニコー ポ ‑ 二‑ムー､ ▲‑一一二 二 二 A一一

e 1 2 3 4 5 6 7 8

状態のビット数

ロg l r l . 1 m g +a e r l a l . l n g Omr l t h . c Ab l LI o . c Xmr l t . h Vk e mc s 図 2 バイ ト単位符号化

0 . 6 0 . 5 線 0 . 4 也 守

0 . 3 0 . 2 0 . 1

×一 サー. 一‑ ‑ ‑一汁‑ ‑ 一 一 一‑ 7 . ‑ ‑ ‑ . ‑ 二 . 一 ' 一 ‑X‑ J : < ‑ 2‑ ‑ ‑. 2 ‑ ‑ ‑. ̲‑ ‑ ′ 一 一一か ̲ ̲ ̲ 一 中一 ^ 一一ムー‑‑A‑‑一 一一‑A ‑∫ . +. . i . ‑ . こ . . . i . .‑ , ‑ エ ; . ニ ー ‑ 甥 . ′ 一 一 皇 ‑ rL. 二名一 ÷′ ̲ . ̲ . ‑ , +. . . . . . . . ‑ . ‑ . +‑‑ . ‑ . . . ‑ ‑ +. ‑ . ‑‑ ‑. . +‑ ‑ ‑ 一 一 一 ‑ ‑ ‑ ‑ +‑ ‑ ‑‑ ‑ ㌔ ‑ +

̲ ̲ i ‑ . イー . . , ' ' . . ‑ , ‑ +‑ , ‑ ‑ . ‑ I l . ‑ 〟

+ ● ー l l l ●

0 1 2 3 4 5 6 7 8

状慾の ビット数

t jg i r l . l n g +a e r i a l . l r n g Om a r l t h . c Ab l Ll o . c Xm a r l t h マk e mc s 図 3 ビット単位符号化

して も)圧縮率 の増大が期待で きる.最大 の圧縮率が得 られ るところで比較す ると,本論文 で提案 した ビッ ト単位符号化法では,バイ ト単位符号化法 と比べ,約 1 3 % 高い圧縮率が得 ら れている.

表 1 に ,UN IX の標準圧縮方式 として提供 されてい る c o mpr e

s(LZW 符号化法( 5 ) ) コマン ドの各 ファイルに対す る圧縮率が示 されてい る. LZW 法 は,文字 の連続パ ターンを 符号化す る形の方法であるため, ソースファイルの ように相関の高いファイルに対 しては非 常 に強力のはずである.本方式 は,直前の出力文字 とのマル コフ性 を利用 しているに過 ぎな いが ,LZW 法 と比較 して も,画像 ファイルに対 して約 2 0 %,C 言語 ソースファイルで約 5

%,実行形式 ファイルで約 3% ,それぞれ高い圧縮率が得 られてい る. この理 由 として,本

方式 は ビット単位で圧縮 を行 うため,バ イ ト単位 の情報 の内部 (ピットの連 な り) に存在す

る冗長性 をもよ く取 り除いてい ると考 えられる.す なわ ち,バイ ト単位符号化 では,文字 は

1 4

全 く別々の記号 として扱われ,文字の連 な り,確率の偏 りの度合いが圧縮率を決め るが, ど ッ ト単位符号化では,それ らに加 えて ビッ トの連 な りにおける相関 も圧縮率 を高め る方向に 作用す る.例 えば, アスキーファイルでは文字 abc〜 Oは上位 4 ビットが 0110 と共過 であ るが,バイ ト単位符号化 では, これ らを全 く別々の記号 として扱 うのに対 して, ビット 単位符号化ではこの共通性が圧縮率を高める方向に作用 している.

4. む す び

多値情報源を 2 億算術符号で効率 よ く,容易に符号化す る方法 を示 した. まず,情報源出 力 を ビッ トのベ ク トルに分解 し,それ と同時 に多値出力の確率分布 を条件付 き確率で表現す ることによって ,2 倍算術符号 での符号化が可能 となることを示 した. さらに,実際 の UN

IX 上 のファイルに適用 して圧縮率を調べた.その結果,高い圧縮率 が得 られ ることで知 ら れている compr e s s コマン ド (LZW 法) と比較 して も,本方式 は画像 ファイルで約 2 0%, C 言語 ソースファイルで約 5% ,実行形式 ファイルで約 3% ,それぞれ高い圧縮率 を示す こ とが明か となった.

本方式では,直前 の文字 とのマル コフ性のみを用いてい るが, さらに多 くの文字 とのマス コフ性 を考慮 しても, よ り高い圧縮率が期待できることが,実験結果か ら明か となったので, これを詳 しく調べ ること,及 び符号化の高速化が今後 の課題であ る.

謝 辞

実験 に用いた標準画像 を提供 して頂いた東大生研関係者各位 に感謝す る. また,本研究の 一部 は,平成元年度科学研究費補助金奨励研究 ( A) ( 課題番号 : 01 7 50 3 0 8) の援助 の下 に 行われた.

参 考 文 献 ( 1 ) 笠原,田崎,小倉 :情報理論,昭晃堂 ( 昭 6 0 ‑1 0 ) .

( 2 ) ∫ . Ri s s a n e nan dG. G. La ngdo n, J r: " Ar i t hme t i cCo°i n g, " I BM ∫. Re s . DEVELOP, vol . 2 3 , p p.

1 4 9 ‑ 1 6 2( Mar c h1 9 7 9 ) .

( 3 )∫ .Ri s s a ne nan dG.G.Lan gdo n, J r:" Uni ve r s alMode l i n ga ndCo°i ng, " I EEETr a ms . I nf o m . The o r y, γ ol .

T‑ 2 7 , 1 ,pp.1 2 ‑ 2 3( J a m.1 9 8 1 ) .

(4

)A.Papo ul i s: Pr o b a b i l i t y ,Ro nd o m 一 r an' a b l e s ,andSt o c h a s i i cPy 1 0 C e S S e S ,Mc Gr awHi l l( 1 9 8 4 ) . ( 5 ) T. A. We l c h:" ATe c hni quef o rHi g h･ Pe r f o mac eDa t aCo mp r e s s i o n, " I EEECo mp ut e r , pp. 8

‑ 1 9

( J une1 9 8 4 ) .