Modeling analysis of ant system with multiple tasks and its application to spatially adjacent cell state estimate

Abstract

The problem of multi-cell tracking plays an important role in studying dynamic cell cycle behaviors. In this paper, a novel ant system with multiple tasks is modeled for jointly estimating the number of cells and individual states in cell image sequences. In our ant system, in addition to pure cooperative mechanism used in traditional ant colony optimization algorithm, we model and investigate another two types of ant working modes, namely, dual competitive mode and interactive mode with cooperation and competition to evaluate the tracking performance on spatially adjacent cells. For adjacent ant colonies, dual competitive mode encourages ant colonies with different tasks to work independently, whereas the interactive mode introduces a trade-off between cooperation and competition. In simulations of real cell image sequences, the multi-tasking ant system integrated with interactive mode yielded better tracking results than systems adopting pure cooperation or dual competition alone, both of which cause tracking failures by under-estimating and over-estimating the number of cells, respectively. Furthermore, the results suggest that our algorithm can automatically and accurately track numerous cells in various scenarios, and is competitive with state-of-the-art multi-cell tracking methods.

1 Introduction

Cell behavior is an important facet of biomedical research, from basic biological research to advanced industrial applications such as drug discovery, genomics, proteomics and tissue engineering. Analysis of cellular behavior faces many challenges. Some of the image acquisition techniques require that images are captured in a controlled environment to deal with biological phenomena. A frequent outcome is poor image quality. Cells leaving or entering the field-of-view will vary the local cell population density. Complex cellular topologies such as shape deformation and partial overlap present topological challenges. Cells dividing, moving close or colliding further complicate the situation. The computational complexity of cell tracking algorithms is increased by uneven movement of the cells. Conventional and manual techniques are tedious and time consuming, and they limit the amount of data available for analysis. For efficiency and accuracy, the development of automated tracking methods that eliminate the bias and variability to a certain degree is of great importance.

During the past few years, researchers have developed many algorithms for automated cell tracking. For a comprehensive survey on recent work, the reader is referred to [1–7]. Tracking based on detection methods is discussed in [1–3, 8]. Classical tracking algorithms usually handle the detection [9, 10] and tracking tasks separately, but tracking may fail under problematic imaging conditions such as large cell density, cell division events, or segmentation errors. Tracking methods based on evolving models simultaneously handle both detection and tracking. These approaches include mean-shift [4, 11], active contours [5], and level sets [6]. These methods require extra heuristics to prevent contacting boundaries from merging when two or more objects approach very closely. Tracking based on Bayesian probabilistic framework methods has also been proposed [7, 12–14], and is more robust to low resolution and high signal-to-noise (SNR) scenarios than other tracking methods.

Ant colony optimization (ACO) is a biologically-inspired optimization approach based on the self-organizing capabilities of ant colonies in their search for food. Since Dorigo pioneered this approach in [15], ant colony methods have been successfully applied in diverse combinatorial optimization problems [16–18] as well as non-optimization problems [19–27].

During cell image sequencing, two or more cells will very likely contact or present occlusions. In such cases, the image is not easily associated with spatially adjacent images because the joint observation cannot be easily segmented. Because the components of corresponding cell states are now coupled, the tracking of spatially adjacent cells or cell occlusions becomes a challenging task, rendered more complicated by low SNR in the image data. Although some effective cell automated methods have been developed in real tasks, we are aware of few reports on the application of ant behavior to multiple-cell tracking with spatially adjacent cells. In natural ant colonies, the movement of each ant is stochastic and typically non-linear. Similarly, in most cell image sequences, each cell moves in an irregular way and displays non-linear dynamic behavior. Furthermore, to some extent, the trails of individual ants are analogous to the tracks of individual cells. Motivated by these similarities, we propose that individual cell parameters in sequential frames could be adaptively and accurately captured by an ant system algorithm. To this end, we develop a novel ant system with multiple tasks that jointly estimates the number of cells and their individual states in cell image sequences. Depending on the initial distribution of the ant colony, the colony is roughly divided into several groups, each assigned the task of finding a potential cell through the defined ant working mode. To improve the performance of our proposed ant system, we establish three types of ant working modes, namely, pure cooperation mode, dual competitive mode and interactive mode with cooperation and competition. These modes are applied to an ensemble of spatially adjacent cells. Finally, the multiple similar tasks are merged to extract the multi-cell state and spatially adjacent cells.

The main contributions of our method are summarized as follows: (1) applying an ant system with multiple tasks to the tracking of spatially adjacent cells; (2) developing three types of ant working modes; pure cooperation, dual competition and an interactive mode with cooperation and competition to improve the performance of the algorithm.

The remainder of this paper is organized as follows. Section 2 overviews related work on cell tracking and mode design of ACO methods. The conventional ACO algorithm is briefly introduced in Sect. 3. Section 4 describes our proposed ant system with its multiple tasking algorithm and examines the three ant working modes. Section 5 presents the tracking results generated from our three proposed ant working modes. Also in this section, the performance of our proposed algorithm is compared with that of other methods. Our proposed algorithm for tracking spatially adjacent cells is summarized in Sect. 6.

