This paper reports on a new software platform called VAUCANSON and dedicated to the computation with automata and transducers. Its main feature is the capacity of dealing with automata whose labels may belong to various algebraic structures. The paper successively describes the main features of the VAUCANSON platform, including the fact that the very rich data structure used to implement automata does not weigh too much on the performance, shows how VAUCANSON allows to program algorithms on automata in a way which is very close to the mathematical expression of the algorithm and finally explains the main choices of the programming design that enable to achieve both genericity and efficiency.

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.

Carrier Sense Multiple Access/Collision Detection (CSMA/CD) is the protocol for carrier transmission access in Ethernet networks (international standard IEEE 802.3). On Ethernet, any Network Interface Card (NIC) can try to send a packet in a channel at any time. If another NIC tries to send a packet at the same time, a collision is said to occur and the packets are discarded. The CSMA/CD protocol was designed to avoid this problem, more precisely to allow a NIC to send its packet without collision. This is done by way of a randomized exponential backoff process. In this paper, we analyse the correctness of the CSMA/CD protocol, using techniques from probabilistic model checking and approximate probabilistic model checking. The tools that we use are PRISM and APMC. Moreover, we provide a quantitative analysis of some CSMA/CD properties.

This paper presents a morphological classifier with application to color image segmentation. The basic idea of a morphological classifier is to consider that a color histogram is a 3D gray-level image and that morphological operators can be applied to modify this image. The final objective is to extract clusters in color space, that is, identify regions in the 3D image. In this paper, we particularly focus on a powerful class of morphology-based filters called levellings to transform the 3D histogram-image to identify clusters. We also show that our method gives better results than the ones of state-of-the-art methods.

The problem of person identification based on their hand images has been addressed. The system is based on the images of the right hands of the subjects, captured by a flatbed scanner in an unconstrained pose. In a preprocessing stage of the algorithm, the silhouettes of hand images are registered to a fixed pose, which involves both rotation and translation of the hand and, separately, of the individual fingers. Independent component features of the hand silhouette images are used for recognition. The classification performance is found to be very satisfactory and it was shown that, at least for groups of one hundred subjects, hand-based recognition is a viable secure access control scheme.

This paper deals with the implementation of algorithms in the specific domain of image processing. Although many image processing libraries are available, they generally lack genericity and flexibility. Many image processing algorithms can be expressed as compositions of elementary algorithmic operations referred to as blocks. Implementing these compositions is achieved using generic programming. Our solution is compared to previous ones and we demonstrate it on a class image processing algorithms.

In this contribution, a mobile location method is provided using measurements from two different Base-Stations. Although computationally from two different Base-Stations. Although based on a simple trilateration and takes into account error measurements caused by Non-Line-Of-Sight (NLOS) and near-far effect. The new method attributes an index of confidence for each measure, in order to allow the mobile to select the two most reliable measures and not to use all measures, equally.

The C++ language offers a two layer evaluation model. Thus, it is possible to evaluate a program in two steps: the so-called static and dynamic evaluations. Static evaluation is used for reducing the amount of work done at execution-time. Programs executed statically (called metaprograms) are written in C++ through an intensive use of template classes. Due to the complexity of these structures, writing, debugging and maintaining C++ meta-programs is a difficult task. Metagene is a program transformation tool which simplifies the development of such programs. Due to the similarities between C++ meta-programming and functional programming, the input language of Metagene is an ML language. Given a functional input program, Metagene outputs the corresponding C++ meta-program expressed using template classes.

Video games and simulators commonly use very detailed textures, whose cumulative size is often larger than the GPU memory. Textures may be loaded progressively, but dynamically loading and transferring this large amount of data in GPU memory results in loading delays and poor performance. Therefore, managing texture memory has become an important issue. While this problem has been (partly) addressed early for the specific case of terrain rendering, there is no generic texture management system for arbitrary meshes. We propose such a system, implemented on today’s GPUs, which unifies classical solutions aimed at reducing memory transfer: progressive loading, texture compression, and caching strategies. For this, we introduce a new algorithm – running on GPU – to solve the major difficulty of detecting which parts of the texture are required for rendering. Our system is based on three components manipulating a tile pool which stores texture data in GPU memory. First, the Texture Load Map determines at every frame the appropriate list of texture tiles (i.e. location and MIP-map level) to render from the current viewpoint. Second, the Texture Cache manages the tile pool. Finally, the Texture Producer loads and decodes required texture tiles asynchronously in the tile pool. Decoding of compressed texture data is implemented on GPU to minimize texture transfer. The Texture Producer can also generate procedural textures. Our system is transparent to the user, and the only parameter that must be supplied at runtime is the current viewpoint. No modifications of the mesh are required. We demonstrate our system on large scenes displayed in real time. We show that it achieves interactive frame rates even in low-memory low-bandwidth situations.