JP6887232B2 - Coding device, coding method, decoding device and decoding method - Google Patents

Description

The present invention relates to a coding device, a coding method, a decoding device and a decoding method.

Conventionally, in the compression of floating point numbers, a technique has been known in which a floating point number to be coded is predicted and the difference information between the coded target value and the predicted value is encoded. In the coding of the mantissa part of the sign part, exponent part, and mantissa part that compose the floating point number, the difference between the mantissa part of the predicted value and the mantissa part of the coded target value is calculated, and the difference value is context-based. There is a method of performing entropy encoding of (see, for example, Non-Patent Document 1). In the technique described in Non-Patent Document 1, a value representing the magnitude of the difference is obtained, and the value is used as a coding context for the difference in the mantissa.

Isenburg, Martin, Peter Lindstrom, and Jack Snoeyink. "Lossless compression of pressed floating-point geometry." Computer-Aided Design 37.8 (2005): 869-877.

In the method described in Non-Patent Document 1, a value representing the magnitude of the difference in the mantissa is used as a context when encoding the difference in the mantissa. Therefore, in order to make the code data obtained in this way decodable, a value representing the magnitude of the difference in the mantissa part is separately encoded and included in the code data, and the coded value is decoded on the decoding side. After that, it is necessary to decode the difference of the mantissa. This can cause a decrease in coding efficiency.

The present invention has been made in view of these problems, and an object of the present invention is a technique capable of suppressing or preventing a decrease in the coding efficiency of the mantissa even when a context is used when entropy-coding a floating-point number. Is in the offer.

One aspect of the present invention relates to a coding device. This coding device includes a mantissa extraction means for extracting a mantissa of a floating point number and a coding means for encoding the extracted mantissa. The coding means identifies the probabilistic model based on the fixed decimal representation of the digits corresponding to at least some of the extracted mantissa digits, and uses the identified probabilistic model to code at least some of the digits. To be.

Another aspect of the present invention is a decoding device. This decoding device decodes the exponential decoding means for decoding the encoded floating-point exponent and the fixed decimal representation digit corresponding to the mantissa digit of the encoded floating-point number to be decoded. It includes a determination means for determining from an exponent, and a mantissa decoding means for specifying a probability model based on the determined place of a fixed decimal representation and decoding the place of the decoding target using the specified probability model.

According to the present invention, even when a context is used when entropy-coding a floating-point number, it is possible to suppress or prevent a decrease in the coding efficiency of the mantissa.

Explanatory drawing which shows the single precision floating point representation of IEEE754. An explanatory diagram showing the correspondence between the sign part, the exponent part, the mantissa part and the real number of the floating point number. The block diagram which shows the function and structure of the coding apparatus which concerns on 1st Embodiment. The block diagram which shows the example of the hardware composition of the coding apparatus of FIG. The flowchart which shows the flow of a series of processing in the coding apparatus of FIG. The flowchart which shows the detail of the coding step of the mantissa part of FIG. An explanatory diagram showing a table showing the correspondence between an exponent, a context number, and a place in a fixed decimal representation. The block diagram which shows the function and structure of the decoding apparatus which concerns on 2nd Embodiment. The flowchart which shows the flow of a series of processing in the decoding apparatus of FIG. FIG. 10A is an explanatory diagram of surface information, and FIG. 10B is an explanatory diagram of vertex coordinates. The block diagram which shows the function and structure of the 3D processing apparatus which concerns on 4th Embodiment. The flowchart which shows the flow of a series of processing in a 3D processing apparatus. The figure which plotted the decimal place of the fixed decimal representation on the horizontal axis and the appearance probability of 1 on the vertical axis. The flowchart which shows the flow of the generation process of the difference information which concerns on a modification.

Hereinafter, embodiments of the present invention will be described with reference to the drawings. However, the embodiments of the present invention are not limited to the following embodiments. The same or equivalent components, members, and processes shown in the drawings shall be designated by the same reference numerals, and redundant description will be omitted as appropriate. In addition, some of the members that are not important for explanation are omitted in each drawing.

Before going into the description of the embodiments, the widely used IEEE754 floating point representation and context-based entropy encoding will be described to aid understanding.

FIG. 1 is an explanatory diagram showing a single precision floating point representation of IEEE 754. In the floating point representation of IEEE754, in the case of single precision, the upper 1 bit constitutes the sign unit S, the next upper 8 bits constitutes the exponential part E, and the remaining 23 bits form the mantissa part M, as shown in FIG. When the floating point number F is expressed using S, E, and M, the following equation 1 is obtained.

FIG. 2 is an explanatory diagram showing the correspondence between the sign unit S, the exponent part E, the mantissa part M, and the real number of the floating point number. The sign part S specifies the positive / negative, and the exponential part E specifies the section having a width different by twice, such as the section [1, 2) if 127 and the section [2, 4) if 128. mantissa M identifies a section of a further 2 ²³ divides the specified interval. In the double precision of IEEE754, the exponent part is 11 bits and the mantissa part is 52 bits, and there are other expressions having different expressions such as no exponent part and the radix is not 2. However, the basic idea of floating point representation is as described above.

