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 gradient detection as a post processing step. The outlines thinning is using pre-calculated parameters such as gradient magnitude and gradient orientation retrieved at edge extraction step.

Determine Gradients parameters

To extract thin stable edges, you first need to calculate gradient magnitude and orientation. Frequently to resolve edge parameters we apply square masks with size 3×3. The Sobel tutorial describes the exact process of using masks as gradient detector. A good contour operator provides accurate information about the orientation and size of the gradient. The result of this process will lead to thick edges with different magnitude as on the following image.

Sobel filter
Result of Sobel operator

After execution of gradient thinning operator the resulting image will look like the one bellow.

Non-maximum suppression filter
Result of Non-maximum suppression operator

Edge thinning – Non maximum suppression

Once the edge detection step is completed, it’s time to process the gradients and extract the thin edges. Ideally, the contours should be one pixel wide. To achieve this we use the famous Non-maximum suppression algorithm. The steps below can describe it:

  • Iterate through each image pixel
  • For each edge pixel choose its two neighbors based on gradient direction and use them for comparison
  • For each edge pixel choose its two neighbors based on gradient direction and use them for comparison
Non maximum suppression edge neighbors
Edge neighbors based on gradient direction

If the gradient 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 edge magnitude

Non-maximum suppression (NMS) source code

The Sobel article describes in detail how to calculate gradient magnitude and orientation. Then using the gradient parameters it comes turn to NMS fragment shader execution. Using degrees operator the shader convert angle parameter stored into u_image from radians to degrees as theta. Each orientation is used to find the proper neighbors ca and cb. Finally compare each two neighbors with the central gradient magnitude cc and suppress if needed.

WebGL Fragment Shader


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

Visit FivekoGFX on GitHub for more image processing examples


Non maximum suppression Demo

 
Sigma: 3


Related Articles