558
R. Frühwirth et al.
−2
−1
0
1
2
3
4
0
1
2
3
4
5
θ
n
Fig. 13.2 Histogram of θ = arctan(v/u)
an increment of a set of histogram bins. Measurements lying along straight lines
tend to create peaks in the histogram, and the lines can be found by searching for
peaks in this histogram. The granularity of the discretization has to be optimized
for each specific application, as it depends on the amount of noise present and the
actual values of measurement uncertainties. A too fine-grained histogram can split
or destroy peaks if the measurement uncertainties are non-negligible. On the other
hand, a too course-grained histogram increases the sensitivity to noise, and nearby
tracks may merge into a single peak.
The basic formulation of the Hough transform is an example of a divergent
transform, i.e., one measurement in image space corresponds to a set of increments
of histogram entries in parameter space. The Hough transform can also be made
convergent by considering instead a pair of measurements in image space. A unique
line passes through any such pair, and only one entry in the parameter space
histogram needs to be incremented. A possible disadvantage of such an approach
is that the number of pairs grows quadratically with the number of measurements in
image space. In order to reduce computational complexity, one may consider only
a randomly selected subset of all the pairs. This is the basic feature of probabilistic
Hough transforms [4].
The Hough transform has turned out to be successful also for finding circles
passing through the origin. With this constraint, two parameters are enough to
uniquely describe the circle, and the task again amounts to finding peaks in a twodimensional histogram. With three or more parameters, one has to search for clusters
in multi-dimensional spaces, and in this case the Hough transform is in general less
powerful than in the two-dimensional case.
R. Frühwirth et al.
−2
−1
0
1
2
3
4
0
1
2
3
4
5
θ
n
Fig. 13.2 Histogram of θ = arctan(v/u)
an increment of a set of histogram bins. Measurements lying along straight lines
tend to create peaks in the histogram, and the lines can be found by searching for
peaks in this histogram. The granularity of the discretization has to be optimized
for each specific application, as it depends on the amount of noise present and the
actual values of measurement uncertainties. A too fine-grained histogram can split
or destroy peaks if the measurement uncertainties are non-negligible. On the other
hand, a too course-grained histogram increases the sensitivity to noise, and nearby
tracks may merge into a single peak.
The basic formulation of the Hough transform is an example of a divergent
transform, i.e., one measurement in image space corresponds to a set of increments
of histogram entries in parameter space. The Hough transform can also be made
convergent by considering instead a pair of measurements in image space. A unique
line passes through any such pair, and only one entry in the parameter space
histogram needs to be incremented. A possible disadvantage of such an approach
is that the number of pairs grows quadratically with the number of measurements in
image space. In order to reduce computational complexity, one may consider only
a randomly selected subset of all the pairs. This is the basic feature of probabilistic
Hough transforms [4].
The Hough transform has turned out to be successful also for finding circles
passing through the origin. With this constraint, two parameters are enough to
uniquely describe the circle, and the task again amounts to finding peaks in a twodimensional histogram. With three or more parameters, one has to search for clusters
in multi-dimensional spaces, and in this case the Hough transform is in general less
powerful than in the two-dimensional case.