Tracking Cell Splits and Merges
Tracking Cell Splits and Merges While bifurcation and amalgamation are issues which have been addressed in other problem domains (Silver and Zabusky, 1993), the size and complexity of this problem pose several unique obstacles. First, this application requires that splitting and merging histories be acquired and visualized over thousands of frames of videotape displaying hundreds of actions. Further, as many as 50 individual cells must be tracked from image to image, so tracking solutions must avoid complex computational methodologies.
This paper describes our work in tracking splits and merges using a multiphase approach. During a preprocessing phase, each frame of videotape is digitized, clipped, masked, and converted to an individual raster image. The next phase is the segmentation of cells within each image. During this phase, a data structure is constructed for each image which provides information about the overall content including the number of cells in the image. The structure also contains information about each cell in the image including size, principal axes, center of mass, bounding box, and mean intensity level. The details of this phase are described elsewhere (Robbins and Gorman, 1996).
We assume the images have been successfully segmented and image information and cell statistics have been collected. The remainder of the paper discusses how this information is used to detect cell splits and merges. The next section describes the overall approach for detecting splits and merges from the segmented data. We introduce an overlap-distance ratio to quantify splits and merges. Section III presents the details of the algorithm, and Section IV shows how the algorithm performs on experimental data. Section V considers a generalization of the basic algorithm to handle dissipation, creation and multiple cell activity.
The mapping step may fail because cells move large distances, reposition in unexpected ways, split or merge. For applications in which the cells move large distances from image to image, the center-of-mass determination can be augmented by a projection of cell motion to determine a one-to-one mapping. The approach presented in this paper assumes continuity of motion, and we do not consider unexpected repositioning.
Several factors must be considered in determining the correspondence of cells in the current image to their correct ancestors in the previous image during a split or a merge. Distance is still a primary factor in completing the mapping process. Another important factor is the amount of pixel overlap present between the cells in subsequent images. Pixel overlap is roughly the number of pixels a cell in one image has in common with a cell in another image if the two images are overlaid.
An efficient method for approximating this overlap is to compare bounding boxes of each of the cells in the two images as shown in Figure 2. The overlap of the bounding boxes can be expressed directly in terms of the coordinates of the rectangle corners.
In order to quantify splits and merges,
we developed a scaled measure of split/merge likelihood
called the {\em overlap-distance ratio}.
The overlap-distance ratio for cell i in image t
with cell j in image t+1 is denoted by
Let
Let
The scaled overlap is the fraction of the smaller cell's area
contained in the other cell. Since only cells which exceed a
certain minimum size are tracked,
the denominator in Equation 3
is always
greater than zero.
Finally,
Correctly mapping the cells between images using the overlap-distance ratio is possible because of the nature of the cell development. As a cell splits or merges, it does not have time over the course of one image to move out of the range of the bounding box of its ancestor. Even if the distance computation indicates it is not the closest cell, the cell will be matched as long as there is overlap. This method is capable of picking up multiple splits and/or merges within one image frame because the matching methodology is done independently for each cell.
Since the goal of this mapping is to track and analyze cell interaction over time, histories can be maintained for each cell by including an external label. These labels are output to a file for use in animation and other visualizations of cell activity. At startup, all cells are assigned an external label. As the cells are correctly mapped from one image to the next, these labels are propagated through the images. If a merge is detected, one of the labels is retained and transferred to the newly formed cell and the other is freed to a pool of available labels. If a split is detected, the label from the splitting cell is transferred to one of the new cells and a new label is retrieved from the pool of available labels for the other cell. Figure 3 shows how these external labels are maintained throughan image sequence.
The external labels are required because the information for the same cell is not always maintained in the same position in the array across images. Shifts in array position can be due to a change in the number of cells in the image from a split or merge. Movement of cells between images can also cause a reordering if the cells are encountered in a different order during segmentation.
Once the mapping of the entire sequence of images is complete, the cell histories can be visualized using computer animation. Unless a visualization requires cell positions, only information from images in which actions were detected is saved. This information includes the number of cells in the image that the action took place, the type of action(s) detected in the image, the labels of the splitting/merging cells and the labels of the resulting cells. A count of the number of images between actions can also be included to portray the passage of time.
If there are m cells in image t (the previous image) and n
cells in image t+1 (the current image), an m by n matrix is
required to hold the overlap-distance ratios
Once the matrix of overlap-distance ratios is computed, split/merge
detection proceeds as follows. For cell i in the previous image,
the number of potential matches with cells in the current image is
computed as the number of entries in row i with
The column labeled current counters in Figure 4 holds the total number of matches of each cell in the previous image to cells in the current image. The cell numbers of the matches are shown in the current mapping structure. Cell 4 in the previous image matches cells 4 and 5 in the current image indicating a split has occurred. A similar procedure is performed for the detection of merges by reviewing the row labeled previous counters. In Figure 4, all of the matched cells have low scaled distances and high scaled overlaps indicating little movement between images.
After all of the computations are completed,
the counters must be analyzed to
insure no phantom splits or merges took place.
This phenomenon can occur if
there is considerable movement of cells between images
or there is incidental overlap of bounding boxes.
These factors can cause
The difficulty can be eliminated by increasing the value of L or by incorporating a projection of cell motion into the calculation of closest cell. For the example in Figure 7, adjusting L to .30 removes all of the phantom splits and merges. In general, for mappings in which there is considerable movement, L will have to be increased.
At this point the mapping is complete. The program steps through the mapping arrays and transfers the proper labels from the cells in the previous image to those in the current image. The program uses the counters associated with each cell to determine if any actions took place. The current counters for the previous image whose values are greater than one indicate a split occurred between images. The corresponding cell numbers in the current image are held in the current mapping array. Similarly, the previous counters greater than one for the current image indicate a merge took place. The merging cells numbers are held in the previous mapping array.
To test the robustness of the methodology, the current image in Figure 6 was inserted at an arbitrary point in the image sequence to simulate considerable cell movement between images with no other actions. This image sequence created the phantom actions discussed previously. Again, the algorithm correctly acted by not detecting an action.
A cell which dissipates will not have an associated cell in the current image, so its current counter value will be zero. A newly created cell has no ancestor in the previous frame so its previous counter is zero. In general, a cell maintains a zero value if there was no match with any other cell in the image or the overlap-distance ratio was below the cutoff value. To insure the cell was a valid dissipation or creation, the overlap-distance ratio is examined. If the ratio is below a threshold (to account for incidental bounding box overlap), the cell is treated as a valid dissipation or creation. Otherwise, the mapping is updated to indicate a split or merge. For a true dissipation, the label can be freed, while a new label must be generated for a newly created cell.
There is also the potential for three or more cells to merge into one (Figure 9) or for one cell to split into three or more cells. This is easily determined by examining the counters for values greater than two. Except for insuring all of the labels are appropriately handled, no additional action is required.
We tested these generalizations using a more complex sequence of 100 image frames which included over 40 actions within them. In each instance, the mapping was completed and the tracking was able to continue throughout the sequence.
Our mapping methodology has several advantages in applications involving extensive data sets. First, there are no complex computations needed to perform the mapping. This introduces minimal overhead in the segmentation process. Second, the actual images are not required to perform the mapping, and therefore mapping can be done after the segmentation is complete. The method only requires information on the object center coordinates, area,and bounding box. This information can easily be held in main memory during the entire tracking process.
We developed our image processing programs under the Khoros image processing environment (Konstatinides and Rasure, 1994). Although the programs execute more slowly in this environment, the common data formats and development support allow more rapid prototyping.
The detection of splits and merges is an important intermediate step in understanding and modeling. However, this processing by itself is insufficient in making the underlying processes accessible for analysts. Visualization and computer animation are also important. Related work in this area is discussed in (Withers, 1996).
[2] M. el-Hamdi, M. Gorman and K. A. Robbins, Deterministic chaos in laminar premixed flames: Experimental classification of chaotic dynamics, Combustion Science & Tech., 94 (1993) p. 87-103.
[3] D. Gauthier, M. Levine and K. Wu, Live cell image segmentation, IEEE Trans on Biomedical Engineering, 42:1 (1995) p. 1-12.
[4] K. Konstatinides and J. Rasure, The Khoros software development environment for image and signal processing, IEEE Trans on Image Processing, 3:3 (1994) p. 243-252.
[5] K. A. Robbins and M. Gorman, A case study using image processing and computer animation to analyze spatial and temporal structure in pattern formation, University of Texas at San Antonio Technical Report 96-2, 1996.
[6] R. Samtaney, D. Silver, N. Zabusky and J. Cao, Visualizing features and tracking their evolution, Computer, 27:7 (1994) p. 20-27.
[7] D. Silver and N. Zabusky, Quantifying visualizations for reduced modeling in nonlinear science: Extracting structures from data sets, J. Visual Commun. and Image Representation, 4:1 (1993) p. 46-61.
[8] J. A. Withers, Tracking large-scale evolving structures, Master's Thesis, University of Texas at San Antonio, (expected May 1996).
