A 660Kb PDF of this article as it appeared in the magazine complete with images is available by clicking HERE
Greetings and welcome from the US Northwest! In the last issue, I related some fun experiences while scanning seacliffs in San Diego. In this article, I would like to discuss some of the challenges we faced while trying to geo-reference our data and the subsequent development of a freely available program, PointReg to enable fast, accurate alignment of laser scan data.
Point Cloud Alignment
First, I would like to briefly review common workflows for point cloud geo-referencing. Despite many recent advances in technology and software for scan alignment, point cloud georeferencing can still be challenging for some applications. I refer you to the book Airborne and Terrestrial Laser Scanning, edited by Vosselman and Maas (2010) for a thorough review of point cloud alignment techniques and references. Most methods can be summarized as directgeoreferencing, target based resection, or software (aka cloud to cloud) techniques. Some software also allows you to mix and match some of these approaches. Each of these techniques calculate the transformation of the scan with translation (X,Y,Z) and rotation (, , ) components (Figure 1). With some scanners, the user can input environmental corrections for scaling as well; however, this is done independent of the alignment process.
For direct geo-referencing, the scanner is setup over a control point, leveled and backsighted to a point of known coordinates to geo-reference the scan, providing the advantage that the scan is geo-referenced in the field, rather than during post-processing. This follows a more traditional surveying workflow. The disadvantage is that it requires more time and precision in instrument setup compared to other techniques.
Target-based techniques use either reflective or easily identifiable pattern targets as common tie points between scans, so the scanner’s origin and orientation is determined indirectly. Targets do require additional time to set-up and need to be externally surveyed for geo-referencing. Also, for most longer range applications, targets often need to be scanned in separately at higher resolutions than the rest of the scene. However, the registration process is fairly simple and fast to implement in most commercial software, provided the user follows a consistent naming convention.
Software approaches (cloud to cloud registration) generally use common features found in the point clouds of neighboring scans to match the scans into a common coordinate system. A simple version of this is a procedure where the user selects 3 or more matching points between each scan, similar to earlier photo-stitching software. Because manual selection can be tedious, several approaches have been developed to automatically determine the matching point pairs. However, most automated matching algorithms require that the scan alignment is closely approximated as a starting point.
Traditionally, the point pairs were found using the Iterative Closest Point (ICP) algorithm (developed by Besl and McKay, 1992), which assigns the closet point in one scan as a match to another point in a second scan. Several point pairs are established and used for a least squares adjustment to determine the coordinate transformation parameters. As the alignment is refined, point-pairs can be updated.
The ICP algorithm has several variants to improve speed, stability, and accuracy. A common variant is minimizing the distance between a point to a plane rather than point to point. Scans are typically aligned in a pair-wise fashion, two at a time. There are also global registration techniques to improve scan alignments between multiple neighbors. Recent work uses geometric primitives found in the scans as matching features such as cylinders, spheres, etc. between scans to provide the transformations and has shown great promise in many applications such as plant and industrial scanning.
Software-based registration has the advantage that it requires minimal setup time since the scanner does not need to be leveled over a control point and targets are not needed. It also has the advantage that the registration is performed using thousands of points rather than just a limited number (typically 35) of targets. However, for the alignment to be successful, scans need to have sufficient overlap on distinct features. Software alignments can be time consuming in processing since the user needs to closely align the scans and usually run through several iterations. An additional setback to this approach is that the scans may be in a common coordinate system, but still need to be geo-referenced into a standard coordinate system. Either a baseline scan that has been geo-referenced is required or the user needs to determine coordinates of points in the point cloud that they have geo-referenced coordinates for.
Dynamic Environments
When scanning on the coast, we were faced with multiple challenges that produced difficulties in scan data collection and geo-referencing. (Each application of scanning will typically have its own unique challenges). First, the ocean created relatively short time windows (46 hours) to complete the field work and reduced the amount of the beach we could set the instrument up on. Second, the crumbling cliffs were not good places to set up targets for both safety reasons and because we would constantly have to replace targets. Control points cannot be effectively setup on the beach itself because of waves, public restrictions, and seasonal sand variations.
We mounted our scanner to a wagon to reduce setup time; however, the wagon platform was difficult to level. Another problem we faced that was that since the cliffs were eroding, we could not collect a baseline scan and use that as alignment for all subsequent scans. Each survey needed to be independent for accurate change analysis. When we employed software alignment procedures, we found significant problems with error propagation and required a lot of manual interaction. Hence, we had to deviate from typical procedures to align the scans.
PointReg
PointReg, a free software program I developed, employs a hybrid approach incorporating the direct geo-referencing and software based approaches previously discussed. Here-in, I will only provide a quick summary of PointReg. For more detailed information I refer you to two recent publications (Olsen et al., 2009) and (Olsen et al. 2011) in the ASCE Journal of Surveying Engineering which discuss more of the nuts and bolts of how the program works and operates along with accuracy assessments.
During the field data collection, the operator obtains most of the georeferencing transformation parameters needed for scan alignment. First, the scan origin coordinates can be obtained through RTK GPS, determining the translation in X,Y,Z. Second, because of difficultly in leveling the instrument mounted to a wagon, we relied on level compensators to determine the rotation about the scanner’s X and Y axes. The rotation about the Z axis, however, proved to be the most difficult value to obtain precisely. An estimate for the rotation about the Z axis can be found using a variety of methods, depending on the scanner and workflow, including:
1. Backsight (align) the scanner to a previous scan position or known point, if available,
2. Consistently orient the scanner to a certain direction (e.g. North or West),
3. Use a digital compass to determine the orientation of the scanner,
4. Rotate scans about their origin in software until a close fit is found, or
5. Pick a point in scan and find same point in a geo-referenced dataset and calculate the required rotation.
As part of my graduate studies, I derived a direct least-squares solution to refine the Z-rotation of a scan to match neighboring scans, which is implemented into PointReg. Although it is a direct solution, I found that iterations were still required for a few reasons. First, all of our scans needed to be aligned and geo-referenced. The assumption with least squares is that you are only adjusting one of the datasets to fit fixed control points in a second dataset. Second, as the alignment is improved, better point pairs can be selected.
Several features of PointReg are:
1. It operates in batch mode, automating much of the alignment procedure,
2. It simultaneously aligns and geo-references scans,
3. The alignment is determined based on multiple scan neighbors,
4. The program has an improved spatial distribution of point pairs. Point pairs are selected from areas with sufficient coverage and are distributed across the entire scan window.
5. All scans are able to be adjusted (i.e. does not require a fixed scan),
6. Prevents error propagation by constraining key geo-referencing parameters, and
7. Users have a lot of flexibility to adjust parameters of the registration.
Unfortunately, PointReg is not the answer for everything. I (and others I have worked with) have thoroughly tested it for dynamic environments (such as the coast) and found it to perform consistent with the equipment used (RMS -Root Mean Square error values between scans typically range from 24 cm with RTK GPS and a scanner with a nominal accuracy of 5mm). However, for small sites, interior scanning, and many other applications, targets would probably be a more efficient approach.
Perhaps the most significant limitation of PointReg is derived from the current situation of limited data interoperability between scan systems. Until the E57 format is standardized into manufacturer software, ASCII txt files are the simplest (and probably slowest) way to read scan data from any scanner. However, to speed up repeat runs, these text files are converted to a binary format. Additionally, the rotation values output from PointReg can be directly applied in most scanner software without requiring re-input of the entire point cloud dataset.
Scan Alignment Quality Control
There are several measures of scan alignment quality, which can be used for any alignment method. The amount of time and energy spent on these quality control measures should be representative of the project QA/ QC requirements and quantity of data generated. First, an external dataset (e.g. topo points acquired with a total station or GPS, depending on accuracy needs) provides validation of the geo-referencing quality. However, this requires additional field time, equipment, and personnel. Second, the RMS values obtained through most alignment software provides a useful mathematical evaluation of accuracy. These values, however, can be influenced by clutter (e.g. vegetation, people, etc.) in the scan scene. Visual checks and verifications should also be performed. Although large misalignments are generally easy to spot when visually inspecting the data, subtle misalignments require extra attention. One check is to color each scan differently and look at areas of overlap (see Figures 2 and 3). When one color is predominant (Figure 2), that indicates the alignment is very poor. Rather, the colors should blend together in areas of overlap (Figure 3). Note that there will still be some sections where one color tends to dominate due to increased point density or because that location was only visible from one scan. Finally, visual examination of cross sections can help evaluate the effectiveness of an alignment. Scans that are misaligned will appear as multiple profiles, rather than a single profile.
Final Remarks
PointReg and a GUI are available for free download at: http://www.engr.orst. edu/~olsen/PointReg/. As new ideas come to mind, I continually update PointReg and add in new features. I welcome any feedback regarding the program and hope you find it useful.
Michael Olsen is an Assistant Professor of Geomatics in the School of Civil and Construction Engineering at Oregon State University. He currently chairs the ASCE Geomatics Spatial Data Applications Committee and is on the editorial board for the ASCE Journal of Surveying Engineering. He has BS and MS degrees in Civil Engineering from the University of Utah and a Ph.D. from the University of California, San Diego.
Note: References for this article can be found in the PDF.
A 660Kb PDF of this article as it appeared in the magazine complete with images is available by clicking HERE