(57)【特許請求の範囲】
【請求項１】
データを走査して得られるランレングス値列を０のビット連続数と１のビット連続数との組を入力単位として順次入力し、所定の符号列に変換して出力するデータ符号化方法であって、
前記入力単位のデータに対応する状態値の算定として、前記０のビットの連続数Ｘ、前記１のビットの連続数Ｙ、直前の０のビットの連続数Ａおよび直前の１のビットの連続数Ｂが、Ｘ≠Ａ且つＹ≠Ｂの関係にある場合に状態Ｓ０の値を状態値Ｓとし、Ｘ＝Ａ且つＹ≠Ｂの関係にある場合に状態Ｓ１の値を状態値Ｓとし、Ｘ≠Ａ且つＹ＝Ｂの関係にある場合に状態Ｓ２の値を状態値Ｓとし、Ｘ＝Ａ且つＹ＝Ｂの関係にある場合に状態Ｓ３の値を状態値Ｓとして算定する算定工程と、
直前の状態値Ｔが状態Ｓ３であり、かつ、前記状態値Ｓと直前の状態値Ｔとが等しい一致事象となった場合にこれを反復事象とみなして、該反復事象が連続して発生する反復数Ｎを算出する反復数算定工程と、前記反復事象の発生後に、前記状態値Ｓと直前の状態値Ｔとが異なる不一致事象または入力完了となった場合に回帰事象と判定する回帰事象判定工程と、前記不一致事象が発生した場合に前記状態値Ｓの値を示す状態符号を生成する状態符号生成工程と、前記状態符号生成工程による状態符号の生成が終了するかまたは前記一致事象が発生した際に、前記０のビットの連続数Ｘまたは前記１のビットの連続数Ｙの値を示す数値符号を生成する第１の数値符号生成工程と、前記回帰事象が発生した場合に、前記状態符号生成工程による状態符号の生成に先だって、前記反復数算定工程によって算定された反復数Ｎの値を示す数値符号を生成する第２の数値符号生成工程と、を含んで前記入力単位のデータに対応する状態符号および数値符号の生成する生成工程と、
を含んだことを特徴とするデータ符号化方法。
【請求項２】
前記算定工程は、符号化を開始する際に、Ｔ、Ａ、Ｂおよび反復数Ｎにそれぞれ所定の初期値を格納する初期化工程と、前記ＸおよびＹに前記ランレングス値を入力する入力工程と、前記入力工程による入力後に、前記状態値Ｓを生成する状態値生成工程とを含み、
前記生成工程は、前記状態値生成工程により生成された状態値Ｓに対応して前記一致事象または不一致事象の発生を判定する一致事象判定工程と、前記一致事象の発生に応答して前記反復事象の発生の有無を判定する反復事象判定工程と、前記反復事象の発生に応答して前記反復数を加算する反復数加算工程と、前記不一致事象の発生または符号化対象データの終了に応答して前記回帰事象の発生の有無を判定する回帰事象判定工程と、前記回帰事象の発生に応答して前記反復数Ｎの値を示す反復数数値符号を生成する反復数数値符号生成工程と、前記反復数数値符号の生成後に前記反復数Ｎを所定の初期値に戻す回帰工程と、前記不一致事象の発生または前記回帰工程による反復数Ｎの初期化に応答して前記状態値Ｓの値を表現する状態符号を生成する状態符号生成工程と、前記状態符号生成工程による状態符号の生成または前記反復事象判定工程による反復事象の発生の判定後に、前記ＸがＡと一致しない場合に該Ｘに対応する数値符号を生成し、前記ＹがＢと一致しない場合に該Ｙに対応する数値符号を生成する数値符号生成工程と、前記数値符号生成工程による数値符号の生成または前記反復数加算工程による反復数Ｎの加算後に、前記Ａの内容をＸに更新し、前記Ｂの内容をＹに更新し、前記Ｔの内容をＳに更新する直前値更新工程とを含んだ
ことを特徴とする請求項１に記載のデータ符号化方法。
【請求項３】
符号列データを走査して得られる符号列を入力し、０のビット連続数Ｘと１のビット連続数Ｙとの組を単位とするランレングス値列に復元して出力するデータ復号化方法であって、
復号化を開始する際に、復元される状態値を記憶する記憶部Ｓ、復元されるランレングス値のうち前記Ｘに相当する値を記憶する記憶部Ｃおよび復元されるランレングス値のうち前記Ｙに相当する値を記憶する記憶部Ｄに所定の初期値を代入して初期化する初期化工程と、
所定の符号単位を入力して該符号が数値符号Ｐであるか状態符号Ｑであるかを判定する入力符号種判定工程と、
前記入力符号種判定工程により数値符号と判定された場合に、該符号を数値に復元して記憶部Ｌに記憶する数値符号復元工程と、
前記入力符号種判定工程により状態符号と判定された場合に、該符号を前記状態値に復元して前記Ｓに記憶する状態符号復元工程と、
前記Ｌに復元数値が格納された時点での状態値Ｓの値が、Ｘ≠Ａ且つＹ≠Ｂの関係にある状態Ｓ０、Ｘ＝Ａ且つＹ≠Ｂの関係にある状態Ｓ１、Ｘ≠Ａ且つＹ＝Ｂの関係にある状態Ｓ２若しくはＸ＝Ａ且つＹ＝Ｂの関係にある状態Ｓ３（ただし、Ａを直前の０のビットの連続数とし、Ｂを直前の１のビットの連続数とする）のいずれであるかを識別する識別工程と、
前記Ｓに新たな状態値が格納された時点で、該Ｓの値が前記Ｓ３と一致するか否かを判定するＳ３状態判定工程と、
前記識別工程により前記Ｓの値が前記Ｓ０であると識別された場合に、前記Ｌの値を前記Ｃに格納した後に、次の数値符号を入力および復元して、前記Ｄに格納する第１のラン値更新工程と、
前記識別工程により前記Ｓの値が前記Ｓ１であると識別された場合に、前記Ｌの値を前記Ｄに格納する第２のラン値更新工程と、
前記識別工程により前記Ｓの値が前記Ｓ２であると識別された場合に、前記Ｌの値を前記Ｃに格納する第３のラン値更新工程と、
前記第１、第２または第３のラン値更新工程による更新が終了した時点または前記Ｓ３状態判定工程により前記Ｓの値が状態値Ｓ３と一致すると判定された時点で、前記ＣおよびＤの値を一組のランレングス値として出力する第１の出力工程と、
前記識別工程により前記Ｓ値の値が前記Ｓ３であると識別された場合に、前記ＣおよびＤの値を一組のランレングス値として前記Ｌの値に対応する回数分出力する第２の出力工程と、
を含んだことを特徴とするデータ復号化方法。
【請求項４】
前記請求項１〜３のいずれか一つに記載された方法をコンピュータに実行させるプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、データを走査して得られるランレングス数値列を０のビット連続数と１のビット連続数との組を入力単位として順次入力し、所定の符号列に変換して出力するデータ符号化方法、符号列データを走査して得られる符号列を入力し、０のビット連続数Ｘと１のビット連続数Ｙとの組を単位とするランレングス数値列に復元して出力するデータ復号化方法、およびその方法をコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体に関する。
【０００２】
【従来の技術】
従来、レーザープリンタなどの印刷装置では、印刷対象となる画像データを圧縮（符号化）して一時的にメモリに蓄積し、このメモリに蓄積した圧縮データを伸張（復号）しながら実際の印刷をおこなうことにより、画像データを記憶するためのメモリのメモリ容量を低減する省メモリ技術が知られている。
【０００３】
かかる省メモリ技術の本来の目的は、画像データを記憶するメモリのメモリ容量を低減してコストダウンを図ることにあるので、画像データを圧縮又は伸張するための複雑な専用ハードウエアを設けるのは妥当ではなく、印刷装置のマイクロプロセッサにこれらの処理をソフトウエア的におこなわせる必要がある。
【０００４】
ここで、二次元静止画像の符号化技術としては、副走査方向のデータ相関を考慮してデータ圧縮をおこなう二次元圧縮技術や算術符号を用いて予測符号化をおこなう予想符号化技術が高い圧縮率を得ることができる技術として知られている。
【０００５】
しかし、印刷装置のマイクロプロセッサを用いてこれらの符号化技術をソフトウエア的に実現しようとすると、処理遅延が生じてしまうので、印刷解像度や印刷速度が日々向上する昨今では、これらの符号化技術を用いることは効率的ではない。このため、マイクロプロセッサに圧縮伸張をおこなわせる場合には、一次元圧縮と呼ばれる比較的単純な圧縮技術が広く用いられている。
【０００６】
従来の一次元圧縮技術としては、ランレングス処理やファクシミリ装置などで採用されているＭＨ（Modified Haffman）符号が広く知られているが、疑似中間調画像のような色（白黒）が短い周期で頻繁に変化する画像データの場合には、効率良く圧縮することができない。特に、パーソナルコンピュータやネットワークの進展によってイメージデータを印刷する機会が増加してきたため、このＭＨ符号を省メモリ機構として採用するのは効率的ではない。
【０００７】
このため、色が短い周期で頻繁に変化する画像データの圧縮率を改善するために、画像データやランレングスの繰り返し性を検出する符号化技術が知られている。たとえば、特許第２６８３５０６号公報（従来技術１）には、白ワードの長さと黒ワードの長さを両方記述可能な制御ワードを使用することにより、白ワードと黒ワードが比較的短い周期で規則的に現れるイメージデータを効率的に圧縮するデータ圧縮（伸張）方法及び装置が開示されている。
【０００８】
具体的には、この従来技術１では、あるワード長（バイト）を規定し、すべてが白であるデータ単位を白ワードとし、すべてが白でないものを黒ワードとして取り扱い、それらの繰り返し出現数、黒ワードの内容、制御語などをワード長単位で符号化しているので、符号化および復号化に際して特別な符号テーブルを必要とせず、また、ワード長単位で処理できるのでマイクロプロセッサで処理しても十分な処理性能を期待することができる。
【０００９】
また、特開平９−６５１４７号公報（従来技術２）には、白および黒の各々のランレングスを記憶し、ある色のランレングス値が同色の直前のランレングス値と一致する場合に、所定の反復符号を生成することにより、圧縮率および処理速度を改善する画像信号圧縮（復元）方法および装置が開示されている。
【００１０】
【発明が解決しようとする課題】
しかしながら、上記従来技術１では、ワード列単位で繰り返し性を検出しているので、対象となる画像データに含まれる繰り返しの周期とワード長とが一致するかまたは倍数となる場合にのみ高い圧縮率が得られるにすぎず、一般的な画像データについて十分な圧縮が得られないという問題がある。
【００１１】
また、上記従来技術２では、ラン長の一致が発生したときに生成される反復符号が一致しなかった場合に符号化される符号語に比べて十分に少ないデータ量である場合にのみ圧縮率が向上するものにすぎないという問題がある。すなわち、より短い符号語を反復符号に割り当てることは、相対的に一致しないラン長の符号語を長くするので、色が短い周期で頻繁に変化するような画像データに対しては十分な圧縮率を持つ符号セットを得ることが困難になる。
【００１２】
具体的には、この従来技術２の実施の形態では、符号セットはＭＨ符号に類似するものであり、マイクロプロセッサによる処理ではランレングス符号技術のような高速性を期待することができない。また、ランレングス値を記憶するための記憶部が色に対応して設けられているので、ランレングス値の比較や格納に際して、色に応じて参照・格納先を選択する処理が必要となり、マイクロプロセッサによる高速処理の妨げになるという問題もある。
【００１３】
なお、上記二次元圧縮技術、予測符号化技術およびＭＨ符号化などにおいては、ラインバッファ、確率テーブル、符号テーブルといった比較的大きな容量のメモリが必要になるという問題がある。たとえば、１２００ｄｐｉ（ドット／インチ）の解像度、２５ｐｐｍ（ページ／分）の印刷速度であれば、画素周波数は１００ＭＨｚを超えるのが一般的である。このような周波数で上記メモリを含む符号化／復号化のハードウエア回路を動作させることは極めて困難であり、また、たとえ回路を並列化して低周波数で動作させるとしても、テーブルをも含めて並列化する必要があるので大規模な回路となり、コストアップにつながる結果となる。
【００１４】
また、特願平１１−１２４７９号には、ランレングス値が同色の直前のランレングス値と一致する事象が連続する場合に、その連続数を符号化することにより、符号数を削減するよう構成することにより、疑似中間調画像データに対しても高い圧縮率と高い処理速度とを両立できるようにしたデータ符号化および復号化方法が記載されているが、誤差拡散処理を施した疑似中間調画像を含むような画像データの場合には、十分な圧縮率が得られない。
【００１５】
この発明は、上述した従来技術による問題点を解消するため、誤差拡散処理により生成された疑似中間調画像データについても効率良く圧縮することができ、マイクロプロセッサによるソフトウエア処理に適合するデータ符号化方法、データ復号化方法、およびその方法をコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体を提供することを目的とする。
【００１６】
【課題を解決するための手段】
上述した課題を解決し、目的を達成するため、請求項１の発明に係るデータ符号化方法は、データを走査して得られるランレングス値列を０のビット連続数と１のビット連続数との組を入力単位として順次入力し、所定の符号列に変換して出力するデータ符号化方法であって、前記入力単位のデータに対応する状態値の算定として、前記０のビットの連続数Ｘ、前記１のビットの連続数Ｙ、直前の０のビットの連続数Ａおよび直前の１のビットの連続数Ｂが、Ｘ≠Ａ且つＹ≠Ｂの関係にある場合に状態Ｓ０の値を状態値Ｓとし、Ｘ＝Ａ且つＹ≠Ｂの関係にある場合に状態Ｓ１の値を状態値Ｓとし、Ｘ≠Ａ且つＹ＝Ｂの関係にある場合に状態Ｓ２の値を状態値Ｓとし、Ｘ＝Ａ且つＹ＝Ｂの関係にある場合に状態Ｓ３の値を状態値Ｓとして算定する算定工程と、直前の状態値Ｔが状態Ｓ３であり、かつ、前記状態値Ｓと直前の状態値Ｔとが等しい一致事象となった場合にこれを反復事象とみなして、該反復事象が連続して発生する反復数Ｎを算出する反復数算定工程と、前記反復事象の発生後に、前記状態値Ｓと直前の状態値Ｔとが異なる不一致事象または入力完了となった場合に回帰事象と判定する回帰事象判定工程と、前記不一致事象が発生した場合に前記状態値Ｓの値を示す状態符号を生成する状態符号生成工程と、前記状態符号生成工程による状態符号の生成が終了するかまたは前記一致事象が発生した際に、前記０のビットの連続数Ｘまたは前記１のビットの連続数Ｙの値を示す数値符号を生成する第１の数値符号生成工程と、前記回帰事象が発生した場合に、前記状態符号生成工程による状態符号の生成に先だって、前記反復数算定工程によって算定された反復数Ｎの値を示す数値符号を生成する第２の数値符号生成工程と、を含んで前記入力単位のデータに対応する状態符号および数値符号の生成する生成工程と、を含んだことを特徴とする。
【００１７】
この請求項１の発明によれば、入力単位のデータに対応する状態値の算定で、０のビットの連続数Ｘ、１のビットの連続数Ｙ、直前の０のビットの連続数Ａおよび直前の１のビットの連続数Ｂが、Ｘ≠Ａ且つＹ≠Ｂの関係にある場合に状態Ｓ０の値を状態値Ｓとし、Ｘ＝Ａ且つＹ≠Ｂの関係にある場合に状態Ｓ１の値を状態値Ｓとし、Ｘ≠Ａ且つＹ＝Ｂの関係にある場合に状態Ｓ２の値を状態値Ｓとし、Ｘ＝Ａ且つＹ＝Ｂの関係にある場合に状態Ｓ３の値を状態値Ｓとして算定して、直前の状態値Ｔが状態Ｓ３であり、かつ、状態値Ｓと直前の状態値Ｔとが等しい一致事象となった場合にこれを反復事象とみなして、該反復事象が連続して発生する反復数Ｎを算出し、反復事象の発生後に、状態値Ｓと直前の状態値Ｔとが異なる不一致事象または入力完了となった場合に回帰事象と判定し、不一致事象が発生した場合に状態値Ｓの値を示す状態符号を生成し、この状態符号の生成が終了するかまたは一致事象が発生した際に、０のビットの連続数Ｘまたは１のビットの連続数Ｙの値を示す数値符号を生成し、回帰事象が発生した場合に、状態符号の生成に先だって反復数Ｎの値を示す数値符号を生成することとしたので、一致事象、不一致事象、反復事象、回帰事象の概念を利用して、誤差拡散処理により生成された疑似中間調画像データについても効率良くデータを圧縮することができる。
【００２２】
また、請求項２の発明に係るデータ符号化方法は、請求項１の発明において、前記算定工程は、符号化を開始する際に、Ｔ、Ａ、Ｂおよび反復数Ｎにそれぞれ所定の初期値を格納する初期化工程と、前記ＸおよびＹに前記ランレングス値を入力する入力工程と、前記入力工程による入力後に、前記状態値Ｓを生成する状態値生成工程とを含み、前記生成工程は、前記状態値生成工程により生成された状態値Ｓに対応して前記一致事象または不一致事象の発生を判定する一致事象判定工程と、前記一致事象の発生に応答して前記反復事象の発生の有無を判定する反復事象判定工程と、前記反復事象の発生に応答して前記反復数を加算する反復数加算工程と、前記不一致事象の発生または符号化対象データの終了に応答して前記回帰事象の発生の有無を判定する回帰事象判定工程と、前記回帰事象の発生に応答して前記反復数Ｎの値を示す反復数数値符号を生成する反復数数値符号生成工程と、前記反復数数値符号の生成後に前記反復数Ｎを所定の初期値に戻す回帰工程と、前記不一致事象の発生または前記回帰工程による反復数Ｎの初期化に応答して前記状態値Ｓの値を表現する状態符号を生成する状態符号生成工程と、前記状態符号生成工程による状態符号の生成または前記反復事象判定工程による反復事象の発生の判定後に、前記ＸがＡと一致しない場合に該Ｘに対応する数値符号を生成し、前記ＹがＢと一致しない場合に該Ｙに対応する数値符号を生成する数値符号生成工程と、前記数値符号生成工程による数値符号の生成または前記反復数加算工程による反復数Ｎの加算後に、前記Ａの内容をＸに更新し、前記Ｂの内容をＹに更新し、前記Ｔの内容をＳに更新する直前値更新工程とを含んだことを特徴とする。
【００２３】
この請求項２の発明によれば、符号化を開始する際に、Ｔ、Ａ、Ｂおよび反復数Ｎにそれぞれ所定の初期値を格納し、ＸおよびＹにランレングス値を入力し、この入力後に状態値Ｓを生成し、生成された状態値Ｓに対応して一致事象または不一致事象の発生を判定し、一致事象の発生に応答して反復事象の発生の有無を判定し、反復事象の発生に応答して反復数を加算するし、不一致事象の発生または符号化対象データの終了に応答して回帰事象の発生の有無を判定し、回帰事象の発生に応答して反復数Ｎの値を示す反復数数値符号を生成し、反復数数値符号の生成後に反復数Ｎを所定の初期値に戻し、不一致事象の発生または反復数Ｎの初期化に応答して状態値Ｓの値を表現する状態符号を生成し、状態符号の生成または反復事象の発生の判定後に、ＸがＡと一致しない場合に該Ｘに対応する数値符号を生成し、ＹがＢと一致しない場合に該Ｙに対応する数値符号を生成し、数値符号の生成または反復数Ｎの加算後に、Ａの内容をＸに更新し、Ｂの内容をＹに更新し、Ｔの内容をＳに更新することとしたので、マイクロプロセッサによるソフトウエア処理に適合したデータの圧縮をおこなうことができる。
【００２４】
また、請求項３の発明に係るデータ復号化方法は、符号列データを走査して得られる符号列を入力し、０のビット連続数Ｘと１のビット連続数Ｙとの組を単位とするランレングス値列に復元して出力するデータ復号化方法であって、復号化を開始する際に、復元される状態値を記憶する記憶部Ｓ、復元されるランレングス値のうち前記Ｘに相当する値を記憶する記憶部Ｃおよび復元されるランレングス値のうち前記Ｙに相当する値を記憶する記憶部Ｄに所定の初期値を代入して初期化する初期化工程と、所定の符号単位を入力して該符号が数値符号Ｐであるか状態符号Ｑであるかを判定する入力符号種判定工程と、前記入力符号種判定工程により数値符号と判定された場合に、該符号を数値に復元して記憶部Ｌに記憶する数値符号復元工程と、前記入力符号種判定工程により状態符号と判定された場合に、該符号を前記状態値に復元して前記Ｓに記憶する状態符号復元工程と、前記Ｌに復元数値が格納された時点での状態値Ｓの値が、Ｘ≠Ａ且つＹ≠Ｂの関係にある状態Ｓ０、Ｘ＝Ａ且つＹ≠Ｂの関係にある状態Ｓ１、Ｘ≠Ａ且つＹ＝Ｂの関係にある状態Ｓ２若しくはＸ＝Ａ且つＹ＝Ｂの関係にある状態Ｓ３（ただし、Ａを直前の０のビットの連続数とし、Ｂを直前の１のビットの連続数とする）のいずれであるかを識別する識別工程と、前記Ｓに新たな状態値が格納された時点で、該Ｓの値が前記Ｓ３と一致するか否かを判定するＳ３状態判定工程と、前記識別工程により前記Ｓの値が前記Ｓ０であると識別された場合に、前記Ｌの値を前記Ｃに格納した後に、次の数値符号を入力および復元して、前記Ｄに格納する第１のラン値更新工程と、前記識別工程により前記Ｓの値が前記Ｓ１であると識別された場合に、前記Ｌの値を前記Ｄに格納する第２のラン値更新工程と、前記識別工程により前記Ｓの値が前記Ｓ２であると識別された場合に、前記Ｌの値を前記Ｃに格納する第３のラン値更新工程と、前記第１、第２または第３のラン値更新工程による更新が終了した時点または前記Ｓ３状態判定工程により前記Ｓの値が状態値Ｓ３と一致すると判定された時点で、前記ＣおよびＤの値を一組のランレングス値として出力する第１の出力工程と、前記識別工程により前記Ｓ値の値が前記Ｓ３であると識別された場合に、前記ＣおよびＤの値を一組のランレングス値として前記Ｌの値に対応する回数分出力する第２の出力工程と、を含んだことを特徴とする。
【００２５】
この請求項３の発明によれば、復号化を開始する際に、復元される状態値を記憶する記憶部Ｓ、復元されるランレングス値のうち前記Ｘに相当する値を記憶する記憶部Ｃおよび復元されるランレングス値のうち前記Ｙに相当する値を記憶する記憶部Ｄに所定の初期値を代入して初期化し、所定の符号単位を入力して該符号が数値符号Ｐであるか状態符号Ｑであるかを判定し、数値符号と判定された場合に、該符号を数値に復元して記憶部Ｌに記憶し、状態符号と判定された場合に、該符号を状態値に復元してＳに記憶し、Ｌに復元数値が格納された時点での状態値Ｓの値が、Ｘ≠Ａ且つＹ≠Ｂの関係にある状態Ｓ０、Ｘ＝Ａ且つＹ≠Ｂの関係にある状態Ｓ１、Ｘ≠Ａ且つＹ＝Ｂの関係にある状態Ｓ２若しくはＸ＝Ａ且つＹ＝Ｂの関係にある状態Ｓ３のいずれであるかを識別し、Ｓに新たな状態値が格納された時点で、該Ｓの値がＳ３と一致するか否かを判定し、Ｓの値がＳ０であると識別された場合に、Ｌの値をＣに格納した後に次の数値符号を入力および復元してＤに格納し、Ｓの値がＳ１であると識別された場合に、Ｌの値をＤに格納し、Ｓの値がＳ２であると識別された場合に、Ｌの値をＣに格納し、更新が終了した時点またはＳの値が状態値Ｓ３と一致すると判定された時点で、ＣおよびＤの値を一組のランレングス値として出力し、Ｓ値の値がＳ３であると識別された場合に、ＣおよびＤの値を一組のランレングス値としてＬの値に対応する回数分出力することとしたので、誤差拡散処理により生成された疑似中間調画像データを圧縮したものを効率良く復元することができる。
【００２６】
また、請求項４の発明に係る記録媒体は、請求項１〜３のいずれか一つに記載された方法をコンピュータに実行させるプログラムを記録したことで、そのプログラムを機械読み取り可能となり、これによって、請求項１〜３のいずれか一つの動作をコンピュータによって実現することができる。
【００２７】
【発明の実施の形態】
以下に添付図面を参照して、この発明に係るデータ符号化方法、データ復号化方法、およびその方法をコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体の好適な実施の形態を詳細に説明する。なお、本実施の形態では、誤差拡散処理により生成された疑似中間調画像データをデータ符号化または復号化する場合を示すこととする。
【００２８】
まず最初に、本実施の形態に係るデータ符号化方法およびデータ復号化方法の概念について説明する。図１は、本実施の形態に係るデータ符号化方法およびデータ復号化方法の概念を説明するための説明図である。
【００２９】
同図においては、データを走査して得られるランレングス数値列について、値が’０’であるビットの連続数（以下「Ｘ」と言う）と、値が’１’であるビットの連続数（以下「Ｙ」と言う）との一組を入力単位として順次入力し、所定の符号列に変換して出力するデータ符号化をおこなう。
【００３０】
具体的には、このＸの直前の値を「Ａ」、Ｙの直前の値を「Ｂ」とし、
Ｘ≠Ａ  且つ  Ｙ≠Ｂ
の状態をＳ０とし、
Ｘ＝Ａ  且つ  Ｙ≠Ｂ
の状態をＳ１とし、
Ｘ≠Ａ  且つ  Ｙ＝Ｂ
の状態をＳ２とし、
Ｘ＝Ａ  且つ  Ｙ＝Ｂ
の状態をＳ３とする。
【００３１】
また、この状態に応じてＳ０〜Ｓ３のいずれかの値を持つ状態値を「Ｓ」とし、このＳの直前の値を「Ｔ」とする。そして、Ｓ＝Ｔとなる事象を「一般事象」とし、Ｓ≠Ｔとなる事象を「不一致事象」とし、このＴがＳ３であるときに一致事象が発生すれば「反復事象」とし、この反復事象が連続して発生する数を「反復数Ｎ」とする。
【００３２】
さらに、この反復事象が発生した後に、不一致事象が発生するかまたは入力が完了すれば「回帰事象」とし、不一致事象が発生した場合には状態値Ｓの値を示す状態符号Ｑを生成し、符号生成を終了した時点または一致事象が発生した時点において、Ｘ≠Ａである場合にはＸの値を示す数値符号Ｐを生成し、Ｙ≠Ｂである場合にはＹの値を示す数値符号Ｐを生成し、回帰事象が発生した場合には状態符号の生成に先立って反復数Ｎの値を示す数値符号Ｐを生成する。
【００３３】
図１においては、圧縮対象となるデータが３ビットの’０’で始まり、４ビットの’１’、３ビットの’０’へと続く場合を示している。ランレングスの計測を’０’から始める場合には、データを走査して得られるＸおよびＹの数値列は、それぞれ’０’の連続数および’１’の連続数となるので、この一組の値が符号化部に順次入力されることになる。
【００３４】
同図では、各入力値についての各数値、事象および生成される符号を図示しているが、各事象に関しては、事象がある場合には’○’を記載し、事象がない場合には空欄としている。また、各符号に関しては、符号出力がある場合には’○’を記載し、符号が出力されない場合には空欄としている。
【００３５】
なおここでは、状態符号と数値符号の２つの属性を持つが、数値符号についてはどの数値に対応するものであるかを把握できるように３種類に分けて図示している。また厳密に言うと、データの最初のＸ、ＹおよびＳには直前の値（Ａ、ＢおよびＴ）が存在しないことになるが、ここではＡ、ＢおよびＳの初期値はすべて’０’とする。
【００３６】
このように、本実施の形態では、ランレングス値が同一計測対象値の直前のランレングス値と一致する事象が連続する場合に、その連続数を符号化することで符号数を削減するという従来技術の特徴を、Ｓ３が複数回連続する場合に反復数Ｎに対応する数値符号Ｐを生成することで承継することにより効率的に符号数を削減している。加えて、ＸまたはＹのいずれか一方が直前の値と一致する反面他方が一致しない場合すなわちＳ１またはＳ２の状態が連続する場合にも効率的に符号数を削減している。
【００３７】
特に、誤差拡散された画像データにおいては、Ｓ１およびＳ２の状態が連続する確率が高いので、この実施の形態による符号数削減の効果は大きい。たとえば、同図では、１２組すなわち２４個のランレングス値が入力されているが、出力される符号数は１１個に削減され、符号数が削減されていることが分かる。
【００３８】
次に、本実施の形態で用いる符号化手順について説明する。図２は、本実施の形態で用いる符号化手順を示すフローチャートであり、図３は、図２のステップＳ２０９およびＳ２１９に示す未出力Ｎ符号化手順を示すフローチャートである。
【００３９】
図２に示すように、まず最初に、Ａ、ＢおよびＴに所定の定数Ｃを設定し、Ｎに０を設定する初期化処理をおこなう（ステップＳ２０１）。なお、ここでは説明の便宜上、Ａ、ＢおよびＴに同じ定数Ｃを設定することとするが、異なる値を設定することもできる。ただし、Ｔの初期値はＳ０に示す値であることが符号数を削減するうえで望ましい。その理由は、最初のＸおよびＹの入力に対して状態値ＳがＳ０となる場合が最も高い確率で発生するため、無意味な不一致事象の発生による状態符号の生成を抑制できるからである。また、ＡおよびＢの初期値は、ランレングスの測定を開始する際の値と異なる値を設定することが符号数を削減するうえで望ましい。
【００４０】
そして、かかる初期化処理を終えたならば、ＸおよびＹに一組のランレングス値を入力して格納する入力処理をおこない（ステップＳ２０２）、この入力に対応して所定の状態Ｓを生成する状態作成処理をおこなう（ステップＳ２０３〜Ｓ２０７）。
【００４１】
具体的には、まずＳ値に０を代入してを初期化した後に（ステップＳ２０３）、Ｘ値とＡ値を比較して（ステップＳ２０４）、両者が一致する場合には（ステップＳ２０４肯定）このＳに’１’を加算し（ステップＳ２０５）、一致しない場合には（ステップＳ２０４否定）そのままステップＳ２０６に移行する。さらに、Ｙ値をＢ値と比較して（ステップＳ２０６）、両者が一致する場合には（ステップＳ２０６肯定）Ｓに’２’を加算する（ステップＳ２０７）。したがって、Ｓ０を表す数値は０、Ｓ１を表す数値は１、Ｓ２を表す数値は２、Ｓ３を表す数値は３となる。
【００４２】
その後、生成された状態値Ｓの値がＴと一致するか否かを判断する一致事象判定処理をおこない（ステップＳ２０８）、一致する場合（ステップＳ２０８肯定）には一致事象であると判断し、一致しない場合（ステップＳ２０８否定）には不一致事象であると判断する。
【００４３】
具体的には、一致事象が発生した場合には（ステップＳ２０８肯定）、Ｓ値が３であるか否かを判断し（ステップＳ２１１）、このＳ値が３すなわちＳ３と一致する場合に（ステップＳ２１１肯定）反復事象があるものと判定し、反復数Ｎの値をインクリメントして（ステップＳ２１２）、ステップＳ２１７に移行する。
【００４４】
これに対して、不一致事象が発生した場合には（ステップＳ２０８否定）、反復事象が発生しないものと判定して、未出力Ｎ符号化をおこなう（ステップＳ２０９）。具体的には、図３に示すように、反復数Ｎの値が０よりも大きいか否かを判断し（ステップＳ３０１）、０よりも大きい場合には（ステップＳ３０１肯定）、回帰事象が発生したものと判定し、数値符号化（Ｎ）をおこなって数値符号を出力した後（ステップＳ３０２）、Ｎに０を代入して初期化する（ステップＳ３０３）。一方、反復数Ｎの値が０のままである場合には（ステップＳ３０１否定）、回帰事象が発生していないものと判断する。
【００４５】
そして、この未出力Ｎ符号化を終えたならば、状態Ｓの値を表現する状態符号を生成し出力する状態符号化（Ｓ）をおこない（ステップＳ２１０）、ラン数値符号出力処理をおこなう（ステップＳ２１３〜Ｓ２１６）。
【００４６】
具体的には、まずＸ値とＡ値を比較し（ステップＳ２１３）、両者が一致しない場合には（ステップＳ２１３否定）、Ｘの値を表現する状態符号を生成し出力する数値符号化（Ｘ）をおこなう（ステップＳ２１４）。また、Ｙ値とＢ値を比較し（ステップＳ２１５）、両者が一致しない場合には（ステップＳ２１５否定）、Ｙの値を表現する状態符号を生成し出力する数値符号化（Ｙ）をおこなう（ステップＳ２１６）。
【００４７】
その後、ＡをＸ値で更新し、ＢをＹ値で更新し、ＴをＳ値で更新する直前値の更新をおこない（ステップＳ２１７）、符号化対象データがあるならば（ステップＳ２１８否定）ステップＳ２０２に移行して上記処理を繰り返す。なお符号化対象データがなくなった場合には（ステップＳ２１８肯定）、すでに説明した未出力Ｎ符号化をおこなって（ステップＳ２１９）処理を終了する。
【００４８】
上記一連の処理をおこなうことにより、不一致事象が発生した場合には状態値Ｓの値を示す状態符号Ｑを生成し、符号生成を終了した時点または一致事象が発生した時点で、Ｘ≠Ａである場合にはＸの値を示す数値符号Ｐを生成し、Ｙ≠Ｂである場合にはＹの値を示す数値符号Ｐを生成し、回帰事象が発生した場合には、状態符号の生成に先立って反復数Ｎの値を示す数値符号Ｐを生成して符号化することができる。
【００４９】
なお、上記処理手順をソフトウエアで実現する場合には、Ｘ，Ｙ，Ａ，Ｂ，Ｓ，ＴおよびＮには適切なメモリを割り当てれば良いが、マイクロプロセッサの汎用レジスタを用いることが処理性能を向上するうえで望ましい。また、定数Ｃと各制御については、プログラムすなわち命令コードとして記述することで実現できる。
【００５０】
また、上記一連の説明では説明の便宜上、ランレングス測定入力（ステップＳ２０２）およびこれに関連するデータ終了判定（ステップＳ２１８）および符号生成（ステップＳ２１０、Ｓ２１４、Ｓ２１６、Ｓ３０２）についての詳細な説明を省略した。
【００５１】
次に、本実施の形態に係るデータ復号手順について説明する。図４は、本実施の形態に係るデータ復号手順を示すフローチャートである。同図に示すように、復号処理を開始する際に、復元される状態値を記憶するＳと、復元されるランレングス値のうちＸに相当する値を記憶するＡと、Ｙに相当する値を記憶するＢとに、それぞれ定数Ｃを代入して初期化する（ステップＳ４０１）。なお、復号が正しくおこなわれるためには、Ａ、ＢおよびＳに代入される初期値は、符号化時の初期化処理（図２のステップＳ２０１）時に、Ａ、ＢおよびＳに代入した値と同じ値を代入する必要がある。
【００５２】
そして、この初期化処理を終えたならば、符号入力をＫに代入し（ステップＳ４０２）、このＫが数値符号Ｐであるか状態符号Ｑであるかを判断する入力符号判定処理（ステップＳ４０３）をおこなう。その結果、数値符号であると判断された場合には（ステップＳ４０３肯定）、このＫに格納された符号を数値に復元してＬに記憶する数値復元処理（ステップＳ４０４）をおこない、状態識別処理（ステップＳ４０５〜４０７）に移行する。
【００５３】
具体的には、状態値Ｓが０であるか否かを確認し（ステップＳ４０５）、状態値Ｓが０である場合には（ステップＳ４０５肯定）、Ｓ０に対応する処理すなわちＡに復元されたランレングス値であるＬの値を格納し（ステップＳ４０８）、次の符号単位を入力してＫに格納し（ステップＳ４０９）、Ｋに格納された符号を数値に復元してＬに格納し（ステップＳ４１０）、Ｌの値をＢに格納する（ステップＳ４１１）処理をおこない、Ａを出力ＸとしＢを出力Ｙとした一組のランレングス値として出力する（ステップＳ４１４）。
【００５４】
また、状態値Ｓが０でない場合には（ステップＳ４０５否定）、状態値Ｓが１であるか否かを確認し（ステップＳ４０６）、状態値Ｓが１である場合には（ステップＳ４０６肯定）、Ｓ１に対応する処理すなわちＬ値をＢに格納する処理をおこない（ステップＳ４１２）、Ａを出力ＸとしＢを出力Ｙとした一組のランレングス値として出力する（ステップＳ４１４）。
【００５５】
さらに、状態値Ｓが１でない場合には（ステップＳ４０６否定）、状態値Ｓが２であるか否かを確認し（ステップＳ４０７）、状態値Ｓが２である場合には（ステップＳ４０７肯定）、Ｓ２に対応する処理すなわちＬ値をＡに格納する処理をおこない（ステップＳ４１３）、Ａを出力ＸとしＢを出力Ｙとした一組のランレングス値として出力する（ステップＳ４１４）。
【００５６】
また、状態値Ｓが２でない場合には（ステップＳ４０７否定）、Ｓ３に対応する処理をおこなう。具体的には、Ｌの値を初期値としてＮに格納した後（ステップＳ４１７）、Ａを出力ＸとしＢを出力Ｙとした一組のランレングス値として出力し（ステップＳ４１８）、Ｎをデクリメントした後（ステップＳ４１９）、このＮの値が０でなければ（ステップＳ４２０否定）、ステップＳ４１８に移行して処理を繰り返す。そして、Ｎの値が０になった時点で（ステップＳ４２０肯定）、終了判定をおこない（ステップＳ４２１）、終了しない場合には（ステップＳ４２１否定）、上記ステップＳ４０２に移行する。
【００５７】
また、上記ステップＳ４０３で数値符号であると判断された場合には（ステップＳ４０３否定）、Ｋに格納された符号を状態値に復元してＳに格納し（ステップＳ４１５）、このＳが３であるか否かを確認する（ステップＳ４１６）。その結果、このＳが３である場合には（ステップＳ４１６肯定）、ステップＳ４１４に移行し、Ｓが３でなければ（ステップＳ４１６否定）ステップＳ４２１に移行する。
【００５８】
上記一連の処理をおこなうことにより、状態符号を入力して所定の状態値Ｓに復元した時点で、このＳがＳ３の状態である場合には一組のランレングス値が省略されているので、数値符号の入力を待つことなくその時点でＡおよびＢに記憶した一組のランレングス値の出力をおこなうことができる。
【００５９】
また、数値符号を入力し所定の数値に復元してＬに記憶した時点で、このＳ値がＳ０である場合には、一組のランレングス値が一組の数値符号に符号化されているので、このＬに記憶した値と次の数値符号を復号して得られる値とを用いて一組のランレングス値の出力をおこなう。
【００６０】
また、このＳ値がＳ１である場合には、０の連続数に対する数値符号が省略されているので、Ａに記憶した値と復元した数値Ｌとを用いて一組のランレングス値の出力をおこない、このＳ値がＳ２である場合には、１の連続数に対する数値符号が省略されているので、Ｂに記憶した値と復元した数値Ｌとを用いて一組のランレングス値の出力をおこなう。
【００６１】
さらに、このＳ値がＳ３である場合には、復元された数値は反復数Ｎであり、Ｎ組のランレングス値が省略されているので、その時点でＡおよびＢに記憶された値を用いて一組のランレングス値の出力動作を数値の回数分繰り返す。このため、図２に示したデータ符号化手順で生成した符号列データから元のランレングス列を復号することができる。
【００６２】
なお、上記処理手順をソフトウエアで実現する場合には、Ｘ，Ｙ，Ａ，Ｂ，Ｓ，Ｔ，Ｋ，ＬおよびＮには適切なメモリを割り当てれば良いが、マイクロプロセッサの汎用レジスタを用いることが処理性能を向上するうえで望ましい。また、定数Ｃと各制御については、プログラムすなわち命令コードとして記述することで実現できる。
【００６３】
また、上記一連の処理のいくつかは省略することができ、たとえば、反復数を計数記憶するためのＮと、復元された数値を記憶するＬとを兼用して一方を省略することもできる。出力ランレングス値を記憶するＸおよびＹの一方で他方を代用することもできる。
【００６４】
さらに、上記一連の説明では説明の便宜上、ランレングス数値出力（ステップＳ４１４およびＳ４１８）およびこれに関連するデータ終了判定（ステップＳ４２１）についての詳細な説明を省略した。
【００６５】
次に、図２および図４に示したデータ符号化処理およびデータ復号化処理に用いる符号セットについて説明する。図５は、図２および図４に示したデータ符号化処理およびデータ復号化処理に用いる符号セットの一例を示す説明図である。
【００６６】
同図に示すように、本実施の形態で用いる符号セットは第１〜第６の６種類の符号単位で構成され、具体的には、第１の符号形式Ｐ１〜第３の符号形式Ｐ３は数値を示す数値符号Ｐであり、第４の符号形式Ｑ１〜第６の符号形式Ｑ３は、状態値を示す状態符号Ｑである。
【００６７】
ここで、第１の符号形式Ｐ１は、４ビット幅を有し、該４ビットの数値が”１０”未満であることを利用して識別されるものであり、該数値に１を加算した値が数値Ｌに対応する。第２の符号形式Ｐ２は、８ビット幅を有し、符号列において先行する上位４ビットの値が”１１”または”１２”であることにより識別されるものであり、下位ビットの値に”１１”を加算した値が数値Ｌに対応する。
【００６８】
第３の符号形式Ｐ３は、少なくとも８ビット幅で４の倍数となるビット幅を有し、符号列において先行する上位４ビットの値が”１２”であることにより識別される。この４ビットについては、’８’以上の数値が検出されるまで各４ビットの下位３ビットを上位に向かって連接した（つなぎ合わせた）数値に”４３”を加算した値が数値Ｌに対応する。
【００６９】
第４の符号形式Ｑ１は、４ビット幅を有し、該４ビットの数値が”１３”であることにより識別され、直前の状態値に’１’を加算した値の下位２ビットが新たな状態値に対応する。第５の符号形式Ｑ２は、４ビット幅を有し、該４ビットの数値が”１４”であることにより識別され、直前の状態値に’２’を加算した値の下位２ビットが新たな状態値に対応する。第６の符号形式Ｑ３は、４ビット幅を有し、該４ビットの数値が”１５”であることにより識別され、直前の状態値に’３’を加算した値の下位２ビットが新たな状態値に対応する。
【００７０】
なお、状態値の値としては４つの値を取り得るが、状態符号は状態値に変化が生じた場合にのみ生成される。ある状態値から他の状態値への移行対象は３つしかないので、状態符号の数は３つに削減されている。
【００７１】
また、数値符号Ｐにおいて、値が’０’となる符号を明示していないが、後述する変換手順を用いて’０’を表現することが望ましい。ただし、この符号形式は、表現可能な値域を原理的に制約するものではなく、第３の符号形式Ｐ３を用いる場合には任意の整数を表現することができる点に留意する必要がある。なぜなら、数値を復元する処理に用いられる一時記憶は有限のビット幅を持つものであるが、Ｐ３符号の長さには制約がないので、連接と加算による処理結果が桁上がりによる’０’や負数となる符号を生成できるからである。
【００７２】
次に、図５に示した符号セットを用いた場合の入力符号種判定、状態符号化制御、状態復元処理、数値符号化処理および数値復元処理について説明する。まず、入力符号種の判定（図４のステップＳ４０３に対応する）においては、符号の先行する上位４ビットの値が”１２”以下の値であれば数値符号であると判断し、それ以外の場合には状態符号であると判断することができる。
【００７３】
図６は、図５に示した符号セットを用いた場合の状態符号化制御手順を示すフローチャートであり、図７は、図５に示した符号セットを用いた場合の状態復号化制御手順を示すフローチャートである。なお、図中に示す「Ｋ（ｎ）←数値」は、右辺の数値の下位ｎビットを符号として出力することを意味し、「Ｗ」は、演算に使用する作業メモリである。
【００７４】
図６に示すように、状態符号化をおこなう場合には、状態値Ｓから直前の状態値Ｔを減じた値と’３’とをビットごとに論理和し、これに”１２”を加算した値を作業メモリＷに格納し（ステップＳ６０１）、この作業メモリＷの下位４ビットを４ビットの符号Ｋとして出力する（ステップＳ６０２）ことになる。
【００７５】
図７に示すように、状態復号化をおこなう場合には、Ｑ１〜Ｑ３のいずれかの符号の発生に対応して、符号の値から”１２”を減じた値をそれまでの状態値Ｓに加算し、その結果の値と定数値’３’とのビットごとの論理積をとってこれを新たな状態値として状態値Ｓに格納する（ステップＳ７０１）ことになる。
【００７６】
上記図６および図７に示す制御をおこなうことにより、所定の状態符号の生成および該状態符号を用いた状態値の復元が可能となる。たとえば、符号化の直前の状態値Ｔが’０’で新たな状態値Ｓが’３’である場合には、「Ｓ−Ｔ」は’３’となるため、この値と定数値’３’のビットごとの論理積は’３’となる。そして、この値に”１２”を加えた”１５”すなわちＱ３符号が生成される。一方、状態符号を復元する際には、「Ｋ−１２」は”３”となり、この値にそれまでの状態値’０’を加えた値’３’と定数値’３’のビットごとの論理積をとると、’３’が新たな状態値Ｓとなり、正しく復元されていることが分かる。
【００７７】
また、符号化の直前の状態値Ｔが’３’で新たな状態値Ｓが’０’である場合には、「Ｓ−Ｔ」は’−３’となり、この値と定数値’３’のビットごとの論理積は’１’となるので、この値に”１２”を加えた”１３”すなわちＱ１符号が生成される。一方、状態符号を復元する際には、「Ｋ−１２」は”１”となり、この値にそれまでの状態値’３’を加えた値’４’と定数値’３’のビットごとの論理積をとると、’０’が新たな状態値Ｓとなり、正しく復元されていることが分かる。
【００７８】
図８は、図５に示した符号セットを用いた場合の数値符号化制御手順を示すフローチャートであり、図９は、図５に示した符号セットを用いた場合の数値復号化制御手順を示すフローチャートである。なお、図中に示す「Ｋ（ｎ）←数値」は、右辺の数値の下位ｎビットを符号として出力することを意味し、「Ｗ」は、演算に使用する作業メモリである。
【００７９】
図８に示すように、ここでは符号化対象である数値「Ｖ」をＰ１〜Ｐ３のいずれかの符号に変換して出力する。すでに言及したように、この数値符号Ｐには値が’０’となる符号が定義されていないので、ここでは「Ｖ＝０」である場合にはこれを「Ｚ」という定数値に変換する０値変換処理をおこなっている。すなわち、Ｖ＝０となる頻度が非常に低いため、これを比較的に長い符号語に割り当てることにより圧縮率の改善を図っている。具体的には、下記に示すステップＳ８０１〜Ｓ８０４がこの０値変換処理に相当し、ステップＳ８０５以降が数値から符号語を生成する処理に相当する。
【００８０】
同図に示すように、まず最初に、符号化対象値Ｖが定数値Ｚ以上であるか否かを判断し（ステップＳ８０１）、Ｚ以上である場合には（ステップＳ８０１肯定）Ｖの値をインクリメントする（ステップＳ８０２）。また、Ｚ以上でない場合には（ステップＳ８０１否定）Ｖが０であるか否かを判断し（ステップＳ８０３）、Ｚが０であれば（ステップＳ８０３肯定）Ｖに定数値Ｚを格納する（ステップＳ８０４）。
【００８１】
そして、この０値変換処理を終えたならば、その時点での符号化対象値Ｖが”１０”以下であるか否かを判断し（ステップＳ８０５）、”１０”以下である場合には（ステップＳ８０５肯定）、Ｖから’１’を減じた値の下位４ビットを符号として出力して（ステップＳ８０６）、数値符号化を終了する。
【００８２】
一方、Ｖが”１０”以下でない場合には（ステップＳ８０５否定）、このＶが”４２”以下であるか否かを判断し（ステップＳ８０７）、”４２”以下である場合には（ステップＳ８０７肯定）このＶに”１４９”を加えた値の下位８ビットを符号として出力し（ステップＳ８０８）、数値符号化を終了する。Ｐ２符号の定義から、「Ｋ（８）←１６０＋（Ｖ−１１）」すなわち「Ｋ（８）←Ｖ＋１４９」となるので、ここで生成される符号がＰ２符号にほかならない。なお、この”１６０”を２進数表現すると「１０１０００００」となるので、上位３ビットが符号固有の定数となる。
【００８３】
また、上記ステップＳ８０７において、Ｖが”４２”以下でないと判断された場合には（ステップＳ８０７否定）、まずＰ３符号の開始識別符号として”１２”の値を持つ４ビットの符号を出力する（ステップＳ８０９）。その後、このＶから”４３”を減じた値を作業メモリＷに格納し（ステップＳ８１０）、このＷの値が’８’未満であるか否かを調べる（ステップＳ８１１）。
【００８４】
その結果、’８’以上である場合には（ステップＳ８１１否定）、Ｗ値の下位３ビットの値を４ビットの符号として出力するとともに（ステップＳ８１２）、このＷ値を３ビット分右にシフトして符号出力した部分を切り捨てた後に（ステップＳ８１３）、上記ステップＳ８１１に戻る。
【００８５】
これに対して、’８’未満である場合には（ステップＳ８１１肯定）、Ｗ値に’８’を加えた値を４ビットの符号として出力して（ステップＳ８１４）、数値符号化を終了する。なお、定数’７’を２進数表現すると「０１１１」となるので、ステップＳ８１２で生成される符号は常に’８’以上の数値となり、この符号が数値部の最後のものであることを明示でき、この符号がＰ３符号に他ならないことが分かる。
【００８６】
図９に示すように、数値復元をおこなう場合には、Ｐ１〜Ｐ３のいずれかの符号形式で符号化された符号列を順次４ビット単位で読み出し、作業メモリＷに数値を復元することになる。なお、「Ｋ←符号入力」なる標記は、Ｋに４ビットの符号を数値として入力することを意味する。また、ここでは図８に示した０値変換処理の逆変換である「０値逆変換処理」をおこなっている。下記に示すステップＳ９０１〜Ｓ９１１が数値復元処理に相当し、ステップＳ９１２以降が０値逆変換処理に相当する。
【００８７】
同図に示すように、数値復元処理をおこなう場合には、まず符号の最初の４ビットをＫに入力し（ステップＳ９０１）、このＫ値が”１０”未満であるか否かを判断する（ステップＳ９０２）。そして、Ｋ値が”１０”未満である場合には（ステップＳ９０２肯定）、このＫ値に’１’を加えた値を復元数値としてＷに格納し（ステップＳ９０３）、後述する０値逆変換処理に移行する。なお、最初の４ビットが”１０”未満である符号はＰ１符号に他ならないので、このＫ値に’１’を加えることで数値に復元できる。
【００８８】
これに対して、Ｋ値が”１０”未満でない場合には（ステップＳ９０２否定）、このＫ値が”１２”であるか否かを判断し（ステップＳ９０４）、”１２”でない場合には（ステップＳ９０４否定）、Ｋ値を４ビット左シフトした値をＷに記憶し、このＫに符号の次の４ビットを入力して、Ｗと新たなＫ値とを加えた値から”１４９”を減じた値を復元数値としてＷに格納した後（ステップＳ９０５）、後述する０値逆変換処理に移行する。
【００８９】
一方、Ｋ値が”１２”である場合には（ステップＳ９０４肯定）、符号が８ビット長を持つＰ２符号に他ならないので、Ｗの値を’０’に初期化した後（ステップＳ９０６）、符号の次の４ビットをＫに入力し（ステップＳ９０７）、ＷにこのＫ値を加算し（ステップＳ９０８）、該Ｋ値が’８’未満であるか否かを判断する（ステップＳ９０９）。
【００９０】
その結果、Ｋ値が’８’未満である場合には（ステップＳ９０９肯定）、以降に数値部の符号が続くので、Ｗの値を３ビット左にシフトした後に（ステップＳ９１０）、上記ステップＳ９０７に移行する。
【００９１】
これに対して、Ｋ値が’８’未満でない場合には（ステップＳ９０９否定）、それまでのＷに”３５”を加算した値をあらためてＷに格納し（ステップＳ９１１）、０値逆変換処理に移行する。Ｐ３符号では、その４ビットとして’８’以上の値が検出されるまで各４ビットの下位３ビットを上位に向かって連接した（つなぎ合わせた）数値に”４３”を加算した値が復元数値に対応する。そして、’８’以上の数値が検出されたときのＫの値には、数値部分の終了を示す’８’が余分に加算されているので、ここでは「４３−８」である”３５”を加算している。
【００９２】
その後、０値変換処理を復元する０値逆変換処理をおこなう。具体的には、復元された数値Ｗが定数Ｚよりも大きな値であるか否かを確認し（ステップＳ９１２）、Ｚよりも大きな値である場合には（ステップＳ９１２肯定）、Ｗから’１’を減じた値をＷに格納して（ステップＳ９１３）数値復元処理を終了する。
【００９３】
これに対して、数値ＷがＺ以下である場合には（ステップＳ９１２否定）、復元された数値Ｗが定数Ｚと一致するか否かを確認し（ステップＳ９１４）、一致する場合には（ステップＳ９１４肯定）、このＷに’０’を代入して（ステップＳ９１５）数値復元処理を終了する。
【００９４】
上述してきたように、本実施の形態では、０ビットの連続数Ｘ、１ビットの連続数Ｙ、Ｘの直前の値Ａ、Ｙの直前の値Ｂに基づいて、状態Ｓ０〜Ｓ３のいずれかの値を状態値をＳとし、このＳの直前の値をＴとし、不一致事象が発生した場合には状態値Ｓの値を示す状態符号Ｑを生成し、符号生成を終了した時点または一致事象が発生した時点において、Ｘ≠Ａである場合にはＸの値を示す数値符号Ｐを生成し、Ｙ≠Ｂである場合にはＹの値を示す数値符号Ｐを生成し、回帰事象が発生した場合には状態符号の生成に先立って反復数Ｎの値を示す数値符号Ｐを生成するよう構成したので、マイクロプロセッサによるソフトウエア処理で、誤差拡散処理により生成された疑似中間調画像データについても効率良く圧縮することができる。
【００９５】
【発明の効果】
以上説明したように、請求項１の発明によれば、入力単位のデータに対応する状態値の算定で、０のビットの連続数Ｘ、１のビットの連続数Ｙ、直前の０のビットの連続数Ａおよび直前の１のビットの連続数Ｂが、Ｘ≠Ａ且つＹ≠Ｂの関係にある場合に状態Ｓ０の値を状態値Ｓとし、Ｘ＝Ａ且つＹ≠Ｂの関係にある場合に状態Ｓ１の値を状態値Ｓとし、Ｘ≠Ａ且つＹ＝Ｂの関係にある場合に状態Ｓ２の値を状態値Ｓとし、Ｘ＝Ａ且つＹ＝Ｂの関係にある場合に状態Ｓ３の値を状態値Ｓとして算定して、直前の状態値Ｔが状態Ｓ３であり、かつ、状態値Ｓと直前の状態値Ｔとが等しい一致事象となった場合にこれを反復事象とみなして、該反復事象が連続して発生する反復数Ｎを算出し、反復事象の発生後に、状態値Ｓと直前の状態値Ｔとが異なる不一致事象または入力完了となった場合に回帰事象と判定し、不一致事象が発生した場合に状態値Ｓの値を示す状態符号を生成し、この状態符号の生成が終了するかまたは一致事象が発生した際に、０のビットの連続数Ｘまたは１のビットの連続数Ｙの値を示す数値符号を生成し、回帰事象が発生した場合に、状態符号の生成に先だって反復数Ｎの値を示す数値符号を生成することとしたので、一致事象、不一致事象、反復事象、回帰事象の概念を利用して、誤差拡散処理により生成された疑似中間調画像データについても効率良くデータを圧縮することが可能なデータ符号化方法が得られるという効果を奏する。
【００９８】
また、請求項２の発明によれば、符号化を開始する際に、Ｔ、Ａ、Ｂおよび反復数Ｎにそれぞれ所定の初期値を格納し、ＸおよびＹにランレングス値を入力し、この入力後に状態値Ｓを生成し、生成された状態値Ｓに対応して一致事象または不一致事象の発生を判定し、一致事象の発生に応答して反復事象の発生の有無を判定し、反復事象の発生に応答して反復数を加算するし、不一致事象の発生または符号化対象データの終了に応答して回帰事象の発生の有無を判定し、回帰事象の発生に応答して反復数Ｎの値を示す反復数数値符号を生成し、反復数数値符号の生成後に反復数Ｎを所定の初期値に戻し、不一致事象の発生または反復数Ｎの初期化に応答して状態値Ｓの値を表現する状態符号を生成し、状態符号の生成または反復事象の発生の判定後に、ＸがＡと一致しない場合に該Ｘに対応する数値符号を生成し、ＹがＢと一致しない場合に該Ｙに対応する数値符号を生成し、数値符号の生成または反復数Ｎの加算後に、Ａの内容をＸに更新し、Ｂの内容をＹに更新し、Ｔの内容をＳに更新するよう構成したので、マイクロプロセッサによるソフトウエア処理に適合したデータの圧縮をおこなうことが可能なデータ符号化方法が得られるという効果を奏する。
【００９９】
また、請求項３の発明によれば、復号化を開始する際に、復元される状態値を記憶する記憶部Ｓ、復元されるランレングス値のうち前記Ｘに相当する値を記憶する記憶部Ｃおよび復元されるランレングス値のうち前記Ｙに相当する値を記憶する記憶部Ｄに所定の初期値を代入して初期化し、所定の符号単位を入力して該符号が数値符号Ｐであるか状態符号Ｑであるかを判定し、数値符号と判定された場合に、該符号を数値に復元して記憶部Ｌに記憶し、状態符号と判定された場合に、該符号を状態値に復元してＳに記憶し、Ｌに復元数値が格納された時点での状態値Ｓの値が、Ｘ≠Ａ且つＹ≠Ｂの関係にある状態Ｓ０、Ｘ＝Ａ且つＹ≠Ｂの関係にある状態Ｓ１、Ｘ≠Ａ且つＹ＝Ｂの関係にある状態Ｓ２若しくはＸ＝Ａ且つＹ＝Ｂの関係にある状態Ｓ３のいずれであるかを識別し、Ｓに新たな状態値が格納された時点で、該Ｓの値がＳ３と一致するか否かを判定し、Ｓの値がＳ０であると識別された場合に、Ｌの値をＣに格納した後に次の数値符号を入力および復元してＤに格納し、Ｓの値がＳ１であると識別された場合に、Ｌの値をＤに格納し、Ｓの値がＳ２であると識別された場合に、Ｌの値をＣに格納し、更新が終了した時点またはＳの値が状態値Ｓ３と一致すると判定された時点で、ＣおよびＤの値を一組のランレングス値として出力し、Ｓ値の値がＳ３であると識別された場合に、ＣおよびＤの値を一組のランレングス値としてＬの値に対応する回数分出力するよう構成したので、誤差拡散処理により生成された疑似中間調画像データを圧縮したものを効率良く復元することが可能なデータ復号化方法が得られるという効果を奏する。
【０１００】
また、請求項４の発明によれば、請求項１〜３のいずれか一つに記載された方法をコンピュータに実行させるプログラムを記録したことで、そのプログラムを機械読み取り可能となり、これによって、請求項１〜３のいずれか一つの動作をコンピュータによって実現することが可能な記録媒体が得られるという効果を奏する。
【図面の簡単な説明】
【図１】この発明の実施の形態に係るデータ符号化方法およびデータ復号化方法の概念を説明するための説明図である。
【図２】本実施の形態で用いる符号化手順を示すフローチャートである。
【図３】図２のステップＳ２０９およびＳ２１９に示す未出力Ｎ符号化手順を示すフローチャートである。
【図４】本実施の形態に係るデータ復号手順を示すフローチャートである。
【図５】図２および図４に示したデータ符号化処理およびデータ復号化処理に用いる符号セットの一例を示す説明図である。
【図６】図５に示した符号セットを用いた場合の状態符号化制御手順を示すフローチャートである。
【図７】図５に示した符号セットを用いた場合の状態復号化制御手順を示すフローチャートである。
【図８】図５に示した符号セットを用いた場合の数値符号化制御手順を示すフローチャートである。
【図９】図５に示した符号セットを用いた場合の数値復号化制御手順を示すフローチャートである。
【符号の説明】
Ｘ    ０の連続数
Ｙ    １の連続数
Ａ    直前のＸ値
Ｂ    直前のＹ値
Ｓ    状態値
Ｔ    直前のＳ値
Ｎ，Ｐ，Ｐ１，Ｐ２，Ｐ３    数値符号
Ｑ、Ｑ１，Ｑ２，Ｑ３    状態符号
【図１】
0003753580.tif 000002
【図２】
0003753580.tif 000003
【図３】
0003753580.tif 000004
【図４】
0003753580.tif 000005
【図５】
0003753580.tif 000006
【図６】
0003753580.tif 000007
【図７】
0003753580.tif 000008
【図８】
0003753580.tif 000009
【図９】
0003753580.tif 000010