Next, context-based entropy coding will be described. In entropy coding, the optimum code is assigned according to the appearance probability (probability model) of the symbol to be coded, and the amount of data is reduced. Since the lower limit of the amount of data per symbol after entropy encoding is the entropy of the symbol, it is important to perform data processing so that the entropy becomes small in order to reduce the amount of data. At this time, the entropy becomes smaller when the symbol appearance probability is biased. Entropy coding includes, for example, Huffman coding, Golomulais coding, arithmetic coding and the like.

The context represents a precondition for the probability of occurrence, and if appropriate preconditions are selected, data with different means and variances can be separated from the original data set. That is, the appearance probability can be easily biased. Therefore, the introduction of context can be expected to reduce entropy. In context-based entropy coding, the coding target is classified into multiple categories according to their meaning and state, a context number is assigned to each category, and the coding target is entropy-coded based on the occurrence probability managed for each context number. Will be done.

[First Embodiment]
In the present embodiment, when the floating point number to be encoded and the predicted value thereof are obtained, the floating point number is encoded using the predicted value. Here, it is assumed that the floating point number is represented by the single precision of IEEE754. However, the representation of floating point numbers is not limited to IEEE754, and the technical idea according to the present embodiment can be applied to all floating point representations by corresponding to individual properties.

In this embodiment, as a context for coding the mantissa part of the floating point number, the place of the fixed decimal representation that can be obtained from the exponent part of the floating point number is used. As a result, the code data for the context can be eliminated without degrading the performance of the context separation of the coded target, and the compression performance is improved.

FIG. 3 is a block diagram showing the functions and configurations of the coding device 301 according to the first embodiment. When the floating point number A to be encoded and the predicted value P thereof are input, the coding device 301 outputs the code data of the floating point number A to be encoded. The coding device 301 includes a target acquisition unit 302, a prediction acquisition unit 303, a code / exponential extraction unit 304, a mantissa extraction unit 305, a code / exponential difference generation unit 306, a mantissa difference generation unit 307, and a mantissa division. A unit 308, a coding unit 309, and a code output unit 310 are provided.

The target acquisition unit 302 acquires a floating point number A to be encoded. The target acquisition unit 302 outputs the acquired floating point number A to the sign / exponential extraction unit 304 and the mantissa extraction unit 305. The prediction acquisition unit 303 acquires the predicted value P of the floating point number A acquired by the target acquisition unit 302. The prediction acquisition unit 303 outputs the acquired predicted value P to the code / exponential extraction unit 304 and the mantissa extraction unit 305.

The code / exponential extraction unit 304 extracts the value SA of the code unit and the value EA of the exponent unit from the floating point number A output from the target acquisition unit 302. The code / exponential extraction unit 304 outputs the extracted values SA and EA to the code / exponential difference generation unit 306. The code / exponential extraction unit 304 extracts the value SP of the code unit and the value EP of the exponent unit from the predicted value P output from the prediction acquisition unit 303. The code / exponential extraction unit 304 outputs the extracted values SP and EP to the code / exponential difference generation unit 306.

The mantissa extraction unit 305 extracts the value MA of the mantissa from the floating point A output from the target acquisition unit 302. The mantissa extraction unit 305 outputs the extracted value MA to the mantissa difference generation unit 307. The mantissa extraction unit 305 extracts the value MP of the mantissa from the predicted value P output from the prediction acquisition unit 303. The mantissa extraction unit 305 outputs the extracted value MP to the mantissa difference generation unit 307.

The sign / exponential difference generation unit 306 calculates the difference between the value SA of the sign part of the floating point number A and the value SP of the sign part of the predicted value P. The sign / exponential difference generation unit 306 calculates the difference between the value EA of the exponential part of the floating point number A and the value EP of the exponent part of the predicted value P. The code / exponential difference generation unit 306 outputs a difference signal SD representing the calculated difference of the code unit and the difference of the exponent unit to the mantissa difference generation unit 307. The code / exponential difference generation unit 306 outputs the difference signal SD and the context CTX1 for coding the difference signal SD to the coding unit 309. The handling of the difference signal SD and the context will be described later.

The mantissa difference generation unit 307 monitors the difference signal SD generated by the code / exponential difference generation unit 306, and whether the sign part and the exponent part of the floating point A match the sign part and the exponent part of the predicted value P, respectively. Determine if this is not the case. In the former case, the mantissa difference generation unit 307 calculates the difference MD between the value MA of the mantissa part of the floating point A and the value MP of the mantissa part of the predicted value P. The mantissa difference generation unit 307 outputs the calculated difference of the mantissa part to the mantissa division unit 308. In the latter case, the mantissa difference generation unit 307 outputs the value MA of the mantissa part of the floating point A to the mantissa division unit 308 as it is without calculating the difference.

