Click here to Skip to main content
15,888,984 members
Search within:


Articles / Programming Languages / C#
 
Article

Canny Edge Detection in C#

Rate me:
Please Sign up or sign in to vote.
4.65/5 (60 votes)
23 Apr 2012CPOL2 min read 331.5K   25.5K   97   63
Implementation of canny Edge Detection Algorithm

Image 1

Introduction

The purpose of edge detection in general is to significantly reduce the amount of data in an image, while preserving the structural properties to be used for further image processing. Several algorithms exists, and this worksheet focuses on a particular one developed by John F. Canny (JFC) in 1986. Even though it is quite old, it has become one of the standard edge detection methods and it is still used in research.

The aim of JFC was to develop an algorithm that is optimal with regards to the following criteria:

1. Detection: The probability of detecting real edge points should be maximized while the probability of falsely detecting non-edge points should be minimized. This corresponds to maximizing the signal-to-noise ratio.

2. Localization: The detected edges should be as close as possible to the real edges.

3. Number of responses: One real edge should not result in more than one detected edge (one can argue that this is implicitly included in the first requirement).

With Canny’s mathematical formulation of these criteria, Canny’s Edge Detector is optimal for a certain class of edges (known as step edges). A C# implementation of the algorithm is presented here.

Background

The readers are advised to do more research on canny edge detection method for detailed theory.

Using the code

The Canny Edge Detection Algorithm

The algorithm runs in 5 separate steps:

1. Smoothing: Blurring of the image to remove noise.

<pimplemented through="" gaussian="" filtering="" with="" specific="" kernel="" size="" (n)="" and="" envelope="" parameter="" sigma.<="" p=""> <pthe gaussian="" filter="" mask="" is="" generated="" by="" following="" function="" :="" <="" p="">
C#
private void GenerateGaussianKernel(int N, float S ,out int Weight)
        {

            float Sigma = S ;
            float pi;
            pi = (float)Math.PI;
            int i, j;
            int SizeofKernel=N;
            
            float [,] Kernel = new float [N,N];
            GaussianKernel = new int [N,N];
            float[,] OP = new float[N, N];
            float D1,D2;


            D1= 1/(2*pi*Sigma*Sigma);
            D2= 2*Sigma*Sigma;
            
            float min=1000;

            for (i = -SizeofKernel / 2; i <= SizeofKernel / 2; i++)
            {
               for (j = -SizeofKernel / 2; j <= SizeofKernel / 2; j++)
                {
                    Kernel[SizeofKernel / 2 + i, SizeofKernel / 2 + j] = ((1 / D1) * (float)Math.Exp(-(i * i + j * j) / D2));
                    if (Kernel[SizeofKernel / 2 + i, SizeofKernel / 2 + j] < min)
                        min = Kernel[SizeofKernel / 2 + i, SizeofKernel / 2 + j];

                 }
            }
            int mult = (int)(1 / min);
            int sum = 0;
            if ((min > 0) && (min < 1))
            {

                for (i = -SizeofKernel / 2; i <= SizeofKernel / 2; i++)
                {
                    for (j = -SizeofKernel / 2; j <= SizeofKernel / 2; j++)
                    {
                        Kernel[SizeofKernel / 2 + i, SizeofKernel / 2 + j] = (float)Math.Round(Kernel[SizeofKernel / 2 + i, SizeofKernel / 2 + j] * mult, 0);
                        GaussianKernel[SizeofKernel / 2 + i, SizeofKernel / 2 + j] = (int)Kernel[SizeofKernel / 2 + i, SizeofKernel / 2 + j];
                        sum = sum + GaussianKernel[SizeofKernel / 2 + i, SizeofKernel / 2 + j];
                    }

                }

            }
            else
            {
                sum = 0;
                for (i = -SizeofKernel / 2; i <= SizeofKernel / 2; i++)
                {
                    for (j = -SizeofKernel / 2; j <= SizeofKernel / 2; j++)
                    {
                        Kernel[SizeofKernel / 2 + i, SizeofKernel / 2 + j] = (float)Math.Round(Kernel[SizeofKernel / 2 + i, SizeofKernel / 2 + j] , 0);
                        GaussianKernel[SizeofKernel / 2 + i, SizeofKernel / 2 + j] = (int)Kernel[SizeofKernel / 2 + i, SizeofKernel / 2 + j];
                        sum = sum + GaussianKernel[SizeofKernel / 2 + i, SizeofKernel / 2 + j];
                    }

                }

            }
          //Normalizing kernel Weight
          Weight= sum;
         
         return;
        }

