6. Drøfting
6.1 Ein kort refleksjon
Tendo como base os fundamentos te´oricos descritos at´e o momento, vamos agora verificar como podemos aplic´a-los `a soluc¸˜ao do problema da correspondˆencia em vis˜ao est´ereo. Para isso, vamos modelar nosso problema como um problema de rotulac¸˜ao de grafos. O principal objetivo ´e encontrar uma rotulac¸˜ao consistente (representando as disparidades) de um grafo (representando os pixels da imagem). Tal problema pode ser formulado com base na teoria apresentada de fluxo m´aximo e cortes m´ınimos em grafos e, geralmente, ´e separado em pro- blemas de fluxo m´aximo e de cortes m´ınimos pois, embora tenhamos visto que o problema de fluxo m´aximo pode ser resolvido ao encontrarmos um corte m´ınimo, cada uma dessas abordagens define a estrutura do grafo de uma forma diferente.
A primeira formulac¸˜ao do problema da correspondˆencia est´ereo baseado em grafos foi proposta em [Roy e Cox, 1998]. O grafo ´e constru´ıdo com base nas formulac¸˜oes propostas para fluxo m´aximo: o grafo ´e constru´ıdo formando uma malha 3D de pontos(x′, y′, d), onde (x′, y′) s˜ao coordenadas dos pixels na imagem e d ´e um valor de disparidade pertencente ao conjunto de valores poss´ıveis, mais uma origem s e um dep´osito t. Mais formalmente, ´e
definido um grafoG = (V, E) onde V ´e definido como: V = V∗∪ {s, t},
ondeV∗ ´e a malha 3D:
V∗ = {(x′, y′, d) : x′ ∈ [0 . . . x′max], y′ ∈ [0 . . . ymax′ ], d ∈ [0 . . . dmax]},
onde(x′max + 1, ymax′ + 1) ´e dado pelo tamanho da imagem de entrada e d′max ´e dado pela disparidade m´axima. Internamente, a malha ´e 6-conectada e a origems ´e conectada ao plano
A.3 Fluxo M´aximo e Cortes M´ınimos em Grafos 119 Direção do Fluxo: Plano Frontal Plano de Fundo 6-conectada (x', y', d) x' d
s
t
Superfície de Disparidade y'Figura A.5: Correspondˆencia est´ereo como um problema de fluxo m´aximo. Imagem obtida em [Roy e Cox, 1998].
Os custos associados `as arestas s˜ao representados por func¸˜oes de custo. No grafo defi- nido, o corte m´ınimo, separando a origem do dep´osito ´e encontrado. As disparidades s˜ao associadas `a cada pixel a partir do corte m´ınimo da seguinte forma: para cada ponto(x′, y′),
a maior disparidade associada `a aresta ao longo do corte m´ınimo ´e selecionada. Note que, dessa forma o problema pode ser interpretado como determinar uma superf´ıcie de custo ´otimo que separe a origems do dep´osito t no volume de disparidade criado.
Posteriormente, apresentando resultados mais promissores, temos uma formulac¸˜ao do problema do corte m´ınimo proposta em [Boykov et al., 1999] e posteriormente adaptado em [Kolmogorov e Zabih, 2002]. Essas abordagens definem o problema da correspondˆencia est´ereo da seguinte forma: seja L o conjunto de pixels na imagem da esquerda, seja R o
conjunto de pixels na imagem da direita, e sejaP o conjunto de todos os pixels: P = L ∪ R.
Um pixelp ter´a coordenadas (px,py). Uma energia funcional apropriada ´e ent˜ao constru´ıda em func¸˜ao de um conjunto de valores de disparidade. Neste caso, o objetivo ´e encontrar um configurac¸˜ao de disparidadef que minimize uma func¸˜ao de energia global constru´ıda. Tal
tarefa envolve o conceito de movimentos.
Considere uma disparidade particular (ou r´otulo)α. Uma configurac¸˜ao f′ ´e dita estar em um ´unico movimento de expans˜ao-α de f se, para todos os pixels p ∈ L f′
p = fp oufp′ = α (fp denota o valor de disparidade de um pixelp). Agora considere um par de disparidade α eβ onde, α 6= β. Uma configurac¸˜ao f′ ´e dita estar em um ´unico movimento de troca-αβ de f se, para todos os pixels p ∈ L que tenham r´otulos α ou β, f′ = α ou f′ = β, e para todos
os outros pixelsfp′ = fp.
A.3 Fluxo M´aximo e Cortes M´ınimos em Grafos 120
encontrar eficientemente um forte m´ınimo local de energia; mais especificamente, a menor configurac¸˜ao de energia dentro de um ´unico movimento de expans˜ao-α ou de troca-αβ de f ,
respectivamente. Esta operac¸˜ao de aprimoramento local pode ser obtida via cortes de grafos. O algoritmo de expans˜ao consiste de uma seq¨uˆencia de melhorias locais atrav´es de expans˜ao-
α, para diferentes valores de disparidade α, at´e que nenhuma expans˜ao-α possa reduzir a
energia. Da mesma forma, o algoritmo de troca consiste de uma seq¨uˆencia de operac¸˜oes de trocas-αβ para diferentes pares de disparidades α, β, at´e que nenhuma troca-αβ possa
reduzir a energia. [Kolmogorov e Zabih, 2002] propuseram uma melhoria na formulac¸˜ao da func¸˜ao de energia usada por Boykov, onde as oclus˜oes foram explicitamente representadas.
Apˆendice B
Est´ereo com Minimizac¸˜ao de Energia via
Corte de Grafos
O algoritmo de est´ereo com minimizac¸˜ao de energia via corte de grafos, aqui denominado EMGC (Energy Minimization via Graph Cuts) [Kolmogorov e Zabih, 2002], ´e o que atual- mente vem apresentando os melhores resultados na obtenc¸˜ao de mapas de disparidade de um est´ereo denso, conforme estudo comparativo apresentado em [Scharstein et al., 2001]. Al´em disso, o EMGC responde bem ao uso de um par est´ereo com ´areas oclusas, que s˜ao caracterizadas por pontos da cena vis´ıveis em somente uma das imagens.
B.1
Representac¸˜ao do Problema
SejaA o conjunto n˜ao ordenado de pares de pixels que potencialmente podem ser corres-
pondentes. Para o est´ereo com cˆameras alinhadas, ou imagens retificadas, ´e poss´ıvel fazer o uso da geometria epipolar de tal forma que:
A = {hp, qi|py = qy e 0 6 qx− px < k}.
Assumindo que as disparidades se encontram em um intervalo finito, ent˜ao cada pixel na imagem da esquerdaL pode potencialmente corresponder a um dos k poss´ıveis pixels
na imagem da direita R. O objetivo ´e encontrar um subconjunto de A contendo apenas
pares de pixels que efetivamente sejam correspondentes. Equivalentemente, ´e dado a cada assinalamentoa ∈ A um valor fa cujo valor ´e 1 se os pixelsp e q se correspondem e 0 em caso contr´ario. Os assinalamentos que possuem valor 1 s˜ao ditos ativos.
B.2 O algoritmo de Est´ereo Utilizando Movimenta¸c˜ao de Expans˜ao da Disparidade 122
f . Seja Np(f ) o conjunto de assinalamentos ativos em f que envolvem o pixel p, (p.e.
Np(f ) = {hp, qi ∈ A(f )}). Uma configurac¸˜ao f ´e dita ´unica se cada pixel est´a envolvido em, no m´aximo, um assinalamento ativo, ou seja, n˜ao exista ambig¨uidade:
∀p ∈ {L ∪ R} |Np(f )| ≤ 1 ´
E importante observar que|Np(f )| = 0 significa que n˜ao h´a um assinalamento ativo e, por conseq¨uˆencia, o pixel em quest˜ao ´e uma oclus˜ao.
O problema consiste, ent˜ao, em obter o conjunto de assinalamentos ativosf de A(f ) que
representem o conjunto de disparidades do par est´ereo.