SYSTEM AND METHOD FOR ORIENTATING SCAN CLOUD DATA RELATIVE TO BASE REFERENCE DATA

• US 20100164951A1
• Filed: 12/20/2007
• Published: 07/01/2010
• Est. Priority Date: 12/20/2006
• Status: Active Grant

• Current Assignee: Michael Paul Stewart
• Original Assignee: Michael Paul Stewart
• Inventors: STEWART, Michael Paul
• Granted Patent: US 9,625,253 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• CPC Class Codes: G01B 11/105 using photoelectric detection means
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/30136 Metal
• CPC Class Codes: G06T 7/75 involving models

Abstract

A system for orientating scan cloud data of a surface relative to base reference data is provided. The orientating system includes an input source generator adapted to provide the scan cloud data, a tilt-correction means for orientating the point cloud data relative to the base reference data, and a data editing means for filtering spurious point data from the accumulated point cloud data, wherein the base reference data represents at least geometrical parameters of a base reference, the base reference being substantially distinct from the target surface. A system for identifying features in scan could data of a surface is also provided. The identifying system includes an input source generator adapted to provide the scan cloud data, and a partitioning means for partitioning the point cloud data into discrete segments corresponding to different geometric sections of the surface.

Claims

1. A system for orientating scan cloud data of a target surface relative to base reference data comprising:

an input source generator adapted to provide the scan cloud data;

a tilt-correction means for orientating the point cloud data relative to the base reference data; and

a data editing means for filtering spurious point data from the accumulated point cloud data, wherein the base reference data represents at least geometrical parameters of a base reference, the base reference being substantially distinct from the target surface.

2. A system in accordance with claim 1, wherein the data editing means further includes partitioning means for partitioning the point cloud data into discrete segments corresponding to different geometrically described sections of the target surface.

3. A system in accordance with claim 1, wherein the data editing means is adapted to operate prior to the tilt-correction means.

4. A system in accordance with claim 2, wherein the data editing means includes at least one of a scanner structure filter, an intensity filter, and a range filter, wherein the scanner structure filter is configured to remove a first point attributable to a supporting means for at least one of situating stabilizing, and protecting the input source generator, wherein the intensity filter is configured to remove a second point in the accumulated point cloud data above a threshold intensity value, and wherein the range filter is configured to remove a third point that is one of less than a minimum and greater than a maximum threshold in the accumulated point cloud data.

5. A system in accordance with claim 4, where the base reference data includes a radius variable and a length variable, and wherein the range filter derives the threshold from the radius variable and the length variable.

6. A system in accordance with claim 4 wherein the tilt-correction means includes a point cloud data orientation means, wherein the point cloud data orientation means comprises:

a temporary point removal means for temporarily removing fourth point that is substantially longitudinally parallel with the first point that is removed by the scanner structure filter;

a rotation values means for calculating a rotation value to be applied to the scan cloud data;

a scan cloud data rotation process; and

a point restoration means whereby the fourth point removed by the temporary point removal means is restored to the accumulated point cloud data.

7. A system in accordance with claim 6, wherein the point cloud data orientation means includes a rotation value software utility comprising:

a translator process to translate the scan cloud data using a centroid reduction

${\left(\begin{array}{c}{x}^{\mathrm{\prime <br><br>}}\\ y^{\mathrm{\prime <br><br>}}\\ z^{\mathrm{\prime <br><br>}}\end{array}\right)}_i={\left(\begin{array}{c}x\\ y\\ z\end{array}\right)}_i-\left(\begin{array}{c}\stackrel{\_}{x}\\ \stackrel{\_}{y}\\ \stackrel{\_}{z}\end{array}\right)$ $\mathrm{where}<br><br>\left(\begin{array}{c}\stackrel{\_}{x}\\ \stackrel{\_}{y}\\ \stackrel{\_}{z}\end{array}\right)=\frac{1}{n}<br><br>\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>{\left(\begin{array}{c}x\\ y\\ z\end{array}\right)}_i;<br><br>$

and

a calculator process to determine a rotation value via eigenvalue decomposition of a covariance matrix of the scan cloud data Λ

=MCM^T where

$C=\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>{\left(\begin{array}{c}{x}^{\mathrm{\prime <br><br>}}\\ y^{\mathrm{\prime <br><br>}}\\ z^{\mathrm{\prime <br><br>}}\end{array}\right)}_i<br><br>{\left(\begin{array}{ccc}{x}^{\mathrm{\prime <br><br>}}& y^{\mathrm{\prime <br><br>}}& z^{\mathrm{\prime <br><br>}}\end{array}\right)}_i.$

