Model-based scan line encoder

A model-based scan line encoder is disclosed. A method of model-based scan line encoding includes defining a geometry model for describing a scan line of a scan, the scan line including multiple scan points. The method further includes calculating a trajectory model representing an approximate pattern of deviation of the multiple scan points relative to the geometry model. The method further includes calculating multiple residuals, each of the residuals associated with a difference between the deviation of the scan points and the trajectory model. The method may further include compressing the residuals.

BACKGROUND

Field

The embodiments disclosed herein relate to compression and retrieval of three-dimensional (3-D) laser scan data.

Relevant Technology

Scanning devices for capturing 3-D reality using laser imaging, detection, and ranging (LIDAR) techniques such as those described in U.S. Pat. No. 7,701,558 and U.S. Pat. No. 5,988,862 have been growing in popularity and usage. Generally, the laser scanners may include some form of LIDAR that generates one or more range samples of one or more target surfaces. The LIDAR may also generate ancillary data associated with the samples, such as a measure of the return intensity of the laser, described as “active color” and/or the color of the sampled surface described as “passive color.” Intensity may refer to the light returned from the surface from the laser, which may include several distinct wavelengths. Color may refer to light passively returned from a surface, which may be composed of one or more distinct bands of interest as with hyper spectral and/or thermal imaging.

The LIDAR may be mechanically positioned by the laser scanner to sample a region of interest over time. The mechanical positioning of the LIDAR is described as scanning. The positioning process may determine an origin and direction of the LIDAR sample. Together with the range(s), the origin and the direction may be employed to generate sample point(s) in a base coordinate system. Each sample point, together with its ancillary data such as return intensity and/or color, may be described as a scan point. A collection of scan points may be described as a scan. The scan may include scan lines, each of which may include a collection of scan points collected during a single mechanical motion or sweep.

Several examples of mechanical positioning exist. On a typical terrestrial survey LIDAR, such as a Leica ScanStation C10, the mechanical positioning of the LIDAR may be achieved by vertically deflecting a field of view of the LIDAR with a vertical deflector and horizontally rotating the vertical deflector together with the LIDAR. In this way, a scanning field of view generally resembling a sphere may be achieved. In some airborne LIDAR systems, such as the Leica ALS70, the LIDAR may be deflected across a flight path by a deflector. The deflector and the LIDAR may be mounted to an aircraft. Similarly, in some ground-vehicle-based LIDAR systems, the LIDAR may be deflected about an environment as the vehicle moves along a path. A targeting wedge prism scanner may form a LIDAR field of view by passing a laser beam through two round wedge prisms, one rotating at a much slower speed than the second, thus creating a spiral LIDAR sampling path.

SUMMARY

The embodiments disclosed herein relate to compression and retrieval of three-dimensional (3-D) laser scan data.

A method of model-based scan line encoding includes defining a geometry model for describing a scan line of a scan, the scan line including multiple scan points. The method further includes calculating a trajectory model representing an approximate pattern of deviation of the multiple scan points relative to the geometry model. The method further includes calculating multiple residuals, each of the residuals associated with a difference between the deviation of the scan points and the trajectory model. The method may further include compressing the residuals.

Additional features and advantages will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by the practice of the embodiments. The features and advantages of the embodiments will be realized and obtained by means of the instruments and combinations particularly pointed out in the claims. These and other features will become more fully apparent from the following description and claims, or may be learned by the practice of the embodiments as set forth hereinafter.

DESCRIPTION OF EMBODIMENTS

The embodiments disclosed herein relate to compression and retrieval of three-dimensional (3-D) laser scan data. In typical scanning laser imaging, detection, and ranging (LIDAR) devices, the action of the LIDAR may be many times faster than the mechanical positioning, as the range and ancillary measurement data sources are electronic and optical in nature. The position and orientation components of a scan line may vary slowly and may closely follow a low dimensional model. The type of model followed by the scan line may be known in advance.

A model-based scan line encoder is disclosed. The scan line encoder may separate mechanically-driven and electro-optically-driven components of a scan line. The scan line encoder may further define a geometry model to describe the scan line relative to the mechanically-driven components. Scan points of the scan line may be compared to the geometry model and deviations between the scan points and the geometry model may be determined. A trajectory model may be calculated to represent an approximate pattern of the deviations of the scan points relative to the geometry model. Residuals may be calculated to represent the differences between the deviations and the trajectory model. The residuals may be compressed. The compressed residuals may be stored along with the geometry model and the trajectory model. Transforming the data using this model may enable effective lossless and lossy compression techniques. Furthermore, data loss may be matched to native error sources of scanning devices. In some embodiments, an index may allow particular scan data to be quickly located without the need to uncompress the entire data set.

Reference will now be made to the figures wherein like structures will be provided with like reference designations. The drawings are diagrammatic and schematic representations of exemplary embodiments and, accordingly, are not limiting of the scope of the claimed subject matter, nor are the drawings necessarily drawn to scale.

FIG. 1is a perspective view of an example terrestrial laser scanner100including a diagrammatic view of the kinematic behavior of the scanner100. The scanner100may be configured to mechanically sweep a laser beam over a 3-D reality by rapidly rotating the laser beam about an approximately horizontal axis101and rotating the scanner100and/or the laser about an approximately vertical axis103incrementally and/or slowly relative to the rotation of the laser beam about the approximately horizontal axis101. The angular position of the laser beam about the approximately horizontal axis101may be generally associated with an elevation102of the laser beam. The angular position of the laser beam about the approximately vertical axis103may be generally associated with an azimuth104of the laser beam.

FIG. 2is an abstract view of example kinematics200of the scanner100ofFIG. 1. A laser beam201may quickly rotate about a fast rotation axis204. The fast rotation axis204may generally correspond to the approximately horizontal axis101ofFIG. 1. As the laser beam201rotates, data samples described herein as scan points207may be taken at fixed time intervals. The scan points207associated with a complete or partial revolution of the fast rotation axis204are described herein as a scan line202. Although shown on a shared curve, the scan points207may be associated with various ranges associated with sampled distances from the origin of the laser beam201.

The laser beam201may rotate about a slow rotation axis206less quickly than the laser beam201rotates about the fast rotation axis204. The slow rotation axis206may generally correspond to the approximately vertical axis103ofFIG. 1. The slow rotation axis206may be nearly aligned with gravity208, and the fast rotation axis204may be nearly perpendicular to gravity208and/or to the slow rotation axis206.

The combination of the laser beam201rotating about the fast rotation axis204and the slow rotation axis206may allow scan points207to be gathered for a 3-D reality such as a room, an environment, or the like.

In some embodiments, the data collected at the scan points207may be associated with azimuth and elevation coordinates relative to the scanner. The azimuth axis may be aligned with gravity208and the elevation axis may be perpendicular to gravity208. Alternately, the azimuth axis and the elevation axis may be associated with some other physical element of the environment and/or an associated scanner. The azimuth and elevation coordinates may be angular coordinates generally corresponding, respectively, to the elevation102and the azimuth104ofFIG. 1.

In a practical laser scanner, the apparent origin of the laser beam201may not correspond directly with the azimuth and elevation coordinates due to misalignments and/or offsets of the scanner, some of which may be described, for example, in relation to the description of scanner calibration techniques in U.S. Pat. No. 7,643,135. For example, the fast rotation axis204and the slow rotation axis206may not be perfectly perpendicular. Furthermore, the origin of the laser beam201may not be related to any of the fundamental physical elements of the scanner kinematics200due to misalignments and/or offsets of the scanner. For example, the slow rotation axis206may not be perfectly in line with the direction of gravity208, and/or the fast rotation axis204may not be perfectly perpendicular to the direction of gravity208.

