Innovative Methodology of On-Line Point Cloud Data Compression for Free-Form Surface Scanning Measurement

Featured Application

On-line point cloud data compression process for 3D free-form surface contact or non-contact scanning measuring equipment.

Abstract

In order to obtain a highly accurate profile of a measured three-dimensional (3D) free-form surface, a scanning measuring device has to produce extremely dense point cloud data with a great sampling rate. Bottlenecks are created owing to inefficiencies in manipulating, storing and transferring these data, and parametric modelling from them is quite time-consuming work. In order to effectively compress the dense point cloud data obtained from a 3D free-form surface during the real-time scanning measuring process, this paper presents an innovative methodology of an on-line point cloud data compression algorithm for 3D free-form surface scanning measurement. It has the ability to identify and eliminate data redundancy caused by geometric feature similarity between adjacent scanning layers. At first, the new algorithm adopts the bi-Akima method to compress the initial point cloud data; next, the data redundancy existing in the compressed point cloud is further identified and eliminated; then, we can get the final compressed point cloud data. Finally, the experiment is conducted, and the results demonstrate that the proposed algorithm is capable of obtaining high-quality data compression results with higher data compression ratios than other existing on-line point cloud data compression/reduction methods.

1. Introduction

With the rapid development of modern industry, three-dimensional (3D) free-form surface parts are being utilized more and more widely. These involve, but are not limited to, aviation, aerospace, shipbuilding, automotive, biomedical and home appliance industries [1,2]. Recently, the automated 3D digitization of free-form surface objects has been widely applied in many areas, such as additive manufacturing (3D printing), rapid prototyping, reverse engineering, civil buildings, medical prosthetics and clinical diagnosis [3,4,5,6,7,8,9,10,11,12,13]. Scanning measurement is one of the key technologies for digitizing 3D physical models with free-form surfaces [14,15,16,17]. Unfortunately, in order to obtain a high-quality profile of a measured surface, scanning measuring devices have to produce massive amounts of point cloud data with great sampling rates, and not all these points are indispensable [18,19,20]. Bottlenecks arise from the inefficiencies of storing, manipulating and transferring them [21]. Furthermore, the parametric modelling from these massive amount of point cloud data is a time-consuming task [22,23,24]. For this reason, compressing the measured point data while maintaining the required accuracy is a crucial task during the scanning measuring process [25]. Herein, the required accuracy is a threshold of distance, which is preset to a constant positive integer before the beginning of scanning measurement. The accuracy of a certain data compression algorithm is characterized by the distance from each sampled point in the initial dense point cloud data to the surface generated by the compressed point cloud. Describing a measured surface with the least point data while guaranteeing a certain data compression accuracy is always an expectation [26,27]. Therefore, a high-quality point cloud data compression algorithm for 3D free-form surface scanning measurement is being pursued constantly [28].

Experts and scholars around the world have been paying more and more attention to this issue, and a number of point cloud data compression/reduction algorithms for free-form/irregular surface scanning measurement have been developed. Lee et al. [29] proposed an algorithm for processing point cloud data obtained by laser scanning devices. This algorithm adopts a one-directional (1D) or bi-directional (2D) non-uniform grid to reduce the amount of point cloud data. Chen et al. [5] presented a data compression method based on a bi-directional point cloud slicing strategy for reverse engineering. This method can preserve local details (geometric features in both two parametric directions) when performing data compression. Ma and Cripps [30] proposed a new data compression algorithm for surface points to preserve the original surface points. The error metric is defined as the relative Hausdorff distance between two principal curvature vector sets for surface shape comparison. After comparison, the difference between the compressed data points and original data points can be obtained. Therefore, redundant points are repeatedly removed until the difference induced exceeds the specified tolerance. Smith, Petrova, and Schaefer [31] presented a progressive encoding and compression method for surfaces generated from point cloud data. At first, an octree is built whose nodes contain planes that are constructed as the least square fit of the data within that node. Then, this octree is pruned to remove redundant data while avoiding topological changes created by merging disjointed linear pieces. Morell et al. [32] presented a geometric 3D point cloud lossy compression system based on plane extraction, which represents the points of each scene plane as a Delaunay triangulation and a set of points/area information. This compression system can be customized to achieve different data compression or accuracy ratios. The above methods have focused on optimizing data compression quality based on building and processing polyhedral models or numerical iterative calculations. Nevertheless, they are all off-line data compression algorithms and can only compress the point cloud data of a whole measured surface after data acquisition. In other words, they cannot perform online data compression during real-time measurement. Data acquisition and data compression processes are completely separate. A large amount of redundant point cloud data occupies a great deal of storage space in scanning measuring devices. Moreover, the transmission and processing of point cloud data still takes up a significant amount of time and hardware resources.

