Fractal bubble algorithm for simplification of 3D point cloud data

Abstract

We present a novel technique for 3D point cloud simplification — the so-called fractal bubble algorithm — to minimize the computational time and overall storage space. The proposed fractal bubble algorithm generates 2D elastic bubbles and copies of themselves through 2D data sets representing planar geometric contours. Each of the bubbles, as it grows, is made to select a single point of its first contact, and all the selected points become the simplified set of points. The fractal bubble algorithm is repeatedly applied to the simplification of planar slices of general 3D point clouds corresponding to 3D geometric objects, leading to the global simplification of 3D point clouds. The benefits of the algorithm are: first the algorithm is computationally light and memory efficient, second it is simple to implement and inherently allows the organized selection of the points of contact and finally it enables us to simplify the point cloud data through a multi-scale fashion by varying a set of user-controlled algorithm parameters. Numerical results verify the effectiveness of the proposed algorithm.

Keywords

3D point cloud fractal bubble algorithm data simplification multi-scale reduction

1 Introduction

The use of 3D point cloud data becomes ubiquitous in engineering applications [1 –4] with the technological development of devices such as the depth camera and the laser scanner for 3D environment identification and also with the increasing needs for understanding the environment and geometric objects either in real-time or offline. However, the number of 3D data points from these devices can easily be piled up to result in a cloud of millions and millions of data points, possibly with a considerable amount of redundancy. It demands a great deal of computational load and excessively large storage space to deal with such a huge set of data points, which is not desirable. So, there is a need for reduction of the original data points into a reasonable size in applications where intensive data processing must follows for geometric understanding of the data.

Over the past few decades, a number of studies have been conducted on the simplification of point cloud data sets. Alexa et al. [5] proposed the simplification algorithms for point cloud object models using moving least square (MLS) method. Du et al. [6] proposed an adaptive out-of-core algorithm for the simplification of the large point cloud models. In this algorithm, first they performed simplification using the quadric matrix, and then used point-pair contraction and point-split methods to further simplify the flat and detailed regions, respectively. Pauly et al. [7] presented a spectral method for processing the point-sampled objects, which dealt directly with the data points and normals by dividing and resampling surface patches using the spectral decomposition approach. Moenning et al. [8] introduced an intrinsic algorithm for point cloud simplification with density guaranteed. This algorithm used the extended fast marching approach to provide the users with controlled and uniform sampling of data points.

Some simplification algorithms used clustering methods to reduce data points by grouping local points and contracting the number of data points. Song et al. [9] proposed a global clustering simplification method by partitioning the original set of data into point clusters and considered each point cluster as a single point. In this algorithm, they treated the data simplification method as an optimization problem and tried to minimize the geometric deviation between the original set of data and the simplified one. Kollios et al. [10] introduced a biased sampling algorithm based on density of local regions, which sped up the process of cluster detection. They computed the probability of each point to select the representative point in the local region. Boissonnat et al. [11] adapted mesh simplification algorithms for the point cloud simplification with guaranteed geometry by using the geodesic Voronoi diagrams. However, their algorithm required a huge amount of computation and a large memory space for the mesh generation.

Some other studies focused on evaluating importance of points based on the object geometry and redundancy, e.g., [12 –14] to simplify the point cloud. Hao et al. [12] proposed a point cloud simplification method aiming at enhancing the relative sharpness of edges in the data. This method first detected data points on the edges, and then applied the progressive simplification on the other non-edge data points. Lee et al. [14] presented a data simplification algorithm by using the information of point normals to local geometric surface. Li et al. [15] introduced a self-adaptive simplification algorithm to efficiently simplify the dense point cloud data by using the normal eigenvalues and thus to make the simplified data contain a sufficient information density around the featured region while less information density in the non-featured region. Heuristic approaches for data simplification to meet the desired number of points have also been investigated for the possible benefit of less computational burn. Carsten et al. [16] introduced the point cloud simplification by using the fast marching farthest point sampling approach. This algorithm facilitated the uniform and feature-sensitive point cloud simplification. Qing et al. [17] proposed an adaptive simplification algorithm for the irregularly distributed point cloud based on the particle swarm optimization approach, and obtained the evenly distributed simplified model.

Recent works have become more interested in developing computationally manageable and robust algorithms due to the need for handling large amount of data. Leal et al. [18] introduced a new method for 3D point cloud simplification by estimating the local density of the large point cloud. This method was known to be robust to outliers and noises. Another recent noticeable work on point cloud simplification was performed by Tafifeng et al. [19], where the redundant points were effectively eliminated up to the level that was computationally manageable. They divided the point cloud into some categories by using the deviation angles of normal vectors, and finally obtained the simplified data by employing the Hausdorff distance approach.

