1. Field of the Invention
The present invention relates to a method and an apparatus for encoding and decoding three-dimensional animation data, and more particularly, to a method and an apparatus for encoding and decoding an orientation interpolator representing information on the rotation of an object in animation.
2. Description of the Related Art
MPEG-4 BIFS, which is one of the international multimedia standards, supports a keyframe-based animation using an interpolator node having keys and key values of an animation.
In order to represent animation as naturally and smoothly as possible using such a keyframe-based animation technique, a considerable number of keys and a considerable amount of key value data are required, and field data between key frames are filled in by interpolation. Interpolation in a virtual reality modeling language (VRML) involves linear or spherical interpolation.
Keys and key values approximate an original animation curve on a temporal axis. FIG. 1 is a diagram illustrating two-dimensional trajectories of animation data, represented by an orientation interpolator node, in accordance with the passage of time on the surface of a three-dimensional sphere. As shown in FIG. 1, the conventional MPEG-4 BIFS supports spherical linear interpolation between keyframes, and an animation path looks similar to a set of segments representing the variation of the animation data.
In an orientation interpolator node provided by BIFS, key data indicate a predetermined moment of time on a temporal axis where an animation is located using discontinuous numbers between −∞ and ∞. Key value data represent information on the rotation of an object in a synthetic image at a predetermined moment of time indicated by key data. Information on the rotation of the object at another predetermined moment of time, which is not represented by key data, is obtained using key data corresponding to two moments of time, which are most adjacent to the predetermined moment of time, by spherical linear interpolation.
In spherical linear interpolation, rotation information is represented by a rotation axis and a rotation angle. MPEG-4 BIFS, like virtual reality modeling language (VRML), supports rotation information represented by a rotation axis and a rotation angle using an orientation interpolator node. When generating a smooth animation using key value data in spherical linear interpolation, differential values of key value data between keyframes are highly correlated with each other, which causes redundancy among data. Accordingly, it is effective to use a method for encoding key value data using differential values of data.
MPEG-4 BIFS provides two different methods for encoding field data represented by keys and key value data of an orientation interpolator node. One is a method for encoding field data using pulse code modulation (PCM) and the other is a method for encoding field data using differential pulse code modulation (DPCM) and entropy encoding.
In the method for encoding field data using PCM, only a quantization process is performed on key data and key value data to be encoded. Since the characteristics of data to be encoded are not considered in this method, this method is considered ineffective. In the method for encoding field data using PCM, field data of an orientation interpolator node are input, and key value data of the field data are converted into values in a quaternion space. Next, keys and key value data are quantized. Quantized field data are output in the form of binary data. In order to measure the degree to which the results of quaternion transformation are visually distorted as compared with original field data, the binary data are restored into key value data consisting of a rotation axis and a rotation angle. Restored field data of an orientation interpolator node are stored and then are output on a screen. It is possible to measure the degree of visual distortion of images caused by a quaternion error using the restored data. Distortion of images can be calculated with Equation (1) below.
                    D        =                                                            (                                                                            ∑                                              i                        =                        0                                                                    i                        <                        N                                                              ⁢                                                                                  ⁢                                          ɛ                      i                                                        N                                )                            2                                =                                                    (                                                                                                    ∑                                                  i                          =                          0                                                                          i                          <                          N                                                                    ⁢                                                                                          ⁢                                              Q                        i                                                              -                                                                  Q                        ^                                            i                                                        N                                )                            2                                                          (        1        )            
In Equation (1), N represents the number of field data, and εi represents a differential value between encoded key value data Qi and key value data {circumflex over (Q)}i restored in a quaternion space.
On the other hand, in the method for encoding field data using DPCM and entropy encoding, a correlation between successive data is considered, and thus this method is considered more effective than the method for encoding field data using PCM in terms of encoding efficiency. In this method, a differential value between previously restored key value data and key value data to be encoded is calculated before a quantization process, and then the differential value is quantized, thus enhancing the encoding efficiency by taking advantage of the characteristics of data shown in the differential value.
FIGS. 2A and 2B are block diagrams of a MPEG-4 PMFC encoder using linear DPCM and entropy encoding, and a MPEG-4 PMFC decoder using inverse linear DPCM and entropy decoding, respectively. A linear DPCM operator shown in FIG. 2A calculates differential data {dot over (Q)}i between current key value data and previously restored key value data following Equation (2).{dot over (Q)}i=Qi{circumflex over (Q)}i−1=(qi,0−{circumflex over (q)}i−1,0,qi,1−{circumflex over (q)}i−1,1,qi,2−{circumflex over (q)}i−2,2,qi,3−{circumflex over (q)}i−1,3)  (2)
In Equation (2), Qi represents original key value data at a predetermined moment of time (t), which are represented by a quaternion, and {circumflex over (Q)}i−1 represents key value data at a predetermined moment of time (t−1), which are restored from an error compensation circuit.
However, the encoding method performed in the apparatus for encoding key value data shown in FIG. 2A does not have a high encoding efficiency. It is possible to easily figure out what the disadvantages of the encoding method are by analyzing key value data, which determine the rotation of an object in a quaternion space. Key value data are represented by a quaternion in the following equation.
                    Q        =                  (                                    cos              ⁢                              θ                2                                      ,                                                            n                  x                                                                    n                                                              ⁢              sin              ⁢                              θ                2                                      ,                                                            n                  y                                                                    n                                                              ⁢              sin              ⁢                              θ                2                                      ,                                                            n                  z                                                                    n                                                              ⁢              sin              ⁢                              θ                2                                              )                                    (        3        )            
For example, when components of one quaternion have the same absolute values as their corresponding components of another quaternion but different signs in a quaternion space, as shown in Equation (3), the two quaternions are considered the same. In other words, the two quaternions provide the same effects in terms of the rotational transformation of an object in a 3D space, which means the factors that affect the rotational transformation of an object are a direction of a rotation axis and a rotation angle, rather than the vector of the rotation axis. However, like in MPEG-4 BIFS, if key value data are represented by a quaternion using Equation (3) and a differential value is linearly calculated by calculating differences in vectors between successive key value data, the differential value is not 0, which means that linear differential values do not reflect redundancy in rotational transformation well. Accordingly, it is impossible to precisely measure the quality of images using the method for measuring the distortion degree of images shown in Equation (1).