Tracking Image dengan Metode feature Lucas-Kanade Sumber: Sumber: -Forsyth & Ponce Chap. 19 -Tomashi, Tomashi, Lucas & Kanade: Kanade: Good Feature to Track -Standford Vision & Modeling
Agenda • Ulasan metode Lucas-Kanade + Implementasi dengan Matlab • Analisa metode Lucas-Kanade • Support Maps / Layers: - Robust Norm - Layered Motion - Background Subtraction - Color Layers
Page 1 1
Lucas-Kanade: Minimisasi fungsi: F
G
Image 1D
u?
Intensitas -
x
E (u ) = ∑ ( F ( x + u ) − G ( x))2 x
≈ ∑ ( Fx ( x)u − Ft ( x))2
Linierisasi:
x
Spatial Gradient
Temporal Gradient
Lucas-Kanade: Minimisasi fungsi: F
G ROI
Image 2D
ROI
(u,v)
E (u , v) =
∑ ( F ( x + u, y + v) − G ( x))
2
x , y∈ROI
≈
∑ ( F ( x, y)u + F ( x, y)v − F ( x, y))
x , y∈ROI
x
y
Spatial Gradient
2
t
Temporal Gradient
Page 2 2
Lucas-Kanade: Minimisasi fungsi:
Image 2D
Minimisasi fungsi E(u,v): ∂E =0 ∂u ∂E =0 ∂v
=>
∑ Fx2 ∑ Fx Fy
∑ F F u = ∑ F F ∑ F v ∑ F F x
y
2 y
C
t
x
t
y
u v =
D
u v =
C D
-1
Impelementasi Lucas-Kanade • Step 0: Inisialisasi (dengan manual) • Step 1: hitung: C dan D dan cari penyelesaian (u,v): - Hitung image derivatives Fx,Fy,Ft • Step 2: re-warp image G: - Sub-pixel image interpolation • Step 3: Loop: - Ukur error / terminate
Page 3 3
Impelementasi Lucas-Kanade •
Step 1: hitung: C dan D dan cari penyelesaian (u,v): - Hitung image derivatives Fx,Fy,Ft
A) Fx, Fy: Filter dengan Gaussian Derivative Kernel:
Impelementasi Lucas-Kanade •
Step 1: hitung: C dan D dan cari penyelesaian (u,v): - Hitung image derivatives Fx,Fy,Ft
B) Ft: Finite Difference of Blurred F and G:
Page 4 4
Impelementasi Lucas-Kanade •
Step 1: hitung: C dan D dan cari penyelesaian (u,v): - Hitung image derivatives Fx,Fy,Ft
- Hitung dengan Gaussian kernel (menggunakan coarse-to-fine strategy dengan pengurangan sigma)
Impelementasi Lucas-Kanade •Step 2: re-warp image G: - Sub-pixel image interpolation
Operasi Warping gunakan fungsi interp2 dari Matlab
Page 5 5
Impelementasi Lucas-Kanade • Step 3: Loop: - Ukur error / terminate
perhatikan:
|| Ft ||2
Analisa Grafis metode LucasKanade
Page 6 6
Lucas-Kanade: problem singulariti Minimisasi fungsi E(u,v): ∂E =0 ∂u ∂E =0 ∂v
=>
∑ Fx2 ∑ Fx Fy
∑ F F u = ∑ F F ∑ F v ∑ F F x
y
2 y
C
t
x
t
y
u v =
D
u v =
C D
-1
Lucas-Kanade: problem singulariti ∑ Fx2 ∑ Fx Fy
∑ F F u = ∑ F F ∑ F v ∑ F F x
y
2 y
t
x
t
y
Fx=0, Fy=0
0 0 C= 0 0
Page 7 7
Lucas-Kanade: problem singulariti ∑ Fx2 ∑ Fx Fy
Fx=0, Fy=0
0 0 C= 0 0
∑ F F u = ∑ F F ∑ F v ∑ F F x
y
2 y
t
x
t
y
Fy=0
a 0 C= 0 0
Lucas-Kanade: problem singulariti ∑ Fx2 ∑ Fx Fy
Fx=0, Fy=0
0 0 C= 0 0
∑ F F u = ∑ F F ∑ F v ∑ F F x
y
2 y
t
x
t
y
Fy=0
a 0 C= 0 0
eig (C ) = (e1,0)
Page 8 8
Lucas-Kanade: Aperture Problem
Fx=0, Fy=0
0 0 C= 0 0
eig (C ) = (e1,0)
Lucas-Kanade: Aperture Problem
Bergen et al.
Page 9 9
Aperture Problem: Bisa diatasi ??? ∑ Fx2 ∑ Fx Fy
∑ F F ∑ F x
y
2 y
eig (C ) = (e1, e 2)
- Hindari sebisa mungkin ! - Gunakan nilai Eigenvalues untuk inisialisasi “Good Features” (lihat paper “Good Features to track” Shi-Tomasi) - Lokasi Good Feature berada pada: min(eig1,eig2) > a
Aperture Problem: Bisa diatasi ??? “Good Features” (Shi-Tomasi)
Page 10 10
Aperture Problem: Bisa diatasi ??? ∑ Fx2 ∑ Fx Fy
∑ F F ∑ F x
y
2 y
eig (C ) = (e1, e 2)
- coba di Hack ! - regularisasi C:
λ 0 Creg = C + 0 λ
Aperture Problem: Bisa diatasi ??? ∑ Fx2 ∑ Fx Fy
∑ F F ∑ F x
y
2 y
eig (C ) = (e1, e 2)
- Simoncelli et al 1991:
Page 11 11
Aperture Problem: Bisa diatasi ??? ∑ Fx2 ∑ Fx Fy
∑ F F ∑ F x
y
2 y
eig (C ) = (e1, e 2)
- Tambah Aperture (window feature) ! - Coarse-to-fine Pyramids (Bergen et al, Simoncelli)
Aperture Problem: Bisa diatasi ??? ∑ Fx2 ∑ Fx Fy
∑ F F ∑ F x
y
2 y
eig (C ) = (e1, e 2)
- Tambah Aperture (window feature) ! - akibat: integrasi ROI lebih besar -> motion model jadi lebih komplex
Page 12 12
Pengembangan Lucas-Kanade secara Affine Affine Motion Model:
x + u a1 y + v = a 3
a2 x a5 + a4 y a6
- 2D Translation - 2D Rotation - Scale in X / Y - Shear Matlab demo ->
Pengembangan Lucas-Kanade secara Affine Affine Motion Model -> digunakan pada Lucas-Kanade:
E (u , v) =
∑ ( F ( x + u, y + v) − G ( x, y))
2
x , y∈ROI
a1 x + a2 y + a3
a4 x + a5 y + a6
a1 C ... = D a6 Matlab demo ->
Page 13 13
• Support Maps / Layers: - Robust Norm - Layered Motion - Background Subtraction - Color Based Tracking
Support Maps / Layers - L2 Norm vs Robust Norm - Bahaya dari fitting secara least square:
Akibat adanya Outliers (gangguan pixel luar) menyebabkan square error menjadi sangat besar
Page 14 14
Support Maps / Layers - L2 Norm vs Robust Norm - Bahaya dari fitting secara least square: L2
D
Support Maps / Layers - L2 Norm vs Robust Norm - Bahaya dari fitting secara least square: L2
robust
D
D
Page 15 15
Support Maps / Layers - Robust Norm -- baik untuk menangani outliers - nonlinear optimization robust
D
Support Maps / Layers
- Black-Jepson-95
Page 16 16
Support Maps / Layers - Layered Motion (Jepson/Black, Weiss/Adelson, …)
Support Maps / Layers - Kasus spesial dari Layered Motion: - Background substraction - Outlier rejection (== robust norm) - Kasus sederhana: Tiap Layer punya warna seragam
Page 17 17
Support Maps / Layers - Color Layers: P(skin | F(x,y))
Page 18 18
