Module -3

Digital Image Processing

Operations
Learning Objectives
1. Overview of Image Processing operation
2. Image Topology (Neighborhood and Connectivity)
3. Arithmetic, Logical & Spatial, Geometric operation
BASIC RELATIONSHIPS AND DISTANCE METRICS
Image Coordinate System

Pixels can be visualized logically and physically.

Logical pixel specify the points of continuous 2D function these are logical in the
sense that they specify a local but occupy no physical area normally this is
represented in the Cartesian first co-ordinate.
 Image Coordinate system

Physical pixels occupy a small amount of space when displayed on

the output device digitized images indicate physical pixels, are
represented in the Cartesian 4th coordinate
 Image Topology
Image topology is a branch of image processing deals with the
fundamental properties of image such as image Neighborhood,
Adjacency and Connectivity.
Neighborhood of a given reference pixels are those pixels with which
the given reference pixel share edges and corners.
The set of pixels {(x+1,y),(x-1,y),(x,y+1), (x,y-1)} are 4 neighbor
pixel
 Diagonal Elements
The set of pixels {(x-1,y-1),(x+1,y+1),(x-1,y+1), (x+1,y-1)} are
diagonal neighbor .
 8-Neighbourhood
Its Union of 4 neighbor pixel and Diagonal Pixel , The set of
pixels {(x+1,y),(x-1,y),(x,y+1), (x,y-1), (x+1,y),(x-1,y),(x,y+1),
(x,y-1)}
 Connectivity
• The relationship between two or more pixel is defined by pixel
connectivity.
• Connectivity information is used to establish the boundaries of the
objects.
• The pixel p and q are said to be connected if certain condition on
pixel brightness specified by set V and spatial adjacency are satisfied.
Binary image {0,1}
Gray scale images {0,255}
Connectivity
 8-connectivity V/S m-connectivity

• 8 connectivity has Multiple path or loop is present.

• In M connectivity there is no multiple paths
 Examples: Connectivity
V = {1, 2}

0 1 1 0 1 1 0 1
1
0 2 0 0 2 0 0 2
0
8-adjacent
0 0 1 0 0 1 0 0
1

11
 Examples: Connectivity
V = {1, 2}

0 1 1 0 1 1 0 1
1
0 2 0 0 2 0 0 2
0
8-Connectivity m-Connectivity
0 0 1 0 0 1 0 0
1

12
 Examples: Adjacency and Path
V = {1, 2}

0 1,1 1 1,2 1 1,3 0 1 1 0 1

1
0 2,1 2 2,2 0 2,3 0 2 0 0 2
0
8-adjacent m-adjacent
0 3,1 0 3,2 1 3,3 0 0 1 0 0
(i)
1
The 8-path from (1,3) to (3,3):
(1,3), (1,2), (2,2), (3,3)
The m-path from (1,3) to (3,3):
(1,3), (1,2), (2,2), (3,3)
(ii) (1,3), (2,2), (3,3)

13
 Relations
Binary relation between two pixel A and B denoted aRb it specifies a
pair of elements of an image

if all these properties holds the relationship is called as equivalence

relation.
 Distance Measures
The distance between the pixels P and Q in an image can be given by
distance measure such as
• Euclidian distance,
• D4 distance
• D8 distance
Consider the three pixels P,Q and Z if the coordinates of the pixels
are P(x,y), Q(s,t), Z(u,w), the distance between the pixels can be
calculated.
Distance Measures

© Oxford University Press 2011

Distance

17
18
Weeks 1 & 2 19
© Oxford University Press 2011
 Important image Characteristics
1. The set of pixels that has connectivity in a binary image is said
to be characterized by the connected set.
2. A digital path or curve from pixel P to another pixel Q is a set of
points P1,P2, P3,… PN. number of pixels is called the length , if
x0=xn, y0=yn path is called a closed path
3. R is called a region if it is a connected component.
4. if a path between any two pixels P and Q lies within the
connected set, it is, called a connected component ,then set S
connected set . A connected set is called a Region.
5. Two regions R1 and R2 are called adjacent if the union of these
sets also forms a connected component. if the regions are not
adjacent is disjoint. 0 1 0 0 1 1
1 1 0 1 1 1
1 1 1 0 1 1

Region -1 Region -2
 Important image Characteristics

