### Finding a rectangle in a hay stack: identifying an object in a #PointCloud

Once a plane is located in a point cloud, some #VirtualReality / #AugmentedReality applications need to know the extent of the planar surface. Here I describe a method to determine the rectangular boundaries of the plane. The point cloud is assumed to be sufficiently dense and points on the plane appear as a relatively flat, rectangular block.

The steps are

1. Calculate the normal vector for a region of the space – see my post on fitting a plane in the point cloud space
2. Select the locations in the point cloud that lie near this plane through the space
3. Eliminate points that are not part of the rectangular block.
4. Align the axes of the points to the length and width of the rectangle
5. Determine the corner points and edges describing the rectangle
6. Rotate the corner points to their locations in the point cloud

The steps use multiple applications of principal components analysis (#PCA) to find the normal vector of the plane, eliminate outliers, and align the point cloud to find the corner points.

The following illustrates the method for a specific point cloud: a point cloud collected by a #ProjectTango tablet in a room containing a table with two booth-style benches along its length.

3d figure of original point cloud showing table (orange dot) between two booth-style seats

In this picture we want to determine the extent of the table. We first determine the plane containing the table top. To eliminate the background and other noise, only points from within 5 cm of the plane are selected.

­3d figure of the point cloud near the plane containing the table top

We next want to remove outliers from this reduced set of points. The points are analyzed using a PCA to align the length and width of the rectangle with the coordinates systems: the first two eigenvectors. First order differences are computed for the coordinates along the first eigenvector, x, and any gaps in the distribution are used to indicate clumps of outliers. Points outside the main distribution are eliminated from further analysis. The same procedure is used for the point coordinates along the second eigenvector, y. The following are the x and y coordinate histograms followed by the 3d plot showing the locations of the outliers.

x and y coordinate histograms showing gaps identifying outliers along eigenvector 2

3d figure of the point cloud with outliers in red

The outliers are removed and the remaining locations are then projected onto the plane.

3d plot of points (with outliers removed) mapped onto the plane

This flattened point cloud is subjected to a final PCA to align the first two eigenvectors with the length and width of the rectangle. Excluding the top and bottom 1 percent on each eigenvector, the range on each eigenvector determines the edges which in turn determine the corners.

plane in 2-d space with edges and corners identified

To locate the corners in the original point cloud space, we reverse the transformations to get the eigenvectors and add back the center point of the original space.

3d plot of original point cloud with the rectangle corners and edges in red

In summary, principal components analysis is used in several different ways: find the normal vector to a plane, align the axes with the rectangle for outlier elimination, and align the axes to determine the bounding edges of the rectangle. This method takes advantage of the linear transformations in PCA to move between the point cloud coordinates and the PCA coordinates. The method can be implemented as part of scene analysis/setup for #AR ./ #VR applications.