See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/254354247

Form Errors in Precision Metrology: A Survey of Measurement Techniques

Article  in  Quality Engineering · July 2012

DOI: 10.1080/08982112.2011.652583

CITATIONS READS

11 893

2 authors:

Abhijit Gosavi Elizabeth A. Cudney

Missouri University of Science and Technology Missouri University of Science and Technology
99 PUBLICATIONS   1,433 CITATIONS    166 PUBLICATIONS   646 CITATIONS   

SEE PROFILE SEE PROFILE

Some of the authors of this publication are also working on these related projects:

Environmental Enteropathy: interaction of water and food View project

Actor-Critic Algorithms & iSMART for Solving Average Reward Semi-Markov Decision Processes View project

All content following this page was uploaded by Abhijit Gosavi on 31 March 2018.

The user has requested enhancement of the downloaded file.

Form Errors in Precision Metrology:

A Survey of Measurement Techniques

Abhijit Gosavi
Email:[email protected]
219 Engineering Management Building
Missouri S & T, Rolla, MO 65409
Elizabeth Cudney
Email: [email protected]
217 Engineering Management Building
Missouri S & T, Rolla, MO 65409

1
 Abstract

This paper presents an overview of foundational concepts and techniques used in metrology
of form errors such as straightness, flatness, circularity, sphericity, and cylindricity. While there
exists a significant body of literature on form-error metrology, to the best of our knowledge, no
review paper has been written on this topic. Our aim here is to (i) present a unified view of
the mathematical foundations of form-error metrology and (ii) to uncover the relative strengths
and weaknesses of a wide spectrum of techniques from the literature. Our analysis concludes
with a discussion of opportunities for future research.

Keywords: form errors, metrology, least-squares, survey, minimum zone.

INTRODUCTION

Our goal in this paper is to present a survey of the measurement techniques employed for surface

metrology features belonging in particular to the class known as form errors. Examples of such fea-

tures include straightness, flatness, circularity, sphericity, and cylindricity. Coordinate Measuring

Machines (CMMs) are widely used in the industry for automated form-error measurement. The

least-squares technique, which was one of the first techniques to have been developed for form-error

measurement, is still widely used in most industrial CMMs. Although, a number of more sophisti-

cated and powerful techniques have now appeared in the literature, to the best of our knowledge,

no survey paper has been written till date that analyzes the plethora of techniques now available

for form-error measurement.

We note at the very outset that in order to keep the scope of this survey manageable, we limit

our attention to form errors (other types of surface errors include waviness and roughness) and to

techniques that can be used with CMMs. Alternatives to CMMs, e.g., vernier callipers, which are

hand-held, or laser trackers, which generate voluminous amounts of data, are not covered. We also

do not cover in this survey issues related to optimal sample sizes, distributions, or other statistical

issues related to form-error measurement.

Our overall objective here is to present an overview of techniques presented in the literature for

analyzing form errors. This survey covers a vast spectrum of techniques and identifies two broad

groups (classes), namely algebraic and computational-geometry-based, into which the techniques

2
surveyed can be classified. The algebraic methods can be further divided into two sub-groups:

white-box (model-based) and blackbox (model-free). A key goal is to highlight differences and

similarities in the various form-error-computation methods developed in the literature. White-box

and black-box methods rely on algebraic properties of mathematical functions constructed from

abstractions of the measurement processes. White-box methods make use of the closed forms of the

underlying functions and analytical-optimization techniques, while black-box methods use numeric

values of the functions and computational-optimization techniques. In contrast to white-box and

black-box methods, computational-geometry methods use geometric properties of the underlying

functions to compute form errors.

Another goal here is to present a unified view of the mathematical foundations of this important

topic. With this in mind, we characterize form errors as functions of vector functions, e.g., the

Euclidean norm (used in least-square methods), the max norm (used in minimax methods), and

the span semi-norm (used in minimum zone methods). In addition, we highlight the relationship

between the minimum zone and the least-squares approaches (Gota and Lizuka, 1977) and the same

between normal and vertical deviations (Murthy and Abdin, 1980; Shunmugam, 1987a).

It is hoped that new research ideas will be stimulated from reading this survey. The rest of this

article is organized as follows. The following section provides a brief discussion of the mathematical

foundations of this subject. The sections entitled “White-Box Methods,” “Black-Box Methods,”

and “Computational Geometry Techniques” discuss white-box, black-box, and computational geo-

metric techniques respectively. The final section concludes this survey with a discussion of possible

topics for future research.

MATHEMATICAL FOUNDATIONS

In this section, our goal is to provide an overview of the mathematical foundations of the science

underlying form-error measurement. In the first subsection, we define reference forms (profiles) and

form deviations, while in the second, we define norms and form errors.

Reference forms and form deviations

To define the form (or profile) error, one first needs to define the reference form. For straight-

3
ness error, the reference form is an imaginary perfect straight line. The same for flatness, circularity

(roundness), sphericity, and cylindricity error is a perfect plane, circle, sphere, and cylinder, re-

spectively. The reference form is constructed using the data collected from the surface of the part

being inspected. Throughout this paper, (xi , yi , zi ) will denote the ith data point’s coordinates in

the x, y, and z axis. The form error is generally a function of the deviations from the reference

form.

Straightness deviation: Let y = mx + c denote the straight line in two dimensions, where m and

c are the parameters of the equation, i.e., the defining parameters. The vertical deviation of a

point, (xi , yi ), on the edge from the reference form will be given by: evi = yi − (mxi + c), where

the superscript v stands for vertical. This is the distance (deviation) along the Y -axis. The normal

deviation of the same point from the reference edge is:

yi − (mxi + c)
eni = √ , (1)
1 + m2

where the superscript n stands for normal. It is easier to minimize vertical deviations rather than

normal deviations, via the well-known least-squares method. This is the reason for their popularity

in commercial software programs. But the normal deviations measure the deviations correctly (ISO,

1983; ANSI: Dimensioning, 1995; ANSI: Definitions, 1995). Unfortunately, normality introduces

