Recognition of overlapping elliptical objects in a binary image

The primary goal of a distance transform is to identify points within a clump that might serve as centers of ellipses. Denote the binary image containing the clump by \({{\varvec{B}}}\), as illustrated in Fig. 2a. The well-known Euclidean distance transform (EDT) of \({{\varvec{B}}}\) is a grayscale image in which pixel intensity is the distance from that pixel location to the closest (in Euclidean distance) boundary pixel. Another interpretation of the intensity of a pixel is as the radius of the largest circle that fits inside the clump, with the pixel as its center. Therefore, given a clump composed of circles, the centers of circles can be identified as the local maximum pixels in the distance transform image with their intensities being the radii. However, when the clump consists of overlapping ellipses, their centers usually are not located at the local maxima of the EDT, as shown in Fig. 2b.

In [10], Talbot et al. generalized EDT by modifying the Euclidean distance to any distance metric. The elliptical distance transform (LDT) is a special case when the distance metric between two 2-D vectors \({\mathbf {p}}\) and \({\mathbf {q}}\) takes the following form with pre-specified \(\sigma\) and \(\phi\):where \(\rho\) and \(\theta\) denote the Euclidean distance and angle between \({\mathbf {p}}\) and \({\mathbf {q}}\).

Then, the pixel intensity of the LDT is the smallest distance (as defined by the above metric) between the pixel and any boundary pixel, or equivalently, is the minor axis radius b of the largest ellipse that fits inside the clump, with the pixel location as its center (x, y), \(\sigma\) as its shape parameter, and \(\phi\) as its orientation parameter. Thus, centers of ellipses with shape and orientation parameters equaling \(\sigma\) and \(\phi\) can be identified from the LDT(\(\sigma\), \(\phi\)) transform as the local maximum pixels with their intensities being the minor axis radius, as shown in Fig. 2c. A major weakness of the LDT is that its implementation based on vector propagation [10] is relatively slow, while the EDT, due to its many desirable properties like radial symmetry, has many fast implementations [28].

In this study, we propose an alternative approach to identify candidate ellipses that achieves the benefits of the LDT, while taking advantage of the faster implementation of the EDT. First, the clump is compressed by factor \(\sigma\) along the direction whose angle to the x-axis is \(\phi\). To do this, the coordinates of pixels inside the clump of \({{\varvec{B}}}\) are transformed with an affine matrix \(T\) characterized by \(\sigma\) and \(\phi\):where \({S} = \begin{pmatrix} 1/\sigma &\quad 0 \\ 0 &\quad 1 \end{pmatrix}, \;\, {\text {and}}\, \; {R} = \begin{pmatrix} \cos \phi &\quad \sin \phi \\ -\sin \phi &\quad \cos \phi \end{pmatrix}\).

Then, the transformed coordinates are rounded and rearranged on a new binary image with proper size, denoted \({{\varvec{B}}}_{\sigma ,\phi }\). Running the EDT on \({{\varvec{B}}}_{\sigma ,\phi }\), with the result denoted \({{\varvec{E}}}_{\sigma ,\phi }\), we can obtain parameters of candidate ellipses from the local maximum pixels of \({{\varvec{E}}}_{\sigma ,\phi }\) with their coordinates transformed back by \({T}^{-1}\) as center coordinates (x, y), their intensity as b, and the LDT values of \(\sigma\) and \(\phi\) as shape and orientation parameters. Figure 3 shows the images of \({{\varvec{B}}}_{\sigma ,\phi }\) and \({{\varvec{E}}}_{\sigma ,\phi }\) for three different choices of \(\sigma\) and \(\phi\).

By iterating this procedure of compression and EDT over a 2D grid search of \(\sigma\) and \(\phi\) values, we are able to establish a pool of candidate ellipses from local maximum pixels of all \({{\varvec{E}}}_{\sigma ,\phi }\). Given a fine enough grid, the optimal ellipses will be included in this pool. However, a large number of ellipses not well fitted to the clump will also be included. The distance transform of a binary image (either LDT or our method) given certain values of \(\sigma\) and \(\phi\) can contain many local maximum pixels, which means a large number of sub-optimal ellipses (\(10^4\)–\(10^5\)) included in the candidate pool, making the ellipse selection step computationally intensive. We apply two refinements to reduce the size of the set of candidate ellipses. One effective approach to diminishing the pool is to find the coordinates of local maximum pixels on smoothed versions of \({{\varvec{E}}}_{\sigma ,\phi }\). This reduces the number of candidate ellipses by an order of magnitude (\(10^3\)–\(10^4\)). This is still too large. This leads to the next section where a second approach, the overlaying method, is introduced to address the issue.

