Apparatus for encoding and decoding key data and key value data of coordinate interpolator and recording medium containing bitstream into which coordinate interpolator is encoded

• US 8,705,610 B2
• Filed: 08/30/2010
• Issued: 04/22/2014
• Est. Priority Date: 11/27/2001
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Lee, Shin-jun, Jung, Seok-yoon, Jang, Euee-seon, Woo, Sang-oak, Han, Mahn-jin, Kim, Do-kyoon, Jang, Gyeong-ja
• Primary Examiner(s): Perungavoor, Sath V
• Assistant Examiner(s): Le, Peter D
• Application Number:
  US12/923,038
• Publication Number:
  US 20100322308A1
• Time in Patent Office: 1,331 Days
• Field of Search: 375/240
• US Class Current: 375/240
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H04N 19/00 Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
• CPC Class Codes: H04N 19/103 Selection of coding mode or of prediction mode
• CPC Class Codes: H04N 19/12 Selection from among a plurality of transforms or standards, e.g. selection between discrete cosine transform [DCT] and sub-band transform or selection between H.263 and H.264
• CPC Class Codes: H04N 19/126 Details of normalisation or weighting functions, e.g. normalisation matrices or variable uniform quantisers
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/136 Incoming video signal characteristics or properties
• CPC Class Codes: H04N 19/14 Coding unit complexity, e.g. amount of activity or edge presence estimation H04N19/146 takes precedence
• CPC Class Codes: H04N 19/25 with scene description coding, e.g. binary format for scenes [BIFS] compression
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/537 Motion estimation other than block-based
• CPC Class Codes: H04N 19/577 Motion compensation with bidirectional frame interpolation, i.e. using B-pictures
• CPC Class Codes: H04N 19/70 characterised by syntax aspects related to video coding, e.g. related to compression standards

Abstract

A method of encoding a coordinate interpolator that includes key data and a key header including information regarding encoding of the key data, the key data representing the position of a key frame on a time axis. The method includes, encoding the key header and encoding the key data according to the result of the encoding performed in the encoding the key header. The encoding of the key data includes performing quantization on the key data according to the quantization bit size and generating differential data by performing differential pulse code modulation (DPCM) on the result of the quantization according to a DPCM order. The encoding of the key data also includes performing a divide-and-divide (DND) on the differential data so that a difference between a maximum and minimum of the differential data can be minimized and performing entropy encoding on the result of the DND.

Claims

1. An apparatus for encoding a coordinate interpolator, which includes key data indicating the location of each keyframe on a temporal axis and key value data representing the location of each vertex of an object in each of the keyframes using coordinates of the vertices each consisting of x, y, and z components, the apparatus comprising:

a key data encoder, which comprises;

a first quantizer which quantizes key data of a coordinate interpolator using predetermined quantization bits;

a first differential pulse code modulation (DPCM) processor which generates differential data of the quantized key data according to a DPCM order;

a divide-and-divide (DND) processor which performs a DND operation on the differential data depending on a relationship between the differential data and a maximum value and a minimum value among them; and

a first entropy encoder which entropy-encodes the differential data input from the DND processor,

a key value data encoder, which comprises;

a second quantizer which quantizes key value data of a coordinate interpolator using predetermined quantization bits;

a second DPCM processor which generates differential data based on the temporal variation of coordinates of each vertex of quantized key value data and differential data based on the spatial variation of the coordinates of each of the vertices of the quantized key value data by performing a predetermined DPCM operation on components of each of the vertices of the quantized key value data;

a dictionary encoder which generates symbols indicating DPCMed differential data of each of the vertices and a DPCM operation mode, which has been performed on the differential data and indexes indicating the positions of the symbols; and

a second entropy encoder which entropy-encodes the symbols and the indexes,

and a header encoder which encodes information necessary to decode a bitstream encoded by the key data encoder and the key value data encoder.

2. The apparatus of claim 1, wherein the key data encoder further comprises a linear key encoder, which identifies a region where key data linearly increase among key data input thereinto and encodes the region.

3. The apparatus of claim 1, wherein the key data encoder further comprises:

