IV) Tracking Overview: The flow chart in figure 1 depicts an outline of our tracking method. After conversion to 8bit PNG-file format, the images are pre-processed to provide a consistent input for the subsequent cell detection. Then, a set of descriptive features is computed for each cell. These features are used by both, the mitosis detector and the path validation methods. The novel aspect of our tracking method is the continuous validation of each cell path. These path validation methods aim to only return paths of very high trustworthiness. If in doubt, the path is excluded from the final description of the cell behaviour. Pre-processing. First, uneven illumination is reduced using a high-pass filter by subtracting a Gauss filtered image from the raw image. Second, the grey values are linearly mapped to 8bit dynamic range using a global image-normalization. The preceding careful adjustment of the microscope for high contrast raw data made these two pre-processing steps sufficient for subsequent cell tracking. Cell-Detection / Segmentation. To detect the cells in our image data I a threshold based segmentation is used. Each pixel xi[I is classified as foreground or background with xi~ foreground if BðxÞwh, background else, : where BðxiÞ is the grey value and h is the global threshold for image I , i.e. all pixels brighter than h are belonging to the foreground. To calculate h we use the very robust method of Otsu [25]. The result of this operation is a binary image with background labelled 0 (no cell) and foreground labelled 1 (cell; see figure 2). The binary data are further refined by morphological filters [26,27]: First, an erosion operator is used to separate tiny false connections between cell areas. Then, a dilatation operation is Figure 1. Diagram of the tracking algorithm. Each functional block is explained in section M&M IV. The novel aspects of the algorithm pertain the path validation and error correction parts (coloured in red). doi:10.1371/journal.pone.0027315.g001 Automated Tracking Turns Cell Culture into Numbers used to fill holes. Finally, all areas smaller than a minimum size are deleted in order to remove small particles and cell debris. Now, each cell is represented as a connected pixel region with foreground value. This binary representation of the raw images will be termed "cell mask" throughout this paper. Finding a cell in subsequent images (tracking). Using the cell mask, the cell tracking problem for a cell in frame t is to determine its successor cell in frame t+1. To map the cells, the intersection between adjacent cell masks is used. The ratio between the intersection and the area of the cell mask, called cell area At and Atz1in frame t and t+1, is defined as forward At\Atz1 and backward overlap = At\Atz1, respectively overlap = Atz1 At (see figure 2). To identify a unique successor cell, we choose the cell pair with the largest overlap provided, both, the forward and backward overlap, exceed the thresholds and with. A large threshold (,1) results in many short, but trustworthy path fragments, whereas a low threshold (,0) results in longer initial path fragments with a lower trustworthiness. The values of depend on a variety of factors, such as cell type, time-interval between the frames and the speed of the cells. For our data, values of and have shown to be a good compromise between number of path fragments and trustworthi- ness. Path fragments. First, highly trustworthy path fragments are calculated using the rigorous criterion for each cell to have one and only one successor/predecessor. If this condition is met, the new cell is added to the path fragment, else the cell path construction is aborted and new paths are started at this point. After this initial construction of path fragments each cell mask belongs to exactly one path pi or in other words: each path fragment follows a cell over a definite time period. The path fragments are consecutively numbered p1,p2,:::,pN . Usually, the construction of path fragments is terminated because more than one overlap between adjacent cell masks occurs. These concurrent overlaps indicate the possibility of different path continuations. We store these possible connections between adjacent path fragments in a symmetrical adjacency matrix. In its initial form, the adjacency matrix does not aim to represent the true cell paths or lineage but serves only as a starting hypothesis for the subsequent path validation process. After several rounds of refinement, false connections become removed. Cell features. For each cell, a set of instructive features is computed analogous to Al-Kofahi et al [28] and stored in a cell assigned feature vector f ~ fx, fy, fA, fB, fC . These features include the mean grey value fB of the cell, which is calculated using the cell mask and the image data. Other features can be derived using the cell mask only: * fx and fy, which represent the x- and y-position of the cell- centroid, * fA denotes the cell-size (area) as the number of pixels stored in a cell mask, * the compactness fC §1 as a measure for the circularity of the P2 cell. It is calculated as fC ~ where P is the perimeter and 4pA A~fA is the cell-area. A compactness of 1 means that a cell is perfectly circular. To analyze changes of the cell or its shape, the difference values of the feature vectors f of two overlapping cells are calculated: speed dV , changes in size dA, brightness dB and compactness dC . For each step in a path, these values are stored in the difference vector d~½dV ,dA,dB,dC , analogous to the cell feature vector. The difference vector d enables us to compute the similarity of two cells [28]. The similarity is given as the probability of the multidimensional normal distribution PLoS ONE | www.plosone.org 3 November 2011 | Volume 6 | Issue 11 | e27315