Patent Description:
A point cloud is generally characterized by a set of points located in three-dimensional (3D) space. For each point in a point cloud, attributes such as color or other data can be associated with points. Given that the amount of data in a point cloud can become quite large, compression is needed in order to store the data to a storage medium such as a disk drive, or in order to transmit the data, such as signaling it to a bit-stream for streaming from a network-enabled server to a client device. While methods for compressing images are well-established, different methods are needed for compressing 3D point clouds, because unlike images which comprise a uniform grid of picture elements or pixels, the points in point clouds can be located anywhere in 3D space.

<NPL>, discloses a method for coding point clouds using prediction and coding of residual; <NPL>, discloses a point cloud coder for 3D immersive video using MPEG/AVC/HEVC like prediction coding scheme, block based; <NPL>, discloses a method of point cloud compression based on projection, prediction and residual coding. There is however is a need for methods, encoders and decoders for compressing, representing and processing point clouds.

Embodiments of the present disclosure relate methods, encoders and decoders representing point cloud signals, and more particularly, to compressing, representing and processing point clouds. A point cloud can be characterized by a set of points located in three-dimensional space, where attributes or other data can be associated with each point. Aspects of the present disclosure include compressing point clouds since the amount of data in a point cloud can be large, resulting in the need for compression, in order to either store the data to a storage medium, or in order to transmit the data, such as signaling the data to a bit-stream for streaming from a network-enabled server to a client device.

Regarding point prediction, some embodiments include signaling the coordinates of each point in a point cloud relative to a predetermined location, by computing the difference between the point position and the predetermined location and signaling it. This difference can be a prediction residual. The predetermined location can be the center of a block containing the points to be processed. The predetermined location can also be a previously-decoded point location, for example the first decoded point.

Some embodiments, which are useful for understanding but not part of the invention, include decoding a difference between a point position and a predetermined location, which can be a prediction residual.

Some embodiments, which are useful for understanding but not part of the invention, include signaling the coordinates of each point in a point cloud relative to a previously-decoded point. For example, given a point in a sequence of points, the difference between the location of the point and the location of the point that was processed or encoded or decoded immediately prior to the point in sequential order, can be computed. This difference can be a prediction residual.

Some embodiments, which is useful for understanding but not part of the invention, include decoding a difference between a point position of a point and the position of a previously-decoded point. This difference can be a prediction residual. The previously-decoded point can be the point that was decoded sequentially prior to the point.

Regarding point reordering and skipping, some embodiments include reordering a sequence of points such that the distance between subsequent points is minimized. Further other embodiments can include reordering a sequence of points such that the number of different distances between subsequent points is minimized.

Some embodiments include skipping the signaling of a point if it is collocated or within a threshold distance from a previously-signaled point. Additionally, if a given decoded point is collocated or within a threshold distance from a previously-signaled point, then the reconstruction of the point can be skipped. The signaling or reconstruction of points or decoded points outside a bounding box or minimum and maximum coordinate limits can also be skipped.

Regarding data-dependent partitioning, some embodiments include performing data-dependent non-uniform partitioning of a space, based on a scoring function that determines a location of the partitioning across at least one dimension of the space. Wherein, data-dependent non-uniform partitioning of the space can be based on measures or calculations from data representing the object, along with information about the current partitioning structure, such as a minimum or maximum block size, wherein a function, i.e. a scoring function, can specify how or where to split the current block or sub-block being processed.

Regarding organizing an unorganized point cloud, some embodiments include organizing an unorganized point cloud by mapping each point to positions in an organizational grid. The mapping process can be implemented with a scanning process, in which the points in the point cloud can be virtually scanned based on their position relative to the scan origin, and in an order based upon a scan direction or angle.

Regarding resampling and realigning a point cloud, some embodiments include using a scoring function to identify a subset of points in a point cloud, and subsequent processing of the point cloud is applied to the subset of points.

Some embodiments include resampling or aligning the points in a point cloud to a predetermined subset of locations such as a grid. The point locations can be signaled, or an index indicating to where the point was aligned can be signaled.

