Generalised Hough transform

<h2 id="history">History</h2>
Merlin and Farber<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> showed how to use a Hough algorithm when the desired curves could not be described analytically. It was a precursor to Ballard's algorithm that was restricted to <a href="/facts/Translation_(geometry)/KlpWmnfX">translation</a> and did not account for <a href="/facts/Rotation/yChkz49x">rotation</a> and <a href="/facts/Scale_(ratio)/1Q9xpvGM">scale</a> changes.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
The Merlin-Farber algorithm is impractical for real image data as in an image with many edge pixels, it finds many false positives due to repetitive pixel arrangements.

<h2 id="theory-of-generalized-hough-transform">Theory of generalized Hough transform</h2>
To generalize the Hough algorithm to non-analytic curves, Ballard defines the following parameters for a generalized shape: a={y,s,θ} where y is a reference <a href="/facts/Origin_(mathematics)/Lm26tRCB">origin</a> for the shape, θ is its orientation, and s = (sx, sy) describes two <a href="/facts/Orthogonality/JVIjYPog">orthogonal</a> scale factors. An algorithm can compute the best set of parameters for a given shape from edge pixel data. These parameters do not have equal status. The reference origin location, y, is described in terms of a template table called the R table of possible edge pixel orientations. The computation of the additional parameters s and θ is then accomplished by straightforward transformations to this table. The key generalization to arbitrary shapes is the use of directional information. Given any shape and a fixed reference point on it, instead of a parametric curve, the information provided by the boundary pixels is stored in the form of the R-table in the transform stage. For every edge point on the test image, the properties of the point are looked up on the R-table and reference point is retrieved and the appropriate cell in a matrix called the Accumulator matrix is incremented. The cell with maximum 'votes' in the Accumulator matrix can be a possible point of existence of fixed reference of the object in the test image.

<h3>Building the R-table</h3>
Choose a reference point y for the shape (typically chosen inside the shape). For each boundary point x, compute ɸ(x), the <a href="/facts/Gradient/TsR7uukj">gradient</a> direction and r = y – x as shown in the image. Store r as a function of ɸ. Notice that each index of ɸ may have many values of r. One can either store the co-ordinate differences between the fixed reference and the edge point ((xc – xij), (yc – yij)) or as the radial distance and the angle between them (rij, αij). Having done this for each point, the R-table will fully represent the template object. Also, since the generation phase is invertible, we may use it to localise object occurrences at other places in the image.

<table><tbody><tr><th>i</th><th>ɸi</th><th>Rɸi</th></tr><tr><td>1</td><td>0</td><td>(r11, α11) (r12, α12)... (r1n, α1n)</td></tr><tr><td>2</td><td>Δɸ</td><td>(r21, α21) (r22, α22)... (r2m, α2m)</td></tr><tr><td>3</td><td>2Δɸ</td><td>(r31, α31) (r32, α32)... (r3k, α3k)</td></tr><tr><td>...</td><td>...</td><td>...</td></tr></tbody></table>
<h3>Object localization</h3>
For each edge pixel x in the image, find the gradient ɸ and increment all the corresponding points x+r in the accumulator array A (initialized to a maximum size of the image) where r is a table entry indexed by ɸ, i.e., r(ɸ). These entry points give us each possible position for the reference point. Although some bogus points may be calculated, given that the object exists in the image, a maximum will occur at the reference point. Maxima in A correspond to possible instances of the shape.

<h3>Generalization of scale and orientation</h3>
For a fixed orientation of shape, the accumulator array was two-dimensional in the reference point co-ordinates. To search for shapes of arbitrary orientation θ and scale s, these two parameters are added to the shape description. The accumulator array now consists of four dimensions corresponding to the parameters (y, s, θ). The R-table can also be used to increment this larger dimensional space since different orientations and scales correspond to easily computed transformations of the table. Denote a particular R-table for a shape S by R(ɸ). Simple transformations to this table will allow it to detect scaled or rotated instances of the same shape. For example, if the shape is scaled by s and this transformation is denoted by Ts.
then
Ts[R(ɸ)] = sR(ɸ) i.e., all the vectors are scaled by s. 
Also, if the object is rotated by θ and this transformation is denoted by Tθ, then
Tθ[R(ɸ)] = Rot{R[(ɸ-θ)mod2π],θ}
i.e., all the indices are incremented by – θ modulo 2π, the appropriate vectors r are found, and then they are rotated by θ.
Another property which will be useful in describing the composition of generalized Hough transforms is the change of reference point. If we want to choose a new reference point ỹ such that y-ỹ = z then the modification to the R-table is given by R(ɸ)+ z, i.e. z is added to each vector in the table.

