Method for adaptive entropy coding of tree structures

Patent metadata

Field	Value
Publication number	US-9532056-B2
Application number	US-201114233519-A
Country	US
Kind code	B2
Filing date	Jul 18, 2011
Priority date	Jul 18, 2011
Publication date	Dec 27, 2016
Grant date	Dec 27, 2016

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.

First claim

The invention claimed is:

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.

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.

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

Assignees

• Jiang Wenfei
• Cai Kangying
• Chen Zhibo
• Thomson Licensing

Inventors

• Jiang Wenfei
• Cai Kangying
• Chen Zhibo

Classifications

• H03M7/6094

  according to reasons other than compression rate or data type · CPC title

• G06T9/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 title

• H04N19/96 Primary

  Tree coding, e.g. quad-tree coding · CPC title

• G06T9/001

  Model-based coding, e.g. wire frame · CPC title

• H03M7/40

  Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code · CPC title