A pipelined architecture for parallel image relaxation operations

Abstract

Discrete relaxation techniques have proven useful in solving a wide range of problems in digital image processing, computer vision, and robot vision. A conventional hardware design for an 8-object, 8-label Discrete Relaxation Algorithm (DRA) requires three 4K memory blocks and maximum execution time of over an hour, which makes such a DRA hardware implementation infeasible. By reformulating the Discrete Relaxation Algorithm into a parallel computational tree, a pipelined Single Instruction stream Multiple Data stream (SIMD) architecture for a highly concurrent computation of an 8-object, 8-label DRA problem has been developed. We give a second implementation which eliminates the excessive memory requirements and performs the DRA computation in microseconds, at the worst case in milliseconds. The chip is fabricated using a 3- <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">{\mu}m</tex> NMOS technology by MOSIS. The major design issues are described in this paper.