Using Principal Components Analysis to determine the best fitting plane from locations in a #PointCloud

20150929_113635[1]

3-d scanners determine locations of points on surfaces thereby creating a point cloud in 3 dimensional space. This point cloud is used to determine the surface of objects scanned with the total set determining a mesh that can be printed or used in #VirtualReality / #AugmentedReality applications.

Some applications such as shooter games need to know the orientation of a surface from locations in the point cloud. One method uses the three closest points to the line-of-sight. This method is easy to program, but estimate is highly sensitive to errors in location and distance estimation. Here I propose a more robust method that reduces the sensitivity to errors by the sensors by incorporating additional points in the neighborhood of the line-of-sight. I will describe the computation of the three-point method and then introduce the multi-point method.

The three-point method

The normal vector characterizes the plane and points in a direction perpendicular to the plane. From three points P0 = <x0,y0,z0> , P1 = <x1,y1,z1>,and P2 = <x2,y2,z2>, two vectors, V1 = P1 – P0 and V2 =P2 – P0 can be created and any point on the plane is the weighted sum of these two vectors.

\left[ \begin{matrix}\alpha_1 V_1x + \alpha_2 V_2x \\ \alpha_1 V_1y + \alpha_2 V_2y \\ \alpha_1 V_1z + \alpha_2 V_2z\end{matrix} \right] = \left[ \begin{matrix} x \\ y \\ z\end{matrix} \right]

We can write the solution to these equations as the determinant whose solutions is the normal vector and is equivalent to taking the cross product of the vectors:

\left| \begin{matrix} x & y & z \\ V_1x & V_1y & V_1z \\ V_2x & V_2y & V_2z \end{matrix} \right| = 0

Which can be written

 \left\langle A,B,C \right\rangle = \left\langle V_1y V_2z - V_1z V_2y, V_1z V_2x - V_1x V_2z, V_1x V_2y - V_1y V_2x \right\rangle

Alternatively, the plane can be specified by the equality in x, y, and z:

 A ( x - x_0 ) + B ( y - y_0 ) + C ( z - z_0 ) = 0

Or

 A x + B y + C z = D

Where

 D=Ax_0+By_0+Cz_0

threepontplant
3 points on the plane they define

The one additional consideration is that if there is a point-of-view (a.k.a. camera), then the normal vector should face toward it, rather than away from it. The normal vector is perpendicular to all vectors on the plane, but its sign is indeterminate. We know that the angle between two vectors, V0 and V1 is:

 \cos\theta = \frac{ V_0 * V_1} { \left\| V_0 \right\| \left\| V_1 \right\| }

The vectors point in the same direction if q  in the interval {-π/2, π/2}. This is occurs when that the dot product of V0 and V1 is greater than zero. Denoting, K is the location of the camera, we compute the dot product of K – P0 and the normal vector to determine if they are both facing the same general direction. If the dot product of these two vectors is greater than zero, the normal vector is already pointing in the direction of the camera. If the dot product is negative, then multiply the normal vector by -1 to reverse its direction so it points toward the camera.

More than three points

Four or more points may or may not share a common plane, so a best fit solution is needed. I use a method that locates a plane through the space that minimizes the sum of the squared distances of all points from the plane surface. Principal components analysis (PCA) is applied to the selected locations in the point cloud and the first two eigenvectors define the plane.

First, a 3 x 3 covariance matrix is computed for the n x 3 matrix of coordinates from the point cloud where n is the number of points to be fit. Next, the covariance matrix is decomposed into its eigenvectors and eigenvalues using PCA. The two eigenvectors with the largest eigenvalues are selected and the cross product of these two eigenvectors is the normal vector.

pcaplane
10 additional points and the plane they define (3 original points connected by red lines)

In this 3-dimensional case, PCA computes directions through the space that maximize the explained variance as expressed by the eigenvalues. Since the total variance in the space spanned by the n x 3 matrix is fixed, the two eigenvectors, with the largest eigenvalues, minimize the variance explained by the third eigenvector. This is equivalent to finding a plane that minimizes the sum of the squared distances (the green lines in the graph) of points in the point cloud from the plane.

If n=3, the #PCA solution and the three-point solution are the same.

Bartlett’s test is a way to determine if the components are significant and if a plane is a sufficiently good approximation of the space.

The method is computationally fast enough to compute planes within interfering with the display #ProjectTango refresh rate. The computation consists of a step to convert the n x 3 matrix to a 3 x 3 matrix followed by a limited number of matrix multiplications on the 3 x 3 matrix.

Advertisements
Comments
One Response to “Using Principal Components Analysis to determine the best fitting plane from locations in a #PointCloud”
Trackbacks
Check out what others are saying...
  1. […] Calculate the normal vector for a region of the space – see my post on fitting a plane in the point cloud space […]



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: