We describe our implementation of a parallel depth recovery scheme for a four-camera multibaseline stereo in a convergent configuration. Our system is capable of image capture at video rate. This is critical in applications that require three-dimensional tracking. We obtain dense stereo depth data by projecting a light pattern of frequency modulated sinusoidally varying intensity onto the scene, thus increasing the local discriminability at each pixel and facilitating matches. In addition, we make most of the camera view areas by converging them at a volume of interest. Results show that we are able to extract stereo depth data that are, on the average, less than 1 mm in error at distances between 1.5 to 3.5 m away from the cameras.>

Fourier inversion is an efficient method for image reconstruction in a variety of applications, for example, in computed tomography and magnetic resonance imaging. Fourier inversion normally consists of two steps, interpolation of data onto a rectilinear grid, if necessary, and inverse Fourier transformation. Here, the authors present interpolation by the scan-line method, in which the interpolation algorithm is implemented in a form consisting only of row operations and data transposes. The two-dimensional inverse Fourier transformation can also be implemented with only row operations and data transposes. Accordingly, Fourier inversion can easily be implemented on a parallel computer that supports row operations and data transposes on row distributed data. The conditions under which the scan-line implementations are algorithmically equivalent to the original serial computer implementation are described and methods for improving accuracy outside of those conditions are presented. The scan-line algorithm is implemented on the iWarp parallel computer using the Adapt language for parallel image processing. This implementation is applied to magnetic resonance data acquired along radial-lines and spiral trajectories through Fourier transform space.

Image processing and computer vision are natural applications for high performance computing (here considered to be general-purpose parallel supercomputing), but there are many barriers to its effective use in computer vision. These barriers are described, two systems (the Carnegie Mellon ALVINN system and the animate vision model at Rochester) that overcame them are discussed, and then a world-wide survey is taken of application of HPC to image processing and computer vision. Finally, the future of this field is described.

For a wide variety of applications, both task and data parallelism must be exploited to achieve the best possible performance on a multicomputer. Recent research has underlined the importance of exploiting task and data parallelism in a single compiler framework, and such a compiler can map a single source program in many different ways onto a parallel machine. The tradeoffs between task and data parallelism are complex and depend on the characteristics of the program to be executed, most significantly the memory and communication requirements, and the performance parameters of the target parallel machine. We present a framework to isolate and examine the specific characteristics of programs that determine the performance for different mappings. Our focus is on applications that process a stream of input, and whose computation structure is fairly static and predictable. We describe three such applications that were developed with our compiler: fast Fourier transforms, narrowband tracking radar; and multibaseline stereo. We examine the tradeoffs between various mappings for them and show how the framework is used to obtain efficient mappings.>

Parallel image processingfor robotics applications differs in a fundamental way from parallel scientific computing applications:the problem size is fixed, and latency requirements are tight.This brings Amdhal 's law in eflect with full force, so that message-passing latency and bandwidth severely restrict performance.In this paper we examine an application from this domain, stereo image processing, which has been imple- mented in Adapt, a niche language for parallel image processing implemented on the Carnegie iWellon-Intel Corporation i Warp.High performance has been achieved for this application.We show how a I/O building block approach on i Warp achieved this, and then examine the implications of this performance for more traditional machines that do not have i Warp's rich I/O primitive set.For example, it does the robot no good to begin processing a new image before the last image is acted upon; doing so can cause the robot to doubly compensate for an inaccuracy in steering, and lead to instability in the control algorithm.WJe would like to speed up this cycle through the use of parallel computers.This paper addresses the perceptual issues, namely capturing and processing sensory data.This tends to be a major bottleneck in such systems, since images are large and often sig-C31993 ACM 0-81864340-4/93/0011 $1.50 Capture Sensory Data Process Sensory Data Parallel systems are widely recognized to be increasing in message passing bandwidth, but latency is not decreasing as rapidly.As we apply more and more processors to a particular problem, message passing latency plays a greater role in limiting overall speed

Several methods for parallel affine image warping on a linear processor array are considered. The methods were implemented on the Carnegie Mellon Warp machine and the Carnegie Mellon-Intel Corporation iWarp computer (treated as a linear array), and performance figures are provided. Both systolic methods, which feed one of the images in a stream, and non-systolic methods, which partition both images, are treated. A scanline method that combines some of the features of both, but which requires a fast transposed method is also described. The authors articulate three characteristics that affect the design of parallel image warping algorithms: affine warping is easily invertible, the mapping is known at the start of execution, and nearby input pixels map to nearby output pixels. The authors conclude that non-systolic methods give slightly better execution time and are easier to programs than systolic methods but require much larger processor memories.>

