Feature Lucas-Kanade(LK) Image Registration & Tracking dengan Metode Lucas & Kanade
• Extraksi feature dengan metode LK ini adalah sangat populer dalam aplikasi computer vision. • Feature diekstraksi dengan mengambil informasi gradient image. • Selanjutnya feature ini bisa dimanfaatkan untuk Image registration, yg. Selanjutnya diugnakan utk. tracking, recognition, dan lain-lain • Pemilihan feature image yang tepat adalah sangat menentukan keberhasilan proses recognition, tracking, etc.
Sumber: -Forsyth & Ponce Chap. 19, 20 -Tomashi & Kanade: Good Feature to Track
Sejarah Perkembangan LK • • • • • • • • • • • LK
Image Registration
Lucas & Kanade (IUW 1981) Bergen, Anandan, Hanna, Hingorani (ECCV 1992) Shi & Tomasi (CVPR 1994) Szeliski & Coughlan (CVPR 1994) Szeliski (WACV 1994) Black & Jepson (ECCV 1996) Hager & Belhumeur (CVPR 1996) Bainbridge-Smith & Lane (IVC 1997) Gleicher (CVPR 1997) Sclaroff & Isidoro (ICCV 1998) Cootes, Edwards, & Taylor (ECCV 1998) BAHH
ST
SC
S
BJ
HB
BL
G
SI
CET
1
Penerapan pada aplikasi: • Stereo
Penerapan metode LK
LK
BAHH
Penerapan pada aplikasi:
BAHH
ST
SC
SC
S
BJ
HB
BL
G
SI
CET
SI
CET
Penerapan pada aplikasi:
• Stereo • Dense optic flow
LK
ST
• Stereo • Dense optic flow • Image mosaics
S
BJ
HB
BL
G
SI
CET
LK
BAHH
ST
SC
S
BJ
HB
BL
G
2
Penerapan pada aplikasi: • • • •
LK
Penerapan pada aplikasi:
Stereo Dense optic flow Image mosaics Tracking
BAHH
ST
SC
• • • • •
S
BJ
HB
BL
G
SI
CET
LK
Stereo Dense optic flow Image mosaics Tracking Recognition
BAHH
ST
SC
?
S
BJ
HB
BL
G
SI
CET
rumusan L&K 1 I0(x)
Derivasi Rumusan Lucas & Kanade
I 0' ( x)
#1 I 0' ( x) = lim
h→0
I 0 ( x + h) − I 0 ( x ) h
3
rumusan L&K 1 h
rumusan L&K 1 h
I0(x)
I0(x+h)
I0(x)
I(x)
I 0' ( x) ≈
I 0 ( x + h) − I 0 ( x ) h
I 0' ( x) ≈
rumusan L&K 1 h
I(x)
rumusan L&K 1 I0(x)
I0(x)
I(x)
h ≈
I ( x) − I 0 ( x) I 0' ( x)
I ( x) − I 0 ( x) h
R
h ≈
I ( x) − I 0 ( x) 1 ∑ | R | x∈R I 0' ( x)
4
rumusan L&K 1
rumusan L&K 1 h0
I0(x)
I(x)
h≈
I(x)
w( x )[ I ( x) − I 0 ( x)] 1 ∑ I 0' ( x) ∑ x w( x) x∈R
h0 ←
rumusan L&K 1
I(x)
w( x )[ I ( x) − I 0 ( x)] 1 ∑ I 0' ( x) ∑ x w( x) x∈R
rumusan L&K 1
I0(x+h0)
h1 ← h0 +
I0(x)
I0(x+h1)
I(x)
w( x )[ I ( x) − I 0 ( x + h0 )] 1 ∑ I 0' ( x + h0 ) ∑ x w( x) x∈R
h2 ← h1 +
w( x)[ I ( x) − I 0 ( x + h1 )] 1 ∑ I 0' ( x + h1 ) ∑ x w( x) x∈R
5
rumusan L&K 1
rumusan L&K 1
I0(x+hk)
I(x)
I0(x+hf)
I(x)
hk +1← hk +
w( x)[ I ( x) − I 0 ( x + hk )] 1 ∑ I 0' ( x + hk ) ∑ x w( x) x∈R
hk +1← hk +
w( x)[ I ( x) − I 0 ( x + hk )] 1 ∑ I 0' ( x + hk ) ∑ x w( x) x∈R
rumusan L&K 2 • Sum-of-squared-difference (SSD) error
Derivasi Rumusan Lucas & Kanade #2
E(h) = Σ [ I(x) - I0(x+h) ]2 x ε R
E(h) ≈ Σ [ I(x) - I0(x) - hI0’(x) ]2 x ε R
6
rumusan L&K 2
∂E ≈ Σ 2[I0’(x)(I(x) - I0(x) ) - hI0’(x)2] ∂h x ε R =0 h≈
Σ
x ε R
I0’(x)(I(x) - I0(x))
Σ
x ε R
I0’(x)2
Perbandingan
h ≈
h ≈
Σ
x
w(x)[I(x) - I0(x)] I0’(x)
Σ
Σ
x
x
w(x)
I0’(x)[I(x) - I0(x)]
Σ
x
I0’(x)2
Perbandingan
h ≈
h ≈
Σ
x
w(x)[I(x) - I0(x)] I0’(x)
Σ
Σ
x
x w(x)
Generalisasi metode LucasKanade
I0’(x)[I(x) - I0(x)]
Σ
x
I0’(x)2
7
Rumus Original
Rumus Original • Dimension of image
E( h ) =
Σ
[ I( x + h ) - I0 (x) ] 2
x εR
E( h ) =
Σ
[ I( x + h ) - I0 (x) ] 2
x εR
1-dimensional
LK
BAHH
Generalisasi 1a
Σ
LK
BAHH
ST
SC
E( h ) =
x x= y
2D:
S
BJ
HB
BL
G
SI
CET
• Dimension of image
[ I( x + h ) - I0 (x) ] 2
xεR
S
Generalisasi 1b
• Dimension of image
E( h ) =
SC
ST
BJ
HB
Σ
[ I( x + h ) - I0 (x) ] 2
xεR
x x = y 1
Homogeneous 2D:
BL
G
SI
CET
LK
BAHH
ST
SC
S
BJ
HB
BL
G
SI
CET
8
Permasalahan A
Permasalahan A Local minima:
Apakah iterasi bisa konvergen?
LK
BAHH
ST
SC
S
BJ
HB
BL
G
SI
CET
Permasalahan A
Permasalahan B Zero gradient:
Local minima:
h≈
-xΣε R I0’(x)(I(x) - I0(x))
Σ
x ε R
h is undefined if LK
BAHH
ST
SC
S
I0’(x)2
Σ
x ε R BJ
I0’(x)2 HB
BL
is zero G
SI
CET
9
Permasalahan B
Permasalahan B’
Zero gradient:
Aperture problem (mis. Image datar):
hy ≈ ? LK
BAHH
Permasalahan B’
ST
∂I 0 (x) (x)(I(x) - I0(x)) ε R ∂y 2 Σ ∂I∂0 y(x) x ε R
-Σ x
SC
S
BJ
HB
BL
G
SI
CET
SI
CET
Jawaban problem A & B • Possible solutions:
No gradient along one direction:
– Manual intervention
?
LK
BAHH
ST
SC
S
BJ
HB
BL
G
10
Jawaban problem A & B
Jawaban problem A & B
• Possible solutions:
• Possible solutions:
– Manual intervention – Zero motion default
LK
BAHH
ST
SC
S
– Manual intervention – Zero motion default – Coefficient “dampening”
BJ
HB
BL
G
SI
CET
LK
BAHH
Jawaban problem A & B
ST
SC
S
S
BJ
HB
BL
G
SI
CET
SI
CET
• Possible solutions:
– Manual intervention – Zero motion default – Coefficient “dampening” – Reliance on good features
BAHH
SC
Jawaban problem A & B
• Possible solutions:
LK
ST
BJ
– Manual intervention – Zero motion default – Coefficient “dampening” – Reliance on good features – Temporal filtering
HB
BL
G
SI
CET
LK
BAHH
ST
SC
S
BJ
HB
BL
G
11
Jawaban problem A & B
Jawaban problem A & B
• Possible solutions:
• Possible solutions:
– Manual intervention – Zero motion default – Coefficient “dampening” – Reliance on good features – Temporal filtering – Spatial interpolation / hierarchical estimation LK
BAHH
ST
SC
S
BJ
HB
BL
G
SI
– Manual intervention – Zero motion default – Coefficient “dampening” – Reliance on good features – Temporal filtering – Spatial interpolation / hierarchical estimation – Higher-order terms CET
LK
BAHH
SC
ST
Kembali lagi: Rumus Original
S
BJ
HB
BL
G
SI
CET
Rumus Original • Transformations/warping of image
E( h ) =
Σ
xεR
[ I( x + h ) - I0 (x) ] 2
E( h ) =
Σ
[ I( x + h ) - I0 (x) ] 2
xεR
δx h= δy
Translations:
LK
BAHH
ST
SC
S
BJ
HB
BL
G
SI
CET
12
Permasalahan C
Generalisasi 2a • Transformations/warping of image
Bagaimana bila ada gerakan(motion) tipe lain?
E(A, h) =
Σ
[ I(Ax + h ) - I0 (x) ] 2
xεR
a b δx A= h= c d δy
Affine:
LK
BAHH
SC
ST
Generalisasi 2a
S
BJ
HB
G
BL
SI
CET
Generalisasi 2b • Transformations/warping of image
E(A) = Affine:
Σ
[ I( A x ) - I0 (x) ] 2
xεR
a1 Planar perspective: A = a4 a7
a b δx A= h= c d δy LK
BAHH
ST
SC
S
BJ
HB
a3 a6 1
a2 a5 a8 BL
G
SI
CET
13
Generalisasi 2b
Generalisasi 2c • Transformations/warping of image
Affine
+
E( h ) = a1 Planar perspective: A = a4 a7
a2 a5 a8
a3 a6 1
Σ
[ I( f(x, h)) - I0 (x) ] 2
xεR
Other parametrized transformations
LK
BAHH
ST
Generalisasi 2c
SC
S
BJ
HB
BL
G
SI
CET
Permasalahan B”
h≈
-xΣε R I0’(x)(I(x) - I0(x))
Σ
x ε R
I0’(x)2
Generalized aperture problem:
~ h ≈ -(JTJ)-1 J (I(f(x,h)) - I0(x))
Other parametrized transformations
LK
BAHH
ST
SC
S
BJ
HB
BL
G
SI
CET
14
Permasalahan B”
Rumus Original
Generalized aperture problem:
E( h ) =
Σ
[ I( x + h ) - I0 (x) ] 2
xεR
?
Rumus Original
Generalisasi 3
• Image type
E( h ) =
• Image type
Σ
[ I( x + h ) - I0 (x) ] 2
xεR
E( h ) =
Σ
||I( x + h ) - I0(x) ||2
xεR
Grayscale images
LK
BAHH
ST
SC
S
BJ
HB
Color images
BL
G
SI
CET
LK
BAHH
ST
SC
S
BJ
HB
BL
G
SI
CET
15
Rumus Original
E( h ) =
Σ
xεR
Rumus Original • Anggapan pixel punya konstan brightness (Constancy assumption)
[ I( x + h ) - I0 (x) ] 2
E( h ) =
Σ
[ I( x + h ) - I0 (x) ] 2
xεR
Brightness constancy
LK
BAHH
SC
ST
Permasalahan C
S
BJ
HB
BL
G
SI
CET
Generalisasi 4a • Constancy assumption
Bagaimana bila iluminasi cahaya bervariasi?
E( h,α,β )= Σ [ I( x + h ) - αI0(x)+β] 2 xεR
Linear brightness constancy
LK
BAHH
ST
SC
S
BJ
HB
BL
G
SI
CET
16
Generalisasi 4a
Generalisasi 4b • Constancy assumption
E ( h,λ) =
Σ
[ I( x + h ) - λΤB(x)] 2
xεR
Illumination subspace constancy
LK
BAHH
SC
ST
Permasalahan C’
S
BJ
HB
BL
G
SI
CET
Generalisasi 4c • Constancy assumption
Bagaimana bila texture berubah?
E ( h,λ) =
Σ
[ I( x + h ) - λΤB(x)] 2
xεR
Texture subspace constancy
LK
BAHH
ST
SC
S
BJ
HB
BL
G
SI
CET
17
Permasalahan D
Jawaban problem D • Percepat konvergensi dengan: – Coarse-to-fine, filtering, interpolation, etc.
Jelas proses konvergensi menjadi lambat bila jumlah #parameters bertambah !!!
LK
BAHH
Jawaban problem D
ST
SC
S
BJ
HB
S
BJ
HB
BL
G
SI
CET
SI
CET
• Percepat konvergensi dengan:
– Coarse-to-fine, filtering, interpolation, etc. – Selective parametrization
BAHH
SC
Jawaban problem D
• Percepat konvergensi dengan:
LK
ST
BL
G
– Coarse-to-fine, filtering, interpolation, etc. – Selective parametrization – Offline precomputation
SI
CET
LK
BAHH
ST
SC
S
BJ
HB
BL
G
18
Jawaban problem D
Jawaban problem D
• Percepat konvergensi dengan:
• Difference decomposition
– Coarse-to-fine, filtering, interpolation, etc. – Selective parametrization – Offline precomputation • Difference decomposition
LK
BAHH
ST
SC
S
BJ
HB
BL
G
SI
CET
Jawaban problem D
Jawaban problem D
• Difference decomposition
• Percepat konvergensi dengan: – Coarse-to-fine, filtering, interpolation, etc. – Selective parametrization – Offline precomputation • Difference decomposition
– Improvements in gradient descent
LK
BAHH
ST
SC
S
BJ
HB
BL
G
SI
CET
19
Jawaban problem D
Jawaban problem D
• Percepat konvergensi dengan:
• Multiple estimates / state-space sampling
– Coarse-to-fine, filtering, interpolation, etc. – Selective parametrization – Offline precomputation • Difference decomposition
– Improvements in gradient descent • Multiple estimates of spatial derivatives
LK
BAHH
ST
SC
S
BJ
HB
BL
G
SI
CET
Generalisasi metode Lucas-Kanade
Rumus Original • Error norm
Modifikasi yg. Dibuat selama ini adalah:
Σ
x εR
[ I( x + h ) - I0 (x) ] 2
E( h ) =
Σ
[ I( x + h ) - I0 (x) ] 2
xεR
Squared difference:
LK
BAHH
ST
SC
S
BJ
HB
BL
G
SI
CET
20
Permasalahan E
Generalisasi 5a • Error norm
Permasalahan dengan ourliers? >> Gunakan robust norm
E( h ) =
Σ ρ ( I( x + h ) -
Robust error norm: ρ (u ) =
LK
BAHH
I0 (x) )
xεR
SC
ST
Rumus Original
S
BJ
u2 k 2 + u2 HB
BL
G
SI
CET
Rumus Original • Image region / pixel weighting
E( h ) =
Σ
xεR
[ I( x + h ) - I0 (x) ] 2
E( h ) =
Σ
[ I( x + h ) - I0 (x) ] 2
xεR
Rectangular:
LK
BAHH
ST
SC
S
BJ
HB
BL
G
SI
CET
21
Permasalahan E’
Generalisasi 6a • Image region / pixel weighting
Bagaimana bila background terjadi clutter (bergoyang)?
E( h ) =
Σ
[ I( x + h ) - I0 (x) ] 2
xεR
Irregular:
LK
BAHH
SC
ST
Permasalahan E”
S
BJ
HB
BL
G
SI
CET
Generalisasi 6b • Image region / pixel weighting
Bagaimana bila objek terhalang (foreground occlusion)?
E( h ) =
Σ
[ I( x + h ) - I0 (x) ] 2w(x)
xεR
Weighted sum:
LK
BAHH
ST
SC
S
BJ
HB
BL
G
SI
CET
22
Generalisasi metode Lucas-Kanade
Generalisasi 6c • Image region / pixel weighting
Modifikasi:
Σ
x εR
[ I( x + h ) - I0 (x) ] 2
E( h ) =
Σ
[ I( x + h ) - I0 (x) ] 2
xεR
Sampled:
LK
BAHH
ST
Generalisasi metode Lucas-Kanade: Ringkasan
E( h ) =
E( h ) =
Σ
x εR
S
BJ
HB
BL
G
[ I( x + h ) - I0 (x) ] 2
SI
CET
Ringkasan • Generalisasi
Σ ρ ( I( f(x, h)) - λΒ(x) ) w(x)
xεR
SC
– Dimension of image – Image transformations / motion models – Pixel type – Constancy assumption – Error norm – Image mask
L&K ? Y Y n Y n Y
23
Ringkasan • Common problems: – Local minima – Aperture effect – Illumination changes – Convergence issues – Outliers and occlusions
Ringkasan L&K ? Y maybe Y Y n
Penanganan aperture effect: – Manual intervention – Zero motion default – Coefficient “dampening” – Elimination of poor textures – Temporal filtering – Spatial interpolation / hierarchical – Higher-order terms
L&K ? n n n n Y Y n
24
