(57)【要約】【課題】二つの画像から対応点を検出して画像のマッチングを行う画像マッチング方法およびこれを用いてフレームの補間を行うフレーム補間方法を提供する。【解決手段】対象画像上に仮設される第１の格子の第１の格子点に対して１対１に写像する参照画像上に仮設される第２の格子の第２の格子点に関して、第１の格子点と第２の格子点の位置によって求まる画像相関ポテンシャルエネルギーの勾配によって受ける力と、第２の格子点に隣接する第２の格子の他の格子点との間の弾性エネルギーから受ける力と、第２の格子点に生じる摩擦力とによって確立される、第２の格子点に関する運動方程式に基づいて動的モデルを生成し、運動方程式を数値解析することによって第２の格子点の平衡状態を求め、第２の格子点と前記隣接格子点との間の距離に応じて格子点間に新たな格子点を追加する。【選択図】      図１
2006260527.tif 000002
【特許請求の範囲】
【請求項１】
第１画像とと第２画像との間の対応関係を求める画像マッチング方法において、
複数の第１の格子点を有する第１の格子を第１画像上に設定するステップと、
前記第１の格子点の各々に一対一に対応する第２の格子点を有する第２の格子を第２画像上に設定するステップと、
前記第１の格子点の位置および画素情報と前記第２の格子点の位置および画素情報とによって求まる画像相関ポテンシャルエネルギーの勾配によって前記第２の格子点が受けるポテンシャル力を計算するステップと、
前記第２の格子点とこの第２の格子点に隣接する前記第２の格子の隣接格子点との間の弾性エネルギーから前記第２の格子点が受ける弾性力を計算するステップと、
前記第２の格子点に生じる摩擦力を計算するステップと、
前記ポテンシャル力、前記弾性力、および、前記摩擦力に基づく前記第２の格子点に関する運動方程式を数値解析することによって前記第２の格子点の平衡状態を求める数値解析ステップと、
前記運動方程式の数値解析中に、前記第２の格子点と前記隣接格子点との間の距離に応じて格子点間に新たな格子点を追加する格子点追加ステップと、
を有することを特徴とする画像マッチング方法。
【請求項２】
第１画像と第２画像との間の対応関係を求める画像マッチング方法において、
第１画像上に設定される第１の格子の第１の格子点に対して１対１に写像する第２画像上に設定される第２の格子の第２の格子点に関して、前記第１の格子点の位置および画素情報と前記第２の格子点の位置および画素情報とによって求まる画像相関ポテンシャルエネルギーの勾配によって前記第２の格子点が受けるポテンシャル力を計算するステップと、
前記第２の格子点とこの第２の格子点に隣接する前記第２の格子の隣接格子点との間の弾性エネルギーから前記第２の格子点が受ける弾性力を計算するステップと、
前記第２の格子点に生じる摩擦力を計算するステップと、
前記ポテンシャル力、前記弾性力、および、前記摩擦力に基づく第２の格子点に関する運動方程式を数値解析することによって前記第２の格子点の平衡状態を求める数値解析ステップと、
前記運動方程式の数値解析中に、前記第２の格子点と前記隣接格子点との間の格子点間距離に応じて前記弾性エネルギーの弾性定数を変更するステップと、
を有することを特徴とする画像マッチング方法。
【請求項３】
前記弾性定数を前記格子点間距離に応じて階段状に変化させるステップを含むことを特徴とする請求項２に記載の画像マッチング方法。
【請求項４】
前記弾性定数を前記格子点間距離に応じて線形に変化させるステップを含むことを特徴とする請求項２に記載の画像マッチング方法。
【請求項５】
前記弾性定数を前記格子点間距離に応じてロジスティック関数的に変化させるステップを含むことを特徴とする請求項２に記載の画像マッチング方法。
【請求項６】
時系列的にに並んでいる第１の参照画像と第２の参照画像と第３の参照画像を用いて、前記第１の参照画像と前記第２の参照画像との間に補間画像を内挿する画像補間方法において、
前記第１の参照画像上の第１の格子の第１の格子点に対して１対１に写像する前記第２の参照画像上の第２の格子の第２の格子点に関して、前記第１の格子点の位置および画素情報と前記第２の格子点の位置および画素情報とによって求まる画像相関ポテンシャルエネルギーの勾配によって前記第２の格子点が受けるポテンシャル力を計算するステップと、
前記第２の格子点とこの第２の格子点に隣接する前記第２の格子の隣接格子点との間の弾性エネルギーから前記第２の格子点が受ける弾性力を計算するステップと、
前記第２の格子点に生じる摩擦力を計算するステップと、
前記ポテンシャル力、前記弾性力、および、前記摩擦力に基づく第２の格子点に関する運動方程式を数値解析することによって前記第２の格子点の平衡状態を求める第１の数値解析ステップと、
前記第２の格子点の平衡状態における前記第２の格子点の分布に基づいて、オクルージョン領域を検出するオクルージョン領域検出ステップと、
画像マッチング手法により前記第２の参照画像と前記第３の参照画像との画素の対応関係を求めるステップと、
前記第２の格子点によって定まる第１の参照画像と第２の参照画像との画素の対応関係と、前記第２の参照画像と前記第３の参照画像との画素の対応関係と、検出されたオクルージョン領域の情報とを用いて、補間画像を生成する補間画像生成ステップと、
を有することを特徴とする画像補間方法。
【請求項７】
前記画像マッチング手法は、
前記第２の参照画像上の前記第２の格子の第３の格子点に対して１対１に写像する第３の参照画像上に設定される第３の格子の第４の格子点に関して、前記第３の格子点と前記第４の格子点の位置によって求まる画像相関ポテンシャルエネルギーの勾配によって前記第４の格子点が受けるポテンシャル力を計算するステップと、
前記第４の格子点とこの第４の格子点に隣接する格子点との間の弾性エネルギーから前記第４の格子点が受ける弾性力を計算するステップと、
前記第４の格子点に生じる摩擦力を計算するステップと、
前記ポテンシャル力、前記弾性力、および、前記摩擦力に基づく前記第４の格子点に関する運動方程式を数値解析することによって前記第４の格子点の平衡状態を求める第２の数値解析ステップと、
前記第３の格子点と前記第４の格子点との関係から、前記第２の参照画像と前記第３の参照画像との画素の対応関係を求めるステップと、
を含むことを特徴とする請求項６に記載の画像補間方法
【請求項８】
前記オクルージョン領域検出ステップでは、前記第２の格子点の平衡状態における前記第２の格子を前記第２の格子点を頂点として有する複数の領域に分割し、前記各領域のオクルージョン信頼度を算出し、閾値より大きい前記オクルージョン信頼度を有する前記領域をオクルージョン領域として検出し、
前記補間画像生成ステップでは、前記オクルージョン領域内の各画素の画素値を、前記第１画像と前記第２画像との画素の対応関係から求められる第１画素値と前記第２参照画像と前記第３参照画像との画素の対応関係から求められる第２画素値とを、前記オクルージョン信頼度に応じた重み付きで合成して求めることを特徴とする請求項６に記載の画像補間方法。
【請求項９】
時系列的に並んでいる第１の参照画像と第２の参照画像と第３の参照画像と第４の参照画像とを用いて、前記第２の参照画像と前記第３の参照画像間に補間画像を内挿する画像補間方法において、
前記第２の参照画像上の第１の格子の第１の格子点に対して１対１に写像する第３の参照画像上の第２の格子の第２の格子点に関して、前記第１の格子点の位置および画像情報と第２の格子点の位置および画像情報とによって求まる画像相関ポテンシャルエネルギーの勾配によって前記第２の格子点が受けるポテンシャル力を計算するステップと、
前記第２の格子点とこの第２の格子点に隣接する前記第２の格子の隣接格子点との間の弾性エネルギーから前記第２の格子点が受ける弾性力を計算するステップと、
前記第２の格子点に生じる摩擦力を計算するステップと、
前記ポテンシャル力、前記弾性力、および、前記摩擦力に基づく前記第２の格子点に関する運動方程式を数値解析することによって前記第２の格子点の平衡状態を求める第１の数値解析ステップと、
前記第２の格子点の平衡状態における前記第２の格子点の分布に基づいて、第１のオクルージョン領域を検出する第１のオクルージョン領域検出ステップと、
前記第３の参照画像上の第２の格子の第３の格子点に対して１対１に写像する第２の参照画像上の第１の格子の第４の格子点に関して、前記第３の格子点の位置および画像情報と第４の格子点の位置および画像情報とによって求まる画像相関ポテンシャルエネルギーの勾配によって前記第４の格子点が受けるポテンシャル力を計算するステップと、
前記第４の格子点とこの第４の格子点に隣接する前記第１の格子の隣接格子点との間の弾性エネルギーから前記第４の格子点が受ける弾性力を計算するステップと、
前記第４の格子点に生じる摩擦力を計算するステップと、
前記ポテンシャル力、前記弾性力、および、前記摩擦力とに基づく前記第４の格子点に関する運動方程式を数値解析することによって前記第４の格子点の平衡状態を求める第２の数値解析ステップと、
前記第４の格子点の平衡状態における前記第４の格子点の分布に基づいて、第２のオクルージョン領域を検出する第２のオクルージョン領域検出ステップと、
前記第２の参照画像と前記第１の参照画像との画素の対応関係を求める第１の画像マッチングステップと、
前記第３の参照画像と前記第４の参照画像との画素の対応関係を求める第２の画像マッチングステップと、
前記第２の格子点によって定まる前記第２の参照画像と前記第３の参照画像との画素の対応関係、前記第４の格子点によって定まる前記第３の参照画像と前記第２の参照画像との画素の対応関係、前記第２の参照画像と前記第１の参照画像との画素の前記対応関係、前記第３の参照画像と前記第４の参照画像との画素の前記対応関係、前記第１のオクルージョン領域の情報、および、前記第２のオクルージョン領域の情報、を用いて補間画像を生成する補間画像生成ステップと、
を有することを特徴とする画像補間方法。
【請求項１０】
前記第１のオクルージョン領域検出ステップでは、前記第２の格子点の平衡状態における前記第２の格子を前記第２の格子点を頂点として有する複数の第１評価領域に分割し、前記第１評価領域の各々のオクルージョン信頼度を算出し、閾値より大きい前記オクルージョン信頼度を有する前記第１評価領域を、前記第１のオクルージョン領域として検出し、
前記第２のオクルージョン領域検出ステップでは、前記第４の格子点の平衡状態における前記第４の格子を前記第４の格子点を頂点として有する複数の第２評価領域に分割し、前記第２評価領域の各々のオクルージョン信頼度を算出し、閾値より大きい前記オクルージョン信頼度を有する前記第２評価領域を、前記第２のオクルージョン領域として検出し、
前記補間画像生成ステップでは、前記第１のオクルージョン領域内の各画素の画素値を、前記第２画像と前記第３画像との画素の対応関係から求められる第１画素値と前記第２参照画像と前記第１参照画像との画素の対応関係から求められる第２画素値とを、前記オクルージョン信頼度に応じた重み付きで合成して求め、前記第２のオクルージョン領域内の各画素の画素値を、前記第３画像と前記第２画像との画素の対応関係から求められる第３画素値と前記第３照画像と前記第４参照画像との画素の対応関係から求められる第４画素値とを、前記オクルージョン信頼度に応じた重み付きで合成して求める、ことを特徴とする請求項９に記載の画像補間方法。
【請求項１１】
前記第１および前記第２の画像マッチングステップでは、ブロックマッチング法により対応関係を求めることを特徴とする請求項６または９に記載の画像補間方法。
【請求項１２】
前記第１および前記第２画像マッチングステップでは、オプティカルフロー推定法により対応関係を求めることを特徴とする請求項６または９に記載の画像補間方法。
【請求項１３】
前記第１および前記第２画像マッチングステップではベイズ法により対応関係を求めることを特徴とする請求項６または９に記載の画像補間方法。
【請求項１４】
前記第１および前記第２画像マッチングステップでは勾配法により対応関係を求めることを特徴とする請求項６または９に記載の画像補間方法。
【請求項１５】
平衡状態における前記第２の格子点の分布に基づいて前記第２の参照画像の表面信頼度を算出する第１の表面信頼度算出ステップと、
平衡状態における前記第４の格子点の分布に基づいて前記第３の参照画像の表面信頼度を算出する第２の表面信頼度算出ステップと、
平衡状態における前記第２の格子点の分布に基づいて第１の中間補間画像を生成し、前記第１の参照画像と前記第２の参照画像との画素の対応関係および前記第１のオクルージョン領域に基づいて第２の中間補間画像を生成し、平衡状態における前記第４の格子点の分布に基づいて第３の中間補間画像を生成し、前記第４の参照画像と前記第３の参照画像との画素の対応関係および前記第２のオクルージョン領域に基づいて第４の中間補間画像を生成する中間補間画像生成ステップと、
を有し、
前記補間画像生成ステップは、前記第３の参照画像の表面信頼度、前記第２の参照画像の表面信頼度、前記第１の中間補間画像、前記第２の中間補間画像、前記第３の中間補間画像、および、前記第４の中間補間画像を用いて、前記補間画像を生成する、
請求項９に記載の画像補間方法。
【請求項１６】
前記第１および前記第２の表面信頼度算出ステップでは、隣接する格子点の間の距離が基準より離れている領域には表面ではないと判定し、前記距離が基準より近い領域を表面であると判定して、表面か否かを表す２値の前記表面信頼度を求めることを特徴とする請求項１５に記載の補間画像生成方法。
【請求項１７】
前記第１および前記第２の表面信頼度算出ステップでは、隣接する格子点の間の距離が第１の閾値未満である領域を表面ではないと判定し、前記距離が第２の閾値より大きく第３の閾値未満である領域を表面であると判定して、表面か否かを表す２値の前記表面信頼度を求めることを特徴とする請求項１５に記載の補間画像生成方法。
【請求項１８】
前記第１の表面信頼度算出ステップでは、前記第２の格子点を頂点とする多角形領域の初期状態の面積と平衡状態の面積との差分に基づいて前記第２の参照画像の表面信頼度を算出し、
前記第２の表面信頼度算出ステップでは、前記第４の格子点を頂点とする多角形領域の初期状態の面積と平衡状態の面積との差分に基づいて前記第３の参照画像の表面信頼度を算出する、
ことを特徴とする請求項１５に記載の補間画像方法。
【請求項１９】
前記第１と第２の表面信頼度算出ステップでは、画像間差分が閾値より大きい領域を表面ではないと判定し、前記画像間差分が前記閾値より小さい部分を表面であると判定して、表面か否かを表す２値の前記表面信頼度を算出するすることを特徴とする請求項１５に記載の補間画像方法。
【請求項２０】
前記第１と第２の表面信頼度算出ステップで求められる表面信頼度は確率であり、前記第１と第２の表面信頼度算出ステップは、さらに、算出された表面信頼度が閾値よりも大きい場合には確率１とし、算出された表面信頼度が前記閾値より小さい場合には確率０とするステップを有することを特徴とする請求項１５に補間画像生成方法。
【請求項２１】
前記第１と第２の表面信頼度算出ステップでは、表面信頼度としてシグモイド関数に基づく確率を算出することを特徴とする請求項１５に記載の補間画像生成方法。
【請求項２２】
前記第１と第２の表面信頼度算出ステップでは、表面信頼度としてガウス分布に基づく確率を算出することを特徴とする請求項１５に記載の補間画像生成方法。
【請求項２３】
前記第１の画像マッチングステップでは、前記第２画像を目標画像として前記第１画像を原画像とする画像マッチングを行い、
前記第２の画像マッチングステップでは、前記第３画像を目標画像として前記第４画像を原画像とする画像マッチングを行い、
前記画像マッチングは、
前記原画像に設定した格子点の各々に関して、前記各格子点の初期位置における前記原画像の画素値と前記各格子点の現在位置における前記目的画像の画素値とに基づく画像相関ポテンシャルエネルギーの勾配による力を計算するステップと、
前記各格子点と前記各格子点に隣接する格子点との間の弾性エネルギーから受ける力を計算するステップと、
前記各格子点に作用する摩擦力を計算するステップと、
前記画像相関ポテンシャルエネルギーの勾配による力、前記弾性エネルギーから受ける力、および、前記摩擦力を含む、前記各格子点に関する運動方程式を離散変数法により数値的に解いて、前記各格子点の平衡状態を求めるステップと、
前記各格子点について、初期位置と平衡状態での位置とを用いて前記原画像と前記目標画像との対応関係を求めるマッピングステップと、
を有する請求項１５に記載の補間画像生成方法。
【請求項２４】
前記第１と第２の画像マッチングステップでは、ブロックマッチングを行うことを特徴とする請求項１５に記載の補間画像生成方法。
【請求項２５】
前記第１と第２の画像マッチングステップでは、オプティカルフロー推定によりマッチング処理を行うことを特徴とする請求項１５に記載の補間画像生成方法。
【請求項２６】
前記第１と第２の画像マッチングステップでは、ベイズメソッドを用いたマッチング処理を行うことを特徴とする請求項１５に記載の補間画像生成方法。
【請求項２７】
前記第１と第２の表面信頼度算出ステップで求められる表面信頼度は確率であり、前記第１と第２の表面信頼度算出ステップでは、前記表面信頼度の補集合である裏面信頼度を求め、裏面信頼度が一定値以上の領域を裏面として求め、前記第１の表面信頼度算出ステップによる第１の裏面と、前記第２の表面信頼度算出ステップによる第２の裏面とからマッチングをおこない、対応付けが正確におこなわれているところは表面であると判定するステップを含むことを特徴とする請求項１５に記載の補間画像生成方法。
【請求項２８】
時系列的に並んでいる第１の参照画像と第２の参照画像と第３の参照画像と第４の参照画像とを用いて、前記第２の参照画像と前記第３の参照画像間に補間画像を内挿する画像補間方法において、
前記第２の参照画像上の第１の格子の第１の格子点に対して１対１に写像する第３の参照画像上の第２の格子の第２の格子点に関して、前記第１の格子点の位置および画像情報と第２の格子点の位置及び画像情報とによって求まる画像相関ポテンシャルエネルギーの勾配によって前記第２の格子点が受けるポテンシャル力を計算するステップと、
前記第２の格子点とこの第２の格子点に隣接する前記第２の格子の他の格子点との間の弾性エネルギーから前記第２の格子点が受ける弾性力を計算するステップと、
前記第２の格子点に生じる摩擦力を計算するステップと、
前記ポテンシャル力、前記弾性力、および、前記摩擦力に基づく前記第２の格子点に関する運動方程式を数値解析することによって前記第２の格子点の平衡状態を求める第１の数値解析ステップと、
前記第２の格子点の平衡状態おける前記第２の格子点の分布に基づいて、第１のオクルージョン領域を検出する第１のオクルージョン領域検出ステップと、
前記第３の参照画像上の前記第２の格子の第３の格子点に対して１対１に写像する第４の参照画像上の第４の格子点に関して、前記第３の格子点と第４の格子点の位置によって求まる画像相関ポテンシャルエネルギーの勾配によって前記第４の格子点が受けるポテンシャル力を計算するステップと、
前記第４の格子点とこの第４の格子点に隣接する他の格子点との間の弾性エネルギーから前記第４の格子点が受ける弾性力を計算するステップと、
前記第４の格子点に生じる摩擦力を計算するステップと、
前記ポテンシャル力、前記弾性力、および、前記摩擦力とに基づく第４の格子点に関する運動方程式を数値解析することによって前記第４の格子点の平衡状態を求める第２の数値解析ステップと、
前記第４の格子点の平衡状態における前記第４の格子点の分布に基づいて、第２のオクルージョン領域を検出する第２のオクルージョン領域検出ステップと、
前記第２の参照画像上の第５の格子点に１対１に写像する前記第１の参照画像上の第６の格子点に関して、前記第５の格子点と前記第６の格子点の位置によって求まる画像相関ポテンシャルエネルギーの勾配によって前記第６の格子点が受けるポテンシャル力を計算するステップと、
前記第６の格子点とこの第６の格子点に隣接する格子点との間の弾性エネルギーから受ける弾性力を計算するステップと、
前記第６の格子点に生じる摩擦力を計算するステップと、
前記ポテンシャル力、前記弾性力、および、前記摩擦力とに基づく前記第６の格子点に関する運動方程式を数値解析することによって前記第６の格子点の平衡状態を求める第３の数値解析ステップと、
第３の参照画像上の第７の格子点に１対１に写像する第４の参照画像上の第８の格子点に関して、前記第７の格子点と前記第８の格子点の位置によって求まる画像相関ポテンシャルエネルギーの勾配によって前記第８の格子点が受けるポテンシャル力を計算するステップと、
前記第８の格子点とこの第８の格子点に隣接する格子点との間の弾性エネルギーから前記第８の格子点が受ける弾性力を計算するステップと、
前記第８の格子点に生じる摩擦力を計算するステップと、
前記ポテンシャル力、前記弾性力、および、前記摩擦力とに基づく前記第８の格子点に関する運動方程式を数値解析することによって前記第８の格子点の平衡状態を求める第４の数値解析ステップと、
前記第２の格子点によって定まる対応関係と、前記第４の格子点によって定まる対応関係と、前記第６の格子点によって定まる対応関係と、前記第８の格子点によって定まる対応関係と、前記第１のオクルージョン領域の情報と、前記第２のオクルージョン領域の情報とを用いて補間画像を生成する補間画像生成ステップと、
を有することを特徴とする画像補間方法。
【請求項２９】
第１画像と第２画像との間の対応関係を求める画像マッチング装置において、
第１画像上に設定される第１の格子の第１の格子点に対して１対１に写像する第２画像上に設定される第２の格子の第２の格子点に関して、前記第１の格子点と前記第２の格子点の位置によって求まる画像相関ポテンシャルエネルギーの勾配によって前記第２の格子点が受けるポテンシャル力を計算するポテンシャル力計算部と、
前記第２の格子点とこの第２の格子点に隣接する前記第２の格子の他の格子点との間の弾性エネルギーから前記第２の格子点が受ける弾性力を計算する弾性力計算部と、
前記第２の格子点に生じる摩擦力を計算する摩擦力計算部と、
前記ポテンシャル力、前記弾性力、および、前記摩擦力とに基づく前記第２の格子点に関する運動方程式を数値解析することによって前記第２の格子点の平衡状態を求める数値解析部と、
前記運動方程式の数値解析中に、前記第２の格子点と前記隣接格子点との間の距離に応じて格子点間に新たな格子点を追加する格子点追加部と、
を有することを特徴とする画像マッチング装置。
【請求項３０】
第１画像と第２画像との間の対応関係を求める画像マッチング装置において、
複数の第１格子点を有する第１格子を第１画像上に設定する第１格子設定部と、
前記各第１格子点の各々に一対一に対応する第２格子点を有する第２格子を第２画像上に設定する第２格子設定部と、
前記第２格子点に作用するポテンシャル力を求めるため、前記第１格子点と前記第２格子点との位置関係に基づく画像相関ポテンシャルエネルギーの勾配に応じた画像相関力を求める画像相関力算出部と、前記第２格子点とこの第２格子点に隣接している前記第２の格子の隣接格子点との間の格子点間の距離に応じた弾性力を求める弾性力算出部と、前記第２の格子点に生じる摩擦力を求める摩擦力算出部とを有する作用力算出部と、
前記画像相関力、前記弾性力、および、前記摩擦力を用いて前記第２格子点の位置および速度を数値的に求める数値解析部と、
前記数値解析部によって求められた前記第２格子点の位置に基づいて、前記第２格子点の各々について前記第２格子点と前記隣接格子点との間の格子点間の距離を求める格子点間距離算出部と、
前記格子点間距離が所定の条件を満たす格子点間に第２格子点を追加する格子点追加制御部と、
前記第２格子点が所定の平衡状態に達するまで、前記数値解析部によって求められた前記第２格子点の位置および速度と、前記格子点追加制御部によって追加された第２格子点の位置および速度とを前記作用力算出部に出力する数値解析制御部と、
を具備することを特徴とする画像マッチング装置。
【請求項３１】
前記作用力算出部は、前記格子点追加制御部によって追加された第２格子点に関しても、前記画像相関力、前記弾性力および前記摩擦力を求める、ことを特徴とする請求項３０に記載の画像マッチング装置。
【請求項３２】
第１画像と第２画像との間の対応関係を求める画像マッチング装置において、
複数の第１格子点を有する第１格子を第１画像上に設定する第１格子設定部と、
前記各第１格子点に対応する第２格子点を有する第２格子を第２画像上に設定する第２格子設定部と、
前記第２格子点に作用するポテンシャル力を求めるために、 
前記第１格子点の位置と前記第２格子点との位置と前記第１格子点の画素情報と前記第２格子点の画素情報とに基づく画像相関ポテンシャルエネルギーの勾配に応じた画像相関力を求める画像相関力算出部、
前記第２格子点とこの第２格子点に隣接している前記第２の格子の隣接格子点との間の格子点間距離と可変な弾性係数とに応じた弾性力を求める弾性力算出部、および、
前記第２の格子点に生じる摩擦力を求める摩擦力算出部、
を備える作用力算出部と、
前記画像相関力、前記弾性力、および、前記摩擦力を用いて前記第２格子点の位置および速度を数値的に求める数値解析部と、
前記数値解析部によって求められた前記第２格子点の位置に基づいて、前記第２格子点の各々について前記格子点間距離を求める格子点間距離算出部と、
前記格子点間距離算出部で算出された前記格子点間距離に応じて、前記作用力算出部で弾性力を算出する際に用いられる前記弾性係数の値を段階的に変更する弾性係数制御部と、
前記第２格子点が所定の平衡状態に達するまで、前記数値解析部によって求められた前記第２格子点の位置および速度を前記作用力算出部に出力する数値解析制御部と、
を具備することを特徴とする画像マッチング装置。
【請求項３３】
第１画像と第２画像との間の対応関係を求める画像マッチング方法において、
複数の第１格子点を有する第１格子を第１画像上に設定する第１格子設定ステップと、
前記各第１格子点に対応する第２格子点を有する第２格子を第２画像上に設定する第２格子設定ステップと、
前記第２格子点に作用するポテンシャル力を求めるために、
前記第１格子点の位置と前記第２格子点との位置と前記第１格子点の画素情報と前記第２格子点の画素情報とに基づく画像相関ポテンシャルエネルギーの勾配に応じた画像相関力を求める画像相関力算出ステップ、
前記第２格子点とこの第２格子点に隣接している隣接格子点との間の格子点間距離に応じた弾性力を求める弾性力算出ステップ、および、
摩擦力を求める摩擦力算出ステップ、
を有する作用力算出ステップと、
前記画像相関力、前記弾性力、および、前記摩擦力を用いて前記第２格子点の位置および速度を数値的に求める数値解析ステップと、
前記数値解析ステップによって求められた前記第２格子点の位置に基づいて、前記第２格子点の各々について前記第２格子点と前記隣接格子点との間の格子点間の距離を求める格子点間距離算出ステップと、
前記格子点間距離が所定の条件を満たす格子点間に第２格子点を追加する格子点追加制御ステップと、
前記第２格子点が所定の平衡状態に達するまで、前記数値解析部によって求められた前記第２格子点の位置および速度と、前記格子点追加制御部によって追加された第２格子点の位置および速度とを前記作用力算出ステップにおいて出力する数値解析制御ステップと、
を有することを特徴とする画像マッチング方法。
【請求項３４】
前記作用力算出ステップは、前記格子点追加制御ステップによって追加された第２格子点に関しても、前記画像相関力、前記弾性力および前記摩擦力を求めることを特徴とする請求項３３に記載の画像マッチング方法。
【請求項３５】
第１画像と第２画像との間の対応関係を求める画像マッチング方法において、
複数の第１格子点を有する第１格子を第１画像上に設定する第１格子設定ステップと、
前記各第１格子点に対応する第２格子点を有する第２格子を第２画像上に設定する第２格子設定ステップと、
前記第２格子点に作用するポテンシャル力を求めるために、
前記第１格子点の位置と前記第２格子点との位置と前記第１格子点の画素情報と前記第２格子点の画素情報とに基づく画像相関ポテンシャルエネルギーの勾配に応じた画像相関力を求める画像相関力算出ステップ、
前記第２格子点とこの第２格子点に隣接している隣接格子点との間の格子点間距離と、可変な弾性係数とに応じた弾性力を求める弾性力算出ステップ、および、
摩擦力を求める摩擦力算出ステップ、
を含む作用力算出ステップと、
前記画像相関力、前記弾性力、および、前記摩擦力を用いて前記第２格子点の位置および速度を数値的に求める数値解析ステップと、
前記数値解析ステップによって求められた前記第２格子点の位置に基づいて、前記第２格子点の各々について前記格子点間距離を求める格子点間距離算出ステップと、
前記格子点間距離算出ステップで算出された前記格子点間距離に応じて、前記作用力算出ステップで弾性力を算出する際に用いられる前記弾性係数の値を段階的に変更する弾性係数制御ステップと、
前記第２格子点が所定の平衡状態に達するまで、前記数値解析ステップによって求められた前記第２格子点の位置および速度を出力する数値解析制御ステップと、
を有する画像マッチング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、二つの画像から対応点を検出して画像のマッチングを行う画像マッチング方法およびこれを用いて画像の補間を行う画像補間方法に関する。
【背景技術】
【０００２】
動き検出、ステレオマッチング、画像モーフィング、画像認識、動画像符号化など多くの技術分野において、一つの画像から他方の画像への対応関係を求める画像マッチングの技術は基本的な技術である。
【０００３】
非特許文献１によれば、画像マッチングの技術は大きく分けて４つに分類できる。即ち、オプティカルフロー手法、ブロックベース手法、勾配法、ベイジアン法がある。オプティカルフロー手法は、「輝度の変化は一定である」というオプティカルフロー式を導出しそのオプティカルフロー式を拘束条件としてフローを求めるものである。ブロックベースの手法はブロック毎のテンプレートマッチングによって動きを求める手法である。勾配法は画像の輝度勾配が減少する方向にマッチングを行う手法である。ベイジアンメソッドは確率的にもっともらしいマッチングを求める手法である。
【０００４】
特許文献１には上記の分類には属さない技術として多重解像度フィルタを用いた画像マッチングの方法が開示されている。この手法は複数の多重解像度フィルタによって複数の多重解像度画像ピラミッドを生成し、画像ピラミッドを上から順にマッチング処理を行うことによって大きな動きから小さな動きまでマッチング可能なロバスト性の高いマッチング技術である。
【特許文献１】登録番号2927350
【非特許文献１】A. Murat Tekalp, “Digital Video Processing”, Prentice Hall, 1995
【非特許文献２】J. Nieweglowski, P. Haavisto, “Motion Compensated Video Sequence Interpolation Using Digital Image Warping”, IEEE Acoustics, Speech, and Signal Processing, vol.5, p205-208, 1994
【非特許文献３】J. Nieweglowski, T. George Campbell, P. Haavisto, “A Novel Video Coding Sheme Based on Temporal Prediction Using Digital Image Warping”, IEEE Transactions on , Volume: 39 Issue: 3 , Aug. 1993
【発明の開示】
【発明が解決しようとする課題】
【０００５】
特許文献１には滑らかな写像関係を求める手段が記載されている。しかし写像を滑らかにするという拘束条件が逆に動きの不連続部分にも働いてしまい不連続な写像が表現できないという課題がある。これは従来の画像マッチング手法では必ず発生するトレードオフであり、滑らかにしようとすれば、不連続が表現しにくくなり、不連続を表現しようとすれば滑らかにならないといった問題があった。
【０００６】
本発明は、滑らかにしても不連続の表現が損なわれず、不連続を表現しようとしても滑らかさが得られる画像マッチング方法およびこれを用いた画像補間方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の一局面は、第１画像と第２画像との間の対応関係を求める画像マッチング方法において、複数の第１の格子点を有する第１の格子を第１画像上に設定するステップと、前記第１の格子点の各々に一対一に対応する第２の格子点を有する第２の格子を第２画像上に設定するステップと、前記第１の格子点の位置および画素情報と前記第２の格子点の位置および画素情報とによって求まる画像相関ポテンシャルエネルギーの勾配によって前記第２の格子点が受けるポテンシャル力を計算するステップと、前記第２の格子点とこの第２の格子点に隣接する前記第２の格子の隣接格子点との間の弾性エネルギーから前記第２の格子点が受ける弾性力を計算するステップと、前記第２の格子点に生じる摩擦力を計算するステップと、前記ポテンシャル力、前記弾性力、および、前記摩擦力に基づく前記第２の格子点に関する運動方程式を数値解析することによって前記第２の格子点の平衡状態を求める数値解析ステップと、前記運動方程式の数値解析中に、前記第２の格子点と前記隣接格子点との間の距離に応じて格子点間に新たな格子点を追加する格子点追加ステップとを有することを特徴とする画像マッチング方法を提供する。
【発明の効果】
【０００８】
本発明によると、滑らかにしても不連続の表現が損なわれず、不連続を表現しようとしても滑らかさが得られる画像を生成できる。
【発明を実施するための最良の形態】
【０００９】
［第１の実施形態］
本実施形態を図１のブロック図に従って説明する。図１によると、例えば、メモリなどを含むプロセッサにより構成される画像マッチング部１１がモデル生成モジュール１２と数値解析モジュール１３とを有する。画像マッチング部１１に対象画像と参照画像の２枚の画像が入力されたときに、フレームメモリの両画像の同じ部分、例えば３Ｄ画像の同じ部分をマッチングする。即ち、２つの画像が入ってきたときに力学的な概念を用いて動的なモデルを生成する。この動的モデルが常微分方程式の形でモデル生成モジュール１２から出力されるので、数値解析モジュール１３はその出力を一般の数値解法により反復的に解いていく。反復計算の最終回に得られる結果の画像がマッチングの最終状態となる。本実施形態では、例えば、プロセッサにより構成される格子点追加モジュール１４が追加されており、後述するように逐次反復的に格子点を追加して動的モデルの解析を反復的に行う。
【００１０】
このことを図２を参照して説明すると、例えば９つの格子点を有する格子空間が対象画像および参照画像にそれぞれ仮設される。この場合、格子点と対象画像および参照画像の画像部分（画素）とは対応している。両者の格子空間は同じサイズであり、対応する点は予め設定されている。例えば、対象画像の格子空間の真ん中の点は参照画像の格子空間の真ん中の点に対応する。対応点が決まっている状態において対象画像と参照画像とのマッチングが行われる。このマッチングにおいて運動方程式を作る。運動方程式はある時間に対してそれぞれの点の動きを一意に対応させる。運動方程式をある時間解くことによって画像の格子が適した形に変形するモデルが作れる。例えば、対象物体が移動しているような画像があるとすると、図２に示すように格子点が動いて変形した格子空間が生成される。時間τの経過においてある時間Τのところで計算をストップすると収束した変形格子空間が生成される。これが基本的な動的モデルである。
【００１１】
次に、格子点追加について説明する。図３において、オブジェクトが対象画像では格子点Ｘｎに近接しているが、参照画像では、オブジェクトが格子点Ynから移動している。即ち、参照画像では、バネが伸びることになる。この場合、オブジェクトが移動しているので、元のオブジェクトの位置に空間が出現する。本来は、この空間に格子点を追加しなければならない。そこで、この空間に格子点が図４に示すように追加される。この場合、格子点間の距離が２を越える毎に格子点が追加される。
【００１２】
上記の画像マッチングおよび格子点追加を以下に更に詳しく説明する。
【００１３】
まず、基本となる画像マッチングにおいて、対象画像として以下のようなモデルを考える。
【００１４】
連続画像モデルが数式１に示すように表される。
【数１】
2006260527.tif 000003
【００１５】
これは実数ベースの連続な画像モデルである。ここでは、デジタル画像を対象と考えているので、上記のモデルをサンプリングした以下のサンプリング画像モデルを用いる。
【００１６】
このサンプリング画像モデルは数式２により表される。  
【数２】
2006260527.tif 000004
【００１７】
このとき画像マッチング問題は以下の条件、即ち数式３を満たす動きベクトルd:R3→R2を探す問題として定式化できる。  
【数３】
2006260527.tif 000005
【００１８】
但し、この定式化の場合、暗に同じ対象物の画像値は時間変化をしないと仮定している。また、動きベクトルdが実数なので、右辺は連続画像モデル（数式１）の表記を用いていることに注意を要する。ここでは、対象画像と参照画像、２枚の画像間の画像マッチングを考えているので、等価な数式４を考える。  
【数４】
2006260527.tif 000006
【００１９】
また、動きベクトルも簡単化され、d:R2→R2となる。点xに対して動きベクトルdは一つだけ決まればよいので、動きベクトルdを一意写像とする。x+d(x)はxに対する写像とみなせるので、g(x)=x+d(x)と定義する。ここでg:R2→R2の一意写像である。上記の画像マッチング問題は数式５を満たす写像gを探す問題に帰着する。  
【数５】
2006260527.tif 000007
【００２０】
写像ｇによって決まる点をy=g(x)と定義する。y∈R2である。x=Vnであるからxは格子空間上の点nに一意に対応する。写像gは一意写像であるからyもxに一意に対応する。従ってyはnに一意に対応する。このことは図５で示される。つまりここで取り扱いたい空間は格子空間上の点nによって１対１に対応する変形格子空間である。
【００２１】
以上のようにy=g(x)=g(Vn)なので、nに１対１に対応することを分かりやすくするために、これをyn=g(x)と再定義する。すると画像マッチング問題の式５は数式６を満たすynoptを探す問題に帰着する。  
【数６】
2006260527.tif 000008
【００２２】
画像マッチング問題の数式６を解くためにここでは点ynに対してダイナミクスを導入する。つまり画像マッチング問題を点ynに関する動的システムを解く問題に帰着させる。点ynは周りの点との関係も考慮しつつ数式６を満たす状態に移動していき平衡状態に収束する。その平衡状態によって画像マッチングが完了したものとする。この状態は図２に示すように表される。
【００２３】
点yに対して新たな時間軸τ∈Rを導入し、関数yn(Ｔ)を定義する。ここで初期値は数式７のように正方格子xと同一であるとする。  
【数７】
2006260527.tif 000009
【００２４】
新たな時間軸を導入したので時間に関する微分が数式８のように定義できる。  
【数８】
2006260527.tif 000010
【００２５】
通常ダイナミクスは以下のような常微分方程式９によって記述される。  
【数９】
2006260527.tif 000011
【００２６】
F∈R2は力の総和である。これは運動方程式とも呼ばれる。
【００２７】
次にyn(τ)にかかる力について考える。まずはダイナミクスを駆動させる力となるポテンシャルエネルギーによる力を考える。これはyn(τ)が数式６を満たす状態に移動するための力である。数式５を変形すると、数式１０となる。  
【数１０】
2006260527.tif 000012
【００２８】
通常、数式１０を厳密に満たす点を探すことは、画像に含まれるノイズ成分などにより困難である。そこで数式１１のようなエネルギー関数を考える。  
【数１１】
2006260527.tif 000013
【００２９】
このエネルギー関数Euが最小となる点を探すようにする。最急降下法の原理を用いれば、yn(Ｔ)の周りでエネルギー関数Euの最急降下の方向に下っていくことによりローカルミニマムに行き着くことができる。従って、この最急降下の方向への勾配をyn(τ)に対する力として定義する。エネルギー関数Euは画像の相関とも考えられるので、この力を画像相関ポテンシャルエネルギーによる力Fuとする。
【００３０】
最急降下の方向への勾配を計算する方法は種々考えられるが、ここでは次のような方法を採用する。図６の(a)には対象画像と参照画像と差分値が示されており、図６(b)に示すように、最急降下方向への勾配は局所最適化によって直接求める。画像モデルScは連続の画像モデルだが、実際にはサンプリングされた画像モデルSpしか利用できない。そこで局所最適化もサンプリングされた画像モデルをベースに行う。図６(a)に示すようにyn(τ)にもっとも近いサンプリング点を局所空間中心ycとしたいので、数式１２のように求める。  
【数１２】
2006260527.tif 000014
【００３１】
隣接空間を数式１３のように定義すると、局所探索空間Ωは数式１４のように定義できる。  
【数１３】
2006260527.tif 000015
【００３２】
【数１４】
2006260527.tif 000016
【００３３】
局所最適化をしてその方向へのベクトルを求め、それを正規化し、勾配の大きさをかけると、数式１５が得られる。この式が画像相関ポテンシャルエネルギーによる力（二乗誤差エネルギー）を示す。  
【数１５】
2006260527.tif 000017
【００３４】
実装上の扱い易さ等からエネルギー関数を数式１６と定義した数式１７の画像相関ポテンシャルエネルギーによる力（絶対値差分誤差エネルギー）を用いることもできる。  
【数１６】
2006260527.tif 000018
【００３５】
【数１７】
2006260527.tif 000019
【００３６】
次に、周辺の点との関係を記述する力について考える。マッチング対象の画像は３次元空間を２次元に投影したものだとする。３次元空間上のオブジェクトが剛体とすると、２次元画像では剛体のサーフェスがオブジェクトとして観測されることになる。３次元空間上のオブジェクトが対象画像と参照画像で観測されるとすると、このときそれぞれの画像上で観測されるオブジェクトの位相は保たれる確率が高い。図７に示すように、対象画像オブジェクト上の点xの位置関係は参照画像オブジェクト上の点yn(τ)でも保たれるはずである。この性質は点yn(τ)の間をバネで接続することによってシミュレーションできる。周辺との関係はバネの力Fkによって記述する。以下のように、まずは対象点周辺の格子点空間Nnを定義する。周囲４点であれば数式１８のようになる。  
【数１８】
2006260527.tif 000020
【００３７】
バネ定数（弾性常数）をkとすれば、点yn(τ)にかかるバネの復元力は数式１９で表されるバネ力となる。なお、弾性常数は画像相関エネルギーと弾性エネルギーのバランサーであり、弾性定数が大きければ変形がしにくくなり結果が安定する。しかし画像への適合性が悪くなる。弾性定数が小さければ変形がしやすくなるので画像の適合性が良くなる。ただし結果が柔軟になりすぎる。そこで、現在のところ、このパラメータは経験的に与えられる。挙動はこのパラメータの値にそれほど敏感ではではないので、基本的にはある一定値を固定的に与えられる。
【数１９】
2006260527.tif 000021
【００３８】
周囲４点を接続すると、数式２０のような４点接続バネモデルとなる。  
【数２０】
2006260527.tif 000022
【００３９】
最後に保存されたエネルギーを散逸させる力について考える。yn(τ)にかかる力がFu, Fkのみではエネルギーが保存されてしまうために系が振動する定常状態となってしまう。そこで保存されているエネルギーを散逸させる力を導入する。これには摩擦力が利用できる。速度が一定と近似できる場合には摩擦力は数式２１で記述できる。  
【数２１】
2006260527.tif 000023
【００４０】
以上の力をまとめると運動方程式は数式２２のようになる。
【００４１】
運動方程式
【数２２】
2006260527.tif 000024
【００４２】
画像相関ポテンシャルエネルギーによる力Fuが解析的には解けないため常微分方程式２２は解析的には解けない。従って、システムのτ→∞における極限を取ることは困難である。そこでシステムが収束するのに十分大きな時間Τを考え、数値解析によってt=(0,Τ)区間を計算することによってシステムの収束状態を推定する。
【００４３】
常微分方程式は初期値が決まれば、数値解析によって一意に解が求まる。一般には常微分方程式の初期値問題といわれるものである。この問題の数値解法は数多く存在するが、有名なものではオイラー法、ルンゲクッタ法、ブリルシュ・ストア法、予測子・修正子法、隠的ルンゲクッタ法などがある。ルンゲクッタ法がもっとも有名かつ使用頻度が高い。しかし式２２は画像のサイズ分の次元を持つため複雑な数値解法は適合しにくい。そこでここでは実現が最も簡単なオイラー法を応用することを考える。オイラー法は一階の常微分方程式に対する数値解法なので、まずは式２２を一階の常微分方程式に変換する。このとき、数式２３のように変数変換を行う。
【数２３】
2006260527.tif 000025
【００４４】
この変数変換を数式２２に代入し、数式２４を作る。  
変換された運動方程式
【数２４】
2006260527.tif 000026
【００４５】
常微分方程式２５に対するオイラー法のスキームは数式２６によって表される。  
【数２５】
2006260527.tif 000027
【００４６】
【数２６】
2006260527.tif 000028
【００４７】
これはt(n)からt(n+1)≡t(n)+hへと解を進展させるものである。ここでx(n)はnステップであることを示しており、hはステップ幅である。オイラー法のスキームを数式２４に適用すると、数式２７のオイラー法による更新式が得られる。
【数２７】
2006260527.tif 000029
【００４８】
以上、画像マッチングをアルゴリズムとしてまとめると以下のようになる。
【００４９】
画像マッチングアルゴリズム：
【数２８】
2006260527.tif 000030
【００５０】
次に、格子点追加ステップについて説明する。上記画像マッチングアルゴリズムの２の処理である。
【数２９】
2006260527.tif 000031
【００５１】
格子点を追加する概念を定式化するために図８に示すような不均質の格子点空間を導入する。不均質格子点空間を利用すれば、格子点追加は図９のような形で表すことができる。図９に示したように格子点を一つ追加することによりそこにかかるバネの力は１／２となる。従って、格子点間の距離が２を超えたときにそこに格子点を追加することにより、バネの力はバネが伸びていないときと等価な状態になる。故に、格子点追加アルゴリズムは以下のようになる。
【数３０】
2006260527.tif 000032
【００５２】
格子点の追加をした後はまた画像マッチングステップに戻る。
【００５３】
上記のような格子点の追加を行うと不均質格子点空間を導入することになり、計算の際には複雑性が増してしまう。そこで、格子点追加モデルの解析をしてみると、図１０に示すように、通常のバネモデルではバネ定数kのバネIに接続されている格子点はkIの力を受ける。ここに格子点を一つ追加すると、それぞれのバネがI/2となるので各格子点の受ける力はkI/2となる。これはバネ定数k/2のバネIを考えたときと同様である。つまりバネの間に一つの格子点を追加することはバネ定数を１／２とすることと等価である。ただし、追加された格子点のポテンシャルに関しては考察していないので、あくまでバネモデルとしては等価というだけであり、ポテンシャルを含めた動的マッチングモデル全体としては等価ではない。
【００５４】
また、上記の説明はバネの平衡状態における力の釣り合いを用いており、バネの動的な挙動に関して述べたものではないので、静的には等価であるといっているに過ぎないことに注意が必要である。
【００５５】
バネに格子点をn個追加することはバネ定数を1/(n+1)倍にすることと静的には等価であることが分かる。バネの長さが２になれば一つ格子点を追加し、３になれば２つ格子点を追加し、４になれば３つ格子点を追加し、・・・、というのが格子点追加のアルゴリズムである。これを簡略化する場合にはバネの長さが２になればバネ定数を１／２にし、３になれば、バネ定数を１／３にし、４になれば、バネ定数を１／４にし、・・・、というようにすればよい。このような可変型のバネモデルは以下のように表せる。
【００５６】
簡略型格子点追加のバネモデル
【数３１】
2006260527.tif 000033
【００５７】
他にも例えば線形に変化する線形関数バネモデル
【数３２】
2006260527.tif 000034
【００５８】
ロジスティック関数バネモデル
【数３３】
2006260527.tif 000035
【００５９】
などを用いることもできる。ここでα＞０，β＞０は定数である。
【００６０】
簡略型の格子点追加アルゴリズムは数式２８のバネモデルを使うということである。つまり画像マッチングアルゴリズムにおいて数式２８のバネモデルを使用すればよい。
【００６１】
丸い物体が平行移動するテストパターンによって効果を確認したところ、格子点追加をおこなわない場合、図１１に示す結果が得られた。これによると、オブジェクトの後ろ境界で歪みが発生していることが分かる。それに対して簡略型格子点追加をおこなった場合の結果が図１２に示されている。これによると、オブジェクトの後ろ境界において余計な歪みが発生していないことが確認できる。
【００６２】
以上のように本実施形態では格子点を追加するというアルゴリズムにより動きの不連続性を表現可能な高精度な画像マッチング手法を提供できる。
【００６３】
［第２の実施形態］（片方向オクルージョンモデル）
本実施形態を図１３のブロック図及びフローチャート図１４に従って説明する。本実施形態では、動画に関してオクルージョン領域をうまく対応させた補間をどう行うかが問題設定であり、動画の画像信号が入力され、画像のフレーム間にオクルージョン領域を含めて補間フレームを生成することを目的とする。
【００６４】
補間フレームを生成する際にはオクルージョン問題があり、品質の高い補間フレームの生成は難しかった。本実施形態ではオクルージョン領域に対して適切に補間を行うことにより高品質の補間フレームを生成できる手法を提供する。
【００６５】
概略的には、例えば、時間t1-t2で通常の画像マッチングを行い、時間t2-t3でオクルージョンマッチングを行う。時間t1-t2の通常マッチングの結果からある基準でもってオクルージョン領域の信頼度を求める。この信頼度とオクルージョンマッチングの結果と画像マッチングの結果の３つから合わせて補間フレームを生成する。即ち、オクルージョンフレームに対する補間フレームを生成する。以下に本実施形態を詳細に説明する。
【００６６】
動画の画像信号は各フレームに分解されて処理に回されるものとする。このとき、各フレームはその都度フレームメモリ２１に蓄えられ、同時にいくつかのフレームにアクセスできるようにする。時刻tにおけるフレームを参照フレームtと呼び、時刻t+lΔtのフレームを参照フレームt+lΔtと呼び、時刻t+2lΔtのフレームを参照フレームt+2lΔtと呼ぶことにする。ここでは参照フレームtと参照フレームt+lΔtの間に補間フレームを内挿する。
【００６７】
オクルージョン領域に対して適切に補間を行うためには、オクルージョン領域を適切に検出しなければならない。本実施形態によって適切に検出できる根拠を図１５を用いて説明する。ここでは丸いオブジェクトが左から右に移動する例を示している。参照フレームt+lΔt上では丸いオブジェクトが移動する前の位置に湧き出しのオクルージョン領域が発生する。
【００６８】
ここで丸いオブジェクトの後ろ部分の格子点に注目する、つまり格子点xn, xn+(1,0)Ｔとyn, yn+(1,0)Ｔに注目する。丸いオブジェクトは移動しているので、マッチングがかかっていれば、格子点yn, yn+(1,0)Ｔの間は大きく広がるはずである。つまりyn, yn+(1,0)Ｔの間のバネは伸びている。このようにオブジェクトが移動して湧き出しのオクルージョン領域が発生する場合には、必ずそこのバネが伸びることが分かる。逆にいうとこのように大きくバネが伸びている部分は湧き出しのオクルージョン領域であるということができる。なお、上付きの「Ｔ」は転置を表す。
【００６９】
図１６は２点差線で示す丸いオブジェクトの移動を１次元的に示している。即ち、丸いオブジェクトが下に移動していく様子を示している。時刻tと時刻t+lΔtの間では丸いオブジェクトの後ろ側に湧き出しのオクルージョンが発生している。そしてそのときバネが伸びていることが分かる。丸いオブジェクトがそのまま下に移動していく場合、時刻t+2lΔtを見ると今の湧き出しのオクルージョン領域に対応する部分が見えていることが分かる。つまり参照フレームt+lΔtと参照フレームt+2lΔtでマッチングを行えば、オクルージョン領域に対応する領域を見つけることができる。即ち、物が動いている場合、動いた物により隠れた領域（陰面領域／オクルージョン（occlusion）領域）が出現する。このときの格子点の状態を見ると、物が動いたときオクルージョン領域のバネは伸びている。従って、バネの伸びている長さによってオクルージョンであるかどうかが判定できる。これをオクルージョンマッチングと呼ぶ。
【００７０】
上記の例では、格子点間の距離を評価値として、距離が基準より大きいこと場合にオクルージョンと判定している。
【００７１】
格子点の分布に基づいてオクルージョンを検出することもできる。オクルージョン領域ではバネが伸びているために格子点の分布の密度は小さくなる。したがって、密度をオクルージョンか否かを判定するための評価値として用い、密度が基準より低いことを検出すればよい。例えば、参照フレームt+2lΔtを複数の均等な矩形領域に分割して各領域内の格子点数を数える。この格子点数は、格子点の分布の密度に対応する量である。
【００７２】
あるいは、密度の替わりに格子点に囲まれた領域の面積を用いてオクルージョンを検出することもできる。オクルージョン領域ではバネが伸びて格子点間距離が大きくなるので、格子点に囲まれた領域の面積は大きくなる。したがって、面積をオクルージョンか否かを判定するための評価値として用い、面積が基準より大きい領域を検出すればよい。例えば、格子点を頂点とし内部に他の格子点を含まない三角形の領域の面積や、格子点を頂点とし内部に他の格子点を含まない四角形の領域の面積を用いる。
【００７３】
以上でオクルージョン領域を検出し、オクルージョン領域に対応する領域のマッチングを行えることが分かる。あとはこれらの結果を融合すればよい。以下具体的にブロック図１３及びフローチャート図１４を用いて説明する。
【００７４】
画像マッチングステップＳ２１では、画像マッチングモジュール２２によって参照フレームtを対象画像として参照フレームt+lΔtを参照画像として画像マッチングを行い写像g(;t;lΔt)を求める。画像マッチングステップＳ１１は第１の実施形態と同様の処理を行う。
【００７５】
オクルージョンマッチングステップＳ２２では、オクルージョンマッチングモジュール２３によって参照フレームt+lΔtを対象画像として参照フレームt+2lΔtを参照画像としてオクルージョン領域を見つける画像マッチングを行う。処理的には画像マッチングステップＳ１１と同じである。従って、第１の実施形態の画像マッチングと同様の処理を行う。オクルージョンマッチングを行いオクルージョン写像g(;t+lΔt;lΔt)を求める。
【００７６】
またオクルージョンマッチングモジュールでは通常の画像マッチング手法を用いることも可能である。すなわち非特許文献１に記載されている一般的な動き推定手法、例えば、ブロックマッチングアルゴリズムやオプティカルフロー推定手法、勾配法、ベイズメソッドなどを用いることができる。
【００７７】
ブロックマッチングアルゴリズムを例に挙げて説明する。ブロックマッチングアルゴリズムはブロック内の動きが一様であると仮定して、ブロック内の格子点に対して同じ動きベクトルを割り当てる手法である。
【００７８】
まずは画面全体を複数の、格子点を含んだ（通常は矩形の）ブロックに分割する。ここでは矩形のブロックを採用する。
【数３４】
2006260527.tif 000036
【００７９】
次に、オクルージョン信頼度算出モジュール２４において実行されるオクルージョン信頼度算出ステップＳ２３について述べる。オクルージョン信頼度はその画素がオクルージョン領域であるかどうかの確率分布である。オクルージョン信頼度が１に近いほどオクルージョン領域である確率が高いことを意味する。バネの長さによってオクルージョン領域を検出すると、前述したように実際には領域における信頼度を算出しなければならない。本実施形態では、動画に関してオクルージョン領域をうまく対応させた画素単位の補間をどう行うかが問題設定であるので、図１７に示すように例えばyn, yn+(0,-1)Ｔ、yn+(-1,-1)Ｔで囲まれた三角形の面積を用いる。この三角形の面積はベクトルの外積の絶対値により数式３４によって求まる。なお、上付きの「Ｔ」は転置を表す。
【数３５】
2006260527.tif 000037
【００８０】
三角形xn, xn+(0,-1)Ｔ、xn+(-1,-1)Ｔと三角形xn, xn+(-1,0)Ｔ、xn+(-1,-1)Ｔの面積は１／２であるから、対応する三角形同士の比を取れば、三角形面積比率は数式３６，３７によって表される。なお、上付きの「Ｔ」は転置を表す。
【数３６】
2006260527.tif 000038
【００８１】
次に、これらの三角形の比から確率分布への変換を行う。バネの長さがある一定値を超えていれば、オクルージョンとすると仮定する。この場合は三角形の比がある一定値を超えていれば、オクルージョンとする。このような変換関数として図１８に示すような数式３８に従ったシグモイド関数が利用できる。
【数３７】
2006260527.tif 000039
【００８２】
ここでαは傾きをあらわす定数、βは傾きの中心の座標である。
【００８３】
格子点nにおける三角形をR1(n),R2(n)とする。以下の処理をすべての格子点nに関して行い、数式３９に従ってオクルージョン信頼度マップを生成する。
【数３８】
2006260527.tif 000040
【００８４】
動き補償ステップは動き補償ユニット２５によって行われ、補間フレーム生成モジュール２６によって行われる補間フレーム生成ステップＳ２４と画像相関信頼度算出モジュール２７によって行われる画像相関信頼度算出ステップＳ２５とからなる。補間フレーム生成ステップ内で画像相関信頼度算出ステップを呼び出す。
【００８５】
まず、補間フレーム生成ステップＳ２４について述べる。ここではDigital Image Warping（非特許文献２、非特許文献３）と同様の手法を採用する。Digital Image Warpingでは、四辺形の各点ごとに動きベクトルを求め、四辺形を二つの三角形に分割し、それぞれの三角形ごとに、（非特許文献３に記載のように）３つの頂点によって求まるアフィン変換を算出し、（非特許文献２に記載のように）そのアフィン変換を用いて内挿する三角形の画像値を求めている。
【数３９】
2006260527.tif 000041
【００８６】
上記のアフィン変換を使って、三角形V内の点(u,v)Ｔは[x,y,1]=[u,v,1]Ｔ(V,Y)で表される三角形Y内の点(x,y)Ｔに対応することが算出できる。なお、上付きの「Ｔ」は転置を表す。
【００８７】
上記のアフィン変換を用いて補間フレームを求める。参照フレームtの時間位置を0、参照フレームt+lΔtの時間位置を1として、内挿する補間フレームの時間位置をΔti(0≦Δti≦1)とする。Δtiに応じて写像g（;t;lΔt）を線形変換するとgi(x,t,lΔt)=x+Δtid(x,t,lΔt)となる。補間フレームの生成は図２０に示すようになる。{gi(x1.t;lΔt), gi(x2.t;lΔt), {gi(x3.t;lΔt)}を頂点とする三角形をW、{x1,x2,x3}を頂点とする三角形をX、{g (x1.t;lΔt), g (x2.t;lΔt), {g (x3.t;lΔt)}を頂点とする三角形をYとする。次式４１で示すような補間フレーム上の三角形Ｗ内の点の画素値を求めたい。
【数４０】
2006260527.tif 000042
【００８８】
そこで三角形Wから三角形Xへのアフィン変換と三角形Yへのアフィン変換をそれぞれ数式４０によって求め、それぞれのアフィン変換から点wに対応する画素値を求める。すなわち点wに対応する三角形X内の点は数式４２によって計算できる。
【数４１】
2006260527.tif 000043
【００８９】
同様にして点wに対応する三角形Y内の点は数式４３によって計算できる。
【数４２】
2006260527.tif 000044
【００９０】
時間位置に従って両フレームの重量平均を取れば、写像g(;t;lΔt)による、数式４４の補間フレームによって補間フレームの画素値を計算できる。
【数４３】
2006260527.tif 000045
【００９１】
これを画面内の全三角形に対して行うことにより写像g(;t;lΔt)による補間フレームを生成する。以下のようにオクルージョン信頼度マップより補間フレーム上のオクルージョン信頼度マップを生成する。写像g(;t;lΔt)による補間フレーム上のオクルージョン信頼度マップは数式４５で表される。
【数４４】
2006260527.tif 000046
【００９２】
同様にして画像相関信頼度算出ステップにより数式４６に基づいて写像g(;t;lΔt)による画像相関信頼度マップを生成する。
【数４５】
2006260527.tif 000047
【００９３】
オクルージョンマッチングによるオクルージョン写像g(;t+lΔt;lΔt)は参照フレームt+lΔtから参照フレームt+2lΔtへのマッチングであるので、参照フレームt+lΔtと参照フレームt間の写像にするには数式４７に基づく線形の変換を行う。
【数４６】
2006260527.tif 000048
【００９４】
ここで方向が反対になるので、フレームは−lΔtとした。Δtiに応じてオクルージョン写像g(;t+lΔt;lΔt)を線形変換すると数式４８の像となる。
【数４７】
2006260527.tif 000049
【００９５】
点の対応関係は図２１に示すようになる。ここで{gi,o(x1.t+lΔt;-lΔt), gi,o(x2.t+lΔt;-lΔt), gi,o(x3.t+lΔt;-lΔt)}を頂点とする三角形をWo、{x1,x2,x3}を頂点とする三角形をXo、{go(x1.t+lΔt;-lΔt), go(x2.t+lΔt;-lΔt), go(x3.t+lΔt;-lΔt)}を頂点とする三角形をYoとする。
【００９６】
点wに対応する三角形Xo内の点は数式４９によって計算できる。
【数４８】
2006260527.tif 000050
【００９７】
同様にして点wに対応する三角形Yo内の点は数式５０によって計算できる。
【数４９】
2006260527.tif 000051
【００９８】
時間位置に従って両フレームの重量平均を取れば、オクルージョン写像g(;t+lΔt;lΔt)による補間フレームの画素値を数式５１によって計算できる。
【数５０】
2006260527.tif 000052
【００９９】
これを画面内の全三角形に対して行うことによりオクルージョン写像g(;t+lΔt;lΔt)による補間フレームを生成する。
【０１００】
画像相関信頼度算出ステップＳ２５によりオクルージョン写像g(;t+lΔt;lΔt)による画像相関信頼度マップを数式５２に基づいて生成する。
【数５１】
2006260527.tif 000053
【０１０１】
以上により写像g(;t;lΔt)による補間フレームとオクルージョン写像g(;t+lΔt;lΔt)による補間フレームが生成できたので、これらを信頼度マップによって合成する。画像相関の信頼確率とオクルージョンの信頼確率は互いに独立している。従ってオクルージョンマッチングを採用する確率は確率の乗法定理より数式５２によって表される。  
【数５２】
2006260527.tif 000054
【０１０２】
また、通常のマッチングを採用する確率は数式５４により求められる。  
【数５３】
2006260527.tif 000055
【０１０３】
これらの確率から合成に用いる透明度を数式５５により算出する。  
【数５４】
2006260527.tif 000056
【０１０４】
この透明度を用いて数式５６に基づいて写像による補間フレームとオクルージョン写像による補間フレームを合成する。  
【数５５】
2006260527.tif 000057
【０１０５】
画面全体に対して以上の処理を行うことによって補間フレームSi,p(w,t+lΔti)が生成できる。
【０１０６】
次に、画像相関信頼度算出ステップＳ２５について述べる。これは各点の写像関係による対応点の信頼度を求めるものである。このような信頼度として各点の画素値の差分値を用いることができる。即ち、画像相関信頼度は数式５７によって算出される。
【数５６】
2006260527.tif 000058
【０１０７】
これは画像の差分値が小さくなるほど信頼度が高くなるというモデルである。ただし画像の相関と画素の差分値は一般に線形の相関があるものではない。つまり画素の差分値が小さければ、確かに画像の相関は高いかもしれないが、画素の差分値がある一定値を超えてしまえば、画素の差分値が大きくても少し小さくても画像の相関としては一様に低いと言える。そのような非線形性を導入するには図１９に示すようなシグモイド関数を利用すればよい。これは数式３８においてα＜０としたものである。これを用いれば、画像相関信頼度を数式５８のように定義できる。  
【数５７】
2006260527.tif 000059
【０１０８】
ここでα＞０，β＞０は定数である。  
以上により本実施形態では湧き出しのオクルージョン領域に対応した高品質な補間フレームの生成が可能である。
【０１０９】
［第３の実施形態］（双方向オクルージョンモデル）
本実施形態を図２２のブロック図及び図２３のフローチャートに従って説明する。本実施形態では動画の画像信号が入力され、それらの間に補間フレームを生成することを目的とする。
【０１１０】
補間フレームを生成する際にはオクルージョン問題があり、品質の高い補間フレームの生成は難しかった。第２の実施形態では、湧き出しのオクルージョンに対応する手法を提供した。本実施形態では時間軸の前方と後方の双方向にマッチングを行うことによって、湧き出しのオクルージョンだけでなく消失のオクルージョンにも対応できるようにするものである。
【０１１１】
動画の画像信号は各フレームに分解されて処理に回されるものとする。このとき各フレームはその都度フレームメモリ３１に蓄えられ、同時にいくつかのフレームにアクセスできるようにする。時刻tにおけるフレームを参照フレームtと呼び、時刻t+lΔtのフレームを参照フレームt+lΔtと呼び、時刻t+2lΔtのフレームを参照フレームt+2lΔtと呼び、時刻t-lΔtのフレームを参照フレームt-lΔtと呼ぶことにする。ここでは参照フレームtと参照フレームt+lΔtの間に補間フレームを内挿する。
【０１１２】
第２の実施形態で説明したが、図１５に示すようにバネの伸びが湧き出しのオクルージョン領域に対応する。この場合は、時間軸の前方方向にマッチングをかけているので、前方マッチングに当たる。ただしオブジェクトの前方部分の消失のオクルージョン領域に関しては考慮されていなかった。図２４に示すように、消失のオクルージョン領域は後方マッチングで見ると、湧き出しのオクルージョン領域であることが分かる。そこで、前方マッチングと後方マッチングを組み合わせることによって両方のオクルージョンに対して対策できることが分かる。
【０１１３】
画像マッチングモジュール３２による画像マッチングステップＳ３１では、時間軸の前方と後方にマッチングを行い二つの写像を出力する。内部処理は第１の実施形態の画像マッチングステップと同じである。つまり、参照フレームtを対象画像、参照フレームt+lΔtを参照画像として第１の実施形態の画像マッチングステップを行い、前方マッチング写像g(;t;lΔt)を出力し、参照フレームt+lΔtを対象画像、参照フレームtを参照画像として第１の実施形態の画像マッチングを行い、後方マッチング写像g(;t+lΔt;-lΔt)を出力する。
【０１１４】
オクルージョンマッチングモジュール３３によるオクルージョンマッチングステップＳ３２では、時間軸の前方と後方にマッチングを行い二つのオクルージョン写像を出力する。内部処理は第１の実施形態の画像マッチングと同じである。つまり参照フレームt+lΔtを対象画像、参照フレームt+2lΔtを参照画像として第１の実施形態の画像マッチングを行い前方オクルージョンマッチング写像g(;t+lΔt;lΔt)を出力し、参照フレームtを対象画像、参照フレームt+lΔtを参照画像として第１の実施形態の画像マッチングを行い、後方オクルージョンマッチング写像g(;t;-lΔt)を出力する。
【０１１５】
オクルージョン信頼度算出モジュール３４によるオクルージョン信頼度算出ステップＳ３３は第２の実施形態と同様である。前方マッチング写像g(;t;-lΔt)を元に前方オクルージョン信頼度マップP(y｜g(;t;lΔt))を算出し、後方マッチング写像g(;t+lΔt;-lΔt)を元に後方オクルージョン信頼度マップP(y｜g(;t+lΔt;-lΔt)を算出する。
【０１１６】
動き補償ステップは、補間フレーム生成モジュール３６により行われる補間フレーム生成ステップＳ３４及び画像相関信頼度算出モジュール３７により行われる画像相関信頼度算出ステップＳ３５とからなる。画像相関信頼度算出ステップＳ３５は、第２の実施形態と同様である。補間フレーム生成ステップ内で画像相関信頼度算出ステップを呼び出す。
【０１１７】
前方マッチングによる補間フレームは、第２の実施形態と同様である。すなわち数式２６，２７，２８，２９，３０によって補間フレームと信頼度マップを求める。なお識別のため以下のように補間フレームはそれぞれ添え字を変更する。
【数５８】
2006260527.tif 000060
【０１１８】
参照フレームtの時間位置を0、参照フレームt+lΔtの時間位置を1として、内挿する補間フレームの時間位置をΔti(0≦Δti≦1)とする。Δtiに応じて後方マッチング写像g(;t+lΔt;-lΔt)を線形変換すると数式５９となる。  
【数５９】
2006260527.tif 000061
【０１１９】
{gi (x1.t+lΔt;-lΔt), gi (x2.t+lΔt;-lΔt), gi (x3.t+lΔt;-lΔt)}を頂点とする三角形をWo、{x1,x2,x3}を頂点とする三角形をX、{g(x1.t+lΔt;-lΔt), g(x2.t+lΔt;-lΔt), g(x3.t+lΔt;-lΔt)}を頂点とする三角形をYとする。
【数６０】
2006260527.tif 000062
【０１２０】
そこで三角形Wから三角形Xへのアフィン変換と三角形Yへのアフィン変換をそれぞれ数式３９によって求め、それぞれのアフィン変換から点wに対応する画素値を求める。すなわち点wに対応する三角形X内の点は数式６０によって計算できる。
【数６１】
2006260527.tif 000063
【０１２１】
同様にして点wに対応する三角形Y内の点は数式６１によって計算できる。
【数６２】
2006260527.tif 000064
【０１２２】
時間位置に従って両フレームの重量平均を取れば、後方マッチング写像g(;t+lΔt;-lΔt)による補間フレームの画素値を数式６２によって計算できる。
【数６３】
2006260527.tif 000065
【０１２３】
これを画面内の全三角形に対して行うことにより後方マッチング写像g(;t+lΔt;-lΔt)による補間フレームを生成する。
【０１２４】
以下のように後方オクルージョン信頼度マップP(y｜g(;t+lΔt;-lΔt)より補間フレーム上の後方オクルージョン信頼度マップを生成する。即ち、後方マッチング写像g(;t+lΔt;-lΔt)による補間フレーム上の後方オクルージョン信頼度マップが数式６３により得られる。  
【数６４】
2006260527.tif 000066
【０１２５】
同様にして画像相関信頼度算出ステップにより後方画像相関信頼度マップも生成する。即ち、後方マッチング写像g(;t+lΔt;-lΔt)による後方画像相関信頼度マップが数式６４により得られる。  
【数６５】
2006260527.tif 000067
【０１２６】
後方オクルージョンマッチングによる後方オクルージョン写像g(;t;-lΔt)は参照フレームtから参照フレームt-lΔtへのマッチングであるので、参照フレームt+lΔtと参照フレームt間の写像にするには、go(x,t;lΔt)=x-d(x,t;-lΔt)という線形の変換を行う。ここで方向が反対になるので+lΔtとした。Δtiに応じて後方オクルージョン写像g(;t;-lΔt)を線形変換すると後方オクルージョン写像は数式６５で示す像となる。  
【数６６】
2006260527.tif 000068
【０１２７】
ここで{gi,o (x1.t; lΔt), gi,o (x2.t;lΔt), gi,o (x3.t;lΔt)}を頂点とする三角形をWo、{x1,x2,x3}を頂点とする三角形をXo、{go(x1.t;lΔt), go(x2.t;lΔt), go(x3.t;lΔt)}を頂点とする三角形をYoとする。
【０１２８】
点wに対応する三角形Xo内の点は数式６６により計算できる。
【数６７】
2006260527.tif 000069
【０１２９】
同様にして点wに対応する三角形Yo内の点は数式６７により計算できる。
【数６８】
2006260527.tif 000070
【０１３０】
時間位置に従って両フレームの重量平均を取れば、後方オクルージョン写像g(;t;lΔt)による補間フレームの画素値が数式６８により計算できる。
【数６９】
2006260527.tif 000071
【０１３１】
これを画面内の全三角形に対して行うことにより後方オクルージョン写像g(;t;lΔt)による補間フレームを生成する。画像相関信頼度算出ステップにより後方画像相関信頼度マップを生成する。即ち、数式６９に基づいて後方オクルージョン写像g(;t;lΔt)による後方画像相関信頼度マップが生成される。
【数７０】
2006260527.tif 000072
【０１３２】
以上により前方マッチング写像g(;t;lΔt)による補間フレームと前方オクルージョン写像g(;t+lΔt;lΔt)による補間フレーム、後方マッチング写像g(;t+lΔt;-lΔt)による補間フレームと後方オクルージョン写像g(;t;-lΔt)による補間フレームが生成できたので、これらを信頼度マップによって合成する。
【０１３３】
画像相関の信頼確率とオクルージョンの信頼確率は互いに独立している。従って前方オクルージョンマッチングを採用する確率は確率の乗法定理より数式７０で表せる。
【数７１】
2006260527.tif 000073
【０１３４】
また、前方マッチングを採用する確率は数式７１で表せる。
【数７２】
2006260527.tif 000074
【０１３５】
後方オクルージョンマッチングを採用する確率は数式７２で表せる。
【数７３】
2006260527.tif 000075
【０１３６】
後方マッチングを採用する確率は数式７３で表せる。
【数７４】
2006260527.tif 000076
【０１３７】
これらの確率から合成に用いる透明度を数式７４により算出する。
【数７５】
2006260527.tif 000077
【０１３８】
この透明度を用いて数式７３に従って信頼度による合成を行う。
【数７６】
2006260527.tif 000078
【０１３９】
画面全体に対して以上の処理を行うことによって補間フレームSi,p(w,t+lΔti)が生成できる。
【０１４０】
［第４の実施形態］
本実施形態の画像マッチング装置を図２５のブロック図を参照して説明する。本実施形態も先の実施形態と同様に動画の画像信号が入力され、それらの間に補間フレームを生成するために使用される画像マッチング装置を提供する。補間フレームを生成する際にはオクルージョン問題があり品質の高い補間フレームの生成は難しかった。本実施形態ではオクルージョン領域に対して適切に補間をおこなうことにより高品質の補間フレームを生成できる手法を用いた画像マッチング装置を提供する。
【０１４１】
図２５に示す構成によると、フレームメモリ４１に画像信号が入力される。フレームメモリ４１は前方マッチングユニット４２と後方マッチングユニット４３に接続される。前方及び後方マッチングユニット４２，４３の出力は画像合成ユニット４４に接続される。
【０１４２】
前方マッチングユニット４２は入力画像信号とフレームメモリ４１の記憶画像信号とが入力される画像マッチング部４２−１及びオクルージョンマッチング部４２−２を有する。前方マッチングユニット４２は更に画像マッチング部４２−１に縦接続される表面信頼度算出部４２−３，４２−４，４２−５及び補間フレーム生成部４２−６を有する。
【０１４３】
同様に後方マッチングユニット４３は入力画像信号とフレームメモリ４１の記憶画像信号とが入力される画像マッチング部４３−１及びオクルージョンマッチング部４３−２を有する。後方マッチングユニット４３は更に画像マッチング部４３−１に縦接続される表面信頼度算出部４３−３，４３−４，４３−５及び補間フレーム生成部４３−６を有する。
【０１４４】
上記構成において、動画の画像信号は各フレームに分解されて処理されるが、このとき各フレームはその都度フレームメモリ４１に蓄えられ、同時にいくつかのフレームにアクセスできるようになっている。本実施形態では、時刻tにおけるフレームを参照フレームtと呼び、時刻t+lΔtのフレームを参照フレームt+lΔtと呼び、時刻t+2lΔtのフレームを参照フレームt+2lΔtと呼び、時刻t+lΔtのフレームを参照フレームt+lΔtと呼ぶことにする。ここでは参照フレームtと参照フレームt+lΔtの間に補間フレームを内挿する。
【０１４５】
オクルージョン領域に対して適切に補間をおこなうためには、オクルージョン領域を適切に検出しなければならない。本実施形態によって適切に検出できる根拠を図２６を用いて説明する。ここでは丸いオブジェクトが左から右に移動する例を示している。参照フレームt+lΔt上では図２６の薄い丸で示したように丸いオブジェクトが移動する前の位置に湧き出しのオクルージョン領域が発生する。ここで丸いオブジェクトの後ろ部分の格子点に注目する、つまり格子点xn, xn+(1,0)Τとyn, yn+(1,0)Τに注目する。丸いオブジェクトは移動しているので、マッチングがかかっていれば、格子点yn, yn+(1,0)Τの間は大きく広がるはずである。つまりyn, yn+(1,0)Τの間のバネは伸びている。このようにオブジェクトが移動して湧き出しのオクルージョン領域が発生する場合には必ずそこのバネが伸びることが分かる。逆にいうとこのように大きくバネが伸びている部分は湧き出しのオクルージョン領域であるということができる。
【０１４６】
図１６を参照して説明したように時刻tと時刻t+lΔtの間では丸いオブジェクトの後ろ側に湧き出しのオクルージョンが発生している。そしてそのときバネが伸びていることが分かる。丸いオブジェクトがそのまま下に移動していく場合、時刻t+2lΔtを見ると今の湧き出しのオクルージョン領域に対応する部分が見えていることが分かる。つまり参照フレームt+lΔtと参照フレームt+2lΔtでマッチングをおこなえばオクルージョン領域に対応する領域を見つけることができる。これをオクルージョンマッチングと呼ぶ。
【０１４７】
図２６に示すようにバネの伸びが湧き出しのオクルージョン領域に対応する。この場合は、時間軸の前方方向にマッチングをかけているので、前方マッチングに相当する。ただし、オブジェクトの前方部分の消失のオクルージョン領域に関しては考慮されていなかった。図２７に示すように、消失のオクルージョン領域は後方マッチングで見ると湧き出しのオクルージョン領域であることが分かる。そこで前方マッチングと後方マッチングを組み合わせることによって両方のオクルージョンに対して対策できることが分かる。
【０１４８】
以上でオクルージョン領域を検出し、オクルージョン領域に対応する領域のマッチングをおこなえることが分かる。
【０１４９】
上記ではバネの伸びによってわき出しのオクルージョン領域を検出できることが分かる。このことは表面の信頼度を算出できることを意味する。バネの伸びだけでなく複数の情報から表面の信頼度を算出できれば、それらの同時確率によってより精度の高い検出が可能になると考えられる。
【０１５０】
以下の特徴を考えてみる。
【０１５１】
オブジェクトが動いた前後にオクルージョンが発生する。前が消失のオクルージョンで後ろが湧き出しのオクルージョンである。
【０１５２】
動的マッチングでは、オブジェクト後ろはバネが伸び、オブジェクト前はバネが縮むという幾何学的な特徴がある。
【０１５３】
特徴１，２より、バネの伸びにより湧き出しのオクルージョンを検出し、バネの縮みにより消失のオクルージョンの検出ができる。図２８がこのことを示している。バネの伸びによる湧き出しのオクルージョンの検出だけでは不足な理由を図２９を参照して以下に説明する。
【０１５４】
時間軸の双方向にマッチングをかけて前方マッチングと後方マッチングをおこなったとする。このとき前方マッチングによりオブジェクト後方のオクルージョン領域が得られ、後方マッチングによりオブジェクト前方のオクルージョン領域が得られる。それら２つのオクルージョンマップを足し合わせれば、図２９の右上のような理想的な結果が得られる。しかし図２９の下側の図に示すように、必ずしもオクルージョンマップが正しく得られるとは限らない。その場合、単純にＯＲを取ってしまうとオブジェクトが欠けてしまったりして画質が劣化してしまう。
【０１５５】
それに対してバネの縮みによる消失のオクルージョンも同時に検出した場合を考えてみる。この場合の例を図３０を用いて説明する。この場合も先ほどと同様に時間軸に双方向にマッチングをおこなうものとする。そのとき前方マッチングの結果からバネの縮みと伸びに対応する２つのオクルージョンマップが得られる。また後方マッチングの結果からも２つのオクルージョンマップが得られる。このとき図２９の下側の図に示すように、前方マッチングの湧き出しのオクルージョン領域(uncovered occlusion)と後方マッチングの消失のオクルージョン領域(covered occlusion)は同じ意味のものを指していると言える。即ち、同じオクルージョン領域を２つの視点から見たものである。これら２つのマップは一つの事象に対して２つの視点からの結果であり、それらの同時確率を求めることによって１つの結果に依存しないよりロバストな結果が得られる。よって図３０に示すように２つのマップの同時確率を求めて（ＡＮＤ）、それら２つの結果のＯＲを取ることによってロバストなオクルージョンマップが得られると考えられる。
【０１５６】
図３１に示すように、実際に先ほどと同じようにオクルージョンマップが正しく得られなかったとしても、この方法であればロバストにオクルージョンマップを得ることができる。更にマッチングの結果の写像そのものの信頼度を求めることによって、その同時確率も加えることによってよりロバストな結果が得られると考えられる。
【０１５７】
マッチングをどのようにおこなうか、マッチングステップについて説明する。対象画像と参照画像が入力されたとき、対象画像から参照画像への対応点のマッチングつまり写像関係を出力する画像マッチング方法を図３２のブロック回路を参照して説明する。図２には、参照画像と対象画像が入力される離散変数ユニット５１の出力がフレームメモリ５２及び画像相関ポテンシャル力計算ユニット５３、弾性エネルギー計算ユニット５４及び摩擦力計算ユニット５５に提供される。
【０１５８】
まずは、このブロック回路に対して問題設定をおこなう。対象とする画像として以下のようなモデルを考える。
【０１５９】
連続画像モデル
【数７７】
2006260527.tif 000079
【０１６０】
これは実数ベースの連続な画像モデルである。本実施形態では、デジタル画像を対象と考えているので、上記のモデルをサンプリングした以下のモデルを用いる。
【０１６１】
サンプリング画像モデル
【数７８】
2006260527.tif 000080
【０１６２】
画像マッチングは、対象画像上の点が参照画像上のどの点に対応するのかを求める問題である。このとき画像マッチング問題は以下の条件式を満たす動きベクトルd:X×T→Xを探す問題として定式化できる。
【数７９】
2006260527.tif 000081
【０１６３】
また動きベクトルdが実数なので右辺は連続画像モデル式７７の表記を用いていることに注意が必要である。ここでは対象画像と参照画像、２枚の画像間の画像マッチングを考えているので等価な以下の問題を考える。
【数８０】
2006260527.tif 000082
【０１６４】
また動きベクトルも簡単化されd:X→Xとなる。点xに対して動きベクトルdは１つだけ決まれば良いので動きベクトルdを一意写像とする。x+d(x)はxに対する写像とみなせるので次式で定義する。
【数８１】
2006260527.tif 000083
【０１６５】
ここでg:X→Xの一意写像である。上記の画像マッチング問題は次式を満たす写像gを探す問題に帰着する。
【０１６６】
画像マッチング問題
【数８２】
2006260527.tif 000084
【０１６７】
ここで写像gによって決まる点を次式で定義する。
【数８３】
2006260527.tif 000085
【０１６８】
ここでy∈Xである。x=Vnであるからxは格子空間上の点nに一意に対応する。
【０１６９】
写像gは一意写像であるからyもxに一意に対応する。よってyはnに一意に対応する。このことを図で表すと図５のようになる。つまりここで取り扱いたい空間は格子空間上の点nによって１対１に対応する変形格子空間である。
【０１７０】
以上のようにy=g(x)=g(Vn)なので、nに１対１に対応することを分かりやすくするために、これを次式で再定義する。
【数８４】
2006260527.tif 000086
【０１７１】
すると画像マッチング問題（数式３）は次式を満たすynを探す問題に帰着する。
【０１７２】
画像マッチング問題
【数８５】
2006260527.tif 000087
【０１７３】
次に問題解決の手段について説明する。画像マッチング問題の式８４を解くために、ここではエネルギー関数を次式のように定義する。
【０１７４】
エネルギー関数
【数８６】
2006260527.tif 000088
【０１７５】
画像マッチング問題の式８４を画面全体のエネルギー関数の最小化問題として以下のような最適化問題として定式化する。
【０１７６】
最適化問題
【数８７】
2006260527.tif 000089
【０１７７】
ここでEuは画像エネルギーでEkは弾性エネルギーとする。これはSnakes[“M. Kass, A. Witkin and D. Terzopoulos, “Snakes: Active Contour Models”, International Journal of Computer Vision, 1, 4, pp.321-331, 1988”]やActive Net[“坂上、山本、”動的な網のモデルActive Netとその領域抽出への応用”, テレビ学誌, 45, 10, pp.1155-1163, 1991”]、CPF[“Y. Shinagawa and T. L. Kunii, “Unconstrained Automatic Image Matching Using Multiresolutional Critical-Point Filters”, IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol.20, No.9, 1998”]で用いられて成功しているアプローチである。
【０１７８】
Euに関しては以下のように説明される。式８４を変形すると次式となる。
【数８８】
2006260527.tif 000090
【０１７９】
となるが、通常式８７を厳密に満たす点を探すことは画像に含まれるノイズ成分などにより困難である。そこで次のようなエネルギー関数を考える。
【数８９】
2006260527.tif 000091
【０１８０】
このエネルギー関数Euが最小となる点を探すよ。
【０１８１】
Ｅkに関しては以下のように説明される。マッチング対象の画像は３次元空間を２次元に投影したものだとする。３次元空間上のオブジェクトが剛体とすると、２次元画像では剛体のサーフェスがオブジェクトとして観測されることになる。３次元空間上のオブジェクトが対象画像と参照画像で観測されるとすると、このときそれぞれの画像上で観測されるオブジェクトの位相は保たれる確率が高い。図７に示すように、対象画像オブジェクト上の点xの位置関係は参照画像オブジェクト上の点ynでも保たれるはずである。このような特性を再現するにはynがバネで構成されたネットのようなものだと考えると都合がよい。つまり弾性エネルギーを導入すればよい。
【０１８２】
よってエネルギー関数の式８５によるエネルギー最小化式８６は、できるだけ式８４が成り立つようにかつ全体が滑らかになるような解を探すことになる。
【０１８３】
SnakesやActive Netでは式８６から次式の最適性必要条件を求める。
【０１８４】
最適性必要条件
【数９０】
2006260527.tif 000092
【０１８５】
これを解くことにより解を求めている。これはエネルギー関数（数式５）を満たす静的な釣り合いの条件を求めていることになる。
【０１８６】
本手法では運動エネルギーΤを導入することにより動的な解法を構築する。点yの動的な挙動に興味があるので、点yに対して新たな時間軸τ∈Rを導入し関数yn(τ)を定義する。新たな時間軸を導入したので時間に関する微分が以下のように定義できる。
【数９１】
2006260527.tif 000093
【０１８７】
そこで運動エネルギーを次式として定義する。
【０１８８】
運動エネルギー
【数９２】
2006260527.tif 000094
【０１８９】
ラグランジアンを以下のように定義する。
【０１９０】
ラグランジアン
【数９３】
2006260527.tif 000095
【０１９１】
このとき変分原理を満たす運動方程式は次式９３のように得られる。
【０１９２】
オイラー方程式
【数９４】
2006260527.tif 000096
【０１９３】
これを展開すると次式の運動方程式が得られる。
【０１９４】
運動方程式
【数９５】
2006260527.tif 000097
【０１９５】
しかし運動方程式９４に従った運動は保存系であり、エネルギー保存則により解は収束しない。そこで系を非保存系にするために次式９５の摩擦エネルギーを導入する。
【０１９６】
摩擦エネルギー
【数９６】
2006260527.tif 000098
【０１９７】
ここでμ>0は動摩擦係数である。摩擦エネルギーを導入した場合のオイラー方程式は以下のようになる。
【０１９８】
摩擦エネルギーの入ったオイラー方程式
【数９７】
2006260527.tif 000099
【０１９９】
これを解くことにより運動方程式９７が得られる。
【０２００】
摩擦の入った運動方程式
【数９８】
2006260527.tif 000100
【０２０１】
これら静的なエネルギー関数と動的なエネルギー関数は直感的には以下のように対比される。図３３に示すように静的なエネルギー関数Ｕによる最適化では、静的な釣り合いの位置を求めるように探索がおこなわれる。そのため基本的には初期値に最も近い釣り合いの位置が求まる。つまり初期値に最も近い局所的最適点が求まるということである。しかし図３３にも示してあるように必ずしも局所最適点が大域的最適点ではない。このように静的なエネルギー関数による最適化では強い初期値依存性がある。
【０２０２】
それに対して本手法のような動的な最適化では、動的な運動の中で探索がおこなわれる。正確には探索が運動として表現されている。よって図３４に示すように最初の位置エネルギーが運動エネルギーに変換されるため局所最適点から飛び出ることが可能となっている。これにより静的なエネルギー関数を用いるよりもより広い範囲を探索できる。よって静的なエネルギー関数を使うよりも、初期値依存性が低くなる可能性と、ノイズ等の影響に対してよりロバストになる可能性がある。
【０２０３】
次に、動的な探索、つまり運動方程式（数式１５）に従った解が最適化問題（数式６）に対する最適性必要条件を満たすことを証明する。
【０２０４】
１．探索が完了したと仮定する。するとyは完全に停止、つまり次式９８が成り立つ。
【数９９】
2006260527.tif 000101
【０２０５】
このとき運動方程式９７より
【数１００】
2006260527.tif 000102
【０２０６】
であるから次式１００が成り立つ。
【数１０１】
2006260527.tif 000103
【０２０７】
よって最適性必要条件式８９を満たす。ゆえに探索が完了したときその点は最適である。
【０２０８】
２．ｙが静止したとする。すると次式１０１が成り立つ。
【数１０２】
2006260527.tif 000104
【０２０９】
このとき運動方程式９７より次式１０２が得られる。
【数１０３】
2006260527.tif 000105
【０２１０】
今yが最適点であるとすると最適性必要条件式８９より
【数１０４】
2006260527.tif 000106
【０２１１】
となり探索が完了する。
【０２１２】
yが最適点でないならば加速度が生じるため探索は完了しない、つまり最適点以外で探索が完了することはない。
【０２１３】
３．摩擦エネルギーの性質より
【数１０５】
2006260527.tif 000107
【０２１４】
つまり運動は停止する。ゆえにいつかは探索が完了する。
【０２１５】
以上１、２，３より運動方程式（数式１５）にしたがった運動は最適化問題式８６に対する最適性の必要条件が満たされる。
【０２１６】
２次の最適性必要条件については一部で満たされない。ポテンシャルの山の頂上で探索が終了することがあり得るからである。そこでポテンシャルの山の頂上では探索が完了しないという条件、つまり
【数１０６】
2006260527.tif 000108
【０２１７】
を仮定すれば２次の最適性必要条件も証明される。この追加の仮定に関してはアルゴリズムにたいして
【数１０７】
2006260527.tif 000109
【０２１８】
ということを要請することによって達成できる。
【０２１９】
以上より運動方程式９７に従った探索は最適化問題式８６に対する最適解を与え、従来の静的な探索に比べてロバストであることが示唆された。
【数１０８】
2006260527.tif 000110
【０２２０】
というように分解できるのでそれぞれについて検討する。
【数１０９】
2006260527.tif 000111
【０２２１】
勾配を計算する方法は色々考えられるがここでは次のような方法を採用する。数式７に示すように、勾配は局所最適化によって直接求める。画像モデルScは連続の画像モデルだが、実際にはサンプリングされた画像モデルSpしか利用できない。そこで局所最適化もサンプリングされた画像モデルをベースにおこなう。yn(τ)にもっとも近いサンプリング点を局所空間中心ycとしたいので次式１０７のように求める。
【数１１０】
2006260527.tif 000112
【０２２２】
局所最適化をしてその方向へのベクトルを求め、それを正規化し勾配の大きさをかけると次式が得られる。
【０２２３】
画像エネルギーによる力（二乗誤差エネルギー）
【数１１１】
2006260527.tif 000113
【０２２４】
実装上の扱いやすさ等からエネルギー関数を次式１１１と定義した画像エネルギーによる力の式１１２を用いることもできる。
【数１１２】
2006260527.tif 000114
【０２２５】
画像エネルギーによる力（絶対値差分誤差エネルギー）
【数１１３】
2006260527.tif 000115
【０２２６】
弾性体が多様体Mにより構成されているとし、M上の点を次式１１３とする。
【数１１４】
2006260527.tif 000116
【０２２７】
弾性エネルギーの１次微分項は次式１１５で表される。
【数１１５】
2006260527.tif 000117
【０２２８】
これは弾性体の収縮を表すエネルギーである。ｙで微分すると
【数１１６】
2006260527.tif 000118
【０２２９】
ここで
【数１１７】
2006260527.tif 000119
【０２３０】
上記多様体Mが格子点を連結したバネモデルで実現されているとし、偏微分を差分方程式で近似する。
【数１１８】
2006260527.tif 000120
【０２３１】
これを式１１７に代入して整理すれば式１１９の４点接続バネモデルが得られる。
【０２３２】
４点接続バネモデル
【数１１９】
2006260527.tif 000121
【０２３３】
以上をまとめると運動方程式は次式のようになる。
【０２３４】
運動方程式
【数１２０】
2006260527.tif 000122
【０２３５】
画像エネルギーによる力Fuが解析的には解けないため常微分方程式（数式１９）は解析的には解けない。よってシステムのτ→∞における極限を取ることは困難である。そこでシステムが収束するのに十分大きな時間Τを考え、数値解析によってt=(0,Τ)区間を計算することによってシステムの収束状態を推定する。
【０２３６】
常微分方程式は初期値が決まれば離散変数法によって一意に解が求まる。一般には常微分方程式の初期値問題といわれるものである。この問題の数値解法は数多く存在するが、有名なものではオイラー法、ルンゲクッタ法、ブリルシュ・ストア法、予測子・修正子法、隠的ルンゲクッタ法などの方法がある。ルンゲクッタ法がもっとも有名かつ使用頻度が高い。しかし式１２１は画像のサイズ分の次元を持つため複雑な数値解法は適合しにくい。そこでここでは実現が最も簡単なオイラー法を応用することを考える。
【０２３７】
オイラー法は一階の常微分方程式に対する数値解法なので、まずは数式１９を一階の常微分方程式に変換する。変数変換を式１２２で施すと、変換された運動方程式１２３が得られる。
【０２３８】
変数変換
【数１２１】
2006260527.tif 000123
【０２３９】
常微分方程式１２４に対するに対するオイラー法のスキームは式１２５となる。
【数１２２】
2006260527.tif 000124
【０２４０】
オイラー法のスキーム
【数１２３】
2006260527.tif 000125
【０２４１】
ここでx(n)はｎステップであることを示しており、hはステップ幅である。オイラー法のスキームを式１２３に適用すると次式１２６の更新式が得られる。
【０２４２】
オイラー法による更新式
よってこの更新式を繰り返し解くことにより収束状態を求めることができる。
【０２４３】
次に補間フレーム生成ステップについて説明する。ここではDigital Image Warping1[“J. Nieweglowski, P. Haavisto, “Motion Compensated Video Sequence Interpolation Using Digital Image Warping”, IEEE Acoustics, Speech, and Signal Processing, vol.5, p205-208, 1994”, ” J. Nieweglowski, T. George Campbell, P. Haavisto, “A Novel Video Coding Sheme Based on Temporal Prediction Using Digital Image Warping”, IEEE Transactions on , Volume: 39 Issue: 3 , Aug. 1993”]と同様の手法を採用する。Digital Image Warpingでは、四辺形の各点ごとに動きベクトルを求め、四辺形を二つの三角形に分割し、それぞれの三角形ごとに、３つの頂点によって求まるアフィン変換を算出し、そのアフィン変換を用いて内挿する三角形の画像値を求めている。
【数１２４】
2006260527.tif 000126
【０２４４】
上記のアフィン変換を使って、三角形V内の点(u,v)Τは次式１２８であらわされる三角形Y内の点(x,y)Τに対応することが算出できる。
【数１２５】
2006260527.tif 000127
【０２４５】
上記のアフィン変換を用いて補間フレームを求める。参照フレームtの時間位置を0、参照フレームt+lΔtの時間位置を1として、内挿する補間フレームの時間位置をΔti(0≦Δti≦1)とする。Δtiに応じて写像g(・,t;lΔt)を線形変換すると次式１２９となる。
【数１２６】
2006260527.tif 000128
【０２４６】
そこで三角形Wから三角形Xへのアフィン変換と三角形Yへのアフィン変換をそれぞれ数式２４によって求め、それぞれのアフィン変換から点wに対応する画素値を求める。
【０２４７】
すなわち点wに対応する三角形X内の点は次式１３０によって計算できる。
【数１２７】
2006260527.tif 000129
【０２４８】
同様にして点wに対応する三角形Y内の点は次式１３１によって計算できる。
【数１２８】
2006260527.tif 000130
【０２４９】
時間位置に従って両フレームの重量平均を取れば、次式１３２によって補間フレームの画素値を計算できる。
【数１２９】
2006260527.tif 000131
【０２５０】
ここで式１２３の右辺は連続画像モデルで書かれている。そのため実際には離散の画像モデルから右辺を計算するためにbi-linear法によって画素値を補間して計算する。これを画面内の全三角形に対しておこなうことにより写像g(・,t;lΔt)による補間フレームを生成する。
【０２５１】
表面信頼度算出１ステップについて説明する。バネの伸びている部分をオクルージョンとして信頼度の高い領域とするのという哲学だったので、逆にいえばバネの変化していない部分が表面として信頼度が高いといえる。
【０２５２】
実際には領域における信頼度を算出しなければならないため図１７に示すように例えば
【数１３０】
2006260527.tif 000132
【０２５３】
で囲まれた三角形の面積を用いる。元の三角形の面積はベクトルの外積の絶対値により次式１３３のように求まる。
【数１３１】
2006260527.tif 000133
【０２５４】
同様にして写像後の三角形の面積が次式１３４によって求まる。
【数１３２】
2006260527.tif 000134
【０２５５】
よって面積の差分値を次式１３５とする。
【数１３３】
2006260527.tif 000135
【０２５６】
差分値が０に近いほど表面の確率が高くなり、差分値が大きくなるほど表面の確率が低くなるとすると、これは差分値が任意の閾値よりも大きければ０とし、小さければ１とすれば都合がよい。
【０２５７】
表面信頼度算出２ステップについて説明する。Coveredなオクルージョン領域（消失のオクルージョン領域）の格子点は理想的には０に縮んでしまうという幾何学的な特性がある。これはuncoveredなオクルージョン領域（湧き出しのオクルージョン領域）が伸びているのと対称的である。Uncoveredなオクルージョン領域の信頼確率は伸びと関連づけたので、coveredなオクルージョン領域の信頼確率は縮みと関連づけるのは自然であろう。
【０２５８】
つまりこれまでは伸びも縮みも等価に扱っていたものを、ここでは伸びと縮みによって異なる信頼確率を生成するようにする。これは理論の対象性からも自然なことのように思われる。
【０２５９】
そこで表面信頼度算出１ステップでも用いた面積の差分を用いて、差分が閾値よりも大きければ０を、小さければ１を設定するようにする。
【０２６０】
続いて表面信頼度算出３ステップについて説明する。これは写像の信頼度が確かならばそれは表面としても確からしいという確率である。これを格子点xに写像g(x)が与えられた元での画像Sk2(・)のもっともらしさとしてモデル化する。一般的にはこれは尤度といわれる。観測される画像にはノイズが加わるとして、格子点xと写像g(x)の画素値を次式１３６によって表す。
【数１３４】
2006260527.tif 000136
【０２６１】
Displaced Pixel Difference（以下DPD）を次式１３７のようにモデル化する。
【数１３５】
2006260527.tif 000137
【０２６２】
このDPDが閾値よりも小さければもっともらしいので確率１を、大きければ確率０を設定する。
【０２６３】
図２５を用いて実際の構成を説明する。
【０２６４】
前方マッチング（４２）、後方マッチング（４３）の両ステップは入力するフレームの違いだけなので、オクルージョン付きマッチングステップとして以下のようにまとめる。なお前方マッチングの場合は入力フレームを読み替えなくても良いが、後方マッチングの場合は
【数１３６】
2006260527.tif 000138
【０２６５】
のように読み替える。また出力結果に対して、前方マッチングの場合にはfを添え字し、後方マッチングの場合にはbを添え字する。
【０２６６】
オクルージョン付きマッチングステップ（図３５）
【数１３７】
2006260527.tif 000139
【０２６７】
【数１３８】
2006260527.tif 000140
【０２６８】
【数１３９】
2006260527.tif 000141
【０２６９】
【数１４０】
2006260527.tif 000142
【０２７０】
【数１４１】
2006260527.tif 000143
【０２７１】
【数１４２】
2006260527.tif 000144
【０２７２】
次に、合成ステップについて説明する。
【数１４３】
2006260527.tif 000145
【０２７３】
以下では、図３２に示すブロック図に従って各ステップの具体的な説明をおこなう。
【０２７４】
離散変数法ステップでは、離散変数法の更新式１２６に従って位置と速度を更新させ、初期値からあらかじめ設定された時刻Τまでの計算をおこなう。ここではオイラー法による離散変数法を用いる。具体的には図３６に示すフローチャートに従って計算をおこなう。その中で、後述する画像力計算ステップ、弾性エネルギー力計算ステップ、摩擦力計算ステップを用いる。
【０２７５】
画像力計算ステップでは、画像相関によるポテンシャルエネルギーによって発生する力Fμを計算する。
【数１４４】
2006260527.tif 000146
【０２７６】
具体的には図３７に示すフローチャートに従って計算をおこなう。なお式１１２に従っても良い。
【０２７７】
弾性エネルギー力計算ステップでは、弾性エネルギーによって発生する力Fkを計算する。
【数１４５】
2006260527.tif 000147
【０２７８】
具体的には図３８に示すフローチャートに従って計算をおこなう。
【０２７９】
摩擦力計算ステップでは、動摩擦力によって発生する力Fμを計算する。
【数１４６】
2006260527.tif 000148
【０２８０】
具体的には図３９に示すフローチャートに従って計算をおこなう。
【数１４７】
2006260527.tif 000149
【０２８１】
具体的には図４０に従って計算をおこなう。
【０２８２】
以上本実施例によりオクルージョン領域に適切な絵を補間可能なロバストで高画質な補間フレームが提供できる。
【０２８３】
［第５の実施形態］
本実施形態も図２５のブロック図を参照して説明する。
【０２８４】
第４の実施形態では、表面信頼度算出１，２，３ステップにおいて閾値による確率化をおこなった。この場合、閾値より大きければ１，小さければ０というように２値の確率しか表現できない。
【０２８５】
そこでより滑らかで精度の高い確率表現を得るために本実施例では以下のようなシグモイド関数を用いる。
【数１４８】
2006260527.tif 000150
【０２８６】
以下の部分については、第３の実施形態より変更する。
【０２８７】
表面信頼度算出１ステップ
【数１４９】
2006260527.tif 000151
【０２８８】
【数１５０】
2006260527.tif 000152
【０２８９】
表面信頼度算出２ステップ
【数１５１】
2006260527.tif 000153
【０２９０】
本実施例の構成により、より滑らかな確率マップが得られるためより高画質な補間フレームが提供できる。
【０２９１】
［第６の実施形態］
本実施形態も図２５のブロック図を参照して説明する。
【０２９２】
本実施例では表面信頼度の確率をガウス分布にしたがった確率分布として記述することにより、よりロバストな表面信頼度を得るものである。
【０２９３】
表面信頼度算出１ステップについて。バネの伸びている部分をオクルージョンとして信頼度の高い領域とするのという哲学だったので、逆にいえばバネの変化していない部分が表面として信頼度が高いといえる。
【０２９４】
実際には領域における信頼度を算出しなければならないため図１７に示すように例えば
【数１５２】
2006260527.tif 000154
【０２９５】
で囲まれた三角形の面積を用いる。元の三角形の面積はベクトルの外積の絶対値により以下のように求まる。
【数１５３】
2006260527.tif 000155
【０２９６】
同様にして写像後の三角形の面積が
【数１５４】
2006260527.tif 000156
【０２９７】
とする。差分値が０に近いほど表面の確率が高くなり、差分値が大きくなるほど表面の確率が低くなるとすると、これは差分値が平均０、分散σ２のガウス分布に従うと考えると妥当である。よって差分値Rの確率密度関数は以下のようにモデル化できる。
【数１５５】
2006260527.tif 000157
【０２９８】
これは確率密度関数であるから分布関数は
【数１５６】
2006260527.tif 000158
【０２９９】
となる。よって差分値R(n)がaからbの間に存在する確率は
【数１５７】
2006260527.tif 000159
【０３００】
で与えられる。
【０３０１】
差分値R(n)=0が得られたときの信頼度を95%にしたいとすると
【数１５８】
2006260527.tif 000160
【０３０２】
とすればよい。よってある差分値が得られたときの表面の確率を次式１４２と定義する。
【０３０３】
表面の確率
【数１５９】
2006260527.tif 000161
【０３０４】
これが三角形内側の表面の信頼度であるからこれを三角形の内側に割り当てメモリする。
【数１６０】
2006260527.tif 000162
【０３０５】
を構築する。
【０３０６】
次に表面信頼度算出３ステップについて述べる。写像の信頼度を確率としてモデル化する。
【数１６１】
2006260527.tif 000163
【０３０７】
一般的にはこれは尤度といわれる。
【０３０８】
観測される画像にはノイズが加わるとして、格子点xと写像g(x)の画素値を
【数１６２】
2006260527.tif 000164
【０３０９】
ここでε１，ε２は加法性ノイズである。Displaced Pixel Difference（以下DPD）を以下のようにモデル化する。
【数１６３】
2006260527.tif 000165
【０３１０】
観測されるノイズが平均０、分散σ２のガウス分布に従うと仮定すると、あるDPDxの尤度は確率密度関数（probability density function, pdf）として次式１４３のように記述できる。
【０３１１】
尤度
【数１６４】
2006260527.tif 000166
【０３１２】
これは確率密度関数であるから分布関数は
【数１６５】
2006260527.tif 000167
【０３１３】
よってあるDPDが得られたときの写像g(x)の確率を次式１４４と定義する。
【０３１４】
写像g(x)の確率
【数１６６】
2006260527.tif 000168
【０３１５】
表面信頼度算出２ステップについて述べる。Covered occlusion（消失なオクルージョン領域）は変形して圧縮されている領域とする。
【数１６７】
2006260527.tif 000169
【０３１６】
を定義する。これらの面積の差分を
【数１６８】
2006260527.tif 000170
【０３１７】
とする。ここでSは面積を算出するオペレータとする。この差分値r(n)が負ならば圧縮されているということである。
【０３１８】
ここで画面全体が単一の領域であるとすると差分値R(n)の分布がガウス分布に従うとしても良さそうである。もし画面が複数領域からなり、covered occlusionが発生しているとするとその領域の差分値R(n)は外れ値として分布する可能性が高い。よって差分値R(n)が０に近いほど表面である確率が高いという信頼度を構築する。
【０３１９】
差分値Rの確率密度関数は以下のようにモデル化できる。
【数１６９】
2006260527.tif 000171
【０３２０】
これは確率密度関数であるから分布関数は
【数１７０】
2006260527.tif 000172
【０３２１】
となる。よって差分値R(n)がaからbの間に存在する確率は
【数１７１】
2006260527.tif 000173
【０３２２】
で与えられる。
【０３２３】
差分値R(n)=0が得られたときの信頼度を95%にしたいとすると
【数１７２】
2006260527.tif 000174
【０３２４】
とすればよい。よってある差分値が得られたときの表面の確率を次式１４５と定義する。
【０３２５】
表面の確率
【数１７３】
2006260527.tif 000175
【０３２６】
実際の構成は以下のようになる。
【０３２７】
表面信頼度算出１ステップ
【数１７４】
2006260527.tif 000176
【０３２８】
表面信頼算出３ステップ
【数１７５】
2006260527.tif 000177
【０３２９】
【数１７６】
2006260527.tif 000178
【０３３０】
表面信頼度算出２ステップ
【数１７７】
2006260527.tif 000179
【０３３１】
以上、本誌実施の形態により表面信頼度の確率をガウス分布にしたがった確率分布として記述することにより、よりロバストな表面信頼度を得ることができ、より高画質な補間フレームを提供できる。
【０３３２】
［第７の実施形態］
本実施形態も図２５のブロック図を参照して説明する。
【０３３３】
背景が静止しているような画像の場合、オクルージョン領域が発生しうるのはフレーム間で変化のある部分のみである。フレーム間で変化のある部分はフレーム間差分を取ると検出することができる。よってこのフレーム間差分から表面信頼度を算出可能である。
【０３３４】
表面信頼度算出４ステップについて説明する。観測される画像にはノイズが加わるとして、フレーム間の画素値を
【数１７８】
2006260527.tif 000180
【０３３５】
ここでε１，ε２は加法性ノイズである。Pixel Difference（以下PD）を以下のようにモデル化する。
【数１７９】
2006260527.tif 000181
【０３３６】
ここでこのPDが任意の閾値よりも小さければ確率１を、大きければ確率０を与えるなどとすることができる。
【０３３７】
また上記のように閾値モデルではなく、ガウス分布モデルに従った以下のような方法でも良い。観測されるノイズが平均０、分散σ２のガウス分布に従うと仮定すると、あるPDxの尤度は確率密度関数（probability density function, pdf）として次式１４６のように記述できる。
【０３３８】
尤度
【数１８０】
2006260527.tif 000182
【０３３９】
これは確率密度関数であるから分布関数は
【数１８１】
2006260527.tif 000183
【０３４０】
となる。よってPDγ(x)がaからbの間に存在する確率は
【数１８２】
2006260527.tif 000184
【０３４１】
で与えられる。静止領域では対応する画素同士の差分値がゼロになるとすると、静止のPDはノイズ成分に等しい。よってノイズの定義から、静止のＰＤは平均０、分散σ２のガウス分布に従っていることになる。静止のPDでの信頼度をガウス分布の信頼区間により設定する。例えば静止のPDに95%の信頼度を持たせたい場合は
【数１８３】
2006260527.tif 000185
【０３４２】
とすればよい。よってあるPDが得られたときの表面の確率を次式１４７と定義する。
【０３４３】
表面の確率
【数１８４】
2006260527.tif 000186
【０３４４】
ここで分散σ２は任意の値を設定しても良いし、Ｍ推定によって与えられた画像から反復的に求めることもできる。
【０３４５】
よって表面信頼度算出４ステップを以下のように構成する。
【０３４６】
表面信頼算出４ステップ
【数１８５】
2006260527.tif 000187
【０３４７】
また背景が完全に静止しているならば、オクルージョンマッチングはおこなわずに、背景そのものをそのまま持ってきても良い。
【０３４８】
第４の実施形態に対して合成ステップに関しても改良を加える。
【数１８６】
2006260527.tif 000188
【数１８７】
2006260527.tif 000189
【０３４９】
以上本実施例により、背景が静止している場合において高画質な補間フレームを提供することができる。
【０３５０】
［第８の実施形態］
画面全体が単一の領域の場合には第６の実施形態のようなガウス分布に従うといっても構わないが、複数領域からなる場合には必ずしもガウス分布に従うとは限らない。そのため精度が低下してしまうこともありうる。そこで本実施例ではガウス分布から外れる領域をＭ推定によって弾くことにより複数領域に対しても精度良くするものである。
【０３５１】
Covered occlusionは変形して圧縮されている領域とする。
【数１８８】
2006260527.tif 000190
【０３５２】
ここでSは面積を算出するオペレータとする。この差分値R(n)が負ならば圧縮されているということである。
【０３５３】
ここで画面全体が単一の領域であるとすると差分値R(n)の分布がガウス分布に従うとしても良さそうである。もし画面が複数領域からなり、covered occlusionが発生しているとするとその領域の差分値R(n)は外れ値として分布する可能性が高い。よって差分値R(n)が０に近いほど表面である確率が高いという信頼度を構築する。
【０３５４】
差分値Rの確率密度関数は以下のようにモデル化できる。
【数１８９】
2006260527.tif 000191
【０３５５】
これは確率密度関数であるから分布関数は
【数１９０】
2006260527.tif 000192
【０３５６】
よってある差分値が得られたときの表面の確率を次式１４８と定義する。
【０３５７】
表面の確率
【数１９１】
2006260527.tif 000193
【０３５８】
複数領域の場合の表面確率
【数１９２】
2006260527.tif 000194
【０３５９】
この確率wはＭ推定の重み関数と関連づけることができる。Ｍ推定の重み関数は平均に近いほど１に近くなり外れるほど０に近くなる関数だからである。
【０３６０】
Ｍ推定の枠組みでモデル化する。Covered occlusionに関して考えたいので圧縮方向のみを対象にする。すなわち伸びている領域は無視したいのでR(n)<1の点を対象とする（R(n)≧1は伸びている領域である）。
【数１９３】
2006260527.tif 000195
【０３６１】
と定義できる。TukeyのBiweight法によると重み関数は
【数１９４】
2006260527.tif 000196
【０３６２】
のように構成できる。ここでc>0は定数であり、正規分布の場合にはc=6.0となる。この重み関数を用いて標本平均、標本偏差が以下のように計算できる。
【数１９５】
2006260527.tif 000197
【０３６３】
ここで上付はイテレーションをあらわす。標本平均＆偏差の計算と重み関数の計算を交互にＩ回イテレーションさせることによってＭ推定を構成する。
【０３６４】
このＭ推定の結果を使って上記の確率を拡張すると以下のようにモデル化できる。
【数１９６】
2006260527.tif 000198
【０３６５】
以上本実施例によって画面が複数の領域からなる場合でも精度良い補間フレームを提供できる。
【０３６６】
［第９の実施形態］
本実施形態も図２５のブロック図を参照して説明する。上記実施形態では、バネの伸びや縮みによってオクルージョン領域を検出する方法が提供されている。マッチングが正確におこなわれていれば、バネが伸びたり縮んだりするのはオクルージョンの領域だと判定ができるが、マッチングが不正確だとバネの伸びや縮みがマッチングミスに起因することがある。そこで本実施形態はマッチングミスを検出し補正することにより高画質な補間フレームを生成できる方法を提供する。
【０３６７】
図４１は、第９の実施形態に従った画像マッチング方法を実施する画像マッチング装置のブロック図を示している。これによると、入力画像信号を記憶するフレームメモリ４１が設けられる。このフレームメモリ４１は前方マッチングユニット４２及び後方マッチングユニット４３に結合され、記憶画像信号をこれらマッチングユニットに入力する。前方及び後方マッチングユニット４２，４３は入力画像信号も入力されおり両信号に基づきマッチング処理を行う。前方及び後方マッチングユニット４２，４３の出力は表面信頼度算出ユニット４５，４６にそれぞれ接続される。表面信頼度算出ユニット４５，４６の出力はマッチングユニット４７に接続されると共に合成ユニット４８に接続される。
【０３６８】
図４２に示すように、オブジェクトが左から右に移動する画像にマッチングをかけたとする。このときマッチングが正しければオブジェクトの格子は対応するオブジェクト上に移動するはずだが、誤マッチングによりオブジェクトが検出できなかったとすると、オブジェクト上の格子点は参照画像上の背景上に位置することになる。しかし、このままでは画像エネルギーが高いため非常に不安定である。そのため周りの少しでも画像エネルギーが低いところを目指して移動する。結果としてそこにはバネの伸びが観測されることになる。
【０３６９】
同様のことは逆側からマッチングをかけても起こる。よって前方と後方でマッチングできなかった領域がそれぞれバネの伸びとして検出される。つまり検出できなかった領域がオクルージョン領域に混じって検出されている可能性が高いと言える。そこでオクルージョン領域同士を再度マッチングかけることによって誤マッチングを補正できる。
【０３７０】
表面信頼度算出４ステップを説明する。
【０３７１】
前方マッチングユニット４２と対応するものを第１の表面信頼度算出ステップ、後方マッチングユニットに対応するものを第２の表面信頼度算出ステップとする。まずは、表面信頼度算出ステップ１の表面信頼度マップの補集合を取り裏面信頼度を求める。または表面信頼度算出ステップ２の表面信頼度マップとの積確率を求め、その補集合を取っても良い。
【０３７２】
裏面信頼度が閾値（例えば０．５）以上の領域を裏面として検出する。それぞれを第１の裏面、第２の裏面とする。参照フレームtを第２の裏面でマスクしたものをマスク参照フレームt、参照フレームt+lΔtを第１の裏面でマスクしたものをマスク参照フレームt+lΔtとする。
【０３７３】
マスク参照フレームtを対象画像、マスク参照フレームt+lΔtを参照画像としてマッチングをおこない前方マッチング写像を求め、マスク参照フレームt+lΔtを対象画像、マスク参照フレームtを参照画像としてマッチングをおこない後方マッチング写像を求める。例えば表面信頼度算出３ステップを用いて前記前方マッチング写像と後方マッチング写像の信頼度を求め、誤マッチング時の表面信頼度とする。
【０３７４】
次に前記表面信頼度算出４ステップの結果も含めて、第４の実施形態のような合成をおこなうことにより、誤マッチングも上手く補償したより高画質な補間フレームを生成できる。
【図面の簡単な説明】
【０３７５】
【図１】本発明の第１の実施形態に従った画像マッチング方法を実行する画像マッチング装置のブロック図
【図２】画像マッチング問題ｙｎに対するダイナミクスを示す図
【図３】別オブジェクトの隣接格子関係を示す図
【図４】格子点追加の概念図
【図５】各空間の繋がりを示す図
【図６】画像相関ポテンシャルエネルギーによる力の想定図
【図７】対象画像上のオブジェクトと参照画像のオブジェクトの位相が保たれる状態を示す図
【図８】不均質格子点空間を示す図
【図９】格子点追加を説明する図
【図１０】格子点追加モデルの解析を説明する図
【図１１】格子点追加をおこなわない場合の写像を示す図
【図１２】簡略型格子点追加をおこなった場合の写像を示す図
【図１３】第２の実施形態による画像マッチング方法を実行する画像マッチング装置のブロック図
【図１４】第２の実施形態の画像マッチング方法を示すフローチャート図
【図１５】オクルージョン領域を示す図
【図１６】オクルージョンマッチングによる解決を説明するための図
【図１７】オクルージョン信頼度を説明するための図
【図１８】シグモイド関数を示す図
【図１９】シグモイド関数を示す図
【図２０】補間方法を説明するための図
【図２１】オクルージョンマッチング補間方法を説明するための図
【図２２】第３の実施形態による画像マッチング方法を実行する画像マッチング装置のブロック図
【図２３】第３の実施形態の画像マッチング方法を示すフローチャート図
【図２４】後方マッチングによるオクルージョン領域を示す図
【図２５】本発明の第４の実施形態に従った画像マッチング方法を実行する画像マッチング装置のブロック図。
【図２６】各空間の繋がりを示す図。
【図２７】後方マッチングによるオクルージョン領域を示す図。
【図２８】バネの延びと縮みにより前後のオクルージョンが検出できることを説明する図。
【図２９】湧き出しの検出だけでは不足であることを説明する図。
【図３０】複数の信頼度による合成を説明する図。
【図３１】正しいマップが得られなかったとしてもロバストがあることを示す図。
【図３２】マッチングステップを実行する概略装置のブロック図。
【図３３】静的なエネルギー関数による最適化を説明する図。
【図３４】静的なエネルギー関数による最適化を説明する図。
【図３５】第４の実施形態の画像マッチング方法を実施するフローチャート図。
【図３６】離散変数法の手順を示すフローチャート。
【図３７】画像相関によるポテンシャルエネルギーによって発生する力を計算する手順を示すフローチャート図。
【図３８】弾性エネルギーによる力を計算する手順を示すフローチャート図。
【図３９】摩擦力を計算する手順を示すフローチャート図
【図４０】補間計算の手順を示すフローチャート図。
【図４１】第９の実施形態に従った画像マッチング方法を実施する画像マッチング装置のブロック図。
【図４２】誤マッチングがバネの延びとして現れる状態を示す図。
【符号の説明】
【０３７６】
１１…画像マッチングユニット、１２…モデル生成モジュール、１３…数値解析モジュール、１４…格子点追加モジュール、２１、３１…フレームメモリ、２２、３２…画像マッチングモジュール、２３、３３…オクルージョンマッチングモジュール、２４、３４…オクルージョン信頼度算出モジュール、２５、３５…動き補償ユニット、２６、３６…補間フレーム生成モジュール、２７、３７…画像相関信頼度算出モジュール、１４…フレームメモリ、４２…前方マッチングユニット、４３…後方マッチングユニット、４４…合成ユニット、４５…表面信頼度計算ユニット、４６…表面信頼度計算ユニット、４７…マッチングユニット、４８…合成ユニット、５１…離散変数ユニット、５３…画像相関ポテンシャル力計算ユニット、５４…弾性エネルギー力計算ユニット、５５…摩擦力計算ユニット
【図１】
2006260527.tif 000199
【図２】
2006260527.tif 000200
【図３】
2006260527.tif 000201
【図４】
2006260527.tif 000202
【図５】
2006260527.tif 000203
【図６】
2006260527.tif 000204
【図７】
2006260527.tif 000205
【図８】
2006260527.tif 000206
【図９】
2006260527.tif 000207
【図１０】
2006260527.tif 000208
【図１１】
2006260527.tif 000209
【図１２】
2006260527.tif 000210
【図１３】
2006260527.tif 000211
【図１４】
2006260527.tif 000212
【図１５】
2006260527.tif 000213
【図１６】
2006260527.tif 000214
【図１７】
2006260527.tif 000215
【図１８】
2006260527.tif 000216
【図１９】
2006260527.tif 000217
【図２０】
2006260527.tif 000218
【図２１】
2006260527.tif 000219
【図２２】
2006260527.tif 000220
【図２３】
2006260527.tif 000221
【図２４】
2006260527.tif 000222
【図２５】
2006260527.tif 000223
【図２６】
2006260527.tif 000224
【図２７】
2006260527.tif 000225
【図２８】
2006260527.tif 000226
【図２９】
2006260527.tif 000227
【図３０】
2006260527.tif 000228
【図３１】
2006260527.tif 000229
【図３２】
2006260527.tif 000230
【図３３】
2006260527.tif 000231
【図３４】
2006260527.tif 000232
【図３５】
2006260527.tif 000233
【図３６】
2006260527.tif 000234
【図３７】
2006260527.tif 000235
【図３８】
2006260527.tif 000236
【図３９】
2006260527.tif 000237
【図４０】
2006260527.tif 000238
【図４１】
2006260527.tif 000239
【図４２】
2006260527.tif 000240