1

Descoberta de Padrões de Perseguição em Trajetórias de Objetos Móveis

Fernando de Lucca Siqueira (fernandols@inf.ufsc.br)

2

Sumário Introdução e Motivação Objetivo Definições e Algoritmo Experimentos Conclusão

3

Introdução e Motivação Popularização de dispositivos móveis

GPS, celulares, redes de sensores, etc Geração de grandes volumes de um novo tipo

de dado Trajetórias de Objetos Móveis

Dado espaço-temporal Conjunto de pontos localizados no tempo e no espaço

na forma (tid,x,y,t)

4

Introdução e Motivação Aplicações

Monitoramento de tráfego urbano Monitoramento de animais Análise de movimento humano ...

Dados brutos Difícil análise Contém pouca informação e conhecimento interessante

5

Introdução e Motivação

T2T3

T1

F1F1 F1

F1

Flock (Laube, 2005)

Encontro (Laube, 2005)

Avoidance (Alvares et al., 2011)

CB-SMoT (Palma et al., 2008)

6

Objetivo

Definir o padrão de perseguição em trajetórias de objetos móveis e um algoritmo para

identificá-lo.

7

Aplicações Aplicações

Monitoramento de presos em regime semi-aberto Análise de comportamento de animais (ex: animais em

extinção) Estratégias de jogos de futebol Jogos de computador ...

8

O método proposto

9

O que é um padrão de perseguição? Dois objetos que andam próximos no espaço

em tempo similar, onde um é o alvo da perseguição e o outro o perseguidor, respeitando:

Tolerância de tempo (Δt) Distância entre os objetos (Δd) Duração mínima (Δc)

10

Candidato a Perseguição Análise de sub-trajetórias Tolerância de tempo Δt Intervalo de tempo entre S1 e S2

Tempos similares

1:001:05

1:10 1:151:20

1:25 1:30 1:351:40

1:451:501:55

1:051:10

1:151:201:25

1:301:35

1:321:40 1:45

1:50

2:00

1:33

2:05

11

Linha Representativa Otimizar o cálculo da distância Segmento de linha L formada pelo primeiro e

último ponto de uma sub-trajetória S = {p3, p4, p5, p6, p7} L = (p3,p7)

1:001:05

1:10 1:151:20

1:25 1:30 1:351:40

1:451:501:55

p1p2

p3

p7 p8

p12

Sub-Perseguição Entre candidatos a perseguição S1 e S2 Distância Δd Para cada ponto pi є S1, verifica distância com L2

Média das distâncias ≤ Δd

d1 d2 d3

1:001:05

1:10 1:151:20 1:45

1:501:55

1:051:10

1:151:201:25

1:30p1p2

q1q2

p7 p9

q8q11

1:50

2:002:05

12

13

Conjunto de Sub-Perseguições Duração maior que Δc

Dois algoritmos de perseguição Puro (Pure Tra-Chasing - PTC) Considerando velocidade (Speed Tra-Chasing - STC)

Perseguição

1:001:05

1:10 1:151:20

1:25 1:30 1:351:40

1:451:501:55

1:051:10

1:151:201:25

1:301:35

1:321:40 1:45

1:50

2:00

1:33

Sub-Perseguição 1 Sub-Perseguição 2 Sub-perseguição 3 2:05

14

Problemas do Padrão de Perseguição Problemas

Falsos Positivos (ex: um conjunto de carros em uma rodovia)

Objetivo da Perseguição

Possíveis Soluções Definir tipos de perseguição com características

diferentes Não considerar perseguição quando um alvo tem vários

perseguidores

15

Tipos de Perseguição Comportamento da perseguição

Como as trajetórias se comportam durante e depois da perseguição? O que o perseguidor faz quando o alvo para? O que acontece depois que as duas trajetórias se encontram?

Analisar Stops CB-SMoT (Palma, 2008)

Detetive Captura

AssaltoCaçada

16

Detetive

15:00

15:10 15:50

15:50

15:30

19:30

19:30

19:00

19:00

