Reconstructing Curvilinear Networks using Path Classifiers and Integer Programming

We propose a novel Bayesian approach to automated delineation of curvilinear structures that form complex and potentially loopy networks. By representing the image data as a graph of potential paths, we first show how to weight these paths using discriminatively-trained classifiers that are both robust and generic enough to be applied to very different imaging modalities. We then present an Integer Programming approach to finding the optimal subset of paths, subject to structural and topological constraints that eliminate implausible solutions. Unlike earlier approaches that assume a tree topology for the networks, ours explicitly models the fact that the networks may contain loops, and can reconstruct both cyclic and acyclic ones. We demonstrate the effectiveness of our approach on a variety of challenging datasets including aerial images of road networks and micrographs of neural arbors, and show that it outperforms state-of-the-art techniques.

Reconstructing Loopy Curvilinear Structures Using Integer Programming

Fethallah Benmansour, Pascal Fua, Engin Türetken

We propose a novel approach to automated delineation of linear structures that form complex and potentially loopy networks. This is in contrast to earlier approaches that usually assume a tree topology for the networks. At the heart of our method is an Integer Programming formulation that allows us to find the global optimum of an objective function designed to allow cycles but penalize spurious junctions and early terminations. We demonstrate that it outperforms state-of-the-art techniques on a wide range of datasets.

Ieee2013

Automated Reconstruction of Curvilinear Networks from 2D and 3D Imagery

Engin Türetken

Reconstructing complex curvilinear structures such as neural circuits, road networks, and blood vessels is a key challenge in many scientific and engineering fields. It has a broad range of applications, from the delineation of micrometer-sized neurons in micrographs to the detection of Earth-sized solar filaments in telescope images. Modern data acquisition systems can produce very large volumes of such imagery in a short period of time. However, despite the abundance of available imagery and the ever-growing demand driven by the applications, existing reconstruction techniques are not robust to noisy and complex data, and require extensive manual intervention that is both time-consuming and tedious. In this thesis, we propose semi-and fully-automated approaches to overcome these limitations. To this end, we first present a novel filtering method that enhances irregular curvilinear structures in noisy image stacks. Unlike earlier approaches that rely on over-simplistic shape models for the structures and that work only on gray-scale images, ours exploits the color information and allows for the arbitrarily-shaped structures that are prevalent in biological imagery. We build a complete semi-automated reconstruction system based on this filtering approach and use it to collect highly accurate delineations from a wide range of datasets. We then propose a novel probabilistic algorithm to automate reconstruction, which uses these delineations as training data to compute, at each image pixel, the likelihood that the pixel is on the centerline of a curvilinear structure. Our algorithm first builds a graph of potential paths using these likelihoods and then seeks to find the tree that best explains the image data and that has spatially smooth branches. In contrast to other graph-based approaches that first span all the vertices and then prune some of the spurious branches using a heuristic procedure, ours selects an appropriate subset of the vertices to be spanned by optimizing a global objective function that explicitly models spurious branches, and combines the data likelihood with a geometric prior. A major limitation common to all graph-based approaches, including this one, is that they model the curvilinear networks as tree structures, which does not apply to many interesting networks such as roads and blood vessels. Furthermore, they rely on heuristic optimization algorithms, which do not provide optimality guarantees. Finally, the data terms in their objective functions are relatively local and have very little informative value. To address these limitations, we propose a new supervised Bayesian approach, which uses path classifiers trained on global appearance and path geometry features, and a Mixed Integer Programming formulation to guarantee optimality of the resulting solutions. Unlike all previous approaches, ours explicitly models the fact that the networks may be cyclic and allows graph vertices to be used more than once, subject to structural and topological constraints. We demonstrate the effectiveness of our approaches on a variety of challenging gray-scale and color datasets including aerial images of road networks and micrographs of neural arbors, and show that they outperform state-of-the-art techniques.

EPFL2013

Methods for Single Trial Analysis of Asynchronous EEG Patterns

Nicolas Bourdaud

Processing of electroencephalographic (EEG) signals has mostly focused on analysing correlates that are time-locked to an observable event. However, when the signal is acquired in less controlled environment, like in the context of a brain-computer interface operating in the real-world, this synchronous nature does not hold any longer. The analysis of such signal requires the design of methods that rely less on time-locked nature. These methods are also the requirements for study endogenous processes for which the ground truth of when the process take place in time is not available. In this thesis, we present methods to analyse brain signals, EEG in particular, that are not time-locked to observable events. This thesis documents three major contributions : (i) it proposes a Bayesian formalism to the problem of asynchronous EEG pattern classification, (ii) it shows the importance of generative models to achieve this task and (iii) it shows that such methods can be used to gather information and classify the EEG correlates of decision-making process while classical methods fail at it. First, we propose methods to handle non-time-locked EEG patterns by making the hypothesis that, in each trial, only a part of the signal contains the relevant pattern of interest. This relevant part can appear at any time in the analysis window and differently for each trial. The rest of the trial corresponds to a non-informative part irrelevant to the targeted cognitive task. Starting from a discriminant asynchronous approach handling independently the time-samples in the trial, we extend this method to a generative Bayesian model where each part is formally modelled. This is a main difference compared to the classical approach which usually try to avoid to model the non-informative part. Then, making the assumption that the informative part can be modelled by a time sequence, we adapt the previous method to a Bayesian model of asynchronous template matching which allows the recognition of the time onset of the pattern of interest in each trial. Second, we show the importance of the generative model which, thanks to the Bayesian approach allows us to alleviate the problem of choosing of the hyperparameters of the initial discriminative approach. Compared to the initial discriminant model, us- ing a generative approach leads to use more parameters into the model but whose estimation is helped by the prior we provide. By doing so, we provide a more intuitive way for the experimenter to adapt the method to other problems. Using a generative model and a Bayesian estimation also enables us to improve the generalisation of the model of asynchronous template matching. This model has indeed been tested as benchmark on jittered evoked potential data and has shown to successfully improve the signal-to-noise ratio, recover the evoked response and classify better than classical methods. Finally, we see the importance of asynchronous methods for classification of the EEG correlates of decision-making process. We test this in the context of the study of the exploration/exploitation contrast. Exploration is related to decision making in an uncertain environment. This situation arises a conflict between two opposing needs : gathering information about the environment and exploiting this knowledge in order to optimise the decision. Using an experimental setup that forces the subjects to switch between exploratory or exploitative actions, we show for the first time that it is possible to classify the EEG correlates of the exploratory behaviour. Moreover, we show that synchronous methods fail at classify this contrast thus requiring advanced asynchronous ones. The results also confirm that the brain areas relevant to this switch are mainly the left parietal and medial frontal cortex which is consistent with the neurophysiological findings based on functional magnetic resonance imagery. In addition we have been able to show the importance of alpha rhythm for this contrast. In summary, this thesis provides a formal framework for classification of asynchronous EEG patterns using a generative Bayesian approach. It also provides a methodology to approach the study of EEG correlates of cognitive tasks when little is known about them and when the targeted pattern is reasonably assumed to be non time-locked.