Preview

PDF, English Download (13MB) | Terms of use

Abstract

Correlation clustering, or multicut partitioning is widely used for image segmentation and graph partitioning. Given an undirected edge weighted graph with positive and negative weights, correlation clustering partitions the graph such that the sum of cut edge weights is minimized. Since the optimal number of clusters is automatically chosen, multicut partitioning is well suited for clustering neural structures in EM connectomics datasets where the optimal number of clusters is unknown a-priori. Due to the NP-hardness of optimizing the multicut objective, exact solvers do not scale and approximative solvers often give unsatisfactory results. In chapter 2 we investigate scalable methods for correlation clustering. To this end we define fusion moves for the multicut objective function which iteratively fuses the current and a proposed partitioning and monotonously improves the partitioning. Fusion moves scale to larger datasets, give near optimal solutions and at the same time show state of the art anytime performance. In chapter 3 we generalize the fusion moves frameworks for the lifted multicut ob- jective, a generalization of the multicut objective which can penalize or reward all decompositions of a graph for which any given pair of nodes are in distinct compo- nents. The proposed framework scales well to large datasets and has a cutting edge anytime performance. In chapter 4 we propose a framework for automatic segmentation of neural structures in 3D EM connectomics data where a membrane probability is predicted for each pixel with a neural network and superpixels are computed based on this probability map. Finally the superpixels are merged to neurites using the techniques described in chapter 3. The proposed pipeline is validated with an extensive set of experiments and a detailed lesion study. This work substantially narrows the accuracy gap between humans and computers for neurite segmentation. In chapter 5 we summarize the software written for this thesis. The provided imple- mentations for algorithms and techniques described in chapters 2 to 4 and many other algorithms resulted in a software library for graph partitioning, image segmentation and discrete optimization.

Translation of abstract (German)

Correlation Clustering oder Multicut Partitionierung ist eine weit verbreitete Technik zur Bildsegmentierung oder Graphpartitionierung. Correlation Clustering partitioniert einen kantengewichteten Graph mit positiv und negativ gewichteten Kanten sodass die Summe der Kantengewichte der geschnittenen Kanten minimiert wird. Da die optimale Anzahl der Kluster automatisch ausgewählt wird, ist die Multicut Paritionierung gut geeignet um neuronale Strukturen in sogenannten EM-Konnektom Datensätzen zu segmentieren, da dort die optimale Anzahl von Klustern nicht a-priori bekannt ist. Da es NP-hart ist die Multicut Zielfunktion zu optimieren skalieren exakte Algorithmen nicht und approximative Verfahren geben schlechte Resultate. In Kapitel 2 untersuchen wir skalierende Methoden für Correlation Clustering. Wir definieren Fusion Moves für die Multicut Zielfunktion. Fusion Moves ist ein iteratives Verfahren das die momentane Partitionierung mit einer Kandidatenpartitionierung fusioniert und so monoton die Partitonierung verbessert. Fusion Moves skaliern zu großen Datensätzen, geben nahezu optimale Lösungen und haben eine gute Perfor- mance selbst wenn sie vor der Terminierung unterbrochen werden. In Kapitel 3 generalisieren wir Fusion Moves für die Lifted Multicut Zielfunktion, eine Generalisierung der Multicut Zielfunktion welche alle Partitionierungen eines Graphes belohnen oder bestrafen kann in der ein beliebiges paar von Knoten in verschiedenen Klustern ist. Die vorgeschlagenen Methoden skalieren gut und haben ein guten Per- formance selbst wenn sie vor der Terminierung unterbrochen werden. In Kapitel 4 wird ein Framework zur automatischen Segmentierung von neuronalen Strukturen in 3D EM Daten vorgestellt. Startend von einer mit einem neuronalen Netz gelernten pixelweisen Membranwahrscheinlichkeit wird eine Superpixel Überseg- mentierung erzeugt. Die Superpixel werden mit den in Kapiteln 2 und 3 vorgeschla- genen Methoden zu Neuronen zusammengefügt. Das vorgeschlagene Framework wird durch umfangreiche Experimente und eine detailreiche Läsion Studien validiert. Der Qualitätsunterschied zwischen menschlich erzeugten Segmentierungen und automa- tisch erzeugten Segmentierungen wurde durch das vorgeschlagene Framework deutlich verringert. In Kapitel 5 wird die für diese Thesis geschriebene Software zusammengefasst. Die be- reitgestellten Implementierungen für die Algorithmen aus Kapitel 2-4 und viele andere Algorithmen resultierten in einer Software Bibliothek zur Graph Partitionierung und Bildsegmentierung.