New parallel Hough transform for circles

Indexing terms Image processing, Picture processing and pattern recognition Abstract: The Hough transform is a well known medium-level image recognition technique for the detection of curves. The conventional Hough tech-nique [I, 21 requires a three-dimensional accumu-lator array (AA) for the detection of circles. Because shape parameterisation and data struc-ture of the accumulator array significantly affect the memory space and computation loading requirements of any hardware or software realisa-tion, they should be carefully selected for any fast and efficient algorithm. A new scheme which uses only a pair of two-dimensional accumulator arrays to reduce the storage and computation time by an order of magnitude or more is pro-posed. This new scheme is capable of discrimin-ating multiple (including concentric) circles in a complex real life image with a recognition rate of 95-100%. Various parallel realisations of this Hough scheme for circles on a general purpose MIMD (a reconfigurable transputer network) machine are discussed and a comparison of their performances with the conventional approach on the basis of execution time and recognition rate is presented.