8.A] Define Image Topology. Briefly explain the topological properties:
i) Connectivity
ii) Relations
iii) Distance Measures.
Image topology is a branch of image processing that deals with the fundamental properties of the image such as image neighbourhood, paths among pixels, boundary, and connected components.
It characterizes the image with topological properties such as neighbourhood, adjacency and connectivity.
Pixel Connectivity
Definition: Pixel connectivity refers to the relationship between two or more pixels in an image, which helps in defining the boundaries of objects within the image. Two pixels, p and q, are considered connected if they satisfy certain brightness conditions specified by a set V and are spatially adjacent. For binary images, V is typically {0, 1}, while for grayscale images, V can be any range of gray levels.
Types of Connectivity:
- 4-Connectivity: Pixels p and q are 4-connected if they share the same value as specified by the set V and if q is in the set N₄(p), meaning that q is one of the four directly adjacent neighbors of p (up, down, left, or right). This implies that any path from p to q involves pixels that are 4-connected to each other.
- 8-Connectivity: Pixels p and q are 8-connected if they share the same value as specified by the set V and if q is in the set N₈(p), meaning that q is one of the eight possible neighbors of p (including diagonals). This type of connectivity allows for diagonal connections between pixels.
- Mixed Connectivity (m-Connectivity): Mixed connectivity, also known as m-connectivity, combines aspects of 4-connectivity and 8-connectivity. Pixels p and q are m-connected if:
- q is in N₄(p) (4-connected).
- q is in N_D(p) (diagonal neighbors) and the intersection of N₄(p) and N₄(q) is empty, ensuring that there are no multiple paths or loops between p and q. This reduces ambiguity in connectivity, particularly in complex images.
8- Connectivity is shown as lines. Here, a multiple path or loop is present. In m-connectivity, there are no such multiple paths.
It can be observed that the multiple paths have been removed.
Relations
A binary relation between two pixels, denoted as aRb, defines a relationship between a pair of elements within an image.
For example, consider an image pattern where the set of elements is A = {x₁, x₂, x₃}. If we use the 4-connectivity relation to define connections between these elements, the resulting set might be A = {x₁, x₂}. This indicates that x₃ is not included because it is not 4-connected to any other element in the image.
The properties of binary relations include:
- Reflexive: A relation is reflexive if, for any element a in the set A, the relation aRa holds.
- Symmetric: A relation is symmetric if aRb implies that bRa also holds.
- Transitive: A relation is transitive if aRb and bRc imply that aRc also holds.
If all three of these properties are satisfied, the relation is called an equivalence relation.
Distance Measures
The distance between two pixels p and q in an image can be measured using various distance measures, including:
- Euclidean Distance: The straight-line distance between the coordinates of pixels.
- D4 Distance (City Block Distance): Calculated as the sum of the absolute differences between the coordinates of the pixels.
- D8 Distance (Chessboard Distance): The maximum of the absolute differences between the coordinates.
Consider three pixels p, q, and z with coordinates P(x,y), Q(s,t), and Z(u,w). The distances between these pixels can be calculated using these measures.
The distance function can be called metric if the following properties are satisfied:
- D(p,q) is well-defined and finite for all p and q.
- D(p,q) >= 0 if p=q, then D(p,q)=0
- The distance D(p,q)=D(q,p)
- D(p,q)+D(q,z) >= D(p,z). This is called the property of triangular inequality.
The Euclidean distance between the pixels p and q, with coordinates (x,y) and (s,t) respectively can be defined as
The advantage of the Euclidean distance is its simplicity. However, since its calculation involves a square root operation, it is computationally costly.
The D4 distance or city block distance can be simply calculated as D4(p,q)=|x-s|+ |y-t|
The D8 distance or chessboard distance can be calculated as D8(p,q)=max(|x-s|,|y-t|)