CS6640 - Project 5 | James Fishbaugh

The Marr-Hildreth edge detection algorithm involves taking the convolution of the Laplacian of a Gaussian with the image. The result image represents a blurred second derivative of the original image. In this image, edges occur at zero crossings. For better results, we also calculate the gradient magnitude of the original image and assign a threshold to it. For example, we for pixel i,j that is a zero crossing in the Laplacian image, we only accept it as an edge if the gradient magnitude at that location is above our threshold.

First I implemented a method that constructs a Gaussian kernel of a given sigma, called create_gaussian. Next, I implemented a method to determine zero crossings in an image, called find_zero_crossings. The method uses a four pixel neighborhood to look for zero crossings and uses nearest neighbor interpolation to determine which pixel has the edge. The result of this function is a binary image where white represents an edge. The driver of this whole process is called marr_hildreth.

In order to get better results, it is a good idea to filter the original image before detecting edges. However, many linear filters cause a lot of blurring around edges. We ideally want to eliminate noise while preserving edges. A median filter does a good job of preserving edges. I implemented a median filter in a method called median_filter.

With the previously mentioned pieces in place, they can be used in an edge detection pipeline. There are several parameters available to tweak to produce the best results for that particular image. For example, we could first do some contrast adjustment of the input image. Then we could apply a median filter to reduce noise. Then we could run the Marr-Hildreth algorithm and provide a sigma for the Gaussian and a threshold for the gradient magnitude. We may find that this didn't produce great results, perhaps the median filter blurred the image too much or we needed a higher value for sigma. The pipeline gives you a lot of flexibility in finding the desired edges.

First I tested the edge detection pipeline on a synthetic image of dark shapes on a light background. This should be about the easiest possible scenario; an image with very strong edges. Figure 1 shows the original image and the edges extracted using the edge detection pipeline. For this simple example, no median filter was needed. Also, there is no need for the Gaussian blurring and threshold on gradient magnitude. The original image has no noise and very strong edges.

I also wanted to test the effect of noise. I wrote a function called add_noise. It simply adds shot noise to a percentage of pixels in the image. Figure 2 shows the result of adding ten percent noise to the synthetic example.

Figure 3 represents an attempt to detect edges from the noisy image without using a median filter. The image on the left used a very low sigma and no threshold on gradient magnitude and as a result shows a high number of spurious edges. The figure on the right represents my best effort to extract only the shapes by adjusting sigma and the threshold. The extracted shapes have been distorted slighting and false edges still remain.

Figure 4 shows the edges extracted from the noisy image by first using a median filter with a 5x5 neighborhood to reduce noise. The image on the left represents a low value of sigma and no thresholding. There are no real false edges visable, but the shapes have been distored. The image on the right uses a larger value of sigma and a small threshold and shows better edges. This example shows the benefit of using a median filter as a preprocessing step.

The following example, shown in figure 5, is an image from the slides. It turned out to be a pretty easy image to extract edges from. The main problem was the highlight on the spoon showing up as an edge. Preprocessing with a 3x3 median filter was performed before using Marr-Hildreth.

The final example, shown in figure 6 turned out to be somewhat problematic. At first glance, it seems the edges would be easy to extract. However, when reduced to grayscale, there is low contrast around the interesting features in the flag. I had to run contrast limited histogram equalization with a window size of 10x10 and a clip percenage of 0.30 as a preprocessing stage. I then used a median filter with a 3x3 neighborhood to reduce artifacts from histogram equalization.

The hough transform takes transforms the input image to an accumulator space. The dimension of the accumulator space is dependent on the numbers of degrees of freedom in transformation. For this project, we are tasked with finding circles of a given radius. The equation of a circle is (x-a)^2 + (x-b)^ = r^2. Since we know r, there are two degrees of freedom in this equation, a and b. Therefore our accumulator space is 2 dimension.

First we solve the above equation for a. Then for every pixel (i,j) in the image we loop over all possible values of b in our discretization and calculate a, using i and j as x and y, respectively. Then we increment our accumulator at location (a,b). I implemented this in a function called hough_circle_finder.

Figure 7 shows a synthetic example where we want to detect the smallest circles, which have a radius of 20 pixels. The image on the left is the accumulator space. Peaks in this space correspond to the centers of circles. We must determine a way to find all the peaks reliably.

Next, I convolved the accumulator image with a Gaussian kernel with sigma = 2.5. The blurred version of the accumulator space is shown in figure 8. Now the peaks are larger and easier to find. However, I need to determine exact pixel where the center of the circle belongs.

In order to find the exact centers, first the accumulator image is thresholded to be between a min and max value. The max value is determined from the largest value in the accumulator. The min value is calculated based on a user supplied percentage of the max value. Now there are small blobs denoting image centers. The final step is a connected component analysis where the centroids of all blobs are calculated. The centroids become the final location of all circles.

Finally, with the centers of circles found, they can be drawn over the original image. Figure 10 shows all the small circles in the example were detected.

An example where automatic circle detection would be important is in manufacturing. As a quality control step, a product could be verified by ensuring the proper number of circles, distribution, etc. Figure 11 shows an example of a surface mount where we are interested in finding the solder beads and any voids present inside the beads.

