(57)【特許請求の範囲】
【請求項１】
コンピュータにより、カメラによって生成されるビデオシーケンスのうちの２枚のビデオフレーム間のアフィン大域的動きを推定する方法であって、
オプティカルフロー拘束方程式を解き、
前記オプティカルフロー拘束方程式と、大域的動き推定があてはまる画素を優先するための重みとに関連する最小二乗関数を反復して最小化し、
前記最小化は、潜在的なアフィン大域的動きの集合を表すグループ化された並進動きベクトルの集合のベクトルで複数回初期化されることでアフィン大域的動き推定の集合を取得し、
前記並進動きベクトルは、ブロックマッチングに基づく位相相関により算出されるそれぞれのベクトルで類似の並進動きベクトルをグループ化することで算出され、
考慮中の前記大域的動き推定により現在のフレームが動き補償された後に、前記アフィン大域的動き推定の集合の中から、前記オプティカルフロー拘束方程式の時間的な勾配の二乗の平均を最小化する一つを選び、
前記平均は、前記オプティカルフロー拘束方程式の前記時間的な勾配の二乗が所定の閾値未満の場合に、前記大域的動き推定があてはまる画素により求められることを特徴とする方法。
【請求項２】
前記最小化は、２枚の前のフレーム間で計算される前記アフィン大域的動きに従って初期化されることを特徴とする請求項１記載の方法。
【請求項３】
前記重みは、反復毎に計算されノイズの分散に関連付けられたスケーリング係数に依存することを特徴とする請求項１記載の方法。
【請求項４】
前記推定は多重分解能動き推定により行なわれることを特徴とする請求項１記載の方法。
【請求項５】
ユークリッド距離に従って動きベクトルのグループ分けが行なわれることを特徴とする請求項１記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ビデオシーケンス中の２枚の連続したフレーム間の支配的な動きを推定する方法に関する。この方法はあらゆる種類のシーン又はカメラの動きのコンフィギュレーションに対し有効である。
【０００２】
【従来の技術】
主要な動き、すなわち、支配的な動きを推定することは、２枚の連続フレーム間ではっきりした動きを推定若しくはセグメンテーションする処理のために重要なステップである。稠密な動きフィールド推定の場合に、この重要なステップは、フレームの大部分に亘る真の明白な動きに近似した初期的な動きを与えることによって上記処理を著しく加速する。特に、支配的な動きが一定ではないとき、すなわち、純粋に並進的な明白な動きではなく、ズーム若しくはカメラの光軸回りの回転のような複雑な動きであるときに上記処理が著しく加速される。上記ステップは、動きセグメンテーション処理の場合に、フレーム全体並びにフレームの領域に適用されるので、領域の動きを識別する基本的なステップを表わす。
【０００３】
２枚の連続フレーム間で支配的な動きを推定するため非常に一般的に使用される方法は、ロバスト的なセグメンテーション法に基づいている。以下では、この方法は、「ロバスト回帰大域的動き推定」と称される。ロバスト回帰大域的動き推定アルゴリズムの主要な特徴は以下の通りである。
【０００４】
・非常に少ないパラメータで支配的な動きを表現する大域的動きモデルを使用する。殆どの場合に、明白な動きの物理的なリアリティと計算的な複雑さとの間で優れた妥協点を与えるアフィン動きモデルが選択される。アフィン動きモデルは、移動、パン、チルト、ズーム及びこれらが組み合わされた動きのようなカメラの動きによって生じた明白な動きを優れた近似で表現する。
【０００５】
・このモデルのパラメータの推定は、外れ値（アウトライアー）、すなわち、支配的な動きとは異なる動きを有する画素を、推定処理から理論的に推定することができるロバスト回帰アルゴリズムを用いて行なわれる。
【０００６】
・この処理は先見的な稠密動きフィールド推定を用いることなく働かせてもよい。大域的動き推定処理のため使用されるデータはソースフレームである。この処理は、周知のオプティカルフロー拘束によって、各画素の輝度関数の推定された時空的（空間・時間的）な勾配に基づく。
【０００７】
・この処理は、大きい動き振幅を取り扱うため、多重分解能スキームで実現してもよい。
【０００８】
【発明が解決しようとする課題】
殆どの場合に、このようなタイプのアルゴリズムは、満足できる結果を与え、支配的な動きを識別することができる。しかし、この従来技術による処理は、大域的な動きの初期値に強く依存する。一般的に、大域的動きは、初期的には零に設定される。また、推定処理が失敗し、良くない大域的動きが得られる多数のコンフィギュレーションが存在する。ソースフレームにテクスチャ情報が不足し、大きい均一領域が含まれる場合に、この従来の処理は、実際の支配的な動きが大きい場合でも、一般的に小さい振幅の動きに収束する。この現象は、特に、カメラによって追跡される大きな前景対象物が背景シーンの上を動き場合にみられる。
【０００９】
この問題は、簡単に説明すると、動きの観察が時空的な勾配に基づいて行なわれ、この観察は、均一な領域若しくはテクスチャの少ない領域に関して明らかに非常に僅かな情報しか与えないということである。このような領域がフレームの大半を占める場合、従来のアルゴリズムは正しい動き値に収束することができず、小さい動きが動き観察に巧く適合すると考えられる。
【００１０】
本発明の目的は上記の従来技術における主要な制限を解決することである。
【００１１】
【課題を解決するための手段】
本発明は、２枚のフレームの間で支配的な動きを推定する方法に関する。本発明の方法は、推定のロバスト性を高めるため、位相相関ピーク検出アルゴリズムと、多重分解能ロバスト回帰アルゴリズムとを組み合わせる。
【００１２】
【発明の実施の形態】
以下、本発明の特徴の一部を表わす実施例、並びに、図１及び２を用いて本発明を説明する。
【００１３】
本発明は、殆どのシーン及びカメラのコンフィギュレーションで機能する汎用的な大域的動き推定処理を実現する。このアルゴリズムは、位相相関ピーク検出法と多重分解能ロバスト回帰法の二つの大域的動き推定方法を組み合わせる。
【００１４】
位相相関ピーク検出アルゴリズムは、２枚のフレーム間でウィンドウに亘って大域的並進運動を推定する高速、効率的なアルゴリズムである。以下に説明する方法において、位相相関ピーク検出アルゴリズムは、多重分解能ロバスト回帰アルゴリズムに潜在的な初期化を行なうため使用される。初期化毎に、多重分解能ロバスト回帰アルゴリズムは大域的動き推定量を計算する。最後のステップでは、最良の推定量が選択される。
【００１５】
図１は、本発明によって実現された汎用的な大域的動き推定処理を説明するフローチャートである。時刻（時点）をｔで表わし、２枚のソースフレームをＩt及びＩt-1で表わすとき、図１に示されたステップ１〜ステップ５は以下の通りである。
【００１６】
ステップ１：相関ピーク検出アルゴリズムを用いて、フレーム内の数個の異なるウィンドウに亘る並進運動が推定される。図２には、一例として５個のウィンドウが使用されるウィンドウ配置が示されている。たとえば、大域的動きが当てはまる画素領域に依存して移動ウィンドウを使用してもよい。
【００１７】
ステップ２：並進運動は類似した運動毎にグループ分けされる。ステップ１で推定されたＮ個の並進運動ベクトルからＰ個の並進運動ベクトルが定義される（Ｐ≦Ｎ）。
【００１８】
ステップ３：種々の利用可能な初期値を用いて、多重分解能ロバスト回帰アルゴリズムを実施して、フレームに亘る大域的動きの推定が行なわれる。動きは、残存する各並進運動ベクトルと、前の時点に推定された前の最終的な大域的動き（フレームＩt-2からフレームＩt-1までの動き）との和から得られる。一番最初の推定時に、この大域的動きは零に設定されている。
【００１９】
ステップ４：最良の推定大域的動きが選択される。
【００２０】
ステップ５：最終的な支配的な動きベクトルが、処理されるべき次のソースフレームに対しステップ２及び３で使用するため、前の支配的な動きベクトルとして記憶される。
【００２１】
以下、大域的動き推定処理を詳述する。
【００２２】
ビデオシーケンス中の2次元の明白な動きのアフィンモデル化は、計算の複雑さ（６個のパラメータを識別すればよいこと）と、物理的なリアリティ（２次元の明白な動きの正確な表現であること）との間の最良の妥協策の一つである。
【００２３】
使用される動きモデルは以下の通りである。フレーム内の点（ｘ，ｙ）の２次元動きベクトルは、６個の動きパラメータ
θ＝（ａ，ｂ，α，β，γ，δ）T
を用いて、式１：
【００２４】
【数１】
0004547066.tif 000002
のようにモデル化される。位相相関ピーク検出アルゴリズムはステップ１で実施される。位相相関の計算は、以下の連続した段階で行なわれる。
【００２５】
・同じサイズｎ×ｍを有する２個の画素ウィンドウｆ１及びｆ２を獲得する。
【００２６】
・２次元高速フーリエ変換（ＦＦＴ）が各ウィンドウの輝度成分に適用され、二つの複素数（ｎ，ｍ）要素配列Ｆ１及びＦ２が得られる。
【００２７】
・クロスパワースペクトルＦ１．Ｆ２を作成し、その絶対値で除算することにより位相差行列が得られる。
【００２８】
・位相相関結果を改良するため、（ｎ．ｍ）次元の重み付け関数が位相差に適用される。この処理の目標は、相関面を妨害し得るノイズの影響を低減させることである。
【００２９】
・位相差行列のフーリエ逆変換は候補変位に対しピークを有する相関面を与える。
【００３０】
最後に、支配的なベクトルを探索する処理は、最も支配的な移動を表わす相関面内の最大ピークを探すことにより行なわれる。
【００３１】
ステップ２は、並進運動ベクトルのグループ分けを行なう。
【００３２】
フレーム内の種々のウィンドウに対し適用された相関ピーク検出アルゴリズムによって得られた推定された並進運動ベクトル
【００３３】
【外１】
0004547066.tif 000003
毎に、以下の第１のテストが行なわれる。
【００３４】
・前に推定された支配的な動きθ（前のフレーム）が並進運動、すなわち、
α＝β＝γ＝δ＝０
であり、かつ、
・この支配的な動きθと、上記の推定された並進ベクトル
【００３５】
【外２】
0004547066.tif 000004
との間のユークリッド距離が所定の閾値未満であるならば、上記の推定された並進ベクトル
【００３６】
【外３】
0004547066.tif 000005
は、並進ベクトルのリストから削除される。同様にして、残りの並進ベクトルがユークリッド距離を用いて比較される。冗長なベクトルは同じ閾値を用いる同じテストによって削除される。尚、成分（ｘ１，ｙ１）と成分（ｘ２，ｙ２）をもつ２個のベクトル間のユークリッド距離は、
√｛（ｘ１−ｘ２）2＋（ｙ１−ｙ２）2｝
である。
【００３７】
次のステップ３は多重分解能ロバスト回帰アルゴリズムを実施する。
【００３８】
大きい動きが存在するとき、又は、並進性の非常に少ない動きが存在する場合に失敗する可能性があり、コストの高い稠密動きフィールド推定を回避するため、大域的動き推定処理は、フレーム輝度の時空的な勾配に基づいて行なわれる。
この時空的な勾配は、周知のオプティカルフロー拘束方程式（式２）により２次元の明白な動きに関連付けられる。
【００３９】
dxΔＩx＋dyΔＩy＋ΔＩt＝０                式２
式中、dx及びdyは動きベクトルの２成分であり、ΔＩx、ΔＩy及びΔＩtは、輝度の時空的勾配、すなわち、輝度の微係数の推定量である。
【００４０】
dx及びdyには、大域的動きモデルに依存して式１により与えられた値が代入され、次に式３が得られる。
【００４１】
（ａ−αｘ−γｙ）ΔＩx＋（ｂ−βｘ−δｙ）ΔＩy＋ΔＩt＝０    式３
全フレームについて大域的動きベクトル
θ＝（ａ，ｂ，α，β，γ，δ）T
を推定するため、典型的な回帰アルゴリズムはθの６個のパラメータ全部に対し、以下の式を最小化する。
【００４２】
【数２】
0004547066.tif 000006
しかし、数個の大域的動きがフレーム内に存在する場合に、上記処理は妨害され、間違った推定を行なう。そのため、ロバスト回帰アルゴリズムが使用される。ロバスト回帰アルゴリズムは、理論的に、外れた値、すなわち、支配的な画素と同じ動きをもたない画素を除去することができる。このアルゴリズムは以下の関数を最小値に抑える。
【００４３】
【数３】
0004547066.tif 000007
式中、ｗｃ（ｘ，ｙ）は現在の大域的動き推定が巧く当てはまる画素を優先するための重み付け関数である。この関数ｗｃに対し数通りの関数（Lorentzian、Geman−Mc Lureなど）が選択される。重要なことは、いずれにしても、この関数が、観察結果を妨害しアルゴリズムの優れた挙動を得るため正しく推定されるべきノイズの変動に関連付けられたスケーリング係数に基づくことである。
【００４４】
推定処理は反復的である。各反復ｋ毎に、前の推定量
【００４５】
【外４】
0004547066.tif 000008
が推定処理の初期化用に使用される。同様に、スケーリング係数
【００４６】
【外５】
0004547066.tif 000009
は、反復的に推定される。
【００４７】
最初に、
【００４８】
【外６】
0004547066.tif 000010
は、
５×Ｒ0
に設定され、式中、Ｒ0は所定値である。全ての実験を通じて、Ｒ0は５０に一致する。したがって、反復毎に、
【００４９】
【外７】
0004547066.tif 000011
は、
【００５０】
【外８】
0004547066.tif 000012
がフレームに亘る推定の加重平均動き補償誤差を表わす場合に、以下の通り計算される。
【００５１】
【数４】
0004547066.tif 000013
スケーリング係数は次の式５によって計算される。
【００５２】
【数５】
0004547066.tif 000014
大きい動きが推定できるように、この処理は多重分解能の形で適用される。すなわち、２枚のフレームの多重分解能ピラミッドが最初に構築され、次に、所定レベルの動きパラメータの初期推定値としてより粗いレベルからの推定値を使用することにより、推定処理が最も粗い分解能から最も細かい分解能まで適用される。
【００５３】
初期大域的動きパラメータベクトルは、以下の通り設定される。
【００５４】
・処理がビデオショットに対し開始され始めたとき、ヌルベクトルが設定される。
【００５５】
・処理が現在のフレームに対し開始され始めたとき、より高い分解能レベルを考慮して再スケーリングされた前の値（すなわち、前の分解能から計算されたベクトル）が設定される。
【００５６】
続いて、反復処理が適用される。
【００５７】
ｋが現在の反復回数を表わす場合を考える。動きパラメータベクトル
【００５８】
【外９】
0004547066.tif 000015
の現在の推定量から、前のフレームの動き補償量の計算が行なわれ、時空的勾配マップが計算される。この処理を継続することにより、θの最初の推定量は、訂正量が小さくなるまで、順次訂正される。各反復におけるロバスト回帰は、訂正用動きパラメータベクトル
【００５９】
【外１０】
0004547066.tif 000016
を与える。大域的動きパラメータは、次式に従って更新される。
【００６０】
【数６】
0004547066.tif 000017
この処理は、推定された大域的動きパラメータの訂正量が所定の閾値よりも小さくなるまで反復される。これにより得られた動きパラメータ
【００６１】
【外１１】
0004547066.tif 000018
は、支配的な動きパラメータベクトルのロバスト評価量であるとみなされる。
【００６２】
次のステップ４は最良の大域的動きベクトルを選択することができる。ロバスト回帰処理中に、支配的な動きのサポート、すなわち、支配的な動きが当てはまるフレームの部分に関する最終的な分散は、以下の通り計算される。
【００６３】
最初に、外れていない画素（支配的な動きが当てはまる場所）が次のテストによって判定される。
【００６４】
【数７】
0004547066.tif 000019
であるならば、画素は外れていない画素である。式中、Ｐは推定処理の最終的な反復回数を表わす。
【００６５】
次に最終的な分散が、外れていない画素の集合に関するΔＩt（ｘ，ｙ）2の平均として計算される。
【００６６】
最良の大域的ベクトルは最終的な分散が最小に抑えられたベクトルとして選択される。
【図面の簡単な説明】
【図１】  支配的な動きの推定アルゴリズムのフローチャートである。
【図２】  並進運動の推定用の種々のウィンドウの配置を示す図である。
【符号の説明】
１    位相相関ピーク検出ステップ
２    動きベクトルグループ分けステップ
３    多重分解能ロバスト回帰ステップ
４    優れた大域的動きの選択ステップ
５    記憶ステップ
【図１】
0004547066.tif 000020
【図２】
0004547066.tif 000021