Hough transform Hough transform principle

Hough Transform Hough transform

principle

  In Cartesian coordinates , A straight line consists of two A=(x1, y1) and B=(x1, y2) determine , Here's the picture ：

  Put a straight line y=kx + b Can be written about (k, q) Function expression for :

  The corresponding transformation is visually represented by graphics, as shown in the following figure ：

  The transformed space is called Hough space . namely ： A straight line in Cartesian coordinate system , Corresponding to a point in Hough space . In turn, , The same holds true , A line in Hough space , Corresponds to a point in the Cartesian coordinate system , As shown in the figure below ：

  Let's see A、B Two points , Corresponding to the case of Hough space ：

 A Mapping to Hough space is a straight line ,B It also maps to a line in Hough space , These two lines have an intersection in Hough space . This intersection represents the Cartesian coordinate system by A、B The slope and intercept of the straight line formed by two points .
  Let's take another look at the collinearity of three points , Here's the picture ：

  It can be seen that , If the points of the Cartesian coordinate system are collinear , Then the lines corresponding to these points in Hough space intersect at a point .
  If there is more than one straight line , As shown in the figure below ：

  We choose as many straight lines as possible to form points , The three straight lines in the above figure converge into A、B At two o 'clock , Corresponding it back to the straight line in the Descartes coordinate system, as shown in the following figure ：

  Come here , We seem to have solved the Hough transform , But if it's like the picture below ：

  Above picture , The slope of a straight line does not exist . To solve this problem , We consider converting Cartesian coordinates to polar coordinates .

  It's the same in polar coordinates , Points in polar coordinates correspond to lines in Hough space , This is the Hough space parameter, which is no longer (k, q) 了 , It is (ρ, θ) Space ,ρ Is the vertical distance from the origin to the line ,θ Represents the angle between the vertical line and the horizontal axis in the clockwise direction , The angle of the vertical line is 0 degree , The angle of the horizontal line is 180 degree .

  We just need to find the location of the intersection in Hough space , The straight line in the original coordinate system can be obtained .

Implementation process

  Suppose there is a size of 100x100 Pictures of the , Use Hough transform to detect the straight line in the picture , The steps are as follows ：

• Straight lines can be used (ρ, θ) Express , First create a 2D Array , We can call it accumulator , Initialize ownership to 0, Row representation ρ, Column means θ.
  
  The size of the array determines the accuracy of the results , If you want the accuracy of the angle to be 1 degree , It needs to 180 Column . about ρ, The maximum value is the diagonal distance of the picture , If you want the accuracy to reach the pixel level , The number of lines should be equal to the diagonal distance of the image .

• Take the first point of the contour edge of the binary graph (x, y), Bring it into the polar coordinate formula of the straight line , Then traverse θ The value of ：0,1,2,…,180, Find the corresponding ρ value , If this value has a corresponding position in the above accumulator , Then add 1.

• Take the first point of the contour edge of the binary graph (x, y), Repeat the above steps , Update accumulator .

• Search for the maximum value in the accumulator , And find the corresponding (ρ,θ), The straight lines in the image can be represented .