connectivity and path

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 (x0, y0), (x1, y1), ….., (xn, yn) where :
(x, y) = (x0, y0) & (s, t) = (xn, yn)

Example 1

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

A 4 neighbor is computer as up,down.left,right so :

1. 2 -> 1
2. 1 -> 2
3. 2 -> 2
4. 2 -> 1
5. 1 -> none (because there is no element 1,2 in 4 neighbors of pixel 1) SO IT IS CLOSED PATH. Represented as :

Example 2 (Shortest-8 path V = {1, 2})


PATH for above image is
1. 2 -> 1
2. 1 -> 2
3. 2 -> 2
4. 2 -> 1
5. 1 -> 2 OK!! (because diagonal neighbors may be up left, up right, bottom left, bottom right)

Closed Path

A Closed path found when (x0, y0) = (xn, yn)

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.