# Methods and apparatus for compression and recovery animation path using a linear approximation

The invention relates to animate three-dimensional graphical models. The technical result is to effectively compress the data in the form of the interpolator for quick transfer and storage of data. The compression device includes an interpolation unit of analysis to highlight a certain number of points of discontinuity of the animation path and output keys and key values corresponding to the points of discontinuity, an encoder for encoding keys, encoder key values and statistical coder. When performing analysis of break points receive an encoded bit stream having a minimum number of break points. 5 C. and 15 C.p. f-crystals, 14 tab., table 2.

The technical field to which the invention relates

The present invention relates to animate three-dimensional (3D) graphical models, and more particularly to devices for compressing and restoring animation path, which is used in the animation, using a linear approximation, as well as to methods of compression and recovery trajectory animation used in these devices, and the data formats for these devices and methods.

Prior art

In 3D computer animation use changes in the area of colors and so on simulated three-dimensional object (3D object).

In Fig.1 shows a diagram illustrating the trajectory animation in 3D-animation, and the vertical axis represents the key values (KLUCHEVSKAYA), and the horizontal axis represents the key (KEY).

As shown in Fig.1, the trajectory 20 animation depicts the trace animation of 3D model 10. The trajectory of 20 information animation is a two-dimensional curve, time-varying, as shown in Fig.1. The trajectory animation can be presented in many ways, the explanation of which is given in Chapter 9 of the book A. K. Jain, "Fundamentals of digital image processing", published by Prentice Hall in 1989 (A. K. Jain, "Fundamentals of Digital Image Processing", Prentice Hall, 1989).

In the expression obtained using the interpolator, the trajectory 20 animation, shaped curve, as shown in Fig.1, it is possible to imagine defined by straight lines using a variety of segments. Significant information in this expression includes break points or vertices of each specific segment of a straight line. In this case, the break point or vertex is expressed as points on the trajectory 20 animation, shown in Fig.1. Using linear interpolation, you can restore the source of the information, used in the modeling language virtual reality (YVR) or in the fourth version of the compression algorithm of the moving image, developed by the Expert group on cinematography, i.e., the algorithm EGC-4 (MPEG-4). The processed information includes keys and key values, and linear interpolation is performed using the specified information.

Interpolators can be divided roughly into 6 types: scalar interpolators, position interpolators, coordinate interpolators, orientation interpolators, normal interpolators and color interpolators. Among them is a scalar interpolators can be expressed as shown in Fig.2. The features and functions of the 6 types of interpolators shown in table 1, all of the interpolators are sets of preset keys and key values corresponding to those keys.

In Fig.3 shows a conventional scheme to explain the data format of the 3D animation and shows the encoder 30, a decoder 40, 50 format data files 3D animation. In this case, the format 50 files of the 3D animation, the output of the encoder 30 is formed so that it contains the model data, animation data, attributes, video/texture and sound.

the animation. 3D animation data is expressed using AMUR or MPEG-4, formed with the information shown in Fig.3. Although for audio, video and 3D models developed standardized compression technology, the only technology General purpose compression-oriented expression developed for the interpolator to determine the trajectory of the animation. In the animation, which includes audio and/or video data, the amount of data for trajectories animation along with 3D models is most necessary amount of data.

