Image Segmentation, Representation & Description

Image Segmentation, Representation &
Description
By
Sachin Chavan
Assistant Professor,
Department of Computer Engineering,
MPSTME, Shirpur Campus

10/15/2021 1
Description
Edge Linking and Boundary Detection
• Ideally, edge detection should yield sets of pixels lying only on edges.
•
• In practice, these pixels seldom characterize edges completely because
of noise, breaks in the edges due to non-uniform illumination, and other
effects that introduce spurious discontinuities in intensity values.
• Therefore, edge detection typically is followed by linking algorithms
designed to assemble edge pixels into meaningful edges and/or region
boundaries.
• In this section, we discuss three fundamental approaches to edge linking
that are representative of techniques used in practice.
• The first requires knowledge about edge points in a local region (e.g., a
neighborhood); the second requires that points on the boundary of a
region be known; and the third is a global approach that works with an
entire edge image.
10/15/2021 Image Segmentation, Representation & Description 2

Local processing
• One of the simplest approaches for linking edge points is to analyze the characteristics of pixels in
•
a small neighborhood about every point (x, y) that has been declared an edge point by one of the
techniques discussed in the previous section.
• All points that are similar according to predefined criteria are linked, forming an edge of pixels
that share common properties according to the specified criteria.
• The two principal properties used for establishing similarity of edge pixels in this kind of analysis
are (1) the strength (magnitude) and (2) the direction of the gradient vector.
• Let denote the set of coordinates of a neighborhood centered at point (x, y) in an image. An edge
pixel with coordinates (s, t) in is similar in magnitude to the pixel at if
• Where E is a positive threshold.

• An edge pixel with coordinates (s, t) in has an angle similar to the pixel at (x, y) if
• where A is a positive angle threshold.

• A pixel with coordinates in is linked to the pixel at (x, y) if both magnitude and direction criteria
are satisfied.
• This process is repeated at every location in the image. A record must be kept of linked points as
the center of the neighborhood is moved from pixel to pixel. A simple bookkeeping procedure is to
assign a different intensity value to each set of linked edge pixels.
Local processing
• The preceding formulation is computationally expensive because all
• neighbors
of every point have to be examined.
• A simplification particularly well suited for real time applications
consists of the following steps:
1. Compute the gradient magnitude and angle arrays, and of the input image, .
2. Form a binary image, , whose value at any pair of coordinates is given by:
Where is a threshold, is a specified angle direction, and defines a “band” of acceptable

directions about A.
3. Scan the rows of and fill (set to 1) all gaps (sets of 0s) in each row that do not exceed a
specified length, . Note that, by definition, a gap is bounded at both ends by one or more 1s.
The rows are processed individually, with no memory between them.
4. To detect gaps in any other direction, , rotate g by this angle and apply the horizontal
scanning procedure in step 3. Rotate the result back by .
• When interest lies in horizontal and vertical edge linking, Step 4 becomes a
simple procedure in which is rotated ninety degrees, the rows are scanned, and
the result is rotated back.
Regional processing
• Often, the location of regions of interest in an image are known or can be
determined.
• This implies that knowledge is available regarding the regional membership of
pixels in the corresponding edge image.
• In such situations, we can use techniques for linking pixels on a regional basis,
with the desired result being an approximation to the boundary of the region.
• One approach to this type of processing is functional approximation, where we fit
a 2-D curve to the known points.
• Typically, interest lies in fast-executing techniques that yield an approximation to
essential features of the boundary, such as extreme points and concavities.
• Polygonal approximations are particularly attractive because they can capture the
essential shape features of a region while keeping the representation of the
boundary (i.e., the vertices of the polygon) relatively simple.
• In this section, we develop and illustrate an algorithm suitable for this purpose.

Regional processing
• Before stating the algorithm, we discuss the mechanics of the procedure using a simple
example.
• Figure shows a set of points representing an open curve in which the end points have been
labeled and These two points are by definition vertices of the polygon.
• We begin by computing the parameters of a straight line passing through A and B.
• Then, we compute the perpendicular distance from all other points in the curve to this line and
select the point that yielded the maximum distance (ties are resolved arbitrarily).

