4.1.1 A Brief Overview of Voronoi Tessellation and Its Properties.

‘Voronoi Diagram’ is a geometric minimization diagram that splits its embedding space into different non-overlapping regions. Each of these regions is characterized by a generating point or an object also known as the ‘site’. All other points in each of these regions are closer to the site in its region than to any other site in the entire embedding space. The closeness of the points to the sites is computed using a distance metric. There can be different types of sites ranging from a point, a line to any complex geometric shape. Depending on the type of sites, the distance metric or the embedding space, several different variations of the Voronoi diagram can be defined. Detailed discussions on many of such variants can be found in [20]–[22].

Based on the characteristic of site and distance function, the locus of the points equidistant from two neighboring sites (also termed as the ‘bisectors’ or ‘edges’) can be hyperplanes or higher order hypersurfaces. We call the Voronoi diagrams with hyperplane bisectors as the ‘Affine Voronoi’ diagrams. The most common example of such an affine diagram is the Voronoi diagram of points based on the Euclidean distance metric.

Let there be point sites in a space , and the set of all sites be . The Voronoi regions associated with these sites are represented as where,(1)where is the half-plane defined by,

(2)The distance for a standard Voronoi diagram is the Euclidean distance defined by

Again, the set of all points on the bisector between two Voronoi regions and is given by,(3)

Some of the properties of the Euclidean distance based Voronoi diagram with point sites are as follows:

1. The line joining any two Voronoi sites and is always perpendicular to the Voronoi bisector/edge ,
2. The perpendicular distances from and to are equal to one another,
3. Any point would satisfy
   and
4. The Voronoi regions, thus produced, are convex polyhedrons and can be expressed as intersection of a finite number of open or closed half spaces.

In Figure 2(A), we have shown some of the properties for a 2D Voronoi tessellation with twenty one sites ( etc.). It can be observed that each of these Voronoi regions is a convex polygon.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 2. A schematic of Voronoi Tessellation and Estimated SAM cell centroids as Voronoi sites.

(A) A Voronoi diagram based on the Euclidean distance metric for twenty one sites in 2D. The figures also show that the Voronoi edges are perpendicular to the line joining any two neighbouring sites. are three of the Voronoi edges and they are the perpendicular bisectors of respectively. (B) Centroids are estimated for around two hundred cells in a SAM tissue, which are also the sites of Euclidean distance based Voronoi tessellation.

https://doi.org/10.1371/journal.pone.0067202.g002

4.1.2 Voronoi Sites Estimation From Sparse Data.

After segmentation and tracking, we are given a sparse set of 3D data-points that lie on the boundary between the neighbouring cells. Our objective is to fit a Voronoi tessellation to these data-points to obtain complete structures of individual cells, represented as Voronoi polyhedrons in 3D. Therefore, ideally the sparse data-points should lie on the bisectors between the neighbouring Voronoi regions. Given a very sparse set of data-points on the bisectors as in the case of ‘Live cell imaging’, the only way to reconstruct the Voronoi diagram is to first estimate the approximate locations of Voronoi sites, from which the Voronoi edges/bisectors can then be computed.

Given a set of generating sites, the construction of the Voronoi diagram can be done through several methods, the most popular of which being Fortune's ‘sweep line’ algorithm. The inverse problem, i.e. to obtain the locations of the sites given the Voronoi bisector, is, however, less studied in the literature. In [23], Evans et al. proposed a linear least-square technique to estimate the Voronoi sites by fitting a Voronoi diagram over a given tessellation pattern. Again, in [24], a number of algorithms have been proposed to obtain the Voronoi sites given the vertices of the Voronoi polygons. But neither of these methods is applicable to the sparse data that we have. These methods require the knowledge of the complete structures of the Voronoi polyhedrons, which is precisely the output that we are after. In fact, because of the extreme sparsity in our dataset, it is rather impossible to obtain unique estimates of the Voronoi sites for individual 3D cells.

In this situation, the knowledge about the physical structure of the SAM stem cells help us in obtaining approximate locations of the Voronoi sites, where each cell is represented as a Voronoi region. In [6], the authors observed that the SAM cells can be represented as Voronoi regions where the sites are located at the approximate centers of the cell nuclei. This observation, along with the fact that the nucleus, located in the central region of the cell, contributes to the majority of the size of a SAM cell motivates us to devise a simple strategy to estimate the approximate site locations, even when the nuclei are not imaged in the confocal image stack.

Given that the sparse set of points on the segmented and tracked slices of a cell are (the 3D data-point set ), the approximate centroid location of the cell would be , where the elements are the arithmetic means of and respectively. Thus, is also the estimated approximate location of the site corresponding to the Voronoi region representing the cell . The centroids for approximately 200 cells from a SAM tissue is shown in Figure 2(B).

Now, the next step would be to generate a dense point cloud sampled from within the SAM structure and to cluster this dense set of 3D data-points into different Voronoi regions (representing individual cells) based on the estimated locations of the sites .

4.1.3 Generation of Dense Point Cloud To Be Partitioned Into Cells: Global Shape of SAM.

At this stage, we estimate the 3D structure of the SAM by fitting a smooth surface to its segmented contours. The surface fitting is done in two steps. In step one, the SAM boundary in every image slice is extracted using the ‘Level Set’ method (Figure 3(A)). A level set is a collection of points over which a function takes on a constant value. We initialize a level set at the boundary of the image slice for each SAM cross section, which behaves like an active contour and gradually shrinks towards the boundary of the SAM. Let the set of points on the segmented SAM contours be ().

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 3. Generation of the dense point cloud from within the reconstructed SAM surface.

(A) The SAM contours extracted from the confocal image stack using Level-Set segmentation, (B) The SAM surface is reconstructed using linear interpolation on a local neighbourhood of points on the SAM contours, (C) A very dense point cloud is extracted from within the reconstructed SAM surface which is clustered using the proposed reconstruction technique into individual cells.

https://doi.org/10.1371/journal.pone.0067202.g003

In the second step, we fit a surface on the segmented points . Assuming that the surface can be represented in the form (where the function is unknown), our objective is to predict at every point on a densely sampled rectangular grid of points bounded by . As the segmented set of data points are extremely sparse, this prediction is done using a linear interpolation on a local set of points on the grid around the point . As the value () for the point is approximated by a linear combination of the values at a few neighboring points on the grid, the interpolation problem can be posed as a linear least-square estimation problem. We also impose a smoothness constraint in this estimation by forcing the first partial derivatives of the surface evaluated at neighboring points to be as close as possible. A MATLAB visualization [25] of the surface is shown in Figure 3(B).

Once the SAM surface () is constructed, we uniformly sample a dense set of 3D points (, a visualization can be found in Figure 3(C)) such that every point in must lie inside . Thus, and the required output from the proposed algorithm is a clustering of these dense data points into cells/clusters such that starting from the sparse set of segmented and tracked points obtained from the confocal slice images of individual cells.

4.1.4 Segmentation of The Dense Point Cloud Into Voronoi Cells.

In this step, we partition the dense point cloud , obtained in the last step, into clusters based on the site locations , estimated in Section 4.1.2.

The cell can be represented as a collection of dense data-points belonging to the Voronoi region as(4)

Once the dense point cloud belonging to each Voronoi region is obtained, we can construct convex polyhedrons with each of these dense point clusters () to obtain the cell resolution 3D reconstruction of SAM.

4.2.1 Estimating The Distance Metric From Sparse Data: Minimum Volume Enclosing Ellipsoid.

Now, the problem at hand is to estimate the parameter pair for each cell/quadratic Voronoi regions from the sparse data-points, as obtained from the segmented and tracked slices, that belongs to the boundary of each cell. Given the extreme sparsity of the data, there is no available method that would provide s for each region. We, in this work, propose an alternative way of estimating pairs directly from the sparse data-points.

An ellipsoidal surface in 3D is given by the locus of the point that satisfies(9)where is the center of the ellipsoid and is a positive definite symmetric matrix. For any point inside the ellipsoid, and for every outside it, .

