Hough Transformation

The Hough Transformation (patented by Paul V. C. Hough in 1962, MethodsAndMeansForRecognizingComplexPatterns.pdf) is one possibility to do pattern recognition. It is a global method which means that all hits (points in 3D space) enter the algorithm at the same time and in the same way. It works for any kind of track shape which can be described by one set of parameters.

Straight Line in a 2D Plane

To describe a straight line in a 2D plane two parameters are needed. These two parameters are chosen to be

attachment:StraightLineParameter.png

The equation describing this straight line is

Equation_sl_1.png .

This equation is then transformed into the following function:

Equation_sl_2.png .

As a next step the positions of the hits are inserted into this function. Each hit then gives one function. If the hits are all on one straight line all functions intersect in one point in Hough Space. The point of intersection gives the parameters describing the straight line the hits are on. The Hough Space for one straight line looks like this:

attachment:HoughSpace_sl.png

Circle in a 2D Plane

Three parameters are needed to describe a circle in a plane:

attachment:CircleParameter.png

The search for circles is split into two parts:

The center of the circle is parametrized by its distance from the origin and the angle between the x-axis and the direction towards the center of the circle. In order to find the center of the circle pairs of hits are used. First one straight line is constructed which crosses two hits. In a second step a second straight line is constructed which is perpendicular to the first straight line and crosses it half way between the two hits. If the two hits are both on the circle, the second straight line also crosses the the center of the circle. In all other cases the second straight line points into a random direction.

attachment:CircleFinding1.png attachment:CircleFinding2.png

The function obtained by this reads:

Equation_cc_1.png .

The positions of the hits are then inserted into the function. Each pair of hits gives one function which all intersect in one point in Hough Space. The Hough Space looks like this:

attachment:HoughSpace_cc.png

Now that the center of the circle is known the radius needs to be determined. This is done by calculating the distance of each hit to the center of the circle. The distance which occurs most often is the radius of the circle.

In order to avoid discontinuities one can use the inverse of D.

attachment:HoughSpace_cc_inverse.png


CategoryTpc

HoughTransformation (last edited 2012-09-04 15:20:00 by IsaHeinze)