LASzip: lossless compression of LiDAR data

1 laszip : lossless compression of LiDAR dataMartin Airborne laser scanning technology ( LiDAR ) makesit easy to collect large amounts of point data that sample theelevation of the terrain beneath. The LAS format has become thede facto standard for storing and distributing the acquired the sampling density of LiDAR increases so does the size ofthe resulting files. Typical LAS files contain tens to hundreds ofmillions points today, but soon billions will be describe a completely lossless compression scheme forLiDAR in binary LAS format versions to Our encodingand decoding speeds are around one to three millions points persecond and our compressed files are only 7 to 25 percent of theoriginal file size. compression and decompression happen on-the-fly in a streaming manner and random-access is supported with adefault granularity of 50,000 points. A reference implementationunencumbered by patents or intellectual property concerns isfreely available with an LGPL-license, making the proposedcompression scheme suitable to become part of the LAS INTRODUCTIONLow flying aircrafts equipped with modern laser-range scan-ning technology ( LiDAR ) collect precise elevation informationfor entire cities, counties, or even states.

2 Shooting 100,000 ormore laser pulses per second onto the earth s surface theytake measurements at resolutions exceeding one point persquare meter. Derivatives of this data such as digital elevationmaps are subsequently used in numerous applications: toassess flood hazards, plan solar and wind installations, carryout forest inventories, aid in power grid maintenance, , the sheer amount of LiDAR data collected posesa significant challenge as not millions but billions of elevationsamples need to be stored, processed, and scanner records the waveform of the returning reflectionfor each laser pulse that it sends out. The intensity peaks ofthis waveform correspond to points that were hit by the laserand that reflected significant portions back to the sensors onthe plane. There can be multiple peaks because the laser mayhit several surfaces such as wires or antennas, branches, leaves,or even birds in flight before reaching the ground. Each peakabove a certain threshold is called a return.

3 The coordinatesof these returns together with intensity, scan angle, GPS time,return number, flight line ID, etc. are the data of off the scanner, the LiDAR data is typically storedin a binary, vendor-specific format. But to exchange the databetween users and across different software packages it wastraditionally converted into a simple ASCII representationwhere each line was listing the attributes of a single flexible and easy to understand, storing millions (or nowbillions) of LiDAR returns in a textual format is cumbersome:the file size grows large, parsing the data is inefficient, and it isnot possible to seek within the file. Addressing these concernsthe ASPRS created a simple binary exchange format - the LASformat [1]. It is now the de facto industry standard for storageand distribution of airborne and mobile LiDAR to LAS , each point record has a core 20 bytes ofwhich 12 bytes store thex,y, andzcoordinate as signedintegers. The header of a LAS file contains scaling factorsfor those integers that specify the precision ( such for cm and for mm).

4 The other 8 bytes storeintensity, scan angle, return count, classifications, etc. Thiscompletes the basic point type0(for details see Table I). Thepoint types1and3add an 8 byte GPS time and the pointtypes2and3provide 6 bytes to store an RGB color. TheLAS specification introduced the point types4and5thatallow attaching full waveform information to each return (withcontroversial design choices) but they are not used of the great features of the LAS format is that it storesthe coordinates as scaled and offset integers thereby requir-ing the producers to think about the actual precision in theirscanned data samples and to choose appropriate incrementssuch as meters (or feet) for storing the coordinates. Thiseliminates the unnecessary if not disastrous bloat of double-precision floats or 20 digit ASCII representations where 15of the 20 digits are really just scanner noise. The absence ofincompressible noise makes it possible to efficiently compressthe LiDAR points in a completely lossless compression schemes are not well suited to com-press LiDAR because they do not have the insights into thestructure of the data to properly model the probabilities ofcertain patterns to occur.

5 The WinZIP compressor does notcompress well while the WinRAR compressor is extremelyslow. Neither scheme is suited for streaming or for random-access decompression, which means the entire file needs to bedecompressed before its contents can be this paper we introduce laszip , a lossless compressor forLiDAR stored in the LAS format. It delivers high compressionrates at unmatched speeds and supports streaming, random-access decompression. The source code is available withLGPL-license and was integrated into the open source librariesLASlib of lastools [2] and libLAS [3]. There is nativesupport for reading and writing LAZ in FME 2012, TopoDOT,VoyagerGIS, and lastools and others are following. LAZ isused internally at USACE, Certainty3D, Watershed Sciences,Riegl, and others. data providers such as Open Topographyprovide LAZ as an compressed download option [4] and theDNR of Minnesota hosts LiDAR for 40 counties exclusivelyin LAZ format with plans to complete the entire state [5].

6 II. BACKGROUNDB efore describing the laszip compressor some preliminar-ies about coordinate precision, the LAS format, related workin point compression , and entropy and difference Floating-Point Precision vs. Integer PrecisionThere is a common miss-conception that floating-point rep-resentations provide more precision than integer presentationsfor storing thex,y,zcoordinates of a point. They do coordinates of LiDAR points from an airborne or amobile survey are spread out in thex-yplane with uniformdistribution, in the sense that there are roughly the samenumber of points per square meter everywhere and that thepoints are acquired with roughly the same precision. Therewill not be one particularly dense area where points need tobe stored with higher precision. The floating-point format isnot designed for storing uniform distributions of a number in floating-point representation means thatthe precision of the number will vary depending on the value ofthat number. The closer it gets to zero the more precision it willhave.

