Image Segmentation Using Local Variation   

Pedro F. Felzenszwalb
Daniel P. Huttenlocher

Overview:

The goal of image segmentation is to divide an image into objects. In reality we solve a slightly different problem: we try to figure out how to split the image into patches (we call them blobs) that are perceptually different to each other. Although blobs don't correspond exactly to the objects in the world we expect a high correlation between them. Blobs cary information such as shape and color distribution which are useful for complicated image understanding tasks such as object recognition and tracking. On the other hand, the common representation of images as a bunch of pixels makes very little information explicit.

Framework:

We treat the problem of image segmentation as a graph partitioning problem. Define a graph H=(V,E) in which each node in V corresponds to an image pixel and there is an edge in E connecting every pair of pixels. The weight of the edge is given by the difference in intensity between the two pixels it connects if the pixels are neighbors in the image domain and it is infinity otherwise. A partition of this graph into disjoint connected components corresponds to a segmentation of the image into disjoint blobs. Given a measure of similarity between two disjoint components and a measure of the internal similarity of a component (how similar the pixels of the components are too each other) we define the following: A partition is over-segmented (too many components) if the similarity between two disjoint components is greater than the internal similarity of each component. A partition is under-segmented (not enough components) if there is a way to split some of its components and obtain a partition that is not over-segmented.

Our Algorithm:

Assume the measure of similarity between two disjoint components to be the weight of the cheapest edge connecting the components. Also assume the measure of internal similarity of a component to be some function of the weights in the minimum-spanning-tree of that component satisfying a monotonicity property. Under these assumptions we have a greedy algorithm to find a partition of the graph that is neither over- nor under-segmented. The algorithm starts with a completely disconnected graph and consider edges in increasing weight order. For each edge it decides if they should be added to the graph based on the similarity functions calculated on the components of the graph built so far. The running time is nearly linear to the number of pixels in the image. In practice it takes 1-2 seconds to segment a 320x240 gray image.

Poscript of a paper describing this work is available here.

Example results:

Click on the images to see segmentation results.