Chapter 7

Image segmentation

No. Question Year

What do you mean by Huffman coding? Analyze the two steps of 2020,
1 Huffman coding with an appropriate example. 2014,
Or, Explain the Huffman Coding. 2015
2015,
2 What do you mean by edge detection?
2011
2020,
3 Write down the Sobel diagonal masks.
2015
4 Describe the criteria for edge linking. 2015
5 Explain the region growing segmentation with an example. 2015
6 What is image segmentation? 2013
7 Write down the importance of edge detection. 2013
2014,
8 Discuss about region-based segmentation.
2016
9 Define image subtraction, image negative, and gray level slicing. 2012
What is image segmentation? Discuss different types of image
10 2020
segmentation techniques.
11 How can you detect a point in an image? 2020
12 Write down the edge linking procedure. 2011
13 Explain the use of motion in segmentation. 2016
Write down the line detection algorithm for Horizontal, Vertical, +45°,
14 2011
and -45°.
Obtain the Huffman’s code for the following sequence:-

15 2015

What is average code length with and without compression?

 Chapter 07
Image segmentation

1. What do you mean by Huffman coding? Analyze the two steps of Huffman coding
with an appropriate example.[2020,2014]
Or, Explain the Huffman Coding. 2015
Answer:
Prefix Codes, means the codes (bit sequences) are assigned in such a way that the code
assigned to one character is not the prefix of code assigned to any other character. This is how
Huffman Coding makes sure that there is no ambiguity when decoding the generated bit
stream.
Let us understand prefix codes with a counter example. Let there be four characters a, b, c and
d, and their corresponding variable length codes be 00, 01, 0 and 1. This coding leads to
ambiguity because code assigned to c is the prefix of codes assigned to a and b. If the
compressed bit stream is 0001, the de-compressed output may be “cccd” or “ccb” or “acd” or
“ab”.
See this for applications of Huffman Coding.
There are mainly two major parts in Huffman Coding
1) Build a Huffman Tree from input characters.
2) Traverse the Huffman Tree and assign codes to characters.
Steps to build Huffman Tree
Input is an array of unique characters along with their frequency of occurrences and output is
Huffman Tree.
1) Create a leaf node for each unique character and build a min heap of all leaf nodes (Min
Heap is used as a priority queue. The value of frequency field is used to compare two
nodes in min heap. Initially, the least frequent character is at root)
2) Extract two nodes with the minimum frequency from the min heap.
3) Create a new internal node with a frequency equal to the sum of the two nodes frequencies.
Make the first extracted node as its left child and the other extracted node as its right child.
Add this node to the min heap.
4) Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the
root node and the tree is complete.
2) Let us understand the algorithm with an example:
3) character Frequency
a 5
b 9
c 12
d 13
 e 16
f 45
Step 1. Build a min heap that contains 6 nodes where each node represents root of a tree with
single node.
Step 2 Extract two minimum frequency nodes from min heap. Add a new internal node with
frequency 5 + 9 = 14.

Now min heap contains 5 nodes where 4 nodes are roots of trees with single element each, and
one heap node is root of tree with 3 elements
character Frequency
c 12
d 13
Internal Node 14
e 16
f 45
Step 3: Extract two minimum frequency nodes from heap. Add a new internal node with
frequency 12 + 13 = 25

Now min heap contains 4 nodes where 2 nodes are roots of trees with single element each,
and two heap nodes are root of tree with more than one nodes.
character Frequency
Internal Node 14
e 16
Internal Node 25
f 45
Step 4: Extract two minimum frequency nodes. Add a new internal node with frequency 14 +
16 = 30
Now min heap contains 3 nodes.
character Frequency
Internal Node 25
Internal Node 30
f 45
Step 5: Extract two minimum frequency nodes. Add a new internal node with frequency 25 +
30 = 55

Now min heap contains 2 nodes.

