Adaptive predictive coding of 2D or 3D mesh information

[0002] 1. Field of the Invention

[0003] The present invention relates to an apparatus for coding property information of a two or three dimensional mesh object used in a synthetic and natural hybrid coding (SNHC) field or a virtual reality markup language (VRML) and a method therefor.

[0004] 2. Description of the Related Art

[0005] In order to display one complete three dimensional object, after dividing the surface of an object into triangles or polygons, information on the positions of the respective vertices and the positions, colors, normal vectors, and texture information of the respective divided surfaces should be described. In the present invention, in a method for reducing the amount of three dimensional information having such a structure, an effective prediction method is provided with respect to coding of color information.

[0006] In conventional methods for coding a mesh object, a method for coding color information is the same as methods for coding the information on the positions of the respective vertices, the information on the normal vectors of the respective surfaces, and the information on textures to cover the respective surfaces. Namely, as shown in FIG. 1, respective input items of information are quantized by a quantizer 10 having an appropriate quantization distance. A predictor 14 calculates a prediction value by an appropriate prediction method using a plurality of items of past information stored in a memory 12 and delayed. An encoder 16 encodes the difference between a value quantized by the quantizer 10 and the prediction value calculated by the predictor 14.

[0007] FIG. 2 shows a parallelogram predicting method among predicting methods used by the predictor 14. In the parallelogram predicting method, a difference value is obtained using property information P₀of a position to be encoded (for example, the information on the positions of the vertices, the information on the normal vectors, the texture information or the color information) and property information items P₁, P₂, and P₃of three adjacent places as follows. Namely, the parallelogram shown in FIG. 2 is obtained using the property information items P₁, P₂, and P₃of the three adjacent places. A prediction value {tilde over (P)}₀of one remaining place of the parallelogram is obtained by the three adjacent places. The coding is performed by supplying a difference P₀−{tilde over (P)}₀between the prediction value {tilde over (P)}₀and the property information P₀to be encoded by the encoder. In the respective surfaces constructing the mesh, it is experimentally established that the encoding efficiency is improved when the information on the positions of the vertices is encoded by the predicting method. However, the following problems are generated when prediction coding is performed with respect to the property information by the conventional prediction method.

[0008] 1. The range of a prediction error signal increases.

[0009] When the prediction is performed by a parallelogram predictor, the range of the property information becomes larger than that of an original signal. Namely, when P₁=P₃=MAX and P₂=MIN, the prediction value becomes (2MAX−MIN) which is much larger than the range of an original signal (MAX−MIN). Here, MAX and MIN respectively refer to the maximum value and the minimum value of the original signal. As the range of the prediction value becomes large, the range of an error signal becomes large, thus deteriorating the efficiency of the encoder.

[0010] 2. Prediction is performed using information items having low correlation.

[0011] In a three dimensional mesh, even the closest vertices may be separated from each other by a considerable distance in space. Therefore, in most cases, even adjacent vertices have low correlation with respect to property information. Therefore, prediction results obtained using vertices separated from each other and having low correlation in order to obtain the prediction value of the property information have a large error, which deteriorates the encoding efficiency.

[0012] Due to the above problems, it is not possible to effectively reduce the amount of information with respect to property information by the prediction error coding performed by the parallelogram predicting method of FIG. 2. The predicting methods using a plurality of adjacent property information items in which the property information items of the peripheral vertices or surfaces are averaged, also deteriorate the coding efficiency when correlation is low.

[0013] It is an objective of the present invention to provide an apparatus for encoding property information of a two or three dimensional mesh object and a method therefor, by which it is possible to effectively compress the property information of the surface of an object when a three dimensional object is expressed by a three dimensional mesh.

[0014] Accordingly, to achieve the above objective, the following methods are provided in the present invention. In the prediction method, property information items of a plurality of adjacent positions are not used. The difference between immediately prior information (most adjacent information) and input property information is obtained, considering the immediately prior information as the prediction value. The difference is used as a prediction error signal. Namely, in the present invention, a predictor having an order of 1 is used. The above predictor is used when the correlation between adjacent information items of input property information items is high, and is not used when the correlation is low. Namely, when the output value of the predictor is fixed to 0, the prediction error signal becomes identical to an original signal. Therefore, the operation is the same as in the case where there is no predictor. The correlation of the input property information is used in order to control two operation modes of the predictor. Namely, auto-correlation is obtained from the input property information. The predictor is used when correlation with an adjacent position is large. When the correlation is low, the predictor is fixed to 0. According to experimental results, coding efficiency is high when the predictor is used for the case where the correlation is larger than 0.9, and when no predictor is used, namely, the input property information is encoded as it is, for the case where the correlation is less than 0.9.

