Hough Transform on Reconfigurable Meshes

摘要

The Hough transform is an important image processing operation. Given an N × N digital image, we first present a parallel algorithm for computing the Hough transform in O((p/k) log N) time on a reconfigurable mesh of O(kN2) processors, 1 ≤ k ≤ p, where p is the number of angles to be considered. Then, on a 3-dimensional reconfigurable mesh using O (kN3) processors, the Hough transform can be computed in O(p/k) time. When setting k = O(p), a constant time algorithm is derived. Furthermore, a more general result is presented; the Hough transform can be computed in O((p log N )/(k log M)) time on a reconfigurable mesh of O (kN2M) processors, where 2 ≤ M ≤ N .