An optimal time multiplication free algorithm for edge detection on a mesh

This paper demonstrates an optimal time, fully systolic algorithm for edge detection on a mesh connected processor array. It uses only inexpensive addition and comparison operations which makes it ideal for fine grained parallelism in VLSI. Given an N × N image in the form of a two-dimensional array of pixels, our algorithm computes the Sobel and Laplacian operators for skimming lines in the image and then generates the Hough array using thresholding. The Hough transforms for M different angles of projection are obtained in a fully systolic manner in O(M + N) time, which is asymptotically optimal. In comparison, a previously published multiplication free algorithm has a time complexity of O(NM). An implementation of our algorithm on a mesh connected fine-grained processor array is discussed, which computes at the rate of approximately 170,000 Hough transforms per second using a 50 MHz clock.