Figure 12 represents my best efforts in detecting the large beads. First, the image was preprocessed using a 3x3 median filter. Then an edge image was produced using Marr-Hildreth with sigma=6.2 and a threshold of 2. The the hough circle finder was run using a sigma=2.5, a threshold percent of 10%, and looking for circles of a radius 35. I was unable to find circles who centers were off the image or the circle on the bottom middle which is obstructed by other things.

My attempt to extract the voids from the surface mount are shown in figure 13. As before, the image was preprocessed using a 3x3 median filter. Then an edge image was produced using Marr-Hildreth with sigma=12.0 and a threshold of 0.7. The the hough circle finder was run using a sigma=2.5, a threshold percent of 10%, and looking for circles of a radius 10. The result are positive, the three voids of radius 10 were detected.

Prove that if we know the radius of a circle and we blur the accumulator space (which consists of all translations) resulting from an edge detector, that this space gives the same result as if we had convolved a blurred version of a circle with the edge image.

Let A(i,j) be the accumulator space. A matrix of all possible positions of a circle with a given radius, obtained from an edge image.
Let G(i,j) be a discrete 2D Gaussian kernel (used for blurring).
Let E(i,j) be the edge image. It will have 1's denoting edges and 0's otherwise.
Let C(i,j) be a circle of a given radius.

Now we must prove that

