Visão Computacional
Visão Estéreo
http://www.dca.ufrn.br/~lmarcos/courses/visao
Shape from stereo
•
•
•
•
Duas ou mais imagens da mesma cena
Tomadas de pontos de vista diferentes
Percepção da 3a dimensão
Inversão de projeção por triangulação
determinando a 3a dimensão
Estéreo x Motion
Random Dot Stereograms
• http://www.nottingham.ac.uk/~etzpc/sirds.ht
ml
• http://www.nottingham.ac.uk/~etzpc/sirds.ht
ml
Princípio básico da reconstrução
estéreo (triângulos)
Objeto
Olho
esquerdo
Olho
direito
Projeção (transformações)
• Objetos guardam relações com mundo real
• Rotação, translação e escala (corpo rígido)
• Determinar pontos correspondentes nas
imagens usando estas restrições
• Tendo as câmeras calibradas em relação ao
sistema de mundo, sabendo-se a distância
entre as câmeras, pode-se determinar o
triângulo e a 3a dimensão
Modelo estéreo
P(x,y, z)
y
(xl,yl)
f
f
(0,0,0)
O
xr ,xr
(b,0,0)
b
x
P(x,
y, z)
y
Premissas
•
•
•
•
•
•
•
(xl, xr
yl) ,xr
f
f
O (0,0,0)b (b,0,0)
(x,y,z) = coordenadas de um ponto no espaço
Origem imagem esquerda (xl, yl) em (0, 0, f)
Ponto focal esquerdo em (0, 0, 0)
Imagem direita (xr, yr) com origem em (b, 0, f)
Ponto focal esquerdo em (0,0,0), direito em (b,0,0)
b = linha de base
f = distância focal (dos centros óticos aos planos
imagens)
x
Projetando no plano
x
x-b
xl = x
f z
z
xr
=
f
xl
xr
f
b
x-b
z
xl =
xr =
fx
z
f (x-b)
z
Deslocamento em y=0
(x,y,z)
y
yl
yr
xl
xr
f
yr yl y
= =
f f z
f
O
b
b
Figura 2.1 - Modelo estéreo
x
yl = yr =
fy
z
xl =
Disparidade estéreo
xr =
• Manipulando as equações:
xl - xr = fx - f (x-b) = fx - fx +
z
• Definindo d
fx
z
f (x-b)
fb
fb
=
z
z
z
z
z
bf
z=
l
r
d
fx
fy
=
nas equações xl z e yl = z
=x -x
• Substituindo z
bxl
• achamos finalmente x =
d
e
byl
y=
d
z
Generalizando (movendo origem)
(-d,0,0)
(0,0,0)
(d,0,0)
Calculando a disparidade
b
d
Observações
• z é inversamente proporcional a d
• z é diretamente proporcional a b
• fixado um erro na determinação de d:
– precisão na determinação de z cresce de forma
direta com b.
– com o crescimento de b, imagens tendem a ser
muito diferentes uma da outra
– ponto visível numa imagem pode não ser
noutra, mesmo com vergência
Mais observações
• d é proporcional à distância focal f
• à medida que f aumenta, imagens também
• aumenta a distância do ponto projetado nas
imagens ao centro destas e em conseqüência
a disparidade
• no modelo ideal:
– pontos próximos disparidade grande
– pontos longe disparidade pequena
– ponto no infinito disparidade zero
Observações
• Modelo com vergência:
– Pontos no horópter: disparidade zero
– Pontos mais próximos que o horópter: disparidade
positiva
– Pontos mais longe que o horópter: disparidade negativa
• Bom sinal, daria para manter um robô a uma certa
distância de uma pessoa usando apenas
disparidade
Horopter
Determinando altura dos pontos
di = di - d 0
h0
hi =
d i
d0  di
di = xri - xli
d 0 = xr 0 - xl 0
Para pequenos valores de h (terrenos planos):
h0
hi = d i
d0
h0
h1
h0
hi = h0 
di
d 0  di
h2
hi
Restrição epipolar
• Verifica-se no sistema ideal apresentado que
as imagem yl e yr são a mesma e definem
uma reta paralela ao eixo x denominada
linha epipolar
• Para eixos óticos não paralelos, as projeções
de um ponto localizam-se em linhas dadas
pela interseção entre cada plano imagem e o
plano formado pelos dois centros óticos
(epipolos) mais o ponto objeto considerado
• Linhas epipolares
Restrição epipolar
P
Dl
S'l
Dr
Sl
Sr
b
P'l
P'r
D'l
D'r
S'r
P
Dl
Restrição epipolar
S'l
D
r
Sl
Sr
b
P'l
S'r
P'r
D'l
D'r
• Supondo a orientação relativa entre os dois sistemas
conhecida (visto a seguir)
• A projeção de um ponto (xl, yl) na imagem esquerda é
um raio que passa pela origem da imagem esquerda
• As coordenadas de um ponto qualquer situado neste
raio, referenciadas ao sistema esquerdo podem ser
expressas por:
x = x s ,
y = y s , z = f s
Restrição epipolar
• No sistema direito, as coordenadas desse
mesmo
ponto
no
raio
projetivo
correspondente são:
x = (r x   r y  r f )s  r
y = (r x   r y  r f )s  r
z = (r y  r y  r f )s  r
Restrição epipolar
• Assumindo que a distância focal nos dois
sistemas é a mesma, as seguintes equações
de projeção podem ser estabelecidas para o
sistema direito:
xr xr
=
f
zr
e
yr yr
=
f
zr
x = (r x   r y  r f )s  r
y = (r x   r y  r f )s  r
z = (r y  r y  r f )s  r
Restrição epipolar
• Usando as abreviações
xr = as  u, yr = bs  v e zr = cs  w
temos as equações anteriores dadas por
xr a cu - aw 1
= 
f
c
c
cs  w
yr b cv - bw 1
= 
f
c
c
cs  w
que representam uma reta pelo ponto (u/w, v/w),
quando s = 0, e por (a/c , b/c), quando s = .
Restrição epipolar
• O primeiro destes pontos S  é a imagem do ponto
nodal (focal) da câmera esquerda no plano da imagem
direita e o segundo é a imagem P  do ponto acima
considerado também na imagem direita.
P
Dl
S'l
D
r
Sl
Sr
b
P'l
P'r
D'l
D'r
S'r
Restrição epipolar
P
Dl
S'l
Dr
Sl
Sr
b
P'l
P'r
D'l
D'r
S'r
Generalidades
• Considere o raio descrito por um ponto P, o
centro Sl do sistema esquerdo e a imagem Pl
do ponto (estão alinhados).
• Se tomarmos um raio Dr paralelo a este, que
passe pelo centro do sistema direito, a
imagem D  deste raio na imagem direita e a
imagem S  do ponto nodal da câmera
esquerda na imagem direita definirão uma
reta coincidente com a primeira linha
epipolar, descrita antes.
Visão Computacional
Visão Estéreo
http://www.dca.ufrn.br/~lmarcos/courses/visao
Profundidade da disparidade e
ângulos de vergência
Vergência
Vergência
Orientação relativa
Orientação Relativa
(uma câmera em relação à outra)
• Restabelecer as posições relativas que uma
câmera tinha em relação à outra, no
momento de tomada das imagens
• Não importa os pontos de mundo, apenas de
imagem.
Orientação relativa
•Achar R, de modo que:
r11 xl  r12 yl  r13 zl  r14 = xr
r21 xl  r22 yl  r23 zl  r24 = yr
r31 xl  r32 yl  r33 zl  r34 = zr
•Sendo que
xr xr
=
f
zr
e
yr yr
=
f
zr
Orientação relativa
• Então, dados n pontos com coordenadas nas
imagens conhecidas, devemos montar um
sistema de equações para achar R
• 9 incógnitas para R
• 3 incógnitas para T
• Total de 12 incógnitas (ou graus de
liberdade)
Orientação relativa
3 equações (restrições normalidade de R) +
1 equação (restrição de ortogonalidade de R)
4 pontos correspondentes no sistema de câmera
Total de 12 restrições seria OK?
Problema de escala
Total de 13 restrições
Orientação relativa
P(x,y,z)
y
yl
yr
xl
y
xr
P(
y
y
x
x,x
y,
b
z)
Figura 2.1 - Modelo
l
r
l
O
b
Figura 2.1 - Modelo estéreo
x
O
estéreo
Mínimo de 5 pontos = 5x2 = 10
10 + 4 = 14 > 13
1 incógnita para S
r
x
Solução
y
y
l
y
r
x
l
O
P(x,
y, z)
x
r
b
x
Figura 2.1 - Modelo estéreo
• 5 pontos com coordenadas de imagem
conhecidas (não coplanares) em ambas as
imagens
Orientação absoluta ou exterior
(sistema em relação ao mundo)
Orientação absoluta
(determina parâmetros intrínsecos)
• Colocar o par (orientado relativamente) em
escala em relação ao mundo. Dada a
disparidade de um ponto, determinar a
coordenada 3D deste.
• O sistema completo fica orientado em
relação ao frame de mundo.
Orientação absoluta (exterior)
• Com 4 pontos não co-planares
+
+
+
+
+
+
+
+
• 16 equações e 16 incógnitas
+
+
+
+
Orientação absoluta
Algoritmos estéreos
1) Extração de feições ou características das
imagens;
2) Estabelecimento de correspondência (matching)
entre as feições extraídas;
3) Reconstrução tridimensional.
Objeto
Olho
esquerdo
Olho
direito
Matching
• Podemos pensar, a princípio, em determinar
detalhes que sejam inconfundíveis nas
imagens, tais como contornos de objetos,
certos ângulos, linhas, etc, em uma imagem
e tentar sua localização na outra
• Usar as diferenças de tons de cinza entre
pixels vizinhos (textura) e tentar estabelecer
a correspondência.
Busca por correspondência
Corresp. estéreo (matching)
• estereogramas de pontos randômicos
• evidências da fase de correspondências
• correlação de áreas ou de features
(elementos)
• as imagens são pré-filtradas (eliminar altas
freqüências e realce de características)
• Ideal: correspondênca para todos os pixels
nas imagens (na prática impossível).
Problemas - ruídos - erros
• Valores da luminância dos pixels
correspondentes podem ser diferentes.
– Diferenças na quantização da luminância
– Características dos sistemas de aquisição
– Diferentes pontos de vista (diferentes ângulos)
– Distorções ocorridas no processo de aquisição
– Má localização dos elementos
– Ruídos.
• Ocultação de um elemento numa imagem.
Visão Estéreo
• Matching
Métodos de matching
• Matching baseado em áreas (completo)
– correlacão entre janelas
– minimização de erros
– relaxação
• Matching baseado em elementos (esparso)
– encontrar elementos
– correlação entre elementos (esparso)
Pré-processamento
• Redução de ruídos
• Realce de elementos (arestas, cantos,
textura)
• Normalização (em torno da média)
• Outras atenuações ou facilitações (wavelets,
multi-resolução, segmentação)
Pré-processamento (filtragem)
I (m, n)
=

 ( m, n)
I ( m, n )
 =
2

2
 (m, n)
2
I ( m, n)
Correlação
• Dada uma janela numa imagem, encontrar
uma janela na outra imagem cujos pixels
sejam o mais similar possível aos pixels da
primeira janela
Correlação
• Determinar mínimo em:
• ou determinar máximo em:
Correlação
Correlação
Correlação cruzada normalizada
Correlação cruzada normalizada
Correlação cruzada normalizada
CORRELAÇÃO DE SINAIS
• Nishihara (1982)
Imagem
Digital
2G(8)
Corr. Sinais
Mapa de
Disparid.
primitiva “and” em imagem reduzida (32x32
posições)
JANELAS ADAPTATIVAS
• 1) restringir tamanho de janela
contornos e por um tamanho máximo
por
• 2) Cálculo da disparidade para cada ponto
da imagem com precisão a nível de píxel.
• 3) Completar o mapa de disparidade
iterativamente
• 4) Densificar o mapa de disparidade
MATCHING POR RELAXAÇÃO
• 1) Cada ponto em uma imagem possui apenas um
valor de profundidade
• 2) O valor da profundidade de um ponto na cena é
similar ao de seu vizinho
Cn+1(x,y,d)={x’,y’,d’ S Cn(x’,y’,d’) x’,y’,d’  Cn(x’,y’,d’) + C0(x,y,d)}
• Termo entre chaves {t}=1 se t>T e 0 caso contrário
• S =conj. pontos x’,y’,d’ tal que |x - x’|1 e d = d’
•  =conj. pontos x’,y’,d’ tal que |x - x’|1 e |d - d’|=1
Livro do Horn (Robot Vision)
• Relaxação usando o gradiente de
sombreamento
d
n 1
i j

1   El  Er 
= d - ( El - El ) 



2   x  x 
n
i j
4
4
4



 2 ( 2 ) =
2

= k (d i j - d i j )
4
2
2
4



 x
 x yx  y
CLIQUE MAXIMAL
• Considere o grafo completo completo cujos nós são os
píxels (ou elementos) de cada imagem
• Ligações ou ramos estão definidos entre cada par deste
conjunto de nós, nos dois sentidos.
• Uma esfera, onde os pontos sobre a superfície de cada
hemisfério é o conjunto de píxels de cada uma das duas
imagens respectivamente, havendo arestas ligando a todos.
• Estabelecer um subgrafo que indique a
melhor semelhança entre cada píxel destas
imagens. O subgrafo solução é denominado
clique maximal.
CORRELAÇÃO de ELEMENTOS
• Encontrar numa das imagens elementos que
possuam características semelhantes a
dados elementos (pixels ou grupos de
pixels) da outra imagem, através do
cômputo de valores de correlação
Métodos baseados em elementos
• El = {{p1,I1},{p2,I2}, …,{pn,In}}
• Er = {{p1,I1},{p2,I2}, …,{pn,In}}
• Percorrer todos os elementos de (El e Er),
encontrando os pares de elementos mais
similares nas duas imagens
Métodos baseados em elementos
CORRELAÇÃO DE CANTOS
• 1) Extração de elementos tais como sequências de arestas
ou aproximações de polígonos e localizar cantos nestes.
• 2) Aplica-se um operador diferencial e relaciona-se pontos
que são cantos por limiarização (thresholding).
• 3) Uso de um modelo explícito da estrutura local da
imagem na vizinhança dos cantos e procurar similares
numéricos para tal modelo por uma minimização não
linear.
CORRESPONDÊNCIA de ARESTAS
• 1) Extração de arestas. Definição de estruturas lineares
compostas por sequencias de pixels.
• 2) Cálculos de valores de correlação nestas estruturas
• 3) Pode-se eliminar algumas arestas na busca da
correspondente, examinando o tamanho da estrutura
(comprimento), a curvatura, etc...
VARREDURA DE LINHAS EPIPOLARES COM
USO DE PROGRAMAÇÃO DINÂMICA
Min h( x1 , x2 , x3 )
x1 , x2 , x3
Min f 2 ( x3 ) , onde
x3
f 2 ( x3 ) = Min ( f1 ( x2 )  h2 ( x2 , x3 ) e
x2
f1 ( x2 ) = Min h1 ( x1 , x2 )
x1
Divide-se o espaço de disparidade dentro de cada
linha epipolar em dois sub-espaços
Resolve-se o problema em um deles e depois no outro
Inter e intra-scan-line
UTILIZAÇÃO DE SNAKES
• tracking de objetos em sequências de imagens
• snake minimiza energia numa spline, guiada por restrições
de forças externas e influenciada pelas forças da imagem
que a empurram em direção a elementos (features) tais
como linhas e arestas
• snakes são contornos ativos que estacionam-se nas
proximidades de arestas, localizando-as de forma precisa.
• Usa-se a continuidade de espaços de escala para
enlarguecer a região de captura nos arredores de um
elemento, ou seja, uma borração inicial da imagem com
um filtro.
2
(
Eest = VsL ( s ) - VsR ( s )
)
Usando Gabor Wavelets e Fourier
• Deslocamento no espaço corresponde a um
deslocamento de fase na transformada de
Fourier
• Wavelets aproxima Fourier
• (Sanger, Qian)
Matching recursivo (LM)
Marcos Medeiros
• Imagem é decomposta em um espaço de
escalas usando Wavelets ou Gaussianas
• Correlação começa em um nível grosseiro e
até chegar ao nível de melhor precisão
• Ganha em tempo de busca, para o melhor
nível
• Gargalo de ter que computar o espaço de
escalas
Marcos Medeiros
• Problema é então como determinar o nível
onde se deve iniciar o matching, que pode
ser diferente para cada pixel
• Solução: usar um predicado e lógica fuzzy
para calcular qual será este nível, para cada
pixel
• No final, usou apenas LoG (não Wavelets)
• Bons resultados (mais rápido que usando as
wavelets)
Trabalho de casa
• Implementar metodos de Reconstrucao Estereo, para
13/11/07
• Passos:
– Determinar o estado da arte em metodos baseados em area
– Determinar o estado da arte em metodos baseados em features
(elementos)
– Determinar o estado da arte em metodos baseados em biologia
(Gabor, Wavelets, Phase based methods, etc).
– Escolher 2 metodos diferentes e implementa-los (usando imagens
providas pelas cameras cedidas ao grupo).
– Entregar um relatorio com o estado da arte.