Binary shape analysis
1
Outline
{ Midterm-related information
{ Class on February 10
{ Assignment 2
{ Mathematical morphology
z Reading: 13.1, 13.2, 13.3
2
Midterm-related information
{ Friday February 13 in class
{ Course topics:
z Image formation (2.2, 2.3, 2.4, 2.5)
z Colour, light and shading
z Image preprocessing (5.1, 5.2, 5.3)
z Segmentation (6)
{ A more detailed list of topics will be posted on the
course web site
{ Allowed materials: one (1) 8.5" x 11" sheet of paper
with any notes you want on both sides (except
descriptions of algorithms); calculator.
3
Midterm-related information (contd)
{ Note: There are many things covered in
chapters 2, 5, and 6 that we haven't
discussed. You are not responsible for
topics we didn't discuss. You are
responsible for lower-level details in the
book of topics that we may have covered at
a higher level in class.
{ Question format: Definitions, matching,
short answer, some calculations, some
sketching/graphing, some general vision-
related problem solving.
4
Midterm Question samples (1)
{ Using a standard slope-intercept line
representation, explain the main concept
of Hough transform for line detection.
Draw several lines in the image space and
sketch the corresponding Hough
transform in the parameter space. Label
all important points, lines, and axes.
{ Explain why the polar representation of
lines is more suitable for line detection
using the Hough transform than the
standard line representation.
5
Midterm Question samples (2)
{ Explain why smoothing and
detection have conflicting aims.
{ Explain why median filtering
performs well in images corrupted
by impulse noise.
{ Explain why LoG is a better edge
detector than the Laplace edge
detector
6
Midterm Question samples (3)
{ Consider a gray-scale image depicting
several objects on a background with a
bimodal histogram. How will the
classification error vary with the choice of
the threshold?
{ Will the area of the segmented object be
more sensitive if the histogram peaks are
narrow or if they are wide?
7
Class on February 10
{ Will be on research strategies for
your project (i.e. how to find the
most relevant papers)
{ Facilitated by Ms. Bette Kirchner,
Engineering Librarian
{ Room 130, main floor of the
McPherson Library.
8
Assignment 2
{ Related to segmentation techniques
{ Will be posted on Monday Feb 9
9
Outline
{ Midterm-related information
{ Class on February 10
{ Assignment 2
{ Mathematical morphology
z Reading: 13.1, 13.2, 13.3
10
What is mathematical morphology?
{ A mathematical tool for investigating the
geometric structure in binary and gray-
scale images
{ Goal: distinguish meaningful shape
information from irrelevant one
z Find boundaries of objects
z Filter out contour irregularities
z Find appropriate shape representations
z etc
{ Our focus today will be on binary image
analysis
11
Mathematical morphology tools
In mathematical morphology, images are
defined as sets of pixels
{ Basic morphological operators are similar to
convolution but using set operations (non-
linear algebra)
{ Morphological operators are useful for:
z Preprocessing
z Postprocessing
z Segmentation
z Representation
12
Basic morphological operators
{ Mostly used in preprocessing or
postprocessing (after segmentation)
z Dilation
z Erosion
z Opening (dilation+erosion)
z Closing (erosion + dilation)
13
Set Operations on Binary Images
A the image (on pixels)
{ Ac the complement of the image (inverse)
{ AB the union of images A and B
{ A B the intersection of images A and B
{ A - B the difference between A and B (the
pixels in A that arent in B)
{ #A the cardinality of A (area of the
object(s))
14
Translation
The image A translated by movement vector t
is
{ At = {c | c = a + t for some a in A}
{ pick up each pixel in A and move it by the
movement vector t
{ In common morphological applications, t is
a unit vector directed towards N, S, E, W
15
Dilation
{ We consider set A and a structuring element B.
{ We combine these two sets using vector
addition
{ Express dilation via translation
Unioned copies of the Unioned copies of
shifted image the shifted
structuring element
16
Result of dilation depends on the shape of the
structuring element
17
Applications of dilation: restoration of
shape continuity
18
Example of Dilation
Structuring
Element
Pablo Picasso, Pass with the Cape, 1960
19
Properties of dilation
Dilation with a large structuring element can be implemented
as an iterative dilation with an elementary structuring element
What structuring element corresponds a single dilation
equivalent to two iterations of a dilation with
20
Erosion
Informally, the result of erosion is everywhere
where the structuring element fits completely
inside shape A
In terms of translation:
Intersection of shifted copies
of the image
21
Result of erosion depends on the
shape of the structuring element
22
Example of Erosion
Structuring
Element
Pablo Picasso, Pass with the Cape, 1960
23
Properties of erosion
{ Not commutative
{ Not associative
24
25
Duality
{ Dual operations are ones that can be defined in
terms of each other. Duals are not inverse
operations
{ Dilation and erosion are dual operations:
{ Intuition: dilating the foreground is the same as
eroding the background with a flipped structuring
element
26
Boundary extraction using dilation and
erosion
{ Can find all of the boundary pixels by
dilating the object and subtracting the
original:
{ where B is a 3 3 structuring element
containing all 1s
{ Or by eroding the original and subtracting
that from the original:
27
Finding boundary pixels
28
Opening
{ erosion followed by dilation
{ Why dilate after erosion?
z erosion finds all the places where the structuring element fits
inside the shape; it only marks these positions at the origin
of the element.
z with a dilation, we fill back in the full structuring element
at places where the element fits inside the object.
{ Openings can be used to remove connections
between objects.
29
Closing
{ Closing works in an opposite fashion from
opening:
{ Used to remove small holes, gaps, etc.
30
Properties of opening and closing
{ Opening and closing are also duals:
{ Intuition: opening to remove small
foreground objects is equivalent to closing
small holes in the background
{ Idempotence : nothing changes after the
first application
31
Applications of opening and closing
{ Opening and closing are basic tools in
morphology-based noise removal.
z Opening removes small protrusions and narrow
connections between objects
z Closing removes small holes
{ The size of the structuring element depends
on the signal-to-noise ratio, and on the size
of holes and small objects considered as
noise.
32
Conditional dilation
{ Conditional dilation involves dilation of an image
followed by intersection with some other condition
image.
{ Application:
33
Conditional dilation applied to shape
morphing (example)
Shape morphing:
a) superposition of the initial shape obj1(green boundary) and the
final shape obj2 (blue boundary);
b) initial shape in grey ;
c), d), e), f) intermediate morphing iterations, resulting in grey
objects with red boundaries;
g) final shape(obj2)
34
Hit or miss operator
{ Can be considered as a binary template
matching
{ Needs two structuring elements: one that
must hit, the other that must miss
{ Example: detection of an upper right corner
z J (hit) finds points with connected left and lower
neighbors
z K (miss) finds points without upper, upper right
and right neighbors
35
Detection of the convex hull using the
hit-and-miss operator
{ The convex hull of an object A is the smallest
convex region C(A) that contains A
{ Important geometric property of objects
z Example: detecting arm waving in human actions
{ Hit and miss is used for detecting (and filling) all
possible concavities in the border of an object
Image of Image of
36
objects convex hulls
37
Detection of the skeleton of the object
{ A skeleton is an object representation that is
z Single-pixel thin
z Lies in the middle of the object
z Preserves the topology of the object
38
Skeleton representation
39
Morphological derivation of the
skeleton
{ Design hit-and-miss operators that find
boundary points that can safely be
removed without breaking the object in two
{ Apply recursively to strip layer by layer
from the exterior of the shape until
convergence
{ Structuring elements (plus other four
rotations)
40
41
Examples of morphological processing
42
Example 1. Segmentation of cells from a microscopy
image (See Matlab demos for Image processing toolbox)
Thresholding applied to the
gradient image rather than the
initial image
43
filling the gaps in the lines surrounding the object
- The dilated gradient mask is created from two
iterative dilations:
1. Dilation using a vertical structuring element
followed by
2. Dilation using a horizontal structuring element
44
45
Remove objects connected on border
Connectivity set to 4 to remove diagonal
connections
46
Smoothing with a double erosion
47
Example2. Extracting patterns from an image
48
