Digital Image Processing 1

Digital Image Processing

Introduction
Object tracking
&
Motion detection
in video sequences
http://cmp.felk.cvut.cz/~hlavac/TeachPresEn/17CompVision3D/1!ma"e#otion.p$f
%ecomen$e$ link:
Digital Image Processing 2
Digital Image Processing 3
DYNMI! "!#N# N$Y"I"
The input to the $'namic scene
anal'sis is a se(uence of ima"e
frames F) x, y, t * taken from the
chan"in" +orl$.
x, y are spatial coor$inates.
,rames are usuall' capture$ at
fi-e$ time intervals.
t represents t.th frame in the
se(uence.
Digital Image Processing %
Motion detection. /ften from a static camera. Common in
surveillance s'stems. /ften performe$ on the pi-el level onl'
)$ue to spee$ constraints*.
Object localization. ,ocuses attention to a re"ion of interest in
the ima"e. Data re$uction. /ften onl' interest points foun$
+hich are use$ later to solve the correspon$ence pro0lem.
Motion segmentation !ma"es are se"mente$ into re"ion
correspon$in" to $ifferent movin" o01ects.
Three-dimensional shape from motion. Calle$ also structure
from motion. 2imilar pro0lems as in stereo vision.
Object tracking. 3 sparse set of features is often tracke$4 e.".4
corner points.
&'(ical ((likations
Digital Image Processing )
Pedestrians in underground
station
Digital Image Processing *
3ssumin" that the scene illumination $oes not
chan"e4 the ima"e chan"es are $ue to relative
motion 0et+een the scene o01ects an$ the
camera )o0server*.
There are three possi0ilities:
2tationar' camera4 movin" o01ects.
#ovin" camera4 stationar' o01ects.
#ovin" camera4 movin" o01ects.
Problem de+inition
Digital Image Processing ,
Motion +ield
5#otion fiel$ is a 6D representation in the ima"e plane
of a )"enerall'* 3D motion of points in the scene
)t'picall' on surfaces of o01ects*.
5To the each point is assigned a velocity vector
corresponding to the motion direction and velocity
magnitude.
Digital Image Processing -
Motion +ield

#.amle/
Digital Image Processing 0
#stimating motion +ield
1. #atchin" of 0locks.
6. #atchin" of o01ects. !nterpretation nee$e$. 3 sparse
motion fiel$.
3. #atchin" of interest points. 3 0it $enser motion fiel$. 3
more $ifficult interpretation. Pro0lems +ith repetitive
structures.
. /ptic flo+4 a $ifferential techni(ue matchin" intensities
on a pi-ellevel4 e-plorin" spatial an$ time variations.
!$eall'4 a $ense motion fiel$. Pro0lems for te-tureless
parts of ima"es $ue to aperture pro0lem )to 0e
e-plaine$*.
Digital Image Processing
"egmentation in 1ideo2
sequences

7ack"roun$ 2u0traction

first must 0e $efine$ a mo$el of the

0ack"roun$

this background model is compare$ a"ainst

the current ima"e an$ then the kno+n
0ack"roun$ parts are su0tracte$ a+a'.

The o01ects left after su0traction are

presuma0l' ne+ fore"roun$ o01ects.
Digital Image Processing 11
#stablis3ing a 4e+erence
Images
#stablis3ing a 4e+erence Images/
5 Di++erence 6ill erase static object/
7 83en a d'namic object move out com(letel' +rom its
(osition9 t3e back ground in re(laced:
Digital Image Processing 12
Object tracking

/01ect trackin" is the pro0lem of $eterminin"

)estimatin"* the positions an$ other relevant
information of movin" o01ects in ima"e se(uences.

T+o.frame trackin" can 0e accomplishe$ usin":

correlation.0ase$ matchin" metho$s

feature.0ase$ metho$s

optical flo+ techni(ues

chan"e.0ase$ movin" o01ect $etection metho$s

Digital Image Processing 13
Main di++iculties in reliable
tracking o+ moving objects

%api$ appearance chan"es cause$ 0'

ima"e noise4

illumination chan"es4

non.ri"i$ motion4

...

8on.sta0le 0ack"roun$

!nteraction 0et+een multiple multiple o01ects

...
Digital Image Processing 1%
;lock matc3ing met3od

Correlation.0ase$ trackin" is 7# metho$

,or a "iven re"ion in one frame4 fin$ the

correspon$in" re"ion in the ne-t frame 0'
fin$in" the ma-imum correlation score )or
other 0lock matchin" criteria* in a search
re"ion

7locks are t'picall' s(uare$ an$ overlappe$

Digital Image Processing 1)
;lock matc3ing met3od
Digital Image Processing 1*
1isible Motion and &rue Motion

9enerall'4 optical
flo+ correspon$s to
the motion fiel$4 0ut
not al+a's.

,or e-ample4 the

motion fiel$ an$
optical flo+ of a
rotatin" 0ar0er:s
pole are $ifferent...
Digital Image Processing 1,
Motion +ield < O(tical +lo6
5

/ptical flo+ is a vector fiel$4 from +hich the motion fiel$

can 0e estimate$ un$er certain con$itions.
z ; unit vector in the a-is z $irection.
f ; focal len"th of a lens.
vi < $ ri
$ t ; velocit' in the ima"e plane.
v < $ r
$ t ; velocit' in the 3D space.
Digital Image Processing 1-
O(tical +lo6
OPTIC FO! " apparent motion of the same #similar$
intensit% patterns
!$eall'4 the optic flo+ can appro-imate pro1ections of the
three.$imensional motion )i.e.4 velocit'* vectors onto the
ima"e plane.
=ence4 the optic flo+ is estimate$ instea$ of the motion
fiel$ )since the latter is uno0serva0le in "eneral*.
Digital Image Processing 10
(erture (roblem

7' anal'zin" pro1ecte$ ima"es4 +e al+a's o0serve a

limite$ area of visi0le motion onl' )$efine$ 0' aperture
of the camera or of the area of influence of the use$
al"orithm for motion anal'sis*.
Digital Image Processing 2=
(erture (roblem 2e.am(le
5 ,or e-ample4 assume that +e either onl' see the
inner rectan"les4 or the +hole three ima"es taken at
times t4 t > 14 t > 6. ,or the inner rectan"les4 +e ma'
conclu$e an up+ar$ translation +ith a minor rotation....
Digital Image Processing 21
(erture (roblem

+e are onl' a0le to

measure the
component of optical
flo+ that is in the
$irection of the intensit'
"ra$ient. ?e are
una0le to measure the
component tan"ential
to the intensit' "ra$ient.
Digital Image Processing 22
O(tical +lo6

tar"et features are

tracke$ over time
an$ their movement
is converte$ into
velocit' vectors
)upper ri"ht*@

lo+er panels sho+ a

sin"le ima"e of the
hall+a' )left *an$
flo+ vectors )ri"ht* as
the camera moves
$o+n the hall

)ori"inal ima"es courtes' of Aean.Bves 7ou"uet*

Digital Image Processing 23
O(tical +lo6
Common ass&mption -
Common ass&mption -
Brightness constancy
Brightness constancy
'
'
The appearance of the image patches
The appearance of the image patches
do not change #brightness constanc%$
do not change #brightness constanc%$
) 1 , ( ) , ( + + t v p I t p I
i i i

3 pi-el from the ima"e of an o01ect in the scene $oes not
chan"e in appearance as it )possi0l'* moves from frame
to frame. ,or "ra'scale ima"es this means +e assume
that the 0ri"htness of a pi-el $oes not chan"e as it is
tracke$ from frame to frame.
Digital Image Processing 2%
O(tical >lo6 ssum(tions/
;rig3tness constanc'
Digital Image Processing 2)
O(tical >lo6 ssum(tions/

Digital Image Processing 2*
O(tical >lo6 ssum(tions/
&em(oral (ersistence

Temporal persistence or small movements. The ima"e motion of a

surface patch chan"es slo+l' in time. !n practice4 this means the
temporal increments are fast enou"h relative to the scale of motion
in the ima"e that the o01ect $oes not move much from frame to
frame.
Digital Image Processing 2,
O(tical >lo6/ 1D !ase

7ri"htness Constanc' 3ssumption:
) ), ( ( ) ), ( ( ) ( dt t dt t x I t t x I t f + +
0
) (

,
_

t x t
t
I
t
x
x
I

x
v
t
x
t
I
I
v
{
0
) (

t
x f
7ecause no chan"e in 0ri"htness +ith time
Digital Image Processing 2-
v

x
I
(patial derivative (patial derivative
Temporal derivative Temporal derivative
t
I
&racking in t3e 1D case/
x
) , ( t x I
) 1 , ( + t x I
p
t
x
x
I
I

p x
t
t
I
I

x
t
I
I
v

)ss&mptions' )ss&mptions'
5
*rightness constanc% *rightness constanc%
5
(mall motion (mall motion
Digital Image Processing 20
&racking in t3e 1D case/
x
) , ( t x I
) 1 , ( + t x I
p
x
I
t
I
Temporal derivative at + Temporal derivative at +
nd nd
iteration iteration
Iterating helps refining the velocit% vector Iterating helps refining the velocit% vector
Can keep the same estimate for spatial derivative Can keep the same estimate for spatial derivative
x
t
previous
I
I
v v

Converges in abo&t , iterations Converges in abo&t , iterations
Digital Image Processing 3=
>rom 1D to 2D tracking
The Math is ver% similar' The Math is ver% similar'
v

x
) , ( t x I
) 1 , ( + t x I
1
v

2
v

3
v

4
v

x
y
) 1 , , ( + t y x I
) , , ( t y x I
x
t
I
I
v

b G v
1

1
]
1

p y y x
y x x
I I I
I I I
G
around window
2
2
1
]
1

p t y
t x
I I
I I
b
around window
Digital Image Processing 31
?$& in P'ramids
Pro0lem:
+e +ant a lar"e +in$o+ to catch lar"e motions4
0ut a lar"e +in$o+ too oft en 0reaks the coherent
motion assumptionC
To circumvent this pro0lem4 +e can track first over
lar"er spatial scales usin" an ima"e p'rami$ an$
then refine the initial motion velocit' assumptions
0' +orkin" our +a' $o+n the levels of the ima"e
p'rami$ until +e arrive at the ra+ ima"e pi-els.
Digital Image Processing 32
?$& in P'ramids
,irst solve optical flo+ at the top la'er an$
then to use the resultin" motion estimates as the
startin" point for the ne-t la'er $o+n.
?e continue "oin" $o+n the p'rami$ in this manner
until +e reach the lo+est level.
Thus +e minimize the violations of our motion
assumptions an$ so can track faster an$ lon"er
motions.
image I
image J
Gaussian pyramid of image I
t-1
Gaussian pyramid of image I
image I image I
t-1
!oarse2to2+ine o(tical +lo6
estimation
run iterative D.E
run iterative D.E
+arp F upsample
.
.
.
Digital Image Processing 3%
#dge
;
lar"e "ra$ients4 all the same
; lar"e
1
4 small
6
G ,rom Ehurram =assan.2hafi(ue C3PH1H Computer Vision 6II3
Digital Image Processing 3)
$o6 te.ture region
;
"ra$ients have small ma"nitu$e
; small
1
4 small
6
G ,rom Ehurram =assan.2hafi(ue C3PH1H Computer Vision 6II3
Digital Image Processing 3*
@ig3 te.tured region
;
"ra$ients are $ifferent4 lar"e ma"nitu$es
; lar"e
1
4 lar"e
6
G ,rom Ehurram =assan.2hafi(ue C3PH1H Computer Vision 6II3
Digital Image Processing 3,
$ocal +eatures +or tracking

...There are many kinds of local features that one

can track...

!f stron" $erivatives are o0serve$ in t+o

ortho"onal $irections then +e can hope that this
point is more likel' to 0e uni(ue.

<J man' tracka0le features are calle$ corners.

!ntuitivel'4 cornersKnot e$"esKare the points
that contain enou"h information to 0e picke$ out
from one frame to the ne-t.
Digital Image Processing 3-
@arris corner detection

The $efinition relies on the matri- of the secon$.

or$er $erivatives )L6x4 L6 y4 Lx Ly* of the ima"e
intensities.
=essian matri- aroun$ a
point:
!utocorrelation matrix of the secon$ $erivative
ima"es over a small +in$o+ aroun$ each point:
Digital Image Processing 30
@arris corner detection
5

=arrisMs $efinition:

Corners are places in the ima"e +here the

autocorrelation matri- of the secon$ $erivatives has
t+o lar"e ei"envalues.

<J there is te-ture )or e$"es* "oin" in at least t-o

separate directions

these t+o ei"envalues $o more than $etermine if a

point is a "oo$ feature to track@ the' also provi$e an
i$entif'in" si"nature for the point.
Digital Image Processing %=
"3i and &omasi/
Aood >eatures to &rack

2hi an$ Tomasi:

9oo$ corner results as lon" as the smaller of

the t+o ei"envalues is "reater than a
minimum threshol$.

2hi an$ TomasiMs metho$ +as not onl'

sufficient 0ut in man' cases "ave more
satisfactor' results than =arrisMs metho$.
Digital Image Processing %1
Alobal a((roac3/
@orn2"c3unck

3 metho$ for fin$in" the optical flo+ pattern +hich

assumes that the apparent velocit' of the
0ri"htness pattern varies smoothl' almost
ever'+here in the ima"e.

3n iterative implementation computes the optical

flo+ of each pi-el.
!om(uter 1ision 2 >all 2==1Digital
Image Processing %2
=orn.2chunck 3l"orithm

&6o criteria/

O(tical +lo6 is smoot39 F

s
Bu9vC

"mall error in o(tical +lo6 constraint equation9 F

3
Bu9vC

MinimiDe a combined error +unctional

F
c
Bu9vC E F
s
Bu9vC F G F
3
Bu9vC
G is a 6eig3ting (arameter

1ariation calculus gives a (air o+ second order

di++erential equations t3at can be solved
iterativel'
Digital Image Processing %3
dvantages < Disadvantages
o+ t3e @orn5"c3unck algorit3m

dvantages /

it 'ields a 3ig3 densit' o+ +lo6 vectors9 i:e: t3e +lo6

in+ormation missing in inner (arts o+ 3omogeneous
objects is +illed in +rom t3e motion boundaries:

Disadvantages/

it is more sensitive to noise than local metho$s.

The =orn.2chunck metho$ is ver' unsta0le in case

of illumination artifacts in ima"e se(uences )$ue to
the assume$ 0ri"htness constanc'*.
!om(uter 1ision 2 >all 2==1Digital
Image Processing %%
Mean2"3i+t &racking

Mean-(hift in tracking task'

track the motion of a cluster of interestin"

features.

1. choose the feature $istri0ution to represent

an o01ect )e.".4 color > te-ture*4

6. start the mean.shift +in$o+ over the feature

$istri0ution "enerate$ 0' the o01ect

3. finall' compute the chosen feature

$istri0ution over the ne-t vi$eo frame.
!om(uter 1ision 2 >all 2==1Digital
Image Processing %)
Mean2"3i+t &racking

2tartin" from the current +in$o+ location4 the

mean.shift al"orithm +ill fin$ the ne+ peak or
mo$e of the feature $istri0ution4 +hich
)presuma0l'* is centere$ over the o01ect that
pro$uce$ the color an$ te-ture in the fi rst
place.

<J !n this +a'4 the mean.shift +in$o+ tracks

the movement of the o01ect frame 0' frame.
!om(uter 1ision 2 >all 2==1Digital
Image Processing %*
Mean2s3i+t algorit3m in action

3n initial +in$o+ is
place$ over a t+o.
$imensional arra' of
$ata points an$ is
successivel'
recentere$ over the
mo$e )or local peak*
of its $ata $istri0ution
until conver"ence
!om(uter 1ision 2 >all 2==1Digital
Image Processing %,
Mean2s3i+t algorit3m

The mean.shift al"orithm runs as follo+s:

1. Choose a search +in$o+:

5 its initial location@

5 its t'pe )uniform4 pol'nomial4 e-ponential4 or

9aussian*@

5 its shape )s'mmetric or ske+e$4 possi0l' rotate$4

roun$e$ or rectan"ular*@

5 its size )e-tent at +hich it rolls off or is cut off *.

6. Compute the +in$o+Ms )possi0l' +ei"hte$* center of

mass.

3. Center the +in$o+ at the center of mass.

. %eturn to step 6 until the +in$o+ stops movin" )it al+a's

+ill*.G
!om(uter 1ision 2 >all 2==1Digital
Image Processing %-
!ams3i+t 2
continuousl' a$aptive mean.shift

!t $iffers from the meanshift in that the search

+in$o+ a$1usts itself in size.
!om(uter 1ision 2 >all 2==1Digital
Image Processing %0
Motion &em(lates

Track "eneral movement an$ are especiall' applica0le to

"esture reco"nition.

9ra$ient metho$

Nsin" motion templates re(uires a silho&ette )or part of a

silhouette* of an o01ect.
!om(uter 1ision 2 >all 2==1Digital
Image Processing )=
Motion &em(lates
Object sil3ouettes/

Object silho&ettes can 0e o0taine$ in a num0er of

+a's:

1. use a reasona0l' stationar' camera an$ then

emplo' frame.to.frame $ifferencin" . Th is +ill "ive
'ou the movin" e$"es of o01ects4 +hich is enou"h
to make motion templates +ork.

6. Bou can use chroma ke'in". ,or e-ample4 if 'ou

have a kno+n 0ack"roun$4 'ou can simpl' take as
fore"roun$ an'thin" that is not 0ack"roun$.
!om(uter 1ision 2 >all 2==1Digital
Image Processing )1
Motion &em(lates
Object sil3ouettes/
To learn a backgro&nd model from -hich %o& can
isolate ne- foregro&nd objects.people as
silho&ettes.
1. Bou can use active silhouettin" techni(uesKfor
e-ample4 creatin" a +all of nearinfrare$ li"ht an$
havin" a near.infrare$.sensitive camera look at the
+all. 3n' intervenin" o01ect +ill sho+ up as a
silhouette.
6. Bou can use thermal ima"es@ then an' hot o01ect
)such as a face* can 0e taken as fore"roun$.
3. ,inall'4 'ou can "enerate silhouettes 0' usin" the
se"mentation techni(ues ....
http://+++.'outu0e.com/+atchOv<.?n7$vPnz03
Digital Image Processing )2
&racking !ars Hsing O(tical
>lo6 4esults 2Mat36orks

The mo$el
locates the cars
in each 0inar'
feature ima"e
usin" the 7lo0
3nal'sis 0lock.

The mo$el uses an optical flo+ estimation techni(ue to
estimate the motion vectors in each frame of the vi$eo
se(uence.
7' threshol$in" an$ performin" morpholo"ical closin" on the
motion vectors4 the mo$el pro$uces 0inar' feature ima"es.
Digital Image Processing )3
!3ange2based blob tracking

3l"orithm

Calculate the 0ack"roun$

!ma"e su0traction to $etection motion 0lo0s

Compute the $ifference ima"e 0et+een t+o frames

Threshol$in" to fin$ the 0lo0s

Docate the 0lo0 center as the position of the o01ect

Digital Image Processing )%

#stimation 2 Prediction

!n a lon" ima"e se(uence4 if the $'namics of the

movin" o01ect is kno+n4 pre$iction can 0e ma$e
a0out the positions of the o01ects in the current
ima"e. This information can 0e com0ine$ +ith the
actual ima"e o0servation to achieve more ro0ust
results
Digital Image Processing ))
Prediction

"'stem
Digital Image Processing )*
Model o+ s'stem

Model o+ s'stem
Digital Image Processing ),
&racking +ormulated using t3e
@idden Markov model B@MMC

=i$$en #arkov mo$el )=##*:

Digital Image Processing )-
&racking +ormulated using t3e
@idden Markov model

The state xk usuall' consists of the position4 the

velocit'4 the acceleration4 an$ other features of the
o01ect

The o0servation zk is usuall' the vi$eo frame at

current time instance.

The transition pro0a0ilit' is mo$ele$ usin" $'namic

mo$el such as constant velocit' mo$el4 or constant
acceleration mo$el

E-ample: 3 constant velocit' $'namic mo$el

Digital Image Processing )0
&3e d'namic s'stem
Digital Image Processing *=
&3e d'namic s'stem

"eneral pro0lem of tr'in" to estimate the state x of a $iscrete.time controlle$

process is "overne$ 0' the linear stochastic $ifference e(uation
+ith a measurement z that is:
The ran$om varia0les "k an$ vk represent the process an$ measurement noise
)respectivel'*.
The' are assume$ to 0e in$epen$ent )of each other*4 +hite4 an$ +ith normal
pro0a0ilit' $istri0utions
!n practice4 the process noise covariance Q
an$
measurement noise covariance # matrices mi"ht change
"ith each time step or measurement, ho"ever here "e
assume they are constant.
Digital Image Processing *1
?alman +ilter
5The Ealman filter is a set of mathematical
e(uations that provi$es an efficient
computational )recursive* means to estimate the
state of a process4 in a +a' that minimizes the
mean of the s(uare$ error.
Digital Image Processing *2
?alman +ilter

T+o "roups of the e(uations for the Ealman filter:

time update e(uations

an$ measurement update e(uations.

The time up$ate e(uations are responsi0le for pro1ectin" for+ar$ )in time* the
current state an$ error covariance estimates to o0tain the a priori estimates for
the ne-t time step.
The measurement up$ate e(uations are responsi0le for the fee$0ackKi.e. for
incorporatin" a ne+ measurement into the a priori estimate to o0tain an
improve$ a posteriori estimate.
Digital Image Processing *3
?alman +ilter

the time up$ate e(uations can also 0e thou"ht of as predictor e(uations

the measurement up$ate e(uations can 0e thou"ht of as corrector

e(uations.

predictor$corrector al"orithm <J solvin" numerical pro0lems:

Discrete Ealman filter

time up$ate e(uations:
Discrete Ealman filter
measurement up$ate e(uations:
time update equations project the state and covariance estimates
forward from time step k-1 to step k .