(57)【特許請求の範囲】
【請求項１】
入力データストリームを圧縮して符号ストリームを出力するデータ圧縮装置であって、
符号化済みの入力データを格納する移動窓と、
前記移動窓中のある位置（エントリ）からの部分列とこれから符号化するデータ列を比較する比較器と、
前記比較器による比較において、最も長く一致するエントリを見つける一致ファインダと、
前記一致ファインダにおいて、一致が見つけられた場合に、そのエントリまでのオフセットと一致長の組（オフセット、一致長）を符号化する一致符号発生器とを具備し、
前記比較器の数が前記移動窓のサイズより少なく、かつ前記エントリとして、前記オフセットが０の近傍（０は含まない）、前記オフセットがＬ（Ｌは外部から与えられるパラメータ）の近傍、前記オフセットが２Ｌの近傍、前記オフセット３Ｌ…の近傍のうちの一部を使用することを特徴とするデータ圧縮装置。
【請求項２】
入力画像データストリームを圧縮して符号ストリームを出力するデータ圧縮装置であって、
符号化済みの入力画像データを格納する移動窓と、
前記移動窓中のある位置（エントリ）からの部分列とこれから符号化するデータ列を比較する比較器と、
前記比較器による比較において、最も長く一致するエントリを見つける一致ファインダと、
前記一致ファインダにおいて、一致が見つけられた場合に、そのエントリまでのオフセットと一致長の組（オフセット、一致長）を符号化する一致符号発生器とを具備し、
前記比較器の数が前記移動窓のサイズより少なく、かつ前記エントリとして、前記オフセットが０の近傍（０は含まない）、前記オフセットがＬ（Ｌは前記入力画像データのライン長）の近傍、前記オフセットが２Ｌの近傍、前記オフセット３Ｌ…の近傍のうちの一部を使用することを特徴とするデータ圧縮装置。
【請求項３】
入力データストリームを圧縮して符号ストリームを出力するデータ圧縮装置であって、
符号化済みの入力データを格納する移動窓と、
前記移動窓中のある位置（エントリ）からの部分列とこれから符号化するデータ列を比較する比較器と、
前記比較器による比較において、最も長く一致するエントリを見つける一致ファインダと、
前記一致ファインダにおいて、一致が見つけられた場合に、そのエントリまでのオフセットと一致長の組（オフセット、一致長）を符号化する一致符号発生器とを具備し、
前記比較器の数が前記移動窓のサイズより少なく、かつ前記エントリとして、前記オフセットが０の近傍（０は含まない）、前記オフセットがＬ（Ｌは外部から与えられるパラメータ）の近傍、前記オフセットが２Ｌの近傍、前記オフセット３Ｌ…の近傍のうちの一部を使用すると共に、
前記オフセット０の近傍としてオフセットＭ、２Ｍ…（Ｍは外部から与えられるパラメータで、Ｍ＜Ｌ）、前記オフセットＬの近傍としてＬ±Ｍ、Ｌ±２Ｍ…、前記オフセット２Ｌの近傍として２Ｌ±Ｍ、２Ｌ±２Ｍ…を採用することを特徴とするデータ圧縮装置。
【請求項４】
一画素あたりｎ（ｎ：２以上の整数）バイトからなる入力画像データストリームを圧縮して符号ストリームを出力するデータ圧縮装置であって、
符号化済みの入力画像データを格納する移動窓と、
前記移動窓中のある位置（エントリ）からの部分列とこれから符号化するデータ列を比較する比較器と、
前記比較器による比較において、最も長く一致するエントリを見つける一致ファインダと、
前記一致ファインダにおいて、一致が見つけられた場合に、そのエントリまでのオフセットと一致長の組（オフセット、一致長）を符号化する一致符号発生器とを具備し、
前記比較器の数が前記移動窓のサイズより少なく、かつ前記エントリとして、前記オフセットが０の近傍（０は含まない）、前記オフセットがＬ（Ｌは外部から与えられるパラメータ）の近傍、前記オフセットが２Ｌの近傍、前記オフセット３Ｌ…の近傍のうちの一部を使用すると共に、
前記オフセット０の近傍としてオフセットＭ、２Ｍ…（Ｍ＝ｎ、Ｍ＜Ｌ）、前記オフセットＬの近傍としてＬ±Ｍ、Ｌ±２Ｍ…、前記オフセット２Ｌの近傍として２Ｌ±Ｍ、２Ｌ±２Ｍ…を採用することを特徴とするデータ圧縮装置。
【請求項５】
網点画像または集中型ディザ画像で、主走査方向の網点の間隔または集中型ディザの山と山の間隔がｎバイトからなる入力画像データストリームを圧縮して符号ストリームを出力するデータ圧縮装置であって、
符号化済みの入力画像データを格納する移動窓と、
前記移動窓中のある位置（エントリ）からの部分列とこれから符号化するデータ列を比較する比較器と、
前記比較器による比較において、最も長く一致するエントリを見つける一致ファインダと、
前記一致ファインダにおいて、一致が見つけられた場合に、そのエントリまでのオフセットと一致長の組（オフセット、一致長）を符号化する一致符号発生器とを具備し、
前記比較器の数が前記移動窓のサイズより少なく、かつ前記エントリとして、前記オフセットが０の近傍（０は含まない）、前記オフセットがＬ（Ｌは前記入力画像データのライン長）の近傍、前記オフセットが２Ｌの近傍、前記オフセット３Ｌ…の近傍のうちの一部を使用すると共に、
前記オフセット０の近傍としてオフセットＭ、２Ｍ…（Ｍ＝ｎ、Ｍ＜Ｌ）、前記オフセットＬの近傍としてＬ±Ｍ、Ｌ±２Ｍ…、前記オフセット２Ｌの近傍として２Ｌ±Ｍ、２Ｌ±２Ｍ…を採用することを特徴とするデータ圧縮装置。
【請求項６】
一画素あたりｍビット（ｍは８で割り切れない自然数）からなる入力画像データストリームを圧縮して符号ストリームを出力するデータ圧縮装置であって、
符号化済みの入力画像データを格納する移動窓と、
前記移動窓中のある位置（エントリ）からの部分列とこれから符号化するデータ列を比較する比較器と、
前記比較器による比較において、最も長く一致するエントリを見つける一致ファインダと、
前記一致ファインダにおいて、一致が見つけられた場合に、そのエントリまでのオフセットと一致長の組（オフセット、一致長）を符号化する一致符号発生器とを具備し、
前記比較器の数が前記移動窓のサイズより少なく、かつ前記エントリとして、前記オフセットが０の近傍（０は含まない）、前記オフセットがＬ（Ｌは外部から与えられるパラメータ）の近傍、前記オフセットが２Ｌの近傍、前記オフセット３Ｌ…の近傍のうちの一部を使用すると共に、
前記オフセット０の近傍としてオフセットＭ、２Ｍ…（Ｍ＝ｍと８の最小公倍数、Ｍ＜Ｌ）、前記オフセットＬの近傍としてＬ±Ｍ、Ｌ±２Ｍ…、前記オフセット２Ｌの近傍として２Ｌ±Ｍ、２Ｌ±２Ｍ…を採用することを特徴とするデータ圧縮装置。
【請求項７】
網点画像または集中型ディザ画像で、主走査方向の網点の間隔または集中型ディザの山と山の間隔がｍビット（ｍは８で割り切れない自然数）からなる入力画像データストリームを圧縮して符号ストリームを出力するデータ圧縮装置であって、
符号化済みの入力画像データを格納する移動窓と、
前記移動窓中のある位置（エントリ）からの部分列とこれから符号化するデータ列を比較する比較器と、
前記比較器による比較において、最も長く一致するエントリを見つける一致ファインダと、
前記一致ファインダにおいて、一致が見つけられた場合に、そのエントリまでのオフセットと一致長の組（オフセット、一致長）を符号化する一致符号発生器とを具備し、
前記比較器の数が前記移動窓のサイズより少なく、かつ前記エントリとして、前記オフセットが０の近傍（０は含まない）、前記オフセットがＬ（Ｌは前記入力画像データのライン長）の近傍、前記オフセットが２Ｌの近傍、前記オフセット３Ｌ…の近傍のうちの一部を使用すると共に、
前記オフセット０の近傍としてオフセットＭ、２Ｍ…（Ｍ＝ｍと８の最小公倍数、Ｍ＜Ｌ）、前記オフセットＬの近傍としてＬ±Ｍ、Ｌ±２Ｍ…、前記オフセット２Ｌの近傍として２Ｌ±Ｍ、２Ｌ±２Ｍ…を採用することを特徴とするデータ圧縮装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に、データ圧縮装置に関するものであり、具体的には、ＬＺ７７およびＬＺ７８に代表される辞書べ−ス方式を基にしたデータ圧縮技術を用いて、特に画像データを効率的に圧縮するデ−タ圧縮装置に関する。
【０００２】
【従来の技術】
現在の辞書ベースによりデータ圧縮をするデータ圧縮方法の起源は、Abraham Lempel氏とJacob Ziv 氏とが１９７７年にIEEE Transaction on Information Theoryに発表した論文｀AUniversal Algorithm for Sequential Data Compression´に見られる。
【０００３】
これは、通称Lempel-Ziv符号化のスライド辞書法又はＬＺ７７法と言われている。
【０００４】
例えば、宗像清治：Ziv-Lempelのデ一タ圧縮法，情報処理，Ｖｏｌ．２６．Ｎｏ．１  （１９８５）に、それが紹介されている。
【０００５】
ＬＺ７７のアルゴリズムは、符号化データを過去のデータ系列の任意の位置から一致する最大長の系列に区切り、過去の系列の複製として符号化する方法である。
【０００６】
具体的には、図３に示すように、符号化済みの入力データを格納する移動窓と、これから符号化するデータを格納する先読みバッファとを備え、先読みバッファのデータ系列と移動窓のデータ系列のすべての部分系列とを照合して、移動窓中で一致する最大長の部分系列を求める。
【０００７】
そして、移動窓中でこの最大長の部分系列を指定するために、「その最大長の部分系列の開始位置」と「一致する長さ」と「不一致をもたらした次のシンボル」との組を符号化する。
【０００８】
次に、先読みバッファ内の符号化したデータ系列を移動窓に移して、先読みバッファ内に符号化したデータ系列分の新たなデータ系列を入力する。
【０００９】
以下、同様の処理を繰り返していくことで、データを部分系列に分解して符号化を実行していくのである。
【００１０】
そして、このような基本的なデータ圧縮技術に対して、多くの改良型が提案されている。
【００１１】
例えば、符号化コードであるのか、生データであるのかを識別するフラグを設けて、符号化コードが生データよりも長くなってしまうときには生データを符号化するという方法をとるＬＺＳＳ符号方式(T.C.Bell,“Better OPM/L Text Compression",IEEE Transaction Commun.,Vol.COM-34,No.12,Dec.(1986)) がある。
【００１２】
また、他の文献としては、Ｍ．ネルソン：データ圧縮ハンドブック改訂第２版、トッパン(1996). ISBN4-8101-8605-9 がある。
【００１３】
ところで、近年、ＯＡシステム（スキャナ、プリンタ、ディジタル複写機など）が普及し、高速化・高解像度化の方向を目指している。
【００１４】
これらの装置では、大容量の画像データを高速で処理する必要があり、高速・高圧縮率のデータ圧縮を加えることで、処理するデータ量を滅らすことが必須となっている。
【００１５】
このようなデータ圧縮の従来技術としては、ＭＭＲ、ＪＢＩＧなど標準化された方式があるが、ＭＭＲは精細な画像で圧縮率が悪化する傾向にある。
【００１６】
また、圧縮率の点ではべストに近いＪＢＩＧは基本的に画素単位の処理であるため高速化に限界があり、高速システムでは採用できなかった。
【００１７】
しかるに、上述した辞書ベース圧縮方式は、基本的にバイト単位の処理であるためＪＢＩＧよりはるかに高速化が可能であり、また精細な画像に対してもＭＭＲほど圧縮率が悪化しないという特徴があり、高速・高解像度のＯＡシステムに適している。
【００１８】
【発明が解決しようとする課題】
しかしながら、従来のＬＺ７７ベースによるデータ圧縮装置では、符号化する際、移動窓中で一致する最大長の部分データ列を求めるためには、これから符号化するデータ列と移動窓の中のすべての位置の間でデータ列比較を行わなければならない。
【００１９】
すなわち、図３に示すように、これから符号化するデータ列を、移動窓中のオフセット１の位置から始まるデ−タ列、オフセット２の位置から始まるデ−タ列、…オフセットｎ（ｎは移動窓のサイズ）の位置から始まるデ−タ列と比較して、最大一致長が得られるオフセットを見つけることである。
【００２０】
これをハ−ドウェアで高速に実現しようとするものが、米国特許第５，００３，３０７により提案されている。
【００２１】
これは、図４に示すように、移動窓のサイズをｎとして、移動窓をｎ個のシフトレジスタＳＲ１〜ｎで実現すると共に、ｎ個の比較器ＣＭＰ１〜ｎを以ってｎ通りの比較を並列に処理しようとするものである。
【００２２】
この方式は１クロックで１つのデータを処理することができる優れたものであるが、移動窓サイズと同数の比較器を並べる必要があり、移動窓のサイズが大きくなると実現が困難である。
【００２３】
例えば、移動窓のサイズを２ｋＢとすると、この従来例では２ｋ個の比較器が必要になる。
【００２４】
本発明は、上述した事情に鑑みなされたもので、データ処理装置及びデータ処理方法において、辞書データと入力データとを比較して一致するデータを符号化すると共に、符号化された圧縮データを復号化する装置及び方法の改善に関するものであり、特に、画像データの周期性に着目して少ない比較器でＬＺ７７ベースのデータ圧縮装置を提供することを目的としている。
【００２５】
【課題を解決するための手段】
本発明によると、上記課題を解決するために、入力データストリームを圧縮して符号ストリームを出力するデータ圧縮装置であって、符号化済みの入力データを格納する移動窓と、前記移動窓中のある位置（エントリ）からの部分列とこれから符号化するデータ列を比較する比較器と、前記比較器による比較において、最も長く一致するエントリを見つける一致ファインダと、前記一致ファインダにおいて、一致が見つけられた場合に、そのエントリまでのオフセットと一致長の組（オフセット、一致長）を符号化する一致符号発生器とを具備し、前記比較器の数が前記移動窓のサイズより少なく、かつ前記エントリとして、前記オフセットが０の近傍（０は含まない）、前記オフセットがＬ（Ｌは外部から与えられるパラメータ）の近傍、前記オフセットが２Ｌの近傍、前記オフセット３Ｌ…の近傍のうちの一部を使用することを特徴とするデータ圧縮装置が提供される。
【００２６】
また、本発明によると、上記課題を解決するために、入力画像データストリームを圧縮して符号ストリームを出力するデータ圧縮装置であって、符号化済みの入力画像データを格納する移動窓と、前記移動窓中のある位置（エントリ）からの部分列とこれから符号化するデータ列を比較する比較器と、前記比較器による比較において、最も長く一致するエントリを見つける一致ファインダと、前記一致ファインダにおいて、一致が見つけられた場合に、そのエントリまでのオフセットと一致長の組（オフセット、一致長）を符号化する一致符号発生器とを具備し、前記比較器の数が前記移動窓のサイズより少なく、かつ前記エントリとして、前記オフセットが０の近傍（０は含まない）、前記オフセットがＬ  （Ｌは前記入力画像データのライン長）の近傍、前記オフセットが２Ｌの近傍、前記オフセット３Ｌ…の近傍のうちの一部を使用することを特徴とするデータ圧縮装置が提供される。
【００２７】
また、本発明によると、上記課題を解決するために、入力データストリームを圧縮して符号ストリームを出力するデータ圧縮装置であって、符号化済みの入力データを格納する移動窓と、前記移動窓中のある位置（エントリ）からの部分列とこれから符号化するデータ列を比較する比較器と、前記比較器による比較において、最も長く一致するエントリを見つける一致ファインダと、前記一致ファインダにおいて、一致が見つけられた場合に、そのエントリまでのオフセットと一致長の組（オフセット、一致長）を符号化する一致符号発生器とを具備し、前記比較器の数が前記移動窓のサイズより少なく、かつ前記エントリとして、前記オフセットが０の近傍（０は含まない）、前記オフセットがＬ（Ｌは外部から与えられるパラメータ）の近傍、前記オフセットが２Ｌの近傍、前記オフセット３Ｌ…の近傍のうちの一部を使用すると共に、前記オフセット０の近傍としてオフセットＭ、２Ｍ…（Ｍは外部から与えられるパラメータで、Ｍ＜Ｌ）、前記オフセットＬの近傍としてＬ±Ｍ、Ｌ±２Ｍ…、前記オフセット２Ｌの近傍として２Ｌ±Ｍ、２Ｌ±２Ｍ…を採用することを特徴とするデータ圧縮装置が提供される。
【００２８】
また、本発明によると、上記課題を解決するために、一画素あたりｎ（ｎ：２以上の整数）バイトからなる入力画像データストリームを圧縮して符号ストリームを出力するデータ圧縮装置であって、符号化済みの入力画像データを格納する移動窓と、前記移動窓中のある位置（エントリ）からの部分列とこれから符号化するデータ列を比較する比較器と、前記比較器による比較において、最も長く一致するエントリを見つける一致ファインダと、前記一致ファインダにおいて、一致が見つけられた場合に、そのエントリまでのオフセットと一致長の組（オフセット、一致長）を符号化する一致符号発生器とを具備し、前記比較器の数が前記移動窓のサイズより少なく、かつ前記エントリとして、前記オフセットが０の近傍（０は含まない）、前記オフセットがＬ（Ｌは外部から与えられるパラメータ）の近傍、前記オフセットが２Ｌの近傍、前記オフセット３Ｌ…の近傍のうちの一部を使用すると共に、前記オフセット０の近傍としてオフセットＭ、２Ｍ…（Ｍ＝ｎ、Ｍ＜Ｌ）、前記オフセットＬの近傍としてＬ±Ｍ、Ｌ±２Ｍ…、前記オフセット２Ｌの近傍として２Ｌ±Ｍ、２Ｌ±２Ｍ…を採用することを特徴とするデータ圧縮装置が提供される。
【００２９】
また、本発明によると、上記課題を解決するために、網点画像または集中型ディザ画像で、主走査方向の網点の間隔または集中型ディザの山と山の間隔がｎバイトからなる入力画像データストリームを圧縮して符号ストリームを出力するデータ圧縮装置であって、符号化済みの入力画像データを格納する移動窓と、
前記移動窓中のある位置（エントリ）からの部分列とこれから符号化するデータ列を比較する比較器と、前記比較器による比較において、最も長く一致するエントリを見つける一致ファインダと、前記一致ファインダにおいて、一致が見つけられた場合に、そのエントリまでのオフセットと一致長の組（オフセット、一致長）を符号化する一致符号発生器とを具備し、前記比較器の数が前記移動窓のサイズより少なく、かつ前記エントリとして、前記オフセットが０の近傍（０は含まない）、前記オフセットがＬ（Ｌは前記入力画像データのライン長）の近傍、前記オフセットが２Ｌの近傍、前記オフセット３Ｌ…の近傍のうちの一部を使用すると共に、前記オフセット０の近傍としてオフセットＭ、２Ｍ…（Ｍ＝ｎ、Ｍ＜Ｌ）、前記オフセットＬの近傍としてＬ±Ｍ、Ｌ±２Ｍ…、前記オフセット２Ｌの近傍として２Ｌ±Ｍ、２Ｌ±２Ｍ…を採用することを特徴とするデータ圧縮装置が提供される。
【００３０】
また、本発明によると、上記課題を解決するために、一画素あたりｍビット（ｍは８で割り切れない自然数）からなる入力画像データストリームを圧縮して符号ストリームを出力するデータ圧縮装置であって、符号化済みの入力画像データを格納する移動窓と、前記移動窓中のある位置（エントリ）からの部分列とこれから符号化するデータ列を比較する比較器と、前記比較器による比較において、最も長く一致するエントリを見つける一致ファインダと、前記一致ファインダにおいて、一致が見つけられた場合に、そのエントリまでのオフセットと一致長の組（オフセット、一致長）を符号化する一致符号発生器とを具備し、前記比較器の数が前記移動窓のサイズより少なく、かつ前記エントリとして、前記オフセットが０の近傍（０は含まない）、前記オフセットがＬ（Ｌは外部から与えられるパラメータ）の近傍、前記オフセットが２Ｌの近傍、前記オフセット３Ｌ…の近傍のうちの一部を使用すると共に、前記オフセット０の近傍としてオフセットＭ、２Ｍ…（Ｍ＝ｍと８の最小公倍数、Ｍ＜Ｌ）、前記オフセットＬの近傍としてＬ±Ｍ、Ｌ±２Ｍ…、前記オフセット２Ｌの近傍として２Ｌ±Ｍ、２Ｌ±２Ｍ…を採用することを特徴とするデータ圧縮装置が提供される。
【００３１】
また、本発明によると、上記課題を解決するために、網点画像または集中型ディザ画像で、主走査方向の網点の間隔または集中型ディザの山と山の間隔がｍビット（ｍは８で割り切れない自然数）からなる入力画像データストリームを圧縮して符号ストリームを出力するデータ圧縮装置であって、符号化済みの入力画像データを格納する移動窓と、前記移動窓中のある位置（エントリ）からの部分列とこれから符号化するデータ列を比較する比較器と、前記比較器による比較において、最も長く一致するエントリを見つける一致ファインダと、前記一致ファインダにおいて、一致が見つけられた場合に、そのエントリまでのオフセットと一致長の組（オフセット、一致長）を符号化する一致符号発生器とを具備し、前記比較器の数が前記移動窓のサイズより少なく、かつ前記エントリとして、前記オフセットが０の近傍（０は含まない）、前記オフセットがＬ（Ｌは前記入力画像データのライン長）の近傍、前記オフセットが２Ｌの近傍、前記オフセット３Ｌ…の近傍のうちの一部を使用すると共に、前記オフセット０の近傍としてオフセットＭ、２Ｍ…（Ｍ＝ｍと８の最小公倍数、Ｍ＜Ｌ）、前記オフセットＬの近傍としてＬ±Ｍ、Ｌ±２Ｍ…、前記オフセット２Ｌの近傍として２Ｌ±Ｍ、２Ｌ±２Ｍ…を採用することを特徴とするデータ圧縮装置が提供される。
【００３２】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照して説明する。
【００３３】
従来技術の項で述べたように、ＬＺ７７ベースのデータ圧縮装置をハードウェアで高速に実現しようとするものが、米国特許第５，００３，３０７に提案されている。
【００３４】
これは、移動窓のサイズをｎとして、移動窓をｎ個のシフトレジスタで実現し、ｎ個の比較器を以ってｎ通りの比較を並列に処理しようとするものである。
【００３５】
この方式は１クロックで１つのデータを処理できる優れたものであるが、移動窓サイズと同数の比較器を並べる必要があり、移動窓のサイズが大き＜なると実現が困難である。
【００３６】
そこで、本発明の第１の実施の形態では、ＬＺ７７をベースとしながらも、これから符号化するデータ列を移動窓中のすべての位置から始まるデータ列と比較するのでなく、一致する可能性の高い位置から始まるデータ列だけを比較対象とすることで、ハードウエア化を容易にしている。
【００３７】
例えば、比較対象位置として１６あるいは３２程度とすれば、同数の比較器で並列に比較処理を行うことは十分に可能である。
【００３８】
しかしながら、単純に比較対象位置の数を減らしただけでは、一致する可能性が小さくなり圧縮率が低下すると考えられる。
【００３９】
このため、第１の実施の形態では、画像データの周期性に着目して比較対象する位置を選択している。
【００４０】
すなわち、移動窓中のすべての部分列を比較するのでなく、画像データの周期性に着目して、一致する可能性の高いデータ位置だけを比較する。
【００４１】
以下、図１を基づいてこの発明の第１の実施の形態の原理を説明する。
【００４２】
ここでは、データの単位をバイトとしている。
【００４３】
画像データの２次元的な局所性を考慮すると、これから符号化しようとするあるバイトと最も類似性が高いのは、そのバイトの上下左右の位置にあるバイトである。
【００４４】
画像データの入力順として一般的な左上から右下へのラスタスキャンを考えると、これから符号化しようとするあるバイトに対して、右と下の隣接バイトはこれから入力されるものであるため移動窓にはまだ入っていない。
【００４５】
したがって、これから符号化しようとするあるバイトに対して、右と下の隣接バイトを比較対象とすることはできない。
【００４６】
そして、これから符号化しようとするあるバイトに対して、左の隣接バイトは入力順でーつ前に入力された最近のデータであり、移動窓中でオフセット１の位置に入っている。
【００４７】
また、上の隣接バイトは、入力画像データのライン長（横幅）がバイト数でＬとすると、移動窓中のオフセットＬの位置に入っている。
【００４８】
ただし、この場合、移動窓のサイズがＬ以上であることが条件である。
【００４９】
従来のＬＺ系コ−デックは、入力が画像デ−タであっても、その周期性を無視して、これから符号化しようとするあるバイトに対して、左方向だけで一致するポイントを探していたことになる。
【００５０】
ここでは、これから符号化しようとするあるバイトに対して、左方向に加えて上方向に隣接する位置とその周辺とを比較ポイントに選んでいる。
【００５１】
このため、移動窓中には、両端の比較ポイントとするバイト（図中、黒四角で示すバイト）部分の間に比較ポイントとしないバイト（図中、白四角で示すバイト）の部分が入っている。
【００５２】
そして、これから符号化しようとするデ−タ列部分（図中、菱形及び＝＝＝＝…で示すバイト）において、菱形で示すバイトがその先頭バイトである。
【００５３】
このようにして、比較対象位置を少なくすることは、オフセット符号を短くすることができる点で優れている。
【００５４】
例えば、移動窓のサイズを２ｋＢとすると、従来例ではオフセットとして２ｋ通りの符号が必要になるが、図１の例ではオフセットとして１６通りしか必要ないので、単純な符号を選んだ場合、従来技術では１１ビットのオフセット符号長になるのに対して、本発明ではオフセット符号長が４ビットと短い。
【００５５】
図２に、本発明の第１の実施の形態による構成図を示す。
【００５６】
第１の実施の形態では、図示しないラインメモリ、メモリ制御部に加えて、例えば、圧縮対象としての画像データの１ライン長をＬとしたとき、移動窓を与える（Ｌ＋５）ＢのシフトレジスタＳＲ、１６個の比較器ＣＭＰ１〜１６、一致位置検出回路（最長判定部）ＤＥＴから構成されている。
【００５７】
本実施の形態は、図１に示す比較対象位置（オフセット、１、２、…５、Ｌ−５、Ｌ−４、…Ｌ−１、Ｌ、Ｌ＋１、…Ｌ＋５）を実装化したものである。
【００５８】
ラインメモリは、入力データのライン長をＬバイトとしてＬ−６分のサイズを持つラインバッファでよい。。
【００５９】
これから符号化するデータ列（現ラインデータ）をこのラインバッファに格納しながら、１ライン前のデータ（前ラインデータ）を図示しない前処理部を介して本実施の形態による符号器に以下に示すような形態で送る。
【００６０】
これと並行して、現ラインデータそのものを図示しない前処理部を介して本実施の形態による符号器に以下に示すような形態でに送る。
【００６１】
本実施の形態による符号器では、前処理部から前ラインデータを５段のシフトレジスタＳＲに入力し、それぞれの段の出力をオフセット１〜５の比較対象位置データとする。
【００６２】
一方、前処理部からオフセットＬ−６にあたる前ラインデータは１１段のシフトレジスタＳＲに入力され、それぞれの段の出力をオフセットＬ−５〜Ｌ＋５の比較対象位置データとする。
【００６３】
これにより合計で１６個所の比較対象位置データは、１６個の比較器ＣＭＰ１〜１６の各一端に入力され、このすベての比較器ＣＭＰ１〜１６の各他端に共通に入力されるこれから符号化しようとするデータ列の先頭バイト（図１の菱形で示すバイト）と比較される。
【００６４】
図５は、比較器ＣＭＰ１〜１６が比較するオフセットを示している。
【００６５】
次に、比較器ＣＭＰ１〜１６及び一致位置検出回路（最長判定部）ＤＥＴの動作を説明する。
【００６６】
各比較器ＣＭＰ１〜１６は、一致継続／一致終了のフラグを持ち、始めは一致継続にプリセットされているクロックごとに比較を行い、不一致があればフラグを一致終了にして次にプリセットされるまで待つ。
【００６７】
初めに、各比較器ＣＭＰ１〜１６のフラグをプリセットすると共に、一致位置検出回路（最長判定部）ＤＥＴ内の一致長カウンタも０に初期化する。
【００６８】
以下、クロックごとに次のように動作する．
一致長カウンタ０ですべてのフラグが一致終了となったら（これは符号化位置（図１の菱形で示すバイト）が比較対象位置（図中、黒四角で示すバイト）のどれともー致しなかったことを示す）、一致位置検出回路（最長判定部）ＤＥＴ内のリテラルコード発生器に符号化位置データを送り、リテラルコードの発生を指示する。
【００６９】
少なくとも一つの比較器が一致継続している間は、クロックごとに一致長カウンタをカウントアップする。
【００７０】
少なくともーつの比鮫器が一致継続しているかどうかの判定は、一致位置検出回路（最長判定部）ＤＥＴ内のＯＲ回路で行うようにしてやればよい。
【００７１】
一致位置検出回路（最長判定部）ＤＥＴは、一致長カウンタ１以上で一致終了したら、一致コ−ドを発生する。
【００７２】
このとき、一致長カウンタは、一致継続している比較器番号と一致長とを一致位置検出回路（最長判定部）ＤＥＴ内の一致コ−ド発生器に送る。
【００７３】
複数の比較器で一致継続していたものが同時に終了となったときは、比較器１に近いほうを採用する。
【００７４】
これは一致位置検出回路（最長判定部）ＤＥＴ内のプライオリティエンコ−ダを使用することで実現できる。
【００７５】
一致位置検出回路（最長判定部）ＤＥＴが、リテラルコードまたは一致コード発生を指示したときは、符号器は各比較器ＣＭＰ１〜１６のフラグをプリセットし、一致長カウンタも０に初期化して上述した初めの動作から続ける。
【００７６】
リテラルコード発生器では、これから符号化する先頭バイトにリテラルコードマーカを付けて出力する。
【００７７】
一致コード発生器では、比較器番号、一致長を入力し、符号表にしたがってオフセットコードと一致長コードからなる一致コードを出力すると共に、これとあわせて一致コードの長さ（オフセットコードの長さ＋一致長コードの長さ）を出力する。
【００７８】
これはＲＯＭとして、オフセットコード、オフセットコードの長さ、一致長コード、一致長コードの長さを、一致位置検出回路（最長判定部）ＤＥＴ内の一致コ−ド発生器に用意しておけばよい。
【００７９】
パケットパッキングでは、リテラルコード発生器または一致コード発生器からコードとコードの長さを入力し、パッキングする。
【００８０】
なお、本実施の形態は、比較対象位置として、図１に示す比較対象位置（オフセット、１、２、…５、Ｌ−５、Ｌ−４、…Ｌ−１、Ｌ、Ｌ＋１、…Ｌ＋５）以外に、図６、図７、図８及び図９に示すような種々の形態を取ることが可能である。
【００８１】
次に、この発明の第２の実施の形態を説明する。
【００８２】
この第２の実施の形態では、２バイト置きの比較ポイント選択を行うもので、入力画像データが、１画素を２バイトで表す多値データとする。
【００８３】
この２バイトのうち、第１バイトは輝度情報を、第２バイトは色差情報を表している。
【００８４】
このような場合、図１０に示すように、あるバイトと他のバイトを比較したとき、輝度バイトと色差バイトは一致する可能性が低く、輝度バイ卜と輝度バイトあるいは色差バイトと色差バイトは一致しやすいと考えられる。
【００８５】
すなわち、このような場合には、移動窓中で奇数だけ離れたポイントを比較ポイントとして選んでも有効ではないことになる。
【００８６】
そこで、このような場合には、比較ポイントの間隔を、前述した第１の実施の形態のように１バイトとする代わりに２バイト置きとすることで、より有効な圧縮化が可能となる。
【００８７】
この場合、比較対象位置は図１２の（ａ），（ｂ）に示すようになる。
【００８８】
図１１に、本発明の第２の実施の形態による構成図を示す。
【００８９】
第２の実施の形態では、図示しないラインメモリ、メモリ制御部に加えて、例えば、圧縮対象としての画像データの１ライン長をＬとしたとき、移動窓を与える（Ｌ＋１０）ＢのシフトレジスタＳＲ、１６個の比較器ＣＭＰ１〜１６、一致位置検出回路（最長判定部）ＤＥＴから構成されている。
【００９０】
本実施の形態は、図１２の（ａ）に示す比較対象位置（オフセット、２、４、…１０、Ｌ−１０、Ｌ−８、…Ｌ−２、Ｌ、Ｌ＋２、…Ｌ＋１０）を実装化したものである。
【００９１】
ラインメモリは、入力データのライン長をＬバイトとしてＬ−１１分のサイズを持つラインバッファでよい。
【００９２】
これから符号化するデータ列（現ラインデータ）をこのラインバッファに格納しながら、１ライン前のデータ（前ラインデータ）を図示しない前処理部を介して本実施の形態による符号器に以下に示すような形態で送る。
【００９３】
これと並行して、現ラインデータそのものを図示しない前処理部を介して本実施の形態による符号器に以下に示すような形態でに送る。
【００９４】
本実施の形態による符号器では、前処理部から前ラインデータを１０段のシフトレジスタＳＲの一つ置きごとに入力し、それぞれの段の出力をオフセット２，４，６，８，１０の比較対象位置データとする。
【００９５】
一方、前処理部からオフセットＬ−１１にあたる前ラインデータは２１段のシフトレジスタＳＲ一つ置きごとに入力され、それぞれの段の出力をオフセットＬ−１０，Ｌ−８，〜Ｌ−２，Ｌ，Ｌ＋２〜Ｌ＋８，Ｌ＋１０の比較対象位置データとする。
【００９６】
これにより合計で１６個所の比較対象位置データは、１６個の比較器ＣＭＰ１〜１６の各一端に入力され、このすベての比較器ＣＭＰ１〜１６の各他端に共通に入力されるこれから符号化しようとするデータ列の先頭バイト（図１０の菱形で示すバイト）と比較される。
【００９７】
なお、比較器ＣＭＰ１〜１６が比較するオフセットは、前述した図５に示されている。
【００９８】
他の構成及びその動作は、前述した第１の実施の形態と同様である。
【００９９】
次に、以上のような本発明における各実施の形態の要約を示す。
【０１００】
（第１の実施の形態）
第１の実施の形態による符号器本体は、ｎラインバッファを持ち、現ラインの周辺位置、前ラインの周辺位置、前々ラインの周辺位置…をエントリとすると共に、一つ前、前ライン同位置、前々ライン同位置…に優先的に短いオフセット符号を割当てる。
【０１０１】
すなわち、従来のＬＺ７７ベースのデータ圧縮装置では、移動窓中で一致する最大長の部分系列を求めるために多くの比較器が必要であったのに対して、本発明の第１の実施の形態では、画像データの周期性に注目し、これから符号化するデータは前ラインの同じ位置あるいはその近傍の位置、または前々ラインの同じ位置あるいはその近傍の位置、または前々々ラインの同じ位置あるいはその近傍の位置…と一致する可能性が高いことから、移動窓中のすべてのエントリを比較対象とするのでなく、一致する可能性が高いオフセット０の近傍（０は含まない）、オフセットＬ（Ｌは画像のライン長で圧縮装置に外部から与えられる）の近傍、オフセット２Ｌの近傍、オフセット３Ｌの近傍…のうちの一部をエントリとして用いることで、少ない比較器で高い圧縮率を得ることができる。
【０１０２】
（第２の実施の形態）
第２の実施の形態による符号器本体は、第１の実施の形態による符号器本体において、ｎバイトブロックのときｎバイト置きのエントリとするもので、特に、網点画像のとき、網点の山の間隔×n(n=1,2…) だけ離れた位置をエントリとすると共に、ブロック長÷バイトで余りがでるとき、最小公倍数置きにエントリとする。
【０１０３】
また、山の間隔がバイトの整数倍でないときは最小公倍数×ｎの位置をエントリとする。
【０１０４】
ところで、上述した第１の実施の形態で、画像データが１画素２バイトからなる画像である場合、これから符号化するデータはオフセット２、４、…のエントリと一致する可能性が高く、オフセット１、３、…のエントリと一致する可能性は低く、前ライン、前々ラインについても同様に、オフセットＬ±２、Ｌ±４、…のエントリと一致する可能性が高く、オフセットＬ±１、Ｌ±３、…のエントリと一致する可能性は低いと考えられる。
【０１０５】
したがって、この第２の実施の形態で、オフセット０の近傍としてオフセットＭ、２Ｍ…（Ｍは１画素のバイト長）、オフセットＬの近傍としてＬ±Ｍ、Ｌ±２Ｍ…、オフセット２Ｌの近傍として２Ｌ±Ｍ、２Ｌ±２Ｍ…をエントリとして用いることで、少ない比較器で高い圧縮率を得ることができる。
【０１０６】
そして、１画素２バイトとなる場合だけでなく、画像データが網点画像または集中型ディザ画像で、主走査方向の網点の間隔または集中型ディザの山と山の間隔が例えば２バイトであるようなときもこれから符号化するデータは主走査方向の網点の間隔または集中型ディザの山と山の間隔分だけ離れたエントリと一致する可能性が高いので、オフセット０の近傍としてオフセットＭ、２Ｍ…（Ｍは１主走査方向の網点の間隔または集中型ディザの山と山の間隔のバイト長）、オフセットＬの近傍としてＬ±Ｍ．Ｌ±２Ｍ…、オフセット２Ｌの近傍として２Ｌ±Ｍ、２Ｌ±２Ｍ…をエントリとして用いることで、少ない比較器で高い圧縮率を得ることができる。
【０１０７】
また、１画素のバイト長や主走査方向の網点の間隔または集中型ディザの山と山の間隔のバイト長が１バイトの整数倍でない場合は、１画素のビット長や主走査方向の網点の間隔または集中型ディザの山と山の間隔のビット長をｍとしたとき、ｍと８の最小公倍数をＭとすると、これから符号化するデータはＭ、２Ｍ、…だけ離れたエントリと一致する可能性が高い。
【０１０８】
そこで、このような場合には、オフセット０の近傍としてオフセットＭ、２Ｍ…（Ｍは上記ｍと８の最小公倍数）、オフセットＬの近傍としてＬ±Ｍ、Ｌ±２Ｍ…、オフセット２Ｌの近傍として２Ｌ±Ｍ、２Ｌ±２Ｍ…をエントリとして用いることで、少ない比較器で高い圧縮率を得ることができる。
【０１０９】
【発明の効果】
以上詳述したように、本発明によれば、データ処理装置及びデータ処理方法において、辞書データと入力データとを比較して一致するデータを符号化すると共に、符号化された圧縮データを復号化する装置及び方法の改善に関するものであり、特に、画像データの周期性に着目して少ない比較器でＬＺ７７ベースのデータ圧縮装置を提供することができる。
【図面の簡単な説明】
【図１】  図１はこの発明による第１の実施の形態の原理を説明するための図。
【図２】  図２はこの発明による第１の実施の形態の構成を説明するための図。
【図３】  図３は従来のＬＺ７７圧縮装置の原理を説明するための図。
【図４】  図４は従来のＬＺ７７圧縮装置の構成を説明するための図。
【図５】  図５はこの発明における比較器ＣＭＰ１〜１６が比較するオフセットを説明するための図。
【図６】  図６はこの発明による第１の実施の形態における他の比較対象位置の選択例を説明するための図。
【図７】  図７はこの発明による第１の実施の形態における他の比較対象位置の選択例を説明するための図。
【図８】  図８はこの発明による第１の実施の形態における他の比較対象位置の選択例を説明するための図。
【図９】  図９はこの発明による第１の実施の形態における他の比較対象位置の選択例を説明するための図。
【図１０】  図１０はこの発明による第２の実施の形態の原理を説明するための図。
【図１１】  図１１はこの発明による第２の実施の形態の構成を説明するための図。
【図１２】  図１２はこの発明による第２の実施の形態の比較対象位置の選択例を説明するための図。
【符号の説明】
ＳＲ…シフトレジスタＳＲ、
ＣＭＰ１〜１６…比較器、
ＤＥＴ…一致位置検出回路（最長判定部）ＤＥＴ。
【図１】
0003730385.tif 000002
【図２】
0003730385.tif 000003
【図３】
0003730385.tif 000004
【図４】
0003730385.tif 000005
【図５】
0003730385.tif 000006
【図６】
0003730385.tif 000007
【図７】
0003730385.tif 000008
【図８】
0003730385.tif 000009
【図９】
0003730385.tif 000010
【図１０】
0003730385.tif 000011
【図１１】
0003730385.tif 000012
【図１２】
0003730385.tif 000013