Aforementioned previous simplification algorithms, even those of heuristic approaches, heavily depends upon mathematical analysis and computations that might not be suitable for small scale problems or cases of generic purposes. In this paper, we present a novel computationally less intensive algorithm for point cloud simplification, called as the fractal bubble algorithm, as a simple geometric approach offering effectiveness for selecting the important representative points. The simplified models preserve the overall shape and contain all the important features representation (such as boundary, corners, concavity, etc.) of the original objects. At the authors’ best knowledge, no other previous works on 3D point cloud simplification have proposed the fractal bubble algorithm. The fractal bubble algorithm provides a multi-scale nature through the use of self-similar hierarchical fractal 2D bubbles. Although designed for 2D data sets, the fractal bubble simplification algorithm can be applied to any general 3D data point cloud after slicing the 3D data into 2D data sets. This algorithm is simple, and easy to implement as it has less mathematically complexity as compared to many previous point-based simplification attempts. Especially when data points are highly scattered, the proposed fractal bubble algorithm reduces the data points very efficiently due to its inherent adaptive nature to select important points.

The paper is organized as follows. Section 2 describes the working principle of fractal bubble algorithm and introduces the fractal bubble algorithm for 2D data point cloud simplification. Section 3 presents the use of the proposed algorithm in the 3D data point cloud simplification. Section 4 numerically evaluates the effectiveness of the fractal bubble algorithm and explains the multi-scale characteristics. Finally Section 5 addresses concluding remarks and a description of possible future works.

2 Fractal bubble algorithm

The fractal geometry, first used by Benoit Mandelbrot [20] to understand geometric patterns, allows us to accurately describe non-Euclidean shapes or rough geometrical irregularities exiting in nature by repeating scaled patterns. See some examples of fractal geometries in Fig. 1. For this reason, a large number of studies have employed the fractal concept for analyzing geometric features [21 –24]. Fractal concept is used as a powerful tool for the characterization in many medical imaging applications such as mammographic tissue classification [21, 24]. Barrett et al. [22] and Zhou et al. [23] presented the applications of fractal analysis to food structure and wear prediction, respectively. Umyai et al. [25] utilized the fractal concept to detect the air bubbles on ribbed smoked sheets.

Fig. 1

Examples of Fractal geometry: (a) the Koch snowflake [26] constructed by using self-similar triangles; (b) a schematic fractal geometry built by using multi scaled castle shapes.

In this section, we introduce our basic fractal bubble algorithm that simplifies the data points dispersed along 2D geometric contours. This algorithm enables us to collect importance points from a large set of original data points by making self-similar 2D elastic bubbles grow from their seed locations until they touch data points. Thereby they capture the object’s important features using a fairly smaller number of points associated with the 2D sub-bubbles. The structure of creating sub-bubbles follows those of common self-similar fractal geometries [21 –24], which has proven their effectiveness in describing complex object shapes in a multi-scale fashion through simply repeating a pattern. In the sequel, detailed procedure of the fractal bubble algorithm and its use in 2D geometric data simplification are addressed.

2.1 Proposed Fractal bubble algorithm: Procedure

Here, the proposed fractal bubble algorithm working for 2D points will be explained step by step in detail. A set of 2D points as a shape instance is assumed to represent a contour of an associated object geometry. Every shape or example considered here has a complex geometry with a large amount of structural irregularities such as protuberances, pores, and possibly replicating structures. The complete algorithm is divided into several steps, as given below.

As the first step of the proposed fractal bubble algorithm, we need to define the locations of seeds for growing fractal bubbles. The seeds for fractal bubbles can be spread on a base geometry, which can be a circle, a triangle, or an ellipse, corresponding to the global shape and distributed nature of data points. Basically the base geometry should be chosen in such a way that the whole point cloud can be expressed well. For example, for the 2D point cloud shown in Fig. 2, a circle can be an acceptable base geometry, though an ellipse or a square may be an alternative choice. For the circular shaped base geometry, its center is defined as the center of mass for all data points, and the radius of base fractal bubble is chosen as the mean length between the length from the nearest point from the center and the length to the farthest point, as shown in Fig. 2. We may be able to rely on some mathematical ways such as the least square method to define the base geometry but at the cost of increased computation time.

Fig. 2

Definition of the base geometry (a circle) that locates the seeds for fractal bubbles.

Once the base geometry is defined, the next step is to spread the seeds for the bubbles along the base geometry and then make them grow to search for importance points in the data points. These become the first order bubbles. The centers of the bubbles remain on what the seeds were first placed. When each of the bubbles is made to grow until it first touches any point among the data points as shown Fig. 3, then keep this point as the selected significant one. Each of bubbles chooses only one point that first comes in contact with its surface, which also defines its radius. It is possible that some data points are selected in multiple times as the first order bubbles find their points of contact. Then, eliminate the duplications. Figure 4 illustrates the sets of selected points depending on the number of bubbles, D. The seeds in Fig. 4 were spread at equal distances along the base circle. Obviously a large number of bubbles selects a large number of significant points.

Fig. 3

Selected importance points by the first-order bubbles.

Fig. 4

Seeds of first-order fractal bubbles depending on the value of D.

However, simply increasing the number of bubbles in the base circle would not be an effective way to capture the detailed features of the geometry that the original data points are supposed to express. The way we propose is to generate the second-order bubbles growing along the first-order bubbles, rather than simply by increasing D, the number of first order bubbles. Since the second-order bubbles are originated along each of the first-order bubbles, the local shape around the contact point of the first-order bubble can be more precisely expressed. Whereas the number D can enhance the global averaged shape, the sub-bubbles works to enhance the local details.

In order to generate the sub-bubbles, all of the first-order bubbles — frozen when they first touched data points — are considered as new base geometries. Along these new base circles, D number of seeds for the sub-bubbles like fractal geometry are scattered. Then, we make the sub-bubbles grow from the seeds points until each of them begins to contact a data point. In this way, D number of points surrounding each seed of the first-order bubbles can be selected as importance points. The procedure can be repeated as much as one wants. Refer to Fig. 5, where X’s denote the importance points found and the dots are the centers of bubbles. As shown in Fig. 5, the first set of fractal bubbles are of the first order, which are used as the base circles in the next order fractal bubbles, and by repeating the same procedure, the N^th order fractal bubbles can be obtained. As the order N increases, the total number of bubbles will also increase to a sufficient amount that can captures the geometric features of original data points. Extracted simplified data points can be seen in Fig. 6.

Fig. 5

Recursive process for generating fractal bubbles by system order N. (Yellow circles represent the base circles): (a) Fractal bubbles of the 1st order; (b) Fractal bubbles up to the 2^nd order in the boxed region in (a); (c) Fractal bubbles up to the 3^rd order in the boxed region in (a); (d) Fractal bubbles up to the 4^th order in the whole region.

Fig. 6

Simplified data points by the fractal bubble algorithm: (a) Fractal bubbles (N=4, D=3); (b) Extracted data points.

2.2 Discussion on 2D fractal bubble algorithm

Now that the procedure of the fractal bubble algorithm has been addressed, here we make some discussion on its multi-scale and other related properties, which yield users some ways to adjust the level of simplification and better quality of reduced points to meet the requirements of target applications.

The shapes of fractal bubbles, associated with two parameters, D and N, are illustrated in Fig. 7. In the upper part of the Fig. 7, parameter D accounting for the number of seeds in each base circle is varied. As D increases, the number of bubbles of the same order is also increasing and good for resulting in a better global feature. However, one must be careful not to choose too large D for given fractal order N, because the total number of bubbles would be too large and so be the computation time as well. In the lower part of Fig. 7, the effect of fractal order N is shown. The fractal order can be considered as a multi-scale parameter that governs the level of detail of simplification since parameter N determines how many local points are collected surrounding a certain base seed point. Thus, using a larger value of N enhances the quality of shape especially at the edges. Simple algebra tells that the number of total fractal bubbles D^N dramatically increases with N, and thus the maximum for N exists in practical implementation. It also gives remedial options to avoid overly simplified data reduction from the original point cloud for given parameter D.

Fig. 7

Construction of fractal bubbles for different values of D and N: (a) Numbers seeds in the base circle (D); (b) Order of fractal bubble (N).

The choice of base geometry, as mentioned before, might affect the quality of preservation of object shape after data reduction. As it can be any geometries like circle, ellipse or triangle, one can choose the best one considering the shape of point distribution. A least square based method could be utilized to find a good candidate for the base geometry. Scattering the seeds along the base geometry can also be made in an adaptive fashion if a sophisticated data simplification is required. These aspects are still left as open issues and can be further investigated in the future.

3 3D point cloud simplification

In this section, the procedure for data simplification of general point cloud that represents any 3D object is presented by using the proposed fractal bubble algorithm. The point cloud is a collection of surface data points of the 3D object, each of which is composed of x, y, and z coordinates. Because the point cloud may contain data points corresponding to background objects in real measurement, a set of pre-processing steps such as data denoising or outlier removal must be applied. Once done, the whole remaining data points are then subdivided into thin segments in a particular direction, so that the data points within each segment become projected onto a 2D plane and thus the fractal bubble algorithm can be applied. Here, the number of subdivision is directly related with the complexity of 3D object. Details of the whole procedure are addressed in the following.

The first step of the 3D point cloud simplification is to filter out noises and outliers in the raw data of 3D point cloud that has been acquired from some depth cameras. There are some well-known point cloud denoising filters including smoothing denoising, outlier removal and statistical denoising filters. However, the filtering by the outlier removal is more suitable for dense point cloud distribution, short distance scanning, fast speed and accuracy [27, 28]. So, we employ the outlier removal filtering in our proposed algorithm to easily eliminate data points of background or environmental objects based on preliminary knowledge of object scales. For ellipsoidal or spherical shapes, we may be able to utilize the shape information to construct a metric to determine the outliers. Figure 8 shows the original point cloud and its filtered version.

Algorithm 1 Procedure of the proposed fractal bubble simplification algorithm.

INPUT: 3D point cloud raw data;

OUTPUT: Simplified 3D point cloud data;

1: Begin procedure

2: read input: raw_3D point cloud;

3: print output: filtered_3D point cloud;

4: data_denoising ();

5: read input: filtered_3D point cloud;

6: print output: a_set_of_2D cross-sections;

7: S1, S2, S3, ..., Sm ← subdivision_3D_Point_cloud ();

8: D, N ← define_param_D_N ();

9: read input: 2D cross-sections;

10: print output: simplified 2D cross-sections;

11: Initialize ← fractal_bubble_algorithm;

12: define ← fractal_bubbles_seeds;

13: for (i = 1, i < = N, i ++) do

14: begin

15: for (J = 1, J < = D, J ++) do

16: begin

17: generate ← _i-th_order_fractal_bubbles;

18: determine ← _points_of_contacts;

19: remove ← duplication_in_selected_points;

20: end for

21: end for

22: if (representation of overall shape && important features ! = satisfactory) then

23: go to step 7 ← with D++ and/or N++ and/or S++;

24: end if

25: read input: simplified 2D cross-sections;

26: print output: simplified 3D point cloud;

27: reconstruct_3D_point_cloud ();

28: End procedure

29: ***********************************************************************************

30: data_denoising ();

31: begin

32: read input: 3D point cloud_with background and/or environmental objects;

33: print output: 3D point cloud _ without background and environmental objects;

34: outlier removal filtering ();

35: filter ← noises && outliers;

36: end function

37: subdivision_3D_point_cloud ();

38: begin

39: S ← define_param_S;

40: define ← axis of subdivision;

41: segmentation ← 3D point cloud into 2D data points

42: /* based on the density of point cloud */

43: end function

44: reconstruct_3D_point_cloud ();

45: begin

46: integrat_2D cross-sections;

47: end function

Fig. 8

Filtering of the point cloud by radius outlier removal algorithm: The raw data points in (a) become smoothly rearranged in an orderly manner like in (b) after applying the outlier removal filter.

Next, the resulting filtered 3D point cloud are to be divided into several thin segments, each of which reduces to a set of 2D data by projecting all the data onto the cutting plane. From this, all the data points within each thin segment comes to lie on the plane. Basically, the separation between the segments can be made of equal thickness. A variable thickness such that the number of data points in each subdivision is identical might be a possible choice in achieving evenly distributed data reduction. Whatever the thickness of subdivision may be, it should be that each projected data point still has its tag containing information on its original 3D coordinates. This is for the purpose of 3D reconstruction after the 2D data reduction by the fractal bubble algorithm. In the usual practice, the axis of least inertia (or the longitudinal direction of the object) can be normally chosen as the axis of subdivision. The reason for doing this way is because the axis of least inertia is likely to be the direction where the gradual change of object shape is minimal. However, if chosen with care, any case-specific direction might be acceptable. Figure 9 demonstrates the subdivision of 3D point cloud in an arbitrary direction. It is clear that the thickness of slices or the number of 2D cross-sections, S, is related to the density of point cloud after simplification. A large S will help preserve the original object shape but the amount of reduction will be insignificant, whereas a small S may result in some loss of geometric information. It turns out that S is another user’s tuning parameter.

Fig. 9

Subdivision of point cloud.

If all sets of the 2D data are prepared by the previous subdivision, then the fractal bubble algorithm described in section 2 is employed to each one. By considering the total number of data in each 2D cross-section, the fractal order and the number of seeds must be determined to achieve the desired amount of data reduction. And once this 2D procedure is over, the 3D reconstruction task comes in order by integrating the reduced cross sections as shown Fig. 10. There might be several ways to do the 3D reconstruction. For example, simply stacking up the reduced data on 2D cross-sections separated by the thickness used for data segmentation, which is the case in Fig. 10. Another way might be just placing all the reduced points in 2D cross-sections back to their original locations; this one is probably more natural. Interpolative relocation of the reduced points could be also conceivable. The overall procedure for simplification of 3D point cloud is shown in Algorithm 1.

Fig. 10

Reconstruction of simplified data points into a 3D shape.

4 Case examples and discussion

This section intends to explore the effectiveness and quality of the proposed simplification algorithm through case examples by employing a variety of 3D point cloud object models. Some of the tested object models were obtained directly by measurement through a depth camera (SR4000, MESA Imaging, Zürich, Switzerland), and the other object models were those open to public for benchmark tests. With these models, we first demonstrate how the basic fractal bubble algorithm works for 2D data simplification in accordance with simplification parameters and then apply the simplification algorithm to 3D point cloud. Finally we give a discussion on the implication of the results.

