An O(1) time algorithms for computing histogram and Hough transform on a cross-bridge reconfigurable array of processors

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 _mN]+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×n image with G gray-level value in constant time using G×n×n processors, and compute the Hough transform of an image with N edge pixels and n×n parameter space in constant time using n×n×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