Now, is, in fact, the Mahalanobis distance of the point from the center of the ellipsoid. Therefore, if a point is equidistant for the centers of two ellipsoids and in the Mahalanobis sense, then,(10)

Now, Equation (10) gives the locus of the points , which is exactly the same as that of the points on the bisector two neighbouring quadratic Voronoi regions parameterized by and . We already have a set of points ()which are sparsely but uniformly z-sampled from the boundaries between neighbouring cells. The tracking algorithm provides us with the exact cell pairs on which every point from this set belongs to. Therefore we can approximately estimate the distance parameters associated with every quadratic Voronoi region individually by fitting an ellipsoid to the sparse data-points belonging to the boundaries of that region. In this paper, we choose fit Minimum Volume Enclosing Ellipsoids (MVEE) to each of for cells individually and obtain approximate estimates of . The estimation strategy is described later in this Section and the details of the same can be found in Section 3 of File S1.

As we are estimating the parameters of quadratic distance metric associated with every individual Voronoi cell separately and then using the distance metrics, thus obtained, to tessellate a dense point cloud, we choose to call the resulting Voronoi tessellation as the ‘Adaptive Quadratic Voronoi Tessellation’ (AQVT).

After registration, segmentation and identification of a cell in multiple slices in the 3-D stack, we can obtain co-ordinates of the set of points on the perimeter of the segmented cell slices. Let this set of points on the cell be . We have to estimate the minimum volume ellipsoid which encloses all these points in and we denote that with . An ellipsoid in its center form is represented by(11)where is the center of the ellipsoid and . Since all the points in must reside inside , we have(12)and the volume of this ellipsoid is

(13)Therefore, the problem of finding the Minimum Volume Enclosing Ellipsoid (MVEE) for the set of points can be posed as(14)

To efficiently solve Problem () we convert the primal problem into its dual problem since the dual is easier to solve. A detailed analysis on the problem formulation and its solution can be found in [26], [27]. Solving this problem individually for each sparse point set , the parameters of the quadratic distance metrics are estimated as . To visually represent these parameters, we have constructed the ellipsoids with each of these parameter pairs and color coded them to represent individual cells in a SAM tissue (Figure 4).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 4. Ellipsoidal representation of the AQVT parameters estimated from the sparse data-points.

(A) The Minimum Volume Enclosing Ellipsoids representing the parameter pairs for individual cells are shown in different colors. (B) The same representation viewed from top.

https://doi.org/10.1371/journal.pone.0067202.g004

4.2.2 3D Tessellation Based on The Estimated Parameters of AQVT: The Final Cell Shapes.

As soon as the parameters of the quadratic distance metrics are estimated from the previous step, the dense point cloud obtained in Section 4.1.3 can be partitioned into different Voronoi regions based on Equation (8), i.e. the dense point cloud belonging to cell is given as(15)

For visualization purpose of the cell resolution 3D reconstruction results, we fit convex polyhedrons to to represent each cell.

4.2.3 Relation Between The AQVT and Deformed Trucncated Ellipsoid Based Tessellation [7].

In a recent work [7], we have shown that the 3D shapes of individual cells in a tightly packed multi-layer tissue can be approximated by deformed truncated ellipsoidal models. In that work, first, the enclosing ellipsoids (MVEE) are fitted to the sparse data-points for each cell, which are then recursively deformed until a certain stopping criterion (see [7]) is satisfied and finally truncated along the overlapping surfaces of those 3D deformed ellipsoids to obtain the final 3D cell shapes.

Following the same notations used before, the estimated enclosing ellipsoids for the sparse point sets are given by . We observed through our experiments that the best 3D reconstruction results are achieved when the estimated ellipsoids are deformed along their axes and the deformation along each axes at each iteration step is proportional to the current length of the axes. Let the factor by which each axis is deformed be and let there be iterations before the algorithm in [7] converges.

As we can express as through Eigenvalue decomposition (see [7]) and the deformed after iterations of deformation can be written asthe points on the reconstructed cell boundary between the cells and , after steps of iteration would be given by,(16)

As is a scalar, the Expression (16) can be rewritten as,(17)

Equation (17) is exactly same as the set of the boundary points between Voronoi regions and for a Adaptive Quadratic Voronoi Tessellation. Thus, under the deformation condition described above, the method proposed in [7] and AQVT produce the same tessellation result. But, the major advantage of using AQVT over [7] is that, AQVT yields the 3D reconstruction result in a single step, whereas, the deformed truncated ellipsoidal model described in [7] is an iterative process. The number of iterations can be very large depending on the choice of the stopping criterion or the step-size in the deformation stage and hence [7] is, in general, a much slower algorithm. Apart from that, the 3D reconstruction results can vary widely depending on the chosen step-size for deformation in [7] and thus the quality of the reconstruction result is often unpredictable. We have experimentally observed that in [7] the least error in reconstruction is achieved when the deformation step sizes for each cell in the tissue are equal or very close to one another. This condition, as shown above, gives us the distance metric of AQVT. Therefore, AQVT provides a unique solution to the 3D reconstruction and is, in most cases, guaranteed to yield better or the same reconstruction result when compared to that in [7] at a significantly less execution time. It can also be noted that the proposed AQVT does not require any user chosen threshold or parameter to be input into reconstruction framework, making the method less ambiguous and more user friendly than [7].

5.3.1 Validation on 3D SAM Data.

There is hardly any biological experiment which can directly validate the estimated growth statistics for individual cells in a sparsely sampled multi layered cluster. In fact, the absence of a method to estimate growth statistics directly using non-computational methods in a live-imaging developmental biology framework is the motivation for the proposed work and we needed to design a method for computationally validating our 3D reconstruction technique. Once the 3D reconstruction is achieved, we can computationally re-slice the reconstructed shape along any arbitrary viewing plane by simply collecting the subset of reconstructed 3D point cloud that lies on the plane.

To show the validation of our proposed method, we have chosen a single time point dataset that is relatively densely sampled along Z (0.225 m between successive slices). Then, we resampled this dense stack at a resolution of 1.35 m to generate a sparser subset of slices that mimic the sparsity generally encountered in a live-imaging scenario. The sparsely sampled slices for a cluster of cells spanning two layers (L1 and L2) in the SAM are shown in Figure 7. The aforementioned tracking method [4] is used to obtain correspondences between slices of the same cells. Different slices of the same cells imaged at different depths in Z are shown using the same number in Figure 7(A). Next, we reconstructed the cell cluster first by the standard Voronoi tessellation using the Euclidean distance metric and then using our proposed method (AQVT) with a quadratic distance metric adapted for each of these cells. The reconstruction results for a subset of the cells for each of these methods are shown in Figures 7(B) and 7(C) respectively for a direct comparison. It can be observed that not only our proposed method very accurately reconstructed the cell shapes but also it has captured the multi-layer architecture of these SAM cells more closely in comparison to its Voronoi counterpart with the Euclidean distance metric.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 7. Reconstruction of a cluster of cells using Euclidean distance based Voronoi tessellation and the proposed AQVT for comparison of the 3D reconstruction accuracy.

(A) Segmented and tracked cell slices for a cluster of fifty two cells from the L1 and L2 layers of SAM. A dense confocal image stack is subsampled at a z-resolution of 1.35 m to mimic the ‘z-sparsity’ observed in a typical Live-Imaging scenario. The slices belonging to the same cell are marked with the same number to show the tracking results. (B) 3D reconstructed structure for a subset of these cells when reconstructed using the Euclidean distance based Voronoi Tessellation. (C) The AQVT based reconstruction result for the same cell cluster.

https://doi.org/10.1371/journal.pone.0067202.g007

To better investigate the accuracy of the reconstruction and to show the clear advantage of using the proposed method of reconstruction quantitatively, we measure distances between the 2D cross sections of the 3D reconstruction results for each cell to the Watershed segmented cell boundaries. By choosing the reslicing plane as m (different slices than those used for reconstruction) from top of the stack for the L1 layer cells and m for the L2 layer cells, we can computationally regenerate the cell walls for these imaging planes along Z. The shapes of cells in the reconstructed slices can be compared against their counterparts in the 2D segmented images and the distance between the shapes would represent the reconstruction error. There are several different distance metrics that can be used to compute the dissimilarity between two shapes such as the Procrustes distance, Hausdorff distance etc., each one having its own advantages. We have chosen to use the Modified Hausdorff Distance (MHD), one of the more popular distance measures in the Hausdorff distance family, to evaluate our reconstruction method. The advantages of MHD over other distance measures for object shape matching is described in details in [28]. It can be noted that the error, thus computed, is analogous to the reprojection error that is widely used in the 3D reconstruction community to quantify the accuracy of reconstruction.

In Figure 8(A), we have shown the computationally resliced cell slices (color coded to represent the same cells at multiple slices) at various depths for Euclidean distance based Voronoi tessellation and Figure 8(B) shows the 2D cross sections for the same cells as obtained by reslicing the 3D cell shapes in the proposed AQVT based reconstruction method. For both the image sets, the computationally obtained cross sections of each cell are superimposed by the Watershed segmentation results for the same cell slices (the ground truth). The MHD between the original and computationally generated cell slices are computed and for each of the cells in 6 different slices, this error is shown in Figure 8(C).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 8. Comparison of the 3D reconstruction accuracy for the proposed AQVT based reconstruction against Euclidean distance based Voronoi tessellation.

(A) The cells shown in Figure 7(A) are reconstructed using the Euclidean distance based Voronoi tessellation and the computationally re-sliced cells are compared against the ground truth. (B) The same cells are reconstructed using the adaptive quadratic distance based Voronoi tessellation and then computationally re-sliced along various depths in z at which we also have the ground truth (in terms of the 2D segmentation results of the cell slices), but were not used in generating the reconstruction results. The computationally obtained cell slices are shown in different colors for different cells and they are superimposed by the ground truth segmentation results. (C) The error in reconstruction (similar to the reprojection error) is computed as the Modified Hausdorff Distance (MHD) between the computationally generated cell slices and the segmentation results on the ground truth images of the same cells. The MHD, computed for each of the 52 cells at different depths in the Z-stack are plotted for both the methods to compare the methods against each other. It can be clearly observed from the plots that the reconstruction error is much larger for the Euclidean distance based Voronoi tessellation (VT) than for AQVT, especially at the terminal () slices, between consecutive layers of cells.

https://doi.org/10.1371/journal.pone.0067202.g008

It can be observed that each of the graphs in Figure 8(C) comprises of the reconstruction errors for individual cell slices for both the methods of the reconstruction. For the slices closer to the center of the cells, both the methods show similar and acceptably small reprojection error. However, in case of the terminal slices for each cell along Z, the proposed adaptive quadratic distance based reconstruction method shows a far better reconstruction accuracy (as evident in the graphs in Figure 8(C)). This improvement of result is more prominent for cells that have non-uniform shapes and growth such as elongation along any one of the axis. We further validate this observation by performing a similar experiment on a cluster of cells of various sizes and dimensions in a sample root meristem longitudinal cross sectional slice image. This experiment and the results are elaborated in the next subsection.

We have also evaluated the accuracy of our method by studying how much do the estimated volumes of the cells differ from ground truth for various levels of sparsity in the z-sampling. For the dense data described before (0.225 m between slices along z), we first estimate the ground truth cell volumes of a cluster of cells by counting the total number of superpixels per cell and multiplying that with the superpixel size (0.2×0.2×0.225 ). Then, we gradually resample the dense stack at 5 successive z resolutions (viz. 0.45, 0.675, 0.9, 1.125, 1.35 m) and for each of these resampled stacks, we reconstruct the same cells using the proposed AQVT and estimate the cell volumes. It can be noted that with each of these respective resampling, the resultant 3D stack becomes more and more sparse. For example, at 0.45 m z resolution of sampling, the average number of slices per cell is 7 or 8, whereas, for 1.35 m, the same cells are captured in an average of 3 slices. The errors in estimation of individual cell volumes at various sparsity levels are shown in Figure 9. We have plotted the means and standard deviations of the absolute errors expressed as a ratio to the ground truth cell volumes. It can be observed that at the densest resampling (0.45 m), the average estimation error is as low as 3% with a standard deviation of 1.3%. The estimation error slowly increases with increased sparsity in the stack and at a sparsity of about 3 slices/cell, the average estimation error is 5.3%, with standard deviation of around 4%. We have repeated the same experiment for Voronoi tessellation with Euclidean distance metric and the average error is much higher at around 30% (see Figure S1).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 9. Errors in AQVT estimated cell volumes from their respective ground truth volumes at various levels of sparsity.

A cluster of cells from a 3D confocal image stack with z resolution of 0.225 m is resampled to generate stacks of 5 different levels of sparsity. Each of these resampled stacks is 3D reconstructed using the proposed AQVT and volumes of each of the cells in the cluster are computed. The means and standard deviations of absolute errors in volumes (expressed as a ratio to the ground truth volumes) of all the cells for each sparser stacks are plotted. The average error slowly increases with increased sparsity but is less than 5.3% with a standard deviation of 4% even at 1.35 m/slice (i.e. 3 slices/cell on an average).

https://doi.org/10.1371/journal.pone.0067202.g009

5.3.2 Validation On 2D Root Meristem Data.

For further evaluating the performance of the proposed AQVT on tightly packed cells of heterogeneous sizes and shapes, we perform similar experiments on a 2D image of root meristem longitudinal cross section with 226 cells. The ground truth segmentation of the tissue is shown in Figure 10(A), the raw images for which can be seen in Figure 5 of [29]. From Figure 10(A), it can be seen that a large number of cells in the tissue slice (shown as - plane in Figure 10(B)) is more elongated along the longitudinal direction (shown as -axis in Figure 10(B)), whereas the other cells have similar and diameters. Again, the cells towards the the periphery are much larger than the cells in the lower central region of the tissue. To mimic the scenario of sparse sampling along one dimension, we artificially sample the segmented cells along (longitudinal) axis (see Figure 10(B)) to generate point clouds for each cell at various sparsity (, where is the average cell diameter along axis). We assume sparse clustering of sampled points per cell (analogous to spatial tracking in 3D) is given to us as the contribution of the present work is dense reconstruction of cells from sparse point clouds, which lies in the post segmentation and tracking stage of the reconstruction pipeline. For each of the resampled point clouds, we use AQVT (in ) to reconstruct the cells (Figure 10(C)). We compute modified Hausdorff distances from every reconstructed cell shape to the ground truth segmentation for quantitative evaluation of the reconstruction accuracy (Figure 10(D)). We can observe that the mean error in the reconstructed cell shapes is less than 6% of average cell longitudinal diameter and the maximum reconstruction error for most of the cells in the tissue is less that 10% for all sparsities upto (average 3 slices or lines/cell).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 10. Validation of AQVT on 2D root apex longitudinal cross section data.

(A) Ground truth segmentation of a sample cross sectional slice of root apical meristem tissue (the source images for this tissue can be found in [29]). (B) The zoomed in tissue after segmentation (B-top) and sparser point clouds per cell (in the - plane) after resampling the tissue at various -resolutions (zoomed in for clarity). (C) The cells (color-coded) are reconstructed using the proposed AQVT with the resampled point clouds as shown in B to present the change in reconstruction quality with increased sparsity in the sampled point clouds for both the larger and elongated cells towards the outer and upper part and the smaller cells towards the lower central part of the tissue. (D) Quantitative measure of reconstruction errors: the difference between actual and reconstructed cell shapes are computed using modified Hausdorff distance (MHD) and the histograms of MHDs for all the cells at every level of sparsity is plotted.

https://doi.org/10.1371/journal.pone.0067202.g010