2
of structured environments [20,27], which require real-
time operation while accurate and meaningful line seg-
ment detections.
2 Related work
Most approaches in the related lit erature use edges ex-
tracted at pixel level from the images as basic infor-
mation. The Sobel edge detector [16] is typically used
as an ap proximation to the first order spatial deriva-
tives I
x
(x, y) and I
y
(x, y). For each pixel i at location
(x
k
, y
k
) the module and orientation of the gradient can
also be estimated as described in [10].
Once obtained, the information of edges at pixel
level can be used in different ways to search for line
segments. Two main groups of techniques can be identi-
fied: those based on accumulation in parametric spaces,
such as methods based on the H ough transform (HT)
[1,3,10,12,17,19,31]; and pixel clustering strategies in
the image plane [6,14,15,18 ].
2.1 Hough transform
The former group basically perform s a parametric trans-
formation to the set of edge pixels, from which lines are
extracted searching for local maxima in the transform
domain. Note that the Standard HT (SHT) detects
lines, but not line segments, which require ad dressing
additional considerations for their detection, as done
in [18,35]. Some oth er works just face the problem of
finding lines, as done by [31,34,19] or recently Aggarwal
with the Regularized HT [1].
The major drawback of the works ba sed on the HT
is the excessive algorithm complexity [31,10], which
avoids its use on online applications.
Random sampling applied to the HT has been orig-
inally proposed by Xu et al. [34], and further improved
by Kiryati et al. [19] to render efficient line segment de-
tectors. A pair of edge points is selected at random to
accumulate a single vote on the transformed domain.
These approaches are the so-called “many-to-one” vot-
ing schemes, in contrast to the “o ne-to-many” corre-
sponding to th e standard HT, which dramatically en-
hances the speediness of the HT. Several variants of
the RHT have been proposed by K¨alvi¨ainen et al. [17],
which improve the sa mpling distribution by means of
a two-steps random process. W indows of fixed or also
random size are randomly selected in the image, and
the RHT is then applied to search for maxima. Walsh
and Raftery [32] proposed an importance sampling pro-
cedure to improve the random sampling used within the
RHT.
The resulting line segments can be further grouped
into longer ones as done by Banderas et al. [3], which
uses Mean Shift procedures to cluster line segments in
the transform domain and obtain a single representative
for each cluster.
Nevertheless, the main problem of these approaches
is that they achieve fast results at the cost of reducing
their accuracy, giving a large number of false negatives
(missdetections due to the termination criteria), espe-
cially in very fast detectors as the PPHT (Progressive
Probabilistic HT) by Matas et al. [12]. Besides, they
require a large set of application-dependant threshold
values to be tuned to obtain adequate results. As fi-
nal remark, the need of such a number of user-defined
thresholds in this type of approaches reduces its ap-
plicability to unsupervised systems as well as making
them more prone to errors.
2.2 Pixel clustering
This group first cl uster sets of conne cted pixels in a
coarse manner according to some common property (e.g.
their orientation) and afterwards compute an estimate
for each set. The work by Burns et al. [6] has been used
as reference by further authors [18,14]. Besides, the use
of connected component analysis (CCA) was first intro-
duced in this context by Nevatia and Babu [26] and fol-
lowed by other authors [18,20]. Analogously, Yuen [35]
proposes a connected version of the HT, which selects at
random an edge pixel and then apply a one-dimensional
accumulation on the an gle pa rameter.
In this field, some of the works exploit the infor-
mation contained in the eigenvalues and vectors of the
image tensor matrix [33], as done by many others [15,
18,20]. Typically, the straightness of the group of pixels
is measured as a function on the eigenvalues (λ
1
, λ
2
).
However, it is not straightforward to classify a pixel,
given its ei genvalues, into these three categories. As
mentioned by Rosten et al [29], many authors have
created unbounded functions that evaluate the “cor-
nerness” of pixels by the computatio n of λ
2
/λ
1
, λ
2
, or
approximations to the relationship b etween eigenvalues
that skip their computation using directly the elements
of the tensor matrix, such as the well known Harris
corner function.
3 Approach overview
The proposed strategy shares some properties with meth-
ods of the two abovementioned groups, although it can
not be classified as belonging to any of them. On the one
hand, it uses a sequential sampling strategy, which is an