[0015] The above objective and advantages of the present invention will become more apparent by describing in detail a preferred embodiment thereof with reference to the attached drawings in which:

[0016] FIG. 1 is a block diagram showing the structure of an apparatus for encoding mesh information according to a conventional technology;

[0017] FIG. 2 is a view for describing a parallelogram predicting method according to the conventional technology;

[0018] FIG. 3 is a block diagram showing the structure of an embodiment of a property information encoder according to the present invention; and

[0019] FIG. 4 is a block diagram showing the structure of another embodiment of a property information encoder according to the present invention.

[0020] Hereinafter, the present invention will be described in detail with reference to the attached drawings.

[0021] Referring to FIG. 3, an embodiment of a property information encoding apparatus according to the present invention includes a quantizer 30, a delay 33, a selector 34, a subtracter 35, and an encoder 36.

[0022] The quantizer 30 quantizes input property information.

[0023] A delay 33 for delaying immediately prior property information and providing the delayed immediately prior property information as a prediction value of the next property information or a predictor according to a conventional method for combining current property information with property information items of a plurality of adjacent positions and outputting the combination result as a prediction value with respect to the current property information, can be used as the predictor which is a unit for predicting currently input property information.

[0024] The selector 34 selects either a prediction value output from the delay 33 or a predetermined value according to the characteristic of the input property information, and outputs the selected value. The subtracter 35 subtracts the value output from the selector 34 from the value output from the quantizer 30. In another embodiment of the present invention, the selector 34 operates in either a selection mode of selecting either the prediction value output from the delay 33 or 0, and outputting the selected value, or a fixed mode of outputting the prediction value output from the predictor. The selection mode is input by a user.

[0025] The encoder 36 compresses the information of a prediction error signal output from the subtracter 35. A lossless encoder such as an entropy encoder is most suitable for the encoder 36 used in the present invention.

[0026] Referring to FIG. 4, another embodiment of a property information encoding apparatus according to the present invention includes a quantizer 40, a delay 43 used for predicting, a selector 44, a subtracter 45 and an encoder 46 similar to FIG. 3 and further includes an auto-correlation calculating unit 41 and a decision unit 42.

[0027] The auto-correlation calculator 41 calculates the auto-correlation of the input property information items. The decision unit 42 generates a control signal so that the selector 44 can select a predicting method according to the auto-correlation. Therefore, the selector 44 selects either the prediction value output from the predictor or 0 according to the result of the decision unit 42 and outputs the selected value.

[0028] The operation of the present invention will be described hereinafter.

[0029] The input property information items are applied to the auto-correlation calculator 41, thus obtaining the auto-correlation. The auto-correlation obtained as mentioned above is compared with a predetermined threshold value (for example, 0.9) by the decision unit 42. A control signal for controlling a predictor used when the auto-correlation is larger than the predetermined threshold value, and controlling no predictor used when the auto-correlation is smaller than the predetermined threshold value, is generated and supplied to the selector 44.

[0030] The delay 43 used as the predictor in one embodiment of the present invention generates property information immediately before one step obtained by delaying the input property information as a prediction value S₁of the current property information and supplies it to the selector 44. 0(S₀) is supplied to another input of the selector 44 for a case in which the predictor is not used. Therefore, when the selector selects 0, the subtracter 45 subtracts 0 which is the value selected by the selector 44, thus suppressing the operation of the predictor. The input selected by the selector 44 is selected according to the control signal supplied by the decision unit 42. The information of the prediction error signal obtained by the subtracter is compressed by the encoder 46 such as an arithmetic encoder.

[0031] According to the present invention, it is possible to effectively compress the surface property information of a three dimensional object when a certain three dimensional object is expressed by a three dimensional mesh. It is possible to construct the most suitable encoder according to an object to be encoded, by selecting an appropriate predictor, according to correlation with respect to an adjacent position in the property information of the three dimensional object.