2 Related works

Works related to our method follow one of two broad approaches.

The first is developing tracking algorithms for spatially adjacent objects. The accurate tracking of spatially adjacent objects is one of the most difficult problems in multi-object tracking, and has been extensively investigated in recent years. Here, we present a brief survey of these works. Huang et al. [28] presented an approach for tracking varying numbers of objects through temporally and spatially significant occlusions. Bose et al. [29] solved the labeling problem when different objects merge or split using a graph model, but the computational cost grows exponentially with the number of objects. Rather than calculating all possible solutions to the labeling problem, Qian et al. [30] developed a spatiotemporal Markov chain Monte-Carlo (MCMC) data association algorithm that efficiently samples the solution space. The interactive tracking algorithm developed by Wei et al. [31], adopts a magnetic-inertia potential model to solve the multiple object labeling problem in the presence of occlusions. Khan et al. [32] proposed a multiple-people tracking method that handles occlusion and lack of visibility in crowded and cluttered scenes. However, the algorithm fails if two or more people approach too closely to be segmented as separate entities. The tracking of multiple persons on a mobile robot equipped with a combination of color and thermal vision sensors was investigated by Cielniak et al. [33], but appropriate action when a person is occluded behind another person remains an unsolved problem. Tao et al. [34] presented a real-time system for multiple-object tracking that copes with long duration and complete occlusion without a priori knowledge of the shape or motion of objects. It is noted that most methods used in multiple people tracking [31–36] cannot be extended directly to multi-cell tracking due to cell deformation, small cell size, cell feature deficiency and cell mitosis, etc. Thus, Dufour et al. [37] presented a fully automated technique for segmenting and tracking cells in 3-D+time microscopy data. This method uses coupled active surfaces with or without edges, together with a volume conservation constraint and several optimizations to handle touching and dividing cells, and cells entering the field of view during the sequence. In the method of Nguyen et al. [38], multiple cell collisions, cells are automatically tracked by modeling the appearance and motion of each collision state and by testing collision hypotheses of possible state transitions. Although some of the above algorithms have resolved special challenges in spatially adjacent objects, they are problem-dependent and not applicable to generic cell tracking problems.

The second broad approach to the tracking problem focuses on various models of ant behavior to solve different problems. In the model of Kanade et al. [22], all ants have memory and are used primarily to find cluster centers combined with the fuzzy C-Means algorithm in feature space. Handl et al. [33] proposed a model in which ants collect and deposit items according to colony similarity measures in their local environment. Neither of these ant-based clustering methods utilizes pheromone information. By contrast, the model of Zhang et al. [39], designed for fast text clustering, includes a pheromone weighting function and a weighting factor that guides the direction of the ant’s movement away from random, and toward the direction of high pheromone concentration (here, the “pheromones” represent the text vectors). Lee et al. [40], proposed a model based on three types of pheromones that handles the efficient-energy coverage problem in wireless sensor networks. The local pheromone helps an ant to organize the coverage set with fewer sensors. Of the two global pheromones, one is used to optimize the number of required active sensors at each point of interest; the other is used to assemble a previously-determined number of sensors at each point of interest. In the model of Misra et al. [41], pheromones and path time delays are used to construct fault-tolerant routing in a mobile ad hoc network. Ramos et al. [42] presented an extended model for digital image habitats, in which artificial ants can perceive and react to the environment. Merkle et al. [43] focused on the single-machine total-weighted tardiness problem. In their model, ants are guided through the decision space by global pheromone information rather than by local pheromone information alone. In the above methods, the probability that any ant will make a decision is affected by pheromone information. In our proposed approach, the amount of pheromone not only affects an ant’s behavior but also allows direct extraction of cell states from the resulting pheromone field.

3 Conventional ACO algorithm

The conventional ACO algorithm simulates the foraging behavior of intelligent multi-agent systems, whereby ants communicate among themselves through the environment by depositing a chemical substance, known as a “pheromone”. The pheromone concentration increases in paths that are frequently traveled by the ants, and decays in paths that become deserted. The higher the pheromone level along a path, the higher the probability that a given ant will follow that path. Thus, using pheromone information alone, ants can search for the shortest path from their nest to a food source.

One of the first problems to be successfully solved by ACO was the traveling salesman problem (TSP) [17], which seeks the optimal path that traverses all cites once before returning to the starting city. Assuming that ant k is currently located in city i, it selects the next city j with probability

