Method, medium and apparatus for encoding and decoding 3D data using adaptive octrees

At least one processor to encode 3D data, comprising:

• an adaptive octree generating unit converting 3D data having one of at least PointTexture, voxel, and octree data into adaptive octree data where nodes have labels, including at least a label representing an empty node that is not encoded and is recognized by resolution information of a bounding volume of a 3D object;
• a node encoding unit encoding nodes of the adaptive octree data;
• and
• a bitstream generating unit generating a bitstream from the nodes encoded in the node encoding unit,
• wherein the adaptive octree data in the adaptive octree generating unit is represented by converting the 3D data into voxel data using a 3D bounding volume and differentiating a voxel on a location where a 3D object exists and a voxel on a location where the 3D object does not exist by predetermined labels, the predetermined labels indicating a case ‘S’ where a node of an adaptive tree structure indicating the 3D data has of sub-nodes, a case ‘W’ where the node has voxels not having objects, a case ‘B’ where the node has voxels having objects, a case ‘P’ where voxel values within the node are encoded by a PPM algorithm, and a case ‘E’ for the empty node where space for voxels of the node does not exist, and
• wherein the node encoding unit comprises:
• a node order selecting unit selecting an order of nodes of the adaptive octree data to be encoded;
• a node SOP selecting unit selecting node type information indicating whether the nodes to be encoded should be encoded into ‘S’ or ‘P’ nodes;
• an ‘S’ node encoding unit encoding detailed information of the ‘S’ node if the node type information is ‘S’;
• and
• a ‘P’ node encoding unit encoding the detailed information of the ‘P’ node if the node type information is ‘P’.

A method of decoding 3D data, comprising:

• receiving a bitstream for the 3D data including header information and node information, wherein the header information includes resolution information of a bounding volume of a 3D object and the node information includes information of nodes making up an adaptive tree structure except for an empty node having no voxel space;
• reading nodes making up the adaptive tree structure from the bitstream;
• decoding the read nodes, wherein no information for the empty node having no voxel space is decoded and the empty node having no voxel space is recognized by only the resolution information of the header information;
• recovering an adaptive octree from the decoded nodes, using at least one processing device, wherein in the adaptive octree nodes have labels, including at least a label representing the empty node;
• and
• recovering and outputting any one of at least octree, voxel, and PointTexture data from the adaptive octree,
• wherein the reading of nodes comprises:
• selecting nodes to be decoded one by one in a breadth-first search scheme starting from a root node while recovering the adaptive tree structure for a 3D object in a top-down manner,
• reading and finding out node type information indicating whether a node to be decoded is an ‘S’ node or a ‘P’ node;
• if the node type information is ‘S’, decoding an average value of color information and decoding labels of sub-nodes;
• and
• if the node type information is ‘P’, decoding depth information and decoding color information, and
• wherein in the recovering of the adaptive octree, the labels comprise ‘S’, ‘W’, ‘B’, ‘P’ and ‘E’, the ‘S’ denoting that a node of a tree indicating the 3D data to be decoded has sub-nodes, the ‘W’ denoting that the node has voxels not having objects, the ‘B’ denoting that the node has voxels having objects, the ‘P’ denoting that voxel values within the node are encoded by the PPM algorithm, and the ‘E’ for the empty node denoting that space for voxels of the node does not exist.

At least one processor for decoding 3D data, comprising:

• a bitstream reading unit receiving a bitstream for the 3D data including header information and node information, wherein the header information includes resolution information of a bounding volume of a 3D object and the node information includes information of nodes making up an adaptive tree structure except for an empty node having no voxel space and reading nodes making up the adaptive tree structure from the bitstream;
• a node decoding unit decoding the read nodes, wherein no information for the empty node having no voxel space is decoded and the empty node having no voxel space is recognized by only the resolution information of the header information;
• an adaptive octree recovering unit recovering an adaptive octree from the decoded, wherein in the adaptive octree nodes have labels, including at least a label representing the empty node;
• and
• a volume data recovering unit recovering any one of at least octree, voxel, and PointTexture data from the adaptive octree,
• wherein the node decoding unit comprises:
• a node order selecting unit selecting nodes to be decoded one by one in a breadth-first search scheme starting from a root node while recovering the adaptive tree structure for a 3D object in a top-down manner;
• a node SOP selecting unit determining node type information indicating whether the nodes to be decoded should be decoded into an ‘S’ node or a ‘P’ node;
• an ‘S’ node decoding unit decoding an average value of color information and decoding labels of sub-nodes if the node type information is ‘S’;
• and
• a ‘P’ node decoding unit decoding depth information and decoding color information if the node type information is ‘P’, and
• wherein in the adaptive octree recovering unit, the labels comprise ‘S’, ‘W’, ‘B’, ‘P’ and ‘E’, the ‘S’ denoting that a node of a tree indicating the 3D data to be decoded has sub-nodes, the ‘W’ denoting that the node has voxels not having objects, the ‘B’ denoting that the node has voxels having objects, the ‘P’ denoting that voxel values within the node are encoded by the PPM algorithm, and the ‘E’ for the empty node denoting that space for voxels of the node does not exist.