Matching 3D freeform shapes to digitized objects and its applications in shape modeling
- 格式：pdf
- 大小：189.40 KB
- 文档页数：8
Matching 3D freeform shapes to digitized objects Joris S.M. Vergeest, Sander Spanjaard and Jos J.O. JelierDelft University of Technology, Design Engineering and ProductionJaffalaan 9, NL-2628 BX Delft, The NetherlandsEmail: j.s.m.vergeest@io.tudelft.nlAbstractIn this paper the problem of matching freeform surface features against measured point data is studied. The motivation for this investigation is the recent demand for fast and robust algo-rithms to detect, to recognize and to automati-cally parameterize predefined types of shape in existing objects. These algorithms serve for the quick and accurate reuse of existing shapes in new designs of products in computer-aided design (CAD). Starting from a theory of pa-rameterized shapes, or features, we developed a practical method and algorithm to determine the occurrence of a freeform feature type in measured data, and to obtain the parameter values of the instance. The parameters not only control the optimal placement and scale of the instance but also some characteristics of the shape itself. We have investigated the influ-ence of 1) the density of the digitized points, 2) the representation form of the shape feature, 3) the matching criterion, 4) the optimization strategy. In addition, performance, graphics and user interface aspects were essential to this research. Numerical and visual examples of the method are presented.1IntroductionDetection and localization of 3D objects in scenes represented by single or multiple 2D images have become a well-established tech-nology. A related, but not so deeply investi-gated problem deals with the identification of 3D objects directly from 3D data. A number of engineering applications rely on robust and efficient shape feature recognition in 3D data, where these data can be either digitized points or synthetic data from some CAD modeling system. Reverse engineering of mechanical parts is the process of obtaining a geometric CAD model from measurements of an existing artifact [1]. The purpose of reverse engineering can be either to provide digital support for subsequent life cycle stages of a product for which no CAD model is available, or to sup-port the redesign of an existing product. To achieve either goal, 3D scanning of the product should result in a point set, at some accuracy and density. From the digitized points the di-mensions of the part or its shape can be de-rived. The generation of a CAD model requires the fitting of one or multiple surfaces to the point data and to build a valid surface or solid model from them [2]. Only for some special cases this step can be fully automated [3]. The level of automation heavily depends on the intended purpose of the CAD model. If the model is static, i.e. if properties should be de-rived from it but the model needs not to be modified, then the CAD model requires no or little structure. However, if the generated CAD model serves as a starting point for design or redesign, then the user expects a number of effective shape handles [4]. These should be based on higher-level geometric structures, or features. It is hence needed to extract an in-stance of the appropriate feature type from the point data.Beyond the domain of prismatic and cylindri-cal objects, feature handling is still a major research area. Free-form features are gaining much interest since they are considered the key elements of computer support of product styl-ing, aesthetic design and shape conceptualiza-tion in general. Recently, some Computer-Aided Industrial Design (CAID) systems have emerged, each of which is in some way based on surface features or free-form features [5,6]. Some systems are dedicated to specific types of features, for example protrusions and de-pressions [7,8].To make these type of systems really versatile and efficient, it is required to extract freeform features (or shape patterns) from existing ob-jects, where these objects are either physical (and be 3D scanned) or virtual (and be sam-pled) [4]. In any case the central problem is the fitting of 3D shape patterns against 3D point sets. An essential requirement of the fitting procedure is that it should not only find place-ment and scale parameters for the pattern, but also shape deformation parameters.In section 2 a brief comment on previous work is given. In section 3 the definitions and the problem statement are made. Both the method and its implementation are described in section 4. Results obtained by the method and a sensi-tivity analysis of the fitting procedure are pre-sented in section 5. Based on the analysis we propose further directions for an effective op-timization strategy in section 6.2Previous workM any methods of processing digitized 3D points have been developed and have become available as commercial products. The nearly automatic generation of CAD surface and solid models from scanned physical objects is becoming practice in industry [2,3]. Also searching for and the identification of features in measured data has been achieved, in as far as these features could be specified as regions with particular differential geometric properties. It is, for example, well feasible to distinguish relatively smooth regions bounded by high-curvature regions [9].Fitting of freeform features to 3D point data is a relatively new topic. However, classification schemes for freeform shape features have been proposed recently [10,11].Methods for (2D and higher dimensional)feature recognition are available, althoughmostly only applicable to gray scale images, or2D and higher dimensional solids [12]. Forsurfaces in 3D ambient space, only a fewresults are known [13,14], which are primarilydedicated to prismatic type of objects.Finally we remark that surface fitting to pointdata is by itself an established technology.These fits typically result in a set of controlpoints for a B-spline surface rather than valuesfor feature parameters of interest.3Definitions and problem statementIn the following we assume that 33 is the am-bient space of our application. However, mostof the results can be generalized to 3n, for anyn > 0.A feature type (or feature, or feature class) t is specified by a mapping G t : Q t→23, where 23is the power set (i.e. the set of all subsets) of 33 and Q t is the set Q t= P1× ... ×P m, called the parameter domain of G t. Typically P i rep-resents the domain of a continuous scalar vari-able q i(such as a dimension or an angle), but in general P i can be any set. For given q∈Q t, G t(q) specifies a subset in 33referred to as feature instance, or pattern, of type t.The problem of freeform pattern fitting to adigitized shape can be stated as follows.For given shape S⊂33, for given shape F⊆S and for given t, find q∈Q t such that d(G t(q), S) is minimal, i.e. search for)),((min FqGdttQq∈(1)where d is a difference criterion (or similarity measure) for two subsets of 33. The actual fit deals with F rather than with S as to allow the user to specify a region of interest; this disre-garding of shape beyond F might increase the performance of an implementation as well.Equation (1) should deliver the feature in-stance of type t that matches F optimally.In this paper we make the following assump-tions.Shape S approximates (a part of) the boundary of a 3D object; typically S is a discrete point set originating from 3D surface scanning.Feature instance G t (q ) represents (a part of) the boundary of a 3D solid. It can be represented as a collection of surfaces. However, degener-ate cases such as the collapsing of the feature instance into a curve or a point are not ex-cluded.The problem can be extended to search among multiple feature types t (the learning set) to find the best fit to shape F . However, in the following, we treat one type t at a time; there-fore, to simplify the notation, we omit the sub-script t .4Method of matchingWe need to specify an appropriate similaritymeasure d for equation (1). d measures the similarity of two shapes and can hence be de-fined as a function d : {G (q )} × {F } → 3.{G (q )} and {F } are the sets of all possibly occurring feature instances and shapes, re-spectively. The distance d should preferably have the properties of a semimetric, i.e for all shapes A , B , C :a) d (A , A ) = 0; any object is at zero distance to itself,b) d (A , B ) ≥ 0; a distance is nonnegative,c) d (A , B ) + d (A , C ) ≥ d (B , C ); if A is similar to both B and C then B must be similar to C .There are many similarity measures defined in the literature [12]. It can be observed that a distance criterion of the form||min max ),(b a B A d Bb A a −=∈∈, (2)has a drawback. Equation (2), known as the directed Hausdorff distance, implies that for each point a in A its distance to B is deter-mined (i.e. the minimum among the distances between a and each point in B ). The largestdistance thus found determines the value of d (A , B ). Suppose that we are searching for a shape A that matches given shape B , where A is a feature instance G (q ). A is thus a param-eterized shape. Suppose further that the pa-rameterization would allow A to degenerate to a single point A ’, located on B ; then it would hold that d (A ’, B ) = 0. Yet we would not con-clude that A ’ is similar to B (see Figure 1). A resembling problem occurs when we reverse the roles of A and B . To cure this problem the (symmetric) Hausdorff distance was intro-duced:h (A , B ) = max(d (A , B ), d (B , A )),(3)where the function d is defined as in equation (2). The Hausdorff distance is known to be robust against perturbations of the shapes, but it is very sensitive to noise and missing data [15]. A problem with h (A ,B ) is that it measures the distance between the entire objects A and B , whereas in our intended application, it is sufficient that the entire B matches any frac-tion of A , which brings us back to the directed Hausdorff distance d (A ,B ).AB Figure 1: Measuring the similarity of shape A to B .To reduce the sensitivity to noise we decided to use a variant of the directed Hausdorff dis-tance (see equation (2)) as follows:∫∈=Ar dVB r VB A d ),(1),(δ(4)where δ(r , B ) is the distance between point r ∈A and object B . The integration is over the space occupied by A , in our case a surface, or a set of surfaces, although it could also be a vol-ume or solid. The use of the integral instead of the maximum reduces the sensitivity of d (A ,B )to noise. Like the directed Hausdorff distance (2), if d (A ,B ) of equation (4) is minimized in asearch among deformable and movable shapes A, the fit would tend to propose a degenerate solution of A, unless the fit is constraint in some way. This is precisely what we propose to do, namely to introduce a particular control of the minimization process by the user. At first sight this seems a compromise, being against the trend to automate feature recogni-tion processes. However, the target application of our method intrinsically depends on the designer’s involvement [4].We need to determine the parameter vector q = (q1, ..., q m) that satisfies equation (1), based on a directed Hausdorff distance between A and B as shown in equation (4). Therefore in equa-tion (4) we substitute A by the feature template G(q) and we substitute B by the scanned (or otherwise imported) objet F. We assume that F is represented by a set of discrete points. The basic procedure for fitting the pattern G(q) to data F is shown in Algorithm 1.FIND-OPTIMAL-FEATURE-PARAMETERS(F, ε)1Obtain the points v j representing F.2q← GUESS3e← LARGE.4while e > ε5do Obtain n sample points p i from G(q). 6e← 0,7for each p i8do Find v j closest to p i.9e←e + |p i - v j| .10e←e/n.11 IMPROVE(q).12return q, eAlgorithm 1. Pattern fitting procedure using a directed Hausdorff distance.The threshold ε defines a convergence criterion for the algorithm. The quantity e is the mean of the distances between points on G(q) and object F. Algorithm 1 stops if this mean is smaller than ε. We note that in practice the fitting procedure is stopped when IMPROVE cannot deliver a new q for which e is significantly smaller than the previously obtained smallest value of e. The IMPROVE function is an optimization program doing the actual search in Q. Implicitly (not shown in the algorithm), IMPROVE evaluates the geometry of G(q) for various points in Q in order to minimize e.We have tested some properties of algorithm 1 using a particular implementation. G(q) is converted into a NURBS surface (or set of surfaces). Hence, from the parameters q the appropriate control points for the NURBS surface(s) are defined. Line 5 has been implemented by NURBS surface sampling. Line 8 is computationally the most expensive part of Algorithm 1, due to its frequent invocation by IMPROVE. If the number of points from F is of the same magnitude as n the the time complexity of the vicinity computation in Line 8 is O(n2). However, this complexity can be reduced to O(n log n) usinga space partitioning technique, see for example[16].The function IMPROVE is currently implemented by a general purpose multi-variable unconstraint function minimization software from Visual Numerics, Houston, Texas. Programming is done in Visual C++ under Windows NT. The visualization is by the Open Inventor package.5Numerical results and sensi-tivity analysisOne of the physical objects that we used to test the algorithm was a prototype of a steering wheel (Figure 2). The length of this object wasabout 130 mm.Figure 2: Physical part selected for 3D scan-ning. A region of interest, containing a ridge, is indicated.This object (S) was scanned using a mechani-cal coordinate measuring machine. From the obtained points, a particular portion (F) wasselected (Figure 3), containing 1154 points. Figure 3: Digitized points S from the physicalpart (top) and the subset of interest F ⊂S. In the point set F the ridge can still be observed. Then it is decided that a particular freeform pattern should be matched to the data F. For the numerical results presented here, the pattern G(q) that we tested was a surface containing a parameterized ridge. The parameters in effect are depicted schematically in Figure 4.Figure 4: Parameters (q) for the pattern G(q). As mentioned, the complexity of a parameterization depends on the application at hand. In this case we assumed that the pattern could be specified by 15 parameters as follows (see Figure 4):•The coordinates of the points c2 and c3 in a local coordinate system, with c1 (not shown) at its origin (6 parameters).•The width a of the pattern, the width w and height h of the ridge (3 parameters).•The orientation of the pattern in a global coordinate system (shown) (3 parameters, not shown).•The location of the pattern in the global coordinate system is defined by c1, which serves as reference point (3 parameters). For the numerical tests we kept the three points c1,c2 and c3 collinear and fixed relative to each other. Hence, 9 parameters (the 3 profile parameters and the 6 DoF for the pose) were left effective. These parameters were translated into B-spline control points for a NURBS representation of G(q).. To implement Line 5 of Algorithm 1, n points p i were sampled from the NURBS surface. These points, for n=595, are shown in Figure 5, where they are located near the digitized points from the physical object.Figure 5: To prepare for the distance computa-tion, points have been sampled from the ridge pattern G(q) (thick points); these are shown adjacent to the digitized sample F (thin points).Near the minimum of e = d(G(q), F), we have determined the sensitivity of the distance measure against the pose of the template G(q) and against the width (w) and height (h) of the ridge. The template matched the measured datawith e = 0.31 mm returned from Line 12 of the algorithm. This matching accuracy is to be interpreted relative to the geometric dimensions of G(q), approximately 30 × 8 × 2Figure 6: The directed Hausdorff distance e between the data sample and the template as a function of the z- and y-coordinate of the tem-plate.Figure 6 shows the directed Hausdorff distance e as a function of the displacement of the tem-plate along the z- and y-directions (see Figure 4 for the axes directions). As could be ex-pected, when the ridge in the template is far away from the ridge in the digitized sample F, then e is nearly insensitive to changes of y. When the two ridges match there is a small but significant drop of e.Also, there is a definite correlation between e and the three pose angles of the template G(q) (not shown).We have computed the distance e as a function of w and h near the optimum matching parameter q; the results are shown in Figure 7. Although the correlation is weak, finding the minimum appears to be feasible. We recall that we implemented the width and the height of the ridge in F by an arrangement of the control points of the NURBS surface.0.01.02.03.04.05.06W id th (m m)Distance(mm)Figure 7: Distance e as a function of the height and the width of the ridge.Sensitivity analysis revealed that some of the parameters can still be determined even if the template and the measured object (see Figure 8) are represented by very sparse data. We reduced the number of points representing F from 1154 to 230, and the points representing the template from 595 to 70. The z-coordinate still shows a clear minimum (not shown). However, the minimum of e as function of y becomes blurred as the data is reduced, see Figure 9. The risk for the fitting algorithm to be trapped into a local minimum is getting significant. These results give insight into an improved fitting strategy based on varying point densities.Figure 8: Using sparse subsamples of both G(q) and F accelerates the matching proce-dure; this figure should be compared to Figure 5.Figure 9: e as a function of y, using coarse subsamples of the data. The plot should be compared to that in Figure 6.Another issue is the, already mentioned, occur-rence of local minima in the e distributions. The fitting procedure must be robust against those. One source of local minima is aliasing due to interfering point samples, as shown in Figure 10.Figure 10: Aliasing of e plotted against x.6Further researchWe have applied a directed Hausdorff distance since our main interest was to detect whether G(q) would match to a portion of S, rather than to S itself. This justified the selection of F⊂S before the actual fits. However, when the pat-tern would contain a hole, the choice of the distance criterion needs to be revisited.Concerning the performance of the algorithm, we already mentioned the reduction of the time complexity using hierarchical space partition-ing. This is really needed, as the general pur-pose minimizer typically makes 500 calls to Algorithm 1. In the current, entirely non-optimized version of the software, one execu-tion of the loop of Lines 7 to 10 takes as long as some 4 seconds on an ordinary PC. Apart from the space partitioning we will take ad-vantage of the correlation between successive calls to the algorithm; points in F that were close to p i during call j are likely to be so in call j+1. Also, coarse subsamples of G(q) and/or F can be used for the initial stages of the fit.In the near future, the method will be general-ized for different types of patterns of freeform features, including those containing holes. Methodological research is needed to place the matching technique in a context familiar to the designer, the stylist and the CAID user.7ConclusionsWe have presented an algorithm to match pa-rameterized shape templates to digitized points. The algorithm is to become a part of an envisaged design tool for the explicit reuse of freeform shape patterns.We have demonstrated that fitting of freeform shape patterns to scanned 3D objects is feasi-ble. Pose parameters can be determined, but also shape parameters can be obtained, which have relevance for a designer. The presented method is relatively robust, even if the scan-ning is sparse and/or if the data contains noise. The technique can be applied to any freeform shape, but it can be used for prismatic objects as well. We have proposed a number of im-provements to the fitting algorithm, to increase its effectiveness and efficiency.References[1]K.A. Ingle, “Reverse Engineering”.McGraw-Hill, New York, 1994.[2]T. Várady, R.R. Martin and J. Cox, “Re-verse engineering of geometrical models- an introduction”. Computer-Aided De-sign, Vol. 29, No. 4, pp 255-268, 1997.[3]N.V. Puntambekar, A.G. Jablokow andH.J. Sommer, "Unified review of 3Dmodel generation for reverse engineer-ing". Computer Integrated Manufactur-ing Systems, Vol. 7, No. 4, pp 259-268,1994.[4]J.S.M. Vergeest, I. Horváth, J. Jelier andZ. Rusák, "Freeform surface copy andpaste techniques for shape synthesis". I.Horváth, A.J. Medland and J.S.M. Ver-geest (Eds.), Proc. 3d Int. Symp. ofCompetitive Engineering, Delft Univer-sity Press, Delft, pp 395-406, 2000. [5]J. Rowe, "Surface modeling". ComputerGraphics Wold, Vol. 20, Nr. 9, pp 47-52,1997.[6]G. Wyvill, D. McRobie and M. Gigante,"Modeling with features". IEEE Com-puter Graphics and Applications, Vol.15, Nr. 5, pp 40-46, 1997.[7]J.C. Cavendish, "Integrating featurebased surface design with free form de-formation". Computer-Aided Design,Vol. 27, Nr. 9, pp 703-711, 1995.[8]P.A. van Elsas and J.S.M. Vergeest,"Displacement feature modelling forconceptual design". Computer-AidedDesign, Vol. 30, Nr. 1, pp 19-27, 1998.[9]G. Renner, T. Váradi and V. Weiss, "Re-verse engineering of freeform features".Proc. PROLAMAT 98, IFIP, 1998. [10]B. Poldermann and I. Horváth, "Surfacedesign based on parametrized surfacefeatures". I. Horváth and Károly Váradi(Eds.), Proc. Int. Symposium on Toolsand Methods for Concurrent Engineer-ing, Institute of Machine Design, Buda-pest, pp 432-446, 1996.[11]M. Fontana, F. Giannini and M. Mei-rana, "A free form feature taxonomy". P.Brunet and R. Scopigno (Eds.), Proc. Eu-rographics'99, Computer Graphics Fo-rum, Vol. 18, Nr. 3, 1999.[12]M. Hagedoorn and R.C. Veltkamp, "Re-liable and efficient pattern matching us-ing an affine invariant metric". Int. Jour-nal of Computer Vision, 31(2/3):203-225, 1999.[13]W.B. Thompson, J.C. Owen, H. Jamesde St. Germain, S.R. Stark and T.C.Henderson, "Feature-based reverse engi-neering of mechanical parts". IEEETran. Robotics and Automation, Vol. 15,N0. 1, 57-66, 1999.[14]J.W.H. Tangelder, P. Ermes, G. Vossel-man and F.A. van den Heuvel, "Meas-urement of Curved Objects Using Gradi-ent Based Fitting and CSG Models". In-ternational Workshop on Photogrammet-ric Measurement, Object Modeling andDocumentation in Architecture and In-dustry, Thessaloniki, Greece, July 7-9,1999. International Archives of Photo-grammetry and Remote Sensing, Vol.12, Part 5W11, pp 23-30, 1999.[15]H. Alt, K. Mehlhorn, H. Wagener and E.Welzl, "Congruence, Similarity, andSymmetries of Geometric Objects". Dis-crete Computational Geometry, 3:237-256, 1988.[16]J. Jansson, I. Horváth and J.S.M Ver-geest, "Implementation and Analysis of aMechanics Simulation Module for Usein Conceptual Design System". Proc.ASME Computers in Engineering Conf.,DETC2000/DAC-14489, ASME, NewYork, 2000.。
