image registration & tracking dengan metode lucas & kanade

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



• Stereo

• Dense optic flow



• Stereo


• Image mosaics



• Stereo


• Image mosaics

• Tracking



• Stereo


• Image mosaics

• Tracking

• Recognition


?

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


Generalisasi 1a


h ) = x R

(E [I( x ) - (x ]2)+ h

y

xx2D:

I


Generalisasi 1b


h ) = x R

(E [I( x ) - (x ]2)+ h

1

y

x

xHomogeneous 2D:

I


Permasalahan A


Apakah iterasi bisa konvergen?

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


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):


Permasalahan B’

No gradient along one direction:

?

Jawaban problem A & B

• Possible solutions:– Manual intervention


• Possible solutions:– Manual intervention– Zero motion default



• Possible solutions:– Manual intervention– Zero motion default– Coefficient “dampening”



• Possible solutions:– Manual intervention– Zero motion default– Coefficient “dampening”– Reliance on good features



• Possible solutions:– Manual intervention– Zero motion default– Coefficient “dampening”– Reliance on good features– Temporal filtering



• Possible solutions:– Manual intervention– Zero motion default– Coefficient “dampening”– Reliance on good features– Temporal filtering– Spatial interpolation / hierarchical estimation



• Possible solutions:– Manual intervention– Zero motion default– Coefficient “dampening”– Reliance on good features– Temporal filtering– Spatial interpolation / hierarchical estimation– Higher-order terms



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


Permasalahan C

Bagaimana bila ada gerakan(motion) tipe lain?

Generalisasi 2a


A, h) = x R

(E [I(Ax ) - (x ]2)+h

Affine:

dc

baA

y

x

h

I


Generalisasi 2a

Affine:

dc

baA

y

x

h

Generalisasi 2b


A ) = x R

(E [I( A x ) - (x ]2)

Planar perspective:

187

654

321

aa

aaa

aaa

A

I


Generalisasi 2b

Planar perspective:

187

654

321

aa

aaa

aaa

A

Affine +

Generalisasi 2c


h ) = x R

(E [I( f(x, h) ) - (x ]2)

Other parametrized transformations

I


Generalisasi 2c

Other parametrized transformations

Permasalahan B”

-(JTJ)-1 J (I(f(x,h)) - I0(x)) h ~

Generalized aperture problem:


- 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


Generalisasi 3

• Image type

h ) = x R

(E ||I( x ) -I(x ||2)+ h

Color images


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


Permasalahan C

Bagaimana bila iluminasi cahaya bervariasi?

Generalisasi 4a

• Constancy assumption

h, )=x R

(E [I( x ) - I(x ]2)++ h

Linear brightness constancy


Generalisasi 4a

Generalisasi 4b


h,) = x R

(E [I( x ) - B(x]2)+ h

Illumination subspace constancy


Permasalahan C’

Bagaimana bila texture berubah?

Generalisasi 4c


h,) = x R

(E [I( x ) - ]2+ h

Texture subspace constancy

B(x)


Permasalahan D

Jelas proses konvergensi menjadi lambat bila jumlah #parameters

bertambah !!!

• Percepat konvergensi dengan:– Coarse-to-fine, filtering, interpolation, etc.


Jawaban problem D

• Percepat konvergensi dengan:– Coarse-to-fine, filtering, interpolation, etc. – Selective parametrization

Jawaban problem D


• Percepat konvergensi dengan:– Coarse-to-fine, filtering, interpolation, etc. – Selective parametrization – Offline precomputation

Jawaban problem D



• Difference decomposition

LK BAHH ST S BJ HB G SI CETSC

Jawaban problem D

BL

Jawaban problem D




– Improvements in gradient descent


Jawaban problem D

BL

• Percepat konvergensi dengan:– Coarse-to-fine, filtering, interpolation, etc. – Selective parametrization– Offline precomputation


– Improvements in gradient descent• Multiple estimates of spatial derivatives


Jawaban problem D

BL

Jawaban problem D

• Multiple estimates / state-space sampling


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:


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ρ


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:


Permasalahan E’

Bagaimana bila background terjadi clutter

(bergoyang)?

Generalisasi 6a


h ) = x R

(E [I( x ) -I(x ]2)+ h

Irregular:


Permasalahan E”

Bagaimana bila objek terhalang (foreground

occlusion)?

Generalisasi 6b


h ) = x R

(E [I( x ) -I(x ]2)+ h

Weighted sum:

w(x)



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

image registration & tracking dengan metode lucas & kanade

Documents