Method and device for coding and decoding key word value data of coordinate internal insertion symbol

TECHNICAL FIELD The present invention relates to an apparatus and method for encoding and decoding a composite image, and more particularly to a keyword for encoding and decoding a coordinate interpolator The value data device and method, wherein the coordinate interpolator uses the vertex coordinates including x, y, and z components in the graphic animation based on the key frame to represent the position of the object.

BACKGROUND Three-dimensional (3D) animation technology has been widely used in 3D computer games or virtual reality computer applications. Virtual Reality Modeling Language (VRML) is a typical example of this 3D animation technology.

International multimedia standards, such as the MPEG-4 binary format for scenes (BIFS) and virtual reality model language (VRML), use interpolator nodes to support 3D animation based on key frames. In MPEG4BIFS and VRML, there are various types of interpolators, including scalar interpolators, position interpolators, coordinate interpolators, directional interpolators, normal line interpolators, and color interpolators. The interpolators, these interpolators and their functions and characteristics are shown in Table 1.

<td>Interpolator</td><td>characteristic</td><td>Features</td>

<td>Scalar interpolator</td><td>Linear interpolation of scalar changes</td><td>Able to express area, diameter and strength</td>

<td>Position interpolation</td><td>Linear interpolation on 3D coordinates</td><td>Parallel movement in 3D space</td>

<td>Directional interpolation</td><td>Linear interpolation of 3D axis and rotation</td><td>Rotation in 3D space</td>

<td>Coordinate interpolation Α-Λ</td><td>Linear interpolation of changes in 3D coordinates</td><td>3D gradient</td>

<td>Normal interpolation</td><td>Linear interpolation of normal 3D coordinates</td><td>Ability to express changes in normal 3D vectors</td>

<td>Color interpolation</td><td>Linear interpolation of color information</td><td>Can express changes in color</td>

02140002.4 No.

<td>symbol</td><td></td><td>Transform</td>

Among the interpolators shown in Table 1, the coordinate interpolator is used to represent information on each vertex position of a 3D object constituting a key frame-based animation, and includes a keyword and a keyword value field. The key field uses discrete numbers between -8 and 8 to indicate the position of each key frame on the time axis. Each key value field specifies information on each vertex position that constitutes a 3D object at a certain instant represented by each key, and includes three components X, y, and ζ. Each key value field includes as many key values as the key fields. In this kind of key frame-based animation, a predetermined key frame is positioned at any position on the time axis, and the animation data between the key frames is filled by linear interpolation.

Because linear interpolation is used in MPEG-4 BIFS and VRML, a considerable amount of keyword data and keyword value data are required to use linear interpolators to make the animation as natural and smooth as possible. In addition, in order to store and transmit such a natural and smooth animation, a considerable amount of memory and a lot of time are required. Therefore, it is best to choose compressed interpolators to make it easier to store and send interpolators.

In predictive MF field coding (PMFC), one of the methods used to encode and decode interpolator nodes in MPEG-4 BIFS, a quantizer, a differential pulse code modulation (DPCM) operator, and a burnt encoder are used The key value data of the coded coordinate interpolator is shown in Figure 1. Taikoo Figure 1. The quantizer and DPCM operator eliminate the redundancy of the key value data, and the DPCM operator outputs the result of its operation to the bad encoder. However, PMFC is not sufficiently effective in encoding key value data, because it only encodes the difference data obtained from general DPCM operations, and only considers the spatial correlation between the vertices constituting the 3D object in the animation. Consider the temporal correlation between such vertices, which is very important in key frame-based animation.

SUMMARY OF THE INVENTION In order to solve the above and other problems, one aspect of the present invention provides a method and device for encoding key value data of coordinate interpolators, in which the temporal correlation between 3D object vertices in animation and the Spatial correlation.

Another aspect of the present invention provides a method and device for decoding key value data of an encoded coordinate interpolator, in which time correlation and spatial correlation between 3D object vertices in an animation are considered.

Another aspect of the present invention provides a bit data stream in which 3D objects in animation are considered

02140002.4 The temporal correlation and spatial correlation between the first vertices encode the key value data of the coordinate interpolator.

Another aspect of the present invention provides a method and apparatus for DPCM operation, which is used in the method and apparatus for encoding key value data of coordinate interpolators according to the present invention, and considers animation The temporal correlation between the vertices of the 3D object and the spatial correlation among them perform DPCM operations on the coordinate data of the 3D object.

Another aspect of the present invention provides a method and apparatus for inverse DPCM operation, which decodes differential data generated by the method and apparatus for DPCM operation according to the present invention.

Therefore, in order to realize the above and other aspects of the present invention, a device for encoding key value data of a coordinate interpolator is provided, wherein the coordinate interpolator uses the coordinate representation of each vertex including X, y, and z components. For the position of each vertex of the object, the device includes: a quantizer, which quantizes the coordinate interpolator input into it with a predetermined quantization bit, and a differential pulse code modulation processor, which quantifies each vertex of the quantized coordinate interpolator Each component performs a predetermined pattern of differential pulse code modulation operation, and thus generates differential data based on the time change of the coordinates of each vertex and differential data based on the spatial change of the coordinates of each vertex; a dictionary encoder, which generates The sign of the differential data of each component of a vertex, the mode of the differential pulse code modulation operation that has been performed on the differential data, and the position index indicating the position of the symbol; and the burnt encoder, which encodes the symbol and position index, where the differential pulse The code modulation processor includes: a differential pulse code modulation operator, which performs a time differential pulse code modulation operation on each component of each vertex of the quantized coordinate interpolator, so as to generate a vertex in a key frame and another key frame The first difference data between the vertices of the quantized coordinate interpolator; the spatial difference pulse code modulation operation is performed on each component of each vertex of the quantized coordinate interpolator, so as to generate the second difference data between the vertices in the same key frame; And perform space-time for each component of each vertex of the quantized coordinate interpolator Inter-differential pulse code modulation operation to generate the third differential data between the vertex and the key frame; a cyclic quantizer, which performs a cyclic quantization operation on the first to third differential data input from the differential pulse code modulation operator to Reduce its range; and a differential pulse code modulation mode selector, which selects one of the first to third differential data that has been cyclically quantized according to the number of bits required for encoding, and outputs the selected differential data, and a dictionary therein The encoder includes: a differential pulse code modulation mode encoder, which generates a symbol representing a combination of differential pulse code modulation modes that has been performed on the data of each component of each vertex and a position index representing the position of the symbol; and an appearance mode encoder, It generates a symbol of the input differential data corresponding to each component of each vertex and a position index indicating the position of the symbol.

In order to realize the above and other aspects of the present invention, a device for decoding a bit data stream is provided, wherein the coordinates of each vertex including X, y, and z components are used to represent the coordinates of each vertex of the object.

02140002.4 The key value data of the coordinate interpolator at the position is encoded. The device includes: a decoder, which generates data to be decoded by a dictionary by decoding the input bit data stream. The data includes the sign and representation of the difference data. The position index of the symbol position and the differential pulse code modulation operation mode; the dictionary decoder uses the data to be decoded by the dictionary to generate differential data; the inverse differential pulse code modulation processor restores the input from the dictionary decoder by following the differential pulse code modulation operation mode The difference data between the key frames and the difference data between the vertices are used to generate quantized data; and an inverse quantizer, which generates recovered key value data by inversely quantizing the quantized data, wherein the dictionary decoder includes: differential pulse code modulation A mode decoder, which decodes information about the mode of differential pulse code modulation operation that has been performed on each component of data of each vertex; and an appearance mode decoder, which is based on the sign and representation of the input differential data to be decoded by the dictionary The position index of the symbol position generates the differential data of each vertex, and the inverse differential pulse code modulation processor includes: the inverse time differential pulse code modulation operator, which pairs the vertices in the key frame and the vertices in another key frame The differential data between the vertices performs the inverse differential pulse code modulation operation; the anti-spatial differential pulse code modulation operator, which performs the inverse differential pulse code modulation operation on the differential data between the vertices in the same key frame and the corresponding reference vertices ; And the inverse differential pulse code modulation mode selector, It outputs the differential data to the inverse time differential pulse code modulation operator or the inverse space differential pulse code modulation operator according to the differential pulse code modulation operation mode.

The anti-DPCM processor used in the device for decoding the bit data stream preferably includes an anti-time DPCM operator, which performs an anti-DPCM operation on the differential data between a vertex in a key frame and a vertex in another key frame; An anti-spatial DPCM operator, which performs an anti-DPCM operation on the differential data between the vertex of the same key frame and its corresponding reference vertex; and an anti-DPCM mode selector, which outputs the differential data to the anti-time DPCM according to the DPCM operation mode Manipulator or anti-space DPCM manipulator.

In order to realize the above and other aspects of the present invention, there is provided a method for encoding key value data of a coordinate interpolator, wherein the coordinate interpolator uses the coordinates of each vertex including x, y, and z components to represent the object's The position of each vertex. The method includes the steps: (a) quantizing the key value data of the coordinate interpolator with a predetermined quantization bit; (b) performing a predetermined mode of differential pulse code modulation operation on each component of each vertex of the quantized coordinate interpolator , And thus generate difference data based on the time change of the coordinates of each vertex and difference data based on the spatial change of the coordinates of each vertex; (c) generate the sign and the paired difference data representing each component of each vertex The mode of the differential pulse code modulation operation performed by the differential data and the position index indicating the position of the symbol; and @) the encoding symbol and the position index, where step (b) includes: (bl) each of the quantized coordinate interpolators Each component of the vertex

02140002.4 The first time difference pulse code modulation operation is performed to generate the first difference data between a vertex in a key frame and a vertex in another key frame, and each component of each vertex of the quantized coordinate interpolator is performed The spatial differential pulse code modulation operation is used to generate the second differential data between the vertices in the same key frame, and the space-time differential pulse code modulation operation is performed on each component of each vertex of the quantized coordinate interpolator, In order to generate the third differential data between the vertex and the key frame; (b2) perform a cyclic quantization operation on the first to third differential data in order to reduce its range; and (b3) according to the number of bits required for encoding, Select one of the first to third differential data that has been cyclically quantized, and step (c) includes: (cl) generating a symbol sum representing the combination of differential pulse code modulation modes that has been performed on the data of each component of each vertex A position index representing the position of the symbol; and (c3) generating a symbol of the input differential data corresponding to each component of each vertex and a position index representing the position of the symbol.

In order to achieve the above and other aspects of the present invention, there is provided a method for generating difference data between quantized coordinate data of vertices constituting an object moving over time. The method includes: performing a time DPCM operation in which differential data between the coordinate data of each vertex that changes according to the passage of time is generated; performing a spatial DPCM operation in which each vertex at a predetermined time and a reference corresponding to the vertex are generated Difference data between vertices; and output the smaller value between the difference data of the time DPCM and the difference data of the space DPCM.

In order to realize the above and other aspects of the present invention, a method for decoding a bit data stream is provided. The coordinates of each vertex including the X, y, and ζ components in the bit data stream represent the coordinates of each vertex position of the object. The key value data of the interpolator is encoded. The method includes: (a) generating data to be decoded by a dictionary by decoding the input bit data stream, which includes the sign of the differential data, the position index indicating the position of the symbol, and the differential pulse code modulation operation mode; (b) the operation mode of the differential pulse code modulation; The symbol and position index of the differential data performs a dictionary decoding operation, and the data to be decoded by the dictionary is used to generate the differential data; (c) According to the differential pulse code modulation operation mode, quantized data is generated by restoring the differential data between the key frames and the differential data between the vertices; and (d) the restored key value is generated by inversely quantizing the quantized data Data, where step (b) includes: (bl) decoding information about the mode of differential pulse code modulation operation that has been performed on each vertex; and © 3) according to the sign of the differential data to be decoded by the dictionary and the position of the sign The position index of each vertex generates the differential data of each vertex, and in step (c), a predetermined inverse differential pulse code modulation operation is performed on the differential data according to the differential pulse code modulation working mode, and the inverse differential pulse code modulation operation includes: A time differential pulse code modulation operator, in which an inverse differential pulse code modulation operation is performed on the differential data between a vertex in a key frame and a vertex in another key frame to generate quantized data; and an inverse spatial differential pulse code Modulation operation, where the pairs are in the same key frame

02140002.4 The differential data between the middle vertex and its corresponding reference vertex performs an inverse differential pulse code modulation operation to generate quantized data.

In order to realize the above and other aspects of the present invention, a method is provided for generating vertex quantized coordinate data constituting an object that changes according to the passage of time by performing a predetermined inverse DPCM operation on difference data between coordinate data of vertices. The method includes: (a) selecting the inverse DPCM operation to be performed on the differential data based on the DPCM operation mode included in the differential data; and (b) performing the selected inverse DPCM operation. Among them, the selected anti-DPCM operation includes the anti-time DPCM operation, in which the inverse DPCM operation is performed on the differential data of each vertex that changes according to the passage of time; and the anti-spatial DPCM operation, in which each vertex at a predetermined moment and the corresponding The difference data between the reference vertices of the vertices performs the inverse DPCM operation.

02140002.4 Description of the Figures Through the following description in conjunction with the accompanying drawings that exemplarily show an example, the above and other objectives and features of the present invention will become clearer, in which: Figure 1 is used to encode coordinate interpolators A block diagram of a conventional device for key value data; FIG. 2A is a block diagram of a device for encoding key value data of a coordinate interpolator according to a preferred embodiment of the present invention, and FIG. 2B is a block diagram of a device according to a preferred embodiment of the present invention A flowchart of a method for encoding key value data of a coordinate interpolator; Fig. 3A is a block diagram of a DPCM processor according to a preferred embodiment of the present invention, and Fig. 3B is a block diagram of a dictionary encoder; Fig. 4A is a block diagram of a dictionary encoder according to the present invention Fig. 4B is a flowchart of DPCM operation, Fig. 4C is a flowchart of dictionary coding, and Fig. 4D is a flowchart of direct coding; Figs. 5A to 5C respectively illustrate the flow chart of DPCM operation according to the present invention. A schematic diagram of quantized key value data, DPCM key value data, and cyclically quantized key value data; FIG. 6A is a schematic diagram illustrating DPCM mode encoding according to a preferred embodiment of the present invention, and FIG. 6B is a schematic diagram illustrating emergence mode encoding , And Figure 6C is a schematic diagram illustrating incremental mode encoding; Figure 7A is a block diagram of an apparatus for decoding key value data of coordinate interpolators according to a preferred embodiment of the present invention, and Figure 7B is a preferred embodiment of the present invention. A flowchart of a method for decoding key value data of a coordinate interpolator of an embodiment; Fig. 8A is a block diagram of a dictionary decoder according to a preferred embodiment of the present invention, and Fig. 8E is a block diagram of an anti-DPCM processor; Fig. 9A is a flowchart of dictionary decoding according to a preferred embodiment of the present invention, and Fig. 9B is an anti-DPCM operation Figure 10 is a schematic diagram illustrating the bit data stream of the data of the vertices and the components of each vertex used in the coordinate interpolator; Figure 11A is a schematic diagram illustrating the decoding of the DPCM mode, and Figure 11B is the diagram illustrating the decoding of the emergence mode Figure 11C is a schematic diagram illustrating incremental mode decoding; Figures 12 to 18 are schematic diagrams illustrating examples of bit data stream syntax, in which bits are read from the bit data stream during the decoding process according to the preferred embodiment of the present invention. The order; Figure 19 is a schematic diagram illustrating an example of the program code, thereby implementing the operation for decoding the key value data;

02140002.4 Figures 20A and 20B are used to compare the performance of the method for encoding and decoding the key value data of the coordinate interpolator according to the present invention with the conventional method for encoding and decoding the key value data of the coordinate interpolator Figure 21A is a block diagram of a DPCM operator according to a preferred embodiment of the present invention, and Figure 21B is a block diagram of an anti-DPCM operator according to a preferred embodiment of the present invention.

DETAILED DESCRIPTION Hereinafter, an apparatus for encoding key value data of a coordinate interpolator according to a preferred embodiment of the present invention will be described in more detail with reference to the accompanying drawings.

2A is a block diagram of an apparatus for encoding key value data of a coordinate interpolator according to a preferred embodiment of the present invention, and FIG. 2B is a key for encoding a coordinate interpolator according to a preferred embodiment of the present invention Flow chart of the method of value data.

2A, the apparatus for encoding key value data of the coordinate interpolator includes a quantizer 300, which quantizes each component of each vertex of the key value data representing the coordinate interpolator with a predetermined quantization bit. ) Data, the DPCM processor 310, which performs a predetermined DPCM operation on the quantized data of each component of each vertex, the dictionary encoder 340, which converts the differential data into symbols and position indexes, and the burnt encoder 350, which Encode the sign and position index of the differential data input into it.

The method for encoding the key value data of the coordinate interpolator is described below with reference to FIG. 2B.

Referring to FIG. 2B, in step S400, the key value data of the coordinate interpolator is input to the quantizer 300 in the form of an N×M matrix. Examples of the key value data of the input coordinate interpolator are shown in the table below.

<td></td><td>1</td><td>2</td><td>··· j</td><td>M</td>

<td></td><td>x(l,l), y(l,l),z(l,l)</td><td>x(l,2), y(l,2),z(l,2)</td><td></td><td>x(l,M),y(l,M), z(l,M)</td>

<td></td><td>x(2,D, y(2,l),z(2,l)</td><td>x(2,2), y(2,2),z(2,2)</td><td></td><td>x(2,M),y(2,M), z(2,M)</td>

<td></td><td></td><td></td><td>x(i,j), y(i,j), z(ij)</td><td></td>

<td></td><td>x(N,l), y(N,l),</td><td>x(N,2), y(N,2),</td><td></td><td>x(N,M),y(N,M),</td>

02140002.4 No.

<td></td><td>z(N,l)</td><td>z(N,2)</td><td></td><td>ζ(Ν,Μ)</td>

In Table 2, N represents the number of key data (key frames), and M represents the number of vertices in each key frame.

The apparatus for encoding the key value data of the coordinate interpolator according to the present invention operates in two different modes to encode the key value data of the coordinate interpolator. One of the modes is the vertex mode, and the other mode is the transpose mode. Table 2 shows the structure of the key value data to be quantized in the quantizer 300 in the vertex mode. Before quantizing the input key value data shown in Table 2, the apparatus for encoding the key value data of the coordinate interpolator according to the present invention transposes the input key value data into an M Η Ν matrix. In the process of decoding the key value data, the transposed matrix is inversely quantized, and the decoded key value data is converted into a NH matrix, so that the same key value data as the input key value data can be restored.

2B, in step S410, the quantizer 300 checks whether the encoding mode of the key value data input from the outside is the transposition mode. If the encoding mode of the input key value data is the transposition mode, the ΝΗΜ matrix of the input critical value data is transposed into the ΜΗΝ matrix in step S420.

Thereafter, the quantizer 300 quantizes the data of each component in the key value data matrix input thereto with a predetermined quantization bit, and outputs the quantized key value data of each component to the DPCM processor 310 in step S430. In the same step, the quantizer 30 converts the minimum value among the input key value data of each component and the maximum range among the data range of the component into a decimal number, and outputs the decimal number to the key value. Header encoder 370.

In step S440, the DPCM processor 310 performs a time DPCM operation, a space DPCM operation, and a space-time DPCM operation on the quantized key value data input therein, and the results of the three different DPCM operations, that is, from the three DPCM operations. Each difference data obtained by the operation performs a cyclic quantization operation, and the difference data having the lowest value among them is output to the dictionary encoder 340.

The dictionary encoder 340 generates and outputs the dictionary symbol Si corresponding to the differential data input from the DPCM processor 310 and the position index 1$. Specifically, the dictionary encoder 340 generates a pattern indicating that the DPCM operation has been performed on the input differential data. Convert the input differential data into a symbol or symbol mark corresponding to the value of the input differential data, and a position index indicating the position of the symbol, and output the symbol and position index to the encoder 350.

02140002.4 First, in step S480, the direct encoder 350 generates a bit data stream by encoding the symbols and position indexes input from the dictionary encoder 340.

Subsequently, steps S400 to S480 are described in more detail with reference to FIGS. 3A to 6C. Referring to FIG. 4A, in step S432, the quantizer 300 selects the maximum value and the minimum value among each component data.

The quantizer 300 calculates the data range of the component using the maximum and minimum values selected in step S432, and determines the maximum range among the data ranges of the component in step S434.

The quantizer 300 uses the minimum value among the data of each component and the maximum range among all the data ranges of the components to quantize the key value data of each component, which is shown in the following equation.

Zhang^=βοΟΓ^~β^~^Χ Dish-1)+ °·⁵)…⑴

Kj,=add(Yi xuU(2^W -1)+05) ~ dagger j '-fMin Z

V," = ask( plate_(2^m -1)+05) In the equation (1), i represents the key data, j represents the vertex, and nKVQBit represents the quantization bit size. In addition, fMin_X, fMin_Y, fMin_Z represent the minimum value in the data of each component, and fMax represents the maximum range in the component data range.

The quantizer 300 outputs the quantized key value data of each component to the DPCM processor 310, converts fMin_X, fMin_Y, fMin_Z, and fMax into decimal numbers, and outputs the decimal numbers to the key value header encoder 370.

The computer stores floating-point numbers as 32-bit binary numbers. In order to reduce the number of bits required for encoding, the quantizer 300 sets fMin_X, fMin_Y in the decimal system₀ fMin_Z and fMax are converted into their respective mantissas and exponents, and this process is represented by the following equation.

mantissa-binary * 2 Qin ° cut less, 5 = mantissa *10^expo,,OT,. ---(2) , "Pie ^V.....^.........^..... V ^J the floatmg-point number in hinaty system ^lfte floating-point number in decimal system For example, the floating-point number 12.34 can be converted into the binary number shown below by a computer.

10001010111000010100011 10000010

Ϊ 2 3

A-Α- σ ι: Fu Qiao·

02140002.4 No.

2: Mantissa in binary

3: The exponential binary number in the binary system can be converted into the decimal number shown later following equation (2).

1234 2

1: Symbol

2: Mantissa in decimal

3: Exponent in decimal system In order to include the mantissa and exponent in decimal system in the bit data stream, the quantizer 300 must calculate the number of bits required to express the mantissa and exponent. An exponent having a value between -38 and 38 can therefore be represented using 7 bits together with the sign. The number of bits required to represent the mantissa depends on the number of bits. The value of the mantissa and the number of bits required to represent the mantissa are listed in the following table. table 3

<td>Mantissa value</td><td>The number of digits in the mantissa</td><td>Number of bits required</td>

<td>0</td><td>0</td><td>0</td>

<td>1-9</td><td>1</td><td>4</td>

<td>10-99</td><td>2</td><td>7</td>

<td>100-999</td><td>3</td><td>10</td>

<td>1000-9999</td><td>4</td><td>14</td>

<td>10000-99999</td><td>5</td><td>17</td>

<td>100000-999999</td><td>6</td><td>20</td>

<td>1000000-9999999</td><td>7</td><td>24</td>

The quantizer 300 outputs the minimum values fMin_X, fMin_Y, and fMin_Z in the data of each component and the maximum range fMax in the data range of the components, which have been converted in accordance with equation (2) and Table 3, to the key value header encoder 370 .

The DPCM processor and DPCM operation according to the present invention will be described below with reference to FIGS. 3A and 4B.

FIG. 3A is a block diagram of the DPCM processor 310 according to the present invention. 3A, the DPCM processor 310 includes a DPCM operator 320, which performs temporal DPCM operations, spatial DPCM operations, and space-time DPCM operations on the data of each component input from the quantizer 300, and a cyclic quantizer 330, which reduces the The range of the differential data input by the DPCM operator 320, and the DPCM mode selector

02140002.4 No.

335, which selects one of the differential data input from the cyclic quantizer 330. The DPCM operator 320 includes a time DPCM operator 321, which performs a time DPCM operation on the quantized data of each component, a spatial DPCM operator 323, which performs a spatial DPCM operation on the quantized data of each component, and a space-time DPCM operator 325. Perform a space-time DPCM operation on the quantized data of each component.

Fig. 4B is a flowchart of DPCM operation according to a preferred embodiment of the present invention. 4B, in step S442, the quantized data of each component is input from the quantizer 300 to the time DPCM operator 321, the space DPCM operator 323, and the space-time DPCM operator 325, and then the respective operators 321, 323 and 325 perform time DPCM operation, space DPCM operation, and space-time DPCM operation on the quantized data of each component.

The temporal DPCM operator 321 calculates the difference between the component data of the vertex in the current key frame and the component data of the vertex in the previous key frame. The time DPCM operation is represented by the following equation: long = B-B, p... (3) In equation (3), i represents key data, and j represents the position index of the vertex.

The spatial DPCM operator 323 calculates the difference between the vertices in the same key frame. Specifically, the spatial DPCM operator 323 uses the following equation to calculate the direct value of the previous vertex, and the spatial DPCM operation has been performed on the previous vertex before the current vertex is subjected to the spatial DPCM operation.

N-1

Entropy(P)=Liaoer log₂ ---(4) i=o In equation (4), Pi represents the probability of a symbol being generated at the vertex, and is equal to Fi/N, where Fj represents how many times the symbol is generated, and N represents the number of keyword data.

The spatial DPCM operator 323 determines the vertex with the lowest direct among the vertices as the reference vertex, and calculates the difference data between the data of the vertex currently subjected to the spatial DPCM operation and the data of the reference vertex. The space operation is represented by the following equation.

"...(5) The space-time DPCM operator 325 performs a spatial DPCM operation on the vertices of the current key frame, and uses the vertices in the previous key frame as reference vertices to perform the spatial DPCM operation on the vertices of the previous key frame, Where it corresponds to the reference vertex of the current key frame, and calculates the difference data between the difference data corresponding to the vertices of the current key frame and the difference data corresponding to the vertices of the previous key frame. In other words, space-time DPCM The result of the spatial DPCM operation by the operator 325

02140002.4 DPCM operation at the first execution time. The space-time DPCM operation is represented by the following equation.

Long=B-{YiP+(%/-Buse/)}...(6) In the process of space DPCM operation and space-time DPCM operation, if or recall one ⁺ (Z.Re/-Zl.Re/)} is less than the minimum value in the quantized data of each component, the minimum value is used for the space DPCM operation and the space-time DPCM operation. On the other hand, if «Re/ or {B,+ (E,Re/ ~B,Re/)} is greater than the maximum value in the quantized data of each component, the maximum value is used for spatial DPCM operations and spatial -Time DPCM operation.

In step S444, the DPCM operator 320 outputs the calculated difference data to the cyclic quantizer 330, and the cyclic quantizer 330 performs a cyclic quantization operation on the time DPCM difference data, the space DPCM difference data, and the space-time DPCM difference data, and The result of the cyclic quantization is output to the DPCM mode selector 335.

FIG. 5A is a graph of an output example of the quantizer 300, and FIG. 5B is a graph of the result of performing a DPCM operation on the quantized data shown in FIG. 5A. As shown in FIG. 5B, by performing the DPCM operation on the quantized data, the range of the data to be encoded can be increased twice the range of the original data. The purpose of cyclic quantization is to perform DPCM operations while maintaining the data range of the quantized value.

In the present invention, it is assumed that the maximum value in the differential data of DPCM is cyclically connected to the minimum value in the differential data of DPCM to perform cyclic quantization. If the result of the linear DPCM operation performed on two consecutive quantized data is greater than half of the maximum value in the DPCM differential data output from the DPCM operator 320, the DPCM output from the DPCM operator 320 is subtracted from the result of the linear DPCM The maximum range value of the difference data in order to produce a value with a smaller absolute value. On the other hand, if the result of linear DPCM is less than half of the minimum value in the maximum range, the maximum range value is added to the result of linear DPCM so as to produce a value with a smaller absolute value.

The operation of the cyclic quantizer 330 is expressed by the following equation.

CircularQuanti zation{X_t)\ ··(7)

-(nQMax-nQMin + 1) (ζ/' X,&gt; 0)

X\ = X_i + (nQMax- nQMin + 1) {otherwise)

X = min (ratio|,||) In equation (7), nQMax represents the maximum value in the differential data of DPCM, and nQMin represents the minimum value in the differential data of DPCM. FIG. 5C shows the result of performing cyclic quantization on the difference data of DPCM shown in FIG. 5B.

The cyclic quantizer 330 outputs the cyclically quantized difference data to the DPCM mode selector 335.

02140002.4 In step S446, the DPCM mode selector 335 calculates the quotient of each DPCM difference data obtained from the time DPCM operation, the space DPCM operation, and the space-time DPCM operation following the equation (4).

After that, the DPCM mode selector 335 in step S448 selects the DPCM difference data with the lowest value among the results of the time DPCM operation, the space DPCM operation, and the space-time DPCM operation as the DPCM operation mode of each vertex, and sets the corresponding DPCM operation mode. The DPCM differential data for the selected DPCM mode and the information about the DPCM mode are output to the dictionary encoder 340.

Subsequently, the dictionary encoder 340 and its operation are described with reference to FIGS. 3B and 4C.

FIG. 3B is a block diagram of the dictionary encoder 340 according to the present invention. Referring to FIG. 3B, the dictionary encoder 340 includes a DPCM mode encoder 342, which encodes the DPCM mode that has been performed on the data of each component of each vertex input therein, and a mode encoder 346 appears, which generates a representation of each vertex The sign of the value of the difference data of each component and the position index indicating the position of the symbol, the incremental mode encoder 348, which generates the symbol flag corresponding to the symbol and the position index indicating the position of the symbol, and the table size calculator 344, which Calculate the size of the symbol table and the symbol flag table representing the difference data of each component of each vertex, and output the difference data input from the DPCM mode encoder 342 to the appearance mode encoder 346 or the incremental mode encoder 348 .

The dictionary encoder 340 detects whether the quantization selection flag of the difference data of each component of each vertex is 1, and if it is, performs subsequent processing that will be described below. On the other hand, if the quantization selection flag of the differential data of a certain vertex is 0, which means that all the key frames of the vertex have the same quantization value, the dictionary encoder 340 will omit the dictionary encoding process and encode the quantized value Qmin as the key The word value title.

Fig. 4C is a flowchart of dictionary encoding processing according to the present invention. Referring to FIG. 4C, in step S462, the differential data of each component of each vertex that has been generated in the DPCM processor 310 is input to the DPCM mode encoder 342, and then the DPCM mode encoder 342 generates the The symbol of the DPCM operation mode performed by the data of each component of the vertex, and the position index indicating the position of the symbol.

FIG. 6A is a schematic diagram illustrating the method of encoding the DPCM mode performed in the encoder 342 according to the DPCM mode of the present invention. Referring to FIG. 6A, the DPCM mode encoder 342 prepares a table in advance, which shows the DPCM mode of each component of each vertex and its respective symbols, as shown in Diagram 4. Table 4 shows the combination of DPCM operations and their corresponding symbols. In Table 4, the time DPCM operation, the space DPCM operation, and the space-time DPCM operation are denoted as T, S, and T+S, respectively.

02140002.4 Table 4

<td>symbol</td><td>DPCM mode</td><td>Pay wan</td><td>DPCM mode</td><td>Pay Τ</td><td>DPCM mode</td>

<td>0</td><td>(Τ, T, T)</td><td>9</td><td>(S, T, T)</td><td>18</td><td>(T+S, T, T)</td>

<td>1</td><td>(Τ, T, S)</td><td>10</td><td>(S, T, S)</td><td>19</td><td>(T+S, T, S)</td>

<td>2</td><td>(T, T, T+S)</td><td>11</td><td>(S, T, T+S)</td><td>20</td><td>(T+S, T, T+S)</td>

<td>3</td><td>(T, S, T)</td><td>12</td><td>(S, S, T)</td><td>21</td><td>(T+S, S, T)</td>

<td>4</td><td>(T, S, S)</td><td>13</td><td>(S, S, S)</td><td>22</td><td>(T+s, S, S)</td>

<td>5</td><td>(T, S, T+S)</td><td>14</td><td>(S, S, T+S)</td><td>23</td><td>(T+S, S, T+S)</td>

<td>6</td><td>(T, T+S, T)</td><td>15</td><td>(S, T+S, T)</td><td>24</td><td>(T+S, T+S, T)</td>

<td>7</td><td>(T, T+S, S)</td><td>16</td><td>(S, T+S, S)</td><td>25</td><td>(T+S, T+S, S)</td>

<td>8</td><td>(T, T+S, T+S)</td><td>17</td><td>(S, T+S, T+S)</td><td>26</td><td>(T+S, T+S, T+S)</td>

Each vertex includes three components X, y, and Z, and the number of combinations of corresponding DPCM operations is 27.

As shown in FIG. 6A, according to the DPCM operation through which the differential data has passed, the differential data of each vertex corresponds to one of the symbols shown in Table 4. The DPCM mode encoder 342 makes the DPCM modes of the vertices correspond to their respective symbols shown in Table 4, and sets a flag indicating that the symbols are present in the respective vertex difference data.

The DPCM mode encoder 342 arranges the symbols of the DPCM mode corresponding to the vertices in a column, and generates the signals in the order from the position index for the symbol with the smaller amplitude to the position index for the symbol with the largest amplitude. Index to the position of the symbol.

As shown in FIG. 6A, the array of symbols of the DPCM mode corresponding to the vertex difference data is (4, 1, 5, 1, 4, 5). Among the symbols, 1 is the smallest symbol and corresponds to (T, T, S). The DPCM mode encoder 342 generates a position index for the symbol 1, so that the bit where a 1 appears in the array of the symbol is directly represented by 1. Therefore, the position index is (0, 1, 0, 1, 0, 0).

Subsequently, the DPCM mode encoder 342 generates a position index for the next smallest symbol 4, which corresponds to the DPCM mode (T, S, S), so that the position of 4 is represented by 1. In the generation of the position index for symbol 4, the position of symbol 1 is not calculated. Therefore, the position index for symbol 4 is (1, 0, 1, 0). In the same way, the DPCM mode encoder 342 generates a position index for symbol 5, which corresponds to (T, S, T+S). The position index for symbol 5 is (1, 1).

Subsequently, the DPCM mode encoder 342 outputs the mark and position index to the table size calculator

02140002.4 No.

344。

Referring again to FIGS. 3B and 4C, the table size calculator 344 calculates the size (A) of the symbol table used to encode the input differential data in the appearance mode, and the symbol used to encode the input differential data in the incremental mode. The mark is very small (B), which corresponds to the symbol in the symbol table set in advance in step S464.

In step S446, the table size calculator 344 calculates the size of the symbol table used in the appearance mode encoder 346 A=S*(AQP+1) (where S represents the number of symbols included in the differential data and AQP represents The size of the bit representing the symbol) and the size of the symbol mark corresponding to the respective symbol B = 2^aqp+11 (AQP represents the size of the bit used to represent the symbol) compare.

If A is less than B, the table size calculator 344 outputs the differential data of each vertex to the appearance mode encoder 346, and if B is less than A, it outputs the differential data to the incremental mode encoder 348.

The operation of the appearance mode encoder 346 will be described below with reference to FIG. 6B.

In step S468, the appearance mode encoder 346 generates a sign corresponding to the value of the input difference data of each vertex, and a position index indicating the position of its respective sign.

Referring to Figure 6B, when the input differential data of the vertex is (3, 7, 3, 7, -4, 7, 3, -4, 3, 7, -4, -4), the mode code appears in step S468 The processor 346 prepares a table in which the symbols 3, 7, and -4 of the difference value of the difference data corresponding to each vertex are sequentially written in one row.

The appearance mode encoder 346 encodes the first symbol 3 in the symbol array and generates a position index for the symbol 3 so that 3 is located and the position is represented by 1 and the other positions are represented by 0. The position index for symbol 3 is (0 1 000 1 0 1 000)_o Subsequently, the appearance mode encoder 346 generates a position index for the lower symbol 7. As shown in FIG. 6B, in the process of generating the position index for the lower symbol, the position of the previous symbol is not calculated again. Therefore, the position index for symbol 7 is (1010100)» In the appearance mode encoder 346, only the symbol positions that have not been encoded are considered to generate all the position indexes for the symbol, so the position index for the symbol-4 is (1 1 l)o In Figure 6B, the flag bSoleKV is set to 0. The flag bSoleKV indicates whether the symbol appears only once in the symbol array of the differential data. If the symbol appears only once and therefore its position index only includes 0, the bSoleBK for the corresponding symbol is set to 1, and the position index of the corresponding symbol is not encoded. The appearance mode encoder 346 outputs the sign of the input differential data, the position index of the sign, and bSoleKV to the direct encoder 350 for encoding the differential data.

The operation of the incremental mode encoder 348 according to the present invention will be described later with reference to FIG. 6C.

02140002.4 In step S469, the incremental mode encoder 348 generates a symbol flag indicating whether the symbol included in the predetermined symbol table is present in the input differential data and a position index for the symbol.

The incremental mode encoder 348 generates a table for symbols expected to be present in the input differential data in advance. In the table, the symbols are arranged in columns in the order from the symbol with the lowest absolute value to the symbol with the largest absolute value, and between two symbols with the same absolute value, the symbol with a positive value is placed in In a row higher than another symbol. Therefore, the order in which the symbols are written in the table is 0, 1, -1,2, -2, 3, -3, . ...The size of the symbol flag corresponding to the symbols in the symbol table is 2^AQP+1-1_OFor example, if AQP is 2, the number of symbols that can be represented by the symbol flag is 7. If the value corresponding to the sign exists in the differential data, the sign flag is set to 1. The position index is generated only for the symbol whose symbol flag is set to 1.

Referring to Figure 6C, if the differential data input to the incremental mode encoder 348 is (-1, -3, -1, 3, 2, -3, -1, 2, -1, -3, 2, 2), Then the symbol existing in the differential data is (-1, 2, -3), and therefore the symbol flag is determined to be (0, 0, 1, 1, 0, 0, 1).

The incremental mode encoder 348 generates a position index for the symbol, where the symbol is positioned in a higher row than the other symbols in the symbol table. As shown in FIG. 6C, the incremental mode encoder 348 sets the position of the symbol, which ranks the highest among the symbols existing in the differential data in the symbol table, and sets other positions with 0, so that the symbol -1 The position index is (1 0 1 000 1 0 1 000). Subsequently, the incremental mode encoder 348 generates a position index for symbol 2 (0 0 10 10 11) regardless of the already encoded position of symbol -1. Finally, the incremental mode encoder 348 generates a position index (1 1 1 1) for symbol 3 regardless of the positions of symbol-1 and symbol 2 that have been encoded. The incremental mode encoder 348 outputs the symbol flag and position index for its respective symbol to the bad encoder 350.

All the position indexes generated by the appearance mode encoder 346 and the incremental mode encoder 348 have a flag called nTrueOne, which indicates whether the original position index has been reversed. Specifically, if nTrueOne is set to 0, the position index is considered to be obtained by reversing its original position index. In the case where the position index includes many 1s, it is possible to enhance the coding efficiency of the algorithm by inverting the position index so as to increase the number of 0s.

The operation of the primary encoder 350 will be described later with reference to FIG. 4.

The bad encoder 350* quotient according to the present invention encodes the symbol sign representing the symbol of the differential data input from the incremental mode encoder 348 and the position index for the symbol, and uses the function enodeS ignedQuasi AAC() to encode from the emergence mode encoder 346 The sign of the input differential data and its respective position index.

02140002.4 No. In encodedSignedQuasiAAC, the content related to the input value and its symbol is used to generate an adaptive algorithm-encoded bit data stream. Specifically, in encodeSignedQuasiAAC(), the first bit that is not 0 is encoded, then its sign is encoded, and the other bits are encoded with zero content.

Fig. 4D is a flowchart of the process of encoding symbols using encodeSignedQuasiAAC().

In step S481, the primary encoder 350 receives the symbol nValue of the differential data to be encoded and its bit size QBito. In step S482, the primary encoder 350 subtracts 2 from nQBit, and stores the result of the subtraction as one that can be crossed.

In step S483, the primary encoder 350 stores the absolute value of the symbol nValue as a variable val, and performs a right shift (SR) operation for val with a number of i. The encoder 350 performs a logical AND operation on the result of the 1 and SR operation, and stores the result of the logical AND operation as a variable bit.

In the first cycle of the process of encoding symbols using encodedSignedQuasiAAC(), the first bit in the input value to be encoded except for the sign bit is detected, and the other bits are read out one by one in the subsequent cycle.

In step S484, the bad encoder 350 detects whether val is greater than 1. If val is greater than 1, use the function qf_encode() to encode the value of bit under zero context in step S485. On the other hand, if val is not greater than 1, the function qLencode() is used to encode the value of bit in the i-th context in step S486.

When val is not greater than 1, the bad encoder 350 checks whether val is 1 again in step S487 . If val is 1, the sign of nValue is set in step S488, and nValue is encoded according to its sign and symbol context in step S489. When the encoding process for one bit is completed, the first encoder 350 sets the value of nValue in step S490. Then, in step S491, it is detected whether the current value of i is less than 0. By repeatedly executing S483 to S490, the encoder 350 will encode the input value until i is less than 0.

Therefore, according to the context assigned to the first bit, the first encoder 350 encodes the first bit whose input value is not 0, and encodes the other bits according to the zero context.

The information to be encoded into the keyword value header in the keyword value header encoder 370 will be described later with reference to FIG. 2A.

The key value header encoder 370 receives the input coordinate coordination program and encodes the data pattern, the number of vertices in each key frame, the number of bits required for the number of vertices, and the maximum number of significant bits per floating point number .

02140002.4 The first key value header encoder 370 encodes the number of quantized bits, the minimum value in the key value data of each component of each vertex, the maximum data range in the data range of each component of each vertex, and each The maximum and minimum values in the quantized data of each component of the vertex.

The key value header encoder 370 receives from the DPCM processor 310 the mode of the DPCM operation that has been performed on the data of each component, the dictionary encoding mode from the dictionary encoder 340, and encodes the DPCM operation mode and Dictionary encoding method.

Subsequently, an apparatus and method for decoding coded coordinate interpolators according to the present invention will be described with reference to FIGS. 7A and 7B.

Fig. 7A is a block diagram of an apparatus for decoding coded coordinate interpolators according to a preferred embodiment of the present invention, and Fig. 7B is a flowchart of a method for decoding coded coordinate interpolators according to a preferred embodiment of the present invention.

Referring to FIG. 7A, the apparatus for decoding encoded coordinate interpolators according to the present invention includes a decoder 800, which decodes the input bit data stream and thus generates data to be decoded by the dictionary, wherein the data includes DPCM differential data Symbol, symbol mark, position index for the symbol, and DPCM operation mode; dictionary decoder 810 generates differential data according to the symbol of the data to be dictionary-encoded and its position index; inverse DPCM processor 830, according to the DPCM operation mode The differential data performs a predetermined inverse DPCM operation to generate quantized data; the inverse quantizer 850 generates recovered key value data by inversely quantizing the quantized data; and the key value header decoder 870 decodes the input bit data stream for The information required for decoding the coordinate interpolator is output to the dictionary decoder 810, the inverse DPCM processor 830, and the inverse quantizer 850.

The following describes the method for decoding the encoded coordinate interpolator according to the present invention with reference to FIG. 7B.

In step S910, the bit data stream in which the coordinate interpolator is encoded is input to the primary decoder 800, and then in step S920, the burnt decoder 800 decodes the input bit data stream. If the input bit data stream has been encoded in the appearance mode, the direct decoder 800 outputs the symbol of each vertex and its position index to the dictionary decoder 810. On the other hand, if the input bit data stream has been encoded in the incremental mode, the burnt decoder 800 outputs the symbol flag indicating the existence of the symbol and the position index for the symbol to the dictionary decoder 810.

In step S930, according to the input dictionary encoding mode, the dictionary decoder 810 decodes the symbol and position index input from the original decoder 800 in the appearance mode or decodes the symbol flag and position input from the original decoder 800 in the incremental mode. The differential data is generated by indexing, and the generated differential data is output to the inverse DPCM processor 830.

02140002.4 According to the decoded DPCMX operation mode of the input differential data, the anti-DPCM processor 830 performs inverse-time DPCM operation, anti-space DPCM operation, and anti-space-time DPCM operation on the differential data input from the dictionary decoder 810 in step S940 One of them generates quantized key value data, and outputs the quantized key value data to the dequantizer 850.

In step S950, the dequantizer 850 dequantizes the quantized key value data input from the inverse DPCM processor 830 using the minimum value and the maximum data range of the data of each component input from the key value header decoder 870 .

In step S960, the dequantizer 850 checks whether the dequantized key value data matrix has been converted into a transposed matrix during the encoding process, and if the matrix of dequantized key value data has been transposed, then in step S965 Transpose the matrix in reverse.

In step S970, the dequantizer 850 outputs the key value data of the restored coordinate interpolator.

Subsequently, the apparatus and method for decoding the encoded coordinate interpolator will be described in more detail with reference to FIGS. 8A to 9B.

The primary decoder 800 first decodes the bit data stream representing the DPCM mode from the input bit data stream, and then decodes the array including bSelFlag, nKVACodingBit, nQMin, and nQMax.

In the encoding process, first set bSelFlag and nKVACodingBit to 1 and 0 respectively. If bSelFlag is decoded to 1, the primary decoder 800 decodes nKVACodingBit, nQMin, and nQMaXo. On the other hand, if bSelFlag is decoded to 0, the primary decoder 800 only decodes nQMin_o After decoding the array of data bSelFlag, nKVACodingBit, nQMin, and nQMax, the bad decoder 800 decodes the nDicModeSelect which represents the dictionary encoding mode. According to the value of nDicModeSelect, the bit data stream to be decoded is divided into two different types as described below.

FIG. 10 is a schematic diagram illustrating the structure of each vertex of the coordinate interpolator and the bit data stream of the component data of each vertex. As shown in Figure 10, if nDicModeSelect is 0, the bit data stream includes symbols and position indexes that have been encoded in the presence mode encoder. On the other hand, if nDicModeSelect is 1, the bit data stream includes the symbol flag and position index that have been encoded in the incremental mode encoder.

The direct decoder according to the present invention described above uses the function decodeSignedQuasiAAC() implemented in the program code shown in FIG. 19_o In the function encodeSignedQuasiAA(), an adaptive algorithm-encoded bit data stream is decoded using the context related to the input value and its symbol. Specifically, in the function decodeSignedQuasiAAC(), the bit after the sign bit is decoded using zero context. The burnt decoder 800 outputs the decoded data to the dictionary decoder 810.

02140002.4 Fig. 8A is a block diagram of the dictionary decoder 810 according to the present invention, and Fig. 9A is a flowchart of dictionary encoding.

As shown in FIG. 8A, the dictionary decoder 810 includes a DPCM mode decoder 812, which restores the DPCM mode of each vertex input therein; a dictionary mode selector 814, which selects the dictionary decoding mode of each vertex input; The device 816 receives the symbol of each component of each vertex and the position index for the symbol from the dictionary mode selector 814, and restores the difference data; and the incremental mode decoder 818, which receives the symbol flag and the position index from the dictionary mode selector 814 It is used to index the position of the symbol and restore the differential data.

Referring to FIG. 9A, in step S931, the sub-decoded component data of each vertex including the symbol, the symbol flag, and the position index is input to the DPCM mode decoder 812.

Before the dictionary-decoded differential data is output to the inverse DPCM processor 830, in step S932, the DPCM mode decoder 812 decodes the inverse DPCM operation mode, where the inverse DPCM operation is performed on each vertex in the inverse DPCM processor 830 The operation performed by the difference data of each component.

The DPCM mode decoding will be described later with reference to FIG. 11A.

Except that the number of symbols representing the combination of the DPCM mode of each component of each vertex is fixed at 27, so the size of the symbol table is also fixed at 27, DPCM mode decoding is the same as the incremental mode decoding that will be described later .

The DPCM mode decoder 812 receives the DPCM mode flag and records the symbols corresponding to the DPCM mode flag in the array according to the input position index.

For example, as shown in FIG. 11A, the symbols corresponding to the input DMCM mode flag are 1 (TTS), 4 (TSS), and 5 (TS T+S), and their respective indexes are (010100), (1010) and (1 1). Therefore, use symbol 1 and its position index (01010 0) to restore the data array (array) (X 1 X 1 XX), use symbol 4 and its position index (1 0 1 0) to restore the data array (4 1 X 1 4 X) ), and use the symbol 5 and its position index (1 1) to restore the data array (4 1 5 1 45) o The restored data array (4 15 14 5) is converted to DPCM mode (TSS) (TTS) (TS T+ S) (TTS) (TSS) (TS T+S) combination array. Therefore, it is possible to indicate which DPCM has been performed on each component of each vertex based on the restored data array.

The DPCM mode decoder 812 outputs the differential data of each component of each vertex to the dictionary mode selector 814 together with the decoded DPCM mode information.

In step S934, according to the value of nDicModeSelect of each component of each vertex, the dictionary mode selector 814 outputs the component data of each vertex input from the DPCM mode decoder 812 to

02140002.4 First appearance mode decoder 816 or incremental mode decoder 818.

If nDicModeSelect is 0, the dictionary mode selector 814 outputs the component data of the vertex to the appearance mode decoder 816, and if nDicModeSelect is 1, the dictionary mode selector 814 outputs the component data of the vertex to the incremental mode decoder 818.

In step S936, the presence mode decoder 816 restores the symbol data and position index of each component to differential data.

Fig. 11B is a schematic diagram illustrating an example of an appearance mode decoding. Referring to FIG. 11B, the appearance mode decoder 816 receives the symbol data from the dictionary mode selector 814 and checks bSoleKV and nTrueOne.

If bSoleKV indicates that there are multiple input symbols in the differential data and nTrueOne indicates that the position index has not been reversed, the appearance mode decoder 816 restores the differential data by inserting the input symbols at the respective positions indicated by their respective position indexes in the data array.

For example, the emergence mode decoder 816 sequentially receives symbols 3, 7, and -4 and their respective positions 1 (0 1 000 1 0 1 000). (1 0 1 0 1 0 0) and (1 1 1) .

The pattern decoder 816 records the first symbol 3 in the differential data array according to the position index (0 1 0 0 0 1 0 1 0 0 0). Therefore, (3 X3XXX3X3XX X) is obtained by inserting the symbol 3 in the differential data array corresponding to the position of 1 in the position index (0 1 0 0 0 1 0 1 0 0 0).

The emergence mode decoder 816 recovers the subsequent symbol 7. In the process of restoring symbol 7, the position of symbol 3 in the differential data array is not considered, so that the position index for symbol 7 is not (0 10 1000 1 0 0), but (1 0 1 0 1 00). The mode decoder 816 records the symbol 7 in the first position in the position not occupied by the symbol 3 in the differential data array, and then corresponds to the position of 1 in the position index (1 0 10 10 0) in the differential data array. Record symbol 7. Therefore, after the symbol 7 is restored, the differential data array is (3 7 3 7 X7 3X3 7 XX).

The appearance mode decoder 816 restores the symbol -4 according to the index (1 1 1), and therefore generates a differential data array of (3 737 -4 73 -4 374 -4).

If bSoleKV is set to 1, it means that there are only input symbols in the differential data, and there is no position index for the input symbols. Therefore, the appearance mode decoder 816 records the input symbol at the first position in the blank differential data array, and performs processing for restoring the next symbol.

In step S936, the incremental mode decoder 818 retrieves the sign and position of each component

02140002.4 The first reference is restored to differential data. The incremental mode decoding will be described later with reference to FIG. 11C.

The incremental mode decoder 818 receives from the dictionary mode selector 814 a symbol flag indicating whether there is a symbol in the differential data, nTrueOne indicating whether the position index has been reversed, and a position index.

The augmentation mode decoder 818 decodes the symbols included in the differential data according to the input symbol flag. Like the symbol table used for incremental mode encoding, in the symbol table used for incremental mode decoding, the symbols are arranged in a column in the order from the symbol with the lowest absolute value to the symbol with the largest absolute value. Between two symbols with the same absolute value, the symbol with a positive value is arranged in a row higher than the other symbols. The size of the symbol mark is 2^{nKVCodingBit+1}-l, where nKVCodingBit represents the number of quantization bits decoded in the bad decoder 800. Therefore, if the sign flag is (00110 0 1), the incremental mode decoder 818 decodes -1, 2, and -3 existing as signs in the differential data.

The position indexes entered after the symbol mark are (1 0 1 000 1 0 1 000), (00 1 0 1 0 1 1), and (1 1 1 1) and correspond to the symbols -1, 2 and 3 respectively.

