IMAGE PROCESSING: Algorithm uses partial derivatives to improve edge detection
One of the most important algorithms used in machine-vision and image-processing systems is that of edge detection. Although a number of different techniques including Sobel, Prewitt, Roberts, and Laplacian exist to perform this function, the most widely used edge detection technique, known as the Canny edge detector, was developed by John F. Canny in 1986 (see J. Canny, “A Computational Approach To Edge Detection,” IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 8(6):679–714, 1986).
In the development of this algorithm, Canny used a filter based on the first derivative of a Gaussian to produce what is still one of the most optimal edge detection algorithms.
Recently, however, a new algorithm based on the principle of edge detection using Boolean partial derivatives (EDBD) has been shown to outperform the Canny algorithm (see figure). Developed by Sos Agaian, a professor of electrical engineering at the University of Texas (San Antonio, TX, USA;www.utsa.edu) and others, the algorithm is now available through BA Logix (Boston, MA, USA; www.balogix.com) as part of the company’s EdgeMax software package.
Applicable both to binary and grayscale images, the technique has been published in the April issue of theIEEE Transactions on Systems, Man and Cybernetics (“Boolean Derivatives with Application to Edge Detection for Imaging Systems,” 40(2):371–382, 2010). Rather than use a filter based on a Gaussian, the EDBD technique first thresholds an image and then applies morphological operations such as thinning and/or skeletonization to generate a binary representation and thin the data to a Boolean expression consisting of 0s and 1s.
From this data a partial derivative of the Boolean expression must be computed. Of course, it is not possible to generate a partial derivative of a Boolean function (PDBFs) in a standard way, since the result will always be zero. However, an alternative method for computing this function is to generate PDBFs with one for each Boolean input literal of the original binary data.
Results from edge detection using Boolean partial derivatives (EDBD) techniques compared with those using the Canny edge detection algorithm.
Imagine for example, that the function:f(x) = f(x1, x2, x3) = (0,0,0,0,0,1,1,1) represents a binary value of an 8-bit string of values across an image. Because there are 8 bits in the data, three variables are needed to describe the complete string. Then, δf(x)/δx1, δf(x)/δx2, and δf(x)/δx3 can be used to represent the PDBFs of the function f(x).
Adding these PDBFs together results in a string with values (0,1,1,1,2,2,2,1). Thresholding this string results in (0,0,0,0,1,1,1,0) and then thinning this vector results in (0,0,0,0,0,1,0,0), which indicates the single step (or edge) in the original function or “image.”
To extend the technique for use with grayscale images, they must first be binarized. This can be accomplished using bit-plane decomposition or iterative thresholding combined with equal interval image slicing, the latter technique often being used in geospatial analysis. PDBFs are then again determined for all of these binary images, the results combined, thresholded, and thinned.
According to Vincent Chun, general manager of BA Logix, such PDBF algorithms outperform the Canny edge detection algorithm both visually and using quantitative measures such as those developed by William Pratt (seeDigital Image Processing, Second Edition, Wiley, 1991) and S. Carlsson (see “Sketch Based Coding of Gray Level Images,” Signal Process., 15(1):57–83, 1988). For system developers wishing to embed the algorithm into an FPGA, BA Logix also offers an FPGA hardware implementation of the algorithm that is capable of processing high-definition video at 60 frames/s.