Patent Description:
in practical applications, many 3D models consist of a large number of connected components. And these multi-connected 3D models usually contain lots of repetitive structures in various transformations, as shown in Fig. Efficient compression methods for this kind of 3D models should be able to extract the redundancy existing in the repetitive structures.

The owner of the current invention also co-owns a <CIT>), which teaches a compression method for 3D models that consist of many small to medium sized connected components, and that have geometric features which repeat in various positions, scales and orientations, the teachings of which are specifically incorporated herein by reference. This method discovers the structures repeating in various positions, orientations and scaling factors. Then the 3D model is organized into "pattern-instance" representation. A pattern is the representative geometry of the corresponding repetitive structure. The connected components belonging to a repetitive structure are called instances of the corresponding pattern and represented by their transformation, i.e. the positions, orientations and possible scaling factors, regarding to the pattern. The orientation of an instance is represented by <NUM> orthogonal axes represented by (x0, y0, z0) and (x1, y1, z1) in Cartesian coordinate system, or (alpha, beta, gamma) in spherical coordinate system.

The owner of the current invention also co-owns a PCT application entitled "Bitstream Syntax and Semantics of Repetitive Structure Discovery Based 3D Model Compression Algorithm" by<CIT>), which teaches a two modes for compressing instance transformation data.

However, there is a need to provide a method and apparatus that can deal with 3D model properties, such as normal, color and texture coordinates, and can compress instances whose transformation includes reflection transformation
Accordingly, the present principles provide a method and apparatus that may be used to compress 3D model properties, such as normal, color and texture coordinates, and compress instances whose transformation includes reflection transformation and generate a bitstream that includes this information.

The present principles provide a method according to claim <NUM> and an apparatus according to claim <NUM> for generating a compressed bitstream from data representing a 3D mesh model.

The present principles also provide a method according to claim <NUM> and an apparatus according to claim <NUM> for processing a compressed bitstream representing a 3D mesh model.

The present principles also provide a computer readable storage medium according to claim <NUM>.

Only the geometry is checked during repetitive structure discovery. One instance can either share property data with the corresponding pattern or have its own property data. The properties of an instance will be compressed separately if it doesn't share properties with the pattern.

The instance transformation can de divided into four parts, reflection part, rotation part, translation part, and possible scaling part. The four parts are compressed separately.

All patterns are compressed together in order to achieve more bitrates saving. During decoding, patterns need to be separated from each other before restoring instances.

<FIG> show an exemplary encoder and decoder suitable for implementing aspects of the present principles. The details of the encoder and decoder are provided in Applicant's co-owned <CIT> and <CIT>, and the descriptions therein are expressly incorporated by reference in this application. As will be appreciated by those skilled in the art, the CODEC can be implemented in hardware, software or firmware, or combinations of these modalities, in order to provide flexibility for various environments in which such 3D rendering is required. Application specific integrated circuits (ASICs), programmable array logic circuits, discrete semiconductor circuits, and programmable digital signal processing circuits, computer readable media, transitory or non-transitory, among others, may all be utilized to implement the present invention. These are all non-limiting examples of possible implementations of the present invention, and it will be appreciated by those skilled in the art that other embodiments may be feasible.

While we want the bitstream to embed all the instance data, we also want it to be efficient and address several applications where sometimes either bitstream size or decoding efficiency or error resilience matters the most.

Therefore, we propose two options for how to put the data of one instance, i.e. its pattern ID (for example, the ID being the actual position of the pattern in the pattern compression data stream, <NUM> for first pattern, <NUM> for second pattern,. ), its reflection transformation part (F), its translation transformation part (T), its rotation transformation part (R) and its scaling transformation part (S), of the patterns in the bitstream. Both of them have their own pros and cons.

Option (A) elementary instance data mode (ID, F, T, R, S, ID, F, T, R, S. ): Using this mode, the pattern ID, reflection transformation part, translation transformation part, rotation transformation part and scaling transformation part of one instance are packed together in the bitstream.

Option (B) grouped instance data mode (ID, ID, F, F, T, T, R, R, S, S): Using this mode, information is grouped together based on information type, that is, the pattern ID, reflection transformation part, translation transformation part, rotation transformation part and scaling transformation part of one instance are packed together in the bitstream.

