Terminable spatial tree-based position coding and decoding

1. A method for encoding input spatial points by a spatial tree structure, comprising:

constructing a cell around the input spatial points;

recursively dividing the cell into sub-cells at different layers; and

assigning a symbol for each sub-cell indicating whether or not there is any spatial points within each sub-cell,

wherein the method further comprising:

terminating further division of the sub-cell, if the sub-cell contains only one spatial point and a distance between a center point of the sub-cell and the spatial point contained in the sub-cell is smaller than a given error tolerance;

encoding, into a bitstream, a position of said input spatial point according to said spatial tree structure comprising the sub-cells.

2. The method according to claim 1 , wherein the given error tolerance is an allowed maximal error which is set depending on a quality requirement of users.

3. The method according to claim 1 , further comprising determining whether to terminate the division of the sub-cell by appending a termination code as a child of a node corresponding to the sub-cell in the spatial tree structure as a function of a maximal number of division layers.

4. The method according to claim 3 , wherein the division of the sub-cell is terminated by appending the termination code as the child of the node corresponding to the sub-cell in the spatial tree structure when the division does not reach the maximal number of division layers.

5. The method according to claim 3 , wherein the division of the sub-cell is terminated without appending the termination code as the child of the node corresponding to the sub-cell in the spatial tree structure when the division reaches the maximal division layer.

6. The method according to claim 3 , further comprising determination of whether to enable the method as a function of an estimation of entropy compared with the case not using the method.

7. A method for decoding a bitstream of a spatial tree structure, comprising:

decoding mode information of the bitstream to determine a terminal coding mode is applied with the bitstream,

recursively dividing a cell of the spatial tree structure into sub-cells at different layers;

wherein the method further comprising:

if the sub-cell contains only one spatial point, terminating further division of the sub-cell if a termination code for the sub-cell is decoded or the division of the sub-cell reaches a maximal number of division layers,

decoding position of spatial points according to said spatial tree structure comprising the sub-cells.

8. The method according to claim 7 , wherein the mode information is a 1-bit flag at the beginning of the bitstream.

9. An encoder for encoding input spatial points by a spatial tree structure, said encoder receives data and generates an encoded signal, said encoder being adapted to perform the following operations:

constructing a cell around the input spatial points;

recursively dividing the cell into sub-cells at different layers; and

assigning a symbol for each sub-cell indicating whether or not there is a spatial point within each sub-cell, and

terminating further division of the sub-cell, if the sub-cell contains only one spatial point and a distance between a center point of the sub-cell and the spatial point contained in the sub-cell is smaller than a given error tolerance;

encoding, into a bitstream, a position of said input spatial paint according to said spatial tree structure comprising the sub-cells.

10. The encoder according to claim 9 , wherein the given error tolerance is an allowed maximal error which is set depending on a quality requirement of users.

11. A decoder for decoding a bitstream of a spatial tree structure, said decoder receiving an encoded signal and generates spatial tree structure, said decoder being adapted to perform the following operations:

decoding mode information of the bitstream to determine a terminal coding mode is applied with the bitstream,

recursively dividing a cell of the spatial tree structure into sub-cells at different wherein the method further comprising:

if the sub-cell contains only one spatial point, terminating further division of the sub-cell if a termination code for the sub-cell is decoded or the division of the sub-cell reaches a maximal number of division layers,

decoding position of spatial points according to said spatial tree structure comprising the sub-cells.

12. The decoder according to claim 11 , wherein the mode information is a 1-bit flag at the beginning of the bitstream.

13. The encoder according to claim 9 , further adapted to perform determining whether to terminate the division of the sub-cell by appending a termination code as a child of a node corresponding to the sub-cell in the spatial tree structure as a function of a maximal number of division layers.

14. The encoder according to claim 13 , wherein the division of the sub-cell is terminated by appending the termination code as the child of the node corresponding to the sub-cell in the spatial tree structure when the division does not reach the maximal number of division layers.

15. The encoder according to claim 13 , wherein the division of the sub-cell is terminated without appending the termination code as the child of the node corresponding to the sub-cell in the spatial tree structure when the division reaches the maximal division layer.

16. The encoder according to claim 13 , further adapted to perform determining whether to enable the method as a function of an estimation of entropy compared with the case not using the method.