Computer Vision and Pattern Recognition
L10. Shape Representation
Dr John Collomosse
[Link]@[Link]
Centre for Vision, Speech and Signal Processing
University of Surrey
Learning Outcomes
After attending this lecture, and doing the reading you
should be able to:
Understand and apply the Hough transform to find simple shapes in images
Explain the term “connected component” and be able to describe how to
separate connected components in an image.
Describe several global shape descriptors (shape factors) for characterising
shape
Recommend solutions to shape recognition tasks
Calculate 1D moments and understand their relationship to basic statistical
quantities
Motivation
Detecting geometric structures e.g. lines in edge maps (e.g. Sobel)
Can be complicated by occlusion, illumination etc.
Bottom-up approach
Walk along runs of edge pixels
At the end of a pixel run, link up
to nearby edge pixel that haven’t
yet been visited
Local
Decision
Making
Top-down approach
Parameterise the model (line) and fit the model
Global vs. local approach
y
line described by (r,)
r
x
The line is infinitely long
What ranges of r and will
enable us to cover all
possible lines?
Line parameterisation
Avoid y=mx+c due to infinite gradient of vertical lines
line described by (r,) r = x cos() + y sin().
Intercept
Intercept . sin = r r
x
Line parameterisation
A way to find the best line – (r, ) for a given image
The best line passes through the most edge pixels
y
line described by (r,)
Each point (r, ) in parameter space
r represents a line in the image
x
r Parameter space
0 2
Hough Transform
Quantize the parameter space into a voting (accumulator space)
y
For each edge pixel in the image
find all lines (r,) passing through it
Parameter space divided into cells
which act as vote counters (init=0)
r
Parameter space
0
2
x
Hough Transform
How to find all the lines passing through (x,y) ?
y For theta = 0 to 2
r() = x cos() + y sin().
End for
r
Parameter space
0
2
x
Hough Transform
Example of an accumulator (Hough) space
Bright peaks are the maxima (lines with most votes)
Over to You
What do you think is the main advantage of the Hough Transform?
Global approach – robust to noise, occlusion etc.
What do you think is the main disadvantage of the Hough Transform?
Deciding on the quantisation level is tricky
Too coarse?
Poor accuracy
Votes miss - cast on nearest neighbour basis
Too fine?
Slow...
1 2 3 4
Lines of finite length
Once the “best” line(s) are found, we can also set limits
Determine where the first and last edge pixel project onto the line
Lines of finite length
Rotation and translation to align the line with a principal axis e.g. y
Max / min on the relevant coordinate e.g. y
y y
line described by (r,) line described by (r,
r r
x
Rotate -
Translate -r
Hough transform for circles
A circle can be parameterised by its centre (a,b) and radius (r)
3D accumulator space r
(a,b)
r
a
b
More complex shapes still....
width height (x,y)
Model of shape we want to find
The Hough transform is impractical for fast
processing
y
h
Computation and space requirement very large
w
even for simple shapes (e.g. rectangle, ellipse)
x
Parameter space
Measuring and Recognising Shape
Detect broken plates on a production line (blue conveyer belt)
Broken plate = large and non-circular
How would
you obtain
the mask?
Photograph taken on production line Binary mask
Connected Components
Often we wish to break an image up into regions for analysis
A connected component is a 4- or 8- connected region
Analyse the shape of each connected component independently
1 Connected components
3
Flood Fill
Recursive algorithm for selecting a homogeneous image region
floodFill (x,y, colour) {
0 255 255 255 255 0
oldcolour=get (x,y);
set (x,y)=colour;
0 0 255 255 255 0
if (get(x-1,y) == oldcolour and not colour)
floodFill (x-1,y,colour);
if (get(x+1,y) == oldcolour and not colour)
0 0 0 255 255 0
floodFill (x+1,y,colour);
if (get(x,y-1) == oldcolour and not colour) 0 0 0 0 128 0
floodFill (x,y-1,colour);
if (get(x,y+1) == oldcolour and not colour)
floodFill (x,y+1,colour); 0 0 0 0 0 0
}
0 0 0 0 0 0
For more details: “Schaum’s outlines: Computer Graphics” (ISBN: 0070503265)
Flood Fill
Recursive algorithm for selecting a homogeneous image region
floodFill (x,y, colour) {
0 255 255 255 255 0
oldcolour=get (x,y);
set (x,y)=colour;
0 0 255 255 255 0
if (get(x-1,y) == oldcolour and not colour)
floodFill (x-1,y,colour);
if (get(x+1,y) == oldcolour and not colour)
0 0 0 255 128 0
floodFill (x+1,y,colour);
if (get(x,y-1) == oldcolour and not colour) 0 0 0 0 128 0
floodFill (x,y-1,colour);
if (get(x,y+1) == oldcolour and not colour)
floodFill (x,y+1,colour); 0 0 0 0 0 0
}
0 0 0 0 0 0
For more details: “Schaum’s outlines: Computer Graphics” (ISBN: 0070503265)
Flood Fill
Recursive algorithm for selecting a homogeneous image region
floodFill (x,y, colour) {
0 255 255 255 255 0
oldcolour=get (x,y);
set (x,y)=colour; etc
0 0 255 255 128 0
if (get(x-1,y) == oldcolour and not colour)
floodFill (x-1,y,colour);
if (get(x+1,y) == oldcolour and not colour)
0 0 0 255 128 0
floodFill (x+1,y,colour);
if (get(x,y-1) == oldcolour and not colour) 0 0 0 0 128 0
floodFill (x,y-1,colour);
if (get(x,y+1) == oldcolour and not colour)
floodFill (x,y+1,colour); 0 0 0 0 0 0
}
0 0 0 0 0 0
For more details: “Schaum’s outlines: Computer Graphics” (ISBN: 0070503265)
Connected Components
We can use flood-fill to “select” a connected component
Once filled we mask out only that colour to isolate component
Connected Components
Assume image = binary mask of connected components
for y=1 to [Link] {
for x=1 to [Link] {
if [Link](x,y)==white {
[Link] (x,y,grey);
workingmask= [Link](grey);
<analyse workingmask>
[Link] (x,y,black);
}
}
Connected Components
Global “shape factors”
Simple dimension-less values computable for a connected component
ymin
Compactness
ymax
xmin xmax
Aspect ratio
Bounding box
Convexity
Waviness
Count of “holes” e.g. O, D, P, B... Convex hull (e.g. MATLAB qhull2)
Over to you
How could we compute an orientation shape factor ?
How could we compute an extent shape factor = length/width?
length
width
Over to you - Solution
How could we compute an orientation shape factor ?
Identify all coordinates of white (set) pixels
x=[ x1 x2 x3 ... xn
y1 y2 y3 ... yn ] width
length
Build Eigenmodel from distribution x
= angle of principal eigenvector from vertical
How could we compute an extent shape factor = length/width?
Ratio of eigenvalues
Or rotate by and compute aspect ratio from bounding box
Solution to the Broken Plate Task?
How would you solve the broken plate finding task using shape factors?
Statistical Moments
Moments are statistical measures computed “about” (relative to) a point
1D example (an image 1 pixel high and 5 pixels wide):
x
1 2 3 4 5
y=1
0 1 1 1 0
The mean or
centriod of the
data is
Statistical Moments (1D)
The mean (b) is an example of a moment
It is “first moment computed about zero” (m1 for short)
th
In general, the moment about zero is:
The zeroth moment is just defined as m0=1
Statistical Moments (1D)
Central moments are moments computed about the mean
Written 1 for short
th
In general, the central moment is:
2 is the variance of the data (measures “spread”= divergence from
mean)
3 is the skew of the data (measures how data is “balanced” about mean)
Summary
After attending this lecture, and doing the reading you
should be able to:
Understand and apply the Hough transform to find simple shapes in images
Explain the term “connected component” and be able to describe how to
separate connected components in an image.
Describe several global shape descriptors (shape factors) for characterising
shape
Recommend solutions to shape recognition tasks
Calculate 1D moments and understand their relationship to basic statistical
quantities
Further Reading
“Feature extraction and image processing”
- pp. 173-180 (Hough transform) – up to the part on ellipses
- pp. 280-288 (Moments)
