Ladar-based motion estimation for navigation

A method for estimating motion with at least one laser radar is disclosed. The method involves scanning a first range image at a first time, locating a plurality of object features in the first range image, scanning a second range image at a second time, receiving motion data for a time period between the first and second times, and locating the plurality of object features in the second range image based, at least in part, on the motion data to determine an orientation of the object. Based on the orientation of the object, the method estimates motion by comparing the location of the plurality of object features in the first scanned range image to the location of the plurality of object features in the second scanned range image.

This application is related to commonly assigned U.S. patent application Ser. No. 11/673,893, filed on Feb. 12, 2007 and entitled “SYSTEM AND METHOD FOR MOTION ESTIMATION USING VISION SENSORS” (the '893 application). The '893 application is incorporated herein by reference.

BACKGROUND

Many guidance, control, and navigation (GNC) applications provide precise navigation when necessary. For example, precision landing of a military aircraft or spacecraft requires precise navigation. In addition, unmanned vehicles, such as unmanned aerial vehicles (UAV) also require accurate position and velocity information in order to properly navigate an area (target). Most of these GNC applications employ one or more global positioning system (GPS) sensors to achieve a necessary level of navigation precision. In addition, stringent requirements on precision landing and navigation dictate stringent performance requirements for the GNC application.

Various methods and systems have been employed to meet these stringent performance requirements. Interest point (corner) detection extracts certain types of point features and estimates contents of the target image. Corner detection is frequently used in navigation, motion detection, and image tracking and recognition. An interest point is a point in the image which has a well-defined position that is suitable for detection, such as the intersection of two edges (that is, a corner). Corner detection quality is typically based on detecting the same corner in multiple images, which are similar but not identical (for example, multiple images having different lighting, translation, and rotation). Simple approaches to corner detection of multiple images often become very computationally expensive and generate less than adequate results.

An inertial measurement unit (IMU) measures acceleration in a plurality of directions. The IMU uses the measured accelerations to estimate motion in each of the measured directions. Unfortunately, the IMU measurements are subject to measurement drift that adversely affects the accuracy of the IMU measurements. Available GPS satellite data updates the IMU measurements, improves the accuracy of the position and velocity data, and periodically corrects any accuracy errors in the IMU measurements. When the GPS satellite data is not available, however, the motion estimates are not available in real time. Furthermore, when results are not immediately available, these stringent performance requirements are violated.

SUMMARY

The following specification discusses ladar-based motion estimation for navigation. This summary is made by way of example and not by way of limitation. It is merely provided to aid the reader in understanding some aspects of one or more embodiments described in the following specification.

Particularly, in one embodiment, a method for estimating motion with at least one laser radar is provided. The method involves scanning a first range image at a first time, locating a plurality of object features in the first range image, scanning a second range image at a second time, receiving motion data for a time period between the first and second times, and locating the plurality of object features in the second range image based, at least in part, on the motion data to determine an orientation of the object. Based on the orientation of the object, the method estimates motion by comparing the location of the plurality of object features in the first scanned range image to the location of the plurality of object features in the second scanned range image.

DETAILED DESCRIPTION

The following detailed description describes at least one embodiment for ladar-based motion estimation for navigation using a laser radar (ladar) to estimate motion. Advantageously, the ladar, in communication with an inertial measurement unit (IMU), provides motion estimates of a host vehicle by using absolute orientation between three-dimensional (3-D) point features. Over a prescribed time period, the motion estimates provide real-time, multi-dimensional navigation information of the host vehicle to one or more navigational monitoring systems in communication with the host vehicle.

FIG. 1is a block diagram of an embodiment of a motion estimation system100. The system100comprises at least a processing unit106, an IMU102, and a ladar104. The ladar104and the IMU102are each coupled to the processing unit106and provide input data to the processing unit106for estimating motion (for example, position, velocity and a combination thereof). In one implementation, the system100further comprises at least one optional GPS sensor108, an optional display element110, and an optional movement actuator112, each of which are in communication with the processing unit106. In this and alternate implementations, the system100resides on at least one of an aircraft, an automobile, a spacecraft, a UAV, and any other host vehicle that requires real-time, multi-dimensional navigation information.

In the example embodiment ofFIG. 1, the IMU102measures motion in at least three degrees of freedom. In particular, the IMU102includes at least three sensors to measure acceleration along three orthogonal coordinate axes. For example, the IMU102comprises, but is not limited to, three linear accelerometers configured to obtain acceleration along the three coordinate axes. In other words, the accelerometer measurements are used to estimate position and velocity, including the effects of gravity. As described in further detail below, the processing unit106determines an absolute orientation (position) of the system100based on the motion measured by the IMU102.

The ladar104transmits light (for example, a laser) out to a target, as further discussed below with respect toFIG. 2. The transmitted light interacts with and is modified by the target. For example, at least some of the transmitted light is reflected (scattered) back to the ladar104for analysis by the processing unit106. The change in the properties of the light enables at least one property (for example, at least one point feature, such as a corner) of the target to be determined.

In one implementation, the ladar104is at least one of a scanning ladar, a flash ladar, and a Doppler ladar. It is understood that the ladar104is suitable for implementation in any appropriate manner for emitting a laser radar signal using any other current and future 2-D and 3-D laser radar technology. The range finder ladar104measures the distance from the ladar104in the vehicle to a target by emitting the light in a single (for example, a horizontal) direction. The time for the light to travel out to the target and back to the range finder ladar is used to determine the range to the target. Similarly, the flash ladar104measures the distance from the ladar104in the host vehicle of the system100to a target by emitting the light in multiple directions at substantially the same time. The Doppler ladar104measures the velocity of the target. When the light transmitted from the Doppler ladar hits the target moving towards or away from the Doppler ladar, the wavelength of the light reflected (scattered) off the target will be changed slightly. This is considered the Doppler shift of the Doppler ladar104. For example, if the target is moving away from the Doppler ladar104, the return light will have a longer wavelength; if moving towards the Doppler ladar104, the return light will be at a shorter wavelength.

Positions based on the IMU102measurements are corrected (updated) with measurements from the optional GPS sensor108. Position data from the GPS sensor108does not drift as with data from the IMU102. When the GPS data is unavailable, one or more positions based on the IMU102are updated (corrected) with measurements from the ladar104. In one implementation, the ladar104is used in conjunction with the GPS sensor108. For example, the ladar104can be used whenever a GPS satellite signal is unavailable or concurrently with the GPS sensor108regardless of availability of a GPS satellite signal. Alternatively, the GPS sensor108is omitted in some embodiments. In such embodiments, data from the IMU102is only updated with measurements from the ladar104.

The ladar104is configured to scan an area near the system100at a first time. The ladar104is implemented as any appropriate device for scanning ranges using, but not limited to, a range finder (line scan) laser radar, a flash laser radar (flash scan), and a Doppler laser radar. It is understood that the system100is capable of accommodating any appropriate number of ladars (for example, at least one ladar104) in a single system100. In one embodiment, the system100includes an (optional) ladar114substantially similar to the ladar104. The (optional) ladar114is (optionally) configured to scan the area near the system100at a second time.

The processing unit106comprises a plurality of program instructions for carrying out the various process tasks, calculations, and generation of signals and other data used in the operation of the system100, such as to correlate the location of point features of a target, and to determine the velocity and position of the device in which system100is located. The system100uses the ladar104to correct and update the target position based on IMU data from the IMU102. In some embodiments, the calculated position based on the IMU data from the IMU102is combined with the calculated position from the ladar104. In other embodiments, the calculated position from the ladar104is used in place of the calculated position based on the IMU data from the IMU102. In such embodiments, the IMU102estimates the location of 3-D point features in a plurality of scans captured by the ladar104. It is understood that the plurality of scans discussed in the present application refer to at least one of a plurality of line scans, flash scans, and Doppler scans.

In operation, the IMU102measures acceleration of a vehicle in at least three degrees of freedom. The IMU102transfers the measured acceleration to the processing unit106. The processing unit106processes the plurality of scans from the ladar104as a plurality of scan images. In particular, the ladar104scans a first scan image at a first time T1and a second scan image at a second time T2. In an alternate embodiment, the ladar104scans the first scan image at the first time T1and the (optional) ladar114scans the second scan image at the second time T2. The processing unit106locates a plurality of features in each of the two scan images from the time T1. The processing unit106correlates the location of the plurality of features in one of the two scan images with the location of the one or more features in the other scan image.

The processing unit106calculates an estimated position and velocity using the measured acceleration from the IMU102. The estimated position and velocity is used by the processing unit106together with the location of the plurality of features in the scan images of the time T1to estimate the location of the plurality of features in at least one of the scan images of the time T2. Based on these estimates, the processing unit106determines the actual location of the plurality of features in the scan image of the time T2by focusing on a small area around the estimated position. The small area is defined by the possible error in the measurements of the IMU102. Once the actual location of the one or more features is determined, the processing unit106calculates the position and velocity of the host vehicle based on a comparison of the location of the one or more features (that is, the absolute orientation) between the scan images from the time T1and the scan images from the time T2as described in further detail below with respect toFIG. 2.

In one implementation, the processing unit106combines the estimated positions and velocities from the IMU102and the ladar104to obtain a more accurate motion estimate. Alternatively, the processing unit106uses the motion estimate from the ladar104. The more accurate estimate is (optionally) displayed on a display element110, in some embodiments. For example, an automobile using the system100(as the host vehicle) will use the display element110to display to a driver of the automobile where the host vehicle is located on a map. In other embodiments, the processing unit106uses the more accurate estimate to determine the necessary actions to take in order to reach a programmed destination. Moreover, the processing unit106generates control signals which are sent to the optional movement actuator112to control the movement of the host vehicle. For example, the processing unit106controls the movement of a UAV in real time based on control signals transmitted to the movement actuator112(such as the throttle, wing flaps, and the like) in the UAV to control at least the pitch, yaw, and thrust of the UAV.

By correlating the location of point features from each of the scan images processed by the processing unit106at a first moment in time with the location of point features from each of the scan images processed in the processing unit106at a second moment in time, the processing unit106determines the position and velocity of the host vehicle. The processing unit106is configured to estimate the location of the point features in the scans from the ladar104at the second moment in time based on data received from the IMU102and the location of the point features in scans obtained at the first moment in time. The estimation of the location of the point features in the second image is described in more detail below with respect toFIGS. 2 and 3. The processing unit106locates the point features in the second image using absolute orientation by scanning the point features in a smaller area located around an estimated location of the point features. Once the actual location of the features is identified, the processing unit106calculates the change in position of the host vehicle.

FIG. 2is a model of an object208detected by the system100at different ranges as detected by the ladar104ofFIG. 1. In particular, the ladar104captures a scan image A1at time T1and a scan image A2at time T2. The scan images A1and A2are provided by way of explanation and not by way of limitation. It is to be understood that the object208and the scan images A1and A2will vary in operation depending on the area near the object208in which the system100is located. In particular, although the object208is shown as a rectangle inFIG. 2, it is to be understood that in other embodiments the object208is any appropriate object from which absolute orientation and motion estimates are determined (for example, the object208is at least one of a tunnel, a building, a tower, a tree, a river, and the like).

The object208is comprised of a plurality of features2021to202N. A feature, as used herein, refers to any set of one or more scans that have a high contrast (for example, a well-defined point) with respect to the surrounding scans in the images A1and A2. Also shown in each of the scan images A1and A2are coordinate axes204. The coordinate axes204are provided for purposes of explanation, but are not necessary for operation. In particular, the coordinate axes204demonstrate the relative position of the object208in each of the scan images A1and A2.

In operation, the ladar104obtains the scan image A1at the time T1and the scan image A2and the time T2. As illustrated inFIG. 2, the object208is offset differently from a center210in the scan image A1than in the scan image B2. Once the scan images A1and A2are captured, the processing unit106locates the features2021to202Nin each of the scan images A1and A2. Once the features2021to202Nare located, the processing unit106correlates the respective locations of each of the features202in the scan image A1with the same features202in the scan image A2. For example, the processing unit106correlates the location of feature2021in the scan image A1with the location of feature2021in the scan image A2. Any appropriate technique will locate the features2021to202N(for example, at least one of a Harris corner detector and a Kanade-Lucas-Tomasi, or KLT, corner detector).

Once each of the features202are correlated, the processing unit106determines the position and attitude of the object208. For example, in this embodiment, the vehicle that comprises the system100has banked and turned to the left as well as pitched downward. The movement of the vehicle causes the object208as depicted in the scan image A2, for example, to move and rotate to the right, and to move up in the scan image A2. In addition, the vehicle has moved toward the object208causing the object208to be larger in the scan image A2. Therefore, the features2021to202Nin the scan image A2are not located near the original position (that is, the scan location) of the features2021to202Nin the scan image A1.

The processing unit106uses IMU data received from the IMU102to determine an approximate location of the features2021to202Nin the scan image A2. For example, the processing unit106locates the feature2021in the scan image A1as a starting point. The processing unit106propagates the location of the feature2021forward based on data received from the IMU102over the time period between time T1and time T2. In propagating the location forward, the processing unit106identifies an area206in which the feature2021is located. The area206results from the known approximate error of measurements obtained from the IMU102. For example, if the IMU102measures a lateral movement of 2 meters to the right over a time period of 1 second but has a known error of 0.1 meters/second, the actual location of feature2021is between 1.9-2.1 meters to the right of its location at time T1. The processing unit106evaluates the scans in the area206to identify the actual location of the feature2021in the scan image A2. Alternatively, the processing unit106evaluates scans successively further away from the estimated location of the feature2021, starting with the scans adjacent to the estimated location, until the actual pixel location is identified. In such embodiments, the approximate error in the IMU data does not need to be known.

The processing unit106uses known techniques, such as the KLT corner detection, to locate the feature2021in the area206. By focusing on the area206of the scan image A2rather than the entire scan image, the processing unit106is able to locate the feature2021substantially faster than in known motion estimation systems that search substantially larger areas. The processing unit106uses the IMU data to estimate the location of the features2021to202N. Once the actual location of the feature2021in the scan image A2is located, the processing unit106calculates the absolute orientation of the remaining features202in the scan image A2. This calculation uses enhanced absolute orientation to correlate each of the features202read in the scan images A1and A2to provide a closed-form solution in calculating the absolute orientation. With knowledge of at least a portion of the motion change and at least a portion of a change in orientation of the features202, motion estimates are determined as described above with a single 3-D ladar (for example, the ladar104).

FIG. 3is a flow diagram illustrating a method300for estimating motion using the system100. The method300addresses estimating motion of the host vehicle with the processing unit106by using enhanced absolute orientation between the 3-D point features2021to202N. Over a prescribed time period, the motion estimates provide real-time, multi-dimensional navigation information of the host vehicle to the one or more navigational monitoring systems in communication with the host vehicle.

At block302, the ladar104scans a first range with the ladar104at a first time. The processing unit106locates the features2021to202Nin the first scanned range image at block304. At block306, the ladar104scans a second range at a second time. The processing unit106receives data from the IMU102for a time period between the first and second times at block308. In one implementation, the processing unit106combines a motion estimate based on IMU data from the IMU102with the motion estimate based on a comparison of the scan of the features2021to202Nin the first range to the scan of the features2021to202Nin the second range from the ladar104. At block310, the processing unit106locates the features2021to202Nin the second scanned range image based at least in part on the IMU data from the IMU102. At block312, the processing unit106estimates motion of the object208using enhanced absolute orientation. The motion estimation of the object208is based on at least a partial comparison of the location of the features2021to202Nin the first scanned range image to the location of the features2021to202Nin the second scanned range image.

In one implementation, the processing unit106locates the features2021to202Nbased on the absolute orientation of the object208by correlating 3-dimensional object features2021to202Nin the first range with 3-D object features2021to202Nin the second range. The processing unit106correlates the features2021to202Nusing at least one of the KLT corner detection algorithm and the Harris corner detection algorithm. In at least the same (and alternate) implementation(s), the processing unit106receives a GPS signal from the (optional) GPS108. In this implementation, the processing unit106estimates motion based, at least in part, on the GPS signal when the GPS signal is available from the optional GPS108.

The processing unit106locates the features2021to202Nin the second range based, at least in part, on the IMU data from the IMU102. Using the IMU data, the processing unit106scans the features2021to202Nin the first range at a first scan location, selects a second scan location in the at least one second range based on the IMU data and the first scan location, and evaluates range scans near the second scan location to identify the actual location of the features2021to202Nin the at least one second range. In one implementation, the processing unit106evaluates the range scans near the second scan location by evaluating the range scans in an area substantially surrounding the second scan location. Moreover, the size of the area is determined based on the approximate error in the IMU data.

While the methods and techniques described here have been described in the context of a fully functioning motion estimation system, apparatus embodying these techniques are capable of being distributed in the form of a computer readable medium of instructions and a variety of forms that apply equally regardless of the particular type of signal bearing media actually used to carry out the distribution. Examples of computer readable media include recordable-type media, such as a portable memory device; a hard disk drive (HDD); a random-access memory (RAM); a read-only memory (ROM); transmission-type media, such as digital and analog communications links; and wired (wireless) communications links using transmission forms, such as (for example) radio frequency and light wave transmissions. The computer readable media may take the form of coded formats that are decoded for actual use in a particular motion estimation system by a combination of digital electronic circuitry and software (or firmware) residing in a programmable processor (for example, a special-purpose processor or a general-purpose processor in a computer).

This description has been presented for purposes of illustration, and is not intended to be exhaustive or limited to the form (or forms) disclosed. Furthermore, the present application is intended to cover any logical, electrical, or mechanical modifications, adaptations, or variations which fall within the scope of the following claims.