1AbstractThis paper describes the design andimplementation of two image-processing algorithmsusing the custom computing platform. is a reconfigurable system that can be tailored toperform a wide variety of tasks. The particular tasksdiscussed here are the Hough transform, a well-knowntechnique for detecting lines in an image, and pyramidgeneration, the process of transforming a single imageinto a set of filtered images with successively lowerspatial resolution. This paper describes how thesecomputationally intensive processes have been mappedonto hardware. Both processes have beendesigned to operate at high speed. In particular, thegeneration of both Gaussian (low-pass) and Laplacian(band-pass) pyramids can occur concurrently in realtime using images from a video camera, assuming thestandard frame rate of 30 images per second. Resultsare presented to illustrate the efficacy of reconfigurableFPGA-based machines to image processingapplications.1 IntroductionGeneral-purpose workstations can provide acceptableperformance for many image-processing tasks whenhigh speed is not required. However, for suchapplications as robotic control, visual tracking, andautonomous navigation, fast image processing isessential. Unfortunately, fast computation rates aredifficult to achieve because of the large amount of dataassociated with images. General-purpose machines areoverwhelmed not only by the numbers of computationsrequired, but also by the I/O requirements of real-timeimage processing, which exceed 7 Megabytes persecond for typical monochrome video cameras.When high performance is needed, the traditionalapproach has been to develop application-specifichardware. The drawbacks of this approach are lengthydesign cycles and costly redesigns when newalgorithms are developed (or when mistakes are foundin the original design). An attractive alternative is toutilize reconfigurable FPGA-based platforms that canbe tailored to different applications without sacrificingperformance.This paper examines the computational benefits of thereconfigurable approach by presenting two case studiesusing the attached processor. A brief overviewof is given in Section 2. The two tasks that arepresented are well known in the image-processingcommunity, and are substantially different in nature.The first of these, described in Section 3, is a 23-FPGAdesign to perform the Hough transform and relatedpreprocessing functions. Section 4 describes two 10-FPGA designs for generating real-time (and near real-time) image pyramids at the standard video rate of 30images per second. Section 5 is a comparison andsummary of these designs.2 The Splash 2 Architecture is a second-generation reconfigurable attachedprocessor designed by the Supercomputing ResearchCenter in Bowie, Maryland. This section presents abrief overview of the system; refer to [Arno92] formore details.A system consists of a Sun SPARC-2 host, aninterface board, and one or more array boards. Up to15 array boards are supported within a singlesystem, and each contains 17 Xilinx XC4010 FPGAsarranged in a linear array and are fully connectedthrough a 16x16 crossbar. (Refer to Figure 1.) The 17FPGAs are designated X0 - X16, and each has a local256Kx16 RAM. The principle data paths betweenFPGAs are 36 bits in width, and can thereforeaccommodate up to four 8-bit picture elements (pixels)simultaneously along with a 4-bit control word.Finding Lines and Building Pyramids with Splash 2A. Lynn Abbott, Peter M. Athanas, Luna Chen, and Robert L. ElliottThe Bradley Department of Electrical EngineeringVirginia Polytechnic Institute and State UniversityBlacksburg, Virginia 24061-01112X X X X X X X XX X X X X X X X12345678910111213141516CrossbarX0X X X X X X X XX X X X X X X X12345678910111213141516CrossbarX0X X X X X X X XX X X X X X X X12345678910111213141516CrossbarX0Processing board #1Processing board #2Processing board #nInput DMA XLOutput DMA XR Interface boardRBusSIMD BusSBus extensionSUN SPARC-2workstationSBusData infromvideo digitizerData outto frame grabber3636Figure 1. The architecture. Up to 15 reconfigurablearray boards can be placed in a system. Each boardcontains 17 Xilinx FPGAs that are connected as a lineararray and through a crossbar.Applications are "programmed" for by creatinga VHDL model which is simulated, refined, andsynthesized to a gate list. An alternative method is touse schematic capture and supporting software such asXBLOX [Xili91]. The gate list is finally mapped ontothe FPGA architecture using the Xilinx or the Synopsissynthesis tools. This design cycle is described morethoroughly in [Arno93].3 Line Detection using theHough Transform3.1 The Hough TransformThe Hough transform is a procedure for detectingstraight lines in an image [Houg62, Duda72]. Linedetection is a very useful low-level operation,particularly for image analysis of scenes that maycontain man-made objects such as buildings, roads, andmanufactured goods. Extensions of the method may beused to detect curves or other objects of known shape.The essence of the method is to transform edge pointsin an image to curves in parameter space. Anaccumulator array is maintained to contain thesecurves. After all edge points have been processed,peaks in the accumulator array (also called the "Hougharray") indicate the parameters of the lines in theoriginal image.To see this, consider the following equation for a line:dx y=+cos sinθθ. The variables x and ycorrespond to horizontal and vertical imagedimensions, respectively. As illustrated in Figure 2a,the value d represents the perpendicular distance of theline from the origin, and θ is the angle of theperpendicular with the x-axis. (The standard slope-intercept equation is not used because of problems withvertical lines.) The problem of line detection is torecover the two parameters d and θ that pass through asignificant number of edge points in the image. This isdone by mapping each edge point (xyii,) in the imageto a sinusoid in d-θ parameter space, as illustrated inFigure 2b. For collinear edge points, all of thecorresponding sinusoids will intersect at the singlepoint (djj,θ) which corresponds to the line throughthe edge points.The standard Hough approach implements theparameter space as an accumulator array, where eachquantized d-θ cell in the array corresponds to a singleline in the image. Each cell in the array is initialized to0. For each edge point, the corresponding sinusoid