(57)【要約】画像から一定画素おきにサブサンプリングした初期解像度画像を符号化する初期解像度符号化手段と、サブサンプリング間隔を順次半分にした画像を符号化する高解像度符号化手段とを有し、高解像度符号化手段は、現解像度において符号化すべき画素のうち、前解像度で符号化済の近傍４画素の中心に位置する画素については前記近傍４画素から線形補間により値を予測し、残りの画素については当該画素を中心としてその上下左右に位置する近傍４画素から線形補間により値を予測する画素値予測手段と、符号化対象画素と予測値との残差を求める予測誤差算出手段と、残差を符号化する可変長符号化手段とを備えることを特徴とする符号化装置である。
2008062687.tif 000002
【特許請求の範囲】
【請求項１】
画像から一定画素おきにサブサンプリングした初期解像度画像を符号化する初期解像度符号化手段と、
サブサンプリング間隔を順次半分にした画像を符号化する高解像度符号化手段と
を有し、
前記高解像度符号化手段は、
現解像度において符号化すべき画素のうち、前解像度で符号化済の近傍４画素の中心に位置する画素については前記近傍４画素から線形補間により値を予測し、残りの画素については当該画素を中心としてその上下左右に位置する近傍４画素から線形補間により値を予測する画素値予測手段と、
符号化対象画素と予測値との残差を求める予測誤差算出手段と、
残差を符号化する可変長符号化手段と
を備えることを特徴とする符号化装置。
【請求項２】
前記高解像度符号化手段は、
前解像度で符号化済の近傍４画素を抽出する第１近傍画素抽出手段と、
前解像度で符号化済の近傍４画素の中心に位置する画素を第１画素として抽出する第１画素抽出手段と、
前記第１画素の左に位置する未符号化の画素を第２画素として抽出する第２画素抽出手段と、
前記第２画素の上下左右に位置する符号化済の近傍４画素を抽出する第２近傍画素抽出手段と、
前記第１画素の上に位置する未符号化の画素を第３画素として抽出する第３画素抽出手段と、
前記第３画素の上下左右に位置する符号化済の近傍４画素を抽出する第３近傍画素抽出手段と
を備えることを特徴とする請求項１に記載の符号化装置。
【請求項３】
前記高解像度符号化手段は、一つの前記第１画素の符号化後に一つの前記第２画素および一つの前記第３画素の符号化を行うことを特徴とする請求項２に記載の符号化装置。
【請求項４】
前記高解像度符号化手段は、前記第２画素の符号化後に前記第３画素の符号化を行うことを特徴とする請求項３に記載の符号化装置。
【請求項５】
前記高解像度符号化手段は、前記第１画素の符号化処理と並行して前記第２画素および前記第３画素の符号化処理を行うことを特徴とする請求項２に記載の符号化装置。
【請求項６】
前記高解像度符号化手段は、前記近傍４画素について、隣り合う画素どうしで差分の絶対値を求め、その総和に対して量子化処理を行って符号化コンテキストを求めるコンテキスト算出手段を備え、
前記可変長符号化手段は、前記符号化コンテキストに応じて符号化パラメータを変更する
ことを特徴とする請求項１から請求項５のいずれかに記載の符号化装置。
【請求項７】
前記コンテキスト算出手段は、前記近傍４画素の符号化コンテキストを、前記近傍４画素がその中心に位置する予測対象画素の左上、左下、右上、右下に存在する場合と、上下左右に存在する場合とで、それぞれ異なるコンテキストとして管理することを特徴とする請求項６に記載の符号化装置。
【請求項８】
画像から一定画素おきにサブサンプリングした初期解像度画像を入力符号から復号する初期解像度復号手段と、
サブサンプリング間隔を順次半分にした画像を復号する高解像度復号手段と
を有し、
前記高解像度復号手段は、
現解像度において復号すべき画素のうち、前解像度で復号済の近傍４画素の中心に位置する画素については前記近傍４画素から線形補間により値を予測し、残りの画素については当該画素を中心としてその上下左右に位置する近傍４画素のすべてが前解像度および現解像度で復号済になるのを待って当該近傍４画素から線形補間により値を予測する画素値予測手段と、
復号対象画素と予測値との残差を入力符号から復号する予測誤差復号手段と、
前記予測された画素値に前記復号された残差を加算して目的の画素値を算出する画素値算出手段と
を備えることを特徴とする復号装置。
【請求項９】
前記高解像度復号手段は、
前解像度で復号済の近傍４画素を抽出する第１近傍画素抽出手段と、
該第１近傍画素抽出手段で抽出された近傍４画素の中心に位置する第１画素について前記画素値算出手段で算出された画素値を出力する第１画素出力手段と、
前記第１画素の復号後に前記第１画素の左に位置する未復号の第２画素の上下左右に位置する復号済の近傍４画素を抽出する第２近傍画素抽出手段と、
該第２近傍画素抽出手段で抽出された近傍４画素の中心に位置する第２画素について前記画素値算出手段で算出された画素値を出力する第２画素出力手段と、
前記第２画素の復号後に前記第１画素の上に位置する未復号の第３画素の上下左右に位置する復号済の近傍４画素を抽出する第３近傍画素抽出手段と、
該第３近傍画素抽出手段で抽出された近傍４画素の中心に位置する第３画素について前記画素値算出手段で算出された画素値を出力する第３画素出力手段と
を備えることを特徴とする請求項８に記載の復号装置。
【請求項１０】
前記高解像度復号手段は、一つの前記第１画素の復号後に一つの前記第２画素および一つの前記第３画素の復号を行うことを特徴とする請求項９に記載の復号装置。
【請求項１１】
前記高解像度復号手段は、前記第２画素の復号後に前記第３画素の復号を行うことを特徴とする請求項１０に記載の復号装置。
【請求項１２】
前記高解像度復号手段は、前記近傍４画素について、隣り合う画素どうしで差分の絶対値を求め、その総和に対して量子化処理を行って符号化コンテキストを求めるコンテキスト算出手段を備え、
前記予測誤差復号手段は、前記符号化コンテキストに応じて復号パラメータを変更すること
を特徴とする請求項８から請求項１１のいずれかに記載の復号装置。
【請求項１３】
前記コンテキスト算出手段は、前記近傍４画素の符号化コンテキストを、前記近傍４画素がその中心に位置する予測対象画素の左上、左下、右上、右下に存在する場合と、上下左右に存在する場合とで、それぞれ異なるコンテキストとして管理することを特徴とする請求項１２に記載の復号装置。
【請求項１４】
コンピュータを用いて画像を符号化する方法であって、
前記コンピュータが、画像から一定画素おきにサブサンプリングした初期解像度画像を符号化する第１のステップと、
前記コンピュータが、サブサンプリング間隔を順次半分にした画像を符号化する第２のステップと
を含み、
前記第２のステップは、現解像度において符号化すべき画素のうち、前解像度で符号化済の近傍４画素の中心に位置する画素については前記近傍４画素から線形補間により値を予測し、残りの画素については当該画素を中心としてその上下左右に位置する近傍４画素から線形補間により値を予測し、それぞれ、符号化対象画素と予測値との残差を求め、該残差を可変長符号化する処理を含むことを特徴とする符号化方法。
【請求項１５】
コンピュータを用いて入力符号から画像を復号する方法であって、
前記コンピュータが、画像から一定画素おきにサブサンプリングした初期解像度画像を入力符号から復号する第１のステップと、
前記コンピュータが、サブサンプリング間隔を順次半分にした画像を復号する第２のステップと
を含み、
前記第２のステップは、現解像度において復号すべき画素のうち、前解像度で復号済の近傍４画素の中心に位置する画素については前記近傍４画素から線形補間により値を予測し、残りの画素については当該画素を中心としてその上下左右に位置する近傍４画素のすべてが前解像度および現解像度で復号済になるのを待って当該近傍４画素から線形補間により値を予測し、それぞれ、復号対象画素と予測値との残差を入力符号から復号し、前記予測された画素値に前記復号された残差を加算して目的の画素値を算出する処理を含むことを特徴とする復号方法。
【請求項１６】
コンピュータに、
画像から一定画素おきにサブサンプリングした初期解像度画像を符号化する第１の処理と、
サブサンプリング間隔を順次半分にした画像を符号化する処理であって、各解像度の符号化処理において、現解像度において符号化すべき画素のうち、前解像度で符号化済の近傍４画素の中心に位置する画素については前記近傍４画素から線形補間により値を予測し、残りの画素については当該画素を中心としてその上下左右に位置する近傍４画素から線形補間により値を予測し、それぞれ、符号化対象画素と予測値との残差を求め、該残差を可変長符号化する第２の処理と
を行わせるための符号化プログラム。
【請求項１７】
前記第２の処理は、
前解像度で符号化済の近傍４画素を抽出するステップと、
前解像度で符号化済の近傍４画素の中心に位置する画素を第１画素として抽出するステップと、
前記第１画素の左に位置する未符号化の画素を第２画素として抽出するステップと、
前記第２画素の上下左右に位置する符号化済の近傍４画素を抽出するステップと、
前記第１画素の上に位置する未符号化の画素を第３画素として抽出するステップと、
前記第３画素の上下左右に位置する符号化済の近傍４画素を抽出するステップと
を含むことを特徴とする請求項１６に記載の符号化プログラム。
【請求項１８】
前記第２の処理では、一つの前記第１画素の符号化後に一つの前記第２画素および一つの前記第３画素の符号化を行うことを特徴とする請求項１７に記載の符号化プログラム。
【請求項１９】
前記第２の処理では、前記第２画素の符号化後に前記第３画素の符号化を行うことを特徴とする請求項１８に記載の符号化プログラム。
【請求項２０】
前記第２の処理では、前記第１画素の符号化処理と並行して前記第２画素および前記第３画素の符号化処理を行うことを特徴とする請求項１７に記載の符号化プログラム。
【請求項２１】
前記第２の処理では、前記近傍４画素について、隣り合う画素どうしで差分の絶対値を求め、その総和に対して量子化処理を行って符号化コンテキストを求めるステップを含み、
前記符号化コンテキストに応じて可変長符号化の符号化パラメータを変更することを特徴とする請求項１６から請求項２０のいずれかに記載の符号化プログラム。
【請求項２２】
前記近傍４画素の符号化コンテキストを、前記近傍４画素がその中心に位置する予測対象画素の左上、左下、右上、右下に存在する場合と、上下左右に存在する場合とで、それぞれ異なるコンテキストとして管理することを特徴とする請求項２１に記載の符号化プログラム。
【請求項２３】
コンピュータに、
画像から一定画素おきにサブサンプリングした初期解像度画像を入力符号から復号する第１の処理と、
サブサンプリング間隔を順次半分にした画像を復号する処理であって、各解像度の復号処理において、現解像度において復号すべき画素のうち、前解像度で復号済の近傍４画素の中心に位置する画素については前記近傍４画素から線形補間により値を予測し、残りの画素については当該画素を中心としてその上下左右に位置する近傍４画素のすべてが前解像度および現解像度で復号済になるのを待って当該近傍４画素から線形補間により値を予測し、それぞれ、復号対象画素と予測値との残差を入力符号から復号し、前記予測された画素値に前記復号された残差を加算して目的の画素値を算出する第２の処理と
を行わせるための復号プログラム。
【請求項２４】
前記第２の処理は、
前解像度で復号済の近傍４画素を抽出するステップと、
該抽出された近傍４画素の中心に位置する第１画素について算出された画素値を出力するステップと、
前記第１画素の復号後に前記第１画素の左に位置する未復号の第２画素の上下左右に位置する復号済の近傍４画素を抽出するステップと、
該抽出された近傍４画素の中心に位置する第２画素について算出された画素値を出力するステップと、
前記第２画素の復号後に前記第１画素の上に位置する未復号の第３画素の上下左右に位置する復号済の近傍４画素を抽出するステップと、
該抽出された近傍４画素の中心に位置する第３画素について算出された画素値を出力するステップと
を含むことを特徴とする請求項２３に記載の復号プログラム。
【請求項２５】
前記第２の処理では、一つの前記第１画素の復号後に一つの前記第２画素および一つの前記第３画素の復号を行うことを特徴とする請求項２４に記載の復号プログラム。
【請求項２６】
前記第２の処理では、前記第２画素の復号後に前記第３画素の復号を行うことを特徴とする請求項２５に記載の復号プログラム。
【請求項２７】
前記第２の処理では、前記近傍４画素について、隣り合う画素どうしで差分の絶対値を求め、その総和に対して量子化処理を行って符号化コンテキストを求めるステップを含み、
前記符号化コンテキストに応じて復号パラメータを変更する
ことを特徴とする請求項２３から請求項２６のいずれかに記載の復号プログラム。
【請求項２８】
前記近傍４画素の符号化コンテキストを、前記近傍４画素がその中心に位置する予測対象画素の左上、左下、右上、右下に存在する場合と、上下左右に存在する場合とで、それぞれ異なるコンテキストとして管理することを特徴とする請求項２７に記載の復号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は２次元信号の符号化および復号装置に関し、特に予測残差を用いた多値２次元信号の符号化および復号装置に関する。
【背景技術】
【０００２】
従来、この種の予測符号化方式は、画像信号に代表される２次元信号を記録媒体に格納する場合やネットワークを通して伝送する場合に、記録媒体や伝送路を効率的に利用するためのデータ圧縮に利用されている。【０００３】
従来の予測符号化の一般的な方式として、既に符号化済の隣接画素（上／左／左上等）から注目画素の値を予測し、残差を符号化する方式がある（例えば特許文献１参照）。図１０に一般的な予測方式の例を示す。行列予測は、左および上の画素Ａ、Ｃから注目画素Ｘの値を予測し、平均予測は、左および右上の画素Ａ、Ｄから注目画素Ｘの値を予測し、平面予測は、左、左上および上の画素Ａ、Ｂ、Ｃから注目画素の値を予測する。これらの方式は何れも予測値の計算式が単純であり、その分だけ処理速度も高速になる。この方式を採用した予測符号化の代表的なものにJPEG-LSがある。【０００４】
従来の予測符号化の他の方式として、元画像から一定画素おきにサブサンプリングした低解像度画像をまず符号化し、次に残りの未符号化画素の値を既符号化画素から補間により予測してその残差を符号化する方式がある（例えば、非特許文献１、特許文献２、３参照）。この方式の利点として、解像度プログレッシブ機能が実現できる点が挙げられる。これにより、巨大な画像であっても、低解像度成分のみを抽出して復号し表示することができ、ユーザの認知的待ち時間を短縮することが可能となる。【０００５】
解像度プログレッシブ機能を有する予測符号化において、未符号化画素の値を既符号化画素から予測する方式には、前解像度の画素のみを使用して予測する方式（例えば非特許文献１、特許文献３参照）、前解像度および現解像度の画素を併用する方式（例えば特許文献２の０００４段落参照）がある。【０００６】
他方、予測残差の符号化に適した可変長符号としては、ハフマン符号、ゴロムライス（Golomb-Rice）符号などが知られている。特にゴロムライス符号は、信号値を「単進符号」＋「kビットの固定長符号（kは有効桁数の推定値）」として出力するもので、０に近い値ほど短い符号長となることから、予測残差の簡易符号化として知られている。またゴロムライス符号は、符号化すべき信号値の有効桁とk値が一致する場合に、最も符号長が短くなるため、それまでに出現した残差の値やコンテキストに応じて最適なk値を予測する適応型ゴロムライス符号が考案されている。例えば特許文献４に記載された適応型ゴロムライス符号化方式は、予測残差dの統計から、最適なk値を予測するものである。具体的には、それまでに出現した予測残差dの絶対値を累積し、その総和aと累積回数nから平均的な有効桁数kが推定される。【０００７】
【非特許文献１】”Fast Progressive Lossless Image Compression”, Proceedings of the 1994 IST/SPIE, 1994/02
【特許文献１】米国特許第5680129号明細書
【特許文献２】特許第2501598号
【特許文献３】特開2005-198014号公報
【特許文献４】米国特許第5764374号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００８】
予測符号化方式は、空間的に近接する画素の相関が高いことを利用し、既に符号化済の近接画素から注目画素の値を予測し、予測値と実際の画素値の差分を符号化する。このため、予測精度が高い程、差分が小さい値の範囲に収まり、可変長符号によって効率良く圧縮することができる。しかしながら、従来の解像度プログレッシブ機能を持つ予測符号化方式では、予測精度を高めるのが難しく、そのために圧縮率を高めることが難しいという課題があった。その理由は次の通りである。【０００９】
まず、未符号化画素の値を既符号化画素から予測する際に、前解像度の画素のみを使用する従来方式の場合、これから符号化しようとする注目画素から離れた既符号化画素を利用せざるを得ない状況が発生するために補間精度が低下する画素が多く発生する。例えば、図１１に示すように画像を２画素に１画素の割合で縦横に間引き、○印の画素を低解像度画像として符号化し、残りの・印の画素の値を○印の画素から補間で予測する場合、隣接する既符号化画素が上下にしか存在しない画素Ｙの補間精度は、左上、左下、右上、右下に既符号化画素が隣接している画素Ｘの補間精度よりも低下する。なぜなら、画素Ｘは近傍４画素からの２次元の内挿により精度良く予測できるのに対して、画素Ｙは上下２画素からの１次元の内挿による予測になるためである。勿論、特許文献２の図７に示されるように周囲の４個の既符号化画素の値を用いてマトリクス演算によって画素Ｙの値を２次元の内挿で予測することもできるが、４つの画素の中心にＹが位置しないため予測式が複雑になる割には、画素Ｘほど精度は高まらない。【００１０】
次に、未符号化画素の値を既符号化画素から予測する際に、前解像度および現解像度の画素を併用する従来方式の場合、図１２に示すように、画素Ｙは上下２つの低解像度の既符号化画素以外に、左、左上および右上の既符号化画素を利用できるため、前解像度の画素のみを使用する方式に比べると予測精度は高まる。しかし、Ｙの右の画素が未符号化画素であるため、精度をより高めるために内挿を使用する場合、複雑な計算式が必要になり、その割には精度が高まらない。【００１１】
本発明の目的は、解像度プログレッシブ機能を持つ予測符号化において、未符号化画素の値を既符号化画素から簡易な計算によって精度良く予測できるようにすることにより、圧縮率の向上と計算時間の短縮を図ることにある。
【課題を解決するための手段】
【００１２】
上記目的を達成する本発明は、画像から一定画素おきにサブサンプリングした初期解像度画像を符号化する初期解像度符号化手段と、サブサンプリング間隔を順次半分にした画像を符号化する高解像度符号化手段とを有し、前記高解像度符号化手段は、現解像度において符号化すべき画素のうち、前解像度で符号化済の近傍４画素の中心に位置する画素については前記近傍４画素から線形補間により値を予測し、残りの画素については当該画素を中心としてその上下左右に位置する近傍４画素から線形補間により値を予測する画素値予測手段と、符号化対象画素と予測値との残差を求める予測誤差算出手段と、残差を符号化する可変長符号化手段とを備えることを特徴とする符号化装置である。【００１３】
上記目的を達成する本発明は、画像から一定画素おきにサブサンプリングした初期解像度画像を入力符号から復号する初期解像度復号手段と、サブサンプリング間隔を順次半分にした画像を復号する高解像度復号手段とを有し、前記高解像度復号手段は、現解像度において復号すべき画素のうち、前解像度で復号済の近傍４画素の中心に位置する画素については前記近傍４画素から線形補間により値を予測し、残りの画素については当該画素を中心としてその上下左右に位置する近傍４画素のすべてが前解像度および現解像度で復号済になるのを待って当該近傍４画素から線形補間により値を予測する画素値予測手段と、復号対象画素と予測値との残差を入力符号から復号する予測誤差復号手段と、前記予測された画素値に前記復号された残差を加算して目的の画素値を算出する画素値算出手段とを備えることを特徴とする復号装置である。【００１４】
上記目的を達成する本発明は、コンピュータを用いて画像を符号化する方法であって、前記コンピュータが、画像から一定画素おきにサブサンプリングした初期解像度画像を符号化する第１のステップと、前記コンピュータが、サブサンプリング間隔を順次半分にした画像を符号化する第２のステップとを含み、前記第２のステップは、現解像度において符号化すべき画素のうち、前解像度で符号化済の近傍４画素の中心に位置する画素については前記近傍４画素から線形補間により値を予測し、残りの画素については当該画素を中心としてその上下左右に位置する近傍４画素から線形補間により値を予測し、それぞれ、符号化対象画素と予測値との残差を求め、該残差を可変長符号化する処理を含むことを特徴とする符号化方法である。【００１５】
上記目的を達成する本発明は、コンピュータを用いて入力符号から画像を復号する方法であって、前記コンピュータが、画像から一定画素おきにサブサンプリングした初期解像度画像を入力符号から復号する第１のステップと、前記コンピュータが、サブサンプリング間隔を順次半分にした画像を復号する第２のステップとを含み、前記第２のステップは、現解像度において復号すべき画素のうち、前解像度で復号済の近傍４画素の中心に位置する画素については前記近傍４画素から線形補間により値を予測し、残りの画素については当該画素を中心としてその上下左右に位置する近傍４画素のすべてが前解像度および現解像度で復号済になるのを待って当該近傍４画素から線形補間により値を予測し、それぞれ、復号対象画素と予測値との残差を入力符号から復号し、前記予測された画素値に前記復号された残差を加算して目的の画素値を算出する処理を含むことを特徴とする復号方法である。【００１６】
上記目的を達成する本発明は、コンピュータに、画像から一定画素おきにサブサンプリングした初期解像度画像を符号化する第１の処理と、サブサンプリング間隔を順次半分にした画像を符号化する処理であって、各解像度の符号化処理において、現解像度において符号化すべき画素のうち、前解像度で符号化済の近傍４画素の中心に位置する画素については前記近傍４画素から線形補間により値を予測し、残りの画素については当該画素を中心としてその上下左右に位置する近傍４画素から線形補間により値を予測し、それぞれ、符号化対象画素と予測値との残差を求め、該残差を可変長符号化する第２の処理とを行わせるための符号化プログラムである。【００１７】
上記目的を達成する本発明は、コンピュータに、画像から一定画素おきにサブサンプリングした初期解像度画像を入力符号から復号する第１の処理と、サブサンプリング間隔を順次半分にした画像を復号する処理であって、各解像度の復号処理において、現解像度において復号すべき画素のうち、前解像度で復号済の近傍４画素の中心に位置する画素については前記近傍４画素から線形補間により値を予測し、残りの画素については当該画素を中心としてその上下左右に位置する近傍４画素のすべてが前解像度および現解像度で復号済になるのを待って当該近傍４画素から線形補間により値を予測し、それぞれ、復号対象画素と予測値との残差を入力符号から復号し、前記予測された画素値に前記復号された残差を加算して目的の画素値を算出する第２の処理とを行わせるための復号プログラムである。
【発明の効果】
【００１８】
本発明によれば、解像度プログレッシブ機能を持つ予測符号化において、未符号化画素の値を既符号化画素から簡易な計算によって精度良く予測することができる。【００１９】
その理由は、現解像度において符号化すべき画素を、前解像度で符号化済の近傍４画素の中心に位置する第１の画素とそれ以外の第２、第３の画素とに分け、第１の画素については、左上、左下、右上、右下の合計４個の既符号化画素から線形補間により値を予測して符号化し、第２および第３の画素については、その上下左右の近傍４画素から線形補間により値を予測して符号化するため、何れの画素も近傍４画素による線形内挿によって値を簡単かつ精度良く予測することができるためである。【００２０】
このように未符号化画素の値を既符号化画素から精度良く予測できるため、予測値と実際の画素値の差分が小さい値の範囲に収まり、可変長符号化によって効率良く圧縮することが可能となる。
【図面の簡単な説明】
【００２１】
【図１】本発明の符号化装置の作用を説明するための図である。
【図２】本発明の符号化装置の一実施の形態のブロック図である。
【図３】本発明の符号化装置の一実施の形態の処理の流れを示すフローチャートである。
【図４】本発明の復号装置の一実施の形態のブロック図である。
【図５】本発明の復号装置の一実施の形態の処理の流れを示すフローチャートである。
【図６】本発明の符号化装置および復号装置の初期解像度における符号化動作および復号動作の説明図である。
【図７】本発明の符号化装置および復号装置の高解像度における符号化動作および復号動作の説明図である。
【図８】符号化の過程で行われる画素値の予測および符号化コンテキスト値の算出、差分の符号化の説明図である。
【図９】復号の過程で行われる画素値の予測および符号化コンテキスト値の算出、差分の復号、画素値の算出の説明図である。
【図１０】未符号化画素の値を既符号化画素から予測する一般的な予測方式の説明図である。
【図１１】未符号化画素の値を既符号化画素から予測する際に、前解像度の画素のみを使用する従来方式の説明図である。
【図１２】未符号化画素の値を既符号化画素から予測する際に、前解像度および現解像度の画素を併用する従来方式の説明図である。
【符号の説明】
【００２２】
１１…画像入力装置
１２、２２…データ記憶装置
１３、２３…データ処理装置
１４…符号出力装置
２１…符号入力装置
２４…画像出力装置
【発明を実施するための最良の形態】
【００２３】
本発明の特徴を、その理解を容易にするために簡単な例を挙げて説明する。今、図１(a)に示すように画像を２画素に１画素の割合で縦横に間引き、○印の画素を低解像度画像として符号化した後、残りの・印の画素を符号化することを考える。本発明では、現解像度において符号化すべき画素を、前解像度で符号化済の近傍４画素の中心に位置する画素とそれ以外の画素とに分け、前者の画素については左上、左下、右上、右下の合計４個の既符号化画素○から線形補間により値を予測し、この予測値と実際の画素値との残差を可変長符号化する。図１(b)に示される画素Ｘはこうして符号化された前者の画素である。【００２４】
図１(b)に示すように○印の画素に加えて画素Ｘが符号化されると、残りの符号化していない・印の画素が、上下左右ともに既符号化の画素で囲まれるようになる。すなわち、図１(a)の状態では、既符号化画素が上下にしか存在しなかった画素は、図１(c)の画素Ｙのように左右に画素Ｘができることにより上下左右ともに既符号化の画素で囲まれる。また、図１(a)の状態では、既符号化画素が左右にしか存在しなかった画素は、図１(c)の画素Ｚのように上下に画素Ｘができることにより上下左右ともに既符号化の画素で囲まれる。そこで、これらの画素Ｙおよび画素Ｚの値を、その上下左右に位置する前解像度および現解像度で符号化済の近傍４画素から線形補間により予測し、この予測値と実際の画素値との残差を可変長符号化する。【００２５】
なお、図１(c)に示される画像の上下左右端に存在する未符号化の画素・は、画像端に存在するため周囲を既符号化の画素で囲むことはそもそも不可能である。この場合は適当な方法で補間すれば良い。例えば画像境界で折り返した位置にある画素を用いて補間する方法によれば、画像の左右の端に存在する未符号化の画素・は図１(d)に示すように画素Ｙと同様に扱え、画像の上下の端に存在する未符号化の画素・は図１(d)に示すように画素Ｚと同様に扱える。【００２６】
図１(a)の状態から図１(d)の状態にするために、先ず画像中の全ての画素Ｘについて符号化を行い、次に残りの画素Ｙ、Ｚの符号化を行う方法でも良いが、画像を複数回にわたって走査する必要性が生じるため、キャッシュを内蔵するコンピュータで符号化処理を行う場合、参照の局所性を増大させることができず、キャッシュヒット率の低下により処理速度が落ちる可能性がある。このため、図１(e)に示すように、一つの画素Ｘの符号化後に一つの画素Ｙと一つの画素Ｚの符号化を行う処理を、走査方向（画像の左端から右端方向）に順次繰り返していく方法が好ましい。【００２７】
また、その際の画素Ｙと画素Ｚの処理順についても、まず画素Ｙを符号化し、次に画素Ｚを符号化するのが好ましい。何故なら、画素Ｚの次に画素Ｙを符号化すると、符号化順がＸ→Ｚ→Ｙ→Ｘとなり、図１(f)に示すように画素Ｙを処理した後、距離の隔たりが大きい画素Ｘに移動しなければならないのに対し、画素Ｙの次に画素Ｚを符号化すると、符号化順がＸ→Ｙ→Ｚ→Ｘとなり、Ｚ→Ｘの距離がＹ→Ｘの距離より短くなるためである。キャッシュの関係で具体的に説明すれば、例えば図１(f)の●印の画素に注目すると、符号化順がＸ→Ｚ→Ｙ→Ｘの場合、Ｙの符号化時に使用されないため、直後のＸの符号化時にキャッシュに存在する可能性が低くなるのに対し、符号化順がＸ→Ｙ→Ｚ→Ｘである場合、Ｚで参照されているため、直後のＸの符号化時にキャッシュに存在している可能性が高まることになる。【００２８】
可変長符号化手段は任意のもので良いが、符号化コンテキストに応じて符号化パラメータを変更する機能を有する可変長符号、例えば適応ゴロムライス符号を用いれば、画素値の空間的局所性に対して符号化パラメータを適応させることができ、圧縮率を更に向上することができる。この場合、符号化コンテキストは、予測に用いる４画素の隣り合う画素どうしで差の絶対値を求め、その総和を量子化するといった簡単な方法で算出することができる。その理由は、予測に用いる４画素は注目画素（画素値を予測しようとする画素）を中心として点対称に配置されているため、４画素のどの画素もコンテキストの算出に関して軽重に差を付ける必要がないためである。【００２９】
また、画素Ｘは左上、左下、右上、右下の４画素から予測し、画素Ｙと画素Ｚは上下左右の４画素から予測するため、近傍４画素の符号化コンテキストを、その中心に位置する予測対象画素の左上、左下、右上、右下に存在する近傍４画素と、上下左右に存在する近傍４画素とで、それぞれ異なるコンテキストとして管理することが望ましい。そして、このコンテキストの管理の面からも、画素Ｙと画素Ｚの処理順については、Ｙ→Ｚの方がＺ→Ｙよりも好ましい。その理由は、Ｚ→Ｙ→Ｚ→Ｙ…の順でコンテキストを更新する場合に比べて、Ｙ→Ｚ→Ｙ→Ｚ…の順でコンテキストを更新する場合の方が、コンテキスト統計値の追随性が良くなるためである。具体的には、Ｚ→Ｙ→Ｚ→Ｙ…の順で処理する場合、Ｙを符号化する際には１画素右・１画素上のＺで直前のコンテキスト更新が行われるので問題はないが、Ｚを符号化する際には３画素左・１画素下のＹで直前のコンテキスト更新が行われる。これに対して、Ｙ→Ｚ→Ｙ→Ｚ…の順で処理する場合、Ｙを符号化する際には１画素左・１画素上のＺで直前のコンテキスト更新が行われ、またＺを符号化する際には１画素左・１画素下のＹで直前のコンテキスト更新が行われる。後者の方が、より空間的に近い画素からの統計値が反映できるため、画像の空間的局所性に対する統計値の追随性が良くなる。これによって最適な符号化パラメータをより高精度に推定できるようになり、圧縮率が向上する。【００３０】
以上の説明では、一つの画素Ｘの符号化後に一つの画素Ｙと一つの画素Ｚの符号化を行う例を示したが、符号化を高速化するために、画素Ｘの符号化処理と並行して画素Ｙおよび画素Ｚの符号化処理を行うことも可能である。【００３１】
符号化された画像の復号は、符号化と逆の手順で行われる。【００３２】
次に、本発明を実施の形態について図面を参照して詳細に説明する。【００３３】
『符号化装置の実施の形態』
図２を参照すると、本発明の符号化装置の一実施の形態は、画像入力装置１１と、データ記憶装置１２と、プログラム制御により動作するデータ処理装置１３と、符号出力装置１４とから構成されている。【００３４】
画像入力装置１１は、符号化の対象となる画像をデータ記憶装置１２に入力する装置であり、例えばカメラやスキャナなどの撮像装置、外部から画像データを受信する通信装置、あるいは磁気ディスク等の外部記憶装置などで構成される。画像の形式は任意であるが、以下では説明の便宜上、Ｎ×Ｍ（Ｎ、Ｍは２のべき乗）画素のビットマップ形式で表現されているものとし、各画素値は多ビットのグレースケールで表されているものとして説明する。【００３５】
データ記憶装置１２は、コンピュータの主記憶装置や補助記憶装置で構成され、符号化の対象となる画像およびその符号化処理の過程で生成された各種のデータを記憶する。本実施の形態の場合、データ記憶装置１２は、画像入力装置１１から入力された画像を記憶する画像メモリ１２１と、現に符号化の対象とする画素の値を記憶する符号化対象画素メモリ１２２と、符号化対象画素の近傍にある４画素の値を記憶する近傍画素メモリ１２３と、近傍４画素から予測された符号化対象画素の値を記憶する予測画素値メモリ１２４と、符号化対象画素の予測値と実際の値との差分を記憶する予測誤差メモリ１２５とを有する。【００３６】
また、本実施の形態は、可変長符号として適応ゴロムライス符号を用いるため、データ記憶装置１２にはさらに、コンテキストメモリ１２６と、第１および第２のコンテキストテーブル１２７および１２８とが設けられている。コンテキストメモリ１２６は、近傍４画素から求められた符号化コンテキストを記憶し、第１および第２のコンテキストテーブル１２７および１２８は、最適なゴロムパラメータ（有効桁数の推定値k）を算出するために符号化コンテキストの統計情報を記憶するために使われる。ここで、コンテキストテーブルが第１、第２の２つ存在する理由は、近傍４画素の符号化コンテキストを、近傍４画素がその中心に位置する予測対象画素の左上、左下、右上、右下に存在する場合と、上下左右に存在する場合とで、それぞれ異なるコンテキストとして管理するためである。【００３７】
データ処理装置１３は、コンピュータのＣＰＵなどで構成され、画像入力装置１１から入力された画像を符号化して符号出力装置１４に出力する処理を実行する。本実施の形態の場合、データ処理装置１３は、初期解像度符号化手段１３１、第１画素抽出手段１３２１、第１近傍画素抽出手段１３３１、第２画素抽出手段１３２２、第２近傍画素抽出手段１３３２、第３画素抽出手段１３２３、第３近傍画素抽出手段１３３３、画素値予測手段１３４、予測誤差算出手段１３５、コンテキスト算出手段１３６および可変長符号化手段１３７を有する。これらのうち、初期解像度符号化手段１３１以外の手段は高解像度符号化手段を構成する。【００３８】
初期解像度符号化手段１３１は、画像メモリ１２１から画素データを順次読み込み、符号化を行う。具体的には、画像メモリ１２１上の画像をあらかじめ定められたｎ（２のべき乗）画素に１画素の割合で縦横にサブサンプリングした（間引いた）画像を抽出して可変長符号化し、符号出力装置１４へ出力する。この初期解像度符号化の際には、各画素はそれまでに符号化された近傍の画素から画素値を予測し、その予測値と実際の画素値との差分を符号化する。予測方法としては従来ＰＮＧで用いられているような各種のフィルタ（たとえば、図１０に示した行列予測）が利用できる。初期解像度の符号化が完了すると、残りの解像度の符号化が行われる。【００３９】
残り解像度の符号化では、まず、初期解像度で使われたサブサンプリング間隔の半分の間隔で、未符号化の画素をサブサンプリングして符号化する。そのサブサンプリング間隔での符号化が全て完了すると、サブサンプリング間隔をさらに半分にして、未符号化の画素がなくなるまで符号化を繰り返す。残り解像度の符号化において、第１画素抽出手段１３２１、第１近傍画素抽出手段１３３１、第２画素抽出手段１３２２、第２近傍画素抽出手段１３３２、第３画素抽出手段１３２３、第３近傍画素抽出手段１３３３、画素値予測手段１３４、予測誤差算出手段１３５、コンテキスト算出手段１３６および可変長符号化手段１３７は、それぞれ以下のような役割を果たす。【００４０】
第１画素抽出手段１３２１は、現解像度において符号化すべき画素のうち、前解像度で符号化済の近傍４画素の中心に位置する画素を第１画素として画像メモリ１２１から抽出し、符号化対象画素メモリ１２２に格納する。【００４１】
第１近傍画素抽出手段１３３１は、第１画素の左上、左下、右上、右下に位置する符号化済の近傍４画素を画像メモリ１２１から抽出し、近傍画素メモリ１２３に格納する。【００４２】
第２画素抽出手段１３２２は、第１画素の符号化後に、現解像度において符号化すべき画素のうち第１画素の左隣に位置する未符号化画素を第２画素として画像メモリ１２１から抽出し、符号化対象画素メモリ１２２に格納する。【００４３】
第２近傍画素抽出手段１３３２は、第２画素の上、下、左、右に位置する符号化済の近傍４画素を画像メモリ１２１から抽出し、近傍画素メモリ１２３に格納する。【００４４】
第３画素抽出手段１３２３は、第２画素の符号化後に、現解像度において符号化すべき画素のうち第１画素の上隣に位置する未符号化画素を第３画素として画像メモリ１２１から抽出し、符号化対象画素メモリ１２２に格納する。【００４５】
第３近傍画素抽出手段１３３３は、第３画素の上、下、左、右に位置する符号化済の近傍４画素を画像メモリ１２１から抽出し、近傍画素メモリ１２３に格納する。【００４６】
画素値予測手段１３４は、近傍画素メモリ１２３に格納されている画素値の平均値を求め、予測画素値メモリ１２４に格納する。【００４７】
予測誤差算出手段１３５は、予測画素値メモリ１２４に格納された画素予測値と、符号化対象画素メモリ１２２に格納された画素値との差分を求め、予測誤差メモリ１２５に格納する。【００４８】
コンテキスト算出手段１３６は、近傍画素メモリ１２３に格納されている近傍４画素の、それぞれ隣り合う画素同士で差分の絶対値を求め、その総和を量子化して符号化コンテキストとしてコンテキストメモリ１２６に格納する。【００４９】
可変長符号化手段１３７は、予測誤差メモリ１２５の値を可変長符号化し、符号出力装置１４へ出力する。本実施の形態の場合、可変長符号化手段１３７は適応ゴロムライス符号化手段であり、第１および第２のコンテキストテーブル１２７、１２８のうちから所望のテーブルを選択し、それに格納されたコンテキストの統計情報から有効桁数の推定値kを算出し、このkを用いて符号化した後、コンテキストメモリ１２６に格納された今回の符号化コンテキストを前記選択したコンテキストテーブルに反映する。【００５０】
符号出力装置１４は、符号化されたデータを図示しない記録媒体に出力したり、伝送路を通じて他所へ送信する装置などである。【００５１】
次に、図２及び図３のフローチャートを参照して、本実施の形態にかかる符号化装置の全体の動作について詳細に説明する。【００５２】
まず、画素抽出のサブサンプリング間隔が、初期解像度の間隔に設定される（図３のステップＳ１０１）。【００５３】
初期解像度符号化手段１３１は、画素抽出座標を原点に初期化し（ステップＳ１０２）、順次画素を抽出して符号化を行う。具体的には、初期解像度のサブサンプリング間隔で画素を抽出し（ステップＳ１０３）、また、その近傍画素を抽出する（ステップＳ１０４）。次に、近傍画素から、平均値フィルタなどによって外挿予測を行い（ステップＳ１０５）、予測誤差を算出して（ステップＳ１０６）、可変長符号化を行い（ステップＳ１０７）、符号出力装置１４へ出力する（ステップＳ１０７）。【００５４】
続いて、初期解像度の初期サブサンプリング間隔での符号化が全て完了したかどうかが判定され（ステップＳ１０８）、完了していなければ抽出座標をシフトして（ステップＳ１０９）、ステップＳ１０３に戻る。完了していれば、解像度をシフト（サブサンプリング間隔を半分に）して（ステップＳ１１０）、残り解像度の符号化（ステップＳ１１１以降）へ進む。【００５５】
残り解像度の符号化では、まず、画素抽出座標が、そのサンプリング間隔での初期座標に初期化される（ステップＳ１１１）。【００５６】
次に第１画素抽出手段１３２１は、前解像度で符号化済の近傍４画素の中心に位置する第１画素を画像メモリ１２１から抽出し、符号化対象画素メモリ１２２に格納する（ステップＳ１１２）。【００５７】
次に第１近傍画素抽出手段１３３１は、第１画素の近傍に位置する前解像度で符号化済の画素４つ（左上、右上、左下、右下）を画像メモリ１２１から抽出し、近傍画素メモリ１２３に格納する（ステップＳ１１３）。【００５８】
次に画素値予測手段１３４は、近傍画素メモリ１２３に格納されている４画素の画素値の平均値を求め、予測画素値メモリ１２４に格納する（ステップＳ１１４）。【００５９】
次にコンテキスト算出手段１３６は、近傍画素メモリ１２３に格納されている４画素の、それぞれ隣り合う画素同士で差分の絶対値を求め、その総和を量子化してコンテキストメモリ１２６に格納する（ステップＳ１１５）。【００６０】
次に予測誤差算出手段１３５は、予測画素値メモリ１２４に格納された画素予測値と、符号化対象画素メモリ１２２に格納された画素値との差分を求め、予測誤差メモリ１２５に格納する（ステップＳ１１６）。【００６１】
次に可変長符号化手段１３７は、第１コンテキストテーブル１２７に格納されたコンテキストの統計情報から符号化パラメータ（有効桁数の推定値k）を算出して予測誤差メモリ１２５の値を可変長符号化し、符号出力装置１４へ出力する（ステップＳ１１７ａ）。また可変長符号化手段１３７は、コンテキストメモリ１２６の内容で第１コンテキストテーブル１２７を更新する（ステップＳ１１７ｂ）。【００６２】
以上で、１つの第１画素の符号化処理が終わり、次に第２画素の符号化が以下のように実行される。【００６３】
まず第２画素抽出手段１３２２は、第１画素の左隣に位置する第２画素を画像メモリ１２１から抽出し、符号化対象画素メモリ１２２に格納する（ステップＳ１１８）。【００６４】
次に第２近傍画素抽出手段１３３２は、第２画素の近傍に位置する符号化済の画素４つ（上、下、左、右）を画像メモリ１２１から抽出し、近傍画素メモリ１２３に格納する（ステップＳ１１９）。【００６５】
次に画素値予測手段１３４は、近傍画素メモリ１２３に格納されている４画素の画素値の平均値を求め、予測画素値メモリ１２４に格納する（ステップＳ１２０）。【００６６】
次にコンテキスト算出手段１３６は、近傍画素メモリ１２３に格納されている４画素の、それぞれ隣り合う画素同士で差分の絶対値を求め、その総和を量子化してコンテキストメモリ１２６に格納する（ステップＳ１２１）。【００６７】
次に予測誤差算出手段１３５は、予測画素値メモリ１２４に格納された画素予測値と、符号化対象画素メモリ１２２に格納された画素値との差分を求め、予測誤差メモリ１２５に格納する（ステップＳ１２２）。【００６８】
次に可変長符号化手段１３７は、第２コンテキストテーブル１２８に格納されたコンテキストの統計情報から符号化パラメータ（有効桁数の推定値k）を算出して予測誤差メモリ１２５の値を可変長符号化し、符号出力装置１４へ出力する（ステップＳ１２３ａ）。また可変長符号化手段１３７は、コンテキストメモリ１２６の内容で第２コンテキストテーブル１２８を更新する（ステップＳ１２３ｂ）。【００６９】
これで１つの第２画素の符号化処理が終わり、次に第３画素の符号化が以下のように行われる。【００７０】
まず第３画素抽出手段１３２３は、第１画素の上隣に位置する第３画素を画像メモリ１２１から抽出し、符号化対象画素メモリ１２２に格納する（ステップＳ１２４）。【００７１】
次に第３近傍画素抽出手段１３３３は、第３画素の近傍に位置する符号化済の画素４つ（上、下、左、右）を画像メモリ１２１から抽出し、近傍画素メモリ１２３に格納する（ステップＳ１２５）。【００７２】
次に画素値予測手段１３４は、近傍画素メモリ１２３に格納されている４画素の画素値の平均値を求め、予測画素値メモリ１２４に格納する（ステップＳ１２６）。【００７３】
次にコンテキスト算出手段１３６は、近傍画素メモリ１２３に格納されている４画素の、それぞれ隣り合う画素同士で差分の絶対値を求め、その総和を量子化してコンテキストメモリ１２６に格納する（ステップＳ１２７）。【００７４】
次に予測誤差算出手段１３５は、予測画素値メモリ１２４に格納された画素予測値と、符号化対象画素メモリ１２２に格納された画素値との差分を求め、予測誤差メモリ１２５に格納する（ステップＳ１２８）。【００７５】
次に可変長符号化手段１３７は、第２コンテキストテーブル１２８に格納されたコンテキストの統計情報から符号化パラメータ（有効桁数の推定値k）を算出して予測誤差メモリ１２５の値を可変長符号化し、符号出力装置１４へ出力する（ステップＳ１２９ａ）。また可変長符号化手段１３７は、コンテキストメモリ１２６の内容で第２コンテキストテーブル１２８を更新する（ステップＳ１２９ｂ）。【００７６】
以上で、１つの第３画素の符号化が終了する。【００７７】
続いて、現解像度のサブサンプリング間隔での符号化が全て完了したかどうかが判定され（ステップＳ１３０）、完了していなければ抽出座標をシフトして（ステップＳ１３１）、ステップＳ１１２に戻る。【００７８】
現解像度のサブサンプリング間隔での符号化が全て完了すると、全ての解像度の処理が完了したかどうかが判定され（ステップＳ１３２）、完了していなければ解像度をシフト（サブサンプリング間隔を半分に）して（ステップＳ１３３）、ステップＳ１１１に戻る。【００７９】
なお、近傍画素の抽出座標が画像外となる場合（画像の上下左右端）は、代替の位置から画素を抽出すればよい。これは、たとえば、画像境界で折り返した位置にある画素を用いるなどの方法があるが、符号化側と復号側とで近傍画素の決定方法が同じであれば復号には問題ないため、その他の座標決定方式を用いるようにしてもよい。【００８０】
また、初期解像度での可変長符号化については、従来のDPCMハフマンなどを用いてもよいし、残り解像度と同じように、コンテキストを算出してゴロムライス符号などを用いて符号化してもよい。なお、初期解像度でコンテキストを算出する場合、たとえば、左上と左の既符号化画素の差、左上と上の既符号化画素の差を求め、その絶対値の総和を量子化してコンテキストとすると効果的である。その際は、画像上端で上の画素が存在しないときは、左の既符号化画素と、二つ左の既符号化画素との差の絶対値を算出し、それを量子化して用いるようにするとよい。この点においても、符号化側と復号側とでコンテキストの算出方法が同じであれば復号には問題ないため、近傍画素が画像外に及ぶ場合には、その他のコンテキスト決定方式を用いるようにしてもよい。【００８１】
次に本実施の形態にかかる符号化装置の効果を説明する。【００８２】
解像度プログレッシブ機能を持つ予測符号化において、未符号化画素の値を既符号化画素から精度良く予測することができる。その理由は、元画像から一定画素おきにサブサンプリングした初期解像度画像を符号化した後、間引かれた画素について符号化する各解像度の符号化処理において、まず前解像度で符号化済の画素４つ（左上、右上、左下、右下）から線形補間してその中心の第１画素を予測し、その残差を可変長符号化し、続いて、第１画素の左および上に位置する第２、第３画素を、直前に符号化された第１画素値および周辺画素３つの合わせて４画素から内挿予測し、その残差を可変長符号化する処理を、繰り返すようにしており、何れの画素も近傍４画素による内挿によって値を精度良く予測することができるためである。【００８３】
解像度プログレッシブ機能を持つ予測符号化において、未符号化画素の値を既符号化画素から簡易な計算で予測することができる。その理由は、第１、第２および第３画素ともその画素を中心とする近傍４画素から予測するため、近傍４画素の画素値の単純な平均値で予測できるためである。【００８４】
圧縮率を高めることができる。その理由は、上記のように未符号化画素の値を既符号化画素から精度良く予測することができるためである。また別の理由は、近傍４画素の差の絶対値の総和をコンテキストとして可変長符号化しており、画素値の空間的局所性に対して符号化パラメータを適応させることができ、その分だけ圧縮率が更に向上するためである。さらに別の理由は、左上、左下、右上および右下の近傍４画素から画素値を予測する第１画素と、上下左右の近傍４画素から画素値を予測する第２および第３画素とで別々のコンテキストテーブルを使用してコンテキストを管理しているため、符号化パラメータの適応度がより改善されるためである。【００８５】
処理速度を速めることができる。その理由は、未符号化画素の値を既符号化画素から簡易な計算で予測できるためである。また別の理由は、一つの第１画素の符号化後にその左隣と上隣の第２および第３画素の符号化を行う処理を走査方向に順次繰り返しており、キャッシュを内蔵するコンピュータで符号化処理を行う際の参照の局所性が増大し、キャッシュヒット率が向上するためである。特に、第２画素の符号化後に、第３画素の符号化を行えば、より一層参照の局所性を増大させることができる。【００８６】
符号化コンテキストの計算が簡易に行える。その理由は、予測に用いる４画素は注目画素を中心として点対称に配置されているため、４画素のどの画素もコンテキストの算出に関して軽重に差を付ける必要がなく、符号化コンテキストは、予測に用いる４画素の隣り合う画素どうしで差の絶対値を求め、その総和を量子化するといった簡単な方法で算出することができるためである。【００８７】
『復号装置の実施の形態』
図４を参照すると、本発明の復号装置の一実施の形態は、符号入力装置２１と、データ記憶装置２２と、プログラム制御により動作するデータ処理装置２３と、画像出力装置２４とから構成されている。【００８８】
符号入力装置２１は、図２に示した符号化装置で符号化された可変長符号をデータ処理装置２３に入力する装置である。【００８９】
データ記憶装置２２は、コンピュータの主記憶装置や補助記憶装置で構成され、復号された画像およびその復号処理の過程で生成された各種のデータを記憶する。本実施の形態の場合、データ記憶装置２２は、復号された画像を記憶する画像メモリ２２１と、復号対象画素の近傍にある４画素の値を記憶する近傍画素メモリ２２３と、近傍４画素から予測された復号対象画素の値を記憶する予測画素値メモリ２２４と、復号対象画素の予測値と実際の値との差分を記憶する予測誤差メモリ２２５と、近傍４画素から求められた符号化コンテキストを記憶するコンテキストメモリ２２６と、第１および第２のコンテキストテーブル２２７および２２８とを有する。【００９０】
データ処理装置２３は、コンピュータのＣＰＵなどで構成され、符号入力装置２１から入力された可変長符号を画像に復号して画像出力装置２４に出力する処理を実行する。本実施の形態の場合、データ処理装置２２は、初期解像度復号手段２３１、第１画素出力手段２３２１、第１近傍画素抽出手段２３３１、第２画素出力手段２３２２、第２近傍画素抽出手段２３３２、第３画素出力手段２３２３、第３近傍画素抽出手段２３３３、画素値予測手段２３４、画素値算出手段２３５、コンテキスト算出手段２３６および予測誤差復号手段２３７を有する。これらのうち、初期解像度復号手段２３１以外の手段は高解像度復号手段を構成する。【００９１】
初期解像度復号手段２３１は、符号入力装置２１から初期解像度の画像に対応する符号を順次入力し、符号化時と同じ予測方式を用いて画素値の予測を行うとともに、符号入力装置２１から入力した符号から予測誤差の値を復号して予測画素値に加算することにより、初期解像度で復号すべき画素すべてを復号して、初期解像度のサブサンプリング間隔で画像メモリ２２１へ出力する。初期解像度の復号が完了すると、残りの解像度の復号が行われる。【００９２】
残り解像度の復号では、まず、初期解像度のサブサンプリング間隔の半分の間隔で、未復号の画素を復号する。そのサブサンプリング間隔での復号が全て完了すると、サブサンプリング間隔をさらに半分にして、未復号の画素がなくなるまで復号を繰り返す。残り解像度の復号において、第１画素出力手段２３２１、第１近傍画素抽出手段２３３１、第２画素出力手段２３２２、第２近傍画素抽出手段２３３２、第３画素出力手段２３２３、第３近傍画素抽出手段２３３３、画素値予測手段２３４、画素値算出手段２３５、コンテキスト算出手段２３６および予測誤差復号手段２３７は、それぞれ以下のような役割を果たす。【００９３】
第１近傍画素抽出手段２３３１は、前解像度で復号済の画素４つ（左上、右上、左下、右下）を画像メモリ２２１から抽出し、近傍画素メモリ２２３に格納する。【００９４】
第１画素出力手段２３２１は、第１近傍画素として抽出された４つの近傍画素の中心に位置する第１画素が復号されると、それを画像メモリ２２１へ出力する。【００９５】
第２近傍画素抽出手段２３３２は、第１画素の復号後に、現解像度において復号すべき画素のうち第１画素の左隣に位置する符号化画素を第２画素とし、この第２画素の近傍に位置する復号済の画素４つ（上、下、左、右）を画像メモリ２２１から抽出し、近傍画素メモリ２２３に格納する。【００９６】
第２画素出力手段２３２２は、第２画素が復号されると、それを画像メモリ２２１へ出力する。【００９７】
第３近傍画素抽出手段２３３３は、第２画素の復号後に、現解像度において復号すべき画素のうち第１画素の上隣に位置する符号化画素を第３画素とし、この第３画素の近傍に位置する復号済の画素４つ（上、下、左、右）を画像メモリ２２１から抽出し、近傍画素メモリ２２３に格納する。【００９８】
第３画素出力手段２３２３は、第３画素が復号されると、それを画素メモリ２２１へ出力する。【００９９】
画素値予測手段２３４は、近傍画素メモリ２２３に格納されている近傍４画素の画素値の平均値を求め、予測画素値メモリ２２４に格納する。【０１００】
コンテキスト算出手段２３６は、近傍画素メモリ２２３に格納されている近傍４画素の、それぞれ隣り合う画素同士で差分の絶対値を求め、その総和を量子化してコンテキストメモリ２２６に格納する。【０１０１】
予測誤差復号手段２３７は、予測誤差の値を符号入力装置２１から読み出して復号し、予測誤差メモリ２２５に格納する。本実施の形態の場合、予測誤差復号手段２３７は適応ゴロムライス復号手段であり、第１および第２のコンテキストテーブル２２７、２２８のうちから所望のテーブルを選択し、それに格納されたコンテキストの統計情報から有効桁数の推定値kを算出し、このkを用いて復号した後、コンテキストメモリ２２６に格納された今回の符号化コンテキストを前記選択したコンテキストテーブルに反映する。【０１０２】
画素値算出手段２３５は、予測画素値メモリ２２４に格納された画素値に予測誤差メモリ２２５の値を加算して目的の画素値を算出し、第１〜第３画素出力手段２３２１〜２３２３を介して画像メモリ２２１へ出力する。【０１０３】
画像出力装置２４は、復号された画像をディスプレイに表示したり、外部記憶装置へ記憶したり、或いは伝送路を通じて他所へ送信する装置などである。【０１０４】
次に、図４及び図５のフローチャートを参照して、本実施の形態にかかる復号装置の全体の動作について詳細に説明する。【０１０５】
まず、画素復号のサブサンプリング間隔が、初期解像度の間隔に設定される（図５のステップＳ２０１）。【０１０６】
初期解像度復号手段２３１は、画素抽出座標を原点に初期化し（ステップＳ２０２）、順次画素を復号する。具体的には、初期解像度のサブサンプリング間隔で近傍画素を抽出し（ステップＳ２０３）、平均値フィルタなどによって外挿予測を行う（ステップＳ２０４）。次に予測誤差の値を符号入力装置２１から読み出して復号し（ステップＳ２０５）、予測画素値に加算することにより画素値を算出する（ステップＳ２０６）。以上により復号された初期解像度の画素値が、初期解像度のサブサンプリング間隔で画像メモリ２２１に順次出力される（ステップＳ２０７）。【０１０７】
続いて、初期解像度の初期サブサンプリング間隔での復号が全て完了したかどうかが判定され（ステップＳ２０８）、完了していなければ抽出座標をシフトして（ステップＳ２０９）、ステップＳ２０３に戻る。完了していれば、解像度をシフト（サブサンプリング間隔を半分に）して（ステップＳ２１０）、残り解像度の復号（ステップＳ２１１以降）へ進む。【０１０８】
残り解像度の符号化では、まず、画素抽出座標が、そのサンプリング間隔での初期座標に初期化される（ステップＳ２１１）。【０１０９】
次に第１近傍画素抽出手段２３３１は、前解像度で符号化済の画素４つ（左上、右上、左下、右下）を抽出し、近傍画素メモリ２２３に格納する（ステップＳ２１２）。【０１１０】
次に画素値予測手段２３４は、近傍画素メモリ２２３に格納されている４画素の画素値の平均値を求め、予測画素値メモリ２２４に格納する（ステップＳ２１３）。【０１１１】
次にコンテキスト算出手段２３６は、近傍画素メモリ２２３に格納されている４画素の、それぞれ隣り合う画素同士で差分の絶対値を求め、その総和を量子化してコンテキストメモリ２２６に格納する（ステップＳ２１４）。【０１１２】
次に予測誤差復号手段２３７は、第１コンテキストテーブル２２７に格納されたコンテキストの統計情報から符号化パラメータ（有効桁数の推定値k）を算出して、符号入力装置２１から読み出した予測誤差の値を復号し、予測誤差メモリ２２５に格納する（ステップＳ２１５ａ）。また予測誤差復号手段２３７は、コンテキストメモリ２２６の内容で第１コンテキストテーブル２２７を更新する（ステップＳ２１５ｂ）。【０１１３】
次に画素値算出手段２３５は、予測画素値メモリ２２４に格納された画素値に予測誤差メモリ２２５の値を加算して目的の第１画素の画素値を算出する（ステップＳ２１６）。【０１１４】
次に第１画素出力手段２３２１は、第１画素の画素値を画像メモリ２２１へ出力する（ステップＳ２１７）。【０１１５】
以上で、１つの第１画素の復号処理が終わり、次に第２画素の復号が以下のように行われる。【０１１６】
まず第２近傍画素抽出手段２３３２は、第１画素の左隣に位置する第２画素の近傍の画素４つ（上、下、左、右）を抽出し、近傍画素メモリ２２３に格納する（ステップＳ２１８）。【０１１７】
次に画素値予測手段２３４は、近傍画素メモリ２２３に格納されている４画素の画素値の平均値を求め、予測画素値メモリ２２４に格納する（ステップＳ２１９）。【０１１８】
次にコンテキスト算出手段２３６は、近傍画素メモリ２２３に格納されている４画素の、それぞれ隣り合う画素同士で差分の絶対値を求め、その総和を量子化してコンテキストメモリ２２６に格納する（ステップＳ２２０）。【０１１９】
次に予測誤差復号手段２３７は、第２コンテキストテーブル２２８に格納されたコンテキストの統計情報から符号化パラメータ（有効桁数の推定値k）を算出して、符号入力装置２１から読み出した予測誤差の値を復号し、予測誤差メモリ２２５に格納する（ステップＳ２２１ａ）。また予測誤差復号手段２３７は、コンテキストメモリ２２６の内容で第２コンテキストテーブル２２８を更新する（ステップＳ２２１ｂ）。【０１２０】
次に画素値算出手段２３５は、予測画素値メモリ２２４に格納された画素値に予測誤差メモリ２２５の値を加算して目的の第２画素の画素値を算出する（ステップＳ２２２）。【０１２１】
次に第２画素出力手段２３２２は、第２画素の画素値を画像メモリ２２１へ出力する（ステップＳ２２３）。【０１２２】
以上で、１つの第２画素の復号処理が終わり、次に第３画素の復号が以下のように実行される。【０１２３】
まず第２近傍画素抽出手段２３３２は、第１画素の上隣に位置する第３画素の近傍の画素４つ（上、下、左、右）を抽出し、近傍画素メモリ２２３に格納する（ステップＳ２２４）。【０１２４】
次に画素値予測手段２３４は、近傍画素メモリ２２３に格納されている４画素の画素値の平均値を求め、予測画素値メモリ２２４に格納する（ステップＳ２２５）。【０１２５】
次にコンテキスト算出手段２３６は、近傍画素メモリ２２３に格納されている４画素の、それぞれ隣り合う画素同士で差分の絶対値を求め、その総和を量子化してコンテキストメモリ２２６に格納する（ステップＳ２２６）。【０１２６】
次に予測誤差復号手段２３７は、第２コンテキストテーブル２２８に格納されたコンテキストの統計情報から符号化パラメータ（有効桁数の推定値k）を算出して、符号入力装置２１から読み出した予測誤差の値を復号し、予測誤差メモリ２２５に格納する（ステップＳ２２７ａ）。また予測誤差復号手段２３７は、コンテキストメモリ２２６の内容で第２コンテキストテーブル２２８を更新する（ステップＳ２２７ｂ）。【０１２７】
次に画素値算出手段２３５は、予測画素値メモリ２２４に格納された画素値に予測誤差メモリ２２５の値を加算して目的の第３画素の画素値を算出する（ステップＳ２２８）。【０１２８】
次に第３画素出力手段２３２３は、第３画素の画素値を画像メモリ２２１へ出力する（ステップＳ２２９）。【０１２９】
以上で、１つの第３画素の復号が終了する。【０１３０】
続いて、現解像度のサブサンプリング間隔での復号が全て完了したかどうかが判定され（ステップＳ２３０）、完了していなければ抽出座標をシフトして（ステップＳ２３１）、ステップＳ２１２に戻る。【０１３１】
現解像度のサブサンプリング間隔での復号が全て完了すると、全ての解像度の処理が完了したかどうかが判定され（ステップＳ２３２）、完了していなければ解像度をシフト（サブサンプリング間隔を半分に）して（ステップＳ２３３）、ステップＳ２１１に戻る。【０１３２】
本実施の形態の復号装置によれば、図２に示した実施の形態の符号化装置で符号化された画像を精度良く高速に復号することができる。
【実施例】
【０１３３】
『符号化装置の実施例』
次に、本発明の符号化装置の具体的な実施例について説明する。【０１３４】
図６および図７は、本実施例にかかる符号化装置による符号化動作を模式的に示した図である。本実施例では、データ処理装置１３としてパーソナルコンピュータを、データ記憶装置１２として半導体メモリ（パーソナルコンピュータに含まれる）を、符号出力装置１４として磁気ディスク装置を備えているものとする。また、画像データは、磁気ディスク装置上のファイルとして与えられるものとする。【０１３５】
まず、磁気ディスク装置から、画像データが読み込まれ、画像メモリ１２１に格納される。【０１３６】
初期解像度符号化手段１３１は、画像メモリ１２１から初期解像度となる所定間隔で画素を抽出して可変長符号化を行い、符号を磁気ディスク装置へ出力する。ここでは、初期解像度を原画像の1/4とし、縦横とも４画素間隔で画素を抽出するものとする。【０１３７】
具体的には、図６の画像メモリ１２１の(1)→(2)→(3)→…→(11)→(12)の順に画素を抽出し、符号化済の上・左画素からの平均値を予測値として（たとえば、(2)と(5)の平均値を(6)の予測値とする）、２次元DPCM符号化を行う。【０１３８】
以上の処理によって、初期解像度の画素全てが符号化されると、次の解像度（原画像の1/2）の符号化処理へ移行する。【０１３９】
図７は、1/2解像度の符号化処理を模式的に示した図である。a,b,c,d,…,j,k,lは、初期解像度符号化手段１３１によって既に符号化済の画素であり、1/2解像度の処理では、(1)→(2)→(3)→…→(17)→(18)の順に符号化が行われる。【０１４０】
まず、第１画素抽出手段１３２１は、画素(1)を抽出して符号化対象画素メモリ１２２に格納する。また、第１近傍画素抽出手段１３３１は、画素(1)の左上、右上、左下および右下の既符号化画素、すなわちa,b,e,fを抽出して近傍画素メモリ１２３に格納する。【０１４１】
続いて、これら近傍画素a,b,e,fから、画素値の予測、および符号化コンテキスト値の算出が行われ、符号化対象画素と予測値との差分が符号化される。詳しくは後述する。【０１４２】
次に、第２画素抽出手段１３２２は、画素(2)を抽出して符号化対象画素メモリ１２２に格納する。また、第２近傍画素抽出手段１３３２は、画素(2)の上、下、左、右の既符号化画素を抽出して近傍画素メモリ１２３に格納する。ここで、画素(2)は画像左端のため、左画素は折り返して(1)を参照する。この結果、a,e,(1),(1)が抽出され、近傍画素メモリ１２３に格納される。【０１４３】
続いて、これら近傍画素a,e,(1),(1)から、画素値の予測、および符号化コンテキスト値の算出が行われ、符号化対象画素と予測値との差分が符号化される。詳しくは後述する。【０１４４】
次に、第３画素抽出手段１３２３は、画素(3)を抽出して符号化対象画素メモリ１２２に格納する。また、第３近傍画素抽出手段１３３３は、画素(3)の上、下、左、右の既符号化画素を抽出して近傍画素メモリ１２３に格納する。ここで、画素(3)は画像上端のため、上画素は折り返して(1)を参照する。この結果、a,b,(1),(1)が抽出され、近傍画素メモリ１２３に格納される。【０１４５】
続いて、これら近傍画素a,b,(1),(1)から、画素値の予測、および符号化コンテキスト値の算出が行われ、符号化対象画素と予測値との差分が符号化される。詳しくは後述する。【０１４６】
画素(4)以降についても、以上の処理が同様に行われる。なお、(16)〜(18)のように、画像端でない画素については、近傍画素として、既に符号化済の近傍４画素の全てが抽出される。【０１４７】
次に、図８を参照して、符号化の過程で行われる画素値の予測および符号化コンテキスト値の算出、差分の符号化について説明する。【０１４８】
図８は、図７における画素(16)の符号化動作を模式的に示した図である。第１画素抽出手段１３２１および第１近傍画素抽出手段１３３１によって、符号化対象画素メモリ１２２には画素(16)が格納され、近傍画素メモリ１２３には画素f,g,j,kが格納されている。【０１４９】
画素値予測手段１３４は、画素f,g,j,kの平均値Predictを求め、予測画素値メモリ１２４に格納する。【０１５０】
予測誤差算出手段１３５は、符号化対象画素(16)と予測画素値Predictとの差分DPCMを求め、予測誤差メモリ１２５に格納する。【０１５１】
コンテキスト算出手段１３６は、隣り合う近傍画素同士の差分の絶対値の総和を求め、それを量子化してContextとし、コンテキストメモリ１２６に格納する。ここでは、fとg、gとk、kとj、jとfの差分を求め、その絶対値の総和を0〜8の９通りの値に量子化する。【０１５２】
コンテキスト算出手段１３６は更に、可変長符号化手段１３７が斜め予測の場合と縦横予測の場合とで別のコンテキストを用いることができるよう、コンテキストテーブル番号を選択する。すなわち、画素(1)(4)(7)(10)(13)(16)…は左上、右上、左下および右下の斜め方向にある近傍画素から予測を行うため、それ用の第１のコンテキストテーブル１２７を選択し、画素(2)(3)(5)(6)(8)(9)…は上下左右にある近傍画素から予測を行うため、第１のコンテキストテーブル１２７とは別の第２のコンテキストテーブル１２８を選択する。【０１５３】
可変長符号化手段１３７は、選択されたコンテキストテーブル１２７または１２８およびコンテキスト値に応じて、特許文献４の方式などを用いて適応ゴロムライス符号化を行う。この適応ゴロムライス符号化処理では、選択されたコンテキストテーブルの当該コンテキスト値における出現数ｎと予測誤差振幅の累積和ａが順次更新され、最適なゴロムパラメータ（有効桁数の推定値）がその都度算出されて、そのパラメータを用いてゴロムライス符号化が行われ、また選択されたコンテキストテーブルの当該コンテキスト値における出現数ｎと累積和ａとが更新される。【０１５４】
以上の処理が1/2解像度の画素全てについて符号化が完了するまで続けられ、1/2解像度での符号化処理が完了する。さらに、1/1解像度の画素全てについて符号化が完了するまで同様の処理を行うことにより、全ての階層の符号化が完了し、磁気ディスクへ出力される。【０１５５】
『復号装置の実施例』
続いて、本発明の復号装置の実施例について説明する。【０１５６】
図６および図７は本実施例の復号装置による復号動作を模式的に示している。本実施例では、データ処理装置２３としてパーソナルコンピュータを、データ記憶装置２２として半導体メモリ（パーソナルコンピュータに含まれる）を、画像出力装置２４として磁気ディスク装置を備えているものとする。また、符号データは、磁気ディスク装置上のファイルとして与えられるものとする。【０１５７】
初期解像度復号手段２３１は、符号データから順次符号を復号し、初期解像度となる所定間隔で、画素を画像メモリ２２１へ出力する。ここでは、初期解像度を原画像の1/4とし、４画素間隔で画素を復号するものとする。具体的には、図６に示すように画像メモリ２２１の(1)→(2)→(3)→…→(11)→(12)の順に、符号化済の上と左画素からの平均値を予測値として（たとえば、(2)と(5)の平均値を(6)の予測値とする）、２次元DPCM復号を行い、画素値を出力する。【０１５８】
以上の処理によって、初期解像度の画素全てが復号されると、次の解像度（原画像の1/2）の復号処理へ移行する。【０１５９】
図７は、1/2解像度の復号処理を模式的に示している。a,b,c,d,…,j,k,lは、初期解像度復号手段２３１によって既に復号済の画素であり、1/2解像度の処理では、(1)→(2)→(3)→…→(17)→(18)の順に復号が行われる。【０１６０】
まず、第１近傍画素抽出手段２３３１は、画素(1)の左上、右上、左下、右下の既符号化画素、すなわちa,b,e,fを抽出して近傍画素メモリ２２３に格納する。【０１６１】
続いて、これら近傍画素a,b,e,fから、画素値の予測、および符号化コンテキスト値の算出が行われ、予測差分が復号される。さらに、画素予測値と予測差分とによって画素値が算出され、画素(1)として画像メモリ２２１へ出力される。詳しくは後述する。【０１６２】
次に、第２近傍画素抽出手段２３３２は、画素(2)の上、下、左、右の既符号化画素を抽出して近傍画素メモリ２２３に格納する。ここで、画素(2)は画像左端のため、左画素は折り返して画素(1)を参照する。この結果、a,e,(1),(1)が抽出され、近傍画素メモリ２２３に格納される。【０１６３】
続いて、これら近傍画素a,e,(1),(1)から、画素値の予測、および符号化コンテキスト値の算出が行われ、予測差分が復号される。さらに、画素予測値と予測差分とによって画素値が算出され、画素(2)として画像メモリ２２１へ出力される。詳しくは後述する。【０１６４】
次に、第３近傍画素抽出手段２３３３は、画素(3)の上、下、左、右の既符号化画素を抽出して近傍画素メモリ２２３に格納する。ここで、画素(3)は画像上端のため、上画素は折り返して(1)を参照する。この結果、a,b,(1),(1)が抽出され、近傍画素メモリ２２３に格納される。【０１６５】
続いて、これら近傍画素a,b,(1),(1)から、画素値の予測、および符号化コンテキスト値の算出が行われ、予測差分が復号される。さらに、画素予測値と予測差分とによって画素値が算出され、画素(3)として画像メモリ２２１へ出力される。詳しくは後述する。【０１６６】
画素(4)以降についても、以上の処理が同様に行われる。なお、画素(16)〜(18)のように、画像端でない画素については、近傍画素として、既に符号化済の近傍画素の全てが抽出される。【０１６７】
次に、図９を参照して、復号処理における画素値の予測および符号化コンテキスト値の算出、差分の復号、画素値の算出について説明する。【０１６８】
図９は、図７における画素(16)の復号動作を模式的に示している。第１近傍画素抽出手段２３３１によって、近傍画素メモリ２２３には画素f,g,j,kが格納されている。【０１６９】
画素値予測手段２３４は、画素f,g,j,kの平均値Predictを求め、予測画素値メモリ２２４に格納する。【０１７０】
コンテキスト算出手段２３６は、隣り合う近傍画素同士の差分の絶対値の総和を求め、それを量子化してContextとし、コンテキストメモリ２２６に格納する。ここでは、fとg、gとk、kとj、jとfの差分を求め、その絶対値の総和を0〜8の９通りの値に量子化する。【０１７１】
コンテキスト算出手段は更に、斜め予測の場合と縦横予測の場合とで別のコンテキストを用いることができるよう、コンテキストテーブル番号を選択する。すなわち、画素(1)(4)(7)(10)(13)(16)…は左上、右上、左下および右下の斜め方向にある近傍画素から予測を行うため、それ用の第１のコンテキストテーブル２２７を選択し、画素(2)(3)(5)(6)(8)(9)…は上下左右にある近傍画素から予測を行うため、第１のコンテキストテーブル２２７とは別の第２のコンテキストテーブル２２８を選択する。【０１７２】
予測誤差復号手段２３７は、選択されたコンテキストテーブルおよびコンテキスト値に応じて、特許文献４の方式などを用いて適応ゴロムライス復号を行う。適応ゴロムライス復号では、コンテキストテーブルの当該コンテキスト値における出現数ｎと、予測誤差振幅の累積和ａが順次更新され、最適なゴロムパラメータ（有効桁数）がその都度算出される。【０１７３】
画素値算出手段２３５は、予測画素値Predictに復号された予測差分の値を加え、復号対象画素(16)として出力する。【０１７４】
以上の処理が1/2解像度の画素全てについて復号が完了するまで続けられ、1/2解像度での復号処理が完了する。さらに、1/1解像度の画素全てについて復号が完了するまで同様の処理を行うことにより、全ての階層の復号が完了し、画像メモリ２２１の内容が磁気ディスクへ出力される。【０１７５】
以上本発明の実施の形態および実施例について説明したが、本発明は以上の例にのみ限定されず、その他各種の付加変更が可能である。【０１７６】
例えば、可変長符号としてゴロムライス符号を使用したが、ハフマン符号など他の種類の可変長符号を使用することもできる。【０１７７】
また、1/4,1/2,1/1の３階層の解像度を持つ例を示したが、４階層以上の解像度プログレッシブ機能に対しても適用可能である。【０１７８】
また、符号化対象画像の縦横の画素数Ｍ、Ｎが何れも２のべき乗に一致する例を示したが、一致しない場合であっても、画像境界で折り返した位置にある画素を用いるなどの方法によって端数部分を同様に処理することができる。【０１７９】
また、各画素値は多ビットのグレースケールで表されているものとして説明したが、それ以外の形式、例えば、多ビットのＲＧＢカラー値や、それを輝度信号（Ｙ）と２つの色差信号（Ｕ、Ｖ）に変換した信号であっても、それらの各々に対して同様の処理を施すことにより符号化および復号が可能である。この場合、コンテキストテーブルはそれぞれ別々に設けるようにしても良いし、性質の似ているものどうしで共用しても良い。例えば、ＵとＶは性質が似ているので、ＵとＶとで第１および第２のコンテキストテーブルを共用させても良い。【０１８０】
また、第１画素の符号化後に第２および第３画素の符号化を行う方法であれば、符号化の順序は図７に示した順序に限定されない。例えば、画像端で折り返して、…(10)→(11)→(12)→(13)→(14)→(15)…の順で符号化しても良い。また、縦方向に走査して、(1)→(2)→(3)→(13)→(14)→(15)…の順で符号化しても良く、ジグザグに走査して、(1)→(2)→(3)→(4)→(5)→(6)→(13)→(14)→(15)…の順で符号化しても良い。【０１８１】
また、復号については第２および第３画素の処理前に第１画素が復号されていることが必要であるが、符号化では最終符号出力までの処理は第１〜第３画素について並行して行うことが可能である。つまり、第１画素の符号化処理と並行して第２画素および第３画素の符号化処理を進めることにより、符号化の処理速度を向上させることができる。【０１８２】
また、本発明の符号化装置および復号装置は、その有する機能をハードウェア的に実現することは勿論、コンピュータとプログラムとで実現することができる。プログラムは、磁気ディスクや半導体メモリ等のコンピュータ可読記録媒体に記録されて提供され、コンピュータの立ち上げ時などにコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータを前述した各実施の形態における符号化装置、復号装置として機能させ、前述した符号化処理、復号処理を行わせる。
【産業上の利用可能性】
【０１８３】
本発明によれば、監視や解析など、高品質の映像取得が必要なシステムにおいて、画像を高速に符号化して伝送するといった用途に適用できる。また、高解像度の映像を高品質にアーカイブし、必要な解像度までを高速に抽出して伝送し表示するといった用途にも適用できる。【０１８４】
本出願は、２００６年１１月２４日に出願された特願２００６−３１６６２７号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2008062687.tif 000003
【図２】
2008062687.tif 000004
【図３】
2008062687.tif 000005
【図４】
2008062687.tif 000006
【図５】
2008062687.tif 000007
【図６】
2008062687.tif 000008
【図７】
2008062687.tif 000009
【図８】
2008062687.tif 000010
【図９】
2008062687.tif 000011
【図１０】
2008062687.tif 000012
【図１１】
2008062687.tif 000013
【図１２】
2008062687.tif 000014
【手続補正書】
【提出日】平成20年8月1日(2008.8.1)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
画像から一定画素おきにサブサンプリングした初期解像度画像を符号化する初期解像度符号化手段と、
サブサンプリング間隔を順次半分にした画像を符号化する高解像度符号化手段と
を有し、
前記高解像度符号化手段は、
前解像度で符号化済の近傍４画素を抽出する第１近傍画素抽出手段と、
前解像度で符号化済の近傍４画素の中心に位置する画素を第１画素として抽出する第１画素抽出手段と、
前記第１画素の左に位置する未符号化の画素を第２画素として抽出する第２画素抽出手段と、
前記第２画素の上下左右に位置する符号化済の近傍４画素を抽出する第２近傍画素抽出手段と、
前記第１画素の上に位置する未符号化の画素を第３画素として抽出する第３画素抽出手段と、
前記第３画素の上下左右に位置する符号化済の近傍４画素を抽出する第３近傍画素抽出手段と、
現解像度において符号化すべき画素のうち、前記第１画素は前記第１近傍画素抽出手段で抽出された前解像度で符号化済の近傍４画素から線形補間により値を予測し、前記第２画素又は前記第３の画素は、前記第１画素の符号化後に、前記第２近傍画素抽出手段又は前記第３近傍画素抽出手段によって抽出された符号化済の近傍４画素から線形補間により値を予測する画素値予測手段と、
符号化対象画素と予測値との残差を求める予測誤差算出手段と、
残差を符号化する可変長符号化手段と
を備えることを特徴とする符号化装置。
【請求項２】
（削除）
【請求項３】
（削除）
【請求項４】
前記高解像度符号化手段は、前記第２画素の符号化後に前記第３画素の符号化を行うことを特徴とする請求項１に記載の符号化装置。
【請求項５】
前記高解像度符号化手段は、前記第１画素の符号化処理と並行して前記第２画素および前記第３画素の符号化処理を行うことを特徴とする請求項１に記載の符号化装置。
【請求項６】
前記高解像度符号化手段は、前記近傍４画素について、隣り合う画素どうしで差分の絶対値を求め、その総和に対して量子化処理を行って符号化コンテキストを求めるコンテキスト算出手段を備え、
前記可変長符号化手段は、前記符号化コンテキストに応じて符号化パラメータを変更する
ことを特徴とする請求項１、請求項４、請求項５のいずれかに記載の符号化装置。
【請求項７】
前記コンテキスト算出手段は、前記近傍４画素の符号化コンテキストを、前記近傍４画素がその中心に位置する予測対象画素の左上、左下、右上、右下に存在する場合と、上下左右に存在する場合とで、それぞれ異なるコンテキストとして管理することを特徴とする請求項６に記載の符号化装置。
【請求項８】
画像から一定画素おきにサブサンプリングした初期解像度画像を入力符号から復号する初期解像度復号手段と、
サブサンプリング間隔を順次半分にした画像を復号する高解像度復号手段と
を有し、
前記高解像度復号手段は、
前解像度で復号済の近傍４画素を抽出する第１近傍画素抽出手段と、
現解像度において復号すべき画素のうち、前解像度で復号済の近傍４画素の中心に位置する画素については前記近傍４画素から線形補間により値を予測し、残りの画素については当該画素を中心としてその上下左右に位置する近傍４画素のすべてが前解像度および現解像度で復号済になるのを待って当該近傍４画素から線形補間により値を予測する画素値予測手段と、
復号対象画素と予測値との残差を入力符号から復号する予測誤差復号手段と、
前記予測された画素値に前記復号された残差を加算して目的の画素値を算出する画素値算出手段と、
前記第１近傍画素抽出手段で抽出された近傍４画素の中心に位置する第１画素について前記画素値算出手段で算出された画素値を出力する第１画素出力手段と、
前記第１画素の復号後に前記第１画素の左に位置する未復号の第２画素の上下左右に位置する復号済の近傍４画素を抽出する第２近傍画素抽出手段と、
前記第２近傍画素抽出手段で抽出された近傍４画素の中心に位置する第２画素について前記画素値算出手段で算出された画素値を出力する第２画素出力手段と、
前記第１画素の復号後に前記第１画素の上に位置する未復号の第３画素の上下左右に位置する復号済の近傍４画素を抽出する第３近傍画素抽出手段と、
前記第３近傍画素抽出手段で抽出された近傍４画素の中心に位置する第３画素について前記画素値算出手段で算出された画素値を出力する第３画素出力手段と
を備えることを特徴とする復号装置。
【請求項９】
（削除）
【請求項１０】
（削除）
【請求項１１】
前記高解像度復号手段は、前記第２画素の復号後に前記第３画素の復号を行うことを特徴とする請求項８に記載の復号装置。
【請求項１２】
前記高解像度復号手段は、前記近傍４画素について、隣り合う画素どうしで差分の絶対値を求め、その総和に対して量子化処理を行って符号化コンテキストを求めるコンテキスト算出手段を備え、
前記予測誤差復号手段は、前記符号化コンテキストに応じて復号パラメータを変更すること
を特徴とする請求項８又は請求項１１のいずれかに記載の復号装置。
【請求項１３】
前記コンテキスト算出手段は、前記近傍４画素の符号化コンテキストを、前記近傍４画素がその中心に位置する予測対象画素の左上、左下、右上、右下に存在する場合と、上下左右に存在する場合とで、それぞれ異なるコンテキストとして管理することを特徴とする請求項１２に記載の復号装置。
【請求項１４】
コンピュータを用いて画像を符号化する方法であって、
前記コンピュータが、画像から一定画素おきにサブサンプリングした初期解像度画像を符号化する第１のステップと、
前記コンピュータが、サブサンプリング間隔を順次半分にした画像を符号化する第２のステップと
を含み、
前記第２のステップは、
現解像度において符号化すべき画素のうち、前解像度で符号化済の近傍４画素の中心に位置する第１の画素については前記近傍４画素から線形補間により値を予測し、
前記第１画素の左に位置する未符号化の第２画素と、前記第１画素の上に位置する未符号化の第３画素とは、前記第１の画素の符号化後、当該画素を中心としてその上下左右に位置する近傍４画素から線形補間により値を予測し、
それぞれ、符号化対象画素と予測値との残差を求め、該残差を可変長符号化する処理
を含むことを特徴とする符号化方法。
【請求項１５】
コンピュータを用いて入力符号から画像を復号する方法であって、
前記コンピュータが、画像から一定画素おきにサブサンプリングした初期解像度画像を入力符号から復号する第１のステップと、
前記コンピュータが、サブサンプリング間隔を順次半分にした画像を復号する第２のステップと
を含み、
前記第２のステップは、
現解像度において復号すべき画素のうち、前解像度で復号済の近傍４画素の中心に位置する第１の画素については前記近傍４画素から線形補間により値を予測し、
前記第１画素の左に位置する未復号の第２画素と、前記第１画素の上に位置する未符号化の第３画素とは、前記第１画素の復号後に、当該画素を中心としてその上下左右に位置する近傍４画素のすべてが前解像度および現解像度で復号済になるのを待って当該近傍４画素から線形補間により値を予測し、
それぞれ、復号対象画素と予測値との残差を入力符号から復号し、前記予測された画素値に前記復号された残差を加算して目的の画素値を算出する処理を含むことを特徴とする復号方法。
【請求項１６】
コンピュータに、
画像から一定画素おきにサブサンプリングした初期解像度画像を符号化する第１の処理と、
サブサンプリング間隔を順次半分にした画像を符号化する処理であって、各解像度の符号化処理において、
現解像度において符号化すべき画素のうち、前解像度で符号化済の近傍４画素の中心に位置する第１の画素については前記近傍４画素から線形補間により値を予測し、
前記第１画素の左に位置する未符号化の第２画素と、前記第１画素の上に位置する未符号化の第３画素とは、前記第１の画素の符号化後、当該画素を中心としてその上下左右に位置する近傍４画素から線形補間により値を予測し、
それぞれ、符号化対象画素と予測値との残差を求め、該残差を可変長符号化する第２の処理と
を行わせるための符号化プログラム。
【請求項１７】
前記第２の処理は、
前解像度で符号化済の近傍４画素を抽出するステップと、
前解像度で符号化済の近傍４画素の中心に位置する画素を第１画素として抽出するステップと、
前記第１画素の左に位置する未符号化の画素を第２画素として抽出するステップと、
前記第２画素の上下左右に位置する符号化済の近傍４画素を抽出するステップと、
前記第１画素の上に位置する未符号化の画素を第３画素として抽出するステップと、
前記第３画素の上下左右に位置する符号化済の近傍４画素を抽出するステップと
を含むことを特徴とする請求項１６に記載の符号化プログラム。
【請求項１８】
（削除）
【請求項１９】
前記第２の処理では、前記第２画素の符号化後に前記第３画素の符号化を行うことを特徴とする請求項１７に記載の符号化プログラム。
【請求項２０】
前記第２の処理では、前記第１画素の符号化処理と並行して前記第２画素および前記第３画素の符号化処理を行うことを特徴とする請求項１７に記載の符号化プログラム。
【請求項２１】
前記第２の処理では、前記近傍４画素について、隣り合う画素どうしで差分の絶対値を求め、その総和に対して量子化処理を行って符号化コンテキストを求めるステップを含み、
前記符号化コンテキストに応じて可変長符号化の符号化パラメータを変更することを特徴とする請求項１６、請求項１７、請求項１９、請求項２０のいずれかに記載の符号化プログラム。
【請求項２２】
前記近傍４画素の符号化コンテキストを、前記近傍４画素がその中心に位置する予測対象画素の左上、左下、右上、右下に存在する場合と、上下左右に存在する場合とで、それぞれ異なるコンテキストとして管理することを特徴とする請求項２１に記載の符号化プログラム。
【請求項２３】
コンピュータに、
画像から一定画素おきにサブサンプリングした初期解像度画像を入力符号から復号する第１の処理と、
サブサンプリング間隔を順次半分にした画像を復号する処理であって、各解像度の復号処理において、現解像度において復号すべき画素のうち、前解像度で復号済の近傍４画素の中心に第１の位置する画素については前記近傍４画素から線形補間により値を予測し、
前記第１画素の左に位置する未復号の第２画素と、前記第１画素の上に位置する未符号化の第３画素とは、前記第１画素の復号後に、当該画素を中心としてその上下左右に位置する近傍４画素のすべてが前解像度および現解像度で復号済になるのを待って当該近傍４画素から線形補間により値を予測し、
それぞれ、復号対象画素と予測値との残差を入力符号から復号し、前記予測された画素値に前記復号された残差を加算して目的の画素値を算出する第２の処理と
を行わせるための復号プログラム。
【請求項２４】
前記第２の処理は、
前解像度で復号済の近傍４画素を抽出するステップと、
該抽出された近傍４画素の中心に位置する第１画素について算出された画素値を出力するステップと、
前記第１画素の復号後に前記第１画素の左に位置する未復号の第２画素の上下左右に位置する復号済の近傍４画素を抽出するステップと、
該抽出された近傍４画素の中心に位置する第２画素について算出された画素値を出力するステップと、
前記第２画素の復号後に前記第１画素の上に位置する未復号の第３画素の上下左右に位置する復号済の近傍４画素を抽出するステップと、
該抽出された近傍４画素の中心に位置する第３画素について算出された画素値を出力するステップと
を含むことを特徴とする請求項２３に記載の復号プログラム。
【請求項２５】
（削除）
【請求項２６】
前記第２の処理では、前記第２画素の復号後に前記第３画素の復号を行うことを特徴とする請求項２５に記載の復号プログラム。
【請求項２７】
前記第２の処理では、前記近傍４画素について、隣り合う画素どうしで差分の絶対値を求め、その総和に対して量子化処理を行って符号化コンテキストを求めるステップを含み、
前記符号化コンテキストに応じて復号パラメータを変更する
ことを特徴とする請求項２３、請求項２４、請求項２６のいずれかに記載の復号プログラム。
【請求項２８】
前記近傍４画素の符号化コンテキストを、前記近傍４画素がその中心に位置する予測対象画素の左上、左下、右上、右下に存在する場合と、上下左右に存在する場合とで、それぞれ異なるコンテキストとして管理することを特徴とする請求項２７に記載の復号プログラム。
【請求項２９】
画像から一定画素おきにサブサンプリングした初期解像度画像を符号化する初期解像度符号化手段と、
サブサンプリング間隔を順次半分にした画像を符号化する高解像度符号化手段とを有し、
前記高解像度符号化手段は、
前解像度で符号化済の近傍４画素の中心に位置する画素を第１画素として抽出する第１画素抽出手段と、
前記第１画素の左に位置する未符号化の画素を第２画素として抽出する第２画素抽出手段と、
前記第１画素の上に位置する未符号化の画素を第３画素として抽出する第３画素抽出手段とを有し、
前記高解像度符号化手段は、
一つの前記第１画素の符号化後に、一つの前記第２画素と一つの前記第３画素との符号化を行う
ことを特徴とする符号化装置。
【請求項３０】
画像から一定画素おきにサブサンプリングした初期解像度画像を符号化する初期解像度符号化手段と、
サブサンプリング間隔を順次半分にした画像を符号化する高解像度符号化手段とを有し、
前記高解像度符号化手段は、現解像度において符号化すべき画素のうち、前解像度で符号化済の近傍４画素の中心に位置する画素については前記近傍４画素から線形補間により値を予測し、残りの画素については当該画素を中心としてその上下左右に位置する近傍４画素から線形補間により値を予測する画素値予測手段と、
符号化対象画素と予測値との残差を求める予測誤差算出手段と、
残差を符号化する可変長符号化手段と、
前記近傍４画素について、隣り合う画素どうしで差分の絶対値を求め、その総和に対して量子化処理を行って符号化コンテキストを求めるコンテキスト算出手段を備え、
前記可変長符号化手段は、前記符号化コンテキストに応じて符号化パラメータを変更する
ことを特徴とする符号化装置。
【請求項３１】
画像から一定画素おきにサブサンプリングした初期解像度画像を入力符号から復号する初期解像度復号手段と、
サブサンプリング間隔を順次半分にした画像を復号する高解像度復号手段とを有し、
前記高解像度復号手段は、
前解像度で復号済の近傍４画素を抽出する第１近傍画素抽出手段と、
該第１近傍画素抽出手段で抽出された近傍４画素の中心に位置する第１画素について前記画素値算出手段で算出された画素値を出力する第１画素出力手段と、
前記第１画素の復号後に前記第１画素の左に位置する未復号の第２画素の上下左右に位置する復号済の近傍４画素を抽出する第２近傍画素抽出手段と、
前記第２近傍画素抽出手段で抽出された近傍４画素の中心に位置する第２画素について前記画素値算出手段で算出された画素値を出力する第２画素出力手段と、
前記第１画素の復号後に前記第１画素の上に位置する未復号の第３画素の上下左右に位置する復号済の近傍４画素を抽出する第３近傍画素抽出手段と、
前記第３近傍画素抽出手段で抽出された近傍４画素の中心に位置する第３画素について前記画素値算出手段で算出された画素値を出力する第３画素出力手段と
を備えることを特徴とする復号装置。
【請求項３２】
画像から一定画素おきにサブサンプリングした初期解像度画像を入力符号から復号する初期解像度復号手段と、
サブサンプリング間隔を順次半分にした画像を復号する高解像度復号手段と
を有し、
前記高解像度復号手段は、
現解像度において復号すべき画素のうち、前解像度で復号済の近傍４画素の中心に位置する画素については前記近傍４画素から線形補間により値を予測し、残りの画素については当該画素を中心としてその上下左右に位置する近傍４画素のすべてが前解像度および現解像度で復号済になるのを待って当該近傍４画素から線形補間により値を予測する画素値予測手段と、
復号対象画素と予測値との残差を入力符号から復号する予測誤差復号手段と、
前記予測された画素値に前記復号された残差を加算して目的の画素値を算出する画素値算出手段とを備え、
前記高解像度復号手段は、前記近傍４画素について、隣り合う画素どうしで差分の絶対値を求め、その総和に対して量子化処理を行って符号化コンテキストを求めるコンテキスト算出手段を備え、
前記予測誤差復号手段は、前記符号化コンテキストに応じて復号パラメータを変更する
ことを特徴とする復号装置。
【国際調査報告】
2008062687.tif 000015
2008062687.tif 000016
2008062687.tif 000017