JP3146092B2

JP3146092B2 - 符号化装置及び復号化装置

Info

Publication number: JP3146092B2
Application number: JP15503693A
Authority: JP
Inventors: 孝義瀬政
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1993-06-25
Filing date: 1993-06-25
Publication date: 2001-03-12
Anticipated expiration: 2016-03-12
Also published as: JPH0715349A

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、符号化装置及び復号化
装置に関する。

【０００２】

【従来の技術】マルコフ情報源の符号化においては、情
報源の出力シンボル系列に対し、既に符号化済みのシン
ボルである参照シンボルにより符号化対象シンボルを予
測し、その予測誤差信号を参照シンボルパターンにより
予測的中率に応じて各予測誤差信号をいくつかの群に分
類し、それぞれに適した符号を用いて符号化が行われて
いる。ここで、以下この予測誤差信号の作成のことを、
予測変換、群に分類することを統合、群の識別子のこと
を次数と呼ぶ。また、符号化されるべき予測誤差信号の
ことを予測誤差シンボルと呼ぶことにする。

【０００３】対象とする信号が２値情報源の場合、この
予測変換及び次数選択方法としては、情報源の統計的性
質の局所的変化に対応するため、適応処理を行う技術が
特開平２−３０５２２５号公報に開示されている。ま
た、予測誤差シンボルの符号化手法については、減算型
算術符号化法が、ＩＢＭ研究開発情報１９８８年１１
月、第３２巻第６号（IBM Journal of Reserch and Dev
elopment, Vol.32,No.6,Nov.1988）の「Ｑ−コーダ対応
２元演算符号器の基礎的原理の外観」（An overview of
the basic principle of the Q-Coder adaptive-binar
y arith-metic coder ）や特開平２−２０２２６７号公
報などに開示されている。これらはシンボル系列を数直
線上で０．０から１．０までの間に写像し、その座標を
符号語として符号化する数直線表示符号化装置の一種
で、生起したシンボルに応じて数直線を分割する際に、
加減算のみで行うものである。

【０００４】２値情報源の符号化の場合には、これら手
法により情報源のエントロピに近い高能率な符号化が実
現できている。多値情報源の場合、これら２値算術符号
を用いるには多値信号を複数の２値信号に変換して符号
化することとなる。以下、図に従って従来の技術による
予測変換、統合及び符号化の過程を説明する。図２３は
従来の技術による１画素８ビットの画像信号の符号化装
置のブロック図である。簡単のため参照シンボルは図２
４の５画素中から注目シンボルと最も相関の強い同一走
査線上の直前のＡの位置の信号とする。また、統合数は
１６とする。

【０００５】図２３で、１は情報源シンボル１０１の系
列から参照シンボルを選択出力する参照シンボル作成
器、２はこの出力である参照シンボルパターン１０２よ
り後述の次数・予測値メモリのアドレス１０３を生成す
るアドレス生成器、３は２値化後の対象シンボルの次数
１０４と予測値１０５を出力する次数・予測値メモリ、
４は符号化対象シンボルを２値化する多値２値変換器、
５は予測値１０５をもとにこの変換器４の出力である２
値符号化シンボル１０６の予測誤差シンボル１０７を作
成する予測変換器、６は次数・予測値メモリ３から出力
された次数１０４をもとに算術符号の領域幅１０８を出
力する領域幅テーブル、７は算術符号器、８は次数・予
測値メモリの読み出しと更新を制御する次数・予測値制
御回路である。ここで、参照シンボル数を１としたこと
より、次数・予測値テーブル（次数・予測値テーブルメ
モリ３の内容）は図２５に示すように２⁸ ×２５５種必
要となる。次数値については統合を１６の群としたこと
からこれを識別するものとなる。ここでは予測的中率の
高い程次数が高いものとする。

【０００６】次にその動作を説明する。情報源から発生
した情報源シンボル１０１（画像信号）は参照シンボル
作成器１でその系列が記憶されると共に、図２４のＡに
示す画素の信号が選択されて参照シンボルパターン１０
２として出力される。アドレス生成器２ではこれをもと
に図２５に示す、当該参照シンボルパターンにおける符
号化対象ビットＭＳＢに対応するメモリアドレスが生成
され、次数・予測値メモリ３から、対象シンボルの当該
ビット（ＭＳＢ）に対する予測値１０５と次数１０４が
出力され、次数１０４情報は図２６に示す領域幅テーブ
ル６で領域幅１０８として変換出力される。

【０００７】一方、情報源シンボル１０１は多値２値変
換器４でＭＳＢが選択され２値符号化シンボル１０６と
して出力される。予測変換器５では予測値１０５とこの
２値符号化シンボル１０６の排他的論理和がとられ予測
誤差シンボル１０７が作成される。そこでこの予測誤差
シンボルは、予測一致の場合に０（ＭＰＳ: More Proba
ble Symbol）、不一致の場合に１（ＬＰＳ: Less Proba
ble Symbol）となる。

【０００８】算術符号器７では領域幅１０８信号をもと
に、予測誤差シンボル１０７を数直線上に写像してゆき
符号化が実行される。次いで２ｎｄＭＳＢの場合は、
アドレス生成器２では参照シンボルパターン１０２と当
該符号化シンボルのＭＳＢのパターンにより、２ｎｄ
ＭＳＢのビットに対応するメモリアドレスが生成され、
次数・予測値メモリ３から予測値１０５と次数１０４が
出力される。一方２値符号化シンボル１０６としても多
値２値変換器４で発生シンボル１０１の２ｎｄＭＳＢが
選択され上記同様の数直線上への写像・符号化が実行さ
れる。以下同様にしてＬＳＢまでの符号化が終了した段
階で次の符号化シンボルの符号化に移る。

【０００９】ここで算術符号化の詳細に触れておく。
今、予測誤差シンボル系列において第ｉ番目のシンボル
をａ_i 、第ｉ時点でのＬＰＳの写像範囲（割当領域）を
Ｓとすると、ＭＰＳ領域を有効領域の下側に取るとすれ
ば、第ｉ時点でのシンボル系列の写像範囲（有効領域）
Ａｉとその下界値座標Ｃｉは、シンボルａ_i がＭＰＳの
とき、Ａｉ＝Ａi-1 − ＳＣｉ＝Ｃi-1 シンボルａ_i がＬＰＳのとき、Ａｉ＝ＳＣｉ＝Ｃi-1 ＋（Ａi-1 −Ｓ）とする。

【００１０】ここで有効領域Ａｉが１／２以下になった
場合には、演算制度を上げるため２のべき乗倍する。こ
のとき座標Ｃｉのオーバーフロー（小数点以上の部分）
分が符号ビット系列として出力される。以下このべき乗
処理を正規化と呼ぶ。Ａｉ更新値＝Ａｉ＊２^m （１／２＜Ａi 更新値≦１）Ｃｉ更新値＝Ｃｉ＊２^m

【００１１】算術符号においては，ＳをＬＰＳの出現確
率（＝予測誤り確率）とすることで、情報源エントロピ
に極めて近い高効率の符号化ができることが知られてい
る。よって、次数に対応した予測的中率に適したＳ値を
選択することで上記処理により算術符号化を行うことが
できる。図２６は次数と領域幅Ｓとの対応表の一例であ
る。表中の値は、上記式中の数値を２¹⁶倍したものを記
してある。この例では、数直線上の領域計算は１６ビッ
ト精度で行うものであり、Ａｉ、Ｃｉはそれぞれ小数以
下１６ビット精度となる。

【００１２】次に予測および統合の適応処理について説
明する。この適応処理方法としては、出力シンボル系列
から連続するＭＰＳとＬＰＳの数を計数して制御する方
式と、上記正規化が生起したときのシンボルがＭＰＳか
ＬＰＳによって制御する方式がある。ここでは後者の方
式を例にとって説明する。次数・予測値制御回路８は正
規化時に予測変換器５の出力シンボルがＭＰＳあるいは
ＬＰＳであるかを判定する。

【００１３】ＬＰＳの場合次数・予測値メモリ３において、その時の参照シンボル
パターンに対応する次数の値を１だけ減算する。これ
は、当該状態における予測が外れたため、予測の的中度
を示す次数を下げることによって、現在の符号化対象と
なっている情報源に対し、次数・予測値を適応させる動
作である。次数が最低次数に達しそれ以上次数を減じる
ことが出来なくなると、予測値を反転させる。この動作
により的中率が極端に悪い予測値は書き換えられる。

