Orientação Automática na Baixa Pombalina:
Classes de Equiprojectividade e Estimação Sequenciala Partir de Vı́deo
André Martins
11 de Setembro de 2005

Resumo
O problema de inferir a orientação de uma câmara que adquire uma sequência de vı́deo é
de grande interesse em Visão por Computador, surgindo aplicações nas áreas de robótica
móvel, calibração e reconstrução 3D.
As abordagens tradicionais requerem um passo intermédio de detecção de padrões(cantos ou linhas de contorno) em cada imagem e a sua posterior correspondência entre
as várias imagens; este passo é computacionalmente pesado e requer o ajuste cuidadosode muitos parâmetros. Em vez disso, este trabalho sugere uma abordagem probabilı́sticade estimação sequencial fazendo uso de um modelo adequado a cenas urbanas, dito
mundo de Manhattan, segundo o qual a maioria dos contornos se alinha em três direcções
ortogonais.
As principais contribuições são: (i) a definição de classes de equivalência de orientações equiprojectivas; (ii) a introdução de um modelo de pequenas rotações adequado
ao movimento da câmara; e (iii) a separação de cada estimação em duas partes reduzindo
a complexidade de O(N 3 ) para O(N 2 ). A redução do peso computacional viabiliza a
sua aplicação em tempo real. O desempenho é avaliado utilizando sequências de vı́deoda Baixa Pombalina.
Palavras-chave: Visão por Computador, orientação da câmara, estimação sequencial, cenas urbanas, calibração da câmara.
Classificação ACM: I.4 (IMAGE PROCESSING AND COMPUTER VISION), I.5 (PATTERN
RECOGNITION), I.3 (COMPUTER GRAPHICS), I.6 (SIMULATION AND MODELING).

Conteúdo
1 Introdução
1.1 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Conteúdo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22
3

2 Geometria do mundo de Manhattan
2.1 Mundo de Manhattan . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Orientação da câmara . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Pontos de fuga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Orientações equiprojectivas . . . . . . . . . . . . . . . . . . . . . . . . .
2.5 Modelo de pequenas rotações . . . . . . . . . . . . . . . . . . . . . . . .
2.6 Generalização para outros mundos estruturados . . . . . . . . . . . . . .

4
4
5
7
8
11
13

3 Estimação sequencial da orientação
3.1 Critério de estimação . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Função de verosimilhança . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 Gradiente de intensidade . . . . . . . . . . . . . . . . . . . . . .
3.2.2 Classes de pixel . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.3 Funções de probabilidade da magnitude do gradiente . . . . . . .
3.2.4 Funções de probabilidade da direcção do gradiente . . . . . . . .
3.2.5 Função de verosimilhança . . . . . . . . . . . . . . . . . . . . . .
3.3 Procedimento de localização das estimativas . . . . . . . . . . . . . . . .
3.3.1 1.◦ passo: Estimação de β e γ . . . . . . . . . . . . . . . . . . . .
3.3.2 2.◦ passo: Estimação de α . . . . . . . . . . . . . . . . . . . . . .
3.3.3 Localização das estimativas . . . . . . . . . . . . . . . . . . . . .
3.4 Hipótese nula e classificação de contornos . . . . . . . . . . . . . . . . .
3.5 Experiências e Resultados . . . . . . . . . . . . . . . . . . . . . . . . . .

16
16
17
17
18
18
19
19
20
20
21
22
22
23

4 Conclusão26

Bibliografia

27

1

Capı́tulo 1

Introdução1.1

MotivaçãoAplicações em áreas como Vı́deo Digital, Realidade Virtual, Robótica Móvel e NavegaçãoAutomática requerem métodos eficientes para estimar a “pose” (i.e., a posição e aorientação) de uma câmara de vı́deo, ao longo do tempo, a partir da sequência de imagens
que esta captura. De modo análogo, em Processamento de Imagem, Reconhecimento de
Padrões e Pesquisa de Imagens surge muitas vezes a necessidade de, a partir de uma única
imagem, caracterizar a estrutura tridimensional (3D) de objectos, o que muitas vezes
requer, de alguma forma, estimar a pose da câmara relativamente a esses objectos. Em
resumo, pode afirmar-se que o desenvolvimento de métodos eficientes para a estimaçãoda posição e/ou orientação de uma câmara, quer a partir de uma imagem, quer a partirde uma sequência de imagens, é actualmente uma das maiores preocupações em Visãopor Computador.
As abordagens tradicionais baseiam-se na detecção de “padrões” em imagens; estes
padrões consistem geralmente em cantos de objectos ou em linhas de contorno. Em
aplicações envolvendo múltiplas imagens, uma vez detectados estes padrões em cadaimagem, o passo seguinte consiste em correspondê-los entre diferentes imagens, por exemplo através de seguimento (pode encontrar-se alguns exemplos em [1, 2, 3]). Em
aplicações que utilizam uma única imagem, os métodos mais comuns envolvem o agrupamento de padrões (ver por exemplo [4, 5, 6]). Todavia, é consensual que tanto a
correspondência como o agrupamento automático de padrões são problemas difı́ceis epara os quais os resultados até agora atingidos se revelam pouco satisfatórios; existe umsério compromisso entre robustez e comportabilidade computacional que muitas vezes
inviabiliza o seu uso em aplicações práticas. Para além disso, o facto de se basear toda
a inferência num conjunto de padrões geralmente pequeno (com relação à totalidade daimagem) faz com que informação útil possa ser prematuramente desprezada.
No caso de múltiplas vistas, têm sido propostos métodos que estimam a estrutura
3D directamente a partir dos valores da intensidade das imagens, i.e., sem envolver adetecção e correspondência de padrões – exemplos disso encontram-se em [7, 8]. Porém,estas abordagens conduzem quase sempre a algoritmos complexos, de convergência lenta,
e demasiado dependentes da hipótese de que, de vista para vista, o padrão de brilho em
pontos correspondentes permanece aproximadamente constante, tornando-os por isso
muito sensı́veis a ruı́do.
No caso de uma única imagem, J. Coughlan e A. Yuille propuseram recentemente
uma abordagem diferente em [9, 10] que evita a detecção e agrupamento de padrões. A
ideia consiste em utilizar conhecimento prévio sobre a estrutura do “mundo”. De facto,
em grande parte das cenas urbanas, muitos contornos estão alinhados com uma de três2direcções ortogonais, definindo um sistema de eixos. Sob este modelo que designaram
por mundo de Manhattan, J. Coughlan e A. Yuille utilizaram técnicas de inferência
bayesiana para estimar a componente rotacional da pose 3D (i.e., a orientação) dacâmara com relação àquele sistema de eixos. O modelo de mundo de Manhattan foi
aplicado depois disso (paralelamente ao trabalho que aqui se apresenta) em [11] para
auto-calibração da câmara e estendido em [12] para ambientes urbanos mais genéricos.
O trabalho aqui apresentado inspira-se no modelo de mundo de Manhattan para
propor um novo método de estimação da orientação 3D a partir de sequências de imagens
de cenas urbanas. As contribuições originais são:• enquanto que em [9, 10] o modelo de mundo de Manhattan é utilizado para estimara orientação a partir de uma única imagem, este método estende o seu uso parasequências de imagens;• é introduzido um novo modelo de pequenas rotações que expressa o facto de acâmara de vı́deo movimentar-se suave e continuamente no espaço 3D;• define-se o conjunto das orientações 3D em termos de classes de equivalência deorientações equiprojectivas, onde são consideradas equivalentes as orientações que
conduzem ao mesmo conjunto de pontos de fuga e, por isso, são indistinguı́veis doponto de vista da estimação. Mostra-se como cada classe de equivalência tem 24
elementos e se relaciona geometricamente com o grupo octaédrico das simetrias
próprias do cubo. Reduz-se o espaço de procura da solução para uma região maispequena que contém o conjunto quociente;• para cada imagem, decompõe-se em dois passos a estimação dos três ângulos que
parametrizam a orientação da câmara: um passo de complexidade O(N 2 ) ondesão estimados dois destes ângulos (elevação e torção), e outro passo de complexidade O(N ) onde é estimado o terceiro ângulo (azimute). Esta decomposiçãoreduz consideravelmente o peso computacional de cada estimação, pois reduz acomplexidade de O(N 3 ) para O(N 2 + N ) = O(N 2 );• mostra-se teoricamente como o modelo de mundo de Manhattan é um caso particular de uma classe de mundos estruturados de dimensão arbitrária e como,uma vez formalizada essa estrutura, todos os resultados fundamentais podem ser
extrapolados.

1.2

Conteúdo

Este trabalho está organizado da seguinte forma: no Capı́tulo II introduz-se a geometria inerente ao modelo de mundo de Manhattan, definindo-se o conceito de orientações
equiprojectivas e o modelo de pequenas rotações; mostra-se também como os mesmos
resultados teóricos podem ser extrapolados para uma classe de mundos estruturados dedimensão arbitrária. O Capı́tulo III debruça-se sobre a abordagem probabilı́stica e consequente implementação do algoritmo de estimação sequencial da orientação da câmara,tendo em conta os conceitos definidos no Capı́tulo II; discute-se ainda os resultados
experimentais da aplicação deste algoritmo a sequências de vı́deo reais. Finalmente, oCapı́tulo IV expõe as conclusões e sugere desenvolvimentos futuros.

3

Capı́tulo 2

Geometria do mundo de
Manhattan
2.1

Mundo de Manhattan