<h3>Alternate way using pairs of edges</h3>
A pair of edge pixels can be used to reduce the parameter space. Using the R-table and the properties as described above, each edge pixel defines a surface in the four-dimensional accumulator space of a = (y, s, θ). Two edge pixels at different orientations describe the same surface rotated by the same amount with respect to θ. If these two surfaces intersect, points where they intersect will correspond to possible parameters a for the shape. Thus it is theoretically possible to use the two points in image space to reduce the locus in parameter space to a single point. However, the difficulties of finding the intersection points of the two surfaces in parameter space will make this approach unfeasible for most cases.

<h3>Composite shapes</h3>
If the shape S has a composite structure consisting of subparts S1, S2, .. SN and the reference points for the shapes S, S1, S2, .. SN are y, y1, y2, .. yn, respectively, then for a scaling factor s and orientation θ, the generalized Hough transform Rs(ɸ) is given by 
 
 
 
 
 R
 
 ϕ
 
 
 =
 
 T
 
 s
 
 
 
 {
 
 
 T
 
 θ
 
 
 
 [
 
 
 ⋃
 
 k
 =
 1
 
 
 N
 
 
 
 R
 
 
 s
 
 k
 
 
 
 
 (
 ϕ
 )
 
 ]
 
 
 }
 
 
 
 {\displaystyle R_{\phi }=T_{s}\left\{T_{\theta }\left[\bigcup _{k=1}^{N}R_{s_{k}}(\phi )\right]\right\}}
 
. The concern with this transform is that the choice of reference can greatly affect the accuracy. To overcome this, Ballard has suggested smoothing the resultant accumulator with a composite smoothing template. The composite smoothing template H(y) is given as a composite <a href="/facts/Convolution/PVPrdz9J">convolution</a> of individual smoothing templates of the sub-shapes.

H
 (
 y
 )
 =
 
 ∑
 
 i
 =
 1
 
 
 N
 
 
 
 h
 
 i
 
 
 (
 y
 −
 
 y
 
 i
 
 
 )
 
 
 {\displaystyle H(y)=\sum _{i=1}^{N}h_{i}(y-y_{i})}
 
. Then the improved Accumulator is given by As = A*H and the maxima in As corresponds to possible instances of the shape.

<h3>Spatial decomposition</h3>
Observing that the global Hough transform can be obtained by the summation of local Hough transforms of disjoint sub-region, Heather and Yang<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> proposed a method which involves the <a href="/facts/Recursive_subdivision/GfIomenN">recursive subdivision</a> of the image into sub-images, each with their own parameter space, and organized in a <a href="/facts/Quadtree/6b23FQoD">quadtree</a> structure. It results in improved efficiency in finding endpoints of line segments and improved robustness and reliability in extracting lines in noisy situations, at a slightly increased cost of memory.

<h2 id="implementation">Implementation</h2>
The implementation uses the following equations:<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

x
        =
        
          x
          
            c
          
        
        +
        
          x
          ′
        
         
         
        o
        r
         
         
        
          x
          
            c
          
        
        =
        x
        −
        
          x
          ′
        
      
    
    {\displaystyle x=x_{c}+x'\ \ or\ \ x_{c}=x-x'}

y
        =
        
          y
          
            c
          
        
        +
        
          y
          ′
        
         
         
        o
        r
         
         
        
          y
          
            c
          
        
        =
        y
        −
        
          y
          ′
        
      
    
    {\displaystyle y=y_{c}+y'\ \ or\ \ y_{c}=y-y'}

cos
        ⁡
        (
        π
        −
        α
        )
        =
        
          x
          ′
        
        
          /
        
        r
         
         
        
          or
        
         
         
        
          x
          ′
        
        =
        r
        cos
        ⁡
        (
        π
        −
        α
        )
        =
        −
        r
        cos
        ⁡
        (
        α
        )
      
    
    {\displaystyle \cos(\pi -\alpha )=x'/r\ \ {\text{or}}\ \ x'=r\cos(\pi -\alpha )=-r\cos(\alpha )}

