See discussions, stats, and author profiles for this publication at: [Link]

net/publication/258918208

An Extended Line Tracking Algorithm

Conference Paper · November 2013

DOI: 10.1109/ROPEC.2013.6702752

CITATIONS READS
8 806

3 authors:

Leonardo Romero Moises Garcia

Universidad Michoacana de San Nicolás de Hidalgo Universidad Michoacana de San Nicolás de Hidalgo
43 PUBLICATIONS 186 CITATIONS 26 PUBLICATIONS 70 CITATIONS

SEE PROFILE SEE PROFILE

Carlos Lara-Alvarez
Centro de Investigación en Matemáticas (CIMAT)
63 PUBLICATIONS 250 CITATIONS

SEE PROFILE

All content following this page was uploaded by Carlos Lara-Alvarez on 21 June 2019.

The user has requested enhancement of the downloaded file.

 An Extended Line Tracking Algorithm
Leonardo Romero Muñoz Moises Garcı́a Villanueva Carlos Alberto Lara Álvarez
Facultad de Ingenierı́a Eléctrica Facultad de Ingenierı́a Eléctrica CINVESTAV, IPN
UMSNH UMSNH Guadalajara, Jal., Mexico
Morelia, Mich., Mexico Morelia, Mich., Mexico Email: carlos lara24@[Link]
Email: lromero@[Link] Email: moises@[Link]

Abstract—This paper introduces an extension of the classical

Line Tracking Algorithm to solve the problem of fitting multiple
straight–lines to a sequence of 2D points. We also analyze the
performance of the extended algorithm to solve a classical prob-
lem in robotics: finding a map of lines from laser measurements;
(a) Big uncertainty, 1 line (b) Low uncertainty, 2 lines
tests show that the extended algorithm obtains reliable models.
Fig. 2. Line models considering different uncertainty.
I. I NTRODUCTION
Let Z = (z1 , . . . , zN ) be a sequence of N measurements
or points where each point zi = hxi , yi i is represented by to other sensors: they are accurate, have a high sampling rate,
its rectangular coordinates; the multiple lines fitting problem and range measurements are easier to interpret than images
consists of finding the set of lines Θ = {θ1 , . . . , θM } that from cameras, for example. Laser data are usually a sequence
best represents Z; To find Θ, we need to discover the number of points R = (hρ1 , φ1 i , . . . , hρN , φN i) where hρi , φi i are the
of lines, M , and the parameters of each line. The multiple polar coordinates of the i-th scan point, where the location of
lines fitting problem occurs in several fields of science and the sensor is the origin of this polar coordinate system. The
engineering; for instance, a mobile robot can build a line laser, using a fixed angular resolution, acquires points in an
map using data sensed from an indoor environment and use ordered sequence, starting at direction φmin and stopping at
it to navigate. In man-made environments (both indoors and φmax (0◦ and 180◦ for the SICK LMS209–S02).
outdoors), planar surfaces are very common and they are This paper develops an extended version of the Line Track-
typically modeled by line segments. Some examples include ing (ELT) Algorithm that improves the accuracy of the lines
corridor or room walls, doors, tables, etc. as well as merging similar lines into a single line. The rest of
Finding the best set of lines is sometimes hard; Figure 1 the paper is organized as follows: Section II briefly reviews
shows a set of points and four hypothetical line sets with 1, existing line extraction methods, specially the Line Tracking
2, 3 and 5 lines, respectively. If the sum of square distance (LT) Method. Section III presents the extensions to the LT
from each point to the associated line is used to decide which Method. Experimental results are presented in Section IV.
model is the best, then the five–lines model shown in Figure 1e Finally, Section V presents the main conclusions of this work.
is chosen because the total error is zero. This case illustrates
II. L INE EXTRACTION ALGORITHMS
the over fitting problem where a very complex model has an
error close to zero, but it is not generally useful. Often simple This section is based in the revision of existing line extrac-
models are preferable than complex models. tion algorithms given in [6]. Probably, the most straightforward
example of a line extractor is the Successive Edge Following
(SEF) algorithm [9]. Briefly, it considers that a new line
begins when the distance between two consecutive scan points
exceeds a certain threshold.
(a) Points Z (b) 1 line (c) 2 lines (d) 3 lines (e) 5 lines
Another algorithm that it is remarkable not only for being
Fig. 1. A data set Z and some hypothetical models to represent it. uncomplicated but also for its reduced time complexity is the
Line Tracking (LT) algorithm [3], also known as Incremental.
The accuracy of the measurements is another factor that Basically, it starts off by building a line model which passes
must be considered when selecting the best model Θ. Figure through the first and second scan points, successively adding
2 represents the uncertainty with circles; a single line model is a new scan point if a line criterion is validated. Otherwise,
preferable when the uncertainty is big (Fig 2a), and the two– the line is terminated and a new one is started, repeating the
lines model is selected when the uncertainty is small (Fig 2b). algorithm until the end of the dataset is reached.
This work focuses on finding lines form laser data, the Unlike the two previous methods, the Iterative End Point
resulting set of lines can be used for indoor and structured out- Fit algorithm (IEPF) [5] is recursive. It begins by constructing
door applications. Lasers have several advantages with respect a line using the first and last scan points. Next, it finds the