Regional processing
• If this distance exceeds a specified threshold, T, the corresponding point, labeled C, is
declared a vertex, as shown in Fig (a).
• Lines from A to C and from C to B are then established, and distances from all points
between A and C to the line AC are obtained.
• The point corresponding to the maximum distance is declared a vertex, D, if the distance
exceeds T; otherwise no new vertices are declared for that segment.
• A similar procedure is applied to the points between C and B.
• Figure (b) shows the result and Fig. (c) shows the next step.
• This iterative procedure is continued until no points satisfy the threshold test. Figure (d)
shows the final result which, as you can see, is a reasonable approximation to the shape
of a curve fitting the given points.
• Two important requirements are implicit in the procedure just explained.
• First, two starting points must be specified; second, all the points must be ordered (e.g.,
in a clockwise or counterclockwise direction).
• When an arbitrary set of points in 2-D does not form a connected path (as is typically
the case in edge images) it is not always obvious whether the points belong to a
boundary segment (open curve) or a boundary (closed curve).
Regional processing
• Given that the points are ordered, we can infer whether we are
dealing with an open or closed curve by analyzing the distances
between points.
• A large distance between two consecutive points in the ordered
sequence relative to the distance between other points as we traverse
the sequence of points is a good indication that the curve is open.
• The end points are then used to start the procedure. If the separation
between points tends to be uniform, then we are most likely dealing
with a closed curve.
• In this case, we have several options for selecting the two starting
points.
• One approach is to choose the rightmost and leftmost points in the
set. Another is to find the extreme points of the curve.

Regional processing
• An algorithm for finding a polygonal fit to open and closed curves may be
•
stated as follows:
– Let P be a sequence of ordered, distinct, 1-valued points of a binary image. Specify two
starting points, A and B. These are the two starting vertices of the polygon.
– Specify a threshold, T, and two empty stacks, OPEN and CLOSED.
– If the points in P correspond to a closed curve, put A into OPEN and put B into OPEN
and into CLOSED. If the points correspond to an open curve, put A into OPEN and B into
CLOSED.
– Compute the parameters of the line passing from the last vertex in CLOSED to the last
vertex in OPEN.
– Compute the distances from the line in Step 4 to all the points in P whose sequence
places them between the vertices from Step 4. Select the point, with the maximum
distance, .
– If place at the end of the OPEN stack as a new vertex. Go to Step 4.
– Else, remove the last vertex from OPEN and insert it as the last vertex of CLOSED.
– If OPEN is not empty, go to Step 4.
– Else, exit. The vertices in CLOSED are the vertices of the polygonal fit to the points in P.

10/15/2021 10
Description
Global processing using the Hough transform
• The methods discussed in the previous two sections are applicable in
situations where knowledge about pixels belonging to individual objects is
at least partially available.
• For example, in regional processing, it makes sense to link a given set of
pixels only if we know that they are part of the boundary of a meaningful
region.
• Often, we have to work with unstructured environments in which all we
have is an edge image and no knowledge about where objects of interest
might be.
• In such situations, all pixels are candidates for linking and thus have to be
accepted or eliminated based on predefined global properties.
• In this section, we develop an approach based on whether sets of pixels lie
on curves of a specified shape.
• Once detected, these curves form the edges or region boundaries of interest.

•• Given
points in an image, suppose that we want to find
subsets of these points that lie on straight lines.
• One possible solution is to find first all lines determined by
every pair of points and then find all subsets of points that are
close to particular lines.
• This approach involves finding lines and then performing
comparisons of every point to all lines.
• This is a computationally prohibitive task in all but the most
trivial applications.

• Hough [1962] proposed an alternative approach,
•
commonly referred to as the Hough transform.
• Consider a point in the xy-plane and the general equation
of a straight line in slope-intercept form, .
• Infinitely many lines pass through but they all satisfy the
equation for varying values of and
• However, writing this equation as and considering the ab-
plane (also called parameter space) yields the equation of a
single line for a fixed pair .
• Furthermore, a second point also has a line in parameter
space associated with it, and, unless they are parallel, this
line intersects the line associated with at some point ,
where is the slope and the intercept of the line containing
both and in the xy-plane.
• In fact, all the points on this line have lines in parameter
space that intersect at .
Hough transform (Example)
• Given four points in the xy plane with the following coordinates
• (1,1), (2,2), (3,3) (4,4) use Hough transform to join these points.
Sol: It is obvious that these four points do form a straight line. But
we come to this conclusion only because our visual system is very
complex and it helps us to visualize a line joining these points. But
the computer needs to be fed with a good algorithm so as to join
these lines.
We shall solve this example on a graph paper to get accurate
results.
We use the equation
Changing the coordinates we get
Substituting values of x and y in above equation we get,
Using above equations we draw four lines in parameter space ab, each
representing a point from the xy plane.

•• From
graph, we get single
intersection point which has
coordinates.
• (1, 0) i.e. a=1, b=0. taking
these values of a and b we
draw line using the
equation.


• Given 5 points, use Hough transform to
• draw line joining these points. (1, 4) (2,
3) (3, 1) (4,1) (5,0)
Sol:
The first step is to draw the given points as
they are
We now use the standard slope-intercept equation of
a straight line
Using the parameter space, we get
Using above equations we draw 5 lines in parameter

space ab, each representing a point from the xy
plane.
• Ifallwe observe carefully, barring line
the other lines intersect each
other at a single point (-1, 5) i.e.
We take this value of a and b and
use it in the equation.

Thresholding
• Because of its intuitive properties, simplicity of
implementation, and computational speed, image thresholding
enjoys a central position in applications of image segmentation.
• In this section, we discuss thresholding in a more formal way
and develop techniques that are considerably more general than
what has been presented thus far.
• In the previous section, regions were identified by first finding
edge segments and then attempting to link the segments into
boundaries.
• In this section, we discuss techniques for partitioning images
directly into regions based on intensity values and/or properties
of these values.

The basics of intensity thresholding
• Suppose that the intensity histogram in Fig. corresponds to an
•
image composed of light objects on a dark background, in such a
way that object and background pixels have intensity values
grouped into two dominant modes.
• One obvious way to extract the objects from the background is to
select a threshold, T, that separates these modes.
• Then, any point in the image at which is called an object point;
otherwise, the point is called a background point.
• In other words, the segmented image, is given by
• When T is a constant applicable over an entire image, the process

given in this equation is referred to as global thresholding.
• When the value of T changes over an image, we use the term
variable thresholding.
• The term local or regional thresholding is used sometimes to
denote variable thresholding in which the value of T at any point
(x, y) in an image depends on properties of a neighborhood of (x,
y).
The basics of intensity thresholding
• If T depends on the spatial coordinates (x, y) themselves,
•
then variable thresholding is often referred to as dynamic or
adaptive thresholding.
• Use of these terms is not universal, and one is likely to see
them used interchangeably in the literature on image
processing.
• Figure shows a more difficult thresholding problem
involving a histogram with three dominant modes
corresponding, for example, to two types of light objects on
a dark background.
• Here, multiple thresholding classifies a point (x, y) as
belonging to the background if , to one object class if and
to the other object class if .
• That is, the segmented image is given by
• where a, b and c are any three distinct intensity values.

Basic Global Thresholding
• As noted in the previous section, when the intensity distributions of objects and
•
background pixels are sufficiently distinct, it is possible to use a single (global)
threshold applicable over the entire image.
• In most applications, there is usually enough variability between images that,
even if global thresholding
• is a suitable approach, an algorithm capable of estimating automatically the
threshold value for each image is required.
• The following iterative algorithm can be used for this purpose:
1. Select an initial estimate for the global threshold, T.
2. Segment the image using T. This will produce two groups of pixels: G1 consisting of
all pixels with intensity values , and G2 consisting of pixels with values .
3. Compute the average (mean) intensity values and for the pixels in and respectively.
4. Compute a new threshold value:
5. Repeat Steps 2 through 4 until the difference between values of T in successive
iterations is smaller than a predefined parameter .

Region-Based Segmentation
•• Let represent the entire spatial region occupied by an image. We

may view image segmentation as a process that partitions into sub
regions, such that
a. is a connected set,
b. .
• Here, is a logical predicate defined over the points in set , and is the
null set.
• The symbol and represent set union and intersection, respectively.
• Two regions are said to be adjacent if their union forms a connected
set.
Region Growing
• As its name implies, region growing is a procedure that groups pixels or
sub-regions into larger regions based on predefined criteria for growth.
• The basic approach is to start with a set of “seed” points and from these
grow regions by appending to each seed those neighboring pixels that
have predefined properties similar to the seed (such as specific ranges
of intensity or color).
• Selecting a set of one or more starting points often can be based on the
nature of the problem.
• When a priori information is not available, the procedure is to compute
at every pixel the same set of properties that ultimately will be used to
assign pixels to regions during the growing process.
• If the result of these computations shows clusters of values, the pixels
whose properties place them near the centroid of these clusters can be
used as seeds.
Region Growing
• The selection of similarity criteria depends not only on the problem under
consideration, but also on the type of image data available.
• For example, the analysis of land-use satellite imagery depends heavily on the
use of color.
• This problem would be significantly more difficult, or even impossible, to solve
without the inherent information available in color images.
• When the images are monochrome, region analysis must be carried out with a set
of descriptors based on intensity levels and spatial properties (such as moments
or texture).
• Descriptors alone can yield misleading results if connectivity properties are not
used in the region-growing process.
• For example, visualize a random arrangement of pixels with only three distinct
intensity values.
• Grouping pixels with the same intensity level to form a “region” without paying
attention to connectivity would yield a segmentation result that is meaningless in
the context of this discussion.
Region Growing
• Another problem in region growing is the formulation of a stopping rule.
• Region growth should stop when no more pixels satisfy the criteria for
inclusion in that region.
• Criteria such as intensity values, texture, and color are local in nature and
do not take into account the “history” of region growth.
• Additional criteria that increase the power of a region-growing algorithm
utilize the concept of size, likeness between a candidate pixel and the
pixels grown so far (such as a comparison of the intensity of a candidate
and the average intensity of the grown region), and the shape of the region
being grown.
• The use of these types of descriptors is based on the assumption that a
model of expected results is at least partially available.