This problem has attracted the attention of many scholars and engineers, and they have proposed quite a number of on-line point cloud data compression/reduction methods. Lu et al. [33] adopted the chordal method to compress point cloud data, and realized the on-line data compression of point cloud data during real-time scanning measurement for the first time. ElKott and Veldhuis [34] presented an automatic surface sampling approach based on scanning isoparametric lines. The sampling locations are confirmed by the deviations between the alternative geometry and sampled model, and the location of each sampling line is confirmed by the curvature of the sampled surface model. Wozniak, Balazinski, and Mayer [35] presented a point cloud data compression method based on fuzzy logic and the geometric solution of an arc at each measured point. This is an on-line data compression method and can be used in the surface scanning measuring process of coordinate measuring machines (CMMs). Jia et al. [36] proposed an on-line data compression method based on the equal-error chordal method and isochronous sampling. In order to solve the problem of massive data storage, dual-buffer and dual-thread dynamic storage is adopted. Tao et al. [37] found that the essence of all the above on-line point cloud data compression methods is the chordal method, which specifies that all discrete dense point sets are connected by straight segments. Therefore, the surface reconstructed by the compressed point cloud will be full of cusp points, and so we cannot obtain a smooth interpolated surface. In view of this limitation, they presented an on-line point cloud data extraction algorithm using bi-Akima spline interpolation.

Although the above methods implement on-line point cloud data compression, they can only eliminate data redundancy of the current scanning line. Nevertheless, most surface 3D scanning measuring devices adopt a layer-by-layer scanning path (e.g., contact scanning probes [38], laser triangle displacement sensors [39], linear structured light systems [40], industrial computed tomography (CT) systems [41], etc.), and adjacent scanning lines are extremely similar in shape. The geometric feature similarity between such scanning layers is bound to result in data redundancy, which makes it possible to further compress the point cloud data during the scanning measuring process. Therefore, this study focuses on identifying and eliminating this kind of data redundancy caused by geometric feature similarity between adjacent scanning layers. After that, the massive amount of point cloud data can be further compressed during the 3D free-form surface measuring process.

The contents of this paper consist of four sections. In Section 2, the innovative methodology of the on-line point cloud data compression algorithm for 3D free-form surface scanning measurement is described in detail. In Section 3, the proposed algorithm was tested in the real-time scanning measuring process and compared with existing methods. Finally, some conclusions are drawn from this paper in Section 4.

2. Innovative Methodology

As shown in Figure 1, the overall process of on-line point cloud data compression in this work consists of four steps. In Step 1, the initial point cloud flow is obtained by 3D scanning measuring devices using an isochronous [42] or equidistant sampling method and the layer-by-layer scanning path is adopted (Figure 2). In Step 2, the initial point cloud data flow is immediately compressed by the chordal method [36] or bi-Akima method [37], both of which compress the amount of point cloud data based on the data redundancy in the current single scanning layer. In Step 3, the data redundancy in the compressed point cloud which is obtained in the previous step is further identified. In Step 4, the identified redundant point data is eliminated, and then we can obtain the final compressed point cloud. At last, the final compressed data flow is transmitted to the storage space of the measurement system.

Herein, the real-time performance of the proposed data compression algorithm needs to be further analyzed and described. The path planning is performed before the start of the scanning measurement in Step 1. As shown in Figure 2, a layer-by-layer scanning path is adopted. The distance between the adjacent scanning layers is determined by the preset measuring accuracy. The measured surface is cut by the scanning layers to form a number of corresponding scanning lines. As shown in Figure 2, there are two planning modes for scanning directions: (i) the progressive scanning mode, and (ii) the S-type scanning mode. Regardless of the scanning mode, the measuring device in Step 1 will continuously transmit the initial point cloud data flow to the data compressor in Step 2. The compressor performs data compression immediately after receiving all initial point data of a single scanning layer, rather than waiting for the entire surface to be scanned before performing data compression. That is, each time the point cloud data in the current scanning layer is completely transmitted to the compressor, the subsequent data compression algorithm is executed immediately. Therefore, the proposed data compression algorithm is essentially a quasi-real-time method, which we call an on-line data compression method.

The flow chart of this algorithm is illustrated in Figure 3, and its principle is described in detail as follows:

2.1. Data Redundancy Identification

In order to identify redundant data points in the compressed point cloud data flow from Step 2, it is first necessary to predict the current scan line in the unmeasured area. Herein, the prediction is realized by Hermite extrapolation [43], and a predicted curve is created. The data redundancy identification algorithm is detailed as follows:

Figure 4 shows the schematic diagram of the data redundancy identification algorithm, in which line $i$ is the current scanning line during the on-line measuring process, and $P_{i,j}$ represents the $j$th point in scanning line $i$. If $j\ge 2$, a shape-preserving piecewise bicubic Hermite curve can be built to predict the shape and direction of the current scanning line; here, we name this the predicted curve, as shown in Figure 4. After that, suppose $k$ is a positive integer and let $1\le k<j$ and the coordinates of point $P_{i,k}$ be $(x_k,y_k,z_k)$; then, a series of specific Hermite interpolation polynomials can be determined by

$$\{\begin{array}{l}{H}_y(x)=y_k{\alpha }_k(x)+y_{k+1}{\alpha }_{k+1}(x)+{y^{\prime }}_k{\beta }_k(x)+{y^{\prime }}_{k+1}{\beta }_{k+1}(x)\\ H_z(x)=z_k{\alpha }_k(x)+z_{k+1}{\alpha }_{k+1}(x)+{z^{\prime }}_k{\beta }_k(x)+{z^{\prime }}_{k+1}{\beta }_{k+1}(x)\end{array},$$

(1)

where

$$\{\begin{array}{l}{\alpha }_k(x)=\left(1+2\frac{x-x_k}{x_{k+1}-x_k}\right){\left(\frac{x-x_{k+1}}{x_k-x_{k+1}}\right)}^2\\ {\alpha }_{k+1}(x)=\left(1+2\frac{x-x_{k+1}}{x_k-x_{k+1}}\right){\left(\frac{x-x_k}{x_{k+1}-x_k}\right)}^2\\ {\beta }_k(x)=\left(x-x_k\right){\left(\frac{x-x_{k+1}}{x_k-x_{k+1}}\right)}^2\\ {\beta }_{k+1}(x)=\left(x-x_{k+1}\right){\left(\frac{x-x_k}{x_{k+1}-x_k}\right)}^2\end{array},$$

(2)

and the first derivatives of ${y^{\prime }}_k$, ${y^{\prime }}_{k+1}$, ${z^{\prime }}_k$, ${z^{\prime }}_{k+1}$ can be estimated by the following formulas.

When $1<k<j$:

$${y^{\prime }}_k={f_y}^{\prime }(x_k)=\{\begin{array}{l}0,\hspace{1em}\hspace{1em}\hspace{1em}if:\frac{y_{k+1}-y_k}{x_{k+1}-x_k}·\frac{y_k-y_{k-1}}{x_k-x_{k-1}}<0\\ \frac{1}{2}\left(\frac{y_{k+1}-y_k}{x_{k+1}-x_k}+\frac{y_k-y_{k-1}}{x_k-x_{k-1}}\right),\hspace{1em}\hspace{1em}\hspace{1em}if:\frac{y_{k+1}-y_k}{x_{k+1}-x_k}·\frac{y_k-y_{k-1}}{x_k-x_{k-1}}\ge 0\end{array},$$

(3)

$${z^{\prime }}_k={f_z}^{\prime }(x_k)=\{\begin{array}{l}0,\hspace{1em}\hspace{1em}\hspace{1em}if:\frac{z_{k+1}-z_k}{x_{k+1}-x_k}·\frac{z_k-z_{k-1}}{x_k-x_{k-1}}<0\\ \frac{1}{2}\left(\frac{z_{k+1}-z_k}{x_{k+1}-x_k}+\frac{z_k-z_{k-1}}{x_k-x_{k-1}}\right),\hspace{1em}\hspace{1em}\hspace{1em}if:\frac{z_{k+1}-z_k}{x_{k+1}-x_k}·\frac{z_k-z_{k-1}}{x_k-x_{k-1}}\ge 0\end{array}.$$

(4)

When $k=1$:

$${y^{\prime }}_1=\{\begin{array}{l}0,\hspace{1em}\hspace{1em}\hspace{1em}if:d_y·\frac{y_2-y_1}{x_2-x_1}<0\\ 3·\frac{y_2-y_1}{x_2-x_1},\hspace{1em}\hspace{1em}\hspace{1em}if:\left|d_y\right|>3\left|\frac{y_2-y_1}{x_2-x_1}\right|\&\frac{(y_2-y_1)(y_3-y_2)}{(x_2-x_1)(x_3-x_2)}<0\end{array},$$

(5)

$${z^{\prime }}_1=\{\begin{array}{l}0,\hspace{1em}\hspace{1em}\hspace{1em}if:d_z·\frac{z_2-z_1}{x_2-x_1}<0\\ 3·\frac{z_2-z_1}{x_2-x_1},\hspace{1em}\hspace{1em}\hspace{1em}if:\left|d_z\right|>3\left|\frac{z_2-z_1}{x_2-x_1}\right|\&\frac{(z_2-z_1)(z_3-z_2)}{(x_2-x_1)(x_3-x_2)}<0\end{array},$$

(6)

in which

$$\{\begin{array}{l}{d}_y=\frac{(x_3+x_2-2x_1)(y_2-y_1)}{(x_2-x_1)(x_3-x_1)}-\frac{(x_2-x_1)(y_3-y_2)}{(x_3-x_2)(x_3-x_1)}\\ d_z=\frac{(x_3+x_2-2x_1)(z_2-z_1)}{(x_2-x_1)(x_3-x_1)}-\frac{(x_2-x_1)(z_3-z_2)}{(x_3-x_2)(x_3-x_1)}\end{array}.$$

(7)

When $k=j$:

$${y^{\prime }}_j=\{\begin{array}{l}0,\hspace{1em}\hspace{1em}\hspace{1em}if:d_y·\frac{y_j-y_{j-1}}{x_j-x_{j-1}}<0\\ 3·\frac{y_j-y_{j-1}}{x_j-x_{j-1}},\hspace{1em}\hspace{1em}\hspace{1em}if:\left|e_y\right|>3\left|\frac{y_j-y_{j-1}}{x_j-x_{j-1}}\right|\&\frac{(y_j-y_{j-1})(y_{j-1}-y_{j-2})}{(x_j-x_{j-1})(x_{j-1}-x_{j-2})}<0\end{array},$$

(8)

$${z^{\prime }}_j=\{\begin{array}{l}0,\hspace{1em}\hspace{1em}\hspace{1em}if:d_y·\frac{z_j-z_{j-1}}{x_j-x_{j-1}}<0\\ 3·\frac{z_j-z_{j-1}}{x_j-x_{j-1}},\hspace{1em}\hspace{1em}\hspace{1em}if:\left|e_z\right|>3\left|\frac{z_j-z_{j-1}}{x_j-x_{j-1}}\right|\&\frac{(z_j-z_{j-1})(z_{j-1}-z_{j-2})}{(x_j-x_{j-1})(x_{j-1}-x_{j-2})}<0\end{array},$$

(9)

in which

$$\{\begin{array}{l}{e}_y=\frac{(2x_j-x_{j-1}-x_{j-2})(y_j-y_{j-1})}{(x_j-x_{j-1})(x_j-x_{j-2})}-\frac{(x_j-x_{j-1})(y_{j-1}-y_{j-2})}{(x_{j-1}-x_{j-2})(x_j-x_{j-2})}\\ e_z=\frac{(2x_j-x_{j-1}-x_{j-2})(z_j-z_{j-1})}{(x_j-x_{j-1})(x_j-x_{j-2})}-\frac{(x_j-x_{j-1})(z_{j-1}-z_{j-2})}{(x_{j-1}-x_{j-2})(x_j-x_{j-2})}\end{array}.$$

(10)

Herein, based on the compressed point cloud data flow from Step 2, the shape-preserving piecewise bicubic Hermite polynomials can be created according to the above algorithm. Then, Hermite extrapolation is performed to create a predicted curve, which is marked in blue as shown in Figure 4, and its analytical formula can be described as follows:

$$\{\begin{array}{l}{H}_y(x)=y_{j-1}{\alpha }_{j-1}(x)+y_j{\alpha }_j(x)+{y^{\prime }}_{j-1}{\beta }_{j-1}(x)+{y^{\prime }}_j{\beta }_j(x)\\ H_z(x)=z_{j-1}{\alpha }_{j-1}(x)+z_j{\alpha }_j(x)+{z^{\prime }}_{j-1}{\beta }_{j-1}(x)+{z^{\prime }}_j{\beta }_j(x)\end{array}.$$

(11)

After that, an estimated point $P_{est}$ is created to move along the predicted curve with a stepping distance of $\lambda$. $P_{i,j}$ is the starting point of $P_{est}$. Meanwhile, a bounding sphere is built with point $P_{est}$ as the center. The radius of the sphere is

$$R_{sph}=\kappa h_{ls},$$

(12)

in which $\kappa \in [1,2]$ is the radius adjustment coefficient, and $h_{ls}$ is the distance between two parallel scannning layers. As shown in Figure 4, the predicted curve with estimated point $P_{est}$ are used to search for the neighbor point $P_{nb}$ from the previous scanning line i−1. The necessary and sufficient conditions for point $P_{nb}$ as the neighbor point of $P_{est}$ are $\left|\overline{P_{est}{P}_{nb}}\right|\le R_{sph}$, which means that $P_{nb}$ is inside the bounding sphere with point $P_{est}$ as its center. At the very beginning, $P_{est}$ coincides with $P_{i,j}$. At this point, there are two possibilities: (i) $P_{i-1,u}$ is inside the bounding sphere (i.e., $\left|\overline{P_{i-1,u}{P}_{i,j}}\right|\le R_{sph}$), or (ii) $P_{i-1,u}$ is outside the bounding sphere. In case (i), $P_{i-1,u}$ is the first found neighbor point. As $P_{est}$ moves along the scanning direction with a stepping distance of $\lambda$, if $\left|\overline{P_{est}{P}_{i-1,u}}\right|<\left|\overline{P_{i,j}{P}_{i-1,u}}\right|$, then $P_{i-1,u}$ is the neighbor point of $P_{est}$; otherwise, discard point $P_{i-1,u}$, as it is not the neighbor point of $P_{est}$ but of $P_{i,j}$. In case (ii), there is no operation because no neighbor point has been found. After case (i) or case (ii) is completed, point $P_{est}$ continues to move forward along the scanning direction until the neighbor point $P_{nb}$ of $P_{est}$ is found; if the neighbor point cannot be found, the search is stopped.

If the neighbor point $P_{nb}$ is found in line $i-1$ (e.g., $P_{i-1,u+1}$ in Figure 4), then a new bounding sphere is built with $P_{i-1,u+1}$ as the center and the radius is $R_{sph}$. After that, we use this new bounding sphere to search for the neighbor point of $P_{i-1,u+1}$ in line $i-2$; and if the neighbor point cannot be found, we stop searching. Next, we take the new neighbor point in line $i-2$ (e.g., $P_{i-2,v+1}$) as a new center to build a bounding sphere and repeat the above process until we find three neighbor points in different scanning lines (e.g., $P_{i-1,u+1}$, $P_{i-2,v+1}$, $P_{i-3,w+1}$ in Figure 4).

Based on the neighbor point set {$P_{i-1,u+1}$, $P_{i-2,v+1}$, $P_{i-3,w+1}$}, the coordinates of estimated point $P_{est}$ can be fixed uniquely. As shown in Figure 4, a bi-cubic Hermite curve is built, and it can be expressed as

$$\{\begin{array}{l}{H}_x(y)=x_{i-2}{\alpha }_{i-2}(y)+x_{i-1}{\alpha }_{i-1}(y)+{x^{\prime }}_{i-2}{\beta }_{i-2}(y)+{x^{\prime }}_{i-1}{\beta }_{i-1}(y)\\ H_z(y)=z_{i-2}{\alpha }_{i-2}(y)+z_{i-1}{\alpha }_{i-1}(y)+{z^{\prime }}_{i-2}{\beta }_{i-2}(y)+{z^{\prime }}_{i-1}{\beta }_{i-1}(y)\end{array},$$

(13)

in which $y$ is an independent variable; ${\alpha }_{i-1}(y)$, ${\alpha }_{i-2}(y)$, ${\beta }_{i-1}(y)$, ${\beta }_{i-2}(y)$ are obtained by Equation (2); ${x^{\prime }}_{i-2}$, ${z^{\prime }}_{i-2}$ are acquired by Equations (3) and (4); and ${x^{\prime }}_{i-1}$, ${z^{\prime }}_{i-1}$ are obtained by Equations (8)–(10). Obviously, the bicubic Hermite curve must be in the curved surface with the equation

$$H_x(y)=x_{i-2}{\alpha }_{i-2}(y)+x_{i-1}{\alpha }_{i-1}(y)+{x^{\prime }}_{i-2}{\beta }_{i-2}(y)+{x^{\prime }}_{i-1}{\beta }_{i-1}(y),$$

(14)

and the predicted curve will pass through this curved surface. Therefore, estimated point $P_{est}$ can be fixed at the intersection of the predicted curve and the curved surface which is described in Equation (14). That is, the coordinates of estimated point $P_{est}(x_{est},y_{est},z_{est})$ can be determined by Equations (11) and (14).

2.2. Data Redundancy Elimination

After the coordinates of estimated point $P_{est}$ are determined, we use $P_{est}$ to replace $P_{i,j+1}$ in scanning line i. Afterwards, the new point set that contains $P_{est}$ is used for bi-Akima interpolation, and there is a deviation $h_{i,k}$ between the interpolated curve and each initial sampled point $Q_k$, where i is the scanning line number and k is the serial number of initial point cloud in line i. As mentioned earlier, the initial point cloud is obtained by 3D scanning measuring devices using the isochronous or equidistant sampling method in Step 1 as shown in Figure 1. The deviation $h_{i,k}$ can be obtained by

$$h_{i,k}=\underset{x\in (X_j,X_{j+1})}{\mathrm{MIN}}(s)=\underset{x\in (X_j,X_{j+1})}{\mathrm{MIN}}\left(\sqrt{{(x-x_k)}^2+{(y-y_k)}^2+{(z-z_k)}^2}\right),$$

(15)

where point $Q_k(x_k,y_k,z_k)$ is an initial sampled point between $P_{i,j}(X_j,Y_j,Z_j)$ and $P_{i,j+1}(X_{j+1},Y_{j+1},Z_{j+1})$, and $P_{curv}(x,y,z)$ is the point in interpolated curve that makes the distance S shortest. Then, the max deviation $d_{\max }$ of the whole curve (i.e., from $P_{i,1}$ to $P_{est}$) can be calculated by the following formula:

$$d_{\max }=\mathrm{MAX}(h_{i,k}),$$

(16)

which is compared with the required accuracy $\epsilon$. If $d_{\max }>\epsilon$, discard point $P_{est}$. If $d_{\max }<\epsilon$, delete current compressed point $P_{i,j+1}$ which is input from Step 2. Next, create an estimative flag $F_{i,j+1}=1$ to replace point $P_{i,j+1}$. This flag takes up only one bit of data storage space. After completing the above process, output the final compressed point cloud data flow, which contains the point coordinate and estimative flag information to the data storage devices. Afterwards, make $j=j+1$, build a new shape-preserving piecewise bicubic Hermite curve to predict the shape and direction of the current scanning line, and create a new estimative point $P_{est}$ to loop through the above data redundancy identification and elimination process until $P_{i,j}$ is the end point of the current scanning line i or the data sampling is over. In addition, when $P_{i,j}$ is the end point of line i, make $i=i+1$ and continue to loop the above algorithm until the measurement is completed.

3. Experimental Results

In order to verify the feasibility of the proposed methodology, some experiments were performed in this section.

3.1. Test A

The on-line point cloud data compression algorithm was tested in the industrial real-time measuring process and compared with existing methods (chordal method and bi-Akima method). The measuring system consists of a contact 3D scanning probe, a vertical lathe and a commercial computer numerical control (CNC) system of SINUMERIK 840D (Munich, Bayern, Germany) as shown in Figure 5. The proposed algorithm is integrated in the original equipment manufacturer (OEM) application that runs on the host computer of the CNC system. The product model of the contact 3D scanning probe is DIGIT-02 (Dalian, Liaoning Province, China). More detailed technical characteristics of the measuring instrument are shown in

Table 1. Detailed technical characteristics of the measuring system.

Technical Characteristics	Values
Scope of X axis	2400 mm
Positioning accuracy of X axis	0.019 mm/1000 mm
Repeatability of X axis	0.016 mm/1000 mm
Scope of Z axis	1200 mm
Positioning accuracy of Z axis	0.010 mm/1000 mm
Repeatability of Z axis	0.003 mm/1000 mm
Positioning accuracy of C axis	6.05″
Repeatability of C axis	2.22″
Measuring range of scanning probe	±1 mm
Accuracy of scanning probe	±8 μm
Repeatability of scanning probe	±4 μm
Stylus length of probe	100 mm/150 mm/200 mm
Contact force (with stylus of 200 mm)	1.6 N/mm
Weight of scanning probe	1.8 kg

.

The measured part is a half-ellipsoidal surface which is welded together by seven pieces of thin-walled aluminum alloy sheet, as shown in Figure 5d, with a semi-major axis of 1450 mm and semi-minor axis of 950 mm. A rotational progressive scanning mode is adopted, and the layer spacing is 7 mm. Figure 6 shows the spatial distribution of the initial point cloud data. The isochronous sampling method is adopted and the number of initial sampling points is 272,638.

Using the same initial point cloud data set as shown in Figure 6, the comparison of data compression performance is made between the proposed method, chordal method and bi-Akima method under different required accuracies (i.e., from 0.001 mm to 1 mm).

Table 2. Compression performance under different required accuracies.

Required Accuracy (mm)	Number of Points			Compression Ratio
	Chordal Method	Bi-Akima Method	Proposed Method	Chordal Method	Bi-Akima Method	Proposed Method
0.001	237,363	122,929	67,448	1.15	2.22	4.04
0.002	189,824	120,952	67,121	1.44	2.25	4.06
0.005	152,674	110,175	63,813	1.79	2.47	4.27
0.01	136,027	93,588	51,062	2.00	2.91	5.34
0.02	123,891	71,629	41,862	2.20	3.81	6.51
0.05	103,205	44,072	28,837	2.64	6.19	9.45
0.1	87,008	27,894	15,974	3.13	9.77	17.07
0.2	61,124	12,191	7102	4.46	22.36	38.39
0.5	28,473	5594	3140	9.58	48.74	86.83
1	9029	3969	2217	30.20	68.69	122.99

summarizes the results of the data compression performance including the number of points and data compression ratio, where the compression ratio is defined as the ratio between the uncompressed size and compressed size:

$$\mathrm{Compression} \mathrm{Ratio}=\frac{\mathrm{Uncompressed} \mathrm{Size}}{\mathrm{Compressed} \mathrm{Size}}=\frac{\mathrm{Number} \mathrm{of} \mathrm{Initial} \mathrm{Points}}{\mathrm{Number} \mathrm{of} \mathrm{Compressed} \mathrm{Points}}.$$

(17)

Obviously, the proposed method has a higher data compression ratio than the chordal method and bi-Akima method, and the chordal method obtains the lowest data compression ratio under the same required accuracy. The number of data points obtained by the proposed method is about half of that obtained by the bi-Akima method under the same required accuracy.

Figure 7 provides the comparison of the compression ratios between the three methods under the different required accuracies. With the decrease in accuracy requirements, the compression ratio increases for all methods; however, for all levels of required accuracy, our proposed compression method manifests a superior compression ratio than the other two methods. Obviously, the chordal method has the lowest data compression ratio. Therefore, we focus on comparing our proposed method with the bi-Akima method in the subsequent experiments.

To make the comparison more vivid and intuitive, Figure 8 visually illustrates the difference between the proposed method and bi-Akima method by displaying spatial distributions of compressed point sets under different required accuracies. Subfigures a, d, g and j show the point cloud distribution compressed by bi-Akima method while subfigures b, e, h and k give the point cloud distribution after data redundancy identification by the proposed method, with the identified redundant points marked in red. In subfigures c, f, i and l, the identified redundant points are eliminated. These subfigures show the distributions of the final compressed point cloud data. By contrast, we can clearly observe the difference of point cloud density between these two methods under the same required accuracy. Take subfigures g–i, for example: when using the bi-Akima method, we can observe that there are many curves roughly along the welded region (Figure 8g), because the bi-Akima method can only deal with the point set in the current scanning line and the data redundancy outside the current scanning line cannot be eliminated. With the involvement of our proposed method, redundant data points are identified and marked in red (Figure 8h) and the data redundancy in the adjacent scanning layers is eliminated and the final compressed point cloud data is obtained (Figure 8i).

To verify the accuracy of the proposed algorithm, Figure 9 analyzes the spatial distribution of deviation between each initial sampled point and the interpolated surface obtained from the final compressed point cloud data under different required accuracies. As can be seen, all the deviations are within the allowable range of required accuracy. Our method can tightly control the deviation within the error tolerance range (i.e., the deviation between each initial sampled point and interpolation curve is less than or equal to the required accuracy). In addition, deviations are far lower than the required accuracy in most of the measured area. In Figure 9d, there is an interesting and noteworthy phenomenon: the upper right sector has a higher deviation. As mentioned earlier, the measured part is a large thin-walled surface which is welded together by seven pieces of aluminum alloy sheet (Figure 5d). The aluminum alloy sheet has a thickness of only 0.8 mm, but its size is very large (the semi-major axis of the ellipse is 1450 mm). The part has undergone great deformation after welding. There is a large and random deviation between each welded part and the original design size. According to past experience, the maximum deviation in a local section can even reach 3 mm. Consequently, we infer that the upper right sector has a higher deviation because of deformation in this area. In the case where the required accuracy is on the order of millimeters (e.g., required accuracy $\epsilon =1 \mathrm{mm}$ in Figure 9d), the compressed point cloud data is very sparse. Therefore, this phenomenon is formed in a region where the point cloud density is low and the local deformation is large. However, in any case, the proposed method can tightly control the deviation within the preset range.

3.2. Test B

The overall structure of the model in Test A is relatively simple. In order to further verify the universality and adaptability of the proposed method, we chose a more complex surface model with a large number of details, edges and sharp features for experimentation. As shown in Figure 10, the tested model is a piece of jewelry, which is inlaid with 30 diamonds of different sizes.

Figure 11 shows the initial point cloud data acquisition result. The progressive scanning mode and equidistant sampling mode were adopted. Scanning lines are along the X-direction (horizontal direction). The distance between two adjacent scanning layers is 0.1 mm, and the distance between adjacent points is 0.05 mm in each scanning layer. The initial point number is 63,376.

The comparison is made between the proposed method and bi-Akima method under different required accuracies (i.e., from 0.001 mm to 1 mm).

Table 3. Compression performance under different required accuracies.

Required Accuracy (mm)	Number of Points		Compression Ratio
	Bi-Akima Method	Proposed Method	Bi-Akima Method	Proposed Method
0.001	18,906	8516	3.35	7.44
0.002	16,857	7609	3.76	8.33
0.005	14,323	6563	4.42	9.66
0.01	12,432	5743	5.10	11.04
0.02	10,720	5007	5.91	12.66
0.05	8767	4232	7.23	14.98
0.1	7190	3535	8.81	17.93
0.2	5892	2974	10.76	21.31
0.5	4625	2412	13.70	26.28
1	4204	2213	15.08	28.64

gives the results of data compression performance, including the number of points and data compression ratio. Obviously, the proposed method has a higher data compression ratio than the bi-Akima method. The number of points obtained by the proposed method is about half of that obtained by bi-Akima method under the same required accuracy.

Figure 12 provides the comparison of the compression ratios between these two methods under different required accuracies. With the decrease in accuracy requirements, the compression ratio increases for all methods; however, for all levels of required accuracy, our proposed compression method manifests a superior compression ratio than the bi-Akima method.

Figure 13 visually illustrates the difference between the proposed method and bi-Akima method by displaying spatial distributions of the compressed point sets under different required accuracies. Subfigures a, d, g and j show the point cloud distribution compressed by the bi-Akima method, while subfigures b, e, h and k give the point cloud distribution after data redundancy identification by the proposed method, with the identified redundant points marked in red. In subfigures c, f, i and l, the identified redundant points are eliminated. These subfigures show the distributions of the final compressed point cloud data. By contrast, we can clearly observe the difference in point cloud density between these two methods under the same required accuracy. Take subfigures j, k and l, for example: when using the bi-Akima method, we can observe that there are many curves roughly along the vertical direction (Figure 13j). This is because the bi-Akima method can only deal with the point set in the current single scanning line, which is along the horizontal direction, and the data redundancy outside the current scanning line cannot be eliminated. With the involvement of our proposed method, redundant data points are identified and marked in red (Figure 13k), the data redundancy in adjacent scanning layers is eliminated and the final compressed point cloud data is obtained (Figure 13l).

In order to verify the accuracy of the proposed algorithm, Figure 14 analyzes the spatial distribution of deviation between each initial sampled point and the interpolated surface obtained from the final compressed point cloud data under different required accuracies. As can be seen, all the deviations are within the allowable range of required accuracy, which proves that the proposed method can tightly control the deviation within the error tolerance range (i.e., the deviation between each initial sampled point and interpolation curve is less than or equal to the required accuracy). In addition, deviations are far less than the required accuracy in most of the measured area.

4. Discussion

The experimental results in Section 3 indicate that the proposed on-line point cloud data compression algorithm for free-form surface scanning measurement has the following features:

• It can further compress point cloud data and obtain a higher data compression ratio than the existing methods under the same required accuracy. Its compression performance is obviously superior to the bi-Akima and chordal methods;
• It is capable of tightly controlling the deviation within the error tolerance range, and deviations in most measured area are far less than the required accuracy;
• Test A preliminarily verifies the application feasibility of the proposed method in an industrial environment. Test B demonstrates that the method is equally effective for complex surfaces with a large number of details, edges and sharp features, and it has stable performance;
• The proposed method has the potential to be applied to industrial environments to replace traditional on-line point cloud data compression methods (bi-Akima and chordal methods). Its potential applications may be in the real-time measurement processes of scanning devices such as contact scanning probes, laser triangle displacement sensors, mobile laser scanners, linear structured light systems, industrial CT systems, etc. The application feasibility of this method needs to be further confirmed in subsequent case studies.

However, the proposed method is not perfect and still has the following limitations. In future work, the following aspects need to be further developed:

• This method can only handle 3D point cloud data streams and is not suitable for processing point cloud data containing additional high-dimensional information (e.g., 3D point cloud data with grayscale or color information). We will try to solve the above problem in our future research work;
• This method can only compress the point cloud data stream which is scanned layer by layer. If the 3D point cloud is randomly sampled and there are no regular scan lines (e.g., 3D measurement with speckle-structure light), our method cannot perform effective data compression. It is a huge challenge to solve the above problems.

5. Conclusions

In an attempt to effectively compress dense point cloud data obtained from a 3D free-form surface during the real-time scanning measuring process, this paper presents a novel on-line point cloud data compression algorithm which has the ability to identify and eliminate data redundancy caused by geometric feature similarity between adjacent scanning layers. At first, the new algorithm adopts the bi-Akima method to compress the initial point cloud data obtained by 3D scanning measuring devices. Next, the data redundancy in the compressed point cloud obtained in the previous stage is further identified and eliminated, and then we can obtain the final compressed point cloud data. Finally, the proposed on-line point cloud data compression algorithm was tested in the real-time scanning measuring process and compared with existing methods (the chordal method and bi-Akima method). The experimental results have preliminarily verified the application feasibility of our proposed method in industrial environment, and shown that it is capable of obtaining high-quality compressed point cloud data with a higher compression ratio than other existing methods. In particular, it can tightly control the deviation within the error tolerance range, which demonstrates the superior performance of the proposed algorithm. This algorithm could be used in the data acquisition process of 3D free-form surface scanning measurement to replace other existing on-line point cloud data compression/reduction methods.