non-linearity in the definition of error thereby complicating its analysis.

Flatness deviation: The equation of a plane in three dimensions is defined as: z = mx + ly + c.

Then the normal deviation of any sampled point, (xi , yi , zi ), from the reference plane is given by

zi − (mxi + lyi + c)
eni = √ , (2)
(1 + m2 + l2 )

and the vertical deviation (distance) is given by: evi = zi − (mxi + lyi + c), which is measured along

the Z-axis.

Circularity deviation: A perfect circle is typically defined by: (x − a)2 + (y − b)2 = R2 if R denotes

the radius of circle and the coordinates of the circle’s center are: (a, b). The defining parameters

of the equation of a circle are thus: a, b, and R. For circularity, the deviation of interest is called

4
the radial deviation, which is measured from a given point along the radius to the circle’s center.
√
Hence the radial deviation for a point, (xi , yi ), is: ei = (xi − a)2 + (yi − b)2 − R, in which the

square-rooted term represents the distance from the circle’s center to (xi , yi ).

Sphericity deviation: The equation of a sphere is: (x − a)2 + (y − b)2 + (z − c)2 = R2 , where R

is the radius of the sphere and the sphere’s center is: (a, b, c). The radial deviation for spheric-

ity, which is an extension of the same for circularity to three dimensions, is defined as: ei =
√
(xi − a)2 + (yi − b)2 + (zi − c)2 − R. The defining parameters of the equation of a sphere are

thus: a, b, c, and R. In the deviation, the square-rooted term is the distance from (xi , yi , zi ) to the

center of the sphere.

Cylindricity deviation: The equation of a cylinder (Gosavi and Phatakwala, 2006), whose radius is

R and whose axis is defined by: (x − u)/m = (y − v)/l = (z − w)/k, is (x − mt − u)2 + (y − lt −

v)2 + (z − kt − w)2 = R2 where

(x − u)m + (y − v)l + (z − w)k

t=
m2 + l2 + k 2

(in the print version of the paper, there was a typo that is corrected above in the red material,

i.e., the version in red above is correct). The defining parameters of the equation are: l, m, k, u,

v, w, and R. The deviation of the ith point on a real cylinder from a perfect cylinder can then be
√
defined as: ei = (xi − mti − u)2 + (yi − lti − v)2 + (zi − kti − w)2 − R, where the square-rooted

term is the normal distance from a point, (xi , yi , zi ), on the surface of the cylinder, to the axis of

the cylinder.

Norms and form errors

The deviation vector, ⃗e, is defined as the vector of all the deviations, i.e., ⃗e = {e1 , e2 , . . . , en }, if

n measurements are made. There are three commonly-used measurement criteria, which use norms

or semi-norms of the deviation vector (see any standard text on vector algebra for definitions of

norms and semi-norms). They are: the Euclidean norm, the max (or maximum) norm, and the

span semi-norm.

5
 √∑
Euclidean norm: The Euclidean norm of the deviation vector ⃗e is defined as: ||⃗e||2 = n 2
i=1 ei .

When the Euclidean norm of the deviation vector is minimized to obtain values for the defining

parameters of the reference surface, the surface obtained is the so-called “least-squares” surface,

which is used in most CMMs for many features.

Max norm: The max (or maximum) norm or the Chebyshev norm of the deviation vector ⃗e is

defined as: ||⃗e||∞ = maxi |ei |, where |x| denotes the absolute value of x. When the max norm is

minimized, one obtains the so-called “minimax” surface.

Span semi-norm: The span semi-norm, or zone, is the difference between the maximum and

the minimum of the deviations. It is defined as:

sp(⃗e) ≡ (max ei − min ei ) = | max ei | + | min ei |. (3)

i i i i

In (3), for the second equality to hold, it is assumed that the set of deviations contains both positive

and negative signs. When the zone is minimized to obtain values for the defining parameters of the

reference surface, the surface obtained is the so-called “minimum-zone” surface. The associated

error is called the zone error, and according to (ISO, 1983) and (ANSI: Dimensioning, 1995; ANSI:

Definitions, 1995) is the true error. Hence, this criterion is of critical importance in form-error

metrology.

Form error: The form error is a function of the deviation vector. It is important to note that the

defining parameters of the reference surface are not always computed by minimizing the zone of the

deviation vector. However, after the defining parameters of the reference surface are determined,

i.e., the reference surface is determined, the form error is declared to equal the zone of the deviation

vector. The question that now arises is: why would one use some criterion other than the zone

to determine the defining parameters, but subsequently use the zone to compute the form error?

The answer is: Although, one uses the zone of the deviation vector to compute the form error, it is

usually easier to use other criteria, e.g., the Euclidean norm, to compute the defining parameters

of the reference surface. That is, one performs an optimization with a surrogate but an imprecise

6
objective function, but after the optimization is performed, the objective function value is computed

with respect to the true objective function, i.e., the zone. Obviously, this is done only if there is a

strong motivation to use an imprecise objective function during the optimization. It is indeed the

case that in form-error metrology, the correct objective function (the zone) is algebraically complex

and not easily optimizable. The Euclidean norm on the other hand can be optimized more easily,

and is hence popular. In general, the procedure of form-error estimation is a three-step procedure

described next.

Step 1: Let (xi , yi ) or (xi , yi , zi ) for i = 1, 2, . . . , n denote the data for the n samples gathered from

the surface to be measured. Determine the values of the defining parameters of the reference

surface that minimize a pre-defined function of the deviations (the Euclidean norm, the max

norm, or the zone) using an algorithm.

Step 2: Use the defining parameters to calculate the deviations.

Step 3: Compute the zone of the vector of deviations and declare the zone to be the form error.

In this three-step procedure, there are a number of factors, and each of them introduces an error

that will be called a bias. The first factor arises from the fact that although there is an infinite

number of points on the actual surface, we use only a finite sample. This is called the sampling bias.

This issue is beyond the scope of this paper, but we refer the interested reader to papers that study

