JP3847891B2

JP3847891B2 - 符号化装置及び方法及び方法を記憶した記憶媒体

Info

Publication number: JP3847891B2
Application number: JP9219297A
Authority: JP
Inventors: 浩梶原
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 1997-04-10
Filing date: 1997-04-10
Publication date: 2006-11-22
Anticipated expiration: 2017-04-10
Also published as: JPH10285601A

Description

【０００１】
【発明の属する技術分野】
本発明は画像データの符号化を行う符号化装置及び方法及び方法を記憶した記憶媒体に関するものである。
【０００２】
【従来の技術】
従来、画像符号化装置で使用される画像符号化方式の一つとして予測符号化方式がある。
【０００３】
予測符号化方式は、符号化対象画素の画素値を周囲の画素から予測し、予測誤差をエントロピ−符号化するものである。これは予測方式を幾つか用意し、周囲の画素に応じて予測方式を適応的に選択してエントロピ−符号化するなど、予測符号化方式をベ−スとした種々の改良方式が提案されている。
【０００４】
【発明が解決しようとする課題】
しかしながら、予測値と符号化対象画素値との予測誤差をエントロピー符号化する場合において、予測誤差Diffが同じ絶対値を有するにもかかわらず符号長が異なる様なエントロピ−符号化に対して、符号化効率を良くする為に依然改善の余地があった。
【０００５】
本発明は上記従来例に鑑みて成されたものであり、予測値と符号化対象画素値との予測誤差をエントロピー符号化する様な場合において、符号化効率を更に向上する為の構成を提供することを目的とする。
【０００６】
具体的には、予測値と符号化対象画素値との予測誤差をエントロピー符号化する様な予測符号化モードを含む複数の符号化モードを切り換えて使用するものにおいて、効率良く符号化を行うことを目的とする。
【０００７】
【課題を解決するための手段】
上述の課題を解決するために本発明の符号化装置によれば、ラスタースキャン順に入力された画素を順次符号化する符号化装置であって、符号化対象画素の周囲画素の状態を判別する状態判別手段と、符号化対象画素の周囲画素に基づいて第１の予測アルゴリズムで予測値を発生し、該予測値と前記符号化対象画素値との予測誤差をＧｏｌｏｍｂ−Ｒｉｃｅ符号化する第１符号化手段と、ランレングス値ＲＬを保持し、符号化対象画素と直前に符号化された画素と画素値が一致する場合にはランレングス値ＲＬをカウントアップし、不一致の場合にはランレングス値ＲＬをＭｅｌｃｏｄｅ符号化する第２符号化手段と、符号化対象画素の周囲画素に基づいて第１とは異なる第２の予測アルゴリズムで予測値を発生し、該予測値と前記符号化対象画素値との予測誤差をＧｏｌｏｍｂ−Ｒｉｃｅ符号化する第３符号化手段と、各符号化対象画素に対して、符号化対象画素の周辺画素の状態及びランレングス値ＲＬに基づいて第１及び第２符号化手段の何れか一方の符号化を施し、第２符号化手段の符号化時に前記不一致の場合には更に前記第３符号化手段による符号化を施す符号化モード選択手段とを備え、前記第３符号化手段は、Ｇｏｌｏｍｂ−Ｒｉｃｅ符号化に用いられるｋパラメータの値が０である場合で、かつ該第３符号化手段による符号化において符号化対象画素の前画素までに対する正の予測誤差と負の予測誤差のうちでより多く発生している方に長い符号長が割り当てられている場合に、前記符号化対象画素に対応する予測誤差の正負の符号を反転させることを特徴とする。
【０００８】
【発明の実施の形態】
（第１の実施の形態）
次に、本発明の第１の実施の形態について図面を参照して詳細に説明する。
【０００９】
図１に本発明に係る第１の実施の形態の構成図を示す。同図において１００は信号を入力するための入力部、１０１は信号線、１０２は予測変換回路、１０４はGolomb−Rice符号化回路、１０５は予測変換回路、１０６は符号予測変換回路、１０７はGolomb−Rice符号化回路、１０８はランレングスカウンタ、１０９はMelcode符号化回路、１１０は状態判別回路、１１１はモ−ドセレクタ、１１２はスイッチ、１１３はスイッチ、１１４は信号線、１１５は２ライン分の画像デ−タを格納するバッファである。
【００１０】
本実施の形態では３つのモ−ドを切り換えて符号化処理を行なう。具体的には、１つ目のモ−ドとして予測変換回路１０２及びGolomb−Rice（ゴロ−ムライス）符号化回路１０４で符号化処理を行なうノ−マルモ−ド、２つ目のモ−ドとしてランレングスカウンタ１０８及びMelcode（メルコ−ド）符号化回路１０９により符号化処理するランレングスモ−ド、３つ目のモ−ドとして予測変換回路１０５及び符号予測変換回路１０６及びGolomb−Rice符号化回路１０７により符号化処理を行なうラン終端モ−ドである。
【００１１】
次に、１画素８ビット（０から２５５の値）のモノクロ画像信号を符号化する場合を例に、本実施の形態での各部の動作を順に説明する。しかしながら、本発明はこれに限らずRGBの各８ビットの色成分、又はLabの各８ビットの輝度色度成分からなる多値カラ−画像を符号化する場合にも適用でき、各成分を上記モノクロ画像信号と同様に符号化すればよい。
【００１２】
また各成分の符号化切換単位は、画面毎に行うこともでき、これによれば画像全体の様子を復号化側で早めに確認することが可能となる。また各成分の符号化切換単位は、画素毎、１ライン毎、複数ラインから成るバンド毎に行うこともでき、これによれば部分的ではあるが完全なカラー画像を早めに見ることができる。
【００１３】
なお、バッファ１１５の内部の値は初期値をすべて０に設定しておくものとする。
【００１４】
まず、入力部１００から符号化対象となる画素（符号化対象画素）がラスタ−スキャン順に入力され、信号線１０１を通じてスイッチ１１２、バッファ１１５へ入力される。
【００１５】
バッファ１１５は信号線１０１から順次入力される画像デ−タを２ライン分格納する。この２ラインは符号化対象画素のラインとその１つ前のラインである。状態判別回路１１０は、符号化対象画素の周辺画素の状態を表す状態番号Sとその位相を表す位相フラグRを生成するものであり、以下の処理を行う。まず、符号化対象画素の周辺画素a，b，c，dに対応する画素デ−タをバッファ１１５から読み出す。
【００１６】
図２に符号化対象画素xに対する周辺画素a，b，c，dの位置関係を示す。図２において周辺画素a，b，c，dは、符号化対象画素xに対する既に符号化済みの画素である。次に読み出した画像デ−タa，b，c，dを用いてd−b，b−c，c−aを求め、各々図３に示す対応に従って−４、−３、−２、−１、０、１、２、３、４の９レベルの値に量子化し、量子化値q（d−b），q（b−c），q（c−a）を求める。
【００１７】
次に、q（d−b）×８１＋q（b−c）×９＋q（c−a）の計算式により周辺画素の状態を表す状態番号Sを生成する。次に状態番号Sの符号の正負を調べ、正である場合には位相フラグを０に設定し、負である場合には位相フラグを１に設定すると共に状態番号Sの正負を反転（正の値に反転）する。以上の処理により、０から３６５までの値をとる状態番号Sと、０または１の値をとる位相フラグRが生成され、出力される。
【００１８】
モ−ドセレクタ１１１は状態判別回路１１０の生成された状態番号Sとランレングスカウンタ１０８の生成するラン長RL、符号化制御信号Ｑに基づいて、符号化モ−ドを選択し、スイッチ１１２およびスイッチ１１３の切換制御を行う。ランレングスカウンタ１０８からのラン長RLの初期値は０とする。
【００１９】
図８に符号化対象画素の１画素に対するモ−ドセレクタ１１１による全体的な符号化モ−ド制御の流れを示す。なお、以下の各ステップの詳細な動作は後述する。
【００２０】
まずSTEP８０１においてモ−ドセレクタ１１１は、最初に符号化対象画素に対応する状態番号Sとラン長RLを入力し、S≠０かつRL＝０と判別した場合にはSTEP８０２へ、それ以外の場合にはSTEP８０３へ処理を進める。
【００２１】
STEP８０２ではスイッチ１１２を端子Cに、スイッチ１１３を端子C’に接続し、ノ−マルモ−ドの符号化を行なう。一方、STEP８０３ではスイッチ１１２を端子Aに、スイッチ１１３を端子A’に接続し、ランレングスモ−ドの符号化即ちラン長の符号化を行う。ランレングスモ−ドの詳細な符号化処理については後述するが、ランレングスモ−ドで実際に符号が出力されるのは画素毎ではなくラン長が確定した場合、すなわち同一画素値の連続がとぎれた場合のみである。この場合、符号化制御信号cの値は’０’から’１’となる。
【００２２】
ステップ８０３の後、ステップ８０４では符号化制御信号cの値を調べ、c＝１の場合にはステップ８０５へと処理を進める。ステップ８０５ではスイッチ１１２を端子Bに、スイッチ１１４を端子B’に接続し、ラン終端モ−ドでの符号化処理を行なう。以上の制御を１画素毎に繰り返して行い、３つの符号化モ−ドを選択して符号化処理する。
【００２３】
上記３つの符号化モードを切り換える理由、即ち３つの符号化モードの役割について簡単に述べる。
【００２４】
ノーマルモードは、予測変換した場合の予測誤差がラプラス分布になるであろうと推測される画素の符号化に適用されるものである。但し、同一輝度レベルの連続が期待される様な場合（周辺画素が同一輝度レベルであるような場合）にはランレングスモードに切り換えることにより、更に符号化効率を上げるものである。
【００２５】
ランレングスモードは、同一輝度レベルの連続が期待される様な場合に用いられるモードであり、予測誤差を符号化するのではなく画素値のラン長を符号化（ランレングス符号化）する。これにより、前記ノーマルモード（予測誤差のHuffman符号化,Golomb-Rice符号化などを用いた場合）では１サンプル当たり１ビット以下では符号化できないが、ランレングスモードでは１サンプル当たり１ビット以下での符号化も可能となり、符号化効率が良くなる。
【００２６】
ラン終端モードは、同一輝度レベルのランが終端した際の符号化対象画素を符号化するものである。また、この画素の値は、ランレングス符号化におけるラン長の終端であるから、直前の画素値ではないことが分かっている。そのため、ノーマルモードのように直前の画素値を予測値とした場合には、予測誤差０は発生せず符号化効率が良くならない様な特殊な状態である。この様な状態であることを考慮して、ランレングスモードが終わった画素、即ち直前の画素との画素値が変化した符号化対象画素はノーマルモードではなくラン終端モードにより符号化を行う。また、上記状態における符号化対象画素を予測符号化した場合には、予測誤差の分布は離散的になることが多く、ラプラス分布からはほど遠いものとなることが推測される。このような条件下ではノーマルモードで用いる後述の予測値修正はあまり有効でないので、これを用いずに符号化する。そして次の符号化対象画素からは直前の画素値を予測値として符号化しても十分符号化効率が良くなる。
【００２７】
以下上述した３つの各符号化モードについて個別に説明する。
【００２８】
まず、予測変換回路１０２とGolomb−Rice符号化回路１０４により符号化処理を行なうノ−マルモ−ドの符号化処理について説明する。
【００２９】
図１の予測変換回路１０２は、符号化対象画素の周囲画素a，b，cから符号化対象画素の画素値を予測し、この予測により発生した予測値と符号化対象画素の実際の画素値との差分（予測誤差）Diff及び後述するパラメ−タkを生成する。図４に予測変換回路１０２の内部構成図を示す。
【００３０】
図４において４０１は予測器、４０２はエラ−フィ−ドバック回路、４０３は予測誤差生成回路、４０４はメモリ、４０５はパラメ−タ更新回路、４０６はkパラメ−タ生成回路である。また、図１には図示されていないが予測変換回路１０２には図１のバッファ１１５から周辺画素a，b，cの画素値のデータ、状態判別回路１１０から状態Sと位相フラグRが入力される。また、スイッチ１１２の端子Cから符号化対象画素の画素値xが入力される。
【００３１】
メモリ４０４には個々の状態番号Sに対する４つのパラメ−タN，A，Bγ，Cαが格納される。これらの値は符号化の開始時にN＝１，A＝４，Bγ＝Cα＝０に初期化される。なお、Nは状態Sの生起回数であり、Aは状態Sにおける予測誤差の絶対値の累計であり、Bγは状態Sにおける予測誤差の累計であり、Cαは予測値を修正する為の修正値である。
【００３２】
以下、図４を用いて予測変換回路１０２の動作を説明する。まず、予測器４０１はバッファ１１５から符号化対象画素の周辺画素a，b，c（位置は図２参照）の画素値を入力し、この画素値a，b，cに基づいて予測値pを生成する。予測値pは以下の式により求める。
【００３３】