The mantissa division unit 308 divides the output of the mantissa difference generation unit 307 (the difference MD of the mantissa part or the value MA of the mantissa part of the floating point A) into bit units and outputs it to the coding unit 309 together with the context CTX2. The coding unit 309 specifies the probabilistic model to be applied in the entropy coding of the input value according to the context. The coding unit 309 entropy-codes the input value using the specified probability model, and outputs the code CD to the code output unit 310. The code output unit 310 outputs the input code.

The coding unit 309 is realized by utilizing "Arithmetic coding for data compression" of Witten et al. Described in Non-Patent Document 1. Specifically, the coding unit 309 is described in Fig. 1 of Non-Patent Document 1. Corresponds to the compress function in the pseudo code described in 4, and the argument ac is the argument that receives the context and the sym is the argument that receives the symbol to be encoded. In this pseudo code, the ArithmeticCoder structure, which is a type of the argument ac representing the context, manages the appearance probability of each symbol. Each time the symbol is encoded, the probability of occurrence of the symbol managed by the selected object is updated. Therefore, by passing different objects according to the context number, context separation is realized. The coding means in the coding unit 309 is not limited to the above, and if it is lossless coding, it may be realized by using other arithmetic coding, run length coding, or the like.

Each part of the coding apparatus 301 shown in FIG. 3 may be composed of hardware, but may be implemented as software (computer program). In this case, this software is installed in the memory of a general computer such as a PC (personal computer). Then, when the CPU of this computer executes the installed software, this computer realizes the function of the above-mentioned coding device 301.

FIG. 4 is a block diagram showing an example of the hardware configuration of the coding device 301 of the present embodiment. The coding device 301 is realized as a computer. The computer includes a CPU 1201, a RAM 1202, a ROM 1203, a keyboard 1204, a mouse 1205, a display device 1206, an external storage device 1207, a storage medium drive 1208, an I / F 1209, and a bus 1210. The CPU 1201 controls the entire computer by using the computer programs and data stored in the RAM 1202 and the ROM 1203, and also executes the above-described processes described as those performed by each part of the coding device 301.

The RAM 1202 is an example of a computer-readable storage medium. The RAM 1202 has an area for temporarily storing computer programs and data loaded from an external storage device 1207, a storage medium drive 1208, and a network interface (not shown). Further, the RAM 1202 has a work area used by the CPU 1201 to execute various processes. That is, the RAM 1202 can appropriately provide various areas. In particular, the RAM 1202 includes a coding buffer described later. The ROM 1203 is an example of a computer-readable storage medium, and stores computer setting data, a boot program, and the like.

The keyboard 1204 and the mouse 1205 can be operated by a computer operator to input various instructions to the CPU 1201. The display device 1206 is composed of a CRT, a liquid crystal screen, or the like, and can display the processing result by the CPU 1201 as an image, characters, or the like.

The external storage device 1207 is an example of a computer-reading storage medium, and is a large-capacity information storage device typified by a hard disk drive device. The external storage device 1207 stores an OS (operating system), computer programs and data for realizing each process shown in FIG. 3 in the CPU 1201, various tables, a database, and the like. The computer programs and data stored in the external storage device 1207 are appropriately loaded into the RAM 1202 according to the control by the CPU 1201, and are processed by the CPU 1201.

The storage medium drive 1208 reads out computer programs and data recorded on a storage medium such as a CD-ROM or DVD-ROM, and outputs the read computer programs and data to an external storage device 1207 or RAM 1202. It should be noted that a part or all of the information described as being stored in the external storage device 1207 may be recorded in the storage medium and read by the storage medium drive 1208.

The I / F 1209 is an interface for inputting a floating point number or the like from the outside and outputting code data, and is, for example, a USB (Universal Social Bus) interface. The bus 1210 connects the above-mentioned parts.

In the above configuration, when the power of the computer is turned on, the CPU 1201 loads the OS from the external storage device 1207 into the RAM 1202 according to the boot program stored in the ROM 1203. As a result, the information input operation can be performed via the keyboard 1204 and the mouse 1205, and the GUI can be displayed on the display device 1206. When the user operates the keyboard 1204 or the mouse 1205 and inputs the start instruction of the coding application stored in the external storage device 1207, the CPU 1201 loads the program into the RAM 1202 and executes it. As a result, the computer functions as the coding device 301.

The coding application program executed by the CPU 1201 basically includes a function corresponding to each part belonging to the coding device 301 of FIG. Here, the coding process result is stored in the external storage device 1207. It is clear from the following description that this computer can be similarly applied to the coding device and the decoding device according to each of the following embodiments.

The operation of the coding device 301 with the above configuration will be described.
FIG. 5 is a flowchart showing a flow of a series of processes in the coding apparatus 301. In S401, the coding device 301 acquires the floating point number A to be coded and its predicted value P. In S402, the coding device 301 separates the floating point number A into the sign unit SA, the exponent part EA, and the mantissa part MA, and separates the predicted value P into the sign part SP, the exponent part EP, and the mantissa part MP. In S403, the coding device 301 encodes the code portion SA and the exponent portion EA of the floating point number A. The coding method here may be any method as long as the code portion SA and the exponential part EA can be restored on the decoding side, and the code part SA and the exponential part EA may be coded independently or may be coded with a dependency relationship. It may be converted. As the coding method, for example, the method described in Non-Patent Document 1 may be adopted. Non-Patent Document 1 discloses a mechanism for collectively outputting the difference information between the code portion and the exponent part obtained by using the code part and the exponent part into one code. The exponent part of the predicted value is used for the coding context at this time. In S404, the coding device 301 encodes the mantissa portion MA of the floating point A.

