Graph reduction and application to lung tumors segmentation

In this thesis, we first present a new band-based strategy for reducing the graphs involved in binary graph cut segmentation. This is done by locally testing if a node is really useful to the maximum flow computation in these graphs. Like previous band-based methods, the remaining nodes are typically located in narrow bands surrounding the object edges to segment. In a first time, we propose an heuristic condition to decide if a node can be added to the reduced graph which can be computed in constant time (except for image borders). When the amount of regularization is large, extra parameters are embedded into this test for both further reducing the graphs and removing segments due to noise in the segmentations. When the amount of regularization is of moderate level, the time required by this algorithm is even compensated by the maximum flow time on the reduced graph. In this situation, we experimentally show that this algorithm drastically reduce the memory usage of standard graph cuts while keeping a low pixel error on segmentations. In a second time, we describe another test with a slightly higher computational cost. We prove that each node satisfying this test can be safely removed without modifying the maximum flow value. Numerical experiments exhibit similar performance than the heuristic test. In a second part, we present an application of this reduction technique devoted to the semi-interactive segmentation of lung tumors in 3D CT images. The novelty of this work is to embed a prior on the object seeds location and control their propagation thanks to a Fast Marching algorithm based on the image gradient. Qualitative and quantitative results against provided ground truths exhibit an accurate delineation of tumors with a Dice coefficient greater than 80\% in average.