978-1-4799-2370-0/13/$31.00 ©2013 IEEE

most distant point pk from the line, and if it is far enough,
two subsets are created taking pk as the splitting point. This
procedure is repeated recursively for all the subsets until the
validation criterion fails.
The Split & Merge (S&M) algorithm [8] is twofold. Its first
phase (split) is similar to the IEPF method. Nevertheless, it
differs from it in that it adds another phase (merge) in which
collinear segments are fused together if the angle between
them is sufficiently small.
In contrast to the previously discussed methods, the RAN-
dom SAmple Consensus (RANSAC) algorithm [2] makes use
of a probabilistic approach, and it robustly fits models in
the presence of data outliers. Firstly, it constructs a line R
using two randomly chosen points from the initial point set.
Fig. 3. Line parameters in the polar form.
Secondly, a consensus set is created, formed by line inliers,
and if it is big enough, the line R is readjusted to the points
included in the consensus set. Otherwise, the algorithm is
where rj and φj are the length and the angle of inclination
repeated until a proper consensus set is found or the maximum
of the normal, respectively. As shown in Figure 3, the normal
number of loop iterations is reached.
is the shortest segment between the line and the origin of a
Another robust method to find lines is the Hough Transform
given coordinate frame. Points z = hx, yi that are on the line
(HT) [4]. The basic theory of the HT is that any point could
θj = hrj , φj i satisfy rj = x cos φj + y sin φj .
be part of some set of possible lines. If we parameterize each
The orthogonal distance from a point zi = hxi , yi i to the
line by its polar coordinates hr, φi, a point is transformed to a
line θj is given by
locus of points in the hr, φi plane corresponding to all the lines
passing though that point. If the plane hr, φi is discretized and d⊥ (zi , θj ) = rj − xi cos φj − yi sin φj . (2)
the contributions of each point are added to the plane hr, φi,
then lines that appear in the set of points will appear as local This equation can be easily derived by considering the line
maxima in the plane hr, φi. In [6], a method named REHOLT ri = xi cos φi + yi sin φi ; such line passes through the point
(Reduced Hough transform Line Tracker) is developed for zi and is parallel to line θj when φi = φj ; Therefore,
detecting lines. It is a technique that combines the speed of the d⊥ (zi , θj ) = rj − ri .
LT algorithm and the robustness of the HT. Using a reduced Under the assumption of the same known normal uncer-
HT, lines are more precisely fitted to their corresponding set tainty in directions x and y, the best line θ with parameters
of points, since the HT is based on a robust voting strategy. hr, φi minimizes the sum of squared perpendicular distances
A main disadvantage of SEF, LT, IEPF and S&M is that they from the points to the line. From n points hxi , yi i (i =
fit lines to a set of points using fast but non-robust methods, 1, . . . , n), it can be shown that the solution is given by [1]
such as least squares for example, which is known to have   " #
problems with outliers [2]. On the other hand, RANSAC is r x cos φ + y sin φ
= 1 −2sxy (3)
a robust method, but its processing time and results are not φ 2 arctan syy −sxx
always the same, because it is a nondeterministic algorithm.
The HT is also a robust method, but it takes a significant Where
amount of processing time and the precision of the results n n
1X 1X
depend of the discretization of the plane hr, φi. x= xi , y= yi ,
n i=1 n i=1
n n
A. The Line Tracking Algorithm X X
sxx = (xi − x)2 , syy = (yi − y)2 ,
The LT algorithm is remarkable not only for being simple i=1 i=1
but also because it is very fast. The method is based on n
X
computing a line θ that fits the last n − 1 points. Then, a sxy = (xi − x)(yi − y).
distance d(zn , θ) from the point zn to line θ is computed. If i=1