it in detail: (Badar et al., 2003; Dowling et al., 1997; Namboothiri and Shunmugam, 1999; Traband

et al., 2004; Kim and Raman, 2000; Kurfess and Banks, 1995; Obeidat, 2008; Gilbert et al., 2009).

The second factor, discussed above, arises when the function used in Step 1, for finding the defining

parameters, is not the zone. Furthermore, in the case of straightness and flatness, using vertical

distances in Step 1 but normal deviations in Step 2 can lead to an additional bias. Finally, a third

source of bias can be traced to machine-measurement error. We now review the three classes of

methods alluded to earlier in the first section.

WHITE-BOX METHODS

7
 For the most part, white-box methods develop a surrogate objective function that can be opti-

mized using well-known optimization techniques which guarantee convergence. Of course, the bias

in these methods arises out of the use of an imprecise objective function. A major strength of these

methods is their robustness and a reduced computational burden. Robustness arises out of the use

of provably convergent optimization techniques, many of which also have a computational burden

lower than that of black-box methods that we will discuss later. In this section, we describe a

wide spectrum of white-box methods described in the literature. We begin with the most popular

white-box method.

The least-squares method

The method used to minimize the Euclidean norm of the deviation vector is often called the

least-squares method or ordinary least squares or regression. Because it exploits the closed form,

the least-squares method is considered to be white-box.

Consider straightness using vertical distances. Step 1 of the generalized procedure minimizes
∑n
the Euclidean norm, i.e., determines m and c to minimize i=1 (yi − mxi − c)2 . The defining

parameters can be determined by solving simultaneously the following two linear equations in

which the unknowns are m and c:

∑
n ∑
n
yi = m xi + nc. (4)
i=1 i=1

∑
n ∑
n ∑
n
xi yi = m x2i + c xi . (5)
i=1 i=1 i=1

From the values of m and c, one computes the deviations via Equation (1), and then the form error

via Equation (3).

The computational elegance of Equations (4) and (5) makes this method attractive for commer-

cial software; the method is robust and all it needs is an algorithm for solving linear equations. The

weakness is that the form error is usually over-estimated, which can be attributed to two sources of

bias, which are: (i) the use of the Euclidean norm — and not the zone — as the objective function,

and (ii) the use of vertical distances — and not normal distances — in the objective function.

8
 Step 1 in flatness measurement involves finding m, l, and c to minimize
∑n
i=1 (zi − mxi − lyi − c)2 . Then the following equations are solved to obtain m, l, and c:

∑
n ∑
n ∑
n
zi = m xi + l yi + nc,
i=1 i=1 i=1

∑
n ∑
n ∑
n ∑
n
xi zi = m x2i + l x i yi + c xi , and
i=1 i=1 i=1 i=1

∑
n ∑
n ∑
n ∑
n
yi z i = m xi yi + l yi2 +c yi .
i=1 i=1 i=1 i=1

One then computes the deviations at each point using Equation (2), and then the form error via

Equation (3).

The least-squares approach for flatness and straightness using vertical distances can be mod-

eled as linear least-squares, which have a straightforward solution. This does not generalize to

circularity and sphericity the functions of which are non-linear. A widely-cited formula for cir-
∑n ∑n ∑n √ 2 2
x
i=1 i
y
i=1 i
x +y
cularity is (Whitehouse, 2002): a = 2 n , b = 2 n , and R = i=1 n i i . This requires

data from equally-spaced points, i.e., points which have an equal angular spacing. A large number

of researchers have worked in the area of developing least-squares-based methods for solving the

circularity problem (Chaudhuri and Kundu, 1993; Cooper, 1993; Takiyama and Ono, 1989; Guu

and Tsai, 1999).

For sphericity, a formula analogous to the one above which also needs equally-spaced data is:
∑n ∑n ∑n ∑n √ 2 2 2
x
i=1 i
y
i=1 i
z
i=1 i
x +y +z
a = 2 n , b = 2 n , c = 2 n , and R = i=1 ni i i . Least-squares solutions and

other approximations for cylindricity have been covered in the literature (Marshall et al., 2001;

Shunmugam, 1986; Murthy, 1982). For least-squares problems, gradient methods of the Gauss-

Newton type (Forbes, 1989) and Levenberg-Marquardt (Shakarji, 1998) type have been recom-

mended by NPL (UK) and NIST (USA), respectively.

Mathematical programming methods

To the best of our knowledge, Murthy and Abdin (1980) were the first to advocate the mini-

mization of the zone in form-error metrology. Also, they used normal distances in measurement of

9
straightness and flatness. Chetwynd (1985) first proposed the use of linear programming methods

to engineering metrology. His approach was aimed at minimizing the zone using vertical distances

in straightness and flatness. For straightness, the linear program (LP) of Chetwynd (1985) is:

Minimize h subject to h ≥ 0,

mxi + c + h ≥ yi ∀i, and mxi + c − h ≤ yi ∀i.

For flatness, the corresponding LP is: Minimize h subject to h ≥ 0,

mxi + lyi + c + h ≥ zi ∀i, and mxi + lyi + c − h ≤ zi ∀i.

Wang (1992) sought to use the correct distance, i.e., the normal distance, but minimized the max

norm. His remarkable formulation resulted in the following non-linear program, in fact, a con-

strained quadratic program (QP) which was solved exactly via sequential quadratic programming

(Bazaraa et al., 1993):

Minimize h subject to h ≥ 0,

di ≤ h ∀i, where

yi − (mxi + c) zi − (mxi + lyi + c)

and di = √ for straightness and di = √ for flatness.
1 + m2 1 + m2 + l 2

Although the objective function in the formulation is linear, the constraints are quadratic which

makes it a QP. The step size in the optimization algorithm was determined using an augmented

Lagrangian. He also minimized circularity and cylindricity using the same strategy and provided

computational evidence of outperforming the least-squares method. Lin et al. (1995) also used

sequential quadratic programming in form-error estimation.

Gass et al. (1998) presented a somewhat distinctive approach for handling the non-linearity

