(57)【特許請求の範囲】
【請求項１】
画像を伝送・蓄積するにあたり，画像フレームを予め定められた大きさの処理領域に分割し，処理領域ごとに各画素の画素値を予測しながら符号化を行う画像符号化方法であって，
処理領域内に存在する被写体の数を被写体数として設定する被写体数設定ステップと，
処理領域内に存在する被写体ごとに，該被写体を識別する被写体識別子に対応付けて，各被写体を代表する１つの画素値を被写体画素値として設定する被写体画素値設定ステップと，
前記被写体画素値を用いて，処理領域内の各画素にどの被写体が撮影されているかを前記被写体識別子で示す被写体マップを生成する被写体マップ生成ステップと，
処理領域周辺の既に符号化済みの領域であるところの参照領域を符号化する際に使用された被写体マップを参照被写体マップとして設定する参照被写体マップ設定ステップと，
前記参照被写体マップを用いて，前記被写体マップを符号化する被写体マップ符号化ステップと，
前記被写体マップに従って各画素に前記被写体画素値の値を割り当てることで処理領域に対する予測画像を生成する予測画像生成ステップと，
前記予測画像を用いて処理領域に対する画像信号を予測符号化する画像信号符号化ステップと，
を含むことを特徴とする画像符号化方法。
【請求項２】
前記参照領域を符号化する際に使用した被写体画素値と，処理領域に対して設定した前記被写体画素値とを比較して，前記参照領域を符号化する際に使用した被写体識別子を，処理領域に対して設定した前記被写体識別子へと置換する置換行列を生成する置換行列生成ステップをさらに含み，
前記参照被写体マップ設定ステップは，前記参照領域を符号化する際に使用した被写体マップを，前記置換行列に従って変換することで，前記参照被写体マップを生成する
ことを特徴とする請求項１に記載の画像符号化方法。
【請求項３】
前記予測画像を用いて，前記画像信号符号化ステップで符号化したデータを復号することで，処理領域に対する復号画像の画像信号を生成する画像信号復号ステップをさらに含み，
前記参照被写体マップ設定ステップは，処理領域周辺の既に符号化済みの画素群に対して，各画素に対する復号画像の画素値に最も近い前記被写体画素値を持つ前記被写体識別子を割り当てることで，前記参照被写体マップを生成する
ことを特徴とする請求項１に記載の画像符号化方法。
【請求項４】
前記参照被写体マップの被写体識別子のエッジ情報に沿って，処理対象領域の分割方法を設定する領域分割設定ステップと，
前記分割方法に従って，前記被写体マップを木構造で表した木構造被写体マップへと変換する被写体マップ変換ステップとをさらに含み，
前記被写体マップ符号化ステップでは，前記参照被写体マップを用いて，前記木構造被写体マップを符号化する
ことを特徴とする請求項１，請求項２または請求項３に記載の画像符号化方法。
【請求項５】
画像の符号データを復号するに際し，画像フレームを予め定められた大きさの処理領域に分割し，処理領域ごとに各画素の画素値を予測しながら復号を行う画像復号方法であって，
処理領域内に存在する被写体の数を被写体数として設定する被写体数設定ステップと，
処理領域内に存在する被写体ごとに，該被写体を識別する被写体識別子に対応付けて，各被写体を代表する１つの画素値を被写体画素値として設定する被写体画素値設定ステップと，
処理領域周辺の既に復号済みの領域であるところの参照領域を復号する際に使用された被写体マップを参照被写体マップとして設定する参照被写体マップ設定ステップと，
前記参照被写体マップを用いて，処理領域内の各画素に撮影されている被写体を前記被写体識別子によって表した被写体マップを前記符号データから復号する被写体マップ復号ステップと，
前記被写体マップに従って各画素に前記被写体画素値の値を割り当てることで処理領域に対する予測画像を生成する予測画像生成ステップと，
前記予測画像を用いて，処理領域に対する復号画像の画像信号を前記符号データから復号する画像信号復号ステップと，
を含むことを特徴とする画像復号方法。
【請求項６】
前記参照領域を復号する際に使用した被写体画素値と，処理領域に対して設定した前記被写体画素値とを比較して，前記参照領域を復号する際に使用した被写体識別子を，処理領域に対して設定した前記被写体識別子へと置換する置換行列を生成する置換行列生成ステップをさらに含み，
前記参照被写体マップ設定ステップは，前記参照領域を復号する際に使用した被写体マップを，前記置換行列に従って変換することで，前記参照被写体マップを生成する
ことを特徴とする請求項５に記載の画像復号方法。
【請求項７】
前記参照被写体マップ設定ステップは，処理領域周辺の既に復号済みの画素群に対して，各画素に対する復号画像の画素値に最も近い前記被写体画素値を持つ前記被写体識別子を割り当てることで，前記参照被写体マップを生成する
ことを特徴とする請求項５に記載の画像復号方法。
【請求項８】
前記参照被写体マップの被写体識別子のエッジ情報に沿って，処理対象領域の分割方法を設定する領域分割設定ステップをさらに含み，
前記被写体マップ復号ステップでは，前記分割方法に従って，前記被写体マップを木構造で表した木構造被写体マップを前記符号データから復号し，前記木構造被写体マップを変換して前記被写体マップを復号する
ことを特徴とする請求項５，請求項６または請求項７に記載の画像復号方法。
【請求項９】
画像を伝送・蓄積するにあたり，画像フレームを予め定められた大きさの処理領域に分割し，処理領域ごとに各画素の画素値を予測しながら符号化を行う画像符号化装置であって，
処理領域内に存在する被写体の数を被写体数として設定する被写体数設定手段と，
処理領域内に存在する被写体ごとに，該被写体を識別する被写体識別子に対応付けて，各被写体を代表する１つの画素値を被写体画素値として設定する被写体画素値設定手段と，
前記被写体画素値を用いて，処理領域内の各画素にどの被写体が撮影されているかを前記被写体識別子で示す被写体マップを生成する被写体マップ生成手段と，
処理領域周辺の既に符号化済みの領域であるところの参照領域を符号化する際に使用された被写体マップを参照被写体マップとして設定する参照被写体マップ設定手段と，
前記参照被写体マップを用いて，前記被写体マップを符号化する被写体マップ符号化手段と，
前記被写体マップに従って各画素に前記被写体画素値の値を割り当てることで処理領域に対する予測画像を生成する予測画像生成手段と，
前記予測画像を用いて処理領域に対する画像信号を予測符号化する画像信号符号化手段と，
を含むことを特徴とする画像符号化装置。
【請求項１０】
前記参照領域を符号化する際に使用した被写体画素値と，処理領域に対して設定した前記被写体画素値とを比較して，前記参照領域を符号化する際に使用した被写体識別子を，処理領域に対して設定した前記被写体識別子へと置換する置換行列を生成する置換行列生成手段をさらに含み，
前記参照被写体マップ設定手段は，前記参照領域を符号化する際に使用した被写体マップを，前記置換行列に従って変換することで，前記参照被写体マップを生成する
ことを特徴とする請求項９に記載の画像符号化装置。
【請求項１１】
前記予測画像を用いて，前記画像信号符号化手段で符号化したデータを復号することで，処理領域に対する復号画像の画像信号を生成する画像信号復号手段をさらに含み，
前記参照被写体マップ設定手段は，処理領域周辺の既に符号化済みの画素群に対して，各画素に対する復号画像の画素値に最も近い前記被写体画素値を持つ前記被写体識別子を割り当てることで，前記参照被写体マップを生成する
ことを特徴とする請求項９に記載の画像符号化装置。
【請求項１２】
前記参照被写体マップの被写体識別子のエッジ情報に沿って，処理対象領域の分割方法を設定する領域分割設定手段と，
前記分割方法に従って，前記被写体マップを木構造で表した木構造被写体マップへと変換する被写体マップ変換手段とをさらに含み，
前記被写体マップ符号化手段では，前記参照被写体マップを用いて，前記木構造被写体マップを符号化する
ことを特徴とする請求項９，請求項１０または請求項１１に記載の画像符号化装置。
【請求項１３】
画像の符号データを復号するに際し，画像フレームを予め定められた大きさの処理領域に分割し，処理領域ごとに各画素の画素値を予測しながら復号を行う画像復号装置であって，
処理領域内に存在する被写体の数を被写体数として設定する被写体数設定手段と，
処理領域内に存在する被写体ごとに，該被写体を識別する被写体識別子に対応付けて，各被写体を代表する１つの画素値を被写体画素値として設定する被写体画素値設定手段と，
処理領域周辺の既に復号済みの領域であるところの参照領域を復号する際に使用された被写体マップを参照被写体マップとして設定する参照被写体マップ設定手段と，
前記参照被写体マップを用いて，処理領域内の各画素に撮影されている被写体を前記被写体識別子によって表した被写体マップを前記符号データから復号する被写体マップ復号手段と，
前記被写体マップに従って各画素に前記被写体画素値の値を割り当てることで処理領域に対する予測画像を生成する予測画像生成手段と，
前記予測画像を用いて，処理領域に対する復号画像の画像信号を前記符号データから復号する画像信号復号手段と，
を含むことを特徴とする画像復号装置。
【請求項１４】
前記参照領域を復号する際に使用した被写体画素値と，処理領域に対して設定した前記被写体画素値とを比較して，前記参照領域を復号する際に使用した被写体識別子を，処理領域に対して設定した前記被写体識別子へと置換する置換行列を生成する置換行列生成手段をさらに含み，
前記参照被写体マップ設定手段は，前記参照領域を復号する際に使用した被写体マップを，前記置換行列に従って変換することで，前記参照被写体マップを生成する
ことを特徴とする請求項１３に記載の画像復号装置。
【請求項１５】
前記参照被写体マップ設定手段は，処理領域周辺の既に復号済みの画素群に対して，各画素に対する復号画像の画素値に最も近い前記被写体画素値を持つ前記被写体識別子を割り当てることで，前記参照被写体マップを生成する
ことを特徴とする請求項１３に記載の画像復号装置。
【請求項１６】
前記参照被写体マップの被写体識別子のエッジ情報に沿って，処理対象領域の分割方法を設定する領域分割設定手段をさらに含み，
前記被写体マップ復号手段では，前記分割方法に従って，前記被写体マップを木構造で表した木構造被写体マップを前記符号データから復号し，前記木構造被写体マップを変換して前記被写体マップを復号する
ことを特徴とする請求項１３，請求項１４または請求項１５に記載の画像復号装置。
【請求項１７】
請求項１ないし請求項４のいずれか１項に記載の画像符号化方法をコンピュータに実行させるための画像符号化プログラム。
【請求項１８】
請求項５ないし請求項８のいずれか１項に記載の画像復号方法をコンピュータに実行させるための画像復号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，距離画像の符号化およびその復号技術に関するものである。
【背景技術】
【０００２】
距離画像とは，カメラから被写体までの距離を画素値として表現した画像のことである。カメラから被写体までの距離はシーンの奥行きとも言えるため，距離画像は奥行き画像と呼ばれることもある。また，奥行きはデプス（Ｄｅｐｔｈ）とも呼ばれるため，デプスマップ（Ｄｅｐｔｈ  Ｍａｐ）と呼ばれることもある。コンピュータグラフィックスの分野では，デプスはＺバッファに蓄積された情報となるためＺ画像やＺマップと呼ばれることもある。なお，カメラから被写体までの距離の他に，表現対象空間上に張られた三次元座標系のＺ軸に対する座標値を距離（デプス）として用いることもある。一般に撮影された画像に対して水平方向をＸ軸，垂直方向をＹ軸とするため，Ｚ軸はカメラの向きと一致するが，複数のカメラに対して共通の座標系を用いる場合など，Ｚ軸がカメラの向きと一致しない場合もある。以下では，距離・奥行き・Ｚ値を区別せずに距離情報と呼び，距離情報を画素値として表した画像を距離画像と呼ぶ。
【０００３】
距離情報を画素値として表す際に，物理量に対応する値をそのまま画素値とする方法と，最小値と最大値の間をある数に量子化して得られる値を用いる方法と，最小値からの差をあるステップ幅で量子化して得られる値を用いる方法がある。表現したい範囲が限られている場合には，最小値などの付加情報を用いる方が距離情報を高精度に表現することができる。
【０００４】
また，等間隔に量子化する際に，物理量をそのまま量子化する方法と物理量の逆数を量子化する方法とがある。一般に距離情報の逆数は視差に比例した値となるため，距離情報を高精度に表現する必要がある場合には前者を，視差情報を高精度に表現する必要がある場合には後者が使用されることが多い。以下では，距離情報の画素値化の方法や量子化の方法に関係なく，距離情報が画像として表現されたものをすべて距離画像と呼ぶ。
【０００５】
距離画像の利用用途の１つとして立体画像がある。一般的な立体画像の表現では観測者の右目用の画像と左目用の画像からなるステレオ画像であるが，あるカメラにおける画像とその距離画像とを用いて立体画像を表現することができる（詳しい技術は，非特許文献１を参照）。
【０００６】
このような１視点における映像と距離画像とを用いて表現された立体映像を符号化する方式には，ＭＰＥＧ−Ｃ Part.3 （ISO/IEC 23002-3 ）を使用することが可能である（詳しい内容は，非特許文献２を参照）。
【０００７】
映像と距離画像とを複数視点に対して持つことで，単視点の場合に表現可能な立体映像よりも，大きな視差を持った立体映像を表現することが可能となる（詳細は，非特許文献３を参照）。
【０００８】
また，このような立体映像を表現する用途以外に，距離画像は，鑑賞者が撮影カメラの配置を気にせずに自由に視点を移動できる自由視点映像を生成するデータの１つとしても使用される。このような撮影カメラとは別のカメラからシーンを見ているとしたときの合成画像を仮想視点画像と呼ぶことがあり，Image-based Rendering の分野で盛んにその生成法が検討されている。多視点の映像と距離画像とから仮想視点映像を生成する代表的な手法としては，非特許文献４に記載の手法がある。
【０００９】
距離画像は１つのコンポーネントで構成されているため，グレースケール画像とみなすことができる。また，被写体が実空間上で連続的に存在し，瞬間的に離れた位置へ移動することができないため，画像信号と同様に空間的相関および時間的相関を持つと言える。したがって，通常の画像信号や映像信号を符号化するために用いられる画像符号化方式や動画像符号化方式によって，距離画像や距離動画像は空間的冗長性や時間的冗長性を取り除きながら効率的に符号化することが可能である。実際にＭＰＥＧ−Ｃ Part.3 では，既存の動画像符号化方式を用いて符号化を行っている。
【００１０】
ここで，従来の一般的な映像信号の符号化方式について説明する。一般に被写体が実空間上で空間的および時間的連続性を持つことから，その見え方は空間的および時間的に高い相関をもつ。映像信号の符号化ではそのような相関性を利用して高い符号化効率を達成している。
【００１１】
具体的には，符号化対象ブロックの映像信号を既に符号化済みの映像信号から予測して，その予測残差のみを符号化することで，符号化する必要がある情報の量を減らし，高い符号化効率を達成する。代表的な映像信号の予想の手法としては，隣接するブロックから空間的に予測信号を生成する画面内予測や，異なる時刻に撮影された符号化済みフレームから被写体の動きを推定して時間的に予測信号を生成する動き補償予測がある。
【００１２】
また，予測残差信号と呼ばれる予測の誤差も，空間的な相関と人間の視覚特性を利用するために，ＤＣＴ等を用いて予測残差信号を周波数空間でのデータへ変換し，低周波領域に残差信号のエネルギーを集中することで，効率的に符号化を行う。各手法の詳細は動画像国際標準規格のＭＰＥＧ−２やＨ．２６４／ＭＰＥＧ−４  ＡＶＣ（非特許文献５）を参照されたい。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】C. Fehn, P. Kauff, M. Op de Beeck, F. Emst, W. IJsselsteijn, M. Pollefeys, L. Van Gool, E. Ofek and I. Sexton,“An Evolutionary and Optimised Approach on 3D-TV ”, Proceedings of International Broadcast Conference, pp.357-365, Amsterdam, The Netherlands, September 2002.
【非特許文献２】W.H.A. Bruls, C. Varekamp, R. Klein Gunnewiek, B. Barenbrug and A. Bourge,“Enabling Introduction of Stereoscopic (3D) Video: Formats and Compression Standards ”, Proceedings of IEEE International Conference on Image Processing, pp.I-89-I-92, San Antonio, USA, September 2007.
【非特許文献３】A. Smolic, K. Mueller, P. Merkle, N. Atzpadin, C. Fehn, M. Mueller, O. Schreer, R. Tanger, P. Kauff and T. Wiegand, “Multi-view video plus depth (MVD) format for advanced 3D video systems”, Joint Video Team of ISO/IEC JTC1/SC29/WG11 and ITU-T SG16 Q.6, Doc. JVT-W100, San Jose, USA, April 2007.
【非特許文献４】C. L. Zitnick, S. B. Kang, M. Uyttendaele, S. A. J. Winder, and R. Szeliski,“High-quality Video View Interpolation Using a Layered Representation”, ACM Transactions on Graphics, vol.23, no.3, pp.600-608, August 2004.
【非特許文献５】Recommendation ITU-T H.264, “Advanced video coding for generic audiovisual services”, March 2009.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
被写体は実空間上で連続であるため高い空間相関をもち，瞬間的に離れた位置へ移動することが不可能であるため高い時間相関を持つ。したがって，空間相関と時間相関とを利用する既存の動画像符号化方式を用いることで，グレースケール画像として表した距離画像を効率的に符号化することが可能である。
【００１５】
しかしながら，距離情報は被写体内部では変化が少なく，被写体間では非常に大きな違いがあることから，空間的または時間的な予測の結果，正確な予測が達成でき予測残差が非常に小さくなるか，全く有効な予測ができず予測残差が非常に大きくなってしまうかのどちらかとなる。つまり，予測残差信号に強いエッジが生成されることになる。そのような強いエッジは，ＤＣＴ等を用いて周波数空間でのデータへ変換されると，低周波領域に残差信号のエネルギーを集中させることができず，多くの高周波成分を生成することになる。その結果，残差信号を効率的に符号化することができない。
【００１６】
図１に，ある距離画像の９×９画素のブロックの一例を示した。このブロックには２つの被写体が存在し，一方の画素値が５０前後で，もう一方の画素値が２００前後である。空間的な予測では，このブロックの１行目と１列目の情報を用いて残りの８×８画素を予測する。すなわち，８×８画素の処理対象ブロックの画素値を，上側および左側に隣接する隣接画素の画素値で予測する。
【００１７】
予測の方法には様々なものがあるが，ここではＨ．２６４に採用されている代表的な２つの予測方法，水平予測と垂直予測の２つの例を示した。図の中央列に示される通り，予測残差には大きく分けて−１５０前後，０前後，１５０前後の３種類の値しか存在せず，かなり大きなエッジが生じている。
【００１８】
この予測残差に８×８の二次元ＤＣＴ（離散コサイン変換）をかけた結果が一番右の列である。直流（ＤＣ）成分は図の一番奥になり，左右に行くほど高周波を表している。図から分かるように，どちらの場合にも，多くの高周波領域に大きな信号が生じており，残差信号のコンパクト化に失敗していることが分かる。
【００１９】
予測を行わないでＤＣＴ等の変換のみを用いて符号化することも可能であるが，別のブロックとの空間的相関を取り除くことができず，さらに符号化効率が悪化してしまう。また，ＤＣＴ等の変換を行わないで符号化することも可能であるが，その場合には，ブロック内の局所的な相関を利用することができず，効率的な符号化を達成することができない。
【００２０】
本発明はかかる事情に鑑みてなされたものであって，距離画像のような画素値がオブジェクトに大きく依存する画像に対して，オブジェクトごとの代表画素値とオブジェクト識別情報を用いることで，距離画像のような画素値がオブジェクトに大きく依存する画像を効率的に符号化する画像符号化に関する技術，およびそのビットストリームを復号する画像復号に関する技術を提供することを目的とする。
【課題を解決するための手段】
【００２１】
本発明は，上記課題を解決するため，画像を伝送または蓄積するにあたり，画像フレームを予め定められた大きさの処理領域（以下，ブロックともいう）に分割し，ブロックごとに各画素の画素値を予測しながら符号化を行う画像符号化において，ブロック内に，固定数の被写体またはブロックごとに可変数の被写体が存在すると仮定し，各ブロックの画像を，「各被写体を代表する画素値（以下，被写体画素値という）」，「各画素の被写体識別情報」という情報で表現する。すなわち，ブロック内の１つの画素に対して，どの被写体であるかを示す１つの被写体識別情報が割り振られ，１つの被写体識別情報には１つの被写体画素値が対応付けられる。この情報に従い，画素ごとに最も類似する値を割り当てるため，複雑なエッジ形状を保持した予測画像を生成することができる。なお，ブロック内に含まれる被写体の数は高々数個に限られるため，この情報の量は限られる。
【００２２】
ここでいう被写体とは，撮影されている個々の物体や人物そのものを意味するのではなく，情報を付与する対象であり，例えば類似する画像信号（輝度，色彩，デプスなど）を持つ領域である。つまり，単一物体であっても，場所によって異なる色を持つ場合には，複数の被写体とみなす。また，画像信号を符号化する必要のない物体や物体の一部分は被写体とはみなさない。すなわち，被写体は，フレーム内の実オブジェクト（被写体）とは関係なく，情報が付与されない実オブジェクトは，本発明でいう“被写体”ではない。また，１つの実オブジェクトに対して２つの情報が付与される場合には，それぞれ別の被写体として扱われる。
【００２３】
本発明およびその実施形態の説明で使用する用語を説明する。
【００２４】
「被写体数」：被写体数は，ブロック内に存在する“被写体”の数であり，情報を付与する対象の個数である。被写体数は，ブロック内の画素値を解析することで生成することができる。例えば，ブロック内の画素を画素値や位置などの情報を用いてクラスタリングし，各クラスタの評価値（例えば，画素値の分散）が一定値以下となるクラスタ数の最大値を被写体数とすることが可能である。また，経験などに基づいて外部から与えたり，予め定められた値を用いることも可能である。被写体数は，付加情報の１つである被写体画素値の個数を表現するために用いられる。また，被写体マップに登場する被写体識別子の最大値を表現するためにも用いられる。
【００２５】
「被写体画素値」：被写体画素値は，“被写体”に対して１つ定義される値であり，その“被写体”を代表する画素値である。画素値としては，輝度値や色差値，Ｒ値などを用いることができる。また，ＲＧＢ値などの複数の色コンポーネント値の集合を用いる場合もある。被写体画素値は，ブロック内の画素値を解析することで生成する。具体的には，ブロック内の画素を画素値や位置などの情報を用いて“被写体数”のクラスタにクラスタリングし，各クラスタごとに，含まれる画素の画素値に対する平均値や中央値を計算することで得る。ブロック内の各画素に対して，その画素の“被写体”に対応する被写体画素値を割り当てることで，そのブロックの予測画像を生成するために用いられる。
【００２６】
「被写体マップ」：被写体マップは，ブロック内の各画素にどの“被写体”が存在しているかを示したものである。具体的には，各画素を“被写体”（被写体画素値）に対応付けられた被写体識別子で表現したものである。最も単純な表現では２次元情報として表現できるが，木構造を用いて表現することもできる。被写体マップは，ブロック内の各画素に対して，その画素値に最も近い被写体画素値に対応する被写体識別子を割り当てることで生成する。なお，画素値と被写体画素値の類似度だけでなく，被写体マップ自体の表現に必要なビット数も鑑みて生成することもある。被写体マップは，予測画像を生成する際に，ブロック内の各画素に対して，どの被写体画素値を割り当てたのかを示すために用いられる。
【００２７】
「付加情報」：本発明で処理対象フレームの画像（映像）信号を予測するために用いる情報を付加情報と呼ぶ。付加情報は，処理を行うブロック単位で生成される。付加情報は，基本的には被写体数・被写体画素値・被写体マップの３つの情報で構成される。
【００２８】
本発明の画像符号化では，以下の処理を行う。
（１）ブロック内に存在する被写体の数を被写体数として設定する。
（２）ブロック内に被写体数だけの被写体が存在すると仮定して，被写体ごとに１つの画素値を被写体画素値として設定する。
（３）被写体を識別する被写体識別子と被写体画素値とを対応づけ，ブロック内の各画素の画素値と被写体画素値とから，ブロック内の各画素にどの被写体が撮影されているかを被写体識別子で示す被写体マップを生成する。
（４）ブロック周辺の符号化済みブロックの画像（映像）信号を符号化する際に使用した被写体マップを参照被写体マップとして設定する。
（５）被写体マップに従って各画素に被写体画素値の値を割り当てることでブロックに対する予測画像を生成する。
（６）参照被写体マップを用いて予測を行いながら被写体マップを符号化する。
（７）予測画像を用いてブロックに対する画像信号を予測符号化する。
（８）被写体数については，符号化する場合と，符号化しない場合とがある。上記（１）の被写体数を設定するステップにおいて，復号側が参照可能な情報のみを用いて被写体数を設定した場合には符号化を行わない。それ以外の場合には符号化を行う。符号化を行わない場合としては，例えば，予め定められた被写体数を設定する場合やブロック周辺の符号化済みのブロックの画像情報や被写体数から予測して設定する場合などがある。符号化を行う場合としては，例えば，ブロック内の画素値を解析して設定した場合がある。なお，符号化にあたっては，被写体数をそのまま符号化する方法と，被写体数の符号量を少なくするために，復号側が参照可能な情報のみを用いて予測値を生成し，その予測値との差分値を符号化する方法がある。
（９）被写体画素値についても，符号化する場合と，符号化しない場合とがある。上記（２）の被写体画素値を設定するステップにおいて，復号側が参照可能な情報のみを用いて被写体画素値を設定した場合には符号化を行わない。それ以外の場合には符号化を行う。符号化を行わない場合としては，例えば，ブロック周辺の符号化済みのブロックの画像情報や被写体画素値から予測して設定する場合などがある。符号化を行う場合としては，例えば，ブロック内の画素値を解析して設定した場合がある。なお，符号化にあたっては，被写体画素値をそのまま符号化する方法と，被写体画素値の符号量を少なくするために，復号側が参照可能な情報のみを用いて予測値を生成し，その予測値との差分値を符号化する方法がある。予測値の生成には，ブロック周辺の符号化済みのブロックの画像情報や被写体画素値，符号化順で先に符号化される被写体画素値を用いることができる。
（１０）以上の被写体マップの符号データ，画像信号の符号データ，さらに被写体数を符号化した場合にはその符号データ，また，被写体画素値を符号化した場合にはその符号データを多重化して出力する。
【００２９】
以上のように，本発明では，予測画像を生成するために，被写体の代表的な画素値である被写体画素値，およびどの被写体画素値を用いて予測画像を生成するかを画素ごとに示す被写体マップの２つの付加情報を用いる。予測画像の生成に「予測方向」という情報を用いていた従来技術と比較して，本発明は，付加情報の符号量が増加するが，正確な予測画像を生成することで，予測残差の符号化に必要な符号量を大幅に減らし，トータルとしてブロックあたりに必要な符号量を削減することができる。
【００３０】
さらに，被写体が空間的に連続していることから，各画素には隣接する画素と同じ被写体が写っている可能性が高い。そのため，被写体の種類を表現する被写体マップを符号化する際に，周辺ブロックを符号化する際に用いた被写体マップを参照して，ブロックに対する被写体マップの各画素における被写体を予測したり，被写体の存在確率を制御することで，必要な符号量を削減することが可能となる。
【００３１】
また，本発明は，ブロック周辺の符号化済みブロックを符号化する際に使用した被写体画素値と，上記（２）で設定した被写体画素値とを比較して，ブロック周辺の符号化済みブロックを符号化する際に使用した被写体識別子を，上記（３）で使用した被写体識別子へと置換する置換行列を生成し，上記（４）の参照被写体マップを設定するステップにおいて，ブロック周辺の符号化済みブロックを符号化する際に使用した被写体マップ内の被写体識別子を，生成した置換行列を用いて，置換することで参照被写体マップを生成してもよい。参照被写体マップで用いられた被写体識別子に対応する被写体と被写体マップで用いられた被写体識別子に対応する被写体を一致させることで，ブロック間で異なる被写体が存在する場合においても，正しく被写体マップにおける空間的相関を利用することができる。
【００３２】
また，本発明は，予測画像を用いて上記（７）で生成された符号データを復号して得られる復号画像を蓄積し，上記（４）の参照被写体マップを設定するステップにおいて，ブロック周辺の符号化済みブロックに対して蓄積されている復号画像を用いて，各画素の画素値に最も近い被写体画素値に対して上記（３）で対応付けられた被写体識別子を割り当てることで参照被写体マップを生成してもよい。周辺ブロックを符号化する際に被写体マップを使用していない場合，符号化対象のブロックに対する被写体画素値を用いて周辺ブロックに対して被写体識別子を割り当てることで参照被写体マップを生成し，ブロック間の被写体の存在に対する相関を利用して，被写体マップを効率的に符号化することができる。
【００３３】
また，本発明は，参照被写体マップのエッジ情報を用いて，ブロックを分割する方法を設定し，その分割方法に従って被写体マップを木構造で表されたものへと変換し，上記（６）の被写体マップを符号化するステップにおいて，参照被写体マップを用いて，木構造で表された被写体マップを符号化してもよい。周辺ブロックにおける被写体の分布に従って分割方法を決定することで，空間相関を利用した木構造を構築することができ，より少ない符号量での符号化を実現することができる。
【００３４】
本発明の復号処理では，以下の処理を行う。
（１）ブロック内に存在する被写体の数を被写体数として設定する。この被写体数の設定では，符号データを復号して得られた被写体数を設定する場合と，周辺ブロックなどで既に復号済みの情報のみを用いて被写体数を設定する場合とがある。符号データから復号を行わない場合としては，例えば，予め定められた被写体数を設定する場合やブロック周辺の復号済みのブロックの画像情報や被写体数から予測して設定する場合などがある。なお，被写体数を復号するにあたっては，符号データから被写体数そのものを復号する場合と，周辺ブロックなどで既に復号済みの情報のみを用いて予測値を生成し，その予測値との差分値のみを符号データから復号する場合とがある。
（２）各被写体識別子ごとに１つの被写体画素値を設定する。この被写体画素値の設定では，符号データを復号して得られた被写体画素値を設定する場合と，周辺ブロックなどで既に復号済みの情報のみを用いて被写体画素値を設定する場合とがある。符号データから復号を行わない場合としては，例えば，ブロック周辺の復号済みのブロックの画像情報や被写体画素値から予測して設定する場合などがある。なお，復号するにあたっては，被写体画素値そのものを復号して直接的に得る場合と，周辺ブロックなどですでに復号済みの情報のみを用いて予測値を生成し，その予測値との差分値を復号して間接的に取得する場合がある。予測値の生成には，ブロック周辺の復号済みのブロックの画像情報や被写体画素値と，復号中のブロックにおいて復号順で先に復号された被写体画素値を用いることができる。
（３）ブロック周辺の復号済みブロックを復号する際に使用した被写体マップを参照被写体マップとして設定する。
（４）参照被写体マップを用いて予測を行いながら，復号対象となる符号データから，被写体マップを復号する。
（５）被写体マップに従って各画素に被写体画素値の値を割り当てることでブロックに対する予測画像を生成する。
（６）予測画像を用いてブロックに対する画像信号を符号データから復号する。
【００３５】
これにより，上記画像符号化によって符号化された画像を復号することができる。
【００３６】
また，本発明は，ブロック周辺の復号済みブロックを復号する際に使用した被写体画素値と，上記（２）で設定した被写体画素値とを比較して，ブロック周辺の復号済みブロックを復号する際に使用した被写体識別子を，復号するブロックに対する被写体識別子へと置換する置換行列を生成し，上記（３）の参照被写体マップを設定するステップにおいて，ブロック周辺の復号済みブロックを復号する際に使用した被写体マップ内の被写体識別子を，生成した置換行列を用いて置換することで，参照被写体マップを生成してもよい。
【００３７】
また，本発明は，上記（６）で得られる復号画像を蓄積し，上記（３）の参照被写体マップを設定するステップにおいて，ブロック周辺のブロックに対して蓄積されている復号画像を用いて，各画素の画素値に最も近い被写体画素値の被写体識別子を割り当てることで参照被写体マップを生成してもよい。
【００３８】
また，本発明は，参照被写体マップのエッジ情報を用いて，ブロックを分割する方法を設定し，上記（４）の被写体マップを復号するステップにおいて，参照被写体マップを用いて，設定した分割方法に従って木構造で表された被写体マップを復号してもよい。
【発明の効果】
【００３９】
本発明によれば，距離画像のような画素値がオブジェクトに大きく依存し，局所的には限られた数の被写体しか存在しないような画像に対して，画像全体を分割して領域ごとに，被写体の存在の空間的な連続性を用いて，各画素に写っている被写体の種類を予測することで，被写体ごとの代表画素値と各画素における被写体の種類を識別するための情報を用いた画像信号予測において必要となる付加情報の符号量を削減し，効率的な画像符号化を実現することができる。
【図面の簡単な説明】
【００４０】
【図１】本発明の課題を説明する図である。
【図２】本発明の第１実施形態による画像符号化装置の構成例を示すブロック図である。
【図３】第１実施形態による画像符号化装置の処理フローチャートである。
【図４】被写体マップの例を示す図である。
【図５】各画素の被写体識別子を符号化する処理のフローチャートである。
【図６】木構造被写体マップを符号化する処理のフローチャートである。
【図７】木構造被写体マップの例を示す図である。
【図８】木構造被写体マップの例を示す図である。
【図９】被写体識別子の情報を用いて可変のブロック分割を設定する例を説明する図である。
【図１０】エッジの向きに沿った形でブロック分割を設定する例を説明する図である。
【図１１】画像符号化装置の他の構成例を示すブロック図である。
【図１２】参照被写体マップを設定する処理のフローチャートである。
【図１３】画像符号化装置のさらに他の構成例を示すブロック図である。
【図１４】画像符号化装置の処理フローチャートである。
【図１５】本発明の第２実施形態による画像復号装置の構成例を示すブロック図である。
【図１６】第２実施形態による画像復号装置の処理フローチャートである。
【図１７】被写体数が符号化されている場合の画像復号装置の構成例を示すブロック図である。
【図１８】被写体画素値が符号化されている場合の画像復号装置の構成例を示すブロック図である。
【図１９】被写体識別子が符号化されている場合の復号処理のフローチャートである。
【図２０】被写体マップの各ノードの情報が符号化されている場合の復号処理のフローチャートである。
【図２１】画像復号装置の他の構成例を示す図である。
【図２２】画像復号装置の他の構成例を示す図である。
【図２３】画像符号化装置をコンピュータとソフトウェアプログラムとによって構成する場合のハードウェア構成例を示す図である。
【図２４】画像復号装置をコンピュータとソフトウェアプログラムとによって構成する場合のハードウェア構成例を示す図である。
【発明を実施するための形態】
【００４１】
本発明では，画像全体を分割して領域ごとに画像信号を予測しながら符号化する場合に，物体が画素の大きさに対してある程度の体積を持ち，空間的に連続して存在している性質を利用することで，処理領域周辺の既に処理が終了した領域の各画素における被写体の種類の情報から，処理領域内の各画素に写っている被写体の種類を予測する。これにより，処理領域内の各被写体を代表する画素値と，処理領域内の各画素の被写体の種類を識別するための情報とを用いた任意の被写体形状に対応した高精度な画像信号予測を行う際に必要となる「処理領域内の各画素の被写体の種類を識別するための情報」の符号化に必要な符号量を減らし，効率的な画像符号化を実現することが可能となる。
【００４２】
以下，本発明の一実施形態を，図面を参照して説明する。
【００４３】
〔第１実施形態：画像符号化装置〕
まず，第１実施形態について説明する。図２は本発明の第１実施形態による画像符号化装置の構成例を示すブロック図である。画像符号化装置１００は，図２に示すように，符号化対象フレーム入力部１０１，符号化対象フレーム記憶部１０２，被写体数設定部１０３，被写体画素値設定部１０４，被写体マップ生成部１０５，被写体マップ記憶部１０６，被写体マップ符号化部１０７，予測画像生成部１０８，画像信号符号化部１０９，および多重化部１１０を備えている。
【００４４】
符号化対象フレーム入力部１０１は，符号化対象となる画像フレームを入力する。符号化対象フレーム記憶部１０２は，入力された符号化対象フレームを蓄積する。被写体数設定部１０３は，予め定められた大きさの処理領域に含まれる被写体数を設定する。被写体画素値設定部１０４は，処理領域に与えられた数の被写体が存在すると仮定して，被写体ごとに被写体画素値を設定する。
【００４５】
被写体マップ生成部１０５は，処理領域に対する被写体マップを生成する。被写体マップ記憶部１０６は，使用された被写体マップを蓄積する。被写体マップ符号化部１０７は，処理領域に対する被写体マップを符号化する。予測画像生成部１０８は，処理領域に対して生成された被写体画素値と被写体マップから，処理領域に対する予測画像を生成する。画像信号符号化部１０９は，処理領域ごとに予測画像を用いて符号化対象フレームの画像信号を符号化する。多重化部１１０は，被写体マップの符号データと，符号化対象フレームの画像信号の符号データを多重化して出力する。
【００４６】
図３は，第１実施形態による画像符号化装置１００の動作を説明するためのフローチャートである。このフローチャートに従って，画像符号化装置１００の実行する処理について詳細に説明する。
【００４７】
まず，符号化対象フレーム入力部１０１により，符号化対象フレームを入力し，符号化対象フレーム記憶部１０２に格納する（ステップＳ１０１）。符号化対象フレームの格納が終了したら，符号化対象フレームを分割し，分割した領域ごとに，符号化対象フレームの画像信号を符号化する（ステップＳ１０２〜Ｓ１１２）。つまり，符号化対象ブロックインデックスをｂｌｋ，総符号化対象ブロック数をｎｕｍＢｌｋｓで表すとすると，ｂｌｋを０で初期化し（ステップＳ１０２），その後，ｂｌｋに１を加算しながら（ステップＳ１１１），ｂｌｋがｎｕｍＢｌｋｓになるまで（ステップＳ１１２），以下の処理（ステップＳ１０３〜Ｓ１１０）を繰り返す。
【００４８】
符号化対象ブロックごとに繰り返す処理では，まず，被写体数設定部１０３で，ブロックｂｌｋに含まれる被写体の数ｎｕｍＯｂｊｓを設定する（ステップＳ１０３）。被写体数は復号側と同じ処理であれば，どのような処理を用いて決定してもかまわない。例えば，常に予め定められた数を設定してもかまわない。
【００４９】
また，符号化対象ブロックごとに異なる値を被写体数として設定してもかまわない。符号化対象ブロックごとに異なる値を設定する方法としては，符号化対象ブロックの画素値に従って被写体数を設定する方法がある。具体的には，符号化対象ブロックの画素に対してｋ−ｍｅａｎｓ法やＡｆｆｉｎｉｔｙ  Ｐｒｏｐａｇａｔｉｏｎなどのクラスタリング手法を用いて，各クラスタ内の画素値分散が予め定められた値以下になるクラスタリング結果のうち，最小のクラスタ数を被写体数にする方法がある。クラスタリングに用いる尺度としては，画素値のみを用いてもかまわないし，画素値と画素位置とからなる値を用いてもかまわない。別の方法としては，被写体数の候補ごとに，その被写体数を設定して符号化した場合の符号量と歪み量との重み付き和で与えられるレート歪みコストを計算し，そのコストが最小になる被写体数を設定する方法がある。
【００５０】
別の方法として，符号化対象ブロック周辺の既に符号化済みのブロックの情報を用いて被写体数を設定する方法がある。具体的には，複数の予め定められた周辺ブロックを符号化する際に設定された被写体数の平均値や中央値を，符号化対象ブロックの被写体数とする方法や，符号化対象ブロック周辺の既に符号化済みの画素群に対して，前述のクラスタリング手法を適用し，各クラスタ内の画素値分散が予め定められた値以下になるクラスタリング結果のうち最小のクラスタ数を，符号化対象ブロックの被写体数にする方法がある。
【００５１】
ブロックごとに異なる被写体数を設定する際に，被写体数が大きくなると符号化効率が低下する場合がある。そのため，被写体数の最大値を予め定めておき，被写体数が一定値以上になるのを防いでもかまわない。
【００５２】
なお，符号化対象ブロックの画素に対する画素値等の情報を用いて，ブロックごとに異なる被写体数を設定する場合には，被写体数を符号化して出力する符号データに含める必要がある。被写体数を符号化する場合，設定した被写体数をそのまま符号化してもかまわないし，符号化対象ブロック周辺の既に符号化済みのブロックに対する画素値などの情報を用いて予測した被写体数との差分値を符号化してもかまわない。
【００５３】
被写体数を符号化する場合，ブロックごとに符号化するのではなく，フレームやスライスと呼ばれる複数ブロックの集合ごとに被写体数を設定・符号化してもかまわない。このようにすることで，被写体数が領域に依存して変化するような場合に，効率的に被写体数を符号化することが可能となる。なお，フレームまたはスライス単位の被写体数の設定・符号化と，ブロックごとの被写体数の設定・符号化とを組み合わせることも可能である。その場合，フレームまたはスライス単位では，そのフレームまたはスライスに含まれる複数ブロックの多くに当てはまると考えられる被写体数を設定・符号化し，ブロックごとにその被写体数からの変化量を設定・符号化する。ブロックごとに設定・符号化する変化量は，隣接する既に符号化済みの領域の情報を用いて予測し，変化量の予測差分として符号化することも可能である。
【００５４】
被写体数の設定が終了したら，次に，被写体画素値設定部１０４で，ブロックｂｌｋ内の被写体ごとに１つの画素値を設定し，被写体画素値Ｖａｌｕｅ（ｉ）とする（ステップＳ１０４）。ここでｉは，被写体を識別するための被写体識別子とし，０以上ｎｕｍＯｂｊｓ未満の整数である。また，被写体識別子は予め定められた規則に従って割り当てる。ここでは，被写体画素値が小さい順に，被写体識別子のｉの値が割り当てられているとする。
【００５５】
被写体ごとに１つの画素値を設定する方法には，どのような方法を用いてもかまわない。例えば，画素値の値域を被写体数で均一量子化し，各範囲の中央値を設定してもかまわない。別の方法としては，ブロックｂｌｋの画素を前述のようなクラスタリング手法を用いて，ｎｕｍＯｂｊｓ個のクラスタに分割し，各クラスタに含まれる画素の画素値の平均値や中央値を，被写体画素値とする方法がある。なお，被写体数を設定する際に，ブロックｂｌｋの画素をクラスタリングしている場合には，被写体数と被写体画素値を同時に設定してもかまわない。
【００５６】
さらに別の方法としては，ｎｕｍＯｂｊｓ個以下のクラスタ数で，クラスタ内の画素値分散値の最大値が別途定められた閾値より小さくなる最小のクラスタ数で分割して，クラスタごとの平均値や中央値を被写体画素値に設定し，ｎｕｍＯｂｊｓ個に不足する分は適当に被写体画素値を設定する方法がある。常に被写体数が一定の場合，本来は単一オブジェクトしか存在しない場合にも，複数の被写体が存在すると仮定することにより，過度に高精度な予測を提供し，後述の被写体マップの符号量が増大してしまう可能性がある。しかし，ターゲットとなるビットレートに応じて閾値を定めて，ｎｕｍＯｂｊｓによらずに被写体識別子を定めることで，符号量が多くなり過ぎるのを防ぐことが可能となる。
【００５７】
さらに別の方法として，符号化対象ブロック周辺の既に符号化済みのブロックを符号化する際に使用された被写体画素値を用いて設定する方法がある。具体的には，周辺ブロックで同じ被写体識別子に対して割り当てられた被写体画素値の平均値や中央値を，符号化対象ブロックの被写体識別子として設定する方法や，周辺ブロックで使用された被写体画素値の集合を求めて，それをｎｕｍＯｂｊｓ個のクラスタへ分割し，各クラスタ内の平均値や中央値を，符号化対象ブロックの被写体識別子として設定する方法がある。
【００５８】
さらに別の方法として，符号化対象ブロック周辺の既に符号化済みの画素に対する画素値を用いて設定する方法がある。具体的には，符号化対象ブロック周辺の既に符号化済みの画素群を，前述のようなクラスタリング手法を用いて，ｎｕｍＯｂｊｓ個のクラスタに分割し，各クラスタに含まれる画素の画素値の平均値や中央値を，被写体画素値とする方法がある。
【００５９】
なお，符号化対象ブロックの画素に対する画素値等の情報を用いて，ブロックごとに異なる被写体画素値を設定する場合には，被写体画素値を符号化して出力する符号データに含める必要がある。被写体画素値を符号化する場合，設定した被写体画素値をそのまま符号化してもかまわないし，また，符号化対象ブロック周辺の既に符号化済みのブロックに対する画素値などの情報を用いて予測した被写体画素値との差分値を符号化してもかまわない。
【００６０】
被写体画素値が得られたら，次に，被写体マップ生成部１０５でブロックｂｌｋに対して被写体マップを生成する（ステップＳ１０５）。生成された被写体マップは，被写体マップ記憶部１０６にブロック位置と対応付けて蓄積されるとともに，被写体マップ符号化部１０７に送られる。ここで，被写体マップとは，ブロックｂｌｋの各画素に対して，被写体識別子を割り当てたものである。例えば，図４のような２次元情報である。図４において，０，１，２の値がそれぞれの画素に対して割り当てられた被写体識別子である。
【００６１】
各画素に対して被写体識別子を割り当てる方法としては，各画素に対して，その画素値に最も近い被写体画素値を持つ被写体識別子を割り当てる方法がある。また，別の方法としては，被写体画素値を設定する際にクラスタリングを行っている場合には，その結果を利用して，クラスタごとに割り当てられた被写体識別子を，そのクラスタに属する画素に対して設定する方法がある。
【００６２】
さらに別の方法としては，複数の被写体マップ候補を生成し，被写体マップ候補ごとに，その被写体マップ候補を用いて符号化を行った際の符号量と歪み量との重み付き和で与えられるレート歪みコストを計算し，その値が最小となるものを被写体マップとして設定する方法がある。その場合，可能性のあるすべての被写体マップを被写体マップ候補にしてもかまわないし，限定した幾つかの特徴的な被写体マップのみを被写体マップ候補にしてもかまわない。特徴的な被写体マップとしては，各画素に対して，その画素値に最も近い被写体画素値を持つ被写体識別子を割り当てて生成した被写体マップや，すべての画素が同じ被写体識別子となるような被写体マップ，水平や垂直に２分割された被写体マップなどがある。
【００６３】
次に，被写体マップ記憶部１０６に蓄積されている符号化対象ブロック周辺の既に符号化済みのブロックを符号化する際に使用された被写体マップを，参照被写体マップとして設定する（ステップＳ１０６）。参照被写体マップの選び方は，復号側と同じであれば，どのような方法を用いてもかまわない。例えば，予め定められた位置関係に存在するブロック群に対する被写体マップとしてもかまわないし，フレームやブロック群などの単位ごとに選び方を示す情報を符号化して，符号データの一部としてもかまわない。具体例としては，符号化対象ブロックに対して上・左・左上に位置するブロックに対する被写体マップの集合を参照被写体マップとして設定する方法がある。
【００６４】
次に，参照被写体マップを用いて，生成された被写体マップを被写体マップ符号化部１０７で符号化する（ステップＳ１０７）。２次元のマップ情報を符号化するにあたっては，ラスタースキャン順やジグザグスキャン順に各画素の被写体識別子を符号化する方法と，四分木（クアッドツリー）や二分木（バイナリツリー）などの木構造のデータに変換した後に，深さ優先探索や幅優先探索による走査順に各ノードの情報を符号化する方法がある。
【００６５】
ラスタースキャン順やジグザグスキャン順に各画素の被写体識別子を符号化する場合の処理を図５のフローに従って詳しく説明する。ここでの処理は符号化対象ブロック内の画素ごとに行われるため，符号化対象ブロック内の画素のインデックスをｐｉｘ，符号化対象ブロック内の画素数をｎｕｍＰｉｘｓで表すとすると，ｐｉｘを０で初期化し（ステップＳ１７０１），その後，ｐｉｘに１を加算しながら（ステップＳ１７０５），ｐｉｘがｎｕｍＰｉｘｓになるまで（ステップＳ１７０６），以下の処理（ステップＳ１７０２〜Ｓ１７０４）を繰り返す。
【００６６】
画素ごとに繰り返される処理では，まず，画素ｐｉｘの周囲の画素群を参照画素群に設定する（ステップＳ１７０２）。参照画素群は，参照被写体マップ内の画素群，または，ｐｉｘより小さなインデックス値の画素群から選択する。参照画素群の選び方としては，復号側と同じであればどのような選び方をしてもかまわない。例えば，予め定められた位置関係に存在する画素群としてもかまわないし，フレームやブロック群などの単位ごとに選び方を示す情報を符号化して復号側へ伝えてもかまわない。ここでは，画素ｐｉｘの上・左・左上で隣接する画素群を参照画素群として設定したとする。
【００６７】
次に，参照画素群に対する被写体識別子から，画素ｐｉｘの被写体識別子の予測値を生成する（ステップＳ１７０３）。予測値としては，１つの被写体識別子を生成する場合と，各被写体識別子の発生確率を生成する場合と，その両方を生成する場合がある。どの予測値を生成するかは，次の符号化の方法に従って決められる。
【００６８】
予測値として１つの被写体識別子を生成する方法としては，参照画素群の中でもっとも多く現れた被写体識別子を予測値とする方法がある。なお，最も多く現れた被写体識別子が複数存在する場合には，予め定められた規則に従って１つの被写体識別子を選択する。例えば，被写体識別子そのものの大きさなどに従って順位付けするとか，画素ｐｉｘに対する位置関係に応じて順位付けする方法がある。
【００６９】
各被写体識別子の発生確率を生成する方法では，参照画素群の中で出現する回数が多いほど高い発生確率になるようにする。ただし，一度も現れていない被写体識別子の発生確率がゼロにはならないようにする必要がある。なお，出現回数に応じてどの程度の発生確率差をつけるかは，固定であっても，可変であってもかまわない。可変にする方法としては，参照画素群に対する被写体識別子の状態ごとに異なる確率テーブルを用意し，符号化開始時に初期化を行い，被写体画素値を１つ符号化する度に符号化したデータに基づいて利用した確率テーブルを更新していく方法がある。この場合，複数のブロックをまたいで確率テーブルを変動させつつ，局所的な変化にも対応させられることから，外れ値が存在する場合においても頑健に発生確率を予測することが可能となる。なお，符号データにランダムアクセス性を持たせるためには，確率テーブルを適当な間隔で初期化し直す必要がある。
【００７０】
両方を生成する方法では，２つの処理を独立して行ってもかまわないし，発生確率を生成した後に，最も大きな発生確率を持つ被写体識別子を探すことで，両方の情報を生成してもかまわない。
【００７１】
予測値が生成されたら，その予測値を用いて画素ｐｉｘに対する被写体識別子の符号化を行う（ステップＳ１７０４）。１つの予測被写体識別子が与えられた場合には，まず，その予測が正しいか否かを表すバイナリ情報を符号化する。次に，予測が正しくない場合にのみ，画素ｐｉｘに対する被写体識別子を符号化する。発生確率が与えられた場合には，その確率に従って，画素ｐｉｘに対する被写体識別子をエントロピー符号化する。エントロピー符号化には，算術符号化やハフマン符号化などを用いることができる。両方の情報が与えられた場合には，まず，その予測が正しいか否かを表すバイナリ情報を符号化し，その後で，予測が正しくない場合に，与えられた発生確率に従って，画素ｐｉｘに対する被写体識別子をエントロピー符号化する。なお，発生確率を符号化履歴に応じて可変にする場合，画素ｐｉｘの被写体識別子の符号化が終了したら，使用した確率テーブルを符号化した被写体識別子に応じて更新する。
【００７２】
被写体マップを符号化するにあたって，被写体マップを木構造のデータに変換した後に，深さ優先探索の走査順に各ノードの情報を符号化する場合の処理を図６のフローに従って詳しく説明する。なお，木構造のデータとは，ブロックｂｌｋをルートとして，各ノードの子ノードには，親ノードのブロックを分割した複数のサブブロックを対応させて，対応する領域の情報をノードに付与することで２次元の情報を表現したものである。このような木構造表現を用いることで，まとまって存在する単一オブジェクトの画素集合を効率よく表現することが可能となり，符号化効率を向上させることが可能となる。
【００７３】
なお，木構造データの定義としては，任意のものを用いることが可能である。例えば，各ノードに対して，そのノードに対応するブロック内のすべての画素の被写体識別子が同じか否かを表すバイナリ情報を付加し，子ノードとして，被写体識別子がすべて同じ場合にはその被写体識別子の番号を持つリーフ（終端ノード），被写体識別子がすべて同じではない場合には自身のブロックを予め定められた方法で分割して生成したサブブロックに対応するノードを定義して木構造の情報を生成することができる。なお，この定義を用いる場合，対応するブロックが１画素になった際に，すべての画素の被写体識別子が同じか否かを表すバイナリ情報のノードを省略することができる。
【００７４】
図４の被写体マップに対して，以上のように生成した木構造データ（木構造被写体マップ）の例を図７に示す。この例は，ブロック分割の際に縦横それぞれを等分する四分木（クアッドツリー）による表現である。
【００７５】
各ノードの定義として別のものを使うこともできる。例えば，各ノードに対して，そのノードに対応するブロック内のすべての画素の被写体識別子が同一な場合にはその被写体識別子の番号に１を足した数，そうでない場合には０を情報として付与し，情報０を付与されたノードに対してのみ，そのブロックを分割したサブブロックに対する子ノードを定義する方法もある。図４の被写体マップに対して，この定義と縦横それぞれを等分してブロック分割を用いる生成した木構造被写体マップが図８である。
【００７６】
木構造データへの変換を介して被写体マップを符号化する処理では，符号化対象ブロックから始めて，ブロックに対するノード情報の生成・符号化を行い，必要に応じてそのブロックを分割し生成されるサブブロックに同様の処理を再帰的に施すことで，被写体マップを符号化する。つまり，未処理ブロックの集合をＮ，処理済み画素の集合をＦ，ブロックｂｌｋをｂ１と表すとすると，Ｎを｛ｂ１｝で，Ｆを参照被写体マップに含まれる画素の集合で初期化した後（ステップＳ１７１１），Ｎが空集合になるまで（ステップＳ１７２１），以下の処理（ステップＳ１７１２〜Ｓ１７２０）を繰り返す。
【００７７】
Ｎが空集合になるまで繰り返される処理では，まず，Ｎから１つのブロックを取り出す（ステップＳ１７１２）。このとき，どのブロックを取り出すかは予め定められた規則に従って決定する。木の走査順を深さ優先探索とする場合には，ＬＩＦＯ（Last In First Out ），つまりスタックのように後から入ったものを先に取り出す。走査順を幅優先探索とする場合には，ＦＩＦＯ（First In First Out），つまりキューのように先に入ったものを先に取り出す。以下では，ここで取り出されたブロックをｂｓと表すものとする。
【００７８】
次に，ブロックｂｓに対する情報Ｉ（ｂｓ）を生成する（ステップＳ１７１３）。ここでは前述の例に従い，ブロックｂｓ内のすべての画素の被写体識別子が同一な場合にはその被写体識別子の番号に１を足した数，そうでない場合には０をＩ（ｂｓ）とする。
【００７９】
次に，画素群Ｆに対する被写体識別子の情報を用いて，Ｉ（ｂｓ）の予測値または生起確率分布，またはその両方を生成する（ステップＳ１７１４）。Ｉ（ｂｓ）の予測値や生起確率分布の生成方法には任意の方法を用いることが可能である。
【００８０】
予測値を生成する方法としては，例えば，Ｆに含まれる画素群のうちブロックｂｓに隣接する画素群に対する被写体識別子のうち，最も多く現れる被写体識別子とその発生頻度を求め，発生頻度が予め定められた閾値以上であれば，その被写体識別子に１を加えた値を予測値とし，閾値未満であれば０を予測値とする方法がある。また，閾値未満であった場合に，０を第１の予測値とし，その被写体識別子に１を加えた値を第２の予測値とする方法もある。
【００８１】
生起確率分布を生成する方法として，例えば，Ｆに含まれる画素群のうちブロックｂｓに隣接する画素群に対する被写体識別子を調べ，各被写体識別子の発生頻度に応じて，生起確率を設定する方法がある。具体的には，まず０に対する確率を計算する。０はブロック内の被写体識別子が１つではない場合なので，計算した発生頻度の最大値が小さいほど大きな値になるように設定する。そのあとで，残りの確率を，発生頻度に応じて分配することで確率分布を生成する。ただし，ブロックサイズが１画素の場合を除き，生起確率はすべての値においてゼロより大きい値である必要がある。
【００８２】
なお，０に対する確率を決定する方法や，発生頻度に応じた分配を行う方法は，固定であっても，可変であってもかまわない。可変にする方法としては，発生頻度や対象の値，ブロックのサイズなどの状態ごとに異なる確率テーブルを用意し，符号化開始時に初期化を行い，値を１つ符号化する度に符号化したデータに基づいて利用した確率テーブルを更新していく方法がある。この場合，複数のブロックをまたいで確率テーブルを変動させつつ，局所的な変化にも対応させられることから，外れ値が存在する場合においても頑健に発生確率を予測することが可能となる。なお，複数の状態ごとに１つの確率テーブルを使うようにしてもかまわない。符号データにランダムアクセス性を持たせるためには，確率テーブルを適当な間隔で初期化し直す必要がある。
【００８３】
また，生起確率分布と予測値の両方を生成する場合には，両者を独立して生成してもかまわないし，生起確率分布を生成した後に，最も高い生起確率を持つ値を予測値としてもかまわない。
【００８４】
Ｉ（ｂｓ）の予測値や生起確率分布の生成が終了したら，それらの情報を用いて，Ｉ（ｂｓ）を符号化する（ステップＳ１７１５）。ステップＳ１７１４において予測値を生成した場合には，予測値が正しいか否かを表すバイナリ情報を符号化し，その後で予測が正しくなかった場合にのみ，Ｉ（ｂｓ）を符号化する。予測値を生成していない場合には，直接Ｉ（ｂｓ）の値を符号化する。なお，Ｉ（ｂｓ）を符号化する際に，ステップＳ１７１４において生起確率分布を生成した場合には，その確率に従って，Ｉ（ｂｓ）をエントロピー符号化する。なお，生起確率分布の生成を符号化履歴に応じて可変にする場合，Ｉ（ｂｓ）の符号化が終了したら，使用した確率テーブルを符号化したＩ（ｂｓ）に応じて更新する。
【００８５】
Ｉ（ｂｓ）の符号化が終了したら，ブロックｂｓに複数の被写体が含まれているか否かをチェックする（ステップＳ１７１６）。木構造データの定義によってチェック方法は異なるが，ここではＩ（ｂｓ）が０であるか否かをチェックする。Ｉ（ｂｓ）が０でない場合には，ブロックｂｓに含まれるすべての画素が同じ被写体識別子を持つため，ブロックｂｓに対しては十分な情報が与えられたことになるため，ブロックｂｓに含まれる画素をＦに追加し（ステップＳ１７１７），ｂｓをＮから削除してブロックｂｓに対する処理を終了する（ステップＳ１７２０）。
【００８６】
Ｉ（ｂｓ）が０の場合には，ブロックｂｓに含まれる各画素に対しての被写体識別子が未だ得られていない状況であるため，ブロックｂｓを分割してより小さなサブブロックを生成する。サブブロックの生成では，まず，ブロック分割を設定する（ステップＳ１７１８）。
【００８７】
ブロック分割の設定方法は，復号側と同じ方式であればどのような方法を用いて決定してもかまわない。例えば，予め定められた固定のブロック分割を設定する方法がある。具体的には，常に縦横それぞれを等分に分割して４つのサブブロックを生成するブロック分割を設定する方法がある。
【００８８】
また，画素群Ｆに対する被写体識別子の情報を用いて，可変のブロック分割を設定する方法もある。最も単純な方法としては，Ｆに含まれる画素群のうちブロックｂｓに隣接する画素群に対する被写体識別子を調べ，Ｆに含まれる隣り合う画素で被写体識別子が異なる部分にサブブロックの境界を設定する方法がある。具体的には，図９のようにＦの画素群に対して被写体識別子が割り振られていた場合には，図９右のようにブロック分割を設定する。このときサブブロックの個数も固定である必要はない。少し複雑な方法としては，Ｆに含まれる画素群における被写体識別子のエッジ情報を抽出し，そのエッジの向きに沿った形でブロック分割を設定する方法がある。具体的には，図１０で表されるようなブロック分割を設定する方法がある。
【００８９】
ブロック分割の設定が完了したら，そのブロック分割に従ってブロックｂｓを分割し，複数のサブブロックを生成する。このとき，生成されたサブブロックをラスタースキャン順やジグザグスキャン順などの予め定められた順にスキャンして，この順番でＮへ追加する（ステップＳ１７１９）。なお，ここではスキャンされたサブブロックをｂｓ１，ｂｓ２，…，ｂｓｋと表してある。なお，ｋは生成されたサブブロック数を表す。その後，ｂｓをＮから削除してブロックｂｓに対する処理を終了する（ステップＳ１７２０）。
【００９０】
被写体マップの符号化が終了したら，被写体マップと被写体画素値とを用いて，予測画像生成部１０８で，ブロックｂｌｋに対する予測画像を生成する（ステップＳ１０８）。具体的には，各画素に対して，被写体マップから得られる被写体識別子に対応する被写体画素値を割り当てることで予測画像を生成する。なお，被写体画素値を符号化して伝送する場合に，被写体画素値を量子化した後で符号化している場合には，量子化・逆量子化して復号側で得られる値を用いて予測画像を生成する必要がある。
【００９１】
なお，上記のように作られた予測画像に対して，さらにディザを加えてもかまわない。被写体マップと被写体画素値を用いた予測画像では，被写体数と同じ数の画素値しか存在しないため，自然画とは異なる性質をもつ画像となる。そのため，ディザを加えることでより自然画に近い変化を与えることができる。ディザ生成には任意の方法を用いることが可能であるが，復号側で同じものを発生できるようにする必要がある。初期化などのためにパラメータが必要な場合には，そのパラメータを符号化する必要がある。
【００９２】
予測画像が得られたら，画像信号符号化部１０９で，ブロックｂｌｋに対する画像信号を予測符号化する（ステップＳ１０９）。符号化にはどのような方法を用いてもかまわない。ＭＰＥＧ−２やＨ．２６４／ＡＶＣなどの一般的な符号化では，ブロックｂｌｋの画像信号と予測画像との差分信号に対して，ＤＣＴなどの周波数変換，量子化，２値化，エントロピー符号化を順に施すことで符号化を行う。
【００９３】
最後に，多重化部１１０で，被写体マップの符号データと，画像信号の符号データとを多重化して出力する（ステップＳ１１０）。被写体数や被写体画素値を符号化している際には，被写体数や被写体画素値に対する符号データも多重化する。なお，ここではブロックごとに多重化しているが，フレーム単位で多重化してもかまわない。ただし，その場合には，復号時に１フレーム分の符号データをバッファリングしてから復号する必要が生じる。
【００９４】
なお，特殊な状況として，被写体数が１の場合，被写体マップは１通りしか存在しないため，被写体マップ設定ステップはその唯一の被写体マップ候補を設定するだけでよく，被写体マップを符号化・多重化する必要はない。
【００９５】
被写体は空間的に大きさを持っているため，その存在と種類を示す被写体マップには空間的相関がある。本実施例では，各ブロックを符号化する際に使用した被写体マップを蓄積しておくことで，あるブロックの被写体マップを符号化する際に，周辺領域の被写体マップから予測を行うことで，空間的相関を利用して必要となる符号量を削減することが可能となる。
【００９６】
ブロックごとに異なる被写体数や被写体画素値を設定する場合，蓄積した被写体マップや符号化する被写体マップにおいて，同じ被写体が異なる被写体識別子を用いて表されていることがある。この場合，蓄積されている被写体マップをそのまま用いたのでは，符号化対象ブロックの被写体マップを正しく予測することができず，空間的相関を利用した符号量削減を実現することができない。
【００９７】
このような場合，被写体マップに加えて被写体画素値も蓄積しておき，ステップＳ１０６において参照被写体マップを設定する際に，各被写体マップに対応するブロックを符号化する際に使用した被写体画素値と符号化対象ブロックに対する被写体画素値を比較して，蓄積されている被写体マップの被写体識別子を，符号化対象ブロックに対して設定した被写体識別子へと変換し，変換された被写体マップを参照被写体マップとして設定する。これによって同一の被写体に対しては同じ被写体識別子で表された参照被写体マップを使用することが可能となり，空間的相関を利用して被写体マップの符号量を削減することができる。このときの画像符号化装置は，図１１で表される。
【００９８】
図１１に示す画像符号化装置１００−１において，図２の画像符号化装置１００と同符号のものは，図２で説明したものと同等の機能を持つ。被写体画素値記憶部１２０は，被写体画素値設定部１０４が設定した被写体画素値を記憶する。被写体マップ変換部１２１は，参照被写体マップを設定する際に，各被写体マップに対応するブロックを符号化する際に使用した被写体画素値と符号化対象ブロックに対する被写体画素値とを比較して，蓄積されている被写体マップの被写体識別子を，符号化対象ブロックに対して設定した被写体識別子へと置換する置換行列を生成し，参照領域を符号化する際に使用した被写体マップを置換行列に従って変換することで，参照被写体マップを生成する。
【００９９】
なお，被写体識別子を変換する方法は，復号側と同じであれば，任意の手法を用いることが可能である。例えば，最も単純な方法としては，周辺ブロックにおける各被写体画素値に対して，その値に最も近い符号化対象ブロックの被写体画素値を同定し，その周辺ブロックの被写体画素値に対する被写体識別子を，同定された被写体画素値に対する被写体識別子へと置換する方法がある。このときのステップＳ１０６における詳細な処理フローは図１２（Ａ）で表される。
【０１００】
まず，仮参照被写体マップを設定する（ステップＳ１６１）。次に，仮参照被写体マップ内の被写体識別子で表されている被写体と，被写体マップで使用されている被写体識別子との対応関係を同定する（ステップＳ１６２）。その後，対応関係に従って仮参照被写体マップを変換して参照被写体マップを生成する（ステップＳ１６３）。
【０１０１】
別の方法としては，周辺ブロックにおける被写体マップと被写体画素値とから周辺ブロックの予測画像を生成し，その予測画像の各画素に対して，その画素値に最も近い被写体画素値を持つ被写体識別子を割り当てることで生成する方法がある。このときのステップＳ１０６における詳細な処理フローは，図１２（Ｂ）で表される。
【０１０２】
まず，仮参照被写体マップを設定する（ステップＳ１６１′）。仮参照被写体マップに対する予測画像を復元する（ステップＳ１６２′）。上記予測画像とブロックｂｌｋの被写体画素値とから参照被写体マップを生成する（ステップＳ１６３′）。なお，この場合，被写体マップや被写体画素値の代わりに予測画像を蓄積しておくことで，予測画像を生成する処理を省略することが可能である。
【０１０３】
また，周辺ブロックには存在したが，符号化対象ブロックには存在しない被写体も存在する。そのため，対応する被写体画素値を同定する際に，その差が一定以内に収まるもののみを対象とし，対応する被写体画素値が求まらない場合には，符号化対象ブロックで使用されていない被写体識別子へと置換してもかまわない。これによってブロックごとに異なる被写体が存在していても，誤った予測によって符号化効率が低下してしまうのを防ぐことができる。
【０１０４】
Ｈ．２６４／ＡＶＣのように，多数存在する予測モードの中から，ブロックごとに最適な予測モードを選択して予測符号化を行う場合，符号化対象ブロックの周辺ブロックにおいて被写体マップを用いない予測モードが使われている可能性がある。そのような場合，被写体マップ記憶部１０６等には周辺ブロックに対する情報が蓄積されていないため，空間的相関を利用した符号量削減を実現することができない。
【０１０５】
このような場合，被写体マップを蓄積する代わりに，符号化結果を復号して得られる復号画像を蓄積しておき，周辺ブロックの復号画像の各画素に対して，その画素値に最も近い被写体画素値を持つ被写体識別子を割り当てることで参照被写体マップを生成する方法がある。これによって周辺ブロックの予測モードによらずに参照被写体マップを設定することが可能となり，空間的相関を利用して被写体マップの符号量を削減することができる。このときの画像符号化装置は，図１３で表される。
【０１０６】
図１３に示す画像符号化装置１００−２が，図２に示す画像符号化装置１００と違う点は，被写体マップ記憶部１０６の代わりに，画像信号復号部１３１と，復号画像メモリ１３２と，参照被写体マップ生成部１３３が用いられることである。画像信号復号部１３１は，画像信号符号化部１０９が符号化した符号化結果を復号し，復号画像を復号画像メモリ１３２に蓄積する。参照被写体マップ生成部１３３は，周辺ブロックの復号画像の各画素に対して，その画素値に最も近い被写体画素値を持つ被写体識別子を割り当てることで参照被写体マップを生成する。
【０１０７】
画像符号化装置１００−２の処理フローを，図１４に示す。図３に示す処理フローとの違い部分だけを説明する。ステップＳ１０５で被写体マップを生成した後，ステップＳ１１３にて，周辺ブロックの復号画像を参照して，被写体マップの符号化に用いる参照被写体マップを生成する。また，ステップＳ１０９で，画像信号を符号化した後，ステップＳ１１４で，画像信号復号部１３１が符号化結果を復号して復号画像メモリ１３２に蓄積する。
【０１０８】
〔第２実施形態：画像復号装置〕
次に，本発明の第２実施形態について説明する。図１５は，第２実施形態による画像復号装置の構成例を示すブロック図である。画像復号装置２００は，図１５に示すように，符号データ入力部２０１，符号データ記憶部２０２，分離部２０３，被写体数設定部２０４，被写体画素値設定部２０５，被写体マップ復号部２０６，被写体マップ記憶部２０７，予測画像生成部２０８，および画像信号復号部２０９を備えている。
【０１０９】
符号データ入力部２０１は，復号対象となる画像フレームの符号データを入力する。符号データ記憶部２０２は，入力された符号データを蓄積する。分離部２０３は，多重化された符号データを複数の異なる情報が符号化されている符号データへと分離する。被写体数設定部２０４は，予め定められた大きさの処理領域に含まれる被写体数を設定する。被写体画素値設定部２０５は，被写体ごとに被写体画素値を設定する。被写体マップ復号部２０６は，符号データから被写体マップを復号する。被写体マップ記憶部２０７は，復号された被写体マップを蓄積する。予測画像生成部２０８は，処理領域に対して得られた被写体画素値と被写体マップから，処理領域に対する予測画像を生成する。画像信号復号部２０９は，処理領域ごとに予測画像を用いて符号データから復号対象フレームの画像信号を復号する。
【０１１０】
図１６は，第２実施形態による画像復号装置２００の動作を説明するためのフローチャートである。このフローチャートに従って，画像復号装置２００の実行する処理について詳細に説明する。
【０１１１】
まず，符号データ入力部２０１より，復号対象フレームに対する符号データを入力し，符号データ記憶部２０２に格納する（ステップＳ２０１）。符号データの格納が終了したら，復号対象フレームを分割し，その領域ごとに，復号対象フレームの画像信号を復号する（ステップＳ２０２〜Ｓ２１１）。つまり，復号対象ブロックインデックスをｂｌｋ，総復号対象ブロック数をｎｕｍＢｌｋｓで表すとすると，ｂｌｋを０で初期化し（ステップＳ２０２），その後，ｂｌｋに１を加算しながら（ステップＳ２１０），ｂｌｋがｎｕｍＢｌｋｓになるまで（ステップＳ２１１），以下の処理（ステップＳ２０３〜Ｓ２０９）を繰り返す。
【０１１２】
復号対象ブロックごとに繰り返される処理では，まず，分離部２０３で，入力された符号データを複数の情報の符号データへと分離する（ステップＳ２０３）。本実施形態では，複数の情報の符号データがブロック単位でインターリーブされている例で説明しているが，フレームなど異なる単位でインターリーブされている場合には，この符号データの分離をブロック単位で繰り返す必要はない。
【０１１３】
符号データの分離が終了したら，次に，被写体数設定部２０４で，ブロックｂｌｋに含まれる被写体の数ｎｕｍＯｂｊｓを設定する（ステップＳ２０４）。被写体数は符号化側と同じ処理を用いて行う。例えば，符号化側で常に予め定められた数を設定している場合には，ここでも同じ数を設定する。
【０１１４】
別の例としては，ブロックごとに異なる被写体数を設定するために，被写体数が符号化され符号データに含まれている場合には，被写体数設定部２０４は，被写体数の符号データを受け取り，復号した結果の値を被写体数として設定する。
【０１１５】
図１７は，被写体数が符号化されている場合の画像復号装置のブロック図である。被写体数が符号化されている場合には，図１７に示すように，被写体数設定部２０４′は，分離部２０３で分離された被写体数の符号データを受け取り，それを復号して被写体数を取得する。なお，被写体数が，ブロックｂｌｋ周辺の処理済みのブロックに対する画素値や被写体数などの情報を用いて生成された予測値との差分値として符号化されている場合には，符号化側と同様の方法で予測を生成し，その値に符号データを復号して得られた値を加えて被写体数を取得する。
【０１１６】
なお，予測値の生成方法としては，ブロックｂｌｋの周辺のブロックを符号化する際に使用された被写体数の平均値または中央値を用いる方法や，ブロックｂｌｋの周辺の復号済み画素群の画素値を解析して，それらの画素群に存在する被写体数を予測値として用いる方法がある。別のブロック復号時の予測値生成のために，前者の方法では使用した被写体数を，後者の方法で復号画像の画素値を蓄積する必要がある。
【０１１７】
また，ブロックごとではなく，フレームやスライスと呼ばれる複数ブロックの集合ごとに被写体数が符号化されている場合もある。そのような場合には，フレームやスライス単位で一度だけ被写体数符号データを復号し，その結果を一時的に蓄積することで，次の更新のタイミングまで繰り返し同じ値を設定する。
【０１１８】
さらに，フレームまたはスライス単位でグローバルな被写体数が符号化され，ブロックごとにそこからの変化量が符号化されている場合もある。そのような場合には，フレームやスライス単位で一度だけグローバル被写体数符号データを復号し，その結果を一時的に蓄積し，その値にブロックごとに復号される変化量の値を加えて，そのブロックで用いる被写体数を得る。さらに，その変化量が隣接するブロックから予測されている場合には，ブロックごとに被写体変化量予測差分を復号し，その値にグローバル被写体数と隣接ブロックからの変化量の予測値とを加えることで，そのブロックで用いる被写体数を得る。
【０１１９】
被写体数の設定が終了したら，次に，被写体画素値設定部２０５で，ブロックｂｌｋ内の被写体ごとに１つの被写体画素値Ｖａｌｕｅ（ｉ）を設定する（ステップＳ２０５）。ここでｉは，被写体を識別するための被写体識別子とし，０以上ｎｕｍＯｂｊｓ未満の整数である。また，被写体識別子は予め定められた規則に従って割り当てる。ここでは，被写体画素値が小さい順に割り当てられているとする。被写体画素値は符号化側と同じ処理を用いて行う。例えば，符号化側で画素値の値域を被写体数で均一量子化し，各範囲の中央値を設定している場合には，ここでも同じ数を設定する。
【０１２０】
別の方法として，復号対象ブロック周辺の既に復号済みのブロックを復号する際に使用した被写体画素値を用いて設定する方法がある。具体的には，周辺ブロックで同じ被写体識別子に対して割り当てられた被写体画素値の平均値や中央値を，復号対象ブロックの被写体画素値として設定する方法や，周辺ブロックで使用された被写体画素値の集合を求めて，それをｎｕｍＯｂｊｓ個のクラスタへ分割し，各クラスタ内の平均値や中央値を，復号対象ブロックの被写体画素値として設定する方法がある。この場合，別のブロックを復号するときのために，使用した被写体画素値を蓄積していく必要がある。
【０１２１】
さらに別の方法として，復号対象ブロック周辺の既に復号済みの画素に対する画素値を用いて設定する方法がある。具体的には，復号対象ブロック周辺の既に復号済みの画素群を，前述のようなクラスタリング手法を用いて，ｎｕｍＯｂｊｓ個のクラスタに分割し，各クラスタに含まれる画素の画素値の平均値や中央値を，被写体画素値とする方法がある。この場合，別のブロックを復号するときのために，復号された画像の画素値を蓄積していく必要がある。
【０１２２】
さらに別の例としては，ブロックごとに異なる被写体画素値を設定するために，被写体画素値が符号化され符号データに含まれている場合がある。その場合には，被写体画素値設定部２０５は，被写体画素値の符号データを受け取り，復号した結果の値を被写体画素値として設定する。
【０１２３】
図１８は，被写体画素値が符号化されている場合の画像復号装置のブロック図である。被写体画素値が符号化されている場合には，図１８に示すように，被写体画素値設定部２０５′は，分離部２０３で分離された被写体画素値の符号データを受け取り，それを復号して被写体画素値を取得する。なお，被写体画素値が，ブロックｂｌｋ周辺の処理済みのブロックに対する画素値や被写体画素値などの情報を用いて生成された予測値との差分値として符号化されている場合には，符号化側と同様の方法で予測値を生成し，その値に符号データを復号して得られた値を加えて被写体画素値を取得する。なお，予測値の生成方法としては，ブロックｂｌｋの周辺のブロックを復号する際に使用された被写体画素値の平均値または中央値などを用いる方法や，ブロックｂｌｋの周辺の復号済み画素群の画素値を解析して，それらの画素群に対する被写体画素値を予測値として用いる方法がある。別のブロック復号時の予測値生成のために，前者の方法では使用した被写体画素値を，後者の方法で復号画像の画素値を蓄積する必要がある。
【０１２４】
被写体画素値の設定が終了したら，次に，被写体マップ記憶部２０７に蓄積されている復号対象ブロック周辺の既に復号済みのブロックを復号する際に使用した被写体マップを，参照被写体マップとして設定する（ステップＳ２０６）。参照被写体マップの選び方は，符号化側と同じ処理を用いる。例えば，予め定められた位置関係に存在するブロック群に対する被写体マップとして設定する。具体例としては，復号対象ブロックに対して上・左・左上に位置するブロックに対する被写体マップの集合を参照被写体マップとして設定する方法がある。なお，フレームやブロック群などの単位ごとに参照被写体マップの選び方を示す情報が符号化されている場合には，そのデータを復号して得られる情報に従って設定する。
【０１２５】
次に，設定した被写体参照マップを用いて，被写体マップ復号部２０６で，分離された符号データから被写体マップを復号する（ステップＳ２０７）。２次元情報の被写体マップは，ラスタースキャンやジグザグスキャンなどの画素スキャン順に各画素の被写体識別子が符号化されている場合と，四分木（クアッドツリー）や二分木（バイナリツリー）などの木構造のデータに変換した後に，深さ優先探索や幅優先探索による走査順に各ノードの情報が符号化されている場合がある。そのため，被写体マップの復号処理は，符号化時に用いられた方法に応じて異なる。
【０１２６】
ラスタースキャンやジグザグスキャンなどの画素スキャン順に各画素の被写体識別子が符号化されている場合の復号処理を，図１９のフローに従って詳しく説明する。ここでの処理は復号対象ブロック内の画素ごとに行われるため，復号対象ブロック内の画素のインデックスをｐｉｘ，復号対象ブロック内の画素数をｎｕｍＰｉｘｓで表すとすると，ｐｉｘを０で初期化し（ステップＳ２７０１），その後，ｐｉｘに１を加算しながら（ステップＳ２７０５），ｐｉｘがｎｕｍＰｉｘｓになるまで（ステップＳ２７０６），以下の処理（ステップＳ２７０２〜Ｓ２７０４）を繰り返す。
【０１２７】
画素ごとに繰り返される処理では，まず，画素ｐｉｘの周囲の画素群を参照画素群に設定し（ステップＳ２７０２），参照画素群に対する被写体識別子から，画素ｐｉｘの被写体識別子の予測値を生成する（ステップＳ２７０３）。予測値としては，１つの被写体識別子を生成する場合と，各被写体識別子の発生確率を生成する場合と，その両方を生成する場合があるが，符号化側と同じものを生成する。ここでの処理は，図５のフローのステップＳ１７０２およびステップＳ１７０３で符号化時に行われるものと同じである。
【０１２８】
予測値が生成されたら，その予測値を用いて画素ｐｉｘに対する被写体識別子を符号データから復号する（ステップＳ２７０４）。１つの予測被写体識別子が与えられた場合には，まず，その予測が正しいか否かを表すバイナリ情報を符号データから復号する。その結果，予測が正しいことが判明した場合には，予測値を画素ｐｉｘに対する被写体識別子とし，予測が正しくないことが判明した場合には，画素ｐｉｘに対する被写体識別子を符号データから復号する。発生確率が与えられた場合には，その確率に従って，画素ｐｉｘに対する被写体識別子を符号データから復号する。両方の情報が与えられた場合には，まず，その予測が正しいか否かを表すバイナリ情報を符号データから復号し，その後で，予測が正しいことが判明した場合には，予測値を画素ｐｉｘに対する被写体識別子とし，予測が正しくないことが判明した場合には，与えられた発生確率に従って，画素ｐｉｘに対する被写体識別子を符号データから復号する。具体的な復号処理は符号化処理に対した方法を用いる。なお，発生確率を符号化履歴に応じて可変にしながら算術符号化されている場合，画素ｐｉｘの被写体識別子の復号が終了したら，使用した確率テーブルを復号した被写体識別子に応じて更新する。更新方法は符号化時と同じ方法を用いることで正しく復号を行うことができる。
【０１２９】
被写体マップが木構造のデータに変換された後に，深さ優先探索の走査順に各ノードの情報が符号化されている場合の処理を，図２０のフローに従って詳しく説明する。なお，木構造のデータとは，ブロックｂｌｋをルートとして，各ノードの子ノードには，親ノードのブロックを分割した複数のサブブロックを対応させて，対応する領域の情報をノードに付与することで２次元の情報を表現したものである。木構造の定義には，任意のものを用いることが可能であるが，符号化側で用いた定義と同じものを用いる必要がある。
【０１３０】
木構造データへの変換を介して符号化された符号データを復号する処理では，復号対象ブロックから始めて，ブロックに対するノード情報を復号し，その復号されたノード情報に応じて，そのブロックを分割してサブブロックを生成し，サブブロックに対して同様の処理を再帰的に施すことで，被写体マップを復号する。つまり，未処理ブロックの集合をＮ，処理済み画素の集合をＦ，ブロックｂｌｋをｂ１と表すとすると，Ｎを｛ｂ１｝で，Ｆを参照被写体マップに含まれる画素の集合で初期化した後（ステップＳ２７１１），Ｎが空集合になるまで（ステップＳ２７２１），以下の処理（ステップＳ２７１２〜Ｓ２７２０）を繰り返す。
【０１３１】
Ｎが空集合になるまで繰り返される処理では，まず，Ｎから１つのブロックを取り出す（ステップＳ２７１２）。このとき，どのブロックを取り出すかは予め定められた規則に従って決定する。木の走査順を深さ優先探索とする場合には，ＬＩＦＯ（Last In First Out ），つまりスタックのように後から入ったものを先に取り出す。走査順を幅優先探索とする場合には，ＦＩＦＯ（First In First Out），つまりキューのように先に入ったものを先に取り出す。以下では，ここで取り出されたブロックをｂｓと表すものとする。なお，取り出す順序は，符号化時と同じ順序でなくてはならない。
【０１３２】
次に，画素群Ｆに対する被写体識別子の情報を用いて，ブロックｂｓに対する情報Ｉ（ｂｓ）の予測値または生起確率分布，またはその両方を生成する（ステップＳ２７１３）。本実施例では，ブロックｂｓ内のすべての画素の被写体識別子が同一な場合にはその被写体識別子の番号に１を足した数，そうでない場合には０をＩ（ｂｓ）とする。ここでの処理は，図６のフローのステップＳ１７１４で符号化時に行われるものと同じである。
【０１３３】
Ｉ（ｂｓ）の予測値や生起確率分布の生成が終了したら，それらの情報を用いて，Ｉ（ｂｓ）を符号データから復号する（ステップＳ２７１４）。ステップＳ２７１３において予測値を生成した場合には，まず予測値が正しいか否かを表すバイナリ情報を復号する。得られたバイナリ情報によって予測が正しいことが判明した場合には，予測値をＩ（ｂｓ）とする。得られたバイナリ情報によって予測が誤っていることが判明した場合には，Ｉ（ｂｓ）を符号データから復号する。なお，ステップＳ２７１３において生起確率分布を生成した場合には，Ｉ（ｂｓ）を復号する際に，その確率に従ってＩ（ｂｓ）をエントロピー復号する。具体的な復号処理は，符号化処理に対応した方法を用いる。なお，生起確率分布の生成を履歴に応じて可変にした符号化が行われている場合には，Ｉ（ｂｓ）の復号が終了したら，使用した確率テーブルを得られたＩ（ｂｓ）に応じて更新する。更新方法は符号化時と同じ方法を用いることで正しく復号を行うことができる。
【０１３４】
次に，復号して得られたＩ（ｂｓ）をチェックし，ブロックｂｓに複数の被写体が含まれているか否かをチェックする（ステップＳ２７１５）。木構造データの定義によってチェック方法は異なるが，ここではＩ（ｂｓ）が０であるか否かをチェックする。Ｉ（ｂｓ）が０でない場合には，被写体マップ上のブロックｂｓに含まれるすべての画素に被写体識別子Ｉ（ｂｓ）−１を割り当て（ステップＳ２７１６），ブロックｂｓに含まれる画素をＦに追加し（ステップＳ２７１７），ｂｓをＮから削除してブロックｂｓに対する処理を終了する（ステップＳ２７２０）。
【０１３５】
Ｉ（ｂｓ）が０の場合には，まず，ブロックｂｓの分割方法を設定する（ステップＳ２７１８）。分割方法の設定はどのように行ってもかまわないが，符号化時に行われるものと同じである必要がある。なお，ここでの処理は，図６のフローのステップＳ１７１８と同じである。ブロック分割の設定が完了したら，そのブロック分割に従ってブロックｂｓを分割し，複数のサブブロックを生成する。このとき，生成されたサブブロックをラスタースキャン順やジグザグスキャン順などの予め定められた順にスキャンして，この順番でＮへ追加する。この処理は，図６のフローのステップＳ１７１９と同じである。その後，ｂｓをＮから削除してブロックｂｓに対する処理を終了する（ステップＳ２７２０）。
【０１３６】
なお，ここで示した木構造の定義などは一例であり，符号化側と定義を共有することが可能であればどのような方法を用いてもかまわない。
【０１３７】
被写体マップの復号が終了したら，次に，予測画像生成部２０８で，ブロックｂｌｋに対する予測画像を生成する（ステップＳ２０８）。具体的には，各画素に対して，被写体マップから得られる被写体識別子に対応する被写体画素値を割り当てることで予測画像を生成する。
【０１３８】
なお，上記のように作られた予測画像に対して，さらにディザを加えてもかまわない。被写体マップと被写体画素値を用いた予測画像では，被写体数と同じ数の画素値しか存在しないため，自然画とは異なる性質をもつ画像となる。そのため，ディザを加えることで，より自然画に近い変化を与えることができる。ディザ生成には，任意の方法を用いることが可能であるが，符号化側と同じ手法を用いる必要がある。なお，符号データにディザ生成装置の初期化等に必要なパラメータが含まれている場合には，それを復号して用いる。
【０１３９】
予測画像が得られたら，画像信号復号部２０９で，ブロックｂｌｋに対する画像信号を復号する（ステップＳ２０９）。画像信号の復号は，符号化時に用いられた方法に応じて異なる。例えば，ＭＰＥＧ−２やＨ．２６４／ＡＶＣなどの一般的な符号化が用いられている場合には，符号データに対して，エントロピー復号，逆２値化，逆量子化，ＩＤＣＴなどの周波数逆変換を行うことで予測残差を復号し，その結果に予測画像を加えることでブロックｂｌｋの画像信号を復元する。
【０１４０】
特殊な状況として，被写体数が１の場合，被写体マップは１通りしか存在しないため，そのブロックに対する被写体マップを符号化しないことで符号量を削減している場合がある。そのような場合には，被写体マップ符号データを復号せずに，その唯一の被写体マップ候補を，そのブロックに対する被写体マップと設定するだけでよい。なお，被写体数が１の場合に，被写体マップを復号するか否かは，符号化時の処理と同じにする必要がある。
【０１４１】
ブロックごとに異なる被写体数や被写体画素値を用いて符号化されている場合，蓄積した被写体マップと復号する被写体マップとで，同じ被写体が異なる被写体識別子を用いて表されていたり，異なる被写体が同じ被写体識別子を用いて表されていることがある。この場合，蓄積した被写体マップをそのまま用いたのでは，復号対象ブロックの被写体マップを正しく予測することができない。
【０１４２】
このような場合，被写体マップに加えて被写体画素値も蓄積しておき，ステップＳ２０６において参照被写体マップを設定する際に，各被写体マップに対応するブロックを復号する際に使用した被写体画素値と復号対象ブロックに対する被写体画素値を比較して，蓄積されている被写体マップの被写体識別子を，復号対象ブロックに対して設定した被写体識別子へと変換し，変換された被写体マップを参照被写体マップとして設定する。これによって同一の被写体に対しては同じ被写体識別子で表された参照被写体マップを使用することが可能となり，空間的相関を利用して正しい予測を行うことが可能となる。このときの画像復号装置は，図２１で表される。
【０１４３】
図２１に示す画像復号装置２００−３では，被写体画素値記憶部２２０に，各被写体マップに対応するブロックを復号する際に使用した被写体画素値を蓄積しておき，被写体マップ変換部２２１は，被写体画素値記憶部２２０に蓄積している被写体画素値と，復号対象ブロックに対する被写体画素値とを比較して，蓄積されている被写体マップの被写体識別子を，復号対象ブロックに対して設定した被写体識別子へと変換する。すなわち，被写体マップ変換部２２１は，参照被写体マップを設定する際に，参照領域を復号する際に使用した被写体画素値と，処理領域に対して設定した被写体画素値とを比較して，蓄積されている被写体マップの被写体識別子を，復号対象ブロックに対して設定した被写体識別子へと置換する置換行列を生成し，参照領域を符号化する際に使用した被写体マップを置換行列に従って変換することで，参照被写体マップを生成する。他の構成は，前述した例と同様である。
【０１４４】
なお，被写体識別子を変換する方法は，符号化側と同じであれば，任意の手法を用いることが可能である。図１２に具体的な変換処理フローの例を示す。
【０１４５】
Ｈ．２６４／ＡＶＣのように，多数存在する予測モードの中から，ブロックごとに最適な予測モードを選択して予測符号化が行われている場合，復号対象ブロックの周辺ブロックにおいて被写体マップを用いない予測モードが使われている可能性がある。そのような場合，被写体マップ記憶部２０７等には，周辺ブロックに対する情報が蓄積されていないため，空間的相関を利用した符号量削減を実現することができない。
【０１４６】
このような場合，被写体マップを蓄積する代わりに，復号結果の復号画像を蓄積しておき，周辺ブロックの復号画像の各画素に対して，その画素値に最も近い被写体画素値を持つ被写体識別子を割り当てることで被写体マップを生成する方法がある。これによって周辺ブロックの予測モードによらず参照被写体マップを設定することが可能となり，空間的相関を利用した正しい予測を行うことができる。このときの画像復号装置は，図２２で表される。
【０１４７】
図２２に示す画像復号装置２００−４では，復号画像記憶部２３１に画像信号復号部２０９が復号した復号画像を蓄積しておき，参照被写体マップ設定部２３２が，周辺ブロックの復号画像の各画素に対して，その画素値に最も近い被写体画素値を持つ被写体識別子を割り当てることで，周辺ブロックの予測モードによらず参照被写体マップを設定する。他の部分は，前述した例と同様である。
【０１４８】
上述した第１，第２実施形態では，１フレーム中のすべてのブロックを本発明によって符号化および復号する処理を説明したが，一部のブロックにのみ適用し，その他のブロックでは，Ｈ．２６４／ＡＶＣなどで用いられる画面内予測符号化や動き補償予測符号化などを用いて符号化を行ってもかまわない。その場合には，ブロックごとにどの方法を用いて符号化したかを示す情報を符号化および復号する必要がある。
【０１４９】
上述した第１，第２実施形態では，１フレームを符号化および復号する処理を説明したが，複数フレーム繰り返すことで動画像符号化にも適用することができる。また，動画像の一部のフレームや一部のブロックにのみ適用することもできる。その場合，被写体の存在には空間的だけでなく時間的な連続性があることから，被写体マップの符号化に用いる参照画素や，被写体画素値の予測に用いる隣接ブロックの定義を，空間方向だけでなく時間方向にも拡張して用いることは容易に類推可能である。
【０１５０】
以上説明した画像符号化および画像復号の処理は，コンピュータとソフトウェアプログラムとによっても実現することができ，そのプログラムをコンピュータ読み取り可能な記録媒体に記録して提供することも，ネットワークを通して提供することも可能である。
【０１５１】
図２３に，画像符号化装置をコンピュータとソフトウェアプログラムとによって構成する場合のハードウェア構成例を示す。本システムは，プログラムを実行するＣＰＵ５０と，ＣＰＵ５０がアクセスするプログラムやデータが格納されるＲＡＭ等のメモリ５１と，カメラ等からの符号化対象の画像信号を入力する符号化対象フレーム入力部５２（ディスク装置等による画像信号を記憶する記憶部でもよい）と，第１実施形態として説明した画像符号化処理をＣＰＵ５０に実行させるソフトウェアプログラムである画像符号化プログラム５３１が格納されたプログラム記憶装置５３と，ＣＰＵ５０がメモリ５１にロードされた画像符号化プログラム５３１を実行することにより生成された多重化符号データを，例えばネットワークを介して出力する多重化符号データ出力部５４（ディスク装置等による多重化符号データを記憶する記憶部でもよい）とが，バスで接続された構成になっている。
【０１５２】
図示省略するが，他に，被写体数記憶部，被写体マップ記憶部，被写体画素値記憶部，予測画像記憶部，被写体マップ符号データ記憶部，画像情報符号データ記憶部，復号画像記憶部などのハードウェアが設けられ，本手法の実施に利用される。また，被写体画素値符号データ記憶部が用いられることもあり，さらに，被写体数符号データ記憶部，被写体数予測値記憶部，被写体画素値予測値記憶部，被写体識別子予測値記憶部，被写体生起確率分布記憶部，変換被写体マップ記憶部が用いられることもある。
【０１５３】
図２４に，画像復号装置をコンピュータとソフトウェアプログラムとによって構成する場合のハードウェア構成例を示す。本システムは，プログラムを実行するＣＰＵ６０と，ＣＰＵ６０がアクセスするプログラムやデータが格納されるＲＡＭ等のメモリ６１と，画像符号化装置が本手法により符号化した多重化符号データを入力する多重化符号データ入力部６２（ディスク装置等による多重化符号データを記憶する記憶部でもよい）と，第２実施形態として説明した画像復号処理をＣＰＵ６０に実行させるソフトウェアプログラムである画像復号プログラム６３１が格納されたプログラム記憶装置６３と，ＣＰＵ６０がメモリ６１にロードされた画像復号プログラム６３１を実行することにより，多重化符号データを復号して得られた復号画像データを，再生装置などに出力する復号画像データ出力部６４とが，バスで接続された構成になっている。
【０１５４】
図示省略するが，他に，被写体数記憶部，被写体マップ記憶部，被写体画素値記憶部，予測画像記憶部，被写体マップ符号データ記憶部，画像情報符号データ記憶部などのハードウェアが設けられ，本手法の実施に利用される。また，被写体画素値符号データ記憶部が用いられることもあり，さらに，被写体数符号データ記憶部，被写体数予測値記憶部，被写体画素値予測値記憶部，被写体識別子予測値記憶部，被写体生起確率分布記憶部，変換被写体マップ記憶部が用いられることもある。
【０１５５】
以上，図面を参照して本発明の実施の形態を説明してきたが，上記実施の形態は本発明の例示に過ぎず，本発明が上記実施の形態に限定されるものでないことは明らかである。したがって，本発明の精神および範囲を逸脱しない範囲で構成要素の追加，省略，置換，その他の変更を行っても良い。
【符号の説明】
【０１５６】
１００  画像符号化装置
１０１  符号化対象フレーム入力部
１０２  符号化対象フレーム記憶部
１０３，２０４  被写体数設定部
１０４，２０５  被写体画素値設定部
１０５  被写体マップ生成部
１０６，２０７  被写体マップ記憶部
１０７  被写体マップ符号化部
１０８，２０８  予測画像生成部
１０９  画像信号符号化部
１１０  多重化部
１２０，２２０  被写体画素値記憶部
１２１，２２１  被写体マップ変換部
１３１，２０９  画像信号復号部
１３２  復号画像メモリ
１３３  参照被写体マップ生成部
２０１  符号データ入力部
２０２  符号データ記憶部
２０３  分離部
２０６  被写体マップ復号部
２３１  復号画像記憶部
２３２  参照被写体マップ設定部
【図１】
0005357199.tif 000002
【図２】
0005357199.tif 000003
【図３】
0005357199.tif 000004
【図４】
0005357199.tif 000005
【図５】
0005357199.tif 000006
【図６】
0005357199.tif 000007
【図７】
0005357199.tif 000008
【図８】
0005357199.tif 000009
【図９】
0005357199.tif 000010
【図１０】
0005357199.tif 000011
【図１１】
0005357199.tif 000012
【図１２】
0005357199.tif 000013
【図１３】
0005357199.tif 000014
【図１４】
0005357199.tif 000015
【図１５】
0005357199.tif 000016
【図１６】
0005357199.tif 000017
【図１７】
0005357199.tif 000018
【図１８】
0005357199.tif 000019
【図１９】
0005357199.tif 000020
【図２０】
0005357199.tif 000021
【図２１】
0005357199.tif 000022
【図２２】
0005357199.tif 000023
【図２３】
0005357199.tif 000024
【図２４】
0005357199.tif 000025