Method and apparatus for encoding and decoding position interpolator

An apparatus for encoding a position interpolator, which includes key data indicating the locations of keyframes on a temporal axis and key value data indicating the location of an object, the apparatus comprising:

• a resampler which samples an animation path constituted by key data and key value data into a predetermined number of sections having an interval of a predetermined amount of time and outputs a position interpolator including resampled key data and resampled key value data;
• a key data encoder which encodes key data input from the resampler;
• and
• a key value data encoder which encodes key value data input from the resampler,
• wherein the key value data encoder comprises:
• a quantizer which quantizes data input thereinto, with predetermined quantization bits;
• a DPCM processor which obtains differential data and predicted differential data of the quantized data and performs a circular quantization operation on the differential data so as to output differential data having a reduced size;
• and
• an entropy encoder which entropy-encodes the differential data input from the DPCM processor.

An apparatus for decoding a bitstream, into which a position interpolator, including key data indicating the locations of keyframes on a temporal axis and key value data indicating the location of an object, is encoded, the apparatus comprising:

• a key data decoder which decodes key data from an input bitstream;
• a key value data decoder which decodes key value data from the input bitstream;
• and
• a position interpolator synthesizer which generates a position interpolator by synthesizing decoded key value data and key value data linearly interpolated using the decoded key value data.

A method for encoding a position interpolator, which includes key data indicating the locations of keyframes on a temporal axis and key value data indicating the location of an object, the method comprising:

• (b) generating key data and key value data, using a processor, to be encoded by extracting, from a first animation path constituted by the position interpolator, a minimum number of break points, which can bring about an error of no greater than a predetermined allowable error limit between the first animation path and a second animation to be generated by the extracted break points;
• (d) encoding the key data generated in step (b);
• and
• (e) encoding the key value data generated in step (b).

A method for encoding a position interpolator, which includes key data indicating the locations of keyframes on a temporal axis and key value data indicating the location of an object, the method comprising:

• (b) sampling an animation path constituted by the position interpolator into a predetermined number of sections having an interval of a predetermined amount of time and thus generating a position interpolator including resampled key data and resampled key value data;
• (d) encoding the key data generated in step (b);
• and
• (e) encoding the key value data generated in step (b),
• wherein step (e) comprises:
• quantizing the key value data generated in step (b), using predetermined quantization bits;
• obtaining differential data and predicted differential data of quantized data and generating differential data having a reduced size by performing a circular quantization operation on the differential data;
• and
• entropy-encoding the differential data having a reduced size.

A method for decoding a bitstream, into which a position interpolator, including key data indicating the locations of keyframes on a temporal axis and key value data indicating the location of an object, is encoded, the method comprising:

• (a) decoding key data from an input bitstream;
• (b) decoding key value data from the input bitstream;
• and
• (c) generating a position interpolator by synthesizing decoded key value data and key value data linearly interpolated using the decoded key value data with decoded key data.

A method of calculating an error between a first path constituted by a plurality of first path points each consisting of a plurality of data components and a second path constituted by a plurality of second path points each consisting of a plurality of data components, the method comprising:

• (a) interpolating path points, using a processor, into the first and second animation paths so that the first and second animation paths have the same path points in terms of reference data component included in each of the path points;
• (b) dividing each of the first and second paths into a predetermined number of sections in consideration of the reference data component so that the predetermined number of sections respectively correspond to the path points;
• (c) calculating an error between the first and second animation paths in each of the sections;
• and
• (d) checking if step (c) has been performed on all the predetermined number of sections and then normalizing the errors obtained in step (c).

A method of extracting break points from a path constituted by path points including a plurality of component data by using linear approximation, the method comprising:

• (a) extracting a beginning point and an ending point of an original path;
• (b) selecting one out of non-extracted path points and linearly interpolating the other non-selected path points using the selected path point and extracted path points;
• (c) calculating an error, using a processor, between the original path and an interpolated animation path generated using the interpolated path points;
• (d) performing steps (b) and (c) on all the non-selected path points and extracting a path point leading to a minimum error between the original animation path and the interpolated path;
• and
• (e) comparing an error between the original path and a path generated using all the extracted path points including the path points extracted in step (d) with a predetermined allowable error limit, and then repeatedly performing steps (b) through (d).

A method of extracting break points from an animation path constituted by path points including the locations of a plurality of keyframes on a temporal axis and the location of an object in each of the keyframes by using linear approximation, the method comprising:

• (a) extracting a keyframe corresponding to a beginning point and an ending point of an original animation path;
• (b) selecting one out of non-extracted keyframes and linearly interpolating other keyframes using the selected keyframe and extracted keyframes;
• (c) calculating an error, using a processor, between the original animation path and an interpolated animation path generated using the interpolated keyframes;
• (d) performing steps (b) and (c) on all the non-selected keyframes and then extracting a keyframe leading to a minimum error between the original animation path and the interpolated animation path;
• and
• (e) comparing an error between the original animation path and an animation path generated using path points corresponding to the keyframes selected in step (d) with a predetermined allowable error limit and then repeatedly performing steps (b) through (d).

A bitstream embodied in a tangible computer readable media, into which a position interpolator, including key data indicating the locations of keyframes on a temporal axis and key value data indicating the location of an object, is encoded, the bitstream comprising:

• key data encoding/decoding information necessary to encode/decode key data;
• and
• key value data encoding/decoding information necessary to encode/decode key value data,
• wherein the key data encoding/decoding information comprises:
• inverse DND operation information comprising the order of inverse DND indicating a predetermined number of cycles of inverse DND to be performed on differential data generated by entropy-decoding the bitstream in order to extend the range of the differential data and maximum and minimum values among differential data used in each cycle of inverse DND operation;
• first inverse DPCM operation information comprising the order of inverse DPCM operation to be performed on the inverse-DNDed differential data so as to convert the inverse-DNDed differential data into quantized key data and intra key data which are used for each cycle of inverse DPCM operation;
• and
• first inverse quantization information used in inverse quantization to generate retrieved key data by inverse-quantizing the quantized key data, and
• the key value data encoding/decoding information comprises:
• entropy-decoding information comprising a flag indicating an entropy-decoding operation to be performed to generate second differential data by entropy-decoding key value data from the bitstream;
• second inverse DPCM operation information comprising information on an inverse DPCM operation to be performed on the differential data so as to convert the second differential data into quantized key value data and intra key value data in each cycle of inverse DPCM operation;
• second inverse quantization information comprising a predetermined number of inverse quantization bits used to retrieve original key value data by inverse-quantizing the quantized key value data;
• and
• inverse normalization information used to inversely normalize the retrieved key value data which are retrieved by inverse quantization using the inverse quantization bits, the inverse normalization information comprising a flag indicating a component having a maximum key value data range, a maximum value in the maximum key value data range, and minimum values among the key value data of each of the components.

A method of decoding a bitstream into which a position interpolator is encoded, the position interpolator comprising a key header containing information regarding key data, a key value header containing information regarding key value data, a plurality of key selection flags indicating whether corresponding respective keyframes are chosen, key data indicating the locations of the keyframes on a temporal axis, and key value data indicating the location of an object on each of the keyframes, the method comprising:

• reading the key header and the key value header and decoding a number of key selection flags keyFlag corresponding to a number indicated by key data number information nNumberOfKey included in the key header if a preserve key bit bPreserveKey included in the key value header is set to 1;
• decoding the key data with reference to the key header;
• and
• reading the key value data and decoding the key value data with reference to the key selection flag and the key value header, the key value header comprising information specifying the orders of inverse normalization, inverse quantization, and inverse circular differential pulse code modulation (DPCM), and entropy decoder type information specifying the type of an entropy decoder needed to be used decode the key value data.

A method of encoding a position interpolator into a bitstream, the position interpolator comprising a key header containing information regarding key data, a key value header containing information regarding key value data, a plurality of key selection flags indicating whether corresponding respective keyframes are chosen, key data indicating the locations of the keyframes on a temporal axis, and key value data indicating the location of an object on each of the keyframes, the method comprising:

• generating a key header, using a processor, comprising a preserve key bit and keyframe number information numberOfkey indicating a total number of keyframes;
• generating a key value header;
• generating a key selection flag with reference to the preserve key bit and the keyframe number information numberOfkey included in the key header;
• generating key data with reference to the key header and encoding the key data;
• and
• generating key value data with reference to the key selection flag and the key value header and encoding the key value data with reference to the key value header, the key value header comprising information specifying the orders of normalization, quantization, and DPCM and entropy encoder type information specifying the type of an entropy encoder used to encode the key value data.