Prewitt Edge Magnitude Detection in SA-C


The Prewitt edge detection masks are one of the oldest and best understood methods of detecting edges in images. Basically, there are two masks, one for detecting image derivatives in X and one for detecting image derivatives in Y. To find edges, a user convolves an image with both masks, producing two derivative images (dx & dy). The strength of the edge at any given image location is then the square root of the sum of the squares of these two derivatives. (The orientation of the edge is the arc tangent of dy/dx.)

In practice, one usually thresholds the result of Prewitt edge detection, in order to produce a discrete set of edges. Below, we show a source image and the thresholded result of Prewitt edge detection:

Raw B/W image of Fort Hood, TX
Result of Prewitt + Threshold

For a more selective (but more complex) edge detections operator, see the Canny operator.

SA-C Source Code

export main;
#include <>
// This is the canonical Prewitt operator. However, instead of
// writing it as an example of convolution, we have written it
// for speed. By making the column operations explicit, we hope
// to enable tcse for computing the vertical edge response. Also,
// we minimize the number of negations. We also threshold the 
// output to 0 or 255
int11 sum3(uint8 data[3]) {}

uint8[:,:] main(uint8 Image[:,:]) 
  uint8 R[:,:] = 
  // PRAGMA (nextify_cse,part_unroll(8,1) )
  for window W[3,3] in Image {
     int11 horiz_mag = sum3(W[2,:]) - sum3(W[0,:]);
     int11 vert_mag = sum3(W[:,2]) - sum3(W[:,0]);
     uint11 edge_mag = SC_sqrt22((int22)horiz_mag*horiz_mag + (int22)vert_mag*vert_mag);
     uint8 clipped_mag = if (edge_mag >127) return(255)
                         else return(0); 
  } return(array(clipped_mag));
} return(R);

Performance Results

The comparisons were made by compiling SA-C routines with the Sept., 2001 version of the SA-C compiler and executing them on an Annapolis Microsystems StarFire with an Xilinx XV-1000 FPGA. The compiler did 8-fold vertical stripmining, among other optimizations. Since the magnitudes of Prewitt edges can be computed using the Intel Image Processing Library (IPL), we used the IPL as a basis of comparison. (Note that IPL routines are hand-optimized assembly code designed to take advantage of MMX technology.) The IPL Prewitt was executed under Windows2000 on an 800MHz Pentium III . The test images were 8-bit 512x512 images.

Seconds (800MHz P3)
Seconds (AMS Starfire)
Cycles (MClocks)
42.1 MHz

Is it bragging to point out that SA-C + FPGA beats hand-optimized Pentium assembly code by a factor of over eighty?

For previous results, click here.