2.1.

Vanishing Point Detection

Finding the VPs in 2-D perspective projections has received much attention since Barnard’s methodology was proposed in 1983.³ Each line group is often processed by the three elements of line extraction, line classification and VP estimation.

Many present studies focus on the second element. With regard to the number of detected VPs, these algorithms aim at estimating three estimate three orthogonal VPs,^4,5 or any present nonorthogonal VP.^3,6,7 Based on their estimation strategy, line classification algorithms are roughly divided into two categories; algorithms that specify accumulator spaces and those that perform the clustering directly on the image plane.

In the former category, an open image plane is mapped into a bounded accumulator space. These algorithms aim for simple operation and do not discriminate between finite and infinite VPs.^3,4,8 Each cell in the space accumulates the lines that pass through its corresponding image point. Cells that have accumulated the most lines will produce the candidate VPs. The performances of these algorithms are mainly determined by the selected accumulator space.

In the latter category, the workspace is the actual image plane.^6,9 Line clustering is generally decided by computations, such as the distances among points and lines. Typical computational methods are random sample consensus (RANSAC) and its variants (such as multi-RANSAC and J-Linkage).^7,10–12 These methods iteratively select the minimal sampling set of image features for computing a candidate VP, and retrieve the feature set consistent with that minimal sampling set. Another traditional approach is the EM approach,^5,13 which alternates between expectation and maximization steps (denoted as E and M steps, respectively). The E step estimates the line clustering from the given current or hypothesized VPs; the M step computes the VPs using the data clusters estimated in the E step.

Although accumulator space–based algorithms require the intrinsic camera parameters, clustering in the image plane operates in an uncalibrated setting. However, RANSAC and its variants do not guarantee an optimal solution, whereas the success of the EM approach depends on the initially estimated VPs. Our present study attempts to overcome the inherent limitations of conventional image plane clustering algorithms, and to detect possible nonorthogonal VPs.

2.2.

Artificial Bee Colony

An ABC algorithm, proposed by Karaboga,¹⁴ simulates the intelligent foraging behavior of honey bee swarms. Originally designed for solving multidimensional and multimodal optimization problems, the ABC algorithm has since been extended to other problems. For example, Akay and Karaboga¹⁵ concluded that ABC efficiently solves integer programming problems. The ABC variant DisABC, introduced by Kashan et al.,¹⁶ was designed for binary optimization.

In the ABC algorithm, the possible solutions to the optimization problem are represented as food sources; the nectar amount in each food source indicates the quality (fitness) of the potential solution. A swarm of bees investigates the optimum solution.^17–19 Each bee assumes one of the following three roles:

The ABC algorithm randomly creates a set of candidate solutions, and each solution is assigned to one employed bee. It then iteratively executes three important steps to find new solutions.

