Recently I had to implement the Canny edge detection algorithm in my Digital Image Processing class at ETS. I had seen the algorithm in use in some of our vision software for the SONIA Project, but I had never actually looked into the details of it until now.
The implementation of the Canny algorithm provides great insights into every aspect of classical spatial-domain digital image processing. It requires the application of lowpass filtering (gaussian blurring), gradient (first derivative) calculation and several iterative and recursive non-linear algorithms.
Of course, edge extraction is not a trivial matter and there are no magical answers. There are several degrees of freedom in the parameters of the edge detector that determine which “edges” will be extracted from a given image.
Over the course of my implementation, I found several excellent resources which have helped me understand the algorithm. The two better ones are both from image processing lecture notes:
- Prof Sohaib Khan’s Canny Edge Detector page at the Lahore University of Management Science provides a step-by-step explanation of the algorithm with figures.
- Cornelia Fermüller’s lecture notes about edge detection cover all aspects of classical edge extraction using multiple gradient definitions, the Laplacian and the Canny algorithm. This page has more theroretical background and is representative of an introductory Digital Image Processing course.
My initial implementation of the algorithm was done in MATLAB using the Image Processing Toolbox. I used this version of the algorithm to generate two movies showing the steps of the algorithm visually (see bottom of this post for the movies). They were generated by saving frames and creating a batch file with ImageMagick command invokations to add captions. The individual frames were then compiled into movies using VirtualDub.
After doing the MATLAB implementation, I went on to make a Java version to see what it would be like to build it from “scratch”, including a basic image processing library. I did not use a pre-defined image processing library, deciding instead to make a simple Matrix class that implemented all the operations required for image processing.
The Java library (MatrixF.java) implements the following operations over float-typed matrices:
- Loading/Saving of MATLAB-compatible text-format matrices
- Elementwise operations between matrices (+, -, kA, k-A, “.*”, “./”)
- Logical operations between matrices, with or without constants (<=, <, ==, !=, >, >=, &&, ||)
- Element-wise application of float functions (ie: Math.sin(), Math.exp(), myFloatMethod())
- Spatial filtering using correlation (equivalent to MATLAB’s filter2() function)
After creating the MatrixF class, I implemented the Canny algorithm, as well as a contour segmentation algorithm using it. The result is in Canny.java.
The Canny algorithm implements the following steps in order:
- Gaussian blur with specified sigma value on source image
- Gradient magnitude and argument calculation using the Prewitt mask
- Gradient argument sectorization (quantization) over the 4 main directions (North/South, East/West, Northeast/Southwest, Northwest/Southeast)
- Non-maxima value supression on gradient magnitude (thinning of contours)
- Hysteresis thresholding of non-maxima-supressed pixels to extract contours (edge-linking)
Using all Float operations and no in-place processing of matrices, the speed gain is still about 16x between the Java version and the MATLAB version, which is significant 🙂 My version of hysteresis thresholding uses a processing list instead of straight recursion, to maximise efficiency and prevent stack overflows (thanks to Jean-François Im for the tips about that).
The example movies showing all steps of the Canny algorithm on two sample images are shown below. You can access the full resolution AVI files from the vimeo entries.
If you want to understand the Canny algorithm better, I encourage you to check-out the two references mentionned above and to try implementing the algorithm from scratch. There is a lot to be learned about image processing from this classic algorithm.