23:0023:00

Cada vez que o alvo para, o perseguidor para atrás As trajetórias não se encontram

17

Captura

15:00

16:20

16:20

15:20

15:10

15:30

20:00

20:0020:10

20:1023:10

23:10

Depois de um encontro, ambas as trajetórias andam juntas

Todos os locais de parada serão os mesmos

18

Assalto

15:00

15:10

16:20

16:2015:20

15:30 20:00 20:10

20:50

Depois do encontro, ambas as trajetórias se distanciam

19

Caça

15:00

16:2016:20

15:1015:20

15:30

19:00

Quando as trajetórias se encontram, o alvo é imobilizado

A trajetória do alvo termina depois do encontro

20

Algoritmo Tra-Chase

Candidato a

perseguição

Sub-perseguiçã

o

Verifica duração

Calcula stops

Verifica tempo do

stops

Detetive

≠

Nome

=

Trajetória do alvo termina

Trajetórias se afastam

Vários stops iguais

Caça

Assalto

Captura

T, Δd, Δt, Δc

Remover múltiplos

perseguidores

21

Trabalhos RelacionadosMétodo Perseguiçã

oFormalização

Tempo Velocidade

Distância

Duração

Algoritmo

TRA-CHASE X X Tolerância

X X X X

CDA (Cao 2006) Timestamp

X X X

MFF (Wachowicz 2011) Timestamp

X X X X

Dodge (2008) X* Timestamp

X X

Hornsby (2008) Timestamp

X

Legendre (2006) X X Timestamp

X X

22

Experimentos Quatro conjuntos de dados

Trajetórias sintéticas (Wachowicz et al. 2011) Trajetórias reais (Gincana em Amsterdã) Trajetórias geradas (Caminhada em Jurerê) Trajetórias geradas com tipos (Caminhada na

UFSC)

23

Gincana em Amsterdã Gincana em Amsterdã

Gincana móvel Perguntas sobre pontos históricos Alunos divididos em grupos (azul, verde, amarelo, etc)

Hipótese Aluno pode perseguir outro aluno de grupo diferente

24

Gincana em Amsterdã

25

Gincana em Amsterdã

26

Caminhada em Jurerê

27

Caminhada em Jurerê

28

Caminhada em Jurerê

29

Caminhada na UFSC Simulações diferentes:

Detetive Alvo deve andar e parar em pontos específicos Perseguidor deve perseguir o alvo evitando ser visto

Caça Alvo deve andar até ser interceptado pelo perseguidor e

desligar o gps Perseguidor deve perseguir alvo até certo ponto,

interceptar o alvo e seguir em frente

30

Caminhada na UFSC (Detetive)

31

Caminhada na UFSC (Detetive)

T1

T2

32

Caminhada na UFSC (Caça)

T3

T4

33

Caminhada na UFSC (Caça)

T4

T3

34

Análise dos Parâmetros Sobre o conjunto de dados gerados Conclusão:

Tempo Distância

Todos os parâmetros dependem da aplicação e dos dados

Exemplos: Perseguição em trajetórias de pedestres no centro de uma

cidade cheia ou vazia, onde as trajetórias fazem vários desvios;

Perseguição em trajetórias de pedestres numa praia deserta ou lotada;

Perseguição em trajetórias de estudantes no campus em horários diferentes.

35

Conclusão Trajetórias são dados difíceis de serem

analisados na forma como são gerados Trajetórias podem ter vários comportamentos

como Flock, avoidance, liderança, padrões periódicos e

perseguição Diferentes algoritmos extraem estes padrões

Contribuição do trabalho: Definição do padrão de perseguição e seus tipos Algoritmo para computá-lo Experimentos para avaliar o algoritmo Análise dos parâmetros

36

Trabalhos Futuros Outras formas de validação

Período do dia, local, etc... Definir medidas de confiança Utilizar informação de contexto Novos tipos de perseguição

Tipo do objeto, velocidade, etc... Aplicações em tempo real

37

Publicações Artigo publicado na revista internacional

Transactions in GIS (Qualis B2) Discovering Chasing Behavior in Moving Object

Trajectories Workshop de Teses e Dissertações do

SBBD/2011 Short paper publicado no GeoInfo/2011

CLASS-CHASE: Um Algoritmo para Classificação de Tipos de Padrões de Perseguição em Trajetórias de Objetos Móveis

Prêmio de segundo melhor artigo do evento

38

Descoberta de Padrões de Perseguição em Trajetórias de Objetos Móveis

Aluno: Fernando de Lucca Siqueira (fernandols@inf.ufsc.br)Orientadora: Drª Vania Bogorny

39

t1 t2t2 + Δt

1:001:05

1:10 1:151:20

1:25 1:30 1:351:40

1:451:501:55

1:051:10

1:151:201:25

1:301:35

1:321:40 1:45

1:50

2:00

1:33

para Δt = 5s

Candidato a Perseguição

T1

T2

p1p2

q1q2

40

target

stalker

1:001:05

1:10 1:151:20

1:25 1:30 1:351:40

1:451:501:55

1:051:10

1:151:201:25

1:301:35

1:321:40 1:45

1:50

2:00

1:33

Perseguição

41

Sub-Trajetória Trajetória

T = (p1, p2, .... pm) Sub-Trajetória S1 de uma trajetória T1

S1 = (pi, pi+1, ..., pi+n) onde pi є T1

1:051:10 1:15

1:201:25 1:30 1:351:40

1:451:501:55

1:101:15

1:201:251:30

1:351:32

1:40 1:451:50

2:00

1:33

1:00

1:05p1

p2p7 p8 p9

T1

T2

S1S2

42

Sub-Trajetória Trajetória

T = (p1, p2, .... pm) Sub-Trajetória S1 de uma trajetória T1

S1 = (pi, pi+1, ..., pi+n) onde pi+n.time ≤ pi.time+tj

1:001:05

1:10 1:151:20

1:25 1:30 1:351:40

1:451:501:55

1:051:10

1:151:201:25

1:301:35

1:321:40 1:45

1:50

2:00

1:33

Tempo de agrupamento tj = 10s

43

Definições

44

Candidate Chasing Entre duas sub-trajetórias S1 e S2 Time tolerance Intervalo de tempo entre S1 e S2

Seja p ponto de S1 e q ponto de S2 qm.time ≤ pn.time + Δt

45

T1 T2T2 + Δt

1:001:05

1:10 1:151:20

1:25 1:30 1:351:40

1:451:501:55

1:051:10

1:151:201:25

1:301:35

1:321:40 1:45

1:50

2:00

1:33

para Δt = 5s

Candidate Chasing

46

T1 T2T2 + Δt

1:001:05

1:10 1:151:20

1:25 1:30 1:351:40

1:451:501:55

1:051:10

1:151:201:25

1:301:35

1:321:43 1:45

1:50

2:00

1:33

para Δt = 5s

Candidate Chasing: Contra-Exemplo

47

Sub-Chasing Verifica distância de S1 com L2 e S2 com L1 Ambas sub-trajetórias devem estar perto da

Representative Segment Line

48

Pseudo Código

49

Pseudo Código

50

Pseudo Código

51

Pseudo Código

52

Experimento 1 Δd = 80m; Δt = 5min, Δc = 10min

53

Conclusão Definição do padrão de perseguição Algoritmo encontra padrões que outros não

encontram Nova técnica de agrupamento de sub-

trajetórias (tempo) Nova técnica de cálculo de distâcia

54

Trabalhos Relacionados Cao et al. 2006; Collocation Discovery

Algorithm Wachowicz et al. 2011; Finding moving flock

patterns among pedestrian through collective coherence

Dodge et al. 2008; Towards a taxonomy of movement patterns

Hornsby et al. 2008; Modeling motion relations for moving objects on road networks.

Legendre et al. 2006; Modeling mobility with behavioral rules

55

56

Conclusões Mesmos parâmetros com semânticas

diferentes