a shifter which obtains a differential datum (mode) having the highest frequency among the differential data input from the first DPCM processor and subtracts the mode from the differential data; and

a folding processor which converts the shifted differential data into positive numbers or negative numbers, and the DND processor selects one of the differential data input from the shifter, the differential data input from the folding processor, and the DNDed differential data depending on the number of bits required for encoding and outputs the selected differential data.

4. The apparatus of claim 1, wherein the second DPCM processor comprises:

a DPCM operator which performs a temporal DPCM operation on each of the components of each of the vertices of the quantized coordinate interpolator so as to generate first differential data between a vertex in one keyframe and the vertex in another keyframe, performs a spatial DPCM operation on each of the components of each of the vertices of the quantized coordinate interpolator so as to generate second differential data between vertices in the same keyframe, and performs a spatio-temporal DPCM operation on each of the components of each of the vertices of the quantized coordinate interpolator so as to generate third differential data between vertices and keyframes;

a circular quantizer which performs a circular quantization operation on the first through third differential data input from the DPCM operator so as to reduce their ranges; and

a DPCM mode selector which selects one of the first through third differential data, which have been circular-quantized, depending on the number of bits required for encoding, and outputs the selected differential data.

5. The apparatus of claim 1, wherein the dictionary encoder comprises:

a DPCM mode encoder which generates symbols representing combinations of DPCM modes which have been performed on data of each of the components of each of the vertices and position indexes indicating the positions of the symbols; and

an occurrence mode encoder which generates symbols corresponding to input differential data of each of the components of each of the vertices and position indexes indicating the positions of the symbols.

6. The apparatus of claim 5, wherein the dictionary encoder further comprises:

an incremental mode encoder which generates a symbol flag indicating whether or not predetermined symbols exist in input differential data of each of the components of each of the vertices and position indexes indicating the positions of the symbols; and

a table size calculator which calculates the size of a first symbol table constituted by the symbols corresponding to the input differential data and the size of the symbol flag and outputs the input differential data of each of the components of each of the vertices, which are input from the DPCM mode encoder, to the occurrence mode encoder or the incremental mode encoder, depending on the sizes of the first symbol table and the symbol flag.

7. An apparatus for decoding a bitstream, into which a coordinate interpolator, which includes key data indicating the location of each keyframe on a temporal axis and key value data representing the location of each vertex of an object in each of the keyframes using coordinates of the vertices each consisting of x, y, and z components, is encoded, the apparatus comprising:

a key data decoder, which comprises;

a header decoder which decodes header information necessary to decode key data and key value data from an input bitstream and outputs the decoded header information;

a first entropy decoder which entropy-decodes the input bitstream and outputs differential data of decoded key data;

an inverse divide-and-divide (DND) processor which extends the range of differential data of the entropy-decoded key data by performing an inverse DND operation on the differential data depending on the an order of DND read from the input bitstream by the header decoder if the order of DND read is set to a value of 1 or greater;

a first inverse differential pulse code modulation (DPCM) processor which performs an inverse DPCM operation on the differential data input from the inverse DND processor as many times as the order of DPCM input from the header decoder and outputs quantized key data, wherein the header information includes information which indicates how many iterations of DND have been performed to adjust a range of DPCM results; and

a first inverse quantizer which inverse-quantizes the quantized key data and outputs decoded key data, and

a key value data decoder, which comprises;

a second entropy decoder which generates data to be dictionary-decoded,

including symbols of differential data of key value data, indexes indicating the positions of the symbols, and a DPCM operation mode, by entropy-decoding the input bitstream;

a dictionary decoder which generates differential data of key value data by performing a dictionary decoding operation depending on a dictionary decoding mode information input from the header decoder;

a second inverse DPCM processor which generates quantized data by retrieving differential data between keyframes and differential data between vertices, which are input from the dictionary decoder, depending on the DPCM operation mode; and

a second inverse quantizer which generates retrieved key value data by inverse-quantizing the quantized data.

8. The apparatus of claim 7, wherein the key data decoder further comprises:

an inverse folding processor which performs an inverse folding operation on the differential data input from the inverse DND processor so as to divide the differential data into positive numbers and negative numbers or bypasses the differential data depending on the order of DND input from the header decoder; and

an inverse shifter which transfers the range of the differential data input from the inverse DND processor or the inverse folding processor by adding a predetermined mode input from the header decoder to the differential data, and the first DPCM processor retrieves the differential data input from the inverse shifter and outputs quantized key data.

9. The apparatus of claim 7, wherein the second inverse DPCM processor comprises:

an inverse temporal DPCM operator which performs an inverse DPCM operation on differential data of each vertex varying in accordance with the passage of time;

an inverse spatial DPCM operator which performs an inverse DPCM operation on differential data between each of the vertices and a reference vertex corresponding to the vertices at a predetermined moment of time; and

an inverse DPCM mode selector which outputs differential data input thereinto to the inverse temporal DPCM operator or the inverse spatial DPCM operator depending on the DPCM operation mode.

10. A method of encoding a coordinate interpolator that comprises key data and a key header comprising information regarding encoding of the key data, the key data representing the position of a key frame on a time axis, the method comprising:

encoding the key header; and

encoding the key data according to the result of the encoding performed in the encoding the key header,

wherein the encoding the key data comprises;

performing quantization on the key data according to the quantization bit size (nKeyQBit);

generating differential data by performing differential pulse code modulation (DPCM) on the result of the quantization according to a DPCM order (nKDPCMOrder);

performing a divide-and-divide (DND) on the differential data so that a difference between a maximum and minimum of the differential data can be minimized; and

performing entropy encoding on the result of the DND.

11. The method of claim 10, wherein the key header comprises:

a quantization bit quantity (nKVQBit) which indicates the number of bits used to quantize the key data;

a key data quantity (nNumberOfKey) which indicates the number of the key data;

a key data digit number (nKeyDigit) which indicates the number of digits of the key data;

a linear key flag (bIsLinearKeySubRegion) which indicates whether the key data comprises a linear key region;

beginning/ending key data (IKey) which is included in the key header if the linear key flag (bIsLinearKeySubRegion) is set to a value of 1, the beginning/ending key data (IKey) indicating where the linear key region begins and ends;

a quantization error adjustment flag (bRangeFlag) which indicates whether to adjust a maximum and minimum of the key data using a method by which a quantization error can be minimized;

an adjusted maximum and minimum (KeyMinMax) of the key data which are included in the key header if the quantization error adjustment flag (bRangeFlag) is set to a value of 1, the adjusted maximum and minimum (KeyMinMax) being used to perform quantization;

the DPCM order (nKDPCMOrder) which indicates how many iterations of DPCM which have been performed;

reference key data (nQIntraKey) which is used to determine whether to perform DPCM, wherein the number of the reference key data (nQIntraKey) corresponds to the DPCM order (nKDPCMOrder);

key data sign bits (nQIntraKeySign), wherein the number of the key data sign bits (nQIntraKeySign) corresponds to the DPCM order (nKDPCMOrder);

a shift flag (bShiftFlag) which indicates whether to shift all the key data based on the key data with a highest frequency among all the key data obtained by DPCM;

a shift value (nkeyShift) which represents the degree to which all the key data is to be shifted;

a shift value sign bit (nKeyShiftSign) which is a sign bit of the shift value (nKeyShift);

a divide-and-divide (DND) order (nDNDOrder) which indicates how many iterations of DND have been performed to adjust a range of DPCM results;

at least one (nKeyMax) of maximums and minimums which are used to perform DND, wherein the number of the maximums and minimums corresponds to the DND order (nDNDOrder);

a sign bit (nKeyMaxSign) which identifies the at least one (nKeyMax) of the maximums and minimums, wherein the number of the sign bit (nKeyMaxSign) corresponds to the DND order (nDNDOrder);

an invert-down flag (bKeyInvertDownFlag) which indicates whether to invert down DND results;

an invert-down value (nKeyInvertDown) which indicates the degree to which the DND results are to be inverted down; and

an adaptive arithmetic coding (AAC) flag (bSignedAACFlag) which indicates whether entropy encoding has been performed using a signed AAC method or an unsigned AAC method,

wherein the linear key region is a region where the key data linearly increases.

12. An apparatus for decoding a bitstream into which a coordinate interpolator that comprises key data and a key header comprising information regarding encoding of the key data, the key data representing the position of a key frame on a time axis, the apparatus comprising:

a processor comprising;

a key header decoding unit which decodes the key header;

a key decoding unit which decodes the key data according to the result of the decoding performed by the key header decoding unit,

wherein the key decoding unit decodes the key data by performing entropy decoding; and

an inverse divide-and-divide (DND) unit which performs inverse DND on the result of the entropy decoding performed by the entropy decoding unit if the DND order (nDNDOrder) is set to a value of 1 or greater,

wherein the key header comprises;

the DND order (nDNDOrder) which indicates how many iterations of DND have been performed to adjust a range of DPCM results.

13. The apparatus of claim 12, wherein the key decoding unit decodes the key data by performing inverse shift, inverse differential pulse code modulation (DPCM), inverse quantization, and linear key synthesis.

14. The apparatus of claim 13, wherein the key header comprises:

a quantization bit quantity (nKVQBit) which indicates the number of bits used to quantize the key data;

a key data quantity (nNumberOfKeY) which indicates the number of the key data;

a key data digit number (nKeyDigit) which indicates the number of digits of the key data;

a linear key flag (bIsLinearKeySubRegion) which indicates whether the key data comprises a linear key region;

beginning/ending key data (IKey) which is included in the key header if the linear key flag (bIsLinearKeySubRegion) is set to a value of 1, the beginning/ending key data (IKey) indicating where the linear key region begins and ends;

a quantization error adjustment flag (bRangeFlag) which indicates whether to adjust a maximum and minimum of the key data using a method by which a quantization error can be minimized;

an adjusted maximum and minimum (KeyMinMax) of the key data which are included in the key header if the quantization error adjustment flag (bRangeFlag) is set to a value of 1, the adjusted maximum and minimum (KeyMinMax) being used to perform inverse quantization;

a DPCM order (nKDPCMOrder) which indicates how many iterations of DPCM which have been performed;

reference key data (nQIntraKey) which is used to determine whether to perform DPCM, wherein the number of the reference key data (nQIntraKey) corresponds to the DPCM order (nKDPCMOrder);

key data sign bits (nQIntraKeySign), wherein the number of the key data sign bits (nQIntraKeySign) corresponds to the DPCM order (nKDPCMOrder);

a shift flag (bShiftFlag) which indicates whether to shift all the key data based on the key data with a highest frequency among all the key data obtained by DPCM;

a shift value (nKeyShift) which represents the degree to which all the key data is to be shifted;

a shift value sign bit (nKeyShiftSign) which is a sign bit of the shift value (nKeyShift);

a divide-and-divide (DND) order (nDNDOrder) which indicates how many iterations of DND have been performed to adjust a range of DPCM results;

at least one (nKeyMax) of maximums and minimums which are used to perform DND, wherein the number of the maximums and minimums corresponds to the DND order (nDNDOrder),

a sign bit (nKeyMaxSign) which identifies the at least one (nKeyMax) of the maximums and minimums, wherein the number of the sign bit (nKeyMaxSign) corresponds to the DND order (nDNDOrder);

an invert-down flag (bKeyInvertDownFlag) which indicates whether to invert down DND results;

an invert-down value (nKeyInvertDown) which indicates the degree to which the DND results are to be inverted down; and

an adaptive arithmetic coding (AAC) flag (bSignedAACFlag) which indicates whether entropy encoding has been performed using a signed AAC method or an unsigned AAC method,

wherein the linear key region is a region where the key data linearly increases.

15. The apparatus of claim 14, wherein the key decoding unit comprises:

a first entropy decoding unit which performs entropy-decoding on the encoded key data by performing inverse signed AAC if the AAC flag (bSignedAACFlag) indicates that the encoded key data has been encoded using the signed AAC method and performs inverse unsigned AAC if the AAC flag (bSignedAACFlag) indicates that the encoded key data has been encoded using the unsigned AAC method;

