(57)【特許請求の範囲】
【請求項１】
画像データを圧縮する方法であって、２値画像データの内、複数ビット列にわたる反復パターンが含まれている行を抽出する抽出ステップと、複数ビット列にわたる該反復パターンの単位パターンと、該単位パターンの繰り返し回数を検出する反復パターン検出ステップと、少なくとも、該単位パターンのデータと、反復パターン内における該単位パターンの繰り返し回数とを使って、画像データ内の複数ビット列にわたる反復パターンを含む行を符号化する符号化ステップと、を備えることを特徴とする画像圧縮方法。
【請求項２】
前記単位パターンの画素幅が予め定められた１以上の固定値であることを特徴とする請求項１に記載の画像圧縮方法。
【請求項３】
前記符号化ステップにおいては、単位パターンを更にデータ圧縮し、該圧縮された単位パターンと該単位パターンの繰り返し回数により符号化することを特徴とする請求項１に記載の画像圧縮方法。
【請求項４】
前記単位パターンの圧縮は、ランレングス符号化方法を使用することを特徴とする請求項３に記載の画像圧縮方法。
【請求項５】
前記符号化ステップにおいて、出現した単位パターンを登録するテーブルを生成し、該単位パターンと同じ単位パターンが符号化の過程で２回以上出てくる場合には、該単位パターンの代わりに該テーブルにおける該単位パターンの登録番号を用いて、画像データを符号化することを特徴とする請求項１に記載の画像圧縮方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、２値のビットマップ画像の圧縮率を向上させる圧縮方法に関する。
【０００２】
【従来の技術】
近年、パソコンなどの情報機器が普及し、様々な用途に使用されている。特に、パソコンで画像を処理する場合が多く見られ、パソコンにプリンタを接続し、画像を印刷したり、インターネットなどのネットワークを介して画像データを転送するなどの処理が行われている。しかし、画像が複雑になればなるほど、パソコンからプリンタへの画像データの転送や、ネットワークを介しての画像データの転送に時間がかかり過ぎるようになり、画像データを圧縮して転送することが望まれる。画像データを圧縮することによって、送信すべきデータの量が少なくなり、転送時間を節約できるものである。
【０００３】
この場合、画像データには、カラーのものや、グレースケールのものなどがあるが、以下では、これらの画像データを２値化した２値化ビットマップ画像の圧縮方法について述べる。
【０００４】
従来の２値ビットマップ画像の圧縮方法としては、ＭＨ（Modified  Huffman）、ＭＲ（Modified  READ）、ＭＭＲ（Modified  Modified  READ）、ＪＢＩＧ（Joint  Bi-level  Image  Group）等があり、ファイルへの格納やＦＡＸなどに広く使用されている。
【０００５】
これらの圧縮方法は、符号化処理が複雑であることから、処理速度の高速化をねらった「ビットマップデータの圧縮方法及び圧縮装置」（特開平８−５１５４５号）が発案されている。
【０００６】
上記特開平８−５１５４５号の画像圧縮方法では、まず画像を所定のライン数単位に水平方向に走査して行間のように連続する空白ラインを垂直スキップとして符号化し、空白ライン以外の領域を論理行として分離する。次に、分離した論理行を１列単位に垂直方向に走査して文字間のように黒画素を含まない空白領域をスキップし、空白領域以外の黒画素を含む領域を分離する。
【０００７】
そして、白画素のみからなる領域と、黒画素のみからなる領域をそれぞれ列数を指定してスキップするように符号化し、同じ画素値の列が連続する領域をその値と繰り返し回数により符号化する。それ以外の領域は画素データをその列数と共にそのまま符号データとして出力する。
【０００８】
【発明が解決しようとする課題】
前述のビットマップデータの圧縮方法には、ディザパターンのような一定の大きさのパターンが繰り返し出現する画像の圧縮率が低下するという問題があった。
【０００９】
図９は、従来のディザパターンの符号化方法を説明する図である。
同図上に示されるように、画像の走査は、例えば、８ライン単位で行われる。空白行は、何も画像データがない部分であるので、８ライン単位の行を何個スキップするかという情報を符号化する。
【００１０】
ディザが含まれている行は論理行として認識され、８ライン毎に、符号化が行われる。同図下は、ディザパターンの符号化方法の説明である。すなわち、従来では、ディザパターンはそのままビットパターンが符号化されており、例えば、８ライン×Ｎ画素からなる論理行の符号化は、ディザが含まれている部分領域をそのまま符号化していた。従って、符号データは、符号語、画素幅Ｎ、部分領域の画素データ（Ｎバイト）からなり、Ｎバイトよりも大きくなっていた。
【００１１】
従って、ディザパターンを含むような画像であっても、有効に圧縮できる画像圧縮方法が望まれるところである。
本発明の課題は、連続して繰り返し出現するパターンを符号化することで圧縮率を向上させる符号化方法を提供することである。
【００１２】
【課題を解決するための手段】
本発明の画像圧縮方法は、画像データを圧縮する方法であって、２値画像データの内、反復パターンが含まれている行を抽出する抽出ステップと、該反復パターンの単位パターンと、該単位パターンの繰り返し回数を検出する反復パターン検出ステップと、少なくとも、該単位パターンのデータと、反復パターン内における該単位パターンの繰り返し回数とを使って、画像データ内の反復パターンを含む行を符号化する符号化ステップとを備えることを特徴とする。
【００１３】
本発明によれば、ディザパターンのように、単位となるパターンが繰り返し出てくる画像データを有効に符号化し、画像データの圧縮率を向上することができる。
【００１４】
【発明の実施の形態】
図１は、本発明の実施形態に従った符号化方法の処理全体の流れを示すフローチャートである。
【００１５】
まず、入力された画像を所定ライン数単位に水平方向に走査し（ステップＳ１０１）、行間のように連続する空白ラインを垂直スキップとして符号化し、空白ライン以外の領域を論理行として分離する（ステップＳ１０２）。
【００１６】
次に、分離した論理行を１列単位に垂直方向に走査し（ステップＳ１０３）、文字間のように黒画素を含まない空白領域をスキップし、空白領域以外の黒画素を含む領域を分離する（ステップＳ１０４）。
【００１７】
更に、ステップＳ１０４の領域分離結果に基づいて、連続して繰り返し出現する同一幅及び同一画素値を有する反復パターンを分離する（ステップＳ１０５）。
【００１８】
そして、ステップＳ１０２、Ｓ１０４、Ｓ１０５で分離した各領域を要素として符号化を行う（Ｓ１０６）。
図２は、本発明の実施形態の第一の原理を示す図である。
【００１９】
論理行の中から連続して繰り返し出現するパターンを検出し、繰り返しの基本となる反復パターンの長さと画素値、及びその繰り返し回数を使用して符号化することにより符号データサイズを削減する。これにより、符号データは、符号語、反復回数Ｋ、画素幅Ｍ、反復パターンの基本パターン（Ｍバイト）からなり、ディザパターンの符号データの長さが、ほぼＮ／Ｋバイトとなり、従来のディザパターンの符号データの長さに比べ、略１／Ｋの長さとなる。
【００２０】
画像の生成過程において、該画像の生成時に使用されるディザパターンの繰り返しの基本要素となるパターンのサイズが既知の場合がある。この場合、繰り返しパターンの検出をこの既知のサイズに限定して行うことで、全てのサイズについて検出を行う場合に比べて検出処理を大幅に削減し、高速に検出することができる。
【００２１】
図３は、本発明の実施形態に従った第二の原理を示す図である。
検出した反復パターンをそのまま符号データとして出力する代わりに、反復パターン自体をラインレングス符号化等のデータ圧縮方法により圧縮することで、符号データサイズを更に削減することができる。
【００２２】
このとき、反復パターンの圧縮効果が無ければ、該反復パターンを圧縮しないで符号データとして出力する。
同図においては、（Ａ）に示されるようなディザパターンがあったとすると、反復長がＭ画素の反復パターンの基本パターンがＫ回繰り返されている。そこで、（Ｂ）に示されるように、Ｍ画素からなる反復パターンの基本パターンを取り出し、これをランレングス符号かする。ランレングス符号化の方法は、（Ｃ）に示されるように、基本パターンの先頭の８行画素からなる列から順に列の中のどこに黒画素があるかを調べる。まず、（Ｂ）の最初の４列は同じパターンであるので、１列分の画素パターンが４つ並んでいるという情報を生成する。次に、黒画素がない列が２列並んでおり、以下同様にして、各列毎に、基本となる黒画素のパターンとそのパターンが列方向に何回連続するかの情報を生成し、Ｍ’バイトのランレングス符号データを生成する。ランレングス符号化を行うと、行わないよりも更に良い圧縮効果が得られる。
【００２３】
ランレングス符号化しない場合は、符号データは、符号語、ランレングスフラグ＝０（ランレングス符号化していないことを示す）、パターン長Ｍ、反復回数Ｋ、パターンデータからなる。ランレングス符号化すると、符号語、ランレングスフラグ＝１（ランレングス符号化していることを示す）、ランレングス符号データ長Ｍ’バイト、反復回数Ｋ、ランレングス符号データという構成の符号データが得られる。
【００２４】
図４は、本発明の実施形態の処理の流れを示すフローチャートである。
同図のフローチャートは、図１に示した原理図におけるステップＳ１０５とステップＳ１０６の処理に対応し、分離された論理行を符号化する処理を示している。空白領域の符号化は従来通りの方法で行う。
【００２５】
以下に、処理フローの説明をする。
ステップＳ２０１：符号化処理開始前に必要な、作業用メモリ領域の割当てや、内部パラメータの初期化などの初期化処理を行う。後述するパターンテーブルに登録されているパターンの個数をカウントするパラメータもここでゼロに初期化しておく。
【００２６】
ステップＳ２０２：論理行から連続して繰り返し出現する同一サイズ及び画素値を持つパターンの有無を検出する。
ステップＳ２０３：Ｓ２０２の検出結果に基づき、反復パターンが検出された場合には処理をＳ２０５に進み、反復パターンが検出されなかった場合には処理をＳ２０４に進む。
【００２７】
ステップＳ２０４：従来の符号化を行う。
ステップＳ２０５：検出された反復パターンの領域を符号化する。
ステップＳ２０６：全ての論理行の符号化が完了したか否かを判断し、完了していない場合には処理をＳ２０２に戻し、完了した場合には符号化処理を終了する。
【００２８】
以下、反復パターン検出処理Ｓ２０２と反復パターン符号化Ｓ２０５の各処理について、図面を参照しながら詳細に説明する。
図５は、反復パターン検出の実施形態を示す処理フローであり、図４のＳ２０２の処理に対応する。
【００２９】
論理行内を１列単位に走査して、連続する反復パターンの単位パターンの有無を確認し、反復パターンの単位パターンがある場合には反復パターンの単位パターンと共にその長さｌｅｎと反復回数ｎｕｍを取得する。
【００３０】
ステップＳ３０１：検出された反復パターンの単位パターンの反復回数を示すｎｕｍに０を設定する。また、反復パターンの単位パターンの検出を開始する列を示す変数ａに１、すなわち論理行の先頭列を設定する。
【００３１】
ステップＳ３０２：検出を開始する反復パターンの長さとしてｌｅｎにＭＩＮ ＬＥＮを設定する。ＭＩＮ ＬＥＮは、予想される反復パターンの単位パターンから適切な値を割り当てればよい。例えば、画像中の反復パターンの単位パターンの幅が４画素以上であることが予め分かっている場合には、ＭＩＮ ＬＥＮ＝４とする。こうすることで、存在しない反復パターンの検出処理を回避し、処理時間を短縮できる。
【００３２】
ステップＳ３０３：参照する列番号を示す変数ｂに、検出する反復パターンのの単位パターン長さｌｅｎをａに加えた値を設定する。
ステップＳ３０４：ａを先頭とするｌｅｎ列の画像と、ｂを先頭とするｌｅｎ列の画像を比較し、一致するか否かを判断する。両者が一致しない場合には処理をステップＳ３０５に移し、両者が一致する場合には処理をステップＳ３１０に進める。
【００３３】
ステップＳ３０５：長さｌｅｎ列の検出する反復パターンの単位パターンの長さｌｅｎに１を加えて、検出する反復パターンの単位パターンの長さを１列分長く設定する。
【００３４】
ステップＳ３０６：反復パターンの単位パターンの長さｌｅｎが検出する最大の長さＭＡＸ ＬＥＮに達したか、またはｌｅｎが検出処理を適用していない残り列数の半分に達したか否かを確認し、いずれかの条件を満たす場合には処理をステップＳ３０３に戻し、両条件ともに満たさない場合には処理をステップＳ３０７に進める。ここで、ｌｅｎが検出処理を適用していない残り列数（ＷＩＤＴＨ−ａ）の半分に達するということは、検出処理しようとしている列位置ａから始まる長さｌｅｎの単位パターンが、残りの列の中に１つより多くは含まれ得ないことを意味している。従って、反復パターンとはならないので、次のパターン検出処理であるステップＳ３０７に進むのである。
【００３５】
ステップＳ３０７：反復パターン検出開始列を示すａに１を加える。すなわち、反復パターンの単位パターンの検出を開始する列を１列進める。
ステップＳ３０８：検出処理を適用していない残り列数が、検出する反復パターンの単位パターンの最短長の２倍以上残っている場合には処理をステップＳ３０２に戻し、そうでない場合にはステップＳ３０９に処理を進める。ステップＳ３０９に進む場合は、検出しようとする単位パターンが残りの列数の中に１つより多く含まれないことになるので、反復パターンとはならないことから、反復パターンの検出処理を終了するための処理に移るものである。
【００３６】
ステップＳ３０９：論理行内に連続して出現する反復パターンが存在しない旨出力して処理を終了する。
以上の処理をステップＳ３０４でＹＥＳとなるまで繰り返し行うことにより、論理行内の連続して出現する反復パターンの有無と、反復パターンが存在した場合には、その位置及び反復パターンの単位パターンが検出された場合には更に以下の処理を行う。
【００３７】
ステップＳ３１０：ここまでの処理により反復パターンが２個連続していることが検出されていることになるため、反復パターンの反復回数をカウントする変数ｎｕｍに２を設定する。
【００３８】
ステップＳ３１１：反復パターン有無を検出する次の列を示すようにｂをｌｅｎに加算し、１パターン分の列数だけ先に進める。
ステップＳ３１５：次に、１パターン先の検出処理開始位置である列ｂが、列幅ＷＩＤＴＨからパターンの幅であるｌｅｎを引いたものより小さいか否か、すなわち、列ｂから始まる長さｌｅｎのパターンが残りの列数の中に収まるか否かを判断する。ｂがＷＩＤＴＨ−ｌｅｎ以下である場合には、ステップＳ３１２に進み、ｂがＷＩＤＴＨ−ｌｅｎより大きい場合には、ステップＳ３１４に進む。
【００３９】
ステップＳ３１２：Ｓ３０４と同様に、ａを先頭とするｌｅｎ列の画像と、ｂを先頭とするｌｅｎ列の画像を比較し、一致するか否かを判断する。両者が一致しない場合には処理をＳ３１４に移し、両者が一致する場合には処理をＳ３１３に進める。
【００４０】
ステップＳ３１３：検出した反復パターンの反復回数を示すカウンタｎｕｍに１を加算し、処理をＳ３１１に戻す。連続する反復パターンが検出されなくなるまでステップＳ３１１〜Ｓ３１３を繰り返し行うことで、反復パターンの連続する個数が検出される。
【００４１】
ステップＳ３１４：検出された反復パターンの開始位置ａと、反復パターンの長さｌｅｎ及び反復回数ｎｕｍを結果として出力し、処理を終了する。
以上の処理により、論理行内に反復パターンが存在するか否かが判明し、反復パターンが存在する場合には、その開始位置と反復パターンの単位パターンの長さ及び反復回数が得られる。
【００４２】
図６は、符号語のビット構成の実施形態を示す図である。
図６（ａ）は、検出した反復パターンをランレングス符号化しないで反復パターンをそのまま符号として出力する例、図６（ｂ）は反復パターンをランレングス符号化して出力する場合の例である。図６（ａ）では、ランレングス符号データでないことを示すため、ランレングス符号化フラグを０にセットし、単位パターンの長さを示すデータ長Ｍで指定された画素幅の反復パターンの単位パターンデータを出力する。図６（ｂ）では、ランレングス符号化されていることを示すため、ランレングス符号化フラグを１にセットし、ランレングス符号化したデータの長さを示すデータ長Ｍ’バイトのランレングス符号データを出力する。何れの場合も、符号化データの中には、反復パターンの単位パターンが何回繰り返し出てくるかを示す反復回数Ｋが設定される。
【００４３】
図７は、パターンテーブルの例を示した図である。
前述のパターンテーブルは、ディザパターンを符号化する場合に、例えば、１ページの文書の中で出てきた単位パターンをその長さと共に登録し、１ページの中で同じ単位パターンが現れた時には、前述の符号化データの内のパターンデータあるいは、ランレングス符号データの部分に、パターンテーブルの登録番号を格納するようにする。登録番号は、画像を符号化していく間に、先に出てきた単位パターンから順次設定されるものであり、最初に出てきた単位パターンが登録番号１であり、２番目に出てきた単位パターンが登録番号２という具合である。
【００４４】
このパターンテーブルは、画像を符号化する場合に生成されるが、符号化データの中には含まれない。符号化された画像を復号する場合には、符号データから順次単位パターンを読み取り、パターンテーブルを復号側で再生する様にする。すると、符号データ内には、符号化の時に出てきた順番で単位パターンが埋め込まれているので、復号する場合にも、順次符号データを復号しながらパターンテーブルを作成すると、符号化の際に得られたものと同じものが得られることになる。したがって、符号データの中に、パターンテーブルの登録番号が出てきた場合には、復号の際に生成したパターンテーブルの登録番号を参照して、単位パターンを取得すれば、正しく符号データを復号することができる。
【００４５】
以上のように、パターンテーブルを使用することにより、符号データに単位パターンのビットデータをそのまま入れるより、圧縮率を上げることができる。更に、ランレングス符号化と併用すれば、画像データの圧縮率を更に上げることができる。
【００４６】
図８は、本実施形態の方法をプログラムで実現する場合に情報処理装置に必要とされるハードウェア環境図である。
バス１０でＣＰＵ１１と接続されたＲＯＭ１２には、ＢＩＯＳなどの基本プログラムが格納される。また、当該プログラムは、バス１０でＣＰＵ１１と接続された、ハードディスクなどの記憶装置１７に格納され、ＲＡＭ１３にコピーされて、ＣＰＵ１１によって実行される。読み取り装置１８は、フレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤなどの可搬記録媒体１９から当該プログラムを読み取り、情報処理装置２１にインストールを可能とするものである。あるいは、可搬記録媒体１９から当該プログラムを直接読み込んで、ＣＰＵ１１に実行させても良い。
【００４７】
入出力装置２０は、キーボード、マウス、テンプレート、ディスプレイなどからなり、情報処理装置２１のユーザからの命令をＣＰＵ１１に伝えたり、ＣＰＵ１１の演算結果をユーザに提示するためのものである。
【００４８】
通信インターフェース１４は、情報処理装置２１をネットワーク１５を介して情報提供者１６に接続するものである。情報提供者１６は、当該プログラムを持っていて、これをネットワーク１５経由で情報処理装置２１にダウンロードし、インストールして、ＣＰＵ１１が実行しても良い。あるいは、情報提供者１６と情報処理装置２１とをネットワーク１５で接続したまま、ネットワーク環境のもとで、当該プログラムを実行するようにしても良い。
【００４９】
（付記１）画像データを圧縮する方法であって、
２値画像データの内、反復パターンが含まれている行を抽出する抽出ステップと、
該反復パターンの単位パターンと、該単位パターンの繰り返し回数を検出する反復パターン検出ステップと、
少なくとも、該単位パターンのデータと、反復パターン内における該単位パターンの繰り返し回数とを使って、画像データ内の反復パターンを含む行を符号化する符号化ステップと、
を備えることを特徴とする画像圧縮方法。
【００５０】
（付記２）前記単位パターンの画素幅が予め定められた１以上の固定値であることを特徴とする付記１に記載の画像圧縮方法。
（付記３）前記符号化ステップにおいては、単位パターンを更にデータ圧縮し、該圧縮された単位パターンと該単位パターンの繰り返し回数により符号化することを特徴とする付記１に記載の画像圧縮方法。
【００５１】
（付記４）前記符号化ステップは、ランレングス符号化方法を使用することを特徴とする付記１に記載の画像圧縮方法。
（付記５）前記符号化ステップにおいて、出現した単位パターンを登録するテーブルを生成し、該単位パターンと同じ単位パターンが符号化の過程で２回以上出てくる場合には、該単位パターンの代わりに該テーブルにおける該単位パターンの登録番号を用いて、画像データを符号化することを特徴とする付記１に記載の画像圧縮方法。
【００５２】
（付記６）画像データを圧縮する方法であって、
２値画像データの内、反復パターンが含まれている行を抽出する抽出ステップと、
該反復パターンの単位パターンと、該単位パターンの繰り返し回数を検出する反復パターン検出ステップと、
少なくとも、該単位パターンのデータと、反復パターン内における該単位パターンの繰り返し回数とを使って、画像データ内の反復パターンを含む行を符号化する符号化ステップと、
を備えることを特徴とする画像圧縮方法を情報処理装置に実現させるプログラム。
【００５３】
（付記７）画像データを圧縮する方法であって、
２値画像データの内、反復パターンが含まれている行を抽出する抽出ステップと、
該反復パターンの単位パターンと、該単位パターンの繰り返し回数を検出する反復パターン検出ステップと、
少なくとも、該単位パターンのデータと、反復パターン内における該単位パターンの繰り返し回数とを使って、画像データ内の反復パターンを含む行を符号化する符号化ステップと、
を備えることを特徴とする画像圧縮方法を情報処理装置に実現させるプログラムを格納した、情報処理装置読み取り可能な記録媒体。
【００５４】
（付記８）画像データを圧縮する装置であって、
２値画像データの内、反復パターンが含まれている行を抽出する抽出手段と、該反復パターンの単位パターンと、該単位パターンの繰り返し回数を検出する反復パターン検出手段と、
少なくとも、該単位パターンのデータと、反復パターン内における該単位パターンの繰り返し回数とを使って、画像データ内の反復パターンを含む行を符号化する符号化手段と、
を備えることを特徴とする画像圧縮装置。
【００５５】
【発明の効果】
以上説明したように、本発明の画像圧縮方法によれば、ディザパターンのように同じパターンが連続して繰り返し出現する画像から繰り返しの基本となる基本パターンを検出して符号化することにより、写真などのディザを含む画像の圧縮率が向上する。このため、データを格納するための記憶容量の削減やデータ転送時間の短縮に大きく寄与する。
【図面の簡単な説明】
【図１】本発明の実施形態に従った符号化方法の処理全体の流れを示すフローチャートである。
【図２】本発明の実施形態の第一の原理を示す図である。
【図３】本発明の実施形態に従った第二の原理を示す図である。
【図４】本発明の実施形態の処理の流れを示すフローチャートである。
【図５】反復パターン検出の実施形態を示す処理フローである。
【図６】符号語のビット構成の実施形態を示す図である。
【図７】パターンテーブルの例を示した図である。
【図８】本実施形態の方法をプログラムで実現する場合に情報処理装置に必要とされるハードウェア環境図である。
【図９】従来のディザパターンの符号化方法を説明する図である。
【符号の説明】
１０      バス
１１      ＣＰＵ
１２      ＲＯＭ
１３      ＲＡＭ
１４      通信インターフェース
１５      ネットワーク
１６      情報提供者
１７      記憶装置
１８      読み取り装置
１９      可搬記録媒体
２０      入出力装置
２１      情報処理装置
【図１】
0003866568.tif 000002
【図２】
0003866568.tif 000003
【図３】
0003866568.tif 000004
【図４】
0003866568.tif 000005
【図５】
0003866568.tif 000006
【図６】
0003866568.tif 000007
【図７】
0003866568.tif 000008
【図８】
0003866568.tif 000009
【図９】
0003866568.tif 000010