Canny Edge Detector

 

Mikel Rodriguez

 

 

 

 

 

 

 

 

 

 

Introduction:

 

Edge detection is an essential preprocessing step in many computer vision algorithms. Within this project we implement one of these methods, the Canny Edge Detector.

 

The Canny edge detector is a popular method for detecting edges that begins by smoothing an image by convolving it with a Gaussian of a given sigma value. Based on the smoothed image, derivatives in both the x and y direction are computed; these in turn are used to compute the gradient magnitude of the image.

 

Once the gradient magnitude of the image has been computed, a process called ‘non maximum suppression’ is performed; in which pixels are suppressed if they do not constitute a local maximum.

 

The final step in the canny edge detector is the hysteresis operator, in which pixels are marked as either edges, non edges and in-between, this is done based on threshold values. The next step is to consider each of the pixels that are in-between, if they are connected to edge pixels these are marked as edge pixels as well.

 

The result of this edge detector is a binary image in which the white pixels closely approximate the true edges of the original image.

 

Instructions for executing the edge detector:

 

 

 

I have implemented the edge detector in Matlab. To run the program, set the appropriate paths and run the function in the following manner:

 

>>canny_edges(MAX,MIN,SIGMA)

 

In which MAX is the maximum threshold value for hysteresis, and MIN value is the minimum. SIGMA is used for generating the Gaussian kernels.

 

 

Results

For:

Max Threshold:1.5

Min threshold 0.05

Sigma :1

 

 Derivative In X

 Derivative in Y

 Gradient

After non maximum suppression

After Hysteresis

 

For:

Max Threshold:1.5

Min threshold 0.05

Sigma :1

 

Derivative In X

Derivatice in Y

Gradient

After non maximum suppression

After Hysteresis

For: A max threshold of 1, a min of 0.04 and a sigma of 1.2

 

 Derivative in x

 Derivative in y

 

 Gradient

 Non Maximum Suppression

 Hysteresis

 

 

 

 

For: A max threshold of 1, a min of 0.04 and a sigma of 1.2

 

 Derivative in x

Derivative in y

Gradient

 Non Max Suppression

 Hysteresis

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Source Code

 

 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% CAP 5405, Fall 2005                                                                                     %

% Canny Edge Detector                                                                                   %

% Mikel Rodriguez                                                                                            %

%                                                                                                                       %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function canny_edges(max_hysteresis_thresh, min_hysteresis_thresh,sigma);

 

 

%%INIT VARIABLES:

 

%%Read in image:

 

ORIGINAL_IMAGE=imread('c:\lenna.pgm');  

 

 

%%Convert to double:

ORIGINAL_IMAGE=im2double(ORIGINAL_IMAGE);    

 

%%Save height and width

[H,W]=size(ORIGINAL_IMAGE);         

 

 

%%Derivatives in x and y

derivative_x=zeros(H,W);              

derivative_y=zeros(H,W);    

 

 

%%Gaussian kernel

size_of_kernel = 6*sigma+1;         

adjust= ceil(size_of_kernel/2)

Y_GAUSSIAN=zeros(size_of_kernel,size_of_kernel);

X_GAUSSIAN=zeros(size_of_kernel,size_of_kernel);

 

%%Create gaussian kernels for both x and y directions based on the sigma

%%that was given.

 

for i=1:size_of_kernel

    for iiii=1:size_of_kernel

        Y_GAUSSIAN(i,iiii) = -( (i-((size_of_kernel-1)/2)-1)/( 2* pi * sigma^3 ) ) * exp ( - ( (i-((size_of_kernel-1)/2)-1)^2 + (iiii-((size_of_kernel-1)/2)-1)^2 )/ (2*sigma^2) );

    end

end

 

for i=1:size_of_kernel

    for iiii=1:size_of_kernel

        X_GAUSSIAN(i,iiii) = -( (iiii-((size_of_kernel-1)/2)-1)/( 2* pi * sigma^3 ) ) * exp ( - ( (i-((size_of_kernel-1)/2)-1)^2 + (iiii-((size_of_kernel-1)/2)-1)^2 )/ (2*sigma^2) );

    end

end

 

 

GRADIENT =  zeros(H,W);       

non_max = zeros(H,W);     

 

post_hysteresis = zeros(H,W); 

 

 

 

 

%%Image Derivatives:

 

for r=1+ceil(size_of_kernel/2):H-ceil(size_of_kernel/2)  

    for c=1+ceil(size_of_kernel/2):W-ceil(size_of_kernel/2)  

        reference_row=  r-ceil(size_of_kernel/2); 

        reference_colum=  c-ceil(size_of_kernel/2); 

        for yyy=1:size_of_kernel  

            for yyy_col=1:size_of_kernel  

                derivative_x(r,c) = derivative_x(r,c) + ORIGINAL_IMAGE(reference_row+yyy-1, reference_colum+yyy_col-1)*X_GAUSSIAN(yyy,yyy_col);

            end

        end

    end

end

 

 

