1. Field of the Invention
This invention generally relates to the fields of remote measurement and three dimensional modeling and, specifically, to improving the spatial resolution of digital elevation models and range measurement datasets.
2. Description of Related Art
Light Detection and Ranging (“LIDAR”) systems are capable of accurately measuring a grid of distances from a sensor to a target object or surface. After processing the raw measurements, accurate three-dimensional models of the target can be produced. LIDAR sensors and LIDAR-derived datasets are widely used in Geographic Information Systems (GIS) for a variety of tasks such as flood plain analysis, city skyline analysis, aerial image ortho-rectification and urban modeling. The level of detail present in such datasets is limited by sensor capabilities, with a typical tradeoff between the number of individual measurements and the physical size and extent of the target. In particular, the spatial resolution of airborne LIDAR sensors is limited by the rate at which individual range measurements can be made.
A single measurement from a LIDAR sensor does not typically correspond to a single infinitesimal point on the target. Due to laser beam divergence, a single measurement corresponds to a region on the target whose size depends in part upon the distance between the sensor and the target. Full waveform LIDAR sensors are capable of recording a signal that represents the distribution of distances measured from the sensor to the region. FIGS. 1 and 2 depict two sample measurements. Typically, the most prevalent distance, the statistical mode 11, measured for a region is determined to be the single representative distance for a given measurement. More advanced statistical analysis of the measurement distribution can also yield information about surface variability. For example, in FIG. 2, the second sample measurement, the dual peaks of the waveform 21, 22 are indicative of two significantly different distances within the single measurement. Such a measurement could be encountered when the measurement region overlaps two distinct surfaces, such as a building roof and the ground below. Decomposing such waveforms correctly is a difficult task which cannot be accomplished by means of the measurement hardware alone (Bretar et al, Managing Full Waveform Lidar Data: A Challenging Task for the Forthcoming Years, International Archives of the Photogrammetry, Remote Sensing and Spatial Information, Vol. 37, Part B1, 2003).
The prior art shows several examples of attempts to improve the ability of LIDAR sensors to obtain detailed three-dimensional information about the surface of a target. For example, U.S. Pat. No. 7,417,717 to Pack et al. discloses a combination LIDAR and electro-optic detector system. In Pack, the electo-optic image is used to match multiple LIDAR shots of a particular target relative to one another so that the overall three-dimensional accuracy of any single LIDAR data set may be improved. Although such a system may result in improvement of the three-dimensional accuracy of a single LIDAR data set, it is still limited by LIDAR sensor capabilities. Moreover, such a system requires multiple measurements of the range (multiple LIDAR passes) from different locations to the target. Such requirements may prove limiting. For example, when mapping large terrestrial areas from the air, safety and regulatory restrictions may prevent secondary passes at a nearer distance to the ground.
U.S. Patent Application No. 2009/0323121 to Valkenburg et al., discloses a hand-held scanner that combines a range sensor, which may be a LIDAR device, a position and orientation sensor and a texture sensor. Although Valkenburg indicates that the data from these devices may be used to create a realistic three-dimensional representation of a scene, Valkenburg does not address how non-LIDAR “texture” data may be used to improve the resolution of the ranging device. Moreover, Valkenburg is directed toward short range applications and not at gathering information about remote targets.
U.S. Patent Application No. 2009/0119010 to Moravec, discloses a navigation and mapping system that combines the use of stereo cameras with long range sensors such as LIDAR. This system is primarily directed toward navigation, however, and it does not address the problem of improving the resolution of the long range sensor system.
It is well known that three-dimensional range information about a target may be derived from the stereographic processing of two or more images of a scene. Due to the passive nature of the measurement, several difficulties exist with this approach. These difficulties include: (1) the correspondence problem, as it is difficult to unambiguously identify the same feature in multiple images due to the presence of noise and differences in perspective and illumination (D. Scharstein and R. Szeliski, A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms, International Journal of Computer Vision, 47(1/2/3): 7-42, April-June 2002); (2) the aperture problem, which results in textureless or repetitive regions of an image pair being difficult to match (Kanade and Okutomi, A Stereo Matching Algorithm with an Adaptive Window: Theory and Experiment, Proceedings of the 1991 IEEE International Conference on Robotics and Automation, Sacramento, Calif., April 1991); and (3) geometric consistency problems such as surface discontinuities and occlusions (Scharstein and Szeliski, 2002).
A variety of approaches exist in the fields of photogrammetry and computer vision to mitigate these problems (Scharstein and Szeliski, 2002). Correspondence problems can be minimized by using advanced feature matching techniques such as SIFT (D. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, International Journal of Computer Vision, International Journal of Computer Vision, 60, 2 (2004) at 91-110) or SURF (H. Bay et al, SURF: Speeded Up Robust Features, Computer Vision and Image Understanding, Vol. 110, No. 3 (2008) at 346-59). Windowing and geometric consistency problems can be mitigated by the use of global optimization methods, such as those set forth in U.S. Pat. No. 6,046,763 to Roy and J. Sun et al, Stereo Matching using Belief Propagation, IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 25, No. 7 (2003) at 787-800.
Although technically possible, it is typically impractical to obtain a level of distance accuracy equivalent to LIDAR from a stereo imaging system. For a given distance to the target, geometric constraints on the stereo baseline as well as limitations on image resolution render unfeasible long distance, high-accuracy distance measurements using stereo imaging. Additionally, the aforementioned challenges can result in blunders in range data derived purely from stereo images. Such problems limit the measurement capabilities of stereo imaging systems.
There is no consideration in the prior art of an approach that simultaneously combines Full Waveform LIDAR measurements with stereo extraction to produce hybrid measurements. Such an approach has several advantages due to the complementary nature of accuracy and measurement density of LIDAR and stereographic range measurements. Full waveform LIDAR sensors can measure ranges to centimeter-level accuracy from distances of up to thousands of meters. Conversely, imaging systems with very high spatial resolutions are commercially available. By carefully processing the two datasets together, the combination of direct range measurements with stereo extraction would enable an increase in measurement density without a loss in ranging accuracy. An additional advantage of such a hybrid dataset would be that the imagery and the range data are inherently consistent. This is important when rendering the imagery upon the three-dimensional surface, for example, since abrupt changes in the depth dimension will tend to correspond with object borders in the imagery, even though the original range measurements would not have permitted such fine resolution. Thus, three-dimensional visualization and renderings of the highest quality can be produced. Lastly, the hybrid nature of the dataset means that with careful selection of the type of imagery (visible, infrared, etc) used by the method, it is possible to fill voids or gaps in the LIDAR measurements, such as those caused by dense clouds or non-reflective surfaces.
Finally, the prior art that has taught the use stereo imagery to improve range data has focused on feature-based improvement rather than global optimization. One example is S. Becker and N. Haala, Refinement of Building Fassades By Integrated Processing of LIDAR and Image Data, International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. 36, Part 3/W49A (2007) at 7-12. This reference concerns the geometric modeling of building facades. Although the modeling method utilizes image data to improve a LIDAR data set, it focuses on recognizable structures, such as edges of windows and doors to accomplish this improvement. Because range data may be taken of any target, not just targets having recognizable structures, a method achieving global optimization of the range data, rather than a feature-based improvement is preferred.
As shown by the prior art, none of the prior approaches have improved the long range measurement capability of range sensors such as LIDAR and IFSAR by combining their measurements with those produced by stereo imaging in a manner that fundamentally improves the resolution and density of the range measurements. The potential advantages of such an approach would address a long felt but unmet need in the field of remote measurement.
USPTO Backgrounds
USPTO Backgrounds