LASindex - simple spatial indexing of LiDAR data





The interactive transcript could not be loaded.


Rating is available when the video has been rented.
This feature is not available right now. Please try again later.
Published on Dec 8, 2012

Airborne LiDAR surveys collect large amounts of elevations samples, often resulting in Terabytes of data. The acquired LiDAR points are typically stored and distributed in the LAS format or - its lossless compressed twin - the LAZ format. However, managing a folder of LAS or LAZ files is not a trivial task when a survey consists, for example, of 500 flight strips containing around 200 million points each. Even a simple area-of-interest (AOI) query requires opening all files and loading all those whose bounding box overlaps the queried AOI. One solution is to copy the survey into a dedicated data base such as Oracle Spatial or PostgreSQL. We present a much simpler alternative that works directly on the original LAS or LAZ files.

To facilitate the exchange of data between users and across software packages, the ASPRS created the LAS format that is now the accepted industry standard for airborne LiDAR. To lower the storage requirements and reduce the transmission bandwidth for LAS files, we proposed the LAZ format - a lossless compressed twin of the LAS format - that is gaining traction in the industry as more and more data providers offer LAZ files (e.g. NOAA, National Land Survey of Finland, Open Topography, USGS, Dielmo3D, DNR Minnesota, ...) and more and more software has LAZ support (e.g. Global Mapper, TopoDOT, FME 2012, QT Modeler, RiProcess, Fugroviewer, ...).

However, the total size of all LAS or LAZ files from one survey still poses a significant challenge as billions of elevation samples need to be managed for processing and distribution. This problem is getting more pronounced as the resolution and converage of LiDAR surveys continues to increase.

A common solution is to create a second copy of the entire survey by loading it into a dedicated spatial data base such as Oracle Spatial or PostgreSQL. Once all the data was uploaded it can then be efficiently queried using established data base technology. But this approach has high start-up costs in terms of time, money, and disk space: the acquisition and installation time for a large software package, possible licensing delays and costs, the time needed to copy the entire survey into the database, and finally the additional disk space required for this second copy. While this initial investment may pay off over time, we describe a much simpler alternative that provides a different trade-off by working directly in-place on the original LAS or LAZ files.

Our minimal-effort spatial indexing scheme has very small setup costs, avoids creating a second copy of the data, and is already in use in the LAStools software suite (see Figure~\ref{fig:gui}). For each LiDAR file we generate a tiny LAX file that resides in the same folder as the *.las or *.laz file and has the same name but with a *.lax extension. The LAX files are generally as small as 0.01 percent (for a LAS file) or 0.1 percent (for a LAZ file) of the file containing the LiDAR data and they can be generated as fast as the points can be read off disk.

The LAX files describe an adaptive quadtree over the x and y coordinates of all points. Each occupied quadtree cell stores a list of point index intervals that together reference all points falling into this cell. By merging all intervals of a cell that are less than 1000 apart in point index space we significanly reduce the number of intervals, the size of the LAX files, and the number of file seek operations.

Although individual cells typically reference too many points this is usually amortized as a typical AOI query will require returning a union of all intervals from many quadtree cells. However, our in-place spatial indexing relies on a certain degree of spatial coherency to be present in the point order. A simple measure of the efficiency of the existing order is to calculate the overhead factor when loading each quadtree cell individually from disk.

The source code for LASindex is freely available under a LGPL license within the open source libraries LASlib of LAStools. It has been extensively field-tested in the LiDAR delivery pipeline of Open Topography (OT) where it is used to efficiently gather data from folders of LAZ files in accordance to area-of-interest queries that are generated by users via OT's popular web-based LiDAR download interface. Another important use is on-the-fly point buffering. When batch processing, for example, 2km by 2km LiDAR tiles to create DTMs via rasterization of a temporary TIN, it is beneficial to load a 100 meter point buffer around each tile to avoid tile boundary artifacts. The presence of LAX files allows doing so efficiently on-the-fly.


When autoplay is enabled, a suggested video will automatically play next.

Up next

to add this to Watch Later

Add to

Loading playlists...