UNIT-I: Digital Image Fundamentals
Presented by:
Shahnawaz Uddin
DIGITAL IMAGE
PROCESSING (WLE-306)
Digital Image Processing (DIP)
“One picture is worth more than ten thousand words”
•Anonymous What is a Digital Image?
• An image is defined as “a two-dimensional function, f(x,y), where x and y are spatial (plane) coordinates, and the amplitude of f at any pair of coordinates (x, y) is called the intensity (gray level of the image) at that point. When x, y, and the amplitude values of f are all finite, discrete quantities, we call the image a digital image.”
• The field of DIP refers to processing digital images by means of a digital computer
• A digital image composed of a finite number of elements, each of which has a particular location and value, which are called picture elements/pixel/pels.
WLE-306(DIP) 3
We can define three types of computerized processes:
Low-, mid-, and high-level.
Low: image preprocessing, noise reduction, enhance contrast etc.
Mid: segmentation, sorting and classification.
High: assembly of all components into a meaningful coherent form
Low Level Process Input: Image
Output: Image Examples: Noise removal, image sharpening
Mid Level Process Input: Image
Output: Attributes Examples: Object recognition,
segmentation
High Level Process Input: Attributes
Output: Understanding Examples: Scene
understanding,
autonomous navigation
Digital Image Processing (DIP)
Fundamental Steps in DIP
Key Stages in Digital Image Processing
Image Acquisition
Image Restoration
Morphological Processing
Segmentation
Representation
& Description Image
Enhancement
Object Recognition
Problem Domain
Colour Image Processing
Image Compression
Key Stages in Digital Image Processing:
Image Aquisition
Image Acquisition
Image Restoration
Morphological Processing
Segmentation
Representation Image
Enhancement
Object Recognition
Key Stages in Digital Image Processing:
Image Enhancement
Image Acquisition
Image Restoration
Morphological Processing
Segmentation
Representation
& Description Image
Enhancement
Object Recognition
Problem Domain
Colour Image Processing
Image Compression
Key Stages in Digital Image Processing:
Image Restoration
Image Acquisition
Image Restoration
Morphological Processing
Segmentation
Representation Image
Enhancement
Object Recognition
Key Stages in Digital Image Processing:
Morphological Processing
Image Acquisition
Image Restoration
Morphological Processing
Segmentation
Representation
& Description Image
Enhancement
Object Recognition
Problem Domain
Colour Image Processing
Image Compression
Key Stages in Digital Image Processing:
Segmentation
Image Acquisition
Image Restoration
Morphological Processing
Segmentation
Representation Image
Enhancement
Object Recognition
Key Stages in Digital Image Processing:
Object Recognition
Image Acquisition
Image Restoration
Morphological Processing
Segmentation
Representation
& Description Image
Enhancement
Object Recognition
Problem Domain
Colour Image Processing
Image Compression
Key Stages in Digital Image Processing:
Representation & Description
Image Acquisition
Image Restoration
Morphological Processing
Segmentation
Representation Image
Enhancement
Object Recognition
Key Stages in Digital Image Processing:
Image Compression
Image Acquisition
Image Restoration
Morphological Processing
Segmentation
Representation
& Description Image
Enhancement
Object Recognition
Problem Domain
Colour Image Processing
Image Compression
Key Stages in Digital Image Processing:
Colour Image Processing
Image Acquisition
Image Restoration
Morphological Processing
Segmentation
Representation Image
Enhancement
Object Recognition
WLE-306(DIP) 15
Components of an Image Processing System
Light & the Electromagnetic Spectrum
WLE-306(DIP) 17
• Chromatic (color) light spans the em energy spectrum from approx.
0.43 to 0.79 µm. In addition to frequency, three basic quantities are used to describe the quality of a chromatic light source: radiance, luminance, & brightness
• Radiance- the total amount of energy radiated by the light source and usually measured in watts (W)
• Luminance- it is the measure of energy an observer perceives from a light source and is measured in lumens (lm)
• Brightness- it is the subjective descriptor of light perception that is practically impossible to measure
Light & the Electromagnetic Spectrum
• Radiance (watt):
• Total amount of energy flow from the light source.
• Luminance (lumens, lm):
• measure of amount of energy an observer perceives from a light source. It varies based on distance from the source, wavelength, etc.
• Brightness:
• a subjective descriptor, describing color sensation.
Light & the Electromagnetic Spectrum
• Primary colors of pigment (subtractive):
WLE-306(DIP) 19
Image Sensing & Acquisition
Image Acquisition using Single Sensor
WLE-306(DIP) 21
Image Acquisition using Sensor Strip
Image Acquisition using Sensor Arrays
Simple Image Formation Model
WLE-306(DIP) 23
Image Sampling & Quantization
WLE-306(DIP) 25
Image Sampling & Quantization
Representing Digital Images
Digital Image Representation
• An image is a function
defined on a 2D coordinate f(x,y)
• The value of f(x,y) is the intensity
• 3 such functions can be defined for a color image, each represents one color component
• A digital image can be represented as a matrix
• Sometimes, the range of values spanned by the gray scale is referred to informally as the dynamic range- the ratio of the maximum
measurable intensity to the minimum detectable intensity level in the system
WLE-306(DIP) 29
An Image Exhibiting Saturation & Noise
Number of Storage Bits for various values of N & k
Spatial and Gray Level Resolution
• Spatial resolution is rather intuitive, and is determined by the quality and
“density” of the sampling
• Sampling theories (e.g., Nyquist-Shannon) state that sampling should be performed at a rate that is at least twice the size of the smallest object/highest frequency
• Based on this, over-sampling and under-sampling (=spatial aliasing) can occur
• Gray level resolution is a term used to describe the binning of the signal rather than the actual difference we managed to obtain when we quantized the signal. 8-bit and 16-bit images are the most common ones, but 10- and 12-bit images can also be found
Spatial and Gray Level Resolution
• Spatial resolution:
• Number of samples per unit length or area
• DPI: dots per inch
specifies the size of an individual pixel
• If pixel size is kept
constant, the size of an image will affect spatial resolution
• Gray level resolution:
• Number of bits per pixel
• Usually 8 bits
• Color image has 3 image planes to yield 8 x 3 = 24 bits/pixel
• Too few levels may cause false contour
WLE-306(DIP) 33
Spatial Resolution
Same Pixel Size, different Sizes
WLE-306(DIP) 35
Same Size, Different Pixel Sizes
Effects of Varying the Gray Level Resolution in a Digital Image
WLE-306(DIP) 37
Effects of varying the number of Intensity levels in a digital Image
Images with varying Degree of Details
WLE-306(DIP) 39
Isopreference Curves
Fig (2.23) Typical Isopreference curves for 3 types of Images in Fig. (2.22)
Image Interpolation
• Image interpolation refers to the “guess” of intensity values at missing locations, i.e., x and y can be
arbitrary
• Note that it is just a guess (Note that all sensors have finite sampling distance) (1) Nearest Neighbor
Interpolation
(2) Bilinear Interpolation (3) Bicubic Interpolation
WLE-306(DIP) 41
• Why do we need image interpolation?
• We want BIG images
• When we see a video clip on a PC, we like to see it in the full screen mode
• We want GOOD images
• If some block of an image gets damaged during the transmission, we want to repair it
• We want COOL images
• Manipulate images digitally can render fancy artistic effects as we often see in movies
Image Interpolation
Bilinear Interpolation Bicubic Interpolation
Graphical Interpretation of Interpolation at Half-pel
column row
f(m,n) g(m,n)
43
Scenario I: Resolution Enhancement
Low-Res.
High-Res.
Scenario II: Image Inpainting
45
Scenario III: Image Warping
Error Concealment
47
damaged interpolated
Error Concealment
Basic Relationship between Pixels
Neighbors of a Pixel:
• 4-neighbors
• Diagonal neighbors
• 8-neighbors
Adjacency, Connectivity, Regions, & Boundaries:
• 4-adjacency
• 8-adjacency
• m-adjacency
Neighbors of a Pixel
• A pixel p at coordinates (x,y) has four horizontal and vertical neighbors whose coordinates are given by:
(x,y-1), (x, y+1), (x-1, y), (x+1,y)
• This set of pixels, called the 4-neighbors of p, is denoted by N4(p). Each pixel is one unit distance from (x, y) and some of the neighbors of p lie outside the digital image if (x, y) is on the border of the image.
(x-1, y)
(x, y-1) P (x, y) (x, y+1)
(x+1, y)
Neighbors of a Pixel
• The four diagonal neighbors of p have coordinates:
(x-1, y-1), (x+1, y-1), (x-1, y+1), (x+1, y+1), denoted by ND (p).
• These points, together with the 4-neighbors, are called the 8-neighbors of p, denoted by N8 (p).
(x-1, y-1) (x-1, y+1)
P (x, y)
(x+1, y-1) (x+1, y+1)
(x-1, y-1) (x-1, y) (x-1, y+1)
(x, y-1) P (x, y) (x, y+1)
Adjacency and Connectivity
• Let V: a set of intensity values used to define adjacency and connectivity.
• 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 V typically contains more elements, for example, V = {180, 181, 182, …, 200}
• If the possible intensity values 0 – 255, V set can be any subset of these 256 values.
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 Types of Adjacency
Types of Adjacency
• m-adjacency:
Two pixels p and q with values from V are m- adjacent if :
• q is in N4(p) or
• q is in ND(p) and the set N4(p) ∩ N4(q) has no pixel whose values are from V (no intersection)
• Important Note: the type of adjacency used must
be specified
Types of Adjacency
• Mixed adjacency is a modification of 8-
adjacency. It is introduced to eliminate the
ambiguities that often arise when 8-adjacency is used.
• For example:
Types of Adjacency
• In this example, we can note that to connect between two pixels (finding a path between two pixels):
• In 8-adjacency way, you can find multiple paths between two pixels
• While, in m-adjacency, you can find only one path between two pixels
• So, m-adjacency has eliminated the multiple path
connection that has been generated by the 8-adjacency.
• Two subsets S1 and S2 are adjacent, if some pixel in S1 is adjacent to some pixel in S2. Adjacent means, either 4-, 8-
A Digital Path
• A digital path (or curve) from pixel p with coordinate (x,y) to pixel q with coordinate (s,t) is a sequence of
distinct pixels with coordinates (x
0,y
0), (x
1,y
1), …, (x
n, y
n) where (x
0,y
0) = (x,y) and (x
n, y
n) = (s,t) and pixels (x
i, y
i) and (x
i-1, y
i-1) are adjacent for 1 ≤ i ≤ n
• n is the length of the path
• If (x
0,y
0) = (x
n, y
n), the path is closed.
• We can specify 4-, 8- or m-paths depending on the type
of adjacency specified.
A Digital Path
• Return to the previous example:
In figure (b) the paths between the top right and
bottom right pixels are 8-paths. And the path
Connectivity
• 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 p in S is called a connected component of S
• If the set S has only one connected component, then set S is called a connected set
Region:
• 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 & Rj are said to be adjacent regions if their union makes a connected set
• The regions which are not adjacent are said to be disjoint regions
• To make sense, the types of adjacency must be specified
• When referring to regions, we consider 4- & 8-adjacency
Region and Boundary (-contd.)
• If an image has K-disjoint regions and none of them touches the image border. Let Ru denotes the union of all the K-disjoint regions and (Ru)c denotes its complement
• Then we call the pixels in Ru the foreground and all pixels in (Ru)c the background of the image
Boundary:
• The boundary (also called border or contour) of a region R is the set of pixels in the region that have one or more neighbors that are not in R
• 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 in the image
• This extra definition is required because an image has no neighbors beyond its borders
• Normally, when we refer to a region, we are referring to subset of an
WLE-306(DIP) 59
Region and Boundary
Distance Measures
• For pixels p, q and z, with coordinates (x,y), (s,t) and (v,w), respectively, D is a distance function if:
(a) D (p,q) ≥ 0 (D (p,q) = 0 iff p = q), (b) D (p,q) = D (q, p), and
(c) D (p,z) ≤ D (p,q) + D (q,z).
Distance Measures
• The Euclidean Distance between p and q is defined as:
D
e(p,q) = [(x – s)
2+ (y - t)
2]
1/2•
Pixels having a distance less than or equal to some value r from (x, y) are the pointscontained in a disk of radius r centered at (x, y)
p (x, y)
q (s, t)
Distance Measures
• The D
4distance (also called city-block distance) between p and q is defined as:
D
4(p,q) = | x – s | + | y – t | Pixels having a D
4distance from (x,y), less than or equal to some value r form a Diamond
centered at (x,y)
p
q (s,t)
D4
Distance Measures
Example:
The pixels with distance D
4≤ 2 from (x,y) form the following contours of constant distance.
The pixels with D
4= 1 are
the 4-neighbors of (x,y)
Distance Measures
• The D
8distance (also called chessboard distance) between p and q is defined as:
D
8(p,q) = max(| x – s |,| y – t |) Pixels having a D
8distance from (x,y), less than or equal to some value r form a square
Centered at (x,y)
p
q (s,t)
D8(b) D
Distance Measures
Example:
D
8distance ≤ 2 from (x,y) form the following contours
of constant distance.
Distance Measures
• Dm distance:
is defined as the shortest m-path between the points.
In this case, the distance between two pixels will
depend on the values of the pixels along the path, as
well as the values of their neighbors.
Distance Measures
• Example:
Consider the following arrangement of pixels and
assume that p, p
2, and p
4have value 1 and that p
1and p
3can have can have a value of 0 or 1
Suppose that we consider the adjacency of pixels
values 1 (i.e. V = {1})
Distance Measures
• Cont. Example:
Now, to compute the D
mbetween points p and p
4Here we have 4 cases:
Case1: If p
1=0 and p
3= 0
The length of the shortest m-path
(the D
mdistance) is 2 (p, p
2, p
4)
Distance Measures
• Cont. Example:
Case2: If p
1=1 and p
3= 0
now, p
1and p will no longer be adjacent (see m- adjacency definition)
then, the length of the shortest
path will be 3 (p, p
1, p
2, p
4)
Distance Measures
• Cont. Example:
Case3: If p
1=0 and p
3= 1
The same applies here, and the shortest –m-path will
be 3 (p, p
2, p
3, p
4)
Distance Measures
• Cont. Example:
Case4: If p
1=1 and p
3= 1
The length of the shortest m-path will be 4 (p, p
1, p
2,
p
3, p
4)
Mathematical Tools Used in
Digital Image Processing
Array Versus Matrix Operations
Linear versus Nonlinear Operations
Linear versus Nonlinear Operations
Arithmetic Operations
Image Addition
(Averaging)
Image Subtraction
Another common use of image multiplication is in masking, also called region of interest (ROI), operations. The process, illustrated in Fig. 2.30, consists simply of multiplying a given image by a
mask image that has 1s in the ROI and 0s elsewhere. There can be more than one ROI in the mask image, and the shape of the ROI can be arbitrary, although rectangular shapes are used
frequently for ease of implementation.
• When working with 8-bit images, setting K=255 gives us a scaled image whose intensities span the full 8-bit scale from 0 to 255
• When performing division, we have the extra requirement that a small number should be added to the pixels of the divisor image to avoid division by 0
• For a given image f, an approach that guarantees the full range of an arithmetic operation between captured images into a fixed number of bits is as follows:
• First, we perform the operation , which creates an image whose minimum value is 0
• Then, we perform the operation , which creates a scaled image, fs, whose values are in the range [0, K]
SET & LOGICAL OPERATIONS
Basic Set Operations
EXAMPLE 2.8: Set operations involving image intensities
Let the elements of a gray scale image be represented by a set A whose elements are triplets of the form (x, y, z), where x and y are spatial coordinates and z denotes intensity. We can define the complement of A as the set Ac = {(x, y, K-z) | (x, y, z) ϵ A} which simply denotes the set of pixels of A whose intensities have been subtracted from a constant K. This constant is equal to 2k -1 where k is the number of intensity bits used to represent z. Let A denote the 8-bit gray scale image in Fig.
2.32(a), and suppose that we want to form the negative of A using set operations. Figure 2.32(b) shows the result. The union of two gray-scale sets Aand Bmay be defined as the set
A U B = {max (a, b) | a ϵ A, b ϵ B}
z
Logical Operations
Spatial Opera Spatial Operations ns (1)
• Spatial operations are performed directly on the pixels of a given image
• We classify spatial operations into three broad categories:
• (1) single-pixel operations, (2) neighborhood operations, and (3) geometric spatial transformations
Spatial Opera Spatial Operations ns (1)
Spatial Operations (3)
Affine Transform
• For assigning intensity levels, we consider nearest neighbour, bilinear, and bicubic interpolation
techniques when
EXAMPLE 2.9: Image rotation and intensity interpolation
• forward mapping
• inverse mapping
• Image registration is an important application of digital image processing used to align two or more images of the same
scene
• In image registration, we have available the input and output images, but the specific transformation that produced the
output image from the input generally is unknown
• the input image is the image that we wish to transform, and what we call the reference image is the image against which we want to
register the input
EXAMPLE 2.10: Image Registration
• The distortion may be caused by the images were taken at different times using the same instrument, such as satellite images of a given location taken several days, months, or even years apart
WLE-306(DIP) 91
EXAMPLE 2.10: Image Registration
Vector and Matrix Operations
Image Transforms
for x=0,1,2, ... , M-1 and y=0,1,2, ..., N-1, where s(x,y,u,v) is called the inverse transformation kernel.
for u=0,1,2, ... , M-1 and v=0,1,2, ..., N-1, where r(x,y,u,v) is called the forward transformation kernel.
• The forward transformation kernel is said to be separable if r(x, y, u, v) = r1(x, u) r2(y, v)
Image Transforms
• In Addition, the kernel r1(x, y) is said to be symmetric if is functionally equal to r2(x, y) so that
r(x, y, u, v) = r1(x, u) r1(y, v)
• T=AFA
• BTB = BAFAB
• If B=A-1, then F=BTB
where F is an M x M matrix containing the elements of f(x,y),
A is an MxM matrix with elements aij = r1(i, j), and T is the resulting MxM transform, with values T(u,v) for u,v =0,1,2, …, M-1
T=AFA
When the forward and inverse kernels of a transform pair satisfy the
conditions of separability and symmetry, and f(x,y) is a square image of size MxM, then transform and inverse transform can be expressed in matrix form:
BTB = BAFAB If B=A-1,
then F=BTB
To obtain inverse transform, we pre- and post-multiply the above eqn. by an inverse transformation matrix B
EXAMPLE 2.11: Image processing in the transform domain
Probabilistic Methods
EXAMPLE 2.12: Comparison of standard deviation values as measures of image intensity contrast.
Figure 2.41 shows three 8-bit images exhibiting low, medium, and high contrast, respectively. The standard deviations of the pixel intensities in the three images are 14.3, 31.6, and 49.2 intensity levels, respectively. The corresponding variance values are 204.3, 997.8, and 2424.9, respectively. Both sets of values tell the same story but, given that the range of possible intensity values in these images is [0, 255], the standard deviation values relate to this range much more intuitively than the variance.
Neighbors of a Pixel
A Pixel p at coordinates ( x, y) has 4 horizontal and vertical neighbors.
Their coordinates are given by:
(x+1, y) (x-1, y) (x, y+1) & (x, y-1)
f(2,1) f(0,1) f(1,2) f(1,0)
This set of pixels is called the 4-neighbors of p denoted by N4(p).
Each pixel is unit distance from ( x ,y).
f(0,0) f(0,1) f(0,2) f(0,3) f(0,4) - - - - - f(1,0) f(1,1) f(1,2) f(1,3) f(1,4) - - - - - f(x,y) = f(2,0) f(2,1) f(2,2) f(2,3) f(2,4) - - - - - f(3,0) f(3,1) f(3,2) f(3,3) f(3,4) - - - - - I I I I I - - - - - I I I I I - - - - -
Neighbors of a Pixel
A Pixel p at coordinates ( x, y) has 4 diagonal neighbors.
Their coordinates are given by:
(x+1, y+1) (x+1, y-1) (x-1, y+1) & (x-1, y-1)
f(2,2) f(2,0) f(0,2) f(0,0)
This set of pixels is called the diagonal-neighbors of p denoted by ND(p).
f(0,0) f(0,1) f(0,2) f(0,3) f(0,4) - - - - - f(1,0) f(1,1) f(1,2) f(1,3) f(1,4) - - - - - f(x,y) = f(2,0) f(2,1) f(2,2) f(2,3) f(2,4) - - - - - f(3,0) f(3,1) f(3,2) f(3,3) f(3,4) - - - - - I I I I I - - - - - I I I I I - - - - -
Adjacency, Connectivity
Adjacency
:
Two pixels are adjacent if they are neighbors and their intensity level ‘V’ satisfy some specific criteria of similarity.e.g. V = {1}
V = { 0, 2}
Binary image = { 0, 1}
Gray scale image = { 0, 1, 2, ---, 255}
In binary images, 2 pixels are adjacent if they are neighbors & have some intensity values either 0 or 1.
In gray scale, image contains more gray level values in range 0 to 255.
Adjacency, Connectivity
4-adjacency:Two pixels p and q with the values from set ‘V’ are 4- adjacent if q is in the set of N4(p).
e.g. V = { 0, 1}
1 1 0 1 1 0 1 0 1
p in RED color
Adjacency, Connectivity
8-adjacency:Two pixels p and q with the values from set ‘V’ are 8- adjacent if q is in the set of N8(p).
e.g. V = { 1, 2}
0 1 1 0 2 0 0 0 1
p in RED color
q can be any value in GREEN color
Adjacency, Connectivity
m-adjacency:Two pixels p and q with the values from set ‘V’ are m-adjacent if
(i) q is in N4(p) OR
(ii) q is in ND(p) & the set N4(p)
n
N4(q) have no pixels whose values are from ‘V’.e.g. V = { 1 }
0
a1
b1
c0
d1
e0
fAdjacency, Connectivity
m-adjacency:Two pixels p and q with the values from set ‘V’ are m-adjacent if
(i) q is in N4(p) e.g. V = { 1 }
(i) b & c
0
a1
b1
c0
d1
e0
f0
g0
h1
IAdjacency, Connectivity
m-adjacency:Two pixels p and q with the values from set ‘V’ are m-adjacent if
(i) q is in N4(p) e.g. V = { 1 }
(i) b & c
0
a1
b1
c0
d1
e0
f0
g0
h1
IAdjacency, Connectivity
m-adjacency:Two pixels p and q with the values from set ‘V’ are m-adjacent if
(i) q is in N4(p)
e.g. V = { 1 } (ii) b & e
0
a1
b1
c0
d1
e0
f0
g0
h1
IAdjacency, Connectivity
m-adjacency:Two pixels p and q with the values from set ‘V’ are m-adjacent if
(i) q is in N4(p)
e.g. V = { 1 } (ii) b & e
0
a1
b1
c0
d1
e0
f0
g0
h1
IAdjacency, Connectivity
m-adjacency:Two pixels p and q with the values from set ‘V’ are m-adjacent if
(i) q is in N4(p) OR e.g. V = { 1 }
(iii) e & i
0
a1
b1
c0
d1
e0
f0
g0
h1
iAdjacency, Connectivity
m-adjacency:Two pixels p and q with the values from set ‘V’ are m-adjacent if
(i) q is in ND(p) & the set N4(p)
n
N4(q) have no pixels whose values are from ‘V’.e.g. V = { 1 } (iii) e & i
0
a1
b1
c0
d1
e0
f0
g0
h1
IAdjacency, Connectivity
m-adjacency:Two pixels p and q with the values from set ‘V’ are m-adjacent if
(i) q is in ND(p) & the set N4(p)
n
N4(q) have no pixels whose values are from ‘V’.e.g. V = { 1 } (iii) e & i
0
a1
b1
c0
d1
e0
f0
g0
h1
ISoln: e & i are m-adjacent.
Adjacency, Connectivity
m-adjacency:Two pixels p and q with the values from set ‘V’ are m-adjacent if
(i) q is in N4(p) OR
(ii) q is in ND(p) & the set N4(p)
n
N4(q) have no pixels whose values are from ‘V’.e.g. V = { 1 }
(iv) e & c
0
a1
b1
c0
d1
e0
fAdjacency, Connectivity
m-adjacency:Two pixels p and q with the values from set ‘V’ are m-adjacent if
(i) q is in N4(p) OR
(ii) q is in ND(p) & the set N4(p)
n
N4(q) have no pixels whose values are from ‘V’.e.g. V = { 1 }
(iv) e & c
0
a1
b1
c0
d1
e0
f0
g0
h1
ISoln: e & c are NOT m-adjacent.
Adjacency, Connectivity
Connectivity: 2 pixels are said to be connected if their exists a path between them.
Let ‘S’ represent subset of pixels in an image.
Two pixels p & q are said to be connected in ‘S’ if their exists a path between them consisting entirely of pixels in ‘S’.
Path/Curve
Path:A (digital) path/curve from pixel p with coordinate ( x, y) with pixel q with coordinate ( s, t) is a sequence of distinct sequence with coordinates (x0, y0), (x1, y1), ….., (xn, yn) where
(x, y) = (x0, y0)
& (s, t) = (xn, yn)
Closed path: (x0, y0) = (xn, yn)
Path
Example # 1: 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}.
4 2 3 2 q
3 3 1 3
2 3 2 2
p 2 1 2 3
Path
Example # 1: Shortest-4 path:
V = {1, 2}.
4 2 3 2 q 3 3 1 3 2 3 2 2
p 2 1 2 3
Path
Example # 1: Shortest-4 path:
V = {1, 2}.
4 2 3 2 q 3 3 1 3 2 3 2 2
p 2 1 2 3
Path
Example # 1: Shortest-4 path:
V = {1, 2}.
4 2 3 2 q 3 3 1 3 2 3 2 2
p 2 1 2 3
Path
Example # 1: Shortest-4 path:
V = {1, 2}.
4 2 3 2 q 3 3 1 3 2 3 2 2
p 2 1 2 3
Path
Example # 1: Shortest-4 path:
V = {1, 2}.
4 2 3 2 q 3 3 1 3 2 3 2 2
p 2 1 2 3
Path
Example # 1: Shortest-4 path:
V = {1, 2}.
4 2 3 2 q 3 3 1 3 2 3 2 2
p 2 1 2 3
So, Path does not exist.
Path
Example # 1: Shortest-8 path:
V = {1, 2}.
4 2 3 2 q
3 3 1 3
2 3 2 2
p 2 1 2 3
Path
Example # 1: Shortest-8 path:
V = {1, 2}.
4 2 3 2 q 3 3 1 3 2 3 2 2
p 2 1 2 3
Path
Example # 1: Shortest-8 path:
V = {1, 2}.
4 2 3 2 q 3 3 1 3 2 3 2 2
p 2 1 2 3
Path
Example # 1: Shortest-8 path:
V = {1, 2}.
4 2 3 2 q 3 3 1 3 2 3 2 2
p 2 1 2 3
Path
Example # 1: Shortest-8 path:
V = {1, 2}.
4 2 3 2 q 3 3 1 3 2 3 2 2
p 2 1 2 3
Path
Example # 1: Shortest-8 path:
V = {1, 2}.
4 2 3 2 q 3 3 1 3 2 3 2 2
p 2 1 2 3
So, shortest-8 path = 4
Path
Example # 1: Shortest-m path:
V = {1, 2}.
4 2 3 2 q
3 3 1 3
2 3 2 2
p 2 1 2 3
Path
Example # 1: Shortest-m path:
V = {1, 2}.
4 2 3 2 q 3 3 1 3 2 3 2 2
p 2 1 2 3
Path
Example # 1: Shortest-m path:
V = {1, 2}.
4 2 3 2 q 3 3 1 3 2 3 2 2
p 2 1 2 3
Path
Example # 1: Shortest-m path:
V = {1, 2}.
4 2 3 2 q 3 3 1 3 2 3 2 2
p 2 1 2 3
Path
Example # 1: Shortest-m path:
V = {1, 2}.
4 2 3 2 q 3 3 1 3 2 3 2 2
p 2 1 2 3
Path
Example # 1: Shortest-m path:
V = {1, 2}.
4 2 3 2 q 3 3 1 3 2 3 2 2
p 2 1 2 3
Path
Example # 1: Shortest-m path:
V = {1, 2}.
4 2 3 2 q 3 3 1 3 2 3 2 2
p 2 1 2 3
So, shortest-m path = 5
Region & Boundary
Region: Let R be a subset of pixels in an image. Two regions Ri and Rj are said to be adjacent if their union form a connected set.
Regions that are not adjacent are said to be disjoint.
We consider 4- and 8- adjacency when referring to regions.
Below regions are adjacent only if 8-adjacency is used.
1 1 1
1 0 1 Ri 0 1 0
Regions & Boundaries
Boundaries (border or contour): The boundary of a region R is the set of points that are adjacent to points in the compliment of R.
0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0
REDcolored 1 is NOT a member of border if 4-connectivity is used between region and background. It is if 8-connectivity is used.
Distance Measures
Distance Measures: Distance between pixels p, q & z with co- ordinates ( x, y), ( s, t) & ( v, w) resp. is given by:
a) D( p, q) ≥ 0 [ D( p, q) = 0 if p = q] …………..called reflexivity b) D( p, q) = D( q, p) .………….called symmetry c) D( p, z) ≤ D( p, q) + D( q, z) ..………….called transmitivity
Euclidean distance between p & q is defined as- De( p, q) = [( x- s)2 + (y - t)2]1/2
Distance Measures
City Block Distance: The D4 distance between p & q is defined as D4( p, q) = |x - s| + |y - t|
In this case, pixels having D4 distance from ( x, y) less than or equal to some value r form a diamond centered at ( x, y).
2
2 1 2
2 1 0 1 2
2 1 2 2
Pixels with D4 distance ≤ 2 forms the following contour of constant distance.
Distance Measures
Chess-Board Distance: The D8 distance between p & q is defined as
D8( p, q) = max( |x - s| , |y - t| )
In this case, pixels having D8 distance from ( x, y) less than or equal to some value r form a square centered at ( x, y).