lanxicy.com

第一范文网 文档专家

第一范文网 文档专家

A Complete Roundness Classification Procedure

Kurt Mehlhoml Thomas C. Sherrner2 Chee K. Yap3

Abstract

We describe a roundness classification procedure, that is, a procedure to determine if the roundness of a planar object 1 is within some EO from an ideal circle. The procedure consists of a probing strategy and an evaluation algorithm working in a feedback loop. This approach of combining probing with evaluation is new in computational metrology. For several definitions of roundness, our procedure uses 0(1 /quaf(l)) probes and runs in time 0(1 /qual(f )2). Here, the quality qual(l) of I measures how far the roundness off is from the acceptreject criterion. Hence our algorithms are “quality sensitive”.

1

Introduction

In this paper, we not only raise the issue of how to define roundness but also give one of the first “complete” roundness classification procedures. It consists of a prnbing strategy that plans and makes the measurements, and a computation and decision strategy which uses the measurements to ultimately classify the object as good or bad. Traditionally, these two strategies are decoupled. In our case, the two strategies are coupled in a feedback loop, giving a holistic approach to the classification problem. This approach can be applied to other problems in computational metrology as well. Let us briefly illustrate the “standard approach’: suppose the roundness of I is defined to be the minimum width w(1) of an annulus that contains the boundary of 1. Assume that our classification problem is to accept 1 iff w(1) s CO. There are 3 steps: (i) Some probing strategy takes a predetermined number n of sample points on the boundary Ofl. (ii) The set S of sample points is then submitted to an algorithm to compute the minimum width w(S) of an annulus that contains S.

(iii) Finally, a decision policy decides to accept or

A basic task of metrology is to decide whether a given planar object is “round” within some specified bound. We call this the roundness classification problem. The literature on roundness chtssiftcation is fairly large; recent algorithmic papers include [10, 7, 3, 13, 11, 2, 6]. The area of computationalmetrology addresses this and similar problems [5, 4, 12,9, 14].

IMm-p[~ck-lnstitu@ fitr Informatik, Im Stadtwald, Ml 23 %arbrucken, ermany, ehlhorntipi.-sb mpg. de G m 2School of Computing Science, Simon FraserUniversity, Burnaby, .C. V5A 1S6,Canada,shermerOcs.sfu. ca, supB ported by the NaturalSciences and EngineeringResearch Council of Canada. 3Courant Institute of Mathematical Sciences, New York University, ew York,NY 10012,U.S.A., yapOcs .nyu. edu, N supported by an National Science Foundation Grant #CCR9402464.

tlr IWnis<ioll10make digllal Il:trd LOIIIC<01’:111 piill ol’(llIs malcII:Il till personnl or clawmml usc IS sfiII~lc(l twllmu( lic Iwn ICICLI Ilml Ihu L.(lIIIL,~ are nol made iw dIslnhlll.xl liW pr.(1111 C<mml..r(l:ll or :Id$’illllig.’.Ills, c’<11~> l righl nollce. (he Illlc ol’llw pld>llmlIflTland ils d;IICappear.

given [ha! u)pyrighl is II! IX’M)ISSN)II 01’lIw ,\C31. kI rcpuhlisll. h) posI on scrvcm or I() rcd14ril)11(c 1,1 lists. md m)lic. c IS Inc.. ‘1”() L’OIIV OIIM’$$ ISC

reject 1 based on the computed vahre w(.S). Typically, we accept iff w(S) s Eo. It is hardly clear that the policy (iii) gives a correct decision since we have substituted “w(1)” with “w(S)”. Computational geometers have traditionally focused on step (ii) only. One of the few papers that discuss the decision policies in step (iii) is found in [15]. We say that the algorithm in this paper is “complete” in the sense that we integrate all three steps, and we prove that our decision policy is correct with respect to the original object 1, not with respect to the sampled set S. Let us fix some notations for the paper. An object f is defined to be any compact simply-connected subset of the plane, with boundary denoted by bd 1.

rctltlirt> >l\cLuIiL

pmnisswn mflor fc~ ( ‘hItfpMmmrrd( ;MMIICIJ:) X icc I;rwx Y( ‘mwri!.hi 1997

,\CiVl()-X()7() I-87X-’)9706

S3.~lJ

129

For a point p, we use R(p, 1) and r(p, 1) to denote the maximal and minimal distance from p to a point in bd 1 respectively], i.e., I/(p, 1) = max(dist(p, q); q c ball] r(p, f) = min[dist(p, q); q e ball}. Our distance measure is the Euclidean distance. when I is understood, we write R(p) instead of R(p, 1) and r(p) instead of r(p, 1). Let ro > 0 and co > 0 be parameters, which we consider fixed throughout the paper. An object I is called (r-o,~o)-rowui or good2 if there is a point p such that ro(l – co) s r(p) s R(p) s ro(l + CO). An object is called bad ifit is not good, In Figure 1, the shaded objects Cl and Cz are bad while C3 and C4 are good.

,’ ,. ,,

of all objects /’ with Sn ~ bd 1’ is either collec~ively good or bad. Without additional assumption on / this will not be the case for any finite n. In this paper, we use the following approximate roundness assumptions, Minimum Quality Assumption(MQA and CMQA): 1 is a body and there is a point p and 8 > 0 such that R(p) s ro(l + ~) and r(p) z ro(l – c!), where ti = 1/20 and co s 6/2. If we further assume that 1 is convex, then we denote the assumption by CMQA. The constant 1/20 in MQA is arbitrary and is easily replaced by larger values. But we feel that the MQA assumption is not critical for practical purposes: modern processes for manufacturing round bodies can easily satisfy our requirement. But the

.“,’ ‘. . . . .. / ‘----‘ ,,’ .. . . . . . ---CT ‘.

a. -. ,,-- ,----0’ 0

,./,-. -.,

‘.

,

,,

..

‘.

,!

,,

,,

\ ‘,

convexity assumption in CMQA is limiting. However, we believe that our techniques can be extended

!,

!:

,,

‘$ ‘. .

‘.

to replace convexity by a bound on the maximum possible negative curvature 2

Main Results

c1

..

...,

,“

.’

,’

..- . . ...--”

......~

/’

,, -------

‘.

,’ ,, ,, ,, ,:

! ,

.

‘.

.,

‘.

,, ,,

I

., ,

,’ ,, ,, ,,

.’

----- -.. ‘. ., ,,

‘. ,,

We explain the intuitive idea of our main results, us-

\

,,

~,

,, >,

‘.

‘. ’--C4 ‘.. -

‘.

‘. . .

.,,

/’

,,

/’

/

,’

--”

Figure 1: Objects Cl and Cz are “clearly” bad; C3 is “clearly” good but the classification of C4 as good is less evident. The four identical annuli indicated by dashed circles have radii ro( 1 – CO)and ro( 1 + 60).

We use the @rger probing model of [ 1]. It postulates that the measurement device can identify a point in the intenor of 1 and can probe along any ray, i.e., determine the first point on the ray in bd 1. Note that this is a simple mathematical model for Coordinate Measurement Machines (CMM’S). CMM’S are considered the state of the art in this area [14]. In this probing model, n probes yield a set S. of at most n points in bd 1. A necessary condition for the classification procedure to be correct is that the set

ISince M / is a CIOSMI bounded set theminimummd mmimum exist. 2this definition of roundness is hy far not the only conceivable one, It is catled referenced rounding in [2]. Our results hold for several other definitions of roundness as we will show in section 5.

ing the objects Cl, . . . . CA in Figure 1. We shall assume that C~’s are known a-priori to be convex. We say that Cl is “clearly” bad because its violation of the outer circle of radius ro( 1 + co) is easily witnessed by the four corners of Cl. (This depends on the convexity assumption.) So if our probe strategy yields a set of points that contains some approximation to each of these four comers, we can confidently reject Cl. Likewise, Cz is bad as witnessed by the 4 indicated points on its boundary, and C3 is witnessed to be good by the 8 indicated points on its boundary. Although Cd is good, it cannot be witnessed by any finite set of points. Informally, the reason is that the roundness of C4 is arbitrarily close to the boundary between “good” and “bad”. We measure this closeness to the boundary by the “quality measure” (the quality of C4 turns out to be o). For a point p, let qucd(p, 1) = min{(r(p) – (1 – Eo)rO,

(1 + ~o)rO – R(p)]/rO,

and let qual(l) = mpmquaf(p, 1).

We call a point p with qual(p, 1) = qual(f) a center of 1 and use c] to denote a center of 1. Let A be

the anntdus with inner radius (1 – co)ro and outer radius (1 + co)ro. For a good object, cl defines a

130

placement of I such that bd I : A and the distance between bd I and bd A is maximized. and for a bad object, c1 defines a placement of I that minimizes the distance between bd 1 n cpl A and bd A. Here, cpl A denotes the complement of A. The minimum

quality assumption implies thatqual(l ) > –(~ –(.) and that (1 –ti)ro s r(cf) s R(cl) s (1 + A)ro. We now state our main results, Basically, we show classification procedures whose complexity is quality sensitive:

Theorem 1 Under assumption CMQA there is a classijlcation algorithm that classifies any body

The strategy is based on two simple subroutines: For any point p, the pair of horizontal probes directed towards p, one from the left and one from the right, is called the horizontal pair for p. If pt and p, are the two contact points returned by the horizontal pair for p, define H(p) = H] (p) to be

is defined to be m. Similarly, the two vertical probes directed towards p, one from above and one from below, is called the vertical pair for p. If the corresponding two contact points are pa and pb, we define V(p) = Vi (p) to be (pa + pb)/2. For completeness, define H(m) = V(m) = cm.

(P? + P,)/2. Note pt = cm iff p, =

that Y(P) = y(H(P)). m; in this case, H(p)

.41s0,

I in time 0(11/qua/(1)1 0(1 l/qual(l)l) probes.

log 11/qual(l)l)

with

Theorem 1 is based on the following two theorems. The following theorem has independent interest:

Theorem 2 Under assumption MQA, six probes and constant running time sufice to determine a point co with dist(co, CI) 5 26r0.

Theorem 4 Let CI be a center of 1 and let p = R(c1 )/r(cl ) – 1. Let p. be any point in the interior of/ and let co = H(V(H(po))). If p ~ 0.1 then dist(co, c]) s p . r(c{ ).

Let co be as in the theorem above and let n be any positive integer. For any integer i, O < i < n, send a ray along the direction 2mi/n, and let Sn be the set of contact points. The quality of Sn is a good approximation of the quality of 1.

Theorem 3 Under assumption CMQA, lquaf(Sn ) –

Proofi In the following analysis, assume without loss of generality that the center cl is at the origin, and r(cl ) is normalized to 1. Let

PI := H(PO),

P2 := V(PI),

p3 := H(p2).

x(pl)

So co = pJ. Without loss of generality, assume > 0 and y(p2) ~ O. First we show an upper bound onx(pl) = Ix(pl) – X(co)l: X(pl) ~

qual(l)l = 0(1/n) in fime O(n log n).

and qual(Sn ) can be computed

42p+p2.

(1)

The complete classification algorithm is given in Figure 2. By Theorem 3 there is a constant c such that lqual(Sn) – qual(l) I s c/n. Therefore, n cannot exceed c . qual(l) and Theorem 1 follows. Note that this procedure runs forever if the quality is O(as when 1 = C4 in Figure 1). In practice, we should stop the algorithm when the quality becomes sufficiently close to O. The structure of the paper is as follows. In section 3 we prove Theorem 2 and in section 4 we prove Theorem 3. In section 5 we extend our results to a larger class of quality measures and in section 6 we list open problems. 3

Initial Placement

There are two cases to consider.

J

case 1 . . . ..Y

-y = J(po)

Figure 3: –1 ~ y(pI)

S 1

We provide a simple strategy for finding a point co close to the center c1 of f. This result has independent and practical interest. For instance, there are highly specialized roundness-measuring machines. Traditionally, the placement of an object in such machines are carried out manually. Our result means that one can easily automate this process withjust 6 initial probes.

Case 1: –1 s y(pI)

s 1. Refer to Figure 3.

Let u], uz be the points where the honzontaf line y = y(po) intersects the unit circle centered at co. Let xi = x(ui) (i = 1,2) and X] < x2. Since the unit circle is contained in 1, the left probe contacts 1 at the x-coordinate xt where Xt s XI. Let X3 be the positive x-coordinate where this line intersects the circle of radius 1 + p centered at

131

Compute

a point co as in Theorem 2.

tl 2; =

Repeat n=2 *n;

Determine S. and compute qual(S,, ) and an interval [f, u] containing qual(l). unti10 g [/, u] If (/ > O) declare 1 good; If (u < O) declare f bad;

Figure 2: The complete classification algorithm. and its suffices to show e s 5p/4. Define h as in Figure 4(ii). A simple calculation shows that e+h=l, and hence e=l– r 1 –gz. h=@g2

co. Since I is contained in the circle of radius 1 + p, the right probe contacts I at the x-coordinate xr where x, s x3. So x (P1) = (xt +x,)/2 s (x] +xJ)/2. Furthermore, since xl = —X2,x(pl) s (.T3 — x2)/2. The quantity X3 – X2 is largest when y(po) = 1 or –1; in this case, the Pythagorean theorem shows

X3—X2= /(1 +PP-

12 =

J-.

Thusx(pl)

Case2: y(pI)

s Jm/2.

.: –1 ory(pl)

Using the Taylor expansion

>1.

We may define x3, xl and XT as in case 1.

(1 –X)ll*

=

1–

Clearly both xt and x, are no greater than

x3.

(

(

;+

X2 T+ X2

X3 R+... ) X3

16(1 –x) ‘

I%us, X( PI) =

(xt + xr)/2

5

x3.

The

coordinate x3 is largest when y equals 1 or – 1, in which case x3 = ~~. Thus X(pl) s J2P + P2. In either case, we obtain the desired bound(1). Notice that pl need not lie inside 1. Hence it is important to argue that pz = V (pl ) is finite. But this follows from the fact that I is a connected set. But in fact, it is easy to show something stronger, namely Pi (for any i ? ~) actually lies inside 1. To see this for p2, observe that X(p]) <0.5, (2)

>

1–

;+F+

)

and on substituting x = g2 in the expression fore,

g2

‘<~+ Using g2 <0.25, e<g2

.g4

d

~+16(1–g2)”

(

;+++*

)

9g2 <~.

which in turn follows from (1) and p s 1/ 10. Next we show ly(p2) – y(co)l < 5p/8, which, under our assumptions, amounts to: Y(P2) s 5P/8. (3)

From g2 = 2p + p2 <2. lp, we conclude that e < 5p/4, which proves (3). We next show lx(p3) – ,r(cl)l s 13p/25. Assuming without loss of generality that x(P3) 2 0, this amounts to x(p3) s 13p/25. (4)

Refening to Figure 4(i), let the line x = x (p I) intersect the unit circle centered at co at the points VI, VZ. Let yi := y(ui ) (i = 1, 2) and yl c yz. The line also intersects the circle of radius 1 + p at the positive y-coordinate yq. As in the proof of ( 1), Case 1, we have Y(P2) s (Y3 – yz)/2. Now the maximum value ys – YZobtains when x(pI ) is maximized. By (1), x(p[ ) s ~~. Let g := ~~ and e represent y3 – YZ when x(pl) = g. So Y(P2) s e/2

With reference to Figure 5(i), let the line y = y(pz) intersect the circles centered at co with radii 1 and 1 + p atthe positive x-coordinates x; and x4, re-

spectively. The above analysis shows x(P3) s (x5 – x~)/2. Assuming without loss of generality that y(p3) 2 0, the value of x$ – X; is increasing with y(pz). Let e’ be the value of X4 – X4 when y(p2) = 5p/8, as in Figure 5(ii). Since

132

I

Q

1,2

q

PI :

VI

—

R

t

(i)

(ii)

Figure 4: Second set of probes: bounding y(pz).

(i)

(ii)

Figure 5: Third set of probes: bounding x (p3).

Y(P2) 5 5P/8, this means x(p3)

s e’/2.

It remains

4

Uniform and Near-Uniform

Probing

to bound e’. Putting 6 = 5p/8, In this section we prove Theorem 3. Recall that we determine a set S. = {uo, . . . . U.–I ) of n points in bd I arranged in clockwise order by uniform probing about co, i.e., by probing along the directions 2mi/n for all i, O s i < n. Let cs be the center of S. and define the core C of 1 by C = {p ~ 1; r(p, 1) 2 (1 –40ro}. We show that c1, co, and C.Slie in the core and that if p and q are points in the core and u and w are points in bd 1 then Zupw < 6L uqw. This implies that lvic~ui+l is at most 12ri/n for all i, O s i K n, i.e., the uniform probing about co amounts to near-uniform probing about C.Swith about the same sampling density. Finally, we show that the nearuniform probing about cs implies that Iqual(I) – qual($l = 0(1/n).

“

=

m--

using an abbreviated version of the previous Taylor expansion. Since 62 = 25p2/64 < p/25, we get e’ c 26p/25, verifying (4). From (3) and (4) we conclude that that II – p3 CIIIs p (5/8)2 + (13/25)2 < p, and the theorem m is proved. Theorem 2 is an easy consequence of Theorem 4 and MQA. MQA implies implies p = R(cf)/r(c/)– I s (1 +d)/(1 –6)– 1 sO.1 and hence dist(co, cl) < p - r(c[ ) = R(c[ ) – r(c] ) S

26r0.

133

4.1

Uniform probing about co amounts to nearuniform probing about C.S.

Lemma 5 The points c1, co, and cs lie in C, R(p, 1) s (1 + 6il)ro for any point p E C, and dist(p, q) ~ 106r0 for any two points p and q from the core. The minimum quality assumption yields r(c~, 1) z (1 –J)ro and hence c] c C and Theorem 2 states that dist(c[, co) s 2&0. Thus r(co, 1) ? (1 – 3c5)r-oand hence co c I. For cs we show dist(c~, c1) s Mro. Assume w.1.o.g. that c1 is at the origin. We show x (es) s 2i5r0, from which the claimed bound on dist(cl, c~) follows by symmetry and elementary calculation. First note that qual(l) s qualS = qual(cs, S) implies Jl(cs, S) s (1 + ~)ro. Next note that n is always a multiple of 4 and hence one of the probes is made along the negative x-axis. It hits 1 in a point whose x-coordinate is at most —(1 — i3)r0. Thus R(cs, S) ? (1 – ~)ro + X(CS) and the bound on X(CS) follows. I is contained in a disk D of radius ( 1 + ~)ro and hence no point in the core of 1 can have distance huger than 56r0 from the center of D. This implies I?(P, 1) s (1 + 60ro for any point p q C, and dist(p, q) s 10?wofor any two points p and q from n. the core. Proof

Figure 6: Situation in the proof of lemma 6

Now we come to the general case. Assume w.1.o.g, ru S rW. Consider the circle with radius r = ru about v and let z be the intersection of this circle with the line 1 through q and w; z is unique since rW ~ r > rq. Then 2P = [Vpw = [Vpz + [Zpw. The angle 1 vpz is bounded by @ by the argument above. If z lies in the wedge ,!vp w we also need to bound Lzpw. Let a be the point on 1 closest to p, let y = lapz and q = /zpw, cf. Figure 8. Then cosy = ra/rU and COS(V y) = rO/rU. +

Lemma 6 Let p and q be points in the core of I and let v and w be points in bd I such that 2LY= [vqw.

Then 2/3 = [vpw ~ 12ci.

Pro& If a z m/12 there is nothing to show. Assume, otherwise. Then arcsin 2 tanCY< 3cr. For a point x we use r. to denote dist(p, x). We proceed in two steps. First assume r = ru = rw. We show P 5 3CY. Let L = 2flr/(2z) be the length of the circular arc from v to w. We bound L from above. We may assume w.1.o.g. that p is at the origin and thatq lies on the positive x-axis, cf. Figure 6. We claim that L is maximal if the axis of the

wedge W = f vq w aligns with the negative x-axis. Indeed consider any other orientation of W‘s axis and consider turning W‘s axis towards the negative x-axis. Then L will grow as long as the “forward leg” of W is longer than the “rear leg” of W. The worst case situation is therefore if W’s axis aligns

P

m

1’

q

c

Figure 8: Bounding q

with the negative x-axis, cf. Figure 7. We have r z (1 – 46)ro, z S 10&o, tana = y/(x+ z), sine = y/r, and x 5 r. Thus,

(x+ Z).

Since cos(y + q) = cos y cos q – sin y sin q this implies sin q = (COS cos q – cos(y + V))/ sin v y < (COS – cos(y + q))/ sin y y — = ((rW – rU)rd)/(rV . rW) . (1/sin y).

tanu ~ztana

sin/1 = y/r =

r

134

v

“h

r

P=<

w

Figure 7: Worst Case

Wehavecosy = ra/ru s 68/(1 –4A) s l/10 and hence sin y = ~? J~W z 9/10. 1( remains to bound (ru – rv )/rW. An obvious bound is 108/(1 – 46), which is, however, much too weak for our purposes.

b

with 2~ s Tr/4 and that the iteration 2A = 6cr, 2@i+[ = 6ct+arcsin 2~1/3 converges monotonically towardsthis solution. A simple induction shows that all iterates stay bounded by 12U. Indeed, 2f30 s 12a md if 2~i ~ 12CXand hence arcsin 2~i /3 s m arcsin & s 6cI then 2~i+1 s 12u. 4.2

qual(Sn) approximates quaf(l)

P

L?’’”._

u r

2P

w

We now conclude our proof of Theorem 3. Let O = JT/n and let S = {uI ...}.} G bdl be the points determined by probing along directions 2t?i, O < i < n, from co. Then luicoui+] = 28 and luic~ui+l s 120, where c~ is the center of S by Lemma 6. Let rs = r(cs, $ and RS = R(cs, S). Lemma 7 rs(l – 18n/n2) s rscos66 s r(cs, 1) s rs. (5)

Figure 9: Bounding rw minus ru

Consider the line L. through u and w and let b be the point closest to p on L; b may or may not lie between u and w. If b lies between u and w then (rw – ru)/rw S s < ; (rw – rb)lrw 1 –cos2p 2sin/32 2p.

If b does not lie between v and w we have rh ? (1 – 46)ro since otherwise a neighborhood of b is contained in 1 and hence v # bd 1 by the convexity of 1. Let r = [bpu. We have cos r = rh/rV and cos(2#? + T) = rbl ru,, cf. Figure 9, and hence (rW – rU)/rW = — – < < — 1 – cos(2#? + r)/cos r 1 – cos2~ + (sin r/ cos r) sin 2A4 2sin2/? + (1/cosr)sin2~ 2/?(1+ l/cos r).

Proofi The upper bound on r(cs, 1) is immediate. For the lower bound, choose q q bd 1 at distance r(cs, 1) from cs. The point q lies angularly between some two samples ui and vi~l around cs. Let 20 = luics~i+l s 120. Since 1 is convex, the line segment [V;, ui+l ] must be contained in 1. Convexity furthermore implies thatthe point q does not lie on the same side of this segment as cs does. Thus, the distance r(cs, 1) from cs to q is at least the distance D from cs to the segment. This distance D is minimized when the distances from cs to ui and from cs to vi+1 are both rs; in this case D = r-scos o ? cos 60, as desired. See Figure 10. The lower bound in terms of n follows from B 0 = x/n and COSO~ 1 –02/2.

Lemma8 Let z = R(cs, 1)/r(cs,

1). Then Rs

Since COST = r~/ru ~ (1 – 46)/(1 + 66) z 1/2 we conclude (rW —rU)/ r~ s 6P and hence sin v 5 6/1/9. Substituting into 2P –6CY s q yields sin(2/1 – b) ~ 2#3/3. This implies 2j3 s 12U. Note that the equation sin(2~ –&) = 2f3/3 has a single solution

Rs < R(cs, 1)

<

COSO sintl~ – ~ Rs(l + 187r/n).

135

For the upper bound in terms of n, observe that sinm s a and z =< (1 +d)/(1 —A) implies

cosc7-sinc7 = ~ and hence

Z2– 1 O/z2– 1

1 –sin2a–sin I–CT(1+W”2)

R(cs, ~) ~ Rs(l + 30) ~ Rs(] + 18T/n).

Figure 10: A lower bound on r(c~, 1)

Lemma 9 qual(.Sn) – 207r/rr s qual(l) s quczl(.S) and qual(Sn ) can be computed in time O (n log n).

Proofi The lower bound on R(CS, 1) is immediate. For (he upper bound, choose q q bd 1 at distance R(CS, 1) from c~, lying angularly between two samples vi and ui+I when seen from cs. Let 20 = LlJiCsU;+I <120. The maximum value of R(cs, 1) is obtained when vi and vi+1 are both at distance Rs from cs, q is on the bisector of Lvic~~i+ 1, and the lines q ui and q vl+l are both tangent to the circle of radius r(cs, 1) centered at cs. This situation is illustrated in Figure 11.

Proof qual((l) s qual(Sn) follows directly from S G bd 1. For the lower bound, let rs = r(cs, S) and Rs = R(CS, S) and observe

~ = > >

=

qual(cs, I) min(r(cs, 1) – (1 – co)ro,

(1 + co)ro – Rs)/ro

min(rs(l – 18m2/n2) – (1 – co)ro, (1 + co)ro – Rs(l + 18m/n))/ro qual(S) – 187r max(rs/rO,

qual(S) – 203r/n. Rs/ro)/n

The bound on the running time follows from [2]. m 5

Other Quality Measures

There are many ways to quantify the roundness of an object besides the one used above. For example, we may require Figure 11: An upper bound on R(cs, 1)

q

Let 1# be the angle about c~ formed by vi+ 1 and the point where q ui+ 1 is tangent to the circle of radius r(cs, f). Then )-(CS, 1) Rs ‘

that the inner radius r(p) lies in some interval [ro – El, r.+ Ez] and the outer radius R(p) in some interval [ro – c3, ro + c4], or thatthe width R(p) —r-(p) lies in some interval [0, c5] or thatthe relative width (R(p) –r(p))/r(p) in some interval [(), I%]or lies

q

cos+=—

cos(l/1 + a) =

)-(CS,

1)

q

R(cs, 1)

q

Rearranging the latter equation,

R(cs, 1) =

that the average distance of a point in bd 1 from the center c lies in some interval [r. –

c7, ro + E7].

r(c,s, 1) cos(~ + u) r(c~, /) cos ~ coso – sin + sin o

Rs cosu – ~(RS/r(cS, /))2 – 1 sino “

=

=

The approach described in this paper is readily extended to the first three constraints above and in fact to a large class of constraints that can be formulated in terms of an annuhts containing the boundary of the body to be classified. Let 7 = {~1, . . . . A} be

136

a family of functions of two real arguments. We call fi the i-th measure ofqua/i~. For a point p let

qual(p, 1) = ,rn)nk fi(r(p, 1), R(p, 1))

We next turn to the second property that qual(S,, ) is a good estimate of qual(l). Assumption CD: For all sufficiently large n, all X-

be (he quality of the body I with respect to p and let qual(l) = mflmqual(p, 1)

centers of f and all $-centers of S~ lies in the core of 1. The quality functions fl, . . . . fk are differentiable and have bounded derivative.

Lemma 11 Under assumptions CDwehave Iqual(l) – qual(Sn)l CMQA, BM, and = 0(1/n).

be the quality of I. We call a point p with qual(I) = qual(p, i) an F-center of I and use C3,[ to denote an :-center of I. The examples above lead to the quality functions ~1(r, R) = r – (ro – EI), fz(r, R) = ro + E2 – r, f3(r, R) = R – (ro –63),

f4(r, R) = ro+c4 – R, f5(r, R) =65 –(R –r),

Proofi

By the first part of assumption CD any C3. S of S lies in the core ~-center cs = of I. Also co lies in the core and hence r(cs, 1) – 0(1/n) s r(cs, 1) s r(cs, S) and

R(c5, S) fi((r(cs. s R(cs, 1) s R(cs, S) + 0(1/n) by 1), R(c~, J)) –

and ~G(r, R) = q – ( R – r)/r. The specialization ~={~l,~l,~q,~d)andcl =~z ==3 =q=coro was considered in the preceding section. Our approach hinges on the following two properties . the quafity of the sample S = Sn can be computed efficiently and

q

Lemmas 7 and 8. Thus, (Ifi(r(cs,

S), R(cs, S))1 = 0(1/n)

and hence

qual(l)

> ?

qual(c~, qual(cs,

1) S) — 0(1/n).

The same argument with C3,1 instead of cs shows qua)(l) = S s qual(cf, 1) qual(cl, S) + 0(1/n) qual(S) + 0(1/n).

the quality of Sn is a good estimate for the quality of 1.

With respect to the first property we observe that the overlay of the furthest and nearest site Voronoi diagram partitions the plane into cells (= regions, edges, and vertices) with the property that for all p in a fixed cell the radii r(p, S) and R(p, S) are determined by a small number of points in the sample S, namely two points for regions, three points for edges, and four points for vertices. For a cell f let S,f be the points in S that determine r(p, S) and R(p, S) for all p in j. AssumptionBM: Let f be a cell and let F be the affine hull of f; F is either the plane, or a line, or a vertex. We assume that the function p ~ qual(p, S~ ) for p e F has only a bounded number of local minima and that these minima are computable in constant time. Assumption BM M certainly satisfied for any quality measure based on the functions fl, . . . . fc above. We proceed under assumption BM. For each f, the equations fi = fj, 1 s i < j c k, partition F into cells wherein each cell we have a fixed ordering of the values of fl ,..., f~. Thus, determining the local minima within a cell amounts to a bounded size (since lSf I s 4) optimization problem. We determine the Iocaf minima of qual(p, Sf ) in F and then test these minima for containment in f. The “surviving” minima are candidates for the Y-center of S. The total number of candidates is 0(n2). We conclude: Lemma 10 Under assumption BM the quality of a sample S of size n can be computed in time O (n2 ).

m Assumption CD is satisfied for afl quality measures based on functions f], . . . . fs. It is not satisfied for the measure qual(p, 1) = f6(r(P, 0, R(p, 1)). Under this measure the center may lie at infinity and not within 1.

12 Under assumptions CMQA, BM, and CD, there is a classi$cation algorithm working in time 0(11/qual(l)12) time with 0(11/qual(l)l) probes. Theorem

Rook The algorithm was already given in section 1. Its correctness and performance follows immediately from Lemmas 10 and 11. n 6

Dkcussion and Open Problems

Our work rises many open problems: We have introduced several notions of roundness, and given a general procedure for their associated classification problems. It seems to us that the different notions of roundness are useful for different applications. It is unclear why the width measure to(l) is dominant in practice. What is the influence of the probing model? For example, what happens for a “line prober” that is able to determine the tangent to the object perpendicular to a specified direction. We conjecture that the error of approximation reduces from O( 1/n ) to 0(1/n2).

137

We claim only a running time of O(n2) for determining qr.M/(.Sn For two quality measures a time ). bound of O(nlogn) can be obtained: For refer-

[ 10] U. Roy and X. Zhmg. Establishment of a pair of concentric circles with the minimum radial separation for assessing rounding error. Computer Aided Design,

24(3):161-168, 1992. [ 1I] Michiel Smid and Ravi Janardan.

enced roundness this is shown in [2] and for width this is shown in [6]. Can the time bound be improved for other quality measures. Does the approach extend to more complicated classification tasks, e.g., determining roundness of a three-dimensional object? In our approach we keep the probing center co fixed although CS. is known to be a much better approximation of c1 as n gets large. Can this be exploited? Is an approach thatclassifies “clearly good” and “clearly bad” objects quickly and takes longer on “borderline objects” of interest to actual metrology? Of course, in practice, one should modify our decision procedure to simply accept or reject once we have determined that the quality is smaller than some constant. This is the decision policy issue studied in [ 15]. Measurement devices make errors [8]. How can this be taken into account? 7

Bibliography

[12]

[13]

[14]

[ 15]

On the width and roundness of a set of points in the plane. Department of Computer Science Report TR 94-62, University of Minnesota, 1994. Vijay Srinivasan and Herbert B. VOelcker, editors. Dimensionali’blerarrcirtgurdMetrology, 345 East 47th c Street, New York, NY 10017, 1993. The American Society of Mechanical Engineers, CRTD-VOI.27. Kurt Swanson. An optimal algorithm for roundness determination on convex polygons. In Proc. 3rd Workshop Algorithms Data Struct., volume 709 of Lecture Notes in Compuler Science,pages601-609, 1993. Chee K, Yap. Exact computationrd geometry and tolerarrcing metrology. In David Avis and Jit Bose, editors, Snapshots of Computational and Discrete Geometry Vol.3. McGill School of Comp.Sci, Tech.Rep. No,SOCS-94.50, 1994. A Volume Dedicated to Godfried Toussaint. Chee K. Yap and Ee-Chien Chang, Issues in the metrology of geometric tolerancing. In M. Overmars, editor, Prw Workshop on Algorithmic Robotics. SpringerVerIag, 1996. (to appear) Lecture Notes in Computer Science.

References [1] RichardCole and Chee K. Yap. Shapefrom probing. [2]

JournalofAlgorithrrrs, 8:19-38, 1987. CtI. Duncan,M.T.Gtiich, andE,A.Ramos. Efficient

approximation afgorithtns and optimizationalgorithms for computational metrology. In Proc. SODA 97, pages

121-130, 1997. [3] H. Ebara, N. Fukuyarna, H. Nakano, and Y. Nakanishi.

Roundness algorithms using the Voronoidiagrams. In Conf Comput. Geom,, page 41, 1989. [4] Sbaw C. Feng and Theodore H. Hopp. A review of current geometric tolerancing theories and inspection data analysis algorithms. TechnicalReport NISTIR-4509, NationalInstituteof Standardsand Technology, U.S. Departmentf Commerce.FactoryAutomation o Systems Division, Gaitbersburg, MD 20899, February 1991. [5] A, B. Forbes. Geometric tolerance assessment. NPL Technical RepmtDITC 210/92, Nationat PhysicalLab oratory,Divisionof Information Technologyand Computing,NPL,Teddington, iddlesex,U.K. TW1I OLW, M October, 1992. [6] J. Garcia and P.A,Rarnos. Fittinga set of points by a circle. In Prac. ACM Conference on Computational GeAbstracts 1st Card. ometry, 1997. [7] V. B. Le and D. T. Lee. Out-of-roundness problem revisited. IEEE Tmns. Pattern Anal, Mach, Intell., PAMI-

13(3):217-223, 1991.

[8] S. D. Phillips, B. Borchardt, and G. Caskey. Measure-

ment uncertain y considerations for coordinate measuring machines. NIST Technical Report NISTJR 5170, National Institute of Standards and Technology, NIST, Precision Engineering Division, Building 220, Roam B113, Gaithersburg, 20899, April, 1993. MD [9] U. Roy, C.R. Liu, and T.C, Woo. Review of dimensioning and tolerancing: representation and processing, Compurer-aided Design, 23(7):466-483, 1991,

138

相关文章:

更多相关标签: