New memory- and computation-efficient hough transform for detecting lines

PATTERN RECOGNITION

卷:37

Article

Chung, KL ; Chen, TC ; Yan, WM

关键词: affine transformation;    algorithms;    complexity;    hough transform;    line-detection;    parameter space;    slope-intercept space;   

DOI  :  10.1016/j.patcog.2003.09.008

来源: Elsevier

【 摘 要 】

The slope-intercept Hough transform (SIHT) is one of the two types of line-detection methods. However, the disadvantage of the SIHT is its low memory utilization, say 50%. Based on the affine transformation, this paper presents a new method to improve the memory utilization of the SIHT from 50% to 100%. According to the proposed affine transformation, we first present a basic SIHT-based algorithm for detecting lines. Instead of concerning floating-point operations in the basic SIHT-based algorithm, an improved SIHT-based algorithm, which mainly concerns integer operations, is presented. Besides the memory utilization advantage, experimental results reveal that the improved SIHT-based algorithm has more than 60% execution time improvement ratio when compared to the basic SIHT-based algorithm and has more than 33% execution time improvement ratio when compared to another type of line-detection methods, such as the (r, theta)-based FIT algorithm and its variant. The detailed complexity analyses for all the related algorithms are also investigated and we show that the time complexity required in the improved SIHT-based algorithm is the least. (C) 2003 Pattern Recognition Society. Published by Elsevier Ltd. All rights reserved.

【 授权许可】

Free