6. The border of the image is called contour or boundary.

A boundary is a set of pixels covering a
region that has one or more neighbors outside
the region.
Typically in a binary image there is a foreground object and a
background object.
The border of the foreground object may have at least one neighbor
in the background. if the border pixels are within the range region
itself it is called inner boundary. This need not be closed.
 Important image Characteristics
7. Edges are present wherever there is an abrupt intensity
changes among the pixels. Edges are similar to boundaries but
may or may not be connected. However boundaries are global
and have a closed path . Figure 3.1 illustrate that can be observed
that edge provides e an outline of the object the pixels that are
covered by the edges lead to region regions

Region -2

Region -1

Edge
 Classification of Image Operations
Reason for classification
1. To know the nature of operations
2. Expected results
3. Computational burden.
Classification based on neighborhood
• Point operations are those whose output value at a specific co-
ordinate is is dependent only on the input values.
• Local operation is one who's output value at a specific co-
ordinate is dependent on the input value in the neighborhood of
the pixel
• Global are those whose values output values at a specific
coordinate is dependent on all the values in the input image
Classification
Image Vs Array Operations
Arithmetic Operations
Arithmetic operations - Addition

© Oxford University Press 2011

© Oxford University Press 2011
Image Subtraction

© Oxford University Press 2011

© Oxford University Press 2011
Image Multiplication
© Oxford University Press 2011
 Image Division

Some of the practical applications of image division is as follows:

1. Change detection
2. Separation of luminance and reflectance components
3. Contrast reduction
Image Division
Logical Operations
 XOR
The practical applications of the XOR and XNOR operations
are as follows:
1. Change detection
2. Use as a subcomponent of a complex imaging operation.
XOR for identical inputs is zero. Hence it can be observed that
the common region of image 1 and image 2 in Fig, is zero and
hence dark.
 NOT Operation
Truth table of the OR and NOR operators
For grey scale values, the inversion operation is described as
g(x,y)= 255- f(x,y)
The practical applications of the inversion operator are as follows:
1. Obtaining the negative of an image. shows the negative of the
original image shown in Fig.
2. Making features clear to the observer
3. Morphological processing
Similarly, two images can be compared
using operators such as
• = Equal to
• >Greater than
• >= Greater than or equal to
• < Less than, <= Less than or equal to
• Not equal to
Geometrical Operation

© Oxford University Press 2011

Scaling Operations
Zooming
 Reflection
Reflection along
X
Shearing
Rotation
Affine Transform
Inverse Transform
© Oxford University Press 2011
© Oxford University Press 2011
Image Interpolation Techniques

What is the need for Interpolation Techniques

Transforms can be of two types. Affine transforms often produce
pixels of the resultant image that cannot be fit as some of the pixel
values are non-integers and often go beyond the acceptable range.
This results in gaps(or holes) and issues related to number of pixels
and range. So interpolation techniques are required to solve these
issues

© Oxford University Press 2011

Image Interpolation Techniques

Forward Mapping
Forward mapping is the process of applying transformations
iteratively to every pixel in the image, yielding a new coordinate
position and copying the values of the pixel to a new position.

Backward Mapping
Backward mapping is the process of checking the pixels of the output
image to determine the position of the pixels in the input image. This
is used to guarantee that all the pixels of the input image are
processed.

© Oxford University Press 2011

Image Interpolation Techniques
Since these new coordinate positions are not integers, the rotation
process cannot be carried out. Thus, the process may leave a gap in the
new coordinate position, which creates poor quality output.
Therefore, whenever a geometric transformation is performed, a
resampling process should be carried out so that the desirable quality
is achieved in the resultant image.
The resampling process creates new pixels so that the quality of the
output is maintained. In addition, the rounding off of the new
coordinate position (3.535,10.605) should be carried out as (4,11).
This process of fitting the output to the new coordinates is called
interpolation.
Interpolation is the method of calculating the expected values for a
function with known pixels.

© Oxford University Press 2011

