JP4497520B2 - Fitting program for free curve - Google Patents

Description

  The present invention relates to a method for constructing a free curve / free curved surface, such as modeling of CAD or CG (computer graphics), and fitting to a curve / curved surface for smoothing a measurement data point sequence.

  In CAD and CG modeling, free curves and free curved surfaces are used. In addition, in recent years, when smoothing measurement data to create smooth curves and curved surfaces, fitting to free curves and free curved surfaces is also performed. Typical examples of these free curves and free curved surfaces are B-spline curves and B-spline curved surfaces. In order to smooth a B-spline curve with a given sequence of points, control points (also called control points) must be calculated. For this reason, simultaneous linear equations must be solved. Refer to p142 to 145 of Non-Patent Document 1 for how to solve this. Then, since all the control point weights are set to 1, the NURBS curve can be read as a B-spline curve.

  Also, to smooth a B-spline curved surface with a given point sequence, simultaneous linear equations must be solved twice. For how to solve this problem, p160 to 162 of Non-Patent Document 1 are helpful. In this case, since the weights of the control points are all 1, the NURBS surface can be read as a B-spline surface.

  As described above, both the B-spline curve and the B-spline curved surface have a problem that it is necessary to solve simultaneous linear equations as shown in FIG. 1 (case A), and the program becomes complicated.

  In addition, when making a smooth curve or curved surface by interpolating measurement data, it is not preferable to interpolate measurement data with noise. For this reason, the measurement data is first subjected to fast Fourier transform, high frequency components are cut in the spatial frequency domain, and then fast Fourier inverse transform is performed to obtain measurement data from which high frequency components have been removed. Subsequently, this is interpolated to obtain a B-spline curve or a B-spline curved surface. At this time, simultaneous linear equations must be solved.

  Therefore, in this process, as shown in FIG. 2 (Case B), four steps of fast Fourier transform, high-frequency component cut, fast Fourier inverse transform, and simultaneous linear equation solution calculation are required. Of these, the Fast Fourier Transform and the Fast Fourier Inverse Transformer are easily packaged because the programs are packaged in dedicated packages, and the high-frequency component cut is very simple as a program. On the other hand, solving simultaneous linear equations is complicated programmatically.

  After all, in both (Case A) and (Case B), solving simultaneous linear equations complicates the program and slows down the processing.

