Detection of Discontinuities, Edge linking and Boundary

Detection of Discontinuities, Edge linking and Boundary Detection: 

Detection of Discontinuities, Edge linking and Boundary Detection Presented by Ch.Venkanna, M.Tech(EI), EC104018.

Image Segmentation: 

Image Segmentation Segmentation: - sub divides an image into its constituent regions or objects Based on two properties of gray-level image values Discontinuity based approach point / line / edge detection Similarity based approach thresholding region growing / splitting / merging

Detection of Discontinuities: 

Detection of Discontinuities Three basic types of gray level discontinuities are - points - lines - edges Detection is through a mask

PowerPoint Presentation: 

The response of the mask at any point is given by

Point Detection: 

Point Detection Detection of isolated point A point has been detected at location on which mask is centered if

Point Detection: 

Point Detection

Point Detection: 

Point Detection

Line Detection: 

Line Detection For digital images the only three point straight lines are only horizontal, vertical, or diagonal (+ or –45  ).

Line Detection: 

Line Detection

Edge Detection: 

Edge Detection It is a set of connected pixels that lie on the boundary between regions Slope of the ramp is inversely proportional to degree of blurring in the edge

Edge Detection: 

Edge Detection

Gradient Operators : 

Gradient Operators First-order derivatives: The gradient of an image f ( x , y ) at location ( x , y ) is defined as the vector: The magnitude of this vector: The direction of this vector:

Gradient operators: 

Gradient operators

Gradient operators: 

Gradient operators Prewitt masks for detecting diagonal edges Sobel masks for detecting diagonal edges

Gradient operators-Example: 

Gradient operators-Example

Gradient operators-Example: 

Gradient operators-Example

Laplacian operator: 

Laplacian operator Second-order derivatives: (The Laplacian) The Laplacian of an 2D function f ( x , y ) is defined as Two forms in practice:

Edge Linking: 

Edge Linking Whatever may be the operator used for edge detection (1 st or 2 nd derivative operators ) should ideally give all the edge points. Problem : But, because of noise or non-uniform illumination of scene, when Sobel operator is applied to image ,the edge points are not always connected or continuous. Therefore, we need to link the edge points to get the meaningful edges. The edge detection algorithms typically are followed by linking procedures.

Edge Linking approaches: 

Edge Linking approaches We need to link all the edge points which are similar in some sense to get a meaningful edge description. Edge linking can be done by two approaches Local processing Global processing 19

Local Processing: 

Local Processing Analyze the characteristics of the edge points in a small neighborhood. All points that are similar according to a set of criteria are linked. Its magnitude Its direction and α denote gradient magnitude and direction. E and A are predefined threshold values

Global Processing: 

Global Processing Hough transforms: (Hough Transform)H.T is a method for detecting straight lines, shapes and curves in images. Classical Hough transform Detect simple shape Line detection Circle detection Hough transform is a mapping from spatial domain to the parameter space.

Hough Transform Technique: 

Hough Transform Technique Given an edge point, there is an infinite number of lines passing through it (variable ‘a’ and ‘b’). This point can be represented as a line in parameter space. Parameter Space intercept slope a b x y b = (-x) a + y P(x,y) Spatial domain

Hough Transformation (Line): 

Hough Transformation (Line) y i =ax i + b b = - ax i + y i ab-plane or parameter space xy-plane all points (x i ,y i ) contained on the same line must have lines in parameter space that intersect at (a ’ ,b ’ )

Hough Transform for Lines: 

Hough Transform for Lines

PowerPoint Presentation: 

25 Step 1: Subdivide ab -plane to accumulator cells. The cell at coordinates (i , j) with accumulator value A(i ,j) corresponds to square associated with parameter space coordinates (a i , b j ) where a min ≤ a i ≤ a max , b min ≤ b j ≤ b max and A(i, j)=0 (Initialization) Step 2: For every ( x k , y k ), find b=-x k a p +y k for each allowed p. Step 3: Round off b to the nearest allowed value b q . I f a choice of a p results in solution b q then we let A(p,q) = A(p,q)+1 Step 4: At the end of the procedure, value Q in A(i,j) corresponds to Q points in the xy-plane lying on the line y = a i x+b j The Procedures of Hough Transform b = - ax i + y i

Performance and Limitation: 

Performance and Limitation Performance With n image points and K accumulator cells, there are nK computation involved. Limitation The slope approaches infinity as the line approaches to vertical. Solution : Avoided using the normal representation of a line x i cos  + y i sin  = 

Hough Transform for Lines: 

Hough Transform for Lines -3 -2 -1 1 2 3 -2 -1 1 2

Rewriting a line as x cos + y sin =  : 

Rewriting a line as x cos  + y sin  =  This implementation is identical to the method using slope-intercept representation. Instead of straight lines, the loci are sinusoidal curves in  -plane . -90 90  -plane x cos  + y sin  = 

Edge-linking method based on the Hough transform (outline): 

Edge-linking method based on the Hough transform (outline) Steps: Compute the gradient of an image and threshold it to obtain a binary image; Specify subdivisions in the  -plane; Examine the counts of the accumulator cells for high pixel concentration; Examine the relationship (principally for continuity) between pixels in chosen cell.

Edge linking - Hough transform (Example) : 

Edge linking - Hough transform (Example)

Thank you: 

Thank you 31