Following subroutine removes noise by Gaussian Filtering

C#
private int[,] GaussianFilter(int[,] Data)
        {
            GenerateGaussianKernel(KernelSize, Sigma,out KernelWeight);

            int[,] Output = new int[Width, Height];
            int i, j,k,l;
            int Limit = KernelSize /2;

            float Sum=0;


 Output = Data; // Removes Unwanted Data Omission due to kernel bias while convolution

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

            }


            return Output;
        }

2. Finding gradients: The edges should be marked where the gradients of the image haslarge magnitudes.

Sobel X and Y Masks are used to generate X & Y Gradients of Image; next function implements differentiation using sobel Filter Mask

C#
private float[,] Differentiate(int[,] Data, int[,] Filter)
        {
            int i, j,k,l, Fh, Fw;

            Fw = Filter.GetLength(0);
            Fh = Filter.GetLength(1);
            float sum = 0;
            float[,] Output = new float[Width, Height];

            for (i = Fw / 2; i <= (Width - Fw / 2) - 1; i++)
            {
                for (j = Fh / 2; j <= (Height  - Fh / 2) - 1; j++)
                {
                  sum=0;
                   for(k=-Fw/2; k<=Fw/2; k++)
                   {
                       for(l=-Fh/2; l<=Fh/2; l++)
                       {
                          sum=sum + Data[i+k,j+l]*Filter[Fw/2+k,Fh/2+l];


                       }
                   }
                    Output[i,j]=sum;

                }

            }
            return Output;

        }

3. Non-maximum suppression: Only local maxima should be marked as edges.

We find gradient direction and using these direction we perform non maxima suppression (Read “Digital Image Processing- by R Gonzales-Pearson Education)

C#
// Perform Non maximum suppression:
           // NonMax = Gradient;

            for (i = 0; i <= (Width - 1); i++)
            {
                for (j = 0; j <= (Height - 1); j++)
                {
                    NonMax[i, j] = Gradient[i, j];
                }
            }
         
            int Limit = KernelSize / 2;
            int r, c;
            float Tangent;
    

            for (i = Limit; i <= (Width - Limit) - 1; i++)
            {
                for (j = Limit; j <= (Height - Limit) - 1; j++)
                {

                    if (DerivativeX[i, j] == 0)
                        Tangent = 90F;
                    else
                        Tangent = (float)(Math.Atan(DerivativeY[i, j] / DerivativeX[i, j]) * 180 / Math.PI); //rad to degree



                    //Horizontal Edge
                    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;
                    }


                    //Vertical Edge
                    if (((-112.5 < Tangent) && (Tangent <= -67.5)) || ((67.5 < Tangent) && (Tangent <= 112.5)))
                    {
                        if ((Gradient[i, j] < Gradient[i + 1, j]) || (Gradient[i, j] < Gradient[i - 1, j]))
                            NonMax[i, j] = 0;
                    }

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

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

                }
            }

4.Double thresholding: Potential edges are determined by thresholding.

5.Edge tracking by hysteresis: Final edges are determined by suppressing all edges that are not connected to a very certain (strong) edge.