8. A system in accordance with claim 7, wherein the rotation value software utility is adapted to rotate the accumulated scan cloud data, the rotation value software utility comprising:

a rotation process to rotate values so that x-longitudinal, y-transverse and z-height axes coincide

${\left(\begin{array}{c}{x}^{\mathrm{″<br><br>}}\\ y^{\mathrm{″<br><br>}}\\ z^{\mathrm{″<br><br>}}\end{array}\right)}_i={M<br><br>\left(\begin{array}{c}{x}^{\mathrm{\prime <br><br>}}\\ y^{\mathrm{\prime <br><br>}}\\ z^{\mathrm{\prime <br><br>}}\end{array}\right)}_i$

where M is a rotation value calculated by the rotation values means.

9. A system in accordance with claim 1, wherein the tilt-correction means includes a tilt-correction software utility for determining and correcting any residual tilt in the accumulated scan cloud data about an axis comprising:

an extractor process to extract a temporary set of points, p, within a set of constraints;

|x_i|<

t_x |y_i|<

t_y z_i>

t_z;

a subtracter process to subtract a mean x co-ordinate from the temporary set of points;

$x_i^{\mathrm{\prime <br><br>}}=x_i-\stackrel{\_}{x}<br><br><br><br>\mathrm{where}<br><br><br><br>\stackrel{\_}{x}=\frac{1}{p}<br><br>\underset{i=1}{\overset{p}{\sum <br><br>}}<br><br>x_i;<br><br>$

forming the following 2D line equation for each point in the resulting temporary set of points;

z_i=mx_i′

+b;

a least-squares calculator to calculate the least-squares estimate of the slope, m, as;

$m=\frac{\underset{i=1}{\overset{p}{\sum <br><br>}}<br><br>z_i<br><br>x_i^{\mathrm{\prime <br><br>}}}{\underset{i=1}{\overset{p}{\sum <br><br>}}<br><br>{\left(x_i^{\mathrm{\prime <br><br>}}\right)}^2};<br><br>$

a rotate angle calculator process to calculate a rotation angle φ

as;

φ

=arctan(m); and

an accumulated scan point rotator process to rotate the accumulated scan point data;

${\left(\begin{array}{c}{x}^{\mathrm{\prime <br><br>}}\\ y^{\mathrm{\prime <br><br>}}\\ z^{\mathrm{\prime <br><br>}}\end{array}\right)}_i=R_2<br><br>\left(\mathrm{\varphi <br><br>}\right)<br><br>{\left(\begin{array}{c}x\\ y\\ z\end{array}\right)}_i<br><br><br><br>\mathrm{where}<br><br><br><br>R_2<br><br>\left(\mathrm{\varphi <br><br>}\right)=\left(\begin{array}{ccc}\cos <br><br><br><br>\mathrm{\varphi <br><br>}& 0& -\sin <br><br><br><br>\mathrm{\varphi <br><br>}\\ 0& 1& 0\\ \sin <br><br><br><br>\mathrm{\varphi <br><br>}& 0& \cos <br><br><br><br>\mathrm{\varphi <br><br>}\end{array}\right).$

10. A system in accordance with claim 2, wherein the partitioning means includes at least one of an opposing-end segmentation means, a floating-object segmentation means for segmenting points in the accumulated point cloud data attributable to objects that are non-fixably connected to the target surface, and a belly segmentation means for segmenting points in the accumulated point cloud data attributable to a cylindrical shell, wherein the opposing-end segmentation means includes at least one of a planar-end segmentation means for segmenting points in the accumulated point cloud data when the base reference data denotes a substantially planar end and a conical-end segmentation means for segmenting points in the accumulated point cloud data when the base reference data denotes a substantially conical end.

11. A system in accordance with claim 10, wherein the at least one of the planar-end segmentation means and the conical-end segmentation means includes an end segmentation software utility comprising:

a frequency calculator process to calculate a frequency of each longitudinal coordinate within the accumulated point cloud data;

a greatest frequency calculator process to determine a greatest positive frequency and a greatest negative frequency of the frequency calculator process;

a threshold addition process to add a threshold value to the greatest negative frequency and the greatest positive frequency; and

whereby the conical-end segmentation means further comprises;

a minima locations calculator process to scan the longitudinal co-ordinate frequencies to determine a minima location from the greatest negative and positive frequencies as towards the location of the input source generator;

a segmentation process to segment the points in the accumulated point cloud data attributable to the planar ends according to the minima location; and