7 This makes it a good format, for example, for numericalcomputations where more precision is needed closer to using the floating-point format to store point coordinatesmeans that there is an increasingly precise spacing of datasamples around one point the origin at the expense of anincreasingly imprecise spacing farther example: in single-precision floating-point there are223different numbers to represent a coordinate between 2 and4 meters with a spacing of2/223= ,there are223different numbers to represent a coordinatebetween 128 and 256 meters with a spacing of128/223= , there are223different numbers to representa coordinate between524,288and1,048,576meters witha spacing of524,288/223= , and of coursethere are also223different numbers to represent a coordinatebetween2,097,152and4,194,304me ters with a spacing of4,194,304/223= If you notice the pattern youalready know that there will also be223different numbersto represent a coordinate between4,194,304and8,388,608meters with a spacing of4,194,304/223= summary, if you store the easting and northing of yourcoordinates directly in floating-point they may retain of precision.

8 If you subtract a constant offset from yourcoordinates so the origin falls into the middle of the boundingbox, then the samples near the origin are stored with incredibleprecision .. much much more than LiDAR appropriate format for storing the coordinates of LiDARpoints are properly scaled and offset integers. They offermuch moreuniformprecision than a corresponding floating-point value for the same number of bits: a 32 bit integer,for example, offers 7 bits more uniform precision than a 32bit floating-point number [6] and similarly a 64 bit integeroffers 10 bits more than a 64 bit float. In order to increase thecoordinate range for a large-scale LiDAR collect, the correctthing to do is to move from 32 bit to 64 bit integers. The LASformat [1] uses scaled and offset 32 bit of atomic itemsizepoint type and size012345point attributesformatsize20 28 26 34 57 63 POINT1020 bytesxxxxxxXint4 bytesxxxxxxYint4 bytesxxxxxxZint4 bytesxxxxxxIntensityushort 2 bytesxxxxxxReturn Number3 bits 3 bitsxxxxxxNumber of Returns of Pulse3 bits 3 bitsxxxxxxScan Direction Flag1 bit 1 bitxxxxxxEdge of Flight Line1 bit 1 bitxxxxxxClassificationuchar 1 bytexxxxxxScan Angle Rankuchar 1 bytexxxxxxUser Datauchar 1 bytexxxxxxPoint Source IDushort 2 bytesxxxxxxGPSTIME108 bytesx xxxGPS Timedouble 8 bytesx xxxRGB126 bytesxx xRedushort 2 bytesxx xGreenushort 2 bytesxx xBlueushort 2 bytesxx xWAVEPACKET1329 bytesxxWave Packet Descriptor Index uchar 1 bytexxBytes Offset to Waveform data uint64 8 bytesxxWaveform Packet Size in Bytes uint 4 bytesxxReturn Point Waveform Location float 4 bytesxxX(t)float 4 bytesxxY(t)float 4 bytesxxZ(t)

9 Float 4 bytesxxTABLE ILASZIP GROUPS THE ATTRIBUTES OF THE POINT TYPES0TO5OF THELAS INTO FOUR ATOMIC ITEMS: POINT10, GPS10, RGB12,ANDWAVEPACKET13 THAT ARE THEN COMPRESSED The LAS formatTo facilitate the exchange of LiDAR data between datavendors, users, and different software packages, the ASPRS created LAS as a simple binary exchange format [1]. A LASfile of the - family consists of a header that can befollowed by any number of variable length records before theactual point data begins. The first 227 header bytes define thecontent of a LAS file: the number of variable length records,the offset to the start of the points, the type and size of eachpoint, the number of points, the offsets and scale factors for theinteger point coordinates, and a bounding box that describesthe extends inx,y, andzof all points in the LAS , where each point can have an attached wave-form, there are 235 header bytes. The extra 8 bytes describe thestart of the waveform data . If this field is zero the waveformsare stored in an external WDP file.

10 If this field is non-zerothe waveforms are stored inside the LAS file after the pointblock and the field contains the offset to the start of thewaveform data . laszip does not (yet) support including thewaveform data inside the LAZ file but always writes it toan external WDP file instead at the moment is, however, an (undocumented) option in place that willcompress the waveforms to a more compact WDZ waveform LiDAR data in LAS format is currentlyonly produced by one vendor. Apparently, the mechanism forwaveform storage was quickly added to the LAS standardto meet the needs of one hardware vendor without seekingmutual consensus among all scanner manufacturers first. Thereis almost no publicly available waveform data stored in theLAS format and there are only a few software products thatcan make use of the waveform data in LAS files. Thereforewe postpone the details for full waveform compression forLAS until it becomes more point types 0 to 5 available in LAS and theattributes they are composed of are detailed in Table I.