10
Extraction de route dans une image à très haute résolution spatiale M. Naouai 1,2 , A. Hamouda 1 et C.Weber 2 1 Faculté des sciences de Tunis, Campus Universitaire el Manar DSI 2092 Tunis le Belvédaire-Tunisie Unité de recherche URPAH [email protected], [email protected] 2 Laboratoire Image et Ville UMR7011-CNRS-Université Louis Pasteur 3rue de l’Argonne F-67000 STRASBOURG [email protected], [email protected] Résumé La disponibilité d’image satellites à très haute résolution spatiale au dessus de zones urbaines est récente. Elle ouvre de nouvelles possibilités pour l'extraction des dispositifs linéaires tels que les routes. La très haute résolution spatiale permet aussi une représentation réelle des routes sur une carte, mais engendre par ailleurs une augmentation significative de bruit. Cet article propose une méthode de détection de route n’utilisant que l’image numérique comme source d’information. Elle permet de détecter et de déterminer à la fois l’orientation des routes en exploitant quelques unes de leurs propriétés intrinsèques :la faible variance du niveau de gris, la faible ou forte luminance moyenne, la présence de fortes courbures dans la direction orthogonale. En outre, une combinaison adéquate de ces caractéristiques, calculée sur un nombre relativement important de supports directionnels orientés fournit, sur des images réelles, une estimation précise de l’orientation locale des structures linéiques. Il est alors possible donc de suivre et d’extraire les lignes de crête présentes sur une image, en effet la méthode utilise une contrainte géométrique forte afin de ne pas dépendre d’un modèle de profil radiométrique de la route qui est trop variable en milieux urbain. Mots clés route, extraction, haute résolution, diffusion anisotrope, détection de contour . 1 Introduction L'interprétation des images constitue pour les cartographes un outil très important, et parfois indispensable, pour optimiser le temps passé sur le terrain tout en améliorant d'une façon très sensible la précision du document cartographique final. L'étendue des surfaces à cartographier et les délais de mise à jour font du développement d'outils algorithmiques de détection d'items cartographiques un enjeu important et indispensable.

Article extraction de route

Embed Size (px)

Citation preview

Page 1: Article extraction de route

Extraction de route dans une image à très haute résolution spatiale

M. Naouai1,2 , A. Hamouda1

et C.Weber2

1 Faculté des sciences de Tunis, Campus Universitaire el Manar DSI

2092 Tunis le Belvédaire-Tunisie

Unité de recherche URPAH [email protected], [email protected]

2Laboratoire Image et Ville UMR7011-CNRS-Université Louis Pasteur

3rue de l’Argonne F-67000 STRASBOURG

[email protected], [email protected]

Résumé La disponibilité d’image satellites à très haute résolution spatiale au dessus de zones urbaines est récente. Elle ouvre de nouvelles possibilités pour l'extraction des dispositifs linéaires tels que les routes. La très haute résolution spatiale permet aussi une représentation réelle des routes sur une carte, mais engendre par ailleurs une augmentation significative de bruit. Cet article propose une méthode de détection de route n’utilisant que l’image numérique comme source d’information. Elle permet de détecter et de déterminer à la fois l’orientation des routes en exploitant quelques unes de leurs propriétés intrinsèques :la faible variance du niveau de gris, la faible ou forte luminance moyenne, la présence de fortes courbures dans la direction orthogonale. En outre, une combinaison adéquate de ces caractéristiques, calculée sur un nombre relativement important de supports directionnels orientés fournit, sur des images réelles, une estimation précise de l’orientation locale des structures linéiques. Il est alors possible donc de suivre et d’extraire les lignes de crête présentes sur une image, en effet la méthode utilise une contrainte géométrique forte afin de ne pas dépendre d’un modèle de profil radiométrique de la route qui est trop variable en milieux urbain.

Mots clés route, extraction, haute résolution, diffusion anisotrope, détection de contour .

1 Introduction

