Actual image
Human boundaries #1
Human boundaries #2
The objective of this assignment was to create an algorithm to correctly detect boundaries in an image.
Detecting boundaries might sound easy, but it is actually an extremely difficult problem. In some ways, the problem is ill posed - even humans don't always agree on what a boundary is:
It is also hard to decide when a group of edges becomes a texture:
The pB Lite algorithm detects boundaries by looking for aggregate changes in texture and brightness. To find these changes, we combine the "texture gradient", "brightness gradient" and the canny edge detector. There are five steps to the algorithm: generating a filter bank, creating a set of paired half disk masks, clustering filter responses into a texture map, calculating texture and brightness gradients using the set of masks and combining features.
To generate a filter bank, we convolve Sobel and Gaussian filters. Then we rotate the result at different orientations and scales.
A set of half-disk masks were generated by creating a disk in Matlab, cutting the disk in half and scaling/rotating the disks. (Read the 'Calculating Gradients' section to understand why the masks were created.)
Next, we apply each filter in our filter bank to our image. We cluster the filter responses using k-means. The resulting clusters form a texton map.
The gradient measures how much a function is changing in a specified direction. However, the functions we are calculating the gradient for are over discrete values. To measure how large the change from pixel to pixel is, we can compare distributions using the Chi-squared test.
To speed up the process of choosing distributions, we can filter the image once with both disks in each half disk pair. Then we can compare the distributions of pixels and get a measure of how large the change in the direction of the half disk pair is.
Results of texture gradients for different mask orientations / scales are shown in the table below. Note how larger radii detect areas with more dynamic texture distributions.
| radii = 5 | radii = 10 | radii = 20 | |
| 22.5 degrees |
|
|
|
| 67.5 degrees |
|
|
|
| 157.5 degrees |
|
|
|
The end result is a stack of directional gradients at different scales. It would have been interesting to experiment with different weights for specific masks, but given the time constraints I just averaged all the results together.
In addition to the texture gradient, the brightness gradient is also useful for detecting edges.
| radii = 5 | radii = 10 | radii = 20 | |
| 22.5 degrees |
|
|
|
| 67.5 degrees |
|
|
|
| 157.5 degrees |
|
|
|
I also averaged the directional brightness gradients together.
Finally, we can combine the averaged texture / brightness gradients and a baseline. I chose to multiply the canny baseline by the mean of the texture and brightness gradients.
As you can see, the implementation clearly beats the baseline. (This is on the set of ten images.) The F score is .59. Unfortunately, it takes a very long time to run.
| Original | Canny | pB Lite |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |