Gradient Non-Maximum Suppression

Gradient non-maximum suppression is an edge thinning algorithm that extracts thin contours of objects in an image. The output of this image processing algorithm is contour curves that are one pixel wide.

Non-maximal suppression is a post-processing step of gradient edge detection operators. This contour thinning algorithm is one of the main steps of the popular Canny edge detector.

Overview

Image edge detectors typically generate thick object boundaries, and this can make further objects recognition difficult. However, many of these algorithms provide useful gradient parameters such as: magnitude and orientation. Some of the most popular gradient detection algorithms are: Sobel edge detector, Prewitt operator or Schaar.

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 this contour thinning operator.

Edge Thinning by NMS

As already noted, the non-maxima suppression algorithm uses gradient magnitude and orientation to find the local peak of the edge line.

The following steps briefly describe how to extract one-pixel-wide edges:

Step 1:

Apply an edge detector such as: Prewitt or Sobel.

Step 2:

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

Step 3:

Compare the strength of the current pixel with the other two as in the image below.

|G(M2)|<|G(M)|>=|G(M1)|

If the pixel’s intensity is lower than one of its two neighbors, suppress it by making it zero (black/background). Otherwise, leave it unchanged and continue with the next one.

Source Code

Once we have the contours of the images through an edge detection filter, we can apply the non-maxima suppression algorithm.

The WebGL shader code below is a sample illustration of how to implement the non-maximal suppression algorithm with GLSL. The OpenGL shader language enables us to do this filtering quickly using GPU computations.

• 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.1415926536

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);
}

Online Example

With these online image tools, you can test how the non-maximum suppression algorithm performs on different gradient operators. You can test it against various edge detectors like: Sobel filter, Prewitt operator and Scharr.

Useful Resources

• Canny edge detector
• Edge Detection with JavaScript

Conclusion

This article reveals a classic image edge thinning algorithm that has many applications in image processing and object recognition. It gives sample source code of non-maximum suppression using GLSL code. The algorithm is applicable to various types of software applications such as extracting outlines from an image as an SVG file.