L'interprétation des images constitue pour les cartographes un outil très important, et parfois indispensable, pour optimiser le temps passé sur le terrain tout en améliorant d'une façon très sensible la précision du document cartographique final. L'étendue des surfaces à cartographier et les délais de mise à jour font du développement d'outils algorithmiques de détection d'items cartographiques un enjeu important et indispensable.

Page 2: Article extraction de route

2 M.Naouai, A.Hamouda et C.Weber

De nombreuses méthodes ont été développées pour répondre au problème de l’observation de la terre à partir d'images satellitaires et aériennes à très haute résolution, notamment dans le cas particulier de l’extraction de route.

L’extraction des routes à partir des images de télédétection, représente toujours un défi important pour les algorithmes informatiques, alors que pour les interprètes humains c’est une tâche immédiate. Dans cet article une méthode novatrice est présentée pour guider l’extraction des routes dans une scène urbaine à partir d’une unique image complexe à très haute résolution spatiale.

Nous présentons dans cet article une méthode de détection de route, tenant compte de la grande variabilité de la scène concernée. Généralement dans une scène urbaine, le revêtement des routes apparaît comme lisse. De même que pour beaucoup d'autres caractéristiques topographiques, il existe des définitions multiples qui conduisent à autant de méthodes algorithmiques de détection. Parmi celles-ci, des méthodes géométriques [1] s'appuient sur le calcul de dérivées partielles du niveau de gris jusqu'au troisième ordre pour extraire les points de plus forte courbure locale. Dans le cas d'images comportant de nombreux détails proches des lignes à détecter, l'estimation des différentes dérivées est fortement perturbée et conduit à des résultats généralement peu satisfaisants. La détection de lignes de crête étant un problème mal posé, l'emploi de méthodes heuristiques tel que l'opérateur directionnel que nous proposons, se justifie pleinement.

Par ailleurs, les filtres directionnels utilisés dans le traitement des images offrent beaucoup de champs d’application : analyse de texture, segmentation, détection de contours [2,17] ou de motifs particuliers (points anguleux, T jonctions), rehaussement [3], filtrage [7]... Dans le domaine spatial, il s’agit de calculer une énergie en fonction de l’orientation [4] afin de rechercher, par exemple, une direction dominante. Il en est de même dans cet article où nous nous attachons à rechercher localement des directions privilégiées correspondant à des segments, des structures linéiques fines telles que des lignes de crête. La deuxième partie, quant à elle, décrit un opérateur local directionnel très sélectif qui permet de mettre en évidence des orientations locales multiples (T-jonctions, ...). Des résultats obtenus expérimentalement sont présentés dans la dernière partie. La précision et la performance de notre détecteur de route sont validées à travers une image satellite (Quickbird) d’une résolution de 60cm.

2 Prétraitement

2.1 filtrage

Le but principal du filtrage dans notre cas est de rendre l’homogénéité sur la route au même niveau. Celle-ci va nous permettre d’introduire rapidement les notions de diffusions anisotropes dans le cas le plus simple, à savoir celui d’une image fixe en niveaux de gris.

2.1.1 Diffusion anisotrope

Soit l’image , qu’on définit comme une application bornée de qui associe

au pixel son niveau de gris .

IyxI ),(

)y

2