character Frequency
f 45
Internal Node 55
Step 6: Extract two minimum frequency nodes. Add a new internal node with frequency 45 +
55 = 100

Now min heap contains only one node.

character Frequency
Internal Node 100
Since the heap contains only one node, the algorithm stops here.
Steps to print codes from Huffman Tree:
Traverse the tree formed starting from the root. Maintain an auxiliary array. While moving to
the left child, write 0 to the array. While moving to the right child, write 1 to the array. Print
the array when a leaf node is encountered.

The codes are as follows:

character code-word
f 0
c 100
d 101
a 1100
b 1101
e 111

2. What do you mean by edge detection? [2015,2011]

Answer:
We can say that sudden changes of discontinuities in an image are called as edges. Significant
transitions in an image are called as edges.
Types of edges
Generally edges are of three types:
• Horizontal edges
• Vertical Edges
• Diagonal Edges
Detect edges
Most of the shape information of an image is enclosed in edges. So first we detect these edges
in an image and by using these filters and then by enhancing those areas of image which
contains edges, sharpness of the image will increase and image will become clearer.
Here are some of the masks for edge detection that we will discuss in the upcoming tutorials.
• Prewitt Operator
• Sobel Operator
• Robinson Compass Masks
 • Krisch Compass Masks
• Laplacian Operator.
Above mentioned all the filters are Linear filters or smoothing filters.

3. Write down the sobel diagonal masks. [2020,2015]

Answer:
The sobel operator is very similar to Prewitt operator. It is also a derivate mask and is used
for edge detection. Like Prewitt operator sobel operator is also used to detect two kinds of
edges in an image:
• Vertical direction
• Horizontal direction
Difference with Prewitt Operator
The major difference is that in sobel operator the coefficients of masks are not fixed and they
can be adjusted according to our requirement unless they do not violate any property of
derivative masks.
Following is the vertical Mask of Sobel Operator:
-1 0 1

-2 0 2

-1 0 1

This mask works exactly same as the Prewitt operator vertical mask. There is only one
difference that is it has “2” and “-2” values in center of first and third column. When applied
on an image this mask will highlight the vertical edges.
How it works
When we apply this mask on the image it prominent vertical edges. It simply works like as
first order derivate and calculates the difference of pixel intensities in a edge region.
As the center column is of zero so it does not include the original values of an image but
rather it calculates the difference of right and left pixel values around that edge. Also the
center values of both the first and third column is 2 and -2 respectively.
This give more weight age to the pixel values around the edge region. This increase the edge
intensity and it become enhanced comparatively to the original image.
Following is the horizontal Mask of Sobel Operator
-1 -2 -1

0 0 0

1 2 1
Above mask will find edges in horizontal direction and it is because that zeros column is in
horizontal direction. When you will convolve this mask onto an image it would prominent
horizontal edges in the image. The only difference between it is that it have 2 and -2 as a
center element of first and third row.

4. Describe the criteria for edge linking. [2015,2011]

Answer:
Edge detectors yield pixels in an image lie on edges.
The next step is to try to collect these pixels together into a set of edges.
Thus, our aim is to replace many points on edges with a few edges themselves.
The practical problem may be much more difficult than the idealised case.
• Small pieces of edges may be missing,
• Small edge segments may appear to be present due to noise where there is no
real edge, etc.
In general, edge linking methods can be classified into two categories:
Local Edge Linkers
-- where edge points are grouped to form edges by considering each point's
relationship to any neighboring edge points.

Global Edge Linkers

-- where all edge points in the image plane are considered at the same time and sets of
edge points are sought according to some similarity constraint, such as points which
share the same edge equation.

5. Explain the region growing segmentation with example. [2015]

