INF 2064 - Visão Computacional e
Realidade Aumentada
Trabalho Final
Disparidades, Correspondências e
Corte Mínimo para Estéreo
Vitor Barata R. B. Barroso
[email protected]
Introdução
O Problema de Visão em Estéreo


Duas câmeras capturam a mesma cena simultaneamente
A partir das duas seqüências de imagens, queremos:


Descobrir pontos, vistos por cada câmera num mesmo
instante, que correspondem ao mesmo ponto real
Deduzir posições reais dos pontos e gerar um modelo virtual
do mundo
Cam 1
Cam 2
O Problema de Visão em Estéreo

Simplificações comuns:





Câmeras sincronizadas, imagens do mesmo instante
Modelo das câmeras conhecido, imagens retificadas
Deslocamento apenas em um eixo, horizontal nas imagens
Distância e ângulo pequenos entre as câmeras
Ruído desprezível
O Problema das Disparidades

Dadas duas imagens de estéreo:


Encontrar os pixels correspondentes e oclusos entre as duas
Gerar um mapa indicando, para cada pixel de uma imagem:


A distância em relação ao pixel correspondente na outra imagem
Um valor especial para indicar oclusão
<x2,y2> = <x1,y1>  d(x1,y1)
O Problema das Disparidades

Modelagem do problema

Superfícies lambertianas: a aparência não varia com o pontode-vista


Semelhança entre pontos individuais medida pela intensidade
(luminância)
Superfícies suaves por partes


Regiões com variação suave de intensidade devem ter variação suave
de disparidade
Descontinuidades na intensidade indicam bordas e devem poder ser
preservadas na disparidade
Abordagens

Análise local


SSD/SAD (“sum of squared/absolute differences”) com janela fixa ou adaptativa

Correlação cruzada normalizada
Correspondência entre pares de pixels estabelecida na imagem inteira por meio
de um problema de otimização (minimização de função de custo/erro/energia)

Têmpera simulada (“Simulated annealing”)

Difusão probabilística

Corte mínimo de grafos
Análise por scanlines



Análise global


Correspondência entre dois pixels depende apenas das vizinhanças (janelas)
Dificuldade de preservar a ordem dos pixels e manter consistência entre scanlines
Análise cooperativa


Baseada na modelagem computacional da visão estéreo humana
Operações locais iterativas resultando numa otimização global
Abordagens

Refinamento do mapa de disparidades


Estimativas de disparidade sub-pixel
Validação cruzada




Computam-se disparidades nos dois sentidos entre duas imagens
Se o pixel A for mapeado em B e este não for mapeado de volta,
marca-se A como ocluso
Filtros para eliminar erros espúrios
Preenchimento de “buracos” por ajuste de superfícies
Algoritmos de Análise Local
Correlação Cruzada
SSD com janela fixa

Idéia: a vizinhança de pixels correspondentes deve ter alta
correlação nas duas imagens
-

SSD com janela fixa

Problema: essa heurística nem sempre funciona,
principalmente perto de descontinuidades de oclusão
-

SSD com janela fixa

Erro associado a mapearmos um pixel A (xA,yA) para um
pixel B (xB,yB) com disparidade (u,v)



Tomamos janelas de tamanho 2W ao redor de ambos pixels
Erro de intensidade = ||I2 – I1|| ou (I2 – I1)2
Erro de mapeamento = soma dos erros de intensidade ao
longo de toda a janela
A
yA
xA
yB= yA +v
B
xB=xA+u
SSD com janela fixa

Escolha do mapeamento do pixel A na segunda imagem

(u,v) que minimize a expressão abaixo, dentre todas as opções
de disparidade consideradas
E (u, v ) 
x A W

y A W
2


I
(
x
,
y
)

I
(
x

u
,
y

v
)
 2
1
x  x A W y  y A W
A
yA
xA
yB= yA +v
B
xB=xA+u
SSD com janela fixa

Resultados após validação cruzada
Algoritmos de Análise Global
Corte Mínimo de Grafo baseado em Pixels
Minimização de Energia

Encaramos a correspondência como um problema de classificação de pixels



A imagem é um conjunto P de pixels com um sistema de vizinhança N
O rótulo/etiqueta de um pixel p é sua disparidade fp, que pode assumir apenas
valores discretos (inteiros ou não)
O mapeamento f pode ser associado à seguinte energia (a ser minimizada):
E ( f )  E data ( f )  E neighbor ( f )

