Evaluation of Circularity from Coordinate data using Maximum Distance Point Strategy (MDPS)

Evaluation of Circularity from Coordinate data using Maximum Distance Point Strategy (MDPS)

V. J. Patel

Associate Professor, Department of Mechanical Engineering, Birla Vishvakarma Mahavidyalaya (Engineering College), Vallabh Vidyanagar – 388120. Gujarat State, INDIA

R. B. Gandhi

Associate Professor, Department of Mathematics, Birla Vishvakarma Mahavidyalaya (Engineering College), Vallabh Vidyanagar -388120. Gujarat State, INDIA

Abstract

Measurement of cylindrical features using Coordinate Measuring Machine (CMM) is one of the important operations in precision engineering industries. The operation necessitates use of efficient computational algorithms as it has to determine radius/diameter of cylindrical features from measured point coordinates. One of the most widely used algorithm for such application is Least-Square Method (LSM) which fits a circle to the points measured using CMM. This paper proposes a new approach termed as Maximum Distance Point Strategy (MDPS) to determine radius/diameter of cylindrical feature for minimizing circularity from measured data-points. The results of MDPS are compared to that of LSM. Moreover, the results of MDPS are also compared with other methods available in literature and it has been found that the results are comparable with the same. It is also demonstrated that the developed methodology offers simplicity in understanding and ease of implementation in computational algorithms.

Keywords: Coordinate Measuring Machine (CMM), Least-Square Method (LSM), Circularity, Sum of Squared Deviations

1. Introduction

   Many functional components in engineering industries have external or internal cylindrical features. When these components are manufactured, closeness to required dimension is expressed in terms of roundness or circularity. Roundness or circularity can be determined using various instruments such as roundness testing machine, dial gauges, Coordinate Measuring Machines (CMM), gap detectors etc. Among these methods, CMM is widely used in industries due to versatility and ease of operation.

   The ANSI Dimensioning and Tolerance Standard Y14.5 [1] defines that the form tolerances on a

   component must be evaluated with reference to an ideal geometric feature. CMM software evaluates circularity of cylindrical features by establishing a circle as a reference geometric feature from the measured points using Least Squares Method (LSM). LSM is predominantly used to estimate best fit circle for the measured points. LSM fits geometric feature to minimize the sum of squares of deviations in predefined measures.

2. Literature Review

   Gander, Colub and Trebel [2] used Gauss-Newton Algorithm (GNA) to minimize the square of error distances for circle. Gauss-Newton algorithm is a modification of Newtons method, which is line-search strategy for finding the minimum of a function, mainly used to solve non-linear least squares problems. If GNA starts nearby the solution, it converges quickly. In other cases, it requires more iteration to converge and sometimes it may not converge at all. Hence, a good initial guess is required for the solution to converge [3].

   Shakarji [4] suggested use of Levenberg-Marquardt algorithm (LMA) to minimize the square of error distances for various features including circle. LMA is trust-region strategy which provides a numerical solution to the problem of minimizing non-linear function. LMA is more robust than GNA. However, even for well- behaved functions and reasonable starting parameters, the LMA tends to be a bit slower than the GNA. LMA can also be viewed as improved GNA with trust region approach [4, 5, 6]. Also, convergence of the solution is highly dependent on choice of Levenberg-Marquardt parameter and its selection is challenging.

   Chernov and Ososkov [7] proposed two new set of algorithms for full circle-fitting and circular arc namely Iterational Linear Regression Method (ILRM) and Modified Linear Regression Method (MLRM). Although ILRM is well-suited for fitting any size of circular arc including full circle, it is slower. The second suggested method (MLRM) is faster, but works only for small arcs.

   Drezner, Steiner and Wesolowsky [8] suggested use of heuristic algorithms for finding a circle whose circumference is close to given set of points. The heuristic uses two efficient algorithms known as minimax and minisum.

   All previous methods are establishing the circle from the measured or simulated points. This circle is base feature for evaluating circularity. Attempts have been also made to develop methods for evaluating error in circularity. Murthy and Abdin [9] applied normal least- square fit to determine circularity error but the values obtained are not the minimum for LSM. Instead, they have suggested that simplex search technique is more suitable. To obtain the minimum zone evaluation for sphericity, numerical methods based on the Monte Carlo, Simplex and Spiral Search techniques have also been suggested by Kanada [10]. Murthy [11] compared different algorithms for circularity evaluation and concluded that simplex search is essential and superior to the other methods for evaluating circularity. Shunmugam

   1. suggested an alternative approach based on minimum average deviation (MAD) in which different geometric features are established using a search technique. The values obtained by this approach are compared with the ones obtained using least squares and minimum deviation methods. Dhanish and Shunmugam

   2. determined minimum zone values using discrete and linear Chebyshev approximations which is applied directly to form data as well as coordinate data provided by CMM. An algorithm suggested by Dhanish [14] guarantees the minimum value of circularity error. Kim and Kim [15] proposed an algorithm for least squares evaluation of circularity which takes geometrical approximation of the orthogonal Euclidean distance in measuring deviational errors of sample data over very small arc so that the assessment criterion of normal least squares is faithfully implemented. Wang, Hossein Cheraghi and Masud [16] formulated a nonlinear optimization problem to find circularity error based on the minimum radial separation criterion. Samuel and Shumugam [17, 18] suggested methods based on computational geometric techniques to deal with CMM measured data and form data.

   The present work aims to define a strategy that finds best fit circle for given set of data points to minimize circularity and it is named as Maximum Distance Point Strategy (MDPS). For the purpose of comparison, results of MDPS are compared with LSM and CMM results. The results of MDPS are also compared with results of methods published in references [9] and [17].

   This is a customized approach to find the best fit circle for evaluating the circularity rather than addressing a general unconstrained nonlinear problem. It is based on the postulate that A unique circle passes through any three non-collinear points in a plane. Hence, selection

   of three points (triplet) plays important role to fit the best circle.

3. Point Selection

The selection procedure for triplet (A, B, C) is as follow.

1. Let Pi(xi, yi), i = 1,2, , n and n > 2, be the CMM measured set of n points.

2. Select a point from Pi and name it as A, which is first point in triplet.

3. Calculate distance from point A to each point Pi

   using equation 2.1.

   APi = (xa xi)2 (ya yi)2 (3.1)

   where, APi is distance from point A to point Pi, i = 1,2, , n,

   xa, ya are coordinates of pont A,

   xi, yi are coordinates of point Pi.

4. Select second point from Pi, i = 1,2, , n (second point in triplet) for which APi is maximum. Name it as B.

5. Point C (third point in triplet) is selected from Pi, i = 1,2, , n such that its normal distance from line AB is maximum.

   To determine maximum normal distance, the following expression is used.

   d(Pi) = |(yB yA) (xi xA) + (xB xA) (yi yA)| (3.2)

   where, i = 1,2, , n

   xa, ya are coordinates of point A, xb, yb are coordinates of point B, xi, yi are coordinates of point Pi.

   The selection procedure is repeated for each point Pi, i = 1,2, , n. Hence, there are n triplets and n candidate circles passing through the triplets.

   In figure 3.1, selection procedure for point 1 as first point in triplet is shown. Since, distance between point 1 and point 3 is the maximum amongst all points, point 3 is selected as second point in triplet. Point 5 is selected as third point in triplet as its distance from line AB is the maximum. The circle shown in figure 3.1 is candidate circle for point 1.

   Amongst all candidate circles, circles which are far from the solution are eliminated heuristically as discussed in section 4.3. The average of center coordinates of the selected circles and the average radii of these circles represent the center and radius of the best fit circle for a given set of points.

   2(xb xa)x0 + 2(yb ya)y0 = (x2 x2) + (y2 y2)

   b a b a

   C

   a

   C

   a

   2(xC xa)x0 + 2(yC ya)y0 = (x2 x2) + (y2 y2)

   for center of the circle (x0, y0) and calculate r0 using r0 = (xa x0)2 + (ya y0)2. This is the circle passing through (xa, ya), (xb, yb) and (xC, yC).

   Repeating the procedure by fixing each point Pi, i =

   1, 2, n, ncenters and nradii are found. To select the best fit circle following heuristic method is used.

   1. Let

      n

      2

      ek = I [(xi ak)2 + (yi bk)2 rk]

      i=l

      Figure 3.1 Selection Procedures for Triplet.

      1. Formulations

         For Pi(xi, yi), i = 1,2, , n and n > 2.

         1. Least Square Method

            A circle with the center (x0, y0) and radius r0 is found such that it minimizes the sum of squared deviations. The circle equation in an implicit form can be written as

            0

            f(x, y) = (x x0)2 + (y y0)2 r2 = 0

            The deviation of distance for a point Pi, i = 1,2, , n

            may be explicitly written as

            ei = (xi x0)2 + (yi y0)2 r0; i = 1,2, , n

            (4.1)

            The sum of squared deviations is then described as

            (ak, bk) is center and rk is radius of kth circle where, k = 1,2, n.

   2. The mean and standard deviation of ek, k = 1,2, n are found.

   3. The circles with ek less than or equal to mean of ek, k = 1,2, n are selected.

   4. Calculate the mean of the coordinates of centers and radii of these selected circles. This gives center and radius of the best fit circle.

   5. Calculate circularity using equation (3.3) for the circle found in step 4.

   6. Steps 1 to 5 are followed for (n m) number of circles; where m is number of circles which are not selected in step 3.

   7. If circularity calculated in step 5 is less than circularity calculated in previous iteration, go to step 7. Otherwise go to step 8.

   8. The circle found in second last iteration is the claimed best fit circle.

