International Journal of Pattern Recognition and Artificial Intelligence

Several nonclosure properties of each class of sets accepted by two-dimensional alternating one-marker automata, alternating one-marker automata with only universal states, nondeterministic one-marker automata, deterministic one-marker automata, alternating finite automata, and alternating finite automata with only universal states are shown. To do this, we first establish the upper bounds of the working space used by "three-way" alternating Turing machines with only universal states to simulate those "four-way" non-storage machines. These bounds provide us a simplified and unified proof method for the whole variants of one-marker and/or alternating finite state machine, without directly analyzing the complex behavior of the individual four-way machine on two-dimensional rectangular input tapes. We also summarize the known closure properties including Boolean closures for all the variants of two-dimensional alternating one-marker automata.

Several nonclosure properties of each class of sets accepted by two-dimensional alternating one-marker automata, alternating one-marker automata with only universal states, nondeterministic one-marker automata, deterministic one-marker automata, alternating finite automata, and alternating finite automata with only universal states are shown. To do this, we first establish the upper bounds of the working space used by "three-way" alternating Turing machines with only universal states to simulate those "four-way" non-storage machines. These bounds provide us a simplified and unified proof method for the whole variants of one-marker and/or alternating finite state machine, without directly analyzing the complex behavior of the individual four-way machine on two-dimensional rectangular input tapes. We also summarize the known closure properties including Boolean closures for all the variants of two-dimensional alternating one-marker automata.

A parallel distributed scheme is presented for extracting a computable feature associated with self similar patterns. Observed patterns are assumed to be specified in terms of a set of contraction mappings that evokes an "avalanche of exploration" in image field. This intrinsically non-deterministic imaging process yields a conditional probability that is represented on a diffusion system. For identifying mapping set, a parallel projection algorithm is designed on a computable set of local minimums of the conditional distribution. The scheme is applied to dynamic detection of fractal patterns.

Over recent years clusters of workstations have begun to replace systems of mainframes. These workstations can be used to behave as a parallel machine, and then could supply supercomputing performance at modest cost. We report an experiment of such a network within PVM framework for an industrial image analysis application.

The goal of the application is to build an automated process of textile color pattern analysis. We plan to build several tools for parallel image analysis, and among those tools, we present here first the parallelization of a quantization algorithm and a way to parallelize a color image pyramid using the Parallel Virtual Machine environment.

One important point is the use of the distributed storage that represents a set of workstations. This distribution allows the complete parallelization of the Read/Write operations.

Asynchronous dynamics are introduced for the iterative computation of morphological image filters. We propose a fine-grain asynchronous algorithmic- architectural model that exploits these new possibilities to improve the convergence efficiency of such operators over standard sequential-recursive or parallel-synchronous update modes. We conclude with VLSI design perspectives and show how asynchronism can be exploited both at functional and architectural levels.

The z-buffer is a well-known hidden-part removal technique commonly used by local illumination algorithms. Some global illumination approaches use this technique too, in order to approximate energy exchanges. In this paper we propose a massively parallel implementation of the z-buffer on the MP-1 machine. Efficiency is achieved by precisely studying the different stages of the algorithm, and by taking care in correctly using the SIMD control of the architecture. Local illumination models are then applied to the z-buffer algorithm, by using Gouraud and Phong's interpolations. Finally, the parallel z-buffer is used in a massively parallel radiosity algorithm. The results obtained allow to provide quickly illuminated images by decreasing dramatically the computation time required for global illumination.

We propose in this paper, a parallel implementation of a ground visualization algorithm. Our input data consist in a Digital Elevation Model (DEM) covering a rectangular region, together with a raster image of the same area (the texture). The goal of the algorithm is to compute in parallel, images of the DEM from any point of view while mapping the texture onto the surface. The main originality of our approach concerns the distribution of the data, leading to a load-balanced and scalable parallel algorithm. We use a workload estimation to partition the output image, and then redistribute the input data according to this division. Special attention is paid on the data structures used for minimizing the cost of communications.

Medical imaging is a powerful mean to access dynamic function of 3D deformable organs of the body. Due to the flow of incoming data, multiresolution methods on parallel computers is the only way to achieve complex processings in reasonable time. We present an active pyramid to model dynamic volumes. This pyramid is built on the first volume of a sequence and contains a binary model of the objects of interest. Previous knowledge is introduced within this binary model. The structure of the pyramid is rigid, but its main interest is that its components are deformed to fit the data using energetical constraints. A multiresolution algorithm based on self-organizing maps is then applied to deform the model through time. This algorithm matches the different levels of the pyramid in a coarse to fine approach. The output of the matching process is the field of deformation, modeling the transformations. This pyramid is applied to real data in the result section. The rigid structure of the pyramid is suitable for massively parallel architectures.

This paper presents a load-balanced parallelization of the well known Marching-Cubes algorithm, that aims at constructing an iso-surface in a 3D image. We first derive a modelization for the computation time as a function of the generated surface complexity. The workload associated to each slice of the input data is evaluated by counting the number of vertices that will be generated on that slice. The slices are then locally redistributed to ensure a balanced workload. We give an upper bound on the number of polygons of the triangulation, and present a family of surfaces whose number of triangles tends to this bound. This analysis allows us to foresee (and thus to allocate) the memory size needed for the data structures and to assign to each vertex a unique global reference.

Experiments done on an Intel Paragon machine are given both for synthetic and medical images. They show the usefulness of our dynamic data redistribution scheme.