According to an embodiment of the present disclosure, which is useful for understanding but not part of the invention, a point cloud decoder including a processor to decode each block in a set of blocks from a point cloud, so as to obtain a decoded point cloud. Wherein each block includes a set of points, such that for each block the processor is to decode a set of prediction residuals from a compressed bitstream. Use a predetermined location in the block, and compute for each prediction residual in the set of prediction residuals, a position of a point by adding the prediction residual to the predetermined location, so as to obtain a set of decoded points for the block. Wherein the decoded points for the blocks in the set of blocks represent the decoded point cloud.

According to another embodiment of the present disclosure, which is useful for understanding but not part of the invention, a method for decoding a point cloud, including using a processor connected to a memory, to decode each block in a set of blocks from a point cloud, so as to obtain a decoded point cloud. Wherein each block includes a set of points, such that for each block the processor is for decoding a set of prediction residuals from a compressed bitstream. Using a predetermined location in the block, and computing for each prediction residual in the set of prediction residuals, a position of a point by adding the prediction residual to the predetermined location, so as to obtain a set of decoded points for the block. Wherein the decoded points for the blocks in the set of blocks represent the decoded point cloud.

According to another embodiment of the present disclosure, which is useful for understanding but not part of the invention, a point cloud decoder including a memory having data stored including previously decoded points. A processor to decode a sequence of points from a compressed bitstream, so as to obtain a decoded point cloud The processor is to decode a sequence of prediction residuals from the compressed bitstream. Compute for each prediction residual in the sequence of prediction residuals, a position of a point by adding the prediction residual to a position of a previously decoded point stored in the memory, so as to obtain a sequence of decoded points. Wherein the sequence of decoded points represents the decoded point cloud.

While the above-identified drawings set forth presently disclosed embodiments, other embodiments are also contemplated, as noted in the discussion. This disclosure presents illustrative embodiments by way of representation and not limitation.

<FIG> is a block diagram illustrating steps of a first point prediction method 100A, according to embodiments of the present disclosure. For example, instead of signaling a coordinate of each point relative to an origin or corner of a region, a component-wise difference between each point and a predetermined location in the block can be signaled. For instance, if the point position is (x,y,z) and the predetermined location in the block is defined as the center of the block (xc,yc,zc), then (x-xc,y-yc,z-zc) is signaled to the bit-stream.

Step <NUM> of <FIG> includes decoding a point cloud, using a processor connected to a memory, to decode each block in a set of blocks from a point cloud, so as to obtain a decoded point cloud, wherein each block includes a set of points.

Step <NUM> of <FIG> includes decoding a set of prediction residuals from a compressed bitstream for each block by a processor.

Step <NUM> of <FIG> includes using a predetermined location in the block.

Step <NUM> of <FIG> includes computing for each prediction residual in the set of prediction residuals, a position of a point by adding the prediction residual to the predetermined location, so as to obtain a set of decoded points for the block, wherein the decoded points for the blocks in the set of blocks represent the decoded point cloud.

<FIG> is a block diagram 100B illustrating some components implementing the methods of the present disclosure, according to embodiments of the present disclosure. For example, a processor <NUM> can be for methods, encoder or decoders of the present disclosure, that is connected to a memory <NUM>. The processor <NUM> can be connected to a network-enabled server <NUM>, which is connected to a client device <NUM>.

According to the present disclosure another method can include a second point prediction method. The second method discloses that given a set of point locations (xn,yn,zn), n = <NUM>,<NUM>,. ,N, the point locations (xn,yn,zn) can be signaled to the bit-stream. If predicting from the center or predetermined location in the block, then for each point location (xn,yn,zn), a prediction residual (xn-xc,yn-yc,zn-zc) is signaled to the bit-stream. In some cases, such as when groups of points are clustered near each other, the prediction residual can be reduced by using previously-decoded points as predictors for a currently-decoded point. For example, the first point n=<NUM> can be signaled as (xn,yn,zn) or (xn-xc,yn-yc,zn-zc). The second point n=<NUM> can be signaled as (x2-x1, y2-y1, z2-z1). The third point can be signaled as (x3-x2,y3-y2,z3-z2), etc. for all n.

For example, the second method can be for decoding a point cloud, including using a processor connected to a memory, to decode each block in a set of blocks from a point cloud, so as to obtain a decoded point cloud. Wherein each block includes a set of points, such that for each block the processor is for decoding a set of prediction residuals from a compressed bitstream. Using a predetermined location in the block, and computing for each prediction residual in the set of prediction residuals, a position of a point by adding the prediction residual to the predetermined location, so as to obtain a set of decoded points for the block. Wherein the decoded points for the blocks in the set of blocks represent the decoded point cloud.

