Generalization of the Fast Hough Transform for Three-Dimensional Images

Abstract

This study is devoted to the analysis of algorithms of calculating the fast Hough transform for two- and three-dimensional images. A method for calculating the fast Hough transform (FHT) for straight lines in a three-dimensional image is proposed; its space and time complexity are Θ(n⁴), where n is the characteristic linear size of the input image. The FHT algorithms for approximation in two- and three-dimensional spaces are considered, and properties of the accuracy and completeness of the corresponding sets of dyadic patterns are investigated.