Embed Size (px)
Citation preview
Interpolação de imagens (Microsoft)
Problema abordado por César Dificuldades▪ Determinação de mapas de profundidade complicado▪ Problemas nos resultados gerados
?
Melhorar obtenção de geometria
Determinar correspondências de pontos (pixels) entre duas imagens Disparidade: deslocamento da posição de um pixel em duas imagens Retificação simplifica o problema Para cada pixel p(x,y) e q(x’,y’)▪ y≡ y’▪ Disparidade: d = x – x’
Mapa de Disparidades Triangulação Mapa de profundidades Podemos obter coordenadas do mundo de cada ponto▪ Calibração do sistema de câmeras conhecida
Desafios Regiões sem textura Regiões de descontinuidade Regiões oclusas
Cortes de Grafo Ferramenta de otimização Problemas modeláveis como minimização de energia
Problema de Estéreo Solução por Minimização de Energia Problema mapeado como um grafo▪ Corte mínimo minimiza energia
Corte Mínimo = Fluxo Máximo
Técnica com custo computacional elevado Número de rótulos (pixels) Número de arestas
Otimizações Redução do espaço de disparidades Multi‐Resolução▪ Pirâmide Gaussiana
Proposta Algoritmos de estéreo Cortes de Grafo Multi‐Resolução
Propor novo método Desempenho superior Acurácia mantida
Minimização de energia Atribuição de rótulos Estéreo como problema de atribuição de rótulos▪ Conjunto P contendo n pixels▪ Conjunto L contendo k rótulos▪ Encontrar configuração f
Forma típica de função de energia
Corte mínimo = energia mínima
Nós do grafo pixels da imagem
Vértices terminais s e t Rótulos possíveis
Pesos das arestas Entre não‐terminais: termo de suavidade Entre terminais e não terminais: termo de dados
Corte: dividir grafo em dois conjuntos S e T Custo do corte = soma das arestas de S a T
Corte mínimo Corte de menor custo Equivalente a calcular fluxo máximo entre os terminais s e t(Ford & Fulkerson)
Grafo com vários nós terminais Problema multi‐label é NP‐difícil Solução iterativa com grafos de dois terminais
Estéreo Rótulos = disparidades = função de diferença de intensidade entre pixel p (esquerda) e p + fp (direita)
)( pp fD
Determinação de mínimo local Expansão‐α▪ Somentes movimentos de expansão
Troca‐αβ▪ Somente movimentos de troca
Partição
, onde
Dados α e β P = P’ para qualquer rótulo l ≠ α,β. Pixels com rótulo α em P passam a ter rótulo β em P’
Abrange funções de energia mais genéricas
}|{ LlPP l }|{ lfPpP pl
Uso permitido quando V é métrica no espaço de rótulos
Permite que um conjunto de pixels alterem seu rótulo para α
Busca iterativa em L por expansão de menor energia em cada ciclo
Pixels com rótulo ou Pixel permanece com seu rótulo atual ou muda para α
Ciclo bem sucedido quando atribuição de rótulos melhor é encontrada
Algoritmo encerra quando não é possível mais minimizar a energia Nenhuma expansão em um mesmo ciclo tem energia menor que a atual
Grafo dinâmico em cada iteração Estrutura depende do rótulo e partição atuais
Aceleração do método Etapas de inicialização Redução de rótulos e arestas
Etapas principais Pirâmide Gaussiana Algoritmo de expansão Upsampling Propagação de Disparidades
Pirâmide para ambas as imagens
Fator de escala = 2
Pouco custo de processamento
Mapa de disparidades obtido é redimensionado
Propagação de mapas de cada nível para o nível seguinte
Fator de escala
Algoritmo de Level Seeding
Espaço de disparidades de um nível: fator k
Algoritmos de redução do espaço de disparidades LDNR (Label Disparity Neibourhood Restricted) EL (Expanding Label Disparity Neighbourhood) EAC (Expanding All Combinations)
Algoritmo de expansão‐α ao invés de troca‐αβ Estéreo x Fluxo Óptico (Worby) Desempenho
Redução do conjunto de rótulos em cada nível
Vizinhanças de rótulos
Pixels já estão próximos de seu rótulo ideal em cada iteração
Input: mapa de disparidades do nível anterior
LDNR: propagação de erros
Conjunto de rótulos cresce a cada iteração
Rótulos expansíveis a todas as vizinhanças de rótulos
Conjunto de rótulos pode conter todos os rótulos
Kolmogorov
Multi‐Resolução
LDNR
EL
EAC
Erros/Comparação
MiddleBury
Contribuição: método utilizando algoritmo de expansão‐α com multi‐resolução
Algoritmos de otimização com resultados visuais semelhantes
Ganho significativo de desempenho
Ainda não executável em tempo real
Possíveis novas abordagens Implementação multi‐threaded
▪ Paralelização do algoritmo▪ Paralelização dos dados
Implementação do método em GPU (Cuda) Etapa inicial de segmentação por cor
Questões?