According to the present disclosure another method can include a third point prediction method. The third method discloses that the first decoded point (x1,y1,z1) can be used to predict subsequent points, so the prediction residual signaled for point n=<NUM> is (x2-x1,y2-y1,z2-z1), and for point n=<NUM> (x3-x1,y3-y1,z3-z1), and so on for all n.

For example, the third method includes a point cloud decoder including a memory having data stored including previously decoded points. A processor to decode a sequence of points from a compressed bitstream, so as to obtain a decoded point cloud The processor is to decode a sequence of prediction residuals from the compressed bitstream. Compute for each prediction residual in the sequence of prediction residuals, a position of a point by adding the prediction residual to a position of a previously decoded point stored in the memory, so as to obtain a sequence of decoded points. Wherein the sequence of decoded points represents the decoded point cloud.

Given a sequence of points (xn,yn,zn), n=<NUM>,<NUM>,. ,N in a block or region, the points can be reordered such that the distance between subsequent points is minimized. Doing so reduces the magnitude or energy of the prediction residuals signaled for the case when a chain or sequence of points is signaled.

Given a sequence of points (xn,yn,zn), n=<NUM>,<NUM>,. ,N in a block or region, the points can be reordered such that the number of different distances between subsequent points is minimized. For example, for one coordinate, if the sequence of differences between five successive points is <NUM>,<NUM>,<NUM>,<NUM>, but if the points can be reordered such as the differences between the successive points becomes <NUM>,<NUM>,<NUM>,<NUM>, then although the total of the differences after reordering is higher than the total before reordering, the number of different distances is reduced. When a coder such as an entropy coder is used to signal these differences or prediction residuals, the residuals generated after reordering points can therefore have a reduced entropy, thus decreasing the number of bits that would need to be signaled to the bit-stream.

When encoding a set of points and signaling them to a bit-stream, if a given point is collocated or within a threshold distance from a previously-signaled point, then that point is not signaled to the bit-stream.

In another embodiment, if a given decoded point is collocated or within a threshold distance from a previously-signaled point, then that point is not reconstructed, i.e. it is not included in the reconstructed point cloud. The total number of reconstructed points in the decoded point cloud can therefore be reduced, thus reducing memory or storage requirements and improving rendering speeds due to the reduced number of points that would need to be rendered.

In another embodiment, if a given point is outside a bounding box or minimum and maximum coordinate limits, then it is not signaled to the bit-stream.

In another embodiment, if a given decoded point is outside a bounding box or minimum and maximum coordinate limits, then it is not included in the reconstructed point cloud.

Referring to <FIG>, the data-dependent non-uniform partitioning <NUM> can be performed according to embodiments of this present disclosure. The data-dependent non-uniform partitioning <NUM> can be based upon measures or calculations based on the data representing the object, along with information about the current partitioning structure, such as a minimum or maximum block size, a function can specify how or where to split the current block or sub-block being processed. For example, in <NUM> of <FIG>, instead of splitting at the halfway positions and breaking the object among different blocks as shown in the prior art method <NUM> of <FIG>, the first split creates four sub-blocks or sub-partitions, but only one of them, the lower-right one, is occupied by object data (see <FIG>), according to the present disclosure. Similarly, <FIG> shows the second split partitions with the lower-right block into four sub-blocks without splitting the object data among different sub-blocks, according to the present disclosure.

If each point in 3D space is mapped or indexed to a position on a 2D grid, then this data-dependent non-uniform partitioning method can be applied to the 2D grid of indices.

<FIG> is a schematic illustrating a PRIOR ART partitioning method for partitioning a 3D space as in an octree. In particular, <FIG> shows the partitioning in 2D space, with a quadtree as shown in <NUM>. The outside border in <NUM> denotes the initial block or partitioning of the space. The star is an example of an object represented by the data in the block. A decision process is used to decide whether to split the initial block into <NUM>^N blocks or partitions, where N is the dimension of the space (N=<NUM> for 2D space and N=<NUM> for 3D space). Each partition is split in half vertically and horizontally into <NUM>^N blocks. This splitting process repeats for each sub-block or sub-partition until a desired stopping criteria is met.

<FIG> is a schematic illustrating a process for using data alone a line to calculate where to perform the data-dependent non-uniform split, wherein given a block or patch <NUM>, data along the vertical halfway split position <NUM> is scanned horizontally by a sliding window <NUM> of data points, which means splitting the current block horizontally, i.e. by a vertical line <NUM>, e.g. into a left sub-block and a right sub-block for the case of partitioning a <NUM>-D grid, according to embodiments of the present disclosure. The skip area <NUM> is on one side of the search area <NUM>, used as input to a scoring function, where skip area <NUM> is on the other side of the search area <NUM>, such that the width of the skip area <NUM> can be set to <NUM>/<NUM> the width of the patch of interest.

<FIG> is a schematic illustrating a process for using data along a line to calculate where to perform the data-dependent non-uniform split, such that given a block or patch <NUM>, data along the horizontal split position <NUM> is scanned vertically by a sliding window <NUM> of data points, which means splitting the current block vertically, i.e. by a horizontal line <NUM>, e.g. into a lower sub-block and an upper sub-block for the case of partitioning a <NUM>-D grid according to embodiments of the present disclosure.

Referring to <FIG> and <FIG>, are schematics or diagrams of at least one process for using data alone a line to calculate where to perform the data-dependent non-uniform split. For example, <FIG> shows a block or patch <NUM>, where data along the vertical halfway split position <NUM> is scanned horizontally by a sliding window <NUM> of data points. These data points can be data related to the position of the points in the point cloud, such as the distance or depth from a plane, or it can be related to attributes in the data, such as brightness or color. The sliding window contains M points, and data across the vertical half-way position is scanned horizontally (<FIG>), i.e. M points are selected and are used as input to a function such as a scoring function. To prevent blocks from becoming too thin, minimum border distance or skip area <NUM> and <NUM> can be defined, for example <NUM>, in which the width of a skip area can be set to <NUM>/<NUM> the width of the patch, which ensures a minimum block size. The sliding window can slide one data point position at a time, or it can skip points, e.g. every other point, to simplify computation. For each window for which a score is computed, the best score, typically a maximum or minimum score, is located, and the position <NUM> corresponding to that best score is indicated as being the split position for splitting the current block horizontally, i.e. by a vertical line <NUM>, e.g. into a left sub-block and a right sub-block for the case of partitioning a <NUM>-D grid.

Referring to <FIG>, if it is desired to split the same block in the other direction, e.g. vertically, this process can be repeated in a direction orthogonal to the initial direction. This will result in a vertical split, i.e. a splitting by a horizontal line <NUM>, into an upper block or blocks and lower block or blocks. The output of this process is the position of each split, for example the location <NUM> of the maximum score resulting from a scoring function, or an index that can be mapped to the position of each split, for example, the position of the split line <NUM> relative to a corner of the patch. If a 2D block is split both horizontally and vertically, then the block is partitioned into four sub-blocks. If only horizontal or only vertical partitioning is done, then the block is partitioned into two sub-blocks. To prevent blocks from becoming too thin, minimum border distance or skip area <NUM> and <NUM> can be defined, for example <NUM>, in which the height of a skip area can be set to <NUM>/<NUM> the height of the patch, which ensures a minimum block size. The sliding window can slide one data point position at a time, or it can skip points, e.g. every other point, to simplify computation. For each window for which a score is computed, the best score, typically a maximum or minimum score, is located, and the position <NUM> corresponding to that best score is indicated as being the split position for splitting the current block horizontally, i.e. by a horizontal line <NUM>, e.g. into a top sub-block and a bottom sub-block for the case of partitioning a <NUM>-D grid.

<FIG> is a schematic illustrating a process for using multidimensional sliding window of data points to calculate where to perform the data-dependent non-uniform split on a block or patch <NUM>, wherein the data is a region oriented along the horizontal split position <NUM>, e.g. vertical rectangle <NUM>, according to embodiments of the present disclosure.

<FIG> is a schematic illustrating a process for using multidimensional sliding window of data points to calculate where to perform the data-dependent non-uniform split on a block or patch <NUM>, wherein the data is a region oriented along a vertical split position <NUM>, e.g. a horizontal rectangle <NUM>, according to embodiments of the present disclosure.

Referring to <FIG> and <FIG>, are diagrams of at least one process for using multidimensional data to calculate where to perform the data-dependent non-uniform split. Instead of using a one-dimensional sliding window of data as input to a scoring function as is illustrated in <FIG> and <FIG>, in <FIG> and <FIG>, data from a multidimensional region, for example, a 2D region <NUM> or <NUM>, can be used as input.

Regarding <FIG>, to prevent blocks from becoming too thin, minimum border distance or skip area <NUM> and <NUM> can be defined, for example <NUM>, in which the width of a skip area can be set to <NUM>/<NUM> the width of the patch, which ensures a minimum block size. The sliding window can slide one data point position at a time, or it can skip points, e.g. every other point, to simplify computation. For each window for which a score is computed, the best score, typically a maximum or minimum score, is located, and the position <NUM> corresponding to that best score is indicated as being the split position for splitting the current block horizontally, i.e. by a vertical line <NUM>, e.g. into a left sub-block and a right sub-block for the case of partitioning a <NUM>-D grid.

Regarding <FIG>, to also prevent blocks from becoming too thin, minimum border distance or skip area <NUM> and <NUM> can be defined, for example <NUM>, in which the height of a skip area can be set to <NUM>/<NUM> the height of the patch, which ensures a minimum block size. The sliding window can slide one data point position at a time, or it can skip points, e.g. every other point, to simplify computation. For each window for which a score is computed, the best score, typically a maximum or minimum score, is located, and the position <NUM> corresponding to that best score is indicated as being the split position for splitting the current block horizontally, i.e. by a horizontal line <NUM>, e.g. into a top sub-block and a bottom sub-block for the case of partitioning a <NUM>-D grid.

<FIG> is a schematic illustrating a 3D point cloud <NUM>, according to embodiments of the present disclosure.

<FIG> is a schematic illustrating a range map or depth map <NUM> which represents the distance of each point from a plane or the elevation or depth of each point is used as data input to the scoring function, according to embodiments of the present disclosure.

<FIG> is a schematic illustrating the output of a scoring function, for example a graph signal processing (GSP) score map <NUM>, in which higher score values <NUM> are illustrated using lighter colors, according to embodiments of the present disclosure. This scoring function, for example, can assign higher score values to areas of the patch, grid, or point cloud that exhibit discontinuities, as can be the case along edges of objects represented in 2D or 3D space.

Still referring to <FIG>, regarding resampling (to reduce the number of points in the block), given a region or block containing P1 points, the scoring function <NUM> can be used to identify a subset of P2 points whose score is less than or greater than a threshold. Subsequent processing of the region, block or partition then continues using the P2 points instead of the P1 points. Computational complexity of the system or the amount of data that is signaled to the bit-stream can be reduced when P2 < P1.

<FIG> is a schematic illustrating a PRIOR ART uniform splitting method <NUM> having a number of patches at <NUM>.

<FIG> are schematics illustrating a method of data-dependent non-uniform splitting <NUM> of <FIG> and <NUM> of <FIG>, according to embodiments of the present disclosure. Wherein, <FIG> shows the locations of non-uniform splitting when using sliding windows <NUM> of <FIG> and <NUM> of <FIG> along lines of data when calculating maximum score points <NUM> of <FIG> and <NUM> <FIG>, resulting in <NUM> patches. Wherein <FIG> shows the locations of non-uniform splitting when using sliding windows <NUM> of <FIG> and <NUM> <FIG> along regions or rectangles of data when calculating maximum score points <NUM> of <FIG> and <NUM> of <FIG>, resulting in <NUM> patches. Specifically, the data-dependent non-uniform splitting <NUM> of <FIG> and <NUM> of <FIG>, according to embodiments of the present disclosure show fewer patches, respectively, <NUM> patches for <NUM> of <FIG>, <NUM> patches for <NUM> of <FIG>, than that of the PRIOR ART method <NUM> of <FIG>, i.e. <NUM> patches.

