(57)【要約】【課題】ごま塩雑音のようなノイズを低減すること。【解決手段】補間画像生成装置において、第１の動きベクトルによって定められる第１の参照画像上の第１のブロックと第２の参照画像上の第２のブロックにおける一致領域の内部の画素情報の分布に基づいた尤度を算出する尤度算出部１１３と、一致領域と不一致領域の空間分布の確率を示す事前確率を算出する事前確率算出部１１４と、尤度と事前確率から一致領域と不一致領域の分割の尤もらしさを示す事後確率を算出する事後確率算出部１１５と、事後確率が最大値を有する場合に、一致領域と不一致領域を尤もらしい領域分割であると判断する判断部１１６と、尤もらしい領域分割であると判断された場合に、第１の参照画像と第２の参照画像と第１の動きベクトルとから一致領域のみに基づいて動き補償を行い、補間画像を生成する動き補償部１２０とを備えた。【選択図】        図１
2006101032.tif 000002
【特許請求の範囲】
【請求項１】
動画像の第１参照画像と第２参照画像との間に内挿する補間画像を生成する補間画像生成装置であって、
前記第１の参照画像と前記第２の参照画像から第１の動きベクトルを求める動き探索手段と、
前記第１の参照画像内の所定サイズのブロックを、一致領域と不一致領域とに分割する領域分割手段と、
前記動き探索手段によって求められた前記第１の動きベクトルによって定められる前記第１の参照画像上の第１のブロックと前記第２の参照画像上の前記第２のブロックにおける前記一致領域の内部の画素情報の分布に基づいた尤度を算出する尤度算出手段と、
前記一致領域と前記不一致領域の空間分布の確率を示す事前確率を算出する事前確率算出手段と、
前記尤度算出手段によって算出された尤度と、前記事前確率算出手段によって算出された事前確率から、一致領域と不一致領域の分割の尤もらしさを示す事後確率をベイズの定理に基づいて算出する事後確率算出手段と、
前記事後確率算出手段によって算出された前記事後確率が最大値を有する場合に、前記領域分割手段によって分割した前記一致領域と前記不一致領域を、尤もらしい領域分割であると判断する判断手段と、
前記判断手段によって前記一致領域と前記不一致領域が尤もらしい領域分割であると判断された場合に、前記第１の参照画像と前記第２の参照画像と前記第１の動きベクトルとから前記一致領域のみに基づいて動き補償を行い、前記補間画像を生成する動き補償手段と、
を備えたことを特徴とする補間画像生成装置。
【請求項２】
前記動き探索手段は、前記判断手段によって前記一致領域と前記不一致領域が尤もらしい領域分割であると判断された場合に前記不一致領域のみに基づいて、第２の動きベクトルを求めることを特徴とする請求項１に記載の補間画像生成装置。
【請求項３】
前記尤度算出手段は、前記第１の参照画像上の第１のブロックと前記第２の参照画像上の前記第２のブロックにおける前記一致領域の画素差分のガウス分布に従った分布に基づいた尤度を算出することを特徴とする請求項１または２に記載の補間画像生成装置。
【請求項４】
前記尤度算出手段は、前記第１の参照画像上の第１のブロックと前記第２の参照画像上の前記第２のブロックにおける前記一致領域の画素差分の一般化ガウス分布に従った分布に基づいた尤度を算出することを特徴とする請求項３に記載の補間画像生成装置。
【請求項５】
前記事前確率算出手段は、前記一致領域と前記不一致領域の空間分布が集中している程高い確率を示す前記事前確率を算出することを特徴とする請求項１〜４のいずれか一つに記載の補間画像生成装置。
【請求項６】
前記事前確率算出手段は、前記一致領域の空間分布が前記不一致領域の空間分布より高い確率を示す前記事前確率を算出することを特徴とする請求項１〜５のいずれか一つに記載の補間画像生成装置。
【請求項７】
前記領域分割手段は、前記第１の参照画像内の所定サイズのブロックを、階層構造で一致領域と不一致領域とに分割することを特徴とする請求項１〜６のいずれか一つに記載の補間画像生成装置。
【請求項８】
前記領域分割手段は、前記第１の参照画像内の所定サイズのブロックを、ランダムに一致領域と不一致領域とに分割することを特徴とする請求項１〜７のいずれか一つに記載の補間画像生成装置。
【請求項９】
動画像の第１参照画像と第２参照画像との間に内挿する補間画像を生成する補間画像生成方法であって、
前記第１の参照画像と前記第２の参照画像から第１の動きベクトルを求める動き探索ステップと、
前記第１の参照画像内の所定サイズのブロックを、一致領域と不一致領域とに分割する領域分割ステップと、
前記動き探索ステップによって求められた前記第１の動きベクトルによって定められる前記第１の参照画像上の第１のブロックと前記第２の参照画像上の前記第２のブロックにおける前記一致領域の内部の画素情報の分布に基づいた尤度を算出する尤度算出ステップと、
前記一致領域と前記不一致領域の空間分布の確率を示す事前確率を算出する事前確率算出ステップと、
前記尤度算出ステップによって算出された尤度と、前記事前確率算出ステップによって算出された事前確率から、一致領域と不一致領域の分割の尤もらしさを示す事後確率をベイズの定理に基づいて算出する事後確率算出ステップと、
前記事後確率算出ステップによって算出された前記事後確率が最大値を有する場合に、前記領域分割ステップによって分割した前記一致領域と前記不一致領域を、尤もらしい領域分割であると判断する判断ステップと、
前記判断ステップによって前記一致領域と前記不一致領域が尤もらしい領域分割であると判断すると判断された場合に、前記第１の参照画像と前記第２の参照画像と前記第１の動きベクトルとから前記一致領域のみに基づいて動き補償を行い、前記補間画像を生成する動き補償ステップと、
を含むことを特徴とする補間画像生成方法。
【請求項１０】
動画像の第１参照画像と第２参照画像との間に内挿する補間画像を生成する補間画像生成プログラムであって、
前記第１の参照画像と前記第２の参照画像から第１の動きベクトルを求める動き探索手順と、
前記第１の参照画像内の所定サイズのブロックを、一致領域と不一致領域とに分割する領域分割手順と、
前記動き探索手順によって求められた前記第１の動きベクトルによって定められる前記第１の参照画像上の第１のブロックと前記第２の参照画像上の前記第２のブロックにおける前記一致領域の内部の画素情報の分布に基づいた尤度を算出する尤度算出手順と、
前記一致領域と前記不一致領域の空間分布の確率を示す事前確率を算出する事前確率算出手順と、
前記尤度算出手順によって算出された尤度と、前記事前確率算出手順によって算出された事前確率から、一致領域と不一致領域の分割の尤もらしさを示す事後確率をベイズの定理に基づいて算出する事後確率算出手順と、
前記事後確率算出手順によって算出された前記事後確率が最大値を有する場合に、前記領域分割手順によって分割した前記一致領域と前記不一致領域を、尤もらしい領域分割であると判断する判断手順と、
前記判断手順によって前記一致領域と前記不一致領域が尤もらしい領域分割であると判断すると判断された場合に、前記第１の参照画像と前記第２の参照画像と前記第１の動きベクトルとから前記一致領域のみに基づいて動き補償を行い、前記補間画像を生成する動き補償手順と、
をコンピュータに実行させる補間画像生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画像の第１参照画像と第２参照画像との間に内挿する補間画像を生成する補間画像生成装置、補間画像生成方法および補間画像生成プログラムに関する。
【背景技術】
【０００２】
動画像を滑らかに表示するために、動画像のフレーム間に画像を内挿補間するフレーム補間方法が利用される。このフレーム補間方法としては、次のような手法がある。
【０００３】
まず、補間フレームを一様格子の補間対象ブロックに分割し、この補間対象ブロックを中心として幾何対称的に２つの参照フレーム間の相関を算出して動きベクトルを求める。そして、フレーム間の相関、すなわち２つの参照フレーム間の画素値の差分絶対値が一定の閾値以下か否かを判断し、ブロック内で一定の閾値以下の画素の領域を一致領域とし、一定の閾値より大きい画素の領域を不一致領域として、二つの領域に分割する。そして、一致領域には該動きベクトルを割り当て、不一致領域は再帰的に探索をおこない、補間フレームの画像を生成する手法である（例えば、特許文献１参照）。
【０００４】
この特許文献１の技術によれば、フレームを一致領域と不一致領域に分割して、各領域で異なる手法で動きベクトルを求めているので、補間フレームに重なりや隙間が生じず、ブロック内に複数の動きが存在してもブロック歪みが発生しないという利点がある。
【０００５】
【特許文献１】特開２００４−１０４６６６号公報（図１５，図１６参照）
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、特許文献１の技術では、一致領域と不一致領域に分割する際に、画素ごとに、２つの参照フレーム間の画素値の差分絶対値を算出し、差分絶対値によって、一致領域に属するか不一致領域に属するかを判定しているため、画面全体に対して非常に微細なレベルでの一致判定を行っている。
【０００７】
実際に、動画を大域的なレベルで観察するとフレーム間で非常に近似しているように観察される部分でも、微細な画素レベルではフレーム間で大きく異なっている場合がある。このような場合に、画素レベルの一致判定の結果と、大域的なレベルな一致判定の結果は必ずしも一致しない。
【０００８】
このため、画素レベルでの一致判定を行って補間フレームを生成した場合には、動画を画面全体から観察したときに、実際の動作とは異なる動作に観察されてしまう場合がある。すなわち、画像にノイズが少ない理想的な場合には、領域分割によりブロック歪みを低減することができるが、ノイズが多い画像の場合には、補間フレームにノイズにより本来と異なる画素値が入ることによって、ごま塩雑音のようなノイズとして視認されてしまうという問題がある。
【０００９】
本発明は、上記に鑑みてなされたものであって、ごま塩雑音のようなノイズを低減するとともに、ブロック歪みを低減して動画像を滑らかに表示することができる補間画像生成装置、補間画像生成方法および補間画像生成プログラムを提供することである。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するために、本発明は、動画像の第１参照画像と第２参照画像との間に内挿する補間画像を生成する補間画像生成装置であって、前記第１の参照画像と前記第２の参照画像から第１の動きベクトルを求める動き探索手段と、前記第１の参照画像内の所定サイズのブロックを、一致領域と不一致領域とに分割する領域分割手段と、前記動き探索手段によって求められた前記第１の動きベクトルによって定められる前記第１の参照画像上の第１のブロックと前記第２の参照画像上の前記第２のブロックにおける前記一致領域の内部の画素情報の分布に基づいた尤度を算出する尤度算出手段と、前記一致領域と前記不一致領域の空間分布の確率を示す事前確率を算出する事前確率算出手段と、前記尤度算出手段によって算出された尤度と、前記事前確率算出手段によって算出された事前確率から、一致領域と不一致領域の分割の尤もらしさを示す事後確率をベイズの定理に基づいて算出する事後確率算出手段と、前記事後確率算出手段によって算出された前記事後確率が最大値を有する場合に、前記領域分割手段によって分割した前記一致領域と前記不一致領域を、尤もらしい領域分割であると判断する判断手段と、前記判断手段によって前記一致領域と前記不一致領域が尤もらしい領域分割であると判断された場合に、前記第１の参照画像と前記第２の参照画像と前記第１の動きベクトルとから前記一致領域のみに基づいて動き補償を行い、前記補間画像を生成する動き補償手段と、を備えたことを特徴とする。
【００１１】
また、本発明は、上記補間画像生成装置に対応した補間画像生成方法および補間画像生成プログラムである。
【発明の効果】
【００１２】
本発明によれば、第１の動きベクトルによって定められる第１の参照画像上の第１のブロックと第２の参照画像上の第２のブロックにおける一致領域の内部の画素情報の分布に基づいた尤度を算出し、一致領域と不一致領域の空間分布の確率を示す事前確率を算出し、算出された尤度と算出された事前確率から、一致領域と不一致領域の領域分割の尤もらしさを示す事後確率をベイズの定理に基づいて算出し、算出された事後確率が最大値を有する場合に、分割した前記一致領域と不一致領域を尤もらしい領域分割であると判断し、一致領域と不一致領域が尤もらしい領域分割であると判断された場合に、第１の参照画像と第２の参照画像と第１の動きベクトルとから一致領域のみに基づいて動き補償を行い、補間画像を生成することで、画素毎での一致判定を行う必要がなくなり、より確からしい手法で一致領域と不一致領域を分割することができるので、ごま塩雑音のようなノイズを低減するとともに、ブロック歪みを低減して動画像を滑らかに表示することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１３】
以下に添付図面を参照して、この発明にかかる補間画像生成装置、補間画像生成方法および補間画像生成プログラムの最良な実施の形態を詳細に説明する。
【００１４】
（実施の形態１）
実施の形態１にかかる補間画像生成装置は、動画像の第１の参照フレームｐ１（第１の参照画像）と第２の参照フレームｐ２（第２の参照画像）との間に内挿する補間フレームの画像を生成する際に、参照フレームｐ１内の所定サイズのブロックを、一致領域と不一致領域とに分割し、領域分割が尤もらしい領域分割か否かを、ベイズ決定規定の概念を用いてＭＡＰ（maximum a posteriori probability）推定問題として定式化したものである。ここで、一致判定問題は、動き推定によって求められた動きベクトルによって定まるブロック対の中を一致領域と不一致領域に分割する問題である。
【００１５】
まず、本実施の形態の補間画像生成装置で行われる一致判定処理で利用するベイズ決定規定について説明する。
【００１６】
ベイズ決定規定は、統計的パターン認識の確率モデルに基づいている。一般的に、ｍ個の類をｃ1，ｃ2，・・・ｃmとし、入力パターンから抽出されたｎ個の特徴の値の組（特徴ベクトル）を、ｘ＝（ｘ1，ｘ2，・・・ｘn）とすると、各類に属するパターンが生起する確率（事前確率）ｐ（ｃi）（ｉ＝１，・・・，ｍ）と、各類ｃiのもとで、パターンｘの生起確率ｐ（ｘ｜ｃi）（ｉ＝１，・・・，ｍ）が知られているものとする。このとき、ｘが生起したという条件のもとで事後確率を最大とする類ｃk、すなわち、次式
ｐ（ｃk｜ｘ）＝ｍａｘｐ（ｃi｜ｘ）
を満たす類ｃkにパターンｘは属すると決定すれば、全体的な識別の誤り確率が最小になることがわかっているという規則がベイズ決定規則である。
【００１７】
本実施の形態の補間画像生成装置では、このベイズ決定規則を、一致判定に利用している。すなわち、一致領域と不一致領域が、入力された画像に対してどの程度尤もらしいかを事後確率（posteriori probability）として定式化している。
【００１８】
ベイズ決定規則では、事後確率は、尤度と事前確率の積で表現される。事前確率は、一致領域と不一致領域の空間分布の確率を示すものとして定式化する。尤度は、観測されるノイズがガウス分布に従うと仮定して、一致領域内のブロック差分をガウス分布としてモデル化する。このようにノイズも考慮に入れて定式化を行うことによってノイズに対してロバスト性を向上させて領域の一致判定をおこなうことができる。
【００１９】
ここで、ｙa，ｙbをブロックＢの画素値、ｘを一致領域、不一致領域を示すラベルとする。すなわち、ｘ＝１が一致領域のラベル、ｘ＝０が不一致領域のラベルである。ＭＡＰ推定問題は、画像ｙが与えられたときの一致判定ｘの確率（事後確率）ｐ（ｘ｜ｙ）を最大化する問題である。ベイス決定規則から、事前確率ｐ（ｘ）と、一致判定ｘが与えられたときのｙの尤度ｐ（ｙ｜ｘ）には、数１式に示す関係がある。
【００２０】
【数１】
2006101032.tif 000003
【００２１】
事前確率ｐ（ｘ）は、局所的に０（不一致領域）と１（一致領域）が交互に繰り返される空間分布、すなわち０（不一致領域）と１（一致領域）が分散している場合に確率的に低くなり、さらに０（不一致領域）の空間分布よりも１（一致領域）の空間分布の方が確率的に高いと定められ、数２式のように定式化される。
【００２２】
【数２】
2006101032.tif 000004
【００２３】
ここで、β、ｃはブロック内の隣接画素の２点であるクリークであり、Ｚは正規化定数である。図２４は、ブロック内の隣接画素の２点であるクリークの一例を示す説明図である。
【００２４】
尤度ｐ（ｙ｜ｘ）は、他の条件が同一の場合には、値が大きい程、条件ｘの元でより尤もらしいことを示す。本実施の形態では、尤もらしさを画素の差分によって表している。よって、一致判定ｘが与えられたときに、一致領域内の差分値が小さいほど、ｐ（ｙ｜ｘ）の値が大きくなり、より尤もらしいとする。
【００２５】
画像で観測されるノイズが、分散σ2、平均０の白色ガウスノイズであるとすると、尤度は数３式のようにモデル化することができる。
【００２６】
【数３】
2006101032.tif 000005
【００２７】
なお、本実施の形態では、ノイズがガウス分布に従うとして尤度のモデル化を行ったが、この他、一般化ガウス分布やポアソン分布に従うとして尤度のモデル化を行っても良い。
【００２８】
数３式のように尤度をモデル化した場合に、ＭＡＰ推定問題が、数４式に示すように定式化することができる。
【００２９】
【数４】
2006101032.tif 000006
ここで数４式の対数を取って、数５式のように定式化してもよい。
【数５】
2006101032.tif 000007
【００３０】
上記数４式（若しくは数５式）を解法して一致判定ｘを算出することにより、ベイズ決定規則のもとでの一致判定を行うことができる。言い換えれば、本実施の形態の補間画像生成装置では、数２式で示される事前確率を求め、数３式で示される尤度を求め、かかる事前確率と尤度とを乗算した数４式で示される事後確率が最大値になる一致判定ｘを求めている。
【００３１】
次に、このようなヘイズ決定規則を利用した一致判定をおこない補間フレームを生成する本実施の形態にかかる補間画像生成装置について説明する。
【００３２】
なお、本実施の形態では、入力画像信号（動画像信号）が６０Ｈｚのノンインタレース信号（プログレッシブ信号）であり、６０Ｈｚのノンインタレース信号に対して隣接する二つの参照フレーム間の時間的中央位置（補間フレーム面）に補間フレームを生成し、その補間フレームを二つの参照フレーム間に内挿することにより１２０Ｈｚのノンインタレース信号に変換する場合を例にとって説明する。また、時間的に先の参照フレームを参照フレームｐ１、時間的に後の参照フレームを参照フレームｐ２とする。ただし、本発明は、上記画像信号に限定されるものではなく、様々なフレームレートの画像信号に対して本発明を適用することができる。
【００３３】
図１は、実施の形態１にかかる補間画像生成装置の機能的構成を示すブロック図である。本実施の形態にかかる補間画像生成装置１００は、図１に示すように、動き推定部１１０と動き補償部１２０とフレームメモリ１３０とを備えている。
【００３４】
動き推定部１１０は、入力される２つの参照フレームｐ１、ｐ２を格子状のブロックに分割して分割されたブロックを一致領域と不一致領域に分割して、各領域で動きベクトルを求めるものである。
【００３５】
動き推定部１１０は、図１に示すように、動き探索部１１１と、領域分割部１１２と、尤度算出部１１３と、事前確率算出部１１４と、事後確率算出部１１５と、判断部１１６とを備えている。
【００３６】
動き探索部１１１は、２つの参照フレームｐ１、ｐ２を入力して、一様格子のブロックごとに第１の動きベクトルを求める処理を行う。また、動き探索部１１１は、後述する判断部１１６によって一致領域と不一致領域が尤もらしい領域分割であると判断された場合に、さらに不一致領域のみに基づいて第２の動きベクトルを求める処理を行う。
【００３７】
領域分割部１１２は、参照フレームｐ１，ｐ２内のブロックを、一致領域と不一致領域とに分割する処理を行う。また、領域分割部１１２は、尤度算出部１１３、事前確率算出部１１４、事後確率算出部１１５、判断部１１６とともに、分割された一致領域と不一致領域についての一致判定処理を行う。
【００３８】
尤度算出部１１３は、動き探索部１１１によって求めた第１の動きベクトルによって定められる参照フレームｐ１のブロックと参照フレームｐ２上のブロックにおける一致領域の内部の画素値の差分のガウス分布に基づいた尤度ｐ（ｙ｜ｘ）を数３式に従って算出する処理を行う。この尤度は、画素の差分によって表され、一致判定ｘが与えられたときに、一致領域内の差分値が小さいほど、尤度ｐ（ｙ｜ｘ）の値が大きくなり、より尤もらしいことを意味する。
【００３９】
事前確率算出部１１４は、一致領域と不一致領域の空間分布の確率を示す事前確率ｐ（ｘ）を数２式に従って算出する処理を行う。この事前確率ｐ（ｘ）は、不一致領域と一致領域が分散している空間分布の場合には低い値となり、さらに不一致領域の空間分布よりも一致領域の空間分布の方が高い値となるように数３式で設定される。
【００４０】
事後確率算出部１１５は、尤度算出部１１３によって算出された尤度と事前確率算出部１１４によって算出された事前確率とを乗算し、一致領域と不一致領域の分割の尤もらしさを示す事後確率ｐ（ｘ｜ｙ）を数４式に従って算出する処理を行う。
【００４１】
判断部１１６は、事後確率ｐ（ｘ｜ｙ）が最大値を有するか否かを判定し、最大値となる場合に、領域分割部１１２によって分割した一致領域と不一致領域を、尤もらしい領域分割であると判断する一致判定処理を行うものである。
【００４２】
動き補償部１２０は、判断部１１６によって一致領域と不一致領域が尤もらしい領域分割であると判断された場合に、参照フレームｐ１，ｐ２と動き探索部１１１で求めた第１の動きベクトルとから一致領域のみに基づいて動き補償を行い、補間フレームを生成する処理を行う。フレームメモリ１３０は、参照フレームの画像を一時的に保存する記憶装置である。
【００４３】
次に、以上のように構成された補間画像生成装置１００による補間画像生成処理について説明する。図２は、補間画像生成の全体処理の手順を示すフローチャートである。
【００４４】
まず、動き探索部１１１は、補間フレームを一様格子の小ブロックｂｌ０に分割し（ステップＳ２０１）、ブロックの走査を開始する（ステップＳ２０２）。そして、動き推定を行い、ブロック内の一致領域となる動きベクトルグループｍｖｇと不一致フィルタグループａｆｇを求める（ステップ２０３）。ここで、かかる動き推定処理については後述する。
【００４５】
次に、動きベクトルグループｍｖｇ、不一致フィルタグループａｆｇ、参照フレームｐ１，参照フレームｐ２から動き補償処理を行い、補間フレームを生成をする（ステップＳ２０４）。かかる動き補償処理については後述する。そして、小ブロックｂｌ０をすべて走査するまで、ステップＳ２０３およびＳ２０４の処理を繰り返し、小ブロックｂｌ０をすべて走査した場合には処理を完了する（ステップＳ２０５）。
【００４６】
次に、ステップＳ２０２における動き推定処理について説明する。図３は、動き推定処理の手順を示すフローチャートである。
【００４７】
動き推定処理では、参照フレームｐ１、ｐ２の探索領域からもっとも相関度の高いブロックを探索し、第１の動きベクトルを求め（動き探索処理）、探索されたブロック対である小ブロックｂｌ１，ｂｌ２の内部において一致・不一致を判定し不一致フィルタａｆを求め（一致判定処理）、不一致画素のみから再帰的に第２の動きベクトルを探索する処理を行う。
【００４８】
まず、動き探索部１１１により反復処理のための変数ｉｔｅを１に初期化して、反復処理を開始し、小ブロックｂｌ０と同サイズのデジタルフィルタを不一致フィルタとし、最初の反復処理の不一致フィルタａｆ［０］にすべて１（不一致画素）を代入する（ステップＳ３０１）。
【００４９】
図４は、最初の反復処理の不一致フィルタａｆ［０］の状態を示す説明図である。図４に示すように、ステップＳ３０１では、不一致フィルタａｆ［０］にすべて１（不一致画素）が設定される。なお、不一致フィルタａｆ［α］は反復回数α（ｉｔｅ＝α）における不一致フィルタであることを示している。
【００５０】
不一致フィルタは、小ブロックｂｌ０と同サイズで、０または１を値として有するデジタルフィルタである。図５は、不一致フィルタの内容を示す説明図である。図５に示すように、不一致フィルタには、一致画素については０、不一致画素について１が設定される。
【００５１】
次に、動き探索部１１１により動き探索処理を行う。図６は、動き探索処理の概要を示す説明図である。図６に示すように、動き探索部１１１は、不一致フィルタ［ｉｔｅー１］の値が１の画素、すなわち不一致領域のみを用いて、補間フレーム上の小ブロックｂｌ０を中心として、幾何学的に対称的な参照フレームｐ１上の小ブロックｂｌ１と参照フレームｐ２上の小ブロックｂｌ２の探索をおこない、最も相関度の高い小ブロックの対を探索し、動きベクトルｍｖ［ｉｔｅ］を求める（ステップＳ３０２）。
【００５２】
図７は、最初の反復時（ｉｔｅ＝１）の場合における動きベクトル推定処理の説明図である。最初の反復処理時において、相関度演算の際に、図７に示すように、不一致フィルタａｆ［０］の値が１の画素のみについて演算をおこなうが、最初の反復時において不一致フィルタａｆ［０］はブロック内の全画素が１（不一致画素）に設定されているので、ブロック内のすべての画素について相関度演算が行われることになる。
【００５３】
図８は、二回目以降の反復時（ｉｔｅ＞１）の場合における動きベクトル推定処理の説明図である。二回目以降の反復処理時においては、相関度演算の際に、図８に示すように、不一致フィルタａｆ［ｉｔｅ−１］の値が１の画素のみについて相関度演算が行われる。
【００５４】
次に、動き探索部１１１によって、動きベクトルｍｖ［Ｉｔｅ］によって定まる、参照フレームｐ１上の小ブロックｂｌ１と、参照フレームｐ２上の小ブロックｂｌ２を求める（ステップＳ３０３）。
【００５５】
次に、領域分割部１１２は、小ブロックｂｌ１と小ブロックｂｌ２から一致判定をおこない、不一致フィルタａｆ［ｉｔｅ］を求める（ステップＳ３０４）。なお、かかる一致判定処理については後述する。
【００５６】
次に、領域分割部１１２は、不一致フィルタａｆ［ｉｔｅ］と不一致フィルタａｆ［ｉｔｅ−１］の論理積を求めて、求めた論理積を不一致フィルタａｆ［ｉｔｅ］に設定する（ステップＳ３０５）。これにより、一致判定処理で得られた不一致フィルタの値が不一致フィルタａｆ［ｉｔｅ］に反映されることになる。
【００５７】
そして、動き探索部１１１は、変数ｉｔｅを１だけ増加して（ステップＳ３０６）、ステップＳ３０２からＳ３０６までの動き探索処理および一致判定処理を繰り返し実行し、変数ｉｔｅが任意の整数であるｎを越えた時点で（ステップＳ３０７）、ステップＳ３０２からＳ３０６までの処理の反復を終了する。これにより、動きベクトルグループｍｖｇ（動きベクトルｍｖ［ｉ］（ｉ＝１．．．ｎ））と、不一致フィルタグループａｆｇ（不一致フィルタａｆ［ｉ］（ｉ＝１．．．ｎ））が出力される。
【００５８】
次に、ステップＳ３０４における一致判定処理について説明する。図９は、一致判定処理の手順を示すフローチャートである。
【００５９】
本実施の形態では、階層的にＭＡＰ推定問題を解法することにより一致判定をおこなっている。まず、領域分割部１１２は、小ブロックｂｌ１と小ブロックｂｌ２を入力して、小ブロックｂｌ１からブロック層ｂｌ＿ｌａｙ１を生成し、小ブロックｂｌ２からブロック層ｂｌ＿ｌａｙ２を生成する（ステップＳ９０１）。かかる階層生成処理については後述する。
【００６０】
次に、領域分割部１１２は、ループ変数をｉとして、階層を順に再帰的に下るループを開始し、ループ変数ｉの初期値として０を設定する（ステップＳ９０２）。
【００６１】
次に、領域分割部１１２は、ブロック層ｂｌ＿ｌａｙ１［ｉ＋１］と同サイズの不一致フィルタａｆを生成し、生成した不一致フィルタａｆの値にすべて１（不一致画素）を設定し（ステップＳ９０３）、ブロック内の走査を開始する（ステップＳ９０４）。ここで、走査インデックスを（ｘ、ｙ）とする。
【００６２】
次いで、探索領域についての組み合わせ探索ループを開始する（ステップＳ９０５）。図１０は、探索領域についての全組み合わせを示す探索領域パターンの例を示す説明図である。図１０において斜線部分が探索領域であることを示している。
【００６３】
そして、領域分割部１１２は、図１０に示す探索領域パターンの中からまだ選択されていない任意の探索領域パターンを一つ選択して組み合わせブロックを生成する（ステップＳ９０６）。そして、組み合わせブロックを不一致フィルタａｆにおける（２x、２ｙ）の位置に貼付して不一致フィルタａｆ＿ｔｍｐを生成する（ステップＳ９０７）。
【００６４】
次に、事前確率算出部１１４により、不一致フィルタａｆ＿ｔｍｐを用いて事前確率ｐ（ｘ）を算出する（ステップＳ９０８）。ここで、事前確率ｐ（ｘ）の算出処理については後述する。
【００６５】
そして、尤度算出部１１３によって、不一致フィルタａｆ＿ｔｍｐ、ブロック層ｂｌ＿ｌａｙ１［ｉ＋１］、ブロック層ｂｌ＿ｌａｙ２［ｉ＋１］を用いて尤度ｐ（ｙ｜ｘ）を算出する（ステップＳ９０９）。ここで、尤度ｐ（ｙ｜ｘ）の算出処理については後述する。
【００６６】
次に、事後確率算出部１１５によって、事前確率ｐ（ｘ）と尤度ｐ（ｙ｜ｘ）の積から事後確率ｐ（ｘ｜ｙ）を算出する（ステップＳ９１０）。
【００６７】
次に、判断部１１６によって、事後確率ｐの最大値を与える不一致フィルタａｆ＿ｔｍｐを不一致フィルタａｆ＿ｍａｘとする（ステップＳ９１１）。具体的には、判断部１１６は、前回までの組み合わせループ内において、ステップＳ９０６で選択された探索領域パターンに応じて生成された不一致フィルタａｆ＿ｔｍｐから求めた事後確率ｐ（ｘ｜ｙ）の最大値より、今回の組み合わせループ内で選択された探索領域パターンに応じて生成された不一致フィルタａｆ＿ｔｍｐから求めた事後確率ｐ（ｘ｜ｙ）が大きいか否かを判断して大きい場合に、今回の事前確率ｐ（ｘ｜ｙ）を与える不一致フィルタａｆ＿ｔｍｐを不一致フィルタａｆ＿ｍａｘとする。
【００６８】
そして、探索領域の全組み合わせについて探索したか否か、すなわち図１０に示す全ての探索領域パターンを選択したか否かを判断し（ステップＳ９１２）、全組み合わせを探索していない場合には（ステップＳ９１２：Ｎｏ）、ステップＳ９０５からＳ９１１までの処理を繰り返して実行する。
【００６９】
一方、ステップＳ９１２において、探索領域の全組み合わせを探索したと判断された場合には（ステップＳ９１２：Ｙｅｓ）、現在の不一致フィルタａｆ＿ｍａｘを不一致フィルタａｆと設定する（ステップＳ９１３）。
【００７０】
そして、ブロック内をすべて走査するまでステップＳ９０４からＳ９１３までの処理を繰り返し実行し（ステップＳ９１４：Ｎｏ）、ブロック内をすべて走査したら（ステップＳ９１４：Ｙｅｓ）、ループ変数ｉをｉ＝ｉ＋１に更新する（ステップＳ９１５）。そして、ループ変数ｉが階層数ｎ以上になるまで、ステップＳ９０２からＳ９１５までの処理を繰り返し（ステップＳ９１６：Ｎｏ）、ループ変数ｉが階層数ｎ以上になったら（ステップＳ９１６：Ｙｅｓ）、処理を終了する。これにより、事後確率ｐ（ｘ｜ｙ）の最大を与える不一致フィルタａｆが出力される。
【００７１】
次に、ステップＳ９０１における階層生成処理について説明する。図１１は、階層生成処理の手順を示すフローチャートである。ここでは、入力された小ブロックｌｂｌから、空間方向にサンプリングされた階層状のブロック層ｌｂｌ＿ｌａｙを生成する処理について説明する。かかる階層生成処理は、図９の一致判定処理におけるステップＳ９０１において、小ブロックｂｌ１、小ブロックｂｌ２のそれぞれに対して実行され、小ブロックｂｌ１のブロック層、小ブロックｂｌ２のブロック層が生成されることになる。ここでは、一般的に、小ブロックｌｂｌを入力して、小ブロックｌｂｌからブロック層ｌｂｌ＿ｌａｙを生成する処理について説明する。
【００７２】
まず、領域分割部１１２は、小ブロックｌｂｌの縦サイズと横サイズから空間方向へのサンプリング回数ｎを算出する（ステップＳ１１０１）。例えば、１６×１６サイズのブロックの場合には、縦横とも４回ずつ１／２スケールのサンプリングを繰り返し適用すると（ｎ＝４）、１×１の最小ブロックとなる。３２×１６であれば、縦横とも４回ずつ１／２スケールのサンプリングを適用すると（ｎ＝４）、２×１の最小ブロックとなる。
【００７３】
次に、領域分割部１１２は、ｎ階ブロック層ｌｂｌ＿ｌａｙのｎ＋１配列を確保する（ステップＳ１１０２）。この配列は、各層の小ブロックを格納する領域として使用される。そして、領域分割部１１２は、ブロック層ｌｂｌ＿ｌａｙ［ｎ］に小ブロックｌｂｌを格納する（ステップＳ１１０３）。
【００７４】
次に、領域分割部１１２は、ループ変数ｉの初期値をｎとして、階層ループを開始する（ステップＳ１１０４）。そして、ブロック層ｌｂｌ＿ｌａｙ［ｉ］を、空間方向に１回サンプリングし、ｌｂｌ＿ｌａｙ［ｉ−１］に格納する（ステップＳ１１０５）。ここで、空間方向のサンプリングは任意のサンプリングを用いても良いが、例えば、周囲４点の平均をサンプリング点とするサンプリングを用いることができる。このサンプリングをおこなうと、スケールは１／２となる。
【００７５】
次に、領域分割部１１２は、ループ変数ｉをｉ−１に更新する（ステップＳ１１０６）。そして、ループ変数ｉが０よりも小さいか否かを判断し（ステップＳ１１０７）、０以上である場合には（ステップＳ１１０７：Ｎｏ）、ステップＳ１１０４からＳ１１０６までの処理を繰り返し実行する。一方、ループ変数ｉが０よりも小さい場合には（ステップＳ１１０７：Ｙｅｓ）、階層生成処理を終了する。これにより、ブロック層ｌｂｌ＿ｌａｙが生成されて出力される。ステップＳ９０１の処理により、小ブロックｂｌ１からブロック層ｂｌ＿ｌａｙ１が生成され、小ブロックｂｌ２からブロック層ｂｌ＿ｌａｙ２が生成されることになる。
【００７６】
次に、図９の一致判定処理のステップＳ９０８における事前確率算出部１１４による事前確率ｐ（ｘ）の算出処理について説明する。図１２は、事前確率算出部１１４による事前確率の算出処理の手順を示すフローチャートである。
【００７７】
事前確率算出部１１４は、まず、不一致フィルタａｆ＿ｔｍｐを入力して、変数ａ，ｎ，ｄをすべて０に初期化し（ステップＳ１２０１）、ブロック内の隣接画素の２点であるクリークを走査する（ステップＳ１２０２）。
【００７８】
次に、対象クリーク内の不一致フィルタａｆ＿ｔｍｐの値がすべて０（一致画素）か否かを調べる（ステップＳ１２０３）。そして、対象クリーク内の不一致フィルタａｆ＿ｔｍｐの値がすべて０（一致画素）である場合には（ステップＳ１２０３：Ｙｅｓ）、変数ａを１だけインクリメントする（ステップＳ１２０５）。
【００７９】
一方、ステップＳ１２０３において、対象クリーク内の不一致フィルタａｆ＿ｔｍｐのいずれかの値が０（一致画素）でない場合には（ステップＳ１２０３：Ｎｏ）、対象クリーク内の不一致フィルタａｆ＿ｔｍｐの値がすべて１（不一致画素）であるか否かを調べる（ステップＳ１２０４）。そして、対象クリーク内の不一致フィルタａｆ＿ｔｍｐの値がすべて１（不一致画素）である場合には（ステップＳ１２０４：Ｙｅｓ）、変数ｎを１だけインクリメントする（ステップＳ１２０６）。
【００８０】
一方、ステップＳ１２０４において、対象クリーク内の不一致フィルタａｆ＿ｔｍｐのいずれかの値が１（不一致画素）でない場合には（ステップＳ１２０４：Ｎｏ）、変数ｄを１だけ増加する（ステップＳ１２０７）。
【００８１】
そして、すべてのクリークを走査したか否かを判断し（ステップＳ１２０８）、すべて走査していない場合には（ステップＳ１２０８：Ｎｏ）、ステップＳ１２０２からＳ１２０７までの処理を繰り返し実行する。一方、すべてのクリークを走査した場合には（ステップＳ１２０８：Ｙｅｓ）、数６式で示されるｓｕｍを算出する（ステップＳ１２０９）。
【００８２】
【数６】
2006101032.tif 000008
【００８３】
次に、ステップ１２０９で算出されたｓｕｍを用いて、数７式により事前確率ｐ（ｘ）を算出する（ステップＳ１２１０）。
【００８４】
【数７】
2006101032.tif 000009
【００８５】
かかる数６式および数７式は、数２式で定式化された事前確率を具体的に求める算出式である。これにより、事前確率が算出されて出力される。
【００８６】
次に、図９の一致判定処理のステップＳ９０９における尤度算出部１１３による尤度ｐ（ｙ｜ｘ）の算出処理について説明する。図１３は、尤度算出部１１３による尤度の算出処理の手順を示すフローチャートである。
【００８７】
まず、尤度算出部１１３は、ブロックｂｌ＿ｌａｙ１，ｂｌ＿ｌａｙ２および不一致フィルタａｆ＿ｔｍｐを入力し、ブロックｂｌ＿ｌａｙ１とｂｌ＿ｌａｙ２の差分ブロックｄｂｌを算出する（ステップＳ１３０１）。そして、不一致フィルタａｆ＿ｔｍｐが０の画素（一致画素）のみに対して、（差分ブロックｄｂｌの２乗）／２の総和ｓｕｍを求める（ステップＳ１３０２）。そして、数８式により尤度ｐ（ｙ｜ｘ）を算出し（ステップＳ１３０３）、出力する。
【００８８】
【数８】
2006101032.tif 000010
【００８９】
次に、図２のステップＳ２０４における動き補償部１２０による動き補償処理について説明する。図１４は、動き補償部１２０による動き補償処理の手順を示すフローチャートである。
【００９０】
動き補償処理では、動き推定処理で出力された動きベクトルグループｍｖｇ（動きベクトルｍｖ［ｉ］（ｉ＝１．．．ｎ））、不一致フィルタグループａｆｇ（不一致フィルタａｆ［ｉ］（ｉ＝１．．．ｎ））、参照フレームｐ１，参照フレームｐ２から動き補償をおこない、補間フレームを生成する。
【００９１】
まず、動き補償部１２０は、反復処理のための変数ｉｔｅを初期値１に設定する（ステップＳ１４０１）。そして、補間フレーム上の小ブロックｂｌ０を中心として、動きベクトルグループｍｖｇの動きベクトルｍｖ［ｉｔｅ］の点対称位置によって定まる参照フレームｐ１上の画像ブロックｐｂ１を求め（ステップＳ１４０２）、動きベクトルｍｖ［ｉｔｅ］によって定まる参照フレームｐ２上の画像ブロックｐｂ２を求める（ステップＳ１４０３）。そして、動き補償部１２０は、補間フレーム上の小ブロックｂｌ０の位置を求める（ステップＳ１４０４）。
【００９２】
そして、動き補償部１２０は、ブロック内の画素の走査を開始し（ステップＳ１４０５）、画像ブロックｐｂ１の対象画素位置における画素と、画像ブロックｐｂ２の画素の平均値を求める（ステップＳ１４０６）。
【００９３】
次に、動き補償部１２０は、不一致フィルタ［ｉｔｅ］の値が０か否か、すなわち、一致画素か否かを調べる（ステップＳ１４０７）。そして、不一致フィルタ［ｉｔｅ］の値が０である場合、すなわち一致画素の場合には（ステップＳ１４０７：Ｙｅｓ）、上記平均画素を補間フレーム上の対象画素位置にコピーする（ステップＳ１４０８）。一方、ステップＳ１４０７において、不一致フィルタ［ｉｔｅ］の値が１の場合、すなわち不一致画素の場合には（ステップＳ１４０７：Ｎｏ）、上記平均画素のコピーを行わない。
【００９４】
ステップＳ１４０７、Ｓ１４０８の処理は、ブロック内の全画素を走査するまで繰り返し実行される（ステップＳ１４０９）。これにより、一致領域のみに対して動き補償処理がなされ補間フレームが生成されることになる。一方、不一致領域の場合には、上記平均画素の補間フレームの小ブロックｂｌ０へのコピーは行われないが、動き補償処理終了後、動き推定処理（図３）において、再帰的に動きベクトル（第２の動きベクトル）が求められることになる。
【００９５】
ブロック内の全画素の走査が終了したら（ステップＳ１４０９：Ｙｅｓ）、動き補償部１２０は、反復処理のための変数ｉｔｅを１だけ増加して（ステップＳ１４１０）、変数ｉｔｅがｎ（任意の整数）を越えたか否かを判断する（ステップＳ１４１１）。そして、変数ｉｔｅがｎを越えるまで、ステップＳ１４０２からＳ１４１０までの処理を繰り返し実行する。
【００９６】
図２のステップＳ２０３の動き推定処理と上述した動き補償処理は、図２のステップＳ２０１で分割した小ブロック０のすべてを走査するまで繰り返し実行され、小ブロック０の走査を終了したら終了し、補間フレームが生成されることになる。
【００９７】
次に、本実施の形態にかかる補間画像生成装置１００による一致判定の結果と従来の手法による一致判定の結果を比較して示す。図１５は、ブロック内で一致領域を変化させた状態を示す説明図である。図１５に示すように、ｘ軸とｙ軸で走査しながら一致領域を変更しその時の事後確率を集計した。図１６は、左半分の領域が一致領域となるノイズのない画像の２つのブロックの例を示す説明図である。従って、事後確率分布は理想的には左半分が一致領域となったときに最大となる。
【００９８】
まず、図１６に示す画像において従来の手法による一致判定、すなわち単純にブロック内の相対位置が等しい画素同士の絶対値差分を取り、その絶対値差分値が閾値（例えば１０）より小さければ一致領域とする一致判定を行って補間フレームを生成した。図１７は、従来の一致判定手法を利用して生成した補間フレームの画像を示す説明図である。図１７に示すように、ノイズが全く存在しない画像の場合には従来の一致判定の手法でも補間画像が正常に生成される。
【００９９】
図１８は、図１６に示す２つのブロックに対して本実施の形態にかかる補間画像生成装置１００による一致判定により求めた事後確率の分布を示す説明図である。図１８に示すように、事後確率分布は、左半分が一致領域のときに事後確率ｐ（ｘ｜ｙ）が最大となっており正確に動作していることが分かる。
【０１００】
図１９は、左半分の領域が一致領域となるノイズが存在する画像の２つのブロックの例を示す説明図である。図１９に示す画像において従来の手法による一致判定を行って補間フレームを生成した。図２０は、従来の一致判定手法を利用して生成した補間フレームの画像を示す説明図である。従来の手法では、画素同士の絶対値差分値が一定の閾値より小さい場合に一致領域とする一致判定を行っているため、ノイズ成分に対応することが出来ず、このため図２０に示すように補間フレームにごま塩雑音が発生していることがわかる。
【０１０１】
図２１は、図１６に示す２つのブロックに対して本実施の形態にかかる補間画像生成装置１００による一致判定により求めた事後確率の分布を示す説明図である。図２１に示すように、事後確率分布は、左半分が一致領域のときに事後確率ｐ（ｘ｜ｙ）が最大となっており、ノイズが含まれる画像に対しても正確に動作していることがわかる。
【０１０２】
このように実施の形態１にかかる補間画像生成装置では、ベイズ決定理論を用いて一致判定問題をＭＡＰ推定問題として定式化し、画素毎での一致判定を行う必要がなくなり、より確からしい手法で一致領域と不一致領域を分割することができるので、ごま塩雑音のようなノイズを低減するとともに、ロバスト性を向上させながら、ブロック歪みを低減して動画像を滑らかに表示することができる。
【０１０３】
（実施の形態２）
実施の形態１にかかる補間画像生成装置１００では、一致判定処理において入力される小ブロックをまず階層生成処理（図１１）によって階層化してから階層ブロックごとに一致判定、事後確率の算出を行っているが、この実施の形態２にかかる補間画像生成装置は、一致判定の処理を行いながら階層化を行うものである。
【０１０４】
本実施の形態にかかる補間画像生成装置の機能的構成は実施の形態１の補間画像装置と同様である。また、補間画像生成の全体処理、動き推定処理、動き補償処理については、実施の形態１の全体処理（図２）、動き推定処理（図３）、動き補償処理（図１４）とそれぞれ同様に行われる。本実施の形態の補間画像生成装置では、図３に示す動き推定処理のステップ３０４における一致判定の処理が実施の形態１と異なっている。
【０１０５】
図２２は、実施の形態２における一致判定処理の手順を示すフローチャートである。まず、領域分割部１１２は、小ブロックｂｌ１と小ブロックｂｌ２を入力して、ループ変数をｉとして、階層を順に再帰的に下っていくループを開始し、ループ変数の初期値として１を設定する（ステップＳ２２０１）。そして、領域分割部１１２は、小ブロックｂｌ１と同サイズの不一致フィルタａｆを用意し、不一致フィルタａｆにすべて１を設定する（ステップＳ２２０２）。
【０１０６】
次に、領域分割部１１２は、ブロック内の走査を開始し、走査インデックスを（ｘ、ｙ）とする（ステップＳ２２０３）。ここで、走査インデックス（ｘ、ｙ）の範囲は（０，０）＜＝（ｘ、ｙ）＜（２(i-1),２(i-1)）とする。そして、領域分割部１１２は、組み合わせ探索ループを開始する（ステップＳ２２０４）。ここで、探索領域の組み合わせは、実施の形態１と同様に、図１０に示す探索領域パターンと同様のものである。
【０１０７】
次に、領域分割部１１２は、図１０の中から一つの探索領域パターンを選択して組み合わせブロックを生成し（ステップＳ２２０５）、この組み合わせブロックを縦横２(n-i-1)倍にスケール変換する（ステップＳ２２０６）。そして、ｓｉｚｅを数９式により算出する（ステップＳ２２０７）。
【０１０８】
【数９】
2006101032.tif 000011
【０１０９】
次に、領域分割部１１２は、組み合わせブロックを不一致フィルタａｆにおける（ｘ＊ｓｉｚｅ，ｙ＊ｓｉｚｅ）の位置に貼付して、不一致フィルタａｆ＿ｔｍｐを生成する（ステップＳ２２０８）。
【０１１０】
次に、事前確率算出部１１４により、不一致フィルタａｆ＿ｔｍｐを用いて事前確率ｐ（ｘ）を算出する（ステップＳ２２０９）。ここで、事前確率ｐ（ｘ）の算出処理については実施の形態１の事前確率算出処理（図１２）と同様に行われる。
【０１１１】
そして、尤度算出部１１３によって、不一致フィルタａｆ＿ｔｍｐ、ブロック層ｂｌ＿ｌａｙ１［ｉ＋１］、ブロック層ｂｌ＿ｌａｙ２［ｉ＋１］を用いて尤度ｐ（ｙ｜ｘ）を算出する（ステップＳ２２１０）。ここで、尤度ｐ（ｙ｜ｘ）の算出処理については実施の形態１の尤度算出処理（図１３）と同様に行われる。
【０１１２】
次に、事後確率算出部１１５によって、事前確率ｐ（ｘ）と尤度ｐ（ｙ｜ｘ）の積から事後確率ｐ（ｘ｜ｙ）を算出する（ステップＳ２２１１）。
【０１１３】
次に、判断部１１６によって、事後確率ｐの最大値を与えるａｆ＿ｔｍｐを不一致フィルタａｆ＿ｍａｘとする（ステップＳ２２１２）。具体的には、判断部１１６は、実施の形態１と同様に、前回までの組み合わせループ内において、ステップＳ２２０５で選択された探索領域パターンに応じて生成された不一致フィルタａｆ＿ｔｍｐから求めた事後確率ｐ（ｘ｜ｙ）の最大値より、今回の組み合わせループ内で選択された探索領域パターンに応じて生成された不一致フィルタａｆ＿ｔｍｐから求めた事後確率ｐ（ｘ｜ｙ）が大きいか否かを判断して大きい場合に、今回の事前確率ｐ（ｘ｜ｙ）を与える不一致フィルタａｆ＿ｔｍｐを不一致フィルタａｆ＿ｍａｘとする。
【０１１４】
そして、探索領域の全組み合わせを探索したか否かを判断し（ステップＳ２２１３）、全組み合わせを探索していない場合には（ステップＳ２２１３：Ｎｏ）、ステップＳ２２０４からＳ２２１２までの処理を繰り返して実行する。
【０１１５】
一方、ステップＳ２２１３において、探索領域の全組み合わせを探索したと判断された場合には（ステップＳ２２１３：Ｙｅｓ）、判断部１１６は、不一致フィルタａｆ＿ｍａｘを不一致フィルタａｆと設定する（ステップＳ２２１４）。
【０１１６】
そして、ブロック内をすべて走査するまでステップＳ２２０３からＳ２２１４までの処理を繰り返し実行し（ステップＳ２２１５：Ｎｏ）、ブロック内をすべて走査したら（ステップＳ２２１５：Ｙｅｓ）、ループ変数ｉをｉ＝ｉ＋１に更新する（ステップＳ２２１６）。そして、ループ変数ｉが階層数ｎ以上になるまで、ステップＳ２２０１からＳ２２１６までの処理を繰り返し（ステップＳ２２１７：Ｎｏ）、ループ変数ｉが階層数ｎ以上になったら（ステップＳ２２１７：Ｙｅｓ）、処理を終了する。これにより、不一致フィルタａｆが出力される。
【０１１７】
このように実施の形態２にかかる補間画像生成装置では、一致判定処理を行いながら小ブロックの階層化を行っているので、別途、予め階層生成処理を必要がなく、一致判定の処理を迅速に行うことができる。
【０１１８】
また、実施の形態２にかかる補間画像生成装置では、ベイズ決定理論を用いて一致判定問題をＭＡＰ推定問題として定式化し、画素毎での一致判定を行う必要がなくなり、より確からしい手法で一致領域と不一致領域を分割することができるので、ごま塩雑音のようなノイズを低減するとともに、ロバスト性を向上させながら、ブロック歪みを低減して動画像を滑らかに表示することができる。
【０１１９】
（実施の形態３）
実施の形態１および２にかかる補間画像生成装置では、一致判定処理において階層的な不一致フィルタを用いたが、この実施の形態３にかかる補間画像生成装置は、不一致フィルタをランダムに与え、統計物理学等におけるメトロポリスアルゴリズムを利用して行って一致判定処理を行うものである。
【０１２０】
本実施の形態にかかる補間画像生成装置の機能的構成は実施の形態１の補間画像装置と同様である。また、補間画像生成の全体処理についても実施の形態１の全体処理（図２）と同様に行われる。本実施の形態の補間画像生成装置では、図２に示す全体処理のステップ３０４における一致判定の処理において、事後確率ｐ（ｘ｜ｙ）の最大値の算出手法が実施の形態１と異なっている。
【０１２１】
本実施の形態における一致判定処理で使用されるメトロポリスアルゴリズム（A. Murat Tekalp, “Digital Video Processing”, Prentice Hall, 1995、p31参照）では、ランダムに与えられた不一致フィルタに対して、事後確率を計算し、アニーリング温度に従って事後確率を採択するかどうかが決定される。アニーリング温度は、アニーリングスケジュールに従って設定される。アニーリング温度が高い場合には、事後確率が低い場合でも採択する可能性があり、それによりローカルマキシマムを脱出できる。アニーリング温度が低くなると、事後確率が低いものが採択される可能性は小さくなり、徐々にグローバルマキシマムへと収束する。
【０１２２】
図２３は、実施の形態３における一致判定処理の手順を示すフローチャートである。領域分割部１１２は、小ブロックｂｌ１と小ブロックｂｌ２を入力して、小ブロックｂｌ１と小ブロックｂｌ２から一致判定を行って不一致フィルタａｆを得る（ステップＳ２３０１）。そして、アニーリング温度Ｔを初期温度Ｔ０で初期化し、ある温度における反復回数ＭをＭ０で初期化し、事後確率の最大値を与える不一致フィルタａｆ＿ｍａｘを入力した不一致フィルタａｆとする（ステップＳ２３０２）。
【０１２３】
次に、事前確率算出部１１４により、不一致フィルタａｆを用いて事前確率ｐ（ｘ）を算出する（ステップＳ２３０３）。ここで、事前確率ｐ（ｘ）の算出処理については実施の形態１の事前確率算出処理（図１２）と同様に行われる。
【０１２４】
そして、尤度算出部１１３によって、不一致フィルタａｆ、小ブロックｂｌ１、小ブロックｂｌ２を用いて尤度ｐ（ｙ｜ｘ）を算出する（ステップＳ２３０４）。ここで、尤度ｐ（ｙ｜ｘ）の算出処理については実施の形態１の尤度算出処理（図１３）と同様に行われる。
【０１２５】
次に、事後確率算出部１１５によって、事前確率ｐ（ｘ）と尤度ｐ（ｙ｜ｘ）の積から現在の事後確率ｐ（ｘ｜ｙ）であるＣｕｒＰを算出し、最大の事後確率ｐ（ｘ｜ｙ）であるＭａｘＰにＣｕｒＰを設定する（ステップＳ２３０５）。
【０１２６】
次に、領域分割部１１２は、不一致フィルタａｆに摂動を加えて摂動解としての不一致フィルタａｆ＿ｎｅｗを生成する（ステップＳ２３０６）。ここで、摂動としては、例えば、ランダムに４ピクセルを選択し、選択された４ピクセルの値を反転させるなどが考えられる。
【０１２７】
そして、事前確率算出部１１４により、生成された不一致フィルタａｆ＿ｎｅｗを用いて事前確率ｐ（ｘ）を算出する（ステップＳ２３０７）。また  尤度算出部１１３によって、不一致フィルタａｆ＿ｎｅｗ、小ブロックｂｌ１、小ブロックｂｌ２を用いて尤度ｐ（ｙ｜ｘ）を算出する（ステップＳ２３０８）。そして、事後確率算出部１１５によって、事前確率ｐ（ｘ）と尤度ｐ（ｙ｜ｘ）の積から次の状態の事後確率ｐ（ｘ｜ｙ）であるＮｅｗＰを算出する（ステップＳ２３０９）。そして、判断部１１６は、次の状態の事後確率ｐ（ｘ｜ｙ）であるＮｅｗＰと現在の事後確率ｐ（ｘ｜ｙ）であるＣｕｒＰの差ΔＣｏｓｔを求め（ステップＳ２３１０）、差ΔＣｏｓｔが０より大きいか否かを判断する（ステップＳ２３１１）。
【０１２８】
そして、次の状態の事後確率ＮｅｗＰと現在の事後確率ＣｕｒＰの差ΔＣｏｓｔが０より大きい場合には（ステップＳ２３１１：Ｙｅｓ）、判断部１１６は、現在の事後確率ＣｕｒＰに次の状態の事後確率ＮｅｗＰを設定し、不一致フィルタａｆに不一致フィルタａｆ＿ｎｅｗを設定する（ステップＳ２３１２）。そして、判断部１１６は、次の状態の事後確率ＮｅｗＰが、最大の事後確率ＭａｘＰより大きいか否かを判断する（ステップＳ２３１３）。
【０１２９】
そして、次の状態の事後確率ＮｅｗＰが、最大の事後確率ＭａｘＰより大きい場合には（ステップＳ２３１３：Ｙｅｓ）、判断部１１６は、最大の事後確率ＭａｘＰに次の状態の事後確率ＮｅｗＰを設定し、事後確率の最大値を与える不一致フィルタａｆ＿ｍａｘに不一致フィルタａｆ＿ｎｅｗを設定する（ステップＳ２３１４）。
【０１３０】
一方、ステップＳ２３１３において、次の状態の事後確率ＮｅｗＰが、最大の事後確率ＭａｘＰ以下の場合には（ステップＳ２３１３：Ｎｏ）、最大の事後確率ＭａｘＰと事後確率の最大値を与える不一致フィルタａｆ＿ｍａｘは変更されない。
【０１３１】
ステップＳ２３１１において、次の状態の事後確率ＮｅｗＰと現在の事後確率ＣｕｒＰの差ΔＣｏｓｔが０以下である場合には（ステップＳ２３１１：Ｎｏ）、判断部１１６は、現在の事後確率ＣｕｒＰと不一致フィルタａｆは変更せず、０から１までの一様乱数を発生させ、この一様乱数がｅｘｐ（ΔＣｏｓｔ／Ｔ）より小さいか否かを調べる（ステップＳ２３１５）。そして、一様乱数がｅｘｐ（ΔＣｏｓｔ／Ｔ）より小さい場合には（ステップＳ２３１５：Ｙｅｓ）、判断部１１６は、現在の事後確率ＣｕｒＰに次の状態の事後確率ＮｅｗＰを設定し、不一致フィルタａｆに不一致フィルタａｆ＿ｎｅｗを設定する（ステップＳ２３１６）。
【０１３２】
一方、ステップＳ２３１５において、一様乱数がｅｘｐ（ΔＣｏｓｔ／Ｔ）以上である場合には（ステップＳ２３１５：Ｎｏ）、現在の事後確率ＣｕｒＰと不一致フィルタａｆは変更されない。
【０１３３】
次に、反復回数Ｍを１だけデクリメントし、Ｍが０になったか否かを調べる（ステップＳ２３１７）。そして、反復回数Ｍが０になっていない場合には（ステップＳ２３１７：Ｎｏ）、ステップＳ２３０６からＳ２３１６までの処理を繰り返し実行する。一方、ステップＳ２３１７において、反復回数Ｍが０になった場合には（ステップＳ２３１７：Ｙｅｓ）、判断部１１６は、時間Ｔｉｍｅに反復回数Ｍを加算し、温度Ｔに減少率αを乗じ、さらに反復回数Ｍに上昇率βを乗じて、それぞれ時間Ｔｉｍｅ、温度Ｔ、反復回数Ｍを更新する（ステップＳ２３１８）。ここで、温度Ｔの減少率αは０．８から１．０の間の値とする。また、Ｍの上昇率βは１．０以上の値とする。
【０１３４】
そして、判断部１１６は、時間Ｔｉｍｅが最大時間ＴｉｍｅＭａｘを超えたか否かを判断して（ステップＳ２３１９）、最大時間ＴｉｍｅＭａｘを超えていない間は（ステップＳ２３１９：Ｎｏ）、ステップＳ２３０６からＳ２３１８までの処理を繰り返し実行する。一方、ステップＳ２３１９において、時間Ｔｉｍｅが最大時間ＴｉｍｅＭａｘを超えた場合には（ステップＳ２３１９：Ｙｅｓ）、処理を終了する。このような処理により、事後確率ｐ（ｘ｜ｙ）を最大値とする不一致フィルタａｆ＿ｍａｘが出力される。
【０１３５】
このように本実施の形態にかかる補間画像生成装置では、不一致フィルタをランダムに与え、統計物理学等におけるメトロポリスアルゴリズムを利用して行って判定処理を行っているので、より確からしい手法で一致領域と不一致領域を分割することができるので、ごま塩雑音のようなノイズを低減するとともに、ロバスト性を向上させながら、ブロック歪みを低減して動画像を滑らかに表示することができる。
【０１３６】
実施の形態１〜３にかかる補間画像生成装置は、ＣＰＵなどの制御装置と、ＲＯＭ（Read Only Memory）やＲＡＭなどの記憶装置と、ＨＤＤ、ＣＤドライブ装置などの外部記憶装置と、ディスプレイ装置などの表示装置と、キーボードやマウスなどの入力装置を備えており、通常のコンピュータを利用したハードウェア構成となっている。
【０１３７】
実施の形態１〜３にかかる補間画像生成装置で実行される補間画像生成プログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のコンピュータで読み取り可能な記録媒体に記録されて提供される。
【０１３８】
また、実施の形態１〜３にかかる補間画像生成装置で実行される補間画像生成プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また、本実施形態の〜装置で実行される補間画像生成プログラムをインターネット等のネットワーク経由で提供または配布するように構成しても良い。
【０１３９】
また、実施の形態１〜３にかかる補間画像生成プログラムを、ＲＯＭ等に予め組み込んで提供するように構成してもよい。
【０１４０】
実施の形態１〜３にかかる補間画像生成装置で実行される補間画像生成プログラムは、上述した各部（動き探索部１１１、領域分割部１１２、尤度算出部１１３、事前確率算出部１１４、事後確率算出部１１４、判断部１１６、動き補償部１２０）を含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵ（プロセッサ）が上記記憶媒体から補間画像生成プログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、動き探索部１１１、領域分割部１１２、尤度算出部１１３、事前確率算出部１１４、事後確率算出部１１４、判断部１１６、動き補償部１２０が主記憶装置上に生成されるようになっている。
【図面の簡単な説明】
【０１４１】
【図１】実施の形態１にかかる補間画像生成装置の機能的構成を示すブロック図である。
【図２】補間画像生成の全体処理の手順を示すフローチャートである。
【図３】動き推定処理の手順を示すフローチャートである。
【図４】最初の反復処理の不一致フィルタａｆ［０］の状態を示す説明図である。
【図５】不一致フィルタの内容を示す説明図である。
【図６】動き探索処理の概要を示す説明図である。
【図７】最初の反復時（ｉｔｅ＝１）の場合における動きベクトル推定処理の説明図である。
【図８】二回目以降の反復時（ｉｔｅ＞１）の場合における動きベクトル推定処理の説明図である。
【図９】一致判定処理の手順を示すフローチャートである。
【図１０】探索領域パターンの例を示す説明図である。
【図１１】階層生成処理の手順を示すフローチャートである。
【図１２】事前確率算出部１１４による事前確率の算出処理の手順を示すフローチャートである。
【図１３】尤度算出部１１３による尤度の算出処理の手順を示すフローチャートである。
【図１４】動き補償部１２０による動き補償処理の手順を示すフローチャートである。
【図１５】ブロック内で一致領域を変化させた状態を示す説明図である。
【図１６】左半分の領域が一致領域となるノイズのない画像の２つのブロックの例を示す説明図である。
【図１７】従来の一致判定手法を利用して生成した補間フレームの画像を示す説明図である。
【図１８】図１６に示す２つのブロックに対して本実施の形態にかかる補間画像生成装置１００による一致判定により求めた事後確率の分布を示す説明図である。
【図１９】左半分の領域が一致領域となるノイズが存在する画像の２つのブロックの例を示す説明図である。
【図２０】従来の一致判定手法を利用して生成した補間フレームの画像を示す説明図である。
【図２１】図１６に示す２つのブロックに対して本実施の形態にかかる補間画像生成装置１００による一致判定により求めた事後確率の分布を示す説明図である。
【図２２】実施の形態２における一致判定処理の手順を示すフローチャートである。
【図２３】実施の形態３における一致判定処理の手順を示すフローチャートである。
【図２４】ブロック内のの２点であるクリークを示す説明図である。
【符号の説明】
【０１４２】
１１０  動き推定部
１１１  動き探索部
１１２  領域分割部
１１３  尤度算出部
１１４  事前確率算出部
１１５  事後確率算出部
１１６  判断部
１２０  動き補償部
１３０  フレームメモリ
【図１】
2006101032.tif 000012
【図２】
2006101032.tif 000013
【図３】
2006101032.tif 000014
【図４】
2006101032.tif 000015
【図５】
2006101032.tif 000016
【図６】
2006101032.tif 000017
【図７】
2006101032.tif 000018
【図８】
2006101032.tif 000019
【図９】
2006101032.tif 000020
【図１０】
2006101032.tif 000021
【図１１】
2006101032.tif 000022
【図１２】
2006101032.tif 000023
【図１３】
2006101032.tif 000024
【図１４】
2006101032.tif 000025
【図１５】
2006101032.tif 000026
【図１６】
2006101032.tif 000027
【図１７】
2006101032.tif 000028
【図１８】
2006101032.tif 000029
【図１９】
2006101032.tif 000030
【図２０】
2006101032.tif 000031
【図２１】
2006101032.tif 000032
【図２２】
2006101032.tif 000033
【図２３】
2006101032.tif 000034
【図２４】
2006101032.tif 000035