The correspondence between the block shown in FIG. 3 and the processing shown in FIG. 5 is as follows. S401 is performed by the target acquisition unit 302 and the prediction acquisition unit 303. S402 is performed by the code / exponential extraction unit 304 and the mantissa extraction unit 305. S403 is performed by the code / exponential difference generation unit 306 and the coding unit 309. S404 is performed by the mantissa difference generation unit 307, the mantissa division unit 308, and the coding unit 309.

FIG. 6 is a flowchart showing the details of the coding step S404 of the mantissa portion MA of FIG. In S501, in the mantissa difference generation unit 307, does the sign part SA of the floating point A and the sign part SP of the predicted value P match, and does the exponent part EA of the floating point A and the exponent part EP of the predicted value P match? To judge. The mantissa difference generation unit 307 calculates the difference in the mantissa part (MD = MA-MP) in S502 when both the sign part and the exponent part match (YES in S501). If the mantissa difference generation unit 307 does not match (NO in S501), the mantissa difference generation unit 307 proceeds to S504 without calculating the difference MD. The reason for this will be explained. As shown in FIG. 2, in floating point representation, a rough region of a value is specified by a sign and an exponent, and a detailed value is specified by a mantissa. Therefore, if there is an error in the prediction of the sign and exponent, it is highly probable that the prediction of the mantissa will be significantly different, and it cannot be expected that the entropy will decrease by obtaining the difference. Therefore, in the present embodiment, when the exponent part and the mantissa part of the floating point number A to be coded do not match those of the predicted value P, the difference in the mantissa part is not calculated to eliminate the waste of processing.

The difference MD of the mantissa is the difference between the MA expressed in 23 bits and the MP expressed in 23 bits, and is expressed in 24 bits. In S503, the mantissa difference generation unit 307 converts the MD represented by 24 bits into the non-negative 23 bit representation MD'. This conversion may be reversible and satisfy the above-mentioned properties, and may be realized by, for example, a modulo operation. After that, the mantissa difference generation unit 307 sets MD'in the coding buffer. The coding buffer represents a 23-bit work area for coding processing. In S504, the mantissa difference generation unit 307 sets the mantissa part MA of the floating point A in the coding buffer. In S505, the coding unit 309 independently encodes each bit of MD'or MA set in the coding buffer. At this time, the context number of the nth bit from the bottom (n is an integer of 0 or more) is EA + n. The reason for setting the context number to EA + n will be described below.

In Non-Patent Document 1, a floating-point exponent to be encoded is used as a context for encoding a value representing the magnitude of the difference in the mantissa. In floating point representation, the exponent determines the place of the fixed decimal representation corresponding to the mantissa. The larger the exponent, the higher the place of the fixed decimal representation corresponding to the mantissa, and the lower the precision of the represented value. Then, when the prediction accuracy when expressed as a fixed decimal is constant, when the exponent when expressed as a floating point is large and / or the higher place in the mantissa is, the prediction is easier to hit and the difference is likely to be smaller. .. Therefore, in Non-Patent Document 1, since the correlation between the exponent part of the floating point number to be encoded and the value representing the magnitude of the difference between the mantissa part is high, the exponent part is used as the context.

However, if the exponential part EA of the floating point number A is used as a context when coding each bit of MD'as in the method described in Non-Patent Document 1, the probability model is appropriately switched depending on the context. Absent. When finding the prediction difference of the mantissa, it is difficult to predict even the lower bits, and the higher the difference in the mantissa, the higher the probability that it will be 0. Will appear. That is, the distribution of values, for example, the probability of occurrence of 0 differs depending on whether the difference in the mantissa is higher or lower. Therefore, it is not efficient to have the high-order bit and the low-order bit as one context.

As described above, assuming that the prediction accuracy when expressed with a fixed decimal is always constant, the appearance ratio of 0 and 1 of each bit of the difference of the mantissa is the place of the fixed decimal representation to which the bit corresponds. It is decided. For example, if the prediction accuracy is ± 0.25, ^{the difference to the second decimal place (2-2} place) in the fixed decimal representation is almost 0, and 0 and 1 become lower from there. The appearance rate approaches randomly. Due to this property, the context may be the position of the fixed decimal representation corresponding to the position of interest in the mantissa part of the floating point representation, and the context is EA + n.

FIG. 7 is an explanatory diagram showing a table showing the correspondence between the exponent EA, the context number, and the place in the fixed decimal representation. m ₁ represents a bit at which n = 15 when the exponent is 127, and m ₂ represents a bit at n = 16 when the exponent is 126. Both of these are fixed decimal representations and correspond to the eighth decimal place, and 142, which has the same context number, is assigned. Therefore, the _{probability model used when the bits of m 1} are entropy-encoded and the probability model used when _{the bits of m 2} are entropy-encoded are the same.

