(57)【要約】      （修正有）【課題】異なる特性を持つ画像が混在している画像、垂直方向や斜め方向のグラデーション画像でも、高い圧縮率の可逆符号化データを生成する。【解決手段】近傍一致情報符号化部１０２は、着目画素が複数の近傍画素のいずれかと等しい場合、近傍一致情報をライン比較部１０３に出力する。また、いずれとも異なる場合、着目画素の画素データを生データ記憶部１０５に出力する。ライン比較部１０３は、着目ラインの符号化データと直前のラインの符号化データとが一致しているか否かを示す制御信号と着目ラインの８個の符号化データをセレクタ１０４に出力する。セレクタ１０４は、制御信号をラインヘッダとして出力し、制御信号が一致していることを示す場合、生データ記憶部１０５に記憶された画素データを出力する。また、制御信号が不一致であることを示す場合、着目ラインの符号化データと生データ記憶部１０５に記憶された画素データを出力する。【選択図】図１
2008227864.tif 000002
【特許請求の範囲】
【請求項１】
入力されたライン毎の画素データについて、着目画素と同じ画素値の画素が、既に符号化された複数の近傍画素に存在する場合に、該当する近傍画素の相対位置を特定する情報を符号化データとして生成する生成手段と、
前記生成手段で生成された着目ラインのｎ画素分の符号化データと、前記着目ラインの１つ前のラインのｎ画素分の符号化データとを比較した結果を含む情報を出力する第１の出力手段と、
前記比較した結果が不一致であったことを示す場合、着目ラインのｎ画素分の符号化データを出力する第２の出力手段と、
前記生成手段で生成された着目ラインのｎ画素分の符号化データ内に、前記着目画素と同じ画素値を持つ近傍画素が存在しないことを示す符号化データが存在する場合、該当する着目画素の画素データを出力する第３の出力手段と
を備えることを特徴とする画像符号化装置。
【請求項２】
入力されたライン毎の画素データについて、着目画素と同じ画素値の画素が、既に符号化された複数の近傍画素に存在する場合に、該当する近傍画素の相対位置を特定する情報を符号化データとして生成する生成工程と、
前記生成工程で生成された着目ラインのｎ画素分の符号化データと、前記着目ラインの１つ前のラインのｎ画素分の符号化データとを比較した結果を含む情報を出力する第１の出力工程と、
前記比較した結果が不一致であったことを示す場合、着目ラインのｎ画素分の符号化データを出力する第２の出力工程と、
前記生成工程で生成された着目ラインのｎ画素分の符号化データ内に、前記着目画素と同じ画素値を持つ近傍画素が存在しないことを示す符号化データが存在する場合、該当する着目画素の画素データを出力する第３の出力工程と
を備えることを特徴とする画像符号化装置の制御方法。
【請求項３】
画像データを、水平方向ｎ画素、垂直方向ｍ画素で構成されるブロック単位に可逆符号化する画像符号化装置であって、
前記ブロック単位に画像データを入力する入力手段と、
入力したブロック内をラスタースキャンして、着目画素を可逆符号化する可逆符号化手段であって、前記着目画素と当該着目画素の近傍であって既に符号化された複数の近傍画素とを比較し、前記着目画素と同じ色の近傍画素が存在するか否かを示すと共に、前記着目画素と同じ色の近傍画素が存在する場合には該当する近傍画素の相対位置を特定する情報を符号化データとして生成する可逆符号化手段と、
前記ブロック内の着目ラインのｎ画素分の符号化データと、前記着目ラインの１つ前のラインのｎ画素分の符号化データとを比較する比較手段と、
該比較手段の比較結果を含む情報をラインヘッダとして出力する第１の出力手段と、
前記比較手段の比較結果が、不一致であったことを示す場合、着目ラインのｎ画素分の符号化データを前記ラインヘッダに後続して出力する第２の出力手段と、
前記可逆符号化手段で生成された着目ラインのｎ画素分の符号化データ内に、前記着目画素と同じ色を持つ近傍画素が存在しないことを示す符号化データが存在する場合、該当する着目画素の画素データを、出力する第３の出力手段と
を備えることを特徴とする画像符号化装置。
【請求項４】
更に、着目画素の近傍に位置する前記複数の近傍画素が示す色数を判定する色数判定手段を備え、
前記可逆符号化手段は、
前記色数判定手段で判定された色数が予め設定された色数以下の場合に、前記着目画素と前記複数の近傍画素との比較を行なって符号化データを生成し、
前記色数判定手段で判定された色数が前記予め設定された色数よりも多い場合には、無条件に、前記着目画素と同じ色を持つ近傍画素が存在しないことを示す符号化データを生成し、
前記第３の出力手段は、前記着目画素の各成分値を予測符号化し、当該予測符号化して得られた符号化データを、出力する
ことを特徴とする請求項３に記載の画像符号化装置。
【請求項５】
前記可逆符号化手段は、
前記着目画素を符号化する際の前記複数の近傍画素の比較の順序を、着目画素の真上の画素の符号化データに従って変更して、符号化データを生成することを特徴とする請求項３又は４に記載の画像符号化装置。
【請求項６】
画像データを、水平方向ｎ画素、垂直方向ｍ画素で構成されるブロック単位に可逆符号化する画像符号化装置の制御方法であって、
前記ブロック単位に画像データを入力する入力工程と、
入力したブロック内をラスタースキャンして、着目画素を可逆符号化する可逆符号化工程であって、前記着目画素と当該着目画素の近傍であって既に符号化された複数の近傍画素とを比較し、前記着目画素と同じ色の近傍画素が存在するか否かを示すと共に、前記着目画素と同じ色の近傍画素が存在する場合には該当する近傍画素の相対位置を特定する情報を符号化データとして生成する可逆符号化工程と、
前記ブロック内の着目ラインのｎ画素分の符号化データと、前記着目ラインの１つ前のラインのｎ画素分の符号化データとを比較する比較工程と、
該比較工程の比較結果を含む情報をラインヘッダとして出力する第１の出力工程と、
前記比較工程の比較結果が、不一致であったことを示す場合、着目ラインのｎ画素分の符号化データを前記ラインヘッダに後続して出力する第２の出力工程と、
前記可逆符号化工程で生成された着目ラインのｎ画素分の符号化データ内に、前記着目画素と同じ色を持つ近傍画素が存在しないことを示す符号化データが存在する場合、該当する着目画素の画素データを、出力する第３の出力工程と
を備えることを特徴とする画像符号化装置の制御方法。
【請求項７】
コンピュータが読込み実行することで、前記コンピュータを請求項１、又は３乃至５のいずれか１項に記載の画像符号化装置として機能させることを特徴とするコンピュータプログラム。
【請求項８】
水平方向ｎ画素、垂直方向ｍ画素で構成されるブロック単位に符号化された画像データを復号する復号装置であって、
前記ブロックの符号化データを入力する入力手段と、
入力したブロックの符号化データ中の、着目ラインの符号化データのラインヘッダが、着目ラインとその直前のラインの符号化データと一致することを示しているか否かを判定する判定手段と、
該判定手段によって一致していると判定された場合、直前のラインのｎ画素分の符号化データを、着目ラインのｎ個の符号化データとして出力し、前記判定手段によって不一致であると判定した場合には、前記ラインヘッダに後続するｎ画素分の符号化データを出力する出力手段と、
該出力手段で出力した符号化データを復号する復号手段であって、
着目ラインの着目画素の符号化データが、当該着目画素の近傍に位置し、既に復号済みの複数の近傍画素と一致することを示している場合には、該当する近傍画素の復号済みの画素データを着目画素の復号結果として出力し、
着目ライン中の着目画素の符号化データが、前記複数の近傍画素のいずれとも不一致であることを示している場合には、前記ラインヘッダ、又は、ｎ画素分の符号化データに後続する画素データから、復号結果の画素データを生成し、出力する復号手段と
を備えることを特徴とする復号装置。
【請求項９】
前記復号手段は、着目ライン中の着目画素の符号化データが、前記複数の近傍画素のいずれとも不一致であることを示している場合には、前記ラインヘッダ、又は、ｎ個の符号化データに後続する画素データが、予測符号化されているものとし、予測復号して出力することを特徴とする請求項８に記載の復号装置。
【請求項１０】
水平方向ｎ画素、垂直方向ｍ画素で構成されるブロック単位に符号化された画像データを復号する復号装置の制御方法であって、
前記ブロックの符号化データを入力する入力工程と、
入力したブロックの符号化データ中の、着目ラインの符号化データのラインヘッダが、着目ラインとその直前のラインの符号化データと一致することを示しているか否かを判定する判定工程と、
該判定工程によって一致していると判定された場合、直前のラインのｎ画素分の符号化データを、着目ラインのｎ個の符号化データとして出力し、前記判定工程によって不一致であると判定した場合には、前記ラインヘッダに後続するｎ画素分の符号化データを出力する出力工程と、
該出力工程で出力した符号化データを復号する復号工程であって、
着目ラインの着目画素の符号化データが、当該着目画素の近傍に位置し、既に復号済みの複数の近傍画素と一致することを示している場合には、該当する近傍画素の復号済みの画素データを着目画素の復号結果として出力し、
着目ライン中の着目画素の符号化データが、前記複数の近傍画素のいずれとも不一致であることを示している場合には、前記ラインヘッダ、又は、ｎ画素分の符号化データに後続する画素データから、復号結果の画素データを生成し、出力する復号工程と
を備えることを特徴とする復号装置の制御方法。
【請求項１１】
コンピュータが読込み実行することで、前記コンピュータを請求項８又は９に記載の画像符号化装置として機能させることを特徴とするコンピュータプログラム。
【請求項１２】
請求項７又は１１に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像データの符号化及び復号技術に関するものである。
【背景技術】
【０００２】
従来、文字、線画、ＣＧ画像など、同一画素値（色）、または同一画素配置の連続が多く見られる画像データを効率的に符号化することを目的として、各種符号化技術が提案されている。
【０００３】
その１つに、符号化対象ライン内の画素データと直上ラインのデータが全位置で一致するか否か、直上ラインを１または複数画素ずらして全画素位置が一致するかどうかを判定し、その判定結果に基づいて画素データを符号化するような技術がある（特許文献１）。
【０００４】
また、符号化の繰り返し、複写、生データの置換のいずれに該当するかを判定し、それによってデータ長を算出するような方法も提案されている（特許文献２）。
【特許文献１】特開平０８−２７２９７８号公報
【特許文献２】特開２００１-０５３６２０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上記の従来技術は、水平方向の上下ライン間で似たような画素の配置を持った画像、特定の周期性を持った画像、水平方向のグラデーション画像では、高い圧縮率が期待できる。
【０００６】
しかしながら、異なる特性を持つ画像が混在している画像、垂直方向や斜め方向のグラデーション画像などでは、高い圧縮率が期待できず、まだ改善の余地がある。
【０００７】
そこで、本発明は、このような画像に対しても高い圧縮率を得る可逆符号化及び復号技術を提供しようとするものである。
【課題を解決するための手段】
【０００８】
かかる課題を解決するため、例えば本発明の画像符号化装置は以下の構成を備える。すなわち、
入力されたライン毎の画素データについて、着目画素と同じ画素値の画素が、既に符号化された複数の近傍画素に存在する場合に、該当する近傍画素の相対位置を特定する情報を符号化データとして生成する生成手段と、
前記生成手段で生成された着目ラインのｎ画素分の符号化データと、前記着目ラインの１つ前のラインのｎ画素分の符号化データとを比較した結果を含む情報を出力する第１の出力手段と、
前記比較した結果が不一致であったことを示す場合、着目ラインのｎ画素分の符号化データを出力する第２の出力手段と、
前記生成手段で生成された着目ラインのｎ画素分の符号化データ内に、前記着目画素と同じ画素値を持つ近傍画素が存在しないことを示す符号化データが存在する場合、該当する着目画素の画素データを出力する第３の出力手段とを備える。
【発明の効果】
【０００９】
本発明によれば、異なる特性を持つ画像が混在している画像、垂直方向や斜め方向のグラデーション画像などでも、高い圧縮率が期待できる可逆符号化及びその復号が可能になる。
【発明を実施するための最良の形態】
【００１０】
以下、添付図面に従って本発明に係る実施形態を詳細に説明する。
【００１１】
［第１の実施形態］
図１は、本実施形態に係る画像符号化装置のブロック構成図である。本実施形態に係る画像符号化装置は、装置全体の制御を司る制御部１５０、ブロック分割部１００、タイルバッファ１０１、近傍一致情報符号化部１０２、ライン比較部１０３、セレクタ１０４、生データ記憶部１０５、符号列形成部１０７を備える。同図において、１０８、１０９は信号線である。
【００１２】
以下、図１を参照して、本実施形態に係る画像処理装置が行う画像符号化処理について説明する。 
なお、本実施形態に係る画像符号化装置が入力する符号化対象の画像データは、ＲＧＢカラー多値画像データであり、各コンポーネント（色成分）８ビットで０〜２５５の範囲の輝度値を表現した画素データにより構成されるものとする。符号化対象の画像データの並びは点順次、即ち、ラスタースキャン順に（言い換えば、ライン毎に画像データを入力することによって）各画素を並べ、その各画素はＲ，Ｇ，Ｂの順番でデータを並べて構成されるものとする。また、画像は水平方向Ｗ画素、垂直方向Ｈ画素により構成されるものとする。但し、入力する画像データはＲＧＢカラーに限らず、ＣＭＹＫやモノクロ画像でもよいことを付言しておく。カラー画像であれば、各画素の値（画素値）は色という概念に該当するであろうし、モノクロ画像であれば、各画素値は濃度という概念に該当するであろう。
【００１３】
まず、信号線１０８から符号化対象となる画像データが入力される。画素データの入力順序は上記の如く、ラスタースキャン順とし、各画素でＲ，Ｇ，Ｂの順番で成分データが入力されるものとする。Ｒ，Ｇ，Ｂをそれぞれ成分番号０，１，２と定義し、画像の左上隅を座標（０，０）として水平方向画素位置ｘ、垂直方向画素位置ｙにある画素の成分番号Ｃの値をＰ（ｘ，ｙ，Ｃ）と表すこととする。例えば、位置（ｘ、ｙ）＝（３，４）である画素が（Ｒ，Ｇ，Ｂ）＝（２５５，１２８，０）という値を持つ場合、Ｐ（３，４，０）＝２５５、Ｐ（３，４，１）＝１２８、Ｐ（３，４，２）＝０と表現する。
【００１４】
ブロック分割部１００は、入力画像を、予め設定された大きさのブロックに分割する。分割した画像はタイルバッファ１０１に格納される。実施形態では、１ブロックのサイズは水平方向８画素、垂直方向８画素の８×８画素として説明する。ただし、後述説明から明らかになるが、水平方向ｎ画素、垂直方向ｍ画素のサイズであっても構わない。
【００１５】
近傍一致情報符号化部１０２はタイルバッファ１０１に格納されるタイルデータをラスタースキャン順に１画素づつ取り出して、符号化を行う。
【００１６】
近傍一致情報符号化部１０２は、着目する画素Ｘの近傍にあって、既に符号化済みの位置にある複数の近傍画素を読込み、着目画素Ｘを符号化する。着目画素Ｘと複数の近傍画素の相対位置関係は図３に示す通りである。本実施形態の場合、近傍画素は、図示の如くＸａ，Ｘｂ，Ｘｃ，Ｘｄの４つである。ここで、着目する画素Ｘの位置を（ｘ、ｙ）とし、これを用いて近傍画素Ｘａ，Ｘｂ，Ｘｃ，Ｘｄを表すと以下の通りである。
Ｘａ＝(Ｐ(ｘ−１，ｙ，０)、Ｐ(ｘ−１，ｙ，１)、Ｐ(ｘ−１，ｙ，２))
Ｘｂ＝(Ｐ(ｘ，ｙ−１，０)、Ｐ(ｘ，ｙ−１，１)、Ｐ(ｘ，ｙ−１，２))
Ｘｃ＝(Ｐ(ｘ−１,ｙ−１, ０)、Ｐ(ｘ−１，ｙ−１，１)、Ｐ(ｘ−１，ｙ−１，２))
Ｘｄ＝(Ｐ(ｘ＋１，ｙ−１，０)、Ｐ(ｘ＋１，ｙ−１，１)、Ｐ(ｘ＋１，ｙ−１，２))
【００１７】
なお、着目画素Ｘが画像の境界位置にあるとき、近傍画素の中には、画像外の位置になることが起こり得る。このような画像外の画素の各成分は“０”であると見なして処理を行なう。なお、この値“０”は一例であって、如何なる値でも構わない。要は、符号化装置及び復号装置間で共通な値を用いるようにすれば良い。
【００１８】
近傍一致情報符号化部１０２は着目ブロックをラスタースキャンする。そして、近傍一致情報符号化部１０２は、着目ブロック中の着目画素Ｘと同じ色の画素がその近傍画素｛Ｘａ，Ｘｂ，Ｘｃ，Ｘｄ｝に存在するか否か、及び、同じ色を持つ画素が存在する場合にはその近傍画素の相対位置を判定する。そして、近傍一致情報符号化部１０２は、上記判定結果を示す情報を符号化データとして出力する（以下、この符号化データを、近傍一致情報という）。
【００１９】
具体的には、近傍画素｛Ｘａ，Ｘｂ，Ｘｃ，Ｘｄ｝と着目画素Ｘとを比較する場合の、その比較順はＸａ→Ｘｂ→Ｘｃ→Ｘｄとする。
【００２０】
ここで、仮に、Ｘ＝Ｘａである場合には、近傍一致情報符号化部１０２は「Ｃａ」を近傍一致情報として出力する。また、Ｘ＝Ｘｂである場合には「Ｃｂ」、Ｘ＝Ｘｃである場合には「Ｃｃ」、Ｘ＝Ｘｄである場合には「Ｃｄ」を出力する。そして、近傍画素｛Ｘａ，Ｘｂ，Ｘｃ，Ｘｄ｝中に、着目画素Ｘと同じ色の画素が存在しなかった場合、近傍一致情報符号化部１０２は「Ｃｎ」を出力する。
【００２１】
実際の近傍一致情報（符号化データ）Ｃａ、Ｃｂ、Ｃｃ、Ｃｄ、Ｃｎは、図６に示すようなバイナリコードである。図示の如く、符号長は、ほぼＣａ、Ｃｂ、Ｃｃ、Ｃｄ、Ｃｎの順に長くしている。これは、着目画素Ｘとその直前（左隣）の画素Ｘａや真上の画素Ｘｂが同じ色である確率が高いためである。ただし、これら近傍一致情報は、固定長としても良い。実施形態の場合、全部で５種類の符号語が定義できればよいので、固定長とするのであれば３ビットあれば十分である。
【００２２】
また、近傍一致情報符号化部１０２は、近傍画素｛Ｘａ，Ｘｂ，Ｘｃ，Ｘｄ｝内に着目画素Ｘと同じ色が存在しなかった場合に限って、着目画素Ｘの各成分値（８×３＝２４ビット）を、生データ記憶部１０５に格納する。この生データ記憶部１０５は、後述する説明から明らかにするが、８画素分の容量（＝３×８＝２４バイト）の容量を有する。
【００２３】
以上の結果、近傍一致情報符号化部１０２は８×８個の近傍一致情報を生成し、ライン比較部１０３に出力する。
【００２４】
ライン比較部１０３は、２ライン分の近傍一致情報、すなわち、８×２個の近傍一致情報を格納する内部メモリを有する。そして、ライン比較部１０３は、近傍一致情報符号化部１０２から１ライン分（８個）の近傍一致情報を入力して、その入力した１ライン分の近傍一致情報をセレクタ１０４に出力すると共に、以下に説明する制御信号を生成し、セレクタ１０４に出力する。以下、ライン比較部１０３が如何にして、この制御信号の生成するかについて説明する。
【００２５】
ライン比較部１０３は、近傍一致情報符号化部１０２から１ライン分の近傍一致情報（８個の近傍一致情報）を入力する度に、前ラインの８個の近傍一致情報とを互いに比較し、着目ラインと前ラインの各々の近傍一致情報が完全に一致しているか否かを判定する。そして、ライン比較部１０３は、その判定結果（比較結果）を制御信号としてセレクタ１０４に出力する。具体的には、次の通りである。
【００２６】
着目ラインがブロック中のｊ番目（０≦ｊ≦７）のラインであり、着目ラインの８個の近傍一致情報を仮にＮj（０），Ｎj（１）、Ｎj（２）…Ｎj（７）と定義する。
【００２７】
ライン比較部１０３は、変数ｉ（０≦ｉ≦７）の全ての値について、次式が満足するとき、制御信号として“１”をセレクタ１０４に出力する。
Ｎj(i)＝Ｎj-1（i)
【００２８】
また、ライン比較部１０３は、上記式が１つでも満足しない場合には、制御信号として“０”をセレクタ１０４に出力すると共に、次のラインの符号化データの入力に備えて、着目ラインの符号化データを内部メモリに格納する。
【００２９】
なお、ここでは、変数ｉとして説明しているが、これは便宜的なものであり、実際は、８個の比較回路と、それぞれの比較回路の出力を論理積するＡＮＤ回路で構成できる。
【００３０】
なお、ｊ＝０の場合、すなわち、着目ラインが着目ブロックの最初のラインであった場合、Ｎj-1（i)の全ては予め定めた近傍一致情報を持つものとして処理する（復号装置でも同様な値であるものと見なす）。
【００３１】
以上のようにして、ライン比較部１０３は、着目ブロックの８ライン分の近傍一致情報の出力と、各ライン毎の制御信号の出力処理を行なう。
【００３２】
次に、セレクタ１０４の処理内容を説明する。このセレクタ１０４は、ライン比較部１０３からの制御信号に従って、１ライン単位に次のような処理を行なう。
【００３３】
＜制御信号が“０”の場合＞
制御信号が“０”の場合は、着目ラインと前ラインとの近傍一致情報が完全一致ではないことを示している。そこで、先ず、セレクタ１０４は、この制御信号（１ビット）をラインヘッダとして出力し、それに後続するように、ライン比較部１０３から出力された着目ラインの近傍一致情報（８個）を符号列形成部１０７に出力する。また、このとき、着目ライン中において近傍一致情報が「Ｃｎ」となっているの個数をカウントする。これは、生データ記憶部１０５内に格納されている画素データの個数をカウントすることと等価でもある。それ故、セレクタ１０４は、生データ記憶部１０５に格納された生データを格納順に、且つ、カウントした個数分だけ読出し、符号列形成部１０７に出力する。なお、当然の事であるが、「Ｃｎ」の個数が“０”である場合、生データの出力は行なわない。図４（ａ）は、制御信号が“０”の場合に、セレクタ１０４が符号列形成部１０７に出力する符号化データのデータ構造を示している。
【００３４】
＜制御信号が“１”の場合＞
制御信号が“１”の場合は、着目ラインと前ラインとの近傍一致情報が完全一致していることを示している。この場合も、セレクタ１０４は、制御信号をラインヘッダとして符号列形成部１０７に出力する。そして、着目ライン中において近傍一致情報が「Ｃｎ」となっているの個数をカウントし、そのカウントした個数の生データを生データ記憶部１０５から読込み、符号列形成部１０７に出力する。つまり、制御信号が“１”の場合、セレクタ１０４は、着目ラインの８個の近傍一致情報を符号列形成部１０７に出力しない。また、「Ｃｎ」の個数が“０”である場合には、生データの出力も行なわない。図４（ｂ）は、制御信号が“１”の場合に、セレクタ１０４が符号列形成部１０７に出力する符号化データのデータ構造を示している。
【００３５】
実施形態では、１ブロックは８ラインで構成される。従って、セレクタ１０４は以上の処理を、８回行なうことになる。
【００３６】
次に、実施形態における符号列形成部１０７の処理について説明する。
【００３７】
符号列形成部１０７は、符号化処理に先立ち、ファイルヘッダを作成し、出力する。フィルヘッダには、画像データのサイズ（水平、垂直方向の画素数）、１ブロックのサイズ、色空間の種類（従って、色成分の数を特定するのと等価）、各成分のビット数等、復号に必要な情報が含まれる。この後、符号列形成部１０７は、セレクタ１０４から１ブロックの各ラインの符号化データを、ファイルヘッダに後続するして順次出力する処理を行なえばよい。
【００３８】
図５は、実施形態における画像符号化装置で生成される符号化画像データファイルの構造を示している。図示の如く、ファイルの先頭には、ファイルヘッダが格納される。そして、それに後続するように各ブロックの符号化データが格納される。各ブロックの符号化データは、図示の如く、１ブロックを構成する各ラインの符号化データで構成され、各ラインの符号化データは図４（ａ），（ｂ）のいずれかのデータ構造となる。復号する場合には、ファイルヘッダを解析し、１ブロックのサイズが仮にｎ×ｍ画素サイズであることが判明した場合には、ｎ個の符号化データで１ブロックのｎラインを復号することになる。
【００３９】
次に、実施形態における画像復号装置を説明する。図２は実施形態における画像復号装置のブロック構成図である。画像復号装置は、装置全体の制御を制御を司る制御部２５０、バッファ２０１、解析部２０２、近傍一致情報記憶部２０３、生データ記憶部２０４、セレクタ２０５、ラインバッファ２０６を備える。以下、同図の構成における処理内容を説明する。
【００４０】
バッファ２０１には、先に説明した画像符号化装置で符号化された画像データファイルのデータが順次格納される。なお、解析部２０２は、ファイルヘッダについての解析結果（画像のサイズ、ブロックサイズ等）を制御部２５０に通知する。これにより、制御部２５０は、各処理部に復号処理に必要な設定を行ない、復号を開始することになる。以下ファイルヘッダ以降の復号処理について説明する。なお、ここでも、ブロックサイズは８×８画素であり、色空間はＲＧＢ、各画素は８ビットの画像を復号するものとして説明する。
【００４１】
解析部２０２は、着目ブロックの着目ラインヘッダ（符号化装置で生成した各ラインの符号化データの先頭の制御信号）を解析する。
【００４２】
この結果、着目するラインの符号化データが、図４（ａ），（ｂ）のいずれのデータ構造かが判明する。説明を分かりやすくするため、復号処理におけるラインヘッダを、符号化装置のそれに合せるべく、以下、制御信号と呼ぶこととする。
【００４３】
＜制御信号が“０”の場合＞
解析部２０２は、制御信号に後続する１ライン分（８個）の近傍一致情報を近傍一致情報記憶部２０３に格納させる。つまり、前ラインの近傍一致情報を、現ラインの近傍一致情報で上書きする。このとき、近傍一致情報中に「Ｃｎ」のコードが何個あるかをカウントする。そして、カウント値が“１”以上である場合には、そのカウントした値で示される個数の生データをバッファ２０１から読出し、生データ記憶部２０４に格納する。
【００４４】
そして、解析部２０２は、近傍一致情報記憶部２０３、生データ記憶部２０４に復号処理に必要なデータの格納が終えると、セレクタ２０５に選択処理の開始要求信号を出力する。
【００４５】
セレクタ２０５は、この開始要求信号を入力すると、近傍一致情報記憶部２０３から順番に近傍一致情報を読出す。読出した近傍一致情報は、着目画素Ｘの符号化データでもある。そこで、着目画素Ｘの近傍一致情報が「Ｃｎ」であるかを判定する。「Ｃｎ」であると判定した場合、着目画素Ｘの生データは、生データ記憶部２０４に格納されているので、その生データを読出し、復号結果として出力する。
【００４６】
また、セレクタ２０５は、着目画素Ｘの近傍一致情報が「Ｃｎ」以外、すなわち、｛Ｃａ、Ｃｂ、Ｃｃ、Ｃｄ｝のいずれかであると判定したとする。この場合、セレクタ２０５は、その近傍一致情報に従い、図３、図６の関係から、近傍画素の画素の各成分のデータをラインバッファ２０６から読出し、それを着目画素の復号結果として出力する。以上の処理を１ライン分の近傍一致情報の個数（実施形態では８個）分だけ行なう。
【００４７】
＜制御信号が“１”の場合＞
制御信号が“１”であるのは、着目ラインの全近傍一致情報が、前ラインの近傍一致情報と等しいことを示している。従って、前ラインで用いた近傍一致情報記憶部２０３の記憶内容をそのまま用いる。つまり、近傍一致情報記憶部２０３のデータは更新されないお。
【００４８】
また、前ラインの復号処理で用いた、「Ｃｎ」のコードの個数もそのまま用いる。もし、「Ｃｎ」の個数は“１”以上であった場合には、制御信号に後続して、その数分の生データをバッファ２０１から読込み、生データ記憶部２０４に格納する。当然、前ラインの復号処理で用いたＣｎの個数が“０”であった場合には、着目ラインの符号化データは、制御信号のみであるので、バッファ２０１からは生データの読込みもしない。
【００４９】
この後、解析部２０２は、セレクタ２０５に、選択処理の開始要求信号を出力すればよい。セレクタ２０５の処理は、「制御信号が“１”の場合」と同じである。
【００５０】
以上の処理を、８回行なうことで、着目ブロックである８×８画素で構成される画像データが可逆的に復号（復元）できることになる。
【００５１】
なお、着目ブロックの先頭ラインを復号する場合や、各ラインの先頭画素を復号する場合、近傍画素Ｘａ、Ｘｂ，Ｘｃ，Ｘｄの幾つかは、ブロック外となる。このようなブロック外の画素の各成分値は“０”と見なして処理を行なえば良い。
【００５２】
また、実施形態では、符号化又は復号しようとする画素位置が、ブロックの先頭ライン、各ラインの先頭画素位置にある場合、近傍画素Ｘａ，Ｘｂ，Ｘｃ，Ｘｄのいくつかは、ブロック外となるという理由で、ブロック外となる近傍画素の各成分値を“０”であるものとして説明した。着目ブロックが、オリジナルの画像データの外周（境界）に接するときは、画像外となった近傍画素の各成分値を固定値として見なして処理するしかない。しかしながら、着目ブロックがオリジナルの画像データの外周のブロックよりも内側のブロックである場合、着目ブロック外の画素は現存する画素であることが約束される。
【００５３】
従って、着目ブロックが、オリジナル画像の境界位置よりも内側のブロックにある場合には、既に符号化したブロックの画素を参照して、近傍一致情報を生成するようにできる。この場合、次のような処理を行なえばよいであろう。
【００５４】
説明を簡単なものとするため、ここでは図１の画像符号化装置に適用する例を説明する。
【００５５】
図１におけるタイルバッファ１０１には、符号化単位の８×８よりも２ライン、２列多い１０×１０個の画素データを読込むようにする。これは、着目画素がブロックの境界位置にあったとしても、その近傍画素Ｘａ、Ｘｂ，Ｘｃ，Ｘｄを確保するためである。
【００５６】
符号化対象のオリジナル画像の左上隅を原点とし、符号化単位である８×８画素のブロックの左上隅位置を（ｘ，ｙ）とするとき、読込む１０×１０個の画素データは、座標（ｘ−１、ｙ−１）、座標（ｘ＋８、ｙ＋８）を対角線の両端部とする矩形範囲内の画素データとして定義できる。
【００５７】
そして、読込まれた１０×１０画素分のデータ中、座標（ｘ，ｙ）、（ｘ＋７，ｙ＋７）を対角線とする矩形を符号化ブロックとして処理すればよい。この結果、符号化しようとする着目画素位置が８×８画素のブロックの先頭ライン上にある、又は、ラインの先頭や後端にあっても、現存する近傍画素を参照して符号化処理を行なうことができる。
【００５８】
なお、１つのブロック分の符号化処理を終えた場合、座標ｘを“８”だけ増加させる。そして、オリジナル画像の右端位置のブロックについて符号化を終えた場合には、ｘ＝０に初期化し、ｙを“８”だけ増加させればよい。つまり、１０×１０個のデータを読込む場合、先頭及び最終ラインの２行、及び、左端及び右端の２列をオーバーラップして読込み、符号化する。
【００５９】
復号装置に適用する場合も同様である。この場合、図２のラインバッファ２０６は、復号しようとする着目ブロックの左、左上、上、右上のブロックの復号結果を格納するだけの容量を備えればよい。ただし、復号しようとする着目ブロックが、オリジナル画像の外周に位置する場合、オリジナル画像外となってしまう画素の各成分は固定値と見なして処理する。
【００６０】
以上であるが、本実施形態の符号化装置について検討すると、次のようなことが言える。
【００６１】
着目画素Ｘに対する近傍画素は図３に示すように、左隣、左斜め上、真上、右斜め上の４つある。着目画素Ｘは、この４つの画素のうち、いずれかを等しい場合、着目画素の符号化データは、図６の符号語Ｃａ、Ｃｂ，Ｃｃ，Ｃｄが生成される。従って、水平方向、垂直方向、斜め方向のグラディエーションについても高い圧縮率が期待できるのは容易に理解できよう。特に、ブロック中の着目ラインの近傍一致情報と前ラインの近傍一致情報が完全に一致し、尚且つ、着目ライン中に符号語Ｃｎが存在しない場合、着目ラインは、実に、ラインヘッダの１ビットにまで圧縮できることになる。
【００６２】
なお、上記実施形態では、１ブロックのサイズを８×８画素のサイズとしたが、これによって本発明が限定されるものではなく、ｎ×ｍ画素サイズとしても構わず、極端には、オリジナルの画像のサイズとしても構わない。但し、ブロックのサイズが大きいほど、２ライン分の近傍一致情報（符号化データ）が互いに一致する可能性は低くなる。従って、好ましくは、入力する可逆符号化対象の画像の水平、垂直方向の画素数と、その画像の読取り解像度をパラメータとして、ブロックサイズを決定することが望ましい。
【００６３】
［第１の実施形態の変形例］
上記第１の実施形態をコンピュータプログラムによって実現する例を第１の実施形態の変形例として以下に説明する。
【００６４】
図７は、本変形例における情報処理装置（例えばパーソナルコンピュータ）のブロック構成図である。
【００６５】
図中、１４０１はＣＰＵで、ＲＡＭ１４０２やＲＯＭ１４０３に記憶されているプログラムやデータを用いて本装置全体の制御を行うと共に、後述する画像符号化処理、復号処理のアプリケーションプログラムを実行する。１４０２はＲＡＭで、外部記憶装置１４０７や記憶媒体ドライブ１４０８、若しくはＩ／Ｆ１４０９を介して外部装置からダウンロードされたプログラムやデータを記憶する為のエリアを備える。また、ＲＡＭ１４０２は、ＣＰＵ１４０１が各種の処理を実行する際に使用するワークエリアも備える。１４０３はＲＯＭで、ブートプログラムや本装置の設定プログラムやデータを格納する。１４０４、１４０５は夫々キーボード、マウスで、ＣＰＵ１４０１に対して各種の指示を入力することができる。
【００６６】
１４０６は表示装置で、ＣＲＴや液晶画面などにより構成されており、画像や文字などの情報を表示することができる。１４０７はハードディスクドライブ装置等の大容量の外部記憶装置である。この外部記憶装置１４０７には、ＯＳ（オペレーティングシステム）や後述する画像符号化、復号処理の為のプログラム、符号化対象の画像データ、復号対象画像の符号化データなどがファイルとして保存されている。また、ＣＰＵ１４０１は、これらのプログラムやデータをＲＡＭ１４０２上の所定のエリアにロードし、実行することになる。
【００６７】
１４０８は記憶媒体ドライブで、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記憶媒体に記録されたプログラムやデータを読み出してＲＡＭ１４０２や外部記憶装置１４０７に出力するものである。なお、この記憶媒体に後述する画像符号化、復号処理の為のプログラム、符号化対象の画像データ、復号対象の画像の符号化データなどを記録しておいても良い。この場合、記憶媒体ドライブ１４０８は、ＣＰＵ１４０１による制御によって、これらのプログラムやデータをＲＡＭ１４０２上の所定のエリアにロードする。
【００６８】
１４０９はＩ／Ｆで、このＩ／Ｆ１４０９によって外部装置を本装置に接続し、本装置と外部装置との間でデータ通信を可能にするものである。例えは符号化対象の画像データや、復号対象の画像の符号化データなどを本装置のＲＡＭ１４０２や外部記憶装置１４０７、あるいは記憶媒体ドライブ１４０８に入力することもできる。１４１０は上述の各部を繋ぐバスである。
【００６９】
上記構成において、本装置の電源がＯＮになると、ＣＰＵ１４０１はＲＯＭ１４０３のブートプログラムに従って、外部記憶装置１４０７からＯＳをＲＡＭ１４０２にロードする。この結果、キーボード１４０４、マウス１４０５の入力が可能となり、表示装置１４０６にＧＵＩを表示することが可能になる。ユーザが、キーボード１４０４やマウス１４０５を操作し、外部記憶装置１４０７に格納された画像符号化用アプリケーションプログラムの起動の指示を行なうと、ＣＰＵ１４０１はそのプログラムをＲＡＭ１４０２にロードし、実行する。これにより、本装置が画像符号化装置として機能することになる。
【００７０】
以下、図８乃至図１０のフローチャートに従って、画像符号化プログラムの処理手順を説明する。
【００７１】
なお、以下の説明では、符号化対象の画像データは、外部記憶装置１４０７に格納されたカラー画像データファイルとし、符号化結果を外部記憶装置１４０７にファイルとして格納する例を説明する。ただし、符号化対象の画像データの発生源、及び、符号化結果の出力先はその種類は問わない。例えば、符号化対象の画像データの発生源は、イメージスキャナでも構わないし、出力先はネットワークでも構わない。また、以下の説明にて、各種バッファ、変数、テーブルは、ＲＡＭ１４０２等のメモリ中に確保しておくものとして説明する。また、符号化対象の画像データは水平方向の画素数がＷ、垂直方向の画素数がＨとし、共に、８の倍数であるものとして説明する。
【００７２】
また、以下では、１０×１０画素のデータを読込み、中央の８×８画素をブロック単位に符号化する例を説明する。これは、着目ブロックがオリジナルの画像データの境界よりも内側にある場合に、隣接するブロックの画素データを参照するためである。また、座標（ｘ，ｙ）の画素データをＰ（ｘ，ｙ）と表現する。ここで、ｘ、ｙの取り得る範囲は、本来は、
０≦ｘ≦Ｗ−１
０≦ｙ≦Ｈ−１
である。しかしながら、１０×１０画素データを読込むため、便宜的に、
−１≦ｘ≦Ｗ
−１≦ｙ≦Ｈ
とする。そして、変数ｘとｙのいずれか一方が“−１”である場合の画素Ｐ（ｘ，ｙ）の各成分値は“０”であるものとする。また、変数ｘがＷと等しい場合、或いは、変数ｙがＨと等しい場合も、画素Ｐ（ｘ，ｙ）の各成分値は“０”であるものとする。
【００７３】
先ず、ステップＳ１にて、ＣＰＵ１４０１は、符号化対象の画像データファイルのヘッダを解析し、符号化出力するファイルのヘッダを生成し、出力する。この際、出力ファイルのヘッダには、画像データのサイズ（水平方向画素数、垂直方向画素数）、色空間、各成分のビット数等、復号時に必要となる情報を含ませる。なお、ここでは、１ブロックのサイズを８×８の固定とみなしているので、ブロックのサイズは不要であるが、１ブロックのサイズをユーザが設定できる場合には、そのサイズもヘッダに格納することになる。また、イメージスキャナからの画像データを符号化する場合には、原稿サイズ、イメージスキャナの読取り解像度に基づき、水平及び垂直方向の画素数を求めることができる。また、これ以降、符号化処理で生成された符号化データは、作成したヘッダに後続するように格納されることになる。
【００７４】
次に、ＣＰＵ１４０１は、ステップＳ２にて、Ｗ個の符号化データ（近傍一致情報）をデータを格納するための配列変数Ｔ［］を初期化する。ここでは、Ｔ［０］乃至Ｔ［Ｗ−１］に、“０Ｂ”（Ｂはバイナリーを示す）を格納するものとするが、復号アプリケーションと同じ様にすればよいので、この値に限られるものではない。
【００７５】
次いで、ステップＳ３に進み、変数ｙを“０”で初期化し、ステップＳ４において変数ｘを“０”で初期化する。この変数ｘ、ｙは、符号化対象の８×８画素のブロックの左上隅画素位置を特定するために用いられる変数である。
【００７６】
次いで、ステップＳ５に進み、Ｐ（ｘ−１、ｙ−１）、Ｐ（ｘ，ｙ−１）、Ｐｘ＋１、ｙ−１）、…、Ｐ（ｘ−７，ｙ−１）、…、Ｐ（ｘ−１，ｙ）、…、Ｐ（ｘ＋８，ｙ＋８）の１０×１０画素データを入力する。ここで、読取り対象の画素のＸ、Ｙ軸の座標値の少なくとも一方が“−１”となった場合、その画素の各成分値は“０”と見なして入力するのは先に説明した通りである。また、Ｘ座標値がＷであるか、或いは、Ｙ座標値がＨである場合も、該当する画素の各成分値は“０”と見なす。
【００７７】
こうして、１０×１０画素分のデータを入力すると、以下のステップＳ６乃至ステップＳ２５において、着目ブロック内の８×８画素である画素Ｐ（ｘ、ｙ）乃至Ｐ（ｘ＋７，ｙ＋７）について符号化処理を行なう。着目ブロック内をラスタースキャンすることになるため、先ず、変数ｊ、ｉを“０”で初期化する（ステップＳ６、Ｓ７）。変数ｊは着目ブロックの垂直方向（Ｙ座標）の座標を示す変数であり、変数ｉは着目ブロックの水平方向（Ｘ軸方向）の座標を示す変数である。
【００７８】
次いで、ステップＳ８に進み、変数ＣＮＴを“０”で初期化する。この変数ＣＮＴは、着目ブロック内のｊ番目のライン中の“Ｃｎ”（図６参照）の符号化データ（近傍一致情報）の個数を計数するための変数である。
【００７９】
ステップＳ９では、フラグＦＬＡＧを初期値“１”を代入する。このフラグＦＬＡＧは、着目ブロック内のｊ番目のラインの全符号化データが、ｊ−１番目のラインの全符号化データを等しいか否かを判定するためのものである。初期値は２ラインの全符号化が互いに等しいものとして仮設定を行なう。
【００８０】
次いで、ステップＳ１０に進み、着目画素Ｐ（ｘ＋ｉ，ｙ＋ｊ）を符号化し、生成された符号化データを一時的にＲＡＭ１４０２内の適当な領域に記憶する。このステップＳ１０での符号化処理は、図３に示すように、着目画素Ｘと近傍画素Ｘａ，Ｘｂ，Ｘｃ，Ｘｄとを順番に比較し、一致する近傍画素が存在するかどうかを判定し、一致する近傍画素が存在した場合には、図６のテーブルを参照して、対応する符号化データを生成すればよい。
【００８１】
次に、ステップＳ１１に進み、着目画素Ｐ（ｘ＋ｉ，ｙ＋ｊ）の符号化データ（近傍一致情報）が“Ｃｎ”であったか否かを判定する。符号化データが“Ｃｎ”であった場合、着目画素と同じ色が近傍画素｛Ｘａ，Ｘｂ，Ｘｃ，Ｘｄ｝に存在しなかったことを示す。それ故、ステップＳ１２に進んで、変数ＣＮＴを“１”だけ増加させる。そして、ステップＳ１３にて、着目画素Ｐ（ｘ＋ｉ，ｙ＋ｊ）の各成分値をＲＡＭ１４０２に一時的に格納する。このステップＳ１３の処理は、第１の実施形態における生データ記憶部１０５（図１参照）に、着目画素データを格納することと等価の処理でもある。
【００８２】
また、ステップＳ１１において、着目画素Ｐ（ｘ＋ｉ，ｙ＋ｊ）の符号化データが“Ｃｎ”以外、すなわち、｛Ｃａ，Ｃｂ，Ｃｃ，Ｃｄ｝のいずれかであった場合、着目画素と同じ色が近傍画素｛Ｘａ，Ｘｂ，Ｘｃ，Ｘｄ｝内に存在することが約束される。従って、ステップＳ１２、１３の処理は行なわない。
【００８３】
ステップＳ１４では、着目画素Ｐ（ｘ＋ｉ，ｙ＋ｊ）の符号化データが、変数Ｔ［ｘ＋ｉ］に格納された符号化データと同じであるか否かを判定する。これは、着目画素の符号化データと、前ラインのＸ座標値が同じ箇所の符号化データとを比較していることに他ならない。両者が異なると判定した場合には、ステップＳ１５に進み、フラグＦＬＡＧを“０”に設定する。また、ステップＳ１６では、次のラインの符号化に備えて、変数Ｔ［ｘ＋ｉ］を、着目画素Ｐ（Ｘ＋ｉ，ｙ＋ｊ）の符号化データで更新する。
【００８４】
この後、処理はステップＳ１７に進み、変数ｉを“１”だけ増加させる。そして、ステップＳ１８にて、変数ｉの値が“７”以下であるか否か、すなわち、着目ブロック中のｊ着目画素位置が、ライン後端（８画素目）に到達したか否かを判断する。
【００８５】
「ｉ≦７」であると判断した場合には、ステップＳ１０乃至ステップＳ１７の処理を繰り返す。また、「ｉ＞７」（ｉ＝８）であると判定した場合、ステップＳ１９に進み、現在のＦＬＡＧの値をラインヘッダとして出力する。ＦＬＡＧの値が“１”であるのは、ｊ番目のラインの８個の符号化データの全てについて、ステップＳ１４の判定が「Ｙｅｓ」となった場合である。換言すれば、ｊ番目の８個の符号化データの全てについて、前ラインの８個の符号化データと完全一致した場合を意味する。また、ＦＬＡＧの値が“０”となるのは、ｊ番目の８個の符号化データの少なくとも１つが、前ライン中の符号化データと不一致であった場合を意味する。それ故、このステップＳ１９においてフラグＦＬＡＧを出力するのは、ラインヘッダを出力するのと等価の意味を持つ。
【００８６】
この後、ステップＳ２０に進み、フラグＦＬＡＧが“１”であったか否かを判断する。ＦＬＡＧ＝０の場合、着目ラインの８個の符号化データ中、少なくとも１つは前ラインの符号化データと不一致であったことになるので、ステップＳ２１にて、ＲＡＭ１４０２に一時的に記憶していた着目ラインの８個の符号化データを出力する。ＦＬＡＧ＝１であった場合には、着目ラインの符号化データは不要であるので、符号化データの出力は行なわない。
【００８７】
この後、ステップＳ２２に進み、変数ＣＮＴが“０”より大きい値であるか否かを判断する。すなわち、ＲＡＭ１４０２に格納された画素の生データの個数が１つ以上あるか否かを判断する。
【００８８】
ＣＮＴ＞０である場合には、ステップＳ２３に進み、ＲＡＭ１４０２に格納されたＣＮＴ個の画素データを格納順に読出し、出力する。
【００８９】
以上のようにして、着目ブロックの変数ｊで示されるラインの符号化データの出力が完了する。
【００９０】
この後、ステップＳ２４にて、変数ｊを“１”だけ増加させ、ステップＳ２５にて変数ｊの値が７以下であるか否かを判断する。ｊ≦７である場合には、着目ブロックの符号化が未完であることになるので、処理はステップＳ７に戻り、上記処理を行なう。
【００９１】
一方、ｊ＞７（ｊ＝８）であると判断した場合には、着目ブロックの全ラインの符号化処理を終えたことを意味する。それ故、ステップＳ２６にて、変数ｘを“８”増加させる。そして、ステップＳ２７にて、変数ｘの値が“Ｗ−８”よりも小さい値であるか否かを判断する。ｘ＜Ｗ−８であると判断した場合、右端のブロックまでの符号化が完了していないことになるので、ステップＳ５に戻る。
【００９２】
また、ｘ≧Ｗ−８であると判断した場合には、ステップＳ２８にて、変数ｙを“８”だけ増加させ、ステップＳ２９にて、変数ｙの値が“Ｈ−８”よりも小さい値であるかを判断する。ｙ＜Ｈ−８であると判断した場合、最下のブロックの符号化が完了していないことになるので、ステップＳ４に戻る。
【００９３】
また、ｙ≧Ｈ−８であると判断した場合には、符号化対象の画像全体の符号化処理が終了したことになるので、本処理を終える。
【００９４】
以上説明したように、本変形例によれば、先に説明した第１の実施形態における画像符号化装置と同様の処理をコンピュータプログラムによって実現でき、且つ、同様の作用効果を奏することも可能になる。
【００９５】
次に、符号化画像データを復号するコンピュータプログラムの処理手順を図１１、図１２のフローチャートに従って説明する。なお、本処理は、外部記憶装置１４０７内に格納された符号化画像データファイルを不図示のＧＵＩを用いて選択してあるものとする。
【００９６】
次に、先ず、ステップＳ５１では、復号対象のファイルのファイルヘッダを解析し、復号処理に必要な情報を取得する。
【００９７】
次いで、ステップＳ５２において、復号結果の画像の水平方向の画素数分の近傍一致情報を格納するための配列変数Ｔ［］をＲＡＭ１４０２に確保し、“０Ｂ”（Ｂはバイナリを示している）で初期化する。
【００９８】
次に、ステップＳ５３に進み、Ｗ＋３個の画素データを格納するための配列変数Ｄ［］をＲＡＭ１４０２に確保し、全画素の全色成分を“０”で初期化する。
【００９９】
この後、処理はステップＳ５４に進み変数ｙを“０”で初期化し、ステップＳ５５で変数ｘを“０”で初期化する。この変数ｘ、ｙは復号しようとするブロックの左上隅の座標を特定するために用いられる変数である。
【０１００】
次いで、ステップＳ５６で、変数ｊを“０”で初期化する。この変数ｊは、着目ブロック内の垂直方向位置（ライン）を特定するための変数である。
【０１０１】
ステップＳ５７では、復号対象のファイルから、ラインヘッダを読込み、ステップＳ５８ではそのラインヘッダのデータを変数ＦＬＡＧに格納する。
【０１０２】
ステップＳ５９では、変数ｉに初期値“０”を格納する。この変数ｉは、着目ブロック内の水平方向位置を特定するための変数である。
【０１０３】
ステップＳ６０では、ＦＬＡＧが“１”であるか否かを判定する。ＦＬＡＧ＝１である場合には、ステップＳ６１にて、配列変数Ｆ［ｉ］に配列変数Ｔ［Ｘ＋ｉ］を格納する。これは、ＦＬＡＧ＝１のとき、着目ライン中の符号化データは、前ラインの符号化データと同じであるからである。また、ＦＬＡＧ＝０であった場合には、ステップＳ６２に進み、復号対象のファイルから１画素分の符号化データを入力し、配列変数Ｆ［ｉ］に格納する。そして、ステップＳ６３にて、配列変数Ｔ［ｘ＋ｉ］にも、読取った符号化データを格納する。
【０１０４】
この後、ステップＳ６４で、変数ｉを“１”だけ増加させ、ステップＳ６５にて変数ｉが“７”以下である間、ステップＳ６０乃至Ｓ６４の処理を繰り返す。
【０１０５】
以上の結果、着目ブロック中の着目ライン（第ｊ番目のライン）の８つの符号化データが配列変数Ｆ［］に格納されることになる。そこで、ステップＳ６６以降では、着目ラインの復号処理を行なう。
【０１０６】
先ず、ステップＳ６６では、変数ｉを再び“０”で初期化する。この後、ステップＳ６７にて、配列変数Ｆ［ｉ］が、“Ｃｎ”（図６参照）であるか否かを判断する。Ｆ［ｉ］＝“Ｃｎ”であった場合には、復号対象ファイルから１画素分の生データ（２４ビット）を読込み、その生データを復号後の画素データとして、ＲＡＭ１４０２に確保された１ブロック分の復号画像領域に一時的に記憶する。また、Ｆ［ｉ］が“Ｃｎ”と等しくない、すなわち、Ｆ［ｉ］が符号化データ｛Ｃａ，Ｃｂ，Ｃｃ，Ｃｄ｝のいずれかと等しい場合には、ステップＳ６９に進み、配列Ｄ［］の中から、符号化データで示される１つの近傍画素データを入力し、それを復号後の画素データとして、ＲＡＭ１４０２に確保された１ブロック分の復号画像領域一時的に記憶する。
【０１０７】
この後、ステップＳ７０に進み、配列変数Ｄ［］内の該当する位置に、復号後の画素データを格納し、配列変数Ｄ［］を更新する。
【０１０８】
この後、ステップＳ７１にて、変数ｉを“１”だけ増加する。そして、ステップＳ７２にて、ｉ≦７であるか否かを判断する。ｉ≦７である場合にはステップＳ６７以降を繰り返す。
【０１０９】
また、ｉ＞７（ｉ＝８）となった場合、着目ブロック中の着目ラインの８画素の復号処理を終えたことになるので、ステップＳ７３にて、変数ｊを“１”だけ増加する、そして、ステップＳ７４にて、ｊ≦７であるか否かを判断する。ｊ≦７である場合には、着目ブロックの全ラインの復号が未完であることになるので、ステップＳ７に処理を戻す。
【０１１０】
また、ステップＳ７４にて、ｊ＞７（ｊ＝８）と判断した場合、着目ブロックの復号処理は終了したことを意味する。それ故、ＲＡＭ１４０２に確保された復号画像領域に格納されている８×８個の画素データを出力する。
【０１１１】
この後、処理はステップＳ７６にて、変数ｘを“８”だけ増加する処理を行ない。そして、ステップＳ７７にて、変数ｘの値が“Ｗ−８”よりも小さい値であるか否かを判断する。ｘ＜Ｗ−８であると判断した場合、右端のブロックの復号が未完であので、ステップＳ５７に戻る。
【０１１２】
また、ｘ≧Ｗ−８であると判断した場合には、ステップＳ７８にて、変数ｙを“８”だけ増加させ、ステップＳ７９にて、変数ｙの値が“Ｈ−８”よりも小さい値であるかを判断する。ｙ＜Ｈ−８であると判断した場合、最下のブロックの復号が完了していないことになるので、ステップＳ５５に戻る。
【０１１３】
また、ｙ≧Ｈ−８であると判断した場合には、画像全体の復号処理が終了したことになるので、本処理を終える。
【０１１４】
以上説明したように、本変形例によれば、先に説明した第１の実施形態における画像復号装置と同様の処理をコンピュータプログラムによって実現でき、且つ、同様の作用効果を奏することも可能になる。
【０１１５】
［第２の実施形態］
上記第１の実施形態、並びのその変形例からも容易に理解できるように、着目ブロック中の第ｊ番目のラインの符号化データ量が少なくできるのは、第ｊ番目のラインの８個の符号化データと、１つ前の第ｊ−１番目のラインの８個の符号化データが互いに一致する場合である。
【０１１６】
これを別な言い方をすれば、着目ライン中の第ｉ番目の画素の符号化データを生成する場合、前ラインのｉ番目の符号化データと同じとなる確率を高めれば、符号化効率を高めることが可能と言える。
【０１１７】
これを実現するには、着目画素Ｘと一致する近傍画素をサーチするとき、近傍画素の順番をＸａ→Ｘｂ→Ｘｃ→Ｘｄの固定順番とするのではなく、適応的に変更させることである。
【０１１８】
以下、この具体例を説明する。説明を簡単なものとするため、符号化対象の画像中の着目ブロックを含む領域には、黒、白の２種類の画素しか存在せず、黒い斜め線がある例を説明する。
【０１１９】
図１３（ａ）の画像は、このような画像の例である。着目ブロックの着目ラインが図示の符号１３０で示されるとする。このライン１３０の先頭の画素を着目画素Ｘとした場合、それに一致する近傍画素は左斜め上の画素Ｘｃ（図３参照）となる。従って、着目画素の符号化データ（近傍一致情報）は、“Ｃｃ”となる。以下同様にライン１３０の各画素の符号化データを求めると、ライン１３０の８個の符号化データは符号化データ列１３０ａのようになる。
【０１２０】
同様に、ライン１３１について符号化ことで、符号化データ列１３１ａが得られる。
【０１２１】
符号化データ列１３０ａと１３１ａとを比較すると、上下で同じ符号化データとなるペアの数は、図示の場合には２つとなる。
【０１２２】
ここで、ライン１３１の先頭画素が、符号化対象である着目画素Ｘである場合について考察する。
【０１２３】
この着目画素Ｘは、その左隣の画素Ｘａと同じ色であるが、着目画素Ｘの真上の画素と同様に、左斜め上の画素Ｘｃと一致すると考えても何等矛盾は生じないし、むしろＸｃと同じであると判定することが望ましいことがわかる。
【０１２４】
そこで、着目画素Ｘを符号化するとき、その真上の画素の符号化データで示される近傍画素と同じ方向にある近傍画素を優先的に比較するようにする。すなわち、着目画素Ｘの真上の画素の符号化データが“Ｃｃ”であったわけであるから、着目画素Ｘと比較する近傍画素Ｘｃを最初に比較するように、その優先順位を繰り上げる。残りは、基本となる順番通りである。この結果、着目画素Ｘと比較する近傍画素の順番は、Ｘｃ→Ｘａ→Ｘｂ→Ｘｄと変更される。なお、着目画素Ｘの真上の画素の符号化データが“Ｃｎ”である場合には、Ｘａ→Ｘｂ→Ｘｃ→Ｘｄの順番に比較する。
【０１２５】
この原理に従ってライン１３１を符号化した結果が、図１３（ｂ）の符号化データ列１３１ｂである。同図の符号化データ列１３０ａと１３１ｂとを比較すると、上下で同じ符号化データとなるペアの数は、図示の場合には４つなり、図１３（ａ）よりも一致するペアの数は増える。また、図１３（ｂ）では、上下の２ラインの符号化データは、残念ならが完全一致とはならない。しかしながら、３ライン目、４ライン目と符号化処理を行なっていくと、上下に隣接する２つラインの符号化データ列が完全一致する可能性は徐々に高くなる。また、単調な斜め方向の線やグラデーションの画像の場合、上下に隣接する２つのラインの符号化データは、高い確率で完全一致することになることは、容易に推察できよう。
【０１２６】
以上であるが、本第２の実施形態を第１の実施形態やその変形例に適用するのは、容易である。着目画素Ｘを符号化する場合（着目画素の近傍一致情報を生成する場合）、真上の画素の符号化データを参照し、比較する近傍画素の順番を適応的に並べ替える構成や処理を追加すれば良いからである。
【０１２７】
［第３の実施形態］
第３の実施形態を説明する。第１の実施形態及びその変形例では、ラインの符号化データ（近傍一致情報）を得た後、そのラインの符号化データと前ラインの符号化データとの一致／不一致の判定を行った。本第３の実施形態では、着目画素の近傍の画素に含まれる色数をも参照して、一致／不一致の判定を実施するか否かを切り替える例について説明する。また、第１の実施形態では、着目画素Ｘが近傍画素｛Ｘａ，Ｘｂ，Ｘｃ，Ｘｄ｝のいずれとも等しくない場合、着目画素Ｘは生データとして出力したが、本第３の実施形態では、このような場合にも、着目画素Ｘを可逆符号化する例を説明する。
【０１２８】
図１４は、第３の実施形態における画像符号化装置の構成を示している。図示において、図１と実質的に同じ機能を持つ処理部には同符号を付した。本装置は、装置全体の制御を司る制御部１５０、ブロック分割部１００、タイルバッファ１０１、近傍一致情報符号化部１０２、ライン比較部１０３、セレクタ１０４、符号列形成部１０７、色数判定部１３１、近傍一致情報符号化部１３２、成分値予測符号化部１３３を備える。以下、各構成の処理内容を説明する。
【０１２９】
＜色数判定部１３１の説明＞
色数判定部１３１は、タイルバッファ１０１に格納された１ブロック分の画像データ（８×８画素）をラスタースキャンし、そのスキャン中の着目画素Ｘの近傍画素｛Ｘａ，Ｘｂ，Ｘｃ，Ｘｄ｝に含まれる色数Ｎｃを検出する。以下は、実施形態における数Ｎｃの求め方の一例である。なお、近傍画素｛ｘａ，Ｘｂ，Ｘｃ，Ｘｄ｝は、既に符号化されていることに注意されたい。
【０１３０】
今、Ｘa，Ｘb，Ｘc，Ｘdの４画素から２画素のペアを取り出す６通りの組み合わせについて考察する。１つのペアを｛，｝で表現すると、６つのペアは次の通りである。
｛Ｘa，Ｘb｝
｛Ｘa，Ｘc｝
｛Ｘa，Ｘd｝
｛Ｘb，Ｘc｝
｛Ｘb，Ｘd｝
｛Ｘc，Ｘd｝
上記６つのペアの中に、同色のペアが幾つあるかをカウントして得られたカウント値から、４画素に含まれる色数Ｎｃを決定できる。つまり、カウント値が“０”であれば、Ｘa，Ｘb，Ｘc，Ｘdの全てが互いに異なる事を示しているので、色数Ｎｃは“４”と判定できる。カウント値が“１”（１ペアのみ互いに等しい場合）であれば色数Ｎｃは“３”であると判定できる。また、カウント値が“２”か“３”であれば、色数Ｎｃは“２”であり、カウント値が“６”であれば、色数Ｎｃは“１”であると判定できる。なお、カウント値が４、５となることはあり得ない。以上のようにすれば、簡単なハードウェアで実現できることも理解できよう。
【０１３１】
さて、色数判定部１３１は、上記のようにして求めた色数Ｎｃ（＝１、２、３、４のいずれか）を、近傍一致情報符号化部１０２及び成分値予測符号化部１３３に出力する。
【０１３２】
＜近傍一致情報符号化部１０２の説明＞
次に、実施形態における近傍一致情報符号化部１０２の処理内容を説明する。
【０１３３】
近傍一致情報符号化部１０２は、着目画素Ｘ、及び、その近傍画素｛Ｘａ，Ｘｂ，Ｘｃ，Ｘｄ｝と、色数判定部１３１からの色数Ｎｃとを入力する。そして、色数Ｎｃに従って、着目画素の符号化データを生成し、ライン比較部１０３に出力すると共に、着目画素Ｘが近傍画素のいずれかと等しいか否かを示す１ビットのフラグ信号Ｆを生成し、成分値予測符号化部１３３に出力する。
【０１３４】
近傍一致情報符号化部１０２は、着目画素と近傍画素｛Ｘａ，Ｘｂ，Ｘｃ，Ｘｄ｝と比較し、一致した近傍画素が存在する場合、図６に示したテーブルに従ってＣａ乃至Ｃｄのいずれか１つを近傍一致情報（符号化データ）として、出力すると共に、一致したことを示すためフラグＦとして“１”を成分値予測符号化部１３３に出力する。また、着目画素Ｘと同じ色を持つ近傍画素が１つも存在しなかった場合には、近傍一致情報符号化部１０２は、近傍一致情報（符号化データ）として“Ｃｎ”を出力し、一致する近傍画素が存在しなかったことを示すためフラグＦとして“０”を成分値予測符号化部１３３に出力する。
【０１３５】
なお、色数Ｎｃが“１”の場合、近傍画素｛Ｘａ，Ｘｂ，Ｘｃ，Ｘｄ｝が全て互いに同じ色である場合であるので、着目画素Ｘと比較するのは画素Ｘａのみで良い。Ｘ＝Ｘａであった場合には、近傍一致情報符号化部１０２は、符号語“Ｃａ”を近傍一致情報として出力し、フラグＦとして“１”を出力する。また、Ｘ≠Ｘａであった場合には、近傍一致情報符号化部１０２は、符号語“Ｃｎ”を近傍一致情報として出力し、フラグＦとして“１”を出力する。
【０１３６】
また、色数Ｎｃが“２”の場合、近傍画素Ｘａ→Ｘｂ→Ｘｃ→Ｘｄの順番に着目画素Ｘと比較する。そして、着目画素Ｘと一致する近傍画素はあった場合、その近傍画素の符号語（Ｃａ乃至Ｃｄ）を近傍一致情報として出力し、フラグＦとして“１”を出力する。なお、Ｎｃ＝２の場合、２つ目の色と比較しても、一致する近傍画素が存在しなかった場合には、それ以降の比較は不要である。例えば、Ｘａ＝Ｘｂ＝Ｘｄ≠Ｘｃの場合、着目画素Ｘと比較するするのは、近傍画素Ｘｃまでで良い。もし、Ｘ≠Ｘｃであった場合には、近傍一致情報（符号化データ）として“Ｃｎ”を出力し、フラグＦとして“０”を出力する。色数Ｎｃが“３”であった場合も同様である。
【０１３７】
なお、色数Ｎｃが“４”であった場合、すなわち、近傍画素｛Ｘａ，Ｘｂ，Ｘｃ，Ｘｄ｝が互いに異なる色であった場合、近傍一致情報符号化部１０２は、無条件に近傍一致情報として“Ｃｎ”を出力し、フラグＦとして“０”を出力する。色数Ｎｃが“４”であった場合、着目画素Ｘが近傍画素｛Ｘａ，Ｘｂ，Ｘｃ，Ｘｄ｝のいずれかと等しいことはあり得るが、その可能性は低いし、一致／不一致を識別するビットを生成することも冗長である。そこで、本実施形態では色数Ｎｃが“４”の場合にあっては、近傍一致情報符号化部１０２は符号語“Ｃｎ”を近傍一致情報として出力し、フラグＦとして“０”を出力する。
【０１３８】
図１５（ａ）、（ｂ）は、本第３の実施形態における近傍一致情報符号化部１０２が生成する近傍一致情報とフラグＦとの関係を示している。
【０１３９】
＜成分値予測符号化部１３３の説明＞
次に、本第３の実施形態における成分値予測符号化部１３３を説明する。本実施形態における成分値予測符号化部１３３は、近傍一致情報符号化部１０２からのフラグＦが“０”の場合に、着目画素Ｘの各成分値を予測符号化し、その結果をバッファ１３４に出力する。換言すれば、フラグＦが“１”である場合には、予測符号化処理を行なわない。
【０１４０】
図１６は、実施形態における成分値予測符号化部１３３のブロック構成図である。
【０１４１】
成分値予測符号化部１３３は、図示の如く、成分値予測部１００２、減算器１００３、予測誤差符号化部１００１を有する。
【０１４２】
成分値予測部１００２に供給される予測式選択信号ｍは、予め制御部１５０が供給しておく。この予測式選択信号ｍは、１つの画像を符号化する際に設定するものであって、画像全体の符号化するまでは固定である。
【０１４３】
成分値予測部１００２は、着目画素Ｘの着目成分の予測値ｐを、近傍画素Ｘａ，Ｘｂ，Ｘｃの同一成分値を参照すると共に、予測式選択信号ｍで決定された予測式に従って算出する。図１７は予測式選択信号ｍとその予測式との関係を示している。
【０１４４】
減算器１００３は、着目画素の着目成分値と、成分値予測部１００２から出力された予測値との差分を算出し、その差を予測誤差ｅとして予測誤差符号化部１００１に出力する。
【０１４５】
予測誤差符号化部１００１では減算器１００３からの予測誤差ｅをGolomb符号を用いて符号化する。Golomb符号は非負の整数値を符号化対象とし、パラメータ変数ｋによって異なる複数の確率モデルによる符号化が可能であるという特徴を持つ。また、Golomb符号化は、符号化対象シンボルとパラメータ変数ｋから符号語を導出することができるため、符号表が不要という利点がある。Golomb符号の一形態がＩＳＯとＩＴＵ−Ｔから国際標準勧告されるＪＰＥＧ−ＬＳ（ＩＳＯ／ＩＥＣ  １４４９５−１｜ＩＴＵ−Ｔ  Recommendation T.87）において予測誤差の符号化方式として採用されている。ここでは減算器１００３から出力される予測誤差ｅを次式により非負の整数値（Ｖとする）に変換した後に，これを選択したｋパラメータでGolomb符号化する．
Ｖ＝２×ｅ        （ｅ≧０の場合）
Ｖ＝−２×ｅ−１  （ｅ＜０の場合）
【０１４６】
符号化対象の非負の整数値Ｖを符号化パラメータｋでGolomb符号化する手順は次の通りである。まず、整数Ｖをｋビット右シフトして整数値ｍを求める。Ｖに対する符号はｍ個の「０」と、これに続く「１」（可変長部）、及び、その後に続く整数Ｖの下位ｋビット（固定長部）である。図１８にｋ＝０、１、２におけるGolomb符号の例を示しておく。ここに述べた符号の構成方法は一例であり、固定長部と可変長部の順序が逆にしても一意復号可能な符号を構成することができ、また、０と１を反対にして符号を構成することもできる。符号化パラメータｋの選択方法としては所定の単位で最適なｋパラメータの選択して符号列に含める方法など様々な手法が考えられるが、本実施形態ではＪＰＥＧ−ＬＳと同様の手法により符号化の過程で更新していく方法を用いる。
【０１４７】
以下、符号化パラメータｋの選択方法について述べる。予測誤差符号化部１００１には符号化済みの画素の数を保持するカウンタＮと、各成分毎に符号化済みの予測誤差の絶対値の合計を保持するカウンタＡ［Ｃ］（Ｃは成分番号であり、０〜２）とを備える。符号化の開始時点でカウンタＮを１に、とカウンタＡ［０］〜Ａ[２]を２に設定する。
【０１４８】
符号化対象の成分値ごとにＮ×２＾ｋ（ｘ＾ｙはｘのｙ乗を示す）がＡ［Ｃ］を超えない最大のｋを求め、これを用いて先に説明した手順にて予測誤差ｅをGolomb符号化し、符号語を出力する。各成分の符号化処理後にＡ［Ｃ］に予測誤差の絶対値｜ｅ｜を加算して更新する。またこの場合、全成分の符号化処理後にＮに１を加えて更新する。なお、Ａ［Ｃ］とＮを所定の範囲内に限定するためにはＮが一定値（例えば３２）に達したタイミングでＡ［Ｃ］とＮを１／２にするといった処理を適用すれば良い。
【０１４９】
なお、実施形態では、予測誤差符号化部１００１として、Golomb符号化を採用する例を示したが、可逆符号化であれば如何なる種類であっても構わない。例えば、ハフマンテーブルを用いて符号化するものでも構わない。
【０１５０】
実施形態では、１つの画素の成分がＲ、Ｇ、Ｂの３つである例を説明しているので、成分値予測符号化部１３３は、１つの画素についてＲ、Ｇ、Ｂの各成分の予測誤差符号化を行ない、その結果得られる３つの成分の符号化データを１セットしてバッファ１３４に出力し、格納する。
【０１５１】
ライン比較部１０３、セレクタ１０４、及び、符号列形成部１０７は第１の実施形態と同じである。
【０１５２】
すなわち、ライン比較部１０３は着目ブロックの着目ラインの８個の近傍一致情報とその真上のラインの８個の近傍一致情報とを比較し、全てが一致した場合にはライン一致を示す制御信号“１”をセレクタ１０４に出力する。また、１つでも不一致であった場合には、不一致を示す制御信号“０”をセレクタ１０４に出力し、次のラインの比較に備え、内部に記憶する。また、ライン比較部１０３は、制御信号を“１”、“０”のいずれに決定しても、着目ラインの８個の近傍一致情報をセレクタ１０４に出力する。
【０１５３】
セレクタ１０４は、ライン比較部１０３からの制御信号に従った処理を行なう。
【０１５４】
＜制御信号が“０”の場合＞
制御信号が“０”の場合（ライン不一致の場合）は、入力した制御信号（１ビット）をラインヘッダとして出力し、符号列形成部１０７に出力する。そして、それに後続するように、ライン比較部１０３から出力された着目ラインの近傍一致情報（８個）を符号列形成部１０７に出力する。また、このとき、着目ライン中において近傍一致情報が「Ｃｎ」となっているの個数をカウントする。これは、バッファ１３４内に格納されている予想符号化された画素数をカウントすることと等価でもある。それ故、セレクタ１０５は、バッファ１３４に格納された予測符号化データを、その格納順に、且つ、カウントした個数分だけ読出し、符号列形成部１０７に出力する。なお、当然の事であるが、「Ｃｎ」の個数が“０”である場合、予測符号化データの出力は行なわない。
【０１５５】
＜制御信号が“１”の場合＞
制御信号が“１”の場合は、着目ラインと前ラインとの近傍一致情報が完全一致していることを示している。この場合も、セレクタ１０４は、制御信号をラインヘッダとして符号列形成部１０７に出力する。そして、着目ライン中において近傍一致情報が「Ｃｎ」となっているの個数をカウントし、そのカウントした個数の生データをバッファ１３４から読込み、符号列形成部１０７に出力する。つまり、制御信号が“１”の場合、セレクタ１０４は、着目ラインの８個の近傍一致情報を符号列形成部１０７に出力しない。また、「Ｃｎ」の個数が“０”である場合には、予測符号化データの出力も行なわない。
【０１５６】
図１９（ａ）、（ｂ）は、制御信号“０”、“１”それぞれにおける、セレクタ１０４が符号列形成部１０７に出力する１ライン分（８画素）の符号化データのデータ構造を示している。図１９（ａ），（ｂ）と図４（ａ），（ｂ）との違いは、図１９（ａ），（ｂ）では、生データの代わりに、近傍一致情報が“Ｃｎ”として判定された画素の予測符号化されたデータが格納されている点である。より分かりやすく言えば、本第３の実施形態は、第１の実施形態で生成される１ライン分の符号化データに付随する「生データ」を、「予測符号化データ」とするものであると言える。
【０１５７】
なお、本第３の実施形態の場合、符号列形成部１０７は、予測式選択信号ｍを特定する情報をファイルヘッダに格納することになる。
【０１５８】
次に、本第３の実施形態における復号装置について説明する。図２０は本第３の実施形態における復号装置のブロック構成図である。図２と同じ処理を行なう構成については同符号を付した。復号装置の処理は、これまでの説明から容易に理解できるであろうから、以下では簡単に説明する。なお、制御部２５０は、ファイルヘッダに格納されている予測式選択信号ｍを読出し、予測復号部２２０に設定しておくものとする。
バッファ２０１には、符号化データが格納される。また、ラインバッファ２０６には、復号済みの画素データが格納される。このラインバッファ２０６は１ライン＋１画素分の容量を有する（近傍画素Ｘａ，Ｘｂ，Ｘｃ，Ｘｄを参照するため）。
【０１５９】
解析部２０２は、内部に１ライン（８個）の近傍一致情報を格納するためのメモリを持つ。このメモリは、着目ラインの前ラインの近傍一致情報を格納するためのものである。そして、解析部２０２は、バッファ２０１の先頭ビットの着目ラインのラインヘッダを解析し、それが“０”であるか、“１”であるかを判定し、判定結果をセレクタ２０５に出力する。
【０１６０】
ラインヘッダが“０”である場合、このラインヘッダに８個の符号化データ（近傍一致情報）が後続していることになる（図１９（ａ）参照）。それ故、解析部２０２は、ラインヘッダに後続する８個の近傍一致情報をバッファ２０１から読込み、内部のメモリを更新すると共に、近傍一致情報記憶部２０３に格納させる。また、このとき、解析部２０２は、着目ライン中の８個の近傍一致情報の中で、符号語“Ｃｎ”の個数ＣＮＴをカウントする。ＣＮＴ＞０であった場合、近傍一致情報に後続してＣＮＴ個の予測符号化データが存在することになるので、そのＣＮＴ個の予測符号化データを予測復号部２２０に、出力する。
【０１６１】
また、ラインヘッダが“１”である場合、このラインヘッダに後続して近傍一致情報は存在しないことになる。同時に、ラインヘッダが“１”であるのは、着目ラインの８個の近傍一致情報は、前ラインの近傍一致情報と同じであることを意味する。それ故、解析部２０２は、内部のメモリに格納された前ラインの近傍一致情報（８個）を近傍一致情報記憶部２０３に格納させる。また、このとき、解析部２０２は、内部メモリの８個の近傍一致情報の中で、符号語“Ｃｎ”の個数ＣＮＴをカウントする。ＣＮＴ＞０であった場合、ラインヘッダに後続してＣＮＴ個の予測符号化データが存在することになるので、そのＣＮＴ個の予測符号化データを予測復号部２２０に、出力する。
【０１６２】
予測復号部２２０は、解析部２０２の制御の下で、バッファ２０１から入力したＣＮＴ個の符号化画素データを入力し、順に復号し、その結果をバッファ２２１に格納する。具体的には、Golomb符号化された符号化データをGolomb復号し、予測誤差ｅを求める。次いで、予測式選択信号ｍに基づき、ラインバッファ２０６内の既に復号された画素データを参照し、予測値ｐを求める。次いで、予測値ｐを、Golomb復号して得られた予測誤差ｅに加算することで、着目画素の着目色成分を復号する。この処理を３つの成分について行なうこで、１画素分のデータを復元し、バッファ２２１に格納する。
【０１６３】
着目ブロックの着目ライン（８個）の近傍一致情報が近傍一致情報記憶部２０３に格納され、且つ、ＣＮＴ個分の予測復号された画素データがバッファ２２１に格納されると、セレクタ２０５はその処理を開始する。
【０１６４】
セレクタ２０５は、近傍一致情報記憶部２０３の先頭から順に処理する。処理対象の近傍一致情報が“Ｃｎ”である場合、その画素データはバッファ２２１に格納されていることになるので、バッファ２２１から該当する画素の全色成分んを読込み出力する。また、セレクタ２０５は、近傍一致情報記憶部２０３から読込んだ近傍一致情報が“Ｃｎ”以外、すなわち、｛Ｃａ、Ｃｂ、Ｃｃ、Ｃｄ｝のいずれかであると判断した場合には、その近傍一致情報で示される位置の画素データをバッファ２０６から読込み、出力する。
【０１６５】
以上説明したように、本第３の実施形態によれば、第１の実施形態で生成された符号化データ中の“生データ（１画素につき２４ビット）”を、予測符号化データとすることで、更なる圧縮率が期待できる。
【０１６６】
なお、第３の実施形態では、着目画素の位置が、着目ブロックの境界に位置するとき、そのブロック外の位置となってしまう近傍画素の各成分値を“０”であるものとして、符号化、または、復号するものとした。しかしながら、第１の実施形態の変形例と同様、着目ブロックが、オリジナルの画像の境界にある場合には、仕方がないが、境界よりも内側にある場合、既に符号化された実在するブロック内の画素を近傍画素Ｘａ，Ｘｂ，Ｘｃ，Ｘｄとしても構わないのは明らかである。
【０１６７】
また、先に説明した第２の実施形態の要件を、本第３の実施形態に適用させても構わない。
【０１６８】
また、本第３の実施形態は、先に説明した第１の実施形態の変形例と同様に、コンピュータプログラムでもって実現することも可能であることは明らかである。
【０１６９】
また、通常、コンピュータプログラムは、ＣＤ−ＲＯＭ等のコンピュータ可読記憶媒体に格納されており、それをコンピュータが備える読取り装置にセットし、システムにコピーもしくはインストールすることで実行可能になる。従って、かかるコンピュータ可読記憶媒体も本発明の範疇に入ることは明らかである。
【図面の簡単な説明】
【０１７０】
【図１】第１の実施形態における画像符号化装置のブロック構成図である。
【図２】第１の実施形態における復号装置のブロック構成図である。
【図３】実施形態におけるブロック内の画素を符号化する際の着目画素と近傍画素との相対位置関係を示す図である。
【図４】第１の実施形態の画像符号化装置が生成する１ライン分の符号化データのデータ構造を示す図である。
【図５】第１の実施形態の画像符号化装置が生成する符号化画像データファイルの構造を示す図である。
【図６】実施形態における近傍一致情報とその符号語との対応を示す図である。
【図７】第１の実施形態の変形例におけるコンピュータのブロック構成図である。
【図８】画像符号化処理をコンピュータプログラムで実現する場合の処理手順を示すフローチャートである。
【図９】画像符号化処理をコンピュータプログラムで実現する場合の処理手順を示すフローチャートである。
【図１０】画像符号化処理をコンピュータプログラムで実現する場合の処理手順を示すフローチャートである。
【図１１】画像復号処理をコンピュータプログラムで実現する場合の処理手順を示すフローチャートである。
【図１２】画像復号処理をコンピュータプログラムで実現する場合の処理手順を示すフローチャートである。
【図１３】第２の実施形態における、比較対象の近傍画素群の並びを固定にした場合と、適応的に変化させた場合の符号化データの違いを示す図である。
【図１４】第３の実施形態における画像符号化装置のブロック構成図である。
【図１５】第３の実施形態における近傍一致情報符号化部が生成する近傍一致情報とフラグを示す図である。
【図１６】第３の実施形態における成分値予測符号化部のブロック構成図である。
【図１７】予測式選択信号ｍと予測式との関係を示す図である。
【図１８】第３の実施形態におけるGolomb符号化処理を説明するための図である。
【図１９】第３の実施形態における１ライン分の符号化データのデータ構造を示す図である。
【図２０】第３の実施形態における復号装置のブロック構成図である。
【図１】
2008227864.tif 000003
【図２】
2008227864.tif 000004
【図３】
2008227864.tif 000005
【図４】
2008227864.tif 000006
【図５】
2008227864.tif 000007
【図６】
2008227864.tif 000008
【図７】
2008227864.tif 000009
【図８】
2008227864.tif 000010
【図９】
2008227864.tif 000011
【図１０】
2008227864.tif 000012
【図１１】
2008227864.tif 000013
【図１２】
2008227864.tif 000014
【図１３】
2008227864.tif 000015
【図１４】
2008227864.tif 000016
【図１５】
2008227864.tif 000017
【図１６】
2008227864.tif 000018
【図１７】
2008227864.tif 000019
【図１８】
2008227864.tif 000020
【図１９】
2008227864.tif 000021
【図２０】
2008227864.tif 000022