In this post we’d like to comment on a paper we’ve found, which presents an interesting algorithm to detect sharp features in point clouds. We’re not sure if would be able to use it as it is presented due to performance issues (we will need a high-performance algorithm in order to work with the point cloud information provided by the Kinect camera, on the fly), but we may use some of its ideas.
Given a point cloud, the algorithm will analyze the neighborhood of each point to decide whether it belongs to a sharp feature or not. It uses the k-nearest points to build the neighborhood, from a kd-tree.
A first pre-processing step consists of building a kd-tree once, and store the result in a graph. In this graph, the minimum spanning tree connecting the point is expanded to connect each point with its k-nearest neighbors.
Given a point p, the local neighborhood Np contains its k-nearest points. We want to decide whether this point p belongs to a sharp feature or not. Feature detection is now performed in two steps.
The first step performs a flatness test in order to discard all points in a planar region. Let T be the set of all possible triangulations of p with its neighbors.
The normal vector of each triangle is calculated as follows:
If the lines passing through p and spanned by the normal are all almost parallel, then the underlying surface is nearly flat at p. To compare them, the angle between these lines is compared. If it is lower than a given threshold (e.g. 15%) the surface is assumed to be nearly flat, without having a sharp feature.
Then a more precise selection process is applied to the remaining candidate points: Gauss map clustering. The discrete Gauss map of the neighborhood of p can be defined as the mapping of T onto the unit sphere centered at p. We therefore use the clustering behavior of the projected points on the sphere.
A proper distance measure should be chosen, to decide how close two elements are. In this case, we have a spherical point set consisting of pairs of symmetric points, so the distance will be measured using the angle between the lines through the cluster.
We then use a “bottom-up” clustering method: it begins with each point as a separate cluster, and merges them successively into larger clusters. The distance between two clusters S1 and S2 is defined as follows:
The clusters are merged, until the distance between two clusters exceeds a certain threshold 
Clusters containing only a few points are discarded (considered noisy points). Opposite clusters on the sphere are considered as one. If in the end only one single cluster remains, the current point will be discarded since it does not belong to a feature. If two, three or four clusters remain, then the point belongs to a sharp feature. And if more than four clusters remain, the current point does not belong to a feature and is therefore discarded.
- Sharp feature with two clusters
There are some additional considerations regarding the parameters that are worth mentioning. The size of neighborhood should be determined considering that a too small neighborhood will not deliver reliable results, and on the otherside, a too big neighborhood may contain points of different regions. A threshold value should also be carefully chosen, since it would be the minimal distance between all resulting clusters.
mapinect 