Referring to <FIG>, the range map or depth map <NUM> represents the distance of each point from a plane or the elevation or depth of each point is used as data input to the scoring function. In the score map <NUM>, the point locations corresponding to the point cloud <NUM> or indices corresponding to the point cloud <NUM>, or corresponding to the range map <NUM>, are highlighted or illustrated with a lighter color where the scoring function was best, e.g. maximum. In this case, a graph signal processing (GSP) method was used to compute the scores. The locations at where the best scores occur in this example tend to correspond to edges or discontinuities in the point cloud <NUM> or range map <NUM>.

Referring to <FIG>, the optimal horizontal and vertical splitting locations <NUM> of <FIG> are shown when the methods of <FIG> and <FIG> are used. Also, the optimal horizontal and vertical splitting locations <NUM> of <FIG> are shown when the methods of <FIG> and <FIG> are used. The graph signal processing (GSP) method can be a fast resampling method. For example, when a particular graph filter is applied on the geometric information of each point in the point cloud, the filtering results or output <NUM> of <FIG> can serve as scores reflecting the importance of a point or set of points input to the filter, in terms of geometric properties. If any other attributes are of interest in the importance evaluation, the same graph filter can be applied on them, and the final filtering score could be a weighted sum of all the filtering results on geometric position and attributes associated with the points.

<FIG> is a flow diagram illustrating a list of some steps for implementing a splitting process <NUM>, according to embodiments of the present disclosure. Some steps for implementing a splitting process, can include step <NUM> which illustrates a splitting function, i.e. "Function Split (r)", that has as input a block, partition or patch r, that has an initial dimension such as width and height.

Referring to steps <NUM>, <NUM> and <NUM>, step <NUM> of FIG. 6A, shows that if the height is greater than the width, that this can be expressed as, "if Height of a patch > Width of a patch". Then, step <NUM> illustrates the split direction can be set to horizontal if the height is greater than the width, otherwise, the split direction can be set to vertical, as shown in step <NUM>, i.e. "choose split direction- > Horizontal, else split direction-> Vertical".

Step <NUM> of FIG. 6A, illustrates a scoring function is then computed, for example, a graph signal processing scoring function GSPscoreScan(conv. width), where conv. width indicates the size, or size and dimensions of the search area. Also, conv. width can include other information, such as the size of the skip area. The scoring function returns max_score_location, which is the location, e.g. a horizontal or vertical position or offset, of the location where the score is optimal, i.e. "max_score_location = GSPscoreScan(conv. The block, partition or patch or region r can be split into two regions r1 (step <NUM>) and r2 (step <NUM>).

Step <NUM> of FIG. 6A, illustrates the block, partition or patch or region (r ) can be split into region <NUM> (r1), wherein r1 corresponds to where the position in the region is to one side of the split location, i.e. r1 = set of points in patch whose position with respect to the split direction is less than ( < ) to the max_score_location.

Step <NUM> of FIG. 6A, illustrates the block, partition or patch or region (r ) that can be split into region <NUM> (r2), wherein r2 corresponds to where the position is on the other side of the split location, i.e. r2 = set of points in patch whose position with respect to the split direction is greater than or equal (>= ) to the max_score_location.

Step <NUM> of FIG. 6A, illustrates that this splitting process can be repeated on the sub-partitions r1, for example, if the sub-partitions satisfy certain criteria, such as a minimum size or dimension, i.e. dimensions of r1 > specified dimension or dimensions.

Step <NUM> of FIG. 6A, shows that if the sub-partitions satisfy the criteria that r1 is greater than the specified dimension, then call Function Split (r1), i.e. if the dimensions of r1 are greater (>) than a specified dimension or dimensions, then call Function Split (r1).

Step <NUM> of FIG. 6A, shows that if the sub-partitions do not satisfy the criteria, then the r1 splitting process is done, i.e. done splitting r1.

Step <NUM> of FIG. 6A, illustrates that this splitting process can be repeated on the sub-partitions r2, for example, if the sub-partitions satisfy certain criteria, such as a minimum size or dimension, i.e. dimensions of r2 > specified dimension or dimensions.

Step <NUM> of FIG. 6A, shows that if the sub-partitions satisfy the criteria that r2 is greater than the specified dimension, then call Function Split (r1), i.e. if the dimensions of r1 are greater (>) than a specified dimension or dimensions, then call Function Split (r1).