the distance is greater than a fixed threshold value Tmax , a The Line Tracking algorithm is presented in Algorithm 1
new line is started. Otherwise, a new line is computed with and it computes the set of lines as well as the indexes of the
all points, including zn . The algorithm starts joining the first points that form each line.
two points with a line.
A line is represented by its normal form, III. A N EXTENDED L INE T RACKING A LGORITHM
After using the LT algorithm, we add two steps: a Back-
θj = hrj , φj i (1) tracking Step and a Merge Step.
Algorithm 1 Line Tracking Algorithm Algorithm 2 Backtracking Algorithm
INPUT: Z, a sequence of points (z1 , . . . , zN ) and Tmax INPUT: Z (z1 , . . . , zN ), Tmax , Θ (θ1 , . . . , θM ) and I
OUTPUT: Θ, a sequence of lines (θ1 , . . . , θM ) and I, a OUTPUT: Θ and I
sequence of indexes for Θ for i = 1, . . . , M − 1 do
hs1 , e1 i ← I(i) // indexes of line θi
i ← 1, j ← 1, l ← 1, Θ ← (), I ← () hs2 , e2 i ← I(i + 1) // indexes of line θi+1
while j < N − 2 do repeat
θl ← best line that fits (zi , . . . , zj+1 ) // (eq. 3) d2 ← d(ze1 , θi+1 )
T ← d(zj+2 , θl ) // (eq. 2) if e1 − s1 + 1 > 2 then
0
if T > Tmax then θi ← best line that fits (zs1 , . . . , ze1 −1 )
0 0
Add θl to Θ d1 ← d(ze1 , θi ) // θi does not include ze1
Add hi, j + 1i to I // indexes of the line θl else
l ←l+1 d1 = Tmax
i←j+2 end if
j←i if d2 < d1 then
else e1 ← e1 − 1, s2 ← s2 − 1 // adjust indexes
j ←j+1 Update indexes of lines θi and θi+1 in I
end if recompute lines θi and θi+1 and update Θ
end while else
return Θ and I break repeat
end if
until s1 = e1
end for
Delete from Θ and I, lines with no points
return Θ and I

B. A Merge Step
After the Backtracking Step, a Merge Step is executed. The
Fig. 4. LT does not estimate accurately line parameters.
idea is to merge two sets of points if every point has a distance
to the new line (computed using both sets of points) less than
or equal to Tmax . In this way, two o more sets of points can
A. A Backtracking Step
be represented by using a single line.
When the LT algorithm is adding new points to a line, it is Algorithm 3 implements this step, where the outputs of
possible that some of the final points (before reach the Tmax Algorithm 2 and the inputs of Algorithm 1 are the inputs for
value) belong to the next line. This situation is shown in Figure this algorithm. The search in the algorithm can be exhaustive
4, where there are two lines (one horizontal and one vertical), or reduced to data sets with similar line parameters. With the
but the horizontal line includes vertical points, so it is slightly Merge step, we obtain a better feature model and also avoid
pull up by these points. The backtracking step reviews if it is the over-fitting problem.
better to associate the last points of a line θl to line θl+1 and
it considers two cases: IV. E XPERIMENTAL R ESULTS
1) The line θl has 3 or more points. In this case, the To show how the Backtracking and Backtracking + Merge
last point is associated to the closest line: θl or θl+1 . algorithms are working, we use a synthetic data set and a real
If the point is associated to θl+1 , the line θl+1 is laser scan (361 measurements from 0◦ to 180◦ for the SICK
recomputed with the new point. This step is repeated LMS209-S02 ).
until an endpoint belongs to line θl . In this way, this step Figure 5 shows the result of the LT algorithm for the
removes the wrong associations of the LT algorithm. synthetic data. Note how two lines, the horizontal line (at
2) The line θl has 2 points. In this case, if the distance the bottom right part of the figure) and a vertical line (at
from the second point of θl to line θl+1 is less than or the top right part of the figure) are not accurately computed,
equal to Tmax , that point is associated to line θl+1 . In because they include point from the next line. Figure 6 shows
that case, the same revision is executed with the first the result of the Backtracking algorithm. Now both lines are
point of θl . At the end, the line θl can be two, one or horizontal and vertical and also there are three single points.
zero points. We can consider these points as outliers because they are far
The Backtracking algorithm is shown in Algorithm 2, where away from any line segment. Figure 7 shows the result of the
the outputs of Algorithm 1 are the inputs of Algorithm 2. Backtracking and the Merge algorithm. There are only three
Algorithm 3 Merge Algorithm
INPUT: Z (z1 , . . . , zN ), Tmax , Θ (θ1 , . . . , θM ) and I
OUTPUT: Θ and D (a set of set of points)
Compute D = {D1 , . . . , DM }, where Di is the set of points
of line θi
loop
Search the pair Da , Db ∈ D | Da 6= Db , where a single
line can represent both sets (given Tmax )
if (successful search) then
Da ← Da ∪ Db
D ← D \ {Db } // delete Db from D
M ←M −1
else
break loop Fig. 6. LT + Backtracking algorithm with synthetic data.
end if
end loop
Recompute line parameters Θ from D
return Θ and D

