PMCCPMCCPMCC

Search tips
Search criteria 

Advanced

 
Logo of nihpaAbout Author manuscriptsSubmit a manuscriptHHS Public Access; Author Manuscript; Accepted for publication in peer reviewed journal;
 
Proc IEEE Int Symp Biomed Imaging. Author manuscript; available in PMC 2011 June 21.
Published in final edited form as:
Proc IEEE Int Symp Biomed Imaging. 2010 June 21; 2010(14-17 April 2010): 552–555.
doi:  10.1109/ISBI.2010.5490286
PMCID: PMC3048333
NIHMSID: NIHMS272393

RESOLVING CLUSTERED WORMS VIA PROBABILISTIC SHAPE MODELS

Abstract

The roundworm Caenorhabditis elegans is an effective model system for biological processes such as immunity, behavior, and metabolism. Robotic sample preparation together with automated microscopy and image analysis has recently enabled high-throughput screening experiments using C. elegans. So far, such experiments have been limited to per-image measurements due to the tendency of the worms to cluster, which prevents extracting features from individual animals.

We present a novel approach for the extraction of individual C. elegans from clusters of worms in high-throughput microscopy images. The key ideas are the construction of a low-dimensional shape-descriptor space and the definition of a probability measure on it. Promising segmentation results are shown.

Keywords: Caenorhabditis elegans, image segmentation, active shape model, high-throughput screening

1. INTRODUCTION

Using automated sample preparation and microscopy, high-throughput screens (HTS) in Caenorhabditis elegans are now being used to test tens of thousands of chemical or genetic perturbations to identify promising drug compounds and regulators of disease [1, 2, 3]. Unfortunately, except for very simple assay readouts, image analysis algorithms have not been available to automatically analyze HTS samples. Instead, researchers must typically inspect each of the hundreds of thousands of microscopy images collected for a screen, a tedious, non-quantitative, subjective, and error-prone process.

The main challenge in analyzing images from high-throughput C. elegans experiments is that the density of worms in each well of the microplates used for such experiments causes the worms to touch or cross over each other. While the outcome of some simple assays can be determined by measuring a property of the foreground in the overall image (e.g., overall fluorescently-stained area in the image [4]), most assays require identifying and measuring a property of each individual worm in the population, most commonly each worm's shape or fluorescent pattern. Image analysis algorithms for tracking one or a few worms over time were developed [5, 6]. However, these methods exploit motion cues to disambiguate touching worms and cannot be used in still images of high-throughput screens. Other advanced methods based on high-resolution analysis and time-resolved 3-D worm images [7, 8] are also not suitable for the comparatively low spatial resolution of HTS experiments.

Meticulous analysis of C. elegans images reveals that while the edges of overlapping worms are not sufficient to separate them, the morphological deformations between the worms' appearances are nearly isometric. This implies that the variability between the worms' appearances can be captured via a low-dimensional feature space, much in the spirit of the commonly used active shape model (ASM) [9, 10]. Just as Leventon et al. [11], we assume that these features are normally distributed, and we validated the assumption experimentally for a comprehensive set of training worms (data not shown). We can therefore define the concept of a probable worm shape and use it to partition a given worm cluster such that the sum of the posterior worm probabilities of the resulting segments is maximized. We demonstrate our method for several HTS samples.

2. THE WORM MODEL

The suggested method consists of two phases. In the training phase a comprehensive set of training worms are used to learn the feature space of the worms' deformations and the probability distribution defined on it. In the test phase we use outcomes of the learning phase to resolve worm clusters. This section presents the learning methodology applied on N training worms obtained by an initial segmentation of the images. The next section deals with partitioning the clusters formed by the remaining worms.

We first represent the shape deformations of the worms by using the medial-axis transform [12], which returns the skeleton of the shape and its distances to the boundaries. Similarly to the ASM, the vector representations of the parameterized skeletons are projected into a lower-dimensional feature space. The compact representation is used for reconstruction and retrieval [10]. Fig. 1 exemplifies the process of skeleton extraction and reconstruction of an individual worm. The skeleton of each worm (Fig. 1A) is extracted (Fig. 1C), and spurs are pruned off by iteratively removing the shortest spur of every branch point of the skeleton. Once a non-branched skeleton is obtained (Fig. 1D), end points are extracted, and n control points are uniformly sampled along the skeleton. The local radii of the worm are also extracted and saved for each of the control points. Thus, the original worm shape can be approximately restored by placing disks with the local radius at each control point, and then smoothing the edges by taking the pair-wise convex hull of the disks (Fig. 1E).

Fig. 1
Creating a worm descriptor. A: Input image (rotated). B: Result from initial segmentation. C: Skeleton. D: Pruned skeleton with control points shown as disks with the local radius. E: Shape recreated from descriptor.

