Basic Relationships between Pixels- Digital Image Processing

of the image.
Neighbours of a pixel

A pixel p at (x,y) has 4-horizontal/vertical neighbours at (x+1,y), (x-1,y), (x,y+1) and (x,y-1). These are called the 4-neighbours of p : N4(p).

A pixel p at (x,y) has 4 diagonal neighbours at (x+1,y+1), (x+1,y-1), (x-1,y+1) and (x-1,y-1). These are called the diagonal-neighbours of p : ND(p).

The 4-neighbours and the diagonal neighbours of p are called 8-neighbours of p : N8(p).
Adjacency between pixels

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.

For example, 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.

We consider three types of adjacency:

a) 4-adjacency: Two pixels p and q with values from V are 4-adjacent if q is in the set N4(p).

b) 8-adjacency: Two pixels p and q with values from V are 8-adjacent if q is in the set N8(p).

c) m-adjacency(mixed adjacency): Two pixels p and q with values from V are m-adjacent if

q is in N4(p), or
2) q is in ND(p) and the set N4(p)∩N4(q) has no pixels whose values are from V.

Connectivity between pixels

It is an important concept in digital image processing.

It is used for establishing boundaries of objects and components of regions in an image.

Two pixels are said to be connected:

if they are adjacent in some sense(neighbour pixels,4/8/m-adjacency)
if their gray levels satisfy a specified criterion of similarity(equal intensity level)

There are three types of connectivity on the basis of adjacency. They are:

a) 4-connectivity: Two or more pixels are said to be 4-connected if they are 4-adjacent with each others.

b) 8-connectivity: Two or more pixels are said to be 8-connected if they are 8-adjacent with each others.

c) m-connectivity: Two or more pixels are said to be m-connected if they are m-adjacent with each others.

1. Basic Relationships between Pixels Presented by - Md . Shohel Rana Lecturer dept. of CSE ISTT DIGITAL IMAGE PROCESSING

2. Neighbors of a Pixel Y X Y X

3. Neighbors of a Pixel f(x,y) = f(0,4) - - - - - f(1,4) - - - - - f(2,4) - - - - - f(3,4) - - - - - f(0 , 0) f(1,0) f(2 , 0) f(3 , 0) I I f(0 , 1) f(1, 1) f(2 , 1) f(3 , 1) I I f(0 , 2) f(1,2) f(2 , 2) f(3 , 2) I I f(0,3) f(1,3) f(2 , 3) f(3 , 3) I I I - - - - - I - - - - - Y X

4. Neighbors of a Pixel (x+1, y) (x-1, y) (x, y+1) & (x, y-1) f(2,1) f(0,1) f(1,2) f(1,0) A Pixel p at coordinates ( x, y) has 4 horizontal and vertical neighbors. Their coordinates are given by: This set of pixels is called the 4-neighbors of p denoted by N 4 (p). Each pixel is unit distance from ( x ,y). f(x,y) = f(0,4) - - - - - f(1,4) - - - - - f(2,4) - - - - - f(3,4) - - - - - f(0,0) f(1,0) f( 2 ,0) f(3 , 0) I I f(0,1) f(1, 1) f( 2 ,1) f(3 , 1) I I f(0, 2 ) f(1,2) f( 2 , 2 ) f(3 , 2) I I f(0,3) f(1, 3) f( 2 ,3) f(3 , 3) I I I - - - - - I - - - - -

5. Neighbors of a Pixel (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) A Pixel p at coordinates ( x, y) has 4 diagonal neighbors. Their coordinates are given by: This set of pixels is called the diagonal-neighbors of p denoted by N D (p). diagonal neighbors + 4-neighbors = 8-neighbors of p. They are denoted by N 8 (p). So, N 8 (p) = N 4 (p) + N D (p) f(x,y) = f(0,4) - - - - - f(1,4) - - - - - f(2,4) - - - - - f(3,4) - - - - - f(0,0) f(1,0) f( 2 ,0) f(3 , 0) I I f(0,1) f(1, 1) f( 2 ,1) f(3 , 1) I I f(0, 2 ) f(1,2) f( 2 , 2 ) f(3 , 2) I I f(0,3) f(1, 3) f( 2 ,3) f(3 , 3) I I I - - - - - I - - - - -