Fig. 7. LT + Backtracking and Merge algorithms with synthetic data.

Fig. 5. LT algorithm with synthetic data.

lines, because the other 3 lines are reduced to single points.

The results from the Backtracking algorithm are similar to the
REHOLT method [6] without using the Hough Transform.
Figures 8, 9 and 10 show the result of the application of
LT, LT + Backtracking and LT + Backtracking and Merge
algorithms (with Tmax = 6cm) to a laser scan. To avoid
spurious lines, only lines with 5 o more points are considered.
Results are similar to the case of synthetic data.
Figure 11 shows the result of the application of the Fig. 8. LT algorithm with a laser scan
RANSAC algorithm to the same laser scan (also with Tmax =
6cm and lines with 5 o more points). In this case, Tmax is the
maximum distance from a point to the line, to consider the is mainly because LT and LT-BT-M algorithms are based on
point as an inlier. In this case the RANSAC algorithm made deterministic methods and especially, they take advantage of
500 iterations to get a line; then its inliers are removed from the sequence of points of the laser scan. A comprehensive ex-
the data set, and the algorithm is applied to the reduced data perimental evaluation of line extraction algorithms (including
set to get new lines. Results from RANSAC and the extended LT, RANSAC, Hough, and S&M) using 2D laser rangefinder
LT algorithm are very similar. for indoor mobile robotics is shown in [7]. They report a speed
Table I shows the time required by each algorithm. The of 344 Hz for the LT algorithm against 29 Hz for RANSAC,
Line Tracking (LT) and the Line Tracking + Backtracking with a better behavior of LT. RANSAC is much slower than
and Merge (LT-BT-M) are much faster than RANSAC. This the LT.
 TABLE I
S PEED AND LINES FOUND UNDER COMMON PARAMETERS .

Algorithm Time (ms) Lines found

LT 30 15
LT-BT-M 49 8
RANSAC 1027 8

used in the Line Tracking algorithm.

This Extended Line Tracking algorithm is simple, accurate
and fast, allowing the algorithm to be used for real-time line
extraction. If lines are accurately determined, then the robot
has better features of the environment.
Fig. 9. LT + Backtracking algorithm with a laser scan
R EFERENCES
[1] Kai Oliver Arras and Roland Y. Siegwart. Feature extraction and scene
interpretation for map-based navigation and map building. In Proc. of
SPIE, Mobile Robotics XII, pages 42–53, 1997.
[2] Robert C. Bolles and Martin A. Fischler. A RANSAC-based approach
to model fitting and its application to finding cylinders in range data. In
IJCAI, pages 637–643, 1981.
[3] G.A. Borges and M.-J. Aldon. Line extraction in 2d range images for
mobile robotics. Journal of Intelligent and Robotic Systems, 40:267–297,
2004.
[4] R. O. Duda and P. E. Hart. Use of the hough transformation to detec lines
and curves in pictures. Communications of the Association for Computing
Machinery, 15:11–15, 1972.
[5] R. O. Duda and P. E. Hart. Pattern classification and scene analysis.
Wiley New York, 1973.
[6] Carlos Fernandez, Vidal Moreno, Belen Curto, and J. Andres Vicente.
Clustering and line detection in laser range measurements. Robotics and
Autonomous Systems, 40:720–726, 2010.
Fig. 10. LT + Backtracking and Merge algorithms with a laser scan [7] Viet Nguyen, Stefan Gächter, Agostino Martinelli, Nicola Tomatis, and
Roland Siegwart. A Comparison of Line Extraction Algorithms using 2D
Range Data for Indoor Mobile Robotics. Autonomous Robots, 23(2):97–
111, August 2007.
[8] T. Pavlidis and S.L. Horowitz. Segmentation of plane curves. IEEE
Transactions on Computers, 23:860–970, 1974.
[9] A. Siadat, A. Kaske, S. Klausmann, M. Dufaut, and R. Husson. An
optimized segmentation method for a 2d laser-scanner applied to mobile
robot navigation. In 3rd IFAC Symposium on Intelligent Components and
Instruments for Control Applications, pages 153–158, 1997.

Fig. 11. RANSAC algorithm with a laser scan

V. C ONCLUSIONS AND F UTURE W ORK

We have presented an Extended Line Tracking algorithm
to find lines given a sequence of points. This method adds
a Backtracking step and a Merge step to the standard Line
Tracking algorithm. The Backtracking step tries to remove
wrong associations of points from adjacent lines and the Merge
step decide between merging set of points (associated to lines)
or not. To merge two set of points, it uses the same criterion

View publication stats