2012 International Workshop on Nonlinear Circuits,Communications and Signal Processing
NCSP'12, Honolulu, Hawaii, USA. March 4-6, 2012

Facet-Growing Approach to Point Cloud Segmentation Using Local
Convexity and OctreeHuan Fu1,2,a ,Fei Wang1,b , Yoshifumi Nishio3,c , Yongjian He1,4,d, Chengwei Hu5,e1

Institute of Artificial Intelligence and Robotics, Xi’an Jiaotong University, China
2
Institute of Computer Software and Theory, Xi’an Jiaotong University, China
3
Department of Electrical and Electronic Engineering, Tokushima University, Japan
4
Xi’an Communication Institute, China
5
Academy of Space Technology, Chinaafuhuan.2009@stu.xjtu.edu.cn, bwfx@mail.xjtu.edu.cn, cnishio@ee.tokushima-u.ac.jp,dheyj@aiar.xjtu.edu.cn, ecwh@aiar.xjtu.edu.cn
Abstract

An novel method using local

surface segmentation. The common features

convexity and octree is proposed to segmentused in this kind of methods are normal vector,irregular 3D point cloud into surfaces. An

curvature and their derivatives. (2) Get themodified octree method is used to produce thedefinition and feature of characteristics in 2D

init facet set which usually contains too manyspace, extended to 3D space, get its newfacets and is meaningless, and then thedefinition and new feature, and use it to pointconnection of the leaf nodes is found. Finally,

cloud segmentation. (3) Use the theory in otherthe adjacent facets are combined if they satisfied

subject and get similar conclusion in point cloudthe local convexity. The proposed method issegmentation. All this methods are well applied

applied to the point cloud of the stone fractured

in surface segmentation of specific requirements.

from a tower and the results are discussed.

They platform nearly perfect on relative smooth

Keywords

Facet-Growing,

Point

Cloud

Segmentation, Local Convexity, Octree

point cloud, but be terrible on coarse one. Mostof the point cloud we get from reality is coarse,
so how to handle the coarse point cloud is themain problem we should solve. In this article,

1. Introduction
Point cloud segmentation is an important
step of many difficult problems such as object

we propose a new method to deal with questionsof this kind.

recognition, object registering and so on. InIn general, the workflow of our approachdifferent kinds of applications, we need tofor surface segmentation from point cloud can behandle a large amount of points’ data to getseparated

different segmentation results. For example, inestimation, initial segment by octree andthe application of dealing with laser scanningfacet-growing using local convexity. First,

from planes, we only need to split the roads,

Normal vector estimation is to calculate thebuildings from the point cloud. But in anothernormal vector of each point by compute theapplication, we may need to get the tree and its

average of the small triangles the point in. Then,branches from street scene's laser scanning. In

the points are assigned to octree's leaf nodes, andour article, we wanted to do more detailed work,

every node contains much information about thewhich is to partition point cloud of stone withpoints. Finally, we merge two connected nodes

rough appearance into several surfaces.

by judging whether they satisfied the local

Traditional

point

cloudsegmentationinthreesteps:

normalvector

convexity requirements.

methods can be divided into three categories: (1)Our segmentation algorithm is present inusing geometry and topology characteristics forSection 2. In Section 3, we display our- 349 -experiment result and discuss the error andnormal. In our approach, the simplest way to

performance of our approach.

solve this problem is to connect the normal tothe position of the point in the point cloud. In
short, if the point is in upper half of the point

2. Our Approach to Surface Segmentation

cloud's least bounding box, the z normal

2.1. Estimation of Normal Vector
Point cloud is composed of a series ofscattered points in 3D space, there is noconnection between points. So it's impossible tocalculate the normal of every point directly. To
estimate the normal vectors of the points, thedata first need to be triangulated. And thecommon Delaunay triangulation method is usedin our approach. After this step, every point isassigned to at least one triangle, the normal
vector of every triangle can be got easily. What
we need to do is the compute the normal of pointby the triangles include that point.
The normal value of point P is estimatedfrom a group of triangles that using point P as
one of their vertexes. Fig.1 shows point P and
its triangles. The normal value of point P andnormalized pint normal at the same point arecomponents must be positive, and be negative inthe other case. According to this criterion, we
can easily correct the normal vector of eachpoint.
2.2. Initial Segment Using Octree
The scan data after registration keep thenormal values for each point. Because the data iscoarse, conventional ordering and merging
procedure will not play well. In our approach,
we apply the octree method to avoid these steps
and get the initial segment. This method can be
represented as a tree structure, as show in Fig.2.
In the octree method, each cubical octant in thepyramidal structure has eight daughters createdby halving the parent cell along x, y and z
directions based on the criteria defined by theapplication.

calculated by Eqs. (1) and (2), respectively:
mnp ni 1

Level 100im
npnp | np |(1)5 6Level 2

1 23 4

Level 321 2223 2431 3233 34(2)81234567825 26

31 32 33

34 35 36

3738

71 72

7374 75

76

77 78

Fig.2 Octree Structure

