"
Team:ETHZ Basel/InformationProcessing/CellDetection
From 2010.igem.org
(→Cell Detection Algorithm) |
(→Cell Tracking Algorithm) |
||
| Line 14: | Line 14: | ||
== Cell Tracking Algorithm == | == Cell Tracking Algorithm == | ||
| + | The main propose of the tracking algorithm is to align cells in adjacent frames to be able to track them. This is achieved by assigning a unique identifier (UID) to every cell, which it ideally keeps over the whole duration of the measurement. | ||
| + | |||
| + | From the cell detection algorithm (see above), the cell tracking algorithm receives the positions of all detected cells. However, not all detected cells are real E. coli cells, but some mud in the flow channel as well as dirt in the microscope apparatus can be wrongly classified as cells (false positives). Furthermore, depending on the threshold used in the cell detection algorithm, more or less cells can be "lost" for one or several adjacent frames (false negatives). The main goal of both algorithms together is to make it possible to track a selected cell over a long period of time. This goal requires that our cell tracking algorithm has to be able to recognize cells and assign them their previous UID, even if they were "lost" over several frames. Furthermore, it must be able to not confuse a cell with false positively detected dirt, if the cell is passing nearby. The case of distinguishing two nearby passing true positively detected E. coli cells is widely omitted in the algorithm due to the complexity of such calculations and the thus unavoidable slow down of the algorithm. Instead, the experiment is set up so that the cell density is quite small. If, by chance, however two true positively detected cells passing close to each other and, by chance, their UIDs are mixed up, the user has to simply correct manually for this mistake by e.g. pressing the right buttons of a joystick. | ||
| + | |||
| + | Due to speed limitations we decided to implement a simple but robust fast algorithm for cell tracking. In the first frame, an UID is assigned to all detected cells and stored together with the position of their centroids in a the so called cell table. In all adjacent frames the Euclidean distance between all detected cells and the already known cells from the previous frame is calculated using matrix arithmetics (fast in Matlab). | ||
Revision as of 12:04, 15 October 2010
Cell Detection and Tracking
Background
One important input of the controller is the current location and the swimming direction of the E. lemming that we decide to control. However, due to experimental limitations, also other E. coli cells will by chance be on the microscope image. We therefore decided to implement a cell detection algorithm which detects all cells in the current frame and combine it with a cell tracking algorithm that aligns the cells in the adjacent frames. Thus it is possible to keep track of the E. lemming without confuse it with other cells. Since the controller has to react in real-time on changes of the direction of the E. lemming, an important requirement for the development of both algorithms was a fast processing time. This requirement is fulfilled by our implementation, which together require around 0.2s of processing time on a Intel Core 2 Duo 3.16 GHz CPU with 1.95 GB RAM. Since the main steps depend on each other and thus can not be parallelized, we applied only one of the cores for Cell Detection and Tracking, and used the other core to listen to a russian techno radio ([http://clubberry.fm/en]) to stay awake.
Cell Detection Algorithm
The cell detection algorithm requires most of the CPU speed, so that it was optimized most for speed while maintaining a sufficiently high percentage of true positive and a sufficiently low percentage of false positive detected cells. However, for the controller it is worse loosing the selected cell than dealing with a reasonably high amount of false positively detected cells, so that in comparison to other cell detection algorithm the emphasis of our algorithm was put on reducing the amount of true negatives. The algorithm is based on a two step approach: First, every compact area having a sharp increase of brightness compared to the background is detected and classified as a cell. Second, cells having unusual properties for an E. coli cell, like a too large or too small area, are sorted out, so that mainly real E. coli cells persist. In the following we describe in more detail the first step.
The microscope image is pre-processed for cell detection by decreasing its size to half of the size obtained by the microscope (336x256 pixels, please be aware that we already used a microscope internal binning of two). This downsizing reduces the speed of the following steps, but showed to not reduce the detection quality too much. The resized image is then filtered by a 3x3 median filter to reduce pixel noise while preserving edges, and its contrast is increased. The image is then differentiated by convolution it with two 3x3 pixel big horizontal respectively vertical edges and calculating the Euclidean norm of the resulting two values for every pixel (Sobel filtering). A binary image is created by setting all pixels to TRUE which have gray-scale level over a user definable threshold and all others to FALSE. With this approach we can detect the borders of the cells. However, these borders may still have holes, which are eliminated by dilating the borders with a horizontal and a vertical line of length 3 pixels. We now detected the contours of each potential cell and, after the interior of the cells is filled, we calculate the properties of them and compare these properties to the properties of typical cells, like the typical area of a cell. If the measured properties of the potential cells deviate to much from the reference properties, the wrongly detected cells get removed. For the remaining cells the centroid is calculated and passed to the cell tracking algorithm as the current position of the cell.
Cell Tracking Algorithm
The main propose of the tracking algorithm is to align cells in adjacent frames to be able to track them. This is achieved by assigning a unique identifier (UID) to every cell, which it ideally keeps over the whole duration of the measurement.
From the cell detection algorithm (see above), the cell tracking algorithm receives the positions of all detected cells. However, not all detected cells are real E. coli cells, but some mud in the flow channel as well as dirt in the microscope apparatus can be wrongly classified as cells (false positives). Furthermore, depending on the threshold used in the cell detection algorithm, more or less cells can be "lost" for one or several adjacent frames (false negatives). The main goal of both algorithms together is to make it possible to track a selected cell over a long period of time. This goal requires that our cell tracking algorithm has to be able to recognize cells and assign them their previous UID, even if they were "lost" over several frames. Furthermore, it must be able to not confuse a cell with false positively detected dirt, if the cell is passing nearby. The case of distinguishing two nearby passing true positively detected E. coli cells is widely omitted in the algorithm due to the complexity of such calculations and the thus unavoidable slow down of the algorithm. Instead, the experiment is set up so that the cell density is quite small. If, by chance, however two true positively detected cells passing close to each other and, by chance, their UIDs are mixed up, the user has to simply correct manually for this mistake by e.g. pressing the right buttons of a joystick.
Due to speed limitations we decided to implement a simple but robust fast algorithm for cell tracking. In the first frame, an UID is assigned to all detected cells and stored together with the position of their centroids in a the so called cell table. In all adjacent frames the Euclidean distance between all detected cells and the already known cells from the previous frame is calculated using matrix arithmetics (fast in Matlab).
