Brevet FR2690262A1 — publié le 19931022

PROCEDE DE PISTAGE A PARTIR D'IMAGES D'ELEMENTS DEFORMABLES ET/OU AUX CONTOURS FORTEMENT BRUITES La présente invention concerne un procédé de pistage à partir d'images d'éléments déformables et/ou aux contours fortement bruités. Un domaine particulier d'application de l'invention consiste dans le pistage de perturbations météorologiques à partir d'images provenant, par exemple, d'un écran radar Les nuages sont des objets déformables dont la forme évolue lentement dans le temps par rapport aux vitesses de traitements d'images existants, et dont la vitesse et l'accélération sont sensiblement continues La déformation de nuages rend difficile la reconnaissance d'un même nuage d'une image à l'autre, et cette difficulté est accrue lorsque l'on désire calculer la vitesse d'un nuage D'autre part, les contours des nuages sont en général très bruités, et il est important, pour pouvoir extraire toute information, d'affiner au maximum ces contours. Le but de la présente invention est de proposer un procédé permettant d'extraire facilement des contours fermés et très fins des objets afin de pouvoir faire une reconnaissance de la forme des objets d'une image à l'autre, et en déduire leurs vitesses. Plus précisément, l'invention concerne un procédé de pistage d'éléments déformables et/ou aux contours fortement bruités, à partir d'images composées d'un nombre entier N de lignes et M de colonnes, et d'un nombre Nx M de pixels codés suivant un nombre entier Q de valeurs de luminance, le procédé étant caractérisé en ce qu'il consiste à: effectuer, sur chaque image, un pré-traitement de mise en forme de l'image afin de lisser les contours; extraire les contours de façon à obtenir des contours fermés et dont les épaisseurs ne dépassent pas un pixel; extraire, pour chaque contour fermé, des paramètres significatifs des contours; comparer, d'une image à l'autre, les paramètres obtenus de façon à reconnaître la forme d'un élément, puis en déduire sa vitesse Le procédé est particulièrement adapté au pistage d'objets lentement déformables par rapport à deux acquisitions d'images successives (pour les nuages, cela dépend de la rotation de l'antenne radar). L'invention sera mieux comprise au vu de la description suivante, faite en référence aux figures annexées. La figure 1 est un synoptique général du procédé selon l'invention; La figure 2 est un synoptique du pré-traitement 1 de la figure 1; La figure 3 est un autre synoptique possible du pré- traitement; La figure 4 montre les étapes à réaliser pour l'extraction des contours; La figure 5 montre l'ordre dans lequel chaque pixel d'un contour doit être testé, conformément à l'invention. La figure 1 montre un synoptique du procédé selon l'invention, synoptique sur lequel ont été représentées les étapes générales du procédé selon l'invention Chaque étape sera détaillée par la suite en référence à d'autres figures: D'après la figure 1, la donnée d'entrée sur laquelle on applique le procédé selon l'invention, consiste en une image de N lignes et de M colonnes, constituée d'un nombre Nx M de points élémentaires ou pixels L'image contient des objets de préférence lentement déformables, typiquement des nuages, dont il va falloir extraire certains paramètres, comme nous le détaillerons plus loin. On considère que l'image provient d'un écran noir et blanc, par exemple d'un écran radar Pour rendre compte des différents niveaux de gris, les pixels sont codés sur Q niveaux de luminance possibles, allant du noir (niveau 0) au blanc (niveau Q-1) Sur cette image brute, les pixels qui sont à l'intérieur des nuages sont blancs, ceux qui sont éloignés des nuages sont noirs Entre ces deux extrêmes, notamment pour les pixels proches ou appartenant aux contours des nuages, les luminances traduisent différents niveaux de gris, codés entre O et Q-1. La première étape du procédé selon l'invention consiste à effectuer, sur cette image brute, un pré-traitement 1 de mise en forme de l'image Le but de ce pré-traitement est de faire ressortir au mieux les nuages (en blanc) sur le ciel (en noir) Si l'on se contente de faire un seuillage de l'image brute pour obtenir une image binaire avec les deux niveaux O et Q-1 de luminance, on fera apparaître des nuages blancs aux contours très irréguliers à cause du bruit Or, pour que la suite du traitement soit possible, il est essentiel d'effectuer en outre, un lissage des contours de façon à approximer au mieux la forme des nuages Cette approximation est en effet primordiale pour la phase de reconnaissance des formes de nuages d'une image à l'autre Nous verrons par la suite (description de la figure 2) que la Demanderesse a choisi d'effectuer une série d'étapes ayant pour rôle d'éroder puis de dilater les contours des nuages, de façon à ce que le résultat global soit un lissage des contours. A l'issue de ce pré-traitement 1, l'image obtenue est toujours composée de Nx M pixels, mais dont les valeurs de luminance sont à deux niveaux, le niveau O et le niveau Q-1 Tous les nuages de l'image, dont les contours ont été lissés selon l'invention, sont par exemple blancs, sur un ciel noir. Compte tenu du choix fait par la Demanderesse sur les paramètres à partir desquels les différentes informations seront déduites (reconnaissance de forme, vitesse de nuage), il est nécessaire de procéder à l'extraction des contours Ck à partir de l'image issue du pré- traitement 1 C'est la deuxième étape du procédé selon l'invention, référencée 2 sur la figure 1 Là encore, pour assurer la faisabilité de la suite du traitement, l'extraction 2 des contours Ck selon l'invention doit garantir l'obtention de contours fermés Nous verrons en effet par la suite que le principe de l'invention repose sur l'assimilation d'un objet lentement déformable à un objet indéformable, assimilation qui permettra d'appliquer des méthodes de calcul propres à la cinématique des objets indéformables pour calculer la vitesse des nuages En outre, l'extraction 2 des contours Ck selon l'invention permet avantageusement d'obtenir des contours Ck dont l'épaisseur ne dépasse pas un pixel Cette épaisseur, ramenée à son minimum, permet de réduire de façon optimale les temps de traitements des étapes suivantes L'image obtenue à l'issue de l'extraction 2 des contours Ck est à nouveau une image binaire dont le niveau de luminance (C -1) est préférentiellement attribué aux pixels des contours Ck extraits, le niveau de luminance O étant attribué à tous les pixels restants. La troisième étape du procédé selon l'invention consiste en l'extraction 3 des paramètres significatifs de chaque contour Ck. On entend par paramètres significatifs les paramètres qui permettent d'obtenir d'une part, un critère simple pour reconnaître les formes des nuages d'une image à l'autre, et d'autre part, une méthode simple de calcul de la vitesse de chaque nuage Comme nous l'avons dit précédemment, les étapes précédentes permettent d'assimiler le nuage à un objet indéformable Or, pour les objets indéformables, un critère simple de reconnaissance consiste en la comparaison du périmètre de ces objets d'une image à l'autre De même, le calcul de la vitesse d'un objet indéformable se déduit aisément du calcul du déplacement du centre de gravité de cet objet Les deux paramètres significatifs choisis par la Demanderesse sont donc le périmètre Pk et le centre de gravité Gk d'un contour Ck Nous détaillerons plus par la suite l'extraction de ces deux paramètres à partir de l'image obtenue après l'extraction 2 des contours Ck. A l'issue de la troisième étape, nous connaissons donc les périmètres Pk et les centres de gravité Gk de tous les contours Ck présents dans l'image. L'étape suivante consiste en la reconnaissance 4 des io contours d'une image à l'autre Toujours dans le cadre de l'assimilation d'un nuage à un objet indéformable, on peut considérer que les périmètres Pk de l'image en cours de traitement sont très peu différents des périmètres Pk' relatifs aux mêmes contours trouvés lors du traitement de l'image précédente Comme il est peu probable que deux nuages différents possèdent le même périmètre, une simple comparaison des périmètres Pk avec les périmètres Pk' et des centres de gravité Gk et Gk' suffit pour reconnaître un contour. La dernière étape du traitement, référencée 5 sur la figure 1, consiste alors à calculer, pour chaque couple de périmètres (Pk, Pk) correspondant au même contour Ck, le déplacement du centre de gravité de Ck pour aller de la position Gk' à la position Gk De ce déplacement, on déduit aisément la vitesse de ce centre de gravité, et donc une estimation de la vitesse du nuage. Nous allons à présent détailler successivement les différentes étapes du procédé selon l'invention. La figure 2 détaille le pré-traitement 1 de mise en forme de l'image. La première étape consiste en un seuillage 11 de l'image brute composée de Nx M pixels, codés sur Q niveaux de luminance, par exemple entre O et Q-1 Ce seuillage 11 consiste à mettre tous les pixels dont la luminance codée est supérieure à un seuil S donné, à (Q-1), et tous les autres pixels à O Le seuil S étant choisi convenablement, par exemple de l'ordre de Q/2, on obtient une visualisation des nuages représentés en blanc sur un fond noir Les contours de ces nuages sont cependant très irréguliers et ne permettent pas la reconnaissance simple des nuages d'une image à l'autre Le procédé selon l'invention propose donc d'effectuer un lissage 12 des contours, ce lissage comportant une première phase d'érosion 13 de l'image, suivie d'une seconde phase de dilatation 14 de l'image La phase d'érosion 13 tient sa dénomination du fait qu'elle permet d'éliminer les pixels blancs isolés Elle consiste à promener une fenêtre carrée de dimension impaire sur l'image, et de remplacer la luminance du pixel central de la fenêtre par le résultat obtenu en effectuant un ET logique entre ce pixel central et ses voisins. La phase de dilatation 14 est duale de la précédente en ceci qu'elle permet d'éliminer les pixels noirs isolés En utilisant la même fenêtre que précédemment, on effectue cette fois-ci un OU logique entre le pixel central et ses voisins. Le lissage des contours obtenu par cette succession d'érosion et de dilatation déforme un peu l'objet Cependant, le traitement est identique sur toutes les images et permet de réduire considérablement le bruit. Les études de la Demanderesse ont montré que l'on pouvait procéder autrement pour effectuer le lissage 12 Cette variante, illustrée sur la figure 3, consiste à utiliser la convolution de l'image issue du seuillage 11 (figure 2) par une matrice de filtrage particulière réalisant une moyenne des luminances. Nous rappelons ci-après le principe de la convolution de l'image par une matrice carrée de dimension 3, pour simplifier les calculs: soit la matrice A: d e f g h k Soit L (i, j) la luminance codée du pixel situé sur la ligne indicée par l'entier i et la colonne indicée par l'entier j. Pour chaque pixel (i, j), on calcule l'expression a x L (i-1, j-1) + b x L (i-1, j) + c x L (i-1, j+l) +d x L (i,j-1) + e x L (i,j) + f x L (i,j+l) ( 1) +g x L (i+l,j-1) + h x L (i+ 1, j+l) + kx L (i+l, j+l). La somme précédente s'effectue modulo Q Le résultat obtenu appartenant à l'intervalle lO, Q-1 l, il peut être considéré comme une valeur de luminance L' (i, j) que l'on affecte au pixel (i, P). La matrice particulière utilisée selon l'invention est une matrice carrée unitaire de dimension P P étant entier impair inférieur aux entiers N et M. L'application de la relation 1 dans ce cas revient à remplacer la luminance L (i, j) du pixel (i, j) par la luminance L' (i, j) représentant la moyenne des luminances des pixels voisins du pixel (i, j). La Demanderesse a montré que la succession des étapes suivantes, à savoir: une première convolution 121 de l'image issue du seuillage 11 par la matrice carrée unitaire; un premier seuillage 122 de l'image convoluée avec un seuil égal préférentiellement à Q/2; une première inverse vidéo 123 de l'image; une seconde convolution 121 ' de l'image inversée par la même matrice carrée unitaire; un second seuillage 122 ' de l'image convoluée avec un seuil sensiblement égal à 0/2; une seconde inverse vidéo 123 '; réalisait entièrement le lissage 12 comprenant les phases d'érosion 13 et de dilatation 14. A chacune des deux convolutions 121, 121 ' précédentes, il est préférable de veiller à ne pas remplacer la luminance L (i, j) du pixel (i, j) par la luminance L' (i, j) tant que le pixel (i, j) est utilisé dans la convolution d'autres pixels Ceci fausserait en effet les résultats Il faut donc, parallèlement à la convolution 124 d'un pixel (i 1,), effectuer un stockage 125 des luminances L' (i, j) Le remplacement 126 des luminances se fait alors soit lorsque toute l'image a été convoluée, soit préférentiellement lorsque l'on ne se sert plus du pixel (i, j) dans la convolution. A l'issue du pré-traitement 1, on est en présence d'une image comprenant des pixels noirs ( 0) appartenant au ciel, ou blancs ( 0-1) appartenant aux nuages (contours compris) Les contours ont,selon l'invention, subi un lissage Conformément à la figure 1, l'image obtenue va subir une étape d'extraction 2 des contours Ck des objets, dont le détail est schématisé sur la figure 4: Il est classique d'extraire les contours d'objets sur une image en utilisant une matrice dite de Laplace Cette matrice est utilisée pour vider l'intérieur des objets, et ne conserver que leurs contours à l'écran Elle est basée sur le principe des filtres Laplacien qui consiste à calculer la dérivée seconde de l'image Il existe de nombreuses matrices de Laplace et le choix d'une matrice particulière a conduit la Demanderesse à analyser plus finement les caractéristiques d'un pixel d'un contour: Pour qu'un pixel (i, j) appartienne à un contour, il faut et il suffit que les deux conditions suivantes soient réalisées en même temps: la luminance L (i, j) de ce pixel est codée à Q-1; au moins un de ses quatre pixels voisins pris sur la même ligne, i et la même colonne j possède une luminance codée à 0. Seuls les quatre pixels voisins tels que définis précédemment doivent être étudiés En effet, la Demanderesse s'est aperçue que l'étude des huit voisins possibles d'un pixel pourrait conduire à classer par erreur des pixels comme appartenant à un contour. Le choix de la matrice de Laplace découle des observations précédentes: comme on ne s'intéresse pas aux voisins d'un pixel central qui ne sont pas sur la même ligne ou sur la même colonne, il faut mettre des coefficients nuis aux places correspondantes. Les autres coefficients sont choisis de façon à pondérer les contributions des pixels considérés Ainsi, la matrice de Laplace particulière choisie selon l'invention est une matrice carrée de dimension 3, dont les coefficients sont 0 -1 01 -1 4 -1 O? -1 à un facteur multiplicatif a près. En se référant à la figure 4, l'extraction 2 des contours consiste donc à effectuer une convolution 21 de l'image par la matrice de Laplace choisie Comme précédemment, il est préférable, parallèlement à la convolution 211 d'un pixel (i, j) donné, de faire un stockage 212 de la valeur L' (i, j) résultante, et de n'effectuer le remplacement 213 de la luminance que lorsque le pixel (i, j) n'est plus utilisé pour la convolution d'autres pixels D'autre part, les pixels qui sont proches du bord de l'image n'ont, par construction, pas de voisins Pour pouvoir appliquer la convolution à ces pixels particuliers, le procédé selon l'invention prévoit de créer des voisins fictifs dont la valeur de luminance est O Ceci permet de garantir l'obtention d'un contour fermé, même sur les bords de l'image, ce qui est indispensable pour la suite du traitement. Suivant les pixels considérés de l'image, les résultats de la convolution 21 seront les suivants: un pixel (i, j) du contour est caractérisé par sa luminance L (i, j) qui est à Q-1 et par un, deux, trois ou quatre voisins éteints (luminance à 0) Les luminances L' (i, ô) seront donc respectivement 0-1, 0-2, 0-3, ou 0-4; un pixel (i, ô) interne au nuage est caractérisé par sa luminance L (i, j) qui est à Q-1, tout comme celles de ses quatre voisins La luminance L' (i, P) sera donc toujours égale à O; un pixel (i, j) externe au nuage est caractérisé par sa luminance L (i, j) qui est à 0, et par un, deux, trois ou quatre voisins éteints (luminance à 0) Les luminances L' (i, j) seront donc respectivement 3, 2, 1 ou 0. On a bien abouti au résultat escompté, à savoir mettre à 0 les pixels internes aux nuages, et laisser les autres sensiblement invariants. L'image obtenue après la convolution 21 contient des pixels dont les luminances appartiennent au groupe {Q-i, Q-2, Q-3, Q-4}, et d'autres pixels dont les luminances appartiennent au groupe { 0,1,2,3} Le procédé selon l'invention propose d'effectuer un seuillage 22 de cette image avec un seuil fixé par exemple à 0/2 de manière à ce que seuls les contours soient allumés, avec une luminance C-1. Conformément à la figure 1, la troisième étape du procédé selon l'invention consiste en l'extraction 3 des paramètres il significatifs de chaque contour Ck de l'image Comme nous l'avons expliqué précédemment, ces paramètres significatifs sont, d'une part les périmètres Pk, et d'autre part, les centres de gravité Gk des contours Ck. Le relevé des contours se fait en parcourant, objet par objet, les points de contours, c'est-à-dire les seuls points de l'image issue du traitement 2 dont la luminance n'est pas à O Le procédé selon l'invention prévoit de tester chaque pixel des contours en cherchant, pour chacun, lesquels de ses huit voisins sont allumés. Pour ce faire, on regarde les huit voisins dans un ordre déterminé tel que celui schématisé sur la figure 5 Cet ordre doit être cohérent avec le balayage de l'écran, c'est-à-dire de haut en bas et de gauche à droite dans l'exemple de la figure 5 dans lequel le pixel testé est le pixel central et l'ordre correspond à l'ordre numéroté de i 5 1 à 8 Cette recherche s'effectue de manière récursive, c'est-à-dire que, dès que l'on rencontre un voisin allumé, on entame une recherche identique sur ce voisin La récursivité impose de faire particulièrement attention si l'on ne veut pas oublier certains points appartenant aux contours, ou encore passer plusieurs fois sur un même point De plus, il faut pouvoir facilement passer d'un contour à l'autre. Les études de la Demanderesse ont montré la nécessité d'associer à chaque pixel des contours une variable d'état pouvant être dans quatre états différents: Etat O: pixel non testé Etat 1: pixel appartenant au contour du pixel testé mais n'ayant pas encore été testé Etat 2: pixel appartenant au contour du pixel testé et ayant subi le test Etat 3: pixel appartenant à un contour précédent (donc déjà testé). Tous les pixels d'un même contour sont déterminés lorsqu'on ne trouve plus de voisins allumés en effectuant les tests de proche en proche Leur variable d'état étant alors dans l'Etat 2, il suffit de les compter pour connaître le périmètre du contour. Quant aux barycentres Gk, leur abscisse et leur ordonnée sont calculées classiquement en effectuant respectivement la moyenne des abscisses et la moyenne des ordonnées des pixels du contour, lesquelles ont été stockées au préalable, par exemple au moment du relevé des contours. Conformément à la figure 1, la reconnaissance 4 des contours Ck s'effectue par comparaison des paramètres significatifs Pk et Gk de l'image courante avec les paramètres significatifs Pk' et Gk' de l'image précédemment traitée Un contour est reconnu comme représentatif d'un même objet s'il satisfait aux deux conditions suivantes: Les barycentres Gk et Gk' sont proches, c'est-à-dire que la distance Gk Gk' est inférieure à une distance maximum imposée par l'utilisateur; Les périmètres Pk et Pk' sont presque égaux, c'est-à- dire que leur différence est inférieure à un seuil prédéterminé. La vitesse Vk d'un contour Ck reconnu est alors déduite du calcul du déplacement du barycentre Ceci est possible seulement grâce aux traitements précédents: en effet, comme les contours ont subi un lissage, si le barycentre se déplace, on est sûr que ce déplacement est représentatif d'un déplacement de l'objet. La mise en oeuvre du procédé selon l'invention s'effectue très avantageusement par ordinateur, en raison des vitesses rapides de traitement. REVENDICATIONS 1 Procédé de pistage d'éléments déformables et/ou aux contours fortement bruités, à partir d'images composées d'un nombre entier N de lignes et M de colonnes, et d'un nombre Nx M de pixels codés suivant un nombre entier Q de valeurs de luminance, le procédé étant caractérisé en ce qu'il consiste à: effectuer, sur chaque image, un pré-traitement ( 1) de mise en forme de l'image afin de lisser les contours; extraire ( 2) les contours de façon à obtenir des contours fermés et dont les épaisseurs ne dépassent pas un pixel; extraire ( 3), pour chaque contour fermé, des paramètres significatifs des contours; comparer, d'une image à l'autre, les paramètres obtenus de façon à reconnaître ( 4) la forme d'un élément, puis en déduire ( 5) sa vitesse. 2 Procédé de pistage selon la revendication 1, caractérisé en ce que le pré-traitement ( 1) de mise en forme de l'image consiste en: un seuillage ( 11) de l'image à un seuil prédéterminé, permettant de mettre tous les pixels dont le code de luminance est supérieur à un seuil prédéterminé à O, et tous les autres pixels à (a -1); au moins une succession d'une érosion ( 13) et d'une dilatation ( 14) de l'image donnant un lissage des contours. 3 Procédé de pistage selon la revendication 2, caractérisé en ce que la succession d'une érosion ( 13) et d'une dilatation ( 14) de l'image est effectuée par: une première convolution ( 121) de l'image par une matrice unitaire de dimension P, P étant un entier impair inférieur aux entiers N et M; un premier seuillage ( 122) de l'image convoluée à un seuil sensiblement égal à Q/2; une première inverse vidéo ( 123) de l'image seuillée; une seconde convolution ( 121 ') de l'image inversée par ladite matrice unitaire; un second seuillage ( 122 ') de la seconde image convoluée à un seuil sensiblement égal à Q/2; une seconde inverse vidéo ( 123 ') 4 Procédé de pistage selon la revendication 3, caractérisé en ce que la première et la seconde convolutions consistent en: une convolution ( 124) d'un pixel i, j de luminance L (i, j) par ladite matrice unitaire; un stockage ( 125) du résultat L' (i, j) de la convolution; un remplacement ( 126) de la luminance L (i, j) par la luminance L' (i, j) dès que le pixel i, j n'est plus utilisé dans les convolutions. Procédé de pistage selon l'une quelconque des revendications précédentes, caractérisé en ce que l'extraction ( 2) des contours consiste en: une convolution ( 21) de l'image issue du pré-traitement ( 1) par une matrice de Laplace de coefficients - 1 O -1 4 -1 O -1 O - à un facteur multiplicatif cc près. un seuillage ( 22) de l'image convoluée à un seuil sensiblement égal à Q/2. 6 Procédé de pistage selon la revendication 5, caractérisé en ce que ladite convolution ( 21) consiste en: une convolution ( 211) d'un pixel i, j de luminance L (i, j) par ladite matrice de Laplace; un stockage ( 212) du résultat L' (i, j) de la convolution; un remplacement ( 213) de L (i, j) par L' (i, j) dès que le pixel i, j n'est plus utilisé dans les convolutions. 7 Procédé de pistage selon l'une quelconque des revendications précédentes, caractérisé en ce que les paramètres significatifs des contours sont constitués par le périmètre Pk et le centre de gravité Gk de chaque contour Ck. 8 Procédé de pistage selon la revendication 7, caractérisé en ce que l'extraction des périmètres Pk des contours Ck consiste à: tester, de manière récursive, chaque pixel des contours Ck en cherchant dans un ordre déterminé, lesquels de ses huit voisins sont allumés; associer à chaque pixel, une variable d'état pouvant être dans les quatre états suivants; Etat O: pixel non testé; Etat 1: pixel appartenant au contour du pixel testé mais n'ayant pas encore été testé; Etat 2: pixel appartenant au contour du pixel testé et ayant subi le test; Etat 3: pixel appartenant à un contour précédent compter, lorsque le test est fini, tous les pixels pour lesquels la variable d'état est dans l'Etat 2. 9 Procédé de pistage selon la revendication 8, caractérisé en ce que l'ordre prédéterminé correspond au balayage de l'écran. Procédé de pistage selon l'une quelconque des revendications 7 à 9, caractérisé en ce que les barycentres Gk sont déterminés par leurs abscisses et leurs ordonnées, en effectuant respectivement la moyenne des abscisses et la moyenne des ordonnées des pixels des contours Ck. 11 Procédé de pistage selon la revendication 10, caractérisé en ce que la forme d'un élément est reconnue ( 4) si, pour deux images traitées successivement, les deux périmètres Pk- et Pk trouvés sont presque égaux et si les deux centres de gravité Gk' et Gk sont proches. 12 Procédé de pistage selon la revendication 11, caractérisé en ce que la vitesse d'un élément est déduite du déplacement du centre de gravité du point Gk' au point Gk.