image registration & tracking dengan metode lucas & kanade
Post on 22-Jan-2016
49 Views
Preview:
DESCRIPTION
TRANSCRIPT
Image Registration & Tracking dengan Metode Lucas & Kanade
Sumber:-Forsyth & Ponce Chap. 19, 20-Tomashi & Kanade: Good Feature to Track
Feature Lucas-Kanade(LK)
• 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.
Sejarah Perkembangan LK
• Lucas & Kanade (IUW 1981)
LK BAHH ST S BJ HB BL G SI CETSC
• 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)
Image Registration
Penerapan metode LK
Penerapan pada aplikasi:
• Stereo
LK BAHH ST S BJ HB BL G SI CETSC
Penerapan pada aplikasi:
• Stereo
• Dense optic flow
LK BAHH ST S BJ HB BL G SI CETSC
Penerapan pada aplikasi:
• Stereo
• Dense optic flow
• Image mosaics
LK BAHH ST S BJ HB BL G SI CETSC
Penerapan pada aplikasi:
• Stereo
• Dense optic flow
• Image mosaics
• Tracking
LK BAHH ST S BJ HB BL G SI CETSC
Penerapan pada aplikasi:
• Stereo
• Dense optic flow
• Image mosaics
• Tracking
• Recognition
LK BAHH ST S BJ HB BL G SI CETSC
?
Derivasi RumusanLucas & Kanade
#1
rumusan L&K 1
I0(x)
)('0 xI
h
xIhxIh
)()(lim 00
0
)('0 xI
rumusan L&K 1
)('0 xI
h
xIhxI )()( 00
h I0(x)
I0(x+h)
rumusan L&K 1
h I0(x)
I(x)
rumusan L&K 1
h I0(x)
h)(
)()('0
0
xI
xIxI
I(x)
rumusan L&K 1
I0(x)
h
Rx xI
xIxI
R )(
)()(
||
1'0
0
RI(x)
rumusan L&K 1
I0(x)
h
RxxxI
xIxIxw
xw )(
)]()()[(
)(
1'0
0
I(x)
rumusan L&K 1
h0 I0(x)
0h
I(x)
RxxxI
xIxIxw
xw )(
)]()()[(
)(
1'0
0
rumusan L&K 1
1h
Rxx
hxI
hxIxIxw
xwh
)(
)]()()[(
)(
1
0'0
000
I0(x+h0)
I(x)
rumusan L&K 1
2h
Rxx
hxI
hxIxIxw
xwh
)(
)]()()[(
)(
1
1'0
101
I0(x+h1)
I(x)
rumusan L&K 1
1kh
Rx k
k
x
k hxI
hxIxIxw
xwh
)(
)]()()[(
)(
1'0
0
I0(x+hk)
I(x)
rumusan L&K 1
1kh
Rx k
k
x
k hxI
hxIxIxw
xwh
)(
)]()()[(
)(
1'0
0
I0(x+hf)
I(x)
Derivasi RumusanLucas & Kanade
#2
rumusan L&K 2
• Sum-of-squared-difference (SSD) error
E(h) = [ I(x) - I0(x+h) ]2x R
E(h) [ I(x) - I0(x) - hI0’(x) ]2x R
rumusan L&K 2
2[I0’(x)(I(x) - I0(x) ) - hI0’(x)2] x Rh
E
I0’(x)(I(x) - I0(x))x R h I0’(x)2
x R
= 0
Perbandingan
I0’(x)[I(x) - I0(x)] h I0’(x)2
x
x
h
w(x)[I(x) - I0(x)]
w(x)x
x I0’(x)
Perbandingan
I0’(x)[I(x) - I0(x)] h I0’(x)2
x
h
x
w(x)[I(x) - I0(x)]
w(x)x
x I0’(x)
Generalisasi metode Lucas-Kanade
Rumus Original
h ) = x R
(E [I( x ) - (x ]2)+ h I
Rumus Original
• Dimension of image
h ) = x R
(E [I( x ) - (x ]2)+ h
1-dimensional
I
LK BAHH ST S BJ HB BL G SI CETSC
Generalisasi 1a
• Dimension of image
h ) = x R
(E [I( x ) - (x ]2)+ h
y
xx2D:
I
LK BAHH ST S BJ HB BL G SI CETSC
Generalisasi 1b
• Dimension of image
h ) = x R
(E [I( x ) - (x ]2)+ h
1
y
x
xHomogeneous 2D:
I
LK BAHH ST S BJ HB BL G SI CETSC
Permasalahan A
LK BAHH ST S BJ HB BL G SI CETSC
Apakah iterasi bisa konvergen?
Permasalahan A
Local minima:
Permasalahan A
Local minima:
Permasalahan B
- I0’(x)(I(x) - I0(x))x R h I0’(x)2
x R
h is undefined if I0’(x)2 is zerox R
LK BAHH ST S BJ HB BL G SI CETSC
Zero gradient:
Permasalahan B
Zero gradient:
?
Permasalahan B’
- (x)(I(x) - I0(x))x R
hy 2
x R
y
I )(0 xy
I
)(0 x
Aperture problem (mis. Image datar):
LK BAHH ST S BJ HB BL G SI CETSC
Permasalahan B’
No gradient along one direction:
?
Jawaban problem A & B
• Possible solutions:– Manual intervention
LK BAHH ST S BJ HB BL G SI CETSC
• Possible solutions:– Manual intervention– Zero motion default
LK BAHH ST S BJ HB BL G SI CETSC
Jawaban problem A & B
• Possible solutions:– Manual intervention– Zero motion default– Coefficient “dampening”
LK BAHH ST S BJ HB BL G SI CETSC
Jawaban problem A & B
• Possible solutions:– Manual intervention– Zero motion default– Coefficient “dampening”– Reliance on good features
LK BAHH ST S BJ HB BL G SI CETSC
Jawaban problem A & B
• Possible solutions:– Manual intervention– Zero motion default– Coefficient “dampening”– Reliance on good features– Temporal filtering
LK BAHH ST S BJ HB BL G SI CETSC
Jawaban problem A & B
• Possible solutions:– Manual intervention– Zero motion default– Coefficient “dampening”– Reliance on good features– Temporal filtering– Spatial interpolation / hierarchical estimation
LK BAHH ST S BJ HB BL G SI CETSC
Jawaban problem A & B
• Possible solutions:– Manual intervention– Zero motion default– Coefficient “dampening”– Reliance on good features– Temporal filtering– Spatial interpolation / hierarchical estimation– Higher-order terms
LK BAHH ST S BJ HB BL G SI CETSC
Jawaban problem A & B
Kembali lagi: Rumus Original
h ) = x R
(E [I( x ) - (x ]2)+ h I
Rumus Original
• Transformations/warping of image
h ) = x R
(E [I( x ) -I(x ]2)+ h
Translations:
y
x
h
LK BAHH ST S BJ HB BL G SI CETSC
Permasalahan C
Bagaimana bila ada gerakan(motion) tipe lain?
Generalisasi 2a
• Transformations/warping of image
A, h) = x R
(E [I(Ax ) - (x ]2)+h
Affine:
dc
baA
y
x
h
I
LK BAHH ST S BJ HB BL G SI CETSC
Generalisasi 2a
Affine:
dc
baA
y
x
h
Generalisasi 2b
• Transformations/warping of image
A ) = x R
(E [I( A x ) - (x ]2)
Planar perspective:
187
654
321
aa
aaa
aaa
A
I
LK BAHH ST S BJ HB BL G SI CETSC
Generalisasi 2b
Planar perspective:
187
654
321
aa
aaa
aaa
A
Affine +
Generalisasi 2c
• Transformations/warping of image
h ) = x R
(E [I( f(x, h) ) - (x ]2)
Other parametrized transformations
I
LK BAHH ST S BJ HB BL G SI CETSC
Generalisasi 2c
Other parametrized transformations
Permasalahan B”
-(JTJ)-1 J (I(f(x,h)) - I0(x)) h ~
Generalized aperture problem:
LK BAHH ST S BJ HB BL G SI CETSC
- I0’(x)(I(x) - I0(x))x R h I0’(x)2
x R
Permasalahan B”
?
Generalizedaperture problem:
Rumus Original
h ) = x R
(E [I( x ) - (x ]2)+ h I
Rumus Original
• Image type
h ) = x R
(E [I( x ) - (x ]2)+ h
Grayscale images
I
LK BAHH ST S BJ HB BL G SI CETSC
Generalisasi 3
• Image type
h ) = x R
(E ||I( x ) -I(x ||2)+ h
Color images
LK BAHH ST S BJ HB BL G SI CETSC
Rumus Original
h ) = x R
(E [I( x ) - (x ]2)+ h I
Rumus Original
• Anggapan pixel punya konstan brightness (Constancy assumption)
h ) = x R
(E [I( x ) -I(x ]2)+ h
Brightness constancy
LK BAHH ST S BJ HB BL G SI CETSC
Permasalahan C
Bagaimana bila iluminasi cahaya bervariasi?
Generalisasi 4a
• Constancy assumption
h, )=x R
(E [I( x ) - I(x ]2)++ h
Linear brightness constancy
LK BAHH ST S BJ HB BL G SI CETSC
Generalisasi 4a
Generalisasi 4b
• Constancy assumption
h,) = x R
(E [I( x ) - B(x]2)+ h
Illumination subspace constancy
LK BAHH ST S BJ HB BL G SI CETSC
Permasalahan C’
Bagaimana bila texture berubah?
Generalisasi 4c
• Constancy assumption
h,) = x R
(E [I( x ) - ]2+ h
Texture subspace constancy
B(x)
LK BAHH ST S BJ HB BL G SI CETSC
Permasalahan D
Jelas proses konvergensi menjadi lambat bila jumlah #parameters
bertambah !!!
• Percepat konvergensi dengan:– Coarse-to-fine, filtering, interpolation, etc.
LK BAHH ST S BJ HB BL G SI CETSC
Jawaban problem D
• Percepat konvergensi dengan:– Coarse-to-fine, filtering, interpolation, etc. – Selective parametrization
Jawaban problem D
LK BAHH ST S BJ HB BL G SI CETSC
• Percepat konvergensi dengan:– Coarse-to-fine, filtering, interpolation, etc. – Selective parametrization – Offline precomputation
Jawaban problem D
LK BAHH ST S BJ HB BL G SI CETSC
• Percepat konvergensi dengan:– Coarse-to-fine, filtering, interpolation, etc. – Selective parametrization – Offline precomputation
• Difference decomposition
LK BAHH ST S BJ HB G SI CETSC
Jawaban problem D
BL
Jawaban problem D
• Difference decomposition
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 S BJ HB G SI CETSC
Jawaban problem D
BL
• Percepat konvergensi dengan:– Coarse-to-fine, filtering, interpolation, etc. – Selective parametrization– Offline precomputation
• Difference decomposition
– Improvements in gradient descent• Multiple estimates of spatial derivatives
LK BAHH ST S BJ HB G SI CETSC
Jawaban problem D
BL
Jawaban problem D
• Multiple estimates / state-space sampling
Generalisasi metode Lucas-Kanade
x R
[I( x ) - (x ]2)+ h I
Modifikasi yg. Dibuat selama ini adalah:
Rumus Original
• Error norm
h ) = x R
(E [I( x ) -I(x ]2)+ h
Squared difference:
LK BAHH ST S BJ HB BL G SI CETSC
Permasalahan E
Permasalahan dengan ourliers? >> Gunakan
robust norm
Generalisasi 5a
• Error norm
h ) = x R
(E (I( x ) -I(x ))+ h
Robust error norm:
22
2
)(uk
uuρ
LK BAHH ST S BJ HB BL G SI CETSC
Rumus Original
h ) = x R
(E [I( x ) - (x ]2)+ h I
Rumus Original
• Image region / pixel weighting
h ) = x R
(E [I( x ) -I(x ]2)+ h
Rectangular:
LK BAHH ST S BJ HB BL G SI CETSC
Permasalahan E’
Bagaimana bila background terjadi clutter
(bergoyang)?
Generalisasi 6a
• Image region / pixel weighting
h ) = x R
(E [I( x ) -I(x ]2)+ h
Irregular:
LK BAHH ST S BJ HB BL G SI CETSC
Permasalahan E”
Bagaimana bila objek terhalang (foreground
occlusion)?
Generalisasi 6b
• Image region / pixel weighting
h ) = x R
(E [I( x ) -I(x ]2)+ h
Weighted sum:
w(x)
LK BAHH ST S BJ HB BL G SI CETSC
Generalisasi metode Lucas-Kanade
x R
[I( x ) - (x ]2)+ h I
Modifikasi:
Generalisasi metode Lucas-Kanade: Ringkasan
= x R
(I( ) - w(x) (x ))h )(E f(x, h)
h ) = x R
(E [I( x ) - (x ]2)+ h I
Ringkasan
• Generalisasi– Dimension of image– Image transformations / motion models– Pixel type– Constancy assumption– Error norm– Image mask
L&K ?Y
Y
n
Y
n
Y
Ringkasan
• Common problems:– Local minima– Aperture effect– Illumination changes– Convergence issues– Outliers and occlusions
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
Ringkasan
L&K ?n
n
n
n
Y
Y
n
top related