Answer:
Segmentation divides an image into its constituent parts or objects. Level of subdivision
depends on the problem being solved. Segmentation stops an object of interest in an
application have been isolated. Segmentation is concerned with dividing an image into
meaningful regions. For example, for an air to ground target acquisition system, interest may
lie in identifying vehicles on the road.
-segment the road from the image
-segment contents of the road down to objects of a range of size that corresponds to the
potential vehicle
-no need to go below this level or segment outside the road boundary
Segmentation algorithm for monochrome images is based on one of the two basic properties
of grey level values.
[Link]
2. Similarity
The segmentation algorithm is pixel oriented. For discontinuity the approaches to partition an
image based on abrupt changes in grey level.
The region in the image is a group of connected pixels with similar properties. Each pixel is
assigned to a particular object or region.
Region Growing:
Region growing is an approach to image segmentation in which neighboring pixels are
examined and added to a region class if edges are detected.
This process is iterated for each boundary pixel in the region. Adjacent region is found a region
merging algorithm is used in which weak edges are dissolved and strong edges are left intact.
Region growing requires a seed, to begin with. Initially, the seed would be a region, but it
would be a single pixel. A new segment is grown from the seed by eliminating as many
neighboring cells as possible that meet the homogeneity criteria. The resultant segment is then
recovered from the process.
A new seed is chosen from the remaining pixel. This continues until all pixels have been
allocated to a segment. The selection of homogeneity criteria in image growing depends not
only on the problem under consideration but also on the type of image to be segmented.
Region growing algorithm varies depending on the criteria used to decide whether a pixel
should be considered in the region or not. The connectivity type used to determine neighbors
and the strategy used to visit neighboring pixels.

[Link] is image segmentation ? [2013]

Answer:
Segmentation divides an image into its constituent parts or objects. Level of subdivision
depends on the problem being solved. Segmentation stops an object of interest in an
application have been isolated. Segmentation is concerned with dividing an image into
meaningful regions. For example, for an air to ground target acquisition system, interest may
lie in identifying vehicles on the road.
-segment the road from the image
-segment contents of the road down to objects of a range of size that corresponds to the
potential vehicle
-no need to go below this level or segment outside the road boundary
Segmentation algorithm for monochrome images is based on one of the two basic properties
of grey level values.
[Link]
2. Similarity
The segmentation algorithm is pixel oriented. For discontinuity the approaches to partition an
image based on abrupt changes in grey level.
7. Write down the importance of edge detection. [2013]
Answer:
Most of the shape information of an image is enclosed in edges. So first we detect these edges
in an image and by using these filters and then by enhancing those areas of image which
contains edges, sharpness of the image will increase and image will become clearer.
Here are some of the masks for edge detection that we will discuss in the upcoming tutorials.
• Prewitt Operator
• Sobel Operator
• Robinson Compass Masks
• Krisch Compass Masks
• Laplacian Operator.
Above mentioned all the filters are Linear filters or smoothing filters.

8. Discuss about region based segmentation. [2014]

Answer:
The region in the image is a group of connected pixels with similar properties. Each pixel is
assigned to a particular object or region.
Region Growing:
Region growing is an approach to image segmentation in which neighboring pixels are
examined and added to a region class if edges are detected.
This process is iterated for each boundary pixel in the region. Adjacent region is found a region
merging algorithm is used in which weak edges are dissolved and strong edges are left intact.
Region growing requires a seed, to begin with. Initially, the seed would be a region, but it
would be a single pixel. A new segment is grown from the seed by eliminating as many
neighboring cells as possible that meet the homogeneity criteria. The resultant segment is then
recovered from the process.
A new seed is chosen from the remaining pixel. This continues until all pixels have been
allocated to a segment. The selection of homogeneity criteria in image growing depends not
only on the problem under consideration but also on the type of image to be segmented.
Region growing algorithm varies depending on the criteria used to decide whether a pixel
should be considered in the region or not. The connectivity type used to determine neighbors
and the strategy used to visit neighboring pixels.