e = n

e2 = n

x )2 + (y y )2 r ]2

s

(4.2)

i=l i

i=l i 0

i 0 0

1. Circularity error

   Denote the maximum value among the deviations ei, i = 1,2, , n as emax and the minimum value as emin. Then, the circularity error h can be computed as (refer Figure 4.1)

   h = emax emin (4.3)

   According to the minimum zone criterion given by ANSI Standard Y14.5 [1], the center (x0, y0) and radius r0 of an ideal circle should be determined such that the circularity h is the minimum.

2. Maximum Distance Point Strategy

   Fix a point, say, Pk and select two other points as explained in section 3. Let the coordinates of the points be (xa, ya), (xb, yb) and (xC, yC). Solve the following system of linear algebraic equations

   Figure 4.1 Definition of circularity error.

1. Results and Discussion

MATLAB programs for evaluating circularity by MDPS and LSM were executed on computer with Intel atom processor, 800 MHz clock speed and 1 GB RAM. The programs were run for CMM measured data set. A hole (circular feature) is measured using SCAN facility available on CMM. The SCAN facility ensures that points in the dataset are uniformly spaced. These measured points are tabulated in Table 1.

Table 2 shows results of circularity (h) evaluation for the dataset presented in Table 1. The results of MDPS and LSM are expressed up to six decimal places. It can be observed that circularity error obtained by MDPS is less than that of LSM. It can also be observed that the same is more than that obtained by CMM result. The CMM results were available up to three decimal places. If circle coordinates and radius values obtained by MDPS are rounded to third decimal place, the circularity error is the same as that obtained by CMM. Table 2 also shows the comparison of sum of squared deviation (es). It can be observed that sum of squared deviation of MDPS is minimum amongst all.

Simplex search is superior to the other methods in many cases [11]. Murthy and Abdin [9] have applied simplex search to find a circle to minimize the circularity error on simulated dataset. The same dataset is used to evaluate MDPS. The circularity error obtained by MDPS appears to be more than simplex search, but it is less than that obtained through LSM (refer Table 3). The MDPS can be used as starting solution for simplex search which can reduce number of iterations in finding the circle by simplex search method.

The programs are also executed for the data presented in table 1(a) of Samuel and Shunmugam [17]. Table 4 summarizes the results for circularity evaluation. It can be seen that the MDPS gives less circularity error than that of LSM, MCC (Maximum Circumscribe Circle) and MIC (Minimum Inscribe Circle). The circularity error obtained by MZ (Minimum Zone) is less than that of MDPS, but sum of squared deviation is higher.

1. Conclusions

   The present paper proposes an approach termed as MDPS to determine dimensions of a cylindrical feature from CMM measured point datasets. MDPS is a simple method to understand and to implement amongst similar methods. It gives better results compared to Least Square Method (LSM) for CMM measured points (Table 2). It is also good on evaluating simulated dataset (Table 3). Results of MDPS are comparable with that of Simplex Search method. This method can be used as starting solution for Simplex Search as its solution is closer to Simplex Search compared to LSM. The MDPS results are also showing its potential compared to Maximum Circumscribe Circle (MCC), Minimum Inscribe Circle

   (MIC) and Minimum Zone (MZ) (Table 4). The developed methodology has great potential for implementation in CMM software for evaluation of circular features.

2. References

