第五回研究会議事録
第五回目の研究会は，2月24日，千葉商科大学にて開催されました．今回の参加人数は，途中参加含めて計9名の方が参加してくれました．
今回の議題は「途切れた軌跡の結合について」をみなさんで討論しました．このテーマは，帷子や鈴木（東大）の現在の研究内容なのですが，レーザスキャナによって人物追跡を行う場合，追跡の失敗が起こると軌跡が途中で切れてしまい，数秒後に再び出てきたときには誰がどの軌跡に対応しているか分からなくなります（そういう断片的な軌跡がいくつもあるという状況です）．
ここで軌跡データというのは，位置と時刻を記録した時系列データで，当然速度や移動方向も副次的に計算できます．こういった情報を基に，断片的な軌跡に対して，どの軌跡とどの軌跡を繋げると最も同一人物として最尤の組み合わせになるか？という問題について，皆さんと考えてみました．
結合コストの計算方法について(by宮田＠千葉商科大)
軌跡接合の組み合わせ最適化を解くために，まず断片軌跡同士の「結合コスト」を計算し，これが全体として最小化される組み合わせを考えればよい．そのためには，どのように結合コストを計算するかが重要．
結合コストに物理的意味を持たせる
軌跡が途切れる前と後を滑らかに繋ぐ3次関数を考えてみる．
位置ベクトル P(t)=(x(t),y(t)) とすると，
P(t) = a0 + a1・t + a2・t^2 + a3・t^3
ここで，軌跡が切れた瞬間の位置，速度ベクトルをそれぞれ P(t0), P'(t0) とし，軌跡が現れた瞬間の位置，速度ベクトルをそれぞれ P(t1), P'(t1) とする．これらの条件から，3次関数 P(t) の各パラメータ a0, a1, a2, a3を求める．
次に，軌跡接合の物理的意味を考えてみると，接合に要するエネルギーを定義することにより，全軌跡を接合するためのエネルギーを最小化させるような組み合わせを考えれば良い．物体に与えられる力は，F = m・a で表される．mは質量で，aは加速度である．ここで質量は一定と仮定すると，力Fは加速度，すなわち位置 P(t) の2階微分で表される．
F(t) = P''(t)
また，物体に与えられるエネルギー（仕事量）は，力と距離の内積 E = F・d によって表される．Fが時刻と共に変化する場合，エネルギーは力Fを軌跡が切れた時間t0から現れた時間t1まで積分すれば良い．
E = ∫|F(t)・ds|
ここでdsは微小距離である．絶対値が付くのは，3次関数の変動が激しいと，仕事をする時間（正の値）とされる時間（負の値）が現れる可能性があるからである．
また，F(t)=P''(t)，ds=P'(t)dt であるので，上式は
E = ∫|P''(t)・P'(t)|dt
と書き換えられる．これを時刻t0からt1まで数値積分することにより，軌跡接合に要するエネルギーを計算することができる．
また，もっと簡便な方法として，軌跡が切れた瞬間の加速度をa1，現れた瞬間の加速度をa2とし，その間の距離をdistすると，
cost = ( a1 + a2 ) * dist
としても，エネルギー的な意味合いもあるので，良いかもしれない．
モンテカルロ・フィルタについて(by帷子＠東大)
最近のコンピュータビジョンなどの分野でかなり流行っている「モンテカルロ・フィルタ」というアルゴリズムについて，簡単に紹介しました．これも応用範囲が広いアルゴリズムだと思います．
時系列データの将来予測や平滑化のためのアルゴリズムとして，カルマンフィルタが有名であるが，カルマンフィルタは「線形・ガウス型」の時系列データしか扱えなかった．すなわち，確率構造が時間と共に複雑に変動する時系列データには適していない．
モンテカルロ・フィルタは，様々な分野で発展してきたアルゴリズムで，分野によっていくつかの呼び名が存在する．
- パーティクルフィルタ
- MCMC（マルコフ連鎖モンテカルロ）
- CONDENSATION
- 逐次モンテカルロ法
などなど．特徴としては，多数の「粒子」で確率密度分布を近似するという点で，「非線形・非ガウス型」の複雑な分布でも表現することができる．また，観測データに外れ値を含むような場合にも比較的ロバストに計算できる．精度と計算量のトレードオフは，粒子の数によって調整できる（最低でも数百は必要と思われる）．昔はコンピュータの性能的に計算が困難とされてきたが，近年のPCの高速化に伴い，発達してきた．しかし，複数の対象を同時に追跡するというのはまだ難しく，そのような問題を解決するための論文を最近よく見かける．
アルゴリズム的には，GA（遺伝的アルゴリズム）に非常によく似ているが，GAは最適解を求めるのが目的なのに対し，モンテカルロ・フィルタは真の確率密度分布を推定することが目的なのが大きな違いである．
応用例：
- 天気の数値予報
- 経済時系列の予測
- 欠損値の補間
- 物体追跡（GPSなど）
最終更新：2007年03月26日 11:41
