Edge Linking and Boundary Detection FOSIP

Edge Linking and Boundary Detection

Edge linking and boundary detection are fundamental techniques in digital image processing and computer vision for identifying the boundaries or edges of objects within an image. These methods are used to segment an image into distinct regions corresponding to different objects or parts of objects.

Edge Detection

The first step is to apply an edge detection operator to the image to identify pixels where there are sharp intensity changes or discontinuities. Common edge detection algorithms include:

Gradient-based: Compute the gradient of image intensity and find maxima, such as the Sobel, Prewitt or Canny operators.
Laplacian-based: Find zero-crossings in the second derivative, such as the Marr–Hildreth operator.

The output is typically a binary image with pixels marked as edge (1) or non-edge (0). However, edges are usually thick and disconnected after applying these operators.

Gradient-Based Edge Detection

The gradient $\nabla f$ of an image $f (x, y)$ at location $(x, y)$ is given by:

\nabla f = [\begin{matrix} G_{x} \\ G_{y} \end{matrix}] = [\begin{matrix} \frac{\partial f}{\partial x} \\ \frac{\partial f}{\partial y} \end{matrix}]

Where $G_{x}$ and $G_{y}$ are the partial derivatives in the x and y directions respectively. These can be approximated by convolving with derivative filters such as:

Sobel Operators:

G_{x} = [\begin{matrix} + 1 & 0 & - 1 \\ + 2 & 0 & - 2 \\ + 1 & 0 & - 1 \end{matrix}] * A and G_{y} = [\begin{matrix} + 1 & + 2 & + 1 \\ 0 & 0 & 0 \\ - 1 & - 2 & - 1 \end{matrix}] * A

The gradient magnitude $| G | = \sqrt{G_{x}^{2} + G_{y}^{2}}$ is used to identify edge pixels as those exceeding a threshold.

Laplacian of Gaussian (LoG)

$LoG (x, y) = - \frac{1}{π σ^{4}} (1 + \frac{x^{2} + y^{2}}{2 σ^{2}}) e^{- (x^{2} + y^{2}) / 2 σ^{2}}$

The LoG computationally approximates the second derivative, finding zero-crossings which indicate edges.

Example Canny Edge Detection

import cv2
import numpy as np 
from matplotlib import pyplot as plt

img = cv2.imread('sample.jpg',0)
edges = cv2.Canny(img,100,200)

plt.subplot(121),plt.imshow(img,cmap='gray')
plt.title('Original Image'), plt.xticks([]), plt.yticks([])
plt.subplot(122),plt.imshow(edges,cmap='gray')
plt.title('Edge Image'), plt.xticks([]), plt.yticks([])
plt.show()

Edge Linking

Once we have a binary edge image, the next step is to link the edges together into coherent edge chains or curves corresponding to the boundaries of objects. Common algorithms include:

Hough Transform: Maps edge points to parameters of lines/curves, clustering peaks identify boundaries.
Graph Search: Treat edge points as nodes, link neighbors with 8-connectivity, find minimum cost boundaries.

The output is a list of linked edge point coordinates representing the object boundaries.

Hough Transform

The Hough transform maps edge points $(x_{i}, y_{i})$ to parameters $(r, θ)$ of lines:

r = x_{i} \cos θ + y_{i} \sin θ

Curves in the $(x, y)$ image map to points in the $(r, θ)$ parameter space. Boundaries correspond to peaks in the accumulator array $H (r, θ)$ counting co-linear points.

Edge Thinning

The extracted boundaries are often thick after linking due to the initial edge operator response. So a final thinning step is applied to obtain thin, one pixel-wide boundary curves. Popular thinning algorithms include:

Morphological thinning: Successively erode away outer boundary pixels without breaking connectivity.
Tracking Methods: Follow the boundary, keeping only selected pixels on the medial axis.

Morphological Thinning

Thinning iteratively removes outer boundary pixels $p$ if certain conditions are met, based on consecutive neighbors in a square neighborhood $N (p)$ .

Common algorithms evaluate a hit-or-miss transform kernel to identify removable pixels while preserving connectivity.

Example

import cv2
import numpy as np

img = cv2.imread('sample.jpg',0)  
kernel = cv2.getStructuringElement(cv2.MORPH_CROSS,(3,3))
edges = cv2.Canny(img,100,200)
dilated = cv2.dilate(edges,kernel,iterations=1)
eroded = cv2.erode(dilated,kernel,iterations=1) 
result = cv2.bitwise_and(dilated,eroded)

cv2.imshow('Thinned Edges',result)
cv2.waitKey(0)
cv2.destroyAllWindows()

Applications

Boundary detection has many applications in image analysis, including:

Object recognition and classification
Shape analysis and measurement
Motion tracking and segmentation
Medical image analysis (organ/tumor boundaries)
Machine inspection (defect detection)

While conceptually simple, reliable boundary detection remains a challenging problem, especially for objects with complex, irregular shapes or in the presence of noise, occlusions, and other artifacts.

This article "Edge Linking and Boundary Detection FOSIP" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Edge Linking and Boundary Detection FOSIP. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

Edge Linking and Boundary Detection FOSIP

Contents