Simplification algorithm of denture point cloud based on feature preserving

Abstract

Due to the point cloud of oral scan denture has a large amount of data and redundant points. A point cloud simplification algorithm based on feature preserving is proposed to solve the problem that the feature preserving is incomplete when processing point cloud data and cavities occur in relatively flat regions. Firstly, the algorithm uses kd-tree to construct the point cloud spatial topological to search the k-Neighborhood of the sampling point. On the basis of that to calculate the curvature of each point, the angle between the normal vector, the distance from the point to the neighborhood centroid, as well as the standard deviation and the average distance from the point to the neighborhood on this basis, therefore, the detailed features of point cloud can be extracted by multi-feature extraction and threshold determination. For the non-characteristic region, the non-characteristic point cloud is spatially divided through Octree to obtain the K-value of K-means clustering algorithm and the initial clustering center point. The simplified results of non-characteristic regions are obtained after further subdivision. Finally, the extracted detail features and the reduced result of non-featured region will be merged to obtain the final simplification result. The experimental results show that the algorithm can retain the characteristic information of point cloud model better, and effectively avoid the phenomenon of holes in the simplification process. The simplified results have better smoothness, simplicity and precision, and are of high practical value.

Keywords

Denture point cloud features preserving multi-feature extraction octree K-means

1. Introduction

With the continuous aggravation of the aging population in China, the oral health problems are becoming more serious. Moreover, the oral health awareness and behavior ability of the masses are constantly improving with the further improvement of the medical insurance system, which brings great challenges to the oral health service system in China [1]. The rapid development of 3D laser scanning technology and breakthroughs in various key technologies have made the digital oral diagnosis and treatment model become a mainstream trend in the field of dental medicine of the future [2]. But with the application of high-precision scanners in the field of stomatology, especially when performing intraoral scans, it is usually necessary to change different orientations for scanning so that obtain an accurate and complete oral model. That inevitably leads to the redundancy of a large amount of data and brings difficulties to the storage, display and 3D reconstruction of point cloud data [3]. Therefore, the data simplification is an essential step in point cloud processing on the premise of ensuring the detailed characteristics of the measured denture point cloud data.

The principle of point cloud simplification is to reduce redundant point clouds as much as possible on the basis of accurately extracting point cloud feature points. The effective extraction of point cloud feature points will greatly reduce the error of simplification and improve the simplification efficiency [4]. At present, point cloud reduction algorithms can be roughly divided into two types: grid-based simplification and point cloud-based simplification. The essence of grid-based simplification algorithm is to construct the polygon mesh, then merge and compress the mesh according to the rules, and delete the redundant polygon mesh and vertices to achieve the purpose of point cloud simplification. The disadvantage of this method is that the grid topology needs to be consistent with each other, and the grid generation requires a large amount of computation, which will consume a lot of time and memory resources [5].

With the characteristic of fast speed and high efficiency, the simplification directly based on point cloud only needs to calculate the geometric information of point cloud, which has attracted more and more attention. Shi et al. [6] firstly extracted the edge features of point clouds, and then used the K-means algorithm to cluster the similarity point clouds. Finally, a subdivision algorithm is proposed to simplify the point cloud data and the simplified results are relatively uniform. But the point cloud features cannot be accurately extracted by using this method, which also affects the accuracy of reconstruction. Xuan et al. [7] extracted the feature points of point cloud based on normal angle and information entropy theory on the base of the estimation of normal vector, and gradually moved the non-feature point cloud to achieve the simplification, but the applicability of this method was not clear enough. Ji et al. [8] proposed a simplified algorithm based on multi-feature extraction, which measured the importance of sample points by constructing a feature formula, so as to retain the detailed features of the point cloud, and construct an octree to simplify the non-feature point cloud. Ma et al. [9] used the method based on edge curvature and area error to extract the detailed features of the point cloud, simplify the point cloud data, which has good robustness. But the accuracy of the simplified data will decrease as the reduction rate increases. Markovic et al. [10] used support vector regression algorithm to identify the points in the high zone rate region of point cloud data, so as to realize feature sensitivity and simplification of point cloud data. Dong and Tian [11] preserved feature points and simplified point cloud data by constructing the information entropy of weight product with different features of observation points.

