German Title: Skalierbare Inferenz für Multi-Target Tracking sich fortpflanzender Zellen

Preview

PDF, English - main document Download (21MB) | Lizenz: Scalable Inference for Multi-Target Tracking of Proliferating Cells by Haubold, Carsten underlies the terms of Creative Commons Attribution-NonCommercial 3.0 Germany

Abstract

With the continuous advancements in microscopy techniques such as improved image quality, faster acquisition and reduced photo-toxicity, the amount of data recorded in the life sciences is rapidly growing. Clearly, the size of the data renders manual analysis intractable, calling for automated cell tracking methods. Cell tracking – in contrast to other tracking scenarios – exhibits several difficulties: low signal to noise ratio in the images, high cell density and sometimes cell clusters, radical morphology changes, but most importantly cells divide – which is often the focus of the experiment. These peculiarities have been targeted by tracking-byassignment methods that first extract a set of detection hypotheses and then track those over time. Improving the general quality of these cell tracking methods is difficult, because every cell type, surrounding medium, and microscopy setting leads to recordings with specific properties and problems. This unfortunately implies that automated approaches will not become perfect any time soon but manual proof reading by experts will remain necessary for the time being. In this thesis we focus on two different aspects, firstly on scaling previous and developing new solvers to deal with longer videos and more cells, and secondly on developing a specialized pipeline for detecting and tracking tuberculosis bacteria. The most powerful tracking-by-assignment methods are formulated as probabilistic graphical models and solved as integer linear programs. Because those integer linear programs are in general NP-hard, increasing the problem size will lead to an explosion of computational cost. We begin by reformulating one of these models in terms of a constrained network flow, and show that it can be solved more efficiently. Building on the successful application of network flow algorithms in the pedestrian tracking literature, we develop a heuristic to integrate constraints – here for divisions – into such a network flow method. This allows us to obtain high quality approximations to the tracking solution while providing a polynomial runtime guarantee. Our experiments confirm this much better scaling behavior to larger problems. However, this approach is single threaded and does not utilize available resources of multi-core machines yet. To parallelize the tracking problem we present a simple yet effective way of splitting long videos into intervals that can be tracked independently, followed by a sparse global stitching step that resolves disagreements at the cuts. Going one step further, we propose a microservices based software design for ilastik that allows to distribute all required computation for segmentation, object feature extraction, object classification and tracking across the nodes of a cluster or in the cloud. Finally, we discuss the use case of detecting and tracking tuberculosis bacteria in more detail, because no satisfying automated method to this important problem existed before. One peculiarity of these elongated cells is that they build dense clusters in which it is hard to outline individuals. To cope with that we employ a tracking-by-assignment model that allows competing detection hypotheses and selects the best set of detections while considering the temporal context during tracking. To obtain these hypotheses, we develop a novel algorithm that finds diverseM- best solutions of tree-shaped graphical models by dynamic programming. First experiments with the pipeline indicate that it can greatly reduce the required amount of human intervention for analyzing tuberculosis treatment.

Translation of abstract (German)