1. ANSI Standard Y14.5, Dimensioning and Tolerancing, The American Society of Mechanical Engineers, New York, 2009.

2. Gander, Colub and Strebel, Least-Squares Fitting of Circles and Ellipses, BIT Numerical Mathematics, Vol. 34 No. 4, pp 558-578, 1994. doi: 10.1007/BF01934268

3. Ravindran, K. M. Radsgell and G. V. Reklaitis Engineering Optimization: Methods and Application, Second Edition, John Wiley & Sons, 2006.

4. Shakarji, Least-Squares Fitting Algorithms of the NIST Algorithm Testing System, Journal of Research of the National Institute of Standards and Technology, vol. 103 no. 6, pp 633-641, 1998.

5. Nocdal and Wright, Numerical Optimization, Springer- Verlag, New York, 1999.

6. Antoniou and Lu, Practical Optimization: Algorithms and Engineering Applications, Springer Science+Business Media, 2007.

7. Chernov and Ososkov, Effective Algorithms for Circle Fitting, Computer Physics Communications, vol. 33 no. 4, pp 329-333, 1984 doi:10.1016/0010-4655(84)90137-1

8. Drezner, Steiner and Wesolowsky, On the Circle Closest to Set of Points, Computer and Operations Research, vol. 29 no. 6, pp 637-650, 2002. doi:10.1016/S0305- 0548(99)00105-7

9. Murthy and Abdin, Minimum Zone Evaluation of Surfaces, International Journal of Machine Tool Design and Research, vol. 20 no. 2, pp. 123-136, 1980 doi:10.1016/0020-7357(80)90024-4

10. Kanada, Evaluation of spherical form errorscomputation of sphericity by means of minimum zone method and some examinations with using simulated data, Precision Engineering, vol. 17 no. 4, pp 281289, 1995. doi:10.1016/0141-6359(95)00017-8

11. Murthy, A Comparison of Different Algorithm for Circularity Evaluation, Precision Engineering, vol 8 no. 1, pp 19-23, 1986 doi:10.1016/0141-6359(86)90005-X

12. Shunmugam, New approach for evaluating form errors of engineering surfaces, Computer Aided Design, vol. 19 no. 7, pp 368-374, 1987 doi:10.1016/0010-4485(87)90037-6

13. Dhanish and Shunmugam, An algorithm for form error evaluation using the theory of discrete and linear Chebyshev approximations, Computer Methods in Applied Mechanics and Engineering, vol. 92 no. 3, pp 309324, 1991. doi:10.1016/0045-7825(91)90019-3

14. Dhanish, A simple algorithm for evaluation of minimum zone circularity error from coordinate data, International Journal of Machine Tools & Manufacture, vol. 42 no. 14, pp 1589-1594, 2002. doi:10.1016/S0890-6955(02)00136-0

15. Kim and Kim, Geometrical tolerances: improved linear approximation of least squares evaluation of circularity by minimum variance, International Journal of Machine

    Tools & Manufacture, vol. 36 no. 3, pp 355-366, 1996. doi:10.1016/0890-6955(95)00056-9

16. Wang, Hossein Cheraghi and Masud, Circularity error evaluation theory and algorithm, Precision Engineering, vol. 23 no. 3, pp 164-176, 1999. doi:10.1016/S0141- 6359(99)00006-9

17. Samuel and Shunmugam, Evaluation of circularity from coordinate and form data using computational geometric

    techniques, Precision Engineering, vol. 24 no. 3, pp 251-

    263, 2000. doi:10.1016/S0141-6359(00)00039-8

18. Samuel and Shunmugam, Evaluation of circularity and sphericity from coordinate measurement data, Journal of Materials Processing Technology, vol. 139 no. 1-3, 90-95, 2003. doi:10.1016/S0924-0136(03)00187-0

Table 1: CMM measured dataset.

Table 2: Results of circularity evaluation for measured points tabulated in Appendix A.

MDPS Maximum Distance Point Strategy, LSM Least Square Method

Table 3: Results of circularity evaluation for data presented in Muthy and Abdin [9].

*R(Radius) is not presented in the reference, hence Sum of squared deviation cannot be calculated

Table 4: Results of circularity evaluation for data presented in Samuel and Shunmugham [17].

MCC Maximum Circumscribe Circle, MIC Minimum Inscribe Circle, MZ Minimum Zone