## 9. Explain about the basic relationships and distance measures between pixels in a digital image.

>Table of contents

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

_{4}(p). Each pixel is a 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.

The four diagonal neighbors of p have coordinates (x+1, y+1), (x+1, y-1), (x-1, y+1), (x-1, y-1)

and are denoted by N

_{D}(p). These points, together with the 4-neighbors, are called the 8-

neighbors of p, denoted by N

_{8}(p). As before, some of the points in N

_{D}(p) and N

_{8}(p) fall outside

the image if (x, y) is on the border of the image.

**Connectivity:**

Connectivity between pixels is a fundamental concept that simplifies the definition of numerous

digital image concepts, such as regions and boundaries. To establish if two pixels are connected,

it must be determined if they are neighbors and if their gray levels satisfy a specified criterion of

similarity (say, if their gray levels are equal). For instance, in a binary image with values 0 and 1,

two pixels may be 4-neighbors, but they are said to be connected only if they have the same

value.

Let V be the set of gray-level values used to define adjacency. In a binary image, V={1} if we

are referring to adjacency of pixels with value 1. In a grayscale 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 gray-level 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 N

_{4}(p).

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

_{8}(p).

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

(i) q is in N

_{4}(p), or

(ii) q is in N

_{D}(p) and the set has no pixels whose values are from V.

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, consider the pixel arrangement shown in

Fig.9 (a) for V= {1}.The three pixels at the top of Fig.9 (b) show multiple (ambiguous) 8-

adjacency, as indicated by the dashed lines. This ambiguity is removed by using m-adjacency, as

shown in Fig. 9 (c).Two image subsets S

_{1}and S

_{2}are adjacent if some pixel in S

_{1}is adjacent to

some pixel in S

_{2}. It is understood here and in the following definitions that adjacent means 4-, 8-

, or m-adjacent. 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

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

In this case, n is the length of the path. If (x

_{0}, y

_{0}) = (x

_{n}, y

_{n}) , the path is a closed path. We can define 4-, 8-, or m-paths depending on the type of adjacency specified. For example, the paths shown in Fig. 9 (b) between the northeast and southeast points are 8-paths, and the path in Fig. 9 (c) is an m-path. Note the absence of ambiguity in the m-path. 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.

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 (which we

recall is a rectangular set of pixels), then its boundary is defined as the set of pixels in the first

and last rows and columns of the image. This extra definition is required because an image has

no neighbors beyond its border. Normally, when we refer to a region, we are referring to a subset

pixel; (c) m-adjacency

of an image, and any pixels in the boundary of the region that happen to coincide with the border

of the image are included implicitly as part of the region boundary.

**Distance Measures:**

For pixels p, q, and z, with coordinates (x, y), (s, t), and (v, w), respectively, D is a distance

function or metric if

The

**Euclidean distance**between p and q is defined as
For this distance measure, the pixels having a distance less than or equal to some value r from(x,

y) are the points contained in a disk of radius r centered at (x, y).
The

**D4 distance (also called city-block distance)**between p and q is defined as
In this case, the pixels having a D

diamond centered at (x, y). For example, the pixels with D4 distance . 2 from (x, y) (the center_{4}distance from (x, y) less than or equal to some value r form apoint) form the following contours of constant distance:

_{4}=1 are the 4-neighbors of (x, y).

The

**D8 distance (also called chessboard distance)**between p and q is defined as

In this case, the pixels with D8 distance from(x, y) less than or equal to some value r form a

square centered at (x, y). For example, the pixels with D8 distance ≤ 2 from(x, y) (the center

point) form the following contours of constant distance:

The pixels with D

_{8}=1 are the 8-neighbors of (x, y). Note that the D

_{4}and D

_{8}distances between p

and q are independent of any paths that might exist between the points because these distances

involve only the coordinates of the points. If we elect to consider m-adjacency, however, the Dm

distance between two points 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. For instance, consider the following arrangement of pixels and assume

that p, p

_{2}, and p

_{4}have value 1 and that p

_{1}and p

_{3}can have a value of 0 or 1:

Suppose that we consider adjacency of pixels valued 1 (i.e. = {1}). If p

_{1}and p

_{3}are 0, the length

of the shortest m-path (the Dm distance) between p and p

_{4}is 2. If p

_{1}is 1, then p

_{2}and p will no

longer be m-adjacent (see the definition of m-adjacency) and the length of the shortest m-path

becomes 3 (the path goes through the points pp

_{1}p

_{2}p

_{4}). Similar comments apply if p

_{3}is 1 (and p1

is 0); in this case, the length of the shortest m-path also is 3. Finally, if both p

_{1}and p

_{3}are 1 the

length of the shortest m-path between p and p

_{4}is 4. In this case, the path goes through the

sequence of points pp

_{1}p

_{2}p

_{3}p

_{4}.

>Table of contents

## 0 comments :

## Post a Comment