Real-time CAM-based Hough transform algorithm and its performance evaluation

Abstract. This paper proposes a highly parallel Hough transform algorithm for real-time straight-line extraction and its hardware implementation on a content-addressable memory (CAM). To achieve high-speed processing, incrementation for voting, which composes the Hough transform, and calculations for coordinate updating are carried out for the every scan line, not every edge pixel, and extracting maxima in Hough space is executed by parallel comparing. Moreover, variously weighted voting achieves more accurate line extraction in spite of the quantization error and noise in the image space. In the implementation, the CAM acts as a PE (processing-element) array that effectively performs highly parallel processing for the Hough transform and also as a memory for two-dimensional Hough space, and both voting and peak extraction are directly executed by the CAM. Evaluations of CAM hardware size, processing time and the accuracy of line extraction show that a real-time and high-resolution Hough transform for a 256256 picture can be achieved using a single CAM chip with current VLSI technology. This CAM-based Hough transform algorithm promises to be an important step towards the realization of a real-time and compact image-understanding system. Received: 15 August 1998 / Accepted: 15 March 2000