Block decomposition and segmentation for fast Hough transform evaluation

The decomposition of binary images using rectangular blocks of foreground p ixels as primitives is considered. Based on this type of decomposition, a f ast method for evaluating the Hough transform is introduced. A complexity a nalysis of the proposed block Hough transform algorithm sets constraints on the complexity of algorithms used for block decomposition, so that the tot al decomposition and Hough transform application time is much less than the time consumed by the usual point Hough transform. Using this analysis, we propose two algorithms for the decomposition and segmentation of binary ima ges into rectangular blocks. A combination of these methods leads to signif icant acceleration in the identification of linear features, which is demon strated in various image processing experiments. (C) 1999 Pattern Recogniti on Society. Published by Elsevier Science Ltd. All rights reserved.