However, it is necessary to separate the contexts when the difference between the mantissa parts is taken and when the difference is not taken, because different symbols have different appearance probabilities even if EA + n has the same value. Since EA + n takes the range of 0 to 255 + 22 = 277, this is realized by adding 278 to the above context number only when no difference is taken.

In addition, the probability of appearance of the symbol differs depending on whether or not all the positions higher than the position of interest are 0. If all the high-order digits are 0, the probability that the symbol to be encoded becomes 0 is high, and if not, it is predicted that the probability is close to random. Therefore, the context is separated depending on whether or not all the positions higher than the position of interest are 0.

As mentioned above, by making the context for coding the mantissa part of the floating point depend on the already encoded exponent part instead of the magnitude of the difference in the mantissa part, a separate sign is output for the context. The context can be reproduced at the time of decoding without doing so. As a result, the mantissa part of the floating point number can be coded efficiently.

Further, according to the coding device 301 according to the present embodiment, context-based entropy coding that does not require the code data for the context to be output separately is realized. Therefore, it is possible to suppress or prevent a decrease in the coding efficiency of the mantissa.

In the first embodiment, for the sake of simplicity, the case where all the mantissa parts correspond to the decimal place of the fixed decimal place has been described, but the present invention is not limited to this, and the same applies to the case where the mantissa part corresponds to the decimal place. Context separation can be done.

[Second Embodiment]
The decoding device according to the second embodiment decodes the code data obtained as a result of the coding by the coding device 301 according to the first embodiment, and reconstructs the floating point number A. In this example, the case where the mantissa part MA of the floating point number A is encoded as it is by the coding apparatus 301 and the code data obtained as a result is decoded will be described. The configuration for decoding the code data corresponding to the difference MD of the mantissa part of the floating point A is an extension of the present embodiment which is obvious to those skilled in the art who have touched the present specification.

FIG. 8 is a block diagram showing the functions and configurations of the decoding device 150 according to the second embodiment. The decoding device 150 includes a code data acquisition unit 151, an exponential decoding unit 152, a decimal place determination unit 153, and a mantissa decoding unit 154.

The code data acquisition unit 151 acquires the code data generated by the coding device 301. The exponential decoding unit 152 decodes the code unit and the exponential unit from the code data acquired by the code data acquisition unit 151. The decimal place determination unit 153 selects the place of the mantissa part to be decoded from the code data. The decimal place determination unit 153 determines the place of the fixed decimal representation corresponding to the selected decimal place of the decoding target from the exponent obtained by the decoding by the exponential decoding unit 152. The mantissa decoding unit 154 specifies a probability model based on the place of the fixed decimal representation determined by the decimal place determination unit 153, and decodes the place to be decoded using the specified probability model.

FIG. 9 is a flowchart showing a flow of a series of processes in the decoding device 150 of FIG. In S951, the code data acquisition unit 151 acquires the code data. In S952, the exponential decoding unit 152 decodes the code unit and the exponential unit of the acquired code data. In S953, the decimal place determination unit 153 selects the place to be decoded from the mantissa part of the code data. In S954, the decimal place determination unit 153 determines the place of the fixed decimal representation corresponding to the place of the decoding target by adding the number of digits of the digit of the decoding target selected in step S953 to the exponent obtained in step S952. To do. In S955, the mantissa decoding unit 154 determines the context number based on the determined place of the fixed decimal representation. In S956, the mantissa decoding unit 154 decodes the digit to be decoded using the probability model corresponding to the determined context number. In S957, the mantissa decoding unit 154 determines whether or not all the digits of the mantissa part have been decoded. If the undecrypted position remains, the process returns to step S953. If all the digits have been decoded, the decoding device 150 outputs the floating point number A represented by the decoded code part, exponent part, and mantissa part in S958.

According to the decoding device 150 according to the present embodiment, the context can be reproduced without decoding the code separately for the context at the time of decoding. As a result, the mantissa part of the floating point number can be efficiently decoded.

[Third Embodiment]
In the first embodiment, a case where a value represented by 23 bits is set in the coding buffer and each bit is independently encoded as a binary signal has been described. In the third embodiment, the 23-bit value is divided into three partitions, so that the mantissa is encoded as a multi-valued signal.

The difference between the present embodiment and the first embodiment is mainly the process of coding the value of the coding buffer performed by the mantissa division unit 308 and the coding unit 309 (step S505 in FIG. 6). Hereinafter, the details of the process corresponding to step S505 of FIG. 6 will be described. Other processes and configurations are in accordance with the first embodiment.

The mantissa division unit according to the third embodiment divides the 23-bit value registered in the coding buffer into three partitions of upper 8 bits, middle 8 bits, and lower 7 bits. That is, there is a partition boundary between the 7th bit and the 8th bit counting from the bottom of 23 bits, and another partition boundary between the 15th bit and the 16th bit. The method of division is not limited to this, and may be arbitrarily divided into, for example, two divisions of 13 bits and 12 bits, or may be divided into four or more partitions.

