An efficient parallel processing algorithm for detecting straight lines on a mesh-connected computer enhanced with a gate-connection network (GCN) is presented. The algorithm is composed of a modified Hough transform that projects compressed pixels in parallel in a given direction and a parallel procedure that extracts the beginning and end points of detected lines. Both parts require the flexible communication capabilities of the enhance mesh. The GCN can be used to dynamically reconfigure the interconnections between hundreds of processors. It is shown how the GCN can electrically connect all of the edge pixels on a straight line. For an n*n pixel array, the algorithm can detect all lines in O(log n) time. Initial experimental results obtained using a simulator of the GCN implemented on a very-large-scale integration (VLSI) chip are presented. Though the accuracy of the algorithm depends largely on the assigned threshold values, the authors believe its speed is superior to that of any other Hough-based technique by a factor of at least two orders of magnitude.
展开▼
