O operador SUSAN, proposto por Smith em [Smith & Brady 1997], segue o método usual de detecção de vértices, ou seja, dada uma imagem, usando uma janela pré-determinada centralizada em cada pixel desta imagem, aplica-se localmente um conjunto de regras. O resultado dessas regras são processadas e fornecem um conjunto de vértices na saída. Será feita uma análise sobre o operador de detecção de vértices SUSAN Smallest Univalue Segment Assimilating Nucleus, ou Menor Segmento de Valor Semelhante ao Núcleo.
O princípio deste detector de vértices é baseado no fato de que cada ponto da imagem tem uma área de intensidade comparável. O algoritmo envolve aplicar uma máscara cir- cular centralizada em cada pixel e então comparar a intensidade dos pixels da vizinhança com a do centro. A área com intensidade similar ao núcleo é denominada de Área USAN, Univalue Segment Assimilating Nucleus.
Uma filtragem não-linear define quais partes da imagem são relacionadas a cada pixel individualmente. Cada pixel associa uma região de intensidade similar. Quando fazemos a minimização desta mesma região, obtemos um método de detecção mais preciso, robusto a ruídos e rápido.
A máscara circular utilizada é uma matriz 7x7: 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 0
De tal forma que representa um circulo discretizado com raio de 3,5 pixels, para cada pixel dentro desta janela, é calculado:
n(m0) =
∑
mc(m, m0)
onde m é um vetor de localização de um pixel dentro da janela, m0 é a localização do ponto central da janela e
c(m, m0) = exp−[(I(m)−I(m0))/t]
6
sendo I(m) é a intensidade (nível de cinza) do pixel no pixel m e t é um limiar da variação de intensidade. Por fim, se n(m0) for maior que um limiar g, o ponto na posição m0 é considerado um vértice. Pode-se dizer que o operador SUSAN considera um vértice como o ponto que tem menos vizinhos similares [E. Loupias & Jolion 2000]. Em uma aplicação de visão estéreo alguns pontos de interesse não tem o seu correspondente ponto marcado precisamente na mesma localização da cena nas duas imagens. O operador SUSAN marca muitos pontos de interesses, valor controlado pelo limiar t, e marca apenas um ponto em cada vértice da imagem. Em vista disso, o operador SUSAN parece ser bastante estável e indicado a aplicações de estereoscopia.
3.2
Fusão Binocular
Após um conjunto de pontos detectados no par de imagens, pode-se iniciar o processo de fusão binocular. Para que o problema de emparelhamento de pontos tenha solução, devem existir restrições que sirvam de guia na busca por pontos correspondentes. Estas restrições são encontradas nas geometria dos dispositivos, destacando-se a linha epipolar e a restrição de ordenação. A correlação entre os vértices detectados na etapa de extração de característica é feita seguindo estas restrições e obtendo os pares de vértices mais correlacionados no par de imagens.
3.2.1
Geometria Epipolar
Consideremos as imagens p e p′ de um ponto P, observado por duas câmeras com centros óticos O e O′. Estes cinco pontos pertencem ao plano epipolar, definido pela intersecção dos dois raios OP e O′P, observados na figura 3.1. Em particular, o ponto p′ está sobre a linha l′onde esse plano e a retina Π′ da segunda câmera se intersectam. A linha l′ é a linha epipolar associada com o ponto p, e passa através do ponto e′, onde a linha base entre os centros óticos O e O′ intersecta Π′. Simetricamente, o ponto p está sobre a linha l que passa através da intersecção e da linha base com o plano Π.
Figura 3.1: Geometria Epipolar: O ponto P, os centros óticos O e O′das duas câmeras, e as duas imagens p e p′de P pertencem ao mesmo plano
Os pontos e e e′são chamados de epipolos das duas câmeras. O epipolo e′é a imagem (virtual) do centro ótico O da primeira câmera na imagem observada pela segunda câmera, e vice versa. Se p e p′são imagens do mesmo ponto, então p′deve estar na linha epipolar associada com p. Essa restrição epipolar é fundamental para visão estéreo e análise de movimento.
A parte mais difícil da análise de dados da visão estéreo é estabelecer correspondên- cias entre as duas imagens, i.e., decidir quais pontos na imagem direita combinam com quais pontos na imagem esquerda. A restrição epipolar limita a busca por essa corre- spondência: As coordenadas do ponto p determinam completamente a junção do raio O
3.2. FUSÃO BINOCULAR 23 e p, conseqüentemente determinando o plano epipolar associado OO′Pe a linha epipolar. A busca por correspondências pode ser restrita a essa linha em vez das imagens inteiras, como ilustrado na figura 3.2. Na análise estéreo, cada câmera deve estar calibrada interna- mente, mas a transformação rígida separando o sistema de coordenadas das duas câmeras é desconhecida. Nesse caso, a geometria epipolar restringe o conjunto de possíveis corre- spondências entre as duas imagens.
Figura 3.2: Restrição epipolar: O conjunto de possíveis correspondências para o ponto p e restringido à pertencer à linha epipolar associada l′
Assumindo-se que os parâmetros intrínsecos de cada câmera são conhecidos, então p= p′. A restrição epipolar implica que os três vetores −→Op,−−→O′p′ e −−→OO′ são coplanares. Portanto:
−→
Op.[−−→OO′×−→Op′] = 0
Pode-se reescrever essa equação de coordenadas independentes no referencial de co- ordenadas associado à primeira câmera como:
p.[
T
× (R
p′)] = 0 (3.1) Onde p = (u,v,1)T e p′ = (u′, v′, 1)T representam os vetores de coordenadas ho- mogêneas da imagem de p e p′,T
é o vetor de coordenadas da translação−−→OO′, separando os dois sistemas de coordenadas, eR
é a matriz de rotação na qual um vetor livre com co-ordenadas w′ no segundo sistema de coordenadas, possui coordenadas
R
.w′no primeiro sistema. Neste caso, as duas matrizes de projeção são dadas pelo sistema de coordenadas anexado à primeira câmera por (I 0) e (R
T, −R
TT
), onde I é a matriz identidade, que é a rotação de uma câmera em relação a si mesma. Então reescrevemos a equação 3.1 como:pTεp′= 0 (3.2)
Onde ε = [
T
X]R
. A matriz de torção simétrica [aX] é o produto cruzado dos vetores a e x, [a×]x = a × x. A matriz ε é uma matriz 3x3 chamada de matriz essencial, como definidapor Longuet [Longuet-Higgins 1981]. Seus nove coeficientes são apenas definidos por uma escala, e podem ser parametrizados pelos três graus de liberdade da matriz de rotação Re os dois graus de liberdade definindo a direção do vetor de translação
T
.εp′pode ser interpretado como um vetor de coordenadas representando a linha epipo- lar associada ao ponto p′na primeira imagem. Uma linha da imagem l pode ser definida pela sua equação au + bv + c = 0, onde (u,v) representam as coordenadas do ponto sobre a linha, (a,b) são as normais às linhas, e c é a distância entre a origem e l. Alterna- tivamente, podemos definir a equação em termos do vetor de coordenadas homogêneas p= (u, v, 1)T de um ponto na linha e o vetor l = (a,b,c)T por l.p = 0. Neste caso a restrição a2+ b2= 1 é relaxada já que a equação é independente a um fator de escala aplicado a l. De tal forma, a equação 3.2 expressa o fato de que o ponto p está sobre a linha epipolar associada ao vetor εp′. Por simetria, fica claro que εTp é o vetor de co- ordenadas representando a linha epipolar associada a p na segunda imagem. A matriz essencial é singular, já que .[
T
é paralelo ao vetor de coordenadas e do epipolo esquerdo,então εTe= −
R
T[.[T
×]e = 0. Pode-se mostrar que e′é um autovetor zero de ε. Huang e Faugeras [Huang & Faugeras 1989] mostraram que a matriz essencial é de fato caracter- izada pelo fato de ser singular com dois autovalores diferentes de zero.
3.2.2
Restrição de Ordenação
A ordem das imagens combinadas sobre um par de linhas epipolares é inversa à or- dem dos atributos das superfícies correspondentes sobre a curva onde a linha epipolar intercepta os limites dos objetos, como se pode observar no lado esquerdo da figura 3.3. Baker e Ohta em [Baker & Binford 1981], [Ohta & Kanade 1985] denominaram este fato de restrição de ordenação. Esta restrição pode não ser satisfeita em cenas reais, em particular quando pequenos objetos ocludem grande parte de objetos posteriores, como no lado direito da 3.3, ou quando há a presença de objetos transparentes.
Figura 3.3: Restrição de ordenação
No caso comum, mostrado à esquerda, na figura 3.3, a ordem dos pontos de carac- terísticas ao longo das duas linhas epipolares é a mesma, e é inversa à ordem dos pontos da cena ao longo da curva onde a superfície observada intersecta o plano epipolar. No
3.2. FUSÃO BINOCULAR 25 caso mostrado à direita, um objeto menor está em frente a um maior. Alguns dos pontos da superfície não são visíveis em uma das imagens; A não é visível na imagem direita, nem C é visível na imagem esquerda. A ordem dos pontos da imagem não é a mesma nas duas figuras: b está à direita de d na imagem esquerda, mas b′ está à esquerda de d′ na imagem direita.
Essa restrição é utilizada para obter algoritmos eficientes, utilizando-se da progra- mação dinâmica para estabelecer correspondências estéreo. Especificamente, assume-se que um número de pontos de características foram encontrados em linhas epipolares cor- respondentes. O objetivo é combinar os intervalos, separando os pontos sobre os dois perfis de intensidade. De acordo com a restrição de ordenação, a ordem dos pontos de características deve ser a mesma. Contudo, o intervalo nessa imagem pode ser reduzida para uma correspondência de pontos simples, retirando correspondências associadas com oclusão e/ou ruído.
3.2.3
Correlação
Os métodos de correlação encontram correspondentes dos pixels em imagens pela comparação de perfis de intensidade na vizinhança de possíveis correspondências. Essa técnica é a primeira técnica proposta para a resolução do problema de fusão binocular. Mais precisamente, consideremos um par estéreo retificado e um ponto (u,v) na primeira imagem. Associa-se com uma janela de tamanho p = (2m + 1) × (2n + 1) centralizada em (u,v), sendo que o vetor w(u,v) ∈ Rp é obtido pela varredura dos valores da janela, uma linha por vez. Dada uma possível correspondência (u + d,v) na segunda imagem, podemos construir um segundo vetor w′(u + d, v) e definir a função de correlação cruzada normalizada correspondente como:
C(d) = 1 |w − w|.
1
|w′− w′|.(w − w).(w′− w′) (3.3) onde os índices u,v e d foram omitidos e w representa o vetor cujas coordenadas são iguais à média das coordenadas de w, como mostrado na figura 3.4.
Na figura 3.4 a posição da segunda janela é separada da primeira por uma diferença d. A duas janelas são codificadas por vetores w e w′, e a função de correlação mede o cosseno do ângulo θ entre os vetores w − ¯we w′− ¯w′obtidos pela subtração entre os componentes de w e w′e as componentes dos vetores de intensidade média na janela correspondente
A função de correlação normalizada C claramente varia entre -1 e +1, e alcança o valor máximo quando o brilho da imagem das duas janelas são relacionados por uma transfor- mação afim I′= λI + µ para algumas constantes λ e µ, com λ > 0. Em outras palavras, o máximo dessa função corresponde às regiões das imagens separadas por uma constante e por um fator positivo de escala, e os pares correspondentes podem ser encontrados pela busca do máximo de C sobre alguma variação pré-determinada de disparidades.
É fácil mostrar que maximizando a função de correlação é equivalente a minimizar a norma da diferença entre os vetores (1/|w − w|) e (1/|w′− w′|)(w′− w′), ou equiv- alentemente, a soma do quadrado da diferença entre os valores dos pixels das janelas normalizadas comparadas. Embora seja computacionalmente custoso o cálculo da função
Figura 3.4: Correlação de duas janelas 3x5 sobre as linhas epipolares correspondentes de correlação normalizada sobre cada pixel da imagem ao longo de uma faixa de dispari- dades, esta pode ser implementada eficientemente através de recursão.
Superfícies inclinadas podem trazer problemas para métodos de correlação baseados em regiões, pois a correlação baseada em regiões assume implicitamente que a superfície observada é paralela aos dois planos das imagens, o que nem sempre é verdade, como mostra a figura 3.5.
Figura 3.5: A perspectiva de superfícies não-frontoparalelas é diferente para as duas câmeras: Um segmento de superfície com comprimento L projeta-se em dois segmen- tos de imagem com diferentes comprimentos l e l′.
Outro problema para os métodos de correlação é o tamanho das janelas, sendo um fator fundamental para o sucesso desta etapa. Se a janela, usada para procurar por cor- respondências, for pequena; O ruído pode facilmente destruir qualquer correspondência; Se o tamanho da janela for aumentado, aumentam-se as ambigüidades nos limites dos objetos que estão em distâncias diferentes.
Estes problemas relacionados à inclinação de superfícies e ao tamanho da janela de correlação sugerem que a busca por correspondências entre características fisicamente
3.2. FUSÃO BINOCULAR 27 significantes da imagem, tais como vértices, e sua vizinhança, devem ser preferidas à utilização apenas de regiões ou níveis de intensidades dos pixels.
A iluminação sobre o par de câmeras deve ser igual para que as imagens adquiridas apresentem o mesmo valor de níveis de cinza para um mesmo ponto. Porém, tal condição é difícil de ser implementada sem a utilização de um dispositivo de iluminação acoplado às câmeras, dependendo basicamente do ambiente visualizado. Como o objetivo é deter- minar a profundidade de objetos em um ambiente desconhecido, é necessário utilizarmos um algoritmo de correlação que seja robusto a esta dificuldade.
A correlação cruzada normalizada de média zero (ZNCC) calcula a correspondência entre pixels independentemente de diferenças no brilho ou contraste nas imagens, devido à normalização efetuada em relação à média e ao desvio padrão. Na literatura, os trabalhos de Crouzil; Psarakis e Evabgelidis; MA e Liu e; Lindoso, Entrena, López-Ongil e Liu, [Crouzil 2004, Psarakis & Evangelidis 2005, YongZhuang Ma 2005, A. Lindoso 2005], demonstram o desempenho da ZNCC é demonstrado. Para uma janela de dimensões 2 ∗ m + 1 × 2 ∗ n + 1, este método de correlação é o seguinte:
ZNCC(i, j) = ∑ n k=−n∑mk=−m[Ide × Idd] a∗σ2(Ide) ∗ σ2(Idd) (3.4) onde a= (2m + 1) ∗ (2n + 1)
Ide= Ie(ui + k, vi + l) − Ie(ui, vi)
Idd= Id(u j + k, v j + l) − Id(u j, v j)
com Ie(ui,vi) e Id(u j,v j) sendo o valor médio do nível de cinza das janelas das imagens esquerda Ie e direita Id, respectivamente, calculados da seguinte forma:
Id(ui, vi) = n
∑
k=−n m∑
l=−m Id(ui + k, vi + l) a Ie(ui, vi) = n∑
k=−n m∑
l=−m Ie(ui + k, vi + l) aσ2(Ide) e σ2(Idd) representam os desvios padrões das janelas das imagens esquerda e direita, respectivamente, calculados da seguinte forma.
σ2(Ide) =∑ n k=−n∑ml=−m[Ide]2 a σ2(Idd) = ∑ n k=−n∑ml=−m[Idd]2 a
agens baseado nas características, vértices e regiões em torno dos vértices, o que pro- porciona uma maior robustez quando comparado com um emparelhamento baseado em apenas um destes atributos.
3.3
Reconstrução
A Reconstrução consiste em recuperar o formato tridimensional de uma cena visu- alizada pelo par de câmeras. Este processo envolve a retificação, reconstrução e trian- gulação das imagens. Variações e aperfeiçoamentos dos métodos de triangulação são apresentados na literatura em [Hopken 2006, Tandler 2006, J. Tandler 2006, Davis et al. 2003].
3.3.1
Retificação da imagem
Os cálculos associados com algoritmos estéreo são consideravelmente simplificados quando as imagens de interesse são retificadas, i.e, substituídas por figuras equivalentes projetivamente com um plano de imagem comum, paralelo à base de junção dos dois centros óticos, como exemplificado na figura 3.6. O processo de retificação pode ser implementado pela projeção das imagens originais em novos planos de imagem. Com uma escolha apropriada do sistema de coordenadas, as linhas epipolares retificadas são mantidas nas novas imagens, e também são paralelas à linha base.
Figura 3.6: Um par estéreo retificado
Na figura 3.6 os dois planos das imagens Π e Π′ são reprojetados sobre um plano comum ¯Π = ¯Π′paralelo à linha base. As linhas epipolares l e l′associadas com os pontos pe p′nas duas imagens, são mapeadas em uma linha de varredura comum ¯l = ¯l′também paralela à linha base e passando através dos pontos reprojetados ¯p e ¯p′. As imagens retificadas são facilmente construídas considerando cada imagem de entrada como um
3.3. RECONSTRUÇÃO 29 poliedro e usando mapeamento de textura para renderizar a projeção dessa rede em um plano ¯Π = ¯Π′.
Existem dois graus de liberdade envolvidos na escolha de um plano de imagem reti- ficado: A distância entre esse plano e a linha base, o qual é irrelevante, desde que se modifique somente na escala das imagens retificadas. Um balanço efetivo pela escala in- vertida dos eixos de coordenadas da imagem e a direção do plano retificado normal no plano perpendicular a base. Uma escolha natural inclui escolher uma plano paralelo à linha onde as duas retinas originais intersectam-se, minimizando a distorção associada com o processo de reprojeção.
3.3.2
Reconstrução
Dado um conjunto estéreo calibrado, dois pontos correspondentes p e p′ estão em princípio direcionados para a frente com o objetivo de reconstruir-se o ponto da cena correspondente, utilizando-se da intersecção de dois raios R = Op e R′= O′p′. Contudo, os raios R e R′nunca irão, na prática, se interceptarem, devido à calibração e aos erros de localização de características, como mostrado na figura 3.7.
Figura 3.7: Triangulação em presença dos erros de medida
Nesse contexto, várias abordagens para o problema de reconstrução podem ser ado- tados. Para construir o segmento da linha perpendicular a R e R′, que intersecta ambos os raios, podemos escolher o ponto médio P desse segmento. Este ponto é o ponto mais próximo aos dois raios e pode ser utilizado como uma pré-imagem de p e p′. Podemos reconstruir um ponto da cena usando uma abordagem algébrica. Através das matrizes de projeção M e M′ e dos pontos correspondentes p e p′ podemos reescrever as constantes z.p = M.P e z′.p′= M′.P′como: p× M.P = 0 p′× M′.P = 0 ⇔ [pX].M [p′X].M′ P= 0 (3.5)
Este sistema sobreconfinado de quatro equações, linearmente independentes nas co- ordenadas homogêneas de P, é resolvido usando o método dos mínimos quadrados. Esta
abordagem não possui uma interpretação geométrica, mas generaliza prontamente o caso de três ou mais câmeras. Pode-se reconstruir um ponto de uma cena associado com p e p′ como um ponto Q com imagens q e q′que minimizam d2(p, q) + d2(p′, q′), mostrados na figura 3.7. Esta abordagem não permite uma computação fechada do ponto reconstruído, o qual deve ser estimado através de técnicas de mínimos quadrados não-lineares como as utilizadas para calibração da câmeras. A reconstrução obtida pode ser utilizada como uma estimativa para inicializar um processo de otimização.
3.3.3
Triangulação Retificada
No caso de imagens retificadas, a noção de disparidade adquire um significado pre- ciso: dados dois pontos p e p′ localizados numa mesma linha de varredura das ima- gens esquerda e direita, com coordenadas (u,v) e (u′, v), a disparidade é definida como a diferença d = u′− u. b representa metade da distância entre os centros óticos, também chamadas de linha base nesse contexto, é fácil mostrar que a distância euclidiana PM no sistema de coordenadas normalizadas anexado à primeira câmera é PM = −2∗b/d, como na figura 3.8.
Na figura 3.8 os raios associados com dois pontos p e p′ sobre a mesma linha de varredura intersectam-se em um ponto P. A distância do ponto P relativa a um sistema de coordenada anexado à câmera esquerda é inversamente proporcional à disparidade d= u′− u. Em particular, a pré-imagem para todos os pares de pontos da imagem com disparidade constante d é frontoparalela ao plano Πd, i.e., um plano paralelo às retinas das câmeras.
Consideremos os pontos q e q′ com coordenadas (u,0) e (u′, 0), e o ponto da cena correspondente Q. Sejam b e b′ as distâncias respectivas entre a projeção ortogonal de Q sobre a linha base e os dois centros óticos O e O′. Os triângulos qQq′ e OQO′ são similares, logo 2 ∗ b = −PM ∗ d, o que prova o resultado para q e q′. Ao caso geral envolvendo p e p′com v = 0 segue-se imediatamente o fato que a linha PQ é paralela às duas linhas pq e p′q′e conseqüentemente também paralela ao plano da imagem retificada. Em particular, o vetor coordenado do ponto P no referencial anexado à primeira câmera é PM = −(B/d)p, onde p = (u,v,1)T é o vetor das coordenadas normalizadas de p. Isso gera o método de reconstrução estéreo.
Na estereoscopia, através do conhecimento da disparidade de cada ponto é possível obter-se a distância euclidiana PM de cada ponto em relação ao centro da cabeça estéreo, representado pelo ponto M de acordo com a equação 4.3, como mostra a figura 3.8.
PM=2 ∗ b
d (3.6)
onde b é metade da distância entre os centros de projeções e o ponto central, M, a distância entre as duas câmeras, e d e a disparidade calculada para cada ponto.
Para obtermos a distancia euclidiana entre os pontos P e M é preciso relacionar estas medidas com a distância focal das câmeras, f . Logo, reescrevemos a equação 4.3 con- siderando a distância focal em relação ao ponto P, obtendo a equação da reconstrução geométrica baseada na triangulação retificada 4.15.
3.3. RECONSTRUÇÃO 31
Figura 3.8: Triangulação retificada entre os dois centros óticos O e O´ das imagens
PM= 2 ∗ b ∗ f
Capítulo 4
Sistema Proposto
Neste capítulo apresentaremos o sistema de estimação da profundidade de objetos em cena baseado numa cabeça estéreo dotada de um par de câmeras CCD. A estimação da profundidade dos objetos na cena utiliza as técnicas apresentadas nos Capítulos 2 e 3. As técnicas de autocalibração baseada em coordenadas polares tridimensionais e em um deslocamento conhecido do robô, e a reconstrução e recuperação da geometria da cena baseadas em coordenadas polares tridimensionais para obtenção da profundidade são apresentadas neste capítulo.
4.1
Cabeça Estéreo
Uma cabeça estéreo robótica é um dispositivo que dá suporte a n-câmeras para a cap- tura de n-imagens diferentes de uma mesma cena, executando-se técnicas de visão com- putacional sobre as imagens capturadas. A utilização dessas técnicas de visão computa- cional torna-se necessária, pois a informação de uma única imagem não determina unica- mente a posição de um dado ponto correspondente no mundo. Pode-se então, através da utilização de duas ou mais câmeras recuperar a informação de profundidade da cena.
A cabeça estéreo utilizada neste trabalho foi a LabRoHead desenvolvida no Labo- ratório de Robótica da UFRN como uma plataforma experimental de baixo custo para aplicação das técnicas propostas. A cinemática desta cabeça estéreo pode ser visualizada na figura 4.1.
Esta plataforma experimental de baixo custo utilizada apresenta uma estrutura feita de tecnil, o que lhe confere um baixo peso, o que é um ponto importante pois se a estrutura for muito pesada pode ocorrer sobrecarregamento dos motores das juntas. Outro ponto importante na estrutura é a precisão na cabeça, já que é necessário que os motores movi- mentem precisamente as partes da cabeça, pois é necessário que as câmeras possuam um alinhamento adequado, a fim de estabelecer-se a restrição epipolar.
Em cada uma das três juntas da cabeça estéreo está acoplado um servomotor, respon-