,(x ),( yxI est le domaine de l’image. Notons 0), Iyx0 (I

La diffusion anisotrope, telle que Perona et Malik l’introduisent dans [12], est une opération de filtrage non linéaire qui permet de faire une distinction bruit/contour. Elle se traduit sous la forme du problème aux limites suivant :

Page 3: Article extraction de route

3

)),,()),,(((),,(

tyxItyxIcdivt

tyxI

(),()0,,( 0 yxIyxI 1)

0 I

n

Avec le bord de et un vecteur nor n mal extérieur à et , appelé fonction de

)(c)0 diffusion t une fonction on n ative, monotone décroissante, telle e 1(c . Il s’agit cette fois

d’une diffusion adaptative, dont le comportement est fonction des variations locales de l’intensité de l’image, grâce à la fonction )(c : lissage fort dans les zones à faible gradient (zones homogènes), et faible dans les zones à fort gradient (contours). Un seuil k permet de distinguer les zones à faible gradient de celles à fort gradient. Perona-Malik proposent par exemple la fonction suivante :

, es n ég qu

))(exp()( 2

k

IIc (2)

Le choix de ce seuil k n’est d’ailleurs pas évident ; il peut être fixé arbitrairement ou en estimant le

2.2 Détection de contour

Pour commencer, une détection de contours est réalisée par un filtre de Canny-Deriche [10].

calisation du point contour

que. La maximisation de ces critères conduit à la

bruit. Pour le déterminer, Perona et Malik proposent de se baser sur un histogramme cumulé du gradient [9].

Canny a proposé en 1983 une étude théorique de la détection de contour. Son étude s'est limitée au cas de la dimension 1, c'est à dire la détection des variations dans un signal bruité.

Trois critères doivent valider un détecteur de contour :

• Détection : robustesse au bruit

• Localisation : précision de la lo

• Unicité : une seule réponse par contour

A chaque critère est associée une formule mathématirésolution d'une équation différentielle dont la solution est le filtre h, qui permet la détection du contour, i.e. la position du contour correspond à :

(IMax ))(xh avec :

(3)

)sin()cos()sin()cos()( 4321 xeaxeaxeaxeaxh xxx x

Page 4: Article extraction de route

4 M.Naouai, A.Hamouda et C.Weber

En un premier temps on va réduire le bruit de l'image originale avant d'en détecter les contours. Ceci permet d'éliminer les pixels isolés qui pourraient induire de fortes réponses lors du calcul du gradient, conduisant ainsi à de faux positifs.

Un filtrage gaussien 2D est utilisé (voir Lissage de l'image), dont voici l'opérateur de convolution :

2

22

222

1),(

yx

eyxG

(4)

Algorithme de détection de contour 1. Convoluer l’image f avec une gaussienne de variance σ.

2

22

222

1),(

yx

eyxG

2. Estimer les directions normales n pour chaque pixel de l’image.

)(

)(

IG

IGn

(5)

3. Localiser le contour par «non-maximal suppression». (Les contours sont donc localisés aux maxima locaux de l’image h convoluée avec l’opérateur G )

0)(

2

2

n

IG

(6)

4. Calculer la magnitude du contour

)( IGIG avec yx GGG (

5.

7)

Eliminer les erreurs de bruit par seuillage hystérésis. de σ.

L'im sée est employée dans notre algorithme, par la suite, pour le calcul de la variance des

6. Répéter les pas 1 à5 pour des valeurs ascendantes

age diffupixels dans l'image.

Page 5: Article extraction de route

5

Figure 1 : Image Originale contour détecté par l’algorithme

de Canny

2.3 Extraction de vallée

Les définitions concernant les Vallée dans la littérature en vision par ordinateur prennent des points de départs très variés. Plusieurs termes tels que ridge, valley [12, 13, 14], watershed [15], crease, seperatrice [16] ont été utilisés pour le concept vallée, avec des approches et des définitions différentes.

Nous présentons dans cette section deux familles de définitions de vallée : les définitions à base de la fonction de hauteur caractérisant plutôt le changement du signal de l'image ; les définitions à base des courbures principales représentant les propriétés intrinsèques structurales de la surface. Ces définitions faites en 2D peuvent être généralisées à un espace à n dimensions. Notons que toutes ces définitions de vallée s'appliquent à une surface sans prendre en compte la notion d'échelle. Une mesure de vallée comportant (la fonction de hauteur, la courbure de la courbe de niveau, la courbure principale, le Laplacien, etc…) admet un extremum local en (x; y) dans une direction d. Si celle-là est plus grande ou plus petite que celle en d'autres points voisins, l'espace des directions est discrétisé. En ce point, Comme l'espace des directions est discrétisé, cette étape n'est pas difficile.

3 Détection de route

D’après les observations, une grande variabilité d’aspect de la route dans l’image existe, il est donc difficile de trouver un modèle générique de la route. Toutefois, quelques caractéristiques majeures peuvent êtres dégagées. La plupart des méthodes d’extraction de routes se basent sur des modèles simples de routes. Par définition, les caractéristiques principales de ces modèles sont communes à beaucoup d’auteurs, à savoir que la route a une radiométrie homogène le long de son axe, et présente un contraste par rapport à son environnement. De plus la longueur de la route et sa courbure sont supposées, varier lentement. Donc une route est une structure linéaire orientée qui correspond localement à un ensemble de pixels disposés selon une direction particulière et présentant des caractéristiques similaires, pour la détecter nous employons un ensemble de supports directionnels de rayons constants [9](figure 2).

Page 6: Article extraction de route

6 M.Naouai, A.Hamouda et C.Weber

Figure 2 : supports directionnels de rayon r

L’algorithme va permettre de rechercher de part et d’autre de la direction initiale (orientation figure 2) en faisant osciller l’angle autour de cette direction. Sur chacun de ces supports, des paramètres caractéristiques seront calculés. D’autant que, Ces supports sont constitués d’un nombre très variable de pixels (figure 2). Pour les faibles rayons envisagés, ceci a une forte incidence sur la valeur des paramètres qui y sont calculés. Pour dépasser ces problèmes et octroyer des propriétés isotropes au détecteur de route, nous allons décrire le voisinage d’un pixel par un faisceau de rayons uniformément répartis, composés chacun d’un nombre identique de points régulièrement espacés (figure 3).

Figure3 : Ensemble de supports directionnels interpolés représenté dans le cas d’un rayon de 7 pixels

L’intensité de chaque point ainsi définit est estimée par interpolation bilinéaire en fonction de celle des quatre pixels voisins [9]. Du fait du lissage engendré par cette interpolation, les valeurs des points interpolés sur un rayon sont généralement plus homogènes que celles des pixels appartenant au support directionnel discret sensiblement équivalent. Ceci procure une meilleure continuité aux paramètres directionnels calculés à partir de ces valeurs.

3.1 Paramètres caractéristiques

Une route est un ensemble d'éléments de contours dans une étendue spatiale bornée, possédant des orientations privilégiées, et contrastés par rapport au bord. Le système d’extraction de route doit générer un réseau tenant compte de la plupart de ses spécifications. A partir de tous ces différents points de vue, quelques caractéristiques majeures représentées dans un vecteur d’état peuvent être dégagées [18]

3.1.1 Contraste

La structure des routes étant souvent contrastées par rapport à leurs voisinages, clairs ou sombres, la moyenne des niveaux de gris ou son écart à une moyenne locale constitue un attribut caractéristique déjà utilisé dans l’algorithme Rotating Kernel Min-Max Transformation [5] et dans [2].

Page 7: Article extraction de route

7

Figure 4 : support de direction i

Pour un support donné (figure 4), dans la direction i, ce premier attribut s’exprime par :

)( 1

)(1

,

r

jjii IMI

rM (8)

I() représente l’intensité d’un pixel

où j est le numéro du point sur le support de direction i

I est l’intensité locale moyenne calculée sur un voisinage de taille PxP centré sur le

pixel traité

3.1.2 Homogénéité

L’homogénéité des niveaux de gris [8] est un autre indicateur pertinent, c’est une information locale et correspond au caractère uniforme d'une région homogène. Ce critère prend en compte la différence de radiométrie entre le point x du support et celle d’un voisinage de taille PxP (moyenne réactualisée à chaque nouveau point intégré), permettant de favoriser la direction de radiométrie la plus homogène. Le fait de réactualiser la moyenne de radiométrie implique d’être suffisamment certains que chaque point intégré appartienne réellement à une route. Il s’agit tout comme dans la recherche du domaine de Nagao [5] possédant la plus faible variance (mais à des fins de filtrage) d’identifier la direction la plus homogène. Elle se traduit par :

2

1,, )()(

1)(

r

jjijii MIMI

rM (9)

L’objectif d’incorporer une telle caractéristique locale dans l’opérateur de détection de route est d’assurer une bonne robustesse aux occlusions.

3.1.3 Courbures Les lignes de crête ont la particularité de présenter (figure 5) dans une direction orthogonale à leur orientation des courbures importantes dont la valeur peut être approchée par le calcul d’une dérivée seconde.

Figure 5 : courbure orthogonale à une ligne de crête

Page 8: Article extraction de route

8 M.Naouai, A.Hamouda et C.Weber

La courbure en un point M, pour une ligne claire (arête) s’exprime par : M

)()()(2)( QIPIMIM (10)

Cette courbure calculée le long du profil d’une ligne assez épaisse fait parfois apparaître deux extrema situés de part et d’autre de la crête véritable (figure 5). Nous lui substituons donc une nouvelle estimation de la courbure, qui ne présente pas le problème de délocalisation observable sur la figure (5.b), sous la forme suivante :

)()(),()()(' QIMIPIMIMinM (11)

Il est possible d’exprimer cette nouvelle courbure en fonction de la précédente :

)()()(2

1)(' QIPIMM (12)

Cette décomposition fait apparaître un terme régulateur qui diminue fortement la courbure lorsqu’elle n’est pas estimée précisément au sommet de la ligne de crête. Dans une direction donnée, l’intensité totale des courbures orthogonales à une ligne claire est finalement approchée par :

r

jjijijijii QIMIPIMIMin

rM

1,,,, )()(),()(

1)( (13)

Pour une ligne sombre c’est à dire vallée, son expression est :

r

jjijijijii MIQIMIPIMin

rM

1,,,, )()(),()(

1)( (14)

3.2 Opérateur de détection de route

Notre opérateur de détection de route prend en considération chacun des trois critères définis précédemment à travers une combinaison linéaire calculée sur les supports de la figure 3.

Son expression est :

(15) positive constante dessont et ,

)()()()(

MMMMA iiii

Algorithme de détection de route : 1. Prétraitement :(filtrage+ détection de contour) 2. Initialisation (recherche de l’ensemble de pixel jugé vallée V) 3. t=1

Vi4. Répeter pour chaque pixel

)(

)(

)(

)(i

M

M

M

t

i

i

i

5. Calcul de vecteur caractéristique

6. Calcul de cout )()()()( MMMMA iiii

7. Le chemin ayant le coût maximum sera considéré le chemin sur la route. 8. Ce chemin sera stocké et considéré en tant que prochaine fenêtre cible pour la détection de route. 9. t=t+1

jusqu'à t= =Card(V)

Page 9: Article extraction de route

9

4 Résultat :

Pour tester notre algorithme nous avons utilisé une image Quickbird (HR) de résolution 60cm

Figure 6 : Résultat de détection

Nous pouvons noter que les routes semblent bien extraites, car notre opérateur de détection permet de distinguer les différentes composantes de structures remarquables et réelles (T-jonctions, structures en Y, ...). Mais on remarque aussi qu’il y a une confusion entre les routes et quelques bâtiments dans la scène, une confusion due au vecteur caractéristique qui est semblable à celui de la route en plus l’algorithme ne peut pas juger la validité des points d’entrés lors de l’initialisation, donc des fausses alarmes génèrent bien évidement de mauvaise détection. L’autre inconvénient c’est que les objets de faible taille qui génère une ombre faible sur la route laissent la détection difficile. Ce détecteur reste cependant sensible à l’orientation de la route car seulement cinq directions possibles sont évaluées.

Par ailleurs, le résultat final dépend impérativement de la taille du support directionnel et du fait qu’il fallait choisir un rayon assez modéré pour affiner le résultat.

5 Conclusion :

Dans cet article une méthode de détection de route appliquée sur une image satellite à très haute résolution spatiale a été déterminée. L’algorithme proposé utilise un support directionnel de rayon constant, prenant en compte plusieurs hypothèses sur les routes (la route est plus claire que son environnement, elle est homogène, a une structure linéaire et lisse, ne change pas brutalement de direction et sa largeur varie peu). Cinq masques sont définis et associés à une fonction de score mesurant conjointement l’homogénéité des niveaux de gris le long de la structure, la courbure et le contraste dans le voisinage. Chaque masque représente une direction différente, et le score maximum indique l’orientation de la route. La précision et la performance de notre détecteur de route sont validées à travers une image satellite Quickbird à très haute résolution. Ainsi, l'objectif de notre opérateur directionnel de détection de route est d’analyser les orientations locales de structures complexes et fines. Il permet aussi un suivi précis des routes et fournit des résultats satisfaisants et concrets.

Page 10: Article extraction de route

10 M.Naouai, A.Hamouda et C.Weber

Références

[1] O. Monga et S. Benayoun, "Using partial derivatives of 3D images to extract typical surface features" Computer Vision and Image Understanding, vol. 61, no. 2, pp. 171- 189, March 1995.

[2] E.P. Simoncelli and H. Farid, "Steerable wedge filters for local orientation analysis" - IEEE Trans. On Image Processing, vol. 5, no. 9, pp. 1377-1382, Sept. 1996.

[3] R. Kutka and S. Stier, "Extraction of line properties based on direction fields" - IEEE Trans. On Medical Imaging, vol. 15, no. 1, pp. 51-58, February 1996.

[4] W.T. Freeman and E.H. Adelson, "The design and use of steerable filters" - IEEE Trans. On Pattern Anal. Machine Intell., vol. 13, no. 9, pp 891-906, 1991.

[5] Y.K. Lee and W.T. Rhodes, "Scale- and rotationinvariant pattern recognition by a rotating kernel min-max transformation" - Optical Information Processing System and Architectures, vol. SPIE pp. 1347(17), July 1990.

[6] M. Nagao and T. Matsuyama, "Edge preserving smoothing" - CVGIP, vol. 9, pp. 394-407, 1979.

[7] F.F. Presetnik and M. Filipovic, "Adaptive median filter of images degraded by speckel noise" - Signal Processing IV, Lacoume et al Eds, Elsevier, Sept. 1988, pp. 651-654.

[8] J.L. Vila et Ph. Bolon, "Filtrage d’ordre adaptatif pour le prétraitement d’images naturelles", Quatorzième colloque GRETSI, Sept. 1993, pp. 563-566. 394

[9] D. Hall, F. Pelisson, O. Riff, and J. L. Crowley. Brand identi_cation using Gaussian derivative histograms. Machine Vision and Applications, 2004.

[10] R. Deriche, Using Canny's criteria to derive an optimal edge detector recursively implemented, Int. J. Computer Vision, Vol. 2, p. 15-20, Avril 1987.

[11] P. Perona and J. Malik, “Scale-space and edge detection using anisotropic diffusion,” IEEE transactions on Pattern Analysis and Machine Intelligence, vol. 12, no. 7, pp. 629–639, 1990.

[12] Robert M. Haralick. Ridges and valleys on digital images. Computer Vision, Graphics, And Image Processing, 22 :28.38, 1983.

[13] S. Chinveeraphan, R. Takamatsu, and M. Sato. Understanding of ridge-valley lines on image-intensity surfaces in scale-space. In Proc. of International Conference CAIP'95, Computer Analysis of Images and Patterns, Prague, Czech Republic, September 1995.

[14] D. Eberly. Ridges in Image and Data Analysis. Kluwer Academic Publishers, 1996.

[15] C. Steger. An unbiased detector of curvilinear structures. Technical report, Technische Universitat Munchen, July 1996.

[16] Antonio M. López, F. Lumbreras, J. Serrat, and J. J. Villaneuva. Evaluation of methods for ridge and valley detection. IEEE Transactions On Pattern Analysis and Machine Intelligence,21(4) :327.335, April 1999.

[17] O D'Hondt, L Ferro-Famil, E Pottier O D’Hondt,L.Ferro-Famil, E Pottier "Local orientation analysis of spatial texture from polarimetric SAR data" Geoscience and Remote Sensing Symposium, 2004. IGARSS '04. Proceedings. 2004 IEEE International, Vol. 2 (2004), pp. 1236-1239 vol.2.

[18] M. Donias et P. Baylou "Un opérateur directionnel multicritère pour la détection et le suivi delignes fines" SEIZIÈME COLLOQUE GRETSI — 15-19 SEPTEMBRE 1997 — GRENOBLE