The misalignments and offsets of the scanner may not be provided by the scanner or by the manufacturer of the scanner. Furthermore, the misalignments and offsets may vary between scanners due to manufacturing tolerances, as well as potentially significant variances in the configuration and manufacturing processes of the scanners. Rather than providing the misalignments and offsets, scanners may instead provide measurement data that accounts for misalignments and offsets via naïve encoding.

The naïve encoding techniques of the scanner are often inefficient. For example, naïve encoding techniques that convert the detected scan data directly to objectively ideal azimuth angles and elevation angles, e.g., to azimuth angles and elevation angles associated with a fundamental physical element such as gravity208, may be inefficient because the misalignments and offsets cause large deviations in the converted quantities. For example, overlapping scan lines located at a zenith, e.g., near the slow rotation axis206opposite the direction of gravity208, of a scan may not intersect as a result of the misalignments and offsets, as disclosed inFIG. 3.

FIG. 3is a diagrammatic view of an example scanning artifact300that may be produced by the scanner100ofFIG. 1. In some instances, the artifact300may occur on a surface intersecting a slow rotation axis306, which may generally correspond to the slow rotation axis206ofFIG. 2. The multiple scan lines302may generally correspond to the scan line202ofFIG. 2taken at multiple locations about the slow rotation axis206. Each scan line may include multiple scan points308, which are shown only on one scan line302afor clarity.

In some instances, the scan lines302may form a void304due to internal manufacturing misalignments, offsets, or the like. For example, the void304may be formed when the fast rotation axis204is not perfectly perpendicular to the slow rotation axis306. Artifacts such as the artifact300may give rise to inefficiencies in naïve encoding techniques.

In some embodiments, model-based scan line encoding may be employed. In some instances, the model-based scan line encoding may provide efficient encoding of scan data.FIG. 4is a flowchart of an example method400of model-based scan line encoding that may be performed by the scanner100ofFIG. 1. The method400is described with continued reference toFIG. 2.

The method400may begin at block402, defining a geometry model for describing a scan line202of a scan, the scan line may include multiple scan points207. For example, the scan line202may lie roughly in a plane and/or roughly in a surface of an open cone. The geometry model may include a plane, a cone, a cylinder, a sphere, or the like or any combination thereof. The scan points207of the scan line202may not be described perfectly by the defined geometry model due to misalignments and/or offsets of the scanner100, or the like. For example, the scan points207may deviate from a plane, a surface of an open cone, and/or the like of the defined geometry model.

FIG. 5is a diagrammatic view of an example geometric model500, which may be employed by the scanner100ofFIG. 1, and/or by the method400ofFIG. 4. With continued reference toFIG. 2, the geometric model500may include a plane502defined relative to the scan line202.

Given a defined plane502, each of the scan points207may be defined relative to the plane502. Scan point506may generally correspond to the scan points207. Scan point506may have, in the plane502, a corresponding projected point507having a range508and an angle. Each scan point506may also include a deviation510normal to the plane502.

In some embodiments, the deviation510may be divided by the range508to derive an angular error that may be considered conceptually as moving the deviation510to a unit cylinder504oriented perpendicular to the plane502. Alternately or additionally, each scan point506may be converted to some other coordinates and/or some other geometric model500. For example, the deviation510may be moved to a unit sphere (not shown) or the like.

FIG. 6is a diagrammatic view of another example geometric model600that may be employed by the scanner100ofFIG. 1, and/or by the method400ofFIG. 4. With continued reference toFIG. 2, the geometric model600may include a cone602defined relative to the scan line202. The geometric model600may generally correspond to the geometric model500ofFIG. 5, with a deviation610of a scan point606being taken from a surface defined by the cone602in a manner generally corresponding to the deviation510ofFIG. 5. The deviation610may optionally be kept on a unit cylinder604as described with reference toFIG. 5. In some instances, the cone602may better model the geometry of the scan line202than the plane502as described with reference toFIG. 5.

