在逆向工程中對適合曲線的數(shù)據(jù)點云的預(yù)處理外文文獻翻譯@中英文翻譯@外文翻譯

1、<p><b>　　附錄</b></p><p><b>　　英文原文</b></p><p>　　The Pre-Processing of Data Points for Curve Fitting in Reverse Engineering</p><p>　　Reverse engineering ha

2、s become an important tool for CAD model construction from the data points, measured by a coordinate measuring machine (CMM), of an existing part. A major problem in reverse engineering is that the measured points having

3、 an irregular format and unequal distribution are difficult to fit into a B-spline curve or surface. The paper presents a method for pre-processing data points for curve fitting in reverse engineering. The proposed metho

4、d has been developed to process the me</p><p>　　Introduction</p><p>　　With the progress in the development of computer hardware and software technology, the concept of computer-aided technology

5、for product development has become more widely accepted by industry. The gap between design and manufacturing is now being gradually narrowed through the development of new CAD technology. In a normal automated manufactu

6、ring environment, the operation sequence usually starts from product design via geometric models created in CAD systems, and ends with the generation of mac</p><p>　　1. Where a clay model, for example, in de

7、signing automobile body panels, is made by the designer or artist based on conceptual sketches of what the panel should look like.</p><p>　　2. Where a sample exists without the original drawing or documentat

8、ion definition.</p><p>　　3. Where the CAD model representing the part has to be revised owing to design change during manufacturing.</p><p>　　In all of these situations, the physical model or sa

9、mple must be reverse engineered to create or refine the CAD model.</p><p>　　In contrast to this conventional manufacturing sequence reverse engineering typically starts with measuring an existing physical ob

10、ject so that a CAD model can be deduced in order to exploit the advantages of CAD technologies. The process of reverse engineering can usually be subdivided into three stages, i.e. data capture, data segmentation and CAD

11、 modeling and/or updating .A physical mock-up or prototype is first measured by a coordinate measuring machine or a laser scanner to acquire the geom</p><p>　　In practical measuring cases, however, there are

12、 many situations where the geometric information of a physical prototype or sample cannot be measured completely and accurately to reconstruct a good CAD model. Some data points of the measured surface may be irregular,

13、have measurement errors, or cannot be acquired. As shown in Fig. 1, the main surface of measured object may have features such as holes, islands, or roughness caused by manufacturing inaccuracy, consequently the CMM prob

14、e cannot cap</p><p>　　Fig. 1. The general problems in a practical measuring case</p><p>　　Measurement of an existing object surface in reverse engineering can be achieved by using either contact

15、 probing or non-contact sensing probing techniques. Whatever technique is applied, there are many practical problems with acquiring data points, for examples, noise, and incomplete data. Without extensive processing to a

16、djust the data points, these problems will cause the CAD model to be reconstructed with an undesired shape. In order to rebuild the CAD model correctly and satisfactorily, this</p><p>　　The Theory of B-splin

17、e</p><p>　　Most of the surface-based CAD systems express shapes required for modeling by parametric equations, such as in Bezier or B-spline forms. The most used is the B-spline form. B-splines are the stand

18、ard for representing freeform curves and surfaces in current commercial CAD systems. B-spline curves and Bezier curves have many advantages in common. Control points influence the curve shape in a predictable natural way

19、, making them good candidates for use in an interactive environment. Both types of c</p><p>　　A B-spline curve is a set of basis functions which combines the effects of n+1 control points. A parametric B-spl

20、ine curve is given by</p><p>　　p(u)= （1）</p><p>　　pi= control points</p><p>　　n+1= number of control points</p><p>　　Ni,k(u) = the B-sp

21、line basis functions </p><p>　　u = parameter</p><p>　　For B-spline curves, the degree of these polynomials is controlled by a parameter k and is usually independent of the number of control poin

22、ts, and the B-spline basis functions are defined by the following expression:</p><p>　　{ (2) and</p><p><b>　　(3)</b></p><p>　　Where k cont

23、rols the degree (k-1) of the resulting polynomials in u and thus also controls the continuity of the curve.</p><p>　　A B-spline surface is defined in a similar way to a tensor product in a B-spline curve. It

24、 is also possible to define a B-spline surface having different degrees in the u- and v-directions:</p><p><b>　　(4)</b></p><p>　　Curve Fitting</p><p>　　Given a set of da

25、ta points measured from existing object, curve fitting is required to pass through the data points. The least-squares fitting technique is the most used algorithm which aims at approximating, based on an iterative method

26、, a set of data points to form a B-spline.</p><p>　　Given a set of data points Qk, k = 0,1,2,. . .,n, that lie on an unknown curve P for certain parameter values uk, k = 0,1,2,. . .,n; it is necessary to det

27、ermine an exact interpolation or best fitting curve, P.</p><p>　　To solve this problem, the parameter values (uk) for each of the data points must be assumed. The knot vector and the degree of the curve are

28、also determined. The degree in practical applications is generally 3 (order = 4). The parameter values can be determined by the chord length method:</p><p><b>　　(5)</b></p><p><b&

29、gt;　　(6)</b></p><p>　　Given the parameter values, a knot vector that reflects the distribution of these parameters has the following form:</p><p><b>　　(7)</b></p><p&

30、gt;　　Fig.2. Curve fitting with unequal distribution of data points.</p><p>　　It can be proved that the coefficient matrix is totally positive and banded with a bandwidth of less than p, therefore, the linear

31、 system can be solved safely by Gaussian elimination without pivoting.</p><p>　　Equation (5) can be written in a matrix form: </p><p><b>　　(8)</b></p><p>　　where Q is an

32、 (m + 1) ×1 matrix, N is an (m + 1)*(n + 1) matrix, and P is an (n + 1)*1 matrix. Since m . n, this equation is over-determined. The solution is</p><p><b>　　(9)</b></p><p>　　The

33、 Requirement for Fitting a Set of Data into a B-Spline Curve</p><p>　　In order to produce a B-spline curve with a “good shape”,some characteristics are required to fit the data point set into a curve present

34、ed in B-spline form. First, the data points must be in a well-ordered sequence. When applying the program to fit a set of data points into a B-spline curve, the data points must be read one by one in a specified order. I

35、f the data points are not in order, this will cause an undesired twist or an out-of-control shape of the B-spline curve.</p><p>　　Secondly, an even dispersion of the data points is better for curve fitting.

36、In the measuring procedure, some factors, such as the vibration of the machine, the noise in the system, and the roughness of the surface of the measured object will influence the result of the measurement. All of these

37、phenomena will cause local shakes in the curve which passes through the problem points. Therefore, a smooth gradation of the location of the data points is necessary for generating a “high quality” B-spl</p><p

38、>　　Having the data points equally distributed is important for improving the result of parameter for fitting a B-spline curve. As the mathematical presentation shows in Eq. (9), the control points matrix [P] is determ

39、ined by the basis functions [N] and data points [Q], where the basis functions [N] are determined by the parameters ui which are correspond to the distribution of the data points. If the data points are distributed unequ

40、ally, the control points will also be distributed unequally and wi</p><p>　　holes, islands, and radius fillets, which prevent the CMM probe from capturing data points with equal distribution. If a curve is r

41、ebuilt by fitting data points with an unequal distribution, as shown in Fig. 2, the generated curve may differ from the real shape of the measured object. Figure 3 illustrates that a smoother and more accurate reconstruc

42、tion may be obtained by fitting an equally spaced set of data points.</p><p>　　The Pre-Processing of Data Points</p><p>　　To achieve the requirements for fitting a set of data points into a B-sp

43、line curve as mentioned above, it is very important and necessary that the data points must be pre-processed before curve</p><p>　　Fig.3. Curve fitting with unequal distribution of data points.</p>&l

44、t;p>　　Fig.4.The procedure of data points pre-processing</p><p>　　fitting. In the following description, a useful and effective method for pre-processing the data points for curve fitting is presented. The

45、 concept of this method is to regress a set of measuring data points into a non-parametric equation in implicit or explicit form, and this equation must also satisfy the continuity of the curvature. For a plane curve, th

46、e explicit nonparametric equation takes the general form: y = f (x). Figure 4 illumination an overview of the procedure to pre-process the da</p><p>　　Fig.5. Curvature is calculated by three discrete points

47、on a circle.</p><p>　　Data point filtering is the first step in displacing the unwanted points and the noisy points. The original data points measured from a physical prototype or an existing sample by a CMM

48、 are in discrete format. When the measured points are plotted in a diagram, the noisy points which obviously deviate from the original curve can be selected and removed by a visual search by the designer for extensive pr

49、ocessing. In addition the distinct discontinuous points which apparently relate to a sharp chan</p><p>　　Many approaches have been developed for generating a CAD model from measured points in reverse enginee

50、ring. A complex model is usually constructed by subdividing the complete model into individual simple surfaces. Each of the individual surfaces defines a single feature in a CAD system and a complete CAD model is obtaine

51、d by further trimming, blending and filleting, or using other surface-processing tools. When the designer is given a set of unorganized data points measured from an existing obje</p><p>　　In order to extract

52、 the profile curves for CAD model reconstruction, in this step, data points are divided into different groups depending upon the result of curvature calculation and analysis of the data points. For each 2D curve, y = f(x

53、), the curvature is defined as:</p><p><b>　　(10)</b></p><p>　　If the data is expressed in discrete form, for any three consecutive points in the same plane (X1,Y1) · (X2,Y2)

54、83; (X3,Y3), the three points form a circle and the centre (X0, Y0) can be calculated as (see Fig. 5):</p><p>　　a = (X1 + X2) (X2 - X1) (Y3 - Y2)</p><p>　　b = (X2 + X3) (X3 - X2) (Y2 - Y1)</p

55、><p>　　c = (Y1 - Y3) (Y2 - Y1) (Y3 - Y2)</p><p>　　d = 2[(X2 - X1) (Y3 - Y2) -(X3 - X2) (Y2 - Y1)]</p><p>　　e = (Y1 + Y2) (Y2 - Y1) (X3 - X2)</p><p>　　f = (Y2 + Y3) (Y3 - Y

56、2) (X2 - X1)</p><p>　　g = (X1 - X3) (X2 - X1) (X3 - X2)</p><p>　　Fig.6. The fillet of the model</p><p>　　Fig.7.The curvature change of the fillet</p><p>　　And,the curva

57、ture k of (X2,Y2) can be defined as: </p><p><b>　　(11)</b></p><p>　　Figure 6 illustrates an example in which the curvatures of a plane curve consisting of a data point set are calcul

58、ated using the previous method. The curvature of the curve determined by the data point set changes from 0 to 0.0333, as shown in Fig. 7. This indicates that there is a fillet feature with a radius 30 in the data points

59、set. Thus, these points can be isolated from the original data points, and form a single feature. By curvature analysis, the total array of data points is divided int</p><p>　　After segmentation, individual

60、groups of data points are separately regressed into explicit non-parametric equations, and then the data points can be regenerated from the regression equation in a well-ordered sequence, with appropriate spacing and an

61、equal distribution so that better fitting can be achieved. The format of the new data point set is valid for fitting into a single simple B-spline curve without inner constraints, which can be applied for further editing

62、 and modifying, such as trimm</p><p>　　Additionally, some regression errors are introduced by the regression operation between the measured points and the regression equation. In the following example, the o

63、rder of the regression equation is discussed, because it bears a close relationship to the regression errors. Given a set of existing data points, the set is regressed using a different order of the regression (order = 2

64、,3,4,5). Figure 8 illustrates the relationship between the order of the regression equations and the regressed e</p><p>　　Fig.8.The relationship between the order and the r.m.s. error.</p><p>　　

65、Implementation</p><p>　　In order to prove the effectiveness and feasibility of the proposed method – the pre-processing of data points for curve fitting, an implemented case is developed following the steps

66、of the flowchart (Fig. 9). A Mitutoyo BN706 coordinate measuring machine equipped with a Reni Shaw PH9 touch probe and SAS statistics software is used as a tool for system implementation. The measurement of the part surf

67、ace is performed via standard CMM control and measurement software (Geopak 2800). To ensure that </p><p>　　First, the cross-sectional curves describing the shape of the implemented sample are measured by the

68、 CMM. The physical object which is typically of symmetric geometry, as shown </p><p>　　Fig.9. The procedure of implemnation</p><p>　　in Fig. 11, is used in the implemented case. The CAD model of

69、 a symmetric object can easily be constructed by mirroring the symmetric features about the centerline. Therefore, some cross-sectional curves which are symmetric require only data for half the curve and then the other h

70、alf can be mirrored to generate the complete curve. The result of the measurement is shown in Fig. 12.</p><p>　　When the measurement is completed, the individual data point sets representing different cross-

71、sectional curves are processed separately. In this implemented case, the central cross-sectional curve is processed as an instance to demonstrate the procedure for pre-processing</p><p>　　Fig.10.Configuratio

72、n of system components for implementation.</p><p>　　Fig.11.The physical model implementation</p><p>　　Fig.12.The result of measurement.</p><p>　　the data points, where 144 points ar

73、e obtained in this curve, as shown in Fig. 13(a). In the data points filtering step, the noisy points and distinct discontinuous points, which obviously deviate from the group of data points, are removed directly for pre

74、-processing. After filtering, the residual data consist of 132 points, as shown in Fig. 13(b). In order to segment the data points, the curvatures of the curve representing the residual data points are calculated and plo

75、tted in Fig. 14. As the </p><p>　　of the median method in which point x1¢, the new coordinate of point x1, is the average of point x0, x1 and x2, x1¢ = (x0 + x1 + x2)/3. The result of the curvature

76、 calculation of the new points, shown in Fig. 16, may be used to segment the curve roughly. Observing the change of curvature and considering the scheme of surface construction, these filtered points are divided into sev

77、eral groups which represent individual feature curves, including the top curve, the side curve, and the fillet curve,</p><p>　　Fig.13.The steps of pre-processing the data points of the central cross-sectiona

78、l curve. </p><p>　　Fig.14.Curvature variation of the central cross-sectional </p><p>　　curve determined by original points.</p><p>　　Fig.15.Smoothing the distribution of points by

79、the media method.</p><p>　　Fig.16.Curvature variation of the central cross-sectional curve determined by new points</p><p>　　Fig.17.The entir procedure of CAD model reconstruction</p><

80、;p>　　After the segmentation step, individual groups of data points are separately regressed into explicit non-parametric equations. To eliminate the regression error caused by rough segmentation, remove several points

81、 at the start and end of each point group before regression. For example, the segmented points for the top curve are the 28th to 118th point, and the equation, regressing the 31st to the 115th point, can be obtained as&l

82、t;/p><p><b>　　(12)</b></p><p>　　Depending on Eq. (12), the data points of the top curve can be regenerated with a well-ordered sequence, pre-determined spacing and equal distribution, a

83、s shown in Fig. 13(d). The result of pre-processing the original data point measured by the CMM allows smooth curves to be fitted to the regenerated data points. Points on a curve where the curvature is equal to zero are

84、 called inflection points. In some situations, there is more than one inflection point on a curve feature which can be applied </p><p>　　When the entire pre-processing procedure is completed, the individual

85、sets of regenerated data points can be transferred to a commercial CAD system (Pro/Engineer is applied here) via the IGES format. All of the feature curves on the measured object can be completely created by fitting diff

86、erent data points sets, which are represented in B-spline form, as shown in Fig. 13(e,f). Interpolating the feature curves, the various surfaces can be constructed with the desired shape. Finally, the complete </p>

87、<p>　　Conclusion</p><p>　　Geometric modeling is a technology that is already used extensively in industrial applications for developing new products. Reverse engineering has become an important tool f

88、or CAD model construction for an existing part from the measuring data. A major difficulty in reverse engineering techniques is to fit the irregular data points of an unequal distribution into a B-spline curve. The proce

89、dure of the pre-processing of data points for curve fitting in reverse engineering is described in this pa</p><p>　　A broader interpretation of the term “reverse engineering” might perhaps involve deducing t

90、he intent of the original designer to some degree. An ideal system of reverse engineering would be able to not only construct a complete geometric model of the source object but also catch the initial design intent. By a

91、pplying the method proposed above, designers may regroup the data points in order to produce the individual feature curves for reconstructing a complete CAD model of the source object to ac</p><p><b>　

92、　中文翻譯</b></p><p>　　在逆向工程中對適合曲線的數(shù)據(jù)點云的預(yù)處理</p><p>　　逆向工程已經(jīng)成為一種從現(xiàn)存物體通過CMM測量的數(shù)據(jù)點重建CAD模型的重要工具.在逆向工程中首要的問題是:測量到的點具有不規(guī)律形式和不對等分布很難用B-spline曲線擬合。這篇論文中介紹了一種在逆向工程中用預(yù)先處理數(shù)據(jù)點來擬合曲線的方法。適合B-spline形式之前來處理先前測

93、量得到的數(shù)據(jù)點的方法已經(jīng)得到了發(fā)展。通過這種方法產(chǎn)生的新的數(shù)據(jù)點形式，適合建立光滑精確B-spline曲線的要求。這種方法的整個的步驟包括：切片，弧度分析，分割，回歸，和再生。在逆向工程中這種方法被實施和用于實踐應(yīng)用。重建的結(jié)果證實了此方法與目前流行的商業(yè)CAD系統(tǒng)的結(jié)合能力。</p><p>　　隨著計算機硬件的軟件技術(shù)的發(fā)展，對促進產(chǎn)品發(fā)展的計算機輔助技術(shù)觀念在工業(yè)領(lǐng)域已被廣泛地接受通過新的CAD技術(shù)的發(fā)展,

94、設(shè)計和制造之間的間隙已逐漸變得越來越密切。在正常的自動化制造環(huán)境下操作順序經(jīng)常是通過用CAD系統(tǒng)創(chuàng)建的幾何模型的產(chǎn)品設(shè)計開始，在幾何模型的基礎(chǔ)上，產(chǎn)生機器制造指令將原材料轉(zhuǎn)化成最終產(chǎn)品然后結(jié)束。由于意識到現(xiàn)代計算機輔助技術(shù)在產(chǎn)品發(fā)展和制造中的優(yōu)勢，因此在CAD系統(tǒng)著重要求創(chuàng)建物體的幾何模型。然而，在創(chuàng)建CAD 模型之前，產(chǎn)品發(fā)展的物理模型和樣本先被產(chǎn)生出來。</p><p>　　例如，在設(shè)計汽車主體控制面板時，設(shè)

95、計者和藝術(shù)家關(guān)于控制板的構(gòu)想到底是在什么樣的基礎(chǔ)上制造黏土模型。沒有最初的草圖，確切的記錄模型在哪里？在制造中由于設(shè)計的改變，CAD模型不得不重新修改的部分哪里？</p><p>　　在所有這些情形中。物理模型或樣本的建立是為了創(chuàng)建和建立CAD模型。與這些常規(guī)的制造順序相反，典型的逆向工程從測量現(xiàn)存的物理實體開始，這樣推斷出來的CAD模型可以更好的利用CAD技術(shù)的優(yōu)勢。逆向工程經(jīng)?？梢约毞譃?個階段：電子數(shù)據(jù)獲取

96、，數(shù)據(jù)分割，和用CAD模型構(gòu)建一個物理模型。樣本起先用CMM或激光掃描儀測量以得到以三維坐標形式存在的幾何圖案的信息。然后，為了更進一步的處理,測量結(jié)果被分割成拓撲狀。就重建模型來說，每個小區(qū)域就代表一個簡單的可以用數(shù)學方面知識描繪其簡單外表的幾何圖案特征。CAD 模型重建區(qū)域的表面是把這些表面連接成完整的可以描述被測量部分或樣本的模型。</p><p>　　然而，在實際測量方案中，存在物理樣本或模型的幾何圖案信

97、息不能被完全測量和準確重建一個好的CAD 模型的情況。一些表面測量的數(shù)據(jù)可能是不規(guī)律的，還有一些測量誤差或者表面是不要求的。如圖1所示，測量物體的主要表面可能有這些特征：由于制造的不精確引起的凹坑，凸起，或噪聲點，因此，CMM探針不能獲取一套完全的數(shù)據(jù)點來重建整個物體的表面。</p><p>　　圖1.在一個實際測量情況中的一般的問題</p><p>　　在逆向工程中，現(xiàn)存實體的測量，可以

98、通過接觸式測量或非接觸式測量技術(shù)來實現(xiàn)。然而無論用什么技術(shù)，這里都有一系列獲取數(shù)據(jù)的實際問題，例如，噪聲和不完全數(shù)據(jù)。如果沒有簡單的程序去校對這些數(shù)據(jù)點。這些問題將引起令人不期望的CAD 模型的重建問題。為了正確和滿意的重建CAD模型，這篇論文中介紹了一種先處理數(shù)據(jù)點去擬合曲線的有用和行之有效的方法，用這種方法，數(shù)據(jù)點被按指定的形式重新生成，并適合指定擬合B-spline曲線的形式，而沒有先前提到的問題。在擬合了所有曲線之后，模型的表面

99、才可能完全和曲線結(jié)合起來。 </p><p>　　B-spline曲線理論</p><p>　　通過含參數(shù)的方程，絕大多數(shù)外觀基礎(chǔ)上的CAD系統(tǒng)都表達了構(gòu)造模型的要求， 如Bezier曲線或 B-spline曲線形式，最長用的是B-spline形式，在目前商業(yè)系統(tǒng)中，B-spline曲線是標準的代表自由曲線和外表的曲線。B-spline曲線和Bezier 曲線有許多共同的

100、優(yōu)勢。用可預(yù)測的普通方法來移動控制點影響曲線形狀，使它們兩者成了構(gòu)建曲面較好的曲線形式。這兩種不同類型的曲線都具有控制點少，獨立的對稱軸和綜合價值。都表現(xiàn)出了凸凹性。然而，在局部的控制曲線形狀這方面，可能B-spline曲線表現(xiàn)出的優(yōu)勢超過了Bezier技術(shù)。如增加控制點而沒有增加曲線的度數(shù)的能力。考慮到現(xiàn)實世界中應(yīng)用的要求，在這篇論文中B-spline技術(shù)被用來代表曲線和曲面。一條B-spline曲線設(shè)定了連接n + 1個 控點。通過