(57)【要約】ユーザインタフェースによるヒューマンインタラクションを取り入れた、ビデオ系列において動くオブジェクトを検出する軌跡に基づいた技術を使用する方法及び関連する装置に関する。本方法は、ビデオフレームにおいて、接続されたコンポーネントのセットを識別及び評価し、接続されたコンポーネントの特徴を予め決定された基準と比較することで接続されたコンポーネントのリストをフィルタリングし、複数のフレームにわたり候補となる軌跡を識別し、候補となる軌跡を評価して選択された軌跡を決定し、インタフェースの使用により誤った軌跡を除き、評価及び除くステップに応じて、ビデオ系列における画像を処理する。
2013514581.tif 000002
【特許請求の範囲】
【請求項１】
ビデオ系列のビデオフレームにおいて、接続されたコンポーネントのセットを識別するステップと、
ユーザインタフェースを通して、選択された接続されたコンポーネントの代替の軌跡を表示するステップと、
前記ユーザインタフェースの入力に応じて、前記選択された接続されたコンポーネントの少なくとも１つの代替の軌跡を除くステップと、
前記除くステップに応じて前記ビデオ系列の画像を表示するステップと、
を含む方法。
【請求項２】
少なくとも１つの画像の特徴に関して、前記接続されたコンポーネントのセットのそれぞれを評価するステップと、
前記接続されたコンポーネントのそれぞれの前記少なくとも１つの画像の特徴を予め決定された基準と比較して、接続されたコンポーネントからなるフィルタリングされたリストを生成するステップと、
連続するフレームについて、前記識別するステップ、前記評価するステップ及び前記比較するステップを繰返すステップと、
前記接続されたコンポーネントのうちの１つを選択するステップと、
前記表示するステップについて、複数のフレームにわたり生成される前記選択された接続されたコンポーネントの代替の軌跡のセットを生成するステップと、
を含む請求項１記載の方法。
【請求項３】
前記選択された接続されたコンポーネントに属する前記代替の軌跡について信頼レベルを生成するステップと、
予め決定された値未満の信頼レベルを有する代替の軌跡を除去するステップと、
を更に含む請求項２記載の方法。
【請求項４】
前記少なくとも１つの画像の特徴は、領域、離心率又は白色度である、
請求項３記載の方法。
【請求項５】
前記ユーザインタフェースは、フレーム時間の関数として代替の軌跡を表す軌跡のビューを利用する、
請求項４記載の方法。
【請求項６】
前記ユーザインタフェースは、複数のフレームのサムネイルビュー及び前記選択された接続されたコンポーネントを強調する前記サムネイルビューにおけるインジケータを利用する、
請求項４記載の方法。
【請求項７】
前記ユーザインタフェースは、前記サムネイルビューにおける前記選択された接続されたコンポーネントを、前記軌跡のビューにおける前記代替の軌跡のうちの１つに関連付ける更なるインジケータを利用する、
請求項６記載の方法。
【請求項８】
前記接続されたコンポーネントのセットを識別するステップは、前記ビデオ系列の画像を処理して、局所的な最大を表す画像を生成するステップを含む、
請求項２記載の方法。
【請求項９】
前記ビデオ系列の画像を処理して、局所的な最大を表す画像を生成するステップを更に含み、前記処理は、前記画像の輝度成分をカーネルと畳込み演算を含む、
請求項２記載の方法。
【請求項１０】
前記カーネルは、正規化されたガウス核である、
請求項９記載の方法。
【請求項１１】
前記基準は、最も近い代替の軌跡への距離、フィールドのエッジへの距離、又は２値オブジェクトマスク内の同じ接続されたコンポーネント内の代替の軌跡の数を含む、
請求項２記載の方法。
【請求項１２】
前記代替の軌跡を評価して選択された軌跡を決定するステップは、接続されたコンポーネントのペアを識別するステップを含み、
前記ペアの１つのコンポーネントは、第一の画像にあり、前記ペアの１つのコンポーネントは、次の画像にあり、
前記ペアにおける２つの接続されたコンポーネントの位置間の距離は、予め決定された距離の閾値未満である、
請求項２記載の方法。
【請求項１３】
前記代替の軌跡を評価して選択された軌跡を決定するステップは、前記軌跡の長さ、前記軌跡を構成する接続されたコンポーネントの特性、及び前記軌跡における根拠のないポイントの数、を評価する、
請求項２記載の方法。
【請求項１４】
前記選択された軌跡に少なくとも部分的に基づいて前記ビデオ系列における画像を処理するステップは、前記選択された軌跡に沿って移動するオブジェクトを強調する、
請求項２記載の方法。
【請求項１５】
前記ユーザインタフェースを介して、前記除くステップにおいて前記選択された接続されたコンポーネントの代替の軌跡を分類するステップを更に含み、前記ユーザインタフェースは、前記代替の軌跡の分類のためのコンテクストメニューを利用する、
請求項７記載の方法。
【請求項１６】
前記ユーザインタフェースは、複数のフレームのサムネイルビュー、前記選択された接続されたコンポーネントを強調する前記サムネイルビューにおけるインジケータ、及び前記代替の軌跡を表示する軌跡ビューを使用し、前記インジケータは、特定の軌跡を特定の選択された接続されたコンポーネントに関連付ける、
請求項２記載の方法。
【請求項１７】
前記サムネイルは、代替の軌跡の実行されているビデオである、
請求項６記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、映像系列における軌跡に基づいた検出システムに関する。  
本出願は、2009年12月16日に提出された米国特許仮出願第61/284,261号の利益を特許請求するものであり、その内容は本明細書に盛り込まれる。
【背景技術】
【０００２】
携帯機器の機能が益々充実し、携帯デジタルテレビ規格が開発されるにつれて、係る装置でビデオ番組を見ることがますます実用的になってきている。しかし、これらの装置の小型スクリーンは、特にスポーツイベントの視聴について幾つかの制限を提示する。スポーツ番組におけるボールのような小さなオブジェクトは、見る事が困難である。高いビデオ圧縮率を使用することは、特に遠くのシーンにおけるボールのような小さなオブジェクトの外観を著しく低下させることで、状況を悪化させる。
【０００３】
従って、画像処理を適用してボールの外観を改善することが望ましい。スポーツビデオにおけるボール又はビデオにおける他の小さな動くオブジェクトを検出することは、困難な課題である。例えばボールは、フィールドラインで遮蔽されるか又はマージされる可能性がある。ボールが完全に目に見えるときでさえ、形状、領域及び色のようなその特性はフレームからフレームへと変わる場合がある。さらに、あるフレームにおいてボールのような特性をもつ多くのオブジェクトが存在する場合、唯一のフレームに基づいてどれがボールであるかに関する判定を行うことは困難であり、従って画像のエンハンスメントを行うことは困難である。
【０００４】
サッカーボール等のような動くオブジェクトを検出して追跡する方法がこれまで開発されており、かなりロバスト且つ正確である。係る方法は、PCT/US10/002039に開示されている。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、これまでの方法は、幾つかの状況において機能しない。機能しない例は、ボールのような所望のオブジェクトを追跡しないこと、又は所望のオブジェクトではない別のオブジェクトを追跡することを含む。  
係るように、従来技術の問題を解決する動くオブジェクトを検出して追跡する改善された方法を提供する必要が存在する。
【課題を解決するための手段】
【０００６】
上述された課題を解決するため、本発明は、ユーザインタフェースによるヒューマンインタラクションを取り入れた、ビデオ系列において動くオブジェクトを検出する軌跡に基づいた技術を使用する方法及び関連する装置に関する。本方法は、ビデオフレームにおける接続されたコンポーネントのセットを識別して評価するステップ。接続されたコンポーネントの特徴を予め決定された基準に比較することで、接続されたコンポーネントのリストをフィルタリングするステップ、複数のフレームにわたり候補となる軌跡を識別するステップ、候補となる軌跡を評価して、選択された軌跡を決定するステップ、インタフェースの使用により正しくない軌跡を除去するステップ、及び評価ステップ並び除去するステップに応じて、ビデオ系列における画像を処理するステップを含む。
【図面の簡単な説明】
【０００７】
本発明は、添付図面を参照して例を通して以下に記載される。
【図１】本発明に係る軌跡に基づくボール検出方法を例示するフローチャートである。
【図２】プレイフィールドマスクを生成し、ボールの候補を識別するプロセスを例示する図である。
【図３】ビデオフレームにおけるボールの候補を例示する図である。
【図４】例示的な候補となる軌跡のプロットである。
【図５】例示的な候補となる軌跡と実際のボールの軌跡のプロットである。
【図６】候補間の違いを示し、多くの候補となる軌跡において所与の候補がどのように存在するかを示す例示的な候補となる軌跡の２次元プロットである。
【図７】異なる視点から図６の例示的な候補となる軌跡のプロットである。
【図８】本発明に係るユーザインタフェースのビューを例示する図である。
【図９】本発明に係るユーザインタフェースの別のビューを例示する図である。
【図１０】本発明に係る軌跡に基づくボール検出及び表示方法のフローチャートである。
【図１１】本発明に係る軌跡に基づくボール検出方法のフローチャートである。
【発明を実施するための形態】
【０００８】
本発明の鍵となる態様は、人間又は別の信頼できる情報源からの最小の入力を使用することで、オブジェクト検出システムの性能を改善することである。
【０００９】
軌跡に基づいた検出システムの目的は、おそらく実際のオブジェクトの経路を表すことである、軌跡のセットＢＴ⊆Ｔを生成することである。Ｔ＝｛Ｔ1,Ｔ2,．．．,ＴM｝は、全ての候補となる軌跡のセットであり、それぞれの候補となる軌跡Ｔ＝｛Ｃ1i,Ｃ2i,ＣNi｝は、所定の時間間隔において滑らかに動いているオブジェクトの実行可能な仮説を形成する連続するフレームにおける候補となるセットであり、１つのフレーム当たり１つの候補が存在する。候補は、ボール又は関心のあるオブジェクトである可能性がある、特定のフレームにおけるオブジェクトである（なお、候補“candidate”はオルタネート“Alternate”とも呼ばれる）。全ての候補のセットは、Ｃと呼ばれ、候補Ｃkiは、軌跡Ｔiのｋ番目のエレメントである。
【００１０】
ＢＴを形成する方法は、軌跡Ｔiを構成するエレメントに基づいて計算される最も高い候補のインデックスΩ(Ｔi)をもつ軌跡を繰り返し取り込み、それを移動させてＢＴを設定するアルゴリズムである。次いで、ＢＴとの所定の不適合さの程度をもつＴにおける全ての軌跡は、トリミングされるか又は削除される。Ｔにおいて軌跡がもはや存在しないとき、アルゴリズムが停止する。
【００１１】
図１は、本発明により採用される軌跡に基づくボール検出方法１００の１実施の形態のフローチャートである。本方法は、サッカーの試合のようなスポーツイベントである場合がある、入力ビデオ系列１１０に適用される。
【００１２】
ステップ１２０で、プレイフィールドマスクＰＭが生成される。マスク生成は、グラスマスクＧＭを生成するため、芝生の領域を検出し、次いで、これら芝生の領域をカバーする穴のない領域である、プレイフィールドマスクを計算することを含む。
【００１３】
ステップ１３０で、ボールである場合がある候補となるオブジェクトが検出される。フレームＦの輝度成分Ｙを正規化されたガウスカーネルＧnkで畳込み演算を行い、出力画像Ｙconvを生成することで、強度画像において局所的な最大値が検出される。画素（ｘ,ｙ）は、Timaxを予め設定された閾値として、Ｙ（ｘ,ｙ）＞Ｙconv（ｘ,ｙ）＋Ｔimaxである場合に、局所的な最大値として指定される。このアプローチは、ボールの画素を分離させることに成功するが、プレーヤ、フィールドライン、ゴールマウス等の幾つかの部分を分離する。それは、これらの特徴が局所的な最大となることができる明るいスポットを含むためである。最終的な結果は、１番目を示す明るいスポットをもつバイナリ画像Ｉimである。Ｉimにおける接続されたコンポーネントＺ＝｛Ｚ1,Ｚ2,．．．，Ｚn｝のセットは、「候補」と呼ばれ、「ボールの候補」を検出するために次のステップにおいて処理される。実施の形態では、Ｇnkは、分散４をもつ９×９のガウス核であり、閾値Ｔimaxは０．１である。
【００１４】
ステップ１２０のプレイフィールド検出からの情報は、候補の数を低減するためにステップ１３０及び１４０で使用される。遠くのシーンにおいて、ボールがプレイフィールドの内側にあり、プレイフィールドの外側のオブジェクトは無視されるという想定がなされる。
【００１５】
図２は、候補の検出のために使用されるプロセスのグラフによる例示を与える。フレーム２１０が与えられると、サッカーフィールドの画素は、フィールドが芝生からなるという情報を使用して識別される。プロセスの結果は、全てのフィールド画素を１として識別し、フィールドにおけるオブジェクトを含む全ての非フィールド画素を０として識別するバイナリマスク２３０である。サッカーフィールドエリアＡfieldは、非フィールドのオブジェクトを含めて、画像２４０に示される、フィールドの境界における画素数として計算される。候補の検出の結果は、画像２２０に示される。フィールド領域にない候補は、除かれ、結果として画像２５０が得られる。
【００１６】
ステップ１３０からの候補の幾つかは、ボールである可能性が非常に低く、ステップ１４０でふるい分け及び認定プロセスを使用して除かれる。スコアは、それぞれの候補について計算され、それぞれがボールの予め確立されたモデルにどの位類似しているかに関する認定が与えられる。
【００１７】
候補の幾つかは、ボールの特徴の統計情報を使用して除去することができる。実施の形態では、ボールの３つの特徴が考慮される。  
Area(A)（領域）は、候補Ｚiにおける画素の数である。  
Eccentricity(E)（離心率）は、「細長さ“elongateness”」の測度である。オブジェクトが細長くなると、離心率が高くなる。実施の形態では、離心率を計算するために２値画像のモーメントを使用することができる。  
Whiteness(W)（白色度）は、白色である画素の品質である。所与の画素のｒ，ｇ及びｂ（それぞれ赤、緑及び青成分）が与えられると、白色度は以下のように定義される。
【００１８】
【数１】
2013514581.tif 000003
サンプルビデオの分析は、領域及び白色度ヒストグラムはガウス分布に従うことを示す。また、離心率ヒストグラムは、離心率の最小値が１であると考慮するため、対称化の後にガウス分布に従う。候補は、それらの特徴が範囲μ±ｎσの外にある場合に却下され、μは平均であり、σは対応する特徴の分布の標準偏差である。このふるいわけプロセスＳに基づいて、Ｚにおける候補は、ボールのようなオブジェクトとして受け入れられるか又は却下される。ボールの特徴はフレームからフレームへと著しく変化するため、緩い範囲が使用される。
【００１９】
領域Ａは、μA＝7.416及びσA＝2.7433によるガウス分布としてモデル化され、範囲はｎA＝３により制御される。Ｅは、μE＝1及びσE＝1.2355によるガウス分布としてモデル化され、範囲はｎE＝３により制御される。Ｗは、μW＝0.14337及びσW＝0.034274によるガウス分布としてモデル化され、範囲はｎW＝３により制御される。候補は、全ての３つの基準が保持されるように適合する必要がある。
【００２０】
また、ステップ１４０において、ふるいわけプロセスＳ（Ｚ）を通過した候補Ｃは、それらの特徴とボールの予め確立されたモデルとの類似性に基づいて認定される。Ａ，Ｅ及びＷは、ボールの候補のスコアを計算するあめに使用されるが、以下に加えて、より厳密なｎの値が使用される。  
最も近い候補への距離（ＤＣＣ）：ある候補Ｃiにおける何れかの画素と他の候補｛Ｃ−Ｃi｝における全ての他の画素との間の画素における最も近い距離。  
フィールドのエッジへの距離（ＤＦ）：所与の候補の中央とプレイフィールドマスクＰＭの外周との間の画素における最も近い距離。  
オブジェクトマスクにおけるそれぞれのブロブ内にある候補の数（ＮＣＯＭ）：所与の候補ＣiとしてオブジェクトマスクＯＭにおける同じ接続されたコンポーネント内にあるＣにおける候補の数。オブジェクトマスクＯＭは、プレイフィールド内の非芝生の画素を示す２値マスクであり、ＰＭ内のＧＭの反転として定義される。
【００２１】
ボールは、互いに常に近いプレイヤのソックスのようなオブジェクトは対照的に、大部分の時間でプレイフィールド内で分離されたオブジェクトであることが期待される。従って、近隣のオブジェクトをもたず、且つ高いＤＣＣを持つ候補は、ボールである可能性が高い。同様に、ボールはフィールドの境界の近くにあることも期待されない。この仮定は、芝生内に他のスペアボールが存在し、プレイフィールドの境界線の外にある場合に特に重要である。
【００２２】
ＯＭは、プレイフィールド内のどの画素が芝生でないかに関する情報を与える。これは、プレーヤ及びフィールドラインを含み、それらの内部に（例えばプレーヤのソックス又はライン部分といった）「ボールのような」ブロブを含む。理想的に、ボールの候補は、他の大きなブロック内にはない。唯一の候補ＣiがＯＭの接続されたコンポーネント内にあることが期待されるとき、ＮＣＯＭiは、理想モデルにおいて１であることが期待される。
【００２３】
従って、ＮＣＯＭを計算することから利益を得る。ある候補ＣiのスコアＳiは、以下のように計算される。
【００２４】
【数２】
2013514581.tif 000004
現段階で、０に等しいスコアを有する候補が拒否される。残りの候補について、スコアＳiは、以下の他の特徴を使用してペナルティが課される。
【００２５】
【数３】
2013514581.tif 000005
実施の形態では、μA＝7.416，σA=2.7443，ｎA＝1.3，μE＝1，σE=1.2355，ｎE＝1.3，μW＝0.14337，σW=0.034274，ｎW＝1.3，DCCthr＝7画素，DFthr＝10画素及びNCOMthr＝1である。
【００２６】
図３は、あるフレームにおけるボールの候補の識別の結果を例示するものであり、（ボールの候補３１０〜３９０についての）カウンディングボックスは、ボールの候補の存在を示す。候補のスコアを表す異なる色がインタフェースにおいて提示される。赤、緑及び青は、３，２及び１のスコアをそれぞれ表す。図３において、候補３９０は赤（すなわちスコア３）であり、候補３５０は緑（すなわちスコア２）であり、残りの候補は青（すなわちスコア１）である。この例示では、候補３１０，３２０，３３５，３４０，３６０及び３８０は、プレイヤの一部又はプレイヤの服を表し、候補３３０，３７０は、フィールドの他のオブジェクトを現し、候補３９０は、実際のボールを表す。
【００２７】
ステップ１５０で、軌跡の開始ポイント又は「シード“seed”」が識別される。候補のペア｛Ｃi，Ｃj｝が閾値ＳＥＥＤthrよりも互いに空間的に近く、且つ１つの候補のスコアが３であるか、又は２つの候補のスコアが２である基準の何れかを満たすように、シードＳＥＥＤkは、２つの連続するフレームＦt，Ｆt+1におけるボールの候補のペア｛Ｃi，Ｃj｝であり、ＣiはＦtに属し、ＣjはＦt+1に属する。好適な実施の形態では、ＳＥＥＤthr＝８画素である。基準は、時間の複雑度のような他の検討事項に対処するために変更される。
【００２８】
ステップ１６０で、候補の軌跡は、ステップ１５０のシードから作成される。軌跡Ｔi＝｛Ｃ1i，Ｃ2i，．．．，ＣNi｝は、フレーム当たり１つで、連続するフレームにおける候補のセットとして定義され、所定の時間間隔又はシードＳＥＥＤiを使用して生成されるフレームレンジにおいて滑らかに動いているオブジェクトの実行可能な仮説を形成する。
【００２９】
両方向においてシードを成長させることで、軌跡を形成するために線形カルマンフィルタが使用される。シードを構成する２つのサンプルは、フィルタの初期状態を決定する。この情報を使用して、フィルタは、次のフレームにおけるボールの候補の位置を予測する。予測された位置でセンタリングされるサーチ窓内に次のフレームにおける候補が存在する場合、予測された位置に最も近い候補が軌跡に追加され、その位置は、フィルタを更新するために使用される。候補が窓において発見されない場合、予測された位置は根拠のないポイントとして軌跡に追加され、フィルタを更新するために使用される。軌跡を構築する手順は、ａ）Ｎ個の連続するフレームについて予測された位置に近い候補が存在しない場合、及びｂ）予測された位置の近くでＫ（例えばＫ＝１）を超える個数の候補が存在する場合に終了する。フィルタは、双方向の方式で機能し、従って時間的に前方に軌跡を成長させた後、カルマンフィルタは、再初期化され、時間的に後方に成長される。軌跡を終了する第一の基準は、その極値で根拠のないポイントのセットを生成する。次いで、これらの根拠のないポイントは、軌跡から除去される。
【００３０】
図４は、上述された方法を使用して形成された候補となる軌跡４１０〜４６０のプロット４００を例示する。ｘ軸は、フレームにおける時間を表す。ｙ軸は、潜在的なボールと画像の左上の画素との間のユークリッド距離である。異なる候補となる軌跡を例示するために複数の色が使用される。
【００３１】
候補となる軌跡Ｔ＝｛Ｔ1,Ｔ2,．．．,ＴM｝の幾つかは、実際のボールにより記述される経路の一部であり、他は、他のオブジェクトに関連する軌跡である。アルゴリズムの目標は、他を却下する一方、実際のボールの経路を表している可能性が高い軌跡のセブセットを選択することで、軌跡ＢＴを形成することである。アルゴリズムは、軌跡の信頼インデックス、軌跡のオーバラップインデックス、及び軌跡の距離のインデックスの使用を含む。それぞれの軌跡のスコアは、軌跡の長さ、軌跡を構成する候補のスコア、及び軌跡における根拠のないポイントの数に基づいて生成される。
【００３２】
信頼インデックスは、以下のように計算される。
【００３３】
【数４】
2013514581.tif 000006
Ω（Ｔj）は軌跡Ｔjの信頼インデックスであり、ｐiはスコア“ｉ”をもつＴjにおける候補の数、ｑi＝ｐi／｜Ｔj｜であり、軌跡においてスコア“ｉ”をもつ候補の分数であり、｜Ｔj｜は、軌跡における候補の数であり、λi及びωi（λ1＜λ2＜λ3及びω2＜ω3）は、コンポーネントの重要度を調節し、ｒは、軌跡における根拠のないポイントの数であり、Tは根拠のないポイントの重要度ファクタである。実施の形態ではλ1＝0.002，λ2＝0.2，λ3＝5，ω2＝0.8，ω3＝2及びT=10である。
【００３４】
それぞれ選択された軌跡について、時間的にオーバラップするものがある。オーバラップインデックスが高い場合、対応する軌跡が廃棄される。インデックスが低い場合、競合する軌跡のオーバラップする部分がトリミングされる。
【００３５】
このオーバラップインデックスは、高い信頼インデックスをもつ長い軌跡に報酬を与える一方、オーバラップしているフレームの数にペナルティを課す。
【００３６】
【数５】
2013514581.tif 000007
ここでＸ（Ｔi,Ｔj）は、軌跡Ｔiの軌跡Ｔjとのオーバラップインデックスである。ρ（Ｔi,Ｔj）は、ＴiとＴjとがオーバラップするフレームの数である。Ω（Ｔi）は、軌跡Ｔiの信頼インデックスである。
【００３７】
軌跡の距離のインデックスの使用は、ＢＴの空間‐時間の整合性が増加する。ボールが最高速度Ｖmax画素／フレームで移動するという仮説を使用して、軌跡の最も近い極値間のボールの候補の空間的な距離が、Ｖmaxに、極値に許容値Ｄを加えたものの間のフレーム数の倍数よりも高い場合、２つの軌跡ＢＴ及びＴiは、適合しない。さもなければ、２つの軌跡は、適合し、Ｔiは、ＢＴの一部である。
【００３８】
距離インデックスは、以下により与えられる。
【００３９】
【数６】
2013514581.tif 000008
ここでｄｉｓｔ（ｐｏｓ（Ｃi），ｐｏｓ（Ｃj））は、候補Ｃi及びＣjの位置間のユークリッド距離であり、ｆｒａｍｅ（Ｃi）は、候補Ｃiが属するフレームである。ｐｏｓ（Ｃ）は、フレーム内の候補Ｃの中心の（ｘ,ｙ）位置であり、ＢＴiは、ＢＴにおけるｉ番目の候補であり、ＣＰＤは、最も近い前の距離であり、ＣＮＤは、最も近い次の距離であり、ＣＰＦは、最も近い前のフレームであり、ＣＮＦは、最も近い次のフレームである。
【００４０】
ＤＩ（ＢＴ，Ｔi）＝１である場合、軌跡ＴiはＢＴと一致する。この基準がなければ、ＴiをＢＴに加えることは、時間的な不一致の問題を提示する可能性があり、この場合、ボールは、極端に短い時間間隔で、ある空間的な位置から別の位置にジャンプする場合がある。軌跡の選択アルゴリズムに距離インデックスの基準を加えることで、この問題が解決される。好適な実施の形態では、Ｖmax＝10画素／フレーム及びＤ＝10画素である。
【００４１】
２つの軌跡選択アルゴリズムが実現及びテストされる。第一のアルゴリズムは、最も高い信頼インデックスをもつ候補となる軌跡を繰り返し選択し、選択された軌跡と適合しない軌跡を除去又はトリミングする。第二のアルゴリズムは、最短経路の問題として定式化することでこの問題を解決しようとする。２つのアルゴリズムは、匹敵する性能を有するように調整される。
【００４２】
Ｔである候補となる軌跡のセットが与えられると、アルゴリズムは、ビデオ系列に沿ったボールの軌跡を記述する候補となる軌跡のサブセットを出力ＢＴとして生成する。アルゴリズムは、最も高い信頼インデックスをもつ軌跡をＴから繰り返し取り込み、それをＢＴに移動する。次いで、ＢＴとオーバラップしているＴにおける全ての軌跡が処理され、オーバラップするインデックスＸ（ＢＴ，Ｔi）及び距離インデックスＤＩ（ＢＴ，Ｔi）に依存して、軌跡のトリミング又は除去が行われる。アルゴリズムは、Ｔにおいて１以上の軌跡が存在しないときに停止する。
【００４３】
アルゴリズムは、以下のように記述される。
【００４４】
【表１】
2013514581.tif 000009
トリミング処理ｔｒｉｍ（ＢＴ，Ｔi）は、軌跡Ｔiから、ＢＴとＴiとの間のオーバラップしているフレームにある全ての候補を除去することからなる。このプロセスがＴiの時間的なフラグメンテーション（すなわち候補は中央から除去される）につながる場合、新たな軌跡としてフラグメントがＴに加えられ、Ｔiは、Ｔから除去される。好適な実施の形態では、オーバラップインデックスの閾値Ｏthr＝０．５が使用される。
【００４５】
図５は、候補となる軌跡５１０〜５５０のセットのプロット５００であり、そのうちの幾つかは、実際のボールの軌跡である。ｘ軸は、フレームにおける時間を表す。ｙ軸は、ボールと画像の左上画素との間のユークリッド距離である。軌跡５２０及び５３０は、ボールの軌跡を記述するアルゴリズムにより選択され、実際のボールの軌跡である。軌跡５１０，５４０及び５５０は、アルゴリズムにより却下される。楕円部分５７０は、ボールの実際の経路を表す。例えば、軌跡の選択アルゴリズムは、実際のボールの軌跡の非常に正確な推定を提供することがわかる。
【００４６】
最終的なボールの軌跡を生成する別の方法は、Dijkstraの最短経路アルゴリズムに基づく。候補となる軌跡は、グラフにおけるノードとして見られる。２つのノード（又は軌跡）間のエッジは、２つの軌跡間の適合性の測度として重み付けされる。適合度の測度の逆は、ノード間の距離として見ることができる。全体のボールの経路の開始及び終了の軌跡（Ｔs，Ｔe）が既知である場合、その間の軌跡は、経路に沿った距離の合計を最小化することでノードＴs及びＴe間のグラフにおける最短経路を発見するDijkstraのアルゴリズムを使用して選択される。
【００４７】
第一のステップで、軌跡間の適合度のスコアを含む適合度マトリクスが生成される。Ｎを候補となる軌跡の数とする。Ｎ×Ｎの適合度マトリクスのセル（ｉ,ｊ）は、軌跡ＴiとＴjの間の適合度スコアを含む。
【００４８】
２つの軌跡Ｔi及びＴjが所定の閾値を超えてオーバラップするか、又はＴiがＴjの後に終了した場合、それらの間の適合度インデックスは、無限大となる。ＴiがＴjの後に終了することを強制することで、経路は常に時間的に先進することが保証される。なお、Φ（Ｔi,Ｔj）がΦ（Ｔj,Ｔi）と同じである必要はないので、基準は適合度マトリクスが非対称であることを意味することに留意されたい。ＴiとＴjとの間のオーバラップインデックスが小さい場合、低い信頼インデックスをもつ軌跡は、適合度インデックスを計算するためにトリミングされる。２つの軌跡間の適合度インデックスは、以下のように定義される。
【００４９】
【数７】
2013514581.tif 000010
ここでΦ（Ｔi,Ｔj）は、軌道ＴiとＴjとの間の適合度インデックスであり、Ω（Ｔi）は、軌跡Ｔiの信頼インデックスである。ｓｄｉｓｔ（Ｔi,Ｔj）は、Ｔiの終わりでの候補とＴjの開始での候補との間の画素における空間的な距離であり、ｔｄｉｓｔ（Ｔi,Ｔj）は、Ｔiの終わりとＴjの開始との間のフレームにおける時間であり、α，β及びγ（all < 0）は、相対的なコンポーネントの重要度であり、好適な実施の形態では、α＝−１／７０，β＝−０．１及びγ＝−０．１である。
【００５０】
ひとたび適合度マトリクスが作成されると、Dijkstraの最短経路アルゴリズムは、ある軌跡のノードから別の軌跡のノードに進行するための距離（すなわち適合度の逆）を最小にするために使用される。全体のボールの経路の開始及び終了の軌跡（Ｔs，Ｔe）が既知である場合、中間の奇跡は、最短経路のアルゴリズムを使用して発見される。
【００５１】
しかし、Ｔs，Ｔeは、事前に知られていない。開始及び終了の軌跡の全ての組み合わせチェックする複雑度を低減するため、閾値よりも高い信頼インデックスをもつ軌跡を使用して、全ての組み合わせのサブセットのみが考慮される。開始及び終了の軌跡（ノード）のそれぞれの組み合わせが順に考慮され、最短経路が上述されたように計算される。最後に、全てのこれらの組み合わせのうちで全体の最良の経路が選択される。
【００５２】
最良のボールの経路は、低コストを有し、時間的に長く、以下の関数を最小にする。
【００５３】
【数８】
2013514581.tif 000011
Ｑは、最初の軌跡Ｔiから最後の軌跡Ｔjまでの最短経路のアルゴリズムを使用して構築されるＴ（ボール経路）からの軌跡のサブセットであり、ＳＣ（Ｑ）は、Ｑのスコアであり、ＣＤ（Ｑ）は、Ｑにおける軌跡を通過する、最初の軌跡Ｔiから最後の軌跡Ｔjまでのコストであり、ｌｅｎｇｔｈ（Ｑ）は、時間的ば軌跡のセットＱの長さであり（すなわち軌跡間のギャップを含むＱによりカバーされるフレーム数）、ｍａｘ＿ｃ及びｍａｘ＿ｌは、構築される全ての最短の経路のうちの最大コスト及び最長の長さである（開始及び終了の奇跡のそれぞれの組み合わせについて１つ）、ｗはコスト対長さの相対的な重要度であり、この実施の形態では、ｗ＝０．５である。
【００５４】
アルゴリズムの結果を改善する１つの方法は、軌跡の信頼インデックスをユーザが操作するのを可能にすることである。これを行うことで、アルゴリズムは、ＢＴを形成するために良好な軌跡の選択を生成するために誘導される。
【００５５】
残念なことに、軌跡の形状により軌跡がノーるのを含むことをユーザは保証することができず、他方で、アルゴリズムにより選択された候補が実際にボールであるかをチェックするため、フレーム毎に進めることはユーザにとって面倒である。
【００５６】
候補をダイレクトに扱う代わりに軌跡のレベルで機能する利点の１つは、ＢＴにおける軌跡のセットの濃度がＢＴにおける候補のセットの濃度よりも常に低いことである。さらに、高い可能性で、所与の軌跡を形成する候補は、同じオブジェクトに対応する。これら２つの仮定を使用して、ＢＴを構成する軌跡についてその選択された候補をもつ唯一のフレームにより、ＢＴにおける軌跡が適切に選択されているかをユーザに迅速に通知し、適切に選択されていない場合には是正措置をとることで十分である。
【００５７】
ユーザにとっての相互作用のエレメントは候補であり、軌跡ではない。従って、ユーザは、（ボールである）良い候補又は（ボールでない）誤った候補として候補を分類することができる。
【００５８】
Ｃgを良い候補とし、Ｃwを誤った候補とする。次いで、
【数９】
2013514581.tif 000012
は、それぞれ、良い候補と誤った候補とを含む軌跡のセットである。
【００５９】
最終的に、候補をＣg及びＣwをとして分類する目標は、Ｔwからの軌跡ではなく、Ｔgからの奇跡を含むＢＴを生成することである。従って、ＢＴを生成するアルゴリズムは、分類された候補を利用するために、幾つかのやり方で変更される。以下は、係る変更の例である。
【００６０】
明らかに、ＢＴの一部となるようにＴgからの軌跡を有することが望まれ、従ってこれを達成するオプションは、Ｔにおける他の軌跡よりも高い信頼インデックスを軌跡Ｔgに与えることである。先に記述されたアルゴリズムは、最も高い信頼インデックスをもつＴからの軌跡を繰り返し取る。
【００６１】
これを追跡する１つの方法は、Ｔにおける最大値よりも大きい新たな信頼インデックスをＴgに与えることによる。これが機能するとしても、これが最良のオプションではない。それは、全ての軌跡Ｔgが同じ信頼インデックスを有し、どれが最小の軌跡であるかを判定することができないためである。良い候補を共有することができる幾つかの軌跡が存在することを念頭に置くことは重要である。図６及び図７を参照されたい。図６は、候補の軌跡のセットを示す。Ｘ軸は、フレームにおける時間を表す。Ｙ軸は、候補と画像の左上の画素との間のユークリッド距離である。Ｚ軸は、異なる軌跡を示すために使用される。候補となる軌跡は通常はオーバラップすることに気付くことは重要である。異なるシェーディングレベルは、軌跡を区別するために使用される。図６に示される多数の軌跡が存在する。例えば、影付けされたバンド６０１〜６１０のそれぞれは、所与の候補となる軌跡であるそれぞれ狭いラインをもつ軌跡のセットである。
【００６２】
図７は、候補となる軌跡Ｔのセットの２次元の表現である。Ｘ軸は、フレームにおける時間を表す。Ｙ軸は、候補と画像の左上の画素との間のユークリッド距離である。図６における軌跡の幾つかは、図７で示される。
【００６３】
好適なオプションは、ポジティブなバイアスＫをそれらの信頼インデックスに加えることである。これを行うことで、Ｔgにおける軌跡は、Ｔgの間で競争する。これは、それらの前の信頼インデックスは、どの軌跡がＢＴについての最初の選択であるかを判定するからである。バイアスＫは、Ｔにおける最大の信頼インデックスとして設定されるか、又はより高い値として設定される。
【００６４】
図８は、ユーザがデータと接触するユーザインタフェースを示す。上のユーザインタフェースプロット又は軌跡のビュー８２０は、候補となる軌跡Ｔを示し、図７におけるように、Ｘ軸はフレームにおける時間を表し、Ｙ軸は、候補と画像の左上画素との間のユークリッド距離を表す。太い軌跡６０４，６０８，６１０及び太線により表される２つの他のラベル付けされない軌跡は、現時点でＢＴに属する。プロットの下には、サムネイル８０１のセットが存在し、それぞれ１つはＢＴの軌跡に関連される。ボールとして検出されたオブジェクト８０５は、サムネイルの中央にあり、円により囲まれている（明確さのために二重下線が施されており）、従ってユーザは、軌跡がボールを追跡しているか否かを迅速に見ることができる。サムネイルが選択されたとき、選択されたサムネイル８０２のフレームは、ボトム又は選択フレーム８１０に現れる。ユーザは、候補となるオブジェクトをボールと設定／非設定することで、候補となるオブジェクトと相互作用する。明確さのために一重下線が施される矩形は、候補を示し、円は、どの候補がボールとして選択されたかを示す。円及び他のマーキングは、ユーザインタフェースの一部であるマーカであり、ユーザインタフェースは、サムネイルにおけるオブジェクトを、サムネイル８０１、ボトム又は選択フレーム８１０におけるオブジェクト及びユーザインタフェースプロット８２０における軌跡と、ユーザが関連付けするのを可能にする。
【００６５】
ユーザは、Ｔwからの軌跡がＢＴの一部となるのを望まない。このことを考慮して、２つのオプションがここでは妥当である。第一のオプションは、Ｔwにおける全ての軌跡を除くことであり、第二のオプションは、それらの信頼インデックスに悪いスコアを与えるように、それらの信頼インデックスを変更することである。
【００６６】
Ｔwからの全ての軌跡を除くことで、それらの何れもＢＴに現れないことが保証される。他方で、この出来事の見込みが低いとしても、トリミングされ、ＢＴを生成するために使用される軌跡の機会を除く。
【００６７】
Ｔwの軌跡に負の値を与え、その信頼インデックスが０よりも低い軌跡を却下するようにアルゴリズムを変更することで、ＢＴを構築するため、Ｔwからの軌跡を使用する問題を回避することができる。ＢＴを生成するプロセスの間、Ｔwからの幾つかの軌跡が誤りとして分類された候補が除かれるやり方でトリミングされる場合、軌跡は、ＢＴの一部になる。信頼インデックスは、誤った候補が除かれた後に正になる。
【００６８】
図９は、インタフェースを再び示す。ここで、選択されたサムネイル８０２は、誤った軌跡６１０を含む。ここで、フレームは、インタフェースのボトム８１０に表示される。候補をクリックすることで、コンテクストメニュー８１５は、スクリーンに現れ、ユーザは、図９に示されるように、その候補を誤った候補として選択することができる。これは、誤った候補を含む全ての軌跡の信頼インデックスを低くし、ＢＴは、計算し直される。
【００６９】
システムは、候補のセットを生成するために使用されるボールの予め確立されたモデルを有する。離心率、サイズ及び色は、上述されたようにモデルの幾つかのエレメントである。
【００７０】
僅かな変更により、システムは、ボールのモデルを更新するため、ユーザ入力から利益を得る。例えば、ユーザがボールの候補を良いボールの候補として設定するたび、モデルのパラメータは、新たな候補と良好に整合するために変更される。
【００７１】
本発明は、図１０におけるフローチャートに示される方法とすることができる。本方法は、ビデオ系列の一部であるビデオフレームにおける接続されたコンポーネントのセットを識別するステップ１０１０を含む。接続されたコンポーネントは、ボールの画素又は靴のような他のオブジェクトの画素である。次いで、ステップ１０２０は、少なくとも１つの画像の特徴に関して接続されたコンポーネントのセットのそれぞれを評価し、画像の特徴は、領域、離心率又は白色度である。次いで、ステップ１０３０は、接続されたコンポーネントのセットのそれぞれの少なくとも１つの画像の特徴を予め決定された基準と比較し、接続されたコンポーネントのフィルタリングされたリストを生成し、このステップは、図１におけるステップ１２０及び１３０の適用を含み、あるフレームの輝度値又は色度値を予め決定された基準として使用し、バックグランドを除去することを含む。ステップ１０４０は、他の連続するフレームにおいて、同じ繰り返すステップ、識別するステップ、評価するステップ及び比較するステップを実行する。ステップ１０５０は、接続されたコンポーネントのうちの選択されたコンポーネントを選択することを含む。次いで、ステップ１０６０は、複数のフレームにわたり生成された、選択された接続されたコンポーネント（すなわち関心のあるオブジェクト）の候補となる軌跡のセットを生成する。ステップ１０７０は、表示するステップであり、この表示するステップでは、選択された接続されたコンポーネントの候補となる軌跡がユーザに示され、本方法は、チャート、プロット等で軌跡をユーザが見るのを可能にするユーザインタフェースを組み込んでいる。ステップ１０８０は、ユーザにより提供された幾つかの入力により、ユーザインタフェースを通して選択された接続されたコンポーネントの特定の候補となる軌跡をユーザが除くステップである。少なくとも１つの実施の形態では、ユーザは、軌跡をダイレクトに除去しないが、候補がボールであるか否かを示すフィードバックを、このステップにおいてアプリケーションに与える。この除去するステップでは、ユーザは、これらの候補がＢＴに含まれないように、誤った候補を本質的に識別する。ステップ１０９０は、ビデオ系列の最終的な画像は、選択するステップ及び除去するステップに応じて表示され、最終的な画像において、所望のオブジェクト及びその軌跡の可視性を改善するオリジナルビデオの部分が選択される。選択される部分は、クローズアップ、トリミングされた部分又はズームされた部分である。改善される可視性は、所望のオブジェクトのセンタリング又はオブジェクトを有さないフレームの除去を含む。
【００７２】
本発明の特徴は、図１１から更に理解され、セットＢＴは、ステップ１１１０においてアルゴリズムにおいて形成される。ステップ１１２０において、ＢＴにおける軌跡は、サムネイルのビュー及び軌跡を組み込んだユーザインタフェースに表示され、選択される。ステップ１１３０において、軌跡は、（ボールである）良い候補又は（ボールではない）誤った候補として分類することができる。また、ステップ１１１０は、ＢＴの組成変更ステップであり、ＢＴは、改善されたＢＴを取得するためにステップ１１３０に応答して組成変更される。ステップ１１１０、１１２０及び１１３０は、ＢＴがもはや変更しなくなるまで繰返され、ボールのようなオブジェクトの検出が可能となる。本発明の実施の形態では、サムネイルは、候補となる軌跡の実行中のビデオである。
【００７３】
本発明は特定の実施の形態の観点で記載されたが、本発明の範囲に含まれる変更が行われることを理解されたい。例えば、様々な処理ステップは、個別に又は組み合わされて実現される場合があり、汎用又は専用のデータ処理ハードウェア又はソフトウェアで実現される場合があり、閾値及び他のパラメータは、ビデオ入力の変更するタイプに適するように調節される場合がある。
【図１】
2013514581.tif 000013
【図２】
2013514581.tif 000014
【図３】
2013514581.tif 000015
【図４】
2013514581.tif 000016
【図５】
2013514581.tif 000017
【図６】
2013514581.tif 000018
【図７】
2013514581.tif 000019
【図８】
2013514581.tif 000020
【図９】
2013514581.tif 000021
【図１０】
2013514581.tif 000022
【図１１】
2013514581.tif 000023
【国際調査報告】
2013514581.tif 000024
2013514581.tif 000025
2013514581.tif 000026
2013514581.tif 000027