The incremental mode decoder 818 records the symbol -1 at the position corresponding to the position of 1 in the position index (1 0 1 0 0 0 1 0 1 0 0 0) in the differential data array, so that the generated data array is (-1 X 1 XXX-1 X-1 XXX)_O Subsequently, the incremental mode decoder 818 restores the symbol 2 by recording 2 in the position corresponding to the position where 1 is in the position index (0 0 10 10 1 1) in the differential data array. In the process of restoring symbol 2, the position of the first symbol -1 in the differential data array is not considered, so that the resulting differential data array is (-1 X-1 X2X-1 2-1 X22)_O The incremental mode decoder 81 recovers the symbol -3 by recording -3 in the differential data array at the position corresponding to the position where 1 in the position index (1 1 1 1) is, so that the resulting differential data array is (-1 -3 -1 -3 2 -3 -1 -3 2 2).

In step S939, the appearance mode decoder 816 and the incremental mode decoder 818 restore the differential data of each component of each vertex, and output the restored differential data to the inverse DPCM processor 830.

FIG. 8B is a block diagram of the anti-DPCM processor 830 according to the present invention, and FIG. 9B is a flowchart of the anti-DPCM operation.

Referring to FIG. 8B, the inverse DPCM processor 830 according to the present invention includes an inverse-time DPCM operator 842, which performs an inverse-time DPCM operation and an inverse-circular quantization operation on the input differential data, and then outputs the quantized key value of the coordinate interpolator Data; the inverse space DPCM operator 844, which performs the inverse space DPCM operation and the inverse loop quantization operation on the input differential data, and then outputs the quantized switch

02140002.4 The first key word value data; an inverse space-time DPCM operator 846, which performs an inverse space-time DPCM operation and an inverse loop quantization operation on the input differential data, and then outputs the quantized keyword value data; and an inverse DPCM mode selector 835, It outputs the input differential data to one of the inverse-time DPCM operator 842, the inverse-space DPCM operator 844, and the inverse-space-time DPCM operator 846.

Referring to FIG. 9B, in step S942, the inverse DPCM mode selector 835 determines the inverse DPCM operation to be performed on the input differential data according to the DPCM operation mode of each component of each vertex recovered in the DPCM mode decoder 812, And according to the reverse DPCM operation mode, the input differential data of each component of each vertex is output.

Each of the DPCM operators 842, 844, and 846 simultaneously performs an inverse DPCM operation and an inverse loop quantization operation on the differential data input thereto.

In step S944, the inverse-time DPCM operator 842 performs the inverse-time DPCM operation on the input differential data according to equation (8), and in step S946, the inverse-space DPCM operator 844 performs the inverse-space DPCM on the input differential data according to the equation (9) Operation, in step S948, the inverse-space-time DPCM operator 846 performs an inverse-space-time DPCM operation on the input differential data following equation (10).

% = Jiu + B "... Shi = Jiu + skillful use/...(9) Yi Guangjiu + Protect...+ Yiyang-Yizhi/)}...(10) In equations to (10), B means The quantization key value data of the j-th vertex in the i-th key frame represents the difference data of the j-th vertex in the Saki key frame, and Ref represents the reference equations (9) and (10), if Use Re/or Li-3 to be less than the minimum value of the quantization key value data of each component, then use the minimum value instead of R or {^-1,7 + (jin,Re/-dagger-l,Re/ )}. If you use Re/or recall 5 ⁺ -/-ΐ®)} is greater than the maximum value in the quantization key value data of each component, then use the maximum value and not use or {Qiao + recall / Yixin)}

Ο

Each of the DPCM operators 842, 844, and 846 uses the equation (1) performs the inverse DPCM operation and simultaneously performs the inverse loop quantization operation in order to extend the reduced value in the encoding process

02140002.4 The range of the difference data.

InverseCircularQuantization{X_t): …(11)

X,.'= X^^nQMax-nQMin +1) (if X,&gt; 0)

X^= X_i + (nQMax-nQMin +1) (otherwise)

X; = + X_t {if nQMin &lt;+ X_t &lt;nQMax) = + Z,.' (/ nQMin &lt;Z,._, +X,.'&lt; nQMax) In equation (11), X is the same input value as Dy, which is the same as R or

-/)} The same as the previous reverse loop quantization value. nQMax and nQMin respectively represent the maximum value and the minimum value in the DPCMed differential data.

In step S949, the inverse DPCM processor 830 outputs the key value data of each component of each vertex that has been inverse DPCM and inverse cyclic quantization to the inverse quantizer 850.

Referring to FIG. 7B, following equation (2), the dequantizer 850 converts the minimum value fMin_X, fMin_Y, and fMin_Z and the maximum range value fMax in the input component data input from the keyword value header decoder 870 into binary numbers, and passes Substituting fMin_X, fMin_Y, blood-blood-B, and blood-xuanyi into equation (12) to inversely quantize the quantized keyword value data input from the inverse DPCM processor 830.

Jin Ba y_id._x = JMin_X+ p fMax ...(12) Liba

Kjy = Μη_ Υ + 2κ product gate x V_u--=βίΐη_Ζ+ ₂„^_e'_fl-x fMax equation (2), nKVQBits represents the size of quantization bits used for inverse quantization.

The dequantizer 850 must output the dequantized key value data of each component of each vertex in the form of a matrix shown in Table 2. In order to achieve this, in step S960, the dequantizer 850 checks whether the mode of the dequantized key value data is the transposition mode before outputting the dequantized key value data. If the mode of the dequantized key value data is the transposition mode, then in step S965, the dequantizer 850 generates and outputs the decoded key value data of the coordinate interpolator by inverse transforming the transposed matrix.

Subsequently, the SDL program code for decoding the encoded bit data stream and the variables used in such program code will be described with reference to FIGS. 12 to 18.

Figure 12 shows the highest class (class) of the bit data stream used to read the compressed coordinate interpolator,

CoordlKey Value Header and CoordlKeyValue are used to read out the coordinates corresponding to the general

02140002.4 The key value information class of the key value field data of the interpolated node. The function qf^start0 is used to initialize the arithmetic decoder before reading the AAC-encoded data.

FIG. 13 shows a program code for generating a bit data stream using the key value header information required for decoding the key value data.

The key value header data is decoded after the key header data is decoded. The key value header includes the number of vertices, key value data parameters for quantization, and maximum and minimum values for quantization. bTranspose is a flag indicating whether it is a transpose mode or a vertex mode. If bTranspose is 1, the transpose mode is selected in the decoding process. On the other hand, if bTranspose is 0, the vertex mode is selected. nKVQBit is the quantization bit used to restore floating-point numbers through inverse quantization. nCoordQBit is the size of bits used to represent the number of vertices nNumberOfCoord. Use nKVDigit after inverse quantization and indicate the maximum number of valid digits of the key value data. The KeyValueMinMax class restores the minimum value used for inverse quantization and the maximum data range divided into mantissa and exponent. The other part of the header information includes the minimum value among the maximum value and the maximum value and the minimum value in the quantization key value data of each component of each vertex. Specifically, nXQMinOfMax represents the minimum value among the maximum values in the quantization key value data of the x component of each vertex. nNumKeyCodingBit represents the bit size of nNumberOfKey representing the number of key data. Need to include nXQMinOfMax and nNumberOfKey information to decode the key value data.

14A and 14B are program codes showing an apparatus for implementing decoding DPCM mode according to the present invention. The meaning of each variable shown in Figs. 14A and 14B is as follows.

nDPCMMode represents the DPCM mode of each component (x, y, z) of each vertex. When nDPCMMode is set to 1, 2, or 3, it represents the time DPCM mode, the space DPCM mode, or the time and space DPCM mode, respectively.

bSelFlag is a flag used to select each component of each vertex. The dictionary encoder 340 is used to encode only the component of each vertex whose bSelFlag is set to 1. selectionFlagContext is the context for reading bSelFlag.

nKVACodingBit represents the coding bit for each component of each vertex. aqpXContext, aqpYContext and aqpZContext are the contexts for the X-axis, Y-axis and Z-axis, respectively, and are used to read nKVACodingBit₀ nRefVertex is the index of the reference vertex for all vertices. refContext is used to read the context of nRefV ertex.

nQM in represents the minimum value in the DPCMed difference data of each component of each vertex.

02140002.4 The qMinContext represents the context for reading nQMin, and qMinSignContext is the context for reading the sign of nQMin.

nQMax represents the maximum value in the DPCMed difference data of each component of each vertex. qMaxContext is the context for reading nQMax, and aMaxSignContext is the context for reading the sign of nQMax.

FIG. 15 is a diagram illustrating the program code for decoding the DPCM mode according to the present invention, and the meaning of each variable shown in FIG. 15 is as follows.

bAddressOfDPCMMode represents the usage of each DPCM dictionary symbol, which is constituted by a combination of DPCM modes for each component in the DPCM dictionary table. Each vertex includes three components, and there may be three different types of DPCM, T, S, and T+S modes in the components of each vertex. As shown in Figure 3, there are 27 dictionary symbols representing the combination of three DPCM modes. dpcmModeDicAddressContext is the context for reading bAddressOfDPCMMode.

bDPCMIndex indicates which DPCM symbol has been used for each vertex. dpcmModelDicIndexContext is the context for reading bDPCMIndex.

