The distance between two labeled ordered trees, /spl alpha/ and /spl beta/, is the minimum cost sequence of editing operations (insertions, deletions, and substitutions) needed to transform a into /spl beta/ such that the predecessor-descendant relation between nodes and the ordering of nodes is not changed. Approximate tree matching has applications in genetic sequence comparison, scene analysis, error recovery and correction in programming languages, and cluster analysis. Edit distance computation is a computationally intensive task, and the design of special purpose hardware could result in a significant speed up. This paper proposes a VLSI architecture for computing the distance between ordered h-ary trees, as well as arbitrary ordered trees. This is the very first special purpose architecture that has been proposed for this important problem. The architecture is a parallel realization of a dynamic programming algorithm and makes use of simple basic cells and requires regular nearest-neighbor communication. The architecture has been simulated and verified using the Cadence design tools.

The distance between two labeled ordered trees, /spl alpha/ and /spl beta/ is the minimum cost sequence of editing operations (insertions, deletions and substitutions, needed to transform or into /spl beta/ such that the predecessor-descendant relation between nodes and the ordering of nodes is not changed). Approximate tree matching has applications in genetic sequence comparison, scene analysis, error recovery and correction in programming languages, and cluster analysis. Edit distance determination is a computationally intensive task, and the design of special purpose hardware could result in a significant speed up. This paper describes in detail a VLSI architecture for computing the edit distance between arbitrary ordered trees, based on a parallel, systolic realization of the dynamic programming algorithm proposed by S.Y. Lu (1979). This architecture represents a significant improvement over that described by Sastry and Ranganathan (1994), which restricted the type of trees that could be processed by it. Two partitioning strategies to process trees of arbitrary sizes and structures on a fixed size implementation in multiple passes are proposed and analyzed.>

The recognition of polygons in 3-D space is an important task in robot vision. Advances in VLSI technology have now made it possible to implement inexpensive, efficient and very fast custom designs. The authors have earlier proposed a class of VLSI architectures for this computationally intensive task, which makes use of a set of local shape descriptors for polygons which are invariant under affine transformations, i.e. translation, scaling, rotation and orthographic projection from 3-D to any 2-D plane. This paper discusses the design and implementation of PMAC, a prototype for polygon matching, as a custom CMOS VLSI chip. The recognition procedure is based on the matching of edge-length ratios using a simplified version of the dynamic programming procedure commonly employed for string matching. The matching procedure also copes with partial occlusions of polygons. The implemented architecture is systolic and fully utilizes the principles of pipelining and parallelism in order to obtain high speed and throughput.

Depth recovery from gray-scale images is an important topic in the field of computer and robot vision. Intensity gradient analysis (IGA) is a robust technique for inferring depth information from a sequence of images acquired by a sensor undergoing translational motion. IGA obviates the need for explicitly solving the correspondence problem and hence is an efficient technique for range estimation. Many applications require real time processing at very high frame rates. The design of special purpose hardware could significantly speed up the computations in IGA. In this paper, we propose two VLSI architectures for high-speed range estimation based on IGA. The architectures fully utilize the principles of pipelining and parallelism in order to obtain high speed and throughput. The designs are conceptually simple and suitable for implementation in VLSI.>

The edit distance between two strings a1, ..., a/sub m/ and b/sub 1/, ..., b/sub n/ is the minimum cost s of a sequence of editing operations (insertions, deletions and substitutions) that convert one string into the other. This paper describes the design and implementation of a linear systolic array chip for computing the edit distance between two strings over a given alphabet. An encoding scheme is proposed which reduces the number of bits required to represent a state in the computation. The architecture is a parallel realization of the standard dynamic programming algorithm proposed by Wagner and Fischer (1974), and can perform approximate string matching for variable edit costs. More importantly, the architecture does not place any constraint on the lengths of the strings that can be compared. It makes use of simple basic cells and requires regular nearest neighbor communication, which makes it suitable for VLSI implementation. A prototype of this array has been built at the University of South Florida.>

The recognition of patterns is an important task in robot and computer vision. The patterns themselves could be one- or two-dimensional, depending upon the application. Pattern matching is a computationally intensive and time consuming operation. The design of special purpose hardware could speed up the matching task considerably, making real-time responses possible. Advances in parallel processing and VLSI technologies have made it possible to implement inexpensive, efficient and very fast custom designs. Many approaches and solutions have been proposed in the literature for hardware implementations of pattern matching techniques. In this paper, we present a detailed overview of some of the important contributions in the area of hardware algorithms and architectures for pattern matching.

Scene matching is the problem of matching regions of two images of the same scene taken by different sensors at different times or under different viewing conditions. Hierarchical scene matching is a technique for reducing the amount of computation involved in scene matching applications. Most of the past research on this problem has concentrated on efficient software algorithms, and very little effort has been expended on custom hardware solutions. We describe the design of SMAC, a new VLSI architecture for Hierarchical Scene Matching. This architecture achieves a significant amount of speedup by utilizing a large amount of parallelism and pipelining. The paper also describes the design and implementation of a prototype CMOS VLSI chip that implements the exhaustive search task of the scene matching algorithm.>

The edit distance between two strings is defined as the minimum cost of a sequence of editing operations (insertions, deletions and substitutions) that convert one string into the other. This paper presents a linear systolic array for computing the edit distance between two strings over a given alphabet. An encoding scheme is proposed which reduces the number of bits required to represent a state in the computation. The architecture is a parallel realization of the standard dynamic programming algorithm proposed by Wagner and Fischer (1974), and can perform approximate string matching for variable edit costs. More importantly, the architecture does not place any constraint on the lengths of the strings that can be compared. It makes use of simple basic cells and requires regular nearest-neighbor communication, which makes it suitable for VLSI implementation. A prototype of this array is currently being built.>

A class of VLSI architectures is proposed for the computationally intensive task of polygon recognition in 3-D space. They make use of a set of local shape descriptors for polygons that are invariant under affine transformations. The recognition procedure is based on the matching of edge length ratios using a simplified version of the dynamic programming procedure commonly used for string matching. The matching procedure also copes with partial occlusion of polygons. The architectures are systolic and fully utilize the principles of pipelining and parallelism in order to obtain high speed and throughput. A prototype VLSI chip implementing one of the proposed architectures is currently being built.>

Scene matching is the problem of matching regions of two images of the same scene taken by different sensors at different times or under different viewing conditions. Hierarchical scene matching generates a multiresolution pyramid of the images to be matched. The authors describe hierarchical scene matching technique, related work and their proposed VLSI architecture. They present a description of the three subsystems-pyramid generation block, exhaustive search block and template match block. Then they briefly describe the performance attainable with the proposed architecture which uses a large amount of parallelism and pipelining.>