Add your own alternative version
Stats
259K views 23.3K downloads 97 bookmarked
Posted
13 Jul 2010

Comments and Discussions


Hey,
First of all, thank you very much for your nice explenation of canny edge algorithm and to share your implementation with the community on CodeProject!
However, a question arises, why do you call the travers method recursively in your code? Before you make you recursive call, you set the entry in your visitmap equal one. This means, once the method is called recursivly, you will immediately leaf the method. And in your current implementation, you will not visit your 8 connected neighbours. Or am I totaly wrong?
Best Regards and Happy Coding
dnn2018





First of all, I apologize for making such a strong statement, but after reading Wikipedia (https://en.wikipedia.org/wiki/Canny_edge_detector#Nonmaximum_suppression) and thinking about it myself, I believe most people are confused between the "angle" of a pixel and the "direction of the edge". I will explain in as much details as I can so everyone can understand exactly what's happening.
First of all, the angle 0 is not arbitrarily defined. If the angle for a particular pixel is 0, it means dy is 0 and dx can be +ve or ve (from the definition of tangent). The direction of dx and dy is hidden in the definition of the Sobel operator where dx is the horizontal (+ve>east, ve>west) direction and dy is the vertical (+ve>south, ve>north) direction. Therefore, angle 0 is defined as the horizontal direction (more on this later).
Now, if we consider a straight edge in which all pixels have an angle 0. This means all pixels have nonzero dx and zero dy, i.e. their values differ from the pixels to their left or right but have the same values as the pixels above or below. This means that this a VERTICAL edge even though all pixels have angles 0 (in the HORIZONTAL direction). Therefore, when we want to to non max suppression to a pixels with angle 0, we're looking at a vertical edge and we should compare its gradient with pixels to the left or right.
i.e. for angle 0 condition, the original code is:
if (((22.5 < Tangent) && (Tangent <= 22.5))  ((157.5 < Tangent) && (Tangent <= 157.5)))
{
if ((Gradient[i, j] < Gradient[i, j + 1])  (Gradient[i, j] < Gradient[i, j  1]))
NonMax[i, j] = 0;
}
and the correct code should be:
if (((22.5 < Tangent) && (Tangent <= 22.5))  ((157.5 < Tangent) && (Tangent <= 157.5)))
{
if ((Gradient[i, j] < Gradient[i+1, j])  (Gradient[i, j] < Gradient[i1, j]))
NonMax[i, j] = 0;
assuming the image is represented as Gradient[x,y] or Gradient[col, row], which I think is what the author intended. Other conditions can be deduced using similar reasoning except one should be careful with +ve and 45 degrees. The +1 or 1 pixels is determined based on the fact that +dx is east and +dy is south (which again is determined inherently from the sobel operator).
Another point that I want to make is that Math.Atan returns value between 90 to 90, so you actually don't need the second condition for all your if statements. In fact, if you have an angle that's greater than 90, say 120 (assuming 0 is the east direction), atan will return 60 instead. This turns out to be correct for our purpose since 60 and 120 is actually on the same line (through origin) and nonmax suppression only cares about the pixels on either side of the line.
Here's my final code:
if (Math.Abs(angle) < 22.5)
{
if ((Gradient[i, j] < Gradient[i + 1, j])  (Gradient[i, j] < Gradient[i  1, j]))
NonMax[i, j] = 0;
}
else if (Math.Abs(angle) > 67.5)
{
if ((Gradient[i, j] < Gradient[i, j + 1])  (Gradient[i, j] < Gradient[i, j  1]))
NonMax[i, j] = 0;
}
else if ((67.5 < angle) && (angle <= 22.5))
{
if ((Gradient[i, j] < Gradient[i + 1, j  1])  (Gradient[i, j] < Gradient[i  1, j + 1]))
NonMax[i, j] = 0;
}
else if ((22.5 < angle) && (angle <= 67.5))
{
if ((Gradient[i, j] < Gradient[i + 1, j + 1])  (Gradient[i, j] < Gradient[i  1, j  1]))
NonMax[i, j] = 0;
}
This is based on two assumptions:
1. Coordinates are represented as [x,y].
2. (0,0) is at the top left corner. X increases to the right and y increases in the downward direction.
In summary, I believe the nonmax suppression in the original code suppresses in the wrong direction, which explains why the edge image in the example looks fuzzy. After the correction, the edge map should look very sharp. If you find my explanation confusing or unnecessarily detailed, then maybe wikipedia can help you understand better!
(And even with all this, this code still saved me a lot of time, so big thanks to Vinayak!)





First of all, I apologize for making such a strong statement, but after reading Wikipedia (https://en.wikipedia.org/wiki/Canny_edge_detector#Nonmaximum_suppression) and thinking about it myself, I believe most people are confused between the "angle" of a pixel and the "direction of the edge". I will explain in as much details as I can so everyone can understand exactly what's happening.
First of all, the angle 0 is not arbitrarily defined. If the angle for a particular pixel is 0, it means dy is 0 and dx can be +ve or ve (from the definition of tangent). The direction of dx and dy is hidden in the definition of the Sobel operator where dx is the horizontal (+ve>east, ve>west) direction and dy is the vertical (+ve>south, ve>north) direction. Therefore, angle 0 is defined as the horizontal direction (more on this later).
Now, if we consider a straight edge in which all pixels have an angle 0. This means all pixels have nonzero dx and zero dy, i.e. their values differ from the pixels to their left or right but have the same values as the pixels above or below. This means that this a VERTICAL edge even though all pixels have angles 0 (in the HORIZONTAL direction). Therefore, when we want to to non max suppression to a pixels with angle 0, we're looking at a vertical edge and we should compare its gradient with pixels to the left or right.
i.e. for angle 0 condition, the original code is:
if (((22.5 < Tangent) && (Tangent <= 22.5))  ((157.5 < Tangent) && (Tangent <= 157.5)))
{
if ((Gradient[i, j] < Gradient[i, j + 1])  (Gradient[i, j] < Gradient[i, j  1]))
NonMax[i, j] = 0;
}
and the correct code should be:
if (((22.5 < Tangent) && (Tangent <= 22.5))  ((157.5 < Tangent) && (Tangent <= 157.5)))
{
if ((Gradient[i, j] < Gradient[i+1, j])  (Gradient[i, j] < Gradient[i1, j]))
NonMax[i, j] = 0;
}
assuming the image is represented as Gradient[x,y] or Gradient[col, row], which I think is what the author intended. Other conditions can be deduced using similar reasoning except one should be careful with +ve and 45 degrees. The +1 or 1 pixels is determined based on the fact that +dx is east and +dy is south (which again is determined inherently from the sobel operator).
Another point that I want to make is that Math.Atan returns value between 90 to 90, so you actually don't need the second condition for all your if statements. In fact, if you have an angle that's greater than 90, say 120 (assuming 0 is the east direction), atan will return 60 instead. This turns out to be correct for our purpose since 60 and 120 is actually on the same line (through origin) and nonmax suppression only cares about the pixels on either side of the line.
Here's my final code:
if (Math.Abs(angle) < 22.5)
{
if ((Gradient[i, j] < Gradient[i + 1, j])  (Gradient[i, j] < Gradient[i  1, j]))
NonMax[i, j] = 0;
}
else if (Math.Abs(angle) > 67.5)
{
if ((Gradient[i, j] < Gradient[i, j + 1])  (Gradient[i, j] < Gradient[i, j  1]))
NonMax[i, j] = 0;
}
else if ((67.5 < angle) && (angle <= 22.5))
{
if ((Gradient[i, j] < Gradient[i + 1, j  1])  (Gradient[i, j] < Gradient[i  1, j + 1]))
NonMax[i, j] = 0;
}
else if ((22.5 < angle) && (angle <= 67.5))
{
if ((Gradient[i, j] < Gradient[i + 1, j + 1])  (Gradient[i, j] < Gradient[i  1, j  1]))
NonMax[i, j] = 0;
}
This is based on two assumptions:
1. Coordinates are represented as [x,y].
2. (0,0) is at the top left corner. X increases to the right and y increases in the downward direction.
In summary, I believe the nonmax suppression in the original code suppresses in the wrong direction, which explains why the edge image in the example looks fuzzy. After the correction, the edge map should look very sharp. If you find my explanation confusing or unnecessarily detailed, then maybe wikipedia can help you understand better!
(And even with all this, this code still saved me a lot of time, so big thanks to Vinayak!)





Hello,
thank you for improvement!
Three question:
1. is your angle is exactly the same as Tangent in article and code?
2. do your or somebody else proof your code?
3. Did you notice that condition ((157.5 < Tangent) && (Tangent <= 157.5)) never meets and how this can affect your final code?
Many thanks in advance,
Alex





if (((157.5 < Tangent) && (Tangent <= 112.5))  ((67.5 < Tangent) && (Tangent <= 22.5)))
should be:
if (((157.5 < Tangent) && (Tangent <= 112.5))  ((22.5 < Tangent) && (Tangent <= 67.5)))
Besides that this implementation saved me lots of time. Thanks.





Hello togerher,
can, please, explain this peace of code inside GaussianFilter:
int[,] Output = new int[Width, Height];
.....
.....
Output = Data;
this make no sence, new int[] can be ommited, because of Output = Data.
Next lines:
for (i = Limit; i <= ((Width  1)  Limit); i++)
{
for (j = Limit; j <= ((Height  1)  Limit); j++)
{
Sum = 0;
for (k = Limit; k <= Limit; k++)
{
for (l = Limit; l <= Limit; l++)
{
Sum = Sum + ((float)Data[i + k, j + l] * GaussianKernel[Limit + k, Limit + l]);
}
}
Output[i, j] = (int)(Math.Round(Sum / (float)KernelWeight));
}
}
Here would be suggested, that Data is "input" and Output is "output", but this not true (see above), Output overwites itself inside loops.
Many thanks in advice!
Alex





Hello together,
as expirienced developer I had try to understand the edge switch/case part (many if's with Tangent as parameter) to identify if fixes suggested here are all really correct.
As I quickly saw, this is simply vector condition, the tangent circle is divided not from 0..360° but from 0..180 (bottom side) and 0..180° (upper side). The 0° is not on the top as usually (as teached at scool) but at 90°.
The is assumption, tangent vector belong an axes is that vector coordinate is near as 22.5° to corresponding axis.
Now taken pen and paper and mark a points on circle.
After that check code.
In my opinion, all parts EXCEPT 45°was CORRECT!
Only 45° part should be corrected as:
if (((157.5 < Tangent) && (Tangent <= 112.5))  ((67.5 >= Tangent) && (Tangent > 22.5)))
The part of horizontal line was correct! The fix posted here by someone is wrong.
Now, result is correct and much more pleasant  the difference is really markable!
Cu,
Alex





Dear Sir,
I am happy to see your response, I am very busy now a days, I started this as my initial PhD Work. Wanted to share with others. keep the things going.
best regards,
Dr. Vinayak Ashok Bharadi





The horizontal part is also wrong:
if (((22.5 < Tangent) && (Tangent <= 22.5))  ((157.5 < Tangent) && (Tangent <= 157.5)))
since the second part will never become true!
Tangent>157.5 and Tangent<=157.5  how should one value ever meet this condition?





Dear Dr. Vinayak Ashok Bharadi,
many thanks for sharing the code.
It's very pleasant to see and try fully workable solution.
But I have some questions:
Many posters note bugs or improvements, some posts are very strage because their does not explain what is buggy and how to solve.
It would be very nice, if You can write here some statements about such posts and mark improved code parts if something was really wrong.
Of couse, it would be also nice, if you upload a new improved version of code here.
Many thanks in advice!
Alex





Original conditions for horizontal line:
if (((22.5 < Tangent) && (Tangent <= 22.5))  ((157.5 < Tangent) && (Tangent <= 157.5)))
Good conditions:
if (((22.5 < Tangent) && (Tangent <= 22.5))  (157.5 < Tangent)  (Tangent <= 157.5))





Can You, please, explain why?
Did You verified that?





Dear Sir,
I am happy to see your response, I am very busy now a days, I started this as my initial PhD Work. Wanted to share with others. keep the things going.
best regards,
Dr. Vinayak Ashok Bharadi





the horizontal edge will never have ((157.5 < Tangent) && (Tangent <= 157.5)). Tangent > 157 then it is horizontal, or Tangent < 157, then it is horizontal too. the range of Tangent is [180,180] if you use Atan2. if you use Atan, the result range is [90,90] anyway. The computation of Tangent and quantification of direction has a discrepancy.





Given the definition of D1 (D1= 1/(2*pi*Sigma*Sigma);), the following line in the GenerateGaussianKernel subroutine is wrong:
Kernel[SizeofKernel / 2 + i, SizeofKernel / 2 + j] = ((1 / D1) * (float)Math.Exp((i * i + j * j) / D2));
(1/D1) should be replaced with D1





I totally agree with you.
Source: I teach statistics.





Can author or somebody commit that?
Did You verified this produces better/correct results?





how to get the edge detection of another image on the same mainform of canny edge detection?





Just joking, but do fix the title, your code is in C, not C#.





It should be Canny Edge Detection in C, not in C#.





Maybe I'm missing something, but the code shown in the article and in the download, are C#.





also see it as c#
project works great
thanks for posting it.





do you have any idea to add subpixel accuracy in this code?





//45 Degree Edge
if (((157.5 < Tangent) && (Tangent <= 112.5))  ((67.5 > Tangent) && (Tangent >= 22.5)))
{
if ((Gradient[i, j] < Gradient[i + 1, j + 1])  (Gradient[i, j] < Gradient[i  1, j  1]))
NonMax[i, j] = 0;
}





What is THE BUG?
What is correct solution?
Can You, please, explain why?
Did You verified that?






General News Suggestion Question Bug Answer Joke Praise Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

