Sage Journals: Discover world-class research

Abstract

The Moving Least Squares (MLS) and Moving Total Least Squares (MTLS) method are widely used for approximating discrete data in many areas such as surface reconstruction. One of the disadvantages of MLS is that it only considers the random errors in the dependent variables. The MTLS method achieves a better fitting accuracy by taking into account the errors of both dependent and independent variables. However, both MLS and MTLS suffer from a low fitting accuracy when applied to the measurement data with outliers. In this work, an improved method named as α-MTLS method is proposed, which uses the Total Least Square (TLS) method based on singular value decomposition (SVD) to fit the nodes in the influence domain and introduces a geometric characteristic parameter α to associated with the abnormal degree of nodes. The generated fitting points are used to construct the parameter and quantify the abnormal degree of the nodes. The node with the largest parameter value is eliminated and the remaining nodes are used to determine the local coefficients. By trimming only one node per influence domain, multiple outliers of measurement data can be effectively handled. There is no need to set threshold values subjectively or assign weights which avoids the negative influence of manual operation. The performance of the improved method is demonstrated by numerical simulations and measurement experiment. It is shown that the α-MTLS method can effectively reduce the influence of the outliers and thus has higher fitting accuracy and greater robustness than that of the MLS and MTLS method.

Keywords

Moving least squares local approximants reconstruction outliers

Introduction

In the past decades, meshless method¹ has been developed into an effective numerical method because of its good characteristics. In the meshless methods, the formation of shape functions is the primary issue. Many kinds of construction methods have been researched, such as the MLS method and the Radial Basis Functions (RBF) method.^2,3 In the above-mentioned methods, the MLS method is widely used and was imported by Lancaster and Salkauskas⁴ for the surface construction with the corresponding error analysis being discussed.^5,6 Different from the traditional Least Square (LS) method,^7,8 the complete polynomial is not applied to establish the fitting function in the MLS method. It consists of a coefficient vector related to the independent variable and a complete polynomial basis function. At the same time, the influence domain is divided by the compact support weight function, and the weight of nodes is distributed in the whole parameter domain. Therefore, the curve and surface reconstruction of the MLS method have the property of local approximation. The MLS approximation has been extensively recorded in the document and applied to engineering fields by many scholars.^9,10 It derived numbers of methods to solve practical engineering problems for which numerical calculation methods are not suitable,^11–13 for example, interpolating element-free Galerkin (IEFG) method for three-dimensional potential problems proposed by Liu¹⁴ and boundary-free element method proposed by Wang¹⁵.

The MLS method has the advantages of simple calculation, high accuracy and smoothness.^16,17 However, the LS method is applied to determine the local approximation and it assumes that there are no errors in the independent variables, while the random errors always occur on all the variables. In the sense of the TLS method, it is more rational to determine the local approximations.^18–20 The MTLS method provides a better choice for handling the random errors of all variables.²¹ Due to the influence of external factors such as artificial or environmental disturbance, the outliers are inevitable in the measurement data in practical engineering problems, which deviates from measurement data in some way and results in the instability of the reconstruction accuracy.^22–24 In this case, neither MLS nor MTLS method can achieve good fitting accuracy due to their sensitivity to the outliers.

Therefore, it is necessary to find a method to avoid the negative effect of these outliers on fitting results. At present, there are two main methods that are feasible and commonly used.^25,26 One of the common methods is to eliminate the outliers by setting a threshold value, and then operate reconstruction using the remaining data samples.^27–29 Nevertheless, the performance of this method greatly depends on the selection of threshold value, and it is difficult to select the appropriate threshold. Another method is to select an appropriate weight function and assign a smaller weight to the outlier to reduce its influence in the fitting process.³⁰ Nevertheless, how to accurately determine the small weight and reduce the negative impact of the outlier is a thorny problem, particularly when there are multiple outliers. In addition, it is also unknown whether assigning small weights will have other negative effects or not.³¹

