Brevet FR2861478A1 — publié le 20050429

PROCEDE DE DETERMINATION DES COEFFICIENTS OPTIMAUX D'UN MASQUE DE CHANFREIN POUR TRANSFORMEE DE DISTANCE L'invention est relative à l'estimation de distance euclidienne entre des points ou des objets d'une image isotrope ou non, avec une erreur relative bornée, par application d'une transformée de distance de chanfrein ("chamfer distance transform" ou "chamfer euclidiean distance transform" en anglo-saxon). Elle s'applique notamment à l'estimation de distances euclidiennes entre des points d'une image constituée d'une carte d'une portion de surface sphérique, telle que celle du globe terrestre, présentant une anisotropie due à la convergence des méridiens vers les pôles. Les transformées de distance de chanfrein sont largement utilisées dans l'analyse d'image. Gunilla Borgefors en décrit des exemples dans son article intitulé " Distance Transformation in Digital Images." Paru dans la revue: Computer Vision, Graphics and Image Processing, Vol. 34 pp. 344378 en février 1986. Les transformées de distance de chanfrein estiment, dans une image, la distance euclidienne séparant un pixel dit pixel but d'un autre pixel dit pixel source à partir de la longueur du trajet le plus court, allant du pixel source au pixel but en passant par des pixels de l'image, choisi parmi une sélection limitée des différents trajets possibles qui ne prend en compte que les trajets passant par des points proches voisins du point but et empruntant, sur leurs parties allant du point source à un point proche voisin, le trajet le plus court déterminé au cours d'estimations de distance effectuées antérieurement. Pour réaliser la sélection limitée des trajets servant à établir une estimation de distance d'un point but, les transformées de distance de chanfrein analysent, tour à tour, tous les pixels d'une image, au cours d'un balayage complet de l'image. Pour que la sélection de trajets effectuée pour chaque pixel de l'image renferme à coup sûr un trajet de longueur minimale, le balayage doit satisfaire une contrainte de régularité. G. Borgefors propose, pour satisfaire cette contrainte de régularité, de balayer les pixels d'une image deux fois consécutivement, dans deux ordres inverses l'un de l'autre, qui sont soit l'ordre lexicographique, l'image étant analysée de haut en bas, ligne par ligne et de gauche à droite au sein de chaque ligne, et l'ordre lexicographique inverse, soit l'ordre lexicographique transposé, l'image ayant subi une rotation de 90 , et l'ordre lexicographique transposé inverse. L'analyse d'un pixel se fait au moyen d'un masque de chanfrein répertoriant les distances séparant le pixel en analyse des pixels les plus proches dans les différentes directions, le maillage des pixels de l'image étant supposé régulier. Elle consiste à sélectionner les pixels du proche voisinage qui, d'une part ont déjà reçu une estimation de distance au cours de la même passe de balayage et qui, d'autre part ont leurs distances au pixel en analyse mentionnées dans le masque de chanfrein, à répertorier les trajets allant, au plus court, du pixel source au pixel en analyse en passant par les différents pixels sélectionnés du proche voisinage, à estimer les longueurs de chacun de ces trajets par sommation de la distances estimée pour le pixel du proche voisinage emprunté par le trajet considéré et de la distance de ce même pixel du proche voisinage au pixel en analyse, et à assimiler la distance du pixel en analyse à la plus courte longueur des trajets répertoriés. Les transformées de distance de chanfrein ont divers intérêts dont les principaux sont: une réduction de la complexité des calculs d'une estimation de distance euclidienne grâce à un emploi exclusif de nombres entiers fait au prix d'approximations et une complexité de calcul qui, tout en étant moindre, reste constante et n'augmente pas avec la présence d'obstacles dans l'image contrairement à la complexité du calcul classique de distance euclidienne classique qui croît avec la présence d'obstacles dans l'image. Les valeurs de distance adoptées pour coefficients du masque de chanfrein sont en effet exprimées à l'aide de nombres entiers qui correspondent, à un facteur multiplicatif d'échelle et à une approximation près, aux distances euclidiennes séparant le pixel en analyse de ses proches voisins. Dans les exemples proposés par G. Borgefors, pour une image dont les pixels ont une répartition isotrope, le masque de chanfrein est de dimensions 3x3 ou 5x5. Lorsqu'il est de dimensions 3x3, le masque de chanfrein renferme deux valeurs entières de coefficients: 3 pour la plus courte des distances de voisinage qui correspond à la distance des pixels les plus proches sur la même ligne et la même colonne que le pixel en analyse et qui sert de facteur multiplicatif d'échelle et d'unité de mesure de distance, et 4 pour une deuxième distance de voisinage correspondant à celle des pixels les plus proches sur les diagonales, la valeur 4 approximant la distance euclidienne vraie qui est 3-). Lorsqu'il est de dimension 5X5, le masque de chanfrein renferme trois valeurs entières de coefficients: 5 pour la première distance de voisinage et le facteur multiplicatif d'échelle, 7 au lieu de 5-N/i,pour la deuxième distance de voisinage et 11 au lieu de 5J pour une troisième distance de voisinage. Le choix des valeurs entières des coefficients du masque de chanfrein est illimité et se fait en adoptant un facteur multiplicatif arbitraire puis en prenant pour coefficients, les valeurs entières se rapprochant le plus des produits par le facteur multiplicatif, des distances euclidiennes de voisinage. Les erreurs faites sur les estimations de distance au moyen de transformées de distance de chanfrein sont liées aux approximations sur les différentes distances de voisinage faites dans les coefficients du masque de chanfrein. Leurs réductions passent par un choix optimum de la combinaison des différentes approximations faites dans les coefficients du masque de chanfrein sur les distances de voisinage. Elles peuvent aussi être réduites par une augmentation du facteur multiplicatif d'échelle mais cette augmentation du facteur multiplicatif conduit à une augmentation de toutes les valeurs entières adoptées pour les coefficients du masque de chanfrein qui se reporte sur la complexité des calculs des estimations de distance. II se pose alors le problème de choisir, pour les coefficients du masque de chanfrein, les plus petites valeurs entières possibles permettant d'obtenir la précision voulue dans les estimations des distances, cela afin de réduire le plus possible la complexité des calculs. Le problème du choix des coefficients optimaux du masque de chanfrein est rendu difficile par le très grand nombre de possibilités offertes pour un même facteur multiplicatif d'échelle dès que le masque de chanfrein dépasse une certaine taille, la valeur entière choisie pour chaque coefficient pouvant être soit une approximation par défaut, soit une approximation par excès, de la distance euclidienne du pixel voisin concerné. Ce problème devient encore plus critique lorsque le choix n'est valable que sur une partie de l'image en raison d'un phénomène d'anisotropie comme c'est le cas, par exemple d'une image formée par une carte d'une portion de la surface du globe terrestre tirée d'une base de données d'élévation du terrain faite à partir d'un maillage régulier en latitude et longitude. La méthode naturelle pour choisir, de manière optimale, les coefficients du masque de chanfrein consiste à tester toutes les possibilités pour un facteur multiplicatif d'échelle donné, en calculant, pour chaque possibilité, les erreurs commises sur des estimations de distance faites à pour tous les pixels de l'image par rapport à un pixel source, et à retenir la possibilité correspondant au taux minimum d'erreur. Cette méthode, qui s'apparente aux méthodes dites "brute force" en anglo-saxon, réclame une quantité considérable de calcul surtout dans les cas où aucune des possibilités testées ne permet d'atteindre la précision recherchée dans les mesures de distance et où l'on est obliger d'augmenter le facteur multiplicatif d'échelle et de recommencer les tests sur les nouvelles possibilités offertes après augmentation du facteur multiplicatif d'échelle. Différents procédés ont été proposés pour choisir les coefficients d'un masque de chanfrein de manière optimale à un moindre coût de calcul que la méthode naturelle. La plupart d'entre eux permettent de déterminer les coefficients du masque de chanfrein à partir d'un facteur multiplicatif d'échelle choisi arbitrairement en cherchant à diminuer l'écart de surface existant entre le disque euclidien et un polygone convexe dit "polygone du chanfrein" dont les distances des sommets au centre correspondent aux valeurs des coefficients du masque de chanfrein. Ces procédés deviennent cependant rapidement délicats à mettre en oeuvre lorsque le disque euclidien est déformé par une anisotropie de l'image. L'invention a pour but la détermination des coefficients optimaux d'un masque de chanfrein, dans le cadre d'une image pouvant être anisotrope, à un coût de calcul moindre que la méthode naturelle. Elle a également pour but une détermination des coefficients optimaux d'un filtre de chanfrein permettant un calcul exact des erreurs commises sur les estimations de distances. Elle a aussi pour but un calcul direct des coefficients entiers optimaux d'un masque de chanfrein. Elle a également pour but le calcul des coefficients optimaux d'un masque de chanfrein correspondant à un facteur multiplicatif d'échelle donné. Elle a pour objet un procédé de détermination des coefficients optimaux C; ,i, i étant un indice ligne variant de P à +P et j un indice colonne variant de Q à +Q, P et Q étant des nombres entiers positifs, d'un masque de chanfrein de transformée de distance fournissant des estimations de distance entre pixels d'une image, lesdits coefficients étant des 1 o approximations, à un facteur multiplicatif d'échelle n près, n étant un nombre entier positif, des distances d'un pixel de l'image soumis à l'analyse du masque de chanfrein par rapport aux pixels de l'image les plus proches dans les différentes directions dits pixels du masque, chaque coefficient étant associé au pixel du masque dont il représente la distance, et la détermination consistant en un choix, pour chaque coefficient, d'une valeur sélectionnée parmi un ensemble de valeurs candidates pour le coefficient considéré. Ce procédé est remarquable en ce qu'il utilise, comme critères de choix: le taux maximum d'erreur d'estimation distance entraîné par le choix d'une valeur candidate pour un coefficient, sur les estimations de distances des pixels de l'image alignés sur un axe de déplacement de l'image correspondant à la direction allant d'un pixel source origine des mesures de distance soumis à l'analyse du masque de chanfrein au pixel du masque associé au coefficient considéré, et le taux maximum d'erreur d'estimation distance entraîné par le choix de deux valeurs candidates pour un couple de coefficients, sur les estimations distance des pixels de l'image contenus dans un secteur angulaire de l'image, délimité par deux axes de déplacement de l'image correspondant aux directions allant du pixel source soumis à l'analyse du masque de chanfrein aux deux pixels du masque associés aux coefficients considérés. Avantageusement, lorsqu'un taux maximum d'erreur x% est imposé, le procédé de détermination des coefficients optimaux d'un masque de chanfrein comporte les étapes suivantes: - calcul, en fonction du facteur multiplicatif d'échelle n, des couples A1,i de valeurs entières correspondant aux approximations par défaut et par excès de chacune des distances des pixels du masque par rapport au pixel soumis à l'analyse du masque, les valeurs entières d'un couple A1,j étant candidates pour le coefficient C;,i du masque de chanfrein affecté au pixel du masque dont elles sont une approximation de la distance, adoption d'un pixel de l'image comme pixel source origine des mesures de distance, calcul, pour chaque valeur entière candidate pour un coefficient, du taux d'erreur d'estimation distance pour des pixel de l'image alignés sur un axe de déplacement de l'image correspondant à la direction allant d'un pixel source origine des mesures de distance soumis à l'analyse du masque de chanfrein au pixel du masque associé au coefficient considéré, premier tri parmi les valeurs entières candidates consistant à éliminer celles pour lequel le taux d'erreur sur axe dépasse le taux maximum d'erreur x% admissible, arrêt de la détermination des coefficients du masque de chanfrein dès que les deux valeurs entières de l'un des 25 couples Au sont éliminées, - si tous les couples AiJ initiaux conservent au moins une valeur entière après le premier tri, poursuite de la détermination des coefficients du masque par le partage du masque de chanfrein et de l'image en 2(P+Q) secteurs angulaires Sk orientés contiguës les uns des autres ayant pour sommet, le pixel en analyse et, pour côtés, des axes de déplacement de l'image correspondant à la direction allant du pixel source soumis à l'analyse du masque de chanfrein à un pixel du masque, et n'englobant aucun autre pixel du masque, calcul, pour chaque secteur angulaire Sk et pour chaque binôme de valeurs entières candidates pour les deux coefficients associés aux deux pixels du masque placés sur les côtés du secteur angulaire Sk considéré, du taux d'erreur d'estimation de distance pour des pixels de l'image appartenant au secteur Sk considéré, deuxième tri parmi les binômes de valeurs entières candidates pour deux coefficients associés à deux pixels du masque placés sur les côtés d'un secteur angulaire Sk consistant à rejeter ceux pour lesquels le taux d'erreur sur axe dépasse le taux maximum d'erreur admissible x%, construction, à partir des binômes de valeurs entières issus du deuxième tri, d'une combinaison de valeurs entières candidates pour chacun des coefficients du masque de chanfrein, test du résultat de la construction, si aucune combinaison n'a pu être construite arrêt de la détermination des coefficients du masque de chanfrein, si au moins une combinaison a pu être construite, adoption de 20 l'une d'elles pour les coefficients du masque de chanfrein. Avantageusement, le procédé précédent est complété par une étape de vérification du respect des conditions de U. Montanari par la combinaison choisie. Avantageusement, la construction, à partir des binômes de valeurs entières issus du deuxième tri, d'une combinaison de valeurs entières candidates pour chacun des coefficients du masque de chanfrein se fait progressivement, en prenant les coefficients dans l'ordre des secteurs angulaires. Avantageusement, le procédé précédent de détermination des coefficients optimaux C1J d'un masque de chanfrein est réitéré avec une augmentation du facteur multiplicatif d'échelle ou du taux maximum d'erreur 15 20 25 30 x% imposé à chaque fois qu'il aboutit à un échec, soit à la suite du premier tri, soit à la suite du deuxième tri. Avantageusement, le procédé de détermination des coefficients optimaux d'un masque de chanfrein comporte les étapes suivantes: - calcul, en fonction du facteur multiplicatif d'échelle n, des couples A; J de valeurs entières correspondant aux approximations par défaut et par excès de chacune des distances euclidiennes des pixels du masque par rapport au pixel soumis à l'analyse du masque, les valeurs entières d'un couple A;,i étant éligibles pour le coefficient C;,1 du masque de chanfrein affecté au pixel du masque dont elles sont une approximation de la distance, adoption d'un pixel de l'image comme pixel source origine des mesures de distance, - calcul, pour chaque valeur entière candidate pour un coefficient, du taux d'erreur d'estimation distance pour des pixel de l'image alignés sur un axe de déplacement de l'image correspondant à la direction allant d'un pixel source origine des mesures de distance soumis à l'analyse du masque de chanfrein au pixel du masque associé au coefficient considéré, affectation à chaque valeur entière candidate, en tant que notation, du taux d'erreur sur axe qui lui correspond, calcul, pour chaque secteur angulaire Sk et pour chaque binôme de valeurs entières candidates pour les deux coefficients associés aux deux pixels du masque placés sur les côtés du secteur angulaire Sk considéré, du taux d'erreur d'estimation de distance pour des pixels de l'image appartenant au secteur Sk considéré, affectation, à chaque binôme de valeurs entières candidates ayant servi au calcul d'un taux d'erreur sur secteur, d'une notation constituée de la valeur la plus élevée du taux d'erreur secteur qui lui correspond et des taux d'erreur sur axe associés aux valeurs entières candidates qui le composent, et construction d'une combinaison de valeurs entières candidates pour chacun des coefficients du masque de chanfrein, à partir des binômes de valeurs entières ayant les plus faibles notations possibles, Avantageusement, le procédé précédent est complété par une étape de vérification du respect des conditions de U. Montanari par la combinaison choisie. Avantageusement, la construction, à partir des binômes de valeurs entières, d'une combinaison de valeurs entière candidates pour chacun des coefficients du masque de chanfrein se fait progressivement, en prenant les coefficients dans l'ordre des secteurs angulaires. Avantageusement, le procédé de détermination des coefficients optimaux est appliqué aux masques de chanfrein utilisés pour l'estimation des distances, par rapport à un mobile, des points d'une zone de la surface terrestre où il évolue, lorsque cette zone est représentée par une carte en deux dimensions, tirée d'une base de données d'élévation du terrain réalisée à partir d'un maillage régulier en latitude et longitude de la surface terrestre. D'autres caractéristiques et avantages de l'invention ressortiront de la description ci-après d'un mode de réalisation donné à titre d'exemple. Cette description sera faite en regard du dessin dans lequel: une figure 1 représente un exemple de masque de chanfrein, des figures 2a et 2b montrent les cellules du masque de chanfrein illustré à la figure 1, qui sont utilisées dans une passe de balayage selon l'ordre lexicographique et dans une passe de balayage selon l'ordre lexicographique inverse, - une figure 3 montre la déformation d'un masque de chanfrein occasionnée par l'anisotropie d'une image ayant des pixels espacés différemment dans la direction des lignes et dans la direction des colonnes, une figure 4 est un diagramme illustrant les axes de déplacement associés aux coefficients du quart supérieur droit du masque de chanfrein montré à la figure 1, des figures 5a et 5b sont des diagrammes montrant des trajets de longueur minimale pour des pixels but placés dans l'image, sur un axe de déplacement ou dans un secteur, - une figure 6 est un diagramme montrant que des pixels but alignés sont reliés à un pixel source par des trajets homothétique de longueurs minimales, une figure 7 est un diagramme illustrant les principales étapes d'un procédé, conforme à l'invention, de détermination des coefficients optimaux d'un masque de chanfrein, - une figure 8 est un diagramme illustrant les principales étapes d'un autre procédé, conforme à l'invention, de détermination des coefficients optimaux d'un masque de chanfrein, et une figure 9 est un diagramme détaillant des étapes du procédé illustré à la figure 7. La distance d'entre deux points d'une surface est la longueur minimale de tous les parcours possibles sur la surface partant de l'un des points et aboutissant à l'autre. Dans une image formée de pixels répartis selon un maillage régulier de lignes, colonnes et diagonales, une transformée de distance par propagation estime la distance d'un pixel dit pixel "but" par rapport à un pixel dit pixel "source" en construisant progressivement, en partant du pixel source, le plus court trajet possible suivant le maillage des pixels et aboutissant au pixel but, et en s'aidant des distances trouvées pour les pixels de l'image déjà analysés et d'un tableau dit masque de chanfrein répertoriant les valeurs des distances entre un pixel et ses proches voisins. Comme montré à la figure 1, un masque de chanfrein se présente sous la forme d'un tableau avec une disposition de cases reproduisant le motif d'un pixel entouré de ses proches voisins. Au centre du motif, une case affectée de la valeur 0 repère le pixel pris pour origine des distances répertoriées dans le tableau. Autour de cette case centrale, s'agglomèrent des cases périphériques remplies de valeurs de distance de proximité non 15 nulles et reprenant la disposition des pixels du voisinage d'un pixel supposé occuper la case centrale. La valeur de distance de proximité figurant dans une case périphérique est celle de la distance séparant un pixel occupant la position de la case périphérique concernée, d'un pixel occupant la position de la case centrale. On remarque que les valeurs de distance de proximité se répartissent en cercles concentriques. Un premier cercle de quatre cases correspondant aux quatre pixels de premier rang, qui sont les plus proches du pixel de la case centrale, soit sur la même ligne, soit sur la même colonne, sont affectées d'une valeur de distance de proximité Dl. Un deuxième cercle de quatre cases correspondant aux quatre pixels de deuxième rang, qui sont pixels les plus proches du pixel de la case centrale placés sur les diagonales, sont affectées d'une valeur de distance de proximité D2. Un troisième cercle de huit cases correspondant aux huit pixels de troisième rang, qui sont les plus proches du pixel de la case centrale tout en restant en dehors de la ligne, de la colonne et des diagonales occupées par le pixel de la case centrale, sont affectées d'une valeur de distance de proximité D3. Le masque de chanfrein peut couvrir un voisinage plus ou moins étendu du pixel de la case centrale en répertoriant les valeurs des distances de proximité d'un nombre plus ou moins important de cercles concentriques de pixels du voisinage. II peut être réduit aux deux premiers cercles formés par les pixels du voisinage d'un pixel occupant la case centrale ou être étendu au-delà des trois premiers cercles formés par les pixels du voisinage du pixel de la case centrale mais il est habituel de s'arrêter à trois premiers cercles. Les valeurs des distances de proximité D1, D2, D3 qui correspondent à des distances euclidiennes sont exprimées dans une échelle dont le facteur multiplicatif autorise l'emploi de nombres entiers au prix d'une certaine approximation. C'est ainsi que G. Borgefors adopte une échelle correspondant à un facteur multiplicatif 5. Elle donne à la distance Dl correspondant à un échelon en abscisse x ou en ordonnée y la valeur 5, à la distance D2 correspondant à la racine de la somme des carrés des échelons en abscisse et ordonnée jx2 + y2 la valeur 7 qui est une approximation de 5, et à la distance D3 la valeur 11 qui est une approximation de 5.f≈. La construction progressive du plus court trajet possible allant à un pixel but, en partant d'un pixel source et en suivant le maillage des pixels 2861478 12 se fait par un balayage régulier des pixels de l'image au moyen du masque de chanfrein. Initialement, les pixels de l'image se voient affecter une valeur de distance infinie, en fait un nombre suffisamment élevé pour dépasser toutes les valeurs des distances mesurables dans l'image, à l'exception du pixel source qui se voit affecter une valeur de distance nulle. Puis les valeurs initiales de distance affectées aux points but sont mises à jour au cours du balayage de l'image par le masque de chanfrein, une mise à jour consistant à remplacer une valeur de distance attribuée à un point but, par une nouvelle valeur moindre résultant d'une estimation de distance faite à l'occasion d'une nouvelle application du masque de chanfrein au point but considéré. Une estimation de distance par application du masque de chanfrein à un pixel but consiste à répertorier tous les trajets allant de ce pixel but au pixel source et passant par un pixel du voisinage du pixel but dont la distance a déjà été estimée au cours du même balayage, à rechercher parmi les trajets répertoriés, le ou les trajets les plus courts et à adopter la longueur du ou des trajets les plus courts comme estimation de distance. Cela se fait en plaçant le pixel but dont on veut estimer la distance dans la case centrale du masque de chanfrein, en sélectionnant les cases périphériques du masque de chanfrein correspondant à des pixels du voisinage dont la distance vient d'être mise à jour, en calculant les longueurs des trajets les plus courts reliant le pixel but à mettre à jour au pixel source en passant par un des pixels sélectionnés du voisinage, par addition de la valeur de distance affectée au pixel du voisinage concerné et de la valeur de distance de proximité donnée par le masque de chanfrein, et à adopter, comme estimation de distance, le minimum des valeurs de longueur de trajet obtenues et de l'ancienne valeur de distance affectée au pixel en cours d'analyse. L'ordre de balayage des pixels de l'image influe sur la fiabilité des estimations de distance et de leurs mises à jour car les trajets pris en compte en dépendent. En fait, il est soumis à une contrainte de régularité qui fait que si les pixels de l'image sont repérés selon l'ordre lexicographique (pixels classés dans un ordre croissant ligne par ligne en partant du haut de l'image et en progressant vers le bas de l'image, et de gauche à droite au sein d'une ligne), et si un pixel p a été analysé avant un pixel q alors un pixel p+x doit être analysé avant le pixel q+x. Les ordres lexicographique, lexicographique inverse (balayage des pixels de l'image ligne par ligne de bas en haut et, au sein d'une ligne, de droite à gauche), lexicographique transposé (balayage des pixels de l'image colonne par colonne de gauche à droite et, au sein d'une colonne, de haut en bas), lexicographique transposé inverse (balayage des pixels par colonnes de droite à gauche et au sein d'une colonne de bas en haut) satisfont cette condition de régularité et plus généralement tous les balayages dans lesquels les lignes et colonnes sont balayées de droite à gauche ou de gauche à droite. G. Borgefors préconise un double balayage des pixels de l'image, une fois dans l'ordre lexicographique et une autre dans io l'ordre lexicographique inverse. La figure 2a montre, dans le cas d'une passe de balayage selon l'ordre lexicographique allant du coin supérieur gauche au coin inférieur droit de l'image, les cases du masque de chanfrein de la figure 1 utilisées pour répertorier les trajets allant d'un pixel but placé sur la case centrale (case indexée par 0) au pixel source en passant par un pixel du voisinage dont la distance a déjà fait l'objet d'une estimation au cours du même balayage. Ces cases sont au nombre de huit, disposées dans la partie supérieure gauche du masque de chanfrein. Il y a donc huit trajets répertoriés pour la recherche du plus court dont la longueur est prise pour estimation de la distance. La figure 2b montre, dans le cas d'une passe de balayage selon l'ordre lexicographique inverse allant du coin inférieur droit au coin supérieur gauche de l'image, les cases du masque de chanfrein de la figure 1 utilisées pour répertorier les trajets allant d'un pixel but placé sur la case centrale (case indexée par 0) au pixel source en passant par un pixel du voisinage dont la distance a déjà fait l'objet d'une estimation au cours du même balayage. Ces cases sont complémentaires de celles de lafigure 2a. Elles sont également au nombre de huit mais disposées dans la partie inférieure droite du masque de chanfrein. Il y a donc encore huit trajets répertoriés pour la recherche du plus court dont la longueur est prise pour estimation de la distance. La figure 3 montre la déformation de la géométrie d'un masque de chanfrein occasionnée par l'anisotropie d'une image ayant des pixels espacés différemment dans la direction des lignes et dans la direction des colonnes. Le fait que l'intervalle entre deux pixels successifs selon une colonne soit dans un rapport r, différent de l'unité, avec l'intervalle entre deux pixels successifs selon une ligne, provoque une déformation en ellipses des cercles concentriques que formaient au préalable les pixels du voisinage de premier, deuxième et troisième rangs. Cette déformation rend les distances de voisinage répertoriées dans le masque de chanfrein dépendantes non seulement du rang mais également de l'orientation du pixel de voisinage concerné dans la constellation formée par l'ensemble des pixels de voisinage répertoriés. Ainsi, parmi les quatre pixels voisins de premier rang, deux situés de part et d'autre du pixel but placé sur la case centrale (case indexée par 0) sont à la distance unitaire 1, les deux autres également situés de part io et d'autre du pixel placé sur la case centrale mais sur la même colonne sont à la distance r. Les quatre pixels de deuxième rang sont à une même distance - Ir' +1 car l'anisotropie considérée conserve les symétries du maillage de pixels de l'image selon les lignes, colonnes et diagonales. Les huit pixels voisins de troisième rang se partagent en deux groupes de quatre, l'un des groupes étant à une distance V4r2 +1 et l'autre groupe à une distance de,Jr2 +4. On en retient donc que l'anisotropie peut modifier la géométrie de la constellation formée par les pixels du voisinage d'un point but et couverte par le masque de chanfrein au point d'affecter aux cases du masque de chanfrein des valeurs de distances de proximité toutes différentes les une des autres. Pour un facteur multiplicatif d'échelle donné, on dispose, pour le choix de chaque coefficient du masque de chanfrein, de deux valeurs entières candidates: la valeur entière la plus proche par défaut et la valeur entière la plus proche par excès du produit du facteur multiplicatif par la distance euclidienne de proximité représentée par le coefficient considéré. Cela donne rapidement de nombreuses possibilités de choix. Le problème se pose alors du choix optimum des valeurs entières des coefficients du masque de chanfrein, optimum dans le sens où il minimalise le taux d'erreur sur les estimations de distance des pixels de l'image. En outre, lorsque l'on s'impose un taux maximum d'erreur x% sur les estimations de distance des pixels d'une image, il est intéressant, pour limiter le plus possible la puissance de calcul nécessaire aux estimations de distance, de rechercher pour les coefficients du masque de chanfrein la combinaison des valeurs entières les plus petites possibles permettant de satisfaire le taux maximum d'erreur x% imposé. En effet, une solution pour parvenir à satisfaire un taux maximum d'erreur x% imposé, consiste à augmenter le facteur multiplicatif d'échelle car plus le facteur multiplicatif d'échelle adoptée est grand, plus les approximations par valeurs entières sont précises et moins les erreurs faites sur les estimations de distances sont élevées. Mais la contrepartie d'un facteur multiplicatif d'échelle élevé est une complexité de calcul accrue due à la manipulation de grandes valeurs entières. La recherche de la combinaison optimale de valeurs entières pour les coefficients d'un filtre de chanfrein, soit pour minimiser le taux d'erreur, soit pour respecter un taux maximum d'erreur x% imposé est donc délicate surtout si l'on considère que l'on peut être amené à reconsidérer le choix du facteur multiplicatif d'échelle, si après avoir tester l'ensemble des combinaisons, aucune ne convient. Pour éviter d'avoir à tester toutes les combinaisons, il y a plusieurs 15 approches possibles. Une première approche consiste à adopter pour coefficients les valeurs entières par défaut car l'on peut montrer que plus les coefficients choisis dans les directions des pixels voisins sont exacts, plus les estimations de distance entre les axes sont surévaluées. Cette approche n'est pas satisfaisante, car l'erreur commise n'est pas maîtrisée lorsque le rapport r des espacements des pixels en hauteur et en largeur de l'image varie. En effet, lorsque r varie de 0,2 à 1, l'erreur atteint 20% pour les rapports les plus faibles. Une deuxième approche consiste à ne tester que les combinaisons vérifiant les conditions de U. Montanari qui exprime le fait que la distance en ligne droite doit être la plus courte. Ces conditions de U. Montanari portent sur deux coefficients a et b du masque de chanfrein affectés à deux pixels connexes du voisinage. L'un a doit être positif tandis que l'autre b doit être compris entre a et 2a. La démarche reste coûteuse en temps de calcul pour les rapports r petits car le temps de calcul est une fonction exponentielle de la précision souhaitée pour les estimations de distance. Une troisième approche décrite ci-après, consiste à procéder par sélection progressive des valeurs entières candidates pour les coefficients d'un masque de chanfrein avec, en cas d'insuccès ou de sélection insuffisante, un éventuel rebouclage après modification du facteur multiplicatif d'échelle ou du taux maximum d'erreur x% imposé. Pour faciliter la compréhension de cette troisième approche par sélection progressive, on se sert, comme montré à la figure 4, d'axes de déplacement sur l'image, correspondant aux distances orientées séparant du pixel source, les pixels de son voisinage couverts par le masque de chanfrein. Ces axes de déplacement ont tous des directions différentes car le masque de chanfrein ne couvre jamais deux pixels du voisinage alignés avec le pixel en analyse placé en son centre, une telle couverture étant 1 o redondante. Du fait de sa définition, un axe de déplacement peut être associé à un coefficient C;,1 du masque de chanfrein. Les axes de déplacement découpent l'image en secteurs O, , ,..centrés sur le pixel source. Sur la figure 4, seul le quart supérieur droit d'un masque de chanfrein est représenté car l'on suppose que l'image conserve, malgré son anisotropie, des propriétés de symétrie axiale par rapport aux directions de ses lignes et colonnes. Egalement pour faciliter la compréhension, on emploiera parfois, une terminologie utilisée par les joueurs d'échec: - déplacement Tour de deux sortes selon l'axe Col ou l'axe C1,o pour prendre en compte un rapport r différent de l'unité entre les espacements unitaire des pixels selon les lignes et les colonnes de l'image, déplacement Fou selon une bissectrice C1,1, déplacement Cavalier de deux sortes selon l'axe C1,2 ou l'axe C2,1 toujours pour prendre en compte un rapport r différent de l'unité entre les espacements unitaire des pixels selon les lignes et les colonnes de l'image. Cette troisième approche par sélection progressive utilise la propriété selon laquelle, lorsque les conditions de U. Montanari sont vérifiées par les coefficients du masque de chanfrein, il est toujours possible de trouver parmi les trajets les plus courts reliant un pixel but à un pixel source un trajet n'employant au plus que deux types de déplacement. Pour le montrer, on suppose que le masque de chanfrein analyse le pixel source. Celui-ci a alors pour coordonnées 0,0 dans le système de repère des coefficients du masque. Le pixel but, qui est un point quelconque de l'image autre que le pixel source, peut être, soit sur un axe de déplacement associé à un coefficient du masque de chanfrein, soit dans l'un des secteurs Q, Q, Q ou Q. Si le pixel but est sur un axe de déplacement, le respect des conditions de U. Montanari fait que le trajet le plus court est le trajet rectiligne suivant cet axe. L'estimation de sa distance ne fait intervenir qu'un coefficient du masque de chanfrein. Ainsi, un pixel but Co,i situé sur l'axe de déplacement horizontal associé au coefficient Col et séparé du pixel source par j pixels intermédiaires a une distance estimée Dtfd égale à j déplacements Tour du premier type: Dtfd = j.Tour1 = j.Co,1 Un pixel but C;,21 situé sur l'axe de déplacement oblique associé au coefficient C1,2, toujours séparé du pixel source par j pixels intermédiaires, a une distance estimée Dtfd égale à j déplacements Cavalier de la première sorte: Dtfd = j.Cavalier1 = j.C1,2 Un pixel but Cj,1 situé sur l'axe de déplacement oblique associé au coefficient C1,1, toujours séparé du pixel source par j pixels intermédiaires, a une distance estimée Dtfd égale à j déplacements Fou: Dtfd = j.Fou = j.C1,1 Un pixel but C2i,i situé sur l'axe de déplacement oblique associé au coefficient 25 C2,1, toujours séparé du pixel source par j pixels intermédiaires, a une distance estimée Dtfd égale à j déplacements Cavalier de la deuxième sorte: Dtfd = j.Cavalier2 = j.C1,2 Un pixel but C;,o situé sur l'axe de déplacement vertical associé au coefficient C1,o, toujours séparé du pixel source par j pixels intermédiaires, a une 30 distance estimée Dtfd égale à j déplacements Tour de deuxième type: Dtfd = j.Tour2 = j.C1,2 Si le pixel but est en dehors des axes de déplacement associés aux coefficients du masque de chanfrein, dans l'un des secteurs Q, Q, Q, Q qu'ils délimitent, le respect des conditions de U. Montanari par les coefficients du masque de chanfrein implique que l'un des trajets les plus courts le reliant au pixel source utilise obligatoirement les deux seuls axes de déplacements associés aux coefficients du masque de chanfrein délimitant le secteur , , ou concerné (Ce résultat se prouve aisément par l'absurde: Si un trajet utilise trois types distincts de déplacement, on peut alors mettre en évidence un autre trajet plus court.). Un pixel but C;o,io appartenant au secteur dont les indices i0 et j0 respectent l'inégalité i0≤(j0-1)/2 et qui est séparé du pixel source par jO-2i0 pixels intermédiaires, a, comme montré à la figure 5a, une distance estimée égale à i0 déplacements Tour et j0-2i0 déplacements Cavalier du premier type: Dtfd = (j0-2i0).Tour1 + i0.cavalier1 = (j0-2i0) Co,1 +i0.C1,2 Pour construire un des trajets de longueur minimale reliant le pixel but au pixel source, on peut partir du pixel but en direction du pixel source par des déplacements Cavalier du premier type, parallèle à l'axe de déplacement associé au coefficient C1,2 du masque de chanfrein puis, une fois atteint l'axe horizontal, rejoindre le pixel source par des déplacements Tour du premier type. Comme le montre la figure 5b, pour construire un des trajets de longueur minimale reliant, au pixel source, un pixel but Cep appartenant au secteur avec des indices i0 et j0 respectant l'inégalité (1 +j0) /2≤2≤j0-1, on peut partir du pixel but en direction du pixel source par des déplacements Fou, parallèle à l'axe de déplacement associé au coefficient C1,1 du masque de chanfrein puis, une fois atteint l'axe de déplacement associé au coefficient C1,2, rejoindre le pixel source par des déplacements Cavalier du premier type. Le calcul des nombres de déplacements NC11 et NC12 dans chacune des deux directions peut se faire au moyen d'un algorithme du genre: Initialisa fion NC11 =0 i=i0 j=j0 On descend... Tant que (i>j/2) j=j-1 i=i-1 NC1 1=NC1 1+1 On complète... 35 NC12 = (j0-NC11)/2 Dans les deux derniers secteurs (D, respectivement , où les indices io et jo des pixels vérifient l'inégalité (1+i0)/2≤jO≤io1, respectivement jO≤(i0-1)/2, la construction d'un trajet de longueur minimale n'utilisant que les deux axes de déplacement portés par leurs côtés et la détermination des nombres de déplacements dans chacune des deux directions qui le composent, se font d'une manière analogue. L'existence, parmi les trajets les plus courts reliant un pixel but à un pixel source, d'un trajet qui n'utilise, au plus, que les deux axes de déplacement portés par les côtés du secteur auquel appartient le point but et dont les nombres de déplacements selon ces deux axes sont déterminables par le calcul, est mise à profit, dans l'approche, par sélection progressive, de la combinaison optimale de valeurs entières pour les coefficients du masque de chanfrein, pour simplifier l'appréciation d'un taux maximum d'erreur d'estimation de distance commise sur l'image. Dans l'approche, par sélection progressive, de la combinaison optimale de valeurs entières pour les coefficients du masque de chanfrein, l'appréciation du taux maximum d'erreur sur les estimations de distance des pixels de l'image résultant de la future sélection opérée est faite en plusieurs étapes. Dans une première étape, elle ne concerne que les pixels situés sur les axes de déplacements associés aux coefficients du masque. Puis elle est ensuite étendue progressivement au reste de l'image analysée par secteurs successifs délimités par les axes de déplacements associés aux coefficients du masque. Cette analyse progressive de l'image pour l'appréciation du taux maximum d'erreur sur les estimations distance résultant de la sélection opérée permet de mener conjointement une sélection des valeurs entières candidates pour les coefficients du masque de chanfrein, considérées individuellement ou par paires et non au niveau des combinaisons complètes possibles, ce qui diminue considérablement le nombre de cas à envisager. La prise en compte des symétries axiales de l'image et de l'isotropie du taux d'erreur sur les estimations distance des pixels alignés avec le pixel source permet de limiter l'analyse de l'image faite pour l'appréciation du taux maximum d'erreur à un petit nombre de pixel, ce qui simplifie encore les opérations. Le taux maximum d'erreur sur les estimations de distance de pixels but placés sur les axes de déplacement associés aux coefficients du masque de chanfrein ne dépend que du coefficient associé à l'axe de déplacement concerné et donc que des valeurs entières candidates pour. ce coefficient. Sa détermination est très rapide puisqu'il correspond au taux d'erreur de l'approximation par excès ou par défaut de la distance euclidienne de voisinage à laquelle correspond une valeur entière candidate pour le coefficient concerné. S'il y a un taux maximum d'erreur x% admissible, l'appréciation de ce taux maximum d'erreur sur axe pour chaque valeur entière candidate sert à un premier tri permettant d'écarter les valeurs entières ne respectant pas le taux d'erreur maximum x% admissible. La mise à l'écart d'une valeur entière fixe le choix d'un coefficient puisque celui-ci n'a que deux valeurs entières candidates, l'une approchant par excès et l'autre par défaut la distance euclidienne de proximité qu'il représente. La mise à l'écart des deux valeurs entières candidates pour un même coefficient supprime toute possibilité de choix et oblige à reconsidérer le facteur multiplicatif d'échelle ou le taux maximum d'erreur x% admissible. S'il n'y a pas de taux maximum d'erreur x% admissible, les taux maxima d'erreur sur axe sont accolés aux valeurs entières candidates en tant que note d'appréciation prise en compte dans une sélection ultérieure. Le taux maximum d'erreur sur les estimations de distance des pixels but appartenant à un secteur délimité dans l'image par des axes de déplacement associés aux coefficients du masque de chanfrein centré sur le pixel source ne dépend que des valeurs de la paire de coefficients du masque de chanfrein associés aux axes de déplacement constituant les côtés du secteur. II est donc à apprécier pour toutes les paires de valeurs entières qu'il est possible de constituer à partir des deux couples de valeurs entières candidates pour les deux coefficients considérés. II y a au plus quatre paires possibles. Au sein d'un secteur de l'image, tous les pixels ne sont pas à tester car les estimations de distance faites sur des pixels alignés par rapport au pixel source présentent la même erreur relative. En effet, considérons la figure 6 montrant différents pixels but P1,4, 35 P2,8, P3,12 et P4,16 disposés dans le premier secteur O, en alignement avec un pixel source Po,o placé à l'origine du repère. On a vu que l'un des trajets les plus courts reliant un pixel but P1,4, P2,8, P3,12 OU P4, 16 au pixel source Po,o n'utilise que les deux axes de déplacements qui définissent les côtés du premier secteur Q et qui sont associés aux coefficients Col et C1,2. Ces trajets les plus courts représentés sur la figure par une succession de flèches en traits épais forment les deux côtés d'un triangle ayant pour base le segment de droite reliant le point but considéré au point source. On remarque que les triangles s'appuyant sur les différents points but sont homothétiques. Cette propriété d'homothétie conserve pour tous les points but considérés P1,4, P2,8, P3, 12 et P4,16 le rapport entre la longueur de la base qui correspond à la distance euclidienne et la somme des longueurs des deux autres côtés qui correspond à l'estimation distance de sorte que l'erreur relative faite sur l'estimation distance est la même pour tous ces points. Pour apprécier le taux d'erreur maximum commis sur les estimations de distance de tous les pixels d'un secteur de l'image, on se contente alors de tester un seul pixel parmi les pixels ayant une même orientation par rapport au pixel source. Cette propriété d'isotropie permet de limiter le calcul du taux maximum d'erreur d'estimation de distance sur un secteur à un nombre de pixels de l'image correspondant au nombre des différentes orientations possibles pour un pixel dans le secteur. Pour l'ensemble des secteurs de l'image, le nombre total de pixels considérés dans les appréciations des taux maxima d'erreur sur secteur correspond au nombre des différentes orientations possibles dans l'image pour un pixel but par rapport au pixel source et même à un sous multiple de ce nombre lorsque l'image a des propriétés de symétrie. S'il y a un taux maximum d'erreur x% admissible, l'appréciation de du taux maximum d'erreur sur secteur pour chaque paire de valeurs entières 3o candidates pour deux coefficients du masque de chanfrein associés à des axes de déplacement connexes qu'il a été possible de construire après le premier tri basé sur le taux maximum d'erreur sur axe, sert à un deuxième tri permettant d'écarter les binômes de valeurs entières candidates pour des couples de coefficients ne respectant pas le taux d'erreur maximum x% admissible. Chaque mise à l'écart d'un binôme de valeurs entières réduit les possibilités de choix de combinaison de valeurs entières pour les coefficients. Si, après ce deuxième tri le choix d'une combinaison se révèle impossible, il faut reconsidérer le facteur multiplicatif d'échelle ou le taux maximum d'erreur x% admissible et recommencer les opération de sélection depuis le début. Dans le cas où il est possible d'extraire des binômes de valeurs entières candidates ayant franchi le deuxième tri, une valeur entière pour chaque coefficient du masque de chanfrein, on soumet la combinaison trouvée à un dernier test consistant à vérifier que ses valeurs entières respectent les conditions de U. Montanari (Formalisation de la banalité Le plus court chemin entre deux points est la ligne droite ) : C1,2 Cette validation progressive simplifie le calcul par le fait qu'elle permet d'abandonner, dans toutes les combinaisons potentielles, une valeur entière pour un coefficient n'ayant pas satisfait au test du taux d'erreur sur un secteur. Cette approche empêche l'explosion combinatoire liée aux tests de tous les jeux de coefficients possibles a priori. Pour un facteur d'échelle n donné, la sélection progressive peut aboutir à l'élimination de toutes les combinaisons ou au contraire à l'autorisation d'un trop grand nombre de combinaisons. Il faut donc régler judicieusement le taux maximum d'erreur x% admissible suffisamment bas pour avoir un résultat intéressant et suffisamment haut pour n'obtenir qu'un résultat. Une solution à ce dilemme consiste à choisir au départ un taux maximum d'erreur x% admissible assez bas pour que le processus de sélection progressif élimine toutes les combinaisons puis à recommencer le processus de sélection progressif en augmentant d'un pas fixe le taux maximum d'erreur x% admissible jusqu'à ce qu'une des combinaisons au moins franchisse le processus de sélection. Cette solution est rapide car si le taux maximum d'erreur x% admissible est trop bas, il se trouvera rapidement, dans les premiers points testés, des secteurs des pixels dont l'erreur d'estimation distance dépassera ce taux. Dans le cas où la sélection progressive conduit à plusieurs combinaisons possibles, on peut, soit recommencer la sélection progressive en diminuant le taux maximum d'erreur x% admissible, soit choisir l'une d'elles au hasard ou en fonction d'un critère de préférence portant sur une propriété des combinaisons tel que par exemple la combinaison dont la somme des valeurs entières est minimale. Si l'on ne cherche pas à respecter un taux maximum d'erreur admissible mais plutôt les valeurs de coefficients du masque de chanfrein optimales du point de vue du taux d'erreur maximum fait sur les estimations distance dans l'image pour un facteur multiplicatif d'échelle donné, l'appréciation du taux maximum d'erreur sur secteur pour chaque paire de valeurs entières candidates pour deux coefficients du masque de chanfrein associés à des axes de déplacement connexes n'est pas utilisée pour un tri mais en tant que note d'appréciation de chaque paire de valeurs entières candidates pour une sélection finale. Au cours de la sélection finale, les différentes paires de valeurs entières candidates se voient affectées trois notes d'appréciation, deux notes relatives aux taux d'erreur sur axe des deux valeurs entières qui les composent et une note relative au taux d'erreur sur secteur dont on retient la plus forte comme note globale puis l'on construit progressivement une combinaison à partir des binômes de valeurs entières candidates, en prenant les coefficients dans l'ordre des secteurs et en choisissant à chaque fois le binôme se raccordant avec le précédant (même valeur entière pour le dernier coefficient choisi) et ayant la notation la plus basse. La figure 7 résume les principales étapes d'un procédé de détermination des coefficients optimaux d'un masque de chanfrein en présence d'un facteur multiplicatif d'échelle n imposé et d'un taux maximum d'erreur x% admissible. Au cours d'une première étape 10, les valeurs entières candidates pour chaque coefficient sont calculées. Ces valeurs entières candidates sont, pour chaque coefficient, les deux nombres entiers approchant le plus par excès et par défaut le produit du facteur multiplicatif d'échelle n par la 1 o distance euclidienne de proximité correspondant au coefficient considéré. Au cours d'une deuxième étape 11, le taux d'erreur d'estimation distance pour des pixels de l'image situés sur l'axe de déplacement associé à chaque coefficient est calculé en donnant au coefficient considéré les valeurs du couple de valeurs entières candidates qui lui est affecté. Ce calcul consiste à déterminer pour chaque valeur entière candidate, le taux d'erreur de l'approximation qu'elle représente. Au cours d'une troisième étape 12, les valeurs entières candidates correspondant à un taux d'erreur sur axe supérieure au taux maximum d'erreur x% admissible sont éliminées. Au cours d'une quatrième étape 13, l'existence, après le premier tri, d'au moins une valeur entière candidate pour chaque coefficient est testée. S'il apparaît qu'un coefficient n'a plus aucune valeur entière candidate, le procédé de détermination des coefficients optimaux du masque de chanfrein est avorté et repris à son départ après avoir augmenté en 16 le taux maximum d'erreur x% admissible. Si tous les coefficients ont au moins une valeur entière candidate, le procédé de détermination des coefficients optimaux du masque de chanfrein se poursuit par une cinquième étape 14 au cours de laquelle les taux d'erreur d'estimation distance pour des pixels appartenant aux secteurs délimité dans l'image par des axes connexes de déplacement associés aux coefficients du masque de chanfrein sont calculés pour tous les binômes de valeurs entières qu'il est possible de constituer à partir des deux couples de valeurs entières candidates pour les deux coefficients considérés et rescapée du premier tri. La cinquième étape 14 est suivie par une sixième étape de tri 15 au cours de laquelle les binômes de valeurs entières candidates donnant des taux d'erreur sur secteur supérieure au taux maximum x% admissible sont éliminées. Au cours d'une septième 17, après les premier et deuxième tris 12 et 15, la construction, à partir des binômes de valeurs entières, de combinaisons de valeurs entières pour chacun des coefficients du masque de chanfrein est engagée. Cette construction peut être une construction progressive en prenant les coefficients dans l'ordre des secteurs et en choisissant à chaque fois le binôme se raccordant avec le précédant (même valeur entière pour le dernier coefficient choisi). Au cours d'une huitième étape 18, la présence d'une combinaison au moins est testée. S'il n'a pas été possible de construire de combinaison, le procédé de détermination des coefficients optimaux du masque de chanfrein est avorté et repris à son départ après avoir augmenté en 16 le taux maximum d'erreur x% admissible. Si une combinaison est présente, le procédé de détermination des coefficients optimaux du masque de chanfrein se poursuit par une dernière étape 19 de vérification des conditions de U. Montanari. En cas de non-vérification des conditions de U. Montanari par la combinaison examinée, celle-ci est éliminée et une autre est extraite des binômes de valeurs entières par retour à l'étape 17 après élimination en 20 de la combinaison précédemment analysée. La figure 8 résume les principales étapes d'un procédé de détermination des coefficients optimaux d'un masque de chanfrein en présence d'un facteur multiplicatif d'échelle n imposé mais sans taux maximum d'erreur x% admissible. Au cours d'une première étape 20, les valeurs entières candidates pour chaque coefficient sont calculées. Ces valeurs entières candidates sont, pour chaque coefficient, les deux nombres entiers approchant le plus par excès et par défaut le produit du facteur multiplicatif d'échelle n par la distance euclidienne de proximité correspondant au coefficient considéré. Au cours d'une deuxième étape 21, le taux d'erreur d'estimation distance pour des pixels de l'image situés sur l'axe de déplacement associé àchaque coefficient est calculé pour le couple de valeurs entières candidates pour le coefficient considéré. Ce calcul consiste à déterminer pour chaque valeur le taux d'erreur de l'approximation qu'elle représente. Au cours d'une troisième étape 22, le taux d'erreur sur axe calculé pour chaque valeur entière candidate est utilisé pour la notation des valeurs entières candidates. Au cours d'une quatrième étape 23, les taux d'erreur d'estimation distance pour des pixels appartenant aux secteurs délimités dans l'image par des axes connexes de déplacement associés aux coefficients du masque de chanfrein sont calculés pour tous les binômes de valeurs entières qu'il est possible de constituer à partir des deux couples de valeurs entières candidates pour les deux coefficients considérés et rescapées du premier tri. Au cours d'une cinquième étape 24, les binômes de valeurs entières ayant servis aux calculs des taux d'erreur reçoivent pour notation, la valeur la plus élevée du taux d'erreur sur secteur qui leur correspond et des taux d'erreur sur axe associés aux valeurs entières qui les composent. Au cours d'une sixième étape 25, une combinaison de valeurs entières pour chacun des coefficients du masque de chanfrein est construite progressivement à partir des binômes de valeurs entières candidates, en prenant les coefficients dans l'ordre des secteurs et en choisissant à chaque fois le binôme se raccordant avec le précédant (même valeur entière pour le dernier coefficient choisi) et ayant la notation la plus basse. Au cours d'une septième étape 26, la combinaison obtenue est testée pour s'assurer qu'elle vérifie les conditions de U. Montanari. Si les conditions sont vérifiées, elle est choisie pour les coefficients du masque de chanfrein. Si les conditions ne sont pas vérifiées, elle est rejetée en 27 et une autre est construite par retour à la sixième étape 25 et changement de l'un au moins des binômes utilisés dans la construction de la nouvelle combinaison. La figure 9 détaille les étapes 14 et 15 de sélection des valeurs entières candidates en fonction du taux d'erreur sur secteur dans le cas d'un masque de chanfrein à 16 coefficients et à symétries axiales selon les lignes et colonnes, comme celui illustré à la figure 4. Les valeurs entières candidates Voo1, Vc12, Vo11,Vo21, Vc10 pour les cinq catégories de coefficient représentées par les coefficients: Co,1, C1,2, C1,1, C2,1, C1,O sont supposées avoir franchi le premier tri (12 figure 7) et être sous les x% d'erreur sur les axes. Dans un premier temps, la ou les valeurs entières Vc01 et Vc12 candidates pour les coefficients Col et C1,2 associés aux axes de déplacements délimitant sont triées par binôme en employant comme critère de tri l'erreur qu'elles entraînent sur les estimations de distance pour des pixels situés dans le secteur (Q figure 4) délimité par les axes de déplacement associés aux coefficients Co,1 et C1,2.. Pour ce faire, au cours d'une première étape 140, on choisit une des valeurs entières Vco1 candidates pour le coefficient Co,1. Au cours d'une deuxième étape, 141, on lui adjoint l'une des valeurs entières Vc12 candidate pour le coefficient C1,2. Au cours d'une troisième étape 142 on calcule l'erreur d'estimation distance entraînée par le binôme formé (Vc01, Vc12) sur les pixel du secteur (O figure 4) délimité par les axes de déplacement associés aux coefficients Col et C1,2 15. On ne retient en finale, à l'étape 150, le binôme formé que si l'erreur sur secteur calculée est inférieure au taux maximum d'erreur admissible x% et l'on recommence pour tous les binômes qu'il est possible de former avec les valeurs entières Vc01 et Vc12 candidates pour les coefficients Col et C1,2 retenues dans le premier tri (12 figure 4). On dispose ainsi, à l'étape 150 des seuls binômes (Vc01, Vc12) permettant de respecter le taux maximum d'erreur admissible x%. Dans un deuxième temps, on fait de même avec la ou les valeurs entières Vc12 candidates au coefficient C1,2 figurant à l'étape 150 dans les binômes (Vc01, Vc12) retenus dans le premier temps et la ou les valeurs entières Vc11 candidates pour le coefficient C1,1 en employant comme critère de tri l'erreur qu'elles entraînent sur les estimations de distance pour des pixels situés dans le secteur (O figure 4) délimité par les axes de déplacement associés aux coefficients C1,2 et C1,1.. Pour ce faire, on retient une valeur entière candidate Vc12 figurant dans les binômes (Vc01, Vc12) retenus à l'étape 150 et on lui adjoint, au cours d'une étape 143, l'une des valeurs entières Vc12 candidate pour le coefficient C1,2. Au cours d'une étape 144 on calcule l'erreur d'estimation distance entraînée par le binôme formé (Vc12, Vc11) sur les pixel du secteur (Q figure 4) délimité par les axes de déplacement associés aux coefficients C1,2 et C1,1 et l'on ne retient en finale, 35 à l'étape 151, le binôme formé que si l'erreur sur secteur calculée est inférieure au taux maximum d'erreur admissible x%. On recommence pour tous les binômes qu'il est possible de former avec les valeurs entières Vc12 candidates pour le coefficient C1,2 apparaissant dans les binômes retenus à l'étape 150 et avec les valeurs entières Vc12 candidates pour le coefficient C1,1 retenues dans le premier tri (12 figure 4). On dispose ainsi, à l'étape 151 des seuls binômes (Vc01, Vc12) et (Vc12 Vc11) permettant de respecter le taux maximum d'erreur admissible x%. Dans un troisième temps, on fait de même avec la ou les valeurs entières Vc11 candidates au coefficient C1,1 figurant à l'étape 151 dans les io binômes (Vc12, Vc11) retenus dans le deuxième temps et la ou les valeurs entières Vc21 candidates pour le coefficient C2,1 en employant comme critère de tri l'erreur qu'elles entraînent sur les estimations de distance pour des pixels situés dans le secteur ( figure 4) délimité par les axes de déplacement associés aux coefficients C1,1 et C2,1 et ainsi de suite dans un 15 quatrième temps. A la fin, on dispose de binômes de valeurs de valeurs entières candidates pour les coefficients dont on est assuré qu'elles conduisent à des valeurs de coefficients respectant le taux maximum d'erreur x% admissible sur les estimations distance dans l'image. Cette approche évite l'explosion combinatoire liée aux tests de tous les jeux de coefficients possibles a priori. Les procédés de détermination des coefficients optimaux d'un masque de chanfrein qui viennent d'être décrits s'appliquent avantageusement aux masques de chanfrein utilisés pour l'estimation des distances, par rapport à un mobile, des points d'une zone de la surface terrestre où il évolue, lorsque cette zone est représentée par une carte en deux dimensions, tirée d'une base de données d'élévation du terrain réalisée à partir d'un maillage régulier en latitude et longitude de la surface terrestre. En effet, dans un tel cas, l'image formée par la carte est anisotrope car ses pixels, qui correspondent aux emplacements des points de mesure d'élévation figurant dans la base de données d'élévation terrain, ont un écartement unitaire en direction des parallèles variant en fonction de la latitude du fait du rapprochement des méridiens en directions des pôles. De ce fait, le motif carré formé, aux faibles latitudes, par les points d'une base de données d'élévation du terrain à maillage régulier en latitude et longitude pour une latitude faible ou nulle se déforme en un motif de plus en plus trapézoïdal lorsque la latitude augmente. Cette déformation oblige à modifier les coefficients du filtre de chanfrein en fonction de la latitude du mobile pour conserver la même précision aux estimations distance. Pour une base de données d'élévation du terrain précise, avec un maillage régulier en latitude et en longitude de 15" d'arc jusqu'à la latitude de 75 et, au-delà, une seule élévation valable pour toute la calotte polaire, l'anisotropie de l'image formée par une carte de zone d'évolution peut être traitée en découpant la surface du globe par bandes de latitude de 6 de large et en associant à chacune de ces bandes un jeu particulier de coefficients optimaux de masque de chanfrein déterminé pour la ligne médiane de cette bande en assimilant le motif du maillage à un rectangle avec un rapport r de l'espacement unitaire des pixels en latitude sur l'espacement unitaire des pixels en longitude égale au cosinus de la latitude: r = cos(Latitude)) Avec un facteur multiplicatif d'échelle de 100 à 1000, on arrive à trouver des coefficients optimaux de masque de chanfrein permettant de respecter un taux d'erreur d'estimation des distances inférieur à 2% dans une plage de latitude allant de 0 à 35 et inférieur à 8% au-delà. Dans cette application, les procédés de détermination des coefficients optimaux d'un masque de chanfrein qui viennent d'être décrits permettent de corriger, sans pré-traitement, la convergence des méridiens vers les pôles tout en garantissant une erreur relative minimale par rapport à la distance orthodromique et en prenant en compte la meilleure résolution disponible d'une base de données d'élévation terrain. REVENDICATIONS 1. Procédé de détermination des coefficients optimaux Cid, i étant un indice ligne variant de P à +P et j un indice colonne variant de Q à +Q, P et Q étant des nombres entiers positifs, d'un masque de chanfrein de transformée de distance fournissant des estimations de distance entre pixels d'une image, lesdits coefficients étant des approximations, à un facteur multiplicatif d'échelle n près, n étant un nombre entier positif, des distances 1 o d'un pixel de l'image soumis à l'analyse du masque de chanfrein par rapport aux pixels de l'image les plus proches dans les différentes directions dits pixels du masque, chaque coefficient étant associé au pixel du masque dont il représente la distance, et la détermination consistant en un choix, pour chaque coefficient, d'une valeur sélectionnée parmi un ensemble de valeurs candidates pour le coefficient considéré, ledit procédé étant caractérisé en ce qu'il utilise, comme critères de choix: le taux maximum d'erreur d'estimation distance entraîné par le choix d'une valeur candidate pour un coefficient, sur les estimations de distances des pixels de l'image alignés sur un axe de déplacement de l'image correspondant à la direction allant d'un pixel source origine des mesures de distance soumis à l'analyse du masque de chanfrein au pixel du masque associé au coefficient considéré, et le taux maximum d'erreur d'estimation distance entraîné par le choix de deux valeurs candidates pour un couple de coefficients, sur les estimations distance des pixels de l'image contenus dans un secteur angulaire de l'image, délimité par deux axes de déplacement de l'image correspondant aux directions allant du pixel source soumis à l'analyse du masque de chanfrein aux deux pixels du masque associés aux coefficients considérés. 2. Procédé selon la revendication 1, appliqué en présence d'un taux maximum d'erreur x% imposé, caractérisé en ce qu'il comporte les étapes suivantes: calcul, en fonction du facteur multiplicatif d'échelle n, des couples A1J de valeurs entières correspondant aux approximations par défaut et par excès de chacune des distances des pixels du masque par rapport au pixel soumis à l'analyse du masque, les valeurs entières d'un couple A;,i étant candidates pour le coefficient C;,] du masque de chanfrein affecté au pixel du masque dont elles sont une approximation de la distance, adoption d'un pixel de l'image comme pixel source origine des mesures de distance, calcul, pour chaque valeur entière candidate pour un coefficient, du taux d'erreur d'estimation distance pour des pixel de l'image alignés sur un axe de déplacement de l'image correspondant à la direction allant d'un pixel source origine des mesures de distance soumis à l'analyse du masque de chanfrein au pixel du masque associé au coefficient considéré, - premier tri parmi les valeurs entières candidates consistant à éliminer celles pour lequel le taux d'erreur sur axe dépasse le taux maximum d'erreur x% admissible, arrêt de la détermination des coefficients du masque de chanfrein dès que les deux valeurs entières de l'un des couples Au sont éliminées, si tous les couples A;,1 initiaux conservent au moins une valeur entière après le premier tri, poursuite de la détermination des coefficients du masque par le partage du masque de chanfrein et de l'image en 2(P+Q) secteurs angulaires Sk orientés contiguës les uns des autres ayant pour sommet, le pixel en analyse et, pour côtés, des axes de déplacement de l'image correspondant à la direction allant du pixel source soumis à l'analyse du masque de chanfrein à un pixel du masque, et n'englobant aucun autre pixel du masque, calcul, pour chaque secteur angulaire Sk et pour chaque binôme de valeurs entières candidates pour les deux coefficients associés aux deux pixels du masque placés sur les côtés du secteur angulaire Sk considéré du taux d'erreur d'estimation de distance pour des pixels de l'image appartenant au secteur Sk considéré, deuxième tri parmi les binômes de valeurs entières candidates pour deux coefficients associés à deux pixels du masque placés sur les côtés d'un secteur angulaire Sk consistant à rejeter ceux pour lesquels le taux d'erreur sur axe dépasse le taux maximum d'erreur admissible x%, construction, à partir des binômes de valeurs entières issus du deuxième tri, d'une combinaison de valeurs entières candidates pour chacun des coefficients du masque de chanfrein, test du résultat de la construction, si aucune combinaison n'a pu être construite arrêt de la détermination des coefficients du masque de chanfrein, si au moins une combinaison a pu être construite, adoption de l'une d'elles pour les coefficients du masque de chanfrein. 3. Procédé selon la revendication 2, caractérisé en ce qu'il comporte en outre une étape de vérification du respect des conditions de U. Montanari par la combinaison adoptée à la suite de l'étape de construction. 4. Procédé selon la revendication 2, caractérisé en ce que la construction, à partir des binômes de valeurs entières issus du deuxième tri, d'une combinaison de valeurs entières candidates pour chacun des coefficients du masque de chanfrein se fait progressivement, en prenant les coefficients dans l'ordre des secteurs angulaires. 5. Procédé selon la revendication 2, caractérisé en ce qu'il est réitéré avec une augmentation du taux maximum d'erreur x% imposé à chaque fois qu'il aboutit à un échec, soit à la suite du premier tri, soit à la 35 suite du deuxième tri. 6. Procédé selon la revendication 2, caractérisé en ce qu'il est réitéré avec une augmentation du facteur multiplicatif d'échelle n à chaque fois qu'il aboutit à un échec, soit à la suite du premier tri, soit à la suite du 5 deuxième tri. 7. Procédé selon la revendication 2, caractérisé en ce qu'il est appliqué avec un taux maximum d'erreur imposé initial xo% suffisamment faible pour qu'il n'aboutissent pas et qu'il est répété en augmentant 1 o progressivement le taux maximum d'erreur imposé x% jusqu'à ce que l'étape de construction aboutisse à une combinaison de valeurs entières candidates pour tous les coefficients du masque de chanfrein. 8. Procédé selon la revendication 1, caractérisé en ce qu'il 15 comporte les étapes suivantes: calcul, en fonction du facteur multiplicatif n, des couples A;,1 de valeurs entières correspondant aux approximations par défaut et par excès de chacune des distances des pixels du masque par rapport au pixel soumis à l'analyse du masque, les valeurs entières d'un couple A1,1 étant éligibles pour le coefficient Cu du masque de chanfrein affecté au pixel du masque dont elles sont une approximation de la distance, - adoption d'un pixel de l'image comme pixel source origine des mesures de distance, - calcul, pour chaque valeur entière candidate pour un coefficient, du taux d'erreur d'estimation distance pour des pixel de l'image alignés sur un axe de déplacement de l'image correspondant à la direction allant d'un pixel source origine des mesures de distance soumis à l'analyse du masque de chanfrein au pixel du masque associé au coefficient considéré, - affectation à chaque valeur entière candidate, en tant que notation, du taux d'erreur sur axe qui lui correspond, - calcul, pour chaque secteur angulaire Sk et pour chaque binôme de valeurs entières candidates pour les deux 35 coefficients associés aux deux pixels du masque placés sur les côtés du secteur angulaire Sk considéré, du taux d'erreur d'estimation de distance pour des pixels de l'image appartenant au secteur Sk considéré, affectation, à chaque binôme de valeurs entières candidates ayant servi au calcul d'un taux d'erreur sur secteur, d'une notation constituée de la valeur la plus élevée du taux d'erreur secteur qui lui correspond et des taux d'erreur sur axe associés aux valeurs entières candidates qui le composent, et construction d'une combinaison de valeurs entières candidates pour chacun des coefficients du masque de chanfrein, à partir des binômes de valeurs entières ayant les plus faibles notations possibles, 9. Procédé selon la revendication 8, caractérisé en ce qu'il 15 comporte en outre une étape de vérification du respect des conditions de U. Montanari par la combinaison adoptée à la suite de l'étape de construction. 10. Procédé selon la revendication 8, caractérisé en ce que la construction, à partir des binômes de valeurs entières, d'une combinaison de valeurs entière candidates pour chacun des coefficients du masque de chanfrein se fait progressivement, en prenant les coefficients dans l'ordre des secteurs angulaires. 11. Procédé selon la revendication 1, caractérisé en ce qu'il est appliqué à la détermination des coefficients optimaux de masques de chanfrein utilisés pour l'estimation des distances, par rapport à un mobile, des points d'une zone de la surface terrestre où il évolue, lorsque cette zone est représentée par une carte en deux dimensions, tirée d'une base de données d'élévation du terrain réalisée à partir d'un maillage régulier en latitude et longitude de la surface terrestre. 12. Procédé selon la revendication 11,caractérisé en ce qu'il est appliqué à la détermination des coefficients optimaux d'un masque de chanfrein valables pour des plages de latitude recouvrant celle de la zone 35 d'évolution du mobile. 10