Method

Accumulation Step

Due to various reasons is the perspective projection of a line segment from the 3D scene onto the 2D image not congruent with the line segment detected in the image. We denote this perfect projection of a line segment as projected line segment. Hence, all vanishing points detection methods have to formulate either implicitly or explicitly a distance function between a vanishing point and a detected line segment. In this context the basic question is: How close is a projected line segment $s'$ with vanishing point $vp$ to its corresponding line segment $s$. In order to answer the question we represent a line segment with the midpoint representation $(m_x, m_y, l,\alpha_s)$ (see figure 3). We define: The perfect line segment $s'$ of a line segment $s$ has the same midpoint as $s$ and has $vp$ as vanishing point. On the basis of this definition a distance function $d(vp,s)$ between a vanishing point $vp$ and a line segment $s$ can be defined as the angle $\alpha$ between the corresponding line segments $s'$ and $s$. Figure 3 gives an example for a finite vanishing point. This distance function fulfill the requirements: Finite and infinite vanishing points are treated in the same way and the distances between points and line segments are independent of their location on the image plane.

Figure 3: Explanation for the distance function $d(vp,s)$ between a line segment $s$ and a finite vanishing point $vp$.

We are now able to formulate and fill the accumulator space. The intersection points, perhaps at infinity, of all pairs of non-collinear line segments are considered as accumulator cells, i.e. potential vanishing points. A line segment $s$ votes for an accumulator cell $a$ if the distance $d(a,s)$ is below a certain threshold $t_{a}$ and the vanishing point does not lie on the projected line segment $s'$, which correspond to $s$. In the search step we are interested in the total vote of an accumulator cell. This vote depends on the length of a line segment (assuming that longer line segments are more reliable) as well as on the distance between accepted line segments and the accumulator cell. We define

$$vote(a) = \sum_{\textrm{all accepted $s$\ of $a$}} w_1 \left... ...ength \ of \ $s$}}{\textrm{maximal \ length \ of $s$}} \right)$$ (1)

as the total vote of an accumulator cell $a$, where the weights $w_1$ and $w_2$ establish this trade off.

Search Step

Vanishing points which correspond to mutual orthogonal directions in the scene have to fulfill the following three criteria: Orthogonal criterion, camera criterion and vanishing line criterion. The first two criteria are affiliated with each other and we consider them first.

Let us consider a special type of perspective cameras with zero skew and same scale factor horizontally and vertically (aspect ratio one). This means that the intrinsic camera matrix is:

$${\small {{K}} = \left( \begin{array}{ccc} f & 0 & x_0 \\ ... ...ray} \right)} \quad \textrm{($\sim$\ means equal up to scale)}$$ (2)

with the focal length $f$ and the principle point $u_0=(x_0, y_0)^T$. We denote the three vanishing points on the image plane by $v_1, v_2$ and $v_3$. Since the vector $K^{-1}v_i$ from the camera centre $c$ to the vanishing point $v_i$ has the vanishing point $v_i$ (see figure 4), we can formulate the orthogonal criterion as:

$$\langle K^{-1}v_1, K^{-1}v_2 \rangle = 0, \langle K^{-1}v_1,... ...= 0 \ \textrm{and} \ \langle K^{-1}v_2, K^{-1}v_3 \rangle = 0,$$

where $\langle \cdot, \cdot \rangle$ is the scalar product. In order to determine the vector $K^{-1}v_i$ the focal length and the principle point have to be determined.

Figure 4: Explanation for the camera geometry and the orthogonal criterion.

It has been shown [4,9,16] that this can be achieved if all vanishing points are finite. Figure 4 shows such a case. The intersection point of the heights of the triangle $(v_1, v_2, v_3)$ defines the principle point and the size of this triangle fixes the focal length. However, in the case of one vanishing point at infinity the principle point is not defined uniquely. It lies on the line segment, which is defined by the two endpoints $v_1$ and $v_2$. Since the principle point is more likely positioned in the centre of the image, we choose it as the point, which lies on the line segment and is closest to the midpoint of the image. If two vanishing points are at infinity, the focal length can not be determined. However, the orthogonal criterion can still be checked since $K^{-1}v_i = v_i$ if $v_i$ is at infinity, i.e. $v_i= (x,y,0)^T$ (see equation 2). We can now specify the camera criterion. This criterion is fulfilled when the principle point and the focal length are inside a certain range, in the case they are calculable. Note, the additional check of the orthogonal criterion is needed for the case of one or two vanishing points at infinity.

Let us consider the vanishing line criterion. Two vanishing points $v_1$ and $v_2$ have a vanishing line when not both vanishing points are at infinity (see figure 1). This criterion checks that a line segment which votes for two vanishing points $v_1$ and $v_2$ is close to the vanishing line of $v_1$ and $v_2$ (see [13] for a formal definition of the criterion).

Algorithm

A brute force version for vanishing point detection is:

The Accumulation Step:
Establish the accumulator space (intersection of all pairs of non-collinear line segments)
Determine the vote of each accumulator cell (equation 1)

The Search Step:
Take the accumulator cell $a_1$ with the highest vote $vote(a_1)$ (equation 1)
Go through all pairs of accumulator cells $(a_i, a_j)$
$\quad$ If the vanishing line criterion is fulfilled for $(a_1, a_i)$, $(a_1,a_j)$ and $(a_i, a_j)$
$\quad \quad$ If the orthogonal criterion and camera criterion is fulfilled for $(a_1, a_i, a_j)$
$\quad \quad \quad$ Calculate $vote = vote(a_1) + vote(a_i) + vote(a_j)$
Take the accumulator cells $a_i, a_j$, with the highest vote $vote$
The vanishing points which correspond to the accumulator cells $a_1, a_i$ and $a_j$ represent the three mutual orthogonal directions of the scene.