To reduce the number of candidate ellipses, we build on the approach of [10] to identify a small subset of ellipses that are better fitted to the clump than the rest. The basic idea is to assign each ellipse a score based on the degree to which the ellipse approximates the contour of the clump and then overlay all ellipses in order of their scores. As a result, the clump is covered by a few of the best-scoring ellipses on the top, while other ellipses completely overlaid or hidden by the better-scoring ellipses are excluded from the candidate pool.

To acquire the score of candidate ellipses, we first compute the EDT of the contour of the clump \({{\varvec{B}}}\), denoted by \({{\varvec{E}}}\). Then for each ellipse, we record the distance from each of its border pixels to the nearest point on the contour of \({{\varvec{B}}}\); these distances are available as the intensities of \({{\varvec{E}}}\). The kth-percentile of the border-pixel distances is assigned to the ellipse as its score, with the choice of k addressed below. A lower score for an ellipse indicates a better fit to the contour. Finally, a new image \({{\varvec{O}}}\) is constructed by overlaying all candidate ellipses in decreasing order of their scores. As shown in Fig. 1c with \(k=50\%\), the best fitting ellipses usually appear on the top of \({{\varvec{O}}}\).

The overlaying method can greatly reduce the number of candidate ellipses because we can ignore completely hidden ellipses. But it can suffer from serious under-fitting or over-fitting [3] depending on the choice of the percentile k. As illustrated in Fig. 4, k must be chosen carefully so that an ellipse that appears to fit part of the image well is not completely overlaid by others. Generally, it is difficult to find a single appropriate value of k. In order to avoid missing any essential ellipses, we compute multiple scores with different percentiles (30%, 50% and 70% for this study). And for each percentile k, the corresponding overlay image \({{\varvec{O}}}_k\) is constructed. Ellipses appearing on any of the \({{\varvec{O}}}_k\) are retained in the candidate pool while others are screened out. This modification is highly effective in ruling out non-optimal ellipses and preserving optimal ellipses, since each \({{\varvec{O}}}_k\) only contains a small number of ellipses, typically less than \(10^2\), and the use of multiple percentiles means that optimal ellipses are less likely to be completely overlaid.

Concave points are points of intersection of objects on the contour. A contour segment is represented by the two concave points that define its ends. It is assumed that pixels on the segment are from the same object. In order to extract concave points, a series of steps are carried out, as illustrated in Fig. 5. First, a sequence of coordinates of contour pixels is acquired using a radial sweep algorithm [29] in a clockwise direction (Fig. 5a). Then, the contour is approximated by a polygon represented by its vertices, also addressed as turning points, ruling out collinear points on the contour as being uninformative (Fig. 5b). Finally, a turning point is determined to be a concave point if the sweeping angle from the preceding point to the next turning point outside the clump is less than \(180^\circ\). The result is shown in Fig. 5c where each segment is presumed to include pixels from a single ellipse.

Here, we provide additional details about the polygon approximation step. In [5, 30], the polygon approximation algorithm keeps three moving pixels \(p_i\), \(p_j\), \(p_k\) and computes the distance between \(p_j\) and line \(\overline{p_i p_k}\), denoted as \(d^j_{ik}\). If the distance exceeds some threshold \(d_{\mathrm{t}}\), then \(p_j\) is deemed to be a turning point. The smaller \(d_{\mathrm{t}}\) is, the more closely the polygon approximates the contour. If \(d_{\mathrm{t}}\) is too small, the algorithm can sometimes mistake a collinear point for a turning point, or if \(d_{\mathrm{t}}\) is too large, then turning points can be missed, undermining the performance of the optimization step described in Sect. 3.2.2. To address this issue, we modified the algorithm to compute distances of all pixels between \(p_i\) and \(p_k\) from the line connecting them and compare the highest of these with \(d_{\mathrm{t}}\). In practice, the increase in computation is negligible. Let set \(P=\{p_1,p_2,\dots ,p_N\}\) denote the contour pixel sequence and Q contain all detected turning points. The algorithm employed is described in Algorithm 1. The concave points are then obtained as a subset of Q.

