(57)【要約】【課題】モデル・ベースのプレイフィールド位置合わせのための方法、装置およびシステムを提供する。【解決手段】入力ビデオ画像が処理される。ビデオ画像の処理は、ビデオ画像に関係するキー点を抽出することを含む。さらに、ビデオ画像に関係する十分なキー点が抽出されたかどうかが判定され、十分なキー点が抽出されていた場合、ビデオ画像の直接的推定が実行され、該直接的推定に基づいて最終的ビデオ画像のホモグラフ行列が生成される。【選択図】図１
2011134322.tif 000002
【特許請求の範囲】
【請求項１】
入力ビデオ画像を処理する段階であって、前記ビデオ画像に関係するキー点を抽出することを含む、段階と；
前記ビデオ画像に関係する十分なキー点が抽出されたかどうかを検出する段階と；
十分なキー点が抽出された場合、前記ビデオ画像の直接的推定を実行する段階と；
前記直接的推定に基づいて最終的ビデオ画像のホモグラフ行列を生成する段階とを含む、
方法。
【請求項２】
前記直接的推定が、少なくとも二つの垂直点と交差する少なくとも二つの水平線に関係するキー点を検出し、評価することによってマッピング仮説を生成することを含む、請求項１記載の方法。
【請求項３】
十分なキー点が抽出されなかった場合に前記ビデオ画像の間接的推定を実行する段階をさらに含む、請求項１記載の方法。
【請求項４】
前記間接的推定が、二つの相続く画像の間の点マッチングを含むグローバル動き推定を実行することを含む、請求項３記載の方法。
【請求項５】
前記ビデオ画像を前処理する段階をさらに含む請求項１記載の方法であって、前処理が前記ビデオ画像のビュー型分類を実行することを含む、方法。
【請求項６】
前記最終的なビデオ画像を表示装置上に表示する段階をさらに含む、請求項１記載の方法。
【請求項７】
入力ビデオ画像を受け取る段階と；
前記ビデオ画像中の複数のオブジェクトを追跡する段階であって、各オブジェクトが個々に追跡されるよう各オブジェクトに追跡子が割り当てられる、段階と；
前記複数のオブジェクトの追跡から帰結する追跡情報を取得する段階とを含む、
方法。
【請求項８】
追跡が、ブーストされたオブジェクトを検出し、相互作用する分散型粒子フィルタ処理を実行することを含む、請求項７記載の方法。
【請求項９】
前記ビデオ画像の背景モデリングおよび背景抽出を実行する段階をさらに含む、請求項７記載の方法。
【請求項１０】
記憶媒体および該記憶媒体と結合されたプロセッサを有するデータ処理システムであって、前記プロセッサは：
入力ビデオ画像を処理する段階であって、前記ビデオ画像に関係するキー点を抽出することを含む、段階と；
前記ビデオ画像に関係する十分なキー点が抽出されたかどうかを検出する段階と；
十分なキー点が抽出された場合、前記ビデオ画像の直接的推定を実行する段階と；
前記直接的推定に基づいて最終的ビデオ画像のホモグラフ行列を生成する段階とを実行する、
データ処理システム。
【請求項１１】
前記直接的推定が、少なくとも二つの垂直点と交差する少なくとも二つの水平線に関係するキー点を検出し、評価することによってマッピング仮説を生成することを含む、請求項１０記載のデータ処理システム。
【請求項１２】
前記プロセッサがさらに、十分なキー点が抽出されなかった場合に前記ビデオ画像の間接的推定を実行する、請求項１０記載のデータ処理システム。
【請求項１３】
前記間接的推定が、二つの相続く画像の間の点マッチングを含むグローバル動き推定を実行することを含む、請求項１２記載のデータ処理システム。
【請求項１４】
前記プロセッサがさらに前記ビデオ画像を前処理する請求項１０記載のデータ処理システムであって、前処理が前記ビデオ画像のビュー型分類を実行することを含む、データ処理システム。
【請求項１５】
記憶媒体および該記憶媒体と結合されたプロセッサを有するデータ処理システムであって、前記プロセッサは：
入力ビデオ画像を受け取る段階と；
前記ビデオ画像中の複数のオブジェクトを追跡する段階であって、各オブジェクトが個々に追跡されるよう各オブジェクトに追跡子が割り当てられる、段階と；
前記複数のオブジェクトの追跡から帰結する追跡情報を取得する段階とを実行する、
データ処理システム。
【請求項１６】
追跡が、ブーストされたオブジェクトを検出し、相互作用する分散型粒子フィルタ処理を実行することを含む、請求項１５記載のデータ処理システム。
【請求項１７】
前記プロセッサがさらに、前記ビデオ画像の背景モデリングおよび背景抽出を実行する、請求項１５記載のデータ処理システム。
【請求項１８】
命令を有する機械可読媒体であって、前記命令は、実行されたときに機械に：
入力ビデオ画像を処理する段階であって、前記ビデオ画像に関係するキー点を抽出することを含む、段階と；
前記ビデオ画像に関係する十分なキー点が抽出されたかどうかを検出する段階と；
十分なキー点が抽出された場合、前記ビデオ画像の直接的推定を実行する段階と；
前記直接的推定に基づいて最終的ビデオ画像のホモグラフ行列を生成する段階とを実行させる、
機械可読媒体。
【請求項１９】
前記直接的推定が、少なくとも二つの垂直点と交差する少なくとも二つの水平線に関係するキー点を検出し、評価することによってマッピング仮説を生成することを含む、請求項１８記載の機械可読媒体。
【請求項２０】
前記命令が、実行されたときに前記機械にさらに、十分なキー点が抽出されなかった場合に前記ビデオ画像の間接的推定を実行させる、請求項１８記載の機械可読媒体。
【請求項２１】
前記間接的推定が、二つの相続く画像の間の点マッチングを含むグローバル動き推定を実行することを含む、請求項２０記載の機械可読媒体。
【請求項２２】
前記命令が、実行されたときに前記機械にさらに、前記ビデオ画像を前処理させる請求項１８記載の機械可読媒体であって、前処理が前記ビデオ画像のビュー型分類を実行することを含む、機械可読媒体。
【請求項２３】
命令を有する機械可読媒体であって、前記命令は、実行されたときに機械に：
入力ビデオ画像を受け取る段階と；
前記ビデオ画像中の複数のオブジェクトを追跡する段階であって、各オブジェクトが個々に追跡されるよう各オブジェクトに追跡子が割り当てられる、段階と；
前記複数のオブジェクトの追跡から帰結する追跡情報を取得する段階とを実行させる、
機械可読媒体。
【請求項２４】
追跡が、ブーストされたオブジェクトを検出し、相互作用する分散型粒子フィルタ処理を実行することを含む、請求項２３記載の機械可読媒体。
【請求項２５】
前記命令が、実行されたときに前記機械にさらに、前記ビデオ画像の背景モデリングおよび背景抽出を実行させる、請求項２３記載の機械可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
分野は概括的にはコンピューティング科学に、より詳細にはビデオ・イメージングに関する。
【背景技術】
【０００２】
画像位置合わせ〔レジストレーション〕問題はビデオ・シーケンスに共通している。典型的には、画像位置合わせは、異なるセンサーからまたは異なる視点からの異なる時刻における二つ以上のビデオ・シーケンスをマッチさせる画像処理において使われる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
しかしながら、画像位置合わせの領域における若干の進歩にもかかわらず、画像における歪みが残る。これらの歪みは、位置合わせ不良〔ミスレジストレーション〕（たとえば、画像の整列不良〔ミスアラインメント〕）を含む。これらの頻繁な歪みを除去できないほか、従来の画像位置合わせアルゴリズムは、そのわずかばかりの成果の一方で、大量の検索スペースを消費する。さらに、従来の画像位置合わせアルゴリズムで実行される検索は安定でない。
【課題を解決するための手段】
【０００４】
本発明の実施形態は、限定ではなく例として、付属の図面の図において図示されている。図面において、同様の参照符号は同様の要素を示す。
【図面の簡単な説明】
【０００５】
【図１】フィールド位置合わせを実行するプロセスを示す図である。
【図２】現実点および仮想点を有するフィールド・モデルのホモグラフ行列（homograph  matrix）の実施形態を示す図である。
【図３】フィールド・モデルと画面イメージの間のホモグラフ・マッピング（homographic  mapping）およびさらに画面イメージの間の動き遷移の実施形態を示す図である。
【図４−１】ハフ（Hough）直線検出および交差点抽出の実施形態を示す図である。
【図４−２】ハフ（Hough）直線検出および交差点抽出の実施形態を示す図である。
【図５−１】Ａ〜Ｃは、スポーツ・ビデオにおけるモデル・ベースのプレイフィールド〔競技場〕位置合わせの実施形態を示す図である。
【図５−２】Ｄ〜Ｅは、スポーツ・ビデオにおけるモデル・ベースのプレイフィールド〔競技場〕位置合わせの実施形態を示す図である。
【図５−３】Ｆ〜Ｇは、スポーツ・ビデオにおけるモデル・ベースのプレイフィールド〔競技場〕位置合わせの実施形態を示す図である。
【図６】ブーストされ相互作用を取り入れた分散型粒子フィルタに基づくマルチ・オブジェクト追跡のためのプロセスの実施形態を示す図である。
【図７】ブーストされ相互作用を取り入れた分散型粒子フィルタの実施形態を示す図である。
【図８】互いに相互作用をもち、グループ（たとえばグループG）をなすオブジェクトを示す図である。
【図９】解像度720×576および960×544の二つのビデオ・クリップに対して実行される本発明の諸実施形態の実装の追跡結果の実施例を示す図である。
【図１０−１】本発明の諸実施形態の実装の追跡結果の別の実施例を示す図である。
【図１０−２】本発明の諸実施形態の実装の追跡結果の別の実施例を示す図である。
【図１１】ソフトウェアおよびハードウェア・コンポーネントのハイブリッドとして実装される本発明の実施形態をもつコンピューティング・システムの実施形態を示す図である。
【発明を実施するための形態】
【０００６】
ある実施形態では、画面イメージとフィールド・モデルとの間の幾何学的な対応を見出し、次いで画面イメージからのプレイフィールド〔競技場〕を標準的なフィールド・モデルにマッピングするためのフィールド位置合わせ技法が開示される。一般にスポーツ、特にサッカーが本稿を通じて使われるが、これは単に例として、簡明のためにそうするまでのことである。本稿に開示される実施形態が内容にかかわらずいかなるビデオ画像にも適用可能であることが考えられている。スポーツの例を続けると、スポーツ・ビデオにおける主要な成分は、ボールおよびプレーヤーの動き軌跡をフィールド・モデルにマッピングすることである。そのようなマッピングを実行する際、各プレーヤーのフィールド座標系における相対位置は、位置合わせされたフィールドから得ることができる。これらの相対位置は、プレーヤーの動き方向、近似スピードおよび活動〔アクティビティ〕を含む。そのような手がかり〔キュー〕は、仮想コンピューティングおよびコンピュータ作図の領域において、チーム・ベースのラインナップおよび戦術解析、活動ベースのシーン検索、ビデオ・コンテンツ・エンリッチメントおよび編集、対話的および没入型〔イマーシブ〕ゲーム、拡張現実感などを容易にするのを助けることができる。
【０００７】
ある実施形態では、ビデオ画像の効果的かつ実際的なフィールド位置合わせを提供するための、関連するフィールド位置合わせハードウェア・コンポーネントに基づく新規なフィールド位置合わせアルゴリズムが提供される。この新規な手法はまず、ビュー型分類を実施し、次いでハフ変換を適用してフィールド直線マークおよびその対応する交差点を検出する。これらの交差点は、フィールド位置合わせのためのキー点として取られる。十分なキー点（たとえば４個以上のキー点）があるときは、最適マッピングを探索するための直接マッチングが実行される。効率的な探索のために、距離変換によって生成される距離マップが、マッチング誤差を計算するために使われる。さらに、探索を加速するため、いくつかの高速拒否基準が探査され、プロセスを高速化するために使われる。キー点の数が十分でない場合（たとえばキー点が４個未満）、ホモグラフィー行列（homography  matrix）は直接取得されなくてもよく、その代わり、相続くフレームの間のグローバルな動きを推定して現在の動き遷移を以前の任意のフィールド・モデル・マッピング行列と組み合わせて現在のホモグラフィー行列を推論することによって間接的に取得されてもよい。この技法およびその有効性および実際性は、先の段落においてさらに述べられている。
【０００８】
この新規で実際的なフィールド位置合わせ技法は、十分なキー点があるまたはない、いかなる型およびビデオ画像数の場合でも機能する。この高度かつ合理的な解決策は、フィールド位置合わせのタスク実行の困難を簡略化する。フィールド位置合わせ技法は、マッチング誤差を測定するために距離変換を用いる。これは、誤差が連続的であることができるようにし、探索をより安定にする。さらに、探索スペースを縮小してプロセスを高速化するためのいくつかの高速拒否基準を発明する。
【０００９】
図１は、フィールド位置合わせを実行するためのプロセスを示している。処理ブロック１０２では、プロセッサを含むコンピューティング・システムを有するカメラのようなビデオ装置に接続されている物理的インターフェースを通じてビデオ入力が受け取られる。処理ブロック１０４では、受け取られたビデオの前処理が実行される。前処理は、優勢色学習および処理ブロック１０６におけるビュー型分類の実行を含む。ビデオにおける優勢色は、色相‐彩度‐値（HSV:  Hue-Saturation-Value）色ヒストグラムを累積することによって実行される。これはプレイフィールドの芝の色に対応する。前述したように、再び注意しておくが、スポーツ（特にサッカー）は簡明のために例として使われているに過ぎず、本発明の実施形態はスポーツ・ビデオに限定されない。たとえば、（ここで使われているような）プレイフィールドの芝の色の代わりに、色は、政治討論の際の米国議会の床、あるいはラリーの間の芝、あるいは昼メロや映画の間のリビングの色であることもできる。次いで優勢色セグメンテーションおよび形態論的〔モルフォロジカル〕フィルタ処理が、接続コンポーネント解析とともに使用されて、プレイフィールドが抽出される。その後、各ビューは四つのビュー型：（１）グローバル・ビュー、（２）中くらいのビュー、（３）クローズアップ・ビューおよび（４）ビュー外の一つに分類される。ここで、グローバル・ビューがさらなる計算のためにフィールド位置合わせモジュールに入力されうる。
【００１０】
処理ブロック１０８では、ハフ直線検出および交差点キー点抽出が実行される。ハフ変換は、プレイフィールド領域を抽出し、次いでプレイフィールド領域内で優勢色と整合しないピクセルがあればそれをリザーブし、二レベル（二値）画像にすることによって直線マークを検出するために実行される。その後、二値画像にハフ変換が適用されて水平および垂直な直線マークが検出され、その交差キー点が得られる。さらに現実のおよび仮想の交差点が検出され、使用される。これは図４−１〜２に示されている。
【００１１】
判断ブロック１１０において、十分なキー点があるかどうかについての判定がなされる。十分な点がある場合、処理ブロック１１２において新規の直接的マッピング推定が実行される。この新規の直接的マッピング推定は、処理ブロック１１４におけるマッチング仮説生成ならびにそれに続く処理ブロック１１６における仮説評価および最適対応探索を通じて実行される。十分な点がない場合には、処理ブロック１１８で間接的マッピング推定が実行される。間接的マッピング推定は、処理ブロック１２０におけるキー点検出、フィルタ処理およびグローバル動き推定ならびにそれに続く処理ブロック１２２における現在マッピング・トランザクション実施を含む。いずれの場合にも（すなわち直接的マッピング推定、間接的マッピング推定のいずれでも）、プロセスはホモグラフ行列（Ht）１２４の生成に進む。
【００１２】
上述したように、画面イメージとフィールド・モデルとの間に十分な点（たとえば、四つより多い対応する点、よって少なくとも二つの水平線および少なくとも二つの垂直線の交差）があるときには、ホモグラフ行列を推定するために、処理ブロック１１２において直接的推定が実行される。この直接的推定は、どの点対が互いに対応するかを判別することを含み、フィールド・モデルおよびこれらの可能な場合が列挙され、誤差評価を通じた最適なものの探索が実行される。ある実施形態では、フィールド・モデルは、これらの実施形態が実行されているビデオ画像の任意の背景またはフィールドを指す。しかしながら、サッカーのテーマを続けると、国際サッカー連盟（FIFA:  Federation  Internationale  de  Football  Association）によって定義される標準的なスポーツ・サッカー・フィールドがこの実施形態においてフィールド・モデルとして使用される。ある実施形態では、現実の交差点（水平線および垂直線のような二つの現実の直線の交差のような）および任意の仮想の交差点（一つの現実の線および一つの延長された現実の線の交差または二つの延長された現実の線の交差のような）がフィールド・モデルにおいて使用される。これらの仮想交差点もフィールド・モデルのキー点であり、ビデオ装置（たとえばカメラ）を較正するために使用できる。
【００１３】
さらに、マッピング仮説生成に関し、マッピング手順を簡略化するために、それぞれの交差キー点対応をガイドするために、直線マークが使用される。フィールド・モデルにおいて、Lhは水平線の数を指し、Lvは垂直線の数を指す（たとえばLh＝10本の水平線、Lv=7本の垂直線）。m本の水平線（Lh＝m）およびn本の垂直線（Lv＝n）があるとすると、たとえば点対応の４個対（4-pair）の
【００１４】
【数１】
2011134322.tif 000003
通りの可能な組み合わせおよび点対応の４個対の可能な組み合わせがある（C(n,k)は組み合わせ演算C(n,k)＝n!/k!(n−k)!）。それぞれの組み合わせが仮説と称されてもよく、検出された画像線とフィールド・モデルの直線マークとの間の可能な対応を反映する。
【００１５】
各仮説評価のために、世界座標から画像平面へのマッピング行列Hが得られる。各仮説の信頼度を評価するために、フィールド・モデルは画像平面にマッピングされ、マッピングされた画像と元の画像との間の距離が計算される。検出された直線に基づいて、距離変換技法が使用され、誤差があればそれを測定するための距離マップが得られる。距離マップが「D」に等しい場合、誤差は：
【００１６】
【数２】
2011134322.tif 000004
である。ここで、Nは0でないピクセルの総数であり、τは最大誤差を制約するための定数である。誤差およびマッピングは互いに反比例していてもよい。たとえば、誤差が小さいほどマッピングはよくなる。最適仮説が最終的なマッチングとして使用される。
【００１７】
探索スペースは膨大なので、仮説評価は計算パワー要件の面で過酷なものとなりうる。ある実施形態では、探索スペースを減らすために、何らかの仮説を速く拒否するために、次の基準のうちの一つまたは複数が使用される：（１）検出された直線（特に垂直線）の角度に基づいて、フィールド側（たとえば、左、右または真ん中の側〔サイド〕）が推定されてもよい。たとえば、プレイ位置が左フィールド側にある場合、フィールド・モデルにおいてマッチングされるべき直線は右にはない。同様に、右側の処理も対応して行われる。この基準を使っていくつかの仮説がフィルタリングされる；（２）二つ以上の水平線または二つ以上の垂直線がフィールド・モデルと所与の画像との間でマッチした場合、フィールド・モデルのサイズが推定される。さらに、推定されたサイズが標準的なフィールド・モデルと大きく異なる場合、この仮説は拒否されてもよく、異なる基準をもつ別の仮説が使用されてもよい；（３）もう一つの高速拒否は、ホモグラフィー行列自身を評価することである。ホモグラフィー行列はいくつかの（たとえば八個の）自由度をもつが、現実画像の形成プロセスは異なる数のパラメータ（たとえば七個）を有していてもよい。たとえばカメラ位置について三個、カメラ回転について三個、焦点距離について一つである。残りの自由度はβ（非等方スケーリング）を含む。これは、水平方向と垂直方向における不均等なスケーリングを表す（現実世界においては典型的には「1」である）。この値は、カメラ較正理論に基づいて得られてもよい。さらに、完全に精確ではなく、計算が数値的に敏感な推定カメラ・パラメータについて、パラメータ受け入れ範囲0.5＜β＜2が設定される。
【００１８】
前述したように、現在フレームに十分なキー点がない（たとえば四個未満）ときには、処理ブロック１１８において前のフレームから現在フレームへのカメラ動き変換（translation）を実行することによって間接的マッピング推定が実行され、処理ブロック１２４で現在のホモグラフィー・マッピング行列が演繹される。ある実施形態では、この間接的マッピング推定手順は、一つまたは複数の特徴点検出、二つの相続く画像間の点マッチング、ランダム・サンプル・コンセンサス（RANSAC:  random  sample  consensus）を介した点対フィルタ処理および最小二乗推定によるグローバル動き計算の一つまたは複数を含む。第一のプロセスは、キー点の検出を含む。ここで、コーナー点、ハリス（Harris）点、高速化堅牢特徴（SURF:  Speed  Up  Robust  Features）などが使用できる。さらに、スケール不変特徴変換（SIFT:  Scale  Invariant  Feature  Transform）特徴がキー点を特徴付けるために使用されてもよい。
【００１９】
前のフレームおよび現在フレームにおけるキー点をそれぞれ検出したのち、前のフレームと現在フレームとの間の対応が設定される。前のフレームにおける各点について、前のフレームの各点から現在フレームの各点への距離が計算され、最も近い点または最短距離がその対応として取られる。キー点対応の組はまた、ノイズまたは偽マッチのような、何らかの突出データ（data  outlier）をも含むことがありうる。その場合、そのような突出データをフィルタ除去するためにRANSACアルゴリズムが適用される。RANSACアルゴリズムは、任意の数の突出データがあるときに、任意の数の突出データを扱う際に、フィールド・モデルの堅牢な当てはめのためのアルゴリズムをいう。その際、グローバル動きパラメータが、最小二乗推定を使ってリザーブされた整合点対応を用いてパースペクティブ・モデルのもとに計算される。たとえば、時刻tにおけるホモグラフィー・マッピング行列がHtであり、時刻t−1からtへの動き遷移行列がMt-1とすると。ひとたびこれらの値が知られたら、ホモグラフィー・マッピング行列は次の公式：Ht＝Mt-1×Ht-1を使って得ることができる。
【００２０】
図２は、現実点２０２および仮想点２０４をもつフィールド・モデルのホモグラフ行列２００の実施形態を示している。ある実施形態では、同次座標をもつ3D点はP＝[X,Y,Z,1]'と表され、平面上の3D点のZ成分は0であり、よって、P＝[X,Y,1]'と表される。網膜上の2D点はp＝[x,y,1]'である。ピンホール・カメラについて、現実世界座標系における3D点Pおよびその対応する2D画像点pは次の関係：p＝H×Pをもつ。ここで、Hは、内的および外的パラメータを使ってパラメータ表現された3×3行列である。これは、現実世界の平面と画面イメージとの間のホモグラフ行列と呼ばれる。
【００２１】
さらに、行列Hは、いくつかの（たとえば八個の）独立したパラメータをもちスケール因子を除いたところまで定義される。たとえば八個のパラメータの値を決定するには、画像位置とフィールド・モデル位置との間の少なくとも四対の点対応が使用される。フィールドは通例、明らかな点特徴はもたないので、点対応を推定するためにプレイフィールド内の直線の交点が使われる。現実の直線および現実の直線の延長（たとえば仮想線）が交わる任意の現実の交点２０２および仮想交点２０４が、キー点と見なされ、いずれもカメラを較正するために使用できる。
【００２２】
図３は、フィールド・モデル３０２と画面イメージ３０４〜３０８との間のホモグラフィック・マッピング３１０〜３１４、さらには画面イメージ３０４〜３０８の間の動き遷移３１６〜３１８の実施形態を示している。サッカーの例を続けると、カメラがゴール前〔ゴールマウス〕近くの領域に焦点を当てる場合、四対より多くの対応する点を見出すことは容易であろう。しかしながら、フィールド中央領域近くの領域またはぼけたもしくは不鮮明な画像（たとえば高速のカメラ動きのために）については、十分な対応するキー点が利用可能でないことがありうるので直線を検出することは少々難しいことがありうる。この問題に対処するため、ある実施形態では、グローバルな動き遷移および直前フレームのホモグラフィー行列を使って、現在のホモグラフィー行列３１０〜３１４が近似的に推論される。フィールド・モデル３０２と画面イメージ３０４〜３０８との間のホモグラフィー行列３１０〜３１４（矢印３１０〜３１４で示される）ならびに相続く画面イメージ３０４〜３０８の間の動き遷移３１６〜３１８（矢印３１６〜３１８で示されるような）がここには図示されている。
【００２３】
グローバル動きモデルがパースペクティブ・モデルでありその変換も3×3行列であるとすると、直前フレームIt-1およびグローバル動き変換Mt-1からの現在フレームの推定（図５のＡ〜Ｇ）は、次の公式：It＝Ht×F（公式１）を使って定式化できる。フィールド・モデルをFと表すと、フィールド・モデルから画像へのマッピングは：It-1＝Ht-1×F（公式２）、It＝Mt-1×It-1（公式３）である。公式２を公式１に代入すると、次式：It＝Mt-1×Ht-1×F（公式４）が得られる。ここで、公式１を公式４と比べると、次の公式：Ht＝Mt-1×Ht-1＝Mt-1×Mt-2×Ht-2＝……＝Mt-1…Mt-k×Ht-kが得られる。
【００２４】
図４−１〜２は、ハフ直線検出および交差点抽出４００の実施形態を示している。ある実施形態では、直線マークを検出するためにハフ変換が使用される。まず、プレイフィールド領域が抽出され４０２、次いで、プレイフィールド４０２内で優勢色と整合しないピクセルがリザーブされ、二レベル画像にされる４０４。次いで、水平および垂直の直線マークがあればこれを検出するために二値画像に対するハフ変換４０６。最後に、水平線と垂直線の交差点が得られ、現実および仮想の交差点が検出され、使用される４０８。
【００２５】
図５のＡ〜Ｇは、スポーツ・ビデオ５００においてモデル・ベースのプレイフィールド位置合わせのある実施形態を示している。列はフレーム番号５０１、元の画面イメージ５０２、ハフ直線検出結果５０４（垂直線および水平線をもつ）、フィールド・モデルの現実の画像へのマッピングの結果５０６およびフィールド位置合わせされた結果５０８を含む。MPEG2フォーマット（たとえば720×576のフレーム・サイズで25フレーム／秒）のビデオ・クリップに対してフィールド位置合わせを実行した結果が与えられる。
【００２６】
灰色の領域は、カメラの焦点領域である。リストされたフレームにおいて、図５−１のＡ〜Ｂ、フレーム２〜２６は、フィールド・モデルの左フィールドであり、図５−２のＣ〜Ｅ、フレーム１２０〜１８０はフィールド・モデルの左中央フィールドであり、図５−３のＦ〜Ｇ、フレーム１２００〜１２５０はフィールド・モデルの右フィールドである。フレーム２、２６、１２０、１８０、１２００および１２５０の結果は、直接的推定によって受領され、一方、フレーム１３０の結果は間接的推定によって得られる。さらに、図のように、ハフ直線画像はフレーム１３０からは欠けている。画像５４０が汚染されているまたは焦点外れであるために十分な数のキー点が得られなかったからである。
【００２７】
図６は、ブーストされ相互作用をもって分散した粒子フィルタに基づくマルチ・オブジェクト追跡のためのプロセスのある実施形態を示している。処理ブロック６０２において入力ビデオが受領される。入力ビデオは、それぞれのビデオ装置がソフトウェア・アプリケーションをもつ、あるビデオ装置から別のビデオ装置へのビデオ／バス・インターフェースを通じて、あるいは同じビデオ装置内で（たとえばプロセッサ／CPUを有するカメラ）、受領されてもよい。処理ブロック６０４において、入力ビデオの背景モデリングおよび前景抽出が実行される。ある実施形態では、ブーストされたオブジェクト検出６０８および相互作用する分散型粒子フィルタ６１０は統合されて、処理ブロック６０６における堅牢かつ効果的なマルチ・オブジェクト追跡を実行する。これを達成するために、ブーストされ相互作用をもって分散された粒子フィルタ（BIDPF:  boosted  interactively  distributed  particle  filter）・ソフトウェアおよびハードウェアが、さまざまなアプリケーション（たとえば、サッカー選手追跡アプリケーションのようなスポーツ選手追跡アプリケーション）における自動的なマルチ・オブジェクト追跡（MOT:  multi-object  tracking）の問題に対処するために設けられる。処理ブロック６１２では、画像のオブジェクト追跡情報（たとえば、位置および数）が得られ、提供される。繰り返すが、サッカーは単にここで簡明のために例として使われているのであって、本発明の実施形態とともに使用できるアプリケーションはいくらでもあり、スポーツやスポーツ・アプリケーションに限定されるものではない。
【００２８】
ある実施形態では、相互作用する分散型粒子フィルタ技法（IDPF:  interactive  distributed  particle  filter  technique）処理ブロック６１０が、さまざまなターゲットの間の相互の隠蔽を扱うよう採用される。動的モデルおよびブースティング検出からの情報を組み込む混合モデルを使う提案される分布が、IDPFの枠組み中に導入される。処理ブロック６０８におけるブーストされた提案分布は、迅速なターゲット検出を許容する。一方、IDPFプロセスは、相互隠蔽の間、そのようなターゲットの同一性〔どれがどれであるか〕を保持することを可能にする。スポーツ・ビデオでは、ブーストされた検出を高速化するのと、偽警報を減らす両方のために、処理ブロック６０４において、所与のプレイフィールドの自動的な学習された色モデルを使って前景が抽出される。前景は、IDPFパフォーマンスを改善するためにデータ駆動のポテンシャル・モデルを発展させるためにも使用される。いくつかのビデオ・シーケンスに対して実行されるこの新規な手法の結果のいくつかは、可変数のオブジェクトの追跡を実証し、カメラ動きおよび相互隠蔽のある動的なシーンにおけるそれらの同一性を正しく維持している（これまでの図に示されるように）。
【００２９】
図７は、ブーストされた相互作用する分散型粒子フィルタのある実施形態を示している。フィールドの色モデルは、HSV色ヒストグラムを累積することによって学習される。次いで、優勢色閾値処理、形態論的フィルタ処理および接続コンポーネント解析を通じてフィールドが抽出される７０２。フィールド中の前景は、優勢色モデルを使ってフィールド色をフィルタリングすることによって得られる７０４。次いで、ブースティング検出器は、複数のスケールで前景画像を横断してスキャンする７０６。このプロセスは、検出を加速し、偽警報があったとしてもそれを減らす。さらに、ターゲット間の相互作用を扱うため、相互作用式分散手法（interactive  distributed  approach）が採用される。この手法では、各オブジェクトについての条件付き密度伝搬が、オブジェクトの観察の間の相互作用を分散型方式でモデル化することによって定式化される。粒子フィルタ処理実装では、いかなる隠蔽問題も、各粒子の重みを調整することによって扱われる。
【００３０】
ある実施形態では、時刻tにおけるターゲットiの状態および対応する観察がxitおよびyitと表される。時刻tまでの状態セットアップはxi0:tであり、ここで、x0は初期状態であり、時刻tまでの観察セットアップはyi0:tである。時刻tにおけるyitの相互作用的観察（interactive  observations）はyJttによって表される。ここで、Jtの諸要素は、観察がyitで相互作用するオブジェクトの諸指数である。追跡の目的は、すべての観察に基づく事後
【００３１】
【数３】
2011134322.tif 000005
を推定することである。yiが他のオブジェクトと何の相互作用ももたないときは、
【００３２】
【数４】
2011134322.tif 000006
である。この定式化は、通常の粒子フィルタ手法と整合する。条件付き独立属性を使って、各相互作用型追跡子（interactive  tracker）についての密度伝搬は次のように定式化される：
【００３３】
【数５】
2011134322.tif 000007
ここで、p(yit|xit)は局所的尤度、p(xit|xi0:t-1)は状態遷移密度であり、これらはベイズ追跡手法と同様である。式
【００３４】
【数６】
2011134322.tif 000008
は、相互作用尤度（interactive  likelihood）として知られており、これはターゲット間の相互作用を特徴付ける。ターゲット間のいかなる統合もない場合、この定式化は複数の独立したベイズ追跡子に退化させられる。
【００３５】
粒子フィルタ実装では、事後確率
【００３６】
【数７】
2011134322.tif 000009
は、
【００３７】
【数８】
2011134322.tif 000010
として（Nはサンプル数）、重み付けられたサンプルの組
【００３８】
【数９】
2011134322.tif 000011
によって特徴付けられる。重要性サンプリング（importance  sampling）理論によれば、重みは
【００３９】
【数１０】
2011134322.tif 000012
として更新される。
【００４０】
図８は、グループ（たとえばグループG）をなし、互いに相互作用をもつオブジェクト８０２〜８０６を示している。粒子の重みを調整するために相互作用尤度
【００４１】
【数１１】
2011134322.tif 000013
を推定するために前景観察に基づいてデータ駆動のポテンシャル・モデルが提案される。さらに、Gは相互作用するオブジェクトによって形成される画像グループとして表され、FG  ８０２は画像前景として表され、SG  ８０４はG内の全プレーヤーの画像領域の和集合として表され、p11はプレーヤー領域内のピクセルが前景に属する確率であり、p10はプレーヤー領域内のピクセルが前景に属さない確率であり、p01はプレーヤー外のピクセルが前景にある確率であり、p00はプレーヤー外のピクセルが背景にある確率であり、p11＋p10＝1、p11＞p10、p01＋p00＝1、p01＜p00である。
【００４２】
ピクセルどうしが独立であるとすると、次の尤度を得る：
【００４３】
【数１２】
2011134322.tif 000014
ここで、CGは規格化定数であり、λ10およびλ01はそれぞれp10およびp01に依存する二つの係数であり、∩は二つの領域の交わりである。この尤度はN10およびN01に依存する。８０６に示されるように、長方形外の白いピクセル８０８がN10をなし、長方形内の黒いピクセル８１０がN01をなす。提案されるポテンシャル・モデルを活用することにより、相互作用尤度
【００４４】
【数１３】
2011134322.tif 000015
は、オブジェクトの推定が観察をよく解釈しない確率を減らす。したがって、これは隠蔽における観察を分離することができ、よってマージング問題〔合体してしまう問題〕を解決できる。
【００４５】
ラベリング問題〔ラベル付けの問題〕を解決するため、ある実施形態では、状態遷移確率p(xit|xit-1,xit-2)が：
【００４６】
【数１４】
2011134322.tif 000016
によって推定される。ここで、p(xit,xit-1)は伝統的な状態遷移密度であり、これは定加速度モデルを使って推定できる。さらに、慣性重みΦit(・)が：
【００４７】
【数１５】
2011134322.tif 000017
として定義される。ここで、σθ、σvは、それぞれ動きベクトルの方向およびスピードの許容できる分散を特徴付ける事前定数である。vi,nt＝xi,nt−xit-1はi番目のオブジェクトのn番目の粒子xi,ntの動きベクトルであり、
【００４８】
【数１６】
2011134322.tif 000018
はxit-2からxit-1への参照動きベクトルを表す。
【００４９】
【数１７】
2011134322.tif 000019
はvi,ntと＾付きのvitの間の角度である。‖・‖はL2ノルムを表す。
【００５０】
粒子フィルタ処理を有効に保つことにおける一つの問題は、いかにして提案分布を設計するかである。ある実施形態では、ダイナミクス事前（the  dynamics  prior）およびブースティング検出（the  boosting  detections）の両方を組み合わせるガウシアン・モデル（Gaussians  model）の混合
【００５１】
【数１８】
2011134322.tif 000020
を使う。パラメータσqは、ブースティング検出のガウシアン分布とダイナミクス事前の間の重なりによって動的に更新される。ブースティング検出を既存のトラック〔追跡〕に割り当てるデータ関連付けのために、直近近傍者（Nearest  Neighbor）アルゴリズムが使われる。
【００５２】
局所尤度p(yit|xit)に関し、ターゲットの観察は、位置xitを中心とする領域R(xit)から抽出された色分布のカーネル密度推定によって表される。現在の観察K(xt)と参照モデルK*との間の類似性を評価するためにバッタチャリヤ（Bhattacharyya）係数が適用される。
【００５３】
【数１９】
2011134322.tif 000021
さらに、観察の空間的情報をエンコードするために、多部分（multi-part）色モデルが採用される。これは、オブジェクトを縦に二つの部分に分ける。こうして、ターゲットIの局所尤度は
【００５４】
【数２０】
2011134322.tif 000022
として定義される。
【００５５】
図９は、実装が解像度720×576および960×544の二つのビデオ・クリップに対して実行されるときの本発明の諸実施形態の実装の追跡結果の実施例を示す。行９０２〜９０６の図は特に、シーンにはいる新しいプレーヤーにフォーカスを当てている。ある実施形態では、はいるプレーヤーは、比較的重度の隠蔽があっても、迅速に検出され、堅牢に追跡される。図のように、行９０４は行９０２の第一の画像においてラベル付けされた楕円形の領域のクローズアップ・ビューを示す。ある技法では、各プレーヤーについての囲みボックス（たとえば追跡子）９０８〜９１２の色は、プレーヤーが他と相互作用をもたない場合には、一意的であってもよい。それ以外の場合には、追跡子の色は黒に変えられてもよい。隠蔽の間、正しい同一性〔どれがどれであるか〕が維持される。これは、相互作用尤度を通じた粒子についての提案される重み調整方式の恩恵である。行９０４は、追跡子どうしが近づいたときに互いにマージされるところを示している（たとえば三つの追跡子９１４〜９１８から二つの追跡子９１４〜９１６になるなど）。さらに、単一の追跡子が二つの追跡子に分裂する場合、新しい追跡が生成されてもよい。それにより、同じターゲットのラベルが隠蔽後には異なっていることがありうる。
【００５６】
図１０−１〜２は、本発明の諸実施形態の実装の追跡結果の別の実施形態を示している。実施形態では、行１００２〜１００８はプレーヤーの追跡結果を示している。各プレーヤー１０１０〜１０１９は対応する追跡子１０２０〜１０２９を使って個々に追跡され、図のように、各プレーヤー１０１０〜１０１９は個々に追跡され、その同一性はいかなる部分的もしくは完全な隠蔽にも関わりなく正しく維持される。
【００５７】
図１１は、ソフトウェアおよびハードウェア・コンポーネントのハイブリッドとして実装された本発明の諸実施形態を有するコンピューティング・システム１１００の実施形態を示している。それらの実施形態のある種の機能はハードウェアにおいて実装され、ある種の他の機能はソフトウェアにおいて実装される。図のように、CPUチップ１１０２はビデオ・コプロセッサ１１１０と一緒に機能するよう設計される。ビデオ・コプロセッサ１１１０は、グラフィック処理ユニット（GPU）のような他の処理ユニットを有するビデオ装置（たとえばビデオ・カメラ）の一部であってもよい。ある実施形態では、ビデオ・コプロセッサ１１１０は、他の従来のソフトウェアおよびハードウェア論理と一緒に機能する任意の数の新規なソフトウェア論理およびハードウェア論理１１００を用い、任意の従来の動作と協調して本発明の実施形態を実行する。
【００５８】
ランダム・アクセス・メモリ（RAM）１１０６は、オブジェクト情報を有するアプリケーション・データベースを有する。メモリ・コントローラ１１０４はRAM  １１０６内のデータにアクセスし、CPU  １１０２および／またはビデオ・コプロセッサ１１１０に処理のために転送する。RAM  １１０６は、倍速RAM（DDR  RAM:  double  data  rate  RAM）、拡張データ出力RAM（EDO  RAM:  extended  data  output  RAM）等を含みうる。任意のデータ（たとえばビデオ画像または処理されるべき他の入力データ）がメモリ１１０８に記憶されてもよく、後刻、任意の結果データ（たとえば、最終ビデオ画像および任意の関連情報）が表示装置１１１２に転送される。あるいはまた、ビデオ・コントローラはCPU  １１０２と同じダイ上にあってもよく、キャッシュおよびメモリ・コントローラの共有が使われてもよい。ディスプレイ１１１２は、陰極線管（CRT）、薄膜トランジスタ（TFT）、液晶ディスプレイ（LCD）、DPLなどさまざまな型のものであってよい。
【００５９】
ある実施形態では、上記のグラフィック・パイプラインのいくつかのプロセスはソフトウェアで実装され、残りはハードウェアで実装される。メモリ２０８はバッファの事前割り当てされた領域を有していてもよいが、本発明がそのように限定されるものではないこと、低位のグラフィック・パイプラインにとってアクセス可能ないかなるメモリが使用されてもよいことは当業者は理解するはずである。コンピュータ・システム１１００はさらに、入出力（I/O）制御ハブ（ICH:  input/output  control  hub）、一つまたは複数のI/O機器などを含んでいてもよい。
【００６０】
CPU  １１０２は、本コンピューティング・システムが実装するいかなるソフトウェア・ルーチンでも実行するために命令を実行する一つまたは複数のプロセッサを含んでいてもよい。命令はしばしば、データに対して実行される何らかの種類の演算を含む。データおよび命令の両方がシステム・メモリ１１０８およびもしあれば付随するキャッシュに記憶される。キャッシュは典型的には、システム・メモリ１１０８よりも短い遅延〔レイテンシ〕時間を有する。たとえば、キャッシュはプロセッサ（単数または複数）と同じシリコン・チップ（単数または複数）上に統合され、および／またはより高速の静的RAM（SRAM）セルとともに構築されてもよい。一方、システム・メモリ１１０８はより低速の動的RAM（DRAM）セルと一緒に構築されてもよい。より頻繁に使われる命令およびデータをシステム・メモリ１１０８ではなくキャッシュに記憶するようにすることによって、コンピューティング・システム１１００の全体的なパフォーマンス効率が改善される。
【００６１】
システム・メモリ１１０８は意図的にコンピューティング・システム１１００内の他のコンポーネントに利用可能にされる。たとえば、コンピューティング・システム１１００へのさまざまなインターフェース（たとえば、キーボードおよびマウス、プリンタ・ポート、ローカル・エリア・ネットワーク（LAN）ポート、モデム・ポートなど）から受信された、あるいはコンピュータ・システム１１００の内部記憶要素（たとえばハードディスク・ドライブ）から取得されたデータ（たとえば入力グラフィック・データ）はしばしば、ソフトウェア・プログラムの実装における一つまたは複数のプロセッサによって作用される前に、一時的にシステム・メモリ１１０８中で待ち行列に入れられる。同様に、ソフトウェア・プログラムがコンピューティング・システム１１００から外部エンティティにコンピューティング・システム・インターフェースの一つを通じて送られるべきである、あるいは内部記憶要素に記憶されるべきであると判定するデータは、しばしば、伝送または記憶される前に、一時的にシステム・メモリ１１０８中で待ち行列に入れられる。
【００６２】
システム・メモリ１１０８とその適切な対応するコンピューティング・システム・インターフェース（およびコンピューティング・システムの設計によっては内部記憶装置）の間でデータが適正に渡されることを保証するためにICHが使われてもよく、ICH自身と観察されたI/O機器との間の双方向のポイントツーポイント・リンクを有していてもよい。メモリ・コントローラ１１０４は、CPU  １１０２、インターフェースおよび内部記憶要素の間での、システム・メモリ１１０８に対する、互いに時間的に近接して生起しうるさまざまな競合する要求を管理するために使われてもよい。
【００６３】
一つまたは複数のI/O機器が、コンピューティング・システム１１００へおよび／またはコンピューティング・システム１１００からデータを転送するために（たとえばネットワーキング・アダプタ）、あるいはコンピューティング・システム１１００内の大規模不揮発性記憶のために（たとえばハードディスク・ドライブ）、実装されてもよい。
【００６４】
本発明のさまざまな実施形態の諸部分は、コンピュータ・プログラム・プロダクトとして提供されてもよい。そのようなコンピュータ・プログラム・プロダクトは、本発明の実施形態に従ったプロセスを実行するようコンピュータ（または他の電子装置）をプログラムするために使用されうるコンピュータ・プログラム命令が記憶されたコンピュータ可読媒体を含んでいてもよい。機械可読媒体は、これに限られないが、フロッピー（登録商標）ディスケット、光ディスク、コンパクトディスク読み出し専用メモリ（CD-ROM）および光磁気ディスク、ROM、RAM、消去可能型プログラム可能読み出し専用メモリ（EPROM）、電気的EPROM（EEPROM）、磁気もしくは光カード、フラッシュ・メモリまたは電子的な命令を記憶するのに好適な他の型のメディア／機械可読媒体を含みうる。
【００６５】
以上の明細書において、本発明について個別的な例示的実施形態を参照しつつ述べてきた。しかしながら、付属の請求項において記載される本発明のより広義の精神および範囲から外れることなくそれにさまざまな修正や変更を施してもよいことは明白であろう。よって、本明細書および図面は制約する意味ではなく、例解するものとして見なされるべきである。
【符号の説明】
【００６６】
１０２  入力ビデオ
１０４  前処理
１０６  ビュー型分類
１０８  ハフ直線検出およびキー点抽出
１１０  十分な点？
１１２  直接的推定
１１４  マッピング仮説生成
１１６  仮説評価
１１８  間接的推定
１２０  グローバル動き推定
１２２  現在マッピング遷移
１２４  ホモグラフ行列(H1)
２０２  現実の交差点
２０４  仮想交差点
３０２  フィールド・モデル
３０４  画面イメージ〔画像〕
３０６  画面イメージ〔画像〕
３０８  画面イメージ〔画像〕
３１０  ホモグラフィック・マッピング、ホモグラフィー行列、ホモグラフ行列
３１２  ホモグラフィック・マッピング、ホモグラフィー行列、ホモグラフ行列
３１４  ホモグラフィック・マッピング、ホモグラフィー行列、ホモグラフ行列
３１６  動き遷移
３１８  動き遷移
４０２  プレイフィールド領域抽出
４０４  優勢色と整合しないピクセルがリザーブされ二値化
４０６  縦横の直線マークを検出するための二値画像に対するハフ変換
４０８  縦横の線の交点が得られる
５０１  フレーム番号
５０２  元の画像
５０４  ハフ直線
５０６  マッピングされた画像
５０８  位置合わせされたフィールド
６０２  入力ビデオ
６０４  背景モデリングおよび前景抽出
６０６  マルチ・オブジェクト追跡
６０８  ブーストされたオブジェクト検出
６１０  相互作用対応の分散型粒子フィルタリング
６１２  オブジェクト追跡情報：位置および数
１１００  コンピューティング・システム
１１０２  CPU
１１０４  メモリ・コントローラ
１１０６  RAM
１１０８  メモリ
１１１０  グラフィクス・コプロセッサ
１１１２  ディスプレイ
１１１４  ハードウェア・グラフィクス・パイプライン
【図１】
2011134322.tif 000023
【図２】
2011134322.tif 000024
【図３】
2011134322.tif 000025
【図４−１】
2011134322.tif 000026
【図４−２】
2011134322.tif 000027
【図５−１】
2011134322.tif 000028
【図５−２】
2011134322.tif 000029
【図５−３】
2011134322.tif 000030
【図６】
2011134322.tif 000031
【図７】
2011134322.tif 000032
【図８】
2011134322.tif 000033
【図９】
2011134322.tif 000034
【図１０−１】
2011134322.tif 000035
【図１０−２】
2011134322.tif 000036
【図１１】
2011134322.tif 000037