【００１４】ＭＰＳの場合次数・予測値メモリ３において、その時の参照シンボル
パターンに対応する次数の値を１だけ加算する。これ
は、当該状態における予測が的中したため、予測の的中
度を示す次数を上げることによって、現在の符号化対象
となっている情報源に対し、次数・予測値を適応させる
動作である。次数がすでに最高次数に達している場合に
は加算は実行されない。この動作により予測が極めてよ
く的中する場合には、次数を上げることによりＳ値が小
さくなり、算術符号器７から出力される符号量を抑える
ことができる。

【００１５】以上の動作により次数・予測値制御回路８
は、情報源の性質に追従して次数・予測値テーブルを書
き換えてゆき、高い符号化効率による算術符号化が実現
できる。

【００１６】

【発明が解決しようとする課題】しかし、多値情報源の
場合、マルコフ状態数は２値信号の場合に比べ非常に大
きなものであり、実際上これらの方式を実現することは
困難である。例えば上記例の場合では簡単のため参照シ
ンボル数を図２４のＡの画素１つとしたが、これでも装
置化しようとすれば次数・予測値メモリとして図２５に
示すように、参照シンボルの値が２５６（２⁸ 即ち０〜
２５５）種類あり、各種２５５（１＋２＋４＋８＋１６
＋３２＋６４＋１２８＝２５５）のテーブルを有し、各
テーブルが次数４ビットと予測値１ビットを必要として
いるため、２５６×２５５×（４＋１）ビット＝６５２
８０×５ビットの容量が必要であり、ＬＳＩ化するには
メモリを別チップとする必要がある。またＳ／Ｗで実現
するにも同様のメモリ空間を要すこととなる。さらに符
号化の効率を上げるため参照シンボル数を例えば３とし
ようとすると、情報源が８ビットの画像信号の場合、次
数・予測値メモリ３のサイズは２²⁴×２５５×（４＋
１）ビットとなってしまい実現不可能になる。

【００１７】この発明は上記のような問題点を解消する
ためになされたもので、参照シンボルの情報を広く取り
入れることが可能で、かつ次数・予測値メモリを大幅に
削減可能な高能率な符号化装置及び復号化装置を得るこ
とを目的にしている。

【００１８】

【課題を解決するための手段】この発明に係る符号化装
置は、多値マルコフ情報源からの符号化シンボルを符号
化する符号化装置において、符号化する符号化シンボル
に先行する複数の先行シンボルを複数の参照シンボルと
して抽出する参照シンボル作成手段と、参照シンボル作
成手段により抽出された複数の参照シンボルのレベルが
互いに等しいか否かを検出する一致検出手段と、一致検
出手段により検出されたレベルが異なる参照シンボルと
符号化シンボルとを比較し、比較結果に基づいて符号化
シンボルのレベルを変換する変換手段と、変換手段によ
り変換された出力を符号化する符号化手段とを備えたこ
とを特徴とする。

【００１９】この第２の発明に係わる符号化装置は、予
め定められた位置関係にある複数の先行シンボル（参照
シンボル）に着目し、参照シンボル内に生起した多値レ
ベルの種類の数を検出する手段と、これによりマルコフ
状態を分離符号化する手段を備えたものである。

【００２０】この第３の発明に係わる符号化装置は、上
記参照シンボルで重複するレベルを有するシンボルを削
除した後に予め定められた順序にシンボルを並べ替える
手段と、符号化シンボルが該並び替えた各シンボルと等
しいか否かを示す信号を生成する多値２値変換手段と、
これを順に２値算術符号により符号化する手段を備えた
ものである。

【００２１】この第４の発明に係わる符号化装置は、符
号化シンボルのレベルが上記参照シンボル内に生起しな
い場合、符号化シンボルのレベルを特定するための情報
を生成する手段と、この情報を上記２値算術符号とは別
に符号化する符号化手段を備えたものである。

【００２２】この第５の発明に係わる符号化装置は、符
号化シンボルのレベルが上記参照シンボル内に生起しな
い場合、上記並び替えた参照シンボルの後にそれ以外の
レベル信号からなる信号系列を生成する手段と、符号化
シンボルがこの信号系列の各レベル信号と等しいか否か
を生成する多値２値変換手段とを備えたものである。。

【００２３】この第６の発明に係わる符号化装置は、符
号化シンボルのレベルが上記参照シンボル内に生起しな
い場合、符号化シンボルのレベルを特定するための必要
なビット数の情報を生成する手段と、この特定情報を１
ビットずつ選択する手段を備えたものである。

【００２４】この第７の発明に係わる符号化装置は、各
マルコフ状態の各２値算術符号化のステップごとに、２
値シンボル出現確率を符号化の中で更新する手段を備え
たものである。

【００２５】この第８の発明に係わる符号化装置は、各
マルコフ状態の各２値算術符号化のステップごとの２値
シンボル出現確率を識別する信号を生成する手段を備え
たものである。

【００２６】この発明に係る符号化装置は、多値情報源
シンボルを符号化する符号化装置において、符号化する
多値情報源シンボルに先行する複数の先行シンボルを複
数の参照シンボルとして抽出する参照シンボル作成手段
と、参照シンボル作成手段により抽出された複数の参照
シンボルを参照シンボルのレベルに基づいて並べ替える
シンボル並べ替え手段と、シンボル並べ替え手段により
並べ替えられた参照シンボルのレベルと符号化する多値
情報源シンボルのレベルとを比較し、符号化する多値情
報源シンボルのレベルが参照シンボルのいずれのレベル
と一致するか又は参照シンボルのいずれのレベルとも一
致していないかということを判定して、その判定結果を
多値情報源シンボルの変換結果として出力する変換手段
と、変換手段により出力された判定結果を符号化する第
１の符号化手段と、多値情報源シンボルのレベルが参照
シンボルのいずれのレベルとも一致しない場合、符号化
する多値情報源シンボルを特定する情報を符号化する第
２の符号化手段とを備えたことを特徴とする。

【００２７】この発明に係る復号化装置は、多値マルコ
フ情報源からの符号化シンボルを符号化したデータを復
号化する復号化装置において、符号化されたデータを復
号化する復号化手段と、復号化する符号化シンボルに先
行する複数の先行シンボルを複数の参照シンボルとして
抽出する参照シンボル作成手段と、参照シンボル作成手
段により抽出された複数の参照シンボルのレベルが互い
に等しいか否かを検出する一致検出手段と、一致検出手
段により検出されたレベルが異なる参照シンボルを用い
て、復号化手段により復号化されたデータを符号化シン
ボルへ変換する変換手段とを備えたことを特徴とする。

【００２８】この発明に係る復号化装置は、多値情報源
シンボルを符号化したデータを復号化する復号化装置に
おいて、多値情報源シンボルを符号化したデータには、
復号化する多値情報源シンボルが参照シンボルのいずれ
のレベルと一致しているか又は参照シンボルのいずれの
レベルとも一致していないかという判定結果と復号化す
る多値情報源シンボルを特定する情報とが含まれてお
り、復号化する多値情報源シンボルに先行する先行シン
ボルを複数の参照シンボルとして抽出する参照シンボル
作成手段と、参照シンボル作成手段により抽出された複
数の参照シンボルを参照シンボルのレベルに基づいて並
べ替えるシンボル並べ替え手段と、復号化する多値情報
源シンボルが参照シンボルのいずれのレベルと一致して
いるか又は参照シンボルのいずれのレベルとも一致して
いないかという判定結果を復号化する第１の復号化手段
と、第１の復号化手段により復号化された判定結果が、
復号化する多値情報源シンボルのレベルが参照シンボル
のいずれかのあるレベルと一致しているということを示
している場合、その判定結果を並べ替え手段により並べ
替えられた参照シンボルの当該レベルへ変換して多値情
報源シンボルとして出力する変換手段と、復号化する多
値情報源シンボルが参照シンボルのいずれのレベルとも
一致していない場合、多値情報源シンボルを符号化した
データに含まれている情報であって、復号化する多値情
報源シンボルを特定する情報を復号化して多値情報源シ
ンボルとして出力する第２の復号化手段とを備えたこと
を特徴とする。

【００２９】

