Gradient and edge.

Tram Ho

This week, I will introduce the algorithm to find the edge in image processing.

What is an edge?

In a digital photo, the pixels of the image intensity that vary sharply from surrounding points are often called edge points. An edge is a set of edges that make up a meaningful shape relative to the shape and structure information of an object in an image, for example, the outline of a face, a hat structure, … Edge separation is the process of extracting edge information by image processing operations.

For example, if we have a picture and we take a horizontal line and then we will take the body level along that line, we will see the gray level change in the values.

Gradient

When it comes to change, we often mention Gradient . The function gradient indicates how well the function increases.

  • Example with a 1-way function: f ( x ) = x 2 f (x) = x ^ {2} f ( x ) = x 2 , its gradient is denoted and calculated as follows: G r a d ( x ) = f ( x ) ( x ) = 2 x Grad (x) = frac { partial f (x)} { partial (x)} = 2x G r a d ( x ) = ( x ) f (x) = 2 x
    • Grad (2) = 4 indicates the increasing direction of the function is right
    • Grad (-1) = – 2 indicates the increasing direction of the function on the left.

The gradient is not only calculated by the first derivative, we can also calculate by the first derivative. With the above brightness variation, we can calculate the first and second derivatives and the corresponding formula as follows:

Edge detection using derivatives

We have 2 ways to detect edges using derivatives:

  • Discover local minimum or maximum value in derivative 1
  • Zero-crosssing detection (which is where the value from negative to positive or vice versa you can see the note in the image above) in the second derivative.

The derivative in 2-dimensional space is calculated as follows:

However, to apply to digital images, approximation of the derivative of the discrete function is necessary. The approximation to the first derivative of the gradient function is calculated as follows (1):

The magnitude of the gradient indicates the intensity of the edge at the point ( x , y ) (x, y) ( x , y ) :

In the digital image, we have the steps to calculate the gradient as follows:

  • Calculate gradients by column
  • Love Gradient in rows
  • Calculate the final gradient by summing the two above gradients.

If we calculate the gradient by the usual method of browsing by rows and columns and then calculating it is very time-consuming, is there a faster way? And we have a way to use the kernel-based math we learned in the previous lesson to calculate.

Various kernels used to compute the gradient

Here, I will introduce you to the most widely used kernel in image processing. First we have an overview of the kernel introduced as follows:

Pixel Difference masks

This kernel clearly shows the first derivative formula with x and y above (1) with -1 behind the number 1 because here we perform the Convolution operation so it reverses.

An example of an image using the above kernel is as follows:

The results are not very good, so we will find out how to understand other kernels for better results.

Robert mask

Roberts masks calculate the gradient diagonally between the two points. The kernel derivates in x and y as follows:

The result with the same original image in the example pixel difference masks with Robert mask is as follows:

We see the results will be darker diagonally, not horizontal or vertical as in the previous kernel, Kernel size 2 x 2 is often difficult to install because the calculation of the main is not clear. Therefore, a window size of 3 x 3 is often used.

Prewitt mask

The prewitt mask is defined as follows:

We have an example using Prewitt mask.

Sobel mask

Another variation of the Prewitt mask that uses an increase of the center point weight to 2 is the Sobel mask. Value 2 is used to smooth the image and also to evaluate the center point more important than other points.

And here is the result when using Sobel mask with the input image:

Laplace gradient

The above kernels calculate the gradient based on the first derivative, with the second derivative gradient in both directions, also known as Laplace in the continuous domain as follows:

In a continuous domain, the above formula is approximated to:

We have a Laplace mask or represents the above H function which means:

Results of using Laplace mask when using Laplace mask:

We find the result is much nicer at the first place, but it’s still not good, because taking the values ​​in the grass base creates discrete dots because the task of detaching edges is to get the valuable seamless edges. treatment.

We have an overview when applying 5 different kernels to separate edges as follows:

More advanced edge detection

Laplacian of a Gaussian (LoG) edge detection

Unlike previous algorithms that calculate gradients using linear operations, this algorithm calculates the gaussian function. The steps for implementing the algorithm are as follows:

  1. Apply LoG to photos:
  2. Detect also zero-crossing in the image.
  3. Filtering the threshold on zero-crossing leaves only the strong points (the big difference between the positive and negative poles)

Examples of steps taken by LoG edge are as follows:

Canny edge detection

The Canny edge splitting method uses a multi-step algorithm to find edges in an image. It was developed by John F. Canny in 1986. The operation of this method can be summarized as follows:

  1. Noise reduction : Images received from receivers often have a lot of noise, so that noise that does not affect the edge separation process should be minimized. Blur the image, reduce noise using a 5×5 Gaussian filter. Size 5×5 usually works well for Canny algorithm. Of course you can also change the size of the blur filter accordingly.
  2. Calculate gradients and gradient directions : Calculate gradients for each pixel using the Sobel edge filter introduced above. Then determine the size of the edge defined as the magnitude of the gradient and the direction of the edge is the direction of the gradient.
  3. Non-maximum Suppression (NMS): eliminates pixels in non-maximum global locations. The edge points are defined as local maxima in the edge magnitude image. The algorithm to determine the edge at each position (x, y) is implemented as follows:
    • Rounded edge direction A n g l e ( θ ) Angle ( theta) A n g l e ( θ ) to the angle is a multiple of 4 5 45 ^ { circ} 4 5 ∘ the nearest corresponds to 8 nearby points.

    • Compare the edge strength of the current point (x, y) with the neighboring point in the direction of the edge and the opposite direction. For example if available A n g l e ( θ ) = 18 0 Angle ( theta) = -180 ^ { circ} A n g l e ( θ ) = 1 8 0 then the 2 neighboring points behind and in front of the current point are compared. If the edge of the point (x, y) is the largest, then that point is the edge, otherwise the edge is not.

  4. Filter the edges: The edges selected in step 3 are mostly real edges, but there are still edges selected that are wrong due to noise or color variation on the surface of an object. The simplest way to differentiate them is to use a threshold that only edges greater than this threshold are retained. Canny’s edge splitting algorithm uses a double threshold including a high and a low threshold. Any points whose edge strength is greater than the high threshold are marked as strong edges. Any points having the magnitude five between the two thresholds are marked as weak edges.
  5. Finally: Points marked as strong edges are selected immediately as edge points. Weak edges are chosen as edge points if and only if they are next to a strong edge. Here strong edges are considered real edges, weak edges can be real or noise edges. And they can only be real edges if adjacent to a point is real edges.

In opencv, we want to use the Canny algorithm just by using the following simple statement:

With cameraman.png image you can download it:

And the result will look like this:

You have a better understanding of the parameters of the Canny () function in the cv2.Canny document

References

  1. Image processing – Le Thanh Ha Chapter 6
  2. RC Gonzalez, RE Woods, “Digital Image Processing,” 4th edition, Pearson, 2018.
  3. Slide
  4. Code github: here
  5. http://deeplearning.net/software/theano/tutorial/conv_arithmetic.html
  6. Feature extraction (Edge, Line, Texture)
  7. https://minhng.info/tutorials/xu-ly-anh-opencv-hien-thuc-canny-edge.html
  8. https://towardsdatascience.com/canny-edge-detection-step-by-step-in-python-computer-vision-b49c3a2d8123
Share the news now

Source : Viblo