CSAIL Research Abstracts - 2005 link to http://publications.csail.mit.edu/abstracts/abstracts05/index.html link to http://www.csail.mit.edu
bullet Introduction bullet Architecture, Systems
& Networks
bullet Language, Learning,
Vision & Graphics
bullet Physical, Biological
& Social Systems
bullet Theory bullet

horizontal line

Voronoi-Based Segmentation on Manifolds

Thouis R. Jones, Polina Golland & Anne Carpenter (Whitehead Institute for Biomedical Research)


We are developing methods and algorithms for high-throughput image analysis for cell images. These are necessary to enable screens of visual phenotype in genoms-scale perturbation experiments. Such methods are also valuable in drug discovery, where large libraries of compounds are screened in a high-throughput manner.

As part of this project, we have developed and algorithm for finding the boundaries between adjacent regions in an image, such as cells, where some sort of "seed" area has already been identified in the individual regions to be segmented, such as the nucleus. The algorithm finds the Voronoi region of each seed on a manifold with a metric controlled by local image properties. We have explored similarities to other methods based on image-controlled metric, such as Geodesic Active Contours, and have developed a fast algorithm for computing the Voronoi regions on the manifold. We are validatating our method against hand-traced boundaries for cell images.


Image Cytometry, the measurement of cell properties from microscope images, is becoming more prevalent. In particular, high-throughput experiments rely on automatic processing of images to deal with the large amount of data they produce [3]. A fundamental operation in cell-image analysis is identifying individual cell boundaries. This is often difficult because there are many different staining protocols, leading to dramatically different appearances for cells. Moreover, the difference between cell interior and cell border may not be very pronounced.

It is usually the case that the nuclei of cells are more easily identifiable, because they have a more uniform appearance and shape, and do not generally abut one another, as cells do. They are also usually interior to the cells. This leads us to phrase the problem of segmenting cells as one of identifying boundaries between regions given "seeds" in individual regions from which to start the segmentation.

Existing methods for region identification, such as watershed [2, 4], are often too fragile. Watershed segmentation treats the image as a height field, and segments pixels according to which minimum a drop of water would flow to if placed on that pixel in the height field. Morphological operations are used to impose a limited set of minima, equivalent to our seed regions. Watershed is quite unstable, because a single erroneous pixel can allow large groups of pixels to change segmentation, by creating a gap leading to a different minimum. We avoid this fragility in two ways: first, by comparing neighborhoods of pixels rather than individual pixels, and second, by including a regularization factor to provide reasonable behavior when the image data does not contain a strong enough edge between two seed regions.

cells segmentation
Drosophila cells stained for Actin,
and their segmentation as found by our algorithm.

[1] Thouis R. Jones, Polina Golland, & Anne Carpenter. Voronoi-Based Segmentation on Manifolds. In Preparation. 2005.

[2] S. Beucher. The Watershed Transformation Applied to Image Segmentation. Scanning Microscopy International, Vol. 6, pp.299-314, 1992. pp. 299-314.

[3] A.E. Carpenter and D.M. Sabatini. Systematic Genome-wide Screens of Gene Function. Nature Reviews Genetics, Vol. 5, pp. 11-22, 2004.

[4] C. Wahlby. Algorithms for Applied Digital Image Cytometry. PhD Thesis, 2003.

horizontal line

MIT logo Computer Science and Artificial Intelligence Laboratory (CSAIL)
The Stata Center, Building 32 - 32 Vassar Street - Cambridge, MA 02139 - USA
tel:+1-617-253-0073 - publications@csail.mit.edu
(Note: On July 1, 2003, the AI Lab and LCS merged to form CSAIL.)