Exploiting Inherent Parallelisms for Accelerating Linear Hough Transform

Abstract—Accelerating Hough transform in hardware has been of interest due its popularity in real-time capable image processing applications. In most existing linear Hough transform architec-tures, an edge map is serially read for processing, re-sulting in a total computation time of at least cycles. In this paper, we propose a novel parallel Hough transform computation method called the Additive Hough transform (AHT), wherein the image is divided using a grid to reduce the total computa-tion time by a factor of . We have also proposed an efficient im-plementation of the AHT consisting of a look-up table (LUT) and two-operand adder arrays for every angle. Techniques to condense the LUT size have also been proposed to further reduce area uti-lization by as much as 50%. Our investigations based on employing an 8 8 grid shows a 1000 speedup compared to existing archi-tectures for a range of image sizes. Area-time trade-off analysis has been presented to demonstrate that the area-time product of the proposed AHT-based implementation is at least 43 % lower than other implementations reported in the literature. We have also in-cluded and characterized a hierarchical addition step in order to generate a global accumulation space equivalent to that of the con-ventional HT. It is shown that the proposed implementation with the hierarchical addition step remains superior to other methods in terms of both performance and area-time product metrics. Fi-nally, we show that the proposed solution is equally efficient when applied on rectangular images. I