FIG. 7is a perspective view of an example movable laser scanner system700. A laser scanner702may be attached to an automobile704or other vehicle configured to move the scanner, as represented by arrow706. As the automobile704moves706, the scanner702may use a laser beam708(shown in a first laser beam position708aand a second laser beam position708b) rotating about a fast rotation axis (not shown) to collect sample points709(shown as a first sample point709aand a second sample point709b) along a scan line710in a manner generally analogous to the scanner100ofFIG. 1. Additional scanners (not shown) may be included on the automobile704to collect additional sample points (not shown).

As the automobile704moves706, the scanner702moves with the automobile704. In some instances, the laser beam708rotates about the fast rotation axis several orders of magnitude faster than the scanner702is displaced by the automobile704motion706. In some embodiments, the displacement of the scanner702may be encoded in the geometric models ofFIG. 5,FIG. 6, or the like. For example, the displacement of the scanner702between collecting sample points709aand709bmay be encoded within the deviation510ofFIG. 5and/or the deviation610ofFIG. 6for the sample points709aand709b.

In some embodiments, an interpolated geometric model may be used. For example, an interpolated geometric model may be used when the laser beam708rotates about the fast rotation axis within several orders of magnitude faster than the scanner702is displaced by the automobile704motion706.

FIG. 8is a diagrammatic view of an example interpolated geometric model800that may be employed by the movable scanner702ofFIG. 7and/or by the method400ofFIG. 4. In some instances, the interpolated geometric model800may result in more efficient encoding of a scan line, such as the scan line710ofFIG. 7. For example, the interpolated geometric model800may result in more efficient encoding of a scan line when the laser beam708rotates about the fast rotation axis at a speed within several orders of magnitude of the speed of the automobile704motion706.

With continued reference toFIG. 7, the interpolated geometric model800may include a first plane802associated with a first frame804. The first plane802may generally correspond to the plane502ofFIG. 5. The first plane802and first frame804may generally be associated with a first laser beam position such as the first laser beam position708aofFIG. 7.

The interpolated geometric model800may further include a second plane806associated with a second frame808. The second plane806may be similar to the first plane802, but the associated second frame808may have a different orientation and/or position relative to the first frame804. The second plane806and second frame808may be associated with a second laser beam position such as the second laser beam position708bofFIG. 7. The second plane806may differ from the first plane802based at least in part on a displacement of a scanner between the first laser beam position708aand the second laser beam position708b. The displacement may result from movement of a vehicle, such as the motion706of the automobile704ofFIG. 7.

The interpolated geometric model800may further include an interpolated geometry810interpolated between the first plane802and the second plane806. The interpolated geometry810may be interpolated for each scan point of a scan line, such as the scan points of the scan line710ofFIG. 7. In some embodiments, the interpolated geometry810may include interpolated planes (not shown) associated with interpolated frames (not shown). In some embodiments, the first plane802, the second plane806, and the interpolated geometry810may be based on angles associated with the multiple scan points of a scan line710.

Other geometry may be used with and/or in place of planes. For example, a cone (not shown) generally corresponding to the cone610ofFIG. 6, a unit cylinder (not shown) generally corresponding to the unit cylinder504ofFIG. 5, and/or a unit sphere (not shown) may be used with and/or in place of the first plane802, the second plane806, and/or the interpolated geometry810.

Referring again toFIG. 4, in some embodiments, defining a geometry model as in block402may be based on a randomly selected subset of scan points. For example, a randomly selected subset of scan points may be used to determine whether a plane, a surface of an open cone, and/or the like should be used in the geometry model, as well as the coordinates for defining the geometry model. Alternately or additionally, the geometry model may be based on a random sample consensus (RANSAC) algorithm. Alternately or additionally, the geometry model may be based on calibration data of an associated laser scanner.

With reference toFIGS. 4 and 5, the method400may continue at block404, calculating a trajectory model representing an approximate pattern of deviation510of the scan points506relative to the geometry model500. For example, the trajectory model may represent an approximate pattern by which the scan points506deviate from a plane, a surface of an open cone, and/or the like. In some embodiments, the trajectory model may include a third-order polynomial. Alternately, the trajectory model may include another mathematic formula or the like.

