Digital Image Processing (18EC733)

Digital Image Processing (18EC733)

Module – 2
Image Enhancement in Spatial Domain:
Image Sampling and Quantization, Some Basic Relationships Between Pixels, Linear and
Nonlinear Operations. Some Basic Intensity Transformation Functions, Histogram
Processing, Fundamentals of Spatial Filtering, Smoothing Spatial Filters, Sharpening Spatial
Filters.

2.1 Image Sampling and Quantization

2.1.1 Basic concepts in Sampling and Quantization
Output of most sensors is a continuous voltage waveform whose amplitude and spatial
behavior are related to the physical phenomenon being sensed. To create a digital image, we
need to convert continuous sensed data into digital form. This involves two processes:
sampling and quantization.
Consider a continuous image f that we want to convert to digital form. An image may be
continuous with respect to the x- and y-coordinates, and also in amplitude. To convert it to
digital form, we have to sample the function in both coordinates and in amplitude. Digitizing
the coordinate values is called sampling. Digitizing the amplitude values is called
quantization.

Dept. of ECE, GAT 1

 Digital Image Processing (18EC733)

Figure A shows image which is continuous both spatially and in terms of intensities. AB is a
row of all pixels along the lines along which sampling is done. Figure B plots the intensities
of each pixel, against the location of the pixels. The random variations are due to image
noise. Figure C shows the sampled points along the line AB. Here, the equally spaced points
(ticks) indicate the linearly spaced samples along the line. Note that while the image is
spatially sampled, it is still continuous in intensities. Figure D shows the quantized signal
from Figure C. The continuous range of intensity values has now been discretized into 8
intervals, from black to white, assigning the closest value to each sample.
This entire process is repeated for each line to produce a digitized 2-D image. In practice,
spatial sampling is determined by the sensor arrangement (limited control), or by mechanical
motion of sensor element (controllable), or quality of optical component (hard to control).
When a sensing array is used for image acquisition, there is no motion and the number of
sensors in the array establishes the limits of sampling in both directions.

2.1.2 Representing Digital Images

Let f(s, t) represent a continuous image function of two continuous variables, s and t. This is
converted to a digital image by sampling and quantization. Suppose that we sample the
continuous image into a 2-D array, f(x, y), containing M rows and N columns, where (x, y) are
discrete coordinates (0 ≤ x ≤ M-1 and 0 ≤ y ≤ N-1). The section of real plane spanned by the
coordinates of an image is called the spatial domain, with x and y being referred to as spatial
variables or spatial coordinates.

Dept. of ECE, GAT 2

 Digital Image Processing (18EC733)

Three basic ways to represent f(x, y):

• 2 axes representing spatial location, third representing intensities.
• As shown on monitor or photograph.
• Graphically, in terms of arrays of values.

Image displays are best for fast visualization. Numerical arrays are used for processing and
algorithm development. M X N Numerical Array can be written as:

Each element of this matrix is called an image element, picture element, pixel, or pel.
Sometimes, it is advantageous to use a more traditional matrix notation to denote a digital
image and its elements:

Image can also be represented as a vector v, of size MNx1 elements, collected column wise.

Dept. of ECE, GAT 3

 Digital Image Processing (18EC733)

Note that the origin of a digital image is at the top left. Positive x-axis extends downward, and
the positive y-axis extends to the right. (Convention based on Raster Scan).
Express Sampling and Quantization mathematically:
Let Z and R denote the set of integers and the set of real numbers, respectively. The sampling
process may be viewed as partitioning the xy-plane into a grid, with the coordinates of the
center of each cell in the grid being a pair of elements from the Cartesian product Z2 which is
the set of all ordered pairs of elements (zi, zj), with zi and zj being integers from Z. f(x,y) is a
digital image if (x, y) are integers from Z2 and f is a function that assigns an intensity value
(that is, a real number from R) to each distinct pair of coordinates (x, y). This functional
assignment is the quantization process.
If f(x,y) is also an integer, Z replaces R, to get a digital image. M, N and L (intensity levels)
have to be decided during digitization. M and N are to be positive integers. Due to quantizing
hardware considerations, L is typically a power of 2. : L = 2k where k is bit of image.
We assume that the discrete levels are equally spaced and that they are integers in the interval
[0, L - 1]. Dynamic range of an imaging system is the ratio of the maximum measurable
intensity to the minimum detectable intensity level. The upper limit is determined by
saturation and the lower limit by noise. Contrast is the difference in intensity between the
highest and lowest intensity levels in an image.

The number, b, of bits required to store a digitized image is:

b=M*N*k
When M = N, this equation becomes:
b = N2 k

Dept. of ECE, GAT 4

 Digital Image Processing (18EC733)

2.1.3 Spatial and Intensity Resolution

Spatial Resolution is a measure of the smallest discernible detail in an image (line pairs per
unit distance, dots (pixels) per unit distance, etc). Alternatively, it is largest number of
discernible line pairs per unit distance (alternating black and white lines). Dots per unit
distance is a measure of image resolution used commonly in the printing and publishing
industry (dpi). To be meaningful, measures of spatial resolution must be stated with respect to
spatial units.
Intensity (Gray Level) Resolution refers to the smallest discernible change in intensity
level. Number of intensity levels usually is an integer power of two (Usually 8, 16 or 32 bits).

