凝縮アルゴリズム

凝縮アルゴリズム（条件付き密度伝播）は、コンピュータビジョンアルゴリズムです。主な用途は、混雑した環境で移動する物体の輪郭を検出および追跡することです。物体追跡は、コンピュータビジョンの中でも最も基本的かつ難しい側面の1つであり、一般的に物体認識の前提条件となります。画像内のどのピクセルが物体の輪郭を構成しているかを識別することは、容易ではない問題です。凝縮は、この問題を解決しようとする確率的アルゴリズムです。

アルゴリズム自体は、IsardとBlakeが1998年にInternational Journal of Computer Visionに掲載した論文で詳細に説明されている。 ^{[ 1 ]}このアルゴリズムの最も興味深い側面の1つは、画像のすべてのピクセルに対して計算を行わないことである。むしろ、処理するピクセルはランダムに選択され、ピクセルのサブセットのみが最終的に処理される。このアプローチの確率的な性質により、何が動いているかについての複数の仮説が自然にサポートされる。評価関数は、主にこの分野の以前の研究から来ており、多くの標準的な統計的手法が含まれている。この研究の独創的な部分は、パーティクルフィルタ推定技術の適用である。

このアルゴリズムは、背景ノイズが多い状況下ではカルマンフィルタが物体追跡をうまく行えないという問題意識から着想を得て開発されました。ノイズが存在すると、物体の状態に関する確率分布が多峰性になり、カルマンフィルタでは適切にモデル化できない傾向があります。最も一般的な形式の凝縮アルゴリズムは、物体や測定値の確率分布に関する仮定を一切必要としません。

凝縮アルゴリズムは、ベクトルで記述されるオブジェクトのコンフォメーションを推定する問題を解決することを目的としている。${\displaystyle \mathbf {x_{t}} }$その時${\displaystyle t}$観察結果に基づくと${\displaystyle \mathbf {z_{1},...,z_{t}} }$検出された特徴のうち、現在時刻までの画像における特徴量。アルゴリズムは、状態 条件付き確率密度の推定値を出力します。${\displaystyle p(\mathbf {x_{t}} |\mathbf {z_{1},...,z_{t}} )}$因数分解サンプリングに基づく非線形フィルタを 適用することにより、モンテカルロ法の発展形と考えることができる。^{[ 1 ]}${\displaystyle p(\mathbf {x_{t}} |\mathbf {z_{1},...,z_{t}} )}$これは、過去のコンフォメーションと測定に基づいて、オブジェクトの可能なコンフォメーションの確率を表すものです。凝縮アルゴリズムは、オブジェクトと観察者の同時分布をモデル化するため、生成モデルです^{[ 2 ] 。}

現在の時点におけるオブジェクトの条件付き密度${\displaystyle p(\mathbf {x_{t}} |\mathbf {z_{1},...,z_{t}} )}$加重された時間インデックス付きサンプルセットとして推定される${\displaystyle \{s_{t}^{(n)},n=1,...,N\}}$重み付き$\displaystyle \pi _{t}^{(n)}}$N は、選択されるサンプル セットの数を決定するパラメータです。${\displaystyle p(\mathbf {x_{t}} |\mathbf {z_{1},...,z_{t}} )}$集合から復元抽出によって得られる。$s_t$対応する要素に等しい確率で$\displaystyle \pi _{t}}$[ ^{1 ]​}

オブジェクトのダイナミクスが時間的マルコフ連鎖を形成するという仮定と、観測が互いに 独立しており、ダイナミクスも独立しているという仮定は、凝縮アルゴリズムの実装を容易にする。最初の仮定により、オブジェクトのダイナミクスは条件付き密度によって完全に決定される。${\displaystyle p(\mathbf {x_{t}} |\mathbf {x_{t-1}} )}$システムダイナミクスのモデルは、${\displaystyle p(\mathbf {x_{t}} |\mathbf {x_{t-1}} )}$アルゴリズムのために選択する必要のある要素も含まれ、一般的には決定論的ダイナミクスと確率的ダイナミクスの両方が含まれます。

このアルゴリズムは、時刻における初期化によって要約できます。${\displaystyle t=0}$そして各時刻tで 3 つのステップがあります。

