1 コンピュータビジョン特論 対象追跡1 物体追跡研究の推移 追跡の応用

テンプレートマッチング（Template matching）
追跡の応用分野

コンピュータビジョン特論
対象追跡１



Crane, etc, Translation-tolerant mask matching using
non-coherent reflective optics, PR, 1968
サーベイランス
（観測、監視、見守り）
運動解析
３次元形状復元
（Structure from Motion）
Template
呉 海元
事前準備
バイクの追跡、プレートナンバの認識
物体追跡研究の推移
検出と追跡（検出）
屋外・環境変動への対応
サーベイランス 個人認識、人物監視
オフライン処理
リアルタイム処理
軍需関係？
全探索
勾配法
予測に基づく手法
追跡しながら
3次元形状の復元
多数人物追跡カウント
 検出：一枚の画像から指定した条件（パターン）
Wakayama University
Vision and Robot Laboratory---- VRL
背景混入の問題
When detecting an object,
をみたす画像領域を抜き出す処理
・1968 更新テンプレートマッチング
見えに基づく手法
一枚の画像から
対象を抜き出す
・1981 Lucas-Kanade
・1991 Tomasi-Kanade
勾配法(レジストレーション）
勾配法（特徴点追跡）
・1971 航空機画像解析
（雲の動きの解析）
・1995 モンテカルロフィルタの利用
bootstrap filter
・1980後半 カルマンフィルタの利用
動きのモデル化
時系列フィルタリング
・1992 J.Boyce, D.Toulson
・1998 M.Isard, A.Blake
ConDensation
α-β-γ トラッカー
・1975 K.Fukunaga
Mean-Shift
Mean-Shift
基盤となる要素技術の発展
ハードウェアの発展
1980年
1990年
・2000 D,.Comaniciu P.Meer
Mean-Shiftを使った非剛体追跡
クラスタリングに基づく手法
EMベースの追跡
パターン認識に基づく手法
・1999
・2001
2000年
SVMを使った追跡
対象のモデル
（パターン）
例：画像から歩行者の検出
入力画像
画像から対象モデルと一番似ている所を探し出す
→対応画素の明るさor色、テクスチャの差を尺度とする
We get a sub-image
containing the target
1
背景混入の問題
ステレオカメラを用いた顔検出の高速化
探索空間・時間の問題

人間の頭部サイズはほぼ一定なので、３次元空間内
の距離が分かれば、画像上での顔の大きさが分かる
Some background pixels will creep into the
target model in its updating.
Isize  Wsize 
foreground pixels,
and …
This
sub-image
This
is the background interfusion problem
contains
both …
that causes
object detecting failure.
背景混入による検出・追跡失敗
Z : 物体までの距離
Larger
Scale
f
Smallest
Scale
50,000 Locations/Scales
background pixels !
ステレオカメラを用いた顔検出の高速化

ステレオカメラを用いることで距離画像を得られる
3D point
f : 焦点距離
Z
Wsize : 実際の大きさ
Isize : 画像上での大きさ
ステレオカメラを用いた顔検出の高速化

画像上での顔の大きさが分かれば、特定のサブウィ
ンドウに対して識別するだけでよい
視差
ｄ
点までの距離
Z
image plane
f
Z
焦点距離f
カメラ間距離
camera
Ｂ
左カメラ
左側の画像
右側の画像
ステレオ（人間の両目）の基本的原理は
三角測量である！（fとBが既知）
右カメラ
Z
Bf
d
距離画像：白ほど距離が近い 矩形の辺の決定：Isize  Wsize  f
Z
メリット： １）早くで検出できる
２）誤検出が少なくなる
2
実行結果（動画２人）
2フレーム間差分による物体の検出・追跡

t-1フレーム
矩形は推定された距離より
統合した領域；点の緑濃さは
距離情報を示す
フレーム間差分例
「現在のフレーム」と「前フレーム」の差分．


○は検出された顔
背景差分例
tフレーム
仮定：背景が固定
照明が不変
全ての処理はビデオレートで実現できている
背景差分による物体の検出

「現在のフレーム」 と「特定の背景画像」の差分．

２フレーム差分の実画像の例
３フレーム間差分による動き領域の検出

仮定：
t-2
t-1
t
背景が既知
照明が不変
t-1の動いた領域
3
Optical flow-based detection
実画像の例
まず、２フレーム間差分
差分
t-1
2値化
A
2値化
B
画像上での対象追跡
（K-means Tracker）
t
差分
t-1
t-2
FG’06, ICPR’06, JMM’06, ACCV’07
情報処理学会CVIM論文誌’05, 07
差分
2値化
(船井若手賞、山下記念賞)
C
電子情報通信システム学会誌’07
t-2
t
３フレーム間差分による動き領域の検出
検出と追跡
検出と追跡（追跡）
 毎フレームから対象を検出すれば追跡？
 追跡：動画像から指定した領域を抜き出し、


A

フレーム間での対応づけを考慮した処理
B
対象のモデル
複数フレーム間
で対象を対応づ
ける
C
t-1フレーム
tフレーム
Maximum Speed
入力画像
フレーム間で対応づけていない
→追跡ではない
4
検出≠追跡
どちらが対応している？
検出だけではわからない
追跡手法に要求される要素
各フレームで検出なら
二個検出された
 追跡対象の回転・平行移動・変形問題
 計算コスト
• リアルタイム（ビデオレート＝30枚/秒）
見えに基づく追跡
 複雑な背景の元でのロバスト性
• 室内、屋外、雑踏
 環境変動への対応
t-1フレーム
tフレーム
フレーム間で対応付けていないのは追跡ではない
検出結果をフレーム間で対応付ければ追跡
出席チェック
 出席チェック
• 検出と追跡は何が違うか？
• 照明変化、背景変動
 パラメータ調整の容易さ
• 初期設定、閾値
見えに基づく追跡手法
追跡手法の分類
 対象の表現（モデル）による分類
追跡対象の情報を何で表現するか
• 見え（局所画像）、色ヒストグラム、エッジ、コーナー
• 最近：高次元特徴→SIFT, SURF, HOG, CoHOG
（ブロックマッチング＋全探索）
１．局所領域（モデルを切り出す）
比較
３．切り出した領域とモデルを比較
 類似性尺度による分類
学籍番号と名前を記入して提出
モデルと画像をどう対応付けるか
• 二乗誤差、相関、など
４．最も類似した領域
を結果とする
類似度最大
（相違度最小）
 探索方法による分類
どうやって追跡対象を見つけるか
• （周辺）全探索、勾配法、動き予測、近似最近傍
これらは互いに関連する
t-1フレーム
tフレーム
２．前のフレームの周辺を探索
前フレームの類似性尺度が最大になる領域に基づいて
現フレームの探索領域を決め、探索を行う
5
見えに基づく手法の類似性尺度
 よく用いられる類似度(相違度)１
見えに基づく手法の類似性尺度
 よく用いられる類似度(相違度)２
x
• SSD(Sum of Squared Differences)
Ｗ
 (d) 
W : 画像中の局所領域（ブロック）
I
x+d
 x
x  W : 領域W内の座標x   
 y
I A (x) : 画像ＩAの座標xの画素値
t-1
t
( x) 
b
b
 I ( x  d)  I
xW
t
( x) 
2
t 1
部分テンプレットが複数用意
見えに基づく追跡の拡張
 よく用いられる類似度３
I t 1
ラスタスキャン
多次元ベクトルと考える
画素毎に差をとって二乗
総和
アフィン変換
x  Ax  d
見えに基づく手法の類似性尺度
 (d ) 
• 画像をベクトルとみなせば、ベクトル間
のユークリッド距離（の二乗）~Ｌ2距離
• 外れ値の影響を受けやすい
• 照明変化の影響を受けやすい
a
 (d) 
 ( A, d) 
• CC(Cross Correlation) 正規化相互相関
• 最も基本的な誤差関数
• 画素値が全体的に変化する
SSD
( x) |
It
a
2
t 1
t 1
 a11 a12  x   d x 

    
 a21 a22  y   d y 
見えに基づく手法の類似性尺度
• SSD(Sum of Squared Differences)
t
• 画像をベクトルとみなした場合のＬ１距離（市街地距離）
• SSDに比べて外れ値の影響を受けにくい
• 照明の影響を受けやすい
d
 dx 
d : 変位量d   
dy 
→全フレームの該当領域W(X)の付近W(X+d)で探索
xW
 | I (x  d)  I
xW
 I ( x  d)  I
変位ｄだけでなく、拡大、縮小、回転などの領域の変形A
を含む追跡
• 画素毎の差分の絶対値の和
2
 I t (x  d)  I t 1 (x)
xW
 (d) 

• SAD(Sum of Absolute Differences)
• 画素毎の差分の二乗和（二乗誤差）
 (d) 
見えに基づく追跡の拡張
 I (x  d)  I I
xW
t
t
t 1
(x)  I t 1

xW
明るさの正規化
xW
t 1
xW
t
xW
t
SSD,SAD
コントラスト
の正規化
t
( x) 
2
t 1
tフレームのx  t  1フレームのAx  d
| I t (x  d)  I t || I t 1 ( x)  I t 1 |
 I ( x)
 I (x  d)

，　I 
1

1
 I ( Ax  d)  I
 a11 a12  x   d x 

    
 a21 a22  y   d y 
xW
• ベクトル間の内積（角度）
• 照明変化に強い
q
６パラメータの最小化が必要→計算量が大きい
全探索では非現実的
11 , a12 , a21 , a22 , d x , d y 
a
ベクトルのノルムが変化しても
内積（CC=cosq)は変わらない
6
見えに基づく追跡＋全探索の問題点
 計算量が多い
