Patent Description:
More particularly, it deals with the post-processing of point clouds.

Thus, the disclosure concerns a method for hole filling of a point cloud and a corresponding device. It also concerns methods for encoding and decoding a point cloud and corresponding encoder and decoder. It further concerns a computer program implementing the hole filling method of the invention.

The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.

A point cloud consists in a set of points usually intended to represent the external surface of a 3D object but also more complex geometries like hair, fur that may not be represented efficiently by other data format like meshes. Each point is defined by its 3D spatial location (x, y and z coordinates in the 3D space), i.e. geometry information, and possibly by other associated attributes, which typically include the color information represented in the RGB or YUV or any other color coordinate system. Other attributes may include a transparency, a reflectance, etc. Geometry can be regarded as one of the attribute data. In the rest of this disclosure, both geometry and other attribute data are considered as attributes of points.

In the following, a colored point cloud is considered, i.e. a set of <NUM>-component points (X, Y, Z, R, G, B) or equivalently (X, Y, Z, Y, U, V) where (X,Y,Z) defines the spatial location of a point in a 3D space and (R,G,B) or (Y,U,V) defines a color of this point.

Colored point clouds may be static or dynamic depending on whether or not the point cloud evolves with respect to time. It should be noticed that in case of a dynamic point cloud, the number of points is not constant but, on the contrary, generally evolves with time. A dynamic point cloud is thus a time-ordered list of sets of points.

Point cloud data sources are found in many applications. Important applications relying on huge point cloud data sources can be found in geographic information systems, robotics, medical tomography and scientific visualization.

Beyond these applications that are more industrial and scientifically oriented, the rise in popularity of inexpensive 3D scanners based on time of flight or other depth sensing technologies, 3D capturing on mobile devices and the rise of cloud based 3D printing are creating a huge demand for large scale interoperable compressed 3D point cloud storage and transmission data formats in the consumer market.

Scanned 3D point clouds often have thousands of points and occupy large amounts of storage space. Additionally, they can be generated at a high rate when captured live from 3D scanners, increasing the data rate even further. Therefore, point cloud compression is critical for efficient networked distribution and storage.

During the capturing of a point cloud, due to surface reflectance properties, occlusions and accessibility limitations, certain areas of the object may be not sampled leading to holes in the resulting point cloud. These holes represent significative missing parts of the 3D point cloud.

Thus, a hole filling technique must be used in order to complete the point cloud.

The prior art works on point cloud hole filling are mainly based on boundary point detection, close boundary loop extraction, and boundary loop filling.

Boundary point detection is performed by projecting the neighboring points of each point of the point cloud to its local tangent plane. Those points whose projected neighboring points cannot form a whole circle are regarded as boundary points. Then, boundary loop extraction is performed by tracing neighboring detected boundary points. When the current tracing boundary meets the boundary point where the current tracing starts, a close boundary loop is found. The resultant closed boundary loops are then filled by adding points in the middle of the boundary loops.

In the prior art, only the closed boundary point loops are regarded as boundaries and will be filled. Therefore, the boundary point detection needs to be accurate. If some boundary points are missed or some points are wrongly detected as boundary points during the detection step or otherwise, boundary loops cannot be closed.

However, boundary point detection is usually difficult, as no connectivity between points is available. Indeed, the calculation of the local tangent plane is dependent on the choice of the neighborhood. As there is no connectivity information available, it is difficult to define the correct neighborhood of each point in the point cloud. Therefore, boundary point detection is usually difficult.

Also, the boundary loop filling step is usually dependent on complex operations like polynomial fitting, surface reconstruction and triangulation.

The article "<NPL>) discloses a method for detecting holes present in laser scans using an angle gap criterion.

Thus, the prior art point cloud hole filling techniques are not suitable for use-cases that require low complexity, such as on-the-fly point cloud rendering and point cloud decoding.

The present disclosure proposes a solution for improving the situation by providing methods and devices according the enclosed claims.

Accordingly, the present disclosure provides a method according to claim <NUM> for hole filling of a point cloud having at least one hole.

Thus, the method of the present disclosure enables a significant reduction of the complexity of the prior art hole filling techniques by using a plane insertion operation. Also, as the present solution does not require to extract closed boundary point loops, accurate boundary point detection is not needed, making the hole filling method of the present disclosure more robust than the prior art solutions.

According to an embodiment, a point of the point cloud is detected as a boundary point using an angle criterion.

This technique for detecting boundary points is described in section <NUM> of the article of <NPL>. Its accuracy is not optimal but it is sufficient for the hole filling method of the present disclosure that does not need to extract precise and close boundary point loops.