物体追跡はリアルタイムの目標となる可能性があるため、アルゴリズムの効率性を考慮することが重要になります。凝縮アルゴリズムは、カルマンフィルタリングに必要なリカッティ方程式の計算量と比較すると比較的単純です。パラメータ${\displaystyle N}$サンプルセット内のサンプル数を決定する要素は、効率性とパフォーマンスのトレードオフを明らかに抱えることになる。

アルゴリズムの効率を高める方法の一つは、物体の形状を表すモデルとして自由度の低いモデルを選択することである。Isard 1998 が用いたモデルは、B スプラインの線形パラメータ化であり、スプラインは特定の構成に限定されている。適切な構成は、複数の視点からの輪郭の組み合わせ、異なる姿勢の物体、および変形する物体に対する主成分分析(PCA)によって解析的に決定された。

イサードとブレイクは物体のダイナミクスをモデル化する${\displaystyle p(\mathbf {x_{t}} |\mathbf {x_{t-1}} )}$決定論的要素と確率的要素を含む2階差分方程式として表す。${\displaystyle p(\mathbf {x_{t}} |\mathbf {x_{t-1}} )\propto e^{-{\frac {1}{2}}||B^{-1}((\mathbf {x_{t}} -\mathbf {\bar {x}} )-A(\mathbf {x_{t-1}} -\mathbf {\bar {x}} ))||^{2})}}$

どこ${\displaystyle \mathbf {\bar {x}} }$は州の平均値であり、${\displaystyle A}$、${\displaystyle B}$これらはそれぞれ、動的モデルの決定論的要素と確率的要素を表す行列である。${\displaystyle A}$、${\displaystyle B}$、 そして${\displaystyle \mathbf {\bar {x}} }$物体が典型的な動きをしている間に、最尤推定によって推定される。 ^{[ 1 ] [ 3 ]}

観測モデル${\displaystyle p(\mathbf {z} |\mathbf {x} )}$データから直接推定することはできないため、推定するには仮定を置く必要がある。Isard (1998) は、対象物を見えなくする可能性のある雑音は空間密度を持つポアソンランダム過程であると仮定している。${\displaystyle \lambda }$また、真の目標測定値は偏りがなく、標準偏差を持つ正規分布に従う。${\displaystyle \sigma }$。

基本的な凝縮アルゴリズムは、単一のオブジェクトを時間的に追跡するために使用されます。単一の確率分布を使用して複数のオブジェクトの可能性のある状態を記述する凝縮アルゴリズムを拡張して、シーン内の複数のオブジェクトを同時に追跡することが可能です。^{[ 4 ]}

クラッターによって物体の確率分布が複数のピークに分裂する可能性があるため、各ピークは物体の構成に関する仮説を表します。スムージングは​​、追跡が完了した後に過去と未来の測定値の両方に基づいて分布を調整し、複数のピークの影響を軽減する統計的手法です。^{[ 5 ]} スムージングは​​未来の測定値の情報が必要なため、リアルタイムで直接行うことはできません。

このアルゴリズムは、移動ロボットの視覚ベースのロボット位置推定に使用できます。^{[ 6 ]} ただし、シーン内のオブジェクトの位置を追跡する代わりに、カメラプラットフォームの位置が追跡されます。これにより、環境の視覚マップが与えられた場合に、カメラプラットフォームをグローバルに位置推定できます。

凝縮アルゴリズムの拡張は、画像シーケンス内の人間のジェスチャーを認識するためにも使用されています。この凝縮アルゴリズムの応用は、人間とコンピュータのインタラクションの可能性の範囲に影響を与えます。ホワイトボード上でのユーザーの単純なジェスチャーを認識して、ボードの領域を選択して印刷または保存するなどのアクションを制御するために使用されています。^{[ 7 ]} また、同じシーン内の複数の車を追跡するために他の拡張も使用されています。^{[ 8 ]}

凝縮アルゴリズムは、ビデオシーケンス内の顔認識にも使用されています。 ^{[ 9 ]}

凝縮アルゴリズムのC言語による実装は、Michael Isard氏のウェブサイトで見つけることができます。

MATLABによる実装は、MathWorks File Exchangeで入手できます。

OpenCVライブラリを使用した実装例は、OpenCVフォーラムで見つけることができます。

• パーティクルフィルタ- 凝縮は、輪郭追跡にサンプリング重要度再サンプリング（SIR）推定を適用するものである。