没有合适的资源？快使用搜索试试~ 我知道了~

# Line segment detection using weighted Mean Shift procedures on a

需积分: 5 0 下载量 99 浏览量
2024-08-09
13:19:35
上传
评论
收藏 5.68MB PDF 举报

温馨提示

线检测

资源推荐

资源详情

资源评论

See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/220654859

Line segment detection using weighted mean shift procedures on a 2D slice

sampling strategy

Article in Pattern Analysis and Applications · May 2011

DOI: 10.1007/s10044-011-0211-4 · Source: DBLP

CITATIONS

38

READS

2,793

4 authors, including:

M

arcos Nieto

V

icomtech

102 PUBLICATIONS 1,391 CITATIONS

SEE PROFILE

C

arlos Cuevas

U

niversidad Politécnica de Madrid

52 PUBLICATIONS 736 CITATIONS

SEE PROFILE

L

uis Salgado

U

niversidad Politécnica de Madrid

135 PUBLICATIONS 1,964 CITATIONS

SEE PROFILE

All content following this page was uploaded by Marcos Nieto on 25 January 2016.

The user has requested enhancement of the downloaded file.

Noname manuscript No.

(will be inserted by the editor)

Line segment detection using weighted Mean Shift

procedures on a 2D Slice sampling strategy

Marcos Nieto · Carlos Cuevas · Luis Salgado · Narciso Garc´ıa

Received: date / Accepted: date

Abstract A new approach towards accurate line seg-

ment detection in images is introduced in this paper for

its application in real-time computer vision systems. It

has been designed to work unsupervised without any

prior knowledge of the imaged scene, hence it does not

require to tune input parameters. Although many works

have been presented about this topic, as far as we know,

none of them achieves a trade-oﬀ between accuracy and

speed as our strategy does. The reduction of the compu-

tational cost compared to other fast methods is based

on a very eﬃcient sampling strategy that sequentially

proposes points on the image that likely belo ng to line

segments. Then, a fast line growing algorithm is applied

based on the Bresenham algorithm, which is combined

with a modiﬁed version of the Mean Shift algorithm

to provide accurate line segments while being robust

against noise. The perfor mance of this strategy is te sted

for a wide variety of images, com paring its results with

popular state of the art line segment de tection meth-

ods. The results show that our proposal outperforms

these works considering simultaneously accuracy in the

results and processing speed.

Keywords line segment · eigenvalues · real-time ·

slice sampling · Mean Shift · Bresenham algorithm

1 Introduction

Straight lines or line segments within an imaged scene

can be of great help to infer its geometric properties

Marcos Nieto, Carlos Cuevas, Luis Salgado, and Narciso Garc´ıa

Grupo de Tratamiento de Im´agenes

Universidad Polit´ecnica de Madrid

E28040 - Madrid, Spain

E-mail: {mnd, ccr, L.Salgado, narciso}@gti.ssr.upm.es

and also the projection process that converts 3D world

elements into a 2D image. Man-made environments typ-

ically contain multiple line segments oriented towards

a number of common directions (belonging to ﬂat su r-

faces such as the gro und, doors, walls, or buildings). For

that re ason, line segments can be used as low level fea-

tures for conventional computer vision problems, such

as the detection of vanishing points [2,20], autocalibra-

tion [28], plane rectiﬁcation techniques [21, 23], 3D re-

construction [22] or object tracking [30].

This paper models the problem of ﬁnding line seg-

ments in real images in a probabilistic way. An image is

considered as a set of observations I = {(x

k

, y

k

)}

k=1...N

coming from a subjacent probability density function

p(x, y) that represents the probability of a pixel to be-

long to a line segm ent. One of the main contributions

of the paper is on the generation of an estimate ˆp(x, y)

of this likelihood distribution from the analysis of the

eigenvalues of the tensor matrix associated to the im-

age pixels. Besides, the real-time performance of the

proposed strategy is achieved by the use of a sequential

sampling technique that selects pixels in the image that

likely belong to line segments according to ˆp(x, y). Line

segments are obtained through the Bresenham grow-

ing algor ithm enhanced with the use of weighted Mean

Shift (wMS) procedures tha t provides accurate ﬁts and

robustness against noise.

The target of our method is the obtention of line

segments in any kind of real images. Therefore, the re-

sults section evaluates the obtained line segments for a

wide variety of real images. Nevertheless, since one of

the major feats of our approach is its low computational

cost, its performan ce is better exploited for vision ap-

plications working on sequences of images. For ins tance,

camera autocalibration strategies base d on the compu-

tation of vanishing points in moving camera sequences

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 ﬁrst 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 diﬀerent ways to search for line

segments. Two main groups of techniques can be identi-

