Background

Boundary detection is one of the more challenging tasks in computer vision. In order to infer anything about an object, it is necessary to know where the object ends and another object begins. Unfortunately, it's very difficult to determine boundaries from one image. This page describes an attempt to perform boundary detection, based on a method of based on a paper by Arbelaez, Maire, Fowlkes, and Malik. My implementation (pb-lite) is a simplified version of their method. Results are evaluated on the Berkeley Segmentation Data Set 500 (BSDS500), which relies on human-determined boundaries for testing accuracy. Details on the assignment can be found here.

Method

Whereas classical edge detection algorithms like Sobel and Canny edge detection only take into account changes in intensity, pb-lite can measure texture gradients as well. To determine an image's texture gradient, a series of filters are applied to the image. We perform clustering using k-means on the filter responses to assign each pixel to a texton. This allows us to quantify the texture of the image at a given pixel. In my implementation, my filters consisted of 16 oriented derivate Gaussian filters (8 orientations, 2 scales) and 1 difference of Gaussians, just as the original paper described. Adding the single DoG filter had a negligible effect on my result. For assigning texture textons, I used 64 clusters.

Once we have texture textons assigned, we can detect gradients for texture, brightness, and color. To determine the gradients, I filtered the image with pairs of half-disc masks (8 orientations, 3 scales for each pair), which is much faster than looping over each pixel of the image. The gradient is then determined by taking the chi-square distance from each filter response over a series of bins. In this formula, g represents the image filtered with the left-half disc image and h the image filtered with the right-half disc.

This process generates an n x m x i matrix, where n and m are the image dimensions and i is the number of disc filter pairs. To obtain the texture gradient, the texture texton map is used for the chi-square distance with 64 bins. For the brightness gradient, a grayscale version of the image is scaled to a [0, 255] range for intensity and the gradient is calculated for 33 bins evenly distributed over that range. I implemented a color gradient by performing the gradient for each color channel (intensities scaled to [0, 255] with 33 bins, just like brightness). To combine this values into one n x m x i matrix for use in the next step, I took the mean of the sum of the 3 resulting matrices.

To combine all these values into one awesome boundary detector, I used the mean of the feature vectors for each metric (texture, brightness, and color) and performed element-wise multiplication with the Canny filter of the image. I experimented with giving each metric higher weight, but no gradient metric seemed to perform better than another. I am suspicious that I did not test this correctly though.

Evaluation

pb-lite is evaluated against several baseline methods, gPb (the Berkeley group's top-of-the line detection algorithm on which this method was based), and the human-annotated examples of BSDS500. I ran my implementation against 200 images in the test-set. The precision-recall curve below shows my result in comparison to the others.

As you can see, my pb-lite bests Canny but is nowhere near as accurate as gPb. My F-scores for the precision-recall curve, in addition to the scores for Sobel and Canny edge detection, are below:

Images

Each boundary detection algorithm determines whether or not a pixel in an image is part of a boundary. The resulting assignments make for a clear visualization of the boundaries in the image. You can view the results of each detection method below for all 200 images tested. 20 are displayed at a time and you can page forward and back using the links. Click on an image to view a full-size version.