$$ p_{ij}^{k} = \left \{ \begin{array}{l@{\quad }l} \frac{[\tau_{ij}]^{\alpha} [\eta_{ij}]^{\beta}}{\sum_{k \in \varOmega_{k}} [\tau_{ik}]^{\alpha} [\eta_{ik}]^{\beta}}, & \mathrm{if}\ j \in \varOmega_{k} \\ 0, & \mathrm{otherwise} \end{array} \right . $$

(1)

where Ω _k denotes the set of cities unvisited by ant k,τ _ij is the amount of pheromone laid along edge (i,j),η _ij is a heuristic function variable, and α and β are real parameters that determine the relative influences of pheromone τ _ij and heuristic η _ij , respectively, on the decision of ant k. After all ants have constructed their individual tours, the corresponding pheromone trail is updated as

$$ \tau_{ij} \leftarrow \zeta \tau_{ij} + \Delta \tau_{ij}\quad \mathrm{where}\ 0 < \zeta < 1 $$

(2)

where ζ is the pheromone persistence coefficient, which simulates pheromone evaporation in the real world. Δτ _ij is the amount of pheromone added to the trail, defined as

$$ \Delta \tau_{ij} = \sum_{k} \Delta \tau_{ij}^{k} $$

(3)

where $\Delta \tau_{ij}^{k} = Q/L_{k}$ if edge (i,j) is traveled by ant k, and 0 otherwise. The fixed constant Q controls the delivery rate of the pheromone, and L _k is the tour length of ant k. The above process is repeated until specified termination conditions are reached.

4 Methods

In this section, we introduce a novel ant system with multiple tasks that estimates the multi-cell parameters. The ant colony is initially divided into several groups by K-means clustering [44]. Each group is assigned a single task; that of searching for a potential cell. These ant groups accomplish their different tasks through their individual pheromone fields and total pheromone field, adopting our proposed ant working modes. Finally, the estimates of multi-cell state and the number of cells at each frame are extracted through merging multiple similar tasks. It is noted that our algorithm builds solutions in a parallel way on N+1 pheromone fields (where N is the initial number of divided ant groups), whereas the conventional ACO algorithm computes solutions in an incremental way on only one pheromone field. The overview of our proposed algorithm is explained in Fig. 1.

Fig. 1

The one-cycle overview of our proposed algorithm

4.1 Initial distribution of ant colony

Background subtraction is commonly used to reduce the search-space and to focus on features of interest in video analysis [45–47]. Moving objects are readily segmented by subtracting the background from the current frame in all regions where the current frame matches the reference frame. Since the background signals in most cell image sequences are slowly varying, this problem can be solved by simplistic, static-background models. Here we apply a recursive technique called the approximate median method to realize fast background subtraction [48]. In this method, each pixel in the background model is compared to the corresponding pixel in the current frame, and is incremented or decremented by one if the new pixel is larger or smaller than the background pixel, respectively. As the iteration evolves, the intensity of a pixel in the background model fluctuates about its median value.

The approximate median foreground detection algorithm compares the current frame to the background model and further identifies the foreground pixels I ₁(i) and binary image pixels I ₂(i) as

$$ I_{1}(i) = \left \{ \begin{array}{l@{\quad}l} I(i), & \mathrm{if}\ \vert I(i) - B(i) \vert > \mathit{Th} \\ 0, & \mathrm{otherwise} \end{array} \right . $$

(4)

$$ I_{2}(i) = \left \{ \begin{array}{l@{\quad}l} 1, & \mathrm{if}\ \vert I(i) - B(i) \vert > \mathit{Th} \\ 0, & \mathrm{otherwise} \end{array} \right . $$

(5)

where I(i) denote the pixels in the current frame, B(i) are the background pixels estimated by the recursive technique

$$B(i) = \left \{ \begin{array}{l@{\quad}l} B(i) + 1 & \mathrm{if}\ I(i) > B(i)\\ B(i) - 1 & \mathrm{if}\ I(i) < B(i) \end{array} \right . $$

and Th is a predefined threshold. If the absolute difference between the pixel intensity in the current frame and the background exceeds the predefined threshold Th, the foreground pixel I ₁(i)=I(i), otherwise I ₁(i)=0. The binary image pixel I ₂(i) also evolves by Eq. (5).

Without loss of generality, we demonstrate how the initial ant colony evolves by a simple example. The corresponding background and foreground obtained by applying the approximate median method to an original cell image (Fig. 2(a)) is shown in Figs. 2(b) and 2(c), respectively. We further assume that an ant is located at pixel i if I ₂(i)=1 in the binary image. Thus, a specified number of ants are “born” in the current frame, as illustrated in Fig. 2(d). These ants are further divided into N subgroups by the K-means clustering method, as shown in Fig. 3. As we observe, the left-bottom ant subgroups are well separated due to large space distance. However, according to the enlarged region A in Fig. 3, those ants corresponding to three spatially adjacent cells have been over-divided into seven subgroups. While such inconsistency typically incurs large errors in the estimated number of cells and their individual states, our proposed ant system can overcome these limitations by assigning different tasks to separate groups, as demonstrated below.

Fig. 2

Generation of initial ant colony (Th=23)

Fig. 3

Results of K-means clustering (N=12)

4.2 Modeling of ant system with multiple tasks

In this section, three types of working modes in an ant system with multiple tasks (AS-MT) are proposed and investigated in detail. The ant working environment in the current cell image (i.e. the pheromone field), is also defined. Each ant can move directly towards one of its neighbors at each time, and any pixel can be visited simultaneously by several ants that have been guided by our proposed pheromone update mechanism.

4.2.1 Pure cooperative mode (PCM) in AS-MT

In the pure cooperative mode, all ants assigned a specific task follow the same pheromone field, as in the traditional ACO algorithm. Without loss of generality, we denote the pheromone field where ants with task s work by τ ^s (s=1,2,…,N), so the pheromone field τ ^s is reduced and equivalent to the total one represented by τ in the pure cooperative mode. Therefore, in the t-th iteration, suppose that an ant with task s is now located at pixel i. The ant will move from pixel i to one of neighboring pixels according to the following probability.

$$ P_{i,j}^{s,k}(t) = \left \{ \begin{array}{l@{\quad }l} \frac{[\tau_{j}(t)]^{\alpha} [\eta_{j}(t)]^{\beta}}{\sum_{j \in H(i)} [\tau_{j}(t)]^{\alpha} [\eta_{j}(t)]^{\beta}},& \mathrm{if}\ j \in H(i) \\ 0, & \mathrm{otherwise} \end{array} \right . $$

(6)

where H(i) denotes the set of neighbors of pixel i, τ _j (t) is the total sum of pheromone amount left by all ants undertaking different tasks on pixel j, η _j is the heuristic information of pixel j (defined later), and parameters α and β denote the relative importance of heuristic and pheromone information, respectively.

Since all ants with multiple tasks share the same pheromone field and move to a neighboring pixel with the same probability, all ants indiscriminately cooperate in the various tasks. If we combine all ants with different tasks together, it is predictable that the obtained result is identical to the one of traditional ACO algorithm.

4.2.2 Dual competitive mode (DCM) in AS-MT

To discern spatially adjacent cells, we regulate the behavior of each ant group by reinforcing the importance of their individual pheromones on their decision making. To this end, we introduce two terms; the ratio of pheromone level of a given task to the total pheromone level, and the absolute importance of the pheromone levels of remaining tasks. Suppose that an ant with task s is now at pixel i, then the ant will move to pixel j with the probability

$$ P_{i,j}^{s,k}(t) = \left \{ \begin{array}{l@{\quad }l} \frac{ [ \frac{\tau_{j}^{s}(t)}{\tau_{j}(t)} ]^{\alpha} \eta_{j}^{\beta} [ \frac{Q}{\tau_{j}(t) - \tau_{j}^{s}(t)} ]^{\gamma}}{\sum_{j \in H(i)} [ \frac{\tau_{j}^{s}(t)}{\tau_{j}(t)} ]^{\alpha} \eta_{j}^{\beta} [ \frac{Q}{\tau_{j}(t) - \tau_{j}^{s}(t)} ]^{\gamma}}, & \mathrm{if}\ j \in H(i)\\ 0, &\mathrm{otherwise} \end{array} \right . $$

(7)

where $\tau_{j}^{s}(t)$ denotes the amount of pheromone deposited by ants with task s on pixel j, τ _j (t) is the sum of pheromone level of all tasks on pixel j, i.e., $\tau_{j}(t) = \sum_{s = 1}^{N} \tau_{j}^{s}(t)$, H(i) and η _j follow the same definitions as in Eq. (6). The parameters α, β and γ regulate the relative importance of corresponding terms. Note that $\frac{\tau_{j}^{s}(t)}{\tau_{j}(t)}$ indicates the ratio of the pheromone level deposited by task s individuals to the total pheromone level in the t-th iteration. Thus, the higher the pheromone level deposited by ants undertaking task s, the more important this pheromone field becomes in ant decision making. The quantity $\frac{Q}{\tau_{j}(t) - \tau_{j}^{s}(t)}$ denotes the absolute importance of the pheromone level deposited by ants completing remaining tasks (where Q is the balance coefficient). From this expression, we note that the larger the pheromone quantity deposited by task s, the less the remaining tasks contribute to ant decision. In addition, both the above relative and absolute terms of pheromone amount of a given task are introduced to reinforce the repulsion on the foreign pheromone, which encourages ants with different tasks to compete with each other to find their individual areas of cell occurrence while establishing a solution.

4.2.3 Interactive mode with cooperation and competition (IMCC) in AS-MT

In our defined interactive mode combining cooperation and competition, ants with different tasks are modeled to work together with appropriate cooperation and repulsion. The repulsion term is characterized by $\frac{\tau_{j}^{s}(t)}{\tau_{j}(t)}$ defined in the same way as in DCM, while cooperation is represented by the total pheromone τ _j (t). Therefore, the model of ant decision is a function of the pheromone amount τ _j (t), the heuristic information function η _j , and the pheromone amount of the current corresponding task $\tau_{j}^{s}(t)$ formulated as

$$ P_{i,j}^{s,k}(t) = \left \{ \begin{array}{l@{\quad}l} \frac{ [ \tau_{j}(t) ]^{\alpha} \eta_{j}^{\beta} [ \frac{\tau_{j}^{s}(t)}{\tau_{j}(t)} ]^{\gamma}}{\sum_{j \in H(i)} [ \tau_{j}(t) ]^{\alpha} \eta_{j}^{\beta} [ \frac{\tau_{j}^{s}(t)}{\tau_{j}(t)} ]^{\gamma}},& \mathrm{if}\ j \in H(i)\\ 0, & \mathrm{otherwise} \end{array} \right . $$

(8)

where H(i), $\tau_{j}^{s}(t)$, τ _j (t) and η _j follow the same definitions as in Eq. (7), and parameters α, β and γ regulate the relative importance of their corresponding terms. It is noted that, during the process of searching solutions, each ant of a given task is assumed to sense some information from its neighboring pixels such as the total pheromone amount τ _j (t), the ratio of pheromone level of a given task to the total pheromone level $\frac{\tau_{j}^{s}(t)}{\tau_{j}(t)}$, and the heuristic function η _j . According to the definition of IMCC, if the relative proportion of pheromone s and the total pheromone amount both remain high at pixel j, the ant of task s is less likely to select pixel j as its next position than when the relative proportion alone is high, since cooperation is offset to some extent by competition with ants undertaking different tasks.

4.2.4 Pheromone update mechanism in AS-MT

In our approach, we assume that N ant groups are utilized to track n multiple objects (N>n), and each group has its own pheromone field, thus we have total N+1 pheromone fields working in parallel as shown in Fig. 1. In areas occupied by spatially adjacent cells, an ant visiting a pixel will deposit a specified amount of pheromone, which changes not only the pheromone intensity of the pixel, but also the pheromone intensity of nearby pixels during the next iteration. In this manner, information is exchanged both within each group and among different groups. To model this happening in real ant world, the pheromone propagation is developed to produce bounded pheromone field, which obviously differs from the one in traditional ACO algorithm, and defined as

$$ \tau_{j}^{s}(t + 1) = \rho \tau_{j}^{s}(t) + r_{j}^{s}(t) + q_{j}^{s}(t) $$

(9)

where ρ(0<ρ<1) is the pheromone persistence coefficient. The quantity 1−ρ represents the evaporation coefficient which simulates the evaporation process of pheromone in real world. $r_{j}^{s}(t)$ denotes the pheromone external input to pixel j at the t-th iteration, given as follows:

$$ r_{j}^{s}(t) = \sum_{k} \Delta r_{j}^{k,s}(t) $$

(10)

where $\Delta r_{j}^{k,s}(t)$ describes the amount of pheromone deposited by ant k with task s on pixel j. Once ant moves to pixel j it will deposit an amount of pheromone $\Delta r_{j}^{k,s}(t) = \Delta \tau_{0}$, otherwise it remains on its original pixel with $\Delta r_{j}^{k,s}(t) = \Delta \tau_{1}$, where (in our tests on cell image data, we set Δτ ₀=0.09, Δτ ₁=0.001).

Compared with the traditional ACO algorithm, it can be seen that the term of $q_{j}^{s}(t)$ models the propagation input to pixel j which improves the inter-communication among nearby ants and its form is defined as:

$$ q_{j}^{s}(t + 1) = \sum _{j' \in H(j)} \frac{P}{\vert H(j') \vert } \bigl(r_{j'}^{s}(t) + q_{j'}^{s}(t)\bigr) $$

(11)

where P denotes the propagation coefficient with 0<P<1, H(j′) denotes the set of neighbors of pixel j′ including position agent j, and |H(j′)| is the cardinality of H(j′). Thus$, \frac{P}{\vert H(j') \vert }$ characterizes the averaged diffusion proportion of total received pheromone intensity at pixel j during the t-th iteration to its neighboring individuals.

It is observed from Eq. (11), the propagation pheromone field at the next iteration is the propagation results of both the field of itself and the external input pheromone field at the current iteration. So, Eq. (11) can be divide two parts and rewritten as

$$\begin{aligned} q_{j}^{s}(t + 1) =& \sum_{j' \in H(j)} \frac{P}{\vert H(j') \vert } r_{j'}^{s}(t) + \sum_{j' \in H(j)} \frac{P}{\vert H(j') \vert } q_{j'}^{s}(t) \\ \triangleq & \Delta \over = \mathit{Pr}_{j}^{s}(t) + Pq_{j}^{s}(t) \end{aligned}$$

(12)

The above models of pheromone aggregation and propagation lead to an important conclusion: the amount of pheromone at any pixel in the environment is bounded, which guarantees stable extraction of each cell state.

Proposition 1

If both functions τ(t+1)=ρτ(t)+r(t)+q(t) and q(t)=Pr(t−1)+Pq(t−1) hold, where r(t)=R is constant, and ρ, P∈(0,1), q(0)=q ₀, τ(0)=τ ₀, q ₀>0, τ ₀>0, then τ(t+1) is bounded.

The proof of this proposition is provided in the Appendix.

4.3 The implementation issues of our algorithm

4.3.1 Heuristic information for ant decision

In probabilistic models, heuristic function is another important parameter for ant decision. Without loss of generality, we assume that each ant can achieve cell histogram and calculate the difference between the area represented by any pixel and the cell sample blobs which is a database of training blobs provided by the user. If an ant moves from pixel i to pixel j, the corresponding heuristic value is defined as

$$ \eta_{j} = e^{ - u(1 - \frac{1}{\vert T \vert }\sum_{i = 1}^{\vert T \vert } \sum_{j = 1}^{M} \min (w_{i}(j),\tilde{w}_{i}(j)))^{\upsilon}} $$

(13)

where μ and υ are the adjustment coefficients designed to achieve a higher likelihood difference comparison between the candidate blob and cell sample blobs,η _j lies in the range of 0 and 1$, \tilde{w}_{i}(j)$ denotes the value of the j-th element of $\tilde{w}_{i}$ in cell sample pool,w _i (j) denotes the histogram at pixel j, M is the total number of elements in histogram w, and |T| is the number of cell samples in the template pool.

4.3.2 Merging and pruning processes

It can be observed from Fig. 3 that ants related to three spatially adjacent cells are divided into seven groups, and this directly results in large errors in cell number or labeling. Such over-segmentation can be eliminated to some extent by merging multiple groups of similar tasks after all pheromone fields have been formed. Considering the different ant pheromone fields, if more than one ant group tends to search for the same cell, the corresponding pheromone fields are probably partially overlapped, and the absolute distance between pheromone peaks is relatively small. However, spatially distant ant groups naturally search for different objects. In these cases, the peak distances between ant pheromone fields are easily discriminated and well separated. Therefore, we introduce the overlapping ratio O _overlap , which determines the extent to which two pheromone peak blobs coincide. In our experiments, two pheromone peak blobs are merged if the overlapping ratio O _overlap >σ, where the threshold σ is set to σ=0.3 in our investigated cell image data.

To remove the false alarms caused by noise and clutter, we adopt a pruning procedure. Suppose that cell size is known a priori. If the number of ants in a group is below the threshold, the irrelevant object is removed by the pruning process. Finally, to establish the individual trajectories of cells of interest, the data in sequential frames are associated by the easily-implemented nearest neighboring method.

To visualize our proposed algorithm in a full view, we summarize the procedure in Table 1 according to the flowchart in Fig. 1.

Table 1 Pseudo-code of our proposed algorithm (not considering data association)

5 Results and discussions

In this section, our proposed algorithm is tested on two challenging low-SNR image sequences containing spatially adjacent and dividing cells, cells of varying shape, varying numbers of cells in different frames, and other complications. We first investigate the effects of the three ant working modes on the estimated performance. Next, the performance of our algorithm is compared among the three modes, and with that of state-of-the-art approaches. Finally, the parameter settings are discussed in detail.

5.1 Estimate results

To evaluate the tracking accuracy between frames, we adopt three measure criterions, namely, label switching rate (LSR), lost tracks ratio (LTR) and false tracks ratio (FTR). The label switching rate is the number of label switching events normalized over the total number of ground truth tracks crossing events, which happen when two objects get very close to each other, sometimes merging into one object. After they are separated, one object is treated as a new object and its label is changed. The lost tracks ratio is the number of tracks lost over the total number of ground truth tracks. The false tracks ratio is the number of false objects that are tracked over the total number of ground truth tracks. All experiments were performed in MATLAB (R2012a) on a 1.7 GHz processor computer with 4 G random access memory.

In case 1, the experiment includes image sequences of closely moving cells and varying numbers of cells, which compares the accuracy and robustness of three types of ant working modes, PCM, DCM and IMCC. The comparison results for tracking performance of three types of modes are presented in Table 2 and Figs. 4, 5, 6 to 7.

Fig. 4

Tracking results of model IMCC

Fig. 5

Tracking results of model PCM

Fig. 6

Tracking results of the DCM model

Fig. 7

Comparison of cells number estimates by various modes

Table 2 Comparison results for tracking performance of three modes

The LSR, LTR and FTR in each frame are recorded throughout 50 Monte-Carlo simulations, and their averages are listed in Table 2. In PCM mode, the parameters are set as ρ=0.7, P=0.6, α=2.5, β=1.2, in DCM they are ρ=0.8, P=0.6, α=3, β=1, γ=1 and in IMCC they are ρ=0.7, P=0.8, α=2.5, β=1.5, γ=1. According to the statistic results, the LSR, LTR and FTR with mode IMCC are all the smallest when compared to the other two modes. It is obvious that IMCC mode performs better than mode PCM and DCM.

Figure 4 presents an example of successful tracking results using our proposed mode, IMCC, where cell 3 enters the field of view in frame 31 then moves close to cell 1. Afterward, two cells are spatially adjacent and move slowly from frame 31 to 45 while cell 2 undergoes relatively fast speed. It can be observed that our proposed mode IMCC can automatically track cells with spatially adjacent, different dynamics and varying numbers (cell 4 enters the field of view in frame 39 and leave in frame 42, and cell 5 enters the field of view in frame 40). Figure 5 shows the results corresponding to our proposed PCM mode. It is noted that cell 1 and cell 3 are falsely merged into one, i.e., cell 3 in frame 39, while the original cell 1 is falsely labeled by cell 6 in frame 40. A similar result occurs in frames 42. We find that label switching happens in these two frames. Figure 6 shows the results using mode DCM. Cell 1 and cell 3 are wrongly divided into three cells i.e., cell 1, cell 4 and cell 3 in frame 30. A similar case happens in frame 42, and it could be seen that false objects are tracked. From what has been discussed above, the performance of model PCM and model DCM is degraded in the case of close data.

Figure 7 presents the comparison of the averaged number of cells, estimated over 20 simulations by various modes. It can be seen that the averaged number of cells estimated by mode IMCC is closed to manual tracking method, while mode PCM and DCM may cause under-estimated or over-estimated number of cells, respectively.

So far, we have evaluated the performance of the three modes on the same image sequence, and it is found that mode IMCC does work and had achieved satisfactory results as we expected. We can conclude that the mode IMCC is more efficient and accurate than other modes.

In case 2, the tracking performance of mode IMCC is further evaluated on dividing cells, different dynamics and varying numbers of cells in cell image sequences. Examples of IMCC-mode tracking results of selected images are presented in Fig. 8. In Fig. 8(a), the two cells occupying the upper right are spatially adjacent and move slowly, while the central cell moves relatively quickly. Two pairs of spatially adjacent cells persist in frames 15–27. In frame 23, the lower right partner of two spatially adjacent cells divides, resulting in three close cells. Figure 8(b) displays the resulting ant distribution in each frame.

Fig. 8

Tracking results of multi close moving cells. (ρ=0.8, P=0.6, α=2.5, β=1, γ=1.1)

According to the tracking results presented in Fig. 8(c), our proposed algorithm could tackle the following challenging cases: cell 3 partly enters the field of view in frame 1, then moves left, partially leaves the field of view in frame 15, and fully leaves the field of view in frame 17. New cells 6 and 5 enter the field of view in frame 15, cell 6 leaves the field of view in frame 19. Cell 4 divides into two cells (labeled 4 and 7) in frame 23. All cells are continuously tracked by our algorithm in succeeding frames. It can be observed that the initial ant distribution of three spatially adjacent cells is adhered in frame 23. Under the cooperation and compete mode of our proposed algorithm, all spatially adjacent cells are successfully separated and tracked. After 50 iterations, the adhesion of the pheromone field is well separated. All these are illustrated in Fig. 8(d). In addition, Figs. 9 and 10 plot the position and instant velocity estimates of each cell. It can be seen that cell 1 undergoes fast dynamics, and cell 3 also moves rapidly both in x and y directions.

Fig. 9

Position estimate of each cell in x and y directions

Fig. 10

Instant velocity estimate of each cell in x and y directions

To better evaluate the tracking performance of our proposed algorithm, we thoroughly compared our proposed algorithm based on mode IMCC with other three recently developed multi-cell tracking algorithms, the particle filter (PF) [46], the multi-Bernoulli filter [7] and the Gaussians Mixture Probabilistic Hypothesis Density (GM-PHD) filter [47]. To ensure an objective and fair comparison, both of which are “detect-before-track” methods, the algorithms were evaluated on the same detection data obtained by a hybrid cell detection algorithm [48]. By contrast, the multi-Bernoulli filter and IMCC are examples of “track-before-detect” techniques. The likelihood function in the multi-Bernoulli filter takes the same form as the heuristic information function used in our ant system (Eq. (12)). As in case 1, all label switching reports, lost track reports and false track reports in each frame are recorded over 50 Monte-Carlo simulations, and their averaged values are listed in Table 3. According to the statistic results in Table 3, the averaged LSR, LTR and FTR are only 1.57 %, 3.17 % and 1.57 %, respectively, using our algorithm. The comparison results demonstrate that our algorithm performs better than the other methods when cells are closely spaced.

Table 3 Comparison results for tracking performance of various methods

Without loss of generality, we present the averaged position errors using the manual tracking result as the ground truth. The positional error in cell 1 in each frame obtained by various methods is shown in Fig. 11. Comparing the performance of the three methods, we again draw the above conclusions.

Fig. 11

Comparison of cell 1 position error estimates by various methods

Computational burden is a major concern when applying ant-system methods to practical problems. For our studied multi-cell tracking approach, real-time tracking is required, and the total processing time must be in principle less than the interval between consecutive samplings. We observe that the computational burden of our algorithm mainly comes from the module of formations of pheromone field, which is calculated with a maximum value of t _max⋅N⋅K, where t _max represents the required iterations, N denotes the number of ant tasks, and K describes the number of birth ants generated at each frame. Figure 12 illustrates the comparisons of executing time using various methods. It is observed that, although our algorithm spends a little more time, which is still less than the sampling interval T=60 s for our studied image sequences, it has achieved better and more stable performance for tracking spatially adjacent cells in terms of LSR, LTR and FTR. As part of future work, the computational burden should be seriously considered and the execution speed should be improved.

Fig. 12

Comparison of executing time using various methods

5.2 Discussions on parameter settings

As mentioned above, three adjustment parameters in the IMCC mode α,β and γ regulate the importance of the total pheromone amount τ _j (t), the ratio of pheromone level of a given task to total pheromone level $\frac{\tau_{j}^{s}(t)}{\tau_{j}(t)}$, and the heuristic function η _j , respectively. In this subsection, the effects of varying these three parameters are evaluated on the estimated performance. This test determines the sensitivity of the algorithm performance to each parameter.

Without loss of generality, different combinations of the three parameters are tested in each frame of case 1 over 50 Monte-Carlo simulations. Other parameters are set as ρ=0.7, P=0.6. The tracking performances of the parameter combinations, in terms of LSR, LTR, and FTR, are summarized in Tables 4 and 5.

Table 4 Statistical results of tracking performance varying α, γ (β=1)

Table 5 Statistical results of tracking performance varying α, γ (β=2)

As implicated in Table 4, as the parameter α increases, both the FTR and LSR decrease significantly, and the LTR changes a little but remains in a low level for a large α value. Therefore, a large value of α is preferred, i.e., α≥2.5. On the other hand, if the parameter γ varies between 0.5 and 2, we observe that the all performance measures degrade for small and large values of γ, and an appropriate value for γ is taken in the range [1,1.5]. When the parameter β increases from β=1 to β=2, the corresponding statistic results are obtained in Table 5, and it is noted that the obtained performance keeps the same level as in Table 4. In other words, the tracking ability is insensitive to the parameter β. As discussed above, in our proposed ant system with different tasks, we suggest the following ranges of the three main parameters: 2.5≤α<5, 1≤β≤2, 1≤γ≤1.5.

6 Conclusion

The proper tracking of spatially adjacent objects remains one of the most difficult problems in automated cell tracking. This paper has introduced a novel ant system with multiple tasks that jointly estimates the number of cells and their individual states in sequences of cell images. To enable tracking of spatially adjacent cells, we devised three types of ant working modes, namely, PCM, DCM, and IMCC. Numerous simulation results on two challenging low-SNR image sequences demonstrated that mode IMCC is more efficient and accurate than the PCM and DCM modes. We also demonstrated the robust tracking performance of our IMCC algorithm, by comparing the LSR, LTR and FTR measures with those of three recently-developed multi-cell tracking algorithms. Finally, the three importance values taken in IMCC mode are discussed and suggested for spatially adjacent multiple cell tracking.

Appendix

Proof

The function q(t) in Eq. (9) can be rewritten as

$$ q(t) = P\bigl[R + q(t - 1)\bigr] $$

(14)

$$ \tau (t + 1) = \rho \tau (t) + q(t) + R $$

(15)

Take a constant λ, let λ−Pλ=PR, then we have

$$ \lambda = \frac{P}{1 - P}R $$

(16)

Then, the Eq. (14) is reduced to

$$ q(t) - \lambda = P\bigl[q(t - 1) - \lambda \bigr] $$

(17)

Due to q(0)=q ₀, then

$$ q(t) = \lambda + (q_{0} - \lambda )P^{t} $$

(18)

Substituting Eq. (18) into Eq. (15), we have

$$ \tau (t + 1) = \rho \tau (t) + AP^{t} + B $$

(19)

where A=q ₀−λ,B=R+λ are constants, let ν is constant

$$ \nu = \frac{B}{1 - \rho} $$

(20)

The Eq. (18) can be rewritten as

$$ \frac{\tau (t + 1) - \nu}{P^{t}} = \frac{\rho}{P} \cdot \frac{\tau (t) - \nu}{P^{t - 1}} + A $$

(21)

Case 1: If ρ≠P, let κ is constant

$$ \kappa = \frac{A}{1 - \frac{\rho}{P}} $$

(22)

Then Eq. (21) can be rewritten as

$$ \frac{\tau (t + 1) - \nu}{P^{t}} - \kappa = \frac{\rho}{P}\biggl( \frac{\tau (t) - \nu}{P^{t - 1}} - \kappa \biggr) $$

(23)

The above form can be rewritten as

$$ \frac{\tau (t) - \nu}{P^{t - 1}} - \kappa = C\biggl(\frac{\rho}{P} \biggr)^{t} $$

(24)

where C is constant, due to τ ₀=τ(0), then C=P(τ ₀−ν)−κ, so we have

$$ \tau (t) = \nu + \kappa P^{t - 1} + \frac{C}{P} \rho^{t} $$

(25)

Due to ρ,P∈(0,1), when t>0, we have

$$ \bigl\vert \tau (t) \bigr\vert \le \vert \nu \vert + \biggl\vert \frac{\kappa}{P} \biggr\vert + \biggl\vert \frac{C}{P} \biggr\vert $$

(26)

So, we say,τ(t) is bounded

Case 2: If ρ=E, Then Eq. (21) can be rewritten as

$$ \frac{\tau (t + 1) - \nu}{P^{t}} = \frac{\tau (t) - \nu}{P^{t - 1}} + A $$

(27)

The above form can be rewritten as

$$ \frac{\tau (t) - \nu}{P^{t - 1}} = At + C $$

(28)

where C is constant, then

$$ \tau (t) = \nu + (At + C)P^{t - 1} $$

(29)

Due to P∈(0,1), we say τ(t) is bounded.