Determining one or more scanner positions in a point cloud

1. A method, comprising:

receiving a point cloud from at least one scanner, wherein the point cloud includes a plurality of points in space representing one or more external surfaces of at least one object in a scene, where each point of the point cloud has a position relative to the at least one scanner;

computing a density value for each point of the point cloud based on a mean distance from the point to a selected number of neighboring points in the point cloud;

selecting a set of points, from the point cloud, determined to be high density points based on the density value determined for each point of the point cloud;

creating one or more clusters from the set of points based on a non-oriented normal value and a curvature value computed for each point of the first set of points;

identifying a selected cluster of the one or more clusters as a circular shaped cluster;

identifying a plurality of inner edge points of the selected cluster;

determining an ellipse that fits the plurality of inner edges points of the selected cluster; and

determining an estimated z coordinate, an estimated y coordinate, and an estimated z coordinate of the scanner utilizing a center of the ellipse and a non-linear least square solver with a threshold number of inner edge points with different density values.

2. The method of claim 1 , wherein the selected number of neighboring points is 50 nearest neighboring points of the point.

3. The method of claim 1 , wherein each point of the set of points is determined to be a top 1% densest point in the point cloud.

4. The method of claim 1 , further comprising computing the non-oriented normal value and the curvature value utilizing a principal component analysis algorithm.

5. The method of claim 1 , wherein a selected point in a first cluster of the one or more clusters has a curvature value of less than 0.1.

6. The method of claim 5 , wherein

an absolute value of a dot product of the non-oriented normal value for the selected point and the non-oriented normal value for each additional point in the first cluster is greater than 0.8, and

the absolute value of the dot product of the non-oriented normal value for the selected point and the non-oriented normal value for a sub-cluster consisting of 29 random points in the first cluster and each additional point is greater than 0.8.

7. The method of claim 1 , wherein identifying that the selected cluster of the one or more clusters is the circular shaped cluster further comprising

determining that a centroid density value of a cluster centroid of the selected cluster is at least 11 times greater than the density value of a particular point in the selected cluster that is a maximum density value of the selected cluster.

8. The method of claim 1 , further comprising:

determining a mean density value for the selected cluster;

computing a local centroid for a particular point in the selected cluster based on the position of the selected number of neighboring points of the particular point;

computing a distance between the particular point and the local centroid;

computing a distance between a cluster centroid and the local centroid; and

determining that the particular point is an inner edge point when d 1 +0.85*MD<d 2 ,

wherein d 1 is the distance between the particular point and the local centroid, MD is the mean density value, and d 2 is the distance between the cluster centroid and the local centroid.

9. The method of claim 1 , further comprising utilizing a least square algorithm to determine an equation for the ellipse fits the plurality of inner edge points.

10. The method of claim 1 , wherein the threshold number of inner edge points with different density values is N, and the method further comprising:

utilizing N(N-1)/2 different combinations of

d

1

*

r

1

2

cos

⁡

(

α

1

)

=

d

2

*

r

2

2

cos

⁡

(

α

2

)

for the threshold number of inner edge points with the non-linear least square solver, where d 1 represents the density value of a first point of the inner edge points with different density values, r 1 represents the distance between the scanner and the first point of the inner edge points with different density values, a 1 represents an angle between the normal of the first point and a direction from the first point to the scanner, where d 2 represents the density value of a second point of the inner edge points with different density values, r 2 represents the distance between the scanner and the second point of the inner edge points with different density values, and a 2 represents an angle between the normal of the second point and a direction from the second point to the scanner.

11. The method of claim 1 , further comprising generating a three dimension model of a scene represented by the point cloud, where the generating is performed utilizing the point cloud with at least the estimated x coordinate, the estimated y coordinate, and the estimated z coordinate of the scanner.

12. A system for determining a scanner position for each of one or more scanners in a point cloud, the system comprising:

processing logic configured to:

receive the point cloud from at least one scanner of the one or more scanners, wherein the point cloud including a plurality of points in space representing one or more external surfaces of at least one object in a scene, where each point of the point cloud has a position relative to the at least one scanner;

compute a density value for each point of the point cloud based a mean distance from the point to a selected number of neighboring points in the point cloud;

select a set of points, from the point cloud, determined to be high density points based on the density value determined for each point of the point cloud;

create one or more clusters from the set of points utilizing a principal component analysis algorithm;

identify a selected cluster of the one or more clusters as a circular shaped cluster;

identify a plurality of inner edge points of the selected cluster;

determine an ellipse that fits the plurality of inner edges points of the selected cluster; and

determine an estimated x coordinate, an estimated y coordinate, and an estimated z coordinate of the scanner utilizing a center of the ellipse and a non-linear least square solver with a threshold number of inner edge points with different density values.

13. The system of claim 12 , wherein the selected number of neighboring points is 50 nearest neighboring points of the point.

14. The system of claim 12 , wherein each point of the set of points is determined to be a top 1% densest point in the point cloud.

15. The system of claim 12 , wherein the processing logic is further configured to compute a non-oriented normal value and the curvature value utilizing the principal component analysis algorithm.

16. The system of claim 15 , wherein a selected point in a first cluster of the one or more clusters has a curvature value of less than 0.1.

17. The system of claim 16 , wherein

an absolute value of a dot product of the non-oriented normal value for the selected point and the non-oriented normal value for each additional point in the first cluster is greater than 0.8, and

the absolute value of the dot product of the non-oriented normal value for the selected point and the non-oriented normal value for a sub-cluster consisting of 29 random points in the first cluster and each additional point is greater than 0.8.

18. The system of claim 12 , wherein when identifying that the selected cluster of the one or more clusters is the circular shaped cluster, the processing logic is further configured to

determine that a centroid density value of a cluster centroid of the selected cluster is at least 11 times greater than the density value of a particular point in the selected cluster that is a maximum density value of the selected cluster.

19. The system of claim 12 , wherein the processing logic is further configured to:

determine a mean density value for the selected cluster;

compute a local centroid for a particular point in the selected cluster based on the position of the selected number of neighboring points of the particular point;

compute a distance between the particular point and the local centroid;

compute a distance between a cluster centroid and the local centroid; and

determining that the particular point is an inner edge point when d 1 +0.85*MD<d 2 ,

wherein d 1 is the distance between the particular point and the local centroid, MD is the mean density value, and d 2 is the distance between the cluster centroid and the local centroid.

20. A non-transitory electronic-device readable medium having instructions stored thereon, the instructions when executed by one or more electronic devices operable to:

receive a point cloud from at least one scanner of the one or more scanners, wherein the point cloud includes a plurality of points in space representing one or more eternal surfaces of at least one object in a scene, where each point in the point cloud has a position relative to the at least one scanner;

compute a density value for each point of the point cloud;

select a set of points, from the point cloud, determined to be high density points based on the density value determined for each point of the point cloud;

create one or more clusters from the set of points utilizing a principal component analysis algorithm;

identify a selected cluster of the one or more clusters as a circular shaped cluster;

identify a plurality of inner edge points of the selected cluster;

determine an ellipse that fits the plurality of inner edges points of the selected cluster; and

determine an estimated x coordinate, an estimated y coordinate, and an estimated z coordinate of the scanner utilizing a center of the ellipse and a non-linear least square solver with a threshold number of inner edge points with different density values.

21. The non-transitory electronic-device readable medium of claim 20 , wherein the selected number of neighboring points is 50 nearest neighboring points of the point.