With the proposed algorithm, the result is less sensitive to the choice of distance threshold \(d_{\mathrm{t}}\), which should depend on the scale and roughness of the contour. In the experiments, we use a subset of the data to identify an appropriate \(d_{\mathrm{t}}\). We try to err on the side of small \(d_{\mathrm{t}}\); this can create false positive contour segments, but the optimization procedure can mitigate the effect of these false positives.

With contour segments and candidate ellipses available, the optimal ellipse subset can be acquired through a matching procedure. Given a group of ellipses, each contour segment defined by a pair of concave points has to be matched to exactly one ellipse. Each ellipse can be matched to by one or more contour segments simultaneously or by none of them. The matching algorithm requires that we define the distance between a contour segment and an ellipse. Then, the goal is to find a subgroup of ellipses from the candidate pool to minimize the total distance to all contour segments.

Let \(\varGamma = \{\gamma _1,\gamma _2,\dots ,\gamma _M\}\) denote the set of contour segments, \(\varPi = \{\pi _1,\pi _2,\dots ,\pi _N\}\) the set of candidate ellipses, and \(\varPi ^* = \{\pi _1^*,\pi _2^*,\dots ,\pi _L^*\} \subseteq \varPi\) the optimal ellipse set.

The distance between contour segment \(\gamma _i\) and candidate ellipse \(\pi _j\) is denoted by \(d_{ij}\) and defined as follows: for each pixel of \(\gamma _i\), find the smallest distance between the pixel and \(\pi _j\) (i.e., the intensity of the pixel on the EDT of \(\pi _j\)’s border), and sum them over all pixels of \(\gamma _i\), which can be written as,where |pq| is the distance between pixel p and q. Then, the loss function of a proposed solution set \({\hat{\varPi }}\) is defined as the sum of the distances from each contour segment i to its closest ellipse j in \({\hat{\varPi }}\),Simply minimizing the loss with respect to \({\hat{\varPi }}\) will cause over-fitting and result in \(\varPi\) being the optimal solution. To avoid this problem, a penalty term \(\lambda |{\hat{\varPi }}|\) is added, where \(|{\hat{\varPi }}|\) is the number of ellipses in \({\hat{\varPi }}\) and \(\lambda\) is a regularization parameter. This constraint encourages the solution to match multiple contour segments to a smaller set of ellipses and thus avoid over-fitting. The optimal set \(\varPi ^*\) is defined asProper selection of \(\lambda\) depends on the image size and noise level. As was done for the distance threshold \(d_{\mathrm{t}}\), a subset of the data is used to select the value of \(\lambda\) in Sect. 4.

The minimization problem can be transformed into an integer programming problem. First, some binary variables are introduced to formalize the matching process:Thus, \(x_{ij}\) identifies the matching of contour segments i to ellipses j, and \(z_j\) identifies the inclusion of ellipse j in the optimal set \(\varPi ^*\). The optimization over the binary variables then has the following form:This optimization problem can be solved using a branch and bound method [31], and the optimal set \(\varPi ^*\) can be obtained from the values of \(z_j\), i.e., ellipse \(\pi _j\) is included in the optimal group if \(z_j=1\). Note that the effect of a falsely detected concave point can be rectified because the two segments incorrectly partitioned by that point will be assigned to the same ellipse (as described at the end of Sect. 3.2.1).

To evaluate the performance of DTECMA and compare with other approaches, a synthetic dataset of 1600 binary images was generated. Each image contains one connected region, which is a union of multiple overlapping ellipses whose parameters are known. The dataset consists of 8 groups of 200 images, each group having in common the number of ellipses within the images, ranging from 2 to 9. Images with more ellipses present increasing complexity and greater difficulty in ellipse recognition. Ellipses were generated at random locations with parameters a, \(\sigma\) and \(\phi\) uniformly distributed on (12.5, 37.5), (1, 3) and (0, 180), subject to a constraint on the degree of overlap. The overlapping rate of each ellipse, defined as the proportion of the area overlapped with other ellipses, is controlled to stay below 60% to avoid completely overlaid ellipse. Examples of synthetic images and their ground truth are shown in Fig. 9a, b.

