Graph Cut Based Segmentation of Predefined Shapes: Applications to Biological Imaging

Emmanuel Soubies, Pierre Weiss, Xavier DescombesICPRAM (Selected Papers) 2013 · DOI

TL;DR

This paper introduces a novel algorithm for segmenting biological cell nuclei (or other objects) by modeling them as non-overlapping ellipses or ellipsoids. It leverages a graph-cut approach combined with a stochastic birth-and-death process to efficiently find the optimal configuration of these shapes, even in challenging, noisy images. This method offers robust and accurate segmentation for applications in cell biology.

What Problem Does This Paper Address?

Accurately segmenting cells and their nuclei is a fundamental challenge in biological imaging, especially with the advent of high-resolution microscopes that probe deeper into tissues. These advanced imaging techniques, like confocal or bi-photon microscopy, often introduce image degradations such as light attenuation, photo bleaching, and heavy noise. These issues make traditional contour-based segmentation methods struggle, as they rely on clear image contrasts and regularity assumptions. The problem is further complicated by the need to identify multiple objects (nuclei) that cannot overlap, and the fact that their exact number and shapes are unknown beforehand.

Methods

The core of the proposed method is a Multiple Birth and Cut (MBC) algorithm. This algorithm iteratively refines a segmentation by:

  • Birth Step: Randomly generating new candidate objects (ellipses/ellipsoids) to add to the current configuration. This step is enhanced by a "local perturbation" heuristic that perturbs existing objects rather than generating entirely new ones, which speeds up convergence.
  • Cut Step: Using a graph-cut algorithm to select the optimal subset of objects from the combined set of existing and newly generated candidates. This step effectively resolves overlaps and minimizes a defined energy function that balances data fidelity (how well the shape fits the image) and prior knowledge (non-overlapping shapes).

The algorithm defines an energy function that is contrast-invariant, meaning it's less affected by variations in image brightness or contrast. This is achieved by using image gradients along the object boundary. To promote well-located objects, a thresholding mechanism is applied to this energy. A key technical innovation is a fast ellipse/ellipsoid intersection detection algorithm, which is crucial for the efficiency of the graph-cut step.

Datasets

The paper demonstrates its method on various biological images, including:

  • A SPIM image of a multicellular tumor spheroid (Figure 1).
  • Drosophila embryos (2D and 3D) (Figures 9, 13).
  • A multicellular tumor spheroid (Figure 10).
  • Spermatozoon colonies (Figure 11).
  • Micro pillars (Figure 12).
  • A 3D multicellular tumor spheroid (Figure 14).

No new datasets were introduced; the focus is on applying the algorithm to existing biological imaging data.

Key Insights and Ideas

  • Shape Priors as a Solution: Instead of relying solely on image intensity, incorporating strong shape priors (ellipses/ellipsoids) is crucial for robust segmentation in degraded biological images.
  • Contrast Invariance is Key: For fluorescence microscopy, energies that are invariant to local contrast changes are essential for reliable segmentation.
  • Graph Cuts for Global Optimization: Graph cuts provide an efficient way to solve the complex, non-convex optimization problem of finding the best configuration of non-overlapping objects.
  • Birth-and-Death Dynamics: A stochastic birth-and-death process, combined with graph cuts, allows for handling an unknown number of objects and escaping local minima.
  • Local Perturbations for Speed: Accelerating convergence by perturbing existing objects, rather than purely random generation, significantly improves performance, especially in higher dimensions.

Key Results

  • The algorithm demonstrates robust segmentation performance on challenging 2D and 3D biological images, even with significant noise, blur, and contrast loss.
  • It successfully identifies nuclei in Drosophila embryos and multicellular tumor spheroids, providing results comparable to human expert segmentations.
  • The MBC algorithm with local perturbations (MBC with LP) shows a significant improvement in convergence speed compared to the standard MBC algorithm, as illustrated by the energy evolution plot (Figure 8).
  • The algorithm is relatively easy to tune, requiring only a few parameters related to the physical properties of the objects (e.g., size variability, ellipticity).
  • Computing times are reported as 5 minutes for a 700x350 image and 2 hours for a 700x350x100 3D image, which is reasonable for many biological applications.

Limitations and Future Work

  • Image Restoration: For extremely blurry images, particularly in the Z-direction for 3D data, image restoration algorithms and the design of new energies robust to strong perturbations are suggested as important future work.
  • Quantitative Evaluation: The authors plan to conduct a quantitative evaluation of the algorithm's efficiency using gold standards.
  • Complex Interactions: Future work will explore encoding more complex interactions between objects to handle scenarios where image level lines don't provide sufficient information for fitting ellipsoids.

Summary updated

BibTeX
@inproceedings{soubies2013graph,
  author = {Emmanuel Soubies and Pierre Weiss and Xavier Descombes},
  title = {{Graph Cut Based Segmentation of Predefined Shapes: Applications to Biological Imaging}},
  booktitle = {ICPRAM (Selected Papers)},
  year = {2013},
  doi = {10.1007/978-3-319-12610-4\_10},
}
Figure