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

Manjit Borah, Chetana Nagendra, Mohan Vishwanath, Robert M. Owens, Mary Jane Irwin

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)67-75
Number of pages9
JournalJournal of VLSI Signal Processing Systems for Signal, Image, and Video Technology
Issue number1
StatePublished - 1996

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Information Systems
  • Electrical and Electronic Engineering


Dive into the research topics of 'An optimal time multiplication free algorithm for edge detection on a mesh'. Together they form a unique fingerprint.

Cite this