KR20100007685A - Fast 3d mesh coding apparatus using connectivity analysis and method thereof - Google Patents

Abstract

PURPOSE: A device and a method for encoding a 3D mesh model by analyzing connection information are provided to apply differential pulse code modulation and arithmetic encoding or determining bit encoding through analysis of a shared vertex without performing phase incision, thereby improving compression complexity of 3D model data and improving a compression rate. CONSTITUTION: A data analyzer(100) separates a vertex, an attribute and vertex connection information configuring a 3D mesh model from data of a 3D mesh model. A mesh model quantization unit(102) uses the information to generate a quantized vertex, attribute and connection information. A differential pulse code modulation unit(106) analyzes a sharing vertex of consecutive connection information of the 3D mesh model according to the quantized connection information to perform differential pulse code modulation. An entropy encoder(108) arithmetically encodes the quantized vertex, attribute information and connection information which is different-pulse-code modulated to output binary arithmetic or determining bit encoded data.

Description

Coding apparatus and method for 3D mesh model through connection information analysis {FAST 3D MESH CODING APPARATUS USING CONNECTIVITY ANALYSIS AND METHOD THEREOF}

The present invention relates to image compression, and in particular, quantizes vertex information of a three-dimensional model, and the connection information constituting the three-dimensional mesh model differs from the remaining values except for shared vertices through shared vertex analysis (SVA). The present invention relates to an apparatus and method for encoding a 3D mesh model that performs pulse code modulation (DPCM) and (binary) arithmetic coding or bit precision coding.

The present invention is derived from the research conducted as part of the IT new growth engine core technology development project of the Ministry of Knowledge Economy and the Ministry of Information and Telecommunication Research and Development. [Task management number: 2008-F-030-01] Technology development].

Currently, a triangular mesh is widely used as a method of representing a 3D image in the field of computer graphics. The triangular mesh image is composed of geographic information of the vertices forming the triangle and connectivity information between the vertices due to the non-uniform structure, so that the amount of data is much larger than a two-dimensional image having a uniform structure.

Therefore, many studies have been actively conducted to solve the problem of storing and transmitting a triangle mesh image.

On the other hand, in the field of three-dimensional graphics using a three-dimensional mesh model in recent years, the use of the three-dimensional mesh model is limited because of the vast amount of information in the use of the three-dimensional mesh model.

This assumes that geometric information of a 3D mesh model is represented by 32-bit floating point, and 96 bits, or 12 bytes of memory space are required to represent one geometric information. This means that if the three-dimensional model is represented by 10,000 vertices having only geometric information, 120 KB is required, and 1.2 MB of memory is required if represented by 100,000 vertices.

In addition, since the connection information allows two or more overlaps, very much memory is required to store the 3D model by the polygon mesh.

Therefore, the necessity of encoding has arisen in the compression of 3D images due to the enormous amount of such information. To this end, MPEG-4 (Moving Picture Expert Group-4)-3D Mesh Coding has been adopted as a standard of ISO / IEC (International Organization for Standardization / International Electrotechnical Compression) in the field of 3 Dimensional Graphics Compression (3DGC). The: 3DMC method encodes and decodes the mesh information of a three-dimensional model represented by an indexed faceset (IFS) file in a virtual language modeling language (VRML) file. Improve the transmission efficiency

Therefore, the present invention applies the differential pulse code modulation and the (binary) arithmetic coding or the decision bit (bit precision) coding to analyze the complexity of the data compression of the three-dimensional model without performing the phase cutting. An object of the present invention is to provide an apparatus and method for encoding a real-time three-dimensional mesh model through connection information analysis that improves and improves a compression ratio.