Abstract Apply is a machine‐independent, low‐level image processing language for expressing local window operations. It has two main advantages: (1) it significantly reduces the programming effort, and (2) it can be mapped onto a wide range of parallel computers. In this paper we report our recent experience on implementing Apply on a Meiko Computing Surface (transputer array machine) using a farmer/gather model. The performance of the Meiko implementation on a number of edge detection algorithms including the popular Canny operator is analysed. Results suggest that the performance of Apply generated code represents peak performance and it is likely to be as efficient as hand‐written code.

The authors review the history of the Carnegie-Mellon Warp machine on Navlab, an autonomous land vehicle, and describe three Navlab vision systems implemented on the Warp machine. They then critically evaluate components of Warp in light of this experience. The Warp machine was used to implement stereo vision for obstacle avoidance and color-based road-following systems. The stereo-vision system was FIDO, which is derived from some of the earliest work in vision-guided robot vehicle navigation. Two color-based road following systems were implemented; one adapted conventional vision techniques to the problem of road recognition and the other used a neural network-based technique to learn road following online. Finally, the authors discuss the value of applications integration with machine development, discuss the limitations of the attached processor model, and give recommendations for future systems.>

The iWarp processor, which integrates both communication and computation functions on a single VLSI component, is described. The iWarp component and subsystems including it are powerful building blocks for constructing a new generation of application-specific computing systems. These special-purpose systems can achieve very high performance, while maintaining a high degree of flexibility to address different needs of an application. In particular, iWarp systems deliver high computation bandwidth (up to 20 GFLOPS for a 1024 cell system), as well as high communication bandwidth (320 Mbytes/s per cell). Programming these systems is assisted by modern tools such as optimizing compilers and parallel program generators.>

A specialized language, called Adapt, for local and global image processing on parallel processors is presented. Adapt is based on a split and merge model. The input image is split into sections, which are processed separately on different processors, and the results are merged using a function written by the user. This model is quite general; any image processing operation that can be computed from top to bottom or from bottom to top on an image can be computed with it. The use of Adapt is illustrated with several programs for important global operations, including histogram, Hough transform, minimum bounding rectangle, and connected components. A preliminary implementation of Adapt exists on the Carnegie Mellon Warp machine. Performance figures from this implementation are provided. A description of how Adapt can be implemented on other architectures is given.>

iWarp is a parallel architecture developed jointly by Carnegie Mellon University and Intel Corporation. The iWarp communication system supports two widely used interprocessor communication styles: memory communication and systolic communication. This paper describes the rationale, architecture, and implementation for the iWarp communication system.

The Warp machine is a systolic array computer of linearly connected cells, each of which is a programmable processor capable of performing 10 million floating-point operations per second (10 MFLOPS). A typical Warp array includes ten cells, thus having a peak computation rate of 100 MFLOPS. The Warp array can be extended to include more cells to accommodate applications capable of using the increased computational bandwidth. Warp is integrated as an attached processor into a Unix host system. Programs for Warp are written in a high-level language supported by an optimizing compiler. The first ten-cell prototype was completed in February 1986; delivery of production machines started in April 1987. Extensive experimentation with both the prototype and production machines has demonstrated that the Warp architecture is effective in the application domain of robot navigation as well as in other fields such as signal processing, scientific computation, and computer vision research. For these applications, Warp is typically several hundred times faster than a VAX 11/780 class computer. This paper describes the architecture, implementation, and performance of the Warp machine. Each major architectural decision is discussed and evaluated with system, software, and application considerations. The programming model and tools developed for the machine are also described. The paper concludes with performance data for a large number of applications.

We report progress in visual road following by autonomous robot vehicles. We present results and work in progress in the areas of system architecture, image rectification and camera calibration, oriented edge tracking, color classification and road-region segmentation, extracting geometric structure, and the use of a map. In test runs of an outdoor robot vehicle, the Terregator, under control of the Warp computer, we have demonstrated continuous motion vision-guided road-following at speeds up to 1.08 km/hour with image processing and steering servo loop times of 3 sec.

This paper describes the scan line array processor (SLAP), a new architecture designed for high-performance yet low-cost image computation. A SLAP is a SIMD linear array of processors, and hence is easy to build and scales well with VLSI technology; yet appropriate special features and programming techniques make it efficient for a surprisingly wide variety of low and medium level computer vision tasks. We describe the basic SLAP concept and some of its variants, discuss a particular planned implementation, and indicate its performance on computer vision and other applications.

Warp is a programmable systolic array processor. One of its objectives is to support computer vision research. This paper shows how the Warp architecture can be used to fulfill the computational needs of low-level vision. We study the characteristics of low-level vision algorithms and show how they lead to requirements for computer architecture. These requirements are met by Warp. We then describe how the Warp system can be used. Warp programs can be classified in two ways: chained versus severed, and heterogeneous versus homogeneous. Chained and severed characterize the degree of interprocessor dependency, while heterogeneous and homogeneous characterize the degree of similarity between programs on individual processors. Taken in combination, these classes give four user models. Sophisticated programming tools are needed to support these user models.