(57)【要約】【課題】辞書に基づいた符号化方式を用いて、圧縮率をより向上させること。【解決手段】辞書に基づいた符号化方式で１次元データ列を符号化する符号化装置で符号化するための１次元データ列を出力する符号化前処理装置であって、複数の画素データが行列状に配列された画像データを記憶する記憶部（Ｓ１１）と、記憶された画像データを、辞書に相当する参照される画素データの数以下の画素データを含む予め定められた形状の矩形領域に分割する分割部（Ｓ１２）と、隣接する矩形領域を順に所定方向に読出す読出部（Ｓ１３）と、読出された矩形領域に含まれる画素データを、予め定められた順番で部分画素データ列として１次元に配列する配列部（Ｓ１４）と、配列された部分画素データ列を、矩形領域が読出された順番で出力する出力部（Ｓ１５）とを備える。【選択図】        図４
2004215173.tif 000002
【特許請求の範囲】
【請求項１】
辞書に基づいた符号化方式で１次元データ列を符号化する符号化装置で符号化するための前記１次元データ列を出力する符号化前処理装置であって、
複数の画素データが行列状に配列された画像データを記憶する記憶手段と、
前記記憶された画像データを、前記辞書に相当する参照される画素データの数以下の画素データを含む予め定められた形状の矩形領域に分割する分割手段と、
隣接する矩形領域を順に所定方向に読出す読出手段と、
前記読出された矩形領域に含まれる画素データを、予め定められた順番で部分画素データ列として１次元に配列する配列手段と、
前記配列された部分画素データ列を、前記矩形領域が読出された順番で出力する出力手段とを備えた、符号化前処理装置。
【請求項２】
前記矩形領域が読出される方向は、矩形領域が長辺で隣接する矩形領域に向かう方向である、請求項１に記載の符号化前処理装置。
【請求項３】
前記分割手段は、前記辞書に基づいた符号化方式で符号化対象となる画素データの数以下の画素データを含む予め定められた形状の矩形領域に分割する、請求項１に記載の符号化前処理装置。
【請求項４】
辞書に基づいた符号化方式で１次元データ列を符号化する符号化装置で符号化するための前記１次元データ列を出力する符号化前処理装置であって、
複数の画素データが行列状に配列された画像データを記憶する記憶手段と、
前記記憶された画像データから、前記辞書に相当する参照される画素データの数以下の画素データを含むラインを、前記ラインが垂直方向に隣接するラインに向かう方向に順に読出す読出手段と、
前記読出されたラインに含まれる部分画素データ列を、前記ラインが読出された順番で出力する出力手段とを備えた、符号化前処理装置。
【請求項５】
辞書に基づいた符号化方式で複数の画素データが行列状に配列された画像データを符号化する符号化装置であって、
前記画像データを記憶する記憶手段と、
前記記憶された画像データを、前記辞書に相当する参照される画素データの数以下の画素データを含む予め定められた形状の矩形領域に分割する分割手段と、
隣接する矩形領域を順に所定方向に読出す読出手段と、
前記読出された矩形領域に含まれる画素データを、予め定められた順番で部分画素データ列として１次元に配列する配列手段と、
前記配列された部分画素データ列を、前記矩形領域が読出された順番で全画素データ列として出力する出力手段と、
前記辞書に基づいた符号化方式で、前記出力された全画素データ列を符号化する符号化手段とを備えた、画像符号化装置。
【請求項６】
前記記憶された画像データを、隣接する複数の前記矩形領域からなるブロックに分割するブロック分割手段をさらに備え、
前記符号化手段は、前記分割されたブロックごとに、前記全画素データ列を符号化する、請求項５に記載の画像符号化装置。
【請求項７】
辞書に基づいた符号化方式で複数の画素データが行列状に配列された画像データを符号化する符号化装置であって、
前記画像データを記憶する記憶手段と、
前記記憶された画像データを、前記辞書に相当する参照される画素データの数以下の画素データを含む予め定められた第１の形状の矩形領域に分割する第１分割手段と、
隣接する第１の形状の矩形領域を順に第１の方向に読出す第１読出手段と、
前記読出された第１の形状の矩形領域に含まれる画素データを、予め定められた順番で第１の部分画素データ列として１次元に配列する第１配列手段と、
前記配列された第１の部分画素データ列を、前記第１の形状の矩形領域が読出された順番で第１の全画素データ列として出力する第１出力手段と、
前記辞書に基づいた符号化方式で、前記出力された第１の全画素データ列を、第１の符号化データ列として符号化する第１符号化手段と、
前記記憶された画像データを、前記辞書に相当する参照される画素データの数以下の画素データを含む予め定められた第２の形状の矩形領域に分割する第２分割手段と、
隣接する第２の形状の矩形領域を順に第２の方向に読出す第２読出手段と、
前記読出された第２の形状の矩形領域に含まれる画素データを、予め定められた順番で第２の部分画素データ列として１次元に配列する第２配列手段と、
前記配列された第２の部分画素データ列を、前記第２の形状の矩形領域が読出された順番で第２の全画素データ列として出力する第２出力手段と、
前記辞書に基づいた符号化方式で、前記出力された第２の全画素データ列を、第２の符号化データ列として符号化する第２符号化手段と、
前記符号化された第１の符号化データ列のデータ長と、前記符号化された第２の符号化データ列のデータ長とを比較する比較手段と、
前記比較されたデータ長が短い符号化データ列を、出力するための符号化データ列として選択する選択手段とを備えた、画像符号化装置。
【請求項８】
前記記憶された画像データをブロックに分割するブロック分割手段をさらに備え、
前記ブロックは、隣接する複数の前記第１の形状の矩形領域で構成されるとともに、隣接する複数の前記第２の形状の矩形領域で構成され、
前記第１符号化手段および前記第２符号化手段は、前記分割されたブロックごとに、それぞれ、前記出力された第１の全画素データ列および前記出力された第２の全画素データ列を符号化する、請求項７に記載の画像符号化装置。
【請求項９】
請求項６に記載の画像符号化装置により、画像データがブロックごとに、辞書に基づいた符号化方式で符号化された符号化データ列を復号して画像データを復元する画像復号装置であって、
前記画像データのうち、復元する前記ブロックの指定を受付ける指定受付手段と、
前記符号化データ列のうち、前記指定されたブロックに対応するブロック符号化データ列を読出す読出手段と、
辞書に基づいた符号化方式の復号方法で、前記読出されたブロック符号化データ列をブロック画素データ列として復号する復号手段と、
前記復号されたブロック画素データ列に含まれる画素データを所定数ごとに予め定められた順番で配列して、予め定められた形状の矩形領域を順次復元する矩形領域復元手段と、
前記順次復元された矩形領域を復元された順に所定方向に隣接するように配列して前記指定されたブロックの画像データを復元する画像データ復元手段とを備えた、画像復号装置。
【請求項１０】
辞書に基づいた符号化方式で１次元データ列を符号化する符号化装置で符号化するための前記１次元データ列をコンピュータで出力する符号化前処理方法であって、
複数の画素データが行列状に配列された画像データを記憶するステップと、
前記記憶された画像データを、前記辞書に相当する参照される画素データの数以下の画素データを含む予め定められた形状の矩形領域に分割するステップと、
隣接する矩形領域を順に所定方向に読出すステップと、
前記読出された矩形領域に含まれる画素データを、予め定められた順番で部分画素データ列として１次元に配列するステップと、
前記配列された部分画素データ列を、前記矩形領域が読出された順番で出力するステップとを含む、符号化前処理方法。
【請求項１１】
辞書に基づいた符号化方式で１次元データ列を符号化する符号化装置で符号化するための前記１次元データ列を出力するコンピュータで実行される符号化前処理プログラムであって、
複数の画素データが行列状に配列された画像データを記憶するステップと、
前記記憶された画像データを、前記辞書に相当する参照される画素データの数以下の画素データを含む予め定められた形状の矩形領域に分割するステップと、
隣接する矩形領域を順に所定方向に読出すステップと、
前記読出された矩形領域に含まれる画素データを、予め定められた順番で部分画素データ列として１次元に配列するステップと、
前記配列された部分画素データ列を前記矩形領域が読出された順番で出力するステップとを前記コンピュータに実行させる、符号化前処理プログラム。
【請求項１２】
請求項１１に記載の符号化前処理プログラムを記録したコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、符号化前処理装置、画像符号化装置、画像復号装置、符号化前処理方法、符号化前処理プログラム、符号化前処理プログラムを記録したコンピュータ読取可能な記録媒体に関し、特に、画像データを効率よく符号化するのに適した符号化前処理装置、画像符号化装置、画像復号装置、符号化前処理方法、符号化前処理プログラム、符号化前処理プログラムを記録したコンピュータ読取可能な記録媒体に関する。
【０００２】
【従来の技術】
従来、２次元データである画像データを１次元データ列に変換して、汎用的な１次元データ列の符号化アルゴリズムを用いて、１次元データ列に変換された画像データを符号化することにより、画像データの符号化が行なわれていた。
【０００３】
また、特開平９−２８９５９１号公報に記載されている画像符号化装置によれば、２値画像データを各ライン単位で走査し、１次元データに変換し、ＰａｃｋＢｉｔｓ方式などのランレングス符号化方式で符号化するとともに、画像の相関を利用して符号化することにより、画像データの符号化が行なわれる。このため、２値画像のような、同一階調の画素が連続することが多い画像においては、圧縮率がよくなる。一方、写真画像のような多値画像として表現される画像では、同一階調の画素が連続することが少ないので、ランレングス符号化方式を用いた場合、画像データがほとんど圧縮されないことがある。また、写真画像では、同一階調の画素が１ラインすべてに亘って連続することは少なく、また、隣接する２つのライン全体が同一であることも少ないので、画像の相関を利用できることが少なくなる。
【０００４】
ここで、画像データを各ライン単位で走査し、１次元データ列に変換し、ＬＺ７７などの辞書に基づいた符号化方式を用いて符号化することを考える。図１７は、画像データの各ライン単位での走査を説明するための図である。図１７（ａ）は、画像データを示す図である。図１７（ａ）を参照して、画像データは、画像を表現するためのデータであり、複数の画素データａ１１〜ａｍｎがｍ×ｎの２次元に配列されたデータである。画素データは、画像を構成する最小の単位要素である画素を表現するためのデータであり、たとえば、画素の色の明度、色相、および、彩度を表現する階調データである。具体的に、色相および彩度が一定で、２５６段階の明度を表現するためには、１画素当たり８ビットの情報量が必要であるので、１つの画素データを表現する情報量が８ビットとなる。
【０００５】
画像データを各ライン単位で走査するとは、まず、画像データの１番目のライン１１に含まれる画素データａ１１〜ａ１ｎを左から順に読出し、次に、画像データの２番目のライン１２に含まれる画素データａ２１〜ａ２ｎを左から順に読出し、同様に３番目のライン１３からｍ番目のライン１４までに含まれる画素データを読出すことである。図１７（ｂ）は、変換された１次元データ列２１を示す図である。図１７（ｂ）を参照して、１番目のライン１１に含まれる画素データａ１１〜ａ１ｎ、２番目のライン１２に含まれる画素データａ２１〜ａ２ｎ、３番目のライン１３に含まれる画素データａ３１〜ａ３ｎ、…、ｍ番目のライン１４に含まれる画素データａｍ１〜ａｍｎの順で１次元データ列２１に変換される。
【０００６】
図１８は、辞書に基づいた符号化方式を説明するための図である。図１８（ａ）は、符号化前の１次元データ列２２を示す図である。ＬＺ７７などの辞書に基づいた符号化方式は、このような１次元データ列２２を所定の辞書に基づき符号化するための方式である。ここで、１次元データ列２２は、ｌ個の画素データｂ０〜ｂ（ｌ−１）からなるデータ列である。
【０００７】
図１８（ｂ）は、符号化部２５の先頭のデータ列が参照部２４に含まれるデータ列と一致する場合について説明するための図である。ＬＺ７７などの辞書に基づいた符号化方式を用いた符号化においては、辞書に相当するＮ個のデータを含むデータ列からなり符号化時に参照される参照部２４と、参照部より少ないＦ個のデータを含むデータ列から成りそのデータ列の一部または全部が符号化の対象となる符号化部２５とからなるスライド窓を１次元データ列２２の先頭から順次スライドさせながら、符号化が行なわれる。
【０００８】
そして、符号化部２５の先頭のｐ個のデータ列｛ｂｊ，…，ｂ（ｊ＋ｐ−１）｝が、参照部に含まれるデータ列｛ｂｉ，…，ｂ（ｉ＋ｐ−１）｝と一致する場合は、参照部に含まれる同一のデータ列｛ｂｉ，…，ｂ（ｉ＋ｐ−１）｝を指示する符号、たとえば、そのデータ列｛ｂｉ，…，ｂ（ｉ＋ｐ−１）｝の参照部中での位置ｍと、そのデータ列｛ｂｉ，…，ｂ（ｉ＋ｐ−１）｝の長さｐと、一致しない最初のデータｂ（ｊ＋ｐ）とを示す符号化データ「ｍｐｂ（ｊ＋ｐ）」で、符号化部２５の先頭の（ｐ＋１）個のデータ列｛ｂｊ，…，ｂ（ｊ＋ｐ−１）｝を符号化する。
【０００９】
ここで、参照部の大きさＮを１０２４ビットとすると、位置ｍおよび長さｐは、それぞれ１２ビットの情報量で表現することができる。また、１次元データ列２２に含まれるデータｂ０〜ｂ（ｌ−１）が、それぞれ、８ビットで表現できるとする。この場合、符号化データ「ｍｐｂ（ｊ＋ｐ）  」は３２ビットで表現することができる。ｐ＝３個以上のデータ列が一致するとき、符号化されるデータ列の情報量は、３２ビット（＝（ｐ＋１）個×８）ビット以上となる。このため、３個以上のデータ列が一致する場合は、符号化後の符号化データの情報量が、符号化前のデータ列の情報量よりも小さくなるので、符号化されたときのデータの圧縮率がよくなる。
【００１０】
図１８（ｃ）は、一致するデータ列を符号化した後の参照部２４ａおよび符号化部２５ａの状態を示す図である。図１８（ｃ）を参照して、符号化部２５の先頭の（ｐ＋１）個のデータ列｛ｂｊ，…，ｂ（ｊ＋ｐ）｝が符号化された後、参照部２４および符号化部２５を含むスライド窓が１次元データ列２２の後方に、（ｐ＋１）個のデータ分、スライドされる。そして、符号化されたデータ列｛ｂｊ，…，ｂ（ｊ＋ｐ）｝が参照部２４ａに入り、新たな符号化部２５ａに含まれるデータ列｛ｂ（ｊ＋ｐ＋１），…，ｂ（ｋ＋ｐ）｝が次の符号化の対象となる。
【００１１】
図１８（ｄ）は、符号化部２５ｂの先頭のデータ列が参照部２４ｂに含まれるデータ列と一致しない場合について説明するための図である。この場合は、符号化部２４ｂの先頭のデータｂｊそのものを示す符号、たとえば、参照部に一致するデータ列がないことを示す符号００と、符号化部２４ｂの先頭のデータｂｊとを示す符号化データ「００ｂｊ」で符号化部２４ｂの先頭のデータｂｊを符号化する。
【００１２】
図１８（ｅ）は、一致しないデータを符号化した後の参照部２４ｃおよび符号化部２５ｃの状態を示す図である。図１８（ｅ）を参照して、符号化部２５ｂの先頭のデータｂｊが符号化された後、参照部２４ｂおよび符号化部２５ｂを含むスライド窓が１次元データ２２の後方に、１個のデータ分、スライドされる。そして、符号化されたデータｂｊが参照部２４ｃに入り、新たな符号化部２５ｃに含まれるデータ列｛ｂ（ｊ＋１），…，ｂｋ｝が次の符号化の対象となる。
【００１３】
【特許文献１】
特開平９−２８９５９１号公報
【００１４】
【発明が解決しようとする課題】
多値画像の特徴としては、隣接画素や近傍画素が同一または類似の階調であることが多いことが挙げられる。このため、多値画像の画像データを各ライン単位で走査した場合に、隣接する２つのラインのうち一方のラインに含まれる画素に隣接する他方のラインに含まれる画素は、一方のラインに含まれる画素と同一の画素データであることが多くなる。その結果、隣接する２つのラインが、同一である蓋然性が高くなる。
【００１５】
しかしながら、画素データが行列状に配列された画像データを各ライン単位で走査し、１次元データ列に変換して、ＬＺ７７などの辞書に基づいた符号化方式を用いて符号化する場合、１ライン分の画素データが参照部に収まりきらないときは、符号化部に含まれているラインの画素と隣接する、前ラインに含まれる画素の画素データのうちの少なくとも一部が参照部から溢れてしまう。このため、符号化部に含まれる符号化対象の画素データ列と同一である蓋然性が高い、隣接するラインの画素データ列のうちの少なくとも一部が参照部から溢れてしまうので、溢れてしまった画素データ列に対応する符号化部に含まれる画素データ列が短く符号化されない。その結果、圧縮率が極端に悪くなるという問題があった。
【００１６】
この発明は上述の問題点を解決するためになされたもので、この発明の目的の１つは、辞書に基づいた符号化方式を用いて、圧縮率をより向上させることが可能な符号化前処理装置、画像符号化装置、画像復号装置、符号化前処理方法、符号化前処理プログラム、および、符号化前処理プログラムを記録したコンピュータ読取可能な記録媒体を提供することである。
【００１７】
【課題を解決するための手段】
上述の目的を達成するためにこの発明のある局面によれば、符号化前処理装置は、辞書に基づいた符号化方式で１次元データ列を符号化する符号化装置で符号化するための１次元データ列を出力する符号化前処理装置であって、複数の画素データが行列状に配列された画像データを記憶する記憶手段と、記憶された画像データを、辞書に相当する参照される画素データの数以下の画素データを含む予め定められた形状の矩形領域に分割する分割手段と、隣接する矩形領域を順に所定方向に読出す読出手段と、読出された矩形領域に含まれる画素データを、予め定められた順番で部分画素データ列として１次元に配列する配列手段と、配列された部分画素データ列を、矩形領域が読出された順番で出力する出力手段とを備える。
【００１８】
この発明に従えば、画像データが、辞書に相当する参照される画素データの数以下の画素データを含む予め定められた形状の矩形領域に分割され、隣接する矩形領域が順に所定方向に読出され、読出された矩形領域に含まれる画素データが、予め定められた順番で部分画素データ列として１次元に配列され、配列された部分画素データ列が、矩形領域が読出された順番で符号化装置に出力される。このため、部分画素データ列が、参照部に含むことのできる画素データの数以下である矩形領域に含まれる画素データの数ごとの周期で配列されることとなり、符号化装置で符号化されるときに、符号化対象となる符号化部に含まれる部分画素データ列の少なくとも一部を含んでいた矩形領域に隣接する矩形領域に含まれていた部分画素データ列が参照部にすべて含まれることとなる。また、矩形領域に含まれる画素データの数は参照部に含むことのできる画素データの数以下に制限され、さらに、画像データにおいては、隣接画素や近傍画素が同一階調であることが多いので、隣接する矩形領域に同じ順番で含まれる２つの画素は、比較的近傍となり、同一である蓋然性が高くなるため、隣接する矩形領域が同一である蓋然性が高くなり、隣接する矩形領域にそれぞれ対応する２つの部分画素データ列が同一である蓋然性が高くなる。その結果、１つの矩形領域に対応する符号化部に含まれる部分画素データ列の少なくとも一部が、隣接する矩形領域に対応する参照部に含まれる部分画素データ列と同一である蓋然性が高くなり、短く符号化される確率が向上するので、辞書に基づいた符号化方式を用いて、圧縮率をより向上させることが可能な符号化前処理装置を提供することができる。
【００１９】
好ましくは、矩形領域が読出される方向は、矩形領域が長辺で隣接する矩形領域に向かう方向である。
【００２０】
この発明に従えば、隣接する２つの矩形領域が長辺で隣接することとなる。また、画像データにおいては、２つの画素の距離が近いほど、２つの画素が同一階調である蓋然性が高くなる。このため、隣接する２つの矩形領域にそれぞれ含まれる対応する２つの画素の距離が、矩形領域が短辺で隣接する場合よりも短くなるので、隣接する矩形領域に含まれる対応する２つの画素が同一である蓋然性がさらに高くなり、隣接する矩形領域がそれぞれ一次元に配列された２つの部分画素データ列が同一である蓋然性が高くなる。その結果、符号化部に含まれる部分画素データ列の少なくとも一部が、参照部に含まれる部分画素データ列と同一である蓋然性がさらに高くなるので、圧縮率をさらに向上させることができる。
【００２１】
好ましくは、分割手段は、前記辞書に基づいた符号化方式で符号化対象となる画素データの数以下の画素データを含む予め定められた形状の矩形領域に分割する。
【００２２】
この発明に従えば、部分画素データ列が、符号化部に含むことのできる画素データの数以下である矩形領域に含まれる画素データの数ごとの周期で配列されることとなり、符号化装置で符号化されるときに、符号化対象となる部分画素データ列がすべて符号化部に含まれ、符号化部に含まれる部分画素データ列を含んでいた矩形領域に隣接する矩形領域に含まれていた部分画素データ列がすべて参照部に含まれる。その結果、１つの矩形領域に対応する符号化部に含まれる部分画素データ列すべてが、隣接する矩形領域に対応する参照部に含まれる部分画素データ列と同一である蓋然性が高くなり、一度に短く符号化される確率が向上するので、圧縮率をさらに向上させることができる。
【００２３】
この発明の他の局面によれば、符号化前処理装置は、辞書に基づいた符号化方式で１次元データ列を符号化する符号化装置で符号化するための１次元データ列を出力する符号化前処理装置であって、複数の画素データが行列状に配列された画像データを記憶する記憶手段と、記憶された画像データから、辞書に相当する参照される画素データの数以下の画素データを含むラインを、ラインが垂直方向に隣接するラインに向かう方向に順に読出す読出手段と、読出されたラインに含まれる部分画素データ列を、ラインが読出された順番で出力する出力手段とを備える。
【００２４】
この発明に従えば、画像データから、辞書に相当する参照される画素データの数以下の画素データを含むラインが、ラインが垂直方向に隣接するラインに向かう方向に順に読出され、読出されたラインに含まれる部分画素データ列が、ラインが読出された順番で出力される。このため、部分画素データ列が、参照部に含むことのできる画素データの数以下であるラインに含まれる画素データの数ごとの周期で配列されることとなり、符号化装置で符号化されるときに、符号化対象となる符号化部に含まれる部分画素データ列の少なくとも一部を含んでいたラインに隣接するラインに含まれていた部分画素データ列が参照部にすべて含まれることととなる。また、ラインに含まれる画素データの数は参照部に含むことのできる画素データの数以下に制限され、さらに、画像データにおいては、隣接画素や近傍画素が同一階調であることが多いので、隣接するラインの同じ位置に含まれる２つの画素は、隣接する画素となり、同一である蓋然性が高くなるため、隣接するラインが同一である蓋然性が高くなり、隣接するラインに対応する２つの部分画素データ列が同一である蓋然性が高くなる。その結果、１つのラインに対応する符号化部に含まれる部分画素データ列の少なくとも一部が、隣接するラインに対応する参照部に含まれる部分画素データ列と同一である蓋然性が高くなり、短く符号化される確率が向上するので、辞書に基づいた符号化方式を用いて、圧縮率をより向上させることが可能な符号化前処理装置を提供することができる。
【００２５】
この発明の他の局面によれば、画像符号化装置は、辞書に基づいた符号化方式で複数の画素データが行列状に配列された画像データを符号化する符号化装置であって、前記画像データを記憶する記憶手段と、記憶された画像データを、前記辞書に相当する参照される画素データの数以下の画素データを含む予め定められた形状の矩形領域に分割する分割手段と、隣接する矩形領域を順に所定方向に読出す読出手段と、読出された矩形領域に含まれる画素データを、予め定められた順番で部分画素データ列として１次元に配列する配列手段と、配列された部分画素データ列を、矩形領域が読出された順番で全画素データ列として出力する出力手段と、辞書に基づいた符号化方式で、出力された全画素データ列を符号化する符号化手段とを備える。
【００２６】
この発明に従えば、画像データが、辞書に基づいた符号化方式の辞書に相当する参照される画素データの数以下の画素データを含む予め定められた形状の矩形領域に分割され、隣接する矩形領域が順に所定方向に読出され、読出された矩形領域に含まれる画素データが、予め定められた順番で部分画素データ列として１次元に配列され、配列された部分画素データ列が、矩形領域が読出された順番で全画素データ列として出力され、辞書に基づいた符号化方式で、出力された全画素データ列が符号化される。このため、部分画像データ列が、参照部に含むことのできる画素データの数以下である矩形領域に含まれる画素データの数ごとの周期で配列されることとなり、符号化手段で符号化されるときに、符号化対象となる符号化部に含まれる部分画素データ列の少なくとも一部を含んでいた矩形領域に隣接する矩形領域に含まれていた部分画素データ列が参照部にすべて含まれることとなる。また、矩形領域に含まれる画素データの数は参照部に含むことのできる画素データの数以下に制限され、さらに、画像データにおいては、隣接画素や近傍画素が同一階調であることが多いので、隣接する矩形領域に同じ順番で含まれる２つの画素は、比較的近傍となり、同一である蓋然性が高くなるため、隣接する矩形領域が同一である蓋然性が高くなり、隣接する矩形領域にそれぞれ対応する２つの部分画素データ列が同一である蓋然性が高くなる。その結果、１つの矩形領域に対応する符号化部に含まれる部分画素データ列の少なくとも一部が、隣接する矩形領域に対応する参照部に含まれる部分画素データ列と同一である蓋然性が高くなり、短く符号化される確率が向上するので、辞書に基づいた符号化方式を用いて、圧縮率をより向上させることが可能な画像符号化装置を提供することができる。
【００２７】
好ましくは、記憶された画像データを、隣接する複数の前記矩形領域からなるブロックに分割するブロック分割手段をさらに備え、符号化手段は、分割されたブロックごとに、全画素データ列を符号化する。
【００２８】
この発明に従えば、画像データが、辞書に基づいた符号化方式の辞書に相当する参照される画素データの数以下の画素データを含む予め定められた形状の矩形領域に分割され、画像データが、隣接する複数の矩形領域からなるブロックに分割され、分割されたブロックごとに、隣接する矩形領域が順に所定方向に読出され、ブロックごとに、読出された矩形領域に含まれる画素データが部分画素データ列として１次元に配列され、ブロックごとに、配列された部分画素データ列が全画素データ列として出力され、ブロックごとに、出力された全画素データ列が符号化される。このため、ブロックごとに、画像データを符号化することができるので、画像データをブロック単位で扱うことができる部分的に復号可能な符号化データ列を生成することができる。
【００２９】
この発明のさらに他の局面によれば、画像符号化装置は、辞書に基づいた符号化方式で複数の画素データが行列状に配列された画像データを符号化する符号化装置であって、前記画像データを記憶する記憶手段と、記憶された画像データを、前記辞書に相当する参照される画素データの数以下の画素データを含む予め定められた第１の形状の矩形領域に分割する第１分割手段と、隣接する第１の形状の矩形領域を順に第１の方向に読出す第１読出手段と、読出された第１の形状の矩形領域に含まれる画素データを、予め定められた順番で第１の部分画素データ列として１次元に配列する第１配列手段と、配列された第１の部分画素データ列を、第１の形状の矩形領域が読出された順番で第１の全画素データ列として出力する第１出力手段と、辞書に基づいた符号化方式で、出力された第１の全画素データ列を、第１の符号化データ列として符号化する第１符号化手段と、記憶された画像データを、辞書に相当する参照される画素データの数以下の画素データを含む予め定められた第２の形状の矩形領域に分割する第２分割手段と、隣接する第２の形状の矩形領域を順に第２の方向に読出す第２読出手段と、読出された第２の形状の矩形領域に含まれる画素データを、予め定められた順番で第２の部分画素データ列として１次元に配列する第２配列手段と、配列された第２の部分画素データ列を、第２の形状の矩形領域が読出された順番で第２の全画素データ列として出力する第２出力手段と、辞書に基づいた符号化方式で、出力された第２の全画素データ列を、第２の符号化データ列として符号化する第２符号化手段と、符号化された第１の符号化データ列のデータ長と、符号化された第２の符号化データ列のデータ長とを比較する比較手段と、比較されたデータ長が短い符号化データ列を、出力するための符号化データ列として選択する選択手段とを備える。
【００３０】
この発明に従えば、画像データが第１の形状の矩形領域に分割されるとともに、第２の形状の矩形領域に分割され、隣接する第１の形状の矩形領域および第２の形状の矩形領域が、それぞれ、順に第１の方向および第２の方向で読出され、読出された第１の形状の矩形領域および第２の形状の矩形領域に含まれる画素データが、それぞれ、予め定められた順番で第１の部分画素データ列および第２の部分画素データ列として１次元に配列され、配列された第１の部分画素データ列および第２の部分画素データ列が、それぞれ、第１の形状の矩形領域および第２の形状の矩形領域が読出された順番で第１の全画素データ列および第２の全画素データ列として出力され、辞書に基づいた符号化方式で、出力された第１の全画素データ列および第２の全画素データ列が、それぞれ、第１の符号化データ列および第２の符号化データ列として符号化され、符号化された第１の符号化データ列のデータ長と、符号化された第２の符号化データ列のデータ長とが比較され、比較されたデータ長が短い符号化データ列が、出力するための符号化データ列として選択される。このため、第１の形状の矩形領域に分割して符号化した第１の符号化データ列と、第２の形状の矩形領域に分割して符号化した第２の符号化データ列とを比較して、より短い符号化データ列を出力するために選択するので、画像データ全体として、より短い符号化データ列を出力することができる。その結果、辞書に基づいた符号化方式を用いて、圧縮率をより向上させることが可能な画像符号化装置を提供することができる。
【００３１】
好ましくは、記憶された画像データをブロックに分割するブロック分割手段をさらに備え、ブロックは、隣接する複数の前記第１の形状の矩形領域で構成されるとともに、隣接する複数の前記第２の形状の矩形領域で構成され、第１符号化手段および第２符号化手段は、分割されたブロックごとに、それぞれ、出力された第１の全画素データ列および出力された第２の全画素データ列を符号化する。
【００３２】
この発明に従えば、画像データは、隣接する複数の第１の形状の矩形領域で構成されるとともに、隣接する複数の第２の形状の矩形領域で構成されるブロックに分割され、分割されたブロックが、第１の形状の矩形領域に分割されるとともに、第２の形状の矩形領域に分割され、ブロックごとに、分割された第１の形状の矩形領域および第２の形状の矩形領域が、それぞれ、読出され、ブロックごとに、読出された第１の形状の矩形領域および第２の形状の矩形領域に含まれる画素データが、それぞれ、第１の部分画素データ列および第２の部分画素データ列として１次元に配列され、ブロックごとに、配列された第１の部分画素データ列および第２の部分画素データ列が、それぞれ、第１の全画素データ列および第２の全画素データ列として出力され、ブロックごとに、辞書に基づいた符号化方式で、出力された第１の全画素データ列および第２の全画素データ列が、それぞれ、第１の符号化データ列および第２の符号化データ列として符号化され、ブロックごとに、符号化された第１の符号化データ列のデータ長と、符号化された第２の符号化データ列のデータ長とが比較され、ブロックごとに、比較されたデータ長が短い符号化データ列が、出力するための符号化データ列として選択される。このため、ブロックごとに、第１の形状の矩形領域に分割して符号化した第１の符号化データ列と、第２の形状の矩形領域に分割して符号化した第２の符号化データ列とを比較して、より短い符号化データ列を出力するために選択するので、ブロックごとに、より短い符号化データ列を出力することができる。その結果、画像データ全体として、さらに、圧縮率を向上させることができる。
【００３３】
この発明のさらに他の局面によれば、画像復号装置は、前述した画像符号化装置により、画像データがブロックごとに、辞書に基づいた符号化方式で符号化された符号化データ列を復号して画像データを復元する画像復号装置であって、画像データのうち、復元する前記ブロックの指定を受付ける指定受付手段と、符号化データ列のうち、指定されたブロックに対応するブロック符号化データ列を読出す読出手段と、辞書に基づいた符号化方式の復号方法で、読出されたブロック符号化データ列をブロック画素データ列として復号する復号手段と、復号されたブロック画素データ列に含まれる画素データを所定数ごとに予め定められた順番で配列して、予め定められた形状の矩形領域を順次復元する矩形領域復元手段と、順次復元された矩形領域を復元された順に所定方向に隣接するように配列して指定されたブロックの画像データを復元する画像データ復元手段とを備える。
【００３４】
この発明に従えば、画像データのうち、復元するブロックの指定が受付けられ、前述した画像符号化装置により画像データが符号化された符号化データ列のうち、指定されたブロックに対応するブロック符号化データ列が読出され、辞書に基づいた符号化方式の復号方法で、読出されたブロック符号化データ列がブロック画素データ列として復号され、復号されたブロック画素データ列に含まれる画素データが所定数ごとに予め定められた順番で配列され、予め定められた形状の矩形領域が順次復元され、順次復元された矩形領域が復元された順に所定方向に隣接するように配列され、指定されたブロックの画像データが復元される。その結果、画像データ全体を復号することなしに、局所的なブロック画像データのみを復元することができる。
【００３５】
この発明のさらに他の局面によれば、符号化前処理方法は、辞書に基づいた符号化方式で１次元データ列を符号化する符号化装置で符号化するための１次元データ列をコンピュータで出力する符号化前処理方法であって、複数の画素データが行列状に配列された画像データを記憶するステップと、記憶された画像データを、辞書に相当する参照される画素データの数以下の画素データを含む予め定められた形状の矩形領域に分割するステップと、隣接する矩形領域を順に所定方向に読出すステップと、読出された矩形領域に含まれる画素データを、予め定められた順番で部分画素データ列として１次元に配列するステップと、配列された部分画素データ列を、矩形領域が読出された順番で出力するステップとを含む。
【００３６】
この発明に従えば、辞書に基づいた符号化方式を用いて、圧縮率をより向上させることが可能な符号化前処理方法を提供することができる。
【００３７】
この発明のさらに他の局面によれば、符号化前処理プログラムは、辞書に基づいた符号化方式で１次元データ列を符号化する符号化装置で符号化するための１次元データ列を出力するコンピュータで実行されるプログラムであって、複数の画素データが行列状に配列された画像データを記憶するステップと、記憶された画像データを、辞書に相当する参照される画素データの数以下の画素データを含む予め定められた形状の矩形領域に分割するステップと、隣接する矩形領域を順に所定方向に読出すステップと、読出された矩形領域に含まれる画素データを、予め定められた順番で部分画素データ列として１次元に配列するステップと、配列された部分画素データ列を矩形領域が読出された順番で出力するステップとをコンピュータに実行させる。
【００３８】
この発明に従えば、辞書に基づいた符号化方式を用いて、圧縮率をより向上させることが可能な符号化前処理プログラム、および、符号化前処理プログラムを記録したコンピュータ読取可能な記録媒体を提供することができる。
【００３９】
【発明の実施の形態】
［第１の実施の形態］
以下、本発明の実施の形態について図面を参照して説明する。なお、図中同一符号は同一または相当する部材を示し、重複する説明は繰返さない。
【００４０】
図１は、第１の実施の形態における符号化前処理装置１００の構成の概略を示すブロック図である。図１を参照して、符号化前処理装置１００は、パーソナルコンピュータ（以下、「ＰＣ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）」という）等のコンピュータで構成される。符号化前処理装置１００は、符号化前処理装置１００の全体を制御するための制御部１１０と、所定の情報を記憶するための記憶部１３０と、符号化前処理装置１００に所定の情報を入力するための入力部１４０と、符号化前処理装置１００から所定の情報を出力するための出力部１５０と、符号化前処理装置１００をネットワーク５００と接続するためのインターフェイスである通信部１６０と、記録媒体１７１に記録された情報を入力したり、記録媒体１７１に必要な情報を記録するための外部記憶装置１７０とを含む。また、制御部１１０と、記憶部１３０と、入力部１４０と、出力部１５０と、通信部１６０と、外部記憶装置１７０とは、バスを介して、互いに接続される。
【００４１】
制御部１１０は、プログラムにしたがって所定の処理を実行するためのＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）と、制御部１１０でプログラムを実行するために必要な作業領域として用いられるＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）と、制御部１１０で実行するためのプログラムを記憶するためのＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）とを含む。
【００４２】
記憶部１３０は、ハードディスクドライブ（以下、「ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）」という）等の磁気ディスク記憶装置である。磁気ディスク記憶装置に代えて、光磁気ディスク記憶装置や、光ディスク等を用いることもできる。
【００４３】
入力部１４０は、キーボード、マウス等であり、符号化前処理装置１００に必要な情報を入力することができる。また、入力部１４０は、スキャナなどの画像を符号化前処理装置１００に入力するための装置を含む。
【００４４】
出力部１５０は、液晶表示装置または陰極線管（以下、「ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）」という）等のディスプレイであり、符号化前処理装置１００から必要な情報を出力することができる。また、出力部１５０は、プリンタを含む。
【００４５】
通信部１６０は、符号化前処理装置１００をネットワーク５００に接続するための通信インターフェイスである。符号化前処理装置１００は、通信部１６０を介して、他のコンピュータと必要な情報を送受信する。
【００４６】
外部記憶装置１７０は、記録媒体１７１に記録されたプログラムやデータを読込み、制御部１１０に送信する。また、外部記憶装置１７０は、制御部１１０からの指示により、記録媒体１７１に必要な情報を書込む。
【００４７】
コンピュータ読取可能な記録媒体１７１としては、磁気テープ、カセットテープ、フロッピー（Ｒ）ディスク、ハードディスク等の磁気ディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等の光ディスク、ＭＯ（Ｍａｇｎｅｔｏ  Ｏｐｔｉｃａｌ  ｄｉｓｋ）、ＭＤ（ＭｉｎｉＤｉｓｃ）等の光磁気ディスク、ＩＣカード、光カード等のメモリカード、あるいは、マスクＲＯＭ，ＥＰＲＯＭ（Ｅｒａｓａｂｌｅ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＥＥＰＲＯＭ（Ｅｌｅｃｔｒｉｏｎｉｃａｌｌｙ  Ｅｒａｓａｂｌｅ  ａｎｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、フラッシュＲＯＭ等の半導体メモリを含めた、固定的にプログラムを担持する記録媒体である。また、記録媒体１７１を、ネットワーク５００からプログラムがダウンロードされるように流動的にプログラムを担持する媒体とすることができる。
【００４８】
図２は、第１の実施の形態における符号化前処理装置１００の機能の概略を示す機能ブロック図である。図３は、第１の実施の形態における符号化前処理装置１００で処理されるデータを示す図である。図２を参照して、符号化前処理装置１００の制御部１１０は、画像分割部１１１と、矩形領域読出部１１２と、画素データ配列部１１３と、画素データ出力部１１４とを含む。また、符号化前処理装置１００の記憶部１３０は、画像記憶部１３１を含む。
【００４９】
図３（ａ）は、画像データを示す図である。図３（ａ）を参照して、画像記憶部１３１は、複数の画素データａ１１〜ａｍｎがｍ画素×ｎ画素の行列状に配列された画像データを記憶する。画像データは、入力部１４０のスキャナなどの画像を入力するための装置から入力されてもよいし、他のＰＣからネットワーク５００および通信部１６０を介して受信されてもよいし、外部記憶装置１７０により記録媒体１７１から読出されてもよい。ここで、画素データａ１１〜ａｍｎとは、画像を構成する最小の単位要素である画素を表現するためのデータであり、たとえば、画素の色の明度、色相、および、彩度を表現する階調データである。具体的に、画像データの各画素を、単色（モノクローム）で、２５６段階の明度を表現するためには、１画素当たり８ビットの情報量が必要であるので、それぞれの画素データａ１１〜ａｍｎを表現する情報量が８ビットとなる。画像データの各画素を、Ｒ（Ｒｅｄ），Ｇ（Ｇｒｅｅｎ），Ｂ（Ｂｌｕｅ）の３原色について、それぞれ２５６段階の明度で表現するためには、１画素当たり２４ビットの情報量が必要であるので、それぞれの画素データａ１１〜ａｍｎを表現する情報量が２４ビットとなる。
【００５０】
画像分割部１１１は、画像記憶部１３１に記憶された画像データを、所定数の画素データを含む予め定められた形状の矩形領域に分割する。図３（ａ）を参照して、所定数の画素データを含む予め定められた形状の矩形領域とは、たとえば、隣接する８個の画素データを含み、幅が４画素分で高さが２画素分の形状の矩形の領域である。具体的には、矩形領域３１は、隣接する画素データａ１１〜ａ１４，ａ２１〜ａ２４を含む４画素×２画素の形状の矩形の領域である。同様に、矩形領域３２〜３４は、それぞれ、画素データａ３１〜ａ３４，ａ４１〜ａ４４、画素データａ５１〜ａ５４，ａ６１〜ａ６４、および、画素データａ（ｍ−１）（ｎ−３）〜ａ（ｍ−１）ｎ，ａｍ（ｎ−３）〜ａｍｎを含む４画素×２画素の形状の矩形の領域である。
【００５１】
なお、所定数の画素データを含む予め定められた形状の矩形領域は、４画素×２画素の形状の矩形領域に限定されず、予め定められた形状であればよく、たとえば、所定数が８の場合は、他に、８画素×１画素、２画素×４画素、あるいは、１画素×８画素のいずれかの形状の矩形領域とすることができる。
【００５２】
また、所定数は、辞書に基づいた符号化方式の辞書に相当する参照される画素データの数以下とする。つまり、矩形領域に含まれる画素データの数は、ＬＺ７７などの辞書に基づいた符号化方式の参照部に含むことのできる画素データの数以下とする。
【００５３】
矩形領域読出部１１２は、隣接する矩形領域を順に所定方向に読出す。図３（ｂ）は、矩形領域を読出す順番を示す図である。図３（ｂ）を参照して、矩形領域読出部１１２は、たとえば、矩形領域３１を読出した後に、矩形領域３１に隣接する矩形領域３２を読出す。同様に、矩形領域３２を読出した後に、矩形領域３２に隣接する矩形領域３３を読出す。そして、最後に、矩形領域３４を読出す。つまり、矩形領域読出部１１２は、上から下に隣接する矩形領域を順に読出す。なお、矩形領域読出部１１２は、１つの矩形領域を読出した後に、その矩形領域に隣接する矩形領域を読出す順で、１つの矩形領域から隣接する矩形領域に向かう方向で、矩形領域を読出すのであれば、他の順番で矩形領域を読出してもよい。たとえば、矩形領域読出部１１２は、下から上に隣接する矩形領域を順に読出したり、左から右に隣接する矩形領域を順に読出したり、右から左に隣接する矩形領域を順に読出してもよい。
【００５４】
画素データ配列部１１３は、矩形領域読出部１１２により読出された矩形領域に含まれる画素データを、予め定められた順番で部分画像データ列として１次元に配列する。図３（ｃ）は、矩形領域に含まれる画素データを１次元に配列する順番を示す図である。図３（ｃ）を参照して、予め定められた順番とは、たとえば、予め定められた形状の矩形領域３０に含まれる画素データｂ１〜ｂ８を１次元に配列する順番であり、ｂ１→ｂ２→ｂ３→ｂ４→ｂ５→ｂ６→ｂ７→ｂ８の順番である。
【００５５】
なお、予め定められた順番は、図３（ｃ）に示した順番に限定されず、予め定められていればよく、たとえば、この場合、他に、ｂ１→ｂ３→ｂ５→ｂ７→ｂ２→ｂ４→ｂ６→ｂ８の順番、ｂ１→ｂ３→ｂ２→ｂ４→ｂ５→ｂ７→ｂ６→ｂ８の順番、あるいは、例示した順番を逆にした順番などとすることができる。
【００５６】
このように、矩形領域に含まれる画素データが予め定められた順番で１次元に配列されることにより、たとえば、隣接する２つの矩形領域３１，３２にそれぞれ含まれる画素データａ１１〜ａ１４，ａ２１〜ａ２４と画素データａ３１〜ａ３４，ａ４１〜ａ４４とが、それぞれ、同じ順番で部分画素データ列｛ａ１１，ａ２１，ａ１２，ａ２２，ａ１３，ａ２３，ａ１４，ａ２４｝，｛ａ３１，ａ４１，ａ３２，ａ４２，ａ３３，ａ４３，ａ３４，ａ４４｝として、１次元に配列されることとなる。
【００５７】
また、画素データａ１１に対応する画素と画素データａ３１に対応する画素とは、１画素分、離れており、互いに近傍の画素である。このため、画像データにおいては、画素データａ１１と画素データａ３１とが、同一である蓋然性が高い。同様に、画素データａ１２〜ａ１４，ａ２１〜ａ２４と画素データａ３２〜ａ３４，ａ４１〜ａ４４とが、それぞれ、同一である蓋然性が高い。
【００５８】
したがって、隣接する２つの矩形領域３１，３２は、同一である蓋然性が高くなる。また、隣接する２つの矩形領域３１，３２がそれぞれ１次元に配列された部分画素データ列｛ａ１１，ａ２１，ａ１２，ａ２２，ａ１３，ａ２３，ａ１４，ａ２４｝，｛ａ３１，ａ４１，ａ３２，ａ４２，ａ３３，ａ４３，ａ３４，ａ４４｝は、同一である蓋然性が高くなる。
【００５９】
なお、矩形領域読出部１１２により矩形領域が読出される方向は、矩形領域が長辺で隣接する矩形領域に向かう方向であることが好ましい。これにより、隣接する２つの矩形領域が長辺で隣接することになり、隣接する２つの矩形領域にそれぞれ含まれる対応する２つの画素の距離が、矩形領域が短辺で隣接する場合よりも短くなるので、２つの画素の画素データが同一である蓋然性がさらに高くなる。たとえば、本実施の形態においては、矩形領域は、４画素×２画素の矩形領域であり、長辺で隣接する矩形領域に向かう方向は、上から下に向かう方向、あるいは、下から上に向かう方向である。このような方向で矩形領域が読出される場合は、左から右に向かう方向、あるいは、右から左に向かう方向で矩形領域が読出される場合より、隣接する矩形領域に含まれる対応する２つの画素の距離が短くなるので、２つの画素の画素データが同一である蓋然性が高くなる。
【００６０】
画素データ出力部１１４は、画素データ配列部１１３により配列された部分画素データ列を、矩形領域が読出された順番で全画素データ列として、通信部１６０を介して符号化装置４００に出力する。図３（ｄ）は、符号化装置４００に出力される全画素データ列４１を示す図である。図３（ｄ）を参照して、全画素データ列４１は、矩形領域ごとに配列された部分画素データ列を、矩形領域が読出された順番で連続するようにした１次元データ列である。
【００６１】
具体的に、全画素データ列４１は、たとえば、矩形領域３１について配列された部分画素データ列｛ａ１１，ａ２１，ａ１２，ａ２２，ａ１３，ａ２３，ａ１４，ａ２４｝、矩形領域３２について配列された部分画素データ列｛ａ３１，ａ４１，ａ３２，ａ４２，ａ３３，ａ４３，ａ３４，ａ４４｝、矩形領域３３について配列された部分画素データ列｛ａ５１，ａ６１，ａ５２，ａ６２，ａ５３，ａ６３，ａ５４，ａ６４｝、…、矩形領域３４について配列された部分画素データ列｛ａ（ｍ−１）（ｎ−３），ａｍ（ｎ−３），ａ（ｍ−１）（ｎ−２），ａｍ（ｎ−２），ａ（ｍ−１）（ｎ−１），ａｍ（ｎ−１），ａ（ｍ−１）ｎ，ａｍｎ｝の順番で連続するようにした１次元データ列であり、｛ａ１１，ａ２１，ａ１２，ａ２２，ａ１３，ａ２３，ａ１４，ａ２４，ａ３１，ａ４１，ａ３２，ａ４２，ａ３３，ａ４３，ａ３４，ａ４４，ａ５１，ａ６１，ａ５２，ａ６２，ａ５３，ａ６３，ａ５４，ａ６４，…，ａ（ｍ−１）（ｎ−３），ａｍ（ｎ−３），ａ（ｍ−１）（ｎ−２），ａｍ（ｎ−２），ａ（ｍ−１）（ｎ−１），ａｍ（ｎ−１），ａ（ｍ−１）ｎ，ａｍｎ｝である。
【００６２】
また、符号化装置４００は、画素データ出力部１１４により出力された全画素データ列を、辞書に基づいた符号化方式、たとえば、ＬＺ７７による符号化方式で符号化する。ＬＺ７７などの辞書に基づいた符号化方式を用いた符号化については、図１８で説明したので説明は繰返さない。
【００６３】
なお、矩形領域に含まれる画素データの数、すなわち、所定数は、８に限定されず、参照部に含むことのできる画素データの数以下であれば、どのような数でもよい。
【００６４】
ここで、画素データのビット数（階調を表わす）をｋビット、ＬＺ７７アルゴリズムにおける参照部の長さをＮ画素の画素データを含み得る長さ、すなわち、（ｋ×Ｎ）ビット、ＬＺ７７の符号化部の長さをＦ画素の画素データを含みうる長さ、すなわち、（ｋ×Ｆ）ビットとする。また、画像データの幅は、ｎ画素である。図３で説明した画像データ全体をライン単位で走査する従来のラスタ順で画像データを１次元に配列した１次元データにＬＺ７７アルゴリズムを適用すると、画像の左上の画素の画素データ（以下、「着目画素データ」という）ａ１１に着目し、同じ列で次の列に含まれる画素データａ２１を符号化するときに、着目画素データａ１１が参照部に含まれているためには、ｎ≦Ｎが成立しなければならない。同様にして、同じ列でさらに次の行にある画素データａ３１を符号化するときに、着目画素データａ１１が参照部に含まれているためには、２ｎ≦Ｎが成立しなければならない。これは、次の行の画素が縦方向の近傍にありながらも符号化を行なう際に参照部に存在する確率は１画素離れただけで非常に小さくなることを意味する。
【００６５】
本実施の形態における矩形領域に含むことができる画素データの数をＬとすると、矩形領域の幅は、高々、Ｌ画素である。また、Ｌ≦ｎである。このため、Ｌ≦Ｎが成立するようにＬを定めれば、縦方向の近傍にある画素が参照部に存在する確率が高くなる。画像データには、２次元的な相関関係があるため、縦方向に近傍する画素が参照部に存在する確率が高くなることで、符号化部における最長一致がより長くなる確率が高いといえる。また、Ｌ＝１の場合、ラスタ順を縦型としたものと同様となるため、折返すことによる効果は得られない。したがって、矩形領域に含まれる画素データの数Ｌが、次式を満たすようにする。
【００６６】
１＜Ｌ≦Ｎ    …  （１）
すなわち、本実施の形態においては、矩形領域に含まれる画素データの数Ｌは、参照部に含むことのできる画素データの数Ｎ以下であるようにする。
【００６７】
これにより、画素データ出力部１１４から出力された全画素データ列４１には、隣接する矩形領域に対応する部分画素データ列が、参照部に含むことのできる画素データの数以下である矩形領域に含まれる画素データの数ごとの周期で配列されることとなり、符号化装置４００で符号化されるときに、符号化部に含まれる部分画素データ列の少なくとも一部を含んでいた矩形領域に隣接する矩形領域に含まれていた部分画素データ列が参照部にすべて含まれることとなる。また、矩形領域に含まれる画素データの数は参照部に含むことのできる画素データの数以下に制限され、さらに、画像データにおいては、隣接画素や近傍画素が同一階調であることが多いので、隣接する矩形領域に同じ順番で含まれる２つの画素は、比較的近傍となり、同一である蓋然性が高くなり、画素データ配列部１１３により隣接する２つの矩形領域がそれぞれ１次元に配列された２つの部分画素データ列が同一である蓋然性が高い。このため、符号化部に含まれる部分画素データ列と、参照部に含まれる部分画素データ列とが同一である蓋然性が高くなる。その結果、１つの矩形領域に対応する符号化部に含まれる符号化対象の部分画素データ列の少なくとも一部が、隣接する矩形領域に対応する参照部に含まれる部分画素データ列と同一である蓋然性が高くなり、短く符号化される確率が向上するので、画像データ出力部１１４は、圧縮率をより向上させることが可能な１次元データ列である全画素データ列を、符号化装置４００に、出力することができる。
【００６８】
また、近傍のＬ画素は同系列の記号列で一致する確立が高いといえる。よって、符号化を行なう際にＬ画素分を参照部と比較できたほうがよい。したがって、矩形領域に含まれる画素データの数Ｌが、次式を満たすようにすることが好ましい。
【００６９】
１＜Ｌ≦Ｆ    …  （２）
すなわち、所定数Ｌが、符号化部に含むことのできる画素データの数Ｆ以下とする。この場合、符号化対象となる部分画素データ列がすべて符号化部に含まれ、符号化部に含まれる部分画素データ列を含んでいた矩形領域に隣接する矩形領域に含まれていた部分画素データ列がすべて参照部に含まれる。その結果、１つの矩形領域に対応する符号化部に含まれる部分画素データ列すべてが、隣接する矩形領域に含まれていた参照部に含まれる部分画素データ列と同一である蓋然性が高くなり、一度に短く符号化される確率が向上するので、圧縮率をさらに向上させることができる。
【００７０】
図４は、第１の実施の形態における符号化前処理装置１００で実行される符号化前処理の流れを示すフローチャートである。図４を参照して、まず、ステップＳ１１で、画像記憶部１３１に画像データが記憶される。画像データは、入力部１４０のスキャナなどの画像を入力するための装置から入力されてもよいし、他のＰＣからネットワーク５００および通信部１６０を介して受信されてもよいし、外部記憶装置１７０により記録媒体１７１から読出されてもよい。
【００７１】
そして、ステップＳ１２で、画像分割部１１１により、ステップＳ１１で記憶された画像データが、所定数の画素データを含む予め定められた形状の矩形領域に分割される。
【００７２】
次に、ステップＳ１３で、矩形領域読出部１１２により、隣接する矩形領域が、順に所定方向に読出され、ステップＳ１４で、画素データ配列部１１３により、ステップＳ１３で読出された矩形領域に含まれる画素データが、予め定められた順番で部分画素データ列として１次元に配列される。
【００７３】
最後に、ステップＳ１５で、画素データ出力部１１４により、ステップＳ１４で配列された部分画素データ列が、ステップＳ１２で矩形領域が読出された順番で全画素データ列として符号化装置４００に出力される。
【００７４】
以上説明したように、第１の実施の形態における符号化前処理装置１００においては、画像データが、８個の画素データを含む矩形領域３１，３２，…に分割され、１つの矩形領域を読出した後に、その矩形領域に隣接する矩形領域を読出す順で、１つの矩形領域から隣接する矩形領域に向かう方向で読出された矩形領域３１，３２，…に含まれる画素データａ１１〜ａ１４，ａ２１〜ａ２４，画素データａ３１〜ａ３４，ａ４１〜ａ４４，…が、部分画素データ列｛ａ１１，ａ２１，ａ１２，ａ２２，ａ１３，ａ２３，ａ１４，ａ２４｝，｛ａ３１，ａ４１，ａ３２，ａ４２，ａ３３，ａ４３，ａ３４，ａ４４｝…として配列され、部分画素データ列｛ａ１１，ａ２１，ａ１２，ａ２２，ａ１３，ａ２３，ａ１４，ａ２４｝，｛ａ３１，ａ４１，ａ３２，ａ４２，ａ３３，ａ４３，ａ３４，ａ４４｝，…が、矩形領域３１，３２，…が読出された順番で符号化装置に出力される。
【００７５】
このため、部分画素データ列が、参照部に含むことのできる画素データの数以下である矩形領域に含まれる画素データの数ごとの周期で配列されることとなり、符号化装置で符号化されるときに、符号化対象となる符号化部に含まれる部分画素データ列の少なくとも一部を含んでいた矩形領域に隣接する矩形領域に含まれていた部分画素データ列が参照部にすべて含まれることとなる。
【００７６】
また、矩形領域に含まれる画素データの数は参照部に含むことのできる画素データの数以下に制限され、さらに、画像データにおいては、隣接画素や近傍画素が同一階調であることが多いので、隣接する矩形領域に同じ順番で含まれる２つの画素は、比較的近傍となり、同一である蓋然性が高くなるため、隣接する矩形領域が同一である蓋然性が高くなり、隣接する矩形領域にそれぞれ対応する２つの部分画素データ列が同一である蓋然性が高くなる。
【００７７】
その結果、１つの矩形領域に対応する符号化部に含まれる部分画素データ列の少なくとも一部が、隣接する矩形領域に対応する参照部に含まれる部分画素データ列と同一である蓋然性が高くなり、短く符号化される確率が向上するので、辞書に基づいた符号化方式を用いて、圧縮率をより向上させることができる。
【００７８】
また、第１の実施の形態における符号化前処理装置１００において、矩形領域読出部１１２により矩形領域が読出される方向を、矩形領域が長辺で隣接する矩形領域に向かう方向とした場合、隣接する２つの矩形領域が、長辺で隣接することとなる。また、画像データにおいては、２つの画素の距離が近いほど、２つの画素が同一階調である蓋然性が高くなる。
【００７９】
このため、隣接する２つの矩形領域にそれぞれ含まれる対応する２つの画素の距離が、矩形領域が短辺で隣接する場合よりも短くなるので、隣接する矩形領域に含まれる対応する２つの画素が同一である蓋然性がさらに高くなり、隣接する矩形領域がそれぞれ一次元に配列された２つの部分画素データ列が同一である蓋然性が高くなる。その結果、符号化部に含まれる部分画素データ列の少なくとも一部が、参照部に含まれる部分画素データ列と同一である蓋然性がさらに高くなるので、圧縮率をさらに向上させることができる。
【００８０】
また、第１の実施の形態における符号化前処理装置１００において、画像分割部１１１が、画像記憶部１３１に記憶された画像データを、辞書に基づいた符号化方式で符号化対象となる画素データの数以下の画素データを含む予め定められた形状の矩形領域に分割する場合、部分画素データ列が、符号化部に含むことのできる画素データの数以下である矩形領域に含まれる画素データの数ごとの周期で配列されることとなり、符号化装置で符号化されるときに、符号化対象となる部分画素データ列がすべて符号化部に含まれ、符号化部に含まれる部分画素データ列を含んでいた矩形領域に隣接する矩形領域に含まれていた部分画素データ列がすべて参照部に含まれる。
【００８１】
その結果、１つの矩形領域に対応する符号化部に含まれる部分画素データ列すべてが、隣接する矩形領域に対応する参照部に含まれる部分画素データ列と同一である蓋然性が高くなり、一度に短く符号化される確率が向上するので、圧縮率をさらに向上させることができる。
【００８２】
図５は、第１の実施の形態の変形例である画像符号化装置２００の機能の概略を示す機能ブロック図である。図５を参照して、図３で説明した符号化前処理装置１００と符号化装置４００とを組合わせて、画像符号化装置２００としたものである。すわなち、画像符号化装置２００は、符号化装置４００の機能を実現するための画素データ符号化部１１５を、符号化前処理装置１００にさらに付加したものである。画素データ出力部１１４により出力された全画素データ列が、画素データ符号化部１１５に入力され、符号化されて、符号化データ記憶部１３２に記憶される。
【００８３】
なお、画素データ符号化部１１５で生成された符号化データ列は、記憶部２３０に設けられた符号化データ記憶部１３２に記憶されてもよいし、通信部およびネットワークを介して他のＰＣに送信されてもよいし、外部記憶装置により記録媒体に記録されてもよい。
【００８４】
第１の実施の形態の変形例における画像符号化装置２００においては、画像データが、参照部に含むことのできる画素データの数以下の画素データを含む矩形領域に分割され、順に所定方向に読出された矩形領域に含まれる画素データが、部分画素データ列として配列され、配列された部分画素データ列が矩形領域が読出された順番で出力された全画素データ列が符号化される。
【００８５】
このため、部分画像データ列が、参照部に含むことのできる画素データの数以下である矩形領域に含まれる画素データの数ごとの周期で配列されることとなり、符号化手段で符号化されるときに、符号化対象となる符号化部に含まれる部分画素データ列の少なくとも一部を含んでいた矩形領域に隣接する矩形領域に含まれていた部分画素データ列が参照部にすべて含まれることとなる。
【００８６】
また、矩形領域に含まれる画素データの数は参照部に含むことのできる画素データの数以下に制限され、さらに、画像データにおいては、隣接画素や近傍画素が同一階調であることが多いので、隣接する矩形領域に同じ順番で含まれる２つの画素は、比較的近傍となり、同一である蓋然性が高くなるため、隣接する矩形領域が同一である蓋然性が高くなり、隣接する矩形領域にそれぞれ対応する２つの部分画素データ列が同一である蓋然性が高くなる。
【００８７】
その結果、１つの矩形領域に対応する符号化部に含まれる部分画素データ列の少なくとも一部が、隣接する矩形領域に対応する参照部に含まれる部分画素データ列と同一である蓋然性が高くなり、短く符号化される確率が向上するので、辞書に基づいた符号化方式を用いて、圧縮率をより向上させることができる。
【００８８】
なお、第１の実施の形態においては、符号化前処理装置１００で行われる処理について説明したが、図４に示した処理をコンピュータで実行する符号化前処理方法、図４に示した処理をコンピュータに実行させるための符号化前処理プログラム、および、符号化前処理プログラムを記録したコンピュータ読取可能な記録媒体として発明を捕らえることができる。
【００８９】
［第２の実施の形態］
第１の実施の形態においては、符号化前処理装置１００が画像データを矩形領域に分割して符号化する場合について説明した。
【００９０】
第２の実施の形態においては、符号化前処理装置１００Ａが画像データをラインごとに読出し符号化する場合について説明する。
【００９１】
第２の実施の形態における符号化前処理装置１００Ａの構成は、図１で説明した第１の実施の形態における符号化前処理装置１００の構成と同様である。
【００９２】
図６は、第２の実施の形態における符号化前処理装置１００Ａの機能の概略を示す機能ブロック図である。図７は、第２の実施の形態における符号化前処理装置１００Ａで処理されるデータを示す図である。図６を参照して、符号化前処理装置１００Ａの制御部１１０Ａは、ライン読出部１１６と、画素データ出力部１１４Ａとを含む。また、符号化前処理装置１００Ａの記憶部１３０は、画像記憶部１３１を含む。画像記憶部１３１は、図２で説明した符号化前処理装置１００の記憶部１３０の画像記憶部１３１と同様である。
【００９３】
図７（ａ）は、画像データを示す図である。図７（ａ）を参照して、画像記憶部１３１は、複数の画素データａ１１〜ａｍｎがｍ×ｎの行列状に配列された画像データを記憶する。画像データは、入力部１４０のスキャナなどの画像を入力するための装置から入力されてもよいし、他のＰＣからネットワーク５００および通信部１６０を介して受信されてもよいし、外部記憶装置１７０により記録媒体１７１から読出されてもよい。
【００９４】
ライン読出部１１６は、画像記憶部１３１に記憶された画像データから、所定数の画素データを含むラインを、ラインが垂直方向に隣接するラインに向かう方向に順に読出す。図７（ａ）を参照して、所定数の画素データを含むラインとは、たとえば、隣接する８個の画素データを含むラインである。具体的には、ライン３５ａは、隣接する画素データａ１１〜ａ１８を含む。同様に、ライン３６ａ〜３８ａは、それぞれ、画素データａ２１〜ａ２８、画素データａ３１〜ａ３８、および、画素データａｍ（ｎ−７）〜ａｍｎを含む。
【００９５】
また、所定数は、辞書に基づいた符号化方式の辞書に相当する参照される画素データの数以下とする。つまり、ラインに含まれる画素データの数は、ＬＺ７７などの辞書に基づいた符号化方式の参照部に含むことのできる画素データの数以下とする。
【００９６】
図７（ｂ）は、ラインを読出す順番を示す図である。図７（ｂ）を参照して、ライン読出部１１６は、たとえば、ライン３５ａを読出した後に、ライン３５ａに垂直方向に隣接するライン３６ａを読出す。同様に、ライン３６ａを読出した後に、ライン３６ａに垂直方向に隣接するライン３７ａを読出す。そして、最後に、ライン３８ａを読出す。つまり、ライン読出部１１６は、上から下に隣接するラインを順に読出す。なお、ライン読出部１１６は、１つのラインを読出した後に、そのラインに垂直方向に隣接するラインを読出す順で、１つのラインから隣接するラインに向かう方向で、ラインを読出すのであれば、他の順番でラインを読出してもよい。たとえば、ライン読出部１１６は、下から上に隣接するラインを順に読出してもよい。
【００９７】
画素データ出力部１１４Ａは、ライン読出部１１６により読出されたラインに含まれる画素データを、ラインが読出された順番で全画素データ列として、通信部１６０を介して符号化装置４００に出力する。図７（ｃ）は、符号化装置４００に出力される全画素データ列４１ａを示す図である。図７（ｃ）を参照して、全画素データ列４１ａは、読出されたラインに含まれる部分画素データ列を、ラインが読出された順番で連続するようにした１次元データ列である。
【００９８】
具体的に、全画素データ列４１ａは、たとえば、ライン３５ａに含まれる部分画素データ列｛ａ１１，ａ１２，ａ１３，ａ１４，ａ１５，ａ１６，ａ１７，ａ１８｝、ライン３６ａに含まれる部分画素データ列｛ａ２１，ａ２２，ａ２３，ａ２４，ａ２５，ａ２６，ａ２７，ａ２８｝、ライン３７ａに含まれる部分画素データ列｛ａ３１，ａ３２，ａ３３，ａ３４，ａ３５，ａ３６，ａ３７，ａ３８｝、…、ライン３８ａに含まれる部分画素データ列｛ａｍ（ｎ−７），ａｍ（ｎ−６），ａｍ（ｎ−５），ａｍ（ｎ−４），ａｍ（ｎ−３），ａｍ（ｎ−２），ａｍ（ｎ−１），ａｍｎ｝の順番で連続するようにした１次元データ列であり、｛ａ１１，ａ１２，ａ１３，ａ１４，ａ１５，ａ１６，ａ１７，ａ１８，ａ２１，ａ２２，ａ２３，ａ２４，ａ２５，ａ２６，ａ２７，ａ２８，ａ３１，ａ３２，ａ３３，ａ３４，ａ３５，ａ３６，ａ３７，ａ３８，…，ａｍ（ｎ−７），ａｍ（ｎ−６），ａｍ（ｎ−５），ａｍ（ｎ−４），ａｍ（ｎ−３），ａｍ（ｎ−２），ａｍ（ｎ−１），ａｍｎ｝である。
【００９９】
本実施の形態におけるラインに含むことができる画素データの数をＬとすると、ラインの長さは、Ｌ画素である。また、Ｌ≦ｎである。このため、Ｌ≦Ｎが成立するようにＬを定めれた、縦方向に隣接する画素が参照部に存在する確率が高くなる。画像データには、２次元的な相関関係があるため、縦方向に隣接する画素が参照部に存在する確率が高くなることで、符号化部における最長一致がより長くなる確率が高いといえる。また、Ｌ＝１の場合、ラスタ順を縦型としてものと同様となるため，折返すことによる効果は得られない。したがって、ラインに含まれる画素データの数Ｌが、次式を満たすようにする。
【０１００】
１＜Ｌ≦Ｎ    …（３）
すなわち、本実施の形態においては、ラインに含まれる画素データの数Ｌは、参照部に含むことのできる画素データの数Ｎ以下であるようにする。
【０１０１】
これにより、画素データ出力部１１４Ａから出力された全画素データ列４１ａには、隣接するラインに対応する部分画素データ列が、参照部に含むことのできる画素データの数以下である矩形領域に含まれる画素データの数ごとの周期で配列されることとなり、符号化装置４００で符号化されるときに、符号化部に含まれる部分画素データ列の少なくとも一部を含んでいたラインに隣接するラインに含まれていた部分画素データ列が参照部にすべて含まれることとなる。
【０１０２】
また、ラインに含まれる画素データの数は参照部に含むことのできる画素データの数以下に制限され、さらに、画像データにおいては、隣接画素が同一階調であることが多いので、隣接するラインに同じ順番で含まれる２つの画素は、隣接画素となり、同一である蓋然性が高くなり、隣接する２つのラインにそれぞれ含まれる部分画素データ列は、同一である蓋然性が高い。このため、符号化部に含まれる部分画素データ列と参照部に含まれる部分画素データ列とが同一である蓋然性が高くなる。
【０１０３】
その結果、１つのラインに対応する符号化部に含まれる符号化対象の部分画素データ列の少なくとも一部が、隣接するラインに対応する参照部に含まれる部分画素データ列と同一である蓋然性が高くなり、短く符号化される確率が向上するので、画素データ出力部１１４Ａは、圧縮率をより向上させることが可能な全画素データ列を１次元データ列として、符号化装置４００に出力することができる。
【０１０４】
なお、本実施の形態においては、ラインに含まれる画素データの数、すなわち、所定数を８として説明したが、これに限定されず、所定数は、参照部に含むことのできる画素データの数以下であれば、どのような数でもよい。
【０１０５】
また、所定数が、符号化部に含むことのできる画素データの数以下とした場合、ラインに含まれる画素データがすべて符号化部に含まれることとなり、符号化部に含まれる部分画素データ列を含むラインと隣接するラインに含まれる部分画素データ列がすべて参照部に含まれているので、符号化部に含まれる符号化対象の部分画素データ列と同一である蓋然性が高い部分画素データ列が、すべて、参照部に含まれ、符号化部に含まれる符号化対象の部分画素データ列をさらに短く符号化することができる。
【０１０６】
図８は、第２の実施の形態における符号化前処理装置１００Ａで実行される符号化前処理の流れを示すフローチャートである。図８を参照して、まず、ステップＳ２１で、画像記憶部１３１に画像データが記憶される。画像データは、入力部１４０のスキャナなどの画像を入力するための装置から入力されてもよいし、他のＰＣからネットワーク５００および通信部１６０を介して受信されてもよいし、外部記憶装置１７０により記録媒体１７１から読出されてもよい。
【０１０７】
次に、ステップＳ２２で、ライン読出部１１６により、ステップＳ２１で記憶された画像データから、所定数の画素データを含むラインが、ラインが垂直方向に隣接するラインに向かう方向に順に読出される。
【０１０８】
最後に、ステップＳ２３で、画素データ出力部１１４Ａにより、ステップＳ２２で読出されたラインに含まれる画素データが、ラインが読出された順番で全画素データ列として、通信部１６０を介して符号化装置４００に出力される。
【０１０９】
以上説明したように、第２の実施の形態における符号化前処理装置１００Ａにおいては、画像データから８個の画素データを含み、１つのラインを読出した後に、そのラインが垂直方向に隣接するラインを読出す順で、１つのラインから隣接するラインに向かう方向に読出されたライン３５ａ，３６ａ，…に含まれる部分画素データ列｛ａ１１，ａ１２，ａ１３，ａ１４，ａ１５，ａ１６，ａ１７，ａ１８｝，｛ａ２１，ａ２２，ａ２３，ａ２４，ａ２５，ａ２６，ａ２７，ａ２８｝，…が、ライン３５ａ，３６ａ，…が読出された順番で出力される。このため、部分画素データ列が、参照部に含むことのできる画素データの数以下であるラインに含まれる画素データの数ごとの周期で配列されることとなり、符号化装置で符号化されるときに、符号化対象となる符号化部に含まれる部分画素データ列の少なくとも一部を含んでいたラインに隣接するラインに含まれていた部分画素データ列が参照部にすべて含まれることととなる。
【０１１０】
また、ラインに含まれる画素データの数は参照部に含むことのできる画素データの数以下に制限され、さらに、画像データにおいては、隣接画素や近傍画素が同一階調であることが多いので、隣接するラインの同じ位置に含まれる２つの画素は、隣接する画素となり、同一である蓋然性が高くなるため、隣接するラインが同一である蓋然性が高くなり、隣接するラインに対応する２つの部分画素データ列が同一である蓋然性が高くなる。
【０１１１】
その結果、１つのラインに対応する符号化部に含まれる部分画素データ列の少なくとも一部が、隣接するラインに対応する参照部に含まれる部分画素データ列と同一である蓋然性が高くなり、短く符号化される確率が向上するので、辞書に基づいた符号化方式を用いて、圧縮率をより向上させることができる。
【０１１２】
なお、第２の実施の形態においては、符号化前処理装置１００Ａで行われる処理について説明したが、図８に示した処理をコンピュータで実行する符号化前処理方法、図８に示した処理をコンピュータに実行させるための符号化前処理プログラム、および、符号化前処理プログラムを記録したコンピュータ読取可能な記録媒体として発明を捕らえることができる。
【０１１３】
［第３の実施の形態］
第１の実施の形態の変形例においては、画像符号化装置２００が画像データ全体について一括して符号化する場合について説明した。
【０１１４】
第３の実施の形態においては、画像符号化装置２００Ａがブロックごとに画像データを符号化する場合について説明する。
【０１１５】
第３の実施の形態における画像符号化装置２００Ａの構成は、図１で説明した第１の実施の形態における符号化前処理装置１００の構成と同様である。
【０１１６】
図９は、第３の実施の形態における画像符号化装置２００Ａの機能の概略を示す機能ブロック図である。図１０は、第３の実施の形態におけるブロックを説明するための図である。図９を参照して、画像符号化装置２００Ａの制御部２１０Ａは、画像分割部２１１と、ブロック分割部２１６と、矩形領域読出部２１２と、画素データ配列部２１３と、画素データ出力部２１４と、画素データ符号化部２１５とを含む。また、画像符号化装置２００Ａの記憶部２３０は、画像記憶部２３１と、符号化データ記憶部２３２とを含む。。
【０１１７】
図１０（ａ）は、画像データを示す図である。図１０（ａ）を参照して、画像記憶部２３１は、複数の画素データａ１１〜ａｍｎがｍ×ｎの行列状に配列された画像データを記憶する。画像データは、入力部のスキャナなどの画像を入力するための装置から入力されてもよいし、他のＰＣからネットワークおよび通信部を介して受信されてもよいし、外部記憶装置により記録媒体から読出されてもよい。
【０１１８】
画像分割部２１１は、画像記憶部２３１に記憶された画像データを、所定数の画素データを含む予め定められた形状の矩形領域に分割する。図１０（ａ）を参照して、所定数の画素データを含む予め定められた形状の矩形領域とは、たとえば、隣接する８個の画素データを含み、幅が８画素分で高さが１画素分の形状の矩形の領域である。
【０１１９】
また、所定数は、辞書に基づいた符号化方式の辞書に相当する参照される画素データの数以下とする。つまり、矩形領域に含まれる画素データの数は、ＬＺ７７などの辞書に基づいた符号化方式の参照部に含むことのできる画素データの数以下とする。
【０１２０】
ブロック分割部２１６は、画像記憶部２３１に記憶された画像データを、隣接する複数の矩形領域からなるブロックに分割する。図１０（ａ）を参照して、隣接する複数の矩形領域からなるブロックとは、たとえば、隣接する８個の矩形領域からなる領域である。この場合、ブロックは、幅が８画素分で高さが１画素分である矩形領域が縦に８個隣接する形状の領域であるので、８画素×８画素の領域となる。具体的に、ブロック５１は、６４画素分の画素データａ１１〜ａ８８を含む。同様に、ブロック５２は、ａ（ｍ−７）（ｎ−７）〜ａｍｎを含む。
【０１２１】
矩形領域読出部２１２は、ブロックごとに、隣接する矩形領域を、順に所定方向に読出す。図１０（ｂ）は、ブロックごとに矩形領域を読出すことを説明するための図である。図１０（ｂ）を参照して、ブロック５１について、ブロック５１に含まれる隣接する矩形領域が順に所定方向に読出される。同様に、ブロック５２について、ブロック５２に含まれる矩形領域が順に所定方向に読出される。
【０１２２】
画素データ配列部２１３は、ブロックごとに、矩形領域読出部２１２により読出された矩形領域に含まれる画素データを、予め定められた順番で部分画像データ列として１次元に配列する。予め定められた順番とは、たとえば、８画素×１画素の形状の矩形領域において、左から右に向かう順番である。
【０１２３】
画素データ出力部２１４は、ブロックごとに、画素データ配列部２１３により配列された部分画素データ列を、矩形領域読出部２１２により矩形領域が読出された順番で全画素データ列として出力する。
【０１２４】
画素データ符号化部２１５は、ブロックごとに、画素データ出力部２１４により出力された全画素データ列を、辞書に基づいた符号化方式、たとえば、ＬＺ７７による符号化方式で符号化して、符号化データ列を生成する。
【０１２５】
符号化データ記憶部２３２は、画素データ符号化部２１５で生成された符号化データ列を記憶する。符号化データ列は、すべてのブロックについての符号化データ列を画像データ全体に対して１つの符号化データ列としてまとめた符号化データ列であってもよいし、ブロックごとに分けられた符号化データ列であってもよい。また、符号化データ列は、ブロックごとに読込可能なデータとして記憶される。さらに、画素データ符号化部２１５で生成された符号化データ列を記憶部２３０の符号化データ記憶部２３２に記憶するようにしたが、これに限定されず、画素データ符号化部２１５で生成された符号化データ列は、通信部およびネットワークを介して他のＰＣに送信されてもよいし、外部記憶装置１７０により記録媒体に記録されてもよい。
【０１２６】
第３の実施の形態における画像符号化装置２００Ａによる符号化処理は、それぞれのブロックに含まれる画像データを第１の実施の形態の変形例における画像データ全体として、第１の実施の形態の変形例における画像符号化装置２００により符号化する処理に相当する。
【０１２７】
なお、ブロックは、８画素×８画素の領域に限定されず、隣接する複数の矩形領域を組合わせた形状の領域であれば、どのような領域でもよい。また、ブロックのサイズは、携帯情報端末などの表示部に表示可能なサイズであることが好ましい。さらに、ブロックのサイズが小さいと、１つの画像データが多くのブロックに分断されてしまい、分断されない場合に短く符号化される部分画素データ列が短く符号化されなくなるので、ブロックのサイズは、具体的には、６４画素×６４画素以上であることが好ましい。
【０１２８】
図１１は、第３の実施の形態における画像符号化装置２００Ａで実行される画像符号化処理の流れを示すフローチャートである。図１１を参照して、まず、ステップＳ４１で、画像記憶部２３１に画像データが記憶される。画像データは、入力部のスキャナなどの画像を入力するための装置から入力されてもよいし、他のＰＣからネットワークおよび通信部を介して受信されてもよいし、外部記憶装置により記録媒体から読出されてもよい。
【０１２９】
そして、ステップＳ４２で、画像分割部２１１により、ステップＳ４１で記憶された画像データが、所定数の画素データを含む予め定められた形状の矩形領域に分割される。
【０１３０】
次に、ステップＳ４３で、ブロック分割部２１６により、ステップＳ４１で記憶された画像データが、隣接する複数の矩形領域からなるブロックに分割される。
【０１３１】
次に、画像データに含まれるそれぞれのブロックごとに、ステップＳ４４〜ステップＳ４９が実行される。まず、ステップＳ４５で、矩形領域読出部２１２により、隣接する矩形領域が、順に所定方向に読出され、ステップＳ４６で、画素データ配列部２１３により、ステップＳ４５で読出された矩形領域に含まれる画素データが、予め定められた順番で部分画像データ列として１次元に配列される。
【０１３２】
そして、ステップＳ４７で、画素データ出力部２１４により、ステップＳ４６で配列された部分画素データ列が、ステップＳ４５で矩形領域が読出された順番で全画素データ列として出力され、ステップＳ４８で、画素データ符号化部２１５により、ステップＳ４７で出力された全画素データ列が、辞書に基づいた符号化方式、たとえば、ＬＺ７７による符号化方式で符号化され、符号化データ列が生成される。
【０１３３】
すべてのブロックについて、ステップＳ４４〜ステップＳ４９が実行された後、ステップＳ５０で、ステップＳ４８でブロックごとに生成された符号化データ列が、符号化データ記憶部２３２に記憶される。ここでは、ステップＳ５０で、符号化データ列を記憶部２３０の符号化データ記憶部２３２に記憶するようにしたが、これに限定されず、符号化データ列は、通信部およびネットワークを介して他のＰＣに送信されてもよいし、外部記憶装置１７０により記録媒体に記録されてもよい。
【０１３４】
以上説明したように、第３の実施の形態における画像符号化装置２００においては、画像データが、所定数の画素データを含む矩形領域に分割され、画像データが、隣接する複数の矩形領域からなるブロックに分割され、ブロックごとに、順に所定方向に読出された矩形領域に含まれる画素データが部分画素データ列として配列され、ブロックごとに、部分画素データ列が、矩形領域が読出された順番で符号化される。このため、ブロックごとに、画像データを符号化することができるので、画像データをブロック単位で扱うことができる符号化データ列を生成することができる。
【０１３５】
なお、第３の実施の形態においては、画像符号化装置２００Ａで行われる処理について説明したが、図１１に示した処理をコンピュータで実行する画像符号化方法、図１１に示した処理をコンピュータに実行させるための画像符号化プログラム、および、画像符号化プログラムを記録したコンピュータ読取可能な記録媒体として発明を捕らえることができる。
【０１３６】
［第４の実施の形態］
第３の実施の形態においては、画像符号化装置２００Ａがブロックごとに画像データを符号化する場合について説明した。
【０１３７】
第４の実施の形態においては、第３の実施の形態で説明した画像符号化装置２００Ａで画像データからブロックごとに符号化された符号化データ列を復号して、ブロックごとに画像データを復元する画像復号装置３００について説明する。
【０１３８】
第４の実施の形態における画像復号装置３００の構成は、図１で説明した第１の実施の形態における符号化前処理装置１００の構成と同様である。また、画像復号装置３００は、ＰＣなどのコンピュータに限定されず、携帯情報端末などであってもよい。
【０１３９】
図１２は、第４の実施の形態における画像復号装置３００の機能の概略を示す機能ブロック図である。図１２を参照して、画像復号装置３００の制御部３１０は、指定受付部３１１と、符号化データ読出部３１２と、復号部３１３と、画素データ配列部３１４と、矩形領域配列部３１５とを含む。画像復号装置３００の記憶部３３０は、符号化データ記憶部３３２と、画像記憶部３３１とを含む。
【０１４０】
符号化データ記憶部３３２は、第３の実施の形態で説明した画像符号化装置２００Ａで画像データがブロックごとに、辞書に基づいた符号化方式で符号化された符号化データ列を記憶する。符号化データ列は、画像符号化装置２００Ａで、ブロックとの対応が識別可能に符号化される。また、符号化データ列は、他のＰＣからネットワークおよび通信部を介して受信されてもよいし、外部記憶装置により記録媒体から読出されてもよい。ブロックとは、画像符号化装置２００Ａで予め定められた形状の領域であり、たとえば、図１０で説明したブロック５１，５２のような８画素×８画素の領域である。なお、ブロックは、８画素×８画素の領域に限定されない。また、ブロックのサイズは、携帯情報端末などの表示部に表示可能なサイズであることが好ましい。これにより、復元されたブロックに対応する画像データを一度に表示することができる。
【０１４１】
指定受付部３１１は、画像データのうち、復元するブロックの指定を、キーボードやマウスなどの入力部３４０から受付ける。ブロックの指定は、入力部３４０から受付けられることに限定されず、他のＰＣからネットワークおよび通信部を介して受付けられるようにしてもよい。
【０１４２】
符号化データ読出部３１２は、符号化データ記憶部３３２に記憶された符号化データ列のうち、指定されたブロックに対応するブロック符号化データ列を読出す。
【０１４３】
復号部３１３は、辞書に基づいた符号化方式の復号方法で、符号化データ読出部３１２により読出されたブロック符号化データ列をブロック画素データ列として復号する。
【０１４４】
矩形領域復元部３１４は、画素データ取得部３１３により復号されたブロック画素データ列に含まれる画素データを、所定数ごとに予め定められた順番で配列して、予め定められた形状の矩形領域を順次復元する。
【０１４５】
画像データ復元部３１５は、矩形領域復元部３１４により順次復元された矩形領域を復元された順に所定方向に隣接するように配列して指定されたブロックのブロック画像データを復元して、復元されたブロック画像データを液晶表示装置などの出力部３５０に出力する。
【０１４６】
図１３は、第４の実施の形態における画像復号装置３００で実行される画像復号処理の流れを示すフローチャートである。図１３を参照して、まず、ステップＳ５１で、指定受付部３１１により、画像データのうち、復元するブロックの指定が、キーボードやマウスなどの入力部３４０から受付けられる。ブロックの指定は、入力部３４０から受付けられることに限定されず、他のＰＣからネットワークおよび通信部を介して受付けられるようにしてもよい。
【０１４７】
次に、ステップＳ５２で、符号化データ読出部３１２により、符号化データ記憶部３３２に記憶された符号化データ列のうち、指定されたブロックに対応するブロック符号化データ列が読出される。
【０１４８】
そして、ステップＳ５３で、復号部３１３により、辞書に基づいた符号化方式の復号方法で、ステップＳ５２で読出されたブロック符号化データ列が、ブロック画素データ列として復号される。
【０１４９】
最後に、ステップＳ５４で、矩形領域復元部３１４により、ステップＳ５３で復号されたブロック画素データ列に含まれる画素データを、所定数ごとに予め定められた順番で配列され、予め定められた形状の矩形領域が順次復元され、ステップＳ５５で、画像データ復元部３１６により、ステップＳ５４で順次復元された矩形領域が、復元された順に所定方向に隣接するように配列され、指定されたブロックのブロック画像データが復元され、ステップＳ５６で、ステップＳ５５で復元されたブロック画像データが、液晶表示装置などの出力部３５０に出力される。また、ステップＳ５５で復元されたブロック画像データは、通信部およびネットワークを介して他のＰＣに送信されてもよいし、外部記憶装置により記録媒体に記録されてもよい。
【０１５０】
なお、第４の実施の形態においては、画像復号装置３００は、第３の実施の形態における画像符号化装置２００Ａにより画像データがブロックごとに符号化された符号化データからブロック画像データを復元するようにしたが、指定受付部３１１で画像データに含まれる全ブロックの指定が受付けられることにより、画像データがブロックごとに符号化された符号化データから画像データ全体を復元することができる。また、画像データ全体を１つのブロックとみなして、第１の実施の形態の変形例における画像符号化装置２００により画像データが全体として一括して符号化された符号化データから画像データ全体を復元することができる。
【０１５１】
以上説明したように、第４の実施の形態における画像復元装置３００においては、画像データのうち、復元するブロックの指定が受付けられ、第３の実施の形態における画像符号化装置２００Ａにより画像データが符号化された符号化データ列から読出された指定されたブロックに対応するブロック符号化データ列が、辞書に基づいた符号化方式の復号方法で、ブロック画素データ列として復号され、復号されたブロック画素データ列に含まれる画素データが所定数ごとに配列され順次復元された矩形領域が、復元された順に配列され、指定されたブロックの画像データが復元される。その結果、画像データ全体を復号することなしに、局所的なブロック画像データのみを復元することができる。
【０１５２】
なお、第４の実施の形態においては、画像復号装置３００で行われる処理について説明したが、図１３に示した処理をコンピュータで実行する画像復号方法、図１３に示した処理をコンピュータに実行させるための画像復号プログラム、および、画像復号プログラムを記録したコンピュータ読取可能な記録媒体として発明を捕らえることができる。
【０１５３】
［第５の実施の形態］
第３の実施の形態においては、画像符号化装置２００Ａが画像データを１つの形状の矩形領域に分割して、ブロックごとに符号化する場合について説明した。
【０１５４】
第５の実施の形態においては、画像符号化装置２００Ｂが画像データを２つの形状の矩形領域に分割してブロックごとに符号化して、２つの符号化データのうち、短く符号化される符号化データをブロックごとに出力する場合について説明する。
【０１５５】
第５の実施の形態における画像符号化装置２００Ｂの構成は、図１で説明した第１の実施の形態における符号化前処理装置１００の構成と同様である。
【０１５６】
図１４は、第５の実施の形態における画像符号化装置２００Ｂの機能の概略を示す機能ブロック図である。図１５は、第５の実施の形態における画像符号化装置２００Ｂで処理されるデータを示す図である。図１４を参照して、画像符号化装置２００Ｂの制御部２１０Ｂは、第１画像分割部２２１Ａと、第２画像分割部２２１Ｂと、ブロック分割部２１６Ａと、第１矩形領域読出部２２２Ａと、第２矩形領域読出部２２２Ｂと、第１画素データ配列部２２３Ａと、第２画素データ配列部２２３Ｂと、第１画素データ符号化部２２５Ａと、第２画素データ符号化部２２５Ｂと、符号化データ列比較部２１７と、符号化データ列選択部２１８とを含む。また、画像符号化装置２００Ｂの記憶部２３０は、図９で説明した画像符号化装置２００の記憶部２３０と同様であり、画像記憶部２３１と、符号化データ記憶部２３２とを含む。
【０１５７】
第１画像分割部２２１Ａ、および、第２画像分割部２２１Ｂは、それぞれ、画像記憶部２３１に記憶された画像データを、所定数の画素データを含む予め定められた第１の形状の矩形領域、および、第２の形状の矩形領域に分割する。隣接する所定数の画素データを含む予め定められた第１の形状の矩形領域とは、たとえば、隣接する８個の画素データを含み、幅が８画素分で高さが１画素分の形状の矩形の領域であり、具体的には、図７（ａ）で説明したライン３５ａ〜３８ａである。図１５（ａ）は、画像データを示す図である。図１５（ａ）を参照して、所定数の画素データを含む予め定められた第２の形状の矩形領域とは、たとえば、隣接する８個の画素データを含み、幅が１画素分で高さが８画素分の形状の領域であり、具体的には、ライン３５ｂ〜３８ｂである。
【０１５８】
なお、本実施の形態においては、幅あるいは高さが１画素分である矩形領域を、便宜的に、ラインという。ライン３５ｂは、隣接する８個の画素データａ１１〜ａ８１を含む１画素×８画素の形状の矩形領域である。同様に、ライン３６ｂ〜３８ｂは、それぞれ、画素データａ１２〜ａ８２、および、画素データａ１３〜ａ８３、および、画素データａ（ｍ−７）ｎ〜ａｍｎを含む１画素×８画素の形状の矩形領域である。
【０１５９】
また、所定数は、辞書に基づいた符号化方式の辞書に相当する参照される画素データの数以下とする。つまり、矩形領域に含まれる画素データの数は、ＬＺ７７などの辞書に基づいた符号化方式の参照部に含むことのできる画素データの数以下とする。
【０１６０】
ブロック分割部２１６Ａは、画像記憶部２３１に記憶された画像データを、隣接する複数の第１の形状の矩形領域からなる領域であるとともに、隣接する複数の第２の形状の矩形領域からなる領域であるブロックに分割する。第５の実施の形態において、ブロックは、図１０（ａ）に示した８画素×８画素の領域とする。この場合、幅が８画素分で高さが１画素分である第１の形状の矩形領域、具体的には、図１０（ａ）で示したライン３５ａ〜３８ａが縦に８個隣接する形状の領域であるとともに、幅が１画素分で高さが８画素分である第２の形状の矩形領域、具体的には、図１５（ａ）で示したライン３５ｂ〜３８ｂが横に８個隣接する形状の領域である。
【０１６１】
第１矩形領域読出部２２２Ａ、および、第２矩形領域読出部２２２Ｂは、ブロック分割部２１６Ａで分割されたブロックごとに、それぞれ、隣接する第１の形状の矩形領域、および、第２の形状の矩形領域を、順に第１の方向および第２の方向に読出す。第１矩形領域読出部２２２Ａは、図７（ｂ）で説明したように矩形領域を読出す。図１５（ｂ）は、第２の形状の矩形領域を読出す順番を示す図である。図１５（ｂ）を参照して、第２矩形領域読出部２２２Ｂは、たとえば、ライン３５ｂを読出した後に、ライン３５ｂに隣接するライン３６ｂを読出す。同様に、ライン３６ｂを読出した後に、ライン３７ｂを読出す。そして、最後に、ライン３８ｂを読出す。
【０１６２】
第１画素データ配列部２２３Ａ、および、第２画素データ配列部２２３Ｂは、ブロックごとに、それぞれ、第１矩形領域読出部２２２Ａ、および、第２矩形領域読出部２２２Ｂにより読出された第１の形状の矩形領域、および、第２の形状の矩形領域に含まれる画素データを、予め定められた順番で部分画像データ列として１次元に配列する。
【０１６３】
第１の形状の矩形領域について予め定められた順番とは、たとえば、８画素×１画素の形状の矩形領域であるラインにおいて、左から右に向かう順番である。図１５（ｃ）は、第２の形状の矩形領域に含まれる画素データを１次元に配列する順番を示す図である。図１５（ｃ）を参照して、第２の形状の矩形領域について予め定められた順番とは、第２の形状の矩形領域３０ｂに含まれる画素データｂ１〜ｂ８を１次元に配列する順番であり、ｂ１→ｂ２→ｂ３→ｂ４→ｂ５→ｂ６→ｂ７→ｂ８の順番である。
【０１６４】
このように、矩形領域に含まれる画素データを予め定められた順番で１次元に配列することにより、たとえば、隣接する２つのライン３５ａ，３６ａにそれぞれ含まれる画像データａ１１〜ａ１８と画素データａ２１〜ａ２８とが、それぞれ、同じ順番で部分画素データ列｛ａ１１，ａ１２，ａ１３，ａ１４，ａ１５，ａ１６，ａ１７，ａ１８｝，｛ａ２１，ａ２２，ａ２３，ａ２４，ａ２５，ａ２６，ａ２７，ａ２８｝として、１次元に配列されることとなる。また、隣接する２つのライン３５ｂ，３６ｂにそれぞれ含まれる画像データａ１１〜ａ８１と画素データａ１２〜ａ８２とが、それぞれ、同じ順番で部分画素データ列｛ａ１１，ａ２１，ａ３１，ａ４１，ａ５１，ａ６１，ａ７１，ａ８１｝，｛ａ１２，ａ２２，ａ３２，ａ４２，ａ５２，ａ６２，ａ７２，ａ８２｝として、１次元に配列されることとなる。
【０１６５】
そして、画素データａ１１に対応する画素と画素データａ２１に対応する画素とは、隣接する画素である。また、画素データａ１１に対応する画素と画素データａ１２に対応する画素とは、隣接する画素である。
【０１６６】
このため、画像データにおいては、画素データａ１１と画素データａ２１とが、同一である蓋然性が高い。また、画素データａ１１と画素データａ１２とが、同一である蓋然性が高い。同様に、画素データａ１２〜ａ１８と画素データａ２２〜ａ２８とが、同一である蓋然性が高い。また、画素データａ２１〜ａ８１と画素データａ２２〜ａ８２とが、同一である蓋然性が高い。
【０１６７】
したがって、隣接する２つのライン３５ａ，３６ａは、同一である蓋然性が高くなり、隣接する２つのライン３５ａ，３６ａがそれぞれ１次元に配列された部分画素データ列｛ａ１１，ａ１２，ａ１３，ａ１４，ａ１５，ａ１６，ａ１７，ａ１８｝，｛ａ２１，ａ２２，ａ２３，ａ２４，ａ２５，ａ２６，ａ２７，ａ２８｝は、同一である蓋然性が高くなる。また、隣接する２つのライン３５ｂ，３６ｂは、同一である蓋然性が高くなり、隣接する２つのライン３５ｂ，３６ｂがそれぞれ１次元に配列された部分画素データ列｛ａ１１，ａ２１，ａ３１，ａ４１，ａ５１，ａ６１，ａ７１，ａ８１｝，｛ａ１２，ａ２２，ａ３２，ａ４２，ａ５２，ａ６２，ａ７２，ａ８２｝は、同一である蓋然性が高くなる。
【０１６８】
第１画素データ出力部２２４Ａ、および、第２画素データ出力部２２４Ｂは、それぞれ、第１画素データ配列部２２３Ａ、および、第２画素データ配列部２２３Ｂにより、配列された第１の部分画素データ列、および、第２の部分画素データ列を、それぞれの矩形領域が読出された順番で第１の全画素データ列、および、第２の全画素データ列として出力する。第１画素データ出力部２２４Ａから出力される第１の全画素データ列は、図７（ｃ）で説明した全画素データ列４１ａと同様である。図１５（ｄ）は、第２画素データ出力部２２４Ｂから出力される第２の全画素データ列４１ｂを示す図である。図１５（ｄ）を参照して、全画素データ列４１ｂは、配列された第２の部分画素データ列を、図７（ｂ）で説明した矩形領域が読出された順番で連続するようにした１次元データ列である。
【０１６９】
具体的に、全画素データ列４１ｂは、たとえば、矩形領域３５ｂに含まれる部分画素データ列｛ａ１１，ａ２１，ａ３１，ａ４１，ａ５１，ａ６１，ａ７１，ａ８１｝、矩形領域３６ｂに含まれる部分画素データ列｛ａ１２，ａ２２，ａ３２，ａ４２，ａ５２，ａ６２，ａ７２，ａ８２｝、矩形領域３７ｂに含まれる部分画素データ列｛ａ１３，ａ２３，ａ３３，ａ４３，ａ５３，ａ６３，ａ７３，ａ８３｝、…、矩形領域３８ｂに含まれる部分画素データ列｛ａ（ｍ−７）ｎ，ａ（ｍ−６）ｎ，ａ（ｍ−５）ｎ，ａ（ｍ−４）ｎ，ａ（ｍ−３）ｎ，ａ（ｍ−２）ｎ，ａ（ｍ−１）ｎ，ａｍｎ｝の順番で連続するようにした１次元データ列であり、｛ａ１１，ａ２１，ａ３１，ａ４１，ａ５１，ａ６１，ａ７１，ａ８１，ａ１２，ａ２２，ａ３２，ａ４２，ａ５２，ａ６２，ａ７２，ａ８２，ａ１３，ａ２３，ａ３３，ａ４３，ａ５３，ａ６３，ａ７３，ａ８３，…，ａ（ｍ−７）ｎ，ａ（ｍ−６）ｎ，ａ（ｍ−５）ｎ，ａ（ｍ−４）ｎ，ａ（ｍ−３）ｎ，ａ（ｍ−２）ｎ，ａ（ｍ−１）ｎ，ａｍｎ｝である。
【０１７０】
第１画素データ符号化部２２５Ａ、および、第２画素データ符号化部２２５Ｂは、第１画素データ出力部２２４Ａ、および、第２画素データ出力部２２４Ｂによりそれぞれ出力された第１の全画素データ列、および、第２の全画素データ列を符号化して、それぞれ、第１の符号化データ列、および、第２の符号化データ列を生成する。
【０１７１】
符号化データ列比較部２１７は、ブロックごとに、第１画素データ符号化部２２５Ａ、および、第２画素データ符号化部２２５Ｂで符号化された第１の符号化データ列のデータ長と、第２の符号化データ列のデータ長とを比較する。
【０１７２】
符号化データ列選択部２１８は、ブロックごとに、符号化データ列比較部２１７で比較されたデータ長が短い符号化データ列を、出力するための符号化データ列として選択する。そして、符号化データ列選択部は２１８は、ブロックごとに読出可能なデータとして、選択された符号化データ列を、記憶部２３０の符号化データ記憶部２３２に記憶させる。また、選択された符号化データ列は、通信部およびネットワークを介して他のＰＣに送信されてもよいし、外部記憶装置により記録媒体に記録されてもよい。
【０１７３】
符号化データ記憶部２３２は、符号化データ列選択部２１８で選択された符号化データ列を記憶する。ここでは、符号化データ列選択部２１８で選択された符号化データ列を記憶部２３０の符号化データ記憶部２３２に記憶するようにしたが、これに限定されず、符号化データ列選択部２１８で選択された符号化データ列は、通信部およびネットワークを介して他のＰＣに送信されてもよいし、外部記憶装置１７０により記録媒体に書込まれてもよい。
【０１７４】
なお、画像データ全体を１つのブロックとみなすことによって、画像データ全体を一括して符号化することができる。
【０１７５】
図１６は、第５の実施の形態における画像符号化装置２００Ｂで実行される画像符号化処理の流れを示すフローチャートである。図１６を参照して、まず、ステップＳ８１で、画像記憶部２３１に画像データが記憶される。画像データは、入力部のスキャナなどの画像を入力するための装置から入力されてもよいし、他のＰＣからネットワークおよび通信部を介して受信されてもよいし、外部記憶装置により記録媒体から読出されてもよい。
【０１７６】
そして、ステップＳ８２で、第１画像分割部２２１Ａにより、ステップＳ８１で記憶された画像データが、所定数の画素データを含む予め定められた第１の形状の矩形領域に分割される。
【０１７７】
また、ステップＳ８３で、第２画像分割部２２１Ｂにより、ステップＳ８１で記憶された画像データが、所定数の画素データを含む予め定められた第２の形状の矩形領域に分割される。
【０１７８】
次に、ステップＳ８４で、ブロック分割部２１６Ａにより、ステップＳ８１で記憶された画像データが、隣接する複数の第１の形状の矩形領域からなる領域であるとともに、隣接する複数の第２の形状の矩形領域からなる領域であるブロックに分割される。
【０１７９】
そして、ステップＳ８５〜ステップＳ９６が、それぞれのブロックについて実行される。
【０１８０】
まず、ステップＳ８６で、第１矩形領域読出部２２２Ａにより、隣接する第１の形状の矩形領域が、順に第１の方向に読出され、ステップＳ８７で、第１画素データ配列部２２３Ａにより、ステップＳ８６で読出された第１の形状の矩形領域に含まれる画素データが、予め定められた順番で第１の部分画素データ列として１次元に配列される。
【０１８１】
次に、ステップＳ８８で、第１画素データ出力部２２４Ａにより、ステップＳ８７で配列された第１の部分画素データ列が、ステップＳ８６で第１の形状の矩形領域が読出された順番で第１の全画素データ列として出力される。
【０１８２】
そして、ステップＳ８９で、第１画素データ符号化部２２５Ａにより、ステップＳ８８で出力された第１の全画素データ列が、辞書に基づいた符号化方式、たとえば、ＬＺ７７による符号化方式で符号化され、第１の符号化データ列が生成される。
【０１８３】
また、ステップＳ９０で、第２矩形領域読出部２２２Ｂにより、隣接する第２の形状の矩形領域が、順に第２の方向に読出され、ステップＳ９１で、第２画素データ配列部２２３Ｂにより、ステップＳ９０で読出された第２の形状の矩形領域に含まれる画素データが、予め定められた順番で第２の部分画素データ列として１次元に配列される。
【０１８４】
次に、ステップＳ９２で、第２画素データ出力部２２４Ｂにより、ステップＳ９１で配列された第２の部分画素データ列が、ステップＳ９０で第２の形状の矩形領域が読出された順番で第２の全画素データ列として出力される。
【０１８５】
そして、ステップＳ９３で、第２画素データ符号化部２２５Ｂにより、ステップＳ９２で出力された第２の全画素データ列が、辞書に基づいた符号化方式、たとえば、ＬＺ７７による符号化方式で符号化され、第２の符号化データ列が生成される。
【０１８６】
ここで、ステップＳ８６〜ステップＳ８９と、ステップＳ９０〜ステップＳ９５とは、連続処理により実行されるようにしたが、並列処理により実行されるようにしてもよい。
【０１８７】
次に、ステップＳ９４で、符号化データ列比較部２１７により、ステップＳ８９で符号化された第１の符号化データ列のデータ長と、ステップＳ９３で符号化された第２の符号化データ列のデータ長とが比較され、ステップＳ９５で、符号化データ列選択部２１８により、ステップＳ９４で比較されたデータ長が短い符号化データ列が、出力するための符号化データ列として選択される。
【０１８８】
以上説明したステップＳ８５〜ステップＳ９６がすべてのブロックについて実行された後、ステップＳ９７で、ステップＳ９５で選択された符号化データ列が符号化データ記憶部２３２に記憶される。ここでは、符号化データ列を記憶部２３０の符号化データ記憶部２３２に記憶するようにしたが、これに限定されず、符号化データ列は、通信部およびネットワークを介して他のＰＣに送信されてもよいし、外部記憶装置により記録媒体に書込まれてもよい。
【０１８９】
なお、画像データ全体を１つのブロックとみなすことにより、画像データ全体を一括して符号化することができる。
【０１９０】
以上説明したように、第５の実施の形態における画像符号化装置２００Ｂにおいては、画像データは、複数の第１の形状の矩形領域３５ａ，３６ａ，…からなるとともに、複数の第２の形状の矩形領域３５ｂ，３６ｂ，…からなるブロック５１…に分割され、分割されたブロック５１，…が、第１の形状の矩形領域３５ａ，３６ａ，…に分割されるとともに、第２の形状の矩形領域３５ｂ，３６ｂ，…に分割され、ブロック５１，…ごとに、順に第１の方向および第２の方向に読出された第１の形状の矩形領域３５ａ，３６ａ，…および第２の形状の矩形領域３５ｂ，３６ｂ，…に含まれる画素データが、それぞれ、第１の部分画素データ列および第２の部分画素データ列として配列され、ブロックごとに、第１の部分画素データ列および第２の部分画素データ列が、それぞれ、第１の形状の矩形領域および第２の形状の矩形領域が読出された順番で符号化された第１の符号化データ列のデータ長と、第２の符号化データ列のデータ長とが比較され、短い符号化データ列が、出力するための符号化データ列として選択される。
【０１９１】
このため、ブロックごとに、第１の形状の矩形領域に分割して符号化した第１の符号化データ列と、第２の形状の矩形領域に分割して符号化した第２の符号化データ列とを比較して、より短い符号化データ列を出力するために選択するので、ブロックごとに、より短い符号化データ列を出力することができる。その結果、画像データ全体として、さらに、圧縮率を向上させることができる。
【０１９２】
また、第５の実施の形態における画像符号化装置２００Ｂにおいて、画像データ全体を１つのブロックとみなした場合は、画像データが第１の形状の矩形領域に分割されるとともに、第２の形状の矩形領域に分割され、順に第１の方向および第２の方向で読出された第１の形状の矩形領域および第２の形状の矩形領域に含まれる画素データが、それぞれ、第１の部分画素データ列および第２の部分画素データ列として配列され、第１の部分画素データ列および第２の部分画素データ列が、それぞれ、第１の形状の矩形領域および第２の形状の矩形領域が読出された順番で符号化された第１の符号化データ列のデータ長と、第２の符号化データ列のデータ長とが比較され、短い符号化データ列が、出力するための符号化データ列として選択される。このため、画像データ全体を１つのブロックとして、より短い符号化データ列を出力することができる。その結果、辞書に基づいた符号化方式を用いて、圧縮率をより向上させることができる。
【０１９３】
なお、第５の実施の形態においては、画像符号化装置２００Ｂで行われる処理について説明したが、図１６に示した処理をコンピュータで実行する画像復号方法、図１６に示した処理をコンピュータに実行させるための画像復号プログラム、および、画像復号プログラムを記録したコンピュータ読取可能な記録媒体として発明を捕らえることができる。
【０１９４】
なお、第１の実施の形態から第５の実施の形態で用いた辞書に基づいた符号化化方式の例として、ＬＺ７７符号化方式を挙げて説明したが、これに限定されず、辞書に基づいて符号化をする方式であれば、他の方式であってもよい。
【０１９５】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【図面の簡単な説明】
【図１】第１の実施の形態における符号化前処理装置の構成の概略を示すブロック図である。
【図２】第１の実施の形態における符号化前処理装置の機能の概略を示す機能ブロック図である。
【図３】第１の実施の形態における符号化前処理装置で処理されるデータを示す図である。
【図４】第１の実施の形態における符号化前処理装置で実行される符号化前処理の流れを示すフローチャートである。
【図５】第１の実施の形態の変形例における画像符号化装置の機能の概略を示す機能ブロック図である。
【図６】第２の実施の形態における符号化前処理装置の機能の概略を示す機能ブロック図である。
【図７】第２の実施の形態における符号化前処理装置で処理されるデータを示す図である。
【図８】第２の実施の形態における符号化前処理装置で実行される符号化前処理の流れを示すフローチャートである。
【図９】第３の実施の形態における画像符号化装置の機能の概略を示す機能ブロック図である。
【図１０】第３の実施の形態におけるブロックを説明するための図である。
【図１１】第３の実施の形態における画像符号化装置で実行される画像符号化処理の流れを示すフローチャートである。
【図１２】第４の実施の形態における画像復号装置の機能の概略を示す機能ブロック図である。
【図１３】第４の実施の形態における画像復号装置で実行される画像復号処理の流れを示すフローチャートである。
【図１４】第５の実施の形態における画像符号化装置の機能の概略を示す機能ブロック図である。
【図１５】第５の実施の形態における画像符号化装置で処理されるデータを示す図である。
【図１６】第５の実施の形態における画像符号化装置で実行される画像符号化処理の流れを示すフローチャートである。
【図１７】画像データの各ライン単位での走査を説明するための図である。
【図１８】辞書に基づいた符号化方式を説明するための図である。
【符号の説明】
１１〜１４  ライン、２１，２２  １次元データ列、２４，２４ａ〜２４ｃ  参照部、２５，２５ａ〜２５ｃ  符号化部、３０〜３４  矩形領域、３０ｂ，３５ａ〜３８ａ，３５ｂ〜３８ｂ  ライン、４１，４１ａ，４１ｂ  全画素データ列、５１，５２  ブロック、１００，１００Ａ  符号化前処理装置、１１０，１１０Ａ  制御部、１１１  画像分割部、１１２  矩形領域読出部、１１３  画素データ配列部、１１４，１１４Ａ  画素データ出力部、１１５  画素データ符号化部、１１６  ライン読出部、１３０  記憶部、１３１  画像記憶部、１４０  入力部、１５０  出力部、１６０  通信部、１７０  外部記憶装置、１７１  記録媒体、２００，２００Ａ，２００Ｂ  画像符号化装置、２１０，２１０Ａ，２１０Ｂ  制御部、２１１  画像分割部、２１２  矩形領域読出部、２１３  画素データ配列部、２１４  画素データ出力部、２１５  画素データ符号化部、２１６，２１６Ａ  ブロック分割部、２１７  符号化データ列比較部、２１８  符号化データ列選択部、２２１Ａ  第１画像分割部、２２１Ｂ  第２画像分割部、２２２Ａ  第１矩形領域読出部、２２２Ｂ  第２矩形領域読出部、２２３Ａ  第１画素データ配列部、２２３Ｂ  第２画素データ配列部、２２４Ａ  第１画素データ出力部、２２４Ｂ  第２画素データ出力部、２２５Ａ  第１画素データ符号化部、２２５Ｂ  第２画素データ符号化部、２３０  記憶部、２３１  画像記憶部、２３２  符号化データ記憶部、３００  画像復号装置、３１０  制御部、３１１  指定受付部、３１２  符号化データ読出部、３１３  復号部、３１４  画素データ取得部、３１５  画素データ配列部、３１６  矩形領域配列部、３３０  記憶部、３３１  符号化データ記憶部、３４０  入力部、３５０  出力部、４００  符号化装置、５００  ネットワーク。
【図１】
2004215173.tif 000003
【図２】
2004215173.tif 000004
【図３】
2004215173.tif 000005
【図４】
2004215173.tif 000006
【図５】
2004215173.tif 000007
【図６】
2004215173.tif 000008
【図７】
2004215173.tif 000009
【図８】
2004215173.tif 000010
【図９】
2004215173.tif 000011
【図１０】
2004215173.tif 000012
【図１１】
2004215173.tif 000013
【図１２】
2004215173.tif 000014
【図１３】
2004215173.tif 000015
【図１４】
2004215173.tif 000016
【図１５】
2004215173.tif 000017
【図１６】
2004215173.tif 000018
【図１７】
2004215173.tif 000019
【図１８】
2004215173.tif 000020