CN110097613A - A kind of B-spline curves generation method and system based on probability calculation - Google Patents

Abstract

The invention discloses a B-spline curve generation method and system based on probability calculation. The method includes: the step of performing coordinate transformation on the input control point group, the step of normalizing the control point coordinate group, and performing binarization processing on the mapping value group and the input node group to obtain the first binary string group and the step of the second binary string group, using the probability calculation method to multiplex the first binary string group based on the second binary string group to obtain the step of the probability value group, and sequentially performing the step of the probability value group Random decoding steps for the normalized inverse operation. The system includes a coordinate transformation module, a normalization module, a binarization module, a probability calculation module and a data decoding module connected in sequence, the coordinate transformation module receives a control point group, and the binarization module receives a node group. The invention generates B-spline curves in a relatively direct calculation manner, which can greatly reduce system complexity, reduce calculation amount, and shorten calculation time.

Description

A B-spline curve generation method and system based on probability calculation

technical field

The invention relates to the field of computer graphic drawing, in particular to a method and system for generating B-spline curves by using a probability calculation method.

Background technique

B-spline curves and surfaces have many excellent properties such as geometric invariance, convex hull, convexity preservation, variation reduction, local support, etc., and are very important parametric curves in computer graphics. The drawing efficiency of B-spline curve directly affects the drawing efficiency of computer image.

In the case of known n+1 control points P _i (i=1, 2, 3...n) and node t, the general expression of the n-degree B-spline curve is as follows:

n is the degree of B-spline curve, t is the input node, and P _k is the control point.

If it is generated by direct calculation, the calculation complexity is relatively high, especially when calculating and generating high-order B-spline curves, the complexity is too high and the speed is slow. The critical path of the current direct calculation method consists of a multiplier, an adder, and the like. The time complexity of B-spline curve of degree 3 is O(t ³ ), the time complexity of B-spline curve of degree 4 is O(t ⁴ ), and the time complexity of B-spline curve of degree n is O(t ⁿ ). It can be seen that with the continuous increase of the degree of B-spline curve, the time complexity of the traditional calculation method is O(t ⁿ ) growth.

Probability calculation [1] is a numerical representation and calculation method. In probability calculation, the ratio of the number of 1s in the sequence to the length of the entire sequence is used to represent the value, and the multiplication, addition, etc. are completed by constructing a simple gate-level circuit. operation to achieve. The method of probability calculation has been applied in research fields such as digital filter, FFT, Turbo decoder, multi-code rate LDPC decoder [2-4] in recent years. Using probability calculations can greatly reduce the amount of calculations.

The references that the present invention relates to are as follows:

[1] W. Qian and M. Riedel, “The synthesis of robust polynomial arithmetic with stochastic logic,” in DAC’08: Proceedings of the 45th Design Automation Conference, Anaheim, CA, USA, Jun.2008, pp.648–653.

[2] Wu Sili, Zhou Yan, Le Yanli, Li Jiaqing. Calculation method of radar detection probability based on measured data [J]. Microcomputer Information, 2008, 7-3.

[3] Chen Jienan, Hu Jianhao. Realization of digital filter based on probability calculation [J]. China Integrated Circuit, 2010, 11.

[4] Hu Jianhao, Chen Jienan. The application of probability calculation in the realization of communication signal processing system [J]. Radio Communication Technology, 2015, 41(2): 01-06.

Contents of the invention

The object of the present invention is to provide a method and system for applying probability calculation to the drawing of B-spline curves in view of the above-mentioned problems. With a simple structure using probability calculations, a more accurate B-spline curve can be quickly drawn through a low-complexity structure and a small amount of calculation.

The technical scheme that the present invention adopts is as follows:

A method for generating B-spline curves based on probability calculations, comprising the following steps:

performing coordinate transformation on the input control point group to obtain the corresponding control point coordinate group;

The step of normalizing the control point coordinate group to obtain the corresponding mapping value group;

Performing binary processing on the values of each of the mapping value groups and the input node groups to obtain the corresponding first binary string group and the second binary string group;

