Patent Document

BACKGROUND OF THE INVENTION 
       [0001]    The use of ranging sensors, such as radar or lidar, to provide real-time information about terrain and obstacles in front of a vehicle, such as a helicopter, is common, and much work has been done to improve the quality of the resultant three-dimensional maps. One approach is to use an evidence grid to accumulate the sensor data across both space and time. A probabilistic approach using an evidence grid was disclosed in U.S. patent application Ser. No. 12/051,801, filed Mar. 19, 2008, the contents of which are hereby incorporated by reference. However, the sensor data that is available from the on-board sensors is usually limited in its coverage by a restricted field of view, limited by obscurants such as dust, limited by shadowing, and often limited by simple lack of time on target. Consequently, the resultant three-dimensional maps have lower resolution than is desired and areas lacking in data. 
         [0002]    Another solution is to use high-resolution a priori data of the target area that is based on sensor measurements taken previously from a different platform, e.g., a UAV. These data can have very high resolution (10 cm accuracy), and contain much information that would be beneficial if it were displayed to the pilot. However, these data cannot be used in place of the real-time sensor data for two reasons. First, the a priori data is old, and may not represent the current start of the target area. Buildings may have been erected (or removed), or vehicles that were present when the a priori data was taken may have been moved. Displaying the old, out-of-date a priori data without correcting for these temporal changes is dangerous. The second problem is that the navigation system of the helicopter has errors, so that the display of the a priori data may not correspond to the current position of the helicopter. This is particularly a problem when flying close to the ground, since the navigation error associated with the altitude is typically much larger than other navigation errors. 
       SUMMARY OF THE INVENTION 
       [0003]    The present invention provides systems and method for improving the presentation of sensed data (e.g., radar) by including a priori data. The a priori data is recast as if it were the output of a virtual sensor. This allows the inclusion of the a priori data into an evidence grid that is combined with data from multiple types of sensors. Before the sensor data is combined into the evidence grid, the sensor data is aligned with the a priori data using an optimization algorithm. 
         [0004]    In one aspect of the invention, the optimization algorithm provides an optimum probability of a match between the sensor data and the a priori data by adjusting the position or attitude associated with the sensor device. This removes any navigational errors associated with the sensor device data. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0005]    Preferred and alternative embodiments of the present invention are described in detail below with reference to the following drawings: 
           [0006]      FIG. 1  is a block diagram of an exemplary system formed in accordance with an embodiment of the present invention; and 
           [0007]      FIG. 2  is a flow diagram of an exemplary process performed by the system shown in  FIG. 1 . 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0008]      FIG. 1  illustrates a system  20  that accurately combines real-time sensor data (e.g., radar, lidar, sonar) with a priori data (e.g., terrain, either exposed or submerged) to provide an accurate up-to-date image of the ground and obstacles for a vehicle. This is of particular benefit to a low flying aircraft, such as a helicopter. Other land-, sea-, or air-based vehicles may also benefit from the system  20 . 
         [0009]    The system  20  includes a processing device  24  that is in signal communication with a sensor device  26 , such as a radar, lidar or combination thereof, and an output device  28 , such as a display device, and a data storage device  30 . The sensor device  26  is operable to transmit multiple simultaneous and/or sequential sensory (detection) signals. The output device  28  outputs (e.g., displays) a representation of the terrain and obstacles, as determined by the processing device  24 , based on data from the sensor device  26  and a priori data from the data storage device  30 . In one embodiment, the a priori data is terrain and obstacle data previously generated. An example of such a priori data is the terrain/obstacle database used in the Enhanced Ground Proximity Warning System (EGPWS) by Honeywell, Inc. 
         [0010]    A priori data is a collection of elevation values at an array of locations. Associated with the a priori data is an uncertainty value that is based on the uncertainties associated with the original sensors and navigation system used to obtain the a priori data. The a priori data can be viewed as being the output of a virtual zero-beamwidth laser rangefinder located at a very high altitude and pointing straight down. Viewed in this way, the a priori data is considered the output from a (virtual) sensor and is put into an evidence grid (e.g., a three-dimensional grid with cells) together with real-time sensor data. Using the evidence grid(s), the processing device  24  resolves conflicts between the real-time sensor data and the a priori data by determining the most probable arrangement of occupied cells after the position and the attitude associated with the real-time sensor data are adjusted. 
         [0011]    The a priori data is prepopulated into the evidence grid, and then, assuming that the a priori data is correct, the probability β that the real-time sensor measurements match the a priori data is calculated. This calculation follows the discussion below (paragraph [0019] and following), but with the a priori data placed in the various cells of the evidence grid, and with β calculated as a function of the sensor position and attitude. The sensor position at the maximum of β is the most likely position based on the real-time data, thus giving the optimum registration between the real-time sensor data and the a priori data. The calculation of the maximum of β as a function of the navigation errors provides not only the corrections to the navigation, but also a covariance matrix describing the sensitivity of the corrections. The covariance matrix can be used to determine how trustworthy the corrections to the navigation data are, so that noisy data do not generate improper corrections. 
         [0012]    As shown in  FIG. 2 , a process  50  performed by the processing device  24  combines the a priori data with other sensor data to generate an optimized understanding of the terrain and obstacles. First, at a block  56 , a first evidence grid is populated with a priori data. The occupancies of the cells in the evidence grid are provided by the a priori data. Next, at a block  58 , data from the sensor device  26  is attained and sent to the processing device  24 . At a block  60 , the probability that the a priori data in the evidence grid would reflect the radar (or lidar) in the same manner that the real world did reflect the real radar is calculated. This calculation is a function of the position and attitude of the sensor and the sensor data. 
         [0013]    At a decision block  64 , the processing device  24  determines if the calculated probability has reached a predefined threshold or a predefined number of iterations have occurred. In another embodiment, a first derivative of the probability with respect to position is less than a predefined threshold, indicating that the probability is at or near a local maximum as a function of position. If the condition of decision block  64  is not true, then at a block  68 , the position and/or attitude of the sensor device  26  is adjusted and the process  50  returns to block  60  to perform the probability calculation based on the new position and/or attitude information. 
         [0014]    If the condition of decision block  64  is true, then the calculated probability is determined to be maximized. An exemplary maximization process is performed by an optimization algorithm by applying an incremental change to the position and/or attitude values (i.e., pointing direction of the sensor device  26 ) and recalculating the probability based on the changed value(s). Blocks  64 - 70  are an example of an unspecified optimization scheme. Other optimization schemes may be used. 
         [0015]    Then, at a block  70  the position and/or attitude of the sensor device  26  are corrected to values when the probability has been maximized. At a block  74 , a second evidence grid is constructed using the a priori data, as if it had been generated by a virtual sensor, and data from the sensor device  26  using the corrected position. Since the a priori data includes the elevation of the terrain at given locations, with an associated uncertainty, the virtual sensor can be taken to be a lidar with zero-beamwidth at a very high elevation and a measurement uncertainty equal to that of the a priori data. Once the a priori data is considered to be the output of this virtual sensor, the combination of the a priori data with the real-time sensor data follows the description in U.S. patent application Ser. No. 12/051,801. Only the a priori data and the sensor data are used to generate the second evidence grid during the first pass through the process  50 . Upon subsequent passes through the process  50 , the previously updated second evidence grid is used at the step of block  74 . The constructed second evidence grid is then used to generate an output, such as an image, for presentation on the output device  28 . 
         [0016]    The optimization steps performed at blocks  60 - 68  align or register the a priori data with the real-time sensor data. The step at block  74  determines if there are any changes between the a priori data and the current state of the scene as measured by the real-time sensor  26 . 
         [0017]    In one embodiment, if the sensor data (i.e., radar data) arrives at a rate of 10 Hz, the optimization steps (blocks  64 - 70 ) are performed once a second, and the step at block  74  is performed the other nine times a second. This saves considerable computational effort. Other update frequencies/strategies may be used. 
         [0018]    The following describes an exemplary process performed at the step  74  shown in  FIG. 2 . 
         [0019]    The evidence grid at its most basic is just a collection of points, and a measure of occupancy at each of these points. Typically, the collection of points forms a uniform grid in three-dimensions, but the uniformity is not required. The measure of occupancy of a cell can be interpreted as the probability that the cell is occupied. A question addressed herein is how to arrange the occupancies of the cells in the evidence grid so as to match as well as possible the measurements corresponding to the sensed environment. 
         [0020]    An approach includes asking the related question: given an evidence grid, with probabilities of occupancy assumed for each cell, what is the probability that a (model) sensor measurement of the evidence grid matches the real-time sensor measurement? If we can make that calculation as a function of the occupancies of the cells, then we can turn the problem of how to fill out the occupancies of the cells in the evidence grid into a related optimization problem, to find the occupancies of the cells that maximize the probability that (modeled) measurements of the evidence grid match the (actual) measurements of the real world. 
         [0021]    p 11  is the probability that a volume in space represented by an occupied evidence grid cell reflects a sensor beam, and can, but need not, make the assumption that this probability is independent both of the distance from the sensor device  26  (up to the maximum range of the sensor device  26 ), and of the angle from the central axis of the sensor device  26  (up to the angular width of the beam). 
         [0022]    Similarly, p 00  is the probability that a volume in space represented by an unoccupied cell does not reflect the sensor beam. From these, the probability that a volume in space represented by an unoccupied cell reflects the sensor beam (a false positive response from the sensor) as p 10 =1−p 00  is obtained, and also the probability that a volume in space represented by an occupied cell does not reflect the beam (a false negative response) as p 01 =1−p 11 . 
         [0023]    The probability that a theoretical sensor measurement of an evidence grid is the same as a measurement of the actual sensed environment can be calculated as follows: 
         [0024]    First, the probability that a single cell makes a reflection is considered. Letting ρ i  be the probability that the ith cell in the evidence grid is occupied, then the probability that the ith cell produces a reflection is: 
         [0000]      ρ i   =p   11 ρ i   +p   10 (1−ρ i )  (1)
 
         [0025]    and the probability that the ith cell does not produce a reflection is: 
         [0000]        i= 1 −p   i   =p   01 ρ i   +p   00 (1−ρ i )  (2)
 
         [0026]    For each range bin up to but not including the range bin within which an object is detected, the probability that there is no return is simply the probability that each of the cells in that range bin does not reflect the beam, which may be expressed as Π i i . For the range bin in which there was a detection, the probability that there is a reflection given the state of the evidence grid is obtained by calculating the probability that there was no detection and subtracting from 1, or 1−Π i i . This simply states that in order for the sensor to detect a reflection, at least one of the cells must have reflected the beam. These probability calculations can be done in this manner for the real-time sensor measurements as well as for the virtual sensor measurements which represent the a priori data. The net result for the probability that a single theoretical sensor measurement of the evidence grid matches the actual radar measurement of the sensed environment is thus 
         [0000]        P   k =Π ik ik [1−Π jk jk ]  (3)
 
         [0027]    where the subscript ik runs in the kth sensor beam over all of the cells lying in the range bin(s) closer to the sensor device  26  than the range bin in which there was an object detection, and the subscript jk runs in the kth radar beam over all of the cells lying in the range bin in which there was an object detection. Then, the processing device  24  can calculate the probability that all of the theoretical sensor measurements made on the evidence grid matches the actual measurements made by multiple beams including both the real-time sensor data transmitted by the sensor device  26  and the virtual sensor data representation of the a priori data as 
         [0000]      β=Π k   P   k   (4)
 
         [0028]    The goal is to find the occupancies ρ i  which maximize β. In so doing, the most likely occupancies are found, given both the measurements of the real-time sensor and the virtual measurements representing the a priori data. 
         [0029]    The product in Eq. (4) can be rearranged so that it is more transparent. In particular, we can examine the dependence of β on the occupancy of a single cell: 
         [0000]      β={Π k i Π k′ [1−Π j′k j′k ]}·[terms independent of ρ i   ]=P (ρ i )·[terms independent of ρ i ]  (5)
 
         [0030]    where the product k is over the sensor beams for which the ith cell is in the beam but from which there is no return in the corresponding range bin, and the product over k′ is over the sensor beams for which the ith cell is in the range bin for which there was a detection. This expression splits the dependence on ρ i  into two parts. The first part is a measure of how often the cell is not seen by a sensor beam. The second part is a measure of how well the current evidence grid supports the actual measured returns. 
         [0031]    A few observations about the result in Eq. (5) follow. First, if a cell never appears in a detected range bin, then the second product in Eq. (5) (over k′) is empty and the occupancy of the cell can be set to zero. In other words, if the cell is never in a detection range bin of any sensor beam, then its occupancy can be set to zero. Second, if the first product in Eq. (5) is empty, then the cell has never been in a sensor range bin with no detection. In this case, ρ i  can be set to 1. 
         [0032]    To solve for the optimum occupancies for those cells which cannot be trivially set to 0 or 1, one may examine more closely the quantity inside the braces in Eq. (5), P(ρ i ). An embodiment seeks the maximum of β with respect to the ρ i , subject to the constraint that 0≦ρ i ≦1 (since ρ i  is a probability of occupancy). 
         [0033]    The maximum of β is experienced when one of the following conditions is met for each cell (note that this optimization is a constrained optimization, since 0≦ρ i ≦1): 
         [0000]      ∂ P (ρ i )/∂ρ i =0, 0&lt;ρ i &lt;1
 
         [0000]      ∂ P (ρ i )/∂ρ i &lt;0, ρ i =1
 
         [0000]      ∂ P (ρ i )/∂ρ i &lt;0, ρ i =0  (6)
 
         [0034]    Solving these equations for the optimum point may be done in a conventional manner, such as using, for example, a steepest-descent method. Each of the calculations discussed above herein may be performed completely or partially by the processing device  24 . 
         [0035]    While the preferred embodiment of the invention has been illustrated and described, as noted above, many changes can be made without departing from the spirit and scope of the invention. Accordingly, the scope of the invention is not limited by the disclosure of the preferred embodiment. Instead, the invention should be determined entirely by reference to the claims that follow.

Technology Category: g