(57)【要約】【課題】【解決手段】  実施例において、粒子のセットが、動的システムの状態の位置を推定するために提供される（１０１０）。ローカルモード・シーキング・メカニズムが、粒子のセットの一つ以上の粒子を移動させるために使用される（１０２０）。そして、粒子のセットの粒子数が修正される（１０３０）。動的システムの状態の位置は、粒子のセットの粒子を使用して推定される（１０４０）。他の実施例は、粒子フィルタ（５６５）を使用して動的な状態推定を提供する。粒子位置が、平均値シフト分析に基づくローカルモード・シーキング・アルゴリズムを使用して修正される（６１０）。そして、粒子数がＫｕｌｌｂａｃｋ−Ｌｅｉｂｌｅｒ−ｄｉｓｔａｎｃｅサンプリング処理を使用して調整される（８３０−８６０）。平均値シフト分析は粒子の縮退を減少させることができる。そして、サンプリング処理は粒子フィルタの計算の複雑さを減少させることができる。実施例は、非線形および非ガウス性システムに適用可能である。
2010505184.tif 000002
【特許請求の範囲】
【請求項１】
動的システムの状態の位置を推定するために、粒子のセットを提供するステップ；
前記粒子のセットの一つ以上の粒子を移動させるために、ローカルモード・シーキング・メカニズムを適用するステップ；
前記粒子のセットの粒子数を修正するステップ；および
前記粒子のセットの粒子を使用して、前記動的システムの前記状態の前記位置を推定するステップ；
を有する方法。
【請求項２】
前記粒子ベースのアルゴリズムが、粒子フィルタアルゴリズムを含む、請求項１記載の方法。
【請求項３】
前記ローカルモード・シーキング・メカニズムが平均値シフト分析処理を含む、請求項１記載の方法。
【請求項４】
前記粒子数を適応させるステップがＫｕｌｌｂａｃｋ−Ｌｅｉｂｌｅｒ−ｄｉｓｔａｎｃｅ（ＫＬＤ）サンプリング処理を使用するステップを含む、請求項１記載の方法。
【請求項５】
前記ＫＬＤサンプリング処理のビンの数を推定するために、ＫＤ−ツリー構造を使用するステップ、を更に有する、請求項４記載の方法。
【請求項６】
前記ＫＤ−ツリー構造を使用するステップは、ＫＤ−ツリーに粒子を挿入するステップを有し、前記粒子はディメンションを含み、かつ粒子を挿入するステップは、
所与の粒子の量子化された値を作り出すために、前記所与の粒子の前記ディメンションを量子化するステップ、
前記所与の粒子を前記ＫＤ−ツリーのノードと関連させることによって、前記ＫＤ−ツリーに前記所与の粒子を挿入するステップ、
異なる粒子の量子化された値を作り出すために、前記異なる粒子の前記ディメンションを量子化するステップ、
前記所与の粒子の前記量子化された値と前記異なる粒子の前記量子化された値とを比較するステップ、および
前記２つの量子化された値を比較した結果に基づき、前記異なる粒子を捨てるか否かを決定するステップ、
を有する請求項５記載の方法。
【請求項７】
前記異なる粒子を捨てるか否かを決定するステップが、前記異なる粒子の前記量子化された値が前記所与の粒子の前記量子化された値と同じである場合、前記異なる粒子を捨てるステップを有する、請求項６記載の方法。
【請求項８】
前記粒子ベースのアルゴリズムは、粒子フィルタアルゴリズムを含み、
前記メカニズムは、平均値シフト分析処理を含み、かつ
前記粒子数を適応させるステップは、Ｋｕｌｌｂａｃｋ−Ｌｅｉｂｌｅｒ−ｄｉｓｔａｎｃｅ（ＫＬＤ）サンプリング処理を使用するステップを含む、
請求項１記載の方法。
【請求項９】
前記粒子数を適応させるステップは、
前記粒子を移動させるために前記メカニズムを適用した後に実行される、
請求項１記載の方法。
【請求項１０】
前記粒子ベースのアルゴリズムは、粒子フィルタアルゴリズムを含み、かつ
複数のタイプのデータが、粒子重みを算出するために用いられる、
請求項１記載の方法。
【請求項１１】
前記粒子フィルタアルゴリズムがビデオのオブジェクトを追尾するために用いられ、かつ前記複数のタイプのデータは、色ヒストグラムデータおよび勾配データを含む、
請求項１０記載の方法。
【請求項１２】
前記粒子ベースのアルゴリズムは、粒子フィルタアルゴリズムを含み、かつ
前記粒子フィルタアルゴリズムは、動的モデルを含み、前記粒子フィルタアルゴリズムの所与の繰返しにおいて、前記動的モデルは（１）第１の運動モデルを使用して粒子の第１の部分を更新し、かつ（２）前記第１の運動モデルと異なる第２の運動モデルを使用して粒子の第２部分を更新する、
請求項１記載の方法。
【請求項１３】
前記粒子フィルタアルゴリズムが、ビデオのオブジェクトを追尾するために用いられ、
前記第１の運動モデルは、ランダムウォーク・モデルを含み、かつ
前記第２の運動モデルは、二次の自己回帰モデルを含む、
請求項１２記載の方法。
【請求項１４】
前記粒子ベースのアルゴリズムは、データの測定を使用する、請求項１記載の方法。
【請求項１５】
前記粒子ベースのアルゴリズムは、ビデオのオブジェクトを追尾するために用いられ、前記動的システムの前記状態は、前記オブジェクトの位置を含み、かつ
当該方法は、
前記オブジェクトの推定位置をエンコーダに提供するステップ、
第１の符号化アルゴリズムを使用して、前記推定位置に対応する前記ビデオの一部をエンコードするステップ、および
第２の符号化アルゴリズムを使用して、前記推定位置に対応しない前記ビデオの他の部分をエンコードするステップ、
を更に有する請求項１記載の方法、
【請求項１６】
前記粒子ベースのアルゴリズムは、ビデオのオブジェクトを追尾するために用いられ、前記動的システムの前記状態は、前記オブジェクトの位置を含み、かつ
当該方法は、
前記オブジェクトの推定位置を処理デバイスに提供するステップ、
前記オブジェクトの強調された表示を可能にするために、前記オブジェクトの前記推定位置を用いて、前記処理デバイスによって、前記ビデオを修正するステップ、
を更に有する請求項１記載の方法。
【請求項１７】
前記強調された表示は、前記ビデオの前記オブジェクトをハイライトするステップを含む、請求項１６に記載の方法。
【請求項１８】
前記ローカルモード・シーキング・メカニズムを適用する前に、
動的モデルを使用して前記一つ以上の粒子を更新することによって、前記粒子のセットの一つ以上の粒子を移動させるステップ、
を更に有する請求項１の方法。
【請求項１９】
前記粒子数を修正するステップの後で、かつ、前記状態の前記位置を推定するステップの前に、粒子の前記セットをリサンプリングすることによって粒子の前記セットの一つ以上の粒子を移動させるステップ、を更に有する請求項１記載の方法。
【請求項２０】
処理デバイスを有する装置であって：
動的システムの状態の位置を推定することに用いる粒子のセットを提供し、
前記粒子のセットの一つ以上の粒子を移動させるために、ローカルモード・シーキング・メカニズムを適用し、
前記粒子のセットの粒子数を修正し、かつ
前記粒子のセットの粒子を使用して、前記動的システムの前記状態の前記位置を推定する、
ことを特徴とする装置。
【請求項２１】
更に前記処理デバイスは、
（１）オブジェクトの位置を含む前記動的システムの前記状態によって、ビデオの前記オブジェクトを追尾し、かつ（２）前記オブジェクトの推定位置を提供し、かつ
更に当該装置は、エンコーダを有し、前記エンコーダは、
（１）前記処理デバイスから前記オブジェクトの前記推定位置を受け取り、（２）第１の符号化アルゴリズムを使用して、前記推定位置に対応する前記ビデオの一部をエンコードし、かつ（３）第２の符号化アルゴリズムを使用して、前記推定位置に対応しない前記ビデオの他の部分をエンコードすること、
を特徴とする請求項２０記載の装置。
【請求項２２】
更に前記処理デバイスは、
（１）オブジェクトの位置を含む前記動的システムの前記状態によって、ビデオの前記オブジェクトを追尾し、かつ（２）前記オブジェクトの推定位置を提供し、かつ
更に当該装置は、後処理デバイスを有し、前記後処理デバイスは、
（１）前記処理デバイスから前記オブジェクトの前記推定位置を受け取り、かつ（２）前記オブジェクトの強調された表示を可能にするために、前記オブジェクトの前記推定位置を用いて、前記ビデオを修正すること、
を特徴とする請求項２０記載の装置。
【請求項２３】
動的システムの状態の位置を推定するために、粒子のセットを提供するための手段；
前記粒子のセットの一つ以上の粒子を移動させるために、ローカルモード・シーキング・メカニズムを使用するための手段；
前記粒子のセットの粒子数を修正するための手段；および
前記粒子のセットの粒子を使用して、前記動的システムの前記状態の前記位置を推定するための手段、
を有する装置。
【請求項２４】
動的システムの状態の位置を推定するために、粒子のセットを形成するステップ；
前記粒子のセットの一つ以上の粒子を移動させるために、ローカルモード・シーキング・メカニズムを使用するステップ；
前記粒子のセットの粒子数を修正するステップ；および
前記粒子のセットの粒子を使用して、前記動的システムの前記状態の前記位置を推定するステップ、
を一つ以上の処理デバイスに実行させるための命令を格納した、プロセッサで読取り可能な、媒体を有する装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動的な状態推定に関する。
【背景技術】
【０００２】
動的システムとは、システムの状態が時間とともに変化するシステムをいう。状態はシステムを特徴づける一組の任意に選ばれた変数でもよい。しかし、状態はしばしば関心対象に関連する変数を含む。例えば、動的システムはサッカーの試合のビデオに対して構成されてもよい。そして、ボールの位置を状態として選択してもよい。ボールの位置が時間とともに変化するので、システムは動的である。ビデオの新しいフレームにおいて、システムの状態の推定、すなわちボールの位置が、関心対象となる。
【０００３】
この出願は、２００６年９月２９日に出願の米国の仮特許出願番号第６０／８４８，２９７号発明の名称「平均化シフトによるローカルモード探索によるＫＬＤサンプリングベース粒子フィルタ」の利益を主張する。そして、この出願は全て本願明細書において引用したものとする。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
実施例において、粒子のセットが、動的システムの状態の位置を推定するために提供される。ローカルモード・シーキング・メカニズムは、粒子のセットの一つ以上の粒子を移動させるために使用される。そして、粒子のセットの粒子数が修正される。動的システムの状態の位置は、粒子のセットの粒子を使用して推定される。一つ以上の実施例の詳細については、添付の図面および下記の明細書において説明する。実施例は、例えば、方法として、または一組のオペレーションを実行するように構成される装置または一組のオペレーションを実行するための命令を格納している装置として実施されてもよい。他の態様および特長は、添付の図面および請求項に関連して考慮される以下の詳細な説明から明らかになる。
【課題を解決するための手段】
【０００５】
まず、概要を説明する。粒子は各々潜在的な状態の候補を示す。本願明細書においては、説明を簡単にするため、状態空間の粒子の位置または粒子のポジションと表現する。特定の実施例によって、粒子フィルタ（ＰＦ：Particle  Filter）を使用した動的な状態推定がなされる。粒子フィルタにおいて、粒子の位置が、平均値シフト分析に基づくローカルモード・シーキング・アルゴリズムを使用して修正される。加えて、粒子フィルタにおいて、ＫｕＨｂａｃｋ−Ｌｅｉｂｌｅｒ−ｄｉｓｔａｎｃｅ（ＫＬＤ）サンプリング処理を使用して、粒子の数が修正される。平均値シフト分析は、粒子の位置を改善することを試みる。このことにより、しばしばＰＦによって経験される縮退の問題を減らすことができる。ＫＬＤサンプリング処理は、ＰＦにおいて使用する粒子数を減少させることを試みる。このことにより、ＰＦの推定能力の質を大幅には犠牲にせずに、ＰＦの計算の複雑さを減らすことができる。実施例は、非線形および非ガウス性システムを取扱う場合に有利である。
【図面の簡単な説明】
【０００６】
【図１】状態推定器のブロック図である。
【図２】図１の状態推定器によって推定された状態に基づきデータを符号化するシステムのブロック図である。
【図３】図１の状態推定器によって推定された状態に基づきデータを符号化するシステムのブロック図である。
【図４】図１の状態推定器の実施例によって実行される様々な機能を示す図である。
【図５】粒子フィルタを実施する方法のフローチャートである。
【図６】ローカルモード・シーキング・メカニズムを更に含む図５の粒子フィルタを実施する方法のフローチャートである。
【図７Ａ】ローカルモード・シーキング・メカニズムを実装するための擬似コード・リストである。
【図７Ｂ】ローカルモード・シーキング・メカニズムを実装するための擬似コード・リストである。
【図８Ａ】ＫｕｌＩｂａｃｋ−Ｌｅｉｂｌｅｒ−ｄｉｓｔａｎｃｅのサンプリング・処理を更に含む図６の粒子フィルタを実施する方法のフローチャートである。
【図８Ｂ】ＫｕｌＩｂａｃｋ−Ｌｅｉｂｌｅｒ−ｄｉｓｔａｎｃｅのサンプリング・処理を更に含む図６の粒子フィルタを実施する方法のフローチャートである。
【図９】ＫＤ−ツリーにより粒子を表している具体例を示す図である。
【図１０】粒子を用いてシステムの状態を推定する方法のフローチャートを示す図である。
【発明を実施するための形態】
【実施例】
【０００７】
図１に、１つの実施例を示す。システム１００は、例えばコンピュータにおいて実現される状態推定器１１０を有する。状態推定器１１０は、粒子アルゴリズム・モジュール１２０、ローカルモード・モジュール１３０および数アダプタモジュール１４０を含む。粒子アルゴリズム・モジュール１２０は、動的システムの状態を推定するための粒子ベースのアルゴリズム（例えばＰＦ）を実行する。ローカルモード・モジュール１３０は、例えば、ＰＦにおける粒子に対して、平均値シフト分析を実行することによって、ローカルモード・シーキング・アルゴリズムを適用する。数アダプタモジュール１４０は、例えば、ＫＬＤサンプリング処理を粒子に適用することによって、粒子ベースのアルゴリズムで使用する粒子数を修正する。モジュール１２０から１４０の実施例の処理は、図４から図１０を用いて後述する。モジュール１２０から１４０は、例えば、別々に実装されるか、単一のアルゴリズムに集積化されてもよい。状態推定器１１０は、入力として初期状態１５０およびデータ入力１６０を持ち、出力として推定された状態１７０を提供する。初期状態１５０は、例えば、初期状態検出器によって、または、手動処理によって決定されてもよい。より典型的な具体例としては、ビデオにおける対象の位置を状態として持つようなシステムが挙げられる。このようなシステムでは、初期のオブジェクト位置は、例えば、自動オブジェクト検出処理を使用したエッジ検出およびテンプレート比較、または、ビデオを見ているユーザにより手動で決定してもよい。データ入力１６０は、例えば、一連のビデオ画像でもよい。推定された状態１７０は、例えば、特定のビデオ画像のボールの位置の推定でもよい。
【０００８】
推定された状態１７０が、様々な目的のために使われ得る。更な詳細な内容を提供するために、図２および３にいくつかの応用を示す。
【０００９】
図２を参照すると、１つの実施例において、システム２００は、送信／記憶装置２２０に接続されるエンコーダ２１０を含む。エンコーダ２１０および送信／記憶装置２２０は、例えば、コンピュータまたは通信エンコーダに実装される。エンコーダ２１０は、図１のシステム１００の状態推定器１１０により提供される推定された状態１７０、状態推定器１１０によって使用されたデータ入力１６０をアクセスする。エンコーダ２１０は、様々な符号化アルゴリズムの一つ以上に従ってデータ入力１６０をエンコードする。そしてエンコードされたデータ出力２３０を送信／記憶装置２２０に提供する。
【００１０】
更に、エンコーダ２１０は、差動的にデータ入力１６０の異なる部分をエンコードするために、推定された状態１７０を使用する。例えば、状態がビデオのオブジェクトの位置を表す場合、エンコーダ２１０は第１の符号化アルゴリズムを使用して推定位置に対応する一部のビデオをエンコードし、かつ第２の符号化アルゴリズムを使用して推定位置に対応しないビデオの他の部分をエンコードしてもよい。第１のアルゴリズムは、第２の符号化アルゴリズムより符号化冗長性を有してもよい。そうすることにより、推定するオブジェクトの（可能性の高い）位置は、ビデオの他の部分よりより詳細で高い解像度によって再生されることが期待される。このようにして、例えば、一般の低解像度の伝送よりは高い解像度を、追尾されるオブジェクトに提供してもよい。そして、例えば、ユーザがよりゴルフマッチのゴルフボールをより楽に見ることができるようにする。このような実施例においては、ユーザが狭い幅（低データ速度）のに接続されたモバイル機器上でゴルフマッチを見ることができる。モバイル機器は、例えば、携帯電話またはパーソナル携帯情報機器（ＰＤＡ）でもよい。低いデータ速度でゴルフマッチのビデオをエンコードし、ゴルフボールをエンコードするために追加にビットを使用することによって、データレートは低く保たれる。
【００１１】
送信／記憶装置２２０は、一つ以上の記憶装置または伝送装置を含んでもよい。したがって、送信／記憶装置２２０は、エンコードされたデータ２３０にアクセスし、かつデータを記憶し２３０、またはデータを送信する２３０。
【００１２】
図３を参照すると、１つの実施例では、システム３００は、ディスプレイ３２０に接続される処理装置３１０を含む。処理装置３１０は、図１のシステム１００の状態推定器１１０により提供される推定された状態１７０にアクセスし、かつ状態推定器１１０により用いられたデータ入力１６０にアクセスする。処理装置３１０は、データ入力１６０を強調するために推定された状態１７０を使用し、拡張データ出力３３０を提供する。ディスプレイ３２０は、強調されたデータ出力３３０にアクセスし、かつディスプレイ３２０に強調されたデータを表示する。
【００１３】
さまざまな実施例は、例えば、オブジェクトをハイライトすることによって、データを強調する。そのような実施例では、ボールの色を明るいオレンジに変えることによって、ボール（オブジェクト）を強調する。加えて、さまざまな実施例は、オブジェクトの推定位置に基づきデータを強調するべきかどうか決める。そのような実施例において、処理装置３１０は、サッカーボールがゴールに入ったかどうかを判断するためにサッカーボールの推定位置を使用する。サッカーボールがゴールに入った場合、処理装置３１０はサッカーの試合を見ているユーザに明示するためにビデオにＧＯＡＬの語を挿入する。例えば、処理装置３１０はプレーのフィールドに関してサッカーボールの位置に関する情報にアクセスすることによってかかる決定をしてもよい、そして、かかる情報は、例えば、カメラの周知の位置および方向から決定してもよい。システム３００の実装は、例えば、送信側または通信リンクの受信側であってもよい。１つの実施例、システム３００および状態推定器１１０が受信側に設置され、データを受け取り、かつ復号化した後に、状態が推定される。他の実施例では、システム３００および状態推定器１１０は、送信側に置かれ、データの強調は、符号化および伝送の前に行われる。送信側のオペレータに強調されたデータの表示を提供する。他の実施例において、システム３００および状態推定器１１０は受信側にある。そして、推定された状態１７０およびデータ入力１６０を送信側に送る。明らかなように、処理装置３１０はエンコーダ２１０として構成されてもよい。そして、強調されたデータを差動的にエンコードする。
【００１４】
図４を参照すると、線図４００は、動的システムの状態の確率分布関数４１０を示す。線図４００は、状態推定器１１０の実装によって実行されるさまざまな機能を模式的に表す。線図４００は、レベルＡ、Ｂ、ＣおよびＤの各々において、一つ以上の機能を表す。
【００１５】
レベルＡは、ＰＦによる４つの粒子Ａ１、Ａ２、Ａ３およびＡ４の生成を表す。わかりやすくするために、別々の垂直の破線は、４つの粒子Ａ１、Ａ２、Ａ３およびＡ４の各々の、確率分布関数４１０の位置を示す。
【００１６】
レベルＢは、平均値シフト分析に基づくローカルモード・シーキング・アルゴリズムによって４枚の粒子Ａ１−Ａ４を対応する粒子Ｂ１−Ｂ４へ移すことを示す。わかりやすくするために、縦の実線は、４つの粒子Ｂ１、Ｂ２、Ｂ３およびＢ４の各々の、確率分布関数４１０の位置を示す。粒子Ａ１−Ａ４の各々のシフトは対応する矢印ＭＳ１−ＭＳ４によって視覚的に示されている。そして、それは粒子Ａ１−Ａ４によって示される位置から、それぞれ、粒子Ｂ１−Ｂ４によって示される位置まで粒子が移動したことを示している。レベルＣは重み付けされた粒子Ｃ２−Ｃ４を表す。そして、それぞれ、粒子Ｂ２−Ｂ４と同じ位置を有する。粒子Ｃ２−Ｃ４は、ＰＦにおいて粒子Ｂ２−Ｂ４に対して決定された重みを示し、様々なサイズで表している。ＫＬＤサンプリング処理に従って、レベルＣは、粒子の数の減少を反映する。粒子Ｂ１は、破棄されている。
【００１７】
レベルＤは、リサンプリング・処理の間に、生成される３つの新しい粒子を表す。レベルＤにおいて生成される粒子の数は、レベルＣの粒子数と同数である。これが矢Ｒ（Ｒは、リサンプリングを表す）で示されている。レベルＡ−Ｄによって表される各々の処理は、図８において更に説明する。
【００１８】
図５を参照すると、１つの実施例において、システムの状態を推定するために、処理５００が使用される。処理５００はＰＦによって状態を推定するために用いる処理の実施例である、なお、他の実施例では、これとは異なった動作をする。処理５００を説明する前に、粒子フィルタ（ＰＦ）の簡単な概要を説明する。なお、ＰＦについての詳細は、より詳細に記述されている他の文献を参照されたい。
【００１９】
ＰＦは、内在する分布および与えられたシステムに関わらず、状態変数の密度の伝播を推定するための利用性の高いベイズ・フィルタ・フレームワークを提供する。密度は、状態空間の粒子によって表される。一般に、動的システムは、次式（数１、数２）のように表現される。
【００２０】
【数１】
2010505184.tif 000003
【００２１】
【数２】
2010505184.tif 000004
【００２２】
【数３】
2010505184.tif 000005
【００２３】
【数４】
2010505184.tif 000006
【００２４】
【数５】
2010505184.tif 000007
【００２５】
【数６】
2010505184.tif 000008
ここで、数３は状態ベクトルを表す。数４は測定ベクトルである。また、ｆおよびｇは２つのベクトルの値関数（それぞれ、動的モデルおよび測定（measurement）モデル）である。数５および数６は、それぞれ、処理（動的）および測定雑音を表す。動的モデルおよび測定モデルは、動的システムの特性に基づいて決定される。
【００２６】
【数７】
2010505184.tif 000009
【００２７】
【数８】
2010505184.tif 000010
ＰＦは、雑音が多い測定（数８）から再帰的に状態（数７）を推定するための方法論を提供する。ＰＦによって、状態分布は、重みづけされた粒子から成る別々のランダムな手段によって近似される。ここで、粒子は、状態空間からの未知の状態のサンプルである。粒子の重みはベイズの理論によって計算される。粒子のセットの進化は、動的モデルに従って各粒子が伝播することによって表現される。
【００２８】
図５を再度参照すると、処理５００は、以前の状態５１０から粒子および累積的な重み係数の初期セットにアクセスすることを含む。累積的な重み係数は、粒子の重みのセットから生成されてもよく、かつ、通常はより速い処理が得られる。なお、処理５００の最初の処理において、以前の状態とは、初期状態のことであり、粒子の初期セットおよび重み（累積的な重み係数）が生成されなければならない。初期状態は、例えば、初期状態１５０として提供されていてもよい。
【００２９】
ループ制御変数「ｉｔ」は、ループ５２０で初期化５１５され、現在の状態が決定されるまでループ５２０が繰り返される。ループ５２０は、ループ制御変数「ｉｔ」を使用し、「ｉｔｅｒａｔｅ」回だけ繰り返し実行される。ループ５２０中で、粒子の初期セットの各粒子は、ループ５２５で別々に処理される。一実施例では、ＰＦはテニスボールを追尾するためのテニス・マッチのビデオに適用される。ループ５２０は、新しいフレームごとに予め定められた回数（ループの繰返し変数「ｉｔｅｒａｔｅ」の値）実行される。ループ５２０の各繰返しは粒子の位置を改善すると推測される。その結果、テニスボールの位置が各フレームに対して推定されるときに、推定は、良好な粒子に基づいて推定される。
【００３０】
ループ５２５は、累積的な重み係数に基づく粒子を選択することを含む５３０。これは、周知のように、最も大きい重みを有する残りの粒子位置を選択する方法である。多くの粒子が同じ位置にあってもよいことに留意されたい。この場合、通常は、位置の各々につき一回だけ、ループ５２５を実行すればよい。ループ５２５は、それから、選択された粒子に対して、状態空間の新しい位置を予測することによって粒子を更新することを含む５３５。予測は、ＰＦの動的モデルを使用する。
【００３１】
ループ５２５は、粒子の更新された重みを、測定モデルＰＦを使用して決定することを含む５４０。重みを決定するためには、周知のように、観測された／測定されたデータ（例えば、現在フレームのビデオ・データ）を分析することが必要である。テニス・マッチ実施例を再び取り上げると、現在フレームのデータは、粒子によって示される位置と、テニスボールの最後の位置のデータとが比較される。比較は、例えば、カラー・ヒストグラムの分析、またはエッジ検出であってもよい。粒子に対して決定される重みは、比較の結果に基づく。オペレーション５４０は、粒子の位置の累積的な重み計数を決定することを含む。
【００３２】
ループ５２５は、他の粒子に対する判断が必要な場合、繰り返される５４２。更に多くの粒子が処理される必要がある場合、ループ５２５が繰り返される、そして、処理５００はオペレーション５３０へジャンプする。最初の（または「古い」）粒子セットのあらゆる粒子に対してループ５２５が実行されると、更新された粒子の完全なセットが生成されたことになる。
【００３３】
ループ５２０は、それから、サンプリングアルゴリズム５４５を使用して「新しい」粒子セットおよび新しい累積的な重み計数を生成する。リサンプリングアルゴリズムは粒子の重みに基づく。したがって、より大きい重みを有する粒子に集中する。リサンプリングアルゴリズムは各々が同じ個々の重みを有する粒子のセットを作り出す。なお、これは、特徴的に多くの粒子を有する特定の位置になされる。このように、粒子位置は、通常は異なる累積的な重み計数を有する。
【００３４】
通常、リサンプリングは、ＰＦにおける共通の課題である縮退を減らすのに寄与する。リサンプリングには幾つかの方法がある。多項式（multinomial）、残差（residual）、層別化（residual）、および系統的なリサンプリングである。１つの実施例は、残差のリサンプリングを使用する。残差リサンプリングは粒子順序に影響されない。
【００３５】
ループ５２０は、ループ制御変数「ｉｔ」をインクリメントする５５０、そして、「ｉｔ」を繰返し数「ｉｔｅｒａｔｅ」５５５と比較する。ループ５２０による他の繰返しが必要である場合、新しい粒子のセットおよびその累積的な重み係数が利用可能とされる５６０。
【００３６】
ループ５２０が「ｉｔｅｒａｔｅ」回数を実行した後に、粒子セットは「良好な」粒子セットであると推定される。そして、現在の状態が決定される５６５。周知のように、新しい状態は、新しい粒子のセットの粒子を平均することによって決定される。
【００３７】
図６を参照すると、１つの実施例は、システムの状態を推定するために、処理６００を使用する。処理６００はＰＦを平均値シフト分析に基づくローカルモード・シーキング・アルゴリズムと結合する処理の実施例である。なお、他の実施例とは異なって動作する。ローカルモード・シーキング・アルゴリズムおよび平均値シフト分析の概要を図７と共に示す。平均値シフト分析を使用したローカルモード・シーキングについての詳細は、他の文献を参照されたい。
【００３８】
平均値シフト・アルゴリズムは、複雑なマルチ・モーダル状態空間の分析のための、および、状態空間の任意に成形されたクラスタを詳細に表現するための一般のノンパラメトリック手法である。平均値シフト・アルゴリズムは、ＰＦにおいて共通での課題である縮退を解決するための方法を提供する。
【００３９】
図６を再度参照すると、処理６００には処理５００と同じ多数のオペレーションが含まれる。このため、反復オペレーションは処理６００では再度説明しない。なお、処理６００は、平均値シフト分析を用いたローカルモード・シーキング・アルゴリズムを実行する付加的なオペレーションを含む６１０。処理６００は、同様に、それぞれ、ループ５２０および５２５と同様であるループ６２０およびループ６２５を含む。ただし、ループ６２０および６２５は、ローカルモード・シーキング・アルゴリズム６１０を実行することを更に含んでいる。ローカルモード・シーキング・アルゴリズムは、勾配に沿って、勾配原則に基づきおよび反復的に、極大と見なされる方向に所与の粒子を移動させる。かかる移動は測定データに基づいて修正される粒子を作り出す。そして、この修正はシステムの状態の予測を改善することになる。
【００４０】
アルゴリズムの「ローカルモード」とは、所与の粒子の位置に対して決定される値である。例えば、「ローカルモード」は、測定または観察されたデータに基づいて計算されてもよい。
【００４１】
図７を参照すると、擬似コード・リスト７００は、平均値シフト分析を用いたローカルモード・シーキング・アルゴリズムを実行するための処理の例を示している。
擬似コード・リスト７００において：
−粒子の現在位置は数９によって表される。
【００４２】
【数９】
2010505184.tif 000011
−粒子の次の位置は数１０によって表される、
【数１０】
2010505184.tif 000012
−所与の粒子の以前の位置のローカルモードは、数１１によって表される
【数１１】
2010505184.tif 000013
ここで「ｕ」は、ローカルモードのためのビン（ｂｉｎ）インデックスである、
−現在の粒子位置のローカルモードは、数１２によって表される。および、
【数１２】
2010505184.tif 000014
−バタチャリヤ係数（「Ｂ−係数」）は、ρによって表される。
【００４３】
擬似コード・リスト７００は、粒子の以前の位置のローカルモードが利用できると仮定することから始める７０５。そして、ローカルモードは、前回において推定された計測空間の状態モードを指している。擬似コード・リスト７００は、それから粒子毎に７１０に進む。粒子ごとに、擬似コード・リスト７００は、現在位置でのローカルモードを決定する。ここで、ローカルモードは、ローカルでの可能性の分布の極大を指す。そして、そのローカルモード７２０に関連するＢ−係数を決定する。
【００４４】
擬似コード・リスト７００は、それから、粒子を移すために、平均値シフト重み（粒子フィルタ・フレームワークの粒子重みとは異なる）を決定する７３０。擬似コード・リスト７００は、それから粒子に対する次の位置を決定する７４０。次の位置の粒子のローカルモードを計算する７５０。そして、次のローカルモードと関連するＢ−係数を計算する７５０。
【００４５】
擬似コード・リスト７００は、現在のＢ−係数を次のＢ−係数と比較する７６０。次のＢ−係数が現在のＢ−係数以上の場合、リスト７００は、より多くの繰返しが必要かどうかについて判断する７７０。その判断は、場所の変更が閾値より大きいかどうかに基づく。場所の変更が閾値より大きい限り、付加的な繰返しが実行される７７０。次のＢ−係数が現在のＢ−係数未満である場合、次のＢ−係数が現在のＢ−係数未満とならないところまで、場所の変更は半分に減らされる７６０。それから、場所の変更が評価され、繰返しが必要か判断される７７０。
【００４６】
図８を参照すると、１つの実施例は、システムの状態を推定するために、処理８００を使用する。処理８００は、ＰＦにおいて、下記の両方を結合する処理の実施例である。すなわち、（１）平均値シフト分析に基づいた、ローカルモード・シーキング・アルゴリズム、および（２）ＫＬＤサンプリング処理。なお、他の実施例とは異なって動作する。ＫＤ−ツリーを含むＫＬＤサンプリング処理の概要に関して、図８−図９を参照しながら、以下説明する。ＫＬＤサンプリング処理およびＫＤ−ツリーについての詳細は別の文献を参照されたい。
【００４７】
ＫＬＤサンプリング処理は、状態推定処理の間、粒子セットの寸法を適応させることによって、ＰＦの効率を改善する統計的アプローチである。鍵となる着想は、ＰＦのサンプル・ベースの表現によって導かれる近似エラーを結合することである。したがって、ＰＦは、密度が状態空間の小さい部分に集中する場合には、より少ない数のサンプルを選択し、状態の不確定度が高い場合には、より多数の数のサンプルを選択する。
【００４８】
処理８００に記載され、かつ用いられるＫＬＤサンプリング処理は、ＫＤ−ツリー構造に基づく。
【００４９】
ここでεはエラーバウンド（error  bound）を示し、１−δは、ＫＬＤがεより小さい可能性を示し、かつ、ｚ１−δは、標準正規分布の上の（１−δ）分位点である。１−δおよびｚ１−δの両者は、正規分布の標準統計数表から入手可能である。通常、１−δは、ＫＬＤサンプリング処理で固定され、かつεは個別に調整することができる。
【００５０】
ＫＤ−ツリーは、ｋ次元データ・ポイントの有限集合を格納する２進数ツリーである。
ＫＤ−ツリーの目的は、セルがあまり多くの入力データ・ポイントを含まないように、階層的にスペースを比較的少ない数のセル（ビン：bins）に分解することである。処理８００において、ＫＤ−ツリー構造は、ＫＬＤ−サンプリングのためのビン（ＫＤ−ツリーのサイズに等しい）の数を算出するために用いる。
【００５１】
ＫＬＤサンプリング処理を用いて、実施例は、固定値の粒子数を有することを回避する。これによって、固定数の粒子を用いる他の実施例と比較して、この実施例では、少ない数の粒子を扱うことを可能とする。これは、計算の複雑度を低下させることができる。加えて、実施例において、適応によって、特定の状況で必要がある場合には、粒子数を増加させることができる。一方、十分な粒子を有しない非適応システムでは、追加すべき粒子が必要である場合、状態を推定することに失敗することがあり得る。例えば、オブジェクト追尾装置は、オブジェクトを追尾に失敗する。実施例の適応性は、ＰＦを推定されたスペースの状態の特性に適応させ、かつ複雑な動的システムの非線形および非ガウス性の課題を解決する際に有効に働く。
【００５２】
図８を再度参照すると、処理８００は処理６００と同じ多数のオペレーションを含む。このため、反復オペレーションは処理８００の説明において割愛する。しかしながら、処理８００は、以下説明するように、多数の付加的なオペレーションを含む。
【００５３】
処理８００は、例えば以前の状態から粒子および累積的な重み係数の初期セットにアクセスすることを含む８１０。加えて、ユーザによって与えられる、エラーバウンドおよびビン（ｂｉｎ）サイズ８１０にアクセスする。ループ制御変数「ｉｔ」および粒子カウント「ｎ」が初期化される。そして、ＫＤ−ツリーがリセットされる８１５。
【００５４】
ループ８２０は、現在の状態を決定するまで、繰り返し実行される。ループ８２０はループ制御変数「ｉｔ」を使用する。そして、「ｉｔｅｒａｔｅ」回、実行を繰り返す。ループ８２０の中で、粒子の初期セットの粒子は、ループ８２５で別に処理される。ループ８２０および８２５は、それぞれ、ＫＬＤサンプリング処理を提供するための修正を除いて、ループ６２０および６２５に類似している。
【００５５】
ループ８２５は、ＫＤ−ツリーに選択された粒子を挿入すること８３０、「ｎ」をインクリメントすること８４０、および、ＫＤ−ツリーの現在のサイズｋを決定すること８４０を含む。ＫＤ−ツリーに粒子を挿入し、かつＫＤ−ツリーのサイズを決定するオペレーションは、図９に図示される。
【００５６】
図９を参照すると、具体例９００は、ＫＤ−ツリーに２次元の粒子を挿入する点が示されている。具体例９００は、テーブルを有する９１０。このテーブルは、０と０．９９の間の正規化された値、および、量子化された値を有する７つの粒子を示している。量子化された値は、正規化数にビンの数を乗算し、小数部を切り捨てることによって求まる。あるいは、ビンサイズによって正規化数を割り、小数部を切り捨てることによって求まる。所望のビンの数は５である。これはビンサイズに対応しており、サイズは０．２である（ビンのサイズは同一と仮定）。例えば、他の実施例では、切上げまたは切捨てでもよい。
【００５７】
具体例９００において、ＫＤ−ツリー９２０は７つの量子化された粒子を含んでいることを示している。量子化された粒子は、挿入処理の間、順番に取られる。第１の量子化された粒子は、ＫＤ−ツリー９２０のルートノードに割り当てられる。挿入されるその他の量子化された粒子はｘ座標を有し、ルートノード粒子（３，４）のｘ座標と比較される。比較に基づいて、（１）ｘ座標がより３より小さい場合、次の量子化された粒子はツリーの左に位置し（２）ｘ座標が３よりも大きい場合、ツリーの右に位置する。（３）ｘ座標が３に等しい場合、破棄される。このように、残りの量子化された粒子を挿入する際に、以下の事象が発生する：
−０は３より小さいので、第２の量子化された（０、１）粒子は、ルートノードの左に位置する、すなわちノードＡに割り当てられる。
−第３の量子化された粒子（３、１）は、ルートノードで捨てられる。その理由は、ｘの係数が３であり同数だからである。なお、第３の量子化された粒子が捨てられる場合であっても、我々は第３の量子化された粒子についてＫＤ−ツリーに挿入されたこととする。
−１はより３小さいので、第４の量子化された粒子（１、３）はルートノードの左に位置する。１つの粒子だけがいかなる所与のノードにも割り当てられることになっているので、第４の量子化された粒子は、ノードのＡで、先ほどの第２の量子化された粒子（０、１）と比較されなければならない。ツリーのノードのＡレベルでの比較は、ｙ座標によってなされる。このように、３が１より大きいため、第４の量子化された粒子はノードのＡの右のノードＣに置かれる。ノードＣとの比較は、ツリーのこのレベルの他のいかなるノードもｘ座標に関してなされる。ＫＤ−ツリー９２０において、ノードと関連する粒子は、そのノードで比較される１つの座標を示すために下線を引いて示される。例えば、ルートノードで粒子（３、４）の３が下線を引かれる。
−４は３よりも大であるので、第５の量子化された粒子（４、２）はルートノードの右のノードのＢに置かれる。
−２が３より小さいので、第６の量子化された粒子（２、２）はルートノードの左に行き、２が１より大きいのでノードのＡの右に行き、かつ、２が１より大であるのでノードのＣの右に行き、ノードのＤに割り当てられる。
−１が３より小さいので、第７の量子化された粒子（１、３）はルートノードの左に行き、３が１より大であるのでノードのＡの右に行き、かつ、ノードＣで１が１に等しいので破棄される。
【００５８】
ツリーｋのサイズは、ノードの数に等しい。ＫＤ−ツリーのノードは、ルートノードおよびノードＡ−Ｄである。したがって、ｋ＝５である。
【００５９】
他の実施例は、粒子を捨てることよりもむしろ、複数の粒子を所与のノードと関連させる。
【００６０】
ループ８２５は、周知の方程式８５０を使用して、エラーバウンド（ε）を達成できる必要な粒子数を推定することを含む。推定値Ｎａは、ツリーのサイズ（ｋ）に依存する。ｋ＝１である場合、Ｎａ＝２を仮定する。ｋ＞１とき、我々はＮａを決定するためにオペレーション８５０の方程式を使用する。ループ８２５は、オペレーション８６０において、「ｎ」を分析する。すなわち、（１）「ｎ」がＰｓ未満であるか（Ｐｓは、ループ８２５で処理されることになっている最小限の粒子数）、および（２）「ｎ」がＮａおよびＰｒ（Ｐｒは、ループ８２５で処理されることになっている最大粒子数）の最小値より小さいかを判断する。「ｎ」がＰｓまたは最低最小値より小である場合、ループ８２５は他の粒子のために繰り返される。判断８６０によって定まる、「ｎ」が十分に大きい場合、処理８００がループ８２５を出る。そして図８に示される次のオペレーションを続行する。このオペレーションは、すでに述べた。
【００６１】
図４を再度参照すると、処理８００がレベルＡ−Ｄの各々における粒子を生成するためのオペレーションを含むことが分かる。例えば、処理８００は、以下の処理を含む。（１）少なくとも線図４００のレベルＡで粒子Ａ１−Ａ４を生成するためのオペレーション８１０および５４５、（２）粒子Ａ１−Ａ４を粒子Ｂ１−Ｂ４の位置へ移すためのレベルＢのローカルモード・シーキング・オペレーション６１０、（３）粒子Ｂ２−Ｂ４のための重みを決定するための重み計算オペレーション５４０（レベルＣで結果として粒子Ｃ２−Ｃ４になる）、（４）粒子数を減らすためのループ８２５（結果としてレベルＣで粒子Ｂ１を破棄することになる）、および、（５）レベルＤで、リサンプリングされた粒子を生成するためのリサンプリング・オペレーション５４５。
【００６２】
図１０を参照すると、粒子を用いてシステムの状態を推定する処理１０００を実施する、粒子ベースのアルゴリズムの１つの実施例が示されている。処理１０００は動的システムの状態の位置を推定するために、粒子のセットを提供することを含む１０１０。これは、例えば、オペレーション８１０および５４５のいずれによって行われてもよい。ローカルモード・シーキング・メカニズムは粒子のセットの一つ以上の粒子を移動させるために使用される１０２０。これは、例えば、ローカルモード・シーキング・オペレーション６１０によって行なわれてもよい。粒子のセットの粒子数は、修正される１０３０。これは、例えば、オペレーション８３０、８４０、８５０および８６０の組合せで実施されてもよい。動的システムの状態の位置は、粒子のセットの粒子を使用して推定される１０４０。これは、例えば、平均算出オペレーション５６５によって実施されてもよい。処理１０００は処理８００のさまざまな側面において類似している。かつ処理８００のオペレーションの多数を省略する。これらは、明らかにオペレーションのオプションの性質を示す。実際、処理１０００のオペレーションの多くもオプションである。
【００６３】
更に、処理１０００は、ＰＦ、平均値シフト分析またはＫＬＤサンプリング処理の使用を詳述しない幅広い方法である。処理１０００は、粒子（１０１０）ローカルモード・シーキング・メカニズム（１０２０）粒子数の修正（１０３０）を必要とする。ＰＦ以外の粒子ベースのアルゴリズムとしては、例えば、モンテカルロ法が含まれる。ローカルモード・シーキング・メカニズムは、平均値シフト分析以外の分析に基づいてもよい。例えば、測定値からの（色）ヒストグラム情報よりもむしろ、エッジまたは勾配情報を考慮してもよい。ＫＬＤサンプリング処理以外の、粒子数を修正するためのアルゴリズムとしては、例えば、重みの合計に閾値を設けるアルゴリズムが含まれる。
【００６４】
明らかに、処理１０００は、ＰＦを使用する実施例によって実行することができる。すなわち、処理１０００は、平均値シフト分析を使用してローカルモード・シーキング・アルゴリズムを実行し、かつ、ＫＬＤサンプリング処理を使用している粒子数を修正する。
【００６５】
以下のさまざまな実施例も、ＰＦの動的モデルを使用する。すなわち、複数の運動モデル、例えばランダムウォーク・モデルおよび自己回帰（ＡＲ：Auto  Regressive）モデルの組合せである。ＰＦのインプリメンテーションとしては、ＰＦの所与の繰返しによる動的モデルであって、（１）第１の運動モデルを使用して、粒子の第１の部分を更新し、かつ、（２）第１の運動モデルと異なる第２の運動モデルを使用して、粒子の第２部分を更新するモデルが含まれる。ビデオのオブジェクトを追尾するために使われる１つの特定の実施例としては、第１の運動モデルはランダムウォーク・モデルであり、そして、第２の運動モデルは二次の自己回帰モデルである例が挙げられる。この追尾に関する実施例はオペレーション５３５を修正することによって処理５００を使用する。２つの運動モデルが交替できるように、修正する必要がある。例えば、この修正は、奇数粒子に対してランダムウォーク・モデルを使用し、かつ偶数粒子に対して二次の自己回帰モデルを使用することによって提供されてもよい。
【００６６】
複数の運動モデルを含む動的モデルを用いて、ＰＦは、多様性のある粒子のセットを形成してもよい。これによって、現在の状態のより良好な推定行うことが可能である。加えて、複数の運動モデルを使用することは、より機敏な状態推定を提供し得る。これは、より機敏なオブジェクトトラッキングを含む。単一のモデル、うまくモデル化されない状態変化が発生し得るため、機敏さが求められる。例えば、予想外の状態変化が発生する。例えば、バスケットボールの予想外のはね上がりによって、ボールが後板の上側で見えなくなることがある。これは、その状態のために使用する運動モデルに合わない動作を呈することになる。
【００６７】
様々な実施例は、測定モデルで、様々なデータを使用する。したがって、さまざまなＰＦの実施例で、多様なデータが、処理５００のオペレーション５４０において、粒子の重みを算出するために用いられる。ビデオのオブジェクトを追尾するために使われるＰＦにおいて、様々なデータとしては、色ヒストグラムデータおよび勾配データ（例えば境界および端）が含まれる。現在のビデオ画像（またはフレーム）の粒子位置のカラー・ヒストグラムが、システムの以前の状態のカラー・ヒストグラムと比較される。更に、勾配データが粒子位置で現在のビデオ画像から集められ、例えば、ボールの一部が粒子位置にあるように見えるか否かが定量的に分析される。色ヒストグラムデータおよび勾配データを考慮することは、複数のキューの融合（fusing  multiple  cues）と呼ばれる。
【００６８】
複数の運動モデルおよび複数のキューの融合は、実施例に組み込まれてもよい。例えば、後述するように、オブジェクトを追尾する実施例は、これらの特長を結合してもよい。
【００６９】
実施例において、「古い」粒子の最初の分布は、白色ガウスまたは一様分布である。最初の粒子重みは、等価なセットである。
動的モデルは、数１３のようにオブジェクト状態ベクトルに依存している。
【００７０】
【数１３】
2010505184.tif 000015
【００７１】
【数１４】
2010505184.tif 000016
【００７２】
【数１５】
2010505184.tif 000017
ここで（ｘ，ｙ）は、オブジェクト・ウィンドウの中心である。数１４は、速度である。数１５は、ウィンドウの拡大縮小速度である。追尾機構を機敏な動作により適格にするために、粒子を２つのグループに分ける。第１の集団の粒子は「ランダムウォーク」モデルで広がる。一方、第二群の粒子は二次の自己回帰モデルによってドリフトする。
【００７３】
各粒子の平均値シフト分析において、ウィンドウサイズは変化しない。したがって、平均値シフトの繰返しは部分的な状態ベクトルにだけ適用される（すなわち、状態がウィンドウサイズおよびウィンドウ位置を含むとみなされる場合であっても、ウィンドウ位置だけが更新される）。一方、計測空間のローカルモードは、物体色のヒストグラムによって表現される。
【００７４】
測定モデルは、色およびエッジ情報の２つのオブジェクト・キューの組合せである。より高い優先度が、色特長に与えられる。これは、色特徴が、モーションブラおよび雑然としたバックグラウンド状況においてロバストである（安定している）ためである。両方の特長の可能性（粒子の重み）は、数１６の通りである。
【００７５】
【数１６】
2010505184.tif 000018
【００７６】
【数１７】
2010505184.tif 000019
【００７７】
【数１８】
2010505184.tif 000020
【００７８】
【数１９】
2010505184.tif 000021
ここで、数１７が成り立ち、数１８は色測定値、数１９はエッジ測定値であり、それぞれ独立であると仮定する。
【００７９】
カラー・ヒストグラムは、オブジェクトの外観をモデル化するために用いる。その距離測定基準は、数２０に等しい。ここで、数２１はバタチャリヤ係数である。したがって、色測定値の可能性は数２２で表される。
【００８０】
【数２０】
2010505184.tif 000022
【００８１】
【数２１】
2010505184.tif 000023
【００８２】
【数２２】
2010505184.tif 000024
エッジの可能性はオブジェクト状態によって定義される楕円周辺のエッジ情報から得られる。以下、この点について詳細に説明する。オブジェクト形状は（例えば、オブジェクトは、ボール、目、ヘッド、手などであり）長方形ウィンドウによってきちんと囲まれた楕円として略モデル化される。そして、これはオブジェクト状態ベクトルによって決定される。この楕円の測定は、エッジ検出によって得られる。これは、各楕円の法線に沿ったK個の一様にサンプルされた楕円ポイントで得られる（例えば、Ｋ＝４８）。Ｓｏｂｅｌ／Ｃａｎｎｙオペレータに基づき、各法線に沿って、最大のエッジ度を有するピクセルが発見される。その法線上の楕円位置からのその距離が記録される。この平均は数２３によって表される。
【００８３】
【数２３】
2010505184.tif 000025
したがって、エッジの可能性は数２４によって計算される。
【００８４】
【数２４】
2010505184.tif 000026
発明の適用事例としては、スポーツビデオにおける対象物のトラッキングが挙げられる。
【００８５】
しかしながら、開示された概念および実施例は動的システムの様々な状態推定問題に適用可能な用途を有する。例えば、自動目標認識、トラッキング、ワイヤレス通信、ガイダンス、ノイズ除去およびファイナンシャルモデリングを含む。特に、非線形および／または非ガウス性を有する（例えば、マルチモーダル分布を有する）システムは、開示された概念および実施例の適用が有益である。
【００８６】
例えば、モジュール１２０−１４０は、別個に、または回路または他のコンポーネントを含む、集積化されたハードウェアユニットで実現できる。加えて、モジュール１２０−１４０は、モジュール１２０−１４０の一つ以上のオペレーションを実行するための一連のインストラクションを実行するように構成される処理装置によって実行されてもよい。同様に、エンコーダ２１０、送信／記憶装置２２０および処理装置３１０は、少なくとも部分的に、そのコンポーネントのオペレーションを実行するための一連の命令を実行するように構成される処理装置によって実行されてもよい。かかる命令は、処理装置内に、または他の記憶装置に格納されてもよい。
【００８７】
本明細書において「接続する（coupled）」は、介在要素なしの直接結合および一つ以上の介在要素による間接的な結合を含む。したがって、一組のデバイスである場合、Ｄ１−Ｄ４がシリアルに接続される場合、デバイスＤ２およびＤ３が介入する場合であっても、Ｄ１およびＤ４は接続される。
【００８８】
本願明細書において記載されているさまざまな方法および特長の実施例は、様々な異なる装置または、特に、アプリケーション（例えば、動画像通信に関連した装置またはアプリケーション）で実施されてもよい。装置の例としては、ビデオ・コーダー、ビデオデコーダ、ビデオ・コーデック、ウェブサーバ、携帯電話、携帯用のデジタル補助装置（ＰＤＡ）、セットトップボックス、ラップトップおよびパーソナル・コンピュータが挙げられる。これらの実施例から明白なように、符号化は様々な経路を通じて送られてもよい。そして、例えば、無線、有線、インターネット、ケーブルテレビのライン、電話回線およびイーサネット（登録商標）接続を含む。加えて、明らかなように、装置は可動性であってもよく、モバイル手段にインストールされてもよい。本願明細書において、１つの態様だけを使用している場合であっても、また特定の態様の参照がなくても、さまざまな態様、実施例および特長が、様々な実装方法で実現されてもよい。例えば、さまざまな態様、実施例および特長は、例えば、以下の一つ以上を使用することで実施されてもよい。（１）方法（またはプロセス）、（２）装置、（３）方法を実行する装置または処理装置、（４）一つ以上の方法を実行するためのプログラムまたは命令セット。（５）プログラムまたは一組の命令を含む装置、および（６）プロセッサで読取り可能な媒体。
【００８９】
コンポーネントまたは装置、例えば状態推定器１１０、エンコーダ２１０、送信／記憶装置２２０および処理装置３１０は、例えば、単独のまたは集積化されたハードウェア、ファームウェアおよび／またはソフトウェアを含んでもよい。例えば、コンポーネントまたは装置は、一般の処理デバイスを指すプロセッサ、マイクロプロセッサ、集積回路またはプログラマブル・ロジック・デバイスを含んでもよい。別の例として、装置は、一つ以上の方法を実行するための命令を有する一つ以上のプロセッサで読取り可能な媒体を含んでもよい。
【００９０】
プロセッサで読取り可能な媒体は、例えば、ソフトウェア・キャリアまたは他の記憶装置、例えばハードディスク、コンパクト・ディスケット、ランダムアクセスメモリ（「ＲＡＭ」）または読取り専用メモリー（「ＲＯＭ」）を含んでもよい。プロセッサで読取り可能な媒体としては、例えば、命令をエンコードまたは送信しているフォーマット化された電磁波を含んでもよい。命令は、例えば、ハードウェア、ファームウェア、ソフトウェア、あるいは電磁波であってもよい。例えば、命令は、オペレーティングシステム、別個のアプリケーション、またはその組み合わせでもよい。したがって、例えば、プロセッサは、方法を実行するように構成される装置、および方法を実行するための命令を有するプロセッサで読取り可能な媒体を含む装置として定義されてもよい。
【００９１】
以上、多くの実施例を記載した。なお、さまざまな修正がなされてもよいことが理解されよう。例えば、異なる実施例の要素は、結合されてもよく、補充されてもよく、修正されてもよく、または、他の実施例を作り出すために取り除かれてもよい。加えて、当業者であれば、他の構造および方法が開示されるものと置換されてもよいと理解する。すなわち、そのようにして生じる実施例が、実施例に開示したものと、実質的に少なくとも同じ機能を有し、少なくとも実質的に同一方法で、かつ実質的に少なくとも同じ結果を導く場合、置換が行われてもよい。したがって、これらおよび他の実施例は、本願に含まれ、かつ、以下の請求項の範囲内にある。
【図１】
2010505184.tif 000027
【図２】
2010505184.tif 000028
【図３】
2010505184.tif 000029
【図４】
2010505184.tif 000030
【図５】
2010505184.tif 000031
【図６】
2010505184.tif 000032
【図７Ａ】
2010505184.tif 000033
【図７Ｂ】
2010505184.tif 000034
【図８Ａ】
2010505184.tif 000035
【図８Ｂ】
2010505184.tif 000036
【図９】
2010505184.tif 000037
【図１０】
2010505184.tif 000038
【手続補正書】
【提出日】平成21年12月11日(2009.12.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
画像内のオブジェクトの位置を推定する際に、粒子ベースのアルゴリズムに使用するために、粒子のセットを提供するステップ；
前記粒子のローカルモードを決定するために、前記粒子のセット内の粒子に、ローカルモード・シーキング・メカニズムを適用するステップ；
前記粒子の前記決定されたローカルモードに基づいて、前記粒子を新しい位置に移動させるステップ；
修正された粒子のセットを生成するために、前記粒子のセットの粒子数を修正するステップ；および
前記修正された粒子のセットで前記粒子ベースのアルゴリズムを使用して、前記画像内の前記オブジェクトの前記位置を推定するステップ；
を有する方法。
【請求項２】
前記粒子ベースのアルゴリズムが、粒子フィルタアルゴリズムを含む、請求項１記載の方法。
【請求項３】
前記ローカルモード・シーキング・メカニズムが平均値シフト分析処理を含む、請求項１記載の方法。
【請求項４】
前記粒子数を修正するステップがＫｕｌｌｂａｃｋ−Ｌｅｉｂｌｅｒ−ｄｉｓｔａｎｃｅ（ＫＬＤ）サンプリング処理を使用するステップを含む、請求項１記載の方法。
【請求項５】
前記ＫＬＤサンプリング処理のビンの数を推定するために、ＫＤ−ツリー構造を使用するステップ、を更に有する、請求項４記載の方法。
【請求項６】
前記ＫＤ−ツリー構造を使用するステップは、ＫＤ−ツリーに粒子を挿入するステップを有し、前記粒子はｎ次元であり、ｎはゼロ以外の整数であり、かつ粒子を挿入するステップは、
所与の粒子の量子化された値を作り出すために、前記所与の粒子を量子化するステップ、
前記所与の粒子を前記ＫＤ−ツリーのノードと関連させることによって、前記ＫＤ−ツリーに前記所与の粒子を挿入するステップ、
異なる粒子の量子化された値を作り出すために、前記異なる粒子を量子化するステップ、
前記所与の粒子の前記量子化された値と前記異なる粒子の前記量子化された値とを比較するステップ、および
前記２つの量子化された値を比較した結果に基づき、前記異なる粒子を捨てるか否かを決定するステップ、
を有する請求項５記載の方法。
【請求項７】
前記異なる粒子を捨てるか否かを決定するステップが、前記異なる粒子の特定の次元の前記量子化された値が前記所与の粒子の前記特定の次元の前記量子化された値と同じである場合、前記異なる粒子を捨てるステップを有する、請求項６記載の方法。
【請求項８】
前記粒子ベースのアルゴリズムは、粒子フィルタアルゴリズムを含み、
前記ローカルモード・シーキング・メカニズムは、平均値シフト分析処理を含み、かつ
前記粒子数を修正するステップは、Ｋｕｌｌｂａｃｋ−Ｌｅｉｂｌｅｒ−ｄｉｓｔａｎｃｅ（ＫＬＤ）サンプリング処理を使用するステップを含む、
請求項１記載の方法。
【請求項９】
前記粒子数を修正するステップは、
前記粒子を移動させるために前記メカニズムを適用した後に実行される、
請求項１記載の方法。
【請求項１０】
前記粒子ベースのアルゴリズムは、粒子フィルタアルゴリズムを含み、かつ
複数のタイプのデータが、前記粒子フィルタアルゴリズムにおける粒子重みを算出するために用いられる、
請求項１記載の方法。
【請求項１１】
前記複数のタイプのデータは、前記画像の色ヒストグラムデータおよび勾配データを含む、
請求項１０記載の方法。
【請求項１２】
前記粒子ベースのアルゴリズムは、粒子フィルタアルゴリズムを含み、かつ
前記粒子フィルタアルゴリズムは、動的モデルを含み、前記粒子フィルタアルゴリズムの所与の繰返しにおいて、前記動的モデルは（１）第１の運動モデルを使用して粒子の第１の部分を更新し、かつ（２）前記第１の運動モデルと異なる第２の運動モデルを使用して粒子の第２の部分を更新する、
請求項１記載の方法。
【請求項１３】
前記粒子フィルタアルゴリズムが、画像の前記オブジェクトを追尾するために用いられ、
前記第１の運動モデルは、ランダムウォーク・モデルを含み、かつ
前記第２の運動モデルは、二次の自己回帰モデルを含む、
請求項１２記載の方法。
【請求項１４】
前記粒子ベースのアルゴリズムは、データの測定を使用する、請求項１記載の方法。
【請求項１５】
前記オブジェクトの前記推定位置をエンコーダに提供するステップ、
第１の符号化アルゴリズムを使用して、前記推定位置に対応する前記画像の一部を、前記エンコーダを用いてエンコードするステップ、および
前記第１の符号化アルゴリズムとは異なる第２の符号化アルゴリズムを使用して、前記推定位置に対応しない前記画像の他の部分を、前記エンコーダを用いてエンコードするステップ、
を更に有する請求項１記載の方法、
【請求項１６】
前記オブジェクトの前記推定位置を処理デバイスに提供するステップ、
前記オブジェクトの強調された表示を可能にするために、前記オブジェクトの前記推定位置を用いて、前記処理デバイスによって、前記画像を修正するステップ、
を更に有する請求項１記載の方法。
【請求項１７】
前記強調された表示は、前記画像の前記オブジェクトをハイライトするステップを含む、請求項１６記載の方法。
【請求項１８】
前記ローカルモード・シーキング・メカニズムを適用する前に、
動的モデルを使用して前記一つ以上の粒子を更新することによって、前記粒子のセットの一つ以上の粒子を移動させるステップ、
を更に有する請求項１記載の方法。
【請求項１９】
前記粒子数を修正するステップの後で、かつ、前記オブジェクトの前記位置を推定するステップの前に、前記粒子のセットをリサンプリングすることによって粒子の前記セットの一つ以上の粒子を移動させるステップ、を更に有する請求項１記載の方法。
【請求項２０】
処理デバイスを有する装置であって：
画像内のオブジェクトの位置を推定する際に、粒子ベースのアルゴリズムに使用するために、粒子のセットを提供し、
前記粒子のローカルモードを決定するために、前記粒子のセット内の粒子に、ローカルモード・シーキング・メカニズムを適用し、
前記粒子の前記決定されたローカルモードに基づいて、前記粒子を新しい位置に移動させ、
修正された粒子のセットを生成するために、前記粒子のセットの粒子数を修正し、かつ
前記修正された粒子のセットで前記粒子ベースのアルゴリズムを使用して、前記画像内のオブジェクトの前記位置を推定する、
ことを特徴とする装置。
【請求項２１】
更に前記処理デバイスは、
前記オブジェクトの前記推定位置を用いて、前記画像内の前記オブジェクトを追尾し、かつ
更に当該装置は、エンコーダを有し、前記エンコーダは、
（１）前記処理デバイスから前記オブジェクトの前記推定位置を受け取り、（２）第１の符号化アルゴリズムを使用して、前記推定位置に対応する前記画像の一部をエンコードし、かつ（３）第２の符号化アルゴリズムを使用して、前記推定位置に対応しない前記画像の他の部分をエンコードすること、
を特徴とする請求項２０記載の装置。
【請求項２２】
更に前記処理デバイスは、
前記オブジェクトの前記推定位置を用いて、前記画像内の前記オブジェクトを追尾し、かつ
更に当該装置は、後処理デバイスを有し、前記後処理デバイスは、
（１）前記処理デバイスから前記オブジェクトの前記推定位置を受け取り、かつ（２）前記オブジェクトの強調された表示を可能にするために、前記オブジェクトの前記推定位置を用いて、前記画像を修正すること、
を特徴とする請求項２０記載の装置。
【請求項２３】
画像内のオブジェクトの位置を推定する際に、粒子ベースのアルゴリズムに使用するために、粒子のセットを提供するための手段；
前記粒子のローカルモードを決定するために、前記粒子のセット内の粒子に、ローカルモード・シーキング・メカニズムを適用するための手段；
前記粒子の前記決定されたローカルモードに基づいて、前記粒子を新しい位置に移動させるための手段；
修正された粒子のセットを生成するために、前記粒子のセットの粒子数を修正するための手段；および
前記修正された粒子のセットで前記粒子ベースのアルゴリズムを使用して、前記画像内の前記オブジェクトの前記位置を推定するための手段、
を有する装置。
【請求項２４】
画像内のオブジェクトの位置を推定する際に、粒子ベースのアルゴリズムに使用するために、粒子のセットを形成するステップ；
前記粒子のローカルモードを決定するために、前記粒子のセット内の粒子に、ローカルモード・シーキング・メカニズムを使用するステップ；
前記粒子の前記決定されたローカルモードに基づいて、前記粒子を新しい位置に移動させるステップ；
修正された粒子のセットを生成するために、前記粒子のセットの粒子数を修正するステップ；および
前記修正された粒子のセットで前記粒子ベースのアルゴリズムを使用して、前記画像内の前記オブジェクトの前記位置を推定するステップ、
を一つ以上の処理デバイスに実行させるための命令を格納した、プロセッサで読取り可能な、媒体を有する装置。
【請求項２５】
前記処理デバイスが一つ以上のエンコーダまたはデコーダに組み込まれている、請求項２０記載の装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
推定された状態１７０が、様々な目的のために使われ得る。更に詳細な内容を提供するために、図２および３にいくつかの応用を示す。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
更に、エンコーダ２１０は、差動的にデータ入力１６０の異なる部分をエンコードするために、推定された状態１７０を使用する。例えば、状態がビデオのオブジェクトの位置を表す場合、エンコーダ２１０は第１の符号化アルゴリズムを使用して推定位置に対応する一部のビデオをエンコードし、かつ第２の符号化アルゴリズムを使用して推定位置に対応しないビデオの他の部分をエンコードしてもよい。第１のアルゴリズムは、第２の符号化アルゴリズムより符号化冗長性を有してもよい。そうすることにより、推定するオブジェクトの（可能性の高い）位置は、ビデオの他の部分よりより詳細で高い解像度によって再生されることが期待される。このようにして、例えば、一般の低解像度の伝送よりは高い解像度を、追尾されるオブジェクトに提供してもよい。そして、例えば、ユーザがよりゴルフマッチのゴルフボールをより楽に見ることができるようにする。このような実施例においては、ユーザが狭いバンド幅（低データ速度）で接続されたモバイル機器上でゴルフマッチを見ることができる。モバイル機器は、例えば、携帯電話またはパーソナル携帯情報機器（ＰＤＡ）でもよい。低いデータ速度でゴルフマッチのビデオをエンコードし、ゴルフボールをエンコードするために追加にビットを使用することによって、データレートは低く保たれる。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００３４
【補正方法】変更
【補正の内容】
【００３４】
通常、リサンプリングは、ＰＦにおける共通の課題である縮退を減らすのに寄与する。リサンプリングには幾つかの方法がある。多項式（multinomial）、残差（residual）、層別化（stratified）、および系統的なリサンプリングである。１つの実施例は、残差のリサンプリングを使用する。残差リサンプリングは粒子順序に影響されない。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００３８
【補正方法】変更
【補正の内容】
【００３８】
平均値シフト・アルゴリズムは、複雑なマルチ・モーダル状態空間の分析のための、および、状態空間の任意に成形されたクラスタを詳細に表現するための一般のノンパラメトリック手法である。平均値シフト・アルゴリズムは、ＰＦにおいて共通の課題である縮退を解決するための方法を提供する。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００５６
【補正方法】変更
【補正の内容】
【００５６】
図９を参照すると、具体例９００は、ＫＤ−ツリーに７個の２次元の粒子を挿入することが示されている。具体例９００は、テーブルを有する９１０。このテーブルは、０と０．９９の間の正規化された値、および、量子化された値を有する７つの粒子を示している。量子化された値は、正規化数にビンの数を乗算し、小数部を切り捨てることによって求まる。あるいは、ビンサイズによって正規化数を割り、小数部を切り捨てることによって求まる。所望のビンの数は５である。これはビンサイズに対応しており、サイズは０．２である（ビンのサイズは同一と仮定）。例えば、他の実施例では、切上げまたは切捨てでもよい。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００５７
【補正方法】変更
【補正の内容】
【００５７】
具体例９００において、ＫＤ−ツリー９２０は７つの量子化された粒子を含んでいることを示している。量子化された粒子は、挿入処理の間、順番に取られる。第１の量子化された粒子は、ＫＤ−ツリー９２０のルートノードに割り当てられる。挿入されるその他の量子化された粒子はｘ座標を有し、ルートノード粒子（３，４）のｘ座標と比較される。比較に基づいて、（１）ｘ座標がより３より小さい場合、次の量子化された粒子はツリーの左に位置し（２）ｘ座標が３よりも大きい場合、ツリーの右に位置する。（３）ｘ座標が３に等しい場合、破棄される。このように、残りの量子化された粒子を挿入する際に、以下の事象が発生する：
・０は３より小さいので、第２の量子化された（０、１）粒子は、ルートノードの左に位置する、すなわちノードＡに割り当てられる。
・第３の量子化された粒子（３、１）は、ルートノードで捨てられる。その理由は、ｘの係数が３であり同数だからである。なお、第３の量子化された粒子が捨てられる場合であっても、我々は第３の量子化された粒子についてＫＤ−ツリーに挿入されたこととする。
・１は３より小さいので、第４の量子化された粒子（１、３）はルートノードの左に位置する。１つの粒子だけがいかなる所与のノードにも割り当てられることになっているので、第４の量子化された粒子は、ノードのＡで、先ほどの第２の量子化された粒子（０、１）と比較されなければならない。ツリーのノードのＡレベルでの比較は、ｙ座標によってなされる。このように、３が１より大きいため、第４の量子化された粒子はノードのＡの右のノードＣに置かれる。ノードＣとの比較は、ツリーのこのレベルの他のいかなるノードもｘ座標に関してなされる。ＫＤ−ツリー９２０において、ノードと関連する粒子は、そのノードで比較される１つの座標を示すために下線を引いて示される。例えば、ルートノードで粒子（３、４）の３が下線を引かれる。
・４は３よりも大であるので、第５の量子化された粒子（４、２）はルートノードの右のノードのＢに置かれる。
・２が３より小さいので、第６の量子化された粒子（２、２）はルートノードの左に行き、２が１より大きいのでノードのＡの右に行き、かつ、２が１より大であるのでノードのＣの右に行き、ノードのＤに割り当てられる。
・１が３より小さいので、第７の量子化された粒子（１、３）はルートノードの左に行き、３が１より大であるのでノードのＡの右に行き、かつ、ノードＣで１が１に等しいので破棄される。
【国際調査報告】
2010505184.tif 000039
2010505184.tif 000040
2010505184.tif 000041
2010505184.tif 000042
2010505184.tif 000043
2010505184.tif 000044