Sincronização Temporal em Redes de Sensores Móveis Baseada

Transcrição

Darlan Nunes de Brito
Sincronização Temporal em Redes de
Sensores Móveis Baseada em Análise de
Sequência de Imagens
Dissertação apresentada ao Curso de
Mestrado em Modelagem Matemática
e Computacional do Centro Federal de
Educação Tecnológica de Minas Gerais,
como requisito parcial à obtenção do título
de Mestre em Modelagem Matemática e
Computacional.
Orientador:
Prof. Dr. Flávio Luis Cardeal Pádua
Centro Federal de Educação Tecnológica de Minas Gerais
M ESTRADO EM M ODELAGEM M ATEMÁTICA E C OMPUTACIONAL
C ENTRO F EDERAL DE E DUCAÇÃO T ECNOLÓGICA DE M INAS G ERAIS
D IRETORIA DE P ESQUISA E P ÓS -G RADUAÇÃO
Belo Horizonte – MG
Outubro de 2008
Resumo
Esta dissertação de mestrado aborda o problema de se estimar a sincronização temporal entre sensores móveis distribuídos em uma rede ad hoc sem fio, por meio do
uso de técnicas de análise de sequências de imagens. Diferentemente dos métodos
existentes, os quais frequentemente se baseiam na ampla adaptação de algoritmos
originalmente projetados para redes com topologias estáticas, ou ainda no desenvolvimento de soluções de hardware e/ou software especialmente projetadas para redes de
sensores móveis, mas que levam a significativos consumos de energia e apresentam
baixa escalabilidade quanto ao número de sensores, esta dissertação de mestrado
propõe uma nova abordagem, potencialmente mais eficiente, a qual é baseada na
análise de sequências de imagens da dinâmica da cena monitorada pelos sensores.
Esta abordagem propõe que se reduza o problema de sincronizar um número genérico
N de sensores heterogêneos ao problema de estimar uma reta em ℜN+1 . Esta reta
captura todas as relações temporais entre os dados dos N sensores distribuídos na
cena e o vídeo da câmera responsável pela visualização dos mesmos. Mediante o
uso da abordagem desenvolvida neste trabalho, é possível projetar redes de sensores
que adquiram um conteúdo de informação mais amplo do ambiente, bem como minimizar a energia gasta por eventuais processamentos de dados de sincronização nos
nós sensoriais ou ainda na transmissão de tais dados pela rede. O presente trabalho
contempla a realização de simulações computacionais e a validação da técnica de
sincronização com dados reais obtidos por meio de câmeras instaladas no ambiente
de interesse bem como sensores instalados em robôs móveis, tais como GPS (Global
Positioning System), sonares, acelerômetros e sensores de profundidade.
PALAVRAS-CHAVE: Redes de sensores móveis, sincronização temporal, rastreamento
visual de objetos, calibração de câmeras, Random Sample Consensus.
Abstract
This work addresses the problem of estimating the temporal synchronization in sensor
networks, by using image sequence analysis of scene dynamics. Unlike existing methods, which are frequently based on adaptations of techniques originally designed for
wired networks with static topologies, or even based on solutions specially designed
for ad hoc wireless sensor networks, but that have a high energy consumption and a
low scalability regarding the number of sensors, this work proposes a novel approach
that reduces the problem of synchronizing a general number N of sensors to the robust
estimation of a single line in RN+1 . This line captures all temporal relations between
the sensors and can be computed without any prior knowledge of these relations. Experimental results show that our method can be successfully used to determine the
temporal alignment in wireless sensor networks.
KEY–WORDS: Mobile Sensors Network, Temporal Alignment, visual object tracking,
Camera Calibration, Random Sample Consensus
Lista de Abreviaturas e Siglas
ABNT Associação Brasileira de Normas Técnicas
GPSI Grupo de Pesquisas em Sistemas Inteligentes
NTP Network Time Protocol
RSSF Rede de Sensores Sem Fio
RBS Reference-Broadcast Synchronization
TDP Time Diffusion Protocol
LAN Local área network
E-RBS Efficient Reference Broadcast Synchronization
TPSN Time Synchronization Protocol for sensor networks
FTPS Flooding Time Synchronization Protocol
NASA North America Spatial Agency
COA College of Atlantic
UFMG Universidade Federal de Minas Gerais
RANSAC Random Sample Consensus
pixels picture elements
Sumário
Lista de Figuras
1 INTRODUÇÃO
p. 16
1.1 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 20
1.1.1 Monitoração de Habitat . . . . . . . . . . . . . . . . . . . . . .
p. 20
1.1.2 Agricultura de Precisão . . . . . . . . . . . . . . . . . . . . . .
p. 22
1.1.3 Monitoração de construções . . . . . . . . . . . . . . . . . . .
p. 25
1.2 Abordagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 26
1.3 Objetivos: Geral e Específicos . . . . . . . . . . . . . . . . . . . . . .
p. 28
1.4 Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 29
1.5 Organização do texto . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 30
2 TRABALHOS RELACIONADOS
p. 32
2.1 NTP - Network Time Protocol . . . . . . . . . . . . . . . . . . . . . . .
p. 32
2.2 TDP - Time-Diffusion Protocol
. . . . . . . . . . . . . . . . . . . . . .
p. 34
2.3 Algoritmos Mini-sync e Tiny-sync . . . . . . . . . . . . . . . . . . . . .
p. 38
2.3.1 Descrição do algoritmo . . . . . . . . . . . . . . . . . . . . . .
p. 39
2.3.2 Processamento de dados nos protocolos Tiny-sync e Mini-sync p. 42
2.4 Soluções específicas para RSSF . . . . . . . . . . . . . . . . . . . . .
p. 44
2.5 RBS - Reference Broadcast Synchronization . . . . . . . . . . . . . .
p. 44
2.6 E-RBS - Eficient RBS . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 47
2.7 FTPS - Flooding Time Synchronization Protocol
p. 48
. . . . . . . . . . . .
2.8 TPSN - Time Synchronization Protocol for Sensor Networks . . . . . .
p. 49
2.9 Considerações finais . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 52
3 FUNDAMENTAÇÃO TEÓRICA
p. 53
3.1 Sistemas de Processamento de Imagem
. . . . . . . . . . . . . . . .
p. 53
3.1.1 Passos fundamentais no processamentos de imagens digitais
p. 54
3.1.2 Aquisição de imagens digitais . . . . . . . . . . . . . . . . . . .
p. 56
3.1.3 Parâmetros das câmeras . . . . . . . . . . . . . . . . . . . . .
p. 58
3.2 Calibração de câmeras . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 63
3.2.1 Parâmetros diretos de calibração . . . . . . . . . . . . . . . . .
p. 63
3.3 Rastreamento de objetos . . . . . . . . . . . . . . . . . . . . . . . . .
p. 66
3.3.1 Representação do objeto . . . . . . . . . . . . . . . . . . . . .
p. 67
3.3.2 Detecção de objetos . . . . . . . . . . . . . . . . . . . . . . . .
p. 68
3.3.3 Rastreamento de pontos . . . . . . . . . . . . . . . . . . . . .
p. 71
3.3.4 Rastreamento de núcleo
. . . . . . . . . . . . . . . . . . . . .
p. 72
3.4 RANSAC - Random Sample Consensus . . . . . . . . . . . . . . . . .
p. 73
3.4.1 Avaliação de hipótese . . . . . . . . . . . . . . . . . . . . . . .
p. 75
3.4.2 Parâmetros para o RANSAC . . . . . . . . . . . . . . . . . . .
p. 75
3.4.3 Eficiência do RANSAC . . . . . . . . . . . . . . . . . . . . . . .
p. 76
4 TÉCNICA DE SINCRONIZAÇÃO PROPOSTA
p. 77
5 Resultados experimentais
p. 87
5.1 Sincronização de Sensores Móveis . . . . . . . . . . . . . . . . . . . .
p. 88
5.1.1 Seqüências Sintéticas . . . . . . . . . . . . . . . . . . . . . . .
p. 88
5.1.2 Seqüências Reais . . . . . . . . . . . . . . . . . . . . . . . . .
p. 91
5.2 Sincronização de Câmeras que não Possuem Sobreposição de Campos de Visão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 92
6 CONCLUSÃO
p. 107
6.1 Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 108
Referências Bibliográficas
p. 109
Lista de Figuras
1.1 Sugestão de utilização de sensores móveis em uma plantação de alfaces. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 17
1.2 Demonstração do desalinhamento temporal em uma cena composta
por dois sensores S1 e S2 visualizados por uma câmera c. Observa-se
que os quadros da câmera c e os dados do sensor S1 e S2 possuem
um desalinhamento temporal ∆T1 = 149 e ∆T12 = 194 respectivamente. p. 19
1.3 Monitoramento de um ecossistema (1) Sensores da rede sem fio para
monitoramento dentro do ninho. (2) Dispositivos de gravação e transmissão dos dados para um nó gateway. (3) Antena transmissora para
um notebook na estação de pesquisa. (4)-(5) Estação de pesquisa
que possui o link de dados com o satélite. (6)Sistema sugerido para
utilização de sensor móvel para monitoramento do ambiente não utilizado pela pesquisa original, (POLASTRE, 2003). . . . . . . . . . . .
p. 23
1.4 Montagem de uma cena composta por sensores movimentando-se
por uma plantação de soja. . . . . . . . . . . . . . . . . . . . . . . . .
p. 24
1.5 Ponte de Akashi Kaikyo no Japão que utiliza monitoramento estrutural
para: (1) validar suposições de projeto; (2) detectar anomalias de
carga; (3) prover informações de seguranças após desastres naturais;
(4)prover informações para manutenção.
. . . . . . . . . . . . . . . .
p. 25
1.6 Visão geral do cenário considerado pela metodologia proposta neste
trabalho. Um câmera de vídeo estática c visualiza um conjunto de
sensores móveis S = s1 , . . . , sn . . . . . . . . . . . . . . . . . . . . . . . .
p. 28
2.1 Arquitetura do sistema de sincronização utilizando TDP (SU; AKYILDIZ, 2005). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 35
2.2 Esta figura mostra que o protocolo TDP não atua durante todo o
tempo para sincronização da RSSF sendo que a sincronização é feita
durante um tempo τ segundos por um nó mestre com intervalos de δ
segundos (SU; AKYILDIZ, 2005). . . . . . . . . . . . . . . . . . . . . .
p. 36
2.3 Arquitetura TDP (SU; AKYILDIZ, 2005). . . . . . . . . . . . . . . . . .
p. 37
2.4 Exemplo da comunicação feita com a transmissão de uma mensagem
partindo do nó 1 sendo imediatamente retornada pelo nó 2 para o
nó 1 contendo o seu tempo local. Cada conjunto de transmissão e
recepção deste resulta em um conjunto de dados (t0 ,tb,tr ). . . . . . .
p. 41
2.5 Dependência linear e restrições impostas para a12 e b12 para 3 conjuntos de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 41
2.6 Análise do caminho crítico para um protocolo de sincronização tradicional (a) e RBS (b). (ELSON, 2003) . . . . . . . . . . . . . . . . . . .
p. 46
2.7 Gráfico comparativo para os protocolos de comunicação E-RBS e
RBS (LEE; YU; KWON, 2006). . . . . . . . . . . . . . . . . . . . . . .
p. 48
2.8 Modelo de sincronização para o método TSPN . . . . . . . . . . . . .
p. 50
3.1 Passos fundamentais no processamento de imagens (GONZALES;
WOODS, 2007). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 54
3.2 (a) Matriz bidimensional que representa uma imagem adquirida por
uma câmera digital cuja resolução é de 56 x 46 pixels. (b) Imagem
adquirida com uma câmera digital convertida para tons de cinza . . .
p. 57
3.3 Esquema de um sistema para a aquisição de imagens digitais (TRUCCO;
VERRI, 1998). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 58
3.4 A relação entre os sistemas de eixos coordenados da câmera e do
mundo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 60
3.5 Figura do alvo de calibração planar . . . . . . . . . . . . . . . . . . . .
p. 64
3.6 Modelo em perspectiva da câmera . . . . . . . . . . . . . . . . . . . .
p. 64
3.7 Representação de objetos.(a) Centróide, (b) múltiplos pontos, (c) Caminho retangular, (d) caminho elíptico, (e) Baseado em múltiplas partes,
(f) Esqueleto do objeto, (g) contorno do objeto com pontos, (h) Contorno completo do objeto, (i) silhueta do objeto (YILMAZ; JAVED;
SHAH, 2006).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 68
3.8 Detecção de objetos utilizando três métodos diferentes (a) Harris, (b)
KLT e (c) operadores SIFT
. . . . . . . . . . . . . . . . . . . . . . . .
p. 69
3.9 Exemplo da metodologia de mistura do modelo gaussiano para subtração de fundo (YILMAZ; JAVED; SHAH, 2006). . . . . . . . . . . . .
p. 70
3.10 Segmentação de uma imagem (a), Segmentação por deslocamentomédio (b) e Método de cortes normalizados(c) (YILMAZ; JAVED; SHAH,
2006). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 70
3.11 Figura de rastreamento por correspondência de pontos. (a) Todas as
possiblidades de associação de pontos no quadro t − 1 com pontos
no quadro t. (b) Conjunto único de associação desenhados com linha
negrito, (c) correspondência multiframe . . . . . . . . . . . . . . . . .
p. 72
3.12 Resultado do rastreamento on-line usado por Jepson et al. (JEPSON; FLEET; EL-MARAGHI, 2003). (a) A região do alvo em diferentes quadros. (b) A probabilidade do componente estável. Note que as
probabilidades em torno da boca e sombrancelha mudam, enquanto
eles permanecem a mesma e em outras regiões . . . . . . . . . . . .
p. 74
4.1 Visualização de dois sensores móveis na cena de interesse, os quais
descrevem trajetórias Q1 (·) e Q2 (·), cujas projeções no plano de imagem da câmera são denotadas por q1 (·) e q2 (·), respectivamente.
Sejam q1 (t) e q2 (t) posições instantâneas estimadas pelo rastreador
no quadro t. Sejam ainda Q1 (t1) e Q2 (t2 ) duas amostras de posições
dos sensores no sistema de coordenadas do mundo, cujas projeções
calculadas com o auxílio de uma matriz de projeção P são denotadas
por q1 (t1 ) e q2 (t2). . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 78
4.2 Figura do robô com uma região de rastreamento no centro de massa
em forma de elipse. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 80
4.3 Exemplo de um espaço de alinhamentos temporais "candidatos"(votos)
para dois sensores na cena. Neste caso, tem-se um espaço de 3 dimensões. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 81
5.1 Espaços de votos 2D obtido por meio da simulação para uma cena artificial contendo um único sensor s1 . A trajetória do sensor rastreada
na seqüência de vídeo sintética na câmera foi corrompida com um
ruído ruído gaussiano branco de média zero e desvio padrão (a)-(c)(e) 5 pixels e (b)-(d)-(f) 10 pixels. A matriz de calibração utilizada
em todos os experimentos corresponde à mesma de uma câmera
real (modelo Sony DCR-TRV320), com erro em subpixels. Os parâmetros de desalinhamento temporal simulados são α = 3.0 e β = 47
para todas as figuras. Em todos os casos, observamos nos gráficos
as retas que recuperam o alinhamento temporal entre o sensor e a
câmera, e que levam a erros menores do que (a)-(b) 1 amostra, (c)(d) 3 amostras e (e)-(f) 5 amostras. . . . . . . . . . . . . . . . . . . . .
p. 96
5.2 Espaços de votos 3D obtidos para cenas artificiais contendo dois sensores móveis s1 e s2 . A trajetória do sensor rastreado na sequência de
vídeo sintética foi corrompida com um ruído ruído gaussiano branco
de média zero e desvio padrão (a)-(c)-(e) 5 pixels e (b)-(d)-(f) 10 pixels. A matriz de calibração utilizada em todos os experimentos corresponde à mesma de uma câmera real (modelo Sony DCR-TRV320),
com erro em subpixels. Os parâmetros de desalinhamento temporal
simulados são α = [1.0 2.0] e β = [46.0 34.0] para todas as figuras.
Em todos os casos observamos nos gráficos as retas que recuperam
o alinhamento temporal entre o sensor e a câmera, e que levam a
erros menores do que (a)-(b) 1 amostra, (c)-(d) 3 amostras e (e)-(f) 5
amostras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 97
5.3 Percentuais de retas que levam a erros médios de alinhamento temporal menores ou iguais a (a) 1, (b) 3 e (c) 5 amostras para níveis
de ruído no sistema de rastreamento de acordo com a Tabela 5.1.1,
dada uma cena composta por apenas um sensor s1 e uma matriz de
calibração com o erro em subpixels. . . . . . . . . . . . . . . . . . . .
p. 98
de ruído no sistema de rastreamento de acordo com a Tabela 5.1 e
uma matriz de calibração com erro em subpixels. As curvas em azul e
vermelho se referem, respectivamente, à sincronização de um sensor
s1 e à sincronização de um sensor s2 com a câmera de referência c,
considerando uma cena artificial composta por dois sensores. . . . .
p. 99
5.5 Espaços de votos 2D obtidos por meio da simulação para uma cena
artificial contendo um único sensor s1 . A trajetória do sensor rastreado
na sequência de vídeo sintética foi corrompida com um ruído ruído
gaussiano branco de média zero e desvio padrão 2. A matrizes de calibração utilizada em todos os experimentos corresponde à mesma de
uma câmera real (modelo Sony DCR-TRV320), adicionado um ruído
gaussiano branco de média zero e desvio padrão (a)-(c)-(e) 5 pixels
(b)-(d)-(f) 10 pixels. Os parâmetros de desalinhamento temporal simulados são α = 1.0 e β = 32.0 para todas as figuras. Em todos os casos
observamos nos gráficos as retas que recuperam o alinhamento temporal entre o sensor e a câmera, e que levam a erros menores do que
(a)-(b) 1 amostra, (c)-(d) 3 amostras e (e)-(f) 5 amostras. . . . . . . . p. 100
5.6 Espaços de votos 3D obtidos por meio da simulação de uma cena
contendo 2 sensores s1 e s2 . A trajetória do sensor rastreado na sequência de vídeo sintética foi corrompida com um ruído ruído gaussiano branco de média zero e desvio padrão 2 pixels. A matrizes de
calibração utilizada em todos os experimentos corresponde à mesma
de uma câmera real (modelo Sony DCR-TRV320), adicionado um
ruído gaussiano branco de média zero e desvio padrão (a)-(c)-(e) 5
pixels (b)-(d)-(f) 10 pixels. Os parâmetros de desalinhamento temporal simulados são α = [3.0 2.0] e β = [45.0 30.0] para todas as figuras.
Em todos os casos observamos nos gráficos as retas que recuperam
o alinhamento temporal entre o sensor e a câmera, e que levam a
erros menores do que (a)-(b) 1 amostra, (c)-(d) 3 amostras e (e)-(f) 5
amostras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 101
de ruído no sistema de calibração de acordo com a Tabela 5.1 e um
ruído no sistema de rastreamento com desvio padrão igual a 2 pixels,
dada uma cena composta por apenas um sensor s1 . . . . . . . . . . . p. 102
de ruído no sistema de calibração de acordo com a Tabela 5.1.1 e o
ruído no sistema de rastreamento com desvio padrão igual a 2 pixels.
As curvas em azul e vermelho se referem, respectivamente, à sincronização de um sensor s1 e à sincronização de um sensor s2 com
a câmera de referência c, considerando uma cena artificial composta
por dois sensores. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 103
5.9 (a) Cena real monitorada pelo sistema de sincronização. Neste caso,
tem-se um único sensor móvel (robô Pioneer 3 AT produzido pela
Active Media), cuja trajetória rastreada no vídeo é ilustrada pela curva
em vermelho. (b) Espaço de votos e reta que recupera o alinhamento
temporal entre o sensor móvel s1 e a câmera c. . . . . . . . . . . . . . p. 104
5.10 Uma cena 3D que é visualizada por N câmeras estacionárias localizadas em diferentes pontos, cujos os campos de visão não são necessariamente sobrepostos. Temos ainda um sensor movendo-se através
do campo de visão de todas as câmeras. . . . . . . . . . . . . . . . . p. 104
5.11 (a) Espaço de votos para a câmera c1 e o movimento do sensor
s. (b) Espaço de votos para a câmera c2 e o movimento do sensor s. Cada ponto em (a) e (b) representam alinhamentos temporais candidatos. As retas reconstruídas tc2 = 3.9979t2 − 269.8932 e
tc2 = 4.0028t2 + 21.6761 descrevem o alinhamento temporal entre o
sensor e as câmeras c1 e c2 respectivamente. Para estas equações a
nova equação obtida tc2 = 1.011tc1 + 291.8797 que recupera o alinhamento temporal entre as duas seqüências de vídeo. . . . . . . . . . . p. 105
5.12 (a) e (b) Trajetórias dos centróides dos sensores nas câmeras 1 e
2, respectivamente. A trajetória azul foi estimada pelo rastreador
WSL (JEPSON; FLEET; EL-MARAGHI, 2003), enquanto a vermelha
foi obtida da projeção da trajetória 3D do sensor no plano de imagem,
usando as matrizes de projeção determinadas durante o processo
de calibração das câmeras. (c) Imagem anterior ao alinhamento foi
criado por superposição da banda verde de um quadro t2 com a vermelha e azul do quadro t1 = (t2 − β g )/α g usando os coeficientes de
alinhamento α g e β g . (d) Após o alinhamento foi criado trocando
a banda verde da imagem com aquela do quadro t1 = (t2 − β e )/α e ,
com α e , β e determinada por nosso algoritmo. Desvios do alinhamento
causam "duas imagem” artificiais . . . . . . . . . . . . . . . . . . . . . p. 106
16
1
INTRODUÇÃO
As chamadas Redes de Sensores Sem Fio (RSSF) têm demonstrado seu grande
potencial ao trazer cada vez mais novas oportunidades e desafios para diferentes campos do conhecimento (CHEE-YEE; KUMAR, 2003). A nova tecnologia de produção
de sensores cada vez menores e com taxas de consumo inferiores a microamperes
tem permitido a ciência ir muito mais longe do que se imaginava na década passada.
Sensores sem fio têm sido criados para ficarem um longo tempo sem a interferência
humana ou até mesmo para que nunca a sofram, como no caso da sonda Spirit que
foi enviada pela agência espacial americana NASA à Marte para explorar o planeta.
Neste caso, é impossível de realizar substituição da bateria da sonda, mas devido ao
custo da missão de envio, é fundamental que a sonda funcione por um longo tempo
colhendo o maior número de amostras possível. Esta nova tecnologia tem propiciado
surgir questões que antes os cientistas não haviam pensado, obrigando aos desenvolvedores deste tipo de tecnologia pensar não somente em questões de hardware e
software mas também em quais são as necessidades dos cientistas para a precisão,
regime de amostragem e sincronização dos sensores (ESTRIN, 2007).
Estruturalmente, as RSSF são compostas por diversos nós sensores distribuídos
espacialmente sobre uma região de interesse, os quais se organizam em uma rede ad
hoc sem fio (TILAK; ABU-GHAZALEH; HEINZELMAN, 2002). Os nós sensores possuem capacidade de comunicação, processamento e sensoriamento, sendo dotados
de uma fonte de energia limitada, cujo consumo é dependente da aplicação de interesse (PERKINS; CORREAL; O’DEA, 2002). Dentre as diversas aplicações de RSSF,
pode-se citar segurança patrimonial, controle de tráfego aéreo, automação industrial,
robótica móvel, sistemas militares de monitoramento e agricultura de precisão (CHEEYEE; KUMAR, 2003; POTTIE; KAISER, 2000). Em todas as aplicações de sistemas
distribuídos, tais como as citadas acima para RSSF, identifica-se a necessidade de
se alinhar temporalmente (sincronizar) os dados adquiridos pelos diversos sensores,
ou seja, colocar as amostras das grandezas físicas medidas pelos sensores em uma
1 INTRODUÇÃO
17
Figura 1.1: Sugestão de utilização de sensores móveis em uma plantação de alfaces.
única linha do tempo de referência. Naturalmente, sem a existência deste referencial
de tempo, não se pode associar ou estabelecer correspondências coerentes temporalmente entre dados de diferentes sensores, o que inviabiliza eventuais análises e
tomadas de decisão coordenadas com base na integração ou fusão de tais dados.
Vejamos o exemplo da Figura 1.1. Nesta cena temos sensores se movimentando
em uma região onde é necessária a determinação de parâmetros como a temperatura ideal para o crescimento das plantas, as condições de umidade relativa do solo
e o índice pluviométrico ou intensidade luminosa nas quais as plantas produzem de
forma mais eficiente. A análise estatística dos dados adquiridos pelos sensores não é
feita pelos próprios nós que têm uma capacidade limitada de processamento, mas sim
em equipamentos com maior capacidade como computadores de pequeno ou grande
porte dependendo da aplicação. Os dados não são enviados no momento em que
são adquiridos pois isto causaria um enorme tráfego de dados na rede, fazendo com
que a mesma ficasse congestionada e lenta, ocorrendo a possibilidade de perda de
dados. Além disto, este envio periódico de dados causaria um grande consumo de
energia. Estima-se que em torno de 17% do consumo total de energia seja gasto
para enviar um conjunto de dados pela rede (POLASTRE, 2003). Devido ao grande
consumo de bateria utilizado para o envio, estes dados então são armazenados nas
memórias internas e posteriormente enviados em grande quantidade para a base de
processamento. Neste cenário surge um problema fundamental que consiste em determinar em qual momento (tempo físico), estas medidas ocorreram. Para relacionar
1 INTRODUÇÃO
18
as medidas de dois ou mais sensores diferentes para o tratamento estatístico dos dados é preciso determinar o momento da aquisição. Assim, quando é preciso unir de
forma consistente dados de sensores diferentes surge a necessidade de determinar a
relação temporal entre as medidas das grandezas. Para isto é preciso que os relógios
dos sensores estejam operando com a mesma base de tempo ou que seja possível
determinar uma base de tempo externa comum a todos.
Tipicamente, o desalinhamento temporal entre diferentes sensores origina-se por
duas razões principais. A primeira relaciona-se com o fato de que os sensores utilizados possam apresentar diferentes taxas de amostragem, enquanto a segunda
relaciona-se com a existência de um deslocamento temporal entre as sequências de
amostras, o qual é criado quando os sensores não são ativados simultaneamente,
daí a necessidade de sincronização entre os sensores. Esta sincronização deve ser
tão mais rápida quanto a necessidade da aplicação exige. Em um documentário recentemente apresentado em um canal de TV pago (POLASTRE, 2003), foi exibida
uma aplicação de uma rede de sensores sem fio em um vinhedo no Canadá onde
65 sensores foram instalados em um acre de terra e enviavam dados de temperatura,
umidade e intensidade da luz do sol com uma freqüência igual a 5 minutos, sendo
então necessária uma sincronização a cada 5 minutos. Em uma outra aplicação, a
estrutura de teste para abalos sísmicos necessita uma sincronização com um tempo
de 5ms (PAEK et al., 2006).
Com o objetivo de se fazer a sincronização de sensores móveis em uma rede sem
fio, este trabalho propõe uma nova metodologia. Especificamente, para a solução
deste problema, propõe-se o uso de câmeras que consigam visualizar toda a cena
ou parte dela. O problema pesquisado deste trabalho pode ser enunciado como se
segue:
Dada uma cena 3D contendo N sensores móveis heterogêneos, distribuídos em
uma rede ad hoc sem fio, cujos movimentos são monitorados por uma câmera de
vídeo calibrada e cujas localizações são conhecidas, deseja-se estimar uma função
de N+1 dimensões responsável por capturar as relações temporais entre todos os
sensores presentes em tal rede.
Para uma melhor compreensão da abordagem proposta neste trabalho, observe
a Figura 1.2, a qual considera uma cena composta por apenas dois sensores S1 e
S2 e uma câmera c. Os quadros da sequência de vídeo obtida pela câmera c bem
como os dados dos sensores S1 e S2 representam informações obtidas no tempo, as
1 INTRODUÇÃO
19
...
...
c
50
0
g1
300
51
t
DT1= 149
DT2= 45
s1
…
0
1
2
3
4
5
6
7
200
8
t1
g2
DT12= 194
s2
…
0
1
2
3
4
5
6
7
8
100
t2
Figura 1.2: Demonstração do desalinhamento temporal em uma cena composta por
dois sensores S1 e S2 visualizados por uma câmera c. Observa-se que os quadros da
câmera c e os dados do sensor S1 e S2 possuem um desalinhamento temporal ∆T1 =
149 e ∆T12 = 194 respectivamente.
quais frequentemente encontram-se desalinhadas (não-sincronizadas). Por exemplo,
supondo que o quadro 51 da câmera c e as amostras 200 e 6 dos sensores S1 e
S2 , respectivamente, correspondem ao mesmo instante de tempo no mundo, diz-se
que os quadros da câmera c e os dados do sensor S1 possuem um desalinhamento
temporal ∆T1 = 149. Analogamente, os quadros da câmera c e os dados do sensor S2
possuem um desalinhamento ∆T2 = -45 e os dados dos dois sensores possuem um
desalinhamento ∆T12 = 194. Os desalinhamentos ∆T1 , ∆T2 e ∆T12 são as incógnitas
cujo processo de determinação foi objeto de estudo e pesquisa neste projeto. De
posse dos valores destas incógnitas, pode-se descrever completamente as relações
temporais entre os sensores.
A idéia básica da abordagem deste trabalho consiste em estender a metodologia
para alinhamento espaço-temporal de múltiplas sequências de vídeo, desenvolvida
por Pádua el. al. (PáDUA, 2005; PáDUA et al., 2004), para o âmbito de elaboração
de uma técnica alternativa para o alinhamento temporal de múltiplos sensores heterogêneos em redes sem fio. Neste contexto, a abordagem aqui feita está fundamentada
1.1 Motivação
20
na definição de uma reta de N + 1 dimensões, a qual captura globalmente as relações
temporais entre um conjunto de N sensores e uma sequência de vídeo adquirida por
uma câmera que visualiza tais sensores em movimento na cena de interesse.
Uma propriedade fundamental desta reta é que ainda embora seu conhecimento
implique no conhecimento do alinhamento temporal entre os sensores e a câmera, a
estimativa de pontos sobre a mesma pode ser realizada sem o conhecimento prévio de
tal alinhamento. Utilizando-se esta propriedade como ponto de partida, a abordagem
desta dissertação de mestrado reduziu o problema de se estimar o alinhamento temporal entre N sensores para o problema de se estimar de forma robusta uma única
reta de N + 1 dimensões a partir de um conjunto de pontos gerados em ℜN+1 .
1.1 Motivação
Nesta seção serão descritas três aplicações de RSSFs que tem se tornado de
grande importância para a comunidade científica. Um dos exemplos é o monitoramento de habitat que tem ajudado na determinação de condições ótimas da fauna e
flora de determinados ecossistemas, com o objetivo de se recuperar espécies em extinção. Outra utilização que tem um futuro promissor é o monitoramento de variáveis
envolvidas no processo de agricultura de precisão com o objetivo de aumentar-se a
produção das fazendas. Finalmente temos o exemplo de monitoração de construções.
Esta monitoração não tem relevância tão grande para a humanidade mas tem utilizado cada vez com maior freqüência as RSSFs para evitar acidentes por desgastes
de material ou prevenção para destruição por desastres naturais.
1.1.1
Monitoração de Habitat
O monitoramento do meio ambiente representa uma das aplicações para redes de
sensores com um enorme potencial de pesquisa para a comunidade científica. Aparelhando o meio ambiente com um grande número de sensores em rede podemos
coletar dados em escala e resolução que seriam dificilmente, ou até impossível de se
conseguir por meio de outra forma de sensoriamento. Com isto é possível realizar tarefas mais complexas como amostragem estatística, fusão de dados e monitoramento
do estado de saúde do ecossistema. A escala temporal das medidas dos sensores
deve ser definida pela ordem de grandeza do tempo de mudança dos organismos.
1.1 Motivação
21
Os sensores devem coletar os dados em taxas iguais ou maiores que as condições de
mudança do meio que está sendo monitorado. O sistema de análise de dados deve ser
capaz de identificar não somente a mudança mas também a duração de eventos. Um
exemplo de utilização de rede de sensores para monitoramento de habitat é mostrado
por Polastre (POLASTRE, 2003), o qual propõe o monitoramento de pássaros marinhos em uma ilha localizada 15km ao sul de Mount Desert Island chamada Great
Duck Island. Nesta ilha há aproximadamente 5000 casais de um pássaro chamado
Petrel os quais vivem em três tipos de habitat diferentes. Nesta ilha foi montado um
observatório pela escola College of Atlantic(COA) para a observação deste ecossistema. Os pesquisadores de pássaros marinhos buscam responder, principalmente, as
seguintes questões:
• Qual é a duração dos vários gradientes de temperatura do ambiente?
• Quais mudanças ocorrem nos ninhos durante o período reprodutivo?
• Quais são os tipos de ninhos que os Petrels selecionam? Quais destas condições
produzem um microclima ótimo para o acasalamento, incubação e choca?
• Quais são as diferenças no microclima entre as áreas que possuem um grande
número de ninhos de Petrel e as áreas que não têm?
É muito improvável que qualquer um dos parâmetros medidos pela rede de sensores sem fio irá determinar porque os Petrels escolhem um determinado lugar para
fazer seus ninhos. Entretanto os muitos parâmetros medidos pelos sensores podem
ajudar a correlacionar os dados que indicam o que leva um pássaro a selecionar um
determinado lugar para seus ninhos.
Neste exemplo, Polastre (POLASTRE, 2003), com o objetivo de ter uma boa aproximação para o problema, colocou um sensor dentro de cada ninho dos Petrels sendo
que alguns ninhos ficaram sem sensor para avaliar o efeito da presença do mesmo.
Estes sensores têm que trabalhar de forma sincronizada pois é necessário determinar se algum fator externo provocou a mudança de temperatura dentro do ninho ou
a mudança da umidade relativa dentro do ninho. Estando os sensores sincronizados,
é possível avaliar se a alteração climática ocorreu em todos os sensores ao mesmo
tempo. Esta sincronização poderia ser feita por meio de envio periódico de mensagens
mas tem-se um problema com este tipo de sincronização que é o aumento significativo
do consumo.
1.1 Motivação
Operação
Transmissão de um pacote
Recepção de pacote
Escuta de rádio por 1ms
Operação do sensor por 1 amostra analógica
Operação do sensor por 1 amostra digital
Leitura de uma amostra do ADC
Leitura da EEPROM
Programar e apagar EEPROM
22
% de consumo de energia
17,37
6,94
1,08
0,94
0,30
0,001
0,96
72,38
Tabela 1.1: Necessidades médias de consumo de energia, para operação do sensor MICA utilizado para monitoração dos ninhos pelo autor da pesquisa.(POLASTRE,
2003)
Pela Tabela 1.1 podemos observar que a segunda maior fonte de consumo de
energia é a transmissão de pacotes. Caso haja um aumento do tamanho do pacote devido ao envio de dados de sincronização, ocorrerá um aumento significativo no
consumo de energia. Caso este pacote precise ser transmitido com uma grande freqüência para se fazer também a sincronização dos sensores teremos uma diminuição
considerável no tempo de operação do sensor. A Figura 1.3 mostra como foi instalado
o sistema de monitoramento dos ninhos.
Como no exemplo da Figura 1.3, sensores móveis podem ser utilizado para monitoração do ecossistema, onde um robô se movimenta fazendo medidas de temperatura, umidade relativa, luz ambiente e entrada e saída dos Petrels no ninho. Para
que se consiga tratar de forma estatística os dados das leituras destes sensores é
necessário determinar o momento que foi realizada cada medida, necessitando então
de uma sincronização entre os sensores pois somente com esta sincronização é possível determinar em qual ninho foi feita a medida e em qual momento, para identificar
mudanças em todo o sistema que provocaram mudanças internas.
1.1.2
Agricultura de Precisão
A variabilidade dos fatores de produção está associada a múltiplas causas, desde
a variabilidade climática até o ambiente em torno de uma única semente (solo, oxigênio, disponibilidade de água e nutrientes etc.) que é depositada no solo. As formas de variabilidade que estão sendo estudadas e manejadas em agricultura de precisão podem ser classificadas em "Variabilidade Espacial” (aquela que ocorre com
um atributo na área, por exemplo: variação da concentração de fósforo no solo em
uma área de 20 hectares), "Variabilidade Temporal” (aquela que ocorre ao longo do
1.1 Motivação
23
Figura 1.3: Monitoramento de um ecossistema (1) Sensores da rede sem fio para
monitoramento dentro do ninho. (2) Dispositivos de gravação e transmissão dos dados para um nó gateway. (3) Antena transmissora para um notebook na estação de
pesquisa. (4)-(5) Estação de pesquisa que possui o link de dados com o satélite.
(6)Sistema sugerido para utilização de sensor móvel para monitoramento do ambiente
não utilizado pela pesquisa original, (POLASTRE, 2003).
tempo, por exemplo: disponibilidade de água no solo em função da sazonalidade
da precipitação pluvial) e uma terceira que representa a ação do homem nas duas
primeiras, chamada "Variabilidade Induzida pelo Manejo” (aquela criada pelas decisões de manejo tomadas nas áreas de cultivo, por exemplo: alocação de culturas
e regulagem de máquinas) (PIRES et al., 2004). Esta última ocorre, por exemplo,
quando há máquinas desgastadas e desreguladas, sistemas de cultivo diferenciados,
partes da lavoura deixadas em pousio por vários anos e deficiência no controle de
plantas daninhas (FARNHAM, 2000).
Uma das alternativas para se monitorar e controlar estas variáveis consiste na utilização de RSSF. A utilização de RSSF em agricultura ainda é bastante rara (WANG;
ZHANG; WANG, 2006), mas com o desenvolvimento de novas técnicas de medida
e de novos sensores que possuem um custo menor é possível que este uso cresça
muito em breve. Dados para muitas variáveis em agricultura de precisão podem ser
obtidas por técnicas de sensoriamento remoto como imagens de satélite, ou fotos
de aviões. Mas é essencial que se tenha também medidas diretas. Estas medidas
muitas vezes são feitas por equipamentos estacionários como estações meteorológicas ou sensores fixados diretamente na terra. Estas medidas estacionárias oferecem
1.1 Motivação
24
Figura 1.4: Montagem de uma cena composta por sensores movimentando-se por
uma plantação de soja.
a desvantagem de fornecer informações apenas de variáveis que envolvem toda a
plantação como o clima da região e o relevo ou como estão as posições das curvas
de nível, por exemplo. Estes dados são muito ruins para prever por exemplo a acidez
do solo em cada região da plantação ou a umidade do solo que são variáveis mais
localizadas. Para medidas mais precisas como estas temos a utilização de sensores
em máquinas que se movimentam pela plantação, como tratores colheitadeiras entre
outras. Esta técnica tem a desvantagem de que estas máquinas não estão sempre se
movimentando pela plantação e para pequenos agricultores onde o manejo através de
maquinário é menor temos que as medidas ficariam bastante prejudicadas. É neste
contexto que surge a necessidade de um sistema de monitoração através de sensores
móveis utilizados para entender a variabilidade da produção. Uma RSSF pode estar
hábil a coletar dados do campo periodicamente e em tempo real, como é o caso para
controle de irrigação (CAMILLI et al., 2007).
Segundo Wang,Zhang e Wang (2006), podemos classificar as aplicações para
agricultura em cinco tipos diferentes: monitoramento do meio ambiente, agricultura de
precisão, controle de máquinas e processos, automatização de benfeitorias e sistema
de rastreabilidade. Cada uma destas aplicações possui um conjunto de variáveis que
devem ser monitoradas e ou controladas pelos sistemas. E muitas destas variáveis
como temperatura e quantidade de luz incidente na folha de uma planta não fazem
muito sentido se não forem informados os momento nos quais estas variáveis foram
medidas, pois estas podem ter sido medidas após a irrigação ou ao amanhecer. Para
1.1 Motivação
25
Figura 1.5: Ponte de Akashi Kaikyo no Japão que utiliza monitoramento estrutural para: (1) validar suposições de projeto; (2) detectar anomalias de carga; (3)
prover informações de seguranças após desastres naturais; (4)prover informações
para manutenção.
avaliação de apenas uma planta, a sincronização não é necessária, mas quando se
quer avaliar os dados de produção de duas plantas diferentes, então é necessário que
se saiba os momentos que foram adquiridos os dados de cada planta sendo então
necessário que se tenha dados de sincronização dos sensores.
1.1.3
Monitoração de construções
A monitoração estrutural procura detectar e localizar problemas estruturais em prédios, aviões, navios ou pontes. Esta monitoração é muito complexa, o que faz com que
demande muita pesquisa até se tornar um método prático. Além disto, é necessário
um grande número de dados para que seja possível fazer alguma previsão utilizando
dados de vibração em um terremoto, vento ou passagem de carros (XU et al., 2004).
Muitos dos monitoramentos feitos hoje têm utilizado sensores com fio mas o monitoramento por meio desta metodologia é caro e muitas vezes este preço torna inviável o
projeto. Uma solução promissora para o problema de monitoramento consiste no uso
de RSSF, pois estas oferecem uma solução de fácil instalação reduzindo com isto os
custos,e as necessidades de manutenção (PAEK et al., 2006).
Assim como em outras aplicações envolvendo redes de sensores sem fio, a monitoração de construções necessita de sensores que possuam o menor consumo de
energia possível para que o índice de manutenção com trocas de bateria seja pequeno
1.2 Abordagem
26
e possa reduzir custos. Esta maior preocupação com a manutenção se justifica devido a grande dificuldade de acesso aos locais onde estão os sensores. Para fazer
sincronizações com períodos contínuos temos que ocorreria um aumento significativo
no consumo de energia. Portanto é fundamental no caso de monitoração estrutural
que se tenha um método de sincronização eficiente.
Uma importante consideração a fazer em monitoração de construções é a taxa na
qual as unidades sensoras fazem a aquisição dos dados. Isto é importante para nos
dar uma idéia das necessidades para desempenho em tempo real do sistema. Esta
taxa de geração de dados depende da taxa de amostragem que viabiliza amostrar a
freqüência fundamental de vibração do sistema. Para estruturas muito grandes, este
modo fundamental é da ordem de hertz e então devemos ter uma taxa de amostragem
da ordem de dezenas de hertz. Mas quando é necessária uma grande quantidade de
sensores, para se realizar a varredura de todos eles seriam necessários uma taxa de
amostragem extremamente alta.
A maioria dos algoritmos usados para analisar informações de vibração são baseados em procedimentos de análise modal (KOTTAPALLI et al., 2003). Para a análise
modal ser feita em uma estrutura é necessário que os dados de vibração obtidos dos
diferentes sensores distribuídos na estrutura estejam sincronizados no tempo. A tolerância para erros na sincronização dos dados deve ser da ordem de milisegundos
(KOTTAPALLI et al., 2003). Para a monitoração com sensores com fio a sincronização
é um problema extremamente fácil de se resolver já que todas as amostragens são
feitas por uma central, mas em uma rede de sensores sem fio este problema tornase um grande desafio. Como podemos observar nos exemplos anteriores temos dois
principais desafios ainda para a difusão dos métodos de monitoramento que utilizam
rede de sensores sem fio que é a sincronização e a diminuição do consumo de energia. Neste contexto este trabalho propõe uma nova metodologia para sincronização
de redes de sensores sem fio que seja mais eficiente produzindo com isto taxas de
consumo de energia e tráfego de rede menores.
1.2 Abordagem
Espera-se que qualquer solução suficientemente genérica para o problema de sincronização temporal entre sensores em uma rede sem fio deva tratar de forma eficaz os seguintes pontos (ELSON; GIROD; ESTRIN, 2002; PALCHAUDHURI; SAHA;
1.2 Abordagem
27
JOHNSON, 2004):
• Consumo de energia: o consumo eficiente de energia em RSSF exerce grande
impacto na qualidade de sua operação.
• Exatidão de sincronização ajustável: protocolos de sincronização tradicionais
tentam alcançar o mais alto grau de exatidão possível. Entretanto, observa-se
que quanto maior é o grau de exatidão do sistema de sincronização, maior é
sua complexidade e seu custo. Portanto, deve-se projetar sistemas nos quais a
exatidão da sincronização seja ajustável à demanda da aplicação.
• Não-determinismo: RSSF são sistemas dinâmicos com consideráveis taxas de
falhas e presença de não-determinismo na operação de seus nós. Neste contexto, o sistema de sincronização projetado deve ser robusto ao comportamento
não determinístico dos nós da rede.
• Multihop: RSSF possuem múltiplos hops distribuídos em sua rede, os quais
costumam se mover segundo trajetórias muitas vezes aleatórias.
• Ausência de fontes externas de sincronização: RSSF podem não possuir
uma infra-estrutura externa que defina uma referência global de tempo.
• Escalabilidade: a eficiência do sistema de sincronização deve ser escalável
diante do aumento do número de sensores a serem sincronizados.
• Independência da topologia de rede: o sistema de sincronização deve ser
robusto às variações na topologia da rede de sensores.
• Taxas de amostragem desconhecidas: as taxas de amostragem das grandezas
físicas medidas pelos sensores são constantes, desconhecidas e arbitrárias.
• Deslocamento temporal arbitrário: o deslocamento temporal entre os dados
dos sensores é constante, desconhecido e arbitrário.
Especificamente, a técnica a ser pesquisada neste projeto considera um cenário
no qual uma câmera estática possa ser adequadamente posicionada no ambiente de
forma que a mesma seja capaz de visualizar o conjunto de sensores se movendo
na cena durante um intervalo de tempo previamente especificado, como ilustrado
na Figura 1.6. Neste cenário, assume-se ainda que a câmera de vídeo utilizada
é uma câmera pinhole calibrada. Sendo os parâmetros intrínsecos e extrínsecos
1.3 Objetivos: Geral e Específicos
28
zc
c
xc
s4
s2
zw
yc
s1
yw
s3
...
sn
xw
Figura 1.6: Visão geral do cenário considerado pela metodologia proposta neste trabalho. Um câmera de vídeo estática c visualiza um conjunto de sensores móveis
S = s1 , . . . , sn .
desta câmera constantes ao longo do tempo, tem se que a transformação que leva as
posições dos sensores no sistema de coordenadas do mundo para o sistema de coordenadas da câmera também será constante. Partindo do pressuposto que os sensores
utilizados bem como a câmera de vídeo operam a taxas de amostragem constantes,
pode-se relacionar as coordenadas temporais (números dos quadros) na sequência
de vídeo da câmera com as coordenadas temporais das amostras da grandeza física
medida pelo sensor por meio da seguinte transformação afim unidimensional:
t i = αi t + β i
(1.1)
onde ti é a coordenada temporal da grandeza física medida pelo sensor Si (i = 1,. . . ,N),
t é o número do quadro na sequência de vídeo obtida pela câmera de referência c e
αi , βi são constantes desconhecidas que representam a dilatação e o deslocamento
temporal, respectivamente, entre o sensor Si e a câmera c. Em geral, estas constantes
não deverão ser números inteiros.
1.3 Objetivos: Geral e Específicos
Pretende-se que este trabalho contribua para o desenvolvimento de Redes de
Sensores Móveis dotando-as de uma infra-estrutura mais eficaz, eficiente e robusta
às intempéries inerentes aos ambientes de atuação das mesmas.
1.4 Contribuições
29
O produto final deste projeto é a apresentação de uma nova metodologia para
sincronização de múltiplos sensores heterogêneos distribuídos em redes ad hoc sem
fio, baseada no uso de técnicas de análise de sequências de imagens, cuja implementação e validação foram inicialmente desenvolvidas com o auxílio de simulações
computacionais e posteriormente com dados reais obtidos por meio de câmeras instaladas no ambiente de interesse e sensores instalados em robôs móveis, tais como
sonares, acelerômetros e sensores de profundidade. Para tanto, foram perseguidos
os seguintes objetivos específicos:
1. Desenvolvimento de um software para simular a dinâmica de uma cena 3D composta por um número genérico de sensores heterogêneos móveis, bem como o
processo de visualização dos mesmos a partir de uma câmera estática calibrada.
2. Reconstrução das trajetórias dos sensores móveis no sistema de coordenadas
do mundo e no plano de imagem da câmera.
3. Extensão da metodologia originalmente desenvolvida por Pádua et al. (PáDUA
et al., 2004), para que a mesma seja capaz de gerar espaços de votos a partir
das trajetórias dos sensores anteriormente estimadas.
4. Validação do processo de reconstrução da reta que captura as relações temporais entre os sensores utilizando-se os espaços de votos anteriormente calculados, o algoritmo RANSAC e o Método do Mínimos Quadrados.
5. Experimentação e validação da metodologia proposta com dados reais.
1.4 Contribuições
A sincronização dos dados adquiridos por múltiplos sensores heterogêneos em
redes de sensores móveis é de fundamental importância para diversas aplicações
relacionadas com a fusão e/ou integração de tais dados. O desenvolvimento de uma
metodologia eficiente para tal fim é uma tarefa crítica para o avanço das pesquisa
em redes de sensores e também robótica móvel. Na Universidade Federal de Minas
Gerais (UFMG), onde já existem grupos consolidados em tais áreas de pesquisa nos
Departamentos de Engenharia Elétrica e Ciência da Computação, tem-se verificado a
demanda por esta metodologia em diversos trabalhos.
1.5 Organização do texto
30
Ao propor uma nova metodologia de sincronização baseada na análise de sequências de imagens da cena monitorada por um conjunto de sensores, este projeto abre
espaço para importantes esforços de pesquisa conjunta entre laboratórios de renome
nacional e internacional da Universidade Federal de Minas Gerais com o Laboratório de Sistemas Inteligentes do Centro Federal de Educação Tecnológica de Minas
Gerais. Certamente, a criação e intensificação das interações entre tais laboratórios
destas instituições durante a execução deste trabalho contribuirão para diversos projetos conjuntos no futuro.
A principal relevância do trabalho para a comunidade científica, que resultou na
publicação em um artigo para o congresso SIBIGRAPI, foi sua contribuição para o
desenvolvimento da base tecnológica responsável pela criação da tecnologia nacional
nas áreas de Redes de Sensores e Visão Computacional. Embora alguns sistemas
para sincronização temporal em redes de sensores já tenham sido descritos e implementados, uma solução fechada e comercial para o problema ainda não está disponível
no Brasil. Devido a barreiras comerciais impostas sobre os componentes do sistema,
já que muitos deles podem ser utilizados na indústria bélica, a execução deste projeto seria de grande contribuição para a comunidade brasileira, já que pode ser um
trabalho de apoio para a criação de produtos nacionais.
Em relação ao estado da arte da pesquisa na área, este trabalho contribuiu com
uma metodologia inovadora, a qual demonstra ser mais eficiente e robusta do que
muitos dos trabalhos relacionados.
Este texto está organizado em 5 capítulos sendo esse o seu primeiro capítulo. No
capítulo 2 são apresentados os trabalhos relacionados e discutidas outras metodologias de sincronização temporal em sistemas distribuídos. Neste capítulo ainda é apresentada uma análise crítica destas metodologias, apresentando os pontos negativos
de cada uma delas. No capítulo 3 é apresentada a fundamentação teórica desta
deste trabalho. Neste capítulo temos uma visão geral sobre aquisição e tratamento
de imagens digitais, seguida por uma descrição de como determinar os parâmetros
que levam a transformação de um ponto no mundo para o plano de imagem. Este
processo é chamado de calibração de câmeras. Apresentamos ainda a descrição do
funcionamento de rastreadores de objetos em uma seqüência de vídeo, que trata-se
31
de determinar a trajetória de um objeto em pixels na câmera. Por último, temos uma
seção para descrever o funcionamento de uma algoritmo simples mas muito robusto
para ajuste de modelos baseado em conjuntos de dados com ruído. Este algoritmo
é chamado de RANSAC-Random Sample Consensus (FISCHLER; BOLLES, 1987).
No capítulo 4 é apresentado em detalhes o algoritmo proposto para solução do problema de sincronização em uma rede de sensores móveis sem fio. Finalmente no
capítulo 5 são apresentados e discutidos os resultados obtidos com a metodologia
de sincronização desenvolvida. Neste capítulo apresentamos resultados obtido para
seqüências sintéticas e uma seqüência real que comprovam a eficiência da técnica
de sincronização proposta. Adicionalmente são apresentados resultados da aplicação
da metodologia para a sincronização de câmeras que não possuem sobreposição de
campos de visão. Finalmente apresentamos as conclusões do trabalho e as direções
futuras para a pesquisa.
32
2
TRABALHOS RELACIONADOS
Diversas metodologias para sincronização temporal em sistemas distribuídos tem
sido propostas ao longo das três últimas décadas, sendo algumas delas responsáveis
por significativos avanços na concepção de tais sistemas (GANERIWAL et al., 2005;
PALCHAUDHURI; SAHA; JOHNSON, 2004; SICHITIU; VEERARITTIPHAN, 2003; ELSON; ESTRIN, 2001; MILLS, 1994, 1989). Grande parte destas metodologias foram
originalmente concebidas para redes de computadores tradicionais como a Internet
e possuem algumas características em comum, tais como: uso de um protocolo de
mensagens sem conexão, uso de servidores que enviam periodicamente mensagens
para clientes contendo seus sinais atuais de clock e uso de técnicas para minimizar
os efeitos negativos do não-determinismo na fase de entrega e processamento das
mensagens. Um deste protocolos é o que veremos na próxima seção, o NTP. Este
protocolo é bastante utilizado em redes com topologias estáticas e internet e vem
sofrendo algumas adaptações para ser utilizado em redes de sensores sem fio.
2.1 NTP - Network Time Protocol
O protocolo NTP consiste de uma rede de servidores primário e secundário, clientes
e um caminho de interconexão. Um servidor primário é sincronizado diretamente
por uma fonte de referência, usualmente um servidor sincronizado com um relógio
atômico. Um servidor de tempo secundário recebe esta sincronização, possivelmente
através de outros servidores primários utilizando o protocolo NTP. Um servidor secundário de tempo propaga sua sincronização, possivelmente via outros servidores
secundários, de um servidor primário por toda a rede, possivelmente compartilhada
para outros serviços. Em circunstâncias normais a sincronização do clock é determinada usando apenas o mais exato e confiável servidor e um canal físico de transmissão. A rede que será sincronizada assume uma configuração hierárquica com a fonte
de referência primária na raiz e decrementando a precisão com o aumento dos níveis
2.1 NTP - Network Time Protocol
33
(MILLS, 1994).
Este método é um exemplo de protocolo utilizado em redes com topologias estáticas como a Internet. Ao longo das décadas, muitas transformações neste tipo de
protocolo têm sido propostas mas todas elas baseiam-se na troca de mensagens sem
conexão. Um servidor envia o seu clock local para as estações que, com base neste
clock, sincroniza seu relógio local. Há uma enorme quantidade de literatura sobre
adaptações neste protocolo com pequenas diferenças para melhoria na precisão da
sincronização, por meio da utilização de métodos heurísticos ou estatísticos.
Neste método é necessário um relógio com uma estabilidade excepcional dos osciladores locais para prover um tempo exato quando a sincronização com o servidor primário falha. Isto acaba se tornando mais um fator que associado a outros
como o tráfego constante de dados na rede para sincronização diminuem o desempenho do sistema. Como citado anteriormente, a precisão destes relógios não é muito
grande. Em sistemas, como a Internet onde não se necessita uma exatidão muito
grande estes sistemas são bastante úteis. O protocolo NTP tem sido bastante utilizado para sincronização em redes onde não se tem necessidades como as de uma
RSSF. A grande desvantagem dos métodos de sincronização que utilizam este protocolo é o fato de necessitarem de uma constante troca de mensagem fazendo com que
aumente consideravelmente o fluxo de dados na rede. Para uma rede de sensores
sem fio contendo um grande número de nós haveria uma grande quantidade de dados
tornando a rede muito lenta.
Um exemplo de adaptação do protocolo NTP para aplicação em RSSF é dado por
Cristian (CRISTIAN, 2005) onde o autor propõe um método onde são realizadas várias
trocas de mensagem entre o servidor e o cliente fazendo com que diminua consideravelmente o não-determinismo causado pelo tratamento das mensagens nos nós da
rede. Além disso, com estas trocas constantes é possível determinar estatisticamente
o tempo que os dados levam para ir do transmissor ao receptor.
Especificamente, no âmbito do desenvolvimento de metodologias para sincronização temporal em RSSF, a tentativa de adaptações em soluções clássicas como as anteriormente citadas, têm-se mostrado bastante insatisfatórias. Diversas são as razões
para o insucesso em adaptações como estas, tais como: uso do tempo lógico (LAMPORT, 1978) como referência ao invés do tempo físico que efetivamente relaciona
eventos no mundo real, adoção de estratégias que consomem grande quantidade de
energia tanto na transmissão como na recepção de mensagens e uso de conheci-
34
mento a-priori sobre a topologia da rede para o estabelecimento de algumas operações de sincronização, o que pode ser altamente ineficaz diante da alta variabilidade
a que está sujeita a topologia de uma RSSF.
Um dos exemplos de adaptações no protocolo NTP é o TDP. Neste protocolo, um
servidor transmite mensagens sem conexão para toda a rede. Assim como no protocolo NTP ocorre a formação de níveis, e cada nível possui um nó que é o nó raiz,
responsável por retransmitir a sincronização feita por um nó raiz do nível superior. Nós
do tipo raiz podem sofre falhas ou até mesmo terminarem a vida útil de sua bateria.
O protocolo TDP auto-configura e auto-organiza para novos endereços o freqüente
particionamento da rede causado por falhas nos nós sensores. Além do mais, o TDP
não depende de qualquer nó em particular, e os nós podem ser apenas por um tempo
server/master e depois se tornarem nós clientes. Dessa forma o trabalho de sincronização da rede pode ser dividido para todos os nós. O TDP é utilizado em dois
casos:
• Com servidores precisos: Toda arquitetura do sistema interagindo com o TDP
é mostrado na Figura 2.1. O principal objetivo do TDP é ajustar o clock dos nós
sensores em toda a rede para operar com a mesma base de tempo. Os sinks
são hardwares específicos, que podem atuar como servidores precisos de tempo
para os nós sensores localizados no "campo de sensores". Eles podem enviar
em broadcast um tempo de referência para todos os nós master na rede de sensores; nós master são nós sensores escolhidos aleatoriamente para sincronizar
seus nós vizinhos. Os nós master usam a referência de tempo recebida para
sincronizar seus nós vizinhos usando TDP. Essencialmente, a base de tempo da
rede de sensores é determinada por meio do tempo enviado pelo sink.
• Sem servidores de tempo precisos: Embora o TDP possa ser usado com
um servidor de tempo preciso, é muito importante discutir sobre a natureza
autônoma do TDP já que a conexão para todos os nós masters pode não ser
possível. Além do mais, a rede de sensores pode ser empregada em áreas que
podem não ser acessadas pelos sinks por um longo período de tempo. Consequentemente, os sinks não podem ser usados como servidores de tempo; a
natureza autônoma do TDP permite que nós sensores operem na mesma base
35
Figura 2.1: Arquitetura do sistema de sincronização utilizando TDP (SU; AKYILDIZ,
2005).
de tempo que é dependente de um nó master utilizando uma base de tempo
conseguida através da internet Coordinated Universal Time - UTC.
Mesmo que os sensores da rede operem na mesma base de tempo, ainda pode
haver uma flutuação (nós sensores que diferem da base de tempo dos servidores
primários) através da rede de sensores. É necessário traduzir o tempo da rede de sensores para um tempo comum, UTC, usado pelos usuários. O sink como mostrado na
Figura 2.1, assim como o Time Translation Algorithm, é responsável por esta tradução
do tempo do mundo físico para a rede de sensores. Além do mais, ele serve como
interface para a rede de sensores e sincronizam o tempo dos servidores utilizando
NTP.
A temporização utilizada na aplicação do TDP é ilustrado na Figura 2.2. Durante
o período ativo, os nós master são reeleitos a cada τ segundos, este é um parâmetro
que depende do tipo da rede de sensores. O nó master envia uma mensagem de
broadcast com informações sobre o seu tempo para seus nós vizinhos que utilizam
este tempo para ajustar os seus relógios. Os nós vizinhos auto determinam para
tornarem-se nó líder que difunde o tempo para seus vizinhos que é recebido dos próximos broadcast. O nó master repete este processo todo δ segundo como mostrado
na Figura 2.2. A duração do período ativo do TDP depende da faixa das variações
do tempo permitida através da rede de sensores. Por outro lado, o período inativo
depende do tamanho da dilatação temporal entre os nós da rede. O período ativo e
inativo são parâmetros que podem ser determinados para diferentes tipos de rede de
sensores.
36
Figura 2.2: Esta figura mostra que o protocolo TDP não atua durante todo o tempo
para sincronização da RSSF sendo que a sincronização é feita durante um tempo τ
segundos por um nó mestre com intervalos de δ segundos (SU; AKYILDIZ, 2005).
A arquitetura TDP consiste de muitos algoritmos e procedimentos como mostrado
na Figura 2.3 apresentada pelo autor do método.
Os algoritmos e procedimentos mostrados na Figura 2.3 são usados de forma
autônoma para sincronizar os nós, remover clocks que estão fora da base de tempo
dos seus vizinhos, e balancear a carga necessária para sincronização ao longo da
rede dos nós sensores. Inicialmente, os nós sensores podem receber um pulso de
inicialização do sink através de um broadcast por toda a rede. Então eles se autodeterminam nós masters, com eleição/reeleição do nó master/difusor pelo procedimento ERP, que consiste de um algoritmo de isolação de nós que diferem dos outros
nós da rede chamado de false ticker isolation algorithm (FIA) e load distribution algorithm (LDA). No final do procedimento de ERP, o nó master eleito começa um procedimento de peer evaluation procedure-PEP enquanto os outros nós da rede não fazem
nada. O procedimento PEP ajuda a remover os nós que diferem na base de tempo
dos nós vizinhos do nó master ou do nó líder.
Após o procedimento PEP, os nós masters eleitos ( identificados como W na Figura
2.3) começam o procedimento de time diffusion procedure (TDP), onde eles difundem mensagens com seus tempos a cada δ segundos por um período de τ segundos. Cada nó vizinho recebe estas mensagens e se auto-determinam nó líder difusor
usando o procedimento de ERP. Além do mais, todos os nós vizinhos ajustam seus
relógios usando o algoritmo de ajuste de tempo (time adjustment algorithm-TAA) e o
Figura 2.3: Arquitetura TDP (SU; AKYILDIZ, 2005).
37
2.3 Algoritmos Mini-sync e Tiny-sync
38
algoritmo de disciplina do clock (colck discipline algorithm-CDA) após esperar por δ
segundos.
O nó líder difusor eleito transmitirá mensagens com seu clock para os nós que se
encontram na sua vizinhança e para nós no raio que é possível que ele faça broadcast.
Note que estas informações do relógio local são difundidas por cada nó líder difusor
para n hops de um nó master, onde cada hop representa um nível do nó master. Este
processo de difusão habilita todos os nós serem sincronizados de forma autônoma.
Além do mais, os nós master são reeleitos a cada τ segundos usando o procedimento
de ERP, que é repetido por θ − 1 vezes, onde θ τ é igual ao tamanho do período ativo
do TDP.
Este algoritmo permite que os nós da rede sejam sincronizados de forma a toda a
rede operar em torno de um tempo padrão. No entanto, não leva em consideração o
tempo utilizado para que a mensagem vá de um nó para outro chamado de tempo de
propagação da mensagem. Isto faz com que a precisão seja diminuída com a distância dos nós ao nó master. Outro problema que diminui consideravelmente a precisão é
o fato de algoritmo desconsiderar o tempo de construção da mensagem nos nós master que é determinístico mas que para o algoritmo deve ser considerado já que ocorre
a transmissão de uma referência absoluta de tempo. Então, para redes com grande
necessidade de precisão este algoritmo não poderia ser utilizado. Outro grande problema da utilização deste algoritmo para sincronização de redes de sensores sem fio
se deve ao fato de ser um algoritmo extremamente complicado e com um excesso de
procedimentos que são executados tantos nos nós clientes como nos master o que
aumenta consideravelmente o consumo de energia que é extremamente crítico neste
tipo de aplicação.
Em (SICHITIU; VEERARITTIPHAN, 2003), os autores apresentam um algoritmo
de sincronização para o deslocamento e dilatação temporal entre nós sensores. Devido a imprevisibilidade e imperfeição das mensagens em uma rede, a sincronização
de clock físico é sempre imperfeita como podemos observar no protocolo TDP apresentado na seção anterior. Na tentativa de solucionar este problema Sichitiu et al.
apresentam dois algoritmos apropriados para sincronização de dois nós da RSSF, um
deles chamado mini-sync e o outro chamado tiny-sync. As principais características
39
destes algoritmos são:
• Drift awareness: o algoritmo não somente considera dilatação temporal entre os
nós sensores, mas também encontra os ajustes da dilatação que permitem a
correção.
• Tight bounds on the precision: utilização de saltos determinísticos para calcular
o deslocamento e a dilatação temporal. Através destas informações absolutas
pode-se deduzir a ordenação de eventos simultâneos.
• Exatidão: considerando-se a incerteza devido ao tempo de propagação da mensagem, a precisão da sincronização obtida pelo método deverá ser arbitrariamente boa.
• Baixa complexidade de tempo e espaço: os nós da RSSF possuem características de baixa capacidade computacional com uma quantidade de memória RAM
pequena. Ambos os algoritmos têm baixa complexidade computacional e necessitam de uma pequena quantidade de memória RAM para operar.
• Robustez a erros de comunicação: a comunicação sem fio é notoriamente sujeita
a erro de comunicação, e então nem todas as mensagens são recebidas corretamente. Estes algoritmos então trabalham bem, mesmo quando uma grande
porcentagem de mensagens são perdidas.
O método proposto por Sichitiu et al. contribuiu consideravelmente para o desenvolvimento de um algoritmo simples que fornece informações exatas sobre deslocamento e a dilatação temporal aliado a um forte caráter determinístico. Estas propriedades são altamente desejáveis em uma RSSF.
2.3.1
Descrição do algoritmo
Considere dois nós em uma RSSF chamados de nó 1 e 2, com seus clocks t1 (t) e
t2(t) respectivamente, onde t é a coordenada universal de tempo (UTC).
Em geral o hardware do relógio do nó i é uma função monotônica não decrescente
no tempo t. Na prática, um oscilador de quartzo é usado para gerar a referência de
tempo real. A freqüência dos osciladores dependem das condições do ambiente, mas
40
em períodos relativamente grande de tempo pode ser considerado que possuem uma
boa exatidão. Para uma freqüência do oscilador fixa, tem-se que:
t i = ai t + bi ,
(2.1)
onde ai é a dilatação temporal do nó i, bi o deslocamento temporal, t é a coordenada
universal de tempo UTC e ti o tempo registrado pelo nó. Em geral, ai e bi serão
diferentes para cada nó e aproximadamente constantes por um grande período de
tempo.
Considerando o exemplo onde temos dois nós 1 e 2 e a equação 2.1, podemos
concluir que t1 e t2 são linearmente dependentes, sendo:
t1(t) = a12t2 (t) + b12.
(2.2)
Estes parâmetros a12 e b12 representam a dilatação e a deslocamento relativos
entre os dois clocks respectivamente. Em um exemplo onde os dois clocks estão
perfeitamente sincronizados, a dilatação relativa é igual a 1 e o deslocamento é igual
a zero.
Vamos considerar que o nó 1 tenha condições de hardware para determinar a
relação entre t1 e t2. O nó 1 envia uma mensagem de prova para o nó 2. A mensagem
de prova contém o instante de tempo t0 que é o tempo do relógio do sensor exatamente
antes ao envio. O nó 2 imediatamente após receber esta mensagem registra o seu
tempo local tb e envia uma mensagem para o transmissor,nó 1, contendo este tempo.
O nó 1 então novamente registra o tempo tr que ele recebeu esta resposta do nó 2. A
Figura 2.4 representa esta troca de mensagens.
As três referências de tempo (t0,tb ,tr ) podem ser utilizadas para determinar os
valores a12 e b12 na Equação 2.2. Então como t0 acontece antes de tb que acontece
antes de tr , as seguintes desigualdades se mantém:
t0(t) < a12t + b12 ,
(2.3)
tr (t) > a12t + b12 .
(2.4)
As medidas descritas acima serão repetidas por muitas vezes e cada conjunto de
dados fornecerá um ponto em um gráfico como aquele da Figura 2.5.
Cada conjunto pode ser representado por 2 restrições no sistema de coordenadas
41
Figura 2.4: Exemplo da comunicação feita com a transmissão de uma mensagem
partindo do nó 1 sendo imediatamente retornada pelo nó 2 para o nó 1 contendo
o seu tempo local. Cada conjunto de transmissão e recepção deste resulta em um
conjunto de dados (t0 ,tb ,tr ).
Figura 2.5: Dependência linear e restrições impostas para a12 e b12 para 3 conjuntos
de dados
.
42
dada pelo clock local dos dois nós t1 e t2. Uma restrição é (tb ,t0 ) e a outra é (tb ,tr ).
As desigualdades 2.3 e 2.4 graficamente requerem que a reta modelada pela
Equação 2.1 seja posicionada entre as duas restrições de cada conjunto de dados.
Os valores exatos de a12 e b12 não pode ser exatamente determinados já que o tempo
de espera entre as mensagens é desconhecido. Mas a12 e b12 podem ser relacionados:
a12 ≤ a12 ≤ a12 ,
(2.5)
b12 ≤ b12 ≤ b12 .
(2.6)
Onde a12 , a12 , b12 e b12 são, respectivamente as dilatações e os deslocamentos
temporais mínimas e máximas das retas de alinhamento entre os sensores 1 e 3.
Nem todas as combinações de a12 e b12 satisfazem as equações 2.5 e 2.6 e são
validas, mas todas as combinações válidas satisfazem as Equações 2.5 e 2.6. Os
parâmetros a12 e b12 podem ser estimados como a seguir:
∆a12
,
2
∆b12
,
b12 = bc
12 ±
2
a12 = ac
12 ±
onde
ac
12 =
(2.7)
(2.8)
a12 +a12
,
2
∆a12 = a12 − a12 ,
bc
12 =
b12 +b12
,
2
∆b12 = b12 − b12 ,
Uma vez estimado a12 e b12 , o nó 1 pode ser sempre ajustado lendo o clock local,
e usando a Equação 2.2 para ter as leituras corretas do nó 2.
2.3.2
Processamento de dados nos protocolos Tiny-sync e Minisync
Após obter os dados como descrito anteriormente, a dilatação e o deslocamento
podem ser estimados usando as desigualdades 2.3 e 2.4. Uma solução para encontrar
o valor ótimo no deslocamento e dilatação envolve resolver dois problemas de programação linear com ambas desigualdades dos muitos pontos adquiridos como descrito
43
anteriormente.
A desvantagem deste método é que, como mais e mais dados são obtidos, os custos computacionais de tempo e espaço aumentam. Além disso, o número de dados
obtidos irá influenciar diretamente na qualidade da previsão feita para o deslocamento
e a dilatação temporal. Sabe-se que os métodos de otimização devem ter uma complexidade computacional pequena devido a capacidade limitada dos nós sensores. Os
algoritmos então propostos por Sichitiu et al. não utilizam todos os dados obtidos para
estimar os parâmetros [a12 , a12 ] e [b12 , b12 ]. Na Figura 2.5, observamos que os parâmetros são restritos somente pelos conjuntos de dados 1 e 3, os quais possuem duas
restrições cada um. Então não é necessário o ponto 2, e este ponto pode ser então
descartado.
O algoritmo proposto então fará a análise dos dados utilizando apenas 4 restrições durante todo o período em que estiver operando. No processamento de um novo
conjunto de dados novas restrições serão comparadas com as quatro restrições existentes e 2 das seis serão descartadas. A operação de comparação decide quais das 4
restrições serão mantidas, o que é muito simples computacionalmente. Em qualquer
momento somente a informação para as 4 melhores restrições precisam ser gravadas.
Este algoritmo é chamado de tiny-sync. O algoritmo tiny-sync possui um baixo custo
computacional, mas no entanto, não garante a solução ótima.
O algoritmo chamado de mini-sync analisa se é possível ou não eliminar algumas
restrições que são irrelevantes para descobrir a solução ótima. Não sendo possível
o algoritmo trabalhará com um número maior de restrições fazendo com que o custo
computacional e de armazenamento aumente consideravelmente.
Como podemos observar o algoritmo é projetado para se fazer a sincronização
entre dois nós sensores da rede. Como as RSSFs são comumente projetadas em
camadas, é possível sincronizar todas as camadas com o nó raiz, mas isto precisará
ser feito de dois em dois nós o que aumentará consideravelmente o tráfego de dados
na rede e ainda acarretará em um decremento linear de acordo com o aumento de
camada na precisão da sincronização (SICHITIU; VEERARITTIPHAN, 2003).
2.4 Soluções específicas para RSSF
44
2.4 Soluções específicas para RSSF
Diante das dificuldades encontradas com as tentativas frustadas de adaptações
das metodologias clássicas, novas técnicas de sincronização temporal têm sido especialmente projetadas para RSSF (GLOBAL. . . , 2006; GANERIWAL et al., 2005;
MARóTI et al., 2004; PALCHAUDHURI; SAHA; JOHNSON, 2004; SICHITIU; VEERARITTIPHAN, 2003; RöMER, 2001; ELSON; GIROD; ESTRIN, 2002; ELSON; ESTRIN, 2001). Analisando-se individualmente os novos métodos propostos, observa-se
que cada um deles possui vantagens e desvantagens, não sendo possível ainda identificar uma metodologia específica como sendo a mais indicada para o desenvolvimento
de sistemas de sincronização em RSSF. Atualmente, a escolha de um dado método
tem sido definida pela aplicação de interesse e suas particularidades.
Dentro deste conjunto de novas técnicas, deve-se ressaltar a metodologia proposta
por Elson e Estrin (ELSON; ESTRIN, 2001; ELSON; GIROD; ESTRIN, 2002), conhecida como RBS (Reference Broadcast Synchronization), a qual é capaz de atingir uma
precisão de 1µ s e se baseia em sinais de clock não sincronizados.
2.5 RBS - Reference Broadcast Synchronization
Esta metodologia, embora alcance uma boa precisão de sincronização, exige um
meio de transmissão bidirecional entre os nós da rede com frequentes trocas de mensagens, e exige que a RSSF possua um canal físico de transmissão de um sinal de
broadcast. Esta última exigência faz com que esta técnica não possa ser utilizada
em redes que empregam conexões ponto-a-ponto. Neste esquema de sincronização
um sinal é enviado em Broadcast para todos os nós. Este sinal não contém dados
do tempo registrado pelo relógio do servidor. Então cada nó que recebeu este sinal
armazena o tempo do seu relógio local no instante que o broadcast é recebido. Os
nós então trocam informações sobre o momento que o broadcast foi recebido, pela
rede.
As tradicionais fontes de erro de sincronização têm 4 componentes distintos. Para
entender melhor estas fontes de erro é muito comum decompor a fonte de latência
da mensagem. A primeira fonte é chamado tempo de envio, que é o tempo gasto
para construir a mensagem no nó transmissor. A segunda fonte é chamada de tempo
de acesso, que é a espera que incorre para o acesso do canal de transmissão. A
45
terceira é o Tempo de Propagação, que é o tempo necessário para a mensagem ir do
transmissor ao receptor. Finalmente o Tempo de Recepção que é o tempo necessário
para processar a mensagem e notificar o nó sensor da chegada do broadcast. O
método de sincronização RBS elimina o erro introduzido pelo Tempo de envio e o
Tempo de acesso do caminho crítico. E como em redes que ocupam uma pequena
área o tempo de propagação é em torno de nanosegundos e a precisão considerada é
de microsegundos temos que este tempo de propagação poderá ser desconsiderado.
A propriedade fundamental do método RBS-Reference Broadcast Synchronization
é que uma mensagem de broadcast é usada para sincronizar apenas um conjunto
de receptores entre si, ao contrário dos protocolos tradicionais que sincronizam um
transmissor com um receptor de mensagens. Eliminando o erro pelo Tempo de Envio e
Tempo de Acesso do caminho crítico, como mostrado na Figura 2.6. Isto é uma grande
vantagem para sincronização em uma LAN, onde o Tempo de Envio e o Tempo de
Acesso são tipicamente os que mais contribuem para o não-determinismo na latência.
Na tentativa de resolver o problema causado por estas fontes de erro, o protocolo
RBS sempre usa uma referência de tempo relativa e nunca comunica um valor de
tempo absoluto. É exatamente esta propriedade que elimina os erros introduzidos pelo
Tempo de Envio e Tempo de Acesso. Cada receptor é sincronizado com um pacote de
referência que foi, por definição, inserido no canal físico do nós sensores, no mesmo
instante. A mensagem não contém o tempo do transmissor, nem é importante que
contenha.
A latência devida ao processamento nos receptores é irrelevante uma vez que é
determinística, e que o RBS trabalha com a diferença no tempo de recepção da mensagem. Além do mais,o clock do sistema pode facilmente ser lido por uma interrupção
quando o broadcast é recebido; isto diminui a espera devida à protocolo de processamento, à este tempo que o receptor leva para interpretar a mensagem dá-se o nome
de deslocamento de fase.
A forma mais simples do RBS é o broadcast de um único pulso para 2 receptores
permitindo então estimar seus deslocamento de fase relativos. Podemos descrever o
protocolo da seguinte maneira:
1. Um transmissor envia um pacote referência para dois outros receptores (i e j);
2. Cada receptor grava o tempo do seu relógio no qual o pulso referência foi recebido;
(a)
46
(b)
Figura 2.6: Análise do caminho crítico para um protocolo de sincronização tradicional
(a) e RBS (b). (ELSON, 2003)
3. Os receptores trocam informações sobre suas observações.
O desempenho deste método de sincronização é limitado pelos seguintes fatores:
• O número de receptores que se quer sincronizar (n). Aplicações colaborativas
frequentemente requerem a sincronização de muitos nós simultaneamente. Com
o crescimento do conjunto de sensores a ser sincronizados esta sincronização
se tornará cada vez mais pobre;
• O não determinismo dos receptores;
• A distorção do relógio dos receptores com seus osciladores possuem diferentes
freqüências. Uma única referência fará somente a sincronização instantânea.
Imediatamente após a sincronização terá uma significativa perda de qualidade
com o deslocamento do clock. A precisão decairá quanto mais tempo passar
desde o evento de sincronização.
A maior vantagem deste método é que todos os nós na rede são capazes de
automaticamente chegarem a um consenso sobre a sincronização. Os nós são ainda
capazes de serem sincronizados independente da distância entre eles. Este método
pode ser aplicado para sensores móveis de uma rede sem fio já que um consenso
sobre a sincronização pode ser determinado rapidamente entre os nós pois movimento
relativo dos nós não afeta adversamente a exatidão da sincronização.
Uma das limitações do RBS é que ele é um método de sincronização por evento
e não realiza uma sincronização dos relógios. Isto significa que enquanto eventos
entre redes serão sincronizados eles não podem considerar seus clocks como uma
referência que terá qualquer significado fora da rede (BROOKS et al., 2005). Outra
2.6 E-RBS - Eficient RBS
47
limitação é a necessidade que a rede tenha um canal de broadcast disponível para
transmissão dos pulsos de referência.
2.6 E-RBS - Eficient RBS
Observando uma deficiência do método RBS proposto em Elson et al. (ELSON;
ESTRIN, 2001) que se relaciona com o fato de a quantidade de mensagens de sincronização ser extremamente alta, Lee et al. (LEE; YU; KWON, 2006) propuseram
um novo método de sincronização, chamado por eles de E-RBS, fundamentado no
protocolo RBS mas com uma eficiência maior quanto a quantidade de mensagens de
sincronização. Esta versão eficiente do RBS pode ser usada em um meio com um
pequeno número de nós. No RBS, um nó específico envia um pacote de referência
em broadcast para os nós sensores que se quer sincronizar. Cada nó sensor grava
o tempo que as mensagens de referência foram recebidas de acordo com seu clock
local. Então os nós trocam informações sobre o momento que receberam este pacote.
No E-RBS o nó sensor determina se enviará informações do tempo ou não. Apenas
uma quantidade reduzida de sensores faz o envio da mensagem de broadcast. Para
decrementar o número de mensagens transmitidas, os nós não enviam um broadcast
todo o tempo, mas somente p% sensores enviam. E cada nó no E-RBS calcula a
informação de ajuste do clock.
Considerando uma certa quantidade de mensagens com erro na rede, o E-RBS
pode reduzir o número de mensagens geradas e melhorar o desempenho do sistema
em relação a eficiência de energia nos nós. Além disto pode sincronizar nós sensores
mais rapidamente que o protocolo RBS original.
Lee et ali. em (LEE; YU; KWON, 2006) descrevem que a desvantagem do RBS
original é a quantidade de mensagem enviada a todo tempo. As comparações feitas
pelo autor através do gráfico da Figura 2.7 mostram dados para taxas de broadcast (p)
de 70%, 60% e 50%. O autor constatou que para p=70% a exatidão alcançada é igual
a p = 100% (RBS original), enquanto ele gera somente 43% das mensagens de broadcast quando comparado ao RBS original. Quando p é 60%, ele gera apenas 30% das
mensagens do RBS original com uma exatidão também similar ao RBS original. Mas
para p=50% o tempo passado entre as mensagens aumentou consideravelmente o
que causou uma grande diminuição na precisão da sincronização.
Com este incremento no RBS, a eficiência energética é suficientemente aumen-
48
Figura 2.7: Gráfico comparativo para os protocolos de comunicação E-RBS e RBS
(LEE; YU; KWON, 2006).
tada. No entanto as outras desvantagens como necessidade de um canal físico para
broadcast e a sincronização baseada em eventos continuam.
O protocolo FTPS sincroniza o tempo de um transmissor com possíveis múltiplos
receptores utilizando uma única transmissão de mensagens de dados em ambos os
lados, transmissor e receptor, a qual contém informações do tempo registrado pelo
próprio clock. Entretanto a sincronização exata do tempo em pontos discretos é uma
solução parcial apenas. Um dos grandes problemas deste método de sincronização
é a necessidade inevitável de compensações para o deslocamento do clock dos nós,
as quais são necessárias para alcançar maior precisão na sincronização e manter o
overhead de comunicação baixo.
A mensagem que é enviada por meio do broadcast contém informações do clock
do transmissor que é o tempo global estimado na transmissão de um dado byte. Os
receptores obtém o correspondente tempo local dos seus respectivos clocks na recepção da mensagem. Consequentemente uma mensagem de broadcast provê um
ponto de sincronização ( um par de tempo global-local) para cada receptor. A diferença
entre o tempo global e o local de um ponto de sincronização estima o deslocamento
do receptor. Ao contrário do protocolo RBS, o clock do transmissor deve ser incluído
2.8 TPSN - Time Synchronization Protocol for Sensor Networks
49
na mensagem transmitida. Portanto, a medida do tempo no lado transmissor deve ser
feita antes do byte contendo o tempo transmitido.
A mensagem broadcast começa com a transmissão do byte de preâmbulo seguido
por um byte de sincronização SYNC. Após este byte de sincronismo são enviados os
dados que se quer comunicar, e a mensagem termina com um byte de checagem de
redundância cíclica (CRC). Durante a transmissão do byte de preâmbulo o receptor
sincroniza-se com a freqüência da portadora do sinal de entrada. Através do byte de
SYNC, o receptor pode calcular o bit de deslocamento temporal. Ele é necessário para
remontar a mensagem com o byte de alinhamento correto. O descritor da mensagem
contém o objetivo, o tamanho dos dados e outros campos, como o identificador da
camada de aplicação que precisa ser notificada no lado receptor. O byte de CRC é
usado para verificar que a mensagem não está corrompida.
A metodologia de sincronização FTPS possui uma boa exatidão. Esta metodologia
resolveu o problema anterior do RBS que era a necessidade de utilização da camada
de broadcast, mas ainda restou o problema de sobrecarga da rede pois a quantidade
de mensagem necessárias para a sincronização com a exatidão anunciada é muito
grande pois os clocks que utilizam cristais como gerador de freqüência possuem um
atraso da ordem de µ s a cada s. Este fato causa 2 impactos diretos para uma rede de
sensores sem fio, o primeiro é o fato de haver uma sobrecarga da rede aumentando o
número de colisões e retransmissões. O segundo impacto é o aumento do consumo
para a transmissão dos dados sendo este um ponto crítico do consumo de bateria.
2.8 TPSN - Time Synchronization Protocol for Sensor
Networks
Ganeriwal et al. (GANERIWAL; KUMAR; SRIVASTAVA, 2003) propõem um algoritmo de sincronização que se baseia no princípio de topologia hierárquica de redes
para sistemas distribuídos. Este algoritmo é baseado em dois passos fundamentais.
O primeiro passo do algoritmo é criar uma topologia hierárquica na rede. Todo nó é
associado a um nível hierárquico. A metodologia assume que um nó no nível i pode
comunicar com qualquer outro no nível i − 1. Somente um nó é associado ao nível 0,
que é chamado "nível raiz". Este estágio é chamado de "fase de descobrimento de
nível". Uma vez que a estrutura hierárquica tenha sido estabelecida, o nó raiz inicia
o segundo estágio do algoritmo, que é chamado de "Fase de sincronização". Nesta
50
Figura 2.8: Modelo de sincronização para o método TSPN
fase, um nó no nível i sincroniza com o nó i-1. Eventualmente todo nó na rede é
sincronizado com o nó raiz e desta forma é alcançada a sincronização em toda a rede.
Em geral, um nó usuário que atua como gateway entre nós sensores da rede e o
mundo externo pode atuar como nó raiz. O nó usuário pode ser equipado com um receptor GPS. Em muitos meios hostis onde é impossível ter uma entidade externa, o nó
raiz pode ser periodicamente alterado entre os nós da rede por meio de um algoritmo
de eleição. Neste caso, ilhas de nós sincronizados serão formadas na rede. Então um
esquema semelhante ao RBS pode ser usado para manter uma sincronização relativa
entre os nós adjacentes.
Quando o sistema é ligado ocorre a primeira fase que é a fase de determinação
dos níveis. Nesta etapa o nó que é determinado para ser o nó do nível 0 inicia esta
fase enviando um broadcast com o pacote level_discovery. Este pacote contém a
identidade e o nível do transmissor. Os vizinhos mais próximos do nó raiz recebem
este pacote e assumem eles próprios um nível maior ou menor que o nível que eles
receberam. Após estabelecer seus próprios níveis eles enviam em broadcast um novo
pacote de level_discovery contendo seus níveis. Este processo é continuado e todo
nó da rede é associado a um nível. Sendo associado a um nível um nó desconsidera
todo e qualquer pacote de level_discovery. Isto faz com que não haja excesso de
transmissão de dados durante esta fase. Então a estrutura hierárquica é criada com
apenas um nó raiz no nível 0.
Na próxima etapa, uma sincronização entre um par de nós é feita ao longo da
estrutura hierárquica estabelecida anteriormente. Uma troca de mensagem entre um
par de nós pode sincronizá-los. A Figura 2.8 mostra esta troca de mensagens entre
um nó A e B. Aqui T1 e T4 representam os instantes de tempo medido pelo clock local
de A. Da mesma forma T1,T2 representam os tempos medidos pelo clock local de B.
No tempo T1, A envia um pacote de pulso de sincronização contendo o número do
nível de A e o valor de T1. O nó B recebe este pacote em T2, onde T2 é igual a T1 +
51
∆ + d. Aqui ∆ e d representam o deslocamento do clock entre os dois nós e o tempo
de demora na propagação respectivamente. No tempo T3, B envia um pacote de
volta para A de acknowledgement. O pacote de acknowledgement contém o número
do nível de B e o valor de T1, T2 e T3. Assumindo que os deslocamentos do clock
e a demora na propagação não mudam em um pequeno espaço de tempo, A pode
calcular o deslocamento e a demora de propagação como:
∆=
(T 2 − T 1) − (T 4 − T 3)
(T 2 − T 1) + (T 4 − T 3)
;d =
.
2
2
(2.9)
Conhecendo o deslocamento, o nó A pode corrigir seu clock de acordo com o clock
de B. Esta é uma abordagem, onde o transmissor sincroniza seu clock com o receptor
(GANERIWAL; KUMAR; SRIVASTAVA, 2003).
Esta troca de mensagem na rede começa com o nó raiz iniciando a fase de
time_sync por um pacote de broadcast. Na recepção deste pacote, os nós ao longo
do nível 1 esperam por um tempo aleatório antes de iniciar a devolução da mensagem
para o nó raiz. Esta aleatoriedade evita a contenção em um acesso médio. Na recepção novamente de um acknowledgement, estes nós ajustam seus clocks para o
nó raiz. Os nós ao longo do nível 2 verão esta troca de mensagem. Isto é baseado
no fato que todo nó no nível 2 tem ao menos um nó do nível 1 na sua vizinhança. Na
escuta destas mensagens, os nós do nível 2 ficam fora da comunicação por um tempo
aleatório, após o qual eles iniciam a troca de mensagem com os nós do nível 1. Esta
aleatoriedade é para assegurar que nós no nível 2 iniciem a fase de sincronização
após os nós no nível 1 terem sido sincronizados.
Este processo é propagado através da rede e eventualmente todo nó é sincronizado
com o nó raiz. Em uma rede de sensores , colisões de pacotes podem ser frequentes.
Para lidar com este cenário, um nó sempre espera um acknowledgment e caso ocorra
um timeout é retransmitido o pulso de sincronização. Este processo continua até uma
mensagem ser bem sucedida. Este método conseguiu uma melhoria de desempenho
igual a duas vezes o desempenho da metodologia RBS em relação a sincronização. O
autor da metodologia não apresenta dados de consumo de bateria mas pela análise
da metodologia é possível observar que o consumo será consideravelmente maior
que na metodologia RBS pois há necessidade de mais trocas de mensagem. Este
aumento no número de mensagens como visto anteriormente afeta significativamente
o consumo de bateria. Um outro fator também importante é a escalabilidade a qual
também será consideravelmente afetada já que o método TPSN necessita de trocas
2.9 Considerações finais
52
constantes de mensagens causando um tráfego considerável de dados na rede.
2.9 Considerações finais
De uma forma geral, embora a maior parte dos novos métodos para sincronização
citados anteriormente procurem desenvolver estratégias para o uso racional de recursos em RSSF, minimizando-se assim o consumo de energia, observa-se que nenhum
dos métodos propostos conseguiu atingir de forma realmente eficaz este objetivo. É
neste contexto, que este projeto de dissertação de mestrado propõe uma metodologia
alternativa baseada na análise de sequências de imagens da dinâmica da cena, a qual
possa contribuir juntamente com as demais técnicas propostas na literatura para um
processo de se estimar a sincronização temporal que leve a resultados precisos, mas
que ao mesmo tempo não exija um alto consumo de energia na rede. Diferentemente
das metodologias existentes, este trabalho propõe que se estime uma linha do tempo
de referência, responsável pela recuperação das relações temporais entre os dados
dos sensores, a partir da informação medida por um dos próprios sensores da rede,
no caso, as imagens de uma câmera de vídeo.
53
3
FUNDAMENTAÇÃO TEÓRICA
Este capítulo apresenta alguns conceitos fundamentais relacionados à área de
processamento e análise de imagens, os quais formam a base teórica da técnica
proposta neste trabalho para sincronização em redes de sensores sem fio.
A visão é o nosso principal sentido, então não surpreende que imagens tenham
uma grande importância em nossas atividades. Entretanto, a visão humana é limitada
a uma pequena banda do espectro eletromagnético, que devido a isto, chamamos de
espectro do visível. Equipamentos de processamento e análise de imagens, também
chamados de equipamentos de visão computacional, ao contrário da visão humana,
operam com quase todo o espectro eletromagnético, desde os raios γ até ondas de
rádio. Eles podem tratar dados do espectro eletromagnético gerados por fontes que os
humanos não estão acostumados a associar com imagens já que não fazem parte do
espectro visível. São exemplos deste tipo de dados, infravermelho, ondas de rádio, e
ondas eletromagnéticas de alta energia como raios γ e outros. Por meio do tratamento
dos dados é possível transformar em imagens ondas que não fazem parte do espectro
eletromagnético como o ultrasom. Podemos concluir então que o processamento de
imagens digitais agrupa uma grande variedade de campos de aplicações.
Em (GONZALES; WOODS, 2007), os autores consideram três tipos principais de
tarefas durante o tratamento de imagens: processamentos de baixo, médio e alto nível.
Processamentos de baixo nível envolvem operações primitivas como processamento
de imagens para reduzir ruídos, aumento do contraste e restauração das imagens.
Um processamento de baixo nível é caracterizado pelo fato que ambos, entrada e
saída são imagens. Processamento de nível médio em imagens envolve tarefas como
segmentação (particionamento de uma imagem em regiões ou objetos), descrição de
54
Figura 3.1: Passos fundamentais no processamento de imagens (GONZALES;
WOODS, 2007).
como traduzir objetos para uma forma apropriada para processamento computacional
e classificação de objetos individuais. Um processamento de nível médio é caracterizado pelo fato que suas entradas geralmente são imagens, mas suas saídas são
atributos extraídos da imagem. Processamentos de alto nível envolvem determinar o
significado de um conjunto de objetos reconhecidos, por meio de análise de imagens,
e fazendo funções cognitivas normalmente associadas com a visão.
3.1.1
Passos fundamentais no processamentos de imagens digitais
A Figura 3.1 ilustra alguns dos passos fundamentais executados por um sistema
de processamento e análise de imagens.
• Aquisição de imagem: a capacidade de adquirir imagens que tornou possível
o processamento de imagens digitais. Este passo consiste em converter ondas eletromagnéticas em um valor numérico digital. Esta conversão é feita por
elementos fotosensores. Estas ondas podem ser provenientes de fontes de luz
visível ou outras freqüências do espectro.
• Realce de imagem: esta é uma das áreas mais simples do processamento
de imagens digitais. Basicamente, a idéia por trás das técnicas de realce é
55
trazer detalhes obscurecidos, ou simplesmente elucidar certas características de
interesse na imagem. Um exemplo familiar de realce é quando incrementamos o
contraste de uma imagem para observa-la melhor.
• Restauração de imagem: é uma área que tem como objetivo melhorar a aparência de uma imagem. Entretanto, de modo diferente do realce, que é subjetivo,
restauração da imagem é objetiva, já que técnicas de restauração tendem ser
baseadas em modelos estatísticos e probabilísticos de degradação de imagem.
Realce, por outro lado, é baseado em preferências humanas do que constitui um
resultado ótimo.
• Compressão: como o próprio nome já diz, são técnicas com o objetivo de reduzir o espaço necessário para salvar uma imagem, ou diminuir a velocidade
necessária para transmiti-la. Embora tecnologias de armazenamento tem tido
avanços significativos nas últimas décadas, o mesmo não pode ser dito da velocidade de transmissão. Isto é observado na internet que tem uma quantidade
considerável de imagens. A compressão de imagens é utilizada por usuários
para o armazenamento de arquivos, como por exemplo, os que utilizam extensões como jpg usado em imagens do formato JPEG.
• Segmentação: procedimentos que particionam uma imagem em suas partes
constituintes ou objetos. Em geral, segmentação automática é uma das mais
difíceis tarefas em processamento digital de imagens (GONZALES; WOODS,
2007). Um processo de segmentação ruim torna o processo de reconhecimento
do objeto mais longo e trabalhoso, ainda o levará à falha. Devido a isto, quanto
mais exato o processo de segmentação, maior será a chance de obter sucesso
no processo de reconhecimento do objeto ou parte do mesmo.
• Representação: usualmente trata-se de uma etapa posterior ao estágio de segmentação. Escolher uma representação é somente parte da solução para transformar um conjunto de dados em uma forma apropriada para a etapa de processamento subseqüente. Por isto, é importante escolher bem o método de
representação das características de interesse da forma ou região.
• Descrição: também chamada de seleção de características tem o objetivo de
extrair atributos que resultam em algumas informações quantitativas de interesse
ou características básicas para diferenciar uma classe de objetos de outra.
56
• Reconhecimento: é o processo que associa um rótulo a um objeto baseado em
seus descritores.
Os dados sobre o domínio de um problema são codificados em um sistema de
processamento de imagem na forma de uma base de dados. Esta base de dados
pode ser um simples detalhamento da região de uma imagem onde a informação de
interesse será encontrada, limitando a busca de uma determinada informação. A base
de dados pode ser muito complexa, como uma lista encadeada de todos os maiores
possíveis defeitos na inspeção de um material ou uma base de dados contendo imagens de satélite de alta resolução de uma região, com aplicações para detecção de
mudanças. Descreveremos agora com mais detalhes os tópicos citados acima de
maior interesse para o nosso trabalho, relacionando com o processamento digital de
imagens.
3.1.2
Aquisição de imagens digitais
Adquirir uma imagem digital envolve processos de transformação da imagem captada pelos sensores em números digitais que são posteriormente processados por
um computador. Os dois tipos de imagem normalmente utilizados em visão computacional, são:
• Imagem de intensidade, são as imagens fotográficas comuns onde intensidade
de luz codificada serão obtidas por meio de câmeras de vídeo.
• Imagens de profundidade, codificam apenas a forma e a distância obtidas por
sensores especiais como sonares ou scanners a laser.
Imagens de intensidade medem a quantidade de luz que atingem um dispositivo
fotosensível. Imagens de profundidade são obtidas diretamente da estrutura 3-D de
uma cena, visualizada através de uma variedade de técnicas.
É importante realçar que qualquer imagem digital, indiferente do tipo, é uma matriz
bidimensional de números. Na Figura 3.2 temos um exemplo para o tipo de imagem
de intensidade. Este formato de aquisição de imagens tem duas conseqüências fundamentais.
• A relação exata entre a imagem digital e o mundo físico é determinada pelo
processo de aquisição, que depende do sensor utilizado.
57
• Qualquer informação contida na imagem deve em última análise, ser extraída de
uma matriz bidimensional.
(a)
(b)
Figura 3.2: (a) Matriz bidimensional que representa uma imagem adquirida por uma
câmera digital cuja resolução é de 56 x 46 pixels. (b) Imagem adquirida com uma
câmera digital convertida para tons de cinza
A entrada para uma câmera de vídeo é, como se sabe, a luz que chega através
do conjunto óptico a seu plano de imagem. A Figura 3.2 verifica-se a existência de
uma matriz CCD com dimensões n x m contendo um grid de sensores fotosensíveis à
intensidade da luz. Cada fotosensor pode ser considerado como uma pequena caixa
preta retangular que converte energia da luz em tensão. A saída da matriz de CCD
é usualmente um sinal elétrico contínuo (o sinal de vídeo). Pode-se recuperar este
sinal gerado, ou seja, recuperar a imagem de vídeo, fazendo a varredura dos fotosensores na matriz de CCD em uma dada ordem e lendo suas tensões que foram
convertidas para um valor digital. O sinal de vídeo é enviado para um dispositivo
eletrônico chamado digitalizador de imagem de vídeo, onde é digitalizado e transformado em uma matriz bidimensional, contendo de M x N valores inteiros. Neste ponto,
as imagens podem ser convenientemente representadas por uma matriz E(M,N), cujos elememtos são chamadas de pixels (um acrônimo para picture elements), onde N
e M são dois inteiros expressando as dimensões da imagem. Finalmente a matriz E é
transferida para um computador para o processamento das imagens.
A respeito da matriz E podemos afirmar:
58
Figura 3.3: Esquema de um sistema para a aquisição de imagens digitais (TRUCCO;
VERRI, 1998).
E(M,N) denota a intensidade gravada pelo fotosensor da matriz de CCD em um
determinado pixel(M,N).
3.1.3
Parâmetros das câmeras
Algoritmos para reconstrução de estruturas 3-D de cenas ou para recuperação da
posição de objetos no espaço, necessitam de equações que relacionem as coordenadas de pontos 3-D no espaço com as coordenadas dos seus pontos correspondentes na imagem. Estas equações são escritas em relação ao sistema de eixos
coordenados de referência da câmera. Frequentemente assume-se que:
• O sistema de eixos coordenados de referência da câmera pode ser localizado
em relação ao sistema de eixos coordenados de referência no mundo.
• As coordenadas dos pontos no plano de imagem, relativos ao sistemas de eixos
coordenados da câmera podem ser obtidos a partir das coordenadas correspondentes em pixel.
Parâmetros Extrínsecos
O sistema de eixos coordenados da câmera foi introduzido com o propósito de
escrever as equações fundamentais da projeção em perspectiva. Entretanto, o sistema de eixos coordenados da câmera é muitas vezes desconhecido, e um problema
comum consiste em determinar a localização e a orientação do sistema de eixos coordenados da câmera em relação a algum sistema de eixos coordenados de referência
no mundo, usando somente informações da imagem. Os parâmetros extrínsecos são
definidos como um conjunto de parâmetros geométricos que identificam a transformação única entre o sistema de eixos coordenados de referência da câmera e um
sistema de eixos coordenados do mundo.
59
É comum descrever a transformação entre o sistema de eixos coordenados da
câmera e do mundo por meio de:
• Um vetor de translação 3-D, T, descrevendo a posição relativa das origens dos
dois sistemas de eixos coordenados,
• Uma matriz de rotação 3x3, R, que é ortogonal (R⊤ R = RR⊤ = I) e que é responsável por alinhar os sistemas de eixos coordenados da câmera e do mundo.
É importante ressaltar que as relações de ortogonalidade reduzem o número de
graus de liberdade de R para três.
Podemos observar na Figura 3.4 que a relação entre as coordenadas do ponto
P no sistema de eixos coordenados do mundo Pw , e as coordenadas do ponto P no
sistema de coordenadas da câmera, Pc pode ser expresso por:
Pc = R(Pw − T),
(3.1)
onde

