Parallel Image Analysis and Processing

The following sections are included:

• CONTENTS

The following sections are included:

• Parallel Image Analysis

• 2-D, 3-D Grammars and Automata

• Neural Nets and Learning

Advances in VLSI technology make it possible to realize systems of very high complexity in a small volume of hardware using integration. In many application fields, it is necessary to implement certain algorithms, or even complete information processing systems, directly in silicon. Application domains which are likely to benefit are in the fields of signal processing and scientific computing.

In this paper, we consider several steps which we believe to be essential in the design path of a special purpose architecture, and we present methodologies for achieving design requirements. These solutions are based on experience gathered in the Parallel VLSI Architecture group of IRISA.

Octrees offer a powerful means for representing and manipulating 3-D objects. This paper presents an implementation of octree manipulations using a new approach on a shared memory architecture. Octrees are hierarchical data structures used to model 3-D objects. The manipulation of these data structures involves performing independent computations on each node of the octree. Octrees are much easier to deal with than other forms of representations used to model 3-D objects especially where extensive manipulations are involved. When these operations are distributed among multiple processing elements (PEs) and executed simultaneously, a significant speedup may be achieved. Manipulations such as a complement, a union, an intersection and other operations such as finding the volume and centroid which this paper describes are implemented on the Sequent Balance multiprocessor, hi this approach the PEs are allocated dynamically, resulting in a uniform load balancing among them. The experimental results presented illustrate the feasibility of the approach. Although this evaluation has been originally done for shared memory machines, it will provide insight for the evaluation of other architectures.

This paper presents efficient and optimal parallel algorithms for multidimensional image template matching on CREW PRAM model. For an N^d image and an M^d window, we present an optimal (respectively efficient) algorithm which runs in 0(log(M)) time with 0(M^d×N^d/log(M) processors (respectively 0(M^d×N^d)). We also present efficient and optimal algorithms for solving the multidimensional array and pattern matching.

The two-dimensional mesh computer architecture has proven to be an appropriate means to apply parallel computation to problems in image processing. However, this is most often done using local-neighbourhood operations to accomplish image filtering and morphological transformations. The discovery of structures in an image such as repetitions and symmetries is another form of visual analysis, and yet relatively little has been done to apply mesh computers to this problem. In this paper, we apply the primitive operations of prefix scanning and sorting to efficiently implement a repetition finding algorithm for arrays. The computational complexity of the algorithm on a n × n mesh is 0(n log k) where k is the width of the largest repeated block in the array. The algorithm was implemented on a MasPar MP-1 computer. We describe variations of the algorithm for solving several related problems including the detection of partial symmetries in an image and repetitions in images modulo pixel-value transformations.

The graph structure is a strong formalism for representing pictures in syntactic pattern recognition. Many models for graph grammars have been proposed as a kind of hyper-dimensional generating systems, whereas the use of such grammars for pattern recognition is relatively infrequent. One of the reasons is the difficulty of building a syntax analyzer for such graph grammars. In this paper, we define a subclass of nPCE graph grammars and present a parsing algorithm of O(n) for both sequential and parallel cases.

This paper first shows that REC, the family of recognizable picture languages in Giammarresi and Restivo,³ is equal to the family of picture languages accepted by two-dimensional on-line tessellation acceptors in Inoue and Nakamura.⁵ By using this result, we then solve open problems in Giammarresi and Restivo,³ and show that (i) REC is not closed under complementation, and (ii) REC properly contains the family of picture languages accepted by two-dimensional nondeterministic finite automata even over a one letter alphabet.

“Leaf-size” (or “branching”) is the minimum number of leaves of some accepting computation trees of alternating devices. For example, one leaf corresponds to nondeterministic computation. In this paper, we investigate the effect of constant leaves of two-dimensional alternating Turing machines, and show the following facts: (1) For any function L(m, n), k leaf- and L(m, n) space-bounded two-dimensional alternating Turing machines which have only universal states are equivalent to the same space bounded deterministic Turing machines for any integer k ≥1, where m (n) is the number of rows (columns) of the rectangular input tapes. (2) For square input tapes, k + 1 leaf- and o(log m) space-bounded two-dimensional alternating Turing machines are more powerful than k leaf-bounded ones for each k ≥ 1. (3) The necessary and sufficient space for three-way deterministic Turing machines to simulate k leaf-bounded two-dimensional alternating finite automata is n^k+1 , where we restrict the space function of three-way deterministic Turing machines to depend only on the number of columns of the given input tapes.

We study some properties of array grammars, called puzzle grammars, introduced in Ref. 7. We give a new method, using puzzle grammar, for generating the set of rectangles. We prove that the emptiness problem for puzzle grammar is undecidable. We show that the non-overlapping problem for puzzle grammar is decidable.

We propose a new system of generating array languages in parallel, based on a partitioned cellular automaton (PCA), a kind of cellular automaton. This system is called a PCA array generator (PCAAG). The characteristic of PCAAG is that a “reversible” version is easily defined. A reversible PCA (RPCA) is a backward deterministic PCA, and we can construct a deterministic “inverse” PCA that undoes the operations of the RPCA. Thus if an array language is generated by an RPCA, it can be parsed in parallel by a deterministic inverse PCA without backtracking. We also define two subclasses of PCAAG, and give examples of them that generate geometrical figures.

We introduce a sequential/parallel parsing algorithm for analyzing 3-dimensional polyhedral objects represented by 3-d universal array grammars. The mechanism serves as a compromise between purely sequential methods, which normally take too much time, and purely parallel methods, which take too much hardware for large digital arrays. Several examples of 3-d polyhedral objects of various shapes and their corresponding parsing sequences are illustrated. Future research topics are discussed.

Three-dimensional (3D) shape recovery from a monocular image is the inverse process of optical projection and necessitates the use of additional constraints on 3D features of the objects. We have proposed the method of shape recovery based on some hypothetical constraints and its realization by energy minimization using a parallel network. In this paper, we will discuss an extension of our proposal with the aim of correcting noise and errors in an input image through the process of shape recovery. It is hardly possible to extract edges and vertexes free from noise and errors from a real image. For the robustness of the system, we must provide our system with the ability to correct such noise and errors. In this extension, we can also modulate the inclination of the process toward model-driven or data-driven.

Distortion invariant pattern recognition is an interesting problem from the biological and technological point of view. However, it has not yet been solved by neural networks in satisfactory way. This paper investigates an associative neural network system to improve the recalling accuracy for distortion patterns. On a perception type of neural network with feedback, error back-propagation algorithm and energy function are used for a learning process and a recalling process, respectively. By using gradated patterns as learning and unknown patterns, it is shown that the recalling accuracy becomes higher than using original pattern themselves.

An equal matrix grammar is a parallel rewriting system. In this paper, we consider the problem of learning equal matrix grammars from examples. We introduce a learning method based on control sets and show two subclasses learnable in polynomial time with learning methods for regular sets. We also show that for any equal matrix language there exists an equal matrix grammar learnable efficiently from positive structural examples only.

Learning of certain classes of two-dimensional picture languages is considered in this paper. Linear time algorithms that learn in the limit, from positive data the classes of local picture languages and locally testable picture languages are presented. A crucial step for obtaining the learning algorithm for local picture languages is an explicit construction of a two-dimensional on-line tessellation acceptor for a given local picture language. A polynomial time algorithm that learns the class of recognizable picture languages from positive data and restricted subset queries, is presented in contrast to the fact that this class is not learnable in the limit from positive data alone.

The following sections are included:

• INDEX