multiplexing the first binary string based on the second binary string to obtain a probability value group;

The step of randomly decoding the probability value group, and performing normalized inverse operation on the decoding result to obtain the corresponding point coordinate group.

The above scheme is based on the probability calculation method to generate B-spline curves. The calculation process only involves addition, comparison and multiplexing. It belongs to the method that the complexity increases linearly with the increase of the number of B-spline curves. In the direct calculation, the complexity is The O(t ⁴ ) method greatly reduces the amount of calculation, the complexity of calculation, and the time-consuming calculation, especially when generating high-order B-spline curves.

Further, the above binarization process is a process of shifting and comparing the data to be binarized with a pseudo-random code of a preset length to obtain a comparison result.

Further, the above-mentioned multiplexing of the first binary string based on the second binary string is specifically: using the result of adding the corresponding bits of the second binary string as the multiplex control terminal, to multiplex the first binary string.

Further, in the above-mentioned normalization processing of the control point coordinate group, the normalization method is: GP _i =(A _i -min(A ₀ ,A ₁ ,A ₂ .....A _n ))/( max(A ₀ ,A ₁ ,A ₂ ....A _n )-min(A ₀ ,A ₁ ,A ₂ .....A _n )),(i=0,1,2,... n); among them, min(.) is the minimum value function, max(.) is the maximum value function, n is the number of control point groups, A ₀ , A ₁ , A ₂ .....A _n is the control point Coordinate group, GP _i is the normalized mapping value.

A B-spline curve drawing system based on probability calculation, which includes sequentially connected coordinate transformation module, normalization module, binarization module, probability calculation module and data decoding module; wherein:

The coordinate transformation module is used to perform coordinate transformation on the input control point group, and output the corresponding control point coordinate group;

The normalization module is used to normalize the received control point coordinate group, and output the corresponding mapping value group;

The binarization module is used to receive the mapping value group output by the normalization module, and also receives the input node group. The binarization module is used to binarize the received data and output the corresponding binary string. For the probability of receiving The value group corresponds to the output of the first binary string group, and for the received node group, it corresponds to the output of the second binary string;

The probability calculation module multiplexes the first binary string based on the second binary string to output a set of probability values;

The data decoding module performs random decoding and normalized inverse operation on the received probability value group to obtain the position coordinates of the drawing points.

Further, the above-mentioned binarization module is used to perform binarization processing on the received data based on the pseudo-random code.

Further, the above-mentioned binarization module includes a pseudo-random code generation unit and a comparator; the pseudo-random code generation unit is used to generate a pseudo-random code of preset length, and the output terminal of the pseudo-random code generation unit is connected to the The first input terminal of the comparator, the second input terminal of the comparator is used to receive the output value of the normalization module, and the output terminal of the comparator outputs a binary string corresponding to the data received by the second input terminal. That is, when the input of the second input terminal of the comparator is a mapping value group, its output terminal outputs the first binary string; when the input terminal of the second input terminal of the comparator is a node group, its output terminal outputs the second binary string string.

Further, the above-mentioned probability calculation module multiplexes the first binary string group based on the second binary string group specifically: the probability calculation module selects the second binary string group based on the result of adding the corresponding bits of the second binary string group A binary string is multiplexed.

Further, the above-mentioned probability calculation module includes an adder and a multiplexer, the input end of the adder is used to receive the second binary string group, the output end of the adder is connected to the control end of the multiplexer, and the multiplexer The coefficient input terminal of the selector is used to receive the first binary string group, and the output terminal of the multiplex selector outputs the probability value group.

Further, the normalization method of the above normalization module is:

GP _i ＝(A _i -min(A ₀ ,A ₁ ,A ₂ .....A _n ))/(max(A ₀ ,A ₁ ,A ₂ ....A _n )-min(A ₀ ,A ₁ ,A ₂ .....A _n )),(i＝0,1,2,...n); among them, min(.) is the function for finding the minimum value, and max(.) is the function for finding the maximum value Value function, n is the number of control point groups, A ₀ , A ₁ , A ₂ .....A _n is the coordinate group of control points, and GP _i is the normalized mapping value.

