(57)【要約】  カメラ動き解析及び移動物体解析のための方法及び統合システム、並びに、ショットを変更することなく、主として、ビデオ及びビデオセグメントにおけるカメラ動きパラメータからセマンティクスを抽出する方法が説明される。このようなビデオの典型例は、デジタルカメラによって撮影されたホームビデオ及び業務用ビデオ又はフィルムのセグメント、すなわちクリップである。抽出されたセマンティクスは、注釈、ブラウジング、編集、フレーム強調、キーフレーム抽出、パノラマ生成、印刷、検索、要約等の複数のビデオ／画像の理解及び管理のアプリケーションに直接使用することができる。また、移動物体のアプリオリな知識に依拠しない、その移動物体の検出及び追跡を行う自動方法も説明される。これらの方法はリアルタイムで実行することができる。
2008518331.tif 000002
【特許請求の範囲】
【請求項１】
一対の連続した画像間のカメラ動きを推定する方法であって、
前記一対の連続した画像から動きベクトルを求めるステップであって、
前記一対の連続した画像の一方を複数の画素ブロックにセグメント化するステップ（７０２）と、
前記画像の少なくとも１つの特徴に対応するブロックを選択するステップ（７０４）と、
選択された各ブロックに対応する輝度値を求めるステップ（７０６）と、
前記輝度値に基づいて、前記選択されたブロックを、前記一対の連続した画像の他方の画素ブロックとマッチングするステップ（７０８）と、
前記一対の連続した画像のマッチングされたブロックに関連した動きベクトルを求めるステップ（７１０）と
によって前記動きベクトルを求めるステップと、
前記動きベクトルに基づいて前記カメラの動きのアフィンモデルを推定するステップ（７１２）であって、該推定されたアフィンモデルは、一組のカメラ動きパラメータを決定する、推定するステップ（７１２）と
を含むことを特徴とする、一対の連続した画像間のカメラ動きを推定する方法。
【請求項２】
各ブロックは８×８画素アレイであることを特徴とする、請求項１に記載の一対の連続した画像間のカメラ動きを推定する方法。
【請求項３】
動きベクトルは、探索範囲内における歪み値を最小にすることによって求められることを特徴とする、請求項１に記載の一対の連続した画像間のカメラ動きを推定する方法。
【請求項４】
前記動きベクトルを濾波するステップであって、それによって、外れ値を除去する、濾波するステップをさらに含むことを特徴とする、請求項１に記載の一対の連続した画像間のカメラ動きを推定する方法。
【請求項５】
前記一対の連続した画像をダウンサンプリングするステップをさらに含み、動きベクトルは、ダウンサンプリングされた画像から求められることを特徴とする、請求項１に記載の一対の連続した画像間のカメラ動きを推定する方法。
【請求項６】
前記アフィンモデルは、前記カメラの焦点距離及び３つの直交軸を中心とした回転角に基づいていることを特徴とする、請求項１に記載の一対の連続した画像間のカメラ動きを推定する方法。
【請求項７】
前記推定されたアフィンモデルを繰り返すステップであって、それによって、外れ値を除去する、繰り返すステップをさらに含むことを特徴とする、請求項１に記載の一対の連続した画像間のカメラ動きを推定する方法。
【請求項８】
ビデオ動き理解のための装置（６２０）であって、
光学フロー解析に輝度画像を使用して、数対の連続した画像の画素ブロックから動きベクトルを生成する光学フロー解析器（６２２）、及び、該動きベクトルに基づいてアフィンモデル推定値を生成するアフィンモデル推定器（６２４）を含むカメラ動き推定器（６２０）と、
前記アフィンモデル推定値に基づいてブロックの残差（６３２）を求め、該残差に基づいてブロックを選択し、選択されたブロックを濾波（６３４）する物体検出器（６３０）であって、物体のサイズ及び位置を特定する限界ボックスを生成する、物体検出器（６３０）と
を備えることを特徴とする、ビデオ動き理解のための装置。
【請求項９】
データ準備デバイスであって、
入力ビデオ信号を復号して画像シーケンスを生成する復号器と、
前記画像シーケンスを受け取って、より低い解像度の画像シーケンスを生成するダウンサンプラと、
前記ダウンサンプリングされた画像シーケンスから輝度情報を抽出するデバイスと
を備える、デバイス準備デバイスをさらに備えることを特徴とする、請求項８に記載のビデオ動き理解のための装置。
【請求項１０】
前記アフィンモデル推定値の組み合わせに基づいて少なくとも１つのセンテンスを生成するセマンティク意味パーサと、
前記限界ボックスに基づいて標的モデル及び標的候補確率密度関数を求め、追跡された移動物体の表示を生成する標的モデル／確率計算機及び係数マキシマイザを含む移動物体追跡器と
をさらに備えることを特徴とする、請求項８に記載のビデオ動き理解のための装置。
【発明の詳細な説明】
【背景技術】
【０００１】
［背景］
カメラ動き解析及び物体動き解析を含むビデオ動き解析は、ビデオコンテンツを理解する重要な部分であり、コンテンツ理解は、パーソナルコンピュータ（ＰＣ）、デジタルエンターテイメントシステム、カメラ、さらにはプリンタも含む多くのマルチメディアシステムにおいて、ビデオのブラウジング、検索、編集、印刷等において重要な役割を果たす。
【０００２】
現在、プリンタは、文書及び画像等の平面（２次元）のメディアコンテンツ（媒体内容）を表現することを得意とするが、ビデオ印刷は、まだ多くの労力を必要とする問題である。その理由は、３次元（３Ｄ）信号（すなわち、２つの空間次元及び１つの時間次元）として、ビデオは膨大な量の冗長性を有するはるかに多くの情報を含み、これを用紙等の静的な媒体によって容易に表現することができないからである。
【０００３】
ビデオ印刷の１つの方法は、ビデオクリップからキーフレームを選択して、選択されたフレームを印刷することである。あいにく、セマンティクな意味を最大にするようにキーフレームを選択することは、困難なコンピュータビジョン及び人工知能の問題であるので、キーフレーム抽出タスクを自動化することは簡単なことではない。妥当な個数のキーフレームのみを印刷することは通常容認できるので、解決法は制約を受ける。キーフレームは、色、テクスチャ、動き等の低レベルのコンテンツの特徴を解析することによって抽出することができる。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
動き解析及びコンテンツ理解の既存の手法は、すべてのタイプのビデオ（たとえば、ホームビデオ及び業務用ビデオ、短いビデオクリップ記録及び長いビデオ記録等）にとって十分に一般的ではないか、又は、ＰＣのような一般処理システム及びカメラのような組み込みシステムにとってあまりにも低速であるかのいずれかである。既存の手法は、通常、たとえば、（既知の顔のモデルを有する）人又は（所定の車のモデルを有する）車の動きの追跡といった特定のタスク用に設計されており、対応する簡略化が行われており、適用範囲が限られている。
【課題を解決するための手段】
【０００５】
［概要］
一態様では、本発明は、一対の連続した画像間のカメラ動きを推定する方法であって、一対の連続した画像から動きベクトルを求めること、及び動きベクトルに基づいてカメラの動きのアフィンモデルを推定することを含む、一対の連続した画像間のカメラ動きを推定する方法である。動きベクトルを求めることは、一対の連続した画像の一方を複数の画素ブロックにセグメント化すること、画像の少なくとも１つの特徴に対応するブロックを選択すること、選択された各ブロックに対応する輝度値を求めること、輝度値に基づいて、選択されたブロックを、一対の連続した画像の他方の画素ブロックとマッチングすること、及び一対の連続した画像のマッチングされたブロックに関連した動きベクトルを求めることを含む。推定されたアフィンモデルは、一組のカメラ動きパラメータを決定する。
【０００６】
本発明の別の態様では、カメラ動きパラメータをセマンティクな意味に変換する方法は、カメラによって捕捉された数対の連続した画像から動きベクトルを求めること、動きベクトルに基づいてアフィンモデルを推定することにより、各一組のカメラ動きパラメータを求めること、及びそれら数組のカメラ動きパラメータからセマンティクな意味を生成することを含む。セマンティクな意味は、数組のカメラ動きパラメータを複数の規模及び方向に量子化すること、及び、ほぼ同じ規模及び方向に量子化された連続した数組のカメラ動きパラメータを特定することにより、量子化された数組から少なくとも１つのセンテンスを生成することによって生成される。
【０００７】
本発明のさらに別の態様では、カメラによって捕捉された画像における物体を検出する方法は、数対の連続した画像から動きベクトルを求めること、動きベクトルに基づいてアフィンモデルを推定すること、動きベクトル及びアフィンモデル推定値から数対の連続した画像の各画素ブロックの残差を計算すること、及び残差に基づいて物体を検出することを含む。
【０００８】
本発明のさらに別の態様では、ビデオ動き理解のための装置は、光学フロー解析に輝度画像を使用して、数対の連続した画像の画素ブロックから動きベクトルを生成する光学フロー解析器、及び、動きベクトルに基づいてアフィンモデル推定値を生成するアフィンモデル推定器を含むカメラ動き推定器と、アフィンモデル推定値に基づいてブロックの残差を求め、残差に基づいて外れブロックを削減し、残りのブロックを濾波する物体検出器であって、物体のサイズ及び位置を特定する限界ボックスを生成する、物体検出器とを備える。
【０００９】
添付図面は、本明細書に援用されて、本明細書の一部を構成する。添付図面は、本発明の実施の形態を示し、この記述と共に、本発明を説明するものである。
【発明を実施するための最良の形態】
【００１０】
［詳細な説明］
本発明と一致した実施態様の以下の説明は、添付図面を参照する。異なる図面における同じ参照番号は、同じ要素又は類似の要素を特定する。以下の詳細な説明は、本発明を限定するものではない。その代わり、本発明の範囲は、添付の特許請求の範囲によって規定される。
【００１１】
カメラ動き解析及び移動物体解析のための統合システム、並びに、ショットを変更することなく、主として、ビデオ及びビデオセグメントにおけるカメラ動きパラメータからセマンティクスを抽出する方法を説明する。このようなビデオの典型例は、デジタルカメラによって撮影されたホームビデオ及び業務用ビデオ又はフィルムのセグメント、すなわちクリップである。抽出されたセマンティクスは、注釈、ブラウジング、編集、フレーム強調、キーフレーム抽出、パノラマ生成、印刷、検索、要約等の複数のビデオ／画像の理解及び管理のアプリケーションに直接使用することができる。また、移動物体のアプリオリな知識に依拠しない、その移動物体を検出する完全自動方法も説明する。その上、それらの方法をリアルタイムで実行できるように処理を高速化する手段も説明する。
【００１２】
本発明の一実施の形態によるリアルタイムビデオセマンティクス解析は、コンピュータビジョン及び統計的パターン認識の知識に基づいてビデオコンテンツを理解するための動き情報を使用する。一般に、或る種の解析は、グローバル／カメラ動き推定及び前景／物体動き解析の少なくとも２つの部分を含む。カメラ動き推定は、光学フロー解析と、カメラ動き推定と、カメラ動きの量子化、センテンス生成、及びパラグラフ生成を実施するセマンティクな意味の抽出とを伴う。カメラの動き推定によって、カメラ動きのアフィンモデル表現がセマンティク表現に変換される。物体動き解析は、物体の検出と、物体のアプリオリな知識なしに追跡することとを伴う。高速でローバストな実施のために、カメラ動き推定は、加速されたブロック選択及びブロックマッチングを含むことができ、物体の追跡は、空間情報強化カラーヒストグラム（spatial information enhanced color histogram）を使用することができる。
【００１３】
したがって、フレームの入力シーケンス、すなわち画像の入力シーケンスは、カメラ動き解析に基づいてチャンクに有効に分割され、これらのチャンクには、便利な方法でインデックスすることができる。たとえば、０．１秒から２．０秒までは、カメラが高速ズームイン動作をしており、２．０秒から５．０秒までは、カメラの焦点が固定されていた等である。次に、チャンク（複数可）の物体（複数可）が検出され、その物体の動きが追跡され、その結果、各ビデオフレームは、たとえば移動物体の位置及びサイズといったパラメータよってさらにインデックスされる。従来のシステム及び方法とは対照的に、本発明のシステム及び方法は、容易に入手可能なプロセッサでリアルタイムに動作することができる。
【００１４】
カメラ動き推定
カメラ（グローバル）動きは、ズーム、パニング、回転等のカメラ操作によって誘発される動きを指す。物理的なカメラ動きは、通常、２つの連続フレーム間の適度で且つ時間的に連続した変化である。その影響は、カメラ動きによって定義されたアフィン変換に続くフレーム全般にわたる規則正しい光学フロー変化として観測することができる。実際のビデオでは、この状況は、前景の動き及び他の信号雑音によって多少悪化する。カメラ動き推定によって、観測された雑音のある光学フローアクティビティに基づくカメラ動きのアフィンモデルが見出される。一般に、これは、光学フロー解析及びアフィンモデル推定を含む。
【００１５】
光学フロー解析
光学フロー解析は、フレーム間の動きベクトル、すなわち動き推定を求めることを伴う。動き推定の基本的な方法はブロックマッチングである。図１に示すように、ｋ番目のフレームにおける画素寸法（Ｗ，Ｈ）を有する位置（ｍ，ｎ）のブロックと、（ｋ−１）番目のフレームにおける動きベクトル（ｉ，ｊ）によってシフトされた当該ブロックとの間の強度差は、
【００１６】
【数１】
2008518331.tif 000003
【００１７】
によって表すことができる。ここで、Ｉは、通常、画素の輝度である。誤差メトリックＥ（ｉ，ｊ）は、２乗誤差ｅ（Ｉk，Ｉk-1）の合計又は絶対誤差ｅ（Ｉk，Ｉk-1）の合計とすることができる。絶対誤差の合計の方が計算コストは少ない。ブロックに関連した動きベクトルは、探索範囲（Ｍ，Ｎ）内において、以下の式
【００１８】
【数２】
2008518331.tif 000004
【００１９】
に従った最小歪みＶを与えるベクトルと考えられる。
【００２０】
便利な探索範囲はＭ＝Ｎ＝８であるが、他の探索範囲、たとえばＭ＝Ｎ＝１６も使用することができる。８×８画素ブロック又は８×８画素アレイに基づいて動きベクトルを求めることは、ＭＰＥＧ−２、ＭＰＥＧ−４、及びＷｉｎｄｏｗｓ（登録商標）Ｍｅｄｉａを含む多くの共通のビデオ符号化アルゴリズムの機能である。実際は、これらの符号化アルゴリズム又は他の符号化アルゴリズムによって生成された動きベクトルは、後述するカメラ動き推定及び物体動き解析の他の機能と共に使用することができる。それにもかかわらず、ＭＰＥＧ−２のような圧縮アルゴリズムにおいて動きベクトルを求めることは、カメラ動きを求めるというよりもむしろ、顕著な歪みなしに圧縮を最適化することを目的としていることが十分理解されよう。
【００２１】
一実施の形態では、数式２によって与えられる動きベクトルを見つけるために、探索範囲内の網羅的探索を行って、大域的最適化を提供することができる。このような探索は、あまりにも多くの計算を行うので、プロセッサによってはリアルタイムで行うことができない場合がある。したがって、別の実施の形態では、網羅的探索の代わりに、高速探索アルゴリズムを使用することができる。この高速探索アルゴリズムは、J.R. Jain他著の「Displacement Measurement and Its Application in Interframe Image Coding」（IEEE Trans. on Communications vol. COM-29, pp. 1799-1808 (Dec. 1981))に記載されている２次元（２Ｄ）対数探索法、J.Y. Tham他著の「A Novel Unrestricted Center-Biased Diamond Search Algorithm for Block Motion Estimation」（IEEE Trans. on Circuits and Systems for Video Technology vol. 8, pp. 369-377 (Aug. 1998)) に記載されているようなダイヤモンド探索法、それ以外の既知の探索法等である。多くの高速探索アルゴリズムは、探索範囲における歪みＶが、小さな極小値を有する単調な凸面であるとの仮定に基づいている。
【００２２】
別の実施の形態では、T. Koga他著の「Motion-Compensated Interframe Coding for Video Conferencing」（Proc. Nat'l Telecommunications Conf. pp. G5.3.1-G5.3.5, New Orleans, LA (Dec. 1981))に記載されているような高速３ステップ探索アルゴリズムを使用することができる。この高速３ステップ探索アルゴリズムは、速度とセマンティクな正確さとをバランスさせることができる。３ステップ探索アルゴリズムを図２に示す。探索範囲を−８から＋８とする。第１ステップでは、９つの頂点（ステップ１用に数字１によって示す）を有する１６×１６画素ィンドウが、一対の連続フレームの一方において探索される。図２に示すように、この一対の連続フレームの他方の原点に第１のウィンドウの中心を置く。数式２による９つの歪み値が、９つの頂点において計算される。この例では、９つの頂点の右上の頂点が、第１のステップで計算された９つの歪み値の最小値を与える。第２のステップでは、最小のコスト関数を与えるものとして第１のステップにより特定された頂点に中心がある５×５ウィンドウがチェックされる。したがって、さらに別の９つの歪み値が、５×５ウィンドウの９つの頂点（数字２によって示す）において計算される。この例では、９つの頂点の右下の頂点が、第２のステップで計算された９つの歪み値の最小値を与える。第３のステップでは、最小のコストを与えるものとして第２のステップにより特定された点に中心がある３×３ウィンドウがチェックされる。したがって、さらに別の９つの歪み値が、３×３ウィンドウの９つの頂点（数字３によって示す）において計算される。３×３ウィンドウに関連した９つの歪み値の最小値（この例では、右下の点）が、最終的な動きベクトルを与える。
【００２３】
数式２の最小歪みに基づいて動きベクトルを求めることは、ビデオ符号化ではうまく機能する。しかしながら、この動きベクトルを求める技法は、ランダムな雑音によって誤った結果を提供する場合がある。このランダムな雑音は、探索範囲全体にわたる歪み分布に非常に小さな変化を与える。このような小さな変化は、フレームの均一な部分のブロック、たとえば雲のない空のブロックについて発生し得る。したがって、本発明の一実施の形態では、動きベクトルは、画像全体にわたる複数のブロックの動きベクトルを求め、次いで、外れ値を除去することによって「濾波」される。この適用において、外れ値は、フレームの残りのブロック又はフレームの一組の複数のブロックの動きベクトルのコンセンサスとはかなり異なる動きベクトルを有するブロックである。このコンセンサスは、以下でより詳細に説明するアフィンモデル推定から好都合に求められ、アフィンモデルを使用した予測動きベクトルと実際の動きベクトルとの間の誤差間の分散に基づいて得られる。外れブロックは、しきい値よりも大きな動きベクトル予測誤差を有するブロックである。このしきい値は、或る標準偏差等の値に設定することができる。
【００２４】
一般に、外れ値は、物体の動きによる外れ値及びブロックのミスマッチングによる外れ値の２つのカテゴリーに分類される。物体の動きによる外れ値は、物体の検出にとって有用な情報を有する。たとえば、前景に河岸線、河上にボート、及び背景に他方の河岸線を含むシーンにおいて、そのボート（すなわち、物体）は、カメラ動きとは異なるそれ自身の動きを有する。外れ値が物体のミスマッチングしたブロックによる別の例である、前景に帽子を被った男性及び背景に斜めのサイディングを有する建物を含むシーンでは、その建物の壁に位置するブロックは、単純な領域テクスチャ（region texture）を有し、その結果、それらの壁は、探索範囲において小さな歪み分布分散を与える。この歪み分布分散によって、より雑音の影響を受けやすい動きベクトルが与えられる。外れ値の他の理由には、突然の輝度の変化、カメラ動きの規模と比較して探索範囲が限られていること、及び、高速探索手法による極小値が含まれる。
【００２５】
外れ値は、アフィンモデル推定に影響を与える可能性があり、したがって、上述したような濾波によって外れブロック及び外れ動きベクトルの個数を削減することが好都合である。外れ値の個数を削減する別の方法は、画像から任意にセグメント化することができるすべてのブロックを単に使用するのではなく、マッチング計算用のブロックを選択することによるものである。マッチング用のブロックを選択する一方法は、特徴選択であり、この特徴選択は、外れ値の個数及びブロックマッチング計算（動きベクトルを求めること）の量を効率的に削減することができる。ブロックマッチングに使用する必要があるブロックは、画像において選択された１つ又は複数の特徴に関連したブロック又はそれら特徴に対応するブロックだけである。これは、もちろん、リアルタイムアプリケーションに好都合となる可能性がある。
【００２６】
画像又はビデオフレームは、空、ボート、建物、人等の一組の物体を含むことが理解されよう。物体は、静止している場合もあるし、動いている場合もあり、色、テクスチャ、形状等が異なる場合がある。信号又は画像若しくはビデオフレームの特徴は、通常、信号／画像／フレームから計算されるものであり、データの特性の或る態様を表す。たとえば、カラーヒストグラム及びカラーレイアウトは、画像の色から導出されるので、画像又はビデオフレームの２つの種類のカラー特徴である。動き推定のためにフレームのすべてのブロックを使用する代わりに、特徴ベースの選択手法を採用することができる。すなわち、画像の１つ又は２つ以上の特徴に基づいてブロックを選択することができる。これらの特徴は、カラー特徴、テクスチャ特徴、エッジ特徴等とすることができる。
【００２７】
特徴選択は、一般に、画素ベース又はブロックベースのいずれかとすることができる。前者は、画素に関する推定に基づいて特徴を選択するものである。この画素に関する推定は、ＫＬＴ変換又はモラベック作用素（Moravec operator）のいずれかを伴う場合がある。ブロックベースの特徴選択は、ブロック全体の特性に基づいて特徴を選択するものであり、テンポラルテクスチャ解析又は離散コサイン変換（ＤＣＴ）エネルギー統計値を伴う場合がある。
【００２８】
ブロックベースの特徴選択方法の一タイプは、エッジ検出を使用して、画像のブロックを選択する。ゾーベル（Sobel）アルゴリズム、ラプラスアルゴリズム、キャニー（Canny）アルゴリズム等の多くのエッジ検出方法が存在する。これらの方法は、異なる複雑さ及びエッジ品質を有する。一般に、エッジ検出は、入力画像のエッジマップを計算することによって実行される。入力画像のエッジマップは画像の１つの特徴である。エッジマップは、ブロックを選択するための特徴として使用される。すなわち、十分なエッジを含むブロックのみが選択される。
【００２９】
エッジベースの特徴選択方法の特定の例は、以下の２つの３×３の１Ｄゾーベル方向性作用素（Sobel directional operator）を使用する。
【００３０】
【数３】
2008518331.tif 000005
【００３１】
これらの作用素は、画素ブロックの輝度値に適用され、その結果の絶対値の合計を使用して、エッジ情報を抽出することができる。一実施の形態では、一定の個数のエッジ画素を明らかにしているブロックのみが、動き補償中に選択される。
【００３２】
選択されたブロックの判定しきい値は、好都合なことに、画像の勾配の規模の統計分布に従って動的に調整することができる。キャニー（Canny）エッジ検出は、たとえば、検出されるエッジの最終結果に影響を与える可能性のある２つのしきい値（１つは高く、１つは低い）を伴う。これらのしきい値は、勾配の規模の統計データを使用して決定することができる。
【００３３】
外れ値を特定して削除することに加えて、追加手段を採用して、計算コストをさらに削減し、且つ、速度を増加させ、能力の低いプロセッサによるリアルタイム実行を可能にすることが好都合となる可能性がある。これらの追加手段には、画像解像度ダウンサンプリング、ブロック選択ダウンサンプリング、及び中途終了が含まれ、外れ値を削除することが効率的に濾波することであるのと同様に、これらの追加手段も、濾波と考えることができる。
【００３４】
画像解像度ダウンサンプリングでは、動きベクトルを求めるプロセスは、解像度を低くした画像に対して実行される。たとえば、入力ビデオを３２０×２４０画素／フレーム（１／４ＶＧＡ）にダウンサンプリングすることもできるし、１６０×１２０画素／フレームにさえもダウンサンプリングすることもできる。１／４ＶＧＡへのダウンサンプリング又はさらに低い解像度へのダウンサンプリングは、計算コストを大幅に削減すると同時にセマンティクな意味の抽出及び移動物体の検出の点で満足な結果を達成することができる。
【００３５】
ブロック選択ダウンサンプリングでは、ブロックが選択されて処理されるが、その後、隣接したブロックは類似の動きの振る舞いを有するとの仮定の下で、選択されたブロックのすぐ隣のブロックのすべては処理されない。
【００３６】
中途終了は、ブロックの補償残差を計算することを伴う。ブロックの画素差を合計することによって生成されたブロックの累積歪みＶが、すでに処理されたブロックの現在観測されている最小歪みよりも大きい場合、計算は終了され、そのブロックは省略される。これも、不要な計算を回避することによってコストを削減する。
【００３７】
アフィンモデル推定
カメラ動きＣは、４つのパラメータの関数としてモデル化することができる。これら４つのパラメータは、カメラの焦点距離Ｆ、及び、空間座標直交軸Ｘ、Ｙ、Ｚのそれぞれを中心とする回転角α、β、γである。このカメラ動きは、Ｃ＝Ｃ（Ｆ，α，β，γ）によって表すことができ、図３によって示されている。空間の任意の点Ｐ（ｘ，ｙ，ｚ）は、以下のベクトル変換に従って、カメラのビュー平面の点Ｑ（ｕ，ｖ）に投影することができる。
【００３８】
【数４】
2008518331.tif 000006
【００３９】
ここで、ｚｏｏｍ（ズーム）、ｒｏｔａｔｉｏｎ（回転）、ｐａｎX（パン）、及びｐａｎY（パン）は、カメラ動きＣによって決定される４つパラメータである。これらのパラメータ間の関係は、J. Park他著の「Estimation of Camera Parameters from Image Sequence for Model-Based Video Coding」（IEEE Trans. on Circuits and Systems for Video Technology vol. 4, pp. 288-295 (June 1994))に記載されている。非立体的なビデオ信号の場合、奥行きマッピング情報は存在しないので、ｚ＝１である。
【００４０】
数式３は、列ベクトル（ｘ，ｙ，ｚ）のアフィン変換として認識されよう。一般に、アフィン変換は、平行移動がその後に続く線形変換であり、たとえば、Ａ（ｘ）＝Ｍｘ＋ｖである。ここで、Ａ（ｘ）はベクトルｘの変換であり、Ｍは行列であり、ｖはベクトルである。行列Ｍに６つのパラメータを有する一般のアフィンモデルと比較して、４つのパラメータを有する数式３のモデルは、より高速に処理することができるので、広範囲のビデオのリアルタイムのセマンティクな意味解析により良く適合することができる。もちろん、４つのパラメータへの簡略化は必須ではないことが十分理解されよう。
【００４１】
アフィンモデルは、以下の行列の式に従って最小２乗誤差（ＬＳＥ）回帰を使用することにより推定される。
【００４２】
【数５】
2008518331.tif 000007
【００４３】
ここで、Ｎはサンプル数、すなわち、選択された特徴ブロックの個数である。各サンプルは、動きベクトルによって関連付けられた現フレーム及び先行フレームの座標値である観測結果（ｘi，ｙi，１）及び出力（ｕi，ｖi）を含む。特異値分解を使用してＡを解くことができる。ＬＳＥ回帰によるアフィンモデル推定の態様は、S. Boyd及びL. Vandenberghe著のConvex Optimization, Section 1.2, Cambridge University Press(2004)に記載されている。
【００４４】
アフィンモデルを繰り返すことによって、すなわち、先行する計算（複数可）の結果を使用して数式４を計算することによって、残差がしきい値よりも大きいブロックを外れ値として排除することができる。これも、エッジベースの特徴検出がこのような濾波であるのと同様に、動きベクトルの濾波と考えることができる。しきい値は、あらかじめ定めておくことができ、誤差の標準偏差の関数に基づくことができる。残差Ｒは、
【００４５】
【数６】
2008518331.tif 000008
【００４６】
によって与えることができる。ここで、Ｐk、
【００４７】
【数７】
2008518331.tif 000009
【００４８】
は、動きベクトル（ｖx，ｖy）によって関連付けられたブロックである。しきい値が固定されていても、新たな外れ値が、各繰り返しで特定されて排除される場合がある。モデルの繰り返しは、所与の回数の繰り返しの後、又は、アフィンパラメータの組が所望の程度まで安定した時に終了される。起こり得る発散を回避するために、繰り返しの最大数を定義することができる。一実施の形態では、モデルの３回又は４回の繰り返しが実行された後に、ほとんどのフレームのアフィンモデル推定が適しているものとすることができる。
【００４９】
図４は、上述したような２つの画像間のカメラ動きを推定する方法のフローチャートである。ステップ７０２において、画像の１つが、１つ又は２つ以上のブロックにセグメント化され、ステップ７０４において、これらのブロックの１つ又は２つ以上が選択されて、さらに処理される。この選択は、好ましくは、画像の１つ又は複数の物体の１つ又は２つ以上のエッジに対応するブロックを見つけることによって実行される。選択されたブロック（複数可）に対応する輝度値が求められ（ステップ７０６）、次に、選択されたブロックが、２つの画像の他方の画像の対応するブロックとマッチングされる（ステップ７０８）。動きベクトルが、次に、マッチングされたブロックについて求められ（ステップ７１０）、一組のカメラ動きパラメータが、画像間のカメラの動きの推定されたアフィンモデルから求められる（ステップ７１２）。
【００５０】
セマンティクな意味の抽出
アフィンモデル推定によって、各フレームについて一組の動きパラメータが求められる。各組は、特定のフレームが捕捉された瞬間におけるカメラの動きを表している。カメラの対象となる自由な状態に従って、カメラのアフィンモデルを定義する異なる方法が存在することが理解されよう。デジタルカムコーダ又は監視ビデオ等、場合によっては、カメラ動きパラメータを記録して既知とすることができ、したがって、カメラモデルを推定する必要がない。いずれにしても、これらの組は、高レベルのセマンティクな意味を取り出すために要約される。
【００５１】
図５は、数フレームのシーケンスのアフィンモデルパラメータｚｏｏｍ、ｒｏｔａｔｉｏｎ、ｐａｎX、及びｐａｎYを示している。本発明の一実施の形態によれば、セマンティクな意味は、モデルパラメータから抽象化される。たとえば、図５に示すフレームの場合、このカメラ動きは、より適切には、たとえばシーン又は物体への集中といった「合焦（Focus）」と呼ぶことができる。セマンティクな意味の抽象化のための３つの技法は、以下でより詳細に説明する、カメラ動き量子化、「センテンス」生成、及び「パラグラフ」生成である。所望の抽象レベルに応じて、センテンス生成及びパラグラフ生成の一方又は双方を使用することができる。
【００５２】
カメラ動き量子化では、カメラの動き、すなわち、アフィンモデルパラメータが、最初に、いくつかの規模レベル及び方向に量子化される。図６Ａは、カメラのｐａｎパラメータを量子化するための一例示の図式を示している。ｚｏｏｍ及びｒｏｔａｔｉｏｎ等の他のパラメータも同様に量子化することができる。この図式では、Ｘ軸及びＹ軸等の直交軸に沿ったｐａｎの規模が、合焦、低速、中速、及び高速の４つの領域に分類される。動き方向は、図６Ｂに示すように量子化される。カメラの振動及び雑音の干渉に対してローバストであるために、好ましくは、図６Ｃに示すように、ヒステリシスしきい値処理を使用して、遷移が決定される。図６Ａ、図６Ｂ、図６Ｃに示す量子化の代わりに、他の量子化も使用できることが十分理解されよう。
【００５３】
「センテンス」生成では、たとえば数秒といった小さな時間間隔にわたる画像シーケンスが、それら画像のアフィンモデルの類似度に基づいて互いに自然にクラスタリングされて、妥当な個数のセマンティク領域が生成される。換言すれば、量子化された同じカメラ動きパラメータを共有する隣接したフレームは、より長い１つの時間間隔に融合される。このより長い１つの時間間隔は、この出願では「センテンス」と呼ばれる。この融合ステップは、１つのビデオクリップをいくつかのセンテンスに要約する。これらのセンテンス内では、カメラ動きは一致している。すなわち、アフィンモデルパラメータは、同じレベル又は類似のレベルに量子化されている。同時に、平均アフィンモデルが、各センテンスについて計算される。
【００５４】
「パラグラフ」生成は、センテンス生成をさらに拡大するものであり、したがって、パラグラフは、たとえば数十秒といったより長い画像シーケンスの抽象化である。以下でより詳細に説明するように、隣接した（連続した）センテンスの継続期間のヒストグラムが推定される。さらなる融合ステップが実行されて、ビデオが、感度しきい値によって決定された複数のセマンティクパラグラフに要約される。複数のセンテンスは、それらの類似度に基づいて１つ又は２つ以上のパラグラフに融合される。この類似度は、アフィンモデルパラメータ間の距離メトリックに従って測定することができる。適した距離メトリックは、パラメータ間のユークリッド距離である。各パラグラフのセマンティクな意味は、重み付けアフィンモデルを使用して再評価される。
【００５５】
アフィンモデル推定、パラメータ量子化、センテンス生成、及びパラグラフ生成のプロセスを図７に示す。図７は、ビデオの時間軸上の目盛りによって、ビデオクリップのフレームの連続を示している。クリップにはＮf個のフレームが存在するものとし、各フレームｉ（ここで、ｉ＝１，２，…，Ｎf-1，Ｎfである）は、継続期間ｔfi、推定されたアフィンモデルＡfi、及び量子化されたカメラ動きＳfiを有するものとする。センテンス生成によって、ＮS個のセンテンスが生成され、図７では、各センテンスｊは、量子化された各カメラ動きＳSj、アフィンモデルＡSj、及び継続期間ｔSjによって特定される。ここで、
【００５６】
【数８】
2008518331.tif 000010
【００５７】
である。
【００５８】
センテンスが生成された後、継続期間ｔSjのヒストグラムが生成され、継続期間ｔSjの分布が評価される。継続期間許容しきい値Ｔdが使用されて、センテンスがＮP個のパラグラフに融合される。Ｔdよりも大きな継続期間を有するセンテンスは、アンカーセンテンスＳAとして機能し、それ以外のセンテンスは、アフィンモデル間の距離測定値（ここで、距離はユークリッド距離とすることができる）に基づいてこれらのアンカに融合される。
【００５９】
各パラグラフｋのカメラ動きのセマンティクな意味は、
【００６０】
【数９】
2008518331.tif 000011
【００６１】
から評価される。ここで、Ｑ（Ａ）は、アフィンモデルパラメータからセマンティクなカメラ動きへの量子化マッピングであり、Ｄは選択された距離である。このプロセスにおいて、しきい値Ｔdは、セマンティクなカメラ動きの変化を検出する感度を設定する。
【００６２】
図８は、上述したようにカメラ動きパラメータをセマンティクな意味に変換する方法のフローチャートである。ステップ１０２において、動きベクトルが求められるか又は提供され、次に、ステップ１０４において、カメラ動きパラメータが、動きベクトルから求められる。これらの組の動きパラメータは量子化され（ステップ１０６）、同様に量子化された組が、センテンスとして特定され、オプションとして、パラグラフとして特定される（ステップ１０８）。
【００６３】
物体の検出及び追跡
この出願では、ビデオシーケンスにおける移動物体は、一般に、対象となる動きの程度及びセマンティクな意味を有する領域として定義される。移動物体の動きは、ビデオシーケンスの一連のフレームのそれぞれにおいて、その移動物体のロケーション及びサイズを見つけることによって好都合に追跡される。顔の追跡への限定又は所定のモデル（たとえば、車等の対象物体の３次元モデル）等、或る簡略化を伴うことが多い移動物体の検出及び追跡の従来の手法とは異なり、本発明による移動物体の検出は、動き情報にのみ基づいており、アプリオリな知識は必要とされない。
【００６４】
物体の検出
本発明によれば、移動物体の検出は、前景の動き振る舞いが背景の動き振る舞いと異なるという仮定、及び、動き補償残差が
Ｒk（ｍ，ｎ）＝‖Ｂk（ｍ，ｎ）−Ａ・Ｂk-1（ｍ＋ｖx，ｎ＋ｖy）‖（数式８）
に従って推定される場合に、移動物体の領域（すなわち、前景又は背景）が外れ値として明らかにされるという仮定に基づいている。ここで、Ｒk（ｍ，ｎ）は、ｋ番目のフレームのロケーション（ｍ，ｎ）から開始するブロックの残差であり、Ｂk及びＢk-1は、動きベクトル（ｖx，ｖy）によって関連付けられたブロックであり、Ａはアフィンモデルである。残差Ｒkのリアルタイム推定には、その推定の計算コストを削減することが必要とされる場合があることに留意されたい。コストを削減する一方法は、アフィンモデル推定中に１つ又は複数の外れ値として特定された１つ又は複数の領域に対してのみ数式８の推定を実行することである。それ以外の領域は、繰り返し中にＬＳＥ基準をすでに満たしている、すなわち、動きパラメータがアフィンモデルによって定義された後のブロックについては、残差は小さくなるので、コストは削減される。
【００６５】
外れ値は、背景の動き推定の雑音に起因する可能性もあるので、移動物体の領域が外れ値として明らかにされるという仮定は、現実のビデオシーケンスに有効でない場合がある。したがって、動きベースの物体の検出の重要なタスクは、実際の物体を外れ値における背景雑音と区別することである。したがって、本発明によれば、対象となる物体が適度なサイズを有し、且つ、画像の中央に位置する傾向があると仮定することによって、実際の物体は背景雑音と区別される。適度なサイズの仮定の結果、十分な残差が明らかにされ、かなりのセマンティクな意味が提供される。中央にバイアスをかける仮定は、物体のロケーションが中央から離れるにつれて物体への人々の興味が徐々に弱まるという理解を反映している。これらの仮定は、一般に入手可能なプロセッサでリアルタイム動作を容易にする限りにおいては望ましいが、必須ではないことが十分理解されよう。これらの仮定に基づいて、以下でより詳細に説明するような一組の重みパラメータを適用することにより、残差は濾波される。
【００６６】
図９は、入力ビデオシーケンスにおける物体を検出するための装置２００のブロック図である。この装置は、とりわけ、説明した動作を実行するように構成されたロジックとして実施することもできるし、１つ又は２つ以上のプログラマブルプロセッサとして実施することもできるし、これらの組み合わせとして実施することもできることが理解されよう。
【００６７】
装置２００はデバイス２０２を含む。このデバイス２０２は、カメラ動きを推定して、入力シーケンスにおける数対の連続した画像から上述したような動きベクトル及びアフィンモデル推定値を生成する。モデルパラメータは、数式８に従って残差Ｒkを求めるデバイス２０４に提供される。残差、すなわち、誤差画像は、フィルタ２０６に提供される。フィルタ２０６は、濾波された残差における検出された物体の表示を生成する。フィルタ２０６は、空間位置フィルタ２０６１、動き規模フィルタ２０６３、ブロック領域サイズ／規模フィルタ２０６５、及び時間フレームフィルタ２０６７の１つ又は２つ以上を好都合に含む。これらのフィルタは、以下でより詳細に説明する。
【００６８】
空間位置フィルタ２０６１は、フレームの中央領域の近くに位置するブロックに、より高い重みを割り当てる。一例示のフィルタ関数は、
【００６９】
【数１０】
2008518331.tif 000012
【００７０】
等の指数関数である。ここで、ｆs（Ｐ）はフィルタの出力であり、Ｐは濾波されているブロックであり、‖Ｐ‖はブロックＰと画像の中央との間の距離であり、Ｍは重みがゼロである場合の所定の値であり、ε及びλは、フィルタ関数を正規化してフィルタ関数を一般の確率関数により似たものとするのに使用されるパラメータである。
【００７１】
動き規模フィルタ２０６３は、カメラの動きの規模が大きいほど、外れ値が背景雑音によってより大きな影響を受ける傾向にあることから有用である。たとえば、パニングの規模を考える。一例示の動き規模フィルタ関数は、
【００７２】
【数１１】
2008518331.tif 000013
【００７３】
等のガウスベースのものである。ここで、ｆm（‖ＰM‖）はフィルタの出力であり、Ｐは濾波されているブロックであり、‖ＰM‖はパニングの規模であり、偏差σは、探索範囲の境界上になるように設定される。
【００７４】
これらの空間位置フィルタと動き規模フィルタとの間の相違は、フレーム境界上におけるそれらフィルタの振る舞いにある。空間位置フィルタは、フレーム境界上においてゼロの重みを割り当て、動き規模フィルタは、探索境界上において非ゼロの重みを与える。これらの２つのフィルタは、重みを計算する計算コストを削減するために参照表によって実施することができる。
【００７５】
空間位置濾波及び動き規模濾波の後、調整された残差
【００７６】
【数１２】
2008518331.tif 000014
【００７７】
が、
【００７８】
【数１３】
2008518331.tif 000015
【００７９】
によって与えられる。続く２つのフィルタは、この調整された残差を使用する。
【００８０】
ブロック領域サイズ／規模フィルタ２０６５を実施するために、外れブロックが、最初に、それらブロックの接続性に基づいて領域にクラスタリングされる。これは、図１０Ａによって示すような高速フラッディングアルゴリズムで行うことができる。図１０Ａでは、星印でマーキングされたブロックが接続性探索の開始元である場合、そのすぐ隣のブロックのすべてが所定の順序でチェックされる。この所定の順序は、この図では０〜７の番号によって示されている。チェックされた各ブロックは、それに対応して適切にマーキングされ、後の探索で再びチェックされないようにされる。隣のブロックの中で外れブロックが検出された場合、その外れブロックにフラグが付けられ（この図では、ブロック４のダイヤのマークが外れ値を示す）、開始元は、フラグが付けられたブロックに移動され、探索は、すぐ隣のブロックにおいて同じ所定の探索順序で継続する。事前にチェックされたすべてのブロックは省略され、その結果、この例では、２〜６の番号が付けられたブロックがチェックされることに留意されたい。
【００８１】
フィルタ２０６５は、この手順を再帰的に繰り返す。これは、外れブロックのすべてを互いに接続するための効率的な方法である。この手順は、P. O. Duda、P. E. Hart、及びD. G. Stork著のPattern Classification, Wiley, New York (2001)に記載されている、サンプルの距離に基づく自然クラスタリングアルゴリズム（natural clustering algorithm）の簡略化された離散バージョンと考えることができる。
【００８２】
外れブロックのすべてが特定の領域に一旦クラスタリングされると、各領域は、限界ボックス（図１０Ｂに示す）及び代表的な残差の規模によって効率的に表される。この代表的な残差の規模は、その領域のすべてのブロックの中で最大の残差として定義することができる。限界ボックスは、検出された物体を示す。一実施の形態では、第１のしきい値よりも小さなサイズ又は第２のしきい値よりも小さな規模を有するどの領域も濾波除去される。第３のしきい値よりも大きなサイズを有する領域が少なくとも１つ存在する場合、このフレームのアフィンモデルは信頼できないものと仮定することができるので、そのフレームは移動物体の検出については省略される。
【００８３】
すべてのフレームが移動物体を検出するのに適しているとは限らないので、時間フレームフィルタ２０６７が有用な場合がある。たとえば、移動物体のブロックの残差は、背景雑音によって圧倒される場合があり、物体の検出を困難にする。背景雑音からの残差は、複数ある理由の中でもとりわけ、複雑なテクスチャ及び高速なカメラ動きによって大きくなる場合がある。このために、まず第１に、互いに接続されたブロックのすべて又はほぼすべてが、大きな領域に結合される。時間フレームフィルタ２０６７は、物体を検出する候補として１つの支配的なブロック領域を有するフレームを選択するように動作する。したがって、支配的な残差及び適度なサイズのブロック領域を有するフレームのみが維持される。このようなフレームは、検出された物体を含む。それ以外のフレームは、それ以降の処理から省略することができる。
【００８４】
図１１は、上述したような本発明による物体の検出方法のフローチャートである。ステップ４０２において、動きベクトルが、数対の連続した画像から求められ、これらの動きベクトルは、ステップ４０４においてアフィンモデルを推定するのに使用される。ステップ４０６において、残差が、動きベクトル及びアフィンモデルに基づき、数対の画像の各画素ブロックについて計算される。ステップ４０８において、物体が残差に基づいて検出される。
【００８５】
物体の追跡
移動物体が一旦検出されると、その位置及びサイズ（図１０Ｂに示したのと同様の画素の限界ボックスによって表される）は、以下でより詳細に説明する移動物体追跡器に転送することができる。本発明の移動物体追跡プロセスによれば、考慮する必要があるのは、移動物体のより正確な輪郭の代わりに限界ボックスのみである。限界ボックスは、十分なセマンティクな意味を提供し、物体の正確な輪郭の算出には、広く入手可能な現在のプロセッサによってリアルタイムで容易に行うことができないより複雑な計算が必要とされる。
【００８６】
たとえば、移動物体は、ビデオクリップの開始フレームで検出される場合があり、その後、その物体は、ビデオクリップの後続のフレームを通して追跡される場合がある。別の例として、移動物体は、定期的に（たとえば、１００フレームごとに１回又は２秒ごとに１回等）検出される場合があり、その後、その移動物体の標的モデルは、更新される場合もあるし、現在の標的に取って代わる、より目立った移動物体が見つけられる場合もある。さらに別の例として、たとえば、現在の移動物体がフレームの外部に移動した時といった一定の基準が満たされた時に、移動物体が検出される場合がある。
【００８７】
検出された移動物体は、その量子化されたカラーヒストグラムによって好都合に表すことができる。この量子化されたカラーヒストグラムは、ＮR×ＮG×ＮBビンを有するＲ−Ｇ−Ｂ（赤−緑−青）空間等の便利な色空間において形成することができる。ここで、ＮR、ＮG、ＮBは、それぞれＲ、Ｇ、Ｂの色チャネルのビンの個数である。Ｒ−Ｇ−Ｂ空間の代わりに、ＹＵＶ空間及びマゼンタ−イエロー−シアン空間等の他の色空間も使用できることが十分理解されよう。カラーヒストグラムの利点は、物体が、回転、拡大縮小、さらには堅くない曲げ等の複雑な動きを受けている時のそのローバスト性である。
【００８８】
本発明の別の実施の形態では、空間的に強化されたカラーヒストグラムを使用して、検出された移動物体を表すことができる。限界ボックス５００は、図１２によって示されるように、周縁部５０２及び中央部５０４に分割される。この図では、中央部５０４の（画素での）高さ及び幅は、周辺部５０２の高さＨ及び幅Ｗの２分の１である。各部は、それ自身のヒストグラム統計値を有し、全体のヒストグラムは、これら２つの局部的なヒストグラムを連結したものである。空間情報を有するカラーヒストグラムを区画する他の方法も使用できることが理解されよう。
【００８９】
カラーヒストグラムは、好ましくは、以下のような確率の形状に正規化される。
【００９０】
【数１４】
2008518331.tif 000016
【００９１】
ここで、σはクロネッカデルタ関数であり、ｕはヒストグラムインデックスであり、ｑはヒストグラム確率であり、ｂ（ｘi）は移動物体領域に位置する画素ｘiをヒストグラムビンの１つのエントランスにマッピングする関数であり、Ｎは物体領域の画素数である。ここで、「エントランス」とは、ビンのインデックスを意味する。たとえば、１００個のヒストグラムビンが存在する場合、１〜１００の番号が、特定のカラービンの位置を突き止めるエントランス（インデックス）である。
【００９２】
一実施の形態では、カラーヒストグラムを直接使用する代わりに、カーネル関数が適用され、中心から遠く離れた画素ほど、より小さな重みが割り当てられる。このようなカーネルベースの追跡（ＫＢＴ）は、D. Comaniciu、V. Ramesh、P. Meer著の「Real-Time Tracking of Non-Rigid Objects Using Mean Shift」（IEEE Conf. Computer Vision and Pattern Recognition (CVPR '00), Vol. 2, pp. 142-149, Hilton Head Island, SC (2000))、及び、D. Comaniciu、V. Ramesh、P. Meer著の「Kernel-Based Object Tracking」（IEEE Trans. Pattern Analysis Machine Intell., Vol. 25, No. 5 (2003))に記載されている。カーネル選択の原理は、凸状で且つ単調減少するカーネルプロファイルを有するカーネルを選択することである。上記で引用したComaniciu他による論文に記載されたイパネクニコフ（Epanechnikov）カーネル関数が、かなりの計算の簡略化を与えることができる。
【００９３】
カーネル関数では、標的モデル及び標的候補の双方が、重み付けられたカラーヒストグラム確率密度関数（ＰＤＦ）として表される。次に、標的モデルから最小距離を有する標的候補が見つけられる。詳細には、標的モデル及び標的候補が与えられると、この類似度メトリックは、一実施の形態では、バタチャリア（Bhattacharyya）係数であり、この係数は、直接的な幾何学的解釈を有する発散タイプの尺度である。この係数は、ｍ次元単位ベクトル間の角度のコサインである。標的モデルと候補との間の距離は、バタチャリア係数に基づいており、距離を最小にする標的候補を見つける物体追跡タスクは、バタチャリア係数を最大にする候補を見つけることと等価である。
【００９４】
距離を最小にするために、上記で引用したComaniciuによる論文に記載された勾配ベースの平均値シフトの繰り返しを使用することができる。上述したダイヤモンド探索（ＤＳ）アルゴリズム及び３ステップ探索（ＴＳＳ）アルゴリズムを組み合わせたものを使用することができる。一般に、第１のステップでは、ＤＳアルゴリズム及びＴＳＳアルゴリズムの双方が適用され、（距離最小化の点で）成功したアルゴリズムが処理を続け、他方のアルゴリズムは終了する。第２のステップでは、この残っているアルゴリズムが、最小距離が見つかるまで、自身のルールを使用して探索を続ける。
【００９５】
移動物体の追跡時に、標的モデルは、物体検出段階で検出された物体、すなわちフィルタ２０６の出力、から得られる。この標的モデルは、オプションとして、物体追跡段階で追跡された物体で更新される。これは、定期的に行うこともできるし、標的モデルと選択された標的候補との間に大きな相違が存在すると判断されるごとに行うこともできる。また、モデルは、メモリの有無にかかわらず更新することができる。
【００９６】
例示のアーキテクチャ
リアルタイムビデオ動き理解のための全体的なシステムアーキテクチャの一例を図１３に示す。システム６００は、データ準備デバイス６１０、カメラ動き推定器６２０、移動物体検出器６３０、及び移動物体追跡器６４０を含む。図９と共に上述したように、システム６００は、とりわけ、適切に構成されたロジック及び／又は適切にプログラミングされたプロセッサによって実現することができる。
【００９７】
データ準備デバイス６１０は、入力ビデオ信号を必要に応じて復号して画像シーケンスを生成する復号器６１２を含むことができる。ダウンサンプラ６１４は、画像シーケンスを受け取って、低解像度の画像シーケンスを生成することができる。この低解像度の画像シーケンスは、適した遅延デバイス６５２を通って物体追跡器６４０に提供することができる。データ準備デバイスは、ダウンサンプリングされた画像シーケンスから輝度情報を抽出するデバイス６１６をさらに含むことができる。復号、ダウンサンプリング、及び輝度抽出は、上述した理由から常に必要であるとは限らない。
【００９８】
カメラ動き推定器６２０は、光学フロー解析器６２２を含むことができる。この光学フロー解析器６２２は、データ準備デバイス６１０又は別のデータ源のいずれかからの輝度画像を使用して、光学フロー解析を行う。解析器６２２は、好ましくは、上述したような画像シーケンスからの現在の画像及びバッファリングされた前の画像に対して解析を実行できるように、適したメモリバッファを含む。その上、解析器６２２は、減算器６５４及び適した遅延デバイス６５６が数対の連続した画像から生成することができる差分画像に対して好都合に動作する。解析器６２２は、画像シーケンス又は差分画像シーケンスから動きベクトルを生成し、この動きベクトルは、アフィンモデル推定器６２４に提供される。アフィンモデルは、好ましくは、上述したようなＬＳＥを使用して動きベクトルに基づき推定される。推定されたアフィンモデルは、次に、必要に応じて、セマンティク意味パーサ６２６に提供することができる。セマンティク意味パーサ６２６は、上述したようなアフィンモデル推定値の組み合わせに基づいてセンテンスを生成し、オプションとしてパラグラフを生成する。
【００９９】
アフィンモデル推定値は、物体検出器６３０の残差計算機６３２に提供される。残差計算機６３２は、遅延デバイス６５６によって適切に遅延された画像を受け取る。物体を検出するかどうかは、スイッチ又は他の適した決定デバイス６５８によって制御することができる。外れ値の残差は、アフィンモデル推定値を使用して求めることができ、外れ値は、上述したように移動物体を検出するために選択される。選択された画素又はブロックは、上述したフィルタ１０６として動作して物体の領域を突き止めるフィルタ６３４によって処理される。この情報は、物体ロケータ６３６に渡される。物体ロケータ６３６は、物体の位置及びサイズを限界ボックス又は等価な情報として好都合に提供する。物体の位置及びサイズを特定する限界ボックス又は等価な情報は、物体追跡器６４０に提供される。
【０１００】
追跡器６４０は、標的モデル及び標的候補ＰＤＦを求める標的モデル／確率計算機６４２及び係数マキシマイザ６４４を含み、バタチャリア係数は、距離を最小にするために、上述したように最大化される。最後に、追跡された移動物体の表示が出力され、現在のフレームの処理が完了する。追跡された移動物体の表示の性質は、好都合に、物体境界領域のロケーション（たとえば、図１０Ｂにおけるような限界ボックスの場合には、左側、上部、右側、及び下部）とすることができる。
【０１０１】
システム６００は、１．０ＧＨｚプロセッサ及び２５６Ｍバイトのランダムアクセスメモリを有するラップトップコンピュータで実施された。システムの一例示の使用では、入力ビデオ信号は、毎秒３０フレームの１０秒の長さのビデオシーケンスであった。各フレームは、ＭＰＥＧ−１フォーマットに従って符号化された３５２×２４０画素を含んでいた。これらのビデオフレームは、４分の１のサイズ、すなわち１７６×１２０にダウンサンプリングされた。したがって、システム６００は、ＭＰＥＧ−１復号器６１２を含んでいた。このＭＰＥＧ−１復号器６１２は、１０秒の入力シーケンスを復号するのに２．０１６秒を使用した。この１０秒の入力シーケンスは、テニスの試合中の一方の選手の一ショットであった。すべてのカメラ動き推定値は、１．０８９秒で完了し、シーケンス全体の期間中の物体の検出及び追跡は、１．１５１秒で完了した。したがって、ビデオ動き解析の全時間、すなわちコスト（２．２４秒）は、この例の復号コスト（２．０１６秒）に匹敵し、復号、カメラ動き解析、及び物体動き解析（検出及び追跡）を含むすべての処理は、リアルタイム（１０秒）よりも速く終了した。上述したように、符号化されたビデオクリップの代わりに画像シーケンスを使用することによって、復号コストを節約することができ、この例のプロセス全体の速度を２倍にすることができる。さらに、画像シーケンスがＹ−Ｕ−Ｖフォーマットで提供される場合、色空間変換のコストも節約することができる。
【０１０２】
上述したラップトップコンピュータで実施されたシステム６００の別の例示の使用では、サンフランシスコの或る波止場の２６秒のビデオが、入力ビデオ信号として使用された。このビデオは、ＭＪＰＥＧフォーマットで符号化され、毎秒１５フレームを含んでいた。各フレームは、６４０×４８０画素を含んでいた。上述したように、入力フレームは、幅が２００画素以下となるまで２分の１ずつダウンサンプリングされ、この例では、使用された最終的な画像サイズは１６０×１２０であった。したがって、システム６００は、ＭＪＰＥＧ復号器６１２を含んでいた。ＭＪＰＥＧ復号器６１２は、２６秒の入力シーケンスを復号するのに９．２６３秒を必要とした。すべてのカメラ動き推定は、２．３７３秒で完了し、全シーケンスの期間中の物体の検出及び追跡は、１．３２３秒で完了した。したがって、ビデオ動き解析の全コスト（３．６９６秒）は、この例の復号コスト（９．２６３秒）よりもかなり小さく、復号、カメラ動き解析、及び物体動き解析（検出及び追跡）を含むすべての処理は、リアルタイム（２６秒）よりも速く終了した。
【０１０３】
これらの例から、システム６００の使用は、アクションビデオ、コマーシャルビデオ等を含む一般のタイプのビデオに実用的であることが分かる。画像サイズがより大きくなると、復号及びダウンサンプリングのコストが、全計算コストを支配する可能性があるが、この場合も、このコストは、輝度画像シーケンスが入力信号として提供される場合に節約することができる。
【０１０４】
本発明は、たとえば、ビデオ印刷のためにビデオシーケンスの特定のフレームを見つけるのに使用することができる。加えて、本発明は、自動ビデオ編集及び知的ビデオブラウジングにも適用でき、ビデオのコンテンツのより良い理解を可能にし、その結果、ビデオのハイライトのより正確な把握を可能にする。本発明の移動物体の検出及び追跡によれば、適切なサイズ及び位置の移動物体を有するビデオフレームを検出することができ、所望でないフレームを無視又は削除することができる。
【０１０５】
上述した手順は、必要に応じて繰り返し実行されることが十分理解されよう。理解を容易にするために、本発明の多くの態様が、たとえば、プログラマブルコンピュータシステムのエレメントが実行できる動作シーケンスの点から説明されている。さまざまな動作は、専用回路（たとえば、専用機能を実行するように相互接続されたディスクリート論理ゲート又は特定用途向け集積回路）が実行することもできるし、１つ又は２つ以上のプロセッサによって実行されるプログラム命令が実行することもできるし、双方の組み合わせが実行することもできることが認識されよう。
【０１０６】
その上、本発明は、コンピュータベースのシステム、プロセッサを含むシステム、又は媒体から命令をフェッチしてそれら命令を実行できる他のシステム等である、命令実行システム、命令実行装置、若しくは命令実行デバイスによって使用されるか、又は、それら命令実行システム等と共に使用される適切な一組の命令を記憶した任意の形態のコンピュータ可読記憶媒体内に具現化されるものとさらに考えることができる。本明細書で使用されるように、「コンピュータ可読媒体」は、命令実行システム、命令実行装置、若しくは命令実行デバイスにより使用されるプログラム又はそれら命令実行システム等と共に使用されるプログラムの収容、記憶、通信、伝搬、又はトランスポートを行うことができるあらゆる手段とすることができる。コンピュータ可読媒体は、たとえば、電子的な、磁気的な、光学式の、電磁気的な、赤外線の、又は半導体のシステム、装置、デバイス、又は伝搬媒体とすることができるが、これらに限定されるものではない。コンピュータ可読媒体のより具体的な例（網羅的な列挙ではない）には、１つ又は２つ以上のワイヤを有する電気接続、ポータブルコンピュータディスケット、ランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、消去可能プログラマブル読み出し専用メモリ（ＥＰＲＯＭ又はフラッシュメモリ）、及び光ファイバが含まれる。
【０１０７】
このように、本発明は、多くの異なる形態で具現化することができるが、これらのすべてが上述されているとは限らず、このようなすべての形態は、本発明の範囲内にあるように意図されている。本発明のさまざまな態様のそれぞれについて、このようなあらゆる形態は、説明した動作を実行する「ように構成されたロジック」と呼ぶこともできるし、或いは、説明した動作を実行「するロジック」と呼ぶこともできる。
【０１０８】
「備える」という用語は、この出願で使用される場合、明言した特徴、完全体、ステップ、又はコンポーネントが存在することを明示しており、１つ又は２つ以上の他の特徴、完全体、ステップ、コンポーネント、又はそれらの群が存在すること又は追加されることを排除するものではないことを強調しておく。
【０１０９】
本発明の例示の実施の形態の上記説明は、図解及び説明を提供するが、網羅的であることを目的とするものでもなければ、開示した正確な形態に本発明を限定することを目的とするものでもない。変更及び変形が、上記教示に鑑み可能であるか、又は、本発明の実施から獲得される場合もある。添付の特許請求の範囲及びその均等なものが、本発明の範囲を規定する。
【図面の簡単な説明】
【０１１０】
【図１】動き推定のブロックマッチングの一実施の形態を示す図である。
【図２】３ステップ探索アルゴリズムの一実施の形態を示す図である。
【図３】カメラ動きのモデルを示す図である。
【図４】本発明の一実施の形態によるカメラ動きを推定する方法のフローチャートである。
【図５】ビデオフレームシーケンスのアフィンモデルパラメータを示す図である。
【図６Ａ】ヒステリシスしきい値を有する規模レベル及び方向へのカメラ動き量子化を示す図である。
【図６Ｂ】ヒステリシスしきい値を有する規模レベル及び方向へのカメラ動き量子化を示す図である。
【図６Ｃ】ヒステリシスしきい値を有する規模レベル及び方向へのカメラ動き量子化を示す図である。
【図７】センテンス及びパラグラフの生成の一実施の形態を示す図である。
【図８】本発明の一実施の形態による、カメラ動きパラメータをセマンティクな意味に変換する方法のフローチャートである。
【図９】物体を検出するための装置の一実施の形態のブロック図である。
【図１０Ａ】高速フラッディングアルゴリズムの一実施の形態を示す図である。
【図１０Ｂ】限界ボックスを示す図である。
【図１１】本発明の一実施の形態による、物体の検出方法のフローチャートである。
【図１２】周縁部及び中央部に分割された物体領域を示す図である。
【図１３】本発明の一実施の形態による、ビデオ動き理解のための装置のブロック図である。
【図１】
2008518331.tif 000017
【図２】
2008518331.tif 000018
【図３】
2008518331.tif 000019
【図４】
2008518331.tif 000020
【図５】
2008518331.tif 000021
【図６Ａ】
2008518331.tif 000022
【図６Ｂ】
2008518331.tif 000023
【図６Ｃ】
2008518331.tif 000024
【図７】
2008518331.tif 000025
【図８】
2008518331.tif 000026
【図９】
2008518331.tif 000027
【図１０Ａ】
2008518331.tif 000028
【図１０Ｂ】
2008518331.tif 000029
【図１１】
2008518331.tif 000030
【図１２】
2008518331.tif 000031
【図１３】
2008518331.tif 000032
【国際調査報告】
2008518331.tif 000033
2008518331.tif 000034
2008518331.tif 000035