Overview of existing methods

The majority of vanishing point detection methods rely on line segments detected in the image. In this overview only those methods will be considered in more detail. A different approach is to utilize the intensity gradients of the pixel units in the image directly [6,17].

The task of detecting those vanishing points that correspond to the dominant directions of a scene is traditionally solved in two steps. Firstly, line segments are clustered together on the condition that a cluster of line segments shares a common vanishing point. We denote this step as the accumulation step. In the second step, the dominant clusters of line segments are searched for. We refer to this step as the search step.

Let us consider the accumulation step first. In order to reduce the computational complexity of the clustering process, the unbounded image $R^2$ is mapped onto a bounded space. This has the additional advantage that infinite and finite vanishing points can be treated in the same way. The bounded space, also denoted as accumulator space, can then be partitioned into a finite number of cells, so-called accumulator cells.

Barnard [2] suggested the Gaussian sphere centred on the optical centre of the camera as an accumulator space (see Figure 2).

Figure 2: The Gaussian sphere as an accumulator space.

A great circle on the Gaussian sphere represents a line segment in the image and a point on the Gaussian sphere corresponds to a vanishing point in the image. Figure 2 shows that the great circles of two line segments in the image plane always intersect in one point, their vanishing point. For the accumulation of line segments, the Gaussian sphere is tessellated into accumulator cells, and each cell is increased by the number of great circles which pass through it.

This approach was then enhanced in other works. Since Barnard chose an irregular and quite ad hoc tessellation of the Gaussian sphere, this was improved by Quan and Mohr [12]. Lutton et al. [10] investigated the influence of different error types, e.g. error due to the finite extension of the image, in the accumulation process on the Gaussian sphere. Magee and Aggarwal [11] accumulated the projection of the intersection points of all pairs of line segments in the image onto the Gaussian sphere. This approach is computationally more intensive but on the other hand more accurate. Alternative accumulator spaces were introduced by the authors [15,3]. Brillault [3] established an uncertainty model for a line segment. According to this model an accumulator space is introduced, in which the expected uncertainty of a line segment remains constant in the accumulator space.

A different approach to reducing the computational complexity of the accumulation step is to apply the Hough transformation by mapping the parameters of the line segments into a bounded Hough space [1,17]. Tuytelaars et al. [17] applied the Hough transformation three times (Cascade Hough transformation). At different levels of the Cascade Hough transformation a peak in the Hough space corresponds to a vanishing point and a vanishing line respectively.

A fundamental drawback of all techniques which transfer information from the image into a bounded space is that the original distances between lines and points are not preserved. Let us consider the two great circles of the two line segments in figure 2. Due to the perspective effect of the projection from the image plane onto the Gaussian sphere the distance between these two great circles differs when the two line segments undergo the same movement on the image plane. Therefore, the distance between a line segment and a vanishing point depends on their location on the image plane, i.e. the distances between points and lines on the image plane are not translationally and rotationally invariant. This drawback can be avoided when line segments are not transformed into a bounded space, i.e. the image plane is chosen as the accumulator space. Rother [13] (see next section) showed that although the image plane is used as the accumulator space finite and infinite vanishing points can be treated in the same way.

In the past, more effort has been spent on the accumulation step than on the search step. One of the reasons for this is that the directions in the scene of the searched dominant vanishing points do not have to be orthogonal. This means that the orthogonality of the direction of vanishing points was not treated as an additional criterion of the search step. In [11,12] the search step was designed in a straight forward manner. Firstly, the dominant vanishing point, which corresponds to the accumulator cell with most line segments, is detected. After removing the line segments which correspond to this vanishing point the search for a maximum in the accumulator space is repeated. The iterating process stops when the number of line segments of a dominant vanishing point is below a certain threshold. This approach is characterized by a minimal computational effort.

Recently, van den Heuvel [8] developed a method for detecting the three mutually orthogonal directions in the scene. The orthogonality criterion was explicitly used, which means that all combinations of three possible vanishing points have to be considered. This method requires higher computational effort than the approach mentioned above. However, van den Heuvel chose one of the vanishing points manually. Rother [13] (see next section) established beside the orthogonality criterion two other criteria (camera and vanishing line criterion) which three orthogonal vanishing points have to fulfill. Coughlan and Yuille [6] searched for two orthogonal directions in the scene using statistics.