hide
Free keywords:
Computer Science, Computer Vision and Pattern Recognition, cs.CV
Abstract:
Lineage tracing, the joint segmentation and tracking of living cells as they
move and divide in a sequence of light microscopy images, is a challenging
task. Jug et al. have proposed a mathematical abstraction of this task, the
moral lineage tracing problem (MLTP) whose feasible solutions define a
segmentation of every image and a lineage forest of cells. Their branch-and-cut
algorithm, however, is prone to many cuts and slow convergences for large
instances. To address this problem, we make three contributions: Firstly, we
improve the branch-and-cut algorithm by separating tighter cutting planes.
Secondly, we define two primal feasible local search algorithms for the MLTP.
Thirdly, we show in experiments that our algorithms decrease the runtime on the
problem instances of Jug et al. considerably and find solutions on larger
instances in reasonable time.