【作用】この第１の発明に係わる符号化装置は、複数の
参照シンボルがお互いにどのシンボルと等しいか（ある
いは等しくないか）という情報により情報源を統合する
ことにより、高い圧縮性能で情報圧縮を可能とするもの
である。

【００３０】この第２の発明に係わる符号化装置は、複
数の参照シンボルの中に何種類の多値レベルがあるかに
よって情報源を統合することにより、高い圧縮性能で情
報圧縮を可能とするものである。

【００３１】この第３の発明に係わる符号化装置は、参
照シンボル内に生起するレベル値と符号化シンボルが等
しいか否かの信号を２値算術符号化することにより、高
い圧縮性能で情報圧縮を可能とするものである。

【００３２】この第４の発明に係わる符号化装置は、符
号化シンボルのレベルが参照シンボル内に生起しない場
合、このレベルを特定する情報を別途符号化することに
より、高い圧縮性能で情報圧縮を可能とするものであ
る。

【００３３】この第５の発明に係わる符号化装置は、符
号化シンボルのレベルが参照シンボル内に生起しない場
合、参照シンボル内に生起するレベル以外のレベル信号
と符号化信号が等しいか否かを２値算術符号化すること
により、高い圧縮性能で情報圧縮を可能とするものであ
る。

【００３４】この第６の発明に係わる符号化装置は、符
号化シンボルのレベルが参照シンボル内に生起しない場
合、このレベルを特定する信号を１ビットずつ２値算術
符号化することにより、高い圧縮性能で情報圧縮を可能
とするものである。

【００３５】この第７の発明に係わる符号化装置は、２
値算術符号化において２値シンボル出現確率を実際に生
起する信号系列に応じて更新してゆくことにより、高い
圧縮性能で情報圧縮を可能とするものである。

【００３６】この第８の発明に係わる符号化装置は、２
値算術符号化において当該情報源の符号化において適当
と思われる２値シンボル出現確率を予め設定し、その後
で実際の符号化処理を行わせることにより、高い圧縮性
能で情報圧縮を可能とするものである。

【００３７】この第９の発明に係わる符号化装置は、変
換手段が参照シンボルと符号化シンボルを比較し、その
比較結果に基づいて符号化手段が符号化を行うものであ
り、符号化シンボルが参照シンボルと同一の値を取るこ
とが多い場合には、効率の良い符号化が可能となる。特
に、コンピュータプログラム等により作られるアニメー
ションや、コンピュータ・グラフィックス等の画像情報
を符号化する場合には、特定のパターンが繰り返された
り、限られた色で表示することが多いため、符号化シン
ボルが参照シンボルと同一の値を取る可能性が高くな
り、このような情報を符号化する場合には、参照シンボ
ルと符号化シンボルを比較して、一致するか一致しない
かという比較結果を符号化することにより効率の良い符
号化が行える。

【００３８】この第１０の発明に係わる復号化装置は、
上記第１の発明に係わる符号化装置により符号化された
情報を復号化するものである。

【００３９】この第１１の発明に係わる復号化装置は、
上記第９の発明に係わる符号化装置により符号化された
情報を復号化するものである。

【００４０】

【実施例】実施例１．以下、本発明を図示実施例に基づいて説明する。図１は
本発明における１画素８ビットからなる画像信号の符号
化装置のブロック図で、図２３の従来の符号化装置との
違いは、参照シンボルパターン１０２より参照シンボル
同士がどの様な一致関係にあるかを検出する一致検出器
９、この出力１１２をもとに参照シンボルパターン１０
２のレベル値を並べ替えるシンボル並び替え器１０、注
目情報源シンボル１０１のレベルがこの参照シンボル中
に生起しない場合これを特定するための特定情報作成器
１１、この特定情報信号１１５を符号化する符号器１
２、及び、算術符号器７の出力１１４と特定情報符号器
１２の出力１１６を切り替えて符号出力１０９とするた
めの切替器１３が追加されていることである。

【００４１】次に、本実施例の動作について説明する。
ここでは、参照画素数が５である場合について説明す
る。ここで、参照画素（参照シンボルともいう）は、図
２４に示すＡ，Ｂ，Ｃ，Ｄ，Ｈの５画素とする。また、
１画素は８ビットで現されるので、各参照シンボルの信
号のレベル（レベル値ともいう）は０〜２５５のいずれ
かをとるものとする。情報源から発生したシンボル１０
１（画像信号）は参照シンボル作成器１でその系列が記
憶されるとともに、図２４に示す５画素の信号が選択さ
れて参照シンボルパターン１０２として出力される。一
致検出器９ではこの参照シンボル同士の一致関係を検出
する。

【００４２】参照画素数が５であるので、一致関係とし
ては、５画素すべてが一致する場合から、１画素のみ異
なる場合、・・・、５画素すべて異なる場合と、図２に
示す５２通りの組み合わせがあることになる。なおここ
で、＃１〜＃５は参照シンボルをＡ，Ｂ，Ｃ，Ｄ，Ｈの
順に並べて、参照シンボルのレベル値（０〜２５５）の
中で新たに生起したレベルを＃１から順に番号をつけて
行った場合の数値を示している。例えば、Ａ，Ｂ，Ｃ，
Ｄ，Ｈのレベルがすべて等しい場合、生起したレベル
は、＃１，＃１，＃１，＃１，＃１となる。また、Ａ，
Ｂ，Ｃ，Ｄのレベルが等しく、Ｈのレベルが異なる場
合、生起したレベルは、＃１，＃１，＃１，＃１，＃２
となる。また、Ａ，Ｂ，Ｃ，Ｈのレベルが等しく、Ｄの
レベルが異なる場合、生起したレベルは、＃１，＃１，
＃１，＃２，＃１となる。一致信号１１２はこの５２通
りを識別するため６ビットの信号となる。シンボル並べ
替え器１０ではこの一致信号１１２を受け、参照シンボ
ルをＡ，Ｂ，Ｃ，Ｄ，Ｈの順に並べた場合に新たに生起
したレベル値を並べ替え参照シンボル１１３として出力
する。例えば、Ａ，Ｂ，Ｃ，Ｄ，Ｈのレベルが全て等し
い場合、生起したレベルは＃１しか存在しないため、シ
ンボル並べ替え器１０は並べ替え参照シンボルとしてＡ
のレベル値を多値２値変換器４に対して出力する。ま
た、Ａ，Ｂ，Ｃ，Ｄのレベルが等しく、Ｈのレベルが異
なる場合、生起したレベルは＃１と＃２であり、Ａのレ
ベル値と、Ｈのレベル値を並べ替え参照シンボル１１３
として多値２値変換器４に対して出力する。同様に、
Ａ，Ｂ，Ｃ，Ｈのレベルが等しく、Ｄのレベルが異なる
場合は、生起したレベルが＃１と＃２であり、Ａのレベ
ル値とＤのレベル値を並べ替え参照シンボル１１３とし
て多値２値変換器４に対して出力する。

【００４３】多値２値変換器４では、符号化対象シンボ
ル１０１と並べ替え参照シンボル１１３が一致するか否
かを検出して２値符号化シンボル１０６を作成してこれ
を従来の装置同様にして２値算術符号化を行う。もし、
いずれの参照シンボルとも一致しない場合は、特定情報
信号１１５として、符号化対象シンボル自身を特定情報
符号器１２でハフマン符号化する。

【００４４】以下に５つの参照シンボルのレベルが全て
異なる場合、及び全て一致する場合について説明する。
なお、以下の説明で「＝」の左辺と右辺はシンボルのレ
ベルを示している。また、「！＝」はｎｏｔ＝を示して
おり、その左辺、右辺は同様にシンボルのレベルを示す
ものとする。例えば、５つの参照シンボルのレベルがい
ずれも異なる場合 (1) Ｘ＝＃１の場合 “０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃１の場合 “１”を算術符号化し、(2) へ (2) Ｘ＝＃２の場合 “０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃２の場合 “１”を算術符号化し、(3) へ (3) Ｘ＝＃３の場合 “０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃３の場合 “１”を算術符号化し、(4) へ (4) Ｘ＝＃４の場合 “０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃４の場合 “１”を算術符号化し、(5) へ (5) Ｘ＝＃５の場合 “０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃５の場合 “１”を算術符号化し、(6) へ (6) Ｘを特定情報符号器１２で符号化し、次符号化対象シンボルの処理へ。

