Processing Lidar with MPI - Liblas + MPICH2

I did some work in the last company for processing and reclassifying Lidar points using Liblas. The first Python implementation had lots of point-in-polygon queries and even with prepared geometries in GEOS took a few hours. We improved the execution of this by rasterizing the polygons, while polygons in theory have arbitrary precision and rasters are limited to the spacing they are gridded at, in this case the polygons were derived by classifying a rasterized version of the Lidar and the raster mask should have the same degree of precision.

The mask is overly generous in classes at times, considering each class as a local surface. A piecewise interpolation model can often be used to identify disparate points in context and perform class switching. In unordered Lidar data this may lead to many passes through the data generating neighbourhood class relationships if an index has not been built e.g. Octree.

I decided to adopt the Google philosophy of scale solves everything - and implemented the Lidar processing using MPI (Specifically MPICH2). The solution is implemented with task queues.

1. Read all data on all nodes except last
2. Node 0 makes a pass through all data sending each point in round robin to intermediate nodes
3. Intermediate nodes receive a point and make another pass through all data identifying nearby points and using them in an IDW2 estimate
4. Intermediate nodes message with IDW2 estimate to last node in the set (in charge of serializing) which makes various comparisons against classification masks (e.g. SRTM Water Boundary mask) and geo-statistical surface consistency before reclassifying and serializing to an output LAS file.

The task is essentially O(n^2) but with sufficient nodes we can bring it down to O(n*n/M+M*overheads) where M is the number of nodes. If the dataset is large enough and M is suitably chosen we gain significant speed increases. I got so carried away with Lidar + MPI ( and since I don't want to mix it with my PhD stuff) I started a small code dump on Google Code. Use CMake and see if you can build it. Lots of sample Lidar here.