EDGE DETECTION [PDF]

A First Course in Machine Vision

EDGE DETECTION By: Ehsan Khoramshahi

Edge Detection, basics  Edge Detection Process:  Definition: a process which attempts to

capture the significant properties of objects in the image.  Which Properties?  Discontinuity in  photometrical,  Geometrical  physical characteristics of objects.  This variation result to variation in the gray level

image.

Edge Detection, basics  Types of Variations:    

Step Edges (discontinuities) Ramps Local extrema (line edges) Junctions (2D features formed where at least two edges meet)

 The purpose of edge detectors  Localize these features  Also Identify the physical phenomena which

produce them

The source of Edge  Inside an Object (Texture, Different Parts)  Between the objects

Example of Discontinuities inside an object

Example of Discontinuities between objects

Why Edge Is Important  Many Processes rely on Edges !!  Like????  Object Recognition(Example License Plate

Detection System)  Some Stereo Matching Systems.  Face Recognition systems.  Many Feature Extraction Techniques

Desired properties  All the subsequent processing rely on edge

detector.  Edge detector should be efficient and reliable 

Ill posed operators: operators which small error in the data or in subsequent calculation result in much larger error in answer.

 Despite the fact that gradient

operators are ill posed they used in most of the edge detector routines.

Variety of edge detectors  general purpose edge detection algorithm is

difficult. Why?  It is difficult to design it in a way that perform well

in many contexts and capture the requirements of subsequent processing stage.

 So variety of edge detectors have been

invented , they are different in :  purpose  mathematical/algorithmic properties

We’ll talk about  Characteristic of edges  Property of a detector  Methodology of edge detection  Method for Corner detections

Types of edges  Step  Ideal  Noisy  Smoothed  Line  Roof  Ramp  Pulse  Staircase

Properties of edge detector  An edge detector accepts digital image as

input and generate the edge map as output.  The edge map of some detectors includes explicit information the position and strength of edges, their orientation, and the scale. Notice! Here we have only position information!

How many classes of Edge detectors Exist?

 From the point of view of integration of an

edge detector into a computer vision system there are two classes of edge detectors 1. Detectors which do not use a prior knowledge about the scene 2. Detectors which use a prior knowledge about the scene 

They are not accurate for general purpose applications but more useful for specific vision systems

Steps of an Edge detection process  Smoothing  Reducing noise  Regularizing the numerical differentiation

 Differentiation  Evaluation of desired derivation of the image

 Labeling  Localizing edge  Increasing the signal to noise ratio by

suppression(removing) false edges.

Image Differentiation  Recall: purpose of edge detection was to

localize variation in gray level and identify the physical phenomena which produced them.  Differentiation operation consist of partial

derivatives.

 Differentiation operation is characterized by:  the order of its partial derivatives  The invariance to rotation  Its linearity

1-Smoothing  Recall: Image differentiation is ill-pose

problem, so the noise reduction is a mandatory step.  a positive effect : reduce noise to ensure robust edge detection  Negative effect: Information loss  There should be trade off between loss of information and noise reduction.

2-differentiation  The most commonly used operators are:  Gradient  First order derivative defined as vector

 It is non-linear and invariant to rotation  In a noisy image, the use of several directional derivates may be useful for increasing the signal-to-noise ratio

 Laplacian  Second order  Second-order directional derivatives

3-Labeling  Recall: Involves localizing edges and increasing signal-to-noise ratio by suppression false edges.  Localization procedure depends on the differentiation operator uses  Early Edge detectors: Edges were localized by thresholding the gradient modulus.  The edges weren’t filiform (thread form) so a

skeletization operation was required.  An Improvement has achieved by the use of the nonmaximum suppression algorithm

Gradient Based Edge Detectors  First order Derivative/Gradient Method  Roberts Operator  Sobel Operator  Prewitt Operator

 Second Order Derivative  Laplacian  Laplacian of Gaussian  Difference Of Gaussian

Roberts Operator  Convolve Image with Following Filters  Gradient then defined as:

Sobel Operator  Convolve Image with Following Filters

 Gradient then defined as:

Prewitt Operator  Convolve Image with Following Filters

 Gradient then defined as:

Laplacian aplacian of Gaussian(LOG)  Smoothing with a Gaussian Filter has good effect on

an ill-posed problem as expressed before.  This pre-processing step reduces the high frequency noise components prior to the differentiation step.  Since both the Gaussian and the Laplacian kernels are usually much smaller than the image, this method usually requires far fewer arithmetic operations.  The LoG (`Laplacian of Gaussian') kernel can be precalculated in advance so only one convolution needs to be performed at run-time on the image

LOG

Sample of thick edges

Canny Edge Detector  Solve the problem of thickness  Edges are very thin!!!  More informative  Actually could be considered as an additional

step over any gradient based edge detector.  It is ill pose again because of using gradient

Canny Algorithm Steps 1. Preprocessing: Convolve the original Image

with a 5x5 Gaussian mask. 2. Calculate the edge strength  We can use Sobel edge detector in Horizontal and

vertical directions

3. Calculate the edge Directions  Only four main directions are important and will

be considered.

4. Perform non-maximum suppression

non-maximum suppression algorithm  In this context a point is local maximum if its

gradient modulus(length) is greater than its neighbors in edge direction. N1

N2

N3

N4

Central Pixel

N5

N6

N7

N8

Compare Canny with Others

Corner Detection  The goal is to detect the corners.  It is very useful specially for feature extraction and tracking.  Harris: One of the best corner detector  Invariant to :  Rotation  Scale  Illumination variation  Image noise  accuracy is acceptable for many applications  Performance is good

Intuition About Harris Operator

Some Object

Intuition About Harris Operator Edges

Some Object

Intuition About Harris Operator Corners

Intuition About Harris Operator Magnify

Intuition About Harris Operator Horizontal Edge after convolution with Gaussian Mask

Intuition About Harris Operator Horizontal Edge after convolution with Gaussian Mask

Intuition About Harris Operator Horizontal Edge after convolution with Gaussian Mask Vertical Edge after convolution with Gaussian

Intuition About Harris Operator Horizontal Edge after convolution with Gaussian Mask Vertical Edge after convolution with Gaussian

Result of Multiplication

Intuition About Harris Operator Horizontal Edge after convolution with Gaussian Mask Vertical Edge after convolution with Gaussian

Order-Statistics Filter

Intuition About Harris Operator Horizontal Edge after convolution with Gaussian Mask Vertical Edge after convolution with Gaussian

Order-Statistics Filter

Harris Corner Detector Example

Harris Corner Detector Example 2

Harris Parameters  Gaussian Smoothing parameters  Size of Order Statistic mask  Threshold of acceptable edges

Thanks!!!  Your Questions