in circularity and sphericity. They used a surrogate objective function which can be optimized

via linear programming. They also provided encouraging computational experience which shows

that their approach approximates the true error. We now describe their approach for circularity.

10
Essentially, the mathematical program they employ is:

Minimize max |Mi | − min |Mi | where Mi = (xi − a)2 + (yi − b)2 − R2 .
i i

√
Note that the ith component of the true deviation vector in circularity is (xi − a)2 + (yi − b)2 −R.

Clearly, Mi = x2i + yi2 − 2xi a − 2yi b − ρ in which ρ is defined as: ρ = R2 − a2 − b2 . However, the

surrogate, Mi , used above, leads to an elegant LP. Then, the mathematical program given above

becomes: Minimize h subject to h ≥ 0

h ≥ x2i + yi2 − 2xi a − 2yi b − ρ ∀i,

−h ≤ x2i + yi2 − 2xi a − 2yi b − ρ ∀i.

In the above, the decision variables are h, a, b, and ρ. When the LP is solved, the values of a and b

are used in the definition of ρ to determine the value of R. A simple extension exists to sphericity

using: Mi = (xi − a)2 + (yi − b)2 + (zi − c)2 − R2 .

Several other researchers have used mathematical programming in the computation of form

error. Cheraghi et al. (1996) and Weber et al. (2002) developed a linear approximation of the

objective function using Taylor’s series. Their approach required a least-squares solution in the

first phase, and in the second phase, the solution of an LP. A non-linear programming approach

in which the objective function was exploited to derive a feasible search direction (Wang et al.,

2001, 1999) along with convergence guarantees to local optima. Ventura and Yerelan (1989) also

developed a non-linear optimization procedure to solve the circularity problem. Prakasvudhisarn

et al. (2003) use support-vector regression that employs mathematical programming for minimizing

the zone.

Linearization

A large number of linear approximations (also called limacon approximations) to non-linear

features have been devised in the literature (Chetwynd, 1979; Murthy, 1986; Shunmugam, 1986;

Landau, 1987; Yerelan and Ventura, 1988; Lai and Chen, 1996). These approximations develop a

11
linear surrogate for the non-linear feature. We now describe them for circularity and sphericity.

Circularity: For circularity, the polar coordinates (ri , θi ) and the Cartesian coordinates, (xi , yi ),
√
share the following relation: xi = ri cos θi , yi = ri sin θi , ri = x2i + yi2 , and θi = tan−1 (yi /xi ) .

The radial deviation at any point can be expressed approximately using the following linearized

equation ei ≈ ri − (R + a cos θi + b sin θi ), where R denotes the circle radius and (a, b) is the center.

The power of this linearization can be exploited by using it in a least-squares method in which one
∑ 2
seeks to minimize i ei . There will be three unknowns, R, a, and b, in the following set of linear

equations, which have to be solved simultaneously:

∑
n ∑
n ∑
n
ri = nR + a cos θi + b sin θi .
i=1 i=1 i=1

∑
n ∑
n ∑
n ∑
n
ri cos θi = R cos θi + a cos2 θi + b sin θi cos θi .
i=1 i=1 i=1 i=1

∑
n ∑
n ∑
n ∑
n
ri sin θi = R sin θi + a sin θi cos θi + b sin2 θi .
i=1 i=1 i=1 i=1

Sphericity: For sphericity, one can use spherical cooridinates: (ri , θi , ϕi ), whose relationship with

Cartesian coordinates, (xi , yi , zi ), is defined below:

√ ( ) ( )
−1 yi zi
ri = x2i + yi2 + zi2 , θi = tan , and ϕi = cos−1 .
xi ri

The radial deviation is: ei ≈ ri − (R + a cos ϕi cos θi + b cos ϕi sin θi + c sin ϕi ), where the sphere’s

center is (a, b, c) and the radius is R. For cylindricity, see Shunmugam (1986) for an analogous

approximation.

Chebyshev approximations

A method that minimizes the max norm, i.e., any “minimax” method, in practice outperforms

the least-squares method. As a result, the minimax criterion has attracted considerable attention.

Chebyshev approximations of a function (see any standard text on numerical analysis, e.g., Ral-

ston and Rabinowitz (2001)) can be used to determine a minimax approximation of the function.

Loebritz (1993) is one of the first works to have used this approximation. Dhanish and Shunmugam

12
(1991) used a Chebyshev approximation in an iterative algorithm for straightness, flatness, circu-

larity, sphericity, and cylindricity. They develop an approach in which one begins with a subset of

the data and modifies the data set progressively. Chatterjee and Roth (1997) present a minimax

algorithm for straightness and flatness. Fukuda and Shimokohbe (1984) used a minimax approx-

imation to minimize the zone. Grinde and Ventura (1994) use the minimax criterion for center

estimation in sphericity. Gosavi (1995) used a rational function Chebyshev approximation (Press

et al., 1992) using the second algorithm of Remes (Ralston and Rabinowitz, 2001) for straightness,

flatness, and circularity.

BLACK-BOX METHODS

In contrast to white-box methods which employ analytical properties of the objective function,

black-box methods treat the objective function as a black box of which only numeric values are

of interest. Consequently, black-box methods do not rely on any specific property of the objective

function, and, in principle, can work on any objective function. Hence the bias that arises from

approximating the objective function, which is often present in white-box methods, is non-existent

with black-box methods. Unfortunately, black-box methods are (i) not guaranteed to converge to

global optima and (ii) may require a large number of function evaluations (and hence a long time).

It is to be noted, however, that with the increasing power of computers, the latter point does not

pose a serious challenge nowadays.

A large number of computational methods are available in the literature, which can be used

in form-error metrology. Some of the well-known ones are: the Nelder-Mead simplex procedure

(Nelder and Mead, 1965), the Hooke-Jeeves procedure (Hooke and Jeeves, 1961), derivative-based

methods, and meta-heuristics, e.g., genetic algorithms, simulated annealing, and tabu search. The