In summary, owing to adopting above-mentioned technical scheme, the beneficial effect of the present invention is:

The existing scheme adopts the method of direct calculation, and the key path of the calculation is mainly composed of multiplication. For the n-degree B-spline curve, the complexity of drawing is O(t ⁿ ), it can be seen that it grows in O(t ⁿ ), The amount of calculation is large and the calculation takes a long time. And the present invention adopts the mode of probability calculation to draw B-spline curve, and the critical path of its calculation is made up of addition, comparison and multi-way selection, for n times of B-spline curve, need to carry out 2n times of comparison, 1 time of n-bit addition and 1 multi-way selection of n+1 selection. Obviously, the calculation amount of drawing increases linearly with the increase of the number of B-spline curves, and the complexity of calculation (or system structure) increases linearly. Compared with the direct calculation method, it is significantly The calculation complexity is reduced, the calculation amount is small, and the calculation speed is fast (especially for the drawing of high-order B-spline curves), which is convenient for realization on hardware such as FPGA.

Description of drawings

The invention will be illustrated by way of example with reference to the accompanying drawings, in which:

Fig. 1 is an embodiment of the flow of the B-spline curve generation method based on probability calculation.

Fig. 2 is a structural diagram of a B-spline curve drawing method based on probability calculation.

Fig. 3 is an embodiment of the binarization module structure.

Fig. 4 is an embodiment of the probability calculation module structure.

Fig. 5 is a cubic B-spline curve drawn by the scheme of the present invention and by direct calculation.

Fig. 6 is a number of cubic B-spline curves drawn by the scheme of the present invention.

Wherein, in Fig. 5 and Fig. 6, dotted line curve is the cubic B-spline curve drawn by the scheme of the present invention, and solid line curve is the cubic B-spline curve drawn by the mode of direct calculation; Among Fig. 6, (a) is the result of taking 256-bit pseudo-random code, (b) is the result of taking 512-bit pseudo-random code, (c) is the result of taking 1024-bit pseudo-random code, (d) is taking the result of 2048-bit pseudo-random code The result of the random code.

Detailed ways

All features disclosed in this specification, or steps in all methods or processes disclosed, may be combined in any manner, except for mutually exclusive features and/or steps.

Any feature disclosed in this specification (including any appended claims, abstract), unless otherwise stated, may be replaced by alternative features which are equivalent or serve a similar purpose. That is, unless expressly stated otherwise, each feature is one example only of a series of equivalent or similar features.

Embodiment one

This embodiment discloses a method for generating a B-spline curve based on probability calculation, including the following steps:

Based on the general expression of the B-spline curve, coordinate transformation is performed on the input control point P _i (i=1, 2, 3...n), and the corresponding control point coordinate A _i (i=1, 2, 3...n) is obtained n) steps.

The coordinates of the control points are normalized to obtain the corresponding mapping value GP _i (i=1, 2, 3...n), wherein the normalization method is:

GP _i ＝(A _i -min(A ₀ ,A ₁ ,A ₂ .....A _n ))/(max(A ₀ ,A ₁ ,A ₂ ....A _n )-min(A ₀ ,A ₁ ,A ₂ .....A _n )),(i＝0,1,2,...n); among them, min(.) is the function for finding the minimum value, and max(.) is the function for finding the maximum value value function.

Based on the N-bit pseudo-random code R _i (i=1, 2, 3...n), each mapping value GP _i (i=1, 2, 3...n) and the input node t _k (k=1, 2...n) A step of performing binarization processing respectively to obtain corresponding binary strings B _i (i=1, 2...n) and Xi ( _i =1, 2...n).

S(i)=X ₁ ( _i )+X ₂ (i)+...+X _n (i), (i= 1, 2...N) as the multiplex control terminal, with B _i (i=1,2...n) as the multiplex coefficient input terminal, the probability value Y(i)=B _{S( i)} (i=0,1,2...N) steps.