r11 r12 r13




R=
 r21 r22 r23  .
r31 r32 r33
(3.2)
Então temos que os parâmetros extrínsecos são o vetor de translação, T, e a
matriz de rotação, R (ou melhor, seus parâmetros livres), que especificam a transformação entre os sistemas de eixos coordenados da câmera e do mundo.
Parâmetros intrínsecos
Os parâmetros intrínsecos podem ser definidos como o conjunto de parâmetros
necessário para caracterizar a geometria óptica e as características digitais da câmera.
Para uma câmera pinhole precisamos de 3 conjuntos de parâmetros intrínsecos os
quais especificam:
• A projeção perspectiva , cujo único parâmetro é a distância focal, f ;
• A transformação entre as coordenadas relativas ao sistema de coordenadas da
câmera e às coordenadas correspondentes em pixels;
60
Figura 3.4: A relação entre os sistemas de eixos coordenados da câmera e do mundo
• A distorção geométrica introduzida pelo sistema óptico;
Para encontrar o segundo conjunto de parâmetros intrínsecos, devemos associar
as coordenadas (xim , yim ) de um ponto na imagem em unidades de pixels com as coordenadas (x, y) do mesmo ponto no sistema de eixos coordenados da câmera. As
coordenadas (xim , yim ) podem ser determinadas como coordenadas de um novo sistema de eixos coordenados da câmera, algumas vezes chamado sistema de eixos
coordenados do plano de imagem.
Desprezando qualquer distorção geométrica introduzida pelo sistema óptico e na
suposição que a matriz CCD é composta por uma matriz retangular de elementos foto
sensíveis, tem-se que:
x = −(xim − ox )sx
y = −(yim − oy )sy
.
(3.3)
Sendo (ox , oy ) as coordenadas em pixels do centro da imagem (o ponto principal), e
(sx , sy ) os tamanhos efetivos dos pixels (em milímetros) na direção vertical e horizontal
respectivamente. Sendo assim, o conjunto de parâmetros intrínsecos é composto
pelos seguintes parâmetros f , ox , oy , sx , sy .
61
O sinal trocado na Equação 3.3 é devido ao fato de que os eixos horizontal e
vertical da imagem e do sistema de eixos coordenados da câmera tem orientações
opostas em relação aos eixos horizontal e vertical do sistema de eixos coordenados
do mundo.
Em muitos casos, o sistema óptico introduz distorções nas imagens. Estas distorções se tornam evidentes na periferia da imagem, ou em outra parte sempre que
se trabalha com grandes campos de visão. Felizmente, estas distorções foram modeladas como uma distorção radial simples por (TRUCCO; VERRI, 1998) de acordo com
as relações a seguir:
x = xd (1 + k1 r2 + k2 r4 )
y = yd (1 + k1 r2 + k2 r4 )
.
(3.4)
Como mostrado pela Equação 3.4, esta distorção corresponde a um deslocamento
dos pontos da imagem. O deslocamento é nulo no centro da imagem, e aumenta com
a distância do pontos ao centro da imagem. Os parâmetros k1 e k2 são parâmetros
intrínsecos adicionais. Uma vez que eles são muito pequenos, a distorção radial é
ignorada quando não é necessária uma precisão muito alta em todas as regiões da
imagem, ou quando os pixels periféricos podem ser descartados. Caso contrário,
como k2 ≪ k1 , k2 é frequentemente desprezado, e k1 é somente o parâmetro intrínseco
a ser estimado no modelo de distorção radial.
Sendo assim têm-se que os parâmetros intrínsecos são definidos como distância focal, f , a localização do centro da imagem em coordenadas em pixels,(ox , oy ), o
tamanho efetivo em pixel na direção horizontal e vertical (sx , sy), e se necessário, o
coeficiente de distorção radial, k1 .
Modelos de câmera
Podemos agora escrever as relações que ligam diretamente as coordenadas em
pixels de um ponto na imagem com as coordenadas correspondentes de um ponto 3-D
no mundo, sem explicitar referências para o sistema de eixos coordenados da câmera.
Para obtermos uma equação linear que nos dá a projeção de um ponto no mundo
para a imagem podemos escrever as equações básicas de projeção perspectiva para
o sistema de eixos coordenados da câmera:
62
x = f XZ
x = f YZ
.
(3.5)
Então, substituindo 3.1 e 3.3 na Equação 3.5 temos as seguintes equações lineares:
R⊤ (P −T)
−(xim − ox )sx = f R1⊤ (Pw −T)
3
w
,
−(yim − oy )sy = f
(3.6)
R⊤
2 (Pw −T)
R⊤
3 (Pw −T)
onde Ri para i = 1, 2, 3, é um vetor 3-D formado pela i-ésima linha da matriz R. De
fato, a Equação 3.6 relaciona as coordenadas 3-D dos pontos no mundo com as coordenadas correspondentes na imagem, por meio dos parâmetros extrínsecos e intrínsecos.
Desprezando a distorção radial, podemos reescrever a Equação 3.6 como um produto matricial. Para este propósito, definimos duas matrizes , Mint e Mext , como a
seguir:

− sfx

Mint = 
 0
0
Mext

0
ox


− sfy oy 

0
1

(3.7)
r11 r12 r13 −R⊤
1T


⊤T 
= x
r
r
r
−R
21
22
23
2


⊤
r31 r32 r33 −R3 T
Então a matriz Mint depende somente dos parâmetros intrínsecos, enquanto a matriz Mext depende somente dos parâmetros extrínsecos. Se adicionarmos uma quarta
coordenada igual a 1 em Pw o que significa expressá-lo em coordenadas homogêneas,
e formarmos o produto Mint Mext Pw , obtemos uma equação matricial descrevendo a projeção em perspectiva, que podemos determinar como sendo:
3.2 Calibração de câmeras
63



Xw



x1
 Y 


w 
 x2  = Mint Mext 

.


 Zw 


x3
1
(3.8)
Pode-se determinar a partir do vetor[x1 , x2 , x3 ]⊤ , dois parâmetros (x1 /x3 ) e (x2 /x3 )
que nada mais são que as coordenadas em pixel de um ponto no mundo:
x1
x2
= xim
.
x2
x3
(3.9)
= yim
A tarefa de calibração de uma câmera consiste em estimar os valores dos parâmetros intrínsecos e extrínsecos do modelo da câmera. A idéia chave da calibração
é:
Escrever as equações de projeção associando coordenadas conhecidas de um
conjunto de pontos 3-D no mundo e suas projeções no plano de imagem, encontrando
os parâmetros intrínsecos e extrínsecos para a câmera.
Para determinar as coordenadas de alguns pontos 3-D, métodos de calibração
baseiam-se em uma ou mais imagens de um alvo de calibração, que é um objeto 3-D
de geometria conhecida, possivelmente localizado em uma posição do espaço conhecida e gerando características da imagem que podem ser localizadas exatamente. A
Figura 3.5 mostra um padrão de calibração, consistindo de bolinhas pretas espalhadas
na cena de interesse.
3.2.1
Parâmetros diretos de calibração
Considere um ponto P em 3-D, definido por suas coordenadas [X w,Y w , Z w ]⊤ no sistema de eixos coordenados do mundo. Estas coordenadas no mundo são conhecidas.
Temos também que [X c,Y c , Z c ]⊤ são coordenadas do mesmo ponto porém referente
ao sistema de eixos coordenados da câmera. Usualmente, a origem do sistema de
eixos coordenados da câmera é o centro de projeção da mesma, e o eixo Z é o eixo
64
Figura 3.5: Figura do alvo de calibração planar
Figura 3.6: Modelo em perspectiva da câmera
óptico como podemos observar na Figura 3.6. A posição e orientação do sistema
de eixos coordenados da câmera são desconhecidos e diferentemente do sistema de
eixos coordenados do plano de imagem, o sistema de eixos coordenados da câmera é
inacessível diretamente. Isto é equivalente dizer que não conhecemos os parâmetros
extrínsecos da câmera, que é, a matriz R de rotação 3x3 e o vetor de translação 3-D
vetor T que fornece a relação:

Xc


Xw





 Y c  = R  Y w  + T.




c
w
Z
Z
(3.10)
65
A Equação 3.10 pode ser escrita como
X c = r11 X w + r12Y w + r13 Z w + Tx
X c = r21 X w + r22Y w + r23 Z w + Ty .
(3.11)
X c = r31 X w + r32Y w + r33 Z w + Tz
Assumindo que as distorções radiais podem ser desprezadas, podemos escrever
as coordenadas da imagem de [X c,Y c , Z c ]⊤ no sistema de eixos coordenados de referência no plano de imagem como:
f Xc
+ ox ,
sx Z c
f Yc
+ oy .
yim = −
sy Z c
xim = −
(3.12)
(3.13)
As equações 3.12 e 3.13 dependem dos cinco parâmetros intrínsecos, f (distância
focal), sx e sy (tamanhos efetivos dos pixels na horizontal e vertical), e ox e oy (coordenadas do centro da imagem). Devido a forma particular das equações 3.12 e 3.13,
os cinco parâmetros não são independentes. Entretanto, se nós fizermos fx = f /sx
e α = sy /sx , podemos considerar um novo conjunto de quatro parâmetros intrínsecos
ox , oy , fx e α , todos independentes um do outro. O parâmetro fx é simplesmente a distância focal expressa em pixels efetivos horizontais, enquanto α , usualmente chamado
de razão de aspecto, especifica a deformação induzida pelo processo de aquisição.
Substituindo as equações 3.11 em 3.12 e 3.13 temos:
x − ox = − f x
r11 X w + r12Y w + r13 Z w + Tx
,
r31 X w + r32Y w + r33 Z w + Tx
(3.14)
y − oy = − f y
r21 X w + r22Y w + r23 Z w + Tx
.
r31 X w + r32Y w + r33 Z w + Tx
(3.15)
Note que 3.14 e 3.15 desconsideram o sistema de eixos coordenados da câmera
e associam diretamente as coordenadas do mundo com as coordenadas da câmera
(x, y) do ponto correspondente da imagem. Se usarmos um padrão de calibração
conhecido, ambos vetores serão mensuráveis. Isto sugere que, dado um número
suficiente de pontos no padrão de calibração podemos tentar resolver 3.14 e 3.15
para conhecer os parâmetros. Esta é a idéia básica por trás da maioria dos métodos
de calibração.
3.3 Rastreamento de objetos
66
Especificamente, o algoritmo de calibração utilizado em nosso trabalho de pesquisa
é um algoritmo proposto por Heikkilä em (HEIKKILA, 2000). Este algoritmo mostra-se
mais pesado computacionalmente que métodos tradicionais de calibração, no entanto,
oferece uma precisão muito maior que estes métodos (HEIKKILA, 2000). O algoritmo
proposto por Heikkilä possui três passos. Como o primeiro passo, o objetivo é determinar um conjunto inicial de parâmetros através das técnicas citadas acima. No
segundo passo os parâmetros do modelo direto são estimados minimizando os pesos atribuídos a soma dos quadrados da diferença entre as observações e o modelo.
No terceiro passo são determinados os parâmetros de modelo reverso que fornecem
consistência aos resultados em ambas as direções.
Segundo o autor em (HEIKKILA, 2000) a precisão alcançada por este método é de
1/50 pixels. Como estamos considerando que as câmeras são estáticas, então a matriz de calibração será calculada apenas uma vez o que torna o custo computacional
baixo.
O rastreamento de objetos é uma das mais importantes tarefas no campo de Visão
Computacional. Em linhas gerais há três passos chaves na análise de vídeos com o
propósito de se fazer rastreamento de objetos: detecção de movimentos de interesse,
rastreamento quadro a quadro e análise da trajetória para reconhecer seus comportamentos.
A grosso modo, a tarefa de rastrear um objeto pode ser definida como o problema de se estimar sua trajetória no plano de imagem. Em outras palavras, um rastreador associa rótulos consistentes para os objetos rastreados em diferentes quadros
do vídeo. Rastrear um objeto pode ser muito difícil devido a vários fatores, tais como,
ruído nas imagens, complexidade de movimentos, oclusão do objeto total ou parcial,
objetos de forma complexa, mudanças na iluminação da cena e necessidades de processamento em tempo real.
Pode-se simplificar a tarefa de rastreamento impondo restrições aos movimentos
e/ou aparência dos objetos. Por exemplo, quase todos os algoritmos de rastreamento
assumem que no movimento do objeto não ocorrem mudanças bruscas, o que implica em restringir o movimento do objeto para ter velocidade constante ou aceleração
constante. O conhecimento a-priori sobre o número de objetos, seus tamanhos, ou a
67
aparência e forma, pode ser usados para simplificar a solução do problema.
3.3.1
Representação do objeto
Para se realizar o rastreamento de algum objeto em um vídeo é preciso que este
objeto possa ser localizado em cada quadro para assim determinar sua trajetória.
Com o objetivo de se fazer este rastreamento é necessário que o objeto que se deseja
rastrear tenha alguma forma de representação. Existem várias formas de se fazer
a representação de objetos sendo algumas delas mostradas na Figura 3.7. Nesta
figura vemos que os objetos podem ser representados por um ponto, que é o centróide (Figura 3.7(a)) ou por um conjunto de pontos (Figura 3.7(b)) (YILMAZ; JAVED;
SHAH, 2006). Em geral, a representação por pontos é apropriada para rastreamento
de objetos que ocupam uma pequena região na imagem. Outra forma de representar
um objeto é através da forma geométrica primitiva. O objeto é representado por um
retângulo ou elipse Figura 3.7(c) e (d) (YILMAZ; JAVED; SHAH, 2006). Embora as
formas geométricas sejam mais apropriada para representar objetos rígidos simples,
elas são usadas também para rastreamento de objetos não rígidos. Uma outra técnica
bem comum para representação de objetos em tarefas de rastreamento é baseada no
Contorno da silhueta do objeto (Figura 3.7(g),(h)). A região dentro do contorno é
chamada a silhueta do objeto (Figura 3.7(i)), A silhueta e a representação do contorno
são apropriados para rastreamento de objetos complexos não rígidos. Modelos de
formas articuladas são utilizados para objeto que tem partes que podem se mover,
e que sejam de interesse para o rastreamento de forma distinta. Objetos articulados são compostos por partes que são colocadas juntas. A relação entre as partes
são governadas pelo modelo de movimento cinemático. A fim de representar um objeto articulado podemos modelar as partes constituintes usando retângulos ou elipses
como mostrado na Figura 3.7(c)-(d). Na representação por Modelo do esqueleto o objeto pode ser determinado aplicando eixos medianos na silhueta do objeto. Este modelo é normalmente usado para representação e reconhecimento de objetos (YILMAZ;
JAVED; SHAH, 2006). A representação do esqueleto pode ser usada para modelar
objetos rígidos ou articulados (Figura 3.7(f)).
Algumas representações de aparência comuns no contexto de rastreamento de
objetos são:
Funções de densidade de probabilidade das aparências dos objetos que podem
ser paramétricas, como uma gaussiana ou uma mistura de gaussianas, ou não-paramétricas.
68
Figura 3.7: Representação de objetos.(a) Centróide, (b) múltiplos pontos, (c) Caminho
retangular, (d) caminho elíptico, (e) Baseado em múltiplas partes, (f) Esqueleto do
objeto, (g) contorno do objeto com pontos, (h) Contorno completo do objeto, (i) silhueta
do objeto (YILMAZ; JAVED; SHAH, 2006).
As funções de densidade de probabilidade das aparências dos objetos, podem ser calculadas a partir de regiões da imagem especificadas por modelos de formas (região
interior de uma elipse ou um contorno).
Modelos (templates) formados usando formas geométricas simples ou silhuetas.
Templates, entretanto, somente codificam a aparência gerada por um único ponto de
vista. Então eles são somente apropriados para rastreamento de objetos cujas orientações não variam consideravelmente durante o rastreamento.
Modelos de aparência ativa são gerados por modelamentos simultâneos da forma
e aparência do objeto. Em geral, a forma dos objetos é definida a partir de um conjunto
de marcos referenciais (landmarks). De forma semelhante a representação baseada
em contorno, os marcos referenciais podem estar nas bordas do objeto ou, alternativamente, podem estar dentro da região do objeto. Para cada marco um vetor de
aparência é armazenado, contendo informações de forma, cor, textura ou gradiente
de tamanho. Modelos de aparência ativa necessitam uma fase de treinamento onde
as formas e aparência associada são aprendidas de um conjunto de amostras.
Modelos de aparência para múltiplas vistas. Codificam diferentes vistas de um objeto. Uma abordagem para representar diferentes visualizações de um objeto consiste
em gerar um subespaço a partir das vistas dadas (YILMAZ; JAVED; SHAH, 2006).
3.3.2
Detecção de objetos
Todo método de rastreamento requer um mecanismo de detecção de objeto em
todos os quadros ou no primeiro quadro que o objeto aparece no vídeo. Uma abor-
69
dagem muito comum para detecção de objetos é usar informações vindas de um único
quadro. Entretanto alguns métodos de detecção de objetos fazem uso do cálculo de informações temporais, calculadas de uma seqüência de quadros para reduzir o número
de detecções falsas. Esta informação temporal é normalmente dada na forma de subtração de quadros, que elucida regiões alteradas nos quadros consecutivos. Dada a
região do objeto na imagem, é então a tarefa do rastreador fazer a correspondência
de um quadro para o próximo gerando a trajetória. Alguns métodos de detecção de
objetos são:
• Detecção de pontos que são usados para encontrar pontos de interesse em uma
imagem que tem uma textura expressiva em suas respectivas localizações, como
mostrado na Figura 3.8.
Figura 3.8: Detecção de objetos utilizando três métodos diferentes (a) Harris, (b) KLT
e (c) operadores SIFT
• Subtração do fundo da cena: pode ser alcançada construindo uma representação da cena chamada modelo de fundo, e então encontrando desvios do modelo para cada quadro de entrada. Qualquer mudança significante na região da
imagem do modelo de fundo, significa o movimento do objeto. Os pixels constituindo a região sobre investigação são marcados para processamento futuro.
Normalmente, um algoritmo de componente conectado é aplicado para obter
regiões correspondentes conectadas para os objetos. Este processo é chamado
de subtração de fundo. Na Figura 3.9 vemos um exemplo de aplicação desta
técnica.
• Segmentação: o principal objetivo de um algoritmo de segmentação de imagem
é particionar a imagem em regiões similares perceptíveis, como visto na Figura
3.10. Todo algoritmo de segmentação apresenta dois desafios, de determinar o
critério para uma boa partição e desenvolver o método para alcançar particionamento eficiente.
70
Figura 3.9: Exemplo da metodologia de mistura do modelo gaussiano para subtração
de fundo (YILMAZ; JAVED; SHAH, 2006).
Figura 3.10: Segmentação de uma imagem (a), Segmentação por deslocamentomédio (b) e Método de cortes normalizados(c) (YILMAZ; JAVED; SHAH, 2006).
• Aprendizado supervisionado: a detecção do objeto será feita aprendendo diferentes visualizações automáticas de um conjunto de exemplos por meio de um
aprendizado supervisionado. Dado um conjunto de exemplos aprendidos, métodos de aprendizado supervisionado geram uma função que mapeia entradas
para saídas desejadas. Uma formulação padrão do aprendizado supervisionado
é o problema de classificação onde o aprendiz aproxima o comportamento de
uma função.
Os algoritmos de rastreamento de objetos podem ser divididos em três categorias
diferentes
• Rastreamento de pontos: objetos detectados em frames consecutivos são representados por pontos, e a associação dos pontos é baseada no estado anterior
que pode incluir a posição do objeto e o movimento.
• Rastreamento de núcleos: refere-se à forma e aparência do objeto, por exemplo,
o núcleo pode ser um modelo retangular ou uma forma elíptica com um histograma associado. Objetos podem ser rastreados determinando o movimento
do núcleo em quadros consecutivos. Este movimento normalmente é realizado
na forma de uma transformação paramétrica semelhante com translação, rotação e afins.
71
• Rastreamento de silhueta: o rastreamento é feito estimando a região do objeto
em cada quadro. Métodos de rastreamento de silhueta necessitam de funções
de densidade de probabilidade das aparências de objetos e, modelos de formas,
que são representados com mapa de fronteiras. Ambos os métodos podem ser
considerados essencialmente aplicação de segmentação no domínio temporal,
usando o conhecimento dos quadros anteriores.
3.3.3
Rastreamento de pontos
As técnicas de rastreamento de pontos podem ser compreendidas como a correspondência da representação de objetos detectados por pontos através dos quadros.
Correspondência de pontos é um problema especialmente complicado na presença de
oclusões, detecções ruins, entradas e saídas de objetos na cena. Os métodos de correspondência de pontos podem ser dividos em duas grandes categorias, chamadas,
métodos determinísticos e métodos estatísticos. Os métodos determinísticos usam
heurísticas de movimento qualitativas (VEENMAN; REINDERS; BACKER, 2001) para
restringir o problema de correspondência. Por outro lado, métodos probabilísticos
explicitam a medida do objeto e consideram incertezas para estabelecer a correspondência.
Métodos determinísticos por correspondência, definem um custo associado a cada
objeto no quadro t − 1 para um único objeto no quadro t usando um conjunto de restrições de movimento. A minimização da função de custo da correspondência é formulada como um problema de otimização combinatória. Uma solução, que consiste
na correspondência um-a-um mostrada na Figura 3.11(b) através de todas as associações possíveis Figura 3.11(a). Em alguns casos podemos obter a solução ótima, por
exemplo, pelo método de busca gulosa. O custo da correspondência é usualmente
definido usando uma combinação das seguintes restrições, proximidade, velocidade
máxima, pequenas mudanças na velocidade, movimento comum, rigidez e uniformidade de pontos proximos.
Medidas obtidas de sensores de vídeo invariavelmente contém ruído. Além do
mais, o movimento dos objetos pode sofrer perturbações aleatórias, por exemplo,
manobra de veículos. Métodos de correspondência estatística resolvem estes problemas rastreando as medidas e as incertezas dos modelos durante a estimativa do
estado do objeto. Os métodos de correspondência estatísticas usam a abordagem do
espaço de estudos para modelar as propriedades do objeto como posição, velocidade,
72
Figura 3.11: Figura de rastreamento por correspondência de pontos. (a) Todas as
possiblidades de associação de pontos no quadro t − 1 com pontos no quadro t. (b)
Conjunto único de associação desenhados com linha negrito, (c) correspondência multiframe
e aceleração. As medidas normalmente consistem de posições de objetos na imagem,
que são obtidas por um mecanismo de detecção.
3.3.4
Rastreamento de núcleo
O rastreamento de núcleo é feito tipicamente determinando o movimento do objeto,
que é representado por uma região primitiva de um quadro para o próximo. O movimento do objeto é geralmente na forma de um movimento paramétrico (translação,
conformação) ou a determinação do fluxo de densidade calculado em quadros consecutivos. Estes algoritmos diferem em termos de aparência de representação usada,
o número de objetos rastreados e o método usado para estimar o movimento do objeto.
Jepson et al. 2003 (JEPSON; FLEET; EL-MARAGHI, 2003) propõem um rastreador de núcleo de objetos que utiliza uma mistura de três componentes, consistindo
das características de aparência estável, características de transientes e processo de
ruído. O componente estável identifica as características mais confiáveis para estimar
o movimento, que é, a região do objeto cuja aparência não muda rapidamente todo o
tempo. Os componentes transitórios identificam as mudanças rápidas nos pixels dos
quadros consecutivos. O componente de ruído utiliza os pontos fora da reta na aparência do objeto que surge devido ao ruído. Uma versão on-line do algoritmo é usado para
aprender os parâmetros das misturas destes três componentes. Os autores usam a
fase de filtros sintonizáveis respondendo como características para representação da
aparência. A forma do objeto é representada por uma elipse. O movimento do objeto
é calculado em termos de deformação da região rastreada um quadro após o outro. A
3.4 RANSAC - Random Sample Consensus
73
transformação da deformação consiste da translação, (tx ,ty), rotação (a, b), e escala, s,
sendo descrita pela Equação 4.3:
x′
y′
!
=s
a
b
−b a
!
x
y
!
+
tx
ty
!
.
(3.16)
A combinação de componentes estáveis e transientes é usada para determinar
os parâmetros degenerados. A vantagem do aprendizado estável e características
de transientes é que um pode dar mais peso para características estáveis para o
rastreamento, por exemplo, se a face de uma pessoa que está falando está sendo
rastreada, então a testa ou a região do nariz pode dar uma melhor correspondência
para a face no próximo quadro que a boca (Figura 3.12). Este trabalho utilizou com
sucesso a técnica proposta por Jepson et al. nos experimentos com cenas reais.
O algoritmo RANSAC (Random Sample Consensus) que foi introduzido por Fischer e Bolles em 1981 (FISCHLER; BOLLES, 1987) pode ser considerado como um
paradigma para ajustes robustos de modelos. Este algoritmo é robusto uma vez que
possui boa tolerância para pontos atípicos (outliers) nos dados experimentais. Além
disto, este algoritmo é capaz de interpretar e refinar dados contendo uma porcentagem significativa de erros grosseiros (FISCHLER; BOLLES, 1987). A estimativa será
considerada correta apenas se alcançar uma determinada probabilidade, uma vez
que o RANSAC é um estimador aleatório. Este algoritmo tem sido aplicado em uma
grande quantidade de problemas em visão computacional, como detecção de geometrias primitivas e segmentação de movimento (FISCHLER; BOLLES, 1987).
Embora o RANSAC seja um algoritmo bastante simples, ele é uma ferramenta
muito poderosa. Em um processo iterativo, ele aleatoriamente seleciona subconjuntos
da entrada de dados e calcula os parâmetros do modelo que melhor se ajustam às
amostras (FISCHLER; BOLLES, 1987). Amostras são selecionadas uniformemente
a partir do conjunto de entradas. Cada ponto tem a mesma probabilidade de seleção. Para cada amostra uma hipótese é construída calculando-se os parâmetros do
modelo. O tamanho da amostra depende do modelo que se quer encontrar, sendo
tipicamente, o menor tamanho necessário para determinar os parâmetros do modelo
(FISCHLER; BOLLES, 1987). Por exemplo, para encontrar um círculo no conjunto de
74
Figura 3.12: Resultado do rastreamento on-line usado por Jepson et al. (JEPSON;
FLEET; EL-MARAGHI, 2003). (a) A região do alvo em diferentes quadros. (b) A probabilidade do componente estável. Note que as probabilidades em torno da boca e
sombrancelha mudam, enquanto eles permanecem a mesma e em outras regiões
75
dados, é necessário determinar três pontos, uma vez que três pontos são suficientes
para determinar os parâmetros de um círculo.
3.4.1
Avaliação de hipótese
Em uma segunda fase, a qualidade dos parâmetros do modelo são avaliados no
conjunto completo de dados. Diferentes funções de custo podem ser usadas para a
avaliação, sendo comum se avaliar o número de pontos consistentes com o modelo
(FISCHLER; BOLLES, 1987). O processo é terminado quando a probabilidade de
encontrar um modelo melhor torna-se baixa. Normalmente, os parâmetros estimados
do modelo são recalculados, por exemplo, utilizando um método de linearização de
mínimos quadrados, para ajustar o subconjunto de dados que determinaram a melhor
estimativa. Os dados de entrada podem necessitar de muitos modelos diferentes.
Neste caso, os parâmetros para o primeiro modelo são estimados, os pontos de dados
que foram utilizados para o modelo são removidos dos dados de entrada e o algoritmo
é simplesmente repetido com o resto dos dados para encontrar o melhor modelo.
Dependendo no tamanho das amostras, o algoritmo RANSAC pode lidar bem com
níveis de ruído acima de 50% (FISCHLER; BOLLES, 1987).
3.4.2
Parâmetros para o RANSAC
O algoritmo do RANSAC usa três parâmetros para controlar o processo de estimativa do modelo (CANTZLER, 2004). O primeiro parâmetro (ε ) é uma tolerância para
o erro que determina um volume dentro do qual todos os pontos compatíveis devem
estar. O segundo parâmetro (p) é a probabilidade na qual pelo menos uma das seleções aleatórias produza um conjunto de candidatos sem erro. Finalmente, o terceiro
parâmetro (r) é a probabilidade que um candidato aleatoriamente selecionado tem de
ser um ponto que está dentro do modelo. Os parâmetros p e r definem o número de
iterações z do RANSAC como a seguir:
log(1 − p)
z=
.
log(1 − r2 )
(3.17)
A Equação 3.17 expressa o fato que z deve ser grande o suficiente para garantir que, com probabilidade p, pelo menos um conjunto de candidatos selecionados
aleatoriamente se ajuste ao modelo (inlier ).
3.4.3
76
Eficiência do RANSAC
A velocidade do RANSAC depende de dois fatores principais (CHUM; MATAS,
2002). Primeiro o número de amostras que devem ser encontradas para garantir uma
certa confiança e obter uma boa estimativa. Em segundo lugar, o tempo gasto para
avaliar a qualidade de cada modelo hipotético. O segundo fator é proporcional ao
tamanho do conjunto de dados.
Tipicamente, um número muito grande de parâmetros de modelos errados e de
amostras contaminadas são avaliados. Como os modelos são consistentes somente
com uma pequena fração de dados (CANTZLER, 2004), a avaliação dos modelos
pode ser otimizada computacionalmente fazendo uma avaliação aleatória(CHUM; MATAS, 2002). Cada modelo hipotético é primeiro testado com um pequeno número de
pontos aleatórios do conjunto de dados. Se o modelo não determina de forma adequada o conjunto aleatório, então assumimos com uma alta confiabilidade que o modelo não é uma boa estimativa. Novos modelos de conjuntos aleatórios são então
avaliados no conjunto completo dos dados.
O desempenho do RANSAC diminui com o aumento da quantidade de amostras ou
no caso de múltiplos modelos serem determinados pelos dados devido a diminuição
da probabilidade de amostragem de um conjunto que é composto inteiramente por
inliers. Uma observação muito comum é que outliers possuem uma distribuição difusa. Por outro lado, inliers tenderão ser localizados muito próximos uns dos outros.
Consequentemente, a amostragem uniforme dos pontos é trocada pela seleção de um
conjunto de amostras baseada na proximidade levando em conta a relação espacial
(MYATT et al., 2002). A seleção do conjunto de amostras de pontos adjacentes pode
aumentar significativamente a probabilidade de selecionar um conjunto de inliers e então reduzir o número de amostras necessárias para encontrar uma boa estimativa de
modelo.
77
4
TÉCNICA DE SINCRONIZAÇÃO
PROPOSTA
Especificamente, a técnica para sincronização temporal em redes de sensores
móveis desenvolvida neste projeto considerou um cenário no qual uma câmera estática adequadamente posicionada no ambiente seja capaz de visualizar os sensores
se movendo na cena durante um intervalo de tempo previamente especificado, como
ilustrado na Figura 1.6. Neste cenário, assumimos ainda que a câmera de vídeo utilizada é uma câmera do tipo pinhole calibrada.
Mediante o processo de calibração da câmera pode-se determinar seus parâmetros intrínsecos e extrínsecos. Estes parâmetros levam às equações que são utilizadas
para a projeção de pontos com coordenadas 3D no mundo para o plano de imagem
da câmera. sendo possível então utilizar estes parâmetros na determinação das trajetórias no plano de imagem, de sensores que se movimentam segundo trajetórias
3D conhecidas na cena monitorada. É fundamental para o método de sincronização
proposto que estes parâmetros levem a projeções no plano de imagem com uma boa
exatidão. Pois é desta forma que a trajetória do sensor no mundo poderá ser associada à trajetória correspondente no plano de imagem. Esta exatidão dos parâmetros
de calibração irá depender de quão exata é a determinação da localização dos pontos
no alvo de calibração utilizado. Uma vez que a câmera utilizada é estática, garante-se
que seus parâmetros intrínsecos e extrínsecos sejam constantes no tempo.
Partindo da idéia que os sensores utilizados bem como a câmera de vídeo operam a taxas de amostragem constantes, pode-se relacionar as coordenadas temporais (números dos quadros) na sequência de vídeo da câmera com as coordenadas
temporais das amostras da grandeza física medida pelo sensor por meio da seguinte
transformação afim unidimensional:
t i = αi t + β i ,
(4.1)
78
yc
q1( )
zc
q1(t)
e1
xc
~
q1(t1)
P
~
q2(t2)
Q1 ( )
q2(t)
e2
Q1(t1)
q2( )
plano de imagem
P
zw
yw
Q2(t2)
xw
Q2 ( )
Figura 4.1: Visualização de dois sensores móveis na cena de interesse, os quais
descrevem trajetórias Q1 (·) e Q2 (·), cujas projeções no plano de imagem da câmera
são denotadas por q1 (·) e q2 (·), respectivamente. Sejam q1 (t) e q2 (t) posições instantâneas estimadas pelo rastreador no quadro t. Sejam ainda Q1 (t1 ) e Q2 (t2 ) duas
amostras de posições dos sensores no sistema de coordenadas do mundo, cujas projeções calculadas com o auxílio de uma matriz de projeção P são denotadas por q1 (t1)
e q2 (t2).
onde ti é a coordenada temporal da grandeza física medida pelo sensor Si (i = 1, . . . , N),
t é o número do quadro na sequência de vídeo obtida pela câmera de referência c e
αi , βi são constantes desconhecidas que representam a dilatação e o deslocamento
temporal, respectivamente, entre o sensor Si e a câmera c. Em geral, estas constantes
não deverão ser números inteiros.
As relações entre as coordenadas temporais dos dados de um sensor com as
coordenadas temporais da sequência de vídeo da câmera, capturadas pela Equação
4.1, induzem uma relação global, a qual pode ser representada pela reta de N + 1
dimensões ζ a seguir:
ζ = {[α1 . . . αN + 1]⊤t + [β1 . . . βN + 1]⊤ |t ∈ ℜ}
(4.2)
79
A propriedade chave desta reta, pela qual a estimativa de pontos sobre a mesma
pode ser realizada sem o conhecimento prévio do alinhamento temporal entre os sensores e a câmera, permite a elaboração de um algoritmo simples para sua reconstrução a partir das trajetórias dos sensores na cena bem como de suas respectivas
projeções no plano de imagem da câmera de referência.
Considere, por exemplo, a Figura 4.1 onde uma câmera visualiza dois sensores
móveis na cena de interesse. Nesta figura, as trajetórias dos centros de massa dos
sensores no sistema de coordenadas do mundo são representadas por Q1 (·) e Q2 (·),
enquanto suas projeções no plano de imagem da câmera são denotadas por q1 (·) e
q2 (·), respectivamente. Suponha que as trajetórias dos sensores no plano de imagem
tenham sido estimadas mediante o uso de um sistema de rastreamento automático
de objetos (SHI; TOMASI, 1994; ISARD; MACCORMICK, 2001; JEPSON; FLEET; ELMARAGHI, 2003). O sistema de rastreamento é o que torna possível determinar a
posição em pixels do sensor em cada quadro da sequência de imagens obtida pela
câmera. É importante que a trajetória do sensor seja uma trajetória contínua, ou seja,
uma trajetória suave pois a complexidade de movimentos torna o rastreamento uma
tarefa muito pesada computacionalmente, tornando o processamento em tempo real
uma tarefa extremamente complexa. Devido ao fato de o sensor ser um objeto rígido
pode-se escolher uma representação de forma a simplificar a tarefa de rastreamento.
Conclui-se então que o modelo de rastreamento de núcleo é o método que apresenta
característica mais adequadas as necessidades da pesquisa.
No rastreamento de núcleo o sensor móvel é representado por uma região primitiva, esta região é determinada por uma forma fundamental que pode ser uma elipse
como no exemplo da Figura 4.2. O método de rastreamento de núcleo consiste em
identificar o sensor através de uma mistura de três componentes, dentro da forma
fundamental, consistindo das características de aparência estável, características de
transientes e processo de ruído.
O movimento do sensor é determinado em termos da deformação da região rastreada um quadro após o outro. A transformação da deformação consiste da translação,
(tx ,ty), rotação (a, b), e escala, s, que são relacionados de acordo com a equação 4.3:
x′
y′
!
=s
a
b
−b a
!
x
y
!
+
tx
ty
!
(4.3)
Os parâmetros iniciais utilizados pelo rastreador em nossos experimentos com
80
Figura 4.2: Figura do robô com uma região de rastreamento no centro de massa em
forma de elipse.
cenas reais foram a = 5, b = 10, x = 166 e y = 6 que é a localização do centro de
massa do robô que possui o sensor, no primeiro quadro da sequência. A partir daí
o rastreador vai determinando as variáveis x′ , y′ e atualizando as matrizes quadro a
quadro.
A partir do algoritmo acima a trajetória do sensor na câmera é determinada com
um erro já previamente conhecido. As trajetórias dos sensores no sistema de coordenadas do mundo podem ser estimados com o auxílio de odômetros e sistemas de
GPS, por exemplo.
Assumindo-se que a câmera utilizada é uma câmera do tipo pinhole e está calibrada, pode-se estimar para cada posição do sensor no sistema de coordenadas do
mundo sua correspondente projeção no plano de imagem da câmera, a partir da utilização de uma matriz de projeção P. Na Figura 4.1, por exemplo, duas amostras de
posições Q1 (t1 ) e Q2 (t2 ) dos sensores no sistema de coordenadas do mundo possuem
projeções q̃1 (t1 ) e q̃2 (t2 ) no plano de imagem, as quais foram calculadas usando-se P.
Observa-se na Figura 4.1 que a partir da busca de associações no plano de imagem entre posições dos sensores estimadas pelo rastreador com as suas posições
calculadas por meio da matriz de projeção P, pode-se adicionalmente inferir correspondências entre as coordenadas temporais dos dados dos sensores e da câmera.
Considere, por exemplo, as posições instantâneas q1 (t) e q2 (t) na Figura 4.1, correspondentes ao quadro t da sequência de vídeo. Assumindo-se que q1 (t) e q2 (t)
81
Figura 4.3: Exemplo de um espaço de alinhamentos temporais "candidatos"(votos)
para dois sensores na cena. Neste caso, tem-se um espaço de 3 dimensões.
tenham correspondências temporais com as posições Q1 (t1) e Q2 (t2) no sistema de
coordenadas do mundo, conclui-se que as projeções q̃1 (t1 ) e q̃2 (t2) deverão coincidir
no plano de imagem com os pontos q1 (t) e q2 (t) ou estarem a distâncias ε1 e ε2 , cujos
valores são funções dos erros, do rastreador e do sistema de calibração da câmera.
Note que a partir desta observação, pode-se inferir que as coordenadas temporais
t, t1 e t2 referentes ao quadro da sequência de vídeo e das amostras das posições
dos dois sensores, respectivamente, devem representar o mesmo instante de tempo
no qual as medições realizadas pelos sensores nas posições Q1 (t1 ) e Q2 (t2) foram
efetuadas. Considerando-se um número genérico N de sensores na cena, pode-se
derivar com base neste raciocínio um conjunto ν de pontos com N + 1 dimensões que
representam alinhamentos temporais "candidatos” entre os dados dos N sensores e
os quadros da sequência de vídeo da câmera:
ν = {[t . . .tn]⊤ |D(qi (t), q̃ j (t j )) ≤ ε , para (i, j) = 1, . . ., N},
(4.4)
onde D(·) é uma função que calcula a distância euclidiana entre dois pontos e "representa” um valor de tolerância em pixels, o qual é dado pela média dos erros dos
sistemas de rastreamento e calibração.
Em geral, o conjunto ν definido na Equação 4.4 é composto não somente pelos
82
pontos sobre os quais passa a reta que captura as relações temporais entre os dados
dos sensores e da sequência de vídeo, mas também por diversos pontos espúrios,
os quais eventualmente também poderão satisfazer a restrição definida na Equação
4.4. A Figura 4.3 ilustra um possível espaço de alinhamentos temporais "candidatos”
(votos) no caso de uma cena composta por apenas dois sensores móveis.
Dado o espaço de votos, o próximo passo consiste em reconstruir a reta responsável por representar a linha do tempo de referência. Para se reconstruir tal reta, a
metodologia proposta neste trabalho utiliza o algoritmo RANSAC.
Observa-se pela Equação 4.1 que o mínimo de pontos necessários para determinar os parâmetros livres do modelo que recupera o alinhamento temporal entre a
câmera e os sensores são 2, uma vez que trata-se de uma equação linear. Aleatoriamente é selecionado um subconjunto S1 de dois pontos entre todos os dados formando
um conjunto W e o modelo inicial, que no problema aqui pesquisado é o de uma reta.
Utiliza-se o modelo da reta para determinar o subconjunto S1∗ de todos os pontos que
estão dentro de uma tolerância de erro da reta que se ajustou aos parâmetros determinados pelos dois pontos. O conjunto S1∗ é chamando conjunto consenso de S1 .
Se a quantidade de dados presentes no conjunto S1∗ é maior que um valor l, que
é uma função da estimativa do número de dados com erros grosseiros em W , usa-se
S1∗ para determinar um novo modelo M1∗ . Se a quantidade de dados de S1∗ é menor
que l. aleatoriamente seleciona um novo subconjunto S2 e repete o processo acima.
Se após um número predeterminado de repetições, nenhum conjunto consenso com
l ou mais dados foi encontrado, É feita a escolha do conjunto com o maior número
de dados encontrado, ou termina em falha. Existem três parâmetros principais para o
algoritmo RANSAC:
1. A tolerância ao erro utilizada para determinar se é ou não compatível com o
modelo linear proposto
2. O número de iterações para que sejam testados subconjuntos
3. O parâmetro l, que é o número de pontos compatíveis usados para implicar que
o modelo correto foi encontrado.
Se o modelo é uma função simples dos pontos de dados ou seja é possível determinar um modelo que prevê o comportamento de todos os dados, é útil estabelecer
a tolerância ao erro analiticamente. A variação na tolerância de erro é normalmente
83
relativamente pequena considerando-se o valor dos erros grosseiros. Então um único
erro para todos os dados normalmente é suficiente. No entanto, não existe nenhuma
regra para determinação deste parâmetro. Neste caso foi feito testes com três parâmetros diferentes sendo escolhido os erros máximos de 1,3 e 5 amostras de forma
que o tempo máximo de erro de alinhamento temporal não ultrapasse 1,66s.
O número máximo de iterações z foi determinado através da fórmula
log(1 − p)
z=
,
log(1 − r2 )
(4.5)
onde p é a probabilidade de que pelo menos um dos subconjuntos selecionados esteja
sem erros e r é a probabilidade que um conjunto selecionado aleatoriamente seja um
ponto sobre a reta determinada pelo modelo.
A Equação 4.5 expressa o fato que z deve ser grande o suficiente para garantir que,
com a probabilidade p, pelo menos um par de candidatos aleatoriamente selecionado
corresponda ao modelo linear selecionado. Usou-se p = 0, 99 e r = 0.05(z = 1800 iterações) para todos os experimentos, os quais são valores bastante conservadores que
garantem resultados exatos em todos os experimentos, como será demonstrado no
capítulo 5. Para o nosso método podemos observar que todas as vezes que o algoritmo RANSAC foi utilizado encontrou o modelo correto, devido a isto, não foi utilizado
o parâmetro l.
Após a estimativa realizada pelo RANSAC do potencial conjunto de candidatos sobre os quais a reta deva passar, a metodologia proposta neste projeto é que se utilize
o método dos mínimos quadrados sobre este conjunto para se estimar os parâmetros
da reta.
Dada a equação da reta, pode-se então estabelecer as relações temporais demandadas pela aplicação em questão.
Consequentemente para especificar completamente o algoritmo de alinhamento
respondemos três questões:
1. Como determinar a trajetória característica qi (·), para i = 1, . . ., N?
2. Como estimar o conjunto ν para cada qi (ti )?
3. Como determinar o alinhamento temporal ζ
A seguir é apresentado o algoritmo desenvolvido para a técnica de sincronização
proposta neste trabalho.
84
85
Algoritmo de alinhamento temporal
Entrada
1: N; {Número de sensores}
2: P; Matriz de parâmetros da câmera
Saída
3: [α1 . . . αN ]⊤ ; { Parâmetros de dilatação temporal da reta de alinhamento ζ .}
4: [β1 . . . βN ]⊤ ; {Parâmetros de deslocamento temporal da reta do tempo ζ . }
INÍCIO
5: Passo 1 - Gerar o espaço de votos:
ν = [t . . .tn ]⊤ |D(qi (t), q̃ j (t j )) ≤ ε para (i, j) = 1, . . . , N.
6: for i ←− 1 to N do
7:
Obtenha a trajetória dos sensores no mundo Qi (·).
8: end for
10:
Faça o rastreamento da trajetória do sensor q̃i (·)
no plano de imagem
11: end for
13:
14:
for c ←− 1 to Cada ponto da trajetória no mundo do
for d ←− 1 to cada ponto da trajetória do sensor i do
if a distância euclidiana D entre qi (t) posição do sensor obtida
15:
pelo rastreador estiver a uma distância menor que ε de
q̃i (t j ) (posição projetada)
16:
if esta distância é a menor encontrada
17:
Armazene as coordenadas temporais t do quadro da câmera para cada
amostra t j do sensor
18:
end if
19:
20:
21:
end if
end for
end for
22: Construa o conjunto νqi (t) através dos dados de todos os quadros t
concatenando então na forma de uma matriz unidemensional [t1 . . .tN ]
23: end for
24: Construa o espaço de votos fazendo a união de todos os conjuntos νqi (t) .
25: {Passo 2- Determina a reta ζ para a junção de todos os conjuntos estimados νqi (t) }
86
26: Aplique o algoritmo do RANSAC no espaço de votos para determinar
o conjunto de dados que melhor ajusta a linha ζ desejada.
27: Aplique o método dos mínimos quadrados sobre todo o conjunto de dados
estimados pelo RANSAC para determinar os parâmetros da reta: [α1 . . . αN ]⊤ e [β1 . . . βN ]⊤ .
28: return([α1 . . . αN ]⊤ [β1 . . . βN ]⊤ )
END
Como podemos observar o método de sincronização proposto utiliza um algoritmo
bastante simples. No próximo capítulo descreveremos os resultados da aplicação
deste algoritmo em seqüências reais e sintéticas.
87
5
Resultados experimentais
Neste capítulo, é apresentado e discutido os resultados experimentais da aplicação da técnica de sincronização desenvolvida em uma cena real, em cenas sintéticas e um resultado adicional referente à extensão da aplicação da técnica para sincronização de câmeras que não possuem sobreposição de campos de visão. Primeiro,
na Seção 5.1, fez-se uma análise de seqüências reais e sintéticas que tem como objetivo mostrar o comportamento do algoritmo de sincronização temporal em uma rede de
sensores móveis, buscando-se avaliar a aplicabilidade, a escalabilidade e a exatidão
da metodologia proposta diante da variação de parâmetros críticos para a qualidade
dos alinhamentos temporais calculados. Na Subseção 5.1.1 são apresentados os resultados obtidos para a simulação de diversos cenários onde as variáveis de interesse
do sistema puderam ser controladas. Foram Apresentadas medidas quantitativas da
qualidade dos alinhamentos temporais como função de três fatores principais: (1) A
exatidão da estimativa inicial dos parâmetros intrínsecos e extrínsecos que capturam
as relações geométricas entre as trajetórias dos sensores no mundo e suas projeções
no plano de imagem; (2) a quantidade de ruído no sistema de rastreamento e (3) o
número de sensores sincronizados. Na Sub-seção 5.1.2 mostramos a aplicação da
técnica em uma seqüência de vídeo obtida de um cenário dinâmico real composto por
um único sensor móvel, especificamente um robô Pioneer 3 AT produzido pela Active
Media (ver Figura 5.9(a)). Por meio deste cenário simples conseguimos demonstrar
a aplicabilidade do método que foi exaustivamente testado com as seqüências sintéticas.
5.1 Sincronização de Sensores Móveis
88
5.1.1
Seqüências Sintéticas
Por meio do uso de um simulador, desenvolvido com o auxílio do software MATLAB, foram criadas cenas dinâmicas artificiais contendo sensores móveis distribuídos
em uma rede ad hoc. Nestes cenários artificiais, foram simulados os processos de
monitoramento dos sensores a partir de uma câmera de vídeo calibrada, responsável
pela geração das seqüências de vídeo sintéticas. Os parâmetros intrínsicos e extrínsicos referentes à câmera artificial possuíam valores idênticos aos valores dos parâmetros de uma câmera real (modelo Sony DCR-TRV320 Digital Camcorder) utilizada
em experimentos anteriores.
Nesta fase dos experimentos, buscou-se fundamentalmente estudar os efeitos de
dois parâmetros críticos para a exatidão do alinhamento temporal entre os sensores,
especificamente o (i) nível de ruído do sistema de rastreamento e o (ii) nível de ruído
no sistema de calibração da câmera. Os valores atribuídos a estes parâmetros, bem
como aos demais parâmetros utilizados durante as simulações são listados na Tabela
5.1.
Os níveis de ruído no sistema de rastreamento e no sistema de calibração foram
simulados como ruídos brancos gaussianos de média zero e desvios padrões variáveis conforme a Tabela 5.1. Para cada par possível de níveis de ruído de rastreamento
e calibração, foram simulados 100 eventos dinâmicos distintos na cena artificial. Em
seguida, dados os espaços de votos dos eventos dinâmicos simulados, foram calculados os percentuais das retas que capturam o alinhamento temporal e que levam a
erros de alinhamento temporal médios menores ou iguais a 1, 3 e 5 amostras. Especificamente, os valores destes erros são dados pela média dos valores absolutos
Parâmetros
Num. Sensores
Erro Rastreador
Erro Calibração
Num. Quadros
p (RANSAC)
r (RANSAC)
ε (RANSAC)
Valores
{1, 2}
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} pixels
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} pixels
256
0, 99
0, 05
0, 5
Tabela 5.1: Valores dos parâmetros utilizados durante as simulações.
89
das diferenças entre as coordenadas temporais determinadas pela reta estimada e as
coordenadas temporais determinadas pela reta de referência que modela o deslocamento temporal real entre os sensores e a câmera:
tik = αit k + βi ,
(5.1)
onde tik é a coordenada temporal da grandeza física medida pelo sensor Si (i = 1, . . ., N)
e t k é o número do quadro na seqüência de vídeo obtida pela câmera de referência c
determinados pelo modelo.
Por esta razão, se tie representa a coordenada temporal correspondente a t k , determinada usando a reta estimada pelo nosso método, o erro de alinhamento temporal
médio εt é dado por:
εt =
1 M−1 e k
|ti (t ) − tik (t k )|,
M t∑
k =0
(5.2)
onde M é o número de quadros na seqüência de vídeo obtido pela câmera.
Dentre os experimentos realizados com cenas sintéticas, foram selecionados e
são mostrados neste trabalho alguns resultados obtidos para os casos 2D e 3D, os
quais referem-se, respectivamente, ao cenário trivial no qual as cenas contém apenas
um sensor móvel e ao cenário no qual as cenas possuem dois sensores móveis. Nas
Figuras 5.1 e 5.2 observa-se espaços de votos 2D e 3D, onde foram simulados ruídos
no sistema de rastreamento com desvio padrão 5 e 10 pixels. Pode-se observar também as retas que recuperam o alinhamento temporal entre os sensores e a câmera
e que levam a erros menores ou iguais a 1 amostra Figuras 5.1(a)-(b) e 5.2(a)-(b), 3
amostra Figuras 5.1(c)-(d) e 5.2(c)-(d) e 5 amostras Figuras 5.1(e)-(f) e 5.2(e)-(f) . Um
outro experimento de interesse é a variação do ruído no sistema de calibração cujos
resultados são apresentados nas Figuras 5.5 e 5.6. Neste experimento temos que o
desvio padrão do ruído no sistema de rastreamento é fixo e igual a 2 pixels. Foi acrescentado um ruído nas matrizes de projeção com desvio padrão de 5 e 10 pixels. Os
resultados exibidos nas Figuras 5.3 e 5.4, correspondem aos percentuais de retas de
alinhamento temporal, onde o desvio padrão no ruído do rastreador varia de acordo
com a Tabela 5.1. Estes gráficos mostram resultados de alinhamentos temporais que
levam a erros médios menores ou iguais a 1,3 e 5 amostras. É importante ressaltar
que estes erros são razoáveis para a grande maioria das aplicações.
Analisando-se a Figura 5.3(a), observa-se que em cenários nos quais o ruído no
sistema de rastreamento é pequeno (desvio padrão igual a 1), o método de alinha-
90
mento temporal proposto conseguiu recuperar, em pouco mais de 50% das vezes,
retas que levam a erros médios menores ou iguais a 1 amostras. Este resultado
apresenta-se muito conservador já que o erro de uma amostra, em uma câmera comum de 30 quadros por segundo (30fps), que representa uma precisão no alinhamento de 33,33ms. É importante considerar que esta precisão dependerá apenas da
taxa de quadros da câmera e não do método. Utilizando uma câmera com a taxa de
quadros maior a precisão aumentará sem a necessidade de alteração no método de
sincronização. Observa-se ainda neste gráfico que mesmo para condições de ruídos
extremamente adversas no sistema de rastreamento, como para ruídos em torno de
10 pixels, ainda assim o algoritmo consegue determinar o alinhamento correto em
aproximadamente 10% dos casos. Conclui-se que isto é uma característica importante do nosso método, pois este ruído de 10 pixels, refere-se ao ruído adicionado na
trajetória do robô projetada no plano de imagem da câmera, o que representaria um
erro de projeção igual 20,08% do seu campo de visão. Este erro é sem dúvida um
valor que dificilmente será encontrado em qualquer sistema de projeção da trajetória
dos sensores móveis. Observamos que pelo gráfico da Figura 5.3(b), para os mesmo
níveis de ruídos mas para retas que recuperam o alinhamento com erros menores ou
iguais a 3 amostras o cenário já mostra-se mais favorável levando a porcentagem de
retas recuperadas superiores a 60% mesmo para desvio padrão dos ruídos de até 10
pixels. A porcentagem de alinhamentos que recuperam retas com erros inferiores a 5
amostras está acima de 70% mesmo para condições onde o desvio padrão do ruído
no sistema de rastreamento é de 10 pixels como mostrado na Figura 5.3(c). Para o
caso onde tem-se uma cena composta por dois sensores s1 e s2 mostrado na Figura
5.4 tem-se um comportamento do gráfico de percentual de retas recuperadas extremamente parecido com os gráficos da Figura 5.3 sugerindo que a exatidão do algoritmo
de alinhamento independe da quantidade de sensores na cena.
Nas Figuras 5.7 e 5.8 são exibidos os percentuais de retas recuperadas com erros
menores ou iguais a 1, 3 e 5 amostras, para o experimento onde tem-se um erro no
sistema de rastreamento fixo e igual a 2 pixels e é feita a variação do ruído no sistema
de calibração da câmera. Estes resultados mostram que o ruído acrescentado no
sistema de calibração não teve o mesmo efeito que o ruído acrescentado no sistema
de rastreamento. Especificamente, comparando-se as Figuras 5.7 e 5.3 observa-se
que o ruído acrescentado no sistema de rastreamento, tende a ser mais crítico que
o ruído no sistema de calibração da câmera. Observa-se, por exemplo, que para um
ruído no sistema de calibração igual a 5 pixels e o erro máximo no número de amostras
91
igual a 3, Figura 5.7(b) tem-se o percentual de acerto é de aproximadamente 100%. Já
para as mesmas condições mas com a variação do ruído no sistema de rastreamento,
Figura 5.3(b), temos um percentual de acerto de aproximadamente 80%.
Na Figura 5.8 tem-se os gráficos de percentuais para retas recuperadas para uma
cena composta por dois sensores. Nestes experimentos, nos quais estudou-se o efeito
da variação do ruído no sistema de calibração observa-se que os percentuais de retas que levaram a erros médios de alinhamento temporal menores ou iguais a 1,3 e 5
amostras são em geral menores que os percentuais de retas correspondentes mostrados na Figura 5.4 que representam os resultados obtidos com os experimentos nos
quais se estudou-se o efeito da variação do ruído no sistema de rastreamento. No entanto observa-se que este percentual foi reduzida consideravelmente. Mas quando se
compara estes resultados com os obtidos na Figura 5.8 vê-se que a diferença se situa
em aproximadamente 2 pixels, o que é exatamente o ruído acrescentado no sistema
de rastreamento. É importante observar que no experimento da Figura 5.4 o ruído no
sistema de calibração é da ordem de sub-pixel tornando o erro total igual ao erro apresentado no gráfico. Já para estes experimentos o erro líquido é o erro apresentado
pelo gráfico da Figura 5.8 mais o erro do sistema de rastreamento com desvio padrão
igual a 2 pixels.
5.1.2
Seqüências Reais
A seqüência de vídeo real utilizada para validar a aplicabilidade do método proposto refere-se a uma cena contendo um único sensor móvel, especificamente um
robô Pioneer 3 AT produzido pela Active Media, conforme ilustrado na Figura 5.9(a).
O monitoramento da cena foi realizado por uma câmera Sony DCR-SR62, tendo a
mesma sido calibrada previamente (STROBL et al., 2008). O comprimento da seqüência de vídeo corresponde a 750 quadros, tendo os mesmos resolução de 720 ×
480 pixels.
As trajetórias do robô no sistema de coordenadas do mundo e no plano de imagem
da câmera foram determinadas, respectivamente, por um sistema de localização visual
(GARCIA et al., 2007) e por um rastreador visual automático (JEPSON; FLEET; ELMARAGHI, 2003).
A partir das amostras de posição do sensor móvel no sistema de coordenadas do
mundo e usando-se os quadros da câmera responsável pelo monitoramento, determinou-
5.2 Sincronização de Câmeras que não Possuem Sobreposição de Campos de Visão
92
se visualmente a reta real que recupera o alinhamento temporal entre a câmera e o
sensor, sendo tal estimativa modelada pela seguinte equação: tc = 4 ∗ts1 −271, onde ts1
representa a coordenada temporal da amostra adquirida pelo sensor, e tc corresponde
ao número do quadro obtido pela câmera.
A Figura 5.9(b) ilustra a reta estimada pelo método proposto, a qual recupera o
alinhamento temporal entre a câmera e o sensor: tc = 3, 9948 ∗ ts1 − 269, 2136. Os parâmetros usados pelo algoritmo RANSAC são os mesmos ilustrados na Tabela 5.1. A
reta exibida leva a um erro médio de sincronização de aproximadamente 7,5ms, para
uma seqüência de vídeo de 1,5s, sendo este resultado bastante razoável para muitas
aplicações em redes de sensores móveis.
Nesta seção será mostrado os resultados adicionais para sincronização de N
seqüências de vídeo não sincronizadas adquiridas por diferentes câmeras que não
possuem sobreposição de campos de visão. Esta metodologia de sincronização de
câmeras é útil na sincronização de sensores que estão em uma rede multihop onde
hops diferentes são visualizados por câmeras diferentes.
Infelizmente, embora a sincronização temporal do conjunto de câmeras possa ser
realizado via hardware, por exemplo, por meio do envio de sinais de sincronização (KITAHARA et al., 2001), esta abordagem possui um alto custo e precisa ser feita anteriormente ao processo de aquisição das sequências de vídeo. Alternativamente, métodos
de sincronização via software vêm sendo utilizados com sucesso, sendo os mesmos
baseados em pistas visuais presentes na cena. Esta estratégia é utilizada pela técnica
apresentada neste trabalho. Qualquer método de sincronização de câmeras deve ter
a capacidade de tratar os seguintes casos:
• Taxas de quadros das câmeras desconhecidas;
• Deslocamento temporal arbitrário entre as seqüências de vídeo;
• Movimento e velocidade dos objetos arbitrários;
• Existência de falhas no rastreamento de objetos, o que significa que o objeto não
poderá ser rastreado por um grande número de quadros;
93
• Redução da eficiência computacional diante do aumento do número de seqüências de vídeo;
• Setup do conjunto de câmeras é desconhecido.
Estas necessidades foram tratadas por nós durante o desenvolvimento da nossa
metodologia, que tratou todos os casos acima exceto o último. Especialmente, assumimos que o setup do conjunto de câmeras é composto por câmeras estacionárias,
cujos parâmetros intrínsecos e extrínsecos são conhecidos a-priori.
Considere o cenário ilustrado na Figura 5.10. Dado N seqüências de vídeo sem sobreposição de campo de visão, a reta que recupera o alinhamento entre as seqüências
pertence ao conjunto de números reais com N + 1 dimensões (ℜN+1 ), que descreve
completamente todas as relações temporais entre as seqüências e o movimento do
sensor na cena.
Para demonstrar a aplicabilidade do nosso algoritmo são apresentados resultados experimentais com seqüências reais, onde tem-se como objetivo sincronizar N
seqüências de vídeo adquiridas por câmeras que não possuem sobreposição de campos de visão. Especificamente, nossa metodologia foi testada em uma cena composta
por duas câmeras de vídeo e um sensor móvel (robô Pioneer 3 AT da Active Media).
As dimensões de ambas as imagens dos dois conjuntos de dados são 720 x 480 pixels. Os dados foram obtidos por duas câmeras Sony DCR-SR62 sem sobreposição
de campo de visão. As câmeras capturam os quadros com taxas idênticas e iguais a
30fps, implicando uma unidade de dilatação temporal (α = 1). A referência verdadeira
do deslocamento temporal entre as seqüências de vídeo era β = 292 ± 0.5 quadros.
Os valores dos parâmetros principais usados em nosso alinhamento temporal estão
listados na Tabela 5.1.
Os dados de localização 3D dos sensores foram estimados a uma taxa de 7.5
amostras por segundo usando a localização visual proposto por Garcia el al. (2007).
Os quadros na seqüência de vídeo contendo um único objeto rígido (sensor) movendo
sobre um fundo estático, ao longo uma trajetória suave como ilustrado na Figura
5.12(a)-(b). Para a tarefa de rastreamento foi utilizado o rastreador WSL (JEPSON;
FLEET; EL-MARAGHI, 2003) para rastrear o sensor (trajetória azul na Figura 5.12(a)(b). O rastreador WSL foi inicializado manualmente no primeiro quadro de cada seqüência.
As câmeras foram calibradas de acordo com o algoritmo implementado por Strobl
94
et al.(??). Na Figura 5.12(a)-(b) mostramos a projeção 3D das localizações no plano
de imagens de ambas as câmeras (trajetórias vermelhas). Observe que estas projeções definem trajetórias muito ruidosas nos planos de imagem.
Foi usado o erro de alinhamento temporal médio como nossa unidade básica de
medida para avaliar a exatidão do nosso método. Especificamente, seu valor é dado
pela média dos valores absolutos das diferenças entre as coordenadas temporais determinadas pela reta estimada e as coordenadas temporais determinadas pela reta de
referência que modela o deslocamento temporal real entre as câmeras:
g
tc2
= tc1 + 292
(5.3)
onde tc1 representa a coordenada temporal da seqüência obtida pela câmera c1 e
g
tc2
representa sua coordenada temporal correspondente na seqüência obtida pela
câmera c2 , determinada pelo modelo real.
e representa a coordenada temporal correspondente a t ,
Por esta razão, se tc2
c1
determinada usando-se a reta estimada pelo nosso método, o erro de alinhamento
temporal médio εt é dado por:
1 M−1 e
g
|tc2(tc1 ) − tc2 (tc1)|
εt =
∑
M tc1 =0
(5.4)
onde M é o número de quadros na seqüência de vídeo obtido pela câmera c1 (neste
caso, M = 756).
Na Figura 5.11(a)-(b), são mostrados os espaços de votos para o sensor s se
movendo e duas câmeras c1 e c2 usados em nossos experimentos. As equações
de retas recuperadas; tc1 = 3.9979ts − 269.8932 e tc2 = 4.0028ts + 21.6761 descreve o
alinhamento temporal entre o sensor e as câmeras c1 e c2 , respectivamente. A partir
e = 1.0011t + 291.8797 que recupera o
destas equações obtém-se a nova equação tc2
c1
alinhamento temporal entre duas sequências de vídeo. De acordo com a Equação 5.4,
a reta reconstruída produz um erro de alinhamento temporal médio de 0.9764 quadros
ou 32.5 milisegundos.
Por esta razão, nossos resultados mostram que o método pode ser bem sucedido para sincronizar as seqüências de vídeos que possuem grandes desalinhamentos
temporais (292 quadros neste exemplo). Este cenário pode ser crítico para muitas das
metodologias de alinhamento temporal existentes. As Figuras 5.12(c)-(d) confirmam
95
que o alinhamento temporal estimado entre as seqüências de vídeo foi efetivamente
recuperado. Na Figura 5.12(c), A imagem exibida (antes do alinhamento temporal) foi
criada pela sobreposição da banda verde de um quadro tc2 com as bandas vermelhas e azul do quadro tc1 = (tc2 − β g )/α g , usando-se os parâmetros α g e β g da reta
de referência que modela o desalinhamento temporal entre as câmeras. Observe o
desalinhamento temporal entre as seqüências de vídeo. Na Figura 5.12(d), a imagem (depois do alinhamento temporal) foi criada pela substituição da banda verde
do quadro tc2 pela banda verde do quadro tc1 = (tc2 − β e )/α e , onde α e ,β e são parâmetros estimados pelo nosso método. Note que as seqüências foram perfeitamente
sincronizadas desaparecendo o efeito da presença de dois robôs sensores.
300
300
250
Ts1 = 3.0000 * t + 41.1315 →
Número da amostra (S1)
250
200
150
100
50
0
0
Ts1 = 3.0000 * t + 43.7102 →
200
150
100
50
10
20
30
40
50
60
70
0
0
80
10
20
Número da amostra (C)
(a)
250
Ts1 = 3.0000 * t + 44.8036 →
50
60
70
80
(b)
200
150
100
50
Ts1 = 3.0000 * t + 46.0866 →
200
150
100
50
10
20
30
40
50
60
0
0
70
10
20
30
40
50
60
70
(c)
(d)
300
300
250
250
Ts1 = 3.0000 * t + 45.5323 →
40
300
250
200
150
100
50
0
0
30
300
0
0
96
Ts1 = 3.0000 * t + 44.8497 →
200
150
100
50
10
20
30
40
(e)
50
60
70
0
0
10
20
30
40
50
60
70
(f)
Figura 5.1: Espaços de votos 2D obtido por meio da simulação para uma cena artificial
contendo um único sensor s1 . A trajetória do sensor rastreada na seqüência de vídeo
sintética na câmera foi corrompida com um ruído ruído gaussiano branco de média
zero e desvio padrão (a)-(c)-(e) 5 pixels e (b)-(d)-(f) 10 pixels. A matriz de calibração
utilizada em todos os experimentos corresponde à mesma de uma câmera real (modelo Sony DCR-TRV320), com erro em subpixels. Os parâmetros de desalinhamento
temporal simulados são α = 3.0 e β = 47 para todas as figuras. Em todos os casos, observamos nos gráficos as retas que recuperam o alinhamento temporal entre o sensor
e a câmera, e que levam a erros menores do que (a)-(b) 1 amostra, (c)-(d) 3 amostras
e (e)-(f) 5 amostras.
α = [1.2479 1.9494]
β = [36.1301 36.1743]
α = [1.0000 2.0290]
β = [46.0000 33.3827]
120
120
100
80
60
40
20
0
200
Nú
100
80
60
40
20
0
me
150
ro
da
100
am
os
tra
(S
2)
300
200
50
100
0
0
da
ero
Núm
tra
mos
(S1
)
a
Nú 200
me
150
ro
da
100
am
os
tra
(S
2)
300
200
50
100
0
(a)
100
80
60
40
20
100
80
60
40
20
0
300
150
ro
da
a
100
mo
str
a(
S2
S1)
200
50
m
100
0
)
a(
ostr
aa
ro d
e
Núm
0
Nú 200
me
150
ro
da
100
am
os
tra
(S
2)
300
50
m
100
0
0
Núm
aa
ro d
a(
ostr
e
(d)
α = [0.9860 1.9505]
β = [46.2207 35.5182]
120
120
100
80
60
40
20
0
200
100
80
60
40
20
0
me
150
ro
da
100
am
os
tra
(S
2)
S1)
200
(c)
α = [0.9752 2.0017]
β = [48.0320 33.8975]
a
120
0
200
Nú
Núm
)
(S1
α = [0.9880 1.9094]
β = [46.2637 36.5424]
120
me
0
da
ero
tra
mos
(b)
α = [1.1509 1.9916]
β = [41.1887 34.5399]
Nú
97
300
200
50
100
0
0
(e)
er
Núm
o da
1)
a (S
str
amo
Nú 200
me
150
ro
da
100
am
os
tra
(S
2)
300
200
50
100
0
0
Núm
er
o da
1)
a (S
str
amo
(f)
Figura 5.2: Espaços de votos 3D obtidos para cenas artificiais contendo dois sensores
móveis s1 e s2 . A trajetória do sensor rastreado na sequência de vídeo sintética foi
corrompida com um ruído ruído gaussiano branco de média zero e desvio padrão (a)(c)-(e) 5 pixels e (b)-(d)-(f) 10 pixels. A matriz de calibração utilizada em todos os experimentos corresponde à mesma de uma câmera real (modelo Sony DCR-TRV320),
com erro em subpixels. Os parâmetros de desalinhamento temporal simulados são
α = [1.0 2.0] e β = [46.0 34.0] para todas as figuras. Em todos os casos observamos nos gráficos as retas que recuperam o alinhamento temporal entre o sensor e a
câmera, e que levam a erros menores do que (a)-(b) 1 amostra, (c)-(d) 3 amostras e
(e)-(f) 5 amostras.
98
100
90
80
% de retas
70
60
50
40
30
20
10
0
0
2
4
6
8
Desvio padrão do ruído do rastreador
10
(a)
100
90
80
% de retas
70
60
50
40
30
20
10
0
0
2
4
6
8
10
(b)
100
90
80
% de retas
70
60
50
40
30
20
10
0
0
2
4
6
8
10
(c)
Figura 5.3: Percentuais de retas que levam a erros médios de alinhamento temporal
menores ou iguais a (a) 1, (b) 3 e (c) 5 amostras para níveis de ruído no sistema de
rastreamento de acordo com a Tabela 5.1.1, dada uma cena composta por apenas um
sensor s1 e uma matriz de calibração com o erro em subpixels.
99
100
90
80
% de retas
70
60
50
40
30
20
10
0
0
2
4
6
8
10
(a)
100
90
80
% de retas
70
60
50
40
30
20
10
0
0
2
4
6
8
10
(b)
100
90
80
% de retas
70
60
50
40
30
20
10
0
0
2
4
6
8
10
(c)
menores ou iguais a (a) 1, (b) 3 e (c) 5 amostras para níveis de ruído no sistema
de rastreamento de acordo com a Tabela 5.1 e uma matriz de calibração com erro em
subpixels. As curvas em azul e vermelho se referem, respectivamente, à sincronização
de um sensor s1 e à sincronização de um sensor s2 com a câmera de referência c,
considerando uma cena artificial composta por dois sensores.
300
300
250
Ts1 = 0.9803 * t + 34.6176 →
250
200
150
100
50
0
0
Ts1 = 0.9755 * t + 27.0763 →
200
150
100
50
50
100
150
200
0
0
250
50
(a)
Ts1 = 0.9887 * t + 29.9924 →
250
Ts1 = 0.9861 * t + 31.8095 →
250
200
(b)
200
150
100
50
200
150
100
50
50
100
150
200
0
0
250
50
100
(c)
200
250
(d)
250
Ts1 = 0.9847 * t + 32.2664 →
Ts1 = 0.9717 * t + 38.1412 →
200
250
150
300
150
300
250
200
150
100
150
100
50
50
0
0
100
300
0
0
100
50
100
150
(e)
200
250
0
0
50
100
150
200
250
(f)
Figura 5.5: Espaços de votos 2D obtidos por meio da simulação para uma cena artificial contendo um único sensor s1 . A trajetória do sensor rastreado na sequência de
vídeo sintética foi corrompida com um ruído ruído gaussiano branco de média zero e
desvio padrão 2. A matrizes de calibração utilizada em todos os experimentos corresponde à mesma de uma câmera real (modelo Sony DCR-TRV320), adicionado um
ruído gaussiano branco de média zero e desvio padrão (a)-(c)-(e) 5 pixels (b)-(d)-(f) 10
pixels. Os parâmetros de desalinhamento temporal simulados são α = 1.0 e β = 32.0
para todas as figuras. Em todos os casos observamos nos gráficos as retas que recuperam o alinhamento temporal entre o sensor e a câmera, e que levam a erros
menores do que (a)-(b) 1 amostra, (c)-(d) 3 amostras e (e)-(f) 5 amostras.
α = [3.1782 2.3000]
β = [42.9331 7.8504]
80
α = [2.9679 1.9246]
β = [44.3877 30.9180]
80
60
40
20
0
60
40
20
0
Nú 300
me
ro
da
a
300
200
200
mo
100
str
a(
S2
100
0
)
tra
mos
(S1
)
Nú 300
me
ro
da
150
os
tra
aa
ro d
e
Núm
0
200
200
am
100
100
0
)
α = [3.1546 1.9486]
β = [38.1042 31.3491]
60
40
20
α = [2.8068 2.0590]
β = [45.2056 27.8936]
80
60
40
20
0
0
200
200
150
am
os
tra
100
100
50
(S
2)
0
0
o da
er
Núm
a (S
str
amo
1)
Nú 300
me
ro
da
200
200
am
150
os
tra
100
100
50
(S
2)
0
(c)
0
a
ro d
úme
a (S
str
amo
1)
N
(d)
α = [2.9812 2.7552]
β = [43.6783 −14.7882]
60
40
20
0
α = [2.9943 1.8655]
β = [44.7514 30.5777]
80
80
Nú
(b)
80
Nú 300
me
ro
da
0
S1)
a(
ostr
m
a
o da
mer
50
(S
2
(a)
Nú 300
me
ro
da
101
60
40
20
0
200
am
os
tra
100
(S
2)
0
−50
(e)
0
100
50
Núm
er
o da
200
150
a (S
str
amo
1)
Nú 300
me
ro
da
200
200
150
am
os
tra
100
100
(S
2
50
)
0
0
o da
mer
(S
stra
amo
1)
Nú
(f)
Figura 5.6: Espaços de votos 3D obtidos por meio da simulação de uma cena contendo 2 sensores s1 e s2 . A trajetória do sensor rastreado na sequência de vídeo
sintética foi corrompida com um ruído ruído gaussiano branco de média zero e desvio
padrão 2 pixels. A matrizes de calibração utilizada em todos os experimentos corresponde à mesma de uma câmera real (modelo Sony DCR-TRV320), adicionado um
ruído gaussiano branco de média zero e desvio padrão (a)-(c)-(e) 5 pixels (b)-(d)-(f)
10 pixels. Os parâmetros de desalinhamento temporal simulados são α = [3.0 2.0] e
β = [45.0 30.0] para todas as figuras. Em todos os casos observamos nos gráficos as
retas que recuperam o alinhamento temporal entre o sensor e a câmera, e que levam
a erros menores do que (a)-(b) 1 amostra, (c)-(d) 3 amostras e (e)-(f) 5 amostras.
102
100
90
80
% de retas
70
60
50
40
30
20
10
0
0
2
4
6
8
Desvio padrão do ruído da matriz de calibração
10
(a)
100
90
80
% de retas
70
60
50
40
30
20
10
0
0
2
4
6
8
10
(b)
100
90
80
% de retas
70
60
50
40
30
20
10
0
0
2
4
6
8
10
(c)
calibração de acordo com a Tabela 5.1 e um ruído no sistema de rastreamento com
desvio padrão igual a 2 pixels, dada uma cena composta por apenas um sensor s1 .
103
100
90
80
% de retas
70
60
50
40
30
20
10
0
0
2
4
6
8
10
(a)
100
90
80
% de retas
70
60
50
40
30
20
10
0
0
2
4
6
8
10
(b)
100
90
80
% de retas
70
60
50
40
30
20
10
0
0
2
4
6
8
10
(c)
calibração de acordo com a Tabela 5.1.1 e o ruído no sistema de rastreamento com
desvio padrão igual a 2 pixels. As curvas em azul e vermelho se referem, respectivamente, à sincronização de um sensor s1 e à sincronização de um sensor s2 com a
câmera de referência c, considerando uma cena artificial composta por dois sensores.
(a)
104
(b)
Figura 5.9: (a) Cena real monitorada pelo sistema de sincronização. Neste caso,
tem-se um único sensor móvel (robô Pioneer 3 AT produzido pela Active Media), cuja
trajetória rastreada no vídeo é ilustrada pela curva em vermelho. (b) Espaço de votos
e reta que recupera o alinhamento temporal entre o sensor móvel s1 e a câmera c.
Figura 5.10: Uma cena 3D que é visualizada por N câmeras estacionárias localizadas
em diferentes pontos, cujos os campos de visão não são necessariamente sobrepostos. Temos ainda um sensor movendo-se através do campo de visão de todas as
câmeras.
(a)
105
(b)
Figura 5.11: (a) Espaço de votos para a câmera c1 e o movimento do sensor s. (b)
Espaço de votos para a câmera c2 e o movimento do sensor s. Cada ponto em (a)
e (b) representam alinhamentos temporais candidatos. As retas reconstruídas tc2 =
3.9979t2 − 269.8932 e tc2 = 4.0028t2 + 21.6761 descrevem o alinhamento temporal entre
o sensor e as câmeras c1 e c2 respectivamente. Para estas equações a nova equação
obtida tc2 = 1.011tc1 + 291.8797 que recupera o alinhamento temporal entre as duas
seqüências de vídeo.
50
50
100
100
150
150
200
200
250
250
300
300
350
350
400
400
450
106
450
100
200
300
400
500
600
700
100
200
300
400
500
600
700
(a) Trajetória do sensor na câmera 1
(b) Trajetória do sensor na câmera 2
(b) Antes do alinhamento temporal
(c) Depois do alinhamento temporal
Figura 5.12: (a) e (b) Trajetórias dos centróides dos sensores nas câmeras 1 e 2, respectivamente. A trajetória azul foi estimada pelo rastreador WSL (JEPSON; FLEET;
EL-MARAGHI, 2003), enquanto a vermelha foi obtida da projeção da trajetória 3D do
sensor no plano de imagem, usando as matrizes de projeção determinadas durante
o processo de calibração das câmeras. (c) Imagem anterior ao alinhamento foi criado por superposição da banda verde de um quadro t2 com a vermelha e azul do
quadro t1 = (t2 − β g )/α g usando os coeficientes de alinhamento α g e β g . (d) Após
o alinhamento foi criado trocando a banda verde da imagem com aquela do quadro
t1 = (t2 − β e )/α e , com α e , β e determinada por nosso algoritmo. Desvios do alinhamento
causam "duas imagem” artificiais
107
6
CONCLUSÃO
Este trabalho de dissertação de mestrado mostrou um nova abordagem sobre o
problema de se fazer a sincronização temporal em uma rede de sensores móveis com
ou sem fio. Esta nova metodologia de sincronização aqui desenvolvida deverá ser
capaz de contribuir para o desenvolvimento de redes que possuam uma infra-estrutura
mais eficaz, eficiente e robusta às instabilidades do meio ambiente.
Mais especificamente nossa metodologia de alinhamento apresenta várias características diferentes das metodologias existentes. Uma importante característica é o
fato de não haver tráfego de dados, para sincronização, pela rede. Esta característica
implica em dois ganhos principais, um está relacionado com a economia no consumo
de energia. Já que como visto anteriormente grande percentagem deste consumo se
deve a comunicação de dados. Outra grande melhoria ainda relacionada a diminuição
do tráfego de dados é a diminuição da quantidade de colisões de dados na rede, o
que aumenta a velocidade de transferência de dados.
Através da metodologia proposta neste trabalho de dissertação de mestrado é possível atingir uma alta exatidão da sincronização apenas alterando a taxa de amostragem
da câmera e dos sensores. Nosso método de sincronização é independente das taxas
de amostragem, a única restrição é que esta seja constante. Devido a diversos fatores,
como exemplo a possibilidade de defeito em alguns dos sensores, RSSF tem um comportamento altamente não determinístico. Nossa metodologia independe da topologia
da rede e não tem nenhuma relação específica com os nós da rede. Então caso este
nó saia do campo de visão da câmera ou apresente defeito, isto não afetará em nada
a sincronização dos outros nós da rede.
Redes de sensores sem fio normalmente tem a função de cobrir grandes áreas,
como nos exemplos de plantações de soja ou monitoramento de habitat. Nestas
condições é possível haver um conjunto de sensores comunicam entre si mas não conseguem se comunicar com outros conjuntos que estão distantes. Neste caso ocorre a
6.1 Trabalhos futuros
108
formação de hops. Uma rede que tem esta característica é chamada multihop. Como
podemos observar esta é uma característica extremamente importante em redes de
sensores sem fio. Nossa metodologia é capaz de sincronizar sensores que estão em
hops diferentes. Utilizando varias câmeras com diferentes campos de visão, que não
necessitam estarem sobrepostos, como visto na Seção 5.2, é possível sincronizar as
câmeras entre si e consequentemente os nós sensores. cada um destes campos de
visão pode ser definido como sendo um hop. Para cobrir estas áreas muito grandes
é preciso também uma grande quantidade de sensores. Temos então que qualquer
metodologia de sincronização suficientemente genérica deve ser escalável quanto a
quantidade de sensores. Podemos concluir que nosso método é escalável pois a
precisão da sincronização independe da quantidade de sensores na rede. Podemos
observar através dos dados de percentagem de retas de alinhamento temporal recuperadas, que nosso método independe também das taxas de amostragem dos sensores
e da câmera.
Concluímos então que a metodologia de solução proposta neste trabalho de dissertação de mestrado mostra-se bastante promissora, pois nela são tratados os pontos que levam a uma solução genérica para o problema de sincronização temporal.
6.1 Trabalhos futuros
Como proposta de trabalho futuros identificamos a necessidade de realizar experimentos com cenas reais onde tenhamos um cenário mais desafiado e um número
maior de sensores. Esperamos com estes experimentos poder confirmar a escalabilidade do método proposto. Temos também um outro grande desafio que é realizar
experimentos reais de cenas contendo sensores se movimentando em trajetórias tridimensionais.
109
ARVIND, K. Probabilistic clock synchronization in distributed systems. IEEE Trans.
Parallel Distrib. Syst., IEEE Press, Piscataway, NJ, USA, v. 5, n. 5, p. 474–487, 1994.
ISSN 1045-9219.
BROOKS, T. T. et al. A review of synchronization methods in wireless sensor networks.
1st International Conference on Sensing Technology, p. 338–343, Novembro 2005.
CAMILLI, A. et al. From wireless sensors to field mapping: Anatomy of an application
for precision agriculture. Computers and Electronics in Agricuture., Elsevier Science
Publishers B. V., Amsterdam, The Netherlands, The Netherlands, v. 58, n. 1, p. 25–36,
2007. ISSN 0168-1699.
CANTZLER, H. Random sample consensus. In: . [S.l.: s.n.], 2004.
CHEE-YEE; KUMAR, C. Sensor Networks: Evolution, Opportunities, and Challenges.
Procedures of the IEEE, v. 91, n. 8, p. 1247–1256, 2003.
CHUM, O.; MATAS, J. Randomized ransac with td,d test. In: In Proceedings of the
13th British Machine Vision Conference (BMVC. [S.l.: s.n.], 2002. p. 448–457.
CRISTIAN, F. Probabilistic clock synchronization. Distributed Computing, v. 3, n. 3, p.
146–158, Setembro 2005.
ELSON, J.; ESTRIN, D. Time synchronization for wireless sensor networks. In: . [S.l.:
s.n.], 2001. p. 186–186.
ELSON, J.; GIROD, L.; ESTRIN, D. Fine-Grained Network Time Synchronization using
Reference Broadcasts. 2002.
ELSON, J. E. Time Synchronization in Wireless Sensor Networks. Tese (Doutorado)
— University of California, 2003.
ESTRIN, D. Reflections on Wireless Sensing Systems: From Ecosystems to Human
Systems. [S.l.], 01 2007.
FARNHAM, D. E. Site-specific crop management: what have we learned and where
do we go from here? 10 2000. Ames: Iowa State University-Department of Agronomy.
FISCHLER, M. A.; BOLLES, R. C. Random sample consensus: a paradigm for
model fitting with applications to image analysis and automated cartography. Morgan
Kaufmann Publishers Inc., San Francisco, CA, USA, p. 726–740, 1987.
110
GANERIWAL, S. et al. Rate-adaptive time synchronization for long-lived sensor
networks. In: SIGMETRICS ’05: Proceedings of the 2005 ACM SIGMETRICS
international conference on Measurement and modeling of computer systems. New
York, NY, USA: ACM, 2005. p. 374–375. ISBN 1-59593-022-1.
GANERIWAL, S.; KUMAR, R.; SRIVASTAVA, M. B. Timing-sync protocol for sensor
networks. In: . [S.l.]: ACM Press, 2003. p. 138–149.
GARCIA, R. F. et al. Um Arcabouço para a Localização de Enxames de Robôs. In:
Proc. of VIII SBAI. [S.l.: s.n.], 2007.
GLOBAL Clock Synchronization in Sensor Networks. IEEE Trans. Comput., IEEE
Computer Society, Washington, DC, USA, v. 55, n. 2, p. 214–226, 2006. ISSN
0018-9340. Member-Qun Li and Member-Daniela Rus.
GONZALES, R. C.; WOODS, R. E. Digital Image Processing. Third edition. [S.l.]:
Pearson Prentice Hall, 2007.
HEIKKILA, J. Geometric camera calibration using circular control points. IEEE
Transactions on Pattern Analysis and Machine Intelligence, v. 22, n. 10, p. 1066–1077,
2000.
ISARD, M.; MACCORMICK, J. Bramble: a bayesian multiple-blob tracker. In: Computer
Vision, 2001. ICCV 2001. Proceedings. Eighth IEEE International Conference on. [S.l.:
s.n.], 2001. v. 2, p. 34–41.
JEPSON, A.; FLEET, D.; EL-MARAGHI, T. Robust on-line appearance models for
visual tracking. v. 25, n. 10, p. 1296–1311, June 26 2003.
KITAHARA, I. et al. Large-scale virtualized reality. In: Conference on Computer Vision
and Pattern Recognition - Technical Sketches. [S.l.: s.n.], 2001.
KOTTAPALLI, V. A. et al. Two-tiered wireless sensor network architecture for structural
health monitoring. In: SPIE 10th Annual International Symposium on Smart Structures
and Materials. [S.l.: s.n.], 2003.
LAMPORT, L. Time, clocks, and the ordering of events in a distributed system.
Commun. ACM, ACM, New York, NY, USA, v. 21, n. 7, p. 558–565, 1978. ISSN
0001-0782.
LEE, H.; YU, W.; KWON, Y. Efficient rbs in sensor networks. In: ITNG ’06:
Proceedings of the Third International Conference on Information Technology: New
Generations. Washington, DC, USA: IEEE Computer Society, 2006. p. 279–284. ISBN
0-7695-2497-4.
MARóTI, M. et al. The flooding time synchronization protocol. In: SenSys ’04:
Proceedings of the 2nd international conference on Embedded networked sensor
systems. New York, NY, USA: ACM, 2004. p. 39–49. ISBN 1-58113-879-2.
MILLS, D. L. Internet time synchronization: The network time protocol. RFC Editor,
United States, 1989.
111
MILLS, D. L. Precision synchronization of computer network clocks. SIGCOMM
Comput. Commun. Rev., ACM, New York, NY, USA, v. 24, n. 2, p. 28–43, 1994. ISSN
0146-4833.
MYATT, D. et al. Napsac: High noise, high dimensional model parameterisation - it’s in
the bag. In: British Machine Vision Conference. [S.l.: s.n.], 2002. p. 458–467.
PAEK, J. et al. A wireless sensor network for structural health monitoring: Performance
and experience. IEEE, p. 1–4, 02 2006.
PALCHAUDHURI, S.; SAHA, A. K.; JOHNSON, D. B. Adaptive clock synchronization
in sensor networks. In: of International Symposium on Information Processing in
Sensor Networks. [S.l.: s.n.], 2004. p. 340–348. ISBN 1-59593-022-1.
PáDUA, F. et al. Linear sequence-to-sequence alignment. In: IEEE International
Conference on Computer Vision. [S.l.: s.n.], 2004. v. 1, p. 746–756.
PáDUA, F. C. de. Spatio-Temporal Alignment of Video Sequences Captured from
Multiple Viewpoints. Tese (Phd thesis) — Universidade Federal de Minas Gerais, Belo
Horizonte, Minas Gerais, Brasil, December 2005.
PERKINS, M.; CORREAL, N.; O’DEA, B. Emergent wireless sensor network
limitations: a plea for advancement in core technologies. In: Proceedings of IEEE
Sensors. [S.l.: s.n.], 2002.
PIRES, J. L. F. et al. Discutindo agricultura de precisão - aspectos gerais. 03 2004.
EMBRAPA TRIGO.
POLASTRE, J. R. Design and Implementation of Wireless Sensor Networks for
Habitat Monitoring. Dissertação — University of California at Berkeley, Berkley,CA, 05
2003.
POTTIE, G. J.; KAISER, W. J. Wireless integrated network sensors. Commun. ACM,
ACM, New York, NY, USA, v. 43, n. 5, p. 51–58, 2000. ISSN 0001-0782.
RöMER, K. Time synchronization in ad hoc networks. In: MobiHoc ’01: Proceedings
of the 2nd ACM international symposium on Mobile ad hoc networking & computing.
New York, NY, USA: ACM, 2001. p. 173–182. ISBN 1-58113-428-2.
SHI, J.; TOMASI, C. Good features to track. In: IEEE Conference on Computer Vision
and Pattern Recognition. [S.l.: s.n.], 1994.
SICHITIU, M.; VEERARITTIPHAN, C. Simple, Accurate Time Synchronization for
Wireless Sensor Networks. 2003.
STROBL, K. et al. Camera Calibration Toolbox for Matlab. Institute of Robotics and
Mechatronics, German Aerospace Center (DLR): [s.n.], 2008.
SU, W.; AKYILDIZ, I. F. Time-diffusion synchronization protocol for wireless sensor
networks. IEEE/ACM Trans. Netw., IEEE Press, Piscataway, NJ, USA, v. 13, n. 2, p.
384–397, 2005. ISSN 1063-6692.
112
TILAK, S.; ABU-GHAZALEH, N.; HEINZELMAN, W. A Taxonomy of Wireless
Microsensor Network Models. 2002.
TRUCCO, E.; VERRI, A. Introductory Techniques for 3-D Computer Vision. Upper
Saddle River, NJ, USA: Prentice Hall PTR, 1998. ISBN 0132611082.
VEENMAN, C. J.; REINDERS, M. J. T.; BACKER, E. Resolving motion correspondence
for densely moving points. IEEE Trans. Pattern Anal. Mach. Intell., IEEE Computer
Society, Washington, DC, USA, v. 23, n. 1, p. 54–72, 2001. ISSN 0162-8828.
WANG, N.; ZHANG, N.; WANG, M. Wireless sensors in agriculture and food
industry–recent development and future perspective. Computers and Electronics in
Agriculture, v. 50, n. 1, p. 1–14, January 2006.
XU, N. et al. A wireless sensor network for structural monitoring. In: ACM Conference
on Embedded Networked Sensor Systems. Baltimore,MD: ACM Portal, 2004.
YILMAZ, A.; JAVED, O.; SHAH, M. Object tracking: A survey. ACM Comput. Surv.,
ACM Press, New York, NY, USA, v. 38, n. 4, 2006. ISSN 0360-0300.

Sincronização Temporal em Redes de Sensores Móveis Baseada

Transcrição

Documentos relacionados

talvez sim, pelo menos nas digitais

Audioguias - Centro Português de Fotografia

Sensores Aerotransportados

Tecnologiaem

Sin título-1

Renault Master Fourgon 2.3 dCi L2H2 3.5T Confort

Volante 6 SK - MTE

FireWatch

ip 449-09 i9access

6. Sensores e percepção Para que a plataforma - LAR