According to the invention, a point of the point cloud is detected as a boundary point if the largest angle gap between two consecutive local neighbors of the point is larger than a first threshold and the largest angle gap between two consecutive further neighbors of the point is smaller than a second threshold.

Local neighbors means here close neighbors, for instance distance-<NUM> neighbors, while further neighbors are located further, for instance distance-<NUM> neighbors. The second threshold condition allows to avoid detecting false boundary points.

For example, the first threshold is equal to <NUM> degrees and the second threshold is equal to <NUM> degrees.

According to the invention, the angle gap between consecutive neighbors is the angle gap between the projections of these neighbors on a tangent plane of the point. Advantageously, at least one boundary point group is defined for each boundary region and each boundary point group is covered by one plane.

Advantageously, the method comprises determining an attribute of each new point. According to an embodiment, the attribute is the color.

Advantageously, the attribute is determined by interpolation from nearby points of the point cloud.

According to an embodiment, the interpolation is performed in the (R,G,B) color space.

According to another embodiment, the interpolation is performed in the (Y,U,V) color space.

The present disclosure also provides a hole filling device according to claim <NUM> for hole filling a point cloud having at least one hole.

Advantageously, the modules of the hole filling device are implemented by one or more processors.

According to another aspect, the present disclosure provides a method for coding a point cloud representing a 3D object, comprising a hole filling post-processing according to the present disclosure.

The present disclosure also provides a method for decoding a point cloud representing a 3D object, comprising a hole filling post-processing according to the present disclosure.

The present disclosure also provides an encoder comprising the hole filling device of the present disclosure.

The present disclosure further provides a decoder comprising the hole filling device of the present disclosure.

The methods according to the disclosure may be implemented in software on a programmable apparatus. They may be implemented solely in hardware or in software, or in a combination thereof.

Since these methods can be implemented in software, they can be embodied as computer readable code for provision to a programmable apparatus on any suitable carrier medium. A carrier medium may comprise a storage medium such as a floppy disk, a CD-ROM, a hard disk drive, a magnetic tape device or a solid state memory device and the like.

The disclosure thus provides a computer-readable program comprising computer-executable instructions to enable a computer to perform the hole filling method of the invention.

The diagram of <FIG> illustrates an example of the general algorithm for such computer program.

The present invention is illustrated by way of examples, and not by way of limitation, in the figures of the accompanying drawings, in which like reference numerals refer to similar elements and in which:.

The method for hole filling of a 3D point cloud according to an embodiment of the present disclosure is illustrated in the flowchart of <FIG>.

The method starts at step <NUM> by a detection of the boundary points of the point cloud.

A point of the point cloud is detected as a boundary point using preferably an angle criterion.

Thus, a point P of the point cloud with the largest angle gap g between two consecutive neighbors of P projected on the local tangent plane of P larger than a first threshold T1 are considered as possible boundary points. A possible value of T1 is <NUM> degrees. According to one embodiment, for each point P, a mean point M and a covariance matrix C are calculated using the distance-S neighborhood, {Ni }, of P, where S=<NUM> for example, using the following: <MAT> <MAT> where n is the number of P's distance-S neighbors.

Here, the distance-S neighborhood Neigh(xNeigh, yNeigh, zNeigh) of a point P(xp, yp, zp) is defined by <MAT>.

Then, the eigenvectors and corresponding eigenvalues of C are calculated. After being normalized and sorted in decreasing order of eigenvalues, the three eigenvectors are chosen as the X, Y and Z axes of a local coordinate system at the point P.

The origin of the local coordinate system is M.

Let's denote the three sorted and normalized eigenvectors as <MAT> and <MAT>, corresponding to the X, Y and Z axes in the figure.

Each S-neighbor Ni is projected to the XOY plane of the local coordinate system as follows.

Firstly, <MAT>, the coordinates of Ni represented in the local coordinate system, are calculated by <MAT>, where Transf is a 4x4 matrix represented in <FIG>. Then, <MAT> is the result of projecting Ni to the XOY plane of the local coordinate system.

As it appears in <FIG>, the matrix Transf includes a 3x3 rotation matrix R and a translation vector T.

According to an embodiment, R is calculated by R = q * p, where q and p are two quaternions.

The vector p represents the rotation which makes the X axis of the world coordinate system to be aligned with the X axis of the local coordinate system.

p is determined by the rotation axis <MAT> and the rotation angle <MAT>. Then, p = <MAT>.