In the first step, each employed bee searches for a new solution within the neighborhood of its current solution. Let ${\mathbf{X}}_{\mathbf{i}}=(x_{i1},\dots ,x_{id},\dots ,x_{iD})$ be the position of the $i$’th food source (the $i$’th solution to the problem), $D$ be the dimension of the problem, and $f({\mathbf{X}}_{\mathbf{i}})$ be the amount of nectar (quality of the solution). The position of a new food source (${\mathbf{X}}_{\mathbf{i}}^{\prime }=(x_{i1}^{\text{'}},\dots ,x_{id}^{\text{'}},\dots ,x_{iD}^{\text{'}})$) is calculated as follows:

If the nectar amount $f({\mathbf{X}}_{\mathbf{i}}^{\prime })$ is greater than $f({\mathbf{X}}_{\mathbf{i}})$, the artificial bee memorizes ${\mathbf{X}}_i^{\text{'}}$ and shares her information with onlooker bees. The position of the $i$’th food source becomes ${\mathbf{X}}_i^{\text{'}}$. If $f({\mathbf{X}}_{\mathbf{i}}^{\prime })$ does not exceed $f({\mathbf{X}}_{\mathbf{i}})$, the food source remains at ${\mathbf{X}}_i$.

In the second step, based on the information provided by the employed bees, each onlooker bee probabilistically chooses a candidate solution to further update. The probability is decided by the roulette wheel rule

In the third step, employed bees whose solutions never improve after a predetermined number of trials (called the limit) become scouts and their solutions are abandoned. The scouts embark on random searches for new solutions. The new random position chosen by the scout is calculated as follows:

In Eq. (4), $x_{\min }^d$ and $x_{\max }^d$ are the lower and upper bounds of the food source position, respectively, in dimension $d$.

3.1.

Modeling the Problem of Vanishing Point Detection Using Artificial Bee Colony

VP detection is a typical chicken-and-egg problem: if the line clustering is known, then the VPs can be computed reciprocally; if the VPs are known, the line clustering can be retrieved. Therefore, given a set of features describing the linear structure in an image, VP estimation strategies typically proceed by clustering and estimation. The lines are first classified into groups with common VPs. The approximate VP is then located from the line cluster. Like other algorithms, our proposed algorithm alternately iterates the clustering and estimation steps. Especially, the line classification is modeled as an unsupervised clustering problem solved by a novel ABC, and its optimal result is processed by the estimation step.

One of the key issues in designing a successful algorithm for VP detection is to suitably assign the line classification solutions to the food sources in the ABC algorithm. In this study, a food source is defined as a binary vector representing a partition of the line set. Binary vector encoding proceeds as follows. Based on some heuristic information, the set of line segments in an image is initially partitioned into line clusters. VPs computed by those line clusters are then collected into a set. A food source is finally encoded as a binary vector whose dimensions are equal to the size of the VP set. Each vector component, either 1 or 0, indicates whether the VP at the corresponding set position is selected to repartition line clusters through the latter optimal steps. As shown in Fig. 1, 200 line segments $\{{\xi }_1,{\xi }_2,\dots ,{\xi }_{200}\}$ extracted from an image are initially divided into seven subsets. A VP set $\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_7\}$ is built from each subset producing one VP. A binary vector $\{\mathrm{0,1},\mathrm{1,0},\mathrm{1,1},1\}$ is randomly generated as a food source (solution) to indicate the selected VP set $\{{\mathbf{v}}_2,{\mathbf{v}}_3,{\mathbf{v}}_5,{\mathbf{v}}_6,{\mathbf{v}}_7\}$. The set $\{{\xi }_1,{\xi }_2,\dots ,{\xi }_{200}\}$ is then repartitioned so that each line segment is associated with one VP of the set $\{{\mathbf{v}}_2,{\mathbf{v}}_3,{\mathbf{v}}_5,{\mathbf{v}}_6,{\mathbf{v}}_7\}$ or is marked as an outlier.

Fig. 1

Example showing the encoding procedures of a solution vector.

Another problem that arises when modeling VP detection using the ABC algorithm is how to evaluate and update food sources (solutions).^17,18 In the present study, the fitness of a solution is evaluated by validating the line cluster, thus determining whether the cluster is cohesive with low coupling. In particular, a distance function is introduced to measure the deviation between each VP and the corresponding line segment. Moreover, the solutions are updated by the three types of bees (employed bees, onlooker bees, and scouts), as described in Sec. 4.

3.2.

A Priori Information of Line Segments

The angle of two line segments in an image plane, which corresponds to the perspective view of two parallel lines in an object plane, is related to the shooting angle and the distances between the parallel lines and between the image and the object plane. The shooting angle is usually presented by the angle between the image and the object plane. More specifically, the angle of two segments widens as the shooting angle becomes larger or as the parallel lines become more separated, but decreases with an increasing distance of the two planes. In practice, the distances between parallel lines in a man-made environment are distributed within a certain range, whereas the scene images have often been shot from a general shooting angle at a medium-to-long distance. Therefore, the angle between two arbitrary line segments, corresponding to a family of parallel lines in 3-D space, is constrained within a small interval. Furthermore, we know a priori that parallel lines are often similarly inclined in medium-to-long range scenes. For example, consider the building image in Fig. 2(a). We first compute the inclination angle of each line segment in the image; next, we construct a histogram of the inclined angles [see Fig. 2(b)]. The inclined angles of the line segments clearly concentrate within several subintervals of the histogram.

Fig. 2

Example showing the features of line segments. (a) Image with detected line segments. (b) Histogram of inclined angles of segments in the image.

3.3.

Preliminary Processing of the Initial Cluster

The input to our algorithm is a set of line segments $E$, which are obtained from the image ($I$) using a line segment detector (LSD). Each line segment ${\xi }_k\in E$ is represented by its two endpoints expressed as homogenous coordinates $[\begin{array}{cc}{\mathbf{p}}_{1k}& {\mathbf{p}}_{2k}\end{array}]$. From the input matrix, we can derive other attributes of ${\xi }_k$ such as the length (${\mathrm{len}}_k$) and inclined angle (${\theta }_k$). Among the many line segments typically contained in $E$, very short segments contribute little information for the VP detection. Therefore, line segments shorter than 5% of the image height are filtered from set $E$. Sequentially, outliers with anomalous inclined angles are also removed. To initialize the proposed algorithm, the set of remaining line segments is then partitioned into several groups. The preprocessing of set $E$ is detailed in the Secs. 3.3.1 and 3.3.2.

4.1.

Notation

A novel ABC algorithm called DCABC is presented in this section. For this purpose, we first define some essential symbols:

${\mathbf{l}}_k$ is the line passing along segment ${\xi }_k$, represented in homogeneous coordinate form.

$D$ is the maximum number of line classifications, determined by the number of valid angular domains.

${\mathrm{AL}}_d$ is a valid angular domain indexed by $d$ with $d=\mathrm{1,2},\dots ,D$.

${\mathbf{v}}_d$ is a VP initialized by the dth valid angular domain (${\mathrm{AL}}_d$).

$V=\{{\mathbf{v}}_d\in \mathfrak{R}|d=1,\dots ,D\}$ is the set of $D$ VPs, where ${\mathbf{v}}_d$ is a VP corresponding to ${\mathrm{AL}}_d$.

$C_d$ is a line cluster of segments closer to ${\mathbf{v}}_d$ than to any other VP in $V$.

${\mathbf{X}}_{\mathbf{i}}=(x_{i1},\dots ,x_{id},\dots ,x_{iD})$ is a binary vector of food source positions in the DCABC. If $x_{id}=1$, the corresponding ${\mathbf{v}}_d$ in $V$ has been selected as part of the solution proposed by ${\mathbf{X}}_{\mathbf{i}}$. If $x_{id}=0$, ${\mathbf{v}}_d$ is excluded from the solution.

${\mathbf{X}}_{\beta }$ is the position of the best current food source.

$V_i$ is a subset of VPs, represented by a position vector ${\mathbf{X}}_i$, such that $V_i=({\mathbf{v}}_d)\forall d:x_{id}=1$ with $V_i\subseteq V$.

$V_r$ is the set of VPs in $V$ that have not been selected by ${\mathbf{X}}_{\beta }$, such that $V_r=({\mathbf{v}}_d)\forall d:x_{\beta d}=0$ with $V_r\subseteq V$.

$d({\xi }_k,{\mathbf{v}}_d)$ denotes the distance between the VP ${\mathbf{v}}_d$ and the line segment ${\xi }_k$.

4.2.

Partition Strategy and Validity Index

Essentially, this paper regards the line classification step in the VP detection as a clustering procedure. The clustering process, which separates the objects into groups, is realized by unsupervised or supervised learning. In unsupervised clustering (also known as dynamic clustering), the number of classes need not be specified in the training data. In supervised clustering, the number of classes must be predetermined. Our algorithm belongs to the former category.

4.3.

Generating a New Partition

The ABC algorithm was initially designed for solving numerical optimization problems, which are continuous problems, and has proven successful at this task. However, the present line classification task is treated as a dynamic clustering problem with binary optimization. To adapt the basic ABC algorithm to dynamic clustering problems, we introduce two changes. First, as mentioned previously, the position (${\mathbf{X}}_i$) of a food source is represented as a binary vector indicating the selected clustering centroids. Second, when generating a new solution by Eq. (1), we substitute the “−” operator with a dissimilarity measure of the binary vectors. This substitution is inspired from the DisABC algorithm,¹⁶ but here we modify both the dissimilarity measure and solution reconstruction to ensure low complexity and fast convergence.

Before progressing further, we introduce some new notations. Suppose that ${\mathbf{X}}_i=(x_{i1},x_{i2},\dots ,x_{iD})$ and ${\mathbf{X}}_j=(x_{j1},x_{j2},\dots ,x_{jD})$ are binary vectors with $D$ dimensions. Let

Reshaping Eq. (1) as ${\mathbf{X}}_i^{\prime }{\mathbf{-}\mathbf{X}}_i={\phi }_i({\mathbf{X}}_i{\mathbf{-}\mathbf{X}}_k)$ and replacing the “−” operator by the Hamming distance between the two binary vectors, the new position is expressed as

In this work, we construct a new solution vector ${\mathbf{X}}_i^{\prime }$ that equalizes $H({\mathbf{X}}_i^{\prime },{\mathbf{X}}_i)$ and $T$. In other words, the new vector ${\mathbf{X}}_i^{\prime }$ contains $T$ bits whose values differ from those of the corresponding bits in ${\mathbf{X}}_i$. Therefore, ${\mathbf{X}}_i^{\prime }$ is obtained by flipping $T$ bits of ${\mathbf{X}}_i$ from 1 to 0, or from 0 to 1, employing problem-dependent heuristics to instruct the bit selection. Let us recap the problem of VPs detection.

As previously mentioned, a position vector ${\mathbf{X}}_i$ indicates the VPs selected from the set $V$, which partition the line segments into line clusters. Obviously, the more line segments in a line cluster, the better the VP estimation. Therefore, the number of line segments in each line cluster can be utilized as a heuristic for generating new solutions.

A component $x_{id}$ of a solution vector ${\mathbf{X}}_i=(x_{i1},x_{i2},\dots ,x_{iD})$ corresponds to a line cluster $C_{id}$, and the number of line segments in $C_{id}$ is denoted ${\mathrm{NL}}_{id}$. Therefore, if component $x_{id}$ is 0, $C_{id}$ will be an empty set and ${\mathrm{NL}}_{id}$ will also be 0. We collect the current solution ${\mathbf{X}}_i$ and its neighbor ${\mathbf{X}}_k$ into an index set $\mathrm{SI}=S_{\mathrm{Index}}({\mathbf{X}}_i,{\mathbf{X}}_k)$, and create two additional sets ${\mathrm{NLS}}_i$ and ${\mathrm{NLS}}_k$ that record the number of line segments in the line clusters indexed by the elements in SI. Specifically, for each index $d$ in SI, if $x_{id}$ equals 1, ${\mathrm{NL}}_{id}$ is added to the set ${\mathrm{NLS}}_i$; otherwise, ${\mathrm{NL}}_{kd}$ is added to the set ${\mathrm{NLS}}_k$.

The new solution vector ${\mathbf{X}}_i^{\prime }$ can be simply constructed from the obtained $T$, ${\mathrm{NLS}}_i$, and ${\mathrm{NLS}}_k$. The candidate solution ${\mathbf{X}}_i^{\prime }$ is initialized with a copy of ${\mathbf{X}}_i$ and is computed in three steps: (1) select the bit within ${\mathbf{X}}_i^{\prime }$ for which the number of line segments of the corresponding cluster is minimized in ${\mathrm{NLS}}_i$ and switch it from 1 to 0; (2) select the bit within ${\mathbf{X}}_i^{\prime }$ for which the number of line segments of the corresponding cluster is minimized in ${\mathrm{NLS}}_k$ and switch it from 0 to 1; (3) delete the minimal value of ${\mathrm{NLS}}_i$ and the maximal value of ${\mathrm{NLS}}_k$. These three steps are repeated until $T$ bits are flipped.

4.4.

Estimating a Vanishing Point for Segment Clustering

Once the line segments have been grouped into line clusters based on their estimated VPs, we refine the related VP locations for each line cluster $C_d$. To this end, we compute the point in the image plane that minimizes the sum of the distances to the lines sharing a common VP. Using the definition of the distance between a VP and a line segment [Eq. (7)], we estimate the VP ${\widehat{\mathbf{v}}}_d$ of line cluster $C_d$ as

In practice, Eq. (13) is solved by a least-squares algorithm.

4.5.

Description of the Dynamic Clustering Artificial Bee Colony Algorithm

Based on the above analysis, the DCABC algorithm flow is presented in Fig. 3. The main steps of the algorithm include the following stages.

Fig. 3

Dynamic clustering artificial bee colony (DCABC) algorithm flowchart.

Fig. 4

Subflowchart of initialization for the DCABC algorithm.

Fig. 5

Subflowchart of the searching procedure for an employed (or onlooker) bee.

Fig. 6

Subflowchart for reconstructing vanishing point (VP) set.

In Stage 1, certain parameters have to be preset for the DCABC algorithm. Generally, onlooker bees form 50% of the colony, employed bees form 50%, and the number of scout bees is, at most, one for each cycle. Here, the number of onlooker bees is selected to be equal to the number of employed bees so that the algorithm has fewer controlling parameters. According to previous research,²¹ as the colony size increases, the algorithm produces better results. However, after a sufficient colony size is achieved, any further size increase does not improve the algorithm performance significantly. Here, the colony size is empirically set to 30 at Stage 1. The control parameter “limit” determines the “scout bee” production (see Sec. 2.2). The “limit” value is inversely proportional to the scout production frequency; an increase in the number of scouts encourages exploration, whereas increasing the onlookers on one food source encourages its exploitation. A “limit” value of 60 is considered appropriate in the present study, representing a quarter of the product of the colony size with the dimensions of the problem. Criteria 1 and 2 determine the termination conditions for the two cycles, where both are based on the maximum number of iterations, and two variables ($t_1$,$t_2$) serve as the counters. Here, the upper limits of $t_1$ and $t_2$ are empirically set to 3 and 35, respectively.