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
- the closest distance of the track to the origin of the coordinate system.
- the angle between the x-axis and the direction of the closest distance.
The equation describing this straight line is
This equation is then transformed into the following function:
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:
Circle in a 2D Plane
Three parameters are needed to describe a circle in a plane:
- the shortest distance between track and origin.
- the angle between the x-axis and the direction of the shortest distance
- radius/ curvature of the circle.
The search for circles is split into two parts:
- Search for the center of the circle.
- Determination of the radius of the circle.
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.
The function obtained by this reads:
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:
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.