When encoding each partition, the coding unit of the third embodiment processes the place of the fixed decimal representation corresponding to the least significant bit as a context. Therefore, a context number of EA is assigned to the lower 7 bits, EA + 7 is assigned to the middle 8 bits, and EA + 15 is assigned to the upper 8 bits. However, since the upper / middle bits, which are 8 bits, and the lower bits, which are 7 bits, have different numbers of digits, they may be treated as independent contexts. The coding method in the coding unit conforms to the coding method in the first embodiment.

In the present embodiment, since the coding process is performed on an 8-bit or 7-bit multi-valued symbol, it is possible to realize coding using the correlation between adjacent bits. As a result, it can be expected that the coding performance will be improved as compared with the first embodiment. Further, the alternative coding method includes universal coding such as Golomlayis code, Huffman code, ZIP compression, etc. in addition to arithmetic coding, which makes it easier to handle.

For example, when performing context separation by Huffman coding, there are a method of constructing a Huffman table for each context, a method of encoding symbols independently for each context, and the like.

According to the coding apparatus according to the third embodiment, the value can be processed in a coding unit close to 8 bits, which is easy to handle in computer processing, and the processing efficiency can be improved. Further, improvement in coding performance can be expected.

Since it is harder to predict the lower 7 bits than the upper 8 bits and the middle 8 bits, the mantissa difference generator uses the mantissa part MA of the floating point A and the mantissa part MP of the predicted value P for the lower 7 bits. It is not necessary to generate the difference of.

[Fourth Embodiment]
In the fourth embodiment, the apex coordinates of the 3D polygon are coded by using the coding device described in the first or third embodiment. The 3D polygons handled in this embodiment are represented as a set of triangular patches. Each patch is composed of surface information and vertex coordinates, and these are collectively called shape information.

FIG. 10A is an explanatory diagram of surface information. FIG. 10B is an explanatory diagram of vertex coordinates. To represent one triangle patch, it is necessary to specify the coordinates of the vertices of the triangle. However, in the 3D polygon, since a plurality of triangles share the same vertex coordinates, the unique vertex coordinates are managed as a list, and each triangle has a vertex ID for referring to the vertex. Specifically, the IDs of the vertices of each triangle are managed by the table shown in FIG. 10 (A). The vertex coordinates are managed by a table that holds the XYZ components of the coordinates of each vertex shown in FIG. 10 (B). Here, the vertex ID is represented by a 4-byte unsigned integer, and the vertex coordinates are represented by a single-precision floating point (4 bytes) of IEEE754.

FIG. 11 is a block diagram showing the functions and configurations of the 3D processing apparatus 800 according to the fourth embodiment. The 3D processing device 800 includes a shape information acquisition unit 801, a surface information extraction unit 802, a vertex coordinate extraction unit 803, a surface information coding unit 804, a vertex coordinate prediction unit 805, a floating fraction coding unit 806, and the like. A code output unit 807 and a 3D data generation unit 808 are provided.

The 3D data generation unit 808 generates 3D polygons based on user input or the like. The 3D data generation unit 808 generates shape information representing a 3D polygon in the form of a table shown in FIGS. 10 (A) and 10 (B). The shape information acquisition unit 801 acquires the shape information generated by the 3D data generation unit 808, and outputs the acquired shape information to the surface information extraction unit 802 and the vertex coordinate extraction unit 803. The surface information extraction unit 802 extracts surface information from the shape information acquired by the shape information acquisition unit 801 and converts it into a data structure that is easy to encode. The surface information extraction unit 802 outputs the converted data to the surface information coding unit 804. The vertex coordinate extraction unit 803 extracts the vertex coordinates from the shape information acquired by the shape information acquisition unit 801. The vertex coordinate extraction unit 803 outputs the extracted vertex coordinates to the vertex coordinate prediction unit 805 and the floating point coding unit 806.

The surface information coding unit 804 encodes the surface information extracted by the surface information extraction unit 802, outputs the code data to the code output unit 807, and at the same time, the adjacency relationship and vertices of the surfaces and vertices constructed at the time of coding. Auxiliary information such as the coding order of is output to the vertex coordinate prediction unit 805. The vertex coordinate prediction unit 805 predicts the coordinates of each vertex from the coordinates of the vertices encoded earlier based on the auxiliary information. The vertex coordinate prediction unit 805 outputs the predicted coordinates of each vertex obtained as a result of the prediction to the floating point coding unit 806. The floating point coding unit 806 uses the predicted coordinates input from the apex coordinate prediction unit 805 to encode the floating point input from the apex coordinate extraction unit 803 in the order obtained earlier, and encodes the code data into a code output unit. Output to 807. The floating point coding unit 806 corresponds to the coding device 301 of FIG. The code output unit 807 multiplexes the input code data and outputs it to the outside.

The operation of the 3D processing apparatus 800 with the above configuration will be described.
FIG. 12 is a flowchart showing a flow of a series of processes in the 3D processing apparatus 800. In S901, the 3D processing device 800 acquires shape information. In S902, the 3D processing apparatus 800 extracts surface information from the shape information and encodes the extracted surface information. Many techniques have been proposed for coding surface information. For example, "Triangle Mesh Compression" by Touma et al., "TFAN: A low complexity 3D mesh compression algorithm" by Mamoo et al., Etc. may be used.

In S903, the 3D processing apparatus 800 generates predicted vertex coordinates based on the coding order of the vertex coordinates. If the prediction of the vertex coordinates is simple, the vertex coordinates encoded immediately before can be used as the prediction. Alternatively, the parallelogram prediction described in Non-Patent Document 1 may be used. In S904, the 3D processing apparatus 800 encodes the vertex coordinates using the predicted vertex coordinates. In S905, the 3D processing device 800 outputs code data.

The correspondence between the block of FIG. 11 and the process of FIG. 12 is as follows. S901 is performed by the shape information acquisition unit 801. S902 is performed by the surface information extraction unit 802 and the surface information coding unit 804. S903 is performed by the vertex coordinate extraction unit 803 and the vertex coordinate prediction unit 805. S904 is performed by the floating point encoding unit 806. The code output unit 807 performs S904.

According to the 3D processing apparatus 800 according to the fourth embodiment, in the processing of the 3D polygon, the same effects as those exerted by the coding apparatus according to the first or third embodiment are exhibited. ..

[Modified example of the fourth embodiment]
A method for improving the coding apparatus suitable for the fourth embodiment will be described. In the fourth embodiment, the vertex coordinates of the 3D shape information are input to the coding device. The vertex coordinates consist of floating point numbers of three components (X, Y, Z) in 3D space, and each component has a different density and appearance range of the floating point numbers. Therefore, the distribution of symbols that appear for each component is different. Therefore, in this modification, the coding context is separated for each XYZ component.

