Original Image Sobel Baseline Canny Baseline pB-Lite

Project Description

In this project we sought to improve on the boundary detection capabilities of Canny and Sobel baseline detectors using the probability of boundary (pB) method described in Arbelaez, Maire, Fowlkes, and Malik. TPAMI 2011 (pdf). The well established Canny and Sobel methods use intensity discontinuities to indicate boundary locations, while the pB method also investigates texture and color gradients. This allows the pB method to suppress false positives given by the other methods.

Multi-scale Filter Banks and Masks

The pB pipeline begins with creating a filter bank. I created a set of filters 16 orientations and 2 scales. The filters are approximating the derivative of a Gaussian at a given orientation and scale. These filters will be used to encode the texture properties of a input image.

I also generated a bank of half-disc masks (8 orientations, 3 scales). These will be used later in the pipeline to calculate the texture, brightness, and color gradients across the input image.

Computing Gradients

The objective of the pB pipeline is to calculate a pB score for each pixel in an image. The pB score is calculated using the gradient features from the texton map, brightness, and color values of the input image. The gradients are calculated by convolving the half-disc masks with each of the feature map versions of the input image. The pixel values are first binned into a predetermined set of bins.

Looping over each pixel location was avoided by assigning bin values to each pixel, and then using the half-disc masks to filter each version of the image where only the pixels with a certain bin value had value 1 and all other locations had value 0. By looping through all of the bin values and computing this filter operation, the histogram of gradients was computed more quickly.

Each pair of half-disc masks were convolved with one of the feature map versions of the image. This resulted in two histogram of gradients matrices. Because each pair of half-disc masks were the opposite of each other, the distance between their matrices would give an impression of where the strong gradients in the image were. If the distance between the upper and lower disc histograms was great, then that pixel was the location of a gradient. If not, there was probably not a gradient there. I used the chi-squared distance to calculate the gradient strength.

Texton Map and Gradients

To determine the texture gradient, a texton map had to be made for the image. Two examples of texton maps are shown below. I calculated the texton map by convolving each filter in the filterbank with the input image. This resulted in a 3D matrix where every pixel location was a 32 dimensional vector of filter convolution results. I used the kmeansML.m script to cluster the vectors at each pixel location into one of 64 clusters. The cluster value for a pixel was its 'texton id'. The texton maps below are visualizations of the texton id distributions for the example images.

The texture gradients were then computed using the method described above on the texton map.

Brightness Gradients

The brightness gradients were calculated from a map of the image's intensity values at each pixel site. I used 128 bins evenly spaced from 0 - 256.

Color Gradients

To compute the color gradients, I first converted the image into CIE Lab color space. I then binned each pixel value into one of two bins depending on whether the a color or the b color was greater. This was a very simplistic scheme, but below I can show that it made a small increase in performance over simply using texton and brightness gradients.

Mean Feature Strength

To calculate the pB score, I averaged the values of the texton, brightness, and color gradients. A visualization of the resultant feature strength is shown below.

Original Image Texton Map Mean Feature Strength

Calculating pB Score

I calculated the final pB-lite score by taking an element-wise product of the Canny baseline and the mean feature strength. An example of this process is shown below.

Canny Baseline .* Mean Feature Strength = pB-Lite

Comparisons with Baseline Methods

When I tested the pB-lite images against the other baselines using only the texton and brightness gradients, I had slightly worse performance than the Canny baseline on the 10 images sub-set. When I also used the color gradient, the performance was about equal or slightly better.

pB-Lite Performance with only tg and bg (10 images used) pB-Lite Performance with tg, bg, and color gradient (10 images used)

Unfortunately, when I tested on the 200 image test set, my pB-Lite did obviously worse than the Canny baseline. If I were to try this again, I would increase the size of the filter bank and experiment with different shaped filters. I would also use the color space more intelligently.

pB-Lite Performance with tg, bg, and color gradient (200 images used)

Appendix: Using Integral Images to Compute Gradients

In order to speed up testing, I attempted to use integral images to compute the gradients more quickly. I followed the procedure outlined in the appendix to Arbelaez, Maire, Fowlkes, and Malik. TPAMI 2011 (pdf). Unfortunately, my implementation was not any faster because of the time consumed by the imrotate function. I was not sure how to speed up that function other than to use a MEX implementation, which I did not have time to investigate. Pre-rotating the integral images was another idea, but since each image needed to be rotated at a different angle I wasn't sure how to parallelize that operation.

%% loop over binvalues (and loop over each mask pair)
(...looping over orientations, radii, binvalues...)
tmp = zeros(size(img));
%turn img into a binary matrix where 1's indicate the current binvalue
tmp(img(:)<=binvalues(b) & img(:)>prev_binval) = 1;
% gi = conv2(tmp, masks{o,r,1}, 'same');
% hi = conv2(tmp, masks{o,r,2}, 'same');
%Using integral image to calculate gradients
int_tmp = cumsum(cumsum(tmp,2));
rotate = imrotate(int_tmp,mask_orients(o),'nearest', 'crop');
gi = zeros(size(rotate));
hi = zeros(size(rotate));

gi(:,:) = rotate(max(1, (1:size(gi,1))-mask_radii(r)), max(1,(1:size(gi,2))-mask_radii(r)))+...
rotate(min(size(gi,1),(1:size(gi,1))+mask_radii(r)), (1:size(gi,2)))-...
rotate(min(size(gi,1),(1:size(gi,1))+mask_radii(r)), max(1,(1:size(gi,2))-mask_radii(r)))-...
rotate(max(1, (1:size(gi,1))-mask_radii(r)), (1:size(gi,2)));

hi(:,:) = rotate(max(1, (1:size(hi,1))-mask_radii(r)), (1:size(gi,2)))+...
rotate(min(size(hi,1),(1:size(hi,1))+mask_radii(r)), min(size(hi,2),(1:size(hi,2))+mask_radii(r)))-...
rotate(min(size(hi,1),(1:size(hi,1))+mask_radii(r)), (1:size(gi,2)))-...
rotate(max(1, (1:size(gi,1))-mask_radii(r)), min(size(hi,2),(1:size(hi,2))+mask_radii(r)));
gi = imrotate(gi, -mask_orients(o),'nearest', 'crop');
hi = imrotate(hi, -mask_orients(o),'nearest', 'crop');

%aggregate chi-sqr dist (a sum over bins)
gradient(:,:,o*size(mask_radii,2)-(size(mask_radii,2)-r)) = ...
gradient(:,:,o*size(mask_radii,2)-(size(mask_radii,2)-r)) + ...
0.5*(gi-hi).^2./(gi+hi+eps);