sin
        ⁡
        (
        π
        −
        α
        )
        =
        
          y
          ′
        
        
          /
        
        r
         
         
        
          or
        
         
         
        
          y
          ′
        
        =
        r
        sin
        ⁡
        (
        π
        −
        α
        )
        =
        r
        sin
        ⁡
        (
        α
        )
      
    
    {\displaystyle \sin(\pi -\alpha )=y'/r\ \ {\text{or}}\ \ y'=r\sin(\pi -\alpha )=r\sin(\alpha )}

Combining the above equations we have:

x
          
            c
          
        
        =
        x
        +
        r
        cos
        ⁡
        (
        α
        )
      
    
    {\displaystyle x_{c}=x+r\cos(\alpha )}

y
          
            c
          
        
        =
        y
        +
        r
        sin
        ⁡
        (
        α
        )
      
    
    {\displaystyle y_{c}=y+r\sin(\alpha )}

Constructing the R-table

(0) Convert the sample shape image into an edge image using any <a href="/facts/Edge_detection/9VplpIcS">edge detecting</a> algorithm like <a href="/facts/Canny_edge_detector/z4EExfNu">Canny edge detector</a>
(1) Pick a reference point (e.g., (xc, yc))
(2) Draw a line from the reference point to the boundary
(3) Compute ɸ
(4) Store the reference point (xc, yc) as a function of ɸ in R(ɸ) table.
Detection:

(0) Convert the sample shape image into an edge image using any edge detecting algorithm like <a href="/facts/Canny_edge_detector/z4EExfNu">Canny edge detector</a>.
(1) Initialize the Accumulator table: A[xcmin . . . xcmax][ycmin . . . ycmax]
(2) For each edge point (x, y)
(2.1) Using the gradient angle ɸ, retrieve from the R-table all the (α, r) values indexed under ɸ.
(2.2) For each (α,r), compute the candidate reference points:
xc = x + r cos(α)
yc = y + r sin(α)
(2.3) Increase counters (voting):
++A([[xc]][yc])
(3) Possible locations of the object contour are given by local maxima in A[xc][yc].
If A[xc][yc] > T, then the object contour is located at (xc, yc)
General case:
Suppose the object has undergone some rotation Θ and uniform scaling s:

(x′, y′) → (x″, y″)
x″ = (x′ cos(Θ) – y′ sin(Θ))s
y″ = (x′ sin(Θ) + y′ cos(Θ))s
Replacing x′ by x″ and y′ by y″: 
xc = x – x″ or xc = x - (x′ cos(Θ) – y′ sin(Θ))s
yc = y – y″ or yc = y - (x′ sin(Θ) + y′ cos(Θ))s
(1) Initialize the Accumulator table: A[xcmin . . . xcmax][ycmin . . . ycmax][qmin . . . qmax][smin . . . smax]
(2) For each edge point (x, y)
(2.1) Using its gradient angle ɸ, retrieve all the (α, r) values from the R-table
(2.2) For each (α, r), compute the candidate reference points:
x′ = r cos(α)
y′ = r sin(α)
for(Θ = Θmin; Θ ≤ Θmax; Θ++)
for(s = smin; s ≤ smax; s++)
xc = x - (x′ cos(Θ) – y′ sin(Θ))s
yc = y - (x′ sin(Θ) + y′ cos(Θ))s
++(A[xc][yc][Θ][s])
(3) Possible locations of the object contour are given by local maxima in A[xc][yc][Θ][s]
If A[xc][yc][Θ][s] > T, then the object contour is located at (xc, yc), has undergone a rotation Θ, and has been scaled by s.
<h2 id="advantages-and-disadvantages">Advantages and disadvantages</h2>
<h3>Advantages</h3>
<ul><li>It is robust to partial or slightly deformed shapes (i.e., robust to recognition under occlusion).</li>
<li>It is robust to the presence of additional structures in the image.</li>
<li>It is tolerant to noise.</li>
<li>It can find multiple occurrences of a shape during the same processing pass.</li></ul>
<h3>Disadvantages</h3>
<ul><li>It has substantial computational and storage requirements which become acute when object orientation and scale have to be considered.</li></ul>
<h2 id="related-work">Related work</h2>
Ballard suggested using orientation information of the edge decreasing the cost of the computation. Many efficient GHT techniques have been suggested such as the SC-GHT (Using slope and curvature as local properties).<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
Davis and Yam<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> also suggested an extension of Merlin's work for orientation and scale invariant matching which complement's Ballard's work but does not include Ballard's utilization of edge-slope information and composite structures

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Hough_transform/cYmx4Duw">Hough transform</a></li>
<li><a href="/facts/Randomized_Hough_transform/G15psxTp">Randomized Hough transform</a></li>
<li><a href="/facts/Radon_transform/JskFJRMS">Radon transform</a></li>
<li><a href="/facts/Template_matching/sE13sU8W">Template matching</a></li>
<li><a href="/facts/Outline_of_object_recognition/cdLpak1I">Outline of object recognition</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="/facts/OpenCV/V1tXAxyz">OpenCV</a> implementation of generalized Hough transform <a href="http://docs.opencv.org/master/dc/d46/classcv_1_1GeneralizedHoughBallard.html">http://docs.opencv.org/master/dc/d46/classcv_1_1GeneralizedHoughBallard.html</a></li>
<li>Tutorial and implementation of generalized Hough transforms <a href="http://www.itriacasa.it/generalized-hough-transform/default.html">http://www.itriacasa.it/generalized-hough-transform/default.html</a></li>
<li>Practical Generalized Hough transform implementation <a href="http://www.irit.fr/~Julien.Pinquier/Docs/Hough_transform.html">http://www.irit.fr/~Julien.Pinquier/Docs/Hough_transform.html</a></li>
<li>FPGA implementation of generalized Hough transforms, IEEE Digital Library <a href="https://ieeexplore.ieee.org/document/5382047/">https://ieeexplore.ieee.org/document/5382047/</a></li>
<li><a href="/facts/MATLAB/qPjLISCk">MATLAB</a> implementation of generalized Hough transform <a href="http://www.mathworks.com/matlabcentral/fileexchange/44166-generalized-hough-transform">http://www.mathworks.com/matlabcentral/fileexchange/44166-generalized-hough-transform</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">D.H. Ballard, "Generalizing the Hough Transform to Detect Arbitrary Shapes", Pattern Recognition, Vol.13, No.2, p.111-122, 1981 <a href="http://www.cs.utexas.edu/~dana/HoughT.pdf" target="_blank">http://www.cs.utexas.edu/~dana/HoughT.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Jaulin, L.; Bazeille, S. (2013). Image Shape Extraction using Interval Methods (PDF). In Proceedings of Sysid 2009, Saint-Malo, France. <a href="http://www.ensta-bretagne.fr/jaulin/paper_hough.pdf" target="_blank">http://www.ensta-bretagne.fr/jaulin/paper_hough.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Merlin, P. M.; Farber, D. J. (January 1975). "A Parallel Mechanism for Detecting Curves in Pictures". IEEE Transactions on Computers. C-24 (1): 96–98. doi:10.1109/t-c.1975.224087. ISSN 0018-9340. S2CID 27723442. <a href="https://escholarship.org/uc/item/0k76c6tt" target="_blank">https://escholarship.org/uc/item/0k76c6tt</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">L. Davis, "Hierarchical Generalized Hough Transforms and Line Segment Based Generalized Hough Transforms", University of Texas Computer Sciences, Nov 1980 <a href="http://www.cs.utexas.edu/ftp/techreports/tr80-6.pdf" target="_blank">http://www.cs.utexas.edu/ftp/techreports/tr80-6.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">J.A. Heather, Xue Dong Yang, "Spatial Decomposition of the Hough Transform", The 2nd Canadian Conference on Computer and Robot Vision, 2005. <a href="https://ieeexplore.ieee.org/document/1443168/" target="_blank">https://ieeexplore.ieee.org/document/1443168/</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Ballard and Brown, section 4.3.4, Sonka et al., section 5.2.6 <a href="http://www.cse.unr.edu/~bebis/CS791E/Notes/GeneralizedHough.pdf" target="_blank">http://www.cse.unr.edu/~bebis/CS791E/Notes/GeneralizedHough.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">A. A. Kassim, T. Tan, K. H. Tan, "A comparative study of efficient generalised Hough transform techniques", Image and Vision Computing, Volume 17, Issue 10, Pages 737-748, August 1999 <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">L. Davis and S. Yam, "A generalized hough-like transformation for shape recognition". University of Texas Computer Sciences, TR-134, Feb 1980. <a href="https://web.archive.org/web/20170706135526/ftp://ftp.cs.utexas.edu/pub/techreports/tr80-134.pdf" target="_blank">https://web.archive.org/web/20170706135526/ftp://ftp.cs.utexas.edu/pub/techreports/tr80-134.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
</ol>

Generalised Hough transform open-in-new

Generalised Hough transform