Method for adaptive entropy coding of tree structures

• US 9,532,056 B2
• Filed: 07/18/2011
• Issued: 12/27/2016
• Est. Priority Date: 07/18/2011
• Status: Active Grant

• Current Assignee: Interdigital Vc Holdings, Inc. (InterDigital, Inc.)
• Original Assignee: Thomson Licensing (Vantiva SA)
• Inventors: Jiang, Wenfei, Cai, Kangying, Chen, Zhibo
• Primary Examiner(s): Czekaj, Dave
• Assistant Examiner(s): Owens, Tsion B
• Application Number:
  US14/233,519
• Publication Number:
  US 20140185668A1
• Time in Patent Office: 1,989 Days
• US Class Current: 1/1
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: G06T 9/40 Tree coding, e.g. quadtree, octree
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/4056 Coding table selection
• CPC Class Codes: H03M 7/6088 according to the data type
• CPC Class Codes: H03M 7/6094 according to reasons other than compression rate or data type
• CPC Class Codes: H04N 19/44 Decoders specially adapted therefor, e.g. video decoders which are asymmetric with respect to the encoder
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding

Abstract

In 3D mesh coding, the geometry data is compressed by spatial tree based approaches. Bitstreams that result from the traversal of a tree structure of spatial tree based approaches for encoding 3D mesh models have systematically special redundancies, which is exploited for further improving the mesh model compression. A method for encoding a bitstream comprises steps of defining at least a first and a second symbol group of binary symbols, with S1 being a subset of S2, determining within the bitstream first portions, second portions and third portions, wherein first portions have Th1 or more consecutive S1 symbols and second portions have Th2 or more consecutive S2 symbols, encoding the bitstream, wherein first portions, second portions and third portions are encoded using different codes, and encoding values indicating the boundary positions between the first, second and third portions in the bitstream.

Claims

1. A method for encoding a bitstream, the bitstream representing a traversed octree representation of a 3D mesh model, the method comprising:

defining at least a first and a second symbol group of binary symbols, wherein the first symbol group is a subset of the second symbol group;

determining within the bitstream two or more first portions, zero or more second portions and two or more third portions, wherein each first portion has at least a first pre-defined number of consecutive symbols of the first symbol group, each second portion has at least a second pre-defined number of consecutive symbols of the second symbol group, and wherein remaining parts of the bitstream are third portions;

determining in the bitstream a part that comprises only first and third portions;

encoding the bitstream, wherein said first portions are encoded using a first code, said second portions are encoded using a second code and said third portions are encoded using a third code; and

encoding values indicating the boundary positions between the first, second and third portions in the bitstream, wherein in said part that comprises only first and third portions the encoding of a boundary position between a first portion and an adjacent third portion is skipped and implicitly encoded if the third portion has a pre-defined length.

2. Method according to claim 1, wherein the first symbol group comprises binary symbols that have one bit set to 1 and remaining bits set to 0, and the second symbol group comprises binary symbols that have one or two bits set to 1 and the remaining bits are 0.

3. Method according to claim 1, wherein the encoding comprises a first encoding using the first code based on a first symbol set, a second encoding using the second code based on a second symbol set and a third encoding using the third code based on a third symbol set, and wherein at least a part of the first, second and third encoding is performed simultaneously.

4. Method according to claim 1, wherein decoder control information is encoded at the beginning of the bitstream, the decoder control information comprising said values indicating the boundary positions between the first, second and third portions of the bitstream.

5. Method according to claim 1, wherein the boundary positions or lengths of the first, second and third portions in the bitstream are encoded as a sequence of values, wherein for the first part and for first portions of the second part of the bitstream the values representing boundary positions are encoded in a monotonic order if no boundary is skipped, and wherein said implicit encoding of a boundary position between a first portion and an adjacent third portion comprises swapping the boundary order of said first portion.

6. Method according to claim 1, wherein said pre-defined length of the third portion of the bitstream is one.

14. A non-transitory computer readable medium having executable instructions to cause a computer to perform a method according to claim 1.

7. Method for decoding a bitstream, the bitstream representing a traversed octree representation of a 3D mesh model, comprising:

decoding from the beginning of the bitstream control information that comprises lengths of the first, second and third portions;

determining, according to said control information, within the bitstream at least two or more first portions, each having consecutive symbols of a first symbol group, zero or more second portions, each having consecutive symbols of a second symbol group, and two or more third portions having symbols of a third symbol group, wherein at least one of said third portions and said zero or more second portions are in a consecutive first part of the bitstream, and at least one of said first portions and said at least two second portions are in a consecutive second part of the bitstream;

decoding said consecutive symbols of the at least two or more first portions to symbols of a fixed length using a first symbol decoder based on a first symbol group;

decoding said consecutive symbols of the zero or more second portions to symbols of said fixed length using a first symbol decoder based on a second symbol group, wherein the second symbol group comprises said symbols of the first symbol group and additional symbols if at least one second portion was determined;

