(57)【要約】【課題】  オーバーラップする２つのセグメントの上下関係を入れ替えてリファレンス画像との誤差が最小になる組み合わせを探索する従来方法は、組み合わせ数が増加して誤差計算のコストが膨大になる。【解決手段】  侵食量算出部１２７は、セグメント貼り付け部１２６より出力されるオーバーラップ情報とセグメンテーション部１２２より出力されるリファレンス画像のセグメント情報を入力として受け、それらの互いの侵食量を求めて出力する。Ｚ−Ｏｒｄｅｒ決定部１２８は、入力侵食量に基づき、侵食画素数の少ない参照画像の画像セグメントが上に配置されるようにオーバーラップする画像セグメントの合成順序を決定する。これにより、参照画像から切り出したセグメントの形状とリファレンス画像から切り出したセグメントの形状が互いに異なる場合でも、簡便な検査方法で上下関係を決定できる。【選択図】            図２
2005123921.tif 000002
【特許請求の範囲】
【請求項１】
時間連続する２枚の２次元画像のうち時間的に過去の一方の２次元画像を参照画像とし、他方の２次元画像をリファレンス画像としたとき、前記参照画像から切り出した同じ特徴を持つ画素の集合である任意形状の第１の画像セグメントと、前記リファレンス画像から切り出した同じ特徴を持つ画素の集合である任意形状の第２の画像セグメントとの合成順序を決定する画像セグメントの合成順序決定装置であって、
前記第１の画像セグメントと前記第２の画像セグメントを、それぞれ前記参照画像及び前記リファレンス画像から別々に切り出すセグメンテーション手段と、
前記第１の画像セグメントと前記第２の画像セグメントに基づき、前記第１の画像セグメントを移動して前記リファレンス画像を近似するための、前記第１の画像セグメントの移動先を示す動きベクトルを検出する動きベクトル検出手段と、
前記第１の画像セグメントを前記動きベクトルに従って移動したときに、対応する前記第２の画像セグメントのセグメント境界を越えて少なくとも一部がオーバーラップする関係にある複数の前記第１の画像セグメントの隠蔽関係を示すオーバーラップ情報を生成するセグメント貼り付け手段と、
前記第１の画像セグメントを前記動きベクトルに従って移動したときに、前記第１の画像セグメントに対応する前記第２の画像セグメントのセグメント境界を越えて、前記隠蔽関係にある別の第１の画像セグメントに対応する別の第２の画像セグメント内にオーバーラップする部分が侵食する面積を、前記オーバーラップ情報に基づき前記隠蔽関係にある複数の第１の画像セグメントのそれぞれについて算出する侵食量算出手段と、
前記侵食量算出手段により算出された複数の前記面積のうち、少ない面積の前記第１の画像セグメントほど上に表示されるように、前記第１の画像セグメントの合成順序を決定する合成順序決定手段と
を有することを特徴とする画像セグメントの合成順序決定装置。
【請求項２】
時間連続する２枚の２次元画像のうち時間的に過去の一方の２次元画像を参照画像とし、他方の２次元画像をリファレンス画像としたとき、前記参照画像から切り出した同じ特徴を持つ画素の集合である任意形状の第１の画像セグメントと、前記リファレンス画像から切り出した同じ特徴を持つ画素の集合である任意形状の第２の画像セグメントとの合成順序を決定する画像セグメントの合成順序決定装置であって、
前記第１の画像セグメントと前記第２の画像セグメントを、それぞれ前記参照画像及び前記リファレンス画像から別々に切り出すセグメンテーション手段と、
前記第１の画像セグメントと前記第２の画像セグメントに基づき、前記第１の画像セグメントを移動して前記リファレンス画像を近似するための、前記第１の画像セグメントの移動先を示す動きベクトルを検出する動きベクトル検出手段と、
前記第１の画像セグメントを前記動きベクトルに従って移動したときに、対応する前記第２の画像セグメントのセグメント境界を越えて少なくとも一部がオーバーラップする関係にある複数の前記第１の画像セグメントの隠蔽関係を示すオーバーラップ情報を生成するセグメント貼り付け手段と、
前記第１の画像セグメントを前記動きベクトルに従って移動したときに、前記第１の画像セグメントに対応する前記第２の画像セグメントのセグメント境界を越えて、前記隠蔽関係にある別の第１の画像セグメントに対応する別の第２の画像セグメント内にオーバーラップする部分における該第１及び第２の画像セグメントの各画素の輝度値の絶対値誤差の和を、前記オーバーラップ情報に基づき前記隠蔽関係にある複数の第１及び第２の画像セグメントのそれぞれについて算出する誤差量算出手段と、
前記誤差量算出手段により算出された複数の前記絶対値誤差の和のうち、該絶対値誤差の和が少ない前記第１の画像セグメントほど上に表示されるように、前記第１の画像セグメントの合成順序を決定する合成順序決定手段と
を有することを特徴とする画像セグメントの合成順序決定装置。
【請求項３】
時間連続する２枚の２次元画像のうち時間的に過去の一方の２次元画像を参照画像とし、他方の２次元画像をリファレンス画像としたとき、前記参照画像から切り出した同じ特徴を持つ画素の集合である任意形状の第１の画像セグメントと、前記リファレンス画像から切り出した同じ特徴を持つ画素の集合である任意形状の第２の画像セグメントとの合成順序を決定する画像セグメントの合成順序決定装置をコンピュータにより実現させるためのプログラムであって、
前記コンピュータを、
前記第１の画像セグメントと前記第２の画像セグメントを、それぞれ前記参照画像及び前記リファレンス画像から別々に切り出すセグメンテーション手段と、
前記第１の画像セグメントと前記第２の画像セグメントに基づき、前記第１の画像セグメントを移動して前記リファレンス画像を近似するための、前記第１の画像セグメントの移動先を示す動きベクトルを検出する動きベクトル検出手段と、
前記第１の画像セグメントを前記動きベクトルに従って移動したときに、対応する前記第２の画像セグメントのセグメント境界を越えて少なくとも一部がオーバーラップする関係にある複数の前記第１の画像セグメントの隠蔽関係を示すオーバーラップ情報を生成するセグメント貼り付け手段と、
前記第１の画像セグメントを前記動きベクトルに従って移動したときに、前記第１の画像セグメントに対応する前記第２の画像セグメントのセグメント境界を越えて、前記隠蔽関係にある別の第１の画像セグメントに対応する別の第２の画像セグメント内にオーバーラップする部分が侵食する面積を、前記オーバーラップ情報に基づき前記隠蔽関係にある複数の第１の画像セグメントのそれぞれについて算出する侵食量算出手段と、
前記侵食量算出手段により算出された複数の前記面積のうち、少ない面積の前記第１の画像セグメントほど上に表示されるように、前記第１の画像セグメントの合成順序を決定する合成順序決定手段と
して機能させることを特徴とする画像セグメントの合成順序決定プログラム。
【請求項４】
時間連続する２枚の２次元画像のうち時間的に過去の一方の２次元画像を参照画像とし、他方の２次元画像をリファレンス画像としたとき、前記参照画像から切り出した同じ特徴を持つ画素の集合である任意形状の第１の画像セグメントと、前記リファレンス画像から切り出した同じ特徴を持つ画素の集合である任意形状の第２の画像セグメントとの合成順序を決定する画像セグメントの合成順序決定装置をコンピュータにより実現させるためのプログラムであって、
前記コンピュータを、
前記第１の画像セグメントと前記第２の画像セグメントを、それぞれ前記参照画像及び前記リファレンス画像から別々に切り出すセグメンテーション手段と、
前記第１の画像セグメントと前記第２の画像セグメントに基づき、前記第１の画像セグメントを移動して前記リファレンス画像を近似するための、前記第１の画像セグメントの移動先を示す動きベクトルを検出する動きベクトル検出手段と、
前記第１の画像セグメントを前記動きベクトルに従って移動したときに、対応する前記第２の画像セグメントのセグメント境界を越えて少なくとも一部がオーバーラップする関係にある複数の前記第１の画像セグメントの隠蔽関係を示すオーバーラップ情報を生成するセグメント貼り付け手段と、
前記第１の画像セグメントを前記動きベクトルに従って移動したときに、前記第１の画像セグメントに対応する前記第２の画像セグメントのセグメント境界を越えて、前記隠蔽関係にある別の第１の画像セグメントに対応する別の第２の画像セグメント内にオーバーラップする部分における該第１及び第２の画像セグメントの各画素の輝度値の絶対値誤差の和を、前記オーバーラップ情報に基づき前記隠蔽関係にある複数の第１及び第２の画像セグメントのそれぞれについて算出する誤差量算出手段と、
前記誤差量算出手段により算出された複数の前記絶対値誤差の和のうち、該絶対値誤差の和が少ない前記第１の画像セグメントほど上に表示されるように、前記第１の画像セグメントの合成順序を決定する合成順序決定手段と
して機能させることを特徴とする画像セグメントの合成順序決定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像セグメントの合成順序決定装置及び合成順序決定プログラムに係り、特にテレビ画像など時間的に連続する２次元画像を任意形状のセグメントに分割し、そのセグメントにより予測画像を生成する画像セグメントの合成順序決定装置及び合成順序決定プログラムに関する。
【背景技術】
【０００２】
従来、ディジタル記録装置やディジタル放送などに代表される画像高能率符号化方式として、ＭＰＥＧ２（Moving Picture Experts Group phase 2）方式が広く用いられている。このＭＰＥＧ２方式では、２次元画像をオーバーラップすることのない矩形領域に分割して符号化する。ここでは本発明と関係のあるフレーム間の予測符号化部を中心にこの矩形領域の処理方法を説明する。
【０００３】
フレーム間予測では前記矩形領域の画像に対して、時間的に前後する画像（以後、参照画像と表記）から画素値の誤差の少ない領域を予測値として選択し、選択された領域の位置を示す情報と選択された領域と実画像（以後、リファレンス画像と表記）との予測誤差か符号化される。
【０００４】
一例として、図１１（ａ）の画像を基に図１１（ｂ）の予測画像を作成することを考える。図１１（ａ）と同図（ｂ）は時間的に連続するフレームで、始めに円１ａと三角形２ａが図１１（ａ）に示すように互いに離れた位置関係にあり、次のフレーム（リファレンス画像）で図１１（ｂ）に１ｂで示すように円が三角形２ｂと重なった位置関係に移動したものとする。
【０００５】
この場合、まず、図１２（ｂ）に破線で示すように一定間隔で区切られた矩形状のブロックを作成する。このブロックが符号化される単位となる。なお、図１２（ａ）は図１１（ａ）と同一画像であり、図１１（ｂ）と図１２（ｂ）も同一画像である。次に、図１２（ｂ）のブロック３の予測値を図１２（ａ）の１フレーム前の画像中から探索する場合には、図１２（ａ）のブロック５やブロック６が予測候補となるが、誤差のより少ないブロック５が予測値として選択される。同様に、図１２（ｂ）のブロック４の予測値として、図１２（ａ）のブロック７やブロック８が考えられるが、より誤差の少ないブロック７が予測値として選択される。
【０００６】
以後、図１２（ｂ）の全ブロックに対して、上述の探索を行い、図１２（ｃ）に示すように、選択した前記ブロック５及び７を含む予測画像を得る。この予測画像を作成するための各ブロックのベクトル情報と、予測画像である図１２（ｃ）とリファレンス画像である図１２（ｂ）との予測誤差が、ＤＣＴ（Discrete Cosine Transform:離散コサイン変換）による直交変換や量子化の過程を経てハフマン符号など可変長符号化され符号器から出力される。復号化器では、前記ベクトル情報から予測画像を生成し、前記予測誤差を加えることで画像が復元される。
【０００７】
これに対して、セグメント単位の符号化技術が知られている。これは、画像中の同じ特徴量を持つ領域を任意形状に分割する方式である。特徴量とは、例えば輝度値や色、周波数などが挙げられる。このセグメント単位の符号化が前記のブロック単位の符号化と大きく異なる点は、予測画像の探索単位がブロックからセグメントに変わったことである。
【０００８】
このセグメントの探索手法の一例として、２フレーム間で前方（時間順）と後方（時間逆順）の両方向でセグメントのマッチングを取るセグメント探索法が知られている。このセグメント探索法により、セグメントの一部が隠蔽されていても、前方マッチングまたは後方マッチングのどちらかが成功するため、セグメント単位の動き補償が可能となる。
【０００９】
図１１の例にこのセグメント探索法を適用すると、図１１（ａ）と同一の画像を示す図１３（ａ）において、円１ａはその外周に沿って切り出され、図１３（ａ）中の三角形２ａもその外周に沿って切り出される。切り出された円１ａは図１３（ｂ）の円１ｃの位置に移動され、次いで三角形２ａが図１３（ｃ）の三角形２ｂのように円１ｃにオーバーラップするように配置される。この図１３（ｃ）が予測画像となる。
【００１０】
図１２（ｃ）の予測画像と図１３（ｃ）の予測画像から明らかなように、セグメント単位の符号化技術を用いた予測画像の方がリファレンス画像である図１１（ｂ）との予測誤差が少なくなる可能性がある。その理由の一つに、セグメントのオーバーラップが許可されている点がある。前記特許文献１では、このオーバーラップの上下関係（隠蔽関係）をＺオーダー（Ｚ−Ｏｒｄｅｒ）と呼んでいる。ただし、２つのセグメントのオーバーラップの上下関係には、図１４（ａ）に示すように円１ｃの上に三角形２ｂが貼り付けられる場合と、図１４（ｂ）に示すように三角形２ｂの上に円１ｃが貼り付けられる場合の２通りがある。前記特許文献１では、この上下関係を入れ替えながらリファレンス画像との誤差を計算し、誤差の少ない上下関係を選択する方法が開示されている。
【００１１】
【特許文献１】国際公開第０２／１３１２７号パンフレット
【発明の開示】
【発明が解決しようとする課題】
【００１２】
前記特許文献１では、セグメントを同じ動きをする画素の集まりとして定義しているが、厳密には１つのセグメントが剛体であることが必須であり、２フレーム間でセグメントの大きさや形が変化しないという前提条件に基づいている。しかし、実際の映像では被写体の移動により、撮影しているカメラから被写体までの距離の変化や新たな隠蔽が発生するため、被写体画像に関するセグメントの大きさや形が変化しないことは稀であり、前記特許文献１の技術をそのまま適用することはできない。セグメントの大きさや形が変化することを前提に予測画像を作成すると、リファレンス画像のセグメントとは異なる形状のセグメントを貼り付けなければならないからである。
【００１３】
従って、現実的に画像を扱おうとする場合には、リファレンス画像のセグメントとは大きさや形状の異なるセグメントを対象に上下関係（合成順序）を決定しなければならない。しかるに、前記特許文献１には、オーバーラップする２つのセグメントの上下関係を入れ替えてリファレンス画像との誤差が最小になる組み合わせを探索する発明が開示されているが、画像中のセグメントの大部分で形状変化が起こることを考慮すると、組み合わせ数が増加して誤差計算のコストが膨大になる。
【００１４】
本発明は上記の点に鑑みなされたもので、時間連続する２フレームのうち参照画像から切り出されたセグメントを用いて動き補償し、リファレンス画像と誤差の少ない予測画像を作ることにより、オーバーラップするセグメントの上下関係（隠蔽関係）を容易に、かつ、少ない計算量で判定して画像セグメントの合成順序を決定し得る画像セグメントの合成順序決定装置及び合成順序決定プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
上記の目的を達成するため、第１の発明の画像セグメントの合成順序決定装置は、時間連続する２枚の２次元画像のうち時間的に過去の一方の２次元画像を参照画像とし、他方の２次元画像をリファレンス画像としたとき、参照画像から切り出した同じ特徴を持つ画素の集合である任意形状の第１の画像セグメントと、リファレンス画像から切り出した同じ特徴を持つ画素の集合である任意形状の第２の画像セグメントとの合成順序を決定する画像セグメントの合成順序決定装置であって、第１の画像セグメントと第２の画像セグメントを、それぞれ参照画像及びリファレンス画像から別々に切り出すセグメンテーション手段と、第１の画像セグメントと第２の画像セグメントに基づき、第１の画像セグメントを移動してリファレンス画像を近似するための、第１の画像セグメントの移動先を示す動きベクトルを検出する動きベクトル検出手段と、第１の画像セグメントを動きベクトルに従って移動したときに、対応する第２の画像セグメントのセグメント境界を越えて少なくとも一部がオーバーラップする関係にある複数の第１の画像セグメントの隠蔽関係を示すオーバーラップ情報を生成するセグメント貼り付け手段と、第１の画像セグメントを動きベクトルに従って移動したときに、第１の画像セグメントに対応する第２の画像セグメントのセグメント境界を越えて、隠蔽関係にある別の第１の画像セグメントに対応する別の第２の画像セグメント内にオーバーラップする部分が侵食する面積を、オーバーラップ情報に基づき隠蔽関係にある複数の第１の画像セグメントのそれぞれについて算出する侵食量算出手段と、侵食量算出手段により算出された複数の面積のうち、少ない面積の第１の画像セグメントほど上に表示されるように、第１の画像セグメントの合成順序を決定する合成順序決定手段とを有する構成としたものである。
【００１６】
この発明では、参照画像の画像セグメント形状とリファレンス画像の画像セグメント形状とが異なる場合でも、侵食量（侵食面積）が小さい画像セグメントほど上に表示されるように決定できる。
【００１７】
また、上記の目的を達成するため、第２の発明の画像セグメントの合成順序決定装置は、第１の画像セグメントと第２の画像セグメントを、それぞれ参照画像及びリファレンス画像から別々に切り出すセグメンテーション手段と、第１の画像セグメントと第２の画像セグメントに基づき、第１の画像セグメントを移動してリファレンス画像を近似するための、第１の画像セグメントの移動先を示す動きベクトルを検出する動きベクトル検出手段と、第１の画像セグメントを動きベクトルに従って移動したときに、対応する第２の画像セグメントのセグメント境界を越えて少なくとも一部がオーバーラップする関係にある複数の第１の画像セグメントの隠蔽関係を示すオーバーラップ情報を生成するセグメント貼り付け手段と、第１の画像セグメントを動きベクトルに従って移動したときに、第１の画像セグメントに対応する第２の画像セグメントのセグメント境界を越えて、隠蔽関係にある別の第１の画像セグメントに対応する別の第２の画像セグメント内にオーバーラップする部分における第１及び第２の画像セグメントの各画素の輝度値の絶対値誤差の和を、オーバーラップ情報に基づき隠蔽関係にある複数の第１及び第２の画像セグメントのそれぞれについて算出する誤差量算出手段と、誤差量算出手段により算出された複数の絶対値誤差の和のうち、絶対値誤差の和が少ない第１の画像セグメントほど上に表示されるように、第１の画像セグメントの合成順序を決定する合成順序決定手段とを有する構成としたものである。
【００１８】
この発明では、参照画像の画像セグメント形状とリファレンス画像の画像セグメント形状とが異なる場合でも、オーバーラップする部分における第１及び第２の画像セグメントの各画素の輝度値の絶対値誤差の和が小さい画像セグメントほど上に表示されるように決定できる。
【００１９】
また、上記の目的を達成するため、第３の発明の画像セグメントの合成順序決定プログラムは、第１の発明の画像セグメントの合成順序決定装置をコンピュータにより実現させるためのプログラムであって、コンピュータを、
第１の画像セグメントと第２の画像セグメントを、それぞれ参照画像及びリファレンス画像から別々に切り出すセグメンテーション手段と、第１の画像セグメントと第２の画像セグメントに基づき、第１の画像セグメントを移動してリファレンス画像を近似するための、第１の画像セグメントの移動先を示す動きベクトルを検出する動きベクトル検出手段と、第１の画像セグメントを動きベクトルに従って移動したときに、対応する第２の画像セグメントのセグメント境界を越えて少なくとも一部がオーバーラップする関係にある複数の第１の画像セグメントの隠蔽関係を示すオーバーラップ情報を生成するセグメント貼り付け手段と、第１の画像セグメントを動きベクトルに従って移動したときに、第１の画像セグメントに対応する第２の画像セグメントのセグメント境界を越えて、隠蔽関係にある別の第１の画像セグメントに対応する別の第２の画像セグメント内にオーバーラップする部分が侵食する面積を、オーバーラップ情報に基づき隠蔽関係にある複数の第１の画像セグメントのそれぞれについて算出する侵食量算出手段と、侵食量算出手段により算出された複数の面積のうち、少ない面積の第１の画像セグメントほど上に表示されるように、第１の画像セグメントの合成順序を決定する合成順序決定手段として機能させることを特徴とする。
【００２０】
この発明では、参照画像の画像セグメント形状とリファレンス画像の画像セグメント形状とが異なる場合でも、侵食量（侵食面積）が小さい画像セグメントほど上に表示されるように決定できる。
【００２１】
更に、上記の目的を達成するため、第４の発明の画像セグメントの合成順序決定プログラムは、第２の発明の画像セグメントの合成順序決定装置をコンピュータにより実現させるためのプログラムとしたことを特徴とする。
【００２２】
この発明では、参照画像の画像セグメント形状とリファレンス画像の画像セグメント形状とが異なる場合でも、オーバーラップする部分における第１及び第２の画像セグメントの各画素の輝度値の絶対値誤差の和が小さい画像セグメントほど上に表示されるように決定できる。
【００２３】
上記の各発明では、第１の画像セグメントを動きベクトルに基づき移動して予測画像に貼り付けた際に、リファレンス画像をセグメンテーションして得られた第２の画像セグメントのセグメント境界からはみ出している部分が、周辺のどの画像セグメントに何画素侵食しているかを求める。前記操作を全ての画像セグメントで行い、オーバーラップしている２つの画像セグメントがお互いに侵食している画素数を比較し、侵食している画素数が少ない方を上の階層に決定する。前記侵食画素数の比較をオーバーラップしているセグメントについて全て求め、上下関係を調べることで第１の画像セグメントの合成順序が決定される。これは、同じ特徴（すなわち、同じような輝度値又は色差値）を持つ画素の集まりが画像セグメントであるため、侵食部分の１画素当りの誤差も略一様に同じ値になるので、
全誤差量＝（１画素の誤差）×（画素数）
と表せるからである。ここで、１画素の誤差とは、動きベクトルに基づき移動した後の侵食し合う２つの第１の画像セグメントの１画素あたりの輝度値の絶対値誤差である。
【００２４】
または、侵食部分の絶対値誤差の和の大小により第１の画像セグメントの合成順序を決定することもできる。この結果、第１乃至第４の発明によれば、画素数のカウントまたは絶対値誤差の和を求め比較するという簡便な方法でセグメント間の合成順序決定を実現することができる。
【発明の効果】
【００２５】
本発明によれば、参照画像から切り出した第１の画像セグメントの形状とリファレンス画像から切り出した第２の画像セグメントの形状が互いに異なる場合でも、侵食面積の比率、すなわち画素数の比率、または侵食部分のみの絶対値誤差の和という簡便な検査方法で上下関係（隠蔽関係）を決定できるので、任意形状符号化におけるオーバーラップ処理を低廉な計算コストで実現できる。
【発明を実施するための最良の形態】
【００２６】
次に、本発明を実施するための最良の形態について図面と共に説明する。図１は本発明になる画像セグメントの合成順序決定装置を含む画像高能率符号化装置（エンコーダ）の一例のブロック図を示す。この画像高能率符号化装置（エンコーダ）は、入力された時間的に連続する２フレームの２次元画像信号から予測画像を生成し、ハフマン符号や算術符号などによりセグメント形状情報、動きベクトル、画像セグメント（以下、単に「セグメント」ともいう）の合成順序を示すＺオーダー（Ｚ−Ｏｒｄｅｒ）情報及び、予測誤差を符号化して出力する。
【００２７】
ここでは、予め参照画像を構成するデータが符号化された後、出力端子１９から出力され復号化装置（デコーダ）に伝送されると共に、セグメント単位画像符号化装置（エンコーダ）内のローカルデコーダ１８にも入力され、復号化された参照画像信号がローカルデコーダ１８から出力されているものとして以下では説明する。
【００２８】
まず、入力端子１１から符号化されるべき２次元のリファレンス画像信号が入力される。この時間的に連続する入力リファレンス画像信号とローカルデコーダ１８から出力される参照画像信号は、本発明の画像セグメントの合成順序決定装置であるＺ−Ｏｒｄｅｒ決定器１２へそれぞれ入力される。Ｚ−Ｏｒｄｅｒ決定器１２は、時間的に連続する２フレームの画像信号（リファレンス画像信号及び参照画像信号）のうち、参照画像を任意形状の画像セグメントに分割した（切り出した）後、リファレンス画像から前記画像セグメントの移動先を示す動きベクトルを検出し、分割して得た前記画像セグメントを、検出した動きベクトルに従って移動する。
【００２９】
この際に、前記画像セグメント間でオーバーラップが発生する部分があれば上下関係を決定する（すなわち、画像セグメントの合成順序を決定する）。以上の処理により求められたセグメント形状情報が端子１３より出力されると共に、Ｚ−Ｏｒｄｅｒ情報が端子１４より出力され、さらに動きベクトル情報が端子１５より出力される。
【００３０】
次に、予測誤差器１６では、端子１３〜１５から入力される情報をもとに予測画像信号を生成した後、この生成した予測画像信号と入力端子１１より入力されるリファレンス画像信号との誤差を求めて、その予測誤差信号を可変長符号化器１７へ出力する。可変長符号化器１７では、端子１３〜１５から入力されるセグメント形状情報、動きベクトル、Ｚ−Ｏｒｄｅｒ情報及び、予測誤差器１６から入力される予測誤差信号をＤＣＴなどの公知の直交変換や量子化処理の後、ハフマン符号や算術符号などにより符号化する。
【００３１】
可変長符号化器１７から出力される符号化信号は出力端子１９から出力されると共に、ローカルデコーダ１８へ入力される。ローカルデコーダ１８では、可変長符号化器１７から入力された符号化信号を復号して、リファレンス画像信号を再構成する。この再構成されたリファレンス画像信号は、次の時間のリファレンス画像信号を符号化するための参照画像信号としてローカルデコーダ１８から出力され、Ｚ−Ｏｒｄｅｒ決定器１２へ入力される。
【００３２】
次に、本発明になる画像セグメントの合成順序決定装置を構成するＺ−Ｏｒｄｅｒ決定器１２の構成と動作について詳述する。図２は本発明になる画像セグメントの合成順序決定装置の一実施の形態のブロック図、図３は図２の一例の動作説明用フローチャートである。図２中、図１と同一構成部分には同一符号を付してある。図２において、本発明になる画像セグメントの合成順序決定装置を構成するＺ−Ｏｒｄｅｒ決定器１２の入力端子１１に入力された符号化されるべき２次元のリファレンス画像信号は、画像メモリ１２１により所定フレーム分蓄積された後セグメンテーション部１２２により画像セグメント単位に分割される。また、これと同時に、図１のローカルデコーダ１８から出力された参照画像信号は、図２の入力端子２０を介して画像メモリ１２３に供給されて所定フレーム分蓄積された後セグメンテーション部１２４により画像セグメント単位に分割される（以上、図３のステップＳ１）。
【００３３】
この際、セグメンテーション部１２４より出力されるセグメント情報は、符号化に用いるため出力端子１３より外部へ出力される。ここでは、本発明はセグメンテーションの方法とは独立して考えることができるので、その方法の詳細な説明は省略するが、例えば特開平１０−６９５４４号公報の公知の画像セグメント化方法などを用いることができる。
【００３４】
図４は本実施の形態を説明するための２枚の画像例であり、図４（ａ）は参照画像の一例、図４（ｂ）はリファレンス画像の一例を示す。図４（ａ）に示す参照画像は、セグメンテーション部１２４により四角形４１ａ、三角形４２ａ及び円４３ａの３つのセグメントに分割される。また、図４（ｂ）に示すリファレンス画像は、セグメンテーション部１２２により四角形４１ｂ、三角形４２ｂ及び円４３ｂの３つのセグメントに分割される。
【００３５】
次に、上記のステップＳ１で得られた参照画像のセグメントが、動きベクトル情報に基づいて移動される（図３のステップＳ２）。すなわち、このステップＳ２では、図２の動きベクトル検出部１２５にセグメンテーション部１２２、１２４より出力されるセグメント情報が入力され、動きベクトルが求められる。この動きベクトルの探索手法については本発明の要旨とは直接の関係はなく、また公知であるので詳細な説明は省略するが、例えば前記特許文献１に記載の方法などを利用できる。
【００３６】
動きベクトル検出部１２５で求められた動きベクトル情報は、出力端子１５より外部へ出力されると共に、セグメント貼り付け部１２６へ入力される。セグメント貼り付け部１２６は、動きベクトル検出部１２５より入力される動きベクトル情報に基づいて、セグメンテーション部１２４より入力される参照画像のセグメントを移動する。以上の処理が図３のステップＳ２である。
【００３７】
図４の例では、図４（ａ）の参照画像のセグメントを移動して図４（ｂ）のリファレンス画像のセグメントを近似する予測画像を作成することになる。すなわち、図４（ａ）に示す四角形４１ａを図４（ｂ）に示す四角形４１ｂへ、同図（ａ）の三角形４２ａを同図（ｂ）の三角形４２ｂへ、同図（ａ）の円４３ａを同図（ｂ）の円４３ｂの位置へ移動させる。実際の画像では、円４３ａに一部が隠蔽されていた三角形４２ａは、四角形４１ｂに一部隠蔽され、大きさの大きくなった三角形４２ｂとなっている。また、四角形４１ａは大きさが４１ｂに示すように小さくなり、三角形４２ｂの一部を隠蔽している。さらに三角形４２ａの一部を隠蔽していた円４３ａは、大きさも位置も変化なく単独で存在する円４３ｂとなる。
【００３８】
図５（ａ）は、図４（ａ）の参照画像をセグメンテーションした結果のセグメント境界を破線５１ａ、５２ａ、５３ａで示したものであり、図５（ｂ）は、図４（ｂ）のリファレンス画像をセグメンテーションした結果のセグメント境界を破線５１ｂ、５２ｂ、５３ｂで示したものである。動きベクトルにより生成される予測画像としては、図５（ｂ）の破線で示されるセグメント境界５１ｂ及び５２ｂの内部に図４（ａ）の四角形４１ａと三角形４２ａを配置した場合に、図６と図７の２通りの配置が考えられる。
【００３９】
すなわち、図６は四角形４１ａが４１ａ’に、三角形４２ａが４２ａ’で示すように、それぞれセグメント境界５１ｂ及び５２ｂの内部に配置されることにより、四角形４１ａ’が三角形４２ａ’の一部を隠蔽している場合である。一方、図７は四角形４１ａが４１ａ”に、三角形４２ａが４２ａ”で示すように、それぞれセグメント境界５１ｂ及び５２ｂの内部に配置されることにより、三角形４２ａ”により四角形４１ａ”の一部が隠蔽されている場合である。この隠蔽関係の存在をオーバーラップ情報として図２のセグメント貼り付け部１２６は出力する。
【００４０】
次に、図３のステップＳ２のセグメント移動により発生したオーバーラップする２つのセグメントを、対応するリファレンス画像のセグメント境界に基づき、お互いに侵食する画素数をカウントする（図３のステップＳ３）。すなわち、このステップＳ３において、図２の侵食量算出部１２７は、セグメント貼り付け部１２６より出力されるオーバーラップ情報とセグメンテーション部１２２より出力されるリファレンス画像のセグメント情報を入力として受け、それらの互いの侵食量を求めて出力する。ここで、侵食量とは、参照画像のセグメントを対応するリファレンス画像のセグメント境界内に嵌め込んだ時に、リファレンス画像のオーバーラップしている他のセグメントの領域にはみ出している面積をいう。
【００４１】
一例として、図４（ａ）の参照画像中の四角形４１ａと三角形４２ａの侵食画素数をカウントする操作を説明する。この場合、図３のステップＳ１で求めたリファレンス画像のセグメンテーション結果である図５（ｂ）の四角破線枠のセグメント境界５１ｂが、図４（ａ）の参照画像のセグメントの四角形４１ａに対応し、リファレンス画像のセグメンテーション結果である図５（ｂ）の三角破線枠のセグメント境界５２ｂが、図４（ａ）の参照画像のセグメントの三角形４２ａに対応している。
【００４２】
従って、四角形４１ａが三角破線枠のセグメント境界５２ｂへ侵食している画素数は、図８に示すように、四角破線枠のセグメント境界５１ｂと四角形４１ａの外枠６０の間に存在し、かつ、三角破線枠のセグメント境界５２ｂの内部に存在する領域６１の画素数となる。また、三角形４２ａが四角破線枠のセグメント境界５１ｂへ侵食している画素数は、図９に示すように、三角破線枠のセグメント境界５２ｂと三角形４２ａの外枠６２の間に存在し、かつ、四角破線枠のセグメント境界５１ｂの内部に存在する画素数であるが、図９から分かるようにこの場合の侵食画素はない。
【００４３】
最後に、図３のステップＳ３で求めた侵食画素数の少ない画像セグメントが上に配置されるように画像セグメントの合成順序であるＺ−Ｏｒｄｅｒを決定する（図３のステップＳ４）。すなわち、このステップＳ４において、図２のＺ−Ｏｒｄｅｒ決定部１２８は、侵食量算出部１２７より入力される侵食量に基づき、侵食画素数の少ない参照画像の画像セグメントが上に配置されるようにオーバーラップする画像セグメントの合成順序を決定し、決定したその画像セグメントの合成順序情報（Ｚ−Ｏｒｄｅｒ情報）を出力端子１４より外部へ出力する。
【００４４】
図８と図９の例では、三角形４２ａの侵食画素数（この場合は零画素）の方が少ないため、三角形４２ａが四角形４１ａの上に配置される図７に４２ａ”、４１ａ”で示す配置が予測画像として選択される。以上で、１組のオーバーラップする画像セグメントの合成順序（Ｚ−Ｏｒｄｅｒ）が求められる。この動作を全てのオーバーラップする画像セグメントについて行うことで、予測画像が完成する。
【００４５】
次に、本発明のオーバーラップする画像セグメントの上下関係を決定する他の手法について、図１０のフローチャートと共に説明する。ただし、図１０中、図３と同じ動作をするステップには同一の番号が付与されている。図中のステップＳ１とＳ２は上述しているので説明を省略する。本実施の形態では、図１０のステップＳ１１において図３のステップＳ３の画素数の代わりに、リファレンス画像との画素の絶対値誤差の和を求める点に特徴がある。すなわち、図８の侵食領域６１内にある四角形４１ａの画素の輝度値Ｙ（ｘ）と、図８の侵食領域６１内にある三角形４２ａの画素の輝度値Ｄ（ｘ）の絶対値誤差の和Ｅを次式により求める。
【００４６】
【数１】
2005123921.tif 000003
ただし、上式中、ｘは侵食領域６１の内部にある画素を示す値である。同様に、図９で三角形４２ａが四角形５１ｂに侵食している部分の絶対値誤差の和を求めるが、この例では零である。ここで、上記の数１の数式中、｜Ｙ（ｘ）−Ｄ（ｘ）｜は、ｘによらず略一定値になることが予想され、Ｑ＝｜Ｙ（ｘ）−Ｄ（ｘ）｜とすると、上式はＥ＝Ｑ・ｘと表すことができる。
【００４７】
次に、図１０のステップＳ１１で求めた侵食している領域の絶対値誤差の和の少ないセグメントを上に配置するようにＺ−Ｏｒｄｅｒを決定する（図１０のステップＳ１２）。ここで、例えばオーバーラップしている２つのセグメントＡ、Ｂのうち、Ａの１画素当りの輝度値をＰａ、ＢのそれをＰｂとすると、ＡがＢに侵食している部分の誤差はＱａ＝｜Ｐａ−Ｐｂ｜となり、ＢがＡに侵食している部分の誤差はＱｂ＝｜Ｐｂ−Ｐａ｜となるが、絶対値をとっているため、Ｑａ＝Ｑｂとなる。
【００４８】
一方、ＡがＢに侵食している部分の誤差量は、数１に基づき、Ｅａ＝Ｑａ・ｘａと表せ、同様に、ＢがＡに侵食している部分の誤差量はＥｂ＝Ｑｂ・ｘｂと表すことができる（ただし、ｘａ、ｘｂは、侵食している領域のセグメントＡ、Ｂの画素数）。ここで、上記のようにＱａ＝Ｑｂであるから、ＥａとＥｂの大小関係はｘａとｘｂの大小関係で決定される。従って、上記のステップＳ１２では、侵食している領域の絶対値誤差の和の少ないセグメントを上に配置するのである。なお、図１０の実施の形態では、演算量は増加するものの図３の実施の形態よりも正確な画像セグメントの合成順序を求めることが可能である。
【００４９】
なお、以上の実施の形態では２つの画像セグメントがオーバーラップしている様子で説明したが、本発明はこれに限定されるものではなく、例えば同じ領域に３つ以上の画像セグメントがオーバーラップしている場合でも、その中の２つの画像セグメントの組を選択しながら上下関係を決定することで本発明を適用できる。この場合、オーバーラップしている部分の侵食面積が小さいものほど上に表示されるような順序で画像セグメントが合成される。また、図１以外の構成のセグメント単位画像符号化装置にも本発明の適用は可能である。
【００５０】
また、本発明は、上記の装置の機能をコンピュータに実現させるためのコンピュータプログラムも含むものである。このコンピュータプログラムは、記録媒体から読み取られてコンピュータに取り込まれてもよいし、通信ネットワークからダウンロードしてコンピュータに取り込まれてもよい。
【図面の簡単な説明】
【００５１】
【図１】本発明の画像セグメントの合成順序決定装置を含む画像高能率符号化装置（エンコーダ）の一例のブロック図である。
【図２】本発明になる画像セグメントの合成順序決定装置の一実施の形態のブロック図である。
【図３】本発明によるオーバーラップするセグメントの上下関係の決定処理方法の一例の説明用フローチャートである。
【図４】参照画像とリファレンス画像の一例である。
【図５】セグメンテーション結果の一例の説明図である。
【図６】セグメント貼り付けによる予測画像の一例を説明する図である。
【図７】セグメント貼り付けによる予測画像の他の例を説明する図である。
【図８】侵食面積の一例の説明図である。
【図９】侵食面積の他の例の説明図である。
【図１０】本発明によるオーバーラップするセグメントの上下関係の決定方法の他の例のフローチャートである。
【図１１】予測画像を生成する過程を説明するための参照画像とリファレンス画像の一例である。
【図１２】ブロック単位符号化における予測画像の生成過程の説明図である。
【図１３】セグメント単位符号化における予測画像の生成過程の説明図である。
【図１４】セグメント単位符号化におけるセグメント貼り付け順の違いにより生成される予測画像の違いを説明する図である。
【符号の説明】
【００５２】
１１  リファレンス画像入力端子
１２  Ｚ−Ｏｒｄｅｒ決定器
１３、１４、１５、１９  出力端子
１６  予測誤差器
１７  可変長符号化器
１８  ローカルデコーダ
２０  参照画像入力端子
４１ａ、４１ｂ  四角形
４２ａ、４２ｂ  三角形    
４３ａ、４３ｂ  円
５１ａ、５１ｂ  四角破線枠のセグメント境界
５２ａ、５２ｂ  三角破線枠のセグメント境界
５３ａ、５３ｂ  円破線枠のセグメント境界
６０、６２  外枠
６１  画素の侵食領域
１２１、１２３  画像メモリ
１２２、１２４  セグメンテーション部
１２５  動きベクトル検出部
１２６  セグメント貼り付け部
１２７  侵食量算出部
１２８  Ｚ−Ｏｒｄｅｒ決定部
【図１】
2005123921.tif 000004
【図２】
2005123921.tif 000005
【図３】
2005123921.tif 000006
【図４】
2005123921.tif 000007
【図５】
2005123921.tif 000008
【図６】
2005123921.tif 000009
【図７】
2005123921.tif 000010
【図８】
2005123921.tif 000011
【図９】
2005123921.tif 000012
【図１０】
2005123921.tif 000013
【図１１】
2005123921.tif 000014
【図１２】
2005123921.tif 000015
【図１３】
2005123921.tif 000016
【図１４】
2005123921.tif 000017