Edata mede o erro de intensidade entre pixels correspondentes:
E data ( f )   D p ( f p )   I  p  f p   I  p 
2
pP

pP
Eneighbor penaliza relações indesejadas entre disparidades de pixels vizinhos.
Geralmente, é usado para garantir a conservação de regiões suaves ( V(a,a) = 0 )
e descontinuidades:
E neighbor ( f )  E smooth ( f ) 
V  f
{ p ,q }N
pq
p
, fq 
Minimização Local de Energia

Minimizar E(f) para uma imagem é um problema NP-difícil


Milhões de mapeamentos possíveis!
Muitos mínimos locais ruins!


Buscamos um mínimo local forte, próximo ao global
Algoritmo iterativo:


Começamos com um mapeamento f arbitrário
Ciclo:


f pode ser alterado por “movimentos”, gerando vários possíveis f ’
Para cada f ’ que possa ser gerado a partir de f




Encontrar f’ que tem a menor energia
Se E(f ’) < E(f), fazemos f  f ’
Repetir o ciclo enquanto for possível qualquer atualização de f
Crítico: encontrar f ’ de menor energia em cada iteração

Conseguiremos em tempo polinomial, praticamente linear!
Tipos de movimentos

Movimentos locais

Alteração do rótulo (disparidade) de um pixel para um valor
qualquer


Costuma achar mínimos locais muito distantes do global
Movimentos globais

Inversões 



Substituímos, de uma só vez, rótulos  por  e vice-versa, para
qualquer número de pixels
Achar mínimos locais muito fortes
Expansões 


Substituímos, de uma só vez, o rótulo de qualquer número de
pixels por um rótulo 
Acha mínimos locais a um fator pequeno e conhecido do global
Corte Mínimo de Grafos

Solução por Grafos:






Um nó para cada pixel da imagem

Apenas rótulos  ou  para inversões

Qualquer rótulo para expansões
Nós terminais extras:

 e  para inversões

 e ! para expansões
Arestas entre cada pixel e ambos terminais
Arestas entre pares de pixels vizinhos
Pesos apropriados nas arestas
Corte do grafo:




Conjunto mínimo de arestas que separa os terminais
Partição dos nós em subconjuntos contendo cada terminal
Custo do corte é dado pela soma dos pesos das arestas
Corte mínimo: aquele com o menor custo possível
Corte Mínimo de Grafos

Relacionando com o problema:



Corte do grafo  mapeamento f ’

O corte separa cada pixel de um, e apenas um, dos terminais

Os pixels recebem o rótulo do nó terminal que foi separado pelo corte
Custo do corte  energia de f ’
Corte mínimo  f ’ de menor energia
Corte Mínimo de Grafos

Construção do grafo:

Pesos das arestas são penalidades pelo corte passar por elas



Projetados para casar o custo do corte com a energia do mapeamento
Refeita dinamicamente a cada ciclo do algoritmo
Pode ser necessário criar vértices auxiliares

Para expansões α, aparecem apenas entre vértices com rótulos diferentes em f
Grafo para Inversões
t p  D p     qN p V  , f q ,
p  P
t p  D p      qN p V  , f q ,
p  P
qP
qP
e p ,q   V (  ,  ),

p ,q N
p ,qP
Grafo para Expansões

t p  ,
p  P
t p  D p  f p ,
p  P
t p  D p  ,
pP
e  p ,a   V ( f p ,  ) 

ea ,q   V (  , f q )  p , q  N , f p  f q


t a  V ( f p , f q ) 
e p ,q   V ( f p ,  ),  p , q  N , f p  f q
Comparação
Imagem Esquerda
Correlação
Disparidades Verdadeiras
Corte de Grafo
por Pixels
Corte de Grafo
por Atribuições
Algoritmos de Análise Global
Corte Mínimo de Grafo baseado em Atribuições
Reformulação do Problema

A formulação anterior trata as imagens de forma assimétrica e
não trata:



Oclusões – pixels de uma imagem sem correspondente na outra
Unicidade – cada pixel só deveria ser mapeado a um único pixel de destino
Abordagem alternativa


Pixels:

Imagem da esquerda L com pixels l  L

Imagem da direita R com pixels r  R

União de todos os pixels p  P = L  R
Atribuições

Conjunto A de todas as atribuições a = < l , r > que podem ser feitas correspondendo
pares de pixels nas duas imagens

O rótulo fa de uma atribuição a só pode ser 1 (ativa) ou 0 (inativa)

Unicidade: impomos que só pode haver uma (ou nenhuma) atribuição ativa para cada
pixel
Unicidade e Movimentos


Unicidade

f = configuração de atribuições (ativas e inativas)

active(f) = {a : fa = 1} = conjunto de atribuições ativas em f

Nl(f) = { <l,x> ativa } = atribuições ativas que envolvem o pixel l

Nr(f) = { <x,r> ativa } = atribuições ativas que envolvem o pixel r

Pixel ocluso: | Np(f) | = 0

Unicidade: | Np(f) | <= 1, p  P
Expansão 

A = todas as atribuições com disparidade α

active(f’)  (active(f)  A)

Quaisquer atribuições podem ser desfeitas
Atribuições com disparidade α podem ser acrescentadas


Inversão 

A = todas as atribuições com disparidade α ou β

(active(f’)  A) = (active(f)  A)
Atribuições com disparidades α ou β podem ser acrescentadas ou removidas

Função de Energia

Usamos a seguinte função de energia:
E ( f )  E data ( f )  Eocclusion ( f )  E smooth ( f )

Penalidades:
E data ( f ) 
2






I
a

I
a
 dst
src
aactive f

E occlusion ( f )  T ( occluded( p )) K occ
pP

Vizinhança: atribuições são vizinhas quando partem ou chegam em pixels vizinhos

Inversão: penaliza atribuições ativas próximas com disparidades diferentes
E smooth ( f )  { a1 ,a 2 }N
d  a1 d  a 2


V
a1 a 2
 T  f  a1   f  a 2   1

Expansão: penaliza a não existência de atribuições ativas próximas com a mesma disparidade
E smooth ( f )  { a1 ,a 2 }N
d  a1 d  a 2
 V
a1 a 2
 T  f  a1   f  a 2 

Grafo para Expansões




Definições:

A0 = {aactive(f) : d(a)  α}

A = {aA : d(a) = α}

F = (f : active(f) = Ã), Ã = A0  A

Np(F)  {0,1,2}, p  P
Vértices:

terminais s,t

cada atribuição a  Ã
0
t
a
a0
1
Arestas direcionadas:
1
s
0

(s,a) e (a,t) entre cada atribuição e os terminais

(a1,a2) e (a2,a1) entre a1 e a2 vizinhas ({a1, a2}  N, ambas  A0 ou ambas  A )

(a1,a2) e (a2,a1) entre a1A0 e a2A ambas envolvendo um pixel p
Relacionando:

aA0  f’(a) = 1 se a ficar ligado a s (se (s,a) não for cortada)

aA  f’(a) = 1 se a ficar ligado a t (se (a,t) não for cortada)

aÃ  f’(a) = 0
Custo de dados

Lembrando:


aA0  f’(a) = 1 se a ficar ligado a s (se (s,a) não for cortada)
aA  f’(a) = 1 se a ficar ligado a t (se (a,t) não for cortada)
E data ( f ) 

2






I
a

I
a
 dst
src
aactive f


D( a )
aactive f
Então:
( a , t )  D  a , a  A
0
( s , a )  D  a , a  A
t
D(a0)
a
a0
s
D(a)
Custo de oclusão e unicidade

Lembrando:



aA0  f’(a) = 1 se a ficar ligado a s (se (s,a) não for cortada)
aA  f’(a) = 1 se a ficar ligado a t (se (a,t) não for cortada)
E occlusion ( f )  T ( occluded( p )) K occ
Definições:
pP
Docc ( a  l , r  )  Docc l   Docc  r 
t
Docc ( p )  K occ  T ( active( F )  1)

Então:
( s , a )  Docc  a , a  A 0
( a , t )  Docc  a , a  A
 p  P , p  a1 , p  a 2

( a 2 , a1 )  K occ  a1  A 0 , a 2  A
( a1 , a 2 )  
a0

Kocc
Docc(a0)
s
Docc(a)
a
Custo de (des)continuidade

Lembrando:


aA0  f’(a) = 1 se a ficar ligado a s (se (s,a) não for cortada)
aA  f’(a) = 1 se a ficar ligado a t (se (a,t) não for cortada)
E smooth ( f )  { a1 ,a 2 }N

d  a1 d  a 2
Definição:

V
a1 a 2
 T  f  a1   f  a 2 
D smooth ( a )  da(1a,a 2)dN(a ) V a1 ,a 2
1
a 2 Ã

a2 d
2
Então:
( a , t )  D smooth  a , a  A 0
a1 , a 2  N
( a 1 , a 2 )  V a 1 ,a 2 

 d ( a1 )  d ( a 2 )
( a 2 , a 1 )  V a 1 ,a 2 
 a , a  A 0 ou A
1
2

a 2d
a1 d
a2 d
a2 d
Custo de (des)continuidade

Lembrando:


aA0  f’(a) = 1 se a ficar ligado a s (se (s,a) não for cortada)
aA  f’(a) = 1 se a ficar ligado a t (se (a,t) não for cortada)
E smooth ( f )  { a1 ,a 2 }N

d  a1 d  a 2
Definição:

V
D smooth ( a )  da(1a,a 2)dN(a ) V a1 ,a 2
1
a 2 Ã

2
a1 a 2
 T  f  a1   f  a 2 
Dsmooth
(a0)

t
Então:
( a , t )  D smooth  a , a  A 0
a1 , a 2  N
( a 1 , a 2 )  V a 1 ,a 2 

 d ( a1 )  d ( a 2 )
( a 2 , a 1 )  V a 1 ,a 2 
 a , a  A 0 ou A
1
2
a
a0
s
Grafo para Expansões
0


(
s
,
a
)

D
a
,
a

A
 Pesos:
occ
( a , t )  D occ  a , a  A
( a , t )  D  a   D smooth  a , a  A 0
( s , a )  D  a , a  A
( a 1 , a 2 )  V a1 ,a 2  a 1 , a 2  N

( a 2 , a 1 )  V a1 ,a 2  a 1 , a 2  Ã
( a1 , a 2 )    p  P , p  a1 , p  a 2

( a 2 , a 1 )  K occ  a 1  A 0 , a 2  A
D occ ( a  l , r  )  D occ l   D occ  r 
D smooth ( a )  a
1
,a 2 N ,d ( a 1 )  d ( a 2 ),a 2 Ã
V a 1 ,a 2
Grafo para Inversões

Definições:

A0 = {aactive(f) | d(a)  α e d(a)  β}
A = {aA | d(a) = α}, A = {aA | d(a) = β}

A = A  Aβ


Vértices:



0
1
aα
aβ
1
0
Arestas direcionadas:




terminais s,t
cada atribuição aA
t
(s,a) e (a,t) entre cada atribuição e os terminais
(a1,a2) entre a1A e a2A vizinhas ({a1, a2}N)
(a2,a1) entre a1A e a2A ambas envolvendo um pixel p
Relacionando:



aA  f’(a) = 1 se a ficar ligado a s (se (s,a) não for cortada)
aAβ  f’(a) = 1 se a ficar ligado a t (se (a,t) não for cortada)
aAβ  f’(a) = f(a)
s
Custo de dados

Lembrando:


aA  f’(a) = 1 se a ficar ligado a s (se (s,a) não for cortada)
aAβ  f’(a) = 1 se a ficar ligado a t (se (a,t) não for cortada)
E data ( f ) 

2






I
a

I
a
 dst
src
aactive f


D( a )
aactive f
Então:
( a , t )  D  a , a  A

( s , a )  D  a , a  A 
D(aα)
t
aα
aβ
s
D(aβ)
Custo de oclusão (e unicidade)

Lembrando:



aA  f’(a) = 1 se a ficar ligado a s (se (s,a) não for cortada)
aAβ  f’(a) = 1 se a ficar ligado a t (se (a,t) não for cortada)
E occlusion ( f )  T ( occluded( p )) K occ
Definições:
pP
Docc ( a  l , r  )  Docc l   Docc  r 
t
Docc ( p )  K occ  T ( active( F )  1)

Então:
a
( s , a )  Docc  a , a  A
( a , t )  Docc  a , a  A 

Kocc
Docc(a)
( a1 , a 2 )     p  P , p  a1 , p  a 2

( a 2 , a1 )  K occ  a1  A , a 2  A 
Docc(aβ)
s
aβ
Custo de (des)continuidade

Lembrando:



aA  f’(a) = 1 se a ficar ligado a s (se (s,a) não for cortada)
aAβ  f’(a) = 1 se a ficar ligado a t (se (a,t) não for cortada)
E smooth ( f )  { a1 ,a 2 }N
Definição:
d  a1 d  a 2

V
a1 a 2
 T  f  a1   f  a 2   1
D smooth ( a )  a1 ,a02 N Va1 ,a 2
aβ
a 2 A

Então:
( a , t )  D smooth  a , a  A
( s , a )  D smooth  a , a  A 
( a1 , a 2 )  V a1 ,a 2  a1 , a 2  N



a

A
,
a

A
( a 2 , a1 )  0
2
 1

aβ
a
aβ
aβ
Custo de (des)continuidade

Lembrando:



aA0  f’(a) = 1 se a ficar ligado a s (se (s,a) não for cortada)
aA  f’(a) = 1 se a ficar ligado a t (se (a,t) não for cortada)
E smooth ( f )  { a1 ,a 2 }N
Definição:
d  a1 d  a 2

V
a1 a 2
D smooth ( a )  a1 ,a02 N Va1 ,a 2
a 2 A

 T  f  a1   f  a 2   1
Dsmooth
(a)

t
Então:
( a , t )  D smooth  a , a  A
a
aβ
( s , a )  D smooth  a , a  A 
( a1 , a 2 )  V a1 ,a 2  a1 , a 2  N



a

A
,
a

A
( a 2 , a1 )  0
2
 1
s
Dsmooth(aβ)
Grafo para Inversões

Pesos: ( s , a )  D occ  a , a  A
( a , t )  D occ  a , a  A 
( a , t )  D  a   D smooth  a , a  A 
( s , a )  D  a   D smooth  a , a  A 
 a 1 , a 2  N

( a 1 , a 2 )  V a 1 ,a 2  a 1  A  , a 2  A 
[( a 1 , a 2 )   ]  p  P , p  a 1 , p  a 2

( a 2 , a 1 )  K occ  a 1  A  , a 2  A 
( a 2 , a1 )  0
Docc ( a  l , r  )  Docc l   Docc  r 
D smooth ( a )  a1 ,a02 N V a1 ,a 2
a 2 A
Inversões e Unicidade

Unicidade no algoritmo de inversões

Não incluir atribuições aαβ=<l,r> se Nl(f) = {a0} ou Nr(f) = {a0}



Custo ∞ para ligar simultaneamente aα e aβ envolvendo um mesmo pixel
Vantagens



Como a atribuição a0 não será desligada, não podemos ligar aα nem aβ
Unicidade garantida por construção
Implementação mais simples, cada pixel admite
apenas uma atribuição ativa em cada instante
Problema


Inversões ficam restritas demais e perdem poder
Atingimos mínimos locais muito ruins
Parâmetros

Custo de dados

Custo de oclusão: Kocc

Custo de suavidade:
D ( a )  min I  a dst   I  a src
 , d max 
2
D ( a )  min I  a dst   I  a src  , d max 


Fixo ou proporcional à descontinuidade?
Rezudido onde há descontinuidade de intensidade?
V a 1 ,a 2
  , se max I  a l 1   I  a l 2  , I  a r 1   I  a r 2   d min

 3 , caso contrário
Comparação
Imagem Esquerda
Correlação
Disparidades Verdadeiras
Corte de Grafo
por Pixels
Corte de Grafo
por Atribuições
Melhor Resultado




Expansão de atribuições
Custo de dados quadrático limitado em 400
Custo de oclusão 15
Custo de continuidade 10

Aumentado para 100 se intensidades diferem menos de 10
Referências

Y Boykov, O Veksler, R Zabih, Fast Approximate Energy
Minimization via Graph Cuts - IEEE Transactions on Pattern
Analysis and Machine Intelligence, vol. 23, no. 11, pp. 1222-1239,
November, 2001.

V Kolmogorov, R Zabih, Computing Visual
Correspondence with Occlusions via Graph Cuts International Conference on Computer Vision, 2001

D Scharstein, R Szeliski, A taxonomy and evaluation of
dense two-frame stereo correspondence algorithms International Journal of Computer Vision, vol. 47, no. 1-3, pp. 7-42,
April, 2002