decoding the symbols of said two or more third portions to symbols of said fixed length using a third symbol decoder based on a third symbol group, wherein the third symbol group comprises only symbols that are not comprised in said second symbol group; and

providing the decoded symbols of said first, second and third portions of the bitstream in a sequential order according to said control information.

8. Method according to claim 7, wherein the first symbol group comprises binary symbols that have one bit set to 1 and remaining bits are 0, and the second symbol group comprises binary symbols that have one or two bits set to 1 and the remaining bits are 0.

9. Method according to claim 7, wherein the decoding control information from the beginning of the bitstream comprises decoding a sequence of values indicating boundary positions of the first, second and third portions in the bitstream, wherein the values representing boundary positions for the first part of the bitstream have a monotonic order, and wherein the values representing boundary positions for first portions of the second part of the bitstream have a monotonic order, further comprising:

detecting at least one pair of values representing boundary positions in the second part of the bitstream having swapped monotonic order; and

inserting at a boundary position according to one of said values one of said first portions having a length according to the difference between said at least one pair of values.

10. Method according to claim 7, wherein said decoding of the at least two or more first portions, said decoding of the zero or more second portions if at least one second portion was determined and said decoding of said two or more third portions is performed at least partially simultaneously, and wherein the step of providing the decoded symbols of the first, second and third portions of the bitstream comprises reordering said first, second and third portions.

15. A non-transitory computer readable medium having executable instructions to cause a computer to perform a method according to claim 7.

11. An apparatus for encoding a bitstream, comprising at least a memory and one or more processors, wherein the one or more processors are configured to:

define at least a first and a second symbol group of binary symbols, wherein the first symbol group is a subset of the second symbol group;

determine within the bitstream two or more first portions, zero or more second portions and two or more third portions, wherein each first portion has at least a first pre-defined number of consecutive symbols of the first symbol group, each second portion has at least a second pre-defined number of consecutive symbols of the second symbol group, and wherein remaining parts of the bitstream are third portions;

determine in the bitstream a part that comprises only first and third portions;

encode the bitstream, wherein said first portions are encoded in a first sub-encoder using a first code, said second portions are encoded in a second sub-encoder using a second code and said third portions are encoded in a third sub-encoder using a third code; and

encode values indicating the boundary positions between the first, second and third portions in the bitstream, wherein in said part that comprises only first and third portions the encoding of a boundary position between a first portion and an adjacent third portion is skipped and implicitely encoded if the third portion has a pre-defined length.

12. An apparatus for decoding a bitstream, comprising at least a memory and one or more processors, wherein the one or more processors are configured to:

decode from the beginning of the bitstream control information;

determine, according to said control information, within the bitstream at least two or more first portions, each having consecutive symbols of a first symbol group, zero or more second portions, each having consecutive symbols of a second symbol group, and two or more third portions having symbols of a third symbol group, wherein at least one of said third portions and said zero or more second portions are in a consecutive first part of the bitstream, and at least one of said first portions and said at least two second portions are in a consecutive second part of the bitstream;

decode said consecutive symbols of the at least two or more first portions to symbols of a fixed length using a first symbol decoder, based on a first symbol group;

decode said consecutive symbols of the zero or more second portions to symbols of said fixed length using a first symbol decoder if at least one second portion was determined; and

decode the symbols of said two or more third portions to symbols of said fixed length using a third symbol decoder based on a third symbol group, wherein the third symbol group comprises only symbols that are not comprised in said second symbol group; and

provide the decoded symbols of said first, second and third portions of the bitstream in a sequential order according to said control information.

13. Apparatus according to claim 12, wherein the one or more processors are configured to decode a sequence of values indicating boundary positions of the first, second and third portions in the bitstream, wherein the values representing boundary positions for the first part of the bitstream have a monotonic order, and wherein the values representing boundary positions for first portions of the second part of the bitstream have a monotonic order, and the one or more processors are further configured to:

detect at least one pair of values representing boundary positions in the second part of the bitstream having swapped monotonic order; and

insert at a boundary position according to one of said values one of said first portions having a length according to the difference between said at least one pair of values.

16. A non-transitory computer readable medium having stored thereon an encoded bitstream representing a 3D mesh model and being encoded using at least a first and a second symbol group of binary symbols, wherein the first symbol group is a subset of the second symbol group, the encoded bitstream comprising:

two or more first portions, zero or more second portions and two or more third portions, wherein each first portion has at least a first pre-defined number of consecutive symbols of the first symbol group, each second portion has at least a second pre-defined number of consecutive symbols of the second symbol group, and remaining parts of the bitstream are third portions, and wherein said first portions are encoded using a first code, said second portions are encoded using a different second code and said third portions are encoded using a third code different from the first and second codes;

at least one part that comprises only first and third portions; and

values indicating boundary positions between the first, second and third portions in the bitstream, wherein in a part that comprises only first and third portions the encoding of a boundary position between a first portion and an adjacent third portion is skipped and implicitely encoded if the third portion has a pre-defined length.