We know that A consists of every possible placement of a circle C, obtained from the edge image E. We also know the edge image E is 0 where there isn't an edge and 1 where there is an edge. Therefore, we can write A as a 2D discrete correlation. Furthermore, since a circle is symmetric, it can be written as a 2D discrete convolution (there is no difference when flipping the circle).

	Name:		James Fishbaugh
	Email:		jfishbau@cs.utah.edu
	CS6640 - Project 5
	Preprocessing and Edge Detection Marr-Hildreth The Marr-Hildreth edge detection algorithm involves taking the convolution of the Laplacian of a Gaussian with the image. The result image represents a blurred second derivative of the original image. In this image, edges occur at zero crossings. For better results, we also calculate the gradient magnitude of the original image and assign a threshold to it. For example, we for pixel i,j that is a zero crossing in the Laplacian image, we only accept it as an edge if the gradient magnitude at that location is above our threshold. First I implemented a method that constructs a Gaussian kernel of a given sigma, called create_gaussian. Next, I implemented a method to determine zero crossings in an image, called find_zero_crossings. The method uses a four pixel neighborhood to look for zero crossings and uses nearest neighbor interpolation to determine which pixel has the edge. The result of this function is a binary image where white represents an edge. The driver of this whole process is called marr_hildreth. Median Filter In order to get better results, it is a good idea to filter the original image before detecting edges. However, many linear filters cause a lot of blurring around edges. We ideally want to eliminate noise while preserving edges. A median filter does a good job of preserving edges. I implemented a median filter in a method called median_filter. Edge Detection Pipeline With the previously mentioned pieces in place, they can be used in an edge detection pipeline. There are several parameters available to tweak to produce the best results for that particular image. For example, we could first do some contrast adjustment of the input image. Then we could apply a median filter to reduce noise. Then we could run the Marr-Hildreth algorithm and provide a sigma for the Gaussian and a threshold for the gradient magnitude. We may find that this didn't produce great results, perhaps the median filter blurred the image too much or we needed a higher value for sigma. The pipeline gives you a lot of flexibility in finding the desired edges. Experiments First I tested the edge detection pipeline on a synthetic image of dark shapes on a light background. This should be about the easiest possible scenario; an image with very strong edges. Figure 1 shows the original image and the edges extracted using the edge detection pipeline. For this simple example, no median filter was needed. Also, there is no need for the Gaussian blurring and threshold on gradient magnitude. The original image has no noise and very strong edges. Figure 1: Left) Original image. Right) Final edge image (sigma=1.1, threshold=0). I also wanted to test the effect of noise. I wrote a function called add_noise. It simply adds shot noise to a percentage of pixels in the image. Figure 2 shows the result of adding ten percent noise to the synthetic example. Figure 2: Original image from figure 1 with 10% noise. Figure 3 represents an attempt to detect edges from the noisy image without using a median filter. The image on the left used a very low sigma and no threshold on gradient magnitude and as a result shows a high number of spurious edges. The figure on the right represents my best effort to extract only the shapes by adjusting sigma and the threshold. The extracted shapes have been distorted slighting and false edges still remain. Figure 3: Left) Edge image with false edges (sigma=1.1, threshold=0). Right) Edge image with less false edges (sigma=4.0, threshold=70). Figure 4 shows the edges extracted from the noisy image by first using a median filter with a 5x5 neighborhood to reduce noise. The image on the left represents a low value of sigma and no thresholding. There are no real false edges visable, but the shapes have been distored. The image on the right uses a larger value of sigma and a small threshold and shows better edges. This example shows the benefit of using a median filter as a preprocessing step. Figure 4: Left) Edge image with distorted objects (sigma=1.1, threshold=0). Right) A better edge image (sigma=2.0, threshold=10). The following example, shown in figure 5, is an image from the slides. It turned out to be a pretty easy image to extract edges from. The main problem was the highlight on the spoon showing up as an edge. Preprocessing with a 3x3 median filter was performed before using Marr-Hildreth. Figure 5: Left) Original image. Right) Resulting edge image (sigma=2.5, threshold=10). The final example, shown in figure 6 turned out to be somewhat problematic. At first glance, it seems the edges would be easy to extract. However, when reduced to grayscale, there is low contrast around the interesting features in the flag. I had to run contrast limited histogram equalization with a window size of 10x10 and a clip percenage of 0.30 as a preprocessing stage. I then used a median filter with a 3x3 neighborhood to reduce artifacts from histogram equalization. Figure 6: Left) Original image. Right) Resulting edge image (sigma=3.5, threshold=10). Circle Detection Hough Transform The hough transform takes transforms the input image to an accumulator space. The dimension of the accumulator space is dependent on the numbers of degrees of freedom in transformation. For this project, we are tasked with finding circles of a given radius. The equation of a circle is (x-a)^2 + (x-b)^ = r^2. Since we know r, there are two degrees of freedom in this equation, a and b. Therefore our accumulator space is 2 dimension. First we solve the above equation for a. Then for every pixel (i,j) in the image we loop over all possible values of b in our discretization and calculate a, using i and j as x and y, respectively. Then we increment our accumulator at location (a,b). I implemented this in a function called hough_circle_finder. Figure 7 shows a synthetic example where we want to detect the smallest circles, which have a radius of 20 pixels. The image on the left is the accumulator space. Peaks in this space correspond to the centers of circles. We must determine a way to find all the peaks reliably. Figure 7: Left) Original image. Right) Accumulator space. Next, I convolved the accumulator image with a Gaussian kernel with sigma = 2.5. The blurred version of the accumulator space is shown in figure 8. Now the peaks are larger and easier to find. However, I need to determine exact pixel where the center of the circle belongs. Figure 8: Accumulator space blurred with a Gaussian (sigma=2.5). In order to find the exact centers, first the accumulator image is thresholded to be between a min and max value. The max value is determined from the largest value in the accumulator. The min value is calculated based on a user supplied percentage of the max value. Now there are small blobs denoting image centers. The final step is a connected component analysis where the centroids of all blobs are calculated. The centroids become the final location of all circles. Figure 9: Thresholded image of figure 8. Finally, with the centers of circles found, they can be drawn over the original image. Figure 10 shows all the small circles in the example were detected. Figure 10: Small circles detected. Detecting Solder Beads and Voids An example where automatic circle detection would be important is in manufacturing. As a quality control step, a product could be verified by ensuring the proper number of circles, distribution, etc. Figure 11 shows an example of a surface mount where we are interested in finding the solder beads and any voids present inside the beads. Figure 11: Surface mount with dark circles representing solder beads and smaller white circles representing voids. Figure 12 represents my best efforts in detecting the large beads. First, the image was preprocessed using a 3x3 median filter. Then an edge image was produced using Marr-Hildreth with sigma=6.2 and a threshold of 2. The the hough circle finder was run using a sigma=2.5, a threshold percent of 10%, and looking for circles of a radius 35. I was unable to find circles who centers were off the image or the circle on the bottom middle which is obstructed by other things. Figure 12: Top Left) Edge image. Top Right) Accumulator image. Bottom) Extracted beads. My attempt to extract the voids from the surface mount are shown in figure 13. As before, the image was preprocessed using a 3x3 median filter. Then an edge image was produced using Marr-Hildreth with sigma=12.0 and a threshold of 0.7. The the hough circle finder was run using a sigma=2.5, a threshold percent of 10%, and looking for circles of a radius 10. The result are positive, the three voids of radius 10 were detected. Figure 13: Top Left) Edge image. Top Right) Accumulator image. Bottom) Extracted voids. Mathematical Proof Prove that if we know the radius of a circle and we blur the accumulator space (which consists of all translations) resulting from an edge detector, that this space gives the same result as if we had convolved a blurred version of a circle with the edge image. Let A(i,j) be the accumulator space. A matrix of all possible positions of a circle with a given radius, obtained from an edge image. Let G(i,j) be a discrete 2D Gaussian kernel (used for blurring). Let E(i,j) be the edge image. It will have 1's denoting edges and 0's otherwise. Let C(i,j) be a circle of a given radius. Now we must prove that We know that A consists of every possible placement of a circle C, obtained from the edge image E. We also know the edge image E is 0 where there isn't an edge and 1 where there is an edge. Therefore, we can write A as a 2D discrete correlation. Furthermore, since a circle is symmetric, it can be written as a 2D discrete convolution (there is no difference when flipping the circle). Therefore, A will equal 0 everyplace there was no edge in the original image and will equal the value of the circle everywhere there was an edge. Now we can write the left hand side of the equation as Finally, because of the associativity and commutative properties of convolution, we can write the left hand side of the equation as Therefore we have proved that blurring the accumulator space resulting from an edge detector is equivalent to convolving a blurred version of a circle with the edge image.
	Last Updated: May 01, 2009