Parameter Space; Hough Transform

The approach discussed here detects lines even if they are disrupted by noise or are only partially visible. We start by assuming that we have a segmented image that contains lines of this type. The fact that points lie on a straight line results in a powerful constraint that can be used to determine the parameters of the straight line. For all points [x_n, y_n]T on a straight line, the following condition must be met:

 

y_n = a₀ + a₁x_n,                                                 (16.7)

16.5 Model-Based Segmentation                                                  437

A                                                                    b

a1     a0

10                                                                     6

 

4

 

5

2

y                                                                    a₁

0

0

 

-2

 

-5

-6 -4   -2   0    2   4    6

x

-4

0         1         2         3         4

T

a0

 

Σ    Σ

Figure 16.6: Hough transform for straight lines: the x, y

mapped onto the [a₀, a₁]^T model space ( b ).

data space ( a ) is

 

where a₀ and a₁ are the off set and slope of the line. We can read Eq. (16.7) also as a condition for the parameters a₀ and a₁:

a₁ = y n − 1 a₀.                                              (16.8)

x_n   x_n

−

This is again the equation for a line in a new space spanned by the parameters a₀ and a₁. In this space, the line has the off set y_n/x_n and a slope of 1/x_n.

With one point given, we already cease to have a free choice of a₀ and

a₁ as the parameters must satisfy Eq. (16.8).

The space spanned by the model parameters a₀ and a₁ is called the model space. Each point reduces the model space to a line. Thus, we can draw a line in the model space for each point in the data space, as illustrated in Fig. 16.6. If all points lie on a straight line in the data space, all lines in the model space meet in one point which gives the parameters a₀ and a₁ of the lines. As a line segment contains many points, we obtain a reliable estimate of the two parameters of the line. In this way, a line in the data space is mapped onto a point in the model space. This transformation from the data space to the model space via a model equation is called the Hough transform. It is a versatile instrument to detect lines even if they are disrupted or incomplete.

In practical applications, the well-known equation of a straight line given by Eq. (16.7) is not used. The reason is simply that the slope of a line may become infi nite and is thus not suitable for a discrete model space. A better parameterization of a straight line is given by using two diff erent parameters with fi nite values. One possibility is to take the

438                                                                                                    16 Segmentation

 

A                                                      b

C                                                       d

Figure 16.7: Orientation-based fast Hough transform: a and b unevenly illumi- nated noisy squares; c and d Hough model space with the distance d (horizontal axis) and the angle θ (vertical axis) of the lines according to Eq. (16.9) for a and b, respectively.

 

angle of the slope of the line and the distance of the line from the center of the coordinate system. With these two parameters, the equation of a straight line can be written as

 

n ¯ x = d  or  x cos θ + y sin θ = d,                                      (16.9)

where n ¯ is a vector normal to the line and θ the angle of this vector to the x axis of the image coordinate system.

The drawback of the Hough transform method for line detection is the high computational eff ort. For each point in the image, we must compute a line in the parameter space and increment each point in the model space through which the line passes.

16.6 Further Readings‡                                                                                        439

 

⇐ Предыдущая64656667686970717273Следующая ⇒

Поделиться: