This paper deals with the minimization of the total variation under a convex data fidelity term. We propose an algorithm which computes an exact minimizer of this problem. The method relies on the decomposition of an image into its level sets. Using these level sets, we map the problem into optimizations of independent binary Markov Random Fields. Binary solutions are found thanks to graph-cut techniques and we show how to derive a fast algorithm. We also study the special case when the fidelity term is the $L^1$-norm. Finally we provide some experiments.

Having 300 students a year implement a compiler is a debatable enterprise, since the industry will certainly <i>not</i> recruit them for this competence. Yet we made that decision five years ago, for reasons not related to compiler construction. We detail these motivations, the resulting compiler design, and how we manage the assignment. The project meets its goals, since the majority of former students invariably refer to it as <i>the</i> project that taught them the most.

Attribute Grammars (AGs) provide a very convenient means to bind semantics to syntax. They enjoy an extensive bibliography and are used in several types of applications. Yet, to our knowledge, their use to disambiguate is novel. We present our implementation of an evaluator of attributes for ambiguous AGs, tailored to ambiguous parse trees disambiguation. This paper focuses on its implementation that heavily relies on Stratego/XT, which is also used as language to express the attribute rules. A companion paper presents the disambiguation process in details 200505-SUD-disamb.

We propose a novel approach to semantics driven disambiguation based on Attribute Grammars (AGs). AGs share the same modularity model as its host grammar language, here Syntax Definition Formalism (SDF), what makes them particularly attractive for working on unstable grammars, or grammar extensions. The framework we propose is effective, since a full ISO-C99 disambiguation chain already works, and the core of the hardest ambiguities of C++ is solved. This requires specific techniques, and some extensions to the stock AG model.

By the means on its annotations, Syntax Definition Formalism (SDF) seems to be extensible: the user is tempted to tailor its grammar syntax by adding new annotation kinds. Unfortunately the standard SDF crunching tools from Stratego/XT do not support the extension of SDF, and the user has to develop the whole set of tools for her home grown extension(s). We present the SDF tool set that provides “weak” genericity with respect to the grammar grammar: support for arbitrary SDF annotations. We would like to contribute it to Stratego/XT since its components subsume their stock peers. Finally, we present a set of four extensions we find useful.

This papers presents a comprehensive and general form of the Tarjan’s union-find algorithm dedicated to connected operators. An interesting feature of this form is to introduce the notion of separated domains. The properties of this form and its flexibility are discussed and highlighted with examples. In particular, we give clues to handle correctly the constraint of domain-disjointness preservation and, as a consequence, we show how we can rely on “union-find” to obtain algorithms for self-dual filters approaches and levelings with a marker function.

Spatial relations play an important role in recognition of structures embedded in a complex environment and for reasoning under imprecision. Several types of relationships can be modeled in a unified way using fuzzy mathematical morphology. Their combination benefits from the powerful framework of fuzzy set theory for fusion tasks and decision making. This paper presents several methods of fusion of information about spatial relationships and illustrates them on the example of model-based recognition of brain structures in 3D magnetic resonance imaging.

This paper deals with the minimization of the total variation under a convex data fidelity term. We propose an algorithm which computes an exact minimizer of this problem. The method relies on the decomposition of an image into its level sets. Using these level sets, we map the problem into optimizations of independent binary Markov Random Fields. Binary solutions are found thanks to graph-cut techniques and we show how to derive a fast algorithm. We also study the special case when the fidelity term is the $L^1$-norm. Finally we provide some experiments.

This paper deals with the total variation minimization problem when the fidelity is either the $L^2$-norm or the $L^1$-norm. We propose an algorithm which computes the exact solution of these two problems after discretization. Our method relies on the decomposition of an image into its level sets. It maps the original problems into independent binary Markov Random Field optimization problems associated with each level set. Exact solutions of these binary problems are found thanks to minimum-cut techniques. We prove that these binary solutions are increasing and thus allow to reconstruct the solution of the original problems.

This paper presents a fast method for road network extraction in satellite images. It can be seen as a transposition of the segmentation scheme "watershed transform + region adjacency graph + Markov random fields" to the extraction of curvilinear objects. Many road extractors can be found in the literature which are composed of two stages. The first one acts like a filter that can decide from a local analysis, at every image point, if there is a road or not. The second stage aims at obtaining the road network structure. In the method we propose, we rely on a "potential" image, that is, unstructured image data that can be derived from any road extractor filter. In such a potential image, the value assigned to a point is a measure of its likelihood to be located in the middle of a road. A filtering step applied on the potential image relies on the area closing operator followed by the watershed transform to obtain a connected line which encloses the road network. Then a graph describing adjacency relationships between watershed lines is built. Defining Markov random fields upon this graph, associated with an energetic model of road networks, leads to the expression of road network extraction as a global energy minimization problem. This method can easily be adapted to other image processing fields where the recognition of curvilinear structures is involved.