Mapping the generalized Hough transform on a mesh connected computer
Marco Ferretti · 2002
The computational complexity of the generalized Hough transform (GHT) on a mesh-connected computer (MCC) is analyzed, and a practical algorithm is given for bidimensional shape recognition which is useful in any real situation, not just in the asymptotic case. The problem of shape detection is introduced, along with a description of the generalized Hough transform. Mapping such a transform onto a massively parallel computer that consists of a mesh of four connected processing elements is shown. The mapping uses formally defined, general-purpose data movement techniques that have been introduced for other kinds of problems on such architectures. Using these results, it is shown that the time complexity of the GHT is O(Rn log n), where R is the number of points used to describe the shape and n is the linear dimension of the MCC.>