物体追跡技術について 物体追跡とは:

物体追跡技術について!
物体追跡とは"!
•  指定した対象が画像上でどこにいるかを推定する問題!
•  物体追跡方法!
–  逐次処理!
•  対象が次フレームでどのように変化したかを順方向に探索!
–  一括処理!
•  動画像全体を用いて順方向と逆方向から最適化
逐次処理による物体追跡法"!
•  領域ベースの物体追跡手法!
–  更新テンプレートマッチング，アクティブ探索!
–  #$%&'()*+法,!-%./01$!2*13$.!
–  オンライン学習!
•  特徴点ベースの物体追跡手法!
–  456法!
–  7892!6.%0:*&;
逐次処理による物体追跡法"!
•  領域ベースの物体追跡手法!
–  更新テンプレートマッチング，アクティブ探索!
–  #$%&'()*+法,!-%./01$!2*13$.!
–  オンライン学習!
•  特徴点ベースの物体追跡手法!
–  456法!
–  7892!6.%0:*&;
領域ベースの物体追跡手法"!
逐次処理による物体追跡法"!
•  領域ベースの物体追跡手法!
–  更新テンプレートマッチング，アクティブ探索!
–  #$%&'()*+法,!-%./01$!2*13$.!
–  オンライン学習!
•  特徴点ベースの物体追跡手法!
–  456法!
–  7892!6.%0:*&;
テンプレートマッチング"!6$<=1%3$!<%30)*&;!
•  予め用意したテンプレートと入力画像とのマッチング!
–  テンプレートと画像の類似計算!
–  テンプレートの更新!
–  探索回数の減少
テンプレート
入力画像
類似度の計算"!!
•  テンプレートと画像の類似計算!
–  77>!?7@<!AB!7C@%.$!>*D$.$&0$：類似度E!
–  7F>!?7@<!AB!FG(A1@3$!>*D$.$&0$：相違度E!
：入力画像
：テンプレート画像
類似度の計算"!!
•  正規化相互相関!HII!?HA.<%1*J$K!0.A(('0A.$1%/A&E!
テンプレートの更新"!!
•  対象物の見えは時間と共に変化する!
–  テンプレートを適応的に更新
入力画像
更新
テンプレート
更新テンプレートとの比較"!!
更新した
テンプレート
初期
テンプレート
テンプレートの更新あり
テンプレートの更新なし
高速化"!!
•  テンプレートの全探索における高速化!
–  残差逐次検定法!
LM 初期探索位置におけるテンプレートの類似度77>を!
初期しきい値とする!6)N77>L!
OM 次の探索位置での類似度77>*を計算!
–  77>*!P!6)Q 次の探索位置に移動!
RM テンプレート全体に類似度が計算できれば!
–  6)!N!77>*!Q 次の探索位置に移動
疎密探索法による高速化"!!
•  疎密探索法!
–  S画素に対する平均をL画素に置き換え解像度を下げた画像を生成!
–  低解像度画像から順に探索!
–  １段階低い解像度での結果により探索範囲を限定
32 32
64 64
128 128
逐次処理による物体追跡法"!
•  領域ベースの物体追跡手法!
–  更新テンプレートマッチング，アクティブ探索!
–  #$%&'()*+法,!-%./01$!2*13$.!
–  オンライン学習!
•  特徴点ベースの物体追跡手法!
–  456法!
–  7892!6.%0:*&;
#$%&'7)*+法"!!
•  カラーヒストグラム特徴による追跡!
–  ある関数B?TEの初期値周辺のある区間での傾きを求め，求めた
傾きでB?TEの値が大きくなる方向へ区間の中心を移動させ，初
期値周辺でB?TEが極大となる位置を求める方法
Mean-Shift Vector
#$%&'()*+の特徴"!!
•  カラーヒストグラムベースの追跡手法!
–  局所的な探索によるトラッキングが可能!
–  ピクセル分布の特徴を元に探索するため，様々な形状の物
体をトラッキング可能!
–  部分的なオクルージョンや混雑状態，カメラの位置変化に対
して頑健
カラーヒストグラムの特徴量"!!
•  ウインドウ内の特徴量!
–  9UVそれぞれの１次元正規化カラーヒストグラムを計算
初期ウインドウの正規化
カラーヒストグラム
位置xにおけるウインドウの
正規化カラーヒストグラム
重みの計算"!!
初期ウインドウの
正規化カラーヒストグラム
各位置iにおける
重みを計算
初期フレーム
位置X
位置Xにおける
正規化カラーヒストグラム
現在のフレーム
重みの計算"!!
初期ウインドウの
正規化カラーヒストグラム
各位置iにおける
重みを計算
初期フレーム
位置X
位置Xにおける
正規化カラーヒストグラム
現在のフレーム
移動量の計算"!!
•  9UVカラーヒストグラム重みの統合!
•  #$%&'7)*+移動量!?#$%&'7)*+ベクトル）の計算
重み
求めたウィンドウ位置周辺の重み分布を基に、ウ
ィンドウの移動量Δxを求める
トラッキング手順"!!
LM  Lフレーム前に求められたウィンドウ位置TWを中心とした正規化カラー!
ヒストグラム特長K?TWEを求める!
OM  ウィンドウ内およびその周辺の各ピクセルの重みX*を求める!
RM  移動量YTを計算し，移動先の位置TL!N!TW!Z!YTを求める!
SM  このとき、移動量YT!N!TL!'!TWが予め設定しておいた[よりも大きい!
場合は，TW!Q!TLとして!(3$=MLに戻る
→最終的に得られたx1を現在のフレームにおけるウィンドウ中心とする
#$%&'7)*+によるトラッキング例"!!
#$%&'7)*+によるトラッキング"!!
• 
• 
局所的な探索によるトラッキングが可能!
ピクセル分布の特徴を元に探索するため，様々な形状の物体をトラッキング可能!
• 
部分的なオクルージョンや混雑状態，カメラの位置変化に対して頑健
逐次処理による物体追跡法"!
•  領域ベースの物体追跡手法!
–  更新テンプレートマッチング，アクティブ探索!
–  #$%&'()*+法,!-%./01$!2*13$.!
–  オンライン学習!
•  特徴点ベースの物体追跡手法!
–  456法!
–  7892!6.%0:*&;
時系列フィルタリング"!
•  制御理論の分野で研究!
•  未来の値を予測!
•  ノイズを含む観測値から対象の状態を推定!
•  パーティクルフィルタ!
–  非線形!
–  非ガウス型の状態空間モデル!
–  状態空間や観測モデルなどに制約がない
画像から直接追跡対象の状態を推定することが可能
"CONDENSATION - Conditional Density Propagation for Visual Tracking," Isard, M, International Journal of Computer Vision, 1998
パーティクルフィルタ"!
73$=W!初期設定!
73$=L!パーティクルの遷移!
73$=O!観測!
73$=R!尤度計算!
73$=S!対象推定!
73$=\!選択
パーティクルフィルタ"!
73$=W!初期設定!
73$=L!パーティクルの遷移!
73$=O!観測!
73$=R!尤度計算!
初期パーティクルの配置
73$=S!対象推定!
73$=\!選択
パーティクルフィルタ"!
73$=W!初期設定!
73$=L!パーティクルの遷移!
73$=O!観測!
73$=R!尤度計算!
初期パーティクルの配置
73$=S!対象推定!
t+1フレームへの予測
73$=\!選択
パーティクルフィルタ"!
73$=W!初期設定!
73$=L!パーティクルの遷移!
73$=O!観測!
73$=R!尤度計算!
初期パーティクルの配置
73$=S!対象推定!
t+1フレームへの予測
73$=\!選択
観測
パーティクルフィルタ"!
73$=W!初期設定!
73$=L!パーティクルの遷移!
73$=O!観測!
73$=R!尤度計算!
初期パーティクルの配置
73$=S!対象推定!
t+1フレームへの予測
73$=\!選択
観測
尤度の計算
パーティクルフィルタ"!
73$=W!初期設定!
73$=L!パーティクルの遷移!
73$=O!観測!
73$=R!尤度計算!
初期パーティクルの配置
73$=S!対象推定!
t+1フレームへの予測
73$=\!選択
観測
尤度の計算
対象物体の推定
パーティクルフィルタ"!
73$=W!初期設定!
73$=L!パーティクルの遷移!
73$=O!観測!
73$=R!尤度計算!
初期パーティクルの配置
73$=S!対象推定!
t+1フレームへの予測
73$=\!選択
観測
尤度の計算
対象物体の推定
パーティクルの選択
73$=W!初期設定"!
•  参照ヒストグラムの作成!
–  ]7^ヒストグラム分布"!
•  H個のパーティクルを生成
参照パターン
初期フレームt
73$=L!パーティクルの遷移"!
•  状態遷移モデルを用いてパーティクルを遷移
ωt : ガウシアンノイズ
t+1フレーム
73$=O!観測"!
•  色ヒストグラムの取得!
–  ]7^ヒストグラム分布"!
t+1フレーム
73$=R!尤度計算"!
•  参照ヒストグラムと取得したヒストグラムの類似度を計算!
–  V)%_%0)%.``%係数を使用!
–  類似度が尤度となる
参照パターン
類似度
ヒストグラムの比較
t+1フレーム
ヒストグラムの類似度
尤度分布
73$=S!対象推定"!
•  重み付き平均より対象物体を推定!
–  は を合計Lになるように正規化した尤度
参照パターンの更新
t+1フレーム
73$=\!選択"!
•  尤度が高い順にH個のパーティクルを選択!
–  高い尤度のパーティクルを複製!
–  低い尤度のパーティクルを消去
t+1フレーム
追跡例"!
類似物体に頑健なパーティクルフィルタ"!
•  パーティクルフィルタの問題点!
–  色特徴を用いたパーティクルフィルタ!
•  類似物体に影響を受けやすい!
•  混合正規分布モデルを用いて類似物体の判別!
a4M!b:@<%,!$3M!%1,!ccF!VAA(3$K!-%./01$!2*13$."!#@1/3%.;$3!>$3$0/A&!%&K!6.%0:*&;dd,!eII^,!OWWSf!
類似物体を含まない尤度分布
類似物体を含む尤度分布
対象物体正規分布の判別"!
•  各正規分布の中心と前状態の対象物体の重心推定値との距
離を測定!
–  最も距離が近い正規分布を対象物体の尤度で構成されるものと判別
前状態
対象物体重心位置
対象物体正規分布の推定
対象物体正規分布
類似物体に頑健なパーティクルフィルタ"!
•  判別した対象物体正規分布と尤度分布を掛け合わせる!
–  対象物体のみを考慮した尤度分布を作成
対象物体正規分布
対象物体尤度分布
尤度分布
パーティクルフィルタによる人追跡例"!
従来法
混合正規分布モデルを使用
車追跡例"!
従来法
混合正規分布モデルを使用
#$%&'7)*+とパーティクルフィルタの違い"!
•  #$%&'7)*+!
–  局所的な追跡!
•  パーティクルフィルタ!
–  パーティクルによる大域的な追跡が可能
Mean-Shift
パーティクルフィルタ
#$%&'7)*+とパーティクルフィルタの違い"!
手法
Mean-Shift
パーティクルフィルタ
繰り返し解析
(局所計算による極大値)
重み付き確率
(ランダムサンプリング
による大域解の近似)
局所解
鋭いピーク
○
○
逐次処理による物体追跡法"!
•  領域ベースの物体追跡手法!
–  更新テンプレートマッチング，アクティブ探索!
–  #$%&'()*+法,!-%./01$!2*13$.!
–  オンライン学習!
•  特徴点ベースの物体追跡手法!
–  456法!
–  7892!6.%0:*&;
ブースティングによる物体追跡
追跡対象の変化にあわせて特徴量を更新
時刻t
時刻t−１
学習サンプル
セレクタ１
AdaBoost
特徴量を選択
オフラインで学習した検出器
＝特徴量候補
セレクタ２
セレクタ３
＋
強識別器
H(x)=!"nhn(x)
セレクタ４
セレクタ＝弱識別器
Ｏｎｌｉｎｅ Boostingについて
Ozaら[2001] Online Bagging and Boosting
Offlineで学習した弱識別器の識別関数をOnline時に
更新する!
すべての弱識別器を更新
Grabnerら[2006] On-line Boosting and Vision!
弱識別器を複数のグループに分け、追跡対象に適した
弱識別器を各グループから選択・更新
形状変化や隠れが生じるようなシーンでの追跡を実現
Online Boostingの問題点
追跡性能はセレクタの個数に依存
弱識別器の個数⇔計算コスト
selector1
selector2
selector3
selector5
0
高性能な
・弱識別器
・識別器選択手法
が必要
Ｏｎline Real Boosting
Real AdaBoostをOnline Boostingに適用
頭部確率を出力する識別関数をもつ弱識別器を選択
AdaBoost
1
０
selector1
0,1を出力
識別関数
1
０
識別関数
Real AdaBoost
弱識別器候補
弱識別器選択
最適な弱識別器
Online Real Boostingによる弱識別器選択
弱識別器候補
初期位置
Selector n
positive
エラーが最小
の弱識別器を
選択
エラー
negative
学習画像生成
セレクタｎでの弱識別器選択
Offline学習時に選択された特徴量パターン
!  Real AdaBoost +(Haar, ABS Haar, Edgelet, EOH特徴量)
!  AdaBoost +Haar特徴量
Online Real Boostingによる追跡性能
少ないセレクタ数(50個）で高い追跡性能
• 
• 
• 
追跡にはParticle Filterを用いる
Offilne学習：Real AdaBoostにより、弱識別器300個を選択
特徴量タイプ： Haar, ABS Haar, Edgelet, EOH特徴量
Mean Shift法との比較
照明変化や顔向き変化が生じるシーンで
追跡性能が向上
提案手法
Mean Shift
b&1*&$!9$%1!VAA(/&;に用いる特徴量!
正解画像!
人体追跡!
・ ・ ・!
非正解画像!
特徴量候補!
（オフライン学習）!
時刻t!
・ ・ ・!
時刻t+n!
限られた特徴量候補から選択（オフライン学習に依存）
形状変化に応じた最適な特徴量が選択できない
Hard Decision Feature
時刻t+m!
形状変化可能な特徴量!
正解画像!
人体追跡!
・ ・ ・!
非正解画像!
特徴量候補!
（オフライン学習）!
時刻t!
・ ・ ・!
時刻t+n!
時刻t+m!
追跡物体の形状変化に対応するために、
形状変化に応じて形状の変化が可能な特徴量
Soft Decision Feature
7A+!>$0*(*A&!2$%3@.$について!
基準特徴量の確率密度分布と類似する特徴量をグルーピング
特徴量：形状、確率密度関数Wy（正解、非正解）から構成
W-1
W-1
W+1
W+1
変形特徴量
基準特徴量
類似度
確率密度関数の更新
If S ＞ TH Wynew,j=Wyorg,j +
Wytrans,j
Soft Decision Feature
W-1
W+1
Basis type
Transform type
New Probability density
]>2による追跡
7>2による追跡
]%.K!>$0*(*A&!2$%3@.$!^M7M!7A+!>$0*(*A&!2$%3@.$!
Hard Decision Feature
姿勢が変化すると特徴量が頭部に集中し、人体全体を捉えられない
直立時
特徴量
座り込み時
特徴量
Soft Decision Feature
姿勢が変化しても特徴量が分散し、人体全体を捉える
直立時
特徴量
座り込み時
特徴量
逐次処理による物体追跡法"!
•  領域ベースの物体追跡手法!
–  更新テンプレートマッチング，アクティブ探索!
–  #$%&'()*+法,!-%./01$!2*13$.!
–  オンライン学習!
•  特徴点ベースの物体追跡手法!
–  456法!
–  7892!6.%0:*&;
特徴点マッチング
不変特徴(SIFT,SURF)を利用
7g26アルゴリズム
•  7g26の処理は大きく分けてO段階
1. キーポイント検出
スケールとキーポイント検出
Difference-of-Gaussian処理
キーポイントのローカライズ
キーポイントの絞り込み
サブピクセル位置推定
2. 特徴記述
オリエンテーションの算出
特徴量の記述
画像の勾配強度と方向算出
勾配方向ヒストグラム作成
>AU画像からの極値検出
•  >AU画像から極値?極大値A.極小値Eを検出
–  注目画素の>AU値を画像スケール空間のOh近傍と比較
ー
3枚1組
ー
ー
スケール
平滑化画像
DoG画像
キーポイントのローカライズ
•  キーポイントに向かない点
–  エッジ上の点
開口問題
–  >AU出力の小さい点ノイズの影響を受け易い
→主曲率とコントラストにより削除
キーポイント候補点
(キーポイント数:1895点)
主曲率による候補点削除
(キーポイント数:1197点)
コントラストによる候補点削除
(キーポイント数:421点)
オリエンテーションの算出
•  キーポイントのオリエンテーション
–  オリエンテーションの向きに正規化を行うことで回転に不
変な特徴量を算出
平滑化画像L(u, v)!
キーポイントが検出された平滑化画像
勾配方向
を算出
の勾配強度
と
勾配方向ヒストグラムの作成
• 
勾配情報から勾配方向ヒストグラムを作成
–  全方向をRh方向に離散化
–  キーポイントの持つスケールに対応する領域から勾配を算出
–  ガウス窓と勾配強度から重みをヒストグラムに加算
ガウス窓
"!
勾配強度
m(u,v)
勾配方向
= 重み
1
勾配方向ヒストグラム
h!
0
0
勾配方向(36bin)
35
特徴量の記述：記述領域の方向の正規化
•  特徴量を記述する領域をキーポイントが持つ䈊
オリエンテーションに合わせて回転させる
キーポイントのオリエンテーション
特徴量記述領域
回転に対する不変性を得る
特徴量の記述：特徴ベクトル算出
8方向
4分割
ガウス窓
特徴ベクトルを算出：
4分割
周辺領域を一辺4ブロックの計16ブロックに分割
ブロックごとに8方向(45度ずつ)の勾配方向ヒストグラム作成
ヒストグラムの各方向が特徴ベクトルとなる
4ブロック 4ブロック 8方向=128次元
特徴ベクトルの正規化
•  LOi次元の各特徴ベクトルの長さをベクトルの総和で正規化
照明変化に頑健な特徴量を得る
7g26特徴量の不変性を得る過程
1. キーポイント検出
・スケールとキーポイント検出 →スケール変化に対する不変性
・キーポイントのローカライズ →ノイズに対する頑健性
2. 特徴記述
・オリエンテーションの算出
→回転に対する不変性
・特徴量の記述
→照明変化に対する頑健性
7g26を用いた特徴点追跡
•  456法
–  追跡対象を剛体モデルと仮定
–  微小時間における領域は平行移動のみ，照明の変化による輝度変化が
ないという状態を仮定
–  一定領域内の情報を用いて移動先の推定
•  7g26を用いた特徴点追跡
–  特徴点ごとに情報を最も含むスケールを検出
–  特徴量に応じた領域を用いて移動先の推定
–  回転・スケール変化・照明変化に頑健な追跡が可能
SIFT特徴量の類似度を重みとしたMean-Shift探索による特徴点追跡
[都築 et al., 情処論 08]
7g26を用いた追跡
7892?7=$$K$K!8=!9AG@(3!2$%3@.$(Eの
処理の流れ
1. キーポイント検出子
‒  キーポイント(特徴点)の検出
‒  スケール探索
2. 記述子
‒  オリエンテーション
‒  特徴量の記述
処理の流れ
LM  近似ヘッセ行列の算出
–  VAT!j13$.による近似
–  g&3$;.%1!g<%;$による高速化
OM  スケールスペースの構築
RM  極値探索によるキーポイント検出
入力画像
近似ヘッセ行列の算出
• box filter!
• integral image!
• scale: #!
スケールスペースの構築
• scale #の変更
極値探索
キーポイント
ヘッセ行列
•  O次微分の集合
•  Lはガウシアンの各方向のO次微分を画像Iに畳み
込んだ応答値
Lxx
Lyy
Lxy
エッジの種類と判別式
•  エッジの種類
–  xy方向の両方の輝度差が大きいが極性が違う
–  xy方向の片方が輝度差が大きい
–  xy方向の両方の輝度差が大きい
•  判別式
ガウシアンの2次微分は計算コストが高いため判別に時間が掛かる
VAT!j13$.による近似
Lxx
Lyy
Lxy
Dxx
Dyy
Dxy
判別式
0.9倍：近似誤差修正
g&3$;.%1!g<%;$!
•  矩形領域の輝度値の和を高速に算出可能
•  利点
–  領域の数が多い場合
–  領域が重なり合う場合
O
S = A-B-C+D
B
D
S
C
A
特徴点とは
•  輝度差が大きい?エッジ）
–  テスクチャが多い
–  その場所の固有の情報が多い䈊
→ 特徴点に向いている
GAT!j13$.(!
スケールスペース
•  スケールkを増加し，複数の近似ヘッセ行列
を作成
Scale!
Scale!
–  スケールk!"!LMO,!OMW,!OMi,!RMh!
–  フィルタサイズ "!l!T!l,!L\!T!L\,!OL!T!OL,!Om!T!Om!
極値探索
Scale!
•  Oh近傍で極値ならキーポイント
キーポイント検出例
SURF(Speeded Up Robust Features)
1. SURFのキーポイント検出子
2. SURFの記述子
オリエンテーションの算出
•  h(の領域からオリエンテーションを算出
•  ]%%.'n%o$1$3を用いて勾配方向と強度を算出
–  オリエンテーション算出領域内をラスタ操作
–  x方向とy方向の応答?dx, dyEから勾配方向と強度を算出
4s!
4s!
９
6s!
x
peak
6s!
0!
y
5!
オリエンテーションの割り当て
•  勾配方向の分解能はhW度
–  ６方向のヒストグラムを作成
•  勾配強度の和が最も大きい角度䈊
→ オリエンテーション
6s!
peak
6s!
0!
5!
方向の正規化
LM  記述範囲としてOW(の領域を選択
OM  領域をSpS?NLhEブロックに分割
RM  記述範囲をオリエンテーション方向に回転
20s!
20s!
特徴ベクトル算出
•  Lつのブロックを４分割
•  分割した同じサイズの]%%.'n%o$1$3を作成
–  応答値よりqdx，qdy，qrdxr，qrdyrを算出䈊
→ 16分割!4次元＝64次元
7892!6.%0:*&;!
" Oフレーム間の7892特徴量をマッチング!
" グラフマッチング!
" マッチング点の関係から物体全体の動きを推定!
" 特徴点を前景と背景にわけ、隠れているか否か判
定!
グラフマッチング
7892!6.%0:*&;!
7892!6.%0:*&;!
•  重なりへの対応!
オクルージョン！
7892!6.%0:*&;結果
移動体追跡のまとめ"!!
•  よりロバストな移動体追跡を実現すには!
–  アピアランス?形状）特徴による追跡!
–  カラー特徴による追跡!
•  形状変化に頑健!
•  追跡手法の選択!
–  解くべき問題を考慮（メリットとデメリット）!
•  #$%&'7)*+!^M7M!-%./01$!2*13$.!
•  特徴点ベース ^M7M!領域ベース!
物体追跡例（１）
物体追跡例（２）
物体追跡例（３）