whereby the conical-end segmentation means uses the greatest negative and positive frequencies of the minima locations calculator process to segment the points in the accumulated point cloud data attributable to the conical end.

12. A system in accordance with claim 1, further including a non-fixably connected volume measurement means for measuring the volume of objects that are non-fixably connected to the target surface.

13. A system in accordance with claim 1, further including a hole measurement means for measuring the size of apertures in the target surface.

14. A system in accordance with claim 12, wherein the non-fixably connected volume measurement means further comprises a ball-ore discrimination means for measuring a ratio of a set of balls to non-ball materials.

15. A system in accordance with claim 12, wherein the non-fixably connected volume measurement means further comprises a ball size measurements means for measuring a size of a set of balls within a cylindrical shell.

16. A system in accordance with claim 10, wherein the floating-object segmentation means includes a floating-object software utility that operates after the opposing-end segmentation means has been effected on the scan cloud data, the floating-object software utility comprising:

a radius frequency calculator process to calculate a frequency of each cylindrical radius value in accumulated scan cloud data;

a peak value determinative process to determine a peak value of the radius frequency calculator process and segmenting points based on the peak value;

a segmentation fitting process to fit the segmented points to a plane by eigenvalue-based decomposition;

a scan cloud translation process to translate scan cloud data of m points to a centroid

${\left(\begin{array}{c}{x}^{\mathrm{\prime <br><br>}}\\ y^{\mathrm{\prime <br><br>}}\\ z^{\mathrm{\prime <br><br>}}\end{array}\right)}_i={\left(\begin{array}{c}x\\ y\\ z\end{array}\right)}_i-\left(\begin{array}{c}\stackrel{\_}{x}\\ \stackrel{\_}{y}\\ \stackrel{\_}{z}\end{array}\right)<br><br><br><br>\mathrm{where}<br><br><br><br>\left(\begin{array}{c}\stackrel{\_}{x}\\ \stackrel{\_}{y}\\ \stackrel{\_}{z}\end{array}\right)=\frac{1}{n}<br><br>\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>{\left(\begin{array}{c}x\\ y\\ z\end{array}\right)}_i;<br><br>$

an eigenvalue decomposition process to determine an eigenvalue decomposition of a covariance matrix Λ

=MCM^T where

$C=\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>{\left(\begin{array}{c}{x}^{\mathrm{\prime <br><br>}}\\ y^{\mathrm{\prime <br><br>}}\\ z^{\mathrm{\prime <br><br>}}\end{array}\right)}_i<br><br>{\left(\begin{array}{ccc}{x}^{\mathrm{\prime <br><br>}}& y^{\mathrm{\prime <br><br>}}& z^{\mathrm{\prime <br><br>}}\end{array}\right)}_i;<br><br>$

a plane model is given by ax+by+cz−

d=0 where (a, b, c) are elements of an eigenvector corresponding to a smallest eigenvalue, and

$d=\left(a<br><br><br><br>b<br><br><br><br>c\right)<br><br>\left(\begin{array}{c}\stackrel{\_}{x}\\ \stackrel{\_}{y}\\ \stackrel{\_}{z}\end{array}\right);<br><br><br><br>$

a residual deviation calculation process to calculate a residual deviation, v, from a best-fit plane for each point;

ax_i+by_i+cz_i−

d=v_i; and

a points discardal process to discard a point above the plane based on the residual deviation.

17. A system in accordance with claim 10, wherein the belly segmentation means includes a belly segmentation software utility, comprising:

a centroid refiner process to refine a centroid of point cloud on the longitudinal axis by calculating a mean value at an end of said substantially cylindrical shell using an equal number of points

${\stackrel{\_}{x}}_L=\frac{1}{p^{-}}<br><br>\underset{i=1}{\overset{p^{-}}{\sum <br><br>}}<br><br>x_i^{-}$

such that

$\frac{p^{-}}{n}\ge <br><br>t_p<br><br><br><br>\mathrm{and}<br><br><br><br>{\stackrel{\_}{x}}_R=\frac{1}{p^{+}}<br><br>\underset{i=1}{\overset{p^{+}}{\sum <br><br>}}<br><br>x_i^{+}$

such that

$\frac{p^{+}}{n}-\frac{p^{-}}{n}\le <br><br>t$

where ⁻

and ⁺ refer to points from left and right ends of a belly liner point cloud, respectively;

a scan cloud translation process to translate the scan cloud data by a mean of these two means

$x_i^{\mathrm{\prime <br><br>}}=x_i-\stackrel{\_}{x}<br><br><br><br>\mathrm{where}<br><br><br><br>\stackrel{\_}{x}=\frac{{\stackrel{\_}{x}}_L+{\stackrel{\_}{x}}_R}{2};<br><br>$

