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

The process of extraction thin stable edges is preceded by gradient magnitude and orientation calculation. Frequently edge parameters are resolved using square masks with size 3×3. The image is processed using these masks in a way that gradients strength and orientation are retrieved as described into Sobel tutorial. The result of this process will lead to thick edges with different magnitude as on the following image.

Sobel filterSobel operator result

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

Non-maximum suppression filterResult of Non-maximum suppression operator

Edge thinning – Non maximum suppression

 

After the edge detection step is done it is time to process gradients and retrieve thin edges ideally one pixel width. One of the most widely used technique is the so called Non-maximum suppression. It can be described by the following steps:

* Iterate through each pixel

* 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 gradient magnitude and orientation is calculated as described into the Sobel article. 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