Method and apparatus for encoding and decoding data
Abstract
This record has no abstract on file.
Term
Term ended
Expired 27 November 2022, 3.8 years ago.
- Priority
- Filed
- Granted
- Expired
- Today
8 claims: 3 independent, 5 dependent
- 1An apparatus for encoding data, comprising:a quantizer (310) which is arranged to quantize data input thereinto into predetermined quantization bits;a quantization error minimizer (320) which is arranged to receive the input data and the quantized data, and to output maximum and minimum values for decoding the quantized data such that a quantization error of the quantized data is minimal;a DPCM operator (340) which is arranged to generate differential data by performing a DPCM operation on the quantized data;an entropy encoder (350) which is arranged to entropy-encode the differential data input from the DPCM operator and to output the entropy-encoded differential data into a bitstream;and a header encoder (370) which is arranged to encode the maximum and minimum values to be included in the bitstream;characterised in that the quantization error minimizer comprises: an initial value setting unit (321) which is arranged to receive the input data and the quantized data, to set up an initial value of a minimum error value e min by calculating the quantization error, to calculate the decimal digit number of the minimum value among the input data and to set up an adjusted minimum value min' and an initial value of a quantization error minimizing value min min ;an adjusted minimum value renewing unit (323) which is arranged to renew the adjusted minimum value min' by performing a predetermined operation on the adjusted minimum value min';a determining unit (325) which is arranged to determine whether the quantization error minimizing value min min is a minimum value to be used for inverse quantization depending on the value and decimal digit number of the renewed adjusted minimum value;and an error value renewing unit (327) which is arranged to calculate a quantization error value based on the renewed adjusted minimum value, to assign the adjusted minimum value to the quantization error minimizing value min min and the calculated quantization error value to the minimum error value e min if the calculated quantization error value is smaller than the minimum error value e min , and to output the minimum error value e min to the adjusted minimum value renewing unit.
- 4A method for encoding data, comprising:(a) quantizing input data with predetermined quantization bits;(b) generating differential data by performing a DPCM operation on the quantized data;(c) generating a bitstream by entropy-encoding the differential data generated in step (b);(d) outputting maximum and minimum values for decoding the quantized data such that a quantization error of the quantized data is minimal;and (e) encoding the maximum and minimum values to be included in the bitstream. characterised in that step (d) comprises: (d1) setting up (S404) an initial value of a minimum error value e min by calculating the quantization error using the input data and the quantized data, calculating the decimal digit number of the minimum value among the input data, and setting up (S406) an adjusted minimum value min' and an initial value of a data error minimizing value min min ;(d2) renewing (S408) the adjusted minimum value min' by performing a predetermined operation on the adjusted minimum value min';(d3) determining (S410) whether the quantization error minimizing value min min is a minimum value to be used for inverse quantization depending on the value and decimal digit number of the renewed adjusted minimum value;and (d4) calculating (S414) a quantization error value based on the renewed adjusted minimum value if the quantization error minimum value min min has not been determined as the minimum value to be used for inverse quantization in step (d3), assigning (S418) the adjusted minimum value to the quantization error minimizing value min min and assigning the calculated quantization error to the minimum error value if the calculated quantization error value is smaller than the minimum error value e min , and moving on to step (d2).
Independent claims3
205 paragraphs, as filed
0001The present invention relates to an apparatus and a method for encoding data.
0002<figref idref="f0001">FIG. 1</figref> is a block diagram showing the structures of a conventional apparatus for encoding data and a conventional apparatus for decoding data. Referring to <figref idref="f0001">FIG. 1</figref>, a conventional apparatus for encoding data includes a quantizer 100, a DPCM operator 110, and an entropy decoder 120. According to a conventional method for encoding data, input data are quantized with a predetermined number of bits in the quantizer 100 and are input into the DPCM operator 110. The DPCM operator 110 generates differential data by subtracting the current quantized data input from the quantizer 100 from previous quantized data and outputs the differential data to the entropy decoder 120. The entropy decoder 120 encodes the differential data into a bitstream using a predetermined entropy-encoding method.
0003Referring to <figref idref="f0001">FIG. 1</figref>, a conventional apparatus for decoding data includes an entropy decoder 130, an inverse DPCM operator 140, and an inverse quantizer 150. A bitstream, into which data are encoded, is input into the entropy decoder 130. The entropy decoder 130 outputs differential data inversely performing the process performed by the entropy encoder, and then the inverse DPCM operator 140 converts the differential data input from the entropy decoder 130 into quantized data and outputs the quantized data to the inverse quantizer 150. The inverse quantizer 150 inversely quantizes the quantized data input from the inverse DPCM operator 140 and then outputs decoded data.
0004However, since the aforementioned conventional method for encoding data only performs a simple DPCM operation so as to reduce the amount of data to be encoded and encodes data having a plurality of components without considering the characteristics of each of the x, y, and z components of the data, especially when the data are consecutively input, its encoding efficiency is not high enough.
0005In an aspect of the present invention to provide a method according to claim 4 and an apparatus according to claim 1 for encoding and decoding data, which can minimize a quantization error generated during a quantization process and can encode the sign of data.
0006The above objects and advantages of the present invention will become more apparent by describing in detail preferred embodiments thereof with reference to the attached drawings in which: <ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">FIG. 1</figref> is a block diagram showing the structures of a conventional apparatus for encoding data and a conventional apparatus for decoding data;</li><li><figref idref="f0002">FIG. 2A</figref> is a block diagram of an apparatus for performing a DPCM operation according to a preferred embodiment of the application from which the present application corresponds, and <figref idref="f0003">FIG. 2B</figref> is a flowchart of a DPCM operation;</li><li><figref idref="f0003">FIG. 3A</figref> is a block diagram of an apparatus for encoding data using a DPCM operator corresponding to <figref idref="f0002">Figure 2A</figref>, and <figref idref="f0004">FIG. 3B</figref> is a corresponding flowchart;</li><li><figref idref="f0005">FIG. 4A</figref> is a block diagram of an apparatus for encoding data according to a preferred embodiment of the present invention, which can minimize a quantization error, and <figref idref="f0006">FIG. 4B</figref> is a flowchart of a method of minimizing a quantization error;</li><li><figref idref="f0007">FIG. 5A</figref> is a block diagram of an apparatus for encoding data, which normalizes input data having a plurality of components and then encodes the normalized data, and <figref idref="f0008">FIG. 5B</figref> is a flowchart of a method of normalizing data;</li><li><figref idref="f0009">FIG. 6A</figref> is a block diagram of an apparatus for encoding data which encodes key value data of a position interpolator according to a preferred embodiment of the present invention, and <figref idref="f0010">FIG. 6B</figref> is a flowchart of a method of encoding key value data;</li><li><figref idref="f0011">FIGS. 7A</figref> and <figref idref="f0012">7B</figref> are flowcharts of the operation of a floating-point number encoder shown in <figref idref="f0009">FIG. 6A</figref>;</li><li><figref idref="f0013">FIGS. 7C</figref> and <figref idref="f0014">7D</figref> are flowcharts of the operation of an entropy decoder according to a preferred embodiment of the present invention;</li><li><figref idref="f0015">FIG. 8</figref> is a diagram illustrating step S683 shown in <figref idref="f0013">FIG. 7C</figref>;</li><li><figref idref="f0015">FIGS. 9A</figref> and <figref idref="f0016">9B</figref> are diagrams illustrating the steps shown in <figref idref="f0014">FIG. 7D</figref>;</li><li><figref idref="f0017">FIG. 10A</figref> is a block diagram of an inverse DPCM operator, and <figref idref="f0018">FIG. 10B</figref> is a flowchart of an inverse DPCM operation;</li><li><figref idref="f0018">FIG. 11</figref> is a block diagram of an apparatus for decoding data using an inverse DPCM operator;</li><li><figref idref="f0019">FIG. 12A</figref> is a block diagram of an apparatus for decoding data using an inverse normalizer, and <figref idref="f0020">FIG. 12B</figref> is a flowchart of the operation of an inverse normalizer;</li><li><figref idref="f0021">FIG. 13A</figref> is a block diagram of an apparatus for decoding key value data, and <figref idref="f0022">FIG. 13B</figref> is a flowchart of a method for decoding key value data;</li><li><figref idref="f0023">FIG. 14A</figref> is a detailed flowchart of step S1320 shown in <figref idref="f0022">FIG. 13B</figref>;</li><li><figref idref="f0024">FIG. 14B</figref> is a detailed flowchart of step S1330 shown in <figref idref="f0023">FIG. 14A</figref>;</li><li><figref idref="f0025">FIG. 14C</figref> is a detailed flowchart of step S1380 shown in <figref idref="f0022">FIG. 13B</figref>;</li><li><figref idref="f0026">FIG. 15</figref> is a diagram illustrating the order of components of a bitstream which is input into an entropy decoder;</li><li><figref idref="f0026">FIGS. 16A</figref> and <figref idref="f0027">16B</figref> are graphs illustrating the results of a predictive DPCM operation;</li><li><figref idref="f0027 f0028">FIGS. 17A through 17C</figref> are graphs illustrating the results of a circular-DPCM operation;</li><li><figref idref="f0029">FIGS. 18A and 18B</figref> are graphs illustrating keys of a position interpolator and key value data; and</li><li><figref idref="f0030 f0031 f0032 f0033 f0034 f0035 f0036 f0037">FIGS. 19 through 27</figref> are diagrams showing examples of program codes by which a process of reading a bitstream in a method for decoding data is realized.</li></ul>
0007Hereinafter, the present invention will now be described more fully with reference to the accompanying drawings.
0008<figref idref="f0002">FIG. 2A</figref> is a block diagram of an apparatus for performing a DPCM operation, and <figref idref="f0003">FIG. 2B</figref> is a flowchart of a DPCM operation.
0009Referring to <figref idref="f0002">FIG. 2A</figref>, an apparatus for performing a DPCM operation includes a circular DPCM operator 200, which includes a DPCM operator 210 performing a general DPCM operation and then outputting differential data and a circular quantization operator 220 performing a circular quantization operation on differential data input thereinto so as to reduce their range, a predictive-circular DPCM operator 230, which includes a predictive DPCM operator performing a predictive DPCM operation on quantized data input thereinto and then outputting predicted differential data and a circular quantizer 250 performing a circular quantization operation on differential data input thereinto so as to reduce their range, and a selector 260, which selects one from between the differential data input from the circular DPCM operator 200 and the differential data input from the predictive-circular DPCM operator 230 based on the value of the differential data input thereinto.
0010Referring to <figref idref="f0003">FIG. 2B</figref>, a DPCM operation will be described in the following.
0011Data, which are quantized following an arbitrary quantization method, are input into the circular DPCM operator 200 and the predictive-circular DPCM operator 230 in step S210.
0012In the circular DPCM operator 200, the DPCM operator 210 generates differential data by performing a general DPCM operation on the quantized data input thereinto and outputs the generated differential data to the circular quantizer 220. The circular quantizer 220, then, performs a circular quantization on the differential data input from the DPCM operator 210 in step S220a.
0013In particular, the DPCM operator 210 calculates the differential data by subtracting previous quantized data from the current quantized data input in step S210. Thereafter, the circular quantizer 220 performs circular quantization on the calculated differential data. The operation of the circular DPCM operator 200 is expressed by the following equation.<maths id="math0001" num="(1)"><math display="block"><msub><mover><mi>P</mi><mo>^</mo></mover><mi>i</mi></msub><mo>=</mo><mi mathvariant="italic">CircularQuantization</mi><mo></mo><mfenced separators=""><msub><mover><mi>P</mi><mo>˜</mo></mover><mi>i</mi></msub><mo>-</mo><msub><mover><mi>P</mi><mo>˜</mo></mover><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msub></mfenced><mspace width="2em" /><mfenced separators=""><mi>i</mi><mo>=</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>n</mi></mfenced></math><img file="EP1565000B1_D0001.tif" /></maths>
0014In Equation (1), n represents the number of data. The circular quantization will be described later.
0015The predictive DPCM operator 240 in the predictive-circular DPCM operator 230 calculates predicted differential data by performing a predictive DPCM operation on differential data input thereinto, and then the circular quantizer 250 performs a circular quantization on the predicted differential data in step S220b.
0016In particular, the predictive DPCM operator 240 generates the predicted differential data by subtracting predicted data from current quantized data and outputs them. In order to obtain the predicted data for the current quantized data, differential values are obtained by subtracting from previous quantized data quantized data prior to the previous quantized data and then are added to previous differential data so that the predicted data for the current data are calculated.
0017The predicted data calculated by the predictive DPCM operator 240 may not be beyond a maximum range of quantized data input thereinto. In other words, if the predicted data exceed a maximum value in a quantization range of the input quantized data, the predictive DPCM operator 240 sets up the predicted data as a maximum value in a quantization range of the input quantized data and generates differential data for current data by subtracting the current data from the predicted data. If the predicted data are smaller than a minimum value in the quantization range of the input data, the predictive DPCM operator 240 determines the current data as predicted differential data. Hereinafter, this operation of the predictive DPCM operator 240 will be referred to as a "modified predictive DPCM operation" in the following.
0018The predicted differential data calculated by the predictive DPCM operator 230 are input into the circular quantizer 250 and are subjected to a circular quantization operation.
0019The operation of the predictive-circular DPCM operator 230 may be expressed by the following equation.<maths id="math0002" num="(2)"><math display="block"><mtable columnalign="left"><mtr><mtd><mover><msub><mover><mi>P</mi><mo>˜</mo></mover><mi>i</mi></msub><mo>^</mo></mover><mo>=</mo><mfenced separators=""><msup><mn>2</mn><mi mathvariant="italic">nQuantBit</mi></msup><mo>-</mo><mn>1</mn></mfenced><mo>-</mo><msub><mover><mi>P</mi><mo>˜</mo></mover><mi>i</mi></msub></mtd><mtd><mspace width="1em" /></mtd><mtd><mfenced separators=""><mi mathvariant="italic">if</mi><mspace width="1em" /><mn>2</mn><mo>×</mo><msub><mover><mi>P</mi><mo>˜</mo></mover><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>-</mo><msub><mover><mi>P</mi><mo>˜</mo></mover><mrow><mi>i</mi><mo>-</mo><mn>2</mn></mrow></msub><mo>></mo><msup><mn>2</mn><mi mathvariant="italic">nQuantBit</mi></msup><mo>-</mo><mn>1</mn></mfenced></mtd></mtr><mtr><mtd><mover><msub><mover><mi>P</mi><mo>˜</mo></mover><mi>i</mi></msub><mo>^</mo></mover><mo>=</mo><msub><mover><mi>P</mi><mo>˜</mo></mover><mi>i</mi></msub></mtd><mtd><mspace width="1em" /></mtd><mtd><mfenced separators=""><mi mathvariant="italic">if</mi><mspace width="1em" /><mn>2</mn><mo>×</mo><msub><mover><mi>P</mi><mo>˜</mo></mover><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>-</mo><msub><mover><mi>P</mi><mo>˜</mo></mover><mrow><mi>i</mi><mo>-</mo><mn>2</mn></mrow></msub><mo><</mo><mn>0</mn></mfenced></mtd></mtr><mtr><mtd><mover><msub><mover><mi>P</mi><mo>˜</mo></mover><mi>i</mi></msub><mo>^</mo></mover><mo>=</mo><msub><mover><mi>P</mi><mo>˜</mo></mover><mi>i</mi></msub><mo>-</mo><mfenced separators=""><mn>2</mn><mo>×</mo><msub><mover><mi>P</mi><mo>˜</mo></mover><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>-</mo><msub><mover><mi>P</mi><mo>˜</mo></mover><mrow><mi>i</mi><mo>-</mo><mn>2</mn></mrow></msub></mfenced></mtd><mtd><mspace width="1em" /></mtd><mtd><mfenced><mi mathvariant="italic">otherwise</mi></mfenced></mtd></mtr><mtr><mtd><msub><mover><mi>P</mi><mo>^</mo></mover><mi>i</mi></msub><mo>=</mo><mi mathvariant="italic">CircularQuantization</mi><mfenced><mover><msub><mover><mi>P</mi><mo>˜</mo></mover><mi>i</mi></msub><mo>^</mo></mover></mfenced></mtd><mtd><mspace width="1em" /></mtd><mtd><mspace width="1em" /></mtd></mtr></mtable><mspace width="1em" /></math><img file="EP1565000B1_D0002.tif" /></maths>
0020In Equation (2), i is an integer between 2 and n - 1, and n indicates the number of data.
0021<figref idref="f0026">FIG. 16A</figref> shows the results of performing a simple predictive DPCM operation on 50 quantized data having a maximum value of 1024 and a minimum value of 0, and <figref idref="f0027">FIG. 16B</figref> shows the results of performing a modified predictive DPCM operation on the same data as in the case of <figref idref="f0026">FIG. 16A</figref> so that differential data for the data are adjusted following Equation (2), in a case where predicted data values for the data are beyond the maximum value or below the minimum value among the data.
0022As a result of the simple predictive DPCM operation, predicted differential data have as wide a range as about 3,000, as shown in <figref idref="f0026">FIG. 16A</figref>. As a result of the modified predictive DPCM operation, predicted differential data have as narrow a range as no greater than 2,000, as shown in <figref idref="f0027">FIG. 16B</figref>. This means that it is more likely to obtain predicted differential data having a narrower range in the modified predictive DPCM operation than in the simple predicted DPCM operation.
0023Hereinafter, circular quantization will be described in the following.
0024<figref idref="f0027">FIG. 17A</figref> shows quantized data, and <figref idref="f0028">FIG. 17B</figref> shows the results of performing a DPCM operation on the quantized data shown in <figref idref="f0027">FIG. 17A</figref>. As shown in <figref idref="f0028">FIG. 17B</figref>, the range of differential data can be increased after a DPCM operation up to two times as wide as it used to be before the DPCM operation. Accordingly, it is possible to say that a circular quantization operation is employed for making it happen that a DPCM operation is performed while maintaining the range of differential data subjected to the DPCM operation within the range of input data.
0025The circular quantization operation is performed on the assumption that a maximum value and a minimum value in a quantization range are circularly connected to each other. Accordingly, if differential data, which are the results of performing linear DPCM on two consecutive quantized data, are greater than half of the maximum value in the quantization range, their values can be decreased by subtracting the maximum value from each of the differential data.
0026If the differential data are smaller than half of the minimum value in the quantization range, their values can be decreased even more by adding the maximum value in the quantization range to each of the differential data.
0027Supposing that <i>X</i> and <i>X̂</i> indicate input differential data and circularly-quantized differential data, respectively, the circular quantization can be expressed by the following equation.<maths id="math0003" num="(3)"><math display="block"><mtable columnalign="left"><mtr><mtd><mi mathvariant="italic">CircularQuantization</mi><mfenced><msub><mi>X</mi><mi>i</mi></msub></mfenced><mo>=</mo><msub><mover><mi>X</mi><mo>^</mo></mover><mi>i</mi></msub><mo>=</mo><mi mathvariant="italic">Min</mi><mfenced><mfenced open="|" close="|"><msub><mi>X</mi><mi>i</mi></msub></mfenced><mfenced open="|" close="|"><msub><mrow><mi>X</mi><mo></mo><mi>ʹ</mi></mrow><mi>i</mi></msub></mfenced></mfenced></mtd><mtd><mspace width="1em" /></mtd></mtr><mtr><mtd><msub><mrow><mi>X</mi><mo></mo><mi>ʹ</mi></mrow><mi>i</mi></msub><mo>=</mo><msub><mi>X</mi><mi>i</mi></msub><mo>-</mo><mfenced separators=""><msup><mn>2</mn><mi mathvariant="italic">nQBits</mi></msup><mo>-</mo><mn>1</mn></mfenced><mspace width="2em" /><mfenced separators=""><mi mathvariant="italic">if X</mi><mo>≥</mo><mn>0</mn></mfenced></mtd><mtd><mspace width="1em" /></mtd></mtr><mtr><mtd><msub><mrow><mi>X</mi><mo></mo><mi>ʹ</mi></mrow><mi>i</mi></msub><mo>=</mo><msub><mi>X</mi><mi>i</mi></msub><mo>+</mo><mfenced separators=""><msup><mn>2</mn><mi mathvariant="italic">nQBits</mi></msup><mo>-</mo><mn>1</mn></mfenced><mspace width="2em" /><mfenced><mi mathvariant="italic">otherwise</mi></mfenced></mtd><mtd><mspace width="1em" /></mtd></mtr></mtable><mspace width="1em" /></math><img file="EP1565000B1_D0003.tif" /></maths>
0028In Equation (3), nQBits indicates a bit size used for quantization. <figref idref="f0028">FIG. 17C</figref> shows the results of performing the circular quantization on the differential data shown in <figref idref="f0028">FIG. 17B</figref>.
0029Referring to <figref idref="f0003">FIG. 2B</figref> again, circularly-quantized differential data and circular-quantized predicted differential data are output to the selector 260, and then the selector 260 performs a sum-of-absolute-difference (SAD) operation on the input differential data in step S230. Here, the SAD operation is performed so that the absolute values of input data are all added. In step S230, the selector adds all the absolute values of the circular-quantized differential data and adds all the absolute values of the circular-quantized predicted differential data.
0030Thereafter, the selector 260 compares the sum of the absolute values of the quantized differential data and the sum of the absolute values of the predicted differential data, selects differential data having a smaller sum of absolute values from between the quantized differential data and the predicted differential data, and outputs the selected differential data in step S240. The reason why the selector 260 selects differential data having a smaller sum of absolute values is that they supposedly have a narrower range of values. For example, in entropy-encoding predicted differential data, the number of bits required for encoding differential data having a smaller sum of absolute values is expected to be smaller than the number of bits required for encoding differential data having a larger sum of absolute values.
0031It is obvious to one skilled in the art that the SAD operation is merely one of the methods for selecting a certain group of differential data, and thus the selector 260 may adopt a different method to select differential data.
0032<figref idref="f0003">FIG. 3A</figref> is a block diagram of an apparatus for encoding data, and <figref idref="f0004">FIG. 3B</figref> is a flowchart illustrating the operation of the apparatus for encoding data. The apparatus for encoding data includes the aforementioned DPCM operator.
0033The apparatus for encoding data shown in <figref idref="f0003">FIG. 3A</figref> includes a quantizer 310 which quantizes input data with a predetermined quantization bit, a DPCM processor 340 which performs a circular DPCM operation and a predictive DPCM operation on the quantized data and then outputs differential data, and an entropy encoder 350 which performs a predetermined entropy-encoding operation on the differential data input from the DPCM processor 340 and then outputs a bitstream. The DPCM processor 340 comprises the aforementioned DPCM operator of the present invention.
0034Referring to <figref idref="f0003">FIGS. 3A</figref> and <figref idref="f0004">3B</figref>, data to be encoded are input into the apparatus for encoding data in step S310, and are quantized with a predetermined number of quantization bits in the quantizer 310 and output to the DPCM processor 340 in step S320.
0035The circular DPCM operator 200 in the DPCM processor 340 performs a DPCM operation and a circular quantization operation on the quantized data input from the quantizer 310 and then outputs the results to the selector 260. In addition, the predictive-circular DPCM operator performs a predictive DPCM operation and circular quantization on the quantized data input from the quantizer 310 in step S330.
0036The selector 260 performs an SAD operation on the differential data input from the circular DPCM operator 200 and the differential data input from the predictive-circular DPCM operator 230, selects differential data to be output to the entropy decoder 350, and outputs the selected differential data in step S340.
0037The entropy encoder 350 performs a predetermined entropy-encoding operation on the differential data input from the selector 260 so that they are entropy-encoded and a bitstream is generated in step S350.
0038An apparatus for encoding data according to an embodiment of the present invention includes a maximum value and a minimum value used for minimizing a quantization error in a bitstream and encodes the bitstream so that a quantization error can be minimized when decoding encoded data.
0039Referring to <figref idref="f0005">FIG. 4A</figref>, an apparatus for encoding data according to a preferred embodiment of the present invention includes a quantizer 310, a DPCM operator 110/340, an entropy encoder 350, a quantization error minimizer 320 which receives data and quantized data, adjusts a maximum value and a minimum value among the data so that the quantization error can be minimized, and outputs the adjusted maximum and minimum values, and a header encoder 370 which encodes the maximum and minimum values input from the quantization error minimizer 320 into header information and lets the information included in a bitstream.
0040The quantization error minimizer 320 includes an initial value setting unit 321 which sets a minimum error value e<sub>min</sub>, an adjusted minimum value min', and a quantization error minimizing value min<sub>min</sub>, an adjusted minimum value renewing unit 323 which renews the adjusted minimum value min' by performing a predetermined operation, a determining unit 325 which determines the quantization error minimum value min<sub>min</sub> as a minimum value to be used for inverse quantization based on the digit number and value of the renewed adjusted minimum value, an error value renewing unit 327 which calculates a quantization error value using the renewed adjusted minimum value, renews the adjusted minimum value min' and the calculated error value into the quantization error minimum value min<sub>min</sub> and the minimum error value e<sub>min</sub>, respectively, if the calculated error value is smaller than the minimum error value e<sub>min</sub>, and outputs the results of the renewal to the adjusted minimum value renewing unit 323.
0041The quantization error minimizer 320 controls a quantization range so as to minimize a quantization error by performing quantization and inverse quantization on input data.
0042In particular, when Max represents a fixed maximum value to be used for quantization, Min represents an adjusted minimum value to be used for quantization, X<sub>i</sub> represents an input value, and nQuanBit represents the number of bits used for quantization, a quantized input value <i>X̃<sub>i</sub></i>, an inversely quantized value <i>X̃<sub>i</sub></i>, and an error e<sub>i</sub> are calculated following Equation (4).<maths id="math0004" num="(4)"><math display="block"><mtable columnalign="left"><mtr><mtd><msub><mover><mrow><mi>X</mi></mrow><mo>˜</mo></mover><mi>i</mi></msub><mo>=</mo><mi mathvariant="italic">floor</mi><mo></mo><mfenced separators=""><mfrac><mrow><msub><mi>X</mi><mi>i</mi></msub><mo>-</mo><mi mathvariant="italic">Min</mi></mrow><mrow><mi mathvariant="italic">Max</mi><mo>-</mo><mi mathvariant="italic">Min</mi></mrow></mfrac><mo>*</mo><mfenced separators=""><msup><mn>2</mn><mi mathvariant="italic">nQuantBit</mi></msup><mo>-</mo><mn>1</mn></mfenced><mo>+</mo><mn>0.5</mn></mfenced></mtd></mtr><mtr><mtd><msub><mover><mrow><mi>X</mi></mrow><mo>˜</mo></mover><mi>i</mi></msub><mo>=</mo><mfrac><mrow><msub><mover><mi>X</mi><mo>˜</mo></mover><mi>i</mi></msub><mo>*</mo><mfenced separators=""><mi mathvariant="italic">Max</mi><mo>-</mo><mi mathvariant="italic">Min</mi></mfenced></mrow><mrow><msup><mn>2</mn><mi mathvariant="italic">nQuantBit</mi></msup><mo>-</mo><mn>1</mn></mrow></mfrac><mo>+</mo><mi mathvariant="italic">Min</mi></mtd></mtr><mtr><mtd><msub><mi>e</mi><mi>i</mi></msub><mo>=</mo><msub><mrow><mi>X</mi></mrow><mi>i</mi></msub><mo>-</mo><msub><mover><mrow><mi>X</mi></mrow><mo>^</mo></mover><mi>i</mi></msub></mtd></mtr></mtable></math><img file="EP1565000B1_D0004.tif" /></maths>
0043In order to reduce the sum Σ<i>e<sub>i</sub></i> of errors, the quantization error minimizer 320 controls Min so that the sum Σ<i>e<sub>i</sub></i> of errors can be minimized and decodes quantized data using a minimum value which can minimize a quantization error in decoding data.
0044The quantizer 310, the DPCM operator 110/340, and the entropy encoder 350 are almost the same as the corresponding elements of the aforementioned apparatus for encoding data, and thus their detailed description will not be repeated here. Hereinafter, the operation of the quantization error minimizer 320 will be described more fully with reference to <figref idref="f0006">FIG. 4B</figref>.
0045The initial value setting unit 321 receives the same data as data input into the quantizer 310 as well as quantized data output from the quantizer 310 in step S402.
0046The initial value setting unit 321 obtains a maximum value max and a minimum value min from among the input data and calculates the digit number of the minimum value min. Next, the initial value setting unit 321 calculates a quantization error e by inversely quantizing the quantized data using the maximum value max and the minimum value min and sets the quantization error e as an initial minimum error value e<sub>min</sub> in step S404.
0047The initial value setting unit 321 subtracts the result of dividing a quantization step size QuantSpace by 2 from the minimum value min among the input data and sets the result of the subtraction as an initial adjusted minimum value min'. Then, the initial value setting unit 321 sets the initial adjusted minimum value min' as a quantization error minimum value min<sub>min</sub> and outputs the adjusted minimum value min' to the adjusted minimum value renewing unit323 in step S406.
0048The adjusted minimum value renewing unit 323 renews the adjusted minimum value min' input from the initial value setting unit 321 by performing a predetermined operation. According to a preferred embodiment of the present invention, the adjusted minimum value renewing unit 323 renews the adjusted minimum value min' input from the initial value setting unit 321 following Equation (5) and outputs the renewed adjusted minimum value min' to the determining unit 325 in step S408. <maths id="math0005" num="(5)"><math display="block"><mi>minʹ</mi><mo>=</mo><mfrac><mrow><mi mathvariant="italic">Mantissa</mi><mfenced><mi>minʹ</mi></mfenced><mo>+</mo><mn>1</mn></mrow><msup><mn>10</mn><mrow><mi mathvariant="italic">Exponent</mi><mfenced><mi>minʹ</mi></mfenced></mrow></msup></mfrac></math><img file="EP1565000B1_D0005.tif" /></maths>
0049The determining unit 325 calculates the digit number of the renewed adjusted minimum value min', compares the result of the calculation with the digit number of the minimum value min among the input data, which is calculated by the initial value setting unit 321, and compares the renewed adjusted minimum value min' with the result of adding the minimum value min among the input data to the result of dividing the quantization step size QuantSpace by 2, in step S410.
0050If the digit number of the renewed adjusted minimum value min' is greater than the digit number of the minimum value min among the input data, or if the renewed adjusted minimum value min' is greater than <maths id="math0006" num=""><math display="inline"><mi>min</mi><mo>+</mo><mfrac><mi mathvariant="italic">QuantSpace</mi><mn>2</mn></mfrac><mo>,</mo></math><img file="EP1565000B1_D0006.tif" /></maths> the determining unit 325 determines the currently stored quantization error minimizing value min<sub>min</sub> as a minimum value to be used for inverse quantization and outputs the quantization error minimizing value min<sub>min</sub> to the outputting unit 329. If the digit number of the renewed adjusted minimum value min' is not greater than the digit number of the minimum value min among the input data and the renewed adjusted minimum value min' is not greater than <maths id="math0007" num=""><math display="inline"><mi>min</mi><mo>+</mo><mfrac><mi mathvariant="italic">QuantSpace</mi><mn>2</mn></mfrac><mo>,</mo></math><img file="EP1565000B1_D0007.tif" /></maths> the determining unit 325 outputs the renewed adjusted minimum value min' to the error value renewing unit 327.
0051The error value renewing unit 327 inversely quantizes the quantized data using the renewed adjusted minimum value min' and the maximum value max obtained by the initial value setting unit 321 and calculates the quantization error e in step S414.
0052The error value renewing unit 327 compares the newly calculated error value e with the minimum error value e<sub>min</sub> in step S446. As a result of the comparison, if the newly calculated error value e is smaller than the minimum error value e<sub>min</sub>, the error value renewing unit 327 renews the minimum error value e<sub>min</sub> with the newly calculated error value e and renews the quantization error minimum value min<sub>min</sub> with the renewed adjusted minimum value min' in step S418. On the other hand, if the newly calculated error value e is greater than the minimum error value e<sub>min</sub>, the error value renewing unit 327 performs step S408 again without renewing the minimum error value e<sub>min</sub> and the quantization error minimum value min<sub>min</sub>.
0053The maximum and minimum values used for minimizing a quantization error, which are obtained through the above-mentioned processes, are output to the header encoder 370 and are encoded as header information. Then, the header information is included in a bitstream generated by the entropy encoder 350.
0054<figref idref="f0007">FIG. 5A</figref> is a block diagram of an apparatus for encoding data, and <figref idref="f0008">FIG. 5B</figref> is a flowchart of the operation of a normalizer shown in <figref idref="f0007">FIG. 5A</figref>. The apparatus for encoding data increases the efficiency of encoding data by normalizing input data having a plurality of components.
0055As shown in <figref idref="f0007">FIG. 5A</figref>, an apparatus for encoding data includes a normalizer 300 which calculates a maximum range among data ranges of components input into the apparatus for encoding data and normalizes data of each of the x, y, and z components based on the maximum range, a quantizer 310 which quantizes normalized data with a predetermined number of quantization bits, a DPCM operator 110/340 which performs a DPCM operation on quantized data and outputs differential data, and an entropy encoder 350 which entropy-encodes differential data and then outputs an encoded bitstream.
0056The quantizer 310, the DPCM operator 110/340, and the entropy encoder 350 are the same as the corresponding elements of the apparatus for encoding data above, and thus their detailed description will not be repeated here. Only the operation of the normalizer 300 will be described in the following with reference to <figref idref="f0008">FIG. 5B</figref>.
0057In a case where data to be encoded comprises a plurality of components, for example, if input data consists of three components x, y, and z to represent the location of an object in a three-dimensional space, each of the x, y, and z components is input into the normalizer 300 of the apparatus for encoding data. Then, the normalizer 300 calculates a maximum range among the ranges of the x, y, and z components and normalizes data of each of the x, y, and z components based on the maximum range.
0058The normalizer 300 receives data of each component and calculates data ranges of the x, y, and z components following Equation (6) in step S512. Then, the normalizer 300 calculates a maximum range among the data ranges of the x, y, and z components by comparison in step S514. <maths id="math0008" num="(6)"><math display="block"><mtable columnalign="left"><mtr><mtd><msub><mi mathvariant="italic">Max</mi><mi>j</mi></msub><mo>=</mo><msubsup><mi mathvariant="italic">Max</mi><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mi>n</mi></msubsup><mfenced><msub><mover><mi>P</mi><mo>‾</mo></mover><mi mathvariant="italic">ij</mi></msub></mfenced></mtd></mtr><mtr><mtd><msub><mi mathvariant="italic">Min</mi><mi>j</mi></msub><mo>=</mo><msubsup><mi mathvariant="italic">Min</mi><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mi>n</mi></msubsup><mfenced><msub><mover><mi>P</mi><mo>‾</mo></mover><mi mathvariant="italic">ij</mi></msub></mfenced></mtd></mtr><mtr><mtd><msub><mi mathvariant="italic">Range</mi><mi>max</mi></msub><mo>=</mo><mi mathvariant="italic">Max</mi><mo></mo><mfenced separators=""><msub><mi mathvariant="italic">Max</mi><mi>x</mi></msub><mo>-</mo><msub><mi mathvariant="italic">Min</mi><mi>x</mi></msub><mo>,</mo><msub><mi mathvariant="italic">Max</mi><mi>y</mi></msub><mo>-</mo><msub><mi mathvariant="italic">Min</mi><mi>y</mi></msub><mo>,</mo><msub><mi mathvariant="italic">Max</mi><mi>z</mi></msub><mo>-</mo><msub><mi mathvariant="italic">Min</mi><mi>z</mi></msub></mfenced></mtd></mtr></mtable></math><img file="EP1565000B1_D0008.tif" /></maths>
0059Thereafter, the normalizer 300 normalizes the data of each of the x, y, and z components using the following equation in step S516. <maths id="math0009" num="(7)"><math display="block"><msub><mover><mi>P</mi><mi>‿</mi></mover><mi mathvariant="italic">ij</mi></msub><mo>=</mo><mfrac><mrow><msub><mover><mi mathvariant="italic">P</mi><mo>‾</mo></mover><mi mathvariant="italic">ij</mi></msub><mo>-</mo><msub><mi mathvariant="italic">Min</mi><mi mathvariant="italic">j</mi></msub></mrow><msub><mi mathvariant="italic">Range</mi><mi>max</mi></msub></mfrac></math><img file="EP1565000B1_D0009.tif" /></maths>
0060In Equations (6) and (7), n represents the number of data, i = 0, 1, ..., n-1, and j represents each of the components x, y, and z. As shown in Equation (7), the x, y, and z components are normalized using the maximum range Range<sub>max</sub> among their data ranges. As a result of such normalization, the redundancy of data regarding components not having the maximum range Range<sub>max</sub> increases, and accordingly, the efficiency of encoding data also increases.
0061The normalizer 300 normalizes each of the components of the input components and outputs the results of the normalization to the quantizer 310, and then the quantizer 310 quantizes the normalized data input from the normalizer 300 with a predetermined number of quantization bits and outputs the results of the quantization to the DPCM operator 110/340. Thereafter, the DPCM operator 110/340 generates differential data by performing a DPCM operation on the quantized data input from the quantizer 310 and outputs the differential data to the entropy encoder 350 so that they can be encoded.
0062Hereinafter, an apparatus for encoding data according to an embodiment of the present invention, into which the aforementioned DPCM operator, the aforementioned apparatus for encoding data according to the present invention which is capable of minimizing a quantization error, and the aforementioned apparatus for encoding data, which is capable of encoding data having a plurality of components, are integrated, will be described.
0063Even though an apparatus for encoding data according to an embodiment of the present invention will be specifically described as encoding key value data of a position interpolator among three-dimensional animation data in the following, it can also encode other general types of data obviously.
0064A position interpolator is information on the position of a path of an animation in a key frame-based animation which is one of basic techniques of representing a computer-synthesized 3D animation. The key frame-based animation is used for defining the order of animations based on the moment when key data appear. A frame corresponding to the moment when key data appear is called a key frame.
0065In the key frame-based animation, a plurality of key frames and frames among the key frames constitute an animation, and the frames are interpolated among the key frames (or the frames among the key frames are generated using interpolation).
0066International multimedia standards, such as MPEG-4 binary format for scene (BIFS) and virtual reality modeling language (VRML), support a key frame-based animation using an interpolator node. In MPEG-4 BIFS and VRML, there are various kinds of interpolators including a scalar interpolator, a position interpolator, a coordinate interpolator, an orientation interpolator, a normal interpolator, and a color interpolator. These interpolators and their functions and characteristics are shown in Table 1. <tables id="tabl0001" num="0001"><table frame="all"><title>Table 1</title><tgroup cols="3"><colspec colnum="1" colname="col1" colwidth="28mm" /><colspec colnum="2" colname="col2" colwidth="73mm" /><colspec colnum="3" colname="col3" colwidth="65mm" /><thead><row><entry align="center" valign="top">Kind of Interpolator</entry><entry align="center" valign="top">Characteristics</entry><entry align="center" valign="top">Function</entry></row></thead><tbody><row><entry align="center">Scalar interpolator</entry><entry>Linear interpolation of scalar variations</entry><entry>Capable of representing area, diameter, and intensity</entry></row><row><entry align="center">Position interpolator</entry><entry>Linear interpolation on 3D coordinates</entry><entry>Parallel movement in 3D space</entry></row><row><entry align="center">Orientation interpolator</entry><entry>Linear interpolation of 3D coordinate axis and amount of rotation</entry><entry>Rotation in 3D space</entry></row><row><entry align="center">Coordinate interpolator</entry><entry>Linear interpolation of variations in 3D coordinates</entry><entry>3D morphing</entry></row><row><entry align="center">Normal interpolator</entry><entry>Linear interpolation of 3D coordinates of normal</entry><entry>Capable of representing variations in 3D vector of normal</entry></row><row><entry align="center">Color interpolator</entry><entry>Linear interpolation of color information</entry><entry>Capable of representing variations in color</entry></row></tbody></tgroup></table></tables>
0067The position interpolator shown in Table 1 is used to show the position information of a keyframe-based animation and is comprised of keys and key value fields. Key fields represent the position of each key frame on a temporal axis using_ discontinuous numbers in a range between - ∞ and ∞. Each of the key value fields specifies information on the position of an object at a moment represented by each of the keys and includes three components x, y, and z. Each of the key value fields includes as many key values as each of the key fields has.
0068An example of the position interpolator is shown in <figref idref="f0029">FIGS. 18A and 18B</figref>. In particular, <figref idref="f0029">FIG. 18A</figref> shows key data, and <figref idref="f0029">FIG. 18B</figref> shows key value data.
0069Linear interpolation has been employed in MPEG-4 BIFS and VRML. However, in order to represent an animation smoothly and naturally using linear interpolation, a considerable amount of key data and key value data has been required. In addition, in order to store and transmit such an animation, a storage having a large capacity and plenty of time have been required. Accordingly, it is preferable to compress interpolators to store and transmit the interpolators.
0070In MPEG-4 BIFS, a method for encoding and decoding an interpolator node called predictive MF coding (PMFC) has been used. In the PMFC method, like the operation of the conventional apparatus for encoding data shown in <figref idref="f0001">FIG. 1</figref>, key value data of a position interpolator are encoded using a quantizer, a DPCM operator, and an entropy encoder. The quantizer and the DPCM operator reduces redundant key value data, and the output of the DPCM operator is input into the entropy encoder. However, in the PMFC method, differential data obtained by a DPCM operation are entropy-encoded, and thus the encoding efficiency is not high enough. In addition, due to the limits that the entropy encoder has, it is almost impossible to provide an animation of high quality.
0071Accordingly, the present invention provides an apparatus for encoding key values into which the aforementioned DPCM operator according to the present invention, the aforementioned apparatus for encoding data according to the present invention which is capable of minimizing a quantization error, and the aforementioned apparatus for encoding data according to the present invention, which is capable of encoding data having a plurality of components, are integrated, thus increasing the efficiency of encoding key value data
0072<figref idref="f0009">FIG. 6A</figref> is a block diagram of an apparatus for encoding key value data according to an embodiment of the present invention, and <figref idref="f0010">FIG. 6B</figref> is a flowchart of the operation of the apparatus for encoding key value data.
0073Referring to <figref idref="f0009">FIG. 6A</figref>, the apparatus for encoding key value data includes a normalizer 300 which normalizes input key value data of each component based on a maximum range among the data ranges of the x, y, and z components, a quantizer 310 which quantizes normalized key value data with a predetermined quantization bit, a quantization error minimizer 320 which receives the minimum values and the maximum range from the normalizer 300 and adjusts and outputs maximum and minimum values so that a quantization error can be minimized, a floating-point number encoder 330 which receives the minimum values and the maximum range from the quantization error minimizer 320 and converts the maximum range and the minimum values used for minimizing a quantization error into decimal numbers, a DPCM processor 340 which obtains differential data and predicted differential data of quantized key value data and performs a circular quantization operation so as to reduce the range of the differential data, an entropy encoder 350 which entropy-encodes differential data and then outputs a bitstream into which key value data are encoded, and a key value header encoder 360 which encodes information required for decoding a bitstream and allows the information to be included in the bitstream.
0074The operation of the apparatus for encoding key value data according to the present invention will be described with reference to <figref idref="f0010">FIG. 6B</figref>.
0075Key value data of each of the x, y, and z components are input into the normalizer 300 of the apparatus for encoding key value data in step S600. Then, the normalizer 300 calculates a maximum range among the data ranges of the x, y, and z components and normalizes the key value data of the input x, y, and z components based on the maximum range in step S610. The process of normalizing the key value data input into the normalizer 300 has been described above and thus will not be repeated here.
0076The normalized key value data of the x, y, and z components are input into the quantizer 310, and then the quantizer 310 quantizes the normalized key value data with a predetermined number of quantization bits nQuanBit following Equation (8) in step S620.<maths id="math0010" num="(8)"><math display="block"><msub><mover><mi mathvariant="italic">P</mi><mo>˜</mo></mover><mi mathvariant="italic">ij</mi></msub><mo>=</mo><mi mathvariant="italic">foor</mi><mo></mo><mfenced separators=""><msub><mover><mi mathvariant="italic">P</mi><mo>‾</mo></mover><mi mathvariant="italic">ij</mi></msub><mo>×</mo><mfenced separators=""><msup><mn>2</mn><mi mathvariant="italic">nQuantBit</mi></msup><mo>-</mo><mn>1</mn></mfenced><mo>+</mo><mn>0.5</mn></mfenced></math><img file="EP1565000B1_D0010.tif" /></maths>
0077In Equation (8), floor( ) is a function for converting an input floating-point number into a maximum integer of no greater than the input floating-point number. The quantizer 310 outputs the quantized key value data to the DPCM processor 340 and the quantization error minimizer 320.
0078The quantization error minimizer 320 receives the minimum values and the maximum range from the normalizer 300, calculates the minimum values and the maximum values using the minimum values and the maximum range input from the normalizer 300, determines a minimum value and a maximum value to minimize a quantization error in step S630, calculates the minimum values and the maximum range using the determined minimum and maximum values, and outputs the minimum values and the maximum range to the floating-point number converter 330 so that they are encoded into a key value header. Here, the minimum and maximum values determined by the quantization error minimizer 320 are used to minimize a quantization error.
0079Hereinafter, step S650 performed by the floating-point number encoder 330 will be described with reference to <figref idref="f0011">FIG. 7A</figref>.
0080The floating-point number encoder 330 receives minimum values x_min, y_min, and z_min among the key value data of each of the x, y, and z components, a maximum value max of a component having the maximum range, information nWhichAxis on which component a maximum value max belongs to, and the digit number nKeyValueDigit of the original key value data in step S651.
0081In order to enhance the efficiency of encoding key value data by decreasing the number of bits required for encoding, the floating-point number encoder 330 converts x_min, y_min, z_min, and max, which are represented by binary numbers, into decimal numbers in step S652.
0082A computer stores floating-point numbers in the form of 32-bit binary numbers. When a floating-point number in the binary system is input, the floating-point number encoder 330 converts the floating-point number into a mantissa and its exponent in the decimal system, following Equation (9).<maths id="math0011" num="(9)"><math display="block"><munder><munder><mrow><mi mathvariant="italic">mantissa</mi><mi mathvariant="italic">_</mi><mi mathvariant="italic">binary</mi><mo>*</mo><msup><mn>2</mn><mrow><mi>exp</mi><mi mathvariant="italic">onent</mi><mi>_</mi><mi mathvariant="italic">binary</mi></mrow></msup></mrow><mo>︸</mo></munder><mrow><mi mathvariant="italic">floating</mi><mo>-</mo><mi mathvariant="italic">point number in binary system</mi></mrow></munder><mo>=</mo><munder><munder><mrow><mi mathvariant="italic">mantissa</mi><mo>*</mo><msup><mn>10</mn><mrow><mi>exp</mi><mi mathvariant="italic">onent</mi></mrow></msup></mrow><mo>︸</mo></munder><mrow><mi mathvariant="italic">floating</mi><mo>-</mo><mi mathvariant="italic">point number in decimal system</mi></mrow></munder></math><img file="EP1565000B1_D0011.tif" /></maths>
0083For example, a floating-point number 12.34 in the decimal system can be converted into a binary number by a computer, which is shown in the following.<maths id="math0012" num=""><math display="block"><mfrac><mn>0</mn><mn>1</mn></mfrac><mo></mo><mfrac><mn>10001010111000010100011</mn><mn>2</mn></mfrac><mo></mo><mfrac><mn>10000010</mn><mn>3</mn></mfrac></math><img file="EP1565000B1_D0012.tif" /></maths><ol id="ol0001" compact="compact" ol-style=""><li>1: the sign</li><li>2: the mantissa in the binary system</li><li>3: the exponent in the binary system</li></ol>
0084The binary number can be converted back into the original decimal number following Equation (9), which is shown in the following.<maths id="math0013" num=""><math display="block"><mfrac><mn>0</mn><mn>1</mn></mfrac><mo></mo><mfrac><mn>1234</mn><mn>2</mn></mfrac><mo></mo><mfrac><mn>2</mn><mn>3</mn></mfrac></math><img file="EP1565000B1_D0013.tif" /></maths><ol id="ol0002" compact="compact" ol-style=""><li>1: the sign</li><li>2: the mantissa in the decimal system</li><li>3: the exponent in the decimal system</li></ol>
0085In order to include a mantissa and an exponent of the decimal system in a bitstream, the number of bits required to represent the mantissa and the number of bits required to represent the exponent must be calculated. An exponent has a value between -38 and 38 and thus may be expressed together with its sign using 7 bits. The number of bits required to represent a mantissa depends on the digit number of the mantissa. Values of various ranges and the number of bits required to represent their mantissas are shown in the following table. <tables id="tabl0002" num="0002"><table frame="all"><title>Table 2</title><tgroup cols="3"><colspec colnum="1" colname="col1" colwidth="32mm" /><colspec colnum="2" colname="col2" colwidth="40mm" /><colspec colnum="3" colname="col3" colwidth="67mm" /><thead valign="top"><row><entry align="center">Ranges of values</entry><entry align="center">Digit number of mantissa</entry><entry align="center">Number of bits required to represent mantissa</entry></row></thead><tbody><row><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry></row><row><entry align="center">1-9</entry><entry align="center">1</entry><entry align="center">4</entry></row><row><entry align="center">10-99</entry><entry align="center">2</entry><entry align="center">7</entry></row><row><entry align="center">100 - 999</entry><entry align="center">3</entry><entry align="center">10</entry></row><row><entry align="center">1000 - 9999</entry><entry align="center">4</entry><entry align="center">14</entry></row><row><entry align="center">10000 - 99999</entry><entry align="center">5</entry><entry align="center">17</entry></row><row><entry align="center">100000 - 999999</entry><entry align="center">6</entry><entry align="center">20</entry></row><row><entry align="center">1000000 - 9999999</entry><entry align="center">7</entry><entry align="center">24</entry></row></tbody></tgroup></table></tables>
0086The floating-point number encoder 330 checks if the digit numbers of x_min, y_min, and z_min are the same in step S453. If they are not the same, they are output to the key value header encoder 360 and are encoded as a key value header in step 654.
0087If the digit numbers of x_min, y_min, and z_min are the same, the floating-point number encoder 330 checks if they are the same as the digit number of the original key value data in step S655. If their digit numbers of x_min, y_min, and z_min are not the same as the digit number of the original key value data, one of the digit numbers of x_min, y_min, and z_min is output to the key value header encoder 360 and are encoded as a key header in step S656.
0088Thereafter, the floating-point number encoder 330 checks among which component key value data the maximum value max among all the key value data of the x, y, and z components is selected from and determines whether or not the digit number of max is the same as the digit number of a minimum value among the key value data of the component, from which the maximum value max comes, in step S657.
0089If the digit number of max is not the same as the digit number of the minimum value among the key value data of the component, from which the maximum value max comes, it is output to the key value header encoder 360 and is encoded as a key value header. On the other hand, if the digit number of max is the same as the digit number of the minimum value among the key value data of the component to which the maximum value max belongs to, state information describing that they are the same is output to the key value header encoder 360 in step S658.
0090The aforementioned operation of the floating-point number encoder 330 is for encoding the mantissa of a converted floating-point number, and a process of encoding information on the exponent of the floating-point number into a key value header will be described in the following.
0091The floating-point number encoder 330 identifies which one is a maximum value among the absolute values of the exponents of x_min, y_min, z_min, and max, stores the identified maximum value as nMaxExp, and encodes nMaxExp into a key value header of several bits in step S659.
0092Thereafter, the floating-point number encoder 330 checks if the signs of the exponents of x_min, y_min, z_min, and max are the same in step S460. If they are the same, bSameSignExp is set to 1 and their sign is output to the key value header encoder 360 in step S661. On the other hand, if they are not the same, bSameSignExp is set to 0 in step S662, and then encoding of the information on the exponents of x_min, y_min, z_min, and max are completed.
0093Referring to <figref idref="f0012">FIG. 7B</figref>, the floating-point number encoder 330 encodes the sign of the converted floating-point number in step S663 before encoding x_min, y_min, z_min, and max into a key value header.
0094Next, the floating-point number encoder 330 calculates the number of bits required for encoding the floating-point number referring to Table 2 and outputs the mantissa of the floating-point number, having as many bits as the result of the calculation, to the key value header encoder 360 in step S664.
0095The floating-point number encoder 330 calculates the number of bits required for encoding nMaxExp referring to Table 2 and outputs the exponent of the floating-point number having as many bits as the result of the calculation, to the key value header encoder 360 in step S665.
0096The floating-point number encoder 330 checks based on bSameSignExp if exponents of x_min, y_min, z_min, and max have the same sign. If they do not have the same sign, their signs are output to the key value header encoder 360 and are encoded in step S667, thus completing the process of encoding the maximum and minimum values among the key data of each of the x, y, and z components input from the normalizer 300.
0097The floating-point number encoder 330 receives the maximum and minimum values required for minimizing a quantization error from the quantization error minimizer 320 and encodes them into the key header through the above-described steps.
0098Referring to <figref idref="f0010">FIG. 6B</figref> again, the DPCM processor 340 performs a circular DPCM operation and a predictive-circular DPCM operation on the quantized key value data and outputs differential data to the entropy encoder 350 in step S670. The DPCM processor 340 is constituted by the aforementioned DPCM operator, and the operation and structure of the DPCM operator have been described above. The only difference between the DPCM processor 340 and the aforementioned DPCM operator is that the DPCM processor 340 performs a circular DPCM operation and a predictive-circular DPCM operation on the key value data of each of the x, y, and z components, separately.
0099The differential data output from the DPCM processor 340 are entropy-encoded in the entropy encoder 350 in step S680.
0100Referring to <figref idref="f0013">FIG. 7C</figref>, the entropy encoder 350 entropy-encodes the differential data of the key value data of each of the x, y, and z components.
0101The entropy encoder 350 checks referring to the differential data of each of the x, y, and z components if the quantized values of the x, y, and z components are the same and completes the entropy-encoding in step S681 if they are the same. For example, in a case where in a three-dimensional animation, a train moves in a horizontal direction which is the same as the direction of the x component, the key value data of the x component vary. However, there is little change in the y and z components. Accordingly, if the y and z components are quantized, they are supposed to have the same value. Accordingly, there is no need to encode all key value data which are practically the same, and thus it is possible to enhance the efficiency of encoding by encoding only one of the key value data into a key value header.
0102If the quantized key value data of each of the x, y, and z components are not the same, the entropy encoder 350 reads a predetermined value which has been set up in advance, in step S682. Thereafter, the entropy encoder 350 encodes the differential data of the quantized key value data of each of the x, y, and z components using a unary AAC function in step S683 or encodes them using a successive quantization AAC function in step S685.
0103Hereinafter, the unary AAC function will be described with reference to <figref idref="f0015">FIG. 8</figref>. The unary AAC function converts symbols to be encoded into several bits which consist of a series of 0s, a flag bit 1 indicating that the series of zeros end, and one bit representing the sign of the symbol. Here, the series of zeros corresponds to the magnitude of the symbol. For example, 256 is encoded using the unary AAC function into a series of bits consisting of two hundred fifty six Os, 1 which is a flag bit indicating the series of 0s ends, and 0 which represents the sign of 256, i.e., a plus sign. Due to the unary AAC function, the redundancy of the bits representing the symbol to be encoded increases, which enhances the efficiency of encoding the symbol.
0104Referring to <figref idref="f0014">FIGS. 7D</figref>, <figref idref="f0015">9A</figref>, and <figref idref="f0016">9B</figref>, a method of encoding symbols using the SQ AAC function will be described. The SQ AAC function encodes symbols continuously renewing a quantization range.
0105<figref idref="f0015">FIG. 9A</figref> is a diagram illustrating a method of encoding symbols using the SQ AAC function. As shown in <figref idref="f0015">FIG. 9A</figref>, an input symbol to be encoded is 1, and a minimum value and a maximum value in an encoding range are 0 and 9, respectively.
0106Referring to <figref idref="f0015">FIG. 9A</figref>, in a first step of encoding the symbol, the encoding range is divided into two sub-ranges, i.e., an upper range and a lower range, and then it is checked whether the symbol to be encoded, i.e., 1, belongs to the upper range or the lower range. Since 1 belongs to the lower range, 0 is encoded and the lower range is renewed into a new encoding range. Accordingly, the new encoding range for the second step is from 0 to 4.
0107In the second step, the new encoding range of 0 - 4 is divided into two sub-ranges, i.e., an upper range and a lower range, and then it is checked whether 1 belongs to the upper range or the lower range. Since 1 belongs to the lower range, 0 is encoded, and the maximum value in the encoding range is renewed into 1 which is the maximum value in the lower range. Accordingly, a new encoding range for the third step, which used to be the lower range, is from 0 to 1.
0108In the third step, the encoding range of 0 - 1 is divided into an upper value and a lower value, and then it is checked whether 1 belongs to an upper range. Since 1 is equal to the upper value, 1 is encoded and then the minimum value in the corresponding encoding range is renewed into 1. Accordingly, a new encoding range is [1, 1] so that its maximum and minimum values are the same. When minimum and maximum values in an encoding range are the same, the encoding process using the SQ AAC function is completed.
0109<figref idref="f0014">FIG. 7D</figref> is a flowchart of a process of encoding differential data of key value data of a component using the SQ AAC function, which is performed in the entropy encoder 350 according to the present invention.
0110Referring to <figref idref="f0014">FIG. 7D</figref>, the entropy encoder 350 receives differential data (hereinafter, referred to as symbols) of key value data, the number nQP of bits required for entropy-encoding the symbols, nStartlndex indicating the first index of symbols to be encoded into a bitstream, and the number (n) of symbols to be encoded in step S692.
0111The entropy encoder 350 encodes the signs of the symbols and converts the symbols into positive numbers in step S694. The reason the symbols are converted into positive numbers is that negative numbers are not allowed in subsequent processes.
0112The entropy encoder 350 identifies a maximum value among the positive numbers, stores the maximum value as nMax, and encodes nMax into as many bits as nQP in step S696.
0113The entropy encoder 350 initializes a range within which the symbols will be encoded and sets a minimum value <i>P̂</i><sub><i>i</i>·min</sub> and a maximum value <i>P̂</i><sub><i>i</i>·max</sub> in the encoding range to 0 and nMax, respectively. In addition, the entropy encoder 350 allots a one-bit flag <i>P̂<sub>i·found</sub></i> to each of the symbols. The flag <i>P̂<sub>i·found</sub></i> is used for changing probability models during encoding the symbols. The flag <i>P̂<sub>i·found</sub></i> is set as 'false' at the beginning and is converted into 'true' when a value to be encoded next is 1, and thereafter, the probability model having been used for encoding the symbols so far is replaced by another.
0114Next, the entropy encoder 350 identifies a differential datum (i = nStartlndex) of each of the x, y, and z components, which is supposed to be encoded first, and sets a flag bDone, which indicates whether or not encoding all the symbols is completed, as 'true' in step S700.
0115The entropy encoder 350 repeatedly performs steps S702 through S718, which will be described in the following, until maximum and minimum values in an encoding range for each of the symbols become the same, i.e., until there is no symbol left to be encoded. Here, when maximum and minimum values in an encoding range for a symbol are the same, it is considered that encoding of the symbol is completed.
0116The entropy encoder 350 checks if <i>P̂</i><sub><i>i</i>·max</sub> is equal to <i>P̂</i><sub><i>i</i>·min</sub> in step S702. If <i>P̂</i><sub><i>i</i>·max</sub> is equal to <i>P̂</i><sub><i>i</i>·min</sub>, the method moves on to a step for encoding the next symbol, and if not, bDone is set as 'false', which means the encoding of the current symbol (the symbol currently being encoded) is not completed yet, in step S704.
0117The entropy encoder 350 calculates a middle value nMid in the encoding range for the current symbol in step S706 and compares the middle value nMid with the value of the current symbol in step S708. In a preferred embodiment of the present invention, the middle value nmid is calculated using the following equation.<maths id="math0014" num="(10)"><math display="block"><mi mathvariant="italic">nMid</mi><mo>=</mo><mfrac><mrow><msub><mover><mi>P</mi><mo>^</mo></mover><mrow><mi>i</mi><mo>⋅</mo><mi>max</mi></mrow></msub><mo>+</mo><msub><mover><mi>P</mi><mo>^</mo></mover><mrow><mi>i</mi><mo>⋅</mo><mi>min</mi></mrow></msub></mrow><mn>2</mn></mfrac><mo>+</mo><msub><mover><mi>P</mi><mo>^</mo></mover><mrow><mi>i</mi><mo>⋅</mo><mi>min</mi></mrow></msub><mo>+</mo><mn>1</mn></math><img file="EP1565000B1_D0014.tif" /></maths>
0118As a result of the comparison, if the current symbol value is not greater than the middle value nMid, which means that the current symbol belongs to the upper range, then 0 is issued to a bitstream and the maximum range <i>P̂</i><sub><i>i</i>·max</sub> in the encoding range for the current symbol is replaced by the middle value nMid in step S710.
0119On the other hand, if the current symbol value is greater than the middle value nMid, which means that the current symbol belongs to the upper range, then 1 is issued to the bitstream and the minimum value <i>P̂</i><sub><i>i</i>·min</sub> in the encoding range for the current symbol is replaced by the middle value nMid. When the value of the symbol currently being encoded exceeds the middle value nMid for the first time, in other words, when 1 is issued to the bitstream for the first time, <i>P̂<sub>i·found</sub></i> is set as 'true' in step S712 so as to change the probability model for encoding the symbols.
0120There are two probability models used in the SQ AAC function. One is notFoundContext for entropy-encoding bits output before 1 is issued from each of the symbols for the first time, and the other is FoundContext for entropy-encoding bits output right after 1 is issued from each of the symbols for the first time. The purpose of using two different probability models is to increase the probability of 0 being generated during using notFoundContext. As the probability of 0 being generated increases, the efficiency of entropy-encoding a symbol increases.
0121Thereafter, the entropy encoder 350 checks if <i>P̂<sub>i·found</sub></i> is true or false in step S714. If <i>P̂<sub>i·found</sub></i> is true, the entropy encoder 350 encodes the symbols using FoundContext in step S716, and if not, the entropy encoder 350 encodes the symbols using notFoundContext in step S718.
0122When the process of encoding the current symbol ranging from step S702 to step S718 is completed, which means the entropy encoder completes the encoding of the current symbol in only one stage, the entropy encoder 350 increases an encoding index i by 1 in step S720. Next, the entropy 350 checks whether or not all the symbols are completely encoded in the current stage in step S722. If there are symbols left to be encoded in the current stage, the entropy encoder 350 performs steps S702 through S722 again.
0123When all the symbols in one stage are completely encoded, the entropy encoder 350 checks based on the flag bDone if the encoding of all stages is completed, in step S724. If bDone is true, the entropy encoder 350 completes the whole encoding process in the current stage and starts to encode the next component, and if not, the entropy encoder 350 performs steps S700 through S722 again to encode the remaining symbols.
0124<figref idref="f0016">FIG. 9B</figref> is a diagram illustrating a process of encoding a plurality of symbols using the SQ AAC function. Specifically, <figref idref="f0016">FIG. 9B</figref> shows a process of encoding 0, 1, 2, 3, 4, and 9 using the SQ AAC function.
0125Referring to <figref idref="f0010">FIG. 6B</figref> again, if the apparatus for encoding data according to the present invention generates a bitstream by entropy-encoding all input key value data, the key value header encoder 360 encodes information required for decoding the encoded key value data into key value header information, adds the key value header information to the bitstream, and outputs the resulting bitstream in step S730.
0126The key value header encoder 360 encodes the number and digit number of input key value data to be encoded and the quantization bit size of the key value data. Next, the key value header encoder 360 identifies if each of the x, y, and z components has the same quantized values (for example, even though the key value data of each of the x, y, and z components vary, the quantized key value data of the x component have the same value because the degree to which the key value data of the x component vary is very small) and encodes the result into a flag.
0127For example, if the quantized values of the x component are not the same, whether a circular DPCM operation or a predictive-circular DPCM operation has been used to encode the key value data of the x component and whether the key value data of the x component will be encoded using the unary AAC function or the SQ AAC function are encoded into flags. If the key value data of the x component is not expected to be encoded using the unary AAC function, the encoding bit size of the x component and the start index of x component to be entropy-encoded is encoded into a key value header.
0128Likewise, if the key value data of each of the y and z components are not the same, header information of the y and z components, which exactly corresponds to the aforementioned header information of the x component is encoded into a header.
0129If the quantized values of the x component are not the same, the unary AAC function is not used to encode the key value data of the x component, and the start index of x component to be entropy-encoded is 1, then the first quantized key value datum is encoded as an intra datum. In the same manner, the first quantized key value datum of each of the y and z components is encoded as an intra datum.
0130The key value header encoder 360 identifies which component among the x, y, and z components has a maximum range. If the x component has a maximum range, the key value header encoder 360 sets up a variable nWhichAxis at 0. If the component y has a maximum range, the key value header encoder 360 sets up nWhichAxis at 1. If the component z has a maximum range, the key value header encoder 360 sets up nWhichAxis at 2. Thereafter, the key value header encoder 360 encodes nWhichAxis, x_min, y_min, z_min, and max into a key header using the floating-point number encoder 330.
0131Hereinafter, an example of computer programs into which a method for encoding data according to a fourth embodiment of the present invention is realized will be described.
0132The apparatus for encoding data according to the present invention encodes a position interpolator into a bitstream, which will be described in the following. For better understanding, conventional program codes and variables will be described in the following in the form of SDL language.
0133<figref idref="f0030">FIG. 19</figref> shows an example of program codes into which a compressed position interpolator is realized. In <figref idref="f0030">FIG. 19</figref>, a top class for reading a bitstream of a compressed position interpolator is shown. The first class includes PoslKeyValueHeader and PoslKeyValue. PoslKeyValueHeader includes header information for decoding PoslKeyValue, and class PoslKeyValue reads key value data regarding the compressed position interpolator from the bitstream. A function qf_start( ) is used to initialize an arithmetic decoder before reading part of the bitstream which is AAC-encoded.
0134<figref idref="f0031">FIG. 20</figref> shows program codes of PosIKeyValueHeader. Referring to <figref idref="f0031">FIG. 20</figref>, among variables stored in PoslKeyValueHeader, nNumKeyValueCodingBit represents the bit size of nNumberOfKeyValue, nNumberOfKeyValue represents the number of key value data, and nKVQBit represents the quantization bit size of the key value data.
0135x_keyvalue_flag, y_keyvalue_flag, and z_keyvalue_flag indicate if the x, y, and z components has the same quantized value and nKVDigit represents a maximum number of most significant digits of each of the key value data. nKVDPCMOrder_X, nKVDPCMOrder_Y, and nKVDPCMOrder_Z correspond to the order of DPCM used for the key value data of each of the x, y, and z components, respectively. If DPCM has been performed, a flag is set to 0, and if predictive DPCM has been performed, the flag is set to 1.
0136bisUnaryAAC_X, blsUnaryAAC_Y, and blsUnaryAAC_Z each indicate that an unary AAC function has been used during entropy-encoding. nKVCodingBit_X, nKVCodingBit_Y, and nKVCodingBit_Z indicate the encoding bit size for the x, y, and z components, respectively. nStarttndex_X, nStartIndex_Y, and nStartlndex_Z represent the start index of each component axis to be encoded. firstKV_X, firstKV_Y, and firstKV_Z represent a first quantized key value datum of each of the x, y, and z components, respectively, which are encoded as intra data.
0137<figref idref="f0032">FIG. 21</figref> shows program codes of class KeyValueMinMax. Referring to <figref idref="f0032">FIG. 21</figref>, class KeyValueMin retrieves the maximum and minimum values that have been used for normalization of key value data. bUse32float indicates whether or not a 32-bit floating-point number has been used to store the maximum and minimum values. If bUse32Float is 0, the maximum and minimum values for normalization of key value data are encoded using IEEE Standard 754 floating-point number format. If not, the maximum and minimum values for normalization of key value data are encoded using the floating-point number encoder.
0138nWhichAxis represents a component having a maximum range among the x, y, and z components. In the present embodiment, if nWhichAxis is 0, the X-axis has a maximum range, if nWhichAxis is 1, the Y-axis has a maximum range, and if nWhichAxis is 2, the Z-axis has a maximum range.
0139bAliSameMantissaDigitFlag indicates whether or not the mantissas of minimum values among the key value data of each of the x, y, and z components have the same digit number, and bSameKVDigitFlag represents the digit number of the mantissas of the minimum values is the same as nKVDigit. nMantissaDigit_X, nMantissaDigit_Y, and nMantissaDigit_Z represent the digit number of the mantissas of the minimum values among the key value data of each of the x, y, and z components, respectively.
0140bMaxDigitFlag indicates whether or not the mantissa of a maximum value has the same digit number as a minimum value of component, from which the maximum value max comes. If the digit number of the mantissa of the maximum value is different from the digit number of the mantissa of the minimum value, the digit number of the mantissa of the maximum value is read from the bitstream.
0141nMantissaDigit_M represents the digit number of the mantissa of the maximum value, and nExponentBits represents the number of bits required for encoding the maximum absolute exponent among the exponent of the maximum and minimum values. bAllSameExponentSign indicates whether or not the signs of the x, y, and z components are the same, and nExponentSign represents the sign of an exponent when bAlISameExponentSign is true.
0142fpnMin_X, fpnMin_Y, fpnMin_Z, and fpnMax represent floating-point numbers in the decimal system which are decoded. A method of decoding fpnMin_X, fpnMin_Y, fpmMin_Z, and fpnMax will be described later with FloatingPointNumber. fMin_X, fMin_Y, and fmin_Z represent a minimum value among the key value of each of the x, y, and z components, and fMax represents a maximum value among the key value data of the component having the maximum range.
0143Program codes of class FloatingPointNumber will be described in the following with reference to <figref idref="f0033">FIG. 22</figref>. Class FloatingPointNumber expresses floating-point numbers using the decimal system. nmantissa represents the mantissa of a floating-point number in the decimal system, and nExponent represents the exponent of the floating-point number.
0144nsign represents the sign of a floating-point number, and nExponentSign represents the sign of the exponent of the floating-point number.
0145Program codes of class PoslKeyValue will be described in the following with reference to <figref idref="f0034">FIG. 23</figref>. Referring to <figref idref="f0034">FIG. 23</figref>, among variables stored in class PoslKeyValue, keyValue_X, keyValue_Y; and keyValue_Z represent an array of the key value data of each of the x, y, and z components, respectively, in a position interpolator. If nStartIndex_X is set to 0, keyValue_X[0] is decoded from a bitstream using an arithmetic decoder. If nStartIndex_X is set to 1, keyValue_X[0] is decoded from the key value header decoder. In the same manner, keyValue_Y[0] and keyValue_Z[0] are determined. When arithmetically decoding keyValue_X[0], keyValue_Y[0], and keyValue_Z[0] from the bitstream, a decodeUnaryAAC or decodeSQAAC function is used.
0146Context models kVXSignContext, kVYSignContext, and kVZSignContext are used to decode the signs of keyValue_X, keyValue_Y, and keyValue_Z, respectively. The context models kVXSignContext, kVYSignContext, and kVZSignContext are transmitted to the decodeUnaryAAC or decodeSQAAC function.
0147MaxValueContext, FoundContext, and NotFoundContext are used to entropy-decode the absolute values of key values. For example, kVXMaxValueContext, kVXFoundContext, and kVXNotFoundContext are used to decode keyValue_X. MaxValueContext, FoundContext, and NotFoundContext are transmitted to the decodeUnaryAAC or decodeSQAAC function.
0148Context models kVXUContext, kVYUContext, and kVZUContext are used to decode keyValue_X, keyValue_Y, and keyValue_Z and are transmitted to the decodeUnaryAAC function.
0149Hereinafter, an inverse DPCM operator, which outputs quantized data by restoring differential data generated by the aforementioned DPCM operator, will be described with reference to <figref idref="f0017">FIGS. 10A</figref> and <figref idref="f0018">10B</figref>.
0150<figref idref="f0017">FIG. 10A</figref> is a block diagram of an inverse DPCM operator, and <figref idref="f0018">FIG. 10B</figref> is a flowchart of an inverse DPCM operation.
0151Referring to <figref idref="f0017">FIG. 10A</figref>, an inverse DPCM operator includes an inverse circular DPCM operator 1020, which performs an inverse circular quantization operation on differential data input thereinto so as to extend their range, performs an inverse DPCM operation on the input differential data, and then outputs quantized data, an inverse predictive-circular DPCM operator 1030 which performs an inverse circular quantization operation on differential data input thereinto so as to extend their range, performs an inverse predictive DPCM operation on the input differential data, and then outputs quantized data, and a determining unit 1010 which outputs differential data to either the inverse circular DPCM operator 1020 or the inverse predictive-circular DPCM operator 1030 depending on the kind of DPCM that has been performed on the differential data.
0152An inverse DPCM operation will be described in the following with reference to <figref idref="f0018">FIG. 10B</figref>. Referring to <figref idref="f0017">FIGS. 10A</figref> and <figref idref="f0018">10B</figref>, differential data subjected to an inverse DPCM operation are input into the determining unit 1010. Then the determining unit 1010 identifies what kind of DPCM has been performed on the input differential data, determines what kind of inverse DPCM will be performed on the input differential data based on the result, and outputs the differential data to either the inverse circular DPCM operator 1020 or the inverse predictive-circular DPCM operator 1030 in step S1010.
0153If the differential data are input into the inverse circular DPCM operator 1020 and nMax is a maximum value in a quantization range of the input differential data, the inverse circular DPCM operator 1020 obtains quantized differential data <maths id="math0015" num=""><math display="inline"><msub><mrow><mover><mi>P</mi><mi>‿</mi></mover><mo></mo><mi>ʹ</mi></mrow><mi>i</mi></msub></math><img file="EP1565000B1_D0015.tif" /></maths> in step S1020 by performing inverse circular quantization on the input differential data <maths id="math0016" num=""><math display="inline"><msub><mover><mi>P</mi><mi>‿</mi></mover><mi>i</mi></msub><mo>,</mo></math><img file="EP1565000B1_D0016.tif" /></maths>, which is shown in the following equation.<maths id="math0017" num="(11)"><math display="block"><mtable><mtr><mtd><msub><mrow><mover><mi>P</mi><mi>‿</mi></mover><mo></mo><mi>ʹ</mi></mrow><mi>i</mi></msub><mo>=</mo><msub><mover><mi>P</mi><mi>‿</mi></mover><mi>i</mi></msub><mo>-</mo><mfenced separators=""><mi mathvariant="italic">nMax</mi><mo>+</mo><mn>1</mn></mfenced></mtd><mtd><mspace width="1em" /></mtd><mtd><mfenced separators=""><mi mathvariant="italic">if</mi><mspace width="1em" /><msub><mrow><mover><mi>P</mi><mi>‿</mi></mover><mo></mo><mi>ʹ</mi></mrow><mi>i</mi></msub><mo>≥</mo><mn>0</mn></mfenced></mtd></mtr><mtr><mtd><msub><mrow><mover><mi>P</mi><mi>‿</mi></mover><mo></mo><mi>ʹ</mi></mrow><mi>i</mi></msub><mo>=</mo><msub><mover><mi>P</mi><mi>‿</mi></mover><mi>i</mi></msub><mo>+</mo><mfenced separators=""><mi mathvariant="italic">nMax</mi><mo>+</mo><mn>1</mn></mfenced></mtd><mtd><mspace width="1em" /></mtd><mtd><mfenced><mrow><mi mathvariant="italic">if</mi><mspace width="1em" /><msub><mover><mi>P</mi><mi>‿</mi></mover><mi>i</mi></msub><mo><</mo><mn>0</mn></mrow></mfenced></mtd></mtr></mtable></math><img file="EP1565000B1_D0017.tif" /></maths>
0154Thereafter, the inverse circular DPCM operator 1020 obtains a value A of an inverse-DPCMed differential datum and a value B of an inverse-DPCMed differential datum by substituting input differential data <maths id="math0018" num=""><math display="inline"><msub><mover><mi>P</mi><mi>‿</mi></mover><mi>i</mi></msub></math><img file="EP1565000B1_D0018.tif" /></maths> and inversely circular-quantized differential data <maths id="math0019" num=""><math display="inline"><msub><mrow><mover><mi>P</mi><mi>‿</mi></mover><mo></mo><mi>ʹ</mi></mrow><mi>i</mi></msub><mo>,</mo></math><img file="EP1565000B1_D0019.tif" /></maths>, respectively, obtained from Equation (11) into Equation (12).<maths id="math0020" num="(12)"><math display="block"><mtable><mtr><mtd><mi>A</mi><mo>=</mo><msub><mover><mi>P</mi><mi>‿</mi></mover><mi>i</mi></msub><mo>+</mo><msub><mover><mi>P</mi><mo>˜</mo></mover><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msub></mtd><mtd><mspace width="1em" /></mtd></mtr><mtr><mtd><mi>B</mi><mo>=</mo><msub><mrow><mover><mi>P</mi><mi>‿</mi></mover><mo></mo><mi>ʹ</mi></mrow><mi>i</mi></msub><mo>+</mo><msub><mover><mi>P</mi><mo>˜</mo></mover><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msub></mtd><mtd><mspace width="1em" /></mtd></mtr></mtable></math><img file="EP1565000B1_D0020.tif" /></maths>
0155In Equation (12), n represents the number of data, and i represents an integer between 1 and n - 1.
0156If A is not smaller than 0 and not greater than nMax, the inverse circular DPCM operator 1020 outputs A as inverse circular-DPCMed data <maths id="math0021" num="(12)"><math display="inline"><msub><mover><mi>P</mi><mo>˜</mo></mover><mi>i</mi></msub><mn>.</mn></math><img file="EP1565000B1_D0021.tif" /></maths> If A is smaller than 0 or greater than nMax, the inverse circular DPCM operator 1020 outputs B in step S1040.
0157The inverse predictive-circular DPCM operator 1030 obtains the inversely circular-quantized predicted differential data <img file="EP1565000B1_D0022.tif" /> in step S1020 by performing inverse circular quantization on the predicted differential data <img file="EP1565000B1_D0023.tif" />using Equation (11).
0158If <maths id="math0022" num=""><math display="inline"><mi mathvariant="normal">P</mi><mo>=</mo><mn mathvariant="normal">2</mn><mo>×</mo><msub><mover><mi mathvariant="italic">P</mi><mo>˜</mo></mover><mrow><mi mathvariant="italic">i</mi><mo>-</mo><mn mathvariant="normal">1</mn></mrow></msub><mo>+</mo><msub><mover><mi mathvariant="italic">P</mi><mo>˜</mo></mover><mrow><mi mathvariant="italic">i</mi><mo>-</mo><mn mathvariant="normal">2</mn></mrow></msub></math><img file="EP1565000B1_D0024.tif" /></maths> where P represents predicted data used for decoding, the inverse circular DPCM operator 1030 calculates A by substituting <img file="EP1565000B1_D0023.tif" /> into Equation (13) and calculates B by substituting <img file="EP1565000B1_D0022.tif" /> into Equation (14). <maths id="math0023" num="(13)"><math display="block"><mtable columnalign="left"><mtr><mtd><mi>A</mi><mo>=</mo><mi mathvariant="italic">nMax</mi><mo>-</mo><msub><mover><mi>P</mi><mi>‿</mi></mover><mi mathvariant="italic">i</mi></msub></mtd><mtd><mfenced separators=""><mi mathvariant="italic">ifP</mi><mo>></mo><mi mathvariant="italic">nMax</mi></mfenced></mtd></mtr><mtr><mtd><mi>A</mi><mo>=</mo><msub><mover><mi>P</mi><mi>‿</mi></mover><mi mathvariant="italic">i</mi></msub></mtd><mtd><mfenced separators=""><mi mathvariant="italic">ifP</mi><mo><</mo><mn>0</mn></mfenced></mtd></mtr><mtr><mtd><mi>A</mi><mo>=</mo><msub><mover><mi>P</mi><mi>‿</mi></mover><mi mathvariant="italic">i</mi></msub><mo>+</mo><mi>P</mi></mtd><mtd><mfenced><mi mathvariant="italic">otherwise</mi></mfenced></mtd></mtr></mtable></math><img file="EP1565000B1_D0025.tif" /></maths><maths id="math0024" num="(14)"><math display="block"><mtable columnalign="left"><mtr><mtd><mi>B</mi><mo>=</mo><mi mathvariant="italic">nMax</mi><mo>-</mo><msub><mrow><mover><mi>P</mi><mi>‿</mi></mover><mo></mo><mi>ʹ</mi></mrow><mi mathvariant="italic">i</mi></msub></mtd><mtd><mfenced separators=""><mi mathvariant="italic">ifP</mi><mo>></mo><mi mathvariant="italic">nMax</mi></mfenced></mtd></mtr><mtr><mtd><mi>B</mi><mo>=</mo><msub><mrow><mover><mi>P</mi><mi>‿</mi></mover><mo></mo><mi>ʹ</mi></mrow><mi mathvariant="italic">i</mi></msub></mtd><mtd><mfenced separators=""><mi mathvariant="italic">ifP</mi><mo><</mo><mn>0</mn></mfenced></mtd></mtr><mtr><mtd><mi>B</mi><mo>=</mo><msub><mrow><mover><mi>P</mi><mi>‿</mi></mover><mo></mo><mi>ʹ</mi></mrow><mi mathvariant="italic">i</mi></msub><mo>+</mo><mi>P</mi></mtd><mtd><mfenced><mi mathvariant="italic">otherwise</mi></mfenced></mtd></mtr></mtable></math><img file="EP1565000B1_D0026.tif" /></maths>
0159In Equations (13) and (14), n represents the number of data and i is an integer between 1 and n - 1.
0160If A is not smaller than 0 and not greater than nMax, the inverse circular DPCM operator 1020 outputs A as the inversely predictive-circular-DPCMed data <i>P̃<sub>i</sub></i>. If A is smaller than 0 or greater than nMax, the inverse predictive-circular DPCM operator 1020 outputs B as <i>P̃<sub>i</sub></i> in step S1040.
0161Hereinafter, an apparatus for decoding data will be described with reference to <figref idref="f0018">FIG. 11</figref>. The apparatus for decoding data decodes a bitstream, into which input data have been encoded using the apparatus for encoding data, using the DPCM operator according to the present invention.
0162Referring to <figref idref="f0018">FIG. 11</figref>, the apparatus for decoding data includes an entropy decoder 1120, an inverse DPCM processor 1130, which is constituted by the aforementioned inverse DPCM operator, and an inverse quantizer 1140.
0163The entropy decoder 1120 generates differential data by entropy-decoding an input bitstream and outputs the differential data to the inverse DPCM processor 1130.
0164The inverse DPCM processor 1130, as described above, identifies what kind of DPCM has been performed on the input differential data, performs an inverse circular DPCM operation or an inverse predictive-circular DPCM operation on the differential data, and outputs quantized data to the inverse quantizer 1140.
0165The inverse quantizer 1140 inversely quantizes the quantized data input from the inverse DPCM processor 1130 with predetermined quantization bits and outputs retrieved data.
0166Hereinafter, an apparatus for decoding data will be described with reference to <figref idref="f0019">FIGS. 12A</figref> and <figref idref="f0020">12B</figref>. The apparatus for decoding data decodes a bitstream, into which data having a plurality of components that have been normalized by the normalizer according to the present invention are encoded.
0167Referring to <figref idref="f0019">FIG. 12A</figref>, the apparatus for decoding data includes an entropy decoder 1120 which entropy-decodes an input bitstream and thus outputs differential data, an inverse DPCM operator 140/1130 which performs an inverse DPCM operation on the differential data input from the entropy decoder 1120 and outputs quantized data, an inverse quantizer 1140 which inversely quantizes the quantized data input from the inverse DPCM operator 140/1130 and outputs normalized data, and an inverse normalizer 1150 which receives minimum among key value data of each component and a maximum value of a component having the maximum range, calculates a maximum range of normalized data, and inversely normalizes the quantized data input from the inverse quantizer 1140 based on the maximum range.
0168The operations and structures of the entropy decoder 1120, the inverse DPCM operator 140/1130, and the inverse quantizer 1140 are the same as the operations and structures of the corresponding elements of the apparatus for decoding data above, and thus their description will not be repeated here. The operation of the inverse normalizer 1150 will be described in the following with reference to <figref idref="f0020">FIG. 12B</figref>.
0169The inverse normalizer 1150 receives the maximum value fMax used for normalization, which is decoded from the input bitstream, the minimum values fMin_X, fMin_Y, and fMin_Z of the x, y, and z components, respectively, the information nWhichAxis on which component axis has a maximum value, and the information bUse32Float on the type of encoding in step S1210.
0170The inverse normalizer 1150 identifies based on bUse32Float whether or not fMax, fMin_X, fMin_Y, and fMin_Z are encoded with IEEE Standard 754 floating-point number format, and if they are not, the inverse normalizer 1150 calculates a maximum value Range<sub>max</sub> in a maximum range using the following equations. If fMax, fMin_X, fMin_Y, and fMin_Z are encoded with 32 bits, the inverse normalizer 1150 determines fMax as Range<sub>max</sub> in step S1220. <maths id="math0025" num="(15)"><math display="block"><mtable columnalign="left"><mtr><mtd><msub><mi mathvariant="italic">Range</mi><mi>max</mi></msub><mo>=</mo><mi mathvariant="italic">fMax</mi><mo>-</mo><mi mathvariant="italic">fMin_X</mi></mtd><mtd><mfenced separators=""><mi mathvariant="italic">if nWhichAxis</mi><mo>=</mo><mn>0</mn></mfenced></mtd></mtr><mtr><mtd><msub><mi mathvariant="italic">Range</mi><mi>max</mi></msub><mo>=</mo><mi mathvariant="italic">fMax</mi><mo>-</mo><mi mathvariant="italic">fMin_Y</mi></mtd><mtd><mfenced separators=""><mi mathvariant="italic">if nWhichAxis</mi><mo>=</mo><mn>1</mn></mfenced></mtd></mtr><mtr><mtd><msub><mi mathvariant="italic">Range</mi><mi>max</mi></msub><mo>=</mo><mi mathvariant="italic">fMax</mi><mo>-</mo><mi mathvariant="italic">fMin_Z</mi></mtd><mtd><mfenced separators=""><mi mathvariant="italic">if nWhichAxis</mi><mo>=</mo><mn>2</mn></mfenced></mtd></mtr></mtable></math><img file="EP1565000B1_D0027.tif" /></maths>
0171If Range<sub>max</sub> is determined, the inverse normalizer 1150 inversely normalizes the data of each of the x, y, and z components based on Range<sub>max</sub> using the following equations in step S1230. <maths id="math0026" num="(16)"><math display="block"><mtable columnalign="left"><mtr><mtd><msub><mover><mi>P</mi><mo>^</mo></mover><mrow><mi>i</mi><mo>,</mo><mi>x</mi></mrow></msub><mo>=</mo><msub><mover><mover><mi>P</mi><mo>˜</mo></mover><mo>^</mo></mover><mrow><mi>i</mi><mo>,</mo><mi>x</mi></mrow></msub><mo>×</mo><msub><mi mathvariant="italic">Range</mi><mi>max</mi></msub><mo>+</mo><mi mathvariant="italic">fMin_X</mi></mtd><mtd><mspace width="1em" /></mtd></mtr><mtr><mtd><msub><mover><mi>P</mi><mo>^</mo></mover><mrow><mi>i</mi><mo>,</mo><mi>y</mi></mrow></msub><mo>=</mo><msub><mover><mover><mi>P</mi><mo>˜</mo></mover><mo>^</mo></mover><mrow><mi>i</mi><mo>,</mo><mi>y</mi></mrow></msub><mo>×</mo><msub><mi mathvariant="italic">Range</mi><mi>max</mi></msub><mo>+</mo><mi mathvariant="italic">fMin_Y</mi></mtd><mtd><mspace width="1em" /></mtd></mtr><mtr><mtd><msub><mover><mi>P</mi><mo>^</mo></mover><mrow><mi>i</mi><mo>,</mo><mi>z</mi></mrow></msub><mo>=</mo><msub><mover><mover><mi>P</mi><mo>˜</mo></mover><mo>^</mo></mover><mrow><mi>i</mi><mo>,</mo><mi>z</mi></mrow></msub><mo>×</mo><msub><mi mathvariant="italic">Range</mi><mi>max</mi></msub><mo>+</mo><mi mathvariant="italic">fMin_Z</mi></mtd><mtd><mfenced separators=""><mi>i</mi><mo>=</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>n</mi></mfenced></mtd></mtr></mtable></math><img file="EP1565000B1_D0028.tif" /></maths>
0172In Equation (16), n represents the number of data.
0173Hereinafter, an apparatus and a method for decoding data will be described with reference to <figref idref="f0021">FIGS. 13A</figref> and <figref idref="f0022">13B</figref>. The apparatus for decoding data decodes a bitstream, into which key value data of a position interpolator representing the location of an object in a three-dimensional animation have been encoded using the method for encoding data according to the present invention.
0174Referring to <figref idref="f0021">FIG. 13A</figref>, the apparatus for decoding data includes a key value header decoder 1110, which decodes information required for decoding from a bitstream, an entropy decoder 1120, which entropy decodes the bitstream input thereinto and thus outputs differential data, an inverse DPCM processor 1130, which performs an inverse circular DPCM operation or an inverse predictive-circular DPCM operation on the differential data input from the entropy decoder 1120 and thus outputs quantized key value data, an inverse quantizer 1140, which inversely quantizes the quantized key value data input from the inverse DPCM processor 1130 and thus outputs normalized key value data, a floating-point number decoder 1160, which receives minimum and maximum values from the key value header decoder 1110, converts minimum values among the key value data of each of the x, y, and z components and the maximum value of a component having the maximum range, into binary numbers, and outputs the binary numbers, and an inverse normalizer 1150, which receives the minimum values among the key value data of each of the x, y, and z components and a maximum value of a component having the maximum range, from the floating-point number decoder 1160, calculates the maximum range from the minimum values and the maximum value from the floating-point number decoder 1160 and then inversely normalizes the key value data input from the inverse quantizer 1140.
0175Hereinafter, a method for decoding data will be described with reference to <figref idref="f0022">FIG. 13B</figref>. Referring to <figref idref="f0022">FIG. 13B</figref>, a bit stream of encoded key value data are input into the entropy decoder 1120 and the key value header decoder 1110. Then, the key value header decoder 1110 decodes header information required for decoding from the bitstream and outputs the decoded header information to the entropy decoder 1120, the inverse DPCM processor 1130, and the inverse quantizer 1140 in step S1300.
0176The entropy decoder 1120 entropy-decodes the bitstream and then outputs differential data to the inverse DPCM processor 1130 in step S1320.
0177<figref idref="f0023">FIG. 14A</figref> is a detailed flowchart of step S1320. Referring to <figref idref="f0023">FIG. 14A</figref>, a bitstream <i><o ostyle="single">P<sub>i</sub></o></i> is input into the entropy decoder 1120 in step S1321. <figref idref="f0026">FIG. 15</figref> is diagram showing the sequence of encoded key value data which are input into the entropy decoder 1120 and are subjected to entropy-decoding.
0178The entropy decoder 1120 checks if key value data of a component, for example, x, have the same quantized value in step S1322. If the key value data of the component have the same quantized value, all symbols of the component are decoded setting them as a minimum value input from the key value header decoder 1110, for example, fMin_X, in step S1323.
0179If the key value data of the component do not have the same quantized value, the entropy decoder 1120 checks if the key value data have been encoded using an unary AAC function, in step S1324. If the key value data have been encoded using an unary AAC function, they are decoded using the unary AAC function in step S1325.
0180The unary AAC function reads 0s from the bitstream until a bit "1" appears, converts the number of 0s into an absolute value, reads a bit next to the bit "1" as the sign of value if the bit is "0", the sign of value is positive, if the bit is "1 ", the sign of value is negative, and outputs a decoded value.
0181If the key value data of the component have not been encoded using the unary AAC function, the entropy decoder 1120 decodes the bitstream, into which the key value data of the component are encoded, using an SQ AAC function, which will be described in the following.
0182The entropy decoder 1120 decodes the signs of all the symbols from the bitstream, decodes the maximum value nMax, and initializes the decoding range of all the symbols (ranging from 0 to nMax) and the flag <maths id="math0027" num=""><math display="inline"><msub><mover><mi>P</mi><mi>‿</mi></mover><mrow><mi>i</mi><mo>⋅</mo><mi mathvariant="italic">found</mi></mrow></msub></math><img file="EP1565000B1_D0029.tif" /></maths> as 'false' in step S1331.
0183Thereafter, the entropy decoder 1120 determines a key value datum to be decoded first (i = nStartlndex) and sets bDone as 'true' in step S1332.
0184The entropy decoder 1120 performs steps S1333 through S1343 again to decode the symbols.
0185In particular, the entropy decoder 1120 checks if the maximum value <maths id="math0028" num=""><math display="inline"><msub><mover><mi>P</mi><mi>‿</mi></mover><mrow><mi>i</mi><mo>⋅</mo><mi>max</mi></mrow></msub></math><img file="EP1565000B1_D0030.tif" /></maths> and the minimum value <maths id="math0029" num=""><math display="inline"><msub><mover><mi>P</mi><mi>‿</mi></mover><mrow><mi>i</mi><mo>⋅</mo><mi>max</mi></mrow></msub></math><img file="EP1565000B1_D0031.tif" /></maths> in the decoding range are the same in step S1333.
0186If <maths id="math0030" num=""><math display="inline"><msub><mover><mi>P</mi><mi>‿</mi></mover><mrow><mi>i</mi><mo>⋅</mo><mi>max</mi></mrow></msub></math><img file="EP1565000B1_D0032.tif" /></maths> and <maths id="math0031" num=""><math display="inline"><msub><mover><mi>P</mi><mi>‿</mi></mover><mrow><mi>i</mi><mo>⋅</mo><mi>min</mi></mrow></msub></math><img file="EP1565000B1_D0033.tif" /></maths> are the same, the symbol to be encoded is determined as a maximum value (or a minimum value) in the decoding range in step S1334, and if not, the entropy decoder 1120 sets bDone as 'false' and renews a middle value nMid in the decoding range following Equation (17) in step S1335.<maths id="math0032" num="(17)"><math display="block"><mi mathvariant="italic">nMid</mi><mo>=</mo><mfrac><mrow><msub><mover><mi>P</mi><mi>‿</mi></mover><mrow><mi>i</mi><mo>⋅</mo><mi>max</mi></mrow></msub><mo>+</mo><msub><mover><mi>P</mi><mi>‿</mi></mover><mrow><mi>i</mi><mo>⋅</mo><mi>min</mi></mrow></msub></mrow><mn>2</mn></mfrac><mo>+</mo><msub><mover><mi>P</mi><mi>‿</mi></mover><mrow><mi>i</mi><mo>⋅</mo><mi>min</mi></mrow></msub><mo>+</mo><mn>1</mn></math><img file="EP1565000B1_D0034.tif" /></maths>
0187The entropy decoder 1120 checks if the context flag <maths id="math0033" num=""><math display="inline"><msub><mover><mi>P</mi><mi>‿</mi></mover><mrow><mi>i</mi><mo>⋅</mo><mi mathvariant="italic">found</mi></mrow></msub></math><img file="EP1565000B1_D0035.tif" /></maths>is true in order to determine a probability model for decoding, in step S1336. If the context flag<maths id="math0034" num=""><math display="inline"><msub><mover><mi>P</mi><mi>‿</mi></mover><mrow><mi>i</mi><mo>⋅</mo><mi mathvariant="italic">found</mi></mrow></msub></math><img file="EP1565000B1_D0036.tif" /></maths> is true, the entropy decoder 1120 decodes the bitstream using FoundContext in step S1337, and if not, the entropy decoder 1120 decodes the bitstream using notFoundContext in step S1338.
0188The entropy decoder 1120, which has decoded one bit from the bitstream, checks if the bit read from the bitstream is 1 in step S1339, and if not, the entropy decoder 1120 replaces the maximum value <maths id="math0035" num=""><math display="inline"><msub><mover><mi>P</mi><mi>‿</mi></mover><mrow><mi>i</mi><mo>⋅</mo><mi>max</mi></mrow></msub></math><img file="EP1565000B1_D0037.tif" /></maths> in the decoding range with the middle value nMid in step S1340. If the bit decoded from the bitstream is 1, the entropy decoder 1120 replaces the minimum value <maths id="math0036" num=""><math display="inline"><msub><mover><mi>P</mi><mi>‿</mi></mover><mrow><mi>i</mi><mo>⋅</mo><mi>min</mi></mrow></msub></math><img file="EP1565000B1_D0038.tif" /></maths> in the decoding range with the middle value nMid and sets the context flag <maths id="math0037" num=""><math display="inline"><msub><mover><mi>P</mi><mi>‿</mi></mover><mrow><mi>i</mi><mo>⋅</mo><mi mathvariant="italic">found</mi></mrow></msub></math><img file="EP1565000B1_D0039.tif" /></maths> as 'true' in step S1341.
0189The entropy decoder 1120 increases the decoding index i by 1 in step S1342, checks if all the key value data of the component are completely decoded in the current stage in step S1343, and performs steps S1333 through S1342 if there are symbols left to be decoded in the current stage.
0190If all the key value data of the current stage have been decoded, the entropy decoder 1120 checks if additional stage is needed to decode key value data of the current components in step S1344 and if so, performs steps S1332 through S1343 again. The entropy decoder checks if all key value data of the current component have been decoded, the entropy decoder starts to decode the key value data of the next component.
0191Referring to <figref idref="f0021">FIGS. 13A</figref> and <figref idref="f0022">13B</figref>, differential data of the key value data decoded by the entropy decoder 1120 are input into the inverse DPCM processor 130, and then the inverse DPCM processor 1130 performs an inverse circular DPCM operation or an inverse predictive-circular DPCM operation on the input differential data depending on the type of DPCM performed. The inverse circular DPCM operation and the predictive-circular DPCM operation are the same as the operation of the aforementioned inverse DPCM operator except that they are performed on the key value data of each of the x, y, and z components, separately.
0192The inverse DPCM processor 1130 outputs quantized key value data<maths id="math0038" num=""><math display="inline"><msub><mover><mi>P</mi><mo>˜</mo></mover><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub></math><img file="EP1565000B1_D0040.tif" /></maths> generated by an inverse DPCM operation to the inverse quantizer 1140, and then the inverse quantizer 1140 inversely quantizes <maths id="math0039" num=""><math display="inline"><msub><mover><mi>P</mi><mo>˜</mo></mover><mrow><mi mathvariant="italic">i</mi><mo>,</mo><mi mathvariant="italic">j</mi></mrow></msub></math><img file="EP1565000B1_D0041.tif" /></maths> using the quantization bits nKeyValueQBits input from the key value header decoder 1110 in step S1370. When n represents the number of key value data input from the key value header decoder 110, the inverse quantization performed in the inverse quantizer 1140 can be expressed by the following equation.<maths id="math0040" num="(18)"><math display="block"><msub><mover><mi>P</mi><mo>^</mo></mover><mi mathvariant="italic">ij</mi></msub><mo>=</mo><mfrac><msub><mover><mi>P</mi><mo>˜</mo></mover><mi mathvariant="italic">ij</mi></msub><mfenced separators=""><msup><mn>2</mn><mi mathvariant="italic">nKeyValueQBits</mi></msup><mo>-</mo><mn>1</mn></mfenced></mfrac><mspace width="2em" /><mfenced separators=""><mi>i</mi><mo>=</mo><mi mathvariant="italic">nStartIndex</mi><mo>,</mo><mo>…</mo><mo>,</mo><mi>n</mi><mo>;</mo><mi>j</mi><mo>=</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo>,</mo><mi>z</mi></mfenced></math><img file="EP1565000B1_D0042.tif" /></maths>
0193The inverse quantizer 1140 generates normalized data by performing inverse quantization on the key value data of each of the x, y, and z components and outputs the normalized key value data of each of the x, y, and z components to the inverse normalizer 1150.
0194The inverse normalizer 1150 inverse normalizes the normalized key value data input from the inverse quantizer 1140 using the information input from the floating-point number decoder 1160.
0195Hereinafter, the inverse normalization of the normalized key value data of each of the x, y, and z components will be described with reference to <figref idref="f0025">FIG. 14C</figref>.
0196The floating-point number decoder 1160 receives the information bUse32Float and checks if bUse32Float is true. If bUse32Float is true, the floating-point number decoder receives the maximum value fMax used for inverse normalization, the minimum values fMin_X, fMin_Y, and fMin_Z among the key value data of each of the x, y, and z components with IEEE Standard 754 floating-point number format, if not, the floating-point number decoder receives the maximum value fMax used for inverse normalization, the minimum values fMin_X, fMin_Y, and fMin_Z among the key value data of each of the x, y, and z components, and receives the information nWhichAxis on which component the maximum value fMax belongs to in step S1382.
0197The floating-point number decoder 1160 converts fMax, fMin_X, fMin_Y, and fMin_Z which are represented in the decimal system into binary numbers following Equation (9) and outputs the converted values to the inverse normalizer 1150 in step S 1384.
0198The inverse normalizer 1150 checks based on bUse32Float if fMax, fMin_X, fMin_Y, and fMin_Z have been encoded into 32 bits. If fMax, fMin_X, fMin_Y, and fMin_Z have been encoded into 32 bits, the inverse normalizer 1150 determines fMax as Range<sub>max</sub> and if not, the inverse normalizer and calculates the maximum value Range<sub>max</sub> in the maximum range following Equation (15) in step S1386.
0199If Range<sub>max</sub> is determined, the inverse normalizer 1150 inversely normalizes the key value data of each of the x, y, and z components based on Range<sub>max</sub>, following Equation (16) in step S1388.
0200Examples of program codes, by which the operation of the apparatus for decoding data according to the third embodiment of the present invention are realized, are shown in <figref idref="f0035 f0036 f0037">FIGS. 24 through 27</figref>.
0201<figref idref="f0035">FIG. 24</figref> shows an example of C++ program codes, into which an inverse circular DPCM operation is realized, and <figref idref="f0035">FIG. 25</figref> shows an example of C++ program codes, by which an inverse predictive-circular DPCM operation is realized.
0202The inverse circular DPCM operation and the inverse predictive-circular DPCM operation all include an inverse circular quantization routine for selecting a certain value in a quantization range.
0203Examples of C++ program codes, by which the operation of an entropy decoder (adaptive arithmetic decoder) is realized, are shown in <figref idref="f0036">FIGS. 26</figref> and <figref idref="f0037">27</figref>. Here, qf_decode( ) represents a function for reading one bit from a bitstream.
0204The present invention can be realized as computer-readable codes written on a computer-readable recording medium. Here, the computer-readable recording medium includes any kind of recording medium which can be read by a computer system. For example, the computer-readable recording medium may be a ROM, a RAM, a CD-ROM, a magnetic tape, a floppy disk, an optical data storage, and carrier wave (transmission through the Internet). The computer-readable recording medium can be transmitted to computer systems connected via a network, and a computer can read the recording medium in a decentralized way.
0205While this invention has been particularly shown and described with reference to preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the scope of the invention as defined by the appended claims.
79 sheets
Sheet 1 Sheet 2 Sheet 3 Sheet 4 Sheet 5 Sheet 6 Sheet 7 Sheet 8 Sheet 9 Sheet 10 Sheet 11 Sheet 12 Sheet 13 Sheet 14 Sheet 15 Sheet 16 Sheet 17 Sheet 18 Sheet 19 Sheet 20 Sheet 21 Sheet 22 Sheet 23 Sheet 24 Sheet 25 Sheet 26 Sheet 27 Sheet 28 Sheet 29 Sheet 30 Sheet 31 Sheet 32 Sheet 33 Sheet 34 Sheet 35 Sheet 36 Sheet 37 Sheet 38 Sheet 39 Sheet 40 Sheet 41 Sheet 42 Sheet 43 Sheet 44 Sheet 45 Sheet 46 Sheet 47 Sheet 48 Sheet 49 Sheet 50 Sheet 51 Sheet 52 Sheet 53 Sheet 54 Sheet 55 Sheet 56 Sheet 57 Sheet 58 Sheet 59 Sheet 60 Sheet 61 Sheet 62 Sheet 63 Sheet 64 Sheet 65 Sheet 66 Sheet 67 Sheet 68 Sheet 69 Sheet 70 Sheet 71 Sheet 72 Sheet 73 Sheet 74 Sheet 75 Sheet 76 Sheet 77 Sheet 78 Sheet 79
Every citation, both ways
| Document | Relation | Office |
|---|---|---|
| WO9903067A | Cites | World Intellectual Property Organization (WIPO) |
| SIGNES J: "Binary format for scene (BIFS): combining MPEG-4 media to build rich multimedia services" PROCEEDINGS OF THE SPIE, SPIE, BELLINGHAM, VA, US, vol. 3653, pt.1-2, 25 January 1999 (1999-01-25), pages 1506-1517, XP002160811 ISSN: 0277-786X | Non-patent | – |
| GERSHO A: "Principles of Quantization" IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS, IEEE INC. NEW YORK, US, vol. CAS-25, no. 7, 1 July 1978 (1978-07-01), pages 427-436, XP002285971 | Non-patent | – |
| KIM J D K ET AL: "Animation data compression in MPEG-4: interpolators" PROCEEDINGS 2002 INTERNATIONAL CONFERENCE ON IMAGE PROCESSING. ICIP 2002. ROCHESTER, NY, SEPT. 22 - 25, 2002, INTERNATIONAL CONFERENCE ON IMAGE PROCESSING, NEW YORK, NY : IEEE, US, vol. VOL. 2 OF 3, 22 September 2002 (2002-09-22), pages 33-36, XP010607503 ISBN: 0-7803-7622-6 | Non-patent | – |
140 members in 7 offices
Priority claims23
| Document | Office | Kind | Date |
|---|---|---|---|
| 33313001 | United States of America | P | |
| 333130P | United States of America | – | |
| 33454101 | United States of America | P | |
| 334541P | United States of America | – | |
| 34210101 | United States of America | P | |
| 342101P | United States of America | – | |
| 36959702 | United States of America | P | |
| 369597P | United States of America | – | |
| 20020067679 | Republic of Korea | A | |
| 2002067679 | Republic of Korea | – | |
| 02258179 | European Patent Office (EPO) | A | |
| EP20020258179 | – | – | – |
| KR20020067679 | – | – | – |
| US20010333130P | – | – | – |
| US20010334541P | – | – | – |
| US20010342101P | – | – | – |
| US20020369597P | – | – | – |
| 333130P | – | – | – |
| 334541P | – | – | – |
| 342101P | – | – | – |
| 369597P | – | – | – |
| 2002067679 | – | – | – |
| 022581797 | – | – | – |
Members140
| Document | Office | Kind | |
|---|---|---|---|
| KR20030043620A | Republic of Korea | A | |
| KR20030043621A | Republic of Korea | A | |
| KR20030043622A | Republic of Korea | A | |
| KR20030043634A | Republic of Korea | A | |
| KR20030043655A | Republic of Korea | A | |
| KR20030043657A | Republic of Korea | A | |
| KR20030043690A | Republic of Korea | A | |
| US2003103572A1 | United States of America | A1 | |
| US2003103573A1 | United States of America | A1 | |
| US2003108107A1 | United States of America | A1 | |
| EP1320264A2 | European Patent Office (EPO) | A2 | |
| EP1320265A2 | European Patent Office (EPO) | A2 | |
| EP1320266A2 | European Patent Office (EPO) | A2 | |
| EP1322118A2 | European Patent Office (EPO) | A2 | |
| EP1322119A2 | European Patent Office (EPO) | A2 | |
| EP1322120A2 | European Patent Office (EPO) | A2 | |
| CN1428742A | China | A | |
| CN1428745A | China | A | |
| US2003128215A1 | United States of America | A1 | |
| US2003128883A1 | United States of America | A1 | |
| US2003128884A1 | United States of America | A1 | |
| CN1431627A | China | A | |
| CN1432971A | China | A | |
| CN1433164A | China | A | |
| EP1331824A2 | European Patent Office (EPO) | A2 | |
| US2003147470A1 | United States of America | A1 | |
| CN1438613A | China | A | |
| JP2003248838A | Japan | A | |
| JP2003248839A | Japan | A | |
| JP2003249856A | Japan | A | |
| CN1441387A | China | A | |
| JP2004007380A | Japan | A | |
| JP2004007392A | Japan | A | |
| JP2004007393A | Japan | A | |
| JP2004030557A | Japan | A | |
| CN1568012A | China | A | |
| CN1187716C | China | C | |
| KR100480787B1 | Republic of Korea | B1 | |
| EP1320265A3 | European Patent Office (EPO) | A3 | |
| EP1322119A3 | European Patent Office (EPO) | A3 | |
| EP1320264A3 | European Patent Office (EPO) | A3 | |
| EP1322120A3 | European Patent Office (EPO) | A3 | |
| CN1206613C | China | C | |
| KR100499135B1 | Republic of Korea | B1 | |
| EP1322118A3 | European Patent Office (EPO) | A3 | |
| EP1564999A2 | European Patent Office (EPO) | A2 | |
| EP1565000A2 | European Patent Office (EPO) | A2 | |
| CN1664863A | China | A | |
| EP1320266A3 | European Patent Office (EPO) | A3 | |
| EP1331824A3 | European Patent Office (EPO) | A3 | |
| EP1592253A1 | European Patent Office (EPO) | A1 | |
| KR20050109413A | Republic of Korea | A | |
| JP2005348395A | Japan | A | |
| KR100537500B1 | Republic of Korea | B1 | |
| JP3733107B2 | Japan | B2 | |
| KR100543697B1 | Republic of Korea | B1 | |
| JP2006033869A | Japan | A | |
| CN1734502A | China | A | |
| JP2006050609A | Japan | A | |
| KR100552665B1 | Republic of Korea | B1 | |
| KR100552666B1 | Republic of Korea | B1 | |
| KR100552710B1 | Republic of Korea | B1 | |
| CN1741392A | China | A | |
| JP3756875B2 | Japan | B2 | |
| KR100561875B1 | Republic of Korea | B1 | |
| US7026960B2 | United States of America | B2 | |
| US2006171533A1 | United States of America | A1 | |
| CN1277239C | China | C | |
| CN1856105A | China | A | |
| CN1878311A | China | A | |
| CN1878312A | China | A | |
| CN1294540C | China | C | |
| EP1565000A3 | European Patent Office (EPO) | A3 | |
| EP1564999A3 | European Patent Office (EPO) | A3 | |
| EP1750447A2 | European Patent Office (EPO) | A2 | |
| US7181071B2 | United States of America | B2 | |
| JP2007052804A | Japan | A | |
| EP1761065A2 | European Patent Office (EPO) | A2 | |
| US2007053600A1 | United States of America | A1 | |
| JP2007066321A | Japan | A | |
| CN1941910A | China | A | |
| CN1310192C | China | C | |
| US7206457B2 | United States of America | B2 | |
| JP3905834B2 | Japan | B2 | |
| US2007116368A1 | United States of America | A1 | |
| CN1320503C | China | C | |
| CN1976473A | China | A | |
| CN101009837A | China | A | |
| JP3953411B2 | Japan | B2 | |
| US2007183674A1 | United States of America | A1 | |
| JP3965360B2 | Japan | B2 | |
| CN100343879C | China | C | |
| JP4002502B2 | Japan | B2 | |
| CN100350433C | China | C | |
| US7336713B2 | United States of America | B2 | |
| JP4070783B2 | Japan | B2 | |
| JP4104615B2 | Japan | B2 | |
| US7406206B2 | United States of America | B2 | |
| CN100414996C | China | C | |
| US7446771B2 | United States of America | B2 |
40 legal events, as 5 offices reported them to INPADOC
Over the term
Point at a mark for the eventEvents
| Event | Code | Office | |
|---|---|---|---|
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Notification of lapseLapsedST | ST | FR | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Gb: european patent ceased through non-payment of renewal feeCeasedGBPC | GBPC | EP | |
| Application deemed withdrawn, or ip right lapsed, due to non-payment of renewal feeWithdrawnR119 | R119 | DE | |
| Annual fee paid to national office [announced via postgrant information from national office to epo]GrantedPGFP | PGFP | EP | |
| No opposition filedOpposition26N | 26N | EP | |
| No opposition filed within time limitOppositionORIGINAL CODE: 0009261PLBE | PLBE | EP | |
| Information on the status of an ep patent application or granted ep patentGrantedSTATUS: NO OPPOSITION FILED WITHIN TIME LIMITSTAA | STAA | EP | |
| No opposition filed against granted patent, or epo opposition proceedings concluded without decisionGrantedR097 | R097 | DE | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Fee paymentPLFP | PLFP | FR | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Discontinued in the netherlands as no translation has been filedVDEP | VDEP | NL | |
| Annual fee paid to national office [announced via postgrant information from national office to epo]GrantedPGFP | PGFP | EP | |
| Annual fee paid to national office [announced via postgrant information from national office to epo]GrantedPGFP | PGFP | EP | |
| Dpma publication of mentioned ep patent grantGrantedR096 | R096 | DE | |
| Divisional application: reference to earlier applicationAC | AC | EP | |
| Designated contracting statesAK | AK | EP | |
| European patent grantedGrantedFG4D | FG4D | GB | |
| (expected) grantORIGINAL CODE: 0009210GRAA | GRAA | EP | |
| Grant fee paidORIGINAL CODE: EPIDOSNIGR3GRAS | GRAS | EP | |
| Intention to grant announcedINTG | INTG | EP | |
| Despatch of communication of intention to grant a patentORIGINAL CODE: EPIDOSNIGR1GRAP | GRAP | EP | |
| Information provided on ipc code assigned before grantRIC1 | RIC1 | EP | |
| Information provided on ipc code assigned before grantRIC1 | RIC1 | EP | |
| Amendment of ipc main classPREVIOUS MAIN CLASS: H04N0007260000R079 | R079 | DE | |
| Party data changed (applicant data changed or rights of an application transferred)RAP1 | RAP1 | EP | |
| First examination report despatched17Q | 17Q | EP | |
| Designation fees paidAKX | AKX | EP | |
| Request for examination filed17P | 17P | EP | |
| Designated contracting statesAK | AK | EP | |
| Request for extension of the european patentAX | AX | EP | |
| Search report despatchedORIGINAL CODE: 0009013PUAL | PUAL | EP | |
| Divisional application: reference to earlier applicationAC | AC | EP | |
| Designated contracting statesAK | AK | EP | |
| Request for extension of the european patentAX | AX | EP | |
| Public reference made under article 153(3) epc to a published international application that has entered the european phaseORIGINAL CODE: 0009012PUAI | PUAI | EP |
Numbers
- Publication
- 1565000
- Publication, DOCDB
- 1565000
- Publication, EPODOC
- EP1565000
- Application
- 5076146
- Application, DOCDB
- 05076146
- Application, EPODOC
- EP20050076146
Titles3
- German
- Verfahren und Vorrichtung zur Datenkodierung und -dekodierung
- English
- Method and apparatus for encoding and decoding data
- French
- Méthode et appareil pour le codage et le décodage de données
Classification
- CPC, 2
- H04N19/98
- H04N19/593
- IPC, 4
- H04N19 98
- H03M7 34
- H04N7 26
- H04N19 593
Designated states6
- Contracting states, 6
- Belgium
- Germany
- Spain
- France
- United Kingdom
- Netherlands (Kingdom of the)