Non-max suppression

Question

We've learned that you can get the gradient direction with atan(dy/dx) which is the direction orthogonal to the edge. Now we had a homework where we were supposed to discretize this direction into four classes (x- and y-direction and both diagonals) and then check both pixel neighbors in the best matching direction for non-max suppression.

I didn't fully get the solution though. Obviously we had four cases:

1. abs(angle) < pi/8, so the gradient (roughly) points in x-direction, thus we check img(i, j-1) and img(i, j+1) (assuming the image origin is in the top left)

2. angle > pi/8 && angle <= 3*pi/8, so the gradient points to the top right. Now I thought we need to check img(i-1, j+1) and img(i+1, j-1) but instead we check img(i-1, j-1) and img(i+1, j+1) which seems like the orthogonal diagonal.

The other two cases are equivalent. I tried to change this but then the edges really look weird so this seems correct but I don't understand why.

Can someone explain this to me?

Waldron

Non-max suppression is a way to eliminate points that do not lie in important edges. In your first case if the gradient is close to zero degrees at a given point, that means the edge is to the north or to the south, and that point will be considered to be on the edge if the magnitude of this point is greater than both magnitudes of the points to its left and right (as in your example). In your second case you are checking for gradient at 45 degrees, so the edge is at 135 degrees, so you keep the point if it is greater that the points along the gradient direction, i.e. (-1, -1) and (1, 1). – Nightshirt

Yeah see, it's along the gradient direction aka. 45° aka. to the top right. I'm not sure which coordinate system you were using. (-1, -1) and (1, 1) seems like a classical cartesian system with its oritin in the bottom left. We did this in matlab though so the image origin is in the top left and therefore it seem like we check in edge direction aka. 135° aka. to the top left. – Waldron

That is clearly the same coordinate system I used since I said the gradient is at 45 degrees and (-1, -1), (1, 1) are along this gradient. This turns out to be the same in the cartesian plane, it is not relevant to where the origin is in this case. My previous answer maintains, what is the complication you are having with it ? Is it related to (-1, -1) being supposedly above your origin ? – Nightshirt

Does this drawing i.imgur.com/9lpvf.png help ? – Nightshirt

I think it was just confusion between matlab and cartesian coordinates. As I said, matlab uses the system which is on the right side in your drawing but for some reason I aligned the angles in the left system... – Waldron

Answer 1

Non-max suppression is a way to eliminate points that do not lie in important edges. In your first case if the gradient is close to zero degrees at a given point, that means the edge is to the north or to the south, and that point will be considered to be on the edge if the magnitude of this point is greater than both magnitudes of the points to its left and right (as in your example). In your second case you are checking for gradient at 45 degrees, so the edge is at 135 degrees, and so you keep the point if it is greater than the points along the gradient direction, i.e. (-1, -1) and (1, 1). Rotating the coordinate system doesn't affect this.

Nightshirt

I have little confusion in your explanation. As per the drawing above, you have shown the figure for case 2(gradient angle = 45 degree). But say for gradient = 22.5 degree, as per your drawing, we have to check the points (-1, 0) and (1, 0) which is top and bottom. Am I correct?? – Awry

Answer 2

Here's a python implementation of Non Maxima Suppression used in Canny Edge Detection process.

They concentrate on North and South, North-East and South-West, East and West, and South-East and North-West. Then decide which values to keep.

Hope it helps someone who needs NMS for finding better edge.

Bolden

Answer 3

Might be late for the original question, but the following link might help anyone struggling to understand non-max suppression.

Java Demo of non-max suppression

Wheal

"This University of Southampton personal web page service is currently unavailable. We apologise for any inconvenience caused" – Cigarillo

Same "unavailable" here – Almanza

@MonicaHeddneck Reminds me of "Wisdom of Ancients" on xkcd – Badderlocks