Optimal computing hough transform on a reconfigurable array of processors with wider bus networks

摘要

The parallel computation model on which our algorithms are based is the reconfigurable array of processors with wider bus networks. Conventionally, only one bus is connected between two processors, but in this machine it has a set of buses. Such a characteristic makes the computation power of this machine enormous. Based on the base-m number system, we first derive a constant time algorithm to compute the prefix sum for the bit one of a binary sequence of size N using N processors. Then two applications, such as the histogram of an n × n image and the Hough transform of N edge pixels with n × n parameter space are also solved in constant time using n × n and n × (N + 1) processors respectively. Both results are shown to be optimal.