Randomly decode the probability value, and perform a normalized inverse operation on the decoded result to obtain the corresponding point coordinates. Through the points on the coordinates of each point, the corresponding B-spline curve can be drawn.

Embodiment two

As shown in Figure 1, the first embodiment discloses a method for generating a B-spline curve based on probability calculation, including the following steps:

1. Based on the general expression of B-spline curve, carry out coordinate transformation on the input control point group P _i (i=1, 2, 3...n), and obtain the corresponding control point coordinate group A _i (i=1, 2 , 3...n) steps.

The expression of B-spline curve is:

Among them, P ₀ , P ₁ ,...P _n is the control point group of the curve; n is the degree of B-spline curve, such as cubic B-spline curve, n is 3; t is a decimal value between 0 and 1; k is the kth point among them, and the value range of k is 0, 1, 2,...n. Transform formula (1) to get the following formula (probability calculation polynomial):

Taking the cubic B-spline curve as an example, the expression of the B-spline curve is expanded to get:

P(t)＝1/6(P ₀ (-t ³ +3t ² -3t+1)+P ₁ (3t ³ -6t ² +4)+P ₂ (-3t ³ +3t ² +3t+1) +P ₃ t ³ ) (2)

Formula (3) is obtained from formula (2):

P(t)＝1/6((P ₀ +4P ₁ +P ₂ )+(-3P ₀ +3P ₂ )t+(3P ₀ -6P ₁ +3P ₂ )t ² +(-P ₀ +3P ₁ - 3P ₂ +P ₃ )t ³ )

(3), corresponding to the control point coordinates, the transformation is obtained:

in:

A ₀ =1/6(P ₀ +4P ₁ +P ₂ ) (5),

A ₁ =1/6(4P ₁ +2P ₂ ) (6),

A ₂ =1/6(2P ₁ +4P ₂ ) (7),

A ₃ =1/6(P ₁ +4P ₂ +P ₃ ) (8).

Through the input control point group P ₀ -P ₃ , the control point coordinate group A ₀ -A ₃ is obtained.