Several quantitative criteria have been used for evaluation of approaches to identifying overlapping elliptical objects. The Jaccard index is a region-based measure that quantifies the overall coverage of the ellipse-fitting image \(I_{\mathrm{f}}\) (the union of the selected ellipses \(\varPi ^*\)) to the original image \(I_{\mathrm{o}}\) as follows:Higher values of the Jaccard index indicate a better fit. Two other contour-based metrics, Hausdorff distance and mean absolute contour distance (MAD), introduced in [1, 4] are also used. They measure the overall distance between the contours of \(I_{\mathrm{f}}\) and \(I_{\mathrm{o}}\). They are defined as:where D(i) denotes the minimal Euclidean distance of pixel i to the contour of \(I_{\mathrm{o}}\) and \(C_{\mathrm{f}}\) denotes the contour of \(I_{\mathrm{f}}\). Lower values of the contour-based measures indicate a better fit. A drawback of all of these metrics is that, instead of checking whether each ellipse is well fitted to the original image, they only evaluate the fit of the set of ellipses. In certain cases, a poor result, where the selected ellipses under-fit or over-fit the image, may still achieve good aggregate measures, as shown in Fig. 6.

To assess performance for each ellipse instead of the whole set, we reconsider the evaluation process from a clustering perspective and propose to use the adjusted Rand index (ARI) [34] as a contour-based performance measure. Given the set of contour pixels of a binary image consisting of overlapping ellipses, the ground truth clustering of the set is defined to be a clustering with pixels from the same ellipse being clustered into the same group and pixels from different ellipses being clustered into different groups (intersecting pixels can be dropped or randomly assigned). The result of an ellipse-fitting algorithm applied to the image also corresponds to a clustering of the contour pixels: each contour pixel is assigned to the nearest ellipse in the solution set and the set of contour pixels assigned to a given ellipse can be viewed as a cluster. For example, in the left-hand side image of Fig. 6 all contour pixels belong to one cluster according to the dashed black line, while in the right-hand side image they are assigned into 3 clusters. In DTECMA, the cluster assignments are given by the binary variables \(x_{ij}\). The Rand index (RI) [35] is a measure of the similarity between two clusterings. Given a set of n elements, the RI between two clusterings X and Y is computed as follows:where a is the number of pairs of elements that are placed in the same cluster in X and in the same cluster in Y, and b is the number of pairs placed in different clusters in X and in different clusters in Y. The ARI is a modified version that corrects the clustering similarity measure for chance agreement under the permutation model [36]:The clustering perspective on contour pixels and ARI provides an approach to evaluating how close the fitting result is to the ground truth, which we believe is more objective than visual inspection and more relevant than previous metrics (see Fig. 6). For this experiment, ARI is used as the primary evaluation criterion, with Jaccard index, Hausdorff distance and MAD serving as supplementary metrics.

There are two parameters that have a significant impact on performance of DTECMA. These are the distance threshold \(d_{\mathrm{t}}\) of the polygon approximation (Sect. 3.2.1) and the regularization parameter \(\lambda\) of the optimization approach (Sect. 3.2.2). For the simulated data study, we use half of the synthetic images (8 groups of 100), referred to as the validation set, to select these parameters, while the rest of the images, referred to as the test set, are used for evaluation.

The distance threshold \(d_{\mathrm{t}}\) used in the polygon approximation determines the maximum distance between a turning point and the line connecting its two neighboring turning points. It plays a vital role in concave point extraction. Since the ground truth (ellipse parameters) of the simulated data is known, the true concave points are in fact the intersection points of ellipses on the contour. Concave points of an image can be viewed as a partition of the contour, namely a clustering, so ARI can be used as a performance measure for concave point extraction as it was ellipse fitting. The plot on the left of Fig. 7 shows average ARI as a function of \(d_{\mathrm{t}}\) for the 8 groups with different number of ellipses. The results strongly support the choice \(d_{\mathrm{t}} = 1\) for this dataset.