In this research, the octree method is used
for segmenting the point cloud data. The main
steps are executed as follow: Firstly, find out themaximum and minimum at each axes, which aremarked as xmax , ymax , zmax and xmin , ymin , zmin ,Fig.1 Calculation of the normal value of a point.

and then, we can get the minimum bounding box

As the figure above described, the normalof the point cloud. The eight vertexes of the boxof P is calculated by getting average of 6
triangles.

store in the root node as the frame points, theAfter this step, the normal of each point is

its content point, the average normal iscalculated without orientation. And what wewhole points of the cloud also store in the root as
calculated by Eq.(3) as its value.

should do next is to decide the orientation of the- 350 -mn   ni / m

(3)

i 0

Where ni is the unit normal vector of point i ina node and m is the number of points in thecell.
There are two factors to decide whether anode is continued to be partitioned into eightdaughters. One is the standard deviation of point
normal vectors, which is calculated by:m |

 (n  n )
i 1

2i(4)

|

m

When the standard deviation is larger thantheuser-definedtolerance,

thenodeFig.3 Local convexity holds if the center point of a surfaceisis below the other surface

number of points in each node. If the number is

As illustrated in Fig.3, two neighboring
surfaces si and s j are termed locally convexsmaller than the user-defined tolerance, theto each other, if center point pi lies below thesubdivided procedure stops. The target of thesurface s j . In another word, if their normal

initial segmentation is to get the points into

vectors approximately have the same direction,
two surfaces are considered as locally convex.
The connections between nodes are divided

subdivided into eight. The other one is thegroups

withsimilarproperty

andbeing

connected in geometry. So we set these twoparameters: N num and node

into three classes: facet-connect, line-connect
to build theand point-connect, which are judged by therelationship of the minimum bounding boxes ofoctree.
The ideal result of initial segmentation issurfaces.
After this merge procedure, the result will

that, the standard deviation all leave nodes of thetree is under the user's definition, and thebe good enough for our application.

number of points is nearly the same, the tree is athree-level tree. Because of the data, its result is

3. Experiment and Conclusion

terrible. So we do our best to make theOur approach is used on the point cloud of

distribution of the point be equal, and platformthe stone. And the result is shown as follow. Our

the next step to optimize the result.

method of merging facets can reduce the number

2.3. Facet-Growing Approachof surfaces effectively. And the strategy we used

The steps above assign the points into

will be different in different application. The

several nodes with a feature value. Then our task

Fig.4 shows the result of our experiment. The

is to merge this node with taking advantage ofdata we used is a point cloud consisting of more

local convexity.

than 100 thousand points.

- 351 -find a new way to estimate the normal of pointand find a new way to explain the connection
between nodes.

References:[1] H.Woo,E.Kang,Semyung Wang and Kwan H.Lee. A new
segmentation method for point cloud data. International
Journal of Machine Tools & Manufacture 42:167-178,
2002.
[2] M.Yang,E. Lee. Segmentation of measured point datausing a parametric quadric surface approximation.

(a)Computer-Aided Design 31:449-457, 1999.
[3] Frank Moosmann,Oliver Pink and Christoph Stiller.
Segmentation of 3D lidar data in non-flat urban
environments using a local convexity criterion. IEEE
Intelligent Vehicle Symposium, 2215-220, 2009.
[4] A.Jagannathan and E.L. Miller. Three-dimensionalsurface mesh segmentation using curvedness-based
region growing approach. IEEE Transaction on PatternAnalysis and Machine Intelligence. 29(12):2195-2204,
2007[5] D. Steinhauser, O. Ruepp, and D.Burschka. Motion(b)

segmentation and scene classification from 3D LIDAR
data. Intelligent Vehicles Symposium, 398-403, 2008.
[6] X. Zhu, H. Zhao, Y. Liu, Y. Zhao, and H. Zha.
Segmentation and classification of range image from anintelligent

vehicleinurbanenvironment.

IEEEInternational Conference on Intelligent Robots andSystems, 1457-1462, 2010.
[7] R. Mario and V. Markus, Point Cloud Segmentation
Based on Radial Reflection Computer Analysis ofImages and Patterns, Lecture Notes in Computer
Science, 5702:955-962, 2009.
[8] R. Rusu, A. Holzbach, N, Blodow and M. Beetz. Fast(c)
Fig.4 a) The initial segmentation has 671 facet. b) Get two

Geometric Point Labeling using Conditional Random

seeds, and merge the facets into 3 surfaces. c) Combine theFields. IEEE International conference on Intelligent
Robots and Systems, 7-12, 2009.

facets iteratively and get 10 surfaces.

[9] C. Tai, M. Huang, The processing of data points basing

In this paper, we present a new way toon design intent in reverse engineering. International

handle irregular point cloud data. But because

Journalthe data cloud we used is dense in the top

40:1913-1927, 2000..

ofMachine

Tools

andManufacturesurface and sparse at other position. The[10] C. S. R. Aguiar, S. Druon, and A. Crosnier, 3D datasets

traditional way to get the normal of the point on

segmentation based on local attribute variation IEEEthe bottom and side faces may has terrible errors,

International Conference on Intelligent Robots andand it's hard to split the side part into surfaces

Systems, 3205-3210, 2007.

accurately. The next step in our research is to- 352 -