Introduction

The task given by this assignment is to develop a simplified of version of pb, a boundary detection algorithm from Berkeley. Our boundary detector will be a modification of the recent work of Arbelaez, Maire, Fowlkes, and Malik. Evaluation is carried out against human annotations (ground truth) from a subset of the Berkeley Segmentation Data Set 500 (BSDS500)

Approach

Texture gradient

The key idea of pb-lite is to take texture gradients into consideration, while classical texture edge detection only looks at intensity gradients. In order to measure how quickly the texture is changing at any given point, the algorithm filters the input image with a set of different filters. This gives us a X-dimensional feature vector at each pixel (where X is the number of filters we are using). The algorithm will then simplify this representation by replacing each feature vector with a discrete texton id by clustering the filter responses (using kmeans and K=64 clusters). The local texton gradient is computed by comparing the distributions of left / right half-disc pairs (of different orientations and scales) centered at a pixel. If the distribution of texton ids under the left and right half-disc are similar the gradient will be small and large if the distribution is dissimilar. The algorithm uses chi-square distance to compare the two distributions.

Brightness gradient

To obtain the brightness gradient, the algorithm first converts to image to gray scale and then bins each pixel into one of 32 different brightness values. To compare the local distributions of brightness values at each pixel, we use the same approach as described in Texture gradient, using left and right half-discs and chi-square distance.

Color gradient

The color gradient is calculated similar to the Texture gradient. The algorithm clusters the colors of an image into K=64 clusters by applying kmeans. The difference between local distributions of color values gets again calculated by using left and right half-discs and chi-square distance.

Integral images

The appendix in Arbelaez et al. 2011 mentions the use uf integral images (or summed area tables) to quickly compute local histograms. In a summed area table (I) the total energy of an axis-aligned rectangle can be computed with the following formula:
I(upper-left-point) + I(lower-right-point) - I(upper-right-point) - I(lower-left-point)
The described approach makes use of this fact and precomputes summed area tables for an image in different orientations and then approximates the left and right half-disks with rectangles.

Results

Discussion

My implementation of integral images has not provided any speed-up (it is even slower as the initial approach). The final algorithm does not make use of them. The enhanced filter bank has not improved the benchmark results, it performed slightly worst. The addition of the color gradient measure did not seem to have a big impact on the benchmark result. The presented graphs are the results of the benchmark using a 10 image subset of the total test set.