4.1 Effect of parameters of fractal bubbles

A planar data segment of a 3D point cloud data representing a mug is used to quantitatively demonstrate the effect of the parameters of the fractal bubble algorithm on the simplification of 2D data, as shown in Fig. 11. We used a circular base geometry and varied the number of seeds and the fractal order. Figure 11(a) shows how the number of data points captured—denoted as ‘x’ symbol in green color—changed as the number of seeds, D, increased while the fractal order was kept as N=1. With a larger D, the captured points came to better approximate the original geometric shape. Although the seed points were made to spread in equal intervals along the base circle, the bubbles adaptively selected the data points in a well distributed manner even with disconnected or vacant data points in the top and the bottom. When the order of the fractal bubbles, N, was made to vary while keeping the number of seeds as D=4, the generated bubbles dramatically increased by N, as shown in Fig. 11(b).

Fig. 11

Comparison of the effects of parameter D and N: (a) Effect of the number of seeds (D); (b) Effect of the number of fractal order (N).

It appeared that the selected points up to N = 2 showed rather congregated patterns about the points selected from the bubbles of lower fractal orders but then they came to spread widely as N further increased. If we had chosen a larger D, the selected points would have been spread more uniformly with a smaller N.

From this figure, we could see that the fractal bubbles are able to select nearest data points regardless of their distances from the center of fractal bubbles. This property gives the proposed fractal bubble algorithm a significant flexibility in many respects. For example, the natural elastic bubbles smoothly catch the overall contour of the data points without much regards to the given base geometries. Moreover, the contour shape of data points, whether they are poorly distributed or even disconnected, does not much influence the quality of simplification. These mean that the proposed algorithm is less sensitive to conditions of data points. Additionally, any given combination of algorithmic parameters (D and N) enables us to anticipate how detail the simplified set of data points would be, so the simplification in the multi-scale fashion may be achieved by adjusting those parameters, without undermining major features of the data points.

4.2 Simplification of 3D point clouds

Here we demonstrate the simplification for various objects of 3D point clouds with particular attention to the effects of tunable parameters of the proposed algorithm. We used some publicly available 3D models and some of our own. First a series of simulation was conducted to examine the effect of individual parameters of the simplification process, and after that additional simulation was carried out to discuss the combined effect of the parameters.

Figure 12 shows the original and simplified 3D point clouds of the Stanford Bunny and the Stanford Dragon [29]. The simplified 3D point clouds were obtained by using different values of parameter D, while the other parameters were kept constant (i.e., N=2 and S=100). Prior to applying the fractal bubble algorithm, the original 3D point clouds were sliced into 2D segments in the direction to the major axis of moment of inertia. As shown in Fig. 12(up), the quality of the simplified Stanford Bunny was improved with the increment of D. If we look at the simplified model with D=8, the shape of the Stanford Bunny contains all the important features even though the number of data points is 3687 only, which is one ninth of the number of original data points. By increasing the value of parameter D to 16, the shape of the simplified Stanford Bunny had more clear representation with much similarity with the original set of data points, although the number of simplified point was still less than a quarter of the number of original data points. Finer and less flawed shapes were obtained by increasing the value of D to 16 or higher. It should be pointed out that, in theory, the number of simplified 3D points is supposed to be, but the actual number of points is smaller than the expected one. This is because some points are possibly selected multiple times by different fractal bubbles. In Fig. 12(down), similar results are provided but with the Stanford Dragon which has a more complicated shape. The visual quality of the simplified

Fig. 12

Effect of parameter D on the data simplification of 3D point cloud models (N=2, S= 100): (Up) the Stanford Bunny; (Down) the Stanford Dragon.

Stanford Dragon was improved as D increased. For D=16, the simplified shape of the Stanford Dragon became very close to the original shape with less than a quarter of the original data points. These results show that the fractal bubble algorithm, with a proper choice of parameter D, can simplify the point cloud effectively, while maintaining major features of original geometries.

Figure 13 shows the effect of fractal order N on the simplification results, while all other parameters are kept constant (i.e., D=5 and S=100). Contrary to the effect of parameter D, a slight increment in N made a great change in simplification results, as can be seen in Fig. 13, that is, the number of simplified points increased dramatically with N. For N=3, the simplified models of the Stanford Bunny and the Stanford Dragon almost recovered their original models, though their data points were reduced by one sixth. At further higher orders of N, the shapes of the simplified data points got closer to their original shapes, but at the cost of increased computation time.

Fig. 13

Effect of parameter N on the data simplification of 3D point cloud models (D=5 and S=100): (Up) the Stanford Bunny; (Down) the Stanford Dragon.