Nelder-Mead approach, also called flexible polygon search, has been exploited extensively (Murthy

and Abdin, 1980; Kanada and Suzuki, 1993; Kanada, 1995; Damodarasamy and Anand, 1999).

Elmaraghy et al. (1990) employed a Hooke-Jeeves search and Lai et al. (Lai et al., 2000) make

use of a genetic algorithm. Derivative descent has been used in white-box methods (Cardou et al.,

1972; Zhu et al., 2003) and black-box methods (Gosavi and Phatakwala, 2006).

13
 In the Nelder-Mead algorithm, one starts with a simplex, which is essentially a convex hull of

(D + 1) points selected randomly from the solution space, where D denotes the number of defining

parameters. The best point in the simplex, i.e., the point with the lowest function value, and the

worst (with the highest function value) point are identified. Then the centroid of the points in the

simplex other than the worst point is computed. A so-called reflection is performed, and a new

vertex is generated. If the new vertex is better (has a lower function value) than the worst vertex

in the simplex, the latter is replaced by the new vertex. Although it is of a heuristic nature, the

algorithm works well for a small value for D

In steepest gradient descent, the iterative algorithm begins at an arbitrary solution. Let the

solution for the ith defining parameter in the pth iteration of the algorithm be denoted by qip , and
p
the vector q⃗p = {q1p , q2p , . . . , qD }. The heart of the algorithm is as follows:


∂f (.) 
qip+1 ← qip − µ , for all i = 1, 2, . . . , D,
∂qi q⃗=q⃗p

where f (.) is usually the zone. The algorithm is terminated by checking whether the gradient norm

is less than a stopping tolerance, i.e., if

v
uD ( )2
u∑ ∂f (.) 
t  < ϵ,
∂q 
i=0 i q⃗=q⃗p

where ϵ denotes the stopping tolerance, which is generally set to a small number.

Black-box methods can be used on complex features, but tend to be slower than white-box

methods. Also, some researchers are uncomfortable with using them, because they do not ex-

ploit analytical properties, relying on numeric values instead. Computational-geometry methods

carry the promise of a considerably-reduced computational time, and hence form the most exciting

methods on the frontier of form-error metrology. We now present a review of these methods.

COMPUTATIONAL GEOMETRY TECHNIQUES

A number of researchers have used computational geometry (see e.g., Preparata and Shamos

(1985) for a textbook) for form-error computation. A central idea in such methods is to construct at

14
least two surfaces which (i) enclose within them all the measured points and (ii) have the minimum

separating distance; in case of straightness and flatness, the two surfaces are parallel straight

lines and planes, respectively, in case of circularity and sphericity, the two surfaces are concentric

circles and spheres, respectively, and finally for cylindricity, the surfaces are co-axial cylinders with

different radii. Most of the algorithms in this class are iterative, and start with a good solution,

which is progressively improved until the optimal or near-optimal solution is obtained. These

algorithms generally use the so-called Voronoi diagrams and employ the theory of convex sets. A

positive aspect of these algorithms is that most of them attempt to minimize the zone.

Elzinga and Hearn (1971) is an early work that presents a fundamental geometry method for

a minimax problem in location theory. Traband et al. (1989) used a convex-hull method that

can be applied for measuring flatness. Huang et al. (1993) developed a so-called Control Plane

Rotation Scheme for minimum zone evaluation. Carr and Ferreira (1995) developed a procedure

that searches, by rotation, the direction vector at which two parallel planes (or straight lines

for straightness error) have the minimum distance. Damodarasamy and Anand (1999) embed a

computational-geometry mechanism within a flexible polygon search (Nelder and Mead, 1965), and

produce some remarkable computational results. Shunmugam (1987b) has developed a “median

search technique” that constructs in an iterative fashion a so-called median plane as the reference

plane and has shown that when the defining parameters of this plane are used in calculating the

form error, the latter is smaller than that obtained with the least-squares plane. Huang (1999)

developed an approach to determine straightness by using points on the vertices of the convex hull

of the measured points. Rajagopal and Anand (1999) developed a “selective data-partitioning”

technique for determining circularity error. Lai and Wang (1988), Le and Lee (1991) and Kim

et al. (2000) used a Voronoi-diagram technique, which employs the concepts of convex hull, to

compute circularity. Roy and Zhang (1992) formulated a technique that considers all possible pairs

of concentric circles for measuring the circularity error. Etesami and Qiao (1990) provide a Voronoi

diagram to determine the centers of the maximum inscribed and the minimum circumscribed circles.

Roy and Xu (1995) used a method that develops co-axial cylinders coupled with Voronoi diagrams

for measuring cylindricity. Cheraghi et al. (2003) developed a procedure that rotates the cylinder

15
in a fashion such that the circularity error in a projected circle, which can be computed relatively

easily, can be exploited to determine the cylindricity error.

We note that research in computational geometry for form-error measurement is relatively novel

and new, and it is also likely to have a significant influence on this field. As of now, however, most

industrial strength CMMs tend to use algebraic methods. This may change in the future.

16
CONCLUSIONS

Form-error computation is a critical function of the quality-control department in any precision-

manufacturing industry. Some textbooks on surface metrology have appeared (Miller, 1962; White-

house, 2002) in the open literature. However, there is no book that deals elaborately with form-error

computation, which is one reason why we felt the need for writing a review. Our review focused

on optimization techniques used in form-error metrology.

Some of the highlights of our findings are as follows. The literature on the measurement tech-

niques is broadly classifiable into two streams, namely algebraic and geometric, and within the

algebraic class, one finds two different sub-classes of techniques, namely white-box and black-box.

The complexity of the correct objective function, i.e., the zone, which is difficult to optimize as

a result, appears to be major source of the approximations that are difficult to avoid. The ap-

proximations appear in developing a surrogate (white-box) or in the technique itself (black-box).

The appeal of a linearization approach became evident because of its ability to make the objec-

tive function more easily optimizable and amendable to linear regression/linear programming. The

black-box techniques, which use this function as it is in the optimization, appear to be of an it-

erative nature may be time-consuming on the computer. It is important to note that reliance on

linear regression (least squares) in commercial CMMs can be traced to the complexity of analyzing

the zone.

An aspect beyond the scope of this paper is that of statistical issues related to sampling.

However, it must be pointed out that statistical issues can play a role in deciding whether it is

worthwhile using normal distances instead of vertical distances (Badar et al., 2003; Shunmugam,

1987a) because of the increased computational time. Also, according to Dowling et al. (1995),

the least-squares method may be safer in practice than the minimum zone error. There is also a

growing body of literature that seeks to use laser trackers for function fitting (see e.g., Yang and

Qian (2008)). Laser trackers gather data for millions of points (point cloud ) on the surface of the

part. Sampling becomes very critical as a result, since most metrology algorithms are likely to

become very slow in processing millions of points. Least squares, which requires only additions and

is not of an iterative nature, is likely to fare better in this scenario; however, the approximations it

17
introduces are only likely to be amplified.

A number of other issues related to form-error metrology were not covered in this review. We

would like to provide the reader with some pointers in these directions however. Roughness and

waviness form two other types of surface errors, distinct from form errors, and have been discussed

widely in the literature, e.g., Whitehouse (2002) and Raja et al. (2002). An interesting paper on

form-error measurement with traditional instruments such as gauges is Griffith (2002). Sample-

size determination for form-error measurement, i.e., determining the number of data points to be

selected, is a critical issue that has been examined in many papers, e.g., Dowling et al. (1997).

For an understanding of tolerance evaluation in the form-error context, please see Traband et al.

(2004). An interesting paper that considers the distribution of flatness measurements with the aim

of improving fits in assemblies is Berrado et al. (2006). Finally, form errors of complicated surfaces,

e.g., cones, have been covered in Chung and Raman (1999).

We conclude this paper with some directions for future research in form-error metrology that

we believe our review uncovered.

• The combined use of normal distances (as in Wang (1992)) and the zone (as in Chetwynd

(1985)) has not been attempted in the literature and should form an interesting avenue

for future research for all features. This is because the sequential quadratic procedure is

guaranteed to converge to the global optimum (Bazaraa et al., 1993).

• The surrogate-function approach of Gass et al. (1998) could perhaps be exploited in cylin-

dricity. The power of their approach is that the objective function can be optimized by linear

programming for which efficient software programs are available. Linearization (Chetwynd,

1979) is yet another powerful approximation that could be combined with the linear program-

ming approach of Chetwynd (1985) for circularity and sphericity.

• There is a need for developing CMM software based on computational-geometry-based tech-

niques. While software based on linear programming and statistical techniques are readily

available, software for computational geometry have to be tailor-made for the technique at

hand. However, the development of such software programs is likely to increase the usage of

18
 these techniques in industrial strength CMMs.

• There is an urgent need to study six sigma methodologies that can benefit from improved

form-error metrology. The literature on the interface of surface metrology and six sigma

appears to be scant.

ABOUT THE AUTHORS

Abhijit Gosavi has a Ph.D. in Industrial Engineering from the University of South Florida, an

M. Tech in Mechanical Engineering from the Indian Institute of Technology, Madras, and a B.E.

in Mechanical Engineering from Jadavpur University, Calcutta. His research interests are in simu-

lation modeling, Markov decision theory, and quality control. He has published in these areas, and

some of his work has appeared in Automatica, INFORMS Journal on Computing, and Management

Science. He is the Division Chair of the Industrial Engineering Division of the American Society of

Engineering Education (2010-2011). He joined as an Assistant Professor in the Engineering Man-

agement and Systems Engineering Department of Missouri University of Science and Technology

in 2008. He is a member of IIE, INFORMS, and ASEE.

Elizabeth Cudney is an Assistant Professor in the Engineering Management and Systems En-

gineering Department at Missouri University of Science and Technology. She received her B.S. in

Industrial Engineering from North Carolina State University, Master of Engineering in Mechanical

Engineering and Master of Business Administration from the University of Hartford, and her doc-

torate in Engineering Management from the University of Missouri - Rolla. In 2010, Dr. Cudney

was inducted into the ASQ International Academy for Quality. She received the 2008 ASQ A.V.

Feigenbaum Medal and the 2006 SME Outstanding Young Manufacturing Engineering Award. She

is an ASQ Certified Quality Engineer, Manager of Quality/Operational Excellence, and Certified

Six Sigma Black Belt. She is a member of the ASEE, ASEM, ASME, ASQ, IIE, SAE, and the

Japan Quality Engineering Society (JQES).

19
ACKNOWLEDGEMENTS

The authors thank Martin Wortman, Shantanu Phatakwala, and Galya Novakova for pointing

us to references in the literature.

References

ANSI: Definitions. Mathematical Definitions of Dimensioning and Tolerancing Principles, ANSI Y

14.5. American Society of Mechanical Engineers, New York, NY, 1995.

ANSI: Dimensioning. Dimensioning and Tolerancing, ANSI Y 14.5. American Society of Mechan-

ical Engineers, New York, NY, 1995.

M.A. Badar, S. Raman, and P.S. Pulat. Intelligent search-based selection of sample points for

straightness and flatness estimation. Journal of Manufacturing Science and Engineering, 125:

263–271, 2003.

M. Bazaraa, H. Sherali, and C. Shetty. Non-linear Programming: Theory and Algorithms. John

Wiley and Sons, New York, second edition, 1993.

A. Berrado, N.F. Hubele, and E.S. Gel. An empricial investigation into the distribution of flatness

measurements. Quality Engineering, 18:351–357, 2006.

A. Cardou, G. Boullion, and G. Tremblay. Some considerations on the flatness of surface plates.

Microtecnic, 26(7):367–368, 1972.

K. Carr and P. Ferreira. Verification of form tolerances, Part I: Basic issues, flatness, and straight-

ness. Precision Engineering, 17(2):131–143, 1995.