9. Define image subtraction, image negative and gray level slicing. [2012]
Answer:
Image subtraction
Image subtraction or pixel subtraction is a process whereby the digital numeric value of one
pixel or whole image is subtracted from another image. This is primarily done for one of two
reasons – leveling uneven sections of an image such as half an image having a shadow on it,
or detecting changes between two images. This detection of changes can be used to tell if
something in the image moved. This is commonly used in fields such as astrophotography to
assist with the computerized search for asteroids or Kuiper belt objects in which the target is
moving and would be in one place in one image, and another from an image one hour later
and where using this technique would make the fixed stars in the background disappear leaving
only the target.

image negative
In photography, a negative is an image, usually on a strip or sheet of transparent plastic film,
in which the lightest areas of the photographed subject appear darkest and the darkest areas
appear lightest. This reversed order occurs because the extremely light-sensitive chemicals a
camera film must use to capture an image quickly enough for ordinary picture-taking are
darkened, rather than bleached, by exposure to light and subsequent photographic processing.
In the case of color negatives, the colors are also reversed into their respective complementary
colors. Typical color negatives have an overall dull orange tint due to an automatic color-
masking feature that ultimately results in improved color reproduction.

10. What is image segmentation ? Discuss different types of image segmentation

techniques. [2020]

Image segmentation: Segmentation subdivides an image into its constituent regions or

objects. The level to which the subdivision is carried depends on the problem being solved.
That is, segmentation should stop when the objects of interest in an application have been
isolated.
Techniques:
Image segmentation algorithms generally are based on one of two basic porperties of intensity
values:
i)Discontinuity
e.g. Edges in an image

ii)Similarity
e.g. Thresholding, region growing, and region splitting and merging.

[Link] can you detect a point in images? [2020]

Answer:

Point Detection:

The response of the mask at any point in the image is given by

R= 𝑊1 𝑍1 + 𝑊2 𝑍2 + ⋯ … … + 𝑊9 𝑍9

= ∑9𝑖=1 𝑊𝑖 𝑍𝑖

𝑍𝑖 = 𝐺𝑟𝑎𝑦 𝑙𝑒𝑣𝑒𝑙

𝑊𝑖 = 𝑀𝑎𝑟𝑘 𝐶𝑜𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡

Now consider the following Point detection mask.

-1 -1 -1

-1 8 -1

-1 -1 -1

Fig: Point Detection Mask.

Using the mask in the figure we say that a point has been detected at the location on which
the mask is centered if,

|R| ≥ T

Where T is a non-negative threshold and R is given by equation. Basically, this formulation

measures the weighted differences between the center point and its neighbors.

The idea is that an isolated point a point whose gray level is significantly different from its
background and which is located in a homogeneous or nearly homogeneous area will be
quite different from its surroundings and thus be easily detectable by this type of mask.

The mask coefficients sum to zero, indicating that the mask response will be zero in areas of
constant gray level.

[Link] down the edge linking procedure. [2011]

Edge linking and boundary detection operations are the fundamental steps in any image
understanding. Edge linking process takes an unordered set of edge pixels produced by an
edge detector as an input to form an ordered list of edges. Local edge information are
utilized by edge linking operation; thus edge detection algorithms typically are followed by
linking procedure to assemble edge pixels into meaningful edges. One of the simplest
approaches of linking edge points is to analyze the characteristics of pixels in a small
neighborhood (say, 3 x 3 or 5 x 5) about every point (x, y) in an image that has undergone
edge-detection. All points that are similar are linked, forming a boundary of pixels that share
some common [Link] two principal properties used for establishing similarity of
edge pixels in this kind of analysis are (1) the strength of the response of the gradient
operator used to produce the edge pixel; and (2) the direction of the gradient vector. The first
property is given by the value of , the gradient. Thus an edge pixel with coordinates in a
predefined neighborhood of (x, y) is similar in magnitude to the pixel at (x, y) if where E is a
non negative thresholdThe direction (angle) of the gradient vector is given by. An edge pixel
at in the predefined neighborhood of (x, y) has an angle similar to the pixel at (x, y) ifwhere
A is a nonnegative angle threshold. As noted in 9.2.3, the direction of the edge at (x, y)
is perpendicular to the direction of the gradient vector at that point.A point in the predefined
neighborhood of (x, y) 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
book keeping procedure is to assign a different gray level to each set of linked edge pixels.
[Link] use of motion in segmentation. [2016]