Next, the effect of parameter S on the simplification of 3D data points was investigated by varying S value while all other parameters were kept constant (i.e., N=2 and D=8). Basically, parameter S can be viewed as the resolution of representation in the longitudinal direction. Too small S’s are likely to cause loss of detail in the segmentation, whereas too large S would ask for a large amount of computation time. As can be seen in Fig. 14, the larger the value of S is, the higher the level of representation or resolution of the simplified model becomes. The simplified models of the Stanford Bunny and Dragon make their fine representations at S=100, with noticeable reduction in the amount of data points. Here again, we must compromise between the detail and the computation time when choosing an appropriate value of S.

Fig. 14

Effect of parameter S on the simplification of 3D point cloud models (N=2 and D=8): (Up) the Stanford Bunny; (Down) the Stanford Dragon.

The dominant use of a certain parameter of the fractal bubble algorithm could yield a different results in the local features of the simplified 3D models. Fig. 15 shows three reduced models of the Stanford Bunny, where the left, the middle, and the right images, respectively, are the reduced models with a larger choice of D, N, or S than the others. Although the number of data points in all the three simplified object models were of a similar order (that is, 15910 points, 13745 points, and 14745 points), the simplified result by the dominant use of N (the middle one) was most satisfactory and superior to others in terms of resemblance with the original shapes of object; the edges in this reduced object model were sharply reconstructed and the data points were gently distributed on the surface. The simplification result with dominant parameter D (the left one) also preserved most of important features of the original model, but the edges were not represented as good as the middle one. The simplification result with dominant parameter S (the right one), contrary to the previous two cases, did not show the finger-print like surface data pattern. This seems to be due to the use of high S value which would increase the resolution in the segmentation direction to express the complex 3D models accurately.

Fig. 15

Comparison of simplification results for different values of the parameters: (Left) D=32, N=2, S=100, 15910 points; (Middle) D=8, N=4, S=100, 13745 points; (Right) D=8, N=2, S=500, 14745 points.

We have tested the fractal bubble algorithm to two other 3D point cloud models, that is, the Yoga and the Statue of GLady, retrieved from [30, 31], in order to explore the ability of the proposed algorithm when simplifying data points having jointed multiple 2D contour shapes. Note that the two object models in Fig. 16 would show several disconnected 2D circular contours around the limbs when segmented in the body’s longitudinal direction. Even so, the fractal bubble algorithm was able to successfully simplify the original data points well, without any additional effort or modification of the algorithm. This verifies that the fractal bubble algorithm’s ability to reduce general geometric shapes of 3D point clouds, no matter what they might be convex or concave.

Fig. 16

Examples of simplification results with other models: (a) Yoga (original data points: 21903 points, simplified data points: 8727 points (S=100, D=8, N=3)); (b) Statue of GLady (original data points: 44230 points, simplified data points: 7241 points (S=100, D=6, N=3)).

Table 1

Computational times and the reduced numbers of data points for different example models

Original model	D = 10, N = 2, S = 200	D = 20, N = 2, S = 100	D = 10, N = 3, S = 100
(No of points)	Computational time	Computational time	Computational time
	(No of points)	(No of points)	(No of points)
The Stanford Bunny (35336 points)	23[sec] (7057 points)	36[sec] (7442 points)	136[sec] (11387 points)
The Stanford Dragon (43467 points)	25[sec] (7618 points)	45[sec] (7867 points)	215[sec] (12904 points)
Yoga Lady (21903 points)	16[sec] (6425 points)	29[sec] (6272 points)	125[sec] (8793 points)
Glady (44230 points)	26[sec] (9204 points)	29[sec] (10035 points)	198[sec] (14244 points)

Table 2

Comparison of our algorithm with other point cloud simplification algorithms

Reference	Dataset	Original model	Simplified model	Computational time
		(No of points)	(No of points)	(Seconds)
Ref [32]	Bunny	35947 points	11779 points	Not given
Ref [12]	Bunny	35947 points	3595	2093
Ref [33]	Bunny	34,835 point	13571 points	111.238
Ref [34]	Bunny	35947 points	3594 points	1720
Ours(D = 8, N = 2, S = 100)	Bunny	35336 points	3687 points	15

Since the computational time is another important factor along with stroage space that needs to be considered in the simplification process. Table 1 lists the computational times taken during the simplification process and the reduced numbers of data points for different example models with different combinations of the simplification parameters. And Fig. 17 shows the graphical representation of the corresponding results.

Fig. 17

Computational time used and memory storage reduction after simplification by the fractal bubble algorithm.

To yield the results, the simplification algorithm was coded by C language and was run on an IBM compatible PC with core i5 (by single core processing). It can be seen that the fractal order parameter, N, influenced the overall computation time more significantly than any other parameters. And D was relatively more sensitive to the computation time than S. Thus, it would be desirable that the simplification parameters be carefully selected especially for N. After all, a proper combination of parameters is supposed to meet the level of simplification required to represent the overall shape and important features of the original model, as well as reducing the computation time.