【００４５】逆に、５つの参照シンボルがすべて一致す
る場合 (1) Ｘ＝＃１の場合 “０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃１の場合 “１”を算術符号化し、(2) へ (2) Ｘを特定情報符号器１２で符号化し、次符号化対象シンボルの処理へという処理を施す。参照シンボル内の生起レベル数が
１，５以外についても同様な処理とする。

【００４６】図３はこの実施例により符号化された一例
を示す図である。図３（ａ）は符号化対象シンボルＸの
レベルがいずれかの参照シンボルのレベルと一致した場
合を示している。例えば、３１は符号化対象シンボルＸ
が＃１と一致した場合を示している。また、３２は符号
化対象シンボルＸが＃２と一致した場合を示している。
３３は符号化対象シンボルＸが＃３と一致した場合を示
している。３４は符号化対象シンボルＸが＃５と一致し
た場合を示している。図３（ｂ）は５つの参照シンボル
のレベルがいずれも異なる場合であって、符号化対象シ
ンボルＸのレベルが５つの参照シンボルのいずれのレベ
ルとも一致しない場合の例を示している。この場合に
は、５つの参照シンボルと一致しなかったことを示す５
ビットの“１”と特定情報信号３６が出力される。図３
（ｃ）は５つの参照シンボルが全て一致する場合であっ
て、符号化対象シンボルＸが参照シンボルのレベルと一
致しない場合を示している。この場合には、１ビットの
“１”と特定情報信号３８が出力される。図３（ｄ）は
前述した図３（ａ）〜図３（ｃ）で示した情報が連続し
て発生した場合を示している。

【００４７】多値２値変換器４で発生された２値符号化
シンボル１０６は図３（ｄ）に示すような系列として予
測変換器５に入力され、その後算術符号器７により符号
化される。一方、特定情報作成器１１により作成された
特定情報信号１１５は特定情報符号器１２に入力され、
符号化されて出力される。

【００４８】上記説明で明らかなように、２値算術符号
化のステップとしては、参照シンボル中に生起するレベ
ル数に応じて、符号化処理する２値符号化シンボル１０
６の数は異なってくる。そこで、そのそれぞれについて
効率的な符号化を行うため、次数・予測値メモリ３内に
格納される次数と予測値については、別々の数値（テー
ブル）を用意する。このテーブル総数は図２に示す様
に、１５１種となる。図４にこのテーブルの内容の一例
を示す。

【００４９】例えば図３に示すように、Ａ，Ｂ，Ｃ，
Ｄ，Ｈのレベルが全て等しい場合は、符号化対象シンボ
ルＸのレベルが参照シンボルＡのレベルと等しいかどう
かという１種類のテーブルを持っている。また、参照シ
ンボルＨのレベルが他のレベルと異なる場合には、符号
化対象シンボルＸのレベルが参照シンボルＡと等しいか
どうかの場合に参照するテーブルと、符号化対象シンボ
ルＸのレベルが参照シンボルＨのレベルと等しいかどう
かの場合に参照するテーブルの２つのテーブルを用意す
る。

【００５０】特定情報信号１１５の符号化は、情報源の
シンボル出現確率に応じたハフマン符号化を行うことに
より実現できる。あるいは、より簡易には、符号化対象
シンボルＸそのものを８ビットで符号化することでも良
い。切替器１３は、算術符号器７で符号化された算術符
号１１４と特定情報符号器１２により符号化された特定
情報符号１１６を切り替えて符号１０９として出力す
る。この切替器１３の切り替え動作は時分割により２つ
の符号１１４，１１６を切り替えるようにしても構わな
いし、あるいは、２つの符号１１４，１１６を多重化さ
せることにより１つの符号１０９として出力するような
場合であっても構わない。算術符号器７、及び特定情報
符号器１２は算術符号１１４と特定情報符号１１６をそ
れぞれ別々に生成し、生成した符号１１４，１１６を図
示しないメモリに記憶させるとともに、切替器１３は別
々にメモリに記憶された算術符号１１４と特定情報符号
１１６を読み出して符号１０９を生成し、出力する。

【００５１】上記方式により、参照シンボル情報として
図２４の５画素の情報を用いた、高効率な符号化装置が
実現できる。しかも、学習に用いる次数・予測値メモリ
３の容量としては、１５１×（４＋１）ビットと極めて
小規模な回路で実現できる。

【００５２】以上のように、この実施例は符号化対象シ
ンボルＸのレベルが参照シンボルＡ，Ｂ，Ｃ，Ｄ，Ｈと
同一のレベルを持つ場合に、効率良く符号化を行うこと
ができる。例えば、コンピュータ・グラフィックスや、
アニメーション等の画像信号を符号化する場合には、同
一色や限られた色を連続して使う場合が多いため、この
ような符号化装置がよく適合する。自然画像等の無限の
色彩を表示するような画像情報を符号化する場合に比べ
て、前述したようなコンピュータ・グラフィックスによ
る画像情報やアニメーション等の画像情報を符号化する
場合の符号化効率が向上する。

【００５３】実施例２．図５は本発明の他の実施例である復号化装置のブロック
構成を示している。図で、１３は別々に格納された算術
符号データと特定情報符号化データを後述の各復号器の
要求に従い、読み出す切替器、１４は算術符号ビット系
列１１４より領域幅１０８をもとに予測誤差シンボルを
再生する算術復号器、１５は特定情報符号ビット系列１
１６より特定情報信号１１５を再生する特定情報復号
器、１６は上記予測誤差シンボル１０７と予測値１０５
の排他的論理和演算を行って２値符号化シンボル１０６
を再生する予測逆変換器、１７は並べ替え参照シンボル
１１３と２値符号化シンボルをもとに、符号化シンボル
が参照シンボル内のレベルと同一な場合に情報源シンボ
ルを再生する２値多値変換器、１８は符号化シンボルの
レベルが参照シンボル内に生起しない場合に特定情報信
号１１５をもとに情報源シンボルを再生する特定情報逆
変換器、２２はこの２つの変換器の信号を選択して情報
源シンボルとするための切替器であり、他の部分は図１
の符号化装置と同一の回路となっている。

【００５４】切替器１３は図１に示した切替器１３と同
様のものであっても構わない。この場合には切替器１３
は符号１０９を生成せず、算術符号出力１１４と特定情
報符号出力１１６をそれぞれのメモリから読み出して算
術復号器１４と特定情報復号器１５に出力する。また、
図５に示した切替器と図１に示した切替器は回線等によ
り接続され、遠隔地に配置されたものであっても構わな
い。その場合、復号化装置の切替器１３は送られてきた
符号１０９から時分割に算術符号と特定情報符号を分離
するか、あるいは多重化されてきたデータを分離する機
能を持つものとする。

【００５５】以下本実施例の動作を説明する。まず、符
号データ系列１０９より、算術復号器により１シンボル
毎算術復号化を行う。算術符号の復号化においては、Ｃ
レジスタの内容である相対座標をＣｉ、第ｉ番目の予測
誤差シンボルａ_i 時点でのＬＰＳの領域幅をＳとする
と、Ｃi-1 ＜（Ａi-1 −Ｓ）ならばａ_i はＭＰＳＡｉ＝Ａi-1 −ＳＣｉ＝Ｃi-1 Ｃi-1 ≧（Ａi-1 −Ｓ）ならばａ_i はＬＰＳＡｉ＝ＳＣｉ＝Ｃi-1 −（Ａi-1 −Ｓ）とする。ここで有効領域Ａｉが１／２以下になった場合
には、演算精度を上げるために正規化処理として２のべ
き乗倍する。このときＣｉの最下位にｎビットの符号デ
ータを入力する。Ａｉ更新値＝Ａｉ＊２^m （１／２＜Ａｉ更新値≦１）Ｃｉ更新値＝Ｃｉ＊２^m

【００５６】予測逆変換器１６では予測誤差シンボルが
ＭＰＳの場合は予測値１０５を、ＬＰＳの場合はその反
転を２値符号化シンボル１０６として１ビット毎再生す
る。そして、２値多値変換器１７において、並べ替え参
照シンボルにより情報源シンボルの再生を行うが、当該
情報源シンボルのレベルが特定できない場合（即ち当該
シンボルに対する２値符号化シンボルが全て１の場合）
は、特定情報復号器により、特定情報を復号し、特定情
報逆変換器１８により情報源シンボルを再生する。

【００５７】例えば、５参照シンボルのレベルが何れも
異なる場合、１ビット算術復号し、 (1) ２値符号化シンボルが“０”の場合Ｘ＝＃１とし、次シンボルの処理へ２値符号化シンボルが“１”の場合１ビット算術復号し(2) へ (2) ２値符号化シンボルが“０”の場合Ｘ＝＃２とし、次シンボルの処理へ２値符号化シンボルが“１”の場合１ビット算術復号し(3) へ (3) ２値符号化シンボルが“０”の場合Ｘ＝＃３とし、次シンボルの処理へ２値符号化シンボルが“１”の場合１ビット算術復号し(4) へ (4) ２値符号化シンボルが“０”の場合Ｘ＝＃４とし、次シンボルの処理へ２値符号化シンボルが“１”の場合１ビット算術復号し(5) へ (5) ２値符号化シンボルが“０”の場合Ｘ＝＃５とし、次シンボルの処理へ２値符号化シンボルが“１”の場合 (6) へ (6) Ｘを特定情報復号器で復号し、次シンボルの処理へ。

【００５８】例えば逆に、５参照シンボルがすべて一致
する場合、１ビット算術復号し、 (1) ２値符号化シンボルが“０”の場合Ｘ＝＃１とし、次シンボルの処理へ２値符号化シンボルが“１”の場合 (2) へ (2) Ｘを特定情報復号器で復号し、次シンボルの処理へという処理を施す。参照シンボル内の生起レベル数が
１，５以外についても同様な処理とする。

【００５９】例えば、図３（ａ）に示す場合には、２値
符号化シンボル１０６において０が復号されてきた場合
には、２値多値変換器１７はシンボル並べ替え器１０か
ら出力されてきた並べ替え参照シンボルの最初のレベル
を用いて情報源シンボル１０１を生成する。あるいは、
２値符号化シンボル１０６が１，０と復号された場合に
は、２値多値変換器１７はシンボル並べ替え器１０から
並べ替えられて出力された並べ替え参照シンボル１１３
の中から２番目のものを情報源シンボル１０１として生
成する。また、図３（ｂ）に示すように、２値符号化シ
ンボル１０６が１，１，１，１，１として復号された場
合には、２値多値変換器１７は情報源シンボル１０１は
シンボル並べ替え器１０から出力される並べ替え参照シ
ンボルのいずれとも一致しないことを判定する。この場
合には、切替器１９は特定情報逆変換器１８からの情報
を用いて情報源シンボル１０１を生成する。また、図３
（ｃ）に示すように、２値符号化シンボル１０６として
１が復号された場合には、２値多値変換器１７はシンボ
ル並べ替え器１０から出力される並べ替え参照シンボル
１１３と情報源シンボル１０１が異なる値を持つことを
検出する。この場合には、切替器１９は特定情報逆変換
器１８からの特定情報信号１１５を用いて情報源シンボ
ル１０１を生成する。これら処理により、情報源シンボ
ル１０１が歪なく再現できる。

【００６０】実施例３．上記実施例においては、次数・予測値メモリ３に格納さ
れる次数・予測値テーブルとして、参照シンボルの一致
状態全てにそれぞれ個別に設定したが、装置規模を縮小
させるため適当な縮退を行うことも可能である。図６は
その一例を示しており、ここでは参照シンボル内の信号
の生起レベル数が同じものは１つに統合している。この
統合したものを、図６中、「参照シンボル中のレベルの
種類」で示している。これにより次数・予測値メモリ３
は１５×（４＋１）ビットで良いこととなる。

【００６１】実施例４．図７は、さらに装置規模を縮小させるため、適当な縮退
を行う場合を示したものである。図７は図６に示したも
のをさらにレベルの種類毎に１つのテーブルを持つよう
に縮退したものである。即ち、参照シンボル内の信号の
生起レベルの数が１，２，３，４，５のいずれの場合で
もテーブルを１つしか持たないようにしたものである。
これにより、次数・予測値メモリ３は５×（４＋１）ビ
ットで良いこととなる。

【００６２】実施例５．また、図８は他の実施例である符号化装置のブロック図
を示している。本実施例においては特定情報の符号化法
として、参照シンボル内に生起したレベル信号と同様の
手法により符号化するものである。このため本実施例の
ブロック構成では、図１の実施例と比べて、特定情報作
成器１１、特定情報符号器１２、切替器１３が削除され
ている。

【００６３】本実施例の符号化手順としては、例えば、
５つの参照シンボルのレベルがいずれも異なる場合 (1) Ｘ＝＃１の場合 “０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃１の場合 “１”を算術符号化し、(2) へ (2) Ｘ＝＃２の場合 “０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃２の場合 “１”を算術符号化し、(3) へ (3) Ｘ＝＃３の場合 “０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃３の場合 “１”を算術符号化し、(4) へ (4) Ｘ＝＃４の場合 “０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃４の場合 “１”を算術符号化し、(5) へ (5) Ｘ＝＃５の場合 “０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃５の場合 “１”を算術符号化し、(6) へ (6) Ｘ＝＃＃１の場合 “０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃＃１の場合“１”を算術符号化し、(7) へ・・・ (255) Ｘ＝＃＃２５０の場合 “０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃＃２５０の場合 “１”を算術符号化し、次符号化対象シンボルの処理へ。

【００６４】ここで＃＃１〜＃＃２５０は、情報源シン
ボルの２５６種のレベル値から参照シンボルパターン中
に生起したものを削除した後、出現確率の大きい順に並
べたものである。ここで、２５５の比較を行っているの
は、２５６種のレベル値しか存在しない場合に２５５ま
での一致、不一致を検出することにより、２５５までの
不一致が検出された場合には、残りの２５６種目のレベ
ル値であることは自動的に判明するためである。

【００６５】５つの参照シンボルがすべて一致する場合
は、 (1) Ｘ＝＃１の場合 “０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃１の場合 “１”を算術符号化し、(2) へ (2) Ｘ＝＃＃１の場合 “０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃＃１の場合“１”を算術符号化し、(3) へ・・・ (255) Ｘ＝＃＃２５４の場合 “０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃＃２５４の場合 “１”を算術符号化し、次符号化対象シンボルの処理へとする。参照シンボル内の生起レベル数が１，５以外の
場合も同様である。

【００６６】図９は＃＃１〜＃＃２５０（あるいは＃＃
２５０〜＃＃２５４）までのシンボルパターンを生成す
る方法を示す図である。図９（ａ）は情報源シンボルが
取り得る２５６種のレベル値から出現確立の大きい順に
並べたパターンテーブルである。符号化装置及び復号化
装置の両方に同一内容のパターンテーブルを用意してお
く。このパターンテーブルは電源ＯＮの時点で互いに通
信し合うことにより、共有することが可能である。ある
いは、変更の必要が生じた際には、その度に互いに通信
してアップデートするようにしても構わない。このよう
に、図９（ａ）に示すようなパターンテーブルが符号化
装置及び復号化装置に設けられているものとする。そし
て、図に示すように、パターンテーブルの中に５つの参
照シンボルがそれぞれ異なるレベルで存在した場合に
は、参照シンボルパターン中に生起したものを削除し、
図９（ｂ）に示すような新たなパターンテーブルを生成
する。この図９（ｂ）に示す新たなパターンテーブルも
出現確立の大きい順に並べたものである。なお、図９に
示す場合には、５つの参照シンボルがいずれも異なる場
合のパターンテーブルの生成方法を示しているが、５つ
の参照シンボルが全て一致する場合には、２５６種のレ
ベル値から１つのレベル値が除かれて新たに２５５種の
レベル値を持つパターンテーブルが生成される。参照シ
ンボル内の生起レベル数が１又は５以外についても同様
にしてパターンテーブルを生成することができる。

【００６７】本実施例の場合、次数・予測値メモリ３の
容量は、図１０に示すように参照シンボル内に生起する
レベルの数（１〜５）にのみ着目するとすれば、各符号
化シンボルとも最大２５５回２値算術符号化を行うこと
から、５×２５５×（４＋１）ビットとなる。

【００６８】実施例６．図１１は、図８の実施例に基づく符号化データを復号す
る復号化装置のブロック構成図である。１４，１６，１
７が算術復号器、予測逆変換器、２値多値変換器となっ
ている以外は、図８の装置と同様の構成である。

