Reconstrução e caracterização de estruturas anatómicas exteriores usando visão activa

RELATÓRIO INTERNO Reconstrução e Caracterização de Estruturas Anatómicas Exteriores usando Visão Activa Teresa Cristina de Sousa Azevedo João Manuel R. S. Tavares Mário A. P. Vaz Setembro de 2005 Reconstrução e Caracterização de Estruturas Anatómicas Exteriores usando Visão Activa Por: Teresa Cristina de Sousa Azevedo Licenciada em Engenharia Electrotécnica e de Computadores pela Faculdade de Engenharia da Universidade do Porto (2002) Orientador: João Manuel R. S. Tavares Professor Auxiliar da Faculdade de Engenharia da Universidade do Porto, Departamento de Engenharia Mecânica e Gestão Industrial Co-orientador: Mário A. P. Vaz Professor Associado da Faculdade de Engenharia da Universidade do Porto, Departamento de Engenharia Mecânica e Gestão Industrial RESUMO Este trabalho teve como principais objectivos a familiarização e análise de técnicas de Visão Computacional para a Reconstrução Tridimensional de Objectos, tendo sido iniciado o desenvolvimento de uma plataforma computacional. O presente relatório é constituído por três capítulos: no primeiro, são definidos os objectivos; no segundo, é apresentada a plataforma computacional, assim como alguns resultados experimentais; no terceiro e último capítulo, são apresentadas as conclusões relativas ao estudo e ao desenvolvimento realizado e, finalmente, são referidas as perspectivas de trabalho futuro. ABSTRACT The work carried through had as main goals the familiarization and analysis of Computer Vision techniques for Three-Dimensional Reconstruction of Objects. From this work the development of a computer platform has been initiated. The present report has three chapters: in the first one, the goals are defined; in the second, the computer platform is presented, as well as some experimental results; in the third and last chapter, the conclusions relative to the study and work done are drawn and, finally, some perspectives of future work are given. Índice CAPÍTULO 1. INTRODUÇÃO ...................................................................... 1 1.1. INTRODUÇÃO À VISÃO COMPUTACIONAL....................................................................2 1.2. RECONSTRUÇÃO 3D DO CORPO HUMANO ....................................................................3 1.3. OBJECTIVOS ................................................................................................................4 CAPÍTULO 2. PLATAFORMA COMPUTACIONAL..................................... 7 2.1. PLATAFORMA COMPUTACIONAL EM DESENVOLVIMENTO ...........................................8 2.2. EXTRACÇÃO DE PONTOS FORTES ...............................................................................10 2.2.1. Detector de Harris ...........................................................................................10 2.2.2. Métodos de extracção de pontos fortes considerados......................................12 2.2.3. Resultados obtidos............................................................................................13 2.3. EMPARELHAMENTO DE PONTOS FORTES ENTRE IMAGENS (MATCHING)......................15 2.3.1. Correlação simples ..........................................................................................16 2.3.2. Correlação normalizada de média nula...........................................................17 2.3.3. Algoritmo de Lucas-Kanade.............................................................................17 2.3.4. Métodos de emparelhamento de pontos considerados.....................................18 2.3.5. Resultados obtidos............................................................................................19 2.4. GEOMETRIA EPIPOLAR...............................................................................................19 2.4.1. Método dos 8 pontos ........................................................................................24 2.4.2. Método dos 7 pontos ........................................................................................24 2.4.3. Algoritmo de RANSAC.....................................................................................24 2.4.4. Algoritmo de LMedS.........................................................................................25 2.4.5. Algoritmo de MAPSAC.....................................................................................26 2.4.6. Determinação das linhas epipolares................................................................26 2.4.7. Métodos de cálculo da geometria epipolar considerados ...............................26 2.4.8. Resultados obtidos............................................................................................27 2.5. RECTIFICAÇÃO ..........................................................................................................29 2.5.1. Rectificação projectiva sem cálculo da geometria epipolar............................30 2.5.2. Resultados obtidos............................................................................................31 2.6. MAPA DE DISPARIDADE .............................................................................................32 2.6.1. Algoritmo de Stan Birchfield............................................................................34 2.6.2. Resultados obtidos............................................................................................35 CAPÍTULO 3. CONCLUSÕES E TRABALHO FUTURO........................... 37 3.1. CONCLUSÕES............................................................................................................. 38 3.2. TRABALHO FUTURO................................................................................................... 38 BIBLIOGRAFIA ............................................................................................ 39 Capítulo 1. Introdução 1 Introdução 1.1. Introdução à Visão Computacional Visão Computacional é a área da ciência que se dedica a desenvolver teorias e métodos e técnicas de extracção automática de informações úteis a partir de imagens (geométricas, topológicas, …), de forma o mais semelhante possível à realizada pelo ser humano no seu complexo sistema cognitivo visual. Tais imagens podem ser capturadas pelos mais diversos dispositivos, tais como câmaras de vídeo, scanners, etc. Por este motivo, a recente evolução tecnológica dos computadores digitais e dos dispositivos de aquisição de imagens, a preços cada vez mais reduzidos, tem possibilitado uma crescente aplicação da Visão Computacional nas mais diversas áreas [Coelho, 2003], como por exemplo: • Engenharia (prototipagem rápida, design, ...); • Realidade virtual (actores e objectos virtuais, sistemas de realidade aumentada, ...); • Medicina (estudos antropométricos, análise da evolução de deformações, desenvolvimento e fabrico de próteses, planeamento de cirurgias, ...); • Arquitectura (reconstrução de estruturas, esculturas, ...); • Sistemas de navegação (controlo de robots, aquisição automática de alvos, …); • Indústria (controlo de qualidade, …); • Sistemas de segurança (identificação e autenticação de pessoas por reconhecimento da íris, impressões digitais, entre outras informações biométricas, ...). É particularmente relevante ressaltar que, numa época em que a interacção com os computadores se torna cada vez mais frequente e necessária, a Visão Computacional permite considerar uma vasta área de interfaces mais eficazes, eficientes e intuitivas entre o mundo humano e o dos computadores, o que terá implicações revolucionárias tanto em termos tecnológicos e científicos como sociais. Tendo como precursor Larry Roberts [Roberts, 1963], estudante de doutoramento no MIT (Massachussets Institute of Technology) em 1962, foi só na década de 70 que se reconheceu a importância da Visão Computacional, principalmente no âmbito de determinação de parâmetros tridimensionais (3D). Com esta abertura, têm-se assistido, ao longo dos tempos ao aparecimento de novas técnicas que, directa ou indirectamente, permitiram obter das imagens mais informação, como o conhecimento das posições 3D 2 Introdução relativas a um determinado referencial ou orientações locais das superfícies captadas nas imagens [Shoaff, 2000]. As técnicas sem contacto para recuperar a geometria 3D de um objecto podem ser divididas em duas categorias [Coelho, 2003], Fig. 1: 1. Activas – requerem a projecção directa de energia (luz estruturada, ultra-sons, raios laser,...) sobre o objecto em análise ou utilizam o movimento da(s) câmara(s) ou do próprio objecto para obter informações sobre a sua forma 3D; 2. Passivas – não requerem a projecção de energia, usando apenas a iluminação ambiente existente, não necessitando de equipamentos especiais. São de aplicação mais geral mas, no entanto, a extracção de informação tridimensional é geralmente mais difícil. Fig. 1 - Divisão usual das técnicas sem contacto para obtenção de informação 3D de um objecto. 1.2. Reconstrução 3D do corpo humano Nos dias de hoje, a reconstrução tridimensional do corpo humano é um tópico de grande interesse, com utilização prática na indústria cinematográfica, realidade virtual ou em aplicações biomédicas. Os modelos 3D são normalmente obtidos utilizando scanners, geralmente dispendiosos mas simples de usar. Tais sistemas, utilizam tecnologias (tais como: luz estruturada, feixe laser, …) que providenciam um elevado número de pontos, utilizados 3 Plataforma Computacional 2.2. Extracção de pontos fortes O primeiro passo dos métodos de Visão 3D mais comuns é a detecção de pontos fortes numa imagem. Esses pontos são aqueles que têm uma componente 2D característica sobre o objecto; ou seja, são pontos que reflectem discrepâncias relevantes entre os seus valores de intensidades e os dos seus vizinhos; usualmente, são os vértices dos objectos. A sua extracção, permite posteriormente correlacioná-los sequencialmente noutras imagens e este emparelhamento torna possível a posterior reconstrução 3D. 2.2.1. Detector de Harris Numa imagem I em tons de cinzento, a matriz de covariância do gradiente, M , define-se pela seguinte equação: AC MCB ⎡ ⎤ = ⎢ ⎥ ⎣ ⎦, (1) sendo ( ) 2 A Ix=∂ ∂ , ( ) 2 B Iy=∂ ∂ e ( ) ( ) CIxIy = ∂∂ ∂∂ , com ( ) I x ∂ ∂ e ( ) I y∂∂ os gradientes da imagem I nas direcções x e , respectivamente, yFig. 5. Fig. 5 – Da esquerda para a direita: imagem original , resultado da derivada na direcção horizontal I ( ) Ix ∂ ∂ e vertical ( ) Iy ∂ ∂. Se os dois valores próprios da matriz M , 1 λ e 2 λ , forem elevados e similares em magnitude, significa que foi detectado um vértice, Fig. 6. Em 1988, Harris e Stephens [Harris, 1988], definiram a seguinte função de medida para a determinação de pontos fortes: 10 Plataforma Computacional Fig. 6 - Divisão do espaço dos valores próprios de M , para a detecção de pontos fortes ou fronteiras de objectos (imagem retirada de [Parks]). , (2) 2 det( ) (trace( ))RMkM=− onde 2 12 det( ) M AB C λλ ==− e 12 trace( ) M AB λ λ = +=+. Harris sugere , mas como usualmente este parâmetro necessita de ser estimado, Noble [Noble, 1989] sugeriu um re-arranjo da função de medida: 0.04k= det( )/( ( ) )RMtraceM ε =+ . (3) em que ε é uma constante ( ) utilizada de forma a evitar um denominador nulo no caso de -52 2x10 M ter traço nulo. Na Fig. 7, pode-se verificar o resultado da aplicação das funções de medida (2) e (3), sobre uma imagem em tons de cinzento. Em ambos os casos, se os valores próprios forem similares e elevados, det( ) M é muito maior que , logo o resultado será também elevado. Os máximos locais de serão os pontos fortes da imagem ()trace M R R I . De forma a minimizar os resultados obtidos, pode-se impor que seja superior a um dado valor de limiar (threshold). R Como este método é muito sensível ao ruído, usualmente aplica-se aos termos de M um filtro de suavização Gaussiano. Como este filtro introduz pontos fortes extra, tal pode ser compensado utilizando posteriormente um operador morfológico de dilatação. 11 Plataforma Computacional Fig. 7 – Da esquerda para a direita: imagem original, resultado da aplicação da equação (2) (imagem negada) e da equação (3) (imagem negada). 2.2.2. Métodos de extracção de pontos fortes considerados Na Fig. 8, estão visíveis os algoritmos actualmente disponíveis na plataforma computacional para a detecção de pontos fortes. Algoritmos disponíveis para a extracção de p ontos fortes Fig. 8 – Algoritmos disponíveis, na plataforma computacional, para a determinação de pontos fortes numa imagem. Os programas 1 e 2 utilizam o método de Harris. Ambos calculam M , utilizando o operador de gradiente Prewitt, : G . (4) 101 111 101, 0 0 0 101 1 1 1 xy G G − ⎡⎤⎡ ⎢⎥⎢ =− = ⎢⎥⎢ ⎢⎥⎢ − −−− ⎣⎦⎣ ⎤ ⎥ ⎥ ⎥ ⎦ O programa 1, utiliza a equação (3) para definir a função de medida e determina como pontos fortes R (, ) x y aqueles que satisfaçam a condição de threshold (, ) R xy t≥ e a condição (, ) (, ) R xy Dxy=, sendo a imagem após a dilatação de . DR Já o programa 2, usa a equação (2) com 0.04k = , elimina todos os píxeis que não são máximos numa janela de dimensão 33 × , e selecciona os pontos mais fortes. n 12 Plataforma Computacional Por outro lado, os programas 3 e 4 determinam os pontos fortes directamente dos valores próprios de M , utilizando para tal o operador de gradiente de Sobel: . (5) 101 1 2 1 202, 0 0 0 101 1 2 1 xy G G − ⎡⎤⎡ ⎢⎥⎢ =− = ⎢⎥⎢ ⎢⎥⎢ −−− ⎣⎦⎣ ⎤ ⎥ ⎥ ⎥ − ⎦ Para píxel (, ) x y da imagem I , determina 12 min( , ) λ λλ = , seleccionando os máximos numa vizinhança e eliminando os que não satisfaçam a condição de threshold ww× t λ ≥. O programa 3 selecciona os pontos (, ) x y que satisfaçam a condição (, ) (, ) x yDxy λ =, sendo a dilatação de (, )Dxy (, ) x y λ , e no final garante uma distância mínima entre os pontos fortes determinados. d Por seu lado, o programa 4 também garante uma distância mínima entre os pontos fortes encontrados e, no final, selecciona os n mais fortes. d 2.2.3. Resultados obtidos Nas Fig. 9 a Fig. 11, estão apresentados os resultados obtidos pelos programas 1 a 4, na extracção de pontos fortes nas imagens de teste consideradas. Como se pode observar, o programa 2 (Torr’s Matlab Toolkit) é o que apresenta piores resultados, principalmente pelo aparecimento de zonas com uma densidade muito elevada de pontos característicos, pois não garante uma distância mínima entre estes, tal como acontece com os programas 3 (OpenCV) e 4 (KLT). Esta propriedade pode ser relevante numa escolha criteriosa de pontos em zonas da imagem com variações de gradiente mais acentuadas. Embora o programa 1 (Peter’s Matlab Functions) não imponha uma distância mínima entre pontos, tal efeito é conseguido com o uso do operador morfológico de dilatação, obtendo-se assim resultados bastante razoáveis. 13 Plataforma Computacional Fig. 9 - As cruzes vermelhas assinalam os pontos fortes encontrados na imagem Tlm_1 (da direita para esquerda e de cima para baixo, são os resultados dos programas 1 a 4). Fig. 10 - As cruzes vermelhas assinalam os pontos fortes encontrados na imagem Rato_1 (da direita para esquerda e de cima para baixo, são os resultados dos programas 1 a 4). 14 Plataforma Computacional Fig. 11 - As cruzes vermelhas assinalam os pontos fortes encontrados na imagem Pc_1 (da direita para esquerda e de cima para baixo, são os resultados dos programas 1 a 4). Após a determinação dos pontos fortes, a plataforma apresenta ao utilizador a lista das coordenadas dos pontos fortes encontrados na primeira imagem do par estéreo, o algoritmo utilizado e os respectivos parâmetros de execução, Fig. 12. 2.3. Emparelhamento de pontos fortes entre imagens (matching) Na metodologia de reconstrução 3D considerada é necessário identificar os pontos 2D nas várias imagens que resultem da projecção do mesmo ponto da cena (matching). Geralmente um reduzido número de pontos de correspondência, é suficiente para se poder determinar uma relação geométrica entre duas imagens, ou seja, a matriz fundamental. A detecção automática das correspondências existentes entre os pontos fortes de duas imagens parcialmente sobrepostas, pode ser realizada através do cálculo de uma das várias medidas de matching existentes, medidas essas que, em geral, para cada ponto forte numa imagem I , calculam o grau de semelhança em toda uma imagem ou para todos os pontos fortes da imagem , sendo para isso analisada e comparada a envolvência de cada um desses pontos. J J 15 Plataforma Computacional Coordenadas dos pontos fortes encontrados na primeira imagem Número de pontos fortes obtidos Algoritmo utilizado e respectivos parâmetros Fig. 12 – Interface da plataforma computacional após a detecção de pontos fortes na primeira imagem. 2.3.1. Correlação simples Este método é usualmente conhecido como SSD (sum-of-square-differences). Considere-se o ponto [] x y mmm= da imagem I . O objectivo é encontrar o ponto [] x xyy mmdmdmd ′=+= + + na imagem tal que J() I m e ()Jm ′ sejam pontos similares. Tal obtém-se minimizando a função de dissimilaridade, definida como: . (6) 2 () ((,) ( , )) xy w Dd Ixy Jx d y d=−++ ∫∫ Um matching perfeito corresponde a obter () 0Dd = . Note-se que esta medida é efectuada numa região de tamanho ww × , denominada por janela de integração. Dado se tratar de uma medida não normalizada, este método é sensível a diferenças da iluminação das duas imagens I e , assim como é significativamente afectada por diferenças de contraste nas regiões de interesse. J 16 Plataforma Computacional 2.3.2. Correlação normalizada de média nula Os problemas encontrados no método anterior são superados se se normalizarem os vectores referentes às imagens, resultando no seguinte coeficiente de correlação: 22 ((, ) ).(( , ) )) () ((, ) ). (( , ) )) xy w xy ww Ixy I Jx d y d J Sd Ixy I Jx d y d J −++− =−++− ∫∫ ∫∫ ∫∫ , (7) onde I e J são os valores médios nas regiões de interesse definidas por . Este método é denominado por ZNCC (zero-mean normalized cross-correlation). Um matching perfeito corresponde a obter e quanto maior for este valor, mais forte é a correspondência entre as regiões de interesse nas duas imagens. w () 1Sd = 2.3.3. Algoritmo de Lucas-Kanade Este algoritmo assume que, se o vector de deslocamento [] x y ddd = for reduzido, a minimização da equação (6) resume-se a resolver o seguinte sistema de duas equações a duas incógnitas: 1 ., com x t W yt W I I deM e I I − ⎡ ⎤ ⎢ ⎥ == ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ∑ ∑, (8) sendo M a matriz de covariância do gradiente da primeira imagem (equação (1)), / x I Ix=∂ ∂ , / y I Iy=∂ ∂ e ( , ) ( , ) t I Ixy Jxy=−. Este algoritmo, é utilizado de uma forma iterativa: começa por obter uma estimativa de a partir de imagens suavizadas de baixa resolução (imagens piramidais), refinando os pontos de emparelhamento com imagens de resolução cada vez mais elevada, até que na última iteração se utilizam as imagens originais ([Lucas, 1981], [Bouguet, 1999]), d Fig. 13. 17 Plataforma Computacional Fig. 13 - Exemplo de construção de uma estrutura piramidal com 3 níveis, a partir da imagem original (à esquerda). 2.3.4. Métodos de emparelhamento de pontos considerados Após a determinação dos pontos fortes na primeira imagem, as funções de emparelhamento tornam-se disponíveis para o utilizador, Fig. 14. Algoritmos disponíveis para o emparelhamento de p ontos fortes Fig. 14 - Algoritmos disponíveis, na plataforma computacional, para o emparelhamento de pontos fortes entre um par de imagens estéreo. O programa 1 utiliza a medida de similaridade do método ZNCC, dada pela equação (7), e o programa 2, a medida de dissimilaridade do método SSD, dada pela equação (6). Ambos têm como parâmetros de entrada os pares de pontos fortes , obtidos nas duas imagens estéreo (, )mm ′ I e , aplicando a função de medida para cada par que satisfaça a condição J 2 mm d ′ −≤ ; ou seja, determinam um desvio máximo entre pontos de correspondência nas duas imagens, tornando assim menor o esforço computacional (o valor deve ser cuidadosamente escolhido). d Já os programas 3 e 4 utilizam o método de Lucas-Kanade (ver secção 2.3.3), necessitando somente do conjunto de pontos fortes encontrados na primeira imagem, do número de imagens piramidais n a usar, do número de iterações máximas para tentar m 18 Plataforma Computacional encontrar o vector de deslocamento d e do valor limite permitido para o resíduo (equação e (8)). 2.3.5. Resultados obtidos De forma a garantir uma comparabilidade mais adequada dos resultados obtidos pelas técnicas consideradas na plataforma para o emparelhamento de pontos fortes, foi utilizado o programa 4 (KLT) para seleccionar os 30 pontos fortes na primeira imagem, que são utilizados como parâmetros de entrada nesta fase da metodologia. Os resultados experimentais obtidos são apresentados nas Fig. 15 a Fig. 17. Nestes, pode-se observar que o emparelhamento de pontos fortes é uma fase crítica em Visão 3D. Em todos algoritmos considerados, verificam-se erros na correlação, sendo o programa 2 (Torr’s Matlab Toolkit) o que apresenta os piores resultados. Em relação às imagens de teste utilizadas, o pior caso é com as imagens “Rato”, pois o objecto em causa apresenta contornos curvilíneos e sem fortes contrastes, factores que complicam em muito o processo de emparelhamento. Após o emparelhamento dos pontos fortes, a aplicação apresenta ao utilizador a lista das coordenadas dos pontos obtidos na segunda imagem, Fig. 18. 2.4. Geometria epipolar Dado um par de imagens estéreo, qualquer ponto do espaço 3D define um plano P P π que contém o ponto e os centros ópticos e de ambas as câmaras. O plano Pl Or O P π é definido como plano epipolar e as linhas de intersecção deste plano com os planos das imagens são definidas como linhas epipolares conjugadas [Hartley, 2004], Fig. 19. A geometria epipolar corresponde à estrutura geométrica entre duas vistas e expressase matematicamente pela matriz fundamental , de dimensão 3 F3 × : 0 T mFm ′ = , (9) onde e são os pontos de correspondência entre duas imagens. O ponto , está sobre a linha epipolar l, definida por: mm′m lFm ′ = . (10) 19 Plataforma Computacional 2.4.5. Algoritmo de MAPSAC MAPSAC - Maximum A Posteriori Sample Consensus ([Torr, 2002]) redefine a equação (14) de forma a atribuir uma “penalidade” aos outliers e um “peso” aos inliers, consoante estes se adequam melhor ou pior à geometria do sistema: 2 i r2 t . (16). 222 2 ii i rrt wtotherwis ⎧≤ =⎨ ⎩e 2.4.6. Determinação das linhas epipolares Após ter sido determinada a matriz fundamental , a partir do emparelhamento de pontos fortes, a linha epipolar que passa pelo ponto na imagem F lm I pode ser obtida pela equação (10). 2.4.7. Métodos de cálculo da geometria epipolar considerados Na Fig. 20, estão visíveis os algoritmos considerados para o cálculo da matriz fundamental. Algoritmos que incluem o cálculo da matriz fundamental F Fig. 20 - Algoritmos disponíveis, na plataforma computacional, para o cálculo da matriz fundamental . F O programa 1 calcula a geometria epipolar usando o algoritmo de RANSAC, utilizando o método de 8 pontos para o cálculo das estimativas de em cada iteração. Termina quando Γ≥ F 99% (12), e recalcula , novamente pelo método de 8 pontos, utilizando somente os pontos inliers encontrados. F 26 Plataforma Computacional Já o programa 3, procede de igual forma mas fornece a possibilidade de optar entre o algoritmo de RANSAC ou LMedS. Por seu lado, o programa 2 utiliza o algoritmo de MAPSAC, sendo as estimativas iniciais de calculadas pelo método de 7 pontos. No final, após a determinação dos pontos inliers e outliers, é determinada pelo método de 8 pontos, tendo o cuidado de minimizar o erro introduzido pela presença de outliers [Torr, 2002]. F F Somente os programas 1 e 3 permitem representar, nas imagens dos resultados, as linhas epipolares obtidas pelos mesmos. 2.4.8. Resultados obtidos O cálculo da matriz fundamental (como uma opção extra nos parâmetros de cada função, F Fig. 21) encontra-se incluído no menu de emparelhamento, pois, como foi descrito anteriormente, os programas determinam os pontos inliers e outliers ao mesmo tempo que calculam . F Fig. 21 - Opção extra de determinação da matriz fundamental , inserida nas funções de emparelhamento de pontos entre imagens (da direita para a esquerda: programas 1, 2 e 3). F Após o cálculo da matriz fundamental , com a determinação dos pontos inliers e outliers, torna-se possível ao utilizador proceder à determinação das linhas epipolares nos pontos inliers, F Fig. 22. 27 Plataforma Computacional Algoritmos disponíveis para a determinação das linhas e p i p olares Fig. 22 - Algoritmos disponíveis, na plataforma computacional, para a determinação das linhas epipolares. A Fig. 23, apresenta os resultados obtidos pelos algoritmos considerados para a determinação das linhas epipolares. Fig. 23 - Linhas epipolares (a verde) e inliers (a azul) obtidos na primeira imagem de cada par de imagens de teste; da esquerda para a direita, resultado do programa 1 usando o algoritmo de Ransac, resultado do programa 1 usando o algoritmo de LMedS, e resultado do programa 2. 28 Plataforma Computacional Como os maus resultados obtidos pelo programa 2 (Torr’s Matlab Toolkit) apresentados nas secções 2.2.3 e 2.3.5 faziam prever, não foi possível obter a geometria epipolar utilizando os seus métodos (visto o número de outliers ser substancialmente superior aos inliers). Dos restantes programas, o que aparenta melhores resultados é o programa 3 (OpenCV), embora se note a necessidade de obter pontos de emparelhamento mais adequados no sentido de se conseguir melhores resultados na estimativa da geometria epipolar. Após o cálculo da geometria epipolar, a plataforma apresenta a matriz fundamental obtida, Fig. 24. Matriz fundamental calculada Fig. 24 - Interface da plataforma computacional após a determinação da geometria epipolar. 2.5. Rectificação Se a geometria epipolar, traduzida pela matriz fundamental, é conhecida, então é possível restringir o problema da correspondência de pontos entre duas imagens usando as linhas epipolares, utilizando a equação (10). Melhor ainda, se as imagens forem alteradas de forma a ficarem coplanares a um plano comum, as linhas epipolares tornam-se paralelas ao 29 Plataforma Computacional eixo horizontal da imagem: operação de rectificação, Fig. 25. Desta forma, torna-se mais fácil a resolução do problema posterior de emparelhamento denso entre imagens. Fig. 25 – Rectificação de duas imagens estéreo. 2.5.1. Rectificação projectiva sem cálculo da geometria epipolar Apresentado em 1999 por Francesco Isgrò e Emanuele Trucco [Isgrò, 1999], este é o algoritmo utilizado pelo programa 5, que é o único a realizar a operação de rectificação. Como o nome indica, este algoritmo rectifica duas imagens estéreo, sem para isso ser necessário a determinação da geometria epipolar, ou mais especificamente, da matriz fundamental. Assim, ao invés de determinar os pontos epipolares, e com eles determinar duas homografias H e H ′ que os mapeiem no infinito, como geralmente fazem os algoritmos de rectificação mais usuais [Hartley, 1998], este algoritmo explora o facto de a matriz fundamental F de um par de imagens rectificadas ter uma forma particular e bem conhecida: 00 0 00 1 01 0 F ⎡ ⎤ ⎢ ⎥ = − ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ . (17) Assim, obtidas as homografias de rectificação H e H ′ , é possível calcular a matriz fundamental , utilizando a equação: F T FHFH ′ = . (18). Combinando as equações (9) e (18), verifica-se que é possível obter H e H ′ directamente dos pontos de correspondência entre duas imagens, mesmo na presença de ruído e de outliers, minimizando a função de custo F: 30 Plataforma Computacional 2 1 (, ) [( ) ] NT i ii H HHmFHm = ′′′ =∑ F. (19) A minimização da equação (19), é um problema não-linear de minimização de mínimos quadrados, possível de resolver, por exemplo, com o algoritmo iterativo de Levenberg-Marquardt ([Press, 1992]), que necessita de uma boa estimação inicial de e para garantir convergência. Tal é obtido minimizando: 0 H 0 H′ 1 (, ) (( ) ) NT i i HH Hm FHm ρ = ′′′ =∑ R Fi , (20) em que ( ) log(1 1/ 2 ) ρ =+zz tem uma distribuição Lorentziana em imagens de baixa resolução. A partir de e , filtra-se os outliers rejeitando aqueles cujo resíduo é superior a 0 H0 H′i r { } 5.2 ii jj med r med r×−, com: 00 () T ii rHmFHm ′′ =i . (21) Obtidos e , itera-se a equação 0 H0 H′(19) em imagens de resolução cada vez mais elevada, até ser obtido H e H ′, a partir das quais F é calculada pela equação (18). 2.5.2. Resultados obtidos Como o programa 5 (Projective Rectification without Epipolar Geometry) necessita de alguns pontos de emparelhamento, para cada par de imagens estéreo experimentais, foi escolhido o método de emparelhamento de pontos fortes que obtivesse os melhores resultados. Os resultados obtidos estão apresentados na Fig. 26. Como se pode observar, ambas as imagens do par estéreo, sofrem uma distorção, que é proporcional à qualidade dos resultados obtidos no cálculo da geometria epipolar. Não foi possível proceder à rectificação do par de imagens Rato_1 e Rato_2, visto que as matrizes de homografia H e H′ da equação (18) determinadas pelo programa 5 eram nulas. 31 Plataforma Computacional Fig. 26 - Resultado da rectificação das imagens de teste pelo programa 5. 2.6. Mapa de disparidade Num sistema estéreo, a informação 3D de uma cena é representada pela disparidade entre duas imagens. Assim, o mapa de disparidade codifica a distância dos objectos em relação à(s) câmara(s), ou seja, pontos muitos distantes têm disparidade zero (geralmente 0, equivalente ao preto) e pontos muito próximos terão a máxima disparidade (geralmente 255, 32 Plataforma Computacional correspondente ao branco). Em resumo, um mapa de disparidade dá a percepção das descontinuidades em termos de profundidade de uma cena, Fig. 27. Fig. 27 - Disparidade entre dois pontos e mm ′ (localizados em imagens previamente rectificadas). Somente os programas 3 e 6, realizam esta operação, Fig. 28, utilizando o algoritmo de Stan Birchfield (descrito na secção seguinte), com a diferença de que o programa 6 também retorna um mapa de descontinuidades definido pelos píxeis que fazem fronteira entre uma mudança de pelo menos dois níveis de disparidade. Algoritmos disponíveis para o cálculo do mapa de dis p aridade Fig. 28 - Algoritmos disponíveis, na plataforma computacional, para a determinação do mapa de disparidade. 33 Plataforma Computacional 2.6.1. Algoritmo de Stan Birchfield Desenvolvido em 1999 [Birchfield, 1999], este algoritmo toma como ponto de partida duas imagens rectificadas. Primeiro, este algoritmo realiza um processo de emparelhamento denso, linha a linha na horizontal (daí a necessidade das imagens serem previamente rectificadas): o algoritmo mede a dissimilaridade entre os pontos, atribuindo a cada sequência de correspondências M um custo )(M γ , que traduz o quão improvável é que essa sequência seja uma correspondência correcta: 1 () (,) m N occ occ m r i i i M Nk Nk dmm γ = ′ =−+ ∑. (22) Nesta equação, os parâmetros e , representam o número de oclusões e de emparelhamentos, sendo e as respectivas constantes de “penalidade” e “recompensa”, e a dissimilaridade entre os píxeis e occ Nm N occ kr k ( , ) ii dmm ′i mi m ′ : (,)min{(,,,),(,,,)} ii ii ii dmm dmmII dmmI I ′′′′ =′ , (23) em que d é uma interpolação linear da intensidade da imagem entre dois píxeis [S. Birchfield, 1998]. Partindo do pressuposto de que descontinuidades são acompanhadas de variações na intensidade da imagem, são definidas restrições a cada sequência de correspondências M , tal como impor um limite máximo ao valor de . d Como a intensidade entre linhas de uma imagem não são independentes, também se realiza uma análise coluna a coluna no mapa de disparidades. Primeiro, a disparidade de um píxel, cujos vizinhos verticais tenham disparidade igual mas diferente dele próprio, torna-se igual à dos seus vizinhos. A seguir, para ambas as direcções, horizontal e vertical, utiliza-se o gradiente na direcção a estudar da imagem original para propagar regiões de confiança no mapa de disparidade. A confiança, para cada pixel, define-se como o número de píxeis contíguos na direcção a estudar com disparidade igual à sua. Posteriormente, o mapa de disparidade é filtrado com um filtro de média, nas duas direcções sequencialmente, de forma a preservar os vértices dos objectos. 34 Plataforma Computacional 2.6.2. Resultados obtidos Esta etapa foi testada com imagens, previamente rectificadas e indicadas pelo programa 6 (Depth Discontinuities by Pixel-to-Pixel Stereo), apresentadas na Fig. 29. Os resultados obtidos estão visíveis nas Fig. 30 e Fig. 31. Fig. 29 - Imagens originais utilizadas pelos programas 3 e 6 para realizar o emparelhamento denso. Fig. 30 - Mapas de disparidade (esquerda) e descontinuidade (direita) obtidos pelo programa 6. Fig. 31 - Mapa de disparidade obtido pelo programa 3. 35