Dept. of ECE, GAT 5

 Digital Image Processing (18EC733)

Effects of Reducing Spatial Resolution

1250 dpi 300 dpi

We observe that with a reduction in the spatial resolution, a lot of fine details in the image are
lost, and the image gets degraded. These effects can be reduced by using appropriate
interpolation methods.
Checkerboard effect – When spatial resolution is very low, the images appear as blocks and
ridges (Checkerboard pattern). Thus, a curve may appear as a staircase.
The checkerboard effect is caused by pixel replication, that is, lower resolution images were
duplicated in order to fill the display area.

Effects of Reducing Intensity Resolution

256-Level image 128-Level image

We notice as the intensity resolution becomes smaller, very fine ridge-like structures in areas
of constant or nearly constant intensity are seen (particularly in the skull). This effect, caused
by the use of an insufficient number of intensity levels in smooth areas of a digital image, is
called false contouring. It appears in the image as contours of gray levels not present in the
original image.
The results illustrate the effects produced on image quality by varying N (Spatial
Resolution) and k (Intensity Resolution) independently. An early study by Huang [1965]
attempted to quantify experimentally the effects on image quality produced by varying N and
k simultaneously.

Dept. of ECE, GAT 6

 Digital Image Processing (18EC733)

The experiment consisted of a set of subjective tests. Images similar to those shown were
used.
• The woman’s face - image with relatively little detail.
• Cameraman - intermediate amount of detail.
• Crowd picture - a large amount of detail.
Sets of these three types of images were generated by varying N and k, and observers were
then asked to rank them according to their subjective quality. Results were summarized in the
form of so-called isopreference curves in the Nk-plane. Each point in the Nk-plane
represents an image having values of N and k equal to the coordinates of that point. Points
lying on an isopreference curve correspond to images of equal subjective quality.
It was found that the isopreference curves tended to shift right and upward. This shift up and
right in the curves simply means larger values for N and k, which implies better picture
quality. Curves tend to become more vertical as the detail in the image increases. This result
suggests that for images with a large amount of detail only a few intensity levels may be
needed. Decrease in k tends to increase the apparent contrast, a visual effect that humans
often perceive as improved quality in an image.

Dept. of ECE, GAT 7

 Digital Image Processing (18EC733)

2.1.4 Image Interpolation

Used extensively in zooming, shrinking, rotating and geometric corrections.
Resampling Methods
➢ Shrinking
➢ Zooming
• Interpolation = using known data to estimate values at unknown locations (Zooming).
• Decimation = reducing the number of pixels (Shrinking).
a) Image Shrinking
Process of reducing spatial resolution by removing certain rows and columns from original
image (subsampling).
Eg: Consider a 1024x1024 image to be shrunk to 512x512.
Alternate rows and columns need to be discarded to get the shrunken image. Further filters
can be used to clean up the image.

b) Image Zooming
• Process of oversampling image to increase spatial resolution.
• Increases the total number of pixels in the image.
• Similar to interpolation process.
• 2 stages:
➢ creation of new pixel locations.
➢ Assignment of new gray level values to these locations.
• Interpolation methods:
➢ Nearest neighbour (Pixel replication)
➢ Bilinear interpolation
➢ Bicubic interpolation

a) Nearest Neighbour Interpolation

First, extra rows and columns are created in zoomed image, and pixel values of the nearest
neighbour are copied into newly created pixels. Has tendency to produce undesirable
artifacts, like severe distortion of straight edges. Used very rarely.

Dept. of ECE, GAT 8

 Digital Image Processing (18EC733)

b) Bilinear Interpolation
New rows and columns are created, and values are assigned based on linear average of
neighbouring pixels. Bilinear interpolation processes 2x2 (4 pixels) squares. First, linear
average of neighbouring row pixels are calculated and then column pixels are used in next
step.

c) Bicubic Interpolation

Dept. of ECE, GAT 9

 Digital Image Processing (18EC733)

2.2 Basic Relationships between Pixels

(x-1, y-1) (x-1, y) (x-1, y+1)

(x, y-1) (x, y) (x, y+1)

(x+1, y-1) (x+1, y) (x+1, y+1)

2.2.1 Neighbors of a Pixel

• A pixel p at coordinates (x, y) has four horizontal and vertical neighbors whose
coordinates are given by:
(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)
• This set of pixels, called the 4-neighbors of p, is denoted by N4(p).
• Each pixel is a unit distance from (x, y), and some of the neighbor locations of p lie
outside the digital image if (x, y) is on the border of the image.
• The four diagonal neighbors of p are denoted by ND(p) and have coordinates:
(x + 1, y + 1), (x + 1, y - 1), (x - 1, y + 1), (x - 1, y - 1)
• These points, together with the 4-neighbors, are called the 8-neighbors of p, denoted by
N8(p).

(a) 4-neighborhood N4(p)

(b) Diagonal neighborhood ND(p)
(c) 8-neighborhood N8(p)