【００６９】実施例７．また、図１２は他の実施例である符号化装置のブロック
図を示している。本実施例においては特定情報の符号化
法として、符号化対象シンボルの数値を、ＭＳＢから順
に１ビットずつ２値算術符号化するものである。このた
め本実施例のブロック構成では、図１の実施例と比べ
て、特定情報符号器１２と切替器１３が削除され、特定
情報用多値２値変換器１９及び２値符号化シンボル１０
６とこの特定情報用多値２値変換器１４の出力である特
定情報２値化シンボル１１７を切り替えて予測変換器５
に入力する切替器２０が付加されている。

【００７０】本実施例では、特定情報の符号化以外につ
いては図１の実施例同様の処理を、特定情報の符号化に
ついては、図２５の従来の装置同様の処理を行う。即
ち、例えば、５つの参照シンボルのレベルがいずれも異
なる場合 (1) Ｘ＝＃１の場合 ”０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃１の場合 ”１”を算術符号化し、(2) へ (2) Ｘ＝＃２の場合 ”０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃２の場合 ”１”を算術符号化し、(3) へ (3) Ｘ＝＃３の場合 ”０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃３の場合 ”１”を算術符号化し、(4) へ (4) Ｘ＝＃４の場合 ”０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃４の場合 ”１”を算術符号化し、(5) へ (5) Ｘ＝＃５の場合 ”０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃５の場合 ”１”を算術符号化し、(6) へ (6) ＸのＭＳＢを算術符号化し、(7) へ (7) Ｘの２ｎｄＭＳＢを算術符号化し、(8) へ・・・ (13) ＸのＬＳＢを算術符号化し、次の符号化対象シンボルの処理へ。

【００７１】逆に、５つの参照シンボルがすべて一致す
る場合 (1) Ｘ＝＃１の場合 ”０”を算術符号化し、次符号化対象シンボルの処理へＸ！＝＃１の場合 ”１”を算術符号化し、(2) へ (2) ＸのＭＳＢを算術符号化し、(3) へ (3) Ｘの２ｎｄＭＳＢを算術符号化し、(4) へ・・・ (9) ＸのＬＳＢを算術符号化し、次の符号化対象シンボルの処理へとする。参照シンボル内の生起レベル数が１，５以外の
場合も同様である。

【００７２】図１３は本実施例における特定情報符号化
の際に使用する、次数・予測値メモリ３の内容の一例を
示すものである。本実施例では、次数・予測値メモリ３
の容量としては、図６と図９のテーブルを併せて、（１
５＋２５５）×（４＋１）ビットとなる。

【００７３】実施例８．図１４は、図１２の実施例に基づく符号化データを復号
する復号化装置のブロック構成図である。１４，１６，
１７，１８，２１が算術復号器、予測逆変換器、２値多
値変換器、特定情報逆変換器、特定情報用２値多値変換
器となっており、２値多値変換器１７からの信号及び特
定情報逆変換器１８からの信号を選択して情報源シンボ
ル１０１とする切替器２２が付加された以外は、図１２
の装置と同様の構成である。

【００７４】図１５は、図１２及び図１４の実施例に示
した符号化装置により、１画素８ビットの画像信号を実
際に符号化した場合の１画素あたりの符号ビット数を示
したものである。対象画像としては、自然画像及び、パ
ーソナルコンピュータのメニュー画面で何れもカラー信
号を８ビットのパレットデータで表現したものである。
図には参考のため、従来の実施例で示した縮退のない多
値マルコフモデルに基づく方式、及び、８ビット信号を
ＭＳＢから順に８枚のビットプレーン信号にしてそれを
縦に接続した画像に対して、２値のマルコフモデル符号
化を適応した方式、同じくビットプレーン画像にファク
シミリの標準方式であるＭＭＲ符号化装置５４を適応し
た場合の数値を示す。３種のマルコフモデル符号化にお
いて参照画素数は順に５，１，１０であり、また、次数
・予測値のテーブルサイズは順に、１５＋２５５，２５
６×２５５，２¹⁰である。

【００７５】本シミュレーションでは２値算術符号は、
小野文孝、吉田雅之、木村智広、木野重徳：“ＭＥＬ−
ＣＯＤＥを用いた算術型マルコフモデル符号化”１９９
０年電子情報通信学会春期全国大会、ＳＡ−６−３、
（１９９０）に示された算術型ＭＥＬＣＯＤＥを用い
た。このため符号次数は実施例で示したものと異なり、
３２種である。

【００７６】図で明かなように、従来のマルコフモデル
符号化に比べ、次数・予測値テーブルは１／２４０ある
いは１／３．８であるのにも関わらず、符号化性能は１
６％あるいは４４％向上している。また、ＭＭＲを用い
た方式に比べると、約２．３倍の圧縮性能向上が可能で
ある。

【００７７】また、自然画像とパレット画を比べてみ
る。自然画像のほうは本発明の方式を用いた場合には、
さほど符号化精度は上がっていないが、パレット画を用
いた場合には、自然画像に比べて符号化精度がより向上
している。このことから、アニメーションによる画像や
コンピュータによるグラフィック画像やメニュー画像等
のコンピュータプログラムによる画像の場合には、本発
明の方式がより圧縮性能が向上していることがわかる。
また、８ビット信号をＭＳＢから順に８枚のビットプレ
ーン信号にして、それを縦に接続した画像に対して未知
のマルコフモデル符号化を適応した方式５３と本発明の
方式５１を比較すると、方式５３の場合には、参照画素
数を１０用いるのに対し、本発明の方式では、参照画素
数が５を用いているにもかかわらず、方式５３に比べて
方式５１は符号ビット数が少なくなっており、数多い参
照画素数を持っているにもかかわらず方式５３は方式５
１に比べて符号化性能が劣るいうことがわかる。

【００７８】実施例９．上記実施例においては、いずれも、次数・予測値メモリ
３の初期値については特別な設定を行わないとした（例
えば各テーブルとも次数は最小値１、予測値は０）が、
予め符号化対象情報源の統計量を測定して適当な初期値
を設定しておくこともできる。この場合、符号化装置、
復号化装置間に暗黙の前提で共通の初期値を利用する方
式、いくつかの典型的な初期値セットを用意しておき、
その何れであるかを符号化／復号化に先だって指示する
方式、また、全ての初期値を符号化／復号化に先だって
指定する方式などが可能である。

【００７９】例えば、２値シンボルの出現確率を識別す
る信号として、予め対象情報源の符号化を行って次数・
予測値メモリ３に格納されたデータを用いることもでき
る。予め対象情報源の符号化を行うということは、実際
の符号化に先だって対象情報源の一部をプリスキャンす
ることによりその対象情報源の持つシンボルの出現確立
を前もって学習することを意味している。この場合、次
数、予測値メモリ３の内容はホスト（制御装置）側に吸
い上げられる（アップロードする）構成にするととも
に、符号化に先だってこのデータを復号化装置にダウン
ロードできる構成にすれば良い。図１６及び図１７は次
数・予測値メモリ３の内容をアップロード、あるいはダ
ウンロードする場合の構成例を示したものである。図１
６及び図１７において、６０は次数・予測値メモリ３の
内容をアップロードし、ホスト６１に送信する更新器、
あるいはホスト６１からメモリの内容を受信し、次数・
予測値メモリ３の内容を更新する更新器である。図１の
実施例の場合はこのデータサイズとしては、上記のよう
に、１５１×５ビットとなる。

【００８０】実施例１０．上記実施例では、２値算術符号化の各ステップにおいて
シンボル出現確率を識別する次数・予測値メモリ３の内
容を符号化の中で更新する例を示したが、上記のように
次数・予測値メモリ３のダウンロードの機能を持たせる
ことで、単一の情報源符号化処理の間は、これを更新し
ない構成にしても良い。これにより、符号化／復号化処
理の高速化が可能である。前述した図１６及び図１７は
この実施例の構成を示しており、図１に示したように、
次数・予測値メモリ制御回路８が存在しないために、次
数・予測値メモリ３の内容を符号化の過程で更新するこ
とはできない。しかし、代わりに更新器６０が存在して
いるため、次数・予測値メモリ３に対してメモリの内容
全体を更新する機能を持たせることが可能になる。

