(57)【要約】【課題】スクリーン等によって変換された周期性をもつ画像データに対して、高速な画像符号化装置、画像復号化装置を提供することを目的としている。【解決手段】周辺画素を用いて画素値の予測を行い、予測値の当り外れを表す予測誤差データ系列を作成する予測変換手段と、前記予測誤差データ系列のラン長をカウントするラン長カウント手段と、前記ラン長を符号化する符号化手段とを備えた画像符号化装置であって、複数の画素からなる相関の強いブロックを検出する相関ブロック検出手段を備え、前記予測変換手段は前記相関ブロック検出手段によって検出されたブロック内の画素を用いて一括して前記予測変換を行うことを特徴とする画像符号化装置であって、複数の画素からなる相関の強いブロックを検出し、検出されたブロック内の画素を用いて一括して予測変換を行うようにしたので、高速な画像符号化装置が得られる。【選択図】  図７
2004172709.tif 000002
【特許請求の範囲】
【請求項１】
周辺画素を用いて画素値の予測を行い、予測値の当り外れを表す予測誤差データ系列を作成する予測変換手段と、前記予測誤差データ系列のラン長をカウントするラン長カウント手段と、前記ラン長を符号化する符号化手段とを備えた画像符号化装置であって、複数の画素からなる相関の強いブロックを検出する相関ブロック検出手段を備え、前記予測変換手段は前記相関ブロック検出手段によって検出されたブロック内の画素を用いて一括して前記予測変換を行うことを特徴とする画像符号化装置。
【請求項２】
前記相関ブロック検出手段は、スクリーン周期と演算処理の単位となるビット数Ｎ（Ｎ：正の整数）の最小公倍数を用いて相関の強い画素のブロックを検出することを特徴とする請求項１記載の画像符号化装置。
【請求項３】
前記ラン長カウント手段は、前記予測誤差データ系列において演算処理の単位となる前記Ｎビットの中に前記予測値の外れビットがあるか否かを判定する判定手段を備え、前記予測値の外れビットがない場合はラン長にＮを加えることを特徴とする請求項１または２記載の画像符号化装置。
【請求項４】
前記符号化手段は、周辺に出現するランの長さの出現頻度に応じてテーブルを切り換えて符号化することを特徴とする請求項１、２または３記載の画像符号化装置。
【請求項５】
復号化手段と、前記復号化によるラン長データから予測誤差データ系列を作成する予測誤差作成手段と、予測誤差データ系列から画素値を復元する逆予測変換手段とを備えた画像復号化装置であって、複数の画素からなる相関の強いブロックを検出する相関ブロック検出手段を備え、前記逆予測変換手段は前記相関ブロック検出手段によって検出されたブロック内の画素を用いて一括して逆予測変換を行うことを特徴とする画像復号化装置。
【請求項６】
前記相関ブロック検出手段は、スクリーン周期と演算処理の単位となるビット数Ｎ（Ｎ：正の整数）の最小公倍数を用いて相関の強い画素のブロックを検出することを特徴とする請求項５記載の画像復号化装置。
【請求項７】
前記復号化手段は、周辺に出現するランの長さの出現頻度に応じてテーブルを切り換えて復号化することを特徴とする請求項５または６記載の画像復号化装置。
【請求項８】
周辺画素を用いて画素値の予測を行い、予測値の当り外れを表す予測誤差データ系列を作成する予測変換ステップと、前記予測誤差データ系列のラン長をカウントするラン長カウントステップと、前記ラン長を符号化する符号化ステップとを有する画像符号化方法であって、複数の画素からなる相関の強いブロックを検出する相関ブロック検出ステップの有し、前記予測変換ステップは前記相関ブロック検出ステップによって検出されたブロック内の画素を用いて一括して前記予測変換を行うことを特徴とする画像符号化方法。
【請求項９】
前記相関ブロック検出ステップは、スクリーン周期と演算処理の単位となるビット数Ｎ（Ｎ：正の整数）の最小公倍数を用いて相関の強い画素のブロックを検出することを特徴とする請求項８記載の画像符号化方法。
【請求項１０】
前記ラン長カウントステップは、前記予測誤差データ系列において演算処理の単位となる前記Ｎビットの中に前記予測値の外れビットがあるか否かを判定するステップを有し、前記予測値の外れビットがない場合はラン長にＮを加えることを特徴とする請求項８または９記載の画像符号化方法。
【請求項１１】
前記符号化ステップは、周辺に出現するランの長さの出現頻度に応じてテーブルを切り換えて符号化することを特徴とする請求項８、９または１０記載の画像符号化方法。
【請求項１２】
復号化ステップと、前記復号化によるラン長データから予測誤差データ系列を作成する予測誤差作成ステップと、予測誤差データ系列から画素値を復元する逆予測変換ステップとを備えた画像復号化方法であって、複数の画素からなる相関の強いブロックを検出する相関ブロック検出ステップを備え、前記逆予測変換手段は前記相関ブロック検出ステップによって検出されたブロック内の画素を用いて一括して逆予測変換を行うことを特徴とする画像復号化方法。
【請求項１３】
前記相関ブロック検出ステップは、スクリーン周期と演算処理の単位となるビット数Ｎ（Ｎ：正の整数）の最小公倍数を用いて相関の強い画素のブロックを検出することを特徴とする請求項１２記載の画像復号化方法。
【請求項１４】
前記復号化ステップは、周辺に出現するランの長さの出現頻度に応じてテーブルを切り換えて復号化することを特徴とする請求項１２または１３記載の画像復号化方法。
【請求項１５】
請求項８、９、１０または１１記載の画像符号化方法を記述した制御プログラムを記憶したことを特徴とする記憶媒体。
【請求項１６】
請求項１２、１３、または１４記載の画像復号化方法を記述した制御プログラムを記憶したことを特徴とする記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は画像データを高能率に圧縮伸長する画像符号化装置、画像符号化方法、画像復号化装置、画像復号化方法、及びその記憶媒体に関するものである。
【０００２】
【従来の技術】
プリンタ、スキャナ、複写機、ファクシミリ等の高解像度化、カラー化に伴って、プリンタ、スキャナ等のデータ入出力装置、データ蓄積装置、ネットワーク通信装置などの記憶容量、伝送時間削減のためのデータ圧縮技術が重要となってきている。
【０００３】
プリンタ、複写機等のデータ出力装置で用いる一般的な画像データは２値画像である。従ってこのような２値画像に対して効率的に圧縮を行うことが重要である。２値画像としては、ディザ画像や誤差拡散画像等があり、自然画像等の中間調画像に対してこのような方式で階調変換した２値画像は、ドットの白／黒の変化が頻繁に発生する。そのため、ロスレス圧縮する場合、ランレングス符号化のような圧縮方式では長いランの発生頻度が低く圧縮効率が上がらない。ここで、スクリーンによる２値画像データやディザ画像は周期的に相関の強い画素が出現する。従って、従来は既に符号化されたこれら相関の強い画素を用いて現画素の白／黒の予測を行い（以下、予測符号化と呼ぶ）、予測の当り外れを表す予測誤差データ系列に対してランレングス符号化を行って圧縮率の向上を図っている（例えば非特許文献１参照）。
【０００４】
以下にスクリーンによる２値画像やディザ画像の符号化技術に対する従来の手法を説明する。図１０は従来の画像符号化装置を実現するための構成図、図１１は従来の画像符号化装置を実現するためのブロック図である。図１０において１００１は制御手段、１００２は２値画像データ入力手段、１００３は予測符号化における予測変換手段、１００４は予測誤差データ系列におけるランの長さをカウントするラン長カウント手段、１００５はラン長カウント手段によってカウントされたラン長を符号化する符号化手段、１００６は符号化データ出力手段、１００７は記憶手段である。以上のように構成された画像符号化装置について図１１のブロック図を用いて処理の流れを説明する。制御手段１００１はデータ入力手段１００２から入力データである２値画像データを受け取り、記憶手段１００７に記憶する。次に予測変換手段１００３は記憶手段１００７に記憶された２値画像データに対して予測符号化を行い予測誤差データ系列を作成し、記憶手段１００７に記憶する（Ｓ１１０１）。そして、ラン長カウント手段１００４は作成された予測誤差データ系列におけるランの長さをカウントする（Ｓ１１０２）。最後に符号化手段１００５はカウントされたラン長に対してエントロピー符号化を行い（Ｓ１１０３）、出力手段１００６から符号化データが出力される。また、これらの動作は記憶手段１００７に記憶された制御プログラムによって制御される場合もある。
【０００５】
また、以下にスクリーンによる２値画像やディザ画像の復号化技術に対する従来の手法を説明する。図１２は従来の画像復号化装置を実現するための構成図、図１３は従来の画像復号化装置を実現するためのブロック図である。図１２において１２０１は制御手段、１２０２は符号化データ入力手段、１２０３は符号化データの復号化手段、１２０４は予測誤差データ系列の作成手段、１２０５は予測誤差データ系列から２値画像データを復元する逆予測変換手段、１２０６は２値画像データの出力手段、１２０７は記憶手段である。以上のように構成された画像復号化装置について図１３のブロック図を用いて処理の流れを説明する。制御手段１２０１はデータ入力手段１２０２から入力データである符号化データを受け取り、記憶手段１２０７に記憶する。次に復号化手段１２０３は記憶手段１２０７に記憶された符号化データを復号化し、記憶手段１２０７に記憶する（Ｓ１３０１）。そして、予測誤差作成手段１２０４は復号化されたラン長データから予測誤差データ系列を作成し、記憶手段１２０７に記憶する（Ｓ１３０２）。次に逆予測変換手段１２０５は記憶手段１２０７に記憶された予測誤差データ系列から２値画像データを復元し、記憶手段１２０７に記憶する（Ｓ１３０３）。最後に出力手段１２０６から復号化された２値画像データが出力される。また、これらの動作は記憶手段１２０７に記憶された制御プログラムによって制御される場合もある。
【０００６】
ここで、予測変換手段１００３はスクリーンの周期やディザ画像の周期から相関の高い符号化済み画素を検出し、検出された画素値を用いて符号化対象画素の画素値を予測し、予測の当り外れのデータを作成する。一方、逆予測変換手段１２０５は同様に相関の高い復号化済み画素を検出し、検出された画素値と予測誤差データから元画像の画素値を復元する。図１４は相関の高い１画素を用いて予測符号化を行った場合の例示図である。スクリーン周期が４画素の場合、４画素前の画素と高い相関が存在する。従って４画素前の画素の値を予測値として符号化対象画素の値を予測し、予測の当り外れを表す予測誤差データを作成する。一方逆予測変換手段１２０５においては相関の高い４画素前の値を用いて予測を行い、予測誤差データとの比較により予測が当りの場合は予測値を、予測が外れの場合は予測と逆の値を実際の画素値とするような変換を行う。
【０００７】
図１５（ａ）はラン長カウント方法の例示図、図１５（ｂ）はラン長カウント方法の説明図である。ラン長カウント手段１００４は予測の当り外れを表す予測誤差データ系列からランの長さをカウントする。予測誤差データは予測当りのデータの連なりと予測外れのデータの連なりが交互に発生することから、図１５（ａ）に示すようにデータ系列の先頭が予測当りか外れか記憶しておけば、それ以降のデータについては予測の当り外れを記憶することなくその長さのみ記憶すればよい。一方、予測外れデータの出現頻度は予測当りデータの出現頻度に比べ低いことが予想されるため、図１５（ｂ）に示すように（予測当りデータの連なり）＋（予測外れデータ）によって１つのランとみなしてカウントする方法も考えられる。予測誤差生成手段１２０４は逆の手順によって復号化されたラン長データから予測誤差データ系列を作成する。
【０００８】
符号化手段１００５は予測誤差データ系列をエントロピー符号化する。符号化方法としてはＧｏｌｏｍｂ符号やＷｙｌｅ符号などの組織的な符号や、ハフマン符号化、あるいは算術符号化等が考えられる。同様に復号化手段１２０３は符号化データから予測誤差データ系列をエントロピー復号化する。
【０００９】
【非特許文献１】
吹抜敬彦、“画像のディジタル信号処理（増補版）”日刊工業新聞社、１９８７年８月５日、ｐ．２６５−２６８
【００１０】
【発明が解決しようとする課題】
しかしながら、上記従来の方法では、画素毎に予測変換を行って予測誤差データを作成して符号化する必要があり、また画素毎に逆予測変換を行って原画像の画素値を復元する必要があるため処理速度に問題があり、高速な符号化装置や復号化装置を得ることが困難であるという問題点を有していた。
【００１１】
本発明は上記従来の問題点を解決するもので、高速な画像符号化装置、画像復号化装置を提供することを目的としている。
【００１２】
【課題を解決するための手段】
上記課題を解決するために、本発明は相関の強い画素ブロックを検出し、ブロック内の画素を用いて予測変換や逆予測変換を行うようにしたもので、この方法により、ブロックの単位で予測変換や逆予測変換を行うことができるので、高速な２値画像符号化装置や２値画像復号化装置が得られる。
【００１３】
【発明の実施の形態】
本発明の請求項１に記載の発明は、周辺画素を用いて画素値の予測を行い、予測値の当り外れを表す予測誤差データ系列を作成する予測変換手段と、予測誤差データ系列のラン長をカウントするラン長カウント手段と、ラン長を符号化する符号化手段とを備えた画像符号化装置であって、複数の画素からなる相関の強いブロックを検出する相関ブロック検出手段を備え、予測変換手段は相関ブロック検出手段によって検出されたブロック内の画素を用いて一括して予測変換を行うことを特徴とする画像符号化装置で、複数の画素からなる相関の強いブロックを検出し、検出されたブロック内の画素を用いて一括して予測変換を行うことができるので、高速な画像符号化を行うことができるという作用を有する。
【００１４】
請求項２に記載の発明は、相関ブロック検出手段は、スクリーン周期と演算処理の単位となるビット数Ｎ（Ｎ：正の整数）の最小公倍数を用いて相関の強い画素のブロックを検出することを特徴とする請求項１記載の画像符号化装置で、相関の強い画素の周期と演算処理の単位となるビット数の最小公倍数を用いることにより簡単に相関の強いブロックを検出することができるので、高速な画像符号化を行うことができるという作用を有する。
【００１５】
請求項３に記載の発明は、ラン長カウント手段は、予測誤差データ系列において演算処理の単位となるＮビットの中に予測値の外れビットがあるか否かを判定する判定手段を備え、予測値の外れビットがない場合はラン長にＮを加えることを特徴とする請求項１または２記載の画像符号化装置で、高速にラン長をカウントすることができ、高速な画像符号化を行うことができるという作用を有する。
【００１６】
請求項４に記載の発明は、符号化手段は、周辺に出現するランの長さの出現頻度に応じてテーブルを切り換えて符号化することを特徴とする請求項１、２または３記載の画像符号化装置で、周辺に出現するランの長さの出現頻度に応じてテーブルを切り換えてエントロピー符号化を行うことができるので、高速に効率よい画像符号化を行うことができるという作用を有する。
【００１７】
請求項５に記載の発明は、復号化手段と、復号化によるラン長データから予測誤差データ系列を作成する予測誤差作成手段と、予測誤差データ系列から画素値を復元する逆予測変換手段とを備えた画像復号化装置であって、複数の画素からなる相関の強いブロックを検出する相関ブロック検出手段を備え、逆予測変換手段は相関ブロック検出手段によって検出されたブロック内の画素を用いて一括して逆予測変換を行うことを特徴とする画像復号化装置で、複数の画素からなる相関の強いブロックを検出し、検出されたブロック内の画素を用いて一括して逆予測変換を行うことができるので、高速な画像復号化を行うことができるという作用を有する。
【００１８】
請求項６に記載の発明は、相関ブロック検出手段は、スクリーン周期と演算処理の単位となるビット数Ｎ（Ｎ：正の整数）の最小公倍数を用いて相関の強い画素のブロックを検出することを特徴とする請求項５記載の画像復号化装置で、相関の強い画素の周期と演算処理の単位となるビット数の最小公倍数を用いることにより簡単に相関の強いブロックを検出することができるので、高速な画像復号化を行うことができるという作用を有する。
【００１９】
請求項７に記載の発明は、復号化手段は、周辺に出現するランの長さの出現頻度に応じてテーブルを切り換えて復号化することを特徴とする請求項５または６記載の画像復号化装置で、周辺に出現するランの長さの出現頻度に応じてテーブルを切り換えてエントロピー復号化を行うことができるので、高速に効率よい画像復号化を行うことができるという作用を有する。
【００２０】
請求項８に記載の発明は、周辺画素を用いて画素値の予測を行い、予測値の当り外れを表す予測誤差データ系列を作成する予測変換ステップと、予測誤差データ系列のラン長をカウントするラン長カウントステップと、ラン長を符号化する符号化ステップとを有する画像符号化方法であって、複数の画素からなる相関の強いブロックを検出する相関ブロック検出ステップの有し、予測変換ステップは相関ブロック検出ステップによって検出されたブロック内の画素を用いて一括して予測変換を行うことを特徴とする画像符号化方法で、複数の画素からなる相関の強いブロックを検出し、検出されたブロック内の画素を用いて一括して予測変換を行うことができるので、高速な画像符号化を行うことができるという作用を有する。
【００２１】
請求項９に記載の発明は、相関ブロック検出ステップは、スクリーン周期と演算処理の単位となるビット数Ｎ（Ｎ：正の整数）の最小公倍数を用いて相関の強い画素のブロックを検出することを特徴とする請求項８記載の画像符号化方法で、相関の強い画素の周期と演算処理の単位となるビット数の最小公倍数を用いることにより簡単に相関の強いブロックを検出することができるので、高速な画像符号化を行うことができるという作用を有する。
【００２２】
請求項１０に記載の発明は、ラン長カウントステップは、予測誤差データ系列において演算処理の単位となるＮビットの中に予測値の外れビットがあるか否かを判定するステップを有し、予測値の外れビットがない場合はラン長にＮを加えることを特徴とする請求項８または９記載の画像符号化方法で、高速にラン長をカウントすることができ、高速な画像符号化を行うことができるという作用を有する。
【００２３】
請求項１１に記載の発明は、符号化ステップは、周辺に出現するランの長さの出現頻度に応じてテーブルを切り換えて符号化することを特徴とする請求項８、９または１０記載の画像符号化方法で、周辺に出現するランの長さの出現頻度に応じてテーブルを切り換えてエントロピー符号化を行うことができるので、高速に効率よい画像符号化を行うことができるという作用を有する。
【００２４】
請求項１２に記載の発明は、復号化ステップと、復号化によるラン長データから予測誤差データ系列を作成する予測誤差作成ステップと、予測誤差データ系列から画素値を復元する逆予測変換ステップとを備えた画像復号化方法であって、複数の画素からなる相関の強いブロックを検出する相関ブロック検出ステップを備え、逆予測変換手段は相関ブロック検出ステップによって検出されたブロック内の画素を用いて一括して逆予測変換を行うことを特徴とする画像復号化方法で、複数の画素からなる相関の強いブロックを検出し、検出されたブロック内の画素を用いて一括して逆予測変換を行うことができるので、高速な画像復号化を行うことができるという作用を有する。
【００２５】
請求項１３に記載の発明は、相関ブロック検出ステップは、スクリーン周期と演算処理の単位となるビット数Ｎ（Ｎ：正の整数）の最小公倍数を用いて相関の強い画素のブロックを検出することを特徴とする請求項１２記載の画像復号化方法で、相関の強い画素の周期と演算処理の単位となるビット数の最小公倍数を用いることにより簡単に相関の強いブロックを検出することができるので、高速な画像復号化を行うことができるという作用を有する。
【００２６】
請求項１４に記載の発明は、復号化ステップは、周辺に出現するランの長さの出現頻度に応じてテーブルを切り換えて復号化することを特徴とする請求項１２または１３記載の画像復号化方法で、周辺に出現するランの長さの出現頻度に応じてテーブルを切り換えてエントロピー復号化を行うことができるので、高速に効率よい画像復号化を行うことができるという作用を有する。
【００２７】
（実施の形態１）
以下、本発明の実施の形態１について説明する。図１は本発明の実施の形態１における画像符号化装置を実現するための構成図を、図２は本発明の実施の形態１における画像符号化装置を実現するためのブロック図を表している。図１６は相関ブロックの検出方法の例示図、図１７は相関ブロックを用いた予測符号化の例示図である。
【００２８】
図１において１０１は画像データに施す処理を制御する制御手段、１０２は２値画像データの入力手段、１０３は複数の画素からなる相関の強いブロックを検出する相関ブロック検出手段、１０４は予測符号化における予測変換手段、１０５は予測誤差データ系列におけるランの長さをカウントするラン長カウント手段、１０６はラン長カウント手段によってカウントされたラン長を符号化する符号化手段、１０７は符号化データの出力手段、１０８は制御プログラムや画像データを記憶する記憶手段である。
【００２９】
以上のように構成された画像符号化装置について、以下、図２のブロック図を用いて処理の流れを説明する。最初に制御手段１０１は入力手段１０２から入力画像である２値画像データを受け取り、記憶手段１０８に記憶する。次に相関ブロック検出手段１０３は、記憶手段１０８に記憶された２値画像データにおいて複数の画素からなる符号化対象ブロックに対して相関の強いブロックを検出する（Ｓ２０１）。そして予測変換手段１０４は検出されたブロック内の画素を用いて符号化対象ブロックの予測変換を行い予測誤差データ系列を作成し、記憶手段１０８に記憶する（Ｓ２０２）。次にラン長カウント手段１０５は作成された予測誤差データ系列におけるランの長さをカウントする（Ｓ２０３）。最後に符号化手段１０６はカウントされたラン長に対してエントロピー符号化を行い（Ｓ２０４）、出力手段１０７から符号化データが出力される。また、これらの動作は記憶手段１０８に記憶された制御プログラムによって制御される場合もある。
【００３０】
相関ブロック検出手段１０３は、複数の画素からなる符号化対象ブロックに対して相関の強いブロックを検出する。スクリーン周期が１０画素の場合、符号化対象ブロック１０画素に対して、直前の１０画素が相関の強いブロックとなるが、演算処理を高速に行うために、スクリーン周期と演算処理単位の最小公倍数を用いて相関の強いブロックを検出する場合も考えられる。例えば図１６に示すようにスクリーンの周期が６画素ピッチの２値画像データに対して、演算処理単位が８ビットの場合、その最小公倍数は２４となる。従って８画素からなる符号化対象ブロックに対して２４画素前の８画素ブロックは相関が高いブロックとなり、相関ブロック検出手段はそのような画素からなるブロックを検出する。また、このような検出手段はスクリーン周期が必要となるが、画像全体に渡って同一のスクリーンの場合、スクリーン周期は固定値であるため、ある定まったスクリーン周期を用いて相関ブロックを検出することができる。一方、領域毎にスクリーン周期が変わる場合、あるいはハッチパターン等がレンダリングされていてスクリーン周期に依存しない周期的なパターンが出現する場合は途中で周期が切り替わったことを識別する必要がある。どこで周期が切り替わるかが分かっている場合は、切り替わりの場所で新しい周期から相関ブロックを検出し、その周期及びその周期がどこまで続くかを示す情報を符号化手段において符号化データに組み込むことも考えられる。あるいは符号化対象周辺の符号化済みデータにおける統計的なデータから相関の強い周期を求め、求めた周期から相関ブロックを検出する場合もある。この場合も求めた周期及びその周期がどこまで続くかを表す情報を符号化データに組み込む場合も考えられるし、復号化手段において復号化対象周辺の復号化済みデータにおける統計的なデータから相関の強い周期を求めることにより符号化データには組み込まない方法も考えられる。この場合、復号化時の周期を求める方法は符号化時と同一の画素を用いて同一のロジックで行う必要がある。
【００３１】
予測変換手段１０４は相関ブロック検出手段１０３によって検出された相関の強いブロック内の画素を用いて予測変換を行う。２値画像データの予測は論理演算で実現可能であり、例えば図１７に示すように演算処理単位が８ビットの場合、符号化対象の８画素ブロックと２４画素前の８画素ブロックとの排他的論理和を演算することにより８画素同時に予測変換を行う方法が考えられる。スクリーン周期のみから相関の強いブロックを検出した場合においても同様に排他的論理和を演算し、複数の画素を同時に予測変換する方法が考えられる。
【００３２】
ラン長カウント手段１０５は予測誤差データ系列のランの長さをカウントする。ここで、予測当たりが０、予測外れが１の場合、予測が当たり続けると予測誤差データ系列は０のビットが連続して出現する。従って演算処理単位が８ビットの場合１バイト（８ビット）単位に０か否かの判定を行い、０の場合はランのカウント数に８加えることで８画素（８ビット）分、一括してカウントすることが可能となり、処理の高速化を図ることができる。
【００３３】
符号化手段１０６はラン長データをエントロピー符号化する。符号化方法としてはＧｏｌｏｍｂ符号やＷｙｌｅ符号等の組織的な符号を用いる場合も考えられるし、ハフマン符号化や算術符号化を用いる場合も考えられる。また、エントロピー符号化を行う際に、周辺に出現するランの長さを記憶し、出現頻度に応じてそれぞれ最適化されたテーブルを用いて符号化を行う方法も考えられる。この場合、周辺に出現する複数のラン長の和を用いてクラス分けし、各クラスに最適なテーブルを用いる場合も考えられるし、周辺の複数のラン長を量子化し、量子化された複数のラン長の値でクラス分けし、各クラスに最適なテーブルを用いる場合も考えられる。
【００３４】
次に、図３は本発明の実施の形態１における画像復号化装置を実現するための構成図、図４は本発明の実施の形態１における画像復号化装置を実現するためのブロック図を表している。
【００３５】
図３において３０１は画像データに施す処理を制御する制御手段、３０２は符号化データの入力手段、３０３は複数の画素からなる相関の強いブロックを検出する相関ブロック検出手段、３０４は符号化データからラン長データを復号化する復号化手段、３０５は復号化されたラン長データから予測誤差データ系列を作成する予測誤差作成手段、３０６は予測誤差データ系列から２値画像データを復元する逆予測変換手段、３０７は復号化された２値画像データの出力手段、３０８は制御プログラムや画像データを記憶する記憶手段である。
【００３６】
以上のように構成された画像復号化装置について、以下、図４のブロック図を用いて処理の流れを説明する。最初に制御手段３０１は入力手段３０２から入力データである符号化データを受け取り記憶手段３０８に記憶する。次に復号化手段３０４は記憶手段３０８に記憶された符号化データを復号化し、記憶手段３０８に記憶する（Ｓ４０１）。そして、予測誤差作成手段３０５は復号化されたラン長データから予測誤差データ系列を作成し、記憶手段３０８に記憶する（Ｓ４０２）。次に相関ブロック検出手段３０３は、記憶手段３０８に記憶された予測誤差データにおいて複数の画素からなる符号化対象ブロックに対して相関の強いブロックを検出する（Ｓ４０３）。そして、逆予測変換手段３０６は検出された相関の強いブロック内の画素と記憶手段３０８に記憶された予測誤差データ系列を用いて符号化対象ブロックの画素値を復元する逆予測変換を行い、記憶手段３０８に記憶する（Ｓ４０４）。最後に出力手段３０７から復号化された２値画像データが出力される。また、これらの動作は記憶手段３０８に記憶された制御プログラムによって制御される場合もある。
【００３７】
相関ブロック検出手段３０３は符号化時に用いた周期を検出する手段であり、符号化時に用いた相関ブロックまでの周期を符号化している場合は復号化手段３０４において復号化された周期から相関ブロックの周期を検出する。一方、符号化時に周期を符号化していない場合は、符号化時と同じように復号化対象周辺の復号化済みデータにおける統計的なデータから相関の強い周期を求める。この場合は符号化時に相関の強い周期を求めたときと同じロジックによって求めることにより、周期データを符号化することなしに復号化を行うことができるようになる。
【００３８】
図５，図６は本発明の実施の形態１における画像符号化装置、画像復号化装置を実現するためのハードウェア構成図を表している。図５において５０１は外部記憶装置、５０２は中央演算処理装置（以下「ＣＰＵ」と略称する）、５０３はリードオンリーメモリ（以下「ＲＯＭ」と略称する）、５０４はランダムアクセスメモリ（以下「ＲＡＭ」と略称する）でそれぞれがバス結合されている。ＲＯＭ５０３内にはプログラムの記憶領域があり、ＲＡＭ５０４内には画像記憶領域がある。図５は組込み機器のハードウェア構成図であるが、汎用機器で本実施の形態を実現する場合は図６に示すように外部記憶装置６０１内にプログラムの記憶領域がある場合もある。ここで、外部記憶装置としてはハードディスク、フロッピー（Ｒ）ディスク、ＣＤ−ＲＯＭ、ＭＯ等がある。また、外部記憶装置はネットワーク等によって接続されている場合もある。
【００３９】
図７は本発明の実施の形態１における画像符号化方法を実現するためのフローチャートを表している。以下に図７を用いて処理の流れを説明する。
【００４０】
図７において外部記憶装置５０１等に記憶されている画像データがＲＡＭ５０４の画像記憶領域に入力された後、Ｓ７０１では符号化対象ブロック番号、ラン長を０に初期化し、符号化対象ブロックと相関の強いブロックとのアドレス距離をオフセットとして設定する。例えば１画素１ビットの２値画像でスクリーン周期が１０画素、演算処理単位が８ビットの場合、１０と８の最小公倍数の４０ビット（８バイト）がオフセットとなる。また、符号化対象ブロックのアドレスにはＲＡＭ５０４に記憶された画像データの先頭ブロックのアドレスを、相関ブロックのアドレスには符号化対象ブロックのアドレスからオフセットを引いたアドレスを設定する。次にＳ７０２では符号化対象ブロック番号がオフセットの値より小さいか否かを判定し処理の分岐を行う。符号化対象ブロック番号がオフセットより小さい場合はＳ７０３において符号化対象に符号化対象ブロックをセットする。一方Ｓ７０２において符号化対象ブロック番号がオフセットより大きい場合はＳ７０４において符号化対象ブロックと相関ブロックの排他的論理和（ＸＯＲ）をとり、その結果を符号化対象にセットする。Ｓ７０５ではセットされた符号化対象ブロックに対して上位ビットから順番にビットが０か否か判定する。値が０のビットが出現した場合はＳ７０６でラン長に１を加える。一方、値が１のビットが出現した場合はＳ７０７でラン長のエントロピー符号化を行う。符号化方法としてはＧｏｌｏｍｂ符号やＷｙｌｅ符号等の組織的な符号を用いる場合も考えられるし、ハフマン符号化や算術符号化を用いる場合も考えられる。符号化されたデータはＲＡＭ５０４に格納される。そしてＳ７０８ではラン長を０にリセットする。Ｓ７０９では全ビットの判定が終了しているかどうかの判定を行い、終了していない場合はＳ７１０に、終了している場合はＳ７１１に進む。Ｓ７１０では判定対象のビットを１ビット下位のビットにシフトしてＳ７０５からの処理を全ビット終了まで繰り返す。符号化対象ブロックの全ビットの処理が終了したらＳ７１１に進み、符号化対象ブロック番号、符号化対象ブロックのアドレス、相関ブロックのアドレスをインクリメントする。そしてＳ７１２では符号化対象ブロック番号が符号化対象ブロック数より小さい場合はＳ７０２に戻って全符号化対象ブロックが終了するまでＳ７０２からＳ７１２までの処理を繰り返す。全符号化対象ブロックが終了している場合は処理を終了する。最後に作成された圧縮データは外部記憶装置５０１等に記憶されるか、ネットワークを介して外部に送信される。また、上述の処理はＣＰＵ５０２を用いて行う。
【００４１】
図８は本発明の実施の形態１における画像復号化方法を実現するためのフローチャートを表している。以下に図８を用いて処理の流れを説明する。
【００４２】
図８において外部記憶装置５０１に記憶されている符号化データがＲＡＭ５０４に入力された後、Ｓ８０１では出力ブロック番号、ラン長を０に初期化し、出力ブロックと相関の強いブロックとのアドレス距離をオフセットとして設定する。ここでのオフセットは符号化時に設定したオフセットと同一の値である必要がある。また、出力ブロックのアドレスにはＲＡＭ５０４上の画像出力領域の先頭アドレスを、相関ブロックのアドレスには出力ブロックのアドレスからオフセットを引いたアドレスを設定する。次にＳ８０２ではエントロピー復号化によりラン長を取得する。そしてＳ８０３では復号化したラン長をラン長の値に加え、復号化データである予測の当たり外れを表す予測誤差データを作成する。次にＳ８０４ではラン長と出力ブロックサイズとに比較を行い、ラン長が出力ブロックサイズより大きい場合はＳ８０５に進み、小さい場合はＳ８１０に進む。ここで出力ブロックサイズは演算処理単位が８ビットの場合は８となる。Ｓ８０５では出力ブロック番号とオフセットの比較を行い、オフセットのほうが大きい場合はＳ８０６に進み、小さい場合はＳ８０７に進む。Ｓ８０６では復号化データの上位ビットを出力ブロックサイズ分出力対象として設定し、一方Ｓ８０７では復号化データの上位ビット（出力ブロックサイズ分）と相関ブロック（出力ブロックサイズ分）との排他的論理和（ＸＯＲ）を出力対象に設定する。Ｓ８０８では出力対象を画像出力領域である出力ブロックに出力し、ラン長から出力ブロックサイズを引く。更に出力ブロックと相関ブロックのアドレスをインクリメントする。演算処理単位が８ビットの場合、出力ブロックサイズは８となりアドレスは８ビット（１バイト）分インクリメントされることになる。Ｓ８０９ではラン長と出力ブロックサイズの比較を行い、ラン長が大きい場合はＳ８０５に進み、Ｓ８０５からＳ８０８までの処理を繰り返す。ラン長が小さい場合はＳ８１０に進む。Ｓ８１０では全出力ブロックの出力が終了しているかどうかの判定を行い、終了していない場合はＳ８０２に進んで、次のランの復号化を行う。一方全出力ブロックの出力が終了している場合は処理を終了する。最後に復号化された画像データは外部記憶装置５０１等に記憶されるか、ネットワークを介して外部に送信される。また、上述の処理はＣＰＵ５０２を用いて行う。
【００４３】
また、図９は、各種データ処理プログラムを格納する記憶媒体のメモリマップの説明図である。
【００４４】
なお、特に図示しないが、記憶媒体に記憶されるプログラム群を管理する情報、例えばバージョン情報、作成者等も記憶され、かつ、プログラム読み出し側のＯＳ等に依存する情報、例えばプログラムを識別表示するアイコン等も記憶される場合もある。
【００４５】
さらに、各種プログラムに従属するデータも上記ディレクトリに管理されている。また、各種プログラムをコンピュータにインストールするためのプログラムや、インストールするプログラムが圧縮されている場合に、解凍するプログラム等も記憶される場合もある。
【００４６】
実施の形態１における図７、図８に示す機能が外部からインストールされるプログラムによって、ホストコンピュータにより遂行されていてもよい。そして、その場合、ＣＤ−ＲＯＭやフラッシュメモリやＦＤ等の記憶媒体により、あるいはネットワークを介して外部の記憶媒体から、プログラムを含む情報群を出力装置に供給される場合でも本発明は適用されるものである。
【００４７】
以上のように、前述した実施の形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読み出し実行することによっても、本発明の目的が達成されることは言うまでもない。
【００４８】
この場合、記憶媒体から読み出されたプログラムコード自体が本発明の新規な機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【００４９】
プログラムコードを供給するための記憶媒体としては、例えば、フロッピー（Ｒ）ディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード、ＲＯＭ、ＥＥＰＲＯＭ等を用いることができる。
【００５０】
また、コンピュータが読み出したプログラムコードを実行することにより、前述した実施の形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているＯＳ（オペレーティングシステム）等が実際の処理の一部または全部を行い、その処理によって前述した実施の形態の機能が実施される場合も含まれることは言うまでもない。
【００５１】
さらに、記憶媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵ等が実際の処理の一部または全部を行い、その処理によって前述した実施の形態の機能が実現される場合も含まれることは言うまでもない。
【００５２】
【発明の効果】
以上のように本発明によれば、周辺画素を用いて画素値の予測を行い、予測値の当り外れを表す予測誤差データ系列を作成する予測変換手段と、前記予測誤差データ系列のラン長をカウントするラン長カウント手段と、前記ラン長を符号化する符号化手段とを備えた画像符号化装置であって、複数の画素からなる相関の強いブロックを検出する相関ブロック検出手段を備え、前記予測変換手段は前記相関ブロック検出手段によって検出されたブロック内の画素を用いて一括して前記予測変換を行うことを特徴とする画像符号化装置であって、複数の画素からなる相関の強いブロックを検出し、検出されたブロック内の画素を用いて一括して予測変換を行うことができるので、高速な画像符号化装置を実現することができる。
【００５３】
また、前記相関ブロック検出手段は、スクリーン周期と演算処理の単位となるビット数Ｎ（Ｎ：正の整数）の最小公倍数を用いて相関の強い画素のブロックを検出するようにしたので、相関の強い画素の周期と演算処理の単位となるビット数の最小公倍数を用いることにより簡単に相関の強いブロックを検出することができるので、高速な画像符号化装置を実現することができる。
【００５４】
また、前記ラン長カウント手段は、前記予測誤差データ系列において演算処理の単位となる前記Ｎビットの中に前記予測値の外れビットがあるか否かを判定する判定手段を備え、前記予測値の外れビットがない場合はラン長にＮを加えるようにしたので、高速にラン長をカウントすることができ、高速な画像符号化を実現することができる。
【００５５】
また、前記符号化手段は、周辺に出現するランの長さの出現頻度に応じてテーブルを切り換えて符号化するようにしたので、周辺に出現するランの長さの出現頻度に応じてテーブルを切り換えてエントロピー符号化を行うことができる、高速で効率よい画像符号化装置を実現することができる。
【００５６】
また、復号化手段と、前記復号化によるラン長データから予測誤差データ系列を作成する予測誤差作成手段と、予測誤差データ系列から画素値を復元する逆予測変換手段とを備えた画像復号化装置であって、複数の画素からなる相関の強いブロックを検出する相関ブロック検出手段を備え、前記逆予測変換手段は前記相関ブロック検出手段によって検出されたブロック内の画素を用いて一括して逆予測変換を行うことを特徴とする画像復号化装置であって、複数の画素からなる相関の強いブロックを検出し、検出されたブロック内の画素を用いて一括して逆予測変換を行うようにしたので、高速な画像復号化装置を実現することができる。
【００５７】
また、前記相関ブロック検出手段は、スクリーン周期と演算処理の単位となるビット数Ｎ（Ｎ：正の整数）の最小公倍数を用いて相関の強い画素のブロックを検出するようにしたので、相関の強い画素の周期と演算処理の単位となるビット数の最小公倍数を用いることにより簡単に相関の強いブロックを検出することができ、高速な画像復号化装置を実現することができる。
【００５８】
また、前記復号化手段は、周辺に出現するランの長さの出現頻度に応じてテーブルを切り換えて復号化するようにしたので、前記復号化手段は、周辺に出現するランの長さの出現頻度に応じてテーブルを切り換えて復号化することができ、高速に効率よい画像復号化装置を実現することができる。
【図面の簡単な説明】
【図１】本発明の実施の形態１における画像符号化装置を実現するための構成図
【図２】本発明の実施の形態１における画像符号化装置を実現するためのブロック図
【図３】本発明の実施の形態１における画像復号化装置を実現するための構成図
【図４】本発明の実施の形態１における画像復号化装置を実現するためのブロック図
【図５】本発明の実施の形態１における画像符号化装置、画像復号化装置を実現するためのハードウェア構成図
【図６】本発明の実施の形態１における画像符号化装置、画像復号化装置を実現するためのハードウェア構成図
【図７】本発明の実施の形態１における画像符号化方法を実現するためのフローチャート
【図８】本発明の実施の形態１における画像復号化方法を実現するためのフローチャート
【図９】各種データ処理プログラムを格納する記憶媒体のメモリマップの説明図
【図１０】従来の画像符号化装置を実現するための構成図
【図１１】従来の画像符号化装置を実現するためのブロック図
【図１２】従来の画像復号化装置を実現するための構成図
【図１３】従来の画像復号化装置を実現するためのブロック図
【図１４】相関の高い１画素を用いて予測符号化を行った場合の例示図
【図１５】（ａ）ラン長カウント方法の例示図
（ｂ）ラン長カウント方法の説明図
【図１６】相関ブロックの検出方法の例示図
【図１７】相関ブロックを用いた予測符号化の例示図
【符号の説明】
１０１  制御手段
１０２  入力手段
１０３  相関ブロック検出手段
１０４  予測変換手段
１０５  ラン長カウント手段
１０６  符号化手段
１０７  出力手段
１０８  記憶手段
３０１  制御手段
３０２  入力手段
３０３  相関ブロック検出手段
３０４  復号化手段
３０５  予測誤差作成手段
３０６  逆予測変換手段
３０７  出力手段
３０８  記憶手段
５０１  外部記憶装置
５０２  中央演算処理装置（ＣＰＵ）
５０３  リードオンリーメモリ（ＲＯＭ）
５０４  ランダムアクセスメモリ（ＲＡＭ）
６０１  外部記憶装置
６０２  中央演算処理装置
６０３  リードオンリーメモリ
６０４  ランダムアクセスメモリ
１００１  制御手段
１００２  入力手段
１００３  予測変換手段
１００４  ラン長カウント手段
１００５  符号化手段
１００６  出力手段
１００７  記憶手段
１２０１  制御手段
１２０２  入力手段
１２０３  復号化手段
１２０４  予測誤差作成手段
１２０５  逆予測変換
１２０６  出力手段
１２０７  記憶手段
【図１】
2004172709.tif 000003
【図２】
2004172709.tif 000004
【図３】
2004172709.tif 000005
【図４】
2004172709.tif 000006
【図５】
2004172709.tif 000007
【図６】
2004172709.tif 000008
【図７】
2004172709.tif 000009
【図８】
2004172709.tif 000010
【図９】
2004172709.tif 000011
【図１０】
2004172709.tif 000012
【図１１】
2004172709.tif 000013
【図１２】
2004172709.tif 000014
【図１３】
2004172709.tif 000015
【図１４】
2004172709.tif 000016
【図１５】
2004172709.tif 000017
【図１６】
2004172709.tif 000018
【図１７】
2004172709.tif 000019