ژوئن 14, 2019
###### الگوریتم جستجوی هارمونی
ژوئن 14, 2019

5 | F a t o u m a t a D e m b e l e
Hough Transform
Generalized Hough Transform:
The GHT is a modified version of the HT that not only searches for analytically defined shapes,
but also arbitrary shapes (shapes that cannot be defined by an analytical equation).
This method uses the principle of template matching, which relies on detecting smaller elements
matching a template image.
Theory:
The HT can be described as a transformation of a point in a 2 dimensional region to a parameter
space, dependent on the shape of the objects to be identified. The basic functionality of the HT is
to detect straight lines. A straight line in the x,y-plane is described by:
y = m*x + b (1)
This line is represented in the Cartesian coordinate system by its parameters b and m where m is
the slope and b is the intercept. Due to the fact that perpendicular lines to the x-axis can give
unbounded values for parameters m and b (b and m rises to infinity), lines are parameterized in
terms of theta θ and r such that:
r= x*cos (θ) + y*sin (θ), for θ [0 ,] (2)
Figure 1
where r is the distance between the line and
the origin, θ is the angle. Thus, given x and y, every
line passing through point (x, y) can uniquely be
represented by (θ, r). Both θ and r have finite sizes. The
distance r will have the maximum value of two times
the diagonal of the image.
6 | F a t o u m a t a D e m b e l e
An edge detector is commonly used to provide a set of points that represents the boundaries in
the image space.
Equation (1) corresponds to a sinusoid curve in the (r, θ) plane unique to that point. If several
points are located on the same line, they produce sinusoids crossing at the parameters for that
line.
Implementation:
An array, called an accumulator is used to detect the existence of a line y = m*x +b. In other
words, it counts the votes for sets of parameter values. For instance, the HT detecting straight
lines has two unknown parameters m and b. The HT then proceeds to a voting in order to
determine which pixel is likely to be an edge on the image. If there is enough evidence that a
point might be an edge, then increment the parameter values corresponding to the lines that
would cause this line to appear in the edge image (Luke Fletcher, 2).
The following is an illustrated example.
Figure 2 (Source: Wikipedia online Hough Transform)
Each point in the Figure 2 is a point in the edge image.
Consider drawing several lines going through each data point.
A line, starting from the origin and perpendicular to each solid line is then drawn, the length and
angle of each dashed line is then measured and stored in the tables in Figure 2.
7 | F a t o u m a t a D e m b e l e
Figure 3 (Source: Wikipedia online Hough Transform)
The graph is Figure 3 shows how different lengths are related to different angles. The
point (purple) where the curves intersect provides the distance and angle from all 3 points
located on the same line. The value of the parameters (angle and length) of the line is then added
to the array for future reference.
Matlab example:
Below is an example of applying the Hough transform on a Gantry crane image.
8 | F a t o u m a t a D e m b e l e
Circular Hough Transform
Implementation:
Unlike the linear HT, the CHT relies on equations for circles. The equation of the a circle is,
r² = (x – a)² + (y – b)² (3)
Here a and b represent the coordinates for the center, and r is the radius of the circle.
The parametric representation of this circle is
x = a + r*cos(θ)
y = b + r*sin(θ) (4)
In contrast to a linear HT, a CHT relies on 3 parameters, which requires a larger computation
time and memory for storage, increasing the complexity of extracting information from our
image.
For simplicity, most CHT programs set the radius to a constant value (hard coded) or provide the
user with the option of setting a range (maximum and minimum) prior to running the application.
For each edge point, a circle is drawn with that point as origin and radius r. The CHT also uses
an array (3D) with the first two dimensions representing the coordinates of the circle and the last
third specifying the radii. The values in the accumulator (array) are increased every time a circle
is drawn with the desired radii over every edge point. The accumulator, which kept counts of
how many circles pass through coordinates of each edge point, proceeds to a vote to find the
highest count. The coordinates of the center of the circles in the images are the coordinates with
the highest count. 