Linear generalized Hough transform and its parallelization

摘要

The Generalized Hough Transform (GHT) proposed by Ballard1 is an effective method for recognizing objects of arbitrary shape. It converts a problem of global pattern matching into local peak searching. However, the GHT has difficulty in handling occluded objects. It also suffers from the congestion at the single peak point when attempting its potential parallelization. In this paper, we present a Linear Generalized Hough Transform (LIGHT) in which a linear numeric pattern is used to replace the single peak in the GHT. The LIGHT is more capable of detecting partially occluded objects. Moreover, it is well-suited for parallelization, especially on SIMD array processors. Several sequential and parallel LIGHT algorithms and our preliminary results are presented. The impact of noise on the effectiveness of the LIGHT algorithm is studied. The result for parallel implementation is obtained from an SIMD onedimensional array processor (the AIS-4000 Vision Processor with 512 processing elements). A speed-up factor of two orders of magnitude is achieved.