【００３４】
エラ−フィ−ドバック回路４０２はメモリ４０４に格納される状態Sにおける後述する予測修正値Cαを用いて予測値pを修正し、修正予測誤差p’を生成する。即ち、状態判別回路１１０から入力される位相フラグRが０ならばp’＝p＋Cαとし、１ならばp’＝p−Cαとする。更に、p’が０未満の場合にはp’＝０とし、p’が２５５以上の場合にはp’＝２５５と制限する。
【００３５】
予測誤差生成回路４０３は符号化対象画素の画素値xと修正予測値p’の差分をとり、予測誤差Diffを求める。位相フラグRが０の場合にはDiff＝x−p’とし、位相フラグRが１の場合にはDiff＝p’−xとする。予測誤差生成回路４０３はDiffが−１２８未満の場合にはDiffに２５５を加え、Diffが１２８以上の場合にはDiffから２５５を引くことにより、Diffの値を−１２８から１２７内で表現することができる。
【００３６】
kパラメ−タ生成回路４０６は、状態Sの生起回数Nと、状態Sでの予測誤差の絶対値の累加値Aをメモリ４０４から読み出し、min（k｜N×２＾k＞＝A）によりGolomb−Rice符号化時に用いるパラメ−タkの値を求める。ここで、min（a|b）は条件bを満たす最小のaを意味する。
【００３７】
パラメ−タ更新回路４０５は、状態Sにおける４つのパラメ−タN，Cα，A，Bγを更新し、N’，Cα’，A’，Bγ’を生成する。まず、Bγ’＝Bγ＋Diff，A’＝A＋｜Diff｜によりBγ’とA’を求める。次にNの値を調べ、Nがしきい値Th１に等しい場合にはN，A，Bγを１/２にする。しきい値Th１はA，Bγ，Nを一定範囲に限定するためのものであり、あらかじめ設定しておく（例えばTh１＝６４）。次に、N’＝N＋１によりNを更新する。
【００３８】
図１２に予測修正値Cαの更新手順を示す。Cα’にCαの値を写した後、まずSTEP１２０１において、Bγ’が−N以下であるかどうかを判定し、−N以下の場合にはSTEP１２０３へ、そうでない場合にはSTEP１２０２へ処理を進める。STEP１２０３ではCα’の値を−１２８と比較し、−１２８より大きい場合にはCα’から１を引く（STEP１２０４）。
【００３９】
次に、Bγ’にNを加える（STEP１２０５）。Bγ’が−N以下である場合にはBγ’＝−N＋１とする（STEP１２０６，１２０７）。STEP１２０２ではBγ’を０と比較し、Bγ’が０以上の場合にはSTEP１２０８へと処理を進め、そうでない場合には更新処理を終了する。STEP１２０８ではCα’の値を１２７と比較し、１２７未満である場合にはCα’に１を加える（STEP１２０９）。次に、Bγ’からNを引く（STEP１２１０）。Bγ’が０以上である場合にはBγ’＝０とする（STEP１２１１，１２１２）。最後に更新されたN’，Cα’，A’，Bγ’で、メモリ４０４に格納されている状態Sにおける４つのパラメ−タN，Cα，A，Bγを置き換える。
【００４０】
以上の処理により、予測変換回路１０２は予測誤差Diffとパラメ−タkとを生成し、Golomb-Rice符号化回路１０４にこれらを出力する。
【００４１】
Golomb−Rice符号化回路１０４は、まず、予測変換回路１０２の出力する予測誤差Diffを次式により非負の整数値Vに変換する。
【００４２】