In addition, as a property often seen in the vertex coordinates of 3D shape information, even if the representation range of floating point numbers (the range that can be represented by the mantissa part) is below a certain number when considered in fixed decimal representation, it may always be 0. .. In FIG. 13, the horizontal axis plots the decimal place of the fixed decimal representation (if 5 is the fifth decimal place), and the vertical axis plots the probability of occurrence of 1 (here, since binary representation is assumed, 0 if it is not 1). It is a figure that was made. This was calculated based on the X component of the vertex coordinates extracted from Cassini (http://nasa3d.arc.nasa.gov/dateil/cassini) of NASA 3D Resources published by NASA. All the numbers below the 31st decimal place are 0. Other similar properties were confirmed in the dataset published by Stanford University. Possible factors for this include information loss due to data conversion between ASCII and binary, approximation processing for improving CAD data processing efficiency, and the accuracy limit of the shape acquisition sensor.

Therefore, when it comes to Cassini data, it is not necessary to take a difference between the 31st and lower decimal places of the mantissa. Originally, when coding by taking the difference of the mantissa, even in the difference data, the 31st decimal place and below should always be 0. However, due to the modulo operation for eliminating the redundancy of the difference information, a signal of 1 may appear at a position corresponding to the 31st decimal place or less at the time of coding. Therefore, the coding efficiency can be lowered by taking the difference.

In view of the above circumstances, in the floating point coding process, a mechanism that does not take a difference with respect to the digits below the predetermined digit is adopted. As a process, S502 and S503 shown in FIG. 6 are replaced with S1101 to S1108 of FIG. FIG. 14 is a flowchart showing the flow of the difference information generation process according to the modified example.

_{T min} is defined as a variable for managing a specific place that is a threshold for taking a difference, and _{the initial value of T min} is set to 277. In S1101, the mantissa difference generation unit according to this modification _{obtains G = T min} −EA. However, if G is smaller than 0, G is set to 0, and if G is larger than 23, G is set to 23. In S1102, the mantissa difference generation unit calculates a difference between the upper (23-G) high order bits (23-G) bit and MP of MA, the calculation result to _{D U.} In S1103, the mantissa difference generation unit converts the _{D U} reversible non-negative in (23-G) bit representations _{D Um.} In S1104, the mantissa difference generator sets _DUm in the upper (23-G) bit of the coding buffer and sets the lower G bit of MA in the lower G bit of the coding buffer. In S1105, the mantissa difference generation unit specifies the _{least significant bit b min} , which is the least significant bit among the MA digits having a value of 1. In S1106, the mantissa difference generation unit _calculates a _{t min} by t _min = EA _{+ b} min. In S1107, the mantissa difference generator compares _{t min} with T _min. When t _min <T _min , the mantissa difference generator updates T _{min in S1108 with T min} = t _min. The _{process ends when t min} ≥ T _{min in} S1107 or after the process in S1108.

According to the processing of this modification, it is possible to perform coding without taking a difference for a fixed decimal place that is provisionally all 0s, and it is possible to suppress or prevent a decrease in coding efficiency. .. In this modification, the case where the range where the difference is not taken is updated every time the vertex coordinates are coded has been described, but the present invention is not limited to this. For example, the lower 7 bits of the mantissa may not take a difference, and the upper 16 bits may take a difference.

In the fourth embodiment, a method of compressing 3D shape information using a floating point encoding device is realized. Further, it is possible to make improvements according to the properties peculiar to 3D shape information. With such a configuration, it is possible to realize predictive coding of floating-point numbers without reducing efficiency even for floating-point numbers in which the information of the lower bits is missing.

The configuration and operation of the apparatus according to the embodiment have been described above. It will be understood by those skilled in the art that these embodiments are examples, and that various modifications are possible for each of the components and combinations of each process, and that such modifications are also within the scope of the present invention. ..

In the fourth embodiment, the coding of the apex coordinates of the 3D shape has been described, but the present invention is not limited to this, and the fourth embodiment is applied to an application in which the object to be coded is represented by a floating point number and its predicted value can be obtained. The technical idea relating to the embodiment of the above can be applied. For example, a texture map (UV map) expressing a texture of a 3D shape, a normal vector, an HDR image expressed by a floating point number, a distance image, and a system for handling audio data are also included in the technique according to the fourth embodiment. The idea can be applied.

In the fourth embodiment, the context is separated for each of the three components of XYZ of the 3D data, but the present invention is not limited to this. For example, in the case of an HDR image, the context is separated for each color space component such as RGB or CMY. You may.

(Other Examples)
The present invention supplies a program that realizes one or more functions of the above-described embodiment to a system or device via a network or storage medium, and one or more processors in the computer of the system or device reads and executes the program. It can also be realized by the processing to be performed. It can also be realized by a circuit (for example, ASIC) that realizes one or more functions.

301 Encoding device, 302 Target acquisition unit, 303 Prediction acquisition unit, 304 Sign / exponential extraction unit, 305 Mantissa extraction unit, 306 Sign / exponential difference generation unit, 307 Mantissa difference generation unit, 308 Mantissa division unit, 309 Coding unit , 310 Code output unit.

Claims (13)

Mantissa extraction means for extracting mantissa of floating point numbers,
A coding means for encoding the extracted mantissa is provided.
The coding means identifies a probabilistic model based on the fixed decimal place corresponding to at least a part of the extracted mantissa places, and uses the identified probabilistic model to identify at least a part of the probabilistic model. A coding device that encodes a place. Further provided with a mantissa dividing means for dividing the extracted mantissa into a plurality of partitions at one or more boundaries.
A claim that the coding means identifies a probabilistic model based on a fixed decimal place corresponding to one of the plurality of partitions, and encodes the one partition using the identified probabilistic model. The coding apparatus according to 1. The coding device according to claim 2, wherein the coding means specifies a probabilistic model based on a fixed decimal place corresponding to the lowest place in the one partition. The coding device according to claim 3, wherein the coding means obtains a corresponding fixed decimal place from the floating point exponent and the number of digits of the lowest place in the one partition. Further provided with a difference generation means for acquiring the predicted value of the mantissa of the floating point number and generating the difference between the extracted mantissa and the predicted value.
The coding device according to any one of claims 1 to 4 , wherein the coding means switches a probability model depending on whether the coding target is the extracted mantissa or the generated difference. The coding device according to claim 5 , wherein the difference generating means does not generate a difference for the extracted digits below a predetermined place of the mantissa. The coding device according to claim 5 , wherein the difference generating means does not generate a difference among the extracted mantissa digits below the digit corresponding to the predetermined decimal place in the fixed decimal representation. The coding means entropy-codes the extracted mantissa.
The coding means is any of claims 1 to 7 , which specifies a probabilistic model in the entropy coding based on the fixed decimal representation corresponding to at least a part of the extracted mantissa digits. The coding apparatus according to item 1. A mantissa extraction step to extract a floating point mantissa,
Includes a coding step that encodes the extracted mantissa.
The coding step identifies a probabilistic model based on the fixed decimal representations corresponding to at least some of the extracted mantissa digits, and uses the identified probabilistic model to identify at least some of the probabilistic models. A coding method that includes a step of coding a place. An exponential decoding means that decodes the coded floating point exponent,
A determinant that determines from the decoded exponent the place of the fixed decimal representation corresponding to the place to be decoded among the mantissa digits of the encoded floating point number.
A decoding device including a mantissa decoding means that identifies a probabilistic model based on a determined fixed decimal representation and decodes the digit of the decoding target using the identified probabilistic model. An exponential decoding step that decodes the encoded floating point exponent,
A determination step to determine the fixed decimal representation of the encoded floating-point mantissa digit corresponding to the decoding target digit from the decoded exponent,
A decoding method including a mantissa decoding step of identifying a probabilistic model based on a determined fixed decimal representation and decoding the digit of the decoding target using the identified probabilistic model. Program for operating as a coding equipment according to the computer in any one of claims 1 to 8. A program for operating a computer as the decoding device according to claim 10.

Images