We use similarity transformation (i.e., rotation and translation) to align the skeletons of the worms to the y-axis minimizing the squared sum of the Euclidean distances of corresponding points along the skeletons [9]. Fig. 2A shows the aligned skeletons of the training set. All images are also mirrored around the y-axis to obtain a symmetric descriptor. Note that the alignment is rigid (no scaling or skew), so that the non-rigid components of the deformations are captured within the shape descriptors. In the absence of prior scaling, for example, segments that are significantly smaller then the average worm have lower probability of being classified as worms. We define the mean worm as the average of the aligned control points and their corresponding distances from the background.

Fig. 2
The training set. A: Connected control points of N worms (and their shape mirrored around the y-axis) after alignment by translation and rotation. B: Variation in radius along the length of all N worms.

Fig. 2B shows the radii of the training worms along their skeletons. The regularity of the worms' radius profiles allows us to represent the radii by a single value; the median thickness of the worm. The deformations of the postures of the worms are therefore described by the coordinates of the n aligned control points and the median thickness of the worm, resulting in a (2n + 1)-dimensional data space.

We use principal component analysis [13] to project the descriptor of the training worms into a lower-dimensional feature space. Let D define the covariance matrix of the descriptors of the training worms. Then,

equation M1
(1)

where bk and λk are the k-th eigenvector and eigenvalue of D, respectively. We were able to restore with good approximation each worm x in the training set using linear combinations of L of the 2N + 1 eigenvectors:

equation M2
(2)

where equation M3 is the averaged worm descriptor, w is a vector of weights, and BL is a matrix of the eigenvectors {b1bL} corresponding to the L larges eigenvalues. Fig. 3 shows five “eigenworms”, each built from an eigenvector multiplied by increasing weights.

Fig. 3
The effect of varying the weights of five of the largest “eigenworms” of the worm model.

We observed that the weights of the training worms are normally distributed. Constructing the feature space of the worms' deformations, we can now define a probability measure on that space:

equation M4
(3)

where ΣL = diag(λ1 …λL). This is the key principle used to resolve clustered objects in the next section.

3. RESOLVING WORM CLUSTERS

Once the shape deformation model is defined, we apply it to resolve the clusters of worms that remain after initial image segmentation (described in Sec. 4). Because the worms in our screens vary only slightly in body area, we can readily identify clusters as objects larger than 1.5 times the mean size of the worms in the training set. Unusually small objects, such as debris and over-segmented worms, are excluded from the analysis.

Let S denote the skeleton of a cluster of worms pruned so that only branches longer than the average radius of a worm remain. S is separated in to segments by cutting the skeleton at every branch point. The skeleton S can now be represented by a sparse undirect graph where each skeleton segment corresponds to a vertex v, and each branch point corresponds to an edge e. Thus, the full cluster skeleton S can be represented by the set of vertices {v} and the set of edges {e}.

Next, we want to resolve the cluster by finding the set of paths ρ through the cluster that has the highest probability of representing a set of worms. A path ρ on S is a set of vertices {v1vm} connected by a set of edges edges {e1en}, where m ≥ 1, n ≥ 0. Note that the number of possible paths in S grows exponentially with the number of edges, or branch points. We first estimate the number of worms in a cluster by dividing the cluster area by the area of the mean worm. We use a greedy algorithm to search for a cluster partition that maximizes the sum of the probabilities of the segments. Formally, let K be the estimated number of worms in a cluster and let ρk be a path in S that represents a worm. We look for a partition {ρ1 …ρK} of S such that the cost

equation M5
(4)

of the partition is minimized. The probability p of a path ρ is given by Eq. 3, where the weights w are obtained when describing the path ρ with the worm model, using Eq. 2.

Fig. 4 shows an example of a cluster with two intersecting worms. We calculate the probability p of each path in the graph. The five most probable sub-skeletons of Fig. 4B are shown in Fig. 4D–H. We select the most probable path to represent a worm in the cluster. When the path contains intersections, we remove the largest vertex; otherwise, we remove it entirely. We continue the process until the remaining vertices are smaller than the smallest worm in the training set.

Fig. 4
A simple cluster and its separation. A: input image. B: binary image after foreground/background segmentation of A. C: skeleton of B partitioned into four vertices (v) and one edge (e). D–H: The 5 most probable skeletons, with corresponding probabilities. ...

4. EXPERIMENT

4.1. Image data

The worm preparation and image acquisition are detailed in Moy et al. [4]. In brief, C. elegans is infected by the bacterial pathogen Enterococcus faecalis, washed, transferred to 384-well plates containing liquid media with the compound to be tested, incubated until the infection kills untreated worms, washed, and imaged by a Discovery-1 automated microscope (Molecular Devices) with a 2× magnification lens.

4.2. Initial image segmentation and model building

To build the training set, we segment worms from the image background by local adaptive thresholding [14] and morphological opening, after reducing illumination variation by subtracting a B-spline surface approximating the image background [15]. Worms are further separated from each other based on gray-scale information by watershed segmentation [16] followed by extensive merging [17].

From the objects identified by this automated method, we manually selected N = 454 correctly segmented worms from a total of 56 images of wells containing approximately 15 worms each. The worms had varying shapes, and approximately 25% of the worms had a straight rod shape, characteristic of dead worms. We cropped the selected worms and the corresponding binary masks from the input images, and a model worm was created using eight eignevectors (L=8) responsible for 99% of the model variation as described above.

4.3. Cluster partition

We applied the proposed segmentation approach to images containing worm clusters that could not be resolved based on gray-scale information alone. Most of the worms were correctly segmented as compared to visual evaluation (Fig. 5). Note that the 4-cluster in Fig. 5A, the 5-cluster in Fig. 5B, the several 2-clusters in Fig. 5C, and the 6-cluster in Fig. 5D were partitioned correctly.

Fig. 5
Four wells from a viability assay with segmentation shown as outlines. The first worm of every cluster, as well as single worms, are outlined in red.

5. CONCLUSION AND FUTURE WORK

We have shown that incorporating shape information allows clusters of C. elegans to be resolved. Once worm clusters can be reliably resolved, the live–dead assay can be automatically scored using simple shape descriptors. For classification of more complex phenotypes, machine learning may be used to derive a combination of texture, shape, and color features. Overall, the algorithms described here show promise as the basis of an open-source toolbox for the robust, automated scoring of a wide range of C. elegans assays.

We are currently exploring more advanced skeletonization algorithms and extending our shape model to handle self-intersections and other challenging topologies. Finally, we will apply the methods to several large screening experiments.

Acknowledgments

This work was supported in part by grant numbers R01 AI072508, P01 AI083214, R01 AI085581 and U54 EB005149 from NIH

6 REFERENCES

[1] Artal-Sanz M, de Jong L, Tavernarakis N. Caenorhabditis elegans: A versatile platform for drug discovery. Biotechnol J. 2006;1:1405–1418. [PubMed]
[2] Kamath RS, Ahringer J. Genome-wide RNAi screening in Caenorhabditis elegans. Methods. 2003;30(no. 4):313–321. [PubMed]
[3] Sifri CD, Begun J, Ausubel FM. The worm has turned – microbial virulence modeled in Caenorhabditis elegans. Trends Microbiol. 2005;13:119–127. [PubMed]
[4] Moy TI, Conery AL, Larkins-Ford J, Wu G, Mazitschek R, Casadei G, Lewis K, Carpenter AE, Ausubel FM. High-throughput screen for novel antimicrobials using a whole animal infection model. ACS Chemical Biology. 2009;4(no. 7):527–533. [PMC free article] [PubMed]
[5] Ramot D, Johnson BE, Berry TL, Carnell L, Goodman M. The parallel worm tracker: A platform for measuring average speed and drug-induced paralysis in nematodes. PLoS One. 2008;3(no. 5):e2208. [PMC free article] [PubMed]
[6] Geng W, Cosman P, Berry CC, Feng Z, Schafer WR. Automatic tracking, feature extraction and classification of C. elegans phenotypes. IEEE Tran Biomed Eng. 2004;51(no. 10):1811–1820. [PubMed]
[7] Long F, Peng H, Liu X, Kim SK, Myers E. A 3D digital atlas of C. elegans and its application to single-cell analyses. Nat Methods. 2009;6(no. 9):667–672. [PMC free article] [PubMed]
[8] Murray JI, Bao Z, Boyle TJ, Boeck ME, Mericle BL, Nicholas TJ, Zhao Z, Sandel MJ, Waterston RH. Automated analysis of embryonic gene expression with cellular resolution in C. elegans. Nat Methods. 2008 [PMC free article] [PubMed]
[9] Cootes TF, Taylor CJ, Cooper DH, Graham J. Active shape models—their training and application,” Comput Vis Image Understand. 1995;61(no. 1):38–59.
[10] Stephens GJ, Johnson B. Kerner, Bialek W, Ryu WS. Dimensionality and dynamics in the behavior of C. elegans. PLoS Comput Biol. 2008;4(no. 4) [PMC free article] [PubMed]
[11] Leventon ME, Grimson WEL, Faugeras O. Statistical shape influence in geodesic active contours. Proc IEEE Conf Comp Vis and Pattern Recog.2000. pp. 316–323.
[12] Goutsias J, Shonfeld D. Morphological representation of discrete and binary images. IEEE Trans Signal Proc. 1991;39(no. 6):1369–1379.
[13] Johnson RA, Wichern DW. Multivariate Statistics, A Practical Approach. Chapman & Hall; 1988.
[14] Gonzales RC, Woods RE. Digital Image Processing. Addison-Wesley; 1993.
[15] Lindblad J, Bengtsson E. A comparison of methods for estimation of intensity nonuniformities in 2D and 3D microscope images of fluorescence stained cells. Proc Scandinavian Conf Image Analysis (SCIA).2001. pp. 264–271.
[16] Vincent L, Soille P. Watersheds in digital spaces: An efficient algorithm based on immersion simulations. IEEE Trans PAMI. 1991;13:583–598.
[17] Wählby C, Sintorn I-M, Erlandsson F, Borgefors G, Bengtsson E. Combining intensity, edge and shape information for 2D and 3D segmentation of cell nuclei in tissue sections. J Microscopy. 2004;215(no. 1):67–76. [PubMed]