Hardware principles for the design of a stereo-matching state machine based on dynamic programming

Abstract

This paper presents basic design principles for hardware implementation of a two-pass stereo-matching algorithm based on dynamic programming. For the first-pass a state-machine is proposed for the recursive calculation of the cost-function. The state-machine works along the diagonal of a 2-D disparity space for each epipolar pair of image scan-lines. On-chip local RAM stores tags that denote the minimum transition cost to every point in the disparity space among possible costs from all three neighboring points. All calculations are within a pre-determined useful disparity range. For the second pass, hardware rules are presented that produce the correct disparity per pixel, by backtracking stored cost values. Hardware stages are structured along a fully parallel pipeline, that outputs disparities in step with the input serial pixel stream at clock rate.