# Feature-Preserved Point Cloud Simplification Based on Natural Quadric Shape Models
## 3 Experiments and Discussions
### Comparison of Algorithms' Efficiency  
In order to compare the FPPS algorithm's efficiency with other algorithms, we carried out the point clouds simplification algorithm experiments on the same platform. The compared algorithms were grid-based, curvature-based, and K-means.  
The type of CPU was CA, US Intel (R) Core (TM) i7-6820 HQ (CPU @2.90 GHZ), and the main memory of the computer was 16 GB.  
The IDE (integrated development environment) of the experiment was visual studio community 2015, and the UI (user interface) was designed by QTS.6.2. The PCL1.8 (point cloud library) was introduced into this experiment for the point cloud's organization. The data sets used were Fandisk, Chair, and Bunny.  
The grid-based simplification is designed and implemented based on the reference [42] and is improved in this experiment for effectiveness. The grid-based simplification created voxels at a specific resolution without geometric feature estimation, and computed the center of each voxel as the simplified point cloud. For the curvature-based simplification algorithm, we computed the curvature for each point by PCA. Then, the index of point clouds was created according to the curvature. In the experiment, when the specific simplification ratio was set, the bigger curvature was saved as simplified point clouds. For the K-means simplification algorithm, the point clouds and the number of clusters are the algorithm's input, and the clusters are computed by K-means. Then, with the same simplification ratio for each cluster, the experiment can be implemented [17]. The experimental results are shown in Table 6.  
The FPPS analyzes the geometric features of a measured object and computes the simplification entropy of point clouds. The entropy-extracted time complexity of the algorithm is O(N) and its space complexity is O(N). Then, FPPS compares the shape features with Natural Quadric Shape Models, and the algorithm's time complexity is O(N). Therefore, as the last column in Table 6 shows, as the number of vertices in the point cloud increases, the memory usage and running time of FPPS become bigger.  
Of the simplification algorithms, the grid-based algorithm has the optimal efficiency, without computing the geometric features. The K-means algorithm used the most system resources, including time and memory. The curvature-based and FPPS simplification algorithms, which are used for surface feature preservation, are more complex than the grid-based algorithm, and the running time of these algorithms is longer. The time and space complexity of the grid-based and curvature-based simplification algorithms is O(N), which is the same with FPPS.  
\begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \multirow{2}{*}{**Data Set**} & \multirow{2}{*}{**Vertices**} & \multicolumn{2}{c}{**Grid-Based**} & \multicolumn{2}{c}{**Curvature-Based**} & \multicolumn{2}{c}{**K-Means**} & \multicolumn{2}{c}{**FPPS**} \\ \cline{3-10}  & & **Time** & **Memory** & **Time** & **Memory** & **Time** & **Memory** & **Time** & **Memory** \\  & & **(s)** & **(M)** & **(s)** & **(M)** & **(s)** & **(M)** & **(s)** & **(M)** \\ \hline
**Fandisk** & 6476 & 0.077 & 10.2 & 4.167 & 12.6 & 10.789 & 28.9 & 4.023 & 11.9 \\ Chair & 15,724 & 0.138 & 10.3 & 7.053 & 13.1 & 68.395 & 29.3 & 7.359 & 17.5 \\ Bunny & 35,947 & 0.121 & 6.6 & 15.610 & 19.3 & 193.828 & 45.6 & 38.066 & 23.1 \\ \hline \hline \end{tabular}
\end{table}
Table 6: The running time and memory usage of the simplification algorithms.  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Simplification Method** & **2000** & **5000** & **10,000** \\ \hline K-means & 100\% & 100\% & 100\% \\ Curvature & 100\% & 100\% & 100\% \\ Random & 100\% & 100\% & 100\% \\ FPPS & 31.06\% & 25.75\% & 23.47\% \\ \hline \hline \end{tabular}
\end{table}
Table 5: The noise simplification ratio \(r\) using the different simplification algorithms.