Representation & Description
Overview
• A region can be represented in 2 ways
– In terms of its external characteristics (its boundary)
focus on shape characteristics
– In terms of its internal characteristics (its region)
focus on regional properties, e.g., color, texture
• Sometimes, we may need to use both ways
2
Overview
• Description describes the region based on the
chosen representation
• For example:
– Representation boundary
– Description length of the boundary, orientation
of the straight line joining its extreme points, and
the number of concavities in the boundary.
3
Sensitivity
• Features selected as descriptors should be as
insensitive as possible to variations in
– Size
– Translation
– Rotation
• The following descriptors satisfy one or more
of these properties.
4
Representation
• Segmentation techniques yield raw data in the form
of pixels along a boundary or pixels contained in a
region
• The raw data sometimes are used directly to obtain
descriptors
• More useful data (descriptors) can be computed
from the raw data in order to decrease the size of
data.
5
Chain Codes
• Based on 4 or 8 connectivity
6
7
Chain Codes Properties
• Starting point is arbitrary
• Drawbacks:
– The resulting chain of codes tends to be quite long
– Any small disturbances along the boundary due to noise or
imperfect segmentation cause changes in the code that
may not be related to the shape of the boundary
• Solve the problems by:
– Resample the boundary by selecting a larger grid spacing
• however, different grid can generate different chain
codes
8
Polygonal Approximations
• Boundary can be approximated with arbitrary
accuracy by a polygon
• Try to capture the “essence” of the boundary
shape with the fewest possible polygonal
segments
• Not trivial and time consuming
• Two techniques:
– Minimum Perimerter Polygons (MPP)
– Splitting techniques
9
Minimum Perimeter Polygons
• The vertices of the polygon are created by the corners
of the inner and outer walls of the cells
10
Splitting Techniques
1. Find the major axis
2. Find the minor axes which perpendicular to major axis and
has distance greater than a threshold
3. Repeat until you can’t split anymore
11
Signatures
Map 2D function to 1D function
12
Boundary Segments
• Decomposing boundary into segments
– To reduce the boundary complexity
– Useful: when it contains one or more significant concavities
• Convex hull H of an arbitrary set S is the smallest convex
set containing S
• The set different H-S is called convex deficiency D of the
set S
13
Skeletons
• Skeleton: The set of points in the region that are equidistant from
the border of the region
• Approaches:
1. Topology-preserving thinning: Thinning the region (e.g. using
erosion) successively while preserving end points and line
connectivity.
2. Medial Axis Transform (MAT) of a region R with border B
• For each point p in R, we find its closest neighbor in B
• If p has more than one such neighbor, it is said to belong to
the medial axis of R
14
Example
15
Boundary Descriptors
• Length of a boundary
• Diameters of the boundary
• Eccentricity
• Shape numbers
16
Length of a boundary
• The number of pixels along a boundary
• It gives a rough approximation of its length
17
Diameters
Diam( B) max[ D( pi , p j )]
i, j
• D is a distance measure
• pi and pj are points on the boundary B
18
Eccentricity
• Ratio of the major to the minor axis
– Major axis = the line connecting the two extreme
points that comprise the diameter
– Minor axis = the line perpendicular to the major
axis
19
Regional Descriptors
• Area
• Perimeter
• Compactness
• Topological descriptors
• Texture
22
Simple descriptors
• Area = the number of pixels in the region
• Perimeter = length of its boundary
• Compactness = (perimeter)2/area
23
Topological descriptors
E=C-H
• E = Euler number
• C = number of connected region
• H = number of holes
24
Euler number
25
Texture descriptors
26
Texture descriptors
27