a circle definition process to define a circle at each end of the substantially cylindrical shell, the circle being a circle of intersection of cylindrical belly surface of said base reference data and at least one of a conical and a planar end surface of base reference data;

a cone definition process to define a cone with the circle as the base and apex on the belly side of the circle having half-apex angle of 45°

; and

a point assignment process to assign each point within the cone to a given end of said substantially cylindrical shell and to assign each point outside of the code to the cylindrical shell.

18. A system in accordance with claim 10, wherein the belly segmentation means comprises a cylinder-fit process, wherein the cylinder-fit process includes a cylinder-fit software utility that operates after the opposing-end segmentation means and the floating-object segmentation means have been effected on the scan cloud data, the cylinder-fit software utility comprises:

an equation forming process to form the following equation for each point in an accumulated scan cloud data ∥

( p_i−

q)×

n∥

−

r=0 where an observation point vector is given by p_i=(x_i y_i z_i)^T, a cylinder position vector is given by q=(0 y_c z_c)^T and a cylinder axis vector is given by n=(a b c)^T;

a weighted constraint addition process to add a weighted constraint a²+b²+c²−

1=0 and solving in parametric least squares;

a cylinder position translation process to translate the entire scan point cloud by the cylinder position vector

${\left(\begin{array}{c}{x}^{\mathrm{\prime <br><br>}}\\ y^{\mathrm{\prime <br><br>}}\\ z^{\mathrm{\prime <br><br>}}\end{array}\right)}_i={\left(\begin{array}{c}x\\ y\\ z\end{array}\right)}_i-\left(\begin{array}{c}0\\ y_c\\ z_c\end{array}\right);<br><br><br><br>$

a rotation value calculator process to calculate rotation angles, φ and

κ

, where

$\mathrm{\varphi <br><br>}=\arctan <br><br>\left(\frac{c}{a}\right)<br><br><br><br>\mathrm{and}<br><br><br><br>\mathrm{\kappa <br><br>}=\arctan <br><br>\left(\frac{-b}{a}\right);<br><br>$

and

a scan cloud transformation process to transform the point cloud

${\left(\begin{array}{c}{x}^{\mathrm{″<br><br>}}\\ y^{\mathrm{″<br><br>}}\\ z^{\mathrm{″<br><br>}}\end{array}\right)}_i={M^T<br><br>\left(\begin{array}{c}{x}^{\mathrm{\prime <br><br>}}\\ y^{\mathrm{\prime <br><br>}}\\ z^{\mathrm{\prime <br><br>}}\end{array}\right)}_i$

where M=R₃(κ

)R₂ (φ

).

26. A system in accordance with claim 1, wherein the base reference data comprises key reference data to describe the geometry of the base reference.

27. A system in accordance with claim 1, wherein the target surface and the base reference are referenced to its own respective co-ordinate system.

28. A system in accordance with claim 1, wherein the base reference represents a contained space.

29. A system in accordance with claim 28, wherein the contained space is bounded by a substantially cylindrical shell with opposing ends.

30. A system in accordance with claim 29, wherein the base reference further comprises parameters defining a location of a central longitudinal axis of the shell, a radius of the shell, and a length of a cylindrical portion of the shell.

19. A system for identifying features in scan cloud data of a target surface comprising:

an input source generator adapted to provide the scan cloud data; and

a partitioning means for partitioning the point cloud data into discrete segments corresponding to different geometric sections of the target surface.

20. A system in accordance with claim 19, further including a non-fixably connected volume measurement means for measuring a volume of objects that are non-fixably connected to the target surface.

21. A system in accordance with claim 19, further including a hole measurement means for measuring a size of an aperture in the target surface.

22. A system in accordance with claim 20, wherein said non-fixably connected volume measurement means further comprises a ball-ore discrimination means for measuring a ratio of a set of balls to non-ball materials.

23. A system in accordance with claim 20, wherein the non-fixably connected volume measurement means further comprises a ball size measurements means for measuring a size of a set of balls within a cylindrical shell.

24. A method for orientating scan cloud data of a target surface relative to base reference data, said method comprising:

providing the scan cloud data;

orientating the scan cloud data relative to the base reference data; and

filtering spurious point data from the accumulated point cloud data.

25. A method for identifying features in scan cloud data of a target surface, said method comprising.

providing the scan cloud data;

and

partitioning the point cloud data into discrete segments corresponding to different geometric sections of the target surface.