Em Visão por Computador, designa-se por mundo o espaço 3D observado por um sistemade visão, geralmente constituı́do por uma ou mais câmaras de vı́deo ligadas a uma
unidade de processamento. O sistema de navegação aqui proposto é constituı́do por
uma única câmara de vı́deo digital ligada a um processador, capturando uma sequência
de imagens {I1 , I2 , . . . , In }. O objectivo do sistema consiste em obter uma sequência
b1 , Ob2 , . . . , Obn } da orientação da câmara para cada um destes instantes.
de estimativas {OConsidera-se parte do objectivo obter desempenhos capazes de viabilizar o uso do sistema
em tempo real, pelo que se dará ênfase à rapidez do processamento.
Em [9, 10], J. Coughlan e A. Yuille sugeriram uma nova abordagem para estimara orientação da câmara a partir de uma única imagem. O seu trabalho, desenvolvido
para o Smith-Kettlewell Eye Research Institute, em São Francisco, tinha como objectivo
implementar um sistema de ajuda para cegos e amblı́opes capaz de orientá-los nas ruas,
avenidas ou no interior de edifı́cios de uma cidade; o sistema seria constituı́do por uma
câmara acoplada no peito do utilizador, cujas imagens seriam processadas de modo aemitir, por exemplo, um aviso sonoro se a trajectória tendesse a desviá-lo para a estrada
ou contra um obstáculo como uma parede.
J. Coughlan e A. Yuille decidiram tirar partido da natureza “urbana” do mundo para
onde o sistema de navegação foi idealizado e, como alternativa aos métodos tradicionais,
propuseram seguir uma abordagem estatı́stica baseada numa modelização prévia domundo capaz de captar essa natureza “urbana”. Assim surgiu o conceito de “mundo de
Manhattan”, que se procurará aqui definir com alguma informalidade.
Definição 2.1 Mundo de Manhattan (do inglês Manhattan world) é um modelo domundo segundo o qual este é constituı́do essencialmente por objectos cujas arestas sãolinhas rectas que, no seu conjunto, estão alinhadas segundo três direcções ortogonais. O
referencial ortonormado (x, y, z) definido por estas direcções designa-se por referencial
de Manhattan, sendo x, y e z designados por eixos de Manhattan.
As Figuras 2.1a-c mostram uma representação esquemática de um mundo de Manhattan e dois exemplos reais de mundos passı́veis de serem modelizados como sendo “deManhattan”: uma fotografia de uma cena interior e outra de uma exterior. Grande partedas cenas “urbanas” podem ser classificadas como mundos de Manhattan; as direcções
ortogonais são devidas à presença de salas, corredores, ruas, avenidas, edifı́cios, etc. A

4

própria designação é inspirada em Manhattan (Nova Iorque), que se caracteriza pelo desenho ortogonal das suas ruas e avenidas e pela paisagem “paralelepipédica” conferida
pelos arranha-céus.
A Baixa Pombalina, em Lisboa, é também um exemplo real de mundo de Manhattan.
Por esse motivo, grande parte das experiências realizadas resultaram de sequências de
vı́deo obtidas nesse local.
Recentemente, outros trabalhos adoptaram modelos inspirados no mundo de Manhattan para cenários ligeiramente diferentes. Um exemplo é o mundo de Atlanta [12],que pode ser visto como uma generalização do mundo de Manhattan adaptado a cenas
onde predominam edifı́cios paralelepipédicos que partilham uma direcção comum – avertical –, mas que fazem um ângulo de azimute entre si.

z
(a)

y

x
(b)

(c)

Figura 2.1: Mundos de Manhattan: (a) Representação esquemática; (b) Fotografia deuma cena interior: sala de aula; (c) Fotografia de uma cena exterior: Rua de Santa
Justa, na Baixa Pombalina de Lisboa. Note-se como em (b) e (c) são visı́veis as três
direcções ortogonais dos eixos de Manhattan.

2.2

Orientação da câmara

O modelo utilizado para a câmara é o da câmara escura 1 . Para uma câmara calibrada,a adopção deste modelo não implica perda de generalidade, pois o conhecimento dos
parâmetros intrı́nsecos da câmara permite rectificar as imagens de modo a simular uma
1

Designado na literatura anglo-saxónica por pinhole camera.

5câmara escura – em [13] e [14], por exemplo, são dados alguns exemplos de métodos decalibração.
De acordo com este modelo, todos os raios ópticos convergem num ponto – o centroóptico – e são projectados numa superfı́cie planar – o plano da imagem. A distância
entre o centro óptico e o plano da imagem é designada por distância focal e o ponto
do plano da imagem mais próximo do centro óptico designa-se por ponto principal.
A Figura 2.2 representa esquematicamente a câmara escura.

f
C – centro óptico
P – ponto principal
f – distância focal
π – plano da imagem

P

C
X'

π
X

Figura 2.2: Representação esquemática da câmara escura. Um ponto X no espaçotridimensional é projectado no ponto X0 do plano da imagem.
Sejam respectivamente (x, y, z) e (n, h, v) os referenciais do mundo de Manhattan eda câmara. Estes relacionam-se através da equação(n, h, v) = (x, y, z) · O ,(2.1)

onde O ∈ SO(3) é uma matriz de rotação que representa a orientação da câmara.
Adoptando o sistema de coordenadas definido pelo referencial de Manhattan, vem:

O = [n, h, v].

(2.2)

A orientação tem três graus de liberdade e pode ser parametrizada por três ângulos
exprimindo três rotações sucessivas (ver Fig. 2.3):• α, o ângulo de compasso ou azimute, correspondendo a uma rotação em torno do
eixo z;• β, o ângulo de elevação sobre o plano xy;• γ, o ângulo de torção em torno da linha de vista.
No texto que se segue, a orientação é frequentemente representada em função destes
parâmetros, O ≡ O(α, β, γ).
De acordo com esta parametrização, os ângulos α, β e γ relacionam-se com n, h e v
da seguinte forma:n = [cos α cos β, sin α cos β, sin β]T
(2.3)
e

·
[h, v] = [h0 , v0 ]cos γ − sin γ
sin γ cos γ

¸
,

(2.4)

onde, representando por “×” o produto externo vectorial,z×n= [− sin α, cos α, 0]T||z × n||
= n × h0 .

h0 =
v0

6

e

(2.5)
(2.6)

z
γ

y

C
x

v
v 0

β

α

v0
P

h
h0

h0
n plano da imagem

Figura 2.3: Parametrização da orientação da câmara. À esquerda: o ângulo de compasso
α e o ângulo de elevação β. À direita: o ângulo de torção γ representado no plano da
imagem.

Utilizando coordenadas homogéneas2 , e escolhendo o centro óptico C como origem dosistema de coordenadas, i.e., C = [0, 0, 0, 1]T , vem para o ponto principal P e para oplano da imagem π:
·
¸
·
¸
fn
n
P=
e π=
,
(2.7)
1
−f
onde f representa a distância focal. Sendo (P; n, h, v) o referencial afim da câmara,
as coordenadas homogéneas de um ponto neste referencial obtêm-se das suas coordenadas homogéneas no referencial (C; x, y, z) multiplicando à esquerda por uma matriz
de transformação 4 × 4 dada por
 T
 

n
−f
nx ny nz −f
 hT


0 
 =  hx hy hz 0  .
T=
(2.8)
T
 v
0   vx vy vz 0 
0T
1
0 0 0
1

2.3

Pontos de fuga

No espaço projectivo P3 , a intersecção de quaisquer duas rectas com a mesma direcçãod é um ponto ideal. A projecção desse ponto ideal no plano da imagem designa-se
por ponto de fuga segundo d. Naturalmente, escolhida uma direcção d, o respectivo
ponto de fuga pode obter-se calculando a intersecção do plano da imagem com a recta
de direcção d que passa no centro óptico.
Posto isto, designando por Wx , Wy e Wz os vectores com as coordenadas homogéneas dos pontos de fuga segundo cada um dos eixos de Manhattan x, y e z, estes
serão necessariamente da forma [wx1 , 0, 0, wx4 ]T , [0, wy2 , 0, wy4 ]T e [0, 0, wz3 , wz4 ]T , respectivamente, e satisfarão π T Wx = π T Wy = π T Wz = 0, o que, recorrendo a (2.7),
conduz a:Wx = [f, 0, 0, nx ]T,

Wy = [0, f, 0, ny ]TeWz = [0, 0, f, nz ]T .

(2.9)

Mudando para o referencial da câmara, o que é feito utilizando a matriz T de (2.8),
correspondem aos mesmos pontos as coordenadas homogéneas TWx = [0, f hx , f vx , nx ]T ,TWy = [0, f hy , f vy , ny ]T e TWz = [0, f hz , f vz , nz ]T , respectivamente.
2

Ver [15] para uma breve explicação desta e de outras noções de Geometria Projectiva.

7

Identificando agora o plano da imagem π com o plano projectivo P2 , os mesmos
pontos de fuga, vistos como pontos 2D, descrevem-se no referencial afim (P; h, v) através
dos vectores de coordenadas homogéneas vx , vy e vz (ver Figura 2.4a) dados por
vx = [f hx , f vx , nx ]T = Rγ · [−f sin α, −f cos α sin β, cos α cos β]T ,(2.10)

vy = [f hy , f vy , ny ]T = Rγ · [f cos α, −f sin α sin β, sin α cos β]T ,(2.11)TT

vz = [f hz , f vz , nz ] = Rγ · [0, f cos β, sin β] .
com

(2.12)


cos γ − sin γ 0
Rγ =  sin γ cos γ 0  .
001(2.13)

onde se recorreu a (2.3)-(2.6). Confrontando as expressões (2.10)-(2.12) com (2.2), podever-se que os pontos de fuga vx , vy e vz se relacionam com as linhas da matriz deorientação de acordo com


0 f 0
[vx , vy , vz ] =  0 0 f  OT .
(2.14)
1 0 0

vx

(a)

vy vx

vz

(b)
vz

vy

Figura 2.4: Pontos de fuga dos eixos de Manhattan sobre duas imagens de um dado. A
orientação da câmara é diferente nas imagens (a) e (b); porém, os pontos de fuga, no
seu conjunto, têm a mesma localização. Note-se como, de (a) para (b), os pontos defuga vy e vz são permutados.

2.4

Orientações equiprojectivas

A expressão (2.14) mostra que a orientação da câmara O pode ser estimada mediante
a localização na imagem dos pontos de fuga dos eixos de Manhattan, vx , vy e vz .
Porém, partindo apenas de uma imagem de um mundo de Manhattan, sem informaçãoadicional sobre a geometria do mundo, tais pontos de fuga são indistinguı́veis, i.e.,
localizá-los equivale a conhecer o conjunto {vx , vy , vz }, não se sabendo, no entanto,qual o ponto de fuga que corresponde a cada eixo de Manhattan – a possibilidade de
permutar os pontos de fuga conduz a múltiplas soluções para a orientação. Esta situaçãoé ilustrada nas Figuras 2.4a-b, onde se mostra como duas orientações da câmara distintas
originam o mesmo conjunto de pontos de fuga. Esta ambiguidade motiva o conceito deequiprojectividade.

8Definição 2.2 (Orientações equiprojectivas) Seja V(O) = {vx , vy , vz } o conjunto
dos pontos de fuga determinado por uma orientação O. Duas orientações O e O0 denominam-se equiprojectivas sse possuem idênticos conjuntos de pontos de fuga, i.e., sse
V(O) = V(O0 ).
A equiprojectividade, como se acaba de definir, satisfaz as propriedades de reflexividade, simetria e transitividade; portanto, é uma relação de equivalência. O resultado
seguinte mostra como pode obter-se a classe de equivalência E(O) de uma dada orientação, i.e., o conjunto de todas as orientações equiprojectivas com O.
Proposição 2.3 Designe-se por SP+ (n) o grupo das matrizes de permutação com
sinal n × n cujo determinante é positivo (i.e., o conjunto das matrizes n × n com
entradas em {−1, 0, 1}, com exactamente um elemento não nulo por linha e por coluna
e com determinante positivo, necessariamente igual a 1).
Duas orientações O e O0 são equiprojectivas sse existir M ∈ SP+ (3) tal que O0 = MO.
Cada classe de equivalência de orientações equiprojectivas tem exactamente 24 elementos, o número de elementos de SP+ (3).
Demonstração: Seja V(O) = [vx , vy , vz ] a matriz definida pelos pontos de fuga
associados a O. O e O0 são equiprojectivas sse possuem os mesmos pontos de fuga amenos de um factor de escala e de uma permutação, i.e., sse existem uma matriz depermutação P e uma matriz diagonal Λ = diag(λ1 , λ2 , λ3 ) tais que V(O) = V(O0 )ΛP. De(2.14) tem-se


0 f 0
V(O) = KOT =  0 0 f  OT ,(2.15)
1 0 0
pelo que multiplicando ambos os membros à esquerda por K−1 (K é obviamente invertı́vel)
conclui-se que O e O0 são equiprojectivas sse OT = O0T ΛP, i.e., sse O0 = ΛPO = MO, com
M = ΛP, ou mij = λi pij . Dado que O, O0 ∈ SO(3), vem |λ1 | = |λ2 | = |λ3 | = 1, i.e.,
mij = ±pij , e det M = 1; isto equivale a ter M ∈ SP+ (3). Ora, o grupo SP+ (n) é isomorfo
ao grupo octaédrico das simetrias “próprias” do n-cubo e tem ordem 12 n! 2n , o total depossı́veis combinações de um número par de operações de permutação e troca de sinal
com n elementos. Para n = 3, vem 12 3! 23 = 24, sendo este o número de elementos decada classe de equivalência definida pela relação de equiprojectividade.

z=f

z=0

x=f
y=0

x=0
y=f

x=–f
y=0

x=0
y=–f

z=–f
x=f
y=0

Figura 2.5: Localização 3D dos pontos principais de orientações equiprojectivas, nos
octantes de uma esfera de raio f centrada em C. Representam-se duas classes de equivalência: os pontos brancos e os pontos pretos; os segundos são o “reflexo” dos primeiros.

9A Figura 2.5 ilustra duas classes de equivalência formadas por orientações equiprojectivas, em que uma é o “reflexo” da outra.
O conceito de equiprojectividade revela-se útil em qualquer problema de estimaçãode orientação ou de localização de pontos de fuga, visto que permite reduzir os espaçosde procura. Assim, em vez de se procurar sobre todo o domı́nio SO(3), pode recorrer-se àrelação de equivalência definida pela equiprojectividade e utilizar um espaço de procurapara a orientação mais pequeno que contenha o conjunto quociente SO(3)/SP+ (3). A
proposição seguinte formaliza este reciocı́nio:
Proposição 2.4 Toda a orientação O ∈ SO(3) tem uma equiprojectiva O0 ∈ R, onde Ré uma região em SO(3) definida por:i π πioni π πi, β∈ − ,, e γ ∈ ]−ϕ, ϕ] ,(2.16)
R = O(α, β, γ) ∈ SO(3) : α ∈ − ,
4 4
4 4
√
com ϕ = arctan 2 ≈ 54.7◦ . Uma afirmação equivalente é: qualquer que seja a orientação da câmara, existe pelo menos um ponto de fuga na região representada na
Fig. 2.6.

