Add your own alternative version
Stats
190.1K views 19.8K downloads 89 bookmarked
Posted
12 Jul 2010

Comments and Discussions



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!)





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 >





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





currently,I'm interest in Canny Edge detection and I decided to apply Canny edge detection in my project. May I know whether Canny edge detection able use in image recognition? Hope to get your reply soon






I was checking out the code (in the download) and I found that the Sobel masks used in DetectCannyEdges() are:
int[,] Dx = {{1,0,1},
{1,0,1},
{1,0,1}};
int[,] Dy = {{1,1,1},
{0,0,0},
{1,1,1}};
This differs from the Sobel masks provided in the included PDF file (which is amazing btw, you must write in the article that one can refer to the PDF to learn how Canny works):
[ 1 0 1 ] [ 1 2 1 ]
KGX = [ 2 0 2 ] KGY = [ 0 0 0 ]
[ 1 0 1 ] [ 1 2 1 ]
I was wondering if this is by intention or a mistake. Could you explain why the difference if it is by intention?
PS: Section 3 (Nonmaximum suppression) in your article appears broken. Perhaps the <pre> tag is malformed or something.





This one I am able to answer. One gives higher priority to horizontal and vertical lines (meaning they will appear slightly darker/thicker), the other treats all lines equally.





Hi sir,
I'm solve to make an implementations to convert an image to binary image bassed in threshold. Now i need some class or namespace to implements Gradient Vector Flow algoritm in C#. Could you or anybody help me plesae?
Thanks you.





Hi sir,
I'm trying to pass MATLAB code to C# code. In Matlab there are constructed many tools, but in C # does not. Your code is really useful, but in my case I need to convert image to binary image, based on threshold. In matlab is very easy because I use im2bw fuction to do it, but in C# i don´t know. Could you help me plesae?
Thanks you.





hello sir ,
I am doing image processing with C.. can u please tel me the equivalent C code for canny edge detection in C since i am very weak and a newbie in C.
thank u





sir is it a c code or c++ code...? m doing it in linux and getting some error





Greetings,
This is a C# code, but with some minor modifications you can run in C,
Edit the main Canny Class file, convert the functions in C/C++ equivalent syntax
Regards,
Dr. Vinayak Ashok Bharadi





This isn't what I would consider an article, this is a code dump. Articles should teach and explain, not be a repository for copy/paste programmers. If this is such a well known topic (as you indicated to others that expressed the same sentiment) then you should have no probelm explaining it





I know that it is a code dump. and I sincerely feel sorry for that , but I just wanted to share the code only with the world, canny edge detection is a widely used function in Image Processing, In the literature you can find the theory. Thank you for your appreciation.
Best Regards,
Dr. Vinayak Ashok Bharadi






Yes, the Travers() should be minimized. There has already been a comment about copypaste code. Why not show a better solution here? Would this one be better?
private void Travers(int X, int Y)
{
if (VisitedMap[X, Y] == 1)
{
return;
}
for (int i = 1; i <= 1; i++)
{
for (int j = 1; j <= 1; j++)
{
if (i == 0 && j == 0)
{
continue;
}
else if (EdgePoints[X + i, Y + j] == 2)
{
VisitedMap[X + i, Y + j] = EdgeMap[X + i, Y + j] = 1;
Travers(X + i, Y + j);
}
}
}
}






i searched several site but got ur one its ow some






In Canny.cs on line 445:
if (((157.5 < Tangent) && (Tangent <= 112.5))  ((67.5 < Tangent) && (Tangent <= 22.5)))
Thank you very much for this article.





Thank you for your suggestion. I will work on this.
Thanks,
Vinayak





I like these kind of scientific development





First: there's a lot of "divide by 2" in the code, but the fraction doesn't change inside the loop. Calculate the average once outside the loop and then use it.
Second, float might be a bad choice because double fits without promotiondemotion into the math registers.
I haven't tried it, but my guess is these simple changes would improve performance.





The 2D Gaussian kernel [Math.Exp((i * i + j * j) / D2)] is separable into a horizontal pass and a vertical one (because the expression above can be written as Math.Exp((i*i)/D3) * Math.Exp((j*j)/D3) where D3 is sigma * root two).
This means that the 2D convolution can be performed by a horizontal filtering pass followed by a vertical filtering pass, which means that it becomes an O(2N) operation instead of O(N^2). This is an important speedup when N is more than (say)10.
Phil Atkin
Synoptics Ltd., Cambridge, UK





In response to the other posters, you say "The canny edge detection algorithm is very well known...". If it is well known, then there is no need to post it here on CP. If your goal was to simply make an open source implementation of the technique, then please post it on a site that specializes in code management (codeplex, github, etc).
The point of writing an article is to highlight things that might not be obvious in the code. Most of us don’t have time to go through code files line by line looking for comments; especially not when the code is just raw mathematics.






The code is informative, not the article. I think you are missing the point I, and others, are trying to make. Any of us could post some code and say "Here is code that does Foo following the Bar algorythm", but that doesn't mean it qualifies as an article. As you've seen from the other posts, I'm not alone on this opinion. You need to explain the details better because 99.99% of us don't know anything about edge detection.
Josh Fischer





I agree with you on not explaning the article... he should explain the Code/Algorithm...
But I dont agree on everything else... why you want to discorage new member, who is trying to start contributing on something ?
(Atleast he is not like me sucking up everything, not sharing anything... )





I'm not trying to discourage him, in fact I'm trying to do the opposite. The value of CP, IMHO, is that people take the time to explain their topic. Sometimes they are very simple things for newbies, other times they are complex topics which only a small percentage of people care about (this article may qualify as the latter). Either way, you should be able to read the article without having to look at code and/or comments to get a good idea of what's going on.
It may seem counterintuitive, but the fact that I'm commenting on this article shows I am being encouraging. I want more explanation because it looks very interesting and I want to understand the code/article better.
So Vinayak Bharadi, good start, but please look at some of the other popular aritlces on CP to get a feel for what most people are expecting.
Josh Fischer





I didnt know about canny edge algorithm.. and if you actually read the article, you get an idea on how it works.







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.

