Faster line detection algorithms on enhanced mesh connected arrays

The problem of detecting lines in an image with N edge pixels on mesh connected computers with N processors is considered, and four new and efficient algorithms which detect lines by performing a Hough transform are presented. The first algorithm runs in O(N¹2/+n) time on a 2D (2 dimensional) mesh, where n is the number of theta values considered. The second algorithm runs in O((N/n)¹2/+n) time on a 3D mesh. The third algorithm runs in O(log (N/n)+n) time on a mesh plus tree, and the fourth algorithm runs in O(n log N/log n) time on a mesh with reconfigurable buses. All of the algorithms presented in the paper have smaller time complexities than the known results in the literature.