FIG. 9illustrates a graph900of a deviation902of sample points904from a geometric model. The sample points are arranged by row index with overlaid trajectory models (“elevation trajectory model909” and “azimuth trajectory model910”). The graph900illustrates sample point904deviation in the elevation coordinate (“elevation deviation906”) and sample point904deviation902in the azimuth coordinate (“azimuth deviation908”). In some embodiments, the deviation902may be measured in micro-radians (uR). In some instances, jagged azimuth deviation908, such as seen inFIG. 9may result from the motorization technology used in a particular scanner. The azimuth trajectory model910may be calculated to represent an approximate pattern of the azimuth deviation908. The elevation trajectory model909may be similarly calculated to represent an approximate pattern of the elevation deviation906.

Although the elevation deviation906and the azimuth deviation908are shown, more or fewer deviation coordinates and/or trajectory models909and910may alternately or additionally be used. For example, a single deviation coordinate (not shown) defined relative to a geometry model such as the geometry models500,600, and700ofFIGS. 5, 6, and7, respectively, may be used. Furthermore, a single trajectory model (not shown) may be calculated to represent the deviation902based on the single deviation coordinate.

Referring again toFIG. 4, with continued reference toFIG. 9, the method400may continue at block406, calculating residuals associated with a difference between the deviation of the scan points and the trajectory model. For example, residuals912of the azimuth deviation908and the azimuth trajectory model910may be calculated.

The method400may continue at block408, compressing the residuals. For example, the residuals912between the azimuth deviation908and the azimuth trajectory model910may be compressed. The values of the residuals may be very small such that compression to a fraction of the scanner accuracy, which may be measured in arc-seconds (approximately 5 uR), may require only a few bits per scan point.

In some embodiments, the residuals may be delta encoded before compression. Alternately or additionally, the residuals may be encoded using eight-bit universal character set transformation format (UTF-8) encoding before compression. Alternately or additionally, the residuals may be run length encoded before compression.

The scan data may occupy a significantly reduced space in a memory and/or a storage. Furthermore, the scan data may include little to no loss in accuracy compared to conventional naïve encoding techniques. In some embodiments, the compressed scan data may be approximately ¼, ⅕, or ⅛ of the size of scan data compressed using conventional naïve encoding techniques.

FIG. 10is a flowchart of an example model-based compression process1000that may be performed by the scanner100ofFIG. 1. Given a collection of points in a scan line1002, the process1000may be used to compress the scan line data.

In block1004, a geometry model type may be defined. The geometry model type may be defined in advance. The geometry model type may alternately be defined based at least in part on the scan line1002. In some embodiments, the scan line1002or a collection of scan lines may be fit to multiple geometry models and a best fit may be selected.

In block1006, geometry model parameters may be defined. The geometry model parameters may describe a geometric model on which the LIDAR scanner was pointed. For example, the scan lines may be fit to a plane cone, cylinder, sphere, or the like or any combination thereof, and points in space may be in polar coordinates off of the geometry model.

In blocks1008and1010, the scan points of the scan line1002may be projected to the geometric surface and a trajectory model transforming a point index (described herein as channel I1008, or point number to row index) to trajectory coordinates on the geometry model may then be calculated. For example, the trajectory model may be a third-order polynomial or other low-order polynomial.

In block1012, the residuals against the trajectory model from block1010may be computed for each point. Depending on the compression strategy, the point row index1014and/or the residuals1016,1018, and1020may be compressed at block1022.

The geometry and/or trajectory models1024and the geometry model extents1026may be stored together with the compressed scan line components1028,1030, and1032. Three channels (A, B, and C) are shown together with the row index (I), though more or fewer channels may be possible. Data fidelity (loss) in compression may be matched against each model and constant in each channel.

