Differential Equations and Edge Detection

On a computer, images are represented as a discrete collection of pixels. These pixels represent a linear combination of Red, Green, and Blue values which can be used to produce different colors. However, when processing an image, especially for edges, it is often inefficient and not very useful to process all three values for each pixel. This is because even small images can be made of hundreds of pixels, and some larger images are even made of millions of individual pixels. Processing the three red, green, blue values over potentially millions of pixels could end up being very costly and slow. As a result, the intensity of the image is often calculated and used instead. Although the exact definition for the intensity of a color can be a bit complex, for our purposes it suffices to think of it as simply the brightness of a color^[1]. There are multiple ways of calculating this value, two of which are listed below:

Average intensities of each red green blue value^[3]

\[ \frac{red + green + blue}{3} \]

Formula for Luminance^[4]

\[ 0.299*red + 0.587*green + 0.114*blue \]
These formulas result in a single value based on the amount of red, green, or blue the pixel has. Visually, the result is a shade of gray from the original image - another way to think of it is that all color data has been stripped and replaced with a single value of how bright the pixel is. This will improve processing time and efficiency while still being able to detect changes between pixels. However, there is still the issue of the loss of data. Although this is usually not a problem, in some cases it can lead to unexpected results. The main problem that may arise is that different colors can have the same intensity - especially when using the first equation. In edge detection, this can possibly lead to the absence of an edge when in fact there is one. While this can be prevented by using all three values instead of the intensity, it is often not necessary as the cases are rare and the edges themselves not very strong. Now that we have gone over how the intenstiy of an image can be calculated and used, next we will talk about how vectors can be calculated from images.

Images are commonly stored on computers as an array of pixels. Although on software they can be stored as a 1 dimensional array, it would be more accurate to think of these arrays as representing a 2 dimensional image. As a 2-Dimensional image, each pixel would have 8 surrounding neighbor pixels (North, North East, East, South East, South, South West, West, and North West). In each direction we can calculate a scalar quantity from the pixel - either an RGB value or its corresponding intensity. In otherwords, we have both a direction, and magnitude - thus we can calculate vector quantities for every pixel in an image. If we extend that principle to the whole area of pixels, can think of the Image as a 2D vectorspace. Furthermore, we can represent this image as a 2D matrix. Note, however, that this matrix will be very large - images are often a few thousands pixels wide by a few thousand pixels long, resulting in a total number of pixels to the order of millions. Now we can perform operations such as finding the gradient vector at a certain point, or perform convolution between the image matrix and another operator matrix. Let us first consider finding the gradient of a matrix.

The gradient vector is essentially the derivative of a vector. In the case of images, we are working with a 2-Dimensional space, so we can think of the gradient vector in terms of x and y. \[ \vec{\nabla}f(x, y) = \langle{\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}}\rangle \] This is our first use of differential equations with images, so it is worth our time to delve a bit further. In essence edge detection requires us to find the difference in intensity between a pixel and its surrounding neighbor pixels. The gradient vector allows to do just that on an image, which is why it is of much importance to us. However, the equation introduced above models the gradient vector on a continuouos space - whereas on computers images are stored as a discrete 2-Dimensional collection of pixels. Thus a separate equation must be considered for the discrete case^[5]. \[ \frac{\partial f}{\partial x} = \frac{I(x + 1, y) - I(x - 1, y)}{2} \] \[\frac{\partial f}{\partial y} = \frac{I(x, y + 1) - I(x, y - 1)}{2} \] I represents the 2-D image matrix, and the (x, y) refer to the pixel located at the point (x, y) on the image. Once the gradient vector is determined, some other properties can also be calculated. Specifically, the magnitude and angle of the gradient can be calculated. Because the gradient is essentially a derivative, its magnitude quantifies how quickly the image is changing at that point^[5]. In other words, the magnitude is a measure of how strong or defined an edge is compared with its neighboring pixels. The angle of the gradient will be normal to the edge, and so it can be used to calculate the direction of the edge.

Magnitude

\[ \| \mathbf{G} \| = \sqrt{{G_x}^2 + {G_y}^2} \]

Angle

\[ \theta = \arctan{\frac{G_y}{G_x}} \]

Matrix convolution involves the multiplication of a matrix against another matrix^[2]. This works by taking the center of a smaller matrix, which is called the kernel, and positioning it against an element of a larger matrix. Then the sum of the products of the values of the kernel with the corresponding value of the larger matrix is found. This sum is the new element at the position. This process is repeated until the whole matrix is covered. In this project we use special operators as the kernel that will be multiplied across the whole image matrix to calculate the gradient vectors of the image. One of the main problems to consider when conducting convolution with matrices, are the edges. For example, imagine we are using a 3x3 matrix as an operator for matrix convolution with a 100x100 matrix. If we center the 3x3 matrix along the edge of the larger matrix, then not all of the elements of the kernel will have a corresponding element from the larger matrix to multiply with. This can be accounted for in a couple of different ways. One method is to pad the edges of the 100x100 matrix with a border of zeroes one pixel deep. This would allow for convolution against the edges of the matrix, while not changing the overall values. Another way to handle this is to not start from the edge but from 1 element away from the edges. This would result in a smaller size matrix after the convolution, but the data will still be accurate. This project uses the first method, and pads matrices before convolution.