Region Growing
• Let: denote an input image array; denote a seed array containing 1s at the
• locations of seed points and 0s elsewhere; and denote a predicate to be
applied at each location .
• Arrays and are assumed to be of the same size.
• A basic region-growing algorithm based on 8-connectivity may be stated
as follows.
1. Find all connected components in and erode each connected component to one pixel;
label all such pixels found as 1. All other pixels in S are labeled 0.
2. Form an image such that, at a pair of coordinates , let if the input image satisfies the
given predicate, at those coordinates; otherwise, let .
3. Let be an image formed by appending to each seed point in all the 1-valued points in
that are 8-connected to that seed point.
4. Label each connected component in with a different region label (e.g., 1, 2, 3, …..). This
is the segmented image obtained by region growing.

Region Growing 5 6 6 6 7 7 6 6
6 7 6 7 5 5 4 7
• Consider an 8 X 8 image, the grey level
• ranges from 0-7. segment this image 6
5
6
4
4
5
4
4
3
2
2
3
5
4
6
6
using the region growing technique. 0 3 2 3 3 2 4 7
• Here we need to decide on predicate and 0 0 0 0 2 2 5 6
seed pixel. 1 1 0 1 0 3 4 4
1 0 1 0 2 3 4 5
• Let the predicate be
5 6 6 6 7 7 6 6
• Where th is threshold. In this case let the
6 7 6 7 5 5 4 7
threshold be 3.
6 6 4 4 3 2 5 6
5 4 5 4 2 3 4 6
• We assume 4-connectivity. Let us start
0 3 2 3 3 2 4 7
with seed pixel 6 (highlighted red). 0 0 0 0 2 2 5 6
1 1 0 1 0 3 4 4
1 0 1 0 2 3 4 5

Region Growing 5 6 6 6 7 7 6 6
6 7 6 7 5 5 4 7
• Let us take the seed pixel as 3. let 6 6 4 4 3 2 5 6
predicate be the same. 5 4 5 4 2 3 4 6
• Thus this image is segmented into 3 0 3 2 3 3 2 4 7
different regions by using a different 0 0 0 0 2 2 5 6
seed point. 1 1 0 1 0 3 4 4
• In this method, at a time only one pixel 1 0 1 0 2 3 4 5
is assigned as a member of the current
region because of which it is very slow.
5 6 6 6 7 7 6 6
6 7 6 7 5 5 4 7
6 6 4 4 3 2 5 6
5 4 5 4 2 3 4 6
0 3 2 3 3 2 4 7
0 0 0 0 2 2 5 6
1 1 0 1 0 3 4 4
1 0 1 0 2 3 4 5

Region Splitting
• In this case we try to satisfy the homogeneity property where pixels
that are similar are grouped together.
• If the grey levels present in the region do not satisfy the property, we
divide the region into four equal quadrants.
• If the property is satisfied, we leave the region as it is.
• This is done recursively until all the regions satisfy the property.
• To explain this in terms of graph theory, we call each region a node.
• This node (Parent Node) is split into its four children (leaf nodes) if
it does not satisfy the given property.
• If the node satisfies the property, it is left as it is.
• We now check each leaf node and see if these leaf nodes satisfy the
given property. If yes, they are left unaltered and if no, there are
further split.
10/15/2021 30
Description
Region Splitting
•• This particular splitting technique has

a convenient representation in the
form of quad tree.
• Consider figure shown.
• In this, image R represents the entire
image and hence R is the parent node.
• This parent node split into four leaf
nodes, , ,
• Of these leaf nodes only does not
contain pixels which satisfy some
common property and hence split
again i.e. .