Kontinuierliche Fortschritte in der Mikroskopie wie z.B. verbesserte Bildqualität, höhere Aufnahmegeschwindigkeit und weniger fototoxische biologische Marker, lassen die Menge an aufgezeichneten Videos in den Biowissenschaften rapide wachsen. Aufgrund der Größe der Daten wäre eine manuelle Analyse schwer zu bewältigen, weshalb automatisierte Verfahren vonnöten sind. Im Gegensatz zu anderen Tracking-Szenarien hat das Zell-Tracking einige verkomplizierende Besonderheiten: ein schlechtes Signal-zu-Rauschen Verhältnis in den Bildern, eine hohe Dichte von Zellen bis hin zu Zellhaufen, starke Veränderungen der Form. Aber am allerwichtigsten ist, dass Zellen sich teilen können – was oft das Hauptaugenmerk der biologischen Studie ist. Diese Besonderheiten wurden in vorangegangenen Arbeiten mit so genannten Tracking-by- Assignment-Methoden angegangen, bei denen zuerst Detektionshypothesen extrahiert werden, welche dann im Tracking über die Zeit hinweg miteinander verbunden werden. Es wäre schwierig, die Qualität dieser Zell-Tracking Methoden im Grundsatz zu verbessern, da jeder Zelltyp, jedes die Zellen umgebende Medium und jede Mikroskopeinstellung zu Aufnahmen führen, die ihre ganz speziellen Eigenschaften und Probleme haben. Dies bedeutet leider auch, dass Tracking Methoden in absehbarer Zukunft nicht perfekt werden, sondern dass ein Korrekturlesen der Ergebnisse von Experten vorerst nötig bleiben wird. In dieser Forschungsarbeit widmen wir uns deshalb zwei anderen Aspekten: zum einen der Skalierung von bekannten und der Entwicklung neuer Lösungsmethoden für etablierte Trackingmodelle und zum anderen der Konstruktion einer speziellen Pipeline um Tuberkulosebakterien zu detektieren und zu verfolgen. Die leistungsfähigsten Tracking-by-Assignment Methoden sind als Probabilistische Graphische Modelle formuliert und werden als Integer Lineare Programme gelöst. Weil diese Integer Linearen Programme aber im Allgemeinen NP-schwer sind, führt eine Vergrößerung des zu lösenden Problems zu einer Explosion des benötigten Rechenaufwands. Zu Beginn dieser Arbeit formulieren wir eines dieser Modelle im Stil eines Netzwerk-Fluss Problems mit Nebenbedingungen um und zeigen, dass es dadurch effizienter zu lösen wird. Da Netzwerk-Fluss Algorithmen sehr erfolgreich im Personen-Tracking eingesetzt werden, entwickeln wir eine Heuristik um zusätzliche Bedingungen – hier für Zellteilungen – in solch einer Methode zu behandeln. Das erlaubt uns qualitativ hochwertige Annäherungen an die Trackinglösung zu finden und gleichzeitig eine polynomielle Laufzeitschranke anzugeben. In unseren Experimenten bestätigt sich die geringere Komplexität dadurch, dass unsere Methode deutlich besser zu größeren Problemen skaliert. Nichtsdestotrotz ist der Ansatz single-threaded und nutzt die verfügbaren Ressourcen von Mehrprozessormaschinen noch nicht aus. Damit das Tracking parallelisiert werden kann, stellen wir eine effektive Methode vor um lange Videos in einzelne Intervalle zu zerlegen und diese unabhängig voneinander zu lösen. Durch die anschließende Optimierung eines simplen globalen Problems werden die Teillösungen so zusammengesetzt, dass an den Schnittstellen keine Unstimmigkeiten entstehen. Um noch einen Schritt weiter in diese Richtung zu gehen, schlagen wir ein Softwaredesign für ilastik vor, das auf Microservices aufbaut und das es erlaubt, die Berechnungsschritte für die Segmentierung, die Extraktion von Objekteigenschaften, das Klassifizieren von Objekten und dem Tracking auf mehrere Maschinen in einem Cluster oder der Cloud zu verteilen. Letztendlich betrachten wir den Anwendungsfall des Erkennens und Trackings von Tuberkulosebakterien genauer, da es für dieses wichtige Problem bisher keine zufriedenstellende automatische Methode gab. Eine Besonderheit dieser länglichen Zellen ist, dass sie sich so nahe kommen, dass man die Individuen kaum voneinander abgrenzen kann. Wir verwenden daher ein Tracking-by-Assignment Modell, das beim Tracking aus einer großen Menge von teils konkurrierenden Detektionshypothesen diejenigen auswählt, die im gesamten zeitlichen Kontext am plausibelsten sind. Um diese Hypothesen zu erlangen, entwickeln wir einen neuen Algorithmus der die M besten diversen Lösungen von baumförmigen graphischen Modellen mittels dynamischem Programmieren finden kann. Erste Versuche mit dieser Pipeline deuten darauf hin, dass wir damit Tuberkulosebakterien zuverlässig tracken können.