An O(1) time algorithms for computing histogram and Hough transform on a cross-bridge reconfigurable array of processors
Tzong‐Wann Kao, Shi‐Jinn Horng, Y.-L. Wang · IEEE Transactions on Systems Man and Cybernetics · 1995
In this paper, instead of using the base-2 number system, we use a base-m number system to represent the numbers used in the proposed algorithms. Such a strategy can be used to design an O(T) time, T=[log/sub m/N]+1, prefix sum algorithm for a binary sequence with N-bit on a cross-bridge reconfigurable array of processors using N processors, where the data bus is m-bit wide. Then, this basic operation can be used to compute the histogram of an n/spl times/n image with G gray-level value in constant time using G/spl times/n/spl times/n processors, and compute the Hough transform of an image with N edge pixels and n/spl times/n parameter space in constant time using n/spl times/n/spl times/N processors, respectively. This result is better than the previously known results. Also, the execution time of the proposed algorithms is tunable by the bus bandwidth.>