The vector q represents the rotation which makes the Y axis of the world coordinate system, after being rotated by p, to be aligned with the Y axis of the local coordinate system.

q is determined by the rotation axis <MAT> and the rotation angle <MAT> <MAT>.

Secondly, the angle ∝i between <MAT> and <MAT> is calculated by ∝i = arctan<NUM>(y' , x' ).

Thirdly, all the neighbors Ni are sorted by the angle ∝i into a list.

Fourthly, the difference of ∝i of two adjacent Ni in the list of all Ni is calculated. If the largest difference, or gap, noted g is larger than a first threshold T1, then P is considered as a possible boundary point.

Then for each possible boundary point P of the point cloud, the following process is carried out.

This process starts by finding further neighbors of the point P. The further neighbors of P are defined as all the points falling on the surface of the cube or sphere which is centered at P and with scale or diameter <NUM>*S'.

The choice of the value of S' is preferably dependent on the scale of the hole to be filled, for instance of S' may be chosen equal to <NUM>.

Then, all the further neighbors of P are projected on the tangent plane of P and sorted according to their angles around P.

Then, the largest gap g' between two consecutive projected further neighbors is computed. Only points having g' smaller than a second threshold T' are considered as boundary points. A possible value of T' is <NUM> degrees.

Then, at step <NUM>, all the detected boundary points are sorted into a queue, named all_boundary_point_queue, such that the number of their distance-N neighbors that are also boundary points is increasing. A possible value of N is <NUM>. Indeed, the boundary points with more neighbors, which are also boundary points, are most likely to be located on a big hole.

At step <NUM>, it is checked if all_boundary_point_queue is empty. If yes, the process ends.

Otherwise, the first boundary point is popped out from all_boundary_point_queue and is considered at step <NUM>. A queue associated to this boundary point, named current_boundary_point_queue, is created. Said first boundary point is marked as visited and pushed into current_boundary_point_queue. A new boundary point region, boundary_region_current, is created and set as empty in the beginning.

At step <NUM>, it is checked whether or not current_boundary_point_queue is empty. If this is the case, the process continues to step <NUM> described later on.

If current_boundary_point_queue is not empty, the boundary point at the front of current_boundary_point_queue, named boundary_point_cur, is popped out from current_boundary_point_queue.

At step <NUM>, boundary_point_cur is added to boundary_region_current.

At step <NUM>, the distance-N neighbors of boundary_point_cur which are also boundary points and not marked as visited yet are added to current_boundary_point_queue.

Then, at step <NUM>, said distance-N neighbors of boundary_point_cur which are also boundary points and not marked as visited yet are marked as visited.

Then, the process goes to step <NUM> where it is checked if current_boundary_point_queue is empty.

If the queue is empty, the process goes to step <NUM> at which boundary_region_current is covered with several planes in order to approximate the underlying surface around each boundary region.

Firstly, the covering process starts from a boundary point, noted as boundary-point-start, belonging to boundary_region_current which has not been marked as covered to construct a boundary point group noted as boundary-point-group. The boundary-point-start is added to boundary-point-group and boundary-point-start is marked as covered and checked.

Secondly, distance-N neighbors of boundary-point-start which belong to boundary_region_current and have not been marked as covered and checked are considered. Then a mean point MEAN and a normal NORMAL are calculated by applying Principal Component Analysis (PCA) on boundary_point_start and said its distance-N neighbors of boundary_point_start which belong to boundary_region_current and have not been marked as covered and checked.

Then, a new plane PLN is defined by NORMAL*(P-MEAN) = <NUM>, where * is vector dot product.

Thirdly, the distance of each of the distance-N neighbors of boundary-point-start, which belong to boundary_region_current and have not been marked as covered and checked, noted as boundary-point-neigh, to PLN is calculated as NORMAL*( boundary-point_neigh -MEAN).

Fourthly, on one side the distance-N neighbors of boundary-point-start which belong to boundary_region_current, which have not been marked as covered and as checked, and which their distances to PLN is less than a user defined threshold THRES_PLANE are added to boundary-point-group and marked as covered and checked. For example, THRES_PLANE=<NUM>. On the other side, the distance-N neighbors of boundary-point-start which belong to boundary_region_current, have not been marked as covered and as checked, and their distances to PLN is bigger than a user defined threshold THRES_PLANE are marked as checked and are not added to boundary-point-group.

The above process is repeated until all the points belonging to boundary_region_current are marked as checked.

Then, it is checked whether all the boundary points belonging to boundary_region_current are marked as covered. If yes, the process goes to step <NUM>. If not, all points belonging to boundary_region_current are marked as unchecked. Then, the plane growing process as described above is repeated starting from a boundary point belonging to boundary_region_current that has not been marked as covered and a new boundary-point-group is defined. The plane growing and new boundary point group creation process are repeated until all the boundary points belonging to boundary_region_current are marked as covered.

At step <NUM>, for each boundary region, the associated planes are transformed to new points to be included in the point cloud.

Firstly, potential new points to be included in the point cloud are determined as follows for each of the determined planes at step <NUM>.

For each boundary point group, the associated plane is defined by applying PCA on all the boundary points belonging to the boundary point group. All the boundary points belonging to the current boundary point group and their distance N' neighbors are projected on the plane associated to the current boundary point group. Then, on the plane, inside a bounding box of all projected points, the unoccupied points constitute one group of the potential new points. A possible value of N' is <NUM>.

Secondly, each group of the potential new points is then projected to the world coordinate system by applying the reverse process of projecting points to local coordinate system described before. Overlapping points are merged together. After merging, the left new points are added to the input point cloud.

Then, at step <NUM>, for each new point PNew inserted in the point cloud at step <NUM>, its color is determined by interpolating the color attribute of its nearby existing and newly added points of the point cloud.

The color interpolation may be performed either in the (R,G,B) or in the (Y,U,V) space.

For instance, the interpolation advantageously uses the following formula expressed in the (Y,U,V) space: <MAT> where PNearest is the nearest neighbor to PNew except PUnderSampled.

The same formula can be written in the (R,G,B) space by replacing (Y,U,V) by (R,G,B).

<FIG> is a block diagram of an exemplary embodiment of an encoder <NUM> implementing the encoding method of a 3D point cloud of the present disclosure.

Advantageously, the encoder <NUM> includes one or more processors and a memory <NUM>.

The encoder <NUM> comprises a coding module <NUM> configured to encode an input 3D point cloud into a bit stream.

According to the present disclosure, the encoder <NUM> also comprises a hole filling device <NUM> comprising:.

According to the represented embodiment, a bus <NUM> provides a communication path between various elements of the encoder <NUM>. Other point-to-point interconnection options (e.g. non-bus architecture) are also feasible.

<FIG> is a block diagram of an exemplary embodiment of a decoder <NUM> implementing the decoder method of the present disclosure.

Advantageously, the decoder <NUM> includes one or more processors and a memory <NUM>.

The decoder <NUM> comprises a decoding module <NUM> configured to decode an input bit stream into a 3D point cloud.

According to the present disclosure, the decoder <NUM> also comprises the hole filling device <NUM> described above.

According to the represented embodiment, a bus <NUM> provides a communication path between various elements of the decoder <NUM>. Other point-to-point interconnection options (e.g. non-bus architecture) are also feasible.

While there has been illustrated and described what are presently considered to be the preferred embodiments of the present invention, it will be understood by those skilled in the art that various other modifications may be made, and equivalents may be substituted, without departing from the true scope of the present invention. Additionally, many modifications may be made to adapt a particular situation to the teachings of the present invention without departing from the central inventive concept described herein.

Furthermore, an embodiment of the present invention may not include all of the features described above. Therefore, it is intended that the present invention is not limited to the particular embodiments disclosed, but that the invention includes all embodiments falling within the scope of the appended claims.

Expressions such as "comprise", "include", "incorporate", "contain", "is" and "have" are to be construed in a non-exclusive manner when interpreting the description and its associated claims, namely construed to allow for other items or components which are not explicitly defined also to be present. Reference to the singular is also to be construed to be a reference to the plural and vice versa.

Claim 1:
A computer-implemented method for hole filling of a scanned or captured point cloud having at least one hole, comprising:
- detecting (<NUM>) boundary points of the point cloud;
- grouping (<NUM>) the detected boundary points in boundary regions based on their spatial adjacency;
- covering (<NUM>) each boundary region with at least one plane; and
- inserting (<NUM>) new points in the point cloud using the planes covering the boundary regions;
wherein a point of the point cloud is detected as a boundary point based on an angle gap between two consecutive local neighbors of the point;
wherein the angle gap between consecutive neighbors is the angle gap between the projections of these neighbors on the local tangent plane of the point; and
wherein a point of the point cloud is detected as a boundary point if the largest angle gap between two consecutive local neighbors of the point is larger than a first threshold and the largest angle gap between two consecutive further neighbors of the point is smaller than a second threshold.