Table 2 shows the comparison of our proposed algorithm with the other point cloud simplification algorithms [12 , 32–34]. we consider the previously discussed simplified model with the simplification parameters D=8, N=2, and S=100, shown in Figs. 12 and 14, as a candidate for comparison. It can be seen that the running time of our proposed algorithm is faster than the other point cloud simplification algorithms, while the simplified data points of our proposed algorithm are almost equal or less than the one obtain from the other point cloud simplification algorithms. This contest could be used as a reference for the efficiency of our proposed algorithm, although they were measured in different experiment environments.

Throughout this section, the quality of simplified result using the proposed algorithm has been evaluated rather in a qualitative and visual way. Since the proposed algorithm was not intended for mathematically oriented applications, a strict quantitative evaluation has not been made. However, one can quantitatively evaluate the closeness between the original and the simplified point clouds by simply applying the one of several well-established methods in literatures [35 –38]. For example, a measure like the Euclidean distance between the sampled point and its projection on the simplified surface [35] could be used, and another possible measure is to use the numerical simplification error by calculating the Hausdorff distance of the two point clouds [36].

5 Conclusion

In this paper, we proposed the so-called fractal bubble algorithm to simplify the 3D data points in object models and validated its effectiveness through numerical examples. The proposed fractal bubble algorithm selects importance data points by recursively generating self-similar 2D bubbles which elastically expand until they come in contact with any points. The reduced set of important points that the fractal bubbles touch is our simplified set of 2D data. In order to exploit the fractal bubble algorithm in 3D data simplification, we first divide the 3D point cloud into a number of 2D data segments, and then apply the fractal bubble algorithm to reduce the number of data points in each 2D data segment. Once the 2D data reduction is completed, we stack up the simplified 2D data sets to reconstruct the 3D shape, keeping the primary features of the original object. This algorithm shows an advantage of multi-scale nature depending upon how the algorithmic parameters are chosen. We presented several numerical results to show performance and characteristics of the proposed simplification algorithm by varying the simplification parameters. We have observed that among the three tuning parameters in the fractal bubble algorithm, the fractal order, N, plays the most critical role in preserving the local and global features of original geometries, but at the cost of probable increased computational time. Users can decide in the middle the optimum sets of parameters by trials without any difficulty.

Footnotes

Acknowledgment

This study was supported by the Korea University Grant.

References

Wöhler

, 3D Computer Vision: Efficient Methods and Applications, 2nd Ed, Springer, Springer: London, UK, 2013.

Bosché

, Forster

and Valero

, 3DSurveyingTechnologies and Applications: Point Clouds and Beyond, Technical report, Heriot-Watt University, UK, 2015.

Lyons-Baral

and Kemeny

, Applications of point cloud technology in geomechanical characterization, analysis and predictive modeling, Mining Engineering 68(5) (2016), 18–29.

Kumar

, Jain

P.K.

and Pathak

P.M.

, Industrial application of point cloud/STL data for reverse engineering, DAAAM International Scientific Book, 2012; Chapter 38.

Alexa

, Behr

, Cohen-Or

, Fleishman

, Levin

and Silva

C.T.

, Point set surfaces, In Proceedings of the IEEE Visualization, California, USA, 21 - 26 October 2001; pp. 21–28.

, Yin

and Kong

, Adaptive Out-of-Core Simplification of Large Point Clouds, In Proceedings of the IEEE International Conference on Multimedia and Expo, Beijing, China, 2-5 July 2007; pp. 1439–1442.

Pauly

and Gross

, Spectral processing of point-sampled geometry, In Proceedings of the annual conference on Computer graphics and interactive techniques, New York, USA, 01 August 2001; pp. 379–386.

Moenning

and Dodgson

N.A.

, Intrinsic point cloud simplification, In Proceedings of the International Conference on Computer Graphics and Vision, Moscow, Russia, 6-10 September 2004.

Song

and Feng

H.Y.

, A global clustering approach to point cloud simplification with a specified data reduction ratio, Computer-Aided Design 40(3) (2008), 281–292.

10.

Kollios

, Gunopulos

, Koudas

and Berchtold

, Efficient biased sampling for approximate clustering and outlier detection in large data sets, IEEE Transactions on Knowledge and Data Engineering 15(5) (2003), 1170–1187.

11.

Boissonnat

J.D.

and Cazals

, Coarse-to-ne surface simplification with geometric guarantees, Computer Graphics Forum 20(3) (2001), 490–499.

12.

Song

and Feng

H.Y.

, A progressive point cloud simplification algorithm with preserved sharp edge data, The International Journal of Advanced Manufacturing Technology 45(5-6) (2009), 583–592.

13.

Kalaiah

and Varshney

, Modeling and rendering of points with local geometry, IEEE Transactions on Visualization and Computer Graphics 9(1) (2003), 30–42.