The regularization parameter \(\lambda\) balances the loss function \(L({\hat{\varPi }})\) and the number of ellipses. The loss function term will depend on the size of the image, so the proper value of \(\lambda\) should be related to the size of each image. To address this issue, a new parameter \(\lambda ^*\) is defined as follows:where S is the area of the binary image. Now, a value of \(\lambda ^*\) can be selected to perform well throughout the dataset. The plot on the right-hand side of Fig. 7 shows the effect of different values of \(\lambda ^*\) on the performance of DTECMA in terms of average ARI. \(\lambda ^*\) was set to 0.5 to obtain the best performance. It is noteworthy that \(\lambda ^*\) values between 0.1 and 1 yield similar performance in terms of ARI, which shows the robustness of the results with respect to this parameter.

Two state-of-the-art methods for detecting overlapping elliptical objects, with code available online, are compared with DTECMA on the synthetic test set. The DEFA model proposed by Panagiotakis et al. [1] is a parameter-free method developed to segment touching cells by ellipse fitting. The method proposed by Zafari et al. [20] integrated three components in an optimization framework that can be solved by a branch and bound (BB) algorithm. It applies techniques from the authors’ previous work [9, 18] on radial symmetry and concave points, and achieved superior performance among the methods compared in [20]. Model parameters for BB were tuned to achieve the best performance with respect to ARI on the validation set. Both methods take a binary image as input; hence, the comparison does not involve the effect of image thresholding.

Four measures including ARI, Jaccard index, Hausdorff distance and MAD were computed for each of the three methods on each image and averaged within each data group of the test set, as shown in Fig. 8. DTECMA achieved consistently superior performance in all measures. As the number of ellipses in the synthetic images increases, potentially complicating the task, DTECMA remains reliable. Another interesting observation is that BB outperforms DEFA in terms of ARI but not for the three traditional measures. This is due to the limitation of traditional measures described in Sect. 4.2.2. Figure 9 provides some examples of the fitting results. Compared with BB, DEFA appears prone to serious under-fitting when ellipses overlap too much, but still manages to cover the image nicely, hence gaining higher scores on traditional measures. BB is more accurate than DEFA in ellipse fitting, but sometimes fails to detect crucial concave points and to group small segments, and as a result does worse on the aggregate measures.

Two public cell data sets with manual labelling are published in [37] as a benchmark for segmentation algorithms. Table 1 provides basic information about the two data sets. The shape of U20S cells is highly varying and irregular. The NIH3T3 cells are more consistent in shape, but binarization of the NIH3T3 images is more challenging because of the varying image intensity.

To transform grayscale images to binary images, we employ the modified Bradley segmentation method described in [1], which is a real-time adaptive thresholding method and has superior segmentation performance on the data sets. After applying an ellipse fitting procedure (e.g., DTECMA or DEFA), touching cells (represented by two ellipses) are split by the line on which each point has the same algebraic distance to both ellipses.

For cell data, the ground truth is annotated on the grayscale image instead of the binary image, which thus requires different evaluation criteria than the ones used with the synthetic data. For example, the Jaccard Index, Hausdorff distance and MAD were used in [1] to evaluate segmentation performance but not useful for assessing cell splitting performance. The ARI cannot be directly computed from the available ground truth information and thus cannot be used either. To assess cell splitting performance, we employ the definitions from [1] for computing the number of false positives (FP) (spuriously segmented cells) and the number of false negatives (FN) (cells that have not been segmented). The FP and FN counts of all images are averaged as a performance measure for cell splitting.

The two parameters of DTECMA are tuned on each data set using just two images. DTECMA is compared with DEFA and two other top performing methods Three-step [38] and LLBWIP [4] that were also used for comparison in [1]. Figure 10 shows an example from the U20S data set. It is worth mentioning that the binarization step plays a vital role in the final results, since it helps the splitting algorithm to distinguish the body of cells from background noise. Despite the shape variation of cells, DTECMA manages to accurately split most touching cells. Table 2 gives the average number of FP and FN for the data sets. We reproduce the result of DEFA and also report the results of Three-step [38] and LLBWIP from [1]. DTECMA provides a notable improvement over DEFA.