Improved mesh algorithms for straight line detection

The problem of detecting lines in an image with N edge pixels on mesh-connected computers with N processors is considered. Four efficient algorithms that detect lines by performing a Hough transform are presented. The first algorithm runs in O( N^1/2+n) time on a 2-D mesh, where n is the number of θ values considered. The second algorithm runs in O((N/n)^1/2+n ) time on a 3-D mesh. The third algorithm runs in O(log( N/n)+n) time on an augmented mesh. The fourth algorithm runs in O(n log N/log n) time on a mesh with a reconfigurable bus. All of the algorithms have smaller time complexities than algorithms in the literature