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.
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.
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.
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.
Step 3:
As a next step, we compare the strength of the current pixel with the other two.
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);
}
Resources
- Canny edge detector – Non-maximum suppression – Wikipedia
