(57)【要約】  【課題】  高速にデータファイルを符号化する符号化装置を提供する。  【解決手段】  画像処理装置（符号化装置）は、入力された画像を既定サイズのブロックに分割し、ブロック毎にランレングス変換処理又は予測処理を行う。ブロック内の画素は、それぞれ独立に処理することができるように構成する。これにより、短いフィードバックや分岐がなく、また並列化に適しているために、符号化処理の高速化が容易になる。また、画像の主走査方向に配列された画素群をブロックとすることにより、画素値のバッファリングに要するメモリ領域を小さくすることができる。【選択図】図５
2007336056.tif 000002
【特許請求の範囲】
【請求項１】
入力されたデータファイルを、符号化処理の順序で配列された複数のデータ要素からなるブロックに分割するブロック分割手段と、
前記ブロック分割手段により分割されたブロックそれぞれについて、他のブロックに含まれるデータ要素に基づいて予測データを生成する予測データ生成手段と、
前記予測データ生成手段により生成された予測データと、前記ブロックに含まれるデータ要素とを比較する比較手段と、
前記比較手段による比較結果に基づいて、入力されたデータファイルの符号を生成する符号生成手段と
を有する符号化装置。
【請求項２】
前記予測データ生成手段は、注目ブロックの予測データを生成する場合に、この注目ブロックの直前に処理対象となった１つのデータ要素を予測データとし、
前記比較手段は、前記注目ブロックに含まれるデータ要素それぞれと、前記予測データとを比較し、
前記符号生成手段は、前記予測データと前記注目ブロックに含まれる全てのデータ要素とが一致する場合に、予測が的中した旨を示す符号をこの注目ブロックの符号として生成する
請求項１に記載の符号化装置。
【請求項３】
前記予測データ生成手段は、注目ブロックの予測データを生成する場合に、この注目ブロックに対して１つの予測データを決定し、決定された予測データが複数配列された予測ブロックを生成し、
前記比較手段は、前記予測データ生成手段により生成された予測ブロックと、前記注目ブロックとを比較し、
前記符号生成手段は、前記予測ブロックと前記注目ブロックとが一致する場合に、予測が的中した旨を示す符号をこの注目ブロックの符号として生成する
請求項１に記載の符号化装置。
【請求項４】
前記予測データ生成手段は、注目ブロックの予測データを生成する場合に、この注目ブロックの直前に処理対象であった直前ブロックを予測データとし、
前記比較手段は、前記注目ブロックのビット列と前記直前ブロックのビット列とを比較し、
前記符号生成手段は、前記注目ブロックのビット列と前記直前ブロックのビット列とが一致する場合に、予測が的中した旨を示す符号をこの注目ブロックの符号として生成する
請求項１に記載の符号化装置。
【請求項５】
前記比較手段は、前記ブロックに含まれる複数のデータ要素と、それぞれのデータ要素に対応する予測データとを並行して比較する
請求項１又は２に記載の符号化装置。
【請求項６】
ブロック単位で予測誤差を算出する予測誤差算出手段
をさらに有し、
前記符号生成手段は、前記予測データと前記ブロックに含まれる全てのデータ要素とが一致する場合に、予測が的中する旨を示す符号を生成し、前記予測データと前記ブロックに含まれるいずれかのデータ要素とが不一致である場合に、前記予測誤差算出手段により算出された予測誤差を示す符号を生成する
請求項１に記載の符号化装置。
【請求項７】
入力されたデータファイルを、符号化処理の順序で配列された複数のデータ要素からなるブロックに分割するブロック分割手段と、
前記ブロック分割手段により分割されたブロックそれぞれについて、他のブロックに含まれるデータ要素に基づいて予測データを生成する予測データ生成手段と、
前記予測データ生成手段により生成された予測データに基づいて、ブロック単位で予測誤差を算出する予測誤差算出手段と、
前記予測誤差算出手段により算出された予測誤差に基づいて、入力されたデータファイルの符号を生成する符号生成手段と
を有する符号化装置。
【請求項８】
入力されたデータファイルを、符号化処理の順序で配列された複数のデータ要素からなるブロックに分割し、
分割されたブロックそれぞれについて、他のブロックに含まれるデータ要素に基づいて予測データを生成し、
生成された予測データと、前記ブロックに含まれるデータ要素とを比較し、
この比較結果に基づいて、入力されたデータファイルの符号を生成する
符号化方法。
【請求項９】
入力されたデータファイルを、符号化処理の順序で配列された複数のデータ要素からなるブロックに分割するステップと、
分割されたブロックそれぞれについて、他のブロックに含まれるデータ要素に基づいて予測データを生成するステップと、
生成された予測データと、前記ブロックに含まれるデータ要素とを比較するステップと、
この比較結果に基づいて、入力されたデータファイルの符号を生成するステップと
をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データファイルを符号化する符号化方法に関する。
【背景技術】
【０００２】
例えば、特許文献１には、画像データの同一２次元パターンをパラレルに検出することによってパターンランレングスデータを得ることにより、パターンランレングスデータに変換する変換処理を高速化する方法が開示されている。
【特許文献１】特開平５−１７６１８１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明は、上述した背景からなされたものであり、高速にデータファイルを符号化する符号化装置を提供することを目的とする。
【課題を解決するための手段】
【０００４】
［符号化装置］
上記目的を達成するために、本発明にかかる符号化装置は、入力されたデータファイルを、符号化処理の順序で配列された複数のデータ要素からなるブロックに分割するブロック分割手段と、前記ブロック分割手段により分割されたブロックそれぞれについて、他のブロックに含まれるデータ要素に基づいて予測データを生成する予測データ生成手段と、前記予測データ生成手段により生成された予測データと、前記ブロックに含まれるデータ要素とを比較する比較手段と、前記比較手段による比較結果に基づいて、入力されたデータファイルの符号を生成する符号生成手段とを有する。
【０００５】
好適には、前記予測データ生成手段は、注目ブロックの予測データを生成する場合に、この注目ブロックの直前に処理対象となった１つのデータ要素を予測データとし、前記比較手段は、前記注目ブロックに含まれるデータ要素それぞれと、前記予測データとを比較し、前記符号生成手段は、前記予測データと前記注目ブロックに含まれる全てのデータ要素とが一致する場合に、予測が的中した旨を示す符号をこの注目ブロックの符号として生成する。
【０００６】
好適には、前記予測データ生成手段は、注目ブロックの予測データを生成する場合に、この注目ブロックに対して１つの予測データを決定し、決定された予測データが複数配列された予測ブロックを生成し、前記比較手段は、前記予測データ生成手段により生成された予測ブロックと、前記注目ブロックとを比較し、前記符号生成手段は、前記予測ブロックと前記注目ブロックとが一致する場合に、予測が的中した旨を示す符号をこの注目ブロックの符号として生成する。
【０００７】
好適には、前記予測データ生成手段は、注目ブロックの予測データを生成する場合に、この注目ブロックの直前に処理対象であった直前ブロックを予測データとし、前記比較手段は、前記注目ブロックのビット列と前記直前ブロックのビット列とを比較し、前記符号生成手段は、前記注目ブロックのビット列と前記直前ブロックのビット列とが一致する場合に、予測が的中した旨を示す符号をこの注目ブロックの符号として生成する。
【０００８】
好適には、前記比較手段は、前記ブロックに含まれる複数のデータ要素と、それぞれのデータ要素に対応する予測データとを並行して比較する。
【０００９】
好適には、ブロック単位で予測誤差を算出する予測誤差算出手段をさらに有し、前記符号生成手段は、前記予測データと前記ブロックに含まれる全てのデータ要素とが一致する場合に、予測が的中する旨を示す符号を生成し、前記予測データと前記ブロックに含まれるいずれかのデータ要素とが不一致である場合に、前記予測誤差算出手段により算出された予測誤差を示す符号を生成する。
【００１０】
また、本発明にかかる符号化装置は、入力されたデータファイルを、符号化処理の順序で配列された複数のデータ要素からなるブロックに分割するブロック分割手段と、前記ブロック分割手段により分割されたブロックそれぞれについて、他のブロックに含まれるデータ要素に基づいて予測データを生成する予測データ生成手段と、前記予測データ生成手段により生成された予測データに基づいて、ブロック単位で予測誤差を算出する予測誤差算出手段と、前記予測誤差算出手段により算出された予測誤差に基づいて、入力されたデータファイルの符号を生成する符号生成手段とを有する。
【００１１】
［符号化方法］
また、本発明にかかる符号化方法は、入力されたデータファイルを、符号化処理の順序で配列された複数のデータ要素からなるブロックに分割し、分割されたブロックそれぞれについて、他のブロックに含まれるデータ要素に基づいて予測データを生成し、生成された予測データと、前記ブロックに含まれるデータ要素とを比較し、この比較結果に基づいて、入力されたデータファイルの符号を生成する。
【００１２】
［プログラム］
また、本発明にかかるプログラムは、入力されたデータファイルを、符号化処理の順序で配列された複数のデータ要素からなるブロックに分割するステップと、分割されたブロックそれぞれについて、他のブロックに含まれるデータ要素に基づいて予測データを生成するステップと、生成された予測データと、前記ブロックに含まれるデータ要素とを比較するステップと、この比較結果に基づいて、入力されたデータファイルの符号を生成するステップとをコンピュータに実行させる。
【発明の効果】
【００１３】
本発明の符号化装置によれば、高速にデータファイルを符号化することができる。
【発明を実施するための最良の形態】
【００１４】
［背景と概略］
まず、本発明の理解を助けるために、その背景を説明する。
ランレングス符号化方式は、データファイルにおいて同一のデータ要素が連続する場合に、このデータ要素群（ラン）を、データ要素値と連続長（ランレングス）で表現する符号化方式である。なお、以下の説明では、画像データを符号化する場合を具体例として説明する。
予測符号化方式（狭義）は、画素値を予測し、その予測誤差を符号とする符号化方式である。予測符号化方式は、処理が簡易であるため広く使われており、国際標準JPEG-LSなどもこの一種に分類できる。なお、ランレングス符号化方式も、直前の画素値を予測値とする点で広義の予測符号化方式に含まれるが、以下の説明では、ランレングス符号化方式と、狭義の予測符号化方式とを区別して説明する。
【００１５】
ランレングス符号化方式及び予測符号化方式は、いずれも広く使われているが、処理が基本的に画素単位であるために、高速化が難しいという問題がある。
【００１６】
そこで、本実施形態における画像処理装置２は、入力された画像を既定サイズのブロックに分割し、ブロック毎にランレングス変換処理又は予測処理を行う。ブロック内の画素は、それぞれ独立に処理することができるように構成する。これにより短いフィードバックや分岐がなく、また並列化に適しているために、符号化処理の高速化が容易になる。
なお、ブロックの形状は種々考えられるが、符号化処理の順序でブロックに入れていくことが望ましい。すなわち、画像データを符号化する場合には、画像の主走査方向に配列された画素群をブロックとする。副走査方向に複数の画素を含むブロックを生成すると、画素値をバッファリングするメモリのサイズが大きくなってしまうからである。
【００１７】
［ハードウェア構成］
次に、実施形態における画像処理装置２のハードウェア構成を説明する。
図１は、本発明にかかる符号化方法が適応される画像処理装置２のハードウェア構成を、制御装置２１を中心に例示する図である。
図１に例示するように、画像処理装置２は、ＣＰＵ２１２及びメモリ２１４などを含む制御装置２１、通信装置２２、ＨＤＤ・ＣＤ装置などの記録装置２４、並びに、ＬＣＤ表示装置あるいはＣＲＴ表示装置およびキーボード・タッチパネルなどを含むユーザインターフェース装置（ＵＩ装置）２５から構成される。
画像処理装置２は、例えば、プリンタ装置３の内部に設けられており、符号化プログラム５（後述）及び復号化プログラム６（後述）がインストールされた装置である。
【００１８】
［符号化プログラム］
図２は、制御装置２１（図１）により実行され、本発明にかかる符号化方法を実現する第１の符号化プログラム５の機能構成を例示する図である。なお、本例では、各画素の画素値が８ビットで表現されている場合を具体例として説明する。
図２に例示するように、第１の符号化プログラム５は、ブロック分割部５００、置換判定部５１０、ランカウンタ５２０及びエントロピ符号化部５３０を有する。
【００１９】
符号化プログラム５において、ブロック分割部５００は、入力されたデータファイルを、符号化処理の順序で配列された複数のデータ要素からなるブロックに分割し、分割されたブロックを置換判定部５１０に出力する。
本例のブロック分割部５００は、図３（Ａ）に例示するように、入力された画像を、主走査方向に配列された４画素（画素０〜画素３）からなるブロックに分割し、各ブロックの画像データ（画素０〜画素３の各画素値）を置換判定部５１０に出力する。
【００２０】
置換判定部５１０（予測データ生成手段）は、注目ブロックの予測データを生成する場合に、他のブロックに含まれるデータ要素（画素値）に基づいて、予測データを生成する。
本例の置換判定部５１０は、図３（Ｂ）に例示するように、注目ブロックの各画素値に対する予測データを生成する場合に、この注目ブロックの直前画素値（画素３’の画素値）を予測データとする。すなわち、直前ブロックに含まれる単一の画素値（最後の画素値）が、注目ブロックに含まれる各画素の予測画素値となる。
なお、置換判定部５１０は、図３（Ｃ）に例示するように、注目ブロックの各画素値に対する予測データを生成する場合に、この注目ブロックの直前ブロックに含まれる各画素値を予測データとしてもよい。すなわち、注目ブロックの各画素に対する予測画素値は、直前ブロックの対応する位置の画素値となるようにしてもよい。
【００２１】
置換判定部５１０は、生成された予測データと、注目ブロックに含まれる各データ要素（画素値）とを比較し、全データ要素が予測データと一致した場合に、予測が的中した旨をランカウンタ５２０に通知し、いずれかのデータ要素が予測データと不一致でなった場合に、予測が外れた旨をランカウンタ５２０に通知し、この注目ブロックに含まれる画素値をそのまま被符号化シンボルとしてエントロピ符号化部５３０に出力する。
本例の置換判定部５１０は、図４（Ａ）に例示するように、直前画素値を４つ配列して予測ブロックを生成し、予測ブロックのビット列と、注目ブロックのビット列（図４（Ｂ））とを比較し、これらのビット列が一致した場合（すなわち、図４（Ｃ）の差分が０の場合）、予測が的中した旨をランカウンタ５２０に通知し、一致しない場合（すなわち、図４（Ｃ）の差分が０以外である場合）、予測が外れた旨をランカウンタ５２０に通知し、注目ブロックのビット列（３２ビット）を被符号化シンボルとしてエントロピ符号化部５３０に出力する。
【００２２】
ランカウンタ５２０は、置換判定部５１０から予測が的中した旨を通知されると、ランレングス（予測的中の連続数）をカウントアップし、予測が外れると、これまでのカウント値（ラン数）を、置換判定部５１０に出力する。置換判定部５１０は、ランカウンタ５２０からラン数が入力されると、このランの予測データ（直前画素値）と、ラン数とを被符号化シンボルとしてエントロピ符号化部５３０に出力する。
【００２３】
エントロピ符号化部５３０は、置換判定部５１０から入力された予測データ及びラン数、又は、注目ブロックの画素値を可変長符号で符号化する。
本例のエントロピ符号化部５３０は、置換判定部５１０から予測データ及びラン数が入力されると、入力された予測データ及びラン数を符号化し、置換判定部５１０から注目ブロックに含まれる画素群のビット列（３２ビット）が入力されると、このビット列を符号化する。
【００２４】
図５は、符号化プログラム５（図２）による符号化処理（Ｓ１０）のフローチャートである。
図５に示すように、ステップ１００（Ｓ１００）において、ブロック分割部５００（図２）は、入力された画像データから、走査順に４画素を切り出し、切り出された４画素を注目ブロックとして置換判定部５１０に出力する。
【００２５】
ステップ１１０（Ｓ１１０）において、置換判定部５１０は、直前ブロックの最後の画素値（すなわち、注目ブロックの直前画素値）を保持しており、保持されている直前画素値と、ブロック分割部５００から入力された注目ブロックの各画素値とを並行して比較する。具体的には、置換判定部５１０は、図４（Ａ）に例示するように、直前画素値が４つ配列されたビット列（予測ブロックのビット列）を生成し、予測ブロックのビット列と、注目ブロックのビット列とを比較して、これらのビット列が完全一致する場合に、予測が的中した旨をランカウンタ５２０に通知し、これらのビット列が完全一致しなかった場合に、予測が外れた旨をランカウンタ５２０に出力する。
【００２６】
ステップ１２０（Ｓ１２０）において、符号化プログラム５は、直前画素値と注目ブロックの各画素値とが全て一致した場合（すなわち、予測が的中した場合）、Ｓ１３０の処理に移行し、直前画素値と注目ブロックのいずれかの画素値とが不一致となった場合（すなわち、予測が外れた場合）、Ｓ１４０の処理に移行する。
【００２７】
ステップ１３０（Ｓ１３０）において、ランカウンタ５２０は、置換判定部５１０から予測が的中した旨を通知されると、ランのカウント値を１つ増加させる。なお、ランの初期値は０である。
符号化プログラム５は、Ｓ１００の処理に戻って、入力された画像データから、次の注目ブロックを切り出す。なお、次の注目ブロックが存在しない場合には、例外処理が実行される。
【００２８】
ステップ１４０（Ｓ１４０）において、ランカウンタ５２０は、置換判定部５１０から予測が外れた旨を通知されると、ランのカウント値を置換判定部５１０に出力して、カウント値を初期化する。
置換判定部５１０は、ランカウンタ５２０から入力されたカウント値（ラン数）と、そのときの予測画素値（直前画素値）とを被符号化シンボルとしてエントロピ符号化部５３０に出力する。
エントロピ符号化部５３０は、置換判定部５１０から入力されたラン数及び直前画素値を可変長符号で符号化する。
【００２９】
ステップ１５０（Ｓ１５０）において、置換判定部５１０は、ラン数及び直前画素値をエントロピ符号化部５３０に出力した後に、注目ブロックの画素値群をエントロピ符号化部５３０に出力する。
エントロピ符号化部５３０は、置換判定部５１０から入力された注目ブロックの画素値群を可変長符号で符号化する。
【００３０】
ステップ１６０（Ｓ１６０）において、符号化プログラム５は、入力された画像データを全て符号化したか否かを判断し、未処理の画素が存在する場合に、Ｓ１００の処理に戻り、全ての画素が符号化された場合に、符号化処理（Ｓ１０）を終了する。
【００３１】
［復号化プログラム］
次に、上記のように符号化された符号データの復号化方法について説明する。
図６は、制御装置２１（図１）により実行される復号化プログラム６の機能構成を例示する図である。
図６に例示するように、復号化プログラム６は、ブロック復号部６００、ラン伸長部６１０、及び画像出力部６２０を有する。
【００３２】
復号化プログラム６において、ブロック復号部６００は、入力された符号データを復号化して、各ブロックの復号値を生成する。本例の復号値は、予測が的中したブロックについては、画素値（直前画素値）及びラン数となり、予測が外れたブロックについては、ブロックに含まれる全画素の画素値となる。
本例のブロック復号部６００は、画素値及びラン数をラン伸長部６１０に出力し、ブロックに含まれる全画素の画素値を画像出力部６２０に出力する。
【００３３】
ラン伸長部６１０は、ブロック復号部６００から入力されたラン数に応じて、入力された画素値を複製し、これらの画素値をブロックの画素値として画像出力部６２０に出力する。
本例のラン伸長部６１０は、（ラン数）×（ブロック内の画素数）だけ、入力された画素値を複製し、複製された画素値を画像出力部６２０に出力する。
なお、図３（Ｃ）に例示するように、直前ブロック全体と注目ブロック全体とをそのまま比較して符号化した場合には、ラン伸長部６１０は、ラン数だけ、直前ブロック（すなわち、４画素分の画素値）を複製し、複製されたブロックを画像出力部６２０に出力する。
【００３４】
画像出力部６２０は、ブロック復号部６００又はラン伸長部６１０から入力されたブロックの画素群を画素毎に分割する。
本例の画像出力部６２０は、ブロック復号部６００から入力されたブロックを４画素として外部に出力する。
【００３５】
図７は、復号化プログラム６（図６）による復号化処理（Ｓ２０）のフローチャートである。
図７に示すように、ステップ２００（Ｓ２００）において、ブロック復号部６００は、入力された符号データを、先頭の符号語から復号化する。復号化されるシンボルは、ラン数及び画素値、又は、ブロックに含まれる画素群の画素値である。
【００３６】
ステップ２１０（Ｓ２１０）において、復号化プログラム６は、復号化されたシンボルがラン及び画素値である場合に、Ｓ２２０の処理に移行し、復号化されたシンボルがブロックに含まれる画素群の画素値である場合に、Ｓ２３０の処理に移行する。
【００３７】
ステップ２２０（Ｓ２２０）において、ラン伸長部６１０は、ブロック復号部６００からラン数及び画素値が入力されると、（ラン数）×（ブロック内の画素数）だけ、画素値を複製し、複製された画素値を画像出力部６２０に出力する。
画像出力部６２０は、ラン伸長部６１０から入力された複数の画素値をそのまま外部に出力する。
【００３８】
ステップ２３０（Ｓ２３０）において、画像出力部６２０は、ブロック復号部６００からブロックに含まれる画素群の画素値が入力されると、入力された画素群の画素値を４画素の画素値として外部に出力する。
【００３９】
ステップ２４０（Ｓ２４０）において、復号化プログラム６は、全ての符号データが復号化されたか否かを判断し、未処理の符号が存在する場合には、Ｓ２００の処理に戻り、全ての符号データが復号化された場合には、復号化処理（Ｓ２０）を終了する。
【００４０】
以上説明したように、本実施形態の画像処理装置２は、ブロック単位でランレングス符号化処理を行うため、符号化処理を高速化できる。
なお、上記実施形態では、ランが途切れた場合（予測が外れた場合）に、ブロックに含まれる画素群の画素値を１つのビット列として符号化したが、この画素群の画素値を画素毎に並行して符号化してもよく、この場合には、復号化処理も各画素の画素値を並行して復号化できる。
【００４１】
［第１の変形例］
次に、上記実施形態の変形例を説明する。
上記実施形態では、ブロック単位でランを計数するため、復号化処理において、（ラン数）×（ブロック内の画素数）を用いて、ランを伸長する必要があるが、符号化処理において、（カウント値）×（ブロック内の画素数）をラン数としてもよい。これにより、画素単位で処理するランレングス方式で復号化することが可能になる。
図８は、第２の符号化処理（Ｓ１２）のフローチャートである。なお、本図に示された処理のうち、図５に示された処理と実質的に同一のものには同一の符号が付されている。
図８に示すように、Ｓ１００において、ブロック分割部５００（図２）は、入力された画像データから、走査順に４画素を切り出し、切り出された４画素を注目ブロックとして置換判定部５１０に出力する。
Ｓ１１０において、置換判定部５１０は、直前ブロックの最後の画素値（直前画素値）を保持しており、保持されている直前画素値と、注目ブロックの各画素値とを並行して比較する。
Ｓ１２０において、符号化プログラム５は、直前画素値と注目ブロックの各画素値とが全て一致した場合、Ｓ１３２の処理に移行し、直前画素値と注目ブロックのいずれかの画素値とが不一致となった場合、Ｓ１４０の処理に移行する。
【００４２】
ステップ１３２（Ｓ１３２）において、ランカウンタ５２０は、置換判定部５１０から予測が的中した旨を通知されると、ランのカウント値をブロック内の画素数だけ増加させる。本例では、１つのブロックに４画素含まれているため、カウント値を４ずつ増加させる。
【００４３】
Ｓ１４０において、ランカウンタ５２０は、置換判定部５１０から予測が外れた旨を通知されると、ランのカウント値を置換判定部５１０に出力して、カウント値を初期化する。
置換判定部５１０は、ランカウンタ５２０から入力されたカウント値（ラン数）と、そのときの予測画素値（直前画素値）とを被符号化シンボルとしてエントロピ符号化部５３０に出力する。
エントロピ符号化部５３０は、置換判定部５１０から入力されたラン数及び直前画素値を可変長符号で符号化する。
【００４４】
ステップ１５２（Ｓ１５２）において、置換判定部５１０は、ラン数及び直前画素値をエントロピ符号化部５３０に出力した後に、注目ブロックの画素値群をエントロピ符号化部５３０に出力する。
エントロピ符号化部５３０は、置換判定部５１０から入力された注目ブロックの各画素値をそれぞれ並行して符号化する。
【００４５】
Ｓ１６０において、符号化プログラム５は、入力された画像データを全て符号化したか否かを判断し、未処理の画素が存在する場合に、Ｓ１００の処理に戻り、全ての画素が符号化された場合に、符号化処理（Ｓ１０）を終了する。
【００４６】
このように生成された符号データは、従来からあるランレングス方式の復号化処理で復号化できる。
【００４７】
［変形例２］
上記実施形態では、ランレングス符号化処理をブロック単位で行う形態を説明したが、第２の変形例では、予測符号化処理をブロック単位で行う形態を説明する。
予測符号化処理では、図９（Ａ）に例示するように、注目位置Ｘのデータ要素に対して、周囲の参照位置Ａ〜Ｃのデータ要素を用いて、予測データを生成し、生成された予測データと、注目位置Ｘのデータ要素（注目データ）との差分（予測誤差）を符号化する。
これをブロック単位で行う場合には、図９（Ｂ）に例示するように、注目位置Ｘのブロックを注目ブロック、参照位置Ａのブロック全体を参照ブロックＡ、参照位置Ｂのブロック全体を参照ブロックＢ、参照位置Ｃのブロック全体を参照ブロックＣとして、注目ブロックに含まれる各画素に対して、参照ブロックの対応する位置にある参照画素値（Ａ０〜Ａ３、Ｂ０〜Ｂ３、及び、Ｃ０〜Ｃ３）を用いて、予測値を算出する。
また、図９（Ｃ）に例示するように、参照位置Ａのブロックを単一の画素値（参照ブロックＡの最後の画素値Ａ３）に縮退させ、参照位置Ｃのブロックを単一の画素値（参照ブロックＣの最後の画素値Ｃ３）に縮退させてもよい。
【００４８】
図９（Ｂ）の予測方法は、多ビット処理による並列化になじみやすいが、図９（Ｃ）の予測方法の方が圧縮率が高くなるという特徴を持つ。いずれの予測方法においても、ブロック内の画素値の予測に、同一ブロック内の画素値を用いていないので、フィードバックループが発生せず、処理の高速化が可能になる。
【００４９】
図１０は、予測符号化方式を適用した符号化プログラム５２の機能構成を例示する図である。なお、本図に示された各構成のうち、図２に示された構成と実質的に同一のものには同一の符号が付されている。
図１０に示すように、第２の符号化プログラム５２は、図２の符号化プログラム５から、置換判定部５１０及びランカウンタ５２０を削除し、予測部５４０及び予測誤差算出部５５０を追加した構成をとる。
【００５０】
予測部５４０は、ブロック分割部５００により生成されたブロック単位で、注目ブロックの予測データを生成し、生成された予測データを予測誤差算出部５５０に出力する。予測データの生成には、注目ブロック以外のブロックに含まれるデータ要素が用いられる。
本例の予測部５４０は、図９（Ｂ）に例示する式を用いて、参照位置Ａのブロック（Ａ０〜Ａ３）、参照位置Ｂのブロック（Ｂ０〜Ｂ３）、及び参照位置Ｃのブロック（Ｃ０〜Ｃ３）の画素値から、注目ブロックの予測データ（Ｘ０〜Ｘ３）を算出する。
【００５１】
予測誤差算出部５５０は、ブロック分割部５００により生成されたブロック単位で、注目ブロックの予測誤差を算出する。
本例の予測誤差算出部５５０は、ブロック分割部５００から入力された注目ブロックと、予測部５４０から入力された注目ブロックの予測データ（Ｘ０〜Ｘ３）との差分を算出し、算出された差分（予測誤差）を被符号化シンボルとしてエントロピ符号化部５３０に出力する。
【００５２】
本例の予測誤差算出部５５０は、図１１（Ａ）に例示するように、注目ブロックに含まれる各画素（注目画素０〜注目画素３）の画素値と、予測データに含まれる各予測値（予測値Ｘ０〜予測値Ｘ３）との差分を算出し、算出された差分（予測誤差０〜予測誤差３）それぞれを被符号化シンボルとする。
なお、予測誤差算出部５５０は、図１１（Ｂ）に例示するように、予測部５４０から入力された予測データ（予測値Ｘ０〜予測値Ｘ３）を１つのブロック（予測ブロック）のビット列とみなし、図１１（Ｃ）に例示するように、注目ブロックのビット列（注目画素０〜注目画素３のビット列が配列されたもの）と、予測ブロックのビット列との差分を、注目ブロックの予測誤差のビット列として算出してもよい。この場合、画素間で繰下がりが生じうるが、画質劣化として許容しうる範囲内である。また、予測誤差のビット列は、画素毎に分割されて被符号化シンボルとしてもよいし、分割せずにこのまま全体を被符号化シンボルとしてもよい。予測ブロックのビット列をまとめて処理する形態では、図９（Ｂ）の予測データ算出処理も、Ａ０〜Ａ３からなるビット列と、Ｂ０〜Ｂ３からなるビット列と、Ｃ０〜Ｃ３からなるビット列とを加減算することにより、Ｘ０〜Ｘ３のビット列を算出できるため、図１１（Ｃ）の方式と整合性がよく、実装性が高い。
【００５３】
このように、第２の符号化プログラム５２は、ブロック単位で予測符号化処理を行うため、予測符号化処理を高速に実現することができる。
【００５４】
［変形例３］
第３の変形例では、上記ランレングス符号化方式と予測符号化方式とを組み合わせる。ランレングス符号化方式と予測符号化符号化とを組み合わせる場合、両者のブロックは一致していなくてもよい。例えば、ランレングス符号化方式は、予測符号化方式よりも処理負荷が軽いので、予測符号化方式よりも並列度（すなわちブロックサイズ）を低くしてバランスしてもよい。
【００５５】
図１２は、第３の符号化プログラム５４の機能構成を例示する図である。なお、本図に示された各構成のうち、図２又は図１０に示された構成と実質的に同一のものには同一の符号が付されている。
図１２に例示するように、符号化プログラム５４は、４×１ブロック分割部５０２、予測部５４０、予測誤差算出部５５０、２×１ブロック分割部５０４、ラン生成部５６０、及び第２のエントロピ符号化部５３２を有する。
【００５６】
４×１ブロック分割部５０２は、入力された画像データを、主走査方向に４画素かつ副走査方向に１画素のブロックに分割する。
２×１ブロック分割部５０４は、入力された画像データを、主走査方向に２画素かつ副走査方向に１画素のブロックに分割する。
すなわち、ランレングス符号化方式が適用される場合には、予測符号化方式が適用される場合よりも小さなブロック（本例では１／２サイズ）が生成される。
【００５７】
２×１ブロック分割部５０４は、予測誤差算出部５５０により算出された各画素の予測誤差を、主走査方向に配列された２画素分ずつまとめて、２×１ブロックの予測誤差を生成する。
ラン生成部５６０は、２×１ブロックの単位で、予測誤差についてランを計数する。すなわち、ラン生成部５６０は、図２の置換判定部５１０及びランカウンタ５２０の機能を有し、予測誤差についてランを計数する。
エントロピ符号化部５３２は、ラン生成部５６０により生成された予測誤差のランデータ（ラン数及び予測誤差、又は、ブロック内の全予測誤差）を可変長符号で符号化する。
【００５８】
本例のエントロピ符号化部５３２は、可変長符号化処理に、２シンボルを新たな１シンボルとして情報源を拡大したハフマン符号を用いることにする。具体的には、図１３に例示するように、エントロピ符号化部５３２は、予測誤差の値及びランの組合せをシンボルとして、ハフマン符号の符号表を設計し、この符号表を用いて、予測誤差及びランの組合せに対応する符号語を出力する。
【００５９】
［その他の変形例］
なお、上記実施形態及び変形例では、いずれも被符号化シンボルを可変長符号でエントロピ符号化しているが、これに限定されるものではなく、これらのシンボル（ラン、画素値、予測誤差など）をそのまま符号として出力してもよい。
【図面の簡単な説明】
【００６０】
【図１】本発明にかかる符号化方法が適応される画像処理装置２のハードウェア構成を、制御装置２１を中心に例示する図である。
【図２】制御装置２１（図１）により実行され、本発明にかかる符号化方法を実現する第１の符号化プログラム５の機能構成を例示する図である。
【図３】ブロック単位のランレングス符号化方式を説明する図である。
【図４】ブロック単位でデータを比較する方法を例示する図である。
【図５】符号化プログラム５（図２）による符号化処理（Ｓ１０）のフローチャートである。
【図６】制御装置２１（図１）により実行される復号化プログラム６の機能構成を例示する図である。
【図７】復号化プログラム６（図６）による復号化処理（Ｓ２０）のフローチャートである。
【図８】第２の符号化処理（Ｓ１２）のフローチャートである。
【図９】ブロック単位の予測符号化方式を説明する図である。
【図１０】第２の符号化プログラム５２の機能構成を例示する図である。
【図１１】予測データの生成方法を例示する図である。
【図１２】第３の符号化プログラム５４の機能構成を例示する図である。
【図１３】ランレングス符号化方式と予測符号化方式とを組み合わせた場合の符号表を例示する図である。
【符号の説明】
【００６１】
２・・・画像処理装置
５，５２，５４・・・符号化プログラム
５００，５０２，５０４・・・ブロック分割部
５１０・・・置換判定部
５２０・・・ランカウンタ
５３０，５３２・・・エントロピ符号化部
５４０・・・予測部
５５０・・・予測誤差算出部
５６０・・・ラン生成部
６・・・復号化プログラム
６００・・・ブロック復号部
６１０・・・ラン伸長部
６２０・・・画像出力部
【図１】
2007336056.tif 000003
【図２】
2007336056.tif 000004
【図３】
2007336056.tif 000005
【図４】
2007336056.tif 000006
【図５】
2007336056.tif 000007
【図６】
2007336056.tif 000008
【図７】
2007336056.tif 000009
【図８】
2007336056.tif 000010
【図９】
2007336056.tif 000011
【図１０】
2007336056.tif 000012
【図１１】
2007336056.tif 000013
【図１２】
2007336056.tif 000014
【図１３】
2007336056.tif 000015