To avoid the influence of outliers on the fitting accuracy, this paper presents an improved MTLS approximation named α-MTLS method. In the influence domain of this proposed method, the TLS method applying SVD³² is used to fit the nodes. The generated fitting points are then applied to quantify the abnormal degree of nodes according to the geometric characteristic parameter α. By trimming only one node per influence domain, multiple outliers of measurement data can be effectively handled. This paper is structured as follows. Section 2 gives a brief introduction to the MLS method. Section 3 outlines the basic concepts of MTLS, and introduces in detail the proposed α-MTLS method. In section 4, the fitting performance of α-MTLS method is demonstrated by numerical simulations and experimental measurement compared with MLS and MTLS method. Finally, section 5 draws the conclusion.

MLS method

MLS is a well-developed method and can approximate the measurement data with high accuracy. The MLS approximation of a given function u^h(x) is expressed as³³

u^{h} (x) = \sum_{i = 1}^{m} p_{i} (x) a_{i} (x) = p^{T} (x) a (x)

(1)

in which p_i(x), i = 1, 2, …, m is monomial basis function, and a_i(x) is the coefficient vectors, which is a function related to coordinate x.

The commonly used basis functions in the two-dimensional case are described as follows.

Linear basis function:

p (x) = {[1, x]}^{T} (m = 2)

Quadratic basis function:

p (x) = {[1, x, x^{2}]}^{T} (m = 3)

To evaluate the approximation of the function, the coefficient a(x) is determined by minimising the L² norm, defined as

J = \sum_{I = 1}^{n} w (| | x - x_{I} | | / r) {[\sum_{i = 1}^{m} p_{i} (x_{I}) a_{i} (x) - u (x_{I})]}^{2}

(2)

where w(|| x–x_I||/r) is a weight function with compact support, it provides the corresponding weights according to the residuals for different nodes, and ensures the good local approximation of nodes, n is the number of nodes in the influence domain. At present, different kinds of weight functions have been proposed and applied to the MLS method.³⁴ The exponential weight function applied in this paper is one of the most popular types and can be expressed by

