コンピュータビジョン特論 第８回対象追跡 ２００６年１１月２２日 加藤丈和 対象追跡とは（検出と追跡） • 検出：一枚の画像から指定した条件をみたす 画像領域を抜き出す処理 • 追跡：動画像から指定した領域を抜き出し、 フレーム間で対応づける処理 • 追跡の分類 – 対象の表現（モデル）による分類 – 類似性尺度による分類 – 探索方法による分類 色ヒストグラムによる追跡 Mean Shift法 • 対象領域内のヒストグラムを計算 対象モデル u番目の色の割合 モデルヒストグラム 入力ヒストグラム ポジション 色ヒストグラムによる追跡 Mean Shift法 類似度 yˆ arg max ˆ (y ) y ヒストグラムによる追跡 Mean Shift法 重み付きヒストグラム u番目のbinの値 1 if i 0 [i ] 0 otherwisex 領域の中心を重視 変形に強い b(x) : xの場所の色（何番目の binの色か） k (d ) : 中心に近いほど大きい 値をとる微分可能な重 み関数 カーネル関数 ｋ（ｄ） ｄ Mean Shift 入力画像のヒストグラムも同様に定義 xi y hはスケール h Mean Shift バタッチャリア係数をテイラー展開（１次の項まで） 前のフレームの位置 重み付きヒストグラムの式を第二項に代入 定数 Mean Shift 第二項を最大化→微分＝０より カーネル関数の微分 Mean Shift ヒストグラムの比 特に とすると １ 微分が定数 ヒストグラムの比 ヒストグラムの比を重みとして、領域内の重心を求める まとめ • モデルの表現と類似性尺度 • 勾配法に基づく探索 • 見えに基づく追跡 – →Lucas Kanade法 • 色ヒストグラムによる追跡 – →Mean Shift法 運動予測に基づく追跡 パーティクルフィルタとその 実装 勾配に基づく追跡の問題点 • 対象の動きに関する知識を利用しない • 初期値（前フレームの結果）が十分解 に近い必要がある • 類似度が解周辺でなめらか（微分可 能）である必要がある • ノイズの影響を受けやすい 類似度 状態 動きと観測のモデル 推定→ x t 状態ベクトル（時刻tの対象の状態、観測できない） yt 観測ベクトル（実際に観測される値） 観測モデル システムモデル xt Ft xt 1 , v t y t H t xt , w t v t : システムノイズ w：観測ノイズ t py t | xt pxt | xt 1 観測できる y1 y2 yt 観測モデル 観測できない x0 xt x1 x2 システムモデル pxt | xt 1 py t | xt 観測ベクトルから観測できない状態ベクトルを推定 状態の推定 観測できる y1 y2 yt 観測モデル 観測できない x0 xt x1 x2 システムモデル pxt | xt 1 py t | xt Yt y1 , y 2 ,, y t という観測が得られたときに x t が何であったかを推定する問題 ただし x はマルコフ性を満たす pxt | X t 1 pxt | xt 1 t X t x1 , x2 ,, xt x t の期待値 xˆ t x t | Yt x t px t | Yt dx t pxt | Yt : Ytという観測が得られた とき xtの状態だった確率 事後確率 線形システムの状態推定 Kalman filter • 線形システム – システムプロセス、観測プロセスが線形 – ガウシアン分布 xt Ft xt 1 , vt y t Ht xt , wt ガウシアン分布 xt Fx t 1 Gvt v t～N (0, Qt ) y t Hxt w t w t～N (0, R t ) pxt | xt 1 N Fx t 1, GQtGT py t | xt N Hxt , Rt xˆ t x t | Yt x t px t | Yt dx t 正規分布 Qt : vtの共分散 R t : w tの共分散 線形システムの状態推定 Kalman filter pxt | xt 1 N Fx t 1, GQtGT py t | xt N Hxt , Rt 線形システム、ガウシアン分布no場合 線形解が求まる（導出は省略） Kalman filter 推定量 期待値 予測 xˆ t|t xˆ t|t 1 K t y t Hxt|t 1 xの共分散 Pt|t Pt |t 1 K t HPt|t 1 K t Pt|t 1H HPt|t 1H R t 1 T カルマンゲイン T 一つ前の推定量 xˆ t |t 1 Fxˆ t 1|t 1 1 Pt |t 1 FPt 1|t 1F T GQt 1G Kalman filter を用いた追跡の例 α-β（-γ）tracker P.R. Kalata 1986 • 慣性を持つ剛体の運動予測のモデル xt 1 Fx t Gv y t Hxt w 運動方程式 2 1 1 t t x t 2 xt xt F 0 1 t 0 0 1 x t 1 2 位置 xt 1 xt txt t xt v1 2 速度 xt 1 xt txt v2 加速度 xt 1 xt v3 画像上の対象追跡では2次元に拡張 1 H 0 0 yt xt w 位置が観測 Kalman filterを用いた追跡の例 • 複数ターゲットの追跡 ICIS２００３ W. Niuら F 背景差分 xˆ t|t yt xˆ t 1|t 1 xˆ t|t 1 Pt|t 1 t-1 ノイズ 予測 t 近いほうを観測値にする Pt|t 推定値（ろ波） Kalman filterを用いた追跡の例 • アフィン変換による変形を含む追跡 – ICCV98(Jebara, Russel and Pentland)など – 対象表現：特徴点集合、アフィン行列 • 剛体の3次元位置、姿勢の追跡 – VISP97（Jung and Wohn)など – 対象表現：特徴点集合、3次元位置、姿勢 • 予測を使って、テンプレートの探索範囲を限定 – ISIE03（G. CAOら）など – 対象表現：テンプレート、位置、速度 Kalman filter の利点と欠点 • 利点 – 線形解が与えられる（計算コスト小） – 次のフレームの予測ができる – 観測ノイズ、システムノイズを吸収できる • 欠点 – 強い制約条件 • システムプロセス、観測プロセスが線形 • ガウシアン分布 – 適用範囲が限られる • ＣＶ分野では限定的な利用 – 検出結果のフレーム間対応付け – ノイズの吸収、スムージング – 探索範囲の限定 Particle Filter • システムプロセス、観測プロセスを非線形に拡張 – Kalman filter のような制約がない – 非ガウシアンの分布を表現 • ランダムサンプリングによる仮説の生成と、各仮説 の尤度推定によって、事後分布を推定(モンテカル ロ近似) • Monte Carlo Filter(北川ら、1995), Bootstrap Filter(Gordon,1996), ConDensation(Isardら、1998) とも呼ばれるが基本的に同じ • その後 Particle Filter(粒子フィルタ)という呼び名に 落ち着く – ただし、ＣＶ分野ではConDensationと呼ばれることも多 動きと観測のモデル 観測モデル システムモデル xt Ft xt 1 , v t y t H t xt , w t v t : システムノイズ w：観測ノイズ t py t | xt pxt | xt 1 観測できる y1 y2 yt 観測モデル 観測できない x0 x t の期待値 pxt | xt 1 xt x1 x2 システムモデル pxt | xt 1 xˆ t x t | Yt x t px t | Yt dx t py t | xt Yt y1 , y 2 ,, y t py t | xt が既知で観測 Yt が与えられたとき pxt | Yt を推定 事後確率 Particle Filter 観測できる y1 y2 yt 観測モデル 観測できない x0 xt x1 x2 システムモデル pxt | xt 1 py t | xt 事後確率 px t , y t , Yt 1 ベイズの定理より px t | Yt px t | y t , Yt 1 py t , Yt 1 py t | x t , Yt 1 px t , Yt 1 py t | x t , Yt 1 px t | Yt 1 pYt 1 py t , Yt 1 py t , Yt 1 py t | x t , Yt 1 px t | Yt 1 py t | x t , Yt 1 px t | Yt 1 py t , Yt 1 py t | Yt 1 pYt 1 ベイズの定理 py t | x t px t | Yt 1 K t py t | x t px t | Yt 1 py t | Yt 1 pa, b p(a) p(b | a) p(b) p(a | b) Particle Filter の枠組み 事後確率 py t | x t px t | Yt1 px t | Yt py t | Yt1 尤度 観測モデル 事前確率 （前フレーム からの予測） pxt | Yt 1 pxt , xt 1 | Yt 1 dxt 1 pxt | xt 1 , Yt 1 pxt 1 | Yt 1 dxt 1 pxt | xt 1 pxt 1 | Yt 1 dxt 1 状態遷移確率 システムモデル 前フレームの 事後確率 事後分布の推定＝システムモデルによって予測しながら、 フレームごとに尤度を求める ただし、状態空間全体を推定することはできない。 →ランダムサンプリングにより近似 Particle Filter の枠組み py t | x t px t | Yt1 px t | Yt py t | Yt1 px t | Yt 1 px t | x t 1 px t 1 | Yt 1 dx t 1 これを連続な状態空間全体で求めるのは非現実的 サンプル集合 St|t s , s ,, s (1) ( 2) t|t t|t (1) ( 2) t|t 1 t|t 1 St|t 1 s ,s (N) t|t (N) t|t 1 ,, s st(|it)～pxt | Yt s ～pxt | Yt 1 1 N pxt | Yt xt st(|it) N i 0 1 pxt | Yt 1 N x N i 0 N→∞で一致する t を用いて離散近似 (i ) t|t 1 s (i ) t |t 1 1 N (i ) xˆ E xt | Yt s t|t N i 0 ディラックデルタ関数 0 x x dx 1 ifx 0 otherwise Particle Filter (1) ( 2) (N) どうやって St|t st(1|t) , st(|2t ) ,, st(|Nt ) St|t 1 st|t 1, st|t 1,, st|t 1 を pxt | Yt pxt | Yt 1 に従って発生させるか p xt 1 | xt st(i )1|t 1 St(i1)|t 1 s t(|it)1～p xt 1 | xt s t(i )1|t 1 ①Fに従って変化させる s t(|it)1 F s t(i )1|t 1 , v St(|ti ) 1 ②尤度＝重みを計算 (i ) t p y t | xt st(|it)1 py N j 1 (i ) N t i 1 ③重みの比に従って選択 St(|ti ) 消滅 消滅 消滅 消滅 t | xt st(|tj) 1 Particle Filter 事後分布 を事前分布 に従って生成したサンプル と各サンプルの尤度 の組で表現 の比に従って選択 に従って更新 尤度 を計算 The Condensation Algorithm home page (Bob Fisher)より サンプルコードが公開されている Particle filterを用いた追跡の例 • ConDensation （IJCV98 M. Isard and A. Blake） • 対象表現：輪郭モデル • 類似度(尤度）：エッジと輪郭の距離 – 照明変化、色の変化に強い – 裾野が広く、滑らかな尤度分布 スプラインモデル x p1 , p 2 ,, p M p2 楕円モデル ２Ｍ次元 x x, y, , , p3 θ α p4 p2 p5 p1 5次元 β (x,y) Particle filterを用いた追跡の例 輪郭からエッジ点までの距離 p(y t | xt st(|it) ) p(z | x) z The Condensation algorithm home pageより Monte Carlo Filterを用いた追跡の利点と欠 点 • 利点 – システムプロセス、観測プロセスが任 意 • あるサンプルに対する尤度が定義でき れば基本的になんでもいい 尤度 – 非ガウシアン分布を表現可能 – 多重仮説 – 尤度分布が局所的に滑らかでなくても いい 状態 • 欠点 – 状態ベクトルが高次元になると計算量 が増加 • 多数のサンプリングが必要 尤度 – 複数ターゲットへの拡張が難しい – 尤度分布の裾野が狭いと不安定になる 状態 まとめ • 動き予測に基づく探索 – 過去のフレームから次の位置を予測 • 線形システム→カルマンフィルタ – 線形に解がもとまる – 制限が大きい • 非線形に拡張→Particle Filter – ランダムサンプリングによる推定
© Copyright 2024 ExpyDoc
