Gradient Non-Maximum Suppression

The gradient Non-maximum suppression also known as edge thinning is a process of extracting thin, one pixel wide object’s contours. This process follows edge detection as a post processing step.

Contour thinning uses pre-calculated gradient parameters: magnitude and orientation.


Demo

On our edge detection demo page you can test how the NMS algorithm works with different gradient operators like: Sobel filter, Prewitt and Scharr.


Overview

To extract thin stable edges, you first need to extract image contours. For this purpose, we often use some popular edge detection algorithm.

In our online demonstration, we use the classic Sobel edge detector to extract contours. This operator gives acceptable results, but we can use Prewitt or Scharr as an alternative.

In its classical form, the discovery of the edges of the image leads to thick boundaries of the objects. However, these algorithms provide useful information about the strength of the gradient and its orientation, that we use for further processing.

The result of Sobel filter without Non-maximum suppression involved
Result of Sobel operator

Often for objects recognition we have to extract the dominant thin contour lines. Here comes the gradient non-maximum suppression algorithm, that we will discuss further in this article.

The picture below shows what the result looks like after applying the contour thinning operator.

Result of edge detection operator after Non-maximum suppression filter
Result of Non-maximum suppression operator

How to get thin edges from images

As already noted, this NMS algorithm relies on the magnitude of the gradient and orientation that we receive from the edge detection operator we use.

Gradient magnitude equation
Gradient magnitude equation
Gradient orientation
Gradient orientation equation

To achieve the contours of an image with a width of one pixel, we apply the following steps:

Step 1:

As with many other analysis algorithms, we go through every pixel of the image.

Step 2:

For each pixel, we select two of its neighbors based on the direction of the gradient.

significant edge neighbors based on gradient direction
Significant edge neighbors based on gradient direction

Step 3:

As a next step, we compare the strength of the current pixel with the other two.

Edge magnitude condition

If the pixel magnitude is lower than one of the both neighbors suppress it by making it zero (black/background). Otherwise keep it unchanged and proceed with the next one.

Non-maximum suppression (NMS) source code

Once we have the contours of the images through an edge detection filter, we will apply the NMS algorithm.

In our online tool, we use the following WebGL shader to thin the outlines of objects. In short our example works as follows:

  • Use the angle parameter from the source image data (u_image) to extract the orientation theta. We apply the OpenGL degrees operator to convert from radians to degrees.
  • Use the orientation to select proper neighbors ca and cb
  • Finally, compare every two neighbors with the central value of the gradient cc and suppress if necessary

precision mediump float;

#define KERNEL_SIZE 3
// our texture
uniform sampler2D u_image;
uniform vec2 u_textureSize;
#define M_PI 3.1415926535897932384626433832795

void main() {
	vec2 onePixel = vec2(1.0, 1.0) / u_textureSize;
	vec2 textCoord = gl_FragCoord.xy / u_textureSize;
	vec4 cc = texture2D(u_image, textCoord);   
	float theta = degrees(cc.y*M_PI*2.0); 
	int ax = 0, ay = 0; 
	if ((theta >= 337.5) || (theta < 22.5)) { ax = 1; ay = 0; } 
	else if ((theta >= 22.5) && (theta < 67.5)) { ax = 1; ay = 1; } 
	else if ((theta >= 67.5) && (theta < 112.5)) { ax = 0; ay = 1; } 
	else if ((theta >= 112.5) && (theta < 157.5)) { ax =-1; ay = 1; } 
	else if ((theta >= 157.5) && (theta < 202.5)) { ax =-1; ay = 0; } 
	else if ((theta >=202.5) && (theta < 247.5)) { ax =-1; ay =-1; } 
	else if ((theta >=247.5) && (theta < 292.5)) { ax = 0; ay =-1; } 
	else if ((theta >= 292.5) && (theta < 337.5)) { ax = 1; ay =-1; }

	vec4 ca = texture2D(u_image, textCoord + onePixel*vec2(ax, ay));
	vec4 cb = texture2D(u_image, textCoord + onePixel*vec2(-ax, -ay));
	gl_FragColor = vec4((((cc.x <= ca.x) || (cc.x < cb.x)) ? vec3(0) : vec3(cc.x)), 1.0);
}

computer-vision-studio-thumb

Resources


Related articles