6.パーティクルフィルタ

コンデンセーションやモンテカルロ。フィルタとも呼ばれることがあるパーティクルフィルタは逐次追跡可能なアルゴリズム。

、つまり追跡の終点をあらかじめ必要としない動画像中において物体の追跡・検出を行うことのできるアルゴリズムでリアルタイム処理ができるほど計算が軽い、そしてオクルージョンにも頑健であり、用いる状態方程式も線形である必要がないといういいことずくめのアルゴリズム。
他にも特徴としておもに画像処理で用いられ、シミュレーションにモンテカルロ法を用いてるというのがある。

物体認識、物体検出の分野において物体を追跡するための方法としてはテンプレートマッチング、背景差分なども考え方的にはとてもわかりやすいし学校の授業でも出てくる。しかしそれらの研究を経て簡単だよ！と生み出されたパーティクルフィルタの理解は一介の馬鹿学生である私にはとても高度であるので、できる限りわかりやすく文章に残したい。

まずこのアルゴリズムが動画中においてどういった仕組みで物体検出しているかについて考える。

まずはMISTさんページから
http://mist.suenaga.cse.nagoya-u.ac.jp/trac/wiki/Tutorial/Practice0

「パーティクルフィルタは、現状態から起こりうる多数の次状態を、多数（数百or数千）のパーティクル（粒子）に見立て、全パーティクルの尤度に基づいた重みつき平均を次状態として予測しながら追跡を行っていくアルゴリズムです。」

わかるかっ！！( 'д'⊂彡☆))Д´) ﾊﾟｰﾝ

ってことで実際の処理を見ながら解説。
↓処理の流れ↓
１.パーティクル(粒子)の初期化
名前にもついてるパーティクル(粒子)を用います。映像内において重みと状態量をもった、つまり特定地点において何かしらの評価される値をもった粒子を配置させる。
最初は粒子を一様に分布させる。

２．予測
次の状態を予測する、最初に意味が分かんなくなるのはこの部分だと思う。
「各粒子において前状態から現状態を予測する。」とうのが理論らしいが、自分的な解釈としては

「ばらまいた粒子からどっちに移動するか予測するぜ、その時にそれぞれどっちの方向に行けばいいのか分かんないので、前状態の情報を用いて移動方向に対して尤度(もっともらしい値)を計算する、この尤度の高い方向、もっとも移動するんじゃねぇかって方向に粒子を移動させる。これでとりあえず次状態を予測するサンプルが作れる。」

そんなかんじ

３．尤度計算、重み付け
移動させた粒子においてそれぞれが求めるものに近いかを、もっともらしいかを計算する。つまりは尤度関数を用いて尤度を計算する、この時に尤度が高いことを距離が近いとか表現することもあるそれはユーグリッド距離のような手法を用いて尤度計算をしているからだと思う。
ほかにも手法はいろいろある、ヒストグラムの近さを求めたり画素の分布で考えたり、けどとりあえずその粒子が検出対象に近いかどうか考えてるんだと思う。

４．対象推定
そうして求めた尤度に対して重み付き平均を求める。

＊重み付き平均
一般的なデータの総和/データの個数で求まるような算術平均、相加平均とはちがいそれぞれのデータの重み(それぞれの持つ個数とか意味)を考慮してる。
詳しくはリンクで
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q129394592

ここではさっきの尤度を重みとして平均を求める。これによってどの部分が物体中心かを求める。これで検出対象をユーザー側にも見やすくできるね

５.フィルタ
重みの大きい粒子位置に粒子を増やし、重みの小さい粒子は消す。
これによって検出物体に粒子が集まる。

６.1〜5を繰り返す。

以上だ。

やっぱわかんねぇ！！( 'д'⊂彡☆))Д´) ﾊﾟｰﾝ

ってことでまとめ

「パーティクルフィルタは映像内に粒子をばら撒いてそれぞれが検出対象に近いかを尤度で判断する、それで尤度の高い場所に検出対象があるだろうと予測、粒子を集中させて検出対象を追い続ける。このときの尤度の求め方、状態量のとり方、運動モデルの設定の仕方によってさまざまなオリジナリティあふれる方法が考えられちゃう！！」
みたいなものだと思って自己完結。

最後に問題点だけ

＊リサンプリングを繰り返していくと制度が著しく低下することがある。し　かし十分多くの粒子数をとることで回避できる。
＊高次元の、自由度の高いシステムモデルを扱うのは難しいらしい。
＊簡単！！とかどこも書いてあったけどぜんぜん難しい、初心者には厳しい

以上。
プログラムはソースいろいろ落ちてるしOpenCVにもあったと思うのでそちらで動かしてみると楽しいと思う。

参考にさせていただいたサイト
http://daweb.ism.ac.jp/koza/koza2008/PF_Nakano20081030.pdf
http://mist.suenaga.cse.nagoya-u.ac.jp/trac/wiki/Tutorial/Practice0