Methods based on Hough Transformation.In HT method, each image point is treated independently, its independent combination of evidence means that it can recognize partial or slightly deformed shapes. The HT converts a difficult global detection problem in image space into a more easily solved local peak detection problem in a parameter space 2.Dori 3 discuss Hough Transform is used in line recognition by transforming spatially extended patterns in binary image data into spatially compact features in a parameter space. Parametric shapes in an image are detected by looking for accumulation points in the parameter space.

If a particular shape is present in the image, then the mapping of all of its points into the parameter space must cluster around the parameter values which correspond to that shape.One way the HT can be used to detect lines is to parameterize it according to its slope and intercept. Straight lines are defined in eq-1 —–(1)Thus, every line in the (x,y) plane corresponds to a point in the (m, c) plane. Every point on the (x,y) plane can have an infinite number of possible lines that pass through it.The gradients and intercepts of these lines form on the (m, c) plane a line described by eq-(2). —–(2)The (m, c) plane is divided into rectangular ‘bins’ which accumulate for each black pixel in the (x,y) plane; all the pixels lying along the line in eqn (2). When the line of eqn (2) is drawn for each black pixel, the cells through which it passes are incremented. Considering the noise, lines are identified as peaks in transformed space, if it is greater than predefined threshold value in eq-1.

The Space complexity of HT based method is quadratic to the image resolution. Hart 4, uses angle-radius instead of slope-intercept parameters to simplify the computation, by using normal parameterization instead of parameter space. This parameterization specifies a straight line by the angle of its normal and its algebraic distance p from the origin. The parameter space can be represented by following equation. It reduces the problem of unbounded of slope and Intercept in original HT to finite parameter space. Although both techniques are not capable in finding polylines. 1 Hough, P. V.

C. “A method and means for recognizing complex patterns”, USA Patent 3,096,654, 1962.2 Illingworth, Kitter,” A Survey of the Hough Transform”, Computer Vision, Graphics, and Image processing 44,87-116,3 Dori D. Orthogonal Zig-Zag: an Algorithm for Vectorizing Engineering Drawings Compared with Hough Transform. Advances in Engineering Software 1997;28(1):11–24 4 Richard O.

Duda, Peter E. Hart, Use if the Hough Transformation To Detect Lines and Curves in Pictures. Technical Note 36, April 1971