Ben Freudberg

CSCI1430

Project 2

Introduction

            The goal of this project was to implement a method of refining the Sobel and Canny edge detection algorithms.  The method involved looking at texture and brightness gradients across the image and using the results to modify the output of Sobel and Canny edge finding filters.

Texture Filters

            The first step in determining the gradient of the texture across the image was to develop a set of filters that allow us to pull out the effects of different textons across the image. The filter bank below looks for textons that represent a shift in any of 16 orientations (more orientations would be easy to implement, but would increase computation time significantly. Each set has multiple scales so that both abrupt and gradual changes in the picture are represented.

Creating histogram with k-means and computing gradients

            After we have run the filters on the image, we have a number of output images (matrices) equal to the number of filters. The value at each pixel of a given output image represents the strength of the influence of the particular texton being tested by that filter. We can then run a k-means algorithm over the set of images so that we may categorize each pixel into one of k (64 for us) categories based on the influence of each of the different filters. Now that we have classified each pixel as belonging to one of k possible textures, we may compute the gradients in many different directions across the texture map in order to find edges. The gradients are computed by running half disk pair filters at multiple orientations on the texture map image. The result of this operation is a set of images, one for each half disk pair orientation. The gradient filter bank is shown below.

            In order to compute the gradients, the filtered results must be organized. A set of matrices is created, one for each bin. If the value of a pixel in the texture map (or brightness or color maps) falls within the current bin range, then that value in the new matrix is set to “1”, otherwise the value is a “0”.  The gradients of these maps are calculated by filtering with pairs of half-disks and then finding the chi-squared value of the two results (one from each half-disk). The gradients of brightness are also computed and integrated into the final solution. The brightness of each pixel is categorized into one of 16 bins. After the pixels have been categorized, the gradients of the map are computed.

Modifying Canny with our texture, brightness and color gradients

            Once all gradients have been computed, they are averaged together. The gradients in all directions at each pixel for each filter and for brightness are summed together and divided by the total number of contributing gradients. This mean value represents the strength of the edginess of any particular pixel. By multiplying the 2d matrix representing the edginess at each pixel by the output of the Canny edge detector we can reduce false positives and refine true positives to yield a more precise final image.

Extra Credit

I implemented several features to improve the performance of this edge detector. I added an extra set of filters to look for textons described by points that are different from their surroundings. I also tried implementing a set of filters that compared the center to either side in one direction. This set had 16 orientations as well, but the extra computation time proved to not be worth the negligible performance improvement.  The other feature I implemented was the use of the image’s color to assist in edge finding. By running Kmeans on the color image, we can assign each pixel to one of 16 color bins. The gradients of this color map can then be calculated as they were for the texture and brightness maps. The color gradients are included when computing the average gradient at each pixel.

Conclusion

After implementing all of these features to refine the Canny output, I was able to achieve an F-score of 0.60, beating Sobel at 0.45 and Canny at 0.58. The graph below is a visualization of the quality of my results vs that of the other methods.

Example Results

Original Image

Canny

Sobel

My PB results