Answer:
Motion Segmentation is the task of identifying the independently moving objects (pixels) in
the video and separating them from the background motion. If the background consists of a
plane, then we can register the various frames onto a common frame perfectly,
using projective transformations. The areas of the image that do not register well belong to
the moving objects. If the registration of all frames is perfect, we can take the image
difference of two registered images. The pixels that have high intensity difference can be
classified as moving objects. However, this simple scheme has a lot of false alarms since
registration is not always perfect. In the presence of slight misregistration, the pixels near
prominent edges usually flag up as moving pixels. In order to reduce the false alarms, we
resort to a detection scheme that combines evidences from (1) image differences, and (2)
optical flow discrepancy.
Example shows a frame marking the moving object pixels in the video sequence detected in
that particular frame.

[Link] down the line detection algorithm for Horizontal , Vertical , +45°
And -45°.
Answer:

Line Detection
Consider the masks shown in figures.

Horizontal +45° Vertical

-45°
-1 -1 2
-1 -1 -1
-1 2 -1
2 2 2
2 -1 -1
-1 -1 -1 -1 2 -1

-1 2 -1

-1 2 -1
2 -1 -1

-1 2 -1

Figure-8.3: Line masks. -1 -1 2

❖ If the first mask were moved around an image, it would

respond more strongly to the lines (one pixel thick) oriented horizontally.
❖ With a constant background, the maximum response would result when the line passed
through the middle row of the mask.
❖ The second mask responds best to the lines oriented at +45°
The third mask to vertical lines and the fourth mask to lines in the -45° direction.
❖ The coefficients in each mask sum to zero, indicating a zero response from the masks in
areas of constant gray level.
❖ The response of the masks at any point in the image is given by R=W1Z1+W2Z2+.....+W9Z9
= =∑9𝑖=1 wi zi;[For 3x3 mask]…...(1)
❖ Let R1,R2,R3,and R4 denote the responses of the masks in Fig-4 from left to right, where
the R's are given by equation(1).
❖ Suppose that the four masks are run individually through an image. If at a certain that
point is said to be more likely associated with a line in the direction of mask i.
❖ e.g.,
If at a point in the image
❖ |R1|>|Rj|, for all j=2,3,4
That particular point is said to be more likely associated with a horizontal line.
15. Obtain the Huffman’s code for the following sequence:-
5 5 5 5 8 8 4 2 7 7 7 2
2
2 2 4 4 7 7 7 7 2 2 2 2
2
2 2 2 2 2 2 2 2 2 2 2 4
4
4
What is average code length with and without compression? [2015]

Solution:
The total frequency is 40
Let,
𝑎2 = 21, 𝑎4 = 6, 𝑎5 = 4, 𝑎7 = 7, and 𝑎8 = 2,

The possibilities,

21 6
𝑎2 = 40 = 0.525, 𝑎4 = 40 = 0.15

4 7 2
𝑎5 = 40 = 0.1, 𝑎7 = 40 = 0.175, 𝑎8 = 40 = 0.05

Symbol Possibilities Source reduction

1 2 3

𝑎2 0.525 0 0.525 0 0.525 0 0.525 0

𝑎7 0.175 11 0.175 11 0.3 10 0. 475 1

𝑎4 0.15 100 0.15 100 0.175 11

𝑎5 0.1 101 0 0.15 101

𝑎8 0.05 101 1

Average length of code:

[Link]= (0.525)1 + (0.175)2 + (0.15)3 + (0.1)4 + (0.05)4
= 1.925 bits (Answer)