What’s the point?! Point characterization explained

In order to find some geometric sense in the point cloud, one of the most basic procedures is to characterize each point in the point cloud. By analyzing a point in reference to its neighbors we can learn to which surface does it belong, and what’s the surface orientation, etc.

Most of point cloud analysis starts with point characterization. A lot of questions arise when we inspect a single point: does it belong to a larger surface or is it noise? Is it the ground? Is it an object? Is it an edge? Many of these questions may be answered by characterizing the underlying geometry of the point. Of course, unless they are noise, no point stands alone. That’s why – we have to start with looking at its neighbors.

The Neighbors

The points in the point cloud do not mean much on their own. We have to look at them within a context. Therefore, the first thing that we do is to find all the neighbors of the point. This has to be carried out for every point in the point cloud. Since the point cloud is not an organized grid, this phase is not straight forward.

To find neighbours we usually begin with structuring the data. This way, it will be easy to access all neighbours for each point in the point cloud when we need it. Think of it as arranging your closet. In order to find your clothes fast, you have to arrange them according to a predefined scheme. You can gather all the pants on one shelf, regardless of the season, or you can collect all summer clothes in that shelf. The space on the shelf that you use may change according to the amount of clothes on them, or it can be unified. It all depends on how you choose to structure.

The same goes for the point cloud. We first need to arrange the points in cells and then find the neighbors, and there are many ways to do it: equal-sized grid (voxels), box-in-a-box (kd-tree), sphere-in-a-sphere (ball-tree), you name it! Pay attention though, it’s not that we are changing the position of the points, we just organize the connection between them so we can reach them easily.

Once the structure is ready, we can search for neighbors. Depending on the structure, the search is carried out by distance (rnn), by looking for the closest neighbors (knn), or by looking at the neighboring cells. The structure, as well as the searching method, defines which neighbors you will access. Therefore, there will be some variations between the different structures/searches and the answer to “who are this point’s neighbors?” is not unique.

The surface

Once we have the neighbors of our point, we can define to which surface it belongs to. We can fit multiple types of surfaces: for example, we can assume the underlying surface is a plane, and then look for the best fitted plane. We can assume it is a part of a sphere, and find out which sphere fits our points the best. We can also assume other planes, like bi-linear, Bi-quadratic, etc. This surface shouldn’t fit all our points, just a local area.

After deciding which type of surface will fit best to our point and its neighbors, we can characterize it and learn more about it.

The normal

The direction a point is defined by the normal direction to the surface at the analyzed point. That is to say, the perpendicular direction to the fitted surface at that point.

The normal direction is in fact the orientation of the (local) surface that the point lies upon. Therefore, we can use it as a clue to define which object the point belongs to (e.g., a roof, a wall). By knowing this, we can also use for visualization purposes (lighting and shading, for example). The collection of the normals in a neighborhood can even add: is it a salient point, does the point belong to vegetation, etc.

There are many ways to compute the normal, not necessarily through modelling the entire scene. Here you can find an example for such a computation.

The curvature

The curvature of a point is another derivative of the fitted surface. It tells us how “fast” the surface is changing its direction. The problem is, that because we are looking at a 3D surface, it really depends in which direction we are going – some directions will be faster and some slower. In fact, there are many types of curvatures: principal, mean, Gaussian, etc.

Because of the numerous types, and the complexity of computation, especially in point clouds, there are currently, no specific ways to compute the curvature. In one of our studies we proposed a simple computation of “convexity”, which we used as a measure for curvature.

The role of point characterization in point cloud analysis

Point characteristics imply on which surface the point was measured, and therefore can tell us to which object it belongs. This way, we can automate point cloud processing and use it for segmentation, object detection, visualization, etc.

There is still a lot to study in this regard. Which curvature describes our points the best and how to compute it, what type and size of neighborhood do we take, and how much does it affect our subsequent analysis, how can we accelerate this characterization, and so forth.

It goes without saying that not only that characterizing the point is still being researched, researchers also focus on how to exploit these characteristics in their analysis of the acquired point cloud.

---