1 Analyse de similarité de trajectoires Laurent Etienne, Thomas Devogele Institut de Recherche de lEcole Navale {laurent.etienne,thomas.devogele}@ecole-navale.fr

1

Analyse de similarité de trajectoires

Laurent Etienne, Thomas DevogeleInstitut de Recherche de l’Ecole Navale

{laurent.etienne,thomas.devogele}@ecole-navale.frParis, Décembre 2008

Outil d'aide aux décideurs concernant le suivi de navires : détection de trajectoires inhabituelles

2


Contexte maritime

Contexte Augmentation du trafic maritime

international Routes maritimes optimisées

(temps, coûts, sécurité) Généralisation du suivi des navires (AIS) Conservation longue durée des trajectoires dans des bases de données + outils d’analyse spatio-temporelle

Problématiques de sécurité Déplacement relatif de navires, croisements, collisions Simulation du comportement et prédiction du déplacement futur Détection des navires au comportement inhabituel

3


Problématique

• Objectif– Détecter en temps réel les trajectoires de navires se comportant

d'une façon inhabituelle par rapport aux trajectoires des navires de même type suivant le même itinéraire

– Qualifier le comportement inhabituelle• Définir

– Des route type à partir des données historiques • fouille de données

– Des outils de comparaison de chaque nouvelle position en temps réel

• par rapport à cette route type• Opérateurs de comparaison : Sur la route à l’heure, en Retard, en

Avance, à droite, A gauche

4


Méthodologie

5


Cas d’étude

BD AIS zone de Brest Données stockées depuis Mai 2007 4 821 447 positions AIS 1005 Navires

Définition d’un route type Itinéraire Brest Arsenal → Lanvéoc Ecole

Navale Type de navires : Transports de passagers

Les Transrades (5 navires)

6


Calcul de routes types

Étapes 1) Sélection des trajectoires ayant le même itinéraire

2) Retrait des trajectoires erronées et incomplètes

3) Recalage des points de départ/arrivée

4) Filtrage des trajectoires (Douglas & Peucker temporel)

5) Changement de repaire temporelle– Date → durée depuis le départ

6) Normalisation temporelle des trajectoires à la durée médiane

7) Calcul statistique de la route type (médiane des points à tous les temps normalisés)

7


Préalable : le Graphe de zones

Définition de zonesPorts, isthmes, DST

Définition d’un Graphe de zones

orienté non completUn itinéraire

= une suite d’arcsAnalyse de chaque arc

Pour notre exemple :A → F

8


Les groupes homogènes de trajectoires

Groupe homogène de trajectoires d'objets de même type suivant le même itinéraire: GHT

IT

Pour l’exemple

GHT Brest Ecole navale,

Navires à Passagers

634 Trajectoires

9


Filtrage des trajectoires erronées

554 Trajectoires conservées

10


Recalage spatial

Recalage spatial des points de départ et d’arrivée Calcul du point d’intersection entre les points de

départ des trajectoires et une ligne représentant la ligne de départ de la route type (frontière de la zone)

Objectif : Filtrage des manœuvres d’accostage Biais de 200 m

11


Filtrage des trajectoires

Algorithme de Douglas & Peucker spatio-temporel

Seuls les points ayant une variation importante du CAP ou de la vitesse sont conservés

Taux de compression avec un seuil à 10 m : 84,54 %

12


Normalisation temporelle

Objectif : Travailler en durée depuis le départ Travailler en % de cette durée

Pour l’exemple : Durée médiane de l'itinéraire : 23m21s

Normalisation temporelle Toute les trajectoires commencent à t début = 0

Toutes les trajectoires finissent à t fin = durée moyenne

Recalage temporelle

13


Méthodologie

14


Calcul de la route type

Agrégation spatiale- Pour chaque temps de chaque position

Interpolation de la position des autres trajectoiresCalcul d’un position médiane

- Ordonnancement temporelle des positions médianes- Filtrage

ExemplePosition à un même temps : points rougesroute type en jaune

15


Couloirs spatio-temporelles

• Pour chaque route type

– Définir un couloir spatial• Une position à l’intérieur du couloir est considérée comme suivant

la route

• Largeur fonction de l’espacement des trajectoires associées

• Non symétrique

• Approche statistique

