Project "3D point cloud classification"

The project names '3D point cloud classification'. I'm excited about 3D point cloud, and I thought the project should have something to do with the real-time 3D reconstruction...

The main purpose of this project is to help robotics and automated vehicles to recognize where is road and where they cannot go. The project itself is very practical, however it has a lot to do with mathematics -_-. From a software engineer point of view, this kind of project should have some kind of API exists. And, yes! We are going to use it without dive deep into the algorithm~!

However, theories and algorithms are part of the reason why I chose CS instead of SE as the graduate major. ^_^ Therefore, complains are allowed, but evasion is prohibited!

頑張ろ！

Now back to the algorithm...


We all know that 3D cameras and LIDAR sensors can only generate 3D point clouds. Point clouds cannot be used until classification or reconstruction. Reconstruction is a series of processes to convert the point cloud into 3D objects and models. Classification is light-weight compared to reconstruction. We only need to specify the type of objects formed by some points. In other words, we only need to recognize if there's a valid path (or plane) for robotics to pass.


To do the job, we need several steps:
1. For each point in the cloud, find all neighbors within a specific range.

2. Compute the weight point of those neighbors. Say the weight point is x-bar, we found N neighbor points and Xi is the matrix [x,y,z] contains dimensional information of the original point. The computation of x-bar is 1/N*Sum(Xi).

3. Compute the covariance matrix using the value of x-bar. The formula to compute the matrix S is 1/N*Sum((Xi-x_bar)(Xi-x_bar)T). The matrix is a 3X3 symmetric positive definite matrix.

4. We need to decompose the matrix and get the eigenvalues λ0, λ1 and λ2.

5. Say v0, v1 and v2 are the eigenvectors corresponding to eigenvalues λ1, λ2 and λ3 respectively.  We build a support plane using v0, v1 and x_bar. Vector v2 is the normal of that plane and x_bar is the center of the plane.

6. We now compare the three eigenvalues. If λ0≈ λ1≈ λ2, it means those points are scattered in the space. If λ0>> λ1, λ2, it means those points spread in a linear pattern, for example in a cylinder. If λ0≈ λ1>> λ2, those points are likely to be on a surface.
 
So~ First of all, I need to figure out the CPU version of the code, which means the code must first work. And then, I'll try to port it to グラフィックカード and see if we can increase the performance.