ϕ ∼ 54.7
0fFigura 2.6: Representação do plano da imagem. É garantida a existência de pelo menosum ponto de fuga na região a sombreado.
Demonstração: Por simplicidade, vamos utilizar coordenadas cartesianas paraei = [vi1 /vi3 , vi2 /vi3 ]T = [f hi /ni , f vi /ni ]T para i ∈ {x, y, z},os pontos de fuga, i.e., v
sendo vi = [vi1 , vi2 , vi3 ]T as coordenadas homogéneas. Como se poderá ver recorrendo
a limites, a eventual existência de pontos “no infinito”, i.e., para os quais vi3 = 0, nãoimplica perda de generalidade. De (2.10)-(2.12) tem-se (para i, j ∈ {x, y, z})
´
³
(
1
2
−
1
se i = j
f
2
ni
eiT v
ej =
(2.17)v
2−f
se i 6= j,ei )1/2 entre os pontos vei eo que permite obter tanto a distância euclidiana di = (e
viT v
eT v
e
v

e = [0, 0]T como o ângulo θij = arccos dii djj formado pelas linhas [eei ] e [eej ], comp
pv
pv
i 6= j.
e , i.e., D = {(u, v) ∈ R2 :Considere-se agora o disco D com raio f e centro em p222
ei ∈ D sse di ≤ f , o que, por (2.17), é equivalente a
u + v ≤ f }. Temos que v
22
2
ni ≥ 1/2. Visto que nx + ny + n2z = 1, a condição ni2 ≥ 1/2 implica n2j ≤ 1/2 para
qualquer j 6= i, o que significa que não pode existir mais que um ponto de fuga nointerior do cı́rculo D. Para além disso, os três pontos de fuga estão todos na fronteiraou no exterior de D sse n2i ≤ 1/2, para i ∈ {x, y, z}.
Para completar a demonstração, é ainda necessário o seguinte resultado intermédio:10

ei e vej , com i 6= j, verificam cos θij ≤ 0.
Lema 2.5 Quaisquer dois pontos de fuga v
ek ∈ D, com k 6= i e k 6= j, então cos θij ≥ − 31 .
Para além disso, se v
Demonstração (do lema): A primeira afirmação é consequência imediata de (2.17).
2
Para demonstrar a segunda afirmação, obtém-se min cos θij = − minf di dj em função de ni

e nj , no domı́nio definido por n2i + n2j ≤ 1/2. O mı́nimo ocorre em |ni | = |nj | = 12 com
valor −1/3.
√
Uma vez que 12 arccos(− 13 ) = arctan 2 ≈ 54.7◦ , a existência de um ponto de fuga na
região a sombreado da Figura 2.6 é uma simples consequência do Lema 2.5. Para se obter
ei um ponto de fuga localizado nessa região(2.16), considere-se uma orientação O e seja v
a sombreado. A Proposição 2.3 garante então a existência de uma orientação equiproey0 , v
ez0 } satisfazendo: (i) v
ez0 = vei , e (ii) d0x ≤ d0y . De
jectiva O0 com pontos de fuga {evx0 , v
√ ¤√¤(2.10) – (2.13) temos, devido a (i), que β 0 ∈ ]−π/4, π/4] e γ 0 ∈ − arctan 2, arctan 2 ,e devido a (ii), que α0 ∈ ]−π/2, π/2], o que conclui a demonstração.

2.5Modelo de pequenas rotações

Vamos agora assumir que a câmara se move e adquire uma sequência de imagens{I1 , . . . , IN }. Seja Ok = O(αk , βk , γk ) a orientação na k-ésima imagem. A sequência deorientações {O1 , . . . , ON } depende apenas da componente rotacional do movimento, i.e.,é independente da translação da câmara. Numa sequência de vı́deo tı́pica, a orientaçãoda câmara varia suave e continuamente. Esta propriedade é formalizada introduzindo omodelo de pequenas rotações, que a seguir se descreve.
Definição 2.6 (modelo de pequenas rotações) Seja Rk (ρk , ek ) ∈ SO(3) a componente rotacional do movimento da câmara entre a (k −1)-ésima e a k-ésima imagem,
onde ρk e ek representam o ângulo e o eixo de rotação, respectivamente. Independentemente de ek , diz-se que a câmara é consistente com o modelo das pequenas rotaçõesµ(ξ) sse existe um “pequeno” ângulo fixo ξ tal que |ρk | ≤ ξ para qualquer k.
Nas experiências realizadas (ver Secção 3.5), usou-se o modelo de pequenas rotaçõesµ(5◦ ), o que implica que para uma taxa de amostragem de 12.5 Hz o ângulo de rotaçãoé sempre menor que 62.5◦ em cada segundo; trata-se de uma hipótese intuitivamenterazoável.
A proposição seguinte expressa como as variações dos ângulos de compasso, elevaçãoe torção entre imagens consecutivas podem ser limitadas devido ao modelo de pequenas
rotações.
Proposição 2.7 Se o movimento da câmara é consistente com o modelo de pequenas
rotações µ(ξ), então, em qualquer instante k, aplicam-se as seguintes restrições:• A variação do ângulo de elevação, ∆β = βk − βk−1 , satisfaz|∆β| ≤ ξ.

(2.18)• A variação do ângulo de compasso, ∆α = αk − αk−1 , satisfaz´³(
cos |∆β|−cos ξse |βk−1 + βk | ≤ π − ξarccos 1 − cos
βk−1 cos βk|∆α| ≤ aξ (βk , βk−1 ) ≡πcaso contrário.
2(2.19)

11

Se Ok−1 se encontra na região R expressa em (2.16), então, independentemente
de βk e βk−1 :|∆α| ≤

max aξ (βk , βk−1 ) = arccos(2 cos ξ − 1).

|βk−1 |≤ π4(2.20)• A variação do ângulo de torção, ∆γ = γk − γk−1 , satisfaz|∆γ| ≤ gξ (βk−1 ),(2.21)

onde gξ é uma função par crescente em [0, π2 ] com gξ (0) = ξ e gξ ( π2 ) = π. Se
Ok−1 ∈ R, então |βk−1 | ≤ π4 e
³π ´,
(2.22)|∆γ| ≤ gξ
4
A Fig. 2.7 mostra o gráfico da função gξ no subdomı́nio [0, π4 ], para ξ = 5◦ ; este
valor de ξ conduz a |∆γ| ≤ 7.08◦ .
7.5

Variação máxima
do ângulo de torção para ξ = 5°

7
6.5

g (β

) = max |∆γ | [°]

ξ k–1

6
5.5
5

β

k–1

4.5
0

5

10

15

20

25

30

35

40

[°]
45

Figura 2.7: Variação máxima do ângulo de torção como função do ângulo de elevaçãoinicial, utilizando um modelo de pequenas rotações µ(5◦ ).
Demonstração:Considere-se Rk (ρk , ek ) como a composição de duas rotações:(nk−1 × nk ),Rk1 (ρk1 , ek1 ), que transforma nk−1 em nk tendo como eixo de rotação ek1 = ||nk−1 × nk ||seguida de Rk2 (ρk2 , ek2 ) que “torce” a câmara em torno do eixo principal, i.e., com
ek1 = nk . Compondo estas duas rotações, e tendo em conta que ek1 ⊥ek2 , obtém-seρρcos ρ2k = cos k21 cos k22 . Portanto, a condição de pequenas rotações |ρk | ≤ ξ implicaρρtanto cos k21 ≥ cos 2ξ como cos k22 ≥ cos 2ξ , i.e., |ρk1 | ≤ ξ e |ρk2 | ≤ ξ. Uma vez quecos ρk1 = nTk nk−1 , de (2.3) obtém-secos ξ ≤ cos ρk1 = cos βk cos βk−1 cos ∆α + sin βk sin βk−1 ≤ cos ∆β,(2.23)o que basta para provar (2.18). De (2.23), obtém-se aindacos ∆α ≥ (cos ξ − sin βk sin βk−1 )/(cos βk cos βk−1 ) ,o que simplificando conduz a (2.19). Se Ok−1 ∈ R, então de (2.16) vem |βk + βk+1 | ≤π/4 + π/4 + ξ ≤ π − ξ. O valor máximo de ∆α ocorre para βk = βk−1 = π4 , conduzindo
assim a (2.20).

12

Quanto a ∆γ, não é possı́vel chegar a uma expressão simples para gξ (βk−1 ); no
entanto, visto que ρk é função de βk−1 , βk , ∆α e ∆γ, pode estudar-se gξ fazendo
αk−1 = γk−1 = 0. Por simetria esférica tem-se que gξ é uma função par; por outro lado,
uma simples inspecção geométrica mostra que gξ (βk−1 ) aumenta com |βk−1 |. Escrevendo
Rk como a composição de três rotações – uma para o compasso, outra para a elevação e
a última para a torção –, e recorrendo à fórmula para o produto de quaterniões, chega-sea√AB − C B 2 + C 2 − A2,
(2.24)|∆γ| = 2 arccos
B2 + C 2
³
´
∆β
∆β
∆α
onde A = cos ρ2k , B = cos ∆α
cos
e
C
=
sin
cos
sin
β
−
cos
β
sin
∆β
. A
k
k
2
2
2
2
maximização numérica de (2.24) com respeito a ∆α e βk (para ρk = ξ) aproxima gξ .
Se a orientação Ok−1 residir na região R definida em (2.16), o espaço de procura para
Ok é significativamente reduzido graças às restrições impostas pela Proposição 2.7. Em
particular, com ξ = 5◦ , tem-se nestas condições|∆α| ≤ 7.08◦ , |∆β| ≤ 5◦ e |∆γ| ≤ 7.08◦ .

(2.25)

Mesmo se Ok−1 ∈/ R, a Proposição 2.4 garante a existência de uma orientação equiprojectiva O0k−1 ∈ E(Ok−1 ) tal que O0k−1 ∈ R. Isto mostra como se pode utilizar conjuntamenteo modelo de pequenas rotações e as orientações equiprojectivas para reduzir significativamente o espaço de procura.

2.6

Generalização para outros mundos estruturados

Muitos dos resultados obtidos nas secções anteriores, em que sempre se teve em menteo modelo de mundo de Manhattan no espaço tridimensional, são na verdade generalizáveis a outros modelos de mundos, não necessariamente tridimensionais, podendo serempregues para estimar a orientação da câmara em cenários de diferente estrutura ou
para aplicar a problemas de dimensão superior, não necessariamente provenientes daárea de Visão por Computador.
De facto, o mundo de Manhattan pode ser visto como um caso particular de mundo
estruturado, tridimensional, onde a maior parte da informação relevante está “alinhada”
segundo três direcções ortogonais, x, y e z. Ora, este raciocı́nio pode generalizar-se auma classe de mundos estruturados, n-dimensionais, onde estão em jogo m direcçõesnão necessariamente ortogonais, x1 , · · · , xm ∈ Rn , com m ≥ n. Sendo (a1 , · · · , an ) oreferencial do mundo e (b1 , · · · , bn ) um outro referencial, designado por referencial dai=nncâmara, onde {ai }i=ni=0 e {bi }i=0 são duas bases ortonormadas de R , os dois referenciais
relacionam-se por(b1 , · · · , bn ) = (a1 , · · · , an )O,(2.26)
onde O é uma matriz de transformação de coordenadas a que se pode chamar orientação e que pertence ao grupo das matrizes ortogonais, O(n); caso a natureza do
problema exija que esta transformação preserve a orientação dos eixos, i.e., seja uma
rotação, tem-se O ∈ SO(n), onde SO(n) é o sub-grupo de O(n) formado pelas matrizes ortogonais com determinante positivo. Em ambos os casos, utilizando o sistema de coordenadas definido pelo referencial canónico do mundo, i.e., (a1 , · · · , an ) =([0, 0, · · · , 1]T , · · · , [1, 0, · · · , 0]T ), vem O = [b1 , · · · , bn ].
No plano da imagem (um sub-espaço de dimensão n − 1), pode associar-se a cadaum dos pontos de fuga segundo as direcções x1 , · · · , xm respectivamente os vectores de13

coordenadas homogéneas v1 , · · · , vm ∈ Rn ; introduzindo as matrizes n × m definidas
como V = [v1 , · · · , vm ] e X = [x1 , · · · , xm ], tem-se

V = KOT X,(2.27)

onde K é uma matriz invertı́vel do tipo da de (2.15). Aliás, para um mundo de Manhattan
tridimensional tem-se n = 3 e X igual à matriz identidade 3× 3, obtendo-se precisamente(2.15).
O objectivo é estimar a orientação supondo que se dispõe de um mecanismo capazde “sondar” o mundo e obter um conjunto de estimativas para a localização dos pontosbm }. Define-se a relação de equiprojectividade em função das
de fuga, V = {bv1 , · · · , v
direcções x1 , · · · , xm da seguinte forma: duas orientações O e O0 são equiprojectivas sse
os pontos de fuga segundo estas direcções tiverem, no seu conjunto, a mesma localização,ou seja, usando (2.27), sse existirem uma matriz de permutação P e uma matriz diagonal
Λ tais que
KOT X = KO0T XΛP.
(2.28)
Como O, O0 ∈ SO(n), deve ter-se O0 = MO com certo M ∈ SO(n); multiplicando ambos os
termos de (2.28) à esquerda por O0 K−1 e à direita por XT (XXT )−1 O, obtém-se por fim:

M = XΛPXT (XXT )−1∧

M ∈ SO(n),(2.29)o que permite caracterizar a classe de equivalência das orientações equiprojectivas para
qualquer mundo nesta classe de mundos estruturados. Note-se que alargando o domı́nio
da orientação para O(n) (i.e., retirando a exigência de que O seja uma rotação) obtém-se
exactamente os mesmos resultados substituindo SO(n) por O(n).
Exemplo 2.8 Tome-se como exemplo um mundo tridimensional (n = 3) constituı́do
por edifı́cios que são prismas de base hexagonal, i.e., com direcções√definidas pelos
vectores√normalizados de R3 : x1 = [0, 0, 1]T , x2 = [0, 1, 0]T , x3 = [ 3/2, 1/2, 0]T e
x4 = [− 3/2, 1/2, 0]T . Fazendo X = [x1 , x2 , x3 , x4 ] e tendo em conta que a multiplicação
por uma matriz de SO(3) preserva a norma, o que implica Λ = diag(±1, ±1, ±1) obtém-se, utilizando (2.29), o seguinte conjunto de soluções para M:


√
 


0
k1√12 k3 23 0
 ±1 0





3
1
0 ±1 0(2.30)M∈,  k2k4 2
0  ∩ SO(3),
2



0
0 ±1
0
0
±1
com |k1 | = |k2 | = |k3 | = |k4 | = 1 e k1 k2 k3 k4 = −1. Cada classe de equivalência
formada pelas orientações equiprojectivas tem portanto, para este modelo de mundo,
1 3
4
2 (2 + 2 ) = 12 elementos, o que coincide com a ordem do grupo de simetrias do prisma
hexagonal.
Exemplo 2.9 (mundo de Manhattan n-dimensional) Os mundos de Manhattan
n-dimensionais são um caso particular desta classe de mundos estruturados, aqueles
para os quais se tem como “directrizes” n vectores ortonormados de Rn , i.e., para os
quais as direcções x1 , · · · , xn satisfazem, para quaisquer i, j, xTi xj = δij , onde δij representa o delta de Kronecker e portanto a matriz X = [x1 , · · · , xn ] é uma matriz depermutação, fazendo com que (2.29) se reduza a M = ΛP ∧ M ∈ SO(n), o que equivalea M ∈ SP+ (n).
Assim, as classes de equivalência de orientações equiprojectivas, num mundo de
Manhattan n-dimensional, são isomorfas ao grupo SP+ (n) das matrizes de permutação

14com sinal cujo determinante é positivo, tendo por isso 12 2n n! elementos (se se alargar odomı́nio da orientação para O(n), tem-se M ∈ SP(n), onde SP(n) é o grupo das matrizes
de permutação com sinal, que contém SP+ (n) como subgrupo, e tem 2n n! elementos).
Em Rn a orientação tem (n − 1) + (n − 2) + ... + 1 = n(n − 1)/2 graus de liberdade.
Assumindo que o mecanismo consegue obter cada uma das estimativas dos pontos de fugabn } independentemente, é possı́vel obter estimativas de cada linha da matriz de{bv1 , ..., v
orientação ao mesmo tempo que se estima cada um dos pontos de fuga, através de um
procedimento recursivo com n − 1 passos: no primeiro passo, estima-se a localização do
b1 no espaço n-dimensional – isto permite obter o sub-espaço de dimensãoponto de fuga v
b2 nessen − 1 que contém todos os outros pontos de fuga; no segundo passo localiza-se v
sub-espaço obtendo-se um sub-espaço de dimensão n−2 que contém os restantes; e assim
bn−1 e v
bn no espaço unidimensional. Em
por diante até ao último passo onde se estima v
cada um destes sub-espaços de dimensão p é possı́vel obter regiões Rp semelhantes à dabn−p+1 .
Proposição 2.4 onde se garante a existência de um ponto de fuga v

15

Capı́tulo 3

Estimação sequencial daorientação
3.1

Critério de estimaçãoPara estimar a sequência de orientações da câmara, {O1 , . . . , ON }, a partir da sequência
de imagens observadas, {I1 , . . . , IN }, propõe-se uma abordagem probabilı́stica de estimação sequencial, fazendo uso dos modelos de mundo de Manhattan (ver Secção 2.1)
e de pequenas rotações (ver Secção 2.5).
Como vimos atrás, o modelo de mundo de Manhattan assume que os contornos presentes na imagem Ik estão, na sua maioria, “alinhados” com os eixos de Manhattan
x, y e z. Ora, é sabido que o gradiente de intensidade é uma medida da magnitude e
direcção destes contornos, facto que é utilizado em numerosas técnicas de processamento
de imagem. Por conseguinte, pode considerar-se que a estatı́stica do gradiente de intensidade de cada imagem, ∇Ik , transporta informação sobre a correspondente orientaçãoda câmara através de uma função de verosimilhança P (∇Ik |Ok ) (como apontado em[9, 10]). Neste trabalho, esta consideração é tida em conta e adaptada a um modelo deestimação sequencial, utilizando-se um critério de maximum a posteriori (MAP) onde aestimativa da orientação para cada instante k é dada pornobk = arg max P (Ok |∇Ik , O
bk−1 , ..., Ob1 ) =
O
(3.1)
Ok
)
(
bk−1 , ..., Ob1 )P (Ok |O=
(3.2)
= arg max P (∇Ik |Ok )P (∇Ik )Oknobk−1 , ..., Ob1 ) ,= arg max P (∇Ik |Ok )P (Ok |O
(3.3)

Ok

onde de (3.1) para (3.2) se assume que cada ∇Ik depende apenas da orientação Ok nesse
mesmo instante, e não de toda a “história” anterior. Uma estimação sequencial completamente bayesiana requeriria métodos Monte Carlo computacionalmente muito pesados(veja-se [16], [17]). Como alternativa, considera-se este processo como um modelo deMarkov oculto (HMM1 ) que percorre estados {Ok } emitindo sı́mbolos {Ik }, e em que
bk−1 , ..., Ob1 ) = P (Ok |O
bk−1 ). De
cada estado só depende do estado anterior, i.e., P (Ok |O
acordo com esta formalização, e aplicando logaritmos a (3.3), vem então:nobk = arg max log P (∇Ik |Ok ) + log P (Ok |O
bk−1 )
O
(3.4)

Ok

1

Do inglês hidden Markov model.

16

bk−1 ) como uma forma
Analisando (3.4), pode encarar-se a probabilidade a priori P (Ok |Ode penalizar grandes variações entre estimações consecutivas da orientação. Experimentalmente verifica-se que este critério simplificado conduz a bons resultados e, explorando
as potencialidades da “equiprojectividade” e do modelo de pequenas rotações introduzidos atrás, pode ser implementado com vista a funcionar em tempo real. Para a primeira
imagem da sequência, k = 1, utiliza-se
b1 = arg max {log P (∇I1 |O1 )} ,
O
O1

(3.5)

que se obtém de (3.4) suprimindo o segundo termo, por se considerar, na ausência deestimativas anteriores, que todas as orientações são equiprováveis.

3.2

Função de verosimilhança

Nesta secção, para simplificar a notação, omite-se o ı́ndice temporal k e deriva-se a funçãode verosimilhança P (∇I|O) para uma imagem genérica. O método utilizado para obter
a função de verosimilhança é inspirado em [9, 10]; segue-se uma breve descrição.

3.2.1

Gradiente de intensidade

Em todas as imagens considera-se apenas a informação monocromática, i.e., a quantidade total de luz presente em cada pixel. Existem muitos métodos para obter estimativas
do gradiente de intensidade (ver por exemplo [18, 19, 20, 21, 22] ou uma análise comparativa de vários destes métodos em [23]). O que aqui se utiliza, pela sua simplicidade e rapidez computacional, é o método da convolução com máscaras de Sobel. Dada uma imagem
I, elimina-se o ruı́do de alta frequência convoluindo-a com um filtro gaussiano – i.e., umamáscara construı́da com a função gaussiana, G(x, y) = 1/(2πσ 2 ) exp[−(x2 + y 2 )/(2σ 2 )]– obtendo-se uma imagem suavizada Is ; de seguida, o gradiente ∇I = (∇Ix , ∇Iy ) éestimado através das convoluções ∇Ix = Is ∗ Sx e ∇Iy = Is ∗ Sy , onde
−1 0 1
Sx =  −2 0 2  e Sy = −SxT
−1 0 1são as máscaras de Sobel.
Por razões de desempenho computacional, são rejeitados todos os pixels cuja informação se considera inútil; tais são:• Os pixels próximos de contornos mas para os quais existem vizinhos cujo gradienteé, em módulo, superior. Este critério de rejeição é também utilizado no algoritmo
de detecção de contornos de Canny (ver [20]) com o intuito de obter contornos
com a espessura média de 1 pixel. Designa-se na literatura anglo-saxónica por
non-maxima supression.
• Os pixels cujo gradiente, em módulo, está abaixo de um determinado limiar, o que
garante que não pertencem a contornos; este critério designa-se por limiarização.
Nas experiências efectuadas, a aplicação destes critérios de rejeição permitiu eliminar
cerca de 80% dos pixels da imagem.

173.2.2

Classes de pixel

Cada pixel da imagem, u = [u, v, 1]T , que não tenha sido rejeitado na etapa anterior,pode ser associado a uma classe mu ∈ {1, 2, 3, 4, 5}. As classes são definidas da seguinte
forma: as classes 1, 2 e 3 referem-se a pixels de contornos alinhados com um dos eixos
de Manhattan, x, y e z respectivamente. A classe 4 abrange os pixels que pertencem acontornos não alinhados com qualquer daqueles eixos. Finalmente, a classe 5 inclui os
pixels que não pertencem a contornos. Estas classes distribuem-se com probabilidades apriori {Pm (mu )}, obtidas off-line através de um detector de contornos binário e fixando
heuristicamente Pm (1) = Pm (2) = Pm (3) = 0, 5 × Pm (4). A Figura 3.1 e a Tabela 3.1
ilustram cada uma das classes de pixel.

5

2

1

3

4

Figura 3.1: Classes de pixel para uma fotografia da Rua Augusta, na Baixa Pombalina,
em Lisboa.

mu
1
2
3
4
5

DescriçãoPixel de um contorno alinhado com x
Pixel de um contorno alinhado com y
Pixel de um contorno alinhado com z
Pixel de um contorno não alinhado com x, y ou z
Pixel não pertencente a qualquer contorno

Pm (mu )
0,138
0,138
0,138
0,276
0,309

Tabela 3.1: Classes de pixel.

3.2.3

Funções de probabilidade da magnitude do gradiente

Seja Eu = (Eu , φu ) a representação polar do gradiente da intensidade da imagem∇I no pixel u, onde Eu = Q[(∇I2x (u) + ∇I2y (u))1/2 ] ∈ {1, ..., N } é a magnitude
do gradiente quantificada por uma função Q com N nı́veis de quantificação, e φu =arctan(∇Iy (u)/∇Ix (u)) é a direcção do gradiente. A magnitude e a direcção do gradiente são condicionalmente independentes, dada a classe do pixel. Naturalmente, a magnitude do gradiente é também condicionalmente independente da orientação da câmarae da localização do pixel. Logo,
P (Eu |mu , O, u) = P (Eu |mu ) P (φu |mu , O, u),
onde½
P (Eu |mu ) =Pon (Eu ) , se mu 6= 5
Poff (Eu ) , se mu = 5,

(3.6)
(3.7)

e Pon (Eu ) e Poff (Eu ) são as funções de probabilidade da magnitude do gradiente quantificado, condicionadas ao evento de o pixel u pertencer (on) ou não (off ) a um contorno,18respectivamente. Estas probabilidades são, também elas, obtidas através de um processo
de treino que decorre off-line, em que se utiliza um detector de contornos binário. Os
seus valores (para uma quantificação logarı́tmica e N = 20) encontram-se representadosna Figura 3.2.
0.2
0.18

0.3

Pon (Eu )

0.25

0.14
0.12

0.2

0.1

0.15

0.08

0.1

0.06
0.04

0.05
0

Poff (Eu )

0.16

0.02
2

4

6

8

0

10 12 14 16 18 20

2

4

6

8

10 12 14 16 18 20

Figura 3.2: Histogramas das funções Pon e Poff . No caso de Pon , como seria de esperar,a probabilidade de se ter valores elevados para a magnitude do gradiente em pixels decontornos é muito maior do que a probabilidade de se ter valores reduzidos.

3.2.4

Funções de probabilidade da direcção do gradiente

Sejam θx (O, u), θy (O, u) e θz (O, u) as direcções do gradiente idealmente observado no
pixel u se mu = 1, 2 e 3, respectivamente. Estas direcções obtêm-se directamente dos
pontos de fuga, dados em função de O por (2.14). A função de probabilidade da direcçãodo gradiente éPang (φu − θx (O, u)) se mu = 1Pang (φu − θy (O, u)) se mu = 2(3.8)
P (φu |mu , O, u) =Pang (φu − θz (O, u)) se mu = 3U (φu )
se mu ∈ {4, 5},onde U (·) é a função densidade de probabilidade uniforme em ] − π2 , π2 ] e Pang é modelizada como uma função “caixa”, i.e.,½(1 − ²)/(2τ ) se t ∈ [−τ, τ ]Pang (t) =²/(π − 2τ )se t ∈ ] − π/2, −τ [ ∪ ]τ, π/2].
Nas experiências efectuadas, estes parâmetros foram afinados para ² = 0.1 e τ = 4◦ (verFigura 3.3).

3.2.5

Função de verosimilhançaFinalmente, a verosimilhança conjunta é obtida de (3.6) marginalizando (i.e., somando)
sobre todos os possı́veis modelos em cada pixel e assumindo independência entre pixels
diferentes:
P (∇I|O) = P ({Eu } |O) =5
Y X

P (Eu |mu ) P (φu |mu , O, u) P (mu ) .

(3.9)

u mu =1

Aplicando logaritmos,
log P (∇I|O) =

X
u

(
log

5
X

)
P (Eu |mu ) P (φu |mu , O, u) P (mu ) .

mu =1

19

(3.10)

Pang

0.1125-4

5.81 x 10
– 90º

– 4º

4º

90º

εu

Figura 3.3: Gráfico da função Pang , a densidade de probabilidade de erro na estimaçãoda direcção do contorno a partir da direcção do gradiente. Naturalmente a densidade émaior para erros pequenos. Por simplicidade e vantagem computacional, é modelizada
como uma “caixa”, onde τ controla a precisão da estimativa e ² é a probabilidade de secometer um erro superior a τ .

3.3

Procedimento de localização das estimativas

Como se descreveu atrás, a maximização expressa em (3.4) permite estimar a orientaçãoda câmara para cada imagem da sequência de vı́deo. O segundo termo desta expressão,bk−1 ), pode ser descrito através de uma função definida a priori ; o primeirolog P (Ok |O
termo é a função de verosimilhança descrita em (3.10). Esta maximização é um problema
de optimização tridimensional em ordem a α, β e γ, que pode ser resolvida por um algoritmo de procura exaustiva nos intervalos de variação destes ângulos, com complexidadeO(N 3 ), onde N descreve a frequência de amostragem daqueles intervalos.
Neste trabalho, propõe-se uma solução aproximada que separa o problema em dois
passos mais simples: uma optimização bidimensional em ordem a β e γ, seguida por
uma procura unidimensional em ordem a α. A complexidade do algoritmo de procura
exaustiva correspondente a estas duas optimizações sucessivas é O(N 2 + N ) = O(N 2 ).
Esta aproximação advém do facto de o ponto de fuga vz ser independente do ângulo decompasso α, como é claro de (2.12).

3.3.1

1.◦ passo: Estimação de β e γDada a k-ésima imagem Ik , com k > 1, procede-se, como primeiro passo, à estimaçãode βk e γk , de acordo com³´noβbk , γbk = arg max log P (∇Ik |β, γ) + log P (β, γ|βbk−1 , γbk−1 ) ,(3.11)
β,γonde a verosimilhança log P (∇Ik |β, γ) é uma versão de (3.10) que apenas modeliza a
informação de direcção dos contornos que são consistentes com o eixo z. Mais especificamente, em vez de (3.8), utiliza-se aqui½Pang (φu − θz (β, γ, u)) se mu = 3
P (φu |mu , β, γ, u) =(3.12)U (φu )
se mu ∈ {1, 2, 4, 5}.
Note-se que a utilização de uma distribuição uniforme é apenas uma forma de ignorar a
informação de direcção do gradiente vinda de todos os pixels excepto daqueles que estãoassociados com o eixo z (i.e., com classe mu = 3) durante a estimação de βk e γk ; talnão significa que aquelas direcções sejam de facto uniformemente distribuı́das.
O segundo termo de (3.11) faz intervir P (β, γ|βbk−1 , γbk−1 ), uma função densidadede probabilidade (f.d.p.) em duas variáveis que se modeliza como sendo gaussiana e

20

“truncada” na região de interesse, i.e.:½
λG(β, γ), se (β, γ) ∈ Iβ × Iγb
P (β, γ|βk−1 , γbk−1 ) =,0c.c.

(3.13)onde:• G(β, γ) é a f.d.p. gaussiana em duas variáveis com valores médios (µβ , µγ ) =(βbk−1 , γbk−1 ) e variâncias (σβ2 , σγ2 );• Iβ =]βbk−1−ξ, βbk−1 +ξ] é o intervalo de variação do ângulo de elevação nas condições
do modelo de pequenas rotações µ(ξ), expresso em (2.18);• Iγ =]bγk−1−gξ (βbk−1 ), γ
bk−1 +gξ (βbk−1 )] é o intervalo de variação do ângulo de torçãonas mesmas condições, expresso em (2.21);R• λ é determinado de modo a ter-se Iβ ×Iγ P (β, γ|βbk−1 , γbk−1 )dβdγ = 1.
A função (3.13) é definida a priori e formaliza o modelo de pequenas rotações, bemcomo a suavidade na variação de βk e γk . As variâncias σβ2 e σγ2 afinam o compromisso
entre a suavidade da sequência estimada de ângulos e a precisão dessas estimativas.
Na primeira imagem da sequência, k = 1, define-se a priori P (β, γ) como uniforme(i.e., constante) no domı́nio dado por (2.16), Iβ × Iγ = ]−45◦ , 45◦ ] × ]−54.7◦ , 54.7◦ ], peloque em vez de (3.11) usa-se:³´
βb1 , γb1 = arg max log P (∇I1 |β, γ).
(3.14)
β,γ3.3.2

2.◦ passo: Estimação de α

Dadas as estimativas βbk e γ
bk , pode estimar-se o ângulo de compasso αk utilizandonoαbk = arg max log P (∇Ik |α, βbk , γbk ) + log P (α|bαk−1 , βbk−1 , βbk ) ,(3.15)αonde a verosimilhança log P (∇Ik |α, βbk , γbk ) é dada directamente por (3.10) e a função abbpriori P (α|bαk−1 , βk−1 , βk ) é também uma f.d.p. gaussiana “truncada”:½
λG(α), se α ∈ Iα
P (α|bαk−1 , βbk−1 , βbk ) =,(3.16)0c.c.
onde:• G(α) é a f.d.p. gaussiana com valor médio µα = αbk−1 e variância σα2 ;• Iα =]bαk−1−aξ (βbk , βbk−1 ), αbk−1 +aξ (βbk , βbk−1 )] é o intervalo de variação do ângulo decompasso nas condições do modelo de pequenas rotações µ(ξ), expresso em (2.19);
R• λ é determinado de modo a ter-se Iα P (α|bαk−1 , βbk−1 , βbk )dα = 1.
Também aqui a variância σα2 afina o compromisso entre a suavidade da sequência estimada de ângulos e a precisão dessas estimativas.
Para a primeira imagem, k = 1, define-se P (α) como uniforme em todo o domı́nio
dado por (2.16), Iα = ]−45◦ , 45◦ ], usando-se portanto em vez de (3.15)
αb1 = arg max log P (∇I1 |α, βb1 , γ
b1 ).
α