G. Chatterjee and B. Roth. On Chebyshev fits for pairs of lines and polygons with specified internal

angles. Precision Engineering, 21:43–56, 1997.

B. Chaudhuri and P. Kundu. Optimum circular fit to weighted data in multi-dimensional space.

Pattern Recognition Letters, 14:1–6, 1993.

20
S. Cheraghi, H. Lim, and S. Motavalli. Straightness and flatness tolerance evaluation: An opti-

mization approach. Precision Engineering, 18:30–37, 1996.

S.H. Cheraghi, G. Jiang, and J.S. Ahmad. Evaluating the geometric characteristics of cylindrical

features. Precision Engineering, 27:195–204, 2003.

D. Chetwynd. Roundness measurement using limacons. Precision Engineering, 1:137–141, 1979.

D. Chetwynd. Applications of linear programming to engineering metrology. Proceedings of the

Institution of Mechanical Engineers, 199(B2):93–100, 1985.

S. Chung and S. Raman. Linear methods for determination of conicity tolerance. CIRP Journal of

Manufacturing Systems, 29(4):323–327, 1999.

I. Cooper. Circle fitting by linear and non-linear least squares. Journal of Optimization Theory

and Applications, 76:381–388, 1993.

S. Damodarasamy and S. Anand. Evaluation of minimum zone for flatness by normal plane method

and simplex search. IIE Transactions, 31:617–626, 1999.

P. Dhanish and M. Shunmugam. An algorithm for form error evaluation—using the theory of

discrete and linear Chebyshev approximation. Computer Methods in Applied Mechanics and

Engineering, 92:309–324, 1991.

M. Dowling, P. Griffin, K. Tsui, and C. Zhou. A comparison of the orthogonal least squares and

minimum enclosing zone methods for form error estimation. Manufacturing Review, 8:120–138,

1995.

M. Dowling, P. Griffin, K. Tsui, and C. Zhou. Statistical issues in geometric feature inspection

using coordinate measuring machines. Technometrics, 39(1):3–17, 1997.

W. Elmaraghy, H. Elmaraghy, and Z. Wu. Determination of actual geometric deviations using

coordiante measuring machine data. Manufacturing Review, 3(1):32–39, 1990.

J. Elzinga and D. Hearn. Geometrical solutions for some minimax problems. Transportation Science,

6:379–394, 1971.

21
F. Etesami and H. Qiao. Analysis of two-dimensional measurement data for automated inspection.

Precision Engineering, 9(1):21–34, 1990.

A. Forbes. Least-squares best-fit geometric elements. National Physical Laboratories, UK, NPL

Report DITC 140/89, 1989.

M. Fukuda and A. Shimokohbe. Algorithms for form-error evaluation — methods of the minimum

zone and the least squares. Proceedings of the International Symposium on Metrology for Quality

Control in Production, Tokyo, pages 197–202, 1984.

S. Gass, C. Witzgall, and H. Harary. Fitting circles and spheres to coordinate measuring machine

data. The International Journal of Flexible Manufacturing Systems, 10:5–25, 1998.

R.C. Gilbert, S. Raman, T.B. Trafalis, S.M. Obeidat, and J.A. Aguirre-Cruz. Mathematical foun-

dations for form inspection and adaptive sampling. Journal of Manufacturing Science and En-

gineering, ASME Transactions, 131:1–7, 2009.

A. Gosavi. Algorithm development and minimum sample size in form measurement. M.Tech Report,

Mechanical Engineering, Indian Institute of Technology, Madras, 1995.

A. Gosavi and S. Phatakwala. A finite-differences derivative descent-approach for estimating form

error in precision-manufactured parts. Transactions of the ASME, Journal of Manufacturing

Science and Engineering, 128(1), 2006.

M. Gota and K. Lizuka. An analysis of the relationship between minimum zone deviation and least

squares deviation in circularity and cylindricity. Proceedings of the International Conference of

Production Engineering, New Delhi, 1977.

G. K. Griffith. Geometric Dimensioning and Tolerancing. Prentice Hall, Upper Saddle River, NJ,

second edition, 2002.

R. Grinde and J. Ventura. Minimax center estimation for inspection of spherical parts. International

Journal of Production Research, 32(9):2031–2047, 1994.

22
S. Guu and D. Tsai. Measurement of roundness: A nonlinear approach. Proceedings of National

Science Council, ROC (A), 23(3):348–352, 1999.

R. Hooke and T. Jeeves. Direct search solution of numerical and statistical problems. Journal of

the ACM, 8:212–229, 1961.

J. Huang. An exact minimum zone solution for three-dimensional straightness evaluation problems.

Precision Engineering, 23:204–208, 1999.

S. Huang, K. Fan, and J. Wu. A new minimum zone method for evaluating straightness errors.

Precision Engineering, 15(3):158–165, 1993.

ISO. Technical Drawings: Tolerancing of form, orientation, location, and runout — Generali-

ties, definitions, symbols, indications on drawing, ISO: 1101-983(E). International Standards

Organization, 1983.

T. Kanada. Evaluation of spherical form errors — computation of sphericity by means of minimum

zone method and some examinations with using simulated data. Precision Engineering, 17:

281–289, 1995.

T. Kanada and S. Suzuki. Evaluation of minimum zone flatness by means of non-linear optimization

techniques. Precision Engineering, 15:274–280, 1993.

K. Kim, S. Lee, and H. Jung. Assesing roundness errors using discrte Voronoi diagrams. Interna-

tional Journal of Advanced Manufacturing Technology, 16(8):559–563, 2000.

W. Kim and S. Raman. On selection of flatness measurement points using coordinate measuring

machines. International Jounral of Machine Tools Manufacturing, 40:427–443, 2000.

T. Kurfess and D. Banks. Statistical verification of conformance to geometric tolerance. Computer-

Aided Design, 27(5):353–361, 1995.

H. Lai, W. Jywe, C. Chen, and C. Liu. Precision modeling of form errors for cylindricity evaluation