Although the above algorithms can simplify and completely retain the details of the point cloud model, they are not applicable to the more complex oral model. Aiming at the above problems, this paper proposes a point cloud simplification algorithm based on feature preserving.

2. Description of algorithm

Defining the input denture model data as $P=\left\{{p_{i}\left({x_{i},y_{i},z_{i}}\right)\left|{i=1,2\ldots,N}\right.}\right\}$ , Where $p_{i}$ is the sampling point of point cloud data. The basic flow of the algorithm in this paper is: Firstly, the spatial topological relation of denture point cloud model is established by using kd-tree algorithm, and k-Neighborhood is constructed for each denture point cloud $p_{i}$ by searching k nearest neighbor points through Euclide distance. Then calculate the measurement operator with relevant feature through the k-Neighborhood. Secondly, for the characteristic areas of the model, the edge features contained in the denture point cloud are extracted by threshold determination after calculating the distance between the sampling point and the neighborhood center. The thin section features (cusp edge) and sharp features (molar occlusal surface) of the denture point cloud model will be extracted through threshold determination by calculating the curvature of the sampling point, the mean value of the included angle of the normal vector, the standard deviation and the average distance between the sampling point and its neighboring points, as well as combining with the proposed feature evaluation function. Thirdly, for the non-characteristic region of the model, the non-characteristic point cloud is spatially divided by octree. The point cloud is divided by octree, and the octree stop partition condition is set through expected simplicity, and the minimum number of leaf nodes is taken as the K-means classification number K value. The cube center of the smallest leaf node partitioned by octree was calculated, and the data point closest to the cube center was used as the initial clustering center. The simplified results of non-characteristic regions are obtained after further subdivision. Finally, the simplification results of edge features, sharp features and non-characteristic regions are fused to obtain the final simplification result. In general, the algorithm is divided into two parts. The first part is to preserve the detailed features of the model as much as possible through the algorithm, and the second part is to replace the non-characteristic areas of the model with few points on the basis of feature retention. The flowchart of denture point cloud simplification algorithm is shown in Fig. 1.

Figure 1.

The simplification algorithm flowchart of denture point cloud.

3. Extraction of denture point cloud feature region

3.1 Search of $k$ -Neighborhood

Point cloud neighborhood is a set of points that the sampling points of point cloud data and its adjacent points satisfy a certain spatial geometric relationship [12]. In this paper, there is no obvious topological relationship between the data of intraoral denture point cloud obtained by using an intraoral scanner, which has unstructured characteristics. In order to extract geometric features of point cloud data effectively, k-Neighborhood is needed to search for point cloud. The commonly methods used to search the k-Neighborhood of scattered point cloud include spatial raster method, octree method and kd-tree method.

Compared with spatial raster method and octree method, kd-tree method has the advantages of fast speed, strong adaptability, which is seldom influenced by point cloud density, and has small footprint on computer memory, etc. Therefore, kd-tree method is used in this paper to construct the denture point cloud data space topology structure.

3.2 Characteristic discriminant parameter calculation

Traditional feature point extraction of point cloud is relatively simple and usually only considers unilateral features, such as the curvature difference between the sampling point and the neighborhood point. In order to retain the detailed features of the oral scan denture model, a multi-feature mixed extraction method is used to extract the features of scattered point clouds in this paper.

3.2.1 The distance from the point to the neighborhood centroid

It is easy to lose edge features when simplifying the data model of non-closed dentures, resulting in boundary shrinkage and distortion. Therefore, in order to avoid the error of deleting the boundary features in the subsequent simplification. the boundary features of the denture model should be detected and protected before the simplification operation. The traditional idea of boundary feature extraction is based on the distribution characteristics of spatial point clouds. If the sampling point $p_{i}$ is the edge point, then the distribution of k-Neighborhood points will be skewed to one side; Otherwise, if it is the internal point cloud, the neighborhood points will be distributed around [13]. According to this idea, this paper uses the method of calculating the distance between the sampling point and its neighborhood centroid to extract point cloud edge features. Although this method can extract a few sharp feature points while extracting edge features, it will not affect the final result of simplification.