【００８１】実施例１１．上記実施例においては、算術符号器及び算術復号器を用
いて符号化する場合について説明したが、算術符号器及
び算術復号器を用いる場合に限らず、その他の符号器、
あるいは復号器を用いる場合であっても構わない。図１
８は算術符号器の代わりにブロック型２値符号器７０を
用いる場合を示している。これは電子通信学会論文誌別
冊「１，２値情報源の符号化圧縮」（大西、上野、小
野：Trens.IECE’77/12 Vol.60-A No.12, pp.1114-112
1）に示された２値情報源の符号化を行うための符号器
である。図１９は前述した論文に示された符号化装置の
一例を示す図である。ブロック型２値符号器７０は２値
情報源を図１９に示したような符号化装置に従って符号
化する際には、優勢シンボルの出現確率をｋとしてｋ＞
ｋ^m ＋ｋ^m+1 ≧１を満たす次数ｍを選べば最も符号化効
率が高いことを利用して符号化を行うものである。図１
９おけるＭは図１８における次数１０４に相当してお
り、また、図１９における通報は図１８における予測誤
差シンボル１０７に相当している。ブロック型２値符号
器７０は次数Ｍと通報１０７を入力することにより、図
１９に示すような符号形式に従って符号化を行うもので
ある。なお、図示しないが、復号化装置においてはブロ
ック型２値復号器というものを備え、図１８に示したブ
ロック型２値符号器７０と逆の動作を行うことにより、
入力した符号から２値符号化シンボルを再生する。

【００８２】実施例１２．図２０はさらに、算術符号器の代わりにハフマン符号器
８０を用いて符号化する場合を示す図である。図におい
て、９０は情報源シンボル１０１のレベルから２５６の
値を出力するレベル変換器、８０はハフマン符号器１か
らハフマン符号器５を備えているハフマン符号器、９
１，９２はハフマン符号器１からハフマン符号器５のい
ずれかを選択するセレクタ、２はセレクタ９１及び９２
に対してハフマン符号器１〜５のいずれかを選択する選
択アドレス信号を出力する選択する選択アドレス生成器
である。

【００８３】次に、図２１は図２０に示した符号化装置
の動作を説明するための図である。ハフマン符号器１は
例えば、５つの参照シンボルの全てのレベルが一致した
場合に情報源シンボルを符号化する符号器である。ハフ
マン符号器２は、５つの参照シンボルのうち、２つのレ
ベルが生起した場合に情報源シンボルを符号化する符号
器である。同様に、ハフマン符号器３，４，５は５つの
参照シンボルのうち、３つのレベル、４つのレベル、５
つのレベルが生起した場合に情報源シンボルを符号化す
る符号器である。選択アドレス生成器２は、一致信号１
１２を入力することにより、５つの参照シンボルの中に
いくつのレベルが生起したかどうかを判定し、生起した
レベルの数に基づいていずれのハフマン符号器を選択す
るかを決定する。例えば、５つの参照シンボルのレベル
が全て同じ場合は、レベル数が１となり、ハフマン符号
器１を選択するように選択アドレス信号１０３を出力す
る。セレクタ９１及び９２はハフマン符号器１を選択す
る。

【００８４】一方、レベル変換器９０は情報源シンボル
１０１とシンボル並べ替え器１０から入力された並べ替
え参照シンボルを比較し、いずれのレベルと一致するか
を比較する。例えば、レベル数が１であり、＃＃１，＃
＃２，＃＃２５５は図９に示したものと同様に出現確率
の高い順に予めパターンテーブルとして登録されている
ものとする。もし、情報源シンボル１０１のレベルが＃
１と一致した場合には、Ｎｏ．０を出力する。あるい
は、情報源シンボル１０１のレベルが＃＃１と一致した
場合には、Ｎｏ．１を出力する。ハフマン符号器はレベ
ル変換器から出力されるＮｏ．１〜Ｎｏ．２５５の番号
に従ってその番号に対応するハフマン符号を符号として
出力する。例えば、図２１に示したように、レベル数が
１であり、＃１と一致した場合には、Ｎｏ．０が出力さ
れ、ハフマン符号器１はハフマン符号として“１１”を
出力する。また、レベル数が２であり、情報源シンボル
が＃２と一致した場合には、Ｎｏ．１が出力され、ハフ
マン符号器２はＮｏ．１に対応する符号として“０１”
を出力する。このように、この実施例では、前述した算
術符号器の代わりにハフマン符号器を用いる場合につい
て説明した。前述した実施例１１及びこの実施例１２に
示すように、符号化装置は算術符号器に限らずその他の
符号器であっても構わない。また、実施例１１及び実施
例１２に示した符号器以外の符号器であっても構わな
い。

【００８５】実施例１３．上記実施例においては、一致検出器９により参照シンボ
ルパターンの中に一致するものが存在するかどうかを検
出していたが、図２２に示すように、一致検出器が存在
しない場合であっても構わない。一致検出器９が存在し
ない場合には、シンボル並べ替え器１０は参照シンボル
作成器から出力される参照シンボルパターン１０２を全
て並べ替え、参照シンボル１１３として出力する。例え
ば、５つの参照シンボルを用いる場合には、５つの参照
シンボルＡ，Ｂ，Ｃ，Ｄ，Ｈが常に並べ替え参照シンボ
ル１１３として多値２値変換器４に対して出力される。
もし、情報源シンボル１０１がこれら５つの参照シンボ
ルの中に常に存在する場合には、多値２値変換器４から
の出力である２値符号化シンボル１０６が一致検出器９
があってもなくても同様の出力を行う。即ち、出力する
２値符号化シンボル１０６の長さには変化はない。しか
し、情報源シンボル１０１が並べ替え参照シンボル１１
３の中に存在しない場合には、図２２に示す例において
は、常に５ビットの“１”が出力されることになる。そ
して、特定情報作成器１１により特定情報信号１１５が
出力される。図２２に示す方式によれば、情報源シンボ
ル１０１が参照シンボルと同じレベルを取る確率が高い
場合ほど、一致検出器９が存在しないことによるデメリ
ットがなくなる。なお、図示しないが、前述した各実施
例において一致検出器９が存在しないようにしても構わ
ない。

【００８６】実施例１４．上記実施例においては参照シンボルの数が５つの場合を
示したが、参照シンボルの数は５つに限らず、１つ、あ
るいは１つ以上の場合であっても構わない。

【００８７】実施例１５．上記実施例は、全てＨ／Ｗにより符号化する例を示した
が、本処理をＳ／Ｗプログラミングにより実現する場合
においても同様の効果を奏する。

【００８８】

【発明の効果】以上のように、この発明によれば、多値
マルコル情報源の符号化に当たり、あらかじめ定められ
た位置関係にある複数の先行シンボル（参照シンボル）
に着目し、それらが互いに等しいか否かを示す信号、あ
るいは、参照シンボル内に生起した多値レベルの種類の
数によりマルコフ状態を分離して符号化することによ
り、符号化効率を大幅に向上させるとともに、装置規模
の小さな符号化又は復号化装置を実現することができ
る。

【図面の簡単な説明】

【図１】本発明の一実施例による符号化装置のブロック
構成図である。

【図２】図１の実施例における次数・予測値メモリの内
容を説明する図である。

【図３】図１の実施例における２値符号化シンボルと特
定情報信号の具体例を示す図である。

【図４】図１の実施例おける次数・予測値メモリの内容
の一例を説明する図である。

【図５】本発明の他の実施例による復号化装置のブロッ
ク構成図である。

【図６】本発明の一実施例における次数・予測値メモリ
の内容の他の一例を説明する図である。

【図７】本発明の一実施例における次数・予測値メモリ
の内容の他の一例を説明する図である。

【図８】本発明の他の実施例を示す符号化装置のブロッ
ク構成図である。

【図９】本発明の他の実施例におけるパターンテーブル
の作成方法を示す図である。

【図１０】本発明の他の実施例における次数・予測値メ
モリの内容を説明する図である。

【図１１】本発明の他の実施例を示す復号化装置のブロ
ック構成図である。

【図１２】本発明の他の実施例を示す符号化装置のブロ
ック構成図である。

【図１３】図１２の実施例おける次数・予測値メモリの
内容の一例を説明する図である。

【図１４】本発明の他の実施例を示す復号化装置のブロ
ック構成図である。

【図１５】本発明の他の実施例および従来方式の符号化
データの圧縮性能を示す図である。

