1. Field of the Invention
The invention relates to terrain navigation in respect of a mobile object subject to travel constraints varying over time, such as an aircraft limited in terms of rate of climb, the limit possibly being negative, and deploying above a terrain zone exhibiting threatening obstacles or reliefs close to or above its flight altitude.
2. Description of the Related Art
Diverse systems have been developed for forewarning the crew of an aircraft of a risk of collision with the ground. Some, such as the TAWS systems (the acronym standing for “Terrain Awareness and Warning System”), make a short-term trajectory forecast for the aircraft on the basis of flight information (position, heading, orientation and amplitude of the speed vector) provided by the onboard equipment, situate this forecast with respect to a map of the region overflown extracted from a terrain elevation database accessible on board and emit alarms destined for the crew of the aircraft whenever the short-term forecastable trajectory comes into collision with the ground. These TAWS systems supplement their alarms with rudimentary recommendations of the kind “Terrain Ahead, Pull up”. Some of them also give information about the level of risk of collision incurred due to the reliefs and the obstacles surrounding the aircraft in the form of a map presenting the reliefs or the obstacles of the terrain overflown as strata of different colors. However, this map of risks of collision with the environment takes account only of the altitudes of the relief relative to the position of the mobile object and does not take account of the existence or otherwise of a realistic trajectory making it possible to join up with the zones displayed.
To satisfy this requirement of ascertaining the points of the terrain overflown that remain accessible after a maneuver for avoiding a relief or an obstacle on the ground, the map of risk of collision with the environment must display only the zones for which there is a possible route from the current position of the mobile object. The realization of such a display involves the association of a metric with a relief map derived from a terrain elevation database.
A known procedure for associating a metric with a relief map derived from a terrain elevation database with regular meshing of the terrestrial surface or of a part of the latter, consists in considering the map presenting the relief on the basis of altitude values appearing, with the geographical coordinates, latitude and longitude of the measurement points, in the elements of the terrain elevation database as an image whose pixels are the altitude values of the points of the terrain elevation database that are illustrated in the map with, as abscissa and ordinate coordinates within the image, the latitude and longitude geographical coordinates of these points appearing in the elements of the terrain elevation database and in calling upon a distance transform operating by propagation to estimate distances within this image.
Distance transforms operating by propagation also known as “chamfer distance transforms” or “chamfer Euclidean distance transforms” deduce the distance of a pixel termed the goal pixel with respect to another pixel termed the source pixel, from the distances previously estimated for the pixels of its neighborhood, through a scan of the pixels of the image. The scan makes it possible to estimate the distance of a new goal pixel with respect to the source pixel by searching for the path of minimum length going from the new goal pixel to the source pixel passing through an intermediate pixel of its neighborhood whose distance has already been estimated, the distance of the new goal pixel to an intermediate pixel of its neighborhood whose distance has already been estimated being given by applying a neighborhood mask commonly called a chamfer mask.
A distance transform of this kind was proposed in 1986 by Gunilla Borgefors for estimating distances between objects in a digital image, in an article entitled: “Distance Transformation in Digital Images” and published in the journal “Computer Vision, Graphics and Image Processing”, Vol. 34 pp. 344-378. One of the interesting benefits of these propagation-based distance transforms is of reducing the complexity of the calculations of a distance estimate by permitting the use of integers.
To select the path of minimum length giving the distance estimate, a propagation-based distance transform must test all the possible paths. This obligation is manifested as a regularity constraint imposed on the order of scanning of the pixels of an image. G. Borgefors proposes, in order to satisfy this regularity constraint, that the pixels of an image be scanned twice consecutively, in two mutually inverse orders, which are either lexicographic order, the image being analyzed from left to right row by row and from top to bottom, and inverse lexicographic order, or transposed lexicographic order, the image having undergone a 90° rotation, and inverse transposed lexicographic order. She also proposes the adoption of a chamfer mask of dimensions 3×3 with two values (3, 4) of neighborhood distances or of dimensions 5×5 with three values (5, 7, 11) of neighborhood distances.
Distance transforms operating by propagation are already employed in the field of terrain navigation for robots. In this context, it is known to use the distance transform of G. Borgefors with a static constraint consisting in routinely allocating an infinite distance to a point under analysis when it is apparent that it belongs to reliefs or obstacles to be circumvented that are cataloged in a memory of prohibited crossing zones, so as to eliminate, from the set of the paths tested during a distance estimation, those passing through the reliefs or obstacles that the robot must circumvent. However, a distance transform operating by propagation used with a static constraint within the context of terrain navigation for robots, is not suitable for terrain navigation for aircraft for which the threat presented by a relief or an obstacle on the ground depends on the vertical profile of its trajectory.
USPTO Backgrounds
USPTO Backgrounds