an inverse DND unit which performs inverse DND on the result of the entropy decoding performed by the entropy decoding unit if the DND order (nDNDOrder) is set to a value of 1 or greater;

an inverse shift unit which inversely shifts the result of the inverse fold performed by the inverse fold unit by as much as the shift value (nKeyShift) if the DND order (nDNDOrder) is set to a value other than −

1, and inversely shifts the result of the entropy decoding performed by the entropy decoding unit by as much as the shift value (nKeyShift) if the DND order (nDNDOrder) is set to a value of −

1;

a first inverse DPCM unit which performs inverse DPCM on the result of the inversely shifting performed by the inverse shift unit according to the DPCM order (nKDPCMOrder);

a first inverse quantization unit which adjusts the result of the inverse DPCM performed by the inverse DPCM unit if the maximum and minimum key data have been adjusted, and performs inverse quantization on the result of the adjusting according to the quantization bit size (nkeyQBit); and

a linear key synthesis unit which, if the decoded key header comprises the linear key region, decodes the key data of the linear key region using the beginning/ending key data ((Key), and performs linear key synthesis on the result of the decoding and the result of the inverse quantization performed by the inverse quantization unit.

16. The apparatus of claim 15, wherein, if the DND order (nDNDOrder) is set to a value of 1 or greater and the invert-down value is not −

1, an invert-down operation, which is an inverse operation of a shift-up operation performed during entropy encoding, is performed, if the DND order (nDNDOrder) is set to a value of 1 or greater and the invert-down value is −

1, the invert-down operation is not performed, and the inverse DND is performed a predetermined number of times corresponding to the DND order (nDNDOrder), wherein, if a current iteration of the inverse DND is not a final iteration of the inverse DND and the at least one (nKeyMax) is a positive value, the current iteration of the inverse DND is performed using an invert-divide-down method, if the current Iteration of the inverse DND is not the final iteration of the inverse DND and the at least one (nKeyMax) is a negative value, the current iteration of the inverse DND is performed using an inverse-divide-up method, and if the current iteration of the inverse DND is the final iteration of the inverse DND, the current iteration of the inverse DND is performed using an inverse-divide-up method regardless of whether the at least one (nKeyMax) is a positive value or a negative value.

17. An apparatus for encoding a coordinate interpolator that comprises key data and a key header comprising information regarding encoding of the key data is encoded, the key data representing the position of a key frame on a time axis, the apparatus comprising:

a processor comprising;

a key header encoding unit which encodes the key header; and

a key encoding unit which encodes the key data according to the result of the encoding performed by the key header encoding unit

wherein the key encoding unit comprises;

a first quantization unit which performs quantization on the key data according to the quantization bit size (nKeyQBit);

a first differential pulse code modulation (DPCM) unit which generates differential data by performing DPCM on the result of the quantization performed by the quantization unit according to the DPCM order (nKDPCMOrder);

a first divide-and-divide (DND) unit which performs DND on the differential data so that a difference between a maximum and minimum of the differential data can be minimized; and

a first entropy encoding unit which performs entropy encoding on the result of the DND performed by the DND unit.

18. The apparatus of claim 17, wherein the key header comprises:

a quantization bit quantity (nKVQBit) which indicates the number of bits used to quantize the key data;

a key data quantity (nNumberOfKey) which indicates the number of the key data;

a key data digit number (nKeyDigit) which indicates the number of digits of the key data;

a linear key flag (bIsLinearKeySubRegion) which indicates whether the key data comprises a linear key region;

beginning/ending key data (IKey) which is included in the key header if the linear key flag (bIsLinearKeySubRegion) is set to a value of 1, the beginning/ending key data (IKey) indicating where the linear key region begins and ends;

a quantization error adjustment flag (bRangeFlag) which indicates whether to adjust a maximum and minimum of the key data using a method by which a quantization error can be minimized;

an adjusted maximum and minimum (KeyMinMax) of the key data which are included in the key header If the quantization error adjustment flag (bRangeFlag) is set to a value of 1, the adjusted maximum and minimum (KeyMinMax) being used to perform quantization;

a DPCM order (nKDPCMOrder) which indicates how many iterations of DPCM which have been performed;

reference key data (nQIntraKey) which is used to determine whether to perform DPCM, wherein the number of the reference key data (nQIntraKey) corresponds to the DPCM order (nKDPCMOrder);

key data sign bits (nQIntraKeySign), wherein the number of the key data sign bits (nQIntraKeySign) corresponds to the DPCM order (nKDPCMOrder)

a shift flag (bShiftFlag) which indicates whether to shift all the key data based on the key data with a highest frequency among all the key data obtained by DPCM;

a shift value (nKeyShift) which represents the degree to which all the key data is to be shifted;

a shift value sign bit (nkeyShiftSign) which is a sign bit of the shift value (nKeyShift) a divide-and-divide (DND) order (nDNDOrder) which indicates how many iterations of DND have been performed to adjust a range of DPCM results;

at least one (nKeyMax) of maximums and minimums which are used to perform DND, wherein the number of the maximums and minimums corresponds to the DND order (nDNDOrder);

a sign bit (nKeyMaxSign) which identifies the at least one (nKeyMax) of the maximums and minimums, wherein the number of the sign bit (nKeyMaxSign) corresponds to the DND order (nDNDOrder);

an invert-down flag (bKeyInvertDowflFlag) which indicates whether to invert down DND results;

an invert-down value (nKeyInvertDown) which indicates the degree to which the DND results are to be inverted down; and

an adaptive arithmetic coding (AAC) flag (bSignedAACFlag) which indicates whether entropy encoding has been performed using a signed AAC method or an unsigned AAC method,

wherein the linear key region is a region where the key data linearly increases.

19. A method of decoding a bitstream into which a coordinate interpolator that comprises key value data and a key value header comprising information regarding encoding of the key value data, the key value data representing the shape and position of an object on a key frame using coordinates of each of a plurality of vertices comprising x, y, and z components, the method comprising:

decoding the key value header; and

decoding the key value data according to the result of the decoding performed in the decoding the key value header,

wherein the decoding the key value data comprises;

entropy-decoding the key value data in units of the x, y, and z components;

dictionary-decoding the entropy-decoded key value data in units of the x, y, and z components;

inversely differential-pulse-code-modulating the dictionary-decoded key value data in units of the x, y, and z components; and

inversely quantizing the inversely differential-pulse-code modulated key value data in units of the x, y, and z components.

20. The method of claim 19, wherein the key value header comprises a transpose flag (bTranspose) which indicates whether the key value data is to be decoded in a vertex mode or in a transpose mode, wherein decoding the key value data further comprises:

determining whether the transpose flag indicates that the key value data is to be decoded in the vertex mode or in the transpose mode and transposing the result of the inversely quantizing if the transpose flag is determined to indicate that the key value data is to be decoded in the transpose mode.

21. The method of claim 19, wherein the key value header comprises:

a quantization bit quantity (nKVQBit) which indicates the number of bits used to quantize the key value data;

maximums and minimums (KVMinMax) of the key value data of the x, y, and z components of the vertices;

a key value digit number nKVDigit which indicates the number of digits of the key value data, needed to read the maximum and minimum (KVMinMax);

a transpose flag (bTranspose) which indicates whether the key value data is to be decoded in a vertex mode or in a transpose mode;

a vertex quantity (nNumberOfCoord) which indicates the number of the vertices; and

maximums and minimums (nXQMinOfMin, nXQMaxOfMin, nXQMinOfMaX, nXQMaXOfMaX, nYQMinOfMin, nYQMaxOfMin, nYQMinOfMax, nYQMaxOfMax, nZQMinOfMin, nZQMaxOfMin, nZQMinOfMax, and nZQMaxOfMaX) among the quantized key value data of the x, y, and z components of the vertices.

22. A method of encoding a coordinate interpolator that comprises key value data and a key value header comprising information regarding encoding of the key value data are encoded, the key value data representing the shape and position of an object on a key frame using coordinates of each of a plurality of vertices comprising x, y, and z components, the method comprising:

encoding the key value header; and

encoding the key value data according to the result of the encoding performed in the encoding the key value header,

wherein the encoding the key value data comprises;

quantizing the key value data in units of the x, y, and z components;

differential-pulse-code-modulating the quantized key value data in units of the x, y, and z components;

dictionary-encoding the differential-pulse-code-modulated key value data in units of the x, y, and a z components; and

entropy-encoding the dictionary-encoded key value data in units of the x, y, and a z components.

23. The method of claim 22, wherein differential-pulse-code-modulating comprises differential-pulse-code-modulating the quantized key value data using a temporal DPCM method by which differential data between the key frames is generated, a spatial DPCM by which differential data between the vertices in the key frame is generated, or a temporal and spatial DPCM method by which differential data between the key frames and differential data between the vertices in the key frame are both generated.

24. An apparatus for decoding a bitstream into which a coordinate interpolator that comprises key value data and a key value header comprising information regarding encoding of the key value data, the key value data representing the shape and position of an object on a key frame using coordinates of each of a plurality of vertices comprising x, y, and a z components, the apparatus comprising:

a processor comprising;

a key value header decoding unit which decodes the key value header; and

a key value decoding unit which decodes the key value data according to the result of the decoding performed by the key value header,

wherein the key value decoding unit comprises;

a second entropy decoder which entropy-decodes the key value data in units of the x, y, and z components;

a dictionary decoder which dictionary-decodes the entropy-decoded key value data in units of the x, y, and a z components;

a second inverse differential pulse code modulator which Inversely differential-pulse-code-modulates the dictionary-decoded key value data in units of the x, y, and z components; and

a second inverse quantizer which inversely quantizes the inversely differential-pulse-code-modulated key value data in units of the x, y, and z components.

25. The apparatus of claim 24, wherein the key value header comprises:

a quantization bit quantity (nKVQBit) which indicates the number of bits used to quantize the key value data;

maximums and minimums (KVMinMax) of the key value data of the x, —

′

, and z components of the vertices;

a key value digit number nKVDigit which indicates the number of digits of the key value data, needed to read the maximum and minimum (KVMinMax);

a transpose flag (bTranspose) which indicates whether the key value data is to be decoded in a vertex mode or in a transpose mode;

a vertex quantity (nNumberOfCoord) which indicates the number of the vertices; and

maximums and minimums (nXQMinOfMin, nXQMaxOfMin, nXQMinOfMax, nxQMaxOfMax, nYQMinOfMin, nYQMaxOfMin, nYQMinOfMax, nYQMaxOfMax, nZQMinOfMiri, nZQMaxOfMin, nZQMinOfMax, and nZQMaxOfMax) among the quantized key value data of the x, y, and z components of the vertices.

26. An apparatus for encoding a coordinate interpolator that comprises key value data and a key value header comprising information regarding encoding of the key value data are encoded, the key value data representing the shape and position of an object on a key frame using coordinates of each of a plurality of vertices comprising x, y, and z components, the apparatus comprising:

a processor comprising;

a key value header encoding unit which encodes the key value header; and

a key value encoding unit which encodes the key value data according to the result of the encoding performed by the key value header encoding unit,

wherein the key value encoding unit comprises;

a second quantizer which quantizes the key value data in units of the x, y, and z components;

a second differential pulse code modulator which differential-pulse-code modulates the quantized key value data in units of the x, y, and z components;

a dictionary encoder which dictionary-encodes the differential-pulse-code modulated key value data in units of the x, y, and z components; and

a second entropy encoder which entropy-encodes the dictionary-encoded key value data in units of the x, y, and z components.

27. The method apparatus of claim 26, wherein the second differential pulse code modulator differential-pulse-code-modulates the quantized key value data using a temporal DPCM method by which differential data between the key frames is generated, a spatial DPCM by which differential data between the vertices in the key frame is generated, or a temporal and spatial DPCM method by which differential data between the key frames and differential data between the vertices in the key frame are both generated.