A survey of efficient Hough transform methods <s> Efficient accumulation methods <s> Abstract : A method for extracting the motion parameters of several independently moving objects from displacments field information is described. The method is based on a generalized Hough transform technique. Some of the problems of this technique are addressed and appropriate solutions are proposed. A modified multipass Hough transform appraoch has been implemented, where i each pass windows are lkocated around objects and the transform is applied only to the displacement vectors contained in these windows. The windows are determined by the degree to which the displacement field is locally inconsistent with previously found motion transformations. Thus, the sensitivity of the Hough transform to local events is increased and the motion parameters of small objects can be detected even in a noisy displacement field. The author also use a multi-resolution scheme in both the image plane and the parameter space and thus reduce the computational cost of the technique. The method is demonstrated by experiments based on artifical images with four parameters of 2-d motion: rotation, expansion and tranlation in both axes. <s> BIB001 </s> A survey of efficient Hough transform methods <s> Efficient accumulation methods <s> Abstract : In the Hough transform, a feature in an input space I votes for parameters in a transform space P with which it is compatible. It it also uses negative votes to vote against parameters with which it is incompatible, background bias and inherent noise in P can be reduced and peaks sharpened. In the usual Hough transform implementation, an array is used to accumulate votes, raising the problem that the space requirement increases exponentially with the number of parameters. Accumulation in a fixed-size content-addressable cache(or hash table) may provide a solution. (Author) <s> BIB002 </s> A survey of efficient Hough transform methods <s> Efficient accumulation methods <s> Two new data structures are defined for use in multidimensional histogramming. Their purpose is to cover a parameter space with a limited number of histogram bins so that fine precision is maintained where it is needed. The original motivation for these data structures was to implement Hough-like transforms in high-dimensional parameter spaces. The two data structures share the ability to adapt to distributions that change with time. <s> BIB003 </s> A survey of efficient Hough transform methods <s> Efficient accumulation methods <s> Abstract We have developed a fast algorithm for the Hough transform that can be incorporated into the solutions to many problems in computer vision such as line detection, plane detection, segmentation, and motion estimation. The fast Hough transform (FHT) algorithm assumes that image space features “vote” for sets of points lying on hyperplanes in the parameter space. It recursively divides the parameter space into hypercubes from low to high resolution and performs the Hough transform only on the hypercubes with votes exceeding a selected threshold. The decision on whether a hypercube receives a vote from a hyperplane depends on whether the hyperplane intersects the hypercube. This hierarchical approach leads to a significant reduction of both computation and storage. Due to the hyperplane formulation of the problem and the hierarchical representation of the hypercube, the computation in the FHT is incremental and does not require multiplication, which further contributes to efficiency. <s> BIB004 </s> A survey of efficient Hough transform methods <s> Efficient accumulation methods <s> We introduce the Adaptive Hough Transform, AHT, as an efficient way of implementing the Hough Transform, HT, method for the detection of 2-D shapes. The AHT uses a small accumulator array and the idea of a flexible iterative "coarse to fine" accumulation and search strategy to identify significant peaks in the Hough parameter spaces. The method is substantially superior to the standard HT implementation in both storage and computational requirements. In this correspondence we illustrate the ideas of the AHT by tackling the problem of identifying linear and circular segments in images by searching for clusters of evidence in 2-D parameter spaces. We show that the method is robust to the addition of extraneous noise and can be used to analyze complex images containing more than one shape. <s> BIB005 </s> A survey of efficient Hough transform methods <s> Efficient accumulation methods <s> A computationally efficient implementation of the Hough transform, called the Adaptive Hough Transform is described. The method uses a coarse to fine search strategy to find peaks in the parameter space using a small accumulator array of fixed size. Its storage requirements are dramatically lower than those for the conventional Hough transform and it is also faster computationally when high dimensional parameter spaces are used. Shape detection using both natural representations of curves and hyperplane representations is discussed and the effectiveness of the method is demonstrated experimentally by applying it to the detection of parametric shapes in images of industrial objects. <s> BIB006
In this section we consider several methods which utilise novel data structures or use techniques that employ nonuniform or multiple resolutions in order to achieve storage and computation savings. Many schemes are based on the observation that it is necessary to have high accumulator resolution only in places where a high density of votes accumulate. O'Rourke and Sloan   BIB003 were among the first to use this principle. They developed two data structures. The first structure, Dynamically Quantised Spaces (DQS)  BIB003 , consists of a binary tree in which each node encloses a rectangular region of space. As data is accumulated rules are used to split and merge cells so that each cell contains, irrespective of its size, approximately the same number of counts evenly distributed throughout its volume. The total number of cells in the tree is an input parameter of the method but in the final tree there will be a concentration of small cells around peaks and this allows peaks to be located more accurately than using the same number of cells in a standard uniform quantisation schemes. The second data structure, Dynamically Quantised Pyramids (DQP)  BIB003 , is based on a multiresolution multidimensional quadtree in which the number and connectivity of cells is small and fixed. A disadvantage of the quadtree structure is that its boundaries, and hence its spatial resolutions, are fixed. This limitation is overcome in the DQP data structure using a dynamic technique, called hierarchical warping, to modify the boundaries of cells by tracking the mean position of data points in their regions of space. The net effect of the boundary adjustment is to produce cells containing approximately equal numbers of votes. However the warping process introduces some errors in the final accumulator totals and means that the final division of space depends on the order in which the data is accumulated i.e. recently accumulated points are most influential on the final result. O'Rourke and Sloan use both data structures in a series of experiments where a 3 parameter space is divided into about 64 cells. They demonstrate the relative abilities of each algorithm to focus on peaks, to dynamically change attention and to detect multiple peaks. Their general conclusion is that DQSs are difficult to implement but perform somewhat better than DQPs. A useful idea suggested by several authors is the iterative focusing of the HT to identify peaks with high counts. Initially the HT can be accumulated in a coarse but uniform resolution parameter space. Regions or cells with high counts at this resolution can then be investigated at higher resolution. Only a few iterations of this procedure can lead to very high parameter resolution. Consider searching for a peak in a q dimensional space resolved into a accumulator bins. The iterative use of a much smaller accumulator of size /5 requires Q(io (fl ) derations to focus down to the same resolution. The computational saving of the method is proportional to the ratio of the number of cells in the two accumulators i.e. f %) times the ratio of iterations i.e. O((|)' * gj{Q). This can be very large. This strategy provides enormous efficiency benefits in terms of both amount of computation and amount of storage space required. It has been used by Adiv BIB001 as an efficient way to search for motion parameters in high dimensional spaces and by Silberberg  to identify the viewing parameters relating stored models to observed shapes. Recently Li et al  BIB004 have detailed a focusing algorithm, the Fast Hough Transform, FHT, which uses a multidimensional quadtree in conjunction with HTs which map image points into hyperplanes. This use of hyperplanes is advantageous as the approximate intersection between planes and parameter cells can be efficiently computed using incremental tests which depend on the known spatial relationship between a quadrant and its four sons. Only additions and shifts are required to implement the test and the computational cost scales only linearly with the dimensionality of the parameter space. Computational gains of O (10 3 ) for 2D lines and O (10 6 ) for 3D plane detection can be achieved. The algorithm is regular in structure and is therefore easily extended to higher dimensional spaces and easily implemented in VLSI hardware. However the FHT currently identifies areas for focusing by requiring that quadrants have a vote count which exceeds a fixed threshold. In complex images this threshold may be difficult to determine and if it is set too low the efficiency of the method will deteriorate as the algorithm will explore too many quadrants. Another problem is related to the incremental intersection testing method. This requires that each quadrant must store the distance of every image feature from its centre. If there are many image features this can represent a large overhead. It is also not clear that all shapes can be naturally mapped into hyperplanes. Finally the quadtree data structure is a static structure and cannot optimally adapt to situations which may require different parameter resolutions along different parameter axes. Li et al  have recognised the last problem and have suggested using a data structure, called the bintree, in which space is partitioned into rectangular regions. Illingworth and Kittler BIB005 BIB006 have developed an iterative coarse to fine search strategy for detecting lines and circles in 2D and 3D parameter spaces. Their implementation is called the Adaptive Hough Transform, AHT. It uses a small accumulator array (typical /? = 9) which is thresholded and then analysed by a connected components algorithm. The shape and extent of connected components determine the new parameter limits which are used in the next iteration. Limits can be decreased, expanded, rotated or merely translated depending on the distribution of counts in the accumulator. Parameter limits are defined independently for each parameter dimension and therefore the method selects appropriate precision for each parameter. The method works well for single object recognition and we are currently investigating strategies for using it to detect multiple objects. The storage gain using the AHT is of the order expected for focusing methods, i.e. ( j J , while experiments with searching for circles in a 3 parameter space demonstrated that it was several hundred times times faster than a standard method. Brown  BIB002 attempted to overcome the storage problems associated with the standard HT by replacing the accumulator array by a small fixed size content addressable store i.e. a hash table in software or a cache if implemented in hardware. Counts are accumulated in the store until it is full and then a flushing or garbage collection method is invoked to release some storage for further use. The simplest flushing strategy is to remove entries with fewest votes. However it is possible to devise schemes which will favour the keeping of recent information or which will incorporate geometric locality information. Brown studied caches of size 32, 64 and 128 and compared their performance againt standard accumulators as he varied flushing strategy and the order of accumulation of the data. He concluded that finite length caches were as practical as accumulators and he was able to predict qualitatively the degradation of their performance as noise increased and cache length decreased.