ﬁed: 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

ﬁnding 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 eﬃcient 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 ﬁxed 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 ﬁ-

nal remark, the need of such a number of user-deﬁned

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 ﬁrst 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 ﬁrst 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 ﬁeld, 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 classiﬁed as belonging to any of them. On the one

hand, it uses a sequential sampling strategy, which is an

3

Sobel and

Eigendecomposition

Computation of (μ

1

,μ

2

)

and μ

Get sample p(x,y) > μ

(jump)

Terminate?

End

Slice sampler 2D

Visited?

Point refinement

(wMS)

Iterative line growing

(Bresenham + wMS)

Update visited

Sequential samplingOperations at pixel level

Line segment generation

p(x,y)

Image

z

k

YES

NO

z

k+1

YES

NO

x

k+1

^

^

Fig. 1 Flow chart of the proposed strategy. The im age is processed in order to obtain the likelihood distribution ˆp(x, y) deﬁned by

the parameters (µ

1

, µ

2

). The mea n value of ˆp(x, y), µ, is used to generate the ﬁrst sample of the algorithm and start runn ing th e slice

sampler, which sequentially generates samples, z

k

. The last stage is the line segment generation, in which the samples are reﬁned and

used as starting point for the iterative line growing algorithm that ﬁnally generates the line segment.

improved version of random sampling approaches based

on the HT. On the other hand, it exploits the eigen-

values and vectors information as also done by some

pixel clustering methods, although in a novel way by

the computation of the likelihood function ˆp(x, y).

The ﬂow chart of the proposed method (which will

be denoted as SSWMS, Slice Sampling Weighted Mean

Shift), is depicted in Fig. 1. As shown, it is composed

of three main stage s: the computation of the likelihood

function, the sequential sampling and the line segment

generation.

The ﬁrst step estimates the likelihood distribution

over the image I such that ˆp(x, y) is the likelihood value

of a pixel (x, y) to b elong to a line segment. This dis tri-

bution is parameterized by (µ

1

, µ

2

), which are statistics

automatically obta ined from the im age. The distribu-

tion is deﬁned using the image tensor matrix, and their

corresponding eigenvalues. This process is guided by

the idea that pixels that belong to line segments must

satisfy two criteria: (i) they have signiﬁcant gradient

magnitude; and (ii) there is only one dominant direc-

tion in their neighborhoods. These concep ts and the

associated methods are described in detail in fur ther

sections.

The sequential sampling, which is based on the slice

sampling algorithm [4,25], sequentially selects pixels in

the image, denoted as z

k

= (x

k

, y

k

), that are good can-

didates to belong to line segments, according to the

computed likeliho od ˆp(z

k

). The design of this stage en-

sures that no repeated samples are selected, so that

z

k

6= z

c

∀c < k. If the slice sampler proposes a sample

z

k

that has been already visite d by the algorithm, the

next sample is selected randomly satisfying ˆp(x, y) > µ,

where µ is the mean value of ˆp(x, y) computed for all

the pixels of the image.

Given a candidate pixel proposed by the sampling

technique, the process arrives to the line segment gener-

ation stage. It starts with the point reﬁnement module,

which uses Mean Shift (MS) procedures on a multidi-

mensional space composed of the position of the pix-

els and their dominant local orientation, denoted as

x

k

= (x

k

, y

k

, θ

k

)

1

. The MS searches for a local maxima

on this space, i.e., it looks for the pixel in the neighbor-

hood of the candidate pixel that most likely belongs to

a line segment.

From th is local maxima, an eﬃcient line growing

strategy, based on the Bresenham algorithm is applied

to connect pixels until the end points of the line seg-

ment are reached. This scheme is ap plied iteratively to

enhance the accuracy of the gene rated line segments.

All the pixels swept by the generated line segment are

marked as visited, and thus not available to be selected

anymore during the sequential samplin g stage.

The overall result of the strategy is that the se-

quential selection of candidates with the slice sampler

is much m ore eﬃcient than pro cessing the whole im-

age in search for line segments (as done by mos t works

based on pixel clust ering techniques), and even than

randomly selecting points on the image without any

guiding criteria (as the works about random sampling

on th e Ho ugh domain). On the other hand, the accu-

racy on the line segment ﬁtting process is provided by

the MS procedure that is used to reﬁne the candidates

and generate good starting and ending points for the

growing algori thm.

1

For the sake of clarity in the notation, italic characters cor-

respond to scalar values while bold characters represent arrays.

剩余15页未读，继续阅读

资源评论

柠檬0711

- 粉丝: 54
- 资源: 9

上传资源 快速赚钱

- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助

安全验证

文档复制为VIP权益，开通VIP直接复制

信息提交成功