CS 143 Project 2

pb-lite: Boundary Detection

Will Allen (weallen)

Methods

For this project, we implemented a simplified version of the boundary detection algorithm of Arbelaez, Maire, Fowles, and Malik. TPAMI, 2011. Our version used color, texture, and brightness features, combined with a baseline Canny detector, to achieve good performance.

Algorithm

There were two steps to the algorithm.

Step 1:

First, we generated a series of filters at different scales and orientations, making a filter bank (left). We chose to use two different scales, sigma = 1 and sigma = 2, and 16 orientations (shown in order of increasing angle of orientation). For each scale and orientation, we created one oriented gaussian. For extra credit, we also added one Laplacian of gaussian filter at sigma, one Laplacian of gaussian filter at 3*sigma, and one gaussian at sigma, for each sigma (final row). We then generated a series of half-circular masks at different scales and orientations (right).

Step 2:

We used four features for edge detection: two channels of color, brightness, and texture. First, We converted each image to grayscale, and filtered that image with each of the filters in our bank, to obtain a response vector at each pixel in the image. Treating each response vector as independent, we used k-means clustering to to classify each pixel into one of 64 categories. The classification of each pixel was used as the texton id for that pixel.

Next, we converted each image into the LAB colorspace, and used that representation to compute brightness and two color gradients (a and b). The brightness or color value at each pixel was discretized into the range 1-255. (The color gradients were extra credit.)

For each feature, used the image masks to compute a multidimensional histogram in the right and left half circle centered a each pixel, in different orientations. We then used the chi-square distance to determine how different these the right and left histograms are at each pixel, resulting in a distance value representing the gradient at each pixel for each feature.

Finally, we averaged the per-pixel gradient for each feature, and multiplied that value with the Canny edge detection response at that pixel, to get a per-pixel boundary score. This final value was used to do non-maximum suppression.

Results

Our algorithm performed better than the baseline Canny and Sobel boundary detectors on the BSDS 500 set. Adding color features and extra filters significantly improved our performance:

ROC with color features and extra filters	ROC without color features and extra filters

The quantitative results show that our algorithm always outperformed the baseline Canny and Sobel detectors, as measured by F-score (results shown with color features and extra filters).

Sobel:	ODS: F( 0.38, 0.55 ) = 0.45 [th = 0.09]	OIS: F( 0.38, 0.55 ) = 0.45	Area_PR = 0.21
Canny:	ODS: F( 0.66, 0.51 ) = 0.58 [th = 0.15]	OIS: F( 0.70, 0.50 ) = 0.59	Area_PR = 0.50
Pb-Lite:	ODS: F( 0.64, 0.57 ) = 0.60 [th = 0.10]	OIS: F( 0.64, 0.57 ) = 0.60	Area_PR = 0.53

Some example segmentations are shown below: