Algorithmic considerations on the computational complexities of digital line extraction problem
Tetsuo Asano, Yasuyuki Kawamura · Systems and Computers in Japan · 2000
The Hough transform is a well-established scheme in computer vision for detecting digital line components in a binary edge image. It seems to be popular mainly because its basic idea of voting in a parameter space is easy to understand. In this paper we discuss the lower bound of the computational complexity of the voting-based method under the condition that all possible digital line components contained in a given image must be detected. Finally, a completely different method based on algorithmic techniques developed in computational geometry is proposed and we prove its advantage in both computation time, and working storage. © 2000 Scripta Technica, Syst Comp Jpn, 31(14): 29–37, 2000