Faster line detection algorithms on enhanced mesh connected arrays
Yi Feng Pan, Henry Y. H. Chuang · IEE Proceedings E Computers and Digital Techniques · 1993
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½+n) time on a 2D (2 dimensional) mesh, where n is the number of θ values considered. The second algorithm runs in O((N/n)½+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(nlog 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.