2.2.2 Adjacency, Connectivity, Region and Boundaries

1) Adjacency
• Let V be the set of intensity values used to define adjacency.
• In a binary image, V = {1} if we are referring to adjacency of pixels with value 1.
• In a gray-scale image, the idea is the same, but set V typically contains more elements.
• Eg: in the adjacency of pixels with a range of possible intensity values 0 to 255, set V
could be any subset of these 256 values.

Dept. of ECE, GAT 10

 Digital Image Processing (18EC733)

Types of Adjacency
1. 4-adjacency: Two pixels p and q with values from V are 4-adjacent if q is in the set
N4(p).
2. 8-adjacency: Two pixels p and q with values from V are 8-adjacent if q is in the set N8(p)
3. m-adjacency (mixed adjacency): Two pixels p and q with values from V are m-adjacent
if:
a) q is in N4(p), OR
b) q is in ND(p), and the set N4(p) ∩ N4(q) has no pixels whose values are from V.

2) Path
• A (digital) path (or curve) from pixel p with coordinates (x, y) to pixel q with coordinates
(s, t) is a sequence of distinct pixels with coordinates:
(x0, y0), (x1, y1), ….. , (xn, yn)
where (x0, y0) = (x, y), (xn, yn) = (s, t), and pixels (xi, yi) and (xi-1, yi-1) are adjacent for
1 ≤ i ≤ n.
• In this case, n is the length of the path.
• If (x0, y0) = (xn, yn), the path is a closed path.
• We can define 4-, 8-, or m-paths depending on the type of adjacency specified.

Dept. of ECE, GAT 11

 Digital Image Processing (18EC733)

Problem
Consider the image segment shown in figure. Compute length of the shortest-4, shortest-8 &
shortest-m paths between pixels p & q where, V = {1, 2}.

Solution:
• V = {1, 2} means all pixels along the path have to have values 1 or 2 only.
• Let us consider each case separately:
Case 1: 4- Path

We see that 4-Path does not exist between p and q, for V={1,2}.

Case 2: 8- Path

We see that the shortest 8-path is of length 4.

Case 3: M-path

We see that M-path exists, and the shortest m-path is of length 5.

Dept. of ECE, GAT 12

 Digital Image Processing (18EC733)

Problem
For V = {2, 3, 4}, compute the length of the shortest 4-, 8- m=paths between P and Q in the
following:

Solution:

3) Connectivity and Regions

• Let S represent a subset of pixels in an image.
• Two pixels p and q are said to be connected in S if there exists a path between them
consisting entirely of pixels in S.
• For any pixel p in S, the set of pixels that are connected to it in S is called a connected
component of S.
• If it only has one connected component, then set S is called a connected set.
• Let R be a subset of pixels in an image.
• We call R a region of the image if R is a connected set.
• Two regions, Ri and Rj are said to be adjacent if their union forms a connected set.
• Regions that are not adjacent are said to be disjoint.

Dept. of ECE, GAT 13

 Digital Image Processing (18EC733)

Problem
Consider the two image subsets, S1 and S2, shown in the following figure. For V={1},
determine whether these two subsets are (a) 4-adjacent, (b) 8-adjacent, or (c) m-adjacent.

Solution:
• Not 4-connected subsets, since the neighboring 1s are NOT 4-adjacent.
• Both 8-connected and m-connected because the neighboring 1s are both 8-adjacent and
m-adjacent.

4) Boundary
• The boundary (also called the border or contour) of a region R is the set of points that
are adjacent to points in the complement of R.
• Border of a region is the set of pixels in the region that have at least one background
neighbor.
• If R happens to be an entire image, then its boundary is defined as the set of pixels in the
first and last rows and columns of the image.
• An image has no neighbours beyond its border.
• Inner border of the region corresponds to boundary points along foreground.
• Outer border corresponds to boundary points along background.

• RED colored 1 is NOT a member of border if 4-connectivity is used between region and
background.
• However, It is, if 8-connectivity is used.

Dept. of ECE, GAT 14

 Digital Image Processing (18EC733)

5) Edges
• Unlike Boundaries, which form a closed path and are GLOBAL, Edges are formed from
pixels with derivative values that exceed a preset threshold.
• The idea of an edge is a LOCAL concept that is based on a measure of gray-level
discontinuity at a point.
• It is possible to link edge points into edge segments, and sometimes these segments are
linked in such a way that they correspond to boundaries, but this is not always the case.
• The one exception in which edges and boundaries correspond is in binary images.

2.2.3 Distance Measures

• For pixels p, q, and z, with co-ordinates (x, y), (s, t), and (v, w), respectively, D is a
distance function or metric if:
➢ D(p, q) ≥ 0 (D(p, q) = 0 if p = q)
➢ D(p, q) = D(q, p)
➢ D(p, z) ≤ D(p, q) + D(q, z) [Triangular Inequality]

a) Euclidean Distance

b) City Block Distance (D4 distance)

Dept. of ECE, GAT 15

 Digital Image Processing (18EC733)

c) Chessboard Distance (D8 distance)

Dept. of ECE, GAT 16