We recently introduced watershed cuts, a notion of watershed in edge-weighted graphs. In this paper, our main contribution is a thinning paradigm from which we derive three algorithmic watershed cut strategies: The first one is well suited to parallel implementations, the second one leads to a flexible linear-time sequential implementation, whereas the third one links the watershed cuts and the popular flooding algorithms. We state that watershed cuts preserve a notion of contrast, called connection value, on which several morphological region merging methods are (implicitly) based. We also establish the links and differences between watershed cuts, minimum spanning forests, shortest path forests, and topological watersheds. Finally, we present illustrations of the proposed framework to the segmentation of artwork surfaces and diffusion tensor images.

A point of a discrete object is called simple if it can be deleted from this object without altering topology. In this article, we present new characterizations of simple points which hold in dimensions 2, 3 and 4, and which lead to efficient algorithms for detecting such points. In order to prove these characterizations, we establish two confluence properties of the collapse operation which hold in the neighborhood of a point in spaces of low dimension. This work is settled in the framework of cubical complexes, which provides a sound topological basis for image analysis, and allows to retrieve the main notions and results of digital topology, in particular the notion of simple point.

We study the watersheds in edge-weighted graphs. We define the watershed cuts following the intuitive idea of drops of water flowing on a topographic surface. We first establish the consistency of these watersheds: They can be equivalently defined by their "catchment basins" (through a steepest descent property) or by the "dividing lines" separating these catchment basins (through the drop of water principle). Then, we prove, through an equivalence theorem, their optimality in terms of minimum spanning forests. Afterward, we introduce a linear-time algorithm to compute them. To the best of our knowledge, similar properties are not verified in other frameworks and the proposed algorithm is the most efficient existing algorithm, both in theory and in practice. Finally, the defined concepts are illustrated in image segmentation, leading to the conclusion that the proposed approach improves, on the tested images, the quality of watershed-based segmentations.

The level sets of a map are the sets of points with level above a given threshold. The connected components of the level sets, thanks to the inclusion relation, can be organized in a tree structure, that is called the component tree. This tree, under several variations, has been used in numerous applications. Various algorithms have been proposed in the literature for computing the component tree. The fastest ones (considering the worst-case complexity) have been proven to run in O(n ln(n)). In this paper, we propose a simple to implement quasi-linear algorithm for computing the component tree on symmetric graphs, based on Tarjan's union-find procedure. We also propose an algorithm that computes the n most significant lobes of a map.

In this work, a new type of watershed transform is introduced: the tie-zone watershed (TZWS). This region-based watershed transform does not depend on arbitrary implementation and provides a unique and optimal solution. Indeed, many solutions are sometimes possible when segmenting an image with a watershed algorithm. In this case, the TZWS assigns each pixel to a catchment basin (CB) if in all solutions it belongs to this CB. Otherwise, the pixel is said to belong to a tie-zone (TZ). We propose an efficient algorithm based on image foresting transform (IFT) which computes the TZWS transform as a shortest-path forest. Finally, two applications of this TZWS are presented: bounding intervals for segmented objects' extensions and a progressive segmentation procedure.

The video segmentation problem can be regarded as a problem of detecting the fundamental video units (shots). Due to different ways of linking two consecutive shots this task turns out to be difficult. In this work, we propose a method to detect both cuts and gradual transitions by image segmentation tools instead of using dissimilarity measures or mathematical models. Firstly, the video is transformed into a 2D image, called visual rhythm by sub-sampling. Afterwards, we apply image processing tools to detect all vertical aligned transitions in this image. The main operator applied here is the morphological multiscale gradient. We also present some experimental results.

We present and compare hardware and system architectures for databases that take advantage of parallelism. First, we state the problem and identify the main comparison criterions (price, performance, extensibility, data availability). Then, we review the major architecture classes (shared nothing, shared everything, shared disks, hybrid) and discuss their advantages and drawbacks for different kinds of workloads.

Efficiency in databases is a major requirement. This paper presents some solutions to cope with this problem. One solution is to execute operations in parallel: this is done in the “Delta Driven Computer” DDC, which is a multiprocessor machine with distributed memory dedicated to relational and deductive databases. In DDC, relations are distributed among the nodes of the machine, and the data are processed asynchronously in each node. To do that in an efficient way, a coprocessor, specialized for relational operations, is also proposed. It is called μSyC, for “microprogrammable Symbolic Coprocessor”. This paper is divided into two parts. The first part describes DDC, presenting the architecture, the languages, and an original computational model. The second part describes μSyC, its architecture, instruction set and the data structures used at the μSyC level.