Use of the Hough Transformation To Detect Lines and Curves in Pictures

Use of the Hough Transformation To Detect Lines and Curves in Pictures

January 1972 | Richard O. Duda and Peter E. Hart
This paper presents an efficient method for detecting lines and curves in digital images, known as the Hough transformation. The method transforms points in the image into curves in a parameter space, allowing the detection of colinear points by finding intersections of these curves. The paper introduces the normal parameterization, which uses the angle θ of the line's normal and its distance ρ from the origin, simplifying the computation compared to the slope-intercept parameters. This parameterization allows for efficient detection of lines and curves by converting the problem into finding intersections in the parameter space. The method is applied to detect colinear points by transforming each point into a sinusoidal curve in the θ-ρ plane. Colinear points correspond to curves that intersect at a common point in the parameter space. The paper also discusses how the method can be extended to detect more general curves by choosing appropriate parameterizations. The Hough transformation is implemented using a two-dimensional accumulator array, where each point in the image is transformed into a curve, and the accumulator is incremented along the curve. High counts in the accumulator indicate the presence of colinear points. The method is efficient because it avoids checking all pairs of points, which would be computationally expensive. The paper also provides alternative interpretations of the method, explaining its efficiency. One interpretation shows that the method considers only the lines through each point, rather than all possible lines between points. Another interpretation relates to the projection of points onto lines, where nearly colinear points project to nearly coincident points. The method is demonstrated with an example, where it successfully detects lines in a digitized image. However, the method has limitations, such as sensitivity to quantization and the potential for detecting meaningless groups of colinear points. The paper concludes that the Hough transformation is a computationally efficient method for detecting lines and curves in images, and can be extended to detect more general curves by choosing appropriate parameterizations.This paper presents an efficient method for detecting lines and curves in digital images, known as the Hough transformation. The method transforms points in the image into curves in a parameter space, allowing the detection of colinear points by finding intersections of these curves. The paper introduces the normal parameterization, which uses the angle θ of the line's normal and its distance ρ from the origin, simplifying the computation compared to the slope-intercept parameters. This parameterization allows for efficient detection of lines and curves by converting the problem into finding intersections in the parameter space. The method is applied to detect colinear points by transforming each point into a sinusoidal curve in the θ-ρ plane. Colinear points correspond to curves that intersect at a common point in the parameter space. The paper also discusses how the method can be extended to detect more general curves by choosing appropriate parameterizations. The Hough transformation is implemented using a two-dimensional accumulator array, where each point in the image is transformed into a curve, and the accumulator is incremented along the curve. High counts in the accumulator indicate the presence of colinear points. The method is efficient because it avoids checking all pairs of points, which would be computationally expensive. The paper also provides alternative interpretations of the method, explaining its efficiency. One interpretation shows that the method considers only the lines through each point, rather than all possible lines between points. Another interpretation relates to the projection of points onto lines, where nearly colinear points project to nearly coincident points. The method is demonstrated with an example, where it successfully detects lines in a digitized image. However, the method has limitations, such as sensitivity to quantization and the potential for detecting meaningless groups of colinear points. The paper concludes that the Hough transformation is a computationally efficient method for detecting lines and curves in images, and can be extended to detect more general curves by choosing appropriate parameterizations.
Reach us at info@study.space