One of the main hurdles in image processing is dealing with noise in an image. In images, noise is often defined as a random variation of brightness or color that is not found in the original object being captured^[11]. Although there are many types of noise, in general noise tends to show up as small white dots that cover an image. The presence of noise can make it difficult to process an image because it causes portions of the image to be left out. One of the main ways to lessen the effects of noise is to apply a smoothing, or blurring, filter on an image. One commonly used smoothing filter is the Gaussian. Gaussian smoothing uses Gauss' equation in 2-Dimensions to weight the image according to a normal distribution. This gets rid of noise because it reduces the variation about the center of the image.

2D Gaussian^[12]

\[ G = \frac{1}{2\pi\sigma^2} e^{-\frac{x^2 + y^2}{2\sigma^2}} \] The larger the sigma value, the greater the standard deviation meaning that more of the image is weighted. This translates to a blurrier image. The x, y coordinates are based on the size of the filter to be applied to the image. For example, a 3x3 filter would have a domain centered at (0, 0), with the top left coordinate at (-1, 1). The resulting filter is then normalized against the sum of all Gaussian values, and then applied against the image using convolution.

3x3 Gaussian filter with sigma of 1

Now that we got the basics out of the way, we can start discussing how these edge detection algorithms really work. We will start with the basic Prewitt operator, move on to the Sobel operator, then the Laplacian operator, before closing with the canny edge detection algorithm.

The Prewitt operator was developed in 1970 by John Prewitt^[6]. It is one of the more basic forms of edge detection, and involves the convolution of a pure first derivative operator on an image. There are two operators - one in the x direction and in the y direction. The matrix in the x direction is shown below, the y direction matrix would be the transpose of this one. As you can see, when the convolution is executed, pixels in the x or y directions will be subtracted to their respective opposite. This will give you the difference in intensity at each pixel. This is essentially a pure discrete representation of the gradient vector of an image.

Prewitt Operator in the X direction

While the Prewitt operator will give you a map of all the differences in intensity, it does not handle noise very well. What this means is that the Prewitt operator is prone to returning false edges resulting in an inaccurate map. To avoid this issue, the Sobel-Feldman operator is commonly used instead. Researchers Irwin Sobel, and Gary Feldman introduced this operator as part of a talk in a larger convention in 1968^[7]. Instead of taking the pure derivative of the pixels, Sobel weighted the neighbors to the East and West, and North and South directions by a factor of 2. As a result, the intensities of the pixels along the corners are not as important in the final result. Another way of thinking of this is that we are blurring the pixels in the corner while still taking them into account. As a result, noise is reduced and a more accurate edge map can be developed. Another visual difference is that because we are adding weights to the values, the resulting intensities will be greater than the Prewitt - meaning that the result will be brighter.

Sobel Operator in the X direction

\[ \vec{\nabla}L(x, y) = \frac{\partial^2 L}{\partial x^2} + \frac{\partial^2 L}{\partial y^2} \] Shown above is the equation that represents the continuous second order derivative used as the basis for the Laplacian operator. The Laplacian operator uses second order derivatives to model or analyze some phenomenon. Although there have been many interesting applications of the Laplacian operator, the exact details of how it works and can be used have unfortunately eluded this student. Based on the original Laplace operator developed by Pierre-Simon de Laplace, the discrete matrix representation can be used to find edges in an image^[3]. However, because this operator essentially detects changes in the changes of the image, it has the downside of being very sensitive to noise. To avoid this, the image is commonly blurred before processing to avoid returning unnecessary edges.

Laplacian Operator

The Canny Edge Detection algorithm builds on the Sobel operator to produce a better map of edges. Once an initial map of edges using the Sobel operator is formed, the edges are thinned through a non-maximum suppression algorithm. This algorithm only keeps the strongest edge and ignores all other weaker edges. Then through double thresholding, edges that are weaker than the lower threshold are filtered out while edges that are stronger than the higher threshold are highlighted. Finally, the edges that lie between the low and high thresholds are either filtered out or highlighted based on its surrounding pixels through hysteresis thresholding. In short, if a weak edge is connected to a strong edge then it is highlighted, and ignored otherwise.^[3] The final result is a clear map of edges. Although this method was developed over 30 years age in 1986 by John F. Canny, it is still one of the more commonly used edge detection algorithms today^[8].

Calculating the edges of an image is an important first step in many different applications of computer vision. The map of edges often carries with them much important and useful data which can be used to classify and describe the image. This feature of the edges is often taken advantage of to build much more complex and helpful algorithms and technologies. One particularly common application of this can be found in object recognition and detection.

Object recognition and detection is a popular field of computer vision that has seen much use in many different fields. For example, many digital cameras use basic face detection algorithms to focus on and track faces when taking a picture. Another example can be seen in businesses like Tesla, which are experimenting on using object detection and recognition to develop self driving cars. Often, a major step in these algorithms is to generate the edges in the image among other features. Then this map of edges is compared with specific points found in hundreds or sometimes thousands of edges of known images. By comparing data such as the angle and magnitude of the edges with a database, computers can classify an image as an object within a specific confidence level^[10]. To handle this part of the computation, some type of neural network or machine learning algorithm is often used. Using only the edges will allow objects to be recognized despite having different lighting, or color. However, it is also important to check different transformations and sizes of the objects^[9].

Go here for a sample implementation
Go here to look at the code