【００４３】
次にこのVをパラメ−タkに基づいてGolomb−Rice符号化する。非負の整数値Vをパラメ−タkに基づいてGolomb−Rice符号化する符号化手順は次のとうりである。
【００４４】
まず、非負の整数値Vを２進数表現する。次にこれを下位kビット部分と上位の残りのビット部分に分割する。次に下位kビット部分に、上位の残りのビット部分を十進で表現される数だけの’０’を付加し、最後に’１’を追加して符号語とする。具体例を挙げると、k＝２，V＝１３の場合、Vの２進数表現’１１０１’の下位２ビット’０１’に上位の残りのビット部分’１１’の表す数、すなわち３個の’０’を付加して’０１０００’とし、最後に’１’を付加して符号語’０１０００１’を生成するという具合である。
【００４５】
なお、図９に上述の符号化処理を施す場合のパラメ−タk＝０，１，２における非負の整数値と符号語の対応を示す。
【００４６】
Golomb-Rice符号化回路１０４で生成された符号は、スイッチ１１３の端子C’へと出力される。
【００４７】
次に、予測変換回路１０５、符号予測変換回路１０６、Golomb−Rice符号化回路１０７により符号化処理を行なうラン終端モ−ドについて説明する。
【００４８】
予測変換回路１０５は周辺画素値a，bから符号化対象画素値を予測し、予測誤差を生成する。図５に予測変換回路１０５の構成図を示す。同図において５０１は比較器、５０２は予測器、５０３は予測誤差生成回路、５０４はメモリ、５０５はkパラメ−タ生成回路である。また、図１には示されていないが、予測変換回路１０５にはバッファ１１５から周辺画素a，bの画素値のデータが入力される。また、スイッチ１１２の端子Bから符号化対象画素値xが入力される。
【００４９】
メモリ５０４には状態番号Sで特定される各状態に対応する３つのパラメ−タN，A，Bαが格納される。N，A，Bαは画像符号化の開始時にN＝１，A＝４，Bα＝０に初期化される。なお、Nは状態Sの生起回数であり、Aは状態Sにおける予測誤差の絶対値の累計であり、Bαは状態Sにおける負の予測誤差が出現した回数である。
【００５０】
図５を用いて予測変換回路１０５の動作を詳細に説明する。まず、比較器５０１はバッファ１１５から渡される符号化対象画素の周辺画素a，bを比較し、b＜aの場合には１を出力し、そうでない場合には０を出力する。以降、この比較器５０１から出力する値を位相フラグr（１or０）と呼ぶことにする。
【００５１】
予測器５０２は周辺画素a，bから予測値pと状態番号Sを生成する。状態番号Sの値はa＝bの場合には１、a≠bの場合には０となる。また、予測値pは常にbとする。
【００５２】
予測誤差生成回路５０３は符号化対象画素値xと予測値pより予測誤差Diffを生成する。位相フラグrが０の場合にはDiff＝x−pとし、位相フラグrが１の場合にはDiff＝p−xとする。
【００５３】
kパラメ−タ生成回路５０５は予測器５０２から状態S、メモリ５０４から状態Sの生起回数Nと状態Sでの予測誤差の絶対値の累加値Aを読み出し、次式によりTを求める。
【００５４】

