View
105
Download
1
Category
Preview:
Citation preview
Algoritmos de Corte de Grafo para Mapas de Disparidades em Estéreo
Vitor Barata R. B. Barrosovbarata@tecgraf.puc-rio.br
INF 2064 - Visão Computacional eRealidade Aumentada
Trabalho Final
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 2Cam 1
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 ponto-de-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
BaseLine - SSD com janela fixa A vizinhança de pixels correspondentes deve
ter alta correlação nas duas imagens
-
BaseLine - SSD com janela fixa Não funciona perto de descontinuidades de
oclusão
-
BaseLine - SSD com janela fixa Validação Cruzada
Calculam-se disparidades nos dois sentidos entre as imagens
Se o pixel A for mapeado em B e este não for mapeado de volta, marca-se A como ocluso
Algoritmos de Corte de Grafo
Energia em Classificação de Pixels 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):
Edata mede o erro de intensidade entre pixels correspondentes:
Esmooth tenta garantir a conservação de regiões suaves sobre cada objeto e descontinuidades entre objetos diferentes:
)()()( fEfEfE smoothdata
2)()(
Pp
pPp
ppdata pIfpIfDfE
Nqp
qppqsmooth ffVfE},{
,)(
Minimização Local de Energia Algoritmo iterativo:
Começamos com um mapeamento f arbitrário Ciclo:
Geramos vários candidatos f ’ aplicando uma regra quedefina os tipos de perturbação (“movimentos”) possíveis
Encontrar o candidato f’ que tem a menor energia Se E(f’) < E(f), fazemos f f ’ e repetimos o ciclo
Movimentos Inversões
Substituímos, de uma só vez, rótulos por e vice-versa,para qualquer número de pixels
Expansões Substituímos, de uma só vez, o rótulo de qualquer número
de pixels por um rótulo
αβ
α
Corte Mínimo de Grafos Solução por Grafos:
Um nó central para cada pixel da imagem Nós terminais:
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 mínimo do grafo: Arestas que separam os terminais com o menor custo possível
Custo = soma dos pesos das arestas O corte separa cada pixel de um dos terminais
Relacionando com o problema: Cada corte do grafo define um mapeamento f’ Corte mínimo determina o candidato f’ de menor energia
Reformulação do Problema Abordagem alternativa
Atribuições Conjunto A de todas as atribuições a = < pl , pr > 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) Oclusão: nenhuma atribuição ativa para determinado pixel Unicidade: não pode haver mais de uma atribuição ativa para cada pixel
Movimentos Expansão
Quaisquer atribuições podem ser removidas Atribuições com disparidade α podem ser acrescentadas
Inversão Atribuições com disparidades α ou β podem ser removidas Atribuições com disparidades α ou β podem ser acrescentadas
Minimização Local de Energia Função de energia:
Penalidades:
Custo de suavização: dado um pixel e sua disparidade, penalizamos... Inversão: cada vizinho que tiver uma atribuição com disparidade
diferente Expansão: cada vizinho que não tiver uma atribuição com a
mesma disparidade
)()()()( fEfEfEfE smoothocclusiondata
2)( ativas
lrdata aIaIfE
occPp
occlusion KpoccludedTfE
))(()(
Resultados
Métrica para Avaliação Mapas de referência (ground truth)
Disparidades sub-pixel! Redução de mapas de imagens em 4x Algoritmos precisariam interpolar
superfícies Vantagem de precisão: trabalhar com
resolução original e reduzir Disparidades extrapoladas/ausentes!
Bordas laterais das imagens “Sombras” de objetos
Avaliação Base middlebury exige interpolações e extrapolações! Inviável.
Falta de referências de estado-da-arte utilizáveis Avaliador próprio:
acertos, erros próximos, erros grosseiros falsas oclusões, falsas correspondências
Resultados Swap x Expand
Em ambos tipos de grafo, expand é mais rápido e correto
Parâmetros Funções de custo para dados, suavidade e oclusão Algoritmos são muito sensíveis
Execução leva vários minutos Inviável explorar plenamente os parâmetros
Idéias Uso de swap para melhorar ou perturbar expand (ruim!) Custo de oclusão e suavidade incrementais (vale à pena?) Filtro de pós-processamento para limpar ruídos
Resultados - Cones
Vista Direita
Resultados - Cones
Vista Esquerda
Resultados - Cones
Ground Truth original
Resultados - Cones
Ground Truth com oclusões
Resultados - Cones
Técnica CorretosPróximo
sGrosseir
osF
InclusosF
Oclusos
Incremental
79.78 12.08 2.90 3.30 1.94
Map Expand
79.24 12.26 3.28 3.29 1.93
Pixel Expand
79.84 5.56 0.73 1.51 12.36
SSD 7x7 77.43 4.94 2.91 3.28 11.45
Resultados - Cones
Ground Truth com oclusões
Resultados - Cones
Expansões Incrementais
Resultados - Cones
Comparação
Resultados - Teddy
Vista Direita
Resultados - Teddy
Vista Esquerda
Resultados - Teddy
Ground Truth original
Resultados - Teddy
Ground Truth com oclusões
Resultados - Teddy
Técnica CorretosPróximo
sGrosseir
osF
InclusosF
Oclusos
Incremental
63.99 23.64 7.94 2.43 2.00
Map Expand
62.31 24.79 8.48 2.44 1.98
Pixel Expand
69.68 8.72 1.78 1.66 18.17
SSD 7x7 72.41 5.68 5.02 12.80 14.08
Resultados - Teddy
Ground Truth com oclusões
Resultados - Teddy
Expansões Incrementais
Resultados - Teddy
Comparação
Conclusão Graph Cut é um método muito útil para visão, pois
permite encontrar mínimos locais fortes em problemas de otimização difíceis.
Problema: não é tempo real Movimentos de expansão são mais rápidos E poderosos Primeiro ciclo já dá resultados interessantes em 15
segundos
Os algoritmos estudados dão resultados aparentemente satisfatórios, mas infelizmente não foi possível comparar com as técnicas do estado-da-arte atual
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
Recommended