VLSI and Parallel Computing for Pattern Recognition and Artificial Intelligence

The following sections are included:

• CONTENTS

Many problems in pattern recognition, artificial intelligence, image processing and computer vision have applications in automatic parts inspection and assembly, robotic vision and control, image registration, geographic and topographic map matching, navigational guidance, target recognition, character recognition, chromosome classification, interpretation of medical images, scene analysis etc. Pattern recognition often involves matching patterns of different shapes, sizes and representations. The task of pattern matching could be complex and computationally intensive depending upon the application and the procedure used. Similarly, in the fields of image processing and computer vision, the performance of sequential computers has been found to be quite inadequate since most applications require processing in real time. A 1024 × 1024 image frame with 256 gray levels requires 8 M pixels for storage and most applications require the storage and processing of multiple frames at very high speeds. Multimedia and video applications require frame rates of 50 to 80 frames per second. Thus, the throughput requirements of these applications could run into giga operations per second. Such tasks often perform a large number of repetitive computations on different data sets, make use of regular and local operations, are modular, and have a fair amount of inherent parallelism. With the rapid advances in VLSI technology and parallel processing, the design of high performance hardware for such computationally intensive tasks has become an attractive solution in real-time applications.

Although massively parallel arrays for spatially mapped applications have been proposed since the 1950s⁴² and built since the 1960s,¹² there have been very few systematic empirical studies that cover more than a small fraction of the design space. The problems have included the lack of a test suite of non-trivial application codes; inadequate language support; the difficulties of balancing evaluation performance with flexibility; and balancing test suite portability with accuracy of evaluation. We describe an environment that addresses these problems. A realistic workload including a series of applications currently being used as building blocks in vision research has been constructed. Both flexibility in architectural parameter selection and simulation efficiency are maintained with a novel new technique that combines virtual machine emulation with trace-driven simulation. The trade-off between fairness to diverse target architectures and programmability of the test suite is addressed through the use of operator and application libraries for a small set of critical functions. We also present examples of the type of results we are obtaining, including the effects of changing ALU designs and datapath widths, finding critical points in register set and cache sizes, the benefits of various types of router networks, and the performance cost of processor virtualization.

In this paper we describe a reconfigurable architecture for image processing and computer vision based on a multi-ring network which we call a Reconfigurable Multi-Ring System (RMRS). We describe the reconfiguration switch for the RMRS and also describe its VLSI implementation. The RMRS topology is shown to be regular and scalable and hence well-suited for VLSI implementation. We prove some important properties of the RMRS topology and show that a broad class of algorithms for the n-cube can be mapped to the RMRS in a simple and elegant manner. We design and analyze a class of procedural primitives for the SIMD RMRS and show how these primitives can be used as building blocks for more complex parallel operations. We demonstrate the usefulness of the RMRS for problems in image processing and computer vision by considering two important operations – the Fast Fourier Transform (FFT) and the Hough transform for detection of linear features in an image. Parallel algorithms for the FFT and the Hough transform on the SIMD RMRS are designed using the aforementioned procedural primitives. The analysis of the complexity of these algorithms shows that the SIMD RMRS is a viable architecture for problems in computer vision and image processing.

Very Large Array Processors (VLAP) will be the need of the future for solving computationally intense Very Large Problems (VLP) common in pattern recognition, image processing and other related areas of digital signal processing. Design methodology of such VLAPs for massively parallel dedicated/general purpose applications is highly complex. Two companion papers (Part 1 and Part 2) on VLAP are presented in this issue. In Part 1, we propose a VLAP called Reconfigurable GIPOP Processor Array (RGPA). The RGPA is made up of high performance processing elements called the Generalized Inner Product Outer Product (GIPOP) processor. Unlike the traditional special/general purpose processors, ours has a totally different and new architecture and organization involving higher level functional units to match with the complex computational structures of numeric algorithms and suitable for massively parallel processing. We also present a strategy for mapping VLPs on VLAPs. In Part 2, we propose a novel VLSI design methodology for implementing cost effective and very high performance processors meant for special purpose applications and in particular, for VLAPs.

The types of functional VLSI chips needed for general and special purpose (computationally intensive) applications are wide ranging. Hence, to reduce the turnaround time of these VLSI chips, mask/field programmable PLAs, gate arrays SLAs and FPGAs are available. However these VLSI arrays are unsuitable for designing ultrahigh performance special purpose VLSI chips. There is a strong need for developing a suitable mask programmable VLSI structures exclusively for designing ultrahigh performance and cost-effective special purpose systems. For this purpose, a macro cell based mask programmable Pacube (PA³ — Programmable Array of Array Adders) VLSI array is proposed in this paper. These arrays can be mask programmed for building cost-effective super computing VLSI functional units. Another important feature is the architecture of the macro-cell, which is designed in such a way that the functional units corresponding to the G-set equations when mapped on the macro-cell arrays possess identical data flow control. This leads to a highly simplified control design for executing complex computations.