for r=1+ceil(size_of_kernel/2):H-ceil(size_of_kernel/2)  

    for c=1+ceil(size_of_kernel/2):W-ceil(size_of_kernel/2) 

        reference_row=  r-ceil(size_of_kernel/2); 

        reference_colum=  c-ceil(size_of_kernel/2); 

        for yyy=1:size_of_kernel  

            for yyy_col=1:size_of_kernel 

                derivative_y(r,c) = derivative_y(r,c) + ORIGINAL_IMAGE(reference_row+yyy-1, reference_colum+yyy_col-1)*Y_GAUSSIAN(yyy,yyy_col);

            end

        end

    end

end

 

 

%%Compute the gradient magnitufde based on derivatives in x and y:

 

for r=1+ceil(size_of_kernel/2):H-ceil(size_of_kernel/2)  

    for c=1+ceil(size_of_kernel/2):W-ceil(size_of_kernel/2)  

        GRADIENT(r,c) = sqrt (derivative_x(r,c)^2 + derivative_y(r,c)^2 );

    end

end

 

%%Perform Non maximum suppression:

 

non_max = GRADIENT;

for r=1+ceil(size_of_kernel/2):H-ceil(size_of_kernel/2) 

    for c=1+ceil(size_of_kernel/2):W-ceil(size_of_kernel/2)  

       

        %%quantize:

        if (derivative_x(r,c) == 0) tangent = 5;       

        else tangent = (derivative_y(r,c)/derivative_x(r,c));   

        end

        if (-0.4142<tangent & tangent<=0.4142)

            if(GRADIENT(r,c)<GRADIENT(r,c+1) | GRADIENT(r,c)<GRADIENT(r,c-1))

                non_max(r,c)=0;

            end

        end

        if (0.4142<tangent & tangent<=2.4142)

            if(GRADIENT(r,c)<GRADIENT(r-1,c+1) | GRADIENT(r,c)<GRADIENT(r+1,c-1))

                non_max(r,c)=0;

            end

        end

        if ( abs(tangent) >2.4142)

            if(GRADIENT(r,c)<GRADIENT(r-1,c) | GRADIENT(r,c)<GRADIENT(r+1,c))

                non_max(r,c)=0;

            end

        end

        if (-2.4142<tangent & tangent<= -0.4142)

            if(GRADIENT(r,c)<GRADIENT(r-1,c-1) | GRADIENT(r,c)<GRADIENT(r+1,c+1))

                non_max(r,c)=0;

            end

        end

    end

end

 

 

 

 

post_hysteresis = non_max;

 

for r=1+ceil(size_of_kernel/2):H-ceil(size_of_kernel/2)  

    for c=1+ceil(size_of_kernel/2):W-ceil(size_of_kernel/2)  

        if(post_hysteresis(r,c)>=max_hysteresis_thresh) post_hysteresis(r,c)=1;

        end

        if(post_hysteresis(r,c)<max_hysteresis_thresh & post_hysteresis(r,c)>=min_hysteresis_thresh) post_hysteresis(r,c)=2;

        end

        if(post_hysteresis(r,c)<min_hysteresis_thresh) post_hysteresis(r,c)=0;

        end 

    end

end

 

 

 

vvvv = 1; 

 

while (vvvv == 1)

   

    vvvv = 0;

   

    for r=1+ceil(size_of_kernel/2):H-ceil(size_of_kernel/2)  

        for c=1+ceil(size_of_kernel/2):W-ceil(size_of_kernel/2)  

            if (post_hysteresis(r,c)>0)      

                if(post_hysteresis(r,c)==2) 

                   

                   

                    if( post_hysteresis(r-1,c-1)==1 | post_hysteresis(r-1,c)==1 | post_hysteresis(r-1,c+1)==1 | post_hysteresis(r,c-1)==1 |  post_hysteresis(r,c+1)==1 | post_hysteresis(r+1,c-1)==1 | post_hysteresis(r+1,c)==1 | post_hysteresis(r+1,c+1)==1 ) post_hysteresis(r,c)=1;

                        vvvv == 1;

                    end

                end

            end

        end

    end

   

end

 

 

 

for r=1+ceil(size_of_kernel/2):H-ceil(size_of_kernel/2) 

    for c=1+ceil(size_of_kernel/2):W-ceil(size_of_kernel/2)  

        if(post_hysteresis(r,c)==2) 

            post_hysteresis(r,c)==0;

        end   

    end

end

 

 

imwrite(ORIGINAL_IMAGE,'C:\Documents and Settings\User\Desktop\Results\original_image.bmp');                        

 

imwrite(derivative_x,'C:\Documents and Settings\User\Desktop\Results\derivative_x.bmp');            

imwrite(derivative_y,'C:\Documents and Settings\User\Desktop\Results\derivative_y.bmp');            

imwrite(GRADIENT,'C:\Documents and Settings\User\Desktop\Results\gradient.bmp');       

imwrite(non_max,'C:\Documents and Settings\User\Desktop\Results\non_max_supr.bmp');      

imwrite(post_hysteresis,'C:\Documents and Settings\User\Desktop\Results\original_image.bmp');