Parallel algorithms for line detection on a 1×N array processor

A description is given of two algorithms that compute the Hough transform for straight lines on N×N images using 1×N processing arrays. The algorithms are developed for 1×N array processors and have been implemented on the AIS-5000 parallel vision computer. The complexity of both algorithms is O(N²+PN) on the 1×N array processor (P is the number of angles polled which determines the θ-resolution of the Hough space), which compares well with the known optimal O(N+P) algorithms for N×N mesh arrays