A parallel graph coloring heuristic with application to real-time segmentation of large images

Date

Nov 5, 2015

Time

2:00 PM - 3:00 PM

Speaker

Yaser Afshar

Affiliation

MPI-CBG

Language

en

Main Topic

Informatik

Other Topics

Informatik

Description

Proper graph coloring assigns colors (positive integers) to the vertices of a graph such that no two neighboring vertices have the same color. Doing so for a complete graph using the minimum number of colors is an NP-hard problem. Efficient approximation heuristics are available since the classic Br elaz algorithm of 1979, which has a +1 error bound with linearithmic runtime. Graph coloring is often used in parallel high-performance computing to identify and schedule independent computational tasks and to orchestrate inter-processor communication. Using effi- cient approximation heuristics on distributed-memory computers, however, either requires global synchronization or several rounds of coloring, conflict detection, and recoloring in order to con- verge to the final result. Both carry increased communication overhead and hence limit parallel scalability. In my thesis, I propose a modification to the greedy coloring heuristic on distributed-memory architectures, which alleviates the communication overhead by requiring only a single round of coloring and no global communication. The key concept is to randomly decompose the graph into independent sub-graphs that are coupled across processor boundaries. This renders the resulting algorithm stochastic, leading to an efficient randomized approximation heuristic. The idea is inspired by parallel Monte Carlo approaches to the Ising model in statistical physics, where random decompositions have been shown to improve the quality of the approximate solution and to accelerate convergence. The new heuristic is applied to enable distributed-memory parallelization of a state-of-the-art multi-region image segmentation algorithm, Region Competition. The Region Competition algo- rithm jointly estimates the number of regions in an image, their shapes, and photometries using a discrete particle representation of region boundaries. It is conceptually related to Markov Ran- dom Fields and Level-Set methods, linking the two approaches. Parallelization of the algorithm has so far proven hard due to global topological dependencies, ensuring that regions remain closed and connected. Formulating the problem as an instance of graph coloring, the Region Competition algorithm can, however, be parallelized using the new heuristic. Doing so enables real-time segmentation of large 3D microscopy images. “Real-time” means that the time required to compute the segmentation is less than the time it takes for the mi- croscope to acquire the image. This avoids storing the entire raw data, which can be several Gigabytes per second, and allows direct feedback control of the microscope depending on image content (“smart microscope”). The parallel Region Competition algorithm presented here en- ables real-time segmentation of large (several Gigabytes per image) 3D fluorescence microscopy images on parallel computer clusters. It hence relaxes the Big-Data challenge in image-based systems biology and opens the door toward smart microscopes. In this talk I present the results and the current status of my work. Furthermore, I show how real-time segmentation of Single-Plane Illumination Microscopy (SPIM) images enables analysis and tracking of tens of thousands of cells in entire developing embryos. I close by giving an outlook of other possible applications of the presented graph coloring heuristic, and of a sampling-based Region Competition algorithm which also provides segmentation uncertainty estimates along with the results. Diese Veranstaltung wird unterstützt von chair of scientific computing for systems biology.

Last modified: Nov 5, 2015, 9:00:48 AM