14.

Lee

K.H.

, Woo

and Suk

, Point data reduction using 3D grids, The International Journal of Advanced Manufacturing Technology 18(3) (2001), 201–210.

15.

, Xu

and Shen

, A self-adaption fast point cloud simplification algorithm based on normal eigenvalues, In Proceedings of the International Congress on Image and Signal Processing, Dalian, China, 14–16 October 2014; pp. 852–856.

16.

Moenning

and Dodgson

N.A.

, A new point cloud simplification algorithm, In Proceedings of the International Conference on Visualization, Imaging and Image Processing, Benalmadena, Spain, 8-10 September, 2003.

17.

Qing

, Tao

, Tatsuo

, Yujie

, Wenting

and Hang

, Point cloud simplification algorithm based on particle swarm optimization for online measurement of stored bulk grain, International Journal of Agricultural and Biological Engineering 9(1) (2016), 71–78.

18.

Leal

, Leal

and German

S.T.

, A linear programming approach for 3d point cloud simplification, IAENG International Journal of Computer Science 44(1) (2017), 60–67.

19.

, Pan

, Gao

and Li

, A novel simplification method of point cloud with directed Hausdorff distance, In Proceedings of the International Conference on Computer Supported Cooperative Work in Design, Wellington, New Zealand, 26-28 April 2017; pp. 469–474.

20.

Mandelbrot

B.B.

, The fractal geometry of nature; Times Books: New York City, USA, 1982.

21.

Priebe

C.E.

, Solka

J.L.

, Lorey

R.A.

, Rogers

G.W.

, Poston

W.L.

, Kallergi

, Oian

, Clarke

L.P.

and Clark

R.A.

, The application of fractal analysis to mammographic tissue classification, Cancer letters 77(2) (1994), 183–189.

22.

Barrett

A.H.

and Peleg

, Applications of fractal analysis to food structure, LWT-Food Science and Technology 28(6) (1995), 553–563.

23.

Zhou

G.Y.

, Leu

M.C.

and Blackmore

, Fractal geometry model for wear prediction, Wear 170(1) (1993), pp. 1–14.

24.

Lopes

and Betrouni

, Fractal and multifrl analysis: A review, Medical Image Analysis 13(4) (2009), 634–649.

25.

Umyai

, Kumhom

and Chamnongthai

, Air bubbles detecting on ribbed smoked sheets based on fractal dimension, In Proceedings of the International Symposium on Intelligent Signal Processing and Communications Systems, Chiang Mai, Thailand, 7-9 Dec. 2011, pp. 1–4.

26.

Available online: https://en.wikipedia.org/wiki/Kochsnowflake, (accessed on Aug. 14, 2017).

27.

Yang

, 134. Research on Denoising Algorithms Based on Point Cloud Data of Terrestrial 3D Laser Scanner, Revista de la Facultad de Ingeniería 32(11), 2017.

28.

Wang

, Outlier formation and removal in 3Dlaser scanned point clouds, 2014, Doctoral dissertation, University of British Columbia.

29.

Available online: http://graphics.stanford.edu/data/3Dscanrep/, (accessed on Oct. 14, 2016).

30.

Available online: http://web.siat.ac.cn/ huihuang/Skeleton/Skeletonpage.html, (accessed on Oct. 19, 2016).

31.

Available online: http://web.siat.ac.cn/ huihuang/Skeleton/Skeletonpage.html, (accessed on Oct. 19, 2016).

32.

Song

and Feng

H.Y.

, Point-cloud simplification with bounded geometric deviations, International Journal of Computer Applications in Technology 30(4) (2007), pp. 236–244.

33.

Ning

, Wang

, Meng

and Zhang

, Optimized shape semantic graph representation for object understanding and recognition in point clouds, Optical Engineering 55(10) (2016), 103–111.

34.

Song

and Feng

H.Y.

, A point cloud simplification algorithm for mechanical part inspection, In Proceedings of the International Conference on Information Technology for Balanced Automation Systems, Boston, USA, September 2006, pp. 461–468.

35.

Shi

B.Q.

, Liang

and Liu

, Adaptive simplification of point cloud using k-means clustering, Computer-Aided Design 43(8) (2011), 910–922.

36.

Pauly

, Gross

and Kobbelt

L.P.

, Efficient simplification of pointsampled surfaces, In Proceedings of the conference of IEEE visualization, Boston, USA, 27 Oct. -1 Nov. 2002, pp. 163–170.

37.

Cignoni

, Rocchini

and Scopigno

, Metro: Measuring error on simplified surfaces, Comput Graph Forum 17(2) (1998), 167–174.

38.

Miao

, Pajarola

and Feng

, Curvature-aware adaptive re-sampling for point-sampled geometry, Comput-Aided Design 41(6) (2009), 395–403.