Fig. 16 is a schematic diagram showing a program code for decoding a dictionary encoding mode according to the present invention. Fig. 16 shows the meaning of each variable as follows.

dDicModeSelect represents the dictionary encoding mode that has been used in the dictionary encoding process. When dDicModeSelect is 1, it means that the dictionary encoding mode is an incremental mode. On the other hand, if dDicModeSelect is 0, it means that the dictionary encoding mode is an appearance mode.

Fig. 17 is a schematic diagram showing a program code for implementing the incremental mode decoding method according to the present invention. Fig. 17 shows the meaning of each variable as follows.

bAddress indicates whether or not the incremental mode dictionary symbol that represents the value of the quantized key has been used. The number of symbols used in the incremental mode table is 2nKvcodingBit+i_x dieAddressContext is the context for reading bAddress.

nTrueOne indicates whether the index data has been reversed. When nTrueOne is 1, the value of 1 in the position index is regarded as the actual value representing the position of the symbol. When nTrueOne is 0, the 0 value in the position index is considered to be the actual value representing the position of the symbol.

bAddrlndex represents the incremental mode symbol for each component of each vertex. dicIndexContext is used to read the context of bAddrlndex.

FIG. 18 is a program code for explaining a decoding method of an appearance pattern according to the present invention, and the meaning of each variable shown in FIG. 18 is as follows.

02140002.4 The nQKV includes the appearance mode symbol, which is quantized key value data. kvXContext, kvYContext, and kvZContext are contexts for reading nQKV, and kvSignContext is context for reading signs of nQKV.

bSoleKV indicates whether the decoded symbol appears only once in the differential data. If the decoded symbol appears only once in the differential data, soleKV is set to 1. dicSoleKVContext is the context for reading bSoleKV.

bDicIndex indicates which dictionary symbol has been used for each component of each vertex. dicIndexContext is the context for reading bDicIndex.

20A is a rate-distortion curve showing the result of performing the test performance of the method for encoding and decoding the key value data of the coordinate interpolator according to the present invention and the conventional MPEG-4 BIFS PMFC method. Specifically, FIG. 20A shows the relationship between the distortion degree and the encoding bit rate in the case of 38 key value data of the encoding coordinate interpolator. As shown in FIG. 20A, the method for encoding and decoding the key value data of the coordinate interpolator has higher efficiency than the conventional MPEG-4 BIFS PMFC method.

Figure 20B includes three schematic diagrams (a), (b) and (c). Specifically, in FIG. 20B, represents animation data, (b) represents animation data encoded/decoded according to the present invention, and (c) represents animation data encoded/decoded following a conventional encoding/decoding method. As shown in FIG. 20B, the method for encoding and decoding the key value data of the coordinate interpolator according to the present invention can provide a higher quality animation than the conventional encoding/decoding method, which is much closer to the original animation.

The method and apparatus for encoding/decoding key value data of coordinate interpolators to display key frame-based animation according to the present invention have been described above with reference to the accompanying drawings, and the preferred embodiments of the present invention are shown. It is obvious to those skilled in the art that the DPCM operation adopted in the preferred embodiment of the present invention is not limited to only the key value data of the coordinate interpolator, but can also be applied to the vertices that include multiple components to describe the three-dimensional object. data.

Figure 21A is a block diagram of a DPCM operator according to the present invention. Referring to FIG. 21A, the DPCM manipulator according to the present invention includes a time DPCM manipulator 2010, which generates a difference between vertex data at a predetermined time and vertex data at another predetermined time constituting a 3D object that changes over time Data; the spatial DPCM operator 2020, which generates differential data between the data of the vertex and the data of the reference vertex at a predetermined time; and the DPCM mode selector 2030, which outputs the differential data input from the time DPCM operator 2010 and the slave The smaller difference data between the difference data input by the spatial DPCM operator 2020.

02140002.4 The DPCM operator according to the present invention preferably further includes a space-time DPCM operator 2040, which calculates the difference data between the difference data between the vertices and the reference vertices in the key frame, and through the spatial DPCM operation As a result, the time DPCM operation is performed to calculate the corresponding difference data in another key frame. Even in the case where the space-time DPCM operator is provided, the DPCM mode selector 2030 still outputs the differential data input from the time DPCM operator 2010, the differential data input from the space DPCM operator 2020, and the space-time DPCM operation The smallest difference data among the difference data input by the device 2040.

The operation of the unit of the DPCM manipulator according to the present invention is the same as the operation of the corresponding unit of the DPCM processor described above.

According to the present invention, the DPCM manipulator receives quantized coordinate data constituting the vertices of the 3D object from the outside.

When the vertex represents the current object, the time DPCM operator 2010 uses equation (3) to calculate the difference data between the coordinate data of the vertex, and calculates the coordinate data of the vertex when the vertex represents the previous object.

The spatial DPCM operator 2020 uses equation (5) to calculate the difference data between the vertices that have performed the DPCM operation and the vertices existing on the same time axis as the DPCMed vertices, selects the vertex with the smallest difference data as the reference vertices, and outputs the difference data.

The DPCM mode selector 2030 calculates the size of the difference data input from the time DPCM operator 2010 and the difference data input from the space DPCM operator 2020, and outputs the difference data with a smaller size together with the DPCM operation information=preferred according to the present invention The embodiment may further include a space-time DPCM operator 2040 in the DPCM operator, which uses equation (6) to perform the above-mentioned spatial DPCM operation on the quantized coordinate data of the 3D object, and perform the spatial DPCM operation on the current vertex and on the previous vertex As a result of performing the spatial DPCM operation, perform the above-mentioned temporal DPCM operation.

The cyclic quantizer 2050 included in the DPCM operator according to the preferred embodiment of the present invention uses equation (7) to reduce the range of the differential data input therein.

Fig. 21E is a block diagram of an inverse DPCM operator, which converts the differential data generated by the DPCM operator according to the present invention into quantized coordinate data.

The inverse DPCM operator according to the present invention includes an inverse time DPCM operator 2110, which performs an inverse DPCM operation on the difference data between the data of a vertex at a predetermined time and the data of a vertex at another predetermined time; an anti-spatial DPCM operator 2120, the data of the vertices and the parameters at the predetermined instant

02140002.4 The difference data between the data of the test vertex performs an anti-spatial DPCM operation; and an anti-DPCM mode selector 2100, which outputs the difference data to the inverse-time DPCM operator 2110 or according to the mode of the DPCM operation that has been performed on the difference data Anti-spatial DPCM operator 2120.

The anti-DPCM operator according to the present invention preferably also includes an anti-space-time DPCM operator 2130, which performs an anti-space-time DPCM operation on the result of the current anti-space DPCM operation and the result of the previous anti-space DPCM operation.

The operation of the unit of the anti-DPCM operator according to the present invention is the same as the operation of the corresponding unit of the aforementioned anti-DPCM processor.

The differential data to be restored to quantized coordinate data is input to the inverse DPCM mode selector 2100. Then, the inverse DPCM mode selector 2100 recognizes which DPCM has been performed on the component data of each vertex included in the input differential data , And output the component data of each vertex to the inverse-time DPCM operator 2110, the inverse-space DPCM operator 2120, and the inverse-space-time DPCM operator 2130.

The inverse-time DPCM operator 2110 follows the equation to perform the inverse-time DPCM operation on the input differential data, and the anti-spatial DPCM operator 2120 follows the equation (9) to perform the inverse-space DPCM operation on the input differential data, and inverse the space-time DPCM The operator 2130 follows equation (10) to perform a space-time DPCM operation on the input differential data.

If the input differential data has been cyclically quantized, each of the DPCM operators 2110, 2120, and 2130 uses equation (11) to perform an inverse cyclic quantization operation on its respective inverse DPCM differential data in order to expand the respective inverse DPCM differential The scope of the data.

The present invention can be implemented as a computer readable code written on a computer readable recording medium. Among them, the computer-readable recording medium includes any kind of recording medium that can be read by a computer system. For example, the computer-readable recording medium may include ROM, RAM, CD-ROM, magnetic tape, floppy disk, optical data storage, carrier wave (transmitted via the Internet), and the like. The computer-readable recording medium can be distributed to computer systems connected via a network, and the computer can read the recording medium in a distributed method.

Taking into account the difference data between the coordinate data of the vertices in different key frames and the difference data between the coordinate data of the vertices of the coordinate interpolator, the key value data for encoding the coordinate interpolator according to the present invention The method and device have high coding efficiency by coding the key value data of the coordinate interpolator.

In addition, the method and device for encoding key value data of coordinate interpolators according to the present invention

02140002.4 The first has higher coding efficiency by using the sign corresponding to the value of the difference data and the position index for the respective sign to express the difference data.

Although the present invention has been shown and described with reference to several preferred embodiments, those skilled in the art will understand that various forms and details can be made without departing from the spirit and scope of the appended claims as defined change.

The present invention is not limited to the above-mentioned embodiments, and various changes and modifications can be made without departing from the scope of the present invention.

02140002.4