Votes merging and ranking in a systolic queue

The authors discuss a systolic structure that stores, accumulates and sorts the contributions from a voting process (e.g., generalized Hough transform). This linear queue can be used reliably in a M-dimensional voting process, where the quantization of each dimension into Q bins yields a space complexity O(Q/sup M/). A N-stage queue uses 3 Mlog(Q) memory bits at each stage and is capable of accumulating online the incoming votes. The flow of data within the queue is designed to minimize the probability that new votes are lost because of overflow. The authors 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, it is shown that the conditions for the arrival times of a couple of coincident addresses to be detected and merged. The characterization of the behavior in time of the queue supports the experimental evidence that such a structure performs the accumulating process very reliably, even with a very small number of stages. 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.