【００５５】
min（k|N×２＾k＞＝T）によりGolomb−Rice符号化時のパラメ−タkの値を求め、出力する。
【００５６】
パラメ−タ更新回路５０６は、状態Sにおける３つのパラメ−タN，A，Bαを更新し、N’，A’，Bα’を生成する。まず、A’＝A＋|Diff|によりA’を求める。次にDiffの正負を調べ、正である場合にはBα’＝Bαとし、負である場合にはBα’＝Bα＋１とする。即ちBαは予測誤差Diffが負であった回数を示すものとなる。また、N’＝N＋１によりN’を求める。
【００５７】
最後に更新されたN’，A’，Bα’で、メモリ５０４に格納されている状態Sにおける３つのパラメ−タN，A，Bαを置き換える。
【００５８】
以上の処理により、予測誤差Diff、kパラメ−タ、状態番号S、状態番号Sの状態における２つのパラメ−タBα，Nを出力する。
【００５９】
符号予測変換回路１０６は、kパラメ−タが０の場合に、BαとNの値から予測誤差Diffの符号（＋/−）を予測し、予測結果に基づいてDiffの符号を変更する。
【００６０】
図６に符号予測変換回路１０６の構成を示す。同図において６０１は反転判定回路、６０２は符号反転回路、６０３はセレクタである。
【００６１】
図６を用いて符号予測変換回路１０６の動作を詳細に説明する。まず、反転判定回路６０１は、k＝０の場合でありかつBα＞N/２の場合に符号反転を指示する信号’１’を、それ以外の場合には符号反転をしないことを指示する信号’０’を出力する。符号反転回路６０２は、この指示信号（１or０）に基づいて符号化対象画素に対応するDiffの符号（＋/−）を反転し、−Diffを信号線６０４に出力する。セレクタ６０３は反転判定回路６０１の出力値が’０’の場合は信号線６０５を通じて入力されるDiffを選択して出力し、’１’の場合には符号反転回路６０２の出力値−Diffを出力する。
【００６２】
以上の処理により、符号予測反転回路１０６は入力値Diffに対し、Diffまたは−Diffを選択して出力する。
【００６３】
ここで、上記符号反転の役割を簡単に説明する。kパラメ−タが０の場合及びkパラメ−タが２の場合のGolomb-Rice符号化の符号化割り当ては図１３の様になる。図１３においてkパラメ−タが０の場合とは符号化画素を含めた周辺画素の値の変動が少ない場合を意味する。よってGolomb-Rice符号化を行った時の整数値Vと符号化出力及び符号長は図のような関係になっている。
【００６４】
一方、kパラメ−タが２の場合は、０の場合と比べ多少符号化画素を含めた周辺画素の値の変動が大きくなっていることを表しているので、これに適した符号化が行えるよう、Golomb-Rice符号化を行った時の後述する整数値V又は予測誤差Diffと、符号化出力又は符号長は図のような関係になっている。
【００６５】
ここで、kパラメ−タが０の場合には、予測誤差Diffが同じ絶対値を有するにもかかわらず必ず符号長が異なるという特徴がある。これに対してkパラメ−タが０以外の値（例えば２）の場合には、予測誤差Diffが同じ絶対値を有するものは同じ符号長になることが多い。
【００６６】
この符号化特性を考慮して、kパラメ−タが０の場合かつBα＞N/２の場合（状態Sにおける予測誤差が負であった回数が過半数を超える場合）に符号反転を行い、それ以外の場合には符号反転をしない様にすれば、同じ絶対値を有する予測誤差Diff（例えば−１と１）で発生頻度が多い方を符号長の短い符号化出力とすることが可能となる。
【００６７】
即ち、−１の方が発生頻度が多ければ符号予測反転回路１０６の符号反転はしないで良しとし、−１の方が発生頻度が少ない（１の方が発生頻度が大きい）時には、−１を１と解釈して符号化し、１を−１として解釈して符号化することで符号化効率を上げることができる。
【００６８】
一方kパラメ−タが０以外の場合にも上記符号反転処理を行うことは可能であるが、本実施の形態ではそれほど効果がないことから、符号反転処理を行わないものとする。
【００６９】
以上の符号反転処理は画像を符号化している途中で適宜切り替わるものではあるが、もちろん、復号化側でも復号化された周辺画素に基づいて上記反転判定回路６０１や符号反転回路６０２と同等の処理部を有するので、どの符号化対象画素の時点から予測誤差Diffの正負の解釈の仕方が切り替わったか知ることができる。
【００７０】
上記符号反転の処理が行われた後、Golomb−Rice符号化回路１０７は、符号予測変換回路１０６の出力する予測誤差Diff’をパラメ−タkでGolomb−Rice符号化し、符号をスイッチ１１３の端子B’へと出力する。まず、Diffを以下の式により非負の整数値Vへと変換する。
【００７１】

【００７２】
次に、非負の整数値Vをパラメ−タkでGolomb−Rice符号化する。Golomb−Rice符号化の手順はGolomb−Rice符号化回路１０４の説明で述べたとうりである。
【００７３】
最後に、ランレングスカウンタ１０８とMelcode符号化回路１０９により符号化処理を行なうランレングスモ−ドについて説明する。
【００７４】
ランレングスカウンタ１０８にはスイッチ１１２の端子Ａから符号化対象画素値ｘ、バッファ１１５から直前の画素値ａが入力され、信号線１１６に符号化制御信号ｃ、信号線１１７に同一輝度連続数ＲＬを出力する。図７はランレングスカウンタ１０８の構成を示したものである。同図において７０１は比較器、７０２はカウンタである。比較器７０１は符号化対象画素値ｘと直前の画素値ａを比較し、値が等しい場合には‘０’を、等しくない場合には‘１’を符号化制御信号ｃとして出力する。カウンタ７０２は内部に同一輝度値の連続数ＲＬを保持しており、比較器７０１の出力する符号化制御信号ｃが‘０’である場合にはＲＬをインクリメントして出力し、符号化制御信号ｃが‘１’である場合にはＲＬの値を出力した後、０にリセットする。
【００７５】
Ｍｅｌｃｏｄｅ符号化回路１０９は信号線１１６から入力される符号化制御信号が‘１’である場合にのみ信号線１１７から入力される同一輝度連続数ＲＬを符号化する。このＭｅｌｃｏｄｅ符号化の手順を図１０に示す。
【００７６】
図１０のSTEP１００１においてまず、Melcode符号化回路１０９の内部に保持されているindex（符号化開始時の初期値は０）に基づいてラン長しきい値RLTが決定する。図１１にindexとRLTの対応関係を示す。次に、STEP１００２ではRLTとラン長RLを比較し、RL≧RLTならばSTEP１００３に処理を進め、そうでない場合にはSTEP１００８へと処理を進める。
【００７７】
STEP１００３では’０’を符号として出力する。続いてSTEP１００４でRL＝RL−RLTによりRLの値を更新する。STEP１００５ではindexの値をインクリメントし、STEP１００６ではindexが３１を超えた場合にはSTEP１００７でindexに３１を設定してからSTEP１００１に処理を戻し、indexが３１を超えない場合にはそのままSTEP１００１に処理を戻す。
【００７８】
一方ステップ１００８へと処理が進んだ場合には、STEP１００８でまず、’１’を符号として出力する。次にSTEP１００９において、RLを２進数表現し、その下位RLTビットを符号として出力する。STEP１０１０ではindexの値をデクリメントし、STEP１０１１でindexが０以下になったかどうか判断する。indexが０以下になった場合にはSTEP１０１２においてindexに０を設定して終了し、indexが０以下になっていない場合にはそのまま終了する。
【００７９】
以上により、ラン長RLに対する符号が生成され、出力される。
【００８０】
上述の処理を、入力部１００より入力される最後の画素まで繰り返し、符号化処理を行う。これにより、信号線１１４に入力画像に対する符号系列を出力する。
【００８１】
なお、上記Melcode符号化の方法についての説明は、「電子通信学会論文誌’７７／１２Ｖｏｌ.Ｊ６０−ＡＮｏ.１２」に開示されているので、詳細は省略する。
【００８２】
以上に説明した３つの各符号化モードが、図８に示した符号化モードの切換に従って用いられる。
【００８３】
上述した符号化方法によれば、カラー又はモノクロの多値画像の情報量を失うことなく可逆（ロスレス）符号化することができる。
【００８４】
なお、本実施例に示したロスレス符号化において、図６に示した符号反転処理を行うことにより、予測誤差Diffが同じ絶対値を有するにもかかわらず符号長が異なる様なGolomb-Rice符号化等のエントロピ−符号化に対して、この符号化特性を考慮して、符号化対象画素の前画素までに予測誤差Diffの正の符号と負の符号の何れが多く発生しているかに基づいて、エントロピ−符号化前に予測誤差Diffを符号反転するか否か（予測誤差Diffの正負の符号の解釈を変えるか否か）を制御する様にすれば、同じ絶対値の予測誤差Diffにおいて発生頻度が多い方を短い符号長とすることができ、効率の良いエントロピ−符号化が可能となる。
【００８５】
また以上の実施の形態の符号反転処理は、符号化対象画素の前画素までに予測誤差Diffの正の符号と負の符号の何れが多い回数発生しているかという、単なる発生回数に基づいて反転処理を行うことを大きな特徴とし、これによれば、符号化対象画素の前画素までの予測誤差Diffの累積値が正の符号と負の符号の何れであるかに基づいて反転処理を行う様な方法と比べて、本実施の形態の方が処理が容易である。更には画像のノイズ等により予測誤差Diffに正又は負の大きな値が発生してしまったときに、上記累積値は正負の一方に偏ってしまい最適な符号反転ができないが、本実施の形態によればこの様なノイズによる影響を受けないで済む。
【００８６】
（変形例）
本発明は上述した実施の形態に限定されるものではない。例えば、符号化対象画素値の予測方法として単純に前値予測を用いる場合にも適用でき、幾つかの予測方法を用意して、適時切り替えても構わない。また、エントロピ−符号化手段としてGolomb−Rice符号とMelcodeを用いているが、これらをハフマン符号等の他のエントロピ−符号化方式に変えても良い。なお、上述の実施の形態ではラン終端モ−ドで符号反転処理を行なったが、本発明はこれに限らず、ノーマルモードの場合に代表される予測値をエントロピー符号化する様な符号化モード又は単独の符号化処理に適用する事も可能であり、これらの変形例も本発明に含まれる。
【００８７】
また本発明は複数の機器（たとえばホストコンピュータ、インタフェース機器、リーダ、プリンタ等）から構成されるシステムに適用しても一つの機器（たとえば複写機、ファクシミリ装置）からなる装置に適用してもよい。
【００８８】
また前述した実施形態の機能を実現する様に各種のデバイスを動作させる様に該各種デバイスと接続された装置あるいはシステム内のコンピュータに、前記実施形態機能を実現するためのソフトウエアのプログラムコードを供給し、そのシステムあるいは装置のコンピュータ（CPUあるいはMPU）を格納されたプログラムに従って前記各種デバイスを動作させることによって実施したものも本発明の範疇に含まれる。
【００８９】
またこの場合、前記ソフトウエアのプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコード自体、及びそのプログラムコードをコンピュータに供給するための手段、例えばかかるプログラムコードを格納した記憶媒体は本発明を構成する。
【００９０】
かかるプログラムコードを格納する記憶媒体としては例えばフロッピーディスク、ハードディスク、光ディスク、光磁気ディスク、CD-ROM,、磁気テープ、不揮発性のメモリカード、ROM等を用いることが出来る。
【００９１】
またコンピュータが供給されたプログラムコードを実行することにより、前述の実施形態の機能が実現されるだけではなく、そのプログラムコードがコンピュータにおいて稼働しているOS(オペレーティングシステム)、あるいは他のアプリケーションソフト等と共同して前述の実施形態の機能が実現される場合にもかかるプログラムコードは本願発明の実施形態に含まれることは言うまでもない。
【００９２】
更に供給されたプログラムコードが、コンピュータの機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに格納された後そのプログラムコードの指示に基づいてその機能拡張ボードや機能格納ユニットに備わるCPU等が実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も本願発明に含まれることは言うまでもない。
【００９３】
【発明の効果】
以上説明したように本発明によれば、同じ絶対値の予測誤差の符号化において発生頻度が多い方を短い符号長とすることができ、効率の良いエントロピー符号化を行える。
【図面の簡単な説明】
【図１】本発明に係る第１の実施の形態でのブロック図を示すものである。
【図２】符号化対象画素と周辺画素の位置関係を示すものである。
【図３】周辺画素の差分値の量子化方法を示すものである。
【図４】予測変換回路１０２の構成を示すものである。
【図５】予測変換回路１０５の構成を示すものである。
【図６】符号予測反転回路１０６の構成を示すものである。
【図７】ランレングスカウンタ１０８の構成を示すものである。
【図８】モ−ドセレクタ１１１による符号化モ−ドの制御を示すものである。
【図９】 kパラメ−タ０，１，２に於けるGolomb−Rice符号の例を示したものである。
【図１０】 Melcode符号化手順を示したものである。
【図１１】ランレングスの符号化におけるindex値に対するRLTの値を示したものである。
【図１２】予測修正値Cの更新手順を示すものである。
【図１３】 kパラメ−タが０の場合及びkパラメ−タが２の場合のGolomb-Rice符号化の符号化割り当ての様子をしめすものである。
【符号の説明】
１００入力部
１０１，１１４，１１６，１１７信号線
１０２，１０５予測変換回路
１０４，１０７Ｇｏｌｏｍｂ−Ｒｉｃｅ符号化回路
１０６符号予測変換回路
１０８ランレングスカウンタ
１０９Ｍｅｌｃｏｄｅ符号化回路
１１０状態判別回路
１１１モ−ドセレクタ
１１２，１１３スイッチ
１１５画像デ−タ系列を格納するバッファ