The present invention as described above is an apparatus for encoding a three-dimensional mesh model, comprising the unique vertex information, the attribute information representing the unique characteristics of the three-dimensional mesh model and the three-dimensional mesh model from the input data of the three-dimensional mesh model. A data analyzer which separates the connection information between the vertices; Mesh model quantization unit for generating quantized vertex information, attribute information and connection information using the vertex information, the attribute information and the connection information between the vertices of the three-dimensional mesh model analyzed by the data analysis unit ; A differential pulse code modulation prediction execution unit configured to perform differential pulse code modulation prediction using Sharable Vertex Analysis of continuous connection information of the 3D mesh model according to the connection information quantized by the mesh model quantization unit; And (binary) arithmetic-encode the vertex information, the attribute information, and the differential pulse code modulated connection information of the quantized three-dimensional mesh model to convert the binary arithmetic coding or decision bit-coded data of the three-dimensional mesh model into a bitstream form. It includes an output entropy encoder.

In the present invention, in the encoding of a 3D mesh model, a phase cutting process is not performed, and the face is a 3D model by applying differential pulse code modulation, (binary) arithmetic coding, and decision bit coding using shared vertex information. It is possible to improve the complexity of the compression and improve the compression ratio, and according to the improvement of the complexity of the compression can be quickly and accurately reconstructed the compressed three-dimensional model, there is an effect of improving the efficiency of the consumption of manpower and resources.

Hereinafter, with reference to the accompanying drawings will be described in detail the operating principle of the present invention. In the following description of the present invention, when it is determined that a detailed description of a known function or configuration may unnecessarily obscure the subject matter of the present invention, the detailed description thereof will be omitted. Terms to be described later are terms defined in consideration of functions in the present invention, and may be changed according to intentions or customs of users or operators. Therefore, the definition should be made based on the contents throughout the specification.

1 is a block diagram of a real-time three-dimensional mesh encoding apparatus through connection information analysis. The three-dimensional mesh encoding apparatus of the present invention analyzes vertex information, connection information, and additional information by analyzing data of an input signal. The information that can be expressed is composed of a part of performing mesh coding and performing shared vertex analysis on the part of the connection information and the part of entropy encoding such data.

Referring to FIG. 1, the data analyzer 100 may include unique vertex information constituting a three-dimensional mesh model, attribute information indicating a characteristic of the three-dimensional mesh model, and three-dimensional information from the input data of the three-dimensional mesh model. Separate connection information between vertices that make up the mesh model. In addition, the data analyzer 100 calculates the complexity of the 3D mesh model and divides the 3D mesh model into a plurality of partial meshes when the complexity value of the 3D mesh model exceeds a preset reference complexity value.

The mesh model quantization unit 102 uses the vertex information, the attribute information of the three-dimensional mesh model analyzed by the data analysis unit 100, and the connection information between the vertices of the three-dimensional mesh model. Create In this case, the above connection information is expressed as a list of indexes in which a plurality of vertex information forms a polygon, and the attribute information includes normals, colors, and texture coordinates of a 3D mesh model composed of polygons.

The shared vertex analyzing unit 104 analyzes shared information between vertices of the 3D mesh model. The differential pulse code modulation unit 106 uses a shared vertex analysis of the continuous connection information of the three-dimensional mesh model according to the connection information quantized by the mesh model quantization unit 102. Perform differential pulse code modulation prediction.

The entropy encoder 108 performs (binary) arithmetic coding on the vertex information, the attribute information, and the differential pulse code modulated connection information of the three-dimensional mesh model quantized by the mesh model quantization unit 102 to perform binary arithmetic coding on the three-dimensional mesh model. Alternatively, the decision bit-coded data is output in the form of a bit stream.

Hereinafter, the shared vertex analysis (SVA) process will be described in more detail.

SVA is a method of removing the redundancy between the vertices by analyzing the vertex information between the previous face and the current face, the equation for obtaining the type information is shown in Equation 1 below.

Type information is calculated using the number of vertices shared between the previous face and the current face, as shown in FIG. For example, when the vertex index of the previous face is (0, 1, 2) and the vertex index of the current face is (2, 3, 0), the index "0" and "2", that is, two indexes are shared, so Type 2 is selected. This type information is represented by four types of information: Type0, Type1, Type2, and Type3.

