t ecnicas de vis~ao aplicadas a navegac ~ao em rob otica m ovel

Universidade de Coimbra
Faculdade de Ci^encias e Tecnologia
Departamento de Engenharia Electrotecnica
~ APLICADAS A
TECNICAS DE VISAO
~ EM ROBOTICA
NAVEGACAO
MOVEL
Tese de Mestrado
Inacio de Sousa Adelino da Fonseca
Licenciado em Engenharia Electrotecnica
Coimbra
Marco de 1998
ii
Dissertac~ao
submetida ao Departamento de Engenharia Electrotecnica
da Universidade de Coimbra
satisfazendo parcialmente os requisitos
para a obtenc~ao do grau de
mestre
iii
iv
Trabalho desenvolvido sob orientaca~o do Dr. Jorge Manuel Miranda Dias - professor
Auxiliar do Departamento de Engenharia Electrotecnica da Universidade de Coimbra
v
vi
Agradecimentos
Desejo dar os meus agradecimentos:
Dr. Jorge Dias, que me disponibilizou o seu apoio, orientac~ao, e o material necessario
para efectuar este trabalho.
Eng. Paulo Peixoto pelo apoio e discuss~ao sobre o problema da determinac~ao do
uxo optico, e ajudas sobre o sistema FreeBSD.
Eng. Paulo Menezes, pela sua ajuda com alguns problemas de instalaca~o do FreeBSD.
a todo o pessoal do ISR, em especial ao Eng. Jorge Batista.
Eng. Lus Almeida, pelo seu apoio e interesse, e pela sua ajuda nos problemas de
hardware que foram aparecendo.
a todo o pessoal do laboratorio, por partilharem muitas horas de trabalho.
Eng. Rui Cortes~ao, pelo seu apoio e amizade ao longo deste tempo. E pela sua
ajuda na teoria de ltros de Kalman, LATEX, FreeBSD.
ao ISEC, onde eu trabalho, que me deu o suporte nanceiro para efectuar esta tese.
ao PRODEP, que me nanciou de 20 Dezembro de 1995 a 20 de Setembro de 1996.
ao meu amigo Lus Marques e esposa, por aqueles pequenos detalhes.
ao meu amigo Emlio, esposa e a pequena lhota In^es.
vii
a Fatima, Susana, Cristina, Nuno Cid, Pedro, ...
a todos os meus amigos, e a minha famlia.
viii
Resumo
O desenvolvimento de sistemas roboticos de elevada exibilidade esta fortemente dependente do estado de desenvolvimento dos sistemas sensoriais. Actualmente esta a ser efectuado um grande esforco de investigac~ao para que os sistemas roboticos sejam autonomos
a nvel das decis~oes de alto nvel a executar. No campo dos sistemas sensoriais, a vis~ao por
computador assume papel preponderante, pois permite melhorar a autonomia do sistema
tal como se prova pelos resultados experimentais apresentados neste trabalho.
Nesta tese, pretende-se apenas estudar o problema da navegaca~o com um robot movel,
utilizando vis~ao.
O problema da navegaca~o pode ser estudado de diferentes perspectivas. Uma passa
pelo reconhecimento de pontos de refer^encia (\landmarks"), que denem locais a atingir
ou a evitar. Eventualmente, estes pontos de refer^encia podem ajudar a localizac~ao do
robot num mapa que represente o meio ambiente. Outra das perspectivas, passa pela
utilizac~ao de informaca~o din^amica, i.e., utilizaca~o de medidas da velocidade em imagens.
Neste trabalho optou-se pela segunda alternativa, baseando o processo de navegac~ao
no controlo das velocidades de rotaca~o e translaca~o do veculo, usando a informac~ao
visual. As soluc~oes apresentadas s~ao baseadas no uxo optico medido em duas c^amaras,
e a diferenca entre ambos os uxos medidos permite controlar a atitude do robot movel.
O objectivo principal e a obtenca~o de algoritmos que possam ser realizados em programas
de computador mas cujo tempo de execuc~ao seja pequeno, e podendo ser utilizado na
malha de controlo de um sistema de controlo. Para obter um processo ainda mais rapido,
s~ao utilizadas imagens log-polar, onde e calculado o uxo optico.
Uma das vantagens da utilizac~ao de imagens log-polar e a facilidade da detecc~ao de
campos de velocidades divergentes, cujo modulo e directamente proporcional ao raio meix
dido relativamente ao centro da imagem. O metodo de navegac~ao descrito neste trabalho
explora uma tecnica de calculo de uxo optico, baseado num esquema multi-resoluca~o,
de modo a obter um campo de uxo de vectores velocidade com coer^encia local. S~ao
apresentados os resultados obtidos atraves de algoritmos baseados na restric~ao do brilho
(\brightness constraint") e no modelo de velocidade am, ambos aplicados a imagens
log-polar. Os algoritmos de detecca~o de uxo optico geram o sinal de erro que permite
controlar a trajectoria de um robot movel dispondo de um sistema de vis~ao activa, e que
ja foi utilizado em outros trabalhos [J. Dias e C. Paredes 95] e [J. Dias e C. Paredes 96].
Outro dos assuntos abordados neste trabalho, ainda no campo da navegac~ao, passa
pela detecc~ao da posic~ao do foco de expans~ao FOE (\Focus of Expansion"), o que permite
explorar a possibilidade de controlar a posic~ao do sensor visual segundo uma direcc~ao de
translac~ao preferida (\Navigation by prefered direction"). Esta tecnica de alinhamento
do sensor permite recuperar de uma forma mais ecaz, a informaca~o visual sobre o meio
ambiente [Alberto Elfes 95]. Note-se que tipicamente, no caso das pessoas, os olhos
mant^em-se alinhados com a direcc~ao do seu movimento, e neste caso esta tecnica simula
este comportamento.
x
Conteudo
v
Agradecimentos
vii
Resumo
ix
1 Introduc~ao
1
1.1 O enquadramento do trabalho . . . . . . . . . . . . . . . . . . . . . . .
1.1.1 Navegac~ao baseada em uxo optico normal . . . . . . . . . . . .
1.1.2 Medida de desempenho de algoritmos de calculo de uxo optico
1.1.3 Transformac~ao Log-polar . . . . . . . . . . . . . . . . . . . . . .
1.1.4 Detecc~ao do foco de expans~ao - FOE . . . . . . . . . . . . . . .
1.1.5 Detecc~ao de obstaculos e tempo ate colis~ao . . . . . . . . . . . .
1.2 A estrutura da tese . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Transformac~ao Log-polar
2.1 Perspectiva geometrica . . . . . . . . . . . . . . . . .
2.2 Transformac~ao Log-Polar . . . . . . . . . . . . . . . .
2.2.1 Transformac~oes Conformais . . . . . . . . . .
2.2.2 Transformac~ao Log-Polar generica . . . . . . .
2.2.3 Uma transformac~ao Log-polar mais elaborada
2.2.4 A transformaca~o log-polar discreta . . . . . .
2.3 Retina din^amica (ou transformaca~o log-polar
din^amica) . . . . . . . . . . . . . . . . . . . . . . . .
xi
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2
3
5
6
7
8
9
11
11
12
12
15
16
19
. . . . . . . . . . . . 21
2.4 Campo de movimento induzido numa c^amara . . . .
2.5 Algumas propriedades da transformaca~o Log-Polar .
2.5.1 Campo de movimento no plano Log-polar . .
2.6 O efeito de sub-amostragem produzido pelo log-polar
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3 Detecc~ao de Movimento nas Imagens
3.1 Campo de movimento induzido numa c^amara por uma superfcie planar . .
3.2 Calculo do uxo optico . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 Filtragem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2 Metodos que utilizam o gradiente . . . . . . . . . . . . . . . . . . .
3.2.3 Algoritmo de uxo optico normal . . . . . . . . . . . . . . . . . . .
3.2.4 Algoritmo de uxo optico usando o modelo am . . . . . . . . . . .
3.2.5 Algoritmo de uxo optico de Horn e Schunck Revisto . . . . . . . .
3.2.6 Calculo de uxo optico usando correlaca~o . . . . . . . . . . . . . . .
3.2.7 Resultados experimentais com imagens sinteticas . . . . . . . . . .
3.2.8 Medida do desempenho de algoritmos de calculo de uxo optico
em imagens log-polar e cartesianas . . . . . . . . . . . . . . . . . .
4 Determinac~ao de Par^ametros do Movimento
4.1 Introduc~ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Estimac~ao do foco de expans~ao . . . . . . . . . . . . . . . . . . .
4.2.1 Equac~oes de velocidade expressas em coordenadas polares
4.2.2 Detecc~ao da direcca~o do foco de expans~ao . . . . . . . . .
4.2.3 Detecc~ao da posica~o do foco de expans~ao . . . . . . . . . .
4.2.4 Resultados de simulaca~o . . . . . . . . . . . . . . . . . . .
4.2.5 Resultados com o sistema experimental . . . . . . . . . . .
4.2.6 Principais conclus~oes sobre a detecca~o do foco de expans~ao
4.3 Controlo do alinhamento de uma c^amara . . . . . . . . . . . . . .
5 Navegac~ao utilizando vis~ao articial
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
23
25
26
29
33
34
35
38
38
40
44
48
49
51
56
65
66
68
70
73
73
77
78
78
85
93
5.1 Introduc~ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.2 Motivac~ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
xii
5.2.1 Sensores de imagens esfericos . . . . . . . . . . . . . . .
5.2.2 Caso especial da utilizaca~o de um sistema de vis~ao activa
5.3 Navegac~ao com duas c^amaras . . . . . . . . . . . . . . . . . . .
5.4 Navegac~ao com duas c^amaras e espelhos . . . . . . . . . . . . .
5.4.1 Espelhos como simuladores de varias c^amaras . . . . . .
5.5 Resultados Simulados e Experimentais . . . . . . . . . . . . . .
5.5.1 Resultados simulados . . . . . . . . . . . . . . . . . . . .
5.5.2 Resultados experimentais . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
95
102
109
112
112
117
117
120
6 Conclus~oes e trabalho Futuro
127
A Denico~es e convenc~oes
131
B O Sistema do Robot Movel
133
C Cinematica dos sistemas autonomos utilizados
137
6.1 Conclus~oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.2 Trabalho futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
C.1 Introduc~ao . . . . . . . . . . . . . . . . .
C.1.1 Transformac~oes entre referenciais
C.1.2 Relac~oes de velocidade . . . . . .
C.2 Cinematica (directa e inversa) . . . . . .
C.2.1 Caso do sistema de vis~ao activa .
C.2.2 Caso dos Pan & Tilt . . . . . . .
C.3 Matrizes \skew symmetric" . . . . . . .
C.4 A inu^encia da velocidade angular . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
137
138
139
142
142
146
150
153
D Pormenores da realizac~ao pratica
155
E Filtros - e - -
163
E.1 Introduc~ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
E.2 Filtro - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
E.2.1 Filtro - - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
xiii
Bibliograa
167
xiv
Lista de Tabelas
2.1 Passos necessarios para estudar os par^ametros dos ltros necessarios a ltragem das imagens, antes da transformac~ao log-polar. . . . . . . . . . . . 31
3.1
3.2
3.3
3.4
3.5
Resultados para a sequ^encia \Translating Tree" usando imagens Log-Polar
Resultados para a sequ^encia \Translating Tree" usando imagens cartesianas
Resultados para a sequ^encia \Diverging Tree" usando imagens Log-Polar .
Resultados para a sequ^encia \Diverging Tree" usando imagens cartesianas
Resultados da estimac~ao do uxo optico usando imagens log-polar para
as sequ^encias de translac~ao e divergente, usando tecnicas descritas em
[J. Barron e D. Fleet 94] . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6 Aplicac~ao do metodo de Fleet a sequ^encia divergente e de translaca~o da
arvore, usando diferentes bases para a transformac~ao log-polar (mantendo
a mesma resoluca~o angular) . . . . . . . . . . . . . . . . . . . . . . . . . .
57
58
59
60
62
63
B.1 Par^ametros para controlar a velocidade da plataforma movel . . . . . . . . 133
xv
Captulo 1
Introduc~ao
O desenvolvimento de sistemas roboticos de elevada exibilidade esta fortemente dependente do estado de desenvolvimento dos sistemas sensoriais. Actualmente esta a ser efectuado um grande esforco de investigac~ao para que os sistemas roboticos sejam autonomos
a nvel das decis~oes de alto nvel a executar. No campo dos sistemas sensoriais, a vis~ao por
computador assume papel preponderante, pois permite melhorar a autonomia do sistema
tal como se prova pelos resultados experimentais apresentados neste trabalho.
Nesta tese, pretende-se apenas estudar o problema da navegaca~o com um robot movel,
utilizando vis~ao.
O problema da navegaca~o pode ser estudado de diferentes perspectivas. Uma passa
pelo reconhecimento de pontos de refer^encia (\landmarks"), que denem locais a atingir
ou a evitar. Eventualmente, estes pontos de refer^encia podem ajudar a localizac~ao do
robot num mapa que represente o meio ambiente. Outra das perspectivas, passa pela
utilizac~ao de informaca~o din^amica, i.e., utilizaca~o de medidas da velocidade em imagens.
Neste trabalho optou-se pela segunda alternativa, baseando o processo de navegac~ao
no controlo das velocidades de rotaca~o e translaca~o do veculo, usando a informac~ao
visual. As soluc~oes apresentadas s~ao baseadas no uxo optico medido em duas c^amaras,
e a diferenca entre ambos os uxos medidos permite controlar a atitude do robot movel.
O objectivo principal e a obtenca~o de algoritmos que possam ser realizados em programas
de computador mas cujo tempo de execuc~ao seja pequeno, e podendo ser utilizado na
malha de controlo de um sistema de controlo. Para obter um processo ainda mais rapido,
1
2
~
CAPITULO 1. INTRODUCAO
s~ao utilizadas imagens log-polar, onde e calculado o uxo optico.
Uma das vantagens da utilizac~ao de imagens log-polar e a facilidade da detecca~o de
campos de velocidades divergentes, cujo modulo e directamente proporcional ao raio medido relativamente ao centro da imagem. O metodo de navegac~ao descrito neste trabalho
explora uma tecnica de calculo de uxo optico, baseado num esquema multi-resoluca~o,
de modo a obter um campo de uxo de vectores velocidade com coer^encia local. S~ao
apresentados os resultados obtidos atraves de algoritmos baseados na restric~ao do brilho
(\brightness constraint") e no modelo de velocidade am, ambos aplicados a imagens
log-polar. Os algoritmos de detecca~o de uxo optico geram o sinal de erro que permite
controlar a trajectoria de um robot movel dispondo de um sistema de vis~ao activa, e que
ja foi utilizado em outros trabalhos [J. Dias e C. Paredes 95] e [J. Dias e C. Paredes 96].
Outro dos assuntos abordados neste trabalho, ainda no campo da navegac~ao, passa
pela detecc~ao da posica~o do foco de expans~ao FOE (\Focus of Expansion"), o que permite
explorar a possibilidade de controlar a posic~ao do sensor visual segundo uma direcc~ao de
translac~ao preferida (\Navigation by prefered direction"). Esta tecnica de alinhamento
do sensor permite recuperar de uma forma mais ecaz, a informaca~o visual sobre o meio
ambiente [Alberto Elfes 95]. Note-se que tipicamente, no caso das pessoas, os olhos
mant^em-se alinhados com a direcc~ao do seu movimento, e neste caso esta tecnica simula
este comportamento.
1.1 O enquadramento do trabalho
Nesta secc~ao sera dada uma breve panor^amica de algumas aplicac~oes da vis~ao na navegaca~o de \robots" e o enquadramento deste trabalho neste domnio de aplicaca~o. Concretamente, ser~ao referenciados trabalhos que utilizam a informac~ao visual como sinal de
erro no controlo do processo de navegaca~o, tecnicas de detecca~o de uxo optico e seu
desempenho, transformac~oes log-polar, e a detecc~ao do foco de expans~ao normalmente
designado por FOE .
1.1. O ENQUADRAMENTO DO TRABALHO
3
1.1.1 Navegac~ao baseada em uxo optico normal
O uxo optico normal e uma tecnica de estimac~ao de movimento nas imagens, de tal modo
que Cornelia Fermuller e Yiannis Aloimonos [C. Fermuller e Y. Aloimonos 92] usaram-na
para estimar movimentos 3-D e inferir da posic~ao do FOE de modo a efectuar acco~es
de seguimento (\tracking"). No nosso caso utilizamos uxo am de modo a detectar a
posic~ao do FOE para estimar a direcc~ao preferida de posicionamento do sensor visual.
V. Sundareswaran e P. Bouthemy [V. Sundareswaran e P. Bouthemy 94] apresentaram duas tecnicas de alinhamento do eixo optico de uma c^amara, utilizando para isso
informac~ao visual. Uma das tecnicas usa o foco de expans~ao e a outra incorpora os
par^ametros do modelo am nas equaco~es de controlo. As tecnicas permitem alinhar o
eixo optico com sucesso, sem conhecimento previo do movimento efectuado pelo sistema
onde a c^amara se encontra. No nosso caso a tecnica de alinhamento do sensor visual
utiliza tambem a posic~ao do FOE na imagem para inferir um melhor posicionamento
do sensor visual, no entanto a nossa tecnica de estimac~ao do FOE e diferente da descrita neste artigo, e apresenta resultados promissores na presenca de algumas restric~oes ao
movimento do sensor visual.
David Coombs e outros [D. Coombs e H. Herman 95] descrevem um processo de detecc~ao de obstaculos em tempo real baseado em uxo optico divergente e periferico, calculado atraves do uxo optico normal. Neste trabalho o uxo optico periferico foi usado
para controlar a atitude do veculo relativamente as paredes de um corredor, e o uxo
optico divergente para estimar o tempo ate impacto, no caso de um obstaculo. No artigo
os autores relatam experi^encias, com o robot a uma velocidade nominal de 30cm/s, efectuando trajectorias durante 20 minutos sem colidir com obstaculos. No nosso trabalho
explora-se a forma de controlar a atitude do veculo atraves do uxo optico medido em
imagens log-polar, apresentando resultados praticos pouco satisfatorios na presenca de
movimentos de rotac~ao.
O calculo do uxo optico usando apenas a restric~ao do brilho, conduz normalmente a
algoritmos cujas soluc~oes podem ser instaveis, uma vez que esta restrica~o por si so, n~ao
verica a coer^encia local do movimento. Soluc~oes mais estaveis podem ser obtidas atraves
de algum processo que controle localmente os valores obtidos para o uxo optico.
4
~
CAPITULO 1. INTRODUCAO
Um exemplo da aplicac~ao destas tecnicas e apresentado no trabalho efectuado por
Peter Nordlund e Tomas Uhlin [P. Nordlund e T. Uhlin 95]. Nesse trabalho e apresentado um algoritmo baseado em uxo optico que permite estimar e seguir um objecto em
movimento. O sistema construdo e capaz de manter o objecto no centro da imagem
atraves do controlo de um sistema de vis~ao activa. O metodo de detecca~o de movimento
utiliza um algoritmo baseado no modelo am para a velocidade projectada na imagem.
No calculo do movimento, a imagem e previamente estabilizada. No nosso caso n~ao utilizamos vis~ao activa, uma vez que o processo seria demasiado complicado de estabilizar,
devido a diculdade acrescida da utilizac~ao do movimento do robot movel, i.e., seria neste
caso bastante difcil anular o uxo induzido devido aos movimentos do robot movel.
Um exemplo de navegac~ao tambem com alguma relev^ancia, foi apresentado pelos autores [Ricardo e Michel 91], onde foram implementadas as seguintes tarefas: seguir uma
parede, chegar perto dum objecto, virar numa esquina, etc. Nesta abordagem, e utilizado
uxo optico, extracc~ao de contornos de objectos, etc, e o campo potencial para realizar o
controlo do veculo.
Neste momento, interessa referir que para alem da abordagem proposta nesta tese,
existem outras diferentes, que pretendem resolver o mesmo problema da navegac~ao local
atraves do uso de \landmarks". Tais exemplos podem ser consultados nos trabalhos dos
autores [Davison e Murray 95] e [Davison e Murray 97].
No controlo moderno, os algoritmos de controlo s~ao implementados em computadores digitais, o que implica sempre uma amostragem de entidades analogicas. A teoria
de sistemas de eventos discretos (\Discrete Event System"), que permite representar um
sistema e a sua din^amica com um automato nito n~ao determinstico apresenta uma
alternativa a outros metodos de controlo discreto. Um desses exemplos e descrito em
[Luca Bogoni e Ruzena Bajcsy 94], onde s~ao apresentadas metodologias para investigar a
funcionalidade em tarefas de manipulaca~o de objectos. A descric~ao da funcionalidade da
tarefa e feita atraves da teoria dos sistemas de eventos discretos, permitindo descrever
varias tarefas a implementar, sendo a sua transic~ao assegurada pelo \automato discreto". No nosso caso optamos por um controlo deste genero atraves da especicaca~o de
um automato discreto com varios estados que permite denir em concreto o controlo a
efectuar, na presenca de determinadas entradas do sistema.
1.1. O ENQUADRAMENTO DO TRABALHO
5
Jose Santos Victor e G. Sandini [J. Santos-Victor e G. Sandini 95] prop~oem uma tecnica
de uxo optico divergente para efectuar navegaca~o. Neste trabalho, o robot encontra-se
equipado com duas c^amaras montadas lateralmente e o controlo da atitude do robot e
efectuado com base no sinal de erro obtido pela comparaca~o dos uxos obtidos em cada
c^amara. O trabalho inspira-se em estudos efectuados sobre insectos voadores que "adoptam" um esquema semelhante de navegaca~o.
1.1.2 Medida de desempenho de algoritmos de calculo de uxo
optico
E importante conhecer o desempenho das tecnicas de calculo de uxo optico, na medida em
que esse conhecimento facilita a escolha do algoritmo a utilizar. Devido ao uxo optico ser
por natureza uma medida com rudo, convem de certa forma saber ate que ponto pode ser
ou n~ao viavel a sua utilizaca~o em algoritmos de controlo. Nesta ordem de ideias optamos
por realizar um estudo do seu comportamento tanto em imagens cartesianas como em
imagens log-polar.
Na literatura, ja existiam alguns trabalhos nesta area, tais como os apresentados por
J.L. Barron e outros [J. Barron e D. Fleet 94] que testaram diferentes tecnicas de uxo optico, usando sequ^encias de imagens sinteticas e reais, relatando diferentes medidas comparativas. As tecnicas de uxo optico testadas, baseiam-se em metodos diferenciais, metodos de correspond^encia de regi~oes, metodos de detecca~o de energia e fase.
Os metodos baseados em equac~oes diferenciais de primeira ordem testados foram: Horn
and Schunck [Horn e Schunck 81] e Lucas and Kanade [B. Lucas e T. Kanade 81]. Os
metodos testados, que utilizam tecnicas baseadas em equac~oes diferenciais de segunda
ordem foram: Nagel [H.H. Nagel 83, H.H. Nagel 87] e Uras, Girosi, Verri, and Torre [S. Uras e F. Girosi 88]. As outras tecnicas testadas foram: Anandan, Heeger, Waxman, Wu, and Bergholm e Fleet and Jepson (ver [J. Barron e D. Fleet 94] para mais
refer^encias). No nosso caso utilizamos as denic~oes apresentadas neste artigo, para estender a sua aplicaca~o a imagens log-polar, podendo assim analisar-se o desempenho dos
algoritmos que utilizem uxo optico medido neste tipo de imagens. Os resultados demonstram que o uxo optico e na realidade uma medida bastante ruidosa quer em imagens
6
~
CAPITULO 1. INTRODUCAO
cartesianas quer em imagens log-polar. No entanto chegamos a conclus~ao que em imagens
log-polar esses erros podem ser atenuados atraves de uma boa especicaca~o, como por
exemplo, saber qual o tipo de uxo que se pretende medir, e atraves deste conhecimento
escolher de uma forma correcta os par^ametros da amostragem log-polar.
1.1.3 Transformac~ao Log-polar
Inspirados no homem, bem como em outros mamferos, muitos investigadores recorrem a
vis~ao articial como uma forma potencial de apreender o meio ambiente, uma vez que a
informac~ao presente em imagens digitais e muito rica. No entanto para se levar a cabo
determinadas tarefas, muita dessa informac~ao e superua, e de modo a se eliminar esses
dados muitas das vezes recorre-se a determinadas tecnicas. Pode-se salientar de entre
muitas, por exemplo a diminuic~ao da resoluca~o das imagens (pir^amides de imagens), bem
como a transformaca~o log-polar. Qualquer destas duas permite reduzir de certa forma o
numero de dados a processar.
Nesta ordem de ideias, nos optamos neste trabalho por estudar as propriedades da
transformaca~o log-polar para permitir suprimir alguma da informac~ao que poderia n~ao
ter grande inu^encia para o m em vista.
De entre muitos autores que estudaram este tipo de transformac~ao salientamos os que
se seguem, por ser aqueles que a nosso ver apresentam maior relev^ancia.
Carl F. R. Weiman [Carl Weiman 94], apresentaram experi^encias em tempo real, onde
usaram um sistema baseado em vis~ao activa binocular. Para efectuar o processamento
da imagem utilizaram ltros de Gabor aplicados a imagens log-polar. Este documento e
uma excelente refer^encia sobre tecnicas de transformac~ao log-polar.
G. Sandini, C.Capurro, F.Panerai [G. Sandini e C. Capurro 95], usaram imagens logpolar para controlar activamente um sistema equipado com sensores visuais. As soluc~oes apresentadas usam medidas de correlac~ao, que servem para controlar os a^ngulos de
verg^encia das c^amaras.
No nosso caso pretendemos medir o uxo optico, mas atraves da utilizac~ao da transformaca~o log-polar a imagens cartesianas, para permitir uma maior velocidade de processamento.
1.1. O ENQUADRAMENTO DO TRABALHO
7
1.1.4 Detecc~ao do foco de expans~ao - F OE
Em navegac~ao atraves de vis~ao, o conhecimento do par^ametro FOE , pode ser utilizado
para determinar e controlar o nosso proprio movimento no espaco. Esta detecca~o e importante, porque assim e possvel estimar alguns dos par^ametros de velocidade da c^amara.
Outra possibilidade e a utilizac~ao do conhecimento da posica~o do FOE para alinhar o
sensor visual com o vector de velocidade de translaca~o, optimizando assim a capacidade
de detecc~ao de fenomenos transitorios na frente da c^amara.
M. Tistarelli, E. Grosso and G. Sandini [M. Tistarelli e E. Grosso 90], apresentaram
um metodo para determinar a posica~o do FOE usando uma tecnica de mnimos quadrados
para determinar a intercepca~o das rectas obtidas da elongac~ao dos vectores de uxo optico.
Neste trabalho n~ao foram apresentados resultados experimentais.
Rami Guissin, Shimon Ullman [R. Guissin e S. Ullman 91], apresentaram um metodo
para determinar a posic~ao do FOE onde e utilizada uma tecnica de procura directa no
campo de uxo optico obtido das imagens. O metodo utiliza uma tecnica de procura 1D
para seleccionar a direcc~ao da recta que passa pelo centro da imagem e pelo FOE . E
possvel utilizar o algoritmo para movimentos com/sem restrico~es da c^amara. No caso de
movimentos sem restric~oes e necessario des-rotacionar o campo de velocidades de modo a
cancelar a velocidade observada no centro da imagem. Esta tecnica aparentemente obtem
boas performances para casos simulados.
Michal Irani, Benny Rousso e Shmuel Peleg [M. Irani e B. Rousso 94], apresentaram
um metodo para determinar a posic~ao do FOE que se baseia no calculo do movimento
efectuado por uma regi~ao da imagem. O movimento calculado nessa regi~ao e ent~ao usado
para anular o uxo de rotac~ao da imagem, de tal forma que as regi~oes detectadas aparecem
ent~ao como estacionarias. As imagens obtidas, teoricamente, est~ao apenas afectadas de
movimentos de translaca~o. O metodo usado utiliza algoritmos baseados em modelos de
velocidade am, e n~ao existe a partida, conhecimento do movimento efectuado.
Yiannis Aloimonos e Zoran Duric [Y. Aloimonos e Z. Duric 94], apresentaram um
metodo para determinar o FOE utilizando uxo optico normal para restringir a translac~ao
do observador. Para resolver o problema das rotac~oes, foi apresentado neste artigo uma
vers~ao modicada do algoritmo apresentado por Horn and Weldon, 1987.
8
~
CAPITULO 1. INTRODUCAO
No nosso caso a detecc~ao do FOE e feita atraves do uxo am, utilizando um metodo
de pesquisa no campo de uxo optico. N~ao foi resolvido o problema das rotac~oes na
totalidade, uma vez que o algoritmo funciona sobre o efeito duma restrica~o, que no nosso
caso e vericada devido ao modo de locomoc~ao do robot movel.
1.1.5 Detecc~ao de obstaculos e tempo ate colis~ao
No nosso trabalho n~ao abordamos este tema, no entanto ca em aberto uma futura implementac~ao de algoritmos que permitam detectar obstaculos e o tempo ate colis~ao atraves
de informac~ao visual. No entanto estes dois conceitos t^em a nosso ver alguma relev^ancia
no desenvolvimento de tarefa de navegaca~o, pelo que optamos por descrever brevemente
alguns dos trabalhos ja realizados, para uma maior informaca~o do leitor.
Massimo Tistarelli e Giulio Sandini [M. Tistarelli e G. Sandini 93], apresentaram um
artigo onde estimam o tempo ate impacto utilizando imagens log-polar. No entanto esta
tecnica apresenta alguma instabilidade devido ao rudo introduzido no calculo do uxo
optico, que advem do uso de uma tecnica diferencial de segunda ordem.
Nicola Ancona e Tomaso Poggio [N. Ancona e T. Poggio 93], usaram um esquema
baseado em uxo optico para detectar a expans~ao e rotac~ao entre imagens, de modo a
obter assim uma estimativa do tempo ate colis~ao. O metodo foi utilizado em imagens
reais com sucesso.
Thomas Cord e Dirk Pallmer [T. Cord e D. Pallmer 94], apresentaram um metodo
para estimac~ao da profundidade que requer um movimento controlado da c^amara ao longo
do seu eixo optico. As sequ^encias de imagens s~ao analisadas de modo a calcular os vectores
translac~ao de pontos caractersticos.
P. Fornland [P. Fornland 95], apresentou um metodo de detecca~o de obstaculos no
qual a c^amara movimenta-se paralelamente ao ch~ao. Os par^ametros da c^amara est~ao
linearmente relacionados com as derivadas de primeira ordem da sequ^encia de imagens.
O movimento e estimado atraves do metodo RANSAC [Roth, Gerhard e Levine 92].
1.2. A ESTRUTURA DA TESE
9
1.2 A estrutura da tese
A presente dissertac~ao e composta por seis captulos, incluindo este, onde e descrito o
trabalho efectuado, bem como o conteudo dos captulos que se seguem.
No captulo 2, s~ao apresentados os modelos de projecca~o utilizados para representar
as c^amaras, e as tecnicas de transformac~ao log-polar. Sera efectuada uma descric~ao das
propriedades do log-polar, bem como a relac~ao entre as coordenadas utilizadas. Este
captulo introduz os fundamentos necessarios a compreens~ao do trabalho apresentado nos
captulos que se seguem.
No captulo 3, s~ao descritos os algoritmos de detecca~o de movimento, especialmente aqueles que se baseiam em modelos de gradiente. E introduzido neste captulo um
algoritmo baseado no uxo optico normal, atraves da introduca~o de um pre- e pos- processamento e dum sistema de votac~ao que melhora os resultados obtidos atraves do algoritmo de uxo optico normal. S~ao tambem apresentados os algoritmos de Horn e Schunck
[Horn e Schunck 81], os algoritmos baseados no modelo am e um algoritmo de calculo
de uxo optico baseado em tecnicas de correlaca~o cujos resultados s~ao mais robustos, mas
cujo processo em si e mais lento. Neste captulo e tambem introduzido o modelo am
para o plano log-polar. De seguida, e efectuado um estudo do desempenho de alguns algoritmos de calculo de uxo optico no plano log-polar e cartesiano. As medidas efectuadas
s~ao id^enticas as utilizadas por J.L. Barron e outros [J. Barron e D. Fleet 94].
No captulo 4 e apresentado um metodo para determinar alguns par^ametros do
movimento, tal como a detecc~ao da posica~o do FOE , que permite identicar a direcc~ao
de translac~ao do sensor visual.
Finalmente com base na detecc~ao da posic~ao do FOE e apresentado um metodo para
efectuar um processo de alinhamento e estabilizaca~o duma c^amara montada num robot
movel em movimento puramente translacional - detecc~ao da direcc~ao preferida -.
10
~
CAPITULO 1. INTRODUCAO
No captulo 5, e dado particular ^enfase a implementac~ao/construc~ao de algoritmos de
navegac~ao, a din^amica do sistema, e ao uso do uxo optico como medida para calculo do
erro usado para controlo da din^amica do sistema. E tambem aqui discutida a realizaca~o
da aplicac~ao em tempo real.
Finalmente, no captulo 6 ser~ao apresentadas as conclus~oes deste trabalho.
Captulo 2
Transformac~ao Log-polar
Neste captulo, descreve-se a forma de aplicar a transformaca~o log-polar a imagens contnuas
e discretas, fornecendo assim os fundamentos necessarios para uma correcta compreens~ao
do trabalho que e apresentado nos restantes captulos.
2.1 Perspectiva geometrica
Neste modelo a imagem obtida pelas c^amaras e representada pelo plano I e o ponto de
perspectiva central pelo ponto O (ver gura 2.1). Por denic~ao, a projecca~o de um ponto
3D P (X; Y; Z ) no plano I, e expressa matematicamente por:
u = fx XZ
v = fy YZ
(2.1)
onde fx e fy correspondem a dist^ancia focal afectada do factor de escala horizontal e
vertical. As imagens representadas na g. 2.2 s~ao exemplos de imagens geradas por
alguns modelos de perspectiva e correspondentes a variantes do modelo expresso pelas
equac~oes ( 2.1).
11
12
~ LOG-POLAR
CAPITULO 2. TRANSFORMACAO
2.2 Transformac~ao Log-Polar
Os sistemas de vis~ao baseados em imagens com resoluc~ao espacial homogeneas, t^em diculdades em fornecer respostas em tempo real, quando se encontram na presenca de
um meio ambiente mutavel. A realizac~ao de um sistema visual com um comportamento
reactivo, necessita de alguma selectividade espacial nas imagens. Esta selectividade pode
ser obtida atraves duma amostragem espacialmente variavel. Nessa situac~ao, a imagem
e \separada" numa zona central de grande informac~ao espacial - a fovea - e numa zona
cuja resoluc~ao espacial decresce a medida que o raio ao centro aumenta. O modelo mais
convincente, para este tipo de comportamento, e a transformac~ao log-polar.
Basicamente, um modelo deste genero pode ser obtido atraves duma transformaca~o
que transforma os pontos medidos relativamente ao centro da imagem cartesiana, de uma
forma proporcional a sua dist^ancia a esse centro, e tambem proporcional a resoluca~o
angular medida relativamente a um eixo. Esta transformac~ao na sua forma mais simples
resume-se a uma transformac~ao entre coordenadas cartesianas para coordenadas polares,
seguida da aplicac~ao da func~ao logaritmo a coordenada radial ( 2 <+, 2 [0; 2[,
a; b > 1). Este tipo de transformac~ao reduz signicativamente, a quantidade de dados
a tratar, e pode desta forma ser um meio de gerar sinais de \feedback" visuais, que
possam ser usados em navegac~ao (ver o Anexo A para as notac~oes utilizadas nas secc~oes
seguintes).
2.2.1 Transformac~oes Conformais
Muitos dos problemas de engenharia, podem ser tratados e resolvidos atraves de
metodos de analise complexa. A transformaca~o conformal insere-se neste domnio da
matematica e e um metodo bastante utilizado na engenharia em geral para resolver problemas da teoria de potencial em duas dimens~oes, pois permite simplicar as resoluc~oes.
Segundo as denico~es de [Erwin Kreyszig 79], uma transformac~ao diz-se conformal
ou que preserva ^angulos, se esta mantiver o valor dos a^ngulos entre curvas orientadas,
quer em valor, quer em direcc~ao, isto e, as imagens de duas quaisquer curvas orientadas que se intersectem num ponto, mant^em a mesma relac~ao geometrica angular apos a
~ LOG-POLAR
2.2. TRANSFORMACAO
13
[CAM]
P
p
f
O
Z
0
u
X
v
I
Y
Figura 2.1: Modelo de perspectiva geometrica
Figura 2.2: Imagens sinteticas geradas por (da esquerda para a direita): modelo
geometrico, modelo ortograco, modelo semi-esferico. As respectivas equaco~es do modelo s~ao dadas por: u = X:Su , v = Y:Sv para o modelo ortograco e por u = XS :Su ,
v = YS :Sv para o modelo semi-esferico, onde Xs = X p(X +Yr +Z ) , Ys = Y p(X +Yr +Z ) e
Zs = Z p(X +Yr +Z ) , sendo r o raio da esfera.
2
2
2
2
2
2
2
2
2
~ LOG-POLAR
CAPITULO 2. TRANSFORMACAO
14
transformac~ao.
Esta transformac~ao contem propriedades interessantes para o domnio deste trabalho,
na medida em que nos permite vericar que tipo de informac~ao pode ser preservada pela
transformac~ao, e que se expressa pelos seguintes teoremas:
Teorema 2.1 Se uma funca~o complexa ! = f (z) = u(x; y) + i:v(x; y) onde z = x + i:y
esta denida num domnio D do plano complexo Z , ent~ao para cada ponto de D existe um
ponto correspondente no plano W . Desta forma, existe uma transformac~ao do plano Z
para o plano W . A func~ao f (z ) dene uma transformac~ao conformal, excepto nos pontos
onde f 0(z ) e zero, se e se so f (z ) e uma func~ao analtica.
Teorema 2.2 A func~ao f (z) = u(x; y)+i:v(x; y) onde z = x+i:y e analtica num domnio
D, se as func~oes u(x; y) e v(x; y) de variaveis reais x e y tiverem derivadas continuas de
primeira ordem, que satisfacam as equac~oes de Cauchy-Riemann num domnio D, isto e,
@u
@x
= @v
@y e
@u
@y
@v
= , @x
(2.2)
ou se a funca~o estiver expressa em coordenadas polares, z = ei , e f (z ) = u(; ) +
i:v(; ), ent~ao as equaco~es de Cauchy-Riemann ser~ao dadas por:
@u
@
1 @u @v
= 1 @v
@ e , @ = @
(2.3)
A demonstrac~ao destes teoremas sai do domnio deste tese, mas podera ser consultada
em [Erwin Kreyszig 79].
Um exemplo de transformaca~o muito utilizada em vis~ao por computador (transformac~oes 2D para 2D) corresponde a transformaca~o log-polar. A transformac~ao log-polar
utilizada no desenvolvimento desta tese, pela forma como foi denida n~ao apresenta a
propriedade de transformac~ao conformal, mas este facto n~ao e muito preocupante, porque n~ao se pretende medir ^angulos entre objectos. A sua denica~o pode ser dada como
(! = + i):
z = x + iy = f ,1(!) = a :cos() + i:a :sin():
(2.4)
e na proxima secc~ao abordaremos mais em pormenor este assunto. No entanto, pode-se
denir uma transformac~ao log-polar com a propriedade conformal, i.e., se z = ei , ent~ao
~ LOG-POLAR
2.2. TRANSFORMACAO
15
a sua transformac~ao ! no domnio log-polar e
! = + i: = f (z ) = loga (z ) = loga () + i: lna
(2.5)
e a sua transformac~ao inversa e descrita por,
z = x + i:y = f ,1(!) = a :cos(: ln a) + i:a :sin(: ln a):
(2.6)
2.2.2 Transformac~ao Log-Polar generica
Assuma-se ent~ao um ponto (u; v) da imagem, expressa em coordenadas cartesianas. O par
(; ) especica o mesmo ponto, mas em coordenadas polares 1. O ponto (u; v) no plano
cartesiano, pode ser representado por um numero complexo z , e pelas suas coordenadas
polares (; ), atraves de:
z = u + i:v = :ei:
(2.7)
com
p
= u2 + v2
(2.8)
= tan,1 uv
A transformac~ao logartmica complexa (ou transformaca~o log-polar) e, desta forma, denida como
w = ln(z )
(2.9)
para cada z 6= 0, onde <(w) = ln() e =(w) = + 2k. Para z 6= 0 existe uma
singularidade que sicamente num sensor de imagem corresponderia a uma zona em que os
\pixels" teriam de ser innitesimamente pequenos e innitamente numerosos no centro do
sensor - uma congurac~ao que sicamente n~ao e realizavel - . Para excluir a periodicidade
da parte imaginaria, e assumido k = 1 de modo a restringir os valores possveis de =(w)
ao intervalo [0; 2[. Ao plano (ln(); ) tambem se chama de plano w. Facilmente se
demonstra que uma rotac~ao centrada na origem do plano z resulta num deslocamento na
direcc~ao no plano w e que uma multiplicaca~o por um factor de escala no plano z , resulta
num deslocamento na direcc~ao ln() no plano w.
1
Assumindo as notac~oes indicadas no Ap^endice A.
~ LOG-POLAR
CAPITULO 2. TRANSFORMACAO
16
Esta denic~ao pode ser extensvel a outros casos, de modo a permitir trabalhar imagens com diferentes \aspect ratio", ou quando e necessario efectuar amostragens com
diferentes espacamentos nos eixos horizontal e vertical. Esta transformaca~o podera ser
extremamente util para imagens com diferentes resoluco~es nos dois eixos, caso se pretenda
transformar toda a imagem cartesiana para o plano log-polar. Neste caso a formula geral
para a transformac~ao e dada por (n~ao se trata de uma transformaca~o conformal):
8
<
u(; ) = a cos()
(2.10)
v(; ) = b sin()
As constantes a e b controlam a evoluc~ao da transformac~ao na direcc~ao radial, e para
valores particulares podem ser obtidos respectivamente transformac~oes em crculos ou em
elipses para os casos de a = b ou a 6= b. Esta e a transformac~ao log-polar utilizada nas
implementac~oes praticas descritas neste trabalho.
Como a transformac~ao log-polar vai corresponder a uma sub-amostragem da imagem e
muito comum simular transformac~oes log-polar com o uso de pequenas celulas receptoras
de forma circular centradas no ponto de amostragem log-polar. O valor do pixel no plano
log-polar e neste caso dado atraves da media dos \pixels" que pertencem a respectiva
celula circular. Na proxima secc~ao sera apresentado um processo semelhante ao descrito.
Na maioria dos casos o calculo desta media e omitido para permitir um maior velocidade
de processamento.
:
2.2.3 Uma transformac~ao Log-polar mais elaborada
Um dos metodos propostos por [M. Blackburn e H. Nguyen 94] e [Carl Weiman 94] permite que a transformaca~o log-polar seja realizada atraves de crculos conc^entricos radiais.
Em cada crculo conc^entrico existem crculos de amostragem angular, sendo o valor do
pixel de cada amostra no plano log-polar dado pela media dos \pixels" que se encontram
dentro do respectivo crculo para a respectiva amostra angular. Por outras palavras, a
posica~o dos pontos, espacialmente variante e obtida atraves duma amostragem regular
e duma grelha de crculos conc^entricos com N amostras em cada crculo radial. Para
cada um destes crculos conc^entricos com dist^ancia constante ao centro da imagem cartesiana, s~ao efectuadas N amostras angulares, e para cada uma destas amostras, o valor
~ LOG-POLAR
2.2. TRANSFORMACAO
17
Figura 2.3: Representac~ao graca duma transformac~ao log-polar, atraves do uso duma
tecnica de crculos conc^entricos. Neste caso o numero de amostras angulares e de 50.
de amostragem e obtido dos \pixels" que se encontram num crculo centrado na posic~ao
da amostra angular. A gura 2.3, representa gracamente este tipo de amostragem
log-polar.
O numero de amostras em cada crculo e constante, conforme ilustrado na Fig. 2.3.
Para um dado N , a componente radial do -esimo crculo e dada por:
= fovea 1 + p
= foveaa
(2.11)
3N
onde = 0, ..., N , 1 e fovea indica o raio mnimo do crculo quando = 0, e e escolhido
de forma a evitar a sobreposic~ao dos crculos de amostras angulares consecutivas (neste
caso e uma condic~ao universal), e o raio dos crculos R 1 (para o caso = 0). O valor
de fovea e assim dado por:
(2.12)
fovea 3 N
2
Sobre o mesmo crculo conc^entrico s~ao tiradas N amostras espacadas periodicamente por:
P = 2N
(2.13)
e para cada uma destas amostras esta associado um crculo cujo raio e dado por:
R = 23
(2.14)
N
!
18
~ LOG-POLAR
CAPITULO 2. TRANSFORMACAO
1 2π
2 Nθ
Amostra radial K+1
Amostra radial K
2π
Nθ
Figura 2.4: Entre dois crculos conc^entricos consecutivos as amostras angulares s~ao deslocadas de meio perodo.
que e igual para as N amostras (para o mesmo ). Entre dois crculos conc^entricos
consecutivos as amostras angulares s~ao deslocadas de meio perodo (veja-se Fig. 2.4),
porque com este esquema, mesmo na hipotese de se usar um numero de amostras angulares
baixo, conseguir-se-a mesmo assim uma boa representac~ao da imagem original (pode-se
considerar que seria como se tivesse usado o dobro das amostras angulares), onde a formula
matematica e dada por:
2 + odd( )
= N
(2.15)
2
!
com = 0, ..., N , 1.
A transformac~ao para os ndices do plano Log-Polar e assim dada por:
log = loga fovea
log = (1+odd )
2
N
( )
2
(2.16)
Alguns investigadores, propuseram diferentes soluc~oes para efectuar a transformaca~o
log-polar, de modo a conseguir eliminar a singularidade presente na origem. Por exemplo, [A.S. Roger e and E.L. Schwartz 90], propuseram uma transformaca~o log-polar sem
a inclus~ao da fovea.
Outros investigadores, como por exemplo [Carl Weiman 94], propuseram uma forma
eciente de ultrapassar o problema da singularidade. Segundo esses investigadores, a zona
da fovea, representada na Fig. 2.3 pelo crculo central, seria transformada atraves duma
~ LOG-POLAR
2.2. TRANSFORMACAO
19
estrutura rectangular uniformemente preenchida com celulas, cujas areas seriam iguais
a area da celula log-polar mais proxima (o que neste caso seria para = 0). A este
processo eles chamaram de \Isotropic central ll". Um dos benefcios, desta abordagem,
advem do facto, de assim se poder utilizar coordenadas lineares no centro da imagem,
com igual espacamento, permitindo tambem a efectuaca~o de reconhecimento de padr~oes
atraves dum processo invariante a translaca~o. No entanto a descontinuidade, presente na
transic~ao entre a zona de coordenadas (u; v) e a zona de coordenadas (loga (); ), levanta
um problema a transformac~ao da imagem nessa transic~ao, por exemplo a translaca~o e
a rotac~ao. As equac~oes para este processo s~ao semelhantes as equac~oes anteriormente
apresentadas na zona periferica, e para a regi~ao central denida pela restric~ao < fovea
s~ao utilizadas as coordenadas cartesianas.
2.2.4 A transformac~ao log-polar discreta
Para os casos praticos da aplicaca~o do log-polar em vis~ao por computador, o plano W
sera referido como o plano imagem log-polar. As variaveis N e N denem a resoluc~ao
radial e angular da imagem log-polar. A transformac~ao log-polar, sera apenas aplicada a
toda a imagem excepto a zona da fovea. Mas primeiro comecemos com a transformac~ao
geral. No caso discreto, a cada pixel (; ) no plano log-polar, corresponde um pixel (u; v)
no plano imagem. O valor da intensidade do pixel (; ) no plano log-polar e obtido
atraves da aplicac~ao de uma mascara gaussiana, cuja mascara de dimens~ao n n, deve
ser centrada no pixel (u; v) (veja-se Ap^endice D). Denindo o valor incremental angular:
2
(2.17)
= N
a transformada e baseada nas seguintes equac~oes:
8
<
:
u = fovea:a : cos(: )
v = fovea:b : sin(: )
8
>
<
>
:
= arctan ab tan(: )
= fovea a2 cos2(: ) + b2 sin2(: )
q
(2.18)
O valor de fovea e uma constante para permitir que n~ao exista sobreposic~ao de \pixels"
para = 0 (neste caso , apenas assumem valores inteiros). Este valor deve ser escolhido
de forma a que o permetro do crculo para = 0 tenha no mnimo N amostras, pois so
~ LOG-POLAR
CAPITULO 2. TRANSFORMACAO
20
ζ
v
ρ
γ
θ
u
Figura 2.5: Transformaca~o Log-polar e a representac~ao da estrutura de amostragem para
um caso em que a = b.
assim se garante que existem N \pixels" diferentes para N amostras angulares (no caso
em que a = b). Este valor limiar e dado por:
:
fovea N
(2.19)
2
A aplicac~ao desta restric~ao, resulta num crculo central, na imagem do plano cartesiano,
cuja informac~ao la contida n~ao e transformada para o plano log-polar, tal como pode ser
visto atraves da Fig. 2.5. As dimens~oes deste crculo podem ser controladas atraves
do valor do numero de amostras segundo a direcca~o (N ), ou atraves dos valores da
base da func~ao logaritmo. As constante a, b controlam a evoluca~o das amostras segundo
a direcc~ao radial . Da aplicac~ao das equaco~es 2.18 para = 0, ..., N , 1 e = 0,
..., N , 1, resulta a estrutura de amostragem representada na Fig. 2.5 (para a = b).
Outro pormenor importante, e o facto de a resoluc~ao na direcc~ao do log-polar ser sempre
constante para todos os valores radiais, o que resulta numa imagem no plano log-polar
com mais informac~ao sobre a zona central da imagem cartesiana, mas decrescendo para
a periferia. No caso descrito acima, s~ao usadas as variaveis N , a, b, para controlar a
amostragem.
Para o caso de uma transformac~ao log-polar com a = b, pode-se denir fovea max , que permite indicar qual a zona da imagem cartesiana que sera transformada, onde
2
fovea e o raio da zona central n~ao amostrada (fovea) e max a dimens~ao da imagem
cartesiana em \pixels" (assumindo uma imagem quadrangular). A transformac~ao de
^
~ LOG-POLAR DINAMICA)
^
2.3. RETINA DINAMICA
(OU TRANSFORMACAO
21
Figura 2.6: Exemplo duma imagem log-polar. Na esquerda encontra-se a imagem cartesiana, e a direita a imagem log-polar resultante da amostragem pela estrutura representada
na Fig. 2.5
coordenadas polares (; ) para coordenadas log-polares (; ) e dada por:
!
= loga (2.20)
fovea
conforme pode ser visto na Fig. 2.5. A base a do logaritmo e dada na depend^encia de
N por
1 ln max
,
a
= exp
(2.21)
fovea:aN ,1 = max
2
N , 1 2
!!
fovea
Dada uma imagem digital quadrada I (u; v) contendo max max \pixels", pode-se vericar que para um dado fovea max
2 , a transformac~ao n~ao tem uma correspond^encia
unvoca. A Fig. 2.6 mostra um exemplo da transformac~ao log-polar para o que foi descrito anteriormente. Na Fig. 2.7 apresenta-se tambem exemplos da amostragem log-polar
quando a = b, a > b e a < b.
2.3 Retina din^amica (ou transformac~ao log-polar
din^amica)
Na secc~ao 2.2.2 foi denida a transformac~ao log-polar (eq. 2.10). Suponha-se agora, que
e necessario efectuar a transformac~ao, n~ao centrada no ponto (0; 0), mas sim, centrada
num ponto generico (ui ; vi ). A primeira vista, o problema parece simples de resolver,
uma vez que apenas e necessario efectuar a transformac~ao centrada no ponto dado. No
~ LOG-POLAR
CAPITULO 2. TRANSFORMACAO
22
Estrutura de
Amostragem
Log-Polar
a=b
a>b
a<b
Figura 2.7: Exemplos de transformac~oes Log-Polar, quando a = b, a > b, e a < b (veja-se
eq. 2.10).
entanto, o que nos interessa, e obter a nova imagem log-polar utilizando apenas a imagem
log-polar obtida da transformac~ao centrada num ponto (u0 ; v0), para isso e necessario
desenvolver a transformac~ao entre os dois planos log-polar.
Denic~ao 2.1 Uma retina centrada num ponto (u0; v0), e equivalente a uma transfor-
mac~ao log-polar centrada em (u0 ; v0). O termo \retina din^amica" representa a mudanca
do ponto central, onde a transformac~ao log-polar e efectuada.
Suponha-se, ent~ao, que se tem a retina original centrada no ponto (u0 ; v0 ), com variaveis independentes (; ), e que se pretende obter uma retina centrada no ponto (u1 ; v1)
com variaveis independentes ( ; ). Para a primeira retina (ou transformac~ao log-polar)
0
0
^
2.4. CAMPO DE MOVIMENTO INDUZIDO NUMA CAMARA
23
tem-se:
u(; ) = a cos() + u0
v(; ) = a sin() + v0
e para a segunda retina (ou transformaca~o log-polar):
(2.22)
u( ; ) = a cos( ) + u1
v( ; ) = a sin( ) + v1
0
0
0
0
0
0
0
(2.23)
0
Tendo em conta que o novo ponto central (u1; v1 ) pode ser descrito atraves da equac~ao
( 2.22), para um determinado (0 ; 0) atraves de:
a0 cos(0 ) = u1 , u0
a0 sin(0 ) = v1 , v0
(2.24)
a partir de ( 2.22) e ( 2.23) e tendo em conta que se pretende obter a nova imagem
log-polar ( ; ) em funca~o da imagem log-polar (; ), resolvendo para (; ) obtemos:
0
0
"
2
0
0
= tan,1 a sin( )+a0 sin(0 )
0
0
2
#
= 21 loga a cos( ) + a0 cos(0 ) + a sin( ) + a0 sin(0 )
0
0
!
(2.25)
a cos( )+a0 cos(0 )
0
0
Em conclus~ao, no domnio contnuo, esta propriedade permite transformar uma imagem log-polar que tenha sido obtida atraves de um determinado ponto central da imagem
cartesiana numa outra imagem log-polar com outro ponto central, sem ser necessario reutilizar a imagem cartesiana. Em termos praticos sendo as imagens discretas, a utilizaca~o
da retina din^amica oferece alguns problemas de difcil resoluc~ao.
2.4 Campo de movimento induzido numa c^amara
Neste momento e importante estudar o efeito resultante nas imagens a nvel da velocidade
projectada, quando uma c^amara se movimenta num meio ambiente estatico. Para isso
descreve-se de seguida o comportamento do modelo para a projecc~ao da velocidade no
plano imagem, dados os par^ametros de movimento duma c^amara.
~ LOG-POLAR
CAPITULO 2. TRANSFORMACAO
24
(u,v)
Vx
X
Z
Y
f
Vz
Wx
P(X,Y,Z)
p
Wz
Vy
Wy
Figura 2.8: Orientac~ao das velocidades 3D da c^amara
Assuma-se assim, um modelo de perspectiva geometrica conforme descrito na secca~o
2.1, com a equac~ao ( 2.1) que relaciona os pontos 3D com os pontos 2D. A c^amara
possui duas componentes de movimento: a translacional v~ = [vx ; vy ; vz ]T e a rotacional
~! = [!x ; !y ; !z ]T (veja-se a Fig. 2.8). Devido ao movimento da c^amara, o ponto P da
cena com um vector ~p = [X; Y; Z ]T associado, aparenta um movimento relativo a c^amara
_ Y_ ; Z_ ]T pode
com translac~ao ,v~ e com rotac~ao ,~! . Neste caso a velocidade 3D, ~v = [X;
ser expressa por:
~v = ,v~ , ~! ~p
(2.26)
t
t
t
Este e o vector de movimento 3D, que gera o vector de movimento 2D no plano imagem.
Na realidade, estes vectores ser~ao projectados no plano imagem dando origem a uma
imagem do campo de movimento (o uxo optico teorico). Para projectar os vectores de
velocidade 3D e necessario utilizar a equac~ao 2.1 diferenciada em ordem a t:
u_ = X_ Zfx , fxZZ_ X
v_ = Y_Zfy , fyZZ_ Y
2
(2.27)
2
e efectuando a substituica~o de ~v na equaca~o, obt^em-se o uxo induzido na imagem devido
ao proprio movimento da c^amara:
h
u_ v_
T
i
= 1 :A:v~ + B:~!
Z
t
(2.28)
~ LOG-POLAR
2.5. ALGUMAS PROPRIEDADES DA TRANSFORMACAO
25
onde a sua expans~ao e dada por:
2
2
4
3
2
3
5
4
6
6
56
4
, fx 0 u
u_
=1
Z 0 ,fy v
v_
2
3
vx
vy +
vz
2
7
7
7
5
4 vu
fy
, fx + ufx v ffxy
, vufx
,u ffxy
fy + vfy
2
2
3
6
6
56
4
wx
wy
wz
3
7
7
7
5
(2.29)
Obviamente, esta express~ao representa o uxo optico analtico no plano imagem, onde
o primeiro termo representa o efeito do movimento de translac~ao, enquanto que o segundo
e o uxo induzido devido ao movimento de rotac~ao da c^amara. E importante referir, que
o efeito associado a translac~ao depende da profundidade Z (apenas pode ser obtida a
direcc~ao do movimento de translac~ao em vez das suas componentes), e portanto, no caso
da velocidade ser conhecida, pode-se estimar a profundidade relativamente ao referencial
da c^amara.
2.5 Algumas propriedades da transformac~ao Log-Polar
A transformaca~o log-polar apresenta algumas propriedades interessantes, que torna este
processo numa ferramenta bastante util para aplicar no campo da vis~ao por computador.
Algumas dessas propriedades est~ao ligadas ao efeito de rotaca~o, e a mudanca do factor
de escala (relativamente ao centro da imagem). As imagens da Fig. 2.9 ilustram a
propriedade da rotac~ao, que no plano log-polar corresponde a um deslocamento vertical.
Mas, no entanto, a mais importante e a projecca~o do campo de movimento no plano
log-polar, quando o observador efectua movimentos de rotac~ao ou de translaca~o. O que
nos interessa aqui, e observar o que acontece ao campo de uxo optico para alguns tipos de
movimento. E importante referir que atraves das equac~oes obtidas na secc~ao 2.4 facilmente se prova as armac~oes que se seguem, atraves da restric~ao dos pontos tridimensionais
ao tipo de superfcie em quest~ao.
Note-se que o uxo optico gerado no plano imagem duma c^amara, quando esta efectua
movimentos de translac~ao na direcc~ao do seu eixo optico, e divergente, e o seu modulo
aumenta com a dist^ancia ao centro da imagem. Neste caso, existe um ponto designado
de foco de expans~ao (FOE ), que esta situado no centro do uxo optico divergente na
Fig. 2.10 (coincidente com o centro da imagem). Este campo de vectores, no plano
~ LOG-POLAR
CAPITULO 2. TRANSFORMACAO
26
Imagem original
Imagem rodada 90º
Imagem rodada 180º
Imagem rodada 270º
Cartesiano
Log-Polar
Figura 2.9: O efeito da rotac~ao. A imagem cartesiana e rodada, e o consequente efeito no
plano log-polar e uma translac~ao na direcc~ao .
log-polar sera constitudo por um campo de vectores com modulo variavel, mas com a
mesma orientac~ao angular, tal como pode ser visto na Fig. 2.10, e se for efectuado um
histograma na direcc~ao resultara numa funca~o horizontal constante para cada um dos
valores de .
Campos de vectores de uxo optico deste tipo, s~ao bastante importantes para este trabalho.
2.5.1 Campo de movimento no plano Log-polar
Os metodos de amostragem com resoluca~o espacial variavel, possuem algumas caractersticas interessantes. Uma dessas, em particular, e o estudo do calculo do uxo optico
(veja-se Cap. 3). Na realidade, com a amostragem log-polar, e possvel detectar de uma
forma mais ecaz algumas formas de uxo optico que com outras tecnicas normais n~ao
e possvel. Portanto, nesta secc~ao, vai-se efectuar o estudo das relac~oes entre o uxo no
plano cartesiano e no plano log-polar.
@(t)
Para relacionar o uxo optico ( @(t)
@t ; @t ) no plano log-polar com o uxo no plano
~ LOG-POLAR
2.5. ALGUMAS PROPRIEDADES DA TRANSFORMACAO
Cartesiano
log-polar
Cartesiano
~! = 0, vx = vy = 0, vz 6= 0
log-polar
~! = 0, vy = vz = 0, vx 6= 0
Cartesiano
27
log-polar
~! = 0, vx = vz = 0, vy 6= 0
Figura 2.10: Relac~ao entre os uxos opticos dos dois planos, para diferentes tipos de
movimento. Da esquerda para a direita, e representado o uxo no plano imagem seguido
do seu equivalente no plano log-polar. As duas imagens da esquerda representam o uxo
optico divergente, que no plano log-polar e constante. As imagens do centro, e da direita,
correspondem a um uxo horizontal e vertical crescente respectivamente, que no plano
log-polar da origem a vectores com o mesmo modulo, mas com orientaco~es diferentes.
@v(;;t)
cartesiano ( @u(;;t)
@t ; @t ), deve-se diferenciar a equaca~o 2.10 em ordem a t, que resulta
na seguinte equac~ao, que representa a relaca~o entre os dois campos de vectores
2
3
2
32
3
5
4
54
5
@(t)
ln(a) cos() ,a sin()
a
@t
= @(t)
b ln(b) sin() b cos()
@t
na realidade a matriz J representa o Jacobiano da matriz da equac~ao 2.10:
4
@u(;;t)
@t
@v(;;t)
@t
2
J=
4
@u(;;t) @u(;;t)
@
@
@v(;;t) @v(;;t)
@
@
(2.30)
3
(2.31)
5
Usando a notac~ao u_ = @u(;;t)
@t , e efectuando a transformac~ao inversa da eq. 2.30
resulta na relac~ao do campo de vectores do plano cartesiano com o plano log-polar:
2
4
3
2
5
4
_
1
=
cos()2 ln( ab ) + ln(b)
_
cos()
sin()
a
b
, sin() ln(b) cos() ln(a)
a
b
32
54
u_
v_
3
5
(2.32)
e como pode ser visto, a detecc~ao do uxo optico no plano log-polar e igual ao uxo do
plano imagem, mas dividido pela dist^ancia radial (a e b ) relativamente ao centro da
~ LOG-POLAR
CAPITULO 2. TRANSFORMACAO
28
imagem (a matriz representa apenas uma transformac~ao de rotaca~o). Esta propriedade e
de grande utilidade, porque permite detectar campos de uxos crescentes radialmente a
partir do centro da imagem, enquanto que com outras tecnicas sera muito difcil.
No caso em que os par^ametros que controlam a evoluca~o da componente radial s~ao
iguais (a = b), obtemos as seguintes relac~oes:
2
4
e
3
2
32
5
4
54
u_ = a ln(a) cos() , sin()
v_
ln(a) sin() cos()
2
4
3
2
32
5
4
54
cos()
sin()
_
1
ln(a)
ln(a)
=
_
a , sin() cos()
u_
v_
_
_
3
(2.33)
5
3
(2.34)
5
E importante vericar a diferenca entre uma transformaca~o polar e log-polar. Rescrevendo as equac~oes indicadas acima, para o caso polar:
2
4
3
2
32
5
4
54
_
cos() sin()
=
cos()
_
, sin()
u_
v_
3
(2.35)
5
Analisando a equac~ao ( 2.35), verica-se que o uxo optico radial apresenta algumas
diferencas, quando comparado com o caso log-polar. Certamente a utilizaca~o da funca~o
logaritmo na direcc~ao radial e a origem deste facto. Na secc~ao 4.2 veremos esta diferenca,
de uma forma mais explcita.
Como em situac~oes praticas, se utiliza a vers~ao discreta das equac~oes ( 2.33) e ( 2.34)
(para a = b) ent~ao teremos:
2
4
e
3
2
32
5
4
54
u_
ln(a) cos(: ) ,: sin(: )
= fovea:a
v_
ln(a) sin(: ) : cos(: )
2
4
cos(:)
_
1
ln(a)
=
sin(:)
a
fovea
_
, 3
2
5
4
sin(:)
ln(a)
cos(:)
32
54
u_
v_
_
_
3
5
(2.36)
3
5
(2.37)
2.6. O EFEITO DE SUB-AMOSTRAGEM PRODUZIDO PELO LOG-POLAR
29
2.6 O efeito de sub-amostragem produzido pelo logpolar
Nesta secc~ao, analisa-se a transformac~ao log-polar no domnio da frequ^encia e pretendese conhecer a partida as especicac~oes dos eventuais ltros que ser~ao necessarios para
efectuar a transformac~ao log-polar discreta de uma forma conveniente. Assume-se que a
forma conveniente e evitar fenomenos de \aliasing".
Para efectuar o estudo, assuma-se a partida dois sinais bidimensionais contnuos. O
primeiro sinal I (u; v), que e o sinal original, encontra-se representado no domnio cartesiano. O segundo sinal I2(; ) foi obtido do sinal contnuo I (u; v) atraves da transformaca~o
log-polar contnua denida pela equaca~o 2.10 (com b = a > 1).
Para o sinal I (u; v) o seu espectro FT fI g(!u ; !v ) e dado por:
FT fI g(!u ; !v ) =
Z
+1 Z +1
,1 ,1
I (u; v):e,j!u u :e,j!v v dudv:
(2.38)
onde !u = 2fu e !v = 2fv . Utilizando a relaca~o entre I (u; v) e I2(; ) e efectuando-se
uma mudanca de variavel, a mesma transformada pode ser expressa por:
FT fI g(!u ; !v ) =
onde
Z
+1 Z 2
,1 0
2
4
I2(; ):e,j!u a cos() :e,j!v a sin() jJ jdd
(2.39)
3
5
jJ j = a ln(a) cos() ,a sin() = a2 ln a > 0 e I2(; ) = I (a cos(); a sin())
a ln(a) sin() a cos()
que apos as respectivas simplicac~oes, pode ser representada por:
FT fI g(!u ; !v ) = ln a
+1 2 Z 2
cos() ,j!v a sin()
,
j!
a
u
a
I2(; ):e
:e
d d
,1
0
Z
(2.40)
que corresponde a um espectro do sinal com coordenadas cartesianas.
Por outro lado, suponha-se agora o sinal I2(; ) que foi obtido do sinal contnuo
I (u; v) atraves da transformac~ao log-polar contnua. Aplicando a transformada de Fourier
indicada na eq. ( 2.38) ao sinal I2(; ), sabendo que ] , 1; +1[ e [0; 2[, o espectro
do sinal em coordenadas polares e dado por:
FT fI2g(! ; ! ) =
Z
+1 Z 2
,1 0
I2(; ):e,j! :e,j! dd
(2.41)
~ LOG-POLAR
CAPITULO 2. TRANSFORMACAO
30
Comparando as express~oes 2.41 e 2.40, verica-se que existe um factor de escala a2 ln a
que advem da amostragem logartmica.
Como o objectivo e pretender conhecer qual o ltro que se deve aplicar de modo a evitar
\aliasing" e tendo em conta que de facto o processo de amostragem logartmica possui
papel preponderante, vamos estudar em separado o efeito da amostragem logartmica e
angular.
Por simplicidade, para o estudo da amostragem logartmica, considere-se um sinal
unidimensional discreto. Assuma-se desta forma um sinal discreto original xoriginal [n]
com n = 0, ..., N , 1 elementos, amostrado atraves duma func~ao logartmica n = foveaa
com fovea > 0 e = 0, ..., N , 1. Apos a aplicac~ao desta transformac~ao obtem-se o
sinal pretendido x[] = xoriginal [foveaa ].
No entanto, para uma melhor compreens~ao, considere-se ainda sem perda de generalidade, que xoriginal [n] foi obtido dum sinal periodico contnuo x(t) com perodo T0 e que
permite representar completamente o sinal x(t), i.e.,
T
(2.42)
xoriginal [n] = x(t) t , TN0 n dt
0
onde () representa a funca~o delta de Dirac. O sinal discreto e equivalente a uma amostragem logartmica tera deste modo a seguinte forma:
T
a dt
x[] = x(t) t , T0fovea
(2.43)
N
0
Este novo sinal pode n~ao representar correctamente o sinal x(t) devido ao espacamento
das amostras n~ao cumprir o teorema da amostragem [Alan Oppenheim 79]. Este facto
tera maior probabilidade de ocorr^encia quando tende para N , 1, pois para as duas
amostras nais e que existe um maior espacamento. Este espacamento dene a frequ^encia
de amostragem de valor mais baixo e portanto a mais crtica. Por outro lado, dado o
espacamento entre amostras ser variavel, pode-se considerar que a amostragem logartmica
possui uma frequ^encia de amostragem variavel com a posic~ao da amostra.
Para determinar as especicac~oes do ltro vai-se considerar inicialmente um novo sinal
x1[m], obtido de xoriginal [n] atraves de uma amostragem logartmica, mas que contenha na
totalidade todos os elementos de xoriginal [n]. Para tal e necessario denir os par^ametros
da nova funca~o de amostragem. Estes par^ametros est~ao directamente relacionados com
Z
Z
0
0
2.6. O EFEITO DE SUB-AMOSTRAGEM PRODUZIDO PELO LOG-POLAR
Tipo de
sinal
original
Express~ao
do sinal
desejado
x[] =
Numero de Variavel Filtro
amostras de controlo
T0 x(t) t , T0 n dt
0
N
N
n
T0 x(t) t , T0 foveabm dt
0
N
M
m
T0 foveabp dt
T0
0 x(t) t ,
N
N
M
T0 foveaa dt
T0
0 x(t) t ,
N
N
M
xoriginal [n] =
Contem na
totalidade o x1 [m] =
sinal original
Desejado,
mas obtido x2[] =
de x1[m]
31
R
R
R
R
Tabela 2.1: Passos necessarios para estudar os par^ametros dos ltros necessarios a ltragem das imagens, antes da transformac~ao log-polar.
o espacamento das duas amostras nais, uma vez que estas devem estar presentes no
sinal x1 [m]. Considere-se ent~ao uma nova func~ao de amostragem dada por exemplo, por
n = foveabm onde m = 0, ...,M , 1, isto para um determinado b e M . Os valores de b e
M podem ser obtidos atraves da restric~ao na periferia da func~ao foveabm, i.e.,
fovea:bM ,1 = N , 1
fovea:bM ,2 = N , 2
(2.44)
,1 + 1. Apos a
obtendo-se assim para b e M respectivamente b = NN ,,21 e M = logb Nfovea
aplicaca~o desta transformac~ao obtem-se o sinal pretendido x1[m] = xoriginal [foveabm ], que
representa na totalidade x(t).
Desta forma o sinal x1[m] pode ser dado por:
x1[m] =
T0
Z
0
bm dt
x(t) t , T0fovea
N
!
(2.45)
Para obter o sinal x[] a partir de x1[m] e necessario efectuar uma interpolaca~o de N
seguida duma decimac~ao de M , isto porque o sinal x1 [m] tem M amostras e pretende-
~ LOG-POLAR
CAPITULO 2. TRANSFORMACAO
32
se obter no nal um sinal com N amostras. Por esta raz~ao deve-se substituir m pela
seguinte relaca~o:
(2.46)
m = NM , m = p = 0 N , 1
pelo que o sinal x2[] sera assim dado por:
bp dt
x2[] = x(t) t , T0 fovea
(2.47)
N
0
Atraves das equac~oes 2.43 e 2.47 vericamos que ambas representam o mesmo sinal
se a condic~ao a = bp se vericar. Nessa situac~ao o ltro que se deve aplicar depende do
factor de decimac~ao, que neste caso era de M , i.e., a frequ^encia de corte do ltro deve ser
de M . A tabela 2.1 apresenta os passos tomados para se obter esta conclus~ao.
Neste momento, e importante voltar agora ao caso log-polar em 2D, mas primeiro
deve-se estudar a amostragem angular da transformaca~o log-polar.
Para a amostragem angular, o maior factor de decimaca~o acontece na periferia. Nessa
zona a dist^ancia entre amostras angulares e de ' N2 foveaaN ,1 \pixels", o que origina
um factor de decimaca~o de:
2 aN ,1 , 1
(2.48)
K=N
fovea
e para se evitar \aliasing", a frequ^encia de corte do ltro deve ser de K .
Deste modo, para o caso log-polar, a frequ^encia de corte e dada por N , onde N =
max (K; M ). Esta e uma das restric~oes mais severas, devido a amostragem espacial variante, no entanto e possvel desenhar varios ltros para diferentes pontos de amostragem
radial (i.e. a frequ^encia de corte do ltro depende da dist^ancia radial).
E importante referir, que o sinal resultante tera componentes de frequ^encia acima de
, por isso deve-se ter cuidado, quando se utilizam tecnicas de diferenciac~ao. Neste caso
2
deve-se ltrar o sinal nal com um ltro com frequ^encia de corte 2 , perdendo-se assim
alguma informac~ao.
Z
T0
!
Captulo 3
Detecc~ao de Movimento nas Imagens
Neste captulo, e abordado o calculo do uxo optico numa sequ^encia de imagens temporais
apresentando um algoritmo para o seu calculo, bem como a sua extens~ao para imagens
log-polar.
Como o tema principal desta tese e a navegac~ao num espaco especco utilizando
vis~ao din^amica para testar e desenvolver o metodo de navegac~ao, e necessario ter um
estimador do sinal que e resultado do uxo optico na sequ^encia temporal de imagens
que se v~ao adquirindo. Interessa portanto estudar quais os metodos mais adequados e
expeditos para este objectivo. Esta foi a principal motivac~ao para se efectuar este estudo,
tendo tambem em conta que se pretende explorar imagens log-polar. Este ultimo ponto
e decisivo, porque o calculo do uxo optico atraves de imagens log-polar e mais rapido
do que com imagens cartesianas, e consequentemente podem ser obtidos algoritmos com
tempos de execuc~ao muito pequenos. Por conseguinte, e importante abordar o problema
tendo em conta a necessidade de encontrar respostas para:
Das tecnicas de calculo de uxo optico, qual e a mais indicada para usar em imagens
log-polar?
Sera necessario utilizar algum processo adicional para compensar o facto do calculo
do uxo ser baseado em tecnicas diferenciais?
Sera possvel estimar o movimento usando apenas uxo optico normal?
33
~ DE MOVIMENTO NAS IMAGENS
CAPITULO 3. DETECCAO
34
Z
Cam
po d
em
X
ovim
ento
Y
fluxo
optico
ou c
amp
o de
velo
cida
de
Figura 3.1: Relac~ao entre o campo de movimento e o uxo optico
Como ser~ao os resultados inuenciados pelos par^ametros do log-polar?
Nas secc~oes deste captulo tentaremos dar respostas a estas quest~oes.
Consideraveis esforcos t^em sido efectuados no desenvolvimento de tecnicas diferenciais
para o calculo de uxo optico (ou estimaca~o da velocidade projectada usando imagens).
Com base no conhecimento deste uxo e possvel desenvolver tecnicas para o seguimento
de objectos que se movimentam no espaco, determinaca~o de par^ametros de movimento
(\egomotion") ou de navegac~ao com base na informac~ao din^amica obtida a partir de
imagens. Estes problemas s~ao difceis de resolver, uma vez que a velocidade projectada
no plano imagem e a projecca~o da velocidade tridimensional do objecto, que em alguns
casos n~ao pode ser totalmente estimada, como podemos vericar pela Fig. 3.1.
3.1 Campo de movimento induzido numa c^amara por
uma superfcie planar
Reporte-se o leitor a secca~o 2.4, onde foi previamente introduzida a relac~ao entre o campo
de movimento projectado numa imagem e o induzido por uma c^amara em movimento.
Nesta secc~ao e feita uma extens~ao a essa relac~ao para um conjunto de pontos tridimensionais que pertencem a uma superfcie planar.
Os resultados obtidos s~ao interessantes para o calculo de par^ametros de movimento e
navegac~ao, pois as muitas superfcies podem ser representadas como conjunto de pequenos
3.2. CALCULO
DO FLUXO OPTICO
35
planos. Por exemplo, a superfcie das paredes do corredor, onde se pretende efectuar a
navegaca~o, podem modelar-se como planos, ou conjunto de planos.
Assuma-se ent~ao que alguns dos pontos projectados na imagem pertencem a um plano.
Todos esses pontos satisfazem uma restric~ao geometrica correspondente a equac~ao dum
plano Z = C + D:X + E:Y , que pode ser expressa em termos das coordenadas da imagem,
usando a equac~ao 2.1 como:
1 = + :u + :v
(3.1)
Z
e substituindo este resultado na equac~ao 2.29 obt^em-se:
2
4
3
2
3
5
4
5
u_
a + a :u + a3:v + ac :u2 + bc :u:v
= 1 2
v_
b1 + b2:u + b3:v + ac :u:v + bc:v2
(3.2)
onde
a1 = ,fx Vx , fx Wy b1 = ,fy Vy + fy Wx
a2 = ,fxVx + Vz b2 = ,fy Vy , ffxy Wz
(3.3)
a3 = ,fxVx + ffyx Wz b3 = ,fy Vy + Vz
ac = , Wfxy + Vz
bc = Vz + Wfyx
A equaca~o 3.2 descreve o uxo de movimento na imagem representado parametricamente
atraves de oito par^ametros, e gerado por um movimento tridimensional dum plano na cena.
Estes par^ametros s~ao o suporte para os metodos \am", \translacional" e \movimento de
uma superfcie plana" para a determinaca~o do uxo optico no plano imagem, como sera
apresentado nas secc~oes que se seguem. O modelo descrito pela equaca~o 3.2, pode ser
utilizado com um metodo de mnimos quadrados para estimar o uxo optico, e assim o
problema da abertura pode ser ultrapassado atraves deste modelo especco. Este assunto
sera explicado mais tarde.
3.2 Calculo do uxo optico
Para estimar o uxo optico em imagens discretas e necessario ter alguns cuidados como
veremos mais a frente nesta secc~ao. Existem ja alguns trabalhos neste campo, tal como o
trabalho feito por Peixoto [Peixoto 95], onde atraves do calculo do uxo am se estuda a
coer^encia do movimento em sequ^encias de imagens. Este trabalho tem como ponto alto, a
36
~ DE MOVIMENTO NAS IMAGENS
CAPITULO 3. DETECCAO
detecc~ao de dois tipos de movimento (movimento dum objecto na presenca de movimento
de fundo), e a sua possvel remoc~ao. No nosso caso n~ao pretendemos detectar varios
movimentos distintos, mas sim utilizar o modelo am para estimar o foco de expans~ao
como veremos na secc~ao 4.2.
Convem neste momento referir que existem pelo menos quatro grandes estrategias
algortmicas para a determinac~ao do uxo optico, que s~ao baseados:
1. no gradiente : as tecnicas baseadas no gradiente assumem que a intensidade da
imagem se conserva entre imagens. Esta tecnica e a utilizada neste trabalho, e sera
abordada em detalhe nesta secc~ao.
2. na correlac~ao : considera que a distribuica~o local da intensidade das imagens se
mant^em entre estas. Normalmente este calculo e efectuado sobre duas imagens consecutivas separadas temporalmente por um intervalo de tempo 4t muito pequeno.
A tecnica consiste na determinaca~o da posica~o relativa de um pixel, ponto ou caracterstica entre duas imagens temporalmente consecutivas. O uxo optico sera o vector deslocamento entre as posic~oes consecutivas entre as duas imagens. Para achar
este vector e necessario efectuar uma procura de entre alguns candidatos da segunda
imagem e achar o melhor de todos. Alguns investigadores [D. Marr e Poggio 79],
[Barnard e Thompson 80] e [Burt, Xen e Xu 83], usaram as seguintes estrategias
para achar esse candidato:
os candidatos pertencem a uma area onde se considera que no maximo existiu
um deslocamento de x e y \pixels" (velocidades maximas admissveis). A esta
regi~ao chama-se a janela de procura.
O melhor candidato e dado atraves da maxima correlaca~o que usa uma area
a volta do pixel da imagem no tempo t, e a area correspondente em redor
do pixel candidato da imagem t + 4t. Pelo facto do uso de uma janela este metodo considera que a distribuic~ao local da intensidade das imagens se
mantem constante.
3. em energia espaco temporal : neste processo o calculo do uxo optico e baseado
na resposta de ltros sintonizados para determinadas velocidades, considerando-se
3.2. CALCULO
DO FLUXO OPTICO
37
assim que as frequ^encias espaco temporais, est~ao relacionadas com a velocidade dos
\pixels" atraves da seguinte formula:
!t = !u u_ + !v v:_
(3.4)
onde as variaveis u_ , v_ , referem as duas componentes ortogonais da velocidade 2D,
!u , !v s~ao as componentes ortogonais da frequ^encia espacial do estmulo visual, e
!t e a frequ^encia temporal correspondente. A equaca~o 3.4 foi deduzida atraves
da transformada de Fourier aplicada a duas imagens duma sequ^encia temporal,
considerando que existe conservaca~o da intensidade dos "pixels" entre as imagens
[D. Hegger 87].
Segunda a equaca~o 3.4, se o sinal for visto no espaco !u , !v , !t , temos a equac~ao
de um plano. A velocidade (u;_ v_ ) pode ser determinada se o plano for determinado.
Heeger [D. Hegger 87] utiliza doze ltros de Gabor sintonizados em frequ^encias
centrais que est~ao contidas dentro de um cilindro no espaco !u , !v , !t , onde o
eixo do cilindro e o eixo !t . Cada ltro esta sintonizado para dar a sua maxima
resposta para um determinado valor do uxo optico, e desta forma atraves do uso de
diferentes ltros podem-se obter respostas diferentes, que dependem da frequ^encia
espaco temporal das imagens. O melhor dos doze ltros, da origem ao resultado
escolhido, denindo assim os par^ametros do plano.
4. na fase : e um processo semelhante a tecnica da energia espaco temporal, pelo facto
de utilizar ltros sintonizaveis (neste caso passa-banda), no entanto a velocidade
(u; v) e denida em termos do valor da fase para a sada do ltro (normalmente
tecnicas de passagem por zero).
No nosso caso interessa-nos em especial os metodos baseados no gradiente, pois permitem a partir algoritmos com um menor tempo de execuca~o, se bem que, eventualmente,
com um maior erro de calculo. Este ultimo ponto pode ser decisivo pois pode tornar
instavel a soluc~ao encontrada para o problema em causa. Para responder a esta quest~ao,
no nal desta secca~o sera apresentado um estudo realizado para conhecer o desempenho dos algoritmos de uxo optico em imagens cartesianas e log-polar. Neste estudo s~ao
apresentados resultados de comparac~ao entre quatro metodos de calculo do uxo optico.
38
~ DE MOVIMENTO NAS IMAGENS
CAPITULO 3. DETECCAO
3.2.1 Filtragem
Quando se pretende estimar o uxo optico numericamente, e extremamente importante
que se efectue uma ltragem da imagem discreta para eliminar algum do rudo. O processo de ltragem pode ser realizado para seleccionar uma parte do espectro do sinal e/ou
para remover o rudo de alta frequ^encia que normalmente existe nas imagens discretas.
Considerando que a imagem cont^em a densidade espectral concentrada nas baixas frequ^encias, pode-se remover a maior parte do rudo efectuando uma ltragem passa-baixo.
Conforme explicado na secc~ao 2.6, quando e necessario decimar um sinal, deve-se evitar
o fenomeno de \aliasing" atraves da limitaca~o do espectro do sinal. Como a intenc~ao e
utilizar imagens log-polar, neste caso apenas sera efectuada a ltragem espacial para garantir que quando se faz a amostragem log-polar o espectro do sinal e de banda limitada.
No entanto, efectuar uma ltragem espacial consome muito tempo, para se reduzir este
tempo, pode-se vericar que apenas e necessario ltrar uma zona da imagem a volta do
pixel que vai ser amostrado pelo processo log-polar.
3.2.2 Metodos que utilizam o gradiente
Dos metodos de calculo de uxo optico existentes, os metodos diferenciais s~ao os mais
ruidosos, mas permitem obter algoritmos com tempos de execuc~ao muito pequenos. Por
conseguinte, a maioria dos algoritmos propostos e utilizados em processos de tempo real,
exploram a diferenciac~ao dos valores de cinzento para cada pixel, de modo a efectuar a
estimac~ao do campo de velocidade. Estes metodos baseiam-se na observac~ao da mudanca
dos valores de cinzento da imagem I (u; v; t), e s~ao chamados de metodos baseados no
gradiente. A soluca~o para as equac~oes resultantes, fornecem a estimaca~o para o campo de
velocidades do plano imagem, tambem chamado de uxo optico do campo de velocidade
da imagem.
Suponha-se que (u; v) e a posic~ao na imagem dum ponto da cena no instante t, e
que (u;_ v_ ) e a velocidade desse ponto projectada na imagem. O mesmo ponto (u; v) apos
um tempo 4t mover-se-a para uma nova posic~ao (u + u:_ 4t; v + v:_ 4t). Assumindo a
3.2. CALCULO
DO FLUXO OPTICO
39
conservaca~o do brilho da imagem nesse ponto implica que
I (u; v; t) = I (u + u:_ 4t; v + v_ :4t; t + 4t)
(3.5)
Expandindo o termo da direita atraves da serie de Taylor e representando Iu = Iu(u; v; t) =
@I(u;v;t) ; I = I (u; v; t) = @I(u;v;t) ; I = I (u; v; t) = @I(u;v;t) , a equac~ao 3.5 pode ser
v
v
t
t
@u
@v
@t
reduzida a:
Iu u_ 4t + Iv v_ 4t + It4t , Err(4t2) = 0
(3.6)
Esta restric~ao assume que o brilho da imagem I (u; v; t) \sofrera" um pequena variac~ao
durante o intervalo de tempo 4t entre as duas imagens consecutivas, e que I (u; v; t)
e uma func~ao diferenciavel - ou seja obedece as condico~es de expansibilidade em serie
de Taylor. O termo Err(4t2) representa o erro existente neste calculo, pois apenas se
utilizam termos ate a primeira derivada na expans~ao da serie de Taylor. Assumindo
que este erro e desprezavel, ent~ao obteremos a equac~ao 3.7 que representa a designada
\restric~ao do brilho" (brightness constraint):
r~ I:~v + It = 0
(3.7)
~ I = [Iu ; Iv ]T
onde ~v = [u;_ v_ ]T e o uxo optico no instante de tempo t no ponto (u; v) e r
e o gradiente no mesmo ponto.
A equac~ao 3.7 representa a vers~ao vectorial da restrica~o do brilho e, no caso de apenas
se utilizar esta restric~ao para a estimac~ao do uxo optico, apenas a projecca~o do uxo
optico na direcc~ao do gradiente podera ser calculada. Este facto esta relacionado com o
designado problema da abertura e ilustrado na Fig. 3.2. Da gura, conclui-se que apenas
a componente da velocidade que e normal as arestas dos objectos podera ser detectada.
A esta componente chama-se de uxo optico normal e e dada pela equaca~o:
k ~vnormal k = , 2It 2 = , ~It
(3.8)
k rI k
Iu + Iv
q
que e obtida atraves da eq. 3.7.
Pode-se estabelecer uma relac~ao entre o uxo optico normal com o campo de velocidade
normal. Para isso assuma-se um ponto (u; v) com uma velocidade projectada dada por
40
~ DE MOVIMENTO NAS IMAGENS
CAPITULO 3. DETECCAO
~
Posicao
, final
do edge
Abertura
~
Posicao
, inical
do edge
Candidatos ao movimento
dum ponto do edge
Figura 3.2: Representaca~o do problema da abertura. O contorno da linha e observado
atraves duma pequena janela no instante t e move-se para outra posica~o no instante t +1.
O movimento efectuado pode ser uma translaca~o vertical, ou uma translaca~o mais um
deslocamento na direcc~ao da linha. No entanto, como a linha esta a ser observada atraves
duma pequena janela, apenas se pode detectar a componente do uxo optico na direcca~o
perpendicular as arestas.
~ I . O gradiente local normalizado e dado por:
~v = [u;_ v_ ]T e o respectivo gradiente r
~
~n = ~rI = ~1 : Iu :
(3.9)
k rI k k rI k Iv
A velocidade normal no ponto (u; v) e igual a:
un = ~nT :~v = ~1 (Iu :u_ + Iv :v_ ):
(3.10)
k rI k
As duas velocidades s~ao iguais se a subtracca~o da eq. 3.10 e eq. 3.8 for zero:
2
3
4
5
un , k ~vnormal k = ~1 (Iu :u_ + Iv :v_ + It) = ~1 dI
:
(3.11)
k rI k
k rI k dt
Da eq. 3.11 pode-se concluir que as velocidades s~ao iguais se o gradiente localmente for
diferente de zero e de valor elevado, ou se a soma das derivadas locais da func~ao I for
pequena ou nula. Esta e uma restrica~o pratica a efectuar a quando do calculo do uxo
optico, e e aplicado tambem no calculo do uxo optico normal conforme explicado na
secc~ao 3.2.3.
3.2.3 Algoritmo de uxo optico normal
E do conhecimento geral, que o uxo optico normal em geral n~ao e igual ao uxo optico
3.2. CALCULO
DO FLUXO OPTICO
41
real porque o uxo optico normal depende do problema da abertura. Por este facto,
e compreensvel que existam erros quer na amplitude quer na orientaca~o dos vectores
de uxo normal calculados. A quest~ao que se p~oe e a seguinte, poderemos usar algum
processo para corrigir ou atenuar estes erros? O proximo algoritmo e a nossa resposta a
esta pergunta. Atraves de experi^encias realizadas descobriu-se que para obter melhores
resultados a nvel da orientaca~o dos vectores de uxo, era necessario utilizar tr^es estados de
processamento no calculo do uxo optico normal. No entanto, este processo n~ao introduz
acrescimos signicativos a nvel do modulo dos vectores. Os tr^es estados de processamento
s~ao executados sequencialmente e consistem em:
Estado de pre-processamento - neste estado alguns dos pontos numericamente instaveis
s~ao excludos do calculo do uxo optico normal
Estado do calculo do uxo optico normal - calculo do uxo optico tal como denido
Estado de pos-processamento - um mecanismo de votaca~o baseado em tr^es nveis
duma pir^amide de uxo optico normal, para testar a coer^encia dos vectores de
uxo, e o uso de um ltro aplicado a cada ponto para melhorar a estimaca~o do
uxo.
Estes tr^es estados s~ao fundamentais, porque o calculo do uxo optico normal e efectuado
sobre imagens log-polar, onde a diferenciaca~o numerica tende a ser mais instavel. Se isso
e um facto ent~ao qual e a justicac~ao para usar imagens log-polar e uxo optico normal, e
n~ao usar um outro processo ou tecnica de determinaca~o de uxo? Bom, n~ao nos devemos
esquecer que o nosso objectivo e obter resultados em tempo real, ou caso contrario poderse-ia utilizar uma outra tecnica mais elaborada, e eventualmente mais robusta, mas com
o consequente aumento do tempo de processamento.
Estado de pre-processamento
Para cada ponto da imagem, o gradiente e calculado atraves dum operador espacial de
dimens~ao 3 3 (denido na secc~ao 3.2.8) para obter a estimaca~o de I (; ; t), I (; ; t)
e It (; ; t).
42
~ DE MOVIMENTO NAS IMAGENS
CAPITULO 3. DETECCAO
Na pratica, apenas os \pixels" com gradiente e derivada temporal superior a um limiar
ser~ao considerados, de modo a evitar os erros causados pelo rudo associado ao calculo
diferencial. Este processo corresponde ao estado de pre-processamento e e apenas utilizado
no algoritmo do uxo optico normal.
Estado do calculo do uxo optico normal
O uxo optico normal e determinado atraves da explorac~ao da restrica~o do brilho e e
denido como:
~vnormal (; ; t) = , ~It 2 [I ; I ]T :
k rI k
Este vector e calculado apos o estado de pre-processamento.
(3.12)
Estado de pos-processamento
O estado de pos-processamento, serve para garantir a coer^encia do movimento detectado
atraves do uso duma pir^amide de imagens com tr^es nveis. Subir um nvel na pir^amide
resulta numa imagem com metade das dimens~oes da imagem do nvel anterior, onde cada
pixel e obtido atraves da media dos \pixels" duma regi~ao de 2 2 da imagem no nvel
anterior. A imagem resultante e ltrada com uma funca~o gaussiana, de modo a suavizar
a imagem. Este ltro e um ltro passa-baixo para evitar fenomenos de \aliasing" (ver
ap^endice D na express~ao D.1). Para cada imagem da pir^amide, o uxo optico normal
e calculado usando os estados de pre-processamento e o estado do calculo do uxo optico
normal. A consist^encia dos vectores de movimento e efectuada atraves da analise do uxo
optico normal nos tr^es nveis da pir^amide.
No entanto, em primeiro lugar, a consist^encia do uxo optico normal e testada em
cada nvel separadamente, atraves do uso de regi~oes de n n \pixels" (a regi~ao depende
da estrutura de amostragem do log-polar e do nvel da pir^amide). O uxo (;_ _ ) e o mais
votado da regi~ao considerada, calculado nos varios nveis separadamente. As componentes
radiais e angulares do uxo (;_ _ ) s~ao dadas pelas celulas _(l ; l ) e _ (l ; l ), onde l e l
s~ao calculados como:
3.2. CALCULO
DO FLUXO OPTICO
43
1 (max fhist
l = hist,radial
radial ( )g)
;
(3.13)
,
1
l = histangular (max fhistangular ( )g)
onde histradial ( ) = 3=0 _(; ) e histangular ( ) = 3=0 _ (; ). Este processo e ilustrado
na Fig. 3.3. Em cada nvel da pir^amide um processo semelhante ao descrito pela eq.
3.13 e efectuado, mas com a diferenca nas dimens~oes da regi~ao (a regi~ao tera metade das
dimens~oes da regi~ao do nvel da pir^amide anterior). Para o primeiro nvel da pir^amide
(imagem com maior resoluca~o), a regi~ao e de 4 4 \pixels". Um processo de votac~ao
similar a este foi proposto por J.Little e outros, [J. Little, H. Bulthof e T. Poggio 88]
para o calculo do uxo optico em imagens cartesianas.
A vericac~ao da consist^encia do uxo optico normal nos tr^es nveis da pir^amide de
modo a estimar o uxo na imagem de maior resoluca~o, e efectuada da seguinte forma:
todos os \pixels" s~ao vericados nos tr^es nveis, em regi~oes correspondentes, de modo a
vericar a consist^encia angular e de amplitude. O valor resultante para o uxo da regi~ao e
calculado atraves dum processo de votac~ao, cujo criterio consiste em vericar se dois dos
tr^es vectores apresentam a mesma fase, caso contrario sera assumido um valor nulo para
o uxo na respectiva regi~ao. E importante referir que a amplitude entre dois nveis duma
pir^amide tem um factor de escala de 2, e que os vectores de uxo normal s~ao retirados
de regi~oes correspondentes em cada nvel. Estes factos s~ao tambem levados em conta a
quando da comparac~ao das fases dos tr^es vectores, uma vez que pode-se detectar uxo no
nvel mais alto sem este estar presente nos nveis anteriores.
Apos a aplicac~ao dos tr^es estados de processamento do uxo optico normal, as componentes dos vectores resultantes, s~ao continuamente includos num ltro - . O uso deste
ltro permite melhorar a estimac~ao dos vectores de uxo optico, removendo a partida
algum do rudo presente devido ao calculo numerico e para garantir uma certa coer^encia
e consist^encia a nvel temporal. O uso do ltro e util tambem para estimar os valores de
uxo em regi~oes sem textura, caso nesse local, em tempos passados, tenha possudo uxo
n~ao nulo. Neste caso o uxo para esses \pixels" e dado pela predica~o do ltro - (apenas
para 3 amostras consecutivas com uxo nulo). Para alem deste caracter preditivo o uso
do ltro previne uma variaca~o abrupta nos vectores de uxo detectados, enquanto tende
a suavizar a velocidade em termos temporais.
P
P
~ DE MOVIMENTO NAS IMAGENS
CAPITULO 3. DETECCAO
44
j
ζl
ζ
Σ
Componente Radial
k γl
k
γl
γ
γ
Σ
ζ
j ζl
Componente Angular
Figura 3.3: Vericaca~o da consist^encia dos vectores de uxo, atraves do uso de um esquema de votac~ao, tal como e usado para o 1o nvel da pir^amide
3.2.4 Algoritmo de uxo optico usando o modelo am
O segundo metodo explorado, baseia-se tambem na restric~ao do brilho, em conjunca~o com
o modelo am (ou outro) entre duas imagens consecutivas. Esta tecnica foi explorada por
Nordlund & Uhlin [P. Nordlund e T. Uhlin 95], mas para imagens cartesianas. No nosso
caso sera estendida a sua aplicac~ao a imagens log-polar.
Tal como explicado na secca~o 3.2.2, a equac~ao 3.7, assume que a restrica~o de brilho
e vericada, o que implica condico~es de iluminaca~o uniforme.
Uma forma eciente de ultrapassar este problema, pode ser a utilizac~ao de um modelo
de velocidade descrito em func~ao das coordenadas da imagem. Devido ao tempo 4t
entre imagens n~ao ser innitesimal, e natural que a equaca~o 3.7 n~ao se verique em
alguns pontos. No entanto pode-se utilizar um metodo de mnimos quadrados de modo
a minimizar o erro global cometido numa certa regi~ao da imagem (note-se que se esta a
3.2. CALCULO
DO FLUXO OPTICO
45
usar imagens log-polar):
min
8
1
<X
I :_ + I :_ + It
1 X
=0 =0
:
9
=
2
(3.14)
;
Utilizando a express~ao (3.2) a velocidade pode ser descrita de tr^es formas distintas, e para
cada uma delas, pode-se obter uma soluc~ao fechada:
_
modelo puramente translacional: = a1 ,
_
b1
2
3
2
3
4
5
4
5
_
modelo am: = a1 + a2: + a3: ,
_
b1 + b2: + b3:
2
3
2
3
4
5
4
5
modelo duma superfcie planar em movimento:
2
4
_
a + a : + a3 : + a: 2 + b::
= 1 2
,
_
b1 + b2: + b3: + a:: + b: 2
3
2
3
5
4
5
Nestes modelos temos 2, 6 e 8 par^ametros a estimar, respectivamente. Para o modelo
translacional a soluc~ao e dada pela equac~ao:
2
4
I2
I I
P
P
P
3
2
3
2
5
4
5
4
I I
a1
, ItI
:
=
I2
b1
, ItI
P
P
P
3
(3.15)
5
Para o modelo am, podemos inicialmente denir a seguinte matriz simetrica:
2
A=
6
6
6
6
6
6
6
6
6
6
6
6
6
4
e os vectores:
P
I2
I2 I2 2
P
P
simetrica
I2 I2
I2 2
P
P
P
I I
I I I I I2
P
P
P
P
I I I I 2
I I I2
I2 2
P
P
P
P
P
I I I I I I 2
I2
I2
I2 2
P
P
P
P
P
P
3
7
7
7
7
7
7
7
7
7
7
7
7
7
5
(3.16)
~ DE MOVIMENTO NAS IMAGENS
CAPITULO 3. DETECCAO
46
T
i
h
~x = a1 ; a2 ; a3; b1; b2; b3
~k = , ItI ; , ItI ; , It I ; , ItI ; , It I ; , It I h
P
P
P
P
P
P
i
T
neste caso o numero de par^ametros a estimar e de 6 e podem ser obtidos atraves da
seguinte relac~ao:
A:~x = ~k
(3.17)
Para o modelo duma superfcie planar em movimento, denindo as entidades:
q = I + I x~0 = a b
h
T
i
k~0 = ,It:q ,It:q
h
2
C=
2
4
P
P
q2 : 2
q2 :
P
P
T
i
q2:
q2: 2
3
5
2
q:I q:I q:I 2
D = q:I q:I q:I q:I q:I 2 q:I q:I a soluca~o pode ser calculada atraves de:
A DT : ~x = ~k
D C
x~0
k~0
4
P
P
P
P
P
P
P
P
P
P
P
P
2
3
2
3
2
3
4
5
4
5
4
5
q:I q:I 2
3
5
(3.18)
Para usar este metodo, de incio, descreve-se a velocidade atraves do modelo am, e se
o determinante da matriz A for nulo ou abaixo dum limiar, ent~ao sera assumido o modelo
translacional. Se ainda para este modelo o determinante da matriz A estiver abaixo dum
limiar ou for nulo ent~ao sera assumido um uxo nulo para a regi~ao considerada.
Nas equac~oes indicadas anteriormente, a soma e efectuada numa regi~ao de n m
\pixels" de modo a estimar os 6 ou 2 par^ametros ( no nossos testes praticos esta regi~ao
3.2. CALCULO
DO FLUXO OPTICO
47
possu as dimens~oes de 23 36 \pixels" para dividir a imagem log-polar no mesmo numero
de regi~oes para as duas dimens~oes da imagem).
Estes modelos usam a imagem log-polar, tal como se esta fosse uma imagem cartesiana.
Contudo na proxima secca~o podera ser visto, que se pode denir os mesmos modelos, mas
usando o facto de que as imagens utilizadas s~ao imagens log-polar.
Renamento do Algoritmo
Como neste caso s~ao utilizadas imagens log-polar, sera de esperar que se possa usar os
resultados diferenciais, tal como se estes tivessem sido tirados da imagem cartesiana no
mesmo ponto onde a amostragem log-polar e feita, mas com a diferenca, de que neste
caso o log-polar e utilizado apenas para aumentar a velocidade de calculo. Este processo
e facil de implementar, dadas as derivadas espaciais (I ; I ) e usando a eq. 2.36 pode-se
obter (Iu ; Iv ), e com a eq. 2.18, gerar as coordenadas (u; v) dadas as coordenadas (; ).
Usando o metodo desta forma, os par^ametros calculados podem ser relacionados com os
par^ametros de velocidade da c^amara, tal como foi explicado anteriormente. Contudo com
este modelo, a profundidade da cena n~ao pode possuir grandes descontinuidades porque
se assume que os pontos tridimensionais est~ao restringidos a um plano.
Vericac~ao do modelo
Apos a soluc~ao do sistema, pode-se calcular o uxo optico para cada ponto da imagem, e
desta forma vericar quais os pontos da imagem que vericam o modelo. Este facto pode
ser vericado atraves da construc~ao de uma imagem erro usando a equac~ao:
Err = I :_ + I :_ + It
2
(3.19)
O uxo optico pode ent~ao ser novamente determinado para as regi~oes da imagem que n~ao
vericaram o modelo, dando assim a possibilidade de detectar diferentes objectos (caso
estes se encontrem a diferentes profundidades).
48
~ DE MOVIMENTO NAS IMAGENS
CAPITULO 3. DETECCAO
3.2.5 Algoritmo de uxo optico de Horn e Schunck Revisto
O terceiro metodo implementado, usa um processo semelhante ao algoritmo proposto por
Horn e Schunck [J. Barron e D. Fleet 94], mas aplicado neste caso ao plano log-polar.
Este processo combina a restric~ao do brilho com uma restric~ao que garante uma certa
suavidade ao campo de velocidade estimado. O metodo dene as grandezas s(; ) e
c(; ), respectivamente de medida de contraste (transico~es abruptas) e erro na restrica~o
do uxo optico como:
2
2
s(; ) = 14 ( _ ( + 1; ) , _(; ) + _ (; + 1) , _(; ) +
[_ ( + 1; ) , _ (; )]2 + [_ (; + 1) , _ (; )]2)
h
i
h
i
2
c(; ) = I _ + I _ + It
O objectivo principal e o de encontrar os valores que minimizam a seguinte equac~ao numa
determinada regi~ao
[s(; ) + c(; )]
(3.20)
h
i
X
;
+
O 2 < , e e usado como uma forma de balancear a import^ancia entre as func~oes s(; )
e c(; ). Se o se aproxima de zero, a funca~o s(; ) tera mais peso no resultado, caso
contrario sera a func~ao c(; ).
A principal vantagem deste metodo advem do facto da minimizac~ao poder ser resolvida
atraves duma soluc~ao iterativa. A soluc~ao iterativa para obter a velocidade e assim dada
por:
k
I _ +I _ k +It
_ k+1 = _ k , I : 1+:(I
+I )
(3.21)
k
_ +I _ k +It
I
:
I
k
_ k+1 = _ , 1+:(I +I )
onde k indica o numero de iterac~oes, _0 e _ 0 indicam estimativas iniciais da velocidade
k
iniciadas a zero, _ e _ k indicam medias locais na vizinhanca dos pontos considerados. Nas
experi^encias realizadas, estas medias foram tiradas dos 8 \pixels" a volta do pixel (; ).
O valor de e o numero de iterac~oes foram obtidos atraves das experi^encias efectuadas e
s~ao um pouco heursticos. No nosso caso usaram-se 5 iterac~oes com = 3:5.
h
h
i
2
2
2
2
i
3.2. CALCULO
DO FLUXO OPTICO
49
Na pratica este metodo apresenta alguns problemas, uma vez que o uxo tem tend^encia
a ser propagado para outras regi~oes devido as medias da velocidade, e nalguns casos, as
zonas da imagem sem movimento podem assim apresentar velocidade n~ao nula. Este
processo pode ser controlado atraves duma escolha adequada para o numero de iteraco~es.
Outro problema importante, neste metodo, prende-se com as atribuic~oes iniciais na periferia da imagem, pois este uxo tambem sera propagado para outras regi~oes da imagem.
3.2.6 Calculo de uxo optico usando correlac~ao
Uma tecnica bastante importante de calculo de uxo optico, pode ser obtida atraves do
uso de correlac~ao, no entanto este metodo apenas foi testado em imagens cartesianas. O
metodo que se apresenta em baixo, assume que a cena visualizada n~ao possui grandes
descontinuidades em termos de profundidade.
A ideia e em cada imagem da sequ^encia, identicar pontos de interesse (estes pontos
v^em de zonas da imagem com alto contraste). Caso n~ao seja possvel identicar estes
pontos, o metodo falha. O operador de selecc~ao dos pontos de interesse tem por objectivo
seleccionar zonas de alto contraste como por exemplo, zonas de contornos, objectos, etc,
de modo a area em redor do ponto ser facilmente identicavel em imagens futuras. Estes
objectivos podem ser concretizados atraves do uso duma func~ao que retorne medidas da
vari^ancia direccional, retornando os pontos com maxima vari^ancia. A vari^ancia direccional
e medida em pequenas janelas quadrangulares, e neste caso e implementada atraves da
soma do quadrado da diferenca entre \pixels" adjacentes em cada uma das tr^es direcco~es
( horizontal, vertical e diagonal). O operador de interesse retorna assim o valor mnimo
de entre os tr^es valores calculados.
Em cada ponto de interesse, e denido um padr~ao de tamanho n n \pixels" na
imagem I (t), e a correlac~ao e efectuada numa janela de pesquisa com tamanho x y e
centrada no mesmo ponto da imagem I (t + 4t). O deslocamento entre o ponto original
e o ponto onde a correlaca~o e maior dene o uxo optico desse ponto.
Para extrapolar o uxo optico para toda a imagem, considera-se um modelo de uxo
am, e neste caso apenas s~ao necessarios 3 pontos para resolver o sistema de incognitas. No
entanto usando apenas 3 pontos pode resultar em soluco~es instaveis, pois a correlac~ao pode
50
~ DE MOVIMENTO NAS IMAGENS
CAPITULO 3. DETECCAO
Figura 3.4: No topo esquerdo: a imagem com os 8 pontos de interesse usados para estimar
o uxo, a imagem central mostra os pontos identicados pelo processo de correlac~ao, a
imagem a direita mostra a diferenca entre as duas imagens anteriores. Em baixo, a
esquerda encontra-se a diferenca entre a segunda imagem, e a imagem original deslocada
pelo campo de uxo estimado pelo processo de Calculo de uxo optico usando correlac~ao.
falhar em algum ponto. Para resolver este problema s~ao usados m pontos de m regi~oes
diferentes da imagem. O vector de medidas efectuado para cada ponto e [u_ i ; v_ i ; ui ; vi ]T
e usando um metodo de mnimos quadrados, pode-se obter a soluc~ao do sistema. Para
cada ponto considerado obtem-se a seguinte relac~ao matricial:
2
2
4
3
2
5
4
1 ui vi 0 0 0
u_i
=
v_i
0 0 0 1 ui vi
6
6
6
6
36
6
6
56
6
6
6
6
6
4
a1
a2
a3
b1
b2
b3
3
7
7
7
7
7
7
7
7
7
7
7
7
7
5
(3.22)
3.2. CALCULO
DO FLUXO OPTICO
51
Figura 3.5: Evoluc~ao do algoritmo de uxo optico normal. Da esquerda para a direita,
encontra-se representada a evoluc~ao da cena, e o respectivo uxo no plano log-polar.
Em geral, dado um sistema linear de equac~oes
A:~x = ~k
(3.23)
onde A e uma matriz de m n elementos (m > n), ~k e um vector de m elementos e ~x
e um vector de n incognitas, a pseudo-inversa, ou soluca~o de mnimos quadrados e dada
por:
~x = AT A ,1 AT ~k
(3.24)
Nos testes foi usado n = 6 e m = 16. Apos a soluc~ao pode-se gerar o uxo optico para
cada pixel da imagem. A Fig. 3.4 mostra um exemplo desta tecnica.
3.2.7 Resultados experimentais com imagens sinteticas
Nesta secc~ao, ser~ao apresentados alguns resultados experimentais, para o uxo optico, e
uxo optico normal descritos anteriormente.
Os primeiros exemplos nas Fig. 3.5, 3.6 e 3.7, s~ao os resultados dos algoritmos
de uxo optico normal, uxo optico usando os modelos ans, e Horn & Schunck (usam
todos uma pir^amide com tr^es nveis de imagens). As imagens s~ao sinteticas e simulam
a translac~ao de uma c^amara na direcca~o do eixo optico. Das guras, pode-se vericar
que o movimento foi detectado por qualquer um dos metodos, sendo o resultado mais
coerente, o dado pelo algoritmo am. Contudo os outros dois, tambem apresentam um
bom comportamento, no entanto dos tr^es metodos, o uxo optico normal e o mais rapido.
A performance obtida pelo algoritmo de uxo optico normal deve-se a utilizaca~o dos
estados de pre- e pos-processamento.
Uma das formas de testar a robustez dos algoritmos na detecc~ao de movimento, e a
utilizac~ao de situac~oes onde a velocidade na imagem aumente ou seja, que esteja sujeita
52
~ DE MOVIMENTO NAS IMAGENS
CAPITULO 3. DETECCAO
Figura 3.6: Evoluc~ao do algoritmo de uxo optico baseado no modelo am
Figura 3.7: Evoluca~o do algoritmo de Horn & Schunck
a uma acelerac~ao. Neste caso sera possvel detectar se os algoritmos conseguiram seguir
perfeitamente o campo de velocidades. Para isso, a mesma situaca~o foi colocada a cada
algoritmo separadamente, onde era simulada uma velocidade crescente. A velocidade
para dois \pixels" consecutivos foi medida, enquanto a sequ^encia decorria. Neste caso
a cena era oblqua relativamente a c^amara, e a Fig 3.8 mostra a evoluc~ao temporal da
velocidade para os tr^es metodos. Conforme pode ser visto, na 9a amostra, onde o pixel
apresenta velocidade n~ao nula, o metodo am detectou velocidade zero, o Horn & Schunck
detectou velocidade diferente de zero, devido ao fenomeno de propagac~ao, e nalmente, o
metodo do uxo optico normal, com a ajuda do ltro - conseguiu detectar a velocidade
crescente.
As experi^encias que se seguem demonstram os resultados para o metodo de renamento
do modelo am conforme explicado na secca~o 3.2.4, neste caso no plano log-polar, de
modo a ser utilizado na detecca~o da posic~ao do FOE .
Na imagem representada na Fig. 3.9 o observador movimenta-se para a frente em
direcc~ao ao canto da parede. Os par^ametros do modelo am para a imagem cartesiana
(256 256) s~ao:
(a1; a2; a3; b1; b2; b3) = (,0:080501; 0:001473; ,0:000403; 0:038492; 0:000294; 0:005596)
enquanto para o modelo am da imagem log-polar (usando 180 amostras angulares e
3.2. CALCULO
DO FLUXO OPTICO
53
2.5
2
velocity
1.5
1
0.5
0
1
2
3
4
5
6
Samples in time
7
8
9
2
3
4
5
6
samples in time
7
8
9
3
2.5
Velocity
2
1.5
1
0.5
0
1
Figura 3.8: Evoluc~ao temporal da velocidade para dois \pixels" consecutivos( + -uxo
optico Normal * -Modelo am o -Horn & Schunck)
54
~ DE MOVIMENTO NAS IMAGENS
CAPITULO 3. DETECCAO
Figura 3.9: No topo esquerdo, esta representada a sequ^encia. No topo direito o respectivo
uxo optico normal. Em baixo a esquerda o modelo am para a imagem cartesiana, e em
baixo a direita o modelo am para a respectiva imagem log-polar.
a = b = 1:025), foi detectado:
(a1; a2; a3; b1; b2; b3) = (,0:057809; 0:000917; ,0:000409; 0:015966; 0:000031; 0:001717)
a maior diferenca pode ser vista em termos dum valor de escalonamento entre os dois tipos
de par^ametros, e este facto acontece devido ao numero de pontos envolvidos no calculo ser
diferente, no entanto ambos os par^ametros mant^em a tend^encia do movimento detectado
(com a vantagem do log-polar necessitar de menor informaca~o).
No segundo exemplo, foram utilizadas imagens reais, e a c^amara roda para a esquerda,
o modelo am para a imagem cartesiana detectou:
(a1; a2; a3; b1; b2; b3) = (,1:053742; ,0:000685; 0:000571; ,0:007082; 0:000003; ,0:000006)
enquanto para a imagem log-polar:
(a1; a2; a3; b1; b2; b3) = (,0:173429; ,0:000018; 0:000218; ,0:011265; ,0:000040; ,0:000049)
e novamente os par^ametros n~ao s~ao iguais, mas mant^em a tend^encia do movimento efectuado.
3.2. CALCULO
DO FLUXO OPTICO
55
Figura 3.10: Em cima a esquerda encontra-se a sequ^encia. Em cima a direita o respectivo
uxo optico normal. Em baixo a esquerda, o resultado do modelo am nas imagens
cartesianas, e a direita o resultado do modelo am aplicado as respectivas imagens logpolar.
56
~ DE MOVIMENTO NAS IMAGENS
CAPITULO 3. DETECCAO
3.2.8 Medida do desempenho de algoritmos de calculo de uxo
optico em imagens log-polar e cartesianas
Barron e outros [J. Barron e D. Fleet 94] implementaram uma serie de tecnicas de calculo
de uxo optico de modo a comparar as suas performances. Nesta secca~o vamos usar as
mesmas denic~oes para analisar os uxos obtidos, mas usando imagens log-polar. Os
resultados apresentados usam as sequ^encias de imagens \Translating and Diverging Tree
sequences", no plano cartesiano e no plano log-polar (para cada caso sera apresentado o
Erro medio (Ave. Err.), Desvio padr~ao (Sta. Dev.) e Densidade (Dens.)).
O algoritmo de uxo optico normal foi implementado, usando um pir^amide com dois
nveis (Now 2L) e usando uma pir^amide com um nvel (Now 1L).
As imagens foram ltradas com tr^es tipos diferentes de ltros, um ltro gaussiano com
= 1:5, um ltro FIR com mascara
[0:051; 0:0; ,0:087; 0:0; 0:298; 0:475; 0:298; 0:0; ,0:087; 0:0; 0:051]
aplicado na direcc~ao u e de seguida na direcc~ao v, e um ltro de Wechsler [H. Wechsler 90]
denido como:
c c c c c
c b b b c
(3.25)
c b a b c
c b b b c
c c c c c
onde 0 < a < 0:5, b = 1=16 e c = 1=32 , a=16.
2
3
6
6
6
6
6
6
6
6
6
4
7
7
7
7
7
7
7
7
7
5
O processo de estimac~ao das derivadas temporais e espaciaise extremamente importante tal como pode ser visto atraves de estudos realizados por F. Bergholm [F. Bergholm 93].
Devido a esse facto, para estimar as derivadas temporais e espaciais foram usados cinco
metodos diferentes:
1. Para as derivadas espaciais: a matriz [[,1; 0; 1]; [,2; 0; 2]; [,1; 0; 1]] para a direcca~o
u e na direcc~ao v pela sua transposta, em cada caso, o resultado e dividido por 8:0.
3.2. CALCULO
DO FLUXO OPTICO
Dif.
Dif.
1
Dif.
2
Dif.
3
Dif.
4
Dif.
5
Gauss com = 1:5
Metodo Ave. Sta. Den.
Err. Dev.
Now 2L 44.32 19.26 27%
Now 1L 37.05 16.22 19%
Horn 37.63 14.97 28%
Ane 26.96 9.83 28%
Second 36.19 11.82 28%
Ane
Now 2L 45.19 17.12 27%
Now 1L 43.76 16.41 24%
Horn 44.81 16.56 28%
Ane 41.31 15.24 28%
Second 45.47 16.74 28%
Ane
Now 2L 47.49 19.50 28%
Now 1L 39.70 18.45 16%
Horn 36.16 15.25 28%
Ane 26.79 14.37 28%
Second 30.34 8.97 28%
Ane
Now 2L 44.29 19.42 28%
Now 1L 38.66 16.12 19%
Horn 38.30 15.12 28%
Ane 28.63 9.55 28%
Second 37.41 12.48 28%
Ane
Now 2L 44.22 19.36 28%
Now 1L 37.85 16.08 19%
Horn 37.90 15.03 28%
Ane 27.87 9.71 28%
Second 36.29 11.78 28%
Ane
57
ltro FIR
Ave. Sta. Den.
Err. Dev.
45.15 18.96 27%
38.33 16.44 19%
37.92 14.70 28%
27.37 10.13 28%
36.15 11.61 28%
ltro de Wechsler
Ave. Sta. Den.
Err. Dev.
44.56 19.18 27%
37.42 16.25 19%
37.90 14.87 28%
27.09 10.06 28%
36.17 11.72 28%
45.59
44.37
45.22
41.91
45.72
17.15
16.60
16.56
15.51
16.83
27%
24%
28%
28%
28%
45.27
44.05
44.88
41.54
45.59
17.17
16.41
16.68
15.38
16.78
27%
24%
28%
28%
28%
47.17
41.31
37.19
26.90
30.54
19.66
18.78
15.39
14.74
8.15
27%
16%
28%
28%
28%
47.24
40.35
36.59
26.83
30.40
19.32
18.54
15.13
14.51
8.56
27%
16%
28%
28%
28%
45.71
40.13
39.28
29.80
37.93
18.79
16.95
15.72
9.87
12.71
27%
19%
28%
28%
28%
45.28
39.07
38.82
29.13
37.62
19.06
16.35
15.21
9.69
12.55
27%
19%
28%
28%
28%
45.37
39.43
38.67
28.85
36.45
18.80
16.52
15.26
10.06
11.75
27%
19%
28%
28%
28%
44.88
38.28
38.26
28.23
36.33
19.03
16.19
14.97
9.90
11.72
27%
19%
28%
28%
28%
Tabela 3.1: Resultados para a sequ^encia \Translating Tree" usando imagens Log-Polar
~ DE MOVIMENTO NAS IMAGENS
CAPITULO 3. DETECCAO
58
Gauss com = 1:5
Ave. Sta. Den.
Err. Dev.
Now 2L 54.97 13.80 99%
Now 1L 45.62 15.91 61%
Horn 46.34 11.25 100%
Ane 20.59 8.28 100%
Second 18.30 0.94 100%
Ane
Now 2L 59.30 4.40 97%
Now 1L 59.01 4.33 86%
Horn 59.47 3.12 100%
Ane 53.84 2.96 100%
Second 53.43 0.72 100%
Ane
Now 2L 57.74 13.68 99%
Now 1L 41.84 20.20 49%
Horn 39.71 16.79 100%
Ane 10.31 18.31 100%
Second 1.09 0.58 100%
Ane
Now 2L 55.32 13.55 99%
Now 1L 46.08 15.90 60%
Horn 46.86 11.34 100%
Ane 23.89 11.05 100%
Second 19.96 1.38 100%
Ane
Now 2L 55.06 13.76 99%
Now 1L 45.64 16.02 60%
Horn 46.55 11.36 100%
Ane 22.61 10.87 100%
Second 18.65 1.19 100%
Ane
Correla. 1.55 0.93 100%
Dif. Metodo
Dif.
1
Dif.
2
Dif.
3
Dif.
4
Dif.
5
Ave.
Err.
56.33
47.26
45.49
19.20
17.16
ltro FIR
Sta. Den.
Dev.
12.93 99%
15.55 61%
10.53 100%
7.89 100%
0.66 100%
ltro de Wechsler
Ave. Sta. Den.
Err. Dev.
55.51 13.49 98%
45.78 15.68 60%
45.74 10.95 100%
19.54 7.37 100%
17.62 0.76 100%
59.95
59.74
59.93
54.82
54.09
4.22 98% 59.40 4.30 97%
4.59 89% 59.13 4.38 87%
3.06 100% 59.44 3.16 100%
2.75 100% 53.95 2.98 100%
0.52 100% 53.54 0.74 100%
58.50
44.17
37.72
9.48
1.87
12.42
19.57
16.29
15.12
0.07
99% 57.73 13.61 99%
50% 41.80 19.89 49%
100% 38.42 15.96 100%
100% 7.56 12.24 100%
100% 1.16 0.14 100%
56.13
48.51
47.21
22.99
19.00
12.87
15.39
10.60
9.14
1.20
98%
64%
100%
100%
100%
55.84
46.23
46.50
21.84
18.79
13.19
15.58
10.94
8.41
0.81
98%
60%
100%
100%
100%
56.35
47.63
46.29
21.34
17.48
12.87
15.76
10.81
9.50
0.96
98%
61%
100%
100%
100%
55.59
45.75
46.07
20.55
17.66
13.48
15.77
11.10
8.47
0.85
98%
59%
100%
100%
100%
1.55
0.93 100%
6.98
5.07 100%
Tabela 3.2: Resultados para a sequ^encia \Translating Tree" usando imagens cartesianas
3.2. CALCULO
DO FLUXO OPTICO
Dif.
Dif.
1
Dif.
2
Dif.
3
Dif.
4
Dif.
5
Gauss com = 1:5
Metodo Ave. Sta. Den.
Err. Dev.
Now 2L 30.10 9.30 28%
Now 1L 26.41 10.69 19%
Horn 27.36 10.27 28%
Ane 18.33 10.38 28%
Second 23.23 8.63 28%
Ane
Now 2L 32.88 8.84 26%
Now 1L 32.35 8.32 24%
Horn 32.60 8.95 28%
Ane 31.06 9.15 28%
Second 32.06 8.71 28%
Ane
Now 2L 29.72 9.56 28%
Now 1L 25.16 11.80 16%
Horn 23.78 10.94 28%
Ane 10.16 10.22 28%
Second 14.62 8.57 28%
Ane
Now 2L 30.43 9.29 28%
Now 1L 27.66 10.37 18%
Horn 27.96 10.42 28%
Ane 20.69 9.99 28%
Second 24.83 8.64 28%
Ane
Now 2L 30.18 9.38 28%
Now 1L 26.88 10.54 18%
Horn 27.66 10.33 28%
Ane 19.49 10.18 28%
Second 24.02 8.63 28%
Ane
59
ltro FIR
Ave. Sta. Den.
Err. Dev.
30.37 9.06 27%
27.33 10.67 19%
27.51 10.34 28%
19.12 10.53 28%
23.47 8.64 28%
ltro de Wechsler
Ave. Sta. Den.
Err. Dev.
30.37 9.21 27%
26.77 10.71 19%
27.49 10.19 28%
18.61 10.45 28%
23.31 8.64 28%
33.29
32.85
33.00
31.54
32.38
8.85
8.41
8.94
9.24
8.70
27%
24%
28%
28%
28%
32.81
32.56
32.69
31.19
32.19
8.80
8.41
8.99
9.30
8.71
27%
24%
28%
28%
28%
30.24
26.47
23.56
10.68
14.99
9.76
11.81
10.93
10.37
8.60
28%
16%
28%
28%
28%
30.20
25.67
23.80
10.46
14.72
9.49
11.80
10.96
10.26
8.58
28%
16%
28%
28%
28%
31.02
29.84
29.42
22.68
26.54
9.82
11.37
10.91
10.68
8.65
27%
20%
28%
28%
28%
30.52
28.45
28.31
21.46
25.46
9.30
10.59
10.44
10.25
8.65
27%
19%
28%
28%
28%
30.86
28.70
28.29
21.11
25.26
9.88
11.35
10.76
10.83
8.65
27%
19%
28%
28%
28%
30.34
27.50
27.94
20.14
24.44
9.15
10.64
10.39
10.36
8.64
27%
18%
28%
28%
28%
Tabela 3.3: Resultados para a sequ^encia \Diverging Tree" usando imagens Log-Polar
~ DE MOVIMENTO NAS IMAGENS
CAPITULO 3. DETECCAO
60
Gauss com = 1:5
Ave. Sta. Den.
Err. Dev.
Now 2L 37.47 13.66 97%
Now 1L 28.60 12.50 61%
Horn 30.68 11.59 100%
Ane 19.40 8.12 100%
Second 18.67 4.60 100%
Ane
Now 2L 39.09 11.71 93%
Now 1L 37.64 11.41 85%
Horn 38.49 11.75 100%
Ane 36.81 11.22 100%
Second 36.43 10.44 100%
Ane
Now 2L 38.02 14.65 99%
Now 1L 24.06 15.72 49%
Horn 24.27 13.12 100%
Ane 8.38 10.37 100%
Second 8.59 4.90 100%
Ane
Now 2L 37.51 13.60 97%
Now 1L 29.04 12.77 60%
Horn 31.11 11.75 100%
Ane 20.90 8.38 100%
Second 19.13 4.48 100%
Ane
Now 2L 37.54 13.66 97%
Now 1L 28.45 12.45 59%
Horn 30.80 11.66 100%
Ane 19.19 6.87 100%
Second 17.65 4.11 100%
Ane
Correla. 17.37 9.16 100%
Dif. Metodo
Dif.
1
Dif.
2
Dif.
3
Dif.
4
Dif.
5
Ave.
Err.
37.55
29.70
30.60
19.48
18.68
ltro FIR
Sta. Den.
Dev.
13.44 97%
12.43 63%
11.04 100%
7.59 100%
4.63 100%
ltro de Wechsler
Ave. Sta. Den.
Err. Dev.
37.52 13.67 97%
28.52 12.14 59%
30.47 11.20 100%
19.13 8.19 100%
18.23 4.53 100%
39.52
38.66
39.23
37.89
37.09
12.18
11.81
11.85
11.39
10.69
97%
90%
100%
100%
100%
39.14
37.88
38.58
36.98
36.45
11.67
11.40
11.73
11.10
10.46
93%
87%
100%
100%
100%
37.93
24.85
22.51
6.09
5.81
14.68
15.43
12.07
9.74
3.32
98% 37.86 14.59 99%
49% 24.03 15.26 48%
100% 23.56 12.78 100%
100% 7.70 11.20 100%
100% 7.60 4.40 100%
37.40
31.05
31.87
21.29
19.74
13.20
12.51
11.15
6.95
4.76
97%
67%
100%
100%
100%
37.46
29.08
30.96
20.61
18.69
13.57
12.23
11.44
7.83
4.48
97%
59%
100%
100%
100%
37.47
29.79
30.72
19.03
18.00
13.41
12.45
11.04
5.79
4.29
97%
64%
100%
100%
100%
37.41
28.36
30.49
18.76
17.44
13.66
11.96
11.18
6.31
4.16
97%
58%
100%
100%
100%
22.15 8.54 100% 44.64 23.39 100%
Tabela 3.4: Resultados para a sequ^encia \Diverging Tree" usando imagens cartesianas
3.2. CALCULO
DO FLUXO OPTICO
61
Para a derivada temporal: atraves da diferenca das imagens numa regi~ao de 3 3
\pixels" e o resultado e dividido por 9.
2. Para as derivadas espaciais: o vector 121 [1; ,8; 0; 8; 1], e usado para preencher uma
matriz de 5 5 onde cada linha e uma copia do vector. Para a derivada temporal:
atraves da diferenca das imagens numa regi~ao de 5 5 \pixels" e o resultado e
dividido por 25.
3. Para as derivadas espaciais: a matriz [[,1; 1]; [,1; 1]] para a direcc~ao u e na direcc~ao
v pela sua transposta, em cada caso, o resultado e dividido por 4:0. Para a derivada
temporal: atraves da diferenca das imagens numa regi~ao de 2 2 \pixels" e o
resultado e dividido por 4.
4. Para as derivadas espaciais: o vector 121 [1; ,8; 0; 8; 1] para a direcc~ao u e na direcc~ao
v pelo seu vector transposto. Para a derivada temporal: atraves da diferenca das
imagens numa regi~ao de 2 2 \pixels" denida pela matriz [[0; 1; 0]; [1; 0; 1]; [0; 1; 0]]
e o resultado e dividido por 4.
5. Para as derivadas espaciais: o vector [,1; 0; 1] para a direcc~ao u e na direcc~ao v
pelo seu vector transposto, o resultado e dividido por 2. Para a derivada temporal:
atraves da diferenca das imagens numa regi~ao de 2 2 \pixels" denida pela matriz
[[0; 1; 0]; [1; 0; 1]; [0; 1; 0]] e o resultado e dividido por 4.
As tabelas 3.1, 3.2, 3.3, 3.4 apresentam os resultados para as sequ^encias de imagens \translational and diverging tree sequences". Atraves dos resultados apresentados,
verica-se que o metodo para estimar as derivadas desempenha um papel bastante importante na performance da tecnica utilizada, enquanto para os ltros experimentados os
resultados apresentam performances semelhantes [F. Bergholm 93]. Em geral, pode-se
concluir que a performance da detecca~o do uxo optico feito sobre imagens log-polar e
mais baixa do que em imagens cartesianas, no entanto os calculos s~ao mais rapidos (em
media, para as imagens testadas apenas e necessario efectuar 28% dos calculos relativamente ao caso cartesiano). Os resultados para a sequ^encia de imagens divergente em
log-polar s~ao melhores quando comparados com a sequ^encia de translaca~o. Este facto
62
~ DE MOVIMENTO NAS IMAGENS
CAPITULO 3. DETECCAO
Sequ^encia Divergente
Ave. Sta. Den.
Err. Dev.
Fleet ( = 1:25)
2.43 1.84 83%
Anandan
24.20 14.66 100%
Horn (modicado) k rI k 5:0
4.98 4.01 100%
Nagel k rI k 2 5:0
5.74 5.72 100%
Lucas (2 1:0)
4.60 3.20 80%
Singh (passo = 2; n = 2; w = 2; N = 4) 18.57 7.21 100%
Metodo
Sequ^encia de translaca~o
Ave. Sta.
Den.
Err. Dev.
28.01 14.38 82%
30.94 15.52 100%
28.38 13.21 100%
37.52 30.17 100%
28.00 13.75 80%
51.48 26.37 100%
Tabela 3.5: Resultados da estimac~ao do uxo optico usando imagens log-polar
para as sequ^encias de translac~ao e divergente, usando tecnicas descritas em
[J. Barron e D. Fleet 94]
conrma que as imagens log-polar s~ao uma boa ferramenta para detectar campos de velocidades dessa natureza (em alguns algoritmos a performance e superior ao respectivo
caso cartesiano). E importante referir que a transformaca~o log-polar foi efectuada com
N = 150, e a = b = 1:025, o que representa neste caso 28% da informaca~o contida na imagem cartesiana. Entre os algoritmos am, verica-se tambem que o mais consistente e o
\metodo am por regi~oes", devido as imagens visualizadas apresentarem descontinuidades
em profundidade.
Os resultados indicados na tabela 3.5, foram obtidos atraves da implementaca~o descrita em [J. Barron e D. Fleet 94], mas usando a representac~ao log-polar da imagem. O
respectivo uxo correcto foi convertido tambem para log-polar atraves da equac~ao 2.35, e
serve de base de comparac~ao com os uxos obtidos dos respectivos algoritmos, utilizando
as medidas estatsticas indicadas anteriormente. Atraves dos resultados, pode-se constatar que estes metodos \o-line" no caso da sequ^encia de translaca~o apresentam tambem
um erro elevado, mas para o caso da sequ^encia divergente, os resultados s~ao na realidade
bastante bons (deve-se salientar que todos os metodos implementam a ltragem usando
mais do que duas imagens para estimar a derivada temporal, enquanto os metodos apresentados nas tabelas 3.1, 3.2, 3.3, 3.4 apenas usam duas imagens, e as imagens n~ao s~ao
ltradas temporalmente).
3.2. CALCULO
DO FLUXO OPTICO
Metodo de FLEET
Base
logartmica
1.025
1.020
1.015
1.010
Sequ^encia Divergente
Ave. Sta. Den.
Err. Dev.
2.43 1.84 83%
5.41 3.83 68%
12.02 7.39 51%
21.16 9.47 38%
63
Sequ^encia de Translaca~o
Ave. Sta.
Den.
Err. Dev.
28.01 14.38 82%
27.18 13.99 68%
25.80 12.53 54%
30.75 21.58 33%
Tabela 3.6: Aplicac~ao do metodo de Fleet a sequ^encia divergente e de translac~ao da arvore,
usando diferentes bases para a transformaca~o log-polar (mantendo a mesma resoluc~ao
angular)
Os resultados indicados na tabela 3.6, foram obtidos atraves do metodo de Fleet, aplicado as sequ^encias de translac~ao e divergente em log-polar, mas variando a base
logartmica da transformac~ao log-polar, mantendo a mesma resoluc~ao angular. Dos resultados torna-se evidente que a escolha da base do log-polar e decisiva para a performance
obtida para o uxo calculado. Pode-se de certa forma armar que a base do log-polar
desempenha o papel de sintonizar o uxo divergente que se pretende detectar coerentemente.
Em conclus~ao, estes resultados indicam que em geral o calculo do uxo optico sobre
imagens log-polar e mais ruidoso do que sobre imagens cartesianas, no entanto para uxos
divergentes, o log-polar apresenta boas performances com uma quantidade de calculos
inferior, o que neste caso e util, pois e esta a conguraca~o de uxo que pretendemos
detectar.
64
~ DE MOVIMENTO NAS IMAGENS
CAPITULO 3. DETECCAO
Captulo 4
Determinac~ao de Par^ametros do
Movimento
- Determinac~ao da direcc~ao de translac~ao
Este captulo reecte o nosso esforco para implementar uma soluca~o que resolva o
problema da navegaca~o de um observador movel, de modo a detectar a sua direcca~o de
translac~ao e manter a c^amara orientada para essa direcc~ao apesar das eventuais alteraco~es
de movimento do observador. O algoritmo que detecta a direcca~o do movimento explora
as propriedades geometricas da transformaca~o log-polar. Os ensaios experimentais foram
efectuados numa plataforma movel equipada com um sistema de vis~ao activa descrito no
Ap^endice B.
Um observador movel que se movimente num meio ambiente desconhecido necessita
de obter a informac~ao visual mais rica possvel, posicionando o sensor de forma a captar
a informac~ao necessaria a actividade que o observador esta a realizar. Considera-se que
a melhor informac~ao visual e por exemplo, possuir as melhores condic~oes de iluminaca~o,
de focagem e o melhor alinhamento para o sensor visual. Neste captulo, apresenta-se
um algoritmo que permite controlar o sensor visual de modo que a informac~ao visual
captada seja util, i.e., ajusta-o para uma direcca~o preferida enquanto em movimento.
65
66
~ DE PARAMETROS
^
CAPITULO 4. DETERMINACAO
DO MOVIMENTO
X
P
Z
Y
Figura 4.1: Campo de uxo optico visualizado por um observador que se movimente na
direcc~ao do polo P (neste caso direcca~o do eixo Z).
Neste trabalho considera-se como direcca~o preferida a direcca~o denida pelo centro de
perspectiva e o foco de expans~ao.
Nas tarefas de navegac~ao atraves de vis~ao, o conhecimento do foco de expans~ao pode
ser usado para determinar e controlar o nosso proprio movimento translacional no espaco.
Este facto e importante, porque com a posic~ao do foco de expans~ao e possvel estimar
alguns dos par^ametros de velocidade do agente ou observador em movimento. Outra
possibilidade pode ser a utilizac~ao desse mesmo par^ametro para alinhar o sensor visual
com a direcc~ao de translac~ao do sistema.
Num sistema de vis~ao activa podemos denir uma direcc~ao preferencial de forma a
permitir captar informac~ao importante para a navegac~ao. No nosso caso esta direcca~o
corresponde a direcca~o de translac~ao do observador. Um sistema visual que, activamente
tente manter essa direcc~ao e equivalente a manter constante a posica~o do foco de expans~ao
no centro da imagem obtida do sensor visual.
4.1 Introduc~ao
Um observador atraves da sua vis~ao (ou c^amaras no caso dum observador articial),
quando se movimenta com uma velocidade de translaca~o num meio ambiente estatico,
observa a projecc~ao dos deslocamentos nas imagens de uma forma similar ao apresentado
na Fig. 4.1. Se o observador mantiver constante a sua velocidade de translaca~o, o
~
4.1. INTRODUCAO
67
polo frontal, equivalente ao ponto central do uxo radial, sera estacionario. Tambem se
verica, que para um objecto estacionario que se encontre numa direcca~o diferente da
direcc~ao do polo frontal, as imagens retinais desses objectos movem-se mais rapidamente
em func~ao do desvio angular relativo a direcc~ao denida pelo polo frontal e pelo centro
de coordenadas (veja-se Fig. 4.1), se estiverem a mesma dist^ancia.
Contudo, se num observador os olhos, corpo ou cabeca (respectivamente c^amaras,
robot movel e sistema de vis~ao num sistema articial) induzem um movimento rotacional,
o polo P n~ao mant^em a mesma estabilidade posicional.
Uma forma de representar o efeito de projecca~o do movimento de um observador e
atraves de uma esfera [F. Bergholm 90]. A esfera que representa o mundo visvel e apenas
uma elegante idealizaca~o matematica que a partida e suciente para representar os campos
de uxo que podem ser gerados pelos movimentos do observador. Na pratica, esta estrutura de representac~ao pode ser simulada parcialmente atraves do uso de c^amaras normais.
A imagem capturada pelas c^amaras e equivalente a efectuar uma amostra da superfcie
esferica. Normalmente esta amostra possui informaca~o visual suciente para ser utilizada
no controlo da actividade do observador. Neste e no proximo captulo apresentam-se dois
algoritmos para navegac~ao com base neste princpio.
Quando um observador se movimenta no espaco, para se obter a maxima informac~ao
possvel, os olhos devem estar alinhados com a direcca~o do movimento. So desta forma e
possvel detectar obstaculos, corrigir trajectorias de navegaca~o, etc. Todos os observadores
humanos no seu dia a dia, efectuam comportamentos deste genero sem se aperceberem.
Uma das direcc~oes preferenciais do alinhamento do sensor visual e a direcc~ao de translac~ao. Desta forma o conhecimento do polo frontal e crucial para efectuar este genero
de comportamento. Neste caso o objectivo e manter o polo frontal no centro do campo
visual. Este captulo reecte o estudo da implementaca~o deste comportamento especco,
atraves de experi^encias simuladas e reais. Descreve-se neste captulo um algoritmo para
detectar a direcc~ao preferida do sensor visual dum observador movel e manter essa mesma
direcc~ao. O algoritmo detecta a direcc~ao do movimento translacional e explora as propriedades geometricas da transformac~ao log-polar para detectar o polo frontal P - veja-se
Fig. 4.1.
Nas proximas secco~es sera ent~ao introduzido em maior pormenor o processo que foi
68
~ DE PARAMETROS
^
CAPITULO 4. DETERMINACAO
DO MOVIMENTO
brevemente descrito nesta introduc~ao.
4.2 Estimac~ao do foco de expans~ao
Esta secc~ao trata do problema da estimaca~o da direcc~ao do vector de velocidade de translac~ao, atraves da medida das velocidades sobre imagens, quando um observador se movimenta num ambiente estatico. A intercepc~ao do vector de movimento translacional, com o
plano imagem gera um ponto que se denomina como foco de expans~ao ou abreviadamente
por ponto FOE [R. Guissin e S. Ullman 91], [C. Fermuller e Y. Aloimonos 91].
Em alguns casos especiais (baixa velocidade de rotac~ao) os vectores de uxo induzidos
na imagem devido ao proprio movimento do observador, apresentam algumas propriedades
geometricas, que podem ser uteis para detectar na imagem o local onde se encontra o foco
de expans~ao. Estas propriedades geometricas, baseiam-se no facto de que os vectores de
uxo s~ao radiais a partir da posic~ao do foco de expans~ao, e que a linha que passa pelo
foco de expans~ao e pelo centro da imagem apenas possu uxo radial conforme pode ser
visto na Fig. 4.2.
Usando estes factos, pode-se estabelecer um mecanismo de procura da posic~ao do
FOE . O processo baseia-se na detecc~ao da orientac~ao angular (direcc~ao F OE ) da linha
que passa pelo centro da imagem e pelo FOE , atraves dum processo de procura para cada
orientac~ao possvel, escolhendo-se a orientac~ao que apresenta menor uxo circular. De
seguida para detectar a posic~ao do FOE , faz-se uma translac~ao do sistema de coordenadas
para cada ponto pertencente a linha encontrada, ate se encontrar um ponto, do qual os
vectores de uxo s~ao radiais (a este metodo chamamos de retina din^amica).
Em navegac~ao atraves de vis~ao, o conhecimento do par^ametro FOE , pode ser utilizado
para determinar e controlar o nosso proprio movimento no espaco. No nosso caso iremos
demonstrar que e possvel detectar a direcca~o de translac~ao do nosso proprio movimento,
atraves de testes efectuados num robot movel simulado e real e com c^amaras com graus
de liberdade de \pan", \tilt" e verg^encia (veja-se Ap^endice C). No caso do robot movel
simulado, a c^amara encontra-se perto do eixo de coordenadas de rotaca~o do robot, de
modo a simplicar a detecc~ao do FOE , ou caso contrario sera impossvel medir com
~ DO FOCO DE EXPANSAO
~
4.2. ESTIMACAO
69
X
FOE
Di
rec ~
çao
θ
FO
E
Y
Figura 4.2: Propriedade geometrica dos vectores de uxo, quando o observador apresenta
uma velocidade de translaca~o.
precis~ao essa mesma posic~ao. O facto de se poder considerar que o robot se movimenta
num plano horizontal e importante, porque a velocidade translacional e perpendicular ao
vector velocidade rotacional, o que simplica a detecc~ao da direcc~ao F OE , tal como sera
descrito nas proximas secc~oes. O robot simulado e id^entico ao robot descrito no Ap^endice
B.
Em primeiro lugar, sera dada uma apresentac~ao das equac~oes de velocidade no plano
cartesiano, atraves do uso da transformaca~o de coordenadas cartesianas para coordenadas
polares de modo a adquirir o conhecimento de como se comporta o uxo induzido na
direcc~ao FOE , quando a restrica~o descrita atras e utilizada para detectar a linha (restric~ao:
vector velocidade translacional e perpendicular ao vector velocidade rotacional).
De seguida, mostra-se que existe uma relaca~o muito proxima entre os uxos induzidos
descritos em coordenadas polares e em coordenadas log-polares, o que permite expandir o
metodo ao caso de imagens log-polar. Este facto e importante, porque atraves do uso de
imagens log-polar, o processo e mais rapido do que com imagens cartesianas (um exemplo
de um trabalho com algumas semelhancas pode ser visto em [R. Guissin e S. Ullman 91]).
Finalmente, ser~ao apresentados os resultados experimentais, no nal desta secca~o 4.2.
70
~ DE PARAMETROS
^
CAPITULO 4. DETERMINACAO
DO MOVIMENTO
4.2.1 Equaco~es de velocidade expressas em coordenadas polares
Para obter a express~ao da velocidade do observador em coordenadas polares e necessario
conhecer os seus par^ametros de movimento: velocidade rotacional e translacional. A medida que o observador se movimenta no espaco tridimensional n~ao homogeneo, as imagens
adquiridas sofrem alterac~oes. Estas alteraco~es do uxo optico induzido na imagem podem
ser formuladas atraves da equac~ao 2.29. As equac~oes de velocidade no plano cartesiano
expressas em coordenadas polares, podem ser encontradas atraves da transformac~ao 2.35
aplicada a equaca~o de movimento 2.29. Apos essa transformaca~o, obtem-se a seguinte
relac~ao (onde Tcp representa a transformac~ao):
2
4
3
_
1 T pA~v + T p B~!
=
Z c t c
_
(4.1)
5
Quando o observador se movimenta com uma velocidade de translac~ao n~ao nula e uma
velocidade de rotac~ao nula, a velocidade (uxo optico teorico) (u;_ v_ ) no ponto do foco de
expans~ao e nula. Por denic~ao o FOE corresponde ao ponto de intercepc~ao do vector de
movimento translacional com o plano imagem, e tem por coordenadas:
(FOEx ; FOEy ) = fx Vx ; fy Vy
(4.2)
Vz Vz
Com esta denic~ao, a linha que passa pelo centro da imagem e pelo ponto de FOE
apresenta as seguintes relac~oes:
8
>
>
>
>
>
<
>
>
>
>
>
:
y
sin() = p(f Vfy) V+(f
V)
x x
cos() =
2
y y
2
x
p(f Vfx)2V+(f
x x
y Vy )2
(4.3)
Chama-se a atenc~ao do leitor para o seguinte facto: aquilo que se pretende numa
primeira fase e detectar a orientac~ao da recta denida pelo foco de expans~ao e pelo
centro da imagem (recta que contem a origem e o FOE ). O algoritmo para determinar
essa orientac~ao efectua uma pesquisa em todas as orientac~oes possveis, ate encontrar a
orientac~ao onde o uxo circular e menor. A equac~ao do uxo circular encontra-se na
segunda linha do sistema matricial indicado na equaca~o 4.1. No entanto, esta equaca~o
~ DO FOCO DE EXPANSAO
~
4.2. ESTIMACAO
71
depende da profundidade Z de cada ponto considerado, o que a partida inviabiliza o
processo de minimizac~ao, pois n~ao existe forma de conhecer a profundidade de cada ponto.
Tal facto pode ser ultrapassado atraves de restric~oes impostas aos vectores velocidade de
modo que a equac~ao para _ obtida a partir de 4.1 n~ao dependa de Z . Uma das restrico~es
que verica tal facto e:
vx :wx = ,vy :wy
(4.4)
Esta equac~ao pode tambem ser escrita na forma vectorial atraves de:
h
2
3
4
5
w
vx vy : x = 0
wy
i
(4.5)
o que e equivalente a armar que estes dois vectores devem ser perpendiculares 1. Note-se
que os vectores encontram-se no mesmo plano.
Utilizando as equac~oes 4.4 e 4.3, em conjunca~o com a equac~ao 4.1 obtemos (na
direcc~ao FOE ):
(4.6)
:_ = cos2()wz ffyx , ffxy , wz ffxy
h
i
e (na direcc~ao perpendicular a direcc~ao F OE ):
_ = 2 sin() wfyx , cos() wfxy + cos() sin()wz
h
fx
fy
, ffxy + vZz
i
(4.7)
Verica-se assim, que a equac~ao 4.6 n~ao depende de Z e apenas apresenta depend^encias
de !z , sendo os outros par^ametros xos para um determinado e .
De momento, interessa tambem constatar que se pode obter semelhantes resultados
para o log-polar, no entanto na secc~ao 4.2.2 sera descrito a forma de utilizar as equaco~es
4.6 e 4.7, para efectuar a detecc~ao da direcc~ao F OE .
Como sera visto na secc~ao que se segue, pode-se efectuar a mesma analise para o caso
do plano log-polar e as equaco~es obtidas s~ao muito semelhantes as equac~oes 4.6 e 4.7,
a menos de determinados factores constantes. Tal facto permite pensar que sera viavel
utilizar o uxo optico medido em imagens log-polar para estimar a posica~o do foco de
expans~ao.
No caso do robot movel, esta restric~ao e desnecessaria, porque os movimentos possveis do robot s~ao
descritos por v~t = [0; 0; vz ]T e ~! = [0; !y ; 0]T (veja-se Ap^endice B)
1
72
~ DE PARAMETROS
^
CAPITULO 4. DETERMINACAO
DO MOVIMENTO
Extens~ao para o plano log-polar
Para o caso do plano log-polar, usando a equac~ao de uxo induzido 2.29, mas agora
atraves da transformac~ao dada pela equac~ao 2.37, permite obter uma equac~ao semelhante
a equac~ao 4.1. Esta equac~ao pode ser expressa por (onde Tclp representa a transformaca~o):
2
4
_
= 1 TclpA~vt + TclpB~!
Z
_
3
(4.8)
5
Usando novamente os resultados das equac~oes 4.4, 4.3, mas agora na equaca~o 4.8,
chega-se a seguinte express~ao (na direcc~ao F OE ):
fovea
:a ::_
= fovea
a cos2 (: )w
"
z
fx , fy , a w fx
fovea
zf
fy fx
y
#
(4.9)
e a (na direcc~ao perpendicular a direcc~ao F OE ):
fovea:a : ln(a):_ = (foveaa )2 sin(: ) wfyx , cos(: ) wfxy
h
+foveaa cos(: ) sin(: )wz ffxy
i
, ffxy + foveaZ a vz
(4.10)
Estas duas equac~oes s~ao semelhantes as equaco~es do caso polar, e como para ambos os
casos, para efectuar a procura da direcca~o angular e necessario utilizar um determinado
valor angular incremental, as equaco~es na realidade, representam a mesma entidade (a
diferenca reside nos valores de escalonamento, e na amostragem radial).
Para um melhor esclarecimento dos algoritmos propostos, nas proximas secc~oes denese a variavel r como r = para o caso polar e r = foveaa para o caso log-polar e tambem
a func~ao F (r; ) como F (r; ) = r:_ para o caso polar e F (r; ) = r::_ para o log-polar.
A estimaca~o da posic~ao do FOE e feita em duas etapas em sequ^encia:
a detecc~ao da orientac~ao da linha que passa na direcca~o F OE , atraves do uso de
um algoritmo de procura que minimiza uma funca~o F (r; ), processo este que se
denomina de \Detecca~o da direcca~o F OE "
a procura em todos os pontos da linha encontrada, do ponto a partir do qual, o
uxo e radial, processo este que se denomina por \Detecc~ao da posic~ao do FOE "
~ DO FOCO DE EXPANSAO
~
4.2. ESTIMACAO
73
4.2.2 Detecc~ao da direcc~ao do foco de expans~ao
Nesta secc~ao aborda-se o problema de detectar a direcc~ao F OE , que basicamente e conseguida atraves dum algoritmo de procura unidimensional, de entre o espaco de todas as
orientac~oes possveis dentro dum crculo unitario (usando um valor incremental para
o ^angulo), usando a equaca~o 4.6 ou a equac~ao 4.9.
Para cada uma das direcco~es, atraves do uso de n pontos arbitrarios, estima-se a
seguinte quantidade:
M = cos2(: )wz ffx , ffy , wz ffx
#
"
y
atraves do uso da seguinte relac~ao:
M =
x
y
n,1 F (r ; )
k
k=0
Pn,1
k=0 rk
(4.11)
[F (rk ; ) , rk M ]2
(4.12)
P
e de seguida acumulando uma estimativa de erro E para cada direcca~o:
E =
nX
,1
k=0
Apos a construc~ao desta func~ao, a direcc~ao F OE e seleccionada como sendo a posica~o
onde a func~ao E e mnima. No caso do FOE estar presente no centro da imagem, a
func~ao E deveria ser constante, logo sem mnimos, este problema pode ser resolvido
atraves do uso dum limiar aplicado a func~ao E . No entanto os casos ambguos poder~ao
ser resolvidos, se a partida se tiver uma estimativa do movimento (i.e. ter o conhecimento
em que quadrante se encontra o FOE ).
4.2.3 Detecc~ao da posic~ao do foco de expans~ao
Apos a detecc~ao da direcc~ao da recta que passa pela posica~o do FOE , e necessario agora
utilizar um algoritmo que permita estimar a posica~o do FOE na recta previamente identicada. Para efectuar esta estimaca~o realizaram-se testes experimentais com os seguintes
algoritmos:
Algoritmo da linha - este processo apenas usa os vectores de uxo pertencentes a
linha FOE de modo a detectar o ponto onde o uxo radial muda de sentido. Se
74
~ DE PARAMETROS
^
CAPITULO 4. DETERMINACAO
DO MOVIMENTO
algum ponto for encontrado, esse e considerado como a posic~ao do FOE . Noutra
situac~ao o processo falha.
Algoritmo da FFT - explora o conceito da \Retina Din^amica" atraves da procura
em cada ponto da linha FOE , por aquele onde o respectivo histograma radial e constante. Esse ponto e o FOE . A FFT e usada para detectar a forma do histograma.
Algoritmo do Desvio Padr~ao - este algoritmo e semelhante ao algoritmo da FFT,
mas, usa neste caso, o desvio padr~ao do histograma de uxos radiais, o que permite
detectar a forma do graco do histograma. Interessa-nos tal como no Algoritmo da
FFT detectar gracos que apenas contenham uma componente DC .
Algoritmo da linha
Este algoritmo baseia-se na constatac~ao de que os vectores de uxo divergem do FOE ,
sendo assim possvel utilizar um processo de procura na linha F OE , de modo a encontrar
o local onde se verica a invers~ao do sentido dos vectores de uxo (basta apenas vericar
esta condic~ao, a nvel do uxo radial, uma vez que a linha F OE minimiza o uxo angular).
Efectuando as convenc~oes que se indicam de seguida, e possvel construir uma funca~o
unidimensional de procura, onde o FOE se encontra no ponto associado a passagem por
zero da func~ao. Considere-se para isso as seguintes convenco~es:
a dist^ancia radial dos pontos na semi-linha F OE e positiva e a dist^ancia radial dos
pontos da semi-linha = FOE + e negativa. Esta denic~ao pode ser utilizada
para denir uma variavel que constituira a abcissa da func~ao de procura e que e
utilizada para indicar qual e o ponto da recta sob analise.
o sentido positivo do uxo radial e no sentido da semi-linha F OE , e negativo no
sentido = FOE + . Pode-se assim denir a ordenada da func~ao de procura, com
a particularidade de se obter um graco muito proximo duma recta.
No caso da recta do graco da funca~o de procura passar por zero dentro dos limites
das abcissas da funca~o, o FOE encontra-se dentro da imagem, caso contrario podera ser
atribudo ao respectivo limite, dependendo do declive.
~ DO FOCO DE EXPANSAO
~
4.2. ESTIMACAO
75
Como e obvio, na presenca de rotac~oes, o que foi descrito anteriormente e invalido,
mas nesse caso em vez duma linha teremos uma parabola, tal como foi constatado experimentalmente. Nesta situaca~o, apenas e necessario encontrar o ponto mnimo ou maximo
da parabola, conforme a concavidade desta, ou ent~ao o local onde esta intercepta o eixo
do x. Este pressuposto apenas foi validado experimentalmente para pequenos valores de
wx , wy e wz , n~ao sendo verdadeiro noutros casos.
Para estimar o FOE , foi assim utilizado um algoritmo de mnimos quadrados que permite identicar a forma que mais se aproxima do graco da func~ao de procura construda,
usando o modelo
y = a:x2 + b:x + c
(4.13)
cuja soluc~ao e dada por (usando m pontos):
2
6
6
6
4
m,1 x4[k]
k=0
Pm,1
3
k=0 x [k]
Pm,1
2
k=0 x [k]
P
m,1 x3[k]
k=0
Pm,1
2
k=0 x [k]
Pm,1
k=0 x[k]
P
m,1 x2[k]
k=0
Pm,1
k=0 x[k]
P
m
3
7
7
7
5
2
3
2
6
6
6
4
7
7
7
5
6
6
6
4
a
: b =
c
m,1 y[k]:x2 [k]
k=0
Pm,1
k=0 y[k]:x[k]
Pm,1
k=0 y[k]
P
3
7
7
7
5
(4.14)
onde a,b,c s~ao encontrados atraves da resoluca~o do sistema (a func~ao parabolica representa tambem uma linha, quando necessario, pelo que e suciente usar este modelo, para
contemplar os dois casos descritos anteriormente).
Algoritmo da FFT
Este algoritmo utiliza o conceito da \Retina Din^amica" introduzido na secca~o 2.3. Para
estimar a posic~ao do FOE , a retina e centrada em cada ponto pertencente a linha F OE , e
para cada um destes pontos, e efectuado um histograma dos uxos radiais. Note-se que o
uxo radial para cada ponto inspeccionado e denido relativamente ao centro da retina, e
por isso diferente do uxo radial denido relativamente ao centro da imagem (uxo radial
detectado pelo algoritmo de calculo do uxo optico). Esta diferenca pode ser vista atraves
da Fig. 4.3. Para efectuar o histograma e necessario projectar o uxo optico segundo a
direcc~ao radial da retina que esta a ser inspeccionada. Se a retina se encontrar centrada
no FOE , o uxo optico sera radial, e apenas para este caso, o histograma apresentara
um valor constante para qualquer das direcc~oes envolvidas no calculo. Caso contrario,
76
~ DE PARAMETROS
^
CAPITULO 4. DETERMINACAO
DO MOVIMENTO
B
A
Figura 4.3: Exemplo do conceito da \Retina Din^amica" aplicada ao caso log-polar, atraves
da utilizac~ao de 8 direcc~oes distintas (o ponto A indica o centro do log-polar e o ponto B
o centro da retina din^amica).
o histograma apresentara termos modulados. Estes termos, aparecem no histograma,
porque quando a retina n~ao se encontra centrada no FOE , a componente radial utilizada
no histograma e diferente para diferentes direcc~oes angulares, mesmo que o modulo do
uxo seja igual. A sugest~ao para este processo, e neste caso, utilizar o algoritmo da FFT ,
para detectar qual dos histogramas apresenta apenas um termo constante.
O conceito da retina din^amicae facilmente aplicavel a imagens cartesianas discretas, ou
a imagens log-polar continuas, no entanto, quando se utilizam imagens log-polar discretas,
a descric~ao apresentada na secc~ao 2.3 n~ao pode ser usada devido a falta de amostras,
quando se pretende mudar o ponto de aplicaca~o da retina. Qual sera ent~ao a soluc~ao? De
modo a evitar efectuar uma amostragem log-polar para cada retina, e neste caso efectuada
a seguinte aproximac~ao: para realizar o histograma s~ao apenas inspeccionadas 8 direcc~oes
angulares (0; 450; 900; ...) da imagem log-polar (usando apenas 4 pontos para cada direcca~o
radial). Para cada direcc~ao inspeccionada, e necessario converter o uxo optico para a
respectiva direcc~ao radial da retina. Tal processo passa-se como se a amostragem logpolar tivesse sido efectuada no local onde se encontra o centro da retina din^amica (isto
apenas e valido, se o numero de amostras angulares da imagem log-polar for elevado). A
Fig. 4.3 exemplica o que foi referido.
~ DO FOCO DE EXPANSAO
~
4.2. ESTIMACAO
77
1.2e−05
"FOEln00.txt"
1e−05
8e−06
6e−06
4e−06
2e−06
0
0
20
40
60
80
100
120
140
160
180
Figura 4.4: Neste exemplo, ~v = [0; 0; 1]T (cm/s) e ~! = 0. A esquerda encontra-se o
resultado da detecc~ao da direcc~ao FOE , e a direita o campo de uxo optico com a linha
FOE , onde o quadrado a preto indica a posic~ao detectada para o FOE . As dist^ancias
focais s~ao fx = fy = 15:0cm=pixel. Neste caso foram utilizadas 180 amostras angulares.
Devido a zona da fovea, que n~ao e transformada para o plano log-polar, e neste caso
bastante difcil detectar a posic~ao do FOE , se este se encontrar nessa zona (e bastante
difcil neste caso usar um esquema de interpolac~ao, para obter informac~ao na zona da
fovea).
Algoritmo do Desvio Padr~ao
Este algoritmo e bastante semelhante ao anterior, no entanto, em vez de usar uma FFT
para detectar a forma do graco dos histogramas, utiliza o desvio padr~ao de modo a
seleccionar qual o histograma que possu um graco constante. O FOE encontra-se
assim no ponto que deu origem ao histograma com um menor valor de desvio padr~ao.
Nas experi^encias realizadas, em geral, e utilizado um metodo de interpolac~ao de modo a
extrapolar o valor da vari^ancia na zona da fovea. No entanto a utilizac~ao da interpolac~ao
normalmente conduz a resultados mais instaveis.
4.2.4 Resultados de simulac~ao
Neste secc~ao, s~ao apresentados os resultados da detecc~ao do FOE , atraves do uso de uxo
optico simulado obtido directamente da equac~ao 2.29. No primeiro exemplo, apenas se
78
~ DE PARAMETROS
^
CAPITULO 4. DETERMINACAO
DO MOVIMENTO
0.006
"FOEln.txt"
0.005
0.004
0.003
0.002
0.001
0
0
20
40
60
80
100
120
140
160
180
Figura 4.5: Neste exemplo, ~v = [1; 1; 1]T e ~! = [0; 0; 0:1]T (graus=s). A direcc~ao F OE
detectada foi de 42o, uma diferenca de 3o, e mesmo na presenca de uma rotac~ao de
elevado valor.
usa uma translaca~o (Fig 4.4), na Fig. 4.5 e efectuada uma rotac~ao em torno do eixo z e
na Fig. 4.6, a detecca~o torna-se mais difcil porque a rotac~ao e no eixo x, e para este caso
o FOE n~ao foi detectado correctamente, porque a restrica~o 4.4 n~ao e vericada (note-se
que se usa aqui uxo optico sem rudo).
4.2.5 Resultados com o sistema experimental
Em geral, a detecca~o do FOE depende da tecnica de detecc~ao do uxo optico. Assim
sendo, uma das chaves para um sucesso na detecc~ao do FOE e a performance da tecnica
de uxo optico utilizada. De modo aos resultados da posic~ao do FOE serem coerentes,
a percentagem de vectores de uxo deve ser elevada, e nas experi^encias realizadas, os
melhores resultados foram obtidos atraves da utilizac~ao do metodo am e am por regi~oes.
Nas Figuras 4.8, 4.9, 4.10, 4.11 e 4.12 apresentam-se os resultados com imagens
sinteticas para os metodos ans, no plano cartesiano e log-polar.
4.2.6 Principais conclus~oes sobre a detecc~ao do foco de expans~ao
Dos algoritmos propostos para detectar a posica~o do FOE , as seguintes conclus~oes podem
ser retiradas:
~ DO FOCO DE EXPANSAO
~
4.2. ESTIMACAO
79
0.0045
"FOEln.txt"
0.004
0.0035
0.003
0.0025
0.002
0.0015
0.001
0.0005
0
0
20
40
60
80
100
120
140
160
180
Figura 4.6: Neste exemplo, ~v = [1; 1; 1]T e ~! = [0:1; 0; 0]T (graus=s). A direcc~ao F OE
detectada foi de 326o, o que e bastante erroneo, no entanto a restrica~o vx :wx = ,vy :wy
n~ao foi vericada.
0.045
0
"FOEln.txt"
"FOE.txt"
−0.1
0.04
−0.2
0.035
−0.3
0.03
−0.4
0.025
−0.5
0.02
−0.6
0.015
−0.7
0.01
−0.8
0.005
−0.9
0
−1
0
20
40
60
80
100
120
140
160
180
0
20
40
60
80
100
120
140
Figura 4.7: Neste exemplo, ~v = [1; 1; 1]T e ~! = [,0:1; 0:1; 0]T . A direcc~ao F OE detectada
foi de 46o, (um erro de 1o), porque a restrica~o vx :wx = ,vy :wy e vericada neste caso.
80
~ DE PARAMETROS
^
CAPITULO 4. DETERMINACAO
DO MOVIMENTO
1
0.4
0.9
data
interpolated
0.2
0.8
0
0.7
−0.2
0.6
0.5
−0.4
0.4
−0.6
0.3
−0.8
0.2
−1
0.1
0
−1.2
0
20
40
60
80
100
120
140
160
180
0
50
100
150
200
250
Figura 4.8: Experi^encia com o modelo am por regi~oes. Neste exemplo, ~v = [1:0; 0; 0:2]T
e !~ = [0; 0:04; 0]T . A direcc~ao F OE detectada foi 10:0o, e o ponto FOE em
(28:852341; 5:087448). Este resultado assume fx = fy = 10:0
a detecc~ao do FOE depende fortemente da estabilidade do algoritmo de uxo optico
usado.
para valores de rotac~ao elevados, apesar de se vericar a restric~ao imposta pela
equac~ao 4.4, a detecc~ao da orientac~ao F OE e bastante instavel.
o algoritmo da linha e o que apresenta resultados menos satisfatorios, porque apenas
usa o uxo da linha FOE .
o algoritmo da FFT n~ao pode ser utilizado no plano log-polar, porque o histograma
apresenta uma resoluc~ao angular baixa.
o algoritmo do desvio padr~ao e de todos, o melhor, n~ao so a nvel da estabilidade,
mas tambem a nvel da interpolaca~o que permite obter o FOE caso ele se encontre
na zona da fovea.
no geral, os algoritmos propostos apresentam melhores resultados quando aplicados
a imagens cartesianas, no entanto o tempo de processamento e mais elevado do que
~ DO FOCO DE EXPANSAO
~
4.2. ESTIMACAO
1.6
81
0.4
data
interpolated
1.4
0.2
1.2
0
1
0.8
−0.2
0.6
−0.4
0.4
−0.6
0.2
0
−0.8
0
20
40
60
80
100
120
140
160
180
0.025
0
50
100
150
200
250
0.06
Log−Polar, data
Log−Polar, interpolated
0.04
0.02
0.02
0.015
−0.02
0
−0.04
0.01
−0.06
−0.08
0.005
−0.1
−0.12
0
0
20
40
60
80
100
120
140
160
180
−0.14
−150
−100
−50
0
50
100
150
Figura 4.9: Experi^encia com o modelo am. O movimento efectuado e id^entico ao
da Fig 4.8. As imagens do topo representam a detecca~o no plano cartesiano. A
direcc~ao FOE detectada foi 350:0o, e o FOE =(54:810425; ,10:335442). As imagens
em baixo referem-se ao caso log-polar, onde a direcc~ao F OE detectada foi 346:0o, e o
FOE =(52:330307; ,14:952591).
82
~ DE PARAMETROS
^
CAPITULO 4. DETERMINACAO
DO MOVIMENTO
0.25
0.15
data
interpolated
interpola
0.1
0.2
0.05
0
0.15
−0.05
−0.1
0.1
−0.15
−0.2
0.05
−0.25
0
−0.3
0
20
40
60
80
100
120
140
160
180
0.0035
0
50
100
150
200
250
0.04
data
interpolated
0.03
0.003
0.02
0.0025
0.01
0.002
0
0.0015
−0.01
−0.02
0.001
−0.03
0.0005
−0.04
0
0
20
40
60
80
100
120
140
160
180
−0.05
−150
−100
−50
0
50
100
150
Figura 4.10: Experi^encia com o modelo am. O movimento efectuado e ~v =
[10:0; 10:0; 4:0]T e ~! = [0; 0; 0]T ,fx = fy = 15:0. O FOE real neste caso encontra-se
em (37:5; 37:5). Na sequ^encia do topo os pontos a branco indicam a posica~o do FOE
detectada. As imagens do centro representam a detecc~ao efectuada sobre imagens cartesianas, onde a direcc~ao FOE detectada foi de 50:0o, e o FOE =(33:318420; 39:707352).
Em baixo encontra-se o resultado para o caso log-polar. A direcc~ao F OE detectada foi
de 34:0o, e o FOE =(14:960556; 10:091019). Neste caso o log-polar n~ao detectou de forma
correcta a posic~ao do FOE .
~ DO FOCO DE EXPANSAO
~
4.2. ESTIMACAO
83
^
Variancia
FFT com 256 amostras angulares
FFT com 256 amostras angulares
FFT com 256 amostras angulares
Figura 4.11: O movimento e ~v = [2:0; ,2:0; 1:0]T , ~! = [0; 0; 0]T ,fx = fy = 10:0. a
posic~ao real do FOE e (20,-20). Os resultados para o plano cartesiano s~ao: algoritmo
da linha (19.292419,-19.977890), algoritmo da FFT (19,-21), algoritmo do desvio padr~ao (18.000000,-19.000000). Usando imagens log-polar obt^em-se: algoritmo da linha
(8.006317,-7.731613), algoritmo do desvio padr~ao sem interpolac~ao (24.000000,-23.000000)
e com interpolaca~o (7.955401,-8.238059).
84
~ DE PARAMETROS
^
CAPITULO 4. DETERMINACAO
DO MOVIMENTO
Variancia
^
Figura 4.12: O algoritmo do desvio padr~ao para o caso do exemplo apresentado na Fig.
4.11
^
4.3. CONTROLO DO ALINHAMENTO DE UMA CAMARA
85
no caso do log-polar, e em geral a precis~ao dos resultados em imagens log-polar e
suciente.
4.3 Controlo do alinhamento de uma c^amara
Nesta secc~ao apresenta-se o algoritmo de alinhamento do sensor visual com o vector de
movimento translacional - detecc~ao da direcca~o preferida de visualizac~ao. Para conseguir
tal comportamento, utilizou-se um dos algoritmos de detecc~ao do FOE proposto na secc~ao
anterior e atraves dum controlador tenta-se manter a posic~ao do FOE no centro das
imagens (Fig. 4.14). O algoritmo de detecc~ao utiliza imagens log-polar e para efectuar
o controlo utilizou-se um sistema de eventos discretos com dois estados, que se encontra
representado na Fig. 4.13. Um dos estados inicia o processo para efectuar a estimativa
das coordenadas X e Y do FOE . O outro estado monitoriza a posic~ao desejada da
c^amara, que foi calculada na malha de realimentaca~o do controlador indicado na Fig.
4.14, utilizando as estimativas de X e Y obtidas no primeiro estado.
O sinal obtido a sada do controlador indica o erro angular relativamente a posica~o
da c^amara. No diagrama 4.14 existem dois sinais de erro X e Y o que poderia levar o
leitor a pensar num sistema de duas entradas duas sadas. No entanto ambos os sinais
s~ao desacoplados, i.e., tudo se passa como se estivesse na presenca de dois sistemas com
uma entrada uma sada. O sinal de erro do X controla o ^angulo de \Pan" da c^amara,
enquanto o sinal de erro do Y o \tilt". Denindo as func~oes de erro como:
erroX [n] = X [n] , Xdesejado
erroY [n] = Y [n] , Ydesejado
(4.15)
o controlador para cada um dos sistemas pode-se ser descrito atraves da seguinte express~ao:
u[n] = kperro[n] + ki
m
X
k=0
erro[n , k] + kd (erro[n] , erro[n , 1])
(4.16)
onde os kp, ki e kd s~ao ajustados experimentalmente e a funca~o erro sera substituda pela
respectiva func~ao em cada caso. As acc~oes do controlador s~ao executadas repartidamente
86
~ DE PARAMETROS
^
CAPITULO 4. DETERMINACAO
DO MOVIMENTO
Modelo para o controlo do alinhamento
α1
α0
0
1
α2
α3
Σ u ={ α 0 , α 1 , α 2 , α 3 }
Descric~ao dos Estados
0: C^amara em repouso e sistema movel em movimento
1: Controlo da c^amara - c^amara e sistema movel em movimento
Descric~ao dos eventos
0: Estima as coordenadas do FOE
1: Estimac~ao do FOE concluda
2: O motor que controla a posic~ao da c^amara ainda n~ao chegou a posica~o nal
indicada pelo controlador
3: O motor que controla a posic~ao da c^amara chegou a posica~o pretendida
e encontra-se parado
Figura 4.13: Modelo do sistema de eventos discreto para o controlo do alinhamento da
c^amara.
por cada um dos estados discretos, i.e., no estado 0 adquirem-se as imagens para estimar o
FOE , enquanto no estado 1 posiciona-se a c^amara na posica~o calculada pelo controlador.
Salienta-se que a posic~ao das c^amaras e controlada por motores de passo.
Na maioria dos casos, o alinhamento da c^amara foi bem sucedido, devido a cena,
altamente texturada e ao movimento entre imagens ser bastante pequeno, o que permite
uma maior estabilidade na detecc~ao do uxo optico. A Fig. 4.15 apresenta um exemplo
da sequ^encia efectuada pela c^amara.
A Fig. 4.16 apresenta os resultados para o alinhamento duma c^amara agora num
ambiente real. Neste caso a c^amara foi alinhada com o vector de translaca~o do robot e
manteve-se bastante estavel como pode ser visto. No entanto para que tal acontecesse,
^
4.3. CONTROLO DO ALINHAMENTO DE UMA CAMARA
+
Desejado{X,Y}
erro{X,Y}
+
87
PID
^
Controlo da camara
-
X,Y
Filtro de
Kalman
Estimador
do FOE
Imagens
Log-Polar
Imagens
Figura 4.14: Controlador utilizado para o controlo do alinhamento da c^amara. Note-se
que algumas acc~oes do controlador s~ao efectuadas no estado 0, enquanto outras no estado
1.
foi necessario colocar desenhos texturados no ch~ao, de modo a existir textura para uma
melhor estimac~ao do uxo optico e consequentemente uma melhor estimativa da posica~o
do FOE .
O controlo subjacente a este processo passa pela tentativa de estabilizar a posica~o do
FOE no centro da imagem. Denindo a func~ao erro como a diferenca das coordenadas
relativamente ao centro da imagem, e utilizando um PID, pode-se assim controlar os
movimentos de \pan" e \tilt" da c^amara. O sistema experimental encontra-se representado na Fig 5.13, onde os espelhos s~ao usados para a navegac~ao e os Pan & Tilt para as
experi^encias de alinhamento da c^amara usando o FOE .
88
~ DE PARAMETROS
^
CAPITULO 4. DETERMINACAO
DO MOVIMENTO
Figura 4.15: Sequ^encia de alinhamento de uma c^amara com o vector de movimento translacional de um robot, na iterac~ao 0, 11, 17, 21, 25, 29, 33, 37, 41, 45, 49 e 53. O ponto a
branco indica a posic~ao do FOE detectado na imagem log-polar que foi depois reconvertido para a imagem cartesiana.
^
4.3. CONTROLO DO ALINHAMENTO DE UMA CAMARA
89
Figura 4.16: Sequ^encia de alinhamento de uma c^amara com o vector de movimento translacional de um robot. O ponto a preto indica a posic~ao do FOE detectado na imagem
log-polar que foi depois reconvertido para a imagem cartesiana.
90
~ DE PARAMETROS
^
CAPITULO 4. DETERMINACAO
DO MOVIMENTO
180
160
140
120
100
80
60
40
20
0
0
20
40
60
80
100
120
140
160
180
0
20
40
60
80
100
120
140
160
180
200
150
100
50
0
−50
−100
−150
−200
Figura 4.17: Em cima encontra-se representada a coordenada x do FOE , enquanto em
baixo temos os comandos em numero de passos enviados para o motor de \Pan" do
sistema. Estes gracos foram obtidos para o exemplo descrito na Fig. 4.16.
^
4.3. CONTROLO DO ALINHAMENTO DE UMA CAMARA
91
160
140
120
100
80
60
40
20
0
0
20
40
60
80
100
120
140
160
180
0
20
40
60
80
100
120
140
160
180
200
150
100
50
0
−50
−100
−150
−200
Figura 4.18: Em cima encontra-se representada a coordenada y do FOE , enquanto em
baixo temos os comandos em numero de passos enviados para o motor de \Tilt" do
sistema. Estes gracos foram obtidos para o exemplo descrito na Fig. 4.16.
92
~ DE PARAMETROS
^
CAPITULO 4. DETERMINACAO
DO MOVIMENTO
Captulo 5
Navegac~ao utilizando vis~ao articial
5.1 Introduc~ao
Neste captulo explora-se a vis~ao por computador para conduzir um robot movel atraves
dos corredores de ligaca~o de salas de um ambiente estruturado, tal como encontramos em
interiores de edifcios. O prototipo tem como objectivo evitar qualquer embate com as
superfcies das paredes do corredor. Para levar a cabo tal tarefa e proposta uma soluc~ao
com base no equilbrio de uxo optico de c^amaras divergentes.
Numa primeira abordagem para solucionar o problema foi utilizado o uxo optico
medido em imagens obtidas por duas c^amaras para controlar a plataforma movel. Cada
uma das c^amaras adquire imagens de uma das paredes. Com base na diferenca dos uxos
calculados em cada uma das imagens, poder-se-a detectar se o robot se encontra mais
afastado ou mais perto duma das paredes. Desta forma, prova-se que e possvel controlar
os movimentos de rotac~ao e translaca~o do robot movel.
Uma extens~ao a esta abordagem e proposta, baseando-se na utilizac~ao das duas
c^amaras, mas agora associando a cada c^amara dois espelhos que permitem simular quatro
c^amaras virtuais (duas c^amaras virtuais por cada c^amara real). Cada um destes espelhos
tem por func~ao fornecer uma imagem da superfcie da mesma parede do corredor. De seguida, atraves de sinais de controlo sintetizados de cada uma das duas imagens da mesma
parede, pode-se estimar de uma forma muito simples um sinal proporcional a orientac~ao
93
94
~ UTILIZANDO VISAO
~ ARTIFICIAL
CAPITULO 5. NAVEGACAO
que a superfcie da parede faz com o robot movel. A unica restric~ao a soluc~ao, advem
do facto da alterac~ao da orientac~ao das paredes do corredor necessitar de manter uma
certa continuidade. Esta imposic~ao tem a ver com o facto das imagens obtidas pelos dois
espelhos terem um deslocamento espacial horizontal. Por este facto, os locais onde se
d~ao as transico~es das paredes com diferentes orientac~oes s~ao os pontos mais delicados,
uma vez que um espelho fornece imagens de uma zona com uma determinada orientaca~o,
enquanto as imagens obtidas pelo outro apresentam outra orientaca~o distinta. Desta forma o sistema desenvolvido e incapaz de navegar em locais onde a orientaca~o das paredes
apresentem descontinuidades muito altas.
Na proxima secc~ao vamos analisar o problema do posicionamento das c^amaras em
relac~ao ao centro dum referencial de locomoc~ao. Para tal e introduzido o conceito de
esfera de imagem virtual, cujo centro coincide com o referencial de locomoc~ao. Pretendese estudar a forma de posicionar c^amaras convencionais na superfcie dessa esfera, de modo
a obter amostras do sinal captado nessa esfera de imagens. Inicialmente o estudo e feito
a nvel de um equador da esfera, utilizando c^amaras divergentes e de seguida estuda-se o
efeito da mudanca do ^angulo de verg^encia das mesmas c^amaras.
Finalmente s~ao descritas as duas abordagens indicadas anteriormente e de seguida s~ao
apresentados os resultados nais.
5.2 Motivac~ao
Como e do conhecimento geral, a utilizac~ao do uxo optico como medida para um controlo
de uma plataforma movel apresenta alguns problemas, na medida em que por exemplo, o
uxo optico induzido pelo movimento do observador tem de ser separado do uxo gerado
por um objecto que se movimenta livremente no meio ambiente. Trata-se aqui de um problema de segmentac~ao (separac~ao de uxos nas imagens). Uma forma ecaz, de resolver
o problema, pode ser obtida atraves de correlac~ao, no entanto este processo envolve um
elevado custo computacional. Na soluc~ao apresentada pressup~oe-se que o universo em que
o observador se movimenta e estatico, sendo o uxo optico gerado atraves do movimento
do observador movel, utilizado como medida para recuperar alguma informac~ao do meio
~
5.2. MOTIVACAO
95
ωz
[Cam. Cima]
[Esfera]
ou
[Cyclop]
ωx
f
X
r
[Cam. Esquerda]
Z
X
Z
[Cam. Direita]
Y
Y
Z
X
Y
Vr
[Cam. Baixo]
Figura 5.1: Modelo para um sistema de navegac~ao num mundo tridimensional.
ambiente.
5.2.1 Sensores de imagens esfericos
Para fundamentar as restantes secc~oes deste captulo, suponha que se pretende controlar
a atitude dum veculo no espaco tridimensional relativamente ao meio ambiente, a medida
que este se movimenta. Considerando o sistema de referenciais representado na Fig. 5.1 e
modelando o sensor visual por uma superfcie esferica com um raio r, apenas e necessario
controlar as tr^es velocidades indicadas na gura (n~ao considerando o grau de liberdade
de \swing" do veculo) para atingir qualquer ponto do espaco. Bom, mas na realidade
n~ao temos um sensor esferico, contudo podemos simular um, caso se utilizem c^amaras
convencionais cujas posic~oes obedecam a geometria do hipotetico sensor esferico. Desta
forma, a pergunta que se p~oe a partida, e quantas c^amaras se devem utilizar e onde se
devem colocar na superfcie esferica para adquirir a informaca~o necessaria ao controlo do
veculo. Segundo [Nelson, R.C., Aloimonos, J. 87] e [F. Bergholm 90], o uxo medido
ao longo da superfcie da esfera que apresenta maior relev^ancia para o efeito, e o uxo
~ UTILIZANDO VISAO
~ ARTIFICIAL
CAPITULO 5. NAVEGACAO
96
’
[Esfera Vista de tras]
[Esfera Vista de Cima]
eixo Y
A
eixo Z
A
ey
ez
P
ex
P
θ
0
Equador horizontal
ex
α
eixo X
0
eixo X
Equador vertical
Figura 5.2: Decomposica~o do vector velocidade ~p_ nos referenciais descritos pelos versores
e~ ; e~ ; e~ . A esquerda, corte da superfcie esferica segundo um plano contendo os eixos x
e y. A direita, corte da superfcie esferica segundo um plano contendo os eixos x e z
x
y
z
medido segundo o equador e perpendicular a direcc~ao de movimento do veculo. Vamos
ent~ao de seguida efectuar a analise do uxo projectado na esfera.
Considere-se uma esfera de raio unitario em movimento com velocidade expressa por
(~v; !~ ) com ~v; !~ 2 <3. Seja d a dist^ancia do ponto central de projecc~ao da esfera a um
p
ponto tridimensional A com vector ~x. Ent~ao d = x2 + y2 + z 2 e a seguinte relac~ao e
valida:
~x_ = ~! ~x + (~v=d) : k ~x k
(5.1)
Verica-se que qualquer ponto P ao longo da linha de projecca~o do ponto A pode ser
descrito atraves de ~p = ~x; > 0 e 2 <, em particular se P pertencer a superfcie da
esfera tem modulo unitario o que implica =k ~x k,1. A velocidade do ponto A projectada
em P e assim dada por:
~p_ = ~! ~p + (~v=d)
(5.2)
Este vector de velocidade ~p_ pode ser decomposto em tr^es componentes descritas em qualquer sistema de coordenadas ortogonal adequado para o efeito. Como neste momento
interessa estudar o comportamento do uxo ao longo do equador horizontal da esfera
(exemplo esquerdo da Fig. 5.2), vamos descrever o vector velocidade segundo um referencial posicionado nesse equador da esfera, onde o versor e~ tem o mesmo sentido da
direcc~ao radial do ponto A considerado (veja-se Fig. 5.1 e 5.2). Desta forma o ponto
x
~
5.2. MOTIVACAO
97
P na superfcie da esfera e correspondente a projecc~ao de A na sua superfcie, pode ser
denido pelas coordenadas (cos (); sin (); 0). Os versores do referencial s~ao dados por
e~ = [, sin (); cos (); 0]T , e~ = [0; 0; 1]T e o versor e~ n~ao tem interesse uma vez que a
velocidade segundo esta direcca~o n~ao pode ser estimada na superfcie da esfera. Assim a
partir de ( 5.2) temos:
y
z
8
<
:
x
e~ :~p_ = !z + cos ()vy =d , sin ()vx =d ! fluxo paralelo ao equador horizontal
e~ :~p_ = !x sin () , !y cos () + vz =d ! fluxo normal ao equador horizontal
y
z
(5.3)
No nosso caso as velocidades da esfera s~ao dadas por ~v = [0; vy ; 0]T ou ~v = [0; vr ; 0]T e
~! = [!x ; 0; !z ]T pelo que as equaco~es anteriores tomam a seguinte forma:
8
<
:
e~ :~p_ = !z + cos ()vy =d ! fluxo paralelo ao equador horizontal
e~ :~p_ = !x sin ()
! fluxo normal ao equador horizontal
(5.4)
y
z
Pelas equac~oes ( 5.4) conclumos que o uxo normal ao equador permite estimar a velocidade angular !x uma vez que o uxo n~ao depende da profundidade d. Outra conclus~ao
importante a tirar e que o uxo paralelo ao equador tem um comportamento sinusoidal
ao longo desse mesmo equador (note-se que e modulado pela profundidade do respectivo
ponto). Tambem e importante salientar que o uxo paralelo ao equador apos a remoca~o
do factor !z , permite estimar sinais inversamente proporcionais a profundidade em cada
ponto visualizado na superfcie da esfera.
O estudo realizado para o equador horizontal pode ser feito para a mesma circunfer^encia contida no plano Y = 0 (exemplo direito da Fig. 5.2, equador vertical) e apos
se efectuar a decomposica~o da velocidade ~p_ segundo as direcc~oes dos versores e~ e e~ , a
partir de ( 5.2) obtemos:
y
8
<
:
e~ :~p_ = !z : cos () , !x : sin () + vy =d ! fluxo normal ao equador vertical
e~ :~p_ = 0
! fluxo paralelo ao equador vertical
z
y
z
(5.5)
Apos toda esta analise, a pergunta que se segue e, como se pode controlar o sistema,
usando as velocidades medidas na superfcie esferica? Bom, ja se referiu anteriormente da
possibilidade da velocidade medida na esfera ser inversamente proporcional a profundida-
~ UTILIZANDO VISAO
~ ARTIFICIAL
CAPITULO 5. NAVEGACAO
98
Primeiro caso
Segundo caso
Eixo Y
Eixo Y
p1
θ
p2
Eixo X
p1
Eixo X
−θ
p2
Figura 5.3: Representac~ao dos pontos relevantes para efectuar o controlo da velocidade
!z .
de, pelo que n~ao sera de estranhar uma possvel comparac~ao entre as velocidades medidas
em diferentes pontos da esfera, desde que se remova o efeito da velocidade de rotac~ao. Por
conseguinte, e perfeitamente natural que se comparem dois pontos laterais divergentes,
de modo a nos permitir controlar as velocidades !z e !x .
No entanto, por simplicidade, para ja considere-se apenas o controlo da velocidade !z .
Analisando a Fig. 5.3, para o primeiro caso, onde o uxo e~ :~p_ paralelo ao equador e
utilizado (equaca~o ( 5.4)), temos:
y
e~ :~p_ 2 + e~ :~p_ 1 = 2!z + vy
y
y
e~ :~p_ 2 , e~ :~p_ 1 = vy
y
y
1
d2
entre os dois pontos
1
d2
, d1 que depende da velocidade !z
1
+ d1 onde e impossvel estimar a diferenca de profundidade
1
Estes resultados a partida indiciam uma depend^encia da velocidade !z , que por sua vez
e prejudicial ao controlo do sistema.
Vericando agora o segundo caso da mesma gura, e utilizando os dois pontos de vista
da mesma posic~ao lateral, obtemos:
e~ :~p_ 2 + e~ :~p_ 1 = 2!z + cos ()vy
y
y
e~ :~p_ 2 , e~ :~p_ 1 = cos ()vy
y
y
1
d2
1
d2
+ d1 - que depende da velocidade !z
1
, d1 , e possvel comparar as profundidades relativas
1
entre os dois pontos, mesmo na presenca das velocidades de rotaca~o !z e !x
~
5.2. MOTIVACAO
99
Destas duas analises, a conclus~ao a retirar e a seguinte: para controlar a velocidade
!z e necessario utilizar quatro c^amaras, duas para cada ponto de vista lateral, caso se
pretenda remover a inu^encia \maleca" da velocidade !z . Note-se que o controlo pode
ser efectuado de forma independente, i.e., obteve-se uma medida proporcional a orientaca~o
da linha denida pelos dois pontos visualizados, com o referencial de locomoca~o.
Quanto ao controlo da velocidade !x apenas s~ao necessarias duas c^amaras posicionadas
da forma representada na Fig. 5.1 atraves de [cam: Cima] e [cam: Baixo], porque o
valor de !x pode ser estimado atraves do uxo obtido nas c^amaras laterais, tal como foi
explicado anteriormente. Convem, no entanto vericar que de facto atraves do uso do uxo
e~ :~p_ normal ao equador vertical dado pela eq. ( 5.5), a diferenca entre o uxo medido nos
pontos de cima e de baixo da esfera permite comparar as profundidades relativas desses
mesmos pontos. Apos efectuar esse calculo temos:
(5.6)
,2!x + vy d1 , d1
2
1
onde !x pode ent~ao ser removido atraves da estimaca~o obtida pelo uxo normal ao equador
horizontal ~ez :~p_ dado pela equac~ao 5.4, onde o termo restante verica de facto tal criterio.
Em resumo, no total s~ao necessarias seis c^amaras, quatro para controlar a velocidade !z
e duas para a velocidade !x .
Note-se no entanto, que se optar-se por medir as velocidades na superfcie da esfera
so no momento em que o sistema se movimenta com velocidade linear, ent~ao apenas e
necessario utilizar quatro c^amaras no total para efectuar o controlo do sistema. Estas
c^amaras devem estar posicionadas como se encontra representado na Fig. 5.1. Com
as c^amaras direita e esquerda o sistema pode controlar a velocidade !z e com as outras
duas a velocidade !x . Contudo apenas com estas quatro c^amaras e impossvel controlar
o sistema, enquanto se efectua movimentos de rotaca~o. Uma das formas de resolver este
problema e atraves do uso de mais duas c^amaras horizontais, tal como foi referido.
Contudo, existe nesta analise simplicaco~es que convem n~ao levar em conta, uma vez
que na realidade n~ao temos a possibilidade de garantir que o centro do sensor esferico
se encontra coincidente com o referencial de locomoca~o. Para isso vamos numa primeira
fase considerar um pequeno deslocamento. De seguida analisa-se mais em pormenor esta
situac~ao.
y
100
~ UTILIZANDO VISAO
~ ARTIFICIAL
CAPITULO 5. NAVEGACAO
xcyclop
ω
p cyclop
v
Mcam
[cyclop]
[cam]
r
Esfera virtual
f
Pos
cyclop
p’cam
Figura 5.4: Pequenas superfcies da esfera virtual de raio r obtidas atraves de sensores
esfericos reduzidos.
Simulac~ao de uma esfera virtual atraves de pequenos sensores esfericos
Dada a impossibilidade referida, podemos tentar construir o sensor esferico atraves do uso
de pequenos sensores esfericos, dado que estes s~ao mais faceis de posicionar. Para simular
o sensor esferico virtual a partir de pequenos sensores esfericos e necessario relacionar as
velocidades medidas em cada um dos sensores.
Considere-se ent~ao um pequeno sensor esferico com raio f representado na Fig. 5.4
e centrado num referencial [cam] que permite simular parte da superfcie esferica de raio
r que neste momento e considerada como um sensor esferico virtual (esfera no referencial
[cyclop]). Comparando as relac~oes entre as velocidades medidas na esfera pequena (de
raio f ) e as medidas na esfera virtual (de raio r) para o mesmo ponto tridimensional,
temos:
_
~p_ cyclop = k ~x~xcyclop k r
(5.7)
cyclop
sendo ~x_ cyclop = !~ ~xcyclop + ~v . Nesta situaca~o vericam-se as seguintes relac~oes:
8
>
>
>
<
>
>
>
:
~ cyclop +cyclop RcamM~ cam
~xcyclop = Pos
k M~ cam k =k ~xcyclop , P~ oscyclop k
~ cyclop +cyclop RcamM~ cam + ~v
~x_ cyclop = ~! Pos
(5.8)
onde cyclopRcam e uma matriz de transformac~ao que representa a orientac~ao relativa dos
referenciais associados a cada uma das esferas. A velocidade do mesmo ponto medida na
~
5.2. MOTIVACAO
101
esfera pequena e:
_
~p_0 cam = M~ cam f
(5.9)
k M~ cam k
Dado que a relac~ao entre M~_ cam e ~x_ cyclop e dada por:
_
cyclopR M
(5.10)
cam ~ cam = ~x_ cyclop
expressando a velocidade p~_0cam em funca~o da velocidade ~x_ cyclop obtem-se:
,1 ~x_ cyclop
f
(5.11)
p~_0cam = cyclop Rcam
k M~ cam k
no entanto, descrevendo esta velocidade no referencial [cyclop], obtem-se nalmente a
relac~ao pretendida:
k ~xcyclop k
f
p~_0 cyclop =cyclop Rcamp~_0cam = p~_ cyclop
(5.12)
~ cyclop k r
k ~xcyclop , Pos
Comparando neste momento as equac~oes ( 5.7) e ( 5.12) as principais diferencas encontramse no factor fr que se pode considerar a partida conhecido, e o factor desconhecido
k
G = k~xcyclopk~xcyclop
,P~ oscyclop k que representa a relac~ao entre a profundidade do ponto tridimensional medida na esfera imaginaria e a profundidade medida na esfera pequena. Contudo
repare-se que estas velocidades s~ao velocidades tridimensionais e portanto nas respectivas
esferas apenas s~ao medidas as velocidades no plano tangente a esfera, o que corresponde
a retirar a componente radial, respectivamente a componente na direcca~o ~pcyclop e p~0cam.
Desta forma as duas velocidade estimadas em cada um dos sensores nunca ser~ao iguais.
Este facto tem a ver com a decomposic~ao da velocidade ser efectuada segundo referenciais
com diferentes orientaco~es, onde n~ao e possvel estimar as componentes radiais das velocidades. Existe ainda o problema da projecca~o na esfera pequena variar com a variac~ao
da profundidade do mesmo ponto. Como e obvio tal situac~ao n~ao se passa no caso da
esfera virtual.
Contudo, estes problemas s~ao facilmente solucionados se os vectores p~0cam e ~pcyclop
k~xcyclop k
cyclop (r , f ) e G =
forem colineares. Nesta situac~ao P~ oscyclop = k~~xxcyclop
k
k~xcyclop k,(r,f) 1 para
k ~xcyclop k >> r.
A ttulo de exemplo, se r = 15cm, f = 25mm e k ~xcyclop k >> 1; 5m este factor sera
G = 12
11 1; 0(90) e na presenca de velocidades baixas pode ser desprezado.
h
i
~ UTILIZANDO VISAO
~ ARTIFICIAL
CAPITULO 5. NAVEGACAO
102
x
plano imagem
ω
ps
v
^k
f
pc
’
eixo optico
Z
[Camera]
esfera
Figura 5.5: Representac~ao das diferencas entre o pequeno sensor esferico e uma c^amara
convencional.
Simulac~ao do sensor esferico atraves de c^amaras convencionais
Como na realidade os pequenos sensores esfericos v~ao ser simulados atraves de c^amaras
convencionais e importante estudar as diferencas entre ambos.
Considerando a representaca~o da Fig. 5.5, a velocidade ~x_ \sentida" no ponto p~s
da esfera e ~p_ s = k~x~x_ k f , mas projectada na esfera apenas se pode estimar a velocidade
~p_ p = ~p_ s , ~p_ s:x^ x^ = k~x~x_ k f , k~x_~x:^xk f x^ onde ( k~x_~x:^xk f x^) e a componente radial. Para o caso
da c^amara, diferenciando a lei de projecc~ao geometrica p~c = ~xf:k^ ~x em ordem a t, pode-se
expressar ~p_ c = ~xf:k^ ~x_ , (~x:fk^) ~x_ :k^ ~x, que infelizmente n~ao coincide com a velocidade ~p_ p
estimada na superfcie da esfera. Contudo se o vector ~x e o versor k^ forem colineares as
duas velocidades s~ao iguais. Desta forma, apenas se pode utilizar a zona da imagem onde
o sensor e tangente a superfcie esferica, porque so nesse situaca~o ambas as velocidades
podem ser aproximadas.
2
5.2.2 Caso especial da utilizac~ao de um sistema de vis~ao activa
Apesar das analises efectuadas anteriormente, n~ao foi considera um situaca~o, que se prende
com o facto das c^amaras n~ao se posicionarem de uma forma tangente ao sensor esferico
virtual. Um dos exemplos que n~ao obedece a essa situaca~o, e um sistema de vis~ao activa.
Portanto e de alguma forma relevante que se efectue um estudo mais detalhado, para esta
possibilidade, dado o facto de no nosso laboratorio existirem equipamentos que obedecem
~
5.2. MOTIVACAO
103
a essas especicac~oes. Note-se que para esta situac~ao, o centro de projecc~ao das c^amaras
n~ao se situa no centro da esfera virtual e as c^amaras n~ao s~ao tangentes a superfcie da
mesma esfera.
Portanto convem agora utilizar o modelo das c^amaras convencionais. Para estimar
a informac~ao medida nas imagens, e necessario determinar o uxo induzido nas imagens
devido ao movimento do veculo. Para isso, admitindo que todas as c^amaras t^em a mesma
dist^ancia focal f , a relac~ao de rotac~ao entre o referencial da c^amara direita e esquerda
relativamente ao referencial [Cyclop] e respectivamente dada por Rri , Rli:
2
3
6
6
6
4
7
7
7
5
0 0 1
Rri = ,1 0 0
0 ,1 0
0 0 ,1
Rli = 1 0 0
0 ,1 0
2
3
6
6
6
4
7
7
7
5
(5.13)
A translac~ao dos referenciais pode ser expressa para a c^amara direita e esquerda respec~ = [r , f; 0; 0]T e OF
~ = [,r + f; 0; 0]T . As velocidades do
tivamente pelos vectores OF
veculo s~ao dadas pelos vectores ~v = [0; vr ; 0]T e !~ = [!x ; 0; !z ]T , pelo que as velocidades
associadas a um ponto tridimensional p~ = [Xi ; Yi; Zi ]T (onde o ndice i indica c^amara
direita ou esquerda quando substitudo respectivamente por i = r, i = l), s~ao neste caso
dadas por (veja-se ap^endice C):
r
l
i
2
6
6
6
4
X_
Y_
Z_
2
3
~
= Rri,1 ,~v , ~! Rri p~ + OF
7
7
7
5
h
r
r
i
r
6
6
6
4
X_
Y_
Z_
3
7
7
7
5
~
= Rli,1 ,~v , ~! Rlip~ + OF
h
l
i
l
l
(5.14)
Substituindo este resultado na equac~ao 2.27 obter-se-ia o uxo induzido em ambas as
imagens, i.e., u_ l (u; v), v_ l (u; v), u_ r (u; v) e v_ r (u; v). Como se pretende comparar as profundidades dos pontos visualizados, convem que esses pontos sejam pontos correspondentes,
logo pertencentes a uma mesma recta perpendicular a ambos os planos imagem. Este
facto signica que os uxos comparados devem ser u_ r (u; v), v_ r (u; v), u_ l (,u; v) e v_ l (,u; v)
(veja-se Fig. 5.6). Somando os respectivos uxos u_ obtem-se:
2
u
Zr ) (r , f ) (5.15)
u_ r (u; v) + u_ l (,u; v) = 2!z fx + f + fx vr (ZZlZ, Zr ) + fx !z (Zl +
Zr Zl
x
r l
!
~ UTILIZANDO VISAO
~ ARTIFICIAL
CAPITULO 5. NAVEGACAO
104
[Cam. Direita]
[Cam. Esquerda]
(u,v)
(-u,v)
X
Z
Z
X
Y
Y
Figura 5.6: Os uxos comparados u_ r (u; v), v_ r (u; v), u_ l (,u; v) e v_ l (,u; v).
1
0.5
0
-0.5
14
-1
12
0
2
10
4
6
8
Zl
6
10
4
12
14
8
Zr
2
0
,Zr . A vantagem
Figura 5.7: Medida da dist^ancia efectuada pelo sistema, neste caso , ZZll+Z
r
desta medida deve-se ao facto de ser independente das velocidades do sistema, contrariamente a apresentada na Fig. 5.8.
~
5.2. MOTIVACAO
105
Subtraindo os uxos u_ obtem-se:
u_ r (u; v) , u_ l (,u; v) = 2 !xfvfx + fx vr (ZZlZ+ Zr ) + fx !z (Zl Z, ZZr ) (r , f )
y
r l
r l
(5.16)
Somando os respectivos uxos v_ obtem-se:
v_ r (u; v) + v_ l (,u; v) = ,2 !xfufy
x
(5.17)
Subtraindo os uxos v_ obtem-se:
v_ r (u; v) , v_ l (,u; v) = 2 !fz uv
x
(5.18)
Dados os resultados apresentados nas equac~oes 5.15, 5.16, 5.17 e 5.18, as seguintes
conclus~oes podem ser tomadas:
as c^amaras devem ter par^ametros fx, fy id^enticos, caso contrario os resultados obti-
dos n~ao permitem tirar as conclus~oes que se seguem, uma vez que as equaco~es 5.15
a 5.18 ir~ao possuir termos que dependem da profundidade em cada pixel.
as equac~oes 5.17 e 5.18 permitem estimar as velocidades de rotaca~o !x e !z , ja que
os termos presentes nas equaco~es n~ao dependem da profundidade, no entanto para
efectuar a estimac~ao e necessario calibrar as c^amaras.
o primeiro termo presente nas equaco~es 5.15, 5.16 representa o efeito das rotac~oes,
e e um factor prejudicial, no entanto pode ser anulado se a estimaca~o de !x e !z for
correcta.
o terceiro termo presente nas equaco~es 5.15, 5.16 e devido as c^amaras n~ao se
encontrarem posicionadas no eixo de rotac~ao, e o seu efeito e tanto maior quanto
maior a dist^ancia ao centro (r , f ). No caso de esta dist^ancia ser nula, o terceiro
termo desaparece.Os termos dependentes da rotaca~o representam uma quantidade
indesejada em ambas as equac~oes.
no caso de se optar por um controlo em que se estimam estas quantidades apenas
na presenca da translac~ao (quando se efectuam rotac~oes com o veculo a medida de
~ UTILIZANDO VISAO
~ ARTIFICIAL
CAPITULO 5. NAVEGACAO
106
0.8
0.6
0.4
0.2
0
-0.2
-0.4
-0.6
-0.8
14
12
2
4
10
6
8
8
Zl
10
6
12
Zr
4
14
2
Figura 5.8: Medida da dist^ancia efectuada pelo sistema, neste caso , ZZll,:ZZrr . Esta medida
e prefervel a representada na Fig. 5.7, devido a zona mais planar em locais onde Zl
e Zr s~ao aproximadamente iguais, e nos outros possu um crescimento exponencial. No
entanto o pequeno sen~ao, e o facto da medida ser proporcional a fx vr .
sinais de erro para o controlo s~ao desprezados), ent~ao dividindo ( 5.15) por ( 5.16)
obtem-se uma estimativa da profundidade independente dos par^ametros das c^amaras
e das velocidades, i.e., estaremos a medir ZZll ,+ZZrr (este resultado e importante, pois
pode ser medido sem ser efectuada nenhuma calibraca~o dos par^ametros intrnsecos
das c^amaras, a menos do seu posicionamento).
Por outro lado, se se utilizar apenas o segundo termo da equac~ao ( 5.15), estaremos
a medir uma quantidade proporcional a ZZll,:ZZrr , no entanto a constante de proporcionalidade depende de fx vr . Esta medida e prefervel se a velocidade vr de translaca~o
for constante, uma vez que a medida pode variar com vr . O facto desta prefer^encia
pode ser constatado atraves das Fig. 5.8 e 5.7. Na eventualidade de se optar por
um controlo deste genero, note-se que o facto das c^amaras n~ao se encontrarem no
centro de rotaca~o e irrelevante, pois o termo associado sera nulo.
Importa referir que as medidas efectuadas apenas contemplam o resultado para um pixel
em cada uma das imagens, pelo que efectuando uma media para todos os pontos das ima-
~
5.2. MOTIVACAO
107
,Zr , obtem-se uma estimativa proporcional a profundidade
gens para o caso da medida ZZll +Z
r
de todos os pontos visualizados
n,1 Zli ,Zri
i=0 Zli +Zri
(5.19)
n
Em termos praticos, apenas os locais onde se encontram as arestas dos objectos apresentam uxo optico normal. Este facto introduz uma restrica~o muito forte caso se pretenda
utilizar o algoritmo de uxo optico normal, uma vez que os \pixels" correspondentes indicados na Fig. 5.6 podem n~ao apresentar uxo devido a aus^encia de arestas nesses mesmos
pontos. Nesta situaca~o sera impossvel de medir correctamente as quantidades indicadas,
uma vez que e necessario utilizar o uxo desses dois pontos. Uma forma de ultrapassar
este facto pode passar pela utilizac~ao do uxo am, ja que desta forma para todos os
\pixels" da imagem e possvel calcular o uxo optico. No entanto a introduc~ao deste
metodo de calculo obriga a restringir o meio ambiente a superfcies planares, n~ao sendo
no entanto crtico, ja que as paredes do corredor podem ser aproximadas por planos.
De seguida vai-se generalizar o estudo do posicionamento das c^amaras. A ideia e
tentar que as restric~oes impostas ate agora ao posicionamento das c^amaras n~ao sejam t~ao
restritivas como as actuais.
P
Simetria entre c^amaras Convergentes e Divergentes
Apos a analise efectuada anteriormente, neste momento e importante generalizar outros
posicionamentos para as c^amaras. Pretende-se assim estudar qual o efeito da variac~ao
do ^angulo de verg^encia das c^amaras, nas equac~oes 5.15, 5.16, 5.17 e 5.18. Para isso
suponhamos que as c^amaras direita e esquerda podem ser posicionadas segundo um a^ngulo
de verg^encia simetrico (rotac~ao do eixo y do referencial das c^amaras), dando origem a um
possvel posicionamento simetrico convergente ou simetrico divergente, conforme indicado
na Fig. 5.9. Da analise efectuada na secc~ao anterior, apenas existe a necessidade de alterar
a equac~ao 5.14, de forma a incluir uma matriz de transformaca~o que representa a rotac~ao
no eixo y, para cada um dos referenciais, ou seja, Mr = Rri Ry (,vrg ) e Ml = RliRy (vrg ),
onde vrg e um a^ngulo de verg^encia, assumido como sendo simetrico para ambas as c^amaras.
Vericou-se anteriormente para vrg = 0, que e um dos casos mais simples, que as
equac~oes 5.15, 5.16, 5.17 e 5.18 dependem claramente das velocidades de rotac~ao
~ UTILIZANDO VISAO
~ ARTIFICIAL
CAPITULO 5. NAVEGACAO
108
[Esfera Vista de Cima]
[Esfera Vista de Cima]
^
Camara
Esquerda
^
Camara
Esquerda
Vrg
^
Camara
Direita
-Vrg
^
Camara
Direita
Figura 5.9: Estudo do posicionamento das c^amaras para o caso convergente/divergente.
A esquerda apresenta-se o caso de vrg = 0 estudado na secc~ao 5.2, enquanto na Fig.
da direita temos o caso de um posicionamento simetrico divergente (vrg 2 [0; 2 [) ou
convergente (vrg 2 [ 2 ; [).
mesmo que as c^amaras se encontrem posicionadas sobre o eixo de rotaca~o, pelo que n~ao
e de esperar que estas se tornem mais simples para o caso de vrg 6= 0. No entanto
analisando as equac~oes apenas na presenca da velocidade de translac~ao e somando os
respectivos uxos u_ obtem-se:
vrg )u] (Zl , Zr )
u_ r (u; v) + u_ l (,u; v) = Vr [cos(vrg )fx +Zlsin(
(5.20)
Zr
Subtraindo os uxos u_ obtem-se:
vrg )u] (Zl + Zr )
(5.21)
u_ r (u; v) , u_ l (,u; v) = Vr [cos(vrg )fx +Zlsin(
Zr
Somando os respectivos uxos v_ obtem-se:
v_ r (u; v) + v_ l (,u; v) = sin(vrg )VrZl vZr(Zl + Zr )
(5.22)
Subtraindo os uxos v_ obtem-se:
(,Zl + Zr )
(5.23)
v_ r (u; v) , v_ l (,u; v) = , sin(vrg )VrZlv Zr
Analisando as equac~oes 5.20, 5.21, 5.22 e 5.23, podemos vericar a seguinte propriedade:
u_ r (u; v) + u_ l (,u; v) = v_ r (u; v) , v_ l (,u; v) = Zl , Zr
(5.24)
u_ r (u; v) , u_ l (,u; v) v_ r (u; v) + v_ l (,u; v) Zl + Zr
~ COM DUAS CAMARAS
^
5.3. NAVEGACAO
109
cujo resultado n~ao depende do ^angulo de verg^encia (esta equac~ao e valida para todos os
pontos a excepc~ao de alguns pontos u da imagem e posico~es de verg^encia que d~ao origem
a uma divis~ao por zero, por exemplo, para o caso de v_ para vrg = 0 ou vrg = , e para o
caso de u_ para u = 0 quando vrg = 2 ou vrg = 32 ). Este resultado e demasiado abrangente
e importante e dele podem ser tiradas as seguintes conclus~oes, se forem excludos os casos
singulares:
na presenca apenas da velocidade de translaca~o, com base no uxo medido em
posic~oes correspondentes de ambas as imagens, pode-se estimar sempre o valor dado
pela eq. 5.24.
a profundidade e medida segundo o eixo optico das c^amaras e o posicionamento
deste depende do ^angulo de verg^encia.
o valor medido e independente da posic~ao de verg^encia das c^amaras, logo estas
podem ser convergentes ou divergentes.
Um outro processo onde pode ser utilizado este mesmo princpio de posicionamento
das c^amaras e o de seguimento de objectos no espaco tridimensional.
A ttulo nal, pode-se utilizar um sistema de vis~ao activa normal para efectuar acco~es
de navegac~ao, apesar de este n~ao vericar na totalidade as restric~oes do sensor esferico
virtual.
5.3 Navegac~ao com duas c^amaras
Com base no descrito anteriormente, o primeiro processo de navegac~ao que foi testado
usa duas c^amaras posicionadas simetricamente relativamente ao eixo de rotaca~o do robot
como indicado na Fig. 5.10. Tomando como base os seguintes factos:
o movimento de rotac~ao do robot deve ser controlado para evitar o choque com as
paredes do corredor
a velocidade de translac~ao do robot pode ser controlada se for desejavel, no entanto
n~ao e um caso crtico
~ UTILIZANDO VISAO
~ ARTIFICIAL
CAPITULO 5. NAVEGACAO
110
^
Camaras
Divergentes
^
Camaras
convergentes
Velocidade 3d
Velocidade 3d
+
-
+
Sinais de fluxo diferentes
Esquerda - , Direita +
Sinais de fluxo diferentes
Esquerda + , Direita -
Sistema deve rodar para a esquerda em ambos os casos
Figura 5.10: A gura mostra um exemplo, onde a plataforma movel deve rodar para a
esquerda, pois o uxo do lado direito e superior em modulo ao do lado esquerdo. Utilizando
a estrategia de posicionamento e de controlo, e indiferente se as c^amaras est~ao numa
posica~o convergente ou divergente.
deniu-se o sinal de \feedback" que controla a velocidade de translac~ao como
Ffeed =
X
p
u_ 2 + v_ 2
(5.25)
Este sinal e o modulo do uxo optico, que fornece informac~ao sobre os objectos texturados que estejam a ser visualizados. Assumindo uma textura homogenea e no caso do
movimento ser elevado, provavelmente existem muitos objectos em linha de vista, pelo
que sera mais cauteloso abrandar a velocidade de translac~ao.
Para efectuar o controlo do movimento de rotaca~o do robot, efectua-se o calculo indicado pela eq. 5.24 para cada pixel. De seguida somando o valor desse calculo para varios
\pixels" obtem-se:
P
Hfeed =
Pk
u_ r (u;v)+u_ l (,u;v)
ku
v
u=,ku v=,kv u_ r (u;v),u_ l (,u;v)
(2 ku + 1) (2 kv + 1)
=
Pk
ku
Zl,Zr
v
u=,ku v=,kv Zl+Zr
(2 ku + 1) (2 kv + 1)
P
(5.26)
Para as experi^encias realizadas para testes neste captulo, o algoritmo de calculo do uxo
optico utilizado e o metodo am. Com base no sinal obtido atraves da eq. 5.26 um
dos algoritmos de controlo da velocidade angular que se pode elaborar para a plataforma
movel encontra-se indicado na Fig. 5.11.
A Fig. 5.12 apresenta o sistema de eventos discretos de modo a permitir controlar a
velocidade de rotaca~o do robot movel. Este sistema discreto e necessario, pois a estimac~ao
~ COM DUAS CAMARAS
^
5.3. NAVEGACAO
111
Sistema adquire sinais
de entrada utilizando as
imagens
Sim
Robot roda para
a esquerda
Sim
Robot roda para
a direita
HFeed > Limiar
~
Nao
HFeed< -Limiar
~
Nao
Robot apenas
efectua movimentos
translacionais
Figura 5.11: Algoritmo de controlo para determinar quando e que a plataforma movel
deve efectuar movimentos de rotaca~o. A velocidade de rotaca~o e estipulada atraves duma
constante proporcional, i.e., !z = !0 + kp (HFeed , Limiar).
112
~ UTILIZANDO VISAO
~ ARTIFICIAL
CAPITULO 5. NAVEGACAO
dos sinais de erro do sistema apenas s~ao efectuadas quando o robot movel apresenta unicamente velocidade de translac~ao. O estado 0 serve para garantir esta condic~ao, enquanto
no estado 1 se executa o plano de controlo. O processamento das imagens e efectuado a
25Hz para ambas as c^amaras e o controlo da plataforma movel a 2Hz durante o estado 0
Denindo a func~ao de erro como:
etrans: = (Ffeeddireita + Ffeedesquerda ) , Fdesejado
(5.27)
pode-se usar um controlo baseado num controlador expresso por:
u[n] = kp e[n] + ki
m
X
k=0
e[n , k] + kd (e[n] , e[n , 1])
(5.28)
onde os par^ametros kp, ki e kd s~ao ajustados experimentalmente.
A sada do controlador e utilizada para comandar a velocidade de translac~ao, a menos
de uma constante obtida atraves de uma calibrac~ao experimental. Esta calibraca~o foi
efectuada para permitir controlar o veculo dentro de certos limites de velocidade. Notese que o sinal u[n] comanda a sada em velocidade do sistema relativamente a um valor
pre-estabelecido, i.e., se u[n] = 0 a sada n~ao sera nula.
Dos teste efectuados com esta conguraca~o nunca se obtiveram resultados praticos
satisfatorios, devido a velocidade de rotac~ao, pelo que se passou a congurac~ao descrita
na proxima secc~ao.
5.4 Navegac~ao com duas c^amaras e espelhos
5.4.1 Espelhos como simuladores de varias c^amaras
A tecnica de navegaca~o baseada em espelhos, usa a congurac~ao indicada na Fig. 5.14.
Associado a cada c^amara existem dois espelhos, que simulam dois pontos de vista aproximadamente do mesmo local. Considerando que as paredes do corredor s~ao planares
(i.e. pequenas dimens~oes da parede podem ser aproximadas por um plano), com base nos
sinais de \feedback" detectados em cada um dos espelhos, obtem-se uma medida que esta
relacionada com o ^angulo de posicionamento do plano em relaca~o ao sistema de medica~o
~ COM DUAS CAMARAS
^
5.4. NAVEGACAO
E ESPELHOS
113
Modelo para o controlo da velocidade angular
α1
α0
0
1
α2
α3
Σ u ={ α 0 , α 1 , α 2 , α 3 }
Descric~ao dos Estados
0: Plataforma movel apenas se movimenta com velocidade translacional
1: Controlo da velocidade angular do robot movel
Descric~ao dos eventos
0: Estima as entidades angulares em causa enquanto o robot apenas efectua
movimentos de translac~ao. Esta estimativa e conrmada atraves da aquisic~ao
de varias amostras do sinal, uma vez que o processamento das imagens
funciona a 25Hz enquanto o controlo da plataforma movel e executado a
cad^encia de 2Hz . O sinal HFeed e obtido atraves da media das varias
amostras efectuadas.
1: Inicia o controlador da velocidade angular do sistema
2: Aguarda um tempo xo pre-estabelecido, Ts
3: Envia a plataforma movel um comando para esta executar apenas
movimentos translacionais
Figura 5.12: Modelo do sistema de eventos discreto para o controlo da posic~ao angular
do robot movel.
114
~ UTILIZANDO VISAO
~ ARTIFICIAL
CAPITULO 5. NAVEGACAO
Figura 5.13: Sistema de navegac~ao experimental com quatro espelhos. Utiliza uma placa
de aquisic~ao com dois processadores digitais de sinal.
(conforme pode ser visto na Fig. 5.15). Esta relaca~o depende do modelo geometrico associado aos espelhos em conjunc~ao com a c^amara, e aos a^ngulos dos espelhos relativamente
a c^amara.
Desta forma e possvel decidir se o robot movel esta ou n~ao em rota de colis~ao com a
parede.
Utilizando a congurac~ao indicada na Fig. 5.14, pode-se vericar que o sistema e
simetrico, pelo que apenas e necessario analisar uma das c^amaras. Considere-se para isso
a Fig. 5.15. Indicando os sinais medidos em cada imagem dos espelhos como:
1. MMRU - uxo optico medido no espelho de proa na imagem da direita
2. MMRD - uxo optico medido no espelho de popa na imagem da direita
3. MMLU - uxo optico medido no espelho de proa na imagem da esquerda
4. MMLD - uxo optico medido no espelho de popa na imagem da esquerda
uma estrategia de controlo para este caso, que pode ser utilizada e a seguinte (apenas
considerando as estimativas da zona direita):
1. Se k MMRU , MMRD k < limiar ENTA~ O efectua movimentos de translac~ao ou
de rotac~ao para a esquerda
~ COM DUAS CAMARAS
^
5.4. NAVEGACAO
E ESPELHOS
115
Congurac~ao do sistema de navegac~ao com espelhos
Velocidade 3D
Velocidade 3D
2 Espelhos
∆x
2 Espelhos
∆x
∆x
∆x
Velocidade 3D
Velocidade 3D
^
Camara
Direita
^
Camara
Esquerda
-
+
Sinal do Fluxo Medido
Figura 5.14: Nesta Fig. para simplicidade de desenho n~ao se representou a c^amara real
atraves do modelo de perspectiva geometrica, apesar de este ser o modelo correcto.
Parede
Parede
Parede
^
1 camara
direita
2 Espelhos
MMRUMedida no espelho
de proa da direita
~ final
Posicao
,
MMRDMedida no espelho
de popa da direita
~
Posicao
Inicial
,
Movimento
em frente
Figura 5.15: Identicac~ao dos sinais medidos nos espelhos associados a c^amara direita do
sistema
116
~ UTILIZANDO VISAO
~ ARTIFICIAL
CAPITULO 5. NAVEGACAO
Sistema adquire sinais
de entrada utilizando as
imagens
~
Nao
HFeedR > Limiar
Sim
HFeed L> Limiar
Sim
PARA O ROBOT
POSSIVEL EMBATE
~
Nao
~
Nao
Sim
HFeed L> Limiar
Robot roda para
a direita
Robot apenas
efectua movimentos
translacionais
Robot roda para
a esquerda
Figura 5.16: Algoritmo de controlo para determinar quando e que a plataforma movel
deve efectuar movimentos de rotac~ao para o caso dos espelhos.
2. Se MMRU , MMRD > limiar ENTA~ O efectua movimentos de rotac~ao para a
esquerda
3. Se MMRU , MMRD < ,limiar ENTA~ O efectua movimentos de rotac~ao: para
a esquerda ou direita (depende das medidas efectuadas nas imagens da c^amara
esquerda do sistema)
Denindo HfeedR = MMRU , MMRD e HfeedL = MMLU , MMLD o algoritmo
global de funcionamento incorporando as estimativas obtidas das quatro imagens pode
ser o descrito atraves do uxograma representado na Fig. 5.16. Salienta-se para o facto
de neste caso a velocidade de rotac~ao ser constante bem como a velocidade translacional.
O algoritmo de controlo apenas decide qual das acc~oes a tomar.
O sistema de eventos discretos e o indicado na Fig. 5.12. No estado 1 e utilizada
a estrategia de controlo indicada anteriormente, enquanto no estado 0 s~ao adquiridos os
sinais de medida necessarios a este metodo de controlo, tal como descrito na Fig. 5.12.
5.5. RESULTADOS SIMULADOS E EXPERIMENTAIS
117
450
"robot6840.txt"
400
350
300
250
200
150
100
50
0
−15
−10
−5
0
5
10
15
20
25
30
35
Figura 5.17: Evoluc~ao da posica~o Y versos X do robot.
O uxo optico e medido de igual modo ao processo sem espelhos, i.e. mede-se a
componente de uxo segundo a horizontal. No entanto, a diferenca neste caso encontra-se
no processo utilizado, i.e. essa componente e medida atraves dum processo de correlaca~o
unidimensional que detecta o deslocamento horizontal entre imagens consecutivas.
5.5 Resultados Simulados e Experimentais
Nesta secc~ao apresentam-se os resultados simulados/praticos dos dois processos. O primeiro processo foi implementado tanto em simulaca~o como numa situaca~o real, no entanto
os resultados com o equipamento existente nunca chegaram a ser sucientemente satisfatorios, pelo que n~ao s~ao aqui apresentados. Quanto ao caso da navegac~ao com quatro
espelhos, n~ao foi efectuada simulaca~o, pelo que apenas se apresentam os resultados obtidos
numa situaca~o real, que demonstram com sucesso o sistema de navegac~ao.
5.5.1 Resultados simulados
Para validar a primeira estrategia, foi desenvolvido um robot movel simulado, com par^ametros
id^enticos ao robot real, com a capacidade de gerar imagens do local onde se encontra posicionado atraves dum programa de \ray tracing" [Povray Team]. O meio ambiente e
118
~ UTILIZANDO VISAO
~ ARTIFICIAL
CAPITULO 5. NAVEGACAO
5
"vr_wr6840.txt"
4
3
2
1
0
−1
−2
−3
−4
−5
0
20
40
60
80
100
120
140
160
180
Figura 5.18: Velocidade angular do Robot para o caso da Fig. 5.17.
programavel, e independente do processo, e neste caso especco foi programado um corredor virtual. O robot movel apenas pode ser controlado em velocidade, e possui um modelo
dum sistema de 1a ordem com uma constante de tempo programavel. A cena visualizada
pode ser alterada pelo utilizador, para isso e necessario alterar o cheiro que descreve a
cena, sem maiores alteraco~es. O simulador foi desenvolvido em sistema Unix, e segue uma
losoa de cliente/servidor. Permite varios utilizadores ligados simultaneamente ate um
maximo de 4 (este valor apenas e limitado pelo poder de calculo da maquina, uma vez que
o programa de \ray tracing" e computacionalmente pesado). Para o cliente utilizar o simulador basta usar uma ligac~ao por \sockets" num determinado porto [FreeBSD Team].
O interface e semelhante ao duma \shell" atraves do uso de comandos pre-denidos.
Nos seguintes exemplos, o robot navega num corredor, onde as paredes interceptam-se
em tri^angulo, num ponto mais a frente do robot (nota: o referencial do robot simulado
e diferente do referencial da Fig. B.1, i.e., esta rodado de 90o no sentido do ponteiro
do relogio, e a orientac~ao do robot e medida relativamente ao eixo dos Y ). O tempo de
amostragem e neste caso de 0:2 segundos, o "setup" inicial e V rgright = 10:0o, V rgleft =
,10:0o e a posic~ao inicial do robot de (X; Y; ) = (0:0; 0:0; ,10:0o), o que levaria o robot
a colidir com a parede, se este segui-se em frente. A Fig. 5.17 mostra a evoluc~ao da
posica~o do robot para o caso do processo de navegac~ao sem espelhos. Na cena de teste,
o ^angulo maximo admitido era neste caso de 45o, caso contrario o sistema era incapaz
5.5. RESULTADOS SIMULADOS E EXPERIMENTAIS
119
Figura 5.19: Imagens de ambas as c^amaras nos seguintes tempos de amostragem: 4, 87,
102 e 180, para o caso de navegac~ao sem espelhos.
~ UTILIZANDO VISAO
~ ARTIFICIAL
CAPITULO 5. NAVEGACAO
120
40
Robot Cmds
MMLU − MMLD
MMRU − MMRD
30
20
10
0
−10
−20
−30
−40
−50
10
20
30
40
50
60
Figura 5.20: Medidas de \feedback" versos os comandos enviados para o robot, Comandos
(0)- frente (-10)- direita (10)- esquerda (tempo = 0.5s), para o processo com espelhos.
de se reorientar correctamente. Na Fig. 5.18 encontram-se as respectivas velocidades
angulares do robot, enquanto na Fig. 5.19 encontram-se representadas algumas das
imagens adquiridas ao longo do processo de navegaca~o.
5.5.2 Resultados experimentais
Nas Figuras 5.20, 5.21, 5.22, 5.23, 5.24 e 5.25 encontram-se representados os resultados
para o caso do algoritmo de navegac~ao com quatro espelhos, para um dos testes efectuado.
As Fig. 5.21 e 5.20 representam os sinais que foram gerados para este processo.
5.5. RESULTADOS SIMULADOS E EXPERIMENTAIS
121
20
MMLU
MMLD
10
0
−10
−20
−30
−40
−50
−60
20
60
40
60
80
100
120
140
160
180
200
MMRU
MMRD
50
40
30
20
10
0
−10
−20
20
40
60
80
100
120
140
160
180
200
Figura 5.21: Medidas dos sinais MMLU/MMLD e MMRU/MMRD respectivamente (tempo de aquisic~ao 0.08s ou seja 12.5Hz), para o caso da navegac~ao com espelhos.
122
~ UTILIZANDO VISAO
~ ARTIFICIAL
CAPITULO 5. NAVEGACAO
Figura 5.22: Navegac~ao com espelhos (1a parte - imagens exteriores)
5.5. RESULTADOS SIMULADOS E EXPERIMENTAIS
Figura 5.23: Navegac~ao com espelhos (2a parte - imagens exteriores)
123
124
~ UTILIZANDO VISAO
~ ARTIFICIAL
CAPITULO 5. NAVEGACAO
Figura 5.24: Navegac~ao com espelhos (1a parte - imagens interiores)
5.5. RESULTADOS SIMULADOS E EXPERIMENTAIS
Figura 5.25: Navegaca~o com espelhos (2a parte - imagens interiores)
125
126
~ UTILIZANDO VISAO
~ ARTIFICIAL
CAPITULO 5. NAVEGACAO
Captulo 6
Conclus~oes e trabalho Futuro
6.1 Conclus~oes
Nesta tese pretendeu-se implementar alguns processos visuais, utilizando tecnicas de vis~ao.
Concretamente o trabalho foi sendo denido a medida que o tempo foi decorrendo, tendo
no entanto como objectivo principal o desenvolvimento de um sistema que fosse capaz
de navegar num corredor. As soluco~es deveriam a partida utilizar uxo optico normal
sobre imagens log-polar. Como e evidente, sabe-se a priori, que o uxo optico normal
e ruidoso, e quando utilizado sobre imagens log-polar os sinais da provenientes tornamse ainda mais difceis de tratar. Estes sinais s~ao dependentes dos par^ametros utilizados
na transformac~ao log-polar, uma vez que esta transformaca~o funciona como um ltro que
deve ser ajustado para uma determinada gama. Devido ao rudo associado ao uxo optico
normal, o sistema nunca chegou a funcionar correctamente atraves desta tecnica.
O passo seguinte passou pela introduca~o do uxo am sobre as imagens log-polar. O
processo de navegac~ao passou a ser mais estavel, devido ao uxo am minimizar globalmente a restric~ao do brilho, captando assim a tend^encia do movimento. O facto do modelo
associado ao uxo am, ser denido para superfcies planares, n~ao e uma restrica~o severa,
uma vez que a aproximaca~o e valida se as c^amaras estiverem a visualizar uma area relativamente grande da parede. Este processo funciona no entanto com algumas restric~oes,
devido ao problema da textura necessitar de ser aproximadamente igual em ambas as
127
128
~ E TRABALHO FUTURO
CAPITULO 6. CONCLUSOES
paredes.
Finalmente, o sistema, que actualmente se encontra desenvolvido, e com resultados
satisfatorios, utiliza uma tecnica baseada em dois espelhos de modo a podermos comparar
n~ao o uxo entre as duas paredes, mas duas quantidades do uxo medido sobre a mesma
parede. Desta forma desacoplamos o problema da textura, e o processo torna-se assim
estavel. E verdade, que cam ainda alguns problemas por resolver, nomeadamente o
problema da velocidade, isto porque a data o sistema tem diculdades em navegar a uma
velocidade superior a que consegue actualmente (230mm/s). Outros problemas que se
podem apontar a esta tecnica, t^em a ver com a quest~ao da continuidade das inclinac~oes
da parede (n~ao funciona com ^angulos rectos), e com o a^ngulo inicial com que o sistema
inicia o processo, que n~ao pode ser superior a uma inclinac~ao de 35o.
Quanto a detecc~ao do FOE e realinhamento da c^amara de acordo com o vector de
velocidade de translaca~o do robot, ja foram previamente apresentadas as respectivas conclus~oes, no entanto apenas seria importante de referir, que apesar de funcionalmente o
processo apresentar um bom desempenho, a sua utilizac~ao num sistema pratico tem pouca
ou nenhuma utilidade. Isto porque a partida, ao se iniciar o movimento do robot, sabe-se
quais s~ao os par^ametros do movimento, pelo que o FOE n~ao vem apresentar nenhuma
informac~ao valiosa ao processo. Uma das aplicac~oes, em que talvez possa vir a ser util,
seria a de estabilizar a imagem relativamente a pequenos \micro-movimentos" da c^amara,
devido aos movimentos mais bruscos do robot, no entanto, para efectuar esta tarefa, era
necessaria uma elevada precis~ao no calculo do FOE , o que esta longe de ser o caso ( o
processo actual apresenta em media erros de 10%). No entanto n~ao deixa de ser uma
aplicac~ao interessante, como mostram as mais recentes c^amaras de lmagens aereas (a
estabilizaca~o n~ao e como e obvio feita por imagens, mas por inclinometros).
Em conclus~ao:
a resoluca~o das imagens log-polares e inferior a resoluc~ao das imagens cartesianas,
permitindo assim ganhar tempo para efectuar mais calculos, no entanto a que ter
em conta, o processo de transformaca~o, pois em termos praticos, a transformaca~o
requer tabelas, o que do ponto de vista computacional signica um maior numero
de acessos a memoria,
6.2. TRABALHO FUTURO
129
o processo visual de navegaca~o com uxo optico normal revelou-se instavel, devido
aos erros associados ao uxo normal,
a navegaca~o com os espelhos e estavel, no entanto, como tudo, pode ainda ser
bastante melhorada,
a detecc~ao do FOE ainda n~ao e sucientemente precisa para poder ser utilizada na
resoluc~ao de problemas mais praticos e de maior utilidade,
quanto as tecnicas de detecc~ao do uxo optico, pessoalmente, acho que enquanto
n~ao for resolvido o problema da estabilidade, isto e, ter a certeza que o pixel (u; v) se
movimentou mesmo de uma velocidade (vu ; vv ), tudo pode acontecer, e pessoalmente
sou mais a favor de uxo baseado em tecnicas de correlac~ao, do que tecnicas baseadas
na restric~ao do brilho.
6.2 Trabalho futuro
Relativamente a trabalho a desenvolver futuramente, no caso da navegaca~o autonoma,
gostaria primeiro de salientar, que normalmente um ser humano quando se desloca num
meio ambiente, utiliza como refer^encias pontos de interesse - \landmarks" -, sons, etc.
Como o que nos interessa, e a utilizaca~o da vis~ao, para efectuar navegaca~o, se decidirmos
enveredar por este caminho, o problema, neste caso, consiste em saber como s~ao seleccionadas essas \landmarks". E evidente, que na escolha das \landmarks" reside a chave
do problema, uma vez que seleccionada uma \landmark", pode-se impor como objectivo, chegar o mais perto possvel, ou manter uma dist^ancia constante, etc. A vantagem
deste processo, advem do facto de a nvel do processo visual, poder ser resolvido com
correladores, o que e um processo bem mais estavel do que o uxo optico, se bem que
mais dispendioso computacionalmente, e aqui sim, as imagens log-polar podem desempenhar um papel preponderante, conforme ja foi provado por trabalhos desenvolvidos por
[G. Sandini e C. Capurro 95]. Dos varios problemas que esta losoa possa apresentar,
um esta relacionado com a estimaca~o da dist^ancia da base movel a \landmark". As pessoas que ja trabalharam em \tracking", das quais eu faco parte, sabem perfeitamente, que
130
~ E TRABALHO FUTURO
CAPITULO 6. CONCLUSOES
e necessario uma elevada precis~ao a nvel do posicionamento dos motores de verg^encia, e
de pan do sistema que tenta efectuar o tracking. Um outro factor crtico, encontra-se a
nvel da sincronizac~ao de processos, tais como, ler a posica~o do "encoder" o mais proximo
possvel do momento de aquisic~ao da imagem, uma boa calibrac~ao, etc. O engracado, e
que relativamente a estimac~ao da dist^ancia a \landmark", esta poder ser dada apenas por
uma c^amara onde o zoom seja controlado de modo a manter constantes as dimens~oes do
padr~ao na imagem. Desta forma a dist^ancia a \landmark" seria dada em funca~o da posic~ao do motor de zoom da c^amara, eliminando assim os problemas inerentes a utilizac~ao
da triangulac~ao a quando da utilizac~ao das duas c^amaras. Existem como e evidente,
problemas a nvel do tracking da \landmark", que t^em a ver com o ponto de vista da
c^amara relativamente a \landmark". Quanto ao processo de escolha da \landmark", e
algo que a nvel computacional e \transcendental", pois requer intelig^encia por parte da
maquina (la chegaremos, mas talvez infelizmente, n~ao na minha gerac~ao). No entanto,
uma das possibilidades para a selecc~ao das \landmarks", pode passar pela simulac~ao de
dois ouvidos, de modo a implementar processos de sacada activados sonoramente. Este
pode ser de facto um caminho a seguir, integrar processos auditivos em conjunca~o com
processos visuais, uma vez que no caso dos seres humanos, podemos vericar que eles se
encontram estritamente relacionados.
Ap^endice A
Denico~es e convenc~oes
Neste trabalho s~ao usadas as seguintes notac~oes:
(u; v) - refer^encia a coordenadas cartesianas
(u;_ v_ ) - refer^encia ao uxo optico no plano cartesiano
(; ) - refer^encia a coordenadas polares
(;_ _) - refer^encia ao uxo optico no plano polar (ou plano retinal)
(; ) - refer^encia a coordenadas log-polares (num domnio contnuo)
(;_ _) - refer^encia ao uxo optico no plano log-polar (por vezes designado plano cortical)
(; ) - refer^encia a coordenadas log-polares (num domnio discreto)
(;_ _ ) - refer^encia ao uxo optico no plano log-polar (por vezes designado plano cortical)
f - dist^ancia focal da c^amara
su - factor de escala na direcc~ao u do plano cartesiano
sv - factor de escala na direcc~ao v do plano cartesiano
fx = f:su - dist^ancia focal na direcca~o do eixo u do plano cartesiano
fy = f:sv - dist^ancia focal na direcca~o do eixo v do plano cartesiano
[X; Y; Z ] - coordenadas tridimensionais no referencial c^amara
131
~ E CONVENCOES
~
APE^NDICE A. DEFINICOES
132
p
i - numero imaginario (i = ,1)
Ap^endice B
O Sistema do Robot Movel
O robot movel utilizado no trabalho e designado por ROBUTER [Robuter 92]. Os movimentos executados pela plataforma movel adv^em de dois motores DC associados a cada
uma das rodas motoras. Os movimentos permitidos por esta conguraca~o encontram-se
representados na Fig. B.1. O controlo dos motores e efectuado atraves dum sistema
de multiprocessamento baseado no processador 68020, instalado na plataforma movel. A
unica responsabilidade do PC que controla o robot, e a de enviar os par^ametros do movimento que se pretende executado. Os movimentos representados na Fig. B.1 podem
ser divididos em tr^es grupos: translacional (sem velocidade angular), rotac~ao em torno
do centro do eixo central representado na g. pelo ponto RC (sem velocidade linear),
e movimentos compostos. Para denir um dos tr^es movimentos descritos, alem de ser
necessario indicar a velocidade angular e linear, e tambem necessario indicar a durac~ao
do movimento.
Tipo de
Velocidade Linear Velocidade Angular Trajectoria Tempo de durac~ao
Movimento
(mm/s)
(mrad/s)
Raio
(unidades de 40ms)
translacional 1000; :::; 50; 0
0
0
>0
rotacional
0
1000; ::: 100; 0
0
>0
composto 1000; :::; 50; 0 1000; ::: 100; 0 > 400mm
>0
Tabela B.1: Par^ametros para controlar a velocidade da plataforma movel
133
APE^NDICE B. O SISTEMA DO ROBOT MOVEL
134
v>0
w=0
v>0
w>0
v>0
w<0
X
Y
RC
v<0
w<0
v<0
w=0
v<0
w>0
Figura B.1: Movimentos possveis de serem executados pela plataforma movel. w e a
velocidade angular, v e a velocidade linear, r e o raio da trajectoria e o ^angulo de
orientac~ao.
Os valores validos para as velocidades e duraca~o do movimento dependem do tipo de
movimento a executar, e s~ao representados na tabela B.1. Se o movimento e do tipo
composto, o raio e o arco da trajectoria podem ser obtidos atraves das seguintes relac~oes
(T designa o tempo disponvel para executar o movimento):
mm=s] 103
(B.1)
r[mm] = wv[[mrad=s
]
]
[mrad] = w[mrad=s
(B.2)
T [s]
Os movimentos descritos ate esta altura, s~ao baseados num controlo em velocidade, e
podem ser substitudos ou parados a qualquer momento por outro movimento com outros
par^ametros. A transic~ao entre os movimentos e controlada pelo sistema de multiprocessamento, assegurando um movimento global suave do robot.
As seguintes linhas s~ao exemplos de comandos que podem ser enviados a plataforma
movel, permitindo executar um controlo em velocidade:
135
Figura B.2: O sistema de navegac~ao autonomo com o sistema de vis~ao activa, para desenvolvimento de tarefas baseadas em informaca~o visual.
1. usando um movimento composto: "MOTV LA V=100 W=100 T=50";
2. usando um movimento de rotaca~o pura: "MOTV LA V=0 W=100 T=50";
3. usando um movimento linear: "MOTV LA V=100 T=50".
Outro tipo de movimentos possveis, s~ao os baseados no controlo da posic~ao da plataforma movel. Neste caso, os par^ametros especicados, denem a dist^ancia que cada uma
das rodas motrizes devem percorrer, e o tempo em que elas devem executar essa tarefa
(em unidades de 40ms)
O proximo comando exemplica uma das formas deste controlo posicional, executando
neste caso um movimento de rotaca~o em torno do ponto RC :
1. "MOVE P RC=-200,200 P=100".
Na Fig B.2 encontra-se representado o sistema fsico.
136
APE^NDICE B. O SISTEMA DO ROBOT MOVEL
Ap^endice C
Cinematica dos sistemas autonomos
utilizados
Nesta secc~ao, e desenvolvida a cinematica de posica~o/velocidade directa/inversa, para
determinar a posic~ao e orientaca~o dum sistema de vis~ao activa montado num robot movel.
O objectivo principal, e a obtenc~ao das express~oes do uxo induzido a nvel das imagens
de uma c^amara sob a inu^encia dos movimentos dos graus de liberdade disponveis.
C.1 Introduc~ao
Em termos de analise da cinematica, pode-se considerar o robot como sendo constitudo
por corpos rgidos ligados entre si (a esta ligaca~o tambem se chama de junta ou junc~ao),
que possuem capacidade de se movimentarem. Para descrever as relac~oes de translaca~o e
rotac~ao entre ligaco~es adjacentes, Denavit, e Hartenberg (DH), propuseram um metodo
que automaticamente estabelece a matriz de relac~ao entre dois referenciais duma cadeia
de referenciais [K.S.Fu 87]. Para um maior esclarecimento do que se segue, suponha-se
que se possui n +1 referenciais, numerados de 0 a n, e represente-se um referencial generico
como o i-esimo referencial.
137
138
APE^NDICE C. CINEMATICA
DOS SISTEMAS AUTONOMOS
UTILIZADOS
C.1.1 Transformac~oes entre referenciais
Com este metodo, cada sistema de coordenadas pode ser estabelecido e determinado
atraves de tr^es regras basicas:
1. O eixo Zi,1 pertence ao eixo de movimento da i-esima junc~ao.
2. O eixo Xi e normal ao eixo Zi,1, e o seu sentido aponta do eixo Zi,1, para fora.
3. O eixo Yi completa o referencial atraves da regra da m~ao direita.
A representac~ao de DH dos referenciais associados aos corpos rgidos, dependem de
quatro par^ametros associados a cada junta. Estes quatro par^ametros descrevem completamente cada junta, seja ela prismatica (translaciona na direcc~ao do eixo Z ) ou de
revoluc~ao (apenas roda em torno do eixo Z ), e s~ao denidos da seguinte forma:
1. i e o ^angulo da junc~ao do eixo Xi,1 para o eixo Xi , medido a partir do eixo Zi,1
(utilizando a regra da m~ao direita).
2. di e a dist^ancia medida da origem do (i , 1)-esimo sistema de coordenadas ao longo
do eixo Zi,1, ate a intercepc~ao dos eixos Zi,1 e Xi .
3. ai e a dist^ancia desde o ponto de intercepc~ao dos eixos Zi,1 e Xi ate a origem do
i-esimo referencial medida ao longo do eixo Xi (ou a dist^ancia mais curta entre os
eixos Zi,1 e Zi).
4. i e o ^angulo medido do eixo Zi,1, para o eixo Zi em torno do eixo Xi (usando a
regra da m~ao direita).
A partir do momento, em que cada referencial se encontra estabelecido, obedecendo
as regras do metodo DH, pode-se usar a matriz homogenea de transformac~ao entre dois
referenciais consecutivos, por exemplo, o i-esimo e o (i-1)-esimo referencial. A matriz que
relaciona os dois referenciais e dada por:
~
C.1. INTRODUCAO
139
cos i , cos i sin i sin i sin i ai cos i
i,1A = sin i cos i cos i , sin i cos i ai sin i
(C.1)
i
0
sin i
cos i
di
0
0
0
1
onde i , ai , di s~ao constantes, enquanto i e uma variavel associada as junc~oes de revoluc~ao.
No caso da junc~ao ser prismatica, a variavel da junca~o e di, enquanto i , ai e i s~ao
constantes.
A transformac~ao inversa pode ser calculada atraves de:
cos i
sin i
0
,ai
i A = , cos i sin i cos i cos i sin i ,di sin i
(C.2)
i,1
sin i sin i , sin i cos i cos i ,di cos i
0
0
0
1
A relaca~o entre o referencial nal, e o primeiro referencial, pode assim ser dada atraves
da relac~ao da matriz de cinematica directa:
2
3
6
6
6
6
6
6
4
7
7
7
7
7
7
5
2
3
6
6
6
6
6
6
4
7
7
7
7
7
7
5
n
=0 A1:1 A2: : : : :n,1An
(C.3)
nA
0
=n An,1: : : : :2A1:1 A0
(C.4)
0A
e para a transformaca~o inversa:
C.1.2 Relac~oes de velocidade
Nesta secca~o e apresentada a forma de relacionar as velocidades associadas a cada referencial, de modo a poder calcular a velocidade num determinado ponto dum referencial.
Aproximac~ao geometrica
Na representaca~o de DH, a matriz que relaciona os referenciais 0-esimo e i-esimo, pode
ser escrita da seguinte forma:
0Ri 0di
0A =
(C.5)
i
0 1
2
3
4
5
140
APE^NDICE C. CINEMATICA
DOS SISTEMAS AUTONOMOS
UTILIZADOS
onde 0 di representa a relac~ao de deslocamento do referencial i-esimo, e 0 Ri representa a
sua orientaca~o.
A aproximac~ao geometrica, e baseada no produto vectorial (veja-se a secc~ao C.4), i.e.,
se um corpo associado com um referencial, se movimenta com uma velocidade angular
~!i e uma velocidade linear ~vi , um ponto P~i = [X; Y; Z ]T , no i-esimo referencial tera uma
velocidade
P~_ i = ~!i P~i + ~vi
(C.6)
esta velocidade pode ser expressa no 0-esimo referencial atraves da matriz de orientaca~o
0Ri:
P~_ 0 =0 Ri:P~_ i =0 Ri: ~!i P~i + ~vi
(C.7)
contudo, notando que no caso em que R e uma matriz ortogonal, verica-se a seguinte
relac~ao,
R ~a ~b = (R:~a) R:~b ;
(C.8)
e porque, na representaca~o de DH, a rotaca~o e efectuada em torno do eixo Zi, e a translaca~o
tambem e segundo a direcc~ao do eixo Zi, a velocidade P~i pode ser expressa no 0-esimo
referencial como:
P~_ =k ~! k : 0R : [0; 0; 1]T 0 R :P + k ~v k 0R : [0; 0; 1]T
(C.9)
0
i
i
i i
i
i
mas 0Ri [0; 0; 1]T representa o eixo Zi no 0-esimo referencial, e 0Ri :Pi pode ser expresso
como 0 Ai:[PiT ; 1]T ,0 di .
No caso de um ponto generico pertencente ao n-esimo referencial, a inu^encia das
velocidades associadas ao i-esimo referencial na velocidade do ponto generico e dada por
(expressa no 0-esimo referencial):
P~_ =k !~ k : Z 0A :[P T ; 1]T ,0 d + k ~v k Z
(C.10)
0
i
i
n
i
n
i
esta relac~ao torna-se mais simples se o ponto P for [0; 0; 0]T ,
P~_ 0 =k ~!i k : Zi 0 dn ,0 di + k ~vi k Zi
i
(C.11)
Pode tambem ser necessario saber a velocidade angular resultante, devido as varias
velocidades angulares associadas aos referenciais. As velocidades angulares podem ser
~
C.1. INTRODUCAO
141
somadas se forem expressas relativamente ao mesmo referencial. Descrevendo todas as
velocidades no 0-esimo referencial e denindo a sua soma como !0all , ent~ao teremos:
!~ 0all = ~!0 +0 R1:~!1 + : : : +0 Rn:~!n
(C.12)
mas como estamos a usar a representaca~o DH, esta relaca~o pode ser descrita por
!~ 0all = ~!0 + Z1 k ~!1 k + : : : + Zn k ~!n k
(C.13)
tal como para a velocidade linear ~vi .
Suponha-se agora, que se pretende saber a velocidade linear ~v e a velocidade angular ~!
de qualquer ponto do n-esimo referencial, relativamente ao 0-esimo referencial em func~ao
das velocidades angulares de cada referencial. Basta para isso somar as velocidades lineares e angulares, descritas todas num mesmo referencial, por exemplo, o 0-esimo referencial
(0~!i ;0 ~vi ). Se a i-esima junta e de revoluca~o, ent~ao a sua inu^encia e dada por
2
2
Ji =
4
3
0~vi
4
5
0~!i = Ji:!i
Zi 0An:[PnT ; 1]T
Zi
se a junta for prismatica ent~ao:
2
4
0~vi
0 ~!i
,0 di
3
(C.14)
5
3
5
= Ji :vi
(C.15)
Zi
Ji =
0
Adicionando todas as inu^encias e denotando qi como !i ou vi se a junta for de
revoluc~ao ou prismatica respectivamente, ent~ao
q0
~v
= J: ...
(C.16)
~!
qi
onde J e a matriz jacobiana, dada por:
2
3
4
5
h
2
3
4
5
2
3
6
6
6
4
7
7
7
5
J = J0 : : : Jn
i
(C.17)
142
APE^NDICE C. CINEMATICA
DOS SISTEMAS AUTONOMOS
UTILIZADOS
Aproximac~ao analtica
As relac~oes de velocidade, podem ser obtidas analiticamente, atraves da denica~o da
_ Y_ ; Z_ de qualquer ponto, referenciado a um referencial,
derivada, i.e., pode-se estimar X;
se se souber o incremento innitesimal na posic~ao desse ponto. Em termos matematicos,
denindo as func~oes:
P~n(t = 0) = [X; Y; Z; 1];
P~0 (t = 0) =0 An (0; : : : ; i ; d0; : : : ; dj ):P~n (t = 0)
P~0 (t = 4t) =0 An (0 + 4t!0; : : : ; i + 4t!i; d0 + 4tv0; : : : ; dj + 4tvj ):P~n (t = 0)
(C.18)
apenas e necessario usar a denic~ao da derivada para calcular a velocidade:
P~0 (t = 4t) , P~0(t = 0)
P~_ 0 (t = 0) = 4lim
t!0
4t
(C.19)
A velocidade angular poderia tambem ser calculada, e o resultado nal e id^entico ao
expresso em C.13.
C.2 Cinematica (directa e inversa)
Nesta secc~ao, apresenta-se dois exemplos, de acordo com os sistemas usados no desenvolvimento dos trabalhos apresentados nesta tese. Relembrando as regras explicadas na
secc~ao C.1.1, a representac~ao de DH, enquanto sistematica, permite ainda assim algum
grau de liberdade na escolha de alguns par^ametros.
C.2.1 Caso do sistema de vis~ao activa
A primeira congurac~ao usa um sistema de vis~ao activa, num robot movel. Os referenciais
encontram-se representados na Fig. C.1. O Robot movel pode efectuar movimentos de
translac~ao e rotac~ao com as respectivas velocidades vr e !r . O sistema de vis~ao activa
possu quatro graus de liberdade, i.e., Pan, Tilt e verg^encia com velocidades angulares
respectivas !n , !t e !cr e !cl .
C.2. CINEMATICA
(DIRECTA E INVERSA)
143
Z
X
Y
d=0
Z
X
Z
Wcl
Y
Y
X
d=0
Dc
X
Y
Z
Dc
Wcr
Z
Y
Ab
X
Y
Z
X
Z
Y
Wt
X
At
Dn
Z
Ac
Wn
Z
Y
Y
Wr
X
Vr
X
Figura C.1: Referenciais do sistema de vis~ao activa e do robot movel, de acordo com a
representac~ao de DH.
144
APE^NDICE C. CINEMATICA
DOS SISTEMAS AUTONOMOS
UTILIZADOS
Os par^ametros do metodo de Denavit e Hartenberg para a c^amara da esquerda s~ao
assim dados por (desde os referenciais de baixo para os de cima):
2
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
4
0
0
Ac 0 0 !r
0
0
0 0 0 0
0
0
0 Dn 0 0
0
90o At 0 n !n
90o
0
0 Ab t !t
, 90o ,90o ,Dc 0 0 0
, 90o ,90o 0 0 cl !cl
0
Vr
0
0
0
0
0
3
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
5
(C.20)
onde as colunas representam respectivamente:
1. i
2. i
3. ai
4. di
5. variavel da posica~o angular (relacionada com o (i , 1)-esimo ref.)
6. variavel da velocidade angular (relacionada com o (i , 1)-esimo ref.)
7. variavel da velocidade translacional (relacionada com o (i , 1)-esimo ref.)
e para a c^amara da direita:
2
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
4
0
0
0
0
0
0
0
90o
90o
0
o
, 90 ,90o
, 90o ,90o
Ac
0
0
At
0
Dc
0
0 0 !r
0 0 0
Dn 0 0
0 n !n
Ab t !t
0 0 0
0 cr !cr
0
Vr
0
0
0
0
0
3
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
5
(C.21)
C.2. CINEMATICA
(DIRECTA E INVERSA)
145
As matrizes para os referenciais da c^amara da direita s~ao dados neste caso por:
2
1
0A = 0
1
0
0
6
6
6
6
6
6
4
2
1
1A = 0
2
0
0
6
6
6
6
6
6
4
2
cos(n )
2 A = sin(n )
3
0
0
6
6
6
6
6
6
4
0
1
0
0
0
0
1
0
0
0
Ac
1
3
0
1
0
0
0
0
1
0
Dn
0
0
1
3
7
7
7
7
7
7
5
(C.22)
7
7
7
7
7
7
5
(C.23)
0 sin(n )
0 , cos(n )
1
0
0
0
0
0
At
1
3
7
7
7
7
7
7
5
, sin(t ) , cos(t ) 0 ,Ab sin(t )
cos(Tt ) , sin(Tt ) 0 Ab cos(t )
3A =
4
(C.24)
2
3
6
6
6
6
6
6
4
7
7
7
7
7
7
5
0
0
0
0
2
4A
5
2
5A
6=
6
6
6
6
6
6
4
=
6
6
6
6
6
6
4
0
1
0
0
,1 0
0 ,1
0 0
sin(cr )
, cos(cr )
0
0
1
0
0
0
0
1
0
0
Dc
1
(C.25)
3
7
7
7
7
7
7
5
0 cos(cr )
0 sin(cr )
,1 0
0
0
(C.26)
0
0
0
1
3
7
7
7
7
7
7
5
(C.27)
146
APE^NDICE C. CINEMATICA
DOS SISTEMAS AUTONOMOS
UTILIZADOS
Cinematica directa
Usando a propriedade C.3 pode-se encontrar a seguinte relac~ao (com C = cos e S = sin):
2
6
6
4
C(n)C(t)S(cr) + S(n)C(cr) C(n)S(t) C(n)C(t)C(cr) , S(n)S(cr) S(n)Dc , C(n)Ab S(t) + Dn
S(n)C(t)S(cr) , C(n)C(cr) S(n)S(t) S(n)C(t)C(cr) + C(n)S(cr) ,C(n)Dc , S(n)Ab S(t)
S(t)S(cr)
,C(t)
S(t)C(cr)
Ab C(t) + At + Ac
0
0
0
1
(C.28)
3
7
7
5
Cinematica inversa
Usando a propriedade C.4 conclui-se que:
6A
h
0
0 = A6
i
,1
(C.29)
Relac~oes de velocidade
Para este exemplo, n~ao de apresenta o resultado, devido a matriz jacobiana possuir demasiados elementos. No entanto, tal como explicado na secc~ao C.3, tanto o metodo
geometrico como o metodo analtico d~ao o mesmo resultado. Os resultados podem ser vericados atraves do programa listado na pagina de Web http://www.isr.uc.pt/~sousa/ftp.html.
C.2.2 Caso dos Pan & Tilt
A segunda congurac~ao, usa duas unidades de Pan&Tilt, com um robot movel. Os
referenciais encontram-se representados na Fig. C.1. O Robot movel pode efectuar
movimentos de translac~ao e rotac~ao com as respectivas velocidades vr e !r . Cada unidade
de Pan&Tilt possu dois graus de liberdade, i.e., Pan, Tilt com velocidades angulares
respectivas !pr , !tr ou !pl , !tl .
Os par^ametros do metodo de Denavit e Hartenberg para a c^amara da esquerda s~ao
C.2. CINEMATICA
(DIRECTA E INVERSA)
147
Z
X
Y
d=0
X
Z
X
Y
Y
Z
Ai
d=0
Y
X
Y
X
Z
Z
Wtl
Ai
Y
At
Z
Wpl
X
Z
Y
Wtr
Dc
Y
At
X
Z
Wpr
Z
X
Dc
Z
Y
Y
Ap
X
X
Dn
Z
Ac
Y
Z
Y
Wr
X
Vr
X
Figura C.2: Referenciais dos Pan&Tilt e do robot movel, de acordo com a representac~ao
de DH.
148
APE^NDICE C. CINEMATICA
DOS SISTEMAS AUTONOMOS
UTILIZADOS
assim dados por (desde os referenciais de baixo para os de cima):
2
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
4
0
0
0
0
0
0
90
90
0
0
0
90
,90
90
90
0
Ac
0
0
Ap
,Dc
At
0
0
0 !r
0 0
0 0
0 0
0 0
pl !pl
tl !tl
0 0
0
Vr
0
0
0
0
0
0
0
0
0
0
0
0
90
90
0
0
0
90
,90
90
90
0
Ac 0 0 !r
0 0 0 0
0 Dn 0 0
Ap 0 0 0
Dc 0 0 0
At 0 pr !pr
0 Ai tr !tr
0 0 0 0
0
Vr
0
0
0
0
0
0
0
0
Dn
0
0
0
Ai
0
3
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
5
(C.30)
e para a c^amara direita:
2
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
4
3
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
5
(C.31)
As matrizes para os referenciais da c^amara da esquerda s~ao dados neste caso por:
2
1
0A = 0
1
0
0
6
6
6
6
6
6
4
2
1
1A = 0
2
0
0
6
6
6
6
6
6
4
0
1
0
0
0
0
1
0
0
0
Ac
1
3
0
1
0
0
0
0
1
0
Dn
0
0
1
3
7
7
7
7
7
7
5
7
7
7
7
7
7
5
(C.32)
(C.33)
C.2. CINEMATICA
(DIRECTA E INVERSA)
2
1
2A = 0
3
0
0
6
6
6
6
6
6
4
2
1
3A = 0
4
0
0
6
6
6
6
6
6
4
2
cos(pl )
4 A = sin(pl )
5
0
0
6
6
6
6
6
6
4
2
5A =
6
6
6
6
6
6
6
4
149
3
0
0
1
0
0
,1
0
0
0
0
Ap
1
0
0
,1
0
0 0
1 0
0 ,Dc
0 1
7
7
7
7
7
7
5
(C.34)
3
7
7
7
7
7
7
5
0 sin(pl )
0 , cos(pl )
1
0
0
0
(C.35)
0
0
At
1
3
7
7
7
7
7
7
5
, sin(tl ) 0 cos(tl ) ,Ai sin(tl )
cos(tl ) 0 sin(tl ) Ai cos(tl )
0
1
0
0
0
0
0
1
2
0
6A = 1
7
0
0
6
6
6
6
6
6
4
,1 0 0
0 0 0
0 1 0
0 0 1
(C.36)
3
7
7
7
7
7
7
5
(C.37)
3
7
7
7
7
7
7
5
(C.38)
Cinematica directa
Usando a propriedade C.3 pode-se encontrar a seguinte relaca~o:
2
0A
6=
6
6
6
6
6
6
4
sin(pl ) cos(pl ) sin(tl ) cos(pl ) cos(tl ) , cos(pl )Ai sin(tl ) + Dn
, cos(pl ) sin(pl ) sin(tl ) sin(pl ) cos(tl ) , sin(pl )Ai sin(tl ) + Dc
0
, cos(tl )
sin(tl )
Ai cos(tl ) + At + Ap + Ac
0
0
0
1
(C.39)
3
7
7
7
7
7
7
5
APE^NDICE C. CINEMATICA
DOS SISTEMAS AUTONOMOS
UTILIZADOS
150
Cinematica inversa
Usando a propriedade C.4 conclui-se que (com C = cos e S = sin):
2
6
6
A0 = 6
4
S(pl)
,C(pl)
0
,S(pl)Dn + C(pl)Dc
C(pl)S(tl) S(pl)S(tl) ,C(tl) ,S(tl)C(pl)Dn , S(tl)S(pl)Dc + C(tl)At + C(tl)Ap + C(tl)Ac + Ai
C(pl)C(tl) S(pl)C(tl) S(tl)
,C(tl)C(pl)Dn , C(tl)S(pl)Dc , S(tl)At , S(tl)Ap , S(tl)Ac
0
0
0
1
(C.40)
3
7
7
5
Relac~oes de velocidade
Usando o programa de Maple referido, a relaca~o directa da velocidade para o pan&tilt da
direita, e dada por (para um ponto P = [0; 0; 0]T no i-esimo referencial):
sin(Tpr )Ai sin(Ttr ) + Dc
0 sin(Tpr )Ai sin(Ttr ) ,1:0 cos(Tpr )Ai cos(Ttr )
,1:0 cos(Tpr )Ai sin(Ttr ) + Dn 0 ,1:0 cos(Tpr )Ai sin(Ttr ) ,1:0 sin(Tpr )Ai cos(Ttr )
2
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
4
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
5
0
0
1
0
0
0
,1:0Ai sin(Ttr )
0
1
0
0
0
1
, cos(Tpr )
sin(Tpr )
0
(C.41)
as variaveis de controlo das junc~oes s~ao dadas pelo vector
[!r ; Vr ; !pr ; !tr ]T :
(C.42)
Multiplicando a matriz pelo vector obtemos o resultado no seguinte formato vectorial
[vx ; vy ; vz ; !x ; !y ; !z ]T :
(C.43)
A relac~ao inversa da velocidade pode ser calculada atraves do programa em maple.
C.3 Matrizes \skew symmetric"
Uma matriz S diz-se que e uma matriz \skew symmetric" se e se so
ST + S = 0
(C.44)
C.3. MATRIZES \SKEW SYMMETRIC"
151
ou por outras palavras sij + sji = 0 e sii = 0. Para o caso de matrizes de 3 3 a matriz
skew simetrica tem a forma
0 ,s1 s2
S = s1 0 ,s3
,s2 s3 0
2
3
6
6
6
4
7
7
7
5
(C.45)
Se ~a = [ax ; ay ; az ]T e um vector, a matriz skew simetrica pode ser denida como S (~a):
0 ,az ay
S (~a) = az 0 ,ax
,ay ax 0
2
3
6
6
6
4
7
7
7
5
(C.46)
Uma das propriedades importante da matriz S (~a) e a linearidade. Pelo que para
quaisquer vectores ~a e ~b pertencentes a <3 e escalares e t^em-se:
S ~a + ~b = S (~a) + S ~b
(C.47)
Outra propriedade importante da matriz S (~a) e que para qualquer vector p~ = [px ; py ; pz ]T :
S (~a)~p = ~a p~
(C.48)
propriedade esta que pode ser vericada por calculos directos.
Outro facto importante, e que se R33 e uma matriz ortogonal, ent~ao usando a relaca~o
anterior teremos:
RS (~a) RT = S (R~a)
(C.49)
Considere-se que uma matriz de rotaca~o R e func~ao de uma unica variavel . Como
R e ortogonal para qualquer valor de ent~ao:
R():R()T = I
(C.50)
derivando ambos os membros da equac~ao C.50 em ordem a e usando a regra do produto
temos
dR() :R()T + R() dRT () = 0
(C.51)
d
d
152
APE^NDICE C. CINEMATICA
DOS SISTEMAS AUTONOMOS
UTILIZADOS
denindo a matriz S como
S = dRd() :R()T
(C.52)
pode-se vericar que a equac~ao C.51 e id^entica a equac~ao C.44, i.e., a matriz S e uma
matriz skew simetrica. Multiplicando a direita ambos os termos da equaca~o C.52 por
R() e usando a eq. C.50 temos
dR() = S:R():
d
Pode se vericar facilmente atraves de calculos que,
dRx(x )
dx
= S (^x):Rx(x )
dRy(y )
dy
= S (^y):Ry(y )
(C.53)
dRz(z )
dz
= S (^z ):Rz (z )
(C.54)
Suponha-se agora, que temos uma matriz de rotac~ao, relacionando dois referenciais, e
que se vai efectuar uma rotaca~o que pode ser decomposta em tr^es rotac~oes em torno de
cada um dos eixos do referencial, i.e.:
0 R (t) =0 R (0):R :R :R
i
i
x y z
(C.55)
onde x , y , z s~ao ^angulos innitesimais, e a matriz esta denida num sistema directo,
com os ^angulos obedecendo a regra da m~ao direita, derivando em ordem a t obtemos,
d0Ri (t) =0 R (0): @Rx :R :R : @x +0R (0):R : @Ry :R : @y +0R (0):R :R : @Rz : @z
i
i
x
i
x y
dt
@x y z @t
@y z @t
@z @t
(C.56)
mas 0Ri(t) e uma matriz ortogonal, pelo que se verica a eq. C.50, i.e.,
0 R (0):R :R :R :RT :RT :RT :0 R (0)T
i
x y z z y x i
=I
(C.57)
derivando esta eq. em ordem a !x , obtemos uma matriz skew dada por
x T 0
T 0
0
T
0
S =0 Ri (0): @R
@x :Rx : Ri(0) = Ri(0):S (^x): Ri(0) = S Ri(0):x^
e pode facilmente vericar-se que
x
S 0 Ri(0):x^ :Rx :Ry :Rz =0 Ri(0): @R
@x :Ry :Rz
(C.58)
(C.59)
C.4. A INFLUE^NCIA DA VELOCIDADE ANGULAR
153
derivando a eq. C.57 em ordem a !y , obtemos uma matriz skew dada por
y T T 0
T 0
:R
:R
:
R
y
):RTx :0Ri (0)T = S 0Ri(0):Rx :y^
S =0 Ri(0):Rx : @R
i(0) = Ri (0):Rx :S (^
y
x
@y
(C.60)
e pode-se vericar facilmente que
y
S 0Ri(0):Rx :y^ :Rx :Ry :Rz =0 Ri(0):Rx : @R
(C.61)
@y :Rz
e nalmente derivando a eq. C.57 em ordem a !z , obtemos uma matriz skew dada por
z T T T 0
T
0
S =0 Ri (0):Rx :Ry : @R
(C.62)
@z :Rz :Ry :Rx : Ri(0) = S Ri (0):Rx :Ry :z^
e pode-se vericar facilmente que
z
(C.63)
S 0 Ri(0):Rx :Ry :z^ :Rx :Ry :Rz =0 Ri (0):Rx :Ry : @R
@z
agora, usando as eq. C.59, C.61 e C.63 na eq. C.56 obtemos,
d0Ri (t) = S 0R (0): _ :x^ + _ :R :y^ + _ :R :R :z^ :0 R (0):R :R :R
(C.64)
i
x
y x
z x y
i
x y z
dt
onde o factor entre [: : : ] e dado por
_ x + _ z : sin (y ) x^+ _ y cos (x ) , _ z : sin (x ) cos (y ) y^+ _ y sin (x ) + _ z : cos (x ) cos (y ) z^
(C.65)
mas a medida que t ! 0 tambem x = y = z ! 0, Rx = Ry = Rz ! I e nalmente
obtem-se
h
i
d0Ri(0) = S (~! ):0 R (0)
i
dt
(C.66)
T
onde ~! =0 Ri(0): _ x ; _ y ; _ z =0 Ri(0): [!x ; !y ; !z ]T .
h
i
C.4 A inu^encia da velocidade angular
Supondo que a eq. C.5 e variavel no tempo, escrevendo a equaca~o de posic~ao,
~p0(t) =0 Ri (t):~pi +0 di(t)
(C.67)
APE^NDICE C. CINEMATICA
DOS SISTEMAS AUTONOMOS
UTILIZADOS
154
derivando a eq. anterior e usando a regra do produto obtemos (note-se que ~pi e constante):
p~_ 0(t) = 0 R_ i(t):~pi +0d_ i (t) = S (~! ) :0Ri (t):~pi +0d_ i (t) = ~! 0 Ri(t):~pi +~v = !~ ~r+~v (C.68)
onde ~r =0 Ri (t):~pi e a posic~ao do vector expressa no 0-esimo referencial e ~v = 0d_ i (t) e a
velocidade a que o i-esimo referencial se movimenta, e ~! =0 Ri : [!x ; !y ; !z ]T .
Tambem e possvel obter a func~ao aceleraca~o, notando que o seguinte se verica,
d(~a ~b) = d~a ~b + ~a d~b
(C.69)
dt
dt
dt
derivando a express~ao C.68 obtemos,
p~0(t) = !_ ~r + ! (~! ~r) + ~v_
(C.70)
~v_ e a acelerac~ao linear. O termo ! (~! ~r) e chamado de aceleraca~o centrpeta do
ponto. A direcc~ao do vector e sempre direccionada na direcca~o do eixo de rotac~ao e e
perpendicular a esse eixo. O termo !_ ~r e chamado da aceleraca~o transversal.
Contudo, num caso mais geral, quando um ponto ~pi possui velocidade, a relaca~o
anterior modica-se para:
p~_ 0 (t) = ~! ~r + ~v +0 Ri(t):~p_ i
e
(C.71)
p~0(t) = !_ ~r + ! (!~ ~r) + 2! 0Ri(t):~p_ i +0 Ri (t):~pi + ~v_
(C.72)
onde o termo 0Ri (t):~pi representa a acelerac~ao linear (a acelerac~ao do ponto). O termo
2! 0 Ri(t):~p_ i e conhecido como a acelerac~ao de Coriolis.
Ap^endice D
Pormenores da realizac~ao pratica
Para realizar a implementaca~o em tempo real, usou-se neste caso uma placa de processamento de imagem (TDMB412), com dois processadores TMS320C40s (ou C40). Apenas
um dos processadores C40, pode adquirir imagens, e sera designado como o C40 master
(TDM435), e o outro C40 sera referenciado como o C40 slave (TDM407), tal como pode
ser visto na Fig. D.3.
Os processadores TMS320C40 s~ao ideais para o processamento de sinal, em aplicac~oes
que requerem processamento massivo, e bastante repetitivo. As aplicaco~es tpicas para
multiplos C40 incluem:
1. Processamento de imagem & Vis~ao por computador
2. Processamento de sinais vindos de Radares e sonares
3. Sistemas de telecomunicaco~es & processamento de voz
4. Rudo & Analise de vibrac~ao e controlo
5. Controlo em tempo real de alta velocidade & Instrumentaca~o
6. Tratamento de imagens medicas
O processador TMS320C40 possui 6 portos de alta velocidade para efectuar comunicac~oes
entre processadores. Estes portos s~ao bidireccionais e possuem uma largura de banda de
155
156
~ PRATICA
APE^NDICE D. PORMENORES DA REALIZACAO
20MBytes/segundo. Seis canais de DMA permitem I/O paralelamente as operaco~es do
CPU. Um C40 a 50MHz e capaz de efectuar 275 milh~oes de operac~oes/seg e 50MFLOPS.
Os modos de enderecamento incluem o linear, circular e bit-reversed. O processador
utiliza tambem uma unidade de 40/32 bits de oating/xed point.
A placa de processamento TDMB412 e uma motherboard de modulos TIM-40 para o
bus do PC. Esta motherboard possui 4 slots, onde podem ser colocados varios modulos
de I/O TIM-40. O interface da motherboard com o PC hospedeiro e garantido atraves de
uma FIFO de 16-bits de barramento. A placa inclu tambem hardware especco, para
permitir efectuar debug do sistema. A placa permite ainda a interligac~ao entre varias
motherboards, atraves de um bus de alta velocidade, podendo assim construir-se varias
topologias de rede, baseadas em multiplos C40.
Os modulos de processamento TIM-40 podem ter um ou mais DSPs C40. Alguns
destes modulos s~ao especcos, e permitem realizar func~oes tais como, input/output digital/analogico, gracos, e framegrabbing.
A placa TDM435 e um modulo 3 TIM-40 que incorpora um sistema de aquisic~ao de
imagem monocromatico com uma resoluc~ao de 8 bits por pixel, um processador C40, e
um sistema de display RGB de 1024 x 1024 x 24-bit com um plano de overlay de 4-bits. O
sistema de aquisic~ao permite seleccionar uma de quatro entradas que e guardada num de
dois blocos de memoria VRAM (memoria do sistema de vdeo) de 1K x 1K, podendo ser
acedido ao mesmo tempo pelo sistema de aquisic~ao, pelo C40 e pelo sistema de display.
S~ao permitidos varios modos de acesso a memoria VRAM, acessos de 4 bytes, 1 byte, com
mascara, escrita/leitura de blocos, etc, o que da ao sistema uma elevada exibilidade. O
conector de expans~ao da memoria global, e usado para aceder a memoria incorporada na
matherboard principal, que e mapeada na zona de memoria global do C40, permitindo
assim salvaguardar varias imagens consecutivamente. O sistema permite adquirir sinais
PAL ou NTSC, e esta equipado com varios ltros antialising, que podem ser seleccionados
por software. O sistema de aquisica~o permite tambem programar o endereco inicial,
perodo entre linhas, tamanho da frame e tamanho de uma linha. O sistema de display,
permite seleccionar qualquer parte dos 2 blocos de 1K x 1K \pixels" para efectuar o
display. O diagrama de blocos encontra-se representado na Fig D.1.
A placa TDM407 e um modulo TIM-40 que incorpora um DSP C40. Este modulo pode
157
PROG. CLOCK
SYNC
PROC.
CONTROL
4MBytes
LOCAL
EDRAM
R
E
G
local bus
3
2
1
0
DIGITIZER
Video Inputs
TMS320C40
filters
global bus
jtag & comm ports
TIM-40 CONNECTORS
VRAM C
VRAM A
VRAM B
video store1
video store2 overlay store
32
32
16
MUX
MUX
8
PROG. CLOCK
4
R
G
B
H
V
RAMDAC
2
SYNC GEN
Video Outputs
Global Bus Expansion
Figura D.1: Diagrama de blocos do TDM435.
158
~ PRATICA
APE^NDICE D. PORMENORES DA REALIZACAO
1MByte
LOCAL
SRAM
local bus
TMS320C40
global bus
TIM-40 CONNECTORS
4MBytes
GLOBAL
DRAM
Figura D.2: Diagrama de blocos do TDM407.
incorporar memoria DRAM ou SRAM de modo a obter um optimo, mistura de velocidade
e espaco. A combinac~ao de memoria pode ser do tipo DRAM/SRAM, DRAM/DRAM,
SRAM/SRAM ou SRAM/DRAM mapeadas no global bus e no local bus. Num modulo
que incorpore os dois tipos de memoria, o codigo, stack e heap podem ser alocados na
memoria de 0-ws SRAM ate 1MB, enquanto outras alocac~oes de maior escala podem ser
feitas na memoria global ate 4MB. O conector de expans~ao da memoria global, e usado
para aceder a memoria incorporada na matherboard principal, que e mapeada na zona de
memoria global do C40. O diagrama de blocos encontra-se representado na Fig. D.2.
O computador hospedeiro, neste caso e um PC, que comunica com o C40 master,
atraves de um canal FIFO, e ambos os C40 podem transferir dados entre si utilizando
um canal de DMA existente e por um porto para enviar comandos. O tempo perdido na
transfer^encia por DMA e quase nulo, porque o canal tem um alta largura de banda, e
ambos os C40 podem enviar dados enquanto est~ao a efectuar processamento. O Frame
grabber pode adquirir imagens a 25 Hz. No entanto como no nosso caso existem duas
c^amaras, e o formato do vdeo de entrada e PAL interlacado, para diminuir o tempo de
aquisic~ao, apenas se capta um dos campos da imagem para cada c^amara, obtendo-se assim
159
Transtech Image Processing
TDM435 Frame Grabber
Master C40
Slave C40
HOST PC
Figura D.3: A placa de processamento de imagem e utilizada em conjunca~o com o sistema
de vis~ao activa, para desenvolver metodos de navegac~ao visuais.
um frame rate de 50 Hz para ambas as c^amaras.
Para este processo funcionar perfeitamente, as duas c^amaras devem-se encontrar sincronizadas. O tempo de aquisic~ao pode ser paralelizado, sobre o tempo de calculo do uxo
optico, uma vez que podem ser denidos varios buers onde a imagem pode ser guardada, e o C40 master permite efectuar a aquisica~o atraves de interrupca~o, que e activada
ao m de cada campo da imagem. Desta forma e possvel garantir que para a mesma
c^amara, a imagem e sempre adquirida do mesmo campo, pois caso contrario, existiria um
shift vertical entre as imagens, o que em termos de uxo optico e prejudicial, pois com
as c^amaras paradas, seria detectado uxo. O problema desta soluca~o, e que a imagem
adquirida apenas e tratada no proximo ciclo, pois para cada c^amara existem 2 buers, um
com a ultima imagem adquirida, e outro para onde a interrupc~ao \agulhou" a aquisic~ao
actual. De qualquer forma, tal n~ao e crtico, pois o atraso relativamente a imagem mais
actualizada e de 502 s. Para garantir coer^encia temporal para o ltro de kalman, a interrupc~ao guarda o tempo actual, quando inicia uma nova aquisic~ao. Assim que um novo
ciclo de processamento e executado, o C40 master efectua a transformac~ao log-polar e
calcula as derivadas temporais, fazendo de seguida o download das matrizes ao C40 slave
e recebe os resultados no proximo ciclo para a c^amara em quest~ao. O C40 slave calcula
ent~ao o uxo optico de acordo com o tipo de uxo utilizado, gera os sinais de \feedback"
160
~ PRATICA
APE^NDICE D. PORMENORES DA REALIZACAO
e efectua o upload para o C40 master no proximo ciclo para a c^amara em quest~ao. O
C40 master mantem um ltro de kalman para ambas as imagens, efectuando integraca~o
temporal, e efectua o upload para o host a uma cad^encia de 12.5Hz. Por sua vez o host
atraves dum porto serie envia os dados a um sistema unix, onde e efectuado o algoritmo
de controlo e onde s~ao enviados os comandos ao robot movel. Devido a implementaca~o
efectuada, existe um delay de 4 ciclos ( 504 ) entre a imagem actualmente adquirida e o seu
resultado, dois dos delays e devido a aquisica~o e dois devido as comunicaco~es entre master
e slave.
A transformac~ao log-polar e efectuada atraves de uma tabela, onde s~ao guardadas as
posico~es do plano cartesiano onde devem ser feitas as amostras. Os \pixels" na redondeza
do pixel amostrado, s~ao usados para efectuar uma convuls~ao gaussiana, baseada apenas
em shifts, a mascara usada e:
1 2 1
(D.1)
2 4 2
1 2 1
Uma das grandes vantagens do C40 e permitir instruc~oes paralelas (leitura, leitura/escrita,
escrita, adicionar/leitura, ...), desta forma em alguns dos processos o tempo de processamento pode ser reduzido a metade ou mais conforme o caso. Outra das vantagens, e
a de permitir aceder a 4 \pixels", apenas com um acesso a memoria de 32 bits, desta
forma, por exemplo, a implementac~ao da mascara apenas obriga a 3 acessos por cada
ponto log-polar amostrado (sem utilizar as instruc~oes paralelas). A transformaca~o logpolar e um dos casos, em que se pode aproveitar ao maximo estas capacidades, a tipo de
exemplo, a transformac~ao log-polar codicada em assembler gasta cerca 14 do tempo da
vers~ao codicada em c (isto porque o compilador de c n~ao codica instruco~es paralelas).
Para efectuar o calculo do uxo optico normal, foi usada tambem uma tabela. Em
cada entrada da tabela, e guardado o resultado da equac~ao:
E1
(D.2)
2
E1 + E22
para E1; E2 = 0, ..., 256. Desta forma para cada ponto usado e necessario efectuar menos
uma multiplicac~ao e menos uma divis~ao. Nesta implementac~ao, apenas se usa 2 nveis na
pir^amide. A imagem de maior resoluc~ao tem um tamanho de 110x150 \pixels". O tempo
2
3
6
6
6
4
7
7
7
5
161
Figura D.4: Cena de teste: Esquerda - movimento de rotac~ao e de translac~ao, e nos outros
apenas e efectuado movimento de translaca~o. Em cima: um nvel de pir^amide, Em baixo:
2 nveis na pir^amide. O algoritmo e o uxo optico normal.
de processamento anda a volta dos 10Hz, uma vez que o ltro - torna mais pesado o
processamento. A Fig. D.4 mostra os resultados obtidos por este algoritmo.
Quanto ao calculo do uxo am, n~ao merece grandes reparos, a menos que se consegue
neste algoritmo obter 25Hz para a mesma dimens~ao da imagem (sem utilizar pir^amides).
Para o caso do processo de navegaca~o com espelhos, a implementac~ao aproveita ao
maximo todas as potencialidades descritas anteriormente, conseguindo-se obter uma taxa
de processamento a 50Hz e resultados para ambas as c^amaras a 25Hz. A tipo de exemplo,
para o histograma vertical contribuem 100 linhas horizontais. O histograma nal possu
uma resoluc~ao horizontal de 384 linhas, isto porque em cada acesso se obt^em 4 \pixels"
numa palavra de 32bits, mas apenas se utilizam 2 para permitir efectuar a soma desses
162
~ PRATICA
APE^NDICE D. PORMENORES DA REALIZACAO
dois \pixels" simultaneamente atraves duma mascara que zera os outros dois. O C40
master neste caso adquire a imagem duma c^amara e efectua os dois histogramas para as
imagens dos dois espelhos dessa c^amara. De seguida envia os dois histogramas ao C40
slave que efectua os dois processos de correlaca~o para estimar o deslocamento horizontal
nas imagens. Ambos os processadores respeitam os 50Hz, no entanto o resultado da
aquisic~ao actual, so se encontra disponvel com 2 ciclos de atraso.
Em conclus~ao: a performance dos algoritmos depende claramente da experi^encia de
programac~ao do utilizador. Existe um certo tempo de aprendizagem, ate o utilizador
tirar partido de todas as potencialidades dos dois C40, uma vez que a programac~ao em
assembler deve obedecer a forma como o pipeline do processador funciona de modo a
introduzir o mnimo de wait states entre as instruc~oes. Outro tipo de implementaca~o que
deve ser evitada, e a utilizac~ao de calculos em oating point, pois as instruc~oes nativas do
processador apenas possuem precis~ao simples, caso seja necessario maior precis~ao, esta so
e possvel atraves das rotinas de emulac~ao do compilador de c, perdendo-se assim o partido
das instruc~oes paralelas. Um dos casos que pode exemplicar este problema, prende-se
com a estimac~ao do uxo am atraves do metodo dos mnimos quadrados, que teve de
utilizar a emulac~ao, n~ao sendo no entanto neste caso um problema crtico.
Ap^endice E
Filtros - e - -
E.1 Introduc~ao
Os metodos de ltragem e predica~o podem ser usados para a estimac~ao presente ou
futura de quantidades cinematicas, tais como a posic~ao, velocidade e acelerac~ao. Estas
caractersticas tornam os ltros bastante aconselhaveis na utilizaca~o de trabalhos que se
desenvolvam em torno de tarefas de tracking, ou outras, tais como seguir a trajectoria de
um corpo no espaco (ex. estimar a velocidade e acelerac~ao do uxo optico).
Existem 2 modos de abordar o problema. O primeiro e a utilizac~ao de coecientes xos
para o ltro (ltros - e - - ), e o segundo, coecientes que variam com o instante de
amostragem (ltros de kalman), que s~ao determinados a priori atraves de um modelo de
rudo e da din^amica do sistema. O primeiro processo possui vantagens computacionais,
no entanto os ltros de kalman, possuem caractersticas de alta precis~ao quando se trata
de efectuar seguimento de sinais ruidosos. O ltro usado na estimac~ao do uxo optico e
do primeiro genero, e pode ser utilizado em sistemas lineares invariantes .
Neste tipo de ltros, as variac~oes s~ao "acomodadas" ao longo do tempo atraves da sua
modelac~ao como rudo. Este facto proporciona que os sistemas lineares din^amicos com
coecientes invariaveis no tempo possuam equaco~es de estado e de medida, bastante mais
simples do que aquelas que s~ao necessarias para o caso variante no tempo. Os ganhos
associados a ambos os ltros podem ser calculados "o-line", e em ambos os casos, a
163
164
APE^NDICE E. FILTROS - E - -
implementac~ao pode ser recursiva, onde os dados adquiridos no passado s~ao includos nas
presentes estimativas. Desta forma, todos os dados s~ao utilizados, mas s~ao "esquecidos"
de forma exponencial. A estimac~ao do valor da variavel no instante k e x^(kjk) e sera
indicado como xs . Com estes ltros, pode-se predizer os valores para o proximo instante.
A predic~ao um passo a frente e denominada por xp = x(k + 1jk), e signica a estimativa
no instante k + 1 dadas as amostras ate ao instante k.
Filtros com coecientes xos tem a vantagem de uma facil implementaca~o. Um dos
exemplos mais aplicados deste tipo de ltros e o ltro - .
E.2 Filtro -
Este ltro e utilizado especialmente, quando apenas existem amostras de posic~ao do objecto e assume um modelo cuja velocidade e constante. Comecemos ent~ao por assumir
um modelo de velocidade constante: considera-se que o objecto evolu a partir de uma
velocidade inicial atraves de um processo de acelerac~oes, que s~ao constantes durante uma
amostra, mas independentes entre as varias amostras. A equaca~o do ltro - que prediz
o seu estado corrente tem a seguinte forma:
xs (k) = x^(kjk) = xp(k) + [x0 (k) , xp(k)]
(E.1)
[x (k) , x (k)]
(E.2)
vs (k) = x^_(kjk) = vs (k , 1) + qT
0
p
xp(k + 1) = x^(k + 1jk) = xs(k) + Tvs (k)
(E.3)
A variavel T simboliza o intervalo de tempo, x0 (k) e a medida efectuada no instante
k e o e s~ao os par^ametros de ganho xos. A quantidade q e normalmente denida
como a unidade, mas em casos onde existam falhas de medidas pode tomar o numero do
valor de iterac~oes desde a ultima medida efectuada. O processo de inicializaca~o pode ser
denido por:
xs (1) = xp(2) = x0(1)
vs (1) = 0
x0(1)]
vs (2) = [x0(2) ,
T
E.2. FILTRO -
165
A equac~ao ( E.1) e usada directamente quando a observac~ao e efectuada no instante
k. Os valores optimos de e s~ao deduzidos em [S.S. Blackman 86] e dependem apenas
do quociente entre o desvio padr~ao do rudo do processo, e o desvio padr~ao do rudo da
medida. A este quociente chama-se de ndice , e os ganhos e s~ao calculados na
depend^encia de atraves das seguintes express~oes:
p
2 + 8 , ( + 4) 2 + 8
=,
8
2 + 4 , p2 + 8
=
4
(E.4)
(E.5)
E.2.1 Filtro - -
O ltro - - e id^entico ao ltro - , so que e baseado num modelo de aceleraca~o constante. Por esta raz~ao o ltro efectua uma predica~o quadratica, em vez de linear. No geral
este ltro tende a ser mais sensvel ao rudo, mas apresenta um desempenho superior na
predic~ao de velocidades que variam lentamente. As suas equaco~es s~ao as seguintes:
xs (k) = x^(kjk) = xp(k) + [x0 (k) , xp(k)]
[x (k) , x (k)]
vs (k) = x^_(kjk) = vs (k , 1) + Tas (k , 1) + qT
0
p
as (k) = x^(kjk) = as (k , 1) + (qT )2 [x0(k) , xp(k)]
2
T
xp (k + 1) = x^(k + 1jk) = xs(k) + Tvs (k) + 2 as (k)
Uma das inicializac~oes possveis para o ltro e:
xs (1) = xp (2) = x0 (1)
vs (1) = as (1) = as(2) = 0
x0 (1)]
vs (2) = [x0(2) ,
T
+ x0(1)]
a3(3) = [x0(3) , 2xT0(2)
2
(E.6)
(E.7)
(E.8)
(E.9)
APE^NDICE E. FILTROS - E - -
166
Os valores optimos para e s~ao denidos como no caso anterior e dependem do
ndice . O valor optimo para e dado por:
2
= (E.10)
Bibliograa
[Alan Oppenheim 79] Alan V. Oppenheim, Alan S. Willsky, Signals and Systems, Prentice Hall International, Inc.
[Alberto Elfes 95] Alberto Elfes, Robot Navigation: Integrating Perception, Environmental Constraints and Task Execution Within a Probabilistic Framework, International
Workshop, Ressoning with Uncertainty in Robotics Conf. - RUR, 95, Amsterdam,
The Netherlands, December 1995, Springer ISBN 3-540-61376-5.
[A.S. Roger e and E.L. Schwartz 90] Roger, A. S. and Schwartz, E.L. Design considerations for a Space-Variant Sensor with Complex Logarithmic Geometry, Proc. 10th
International Conference on Pattern Recognition,Atlantic City, pp. 278-285,1990.
[Barnard e Thompson 80] S.T. Barnard and W.B. Thompson, Disparity analysis of images, IEEE Trans. Pattern Analysis and Machine Intelligence, PAMI-2:333-340,1980.
[B. Lucas e T. Kanade 81] Lucas, B. and Kanade, T., An iterative image registration technique with an application to stereo vision, Proc. DARPA Image Understanding
Workshop pp 121-130, 1981.
[Burt, Xen e Xu 83] P.J. Burt,C. Yen, and X. Xu, Multi-resolution ow-through motion
analysis, In Proc. IEEE CVPR, pp. 246-252, 1983.
[Carl Weiman 94] Carl F. R. Weiman, Log-Polar binocular vision system, NASA phase
II, SBIR Final report, December 1994.
[C. Brown 95] Christopher Brown, Tutorial on Filtering, Restoration, and State Estimation, University of Rochester, Technical Report 534, June, 1995.
167
BIBLIOGRAFIA
168
[C. Fermuller e Y. Aloimonos 91] C. Fermuller and Y. Aloimonos, Estimating 3-D motion
from image gradients, Technical Report CARTR-618 Computer Vision Laboratory,
Center for Automation Research, University of Maryland, 1991 .
[C. Fermuller e Y. Aloimonos 92] C. Fermuller and Y. Aloimonos, The Role of Fixation
in Visual Motion Analysis, Computer Vision Laboratory, Center for Automation
Research, University of Maryland,1992.
[Davison e Murray 95] David W. Murray, Ian D. Reid and Andrew J. Davison, Steering
and Navigation Behaviours using Fixation, Parks Road, Oxford University.
[Davison e Murray 97] Andrew J Davison and David W Murray, Mobile Robot Localisation Using Active Vision, Parks Road, Oxford University, 1997.
[D. Coombs e H. Herman 95] D. Coombs, M. Herman, T. Hong and M. Nashman, Realtime Obstacle Avoidance Using Central Flow Divergence and Peripheral Flow , National Institute of Standards and Technology, Nist Internal Report, June, 1995.
[D. Hegger 87] D. Heeger, A model for extraction of optical ow, Proc. International Conf.
Computer Vision, London, pg 181-190, 1987.
[D. Marr e Poggio 79] D.Marr, and T.Poggio, A computational theory of human stereo
vision, Proc. Royal Soc., London, B-204:301-308,1979.
[Erwin Kreyszig 79] Erwin Kreyszig, Advanced Engineering Mathematics, Third Edition,
ISBN 0-471-50728-8, 1979.
[E.L. Schwartz 77] E.L. Schwartz. Spatial Mapping in the Primate Sensory Projection:
Analytic Struture and Relevance to Perception, Biological Cybernetics, 25:181194,1977.
[FreeBSD Team] FreeBSD Team,
http://www.FreeBSD.org.
The
FreeBSD
Documentation
Project,
[F. Bergholm 90] F. Bergholm, Decomposition Theory and Transformations of Visual Directions, ICCV 90- Int. Conf. on Computer Vision, Dec 1990, pp. 85-90.
BIBLIOGRAFIA
169
[F. Bergholm 93] Frederik Bergholm, On Velocity Estimation and Mean Square Error,
Proc. 8th Scandinavian Conference on Image Analysis, Trans0, Norway, pp 10931100, May 1993.
[G. Sandini e C. Capurro 95] G. Sandini, C.Capurro, F.Panerai, Space variante vision for
an active camera mount, In Proc. SPIE AeroSense95, Orlando, Florida, April 1995.
[H. Wechsler 90] Harry Wechsler, Computacional Vision, Academic Press, Inc, 1990.
[Horn e Schunck 81] Horn, B.K.P., and Schunck, B.G., Determining optical ow, Articial Intelligence 17: 185-204, 1981.
[H.H. Nagel 83] Nagel, H.H., Displacement vectors derived from second-order intensity
variations in image sequences, Comput. Graph. Image. Process, 21: pp 85-117, 1983.
[H.H. Nagel 87] Nagel, H.H., On the estimation of optical ow: Relations between dierent approaches and some new results, Articial Intelligence, 33 pp 299-324, 1987.
[I. Sousa e J. Dias 96] Inacio Sousa, Jorge Dias, Helder Araujo, Normal Optical Flow Based on Log-Polar Images, 4th International Symposium on Intelligent Robotics Systems, Lisbon,22-26 July,1996.
[J. Barron e D. Fleet 94] J.L. Barron, D.J. Fleet, S.S Beauchemin,Systems and Experiment Performance of Optical Flow Techniques, International Journal of Computer
Vision, Kluwer Academic Publishers, pp 43-77, December, 1994.
[J. Batista e J. Dias 93] J.Batista,J.Dias,H.Araujo,A.de
Almeida,
Monoplanar
Camera Calibration, British Machine Vision Conference, 21-23 September,Surrey,UK,1993,Vol2,pp. 476-488.
[J. Dias e C. Paredes 95] J. Dias, C. Paredes, I. Fonseca, H. Araujo,J. Batista,A.de Almeida, Simulating pursuit with Machines - Experiments with Robots and Articial
Vision, ICRA'94, Int. Conference on Robotics and Automation, Nagoya, Japan, May
21-27, 1995.
170
BIBLIOGRAFIA
[J. Dias e C. Paredes 96] Jorge Dias, Carlos Paredes, Inacio Fonseca, Jorge Batista, Helder Ara'ujo, Simulating Pursuit with Machines, Using Active Vision and Mobile
Robots, IEEE Transactions on Robotics and Automation, IEEE Transactions on Robotics and Automation. February 1998, Volume 14, Number 1, pp 1-18.
[J. Dias e J. Batista 93] J. Dias,J. Batista,C. Simplicio, H. Araujo, A.de Almeida, Implementation of an Active Vision System, International Workshop on Mechatronical
Computer Systems for Perception and Action, Halmstad University,Sweden, pp 4553,June 1-3, 1993.
[J. Little, H. Bulthof e T. Poggio 88] J.Little , H. Bulthof, and T. Poggio. Parallel Optical
Flow using local voting, In IEEE 2nd International Conference in Computer Vision,
1988.
[J. Santos-Victor e G. Sandini 95] J. Santos-Victor, G.Sandini, F.Curotto, S.Garibaldi,
Divergent Stereo in Autonomous Navigation: From Bees to Robots VisLab-TR 01/95,
International Journal of Computer Vision, 14, pp 159-177, March 1995.
[K.S.Fu 87] K.S.Fu, R.C.Gonzalez and C.S.G.Lee, Robotics: Control, Sensing, Vision,
and Intelligence, McGraw-Hill Book Company, 1987.
[L.F. Cheong e C. Fermuller 96] L.F. Cheong, C. Fermuller, Y. Aloimonos, Spatiotemporal representations for visual navigation, Fourth European Conference on Computer
Vision 15 - 18 April 1996 at the University of Cambridge, UK.
[Luca Bogoni e Ruzena Bajcsy 94] , Luca Bogoni and Ruzena Bajcsy, Functionality Investigation using a Discrete Event System Approach Journal of Robotics and Autonomous Systems, Special issues on Discrete Event Systems Applications, Vol. 13, No.
3, pages 173-196, November 1994.
[M. Blackburn e H. Nguyen 94] Michael Blackburn and Hoa Nguyen, Autonomous Visual
Control of a Mobile Robot, NRad Robotics, Naval Command, Control and Ocean
Surveillance Center, San Diego, CA 92152-7383, presented at the 1994 ARPA Image
Understanding Workshop, November 13-16, 1994, Monterey, CA.
BIBLIOGRAFIA
171
[M. Irani e B. Rousso 94] Michal Irani, Benny Rousso and Shmuel Peleg, Recovery of
Ego-Motion Using Image Stabilization, IEEE Transactions,1994,pp. 454-460.
[M. Tistarelli e G. Sandini 93] M. Tistarelli and G. Sandini, On the advantages of polar
and log-polar mapping for direct estimation of time-to-impact from optical ow, IEEE
Transactions and PAMI, 14(4)>401-410,1993.
[M. Tistarelli e E. Grosso 90] M. Tistarelli,E. Grosso and G. Sandini, Dynamic Stereo in
Visual Navigation, University of Genoa Techical report, LIRA-TR 4/90 - October
1990.
[M.J. Hawken e A.J. Parker 94] M.J. Hawken and A.J. Parker. Spatial Receptive Field
Organization in Monkey V1 and its Relationship to the Cone Mosaic, In Models of
Neural Functions. Landy and Monshon, 1994.
[N. Ancona e T. Poggio 93] Nicola Ancona and Tomaso Poggio, Optical ow from 1D
Correlation: application to a simple Time-To-Crash Detector, Massachusetts Institute, AI Memo,N o 1375, C.B.C.L. paper N o 74, 1993.
[Nelson, R.C., Aloimonos, J. 87] Nelson, R.C., Aloimonos, J., Finding Motion Parameters From Spherical Flow Fields (Or The Advantages Of Having Eyes In The Back
Of Your Head), WCV(87), pp. 145-150.
[P. Fornland 95] Par Fornland, Direct Obstacle Detection and Motion from SpatioTemporal Derivatives, Active Perception Laboratory (CVAP), KTH, Stockholm, Prague, Czech Republic, September 1995.
[Peixoto 95] Paulo Jose Monteiro Peixoto, Estudo de Transpar^encia e coer^encia de movimento em sequ^encias de imagens, Tese de Mestrado, Dept. de Engenharia Electrotecnica, Universidade de Coimbra, 1995.
[P. Nordlund e T. Uhlin 95] P. Nordlund and T. Uhlin, Closing the Loop: Detection and
Pursuit of a Moving Object by a Moving Observer, CVAP-Computer Vision and
Active Perception Laboratory, NADA- Royal Institute of Technology, June, 1995.
BIBLIOGRAFIA
172
[Povray Team] PovRay http://www.povray.org.
Persistence
Of
Vision
Development
Team,
[Ricardo e Michel 91] Swain Oropeza Ricardo and Devy Michel, Visually-guided Navigation of a Mobile Robot in a Structured Environment LAAS-CNRS, Toulouse, France.
[R. Guissin e S. Ullman 91] Rami Guissin, Shimon Ullman, Direct Computation of the
Focus of Expansion From Velocity Field Measurements, IEEE Transactions,1991,pp.
146-155.
[Roth, Gerhard e Levine 92] Roth, Gerhard, and Levine, Martin, Minimal Subset Random Sampling for Pose Determination and Renement, AMV Strategies, pp. 1-21.
[Robuter 92] ROBOSOFT Technopole d'lzarbel F-64210 BIDART tel (33) 05 59 41 53 60
fax (33) 05 59 41 53 79 http://www.robosoft.fr.
[S.S. Blackman 86] Samuel S. Blackman, Multiple-Target Tracking with Radar Application, Artech House, Inc, ISBN 0-89006-176-3.
[S. Uras e F. Girosi 88] Uras, S., Girosi, F., Verri, A., and Torre, V., A computational
approach to motion perception, Biol. Cubern 60: pp 79-97, 1988.
[T. Cord e D. Pallmer 94] Thomas Cord and Dirk Pallmer, Distance Measuring for Mobile Robots Using Axial Motion Stereo, Forschungszentrum Informatik, in Proceedings
of the 3th International Workshop on Robotics in Alpe-Adria Region, Bled, July 1994.
[V. Sundareswaran e P. Bouthemy 94] , Venkataraman Sundareswaran, Patrick Bouthemy and Francois Chaumette, Visual servoing using dynamic image parameters
INRIA-Institut National de Recherche en Informatique et en Automatique Rapport
de recherche no 2336 -Ao^ut 1994.
[Yaakov Xiao 93] Yaakov Bar-Shalom, Xiao-Rong Li, Estimation and Tracking:
Principles,Techniques, and Software Artech House, inc, 1993.
BIBLIOGRAFIA
173
[Y. Aloimonos e Z. Duric 94] Yiannis Aloimonos and Zoran Duric, Estimating The Heading Direction Using Normal Flow, International Journal of Computer Vision, Kluwer
Publishers,1994,13:1,pp. 33-56.