Image Interpolation Techniques
During the process of both forward and backward mapping, it may
happen that pixels cannot be fitted into the new coordinates. For
example, consider the process of rotation of a point(10,5) by 450. This
yields
x’ =xcos(theta)-ysin(theta)
=10 cos(45)-5sin(45)
=10(0.707)-5(0.707)
=3.535
y’ = xsin(theta)+ycos(theta)
\= 10 sin(45)+5cos(45)
= 10(0.707)+5(0.707)
=10.605
In addition, the rounding off of the new coordinate position
(3.535,10.605) should be carried out as (4,11). This process of fitting
the output to the new coordinates is called interpolation.
Interpolation is the method of calculating the ©expected values
Oxford University Press 2011 for a
function with known pixels.
Image Interpolation Techniques
Interpolation is the method of calculating the expected values for a
function with known pixels.
Some of the popular interpolation techniques are:
• Nearest neighbor technique
• Bilinear technique
• Bicubic technique

Nearest neighbor technique

• The most elementary form of interpolation is nearest neighbor
interpolation or zero-order interpolation.
• This technique determines the closest pixel and assigns it to every
pixel in the new image matrix, that is, the brightness of the pixels is
equal to the closest neighbor.
• Sometimes, this may result in pixel blocking and can degrade the
resulting image, which may appear spatially disordered. These
distortions are called aliasing. © Oxford University Press 2011
Image Interpolation Techniques
Bilinear interpolation
A more accurate interpolation scheme is bilinear interpolation. This is
called first-order interpolation.
Four neighbours of the transformed original pixels that surround the
new pixel are obtained and are used to calculate the new pixel value.
Linear interpolation is used in both the directions. Weights are
assigned based on the proximity. Then the process takes the weighted
average of the brightness of the four pixels that surround the pixels of
interest.
g(x,y)=(1-a)(1-b)f(x’,y’)+(1-a)bf(x a)bf(x’,y’+1)+
a(1)f(x’+1,y’)+abf(x’+1,y’+1)
If the desired pixel is very close to one of the four nearest neighbor
pixels, its weight will be much higher. This technique leads to blurring
of the edges. However, it reduces aliasing artefacts.
© Oxford University Press 2011
Image Interpolation Techniques
Bicubic interpolation
• High-order interpolation schemes takes more pixels into account.
• Second-order interpolation is known as cubic interpolation.
• It uses a neighbourhood of 16 pixels.
• This technique is very effective and produces images that are very
close to the original.
• In extreme cases, more than 64 neighbouring pixels can be used.
However, as the number of pixel increases, the computational
complexity also increases

© Oxford University Press 2011

Linear Interpolation

© Oxford University Press 2011

 Image Interpolation
• Downsampli
ng

© Oxford University Press 2011

© Oxford University Press 2011
Upsampling

© Oxford University Press 2011

 Set Operations
An image can be visualized as a set. For example, the following
binary image(Fig3 3.25) can be visualized as a set A={(0,0),(0,2),
(2,2)}. The coordinates values represent the value of 1.
Set operators can then be applied to the set to get the resultant,
which is useful for image analysis.
The complement of set A can be defined as the set of pixels that
does not belong to the set A.
Ac={c/c€A}
The reflection of the set is defined as
A={c=-a, a € A}
The union of two sets, A and B can be represented as
AUB={c/(c€A)v(c€B)} Where the pixel c belongs to A,B or both.

© Oxford University Press 2011

© Oxford University Press 2011
Morphology is a collection of operations based on set theory, to
accomplish various tasks such as
• Extracting boundaries,
• Filling small holes present in the image,
• Removing noise present in the image.

• Mathematical morphology is a very powerful tool for analyzing

the shapes of the objects that are present in the images.
Morphological operators often take a binary image and a mask
known as structuring element as input.
• The set operators such as intersection, union, inclusion and
complement can then be applied to images.
• Dilation is one of the two basic operators. It can be applied to
binary as well as grey scale images.
• This operation on binary image is that it gradually increases the
boundaries of the region, while the small holes that are present
in the images become smaller.
Let us assume that A and B are a set of pixel coordinates. The
dilation of A by B can be denoted as
A⊕B={(x,y)+(u,v): (x,y)€A,(u,v) €B}
Where x and y corresponds to the set A, and u and v corresponds
to the set B. The coordinates are added and the union is carried out
to create the resultant set. These kinds of operations are based on
Minkowski algebra.
A Dilation process for the bigger images requires a lot of
computational effort .
© Oxford University Press 2011
 Statistical Operations
Statistics plays an important role in image processing.
Statistical operations can be applied to the image to get the
desired results such as
•Manipulation of brightness
• Contrast.
Useful statistical operations
• Mean,
• Median,
• Mode and
• Mid-range.
The measures of data dispersion also includes
• Quartiles
• Inter-quartile range and
• Variance © Oxford University Press 2011
 Statistical Operations
Some of the frequently used statistical measures are the following

Mean is the average of all the values in the sample(population) and

is denoted as

The overall brightness of the grey scale image is measured using the
mean. This is calculated by summing all the values of the pixels of
an image and dividing it by the number of pixels in the image.

Sometimes the data is associated with a weight. This is called

weighted mean. The problem of mean is its extreme sensitivity to
noise. Even small changes in the input affect the mean drastically.
© Oxford University Press 2011
Median
Median is the value where the given Xi is divided into two equal
halves, with half of the values being lower than the median and
the other half higher. The procedure for obtaining the median is
to sort the values of the given Xi in ascending order. If the given
sequence has an odd number of values, the middle value is the
median. Otherwise, the median is the arithmetic mean of the two
middle values.
Mode
Mode is the value that occurs most frequently in the dataset. The
procedure for finding the mode is to calculate the frequencies for
all of the values in the data. The mode is the value(or values)
with the highest frequency. Normally, based on the mode, the
dataset is classified as unimodal, bimodal and trimodal. Any
dataset that has two modes is called bimodal.
Percentile
Percentiles are data that are less than the coordinate by some
percentage of the total value. For example, the median is the
50th percentile and can be denoted as [Link] 25th
percentile is called the first quartile and the 75th percentile is
called third quartile. Another measure that is useful to measure
dispersion is the inter-quartile range. The inter-quartile is
defined as Q0.75 [Link] quartile range is =0.5 X IQR
Unimodal curves are slightly skewed and the empirical relation
is
Mean-Mode=3x(Mean-Median)
• unimodal frequency curve is moderately skewed.
• In a normal distribution, the mean, median, and mode are the
same.
• In symmetrical distributions, it is possible for the mean and
median to be the same even though there may be several modes.
• In asymmetrical distributions, the mean and median are not the
same.
• These distributions are said to be skewed data where more than
half the cases are either above or below the mean.
Standard Deviation and Variance
The most commonly used measures of dispersion are variance and
standard deviation.
The mean does not convey much more than a middle point. For
example, the following datasets
{10,20,30} and {10,50,0},
both have a mean of 20.
The difference between these two sets is the spread of data.

Standard deviation is the average distance from the mean of the

dataset to each point.
 Entropy
• It’s a measure of the amount of orderliness that is present in
the image.
• The entropy can be calculated by assuming that the pixels are
totally uncorrelated.
• An organized system has low entropy and a complex system
has a very high entropy.
• Entropy also indicates the average global information content.
Its unit is bits per pixel.
• It can be computed using the formula

© Oxford University Press 2011

 Entropy
Where pi is the prior probability of the occurrence of the
message.
Let us consider a binary image, where the pixel assumes only two
possible states,0 or 1 and the occurrence of each state is equally
likely.
Hence, the probability is ½. Therefore, the entropy
H=-[1/2log(1/2)+1/2log(1/2)]=1 bit
Therefore, 1 bit is sufficient to store the intensity of the pixel.
Therefore, binary images are less complex.

© Oxford University Press 2011

 Entropy
Thus, entropy indicates the richness of the image. This can be
seen visually using a surface plot where pixel values are
plotted as a function of pixel position.

© Oxford University Press 2011

Entropy

© Oxford University Press 2011

Entropy

© Oxford University Press 2011

Entropy

© Oxford University Press 2011

Image Convolution

© Oxford University Press 2011

1D-Convolution

© Oxford University Press 2011

© Oxford University Press 2011
1D-Correlation
© Oxford University Press 2011
2D-Convolution

© Oxford University Press 2011

© Oxford University Press 2011
Properties of Convolution

© Oxford University Press 2011

Data Structures

© Oxford University Press 2011

Chain Code

© Oxford University Press 2011

RAG

© Oxford University Press 2011

Relational Structures

© Oxford University Press 2011

Hierarchical Structures

© Oxford University Press 2011

Pyramid Structures

© Oxford University Press 2011

Quadtree

© Oxford University Press 2011

Application Development

© Oxford University Press 2011

Summary
© Oxford University Press 2011