The Inverse Discrete Cosine Transform (IDCT) is an important function in HDTV, digital TV and multimedia systems complying with JPEG or MPEG standards for video compression. However, the IDCT is computationally intensive and therefore very expensive to implement in VLSI using direct matrix multiplication. By properly arranging the input coefficient sequence and the output data, the rows and columns of the transform matrix can be reordered to build modular regularity suitable for custom implementation in VLSI. This regularity can be exploited, so that a single permutation can be used to derive each output column from the previous one using a circular shift of an accumulator's input data multiplied in a special sequence. This technique, using only one 1-dimensional IDCT processor and seven constant multipliers, and its implementation are presented. Operation of 58 MHz under worst case conditions is easily achieved, thus making the design applicable to a wide range of video and real time image processing applications. Fabricated in 0.5 micron triple metal CMOS technology, the IDCT contains 70,000 transistors occupying 7 mm² square silicon. The design has been used on an AT&T MPEG video decoder chip.

In this paper we present and analyze a systolic structure to support the Generalized Hough Transform. Among the structural methods for object recognition, this transform is well established for its flexibility and noise immunity. Its use in actual systems has been however limited by the computational cost associated with the management of votes. Previous work has shown that a limited amount of memory can substitute the large address space required for building the histogram of votes. The systolic queue here introduced substitutes the address space required in a M-dimensional voting process, where the quantization of each dimension into Q bins yields a space complexity O(Q^M). An N-stage queue uses 3 M log(Q) memory bits at each stage and is capable of accumulating the incoming votes on the fly. The flow of data within the queue is designed to minimize the probability that new votes are lost because of overflow. We derive analytic expressions for the growth of the queue during the set-up period and for the time each new vote spends within the queue if it is not accumulated; furthermore, we show the conditions for the arrival times of a couple of coincident addresses to be detected and merged. The analysis of the time behaviour of the queue supports the experimental evidence that such a structure performs the accumulating process very reliably. A VLSI integrated circuit embedding a 50-stage queue is the third in a chip-set for the real time implementation of the Generalized Hough Transform.

We present a new high speed parallel architecture and its VLSI implementation to design a special purpose hardware for real-time lossless image compression/decompression using a decorrelation scheme. The proposed architecture can easily be implemented using state-of-the-art VLSI technology. The hardware yields a high compression rate. A prototype 1-micron VLSI chip based on this architectural idea has been designed. The scheme is favourably comparable to the lossless JPEG standard image compression schemes. We also discuss the parallelization issues of the lossless JPEG standard still compression schemes and their difficulties.

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.

We present four algorithms to perform template matching of an N × N image with an M × M template. The first algorithm is sequential, and the others are based on a SIMD mesh connected computer with N × N processors. In the first three algorithms, both the image and the template are represented by quadtrees, whereas in the last one, the template is represented by a quadtree, and the image is represented by a matrix. The time complexities of the four algorithms are respectively upper-bounded by α₁N²M², α₂N + β₂M², α₃N + β₃M², and β₄M², where α₁, α₂, β₂, α₃, β₃, and β₄ are constants.

Given a pattern of length m and a text of length n, commonly m ≪ n, this paper presents a randomized parallel algorithm for pattern matching in O(n^1/10) (=O(n^1/10 + (n − m)^1/10)) time on a newly proposed n^3/5 × n^2/5 modular mesh-connected computers with multiple buses. Furthermore, the time bound of our parallel algorithm can be reduced to O(n^1/11) if fewer processors are used.

In this paper we present a VLSI fuzzy processor whose main features are a scalable parallel architecture, and the computation of fuzzy inferences based on the a-level set theory, both of which are important in the field of intensive fuzzy computing, as in fuzzy expert systems. A specific analysis is made in the paper, of techniques for the representation of fuzzy sets, in relation to the amount of area occupied and the forms they can assume. From this analysis a solution is extracted and then used for the processor presented in the paper.

The architecture of the processor is chosen after the assessment of possible alternatives by analyzing an appropriate probabilistic model. The processor comprises a set of units which work parallelly and asynschronously to process the various rules. The structure is easy to scale up, as an increase in the number of processing units does not produce bottlenecks in performance. The performance obtainable is about 310 KFLIPS, with a clock frequency of 60 Mhz, 8 input variables, either crisp or fuzzy, and an 8-bit resolution.

This paper describes the design and the VLSI implementation of a novel architecture that performs image rotation in real time. In order to improve throughput, we divide an image-frame into a number of windows. The rotation of each window-center as well as the final displacement of individual pixels within a window is then calculated. A CORDIC-based scheme is used to compute the displacement of a pixel. Our architectural design is incorporated into a chip that has been laid out using VTI (VLSI Technology Inc.) tools obeying the 1.5 μm SCMOS design rules. The chip owes its high processing capability to a combination of pipelining and parallel-processing techniques. For a clock frequency greater than 10.6 MHz, we can perform the rotation of a 512 × 512 gray-level digital image at the rate of 30 frames per second. The chip utilizes around 35,000 transistors and has an estimated silicon area of 211 mils × 276 mils.