In order to encode / decode data encoded using the sharing relationship between the two data, position information, face direction information, and a difference value between two unshared vertex indices are required. The location information is represented by one of three values of 0, 1, and 2 for the triangle mesh. In Type1, location information having the same index value is encoded. In Type2, different location information is encoded. The direction information indicates whether the direction of the current face is the same or different direction as the previous face, which is represented by 0 and 1. The difference between the indexes encodes a circular difference value to reduce the amount of information. The difference value thus applied is defined as DIV (Differential Index Value).

That is, referring to FIG. 2 above, Type 0 indicates when there is no shared vertex between the previous face and the current face. In order to encode such data, encoding is performed using Type information (mode information) and three DIVs.

Type 1 indicates when there is one shared vertex between the previous face and the current face. In order to encode such data, encoding is performed using type information (mode information), position information having the same index value, and two DIVs.

Type 2 has two shared vertices between the previous face and the current face. In order to encode such data, encoding is performed using position information having different type information (mode information), index values, one DIV, and direction information.

Type 3 indicates when there are three shared vertices between the previous face and the current face. In order to encode such data, Type information (mode information) and direction information (face direction) are encoded.

[Table 1] below shows an example of coordindex value of actual VRML data.

[Table 1] Connection Information Coding

In Table 1, the index of the first face F1 is (0, 1, 2) and the index of the second face F2 is (2, 3, 0). In this case, the first index is encoded as it is, and SVA is applied from the second index. In the case of F2, "2" and "2" are shared, resulting in Type2. Since the unshared index is the second of the positions of 0, 1, and 2, the position information is 1. The value of DIV1 becomes "3-1" or "2". When decoding F2, the previous information F1 is previously decoded. Since the Tpye information is 2, two are shared, and one index is calculated as "2 (DIV1) +1 (value of position 1 of F1)" or 3 from DIV1. Therefore, it is decoded as (0, 3, 2). Since the information in the face direction is 1, the value of (2, 3, 0) can be obtained by inverting (0, 3, 2) in reverse.

3 and [Table 2] below are circular difference methods used to reduce the value of DIV according to the present invention. Description.

[Table 2] Connection Information Coding by Circular Difference

Considering the case of DIV1 of F5 in Table 1 with reference to Fig. 3, the maximum index value of VRML data used in this example is 7. Typical difference is "5-0 = 5". This value is stored in a as shown in FIG. 3 (S300). In this case, since c <p in the c and p value size comparison step (S302), b = − (7-5 + 0 + 1) = − 3 (S306). Subsequently, since the absolute value of a is larger than the absolute value of b in the step S308 of comparing the absolute values of a and b, the difference value due to the circular difference becomes -3. That is, the circular difference is changed as shown in [Table 2]. In this case, when calculating the b value in FIG. 3, both values may be eliminated.

Hereinafter, the operation in the entropy encoder 108 will be described in more detail.

In the case of entropy encoding, the sign of the input symbol is transmitted by sending one bit of encoded bits, and the actual entropy encoding is applied to the absolute value. First, the arithmetic coding (AC) operation in the entropy encoder 108 will be described.

In order to apply AC, we need to know the probability distribution for each symbol. It is difficult to calculate the probability of every symbol because the number of symbols increases in proportion to the number of vertices in the model. Therefore, in the present invention, AC is performed by dividing the input value by the quotient and the remainder. In the case of vertex coordinates, the number of symbols is determined according to the size of the quantization bit, and since it is a relatively small value, it can proceed as is without calculation of quotient and remainder.

The process as shown in FIG. 4 is performed by receiving the previously obtained DIV value. MaxBit used here can be arbitrarily adjusted.

Referring to FIG. 4 above, where floor [] is a rounding operation. For example, if the data input is 3000 (S400) and the Maxbit is 1024, first 3000% 1024 or 952 is encoded (S402), and the input is "floor [3000/1024] = 2". In step S404, it is checked whether the input becomes "0" (S406). If the input is not "0", the continuation code is inserted (S408). The changed input 2 is then iteratively encoded again. If the input becomes "0", an end code is inserted (S410), and the next input is encoded.

