(57)【特許請求の範囲】
【請求項１】
複数の画素を順次Ｇｏｌｏｍｂ−Ｒｉｃｅ符号化する符号化装置であって、
符号化対象画素の周辺画素の状態を複数の状態の中から決定する状態決定手段と、
前記符号化対象画素の予測値を、該符号化対象画素の周辺画素に基づき発生する予測値発生手段と、
Ｇｏｌｏｍｂ−Ｒｉｃｅ符号化に用いるパラメータｋ（ｋ≧０）を前記複数の状態毎に格納する学習メモリと、
前記符号化対象画素とその予測値との予測誤差を、前記学習メモリ内の、前記状態決定手段により決定した状態に相当するパラメータｋ、及び前記予測誤差により定まる符号長の可変長符号に符号化するＧｏｌｏｍｂ−Ｒｉｃｅ符号化手段と、
前記符号化対象画素をＧｏｌｏｍｂ−Ｒｉｃｅ符号化した後に、前記パラメータｋを、前記状態決定手段により決定した状態と同じ状態を有する別画素をＧｏｌｏｍｂ−Ｒｉｃｅ符号化する為に予め更新し、前記学習メモリへ書き込むパラメータｋ更新手段とを有することを特徴とする符号化装置。
【請求項２】
更に、前記予測値発生手段による予測値を、前記符号化対象画素よりも前の画素を符号化した際に発生した予測誤差の累積値に基づいて修正する予測値修正手段を有することを特徴とする請求項１に記載の符号化装置。
【請求項３】
前記Ｇｏｌｏｍｂ−Ｒｉｃｅ符号化手段は、更に、前記別画素とその予測値との予測誤差を、前記パラメータｋ更新手段により更新されたパラメータｋに基づいてＧｏｌｏｍｂ−Ｒｉｃｅ符号化することを特徴とする請求項１に記載の符号化装置。
【請求項４】
複数の画素を順次Ｇｏｌｏｍｂ−Ｒｉｃｅ符号化する符号化装置であって、
符号化対象画素の周辺画素の状態を複数の状態の中から決定する状態決定手段と、
前記符号化対象画素の予測値を発生する予測値発生手段と、
Ｇｏｌｏｍｂ−Ｒｉｃｅ符号化に用いるパラメータｋ（ｋ≧０）を前記複数の状態毎に格納する学習メモリと、
前記符号化対象画素とその予測値との予測誤差を、前記学習メモリ内の、前記状態決定手段により決定した状態に相当するパラメータｋ、及び前記予測誤差により定まる符号長の可変長符号に符号化するＧｏｌｏｍｂ−Ｒｉｃｅ符号化手段と、
前記符号化対象画素をＧｏｌｏｍｂ−Ｒｉｃｅ符号化した後に、前記パラメータｋを、前記状態決定手段により決定した状態と同じ状態を有する別画素をＧｏｌｏｍｂ−Ｒｉｃｅ符号化する為に予め更新し、前記学習メモリへ書き込むパラメータｋ更新手段とを有することを特徴とする符号化装置。
【請求項５】
前記Ｇｏｌｏｍｂ−Ｒｉｃｅ符号化手段は、更に、前記別画素とその予測値との予測誤差を、前記パラメータｋ更新手段により更新されたパラメータｋに基づいてＧｏｌｏｍｂ−Ｒｉｃｅ符号化することを特徴とする請求項４に記載の符号化装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は画像データの符号化を行う符号化装置に関するものである。
【０００２】
【従来の技術】
近年、静止画像を電子データとして圧縮し外部に伝送したりメモリに格納したりする用途が増加している。これら画像の中でも医療用の静止画像等については画質を劣化させない様に可逆（ロスレス）圧縮符号化されることが好ましい。
【０００３】
これに伴いこの様な可逆圧縮を効率良く行う為の種々の圧縮符号化方式が提案されている。例えば、符号化対象画素と、周辺画素から生成された予測値との差分を出力し、この差分をGolomb-Rice符号化する手順を行うロスレス圧縮符号化方式の提案がある。
【０００４】
【発明が解決しようとする課題】
しかしながら、これら提案された圧縮符号化方式を実行する為の具体的な装置構成については未だ確立されていない。
【０００５】
本発明は上記従来例に鑑みてなされたものであり、効率良くロスレス圧縮符号化を行うことを主な目的とする。
【０００６】
特に上記ロスレス圧縮符号化方式に適用するGolomb-Rice符号化を高速に行える構成を提供することを目的とする。
【０００７】
【課題を解決するための手段】
上述の目的を達成するために本発明の符号化装置によれば、複数の画素を順次Ｇｏｌｏｍｂ−Ｒｉｃｅ符号化する符号化装置であって、符号化対象画素（例えば本実施の形態ではｘに相当）の周辺画素の状態（同じく図４の状態Ｓに相当）を複数の状態の中から決定する状態決定手段（状態判別回路１１０に相当）と、前記符号化対象画素の予測値（同じくＰ或いはＰ’に相当）を、該符号化対象画素の周辺画素（同じくａ，ｂ，ｃに相当）に基づき発生する予測値発生手段（同じく予測器４０１、エラーフィードバック回路４０２に相当）と、Ｇｏｌｏｍｂ−Ｒｉｃｅ符号化に用いるパラメータｋ（ｋ≧０）を前記複数の状態毎に格納する学習メモリ（同じくメモリ４０４に相当）と、前記符号化対象画素とその予測値との予測誤差を、前記学習メモリ内の、前記状態決定手段により決定した状態に相当するパラメータｋ、及び前記予測誤差により定まる符号長の可変長符号に符号化するＧｏｌｏｍｂ−Ｒｉｃｅ符号化手段（同じくＧｏｌｏｍｂ−Ｒｉｃｅ符号化回路１０４に相当）と、前記符号化対象画素をＧｏｌｏｍｂ−Ｒｉｃｅ符号化した後に、前記パラメータｋを、前記状態決定手段により決定した状態と同じ状態を有する別画素をＧｏｌｏｍｂ−Ｒｉｃｅ符号化する為に予め更新し、前記学習メモリへ書き込むパラメータｋ更新手段（ｋパラメータ生成回路４０６に相当）とを有することを特徴とする。
【０００８】
【発明の実施の形態】
（第１の実施の形態）
次に本発明の第１の実施の形態について図面を参照して詳細に説明する。
【０００９】
図１に本発明の第１の実施の形態を実行するためのブロック図を示す。同図において１００は画像データを入力するための入力部である。
【００１０】
１０１及び１１４は画像データを後段に伝送する信号線、１０２は予測変換回路である。１０４及び１０７はGolomb-Rice符号化回路、１０５は予測変換回路である。１０６は符号化予測変換回路であり、１０８はランレングスカウンタである。１０９はMelcode符号化回路であり、１１０は状態判別回路、１１１はモードセレクタ、１１２及び１１３はスイッチである。１１５は２ライン分の画像データを保持するバッファである。
【００１１】
本実施の形態では、３つの符号化モードを切り換えて符号化を実行する。具体的には、１つ目のモードとして予測変換回路１０２及びGolomb-Rice符号化回路１０４で符号化処理を行うノーマルモード、２つ目のモードとしてランレングスカウンタ１０８及びMelcode符号化回路１０９により符号化処理するランレングスモード、３つ目のモードとして予測変換回路１０５及び符号予測変換回路１０６及びGolomb-Rice符号化回路１０７により符号化処理を行うラン終端モードである。
【００１２】
次に、１画素８ビット（０〜２５５の値）のモノクロ画像信号を符号化する場合を例に、本実施の形態での各部の動作を順に説明する。しかしながら、本発明はこれに限らず、ＲＧＢの各８ビットの色成分、又はＬａｂの各８ビットの輝度、色度成分からなる多値カラー画像を符号化する場合にも適用でき、各成分を上記モノクロ画像信号と同様に符号化すれば良い。
【００１３】
また各成分の符号化切り換え単位は、画面毎に行うこともでき、これによれば画像全体の様子を復号化側で早めに確認することが可能となる。また各成分の符号化切り換え単位は、画素毎、１ライン毎、複数ラインから成るバンド毎に行うこともでき、これによれば部分的ではあるが完全なカラー画像を早期に見ることが可能となる。
【００１４】
なおバッファ１１５の内部の値は初期値を全て０に設定しておくこととする。
【００１５】
まず、入力部１００から符号化対象となる画素（以下符号化対象画素とする）がラスタースキャン順に入力され、信号線１０１を通じてスイッチ１１２、バッファ１１５へ入力される。
【００１６】
バッファ１１５は信号線１０１から順次入力される画像データを２ライン分まで保持しておく。この２ラインは符号化対象画素の存在するラインとその１つ前に入力されるラインである。
【００１７】
状態判別回路１１０は、符号化対象画素の周辺画素の状態を表す状態番号Ｓとその位相を表す位相フラグＲを生成するものであり、以下の処理を行う。まず、符号化対象画素の周辺画素ａ，ｂ，ｃ，ｄに対応する画素データをバッファ１１５から読み出す。
【００１８】
図２に符号化対象画素ｘに対する周辺画素ａ，ｂ，ｃ，ｄの位置関係を示す。図２において周辺画素ａ，ｂ，ｃ，ｄは、符号化対象画素ｘに対する既に符号化済の画素である。次に読み出した画像データａ，ｂ，ｃ，ｄを用いてｄ−ｂ，ｂ−ｃ，ｃ−ａを求め、各々図３に示す対応に従って−４，−３，−２，−１，０，１，２，３，４の９レベルの値に量子化し、量子化値ｑ（ｄ−ｂ），ｑ（ｂ−ｃ），ｑ（ｃ−ａ）を求める。
【００１９】
次にｑ（ｄ−ｂ）×８１＋ｑ（ｂ−ｃ）×９＋ｑ（ｃ−ａ）の計算式により周辺画素の状態を表す状態番号Ｓを生成する。次に状態番号Ｓの符号の正負を調べ、正である場合には位相フラグを０に設定し、負である場合には位相フラグを１に設定すると共に状態番号Ｓの正負を反転（正の値に反転）する。以上の処理により、０〜３６５までの値をとる状態番号Ｓと、０または１の値をとる位相フラグＲが生成され出力される。
【００２０】
モードセレクタ１１１は、状態判別回路１１０の生成された状態番号Ｓとランレングスカウンタ１０８の生成するラン長ＲＬ、符号化制御信号Ｑに基づいて、符号化モードを選択し、スイッチ１１２及びスイッチ１１３の切り換え制御を行う。ランレングスカウンタ１０８からのラン長ＲＬの初期値は０とする。
【００２１】
図８に符号化対象画素の１画素に対するモードセレクタ１１１による全体的な符号化モード制御の流れを示す。なお、以下の各ステップの詳細な動作は後述する。
【００２２】
まずSTEP８０１においてモードセレクタ１１１は、最初に符号化対象画素に対応する状態番号Ｓとラン長ＲＬを入力し、Ｓ≠０かつＲＬ＝０と判別した場合にはSTEP８０２へ、それ以外の場合にはSTEP８０３へ処理を進める。
【００２３】
STEP８０２ではスイッチ１１２を端子Ｃに、スイッチ１１３を端子Ｃ’に接続し、ノーマルモードの符号化を行う。一方、STEP８０３ではスイッチ１１２を端子Ａに、スイッチ１１３を端子Ａ’に接続し、ランレングスモードの符号化即ちラン長の符号化を行う。ランレングスモードの詳細な符号化処理については後述するが、ランレングスモードで実際に符号化出力されるのは画素毎ではなく、ラン長が確定した場合、即ち同一画素値の連続が途切れた場合のみである。この場合、符号化制御信号ｃの値は「０」から「１」となる。
【００２４】
STEP８０３の後、STEP８０４では符号化制御信号ｃの値を調べ、ｃ＝１の場合にはSTEP８０５と処理を進める。STEP８０５ではスイッチ１１２を端子Ｂに、スイッチ１１４を端子Ｂ’に接続し、ラン終端モードでの符号化処理を行う。以上の制御を１画素毎に繰り返して行い、３つの符号化モードを選択して符号化処理する。
【００２５】
上記３つの符号化モードを切り換える理由、即ち３つの符号化モードの役割について簡単に述べる。
【００２６】
ノーマルモードは、予測変換した場合の予測誤差がラプラス分布になるであろうと予測される画素の符号化に適用されるものである。ただし、同一輝度レベルの連続が期待される様な場合（周辺画素が同一輝度レベルである様な場合）にはランレングスモードに切り換えることにより、更に符号化効率を上げるものである。
【００２７】
ランレングスモードは、同一輝度レベルの連続が期待される様な場合に用いられるモードであり、予測誤差を符号化するのではなく画素値のラン長を符号化（ランレングス符号化）する。これにより、上記ノーマルモード（予測誤差のHuffman符号化、Golomb-Rice符号化等を用いた場合）では１サンプル当たり１ビット以下では符号化できないが、ランレングスモードでは１サンプル当たり１ビット以下での符号化も可能となり、符号化効率が良好になる。
【００２８】
ラン終端モードは、同一輝度レベルのランが終端した際の符号化対象画素を符号化するものである。また、この符号化対象画素の値は、ランレングス符号化におけるラン長の終端であるから、直前の画素値とは異なることが分かっている。従って、ノーマルモードの様に直前の画素値を予測値とした場合には、予測誤差０が発生せず符号化効率が良好にならない様な特殊な状態になっている。
【００２９】
この様な状態であることを考慮し、ランレングスモードが終わった画素、即ち直前の画素との画素値が変化した符号化対象画素に対してはノーマルモードではなくラン終端モードにより符号化を行う様にする。また上記状態における符号化対象画素を予測符号化した場合には、予測誤差の分布は離散的な値になることが多く、ラプラス分布からはほど遠いものとなることが推測される。この様な条件下ではノーマルモードで用いる後述の予測値修正はあまり有効でないので、これを用いずに符号化する。なお、次の符号化対象画素からは直前の画素値を予測値として符号化しても符号化効率が良好になる可能性が高い。
【００３０】
以下上述した３つの各符号化モードについて個別に説明する。
【００３１】
まず、予測変換回路１０２とGolomb-Rice符号化回路１０４により符号化処理を行うノーマルモードの符号化処理について説明する。
【００３２】
図１の予測変換回路１０２では、符号化対象画素の周囲画素ａ，ｂ，ｃから符号化対象画素の画素値を予測し、この予測により発生した予測値と符号化対象画素の実際の画素値との差分（予測誤差）Ｄｉｆｆ及び後述するｋパラメータを生成する。
【００３３】
図４に予測変換回路１０２の内部構成図を示す。
【００３４】
図４において４０１は予測器、４０２はエラーフィードバック回路、４０３は予測誤差生成回路、４０４はメモリ、４０５はパラメータ更新回路、４０６はｋパラメータ生成回路である。
【００３５】
また、図１には図示されていないが予測変換回路１０２には図１のバッファ１１５から周辺画素ａ，ｂ，ｃの画素値のデータ、状態判別回路１１０から状態Ｓと位相フラグＲが入力される。また、スイッチ１１２の端子Ｃから符号化対象画素の画素値ｘが入力される。
【００３６】
メモリ４０４には個々の状態番号Ｓに対する４つのパラメータＮ，Ａ，Ｂγ，Ｃαが格納される。これらの値は符号化の開始時にＮ＝１、Ａ＝４、Ｂγ＝Ｃα＝０に初期化される。
【００３７】
また本発明においては、メモリ４０４には符号化対象画素がGolomb-Rice符号化される際に使用されるｋパラメータをも随時更新しながら格納しておく。具体的には、符号化対象画素が符号化された直後に、パラメータＡ及びＮの更新直後のパラメータＡ’及びＮ’を用いてｋパラメータを作成してしまい、上記メモリ４０４に予め格納しておく。言い換えると、このｋパラメータの作成及びメモリへの格納は、上記符号化対象画素以降の画素がこのｋパラメータを用いてGolomb-Rice符号化を開始するタイミングとは関わりなく、前もって行われる。従って、上記符号化対象画素の次以降の画素をGolomb-Rice符号化する際には、この符号化開始のタイミングに合わせてｋパラメータの作成を開始する必要が無くなるので、高速にGolomb-Rice符号化を行うことが可能となる。なおパラメータｋは符号化開始時に２に初期化される。
【００３８】
上記パラメータＮは状態Ｓの生起回数であり、Ａは状態Ｓにおける予測誤差の絶対値の累計であり、Ｂγは状態Ｓにおける予測誤差の累計であり、Ｃαは予測値を修正する為の修正値である。
【００３９】
以下、図４を用いて予測変換回路１０２の動作を説明する。まず、予測器４０１はバッファ１１５から符号化対象画素の周辺画素ａ，ｂ，ｃ（位置関係は図２参照）の画素値を入力し、この画素値ａ，ｂ，ｃに基づいて予測値Ｐを生成する。なお予測値Ｐは以下の式により求める。
【００４０】
0003839974.tif 000002
【００４１】
エラーフィードバック回路４０２はメモリ４０４に入力される状態Ｓにおける後述する予測修正値Ｃαを用いて予測値Ｐを修正し、修正予測誤差Ｐ’を生成する。即ち、状態判別回路１１０から入力される位相フラグＲが０ならばＰ’＝Ｐ＋Ｃαとし、フラグＲが１ならばＰ’＝Ｐ−Ｃαとする。更に、Ｐ’が０未満の時にはＰ’＝０と制限し、Ｐ’＝２５５以上の時にはＰ’＝２５５と制限する。
【００４２】
予測誤差生成回路４０３は符号化対象画素の画素値ｘと修正予測値Ｐ’の差分をとり予測誤差Ｄｉｆｆを生成する。位相フラグＲが０の場合にはＤｉｆｆ＝ｘ−Ｐ’とし、位相フラグが１の場合にはＤｉｆｆ＝Ｐ’−ｘとする。
【００４３】
予測誤差生成回路４０３はＤｉｆｆが−１２８未満の場合にはＤｉｆｆに２５５を加算し、Ｄｉｆｆが１２８以上の場合にはＤｉｆｆから２５５を減算することにより、Ｄｉｆｆの値を−１２８〜１２７の範囲で表現することができる。
【００４４】
パラメータ更新回路４０５は、符号化対象画素がGolomb-Rice符号化されるタイミングに合わせて、メモリ４０４から状態Ｓにおける４つのパラメータＮ，Ａ，Ｂγ，Ｃαを読み出し、これらをＮ’，Ａ’，Ｂγ’，Ｃα’に更新する。具体的にはＡ’＝Ａ＋｜Ｄｉｆｆ｜、Ｂγ’＝Ｂγ＋ＤｉｆｆによりＡ’とＢγ’を求める。ここでＮの値が閾値Ｔｈ１に等しい場合にはＮ，Ａ，Ｂγを１／２倍にする。閾値Ｔｈ１はＮ，Ａ，Ｂγを一定範囲内に限定するためのものであり、予め設定しておく（例えばＴｈ１＝６４）。次に、Ｎ’＝Ｎ＋１によりＮを更新する。
【００４５】
図１２に予測修正値Ｃαの更新手順を示す。Ｃα’にＣαの値を代入した後、まずSTEP１２０１においてパラメータＢγ’が−Ｎ以下であるか否かを判定する。この値が−Ｎ以下であった場合にはSTEP１２０３へ進み、そうでない場合にはSTEP１２０２へ処理を進める。
【００４６】
STEP１２０３ではＣα’の値を−１２８と比較し、−１２８より大きい場合にはＣα’から１を減算する（STEP１２０４）。
【００４７】
次にＢγ’にＮを加算する（STEP１２０５）。次にＢγ’が−Ｎ以下である場合にはＢγ’＝−Ｎ＋１とする（STEP１２０６、１２０７）。
【００４８】
STEP１２０２ではＢγ’を０と比較し、Ｂγ’が０以上の場合にはSTEP１２０８へと処理を進め、そうでない場合にはこの更新処理を終了する。
【００４９】
STEP１２０８ではＣα’の値を１２７と比較し、１２７未満である場合にはＣα’に１を加算する（STEP１２０９）。次に、Ｂγ’からＮを減算する（STEP１２１０）。Ｂγ’が０以上である場合にはＢγ’＝０とする（STEP１２１１、１２１２）。
【００５０】
最後に更新されたＮ’，Ａ’，Ｂγ’，Ｃα’をメモリ４０４に出力し、このメモリに格納されている状態Ｓにおける４つのＮ，Ａ，Ｂγ，Ｃαを置き換える。同時にＮ’とＡ’はｋパラメータ生成回路４０６へも出力される。
【００５１】
ｋパラメータ生成回路４０６では、符号化対象画素のGolomb-Rice符号化が実行されると同時にパラメータ更新回路４０５で更新された、状態Ｓの生起回数Ｎ’、及び状態Ｓでの予測誤差の絶対値の累積加算値Ａ’とを入力すると同時に、min（ｋ｜Ｎ×２＾ｋ＞＝Ａ）によりGolomb-Rice符号化時に用いるｋパラメータの値を求める。ここでmin（ａ｜ｂ）は、条件ｂを満たす最小のａを意味する。
【００５２】
この時点で生成されたｋパラメータは次以降の符号化対象画素のGolomb-Rice符号化が始まるまでメモリ４０４に保持される。そして次以降のGolomb-Rice符号化が始まると同時にｋパラメータが速やかに出力される。この方法によれば、Golomb-Rice符号化が開始される度に、その際メモリ４０４から読み出されるＮとＡからｋパラメータを生成してGolomb-Rice符号化回路１０４へ供給する場合と比較して、ｋパラメータを生成する処理時間だけGolomb-Rice符号化の速度を高めることができ、結果的に全体の符号化速度を高めることが可能となる。
【００５３】
以上の処理により、予測変換回路１０２は予測誤差Ｄｉｆｆとｋパラメータとを生成し、後段のGolomb-Rice符号化回路１０４にこれらを出力する。
【００５４】
Golomb-Rice符号化回路１０４では、まず予測変換回路１０２の出力する予測誤差Ｄｉｆｆを次式により非負の整数値Ｖに変換する。
【００５５】
0003839974.tif 000003
【００５６】
次にこのＶをｋパラメータに基づいてGolomb-Rice符号化する。非負の整数値Ｖをｋパラメータに基づいてGolomb-Rice符号化する符号化手順は次の通りである。
【００５７】
まず、非負の整数値Ｖを２進数表現する。次にこれを下位ｋビット部分と上位の残りのビット部分に分割する。次に下位ｋビット部分に、上位の残りのビット部分を１０進数で表現される数だけの「０」のビットを付加し、最後に「１」のビットを付加して符号語とする。
【００５８】
具体例をあげて説明する。ｋ＝２、Ｖ＝１３の場合には、Ｖの２進数表現「１１０１」を生成し、この下位２ビット「０１」を最初の１〜２ビット目のGolomb-Rice符号化データとし、残りの上位２ビットの「１１」を１０進数で表す数「３」の０（「０００」）を３〜５ビット目のGolomb-Rice符号化データとし、最後に「１」のビットをGolomb-Rice符号化データとして付加する。よってこの場合の最終的なGolomb-Rice符号化データは「０１０００１」となる。
【００５９】
なお、図９に上述の符号化処理を施す場合のｋパラメータ＝０，１，２における非負の整数値と符号語の対応を示す。
【００６０】
Golomb-Rice符号化回路１０４で生成された符号は、スイッチ１１３’の端子Ｃ’へと出力される。
【００６１】
次に予測変換回路１０５、符号予測変換回路１０６、Golomb-Rice符号化回路１０７により符号化処理を行うラン終端モードについて説明する。
【００６２】
予測変換回路１０５は周辺画素値ａ，ｂから符号化対象画素値を予測し、予測誤差を生成する。図５に予測変換回路１０５の構成図を示す。
【００６３】
同図において５０１は比較器、５０２は予測器、５０３は予測誤差生成回路、５０４はメモリ、５０５はｋパラメータ生成回路、５０６はパラメータ更新回路である。また、図１には示されていないが、予測変換回路１０５にはバッファ１１５から周辺画素ａ，ｂの画素値のデータが入力される。また、スイッチ１１２の端子Ｂからは符号化対象画素値ｘが入力される。
【００６４】
メモリ５０４には状態番号Ｓで特定される各状態に対応する３つのパラメータＮ，Ａ，Ｂαが格納される。Ｎ，Ａ，Ｂαは画像符号化の開始時にＮ＝１，Ａ＝４，Ｂα＝０に初期化される。なお、Ｎは状態Ｓの生起回数であり、Ａは状態Ｓにおける予測誤差の絶対値の累計であり、Ｂαは状態Ｓにおける負の予測誤差が出現した回数である。
【００６５】
図５を用いて予測変換回路１０５の動作を詳細に説明する。まず、比較器５０１はバッファ１１５から渡される符号化対象画素の周辺画素ａ，ｂを比較し、ｂ＞ａの場合には１を出力し、そうでない場合には０を出力する。以降、この比較器５０１から出力する値を位相フラグｒ（１又は０）と呼ぶことにする。
【００６６】
予測器５０２は周辺画素ａ，ｂから予測値Ｐと状態番号Ｓを生成する。状態番号Ｓの値はａ＝ｂの場合には１、ａ≠ｂの場合には０となる。また予測値Ｐは常にｂとする。
【００６７】
予測誤差生成回路５０３は符号化対象画素値ｘと予測値Ｐより予測誤差Ｄｉｆｆを生成する。位相フラグｒが０の場合にはＤｉｆｆ＝ｘ−Ｐとし、位相フラグｒが１の場合にはＤｉｆｆ＝Ｐ−ｘとする。
【００６８】
ｋパラメータ生成回路５０５は、状態Ｓ、状態Ｓの生起回数Ｎ、及び状態Ｓでの予測誤差の絶対値の累積加算値Ａを読み出し、次式によりＴを求める。
【００６９】
Ｔ＝｜Ａ        ：Ｓ＝０の時
｜Ａ＋Ｎ／２：  Ｓ＝１の時
【００７０】
min（ｋ｜Ｎ×２＾ｋ＞＝Ｔ）によりGolomb-Rice符号化時のｋパラメータの値を求め、出力する。
【００７１】
パラメータ更新回路５０６は、符号化対象画素がGolomb-Rice符号化されるタイミングに合わせて、メモリ５０４から状態Ｓにおける３つのパラメータＮ，Ａ，Ｂαを読み出し、Ｎ’，Ａ’，Ｂα’に更新する。まず、Ａ’＝Ａ＋｜Ｄｉｆｆ｜によりＡ’を求める。次にＤｉｆｆの正負を調べ、正である場合にはＢα’＝Ｂαとし、負である場合にはＢα’＝Ｂα＋１とする。即ち、Ｂαは予測誤差Ｄｉｆｆが負であった回数を示すものとなる。また、Ｎ’＝Ｎ＋１によりＮ’を求める。
【００７２】
最後に更新されたＮ’，Ａ’，Ｂα’はメモリ５０４に出力され、次の符号化対象画素のGolomb-Rice符号化が開始される前までに、状態Ｓにおける３つのパラメータＮ，Ａ，Ｂαとして置き換えられる。
【００７３】
以上の処理により、予測変換回路１０５は予測誤差Ｄｉｆｆとｋパラメータ、状態番号Ｓ、状態番号Ｓの状態における２つのパラメータＢαとＮを出力する。
【００７４】
符号化予測変換回路１０６は、ｋパラメータが０の場合に、ＢαとＮの値から予測誤差Ｄｉｆｆの符号（＋／−）を予測し、予測結果に基づいてＤｉｆｆの符号を変更する。
【００７５】
図６に符号予測変換回路１０６の構成を示す。同図において６０１は反転判定回路６０２は符号反転回路、６０３はセレクタである。
【００７６】
図６を用いて符号予測変換回路１０６の動作を詳細に説明する。まず、反転判定回路６０１は、ｋ＝０の場合でありかつＢα＞Ｎ／２の場合に符号反転を指示する信号「１」を、それ以外の場合には符号反転しないことを指示する信号「０」を出力する。
【００７７】
符号反転回路６０２は、この指示信号（１又は０）に基づいて符号化対象画素に対応するＤｉｆｆの符号（＋／−）を反転し、−Ｄｉｆｆを信号線６０４に出力する。
【００７８】
セレクタ６０３は反転判定回路６０１の出力値が「０」の場合は信号線６０５を通じて入力されるＤｉｆｆを選択して出力し、「１」の場合には符号反転回路６０２の出力値である−Ｄｉｆｆを出力する。
【００７９】
以上の処理により、符号予測反転回路１０６は入力値Ｄｉｆｆに対し、Ｄｉｆｆ又は−Ｄｉｆｆを選択して出力する。
【００８０】
ここで符号反転の役割を簡単に説明する。ｋパラメータが０の場合及びｋパラメータが２の場合のGolomb-Rice符号化の符号化割り当ては、図１３の様になる。図１３においてｋパラメータが０の場合とは符号化対象画素を含めた周辺画素の値の変動が少ない場合を意味する。よってGolomb-Rice符号化を行った時の整数値Ｖと符号化出力及び符号長は図の様な関係になっている。
【００８１】
一方、ｋパラメータが２の場合には、０の場合と比較して多少符号化対象画素を含めた周辺画素の値の変動が大きくなっていることを表しているので、これに適した符号化が行える様、Golomb-Rice符号化を行った時の後述する整数値Ｖ又は予測誤差Ｄｉｆｆと、符号化出力又は符号長は図の様な関係になっている。
【００８２】
ここでｋパラメータが０の場合には、予測誤差Ｄｉｆｆが同じ絶対値を有するにも拘わらず符号長が異なるという特徴がある。これに対して、ｋパラメータが０以外の値（例えば２）の場合には、予測誤差Ｄｉｆｆが同じ絶対値を有するものは同じ符号長になることが多い。
【００８３】
この符号化特性を考慮して、ｋパラメータが０の場合かつＢα＞Ｎ／２の場合（状態Ｓにおける予測誤差が負であった回数が過半数を越える場合）に符号反転を行い、それ以外の場合には符号反転をしない様にすれば、同じ絶対値を有する予測誤差Ｄｉｆｆ（例えば−１と１）で発生頻度が多い方を符号長の短い符号化出力とすることが可能である。
【００８４】
即ち、−１の方が発生頻度が多ければ符号予測反転回路１０６の符号反転はしないで良しとし、−１の方が発生頻度が少ない（１の方が発生頻度が大きい）時には、−１を１として解釈して符号化することで符号化効率を上げることができる。
【００８５】
一方、ｋパラメータが０以外の場合にも上記符号反転処理を行うことは可能であるが、本実施の形態ではそれほど効果が無いことから、符号反転処理を行わないものとする。
【００８６】
以上の符号反転処理は画像を符号化している途中で適宜切り換わるものではあるが、もちろん、復号化側でも復号化された周辺画素に基づいて上記反転判定回路６０１や符号反転回路６０２と同等の処理部を有するので、どの符号化対象画素の時点から予測誤差Ｄｉｆｆの正負の解釈の仕方が切り換わったかを知ることができる。
【００８７】
上記符号反転の処理が行われた後、Golomb-Rice符号化回路１０７は、符号予測変換回路１０６の出力する予測誤差Ｄｉｆｆ’をｋパラメータを用いてGolomb-Rice符号化し、符号化データをスイッチ１１３の端子Ｂ’へと出力する。まずＤｉｆｆを以下の式により非負の整数値Ｖへと変換する。
【００８８】
Ｖ＝｜−２×（Ｄｉｆｆ−Ｓ）−１  ：  Ｄｉｆｆ＜０の時
｜  ２×（Ｄｉｆｆ−Ｓ）      ：  Ｄｉｆｆ≠０の時
【００８９】
次に、非負の整数値ＶをｋパラメータでGolomb-Rice符号化する。Golomb-Rice符号化の手順はGolomb-Rice符号化回路１０４の説明で述べたのと同じである。
【００９０】
最後に、ランレングスカウンタ１０８とMelcode符号化回路１０９により符号化処理を行うランレングスモードについて説明する。
【００９１】
ランレングスカウンタ１０８には、スイッチ１１２の端子Ａから符号化対象画素値ｘ、バッファ１１５から直前の画素値ａが入力され、信号線１１６に符号化制御信号ｃ、信号線１１７に同一輝度連続数ＲＬを出力する。
【００９２】
図７はランレングスカウンタ１０８の構成を示したものである。
【００９３】
同図において、７０１は比較器、７０２はカウンタである。比較器７０１は符号化対象画素値ｘと直前の画素ａとを比較し、値が等しい時には「１」を、等しくない時には「０」を符号化制御信号ｃとして出力する。カウンタ７０２は内部に同一輝度値の連続数ＲＬを保持しており、比較器７０１の出力する符号化制御信号ｃが「１」である場合にはＲＬをインクリメントして出力し、符号化制御信号ｃが「０」である場合にはＲＬの値を出力した後、０にリセットする。
【００９４】
Melcode符号化回路１０９は信号線１１６から入力される符号化制御信号が「０」である場合にのみ信号線１１７から入力される同一輝度連続数ＲＬを符号化する。このMelcode符号化の手順を図１０に示す。
【００９５】
図１０のSTEP１００１においてまず、Melcode符号化回路１０９の内部に保持されているindex（符号化開始時の初期値は０）に基づいてラン長閾値ＲＬＴが決定する。
【００９６】
図１１にindexとＲＬＴの対応関係を示す。次にSTEP１００２ではＲＬＴとラン長ＲＬとを比較し、ＲＬ≧ＲＬＴならばSTEP１００３に処理を進め、そうでない場合にはSTEP１００８へと処理を進める。
【００９７】
STEP１００３では「０」を符号として出力する。続いてSTEP１００４でＲＬ＝ＲＬ−ＲＬＴによりＲＬの値を更新する。STEP１００５ではindexの値をインクリメントし、STEP１００６ではindexが３１を越えた場合にはSTEP１００７でindexに３１を設定してからSTEP１００１に処理を戻し、indexが３１を越えない場合にはそのままSTEP１００１に処理を戻す。
【００９８】
一方、STEP１００８へと処理が進んだ場合には、STEP１００８でまず、「１」を符号として出力する。次にSTEP１００９において、ＲＬを２進数表現し、その下位ＲＬＴビットを符号として出力する。STEP１０１０ではindexの値をデクリメントし、STEP１０１１でindexが０以下になったかどうか判断する。indexが０以下になった場合にはSTEP１０１２においてindexに０を設定して終了し、indexが０以下になっていない場合にはそのまま終了する。
【００９９】
以上によりラン長ＲＬに対する符号が生成され、出力される。
【０１００】
上述の処理を、入力部１００より入力される最後の画素までに対して繰り返し、符号化処理を行う。これにより信号線１１４に入力される画像データに対する符号系列を出力できる。
【０１０１】
なお、上記Melcode符号化の方法についての説明は、「電子通信学会論文誌,77/12 Vol.J60-A No.12」に開示されているので詳細は省略する。
【０１０２】
以上に説明した３つの各符号化モードが、図８に示した符号化モードの切り換えに従って用いられる。
【０１０３】
上述した符号化方法によれば、カラー又はモノクロの多値画像の情報量を失うことなく可逆（ロスレス）圧縮符号化することができる。
【０１０４】
なお本実施の形態で示したロスレス符号化において、図６に示した符号反転処理を行うことにより、予測誤差Ｄｉｆｆが同じ絶対値を有するにも拘わらず符号長が異なる様なGolomb-Rice符号化等のエントロピー符号化に対して、この符号化特性を考慮して、符号化対象画素の前画素までに予測誤差Ｄｉｆｆの正の符号と負の符号の何れが多く発生しているかに基づいてエントロピー符号化前に予測誤差Ｄｉｆｆを符号反転するか否か（予測誤差Ｄｉｆｆの正負の符号の解釈を変えるか否か）を制御する様にすれば、同じ絶対値の予測誤差Ｄｉｆｆにおいて発生頻度が多い方を短い符号長とすることができ、効率の良いエントロピー符号化が可能となる。
【０１０５】
また以上の実施の形態の符号反転処理は、符号化対象画像の前画素までに予測誤差Ｄｉｆｆの正の符号と負の符号の何れが多い回数発生しているかという、単なる発生回数に基づいて反転処理を行うことを大きな特徴とし、これによれば、符号化対象画素の前画素ｍでの予測誤差Ｄｉｆｆの累積値が正の符号と負の符号の何れであるかに基づいて反転処理を行う様な方法と比較して、本実施の形態の方が処理が容易である。
【０１０６】
更には画像のノイズ等により予測誤差Ｄｉｆｆに正又は負の大きな値が発生してしまった時に、上記累積値は正負の一方に偏ってしまい最適な符号反転処理ができないが、本実施の形態によればこの様なノイズによる影響を受けないで済む。
【０１０７】
（変形例）
本発明は上述した実施の形態に限定されるものではない。例えば、符号化対象画素値の予測方法として単純に前置予測を用いる場合にも適用でき、幾つかの予測方法を用意して、適宜切り換えても構わない。またエントロピー符号化手段としてGolomb-Rice符号とMelcodeを用いているが、これらの一部を他のエントロピー符号化にすることもできる。
【０１０８】
なお上述の実施の形態では、ラン終端モードで符号反転処理を行ったが、本発明はこれに限らず、ノーマルモードの場合には代表される予測値をエントロピー符号化する様な符号化モード又は単独の符号化処理に適用することも可能であり、これらの変形例も本発明の範疇に含まれる。
【０１０９】
なお、本発明は、複数の機器（例えばホストコンピュータ、インタフェース機器、リーダ、プリンタ等）から構成されるシステムの１部として適用しても、１つの機器（たとえば複写機、ファクシミリ装置）からなる装置の１部に適用してもよい。
【０１１０】
また、本発明は上記実施の形態を実現するための装置及び方法のみに限定されるものではなく、上記システム又は装置内のコンピュータ（CPUあるいはMPU）に、上記実施の形態を実現するためのソフトウエアのプログラムコードを供給し、このプログラムコードに従って上記システムあるいは装置のコンピュータが上記各種デバイスを動作させることにより上記実施の形態を実現する場合も本発明の範疇に含まれる。
【０１１１】
またこの場合、前記ソフトウエアのプログラムコード自体が上記実施の形態の機能を実現することになり、そのプログラムコード自体、及びそのプログラムコードをコンピュータに供給するための手段、具体的には上記プログラムコードを格納した記憶媒体は本発明の範疇に含まれる。
【０１１２】
この様なプログラムコードを格納する記憶媒体としては、例えばフロッピーディスク、ハードディスク、光ディスク、光磁気ディスク、CD-ROM、磁気テープ、不揮発性のメモリカード、ROM等を用いることができる。
【０１１３】
また、上記コンピュータが、供給されたプログラムコードのみに従って各種デバイスを制御することにより、上記実施の形態の機能が実現される場合だけではなく、上記プログラムコードがコンピュータ上で稼働しているOS(オペレーティングシステム)、あるいは他のアプリケーションソフト等と共同して上記実施の形態が実現される場合にもかかるプログラムコードは本発明の範疇に含まれる。
【０１１４】
更に、この供給されたプログラムコードが、コンピュータの機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに格納された後、そのプログラムコードの指示に基づいてその機能拡張ボードや機能格納ユニットに備わるCPU等が実際の処理の一部または全部を行い、その処理によって上記実施の形態が実現される場合も本発明の範疇に含まれる。
【０１１５】
本発明においてはGolomb-Rice符号化に用いるｋパラメータを符号化対象画素の符号化を開始する際に生成するのでは無く、符号化対象画素の直前の画素が符号化された直後に、上記符号化対象画素の符号化開始のタイミングとは関わりなく予め作成してメモリに保持しておくようにしたので、上記符号化を高速に行えるという効果がある。
【０１１６】
【発明の効果】
以上説明した様に本発明によれば、効率良くロスレス圧縮符号化を行うことができ、特にｋパラメータを符号化対象画素の符号化の開始タイミングに関係無く予め作成し、学習メモリに保持しておく様にしたので、このｋパラメータを使用するGolomb-Rice符号化を高速に行え、結果的に全体の符号化処理を高速に行うことが可能である。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態に用いるブロック図
【図２】符号化対象画素と周辺画素の位置関係を示す図
【図３】周辺画素の差分値の量子化方法を示す図
【図４】予測変換回路１０２の構成を示す図
【図５】予測変換回路１０５の構成を示す図
【図６】符号予測反転回路１０６の構成を示す図
【図７】ランレングスカウンタ１０８の構成を示す図
【図８】モードセレクタ１１１による符号化モードの制御を示す図
【図９】ｋパラメータ０，１，２におけるGolomb-Rice符号の例を示す図
【図１０】  Melcode符号化の手順を示す図
【図１１】ランレングス符号化におけるindex値に対するＲＬＴの値を示す図
【図１２】予測修正値Ｃの更新手順を示す図
【図１３】ｋパラメータが０，２の場合のGolomb-Rice符号の割り当てを示す図
【符号の説明】
１００  入力部
１０１，１１４，１１６，１１７  信号線
１０２，１０５  予測変換回路
１０４，１０７  Ｇｏｌｏｍｂ−Ｒｉｃｅ符号化回路
１０６  符号予測変換回路
１０８  ランレングスカウンタ
１０９  Ｍｅｌｃｏｄｅ符号化回路
１１０  状態判別回路
１１１  モードセレクタ
１１２，１１３  スイッチ
１１５  バッファ
【図１】
0003839974.tif 000004
【図２】
0003839974.tif 000005
【図３】
0003839974.tif 000006
【図４】
0003839974.tif 000007
【図５】
0003839974.tif 000008
【図６】
0003839974.tif 000009
【図７】
0003839974.tif 000010
【図８】
0003839974.tif 000011
【図９】
0003839974.tif 000012
【図１０】
0003839974.tif 000013
【図１１】
0003839974.tif 000014
【図１２】
0003839974.tif 000015
【図１３】
0003839974.tif 000016