6. 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 is the intensity set 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.

7. Adjacency 4-adjacency: Two pixels p and q with the values from set ‘V’ are 4- adjacent if q is in the set of N 4 (p). e.g. V = { 0, 1} 1 1 1 1 1 1 p in RED color q can be any value in GREEN color.

8. Adjacency 8-adjacency: Two pixels p and q with the values from set ‘V’ are 8- adjacent if q is in the set of N 8 (p). e.g. V = { 1, 2} 1 1 2 1 p in RED color q can be any value in GREEN color

9. Adjacency m-adjacency: Two pixels p and q with the values from set ‘V’ are m-adjacent if (i) q is in N 4 (p) OR (ii) q is in N D (p) & the set N 4 (p ) ⋂ N 4 (q ) have no pixels whose values are from ‘V’. e.g. V = { 1 } a 1 b 1 c d 1 e f g h 1 i

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

11. Adjacency e.g. V = { 1 } (i) b & c a 1 b 1 c d g 1 e h f I Soln: b & c are m-adjacent.

12. 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’. For any pixel p in S, the set of pixels that are connected to it in S is called a connected component of S .

13. P a th s Paths: A path from pixel p with coordinate ( x, y) with pixel q with coordinate ( s, t) is a sequence of distinct sequence with coordinates (x , y ), (x 1 , y 1 ), ….., (x n , y n ) where (x, y) = (x , y ) & (s, t) = (x n , y n ) Closed path: (x , y ) = (x n , y n )

14. P a th s 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

15. P a th s 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

16. P a th s 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

17. P a th s 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

18. P a th s 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

19. P a th s 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

20. P a th s 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.

21. P a th s 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

22. P a th s 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

23. P a th s 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

24. P a th s 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

25. P a th s 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

26. P a th s 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

27. P a th s 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

28. P a th s 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

29. P a th s 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

30. P a th s 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

31. P a th s 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

32. P a th s 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

33. P a th s 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

34. Regions & Boundaries 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 1 R i 1 1 1 1 1 R j 1 1 1

35. Connectivity 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. S: a subset of pixels in an image. For any pixel p in S, the set of pixels that are connected to it in S is called a connected component of S. Ch3: Some basic Relationships between pixels Hanan Hardan 36

36. Regions and boundaries 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. 000000 010010 011010 010110 000000 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 .

37. 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. 1 1 1 1 1 1 1 1 1 1 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.

38. 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] D( p, q) = D( q, p) D( p, z) ≤ D( p, q) + D( q, z) …………..called reflexivity .………….called symmetry ..………….called transmitivity Euclidean distance between p & q is defined as- D e ( p, q) = [( x- s) 2 + (y - t) 2 ] 1/2

39. Distance measures If we have 3 pixels: p,q,z respectively p with ( x , y ) q with ( s , t ) z with ( v , w ) Then: A. D ( p , q ) ≥ 0 , D ( p , q ) = 0 iff p = q B. D ( p , q ) = D ( q , p ) C. D ( p , z ) ≤ D ( p , q ) + D ( q , z ) Ch3: Some basic Relationships between pixels Hanan Hardan 40

40. Euclidean distance between p and q : De ( p , q ) = [( x - s ) 2 + ( y - t ) 2 ] 1/2 D 4 distance (also called city-block distance ): D4 ( p , q ) = | x - s| + | y - t| D 8 distance (also called c hessboard distance ) : D8 ( p , q ) = max (| x - s| , | y - t| )

41. Distance Measures City Block Distance : The D 4 distance between p & q is defined as D 4 ( p, q) = |x - s| + |y - t| In this case, pixels having D 4 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 1 2 2 1 2 2 Pixels with D 4 distance ≤ 2 forms the following contour of constant distance.

42. Distance Measures Chess-Board Distance : The D 8 distance between p & q is defined as D 8 ( p, q) = max( |x - s| , |y - t| ) In this case, pixels having D 8 distance from ( x, y) less than or equal to some value r form a square centered at ( x, y). 2 2 2 2 2 2 1 1 1 2 2 1 1 2 2 1 1 1 2 2 2 2 2 2 Pixels with D 8 distance ≤ 2 forms the following contour of constant distance.