Next, when the bit precision coding (BPC) operation is described in the entropy encoder 108, the BPC is a method of expressing an input symbol by an integer multiple of the bit precision length (BPL). Table 3 below describes how each symbol is encoded according to the BPL when the input sequence is 5, 3, 8, or 2.

[Table 3] BPC Encoding

First, when the BPL is 2, the maximum representable value when the BPL is 2 is "11 (2) = 3". Since 5 = 3 + 2, which is the first input symbol, it may be represented as "11 (2) + 10 (2)". The next input symbol 3 may be represented by "3 + 0", which is represented by "11 (2) + 00 (2)". In this way, "11 (2) + 11 (2) + 00 (2)" in the form of 8 = 3 + 3 + 2, and 2 is encoded as "10 (2)". When decoding, the bitstream ("11101100") and the BPL (2) are known. First, read by the BPL bits to see "11 (2) = 3". By the way, "11 (2)" may be added later. Read the next two bits to get the value "10 (2) = 2". Since this is not " 11 (2) " The rest is decrypted in the same way.

Considering the case where BPL is 3 in [Table 3], 5 is expressed as "101 (2)", but 8 is expressed as "111 (2) + 001 (2)". That is, as shown in [Table 3], the bitstream size changes according to the BPL. In this example, when BPL is 3, the total coded bit is 15 bits and the least bit is required. Therefore, in this case, BPC is performed by setting BPL to 3.

As shown in [Table 3], BPC is first performed for all BPLs to obtain an optimal BPL. This is a time consuming factor. To make this faster, calculate using a frequency table as shown in Table 4 below.

[Table 4] Number of bits allocated to a symbol according to the frequency of the symbol

As shown in [Table 4], if you use the frequency table, you can calculate the required number of bits for each symbol according to the BPL, and multiply it by the frequency of the symbol to calculate all the required number of bits in that symbol.

The number of bits needed to BPC the symbol S is BPL * floor [S / (2BPL-1) +1]. Thus, if there are FS S, the number of bits needed to BPC all S is FS * BPL * floor [S / (2BPL-1) +1]. When calculating BPL, calculate it only until "BPL = floor [log2Max + 1] -1". If the BPL is above this value, you can use the normal binary representation instead of the BPC. Therefore, the BPL calculates the total number of bits from 1 to "floor [log2Max + 1] -1", and it is the smallest of the number of bits (total number of symbols * floor [log2Max + 1]) needed to binarize the input sequence. Select the case.

Finally, the binary arithmetic coding (BAC) operation in the entropy encoder 108 will be described.

In binary arithmetic encoding, a binary value is used as the input value for BAC. In the present invention, the binary input value is converted into a form having a small data size through preprocessing, and then input to a BAC to output a bitstream. When a set of symbols is present, the number of bits needed to represent these symbols in binary is equal to the number of bits needed to represent the maximum of the set. The number of bits required at this time is defined as RBL (Representation Bit Length).

5 illustrates an example of a BAC according to an embodiment of the present invention, in which an input symbol is 5 and a maximum value is 1023, that is, an RBL is ceil [log2 (1023 + 1)] = 10. 5 is represented by the binary number “0000000101” when expressed in 10 bits. In order to represent a sign, a 1-bit sign bit is inserted and this value is directly output to the bitstream. In the present invention, an input binary number except a sign is expressed as a prefix having a fixed number of BPL bits and a Postfix having a variable size. The value of Prefix is a value indicating the position of 1 which is furthest from the Least Significant Bit (LSB). In this example, ceil [log2 (5 + 1)] = 3. Since this value can have a value from 0 to RBL (= 10), it can be expressed as a ceil [log2 (RBL + 1)] bit. Where ceil [] is a rounding operation. Prefix is defined as the size of ceil [log2 (RBL + 1)], and is expressed as "3 = 0011 (2)", that is, in 4-bit form. Postfix is the entire bitstream one after the farthest from the LSB in the original binary representation. In this example, the Postfix is "01". Therefore, "0000000101" goes through preprocessing and becomes "prefix + postfix = 001101", which is the input of the BAC.

Meanwhile, in the above description of the present invention, specific embodiments have been described, but various modifications may be made without departing from the scope of the present invention. Therefore, the scope of the invention should be determined by the claims rather than by the described embodiments.

1 is a block diagram of an apparatus for encoding a 3D mesh model according to an embodiment of the present invention;

2 is an exemplary view of shared vertex analysis according to an embodiment of the present invention;

3 is a flowchart of a circular encoding process according to an embodiment of the present invention;

4 is a flowchart of an arithmetic coding process according to an embodiment of the present invention;

5 is a conceptual diagram of decision bit processing according to an exemplary embodiment of the present invention.

<Brief description of the major symbols in the drawings>

100: data analysis unit 102: mesh model quantization unit

104: shared vertex analysis unit 106: differential pulse code modulation unit

108: entropy encoder

Claims (13)

A data analysis unit that separates vertex information, property information, and connection information between the vertices of the 3D mesh model from data of the input 3D mesh model; A mesh model quantization unit generating quantized vertex information, attribute information, and connection information by using the vertex information, the attribute information, and the connection information of the 3D mesh model analyzed by the data analyzer; A differential pulse code modulator for performing differential pulse code modulation by using shared vertex analysis of continuous connection information of the 3D mesh model according to the connection information quantized from the mesh model quantization unit;  Entropy for performing binary arithmetic coding on the vertex information, the attribute information, and the differential pulse code modulated connection information of the quantized 3D mesh model, and outputting binary arithmetic coding or decision bit coded data of the 3D mesh model in a bitstream form. Encoder 3D mesh model encoding apparatus comprising a. The method of claim 1, The entropy coding unit, And a header for storing data about vertex information, property information, and connection information of the 3D mesh model. The method of claim 1, Connection information of the three-dimensional mesh model, A device for encoding a 3D mesh model, wherein a plurality of vertex information is represented by an index list forming one polygon. The method of claim 3, wherein Attribute information of the three-dimensional mesh model, And a normal, color, and texture coordinate of the three-dimensional mesh model formed of polygons. The method of claim 1, The data analysis unit, After calculating the complexity of the three-dimensional mesh model, if the complexity value of the three-dimensional mesh model exceeds a predetermined reference value of the three-dimensional mesh model, characterized in that to divide the three-dimensional mesh model into a plurality of partial mesh Encoding device. The method of claim 5, wherein The complexity is And an apparatus for encoding a 3D mesh model according to the number of facesets forming the 3D mesh model. Separating vertex information, property information, and connection information between the vertices constituting the 3D mesh model from data of the input 3D mesh model; Generating quantized vertex information, property information, and connection information using the vertex information, property information, and connection information of the separated three-dimensional mesh model; Performing differential pulse code modulation using quantization values of consecutive connection information of the three-dimensional mesh model; Performing entropy encoding of the 3D mesh model by performing binary arithmetic coding or decision bit coding on the vertex information, the attribute information, and the differential pulse code modulated connection information of the quantized 3D mesh model 3D mesh model encoding method. The method of claim 7, wherein The entropy encoded data is, 3D mesh model encoding method characterized in that the output in the form of a bitstream. The method of claim 7, wherein Connection information of the three-dimensional mesh model, And a plurality of vertex information is represented by an index list forming a unit polygon. The method of claim 7, wherein Attribute information of the three-dimensional mesh model, And a normal, color, and texture coordinate of the three-dimensional mesh model formed of unit polygons. The method of claim 7, wherein Separating the connection information between the vertices, Calculating a complexity of the three-dimensional mesh model; Dividing the 3D mesh model into a plurality of partial meshes when the calculated complexity value of the 3D mesh model exceeds a preset reference value 3D mesh model encoding method comprising a. The method of claim 11, The complexity is And a method of encoding the 3D mesh model according to the number of facesets forming the 3D mesh model. A recording medium on which a computer program for performing the encoding method of any one of claims 7 to 12 is recorded.

Images