(57)【要約】【課題】任意方向のエッジが存在する場合でもエッジ方向に適応した予測を行うことが可能な予測器を提供する。【解決手段】予測の参照領域の各画素に対し、水平，垂直，４５°対角，−４５°対角方向に隣接する画素対の加重平均を各方向の勾配とする。対象画素に対し、水平，垂直，４５°対角，−４５°対角方向の各方向に隣接する４つの隣接画素のうち少なくとも２つの画素の画素値の加重平均を演算し、当該加重平均を対象画素の画素値の予測値として出力する。このとき、加重平均において、各画素の画素値の重みを、その画素の隣接方向の勾配の逆数に比例させる。【選択図】図１
2007259306.tif 000002
【特許請求の範囲】
【請求項１】
二次元の入力画像のラスタ走査により順次入力される対象画素に対し、その画素値を予測する予測器であって、
前記入力画像の既走査領域のうちの前記対象画素の近傍の所定の領域を参照領域（causal area）とすると、少なくとも前記参照領域内の画素の画素値を保持する参照領域記憶手段と、
当該参照領域の各画素に対して、水平方向に相隣接する画素対について画素値の絶対値差の所定の加重和又は加重平均を演算し、その演算値又はそれに定数を加えた値を水平勾配Ｄ１として出力する水平勾配演算手段と、
当該参照領域の各画素に対して、垂直方向に相隣接する画素対について画素値の絶対値差の所定の加重和又は加重平均を演算し、その演算値又はそれに定数を加えた値を垂直勾配Ｄ２として出力する垂直勾配演算手段と、
当該参照領域の各画素に対して、４５°対角方向に相隣接する画素対について画素値の絶対値差の所定の加重和又は加重平均を演算し、その演算値又はそれに定数を加えた値を正対角勾配Ｄ３として出力する正対角勾配演算手段と、
当該参照領域の各画素に対して、−４５°対角方向に相隣接する画素対について画素値の絶対値差の所定の加重和又は加重平均を演算し、その演算値又はそれに定数を加えた値を負対角勾配Ｄ４として出力する負対角勾配演算手段と、
前記対象画素に対し、水平方向，垂直方向，４５°対角方向，及び−４５°対角方向の各方向に隣接する既走査領域内の４つの画素のうち少なくとも２つの画素の画素値の加重平均を演算し、当該加重平均を対象画素の画素値の予測値として出力する予測値演算手段と、
を備え、
前記予測値演算手段は、前記加重平均において、各画素の画素値の重みを、その画素の隣接方向の勾配の逆数に比例させることを特徴とする予測器。
【請求項２】
前記水平勾配Ｄ１，前記垂直勾配Ｄ２，前記正対角勾配Ｄ３，及び前記負対角勾配Ｄ４のうち、最小の勾配Ｄｍｉｎ及び２番目に小さい勾配Ｄｍｉｎ２を決定する参照方向決定手段を備え、
前記予測値演算手段は、前記対象画素に対し前記勾配Ｄｍｉｎに対応する方向に隣接する画素の画素値Ｃｍｉｎの重みをη／Ｄｍｉｎ２（ηは規格化定数）、前記勾配Ｄｍｉｎ２に対応する方向に隣接する画素の画素値Ｃｍｉｎ２の重みをη／Ｄｍｉｎとして、画素値Ｃｍｉｎ及び画素値Ｃｍｉｎ２の加重平均を演算し、当該加重平均を対象画素の画素値の予測値として出力することを特徴とする請求項１記載の予測器。
【請求項３】
前記水平勾配演算手段、前記垂直勾配演算手段、前記正対角勾配演算手段、及び前記負対角勾配演算手段は、各画素対の重み係数を、当該画素対の２つの画素のうち前記対象画素に最も近い画素から前記対象画素までの距離の逆数に比例する値として、前記絶対値差の所定の加重和又は加重平均を演算することを特徴とする請求項１又は２に記載の予測器。
【請求項４】
前記ラスタ走査の水平進行方向をｘ軸、垂直進行方向をｙ軸とし、対象画素の座標を（ｘ，ｙ）としたとき、前記参照領域は、座標が（ｘ−１，ｙ），（ｘ−２，ｙ），（ｘ＋１，ｙ−１），（ｘ，ｙ−１），（ｘ−１，ｙ−１），（ｘ−２，ｙ−１），（ｘ＋１，ｙ−２），（ｘ，ｙ−２），（ｘ−１，ｙ−１）の９つの画素で構成されていることを特徴とする請求項１乃至３の何れか一に記載の予測器。
【請求項５】
二次元の入力画像をラスタ走査により１次元化し、予測符号化により符号化する画像符号化器であって、
前記入力画像をラスタ走査により順次入力される対象画素に対し、その画素値を予測する請求項１乃至４の何れか一に記載の予測器と、
前記対象画素の画素値と前記予測器が出力する出力値との差分を、当該対象画素の予測誤差として出力する予測誤差演算手段と、
前記入力画像の各画素について得られる前記予測誤差を符号化する符号化手段と、
を備えたことを特徴とする画像符号化器。
【請求項６】
前記符号化手段は、
前記対象画素の近傍の所定の領域の画素の画素値又は予測誤差に基づいてコンテキストを生成するコンテキスト生成手段と、
前記コンテキストの値に応じて符号化テーブルを選択し、前記予測誤差のエントロピー符号化を行う選択符号化手段と、
を備えていることを特徴とする請求項５記載の画像符号化器。
【請求項７】
前記コンテキスト生成手段は、
前記入力画像の既走査領域のうちの前記対象画素の近傍の所定の領域（以下「テクスチャ判定領域」という。）内のＮｔ個の画素の画素値の平均値μｔを算出する画素平均値演算手段と、
前記テクスチャ判定領域内のＮｔ個の画素のそれぞれに対し、当該画素の画素値が前記平均値μｔより大きいか否かにより２値化し、Ｎｔ次元の２値ベクトルＴをテクスチャ・コンテキストとして出力するテクスチャ・コンテキスト生成手段を備え、
前記選択符号化手段は、前記テクスチャ・コンテキストの値に応じて符号化テーブルを選択し、前記予測誤差のエントロピー符号化を行うことを特徴とする請求項６記載の画像符号化器。
【請求項８】
前記テクスチャ判定領域は、前記対象画素に隣接する４つの画素からなる領域であることを特徴とする請求項７記載の画像符号化器。
【請求項９】
前記コンテキスト生成手段は、
前記前記水平勾配演算手段、前記垂直勾配演算手段、前記正対角勾配演算手段、及び前記負対角勾配演算手段が算出する前記対象画素の４つの勾配の平均値μＤを算出する勾配平均値演算手段と、
前記４つの勾配のそれぞれに対し、当該勾配が前記平均値μＤより大きいか否かにより２値化し、４次元の２値ベクトルＧを勾配コンテキストとして出力する勾配コンテキスト生成手段を備え、
前記選択符号化手段は、前記勾配コンテキストの値に応じて符号化テーブルを選択し、前記予測誤差のエントロピー符号化を行うことを特徴とする請求項６記載の画像符号化器。
【請求項１０】
前記コンテキスト生成手段は、
前記入力画像の既走査領域のうちの前記対象画素の近傍の所定の領域（以下「誤差判定領域」という。）内の画素の予測誤差の平均値μＥを算出する誤差平均値演算手段と、
前記平均値μＥを量子化し、ＮＥ次元の２値ベクトルＱＥを誤差エネルギー・コンテキストとして出力する誤差エネルギー・コンテキスト生成手段を備え、
前記選択符号化手段は、前記誤差エネルギー・コンテキストの値に応じて符号化テーブルを選択し、前記予測誤差のエントロピー符号化を行うことを特徴とする請求項６記載の画像符号化器。
【請求項１１】
前記誤差判定領域は、前記対象画素に隣接する４つの画素からなる領域であることを特徴とする請求項１０記載の画像符号化器。
【請求項１２】
前記コンテキスト生成手段は、
請求項７又は８に記載のテクスチャ・コンテキスト生成手段と、
請求項９に記載の勾配コンテキスト生成手段と、
請求項１０又は１１に記載の誤差エネルギー・コンテキスト生成手段と、
を備え、
前記選択符号化手段は、前記テクスチャ・コンテキスト，前記勾配コンテキスト，及び前記誤差エネルギー・コンテキストの直積ベクトルの値に応じて符号化テーブルを選択し、前記予測誤差のエントロピー符号化を行うことを特徴とする請求項６記載の画像符号化器。
【請求項１３】
コンピュータに読み込ませて実行させることにより、コンピュータを請求項１乃至４の何れか一に記載の予測器として機能させることを特徴とするプログラム。
【請求項１４】
コンピュータに読み込ませて実行させることにより、コンピュータを請求項５乃至１２の何れか一に記載の画像符号化器として機能させることを特徴とするプログラム。
【請求項１５】
二次元の入力画像のラスタ走査により順次入力される対象画素に対し、その画素値を予測する画素値予測方法であって、
前記入力画像の既走査領域のうちの前記対象画素の近傍の所定の領域を参照領域（causal area）とし、
当該参照領域の各画素に対して、水平方向に相隣接する画素対について画素値の絶対値差の所定の加重和又は加重平均を演算し、その演算値又はそれに定数を加えた値を水平勾配Ｄ１とする水平勾配演算ステップと、
当該参照領域の各画素に対して、垂直方向に相隣接する画素対について画素値の絶対値差の所定の加重和又は加重平均を演算し、その演算値又はそれに定数を加えた値を垂直勾配Ｄ２とする垂直勾配演算ステップと、
当該参照領域の各画素に対して、４５°対角方向に相隣接する画素対について画素値の絶対値差の所定の加重和又は加重平均を演算し、その演算値又はそれに定数を加えた値を正対角勾配Ｄ３とする正対角勾配演算ステップと、
当該参照領域の各画素に対して、−４５°対角方向に相隣接する画素対について画素値の絶対値差の所定の加重和又は加重平均を演算し、その演算値又はそれに定数を加えた値を負対角勾配Ｄ４とする負対角勾配演算ステップと、
前記対象画素に対し、水平方向，垂直方向，４５°対角方向，及び−４５°対角方向の各方向に隣接する既走査領域内の４つの画素のうち少なくとも２つの画素の画素値の加重平均を演算し、当該加重平均を対象画素の画素値の予測値として出力する予測値演算ステップと、
を備え、
前記予測値演算ステップにおいては、前記加重平均において、各画素の画素値の重みを、その画素の隣接方向の勾配の逆数に比例させることを特徴とする画素値予測方法。
【請求項１６】
二次元の入力画像をラスタ走査により１次元化し、予測符号化により符号化する画像符号化方法であって、
前記入力画像をラスタ走査により順次入力される対象画素に対し、その画素値を請求項１５に記載の画素値予測方法により予測して予測画素値を算出する画素値予測ステップと、
前記対象画素の画素値と前記予測画素値との差分を、当該対象画素の予測誤差として出力する予測誤差演算ステップと、
前記入力画像の各画素について得られる前記予測誤差を符号化する符号化ステップと、
を備えたことを特徴とする画像符号化方法。
【請求項１７】
前記符号化ステップにおいては、
前記対象画素の近傍の所定の領域の画素の画素値又は予測誤差に基づいてコンテキストを生成するコンテキスト生成ステップと、
前記コンテキストの値に応じて符号化テーブルを選択し、前記予測誤差のエントロピー符号化を行う選択符号化ステップと、
を備えていることを特徴とする請求項１６記載の画像符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、可逆画像符号化の技術に関し、特に、二次元画像を予測符号化により符号化する画像符号化技術に関する。
【背景技術】
【０００２】
従来、二次元画像を符号化する画像符号化技術としては、低複雑度可逆画像圧縮法（low complexity lossless compression for images ：以下「LOCO-I」という。非特許文献１，７参照）や、コンテキスト・ベース適応型非可逆符号化器（context-based, adaptive, lossless image coder ：以下「CALIC」という。非特許文献２参照）などが開発されている。LOCO-Iは、ＪＰＥＧ−ＬＳ規格の基礎とされた技術であり、現在のところ、圧縮性能と計算量との間で最もよく釣り合いのとれた画像符号化方法である（非特許文献３参照）。一方、ＣＡＬＩＣは、ここ数年において圧縮比に関するベンチマークとして使用されてきた画像符号化方法であり、計算量も比較的少ない方法である。画像符号化の分野において、これらの方法は、技術進歩を測る上での工程目標（Milestone）として広く受け入れられている。
【０００３】
以下、LOCO-Iの予測器として用いられているMED（median edge detector）とＣＡＬＩＣの予測器として用いられているGAP（gradient adjusted predictor）について説明する。
【０００４】
ＭＥＤとＧＡＰは、画像をラスタ走査しながら現在の画素の画素値の予測を行う。画素値の予測においては、次の３つの仮定を基礎としている。
（１）予測する画素は局所的なエッジに沿って存在する。
（２）実際の予測値は、局所的なエッジの強度によって調整される。
（３）局所的なエッジの向きと強度は、簡単な局所的な勾配情報に関する走査済みの画素の情報を取り入れることによって検出される。
【０００５】
ＬＯＣＯ−ＩにおけるＭＥＤでは、座標（x，y）の対象画素p(x, y)に対して、走査済みの最隣接画素p(x-1，y)，p(x，y-1)，p(x-1，y-1)からなる参照テンプレート（causal template）に基づいて、垂直方向又は水平方向のエッジ検出を行い、対象画素p(x, y)の画素値P(x, y)の予測が行われる。具体的には、予測値P^(x, y)は次式に基づいて計算される。
【０００６】
【数１】
2007259306.tif 000003
【０００７】
ここで、Ｗ，Ｎ，ＮＷは、それぞれ、画素p(x-1，y)，p(x，y-1)，p(x-1，y-1)の画素値を表す（図１参照）。
【０００８】
一方、ＣＡＬＩＣの予測フェーズで使用されるＧＡＰにおいては、先に走査された画素の勾配情報を取り入れて予測が行われる。ＧＡＰにおいて、現在のピクセルにおける画素強度関数の水平方向及び垂直方向の勾配の大きさdh，dvは、次式に基づいて計算される。
【０００９】
【数２】
2007259306.tif 000004
【００１０】
ここで、Ｗ，Ｎ，ＮＷ，ＮＥ，ＷＷ，ＮＮ，ＮＮＥは、それぞれ、画素p(x-1，y)，p(x，y-1)，p(x-1，y-1)，p(x+1，y-1)，p(x-2，y)，p(x，y-2)，p(x+1，y-2)の画素値を表す。
【００１１】
そして、これらの勾配の大きさdh，dvの差分に基づいて、７つの予測方法の何れかを選択し、対象画素p(x, y)の画素値xの予測が行われる。具体的には、この手順は次のようなアルゴリズムにより実行される。
【００１２】
【数３】
2007259306.tif 000005
【００１３】
ここで、閾値dth1, dth2, dth3, dth4, dth5は実験的に求められる値である。これらの係数を選ぶにあたっては、計算の容易さを考慮する必要もある。画素値が０〜２５５の値をとるとすれば、一般に各閾値はdth1=80, dth2=32, dth3=8, dth4=32, dth5=8 が用いられている。
【非特許文献１】M. J.Weinberger, G. Seroussi, and G. Sapiro, "The LOCO-I lossless image compression algorithm: Principles and standardization into JPEG-LS," IEEE Trans. Image Process., vol. 9, pp. 1309-1324, Aug. 2000.
【非特許文献２】X. Wu and N. D. Memon, "Context-based, adaptive, lossless image coding," IEEE Trans. Commun., vol. 45, pp. 437-444, Apr. 1997.
【非特許文献３】B. Carpentieri, M. J. Weinberger and G. Seroussi, "Lossless compression of continuous-tone image", Proceedings of the IEEE, vol.88, No. 11, November 2000.
【非特許文献４】B. Carpentieri, M. J. Weinberger and G. Seroussi, "Lossless compression of continuous-tone image", Proceedings of the IEEE, vol.88, No. 11, November 2000.
【非特許文献５】X. Wu, "Efficient lossless compression of continuous-tone images via context selection and quantization," IEEE Trans. Image Process., vol. 6, pp. 656-664, May 1997.
【非特許文献６】S.P. Lloyd, "Least squares quantization in PCM," IEEE Trans. Inform. Theory, IT-28, pp. 127-135, March 1982.
【非特許文献７】N. Memon and X. Wu, "Recent developments in context-based predictive techniques for lossless image compression," Comput. J., vol. 40, no. 2/3, pp. 127--136, 1997.
【非特許文献８】Ian H. Witten and Radford Neal, "Calgary arithmetic coding", [online], 2005年11月28日, Ian H. Witten, Rasford M. Neal, and Jhon G. Cleary, [平成18年3月15日検索], インターネット＜URL : ftp://ftp.cpsc.ucalgary.ca/pub/projects/arithmetic.coding＞
【非特許文献９】Witten, I.H., Neal, R. and Cleary, J.G., "Arithmetic coding for data compression," Communication of the ACM, 30(6), pp.520-540, June 1987.
【発明の開示】
【発明が解決しようとする課題】
【００１４】
まず、上述したＭＥＤの予測値を算出する式（１）について考察する。式（１）の右辺の最初の２段は、３つの隣接画素の最小値又は最大値がＮＷである場合には、対象画素はエッジ上に存在することが想定されていると考えることができる。想定されるエッジが水平であるか垂直であるかは、Ｗ，Ｎのうちどちらが最大であるかにより判定される。条件ＮＷ≧max(Ｎ，Ｗ)が満たされている場合、max(Ｎ，Ｗ)=Ｗの場合は垂直エッジ、max(Ｎ，Ｗ)=Ｎの場合は水平エッジが想定されると考える。同様に、条件ＮＷ≦min(Ｎ，Ｗ)が満たされている場合、min(Ｎ，Ｗ)=Ｗの場合は垂直エッジ、min(Ｎ，Ｗ)=Ｎの場合は水平エッジが想定されると考える。そして、想定されるエッジが水平の場合には対象画素p(x, y)の予測値P(x, y)^としてＷが用いられ、想定されるエッジが水平の場合にはＮが用いられる。
【００１５】
式（１）の右辺の３段目はそれ以外の場合、すなわち、条件min(Ｎ，Ｗ)≦ＮＷ≦max(Ｎ，Ｗ)の場合である。ＭＥＤにおいては、この場合は、エッジがあるか否かの判定はできない。仮に、エッジが存在したとしても、その方向を適切に判定するのは困難である。そこで、ＭＥＤでは、この場合、式（１）の右辺３段目に示したように、予測値としてＮ＋Ｗ−ＮＷを選択している。実際、この予測値Ｎ＋Ｗ−ＮＷは、あらゆる条件に対して極めてバランスのよい予測値となっている。
【００１６】
見方を変えると、ＭＥＤは、Ｎ，Ｗ，Ｎ＋Ｗ＋ＮＷのうち最良のもの又は２番目に最良のものを常に選択しているといえる。最初の２つは対象画素p(x, y)の隣接画素である。また、Ｎ＋Ｗ＋ＮＷは、画像の水平軸、垂直軸、及び画素値の軸で規定された三次元空間において、４つの画素（参照テンプレート及び対象画素p(x, y)）が１平面上にあると仮定して、空間外挿を行ったものである。
【００１７】
一方、ＣＡＬＩＣの予測器も、対象画素における水平エッジ又は垂直エッジに基づいて予測を行っていると考えることができる。
【００１８】
式（２ａ），（２ｂ）のdh及びdvは、水平方向及び垂直方向に近接する画素の強度関数の勾配を評価するスケーリング・ファクターである。dh及びdvの値は、局所エッジがある場合に予測性能を向上させるために、入力画像におけるエッジの大きさと方向を検出して、後の予測において必要な調整をするために使用される。各方向の勾配の評価には、３つの絶対値差が使用されている。
【００１９】
勾配評価において、代数的な差の計算ではなく絶対値差が使用されている理由は、異符号の値同士でキャンセルするのを防ぐためである。また、（数３）における閾値dth1, dth2, dth3, dth4, dth5は実験的に選ばれる。また、これらの閾値は、計算の容易さも重視して選択される。
【００２０】
しかしながら、LOCO-IとCALICにおいて採用された上記予測法は、予測値を計算する際に、予測テンプレートにおいて水平エッジと垂直エッジのみしか考慮されない。これは、予測の基礎となる画素が局所的な予測テンプレートに制限されている場合、近接領域の周辺の画素強度の変化が常に上記２種類のエッジにより表現できるという意味では論理的である。すなわち、多数の水平エッジと垂直エッジを組み合わせることによって、いかなる画像における任意の形状又はエッジの線を発生させることができる。しかし、ここで重要なのは、２つのエッジによる表現が、予測誤差を十分最小化するほどに正確となるか否かということである。上述した２つの予測方法においては、予測テンプレートの中に対角線エッジが存在する場合、生じる誤差が不必要に大きくなることが予想される。
【００２１】
そこで、本発明の目的は、予測テンプレートの中に任意方向のエッジが存在する場合においてもエッジ方向に適応した予測を行うことにより、従来よりも高精度で画素値の予測を行うことが可能な予測器、及びそれを用いた画像符号化器を提供することにある。
【課題を解決するための手段】
【００２２】
ここでは、まず、本発明の考え方の基礎となる高精度勾配選択予測器（accurate gradient selection predictor：以下「ＡＧＳＰ」という。）とそれを用いた画像符号化器について説明し、その後、本発明の構成及び作用について説明する。
【００２３】
〔１〕本発明の基本的な考え方
〔１−１〕高精度勾配選択予測器（ＡＧＳＰ）
上記従来の予測器における方法では、予測対象の画素毎に、固定の線形予測量が選択される。このとき、垂直方向の勾配と水平方向の勾配との差分を粗く量子化して、局所的なテクスチャを分類し、その分類に従って線形予測量が選択される。
【００２４】
しかしながら、この方法ではすべての種類の局所的なテクスチャの性質に対して予測器を十分に適応させることはできない。
【００２５】
そこで、本発明の予測器においては、より高精度で動的に局所的なテクスチャに予測器を適応させるようにすることを考える。そのために、垂直方向と水平方向の画素値関数の勾配に加えて、本発明ではそれ以外の任意の方向の画素値関数の勾配も評価して予測を行えるようにする。
【００２６】
さらに、勾配の評価においては、対象画素（current pixel）と各参照画素（causal pixel）との距離も考慮する。例えば、画素対{p(x+1,y-1), p(x+1,y-2)}は画素対{p(x,y-1), p(x,y-2)}よりも対象画素p(x,y)から離れているので、|NN-N|は|NE-NNE|よりも勾配に対しての寄与度は大きい。また、画素対が対象画素から著しく離れている場合には、その画素対は予測に対してはノイズ的な効果をもたらすに過ぎないと考えられる。
【００２７】
以上のような仮定のもとで、ここでは、新たに提案する高精度勾配選択予測器（ＡＧＳＰ）を提案する。ＡＧＳＰは、従来の垂直エッジか水平エッジかの選択に替えて、局所的なテクスチャの優位な方向の検出を行う。以下、ＡＧＳＰにおける予測方法について説明する。
【００２８】
まず、ＡＧＳＰにおいては、局所的なテクスチャの情報を精度よく得るために、図２に示すように、対象画素p(x,y)の周りの４方向（垂直方向，水平方向，４５°対角方向，−４５°対角方向）で勾配の計算を行う。さらに、勾配の評価がノイズに対してロバストとなるように、図１に示した対象画素p(x,y)の周辺の走査済みの９つの画素を参照テンプレート（causal template）として用いる。また、対象画素は、高い確率で、それに隣接する優位なテクスチャに従うであろうという仮定をする。
【００２９】
この仮定に従うと、対象画素の予測においては、勾配の大きさがより小さい方向の隣接画素ほど、より大きな寄与をもたらすといえる。各方向の勾配の評価は、各参照画素間の絶対値差を対象画素方向に補外することによって計算することができる。また、対象画素から大きく離れた画素対については考慮しないこととする。以上の事項を考慮して、垂直方向，水平方向，４５°対角方向，−４５°対角方向の各方向に対する勾配d1, d2, d3, d4を、次式により評価する。
【００３０】
【数４】
2007259306.tif 000006
【００３１】
一方、上述したとおり、勾配に対する各画素対の絶対値差の寄与率は、対象画素からの距離によって異なるべきである。そこで、一つの方向の勾配は、この方向に沿った各画素対の絶対値差の加重和として計算する。各画素対の重み係数は、計算量を考慮して、当該画素対の画素のうち対象画素から最も近い画素までのマンハッタン距離の逆数で定義する。
【００３２】
例えば、画素対{p(x-2, y-1), p(x-1, y-1)}と考える。p(x-2, y-1)から対象画素p(x, y)までのマンハッタン距離は３であり、p(x-1, y-1)から対象画素p(x, y)までのマンハッタン距離は２である。従って、対象画素から最も近い画素はp(x-1, y-1)であり、絶対値差|NWW-NW|の重み係数は１／２となる。
【００３３】
ＡＧＳＰにおいては、図１に示した参照テンプレート内の画素対のみが勾配に寄与すると考える。従って、取り得る重み係数の値は、１又は１／２である。従って、簡単な規格化を行うことによって、勾配d1', d2', d3', d4'として次式が得られる。
【００３４】
【数５】
2007259306.tif 000007
【００３５】
４つの勾配を比較する必要があるため、上記式（４ａ）〜（４ｄ）の４つの加重和を１に規格化する。さらに、どのような勾配であっても０として評価される事態を避けるため（後述の式（７）に特異点が生じることを防止するため）、勾配の各項に１を加える。最終的に、対象画素の近傍における画素値関数の勾配の評価は次式で定義される勾配D1, D2, D3, D4を用いて行う。
【００３６】
【数６】
2007259306.tif 000008
【００３７】
勾配D1の方向は水平方向、勾配D2の方向は垂直方向、勾配D3の方向は４５°対角方向、勾配D4の方向は−４５°対角方向である。
【００３８】
ＡＧＳＰでは、参照テンプレート内の各画素値を用いて計算されるこれらの勾配D1, D2, D3, D4を比較して、対象画素p(x, y)に隣接する４つの際隣接画素p(x-1, y), p(x, y-1), p(x+1, y-1), p(x-1, y-1)の寄与率の大きさを決定し、対象画素p(x, y)の画素値P(x, y)の予測を行う。このとき、勾配の大きさが小さい方向の最隣接画素ほど寄与率が大きくなるようにする。
【００３９】
尚、勾配D1, D2, D3, D4の方向の対象画素p(x, y)の最隣接画素は、それぞれ、p(x-1, y), p(x, y-1), p(x+1, y-1), p(x-1, y-1)である。
【００４０】
本発明者は、各種の入力画像を用いて計算機実験を行った結果、勾配が最小の方向と２番目に小さい方向の２つの最隣接画素を用いて対象画素の画素値予測を行った場合に最もよい結果が得られることが判った。
【００４１】
そこで、ＡＧＳＰにおいては、上記勾配D1, D2, D3, D4のうち、最小のものと２番目に小さいものを選択し、これを勾配Dmin, Dmin2とする。
【００４２】
【数７】
2007259306.tif 000009
【００４３】
また、勾配Dmin, Dmin2の方向の最隣接画素の画素値を、それぞれCmin, Cmin2とする。例えば、もしDmin=D1, Dmin2=D2ならばCmin=W, Cmin2=Nである。
【００４４】
対象画素p(x, y)の画素値の予測は、これら２つの最隣接画素Cmin, Cmin2を用いて行う。対象画素p(x, y)の予測画素値P^(x, y)は、次式のようにCmin, Cmin2の加重平均を用いて計算する。
【００４５】
【数８】
2007259306.tif 000010
【００４６】
ここで、勾配の大きさが小さい方向の最隣接画素ほど寄与率が大きくなるようにするため、Cmin, Cmin2の重み係数は、それぞれ、Dmin2/(Dmin+Dmin2), Dmin/(Dmin+Dmin2)とした。例えば、もしDmin=D2, Dmin2=D4ならばP^(x, y)=(D2NW+D4N)/(D2+D4)となる。
【００４７】
最後に、ＡＧＳＰの計算量を評価するため、ＧＡＰとの比較を行う。まず、両予測器とも、勾配の評価、勾配の比較、及び予測値の決定という３つのステップから構成される。最初のステップは、式（５）と式（２）を比較すると、ＡＧＳＰはＧＡＰに比べて４倍程度の解散を必要とすることが分かる。第２番目のステップでは、ＡＧＳＰはＧＡＰとほぼ等しい計算量を要する。最後のステップにおいても、２つの予測器はほぼ等しい計算量を要する。従って、ＡＧＳＰの計算量は、勾配評価の計算のみ計算量を必要とする点を除いて、ＧＡＰとほぼ等しい。
【００４８】
〔１−２〕画像符号化器
次に、上記ＡＧＳＰを用いて構成される画像符号化器について説明する。本発明の画像符号化器は、入力画像の画素をラスタ走査しながら、各対象画素p(x, y)について上記ＡＧＳＰにより画素値予測を行い、予測値P^(x, y)と実際の画素値P(x, y)との予測誤差e(x, y)を計算する。そして、予測誤差e(x, y)をエントロピー符号化により符号化することによって、入力画像を符号化する。このエントロピー符号化においては、コンテキスト・モデルによる対象画素の分類を行い、分類ごとに異なるハフマン・テーブルを用いてエントロピー符号化を行うことにより、符号化効率を向上させる。ここで、「コンテキスト（context）」とは、画素パターンの類似性を示す指標をいう。
【００４９】
予測器において、画像の冗長性が完全に除去されれば、予測誤差は対象画素周辺のコンテキストの種類によらず常にランダムである。しかしながら、一般に、特定の予測器は絶えず同じコンテキストにおいて同じ予測誤差を繰り返すことが知られている。これは、予測段階において、画像の冗長性を完全に除去することはできないことを意味している（特許文献４参照）。
【００５０】
例えば、入力画像全体の予測誤差の度数分布をとった場合、図３（ａ）のような度数分布が得られたとする。画像の冗長性が完全に除去されていれば、入力画像のどの部分領域の予測誤差の度数分布をとっても図３（ａ）と同様の分布が得られるはずである。しかしながら、実際には、予測後にも画像の冗長性は残るため、画像内において画素値関数の勾配が緩やかな領域（以下「平坦領域」という。）では、予測誤差の度数分布は図３（ｂ）のように０付近に集中し、画像内のエッジ領域の部分の度数分布は図３（ｃ）のように０付近で極小となり正負のある値付近にピークを有するような分布となる。
【００５１】
もし、予測誤差をコンテキストに高い精度で適合させることができれば、圧縮利得をさらに向上させることが可能となる。
【００５２】
上述のような画素値関数の勾配やエッジの方向、又はテクスチャなどのような多くの画像の特徴は、予測誤差の分布をモデル化するための情報として非常に有用である（非特許文献５参照）。そこで、本発明においては、テクスチャ，勾配，及び誤差エネルギーの３タイプのコンテキストの組み合わせを用いて、各画素の周辺のコンテキスト・モデルを構成する。
【００５３】
（１）テクスチャ・コンテキスト
対象画素p(x, y)のテクスチャ・コンテキストを次式（８）のように定義する。
【００５４】
【数９】
2007259306.tif 000011
【００５５】
ここで、表記の都合上、C1=W, C2=N, C3=NW, C4=NEとおく。次に、C(x,y)のすべてのピクセルの平均値μtを計算する。
【００５６】
【数１０】
2007259306.tif 000012
【００５７】
このμtを参照値として、次式によりテクスチャ・コンテキストT(x,y)を計算する。
【００５８】
【数１１】
2007259306.tif 000013
【００５９】
ここで、T(x,y)は４ビットのバイナリ・ベクトルである。T(x,y)の各要素Tiは、平均値μtを基準として、各隣接画素Ciの画素値が平均値μtより大きいか否かで類別した分類情報となっている。このテクスチャ・コンテキストT(x,y)をコンテキストC(x,y)の類別に用いることとする。
【００６０】
（２）勾配コンテキスト
同様に、勾配コンテキストG(x, y)を、次式（１２）により定義する。
【００６１】
【数１２】
2007259306.tif 000014
【００６２】
ここで、各Diは上記式（５ａ）〜（５ｄ）により定義され、μdは次式（１４）により定義されるDiの平均値である。
【００６３】
【数１３】
2007259306.tif 000015
【００６４】
（３）誤差エネルギー・コンテキスト
誤差エネルギーは次式（１５）により定義される。
【００６５】
【数１４】
2007259306.tif 000016
【００６６】
この誤差エネルギーμEはLloyd-Maxスカラー量子化器（非特許文献６参照）により４値に量子化され、量子化された誤差エネルギーを２進表記することにより２次元の２値ベクトルを得る。量子化器の各閾値レベルは、トレーニング画像の組を用いて学習され、最適な値に設定される。そして、一旦設定した後は、常に同じ状態が維持される。量子化された誤差エネルギーμEを２値ベクトルで表したものを誤差エネルギー・コンテキストといい、QE(x, y)（∈{00,01,10,11}）と記す。
【００６７】
（４）コンテキスト・モデル
以上のような３種類のコンテキストを用いて、対象画素の予測誤差を効果的に分類する。コンテキストI(x,y)を次式（１６）により定義する：
【００６８】
【数１５】
2007259306.tif 000017
【００６９】
この場合、I(x,y)は０から１０２３の間の整数値を採り得ることになるが、実際は、G(x,y)とT(x,y)は０と１５の値は取り得ないため、全部で７８４通りの可能なI(x,y)の値が存在する。このI(x,y)の値は、予測誤差の分類のインデックスとして使用される。即ち、７８４通りのコンテキストが存在する。
【００７０】
画像符号化器は、コンテキストI(x,y)の値に基づいて、最適なハフマン・テーブルを選択する。そして、そのハフマン・テーブルを用いて、予測誤差e(x, y)を符号化する。符号化は、適応M-ary算術符号化器（adaptive M-Ary arithmetic coder）により行うことができる（非特許文献８，９参照）。
【００７１】
〔２〕本発明の構成
本発明の予測器の第１の構成は、二次元の入力画像のラスタ走査により順次入力される対象画素に対し、その画素値を予測する予測器であって、
前記入力画像の既走査領域のうちの前記対象画素の近傍の所定の領域を参照領域（causal area）とすると、少なくとも前記参照領域内の画素の画素値を保持する参照領域記憶手段と、
当該参照領域の各画素に対して、水平方向に相隣接する画素対について画素値の絶対値差の所定の加重和又は加重平均を演算し、その演算値又はそれに定数を加えた値を水平勾配Ｄ１として出力する水平勾配演算手段と、
当該参照領域の各画素に対して、垂直方向に相隣接する画素対について画素値の絶対値差の所定の加重和又は加重平均を演算し、その演算値又はそれに定数を加えた値を垂直勾配Ｄ２として出力する垂直勾配演算手段と、
当該参照領域の各画素に対して、４５°対角方向に相隣接する画素対について画素値の絶対値差の所定の加重和又は加重平均を演算し、その演算値又はそれに定数を加えた値を正対角勾配Ｄ３として出力する正対角勾配演算手段と、
当該参照領域の各画素に対して、−４５°対角方向に相隣接する画素対について画素値の絶対値差の所定の加重和又は加重平均を演算し、その演算値又はそれに定数を加えた値を負対角勾配Ｄ４として出力する負対角勾配演算手段と、
前記対象画素に対し、水平方向，垂直方向，４５°対角方向，及び−４５°対角方向の各方向に隣接する既走査領域内の４つの画素のうち少なくとも２つの画素の画素値の加重平均を演算し、当該加重平均を対象画素の画素値の予測値として出力する予測値演算手段と、を備え、
前記予測値演算手段は、前記加重平均において、各画素の画素値の重みを、その画素の隣接方向の勾配の逆数に比例させることを特徴とする。
【００７２】
この構成によれば、対象画素の予測値は、水平方向，垂直方向，４５°対角方向，及び−４５°対角方向の４方向の勾配を考慮して、対象画素に隣接する既走査領域内の４つの隣接画素のうち少なくとも２つの画素の画素値の加重平均により決定される。このとき、勾配が小さい方向の隣接画素の重みは大きく、勾配が大きい方向の隣接画素の重みは小さくなる。従って、エッジの方向である可能性が大きい方向の隣接画素の画素値が予測値に大きく寄与し、エッジの方向である可能性が小さい方向の隣接画素の画素値の寄与は小さくなる。このように、対象画素の予測演算にすべての方向のエッジを考慮することが可能となるため、予測精度を向上させることが可能となる。
【００７３】
本発明の予測器の第２の構成は、前記第１の構成において、前記水平勾配Ｄ１，前記垂直勾配Ｄ２，前記正対角勾配Ｄ３，及び前記負対角勾配Ｄ４のうち、最小の勾配Ｄｍｉｎ及び２番目に小さい勾配Ｄｍｉｎ２を決定する参照方向決定手段を備え、
【００７４】
前記予測値演算手段は、前記対象画素に対し前記勾配Ｄｍｉｎに対応する方向に隣接する画素の画素値Ｃｍｉｎの重みをη／Ｄｍｉｎ２（ηは規格化定数）、前記勾配Ｄｍｉｎ２に対応する方向に隣接する画素の画素値Ｃｍｉｎ２の重みをη／Ｄｍｉｎとして、画素値Ｃｍｉｎ及び画素値Ｃｍｉｎ２の加重平均を演算し、当該加重平均を対象画素の画素値の予測値として出力することを特徴とする。
【００７５】
この構成により、水平，垂直，４５°，−４５°の４方向のうち、エッジ方向である確率の高い２方向の隣接画素（対象画素に隣接する既走査領域内の画素）を用いて、その加重平均で予測を行うため、すべての方向のエッジに対して適切に隣接画素の寄与率を設定することが可能となる。
【００７６】
ここで、ηは規格化定数であり、画素値Ｃｍｉｎの重みと画素値Ｃｍｉｎ２の重みの和が１となるように設定すればよい。従って、η＝Ｄ１Ｄ２／（Ｄ１＋Ｄ２）とすればよい。
【００７７】
本発明の予測器の第３の構成は、前記第１又は２の構成において、前記水平勾配演算手段、前記垂直勾配演算手段、前記正対角勾配演算手段、及び前記負対角勾配演算手段は、各画素対の重み係数を、当該画素対の２つの画素のうち前記対象画素に最も近い画素から前記対象画素までの距離の逆数に比例する値として、前記絶対値差の所定の加重和又は加重平均を演算することを特徴とする。
【００７８】
この構成により、画素対の絶対値差は、対象画素に近いほど大きく勾配に寄与し、対象画素に遠いほど小さく勾配に寄与する。従って、参照領域を広くとっても十分な精度で対象画素近傍の勾配を評価することができ、参照領域内のノイズに対するロバスト性を高めることができる。
【００７９】
本発明の予測器の第４の構成は、前記第１乃至３の何れか一の構成において、前記ラスタ走査の水平進行方向をｘ軸、垂直進行方向をｙ軸とし、対象画素の座標を（ｘ，ｙ）としたとき、前記参照領域は、座標が（ｘ−１，ｙ），（ｘ−２，ｙ），（ｘ＋１，ｙ−１），（ｘ，ｙ−１），（ｘ−１，ｙ−１），（ｘ−２，ｙ−１），（ｘ＋１，ｙ−２），（ｘ，ｙ−２），（ｘ−１，ｙ−１）の９つの画素で構成されていることを特徴とする。
【００８０】
この構成により、予測演算の精度と計算時間とのバランスが適度な状態となり、予測演算の精度を十分に維持しつつ、高速に予測演算を行うことが可能となる。
【００８１】
本発明の画像符号化器の第１の構成は、二次元の入力画像をラスタ走査により１次元化し、予測符号化により符号化する画像符号化器であって、
前記入力画像をラスタ走査により順次入力される対象画素に対し、その画素値を予測する前記第１乃至４の何れか一の構成の予測器と、
前記対象画素の画素値と前記予測器が出力する出力値との差分を、当該対象画素の予測誤差として出力する予測誤差演算手段と、
前記入力画像の各画素について得られる前記予測誤差を符号化する符号化手段と、
を備えたことを特徴とする。
【００８２】
この構成により、予測誤差を小さくできるため、圧縮効率の高い符号化が可能となる。
【００８３】
本発明の画像符号化器の第２の構成は、前記第１の構成において、前記符号化手段は、
前記対象画素の近傍の所定の領域の画素の画素値又は予測誤差に基づいてコンテキストを生成するコンテキスト生成手段と、
前記コンテキストの値に応じて符号化テーブルを選択し、前記予測誤差のエントロピー符号化を行う選択符号化手段と、
を備えていることを特徴とする。
【００８４】
この構成により、コンテキストの値に応じて符号化テーブルを切り替えることにより、より高い効率での圧縮が可能となる。
【００８５】
本発明の画像符号化器の第３の構成は、前記第２の構成において、前記コンテキスト生成手段は、
前記入力画像の既走査領域のうちの前記対象画素の近傍の所定の領域（以下「テクスチャ判定領域」という。）内のＮｔ個の画素の画素値の平均値μｔを算出する画素平均値演算手段と、
前記テクスチャ判定領域内のＮｔ個の画素のそれぞれに対し、当該画素の画素値が前記平均値μｔより大きいか否かにより２値化し、Ｎｔ次元の２値ベクトルＴをテクスチャ・コンテキストとして出力するテクスチャ・コンテキスト生成手段を備え、
前記選択符号化手段は、前記テクスチャ・コンテキストの値に応じて符号化テーブルを選択し、前記予測誤差のエントロピー符号化を行うことを特徴とする。
【００８６】
この構成により、対象画素の周辺の画素値の変化パターンに基づいて符号化テーブルが切り替えられ、より高い効率での圧縮が可能となる。
【００８７】
本発明の画像符号化器の第４の構成は、前記第３の構成において、前記テクスチャ判定領域は、前記対象画素に隣接する４つの画素からなる領域であることを特徴とする。
【００８８】
本発明の画像符号化器の第５の構成は、前記第２の構成において、前記コンテキスト生成手段は、
前記前記水平勾配演算手段、前記垂直勾配演算手段、前記正対角勾配演算手段、及び前記負対角勾配演算手段が算出する前記対象画素の４つの勾配の平均値μＤを算出する勾配平均値演算手段と、
前記４つの勾配のそれぞれに対し、当該勾配が前記平均値μＤより大きいか否かにより２値化し、４次元の２値ベクトルＧを勾配コンテキストとして出力する勾配コンテキスト生成手段を備え、
前記選択符号化手段は、前記勾配コンテキストの値に応じて符号化テーブルを選択し、前記予測誤差のエントロピー符号化を行うことを特徴とする。
【００８９】
この構成により、対象画素の周辺の勾配のパターンに基づいて符号化テーブルが切り替えられ、より高い効率での圧縮が可能となる。
【００９０】
本発明の画像符号化器の第６の構成は、前記第２の構成において、前記コンテキスト生成手段は、
前記入力画像の既走査領域のうちの前記対象画素の近傍の所定の領域（以下「誤差判定領域」という。）内の画素の予測誤差の平均値μＥを算出する誤差平均値演算手段と、
前記平均値μＥを量子化し、ＮＥ次元の２値ベクトルＱＥを誤差エネルギー・コンテキストとして出力する誤差エネルギー・コンテキスト生成手段を備え、
前記選択符号化手段は、前記誤差エネルギー・コンテキストの値に応じて符号化テーブルを選択し、前記予測誤差のエントロピー符号化を行うことを特徴とする。
【００９１】
この構成により、対象画素の周辺の誤差エネルギーに基づいて符号化テーブルが切り替えられ、より高い効率での圧縮が可能となる。
【００９２】
本発明の画像符号化器の第７の構成は、前記第６の構成において、前記誤差判定領域は、前記対象画素に隣接する４つの画素からなる領域であることを特徴とする。
【００９３】
本発明の画像符号化器の第８の構成は、前記第２の構成において、前記コンテキスト生成手段は、
前記画像符号化器の第７又は８の構成に記載のテクスチャ・コンテキスト生成手段と、
前記画像符号化器の第９の構成に記載の勾配コンテキスト生成手段と、
前記画像符号化器の第１０又は１１の構成に記載の誤差エネルギー・コンテキスト生成手段と、
を備え、
前記選択符号化手段は、前記テクスチャ・コンテキスト，前記勾配コンテキスト，及び前記誤差エネルギー・コンテキストの直積ベクトルの値に応じて符号化テーブルを選択し、前記予測誤差のエントロピー符号化を行うことを特徴とする。
【００９４】
本発明のプログラムの第１の構成は、コンピュータに読み込ませて実行させることにより、コンピュータを前記第１乃至４の何れか一の構成の予測器として機能させることを特徴とする。
【００９５】
本発明のプログラムの第２の構成は、コンピュータに読み込ませて実行させることにより、コンピュータを前記５乃至１２の何れか一の構成の画像符号化器として機能させることを特徴とする。
【００９６】
本発明の画素値予測方法は、二次元の入力画像のラスタ走査により順次入力される対象画素に対し、その画素値を予測する画素値予測方法であって、
前記入力画像の既走査領域のうちの前記対象画素の近傍の所定の領域を参照領域（causal area）とし、
当該参照領域の各画素に対して、水平方向に相隣接する画素対について画素値の絶対値差の所定の加重和又は加重平均を演算し、その演算値又はそれに定数を加えた値を水平勾配Ｄ１とする水平勾配演算ステップと、
当該参照領域の各画素に対して、垂直方向に相隣接する画素対について画素値の絶対値差の所定の加重和又は加重平均を演算し、その演算値又はそれに定数を加えた値を垂直勾配Ｄ２とする垂直勾配演算ステップと、
当該参照領域の各画素に対して、４５°対角方向に相隣接する画素対について画素値の絶対値差の所定の加重和又は加重平均を演算し、その演算値又はそれに定数を加えた値を正対角勾配Ｄ３とする正対角勾配演算ステップと、
当該参照領域の各画素に対して、−４５°対角方向に相隣接する画素対について画素値の絶対値差の所定の加重和又は加重平均を演算し、その演算値又はそれに定数を加えた値を負対角勾配Ｄ４とする負対角勾配演算ステップと、
前記対象画素に対し、水平方向，垂直方向，４５°対角方向，及び−４５°対角方向の各方向に隣接する既走査領域内の４つの画素のうち少なくとも２つの画素の画素値の加重平均を演算し、当該加重平均を対象画素の画素値の予測値として出力する予測値演算ステップと、
を備え、
前記予測値演算ステップにおいては、前記加重平均において、各画素の画素値の重みを、その画素の隣接方向の勾配の逆数に比例させることを特徴とする。
【００９７】
本発明の画像符号化方法の第１の構成は、二次元の入力画像をラスタ走査により１次元化し、予測符号化により符号化する画像符号化方法であって、
前記入力画像をラスタ走査により順次入力される対象画素に対し、その画素値を前記画素値予測方法により予測して予測画素値を算出する画素値予測ステップと、
前記対象画素の画素値と前記予測画素値との差分を、当該対象画素の予測誤差として出力する予測誤差演算ステップと、
前記入力画像の各画素について得られる前記予測誤差を符号化する符号化ステップと、
を備えたことを特徴とする。
【００９８】
本発明の画像符号化方法の第２の構成は、前記第１の構成において、前記符号化ステップにおいては、
前記対象画素の近傍の所定の領域の画素の画素値又は予測誤差に基づいてコンテキストを生成するコンテキスト生成ステップと、
前記コンテキストの値に応じて符号化テーブルを選択し、前記予測誤差のエントロピー符号化を行う選択符号化ステップと、
を備えていることを特徴とする。
【発明の効果】
【００９９】
以上のように、本発明の予測器によれば、対象画素の予測演算にすべての方向のエッジを考慮することが可能となるため、予測精度を向上させることが可能となる。
【０１００】
また、本発明に係る画像符号化器によれば、対象画素を既走査領域の画素値情報から高精度で予測できるため、予測誤差が小さく、高効率で画像圧縮をすることが可能となる。
【発明を実施するための最良の形態】
【０１０１】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【０１０２】
〔１〕装置構成
図４は、本発明の実施例１に係る画像符号化器１の構成を表すブロック図である。画像メモリ１０には、二次元の入力画像が記憶されている。走査手段１１は、画像メモリ１０に記憶された入力画像を、ラスタ走査しながら対象画素の画素値を画像符号化器１に出力する。画像符号化器１は、走査手段１１から順次出力する画像データを符号化し、符号化画像記憶手段１２に格納する。
【０１０３】
画像符号化器１は、予測器２，コンテキスト生成手段３，選択符号化手段４，量子化テーブル記憶手段５，符号化テーブル記憶手段６，及び予測誤差記憶手段７を備えている。予測器２は、走査手段１１が出力する対象画素の予測値の演算を行う。コンテキスト生成手段３は、対象画素の画素値と予測値との間の予測誤差を分類するためのコンテキストを生成する。選択符号化手段４は、対象画素の予測誤差の演算を行うとともに、当該予測誤差の符号化を行う。
【０１０４】
量子化テーブル記憶手段５には、コンテキスト生成手段３において、予測誤差の量子化を行う際のLloyd-Max量子化器の量子化テーブルが記憶されている。また、符号化テーブル記憶手段６には、選択符号化手段４において符号化を行う際の符号化テーブルが、それぞれのコンテキストに対応する数だけ記憶されている。予測誤差記憶手段７は、選択符号化手段４において算出される予測誤差を、コンテキストの生成に使用するために一時的に記憶する。
【０１０５】
尚、本実施例の画像符号化器１は、ＡＣＩＣチップとしてＬＩＳにより構成し、又はＰＬＡ（プログラマブル・ロジック・アレイ）を用いて構成するなど、ハードウェア的に実現してもよいが、プログラム・モジュールとしてソフトウェア的に構成し、当該プログラム・モジュールをコンピュータで実行することによってコンピュータを画像符号化器１として機能させるようしてもよい。
【０１０６】
〔２〕予測・符号化処理手順
以上のように構成された本実施例１に係る画像符号化器１について、以下その動作を説明する。
【０１０７】
まず、画像メモリ１０に記憶された入力画像は、走査手段１１によりラスタ走査され、１画素ずつ対象画素として出力される。また、現在走査を行っている走査線の走査済みの画素と、その走査線の前に既に走査された所定本数の走査線の画素とが、参照領域記憶手段２５に逐次記憶される。
【０１０８】
尚、以下の説明のため、走査手段１１が入力画像を走査する際の水平走査進行方向をｘ軸方向とし、垂直走査進行方向をｙ軸とする。また、対象画素の座業を（ｘ，ｙ）と記す。
【０１０９】
図５は、実施例１の画像符号化器１による画像符号化処理の流れを表すフローチャートである。
【０１１０】
まず、ステップＳ１において、走査手段１１から画像符号化器１に対象画素p(x,y)の画素値P(x,y)が入力される。
【０１１１】
ステップＳ２において、画素値P(x,y)は、参照領域記憶手段２５に一時的に保存される。参照領域記憶手段２５は、シフト・メモリ等により構成されており、対象画素p(x、y)が位置する走査線からM（≧2）本前の走査線までの画素値を一時的に記憶する。Mは、参照領域の大きさにより適宜決まる。例えば、参照領域が図１に示したような領域の場合、M=2である。
【０１１２】
ステップＳ３において、予測器２の水平勾配演算手段２１，垂直勾配演算手段２２，正対角勾配演算手段２３，及び負対角勾配演算手段２４は、参照領域記憶手段２５に記憶された参照領域内の各画素の画素値{P(xi,xj)}に基づいて、それぞれ、水平勾配D1，垂直勾配D2，45°対角勾配D3，−45°対角勾配D4を次式（１７ａ）〜（１７ｄ）により演算する。
【０１１３】
【数１６】
2007259306.tif 000018
【０１１４】
ここで、Sは参照領域に含まれる画素の座標の集合を表す。Li1，Li2，Li3，Li4は、対象画素p(x,y)から絶対値差の画素対の各画素までのシティーブロック距離の最小値を表し、式（１８ａ）〜（１８ｄ）で表される。ξ1，ξ2，ξ3，ξ4は、規格化定数であり、式（１９ａ）〜（１９ｄ）で表される。また、ε1，ε2，ε3，ε4は、最隣接画素の加重平均の計算の際の発散防止のために加えられる定数であり、通常は最小値１に設定される。
【０１１５】
【数１７】
2007259306.tif 000019
【０１１６】
【数１８】
2007259306.tif 000020
【０１１７】
式（１７ａ）〜（１７ｄ）より、対象画素に近い画素対の絶対値差ほど、勾配に対する寄与が大きくなっていることが分かる。これにより、対象画素の近傍の隣接画素間勾配の影響を大きく取り入れて対象画素における勾配の予測を精度よく行うことができると共に、加重平均により対象画素の近傍のノイズの影響が軽減され、ノイズに対するロバストとなる。
【０１１８】
参照領域の取り方については任意であるが、対象画素周辺のノイズに対するロバスト性と計算量との釣り合いを考慮して決める必要がある。例えば、参照領域が図１のような領域の場合、式（１７ａ）〜（１７ｄ）は、前述した式（５ａ）〜（５ｄ）となる。
【０１１９】
次に、ステップＳ４において、参照方向決定手段２６は、各勾配D1〜D4を比較して、予測に使用する隣接画素（既走査領域の画素のうち対象画素の最隣接する画素（図１のW,N,NW,NE）をいう。以下同じ。）の方向（以下「参照方向」という。）を決定する。予測に使用する隣接画素の数は２個，３個，４個の何れかである。
【０１２０】
予測に使用する隣接画素の数が２個の場合は、参照方向決定手段２６は、勾配D1〜D4のうち最小の勾配Dmin1及び２番目に小さい勾配Dmin2を決定し、これらの勾配に対応する方向が参照方向とされる。
【０１２１】
予測に使用する隣接画素の数が３個の場合は、参照方向決定手段２６は、勾配D1〜D4のうち最小の勾配Dmin1、２番目に小さい勾配Dmin2、及び３番目に小さい勾配Dmin3を決定し、これらの勾配に対応する方向が参照方向とされる。
【０１２２】
予測に使用する隣接画素の数が４個の場合には、すべての隣接画素が予測に使用されるので、参照方向決定手段２６は特に参照方向を決定する必要はない。
【０１２３】
ステップＳ５において、予測値演算手段２７は、隣接画素の画素値と参照方向決定手段２６により決定された参照方向及びその方向の勾配とに基づいて、次式（２０）により対象画素p(x,y)の予測値P^(x,y)を算出する。
【０１２４】
【数１９】
2007259306.tif 000021
【０１２５】
ここで、勾配Dminα（α＝１，２，３，４）に対応する参照方向の隣接画素の画素値をCminαと記す。αについての和は、それぞれ、予測に使用する隣接画素の数が２個の場合は１，２、予測に使用する隣接画素の数が３個の場合は１，２，３、予測に使用する隣接画素の数が４個の場合は１，２，３，４についてとる。ηは規格化定数であり、式（２１）により決められる。
【０１２６】
【数２０】
2007259306.tif 000022
【０１２７】
例えば、予測に使用する隣接画素の数が２個の場合、式（２０）は式（１４）となる。また、例えば、予測に使用する隣接画素の数が３個の場合、式（２０）は式（２２）となる。
【０１２８】
【数２１】
2007259306.tif 000023
【０１２９】
式（２０）より、参照方向の勾配が小さいほど、その参照方向の隣接画素の画素値が予測値に大きく寄与することが分かる。また、２方向以上の参照方向の隣接画素を参照し、各隣接画素の画素値の重みをその参照方向の勾配の逆数に比例した値として、加重平均により予測値を算出することで、対象画素p(x,y)のエッジの向きがどの方向であっても、そのエッジ方向に適応した予測値の算出が可能となる。
【０１３０】
尚、予測に使用する隣接画素の数は、２，３，４のいずれでもよいが、予測値計算の計算量を考慮して２個とすることが好ましい。
【０１３１】
次に、ステップＳ６において、コンテキスト生成手段３は、テクスチャ・コンテキストC(x,y)を式（８）と同様にして算出する。また、勾配コンテキストG(x, y)を、式（１２）と同様にして算出する。また、誤差エネルギー・コンテキストQE(x, y)を式（１５）と同様にして算出する。さらに、これら３種のコンテキストを直積により合成し（式（１５）参照）、最終的なコンテキストI(x,y)を生成する。
【０１３２】
尚、誤差エネルギー・コンテキストを計算する際には、予測誤差記憶手段７に先に記憶された参照領域の各画素の予測誤差を使用する。また、誤差エネルギー・コンテキストの演算の過程で、誤差エネルギーを量子化する際には、調子かテーブル記憶手段５に記憶された量子化テーブルが用いられる。量子化器としては、入力画像への適応性の観点から、Lloyd-Max量子化器を使用することが好ましい。
【０１３３】
生成される最終的なコンテキストは、誤差エネルギー・コンテキストQE(x, y)の次元を２とすれば、４＋４＋２＝１０次元のベクトルとなる。従って、表現可能なコンテキストの種類としては２１０＝１，０２４通りが考えられる。しかしながら、テクスチャ・コンテキストC(x,y)と勾配コンテキストG(x, y)とは、平均値に対する大小により各ビットを量子化しているため、(0,0,0,0)と(1,1,1,1)という値は取り得ない。従って、出現可能なコンテキストI(x,y)の種類は、１４×１４×４＝７８４通りとなる。これら７８４通りのコンテキストI(x,y)に一対一に対応して、７８４個の符号化テーブルが用意され、符号化テーブル記憶手段６に記憶されている。
【０１３４】
次に、ステップＳ７において、選択符号化手段４は、対象画素p(x,y)における予測誤差e(x,y)を次式（２３）で計算する。
【０１３５】
【数２２】
2007259306.tif 000024
【０１３６】
ステップＳ８において、選択符号化手段４は、算出した予測誤差e(x,y)を予測誤差記憶手段７に記憶させる。この予測誤差e(x,y)は、後の対象画素の誤差エネルギー・コンテキストの計算に使用される。
【０１３７】
ステップＳ９において、選択符号化手段４は、コンテキストI(x,y)の値に応じて符号化テーブル記憶手段６からそれに対応する符号化テーブルを算出する。そして、その符号化テーブルを用いて、予測誤差e(x,y)を符号化しする。符号化器としては、通常のエントロピ符号化器を使用することができ、符号化テーブルとしては、複数のトレーニング画像を用いて学習を行うことにより得られるハフマン・テーブルを使用することができる。
【０１３８】
次に、ステップＳ１０において、選択符号化手段４は、符号化された予測誤差を符号化画像記憶手段１２に保存する。
【０１３９】
最後に、ステップＳ１１において、すべての走査が終了していなければステップS1に戻って次の対象画素の符号化を行い、すべての走査が終了したならば、画像符号化処理を終了する。
【０１４０】
〔３〕実験結果
最後に、上記本発明の画像符号化器を用いて各種画像に対して符号化実験を行った結果及びCALICとの比較について説明する。実験に使用する本発明の画像符号化器としては、〔課題を解決するための手段〕の欄で説明したAGSPを用いた画像符号化器を使用する。また、本発明の画像符号化器の性能比較にCALICを使用する理由は、CALICは現在のところ可逆符号化方法においては最も有効な方法であるといわれているからである。
【０１４１】
テスト画像として、９個の8bitグレースケールの画像を使用した。各画像のサイズは512×512 pixelである。画像符号化の性能の比較に当たっては、符号化効率と計算量の両面から評価を行う。AGSPはCALICｔｐ比較すると若干計算量は多くなる。AGSPの勾配評価の方法のほうがより複雑だからである。
【０１４２】
図６は、MEDにより得られたテスト画像「Lenna」の予測誤差画像である。図７は、CAPにより得られたテスト画像「Lenna」の予測誤差画像である。図８は、本発明のAGSPにより得られたテスト画像「Lenna」の予測誤差画像である。図６〜８において、予測誤差の絶対値が画素強度としてグレースケールで表されている。一見して分かるように、AGSPによる予測誤差は、MEDやCAPの予測誤差に比べて全体的に小さいことが分かる。
【０１４３】
予測誤差の比較を行うため、客観的な指標として予測誤差の０次エントロピーを用いた。（表１）にその結果を示す。（表１）より、すべてのテスト画像において、本発明のAGSPによる予測誤差は、CALICにおける予測誤差よりも全体的に小さくなっていることが分かる。
【０１４４】
【表１】
2007259306.tif 000025
【０１４５】
また、CALICとAGSPとの可逆圧縮率の比較を（表２）に示す。（表２）から分かるように、すべてのテスト画像において、本発明のAGSPによる符号化のほうが、CALICによる符号化に比べて５％程度圧縮率が改善されていることが分かる。
【０１４６】
【表２】
2007259306.tif 000026
【図面の簡単な説明】
【０１４７】
【図１】参照テンプレートを示す図である。
【図２】勾配の４方向を示す図である。
【図３】予測誤差の分布を表す図である。
【図４】本発明の実施例１に係る画像符号化器の構成を表すブロック図である。
【図５】実施例１の画像符号化器１による画像符号化処理の流れを表すフローチャートである。
【図６】MEDにより得られたテスト画像「Lenna」の予測誤差画像である。
【図７】CAPにより得られたテスト画像「Lenna」の予測誤差画像である。
【図８】本発明のAGSPにより得られたテスト画像「Lenna」の予測誤差画像である。
【符号の説明】
【０１４８】
１  画像符号化器
２  予測器
３  コンテキスト生成手段
４  選択符号化手段
５  量子化テーブル記憶手段
６  符号化テーブル記憶手段
７  予測誤差記憶手段
１０  画像メモリ
１１  走査手段
１２  符号化画像記憶手段
２１  水平勾配演算手段
２２  垂直勾配演算手段
２３  正対角勾配演算手段
２４  負対角勾配演算手段
２５  参照領域記憶手段
２６  参照方向決定手段
２７  予測値演算手段
【図１】
2007259306.tif 000027
【図２】
2007259306.tif 000028
【図３】
2007259306.tif 000029
【図４】
2007259306.tif 000030
【図５】
2007259306.tif 000031
【図６】
2007259306.tif 000032
【図７】
2007259306.tif 000033
【図８】
2007259306.tif 000034