On the other hand, in Patent Document 1 related to the previous patent application, as shown in FIG. 3 (Case C), the point sequence p _k is fast Fourier transformed to calculate the discrete Fourier transform P ^* (u) of the point sequence, P ^* (u) is multiplied by the coefficient function C (u) to calculate the discrete Fourier transform Q ^* (u) of the control point sequence q _k , and Q ^* (u) is inversely transformed by fast Fourier transform to obtain the control point sequence q _{Since k} is calculated, it is not necessary to solve simultaneous linear equations as in (Cases A and B). Also, if a higher frequency component than this is removed by the Fourier transform plane using the cut-off frequency ε, a smooth curve or curved surface can be constructed. However, in this method, the number of control points is the same as the number of point sequences. In general, if a data point sequence is applied to a smooth curve / curved surface, the amount of data is reduced, but this method cannot cope with it.
Japanese Patent Application No. 2003-324932 Yo Miura, Kazumasa Mochizuki, “Practical NURBS for CAD / CG Engineers” published by Industrial Research Council, 2001

  Therefore, an object of the present invention is to obtain an appropriate number of data capable of constructing a smooth curve or curved surface without solving simultaneous linear equations.

  To obtain control points for B-spline curves and B-spline curved surfaces without solving simultaneous linear equations, as shown in (Case A ') of Fig. 4, the point sequence is subjected to fast Fourier transform in the spatial frequency domain. A control point is obtained by multiplying with a coefficient function and performing inverse fast Fourier transform. Both Fast Fourier Transform and Fast Fourier Inverse Transform are programs in a dedicated package, so you can easily build a program. Fast Fourier transform and fast Fourier inverse transform are very fast because they are processed by product-sum operation using a dedicated DSP (Digital Signal Processor) or DSP built-in CPU (MMX CPU). Since the operation time of multiplication is negligibly short compared to other operations, the speed can be increased compared to the method using simultaneous linear equations.

  Further, in removing high-frequency noise from a free curve / free-form surface, as shown in (Case B ′) of FIG. 5, instead of the step of solving simultaneous linear equations, a multiplication process with a coefficient function is used. In addition to being able to build a program, the processing time is also greatly reduced.

  Further, regarding the reduction of the number of control points, as shown in FIG. 6 (Case C ′), if the cut-off frequency ε of Case C is set to the Nyquist frequency in the data deletion unit, not only the high frequency component is cut. Since the number of data is also reduced by 2ε (ε <0.5) times, the number of control points can be reduced by 2ε times if a discrete inverse Fourier transform is performed to obtain the control points.

Fast Specifically described, fitting program to free curve according to the present invention smoothes the point sequence p _k B- A program for fitting a point sequence p _k to the spline curve b (t), the point sequence p _k The process of calculating the discrete Fourier transform P ^* (u) of the point sequence p _k by Fourier transform, reducing the data of the discrete Fourier transform P ^* (u) of the point sequence by 2ε times using the Nyquist frequency ε. Te low-frequency component G ^*; process of extracting only the (u 'u' = u / 2ε), multiplied by the low-frequency component G ^* (u ') to the coefficient function C (u'), the control points q _k The process of calculating the discrete Fourier transform Q ^* (u ') and the process of calculating the control point sequence q _k by inverse fast Fourier transform of the discrete Fourier transform Q ^* (u') of the control point sequence q _k It is characterized by having.

  When building a B-spline curve by smoothing a sequence of points, instead of solving simultaneous linear equations, fast Fourier transform, multiplication with coefficient function, inverse fast Fourier transform is used, and the program is simplified. A dedicated package for Fast Fourier Transform and Inverse Fast Fourier Transform can be used, so speed can be increased. Furthermore, since the number of control points can be reduced using the Nyquist frequency, the handling of data is simplified.

  First, the case C method described in Patent Document 1 (Japanese Patent Application No. 2003-324932) will be described.

When a B-spline curve passing through the point sequence p _k is expressed as p (t) using the parameter t, it is given by the following equation.

The B-spline curve p (t) can be expressed by the following equation using the control point q _k .

Here, N _{k, M} (t) is a B-spline basis function of order M and order m = M−1. N is the number of measurement data.

Now, the Fourier integral of the B-spline curve p (t) is P (u), the discrete Fourier transform of the point sequence p _k is P ^* (u), and the discrete Fourier transform of the control point q _k is Q ^* (u) And However, u is a spatial frequency. In addition, when _obtaining the discrete Fourier transform P ^* (u) of the point sequence p _{k and} the discrete Fourier transform Q ^* (u) of the control point q _k , the point sequence p _k and the control are determined from the properties of the discrete Fourier transform. Both point sequences q _k have periodicity and are considered to repeat every N.

The Fourier integral of the B-spline basis function N _{0, M} (t) in equation (2) is represented by the following equation, where F is the symbol of the Fourier transform.

  Here, sinc (u) is as follows.

Looking at equation (2), the B-spline curve p (t) is in the form of convolution of N _{0, M} (t) and q _k , so the Fourier integral P (u) of p (t) is N _0, takes the form of the product of the _M Fourier integral _{F [N 0, M (t} )] of the (t) and the discrete Fourier transform of q _k Q ^* (u). Therefore, the following equation is obtained using equation (3).

Also, the discrete Fourier transform P ^* (u) of p (t) is the periodicity of Eq. (2) and B-spline basis functions N _{k, M} (t), the period of the discrete Fourier transform Q ^* (u) It is expressed by the following formula using the property.

Here, C ′ _m (u) is a coefficient function when the order is m.
Therefore,

Using the new coefficient function C _m (u), the following equation is obtained.

The relationship between the new coefficient function C _m (u) and the order m is shown in Table 1 below.

Note that the discrete Fourier transform of the point sequence p _k can be obtained using fast Fourier transform. If the fast Fourier transform symbol is FFT, it is expressed by the following equation.

When the discrete Fourier transform Q ^* (u) of the control point is subjected to discrete Fourier inverse transform, the control point q _k is obtained. If the symbol of fast Fourier transform is IFFT, it is expressed by the following equation.

By substituting this into equation (2), the B-spline curve p (t) can be obtained.

Figure 7 shows the actual calculation procedure (how to construct a B-spline curve p (t) that interpolates the point sequence p _k ) for the most commonly used m = cubic B-spline curve. become.

The method for removing high-frequency noise from the B-spline curve p (t) that interpolates the point sequence p _k is as shown in FIG. 8 in the case of the most commonly used m = cubic B-spline curve. .

Next, the method of the present invention will be described. In the present invention, B-spline curve p (t) for interpolating N point sequences p _k is not obtained, but B-spline curve b (t) for smoothing point sequences p _k is _obtained . Then, the cutoff frequency ε (ε <0.5) is set as the Nyquist frequency (maximum frequency), and the number of control point sequences q _k is reduced to N ′ = 2εN.

In the method of the present invention, as shown in FIG. 9, the low-frequency component P ^* (u; | u | ≦ ε) of the discrete Fourier transform P ^* (u) of p _k is changed to a new variable u ′ = u / 2ε. And replace with P ^* (u; | u | ≦ ε) = G ^* (u ′; | u ′ | ≦ 0.5). From this, P frequency components ^{* (u) P * (u} ; | u |> ε) are automatically ignored.

Then, the discrete Fourier transform Q ^* (u ′) of the control points q ^* _k (N ′) of the B-spline curve is _obtained by the following equation.

Multiplying the right side of the above equation by 2ε is the discrete Fourier transform of Q ^* (u ') to obtain q ^* _k even though the number of data was N when the discrete Fourier transform P ^* (u) was obtained This is because the number of data is reduced to N ′ in the conversion, and the ratio N ′ / N = 2ε must be applied as a gain. The control point q ^* _k is obtained by the following equation.

Thus, the smoothed B-spline curve b (t) shown in FIG. 10 can be obtained by the following equation.

Here, FIG. 11 shows a specific procedure for obtaining the control point q _k of the B-spline curve b (t) for smoothing the point sequence p _k . Note that m = third order.

  Although the above description has been given for the B-spline curve, it can be easily extended to a B-spline curved surface.

  FIG. 12 shows an example of original data, and FIGS. 13 to 15 show examples of fitting to B-spline curves based on the original data. It can be seen that the original data of N = 64 points decreases according to the numerical value of the cutoff frequency ε (ε <0.5).

  In CAD and CG modeling and fitting of measurement data to curved surfaces, it can be used for applications that apply to B-spline curved surfaces while removing high-frequency noise of given point sequences.

It is a flowchart figure of the construction method of the free curve and free-form surface by (Case A) of a prior art. It is a flowchart figure of the high frequency noise removal method of the free curve and free-form surface by the prior art (case B). It is a figure which is a flowchart of the control point calculation of the B-spline curve by (Case C). It is a flowchart figure of the construction method of the free curve and free-form surface by the prior art (case A '). It is a flowchart figure of the high frequency noise removal method of the free curve and free-form surface by a prior art (case B '). It is a figure which is a flowchart of the control point calculation of a B-spline curve by (case C '). FIG. 6 is a flowchart of data flow in an explanatory diagram of a calculation procedure of a method for constructing a B-spline curve p (t) for interpolating a point sequence p _k . It is explanatory drawing of the calculation procedure of the method of removing the high frequency noise of the B-spline curve p (t) which interpolates the point sequence p _k . It is explanatory drawing of how to obtain | require the low frequency component G ^* (u ') by this invention. It is explanatory drawing of the B-spline curve which smoothes the point sequence by this invention. It is a flow chart diagram of a data flow in the illustration of the calculation procedure of the method for constructing the interpolation B- spline curve p (t) the sequence p _k points according to the present invention. It is explanatory drawing of the original data for the example of fitting to the B-spline curve by this invention. It is explanatory drawing of the example applied to the B-spline curve by this invention. It is explanatory drawing of the example applied to the B-spline curve by this invention. It is explanatory drawing of the example applied to the B-spline curve by this invention.

Explanation of symbols

p _k point sequence
b (t) B-spline curve
Discrete Fourier transform ε the Nyquist frequency of P ^* (u) point sequence
G ^* (u ') Low frequency component
C (u ') coefficient function
q _k control points
Q ^* (u ') Discrete Fourier transform of control points

Claims (1)

A program used in a computer having an input unit,
Based on the sequence p _k point input, to smooth the point sequence p _k B- in fitting program to free curve spline curve b (t) fitting a point sequence p _k,
A computer, a point sequence p _k by fast Fourier transform, a point sequence p and the process of calculating the discrete Fourier transform P ^* (u) of _k, the discrete Fourier transform of the point sequence using the Nyquist frequency epsilon P ^* ( by reducing the data of u) in 2 [epsilon] times the low-frequency component ^{G * (u ';u'} = the steps of extracting u / 2 [epsilon]) by the low-frequency component G ^* (u ') to the coefficient function C (u' ) and over, 'the process of calculating the) discrete Fourier transform Q ^* (u of the braking Gotenretsu q _k' discrete Fourier transform Q of control points q _k ^* (u) and the inverse fast Fourier transform And executing the process of calculating the control point sequence q _k
A program for fitting to a free curve characterized in that the control point sequence q _k of the B-spline curve b (t) is calculated without using simultaneous linear equations .

Images