We define the set $\left\{{p_{ij}\left({x_{ij},y_{ij},z_{ij}}\right)|j=1,2,\ldots k}\right\}$ as the k-Neighborhood points of the sampling point $p_{i}$ , Then the neighborhood centroid of $p_{i}$ is:

$\displaystyle c_{i}=\frac{1}{k}\sum\limits_{j=1}^{k}p_{ij}$ (1)

The distance from the sampling point $p_{i}$ to the centroid of its neighborhood point can be expressed as:

$\displaystyle d_{i}=\left|{p_{i}-c_{i}}\right|$ (2)

3.2.2 Estimation of normal angle and curvature

The normal included angle and curvature of the point cloud in the neighborhood are the key rigid features of the scattered point cloud, which can fully reflect the uneven degree of the surface of the point cloud model and the change of the local surface. It is an important reference to detect and identify the feature points of the point cloud and simplify the point cloud data. At present, the existing methods for calculating the angle and curvature of normal vectors can be roughly divided into three categories: the method based on robust statistics, the method based on Delaunay/Voronoi and the method based on local surface fitting [14]. Principal component analysis (PCA) based on local surface fitting was first proposed by Hoppe et al. [15]. This method does not need to triangulate scattered point clouds, it is very suitable for the algorithm proposed in this paper, and the code is simple to write, easy to operate and runs faster. n this paper, distance weights are added on the basis of the original algorithm to obtain relatively smooth calculation results of the included angle and curvature of normal vectors.

Assuming that the local region of the point cloud can be approximated as a smooth plane, Then the normal vector of any sampling point $p_{i}$ can always be approximated by the normal of k-Neighborhood least square fitting plane of that point. The plane can be expressed as follows:

$\displaystyle H\left({n,d}\right)=\text{argmin}\sum\limits_{i=1}^{k}\left({n% \cdot p_{i}-d}\right)^{2}$ (3)

where $n$ is the normal vector of fitting plane $H$ ; $d$ is the Euclidean distance from the origin of coordinates to the fitting plane $H$ .

When the fitting plane $H$ passes through the centroid $c_{i}$ of the k-Neighborhood of the sampling point $p_{i}$ , and the normal vector n satisfies the unit vector, so if $n_{2}=1$ , the problem can be transformed into the eigenvalue decomposition of the positive semi-definite covariance matrix M in Eq. (4), and the covariance matrix is recorded as:

$\displaystyle M=\frac{1}{K}\sum\limits_{i=1}^{k}\left({p_{i}-c_{i}}\right)% \left({p_{i}-c_{i}}\right)^{T}$ (4)

Considering that the distance between the neighborhood point and the sampling point will affect the result, we assign the Gaussian distance weight $\varphi_{i}$ to all the neighborhood points of the sampling point $p_{i}$ . As a result, the neighborhood points which close to the sampling point have relatively great influence on the normal vector and curvature estimation results so that get a smoother estimation result:

$\displaystyle C=\frac{1}{K}\sum\limits_{i=1}^{k}\varphi_{i}\cdot\left({p_{i}-c% _{i}}\right)\left({p_{i}-c_{i}}\right)^{T}$ (5)

The three eigenvalues of the matrix $\lambda_{1}$ , $\lambda_{2}$ , $\lambda_{3}$ and their corresponding eigenvectors $n_{1}$ , $n_{2}$ and $n_{3}$ can be obtained by solving the covariance matrix $C$ . Assuming $\lambda_{1}\leqslant\lambda_{2}\leqslant\lambda_{3}$ , then the eigenvector corresponding to the minimum eigenvalue is the normal vector of the locally fitted surface at the sampling point $p_{i}$ . It should be noted that the obtained normal vector has semantic ambiguity, which means we only get is the magnitude of the normal vector, but its direction is not yet certain. Some face the inside of the surface, and some face the outside of the surface. Therefore, we have to consistently deal with the obtained normal vector. Assuming that the vector of the known viewpoint is $v_{s}$ , if $n_{i}\cdot v_{s}>0$ , If the normal vector satisfies the direction consistency, if not, the normal vector is flipped to take the opposite direction.

Define the $\left\{{n_{ij}|j=1,2,\cdots k}\right\}$ is the neighborhood normal vector set of the sampling point $p_{i}$ . then the mean of the included angle between the normal of the sampling point and its neighboring points is:

$\displaystyle\theta_{i}=\frac{1}{k}\sum\limits_{j=1}^{k}\text{arccos}\frac{n_{% i}\cdot n_{ij}}{\left|{n_{i}}\right|\cdot\left|{n_{ij}}\right|}$ (6)

The research of Pauly et al. [16] showed that the change of the surface of the point cloud model is equal to the curvature of the model. The eigenvalues represent the changes of the surface along the direction of the respective eigenvectors, so we can extract the curvature characteristics of the denture model according to the eigenvalues previously solved. Define the curvature at the sampling point $p_{i}$ as $\omega_{i}$ :

$\displaystyle\omega_{i}=\frac{\lambda_{1}}{\lambda_{1}+\lambda_{2}+\lambda_{3}}$ (7)

The smaller the value of $\omega_{i}$ , the smoother the local area where the sampling point $p_{i}$ is located. The value range of $\omega_{i}$ is $\left[{0,1/3}\right]$ .

3.2.3 The average distance and the standard deviation of the distance from point to neighborhood

For complex denture point cloud data, the distribution of point cloud data will change with the surface complexity of the model. The density of denture point cloud distribution is usually higher than flat regions of point cloud data in the characteristic areas of cusp, ridge and molar occlusal surface, etc. Therefore, it can help to identify the characteristic region of point cloud by judging the difference of density degree of point cloud in different regions of the model. In this paper, the standard deviation of the distance between the point and its neighboring points is used as the discriminant factor. The denser its neighborhood point distribution is when the sampling point is in the characteristic region. The smaller the dispersion degree between the sampling point and its k-Neighborhood point, the smaller the standard deviation. The distance between the sampling point $p_{i}$ and its neighborhood point is defined as $e_{ij}$ :

$\displaystyle e_{ij}=\sqrt{\left({p_{i}-p_{ij}}\right)^{2}},j=1,2,\ldots k$ (8)

The average distance from the sampling point to the neighborhood point is $h_{i}$ :

$\displaystyle h_{i}=\frac{1}{k}\sum\limits_{j=1}^{k}e_{ij}$ (9)

Then the standard deviation of the distance between the sampling point and its k-Neighborhood point is:

$\displaystyle\sigma_{i}=\sqrt{\frac{1}{k}\sum\limits_{j=1}^{k}\left({e_{ij}-h_% {i}}\right)^{2}}$ (10)

3.3 Discriminant extraction of feature points

In order to detect and protect the edge features of the denture model, we obtained the distance $c_{i}$ from the sampling point to the neighborhood centroid through the above calculation, and extracted the edge features of the denture model through threshold determination. For denture point clouds without edge features, according to the multiple feature measurement factors calculated above: The mean of the normal angle between the sampling point and its neighborhood points is $\theta_{i}$ , the curvature is $\omega_{i}$ , the average distance between the sampling point and the neighborhood points is $h_{i}$ i, the average distance between the sampling point and its k-Neighborhood points $h_{i}$ and the standard deviation $\sigma_{i}$ to construct a feature evaluation function., compare the feature value of each point cloud data with the set threshold, and extract the feature area of the denture model.

For the sampling point $p_{i}$ , the greater the normal Angle $\theta_{i}$ and the $\omega_{i}$ value, the greater the probability that the point $p_{i}$ is the characteristic point. Moreover, $\theta_{i}$ and $\omega_{i}$ are the most critical rigid features of point clouds. Therefore, we add the control coefficient to them when constructing the feature evaluation function so that the algorithm can adapt to different complexity of the point cloud model. The average distance from the sampling point to the neighborhood point is $h_{i}$ , and the standard deviation of the distance from the sampling point to its k-Neighborhood point $\sigma_{i}$ , both of them can reflect the density of the point cloud of the denture model in different regions. The smaller their value, the more likely the point $p_{i}$ is the feature point. Therefore, the characteristic evaluation function is defined as:

$\displaystyle f_{i}=\frac{\alpha\cdot\theta_{i}+\beta\cdot\omega_{i}}{h_{i}+% \sigma_{i}}$ (11)

where $\alpha$ and $\beta$ is the control coefficient of the normal angle and curvature respectively.

This paper defines the characteristic discrimination threshold as:

$\displaystyle F_{i}=\frac{1}{N}\sum\limits_{i=1}^{N}\frac{\theta_{i}+\omega_{i% }}{h_{i}+\sigma_{i}}$ (12)

where $N$ is the number of denture point clouds.

3.4 Non-feature simplification

The complex digital denture model not only contains characteristic areas such as tooth tip, tooth edge and molar occlusal surface, but also contains a large number of flat and smooth non-characteristic areas. If only use the feature points to simplify the point cloud data, it will cause a lot of holes on the reconstructed surface model. Therefore, we need to preserve a certain number of non-feature points while protecting feature points.

The method of cluster simplification can achieve good effect in the flat area of the model. The simplification algorithm based on K-means takes Euclidean distance as the correlation measurement. Through continuous iteration, the evaluation function value is minimized to divide K clusters. Finally, the cluster center is used to replace the whole cluster to obtain the final simplification result. The quality of the result of simplification largely depends on choosing K-value and initialization cluster center. Both the K-value and the initial clustering center of the traditional algorithm are set randomly, and the uncertainty of the initial clustering center will make the clustering results different each time, as well as make the evaluation function fall into the local convergence, which will not get the optimal clustering simplification result.

In order to solve the above problems, this paper uses octree to conduct spatial division of non-characteristic point clouds. The number of partitioned leaf nodes need to be obtained by setting the octree to divide the stopping condition which is the number of point clouds contained in the minimum leaf node. The number of non-empty leaf nodes in the obtained octree and the data points that is closest to the cube center in the non-empty leaf nodes will be regarded as the K-value of K-means clustering algorithm and the initial clustering center point respectively. Therefore, the initial clustering center can change with the density of different data models to ensure the distribution of the initial clustering center is relatively uniform. Then the simplified results of the non-characteristic areas can be obtained by determining whether each maximum normal angle meets threshold $\tau$ for further subdivision.

4. Results and analysis of experiment

In order to verify the performance of this algorithm, we applied this algorithm to canine data (3 644 points), molars data (4 053 points) and bridges data (36 388 points). The data of incisors contain a few detail features, but more plane features. The data of molars contain a few details, but has a high degree of concavity on the surface. The dental bridge data contains many detailed features and many edge features. In order to verify the effectiveness of the algorithm, the simplified results of the proposed algorithm in this paper will be compared with random sampling method, the simplified method based on curvature and the simplified method based on adaptive octree clustering. This paper uses Matlab to test the algorithm with Windows10 system, i5 3.0ghz processor and 8 GB memory.

4.1 Parameter setting

This paper sets different values for the edge threshold $d_{n}$ , the control coefficient of normal angle $\alpha$ and the control coefficient of curvature $\beta$ in the feature evaluation function to extract the characteristic regions of different point cloud models.

The K-value of K-means clustering algorithm and the initial clustering center point are determined by setting the stop condition of octree division which is the number of point clouds contained in the minimum leaf node. The simplified result of the non-characteristic area will be obtained by judging whether the maximum normal angle between clusters meets the threshold $\tau$ for further subdivision to the point cloud. Through the study of point cloud features, we found that the normal Angle $\theta_{i}$ of each point cloud is usually a large value, while the curvature $\omega_{i}$ is relatively small. Therefore, in order to accurately extract the feature points of the point cloud model, we set the control coefficient of normal included Angle $\alpha$ as a small value in the feature evaluation function and set the control coefficient of curvature $\beta$ to a large value. For the denture model with edge features, we use the distance $d_{i}$ from the point to the neighborhood centroid as the discriminant factor. The greater the value of $d_{i}$ , the more likely it is to be the edge point. Therefore, we sorted the extracted edge features in descending order and set the threshold $d_{n}$ according to our needs, then selected the point before the arrangement as the edge features. Table 1 shows the feature extraction and parameter setting of different denture models.

Table 1
Feature extraction parameters of denture model

Data	Parameters
	k	$\alpha$	$\beta$	$d_{n}$
Canines data	10	0.5	10	$d_{\textit{imax}}$
Molar data	9	0.4	8	$d_{\textit{imax}}$
Bridge data	8	3	5	0.1097

Figure 2.

Feature extraction effect of different denture models (a) Canine data (b) Molar data (c) Bridge data.

Figure 3.

Simplification effect of different simplification rate in denture model (a) Canine data (b) Molar data (c) Bridge data.

Figure 2 shows the feature extraction a different denture model. As can be seen from the Table 1 and Fig. 2, we have extracted the characteristic areas of the denture model well after the threshold determination. The features of the canine data model are mainly distributed around the model, especially the occlusal surface and the bottom of the canines. The characteristic area of the molar data model is mainly the concave and convex part of the occlusal surface and the tooth wall. The bridge model contains many feature types, which mainly located at the gingival margin (the part between the crown and the gingival), the edge features and the concave and convex parts on the occlusal surface of teeth.

4.2 Reconstruction effect

In this paper, the simplified point cloud data are obtained through data fusion after extracting the feature point and simplifying the non-feature. In order to verify the validity of the algorithm, this paper simplified denture model by setting different simplification rates. The Geomagic software was used to reconstruct the denture point cloud data at different simplification rates. The simplification rate of defining the point cloud is represented by $\eta$ :

$\displaystyle\eta=\frac{N-M}{N}$ (13)

where $N$ is the number of original point clouds, and $M$ is the number of retained point clouds after reduction.

Figure 4.

The reconstruction effect of different simplification rate in denture model (a) Canine data (b) Molar data (c) Bridge data.

This section mainly studies the influence of different simplification rates on the simplification effect of denture model. From Fig. 3, the simplification results of denture point cloud at different simplification rates save more point data in the feature area of the model, which can completely reflect the outline and detailed features of the denture model.

The point clouds in the non-characteristic region of the model are less preserved, but the point clouds are uniformly distributed in the space, which can avoid the occurrence of holes in the simplified results very well. Figure 4 shows the reconstruction results of point cloud surface under different simplification rates of the denture model. Comparing the reconstruction effect of the original denture point cloud data and the denture model with different reduction rates. The surface reconstruction effect of the model is very good when the simplification rate is 20%, 50% and 70%, the detailed features of the model can be completely retained, and the simplified reconstruction model has a high smoothness. When the simplification rate reaches 80%, some texture information and local detail features will be lost due to the high simplification rate. For example, the surface of the reconstructed model is not smooth enough, and there is a cavity in the tooth space like the bridge data. However, on the whole, the simplified model retains the outline and detailed features of the model well.

4.3 Comparison experiments of different algorithms

In order to further verify the superiority of the proposed algorithm, the random sampling method, the simplified method based on curvature and adaptive octree clustering are respectively used to be compared with the proposed algorithm in this paper. The experimental object is the denture bridge model with more features. In order to judge the simplification results of different simplification algorithms more accurately, each simplification algorithm has a similar simplification rate and it should be set to about 70%. Figure 5 shows the simplified results of the bridge model with different algorithms:

Figure 5.

Simplified results of bridge models with different algorithms (a) Original data (b) The algorithm in this paper (c) Random sampling method (d) The simplified method based on curvature (e) The simplified method based on adaptive octree clustering.

Figure 5(a) is the original dental bridge data model. The number of point clouds is 36 388, which contains a lot of redundant data. Figure 5(b) is the result of the point cloud simplification algorithm based on feature preserving in this paper. The number of point clouds is 10 954 after simplification. The algorithm in this paper concentrates more points on the feature region of the model through multi-feature extraction. The edge of the model was completely retained, the tooth contour was clear, and the detailed features of the denture occlusal surface were maintained well, the points number retained in the non-characteristic area was significantly reduced, as well as the distribution was relatively uniform, so as to ensure smooth and cave-free reconstruction results. Figure 5(c) adopts the random sampling method; The simplified result can be obtained by establishing a function that can generate random numbers to delete the corresponding points of random numbers from the original data. The number of point clouds is 12 130 after simplification, and the simplification rate is 67%. The algorithm has great randomness. As a result, only the basic contour points of teeth are retained, but the detailed features are seriously lost. Figure 5(d) is the result of the simplified method based on curvature. The number of point clouds retained is 11798. This method highlights the curvature of the model, but it retains too many points where the curvature is higher, and too few the points where the curvature is lower. Moreover, this method does not consider the boundary so that the simplification effect is poor. Figure 5(e) shows the results of the simplified method based on adaptive octree clustering, with 11 178 reserved points. This method cannot fully extract the detailed features of the model from the point cloud, and considers boundary conditions, but the simplified results are relatively good.

