A survey of efficient Hough transform methods <s> Task specific principles. <s> We describe an efficient procedure for detecting approximate circles and approximately circular arcs of varying gray levels in an edge-enhanced digitized picture. This procedure is an extension and improvement of the circle-finding concept sketched by Duda and Hart [2] as an extension of the Hough straight-line finder [6]. <s> BIB001 </s> A survey of efficient Hough transform methods <s> Task specific principles. <s> An important problem in vision is to detect the presence of a known rigid 3-D object. The general 3-D object recognition task can be thought of as building a description of the object that must have at least two parts: 1) the internal description of the object itself (with respect to an object-centered frame); and 2) the transformation of the object-centered frame to the viewer-centered (image) frame. The reason for this decomposition is parsimony: different views of the object should have minimal impact on its description. This is achieved by factoring the object's description into two sets of parameters, one which is view-independent (the object-centered component) and one which is view-varying (the viewing transformation). Often a description of the object is known beforehand and the task reduces to finding the objectframe to viewer-frame transformation. This paper describes a method for handling this case: a known object is detected by finding changes in orientation, translation, and scale of the object from its canonical description. The method is a Hough technique and has the characteristic insensitivity to occlusion and noise. <s> BIB002 </s> A survey of efficient Hough transform methods <s> Task specific principles. <s> Considering the Hough transformation as a linear imaging process recasts certain well-known problems, provides a useful vocab-ulary, and possibly indicates a source of applicable literature on the behavior of the Hough transformation in various forms of noise. A consideration of the analytic form of peaks in parameter space sets the stage for the idea of using complementary (negative) votes to cancel off-peak positive votes in parameter space, thus sharpening peaks and reducing bias. <s> BIB003 </s> A survey of efficient Hough transform methods <s> Task specific principles. <s> This paper describes a two-stage Hough procedure for two-dimensional object recognition based on matching local properties of a model set of contour points. The procedure makes use of three strategies: subdivision of the parameter space, classification by multiple properties, and non-maximum suppression. The first stage estimates likely values in a coarsely quantized space of position and orientation. The second stage verifies these estimates in a more precise space with a large set of model points. In both cases, matching of model points to image contour points is based on tangent, curvature and contrast. The evaluation of the parameter space is greatly simplified by simultaneous non-maximum suppression over neighborhoods of both parameters. Experiments show that these strategies are both efficient and robust, even in the case of complex and partial data. One example uses overlapping parts, such as might occur in industrial situations. <s> BIB004 </s> A survey of efficient Hough transform methods <s> Task specific principles. <s> Exact predictions of the performances of the Hough detection of straight lines in two-dimensional images are presented for rectangular and circular retinas, in Cartesian and normal parameterization, in the case of noisy signals. Detection of circles, under the same assumptions, is discussed. The limits of adaptive quantization to reduce intrinsic noise are presented, and it is shown that a signal processing approach is especially convenient to measure the performances of a detector based on the Hough transform. <s> BIB005 </s> A survey of efficient Hough transform methods <s> Task specific principles. <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> BIB006 </s> A survey of efficient Hough transform methods <s> Task specific principles. <s> Abstract A new technique using the straight-line Hough transform is advanced for locating curved objects or target tracks in a 2-D image. Generalized Hough transforms to achieve this are computationally expensive. Our proposed technique involves thresholding the Hough space and performing transformations and an inverse Hough transform. Peaks in this final inverse space provide curved object identification and determination of the parameters of each curved object. A theoretical development and initial simulation results are provided. <s> BIB007
In the standard implementation of the HT storage increases exponentially as the number of parameters, q, increases or the parameter resolution, (oc a) increases. This curse of dimensionality also applies to the amount of computation required, as the parameter hypersurface which each image point generates is usually a (q-1) dimensional hypersurface. The most obvious way to improve efficiency is therefore to ensure that both q and a remain as small as practicable. An obvious strategy is to restrict the range of parameters which are to be found by using apriori knowledge of the specific problem to be solved. A smaller parameter range can be covered to a specified high resolution using fewer accumulator cells i.e. a smaller value of a. For example in many problems which involve circle finding there may be limits on the likely radius of circles or the centre of the circle may be constrained to lie within the interior of the image. In a limiting case it may be known that circles are of a single known radius and in that case the 3 parameter circle finding problem collapses to a 2 parameter problem of finding circle centres. Alternatively the shape may be known to have certain rotational symmetries and these can be exploited to reduce the number of intervals needed to determine orientation. Davies  has considered regular polygonal shapes and concludes that the orientation axis need only be divided into a number of intervals which is equal to the number of polygon sides. A less obvious way of improving the computational efficiency of the HT is to use extra information to restrict the mapping of image to parameter values from a "one to many" mapping to a "one to few" mapping i.e. use extra data to constrain the dimensionality or range of the hypersurface that an image point generates. Edge direction information BIB001 is the most commonly used piece of extra information although curvature and gray level constraints have also been used in this way BIB004  . For example in the case of straight line detection the edge direction is directly related to the line gradient and therefore line finding can be reduced to a 1 parameter histogramming task to find the best intercept value. In the case of circle finding edge angle information restricts each image point mapping to a single line of parameter values on the surface of a cone. The idea of using edge information has been used most notably in Ballards  efficient HT for general shapes. This relies for its efficiency on the indexing of possible localisation point vectors by values of edge direction. Candidate shape points are then only matched to template points which possess the same value of edge direction. A sophisticated use of prior information involves decomposition of high dimensional problems into a series of lower dimensional problems. One of the simplest examples of this type is the use of edge direction information, 8, as a constraint in circle finding. All the edge vectors on a circle must project to a common intersection at the centre of the circle. In BIB006 it is shown how this can be used to define a 2 stage HT. Edge vectors can be estimated using standard operators such as the Sobel operator. The first stage of the modified HT involves mapping image features described by [x\,X2,8) into a 2 parameter space (pi,P2) of circle centres. Peaks identified in the 2 parameter space yield candidate (pi,P2) values which are then used with image point coordinates in a second stage to calculate a histogram of possible P3 or radius values. This radius histogram can be viewed as a trivial 1 parameter HT which maps 4 tuples of (xi,X2,pi,P2) into p3 values. The maximum dimensionality of any of the substages is only 2 and the overall efficiency of the modified HT is dominated by the demands of this stage. The penalty paid for this increased efficiency is the cost of calculating, and the reliance on, good edge information. Edge detection is a computationally intensive task but in most cases this will not outweigh the benefit gained from its use in the two stage HT. Indeed there are many situations where edge information may have to be computed for purposes other than the HT and in these cases no extra computation is incurred. However decomposing the HT into a multistage process may introduce systematic errors as inaccuracies in parameters determined at an early stage propagate into later stages. Tsukune and Goto  have shown that similar edge based constraints can be derived and used to decompose the 5 parameter ellipse finding problem into a 3 stage problem involving determination of at most two parameters at any single step. Ballard and Sabbath BIB002 have shown that parameter decomposition can be a powerful technique in the matching of 2D views to 3D models. Descriptions of 3D objects are usually stored as object centred representations and recognition involves determining the parameters of a transformation which maps a 2D view into these 3D descriptions. The viewing transformation generally involves 7 parameters which cater for changes in scale (l parameter), orientation (3 parameters) and translation (3 parameters). However for orthographic projection there is a natural ordering or dominance of parameters such that they can be sequentially determined in subgroups i.e. scale can be determined without knowledge of orientation or translation and orienation can be found without knowing the value of translation parameters. Ballard and Sabbah give specific algorithms for the case where objects are described by oriented edges and planar surface patches. The maximum dimensionality of any subproblem is only 3. A further possibility for parameter reduction is to consider how any shape maps into a low dimensional space such as that used in line finding. Several authors  BIB003 BIB005   have shown that the distribution of votes in this parameter space has a characteristic shape. Finite length lines produce a butterfly shaped peak of counts rather than a symmetric peak. Leavers and Boyce  have designed filters to enhance this feature in order to increase the reliability of line detection. They have also considered the mapping of circles  into this parameter space. Circles produce a band of votes with a characteristic falloff at the band edges. The edges of the band can be enhanced by a filter and parameters of the circle can be estimated from their positions. Casasent and Krishnapuram BIB007 use the same idea of mapping any shape into a two parameter space but they suggest manipulating the resulting HT parameter space so that upon applying the inverse HT the votes from a shape map to a compact peak. They indicate a general technique for deriving the manipulations which must be performed in parameter space. The position of the peak in the inverse transform space indicates the translation parameters associated with the shape.