Unsupervised Segmentation of Natural Images

via Lossy Data Compression

Allen Y. Yang, John Wright,  Yi Ma, and Shankar Sastry

© Copyright Notice: It is important that you read and understand the copyright of the following software packages as specified in the individual items. The copyright varies with each package due to its contributor(s). The packages should NOT be used for any commercial purposes without direct consent of their author(s). 


We cast natural-image segmentation as a problem of clustering texure features as multivariate mixed data. We model the distribution of the texture features using a mixture of Gaussian distributions. Unlike most existing clustering methods, we allow the mixture components to be degenerate or nearly-degenerate. We contend that this assumption is particularly important for mid-level image segmentation, where degeneracy is typically introduced by using a common feature representation for different textures in an image. We show that such a mixture distribution can be effectively segmented by a simple agglomerative clustering algorithm derived from a lossy data compression approach. Using either 2D texture filter banks or simple fixed-size windows as texture features, the algorithm effectively segments an image by minimizing the overall coding length of the feature vectors. We conduct comprehensive experiments to measure the performance of the algorithm in terms of visual evaluation and a variety of quantitative indices for image segmentation. The algorithm compares favorably against other well-known image segmentation methods on the Berkeley image database.

  Allen Y. Yang, John Wright, Yi Ma, and Shankar Sastry. Unsupervised segmentation of natural images via lossy data compression. To appear in CVIU 2007. [PDF]

Yi Ma, Harm Derksen, Wei Hong, and John Wright. Segmentation of multivariate mixed data via lossy coding and compression. (Preprint) PAMI. 2007. [PDF]

MATLAB Toolboxes:

Segmentation of Mixtures of Gaussians via Pairwise Steepest Descent

This package implements Algorithm 1 in the paper.

Source code: http://www.eecs.berkeley.edu/~yang/software/lossy_segmentation/MDL_segmenter.zip

(c) Copyright. University of California, Berkeley. 2007.

Authors: Wei Hong, John Wright, and Allen Y. Yang.
Contact: Allen Y. Yang <yang@eecs.berkeley.edu>
Last update: 3-6-2007.

Natural-Image Segmentation via Lossy Compression

This package implements the CTM algorithm.

Source code: http://www.eecs.berkeley.edu/~yang/software/lossy_segmentation/CTM_image_segmentor.zip

(c) Copyright. University of California, Berkeley. 2007.

Authors: John Wright and Allen Y. Yang.
Contact: Allen Y. Yang <yang@eecs.berkeley.edu>
Last update: 7-30-2007.

Image Segmentation Benchmark Indices Package

We provide the source codes that implement four standard image segmentation indices that compare the difference between two segmentation results of the same set of images. Particularly, we are interested in comparing segmentation results between an algorithm and human subjects.
  1. The Probabilistic Rand Index (PRI) [Pantofaru2005] counts the fraction of pairs of pixels whose labellings are consistent between the computed segmentation and the ground truth, averaging across multiple ground truth segmentations to account for scale variation in human perception.
  2. The Variation of Information (VoI) metric [Meila2005] defines the distance between two segmentations as the average conditional entropy of one segmentation given the other, and thus roughly measures the amount of randomness in one segmentation which cannot be explained by the other.
  3. The Global Consistency Error (GCE) [Martin2001] measures the extent to which one segmentation can be viewed as a refinement of the other. Segmentations which are related in this manner are considered to be consistent, since they could represent the same natural image segmented at different scales.
  4. The Boundary Displacement Error (BDE) [Freixenet2002] measures the average displacement error of boundary pixels between two segmented images. Particularly, it defines the error of one boundary pixel as the distance between the pixel and the closest pixel in the other boundary image.

Soource code: http://www.eecs.berkeley.edu/~yang/software/lossy_segmentation/SegmentationBenchmark.zip

(c) Copyright. University of California, Berkeley. 2007.

Authors: John Wright and Allen Y. Yang.
Contact: Allen Y. Yang <yang@eecs.berkeley.edu>
Last update: 3-6-2007.

Note: The Berkeley image segmentation benchmark set is available at: http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbench/

Representative Segmentation Results from the Berkeley Segmentation Benchmark Database

We provide here segmentation results on the Berkeley segmentation benchmark obtained by CTM.

There are two ways to download the results.
  1. Direct download the following zipped folders that contain the results of all images in both png image format and mat MATLAB format. The mean distance was used to measure the texture similarity.
  1. Click the following links to see individual rendering of representative examples in six different image categories. The gamma parameter is set as 0.3.


[Return to Home]