SYSTOLIC MERGING AND RANKING OF VOTES FOR THE GENERALIZED HOUGH TRANSFORM
Maria Grazia Albanesi, Marco Ferretti · International Journal of Pattern Recognition and Artificial Intelligence · 1995
In this paper we present and analyze a systolic structure to support the Generalized Hough Transform. Among the structural methods for object recognition, this transform is well established for its flexibility and noise immunity. Its use in actual systems has been however limited by the computational cost associated with the management of votes. Previous work has shown that a limited amount of memory can substitute the large address space required for building the histogram of votes. The systolic queue here introduced substitutes the address space required in a M- dimensional voting process, where the quantization of each dimension into Q bins yields a space complexity O(QM). An N-stage queue uses 3 M log(Q) memory bits at each stage and is capable of accumulating the incoming votes on the fly. The flow of data within the queue is designed to minimize the probability that new votes are lost because of overflow. We derive analytic expressions for the growth of the queue during the set-up period and for the time each new vote spends within the queue if it is not accumulated; furthermore, we show the conditions for the arrival times of a couple of coincident addresses to be detected and merged. The analysis of the time behaviour of the queue supports the experimental evidence that such a structure performs the accumulating process very reliably. A VLSI integrated circuit embedding a 50-stage queue is the third in a chip-set for the real time implementation of the Generalized Hough Transform.