using genetic algorithms. Precision Engineering, 24:310–319, 2000.

23
J.-Y. Lai and I.-H. Chen. Minimum zone evaluation of circles and cylinders. International Journal

of Machine Tools Design Research, 36:435–451, 1996.

K. Lai and J. Wang. A computational geometry approach to geometric tolerancing. Transactions

of the 16th North American Manufacturing Research Conference, pages 376–379, 1988.

U. Landau. Estimation of a circular arc center and its radius. Computer Vision, Graphics, and

Image Processing, 38:317–326, 1987.

V. Le and D. Lee. Out-of-roundness problem revisited. IEEE Transactions on Pattern Analysis

and Machine Intelligence, 13:217–223, 1991.

S.S. Lin, P. Varghese, C. Zhang, and H. Wang. A comparative analysis of CMM form-fitting

algorithms. Manufacturing review, 8:47–58, 1995.

D. Loebritz. CMM software: The key issue. Quality Today, pages s1–s6, 1993.

D. Marshall, G. Lukas, and R. Martin. Robust segmentation of primitives from range data in

the presence of geometric degeneracy. IEEE Transactions on Pattern Analysis and Machine

Intelligence, 23(3):304–314, 2001.

L. Miller. Engineering dimensional metrology. Edward Arnold, London, UK, 1962.

T. Murthy. A comparison of different algorithms for cylindricity evaluation. International Journal

of Machine Tool Design Research, 22:283–292, 1982.

T. Murthy. A comparison of different algorithms for circularity evaluation. Precision Engineering,

8(1):19–23, 1986.

T. Murthy and S Abdin. Minimum zone evaluation of surfaces. International Journal of Machine

Tool Design Research, 20:123–136, 1980.

V. Namboothiri and M. Shunmugam. On determination of sample size in form error evaluation

using coordinate metrology. International Journal of Production Research, 37:793–804, 1999.

24
J. A. Nelder and R. Mead. A Simplex Method for Function Minimization. Computer Journal, 7:

308–313, 1965.

S.M. Obeidat. Adaptive methods for form error determination in discrete point metrology. Un-

published Ph.D. dissertation, University of Oklahoma, Norman, OK, 2008.

C. Prakasvudhisarn, T. Trafalis, and S. Raman. Support vector regression for determination of

minimum zone. Transactions of the ASME, Journal of Manufacturing Science and Engineering,

125(4):736–739, 2003.

F. Preparata and M. Shamos. Computational Geometry. Springer-Verlag, New York, NY, 1985.

W. H. Press, S.A.Tuekolsky, W.T. Vetterling, and B.P.Flannery. Numerical Recipes in C: The Art

of Scientific Computing. Cambridge University Press, Cambridge, pp. 204-208, 1992.

J. Raja, B. Muralikrishnan, and S. Fu. Recent advances in separation of roughness, waviness, and

form. Precision Engineering, 26:222–235, 2002.

K. Rajagopal and S. Anand. Assessment of circularity error using a selective data partition ap-

proach. International Journal of Production Research, 37:3959–3979, 1999.

A. Ralston and P. Rabinowitz. A First Course in Numerical Analysis. Dover Publishers, New

York, NY, second edition, 2001.

U. Roy and Y. Xu. Form and orientation tolerance analysis for cylindrical surfaces in computer-

adied inspection. Computers in Industry, 26:127–134, 1995.

U. Roy and X. Zhang. Establishment of a pair of concentric circles with minimum radial separation

for assessing roundness error. Computer Aided Design, 24:161–168, 1992.

C. Shakarji. Least squares fitting algorithms of the NIST algorithm testing system. Journal of

Research of the National Institute of Standards and Technology, 103(6), 1998.

M. Shunmugam. On assessment of geometric errors. International Journal of Production Research,

24:413–425, 1986.

25
M. Shunmugam. Comparison of linear and normal deviations of forms of engineering surfaces.

Precision Engineering, 9(2):96–102, 1987a.

M. S. Shunmugam. New approach for evaluating form errors of engineering surfaces. Computer

Aided Design, 19:368–374, 1987b.

R. Takiyama and N. Ono. A least square error estimation of the center and radii of concentric arcs.

Pattern Recognition Letters, 10:237–242, 1989.

M. Traband, D. Mederios, and M. Chandra. A statistical approach to tolerance evaluation for

circles and cylinders. IIE Transactions, 36(8):777–785, 2004.

M.T. Traband, S. Joshi, R.A. Wysk, and T.M. Cavalier. Evaluation of straightness and flatness

tolerances using the minimum zone. Manufacturing Review, 2:189–195, 1989.

J. Ventura and S. Yerelan. The minimax center estimation problem for automated roundness

inspection. European Journal of Operational Research, 41:64–72, 1989.

M. Wang, S.H. Cheraghi, and A.S.M. Masud. Circularity error evaluation: theory and algorithm.

Precision Engineering, 23:164–176, 1999.

M. Wang, S.H. Cheraghi, and A.S.M. Masud. Sphericity error evaluation: Theoretical derivation

and algorithm development. IIE Transactions, 33:281–292, 2001.

Yu Wang. Minimum zone evaluation of form tolerances. Manufacturing Review, 5:213–220, 1992.

T. Weber, S. Motavalli, B. Fallahi, and S.H. Cheraghi. A unified approach to form error evaluation.

Precision Engineering, 26:269–278, 2002.

D. Whitehouse. Surfaces and their measurement. Taylor and Francis, New York, 2002.

Pinghai Yang and Xiaoping Qian. Adaptive slicing of moving least squares surfaces: Toward direct

manufacturing of point set surfaces. ASME Journal of Computing and Information Science in

Engineering, 8:1–11, 2008.

26
 S. Yerelan and J. Ventura. Computerized roundness inspection. International Journal of Production

Research, 26(12):1921–1935, 1988.

L. Zhu, H. Ding, and Y. Xiong. A steepest descent algorithm for circularity evaluation. Computer-

Aided Design, 35(3):255–265, 2003.

27

View publication stats