w (s) = {\begin{matrix} \frac{(e^{- 16 s^{2}} - e^{- 16})}{(1 - e^{- 16})} (s \leq 1) \\ 0 (s > 1) \end{matrix}

(3)

This exponential weight function divides the influence domain with x_i. With the movement of x, the weight functions are independent with each other, and the function curves are shown in Figure 1.

Figure 1.

Diagram of the exponential weight function.

The values of the coefficients at the estimate points are acquired as below

a (x) = A {(x)}^{- 1} B (x) u

(4)

where

\begin{matrix} A (x) = P^{T} W (x) P, B (x) = P^{T} W (x) \\ P = [\begin{matrix} p_{1} (x_{1}) & p_{2} (x_{1}) & \dots & p_{m} (x_{1}) \\ p_{1} (x_{2}) & p_{2} (x_{2}) & \dots & p_{m} (x_{2}) \\ ⋮ & ⋮ & ⋱ & ⋮ \\ p_{1} (x_{n}) & p_{2} (x_{n}) & \dots & p_{m} (x_{n}) \end{matrix}] \\ W (x) = diag (w_{1} (s), w_{2} (s), \dots, w_{n} (s)) \\ u (x) = {[u (x_{1}), u (x_{2}), \dots, u (x_{n})]}^{T} \end{matrix}

The approximate function can be further expressed as

u^{h} (x) = p^{T} (x) a (x) = p^{T} (x) A^{- 1} (x) B (x) u

(5)

α-MTLS method

The classical MTLS method

The TLS method can be regarded as an advanced model of the least square method, which takes into account the interference of the regression matrix, whereas the influence of this factor is not considered in the general LS method. The error equation is expressed by

(A + E) x = B + e

(6)

where E is the error of independent variable A and e is the error of dependent variable B.

The SVD of C is expressed as³⁵

C : = [A B] = U Σ V^{T}

(7)

where singular matrix Σ = diag(σ₁, σ₂, …, σ_n+d), σ₁≥σ₂, …, ≥σ_n_+d; n is the column number of the matrix A, and the partitionings are defined as

V : = [\begin{matrix} V_{11} & V_{12} \\ V_{21} & V_{22} \end{matrix}] Σ : = [\begin{matrix} Σ_{1} & 0 \\ 0 & Σ_{2} \end{matrix}]

When V₂₂ is non-singular, the solution of the TLS method exists. In this case, the solution of TLS is

{\hat{X}}_{tls} = - V_{12} {V_{22}}^{- 1}

(8)

To determine the coefficients of local approximants, TLS method is applied to the influence domain of MTLS method. The matrix can be expressed as

C_{x} : = W_{x} [A B] = U_{x} Σ_{x} {V_{x}}^{T}

(9)

where W_x = diag(w(x–x₁), w(x–x₂), …, w(x–x_n)) is the weight matrix. The TLS solution can be obtained as

a (x) = - V_{x 12} V_{x 22}^{- 1}

(10)

MTLS method introduces TLS to determine local fitting parameters and takes the sum of squares of orthogonal residuals as the reference index, which is more rational in dealing with the errors of all variables, exactly as expressed in Figure 2.

Figure 2.

The approximation principle of MTLS method.

α-MTLS method

It can be seen from the above, the local approximants of MTLS method are executed in the orthogonal direction, in which the TLS estimations of influence domain are more appropriate for handling the errors-in-variables (EIV) model compared with the MLS method. However, the fitting accuracies of both methods do not meet the requirements when the outliers exist. Therefore, the α-MTLS is proposed to enhance the fitting accuracy and robustness when there are outliers in measurement data. The construction process of geometric characteristic parameter α for evaluating the abnormal degree of node is shown in Figure 3.

Figure 3.

The construction process of parameter α

As shown in Figure 3, TLS method applying SVD is firstly used to fit the nodes P_i (i = i–3:i+2) in the influence domain to obtain the approximation line and generates the fitting points P^′_i (i = i–3:i+2) which is in the approximation line and has the same x_i with the corresponding node. The parameter α of P_i is the sum of angles formed by the fitting point P^′_i and other nodes. For example, the angle α_i–₃ is formed by the line P_iP_i_–3 and P^′_iP_i_–3, and the angle α_i_–2 is formed by the line P_iP_i_–2 and P^′_iP_i_–2, and so on. It is apparent that N nodes can form N–1 angles and each node has one α value. The node with the largest α will be trimmed and the weighted TLS method applying SVD is employed to calculate the local coefficients using the remaining nodes. With the movement of the influence domain, the global reconstruction of the measurement data is completed in the whole parameter domain.

It can be seen from the introduction above that this method eliminates only one point in each influence domain and each eliminating process is independent of each other. To some extent, the parameter α of the node can reflect the deviation degree from the approximation line and can be used to evaluate the abnormal degree of each node. Different from the MTLS method, in the influence domain of α-MTLS method, the abnormal degree of the generated fitting point is quantified according to the geometric characteristic parameter α, and the outliers will be eliminated.

The following flowchart in Figure 4 shows the procedure of the improved method.

Figure 4.

The procedure of the α-MTLS method.

Numerical and experimental examples

Numerical simulations and experimental examples are given to validate the performance of the α-MTLS method. The fitting results obtained by the MLS and MTLS method are shown as well for comparison.

Case 1

Within this example, the aspheric profile function is considered

y = \frac{c x^{2}}{1 + \sqrt{1 - (1 + k) c^{2} x^{2}}}

(11)

where c = 1/1025 is the curvature of the base circle and k = –1.2 is a constant. A set of evenly distributed points (x_i, y_i), i = 1, 2, …, n obtained by equation (11) are selected and random errors with a mean value of 0 and normal distribution (δ_i, $ε_{i}$ ) are added to X and Y coordinates respectively. Outliers E_i (i = 1:4) are added to the Y coordinate of some random points and thus a set of simulated measurement data (x_im, y_im) is generated.

The fitting accuracy can be evaluated by the sum of the differences between the theoretical values and the fitting values as well as the Root Mean Square (RMS) value

s = \sum_{i = 1}^{n} | y_{i} - y_{if} |

(12)

RMS = \sqrt{\frac{\sum_{i = 1}^{N} {(y_{i} - y_{if})}^{2}}{N}}

(13)

where y_i is the theoretical value and y_if is the fitting value.

Let n = 121 and d = (max(x)–min(x)) × 1/10, where max(x) = 30 and min(x) = 0. The simulated data is fitted by MLS, MTLS and α-MTLS method respectively. Figure 5 shows the fitting curves of the three methods and the corresponding sum of differences and RMS values for the methods above are listed in Table 1.

Figure 5.

The aspheric curve fitting by three methods.

Table 1.

The results of fitting aspherical profile functions by three methods.

Method	$s$	RMS
MLS	0.26671478	0.00352073
MTLS	0.27651588	0.00425174
α-MTLS	0.05819576	0.00035110

Case 2

The wave function is investigated

y = \sin (3 (1 - x)) / \sin 3

(14)

Under the conditions of n = 201 and d = (max(x)–min(x)) × 1/10, in which max(x) = 1 and min(x) = −1. The data is acquired using the same method as that described in Case 1 and is processed by MLS, MTLS and α-MTLS method separately. The corresponding sum of differences and RMS values are shown in Table 2 and the fitting curves are plotted in Figure 6.

Table 2.

The results of three methods for the wave function.

Method	$s$	RMS
MLS	9.73261284	0.11736975
MTLS	7.70130123	0.12663465
α-MTLS	2.77227190	0.01546685

Figure 6.

The wave curve fitting by MLS, MTLS and α-MTLS.

As shown in Figures 5 and 6, the existence of outliers greatly affects the fitting accuracy of MLS and MTLS methods, which makes the nearby data deviate from the normal nodes. Meanwhile, Tables 1 and 2 also show that even if there are only a few outliers in the global domain, the reconstruction result will be totally different. Obviously, the proposed α-MTLS method can achieve a better fitting result for the data with outliers in terms of accuracy and robustness.

Case 3

Within this example, the three-dimensional discrete data of the function are considered

z = {(\frac{x^{2}}{2} - \frac{y^{2}}{2})}^{2}

(15)

the domain Ω is assumed as Ω = [–1, 1] × [ –1, 1] and the surface is divided into a mesh of 33 × 33 nodes. The case is carried out under the conditions of n = 1089 and d = (max(x)+max(y))/10, where max(x) = 1 and max(y) = 1. The fitting results by MLS, MTLS and α-MTLS are shown in Table 3 and Figure 7.

Table 3.

The result of three methods for the 3D surface.

Method	$s$	RMS
MLS	9.46763896	0.01405492
MTLS	6.23022634	0.01549102
α-MTLS	5.05919331	0.00697063

Figure 7.

The surface fitting by three methods. (a) The fitting and error surface of the MLS method. (b) The fitting and error surface of the MTLS method. (c) The fitting and error surface of α-MTLS method.

For the result of each method in Figure 7, the fitted surface and error surface are displayed on the left and right, respectively. It can be seen that although the MLS and MTLS method has good approximation character and can well reflect the geometric contour of the data, they are greatly sensitive to the outliers and only a few outliers in curves and surfaces will lead to the unstable reconstruction of a series of adjacent nodes. The proposed method can effectively eliminate outliers without affecting the reconstruction of nearby nodes and achieve a stable reconstruction accuracy.

Case 4

In this example, the experimental measurement data is used to validate the performance of the proposed method.

The measurement system is mainly composed of a mobile platform and a laser displacement sensor system. SILVERA 080 series guideway with precision positioning controlled by YASKAWA servo driver are used in the three-coordinate mobile platform system. The signal exchange between the mobile platform and PC is controlled by the control card Parker 1505. The feedback of motion position of each axis is provided by the RH 100 series grating displacement sensor produced by Renishaw. The other hardware includes digital display rotary table, electronic control cabinet, PC and so on.

As shown in Figures 8 and 9, a non-contact displacement sensor KEYENCE LK-G150 is used to measure the horizontally fixed cylinder and acquire the contour data of the standard cylinder. The radius of the standard cylinder is 40.1840 mm calibrated by Taylor Hobson PGI 1240 profilometer. The contour data are fitted by MLS, MTLS and α-MTLS respectively. The reconstructed data are processed by the circle regression algorithm and thus the regression radii of three methods are obtained in Table 4. Figure 10 shows the fitting curve of the α-MTLS method. From the radius values in Table 4, compared with the other two methods, it can be known that the α-MTLS result is closest to the standard cylindrical radius under the same condition. The experimental result verifies the good performance of our proposed method.

Figure 8.

Experiment of measuring cylinder with CMM.

Figure 9.

Schematic diagram of CMM.

Table 4.

The radius of handling the standard cylinder by three methods.

Variance			R (mm)
$δ_{i}$	$ε_{i}$	MLS	MTLS	α-MTLS
0.015	0.0005	40.1124	40.1143	40.1166

Figure 10.

The profile fitting of standard cylinder by α-MTLS method.

As mentioned above, the errors in the measurement data are not seriously deviated, and the α-MTLS method still has better fitting accuracy. The case studies in this section demonstrate that α-MTLS method can eliminate the negative effect of outliers without human intervention. Only one node is trimmed per influence domain, even if there are several outliers, this method can also ensure fitting accuracy and robustness.

Conclusion

In this paper, a novel α-MTLS method is proposed, which avoids the negative effects caused by setting threshold value or allocating weights subjectively. In addition to its own characteristics, the α-MTLS method makes full use of all the advantages of the MTLS method. The shape function with high order continuity can be obtained by choosing suitable compact support function with low order basis function. In each influence domain of α-MTLS method, the abnormal degree of the generated fitting point is quantified according to the geometric characteristic parameter α, and the outliers will be eliminated. Numerical simulations and experimental measurement verify the effectiveness of the method.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Science Foundation of China (Grant No. 11572316 and 51605094), the Fundamental Research Funds for the Central Universities (Grant No. WK2090050042), the Thousand Young Talents Program of China, and the Center for Micro and Nanoscale Research and Fabrication at the University of Science and Technology of China.

ORCID iD

Dawei Tang

References

Liu

. An introduction to meshfree methods and their programming. New York: Springer, 2005.

Liu

Wang

. A modified approximate method based on Gaussian radial basis functions. Eng Anal Bound Elem 2019; 100: 256–264.

Zhong

Wang

. Implicit surface reconstruction based on generalized radial basis functions interpolant with distinct constraints. Appl Math Modelling 2019; 71: 408–420.

Lancaster

Salkauskas

. Surfaces generated by moving least squares methods. Math Comput 1981; 37: 141–158.

Zuppa

. Error estimates for moving least square approximations. Bull Braz Math Soc New Ser 2003; 34: 231–249.

Cheng

. Researches on the convergence and error analysis of meshless methods. PhD Thesis, Shanghai University, China, 2007.

Esat

Bahai

. Surface alignment based on the moment of inertia and improved least-squares methods. Proc IMechE, Part B: J Engineering Manufacture 2000; 214(7): 547–554.

Zhao

, et al. An adaptive moving total least squares method for curve fitting. Measurement 2014; 49: 107–112.

Feng

Yang

, et al. An investigation on modeling and compensation of synthetic geometric errors on large machine tools based on moving least squares method. Proc IMechE, Part B: J Engineering Manufacture 2018; 232(3): 412–427.

10.

Singh

. Interpolating meshless local Petrov-Galerkin method for steady state heat conduction problem. Eng Anal Bound Elem 2019; 101: 56–66.

11.

Zhang

Liew

. An improved moving least-squares Ritz method for two-dimensional elasticity problems. Appl Math Comput 2014; 246: 268–282.

12.

Wei

Cheng

. The improved moving least-square Ritz method for the one-dimensional sine-Gordon equation. Math Probl Eng 2014; 2014(3): 1–10.

13.

Zhang

Hao

Liew

, et al. The improved element-free Galerkin method for two-dimensional elastodynamics problems. Eng Anal Bound Elem 2013; 37(12): 1576–1584.

14.

Liu

Cheng

. The interpolating element-free Galekin (IEFG) method for three-dimensional potential problems. Eng Anal Bound Elem 2019; 108: 115–123.

15.

Wang

Zhou

Feng

, et al. An adaptive orthogonal improved interpolating moving least-square method and a new boundary element-free method. Appl Math Comput 2019; 353: 347–370.

16.

Joldesa

Chowdhurya

Witteka

, et al. Modified moving least squares with polynomial bases for scattered data approximation. Appl Math Comput 2015; 266: 893–902.

17.

Khuat

Kim

. A solution to the singularity problem in the meshless method for neutron diffusion equation. Ann Nucl Energy 2019; 126: 178–185.

18.

Wang

Xiang

. Quantum algorithm for total least squares data fitting. Phys Lett A 2019; 383: 2235–2240.

19.

Zhang

, et al. A segment feedrate profile fitting method for parametric interpolation. Proc IMechE, Part B: J Engineering Manufacture 2018; 232(2): 267–280.

20.

Zhao

Champagne

. Diffusion total least-squares algorithm with multi-node feedback. Signal Process 2018; 153: 243–254.

21.

Scitovski

Ungar

Jukic

. Approximating surfaces by moving total least squares method. Appl Math Comput 1998; 93: 219–232.

22.

Ren

Cheung

Kong

. A task specific uncertainty analysis method for least-squares-based form characterization of ultra-precision freeform surfaces. Meas Sci Technol 2012; 23: 54005.

23.

Cross

McBride

Lifton

. The uncertainty of radius estimation in least-squares sphere-fitting, with an introduction to a new summation based method. Precis Eng 2014; 38: 499–505.

24.

Cheung

Kong

, et al. Measuring ultra-precision freeform surfaces using a hybrid fitting and matching method. Meas Sci Technol 2009; 20: 105103.

25.

Liu

Shi

Tian

, et al. Ramp loss least squares support vector machine. J Comput Sci 2016; 14: 61–68.

26.

Wang

Caja

Gómez

. Comparison of methods for outlier identification in surface characterization. Measurement 2018; 117: 312–325.

27.

Chuang

Lee

. Hybrid robust support vector machines for regression with outliers. Appl Soft Comput 2011; 11: 64–72.

28.

Hidalgo

Lee

Seo

. Robust inference for threshold regression models. J Econom 2019; 210: 291–309.

29.

Yang

Shao

Pan

, et al. A study on regularized weighted least square support vector classifier. Pattern Recogn Lett 2018; 108: 48–55.

30.

Chen

Yan

. A robust weighted least squares support vector regression based on least trimmed squares. Neurocomputing 2015; 168: 941–946.

31.

Wen

Hao

Yang

. Robust least squares support vector machine based on recursive outlier elimination. Soft Comput 2010; 14: 1241–1251.

32.

Lin

, et al. Curve and surface reconstruction method for measurement data. Measurement 2016; 78: 278–282.

33.

Joldesa

Chowdhurya

Witteka

, et al. Modified moving least squares with polynomial bases for scattered data approximation. Appl Math Comput 2015; 266: 893–902.

34.

Most

Bucher

. New concepts for moving least squares: an interpolating non-singular weighting function and weighted nodal least squares. Eng Anal Boundary Elements 2008; 32(6): 461–470.

35.

Lin

. An improved total least square calibration method for straightness error of coordinate measuring machine. Proc IMechE, Part B: J Engineering Manufacture 2016; 230(9): 1665–1672.

An α -moving total least squares fitting method for measurement data

Abstract

Keywords

Introduction

MLS method

α-MTLS method

The classical MTLS method

α-MTLS method

Numerical and experimental examples

Case 1

Case 2

Case 3

Case 4

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References