Consequently, together with the compression technology of 3D-models of important and compression technology trajectories animation. Although binary format for scenes (IPS) conforming to the MPEG-4 provides the main method of quantization and/or compression for animation, this method does not reflect the technology that is used for interpolation, and technology of General purpose, and has poor operating characteristics of compression. This is described in the article by EUI C. Janga "Encoding 3D animation: its history and its substantive provisions" in Proc. of the International conference and exposition on media, held in new York in 2000 (Euee S. Jang 3D Animation Coding: its History and Framework", proceedings of the International Conference on multimedia and Expo held in New York city in 2000).

In Fig.4A and 4b present the Noah device for compression, it is shown in Fig.4A, performed by block 60 scalar quantization, and the known device for recovery, shown in Fig.4b, made by block 70 scalar dekvantovanie. The original trajectory animation is entered in the form (key, key) through the input output VH in block 60 scalar quantization, as shown in Fig.4A, and is subjected to scalar quantization. The encoded bit stream, which is the result of scalar quantization is output via the output OUT1. Block 70 scalar dekvantovanie shown in Fig.4b, this takes the encoded bit stream through the input output VH and displays data in the form of restored animation path (key, kluchevskoye) through the output OUT2.

Compression using interpolator in the known IPS corresponding to the MPEG-4 requires scalar quantization, as shown in Fig.4A. Known compression process shown in Fig.4A, is applicable not only to the interpolators, but all items that require compression in DFS. In reverse order of compression, the trajectory animation is restored by block 70 scalar dekvantovanie, and this occurs with the use of an encoded bit-stream input investsoglasheniya interpolators are compressed in the same way, without taking into account the characteristics of each species (interpolators), so that compression cannot be maximized.

Summary of the invention

In order to solve the above problems, a first object of the present invention is to develop a device and method for compressing animation path using a linear approximation, in which carry out efficient compression of animation in the form of the interpolator so that the transmission and storage of data can be performed quickly.

The second objective of the present invention is to develop a device and a method of restoring animation path, designed for efficient recovery of data of the compressed animation path.

The third objective of the present invention is to develop a data format for data compression animation path.

To solve the first problem of the present invention, an apparatus for compressing animation path with the interpolation unit of analysis for extracting a predetermined number of points of discontinuity of the animation path and output keys and key values corresponding to the points of discontinuity, the encoder keys for encoding key that is output from the block terpolation analysis, and statistical coder for statistical coding of keys and key values that are encoded in the encoder key and the encoder key values, respectively, and output the encoded streams of bits.

For solving the second problem of the present invention, an apparatus for restoring animation path with statistical decoder for receiving the encoded bit stream and statistical decoding of the bit stream, the decoder key to accept the statistical decoding and the decoding key, the decoder key values for the reception of the statistical decoder for decoding the key values and the interpolation unit of recovery to get a blank key values by linear interpolation based on the keys and key values decoded in the decoder key and the decoder key values, respectively, and restore the original animation path.

To solve the first problem of the present invention is also a method for compressing animation path, including the stages at which there are a predetermined number of points of discontinuity of the original animation path, allocate keys and key statisticheskoe encoding encoded keys and key values to obtain the encoded streams of bits.

For the second objective, the present invention is also a method of allocation of points of discontinuity animation path, comprising the steps are (a) choose two break points at both end points of the original animation path points gap on the animation path, (b) choose one break point among the remaining break points, with the exception of two selected points of discontinuity (in) interpolate the key values of the remaining break points, excluding the selected break points, using the selected break points, (g) form of the approximated trajectory animation based on the selected break points and interpolated key values, choose the approximated trajectory animation, which has the smallest difference in trajectories between the original trajectory animation and this approximated trajectory animation, and choose break points corresponding to the selected animation path, and (d) choosing one break point among the remaining break points, with the exception of break points selected in steps (a) and (b), and repeating steps (b)-(d) until such time as the difference of the trajectories will not be less than the allowable difference.

The difference between the trajectories is preferably expressed by the sum of kierowanie trajectory animation.

The difference of the trajectories in orientation interpolator preferably defined as the differential angle differential rotation transform, representing the difference between the rotation transformation of the original animation path and the rotation transformation of the approximated trajectory.

For the second objective, the present invention is also a method of restoring animation path, including the stages at which admit and statistical decoding of the encoded bit-stream decode the keys and key values based on the statistical decode and recover the original trajectory animation, receiving a blank key values by linear interpolation on the basis of the decoded keys and key values.

To solve the third problem of the present invention proposed a data format of a bit stream obtained by encoding the animation path, and this data format has a label key to specify the key values, the axis of which is selected among the key values corresponding to the coordinate x, y or z of each point of discontinuity animation path, the key of the array to indicate that, IU the or each z break point, and the key values of the array to specify the key values selected for each break point.

Brief description of drawings

The above-mentioned objectives and advantages of the present invention will become more apparent from the detailed description of preferred specific embodiments of the invention given with reference to the accompanying drawings, where

in Fig.1 shows a diagram illustrating the trajectory animation in three-dimensional animation (3D animation),

in Fig.2 presents an example of an expression animation path used in the modeling language virtual reality (YVR) or MPEG-4,

in Fig.3 presents the conditional diagram illustrating the data format of the 3D animation,

in Fig.4A and 4b presents the block diagram of the known devices for compression and recovery animation path, respectively,

in Fig.5A and 5b shows the block diagrams of devices for compression and recovery animation path according to the present invention, respectively,

in Fig.6 presents a block diagram of a preferred specific variant of implementation of the device for compression according to the present invention, shown in Fig.5A,

in Fig.7 presents a block diagram of a preferred specific varying.8A - 8h presents diagrams illustrating a preferred specific variant selection of break points using a linear approximation according to the present invention,

in Fig.9 presents a diagram illustrating the method of obtaining the difference between the actual trajectory of the animation and the approximated trajectory animation,

in Fig.10 presents a diagram of the quantization process, and more particularly widely used method of encoding by means of differential pulse code modulation (DICM),

in Fig.11a - 11th presents diagrams showing the formats of encoded streams of bits according to the present invention,

in Fig.12 shows a table illustrating the decoding process, expressed in the syntactic expression according to the present invention,

in Fig.13A - 13d shows the graphs of experimental animation sequences for comparison of the compression method according to the present invention with a known compression method,

in Fig.14a - 14f presents diagrams illustrating another preferred specific variant selection of break points using spherical linear approximation according to the present invention.

Description of preferred specific options oussa expressions, used in AMUR and/or MPEG-4, and areas that use interpolators include computer games online, animation ads, etc.,

In Fig.5A shows the block diagram of the device for compressing animation path according to the present invention, which includes a block 80 interpolation analysis, the encoder 82 keys (encoder 82), the encoder 84 key values (KZN-encoder 84) and the statistical encoder 86. In Fig.5b shows the block diagram of the device for recovery animation path according to the present invention, which includes a statistical decoder 90, the decoder 92 keys, the decoder 94 key values and the block 96 interpolation recovery.

Block 80 interpolation analysis device for compression, shown in Fig.5A, selects the keys and key values to be coded, and can be designed to suit the characteristics of different types of interpolators. An example of a detailed analysis will be explained below.

In Fig.6 presents a block diagram of the preferred alternative implementation of the device for compression according to the present invention, shown in Fig.5A. Device for compression, shown in Fig.6, includes a block 80 interpolating the l 104, mode differential pulse code modulation (DICM-quantizer 104), the encoder 84 key values with block 106 quantization by DICM (block 106 DICM-quantization), and the statistical encoder 86.

In Fig.7 presents a block diagram of the preferred alternative implementation of the device for recovery according to the present invention, shown in Fig.5b. This device for recovery includes the statistical decoder 90, the decoder 92 keys with inverse quantizer 126 mode of DICM (DICM-inverse quantizer 126), the decoder 94 key values with DICM-inverse quantizer 128, and the interpolation unit recovery with block 95 interpolation key recovery and key values.

Interpolation expression, applied to the input of block 80 interpolation analysis, includes keys (K) and key values (KZN). In the device for compression, shown in Fig.6, block 80 interpolation analysis adjusts the number of break points in such a way that the trajectory of the animation, which is injected through the input output VH, can be expressed using the minimum number of break points. If the original number of points of discontinuity animation path is N, then //img.russianpatents.com/chr/8804.gif">N). That is, the block 80 interpolation analysis highlights the break point from the original animation path input input output VH.

In the interpolator key and the key value can accordingly be normalized and used. For this purpose, the block 100 to normalize normalizes each of the keys and each of the key values on the original animation path input via the input output VH, and outputs the normalized results in block 102 minimize points of discontinuity. Key supported AMUR has a value in the range between 0 and 1 inclusive.

The way that the block 80 interpolation analysis adjusts the number of points of discontinuity can be defined in such a way that minimizes the difference between the animation path formed by the selected break points, and the original animation path. For this purpose, the block 102 minimize points of discontinuity produces a break point, selected on the basis of normalized key and normalized key values, which are derived from the block 102 normalization in such a way that minimizes the number of selected points of discontinuity. For example, in the case of a position interpolator block 102 minimize points of discontinuity defines a break point in such a way that minimizes the area defined by the block 80 interpolation analysis.

Now will be explained the selection of the break points using a linear approximation performed in block 102 minimize points of discontinuity shown in Fig.6.

In Fig.8A - 8h presents diagrams illustrating the preferred option allocation of break points using a linear approximation according to the present invention. Each point on the trajectory animation is a point of discontinuity. In Fig.8A presents the original trajectory animation. In Fig.8b shows the process of searching both end points (a, b) this trajectory. In Fig.8C shows the process of selecting a break point that is nearest to the original trajectory. In Fig.8d shows the break points a, b and C, which are selected first. In Fig.8E shows the process of selection of the second break points that are close to the original trajectory. In Fig.8f shows the break points a, b, C and D, which is selected by the second. In Fig.8g shows the break points a, b, C, D and E, which are selected third. In Fig.8h shows the break points a, b, C, D, E and F, which selected the fourth.

When the source trajectory animation set such as shown in Fig.8A, repeats the process of searching for points of discontinuity (M break points, 2MN), which is to the of triva (N) on the original animation path, both end points a and b are the starting point. This process is shown in Fig.8b - 8h. At the same time, you can repeat the selection of points of discontinuity until then, until it is determined that the curve approximation is close enough to the original curve.

With reference to the accompanying drawings method, which uses the difference of the areas described below as a method of obtaining the difference between the curve approximation and the actual curve.

In Fig.9 presents a diagram illustrating the method of obtaining the difference between the actual trajectory of the animation and the approximated trajectory animation. Referring to Fig.9, note that the difference between these two trajectories is expressed by the trapezoid or "twisted" by the trapezoid. Equation (1) to obtain the area of the trapezoid and the equation (2) to obtain the square "twisted" trapezoid below. The difference between the actual trajectory 200 animations and approximated trajectory 210 animations can be expressed by the sum of the area of trapezoidal and square "twisted" trapezoidal. The sum of these squares is the difference (D_{PL}) space between the two trajectories, as shown in equation (3).

In the positional interpolator key values represent position in 3D space with X, Y and Z, and the trajectory animation is represented by the three curves in the X, Y and Z. the Block 80 interpolation analysis may allocate a break point on each axis, and at the same time break point on each axis may differ from the break point on the other axis. In the following table 2 shows the result of using the new breakpoints in block 80 interpolation analysis of the actual trajectory, with 8 break points (t0, T1, T2, T3, T4, T5, T6 and T7).

In table 2, "Metcalf" refers to the key label, and KZN_{x}, KZN_{y}and KZN_{z}represent the key values in the X, Y and Z respectively. "On" indicates that the selected key value corresponding to the coordinate x, y or z each break point. N is eastwoodiae any axis at each point of discontinuity, is not selected. Key label indicates the key values, the axis of which is selected among the key values for the axes X, Y, Z at each point of discontinuity. For example, "7" indicates that all key values for all axes is selected, and "6" indicates that all selected key values, except for the key values KZN_{x}for the x-axis.

As shown in table 2, the point T1, T3 and T6 gap refer to the optional break points (marked with a dash " - " in the column "Metcalf"), because the break point is not selected none of the key value for the axes X, Y and z t0 and T7 are the points gap on both ends of the trajectory, in which the selected key values for all axes. In T2 is not selected the key value for the X axis, but the selected key values for the other axes. Therefore, the block 80 interpolation analysis determines the keys corresponding to the 5 break points, instead of the original 8 break points, and defines the key values for each axis, corresponding to the selected break points. Table 2 shows that the required 5 keys and 11 key values. The corresponding relationship between the key and key values can be represented with the label key (key label), which is transmitted separately. Thus, the number of her key values plus one additional key label. Therefore, through this process is achieved by simplifying the expression.

In Fig.14a - 14f presents diagrams illustrating another preferred variant selection of break points using spherical linear approximation according to the present invention. On these drawings is shown a method of reducing the number of break points (also called key frames) in orientation interpolator.

In Fig.14a shows the key value (=Q_{0}, Q_{1}, Q_{2}, ..., Q_{n}in each point of discontinuity with respect to the number n+1 time points on the original animation path, and these key values are marked with black dots. As shown in Fig.14b, first choose two break points (=Q_{0}, Q_{n}), corresponding to the two ends of the animation path. These selected break points are shown as white dots.

In Fig.14C shows the process of choosing the break point (the third break point) among the remaining break points, except for the two end points of the gap. At this point, the number of ways of selecting one break point is (n-1). In Fig.14C shows an example in which you select two candidates (=Q_{1}, Q_{k}). For each of the (n-1) candidates using three already in is not selected. Comparing the original trajectory animation and each of the (n-1) trajectories candidates animation, obtained by interpolation, choose the trajectory candidate of the animation, with the smallest difference of the trajectories. Break point corresponding to the selected trajectory candidate of the animation, choose among (n-1) points-candidates gap. As an example in Fig.14d depicts a variation in which the selected path candidate 2, as shown in Fig.1. The error between the trajectories obtained by using the notion of the mean error E_{cf}.

Referring to Fig.14, note that the fourth break point is chosen, performing the process explained with reference to Fig.14C and 14d, after point selection candidate disparity among the remaining break points, with the exception of three selected points of discontinuity shown in Fig.14d. As an example, in Fig.14f shows that the selected candidate 1. Repeating the process of selecting points in the candidate shown in Fig.14, up until the average error does not become less than the permissible error, choose the break point, the number of which is the same as the number of points of discontinuity of the source trajectory, or less than the number of points of discontinuity of the source trajectory.

Below is poyasneniy rotation differential converting rotation, which is the difference between the rotation transformation of the original animation path and the rotation transformation of the recovered trajectory animation. That is, assuming (,) refers to the key value of the node orientation interpolator, and (’,') indicates the key is restored in block 96 interpolation recovery (vectordenotes the axis of rotation,denotes the magnitude of the rotation, and that the magnitude of the rotation satises[,]), that converts rotation of the arbitrary positionandin 3D-space using (,and (’,’), the resulting quantization error is calculated as the difference betweenand. Thus, if

If Q and Q’ denote the quaternion expression for (,and (,') respectively, which represent the transformation of rotation, hence the following equation (5):

Here AndIn denotes the multiplication of quaternions a and b, and Adenotes the quaternion associated with A. Hence the following equation (6):

Here Q is the amount necessary to specify the relationship of the conversion of rotation betweenandand defined by the following equation (7):

Therefore, if’ indicates the differential angle between theandthencan be obtained by using equation convert quaternion and equation (7), as shown in the following equation (8):

(wherehereafter the surrounding in a predetermined time, on all points of discontinuity animation path. In order to derive an equation for obtaining a quantization error of all intervals of the animation, the instantaneous quantization error to a predetermined time t can be expressed as the following equation (9):

If equation (9) is applied through orientation interpolators for all intervals animation with points of discontinuity, it is possible to deduce the average error E_{cf}and the maximum error E_{max}for the entire interval [t_{0}, t_{L}] as the following equation (10):

Here it should be noted that for E_{cf}first get a partial amount of E^{i}_{cf}for the interval [t_{i-1}, t_{i}] using the following equation (11):

However, also deduce the following equation (12):

Hence deduce the following equation (13):

Since it is difficult to get a definite integral of a function^{2}(in the interval between 0 and 1, carry out the approximation shown in the following equations (14):

These equations can be rearranged in the form of the following equation (17):

To obtain the average error E_{cf}that sums up the partial sum of the E^{i}_{cf}over the entire time interval [t_{0}, t_{L}] as shown in the following equation (18):

To get the maximum error E_{max}choose the maximum value among the values of the maximum error E^{i}_{max}in each interval [t_{i-1}, t_{i}], which is obtained using the following equation (19):

Using the above function approximation, we can approximate E^{i}_{max}as shown in the following equation (20):

The maximum error E_{max}throughout the interval [t_{0}, t_{L}] expressed by the following equation (21):

Block 80 interpolation analysis, shown in Fig.6, 114 sends information about the number of keys, the minimum value and the maximum value of the normalized key values, the permission key and key values, as well as the p 82 keys and sends information about the key values includes a minimum value and a maximum value of normalized key values, the encoder 84 key values.

The following is an explanation of the coding of keys and key values in the encoder 82 keys and the encoder 84 key values. The keys and key values are compressed by the method of DECM-quantization in the encoder 82 keys and the encoder 84 key values, respectively. Quantized information together with other information is sent to the statistical encoder 86, and presented as a stream of bits subjected to final compression encoding through the output OUT3. For example, DICM-quantizer encoder 104 82 keys carries out encoding method DICM-quantization (i.e., encodes the difference between the current value and the immediate previous value) key sent from the block 80 interpolation analysis, and outputs the encoded result in the statistical encoder 86. At the same time, DICM-quantizer encoder 106 84 key values carries out encoding method DICM-quantization (i.e., encodes the difference between the current value and the immediate previous value) key values, minimum values and maximum values of key values sent from the block 80 interp the mA process of quantization and illustrated widely used method of DICM. Referring to Fig.10, note that in the case of key (k) final error (e) is subjected to compression by quantization, as shown by the following equation (22). Fig.10 explains equation (22). That is, get the difference (d1) between the immediate previous value (K_{i-1}) and its previous value (K_{i-2}). The value of the difference (d1) is added to the immediate previous value (K_{i-1}to generate the approximated values (K_{i}). Then get the final error (e) as the difference between the approximated value (K_{i}) and the current value (K_{i}). By the way, the error (e) can be easily obtained as the difference between the current value (K_{i}and the immediate previous value (k_{i-1}).

In Fig.11a - 11th presents diagrams showing the formats of encoded streams of bits according to the present invention. In Fig.11a shows the format of the coded bit stream according to the present invention, which includes a number of keys (colchica) authorization keys (RSRC), resolution of key values (rascs), array ([min/max]) 230 minimum values and maximum values of key values, array ([Metcalf achut array. In Fig.11b shows the format of the array 230 minimum values and maximum values of key values, Fig.11C shows the format of the array 232 of the labels of the keys of Fig.11d shows the format of the array 234 keys, and Fig. 11th shows the format of the array 236 key values.

Array 230 minimum values and maximum values of key values, shown in Fig.11a, is formed from the minimum values for axes X, Y and Z (min_{x}, min_{y}and min_{z}and maximum values for the axes X, Y and Z (max_{x}max_{y}and max_{z}). Array 232 of the labels of the keys formed of n labels key label_{0}Cluch, tag_{1}Cluch, tag_{2}Cluch, tag_{3}Cluch, ..., tag_{n-1}Kluch). Here n denotes the number of keys. Array 234 of keys formed of n keys (key_{0}key_{1}key_{2}key_{3}, ..., key_{n-1}). Here the data keys and the labels of the keys for break points, which are classified as optional, for example - break point T1, T3 and T6 from table 2, it can be deleted from an array of keys or array of the labels of the keys. Thus, an array of keys and/or an array of the labels of the keys may consist of data, the number of which is less than the number (n) of the original keys. Array 236 key values of SF is s (csnu_{0}, kznu_{1}, ..., kznu_{q-1}and r third key values (_Z_{0}, _Z_{1}, ..., _Z_{r-1}). Here pn, qn and rn.

Meanwhile, the device and method of restoring animation path according to the present invention are implemented as the inverse of the compression process. Statistical decoder 90, shown in Fig.7, receives the encoded bit stream through the input output VH, performs statistical decoding this bit-stream and outputs the result of decoding in the decoder 92 keys, and a decoder 94 key values. The decoder 92 keys and decoder 94 key values quantized take the keys and key values, respectively, which are the result of statistical decoding, and using additional information, such as a key label, restore data available prior to the quantization. That is, the decoder 92 keys takes the result of the statistical decoding and decoding keys, and the decoder 94 key values takes the result of the statistical decoder and decodes the key value. To do this, the decoder 92 keys can be made in the form of DECM-decanoate is al - 126 or 128 - decodes the input data decoded in the statistical decoder 90, the method DICM-dekvantovanie.

Block 96 interpolation recovery takes data decoded in the decoder 92 keys and the decoder 94 key values, and restores the original trajectory animation. Block 96 interpolation recovery 124 receives information about the number of keys, the minimum value and the maximum value of the normalized key values and flags of keys from the statistical decoder 90, the keys 120 of the decoder 92 keys and information 122 about the key values from the decoder 94 key values. Block 96 interpolation restores empty key values by linear interpolation, using the input information. For example, in table 2 the key value for the X-axis at the point T2 of the gap can be restored by linear interpolation, using the key values for the points t0 and T4. For this block 96 interpolation recovery can be made in the form of block 95 interpolation key recovery and key values. The recovered trajectory animation in the form of (key, key value) is output through the output VIH.

In Fig.12 submissions is retenu. This table is also called syntax streams of bits.

Referring to the accompanying drawings, note that the compression method animation path using a linear approximation according to the present invention will now be compared with the known method of interpolation compression using DFS in accordance with the algorithm MRE-4.

In Fig.13A - 13d shows the graphs of experimental animation sequences for comparison of the compression method according to the present invention with a known compression method. The vertical axis represents the degree of distortion, the horizontal axis represents the number of bits, the compression method according to the present invention shown with thick lines, and the well-known compression method shown by dashed lines. In Fig.13A - 13d show the results of simulations, each of which used different trajectory animation. The method according to the present invention shows significantly better results in the order of Fig.13b - 13A - 13d - 13C. At the same bit rate compression method according to the present invention showed a much better image quality than the known method using DFS, and at one and the same as ipiano above, interpolation expression animation path is used to simplify this trajectory using break points. However, in the known method, the interval between each key formed uniformly in terms of the trajectory, and therefore is redundant sampling (oversampling) break points. However, in the present invention is obtained simply encoded bit stream having a minimum number of break points. Compression method DICM (DICM compression supports higher linear correlation between break points, and therefore provides an efficient compression using this higher correlation.

Claims

1. Device for compressing animation path containing the unit of analysis interpolator for selecting a predetermined number of points of discontinuity of the animation path and issuance of keys and key values corresponding to the points of discontinuity, the encoder keys for encoding keys issued from the block analysis interpolator encoder key values for encoding key value provided by block analysis of the interpolator, and the statistical coder for statistical coding keys and glucoraphanin streams of bits.

2. The device under item 1, in which the unit of analysis interpolator determines the number of break points in such a way that minimizes the dierence between the approximated trajectory animation, which is obtained using a predefined number of break points allocated points to divide the original animation path and the original path of the animation.

3. The device under item 1, in which the encoder key codes for the keys that are output from the block analysis interpolator method of quantization by means of differential pulse code modulation (DICM-quantization).

4. The device under item 1, in which the encoder key values encodes key value provided by block analysis of the interpolator, the method DICM-quantization.

5. The device under item 1, which accept both end points of the original animation path for the starting point, the unit of analysis interpolator finds a break point break point representing the approximated trajectory animation, which has the smallest difference from the original animation path, and this process is repeated up until the approximated trajectory animation will not be close to the original trajectory.

6. The device under item 5, in which the break point is partly what ctoria animation is the smallest.

7. Device according to any one of p. 3 or 4, in which DICM-quantization represents the encoding of the difference between the current value and the immediate previous value, or represents a coding of the difference between the current value and the approximated value, which is obtained by adding the immediate previous value to the difference between the immediate previous value and its previous value.

8. Device for the recovery animation path containing statistical decoder for receiving the encoded bit stream and statistical decoding of the bit stream, the decoder key to accept the statistical decoding and the decoding key, the decoder key values for the reception of the statistical decoder for decoding key value, and the recovery block interpolator for receiving the key values by linear interpolation based on the keys and key values decoded in the decoder key and the decoder key values, respectively, and restore the original animation path.

9. The device under item 8, in which the decoder decodes keys the result of statistical zakodirovana coder key values decodes the result of the statistical decoding, which is introduced from the statistical decoder, the method DICM-dekvantovanie.

11. The way to restore animation path, including the stages at which admit and statistical decoding of the encoded bit-stream decode the keys and key values based on the statistical decoding, and restore the original path animation, getting key values by linear interpolation on the basis of the decoded keys and key values.

12. The compression method animation path, including the stages at which there are a predetermined number of points of discontinuity of the animation path, allocate the keys and key values using the selected break points and encode the keys and key values, and carry out statistical coding of the coded keys and key values to obtain the encoded streams of bits, the number of break points is adjusted so that the difference between the trajectory animation generated the selected break points and the original trajectory animation, is minimized.

13. The method according to p. 12, in which, additionally, are encoded in streams Biy among the key values, corresponding to the coordinate x, y or z each break point of the trajectory animation keys in an array to indicate that at least one or more key values selected among the key values corresponding to the coordinate x, y or z each break point, and the key values in an array selected for each break point.

14. The method according to p. 13, in which the format further comprises the minimum value of key values corresponding to the X, Y and Z coordinates, and maximum values of key values corresponding to the X, Y and Z coordinates.

15. The method according to p. 13, in which an array of labels includes M data, and M equals the number of source keys or less than this number.

16. The method according to p. 13, in which the array of keys includes M data, and M equals the number of source keys or less than this number.

17. The method according to p. 13, in which the key values include R (n) the first key values corresponding to the x-axis, q (n) of the second key values corresponding to the y-axis, and r (n) the third key values corresponding to the z-axis, n denotes a number of keys.

18. The method of allocation of points of discontinuity trajektorijoje animation points gap on the animation path, (b) choose one break point among the remaining break points, with the exception of two selected points of discontinuity (in) interpolate the key values of the remaining break points, excluding the selected break points, using the selected break points, (g) form of the approximated trajectory animation based on the selected break points and interpolated key values, choose the approximated trajectory animation, which has the smallest difference in trajectories between the original trajectory animation and this approximated trajectory animation, and choose break points corresponding to the selected animation path, and (d) choose one break point among the remaining break points, with the exception of break points selected in steps (a) and (b), and repeating steps (b)-(d) until such time as the difference of the trajectories will not be less than the allowable difference.

19. The method according to p. 18, in which the difference of the trajectories is expressed by the sum of the squares of trapezoidal or twisted trapezoidal, which formed the original trajectory animation and the approximated trajectory animation.

20. The method according to p. 18, in which the difference of the trajectories in orientation interpolator is defined as the differential angle is borota the original animation path and the rotation transformation of the approximated trajectory.

**Same patents:**

FIELD: physics, computing science.

SUBSTANCE: invention relates to coding, decoding and code transformation, and can be used for correction of digital bit stream read out from the drive's head of DVD. Technical result is simplification of device making stochastic correction of RLL (2,10) rule errors in the bit stream of DVD. The device contains sequential synchronous data shift register, register of shift's inhibit, control logic with error detection chains, set for detection of the errors of RLL (2,10) rule and with error correction chains, logic element AND.

EFFECT: simplification of device, which carries our probabilistic error correction of RLL (2,10) rule in the bit stream of DVD.

3 dwg, 7 tbl

FIELD: electric communication, namely systems for data transmitting by means of digital communication lines.

SUBSTANCE: method comprises steps of preliminarily, at reception and transmission forming R matrices of allowed vectors, each matrix has dimension m2 x m1 of unit and zero elements; then from unidimensional analog speech signal forming initial matrix of N x N elements; converting received matrix to digital one; forming rectangular matrices with dimensions N x m and m x N being digital representation of initial matrix from elements of lines of permitted vectors; transmitting elements of those rectangular matrices through digital communication circuit; correcting errors at transmission side on base of testing matching of element groups of received rectangular matrices to line elements of preliminarily formed matrices of permitted vectors; then performing inverse operations for decompacting speech messages. Method is especially suitable for telephone calls by means of digital communication systems at rate 6 - 16 k bit/s.

EFFECT: possibility for correcting errors occurred in transmitted digital trains by action of unstable parameters of communication systems and realizing telephone calls by means of low-speed digital communication lines.

5 cl, 20 dwg

FIELD: technology for encoding and decoding content, in particular, extracting data from buffer and loading them into buffer.

SUBSTANCE: method includes picking data from buffer in response to execution of data access command, while buffer contains multiple data storage devices, forming additional unified address space with bit level addressing. If picked data are contained in source data storage device and in next data storage device, fragment of picked data from source data storage device is concatenated with remaining fragment of picked data from next data storage device to form picked data as continuous block, picked data are stored in assignment device for storing data. Method for loading data into buffer includes storing data into buffer, while if data size exceeds capacity of device for storing data, data are split onto fragments and stored in source storage device and next device. After saving of aforementioned data, data from storage device are moved to memorizing device.

EFFECT: higher speed of loading and data extraction.

5 cl, 26 dwg

FIELD: technology for encoding multimedia objects.

SUBSTANCE: method for encoding a multimedia object includes following stages: multimedia object is encoded for producing a bit stream and information about quality is added to bit stream, while information about quality denotes quality of multimedia object relatively to given position or relatively to given part of bit stream, while information about quality is provided in quality tags, aforementioned quality tag provides a values of quality tag, and value of quality tag characterizes distortion in encoded multimedia object being reproduced, when bit stream is truncated in point, related to quality tag.

EFFECT: development of improved and efficient method/system for encoding multimedia objects.

13 cl, 2 dwg

FIELD: technology for encoding and decoding, used for storing and transferring descriptive elements of document of XML-like structure.

SUBSTANCE: method includes using at least one table, received from XML structure, while table contains identification information for unambiguous identification of each descriptive element on hierarchic tree and structural information, browsing of hierarchic image of sample stored in memory from parent descriptive element to children descriptive elements for reaching encoded descriptive element, and extraction of identification information of each browsed descriptive element, encoding of aforementioned descriptive element in form of fragment, containing aforementioned information content and series of extracted identification information.

EFFECT: provision of efficient sample encoding plan and possible expansion of binary format for further plans, determined within limits of MPEG-7.

7 cl, 6 dwg, 2 tbl

FIELD: radio engineering and television, possible use during generation, transmission and receipt of video-frames.

SUBSTANCE: in accordance to invention introduced additionally to encoder are video frames memory block, first function memory block, video frame transmission block, block for storing video frame being reproduced, while input of encoder serially, through block for forming video frames, video frames memory block, block for forming difference video frame, first frame memory block, video frame transmission block and block for memorizing video frame being reproduced is connected to second input of block for forming difference video frame, third input of which is connected to output of first function memory block, output of which is connected to second input of video frame transmission block, output of which is the output of device encoder. Introduced additionally to decoder are video frames receipt block, comparator and second function memory block, while input of decoder is serially, through video frame receipt block, second frame memory block and comparator, is connected to second video frame restoration block, third input of which is connected to output of second function memory device, and output is the output of decoder of device. Device realizes generation, transmission and receipt of code of function of distribution of screen point brightness in a series of frames, making it possible to increase the code compression coefficient.

EFFECT: increased coefficient of code compression of video frame information.

1 tbl, 1 dwg, 7 app

FIELD: technology for transmitting process data from field device to process control center.

SUBSTANCE: in accordance to the invention, process data contains information about working state of field device, and/or information about process variables measured by field device, and/or field device identification data. Process data appearing in time interval between two transmissions is evaluated, divided onto static and dynamic, data is recorded, transferred to process control center. Static data is transferred in abbreviated form, in form of a binary status value.

EFFECT: creation of method for transmitting reduced amount of process data.

2 cl, 2 dwg

FIELD: computer engineering, possible use for processing signals for serially incoming values.

SUBSTANCE: device contains means for generating first non-integer input value and second non-integer input value, where the first non-integer input value is composed of first source value and third source value by means of first elevation step and second elevation step and following weighing, second non-integer input value is formed by weighing the second source value; means for combining the first and second non-integer input values and for rounding off the non-integer resulting value.

EFFECT: reduced rounding error.

5 cl, 24 dwg

FIELD: physics.

SUBSTANCE: said utility invention relates to signal processing in the form of successive values, e.g., audio signal samples or video signal samples, which, in particular, are especially suitable for lossless coding applications. During processing of a signal containing a sequence of discrete values, having the first frequency band with high energy signal and the second frequency band with low energy signal, the sequence of discrete values is manipulated initially (202) to obtain a sequence of manipulated values so that at least one of the manipulated values would be different from an integer. After that, the sequence of manipulated values is rounded (204) to obtain a sequence of rounded manipulated values. Rounding is performed in order to create a generated rounding error spectrum so that the rounding error with the spectrum created would have higher energy in the first frequency band as compared to the second frequency band.

EFFECT: obtaining particularly efficient coding.

19 cl, 24 dwg

FIELD: information technology.

SUBSTANCE: method contains steps of processing information on the basis of mathematical transformations, divisions of the image into blocks of the image and coding of the current block, and the division of the image is carried out repeatedly on square blocks whose sizes are defined by a mass of initial data. For blocks which are not analysed before, an un-oriented graph is built, whose each top corresponds to one of such blocks, and each block consistently subject to affine transformations. Each transformed block is compared to all other blocks and if the degree of distortions of such a block at replacement of one of other blocks satisfies with it to the set restrictions on quality of the image between corresponding tops the column create an edge for reception the column, minimal covering which the set of tops answers an optimum base subset of blocks. The information is compared with that stored in memory of the block therefore leaving the information on the storage of the image corresponding to the minimal volume of data necessary for restoration of the image, then the procedure is repeated for the next size of the square block.

EFFECT: increase in the factor of compression of the image with minimal loss of quality at its restoration.

2 cl, 1 dwg

FIELD: physics; communication.

SUBSTANCE: present invention pertains to multimedia information transmission systems. The technical outcome is achieved by that, video image, for example, in a multimedia stream is scanned before compression so as to identify symbols, such as graphic characters and alphanumeric characters. The types, positions and sizes of the symbols are recorded for presenting symbolic information. The image is then compressed with or with out compressing the symbols, which can be removed from the image before compression if necessary. The compressed video and symbolic information is sent to a receiver, which decompresses the video, optionally converts the symbols and then inserts them where the symbolic information indicates.

EFFECT: increased efficiency of transmitting compressed multimedia information.

34 cl, 3 dwg