FAST AND HIGH-ACCURACY HOUGH TRANSFORM WITH COMPUTATIONAL COMPLEXITY Θ( log) FOR PROCESSING RECTANGULAR-SHAPED IMAGES OF ARBITRARY SIZES

The Hough transform (HT) is a key tool in digital image processing, used in a wide range of scientific tasks, from document recognition to computed tomography. Algorithmic implementations of HT are traditionally evaluated based on two parameters: computational complexity and accuracy, which is defined as the error of approximating continuous lines with discrete ones formed during the execution of the algorithm. Fast HT algorithms (FHT) with optimal linear-logarithmic computational complexity are well studied; an example is the classic Brady-Yong algorithm, which is applicable exclusively to images with linear dimensions equal to powers of two. Its generalizations, such as the algorithm, allow rectangular images of arbitrary size to be processed, but the accuracy of the HT implemented by them is low, and it decreases as the size of the processed image increases. There are also HT algorithms that maintain a constant upper bound of the approximation error for images of any size. They provide higher accuracy, but their computational complexity approaches near-cubic, which makes them unsuitable for processing large images. This paper proposes the algorithm, which combines near-optimal speed with high accuracy. The algorithm has computational complexity of Θ( log ) when processing images of size × . At the same time, the proposed algorithm guarantees an orthotropic approximation error of continuous lines no greater than λ + 1/2 regardless of the image size, tunable by the control meta-parameter λ ∈ (0; 1]. The paper presents a summary table of experimental results, which can serve as a practical guide for selecting the value of the meta-parameter λ in order to balance accuracy and computational complexity.