C#
private void HysterisisThresholding(int[,] Edges)
        {

            int i, j;
            int Limit= KernelSize/2;


            for (i = Limit; i <= (Width - 1) - Limit; i++)
                for (j = Limit; j <= (Height - 1) - Limit; j++)
                {
                    if (Edges[i, j] == 1)
                    {
                        EdgeMap[i, j] = 1;

                    }

                }

            for (i = Limit; i <= (Width - 1) - Limit; i++)
            {
                for (j = Limit; j <= (Height  - 1) - Limit; j++)
                {
                    if (Edges[i, j] == 1)
                    {
                        EdgeMap[i, j] = 1;
                        Travers(i, j);
                        VisitedMap[i, j] = 1;
                    }
                }
            }




            return;
        }

//Recursive Procedure 
private void Travers(int X, int Y)
        {
            

            if (VisitedMap[X, Y] == 1)
            {
                return;
            }

            //1
            if (EdgePoints[X + 1, Y] == 2)
            {
                EdgeMap[X + 1, Y] = 1;
                VisitedMap[X + 1, Y] = 1;
                Travers(X + 1, Y);
                return;
            }
            //2
            if (EdgePoints[X + 1, Y - 1] == 2)
            {
                EdgeMap[X + 1, Y - 1] = 1;
                VisitedMap[X + 1, Y - 1] = 1;
                Travers(X + 1, Y - 1);
                return;
            }

           //3

            if (EdgePoints[X, Y - 1] == 2)
            {
                EdgeMap[X , Y - 1] = 1;
                VisitedMap[X , Y - 1] = 1;
                Travers(X , Y - 1);
                return;
            }

           //4

            if (EdgePoints[X - 1, Y - 1] == 2)
            {
                EdgeMap[X - 1, Y - 1] = 1;
                VisitedMap[X - 1, Y - 1] = 1;
                Travers(X - 1, Y - 1);
                return;
            }
            //5
            if (EdgePoints[X - 1, Y] == 2)
            {
                EdgeMap[X - 1, Y ] = 1;
                VisitedMap[X - 1, Y ] = 1;
                Travers(X - 1, Y );
                return;
            }
            //6
            if (EdgePoints[X - 1, Y + 1] == 2)
            {
                EdgeMap[X - 1, Y + 1] = 1;
                VisitedMap[X - 1, Y + 1] = 1;
                Travers(X - 1, Y + 1);
                return;
            }
            //7
            if (EdgePoints[X, Y + 1] == 2)
            {
                EdgeMap[X , Y + 1] = 1;
                VisitedMap[X, Y + 1] = 1;
                Travers(X , Y + 1);
                return;
            }
            //8

            if (EdgePoints[X + 1, Y + 1] == 2)
            {
                EdgeMap[X + 1, Y + 1] = 1;
                VisitedMap[X + 1, Y + 1] = 1;
                Travers(X + 1, Y + 1);
                return;
            }


            //VisitedMap[X, Y] = 1;
            return;
        }
               
        //Canny Class Ends
    }

This is performed by a recursive function which performs double thresholding by two thresholds High Threshold(TH) and Low Threshold (TL) and 8-connectivity analysis

Points of Interest

Please refer to "Digital Image Processing" by Gonzalez & woods, Pearson Education

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



Comments and Discussions

 
First PrevNext
Questionapply this code for an image Pin
Hai Luu26-Sep-20 5:34
Hai Luu26-Sep-20 5:34 
QuestionRecursive call of Travers method Pin
dnn201820-Jun-18 4:55
dnn201820-Jun-18 4:55 
QuestionNon maximum suppression is all wrong (seriously)!!! Pin
Member 1220742720-Jul-16 13:04
Member 1220742720-Jul-16 13:04 
QuestionNon maximum suppression is all wrong (seriously)!!! Pin
Member 1220742720-Jul-16 13:04
Member 1220742720-Jul-16 13:04 
First of all, I apologize for making such a strong statement, but after reading Wikipedia (https://en.wikipedia.org/wiki/Canny_edge_detector#Non-maximum_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 non-zero 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:
C#
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:
C#
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[i-1, 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 non-max suppression only cares about the pixels on either side of the line.

Here's my final code:

C#
//Horizontal angle, vertical edge (-22.5~22.5)
                    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;
                    }

                    //Vertical angle, horizontal edge (67.5~90 or -67.5~-90)
                    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;
                    }

                    //-45 degree angle, +45 Degree Edge
                    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;
                    }

                    //45 degree angle, -45 degree Edge
                    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!)
AnswerRe: Non maximum suppression is all wrong (seriously)!!! Pin
infal2-May-17 2:34
infal2-May-17 2:34 
BugBug in Non Maximum Suppression Pin
Azzzez15-Jan-16 11:49
Azzzez15-Jan-16 11:49 
QuestionCan please somebody explain? Pin
infal30-Nov-13 15:24
infal30-Nov-13 15:24 
NewsAsked myself some qestions - here answers. Please commit! Pin
infal28-Nov-13 4:38
infal28-Nov-13 4:38 
GeneralRe: Asked myself some qestions - here answers. Please commit! Pin
vinu_bharadi13-Mar-15 2:36
vinu_bharadi13-Mar-15 2:36 
BugRe: Asked myself some qestions - here answers. Please commit! Pin
tbaust6-Apr-15 5:05
tbaust6-Apr-15 5:05 
SuggestionThanks, but, please, clarify bugs/questions here! Pin
infal28-Nov-13 2:25
infal28-Nov-13 2:25 
QuestionAnother bug Pin
Garga2325-Jul-13 2:29
Garga2325-Jul-13 2:29 
AnswerRe: Another bug Pin
infal28-Nov-13 2:15
infal28-Nov-13 2:15 
GeneralRe: Another bug Pin
vinu_bharadi13-Mar-15 2:37
vinu_bharadi13-Mar-15 2:37 
GeneralRe: Another bug Pin
cenrao15-Apr-15 10:19
cenrao15-Apr-15 10:19 
QuestionWrong code Pin
chipu842-May-13 2:41
chipu842-May-13 2:41 
AnswerRe: Wrong code Pin
Kangerm00se17-Jun-13 5:18
Kangerm00se17-Jun-13 5:18 
AnswerRe: Wrong code Pin
infal28-Nov-13 2:16
infal28-Nov-13 2:16 
Questiondifficulty in project of image processing Pin
Member 950879327-Oct-12 20:46
Member 950879327-Oct-12 20:46 
QuestionWhat if I don't want to detect the edges of Cans? Pin
Dewey29-May-12 13:15
Dewey29-May-12 13:15 
QuestionPlease fix the topic of this article Pin
Francoishill24-Apr-12 20:53
Francoishill24-Apr-12 20:53 
AnswerRe: Please fix the topic of this article Pin
Judah Gabriel Himango3-Jan-13 11:06
sponsorJudah Gabriel Himango3-Jan-13 11:06 
GeneralGreat Article! Works Great! Converted to Visual Studio 2012 with no problems. Pin
Member 1113306625-Apr-15 15:37
Member 1113306625-Apr-15 15:37 
Questionabout subpixel Pin
xiejiahe2-Apr-12 17:49
xiejiahe2-Apr-12 17:49 
Questionthere is a bug in -45 degree Pin
xiejiahe2-Apr-12 17:46
xiejiahe2-Apr-12 17:46 
Last Visit: 31-Dec-99 18:00     Last Update: 30-Apr-24 6:05Refresh123 Next ᐅ

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink
Advertise
Privacy
Cookies
Terms of Use
Layout: fixed | fluid

Posted 13 Jul 2010

Article Copyright 2010 by Dr. Vinayak Ashok Bharadi
Everything else Copyright © CodeProject, 1999-2024

Web01 2.8:2024-04-02:1