Claims

ラスタースキャン順に入力された画素を順次符号化する符号化装置であって、
符号化対象画素の周囲画素の状態を判別する状態判別手段と、
符号化対象画素の周囲画素に基づいて第１の予測アルゴリズムで予測値を発生し、該予測値と前記符号化対象画素値との予測誤差をＧｏｌｏｍｂ−Ｒｉｃｅ符号化する第１符号化手段と、
ランレングス値ＲＬを保持し、符号化対象画素と直前に符号化された画素と画素値が一致する場合にはランレングス値ＲＬをカウントアップし、不一致の場合にはランレングス値ＲＬをＭｅｌｃｏｄｅ符号化する第２符号化手段と、
符号化対象画素の周囲画素に基づいて第１とは異なる第２の予測アルゴリズムで予測値を発生し、該予測値と前記符号化対象画素値との予測誤差をＧｏｌｏｍｂ−Ｒｉｃｅ符号化する第３符号化手段と、
各符号化対象画素に対して、符号化対象画素の周辺画素の状態及びランレングス値ＲＬに基づいて第１及び第２符号化手段の何れか一方の符号化を施し、第２符号化手段の符号化時に前記不一致の場合には更に前記第３符号化手段による符号化を施す符号化モード選択手段とを備え、
前記第３符号化手段は、Ｇｏｌｏｍｂ−Ｒｉｃｅ符号化に用いられるｋパラメータの値が０である場合で、かつ該第３符号化手段による符号化において符号化対象画素の前画素までに対する正の予測誤差と負の予測誤差のうちでより多く発生している方に長い符号長が割り当てられている場合に、前記符号化対象画素に対応する予測誤差の正負の符号を反転させることを特徴とする符号化装置。
ラスタースキャン順に入力された画素を順次符号化する符号化方法であって、
符号化対象画素の周囲画素の状態を判別する状態判別ステップと、
符号化対象画素の周囲画素に基づいて第１の予測アルゴリズムで予測値を発生し、該予測値と前記符号化対象画素値との予測誤差をＧｏｌｏｍｂ−Ｒｉｃｅ符号化する第１符号化ステップと、
ランレングス値ＲＬを保持し、符号化対象画素と直前に符号化された画素と画素値が一致する場合にはランレングス値ＲＬをカウントアップし、不一致の場合にはランレングス値ＲＬをＭｅｌｃｏｄｅ符号化する第２符号化ステップと、
符号化対象画素の周囲画素に基づいて第１とは異なる第２の予測アルゴリズムで予測値を発生し、該予測値と前記符号化対象画素値との予測誤差をＧｏｌｏｍｂ−Ｒｉｃｅ符号化する第３符号化ステップと、
各符号化対象画素に対して、符号化対象画素の周辺画素の状態及びランレングス値ＲＬに基づいて第１及び第２符号化ステップの何れか一方の符号化を施し、第２符号化ステップの符号化時に前記不一致の場合には更に前記第３符号化ステップによる符号化を施す符号化モード選択ステップとを備え、
前記第３符号化ステップは、第２の予測符号化モードにおいてＧｏｌｏｍｂ−Ｒｉｃｅ符号化に用いられるｋパラメータの値が０である場合で、かつ前記第３符号化ステップにおいて符号化対象画素の前画素までに対する正の予測誤差と負の予測誤差のうちでより多く発生している方に長い符号長が割り当てられている場合に、前記符号化対象画素に対応する予測誤差の正負の符号を反転させることを特徴とする符号化方法。
請求項２に記載の符号化方法を実行させるコンピュータプログラムをコンピュータに供給可能な状態で記憶した記憶媒体。