2. A step of normalizing control point coordinate groups A ₀ A ₁ , A ₂ . . . A _n to obtain a corresponding mapping value group GP _i (i=1, 2, 3 .

The normalization process is to map the values of each control point coordinate group A ₀ A ₁ , A ₂ ....A _n to [0,1] respectively, and the normalization mapping conversion method is as follows:

GP _i ＝(A _i -min(A ₀ ,A ₁ ,A ₂ .....A _n ))/(max(A ₀ ,A ₁ ,A ₂ ....A _n )-min(A ₀ ,A ₁ ,A ₂ .....A _n )),(i＝0,1,2,...n)(9), min(.) is the function to find the minimum value, max(.) is the function to find Maximum function.

3. Based on the N-bit pseudo-random code group R _i (i=1, 2, 3...n), the mapping value group GP _i (i=1, 2, 3...n) and the input node group t _k ( k=1,2,3...n) are binarized respectively to obtain the corresponding binary strings B _i (i=1,2,3...n) and Xi ( _i =1,2,3...n) A step of.

The binarization process transforms t _k and GP _i correspondingly into binary strings Xi and _Bi respectively _. Transform input t _k , output to get X _i , input to GP _i , output to get B _i . The conversion process is completed based on the pseudo-random code group. The literature "Pseudo-random code and computer generation" (Wu Mingjie, Du Tiancang, Journal of Liaoning University of Technology, Vol. 21, No. 2) mentioned the idea of using primitive polynomials as feedback shift registers The characteristic polynomial can generate a pseudo-random code sequence.

Pseudo-random code groups are generated by shifting primitive polynomials. Using the primitive polynomial as the characteristic polynomial of the feedback shift register, a pseudo-random code group can be generated. The primitive polynomial is as follows:

In this embodiment, the primitive polynomial is of order 10, that is, n is 10, and 110000101 feedback shift is used to generate an N-bit random code R _i , and N is respectively 256 bits, 512 bits, 1024 bits and 2048 bits for experiments. The drawing results of the corresponding cubic B-spline curves are shown in (a), (b), (c), and (d) in Figure 6.

When performing shift comparison between GP _i and R _i (i=0, 1, 2...,n), if GP _i is greater than or equal to R _i , the output is "1", and if it is less than, the output is "0". The experiment proves that in the obtained binary string of B _i (i takes 1, 2, ... n), the proportion of "1" is the same as the value represented by GP _i . This provides the basis for the application of probability calculation to the drawing of B-spline curve. If the value of GP _i is 0.4, and N is 128 bits, then the number of "1" in B _i is 128*0.4. Although the proportion of "1" in B _i is the same, because the "1" in R _i The position of " is random, so the position of "1" in the binary string in B _i is also random. Similarly, t _k and R _i are shifted and compared (i=0, 1, 2..., n), and a random binary string group X _i is obtained.

4. S(i)=X ₁ (i)+X ₂ (i)+...+X _n (i) is the result of adding the corresponding bits of X _i (i=1,2,3...n) , (i=1,2...N) is used as the multiplex control terminal, and B _i (i=1,2...n) is used as the multiplex gate coefficient input terminal to obtain the probability value group Y(i )= _BS(i) (i=0,1,2...N) step.

As shown in Figure 4, in the probability calculation, an adder and a multiplexer are used, and Xi ( _i =1,2,3...n) is used as the input end of the adder, and each bit is added correspondingly Get S(1)S(2)...S(N), where S(i)=X ₁ (i)+X ₂ (i)+...+X _n (i) (i=1, 2...N). The output terminal S _i (i=1,2,3...N) of the adder is used as the control terminal of the multiplexer, and B _i (i=1,2...n) is used as the coefficient of the multiplexer The input terminal (data input terminal), the output terminal of the multiplexer outputs Y(i)=B _S(i) (i=0,1,2...N), and the output value Y(1)Y(2 )...Y(N). The truth table of B _S(i) calculation is shown in the following table:

5. Perform random decoding on the probability value group, and perform normalized inverse operation on the decoding result to obtain the point coordinates of the curve. Through the points on the coordinates of each point, the corresponding B-spline curve can be drawn.

The random decoding method is:

It counts the ratio of the number of "1" in the binary string in Y(1)Y(2)...Y(N), and the random decoding process is the probability calculation process. Then carry out the normalized inverse operation through formula (12), and obtain the position coordinates of the drawing point.

DY＝Y(max(A ₀ ,A ₁ ,A ₂ ....A _n )-min(A ₀ ,A ₁ ,A ₂ .....A _n ))+min(A ₀ ,A ₁ , A ₂ .... A _n )(12),

DY is the output coordinate value corresponding to the input value t _k and the control point group P ₀ , P ₁ ,...P _n obtained through probability calculation. The B-spline curve can be drawn directly from the value of DY. As shown in FIG. 5, it is the cubic B-spline curve drawn by the method of this embodiment, and the selected pseudo-random code length is 512 bits.

Embodiment Three

As shown in Figure 2, this embodiment discloses a B-spline curve generation system based on probability calculation, which includes a coordinate transformation module, a normalization module, a binarization module, a probability calculation module and a data decoding module connected in sequence ;in:

The coordinate transformation module is used to perform coordinate transformation on the input control point P _i (i=1, 2, 3...n), and output the corresponding control point coordinate A _i (i=1, 2, 3...n);

The normalization module is used to normalize the received control point coordinates, and output the corresponding mapping value GP _i (i=1, 2, 3...n);

The binarization module is used to receive the data output by the normalization module, and also receives the input node t _k (k=1,2,3...n), and the binarization module is used to base the N-bit pseudo-random code on the received data Perform binarization processing and output the corresponding binary string. For the received probability value GP _i , the corresponding output binary string B _i (i=1, 2, 3...n), for the received node t _k , the corresponding output Binary string X _i (i=1, 2, 3...n);

The probability calculation module adds the result S(i)=X ₁ (i)+X ₂ ( _i )+...+X to the corresponding bits of Xi (i=1,2,3...n) _n (i), (i=1, 2...N) is used as the multiplex control terminal, and B _i (i=, 1, 2...3) is used as n as the multiplex coefficient input Terminal, output probability value Y(i)=B _S(i) (i=0,1,2...N);

The data decoding module sequentially performs random decoding and normalized inverse operation on the received data (Y(i) (i=0,1,2...N) output by the probability calculation module) to obtain the position coordinates of the drawing points. Mark the calculated drawing points on the graph to achieve the B-spline curve. As shown in FIG. 5 , the dotted line is a cubic B-spline curve drawn by the drawing system according to this embodiment when the length of the pseudo-random code is 512 bits.

Embodiment Four

This embodiment discloses a B-spline curve generation system based on probability calculation, as shown in Figure 2, which includes a coordinate transformation module, a normalization module, a binarization module, a probability calculation module and a data decoding module connected in sequence .

The coordinate transformation module includes a control point input port, which is used to perform coordinate transformation on the control point group P _i (i=1, 2, 3...n) input from the control point input port, and output the corresponding control point coordinate group A _i (i=1, 2, 3...n). The coordinate transformation method is:

The expression of B-spline curve is:

Among them, P ₀ , P ₁ ,...P _n is the control point group of the curve; n is the degree of B-spline curve, such as cubic B-spline curve, n is 3; t is a decimal value between 0 and 1; k is the kth point among them, and the value range of k is 0, 1, 2,...n. Transform formula (1) to get:

Taking the cubic B-spline curve as an example, the expression of the B-spline curve is expanded to get:

P(t)＝1/6(P ₀ (-t ³ +3t ² -3t+1)+P ₁ (3t ³ -6t ² +4)+P ₂ (-3t ³ +3t ² +3t+1) +P ₃ t ³ ) (2)

Formula (3) is obtained from formula (2):

P(t)＝1/6((P ₀ +4P ₁ +P ₂ )+(-3P ₀ +3P ₂ )t+(3P ₀ -6P ₁ +3P ₂ )t ² +(-P ₀ +3P ₁ - 3P ₂ +P ₃ )t ³ )

(3), corresponding to the control point coordinates, the transformation is obtained:

in:

A ₀ =1/6(P ₀ +4P ₁ +P ₂ ) (5),

A ₁ =1/6(4P ₁ +2P ₂ ) (6),

A ₂ =1/6(2P ₁ +4P ₂ ) (7),

A ₃ =1/6(P ₁ +4P ₂ +P ₃ ) (8).

Through the input control point group P ₀ -P ₃ , the control point coordinate group A ₀ -A ₃ is obtained.

The normalization module is used to normalize the received control point coordinate group, and output the corresponding mapping value group GP _i (i=1, 2, 3...n).

The normalization process is to map the values of each control point coordinate group A ₀ A ₁ , A ₂ ....A _n to [0,1] respectively, and the normalization mapping conversion method is as follows:

GP _i ＝(A _i -min(A ₀ ,A ₁ ,A ₂ .....A _n ))/(max(A ₀ ,A ₁ ,A ₂ ....A _n )-min(A ₀ ,A ₁ ,A ₂ .....A _n )),(i=0,1,2,...n) (9),

min(.) is the minimum value function, max(.) is the maximum value function, and n is the number of control point coordinate groups.

The binarization module also includes a node input port, and the binarization module is used to perform binarization processing on the received data based on the N-bit pseudo-random code group R _i (i=1, 2, 3...n), and obtain corresponding binary string. For the received probability value group GP _i , it corresponds to the output binary string group B _i , and for the received node group t _k , it corresponds to the output binary string group X _i , where i=1,2,3...n,k =1,2,3...n.

As shown in FIG. 3 , the binarization module includes a pseudo-random code generating unit and a comparator, and an output terminal of the pseudo-random code generating module is connected to an input terminal of the comparator. During binarization processing, the data to be processed is input to the other input end of the comparator, and the output end of the comparator outputs a corresponding binary string.

In one embodiment, the pseudo-random code generation unit is a shift register, and the characteristic polynomial of the shift register is a primitive polynomial:

In this embodiment, the primitive polynomial is of order 10, that is, n is 10, and N-bit random code R _i is generated by 110000101 feedback shift, and N is respectively 256 bits, 512 bits, 1024 bits and 2048 bits for experiments. The corresponding drawing results correspond to (a), (b), (c), and (d) in Figure 6 in turn.

The probability calculation module adds the result S(i)=X ₁ (i)+X ₂ (i)+...+X _n (i) to the corresponding bits of X _i (i=1,2,3...n), (i=1,2...,N) as the multiplex control terminal, with B _i (i=1,2,3...n) as the multiplex coefficient input terminal, output probability value group Y(i) = _BS(i) (i=0, 1, 2, . . . N).

As shown in Figure 4, in one embodiment, the probability calculation module includes an adder and a multiplexer, the input end of the adder is used to receive Xi ( _i =1,2,3...n), the adder The output terminal is connected to the control terminal of the multiplexer, the coefficient input terminal of the multiplexer is used to receive B _i (i=1, 2, 3...n), and the output terminal of the multiplexer outputs Y ( i) = B _S(i) (i = 0, 1, 2, . . . N). The truth table of B _S(i) calculation is shown in the following table:

The data decoding module sequentially performs random decoding and normalized inverse operation on the received data (Y(i)(i=0,1,2,...N) output by the probability calculation module) to obtain the position coordinates of the drawing points.

The random decoding method is:

It counts the ratio of the number of "1" in the binary string in Y(1)Y(2)...Y(N). Then carry out the normalized inverse operation through formula (12), and obtain the position coordinates of the drawing point.

DY＝Y(max(A ₀ ,A ₁ ,A ₂ ....A _n )-min(A ₀ ,A ₁ ,A ₂ .....A _n ))+min(A ₀ ,A ₁ , A ₂ .... A _n ) (12),

DY is the output coordinate value corresponding to the input value t _k and the control point group P ₀ , P ₁ ,...P _n obtained through probability calculation. The B-spline curve can be drawn directly from the value of DY. As shown in FIG. 5 , it is a cubic B-spline curve drawn according to the position coordinates output by the system of this embodiment, and the selected pseudo-random code has a length of 512 bits. The resulting error is as follows:

As shown in Figure 6, for the cubic B-spline curve drawn according to the position coordinates output by the system of the present embodiment (other multiple B-spline curve drawing results are similar), curves (a), (b), (c), (d) corresponds to 256-bit pseudo-random code, 512-bit pseudo-random code, 1024-bit pseudo-random code and 2048-bit pseudo-random code in turn. The errors of B-spline curves drawn by pseudo-random codes of different lengths are as follows:

It can be seen from the above table that as the length of the pseudo-random code increases and the difference decreases, the result will become more and more accurate.

The critical path of the system in this embodiment is composed of an adder, a comparator, a multiplexer, and the like. It can be seen from Figure 3 that the 3rd degree B-spline curve needs 6 comparators, 1 adder and 1 four-to-one multiplexer, and the 4th degree B-spline curve needs 8 comparators, 1 adder and 1 five-select one-to-one multiplexer, n-degree B-spline curve requires 2n comparators, one addition and one n+1 one-to-one multiplexer. Therefore, with the continuous increase of the B-spline curve degree, the hardware required by the probability calculation method increases linearly, and the calculation complexity is low.

The present invention is not limited to the foregoing specific embodiments. The present invention extends to any new feature or any new combination disclosed in this specification, and any new method or process step or any new combination disclosed.

Claims (10)

1. a kind of B-spline curves generation method based on probability calculation, which comprises the following steps:

The step of control point group of input is coordinately transformed, obtains corresponding control point coordinates group；

The step of control point coordinates group is normalized, corresponding mapping value group is obtained；

Binary conversion treatment is carried out respectively to the node group of the mapping value group and input, obtain corresponding first binary string group and The step of second binary string group；

Multi channel selecting is carried out to the first binary string group based on the second binary string group, the step of to obtain probability value group；

Probability value group is decoded at random, and inverse operation is normalized to decoding result, obtains corresponding set of coordinates Step.

2. the B-spline curves generation method based on probability calculation as described in claim 1, which is characterized in that the binaryzation The process of processing is compared with carrying out displacement with preset length pseudo noise code to the data of binary conversion treatment to obtain comparison result Process.

3. the B-spline curves generation method based on probability calculation as claimed in claim 2, which is characterized in that described to be based on Two binary string groups carry out multi channel selecting to the first binary string group specifically: the knot of position addition is corresponded to the second binary string group Fruit is as multi channel selecting control terminal, to carry out multi channel selecting to the first binary string group.

4. the B-spline curves generation method based on probability calculation as described in one of claim 1-3, which is characterized in that described During control point coordinates group is normalized, method for normalizing are as follows:

GP_i=(A_i-min(A₀,A₁,A₂.....A_n))/(max(A₀,A₁,A₂....A_n)-min(A₀,A₁,A₂.....A_n)), (i= 0,1,2,...n)；

Wherein, min () is function of minimizing, and max () is maximizing function, and n is control point group quantity, A₀,A₁, A₂.....A_nFor control point coordinates group, GP_iTo normalize obtained mapping value.

5. a kind of B-spline curves drawing system based on probability calculation, which is characterized in that it includes sequentially connected coordinate transform Module, normalization module, binarization block, probability evaluation entity and data decoder module；Wherein:

Coordinate transformation module exports corresponding control point coordinates group for being coordinately transformed to the control point group of input；

Normalization module exports corresponding mapping value group for received control point coordinates group to be normalized；

Binarization block is used to receive the mapping value group of normalization module output, also receives the node group of input, binarization block It is used to analyze the received data carry out binary conversion treatment, exports corresponding binary string, for received probability value group, is then corresponded to defeated First binary string group out, it is for received node group, then corresponding to export the second binary string；

Probability evaluation entity is based on the second binary string and carries out multi channel selecting to the first binary string, with output probability value group；

Data decoder module is decoded and is normalized at random inverse operation to received probability value group, and the position for obtaining graphical pointv is sat Mark.

6. the B-spline curves drawing system based on probability calculation as claimed in claim 5, which is characterized in that the binaryzation Module, which is used to analyze the received data, carries out binary conversion treatment based on pseudo noise code.

7. the B-spline curves drawing system based on probability calculation as claimed in claim 6, which is characterized in that the binaryzation Module includes a pseudorandom number generation unit and a comparator；The pseudorandom number generation unit is used to generate the puppet of preset length Random code, the output end of the pseudorandom number generation unit connect the first input end of the comparator, and the of the comparator Two input terminals are used to receive the output valve of normalization module, and the output end output of comparator corresponds to its second input terminal and received Data binary string.

8. the B-spline curves drawing system based on probability calculation as claimed in claim 5, which is characterized in that the probability meter It calculates module and is based on the second binary string group and multi channel selecting is carried out to the first binary string group specifically: probability evaluation entity is based on the The result that two binary string groups correspond to position addition carries out multi channel selecting to the first binary string group.

9. the B-spline curves drawing system based on probability calculation as claimed in claim 8, which is characterized in that the probability meter Calculating module includes an adder and a multi-channel gating device, and for adder input terminal for receiving the second binary string group, adder is defeated Outlet connects the control terminal of multi-channel gating device, and the coefficient input terminals of multi-channel gating device are used to receive the first binary string group, The output end output probability value group of multi-channel gating device.

10. the B-spline curves drawing system based on probability calculation as described in one of claim 5-8, which is characterized in that described Normalize the method for normalizing of module are as follows:

GP_i=(A_i-min(A₀,A₁,A₂.....A_n))/(max(A₀,A₁,A₂....A_n)-min(A₀,A₁,A₂.....A_n)), (i= 0,1,2,...n)；

Wherein, min () is function of minimizing, and max () is maximizing function, and n is control point group quantity, A₀,A₁, A₂.....A_nFor control point coordinates group, GP_iTo normalize obtained mapping value.