Step <NUM> of FIG. 6A, shows that if the sub-partitions do not satisfy the criteria, then the r2 splitting process is done, i.e. done splitting r2.

<FIG> is a block diagram illustrating some steps for decoding data from a bit-stream, when data-dependent non-uniform splitting is used, according to embodiments of the present disclosure. For example, <FIG> lists the syntax for a bit-stream used for decoding data, when data-dependent non-uniform splitting is used. The initial patch, region, or block size is decoded <NUM>, e.g. a height and width. A split flag for the region is decoded <NUM>. The presence of a split is determined by determining <NUM> whether the split flag is true (yes) or false (no). For example, a flag value of <NUM> can indicate the presence of a split, and a flag value of <NUM> can indicate that no split is present. If the split flag is true (yes), e.g. <NUM>, then the region will be split into sub-regions. If the split flag is false (no), e.g. <NUM>, then the region will not be split further. If the split flag is <NUM>, then the split location or split index which defines each sub-region is decoded <NUM>. The split location can be an offset, absolute location or coordinate, an integer specifying an offset from a pre-specified position in the current region such as the corner of the region, a horizontal, vertical, or horizontal and vertical offset, or an index to a look-up table, which maps each index to a horizontal, vertical, or horizontal and vertical offset. The set of split flags can be considered as being a specification of a split tree, which defines the split hierarchical for the entire set of partitions or sub-partitions. If the split flag is false (no), e.g. <NUM>, then the region is no longer split, and data associated with the region is decoded <NUM>, then the method is done with decoding syntax for region or sub-region <NUM>. This data can include control points for fitting patches, quantized prediction residuals, point location data, or attribute data. If the split flag is true (yes), e.g. <NUM>, and thus sub-regions are defined, then for each sub-region output by <NUM>, the syntax repeats for each sub-region starting from <NUM>. It is not necessary to go back to <NUM> to specify a width and height, because the decoder can infer the width and height of each sub-region based upon the split locations.

Still referring to <FIG>, noted is that the split index includes, but is not limited to:.

Given a region, block or partition containing arbitrarily-located points, the points are resampled or aligned to a predetermined subset of locations. For example, if the coordinates of each point comprise floating point numbers between <NUM> and <NUM>, the coordinates can be aligned, such as through a quantization or repositioning process, such that all coordinates are multiples of <NUM>. In this example, the points would therefore be aligned to a grid of resolution <NUM>. This aligning or resampling therefore reduces the number of possible coordinates for each point, which reduces the number of possible different values for coordinates that would need to be signaled to the bit-stream.

In another embodiment, the coordinates would not be signaled directly, but an index would be signaled. For example, if the coordinate of each point is greater than or equal <NUM> and is less than <NUM>, and if a grid resolution is <NUM>, then point coordinates in the region would be realigned to <NUM> or <NUM>. In that case, a one-bit flag can be used to indicate whether a coordinate has been aligned to <NUM> or <NUM>. If the grid resolution is <NUM>, then nothing would need to be signaled to indicate the realigned point coordinates, as they would be co-aligned with the origin or corner of the region.

<FIG> is a schematic illustrating a method for organizing an unorganized point cloud, according to embodiments of the present disclosure.

<FIG> is a schematic illustrating an organizational grid or a matrix for example, in 2D space, with each position in the grid having an index, according to embodiments of the present disclosure;.

<FIG> is a schematic illustrating a scanning process for a method for organizing an unorganized point cloud, according to embodiments of the present disclosure;.

<FIG> is a schematic illustrating a mapping process for a method for organizing an unorganized point cloud, according to embodiments of the present disclosure;.

For example, the point cloud <NUM> of <FIG> can have N arbitrarily-located points at coordinates (xn,yn,zn), n=<NUM>,<NUM>,. ,N and is denoted as being an unorganized point cloud. In this example, each point is labeled with a letter, A through G. An organizational grid <NUM> of <FIG> is defined as a matrix or grid, for example, in 2D space, with each position in the grid having an index. For the 2D grid case, there is a horizontal index u <NUM> and vertical index v <NUM> of <FIG>. Each point in the point cloud <NUM> of <FIG> will be mapped, thus organized, to a position in the grid <NUM> of <FIG>. Therefore, each point in the point cloud can be indexed via (u,v). Subsequent partitioning of the (u,v) space <NUM> therefore partitions the point cloud <NUM> into subgroups of points where each element in a given partition of (u,v) space corresponds to a subset of points in the point cloud <NUM>.

In one embodiment, the mapping of each point in the point cloud <NUM> to positions in the organizational grid <NUM> of <FIG> is predetermined or known before the point cloud is encoded.

In another embodiment, a process maps each point of the point cloud <NUM> of <FIG> to a position in the organizational grid <NUM> of <FIG>. This process can be a scanning process <NUM> of <FIG>. A position such as a fixed position in 3D space is designated as the scan origin <NUM> of <FIG>. The points in the point cloud <NUM> of <FIG> will be virtually scanned based on their position relative to the scan origin, in an order based upon a scan direction <NUM> of <FIG>. The scan direction can be specified for example by an angle θ relative to a fixed direction. There are J scans, with each scan having a radius or distance <NUM> of <FIG> from the scan origin rj, j=<NUM>, <NUM>,. In the mapping example <NUM> of <FIG>, the point cloud is scanned <NUM>, <NUM>, <NUM> with radii r<NUM>, r<NUM>, r<NUM>, respectively. In this case, the number J of radii correspond to the number of elements V <NUM> of <FIG> in the v-direction of the organizational grid. All points in the point cloud within a given threshold distance from the scan are associated with that scan and then are removed from future consideration for subsequent scans. The range of angles over with a scan operates is divided into U equal partitions where U is the number of elements <NUM> of <FIG> in the organizational grid in the u direction. Given a scan radius rj, the scan <NUM> of <FIG> associated with that radius can be divided into U partitions. These partitions can be equally spaced with respect to the scan direction <NUM>. For all points in the point cloud that have been associated with scan rj, each of those points is assigned to an index position u on the organization grid corresponding to the partition of the scan. Larger values of U would correspond to either longer scans or scans having smaller partitions, e.g. finer resolution scans. In <NUM>, points B and D are associated with the first scan, and are placed in the corresponding row v=<NUM> of the organizational grid. Points A and C are associated with the second scan, and points E, F, and G are associated with the third scan. The final mapping <NUM> of <FIG> of each point in the point cloud to the organizational grid allows each point in the 3D point cloud to be indexed by a location (u,v) in the organizational grid. Empty positions in the organizational grid are not mapped to a point in the point cloud. By mapping in this way, points that are adjacent to each other in 3D space are likely to be adjacent to each other in the organizational grid. Selecting regions or groups of points in the organizational grid therefore are likely to select related groups of points in 3D space.

In another embodiment, U and V are sufficiently large so every point in the point cloud is mapped to a unique position on the organizational grid.

In another embodiment, more than one point can be mapped to the same position in the organizational grid. In this case, the set of points that are mapped to a given position in the organizational grid can be represented by a single point, such as the average of the point positions or some other function of the point positions.

Claim 1:
A point cloud encoder, comprising:
a processor (<NUM>) to encode a block of points from the point cloud (<NUM>), so as to obtain an encoded point cloud, wherein the point cloud (<NUM>) includes a set of blocks and each block includes a set of points, wherein the processor (<NUM>) is to use a predetermined location in the block, compute for each point, a difference between a position of the point to the predetermined location, so as to obtain a set of prediction residuals for the set of points in the block, and a transmitter to transmit the set of prediction residuals over a compressed bitstream,
wherein the point cloud 3D space is mapped or indexed to a position on a 2D grid, characterized in that the point could encoder further comprises:
perform data-dependent non-uniform partitioning on said <NUM>-D grid of a region having a set of points, such that a location of the partitioning across at least one of the two dimensions comprising the <NUM>-D grid is determined by a scoring function which calculates a score associated with the position and attribute of each of the points, to identify a split position for splitting the current block, which is a 2D grid, into two sub-blocks as the location of the partitioning, wherein the scoring function assigns higher values to areas of the point cloud that exhibit edges,
wherein an input to the scoring function is a subset of points along one of the two dimensions within a search area, and the location of the point that corresponds to where an output of the scoring function is maximized, corresponds to the split position in the one of the two dimensions, and the current block is split into the two sub-blocks by a splitting line passing through the splitting position and along the other dimension perpendicular to the one dimension of the two dimensions.