In some embodiments, more compression may be possible, where the geometry and/or trajectory models and the geometric model extents are predictable from scan line to scan line, potentially as the result of a slower time scale mechanical process. Compressing only the scan line components may allow for swift access to the point data as the model and extents for each scan line is available. To search for points in a volume, the models and extents may be searched first. If a scan line contains relevant points, the residuals may be uncompressed. In some embodiments, only those residuals related to the searched-for points need be uncompressed, in contrast to uncompressing all of the residuals.

FIG. 11is a flowchart of another example compression process1100that may be performed by the scanner100ofFIG. 1. The process1100may be described as a geometry model column index model. In some embodiments, creating or estimating the geometric model parameters does not have to be done for each scan line or stored with each scan line1102. Instead, a model for a geometric (G) model may be estimated from row index. Optionally, a parametric (P) model may also be estimated from the row index. The parametric model may generally correspond to the trajectory model described with reference toFIG. 4.

The geometric model may be a slowly varying function of the column index and may be estimated with all scan line models or with a subset of scan line models. The scan line compression may be done with column-index-generated geometry instead of computing a scan line by scan line geometric model.

FIG. 12is a perspective view of an example airborne laser scanner1200. The airborne laser scanner1200for surveying may sweep a laser beam1208rapidly across a flight path1204. Scan data may be divided into scan lines1206. The airborne laser scanner1200may include an aircraft1202carrying a sweeping laser beam1208, such as a LIDAR. The time scale of the aircraft1202flight path1204versus the time scale of the laser beam1208motion may allow for each scan line to be modeled by a geometric model similar to the geometric models described herein. A plane or cone may be inferred from a single scan line506of point data, the center from the flight path1204, and/or from a laser (LAS) file format stored deflection angle.

The geometric model may be fit to the scan line data set collected by the airborne laser scanner1200. In some embodiments, the time for each point may be given for LAS format greater than 1.1 as global positioning system (GPS) time. The center of the cylinder is the aircraft1202position may potentially be inferred at encoding time. The aircraft1202position may be inferred from a stored angle and refined if multiple return points are available. Without multiple return points, points at the edges of the scan lines1206may be found and the distance/height to the aircraft1202center may be inferred from the stored angle. In instances including multiple return points, the multiple return points may lay on the same line, and the intersection of different multiple returns may be used to determine the approximate center of the aircraft1202. A map of row indices may be encoded, as there may be multiple returns.

FIG. 13is a graph1300of example delta-times that may be associated with a scan line of data that may be collected by the airborne laser scanner1200ofFIG. 12. Encoding a GPS time stamp (row index, Ir) for a scan line may be compact, as most points may have one of three values of delta-times. The delta-times with a value of zero may be multiple returns.

FIG. 14is a graph of example modeled scan data1400of elevation (sweep) and azimuth encoding along a single scan line1206of airborne laser scanner1200data. Encoded residuals may be much smaller than the size of the laser beam1208, as 50 uR may correspond approximately to 4 cm on the ground.

InFIGS. 13 and 14, the aircraft1202center is approximately eight hundred (800) meters in height and the LIDAR mirror is a four-parameter oscillating drive model instead of a cubic. A spinning polygon may fit with a cubic similar to a terrestrial laser scanner. The low parameter model and the residual compression technique may be chosen as appropriate.

The embodiments described herein may include the use of a special purpose or general purpose computer including various computer hardware or software modules, as discussed in greater detail below.

Embodiments described herein may be implemented using computer-readable media for carrying or having computer-executable instructions or data structures stored thereon. Such computer-readable media may be any available media that may be accessed by a general purpose or special purpose computer. By way of example, and not limitation, such computer-readable media may include tangible computer-readable storage media including random-access memory (RAM), read-only memory (ROM), electrically erasable programmable read-only memory (EEPROM), compact disc read-only memory (CD-ROM) or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other storage medium which may be used to carry or store desired program code in the form of computer-executable instructions or data structures and which may be accessed by a general purpose or special purpose computer. Combinations of the above may also be included within the scope of computer-readable media.