The current bitstream definition will include both of the above two options. Then the users can choose the one which fits their applications better. A particular implementation may choose to only implement one of the two instance data modes. For that case, the bitstream definition should be changed accordingly. Refer to the "Bitstream syntax and semantics" section for the detail.

Since instances may have larger decoding error, which is defined as the distance between the original component and the component restored from the pattern and instance transformation, some data fields of the bitstream are defined to denote the compressed instance decoding error to guarantee the decoded 3D model quality. Whether or not to compress the decoding error of an instance is based on, for example, the quality requirement.

As shown below, the instance transformation can de divided into four parts, reflection part (Refle), rotation part (Rotat), translation part (Transl), and possible scaling part. <MAT> <MAT>.

The reflection part may be represented by a <NUM>-bit flag, for example, as described in PCT application (fill in application number) entitled "Method and Apparatus for Reflective Symmetry Based 3D Model Compression" by W. Cai, and T.

The rotation part is a 3x3 matrix. The three columns (or rows) of the rotation part are unit orthogonal vectors. In order to address several applications where sometimes either decoding efficiency or decoding error matters the most, we propose two options for how to compress the rotation part. Both of them have their own pros and cons.

Option (A) Cartesian mode. In Cartesian coordinate system, the rotation part can be represented by <NUM> orthogonal axes, (x0, y0, z0) and (x1, y1, z1), and compressed, for example, as described in PCT application (<CIT>.

Option (B) Spherical mode. Using this mode, the rotation part can be converted to Euler angles (alpha, beta, gamma), for example, by "<NPL>, and be compressed, for example, as described in PCT application (<CIT>.

The current bitstream definition will include both of the above two options. Then the users can choose the one which fits their applications better. A particular implementation might choose to only implement one of the two instance rotation compression modes. For that case, the bitstream definition should be changed accordingly. Refer to the "Bitstream syntax and semantics" section for the details.

The translation part is represented by a vector (x, y, z) (pseudo translation vector). While using grouped instance transformation mode, all pseudo instance translation vectors are compressed by octree (OT) decomposition based compression algorithm, for example, by using methods described in PCT Application (<CIT>, which recursively subdivides the bounding box of all pseudo instance translation vectors in an octree data structure. We represent each octree node subdivision by the <NUM>-bit long occupancy code, which uses a <NUM>-bit flag to signify whether a child node is nonempty. An occupancy code sequence describing the octree is generated by breadth first traversing the octree. We compress the occupancy code sequence by dividing it into several intervals and compressing them with different probability models. Since instances may have extremely close pseudo translation vectors, which we call duplicate translation vectors, some data fields of the bitstream are defined to denote the duplicate translation vectors.

The scaling part is represented by the uniform scaling factor S of the instance and compressed by the lossless compression algorithm for floating point numbers, for example, by "<NPL>.

in practical applications, besides geometry, 3D models usually have various properties, such as normal, color and texture coordinates. Requiring instances have the same properties of patterns will limit the number of repetitive structures can be discovered and decrease the compression ratio of A3DMC. Thus we only check the geometry during repetitive structure discovery and the instance may have properties different with the corresponding pattern's properties.

When the elementary instance data mode is used, one data field is defined to denote how to get the properties of an instance from the bitstream.

The property data of one instance (P) follows the other data of the instance, i.e. (ID, F, T, R, S, P, ID, F, T, R, S, P. When the grouped instance data mode is used, all instances should either share the pattern property data or have their own property data. The instance data part of the bitstream is like (ID, ID, F, F, T, T, R, R, S, S, P, P). We use the same 3D model property data field definition of ISO/IEC <NUM>-<NUM>.

The decomposition of the general structure of the compressed bitstream of our repetitive structure discovery based compression algorithm, A3DMC, is as shown in <FIG>. The bitstream starts with the header buffer (A3DMC_stream_header), which contains all the necessary information for decoding the compressed stream: information of whether or not there is at least one repetitive structure in the original model, the 3D model compression method used for compressing geometry, connectivity and properties of all 3D objects (patterns and other parts if necessary), information of whether or not the "grouped instance transformation mode" or "elementary instance transformation mode" is used in this bitstream, information of whether or not there are some parts of the original model which are not repetitive (which we reference as unique part), information of whether or not instance decoding error will be compensated, information of the type of properties instances may have, etc..

If there is no repetitive structure in the original model (repeat_struc_bit != <NUM>), the left part of the bitstream is the compressed input 3d model using the 3D model compression method indicated in A3DMC_stream_header. Otherwise, the next part in the bitstream is the compressed result of all patterns. Depending on which instance transformation packing mode is chosen in this bitstream, either compr_insta_grouped_data or compr_insta_elementary_data is the next part in the bitstream. If there is unique part in the original 3D model, compr uni_part data is attached. Otherwise, the bitstream ends.

in addition to the syntax functions, categories and descriptors already used in SC3DMC specification, we will also use the following two:.

A3DMC_stream_header: contain the header buffer.

A3DMC_steam_data: contain the data buffer.

repeat_struc_bit: a <NUM>-bit unsigned integer indicating whether or not there are more than a certain amount of repetitive structures in the 3D model. <NUM> for no repetitive structure and <NUM> for repetitive structure. 3d_model_compr_mode: a <NUM>-bit unsigned integer indicating the 3d model compression method used to compress a pattern, unique part and the original 3D model itself if it includes no repetitive structures.

QP: a <NUM>-bit unsigned integer indicating the quality parameter. The minimum value of QP is <NUM> and the maximum is <NUM>. pattern_num: a <NUM>-bit unsigned integer indicating the number of all patterns if it is less than <NUM>. The minimum value of pattern_num is <NUM>. pattern_num_2: a <NUM>-bit unsigned integer indicating the number of all patterns if it is not less than <NUM>. In this case, the total pattern number is (pattern_num_2 + <NUM>)
instance_num: a <NUM>-bit unsigned integer indicating the number of all instances if it is less than <NUM>. The minimum value of instance_num is <NUM>. instance_num_2: a <NUM>-bit unsigned integer indicating the number of all instances if it is not less than <NUM>. In this case, the total instance number is (instance_num_2 + <NUM>)
insta_trans_elem_bit: a <NUM>-bit unsigned integer indicating whether "grouped instance transformation mode" or "elementary instance transformation mode" is used in this bitstream. <NUM> for "grouped instance transformation mode" and <NUM> for "elementary instance transformation mode". insta_rotat_mode_bit: a <NUM>-bit unsigned integer indicating the encoding mode of instance rotation transformation. <NUM> for spherical mode and <NUM> for Cartesian mode. use_scaling_bit: a <NUM>-bit unsigned integer indicating whether instance transformation includes scaling factors. <NUM> for scaling factors being included in instance transformation and <NUM> for not. When the scaling factors of most instances equal <NUM>, the instance transformation doesn't include scaling factor. Then all the instances must have the same size with the corresponding pattern. uni_part bit : a <NUM>-bit unsigned integer indicates whether there is unique part in the original 3d model. <NUM> means there is no unique part and <NUM> means there is unique part. If uni_part bit equals <NUM>, it also means that the end of the bitstream is reached right after the pattern instance compression data. error_compensate_enable_bit: a <NUM>-bit unsigned integer indicating whether there are data fields of compressed decoding error for some instances in the bitstream. <NUM> means there is no data field of compressed decoding error of instances in the bitstream and <NUM> means there are data fields of compressed decoding error of some instances in the bitstream. property_enable_bits: a <NUM>-bit flag in which each bit denotes whether a corresponding property (e.g., normal, color, texture coordinate) is encoded. <NUM> means the corresponding property is not encoded and <NUM> means it is encoded. The relationship between the bits and properties is shown in the following table.

The rotation transformation of ith instance in Cartesian mode is represented by <NUM> orthogonal axes (x0, y0, z0) and (x1, y1, z1).

The rotation of ith instance in spherical mode is represented by <NUM> angles, alpha, beta & gamma.

An implementation might choose to only implement one of the two instance data packing modes. For that case, insta_trans_elem_bit in A3DMC_stream_header should be removed from the bitstream definition. If elementary instance data mode is chosen by the implementation, compr_insta_grouped_data should be removed from the bitstream definition. If grouped instance data mode is chosen by the implementation, compr_insta_elementary_data should be removed from the bitstream definition.

An implementation might choose to only implement one of the two instance rotation compression modes. For that case, insta_rotat_mode_bit in A3DMC_stream_header should be removed from the bitstream definition. If Cartesian mode for compressing instance rotation is chosen by the implementation, compr_elem_insta_rotat_spherical should be removed from the bitstream definition. If Spherical mode is chosen by the implementation, compr_elem_insta_rotat_cartesian should be removed from the bitstream definition.

An implementation might choose to not include header in the bitstream for the compressed pattern IDs, translation transformation parts, rotation transformation parts and scaling factors of all instances. For that case, compr_insta_patternID_header, compr_insta_transl_header, compr_insta_rotat_header and compr_insta_scaling_header should be removed from the bitstream definition.

Thus, according to the present principles, a 3D model is represented using the repetitive structure discovery, and a bitstream according to the syntax described above is generated and encoded to deal with the 3D model properties, such as normal, color, and texture coordinates, and to compress instances whose transformation includes reflection transformation. The model data is accessed, the pattern ID and the transformation information and the property information is determined. The pattern ID, transformation information, and the property information is grouped together, according to one of the formats described above, to generate a bitstream representative of the 3D model.

Among others, the present principles provide the following features and advantages:.

A decoder adapted to restore the transformation matrix of a instance from the corresponding decoded reflection, translation, rotation and possible scaling parts, as shown in <FIG>.

The implementations described herein may be implemented in, for example, a method or a process, an apparatus, a software program, a data stream, or a signal. Even if only discussed in the context of a single form of implementation (for example, discussed only as a method), the implementation of features discussed may also be implemented in other forms (for example, an apparatus or program). An apparatus may be implemented in, for example, appropriate hardware, software, and firmware. The methods may be implemented in, for example, an apparatus such as, for example, a processor, which refers to processing devices in general, including, for example, a computer, a microprocessor, an integrated circuit, or a programmable logic device. Processors also include communication devices, such as, for example, computers, cell phones, portable/personal digital assistants ("PDAs"), and other devices that facilitate communication of information between end-users.

Reference to "one embodiment" or "an embodiment" or "one implementation" or "an implementation" of the present principles, as well as other variations thereof, mean that a particular feature, structure, characteristic, and so forth described in connection with the embodiment is included in at least one embodiment of the present principles. Thus, the appearances of the phrase "in one embodiment" or "in an embodiment" or "in one implementation" or "in an implementation", as well any other variations, appearing in various places throughout the specification are not necessarily all referring to the same embodiment.

Additionally, this application or its claims may refer to "determining" various pieces of information. Determining the information may include one or more of, for example, estimating the information, calculating the information, predicting the information, or retrieving the information from memory.

Further, this application or its claims may refer to "accessing" various pieces of information. Accessing the information may include one or more of, for example, receiving the information, retrieving the information (for example, memory), storing the information, processing the information, transmitting the information, moving the information, copying the information, erasing the information, calculating the information, determining the information, predicting the information, or estimating the information.

Additionally, this application or its claims may refer to "receiving" various pieces of information. Receiving is, as with "accessing", intended to be a broad term. Receiving the information may include one or more of, for example, accessing the information, or retrieving the information (for example, from memory). Further, "receiving" is typically involved, in one way or another, during operations such as, for example, storing the information, processing the information, transmitting the information, moving the information, copying the information, erasing the information, calculating the information, determining the information, predicting the information, or estimating the information.

Claim 1:
A method for generating a compressed bitstream from data representing a 3D mesh model, the 3D mesh model including repetitive structures, a repetitive structure being a structure having geometric features that repeat in various positions, scales, and orientations in the 3D model, wherein the repetitive structures are represented by instances of patterns, an instance of a pattern being a transformation of a corresponding pattern, the corresponding pattern being a representative geometry of the corresponding repetitive structure, the method comprising:
accessing information related to an instance of a pattern associated with a structure, the pattern being one of a plurality of patterns, the information including a pattern identifier and transformation information associated with the pattern, wherein the transformation information includes information types corresponding to at least one of a reflection part, a translation part, a rotation part, and a scaling part; and
generating a bitstream comprising a header portion having an indicator indicative of a mode for packing the information in the bitstream among one of a first data packing mode and a second data packing mode, and a data portion including a pattern identifier and transformation information associated with the pattern disposed in the bitstream according to the indicator, wherein:
if the indicator indicates the first data packing mode, generating the bitstream includes, for each one of the instances, grouping together the pattern identifier and its respective transformation information;
if the indicator indicates the second data packing mode, generating the bitstream includes grouping together pattern identifiers and grouping together the transformation information of all of the instances based on the information type.