The Geomagic software was used to reconstruct the 3D surface focusing on the original cloud data of bridge point and the point cloud data simplified by different algorithms. The reconstruction results of the tooth bridge model with different simplified algorithms are shown in Fig. 6 by comparing the reconstruction effects of different algorithms.

xIn this paper, the execution time of different algorithms is recorded under the same system environment. Moreover, in order to quantitatively analyze the results of different simplification algorithms, we take advantage of the standard deviation value after simplification between the reconstructed surface and the original surface to measure the precision of point cloud simplification. The running time and standard deviation of different algorithms are shown in Table 2.

Table 2

Running time and standard deviation of different algorithms

Experimental algorithm	Total points	Points after simplification	Simplification rate	Running time (s)	The standard deviation
The method of this paper	36388	10954	70%	22.7	4.9 $\times$ 10 ${}^{-3}$
The simplified method based on random sampling	36388	12130	67%	9.4	7.1 $\times$ 10 ${}^{-3}$
The simplified method based on curvature	36388	11798	68%	16.4	7.7 $\times$ 10 ${}^{-3}$
The simplified method based on octree clustering	36388	11178	69%	40.5	6.0 $\times$ 10 ${}^{-3}$

Figure 6.

Reconstruction results of tooth bridge model with different simplified algorithms (a) Original data (b) The algorithm in this paper (c) The simplified method based on random sampling (d) The simplified method based on curvature (e) The simplified method based on adaptive octree clustering.

According to the reconstruction results in Fig. 6 and Table 2, the effect of model reconstruction in this algorithm is obviously better than other algorithms under the premise of similar simplification rate. In this paper, the algorithm does not directly simplify the point cloud data, but considers the characteristic region and non-characteristic region of the model respectively. For the feature area, this paper adopts the method of multi-feature discrimination to retain the detailed features of the denture model. It makes the simplified data better highlight the features of the point cloud model, thus improves the accuracy of the algorithm. For non-characteristic regions, this paper adopts the method of octree K-means clustering subdivision to simplify the non-characteristic point cloud. The simplified results are more uniform and smoother in the non-characteristic region, and the cavitation phenomenon can be effectively avoided. Moreover, the simplified model has better smoothness, and the accuracy is obviously better than other algorithms. The algorithm in this paper runs slowly because the multi-feature calculation reduces the overall operating efficiency. The simplified method based on random sampling runs faster. However, combined with the above experimental results, the algorithm sacrifices simplified accuracy. The simplification of feature area and non-feature area of model is similar, the effect of detail feature preserving is not good, and the loss of the data between teeth is serious. The reconstruction effect of the simplified method based on curvature is the worst and the algorithm accuracy are the lowest. The over-simplification of non-characteristic region leads to the cavity problem and the loss of edge features. The simplified method based on adaptive octree clustering can obtain smoother simplification results, but it also fails to consider the edge characteristics of the model so that the edge part of the model is lost and the interdental data is not fully retained. Moreover, the complexity of the algorithm time is the highest because the feature region and the non-feature region are not considered separately.

Compared with other algorithms, the algorithm in this paper not only can retain the detailed features of the model completely, but also effectively simplify the non-feature areas of the model. It can simplify complex denture models while ensuring the accuracy of simplification.

5. Conclusion

In this paper, a point cloud simplification algorithm based on feature preserving is proposed, which can be effectively applied to complex oral scan denture model. Through analysis of the acquired denture data, it is found that the detailed features are mostly located in dental occlusion part, margin and the connection part of the teeth. There are few sharp features around the tooth wall. Therefore, the difficulty in the study of the simplification algorithm based on the denture data is how to extract the detailed features and how to use fewer points to replace the non-characteristic areas of the denture. According to the structure of the denture model, multiple features are specifically extracted to construct the feature discriminant function. The detailed features of the denture model are retained in the way of multi-feature discrimination, so that the simplified data can better highlight the features of the point cloud model, thus improving the accuracy of the algorithm. For the non-feature region of the model, K-means clustering method based on adaptive octree is proposed. Octree provides K value and initialized clustering center for K-means clustering algorithm, and then further iteratively subdivide by determining whether the maximum normal angle of data among clustering clusters meets the threshold value. This method can effectively improve the efficiency of the algorithm and obtain uniform simplification results of non-feature region.

