Catálogo de publicaciones - libros

New technologies for shape acquisition and rendering of digital shapes have simplified the process of creating virtual scenes; nonetheless, shape annotation, recognition and manipulation of both the complete virtual scenes and even of subparts of them are still open problems.

Once the main components of a virtual scene are represented by structural descriptions, this paper deals with the problem of comparing two (or more) sets of 3D objects, where each model is represented by an attributed graph. We will define a new distance to estimate the possible similarities among the sets of graphs and we will validate our work using a shape graph [1].

Segmentation algorithms based on an energy minimisation framework often depend on a scale parameter which balances a fit to data and a regularising term. Irregular pyramids are defined as a stack of graphs successively reduced. Within this framework, the scale is often defined implicitly as the height in the pyramid. However, each level of an irregular pyramid can not usually be readily associated to the global optimum of an energy or a global criterion on the base level graph. This last drawback is addressed by the scale set framework designed by Guigues. The methods designed by this author allow to build a hierarchy and to design cuts within this hierarchy which globally minimise an energy. This paper studies the influence of the construction scheme of the initial hierarchy on the resulting optimal cuts. We propose one sequential and one parallel method with two variations within both. Our sequential methods provide partitions near an energy lower bound defined in this paper. Parallel methods require less execution times than the sequential method of Guigues even on sequential machines.

Spatial relations play a crucial role in model-based image recognition and interpretation due to their stability compared to many other image appearance characteristics. Graphs are well adapted to represent such information. Sequential methods for knowledge-based recognition of structures require to define in which order the structures have to be recognized. We propose to address this problem of order definition by developing algorithms that automatically deduce sequential segmentation paths from fuzzy spatial attribute graphs. As an illustration, these algorithms are applied on brain image understanding.

This paper presents a new technique based on perceptual information for the robust segmentation of noisy 3D scenes acquired by stereo vision. A low-pass geometric filter is first applied to the given cloud of 3D points to remove noise. The tensor voting algorithm is then applied in order to extract perceptual geometric information. Finally, a graph-based segmenter is utilized for extracting the different geometric structures present in the scene through a region-growing procedure that is applied hierarchically. The proposed algorithm is evaluated on real 3D scenes acquired with a trinocular camera.

We define morphological operators on weighted graphs in order to speed up image transformations such as floodings, levelings and waterfall hierarchies. The image is represented by its region adjacency graph in which the nodes represent the catchment basins of the image and the edges link neighboring regions. The weights of the nodes represent the level of flooding in each catchment basin ; the weights of the edges represent the altitudes of the pass points between adjacent regions.

This paper concentrates on a graph-based multilevel temporal segmentation method for scripted content videos. In each level of the segmentat-ion, a similarity matrix of frame strings, which are series of consecutive video frames, is constructed by using temporal and spatial contents of frame strings. A strength factor is estimated for each frame string by using a priori information of a scripted content. According to the similarity matrix reevaluated from a strength function derived by the strength factors, a weighted undirected graph structure is implemented. The graph is partitioned to clusters, which represent segments of a video. The resulting structure defines a hierarchically segmented video tree. Comparative performance results of different types of scripted content videos are demonstrated.

Traditional image models enforce global smoothness, and more recently Markovian Field priors. Unfortunately global models are inadequate to represent the spatially varying nature of most images, which are much better modeled as piecewise smooth. This paper advocates the concept of local influence neighbourhoods (LINs). The influence neighbourhood of a pixel is defined as the set of neighbouring pixels which have a causal influence on it. LINs can therefore be used as a part of the prior model for Bayesian denoising, deblurring and restoration. Using LINs in prior models can be superior to pixel-based statistical models since they provide higher order information about the local image statistics. LINs are also useful as a tool for higher level tasks like image segmentation. We propose a fast graph cut based algorithm for obtaining optimal influence neighbourhoods, and show how to use them for local filtering operations. Then we present a new expectation-maximization algorithm to perform locally optimal Bayesian denoising. Our results compare favourably with existing denoising methods.

A new method for smoothing both gray-scale and color images is presented that relies on the heat diffusion equation on a graph. We represent the image pixel lattice using a weighted undirected graph. The edge weights of the graph are determined by the Gaussian weighted distances between local neighbouring windows. We then compute the associated Laplacian matrix (the degree matrix minus the adjacency matrix). Anisotropic diffusion across this weighted graph-structure with time is captured by the heat equation, and the solution, i.e. the heat kernel, is found by exponentiating the Laplacian eigen-system with time. Image smoothing is accomplished by convolving the heat kernel with the image, and its numerical implementation is realized by using the Krylov subspace technique. The method has the effect of smoothing within regions, but does not blur region boundaries. We also demonstrate the relationship between our method, standard diffusion-based PDEs, Fourier domain signal processing and spectral clustering. Experiments and comparisons on standard images illustrate the effectiveness of the method.

In this paper we develop a new formulation of probabilistic relaxation labeling for the task of data classification using the theory of diffusion processes on graphs. The state space of our process as the nodes of a support graph which represent potential object-label assignments. The edge-weights of the support graph encode data-proximity and label consistency information. The state-vector of the diffusion process represents the object-label probabilities. The state vector evolves with time according to the Fokker-Planck equation. We show how the solution state vector can be estimated using the spectrum of the Laplacian matrix for the weighted support graph. Experiments on various data clustering tasks show effectiveness of our new algorithm.

Graph-based clustering algorithms are particularly suited for dealing with data that do not come from a Gaussian or a spherical distribution. They can be used for detecting clusters of any size and shape without the need of specifying the actual number of clusters; moreover, they can be profitably used in cluster detection problems.

In this paper, we propose a detailed performance evaluation of four different graph-based clustering approaches. Three of the algorithms selected for comparison have been chosen from the literature. While these algorithms do not require the setting of the number of clusters, they need, however, some parameters to be provided by the user. So, as the fourth algorithm under comparison, we propose in this paper an approach that overcomes this limitation, proving to be an effective solution in real applications where a completely unsupervised method is desirable.