Efficient compression of 3D models based on octree decomposition

Patent metadata

Field	Value
Publication number	US-9633473-B2
Application number	US-201214372922-A
Country	US
Kind code	B2
Filing date	Feb 9, 2012
Priority date	Feb 9, 2012
Publication date	Apr 25, 2017
Grant date	Apr 25, 2017

Abstract

To reduce the entropy of occupancy codes of an octree and improve compression efficiency, the present principles provide a method and an apparatus for traversing sub-cells in a cell according to the geometrical property of 3D models. That is, a surface smoothness measure is calculated for each sub-cell and the sub-cells are traversed in a pre-determined order of surface smoothness measures. To compute the surface smoothness measure, a sub-cell is connected to neighboring cells of its parent cell to form triangles and angles. Subsequently, the triangle areas or angular measures are used to compute the surface smoothness measure. When the connectivity information is not available in the 3D model data, the present principles also provide a method and an apparatus for estimating the connectivity.

First claim

The invention claimed is:

1. A method for generating or decoding a bitstream representing a 3D model, comprising:
determining a surface smoothness measure for each one of a plurality of sub-cells of a cell in an octree, the octree being representative of the 3D model, wherein the determining the surface smoothness measure comprises, for a particular sub-cell of the cell:
forming a plurality of triangles in response to the particular sub-cell and neighboring cells of the cell, wherein each one of the triangles is defined by a point representative of the particular sub-cell and two points representative of two cells of the neighboring cells,
determining an area for the each one of the triangles, and
determining the surface smoothness measure for the particular sub-cell in response to the areas of the plurality of triangles; and

determining a traversal order of the sub-cells of the cell in response to the surface smoothness measures of the sub-cells.

2. The method of claim 1 , wherein the traversal order corresponds to an ascending or descending order of the surface smoothness measures.

3. The method of claim 1 , wherein the surface smoothness measure is determined to be a sum of the areas.

4. The method of claim 1 , wherein the determining the surface smoothness measure further comprises, for the particular sub-cell of the cell:
forming a plurality of angles in response to the particular sub-cell and neighboring cells of the cell, wherein each one of the angles is defined by a point representative of the particular sub-cell and two points representative of two cells of the neighboring cells, the point representative of the particular sub-cell corresponding to a vertex of the each one of the angles;
determining an angular measure for the each one of the angles; and
determining the surface smoothness measure for the particular sub-cell in response to the angular measures of the plurality of angles.

5. The method of claim 4 , wherein the surface smoothness measure is determined to be a sum of the angular measures.

6. The method of claim 1 , further comprising:
determining a plurality of cells as the neighboring cells;
determining a sorted order of the neighboring cells, wherein the two cells of the neighboring cells are adjacent to each other in the sorted order; and
connecting the two cells of the neighboring cells.

7. The method of claim 6 , wherein the determining the sorted order comprises:
determining a projection direction in response to the cell and the neighboring cells;
projecting the cell and the neighboring cells to a 2D plane; and
sorting the neighboring cells in a counter-clockwise or a clockwise order around the cell in the 2D plane.

8. The method of claim 7 , wherein the determining the projection direction comprises:
forming a plurality of vectors, each one of the plurality of vectors is defined by the cell and one cell of the neighboring cells;
determining a set of absolute inner products for each axis of three coordinate axes, wherein each absolute inner product in the set of absolute inner products is formed between a vector representative of a corresponding coordinate axis and a respective one vector of the plurality of vectors;
determining a minimum absolute inner product for the set of absolute inner products; and
determining a coordinate axis as the projection direction, wherein the coordinate axis corresponds to a maximum of the three minimum absolute inner products for the three sets of absolute inner products.

9. The method of claim 1 , further comprising:
determining a bit for the each one of the sub-cells, wherein the bit indicates whether a corresponding sub-cell is empty;
forming a bit string using the determined bits for the sub-cells in response to the traversal order; and
entropy coding the bit string into the bitstream.

10. The method of claim 1 , further comprising:
decoding a bit string from the bitstream; and
determining a bit for a corresponding sub-cell in response to the traversal order, wherein the bit indicates whether the corresponding sub-cell is empty.

11. An apparatus for generating or decoding a bitstream representing a 3D model, comprising at least one memory and one or more processors, the one or more processors being configured to:
determine a surface smoothness measure for each one of a plurality of sub-cells of a cell in an octree, the octree being representative of the 3D model, wherein the one or more processors are configured to, for a particular sub-cell of the cell:
form a plurality of triangles in response to the particular sub-cell and neighboring cells of the cell, wherein each one of the triangles is defined by a point representative of the particular sub-cell and two points representative of two cells of the neighboring cells,
determine an area for the each one of the triangles, and
determine the surface smoothness measure for the particular sub-cell in response to the areas of the plurality of triangles; and

determine a traversal order of the sub-cells of the cell in response to the surface smoothness measures of the sub-cells.

12. The apparatus of claim 11 , wherein the traversal order corresponds to an ascending or descending order of the surface smoothness measures.

13. The apparatus of claim 11 , wherein the surface smoothness measure is determined to be a sum of the areas.

14. The apparatus of claim 11 , wherein the one or more processors are configured to, for the particular sub-cell of the cell:
form a plurality of angles in response to the particular sub-cell and neighboring cells of the cell, wherein each one of the angles is defined by a point representative of the particular sub-cell and two points representative of two cells of the neighboring cells, the point representative of the particular sub-cell corresponding to a vertex of the each one of the angles;
determine an angular measure for the each one of the angles; and
determine the surface smoothness measure for the particular sub-cell in response to the angular measures of the plurality of angles.

15. The apparatus of claim 14 , wherein the surface smoothness measure is determined to be a sum of the angular measures.

16. The apparatus of claim 11 , wherein the one or more processors are configured to:
determine a projection direction in response to the cell and the neighboring cells;
project the cell and the neighboring cells to a 2D plane; and
sort the neighboring cells in a counter-clockwise or clockwise order around the cell in the 2D plane.

17. The apparatus of claim 16 , wherein the one or more processors are configured to:
form a plurality of vectors, each one of the plurality of vectors is defined by the cell and one cell of the neighboring cells;
determine a set of absolute inner products for each axis of three coordinate axes, wherein each absolute inner product in the set of absolute inner products is formed between a vector representative of a corresponding coordinate axis and a respective one vector of the plurality of vectors;
determine a minimum absolute inner product for the set of absolute inner products; and
determine a coordinate axis as the projection direction, wherein the coordinate axis corresponds to a maximum of the three minimum absolute inner products for the three sets of absolute inner products.

18. The apparatus of claim 11 , wherein the one or more processors are configured to:
determine a bit for the each one of the sub-cells, wherein the bit indicates whether a corresponding sub-cell is empty;
form a bit string using the determined bits for

Assignees

• Tian Jiang
• Jiang Wenfei
• Cai Kangying
• Thomson Licensing

Inventors

• Tian Jiang
• Jiang Wenfei
• Cai Kangying

Classifications

• G06T17/005 Primary

  Tree description, e.g. octree, quadtree · CPC title

• H04N19/91

  Entropy coding, e.g. variable length coding [VLC] or arithmetic coding · CPC title

• G06T15/04

  Texture mapping · CPC title

• H04N19/134

  characterised by the element, parameter or criterion affecting or controlling the adaptive coding · CPC title

• H04N19/96

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