Scribd Logo
Upload

Welcome to Scribd!

  • 4 views

    8-2d. Hough Transform-17-08-2024

    Uploaded by

    Subhash Battula

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    8-2d. Hough Transform-17-08-2024

    Uploaded by

    Subhash Battula
    4 views43 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    4 views43 pages

    8-2d. Hough Transform-17-08-2024

    Uploaded by

    Subhash Battula

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 43

    Computer Vision

    (Course Code: 4047)

    Module-2:Lecture-3: Hough Transform


    Gundimeda Venugopal, Professor of Practice, SCOPE
    Hough Transform
    Challenge: One of the problem with boundary detection of an object in an image is knowing which edges in
    the image that are corresponding to the boundary we are looking for.
    ❖ Hough Transform provides an elegant solution to the problem when the boundary can described by a small
    number of parameters.
    ❖The Hough Transform is an algorithm patented by Paul V. C. Hough and was originally invented to recognize
    complex lines in photographs (Hough, 1962).
    ❖ The algorithm has been modified and enhanced to be able to recognize other shapes such as circles and
    quadrilaterals of specific types.
    ❖ Perform edge detection first on the Input image (using edge detection algorithms: Canny, Sobel, Laplacian
    etc.) to produce an edge image which will then be used as input into the Hough Transform algorithm.
    Difficulties for the Fitting Approach
    Input Image Edge Map

    Task: Find the two wheels of the bicycle


    ❖ Extraneous Data: Which points to fit to? (e.g., to the bicycle circles, )
    ❖ Incomplete Data: Only part of the model is visible (e.g., Occlusion, Part of the wheel is incomplete.)
    ❖ Noise (e.g., edges close to the wheels which don’t correspond to real edges)

    Solution: Hough Transform (1962)


    Fit / Associate a model with observed features
    ❖Want to associate a model with observed features

    [Fig from Marszalek & Schmid, 2007]

    For example, the model could be a line, a circle, or an arbitrary shape.


    Fitting: Main idea
    • Choose a parametric model to represent a set of features
    • Membership criterion is not local
    ➢Can’t tell whether a point belongs to a given model just by looking at that
    point
    • Three main questions:
    ➢What model represents this set of features best?
    ➢Which of several model instances gets which feature?
    ➢How many model instances are there?
    • Computational complexity is important
    ➢It is infeasible to examine every possible set of parameters and every possible
    combination of features

    Slide credit: L. Lazebnik


    Case study: Line fitting
    ❖Why fit lines?
    Many objects characterized by presence of straight lines

    • Wait, why aren’t we done just by running edge detection?


    Difficulty of Line Fitting
    ❖ Extra edge points (clutter), multiple
    models:
    ➢ which points go with which line, if any?
    ❖ Only some parts of each line detected,
    and some parts are missing:
    ➢ how to find a line that bridges missing
    evidence?
    ❖ Noise in measured edge points,
    orientations:
    ➢ how to detect true underlying
    parameters?
    Voting

    ❖It’s not feasible to check all combinations of features by fitting a model to each
    possible subset.

    ❖Voting is a general technique where we let the features vote for all models that are
    compatible with it.
    ➢ Cycle through features, cast votes for model parameters.
    ➢ Look for model parameters that receive a lot of votes.

    ❖Noise & clutter features will cast votes too, but typically their votes should be
    inconsistent with the majority of “good” features.
    Hough Transform: Line Detection
    Hough Transform: Line Detection

    Note: Straight line equation for m and c


    Hough Transform: Line Detection (Hough Parameter Space)
    Transform all the image points from Image Space to Hough Parameter Space
    Hough Transform: Concept
    Transform all the image points from Image Space to Hough Parameter Space
    Hough Transform: Line Detection Algorithm (with a Voting scheme)

    A(m,c) A(m,c) A(m,c) A(m,c) A(m,c)


    0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1
    0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0
    c 0 0 0 0 0 c 0 0 1 0 0 c 0 0 2 0 0 c 1 1 3 1 1 c 1 1 3 1 1
    0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0
    0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1
    m m m m m
    Initialize Accumulator Adding Point 1 Adding Point 2 Adding Point 3 … Detect Line (m,c) using Voting

    https://fiveko.com/online-tools/hough-circle-detection-demo/
    Multiple Lines Detection
    Better Parameterization
    Two Line Equations
    Better Parameterization
    Better Parameterization
    Better Parameterization
    Hugh Transform Mechanics
    ❖ How big should the accumulator cells be?
    ➢ Too big: Different lines may be merged.
    ➢ Too small: Noise causes lines to be missed. Miss lines because some points that are not exactly collinear cast votes for different buckets
    ❖ How many lines
    ➢ Count the peaks in the accumulator array
    ❖ Try to get rid of irrelevant features
    ➢ Take only edge points with significant gradient magnitude
    ❖ Handling inaccurate edge locations:
    ➢ Increment patch in accumulator rather than single point
    ❖ Strong Edges
    ➢ Give more votes for stronger edges.
    ➢ Examine the surrounding pixels in the chosen cell
    ➢ Edge thinning can be beneficial
    ❖ Change the sampling of (ρ, ) to give more/less resolution
    ❖ Increment neighboring bins (smoothing in accumulator array)
    Hugh Transform Advantages and Disadvantages
    ❖Advantages
    • Can deal with non-locality and occlusion
    • Can detect multiple instances of a model (e.g., line, circle, …) in a single pass
    • Some robustness to noise: noise points unlikely to contribute consistently to any single bin
    ❖ Disadvantages
    ➢ Complexity of search time increases exponentially with the number of model parameters
    ➢ Non-target shapes can produce spurious peaks in parameter space
    ➢ It’s hard to pick a good Accumulator (grid) size
    Line Detection Results
    Line Detection Results
    Line Detection Results

    Different lines are merged

    https://github.com/adityaintwala/Hough-Line-Detection
    Hugh Transform: Circle Detection
    Hugh Transform: Circle Detection
    Hugh Transform: Circle Detection
    Circle Detection Results
    Using Gradient Information
    Using Gradient Information
    Using Gradient Information
    Using Gradient Information
    Hough Transform: Circle Detection

    Note: Complexity of search time increases exponentially with the number of model parameters
    Generalized Hough Transform
    Generalized Hough Transform
    Hough Model
    Generalized Hough Transform
    Results
    Handling Scale and Rotation
    Hough Transform: Comments
    Hough Transform: Line Detection (Parameter Space)
    Hough Transform Concept
    Hough Transform Concept

    You might also like