08-16-2017, 08:42 PM
region growing segmentation for point cloud matlab code
Region growing segmentation
In this tutorial we will learn how to use the region growing algorithm implemented in the pcl::RegionGrowing class. The purpose of the said algorithm is to merge the points that are close enough in terms of the smoothness constraint. Thereby, the output of this algorithm is the set of clusters, were each cluster is a set of points that are considered to be a part of the same smooth surface. The work of this algorithm is based on the comparison of the angles between the points normals.
Theoretical Primer
Let s take a look on how the algorithm works.
First of all it sorts the points by their curvature value. It needs to be done because the region begins its growth from the point that has the minimum curvature value. The reason for this is that the point with the minimum curvature is located in the flat area (growth from the flattest area allows to reduce the total number of segments).
So we have the sorted cloud. Until there are unlabeled points in the cloud, algorithm picks up the point with minimum curvature value and starts the growth of the region. This process occurs as follows:
The picked point is added to the set called seeds.
For every seed point algorithm finds neighbouring points.
Every neighbour is tested for the angle between its normal and normal of the current seed point. If the angle is less than threshold value then current point is added to the current region.
After that every neighbour is tested for the curvature value. If the curvature is less than threshold value then this point is added to the seeds.
Current seed is removed from the seeds.
If the seeds set becomes empty this means that the algorithm has grown the region and the process is repeated from the beginning. You can find the pseudocode for the said algorithm below.
Inputs:
Point cloud = \{P\}
Point normals = \{N\}
Points curvatures = \{c\}
Neighbour finding function \Omega(.)
Curvature threshold c_{th}
Angle threshold \theta_{th}
Initialize:
Region list {R}\leftarrow{\O}
Available points list \{A\}\leftarrow\{1,.., P \}
Algorithm:
While \{A\} is not empty do
Current region \{R_c\}\leftarrow{\O}
Current seeds \{S_c\}\leftarrow{\O}
Point with minimum curvature in \{A\}\rightarrow P_{min}
\{S_c\}\leftarrow\{S_c\}\cup P_{min}
\{R_c\}\leftarrow\{R_c\}\cup P_{min}
\{A\}\leftarrow\{A\}\setminus P_{min}
for i=0 to size ( \{S_c\} ) do
Find nearest neighbours of current seed point \{B_c\}\leftarrow\Omega(S_c\{i\})
for j=0 to size ( \{B_c\} ) do
Current neighbour point P_j\leftarrow B_c\{j\}
If \{A\} contains P_j and cos^{-1}( (N\{S_c\{i\}\},N\{S_c\{j\}\}) )<\theta_{th} then
\{R_c\}\leftarrow\{R_c\}\cup P_j
\{A\}\leftarrow\{A\}\setminus P_j
If c\{P_j\}<c_{th} then
\{S_c\}\leftarrow\{S_c\}\cup P_j
end if
end if
end for
end for
Add current region to global segment list \{R\}\leftarrow\{R\}\cup\{R_c\}
end while
Return \{R\}