• ブロックサイズ×探索領域のサイズの計算コスト
• 回転、スケールなどに拡張した場合はさらに計算
コストが増大する
Lucas & Kanade法
SSD :  
 I ( x  x, y  y, t  t )  I ( x, y, t ) ①
2
SSD :  
Σ内の第一項目をテイラー展開すると
 I ( x  x, y  y, t  t )  I ( x, y, t ) ①
2
xW
xW
Σ内の第一項目をテイラー展開すると
I ( x  x, y  y, t  t )
 I ( x, y, t )  x
 変位量が離散的
↓
Lucas & Kanade法
変位が微少であるから、２次以降の項を無視
(ｘ周辺で線形近似）
解決策
x  d x , x  d y , t  1として①に代入すると
 見え＋勾配法による追跡

 d
( x , y )W
I ( x, y , t )  d y I y ( x, y , t )  I t ( x, y , t ) 
2
x x
I x ( x, y , t ) 
見えに基づく追跡＋勾配法
 勾配法とは、暫定解
まわりの勾配（傾き）に
基づいて山登り（山くだり）によって極大値（極
小値）を見つける

関数f ( x)が無限に微分可能であ るとき
f ( x )のaのまわりのテイラー級 数展開は
以下のようになる

f ( n ) (a)
( x  a) n
n!
n 0
1
 f (a )  f (a )( x  a )  f (a )( x  a ) 2  
2
I
x, y, t , I y ( x, y, t )  I x, y, t , I t ( x, y, t )  I x, y, t 
x
y
t
Lucas & Kanade法
テイラー展開とは？
f ( x)  
Lucas Kanade法
I ( x, y, t )
I ( x, y, t )
I ( x, y, t )
 y
 t

x
y
t
 d I
( x , y )W
x x
( x, y , t )  d y I y ( x, y , t )  I t ( x, y , t ) 
目標はが最小なので
2


 0,
 0となるdを求めればよい
d x
d y

  2 I x ( x, y, t )d x I x ( x, y, t )  d y I y ( x, y, t )  I t ( x, y, t )   0
d x ( x , y )W

  2 I y ( x, y, t )d x I x ( x, y, t )  d y I y ( x, y, t )  I t ( x, y, t )   0
d y ( x , y )W
T
 I x (x1 , t )  I x (x n , t ) 
A
 , d  d x
 I y (x1 , t )  I y (x n , t ) 
dy 
T
b   I t (x1 , t )   I t ( x n , t ) とすると
T
Ad  b  0  A T Ad  A T b  0  A T Ad  A T b
7
Lucas & Kanade法
A T Ad  A T b
Lucas & Kanade法と追跡の安定性

I (x, t )
 I (x, t ) I (x, t )

行列 A A   
I
(
x
,
t
)
I
(
x
,
t
)

 I (x, t ) 
Measurement of motion at every pixel
2
x
T
T
 I x (x1 , t )  I x (x n , t ) 
ここで、A  
 より
 I y (x1 , t )  I y (x n , t ) 
  I x ( x, t ) 2
 I x (x, t ) I y (x, t )
AT A  
I
(
x
,
t
)
I
(
x
,
t
)
 x
 I y (x, t ) 2 
y
となり、A T Aが正則なとき解を持ち 、
dˆ  ( A T A ) 1 A T b
x
y
2
x
y
y
の二つの固有値が大きい時、追跡が安定に行える
• 強い勾配が存在
• 色んな方向（直交する方向）に強い勾配が存在
このようなブロックの追跡は安定
探索不要で推定解が求まる
アフィン変換などへの拡張も可能
Lucas & Kanade法の実装
Alper Yilmaz, Fall 2004 UCF
Example: Optical Flow
見えに基づく追跡のまとめ
Flow field
I
( x, y, t )  I ( x  1, y, t )  I ( x, y, t )
x
I
I y ( x, y, t )  ( x, y, t )  I ( x, y  1, t )  I ( x, y, t )
y
I x ( x, y , t ) 
t=0


空間微分＝隣り合う画素の差

t=0
I t ( x, y , t ) 
I
( x, y, t )  I ( x, y, t  1)  I ( x, y, t )
t
時間微分＝フレーム間の差分

t=1
仮定：
連続画像間で対応している
点の明るさが変化しない
Best estimates where there are “corners”

局所画像そのものを対象モデルとする
SSD,SAD、CCなどの類似性尺度を用いる
平行移動だけでなく、回転、スケールなどへ拡張可能
全探索では計算量が多い→見え＋勾配法
• Lucas＆Kanade法
追跡しやすい特徴点の抽出
• GoodFaturesToTrack
from Russell & Norvig
注：OpenCVの中に関連ライブラリがある
8
勾配に基づく追跡の問題点
 対象の動きに関する知識を利用しない
初期値（前フレームの結果）が十分解に近い
必要がある
 類似度を求めるために、解の周辺でなめらか
（微分可能）である必要がある
 見え隠れなどのノイズの影響を受けやすい

類似度
Affine Motion and Transformation
 Transformation
Motion
x' '  a1 x  a2 y  b1
x' '  (a1  1) x  a2 y  b1
y ' '  a3 x  a4 y  b2
y ' '  a3 x  (a4  1) y  b2
translation
rotation
shear
状態
Rigid (rotation and translation)
Affine
Alper Yilmaz, Fall 2004 UCF
出席チェック
 見えに基づく追跡の弱点はなにか？

勾配法による探索の利点を２つあげなさい
• 学籍番号と名前を記入して提出
 次回は予測に基づく追跡について
9