Research

Tracking cells in Life Cell Imaging videos using topological alignments

Axel Mosig^1,2 , Stefan Jäger¹ , Chaofeng Wang¹ , Sumit Nath³ , Ilker Ersoy³ , Kannap-pan Palaniappan³ and Su-Shing Chen¹

¹  Department of Combinatorics and Geometry, CAS-MPG Partner Institute for Computational Biology, 200031 Shanghai, PR China

²  Max Planck Institute for Mathematics in the Sciences, 04103 Leipzig, Germany

³  Department of Computer Science, University of Missouri-Columbia, Columbia MO 65211, USA

author email corresponding author email

Algorithms for Molecular Biology 2009, 4:10doi:10.1186/1748-7188-4-10

Published:	16 July 2009

Abstract

Background

With the increasing availability of live cell imaging technology, tracking cells and other moving objects in live cell videos has become a major challenge for bioimage informatics. An inherent problem for most cell tracking algorithms is over- or under-segmentation of cells – many algorithms tend to recognize one cell as several cells or vice versa.

Results

We propose to approach this problem through so-called topological alignments, which we apply to address the problem of linking segmentations of two consecutive frames in the video sequence. Starting from the output of a conventional segmentation procedure, we align pairs of consecutive frames through assigning sets of segments in one frame to sets of segments in the next frame. We achieve this through finding maximum weighted solutions to a generalized "bipartite matching" between two hierarchies of segments, where we derive weights from relative overlap scores of convex hulls of sets of segments. For solving the matching task, we rely on an integer linear program.

Conclusion

Practical experiments demonstrate that the matching task can be solved efficiently in practice, and that our method is both effective and useful for tracking cells in data sets derived from a so-called Large Scale Digital Cell Analysis System (LSDCAS).

Availability

The source code of the implementation is available for download from http://www.picb.ac.cn/patterns/Software/topaln webcite.