【図１６】本発明の他の実施例を示す符号化装置のブロ
ック構成図である。

【図１７】本発明の他の実施例を示す復号化装置のブロ
ック構成図である。

【図１８】本発明の他の実施例を示す符号化装置のブロ
ック構成図である。

【図１９】図１８の実施例における符号原理を説明する
図である。

【図２０】本発明の他の実施例を示す符号化装置のブロ
ック構成図である。

【図２１】図２０の実施例におけるレベル変換器、及び
ハフマン符号器の動作を説明する図である。

【図２２】本発明の他の実施例を示す符号化装置のブロ
ック構成図である。

【図２３】従来の技術による符号化装置のブロック構成
図である。

【図２４】符号化対象画素と参照画素の位置関係を示す
図である。

【図２５】従来の技術による次数・予測値メモリの内容
の一例を説明する図である。

【図２６】算術符号化の次数と領域幅の対応の一例を示
す図である。

【符号の説明】

１参照シンボル作成器３次数・予測値メモリ４多値２値変換器７算術符号器８次数・予測値制御回路９参照シンボルの一致検出器１０参照シンボル並べ替え器１１特定情報作成器１２特定情報符号器１４算術復号器１５特定情報復号器１７２値多値変換器１８特定情報逆変換器１９特定情報多値２値変換器２１特定情報２値多値変換器６０更新器６１ホスト７０ブロック型２値符号器８０ハフマン符号器９０レベル変換器９１，９２セレクタ

───────────────────────────────────────────────────── フロントページの続き (58)調査した分野(Int.Cl.⁷，ＤＢ名) H03M 7/40

Claims

(57)【特許請求の範囲】

【請求項１】多値マルコフ情報源からの符号化シンボ
ルを符号化する符号化装置において、符号化する符号化シンボルに先行する複数の先行シンボ
ルを複数の参照シンボルとして抽出する参照シンボル作
成手段と、参照シンボル作成手段により抽出された複数の参照シン
ボルのレベルが互いに等しいか否かを検出する一致検出
手段と、一致検出手段により検出されたレベルが異なる参照シン
ボルと符号化シンボルとを比較し、比較結果に基づいて
符号化シンボルのレベルを変換する変換手段と、変換手段により変換された出力を符号化する符号化手段
とを備えたことを特徴とする符号化装置。
【請求項２】上記符号化装置は、さらに、参照シンボ
ル内に生起した多値レベルの種類の数を検出する手段を
有し、これによりマルコフ状態を分離して符号化するこ
とを特徴とする特許請求の範囲第１項記載の符号化装
置。
【請求項３】各マルコフ状態におけるシンボル符号化
に当たっては、上記参照シンボルで重複するレベルを有
するシンボルを削除した後に予め定められた順序にシン
ボルを並べ替える手段と、符号化シンボルが該並び替え
た各シンボルと等しいか否かを示す信号を生成する多値
２値変換手段と、これを順に２値算術符号により符号化
する手段を有し、符号化シンボルと該並び替えたシンボ
ルと等しくなった場合には、この算術符号化により当該
符号化シンボルの符号化処理を終了とすることを特徴と
する特許請求の範囲第１項又は第２項記載の符号化装
置。
【請求項４】符号化シンボルのレベルが上記参照シン
ボル内に生起しない場合、符号化シンボルのレベルを特
定するための情報を生成する手段と、この情報を上記２
値算術符号とは別に符号化する符号化手段を有すること
を特徴とする特許請求の範囲第３項記載の符号化装置。
【請求項５】符号化シンボルのレベルが上記参照シン
ボル内に生起しない場合、上記並び替えた参照シンボル
の後に上記並び替えた参照シンボルのレベル以外のレベ
ルからなる信号系列を生成する手段と、符号化シンボル
がこの信号系列の各レベル信号と等しいか否かを生成す
る多値２値変換手段とを有し、この変換手段からの２値
信号を符号化シンボルのレベルが上記参照シンボル内に
生起する場合と同様の手法により２値算術符号化するこ
とを特徴とする特許請求の範囲第３項記載の符号化装
置。
【請求項６】符号化シンボルのレベルが上記参照シン
ボル内に生起しない場合、符号化シンボルのレベルを特
定するための必要なビット数の情報を生成する手段と、
この特定情報を１ビットずつ選択する手段を有し、上記
多値２値変換手段からの信号に引き続き、この選択手段
からの特定情報を１ビットずつ２値算術符号化すること
を特徴とする特許請求の範囲第３項記載の符号化装置。
【請求項７】各マルコフ状態の各２値算術符号化のス
テップごとに、２値シンボル出現確率を符号化の中で更
新する手段を有することを特徴とする特許請求の範囲第
１項〜第５項、又は第６項記載の符号化装置。
【請求項８】各マルコフ状態の各２値算術符号化のス
テップごとの２値シンボル出現確率を識別する信号を生
成する手段を有し、情報源シンボル系列の符号化に先立
ってこの出現確率を識別する信号をメモリに設定するこ
とを特徴とする特許請求の範囲第１項〜第６、又は第７
項記載の符号化装置。
【請求項９】多値情報源シンボルを符号化する符号化
装置において、符号化する多値情報源シンボルに先行する複数の先行シ
ンボルを複数の参照シンボルとして抽出する参照シンボ
ル作成手段と、参照シンボル作成手段により抽出された複数の参照シン
ボルを参照シンボルのレベルに基づいて並べ替えるシン
ボル並べ替え手段と、シンボル並べ替え手段により並べ替えられた参照シンボ
ルのレベルと符号化する多値情報源シンボルのレベルと
を比較し、符号化する多値情報源シンボルのレベルが参
照シンボルのいずれのレベルと一致するか又は参照シン
ボルのいずれのレベルとも一致していないかということ
を判定して、その判定結果を多値情報源シンボルの変換
結果として出力する変換手段と、変換手段により出力された判定結果を符号化する第１の
符号化手段と、多値情報源シンボルのレベルが参照シンボルのいずれの
レベルとも一致しない場合、符号化する多値情報源シン
ボルを特定する情報を符号化する第２の符号化手段とを
備えたことを特徴とする符号化装置。
【請求項１０】多値マルコフ情報源からの符号化シン
ボルを符号化したデータを復号化する復号化装置におい
て、符号化されたデータを復号化する復号化手段と、復号化する符号化シンボルに先行する複数の先行シンボ
ルを複数の参照シンボルとして抽出する参照シンボル作
成手段と、参照シンボル作成手段により抽出された複数の参照シン
ボルのレベルが互いに等しいか否かを検出する一致検出
手段と、一致検出手段により検出されたレベルが異なる参照シン
ボルを用いて、復号化手段により復号化されたデータを
符号化シンボルへ変換する変換手段とを備えたことを特
徴とする復号化装置。
【請求項１１】多値情報源シンボルを符号化したデー
タを復号化する復号化装置において、多値情報源シンボルを符号化したデータには、復号化す
る多値情報源シンボルが参照シンボルのいずれのレベル
と一致しているか又は参照シンボルのいずれのレベルと
も一致していないかという判定結果と復号化する多値情
報源シンボルを特定する情報とが含まれており、復号化する多値情報源シンボルに先行する先行シンボル
を複数の参照シンボルとして抽出する参照シンボル作成
手段と、参照シンボル作成手段により抽出された複数の参照シン
ボルを参照シンボルのレベルに基づいて並べ替えるシン
ボル並べ替え手段と、復号化する多値情報源シンボルが参照シンボルのいずれ
のレベルと一致しているか又は参照シンボルのいずれの
レベルとも一致していないかという判定結果を復号化す
る第１の復号化手段と、第１の復号化手段により復号化された判定結果が、復号
化する多値情報源シンボルのレベルが参照シンボルのい
ずれかのあるレベルと一致しているということを示して
いる場合、その判定結果を並べ替え手段により並べ替え
られた参照シンボルの当該レベルへ変換して多値情報源
シンボルとして出力する変換手段と、復号化する多値情報源シンボルが参照シンボルのいずれ
のレベルとも一致していない場合、多値情報源シンボル
を符号化したデータに含まれている情報であって、復号
化する多値情報源シンボルを特定する情報を復号化して
多値情報源シンボルとして出力する第２の復号化手段と
を備えたことを特徴とする復号化装置。