21

(3.17)

3.3.3

Localização das estimativas

Com base nas considerações estabelecidas acima, o algoritmo de estimação da orientaçãopode ser formalizado como se segue.
Algoritmo 3.1 Objectivo: Dada uma sequência de imagens {I1 , . . . , IN } de um
mundo de Manhattan, estimar a correspondente sequência de orientações da câmara,{O1 , . . . , ON }.
• Para cada imagem Ik da sequência de vı́deo:
1. Calcula-se o gradiente ∇Ik ;2. Através de non maxima supression e limiarização, selecciona-se os pixels {u}que contêm informação relevante, obtendo-se {Eu } = {(Eu , φu )};3. Estima-se βbk e γ
bk pelo método de procura exaustiva. Se k = 1, usa-se (3.14)

com o espaço de procura Iβ × Iγ = ]−45◦ , 45◦ ] × ]−54.7◦ , 54.7◦ ], graças a(2.16); se k > 1, usa-se (3.11) e o espaço de procura tem em conta as
estimativas anteriores, sendo para um modelo de pequenas rotações µ(5◦ ):Iβ × Iγ =]βbk−1 − 5◦ , βbk−1 + 5◦ ]×]b
γk−1 − 7.08◦ , γ
bk−1 + 7.08◦ ], conforme (2.25).

