COMP9517: Computer Vision
Motion
Week 7 COMP9517 2021 T1 1
Introduction
• Addingthetimedimensiontotheimageformation
Week 7 COMP9517 2021 T1 2
Introduction
• Achangingscenemaybeobservedviaasequenceof images
Week 7 COMP9517 2021 T1 3
Introduction
• Changesinanimagesequenceprovidefeaturesfor
Week 7
COMP9517 2021 T1 4
– – – – – –
detecting objects that are moving
computing trajectories of moving objects performing motion analysis of moving objects recognising objects based on their behaviours computing the motion of the viewer in the world detecting and recognising activities in a scene
Applications
• Motion-based recognition
– human identification based on gait, automatic object detection
• Automated surveillance
– monitoring a scene to detect suspicious activities or unlikely events
• Video indexing
– automatic annotation and retrieval of videos in multimedia databases
• Human-computer interaction
– gesture recognition, eye gaze tracking for data input to computers
• Traffic monitoring
– real-time gathering of traffic statistics to direct traffic flow
• Vehicle navigation
– video-based path planning and obstacle avoidance capabilities
Week 7 COMP9517 2021 T1 5
Scenarios
• Still camera
Constant background with
– singlemovingobject
– multiplemovingobjects
• Moving camera
Relatively constant scene with
– – –
coherent scene motion singlemovingobject multiplemovingobjects
Week 7
COMP9517 2021 T1 6
Topics
• Change detection
Using image subtraction to detect changes in scenes
• Sparse motion estimation
Using template matching to estimate local displacements
• Dense motion estimation
Using optical flow to compute a dense motion vector field
Week 7 COMP9517 2021 T1 7
Change Detection
Week 7 COMP9517 2021 T1 8
Change Detection
• Detectinganobjectmovingacrossaconstant background
• Theforwardandrearedgesoftheobjectadvance only a few pixels per frame
• By subtracting the image It from the previous image It-1 the edges should be evident as the only pixels significantly different from zero
Week 7 COMP9517 2021 T1 9
Image Subtraction
Step: Derive a background image from a set of video frames at the beginning of the video sequence
PETS 2009 Benchmark
Week 7 COMP9517 2021 T1
10
Image Subtraction
Step: Subtract the background image from each subsequent frame to create a difference image
–
Week 7 COMP9517 2021 T1 11
Image Subtraction
Step: Threshold and enhance the difference image to fuse neighbouring regions and remove noise
Week 7 COMP9517 2021 T1 12
Change Detection • Imagesubtractionalgorithm
Week 7
COMP9517 2021 T1 13
– – – –
1.
2. 3. 4. 5. 6.
Input: images It and It-Δt (or a model image) Input: an intensity threshold τ
Output: a binary image Iout
Output: a set of bounding boxes B
For all pixels [r, c] in the input images,
set Iout[r, c] = 1 if (|It[r, c] –It-Δt[r, c]|>τ)
set Iout[r, c] = 0 otherwise
Perform connected components extraction on Iout
Remove small regions in Iout assuming they are noise
Perform a closing of Iout using a small disk to fuse neighbouring regions Compute the bounding boxes of all remaining regions of changed pixels Return Iout[r, c] and the bounding boxes B of regions of changed pixels
Sparse Motion Estimation
Week 7 COMP9517 2021 T1 14
Motion Vector
• Amotionfieldisa2Darrayof2Dvectors representing the motion of 3D scene points
• Amotionvectorintheimagerepresentsthe displacement of the image of a moving 3D point
– Tail at time t and head at time t+Δt
– Instantaneous velocity estimate at time t
Zoom out Zoom in Pan Left
Week 7 COMP9517 2021 T1
15
Sparse Motion Estimation
• Asparsemotionfieldcanbecomputedbyidentifying pairs of points that correspond in two images taken at times t and t+Δt
• Assumption:intensitiesof interesting points and their neighbours remain nearly constant over time
• Twosteps:
– Detect interesting points at t
– Searchcorrespondingpointsatt+Δt
Week 7 COMP9517 2021 T1 16
Sparse Motion Estimation • Detectinterestingpoints
– Imagefilters
• Canny edge detector
• Kirsch edge operator
• Harris corner detector
• SUSAN corner detector
• Frei-Chen ripple operator •…
– Interest operator
Week 7
COMP9517 2021 T1 17
• •
Computes intensity variance in the vertical, horizontal and diagonal directions
Interest point if the minimum of these four variances exceeds a threshold
Week 7
COMP9517 2021 T1 18
Detect Interesting Points
Procedure detect_interesting_points(I,V,w,t) { for (r = 0 to MaxRow – 1)
for (c = 0 to MaxCol – 1)
if (I[r,c] is a border pixel) break;
else if (interest_operator(I,r,c,w) >= t)
add (r,c) to set V;
}
Procedure interest_operator (I,r,c,w) {
v1 = variance of intensity of horizontal pixels I[r,c-w]…I[r,c+w];
v2 = variance of intensity of vertical pixels I[r-w,c]…I[r+w,c];
v3 = variance of intensity of diagonal pixels I[r-w,c-w]…I[r+w,c+w]; v4 = variance of intensity of diagonal pixels I[r-w,c+w]…I[r+w,c-w]; return min(v1, v2, v3, v4);
}
Sparse Motion Estimation • Searchcorrespondingpoints
– Given an interesting point Pi from It, take its neighbourhood in It and find the best matching neighbourhood in It+Δt under the assumption that the amount of movement is limited
Pi
T
search P region i
best
matching neighbourhood
Qi
motion vector (enlarged)
It Qi
It+Δt
This approach is also known as template matching
Week 7 COMP9517 2021 T1 19
Similarity Measures • Cross-correlation(tobemaximised)
CC(∆x,∆y) = ∑ It (x, y)⋅ It+∆t (x + ∆x, y + ∆y) (x,y)∈T
• Sumofabsolutedifferences(tobeminimised) SAD(∆x,∆y) = ∑ ( ) ( − )
It x,y It+∆t x+∆x,y+∆y (x,y)∈T
• Sumofsquareddifferences(tobeminimised) SSD(∆x,∆y)=()(− )
Week 7
COMP9517 2021 T1 20
It x,y It+∆t x+∆x,y+∆y ∑ 2
(x,y)∈T
Similarity Measures • Mutualinformation(tobemaximised)
MI(A,B)=∑∑P (a,b)log P (a,b)
ab
Subimages to compare:
A ⊂ It B ⊂ It +∆t Intensity probabilities:
PA (a) PB (b)
Joint intensity probability:
P (a,b) AB
Week 7
PB (b)
B AB
AB 2AB P (a)P (b)
A
COMP9517 2021 T1
P(a)
A AB
P (a,b) http://dx.doi.org/10.1016/j.jbi.2011.04.008 21
Dense Motion Estimation
Week 7 COMP9517 2021 T1 22
Dense Motion Estimation • Assumptions:
– The object reflectivity and illumination do not change during the considered time interval
– The distance of the object from the camera and the light sources do not vary significantly over this interval
– Each small neighbourhood Nt(x,y) at time t is observed in some shifted position Nt+Δt(x+Δx,y+Δy) at time t+Δt
• Theseassumptionsmaynotholdtightinreality,but provide useful computation and approximation
Week 7 COMP9517 2021 T1 23
Spatiotemporal Gradient • Taylorseriesexpansionofafunction
f(x+∆x)=f(x) ∂f+x h∆.o.+t ⇒ ∂x
f(x+∆x)≈ f(x)+∂f ∆x ∂x
• MultivariableTaylorseriesapproximation
f(x+∆x,y+∆y,t+∆t)≈ f(x,y,t)+∂f ∆x+∂f ∆y+∂f ∆t ∂x ∂y ∂t
(1)
Week 7 COMP9517 2021 T1
24
Optical Flow Equation
Assuming neighbourhood Nt(x, y) at time t moves over vector V=(Δx, Δy) to an identical neighbourhood Nt+Δt(x+Δx, y+Δy) at time t+Δt leads to the optical flow equation:
f(x+∆x,y+∆y,t+∆t)= f(x,y,t) (2)
Week 7
COMP9517 2021 T1
25
t
t+Δt
Optical Flow Computation Combining (1) and (2) yields the following constraint:
∂f ∆x+∂f ∆y+∂f ∆t=0⇒ ∂x ∂y ∂t
∂f∆x ∂f∆y ∂f∆t
+ + ⇒=0
∂x ∆t ∂y ∆t ∂t ∆t ∂ f v + ∂ f v + ∂ f = 0⇒
∂x x ∂y y ∂t ∇f⋅v=− ft
Week 7
COMP9517 2021 T1 26
where v = (v ,v ) is the velocity or optical flow of f (x, y,t)
and∇f=(fx,fy)=∂( f/∂x,∂f/∂y)isthegradient xy
Optical Flow Computation
• Theopticalflowequationprovidesaconstraintthat can be applied at every pixel position
• However,theequationdoesnothaveuniquesolution and thus further constraints are required
For example, by using the optical flow equation for a group of adjacent pixels and assuming that all of them have the same velocity, the optical flow computation task amounts to solving a linear system of equations using the least-squares method
Many other solutions have been proposed (see references)
Week 7 COMP9517 2021 T1 27
Optical Flow Computation
• Example:Lucas-Kanadeapproachtoopticalflow
Assume the optical flow equation holds for all pixels 𝑝𝑝𝑖𝑖 in a certain neighbourhood and use the following notation:
v = (v ,v ) f = ∂f fy = ∂f f = ∂f x y x ∂x ∂y t ∂t
Then we have the following set of equations:
f ( p ) v + f −( p ) v = f ( p ) x1xy1y t1
fx(p2)vx+fy−(p2)vy = ft(p2)
fx(pN)vx+fy−(pN)vy= ft(pN)
Week 7 COMP9517 2021 T1 28
Optical Flow Computation
• Example:Lucas-Kanadeapproachtoopticalflow
The set of equations can be rewritten as Av = b where
f(p) f(p) x1y1
f (p ) f (p )
A=x2 y2 v=xb=t2
v
xNyN tN
vy
This can be solved using the least-squares approach:
f(p) f(p) −f(p)
⇒ −1 TT(T)T
AAv=Ab v=AA Ab
Week 7 COMP9517 2021 T1 29
−f(p)
t1
−f (p )
Optical Flow Example
Week 7 COMP9517 2021 T1 30
References and Acknowledgements
• Chapter8ofSzeliski2010
• Chapter9ofShapiroandStockman2001 • Imagesdrawnfromtheabovereferences
Week 7 COMP9517 2021 T1 32