In order to verify the validity of the algorithm, different simplification rates are adopted to simplify different denture models. Moreover, the simplification effects of the proposed algorithm are compared with other algorithms. The experiments show that the proposed algorithm in this paper is more suitable for complex digital denture models. The detailed features of denture point cloud can be clearly and accurately retained through multi-feature discrimination. It also can effectively solve the problem that the feature is easy to loss in the traditional simplification algorithm. The point cloud in the flat non-characteristic area is uniformly distributed without holes. And the reconstruction fitting model has higher smoothness, better edge information preserving, the accuracy is significantly higher than other algorithms. The algorithm can also effectively solve the problem that the feature preserving is incomplete and cavitation is easy to occur in relatively flat area when using other algorithms to process digital denture point cloud data. The simplified results have good smoothness, simplicity and precision, and it also have high practical value.

Footnotes

Acknowledgments

This work was supported by Liuzhou Science and Technology Project, Guangxi Province, China (Grant No. 2018DH10501) and Innovation Project of Guangxi Graduate Education (Grant No. YCSW2020218).

References

Tan

Zhou

M.H.

and Song

P.P.

, Research on equity of oral human resources allocation in China from the perspective of healthy oral cavity, Chinese Health Economics 38(12) (2019), 41–43.

Lee

S.J.

and Lee

J.D.

, Digital impressions for implant-supported fixed dental prostheses, Current Oral Health Reports 4 (2017), 136–141.

Mahdaoui

Bouazi

Hsaini

A.M.

and Sbai

E.H.

, Entropic method for 3D point cloud simplification, In: Ben Ahmed

Boudhir

(eds) Innovations in Smart Cities and Applications, SCAMS 2017, Lecture Notes in Networks and Systems, Springer, Cham, 37 (2018), pp. 613–621.

Shoaib

Cheong

Kim

and Cho

, Fractal bubble algorithm for simplification of 3D point cloud data, Journal of Intelligent & Fuzzy Systems 37(6) (2019), 7815–7830.

Yuan

X.C.

L.S.

and Chen

H.W.

, Feature preserving point cloud data simplification, Optical Precision Engineering 23(9) (2015), 2666–2676.

Shi

B.Q.

Liang

and Liu

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

Xuan

Hua

Chen

Zou

and He

, A new progressive simplification method for point cloud using local entropy of normal angle, Journal of the Indian Society of Remote Sensing 46 (2018), 581–589.

C.Y.

Ying

and Fan

J.H.

, A novel simplification method for 3D geometric point cloud based on the importance of point, In IEEE Access 7 (2019), 129029–129042.

Zhang

and Lu

, Research and application of personalized human body simplification and fusion method, EURASIP Journal on Image and Video Processing 55 (2018).

10.

Markovic

Jakovljevic

and Miljkovic

, Feature sensitive three-dimensional point cloud simplification using support vector regression, Technical Gazette 26(4) (2019), 985–994.

11.

Dong

J.M.

and Tian

, Point cloud simplification algorithm based on local entropy, Modern Electronic Technology 43(1) (2020), 20-23+27.

12.

Lee

J.M.

, Fast k-nearest neighbor searching in static objects, Wireless Personal Communications 93(1) (2017), 147–160.

13.

Liu

Z.Y.

Jiang

K.Y.

and Lin

J.Y.

, Interactive extraction of feature edges of scattered point clouds, Computer Engineering and Applications 52(6) (2016), 186–190.

14.

Lyu

Huang

Duan

and Li

, Modeling vehicle collision angle in traffic crashes based on three-dimensional laser scanning data, Sensors (Basel) 17(3) (2017), 482.

15.

Hoppe

Derose

Duchamp

Mcdonald

and Stuetzle

, Surface reconstruction from unorganized points, ACM SIGGRAPH Computer Graphics 26(2) (1992), 71–78.

16.

Pauly

Gross

and Kobbelt

L.P.

, Efficient simplification of point-sampled surfaces, Visualization 2002, pp. 163–170.