10/15/2021 31
Description
Region Splitting 5
6
6
7
6
6
6
7
7
5
7
5
6
4
6
7
6 6 4 4 3 2 5 6
•
• Consider 8 X 8 image. Let the predicate be . also
draw quad tree.
5
0
4
3
5
2
4
3
2
3
3
2
4
4
6
7
• Since the entire image does not satisfy the condition 0 0 0 0 2 2 5 6
of threshold , we split the image into four regions.
1 1 0 1 0 3 4 4
• In this and satisfy the homogeneity condition i.e. all
pixels of satisfy the condition of threshold in other 1 0 1 0 2 3 4 5
words,
5 6 6 6 7 7 6 6
• Similarly all pixels of satisfy the same condition. 6 7 6 7 5 5 4 7
6 6 4 4 3 2 5 6
5 4 5 4 2 3 4 6
0 3 2 3 3 2 4 7
0 0 0 0 2 2 5 6
1 1 0 1 0 3 4 4
1 0 1 0 2 3 4 5

10/15/2021 32
Description
Region Merging
• The region merging method is exactly opposite to the region
splitting method.
• Like the region splitting method, region merging is also applicable
only to images whose number of rows and columns are an integer
power of two.
• In this method, we start from the pixel level and consider each of
them as homogeneous region.
• At any level of merging we check if the four adjacent homogeneous
regions arranged in a 2 X 2 fashion together satisfy the homogeneity
property.
• If yes, they are merged to form a bigger region, otherwise the
regions are left as they are.

10/15/2021 33
Description
Region Merging 5
6
6
7
6
6
6
7
7
5
7
5
6
4
6
7
6 6 4 4 3 2 5 6
•
• Consider 8 X 8 image. Let the predicate be . 5
0
4
3
5
2
4
3
2
3
3
2
4
4
6
7
0 0 0 0 2 2 5 6
5 6 6 6 7 7 6 6 1 1 0 1 0 3 4 4
6 7 6 7 5 5 4 7 1 0 1 0 2 3 4 5
6 6 4 4 3 2 5 6
5 4 5 4 2 3 4 6
0 3 2 3 3 2 4 7 5 6 6 6 7 7 6 6
0 0 0 0 2 2 5 6 6 7 6 7 5 5 4 7
1 1 0 1 0 3 4 4 6 6 4 4 3 2 5 6
1 0 1 0 2 3 4 5 5 4 5 4 2 3 4 6
0 3 2 3 3 2 4 7
0 0 0 0 2 2 5 6
1 1 0 1 0 3 4 4
1 0 1 0 2 3 4 5

10/15/2021 34
Description
Region Splitting & Merging
•
•
•
Let R represent the entire image region and select a predicate Q.
One approach for segmenting R is to subdivide it successively into smaller and smaller
quadrant regions so that, for any region .
• We start with the entire region. If Q(R) = FALSE, we divide the image into quadrants.
• If Q is FALSE for any quadrant, we subdivide that quadrant into sub quadrants, and so on.
• This particular splitting technique has a convenient representation in the form of so-called
quad-trees, that is, trees in which each node has exactly four descendants, as Fig. shows (the
images corresponding to the nodes of a quadtree sometimes are called quadregions or
quadimages).
• Note that the root of the tree corresponds to the entire image and that each node corresponds
to the subdivision of a node into four descendant nodes.
• In this case, only was subdivided further.

10/15/2021 35
Description
•
• If identical
only splitting is used, the final partition normally contains adjacent regions with
properties.
• This drawback can be remedied by allowing merging as well as splitting.
• Satisfying the constraints of segmentation requires merging only adjacent regions whose
combined pixels satisfy the predicate Q.
• That is, if two adjacent regions and are merged only if .
• The preceding discussion can be summarized by the following procedure in which, at
any step, we
1. Split into four disjoint quadrants any region for which .
2. When no further splitting is possible, merge any adjacent regions and for which .
3. Stop when no further merging is possible.
• It is customary to specify a minimum quadregion size beyond which no further splitting
is carried out.

10/15/2021 36
Description
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
• Segment the given 8 x 8 image
using split and merge region 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
segmentation. Here the predicate 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
to be used is that the value of 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1
pixels in region have to exactly
0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1
equal.
• Solution: 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0
– We use the split technique and split the 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0
image till each node has the same value
of pixels, for this image we get
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 1
0 0 0 1 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 0 0
0 0 1 1 1 0 0 0
10/15/2021 37
Description

Image Segmentation, Representation & Description

Uploaded by

Copyright:

Available Formats

Image Segmentation, Representation & Description

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Image Segmentation, Representation & Description

Uploaded by

Copyright:

Available Formats

Image Segmentation, Representation &