Sum of Absolute Difference Implementations for Image Processing on FPGAs

SAD (sum of absolute differences) is a technique for evaluating the similarity between two same size regions, and widely used in stereovision, optical flow, motion estimation and so on. In these applications, a given image is scanned using a fixed size region (window), and the window is compared with the same size regions in another image. When the window is overlapped for generating a dense map, we have several implementation alternatives; storing the partial sums for reusing them afterward or recalculating them when they become necessary, scanning left to right or top to bottom, and dividing the search space horizontally or vertically. With the combination of these alternatives, we can implement a wide range of circuits. In this paper, we evaluate the performance and the size of those circuits, and makes it clear which circuit fits which type of FPGA.