Point Cloud Segmentation Using Gradient Vector Flow Snake
Shoubin Liu and Yingsong Ye
Abstract—This paper presents a new method for extracting
point cloud of useful main surface from 3D point cloud of an
existing product or part. The 3D point cloud is sliced into 2D
point cloud at different slices. For each slice, gradient vector
flow (GVF) is generated. An active contour or snake is applied
to capture the point cloud belonging to main surface. Points
belonging to mini-structures or mini-features are repaired.
Experimental results demonstrate the robustness and the
effectiveness of the proposed algorithm.
I. INTRODUCTION
t is an important way to create an innovative design by
reverse engineering of an existing product or part. Some
3D digitizing equipment, such as a 3D laser scanner or a CT
scanner can generate a huge amount of point cloud data.
Conventional method of manually processing or editing
point cloud data is a time consuming job. To develop
effective and robust computer-aided techniques for point
cloud segmentation is an important topic in reverse
engineering.
The existing methods for point cloud segmentation can be
categorized into edge-based approaches and region-based
approaches. Edge-based approaches identify discontinued
points and further infer individual surface regions of point
cloud. Crease edges or smooth edges identified with
discontinuities in surface normals or curvatures are
commonly used [1]-[2]. Region-based approaches group
points with similarity into surface regions with edges being
derived by intersection or further computations from surfaces.
Clustering and region-growing are some typical techniques
[3]-[4].
Edge-based approaches or region-based approaches
mentioned above are usually applied to the point cloud with
single topology. However, some point clouds, such as those
from CT-scanning or 3D laser scanning of parts with many
mini-structures are of multi-topology. The point cloud with
multi-topology
can be named as complex point cloud. The
first work for complex point cloud segmentation is intended
to identify and extract the point cloud of main surface with
single topology.
This paper presents a new approach using GVF snake for
complex point cloud segmentation. In section 2, the
background regarding GVF snake and its model is described.
Manuscript received November 16, 2010. This work was supported by
the national natural science foundation of China under grant 60873141.
Shoubin Liu is with Shenzhen Graduate School, Harbin Institute of
Technology, Shenzhen 518055, P.R. China. (phone: 86-755-26033516; fax:
86-755-26033774; e-mail: mesbliu@hitsz.edu.cn).
Yingsong Ye is with Shenzhen Graduate School, Harbin Institute of
Technology, Shenzhen 518055, P.R. China. (e-mail: yingsongye@163.com)
In section 3, parameters for controlling GVF snake
performance are discussed. Experimental results are
demonstrated in section 4. The final conclusions are
summarized in section 5.
II. B
ACKGROUND
A. Traditional Snake Model
Traditional snake model was first introduced by Kass et al.
in 1987 [5]. A traditional snake is a curve
(), [0,1]ls s∈
moving over a 2D grey-level image
(, )
xy
to minimize its
energy
1
22
2
'"
0
1
( [ () ()] (()) )
2
snake
ls ls Ils ds
αβ κ
=+−∇
∫
.(1)
where
()ls
is the parametric curve or snake,
(, )
xy
is the
grey-level image function, and
,,
α
κ
are three positive
constants and represent three weighting parameters. The first
term represents the strain energy of the curve. The second
term represents the bend energy of the curve. These two
terms also smooth the curve. The third term attracts the curve
to edges of image
(, )
xy
.
To minimize
nake
E
, calculus of variation is employed and
the dynamics equation of the curve is given by
2
'' ''"
() () () (())
t
ls ls l s Ils
αβ κ
=− +∇∇
. (2)
The image function
(, )
xy
can be replaced with smoothed
version
(, ) (, )Gxy Ixy
σ
∗
, where
(, )Gxy
σ
is the standard
Gaussian function. The operator
∗
is the convolution
operator, and
∇
is the gradient operator.
When the solution
()
t
ls
stabilizes, left term of (2)
disappears. We then obtain the solution for minimizing
energy problem of (1).
The major problem with traditional snake is the limited
capture range. This usually results a difficulty of setting
initial contour. The initial contour must be closed to edges of
image. Arbitrary initial contour will cause wrong results.
This is because the third term of (2) can not spread over
entire 2D image. Consequently, there is no force to attract
the curve to the edges of image.
B. GVF Snake Model
To solve the problem of limited capture range, Xu and
Prince proposed GVF as a new external force for snakes [6].
In Xu’s approach, the attractive force near the
I
International Conference on Information Science and Technology
March 26-28, 2011 Nanjing, Jiangsu, China
978-1-4244-9442-2/11/$26.00 ©2011 IEEE