Basic Relationships Between Pixels

• Neighborhood

• Adjacency

• Connectivity

• Paths

• Regions and boundaries

1
 Relationships Between Pixels

 The structure of a digital image allows to state some basic relationships between pixels that can be useful
in some practical cases.
 Some operations consider groups of pixels that share the same features or are related by some peculiar
characteristics. Example: estimation of the area covered by the river

 identify the pixels which have the color of the river;

 select among these the connected pixels;
 consider the regions that are “naturally” aligned;
 sections
2
of the rivers parted by bridges, necks, or covered.
As mentioned before, an image is denoted by f(x, y). When referring in this section to a particular pixel, such as p and q.
3 f(0,0) f(0,1) f(0,2) f(0,3) f(0,4) - - - - - Y
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) - - - - -
X
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: 4-neighbors
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 -----
 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).
 Neighbors of a Pixel

diagonal-neighbors

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 -----

 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).

4
 Neighbors of a Pixel
8-neighbors
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 -----

 A Pixel p at coordinates ( x, y) has 8-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)
(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 8-neighbors of p denoted by N8(p).

5
 Adjacency

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.

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
q can be any value in GREEN color.
6
 Adjacency

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

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) AND the set N4(p) ∩ N4(q) have no pixels whose values are from ‘V’.

e.g. V = { 1 }
0a 1b 1c
0d 1e 0f
0g 0h 1i
7
 Adjacency

m-adjacency: Two pixels p and q with the values from set ‘V’ are
m-adjacent if
(i) q is in N4(p) First
pixel P

e.g. V = { 1 }
(i) b & c
0a 1b 1c
0d 1e 0f
0g 0h 1I

so: b & c are m-adjacent.

8
 Adjacency

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
0a 1b 1c set N4(p)∩
0d 1e 0f N4(q)=
0g 0h 1I {0} not in V
So: b & e are m-adjacent.
(iii) e & i
0a 1b 1c
0d 1e 0f
0g 0h 1I
So: e & i are m-adjacent.
(iv) e & c
0a 1b 1c
0d 1e 0f
0g 0h 1I
So: e & c are NOT 9m-adjacent.
 Path

 A (digital) path (or curve) from pixel p with coordinates (x0, y0) to pixel q with coordinates (xn, yn) is a
sequence of distinct pixels with coordinates (x0, y0), (x1, y1), …, (xn, yn) , Where (xi, yi) and (xi-1, yi-1)
are adjacent for 1 ≤ i ≤ n.
 Here n is the length of the path.
 If (x0, y0) = (xn, yn), the path is closed path.
 We can define 4-, 8-, and m-paths based on the type of adjacency used.

Example : 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 2q
3 3 1 3
2 3 2 2
p 2 1 2 3

10
Paths

Shortest-8 path: 4 2 3 2q
3 3 1 3
2 3 2 2
p2 1 2 3
So, shortest-8 path = 4
Shortest-m path:
4 2 3 2 q
3 3 1 3
2 3 2 2
p 2 1 2 3
So, shortest-m
11 path = 5
 Connectivity
Connectivity: two 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’.
12
 Connected component and region

Let S represent a subset of pixels in an image

• For every pixel p in S, the set of pixels in S that are connected to p is called a connected
component of S.
• If S has only one connected component, then S is called Connected Set.
• 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 to be adjacent are said to be disjoint.

13
 Regions and boundaries
14

• Boundary (or border)

 The boundary of the 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 of the image.
• Foreground and background
 An image contains K disjoint regions, Rk, k = 1, 2, …, K. Let Ru denote the union of all the K regions, and let
(Ru)c denote its complement.
All the points in Ru is called foreground; EX: 0 0 0 0 0
All the points in (Ru)c is called background. 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
RED colored 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

Given pixels p, q and z with coordinates (x, y), (s, t), (u, v) respectively, the distance
function D has following properties:
• D(p, q) ≥ 0 [D(p, q) = 0, iff p = q]
• D(p, q) = D(q, p)
• D(p, z) ≤ D(p, q) + D(q, z)

The following are the different Distance measures:

• Euclidean Distance :
De(p, q) = [(x-s)2 + (y-t)2]1/2
• City Block Distance:
D4(p, q) = |x-s| + |y-t|
• Chess Board Distance:
D8(p, q) = max(|x-s|, |y-t|)

15