4. Estima-se α
bk pelo método de procura exaustiva. Se k = 1, usa-se (3.17) com
o espaço de procura Iα = ]−45◦ , 45◦ ]; se k > 1, usa-se (3.15) e o espaço deprocura tem em conta as estimativas anteriores, sendo para o mesmo modeloµ(5◦ ): Iα =]b
αk−1 − 7.08◦ , αbk−1 + 7.08◦ ].
bk ) das orientações equiprojectivas com
5. Obtém-se a classe de equivalência E(Obbbk ) uma
Ok = O(bαk , βk , γbk )), recorrendo à Proposição 2.3. Escolhe-se em E(O0bk := O0 .
orientação Ok ∈ R, cuja existência é garantida por (2.16). Faz-se O
kComo foi dito no último parágrafo da Secção 2.5, isto permite manter pequenos espaços de procura na próxima iteração dos passos 3 e 4.
b1 , . . . , O
bN } a que se associam• Como passo final, parte-se da sequência obtida, {Obbbk ) uma oriclasses de equivalência {E(O1 ), . . . , E(ON )} e selecciona-se em cada E(O000entação Ok tal que a sequência {O1 , . . . , ON } satisfaça, em cada instante k, o mob1 , . . . , O
bN } := {O01 , . . . , O0 }.
delo das pequenas rotações. Faz-se então {ON

3.4

Hipótese nula e classificação de contornos

Tal como referido em [9, 10], a estimação da orientação a partir de uma imagem permite
a posteriori:(i) Verificar a validade do modelo de mundo de Manhattan para a imagem dada;(ii) Classificar cada pixel da imagem de acordo com as classes {1, . . . , 5} definidas na
Tabela 3.1.
Em (i), o objectivo é evitar estimativas erradas testando estatisticamente a hipótese domundo de Manhattan; este teste permite detectar quando uma imagem se afasta destemodelo e, nessa eventualidade, abster-se de estimar a orientação.
Neste trabalho, em que a estimação é sequencial, esta verificação tem ainda a mais-valia de permitir detectar perdas de sincronismo no modelo de pequenas rotações, i.e.,situações em que devido à estimação errada de várias orientações consecutivas, a dependência do modelo das estimativas anteriores coloca-o “à deriva”. Uma vez detectadas, estas situações podem ser corrigidas forçando a estimação seguinte a decorrer

22independentemente da estimativa anterior, i.e., como se fosse a primeira imagem deuma nova sequência.
A verificação da validade do modelo de mundo de Manhattan é feita construindo um
modelo de hipótese nula, o que é feito modificando (3.8) para P (φu |mu , O, u) = U (φu )e calculando
"Ã 4
!
#
Y
X
Pm (mu ) · Pon (Eu ) + Pm (5) · Poff (Eu ) U (φu ) , (3.18)
Pnull ({Eu }) =
u

mu =1

o que significa deixar de distinguir diferentes tipos de contorno e deixar de assumir
que a estatı́stica da imagem reflecte qualquer tipo de estrutura tridimensional. A verosimilhança do modelo de hipótese nula é comparada com a do modelo de mundo de
Manhattan, que é aproximada porb)P (Ob).
Pmanh ({Eu }) ≈ P ({Eu } |O

(3.19)b é a orientação estimada. Se log P
onde O
manh ({Eu }) − log Pnull ({Eu }) < δ para um
certo δ ≥ 0 escolhido como margem de confiança, decide-se que o modelo de mundo deb.
Manhattan não é suficientemente verosı́mil e descarta-se O
Em (ii), o objectivo é classificar a posteriori os pixels da imagem com os valores
1, . . . , 5, o que é feito tomando (3.6) e fazendo:mb u = arg max P (Eu |mu ) P (φu |mu , O, u).
mu(3.20)

A classificação dos pixels pode ser levada a cabo com o objectivo de captar a geometria domundo de Manhattan: um procedimento possı́vel é agrupar os pixels classificados como
1, 2 e 3 em linhas com a direcção dos eixos de Manhattan e computar as intersecções
destas linhas, permitindo a sua reconstrução 3D por troços a menos de escalamentos.
Apesar de este procedimento poder ser efectuado utilizando apenas uma imagem, ouso de uma sequência de vı́deo permite refinar a reconstrução das linhas através, por
exemplo, de restrições de proximidade baseadas no modelo de pequenas rotações. Podeainda estabelecer-se correspondências com estas linhas entre as várias imagens, a fim deestimar a translação da câmara e combinar com a orientação já estimada para obter apose completa (posição e orientação) a menos de um escalamento. Por outro lado, os
pixels que forem classificados com mb u = 4 pertencem a contornos não consistentes com
os eixos de Manhattan; estes podem ser utilizados para detectar objectos não alinhadoscom esta estrutura (e.g., pessoas num ambiente urbano), o que tem especial interesseem aplicações envolvendo reconhecimento de padrões.

3.5

Experiências e Resultados

A fim de avaliar a qualidade do método proposto, aplicou-se o Algoritmo 3.1 a um
conjunto de sequências de vı́deo adquiridas na Baixa Pombalina com uma câmara vulgar,
em movimento livre e sem nenhum cuidado especial para evitar vibrações e outros efeitos
indesejáveis. As sequências de vı́deo utilizadas apresentam uma resolução baixa (cadaimagem tem 288 × 360 pixels) e uma grande compressão (formato MPEG-4). Apesar
da pouca qualidade das sequências, algumas contendo imagens sub- ou sobre-expostas
devido a fortes contrastes luz/sombra, e à distorção radial que afasta a câmara do modelo
da “câmara escura”, concluiu-se que o Algoritmo 3.1 é capaz de estimar correctamentea orientação da câmara, de que é exemplo a Figura 3.4.

23

Figura 3.4: Estimativas da orientação da câmara para uma sequência na Rua da Prata,
em Lisboa. Os cubos sobrepostos nas imagens representam a orientação estimada paraos eixos de Manhattan. Representa-se a estimativa na primeira imagem da sequência(k = 1) e para imagens seguintes, em intervalos regulares.
As imagens das Figuras 3.5 e 3.6 provêm de duas outras sequências. Note-se que
em ambos os casos a orientação é correctamente estimada, mesmo na presença demuitos contornos não alinhados com os eixos de Manhattan (por exemplo, as pessoas
na Figura 3.6). Os gráficos em cada uma destas figuras representam as estimativas dos
ângulos que parametrizam a orientação (i.e., os ângulos de compasso, elevação e torção)para as duas sequências. Observando o gráfico, pode ver-se que as estimativas para asequência da Figura 3.6 são um pouco mais ruidosas que as da Figura 3.5, o que se deveà qualidade inferior das imagens. A suavidade destas estimativas é controlada pelas
variâncias postas em jogo nas f.d.p. (3.13) e (3.16), e que são escolhidas a priori ; nas
experiências realizadas, essas variâncias são iguais para os três ângulos e para ambas assequências. Naturalmente, existe um compromisso entre esta suavidade e a capacidadede captar com precisão rotações mais bruscas da câmara.

α
β
γ

40

Graus

20
0

–20
0

20

40
60
Índice da imagem

80

Figura 3.5: Esquerda: imagens 20, 30, 40 e 50 de outra sequência de vı́deo, no Teatro
D. Maria II, em Lisboa. Direita: gráfico temporal com as estimativas dos ângulos decompasso, elevação e torção que parametrizam a orientação da câmara.

24

ture estimation. IEEE TPAMI, 15(9):864–884, 1993.

Fig. 3. Frames 20, 30, 40, and 50 of a video sequence with superimposed cubes representing the estimated orientation of the MW
axes.

[6] R. Szeliski and S. Kang. Recovering 3D shape and motion
from image streams using nonlinear least squares. Jounal of
Visual Comm. and Image Representation, 5(1), 1994.

[7] A. Azarbayejani and A. Pentland. Recursive estimation of
motion, structure, and focal length. IEEE TPAMI, 17(6),1995.

[8] S. Soatto, P. Perona, R. Frezza, and G. Picci. Recursive motion and structure estimations with complete error characterization. In Proc. of IEEE CVPR, pages 428–433, 1993.

[9] J. Thomas, A. Hansen, and J. Oliensis. Understanding noise:αThe critical role of motion error in scene reconstruction. In
βProc. of IEEE ICCV, pages 325–329, 1993.

80[10] γC. Tomasi and T. Kanade. Shape and motion from image
streams under orthography: a factorization method. Int. Jour40
nal of Computer Vision, 9(2), 1992.

Graus

60

20
0

[11] P. Sturm and B. Triggs. A factorization based algorithm for
multi-image projective structure and motion. In European
Conference on Computer Vision, Cambridge, UK, 1996.

[12] L. Quan and T. Kanade. A factorization method for affine
structurefrom line
50
100
150 correspondences.
200
250 In Proc. of IEEE CVPR,Índice da CA,
imagemSan Francisco,USA, 1996.

0[13] P.
Aguiar and
J. Moura.de
Three-dimensionalmodeling from
Figura 3.6: Esquerda: imagens 110, 130, 150 e 170 de uma
terceirasequência
vı́deo,Fig. 4. As in Fig. 3, for frames 110, 130, 150, and 170 of anothertwo-dimensional
video.
IEEE Trans. on Image Processing,noElevadordeSanta
Justa,
em
Lisboa.
Direita:gráfico
temporalcom
asestimativas
vide sequence.
10(10):1541–1551, 2001.

dos ângulos de compasso, elevação e torção que parametrizam a orientação da câmara.

[14] B. Horn and E. Weldon Jr. Direct methods for recovering
motion. Int. Journal of Computer Vision, 2(1):51–76, 1988.

[15] G. P. Stein and A. Shashua. Model-based brightness con-0
A Figura 3.7 ilustra ainda
dois exemplos de classificaçãode contornos, segundo ostraints: On direct estimation of structure and motion. IEEE
−20
métododescrito na Secção 3.4; um para uma imagem interior
e outropara uma 2000.
imagem0
TPAMI,
22(9):992–1015,
exterior. Pode ver-se que −40
a classificação é mais ruidosa[16]no J.casodaimagemexterior,
o world: Compass diCoughlan and A. Yuille. Manhattan−20
que é representativo das restantes experiências efectuadas. rection from a single image by Bayesian inference. In IEEE
−60
ICCV,
Corfu, Greece,
1999. que−40
O αβtempo de processamentoαβ tı́pico para cada imagem dassequênciasé menor−80γγ[17] J.processador
Coughlan and Pentium
A. Yuille. The
world assump1 −60segundo,
tendo os testes sido
efectuados num PC com
IV manhattan
a
0
20
40
60
80
0
50
100
150
200
250
tion: Regularities in scene statistics which enable Bayesian
Frame number
Frame number
3.0 GHz e a implementação do algoritmo no programa MATLAB,
sem utilizar código
inference. In NIPS, Denver CO, USA, 2000.
pré-compilado.
Neste
momento,oalgoritmo
está
a
ser
implementado
em C/C++ com
Fig. 5. Camera angle estimates, for the sequences of Figs. 3 and 4.
[18] A. Martins, P. Aguiar, and M. Figueiredo. Equivalenceo objectivo de ser utilizado em tempo real.
classes for camera orientation. Submitted for publication.
Degrees

Degrees20

Figura 3.7: Exemplos de classificação de contornos para uma imagem interior e outra
exterior. Representa-se respectivamente a vermelho, verde e azul pixels de contornos
alinhados com os eixos de Manhattan x, y e z. Esquerda: Sala de aula. Direita: Praçada Figueira, Baixa Pombalina, Lisboa.

25

Capı́tulo 4

Conclusão
Neste trabalho, propõe-se uma abordagem probabilı́stica para estimar a orientação dacâmara a partir de sequências de vı́deo em cenários urbanos. A abordagem utilizada
tira partido da existência de “regularidades” nos contornos da imagem, o que é expresso
através do modelo de mundo de Manhattan. O método proposto evita os passos intermédios tradicionalmente empregues, como a detecção e correspondência automáticade padrões (cantos ou linhas de contorno), que por serem pouco robustos e computacionalmente pesados limitam o seu uso em aplicações práticas.
Os resultados experimentais demonstram que este método é capaz de lidar correctamente com sequências de vı́deo de baixa qualidade e baixa resolução, ainda que oambiente em causa se afaste razoavelmente do modelo de mundo de Manhattan, devidoà presença de muitos contornos “espúrios”. O algoritmo que aqui se introduz reduz acomplexidade do problema e possibilita obter tempos de processamento que viabilizam
o seu uso num sistema que funcione em tempo real.
As considerações teóricas introduzidas neste trabalho mostram como se pode tirar
partido das classes de equivalência de orientações equiprojectivas para reduzir o domı́nio
de procura da solução. Generaliza-se este conceito para uma classe genérica de mundos
estruturados, n-dimensionais, de que o modelo de mundo de Manhattan tridimensional é
um caso particular. Mostra-se como o mesmo conceito pode ser útil ao desenvolvimentode algoritmos de estimação em que existe conhecimento a priori da estrutura dos dados,
independentemente da dimensão do espaço e do âmbito do problema, não se exigindo
que este esteja relacionado com Visão por Computador.
Desenvolvimentos futuros incluem:• optimização do algoritmo com vista à implementação prática de um sistema protótipo de estimação da orientação 3D em tempo real (trabalho corrente);• desenvolvimento de métodos para estimar adicionalmente a posição 3D da câmara(dada a sua orientação) no sentido de obter uma calibração completa e permitirreconstruir a trajectória e efectuar uma reconstrução 3D do mundo;• investigação do problema de detectar automaticamente a “estrutura” do mundo,
nos casos em que não existe conhecimento prévio desta estrutura;• avaliação da possibilidade de estender o método a problemas provindos de outrasáreas, nomeadamente em Aprendizagem, Regressão e Classificação Automática,
com possı́veis aplicações em Inteligência Artificial, Bioinformática e Processamentode Lı́ngua Natural.

26

Bibliografia[1] O. Faugeras. Three-Dimensional Computer Vision. MIT Press, Cambridge, MA,
1993.
[2] R. Hartley and A. Zisserman. Multiple View Geometry. Cambridge University
Press, 2000.
[3] J. Mundy and A. Zisserman, editors. Geometric Invariants in Computer Vision.
MIT Press, Cambridge, MA, 1992.
[4] E. Lutton, H. Maı̂tre, and J. Lopez-Krahe. Contribution to the determination ofvanishing points using Hough transform. IEEE Trans. on PAMI, 16(4):430–438,
1994.
[5] S. Utcke. Grouping based on projective geometry constraints and uncertainty.
In Proc. IEEE Int. Conf. on Computer Vision, Bombay, India, 1998.
[6] J. Kosecka and W. Zhang. Video compass. In European Conf. on Comp. Vision,
Springer Verlag, LNCS 2350, 2002.
[7] B. Horn and E. Weldon Jr. Direct methods for recovering motion. Int. Jour.
Computer Vision, 2(1):51–76, 1988.
[8] G. P. Stein and A. Shashua. Model-based brightness constraints: On direct
estimation of structure and motion. IEEE Trans. on PAMI, 22(9):992–1015,
2000.
[9] J. Coughlan and A. Yuille. Manhattan world: Compass direction from a single
image by Bayesian inference. In Proc. IEEE Int. Conf. on Computer Vision,
Corfu, Greece, 1999.
[10] J. Coughlan and A. Yuille. The Manhattan world assumption: Regularities inscene statistics which enable Bayesian inference. In Proc. Neural Information
Processing Systems, Denver, CO, USA, 2000.
[11] J. Deutscher, M. Isard, and J. MacCormick. Automatic camera calibration from asingle Manhattan image. In Proc. European Conf. on Computer Vision, Springer
Verlag, LNCS 2350, 2002.
[12] G. Schindler and F. Dellaert. Atlanta world: An expectation-maximization
framework for simultaneous low-level edge grouping and camera calibration incomplex man-made environments. In Proc. IEEE Comp. Soc. Conf. on Computer Vision and Pattern Recognition, Washington, DC, 2004.
[13] Jean-Yves Bouguet.
Camera Calibration(http://www.vision.caltech.edu/bouguetj/calib doc)

27

ToolboxforMatlab.

[14] Zhengyou Zhang. Flexible Camera Calibration by Viewing a Plane from Unknown
Orientations. In Proc. IEEE Int. Conf. on Computer Vision, Kerkyra, Greece,
1999.
[15] I. Herman. The Use of Projective Geometry in Computer Graphics. Lecture
Notes in Computer Science, Springer-Verlag, Amesterdam, Netherlands, 1992.
[16] N. Gordon A. Doucet, N. Freitas. Sequential Monte Carlo Methods in Practice.
Springer-Verlag, New York, 2001.
[17] M. Isard and A. Blake. CONDENSATION – conditional density propagation forvisual tracking. Int. Jour. of Computer Vision, 29(3):5–28, 1998.
[18] E.C. Hildreth Implementation of a theory of edge detection. M.I.T. Artificial
Intell. Lab., Cambridge, MA, Tech. Rep. AITR579, 1980.
[19] R.M. Haralick Digital step edges from zero crossing of second directional derivatives. In IEEE Trans. on Pattern Analysis and Machine Intelligence, 1984.
[20] J.F. Canny. A computational approach to edge detection. In IEEE Trans. on
Pattern Analysis and Machine Intelligence, November 1986.
[21] R.C. Gonzalez, R.E. Woods Digital image processing. AddisonWesley Publishing
Company, Inc, 1993.
[22] S.M. Smith and J.M. Brady. SUSAN - A New Approach to Low Level Image
Processing. Department of Engineering Science, Oxford University, Oxford, UK,1995 (http://www.fmrib.ox.ac.uk/˜steve/susan/susan/susan.html)[23] M. Heath, S. Sarkar, T. Sanocki, K.W. Bowyer A Robust Visual Method for Assessing the Relative Performance of Edge-Detection Algorithms. In IEEE Trans.
on Pattern Analysis and Machine Intelligence, December 1997.

28