– Définir un couloir spatio-temporel• Après une durée de d secondes, une position suivant la route doit

être dans une zone autour de la position de la route type à d.

• Définition de bornes de retard et d’avance acceptables

• Non symétrique

• Approche statistique

16


Calcul du couloir spatial

Pour chaque position de la route type Utilisation d’une droite

perpendiculaire au cap Intersection de cette droite avec

les trajectoires du GHT Classement par coté de la route

type (droite/gauche) Classement par distance à la

route type Sélection des positions

correspondant au neuvième décile (90%) à droite et à gauche de la route type

Stockage dans la BD de connaissance du couloir (ligne droite et ligne gauche)

Exemple Couloir en bleu

17


Calcul du couloir temporel

Pour les positions (issues de intersection) à l’intérieur du couloir spatial Classement par temps

(avance/retard) Classement par écart

temporelle Sélection des écarts

correspondant au neuvième décile (90%)

Stockage dans la BD de connaissance des bornes

18


Visualisation 3D d’un couloir spatio-temporel(temps : axe altitude)

19


Analyse Temps Réel

• Analyse temps réel (perspective)– Une nouvelle position AIS est

reçue– Associer cette position à un

arc– Calculer la durée depuis la

zone de départ– Comparer la position avec les

5 zones de la route type à cette instant

?

20


Conclusion & Perspectives

Bilan Définition d’une méthode de fouille de données

spatio-temporelle pour définir pour chaque itinéraire, une route type et un couloir spatio-temporel

Expérimentation sur les navires à passagers entre Brest et l’Ecole Navale

3 min 31 seconde pour le calcul de la routes et des couloirs (85 % temps CPU consacré à l’extraction des trajectoires du GHT)

Perspectives Analyse spatio-temporelle des positions en temps réels Analyse spatio-temporelle de parties de trajectoires

Louvoyer, vitesse irrégulière, couper un virage, … Appariement de positions à une route type sans

destination renseignée Validation sur d’autres zones

21


Questions ?

Merci de votre attention

Avez vous des questions ?

{laurent.etienne,thomas.devogele}@ecole-navale.fr

22


Analyse de résultats

Différences entre moyenne et médiane

23


Analyse de résultats

Calcul du couloir (médianes 25% 50% 95%)

24


Problématiques

Durées de calcul ETAPE 1 : SELECTION DES POINTS DE DEPART ET ARRIVEE DANS LA BASE DE

DONNEES T +12110 ms ETAPE 2 : CREATION DES TRAJECTOIRES A PARTIR DE LA BASE DE

DONNEEES T +17306 ms ETAPE 3 : RECALAGE DES POINTS DE DEPART ETAPE 4 : RECALAGE DES POINTS D'ARRIVEE ETAPE 5 : FILTRAGE DES TRAJECTOIRES T +19611 ms 649 trajectoires trouvées 521 trajectoires utilisables 128 trajectoires ignorées Durée Max : 0:29:55 Durée Min : 0:18:1 Durée Moy : 0:21:59 ETAPE 6 : NORMALISATION TEMPORELLE DES TAJECTOIRES ETAPE 7 : CALCUL ET MISE A JOUR DES CAPS ET VITESSES T +19852 ms ETAPE 8 : CALCUL DE LA ROUTE TYPE (MOYENNE/MEDIANE) T +30390 ms ETAPE 9 : POUR TOUS LES POINTS MOYENS : INTERPOLATION SPACIALE T

+211644 ms

25


Objectifs secondaires

• Sélectionner les trajectoires de navires de même type ayant le même itinéraires (idéalement dans des conditions de navigation similaires)

• Calculer des routes types suivi par le plus grand nombre de ces navires

• En déduire des couloirs spatio-temporels de navigation permettant de qualifier la trajectoire d’un navire (sur la route, en avance, etc...)

• Comparer des trajectoires ayant le même itinéraire à un instant ou sur une durée

• Détecter en temps réel des comportements inhabituels de navires suivant une route type

• Souligner visuellement les trajectoires de navires ayant un comportement inhabituel

Documents

1 Analyse de similarité de trajectoires Laurent Etienne, Thomas Devogele Institut de Recherche de lEcole Navale {laurent.etienne,thomas.devogele}@ecole-navale.fr