UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE
U NIVERSIDADE F EDERAL DO R IO G RANDE DO N ORTE
C ENTRO DE T ECNOLOGIA
P ROGRAMA DE P ÓS -G RADUAÇÃO EM E NGENHARIA E LÉTRICA
DE C OMPUTAÇÃO
E
Mapeamento Robótico 2,5-D com
Representação em Grade de
Ocupação-Elevação
Anderson Abner de Santana Souza
Orientador: Prof. Dr. Luiz Marcos Garcia Gonçalves
Tese de Doutorado apresentada ao Programa de Pós-Graduação em Engenharia
Elétrica e de Computação da UFRN (área de
concentração: Engenharia de Computação)
como parte dos requisitos para obtenção do
título de Doutor em Ciências.
Número de ordem PPgEE: D74
Natal, RN, Agosto de 2012
UFRN / Biblioteca Central Zila Mamede
Catalogação da Publicação na Fonte.
Souza, Anderson Abner de Santana
Mapeamento robótico 2,5-D com representação em grade de ocupaçãoelevação/ Anderson Abner de Satana Souza - Natal, RN, 2012
109 f.:il
Orientador: Luiz Marcos Garcia Gonçalves
Tese (Doutorado) - Universidade Federal do Rio Grande do Norte. Centro
de Tecnologia. Programa de Pós-Graduação em Engenharia Elétrica e de Computação.
1. Inteligência artificial - Mapeamento - Tese. 2. Grade de ocupação-elevação
- Computação - Tese. 3. Visão estéreo - Computação - Tese. 4. Modelagem
probabilística - Computação - Tese. 5. Robótica - Tese. I. Gonçalves, Luiz
Marcos Garcia. II. Universidade Federal do Rio Grande do Norte. III. Título.
RN/UF/BCZM
CDU 004.896
Mapeamento Robótico 2,5-D com
Representação em Grade de
Ocupação-Elevação
Anderson Abner de Santana Souza
Tese de Doutorado aprovada em 03 de agosto de 2012 pela banca examinadora composta
pelos seguintes membros:
Prof. Dr. Luiz Marcos Garcia Gonçalves (orientador) . . . . . . . . . . . . . . . . . UFRN
Prof. Dr. Pablo Javier Alsina . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . UFRN
Prof. Dr. Diogo Fernandes Pedrosa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . UFRN
Prof. Dr. Flávio Tonidandel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . FEI
Prof. Dr. André Macedo Santana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . UFPI
“Eu te exaltarei, meu Deus e meu
rei; bendirei o teu nome para todo
sempre! Todos os dias te bendirei e
louvarei o teu nome para todo
sempre! Grande é o Senhor e digno
de ser louvado; sua grandeza não
tem limites.” Sl. 145.1-3
Agradecimentos
Ao Senhor criador de todas as coisa por ser o meu constante ajudador e sustentador.
“Todas as coisas foram feitas por ele, e sem ele nada do que foi feito se fez”. Toda honra
e glória ao Deus supremo.
Agradeço aos meus pais Marlene e Abdênego pelo grande incentivo, apoio e orações, que
foram e são de fundamental importância para alcançar os objetivos da minha vida. Por
me ensinar o verdadeiro caminho a ser trilhado na busca de uma vida justa e íntegra.
Não posso deixar de agradecer a minha preciosa e amável esposa Verónica, por sempre
me inspirar e incentivar, mesmo quando isso significava renunciar momentos juntos. Sou
grato pelas sua orações e súplicas diante do nosso Deus, pedindo-lhe forças para tornarme um vencedor.
Aos meus irmãos Afrânio e Andressa, pessoas importantíssimas na minha vida.
Ao meu orientador, professor Dr. Luiz Marcos Garcia Gonçalves, sou grato pelas orientações, conselhos e ensinamentos. Pelo apoio e incentivo para que essa valiosa conquista
na minha formação fosse alcaçada.
Sou grato ao meu grande amigo e companehiro de trabalho André Macedo, à companheira de doutorado Rosiery pelos conselhos e incentivo, e aos demais companheiros do
laboratório NatalNet.
Deixo o meu muito obrigado a todos que direta ou indiretamente participaram dessa conquista. Que Deus os recompense grandemente.
Resumo
Este trabalho apresenta um novo método de mapeamento de ambientes com robôs
móveis com informações tridimensionais para navegação. Muitas abordagens de mapeamento 3D, usam o método em grade de ocupação, o que resulta no uso de muito recurso
computacional tanto na construção como no armazenamento desses mapas. A presente
pesquisa apresenta o mapeamento 2,5-D em grade de ocupação-elevação, a qual é definida
como uma representação discreta, onde cada célula armazena uma probabilidade de ocupação, a altura do espaço mapeado e a variância desse valor de altura.
Essa representação permite que um robô móvel tenha a ciência se um lugar do seu
ambiente está ocupado por um obstáculo e qual a altura desse obstáculo. Dessa forma,
ele pode decidir se é possível navegar sobre o obstáculo ou não, de acordo com suas
habilidades motoras. As informações sensoriais necessárias para construir o mapa são
providas por um sistema de visão estéreo, o qual foi modelado através de uma robusta
análise estatística, considerando os ruídos presentes no processamento estéreo. Os mapas
resultantes favorecem a execução de tarefas como tomadas de decisões na navegação
autônoma, exploração, localização e planejamento de caminhos. Experimentos práticos
reais mostram que o método de mapeamento apresentado é útil para a navegação de robôs
autônomos.
Palavras-chave: Grade de Ocupação-Elevação. Visão Estéreo, Modelagem Probabilística.
Abstract
This work introduces a new method for environment mapping with three-dimensional
information from visual information for robotic accurate navigation. Many approaches
of 3D mapping using occupancy grid typically requires high computacional effort to both
build and store the map. We introduce an 2.5-D occupancy-elevation grid mapping, which
is a discrete mapping approach, where each cell stores the occupancy probability, the
height of the terrain at current place in the environment and the variance of this height.
This 2.5-dimensional representation allows that a mobile robot to know whether a
place in the environment is occupied by an obstacle and the height of this obstacle, thus,
it can decide if is possible to traverse the obstacle. Sensorial informations necessary to
construct the map is provided by a stereo vision system, which has been modeled with
a robust probabilistic approach, considering the noise present in the stereo processing.
The resulting maps favors the execution of tasks like decision making in the autonomous
navigation, exploration, localization and path planning. Experiments carried out with a
real mobile robots demonstrates that this proposed approach yields useful maps for robot
autonomous navigation.
Keywords: 2.5-D Occupancy-Elevation Grid, Stereo Vision, Probabilistic Modeling.
Sumário
Sumário
i
Lista de Figuras
iii
Lista de Tabelas
v
1 Introdução
1.1 Contribuições . . . . . .
1.2 Motivação e Justificativa
1.3 Organização do trabalho
1.4 Produções Científicas . .
1
4
6
7
8
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2 Mapeamento
2.1 O Problema do Mapeamento Robótico . . . . . . . . . . . . . . . . . . .
2.2 Desafios do problema de mapeamento robótico . . . . . . . . . . . . . .
2.2.1 Imprecisões sensoriais . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 Dimensionalidade . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.3 Associação de dados - Matching . . . . . . . . . . . . . . . . . .
2.2.4 Dinamicidade do ambiente . . . . . . . . . . . . . . . . . . . . .
2.2.5 Estratégia de exploração . . . . . . . . . . . . . . . . . . . . . .
2.3 Tipos de Representações . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1 Mapas Topológicos . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.2 Mapas Métricos . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.3 Mapas topológicos vs. Mapas métricos - Vantagens e Desvantagens
2.3.4 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . .
11
11
12
12
13
14
14
15
15
16
17
19
20
3 Mapeamento Visual
3.1 Contextualização . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Configurações de Câmeras mais Utilizadas no Mapeamento Visual
3.2.1 Visão Monocular . . . . . . . . . . . . . . . . . . . . . .
3.2.2 Visão Estéreo . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Estereoscopia . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Geometria Estéreo e Reconstrução 3D . . . . . . . . . . .
3.3.2 Disparidade Estéreo . . . . . . . . . . . . . . . . . . . .
3.4 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . .
23
23
24
24
25
26
26
28
30
i
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4
5
6
7
Grade de Ocupação e Mapas de Elevação
4.1 Grade de Ocupação . . . . . . . . . . . . . . . . . . . . .
4.1.1 Modelo Probabilístico do Sensor . . . . . . . . . .
4.1.2 Algoritmo de Mapeamento em Grade de Ocupação
4.1.3 Trabalhos Relacionados . . . . . . . . . . . . . .
4.2 Mapas de Elevação . . . . . . . . . . . . . . . . . . . . .
4.2.1 Filtro de Kalman . . . . . . . . . . . . . . . . . .
4.2.2 Trabalhos Relacionados . . . . . . . . . . . . . .
4.3 Considerações . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
33
33
35
37
38
41
42
45
46
Grade de Ocupação-Elevação
5.1 Contextualização . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Definição - Grade de Ocupação-Elevação . . . . . . . . . . . .
5.2.1 Etapas do Mapeamento em Grade de Ocupação-Elevação
5.3 Posicionamento - Modelagem Cinemática . . . . . . . . . . . .
5.4 Aquisição e Interpretação de Dados Sensoriais . . . . . . . . . .
5.4.1 Aquisição de Imagens . . . . . . . . . . . . . . . . . .
5.4.2 Calibração Estéreo . . . . . . . . . . . . . . . . . . . .
5.4.3 Retificação . . . . . . . . . . . . . . . . . . . . . . . .
5.4.4 Correspondência Estéreo . . . . . . . . . . . . . . . . .
5.4.5 Cálculo das Coordenadas dos Pontos Detectados . . . .
5.5 Modelagem Sensorial . . . . . . . . . . . . . . . . . . . . . . .
5.5.1 Modelagem Sensorial para Estimar o Valor de Ocupação
5.5.2 Modelagem Sensorial para Estimar o Valor de Elevação
5.5.3 Modelagem das Incertezas e Ruídos Sensoriais . . . . .
5.6 Integração de Dados . . . . . . . . . . . . . . . . . . . . . . .
5.6.1 Integração dos Valores de Ocupação . . . . . . . . . . .
5.6.2 Integração dos Valores de Elevação . . . . . . . . . . .
5.6.3 Definição do Campo Visual de Células Atualizáveis . .
5.7 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
47
47
48
50
52
54
54
55
55
56
56
57
57
59
60
63
63
63
64
65
Experimentos e Resultados
6.1 Visão Geral do Sistema Robótico . . . . . . . . .
6.2 Calibração Estéreo . . . . . . . . . . . . . . . .
6.3 Estimativa das Incertezas Visuais . . . . . . . . .
6.4 Tratamento de Incoerências no Valor de Elevação
6.5 Experimento em Ambiente Interno . . . . . . . .
6.6 Experimento em Ambiente Externo . . . . . . .
6.7 Experimento em Ambiente Misto . . . . . . . . .
6.8 Comparações . . . . . . . . . . . . . . . . . . .
6.9 Análise Geral dos Resultados . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
67
67
68
69
70
72
75
76
81
81
Conclusão e Perspectivas
Referências bibliográficas
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
83
85
Lista de Figuras
1.1
1.2
Diagrama hierárquico do processo de navegação. . . . . . . . . . . . . .
Processo de contrução do mapa em grade de ocupação-elevação. . . . . .
2
5
2.1
2.2
2.3
2.4
Grafico de composição do mapeamento. . . . . . . . . . . . . . . . . . .
Mapa corrompido por erros de odometria. . . . . . . . . . . . . . . . . .
Mapa corrompido por erros de odometria. . . . . . . . . . . . . . . . . .
O problema da exploração é a integração do Mapeamento com o Planejamento de caminhos [Stachniss 2009]. . . . . . . . . . . . . . . . . . . .
Mapemento topológico. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Representação de uma medição de um sonar em uma grade de ocupação. .
Construção de um mapa de características a partir da detecção de retas. . .
12
13
14
2.5
2.6
2.7
3.1
3.2
3.3
3.4
3.5
4.1
4.2
4.3
4.4
4.5
5.1
5.2
5.3
5.4
5.5
5.6
15
17
18
19
Câmeras monoculares. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Câmeras estereoscópicas: (a) câmeras binocular e trinocular; (b) câmera
ominidirecional. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Geometria estéreo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Mapa de disparidade gerado pelo algoritmo de janela variável; (a) imagem
original; (b) mapa de disparidade. . . . . . . . . . . . . . . . . . . . . .
Mapa de disparidade gerado pelo algoritmo de graph-cuts; (a) imagem
original; (b) mapa de disparidade. . . . . . . . . . . . . . . . . . . . . .
25
Gráfico da Distribuição Normal. . . . . . . . . . . . . . . . . . . . . . .
Modelo de medição sensorial. Valores de ocupação para medições de
20m, 30m e 40m. O valor de ocupação se dá com as médias (medidas) e
variâncias (erros) das medições. . . . . . . . . . . . . . . . . . . . . . .
Modelagem Gaussiana bidimensional de um sensor. . . . . . . . . . . . .
Ilustração da representação em grade de ocupação 3D. . . . . . . . . . .
Representação em grade de ocupação 2.5D. É necessária uma estrutura
de dados de 72 elementos para mapear o ambiente ilustrado. . . . . . . .
36
43
Formação da grade de ocupação-elevação. . . . . . . . .
Etapas do mapeamento em grade de ocupação-elevação.
Modelagem cinemática de movimento. . . . . . . . . . .
Câmera estéreo Minoru 3D utilizada no mapeamento. . .
Processo de retificação estéreo. . . . . . . . . . . . . . .
Construção do mapa de disparidade. . . . . . . . . . . .
49
51
53
54
55
56
iii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
25
27
29
30
37
37
42
Modelo inverso do sensor aplicado ao cálculo de ocupação para l p = 10m
e l p = 15m. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.8 Referenciais de coordenadas envolvido no mapeamento. . . . . . . . . .
5.9 Comportamento do modelo sensorial para o cálculo de elevação de uma
célula, levando em consideração as incertezas, para uma madição ht = 2m,
com distâncias l p = 1m, l p = 2m e l p = 3m, σt = 0.032m, σt = 0.13m e
σt = 0.28m, respectivamente. . . . . . . . . . . . . . . . . . . . . . . . .
5.10 O efeito de escorço da superfície não paralela S é diferente para as duas
câmeras: a projeção de S nos planos de imagens tem comprimentos diferentes ll e lr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.11 Desalinhamento vertical dos planos de imagens. . . . . . . . . . . . . . .
5.7
6.1
6.2
Plataforma robótica utilizada nos experimentos. . . . . . . . . . . . . . .
Cena de uma possível passagem: (a) Mesa de computador; (b) Imagem
capturada pela câmera do robô; (c) Mapa de disparidade estimado. . . . .
6.3 Mapas estimados: (a) Valores de ocupação; (b) valores de elevação sem
heurística; (c) valores de elevação com heurística. . . . . . . . . . . . . .
6.4 Cenas visualizadas pelo robô durante o mapeamento: (a) Visão do corredor e armários presentes; (b) Portão gradeado; (c) Terminal de consultas. .
6.5 Vistas superiores do ambiente: (a) Visão superior do prédio explorado a
partir do Google Earth com latitude -5.842853 e longitude -35.197341;
(b)Planta baixa do corredor mapeado. . . . . . . . . . . . . . . . . . . .
6.6 Mapeamento em grade de ocupação-elevação para o ambiente interno.
(a)Valores de ocupação. (b) Valores de elevação; (c) Variância das elevações. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.7 Imagens capturadas pelo robô durante o mapeamento. . . . . . . . . . . .
6.8 Ambiente externo mapeado: (a) Visão superior do ambiente, limitado
pelo retângulo em amarelo (visão do Google Earth) de latitude -5.842677
e longitude -35.19724; (b) Planta baixa. . . . . . . . . . . . . . . . . . .
6.9 Mapeamento em grade de ocupação-elevação para o ambiente externo:
(a)Valores de ocupação. (b) Valores de elevação; (c) Variância das elevações. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.10 Vista superior do ambiente mapeado: (a) vista do Google Earth de latitude
-5.842677 e longitude -35.19724; (b) Planta baixa. . . . . . . . . . . . .
6.11 Diferentes cenas encontradas durante o mapeamento: (a) e (b) Cenas de
ambiente interno. (c) e (d) Cenas de ambiente externo. . . . . . . . . . .
6.12 Resultado do mapeamento do ambiente misto: (a) Valores de ocupação;
(b) Valores de elevação.(c) Variância das elevações. . . . . . . . . . . . .
58
59
60
61
62
68
70
71
72
73
74
76
77
78
79
79
80
Lista de Tabelas
6.1
Comparação de requisitos de memória. . . . . . . . . . . . . . . . . . . .
v
81
Capítulo 1
Introdução
A robótica vem se destacando como uma das áreas das ciências exatas de mais rápida evolução. Com o objetivo de conceber máquinas (os robôs) que auxiliem ou mesmo
substituam os homens em tarefas repetitivas, fastidiosas, de grande precisão e perigosas,
a robótica vem sendo explorada com grande empolgação por cientistas de todo mundo.
Thrun et al. (2005) definem, de uma maneira mais formal, a Robótica como sendo a
ciência de perceber e manipular o mundo físico através de dispositivos controlados computacionalmente.
Pode-se dividir a robótica em duas grandes categorias: a robótica de manipuladores e
a robótica móvel. O objetivo principal da robótica de manipuladores é desenvolver braços
robóticos, que emulam os movimentos dos braços humanos. Tais robôs são aplicados
principalmente nas indústrias, com destaque maior para as linhas de montagens automobilísticas. Porém, apesar do seu grande sucesso, os robôs manipuladores possuem uma
desvantagem fundamental: falta de mobilidade. Um manipulador tem uma região limitada de trabalho que depende de onde está fixado [Siegwart & Nourbakhsh 2004]. Por
outro lado, a robótica móvel trata com robôs que possuem a habilidade de se locomover,
isto é, robôs móveis que podem trafegar através de um ambiente, o que flexibiliza a atuação destes. A robótica móvel é constituída pela classe dos robôs terrestres, aéreos,
subaquáticos e robôs híbridos (capazes de se movimentar em diferentes espaços).
Aliando a capacidade de locomoção dos robôs móveis com recursos computacionais,
poder de comunicação de dados, capacidade de percepção (sensores), entre outros, é possível empregá-los em diversos tipos de aplicações práticas. Como ilustração, pode-se citar
aplicações domésticas (por exemplo, aspiradores de pó e cortadores de grama), industriais (por exemplo, transporte automatizado), urbanas (por exemplo, transportes públicos,
cadeiras de rodas robotizadas), militares (por exemplo, sistemas de monitoramento aéreo
remoto, transporte de suprimentos e de armazenamento em zonas de guerra, sistemas táticos de e combate), de segurança e defesa civil, e militar (por exemplo, patrulhamento
de ambientes, resgate e exploração em ambientes hostis, combate a incêndios) [Wolf
et al. 2009]. Assim, fica clara a importância de se investir em pesquisas para o desenvolvimento desta área tão promissora.
Um dos grandes desafios para a comunidade dos roboticistas é fazer com que os robôs
móveis executem suas tarefas de forma eficiente e segura com o mínimo de interferência
humana, isto é, que sejam autônomos. Para isso, o sistema robótico deve apresentar
CAPÍTULO 1. INTRODUÇÃO
2
características importantes. A primeira delas é a capacidade de percepção, onde através
de sensores, o robô deve perceber o ambiente no qual esta inserido. Como segunda característica o robô deve ser capaz de agir por meio de atuadores e motores, que o habilitam
a produzir ações tais como deslocamento. Por fim, um robô autônomo deve apresentar
robustez e inteligência para lidar com as mais diversas situações, de modo a resolver e
executar tarefas, por mais complexas que sejam [Wolf et al. 2009].
Analisando essas características fundamentais, pode-se entender que um robô móvel
autônomo deve ser capaz de se locomover no seu ambiente de trabalho partindo de uma
configuração inicial até alcançar uma configuração final, guiando-se por um determinado
caminho planejado, de forma segura, ou seja, desviando-se de obstáculos, e obedecendo
às restrições temporais impostas para o cumprimento dessa tarefa. Isto é, o robô deve
estar apto a navegar no seu ambiente de trabalho. O processo de navegação pode ser
subdividido em etapas hierarquizadas (Figura 1.1) que devem ser seguidas e executadas:
Mapeamento de Ambientes, Localização, Planejamento de Caminho, Geração de Trajetória e Execução de Trajetória [Alsina et al. 2002].
Mapeamento
de
Ambientes
Localização
Planejamento
de
Caminho
Geração
de
Trajetória
Execução
de
Trajetória
Figura 1.1: Diagrama hierárquico do processo de navegação.
3
• Mapeamento de Ambientes - percepção e construção de um modelo do ambiente a
partir de informações sensoriais;
• Localização - baseando-se do modelo obtido na etapa anterior juntamente com informações sensoriais extras, é deduzida a pose do robô dentro do ambiente;
• Planejamento de Caminho - o robô calcula um caminho partindo de sua configuração inicial até a configuração final desejada, evitando obstáculos;
• Geração de Trajetória - o caminho gerado é adaptado às restrições temporais e então é calculada a velocidade com que se deseja movimentar;
• Execução da Trajetória - os atuadores são controlados de forma a executarem a
trajetória gerada o mais fielmente possível.
No nível de mapeamento de ambientes, o robô deve coletar dados do seu entorno,
utilizando sensores, visando gerar modelos computacionais com as principais características estruturais do ambiente. Para isso, é necessário que os robôs sejam equipados com
dispositivos de percepção capazes de fornecer algum tipo de informação de seu entorno,
de modo que, a partir de algum processamento, essas informações sejam empregadas na
construção de um mapa do ambiente. Além disso, para que um sistema robótico possa
construir um mapa consistente, é necessário determinar sua pose (posição e orientação)
com relação a algum referencial fixo no mundo. Esse processo de obtenção de dados sensoriais, seu subsequente processamento mais a inferência da pose do robô, tendo como
objetivo a construção de um mapa do espaço no qual o robô está inserido, é chamado de
mapeamento robótico.
O mapeamento pode ser realizado em diferentes tipos espaços, seja em ambientes internos (indoor), ambientes externos (outdoor), ambientes subterrâneos e ambientes subaquáticos. Quanto à utilização, os mapas construídos podem ser considerados na realização de diversas tarefas, desde as mais simples, tais como, desvio de obstáculos,
planejamento de caminhos e localização, às tarefas de maior complexidade, por exemplo, exploração de minas subterrâneas, de instalações nucleares, limpeza de ambientes
tóxicos, combate a incêndios e resgate de suas vítimas, entre outras atividades de maior
dificuldade. Os robôs de diferentes capacidades motoras podem utilizar-se de mapas para
realizar tais missões, por exemplo, Dryanovski et al. (2010) utilizaram um micro veículo
aéreo para mapear ambientes para fins de localização e planejamento de caminho. No
trabalho de Marjovi et al. (2009) foi desenvolvido um time de robôs terrestres que utilizam um mapa para exploração e detecção de fogo em um ambiente. Já no trabalho de
Johannsson et al. (2010) um algoritmo de mapeamento foi implementado em um robô
subaquático com o objetivo de aplica-lo em vigilância de portos e inspeções de casco de
navios.
As primeiras pesquisas mais aprofundadas na linha de mapeamento robótico foram
publicadas no fim dos anos 1980, quando foram divulgados os primeiros estudos com resultados relevantes sobre o assunto. Nesse período, várias formas de mapeamento foram
propostas, empregando diversas estruturas geométricas e topológicas, com o intuito de se
CAPÍTULO 1. INTRODUÇÃO
4
obter a melhor precisão possível na representação do ambiente, sempre com a preocupação de lidar com a alta dimensionalidade dos espaços.
No ano de 2002, Thrun (2002) propôs uma classificação para as representações em
mapeamento robótico, segundo duas abordagens principais: a abordagem métrica e a
topológica. Enquanto os mapas da abordagem métrica armazenam propriedades geométricas do ambiente, os mapas da abordagem topológica descrevem a conectividade
entre diferentes compartimentos do espaço mapeado. Essa classificação é a mais adotada
até hoje, entretanto, uma variação sutil da abordagem métrica, acrescentando a classe de
mapas baseados em características aparece em alguns trabalhos.
Diversos tipos de sensores podem ser utilizados no mapeamento robótico. Os mais
comuns são os sonares, os lasers e as câmeras. Os sonares são atrativos por conta do
custo, são sensores relativamente baratos e podem ser facilmente encontrados no mercado.
Entretanto, apresentam imprecisões significativas nas suas medições. Os lasers, por outro
lado, são altamente precisos e propiciam a aquisição de mapas bem detalhados. Mas,
devido o seu elevado custo monetário deixam de ser atrativos. As câmeras são sensores
que a cada dia estão ficando mais baratos e possibilitam a aquisição de grande quantidade
de dados no entorno do robô. Por esses motivos, as câmeras estão alcançando um papel
de destaque dentre os sensores mais utilizados para mapeamento robótico.
No próximo capítulo o problema do mapeamento robótico será apresentado com maior
profundidade, no qual o problema será mais bem fundamentado com sua formalização, e
suas principais características serão exploradas.
1.1
Contribuições
O presente trabalho propõe um método de mapeamento robótico de ambientes internos e/ou externos, baseado em um sistema de visão com câmeras estéreo usando uma
representação inspirada em uma abordagem métrica probabilística do ambiente mapeado
através de grade de ocupação com informações tridimensionais (mapa 2,5-D), chamada
de grade de ocupação-elevação. Com o sistema de visão estéreo, o robô pode coletar
informações de diferentes lugares com variados tipos de obstáculo, não ficando dependente do tipo de ambiente em que se encontra, tampouco do tipo de características que
este lugar possui. O algoritmo de mapeamento proposto considera uma modelagem probabilística para o sistema de visão utilizado pelo robô, bem como para os movimentos
realizados pelo mesmo. Com isso, os resultados obtidos (os mapas) estarão coerentes
com as informações sensoriais colhidas pelo robô.A Figura 1.2 ilustra de forma simplificada o processo proposto de construção do mapa em grade de ocupação-elevação, onde a
partir dos dados processados e interpretados do sistema de visão, integrados com a pose
(coordenadas e orientação) do robô estimada, o mapa em grade é construído.
Por meio de uma modelagem probabilística do problema de mapeamento, as incertezas
relacionadas aos movimentos do sistema robótico e as imprecisões inerentes ao sistema
de percepção serão tratadas de forma adequada. O processo de modelagem de ambientes
em grade de ocupação-elevação torna o mapeamento independente de quais estruturas
1.1. CONTRIBUIÇÕES
5
Imagem esquerda Imagem direita
Câmera
Estéreo
Robô
Cálculo Estéreo
Modelo de
Odometria
Coordenadas (x, y)
Orientação (θ)
Mapa de
Disparidade
Grade de
Ocupação-Elevação
Figura 1.2: Processo de contrução do mapa em grade de ocupação-elevação.
estão presentes no espaço de trabalho do robô, diferente de outros tipos de mapas, que
dependem, por exemplo, detecção de características ou marcos presentes no ambiente.
Além disso, com as informações 3D o robô terá condições de identificar obstáculos
possíveis de serem transpassados ou não. Cada célula que compõe o mapa em grade de
ocupação-elevação tem armazenada, por meio de técnicas probabilísticas, informações de
ocupação e altura dos obstáculos. Com isso, o robô pode identificar se um determinado
local do ambiente está ocupado por um obstáculo e se o mesmo pode ser superados.
Com o mapa construído a partir da abordagem aqui apresentada, o robô será capaz
de utilizá-lo para realizar diferentes tarefas, desde as mais simples e diretas como, localização, exploração, planejamento de caminhos, à tarefas de maior complexidade, por
exemplo, limpeza de lixos tóxicos, regates de vítimas de desastres, combate a incêndios,
exploração de minas subterrâneas, entre outras.
CAPÍTULO 1. INTRODUÇÃO
6
Assim, pode-se destacar como contribuições principais a modelagem probabilística
do sensor utilizado, no caso um sistema de visão estéreo, de modo que o mapa adquirido
possa representar com fidelidade as informações capturadas e também a construção de um
mapa em grade de ocupação probabilística com informações 3D, sem a necessidade de
uma estrutura de dados tridimensional (mapa 2,5-D, aqui chamado de grade de ocupaçãoelevação), que seria custosa computacionalmente.
Diferente das abordagens existentes na literatura, cada célula do mapa gerado terá um
valor da probabilidade de ocupação, terá uma estimativa da altura dos obstáculos e da
variância da altura, indicando sua acurácia. Deste modo, pode-se identificar obstáculos
possíveis de serem superados a partir do mapa de ocupação-elevação construído, considerando os erros inerentes ao sistema perceptivo robô, os quais são modelados por meio
de técnicas probabilísticas,
1.2
Motivação e Justificativa
Uma das etapas capitais do problema de navegação inteligente consiste no mapeamento de ambientes. Esta fase requer que o robô esteja munido de sensores que o habilite
a construir uma descrição espacial do ambiente no qual está inserido, a partir de informações desses sensores. De posse da descrição espacial ou mapa construído o robô é
capaz de interagir de forma coerente com seu ambiente, realizando uma navegação eficiente e agindo de modo flexível frente a situações inesperadas. Assim, o robô poderá
realizar diferentes tipos de tarefas de forma inteligente e sem a interferência humana,
por exemplo, planejamento de caminhos, exploração, manipulação de objetos, resgates,
limpeza de ambientes contaminados, entre outras.
Entre as maneiras mais difundidas de representação de ambientes mapeados está a
grade de ocupação, proposta inicialmente por Elfes (1987), que modela o estado de ocupação de um ambiente. Nesta abordagem o mapa é representado por uma matriz de células, que podem estar ocupadas, livres ou pode não ter sido mapeadas. Através dessa
abordagem é possível representar o ambiente mapeado de forma relativamente precisa.
Além disso, os mapas em grade de ocupação facilitam a aplicação direta de algoritmos de
planejamento de caminhos, de exploração, de desvio de obstáculo e de localização. Em
anos posteriores, alguns pesquisadores propuseram a expansão da grade de ocupação para
o mapeamento tridimensional dos ambientes, aplicando-o, principalmente, para os casos
onde o terreno de navegação dos robôs não é plano, e nos casos onde é necessário que
seja realizada uma navegação precisa entre os objetos, considerando a altura deles dentro
do ambiente [Moravec 1996, Andert 2009, Dryanovski et al. 2010]. Porém, a construção
desses tipos de mapas requer um vasto custo computacional para o seu armazenamento
e processamento. Para superar esse problema, surgiram, então, os mapas 2,5-D, que armazenam informação tridimensionais em uma estrutura de dados bidimensional.
No tocante aos sensores utilizados no mapeamento, devem ser consideradas certas
propriedades, por exemplo, preço do sensor, custo computacional, consumo de energia, tipo de dados coletados e precisão. Considerando esses requisitos, as câmeras se
apresentam como uma interessante alternativa para os sistemas de percepção robóticos.
Propriedades como baixo custo monetário, portabilidade, baixo consumo de energia e a
1.3. ORGANIZAÇÃO DO TRABALHO
7
grande quantidade de dados que podem ser obtidos por esses sensores, fazem com esses
dispositivos alcancem um papel de destaque em aplicações atuais com robô autônomos.
Entretanto, certas características relacionadas aos sensores podem interferir na qualidade dos mapas construídos pelos robôs, e devem ser consideradas no processo de mapeamento. Os sistemas de percepção possuem imprecisões intrínsecas à natureza do dispositivo de percepção utilizado, que podem distorcer as medições dos dados coletados. Como
consequência, o mapa construído pode possuir incoerências importantes que por sua vez,
comprometem a interação do robô com o seu ambiente de trabalho. Ou seja, o robô pode
construir um mapa inconsistente, fora da realidade espacial do ambiente mapeado. Para
lidar de forma adequada com as imprecisões e incertezas sensoriais surgiram as abordagens de mapeamento baseadas em técnicas e ferramentas probabilísticas. Através das
teorias da probabilidade é possível modelar explicitamente as diversas fontes de ruído e
seus efeitos nas medições.
Diante desse contexto, este trabalho propõe o método de mapeamento em grade de
ocupação-elevação, onde informações tridimensionais dos ambientes mapeamedos serão
armazenadas juntamanete com a probabilidade de ocupação dos mesmos. As informações
que compõem o mapa são tratadas com ferramentas estocásticas para garantir a manipulação adequada dos dados sensoriais, providos por um sistema de câmeras estéreo.
1.3 Organização do trabalho
A apresentação desse trabalho prossegue de acordo com a seguinte organização:
• O Capítulo 2 aborda o tema do mapeamento robótico mais formalmente, apresentando os fundamentos teóricos do problema, desafios que devem ser superados e
classificações;
• O Capítulo 3 trás uma explicação geral sobre o mapeamento de ambientes através
de sistemas de visão e posteriormente aborda o mapeamento visual em grade de
ocupação;
• O Capítulo 4 descreve o mapeamento em grade de ocupação e os mapas de elevação
com suas formalizações matemáticas;
• O Capítulo 5 define o método de mapeamento proposto formalmente, detalhando
a estrutura de construção do mapa em grade de ocupação-elevação e a forma de
integração das informações sensoriais no mapa.
• O Capítulo 6 apresenta os experimentos realizados com o sistema proposto, considerando a aplicabilidade do mesmo tanto em ambientes internos quanto em ambientes externos;
• Finalmente, no Capítulo 7 são apresentadas as considerações finais do trabalho,
delineando as perspectivas futuras para o sistema em questão.
CAPÍTULO 1. INTRODUÇÃO
8
1.4
Produções Científicas
Capítulos de Livro
• Souza, A. A. S., A. M. Santana, A. A. D. Medeiros, L. M. G. Gonçalves. Mapeamento de Ambientes. In: Robótica Móvel. (Org.) Roseli A. Francelin Romero;
Edson Prestes; Fernando Osório; Denis Wolf. LTC/Elsevier, Em publicação.
• Souza, A. A. S., R. S. Maia, L. M. G. Gonçalves. 3D Probabilistic Occupancy
Grid to Robotic Mapping with Stereo Vision. In: Current Advancements in Stereo
Vision. Dr. Asim Bhatti. (Org.). Rijeka: InTech, v. 1, p. 1-21, 2012.
• Souza, A. A. S., A. M. Santana, A. A. D. Medeiros, L. M. G. Gonçalves. Probabilistic Mapping by Fusion of Range-Finders Sensors and Odometry. In: Sensor
Fusion, Aleksandar Lazinica. (Org.). Rijeka: SCIYO, 2010.
• Santana, A. M., A. A. S. Souza, P. J. Alsina, A. A. D. Medeiros, L. M. G. Gonçalves.
Fusion of Odometry and Visual Datas to Localization a Mobile Robot Using Extended Kalman Filter. In: Sensor Fusion, Aleksandar Lazinica (Org.). Sensor Fusion. Rijeka: SCIYO, 2010.
Artigos em Congressos
• Souza, A. A. S., L. M. G. Gonçalves. 2.5-Dimensional Grid Mapping from Stereo
Vision for Robotic Navigation. In: LARS/SBR - Latin American Robotics Symposium, Fortaleza-CE, 2012.
• Souza, A. A. S., L. M. G. Gonçalves. 3D Probabilistic Occupancy Grid to Robotic
Mapping. In: ICINCO - International Confrrence on Informatics in Control, Automation and Robotics, Noordwijkerhout, 2011.
• Souza, A. A. S., L. M. G. Gonçalves. Mapeamento de Ambientes em Grade de
Ocupação Probabilística a Partir de Visão Estéreo. In: Simpósio Brasileiro de Automação Inteligente - SBAI São João Del Rei-MG, 2011.
• Souza, A. A. S., R. S. Maia, L. M. G. Gonçalves. Uma Proposta de um Time de
Robôs Heterogêneos Baseados na Tecnologia Sun SPOT para Mapeamento de Ambientes. In: ROBOCONTROL 2010 Workshop de Robótica Aplicada e Automação,
Bauru, 2010.
• Nascimento, C. V., L. M. G. Gonçalves, A. A. S. Souza, R. Q. Gardiman. Towards
Fine Control Based on Sun SPOT Architecture. In: ROBOCONTROL 2010 Workshop de Robótica Aplicada e Automação, Bauru. 2010.
1.4. PRODUÇÕES CIENTÍFICAS
9
• R. S. Maia, A. A. S. Souza, L. M. G. Gonçalves. Um modelo do Processo de
Aprendizagem proposto para um ambiente multi-robô. In: Peruvian Computing
Week, 2010, Trujillo, Peru. JPC, 2010.
10
CAPÍTULO 1. INTRODUÇÃO
Capítulo 2
Mapeamento
Este capítulo apresenta a fundamentação teórica relacionada ao problema de Mapeamento de ambientes com robôs móveis. Aqui serão apresentados os desafios a serem
suplantados, a classificação adotada para distinguir os diferentes tipos de mapas robóticos, destacando as vantagens e desvantagens de cada abordagem. Ao final do capítulo
será apresentada uma seção ressaltando trabalhos recentes da literatura que utilizam o
mapeamento de ambientes com robôs, com distintos sensores e tipos de mapas, na realização de diferentes tarefas.
2.1 O Problema do Mapeamento Robótico
A tarefa de mapeamento é muitas vezes considerada o mais importante problema na
robótica, cujo progresso pode impactar uma grande parte dos problemas baseados em percepção como, localização, navegação, exploração, assim por diante [Yang & Wang 2011].
E para formalizar melhor o problema do mapeamento algumas observações devem ser
destacadas. A primeira delas diz respeito ao sistema perceptivo dos robôs. Para realizar
o mapeamento de um determinado espaço, um robô deve possuir um conjunto de sensores, que o habilite a obter dados sobre o ambiente. A segunda observação é que este
mesmo sistema de percepção deve fornecer uma estimativa exata da pose (coordenadas e
orientação) do robô em relação a algum referencial fixo global.
Feitas essas observações, o mapeamento de ambientes com robôs pode ser visto como
o problema de construir um modelo espacial do ambiente do robô, com uma representação
computacional, baseando-se nos dados fornecidos pelos sensores internos e externos do
sistema robótico. A Figura 2.1 é uma forma clássica de ilustrar o processo de mapeamento
em gráfico. A referida figura, representa a pose do robô por x e as medições sensoriais
adquiridas a partir de inspeções no ambiente no decorrer do tempo por z. Ambas as
variáveis devem ser conhecidas para que o robô tenha a possibilidade de construir o mapa
m. Perceba que o mapeamento é um processo que se desenvolve com o tempo.
Porém, considerar verdadeira a suposição de que os sensores podem fornecer uma
estimativa exata da pose do robô não é válido, visto que, existem diversas fontes de incertezas no mundo físico que contribuem com a degradação das informações sensoriais
[Thrun et al. 2005]. Então, para ser obter uma estimativa mais precisa da pose do robô
seria necessário a existência de um mapa a priori. Tem-se nesse caso, um paradoxo: o
CAPÍTULO 2. MAPEAMENTO
12
Figura 2.1: Grafico de composição do mapeamento.
sucesso na construção de um mapa coerente depende do conhecimento preciso da pose do
robô, e para inferir uma estimativa correta da pose do robô é necessário um mapa do ambiente a priori. Percebe-se que existe uma interdependência entre localização (inferência
da posição e orientação do robô no ambiente) e mapeamento. Por conta dessa dificuldade muitos pesquisadores desdobram o problema de mapeamento para uma problema de
localização e mapeamento simultâneos ou SLAM (do inglês, Simultaneous Localization
and Mapping)[Grisetti et al. 2007].
Neste trabalho será considerado que o robô possui um sistema de localização baseado
em odometria que fornece uma estimativa relativamente precisa de sua pose, dado que é
feita uma calibração anterior apresentada em [Souza 2008]. Esta abordagem é conhecida
como mapeamento com pose conhecida [Thrun et al. 2005]. O foco do trabalho esta
em fornecer um novo modelo de representação para mapeamento baseado em grade de
ocupação com informações 3D, a fim de que o robô possua a capacidade de determinar se
um dado obstáculo pode ser transposto ou não.
2.2
Desafios do problema de mapeamento robótico
Em um dos trabalhos mais referenciados na área de mapeamento robótico, Thrun
(2002) evidencia alguns desafios que devem ser considerados durante o processo de mapeamento. A seguir, cada desafio será exposto de forma concisa.
2.2.1 Imprecisões sensoriais
Como já mencionado, os robôs necessitam de sensores para realizar o mapeamento.
Esses sensores são limitados no que podem perceber. O alcance e a precisão estão sujeitos a limitações físicas; são susceptíveis a ruídos, que podem degradar suas medições;
e podem sofrer danos estruturais. Além disso, existem incertezas inerentes aos movimentos realizados pelos robôs em seus ambientes. Os motores, responsáveis pela locomoção,
são dispositivos que podem ocasionalmente falhar ou danificar-se. Ademais, os sinais
de controle que os aciona podem variar com a ação de ruídos. Fatores sistemáticos, tais
2.2. DESAFIOS DO PROBLEMA DE MAPEAMENTO ROBÓTICO
13
como as incertezas presentes nos parâmetros que fazem parte da modelagem cinemática
do robô (diferenças no tamanho das rodas, medição equivocada de eixo, etc.) e/ou fatores
não sistemáticos, como as incertezas oriundas de situações inesperadas (colisão com objetos inesperados, escorregamentos das rodas, derrapagens, etc.), também são fontes de
incertezas, que tornam imprecisas as informações do sistema robótico.
Aqui, a grande dificuldade está na natureza do ruído presente nas medições, isto é,
modelar o problema de mapeamento robótico seria relativamente fácil se o ruído em
diferentes medições fosse estatisticamente independente. No entanto, o que se vê é uma
dependência estatística, pois os erros intrínsecos aos movimentos do robô interferem na
forma como as medições sensoriais são interpretadas.
A Figura 2.2 ilustra uma situação em que erros de medição dos movimentos prejudicaram a construção de um mapa preciso, em um robô equipado com sonares. O contorno
mais contínuo em vermelho representa a configuração das paredes do ambiente mapeado,
no caso, um corredor. O ponto na extremidade direita da figura representa a posição do
robô ao término da tarefa de mapeamento.
Figura 2.2: Mapa corrompido por erros de odometria.
Uma boa alternativa para se alcançar o sucesso diante desse desafio é modelar as
fontes de erros por funções probabilísticas, permitindo que os dados sensoriais, mesmo
incertos, sejam tratados de forma adequada durante o processo de mapeamento. Quando
esses fatores são desconsiderados, estamos propensos a testemunhar a construção de mapas inconsistentes e imprecisos.
2.2.2 Dimensionalidade
No mapeamento com robôs deve ser observado também a dimensão dos ambientes.
Não se pode considerar que o mapeamento de um ambiente simples e estruturado, como
um corredor, é igual ou possui os mesmos requisitos e complexidade que o mapeamento
de um ambiente de grandes dimensões, por exemplo, um bairro de uma cidade. Questões
como, tipo de representação utilizada para reproduzir o ambiente mapeado, nível de detalhamento do mapa, dimensões do mapa (2D ou 3D), espaço computacional disponível
(memória), recursos de processamento, entre outras, devem ser analisadas.
Ademais, não se pode esquecer que, quanto maior e mais complexo o ambiente, maior
a probabilidade de ocorrer algum tipo de erro nos movimentos do robô, o que pode acarretar em prejuízos na qualidade do mapa construído.
CAPÍTULO 2. MAPEAMENTO
14
2.2.3 Associação de dados - Matching
É natural que um objeto inserido em um ambiente a ser mapeado seja detectado
mais de uma vez durante o mapeamento em diferentes instantes de tempo. É importante que o robô tenha a capacidade de diferenciar objetos já mapeados dos que ainda
não o foram. Este problema é conhecido como associação de dados ou correspondência de dados (matching). Com o auxílio da Figura 2.3 pode-se entender melhor essa
questão. Nesta figura há duas imagens coletadas, em instantes e posições diferentes, por
uma câmera embarcada em um robô móvel. Todos os pontos interligados por segmentos de retas entre as duas imagens foram reconhecidos, mesmo tendo sido capturadas a
partir de locais distintos. Para outros pontos não foi possível encontrar o seu correspondente. Caso os movimentos realizados dentro do intervalo de captura das imagens fossem
ainda mais acentuados a dificuldade de se encontrar pontos correspondentes nas imagens
aumentaria.
Figura 2.3: Mapa corrompido por erros de odometria.
Ignorar o problema da associação de dados no mapeamento pode conduzir a inconsistências e divergências nos mapas. Um esquema eficiente e efetivo de associação de
dados deve estabelecer diferenças entre medições espúrias e novas medições juntamente
com uma função básica para integrar ao mapa disponível, novas medidas sensorais.
2.2.4 Dinamicidade do ambiente
A grande maioria dos trabalhos relacionados à navegação e mapeamento consideram
os ambientes de trabalho dos robôs como sendo estáticos. Quando o interesse está no mapeamento de ambientes dinâmicos ou não estacionários, como, por exemplo, escritórios
onde pessoas trafegam constantemente e manufaturas onde objetos são transportados para
diferentes lugares, a complexidade do processo de mapeamento aumenta consideravelmente. O robô passa a operar com a imprevisibilidade do ambiente, especialmente quando
há pessoas em movimento constante.
2.3. TIPOS DE REPRESENTAÇÕES
15
Um local já mapeado que sofre em algum instante, determinadas mudanças estruturais
pode não ser reconhecido pelo robô. Dessa forma, há uma grande chance de o robô
considerar esse espaço como sendo uma nova área ainda não mapeada ou até mesmo
desconsiderar as medições coletadas e classificá-las como incoerentes.
2.2.5 Estratégia de exploração
Durante o mapeamento, o sistema robótico deve escolher certos caminhos a serem
seguidos. A questão central é: dado que o robô tem algum conhecimento sobre o mundo,
para onde ele deverá se mover para adquirir novas informações? A resposta a essa pergunta é de responsabilidade da estratégia de exploração, a qual deve estabelecer princípios
para que o robô se movimente com o objetivo de explorar todo o ambiente a ser mapeado.
A estratégia de exploração admite que a pose do robô é precisamente conhecida e
procura direcioná-lo, de modo eficiente, ao longo do ambiente a fim de que o mapa seja
construído em sua totalidade [Stachniss 2009]. Diante disso, é preciso considerar o modelo do ambiente parcialmente montado, e a partir dele, planejar o movimento a ser realizado. O diagrama da Figura 2.4 adaptado do trabalho de Stachniss (2009), considera que
a exploração é uma tarefa que engloba o problema de mapeamento e o planejamento de
caminhos.
SLAM
Mapeamento
Localização
Abordagem
integrada
Exploração
Localização ativa
Planejamento
Figura 2.4: O problema da exploração é a integração do Mapeamento com o Planejamento
de caminhos [Stachniss 2009].
Neste mesmo trabalho, Stachniss (2009) apresenta um apanhado geral das várias técnicas de exploração desenvolvidas, traçando um comparativo com sua proposta, baseada
em mapas de cobertura (coverage maps).
2.3 Tipos de Representações
Existem duas classes principais que diferenciam os tipos de representações de mapas: as representações baseadas em topologia e representações baseadas em informações
métricas [Thrun 2002]. Alguns pesquisadores sugerem acrescentar mais um paradigma
16
CAPÍTULO 2. MAPEAMENTO
de representação baseado em características encontradas nos ambientes [Choset & Fox
2004][Rocha 2006]. Porém, os mapas de características armazenam, na verdade, informações métricas relacionadas às características, por esse motivo essa abordagem será
considerada, nesse trabalho, como uma instância dos mapas métricos. A seguir, as duas
abordagens serão mais bem explanadas.
2.3.1 Mapas Topológicos
A abordagem topológica representa computacionalmente um ambiente mapeado por
meio de um grafo. Em termos gerais, os grafo descrevem a conectividade entre compartimentos de um ambiente mapeado. Os nós do grafo correspondem a áreas que possuem
informações sensoriais homogêneas e as arestas reproduzem a relação de conexão entre
essas regiões representadas por nós.
Do ponto de vista do sistema computacional do robô, a representação de um ambiente mapeado através de um grafo é uma boa alternativa, visto que os grafos são estruturas compactas e podem ser armazenados em uma quantidade relativamente reduzida de
memória. Além disso, a representação em grafos favorece a execução de tarefas de mais
alto nível, como planejamento de caminhos, simplesmente pela aplicação de algoritmos
tradicionais de busca em grafos.
Um problema importante desta abordagem é verificado quando se procura um padrão
de definição de quais estruturas poderão ser consideradas nós e quais relações serão ponderadas para a criação das arestas. Ademais, esse tipo de representação trata o problema
de localização de uma forma abstrata, isto é, não é possível inferir de forma explícita
as coordenadas e a orientação de um robô em um mapa topológico. É possível apenas
afirmar em qual nó, ou seja, em qual área do ambiente o robô se encontra.
Para explicar o processo de construção de um mapa topológico, a Figura 2.5 traz a
ilustração de um cenário típico de um escritório simples, no qual um robô (marco em
vermelho) munido de sonares está encarregado de criar uma representação topológica
do ambiente. Na Figura 2.5(a), o robô começa o processo de mapeamento colhendo
informações de seu entorno, a partir das medidas sensoriais (as 16 linhas que se originam do robô), e identifica os limites do primeiro cômodo. Neste momento, o primeiro
compartimento passa a ser classificado como o nó inicial do mapa topológico. Com o
objetivo de mapear as demais áreas do ambiente, o robô sai do espaço mapeado e segue o
caminho tracejado que o leva a um segundo compartimento, passando a explorá-lo (Figura
2.5(b)). Esse novo espaço, após ser identificado, é classificado como um novo nó do mapa
topológico. Seguindo a trajetória especificada, o robô passa a um novo compartimento,
explorando-o (Figura 2.5(c)) e posteriormente classificando-o como o terceiro nó do grafo
(Figura 2.5(d)). O processo de mapeamento segue (Figura 2.5(e)) e a cada novo cômodo
identificado um novo nó é adicionado ao mapa topológico. É importante observar que as
arestas estão identificando a conexão que existe entre os compartimentos.
Percebe-se que o mapa topológico do exemplo dado pode ser facilmente armazenado
no sistema computacional do robô, essa é uma vantagem constatada neste tipo de representação. Porém, quando se trata da construção de um mapa topológico de ambientes de
dimensões maiores, essa construção pode se tornar mais complicada em virtude das am-
2.3. TIPOS DE REPRESENTAÇÕES
17
1
(a)
(b)
2
2
1
3
1
(c)
(d)
2
3
4
1
(e)
Figura 2.5: Mapemento topológico.
biguidades que podem existir nas informações sensoriais, que geralmente são esparsas.
Isso pode ter como consequência direta, falhas na identificação de áreas já mapeadas e
não mapeadas (problema de associação de dados). Essa característica dificulta a construção e a manutenção de mapas desse tipo.
2.3.2 Mapas Métricos
A abordagem de representação métrica tem como objetivo armazenar informações de
objetos e formações geométricas presentes no ambiente do robô, com certa fidelidade
métrica em relação ao mundo real. Os mapas métricos podem ser divididos nos mapas
baseados em grade de ocupação e nos mapas baseados em características. A seguir, essas
duas classes serão detalhadas.
18
CAPÍTULO 2. MAPEAMENTO
Grade de Ocupação (occupancy grid maps)
O modelo de mapeamento em grade de ocupação foi proposto inicialmente em 1987 e
formalizado em 1989 pelo cientista brasileiro Alberto Elfes [Elfes 1987][Elfes 1989]. É o
método de mapeamento mais representativo, cuja função é reproduzir um espaço em uma
grade (grid) de células, as quais modelam o estado de ocupação do ambiente [Yang &
Wang 2011]. A Figura 2.6 ilustra uma medição realizada por um sonar e como seria a sua
representação em uma grade de ocupação. As células preenchidas de preto representam
prováveis obstáculos detectados pelo sonar, as células em branco representam regiões do
ambiente possivelmente livres ou não ocupadas, por fim, as células em cinza representam
regiões ainda não mapeadas pelo sonar.
Figura 2.6: Representação de uma medição de um sonar em uma grade de ocupação.
O valor de ocupação atribuído às células é inferido por uma função probabilística,
cujo resultado indica a probabilidade de um lugar estar ocupado, a partir de uma medição
sensorial interpretada. A cada nova medição sensorial o valor de ocupação das células
dentro do campo visual dos dispositivos de percepção é atualizado. O modelo espacial
probabilístico baseado em grade de ocupação se apresenta como uma forma de representação que pode ser usada diretamente na realização de tarefas de navegação, tais como
planejamento de caminho com desvio de obstáculo e estimativa de posição [Elfes 1989].
Neste trabalho o mapeamento em grade de ocupação é utilizado para representar o
ambiente mapeado por um robô munido de um sistema de visão estéreo. A grade de ocupação foi escolhida por apresentar algumas interessantes vantagens em relação a outras
representações de mapas. Em um capítulo posterior, o mapeamento em grade de ocupação
será explorado com mais detalhes.
Mapas de características (feature-based maps)
Uma característica pode ser entendida como um objeto ou alguma forma facilmente
detectável presente em um ambiente, por exemplo, retas, cantos, quinas, bordas, círculos, planos ou regiões com alguma propriedade específica. Os mapas de características
registram informações a respeito desses tipos de elementos. Geralmente são informações
contendo alguma relação métrica com o mundo real como, coordenadas cartesianas e coordenadas polares. A Figura 2.7 ilustra um exemplo de características sendo detectadas
em um corredor típico de um ambiente interno. Nesta figura, segmentos de retas presentes
2.3. TIPOS DE REPRESENTAÇÕES
19
em contornos de portas, janelas, piso, etc., são vistos como formas notáveis e adequadas
para a construção de um mapa de características.
Figura 2.7: Construção de um mapa de características a partir da detecção de retas.
Uma vantagem significativa desse tipo de mapa é que muitas vezes possibilita uma
construção compacta se comparada a representações em grade de ocupação. Porém, também possui desvantagens, e a principal delas é a dependência de um procedimento prédefinido para detectar e extrair características do ambiente [Stachniss 2009].
2.3.3 Mapas topológicos vs. Mapas métricos - Vantagens e Desvantagens
Diante do apresentado acima é interessante traçar um diagnóstico comparativo entre
as duas abordagens citadas, conferindo vantagens e desvantagens de cada uma. Para isso,
serão adotados como base os parâmetros levantados no trabalho de Thrun [Thrun 1998].
Uma vantagem importante dos mapas métricos em relação aos topológicos, é que
são mais simples de serem construídos e mantidos, ainda que sejam considerados os
ambientes complexos e grandes. Ainda, a representação métrica torna mais fácil o reconhecimento de lugares diferentes com base na posição geométrica do robô dentro de
um sistema de coordenadas global. Com base em uma boa estimativa da pose do robô,
as diversas medições sensoriais semelhantes, tomadas de diferentes posições, podem ser
distinguíveis. Com isso, locais geometricamente próximos são diferenciados com certa
facilidade. Porém, deve-se atentar para a prerrogativa de se ter uma boa estimativa da
pose do robô, o que não é tão trivial de se obter.
Como já mencionado anteriormente, existe certa dificuldade na construção de mapas
topológicos, ligada a definição de quais estruturas serão classificadas como nós e de quais
informações serão compostas as arestas. Isso se torna ainda mais dificultoso se as informações sensoriais do robô forem esparsas e ambíguas. Porém, como vantagem em
relação à abordagem métrica, a pose do robô não precisa ser exatamente conhecida.
Uma desvantagem da representação métrica está no alto custo computacional que esta
requer para ser construída, armazenada e atualizada. É necessário um maior espaço com-
20
CAPÍTULO 2. MAPEAMENTO
putacional para armazenar mapas dessa abordagem, principalmente quando se tem mapas
em grade de ocupação com uma resolução fina ou mapas de características com grandes
quantidades de características armazenadas. Os mapas topológicos, por sua vez, são compactos de resolução proporcional à complexidade do ambiente. Essa estrutura compacta
favorece o armazenamento em reduzido espaço de memória e a resolução de problemas
de mais alto nível com menor necessidade de processamento.
É possível também, combinar diferentes tipos de representação de mapas em uma
abordagem híbrida [Blanco et al. 2008]. O principal objetivo desta representação é integrar as principais vantagens das abordagens métrica e topológica, o que deve reduzir
as desvantagens pontuais de cada enfoque. Assim, o robô pode, eficientemente, executar
as tarefas mais adequadas para cada tipo de representação. Por exemplo, o robô pode
navegar pelo seu ambiente, planejando rotas através de algoritmos de busca em grafo
pelo mapa topológico, e ao mesmo tempo, pode adotar estratégias locais de desvio de
obstáculos utilizando a representação métrica.
2.3.4 Trabalhos Relacionados
As primeiras investigações que se destacaram na linha de mapeamento de ambientes com robôs surgiram no final da década de 1980. Nesta época foram publicados os
primeiros trabalhos com resultados relevantes. Com essas primeiras pesquisas apareceram vários modelos de mapeamento usando diversas estruturas geométricas e topológicas,
com o objetivo de se alcançar a melhor precisão possível na representação do ambiente,
considerando a dificuldade de lidar com a alta dimensionalidade dos espaços.
Os pesquisadores propuseram em seus trabalhos formas de representações como, representação geométrica 3D por esferas [Goldstein et al. 1987], representação poligonal
[de Saint Vincent 1987], representação por meio de características como pontos, arestas
e cantos [Merat & Wu 1987], modelos geométricos hierárquicos [Kriegman et al. 1987],
representação por grade de ocupação [Elfes 1987], representação baseada na topologia do
ambiente [Kuipers & Byun 1988], entre outras [Angelopoulou et al. 1992].
Posteriormente, em um artigo descrevendo o estado da arte do mapeamento robótico,
Thrun (2002) propôs uma classificação das representações de mapas nas duas classes
apresentadas anteriormente: topológica e métrica. De forma simplista, a abordagem
topológica engloba todas as representações cujo enfoque é reproduzir mapas na forma
de grafo, onde os nós são lugares e a conectividade entre os locais é descrita por suas
arestas. E a abordagem métrica passou a compreender as representações que presam em
armazenar propriedades geométricas do ambiente.
Uma forma mais recente de representar ambientes é através do uso de informações
semânticas que podem ser extraídas dos mapas. É possível, por exemplo, obter uma
classificação dos obstáculos mapeados (cadeiras, mesas, portas abertas ou fechadas, etc.)
através de técnicas semânticas [Wolf & Sukhatme 2008].
A tarefa de mapeamento se estende a distintos ambientes. Os robôs podem ser utilizados para mapear ambientes internos (indoor), ambientes externos (outdoor), ambientes
subterrâneos e ambientes subaquáticos. No trabalho de Santana & Medeiros (2009), eles
aproveitaram o fato de que muitos ambientes internos tem o piso formado por blocos,
2.3. TIPOS DE REPRESENTAÇÕES
21
para implementar um sistema de mapeamento de linhas no plano do piso do ambiente,
sabendo-se que os espaços entre os bloco acabam originando linhas. Gallelos & Rives
(2010), por sua vez, utilizaram um robô equipado de diferentes sensores para mapear ambientes internos e construíram uma representação 3D do ambiente mapeado. Passando
para ambientes externos, Yang & Wang (2011) apresentaram uma abordagem de mapear
ambientes urbanos considerando a existência de objetos estáticos e dinâmicos. Eles exibiram os resultados de seus estudos em mapas baseados em grades de ocupação. Silver et al.
(2004) utilizaram um robô para mapear e explorar minas subterrâneas, atividade essa, que
pode apresentar riscos a seres humanos. Johannsson et al. (2010), por sua vez apresentaram um robô submarino que detecta características a partir de imagens de sonares para
construir um mapa que é posteriormente utilizado em vigilância submarina. Esses são
alguns exemplos de trabalhos que mostram a diversificação de ambientes que podem ser
mapeados utilizando-se diferentes técnicas de mapeamento.
Para que um sistema robótico tenha sucesso em seu mapeamento é interessante que
possua sensores que capturem informações do seu entorno, com certas características
desejáveis: campo de visão amplo, acurácia, dados de fácil interpretação, baixo consumo
de energia, tamanho e peso reduzidos, entre outras. Distintos tipos de sensores podem ser
utilizados, porém os de maior destaque são os sonares, os scanners lasers e as câmeras.
Os sonares são sensores atrativos pelo seu baixo custo, entretanto possuem propriedades que os tornam sensores em desuso. Muitas medições são imprecisas por serem afetadas por problemas de falsas reflexões das ondas sonoras em superfícies planas. Um
recente trabalho que se utiliza de sonares para extrair características de ambientes desordenados foi apresentado por [Lee & Son 2010].
Uma interessante alternativa para a construção de mapas densos são os scanners lasers,
esses são sensores bastante precisos, eficientes e fornecem informações de fácil interpretação e que não necessitam de processamento complexo. Porém, esses sensores não são
hábeis no tratamento de superfícies de vidro. Ademais, são sensores que apresentam um
alto custo monetário. Ruhnke et al. (2011) implementaram um algoritmo de mapeamento
de alta precisão baseado em informações de sensores lasers. Eles propuseram a aplicação
de técnicas de otimização para melhorar as estimativas da pose do robô e das medições
sensoriais, a fim de obter um mapa mais acurado do ambiente.
As câmeras vêm ganhando destaque nos trabalhos relacionados a mapeamento de ambientes e navegação com robôs, por serem dispositivos que podem prover uma grande
quantidade de informações sobre o ambiente no qual estão inseridas. Além disso, são
compactas, leves e podem ser encontradas com custo moderado. Seja com um sistema
de múltiplas câmeras, como os sistemas de visão estéreo e sistemas de câmeras omnidirecionais, ou com sistemas monoculares, são inúmeras as possibilidades de técnicas para
geração de mapas a partir das câmeras, que dependem do tratamento dado às imagens.
O grande desafio encontrado está no processamento das informações em tempo real,
porém este problema vem sendo amenizado com o desenvolvimento de processadores
mais poderosos e de baixo custo. Um interessante trabalho com base em um sistema de
visão foi desenvolvido por Marks et al. (2009). Os autores desenvolveram um mapeamento em grade para ambientes não estruturados com um robô munido de uma câmera
estéreo. O mapa em grade é preenchido com os resultados computados por um modelo
22
CAPÍTULO 2. MAPEAMENTO
sensorial probabilístico que adota a função Gama em seu cerne. Ao final,o mapa adquirido
comporta informações sobre o quão navegável é um determinado terreno.
Com frequência se encontra na literatura autores propondo o uso em conjunto de sensores distintos. O objetivo principal é fundir as informações de todas as fontes para alcançar um mapeamento mais rico e eficiente. Gallelos & Rives (2010), por exemplo,
utilizam um robô provido de uma câmera omnidirecional e um laser para realizar o mapeamento de ambientes internos. No trabalho de Ahn et al. (2007), os autores fundiram
informações de um sistema de visão estéreo e sonares para coletar informações planares
de ambientes internos.
O presente trabalho está no contexto do mapeamento de ambientes com sistema de
câmeras estéreo e representação em grade. As câmeras apresentam inúmeras características que as tornam atraentes para serem aplicadas no mapeamento de ambientes. Essa
abordagem de mapeamento utilizando câmeras (monocular, estéreo ou omnidirecional) é
também conhecida por mapeamento visual (Visual Mapping), que será tema do próximo
capítulo.
Capítulo 3
Mapeamento Visual
Este capítulo contextualiza o problema de mapeamento com sensores visuais, ou seja, a
construção de uma representação espacial a partir de imagens. Este procedimento é também conhecido como mapeamento visual. O capítulo exporá as técnicas de mapeamento
visual com diferentes configurações de câmeras. Ademais, alguns pontos importantes
serão destacados para explicar quais e como as informações visuais podem extraídas
e manipuladas para a construção de mapas robóticos. Semelhantemente ao capítulo
anterior, serão apresentados trabalhos correlacionados ao tema, expondo as técnicas e
novidades utilizadas mais recentemente.
3.1 Contextualização
Como anteriormente explicitado, a tarefa de mapeamento tem um grande impacto em
tarefas que dependem do sistema perceptivo dos robôs como, localização, navegação, exploração, entre outras. Quando este problema é considerado na conjunção dos sensores
visuais ou câmeras, passa a ser denominado de mapeamento visual. Neste contexto, as informações visuais capturadas são utilizadas para que o robô realize sua tarefa empregando
uma navegação visual segura e eficiente, podendo abranger a vigilância de ambientes,
resgate em acidentes ou catástrofes, identificação e rastreamento de objetos, exploração
aérea, patrulhamento, entre outras.
A inspiração para essa abordagem vem da fisiologia humana. O principal sentido
empregado na navegação e localização de uma pessoa entre objetos e obstáculos é o da
visão. Do mesmo modo, na robótica um sistema visual artificial construído a partir de
câmeras pode ser muito útil na navegação e localização de um robô em seu ambiente.
A grande vantagem de se utilizar um sistema de percepção baseado em sensores visuais está na significativa quantidade de informações que podem ser coletadas do entorno
do robô. Isso proporciona uma ampla gama de aplicações possíveis para os sistemas
robóticos quando o principal meio de percepção externo são câmeras. Além dessa importante questão, as câmeras são compactas, leves, consomem pouca energia, são facilmente
integradas ao hardware de um robô, podem ser encontradas no mercado com diferentes
preços, tais características as tornam bastante atrativas. Atualmente, até mesmo as pequenas câmeras embarcadas em celulares estão sendo utilizadas na navegação (odometria visual) de robôs, quando estes utilizam o próprio celular como processador [Aroca
CAPÍTULO 3. MAPEAMENTO VISUAL
24
& Gonçalves 2012]. Essas são características que permitem o desenvolvimento de um
grande conjunto de funcionalidades essenciais na robótica: detecção de obstáculos, rastreamento de pessoas, servovisão, etc. [Lemaire et al. 2007].
Quando aplicadas ao mapeamento robótico, o uso das câmeras traz algumas outras
vantagens: primeira, os dados são percebidos em um ângulo sólido, o que permite abordagens de mapeamento 3D. Segunda, técnicas visuais de estimativa de movimento pode
fornecer um resultado muito preciso sobre os movimentos do robô. E por fim, características muito estáveis podem ser detectadas em diferentes imagens, o que dá a possibilidade
de derivar algoritmos que permitam o associação de dados (matching) entre elas mesmo
com alterações significativas do ponto de vista [Lemaire et al. 2007].
Um grande desafio relacionado aos sistemas de visão artificial está em como tirar
proveito dos sensores visuais com algoritmos confiáveis e eficazes que possam extrair as
informações necessárias para a resolução de problemas [Santana 2011]. Muitas pesquisas
mais antigas ressaltam a dificuldade de que os sistemas baseados em câmeras necessitam
de grandes recursos de processamento para se obter resultados em tempo real. Porém,
com os grandes avanços alcançados no desenvolvimento de processadores mais rápidos,
se percebe um aumento significativo de pesquisas recentes que utilizam os sistemas visuais como fontes de informações sensoriais. O rápido aumento no poder de processamento dos computadores faz com que seja possível lidar com uma maior quantidade
de informações, permitindo melhor compreensão do ambiente, facilitando a tomada de
decisões por parte dos robôs.
3.2
Configurações de Câmeras mais Utilizadas no Mapeamento Visual
Os principais sistemas de percepção visual utilizados em robôs móveis são: visão
monocular e visão estéreo.
3.2.1 Visão Monocular
Os sistemas de visão monocular utilizam apenas uma câmera para coletar informações
do entorno do robô (Figura 3.1). Civera et al. (2008) definem um sistema monocular
como um sensor projetivo cujo objetivo é medir o deslocamento das características em
uma imagem. Com isso, dada uma sequência de imagens de uma cena, tomadas a partir
de uma câmera em movimento, é possível computar a estrutura da cena e o movimento da
câmera a menos de um fator de escala. Geralmente as informações 3D são representadas
por um conjunto esparso de pontos de interesses ou características detectadas. Ou seja, o
uso de sistemas monoculares é mais relevante na construção de mapas de características.
Um dos principais desafios no uso desses sistemas está em dar, inicialmente, estimativas corretas de informações tridimensionais de objetos contando apenas com imagens
[Piniés et al. 2010]. O problema está em determinar um fator de escala para definir a
localização correta dos objetos detectados no mundo. Algumas soluções foram propostas
para lidar com essa problemática. Uma das mais expressivas foi proposta por Civera et al.
3.2. CONFIGURAÇÕES DE CÂMERAS MAIS UTILIZADAS NO MAPEAMENTO VISUAL25
Figura 3.1: Câmeras monoculares.
(2008). Os autores apresentaram uma solução baseada em uma parametrização da profundidade inversa para representar pontos detectados. Essa informação pode ser incorporada
na estimativa dos dados de uma característica, a partir da primeira imagem capturada
onde a característica é observada. Para calcular as estimativas os autores utilizaram o
FKE (Filtro de Kalman Estendido).
3.2.2 Visão Estéreo
Visão estéreo se refere à habilidade de inferir informações de estruturas 3D e distância
à uma cena a partir de duas ou mais imagens tomadas de diferentes pontos de vista. Os
sistemas de visão estéreo se baseiam no sistema visual humano. A diferença na localização da retina esquerda e direita é usada pelo cérebro para reconstruir uma representação
3D do que se vê [Trucco & Verri 1998]. Tendo isso como inspiração, foram desenvolvidos os sistemas de visão estéreo artificiais, os quais podem conter duas ou mais câmeras
para adquirir informações de estruturas 3D. Alguns sistemas dispõem de várias câmeras
arranjadas estrategicamente para capturar imagens em um ângulo de 360 graus, dando
uma visão esférica do ambiente, tais câmeras são chamadas de omnidirecionais. A Figura
3.2 abaixo, ilustra alguns desses sistemas de câmeras estéreo.
(a)
(b)
Figura 3.2: Câmeras estereoscópicas: (a) câmeras binocular e trinocular; (b) câmera
ominidirecional.
CAPÍTULO 3. MAPEAMENTO VISUAL
26
Um sistema de visão estéreo provê, de forma direta, medidas de distâncias aos objetos
capturados em ambas as imagens. Essa é considerada a principal vantagem desse sistema
em relação à visão monocular. O presente trabalho faz uso de um sistema de visão estéreo
de baixo custo com duas câmeras para o mapeamento de ambientes. Por esse motivo,
a seguir, será explanado todo o processo de visão estéreo responsável pela inferência de
informações 3D de estruturas presentes em um ambiente.
3.3
Estereoscopia
Para inferir informações de estruturas 3D a partir de duas imagens tomadas de locais
distintos, usando ferramentas computacionais, é preciso considerar a resolução de dois
problemas principais. O primeiro é conhecido como problema de correspondência, que
consiste em determinar quais pontos capturados na câmera esquerda estão sendo vistos
também pela câmera direita. O segundo está relacionado com a reconstrução da cena
vista pelas câmeras, dados os pontos identificados no problema anterior e a geometria do
sistema estéreo [Trucco & Verri 1998].
Esse processo segue alguns passos importantes: primeiro, calibração das câmeras,
o qual possibilita estimar parâmetros internos das câmeras e parâmetros relativos entre
câmeras; segundo, retirada de distorções das imagens, efeitos esses que são introduzidos
por defeitos de fabricação das lentes; terceiro, retificação das imagens, alinhando-se os
planos das imagens e os eixos óticos; e quarto, estimação do mapa de disparidade ou
imagem de profundidade. Para entender melhor esses problemas é interessante analisar
primeiro a geometria estéreo, usando o modelo de câmera pinhole.
3.3.1 Geometria Estéreo e Reconstrução 3D
Com o auxílio da Figura 3.3 é possível analisar geometricamente como se dá todo o
processo de calculo de coordenadas 3D de um objeto a partir de imagens 2D capturadas
por duas câmeras. Formulando matematicamente, considere o ponto P no mundo de coordenadas desconhecidas, o qual é detectado pelas câmeras esquerda e direita de um sistema
estéreo. Para simplificação do problema, deve-se ponderar que as câmeras possuem os
planos de imagem coplanares e eixos óticos paralelos. Na Figura 3.3, O′ e O representam
os centros de projeção das câmeras, f é a distância focal das câmeras (distância entre o
centro de projeção e o plano de imagem), a distância b entre os centros de projeção O′ e
O, é chamada de linha de base. f e b são parâmetros do sistema estéreo que podem ser
inferidos por uma calibração estéreo.
As coordenadas (xol , ylo ) e (xor , yro ) representam os pontos pelos quais os eixos óticos
intersectam os planos de imagens em ambas as câmeras. O ponto P é representado pelos
pixels de coordenadas (xl , yl ) e (xr , yr ) nos planos de imagem, ou seja, (xl , yl ) e (xr , yr )
são as projeções do ponto P na imagem esquerda e direita respectivamente. Como os
planos de imagem são coplanares e os eixo óticos paralelos, então podemos assumir que
yl = yr . E zc é a distância ou profundidade do ponto P em relação ao sistema estéreo.
3.3. ESTEREOSCOPIA
27
oó
ptic
o
e ix
oó
ptic
o
P
e ix
zc
plano d
a imag
em
(x0l , y0l )
(xl , yl )
(xr , yr )
f
O’
b
(x0r , y0r )
f
O
Figura 3.3: Geometria estéreo.
O método pelo qual a posição do ponto P no espaço tridimensional é determinada é
chamado de triangulação, o qual considera a intersecção dos raios definidos pelos centros
de projeção (O′ e O) e as coordenadas de imagem do ponto P ((xl , yl ) e (xr , yr )). Porém,
a triangulação depende da solução do problema de correspondência, ou seja, (xl , yl ) e
(xr , yr ) devem classificados por algum método como pontos correspondentes. Posteriormente, serão apresentados alguns métodos utilizados para encontrar a correspondência
entre pontos de ambos os planos de imagens.
A profundidade zc pode ser encontrada por semelhança de triângulos, como segue na
Equação 3.1.
b
b − (xl − xr )
=
zc − f
zc
(3.1)
Desenvolvendo a Equação 3.1 chega-se a Equação 3.2.
zc =
b. f
(xl − xr )
(3.2)
Essa equação mostra que a profundidade zc é inversamente proporcional à diferença ou
disparidade entre as duas vistas, assim a disparidade pode ser definida matematicamente
por d = xl − xr . Modificando a Equação 3.2 tem-se a Equação 3.3.
zc =
b. f
d
(3.3)
CAPÍTULO 3. MAPEAMENTO VISUAL
28
Com essa expressão tem-se a definição de uma das coordenadas do ponto P em relação
ao referencial da câmera estéreo, o qual será descrito por Pc . A disparidade é dada pela
solução do problema de correspondência, a qual deve apresentar como resultado final
uma imagem bidimensional, também chamada de mapa de disparidade, cujos valores dos
pixels d(x, y) descrevem a diferença entre duas imagens [Andert 2009]. Usando o mesmo
raciocínio de triangulação e as informações do mapa de disparidade, pode-se encontrar as
coordenadas xc e yc do ponto Pc = (xc , yc , zc )T . As Equações 3.4 e 3.5 expressam essas
relações.
xc = zc .
(x − x0 )
f
(3.4)
yc = zc .
(y − y0 )
f
(3.5)
Nas equações acima (x, y) e (x0 , y0 ) são coordenadas de uma das imagens (esqueda ou
direita). Na prática se limita o valor assumindo valores máximo e mínimo para a distância
zcmin < zc < zcmax , com zcmin > 0 [Andert 2009]. Com as coordenadas do ponto Pc =
(xc , yc , zc )T , a matrix de orientação R e o vetor de translação T que mapeiam o sistema de
câmera em coordenadas de mundo, pode-se, agora, calcular as coordenadas de P.
P = RT .Pc + T
(3.6)
Assim, têm-se as coordenadas do ponto P, antes desconhecida, calculadas através dos
artifícios da geometria estéreo. Nesse ponto, a etapa de reconstrução 3D é concluída.
3.3.2 Disparidade Estéreo
O termo disparidade foi relacionado primeiro ao sistema preceptivo visual humano
para descrever a diferença entre cenas correspondentes enxergadas pelo olho esquerdo e
direito [Sharstein & Szeliski 2002]. Trazendo essa definição para o campo da visão computacional, a disparidade pode ser entendida como a diferença entre as coordenadas de
imagem de um ponto no mundo, capturado pelas câmeras esquerda e direita de um sistema estéreo. Alguns pesquisadores têm definido a disparidade como uma transformação
projetiva tridimensional do espaço 3D [Sharstein & Szeliski 2002].
Neste trabalho, considera-se o uso de um sistema estéreo cujos planos de imagens são
coplanares e os eixos óticos estão alinhados. Essa restrição limita a dedução da disparidade para apenas as coordenadas x das imagens (d = xl − xr ), podendo ser chamada de
disparidade horizontal. Essa prerrogativa facilita a busca e a identificação dos pixels correspondentes (xl , yl ) e (xr , yr ), fazendo com que seja realizada uma redução no espaço de
busca de 2D para 1D, que será apenas uma linha horizontal, restrita ao eixo x dos planos
de imagem esquerdo e direito. Essa consideração é conhecida por restrição epipolar.
Para encontrar os pixels, (xl , yl ) e (xr , yr ), correspondentes a projeção do ponto P em
ambos os planos de imagens, e gerar um mapa de disparidade existem vários algoritmos.
Sharstein & Szeliski (2002) elaboraram um apanhado geral de parte desses algoritmos,
fazendo uma análise comparativa entre eles. Em seu trabalho, Hong & Chen (2004)
3.3. ESTEREOSCOPIA
29
classificaram os algoritmos de correspondência estéreo em duas categorias: algoritmos
locais (baseados no conceito de janelas) e algoritmos globais (baseados em técnicas de
minimização).
Algoritmos Locais
Os algoritmos locais, também chamados de algoritmos de janela variável de pixel (ou
block-macthing), procuram fazer a associação de pixels entre duas imagens de maneira
rápida e com redução de ruído. No momento de realizar uma comparação entre imagens,
não só o valor do pixel buscado é levado em consideração e sim, uma janela de pixels
vizinhos. A premissa por trás dessa abordagem é que a disparidade entre pixels da mesma
janela é aproximadamente igual, isso favorece a redução de ambiguidades na associação
dos pixels entre duas imagens. Basicamente este método gera o mapa de disparidade
seguindo três passos principais: o primeiro passo tem como função a normalização do
brilho das imagens e o realce de textura. O segundo passo, é a busca de pixels correspondentes considerando a restrição epipolar. Aqui, utiliza-se a soma das diferenças absolutas
entre janelas de mesmo tamanho em ambas as imagens para se encontrar a correspondência. O terceiro passo consiste na eliminação de falsas correspondências. Finalmente, após
a execução desses passos a disparidade é calculada para os pixels com valores de disparidade válidos [Bradski & Kaehler 2008]. Essa abordagem gera resultados razoáveis em
tempo-real. A Figura 3.4 apresenta um resultado de um mapa de disparidade gerado pelo
algoritmo de janela variável.
(a)
(b)
Figura 3.4: Mapa de disparidade gerado pelo algoritmo de janela variável; (a) imagem
original; (b) mapa de disparidade.
Algoritmos Globais
Dentre os algoritmos globais que utilizam a minimização para a geração de um mapa
de disparidade se destacam os algoritmos que aplicam princípios de programação dinâmica
e algoritmos baseados em grafos. Apreciando o uso da programação dinâmica, os algoritmos empregados se baseiam no princípio de dividir para conquistar. Neste princípio
um grande problema é dividido em subproblemas, que são solucionados de maneira independentes e suas soluções são organizadas para formar a solução do problema original.
CAPÍTULO 3. MAPEAMENTO VISUAL
30
Analisando na visão estéreo, uma imagem deve ser dividida em linhas (subproblemas) e
soluciona-se a associação para cada uma delas separadamente, considerando a aplicação
de técnicas de minimização de custos em torno da busca do pixel de maior credibilidade
para a associação.
Os algoritmos globais baseados em grafos, também conhecidos na literatura como
graph-cuts, fundamentam-se no conceito de energia de pixels. Nessa abordagem um
mapa de disparidade é calculado previamente para depois ser aprimorado. Com isso é
calculado um valor de energia a qual deve ser globalmente minimizada. A estratégia é
procurar minimizar a energia do mapa de disparidade construindo um grafo, no qual cada
vértice representa um pixel do mapa e cada aresta possui o valor de energia associado
aos pixels conectados a ela. São criadas tabelas com possíveis valores de disparidade
associados a cada vértice e então, é executado um processo de escolha de um melhor
valor de disparidade para todos os pixels da imagem, considerando a minimização de
energia. O graph-cuts apresenta resultados significantes quando comparados a outras
técnicas, em contrapartida possui um grande custo computacional atrelado à geração dos
seus resultados [Hong & Chen 2004]. A Figura 3.5 ilustra um resultado de um mapa de
disparidade gerado pelo algoritmos graph-cuts.
(a)
(b)
Figura 3.5: Mapa de disparidade gerado pelo algoritmo de graph-cuts; (a) imagem original; (b) mapa de disparidade.
Melhorias podem ser realizadas para que o uso dessa técnica possa ter viabilidade em
tarefas de tempo real. Alguns desses avanços foram propostos no trabalho de [Zureiki
et al. 2007]. Diante dos estudos feitos e resultados analisados a partir de alguns testes
realizados com as duas abordagens apresentadas, foi decidido trabalhar nesta pesquisa
com o algoritmo baseado em graph-cuts por apresentar um mapa de disparidade mais
rico em detalhes, o que é mais interessante para o mapeamento de ambientes.
3.4
Trabalhos Relacionados
Nesta seção serão apresentados alguns trabalhos científicos que lidam com o mapeamento robótico baseado em sistemas de visão monocular e estéreo. Aqui serão levantadas
as diferentes estratégias de escolha de informações relevantes para a construção das distintas representações de mapas.
3.4. TRABALHOS RELACIONADOS
31
Os primeiros trabalhos sobre mapeamento robótico utilizando visão foram apresentados na década de 1980 [Moravec 1988, de Saint Vincent 1987]. Essas primeiras evoluções
foram alcançadas com estudos baseados em visão estéreo. Nesta época surgiram as
primeiras pesquisas relacionadas a representação em grade de ocupação e dentro desse
contexto Moravec (1988) propôs um sistema de mapeamento composto por um conjunto
de sonares e um sistema de visão estéreo com duas câmeras. As informações de ambos
os tipos de sensores eram fundidas para construir o mapa de ocupação.
As pesquisas baseadas em visão monocular são mais contemporâneas, elas começaram
a ser desenvolvidas a partir de 2002, quando as primeiras investigações com resultados
significativos foram publicados por Davison [Davison 2002, Davison 2003]. Anos mais
tarde, em um trabalho mais completo, o mesmo pesquisador juntamente com colegas
formalizaram a proposta aplicando-a na localização e mapeamento simultâneos. Eles denominaram a técnica de MonoSLAM [Davison et al. 2007]. Esses trabalhos focaram no
mapeamento em tempo real, algo complexo quando se tem o processamento de grande
quantidade de informações envolvidas.
As soluções robóticas para mapeamento de ambientes com câmeras estéreo se estende desde o uso de sistemas com duas câmeras até o uso de sistemas várias câmeras.
Por exemplo, Andert (2009) utilizou um sistema de visão estéreo de duas câmeras embarcado em um helicóptero para construir um mapa 3D, cujo objetivo final do mapa era a
navegação do aeromodelo. Já no trabalho apresentado por Ogawa et al. (2007), um robô
móvel terrestre equipado com uma câmera estéreo trinocular foi utilizado para construir
um mapa 3D de pontos notáveis do seu ambiente de navegação. Em um trabalho mais recente, Gallelos & Rives (2010) implementaram um mapeamento robótico 3D, desta feita
fundindo as informações de um sistema de câmeras omnidirecional com um laser 2D. O
sensor laser foi utilizado por fornecer dados mais exatos sobre a profundidade de objetos
e obstáculos.
As informações utilizadas para a construção de mapas robóticos com sistemas de visão
monocular ou estéreo podem ser escolhidas de acordo com as particularidades do ambiente de trabalho do robô, de modo a facilitar a detecção das características mais aparentes,
ou podem ser ainda abstraídas para que mapas mais genéricos sejam construídos. Dentro do primeiro raciocínio, existem trabalhos que se concentram na construção de mapas
de características fundamentados em pontos, retas e planos. No âmbito dos sistemas
de visão monocular, Wu et al. (2010) propuseram em seu trabalho uma abordagem de
seleção de pontos notáveis baseada no algoritmo SIFT (Scale-Invariant Feature Transform). Os autores apresentam uma maneira de reduzir a quantidade de pontos-chaves na
realização do mapeamento, consequentemente diminuindo o tempo de convergência do
mapeamento. Já na esfera da visão estéreo Davison (2002), por exemplo, implementaram
um mapeamento com um sistema estéreo onde as características armazenadas eram cantos detectados pelo detector de cantos de Harris. Em outro trabalho [Ogawa et al. 2007],
foi empregado o algoritmo SIFT para detectar as características relevantes do ambiente
capturadas por um sistema estéreo.
Soluções que utilizam a extração de linhas para a construção de mapas com o uso de
sistemas de visão são facilmente encontradas na literatura. Em geral, estas técnicas estão
atreladas ao uso da transformada de Hough para detectar as retas nas imagens. Santana
32
CAPÍTULO 3. MAPEAMENTO VISUAL
& Medeiros (2011) propuseram um sistema de visão monocular para detectar linhas no
plano do chão de pisos de ambientes internos e externos, construindo, posteriormente,
um mapa para armazenamento dessas formas geométricas. Quando se trata de sistemas
estéreo, Chang et al. (2010) apresentaram o mapeamento de linhas verticais detectadas
pelo sistema de visão. Neste caso, informações 3D a respeito das linhas são armazenadas
em um mapa de características. Gallelos & Rives (2010) implementaram a mesma ideia,
porém eles contaram com um robô munido de uma composição de sensores: uma câmera
omnidirecional e um laser, fundindo as informações de ambos.
Na detecção de plano, o uso de sistemas monoculares está na maioria das vezes atrelado a fusão com outros sensores [Servant et al. 2010]. Porém, alguns pesquisadores
utilizam apenas a câmera como fonte de informação [Aires & Medeiros 2010]. O uso de
visão estéreo na detecção de plano também pode ser verificado na literatura. Murarka &
Kuipers (2009), por exemplo, implementaram em seu trabalho uma forma de detecção de
planos e regiões possíveis de serem navegadas por um robô móvel.
Como mencionado anteriormente, os sistemas de visão estéreo podem ser utilizados
na construção de mapas robóticos mais genéricos, isto é, sem a necessidade de se deter a
detecção de um tipo de características particular do ambiente. Grande parte dos trabalhos
que levam em conta essa solução adota o mapeamento em grade de ocupação [Agrawa
et al. 2007] [Andert 2009]. Esses e outros trabalhos serão mais bem explorados em um
capítulo posterior.
Além dessa abrangência de possibilidades na representação de mapas, os sistemas
de visão monocular e estéreo podem ser aplicados na construção de mapas de diferentes
ambientes: internos [Gallelos & Rives 2010, Chang et al. 2010, Santana & Medeiros
2011] e externos [Agrawa et al. 2007, Marks et al. 2009, Andert 2009].
Capítulo 4
Grade de Ocupação e Mapas de
Elevação
Neste capítulo serão apresentadas de maneira mais detalhada a representação em Grade
de Ocupação e os Mapas de Elevação, que formam o fundamento do método de mapeamento proposto. O foco do capítulo está em como se dá a construção, atualização
e manutenção desses tipos de mapas. Apresentaremos o formalismo matemático probabilístico que rege a identificação do estado de ocupação das áreas do ambiente mapeado
e calcula uma estimativa da elevação desses locais, considerando o tratamento dado às
incertezas sensoriais presentes nos dados de medição. Para cada tipo de representação
serão abordados alguns trabalhos relacionados à construção, à aplicações e melhorias
propostas para essas representações.
4.1 Grade de Ocupação
A abordagem de mapeamento em Grade de Ocupação se apresenta como uma representação estocástica das informações espaciais de um ambiente. Cada célula da grade
mantém uma estimativa probabilística do estado de ocupação do lugar por ela representado, que pode ser livre, ocupada ou ainda desconhecida ou não mapeada [Elfes 1989]. A
função estimativa probabilística fornece valores dentro do intervalo [0,1], onde 0 significa
célula livre e 1 representa uma célula ocupada.
A construção da grade envolve a determinação dessas estimativas de maneira iterativa,
levando-se em conta o conhecimento da pose do robô em cada instante de tempo. Neste
ponto, considera-se a hipótese de que as células são estatisticamente independentes, isso
favorece a construção eficiente do mapa em Grade de Ocupação. Embora esta não seja
uma suposição totalmente verdadeira quando se trata, por exemplo, de células que representam um mesmo objeto físico, isso não afeta de forma significativa a precisão de um
mapa. Portanto, a estimativa de um mapa M pode ser fatorada no produto das probabilidades de cada célula mn , como mostra matematicamente a Equação 4.1. Por esta equação,
percebe-se que a inferência do mapa depende do histórico de todas as poses do robô até o
instante atual, x0:t , e de todas as leituras sensoriais realizadas em cada pose, z0:t .
34
CAPÍTULO 4. GRADE DE OCUPAÇÃO E MAPAS DE ELEVAÇÃO
p(M|x0:t , z0:t ) = ∏ p(mn |x0:t , z0,t )
(4.1)
n
As estimativas dos estados das células p(mn |x0:t , z0,t ) são obtidas através da interpretação dos dados dos sensores, empregando modelos probabilísticos, que tratam de
forma adequada as incertezas nas informações espaciais obtidas. Um procedimento de
estimação Bayesiano permite a atualização incremental da Grade de Ocupação a partir
de novas leituras obtidas de múltiplos sensores, desde vários os pontos de vista. Então,
aplicando a Regra de Bayes à p(mn |x0:t , z0,t ), tem-se:
p(mn |x0:t , z0,t ) =
p(zt |mn , x0:t , z0,t−1 ).p(mn |x0:t , z0,t−1 )
p(zt |x0:t , z0:t−1 )
(4.2)
p(zt |mn , xt ).p(mn |x0:t , z0,t−1 )
p(zt |x0:t , z0:t−1 )
(4.3)
Assumindo-se que zt é independente de x0:t e de z0:t−1 , dado que o valor de ocupação de
mn é conhecido, a Equação 4.2 pode ser simplificada (Equação 4.3).
p(mn |x0:t , z0,t ) =
Aplicando a Regra de Bayes a p(zt |mn , xt ) tem-se a seguinte equação,
p(zt |mn , xt ) =
p(mn |zt , xt ).p(zt |xt )
p(mn |xt )
(4.4)
Substituindo a Equação 4.4 na Equação 4.3 e assumindo que xt não provê qualquer informação a respeito de mn se não há medições sensoriais zt , tem-se,
p(mn |x0:t , z0:t ) =
p(mn |zt , xt ).p(zt |xt ).p(mn |x0:t−1 , z0:t−1 )
p(mn ).p(zt |x0:t , z0:t−1 )
(4.5)
Assumindo-se ainda que mn é uma variável binária, a Equação 4.6 pôde ser derivada
usando-se o mesmo raciocínio.
p(¬mn |zt , xt ).p(zt |xt ).p(¬mn |x0:t−1 , z0:t−1 )
p(¬mn ).p(zt |x0:t , z0:t−1 )
(4.6)
p(mn |x0:t , z0:t )
p(mn |zt , xt ).p(¬mn ).p(mn |x0:t−1 , z0:t−1 )
=
p(¬mn |x0:t , z0:t ) p(¬mn |zt , xt ).p(mn ).p(¬mn |x0:t−1 , z0:t−1 )
(4.7)
p(¬mn |x0:t , z0:t ) =
Dividindo a Equação 4.5 pela Equação 4.6 e aplicando as devidas manipulações algébricas, tem-se a seguinte expressão,
Sabendo-se que p(¬A) = 1− p(A), pode-se manipular ainda mais a Equação 4.7, chegandose a Equação 4.8.
p(mn |zt , xt ) 1 − p(mn ) p(mn |x0:t−1 , z0:t−1 )
p(mn |x0:t , z0:t )
=
.
.
1 − p(mn |x0:t , z0:t ) 1 − p(mn |zt , xt ) p(mn ) 1 − p(mn |x0:t−1 , z0:t−1 )
(4.8)
Por questões de inconsistências numéricas, pode-se representar a Equação 4.8 em sua
4.1. GRADE DE OCUPAÇÃO
35
forma logarítmica (Equação 4.9).
log
p(mn |x0:t , z0:t )
p(mn |zt , xt )
= log
−
1 − p(mn |x0:t , z0:t )
1 − p(mn |zt , xt )
p(mn |x0:t−1 , z0:t−1 )
1 − p(mn )
+ log
− log
p(mn )
1 − p(mn |x0:t−1 , z0:t−1 )
(4.9)
Para simplificar, considere,
log
p(mn |x0:t , z0:t )
= ℓtn
1 − p(mn |x0:t , z0:t )
Realizando as devidas substituições, a Equação 4.9 se tranforma na Equação 4.10, pela
qual se dá a atualização do valor de ocupação das células.
ℓtn = log
p(mn |xt , zt )
1 − p(mn )
− log
+ ℓt−1
n
1 − p(mn |xt , zt )
p(mn )
(4.10)
Onde ℓt−1
computa a ocupação da célula mn calculada anteriormente no tempo t − 1,
n
p(mn ) é uma constante que inicializa a grade com uma probabilidade de ocupação, que
pode ser atribuído um valor de acordo com a densidade dos obstáculos no ambiente,
porém, no geral se utiliza p(mn ) = 0.5. A parte mais importante da Equação 4.10 é a
probabilidade p(mn |xt , zt ), a qual é chamada de modelo inverso do sensor. No próximo
capítulo o modelo proposto neste trabalho será devidamente apresentado, considerando
todo o formalismo estocástico necessário para um bom tratamento de informações ruidosas, que é o caso das informações oriundas de sensores. A Equação 4.10 realiza iterativamente a atualização do valor de ocupação de cada célula mn pertencente ao campo de
visão do sensor, a cada nova leitura sensorial.
O valor da probabilidade de ocupação de uma célula mn pode ser recuperado facilmente através da Equação 4.11.
p(mn |x0:t , z0:t ) = 1 −
1
1 + exp(ℓtn )
(4.11)
4.1.1 Modelo Probabilístico do Sensor
O modelo probabilístico do sensor deve refletir o seu comportamento, considerando
suas incertezas. Na literatura é comum encontrar a nomenclatura modelo inverso do sensor [Thrun et al. 2005, Hahnel 2004, Stachniss 2006]. Esse modelo deve retornar o valor
de p(mn |xt , zt ), o qual fará parte da função de atualização da probabilidade de ocupação
do mapa (Equação 4.10).
Os modelos baseados nas funções gaussianas se mostram interessantes quando se está
tratando de sensores ruidosos. As técnicas Gaussianas compartilham a ideia de que a
densidade de probabilidade de que algo aconteça é representada por uma distribuição
normal. Essa distribuição foi estudada pela primeira vez no século XVIII, quando foi
observado que padrões de erros e medidas seguiam uma distribuição simétrica em forma
CAPÍTULO 4. GRADE DE OCUPAÇÃO E MAPAS DE ELEVAÇÃO
36
de sino [Hines et al. 2006]. A Equação 4.12 expõe a função de densidade de probabilidade
de uma Distribuição Normal unidimensional.
1
1 (x − µ)2
p(x) = √
(4.12)
. exp −
2 σ2
2πσ
Na equação acima, x é a variável analisada (também chamada de variável aleatória) com
média µ e variância σ2 . Frequentemente, se observa na literatura essa expressão em sua
forma abreviada N (x; µ, σ2 ), a qual especifica a variável aleatória, sua média e sua variância. A Figura 4.1 esboça graficamente uma distribuição normal de média µ = 3 e variância
σ2 = 0.15.
2
Distribuição Normal − µ = 3, σ = 0.15
0.35
0.3
0.25
P(x)
0.2
0.15
0.1
0.05
0
2
2.2
2.4
2.6
2.8
3
3.2
3.4
3.6
3.8
4
x
Figura 4.1: Gráfico da Distribuição Normal.
Em geral, os modelos probabilísticos Gaussianos para sensores que medem distância
caracterizam três regiões principais: 1) região de baixa probabilidade de ocupação ou
região possivelmente livre; 2) região possivelmente ocupada; 3) região fora do alcance do
sensor. A Figura 4.2 ilustra resultados típicos de um modelo unidimensional gaussiano
de sensor baseado na Equação 4.12, derivados de medições de distância de um sensor.
As regiões de menor valor de probabilidade representam áreas possivelmente livres, as
áreas de pico representam os locais possivelmente ocupados por obstáculos e as regiões
com valor de probabilidade 0.5 representam áreas fora do alcance do campo de visão do
sensor, isto é, áreas não mapeadas.
Porém, essa modelagem pode ser mais sofisticada com o uso de uma Distribuição
Normal bivariada, que estende a derivação de um modelo a duas dimensões espaciais
(Equação 4.13).
1
1 (x1 − µ1 )2 (x2 − µ2 )2
p(x1 , x2 ) =
. exp −
+
(4.13)
2πσ1 σ2
2
σ21
σ22
Essa distribuição é interessante quando o sensor se caracteriza por ter incertezas em mais
de uma variável. Por exemplo, os sonares apresentam incertezas tanto na medição de
distâncias como no seu ângulo de orientação, logo, os sonares podem ser modelados por
4.1. GRADE DE OCUPAÇÃO
37
Modelo Gaussiano 1D de sensor
0.9
0.8
0.7
P(mn|zt, xt)
0.6
0.5
0.4
0.3
0.2
0.1
0
10
15
20
25
30
35
40
45
50
Distância medida(m)
Figura 4.2: Modelo de medição sensorial. Valores de ocupação para medições de 20m,
30m e 40m. O valor de ocupação se dá com as médias (medidas) e variâncias (erros) das
medições.
uma distribuição normal bivariada, onde as variáveis de análise são à distância e o ângulo
de orientação. A Figura 4.3 esboça um gráfico típico da modelagem de um sensor de
distância com incertezas na medida de profundidade e no ângulo de orientação.
Modelo Gaussiano 2D de sensor
0.52
P(mn|zt, xt)
0.51
0.5
0.49
0.48
0
0
10
10
20
20
30
30
40
40
50
50
60
60
70
70
80
80
Figura 4.3: Modelagem Gaussiana bidimensional de um sensor.
Essas são as funções probabilísticas mais comuns na modelagem de sensores no mapeamento em Grade de Ocupação. No próximo capítulo, será exposto o modelo proposto
neste trabalho, o qual tem como objetivo dar o tratamento adequado aos ruídos e incertezas provenientes das imagens capturadas pelo sistema de câmeras estéreo.
4.1.2 Algoritmo de Mapeamento em Grade de Ocupação
Em forma de procedimento o mapeamento em Grade de Ocupação pode ser arranjado
de acordo com o Algoritmo 1. O pseudocódigo apresentado está baseado no exemplo
exposto por Thrun et al. (2005).
CAPÍTULO 4. GRADE DE OCUPAÇÃO E MAPAS DE ELEVAÇÃO
38
Algoritmo 1: mapeamento_em_grade_de_ocupação({ℓt−1
n },xt ,zt )
Entrada: {ℓt−1
n }, xt , zt .
t
Saída: {ℓn }.
para cada célula mn pertence ao mapa faça
se mn está dentro do campo de visão do sensor então
calcule p(mn |zt , xt ) (modelo inverso do sensor);
p(mn |xt ,zt )
n)
t−1
− log 1−p(m
atualize o valor da célula mn com ℓtn = log 1−p(m
p(mn ) + ℓn ;
n |xt ,zt )
senão
ℓtn = ℓt−1
n ;
fim se
fim para
O algoritmo apresenta como dados de entrada {ℓt−1
n }, que são os valores de ocupação
de todas as células calculados previamente, xt , que é vetor com a posição e orientação
do robô e zt , que é o resultado da medição sensorial; e como saída {ℓtn } que representa
os valores de ocupação atualizados. Existe um laço que varre todas as células do mapa e
testa se estão no campo visual do sensor do robô. Caso a célula esteja sendo alcançada
pelo sensor o seu valor de ocupação é atualizado de acordo com o modelo adotado para o
sensor através da Equação 4.10. Senão, permanece com o valor de ocupação previamente
calculado no passo t − 1.
Não há necessidade de varrer todo o mapa em grade para verificar células dentro
ou fora do campo de visão do sensor. Na prática, se faz uma heurística simples para
que somente as células alcançadas pelo sensor sejam percorridas e atualizadas, evitando
assim, maior tempo de processamento.
4.1.3 Trabalhos Relacionados
Uma importante característica do mapeamento em Grade de Ocupação é que ele pode
ser realizado por robôs com distintos sensores. A construção de um mapa em grade
não se restringe a um determinado tipo de sensor. Investigando os sensores mais citados
nesse trabalho (sonar, lasers e câmeras), é fácil encontrar na literatura inúmeras referências que mensionam a construção de mapas em grade com esses dispositivos. Como já
declarado em um capítulo anterior, os primeiros trabalhos em Grade de Ocupação surgiram na década de 1980 [Elfes 1987][Moravec 1988][Elfes 1989]. Esses primeiros estudos
foram elaborados com robôs equipados com sonares. Ainda hoje esses sensores são utilizados nesse tipo mapeamento, apesar de eles apresentarem significantes falhas em suas
medições. Gupta et al. (2007), por exemplo, utilizaram o mapeamento em Grade de Ocupação a partir de informações coletadas por sonares para mapear ambientes dinâmicos.
Uma rede neural é aplicada para que as mudanças percebidas no ambiente sejam tratadas
de forma adequada e expressas corretamente no mapa em grade.
4.1. GRADE DE OCUPAÇÃO
39
Porém, os sonares estão desuso por conta de suas deficiências, pelo barateamento de
sensores mais precisos e pelo desenvolvimento de novas alternativas para a percepção
de ambientes. Outra opção para mapeamento em grade é o uso de lasers. Esses são
sensores precisos, de longo alcance e que podem fornecer dados suficientes para se alcançar a construção de mapas bem detalhados. Alguns trabalhos com laser podem ser
citados. Konrad et al. (2011), por exemplo, implementaram um sistema de mapeamento
em Grade de Ocupação de grandes áreas através um veículo equipado com um laser. Já
Shi et al. (2010), apresentaram uma técnica de mapeamento semântico a partir de uma
Grade de Ocupação criada com dados captados por um laser. Os autores apresentaram o
mapa semântico em grade chamado de Semantic Grid Map, cujo o objetivo é facilitar a
classificação de ambientes em corredores ou salas (escritórios).
O uso de câmeras na construção de mapas em Grade de Ocupação é bem frequente
nas pesquisas mais atuais. Esses dispositivos se destacam pelo seu baixo custo e pela
grande quantidade de informações que podem ser aproveitadas a partir de uma coleta de
dados. Desde sistemas monoculares até sistemas omnidirecionais podem ser aplicados na
montagem de mapas em Grade de Ocupação. Choi & Oh (2006), por exemplo, aplicaram
a técnica de sonar visual às imagens capturadas por um sistema de visão monocular e
fizeram a associação desses dados de distância através de um algoritmo baseado na técnica
chamada Iterative Closest Point (ICP), para produzir um mapa em Grade de Ocupação.
Em seu trabalho de doutorado, Santana (2011) utilizou um robô equipado com uma
única câmera na construção de um mapa híbrido de características e Grade de Ocupação.
Enquanto um procedimento de localização e mapeamento simultâneos está sendo executado sobre um mapa de características, uma estrutura em Grade de Ocupação 2D foi
construída em paralelo a partir de informações de imagens segmentadas. De acordo com
o autor, o mapa em grade serve para realização de um planejamento de caminhos com
desvio de obstáculos de forma mais direta.
Quando se trata de sistemas de visão estéreo em mapeamento em Grade de Ocupação,
deve-se voltar no tempo e mencionar o trabalho de Moravec (1996). Este foi o primeiro
trabalho em Grade de Ocupação com visão estéreo. Além disso, Moravec (1996) também
introduziu a ideia da Grade de Ocupação tridimensional chamada no trabalho de Grade de
Evidência (Evidence Grid), por ser baseada na Teoria da Evidência de Dempster-Shafer,
diferente da abordagem Bayesiana proposta por Elfes (1989).
Vários trabalhos mais recentes que destacam o uso de sistemas de visão estéreo podem ser citados. No trabalho de Andert (2009), por exemplo, um aeromodelo munido
de um sistema estéreo foi utilizado para mapear ambientes externos em uma Grade de
Ocupação tridimensional. Este trabalho mostra com certa profundidade uma interessante
abordagem na construção de mapas em Grade de Ocupação 3D. Em outro interessante
trabalho, Gallelos & Rives (2010) implementaram o mapeamento em Grade de Ocupação
em um robô provido de um laser e uma câmera omnidirecional.
Diversas são as possibilidades de sensores utilizados no mapeamento em Grade de
Ocupação, incluindo a fusão de informações providas de distintas fontes. Uma nova e
eficiente alternativa no mapeamento em Grade de Ocupação surge com o uso do Microsoft Kinect (câmeras RGB-D), um dispositivo que combina uma câmera com sensor
infravermelho em uma única estrutura. Várias são as pesquisas que se aproveitam dessa
40
CAPÍTULO 4. GRADE DE OCUPAÇÃO E MAPAS DE ELEVAÇÃO
interessante combinação de informações para realizar o mapeamento de ambientes seja
em Grade de Ocupação ou em outras forma de representação [Georgiev et al. 2011, Pirker
et al. 2011, Einhorn et al. 2011]. Já existem bibliotecas de código livre com compatibilidade para diferentes plataformas que atraem ainda mais o uso desses dispositivos em
pesquisas na Robótica.
São inúmeras as possibilidades de aplicação dos mapas em Grade de Ocupação, aqui
foram mencionados apenas alguns exemplos, porém vários outros trabalhos podem ser
encontrados na literatura. Thrun et al. (2005) afirmaram que a principal utilidade da técnica de mapeamento em Grade de Ocupação está no pós-processamento, ou seja, no que
se pode realizar a partir do mapa resultante. Com o processo de mapeamento concluído a
Grade de Ocupação pode ser útil para várias aplicações como: planejamento de caminhos,
navegação, desvio de obstáculos, localização, entre outras.
Por exemplo, Lai e colegas [Lai et al. 2006] implementaram um método prático de
planejamento de caminhos para robôs móveis em ambientes desconhecidos. Eles utilizaram uma instância modificada do algoritmo A* sobre um mapa em Grade de Ocupação
parcialmente construído para realizar um planejamento de caminhos de forma incremental. A cada nova medição sensorial incorporada ao mapa o algoritmo busca o melhor caminho a ser seguido. Os autores apresentaram no final do trabalho inúmeros experimentos
ratificando a factibilidade do método proposto. Cherubini & Chaumette (2011) apresentaram em seu trabalho um framework para navegação e desvio de obstáculos baseado em
um sistema de fusão sensorial composto por uma câmera e um laser. A navegação consiste em seguir um caminho tomado a partir de um conjunto de imagens, enquanto que o
desvio de obstáculos é realizado com o auxílio de um mapa em grade construído a partir
do sensor laser.
No contexto do problema de localização, Dryanovski et al. (2011) apresentaram uma
abordagem para solucionar o problema do robô sequestrado. A abordagem proposta utiliza um mapa em Grade de Ocupação para representar os dados sensoriais capturados por
um sensor laser. Tal mapa é posteriormente utilizado em conjunto com outras técnicas
para inferir uma localização precisa para o robô.
Um dos grandes desafios no mapeamento em Grade de Ocupação está no mapeamento de ambientes muito grandes ou mesmo no mapeamento de ambientes com riqueza
de detalhes. Essas duas possibilidades introduzem um ponto fundamental no mapeamento
em Grade de Ocupação, que por muitas vezes é fortemente assinalado como a principal
desvantagem dessa abordagem: o custo computacional. O mapeamento de ambientes com
grandes dimensões e o mapeamento detalhado requerem um razoável poder computacional para serem construídos e processados, além de necessitarem de uma grande quantidade de memória para serem armazenados principalmente em uma representação 3D.
Diante desses problemas, ultimamente surgiram pesquisas que lidam diretamente esses
fatores para encontrar uma solução plausível.
Dryanovski e colegas [Dryanovski et al. 2011] apresentaram uma abordagem para o
mapeamento 3D usando uma Grade de Ocupação multi-volume ou MVOG (Multi-Volume
Occupancy Grid). A MVOG armazena explicitamente informações sobre a ocupação de
espaços 3D. Essa proposta supera as abordagens tradicionais probabilísticas existentes de
mapeamento 3D em termos de uso de memória, devido ao fato de que as observações
4.2. MAPAS DE ELEVAÇÃO
41
sensoriais são agrupadas em volumes verticais contínuos para economizar espaço. O
desempenho da abordagem proposta é analisado por meio de experimentos em ambientes
interiores e exteriores com um robô aéreo.
Ainda dentro das representações tridimensionais, Wurm et al. (2010) expuseram uma
abordagem para a modelagem de ambientes 3D baseados em octrees utilizando uma estimativa de ocupação probabilística denominada de OctoMap. A técnica utilizada é capaz
de representar modelos 3D completos, incluindo áreas livres e desconhecidas. A abordagem foi bem avaliada utilizando-se diferentes conjuntos de dados reais e simulados. Os
resultados demonstram que a proposta é útil para modelar os dados probabilisticamente,
enquanto, ao mesmo tempo, mantem a exigência de memória no mínimo.
Outra interessante pesquisa publicada por Einhorn et al. (2011), traz uma nova técnica
de mapeamento de ambientes que escolhe a resolução de cada célula adaptativamente pela
fusão ou divisão das células, de acordo com uma modelagem estatística apresentada pelos
pesquisadores. Os autores argumentam que essa abordagem permite uma implementação
mais genérica de mapas 2D, 3D e até de mais alta dimensão usando o mesmo algoritmo.
Com essa ideia é possível diminuir o custo computacional relativo ao armazenamento de
um mapa em grade pela fusão de células com medições idênticas.
4.2 Mapas de Elevação
A representação em grade de ocupação é uma interessante ferramenta para representar
informações sobre de ocupação de lugares de um ambiente. E pode ser utilizada também
na representação de informações tridimensionais. Desde a década de 1996 com Moravec
(1996), pouco depois do surgimento do mapeamento em grade de ocupação 2D, até anos
mais atuais, como no trabalho de Andert (2009), pesquisadores introduziram a ideia de
modelar o espaço tridimensional dos robôs em uma grade de ocupação 3D.
O mapeamento tridimensional dos ambientes foi pensado principalmente para os casos onde o terreno de navegação dos robôs não é plano, e nos casos onde é necessário que
seja realizada uma navegação precisa entre os objetos, considerando a altura deles dentro
de um ambiente. Além disso, Liu et al. (2001) apresentam duas importantes vantagens
que justificam a construção de modelos 3D. Primeira, mapas 3D facilitam a solução do
problema da associação de dados, visto que os modelos 3D são mais ricos que os 2D,
portanto apresentam menos ambiguidades. Isso facilita a identificação e distinção de lugares no processo de mapeamento. Segunda, os mapas 3D são interessantes quando o
mapeamento também for utilizado em outras atividades. Modelos 3D são muito mais
adequados para os usuários remotos interessados no interior de um edifício tais como arquitetos, equipes de resgate humanos, ou bombeiros que gostariam de se familiarizar com
um ambiente antes de entrar.
Porém, existe uma grande dificuldade no mapeamento 3D quando o objetivo é representar o ambiente em uma grade de ocupação tridimensional, principalmente ambientes
com grandes dimensões. Perceba que para isso seria necessária uma estrutura 3D onde
cada lugar do ambiente tridimensional seria representado por um cubo, também chamado
de voxel (em inglês, volumetric pixel), o que pode representar a necessidade uma de
grande quantidade de processamento e memória na construção e armazenamento desse
42
CAPÍTULO 4. GRADE DE OCUPAÇÃO E MAPAS DE ELEVAÇÃO
mapa (ver Figura 4.4). Desconsiderando qualquer tipo de otimização, uma estrutura para
armazenar a grade 3D mostrada na Figura 4.4 deveria conter pelo menos 216 elementos
(12x6x3).
3
6
12
Figura 4.4: Ilustração da representação em grade de ocupação 3D.
Para evitar essa grande demanda de recursos de processamento e memória, alguns
pesquisadores propuseram uma solução já usada no mapeamento de terrenos por imagens
de radares, os mapas de elevação ou mapas 2,5-D. Os mapas de elevação são úteis para
modelar o espaço 3D de um robô móvel, de uma maneira compacta. Esta representação
mantem uma grade bidimensional, onde cada célula armazena a altura ou elevação do
terreno no ponto mapeado [Pfaff et al. 2007] (Figura 4.5). Usando o mesmo exemplo da
Figura 4.4, uma grade de elevação para representar a mesma situação deveria conter pelo
menos 72 (12x6) elementos, onde cada elemento teria um valor de elevação associado,
indicando a altura dos obstáculos.
A modelagem e interpretação dos dados sensoriais para a construção desse tipo de
mapa não é guiada por uma formulação padrão, como no caso dos mapas baseados em
grade de ocupação no âmbito da robótica. Diferentes formulações são propostas para a
inicialização e atualização dos valores de elevação das células, a partir de distintos sensores. Aqui, será focada a abordagem baseada no Filtro de Kalman, a mesma ferramenta
utilizada por Pfaff et al. (2007).
4.2.1 Filtro de Kalman
O Filtro de Kalman (FK) é um conjunto de equações matemáticas as quais definem
um processo eficiente de estimação, minizando o erro de estado. Através da análise da
variável denominada variável de observação, outra variável não observável, a variável de
estado, pode ser estimada eficientemente [Kalman 1960]. O Filtro de Kalman padrão
presupõe que uma determinada variável a ser estimada tenha seu modelo linear e que
possa ser descrito sob a forma de um sistema de equações de estado (Equação 4.14).
4.2. MAPAS DE ELEVAÇÃO
43
h53
h21
h2
h1
h71
6
12
Figura 4.5: Representação em grade de ocupação 2.5D. É necessária uma estrutura de
dados de 72 elementos para mapear o ambiente ilustrado.
st = At st−1 + Bt ut + δt
zt = Ct st + γt
(4.14)
Onde s ∈ Rn é o vetor de estados do sistema; ut ∈ Rl é o vetor das entradas de sinais de
controle; zt ∈ Rm é o vetor com as medições sensoriais; a matriz At , de tamanho n × n
é a matriz de transição de estados; Bt , de dimensões n × l, é a matriz de coeficientes de
entrada; a matriz Ct , de tamanho m × n, é chamada de matriz de observação; δt ∈ Rn
representa o vetor de ruídos do processo e γt ∈ Rm é o vetor de erros de medição; t e t − 1
representam os instantes de tempo atual e anterior respectivamente.
O filtro é dividido em duas etapas: predição e atualização. A etapa de predição utiliza o modelo evolutivo do sistema e as propriedades estatísticas dos ruídos presentes no
sistema. Já a etapa de atualização leva em conta medições sensoriais para computar uma
nova estimativa atualizada dos dados estimados na predição. O Algoritmo 2 mostra os
passos do Filtro de Kalman padrão. As entadas do algoritmo são: o estado do sistema
µt−1 no tempo instante anterior; a matriz de covariância Σt−1 , que descreve o ruído de
estado no instante t − 1; os sinais de controle ut ; e as medições zt . A saída será uma
estimativa atualizada do estado, µt , e sua convariância, Σt .
Algoritmo 2: Filtro de Kalman
1 Entrada: µt−1 ,Σt−1 ,ut , zt
2 Saída: µt , Σt
3 µ̄t = At µt−1 + Bt ut ;
T
4 Σ̄t = At Σt−1 At + Rt ;
T
T
−1
5 Kt = Σ̄t Ct (Ct Σ̄t Ct + Qt ) ;
6 µt = µ̄t + Kt (zt − Ct µ̄t );
7 Σt = (I − Kt Ct )Σ̄t
44
CAPÍTULO 4. GRADE DE OCUPAÇÃO E MAPAS DE ELEVAÇÃO
As linas 3 e 4 compõem a etapa de predição, onde é realizada a computação do estado
do sistema µ̄t e os ruídos inerentes ao mesmo Σ̄t , considerando o estado passado. A
média µ̄t é conseguida pela aplicação do sinal de controle ut ao modelo determinístico
de transição de estado. A covariância, Σ̄t , é calculada através da matriz de transição de
estado At , a qual expressa a dependência entre o estado atual com o estado anterior. As
linhas de 5 a 7 fazem parte da etapa de atualização, onde µ̄t é transformada em µt pela
incorporação da medição zt . A variável Kt , chamada de ganho de Kalman, especifica o
quanto uma nova medição influencia na nova estimativa do estado, µt , e sua variância Σt .
No contexto do mapa de elevação as variáveis a serem estimadas são a elevação de
uma célula, representada pela média µ0:t , e sua variância, σ20:t , considerando o histórico
das estimativas passadas. O passo de predição do Filtro de Kalman não causa modificações nos valores de elevação e variância previamente calculados, visto que esta etapa
não considera as novas medições de altura e variância realizadas. Logo, a predição pode
ser descrita pelas Equações 4.15 e 4.16.
µ̄0:t = µ0:t−1
(4.15)
σ̄20:t = σ20:t−1
(4.16)
A cada nova medição do sistema visual devem ser derivadas a altura de um lugar,
agora representada por ht , e sua variância, σt2 , que serão inseridas na etapa de atualização
da formulação do Filtro de Kalman para gerar uma nova estimativa da elevação da célula e
sua variância. Na fase de atualização, o primeiro passo do algoritmo é o cálculo do ganho
de Kalman, Kt , como descrito na linha 5 do Algoritmo 2. Considera-se Ct = 1, pois não
influencia o valor da medição sensorial, e Qt = σt2 a variância dessa nova medição. Com
isso, o cálculo de Kt passa a ser feito pela Equação 4.17.
Kt =
σ̄20:t
σ̄20:t + σt2
(4.17)
Ou, aplicando-se as igualdades das Equações 4.15 e 4.16, tem-se a Equação 4.18:
Kt =
σ20:t−1
σ20:t−1 + σt2
(4.18)
Neste ponto, as novas estimativas da elevação, µ0:t , e sua variância, σ20:t , podem ser calculadas, levando-se em conta a nova medição sensorial, ht , tomada no tempo t, e sua variância σt2 . A partir das equações descritas nas linhas 6 e 7 do Algoritmo 2, pode-se deduzir
as expressões de atualização descritas pelas Equações 4.19 e 4.20, as quais computam
as novas estimativas de elevação de uma célula e sua variância, utilizando-se o ganho de
Kalman dado pela Equação 4.18 e fazendo-se as devidas manipulalções matemáticas.
µ0:t =
σt2 µ0:t−1 + σ20:t−1 ht
σ20:t−1 + σt2
(4.19)
4.2. MAPAS DE ELEVAÇÃO
45
σ20:t =
σ20:t−1 σt2
σ20:t−1 + σt2
(4.20)
4.2.2 Trabalhos Relacionados
Os primeiros trabalhos baseados em mapas de elevação no contexto da robótica foram
apresentados por Bares et al. (1989) e Hebert et al. (1989). Estes trabalhos estão voltados
à navegação de robôs ou sondas planetárias com pernas. A partir das ideias apresentadas
nessas investigações novas pesquisas foram surgindo.
Assim como nos mapas em grade de ocupação, diferentes sensores podem ser utilizados para o mapeamento em grade de elevação, porém se destacam os lasers e as câmeras.
Ye & Borenstein (2003) propõem um algoritmo para adquirir mapas de elevação com
um veículo móvel equipado com um sensor laser. Eles apresentaram a formulação de
uma filtragem especial para eliminar erros de medição ou ruídos do sensor laser e dos
movimentos do robô. Em uma pesquisa mais recente, Kwon et al. (2010) também apresentaram sua proposta para representação de ambientes com mapas de elevação a partir
de informações de um laser. Eles utilizam o mapa para realizar a localização do robô com
o método de Monte Carlo (Monte Carlo Localization) com base na associação de dados
sensoriais com o mapa adquirido.
Quando a principal fonte sensorial são as câmera, várias técnicas podem ser encontradas na literatura. Lacroix et al. (2002) extraíram um mapa de elevação a partir de
imagens estéreo com o objetivo final de prover a navegação outdoor de um robô. Já
Hygounenc et al. (2004) construíram um mapa de elevação com um dirigível autônomo
provido de um sistema de visão estéreo. Eles propuseram um algoritmo para detecção de
características e realizar a correspondência ou matching entre mapas localmente construídos usando essas características. Cappalunga et al. (2010) implementaram um sistema de
mapeamento em mapa de elevação com visão estéreo, onde eles se fundamentaram em
um algoritmo biologicamente inspirado para segmentar pontos no terreno.
Como já mencionado, a construção dos mapas de elevação não obedece a uma formulação básica como é o caso das grades de ocupação. Por esse motivo, diferentes abordagens são adotadas na construção desse tipo de representação. Aqui, serão evidenciadas
duas interessantes abordagens estocásticas, a primeira proposta por Pfaff et al. (2007) e a
segunda apresentada por Marks et al. (2009). Pfaff et al. (2007) apresentam a construção
de mapas de elevação baseado em sensor laser. Em sua proposta, os autores consideram
uma abordagem probabilística baseada no Filtro de Kalman para construir o mapa. A
atribuição de valores de elevação à cada célula do mapa é calculada e atualizada a cada
nova medição de elevação provida pelos sensores, além disso, uma medida de variância,
que indica o intervalo de variação dessa elevação, também é computada obedecendo as
imprecisões sensoriais. Assim, cada célula registra uma média e uma variância da elevação do lugar representado.
Marks et al. (2009) propuseram uma abordagem de construção de mapas de elevação,
a qual é aplicada em um algoritmo de SLAM, denominado por eles de Gamma-SLAM.
O mapa é composto de células quadradas, onde cada uma armazena um valor de altura
46
CAPÍTULO 4. GRADE DE OCUPAÇÃO E MAPAS DE ELEVAÇÃO
atribuído de acordo com uma distribuição Gaussiana, com uma precisão (inversa da variância) e média desconhecida. A distribuição utilizada é a Gama, daí vem o nome do
algoritmo de SLAM proposto. O mapa é utilizado para que o robô conheça lugares possíveis de serem atravessados de acordo com um custo de navegação (o termo usado em
inglês é traversability). Segundo os pesquisadores, o algoritmo de mapeamento roda em
tempo real mesmo em processadores convencionais.
Neste trabalho foi adotada a abordagem de Pfaff et al. (2007), a qual será explicada
de forma detalhada no capítulo posterior, por dar a possibilidade de expressar uma estimativa concreta da elevação de um espaço em medidas métricas, o que é uma informação
interessante no processo de tomada de decisões durante a navegação autônoma.
4.3
Considerações
Neste capítulo foram apresentadas as definições formais da representação em grade
de ocupação e dos mapas de elevação. Diante do exposto neste capítulo, é interessante
ressaltar, que a grade de ocupação e a grade de elevação armazenam informações diferentes. Uma, a grade de ocupação, registra informações sobre a probabilidade de ocupação de uma célula, ou seja, a possibilidade de existir um obstáculo em um determinado
lugar do ambiente. A segunda, grade de elevação, considera a existência de um obstáculo
em um determinado lugar com certa altura. Perceba que a grade de elevação ignora a
possibilidade de existência de obstáculo, ela assume a existência de obstáculo. Isso é indesejável por desprezar as influências das incertezas presentes nas informações sensoriais
na avaliação da existência de obstáculos.
Este trabalho expõe uma representação em grade com informações de ocupação e elevação dos lugares mapeados. A abordagem adotada considera uma formulação estocástica
tanto para a ocupação das células quanto para a estimação da elevação, manipulando de
forma adequada incertezas nas presentes informações sensoriais. Cada célula, registra a
probabilidade de estar ocupada, a altura do local mapeado e a variância dessa altura, que
pode ser considerada uma medida de confiabilidade. Para isso, foi adotada uma formulação estocástica baseada no Filtro de Kalman, a qual será abordada no próximo capítulo,
onde se dará a explicação aprofundada da proposta deste trabalho.
Capítulo 5
Grade de Ocupação-Elevação
Este capítulo tem como objetivo apresentar o sistema de mapeamento proposto neste
trabalho, com as metodologias e técnicas utilizadas na implementação de cada etapa do
framework. De início, será apresentada uma contextualização do sistema de mapeamento
proposto, destacando superficialmente suas características. Em seguida será apresentada
a definição formal da abordagem de representação em grade de ocupação-elevação. Por
meio de um diagrama, serão expostas as técnicas utilizadas para a implementação das
diferentes partes que compõem o sistema de mapeamento proposto. Posteriormente, cada
fase será explorada de forma minuciosa a fim de proporcionar uma correta compreenssão
do projeto como um todo.
5.1 Contextualização
A execução eficiente de tarefas de forma autônoma por robôs móveis está fortemente
vinculada à quantidade de informações que o robô possui de seu ambiente. A construção
de um mapa em grade de ocupação que possua informações confiáveis sobre a localização
de objetos e obstáculos presentes no ambiente do robô, pode contribuir significativamente
para que um robô alcance a autonomia. Quando se requer uma navegação mais precisa,
levando-se em conta a altura dos obstáculos e estruturas de um ambiente, é interessante
que o mapeamento em grade seja expandido para o espaço tridimensional. Os mapas
3D facilitam a solução de problemas de associação de dados, visto que possuem maior
quantidade de informações, que resulta em menos ambiguidades [Liu et al. 2001]. Além
disso, são ideais no mapeamento de lugares onde o terreno se apresenta de forma irregular.
Porém, a grande desvantagem dos mapas em grade tridimensional está no seu elevado
custo computacional necessário para construí-los e armazená-los, principalmente quando
o ambiente mapeado é extenso. Uma interessante alternativa para se alcançar a solução
desse problema, seria o uso dos mapas de elevação 2,5-D. Esta representação mantem
uma grade bidimensional, onde cada célula armazena a altura ou elevação do terreno
no ponto mapeado, constituindo-se uma forma compacta de mapeamento em grade com
informações tridimensionais.
Existem alguns robôs que possuem a capacidade de transpor certos obstáculos dentro de uma determinada faixa de altura, principalmente aqueles que são preparados para
48
CAPÍTULO 5. GRADE DE OCUPAÇÃO-ELEVAÇÃO
a navegação em ambientes externos. Um exemplo clássico seria a navegação dos robôs
que realizam explorações planetárias, que lidam com diversas dificuldades de movimentação em terrenos com diferentes características e desafios. Assim, é interessante que
o robô tenha meios de classificar se uma determinada área pode ser explorada mesmo
que seja povoada por obstáculos. Os mapas de elevação munem os robôs com essa habilidade, permitindo que os lugares mapeados sejam classificados como navegáveis ou
não-navegáveis, de acordo com as capacidades locomotoras deles.
É interessante ressaltar, que a grade de ocupação e a grade de elevação armazenam
informações diferentes. A primeira, a grade de ocupação, registra informações sobre a
probabilidade de ocupação de uma célula, ou seja, a possibilidade de existir um obstáculo em um determinado lugar do ambiente. A última, a grade de elevação, considera
a existência de um obstáculo em um determinado lugar com certa altura. Perceba que a
grade de elevação ignora a possibilidade de existência de obstáculo, ela assume a existência de obstáculo. Isso é indesejável por desprezar as influências das incertezas presentes
nas informações sensoriais na avaliação da existência de obstáculos.
Diante desse contexto, esse trabalho apresenta um arcabouço para o mapeamento de
ambientes interno ou externos baseados em informações visuais (providas por um sistema de câmeras estéreo) e com uma representação em grade com informações sobre
a ocupação e elevação dos espaços mapeados, que concede a um robô a capacidade de
classificar a navegabilidade de uma determinada área do seu ambiente de trabalho, considerando suas habilidades motoras. A abordagem desenvolvida está fundamentada em
uma formulação estocástica tanto para o cálculo de ocupação das células quanto para
a estimação da elevação, manipulando de forma adequada incertezas presentes nas informações sensoriais. Cada célula registra a probabilidade de estar ocupada, a altura do local
mapeado e a variância dessa altura, que pode ser considerada uma medida de confiabilidade. Para o caso do valor de ocupação é utilizada a formulação padrão apresentada no
Capítulo 4, porém com uma modelagem robusta para o tratamento das incertezas sensoriais. Já para o valor de elevação é utilizada uma formulação baseada no Filtro de Kalman.
Assim, tem-se as vantagens de ambas as representações cobinadas em um só mapa.
5.2
Definição - Grade de Ocupação-Elevação
Definindo de uma maneira mais formal, a grade de ocupação-elevação proposta consiste de uma grade bidimensional M de células regulares mn , onde n ∈ N, que armazenam
a probabilidade de ocupação, a elevação (ou altura) e a variância da elevação de um lugar
mapeado do ambiente do robô. Expressando matematicamente, pode ser descrita como
mostra a Expressão 5.1.
M = {hO0:t,n , µ0:t,n , σ20:t,n i,
n = 1, ..., N}
(5.1)
Onde N representa o número de células no mapa em grade. Cada célula do mapa pode ser
descrita por uma tripla, como mostra a Expressão 5.2.
5.2. DEFINIÇÃO - GRADE DE OCUPAÇÃO-ELEVAÇÃO
mn = hO0:t , µ0:t , σ20:t i
49
(5.2)
Nesta expressão, O0:t representa o valor de ocupação da célula mn calculado, ou seja,
O0:t = p(mn |x0:t , z0:t ); µ0:t computa a estimativa do valor de elevação; e σ20:t é o valor
da variância da elevação da célula. Essas grandezas são estimadas de forma iterativa
seguindo a evolução temporal do mapeamento até o instante de tempo t. A Figura 5.1
ilustra a composição do mapa em grade, de acordo com a especificação acima.
Ocupação
Elevação
Grade 2D
Figura 5.1: Formação da grade de ocupação-elevação.
Note que, tanto a estimação da ocupação quanto o cálculo da elevação estão sendo
realizados através de ferramentas probabilísticas, as quais permitem o tratamento correto das incertezas inerentes ao sistema perceptivo robótico. O valor de ocupação (leiase probabilidade de ocupação) é dado por uma função de densidade de probabilidade,
p(mn |x0:t , z0:t ), e o valor da elevação é descrito por uma distribuição normal caracterizada por uma média µ0:t e uma variância σ20:t , ou N (µ0:t , σ20:t ). Assim, cada ponto,
PM = (xM , yM , zM ) ∀ PM ∈ R3 , do ambiente do robô é projetado em uma célula pertencente
à grade de ocupação-elevação.
Como mencionado anteriormente, uma grade de ocupação, registra informações sobre a probabilidade de ocupação de uma célula, ou seja, a possibilidade de existir um
obstáculo em um determinado lugar do ambiente. A grade de elevação assume a existência de um obstáculo em um determinado lugar com certa altura. Isso é indesejável por
desprezar as influências das incertezas presentes nas informações sensoriais na avaliação
da existência de obstáculos. E mapear um espaço em uma grade de ocupação tridimensional demanda grande quantidade de recursos de processamento e memória.
50
CAPÍTULO 5. GRADE DE OCUPAÇÃO-ELEVAÇÃO
Para solucionar essas restrições, a representação em grade 2.5D de ocupação-elevação
considera uma formulação estocástica tanto para a ocupação das células quanto para a estimação da elevação (informação da terceira dimensão), manipulando de forma adequada
incertezas nas presentes informações sensoriais, com uma estrutura de dados bidimensional, onde cada célula registra a probabilidade de estar ocupada, a altura do local mapeado e a variância dessa altura, que pode ser considerada uma medida de confiabilidade
sobre a altura de um obstáculo.
Com isso, além de possuir uma representação que habilite a execução direta de algoritmos de planejamento de caminhos e execução de trajetória com desvio de obstáculos
(característica da grade de ocupação), o robô terá condições de classificar áreas do seu
ambiente, definindo se são adequadas para a navegação ou possuem obstáculos grandes o
suficiente para impossibilitar tal ação.
5.2.1 Etapas do Mapeamento em Grade de Ocupação-Elevação
O diagrama da Figura 5.2 mostra a sequência das etapas necessárias para se alcançar
o mapeamento proposto. De forma resumida essas etapas são decritas a seguir:
• Estimativa da pose: inferência das coordenadas e orientação do robô em relação
a algum referencial fixo no mundo. Neste trabalho esta etapa foi implementada
através do modelo movimento de odometria.
• Aquisição e interpretação de dados sensoriais: corresponde a ciência que o robô tem
sobre o seu entorno. Neste caso, através de uma câmera estéreo o robô coleta as
informações e com a manipulação desses dados, são calculadas as coordenadas dos
pontos pertencentes aos objetos presentes no entorno do robô, em relação ao sistema de câmeras. Por meio de processamento de imagens e do modelo geométrico
do sistema de câmeras é possível realizar tal estimativa.
• Modelagem sensorial: a partir dos dados resultantes das duas etapas anteriores é
possível criar um mapa de ocupação-elevação local de acordo com a modelagem
probabilística proposta, considerando as incertezas das informações sensoriais.
• Integração de dados: através das equações de atualização, responsáveis por atribuir
o valor de ocupação e de elevação às células, é possível integrar ou incorporar as
informações do mapeamento local realizado na etapa anterior com as informações
já existentes no mapa em grade global.
A seguir cada uma dessas etapas será explorada de forma detalhada e concisa, acentuando as principais técnicas utilizadas e propostas sugeridas.
5.2. DEFINIÇÃO - GRADE DE OCUPAÇÃO-ELEVAÇÃO
Figura 5.2: Etapas do mapeamento em grade de ocupação-elevação.
51
52
5.3
CAPÍTULO 5. GRADE DE OCUPAÇÃO-ELEVAÇÃO
Posicionamento - Modelagem Cinemática
Como já citado em capítulos anteriores, o mapeamento de ambientes com robôs depende de uma estimativa da posição do robô, o ideal seria ter uma localização precisa.
Porém, devido a erros sistemáticos e não sistemáticos a situação ideal não pode ser alcançada. Existem certas técnicas que podem amenizar os erros causados nessa etapa.
Através da modelagem cinemática é possível realizar um cálculo aproximado a respeito dos movimentos realizados por um robô e, consequentemente, inferir a sua posição.
O modelo cinemático tradicional para um robô de drive diferencial, se baseia nos sinais
de controle (geralmente medidas de velocidade linear e velocidade angular) enviados aos
motores para estimar as coordenadas e orientação do robô. Se o robô possui sensores de
rotação (encoders) acoplados em suas rodas, alternativamente pode-se utilizar as medidas
de odometria como base para o cálculo dos movimentos do robô sobre o tempo.
A odometria é comumente obtida pela integração das informações fornecidas por encoders acoplados aos robôs. A pose é calculada a partir da integração de pulsos lidos dos
encoders em intervalos de tempo periódicos (por exemplo, a cada 10ms). Experiências
práticas sugerem que a odometria, mesmo que ainda errônea, é geralmente mais precisa
que os modelos baseados em velocidades. As duas abordagens sofrem com escorregamento e derrapagens, porém o modelo de velocidade é ainda afetado por erros inerentes
aos próprios sinais de controle [Thrun et al. 2005]. O modelo de movimento de odometria se difere por utilizar as medições odométricas como sinais de controle e não como
informações sensoriais.
Para se analisar essa modelagem, assuma que a Equação 5.3 descreve a evolução
temporal da localização do robô.
st = f (st−1 , ut )
(5.3)
Onde st = (x, y, θ) é a pose (posição e orientação) sendo calculada; ut = (∆l, ∆θ) são os
sinais de controle providos pelo sistema de odometria com ∆l sendo o deslocamento linear
e ∆θ o deslocamento angular, ambos executados dentro do intervalo de tempo [t − 1,t]. A
Equação 5.3 pode ser colocada de forma mais detalhada, como mostra a Equação 5.4.
st = f (st−1 , ∆l, ∆θ)
(5.4)
A Figura 5.3 explicita melhor os parâmetros da equação por meio da representação
de um robô móvel com acionamento diferencial, o qual possui encoders acoplados em
suas rodas. Dessa figura, r representa o raio das rodas, b diz respeito à distância entre
eixos do robô, e ∆ll e ∆lr são os deslocamentos lineares das rodas esquerda e direita
respectivamente, e fazem parte da expressão matemática para estimar ∆l e ∆θ, como
mostram as expressões abaixo.
∆l =
∆lr + ∆ll
2
(5.5)
∆θ =
∆lr − ∆ll
b
(5.6)
5.3. POSICIONAMENTO - MODELAGEM CINEMÁTICA
53
Y
Dl
Dll
Dql
Dq
r
Dlr
y
b
Dq r
x
X
Figura 5.3: Modelagem cinemática de movimento.
Sabendo-se que ∆ll e ∆lr são grandezas valoradas a partir das medidas de odometria, é
possível detalhar ainda mais essas equações, baseando-se nos deslocamentos angulares
∆θl e ∆θr de cada roda,
∆l =
∆θr r + ∆θl r
2
(5.7)
∆θr r − ∆θl r
(5.8)
b
Pode-se ainda chegar a uma expressão que esteja diretamente relacionada com as informações fornecidas pelos encoders, sabendo-se que,
∆θ =
πNl
πNr
e
∆θr =
(5.9)
Nres
Nres
Onde Nl e Nr são o número de pulsos lidos pelos encoders esquerdo e direito respectivamente e Nres é a resolução do encoder, que indica o número de pulsos em um giro
completo da roda. Tendo essa sequência de informações a respeito da odometria, é conveniente expandir a Equação 5.4, com as devidas relações de movimento para as variáveis
que representam o estado st do robô, como mostra a Equação 5.10.
∆θl =

 
 
xt
xt−1
 yt  =  yt−1  + 
θt−1
θt
∆l
∆l
∆θ sin(θt−1 + ∆θ) − ∆θ sin θt−1
∆l
∆l
∆θ cos(θt−1 ) + ∆θ) + ∆θ cos θt−1
∆θ


(5.10)
Quando não há movimentos angulares ocorrem inconsistências numéricas na Equação 5.10,
portanto o modelo passa então a ser descrito pela Equação 5.11, alcançada quando a
Equação 5.10 é levada ao limite.

 
 
xt
∆l cos θt−1
xt−1
 yt  =  yt−1  +  ∆l sin θt−1 
0
θt
θt−1

(5.11)
54
CAPÍTULO 5. GRADE DE OCUPAÇÃO-ELEVAÇÃO
É importante relembrar que mesmo sendo mais preciso que o modelo de velocidade, o
modelo de odometria é afetado por erros que ocorrem por deslizamentos, escorregamentos, eventos não previstos, entre outros, que influenciam na medição dos encoders. Logo,
é importante que essas fontes de ruídos sejam consideradas no modelo, como mostra a
Equação 5.12.
∆θr = ∆θ̂r + N (0, ε2r )
(5.12)
∆θl = ∆θ̂l + N (0, ε2l )
Onde ∆θ̂r e ∆θ̂l são as medições de deslocamento angulares realizadas pelos encoders, e
N (0, ε2r ) e N (0, ε2l ) são os erros inerentes a essas medidas, que são representados por uma
distribuição normal de média zero e variâncias ε2r e ε2l . Essas grandezas foram estimadas
por meio de exaustivos experimentos práticos publicados em um trabalho anterior [Souza
2008]. O modelo de odometria foi implementado neste trabalho visando uma melhor
estimativa das variáveis que descrevem o estado do robô dentro do seu ambiente.
5.4
Aquisição e Interpretação de Dados Sensoriais
A etapa de dedução do mapa de disparidade pode ser subdividida em sub etapas,
são elas: aquisição de imagens, calibração estéreo, retificação, correspondência estéreo,
cálculo de disparidade, cálculo dos pontos 3D no referencial de câmera para posterior
estimação da distância entre câmera e pontos calculados. Neste trabalho, todo o processamento e manipulação de imagens foi realizado por meio da biblioteca OpenCV (Open
Source Computer Vision Library).
5.4.1 Aquisição de Imagens
Na sub etapa de aquisição foi utilizado um sistema de visão estéreo de baixo custo
nomeado de Minoru 3D (Figura 5.4), cujo funcionamento simultâneo de ambas câmeras
no sistema operacional Linux deve ser aliado à API V4L (Video For Linux). O sistema
estéreo pode ser facilmente conectado a qualquer sistema de computacional com porta
USB.
Figura 5.4: Câmera estéreo Minoru 3D utilizada no mapeamento.
5.4. AQUISIÇÃO E INTERPRETAÇÃO DE DADOS SENSORIAIS
55
A captura das imagens de ambas as câmeras foi realizada por chamadas de funções
da API V4L, a qual favorece o acesso em baixo nível às câmeras através do barramento
USB de forma paralela.
5.4.2 Calibração Estéreo
O segundo passo realizado dentro do procedimento de estimação do mapa de disparidade é a calibração estéreo, processo pelo qual se computa a relação entre as duas câmeras
no espaço tridimensional [Bradski & Kaehler 2008]. O objetivo então é encontrar uma
matriz de rotação R e um vetor de translação T que estabelecem relações métricas entre as
câmeras. Esses parâmetros são de fundamental importância para os cálculos de dedução
das coordenadas dos pontos no mundo a partir de imagens estéreo. Além disso, outras
variáveis podem ser encontradas também durante esse processo, por exemplo, a distância
focal, coordenadas de centro de imagens e coeficientes de distorção, os quais são utilizados para retirar as distorções radiais e tangenciais nas imagens, produzidos por defeitos
nas lentes das câmeras.
5.4.3 Retificação
Durante o calculo de disparidade é mais fácil se aferir valores de disparidade quando
os planos das duas imagens estão exatamente alinhados, restrição assumida durante a
explicação dada sobre geometria estéreo no Capítulo 3. Porém, um alinhamento perfeito
de um sistema estéreo real é raramente conseguido, assim as duas câmeras quase nunca
tem os planos de imagens exatamente coplanares. O passo de retificação estéreo tem
como objetivo reprojetar os planos de imagens das duas câmeras tal que eles possam ser
coplanares, com as linhas das imagens estando alinhadas em uma configuração paralela
frontal [Bradski & Kaehler 2008]. A retificação contribui para o passo de correspondência
estéreo restringindo o espaço de busca por pixels correspondentes, para linha epipolar das
imagens. Isso torna a correspondência mais confiável e computacionalmente tratável. A
Figura 5.5 mostra a execução da retificação estéreo em imagens capturadas pelo sistema
de câmeras empregado nesse trabalho.
Figura 5.5: Processo de retificação estéreo.
CAPÍTULO 5. GRADE DE OCUPAÇÃO-ELEVAÇÃO
56
5.4.4 Correspondência Estéreo
Após a retificação das imagens, considerando-as agora sobre um mesmo plano, o
passo de correspondência pode ser executado. Os pontos correspondentes são computados
apenas sobre as áreas nas quais os campos de visão de ambas as câmeras de sobrepõem.
Neste trabalho foi adotada a correspondência baseada na abordagem graph-cuts, cujos
resultados alcançados se mostraram mais ricos em informações úteis para a construção
do mapa proposto. Detalhes sobre o graph-cuts podem ser encontrados no trabalho de
Hong & Chen (2004).
Terminada a sub etapa de correspondência estéreo, o cálculo de disparidade é automaticamente realizado, finalizando a construção do mapa de disparidade também chamado
de imagem de profundidade. Uma grande dificuldade que pode ser encontrada no cálculo
de disparidade, se verifica quando as imagens são pobres em texturas. Neste caso, a
detecção de pontos correspondentes se torna mais complexa, o que afeta diretamente a
estimação de um mapa de disparidade de qualidade. Esse efeito poderia ser amenizado
com o uso de técnicas de multi-resolução [Gonçalves et al. 2000].
A Figura 5.6 mostra um resultado da estimação do mapa de disparidade, de uma cena
extraída de um experimento realizado em um ambiente interno, utilizando graph-cuts.
(a)
(b)
Figura 5.6: Construção do mapa de disparidade.
5.4.5 Cálculo das Coordenadas dos Pontos Detectados
Com o mapa de disparidade estimado é possível agora, através da geometria estéreo,
estabelecer as coordenadas dos pontos do mapa de disparidade em relação ao referencial
da câmera, Pc = (xc , yc , zc ). As equações do Capítulo 3 da seção 3.3.1, utilizadas nesses
cálculos, podem ser relembradas.
b. f
d
(x − x0 )
xc = zc .
f
zc =
yc = zc .
(y − y0 )
f
(5.13)
(5.14)
(5.15)
5.5. MODELAGEM SENSORIAL
57
Onde d é a disparidade de cada pixel de coordenada (x, y) de uma das imagens (esquerda
ou direita), (x0 , y0 ) são as coordenadas do centro da imagem e f é a distância focal da
câmera, que pode ser obtida no processo de calibração, citado anteriormente.
5.5 Modelagem Sensorial
Essa etapa aufere o resultado das etapas anteriores, funde essas informações para obter
um valor de ocupação e elevação de acordo com uma formulação estocástica, a qual considera a existência de ruídos inerentes aos dados recebidos, tratando-os de forma adequada.
5.5.1 Modelagem Sensorial para Estimar o Valor de Ocupação
No presente trabalho é adotado um modelo probabilístico Gaussiano, o qual modela
o comportamento do sensor visual e das suas incertezas inerentes ao cálculo do mapa
de disparidade. Para isso se faz necessária a computação da distância entre o centro
do sistema estéreo e os pontos Pc = (xc , yc , zc ) calculados para cada pixel com valor de
disparidade válido inferido na etapa anterior. Essa medida de distância é obtida através
da Equação 5.16.
q
(5.16)
l p = xc2 + y2c + z2c
O modelo inverso do sensor utilizado no cálculo de ocupação de uma célula a partir da
distância calculada é dado pela Equação 5.17.
p(mn |st , zt ) = pocc (l) +
∆l p
k
√
!
(
1
+ 0.5 − pocc (l) exp −
2
2π
l − lp
∆l p
2 )
(5.17)
com,
pocc =
(
pmin
0
se 0 < l ≤ l p
se l > l p
(5.18)
O parâmetro k pondera a importância de uma única medição realizada e seu valor é
atribuído observando-se o comportamento do sensor utilizado, e pmin é um valor de ocupação mínimo atribuído às células que estão provavelmente livres. A restrição ∀l ≥ lmin :
p(mn |st , zt ) ∈ [0; 1] deve ser satisfeita para assegurar que os valores de probabilidade resultantes sejam válidos [Andert 2009]. O erro, ∆l p , no cálculo da distância entre a câmera
estéreo e os pontos Pc = (xc , yc , zc ) no espaço, vistos do referencial de câmera, é calculado
pela Equação 5.19.
∆l p = ∆zc
lp
zc
(5.19)
CAPÍTULO 5. GRADE DE OCUPAÇÃO-ELEVAÇÃO
58
Perceba que essa equação tem uma relação direta com a incerteza presente na estimativa da coordenada zc , especificada por ∆zc . Essa incerteza, por sua vez, é diretamente
proporcional aos ruídos causados por erros durante o processo de estimação do mapa de
disparidade. A Equação 5.20 mostra como deve ser calculada a incerteza ∆zc .
∆zc =
z2c
∆d
b. f
(5.20)
Nessa equação os parâmetros de câmera b (distância entre os centros de projeção) e f (distância focal) são novamente utilizados. Porém, o termo mais importante dessa equação,
que reflete os erros inerentes à estimação do mapa de disparidade, é ∆d (em pixels), também chamado de resolução de profundidade [Xiong & Matthies 1997] ou incremento de
disparidade [Bradski & Kaehler 2008]. Assim, as coordenadas passam a ser expressas por
zc + ∆zc , yc + ∆yc e xc + ∆xc , onde incertezas nas coordenadas xc e yc do ponto Pc podem
ser calculadas de acordo com a Equaçãos 5.21, derivada das Equações 5.14 e 5.15 quando
uma entrada x + ∆d e y + ∆d é imputada [Andert 2009].
∆xc = ∆yc = zc
∆d
f
(5.21)
A Figura 5.7 ilustra os efeitos das incertezas sensoriais na estimação de ocupação
inferida pelo modelo inverso do sensor da Equação 5.17. Note que, quanto maior a distância medida entre a câmera até um objeto l p , maior será a incerteza dessa medição.
Esse efeito pondera o valor de ocupação atribuído ao ponto mapeado, considerando os
ruídos de processamento estéreo. Na figura estão exemplificados dois caso de medições
distintas: l p = 10m e l p = 15m. Para a primeira medição, representada pela curva em vermelho, a incerteza inerente a zc é ∆zc = 0.2. A segunda medição, em ciano, tem incerteza
∆zc = 0.3
Efeitos das Incertezas na Probabilidade de Ocupação
1
0.9
0.8
p(mn|zt, xt)
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
2
4
6
8
10
12
14
16
18
20
Distância [m]
Figura 5.7: Modelo inverso do sensor aplicado ao cálculo de ocupação para l p = 10m e
l p = 15m.
5.5. MODELAGEM SENSORIAL
59
5.5.2 Modelagem Sensorial para Estimar o Valor de Elevação
Para encontrar o valor de elevação ou altura de uma célula, cuja projeção do ponto
Pc cai sobre ela, é realizada uma transformação das coordenadas do ponto em relação ao
sistema de câmera para um ponto, PM , com coordenadas relacionadas a um referencial
global. Para isso, deve-se considerar a posição da câmera em relação ao referencial fixo
no robô e a posição do robô em relação ao referencial global. A Figura 5.8 ilustra os
referenciais de coordenadas envolvidos nas transformações necessárias para o cálculo da
altura de uma célula
ZM
XM
TRM
YM
Figura 5.8: Referenciais de coordenadas envolvido no mapeamento.
O sistema de referência definido pelos eixos (XM ,YM , ZM ) representa o referencial
global fixo no mundo, o sistema de referência definido pelos eixos (XR ,YR , ZR ) representa
o referencial do robô e o sistema de referência determinado pelos eixos (Xc ,Yc , Zc ) representa o referencial da câmera. A transformação homogênea TcR calcula as coordenadas do
ponto Pc no referencial do robô e a transformação homogênea TRM estima as coordenadas
no referencial global de um ponto expresso no referencial do robô. Logo, para expressar as coordenadas do ponto Pc no referencial global deve ser aplicada uma sequência de
transformações homogêneas, de acordo com a Equação 5.22.
PM = TRM .TcR .Pc
(5.22)
Com as coordenadas do ponto Pc expressas no referencial global definidas por PM =
(xM , yM , zM ), a altura ou elevação do local do ambiente do robô capturado pela câmera
no instante t passa a ser conhecida, ht = zM . Essa estimativa sofre efeito dos ruídos
calculados pelas Equações 5.20 e 5.21, que com as devidas manipulações algébricas dará
uma estimativa do erro imposto sobre ht , que será expressa como a variância da elevação,
σt2 . A Equação 5.23, extraída a partir das manipulações algébricas citadas, realiza o
cálculo do desvio padrão σt .
σt = ∆zM = ∆yc cos α + ∆zc sin α
(5.23)
Onde α é o ângulo de orientação dos eixos do referencial da câmera em relação ao referencial do robô, cujo valor foi escolhido de forma que o campo visual da câmera alcaçasse
CAPÍTULO 5. GRADE DE OCUPAÇÃO-ELEVAÇÃO
60
a maior área frontal possível, respeitando os intervalos de distância impostos, e ∆yc e
∆zc são as incertezas calculadas pelas Equações 5.20 e 5.21. A Figura 5.9 illustra o
comportamento do modelo sensorial para a elevação. Nesta figura, as linhas verticais
(verde, vernelha e azul) representam a variação da elevação medida, ht = 2m. Perceba
que, a medida que a distância, l p , entre câmera e ponto detectado aumenta, há uma maior
variação (dada pela Equação 5.23) sobre o valor de elevação estimado.
Efeito das incertezas no cálculo de Elevação
2.4
2.3
2.2
Alltura [m]
2.1
2
1.9
1.8
1.7
1.6
0
0.5
1
1.5
2
2.5
3
3.5
4
Distancia [m]
Figura 5.9: Comportamento do modelo sensorial para o cálculo de elevação de uma célula,
levando em consideração as incertezas, para uma madição ht = 2m, com distâncias l p =
1m, l p = 2m e l p = 3m, σt = 0.032m, σt = 0.13m e σt = 0.28m, respectivamente. .
5.5.3 Modelagem das Incertezas e Ruídos Sensoriais
Neste trabalho, foi adotada uma modelagem criteriosa das incertezas que podem afetar a qualidade das informações contidas em um mapa de disparidade e que, consequentemente, podem contribuir de forma negativa na precisão do cálculo dos pontos 3D no
espaço, detectados pelo sistema de câmera estéreo. Baseando-se no trabalho de Xiong &
Matthies (1997), foi levantada uma investigação dos principais fatores que influenciam
na qualidade da estimação de um mapa de disparidade. De acordo com os pesquisadores
duas das principais fontes de erros no cálculo do mapa de disparidade são: efeito de escorço (foreshortening error) e desalinhamento (misalignment error) do sistema estéreo.
A combinação desses erros pode facilmente exceder três décimos de um pixel, o que pode
ser traduzido em um erro significativo no cálculo de l p .
Efeito de escorço
Explicando melhor o erro pelo efeito de escorço (foreshortening error), é interessante
a priori saber o significado de escorço, que se refere ao efeito de perspectiva ou ilusão de
5.5. MODELAGEM SENSORIAL
61
ótica que apresenta os objetos em proporções menores do que são na realidade. Isso acontece quando o plano de imagem da câmera não está fronto-paralelo à cena 3D, causando
certa deformação da imagem direita Ir em relação a imagem esquerda Il . A Figura 5.10
ilustra a consequência do efeito de escorço.
eixo óptico
eixo óptico
S
lr
ll
plano da imagem
plano da imagem
f
f
Ol
b
Or
Figura 5.10: O efeito de escorço da superfície não paralela S é diferente para as duas
câmeras: a projeção de S nos planos de imagens tem comprimentos diferentes ll e lr .
O erro causado por essa deformação no cálculo de disparidade pode ser encontrado
pela Equação 5.24.
∆e f = a.e f
(5.24)
Onde a é o gradiente de disparidade e e f é chamada de sensibilidade de escorço (foreshortening sensitivity). O gradiente de disparidade a indica se certas áreas das imagens
direita e esquerda podem ser comparadas e correlacionadas, e pode ser calculado pela
Equação 5.25 [Li & Hu 2002].
a = 2.
|(x2l − x2r ) − (x1l − x1r )|
k(pl2 − pl1 ) + (pr2 − pr1 )k
(5.25)
pl1 = (x1l , yl1 ) e pl2 = (x2l , yl2 ) são pontos na imagem esquerda Il , enquanto que pr1 = (x1r , yr1 )
e pr2 = (x2r , yr2 ) são pontos na imagem direita Ir . A sensibilidade de escorço e f é definida
pela Equação 5.26.
2
l
Σ3x=−3 Σ3y=−3 y ∂I
∂x
ef =
(5.26)
2
∂Il
3
3
Σx=−3 Σy=−3 ∂x
Esta grandeza mede, em cada pixel, a razão entre a magnitude do erro de disparidade e a
CAPÍTULO 5. GRADE DE OCUPAÇÃO-ELEVAÇÃO
62
magnitude do gradiente de disparidade [Xiong & Matthies 1997].
Desalinhamento do sistema estéreo
O problema do desalinhamento do sistema estéreo pode ser resolvido através do passo
de calibração e posterior retificação, explicados anteriormente. Porém, em sistemas robóticos desenvolvidos para navegar em terrenos externos é verificada a existência de vibrações
mecânicas, que muitas vezes podem ser intensas, e podem deturpar a estimativa dos
parâmetros de câmera, desalinhado o sistema estéreo, como ilustra a Figura 5.11.
plano da imagem
plano da imagem
b
Figura 5.11: Desalinhamento vertical dos planos de imagens.
Os erros causados por esse fator podem ser modelados através da computação de um
parâmetro de sensibilidade de desalinhamento, definido pela Equação 5.27.
∆em = m.em
(5.27)
O parâmetro m representa o desalinhamento vertical e a medida de sensibilidade de desalinhamento vertical, que pode ser calculada através da Equação 5.28.
l ∂Il
Σ3x=−3 Σ3y=−3 ∂I
∂x ∂y
em =
2
l
Σ3x=−3 Σ3y=−3 ∂I
∂x
(5.28)
Nos trabalhos de Xiong & Matthies (1997) e Kim et al. (2005) são sugeridos valores
para o desalinhamento vertical m dentro do intervalo [0, 11; 0, 31], mesmo que o sistema
estéreo tenha passado por um estágio de calibração anterior. O valor total do erro inerente
ao cálculo do mapa de disparidade, devido aos dois fatores explanados acima pode ser
obtido através da Equação 5.29.
∆d = ∆e f + ∆em
(5.29)
Este erro afeta diretamente a estimação das coordenadas dos pontos detectados pelo sistema de câmeras, como já explicado na subseção 5.5.1, anteriormente. Com essa modelagem os dados sensoriais podem ser tratados de forma adequada, levando-se em conta
seus ruídos que produzem incertezas, que por sua vez, serão tratadas de maneira correta
na construção do mapa em grade de acordo com a formulação probabilística adotada para
estimação da ocupação e elevação.
5.6. INTEGRAÇÃO DE DADOS
63
5.6 Integração de Dados
A fase de integração atualiza os valores de ocupação e elevação de acordo com as formulações que serão apresentadas. Aqui, a integração não se refere à operação matemática,
mas sim, ao ato de incorporar novas informações à dados já existentes. Nesta etapa as novas medições sensoriais são incorporadas ao mapa produzindo novos valores da ocupação
e de elevação juntamente com sua variância.
5.6.1 Integração dos Valores de Ocupação
Para os valores de ocupação foi adotada a formulação padrão explicada no Capítulo 4,
logo, através da equação de atualização da formulação da grade de ocupação todas as
células dentro do campo visual do sistema estéreo devem ter a probabilidade de ocupação
atualizada, a partir do valor retornado pelo modelo sensorial. A equação de atualização
apresentada no Capítulo 4 pode ser relembrada neste ponto.
ℓtn = log
p(mn |xt , zt )
1 − p(mn )
− log
+ ℓt−1
n
1 − p(mn |xt , zt )
p(mn )
(5.30)
Com ℓt−1
n refletindo a ocupação calculada anteriormente; p(mn ) é um valor de inicialização da grade, neste trabalho foi utilizado p(mn ) = 0.5; p(mn |zt , xt ) representa o modelo
inverso do sensor (Equação 5.17). O valor da probabilidade de ocupação atualizado de
uma célula mn pode ser recuperado através da Equação 5.31.
p(mn |x0:t , z0:t ) = 1 −
1
1 + exp(ℓtn )
(5.31)
5.6.2 Integração dos Valores de Elevação
Para os valores relacionados à elevação a atualização é realizada através do Filtro de
Kalman, o qual permite que uma nova medição de elevação ht tomada no tempo t e sua
incerteza σt2 sejam incorporadas na estimativa do valor de elevação registrado na grade.
As Equações 5.32 e 5.33 relembram as expressões utilizadas para o calculo dos valores
atualizados da elevação e sua variância respectivamente, para uma célula.
µ0:t =
σt2 µ0:t−1 + σ20:t−1 ht
σ20:t−1 + σt2
(5.32)
σ20:t−1 σt2
σ20:t−1 + σt2
(5.33)
σ20:t =
Nessa formulação matemática, µ0:t representa o valor de elevação da célula após uma
leitura sensorial ht ; σ20:t se refere à variância de µ0:t atualizada a partir da variância calculada da leitura sensorial ht ; e por fim, µ0:t−1 e σ20:t−1 são os valores de elevação e sua
variância estimados no instante t − 1. A formulação apresentada no capítulo anterior e
relembrada neste ponto, segue as mesmas ideias apresentada por Pfaff et al. (2007).
CAPÍTULO 5. GRADE DE OCUPAÇÃO-ELEVAÇÃO
64
5.6.3 Definição do Campo Visual de Células Atualizáveis
A atualização dos valores de ocupação e elevação se dá de forma iterativa nas células
que pertencem ao campo visual do sistema estéreo, definido pelo mapa de disparidade.
Para isso, este trabalho adota uma expansão do algoritmo de Bresenham para o espaço
3D. Para cada pixel (x, y) do mapa de disparidade Dt , com valor de disparidade válido1
é calculado um raio desde o centro da câmera até um ponto PM capturado. Os pontos
sobre o raio traçado são projetados em uma célula no mapa de ocupação-elevação, as
quais terão os valores de ocupação atualizados de acordo com os valores retornados pelo
modelo inverso do sensor exposto anteriormente. O raio é percorrido através do algoritmo
de Bresenham 3D.
O valor de elevação será atualizado na célula correspondente à projeção do ponto
PM na grade, considerando o valor de elevação resultante do modelo sensorial adotado.
O Algoritmo 3 descreve a sequência de passos realizados para atualização das células
no mapa 2,5-D de ocupação-elevação. O algoritmo possui como variáveis de entrada o
mapa em grade M, o mapa de disparidade Dt processado a partir das imagens tomadas
no instante t e a pose (coordenadas e orientação) do robô no ambiente. Como saída,
o algoritmo retorna o mapa M com as células pertencentes ao campo visual do sensor
atualizadas. A variável c na linha 9 representa o tamanho de uma célula.
Algoritmo 3: Atualização do Campo Visual
Entrada: M, Dt , xt .
Saída: M.
1 para cada pixel Dt (x, y) com valor de disparidade válido faça
2
Calcule as coordenadas de mundo PM do ponto detectado;
3
Calcule a distância l p entre a câmera e o ponto detectado (Equação 5.16);
4
Trace um raio desde o centro da câmera até o ponto PM ;
5
// Uso do Algoritmo de Bresenham
para cada ponto do raio, projetado sobre uma célula mn da grade faça
6
Calcule l (distância entre câmera e ponto projetado);
7
Calcule o valor da probabilidade de ocupação, P(mn |xt , zt ), da célula mn
(Equação 5.17);
8
Atualize o valor de ocupação da célula mn na grade (Equação 5.31);
9
Atualize o valor de elevação de mn (Equação 5.32);
Atualize o valor da variância da elevação de mn (Equação 5.33);
10
11
12
fim para
fim para
1 Valores
que resultam em profundidades dentro de um intervalo deduzido de acordo com observações
feitas sobre o comportamento do sensor em relação a sua precisão.
5.7. CONCLUSÃO
65
5.7 Conclusão
Neste capítulo foi exposta de maneira aprofundada a proposta deste trabalho. Foi
definida formalmente a grade de ocupação-elevação que tem como objetivo armazenar informações sobre a ocupação do ambiente do robô juntamente com a altura dos obstáculos
mapeados. Cada etapa do processo de mapeamento proposto foi explicada, considerando
a formulação matemática de cada técnica empregada.
O conjunto de todas as técnicas explicitadas nesse capítulo forma um arcabouço para
o mapeamento de ambientes interno ou externos baseados em informações visuais, com
uma representação em grade, cujos dados registrados contribuem para que um robô móvel
possa navegar de forma autônoma dentro do seu ambiente, permitindo-o classificar a
navegabilidade de uma determinada área do seu espaço, considerando suas habilidades
motoras.
O próximo capítulo apresenta experimentos reais realizados para demonstrar a factibilidade do mapeamento proposto. Foi realizado o mapeamento de diferentes ambientes, com
o fim de mostrar a robustez da proposta tanto para o mapeamento de ambientes internos
quanto para ambientes externos.
66
CAPÍTULO 5. GRADE DE OCUPAÇÃO-ELEVAÇÃO
Capítulo 6
Experimentos e Resultados
Este capítulo tem como objetivo apresentar os resultados do método de mapeamento explicado no capítulo anterior. O sistema tem como entrada mapas de disparidades calculados através do processamento das imagens capturadas pelas câmeras do sistema
estéreo. Os passos para o mapeamento são realizados de acordo com as etapas expostas
no capítulo anterior até se chegar ao resultado final: mapa de ocupação-elevação. Serão
apresentados diversos experimentos englobando diferentes situações possíveis de serem
encontradas nos ambientes reais, sejam internos ou externos. Para contextualizar os experimentos realizados, o capítulo começará identificando o sistema robótico utilizado,
seguindo, posteriormente, com os experimentos feitos em um ambiente interno e finalizando com os experimentos alcançando o mapeamento de ambientes externos e mistos
(com características de ambientes internos e externos).
6.1 Visão Geral do Sistema Robótico
Na validação do mapeamento proposto foram realizados vários experimentos com
o robô de drive diferencial Pioneer 3-AT. Essa plataforma robótica foi construída para
possibilitar a navegação em diferentes tipos de terrenos, daí a sigla AT (All Terrains). O
robô está equipado com 16 sonares, sensores de toque (bumpers), motores diferenciais,
um sistema de câmera estéreo de baixo custo (Minoru 3D) e um PC embarcado, que
possibilita a comunicação do robô com outras centrais de processamento via comunicação
RS-232, porta LAN e Wi-Fi. A Figura 6.1 mostra a plataforma robótica utilizada nos
experimentos deste trabalho.
Neste trabalho o sistema de câmera estéreo foi elegido como fonte única de informações sensoriais externoceptivas para o mapeamento, os demais sensores do robô foram
desconsiderados, bem como o processamento através do PC embarcado. Um notebook
com CPU Intel Core i3, 2.13GHz, com 4GB de memória RAM e HD 500GB, foi conectado ao robô, para atuar como central de processamento. Foi instalado o sistema de operacional Linux Ubuntu 11.04 para operar com as bibliotecas que habilitam a manipulação
das informações internas do robô (velocidade, leitura de encoders, nível de bateria, etc.)
e para lidar com as funções de chamada de sistema necessárias para a câmera estéreo.
Como já foi adiantado no capítulo anterior, na aquisição e processamento imagens
foi utilizada a biblioteca de visão computacional OpenCV (Open Source Computer Vi-
CAPÍTULO 6. EXPERIMENTOS E RESULTADOS
68
Câmera
Estéreo
PC
Embarcado
Sonares
Bumpers
Motores
(Drive diferencial)
Figura 6.1: Plataforma robótica utilizada nos experimentos.
sion Library), versão 2.3-1 aliada com a API V4L (Video For Linux), a qual possibilitou
aquisição simultânea de imagens capturadas.
6.2
Calibração Estéreo
Antes da realização dos experimentos foi realizado o passo de calibração a fim de
inferir os parâmetros internos das câmeras, os parâmetros relativos entre câmeras e os
coeficientes de distorção, necessários para eliminar distorções radiais produzidas pelas
lentes das câmeras. Para tal foi utilizado o método de Zhang [Zhang 2000], já implementado no OpenCV, cujos resultados pode ser verificados abaixo. A matrix M, chamada
de matriz de câmera ou matriz de parâmetros intrínsecos, contém uma estimativa dos
parâmetros internos das câmeras, os quais possuem valores praticamente iguais para ambas as câmeras.

fx

M= 0
0
 

0 cx
439, 581
0
159, 044
f y cy  = 
0
439, 581 113, 12 
0 1
0
0
1
(6.1)
onde fx = fy é a distância focal das câmeras, cx e cy são as coordenadas o centro da
imagem. Os eixos de coordenadas das câmeras estão relacionados de acordo com a
Equação 6.2.
6.3. ESTIMATIVA DAS INCERTEZAS VISUAIS
Pl = RT (Pr − T )
69
(6.2)
R e T são, respectivamente, a matrix de rotação e o vetor de translação entre as câmeras.
Com a etapa de calibração estéreo os seguintes valores foram computados:


0, 999 0 −0, 009

1
0
R= 0
(6.3)
0, 009 0 0, 999


−6, 23
T =  0, 177 
(6.4)
−0, 227
O vetor de translação entre câmeras, T , tem os seus valores expressos em centímetros.
Esses parâmetros são de fundamental importância para o cálculo das coordenadas em
relação ao espaço 3D dos pontos capturados pelas câmeras. Além desses, foram estimados
os coeficientes de distorção, os quais são empregados na correção dos efeitos de distorção
das imagens e na etapa de retificação das imagens, realizado pelo algoritmo de Bouguet
[Bradski & Kaehler 2008].
6.3 Estimativa das Incertezas Visuais
Como explicado no capítulo anterior, existem duas fontes de erros importantes, que
podem afetar significativamente a qualidade ou confiabilidade do mapa de disparidade
em um sistema de visão estéreo: efeito de escorço e desalinhamento. Para aferir essas
medidas, experimentos no processo de estimação de mapas de dispadidade foram realizados, considerando as imagens capturadas durante a exploração dos diferentes ambientes
mapeamdos. O resultado dessa análise, considerando as formulações explicadas no Capítulo 5, seção 5.5.3, podem ser contemplados em seguida, onde consta as médias dos dados
estimados.
∆e f = 0, 04
(6.5)
∆em = 0, 2
(6.6)
Relembrando, ∆e f representa o efeito de escorço e ∆em identifica o erro causado pelo
deslinhamento vertical do sistema estéreo. Essas duas grandezas são combinadas para
resultar na estimativa do incremento de disparidade, ∆d, dado em medidas de pixels,
como mostra a Equação 6.7.
∆d = ∆e f + ∆em = 0, 04 + 0, 2 = 0, 24
(6.7)
Essas estimativas entram no tratamento estocástico dado às medições sensoriais visuais nos cálculos da probabilidade de ocupação e da elevação no mapa 2,5-D apresentado
neste trabalho.
70
6.4
CAPÍTULO 6. EXPERIMENTOS E RESULTADOS
Tratamento de Incoerências no Valor de Elevação
Um desafio nos mapas 2,5-D de elevação é representar de forma coerente lugares
que possuem passagens abaixo de alguma estrutura, por exemplo, pontes, dutos, mesas,
bancadas, entre outros. A Figura 6.2 ilustra uma situação semelhante às descritas.
Figura 6.2: Cena de uma possível passagem: (a) Mesa de computador; (b) Imagem capturada pela câmera do robô; (c) Mapa de disparidade estimado.
Nesta figura o robô se depara com uma mesa de escritório, a qual possui uma área
abaixo de sua estrutura não ocupada por obstáculos, e que pode servir de passagem para
o robô, dependendo de suas dimensões físicas. Na maioria dos trabalhos com mapas de
elevação, essa situação geraria um mapa que desconsideraria essa possibilidade de passagem. Um mapa de elevação tradicional não refletiria a real condição de navegabilidade
do ambiente, visto que o robô utilizado no trabalho poderia passar pela área vazia por
baixo da estrutura da mesa.
Para contornar situações como essas, foi desenvolvida uma heurística simples para
identificar quando um local do ambiente possui estruturas com lacunas ou passagens possíveis de serem exploradas pelo robô que mapeia o ambiente. Durante o mapeamento,
os obstáculos detectados acima da altura do robô não foram computados no mapa de
ocupação-elevação, pelo fato de que eles não fazem parte do espaço navegável do robô.
Considerando a mesma situação mostrada na Figura 6.2, foi aplicada a heurística proposta, onde o resultado pode ser visualizado na Figura 6.3.
6.4. TRATAMENTO DE INCOERÊNCIAS NO VALOR DE ELEVAÇÃO
71
(a)
(b)
(c)
Figura 6.3: Mapas estimados: (a) Valores de ocupação; (b) valores de elevação sem
heurística; (c) valores de elevação com heurística.
A subfigura 6.3(a) traz os valores de ocupação da cena mostrada na Figura 6.2, estimados a partir do processo de mapeamento explicado do capítulo anterior. A barra de
cores ao lado identifica a probabilidade de ocupação das células de acordo com a cor,
células com tendência ao azul escuro representam áreas possivelmente livres; as células
com tendência ao vermelho são as áreas que têm maior probabilidade de estar ocupadas
por obstáculos; e as células em verde ilustram os lugares ainda não mapeados. O ponto
em preto representa o lugar no qual o robô estava no momento da captura da imagem.
As subfiguras 6.3(b) e 6.3(c) representam os valores de elevação sem heurística e com
heurística respectivamente, estimados a partir do cenário da Figura 6.2. Os valores de
elevação são identificados de acordo com a barra de cores. Assim, células em azul mais
escuro representam áreas com pouca ou nenhuma elevação e células mais avermelhadas
esboçam áreas com elevações acentuadas, considerando a navegabilidade do ambiente
para o robô utilizado. O robô com a sua câmera está representado pelos polígonos em
cinza. Na subfigura 6.3(b) a mesa de escritório é representada por várias células com
valores de elevação que chega a aproximadamente 1m. A área livre abaixo da estrutura é
considerada obstáculo, o que não reflete a real condição de navegabilidade do espaço. Já
na subfigura 6.3(c), resultante da aplicação da heurística adotada, percebe-se que há um
CAPÍTULO 6. EXPERIMENTOS E RESULTADOS
72
espaço livre entre células que possuem valores de elevação acentuados, o que permite o
deslocamento do robô por esse trecho. Neste caso, com base nos resultados da heurística
proposta, o robô pode transitar por baixo da mesa.
6.5
Experimento em Ambiente Interno
Neste e nos demais experimentos, foi utilizada uma estrutura de mapeamento com
células de 10 × 10cm, valores considerados adequados para alcançar uma representação
relativamente detalhada [Souza 2008]. O tempo de processamento de um mapa local,
construído a partir de um mapa de disparidade computado, foi em média de 20ms. É
importante ressaltar que o trabalho não está focado em como o mapa de disparidade foi
estimado, portanto não é considerado o tempo de processamento necessário na inferência
do mapa de disparidade.
Este experimento foi realizado nas dependências do Laboratório de Engenharia de
Computação e Automação da Universidade Federal do Rio Grande do Norte. O objetivo
foi apresentar o mapeamento de um ambiente estruturado tipicamente encontrado em espaços interiores. Nesta experiência o robô mapeou uma parte de um corredor habitado por
alguns obstáculos (armários e terminal de consulta). A Figura 6.4 mostra cenas distintas
encontradas pelo robô durante o mapeamento do corredor e a Figura 6.5 apresenta uma
visão superior (Google Earth) e detalha, através de uma planta baixa do espaço mapeado.
(a)
(b)
( c)
Figura 6.4: Cenas visualizadas pelo robô durante o mapeamento: (a) Visão do corredor e
armários presentes; (b) Portão gradeado; (c) Terminal de consultas.
6.5. EXPERIMENTO EM AMBIENTE INTERNO
73
Figura 6.5: Vistas superiores do ambiente: (a) Visão superior do prédio explorado a partir do Google Earth com latitude -5.842853 e longitude -35.197341; (b)Planta baixa do
corredor mapeado.
Neste experimento, o robô se desloca realizando o trajeto indicado pela linha tracejada da Figura 6.5, composto por movimentos lineares e angulares, o que resultou em
uma distância linear percorrida de 15,4m. A grande dificuldade no mapeamento desse
ambiente esteve no processo de estimação de mapas disparidades, visto que, o corredor
era pobre em texturas contrastantes o que dificulta significativamente a inferência de imagens de profundidade. Apesar disso, o processo de mapeamento originou uma grade de
ocupação-elevação coerente com o ambiente, podendo ser aplicada, sem dificuldades, em
uma tarefa de navegação autônoma. A Figura 6.6 exibe os resultados alcançados, onde a
subfigura 6.6(a) expressa os valores de ocupação, a subfigura 6.6(b) exibe os valores de
elevação e a subfigura 6.6(c) apresenta os valores das variâncias referentes às elevações.
Na subfigura 6.6(a) os valores de ocupação obedecem a barra de cores ao lado, a
qual identifica a probabilidade de ocupação de cada célula no mapa, variando de 0 a 1.
Logo, as regiões da figura que tendem ao vermelho representam as células (ou espaços do
ambiente) que têm maior probabilidade de estarem ocupadas por obstáculos; as regiões
em verde claro são os espaços não mapeados, cujas probabilidades de ocupação não informam se os espaços mapeados estão livres ou ocupados. Por fim, as regiões em azul
escuro representam as células com maior probabilidade de estarem livres. A linha amarela
indica o caminho real realizado pelo robô, de acordo com o modelo de movimento apresentado no capítulo anterior. Nesta mesma subfigura, o círculo em amarelo representa o
mapeamento da entrada verificada pela porta aberta ilustrada na subfigura 6.5(a) e o círculo preto representa o mapeamento do portão existente no corredor (ver subfigura 6.4(b)
e subfigura 6.5(b)), o qual tinha uma de suas partes aberta.
A subfigura 6.6(b), contendo os valores de elevação, segue as especificações da barra
de cores ao lado. As células mais avermelhadas representam os prováveis obstáculos
com maior altura, no caso, foram limitados à uma altura de até 80 cm. As células com
tendência a cor azul representam os lugares com elevações mais baixas, incluindo as que
estão no nível do plano do solo. A subfigura 6.6(c) apresenta os valores das variâncias
das elevações estimadas, que podem ser consideradas como medidas de confiabilidade
74
CAPÍTULO 6. EXPERIMENTOS E RESULTADOS
Figura 6.6: Mapeamento em grade de ocupação-elevação para o ambiente interno.
(a)Valores de ocupação. (b) Valores de elevação; (c) Variância das elevações.
6.6. EXPERIMENTO EM AMBIENTE EXTERNO
75
sobre a altura dos obstáculos. Neste caso, o mapa apresenta variâncias baixas, o que
significa que as medidas de elevação são relativamente precisas. Assim, em uma tarefa de
navegação, o robô pode verificar se um determinado local, possivelmente ocupado por um
obstáculo, com uma determinada altura, oscilando no intervalo definido pela sua medida
de variância, pode ser superado.
Caso esse mesmo ambiente fosse mapeado em uma grade de ocupação tridimensional,
como proposto por Andert (2009) e limitando-se o mapeamento de obstáculo até a altura
do robô (80 cm), seria necessária uma estrutura de dados com 250 × 50 × 8 = 100 mil
posições, já na abordagem apresentada neste trabalho foi necessária uma estrutura de
250 × 50 × 3 = 35.750 posições, que pode ser usada para mapear além da altura máxima
do robô sem a necessidade de mais memória.
6.6 Experimento em Ambiente Externo
Para validar o método de mapeamento apresentado também em ambientes externos,
foi realizado um novo experimento em um espaço contendo algumas peculiaridades dos
espaços exteriores. Neste experimento o robô teve de lidar com arbustos, postes e com um
terreno mais irregular. A Figura 6.7 mostra algumas imagens captadas pelo robô durante
o seu trajeto no mapeamento.
A Figura 6.8 exibe uma visão geral do espaço mapeado, destacando os principais
obstáculos encontrados. Na subfigura 6.8(b) os círculos verdes representam os arbustos
e árvores presentes no cenário os pequenos quadrados marrons representam os postes
de concreto e a área amarelada identifica o terreno arenoso. A linha tracejada mostra o
caminho aproximado realizado pelo robô. O resultado do mapeamento executado pode
ser visualizado na Figura 6.9. A subfigura 6.9(a) apresenta os valores de ocupação, a
subfigura 6.9(b) mostra os valores de elevação e a subfigura 6.9(c) exibe os valores de
variâncias das elevações. A linha em amarelo na subfigura 6.9(a) representa o trajeto real
realizado pelo robô calculado pelo modelo cinemático de odometria.
Da mesma forma que no experimento anterior, para cada subfigura as barras de cores
laterais identificam os valores das grandezas representadas. O mapa de ocupação-elevação
construído representa de forma concisa o ambiente real, incluindo seus obstáculos inerentes, como, os arbustos e colunas de concreto. Nas subfiguras 6.9(a) e 6.9(b) estão
destacados alguns lugares específicos, cujas cenas podem ser visualizadas. A elipse em
amarelo corresponde ao mapeamento do espaço mostrado na subfigura 6.7(a), a elipse
em branco representa o mapeamento da cena identificada na subfigura 6.9(d) e o círculo
em vermelho representa o mapeamento da cena vista na subfigura 6.9(e). Nota-se que os
obstáculos foram detectados sem problemas, e a estimativa de suas alturas foram computadas de forma coerente ao cenário real.
Nota-se também, na subfigura 6.9(b), que para as coordenadas x > 200 aparecem mais
regiões com elevações entre 0,1m e 0,2m, próximas ao caminho do robô. Isso ocorre devido as irregularidade do terreno arenoso na região mapeada. Porém, seguindo a trajetória
realizada pelo robô a elevação do terreno favorece a navegação livre, ou seja, não existem
elevações significativas no caminho do robô. Isso acontece devido às maiores quantidades
CAPÍTULO 6. EXPERIMENTOS E RESULTADOS
76
(a)
(b)
(c)
(d)
(e)
(f)
Figura 6.7: Imagens capturadas pelo robô durante o mapeamento.
de informações sensoriais estarem nas regiões frontais ao sistema de câmeras, o que possibilita a atualização frequente do mapa com mais dados oriundos do sensor. Fazendo
a mesma comparação do experimento anterior, considerando uma grade tridimensional
apresentada por Andert (2009), seria necessária uma estrutura de 280 mil posições, enquanto que o mapa construído com o método proposto foi gravado em uma estrutura de
105 mil posições.
6.7
Experimento em Ambiente Misto
Para este experimento foi escolhido um ambiente misto, que apresenta cenas típicas
de cenários internos e de espaços externos, situado no Núcleo de Tecnologia da Univer-
6.7. EXPERIMENTO EM AMBIENTE MISTO
77
12,6m
(a)
(b)
Figura 6.8: Ambiente externo mapeado: (a) Visão superior do ambiente, limitado pelo
retângulo em amarelo (visão do Google Earth) de latitude -5.842677 e longitude 35.19724; (b) Planta baixa.
sidade Federal do Rio Grande do Norte. A subfigura 6.10(a), tomada do Google Earth,
mostra uma visão superior do ambiente mapeado com a trajetória executada pelo robô,
representada pela linha tracejada. O ponto amarelo ilustra o local de partida e o ponto
em ciano identifica a posição de finalização do mapeamento. A planta baixa mostrada
na subfigura 6.10(b) identifica estruturalmente o ambiente mapeado. Os círculos verdes
identificam pequenas plantas no solo, os círculos negros representam jarros de plantas e
os pequenos retângulos são bancas de assento.
Durante o mapeamento o robô se depara com cenas típicas de ambientes internos,
como corredores, bem como imagens vistas em ambientes externos (plantas), a Figura 6.11
ilustra essas situações. Percebe-se pelas imagens da Figura 6.11 que, como consequência das mudanças de cenários, existe uma brusca mudança de iluminação, o que afeta de
forma expressiva a qualidade dos mapas de disparidade, mesmo com o ajuste de brilho automático disponível para as câmeras. Esse efeito, prejudica a interpretação desses dados
para o cálculo das informações de profundidade.
Apesar dos diferentes cenários encontrados pelo robô e das bruscas mudanças de iluminação ocorridas durante o mapeamento, o que resulta distintas situações e dificuldades
na estimação do mapa de disparidade, o método proposto apresentou resultado interessantes, como podem ser vistos na Figura 6.12. A subfigura 6.12(a) mostra o mapa dos
valores de ocupação e a subfigura 6.12(b) os valores de elevação. As elipses vermelhas
marcadas nas figuras destacam o mapeamento da região típica de um ambiente interno
(subfigura 6.11(a)), e os círculos em preto (no mapa de ocupação) e em amarelo (no mapa
de elevação) evidenciam o mapeamento do cenário típico de um ambiente externo (subfigura 6.11(c)). Esta generalidade de aplicações (ambiente com cenas estruturadas e não
estruturadas) é uma característica interessante do método de mapeamento apresentado
neste trabalho, mostrando sua utilidade em diferentes situações práticas.
Comparando-se ao mapeamento em grade de ocupação 3D, é necessária uma grade
3D com 500 mil posições, enquanto que com o mapa de ocupação-elevação proposto
utilizou-se uma estrutura de 187.500 posições.
78
CAPÍTULO 6. EXPERIMENTOS E RESULTADOS
12,6m
(a)
(b)
(c)
Figura 6.9: Mapeamento em grade de ocupação-elevação para o ambiente externo:
(a)Valores de ocupação. (b) Valores de elevação; (c) Variância das elevações.
6.7. EXPERIMENTO EM AMBIENTE MISTO
jardim
79
salas
15,4m
jardim
salas
(a)
(b)
Figura 6.10: Vista superior do ambiente mapeado: (a) vista do Google Earth de latitude
-5.842677 e longitude -35.19724; (b) Planta baixa.
(a)
(c)
(b)
(d)
Figura 6.11: Diferentes cenas encontradas durante o mapeamento: (a) e (b) Cenas de
ambiente interno. (c) e (d) Cenas de ambiente externo.
80
CAPÍTULO 6. EXPERIMENTOS E RESULTADOS
15,4m
(a)
(b)
(c)
Figura 6.12: Resultado do mapeamento do ambiente misto: (a) Valores de ocupação; (b)
Valores de elevação.(c) Variância das elevações.
6.8. COMPARAÇÕES
81
6.8 Comparações
Nesta seção, é feita uma comparação da quantidade de espaço de memória necessário
para o armazenamento dos mapas em grade de ocupação 3D e os mapas em grade de
ocupação-elevação propostos neste trabalho. As comparações serão consideradas sobre
os ambientes mapeados nos experimentos exibidos e explicados, variando a altura limite
do mapeamento. Para todas as condições de mapeamento foi utiliza uma dimensão padrão
para as células de 10 × 10 cm. De acordo com as comparações realizadas na Tabela 6.1,
quanto maior o limite de altura do mapeamento maior o nível de redução de memória.
Isto é, quanto mais alto se deseja mapear, maior a quantidade de memória necessária para
uma grade de ocupação 3D, enquanto que uma grade de ocupação-elevação tem o seu
custo estável. A sigla G.O. significa Grade de Ocupação e G. O-E significa Grade de
Ocupação-Elevação.
Tabela 6.1: Comparação de requisitos de memória.
Experimento
Limite
Num. de elem. Num. de elem.
de altura (cm)
(G. O. 3D)
(G.O-E)
Exp. 1
80
100 mil
37,5 mil
Dim: 25x5m
100
125 mil
37,5 mil
Cel: 10cm
150
187,5 mil
37,5 mil
Exp. 2
80
280 mil
105 mil
Dim: 35x10m
100
350 mil
105 mil
Cel: 10cm
150
525 mil
105 mil
Exp. 3
80
500 mil
187,5 mil
Dim: 25x25m
100
625 mil
187,5 mil
Cel: 10cm
150
937,5 mil
187,5 mil
Redução
de Memória
62,5%
70 %
80%
62,5%
70 %
80%
62,5%
70 %
80%
6.9 Análise Geral dos Resultados
Neste capítulo, foram apresentado vários experimentos realizados com diferentes situações a fim de validar o método de mapeamento proposto. O sistema foi testado em um
ambiente interno, em um ambiente externo e em um ambiente “misto” com peculiaridades
de ambientes internos e externos. Em todos os casos os mapas resultantes se mostram coerentes com o ambiente real mapeado, mesmo com as dificuldades apresentadas, como por
exemplo, iluminação e falta de textura, fatores esses que influenciam a qualidade dos mapas de disparidade. Além disso, é importante ressaltar a redução expressiva do uso de
memória com o método de mapeamento proposto em relação a grade de ocupação 3D,
principalmente quando o mapeamento pondera a representação de estruturas altas.
82
CAPÍTULO 6. EXPERIMENTOS E RESULTADOS
Capítulo 7
Conclusão e Perspectivas
O problema de mapeamento de ambientes através de robô móveis é uma etapa fundamental em direção ao alcance da autonomia. Com uma descrição espacial do seu ambiente
(mapa), indicando a localização de estruturas e obstáculos, um robô pode ser programado
para realizar diferentes tarefas como, desvio de obstáculos, planejamento de caminhos,
localização, exploração, reconhecimento de objetos, limpezas, resgate, combate a incêndios, entre outras.
Diante dessa necessidade, o presente trabalho apresentou uma solução para o mapeamento de ambientes internos e/ou externos com informações tridimensionais, baseadas
em informações sensoriais de distâncias, no presente caso, fornecidas pelo processamento
de imagens capturadas por um sistema de visão estéreo. O mapa em uma grade regular armazena informações de ocupação e elevação dos ambientes mapeados possibilitando que
um robô possa tomar decisões se um local específico pode ser explorado ou não, de acordo
com a probabilidade de ocupação, a elevação dos obstáculos e sua variância. Ouseja, o
robô pode classificar a navegabilidade do terreno do seu ambiente. O mapeamento apresentado considera uma modelagem estocástica a fim de que as informações ruidosas de
robô e sensor sejam tratadas de forma adequada. Tal tratamento se dá por meio de uma
análise robusta das principais fontes de erros no cálculo das informações sensoriais.
O processo de mapeamento que foi descrito obedece uma sequencia de passos: 1)
Cálculo das coordenadas e orientação do robô em relação ao seu ambiente através do
modelo de movimento de odometria. 2) Aquisição e interpretação de dados sensoriais
através de uma câmera estéreo, contendo informações sobre o entorno do robô; 3) Modelagem do comportamento sensorial para a interpretação dos dados da etapa anterior em
informações sobre ocupação e elevação. 4) Integração de dados através de equações estocásticas, responsáveis por integrar as novas medições interpretadas às informações já
existentes sobre a ocupação e elevação das células.
Na validação do mapeamento proposto foram realizados experimentos com um robô
real Pioneer 3-AT equipado com um sistema de visão estéreo de baixo custo (Minoru 3D),
onde procurou-se comprovar a factibilidade do mapeamento para diferentes tipos de ambientes, apresentando distintas situações. Os resultados obtidos se mostraram coerentes à
realidade dos ambientes mapeados consolidando assim, o método proposto. É importante
frisar que o arcabouço de mapeamento proposto pode perfeitamente ser adaptado para
ser utilizado com outros tipos de sensores além das câmeras, como por exemplo, lasers e
kinect.
84
CAPÍTULO 7. CONCLUSÃO E PERSPECTIVAS
Diante disso, a principal contribuição científica desse trabalho relaciona-se com o
desenvolvimento de uma solução para o mapeamento probabilístico de ambientes com
informações 3D, utilizando uma estrutura de dados bidimensional para o armazenamento
do modelo, chamado de grade de ocupação-elevação. Diferentemente das abordagens existentes na literatura, cada célula do mapa construído tem uma função de probabilidade
que remete informações de ocupação, uma média da altura dos obstáculos e a variância da altura, indicando a precisão da medição de altura. Com isso, torna-se possível a
identificação de obstáculos possíveis de serem transpostos a partir do mapa construído.
Além disso, foi realizada uma modelagem probabilística do sistema de visão estéreo, com
identificação das principais fontes de incertezas, o que implica na construção de um mapa
coerente com as informações sensoriais ruidosas.
Considera-se o modelo apresentado uma interessante alternativa para o problema de
navegação de ambientes com desvio e/ou transposição de obstáculos.
Com relação às perspectivas, relacionadas com trabalhos que ainda deverão ser realizados, pretende-se:
1. Testar a abordagem de mapeamento proposta com outros tipos de sensores a fim de
que o sistema seja utilizado em outras plataformas robóticas;
2. Investigar a possibilidade de fusão de células com o objetivo de diminuir ainda mais
a estrutura necessária para armazenar os mapas, tornando-os mais compactos;
3. Adaptar o mapeamento proposto ao problema do SLAM (Simultaneous Localization and Mapping), ponderando sua aplicação em ambientes internos e externos;
4. Serão investigadas as abordagens baseadas no filtro de partículas, como FastSLAM
[Hähnel et al. 2003] e o Rao-Blackwellized particle filter para SLAM [Grisetti
et al. 2007] adequado para mapas em grades;
5. Evoluir a técnica de SLAM para um sistema de localização, mapeamento e planejamento simultâneos (SPLAM), dado que o mapa em grade favorece a aplicação de
algoritmos de planejamento de caminhos de forma direta.
Referências Bibliográficas
Agrawa, M., K. Konolige & R. C. Bolles (2007), Localization and mapping for autonomous navigation in outdoor terrains : A stereo vision approach, em ‘IEEE Workshop on Application of Computer Vision’.
Ahn, S., K. Lee, W. K. Chung & S.-R. Oh (2007), Slam with visual plane: Extracting vertical plane by fusing stereo vision and ultrasonic sensor for indoor environment, em
‘Proc. Of IEEE International Conference on Robotics and Automation’, pp. 4787–
4794.
Aires, K. R. T. & A. A. D. Medeiros (2010), A plane segmentation system based on affine
homography and optical, em ‘Proc. of Conference on Graphics, Petterns and Images
(SIBIGRAPI)’, pp. 346–352.
Alsina, Pablo J., Luiz M. G. Gonçalves, Adelardo A. D. Medeiros, Diogo P. F. Pedrosa &
Frederico C. Vieira (2002), Navegação e controle de robôs móveis, em ‘Mini-Curso:
Congresso Brasileiro de Automática (CBA)’.
Andert, F. (2009), Drawing stereo disparity images into occupancy grids: Measurement
model and fast implementation, em ‘Proc. Of IEEE International Conference on
Intelligent Robots and Systems’, pp. 5191–5197.
Angelopoulou, E., T. Hong & A. Wu (1992), World model representation for mobile
robots, em ‘In Proc. of Intelligent Vehicles ’92 Symposium’, pp. 293–297.
Aroca, R. V. & L. M .G. Gonçalves (2012), ‘Method for reading sensors and controlling
actuators using audio interfaces of mobile devices’, Sensors pp. 1572–1593.
Bares, J., M. Hebert, T. Kanade, E. Krotkov, T. Mitchell, R. Simmons & W. R. L. Whittaker (1989), ‘Ambler: An autonomous rover for planetary exploration’, IEEE Computer Society Press 22(6), 18–22.
Blanco, J.-L., J.-A Fernandez-Madrigal & J. Gonzalez (2008), ‘Toward a unified bayesian
approach to hybrid metric-topological slam’, IEEE Transactions on Robotics
24(2), 259–270.
Bradski, G. & A. Kaehler (2008), Learning OpenCV: Computer Vision with the OpenCV
Library, O’Reilly Media.
85
86
REFERÊNCIAS BIBLIOGRÁFICAS
Cappalunga, A., S. Cattani, A. Broggi, M. S. McDaniel & S. Dutta (2010), Real t ime 3d
terrain elevation mapping using ants optimization algorithm and stereo vision, em
‘Proc. of IEEE Intelligent Vehicles Symposium, University of California’, pp. 21–
25.
Chang, H.-H., S.-Y. Lin & Y.-C. Chen (2010), Slam for indoor envinonment using stereo
vision, em ‘Proc. of Second WRI Global Congress on Intelligent Systems(GCIS)’,
pp. 266–269.
Cherubini, A. & F. Chaumette (2011), Visual navigation with obstacle avoidance, em
‘Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems’,
pp. 1593–1598.
Choi, Y.-H & S.-Y Oh (2006), Grid-based visual slam in complex environment, em
‘Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems’,
pp. 2563–2569.
Choset, H. & D. Fox (2004), The world of mapping, em ‘Proc. of the Workshop on Review
of United States Research in Robotics - National Science Foundation (NSF).’.
Civera, J., A. J. Davison & M. Montiel (2008), ‘Inverse depth parametrization for monocular slam’, IEEE Transactions on Robotics 24(5), 932–945.
Davison, A. (2002), Slam with a single camera, em ‘SLAM/CML Workshop at International Conference on Robotics and Automation’.
Davison, A. (2003), Real-time simultaneous localization and mapping with a single camera, em ‘IEEE International Conference on Computer Vision’, Vol. 2, pp. 1403–
1410.
Davison, A., I. D. Reid, N. D. Molton & O. Stasse (2007), ‘Monoslam: Real-time single camera slam’, IEEE Transaction on Pattern Analysis and Machine Intelligence
29(6).
de Saint Vincent, A. (1987), Visual navigation for a mobile robot building a map of the
occupied space from sparse 3d stereo data, em ‘Proc. of IEEE Int. Conf. on Robotics
and Automation’, Vol. 4, pp. 1429–1435.
Dryanovski, I., W. Morris & J. Xiao (2010), Multi-volume occupancy grids: an efficient
probabilistic 3d mapping model for micro aerial vehicles, em ‘Proc. of IEEE/RSJ
International Conference on Robotics and Systems’, pp. 1553–1559.
Dryanovski, I., W. Morris & J. Xiao (2011), Multi-volume occupancy grids: an efficient
probabilistic 3d mapping model for micro aerial vehicles, em ‘Proc. of IEEE/RSJ
International Conference on Intelligent Robots and Systems’, pp. 1553–1559.
Einhorn, E., C. Schröter & H.-M. Gross (2011), Finding the adequate resolution for grid
mapping - cell size locally adapting on-the-fly, em ‘Proc. of IEEE International Conference on Robotics and Automation’, pp. 1843–1848.
REFERÊNCIAS BIBLIOGRÁFICAS
87
Elfes, A. (1987), ‘Sonar-based real-world mapping and navigation’, IEEE Journal of
Robotics and Automation 3(3), 249–265.
Elfes, A. (1989), Occupancy Grid: A Probabilistic Framework for Robot Perception and
Navigation, Tese de doutorado, Carnegie Mellon University, Pensylvania, USA.
Gallelos, G. & P. Rives (2010), Indoor slam based on composite sensor mixing laser
scans and omnidirectional images, em ‘Proc. of IEEE International Conference on
Robotics and Automation’, pp. 3519–3524.
Georgiev, K., R. T. Creed & R. Lakaemper (2011), Fast plane extraction in 3d range
data based on line segments, em ‘Proc. of IEEE/RSJ International Conference on
Intelligent Robots and Systems’.
Goldstein, M., F. Pin, G. Saussure & C. Weisbin (1987), 3d world modeling based on
combinatorial geometry for autonomous robot navigation, em ‘Proc. of IEEE Int.
Conf. on Robotics and Automation’, Vol. 4, pp. 727–733.
Gonçalves, L., R. Grupen, A. Oliveira, D. Wheeler & A. Fagg (2000), ‘Tracing patterns
and attention: Humanoid robot cognition’, The Intelligent Systems and their Applications 15(1).
Grisetti, G., C. Stachniss & W. Burgard (2007), ‘Improved techniques for grid mapping
with rao-blackwellized particle filters’, IEEE Transactions on Robotics 23.
Gupta, V., G. Singh, A. Gupta & A. Singh (2007), Occupancy grid mapping using artificial neural networks, em ‘Proc. of 2010 International Conference on Industrial
Electronics, Control and Robotics’, pp. 247–250.
Hahnel, D. (2004), Mapping with Mobile Robots, Tese de doutorado, University of
Freiburg, Freiburg, Germany.
Hebert, M., C. Caillas, E. Krotkov, I. S. Kweon & T. Kanade (1989), Terrain mapping
for a roving planetary explorer, em ‘Proc. of the IEEE International Conference on
Robotics and Automation’, pp. 997–1002.
Hines, W. W., D. D. Montgomery, D. M. Goldsman & C. M. Borror (2006), Probabilidade
e Estatística na Engenharia, 4a edição, Ed. LTC, Rio de Janeiro-RJ.
Hong, L. & G. Chen (2004), Segment-based stereo macthing using graph-cuts, em ‘Proc.
Of EEE Computer Society Conference on Computer Vision and Pattern Recognition,
CVPR’, Vol. 1, pp. 74–81.
Hygounenc, E., I.-K. Jung, P. Souères & S. Lacroix (2004), ‘The autonomous blimp
project of laas-cnrs: Achievements in flight control and terrain mapping’, International Journal of Robotics Research 23(4-5), 473–511.
88
REFERÊNCIAS BIBLIOGRÁFICAS
Hähnel, D., D. Fox, W. Burgard & S. Thrun (2003), A highly efficient fastslam algorithm for generating cyclic maps of large-scale environments from raw laser range
measurements, em ‘Proc. Conference on Intelligent Robots and Systems (IROS)’.
Johannsson, H., M. Kaess, B. Englot, F. Hover & J. Leonard (2010), Imaging sonar-aided
navigation for autonomous underwater harbor, em ‘Proc. of IEEE/RSJ International
Conference on Intelligent Robots and Systems’, pp. 4396–4403.
Kalman, R. E. (1960), ‘A new approach to linear filtering and predictive problems’, Transactions of the Journal of Basic Engineering pp. 35–45.
Kim, W. S., A. I. Ansar & R. D. Steele (2005), Performance analysis and validation of a
stereo vision system, em ‘Proc. of IEEE System, Man and Cybernetics’.
Konrad, M., M. Szczot, F. Schule & K. Dietmayer (2011), Generic grid mapping for road
course estimation, em ‘Proc. of IEEE Intelligent Vehicles Symposium’.
Kriegman, D., E. Triendl & T. Binfold (1987), A mobile robot: Sensing, planning and
locomotion, em ‘Proc. of IEEE Int. Conf. on Robotics and Automation’, Vol. 4,
pp. 402–408.
Kuipers, B. & Y.-T. Byun (1988), A robust, qualitative method for spatial learning in
unknown environments, em ‘Proc. of AAAI-88’, pp. 1–12.
Kwon, T.-B, J.-B. Song & S.-H. Joo (2010), ‘Elevation moment of inertia: A new feature
for monte carlo localization in outdoor environment with elevation map’, Journal of
Field Robotics 27(3), 371–386.
Lacroix, S., A. Mallet, D. Bonnafous, G. Bauzil, S. Fleury, M. Herrb & R. Chatila (2002),
‘Autonomous rover navigation on unknown terrains: Functions and integration’, International Journal of Robotics Research 27, 917–942.
Lai, X. C., S. S. Ge, P. T. Ong & A. Mamun (2006), Incremental path planning using
partial map information for mobile robots, em ‘Proc. of International Conference on
Control, Automation, Robotics and Vision’, pp. 1–6.
Lee, S.-J. & J.-B. Son (2010), A new sonar salient feature structure for ekf-based slam, em
‘In Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems’,
pp. 5966–5971.
Lemaire, T., C. Berger, I.-K. Jung & S. Lacroix (2007), ‘Vision-based slam: Stereo and
monocular approaches’, International Journal of Computer Vision 74(3), 343–364.
Li, Z.-N. & G. Hu (2002), ‘Analysis of disparity gradient based cooperative stereo’, IEEE
Transactions on Image Processing 5(11), 1493–1506.
Liu, Y., R. Emery, D. Chakrabarti, W. Burgard & S. Thrun (2001), Using EM to learn 3D
models with mobile robots, em ‘Proc. of the International Conference on Machine
Learning (ICML)’.
REFERÊNCIAS BIBLIOGRÁFICAS
89
Marjovi, A., J. G. Nunes, L. Marques & A. Almeida (2009), Multi-robot exploration
and fire searching, em ‘Proc. of IEEE/RSJ International Conference on Intellingent
Robots and Systems’, pp. 1929–1934.
Marks, T., A. Howard, M. Bajracharya, G. Cotrell & L. Mathies (2009), ‘Gamma-slam:
Visual slam in unstructured environments using variance grid maps’, Journal of
Field Robotics 26(1), 26–51.
Merat, F. & F. Wu (1987), Generation of object descriptions from range data using feature
extraction by demands, em ‘Proc. of IEEE Int. Conf. on Robotics and Automation’,
Vol. 4, pp. 941–946.
Moravec, H. P. (1988), ‘Sensor fusion in certainty grids for mobile robots’, Computer
9(2), 61–74.
Moravec, H. P. (1996), Robot spacial perception by stereoscopic vision on 3d evidence
grid, Relatório Técnico CMU-RI-TR-96-34, CMU Robotics Institute, Pittsburg,
Pensylvania.
Murarka, A. & B. Kuipers (2009), A stereo vision based mapping algorithm for detecting
incline, drop-offs, and obstacles for safe local navigation, em ‘Proc. of IEEE/RSJ
International Conference on Intelligent Robotis and Systems’, pp. 1646–1653.
Ogawa, Y., N. Shimada & Y. Shirai (2007), Environmental mapping for mobile robot by
tracking sift feature points using trinocular vision, em ‘SICE Annual Conference’,
Vol. 1, pp. 1996–2001.
Pfaff, P., R. Triebel & W. Burgard (2007), ‘An efficient extension to elevation maps for
outdoor terrain mapping and loop closing’, The International Journal of Robotics
Research 26(217), 217–230.
Piniés, P., L. M. Paz, D. Gálvez-Lopes & J. D. Tardós (2010), ‘Ci-graph simultaneous
localization and mapping for three-dimensional reconstruction of large and complex
environments using a multicamera system’, Journal of Robotics 27(5), 561–586.
Pirker, K., M. Ruther, H. Bischof & G. Schweidhofer (2011), Fast and accurate environment modeling using three-dimensional occupancy grids, em ‘IEEE International
Conference on Computer Vision Workshops’, pp. 1134–1140.
Rocha, R. (2006), Building Volumetric Maps whit Cooperative Mobile Robots and Useful
Information Sharing: A Distributed Control Approach based on Entropy, Tese de
doutorado, Universidade do Porto, Porto,Portugal.
Ruhnke, M., R. Kummerle, G. Grisetti & W. Burgard (2011), Highly accurate maximum likelihood laser mapping by jointly optimizing laser points and robot poses, em
‘Proc. Of IEEE International Conference on Robotics and Automation’, pp. 2812–
2817.
90
REFERÊNCIAS BIBLIOGRÁFICAS
Santana, A. M. (2011), Localização e Mapeamento Simultâneos de Ambientes Planos
Usando Visão Monocular e Representação Híbrida do Ambiente, Tese de doutorado,
Universidade Federal do Rio Grande do Norte, Natal, Brasil.
Santana, A. M. & A. A. D. Medeiros (2011), ‘A line-based approach to slam using monocular vision’, IEEE Latin America Transaction 9(3), 231–239.
Santana, André M. & Adelardo A. D. Medeiros (2009), Contemporary Robotics - Challenges and Solutions, INTECH, capítulo Simultaneous Localization and Mapping
SLAM of a Mobile Robot Based on Fusion of Odometry and Visual Data Using
Extended Kalman Filter.
Servant, F., P. Houlier & E. Marchand (2010), Improving monocular blane-based slam
with inertial measures, em ‘IEEE/RSJ International Conference on Intelligent
Robots and Systems’, pp. 3810–3815.
Sharstein, D. & R. Szeliski (2002), ‘A taxonomy and evaluation of dense two-frame stereo
correspondence algorithms’, International Journal of Computer Vision 47(1/2/3), 7–
42.
Shi, L., S Kodagoda & G. Dissanayake (2010), Environment classification and semantic grid map building based on laser range finder data, em ‘Semantic Perception,
Mapping and Exploration (SPME) Workshop 2010’.
Siegwart, Roland & Illah R. Nourbakhsh (2004), Introduction to Autonomous Mobile
Robots, MIT Press.
Silver, D., D. Ferguson, A. Morris & S. Thayer (2004), Features extraction for topological mine maps, em ‘Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and
Systems’, pp. 773–779.
Souza, A. (2008), Mapeamento, Dissertação de mestrado, Universidade Federal do Rio
Grande do Norte, Natal, RN, Brasil.
Stachniss, C. (2006), Exploration and Mapping with Mobile Robots, Tese de doutorado,
University of Freiburg, Freiburg, Germany.
Stachniss, C. (2009), Robotic Mapping and Exploration, Springer Tracts in Advanced
Robotics.
Thrun, S. (1998), ‘Learning metric-topological maps for indoor mobile robot navigation’,
Artificial Inteligence 99(1), 21–71.
Thrun, S. (2002), Robotic mapping: A survey, Morgan Kaufmann.
Thrun, Sebastian, Wolfram Burgard & Dieter Fox (2005), Probabilistic Robotics, 1a
edição, MIT Press.
REFERÊNCIAS BIBLIOGRÁFICAS
91
Trucco, E. & A. Verri (1998), Introductory Techniques for 3D Computer Vision, PrenticeHall, USA.
Wolf, D. F, E. V. Simões, F. S. Osório & O. Trindade Junior (2009), Robótica móvel
inteligente: Da simulação às aplicações no mundo real, em ‘Mini-Curso: Jornada de
Atualização em Informática (JAI), Congresso da SBC’.
Wolf, D. & G. Sukhatme (2008), ‘Semantic mapping using mobile robots’, IEEE Transactions on Robotics and Automation 24, 244–258.
Wu, E., L. Zhao, Y. Guo & W. Zhou (2010), Monocular vision slam based on key feature
points selection, em ‘Proc. of IEEE International Conference on Information and
Automation’, pp. 1741–1745.
Wurm, K. M., A. Hornung, M. Bennewitz, C. Stachniss & W. Burgard (2010), Octomap:
A probabilistic, flexible, and compact 3d map representation for robotic systems, em
‘ICRA, Workshop on 3D Perception and Modeling’.
Xiong, Y. & L. Matthies (1997), Error analysis of a real-time stereo system, em ‘Proc. of
IEEE Computer Society Conference on Computer Vision and Pattern Recognition’,
pp. 1087–1093.
Yang, Shao-Wen & Chieh-Chih Wang (2011), Feasibility grids for localization and mapping in crowded urban scenes, em ‘Proc. of IEEE International Conference on
Robotic and Automation’, pp. 2322–2326.
Ye, C. & J. Borenstein (2003), A new terrain mapping method for mobile robot obstacle negotiation, em ‘Proc. of the UGV Technology Conference at the 2002 SPIE
AeroSense Symposium’, pp. 21–25.
Zhang, Z. (2000), ‘A fl exible new technique for camera calibration’, IEEE Transactions
on Pattern Analysis and Machine Intelligence 22, 1330–1334.
Zureiki, A., M. Devy & R. Chatila (2007), Stereo matching using reduced-graph cuts, em
‘IEEE International Conference Image Processing’, Vol. 1.