( PDF ) Segmentação de planos baseada em homografia afim, fluxo óptico e reconstrução métrica

Download PDF

ads:

UNIVERSIDADE DO RIO GRANDE DO NORTEFEDERAL

UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE

CENTRO DE TECNOLOGIA

PROG. DE PÓS-GRAD. EM ENG. ELÉTRICA E DE COMPUTAÇÃO

Segmentação de Planos Baseada em Homograﬁa

Aﬁm, Fluxo Óptico e Reconstrução Métrica

Kelson Rômulo Teixeira Aires

Orientador: Prof. Dr. Adelardo Adelino Dantas de Medeiros

Tese de Doutorado apresentada ao Pro-

grama de Pós-Graduação em Engenharia

Elétrica e de Computação da UFRN (área de

concentração: Engenharia de Computação)

como parte dos requisitos para obtenção do

título de Doutor em Ciências.

Número de ordem PPgEE: D050

Natal-RN / Outubro de 2009

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

ads:

Resumo

Planos são importantes componentes geométricos e podem ser utilizados em uma

larga variedade de tarefas de visão como reconstrução de cenas e navegação de robôs.

É proposto neste trabalho um sistema de segmentação de planos baseado no cálculo de

homograﬁas, na estimação do ﬂuxo óptico e na reconstrução métrica. Primeiramente,

usando duas imagens de uma sequência monocular, um conjunto de pares de pontos de

interesse correspondentes é obtido. Um algoritmo foi desenvolvido para agrupar pontos

de interesse pertencentes ao mesmo plano baseado no erro de reprojeção da homograﬁa

aﬁm. Em seguida, a informação do ﬂuxo óptico estimado é utilizada na expansão dos

planos detectados. Um novo método de estimação de ﬂuxo óptico baseado na informação

de cor é proposto. O próximo passo consiste na extração da geometria epipolar da cena.

A matriz fundamental é estimada utilizando um procedimento iterativo para descartar cor-

respondências espúrias. Assumindo o sistema calibrado a priori, as matrizes da câmera

são computadas a partir da matriz essencial. Finalmente, os pontos são triangulados e

a reconstrução métrica dos principais planos da cena é obtida. Testes foram executados

em diferentes sequências de imagens capturadas em ambientes internos e externos, e os

resultados são apresentados e discutidos.

Palavras-chave: visão computacional, segmentação de planos, ﬂuxo óptico, homo-

graﬁa aﬁm, reconstrução 3D.

Abstract

Planes are important geometric features and can be used in a wide range of vision

tasks like scene reconstruction and robot navigation. This work aims to illustrate a plane

segmentation method based on homography computation, optical ﬂow estimation and

metric reconstruction. Firstly, using two image frames from a monocular sequence, a

set of match pairs of interest points is obtained. An algorithm was developed to cluster

interest points belonging to the same plane based on the reprojection error of the afﬁne

homography. Following this, the estimated optical ﬂow is used to expand each detected

plane. A new optical ﬂow estimation method based on color information is presented. The

nextstepconsistsof to extracttheepipolargeometryof the scene. The fundamental matrix

is estimated using an iterative procedure to discard outliers. Assuming that the system

was calibrated, the camera matrices are computed from the essential matrix. Finally, the

clustered points are triangulated to reconstruct all major planes of the scene. Tests were

performed in different sequences of indoor and outdoor images and results are shown.

Keywords: computer vision, plane segmentation, optical ﬂow, afﬁne homography,

3D reconstruction.

Sumário

Sumário i

Lista de Figuras iii

Lista de Tabelas vii

Lista de Algoritmos ix

Lista de Publicações xi

1 Introdução 1

1.1 Sistema de Visão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.1.1 Módulo de Aquisição . . . . . . . . . . . . . . . . . . . . . . . . 2

1.1.2 Módulo de Processamento . . . . . . . . . . . . . . . . . . . . . 5

1.2 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.4 Visão Geral do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.4.1 Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.5 Organização do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 Detecção do Movimento Inerente a uma Cena 15

2.1 Detecção e Correspondência de Pontos de Interesse . . . . . . . . . . . . 16

2.1.1 Detecção de Pontos de Interesse . . . . . . . . . . . . . . . . . . 16

2.1.2 Descritor Local . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.1.3 Considerações Adicionais . . . . . . . . . . . . . . . . . . . . . 19

2.1.4 Testes e Resultados . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2 Fluxo Óptico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.2.1 Classiﬁcação dos Algoritmos de Fluxo Óptico . . . . . . . . . . . 26

2.2.2 Técnicas Diferenciais . . . . . . . . . . . . . . . . . . . . . . . . 29

2.2.3 Considerações Adicionais . . . . . . . . . . . . . . . . . . . . . 33

2.2.4 Fluxo Óptico a partir da Informação de Cor . . . . . . . . . . . . 34

2.2.5 Método Proposto . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.2.6 Testes e Resultados . . . . . . . . . . . . . . . . . . . . . . . . . 39

3 Geometria de Duas Imagens 51

3.1 Pontos e Retas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.2 Modelo da Câmera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.2.1 Câmera CCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.3 Homograﬁa Planar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.3.1 Homograﬁa Aﬁm . . . . . . . . . . . . . . . . . . . . . . . . . . 58

3.4 Estimação da Homograﬁa Planar . . . . . . . . . . . . . . . . . . . . . . 58

3.4.1 Transformação Linear Direta (DLT) . . . . . . . . . . . . . . . . 59

3.4.2 RANSAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

3.4.3 Estimação da Homograﬁa usando o Modelo Aﬁm . . . . . . . . . 63

3.4.4 Erro de Reprojeção . . . . . . . . . . . . . . . . . . . . . . . . . 64

3.5 Geometria Epipolar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

3.5.1 Matriz Fundamental . . . . . . . . . . . . . . . . . . . . . . . . 65

3.5.2 Estimação da Matriz Fundamental . . . . . . . . . . . . . . . . . 67

3.5.3 Matriz Essencial . . . . . . . . . . . . . . . . . . . . . . . . . . 75

3.6 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

4 Sistema Proposto 79

4.1 Diagrama de Blocos do Sistema Proposto . . . . . . . . . . . . . . . . . 79

4.2 Detecção e Expansão dos Planos 2D . . . . . . . . . . . . . . . . . . . . 80

4.2.1 Detecção de Correspondências . . . . . . . . . . . . . . . . . . . 81

4.2.2 Detecção dos Planos . . . . . . . . . . . . . . . . . . . . . . . . 82

4.2.3 Expansão dos Planos . . . . . . . . . . . . . . . . . . . . . . . . 85

4.2.4 Testes e Resultados . . . . . . . . . . . . . . . . . . . . . . . . . 88

4.3 Reconstrução Métrica dos Planos Identiﬁcados . . . . . . . . . . . . . . 96

4.3.1 Extração da Geometria Epipolar . . . . . . . . . . . . . . . . . . 96

4.3.2 Recuperação dos Parâmetros de Movimento . . . . . . . . . . . . 97

4.3.3 Restrição de Posicionamento e Reconstrução 3D . . . . . . . . . 97

4.3.4 Testes e Resultados . . . . . . . . . . . . . . . . . . . . . . . . . 100

4.4 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

5 Conclusões e Trabalhos Futuros 107

Referências Bibliográﬁcas 110

Lista de Figuras

1.1 Sistema de Visão. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Olho Humano. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3 Modelo de câmera Pinhole. . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.4 Ilusão de Muller-Lyer. . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.5 Interpretação ambígua da imagem baseada em formas de segmentação. . . 6

1.6 Diagrama de blocos simpliﬁcado do sistema proposto. . . . . . . . . . . . 12

2.1 Descritor SIFT calculado a partir de um conjunto de 8×8 pixels divididos

em 2×2 sub-regiões. Cada histograma do descritor possui 8 intervalos de

orientação. O descritor é representado por um vetor de 32 elementos (2×

2×8). O comprimento de cada seta na ﬁgura do lado direito corresponde

à soma das magnitudes dos gradientes próximos àquela direção dentro de

cada sub-região. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2 Exemplos de imagens utilizadas no experimento. . . . . . . . . . . . . . 20

2.3 Resultado da busca por correspondências. Os pontos detectados estão

marcados em vermelho. Retas azuis deﬁnem as correspondências, e os

pontos marcados em verde são correspondências falso-positivas. . . . . . 22

2.4 Pontos de interesse detectados que se repetem nas três imagens de cada

cena. Os pontos estão destacados em vermelho no primeiro quadro de

cada sequência. Os pontos marcados em verde são correspondências

falso-positivas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.5 Vetores do Fluxo Óptico. . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.6 (a) Exemplo de um quadro da sequência de imagens. (b) Fluxo óptico

estimado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.7 Determinação do Movimento de um pixel baseada em correlação. . . . . 27

2.8 Problema da Abertura. O movimento do objeto é descrito por v. No

ponto q, onde a variação de intensidade é unidimensional, o movimento é

ambíguo, podendo ser interpretadocomo contrário a v. Sob tais condições

o problema é mal-condicionado, e sem restrições locais adicionais não

pode ser corretamente determinado. . . . . . . . . . . . . . . . . . . . . 30

iii

2.9 Os pixels de cor preta são utilizados no cálculo do ﬂuxo óptico da região. 37

2.10 Porção do quadro da imagem com 09 regiões N ×N. O vetor de ﬂuxo da

região central é aceito como válido por existir dentre seus vizinhos, pelo

menos um com vetor de ﬂuxo que satisfaz as condições do ﬁltro. . . . . . 38

2.11 Exemplos de imagens utilizadas nos testes. . . . . . . . . . . . . . . . . 39

2.12 Histograma de ângulos e gráﬁco que ilustra a relação entre o número de

condição, ângulo entre os gradientes dos canais de cores e a quantidade

de pixels (eixo vertical). Resultados para a imagem da Figura 2.11a, uti-

lizando o modelo de cor HSV. . . . . . . . . . . . . . . . . . . . . . . . 41

2.13 Histograma de ângulos e gráﬁco que ilustra a relação entre o número de

condição, ângulo entre os gradientes dos canais de cores e a quantidade

de pixels (eixo vertical). Resultados para a imagem da Figura 2.11a, uti-

lizando o modelo de cor RGB normalizado. . . . . . . . . . . . . . . . . 42

2.14 Histograma de ângulos e gráﬁco que ilustra a relação entre o número de

condição, ângulo entre os gradientes dos canais de cores e a quantidade

de pixels (eixo vertical). Resultados para a imagem da Figura 2.11a, uti-

lizando o modelo de cor YUV. . . . . . . . . . . . . . . . . . . . . . . . 43

2.15 Histograma de ângulos e gráﬁco que ilustra a relação entre o número de

condição, ângulo entre os gradientes dos canais de cores e a quantidade

de pixels (eixo vertical). Resultados para a imagem da Figura 2.11b, uti-

lizando o modelo de cor HSV. . . . . . . . . . . . . . . . . . . . . . . . 44

2.16 Histograma de ângulos e gráﬁco que ilustra a relação entre o número de

condição, ângulo entre os gradientes dos canais de cores e a quantidade

de pixels (eixo vertical). Resultados para a imagem da Figura 2.11b, uti-

lizando o modelo de cor RGB normalizado. . . . . . . . . . . . . . . . . 45

2.17 Histograma de ângulos e gráﬁco que ilustra a relação entre o número de

condição, ângulo entre os gradientes dos canais de cores e a quantidade

de pixels (eixo vertical). Resultados para a imagem da Figura 2.11b, uti-

lizando o modelo de cor YUV. . . . . . . . . . . . . . . . . . . . . . . . 46

2.18 Exemplos de imagens utilizadas nos testes. . . . . . . . . . . . . . . . . 47

2.19 Resultados para a imagem 2.18a . . . . . . . . . . . . . . . . . . . . . . 48

2.20 Resultados para a imagem 2.18b. . . . . . . . . . . . . . . . . . . . . . . 48

3.1 Geometria da câmera pinhole. C é o centro da câmera e p o ponto princi-

pal. O centro da câmera está localizado na origem do sistema de coorde-

nadas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.2 Transformação Euclidiana entre o sistema de coordenadas do mundo e o

sistema de coordenadas da câmera. . . . . . . . . . . . . . . . . . . . . . 55

3.3 Considere duas imagens I e I

′

do mesmo plano π, a homograﬁa planar H

consiste em um mapeamento dos pontos q da imagem I para os pontos q

′

da imagem I

′

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

3.4 Plano epipolar: o ponto Q, os centros ópticos C e C

′

das duas câmeras, e

as duas imagens q e q

′

de Q estão sobre o mesmo plano. . . . . . . . . . 64

3.5 Entre as ﬁguras dos lados direito e esquerdo existe uma linha-base re-

versa. Entre as ﬁguras de cima e de baixo, a câmera

′

está rotacionada

180

em torno da linha-base. Perceba que apenas em (a) o ponto recons-

truído está em frente das duas câmeras. . . . . . . . . . . . . . . . . . . . 78

4.1 Diagrama de blocos detalhado do sistema proposto. . . . . . . . . . . . . 80

4.2 Exemplos de imagens utilizadas nos experimentos. . . . . . . . . . . . . 89

4.3 (a) Resultado da triangulação de Delaunay a partir do conjunto de pontos

de interesse detectados na Primeira imagem. (b) Conjunto de triângulos

resultante após o procedimento de ﬁltragem. . . . . . . . . . . . . . . . . 90

4.4 Resultado do procedimento de detecção de planos para as imagens da

Figura 4.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

4.5 Resultado do procedimento de expansão de planos. . . . . . . . . . . . . 93

4.6 Resultado do processo de detecção e expansão de planos para os quadros

1, 9, 16 e 23 de uma sequência. . . . . . . . . . . . . . . . . . . . . . . . 95

4.7 Resultado do processo de detecção e expansão de planos para os quadros

1, 11, 21 e 31 de uma sequência. . . . . . . . . . . . . . . . . . . . . . . 95

4.8 Gráﬁco do erro mediano obtido no processo iterativo de estimação da

matriz fundamental. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

4.9 Posição 3D estimada, deﬁnida por um fator de escala, dos pontos corres-

pondentes para as imagens de cenas internas ilustradas nas Figuras 4.2a

e 4.2b. O ponto vermelho ilustra a posição da câmera no momento da

aquisição do primeiro quadro. . . . . . . . . . . . . . . . . . . . . . . . 102

4.10 Posição 3D estimada, deﬁnida por um fator de escala, dos pontos corres-

pondentes para as imagens de cenas externas ilustradas nas Figuras 4.2d

e 4.2e. O ponto vermelho ilustra a posição da câmera no momento da

aquisição do primeiro quadro. . . . . . . . . . . . . . . . . . . . . . . . 103

4.11 Posição 3D estimada, deﬁnida por um fator de escala, dos pontos cor-

respondentes para o primeiro quadro das sequências ilustradas nas Figu-

ras 4.6 e 4.7. O ponto vermelho ilustra a posição da câmera no momento

da aquisição do primeiro quadro. . . . . . . . . . . . . . . . . . . . . . . 104

Lista de Tabelas

2.1 Número de pontos de interesse detectados nas três imagens de cada cena. 21

2.2 Número de pares de pontos correspondentes e medidas falso-positivas

computadas a partir dos pares de imagens consecutivas de cada cena. . . . 21

2.3 Número de pontos de interesse detectados que se repetem nas três ima-

gens de cada cena. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.4 Erro de magnitude (pixel) e erro angular (graus) do ﬂuxo óptico estimado

em movimentos de zoom e deslocamento da câmera para as imagens da

Figura 2.11. O ﬂuxo óptico foi estimado utilizando o método de Lucas

e Kanade (L&K) para imagens em preto e branco (P&B), e o método

proposto utilizando três sistemas de cores: HSV, YUV e nRGB. . . . . . 40

4.1 Dados referentes ao processo de detecção de pontos de interesse, e busca

por pares de pontos correspondentes entre as duas imagens. Pontos de

interesse detectados no primeiro e segundo quadros da sequência (Q1 e

Q2), quantidade de pares de pontos correspondentes e número de corres-

pondências falso-positivas. . . . . . . . . . . . . . . . . . . . . . . . . . 90

4.2 Dados referentes ao processo de detecção de planos baseada no cálculo

da homograﬁa: quantidade de pontos detectados em cada plano, número

de pontos descartados e número de pontos classiﬁcados de forma errônea. 91

4.3 Erro (%), medidas falso-positivas FP (%) e falso-negativas FN (%) obti-

das no processo de expansão de planos para as imagens da Figura 4.5. . . 94

4.4 Erro (%), medidas falso-positivas FP (%) e falso-negativas FN (%) obti-

das no processo de expansão de planos para as imagens da Figura 4.6. . . 94

4.5 Erro (%), medidas falso-positivas FP (%) e falso-negativas FN (%) obti-

das no processo de expansão de planos para as imagens da Figura 4.7. . . 94

vii

Lista de Algoritmos

3.1 Algoritmo RANSAC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

4.1 Algoritmo de busca por pares de pontos correspondentes entre duas ima-

gens. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

4.2 Algoritmo de obtenção e ﬁltragem de triângulos. . . . . . . . . . . . . . 83

4.3 Algoritmo para escolha da homograﬁa inicial do procedimento de detec-

ção de planos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

4.4 Algoritmo de detecção dos planos de uma cena. . . . . . . . . . . . . . . 86

4.5 Algoritmo para expansão dos planos detectados na cena. . . . . . . . . . 87

Lista de Publicações

Aires, Kelson R. T. e Adelardo A. D. de Medeiros (2007), Estimação do ﬂuxo óptico com

a adição de informação de cor, nos ‘Anais do VIII Simpósio Brasileiro de Automação

Inteligente’, Florianópolis, SC, Brazil.

Aires, Kelson R. T., Andre M. Santana e Adelardo A. D. Medeiros (2008), Optical ﬂow

using color information: preliminary results, in ‘Proceedings of the 2008 ACM Sympo-

sium on Applied Computing’, ACM, Fortaleza, CE, BRA, pp. 1607–1611.

Aires, Kelson R. T. e Helder de J. Araújo (2008), Optical ﬂow estimation using color

information: study and results, in ‘Proceedings of V Congresso Luso-Moçambicano de

Engenharia’, Maputo, Moçambique.

Aires, Kelson R. T., Helder de J. Araújo e Adelardo A. D. de Medeiros (2007), Plane de-

tection using afﬁne homography, nos ‘Anais do XVII Congresso Brasileiro de Automática

- CBA2008’, Juiz de Fora, MG, Brazil.

Aires, Kelson R. T., Helder de J. Araújo e Adelardo A. D. de Medeiros (2008), Plane

detection from monocular image sequences, in ‘Proceedings of 8th IASTED International

Conference on Visualization and Image Processing - VIIP2008’, ACTA Press, Mallorca,

Spain.

Aires, Kelson R. T., Helder de J. Araújo e Adelardo A. D. de Medeiros (2009), Segmenta-

tion of 3d planes based on afﬁne homographies and metric reconstruction, in ‘Image and

Vision Computing’ - In Review.

Aires, Kelson, Helder Araújo e Adelardo Medeiros (2010), A plane segmentation system

based on afﬁne homography and optical ﬂow, in ‘International Conference of Robotic and

Automation - ICRA2010’ - In Review.

Capítulo 1

Introdução

O termo Robótica, introduzido por Isaac Asimov [Medeiros 1998], surgiu como uma

forma de simbolizar a ciência dedicada ao estudo dos robôs. Desde então, pesquisadores

sonham com a possibilidade de desenvolver máquinas autônomas, substitutas dos seres-

humanos, capazes de executar tarefas complexas. Com o objetivo de tornar os robôs

cada vez mais autônomos, pesquisadores começaram a pensar em formas de desenvolver

sistemas sensoriais capazes de fornecer a maior quantidade possível de informação útil

sobre o mundo ao seu redor. Alguns dos sistemas que incorporam esta característica são os

sistemas de Visão Artiﬁcial. Com isto, surgiu a Visão Computacional, que consiste naárea

da ciência dedicada a desenvolver teorias e técnicas voltadas à extração e processamento,

em tempo-real, de informações úteis contidas em imagens [Russel e Norvig 1995].

Com o desenvolvimento tecnológico, a Visão Computacional tem se tornado uma área

cada vez mais atraente para a pesquisa cientíﬁca. A Visão Computacional pode ser vista

como uma entidade de automação e integração de uma larga extensão de processos e re-

presentações usados na percepção, incluindo técnicas como processamento de imagens

e classiﬁcação de padrões. Não menos importantes são as técnicas de modelagem geo-

métrica e processamento cognitivo, já que objetivo e conhecimento são fatores de alto

nível que podem guiar as atividades visuais, e um bom sistema de visão deve tirar pro-

veito disso. Isto constitui apenas parte da visão, já que a própria também requer muitas

características de baixo nível como, por exemplo, habilidade em extrair informações de

cor e luminosidade do ambiente detectado. Outro importante fator é a percepção e o

reconhecimento do objeto, que consiste em comparar modelos do ambiente com mode-

los conhecidos. Desta forma, a Visão Computacional depara-se com o fato de ter que

reinventar constantemente até mesmo o mais básico e ainda inacessível talento do tão

especializado, paralelo e analógico sistema de visão biológico [Forsyth e Ponce 2002].

Atualmente, é bastante comum a utilização de robôs orientados por marcos artiﬁcais

construídos em ambientes chamados de estáticos. O surgimentodeobstáculosno caminho

CAPÍTULO 1. INTRODUÇÃO

do robô, ou situações que impeçam a detecção de tais marcos, podem em algum momento

desorientar o robô. Além disso, o alto custo na construção desses ambientes constitui

uma barreira para este tipo de navegação de robôs, conhecida como "semi-autônoma".

Em vista desses problemas, surge a necessidade de criar mecanismos que aumentem o

grau de autonomia dos robôs, possibilitando uma melhoria na detecção de obstáculos, e

na geração e execução de trajetórias.

1.1 Sistema de Visão

Os sistemas sensoriais geralmente caracterizam-se pelo seu alto custo. Em alguns

casos, esse custo está relacionado ao fator ﬁnanceiro; em outros, as técnicas de processa-

mento dos dados fornecidos pelos sensores tendem a possuir elevado custo computacio-

nal. Ao fazer a opção por reduzir custos ﬁnanceiros de projeto, o projetista deve optar

por tentar melhorar a eﬁciência computacional dos métodos de processamento dos dados

sensoriais. Entenda-se eﬁciência como quão rápido seja a análise dos dados, e posterior

fornecimento dos resultados ao sistema de controle.

A visão é um dos mais importantes sentidos que guiam a interação dos seres com

o mundo. Os possíveis usos da visão são: manipulação, navegação e reconhecimento

de objetos. Basicamente, um sistema de visão computacional é formado pelo módulo

de aquisição de dados e pelo módulo de processamento, como ilustrado na Figura 1.1.

O módulo de aquisição de dados, que tem como componente principal a câmera, é o

responsável por fornecer os dados sensoriais de entrada ao módulo de processamento,

que por sua vez, processa esses dados e fornece parâmetros necessários ao sistema de

controle do robô.

1.1.1 Módulo de Aquisição

Os primeiros estudos sobre visão humana datam da época de Aristóteles. Conside-

rado o criador do pensamento lógico, Aristóteles foi um grande sábio, ﬁlósofo e cientista

que viveu na Grécia antiga por volta do século IV A.C.. Dentre seus diversos trabalhos

cientíﬁcos, Aristóteles explicou que no processo de visão humana, o objeto sendo obser-

vado, de alguma forma, alterava o meio (ar) entre o objeto e o observador. Esta alteração

era propagada ao olho, permitindo o objeto ser visto. Durante a Idade Média a teoria de

Aristóteles foi revertida. A teoria popular da época sugeria que os olhos do observador re-

alizavam emissões ao objeto, e tais emissões faziam com que a visão ocorresse. Tal teoria

não se baseava em dados cientíﬁcos como os disponíveis hoje em dia, e sim em observa-

1.1. SISTEMA DE VISÃO

Sistema de

Controle

Sistema de Visão

Cena 3D

Módulo de

Aquisição

Módulo de

Processamento

Figura 1.1: Sistema de Visão.

ções e conclusões dos sábios da época. Graças aos conhecimentos passados de geração

em geração, e aos estudos cada vez mais aprofundados sobre o assunto, o funcionamento

da visão humana está decifrado.

A visão humana necessita que diversos componentes do olho e do cérebro trabalhem

juntos para seu perfeito funcionamento. Apesar de sua forma globular, o olho humano

é funcionalmente idêntico a uma câmera, com um campo visual de 160

de largura por

135

de altura, aproximadamente. Dentre os componentes do olho humano, ilustrado na

Figura 1.2, os principais são: a córnea, a íris, a pupila, o cristalino e a retina. A córnea é

uma janela refrativa, transparente e altamente curvilínea que permite a entrada de luz no

olho antes de ser parcialmente bloqueada por uma superfície opaca e colorida, chamada

de íris. O cristalino é um tipo de lente presente no olho, e está situado atrás da pupila,

com a função de direcionar o feixe de luz até a retina. A retina, situada na parte de trás

do olho, é composta de células nervosas sendo responsável por levar a imagem através do

nervo óptico ao cérebro [Forsyth e Ponce 2002].

De forma análoga ao funcionamento doolho humano, a formação daimagem acontece

quando o sensor da câmera registra a radiação que interagiu com objetos físicos. Dessa

forma, o brilho de um determinado ponto na imagem está relacionado com a quantidade

de luz irradiada por aquele ponto da superfície observada. O sistema de aquisição de

imagens mais simples é o dispositivo pinhole. Esta câmera possui um pequeno orifício

por onde passa a luz, formando uma imagem geometricamente invertida no plano vertical

oposto no interior do dispositivo, o plano da imagem. O modelo pinhole é ilustrado na

Figura 1.3.

CAPÍTULO 1. INTRODUÇÃO

Figura 1.2: Olho Humano.

Objeto

Imagem

Virtual

Imagem

d d

Orifício

Figura 1.3: Modelo de câmera Pinhole.

1.1. SISTEMA DE VISÃO

Na realidade, as câmeras atuais possuem lentes e apresentam um grau de complexi-

dade bem maior que o modelo pinhole. Apesar de sua simplicidade, o modelo pinhole é

bastante aceitável no processo de modelagem da aquisição de imagens. Como a imagem

produzida pelo modelo pinhole é uma imagem geometricamente invertida, é conveniente

considerar uma imagem localizada em um plano virtual. De acordo com a Figura 1.3,

o plano virtual está localizado à frente da câmera pinhole, a uma distância d, igual à

distância entre o orifício do modelo e o plano de projeção no interior da câmera.

As câmeras podem ser diferenciadas basicamente pelo tipo de sensor utilizado. Desde

o surgimento do modelo pinhole, o avanço tem sido signiﬁcativo. Hoje em dia são comuns

as câmeras com dispositivo sensorial CCD (Charge Coupled Device). Câmeras com este

tipo de sensor utilizam uma grade retangular coletora de elétrons capaz de armazenar uma

informação sobre a quantidade de luz incidente a cada período ﬁxo de tempo. Câmeras

CCD coloridas, assim como o olho humano, utilizam três tipos de sensores: um para o

vermelho, um para o verde e um para o azul [Forsyth e Ponce 2002].

O sinal digital fornecido na entrada do módulo de processamento, ou seja, a imagem

digital, é uma matriz de valores inteiros que representam o brilho em cada ponto discreto

do plano da imagem, em um valor de tempo também discreto. Em uma câmera CCD, o

plano da imagem corresponde a uma matriz, onde cada ponto dessa matriz é chamado de

pixel. Cada pixel pode assumirvalor entre 0 (preto) e 255 (branco), para o caso de imagens

em nível de cinza utilizando uma codiﬁcação de 8 bits. No caso do uso de cor, cada

imagem é representada por três matrizes de valores, ou seja, cada pixel é representado por

três valores no intervalo de 0 a 255. Tais valores especiﬁcam a contribuição de cada uma

das componentes na formação da cor resultante do pixel.

Em robótica, uma ou mais câmeras podem ser utilizadas como dispositivos de sensori-

amento, dependendo da aplicação em questão. Caldeira (2002) utilizou somente uma câ-

mera como dispositivo sensorial para a navegação de umrobô móvel. Piazzi e Prattichizzo

(2006) utilizaram um sistema de visão estéreo para detectar planos a partir de correspon-

dências de pontos entre duas imagens. Existem ainda trabalhos que utilizam sistema de

visão trinocular para navegação de robôs em ambientes internos [Kim e Cho 2006].

1.1.2 Módulo de Processamento

Uma importante característica do sistema de visão humano é que a forma como um

objeto é visto pode ser alterada pelo contexto em que está inserido. Como exemplo, a

famosa ilusão de Muller-Lyer. Na Figura 1.4 as duas retas horizontais possuem o mesmo

tamanho, mas provocam uma ilusão surpreendente. Elas aparentam ter tamanhos diferen-

CAPÍTULO 1. INTRODUÇÃO

Figura 1.4: Ilusão de Muller-Lyer.

tes devido à disposição das setas em cada uma.

A Segmentação é uma tarefa importante na organização da imagem em porções de pi-

xels que correspondam a entidades presentes em determinada cena, tendo como principal

motivação, a obtenção de uma representação compacta da informação útil presente em

uma imagem. Em aplicações de reconhecimento de objetos a segmentação é útil na com-

paração de determinada porção da imagem com um banco de dados pré-armazenado. Na

navegação de robôs, a segmentação da imagem pode ser responsável por encontrar rotas

livres de colisão, bem como a identiﬁcação de obstáculos em determinado ambiente.

Uma experiência simples de segmentação é a forma como uma imagem pode ser in-

terpretada. A Figura 1.5 pode apresentar duas interpretações distintas. Pode ser vista uma

circunferência branca sobre um plano de fundo negro, bem como um retângulo negro com

um furo circular sobre um plano de fundo branco.

Figura 1.5: Interpretação ambígua da imagem baseada em formas de segmentação.

A segmentação pode ser feita baseada em diversas técnicas, e geralmente assumindo

a existência de fatores que, de alguma forma, conectam os pixels de uma imagem. Tais

fatores podem ser: proximidade, similaridade, paralelismo, simetria, continuidade, ou

alguma forma de conﬁguração familiar, como movimentos similares de pixels. Sendo

assim, a segmentação é efetuada e interpretada com base no tipo de dado fornecido como

1.2. MOTIVAÇÃO

parâmetro de entrada. Como exemplo, o tipo de dado mencionado pode ser um campo

de vetores que descreve o movimento de cada pixel na imagem, após ser analisada uma

determinada sequência de quadros. Neste caso, a segmentação produziria campos de

vetores similares, ou seja, uma segmentação de movimentos. Cada segmento poderia ser

interpretado como um objeto, já que pixels de um mesmo objeto tendem a apresentar

movimento de acordo com o movimento do objeto em questão. Dentre outras utilidades

da segmentação com aplicação na área de visão robótica, encontram-se principalmente a

detecção de objetos, a subtração do plano de fundo da imagem e a detecção do plano do

chão onde o robô se movimenta.

1.2 Motivação

Visão Computacional ainda é um campo de pesquisa bastante ativo na comunidade

cientíﬁca. Muitos pesquisadores justiﬁcam o barateamento e a simplicidade do projeto

como fatores preponderantes no uso de tais técnicas. Em algumas situações, estes fatores

podem comprometer a eﬁciência e qualidade dos resultados obtidos e, por consequência,

a segurança envolvida na aplicação do sistema.

Os sistemas de visão utilizam sensores, além de mais baratos, passivos. Em deter-

minados ambientes, a atividade dos sensores (emissão de luz infravermelha ou pulsos

de ultrasom, por exemplo) poderia interferir no estado do sistema. Isto não ocorre com

os sensores dos sistemas de visão, daí sua passividade. Além disso, outra vantagem no

uso de sistemas de visão reside no fato de que a quantidade de informação acerca do

ambiente, disponível em uma imagem, é bem maior que as informações fornecidas pe-

los demais tipos de sensores. Mesmo com todas essas características, sistemas práticos

de visão em tempo-real aplicados a extração de informações do ambiente continuam a

ser objeto de intenso estudo na comunidade cientíﬁca. O problema no uso deste tipo de

sensor é que o processamento de imagens é computacionalmente caro e, dependendo das

técnicas utilizadas, pode ser impreciso.

A extração de informação visual obteve mais atenção a partir do surgimento, poucos

anos atrás, das webcam’s devido a seu baixo custo frente aos demais sensores. Técnicas

que utilizam um sistema sensorial baseado em duas câmeras (visão estéreo) são suﬁcien-

temente expressivas pelo uso de relações geométricas entre tais câmeras, mas necessitam

de calibração complexa, enquanto a robustez a variações de iluminação e a eﬁciência

quanto ao tempo de processamento não são garantidas.

Os sistemas de visão computacional são cada vez mais utilizados na realização de

tarefas que requerem uma rica fonte de informação, e o estado da arte de dispositivos

CAPÍTULO 1. INTRODUÇÃO

computacionais torna possível sua implementação em tempo-real. Como exemplo, o pro-

blema de navegação de um robô móvel em um determinado ambiente. Tal problema pode

ser tratado de duas maneiras: 1) baseado em um modelo do mundo tridimensional re-

construído a partir das informações obtidas pelos sensores; e 2) baseado na informação

do domínio sensorial para predizer colisões e caminhos futuros. A informação espacial

e a informação sobre o automovimento (egomotion) do sistema estão disponíveis a partir

da detecção de movimento presente entre imagens da mesma cena, sejam elas fornecidas

por um sistema estéreo ou por uma sequência monocular.

Assim, tanto o automovimento do sistema de aquisição de imagens como as carac-

terísticas espaciais da cena podem ser estimadas a partir de uma sequência de imagens.

Isto signiﬁca que a correspondência entre o caminho futuro do robô móvel e as localiza-

ções dos objetos no espaço tridimensional pode ser solucionada no próprio domínio da

imagem. Tais conceitos propiciam a utilização de uma única câmera para a aquisição

da sequência de imagens que alimentará o módulo responsável pela detecção do movi-

mento, e por consequência, obarateamentodosistema [Sarcinelli-Filho et al. 2003, Kawa-

moto et al. 2002, DeSouza e Kak 2002, Ohnishi e Imiya 2006, Dao et al. 2005, Kröse

et al. 2005].

A informação obtida a partir da segmentação da imagem em planos pode ser utili-

zada na reconstrução da forma tridimensional do ambiente. A presença de regiões pla-

nares é bastante comum em ambientes produzidos pelo homem, sejam eles ambientes

internos ou externos. Dessa maneira, planos podem ser considerados importantes ele-

mentos geométricos a serem utilizados em uma grande variedade de tarefas baseadas em

visão [Okada et al. 2001], calibração de câmeras [Sturm e Maybank 1999] e reconstrução

de cenas [Tarel 1997].

1.3 Trabalhos Relacionados

Existem diversos métodos empregados na detecção, segmentação, identiﬁcação e re-

construção de planos no espaço, relacionados com a navegação de robôs. Esta seção tem

como objetivo apresentar alguns trabalhos associados ao tema abordado nesta tese. De-

vido à natureza multidisciplinar do sistema proposto, a apresentação de diversos outros

trabalhos relacionados a cada etapa do processo pode surgir em cada capítulo.

A detecção do plano dominante presente na cena é abordada em diversos trabalhos.

Ohnishi e Imiya (2006) sugerem que o ﬂuxo óptico seja calculado e utilizado para deter-

minar pares de pontos correspondentes entre as duas imagens de uma sequência monocu-

lar. Três pares de pontos são selecionados aleatoriamente para o cálculo dos coeﬁcientes

1.3. TRABALHOS RELACIONADOS

de uma transformação aﬁm entre as duas imagens. A transformação aﬁm deﬁne o ﬂuxo

planar. Uma comparação entre o ﬂuxo planar e o ﬂuxo estimado deﬁne o plano dominante

da cena. A desvantagem de seu método consiste na aleatoriedade da escolha dos pontos

para determinação da transformação aﬁm. Além disso, o algoritmo sugerido somente de-

tecta o plano dominante que, segundo eles, corresponde na maioria das vezes ao plano do

chão.

Zhou e Li (2006a) em seu trabalho, estima a homograﬁa dominante a partir de um

conjunto de pontos correspondentes obtidos pelo detector de Harris combinado com uma

medida de dissimilaridade entre as regiões ao redor do ponto. Um método estilo RAN-

SAC é utilizado na detecção da maior quantidade de pontos que estejam de acordo com

a homograﬁa estimada. Os resultados obtidos são promissores, mas o método possui a

desvantagem de utilizar escolha aleatória de pontos para o cálculo da homograﬁa. Em

outro trabalho, Zhou e Li (2006b) sugerem utilizar uma homograﬁa normalizada especí-

ﬁca para detectar o plano do chão. Seu método exige que os parâmetros intrínsecos da

câmera sejam conhecidos. Um esquema modiﬁcado do algoritmo RANSAC é utilizado

no cálculo da homograﬁa e na detecçãos dos pontos pertencentes ao plano do chão.

Zucchelli et al. (2002) apresentam um algoritmo de segmentação de múltiplos planos

baseado no movimento caracterizado pelo ﬂuxo planar a ser calculado. O cálculo do

ﬂuxo planar é realizado por um método iterativo que soluciona um problema de mínimos

quadrados. Resultados demonstram que o sistema funciona bem quando dez ou mais

imagens da mesma cena estão disponíveis, o que constitui uma desvantagem da utilização

do método na navegação de robôs.

Pears e Liang (2001) utilizam múltiplas características visuais presentes nas imagens

para detectar o plano do chão. Pontos de interesse extraídos pelo detector de Harris são

selecionados para calcular um conjunto de homograﬁas. As homograﬁas calculadas re-

presentam possíveis porções planares da imagem. Baseado na informação de cor da cena

e nas homograﬁas calculadas, as porções planares que pertencem ao mesmo plano são

agrupadas. A desvantagem desse método é a restrição à utilização em ambientes especí-

ﬁcos.

Em outro trabalho, Liang e Pears (2002) utilizam múltiplas fontes de informação vi-

sual para a detecção do plano do chão. Informações de cor, contornos e cantos são utili-

zadas no sistema de navegação visual de robôs em ambientes internos. A segmentação do

plano relacionado ao chão é feita baseada no cálculo de homograﬁas, na informação de

cor e nos contornos detectados na cena.

O algoritmo proposto por Okada et al. (2001) baseia-se na extração de segmentos

candidatos a planos utilizando a transformada de Hough a partir da informação de pro-

CAPÍTULO 1. INTRODUÇÃO

fundidade da cena. Em seguida é realizado um ajuste dos segmentos candidatos a planos

ao mapa de profundidade calculado com o objetivo de identiﬁcar planos parciais. Testes

são executados por um robô humanóide subindo um degrau de altura desconhecida.

Amintabar e Boufama (2008) propõem um método para extrair os principais planos

presentes em uma cena a partir de um par de imagens não-calibradas. O método proposto

não assume nenhuma restrição quanto à coplanaridade de pontos. O processo consiste em

selecionar aleatoriamente três pares de pontos de interesse detectados nas duas imagens

para o cálculo da homograﬁa que representa o plano deﬁnido pelos três pontos. Em se-

guida, todos os pontos detectados são veriﬁcados se pertencentes ao plano determinado

pela homograﬁa calculada. Ao ﬁnal deste estágio, um conjunto de pontos coplanares é ob-

tido. Planos com uma quantidade pequena de pontos são descartados. Este procedimento

é repetido para todas as combinações de três pontos e, ao ﬁnal, planos são mesclados

segundo a homograﬁa que os representa. Além da escolha aleatória de pontos, a busca

exaustiva por uma homograﬁa que represente a maior quantidade de pontos possível re-

presenta uma desvantagem na utilização desse método em aplicações como navegação de

robôs.

O método sugerido por Kim e Kim (2004) é baseado na computação do vetor normal

a cada plano presente na cena. A normal aos planos é computada a partir de 3 pares

de correspondências entre as duas imagens e da homograﬁa calculada. Um processo de

reﬁnamento iterativo a partir dos vetores normais calculados é aplicado, com o objetivo

de obter a segmentação do plano do chão. Resultados preliminares são apresentados.

Corso et al. (2003) utilizam um algoritmo de seguimento (tracking) para atualizar a

posição dos planos detectados em uma cena. O algoritmo consiste em calcular a dis-

paridade de um ponto na imagem e em seguida computar o vetor normal ao plano. Os

parâmetros envolvidos no processo são atualizados e com isso o plano deﬁnido pela nor-

mal é rastreado. O método é aplicado à navegação de robôs utilizando visão estéreo e os

resultados mostram que o método é executado com uma boa taxa de quadros por segundo,

além de manter a precisão no rastreamento dos planos detectados.

O método proposto por Montijanoe Sagues (2008) consiste em simultaneamente obter

a localização métrica e reconstrução da cena utilizando homograﬁas. O robô é guiado por

humanos em uma etapa preliminar de aprendizado, onde algumas cenas de referência são

armazenadas na memória do robô. A reconstrução métrica necessita da informação de

profundidade e orientação dos planos. O problema é que diversos parâmetros da cena

devem ser fornecidos. O algoritmo proposto por Montijano necessita somente de um

parâmetro. Os demais são calculados a partir das imagens de referência armazenadas

previamente. A grande desvantagem deste método reside na necessidade da intervenção

1.3. TRABALHOS RELACIONADOS

humana em uma etapa preliminar à execução do sistema. Tal fato torna a navegação

semi-autônoma.

Dao et al. (2005) apresentam um algoritmo de navegação visual que combina localiza-

ção e extração de regiões planares a partir de uma única câmera utilizada por um robô em

ambientes internos. O ﬂuxo óptico é utilizado no rastreamento de um modelo de marco

terrestre. Além disso, os dados do odômetro do robô são combinados com a informação

visual do marco para a determinação de suas dimensões. A homograﬁa entre duas ima-

gens sucessivas é calculada para detectar regiões planares para a navegação. Resultados

experimentais demonstram a robustez do método com relação a ruído e iluminação.

Suhr et al. (2007) apresentam um sistema automático de detecção de vaga livre em

estacionamento baseado em visão. O sistema consiste de dois estágios. Primeiro, um

modelo tridimensional é reconstruído baseado na extração da geometria epipolar da cena

a partir do ﬂuxo óptico estimado. O plano do chão é detectado a partir da reconstrução

euclidiana da cena utilizandoum histograma de valores das coordenadas Y dos pontos 3D.

A informação métrica é recuperada utilizando o fator de escala determinado pela razão

entre a altura da câmera no mundo real e na cena reconstruída. Em seguida, as orientações

dos espaços livres do estacionamento são estimadas utilizando a transformada de Hough

nos pontos projetados no plano horizontal, após os pontos próximos ao solo terem sido

removidos. Resultados são apresentados a partir de testes realizados em situações reais.

Fraundorfer et al. (2006) apresentam um método de detecção de regiões planares a

partir de um conjunto de pontos correspondentes. As regiões detectadas inicialmente são

expandidas e reﬁnadas utilizando homograﬁas calculadas para cada plano. O método

de Silveira et al. (2006) consiste em detectar múltiplas regiões planares através de um

procedimento de votação baseado no cálculo do vetor normal para cada grupo de 3 pixels

escolhidos aleatoriamente. Piazzi e Prattichizzo (2006) sugerem computar, a partir de um

sistema de câmeras estéreo, o vetor normal de um plano utilizando somente três pares de

pontos correspondentes. Os planos são agrupados baseado no vetor normal calculado.

A análise feita por DeSouza e Kak (2002) apresenta diversos métodos de visão com-

putacional aplicados à navegação de robôs móveis. Tais métodos são divididos conforme

o tipo de navegação, em dois grupos principais: Navegação Interna e Navegação Ex-

terna. Cada um desses grupos pode ser subdividido de acordo com o tipo de ambiente a

ser percorrido pelo robô, que pode ser estruturado ou não-estruturado. Muito progresso

tem sido alcançado nas últimas duas décadas, onde acredita-se que os limites que separam

estas áreas são signiﬁcantes.

CAPÍTULO 1. INTRODUÇÃO

1.4 Visão Geral do Trabalho

Neste trabalho, será apresentado um sistema de segmentação de planos no espaço tri-

dimensional a partir de uma sequência de imagens capturadas por uma única câmera. O

sistema a ser apresentado combina técnicas simples para a obtenção de resultados satisfa-

tórios.

Basicamente, o sistema proposto é formado por três módulos principais:

• Detecção de planos;

• Expansão dos planos detectados;

• Reconstrução métrica dos planos segmentados;

A Figura 1.6 ilustra o diagrama de blocos simpliﬁcado do sistema proposto.

DETECÇÃO

RECONSTRUÇÃO

MÉTRICA

PLANOS

EXPANSÃO

PLANOS

Imagem 1

Imagem 2

PLANOS

Figura 1.6: Diagrama de blocos simpliﬁcado do sistema proposto.

A partir de duas imagens de uma sequência monocular, a detecção dos planos presen-

tes na cena é obtida combinando um detector de movimento de pontos entre as imagens,

com um algoritmo de agrupamento de pontos com movimento semelhante.

A detecção de movimento é feita a partir da obtenção de pares de pontos correspon-

dentes entre as imagens. Para isso, pontos de interesse são detectados nas duas ima-

gens e um descritor utilizado para caracterizar cada um desses pontos. Foi utilizado

neste trabalho o detector de Harris [Harris e Stephens 1988] combinado com o descri-

tor SIFT [Lowe 2003]. Em seguida, a correspondência entre os pontos nas duas imagens

é estabelecida baseada em uma medida de correlação entre os descritores. O movimento

é calculado de acordo com o deslocamento de cada ponto entre as imagens capturadas.

A partir do conjunto de correspondências estabelecido, um método baseado no cálculo

de homograﬁas é utilizado para agrupar pontos pertencentes a um mesmo plano. Após

os pontos terem sido agrupados, cada plano detectado é representado por um conjunto de

pontos correspondentes e sua homograﬁa associada.

1.5. ORGANIZAÇÃO DO TRABALHO

O passo seguinte consiste em expandir cada plano detectado na cena. Geralmente, os

planos presentes em uma cena podem ser referentes ao chão ou referentes a obstáculos. A

fase de expansão consiste em comparar o ﬂuxo planar deﬁnido pela homograﬁa de cada

plano detectado com o ﬂuxo óptico estimado para cada pixel da imagem. Um método de

estimação do ﬂuxo óptico baseado na informação de cor é proposto. A expansão de cada

plano é obtida a partir de um processo que observa a diferença entre o ﬂuxo planar e o

ﬂuxo estimado de cada pixel da imagem.

A etapa ﬁnal consiste na reconstrução métrica dos planos detectados. A reconstru-

ção é realizada a partir da extração da geometria epipolar entre as duas imagens da cena.

A geometria epipolar, representada pela matriz fundamental, é calculada a partir de um

esquema iterativo que utiliza o algoritmo dos 8-pontos normalizado [Hartley 1997]. As-

sumindo que os parâmetros intrínsecos da câmera são conhecidos, a matriz essencial é

obtida a partir da matriz fundamental. A matriz essencial calculada fornece as matrizes

de projeção da câmera no momento da aquisição de cada imagem. Por ﬁm, as coorde-

nadas dos pontos no espaço 3D são determinadas por um procedimento de triangulação

linear.

O sistema foi testado utilizando um conjunto de imagens reais adquiridas por uma

câmera móvel. A análise dos resultados obtidos sugere a funcionalidade do sistema pro-

posto.

1.4.1 Contribuições

A principal contribuição desta tese consiste no desenvolvimento de um sistema de

segmentação de planos no espaço 3D. O sistema proposto integra métodos e técnicas

simples na solução de um problema prático. Além disso, contribuições mais especíﬁcas

podem ser identiﬁcadas ao longo do trabalho:

• Desenvolvimento de um método de detecção de planos baseado em homograﬁas;

• Desenvolvimento de um método de estimação de ﬂuxo óptico baseado na informa-

ção de cor;

• Desenvolvimento de um método de expansão dos planos detectados;

• Executação de testes e análise dos resultados.

1.5 Organização do Trabalho

Este documento está dividido em 5 capítulos. O Capítulo 2 procura tratar do movi-

mento inerente a uma cena e como detectá-lo utilizando ﬂuxo óptico e técnicas de busca

CAPÍTULO 1. INTRODUÇÃO

por correspondência, bem como os conceitos envolvidos em tais procedimentos. Em se-

guida, o Capítulo 3 procura mostrar as deﬁnições acerca da geometria envolvida entre

duas imagens da mesma cena, e métodos de extração dessa informação. O Capítulo 4

descreve em detalhes o sistema de detecção e identiﬁcação de planos desenvolvido, bem

como os testes e resultados para cada etapa do processo. Finalmente, o Capítulo 5 apre-

senta a conclusão do trabalho e as perspectivas futuras relacionadas ao sistema proposto.

Capítulo 2

Detecção do Movimento Inerente a uma

Cena

A detecção de movimento constitui característica essencial da percepção. Um orga-

nismo com esta capacidade consegue determinar seus próprios movimentos, a estrutura

do ambiente, além do movimento de outros objetos presentes em seu campo visual. Um

dos principais problemas em detectar o movimento de objetos reais em um ambiente re-

side no fato de que, ao ser projetada uma cena 3D em um plano de imagem bidimensional,

alguma informação é perdida. Isto constitui um dos principais focos de investigação em

visão computacional, que vem do fato de uma imagem 2D poder representar a projeção

de inﬁnitas cenas tridimensionais.

Os movimentos inerentes a uma cena podem ser representados por seu campo de mo-

vimento. Campo de movimento é o campo de velocidades 3D de cada ponto do espaço

que deﬁne completamente o movimento dos objetos presentes em uma cena variante no

tempo, e seu cálculo é um dos principais objetivos do processo de recuperação de movi-

mento [Golland 1995]. O campo de movimento pode ser determinado através da análise

de imagens adquiridas por um sistema de visão. Tais movimentos podem estar relaciona-

dos ao deslocamento do sistema durante o processo de aquisição de imagens, ou a objetos

móveis presentes na cena. De fato, a informação sobre esses movimentos constitui dado

útil sobre a estrutura da cena.

Considere duas imagens de uma sequência adquirida ao longo do tempo por um sis-

tema de visão monocular. A informação de movimento na imagem pode ser extraída

através do cálculo do ﬂuxo óptico, ou através da busca por uma correspondência entre

pontos de interesse detectados nas duas imagens. As seções que se seguem discutem as

duas abordagens.

CAPÍTULO 2. DETECÇÃO DO MOVIMENTO INERENTE A UMA CENA

2.1 Detecção e Correspondência de Pontos de Interesse

Uma forma de recuperar o movimento inerente a uma cena consiste em estabelecer

uma correspondência (match) única entre pontos de interesse, detectados em duas ima-

gens de uma sequência adquirida ao longo do tempo. O deslocamento resultante da dife-

rença entre as posições do mesmo ponto em duas imagens consecutivas da mesma cena,

determina o movimento do ponto no plano da imagem, portanto uma estimativa do campo

de velocidades 2D. Esta abordagem possui como característica o fato de produzir dados

mais precisos e robustos a ruídos no processo de aquisição, embora bem mais escassos

que aqueles resultantes da estimação utilizando técnicas de ﬂuxo óptico.

2.1.1 Detecção de Pontos de Interesse

O termo ponto de interesse pode ser associado de forma simples a um ponto na ima-

gem onde o sinal muda nas duas dimensões. Bordas e cantos (corners) são alguns exem-

plos de pontos de interesse. Ao contrário de bordas, cantos não apresentam ambiguidade

de movimento. Em vista disso, são frequentemente utilizados em pesquisas relacionadas

à análise de forma e de movimento.

Diferentes métodos de detecção de pontos de interesse existem na literatura. Ba-

sicamente, tais métodos são classiﬁcados em três categorias: baseados em intensidade,

baseados em contornos e baseados em modelos paramétricos [Schmid et al. 2000]. O es-

tudo e investigação dos diversos métodos de detecção de pontos de interesse não constitui

objeto de investigação deste trabalho. Sendo assim, um método de detecção foi escolhido

baseado em resultados de trabalhos existentes na literatura [Vincent e Laganière 2001, Ar-

mangué e Salvi 2003, Mikolajczyk et al. 2005, Silveira et al. 2006, Chen et al. 2006].

Método de Harris

Moravec (1977) desenvolveu um dos primeiros detectores de pontos de interesse base-

ados em valores de intensidade da imagem. O detector de Moravec utiliza uma função de

auto-correlação para medir a diferença entre a janela em torno de um determinado pixel e

janelas deslocadas em diversas direções. São utilizados deslocamentos discretos em dire-

ções paralelas às linhas e colunas da imagem. Caso o mínimo das diferenças calculadas

pela função de auto-correlação seja maior que um certo limiar, um ponto de interesse é

detectado. Moravec sugere a função de auto-correlação como

c(x,y) =

∑

[I(x

) −I(x

+ d

)]

, (2.1)

2.1. DETECÇÃO E CORRESPONDÊNCIA DE PONTOS DE INTERESSE

onde I(x,y) é o valor de intensidade da imagem para o pixel (x,y), W é a janela de deslo-

camento, e (d

) corresponde ao deslocamento da janela W e assume valores deﬁnidos

no intervalo discreto [(1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1)].

O método de Moravec apresenta alguns problemas: 1) apenas deslocamentos discretos

em ângulos de 45

são considerados; 2) a resposta do operador é sensível ao ruído devido

a janela de deslocamento ser binária e retangular; e 3) o operador responde fortemente a

bordas porque somente o valor mínimo da função de auto-correlação é considerado.

Como forma de minimizar os efeitos de tais problemas, Harris e Stephens (1988)

propuseram uma melhoria no método de Moravec. Harris sugere utilizar uma expansão

em série de Taylor para o deslocamento na imagem, de forma a possibilitar que todos

os possíveis deslocamentos da janela sejam considerados. Assim, um deslocamento na

imagem pode ser aproximado, utilizando-se somente os termos de primeira ordem da

expansão, como

I(x+ d

,y+ d

) ≈I(x,y) +d

(x,y) + d

(x,y), (2.2)

onde I

(x,y) e I

(x,y) denotam as derivadas parciais calculadas em x e y. Substituindo a

Equação 2.2 na função de auto-correlação dada pela Equação 2.1, obtém-se

c(x,y) =

∑

) + d

)]

, (2.3)

que pode ser reescrita na forma matricial como

c(x,y) =







∑

))

∑

))

∑

))

∑

))





(2.4)

Segundo Harris, a sensibilidade ao ruído do operador de detecção pode ser diminuída

caso uma janela circular gaussiana seja utilizada na ponderação dos pixels da janela de

deslocamento. Finalmente, ele propõe uma reformulação na resposta do detector para

evitar que o mesmo reaja fortemente na presença de bordas.

A função de auto-correlação para o método de Harris é representada pela matriz de

gradientes da Equação 2.4 ponderada por uma janela gaussiana, deﬁnida como

= g⊗



∑

))

∑

))

∑

))

∑

))



, (2.5)

onde g especiﬁca a janela gaussiana, e ⊗ o operador convolução.

CAPÍTULO 2. DETECÇÃO DO MOVIMENTO INERENTE A UMA CENA

Harris deﬁne a resposta do detector, C

, como uma medida baseada no determinante

e no traço da matriz de auto-correlação A

, dada por

= det(A

) −k(trace(A

))

, (2.6)

onde k é constante e ajustado de forma empírica. Um ponto de interesse é detectado se o

valor de C

for maior que um certo limiar deﬁnido.

O método de Harris é um método clássico para detecção de pontos de interesse. Ele

foi escolhido baseado na sua robustez a movimentos de rotação, variação na iluminação,

mudança de escala e ruído. Além disso, tal método é rápido, conﬁável e provê uma boa

taxa de repetitibilidade [Schmid et al. 2000]. A taxa de repetitibilidade especiﬁca o quão

a detecção é independente das mudanças nas condições da imagem. Em outras palavras,

pontos detectados em uma imagem devem ser detectados em posições correspondentes

aproximadas em outras imagens da mesma cena. O trabalho de Schmid et al. (2000)

mostrou que o detector de Harris representa uma boa escolha por ter apresentado melhores

resultados que diversos outros métodos.

2.1.2 Descritor Local

A partir da detecção de pontos de interesse em dois quadros consecutivos de uma

sequência de imagens, uma função pode ser utilizada para estabelecer uma medida de

correlação entre as diferentes vistas de um mesmo ponto no espaço 3D. Um exemplo ób-

vio seria utilizar uma medida de correlação normalizada entre as medidas de intensidade

da região local ao redor do ponto de interesse. O problema com este tipo de medida é que

a simples correlação de porções da imagem é altamente sensível a mudanças no ponto de

vista 3D, deformações não-rígidas, ou ainda variação nas condições de iluminação.

Outra maneira de estabelecer uma medida de correlação seria a utilização de um des-

critor local. Descritores são vetores de características de porções da imagem que podem

ser utilizados para comparar porções em imagens diferentes de uma mesma cena. O

descritor SIFT (Scale Invariant Feature Transform) [Lowe 2003] é um descritor local al-

tamente distinto, e invariante a mudanças na iluminação e ponto de vista 3D. O descritor

SIFT consiste de um histograma baseado na magnitude e orientação do gradiente de todos

os pixels em uma região ao redor do ponto de interesse.

O primeiro passo no cálculo do descritor é computar a orientação e magnitude do

gradiente da imagem de todos os pontos ao redor do ponto de interesse. Com o objetivo

de obter um descritor invariante a orientação, as coordenadas do descritor e as orientações

2.1. DETECÇÃO E CORRESPONDÊNCIA DE PONTOS DE INTERESSE

dos gradientes são rotacionadas em relação à orientação do ponto de interesse, ou seja, a

orientação do ponto de interesse deve ser a orientação de referência igual a 0

Em seguida, cada magnitude calculada em torno do ponto de interesse é atenuada

segundo uma janela gaussiana com variância σ, igual a metade da largura da região ao

redor do ponto de interesse. O próximo passo consiste em deﬁnir n×n sub-regiões de k×

k pixels cada. A partir daí, as magnitudes atenuadas são acumuladas em um histograma de

orientações para cada sub-região. A magnitude acumulada em cada entrada do histograma

de orientações corresponde à soma das magnitudes dos gradientes próximos à direção

daquela entrada. O procedimento de construção do descritor é ilustrado na Figura 2.1.

Figura 2.1: Descritor SIFT calculado a partir de um conjunto de 8×8 pixels divididos

em 2×2 sub-regiões. Cada histograma do descritor possui 8 intervalos de orientação.

O descritor é representado por um vetor de 32 elementos (2 ×2×8). O comprimento

de cada seta na ﬁgura do lado direito corresponde à soma das magnitudes dos gradientes

próximos àquela direção dentro de cada sub-região.

O descritor é então representado por todos os histogramas das sub-regiões. Esta re-

presentação é na forma de um vetor, onde cada elemento do vetor corresponde a cada uma

das direções de cada um dos histogramas. Por ﬁm, para que o descritor seja invariante

à iluminação uma normalização é aplicada de tal forma que o valor máximo do vetor de

características seja igual a 1.

2.1.3 Considerações Adicionais

Como forma de recuperar o movimento inerente a uma cena, uma correspondência

única entre pontos de interesse detectados nas duas imagens deve ser estabelecida. A

distância entre descritores pode ser usada como medida de correlação, como por exemplo

uma simples medida de distância euclidiana. Caso o valor da distância esteja abaixo de

CAPÍTULO 2. DETECÇÃO DO MOVIMENTO INERENTE A UMA CENA

um certo limiar uma possível correspondência é detectada. Um esquema de busca pode

ser utilizado para encontrar os pares de pontos correspondentes.

Primeiramente, para cada ponto de interesse detectado na primeira imagem, é feita

uma busca por um ponto de interesse correspondente na segunda imagem. O critério de

correlação a ser satisfeito é baseado na distância entre os descritores dos pontos nas duas

imagens. Todos os pontos de interesse nas duas imagens que não possuirem um corres-

pondente são descartados. O próximo passo consiste de um procedimento de ﬁltragem

regressiva de forma a prevenir que dois ou mais pontos de interesse na primeira imagem

tenham o mesmo correspondente na segunda. Para cada ponto de interesse remanescente

na segunda imagem, somente o melhor correspondente na primeira imagem é mantido.

Ao ﬁnal do processo de ﬁltragem, um conjunto de pares de pontos correspondentes é

obtido a partir das duas imagens. Este procedimento de busca representa uma parte do

sistema proposto, sendo discutido com mais detalhes na Seção 4.2.

2.1.4 Testes e Resultados

A combinação do método de detecção de Harris com o descritor local SIFT produz

resultados bons, rápidos e estáveis [Mikolajczyk e Schmid 2005]. Como forma de justi-

ﬁcar tal escolha para o processo de busca de pares de pontos correspondentes entre duas

imagens, os resultados de um experimento são apresentados nesta seção. Três imagens

de cada cena são utilizadas no experimento. As imagens são coloridas, embora somente a

informação de intensidade de brilho seja utilizada. A Figura 2.2 mostra uma imagem de

cada uma das cenas.

(a) Cena 01 (b) Cena 02

Figura 2.2: Exemplos de imagens utilizadas no experimento.

O experimento consiste em testar a repetitibilidade de pontos de interesse em ima-

gens da mesma cena. Para isso, os pontos de interesse em cada imagem são detectados

2.1. DETECÇÃO E CORRESPONDÊNCIA DE PONTOS DE INTERESSE

utilizando o método de Harris. Em seguida, para cada ponto de interesse detectado o

descritor SIFT é computado. Utilizando a distância euclidiana entre os descritores como

métrica, é feita uma busca por pares de pontos correspondentes entre a primeira e segunda

imagens, e depois entre a segunda e terceira imagens. A Figura 2.3 (pág. 22) ilustra os

pontos de interesse detectados marcados em vermelho em uma imagem de cada uma das

cenas, bem como as correspondências encontradas de cada ponto, representadas por setas

azuis. Além disso, as correspondências falso-positivas foram computadas e são destaca-

das em verde na mesma ﬁgura. Os dados numéricos referentes a esta primeira parte do

experimento encontram-se nas Tabelas 2.1 e 2.2.

Tabela 2.1: Número de pontos de interesse detectados nas três imagens de cada cena.

Cena 01 Cena 02

Img01 Img02 Img03 Img01 Img02 Img03

Pontos de Interesse 278 278 284 266 260 265

Tabela 2.2: Número de pares de pontos correspondentes e medidas falso-positivas com-

putadas a partir dos pares de imagens consecutivas de cada cena.

Correspondências Falso-Positivos

Cena 01

Img01 ↔ Img02 236 20

Img02 ↔ Img03 239 22

Cena 02

Img01 ↔ Img02 203 26

Img02 ↔ Img03 217 11

De acordo com os dados das Tabelas 2.1 e 2.2, a relação entre o número de correspon-

dência de pontos e a quantidade de pontos detectados é bastante alta. Para todos os casos,

a razão entre as duas medidas ﬁcou acima de 85%. Ainda na Tabela 2.2 pode ser obser-

vado que o número de correspondências falso-positivas está dentro do aceitável. Somente

em um dos casos tal número esteve acima de 10% da quantidade de correspondências

encontradas.

Finalmente, a quantidade de pontos de interesse que se repetem nas três imagens é

calculada, bem como o número de falso-positivos. A Figura 2.4 (pág. 23) ilustra, na

primeira imagem de cada cena, somente os pontos de interesse que se repetem nas três

imagens.

A Tabela 2.3 (pág. 24) apresenta os dados referentes ao experimento. Os valores

sugerem uma boa taxa de repetitibilidade dos pontos de interesse encontrados. Para a

Cena 1, a taxa obtida foi de aproximadamente 73%, e para a Cena 2 foi obtida uma taxa

aproximada de 66%, enquanto que o númerodefalso-positivos permanece baixo (< 10%).

CAPÍTULO 2. DETECÇÃO DO MOVIMENTO INERENTE A UMA CENA

(a) Cena 01

(b) Cena 02

Figura 2.3: Resultado da busca por correspondências. Os pontos detectados estão mar-

cados em vermelho. Retas azuis deﬁnem as correspondências, e os pontos marcados em

verde são correspondências falso-positivas.

2.1. DETECÇÃO E CORRESPONDÊNCIA DE PONTOS DE INTERESSE

(a) Cena 01

(b) Cena 02

Figura 2.4: Pontos de interesse detectados que se repetem nas três imagens de cada cena.

Os pontos estão destacados em vermelho no primeiro quadro de cada sequência. Os

pontos marcados em verde são correspondências falso-positivas.

CAPÍTULO 2. DETECÇÃO DO MOVIMENTO INERENTE A UMA CENA

Tabela 2.3: Número de pontos de interesse detectados que se repetem nas três imagens de

cada cena.

Cena 01 Cena 02

Pontos de Interesse 207 176

Falso-Positivos 20 22

Em vista disso, os resultados apresentados sugerem o método de Harris combinado

com o descritor SIFT como sendo uma adequada escolha para o processo de busca por

correspondência de pontos entre duas imagens [Aires, Araújo e Medeiros 2008b].

2.2 Fluxo Óptico

O ﬂuxo óptico é deﬁnido como a distribuição de velocidades aparentes do padrão de

movimento do brilho através do plano da imagem, em um sistema de visão por compu-

tador, ou na retina do olho, em um sistema de visão biológico. Ele aparece geralmente

devido ao movimento relativo entre objetos e câmera, podendo também ser gerado por

fontes de luz que iluminam a cena [Horn e Schunck 1981]. Em vista disso, o ﬂuxo óptico

descreve direção e magnitude do movimento de pontos da imagem. Em muitos casos,

confunde-se ﬂuxo óptico com campo de movimento. Estes conceitos podem ser bastante

distintos em situações especíﬁcas como, por exemplo, quando há movimento de alguma

fonte de luz na cena [Caldeira 2002].

Uma esfera executando movimento de rotação é um exemplo clássico capaz de dife-

renciar o campo de movimento do ﬂuxo óptico. Assumindo que a esfera executa movi-

mento de rotação, com observador e fonte de luz estáticos, observa-se que o ﬂuxo óptico

é nulo desde que a intensidade do brilho ao longo da imagem não muda, permanecendo o

campo de movimento não-nulo. Outro exemplo a ser citado é o caso de uma cena estática

onde a fonte de luz está em movimento. Neste caso, o ﬂuxo óptico é não-nulo devido

a mudança de brilho na imagem, enquanto que a ausência de movimento faz com que o

campo de movimento seja nulo [Golland 1995].

A estimação do ﬂuxo óptico pode ser feita a partir de uma sequência de imagens

adquiridas por uma única câmera em intervalos ﬁxos de tempo [Horn e Schunck 1981],

ou a partir de imagens adquiridas por duas câmeras, no caso de visão estéreo [Lucas e

Kanade 1981]. No primeiro caso, os deslocamentos de pixels são considerados no tempo,

ou seja, quadro a quadro. No caso da estimação do ﬂuxo óptico aplicado a visão estéreo,

o deslocamento de pixels considerado é relativo à distância entre as câmeras que efetuam

a aquisição, o que possibilita a recuperação do campo de movimento 3D.

2.2. FLUXO ÓPTICO

A Figura 2.5 ilustra a idéia relacionada ao cálculo dos vetores de ﬂuxo que descrevem

o movimento de um objeto entre quadros diferentes de uma mesma cena. Basicamente,

o ﬂuxo óptico pode ser calculado tomando-se uma porção da imagem em um quadro, e

localizando a mesma porção no quadro consecutivo.

Imagem 01 Imagem 02

Figura 2.5: Vetores do Fluxo Óptico.

Um exemplo de um campo de ﬂuxo óptico estimado a partir de dois quadros conse-

cutivos de uma sequência de imagens é ilustrado na Figura 2.6. Na sequência de imagens

capturadas pela câmera, somente o carro que aparece por completo na imagem está em

movimento. A direção do movimento pode ser interpretada a partir da análise da infor-

mação contida no campo de ﬂuxo óptico.

A partir de sua deﬁnição, para o ﬂuxo óptico representar exatamente o movimento da

imagem, um número de condições deve ser satisfeita: iluminação uniforme, reﬂectância

Lambertiana [Forsyth e Ponce 2002] da superfície, e movimento de translação pura para-

lela ao plano da imagem. Na realidade, estas condições nunca são satisfeitas. Ao invés

disso, são assumidas ocorrerem localmente na cena, e portanto, localmente no plano da

imagem. O grau com que essas condições são satisfeitas, em parte, determinam a precisão

com que o ﬂuxo óptico calculado representa o movimento da imagem. Além disso, even-

tos visuais como oclusão, movimentos transparentes, e objetos não-rígidos aumentam a

complexidade relacionada ao cálculo do ﬂuxo óptico.

CAPÍTULO 2. DETECÇÃO DO MOVIMENTO INERENTE A UMA CENA

(a) Imagem

(b) Fluxo Óptico

Figura 2.6: (a) Exemplo de um quadro da sequência de imagens. (b) Fluxo óptico esti-

mado.

2.2.1 Classiﬁcação dos Algoritmos de Fluxo Óptico

Durante as duas últimas décadas, a pesquisa em ﬂuxo óptico foi acelarada, resultando

em algoritmos com as mais diversas aplicações. Dentre as aplicações, podemos citar:

reconstrução 3D, estimação do automovimento, detecção de movimento, segmentação de

objetos, cálculo de tempo-para-colisão (TPC), obtenção de mapa de disparidade, extração

do plano dominante da imagem, cálculo do foco de expansão (FOE), e visão aplicada a

navegação de robôs.

Desde que Horn e Schunck (1981) e Lucas e Kanade (1981) publicaram seus traba-

lhos, uma grande quantidade de métodos para estimar o ﬂuxo óptico tem surgido. Diver-

sos pesquisadores tem tentado calcular de forma mais precisa e eﬁciente o ﬂuxo óptico.

Barron, Fleet, Beauchemin e Burkitt (1994) ﬁzeram uma análise detalhada de vários de-

les, subdividindo-os em: métodos baseados em gradiente, métodos baseados em correla-

ção, métodos baseados na minimização de uma função de energia, e métodos baseados em

fase. Mais tarde, Beauchemin e Barron (1995) incrementaram seu estudo sugerindo, base-

ados nos métodos até então apresentados, nova classiﬁcação: métodos diferenciais base-

ados em intensidade, métodos multi-restrição, métodos baseados em frequência, métodos

baseados em correlação, métodos de movimento múltiplo, e métodos de reﬁnamento tem-

poral. Os limites entre estas classes de métodos não estão claros. Existem técnicas que

incorporam os conceitos de métodos baseados em fase com os de métodos baseados em

correlação, além dos métodos baseados em movimento múltiplo e reﬁnamento temporal

que geralmente se sobrepoem às outras técnicas. McCane, Galvin, Novins e Mills (1998)

avaliaram alguns algoritmos não estudados por Beauchemin e Barron (1995), como os

algoritmos de Camus (1995) e o de Proesmans et al. (1994).

2.2. FLUXO ÓPTICO

Algumas dessas classes de métodos são brevemente tratadas a seguir. Maior ênfase

será dada aos métodos baseados no gradiente. Tais métodos foram escolhidos para uma

investigação mais profunda neste trabalho por possuirem características que facilitam seu

uso em tempo-real, além de fornecerem um campo de vetores de ﬂuxo óptico mais denso.

Métodos Baseados em Correlação

As técnicas baseadas em correlação deﬁnem uma velocidade v de um pixel q com

coordenadas (x,y) na imagem, a partir do deslocamento d = (d

) que produz a melhor

correlação entre regiões das imagens. O cálculo da similaridade deﬁnida por uma função

Φ pode ser generalizado e deﬁnido por um valor de correlação, como

COR(q;d) =

∑

Φ[I

(q+ (i, j)) −I

(q+ d+ (i, j))], com (i, j) ∈ J

, (2.7)

onde I

e I

correspondem à intensidade de brilho dos pixels nas imagens, e J

é a janela

de busca determinada pelo máximo deslocamento presente na cena.

O uso da técnica baseada em correlação pode ser ilustrada na Figura 2.7. O qua-

drado tracejado delimita o deslocamento máximo possível do pixel, formando uma janela

de busca de similaridades de tamanho (2n + 1) ×(2n + 1). O valor de n depende da

velocidade esperada do pixel no plano da imagem. A minimização de uma função de

correlação (ou maximização, dependendo da função empregada) determinará o correto

deslocamento efetuado pelo pixel, consequentemente o vetor velocidade v que descreve

tal movimento. Como geralmente trata-se de estimação de movimento de corpos rígidos,

a velocidade de um dado pixel é considerada igual à de seu vizinho, como ilustrado nas

Figuras 2.7c e 2.7d.

(a) (b) (c) (d)

Figura 2.7: Determinação do Movimento de um pixel baseada em correlação.

Alguns métodos de cálculo do ﬂuxo óptico baseados em correlação podem ser citados.

O método de Anandan apud [Barron, Fleet, Beauchemin e Burkitt 1994] utiliza pirâmide

Laplaciana com busca em multiresolução (coarse-to-ﬁne), e uma estratégia de correlação

CAPÍTULO 2. DETECÇÃO DO MOVIMENTO INERENTE A UMA CENA

baseada na soma do quadrado das diferenças (SSD). A pirâmide Laplaciana permite a

estimação de grandes deslocamentos entre quadros consecutivos de imagens, e ajuda a

realçar a estrutura da imagem, como bordas, por exemplo, que são de extrema importân-

cia. Primeiramente, os deslocamentos são calculados com precisão subpixel no menor

nível de resolução. Os valores encontrados são utilizados como estimativas iniciais para

as camadas com maior resolução até o cálculo do campo de ﬂuxo ﬁnal.

O método de Singh (1991) é realizado em dois estágios. O primeiro é baseado no

cálculo da similaridade a partir de três imagens adjacentes ﬁltradas. O fato de adicionar

superfícies de similaridade de dois quadros tende a desconsiderar mínimos espúrios de-

vidos a ruído ou textura periódica. Singh então converte o valor de similaridade em uma

distribuição de probabilidade. A velocidade com precisão subpixel é calculada como a

média de tal distribuição sobre um deslocamento inteiro. A utilização de distribuições de

probabilidade em métodos diferenciais de cálculo do ﬂuxo óptico é discutida por Simon-

celli et al. (1991).

Apesar dos algoritmos baseados em correlação serem robustos, não satisfazem plena-

mente o critério de eﬁciência computacional. Uma limitação evidente em tais algoritmos

é o fato de sua complexidade computacional aumentar quadraticamente com o deslo-

camento máximo possível permitido para o pixel. Camus (1994) propôs um algoritmo

baseado em correlação que usa busca exaustiva sobre uma pequena vizinhança ao longo

de n quadros. A busca é feita de forma linear no tempo e não no espaço.

Devido à natureza bidimensional dos algoritmos baseados em correlação, eles não so-

frem com o problema da abertura. Tais métodos podem ser aplicados a situações ideais

com iluminação constante, ausência de ruído, e movimentotranslacionalparalelo ao plano

de projeção. Pequenas mudanças na iluminação ambiente podem afetar os valores indivi-

duais da medida de correlação, mas não necessariamente afetarão a melhor similaridade

encontrada, o que pode ser de extrema valia dependendo da aplicação em questão.

Técnicas Baseadas em Energia e Baseadas em Fase

As técnicas baseadas em energia, como o próprio nome sugere, baseiam-se na energia

de saída de ﬁltros velocity-tuned. Estes são também chamados de métodos baseados em

frequência ao utilizar o ajuste de velocidade no domínio de Fourier. O método de Heeger

apud [Barron, Fleet, Beauchemin e Burkitt 1994] utiliza 12 ﬁltros de Gabor ajustados em

diferentes orientações no espaço e diferentes frequências temporais para extrair a energia

local. O cálculo da velocidade da imagem é formulado como um ajuste de mínimos-

quadrados da energia de saída do ﬁltro para o plano no espaço de frequência.

2.2. FLUXO ÓPTICO

As técnicas baseadas em fase são assim deﬁnidas porque a velocidade da imagem é

determinada em termos do comportamento da fase da saída de ﬁltros passa-faixa. Fleet

e Jepson apud [Barron, Fleet, Beauchemin e Burkitt 1994] deﬁniram a componente velo-

cidade em termos do movimento instantâneo dos contornos do nível de fase na saída do

ﬁltro passa-faixa de ajuste de velocidade. Filtros passa-faixa são usados para decompor

o sinal de entrada de acordo com sua escala, velocidade e orientação. Esta é uma técnica

diferencial aplicada à fase ao invés de ser aplicada à velocidade. Técnicas baseadas em

fase e baseadas em energia são inviáveis para aplicação em um sistema de visão utilizado

para navegação de robôs devido a seu alto custo computacional.

2.2.2 Técnicas Diferenciais

As técnicas diferenciais, ou métodos baseados em gradiente, baseiam-se na mudança

de informação de luminância na imagem, ou seja, na mudança da intensidade de brilho,

I(x,y). A estimativa dos vetores de ﬂuxo óptico é feita a partir de derivadas espaço-

temporais da intensidade da imagem.

Como hipótese inicial, a intensidade local do brilho da estrutura é assumida constante

sob movimento em um período de tempo pequeno. Representando a intensidade de brilho

de um pixel (x,y) da imagem, no momento t por I(x,y,t), temos que

I(x,y,t) ≈ I(x+ dx,y+ dy,t + dt), (2.8)

onde (dx,dy) é o deslocamento do pixel (x,y) da imagem após um intervalo de tempo dt.

Considerando a velocidade de deslocamento do pixel e a intensidade de brilho constante

sob tal deslocamento, podemos reescrever a Equação 2.8 da seguinte forma

I(x,y,t) = I(x+ v

dt,y+ v

dt,t + dt), (2.9)

onde v

e v

são as componentes de velocidade do pixel (x,y).

Assumindo a conservação do brilho proposta pela Equação 2.8, um valor de dt pe-

queno, e I(x,y,t) diferenciável, a Equação 2.9 pode ser expandida utilizando série de

Taylor, como

I(x+ dx,y+ dy,t + dt) = I(x,y,t) + v

(x,y,t) + v

(x,y,t) + I

(x,y,t) + O

, (2.10)

onde I

, I

e I

representam as derivadas parciais com relação a x, y e t, e O

representa

os termos de ordem superior da série de Taylor. Tais termos tendem a desaparecer com

CAPÍTULO 2. DETECÇÃO DO MOVIMENTO INERENTE A UMA CENA

dt → 0. Como dt é frequentemente uma fração signiﬁcativa de um segundo, é questi-

onável não computar esses termos, mesmo assim, tais termos geralmente são ignorados

por questões de tempo de processamento.

A partir das Equações 2.9 e 2.10, e ignorando as componentes de ordem superior,

obtém-se a equação de restrição do ﬂuxo óptico [Horn e Schunck 1981]

+ v

+ I

= 0, (2.11)

que pode ser reescrita como

v·(∇I)

+ I

= 0, (2.12)

onde ∇I = (I

) é o gradiente espacial de intensidade, I

é a derivada parcial de primeira

ordem de I(x,y,t), e v = (v

) é o vetor de ﬂuxo óptico.

A Equação 2.11 apresenta duas variáveis a serem determinadas, v

e v

, que descrevem

a magnitude e a orientação de v. Além disso, deﬁne uma restrição local no movimento da

imagem. Esta restrição não é suﬁciente para computar as duas componentes de v. Sendo

assim, somente a componente do movimento na direção do gradiente de intensidade da

imagem pode ser estimada [Horn e Schunck 1981]. Este fenômeno é conhecido como

Problema da Abertura, sendo ilustrado na Figura 2.8.

Quadro 02

Quadro 01

Figura 2.8: Problema da Abertura. O movimento do objeto é descrito por v. No ponto q,

onde a variação de intensidade é unidimensional, o movimento é ambíguo, podendo ser

interpretado como contrário a v. Sob tais condições o problema é mal-condicionado, e

sem restrições locais adicionais não pode ser corretamente determinado.

2.2. FLUXO ÓPTICO

Existem diversas maneiras de adicionar uma restrição ao cálculo do ﬂuxo óptico uti-

lizando as técnicas diferenciais. Algumas delas são discutidas nos métodos a seguir.

Método de Horn & Schunck

Horn e Schunck (1981) assumiram que o ﬂuxo óptico varia suavemente em toda a

imagem. Com exceção nas bordas de objetos, o movimento em pixels adjacentes é bas-

tante similar. Uma medida de quanto o ﬂuxo óptico desvia desta variação de suavização

ideal pode ser calculada como um termo de suavização global, dado por

(

∂v

∂x

)

+ (

∂v

∂y

)

+ (

∂v

∂x

)

+ (

∂v

∂y

)

= ∇v



+ ∇v



. (2.13)

Em vista disso, a Equação 2.13 pode ser combinada com a Equação 2.12, para calcular o

ﬂuxo óptico, por meio da minimização da função

+ I

)

+ α

(∇v



+ ∇v



)dxdy, (2.14)

deﬁnida sobre uma região de interesse D, onde α

deﬁne a inﬂuência do termo de suaviza-

ção. Os vetores de ﬂuxo óptico da imagem são obtidos pela minimização da Equação 2.14

por meio das equações iterativas

k+1

−

+ I

]

+ I

k+1

−

+ I

]

+ I

(2.15)

onde k denota o número de iterações, v

e v

denotam estimativas iniciais do vetor de

velocidade, e

e v

denotam as médias das vizinhanças de v

e v

A convergência do algoritmo clássico de Horn e Schunck (1981) foi demonstrada

por Mitiche e Mansouri (2004). Este método não permite implementação em tempo-real

devido ao mesmo fazer uso de técnicas de solução iterativa, além de impor limitações em

memória. A matriz de coeﬁcientes do sistema de equações pode ser derivada em uma

estrutura hierárquica, tornando atrativo o uso da teoria de sistemas variantes no tempo

para explorar tal estrutura, com o objetivo de encontrar um método de solução direta que

possibilite uma implementação em tempo-real [Dewilde et al. 2004].

CAPÍTULO 2. DETECÇÃO DO MOVIMENTO INERENTE A UMA CENA

Método de Lucas & Kanade

O método de Lucas e Kanade (1981) utiliza um critério de suavidade local que consi-

dera o ﬂuxo óptico constante em pequenas regiões de tamanho N ×N pixels da imagem.

A Equação 2.11 é escrita para cada pixel na região, resultando no conjunto de equações

∑

x∈Ω

(q)[v(∇I(x,y,t))

+ I

(x,y,t)]

, (2.16)

onde W(x,y) denota uma função de ponderação que atribui pesos aos pixels da região Ω

de ﬂuxo óptico constante.

O conjunto de Equações 2.16 é utilizado para produzir uma estimativa de mínimos

quadrados do vetor de ﬂuxo óptico da região Ω. Para cada região, a solução para a Equa-

ção 2.16 pode ser dada pelo método da pseudo-inversa como

Av = A

b ⇒ v = (A

−1

b (2.17)

onde A é a matriz de gradientes espaciais, b o vetor de gradientes temporais. É importante

salientar que o tempo de processamento do algoritmo de Lucas e Kanade diminui consi-

deravelmente com o aumento da região de suavidade deﬁnida por N. Em contrapartida, a

obtenção de uma função de ponderação W(x,y) é diﬁcultada.

Método de Bouguet

O método de Bouguet (1999) utiliza uma técnica de multiresolução aplicada ao mé-

todo de Lucas e Kanade (1981). A justiﬁcativa para isso é a necessidade de uma maior

precisão nas medidas dos vetores de ﬂuxo óptico obtidos. O método utiliza a representa-

ção em pirâmides de uma imagem.

O objetivo do algoritmo é encontrar o vetor de ﬂuxo óptico v que satisfaça a corres-

pondência q= p+v, onde p é o ponto na primeira imagem I

e q o ponto correspondente

em I

. Considere os vários níveis da representação em pirâmides L = 0,...,L

, onde o

nível 0 representa a imagem com maior resolução, ou seja, I

= I. Seguindo a deﬁnição,

o vetor p





é computado como

. (2.18)

Assumindo que um valor inicial de ﬂuxo óptico g





está disponível para

2.2. FLUXO ÓPTICO

o nível L, é necessário encontrar o vetor de deslocamento residual v





que

minimiza a função de erro dada pela equação

) =

∑

x=p

−w

∑

y=p

−w

(x,y) −I

(x+ g

+ v

,y+ g

+ v

))

, (2.19)

onde a janela de integração é mantida de tamanho constante, (2w

+ 1) ×(2w

+ 1).

O algoritmo é inicializado com a estimativa inicial g



0 0



, para L = L

. O

resultado do cálculo é propagado ao próximo nível, L−1, gerando o novo valor inicial

L−1

, de acordo com a expressão

L−1

= 2(g

+ v

). (2.20)

A solução ﬁnal para o ﬂuxo óptico v é dada pela equação

v = v

+ g

. (2.21)

2.2.3 Considerações Adicionais

Algoritmos como os de Lucas e Kanade (1981) e Horn e Schunck (1981) são consi-

derados na literatura como técnicas clássicas de estimação do ﬂuxo óptico. Tais métodos

inspiraram o aparecimento de diversos outros algoritmos, ou modiﬁcações. Nagel apud

[Barron, Fleet, Beauchemin e Burkitt 1994] foi um dos primeiros a usar derivadas de se-

gunda ordem para medir o ﬂuxo óptico. Ele sugeriu uma restrição de suavização orientada

através de gradientes íngremes (bordas) como uma forma de tratar oclusões. Baseada nos

algoritmos de Lucas e Kanade (1981) e Grossman e Santos-Victor apud [Caldeira 2002],

o algoritmo de Caldeira (2002) não utiliza todos os pixels da imagem para o cálculo do

ﬂuxo, tornando-o mais rápido. Além deste, ela sugere a utilização do procedimento de

normalização das derivadas usado no algoritmo de Lai e Vemuri (1998) para o algoritmo

de Horn e Schunck (1981). Os dois algoritmos foram testados para navegação de uma

plataforma robótica móvel [Sarcinelli-Filho et al. 2002a, Sarcinelli-Filho et al. 2003].

Soria et al. (2003) utilizam fusão de dados baseada em um ﬁltro de Kalman, onde

estimativas do vetor de ﬂuxo calculadas em sub-regiões da imagem produzem como re-

sultado uma estimativa melhor que a dos valores de entrada. Um método semelhante foi

usado por Gamarra et al. (2005). Selvatici e Costa (2004) utilizaram uma versão modi-

ﬁcada do agoritmo de Lucas e Kanade (1981), inspirada no trabalho de Sarcinelli-Filho

et al. (2002b), onde descartam vetores não-aceitáveis para produzir mapas de ﬂuxo mais

CAPÍTULO 2. DETECÇÃO DO MOVIMENTO INERENTE A UMA CENA

escassos. Lim e Gamal (2001) utilizaram o algoritmo de Lucas e Kanade (1981) combi-

nado com um sensor de imagens CMOS de alta velocidade para estimar o ﬂuxo óptico

usando altas taxas de quadros em uma sequência de imagens. Proesmans et al. (1994)

apresentaram um método similar ao de Horn e Schunck (1981), tendo como diferença

principal o fato de que um processo de correlação é incorporado na equação de restrição,

e introduziram um método para tratar discontinuidades no ﬂuxo. Em seguida, aplicaram

a generalização a imagens coloridas no espaço de escalas. Métodos que utilizam imagens

coloridas serão vistos mais adiante.

Alguns trabalhos na literatura tentam avaliar métodos existentes de forma empírica,

concentrando-se em aspectos como eﬁciência computacional e precisão de estimativas

[Barron et al. 1992, Barron, Fleet, Beauchemin e Burkitt 1994, Barron, Beauchemin e

Fleet 1994, Beauchemin e Barron 1995, McCane, Galvin, Novins e Mills 1998, McCane,

Galvin e Novins 1998, McCarthy e Barnes 2004, Liu et al. 1998, Caldeira 2002]. Tais

estudos utilizaram diversas medidas de conﬁabilidade para testar vários algoritmos. Den-

tre essas medidas podem ser citados o erro angular e a magnitude da diferença entre os

vetores de velocidade estimados e corretos (quando disponíveis). O trabalho de Barron,

Fleet, Beauchemin e Burkitt (1994) sugere o método baseado em fase de Fleet e Jepson

como sendo o que produz resultados mais precisos em termos gerais. No entanto, tra-

tam de diversas desvantagens em relação a tal método, como por exemplo seu alto custo

computacional. Seu trabalho também sugere o método de Lucas e Kanade (1981) como

o mais eﬁciente apesar de produzir estimativas menos precisas. McCane, Galvin, Novins

e Mills (1998) também sugeriram o método de Lucas e Kanade (1981) como o de melhor

desempenho geral. Em seu trabalho, eles concluiram que o algoritmo de Proesmans et al.

(1994) possui bom desempenho, com a vantagem adicional de produzir um vetor de ﬂuxo

para cada pixel.

2.2.4 Fluxo Óptico a partir da Informação de Cor

A informação de luminância é amplamente utilizada como entrada de baixo nível em

aplicações de Visão Computacional, mesmo quando a informação de cor está disponí-

vel. A extensão da detecção de características para o domínio de cor previne perda de

informação devido à isoluminância e permite-nos explorar informações fotométricas. Em

contrapartida, uma maior quantidade de dados deve ser processada. Uma imagem colo-

rida corresponde a uma imagem "multi-canal", onde cada pixel possui mais de um valor

associado que representam informação de cor e intensidade de brilho. A informação de

cor habilita um sistema de visão a solucionar problemas que requerem uma maior quanti-

2.2. FLUXO ÓPTICO

dade de informação presente em cada pixel da imagem. Sendo assim, a informação de cor

obtida com o uso de uma imagem multi-canal pode ser utilizada no cálculo do ﬂuxo óp-

tico, dispensando o uso de restrições adicionais como no caso da utilização de imagens em

escala de cinza [Golland e Bruckstein 1997, Tagliasacchi 2006, Ohta e Nishizawa 2006].

A imagem colorida representa uma fonte natural de informação adicional que pode fa-

cilitar a solução do problema da abertura (Seção 2.2.2). Ohta (1989) foi um dos primeiros

a propor um método de detecção que não usa restrições adicionais sobre os movimentos

presentes na cena. Segundo ele, o uso da informação de cor poderia reduzir a dependência

de tais considerações. Ohta propõe a utilização dos canais de informação de uma imagem

colorida para derivar as equações suﬁcientes ao cálculo do ﬂuxo óptico em cada pixel.

Uma imagem multi-canal, tal como uma imagem colorida, consiste em mais de uma

imagem, signiﬁcando disponibilidade em derivar mais de uma informação a partir de um

ponto na imagem da cena. A Equação 2.11 pode ser aplicada para cada um dos n canais

da imagem resultando em um sistema com n equações e apenas 2 variáveis, v

e v

, dado

por

+ I

= 0,

+ I

= 0,

+ I

= 0

. (2.22)

A partir daí, dois ou mais canais podem ser escolhidos para o cálculo de v

e v

. Caso

todos os canais sejam utilizados, as componentes do ﬂuxo podem ser determinadas utili-

zando uma técnica de mínimos quadrados. Diversas representações de cores podem ser

utilizadas, como: RGB (Red, Green, Blue), HSV (Hue, Saturation, Value) e YUV (Y - lu-

minance, UV - chrominance). A utilização da informação de cor deve ser baseada no fato

de que os gradientes espaciais obtidos a partir dos diferentes canais sejam independen-

tes. Assim, analisar a independência desses gradientes é equivalente a investigar quanto a

informação de cor reduz o problema da abertura.

Apesar de não ter apresentado algoritmo, método, ou resultados, a discussão aberta

por Ohta (1989) despertou a comunidade cientíﬁca sobre a estimação de ﬂuxo óptico ba-

seada em informação de cor das imagens. Markandey e Flichbaugh (1990) utilizaram

restrições multi-espectrais para estimar os vetores de ﬂuxo óptico. Eles usaram uma com-

binação de imagens infravermelhas e visíveis em seus experimentos. Golland e Brucks-

tein (1997) propuseram um método que utiliza a conservação de cor na cena para derivar

equações baseadas em informação de cor fornecida pelos modelos HSV e RGB norma-

lizado, e com isso calcular os vetores de ﬂuxo óptico. O método de Andrews e Lovell

CAPÍTULO 2. DETECÇÃO DO MOVIMENTO INERENTE A UMA CENA

(2003) extendeu a equação de restrição do ﬂuxo óptico para imagens coloridas. Um mé-

todo baseado em invariantes fotométricas foi proposto por Weijer e Gevers (2004). Zhang

e Lu (2000) utilizaram correlação de regiões da imagem (block matching) para estimar

o ﬂuxo baseado na informação de cor e bordas presentes nas imagens. A estimação do

ﬂuxo óptico baseada em imagens coloridas subaquáticas foi tratada por Madjidi e Ne-

gahdaripour (2003), que posteriormente ﬁzeram uma análise da robustez e precisão de

vários métodos [Madjidi e Negahdaripour 2004]. Gong et al. (2004) generalizaram o mé-

todo de Horn e Schunck (1981) para uma sequência de imagens multi-canais aplicado a

imagens coloridas em multiresolução.

Método de Golland

Golland e Bruckstein (1997) propuseram um método que usa quantidades que repre-

sentam propriedades intrínsecas de cor de um objeto, mais precisas que valores dos canais

do sistema de cor RGB. Tal consideração baseia-se na conservação de cor que, segundo

Golland, mostra-se mais realista que a conservação de brilho.

A geometria do processo de reﬂexão pode mudar signiﬁcativamente com o movi-

mento do objeto. Golland (1995) demonstra que a componente espectral de cada canal

de cor primária, R, G ou B, independe da geometria do processo de reﬂexão. Embora

seja impossível extrair explicitamente a informação da componente espectral, a razão de

uma combinação linear de dois ou mais dos canais RGB, corresponde à razão de duas ou

mais de suas componentes espectrais. Assim, a razão entre os canais continuará invari-

ante ao movimento. Golland utiliza dois modelos de representação de cor baseados em

relações dos canais RGB: RGB normalizado e HSV. Dois canais de informação de cor são

escolhidos e as Equações 2.22 são utlizadas no cálculo do ﬂuxo óptico em cada pixel da

imagem.

Barron e Klette (2002) realizaram uma análise qualitativa e quantitativa de diversos

métodos multi-canais de ﬂuxo óptico. O método de Golland e Bruckstein (1997) foi

implementado com ponderações para cada canal de cor. O vetor de ﬂuxo foi assumido

constante em uma vizinhança (2n+1)×(2n+1). Caso n = 0, obtém-se o método original

de Golland. O método de Lucas e Kanade (1981) padrão para valores na escala de cinza

pode ser obtido atribuindo 0 a todos os pesos, exceto para o canal referente a informação

de brilho, que seria 1. O método de Horn e Schunck (1981) também foi remodelado

utilizando pesos que indicam a importância associada a cada canal de cor da imagem.

A análise de Barron e Klette (2002) mostra que a precisão das estimativas pode ser

sensivelmente melhorada se imagens coloridas estiverem presentes. O método que utiliza

2.2. FLUXO ÓPTICO

peso igual a 1 para todos os canais da imagem, e assume o vetor de ﬂuxo constante em

uma vizinhança (2n+1)×(2n+1), apresentou melhores resultados. Tal método constitui

uma modiﬁcação do algoritmo original de Lucas e Kanade.

2.2.5 Método Proposto

O método proposto neste trabalho [Aires e Medeiros 2007] é baseado no algoritmo

de Lucas e Kanade (1981). Cada quadro da sequência deimagens é dividido em regiões de

tamanho N ×N, onde os pixels dentro de cada região são assumidos possuirem o mesmo

valor de ﬂuxo óptico associado. Para o cálculo do vetor de ﬂuxo em cada região, somente

alguns dos pixels são escolhidos, mas igualmente distribuídos no espaço da região, como

na Figura 2.9.

Imagem

Janela NxN

Figura 2.9: Os pixels de cor preta são utilizados no cálculo do ﬂuxo óptico da região.

Para cada região N ×N é calculado um vetor de ﬂuxo óptico v = (v

) que cor-

responde a todos os pixels da região. Assim, para cada região é formado um sistema de

equações dado por

Ax1

+ I

Ay1

+ I

At1

= 0

Axn

+ I

Ayn

+ I

Atn

= 0

Bx1

+ I

By1

+ I

Bt1

= 0

Bxn

+ I

Byn

+ I

Btn

= 0

Cx1

+ I

Cy1

+ I

Ct1

= 0

Cxn

+ I

Cyn

+ I

Ctn

= 0

(2.23)

onde A, B e C representam os canais do sistema de cor utilizado. Por exemplo, I

By1

CAPÍTULO 2. DETECÇÃO DO MOVIMENTO INERENTE A UMA CENA

representa a derivada parcial em relação a y, calculada para o pixel 1, do canal B.

O sistema de equações 2.23 possui 3n equações em duas variáveis e pode ser escrito

na forma matricial como

A·v+ b = 0, (2.24)

onde v é o vetor de ﬂuxo óptico, A é a matriz 3n×2 de derivadas parciais espaciais, e b

o vetor 3n de derivadas temporais. A solução do Sistema 2.24 é encontrada pelo método

da pseudo-inversa

v = (A

−1

·(A

b). (2.25)

A matriz A

A da Equação 2.25 deve ser não-singular. O número de condição, n

, da

matriz A

A é utilizado para medir a estabilidade numérica do sistema de equações 2.24.

Caso n

esteja acima de um certo limiar, o vetor v é dito indeﬁnido naquela localização

da imagem [Barron e Klette 2002]. O número de condição n

de uma matriz B é dado por







||B||·||B

−1

||, se B é não-singular

∞, se B é singular

. (2.26)

O passo seguinte do método proposto consiste em ﬁltrar o campo de vetores de ﬂuxo

óptico calculado para a imagem. Um ﬁltro baseado na distância euclidiana entre os veto-

res de ﬂuxo é utilizado. Um vetor de ﬂuxo de uma região N ×N somente é aceito como

válido caso exista pelo menos uma região vizinha (vizinhança-8), onde o quadrado da

distância euclidiana entre seus vetores de ﬂuxo não exceda 20% da magnitude do vetor

da janela em questão. A Figura 2.10 ilustra o método empregado.

Figura 2.10: Porção do quadro da imagem com 09 regiões N ×N. O vetor de ﬂuxo da

região central é aceito como válido por existir dentre seus vizinhos, pelo menos um com

vetor de ﬂuxo que satisfaz as condições do ﬁltro.

2.2. FLUXO ÓPTICO

2.2.6 Testes e Resultados

As imagens utilizadas nos experimentos foram previamente suavizadas com um ﬁltro

gaussiano de tamanho 3 ×3 e desvio padrão σ = 2.5. As derivadas parciais espaciais

foram aproximadas utilizando a máscara de Sobel [Gonzalez e Woods 2007], enquanto

que o método das diferenças ﬁnitas [Horn e Schunck 1981] foi utilizado para a derivada

temporal.

Visando uma análise das vantagens e desvantagens da utilização da informação de cor

na estimação do ﬂuxo óptico, três experimentos foram realizados. No primeiro experi-

mento [Aires e Araújo 2008], foi veriﬁcado o condicionamento da matriz A de gradientes

espaciais da Equação 2.25. A matriz A é dada por

A =





. (2.27)

onde I

e I

, i = 1,2 são os gradientes espaciais nas direções x e y do canal i do sistema

de cor em questão. Três modelos de cor foram utilizados nos experimentos: RGB nor-

malizado, YUV e HSV. Para cada teste realizado nas imagens da Figura 2.11, um canal

de cor foi descartado e somente os dois canais remanescentes foram usados para obter a

matriz A. Pixels para os quais o número de condição da matriz A correspondente esteja

acima de um certo limiar são descartados. Este limiar foi empiricamente escolhido igual

a 20.

(a) Flores (b) Frutas

Figura 2.11: Exemplos de imagens utilizadas nos testes.

Além disso, o ângulo entre os vetores de gradiente espacial foi analisado como me-

dida de conﬁabilidade do vetor de ﬂuxo estimado. Somente foram considerados os pixels

com magnitude do vetor de gradiente acima de 15% do valor máximo de magnitude en-

CAPÍTULO 2. DETECÇÃO DO MOVIMENTO INERENTE A UMA CENA

contrado. Os resultados são ilustrados em dois gráﬁcos. Um histograma que mostra o

número de pixels como uma função do ângulo entre os vetores de gradiente. O histo-

grama foi particionado em porções de 10

no intervalo [0

,180

]. O outro é um gráﬁco

3D que mostra a relação entre o número de condição, o ângulo entre os vetores de gradi-

ente e o número de pixels. Os gráﬁcos são apresentados nas Figuras 2.12 - 2.17.

A análise do condicionamento da matriz A é feita de acordo com o número de condi-

ção e o ângulo entre os gradientes. Neste caso, o mal-condicionamento da matriz é veri-

ﬁcado quando o número de condição for maior que um limiar especiﬁcado, ou quando o

ângulo entre os gradientes for próximo de 0

ou de 180

. De acordo com os resultados

apresentados, a quantidade de pixels que provocam o mal-condionamento da matriz A é

menor quando o sistema de cor YUV é utilizado.

O segundo experimento [Aires e Araújo 2008] consiste em calcular o erro angular e

de magnitude entre o ﬂuxo óptico estimado e o ﬂuxo conhecido. Para a obtenção do ﬂuxo

real, dois tipos de movimento foram aplicados nas imagens. Um deslocamento nos eixos

x e y e um procedimento de zoom, conhecidos. Os dados apresentados na Tabela 2.4

mostram que os vetores de ﬂuxo estimados são mais precisos quando o método proposto

é utilizado a partir da informação de cor do sistema YUV.

Tabela 2.4: Erro de magnitude (pixel) e erro angular (graus) do ﬂuxo óptico estimado

em movimentos de zoom e deslocamento da câmera para as imagens da Figura 2.11. O

ﬂuxo óptico foi estimado utilizando o método de Lucas e Kanade (L&K) para imagens

em preto e branco (P&B), e o método proposto utilizando três sistemas de cores: HSV,

YUV e nRGB.

L&K Método Proposto

P&B HSV YUV nRGB

Flores

Zoom

Mag. 0.1430 0.1876 0.1252 0.1652

Ang. 2.7035 3.8045 2.5278 3.3558

Desloc.

Mag. 0.2781 0.2217 0.2524 0.2171

Ang. 1.5538 1.3441 1.2735 1.2692

Frutas

Zoom

Mag. 0.1861 0.2694 0.1547 0.2595

Ang. 3.0473 4.0533 2.6847 4.3048

Desloc.

Mag. 0.5466 0.5195 0.4933 0.4691

Ang. 1.8891 2.0090 1.5171 1.8133

No terceiro e último experimento [Aires, Santana e Medeiros 2008], alguns dos mé-

todos apresentados foram aplicados às imagens ilustradas na Figura 2.18 (pág. 47). Uma

análise simples e preliminar é feita para cada caso apresentado a seguir, visto que o mapa

de ﬂuxo óptico real não está disponível. Nos métodos que utilizam informação de cor, o

sistema YUV foi o escolhido por apresentar os melhores resultados.

2.2. FLUXO ÓPTICO

(a) Canais H e S

(b) Canais H e V

Figura 2.12: Histograma de ângulos e gráﬁco que ilustra a relação entre o número de

condição, ângulo entre os gradientes dos canais de cores e a quantidade de pixels (eixo

vertical). Resultados para a imagem da Figura 2.11a, utilizando o modelo de cor HSV.

CAPÍTULO 2. DETECÇÃO DO MOVIMENTO INERENTE A UMA CENA

(a) Canais R e G

(b) Canais R e B

Figura 2.13: Histograma de ângulos e gráﬁco que ilustra a relação entre o número de

condição, ângulo entre os gradientes dos canais de cores e a quantidade de pixels (eixo

vertical). Resultados para a imagem da Figura 2.11a, utilizando o modelo de cor RGB

normalizado.

2.2. FLUXO ÓPTICO

(a) Canais Y e U

(b) Canais Y e V

Figura 2.14: Histograma de ângulos e gráﬁco que ilustra a relação entre o número de

condição, ângulo entre os gradientes dos canais de cores e a quantidade de pixels (eixo

vertical). Resultados para a imagem da Figura 2.11a, utilizando o modelo de cor YUV.

CAPÍTULO 2. DETECÇÃO DO MOVIMENTO INERENTE A UMA CENA

(a) Canais H e S

(b) Canais H e V

Figura 2.15: Histograma de ângulos e gráﬁco que ilustra a relação entre o número de

condição, ângulo entre os gradientes dos canais de cores e a quantidade de pixels (eixo

vertical). Resultados para a imagem da Figura 2.11b, utilizando o modelo de cor HSV.

2.2. FLUXO ÓPTICO

(a) Canais R e G

(b) Canais R e B

Figura 2.16: Histograma de ângulos e gráﬁco que ilustra a relação entre o número de

condição, ângulo entre os gradientes dos canais de cores e a quantidade de pixels (eixo

vertical). Resultados para a imagem da Figura 2.11b, utilizando o modelo de cor RGB

normalizado.

CAPÍTULO 2. DETECÇÃO DO MOVIMENTO INERENTE A UMA CENA

(a) Canais Y e U

(b) Canais Y e V

Figura 2.17: Histograma de ângulos e gráﬁco que ilustra a relação entre o número de

condição, ângulo entre os gradientes dos canais de cores e a quantidade de pixels (eixo

vertical). Resultados para a imagem da Figura 2.11b, utilizando o modelo de cor YUV.

2.2. FLUXO ÓPTICO

(a) Ferrari 01 (b) Ferrari 02

Figura 2.18: Exemplos de imagens utilizadas nos testes.

Os métodos de Lucas e Kanade (1981), de Bouguet (1999) e de Caldeira (2002), além

do método proposto foram implementados com o valor N = 10 que deﬁne o tamanho da

região de suavidade local. Para o método de Caldeira (2002), 1/8 dos pixels de cada

região N×N foram escolhidos para o cálculo do ﬂuxo. No método proposto somente 1/9

dos pixels foram utilizados.

Os resultados apresentados nas Figuras 2.19 e 2.20 mostram que o método proposto

foi o que apresentou melhores resultados. O campo de ﬂuxo resultante possui uma maior

quantidade de vetores válidos. Os piores resultados foram obtidos com o método de Gol-

land (1995). O ﬂuxo estimado obtido foi o menos denso, em algumas situações não

detectando movimento na sequência de imagens. O método de Bouguet (1999), utili-

zando imagens em nível de cinza, apresentou resultados muito próximos dos resultados

do método proposto, mas apresentou falhas na estimação do ﬂuxo a partir de imagens

com variação de iluminação, como ilustrado na Figura 2.20

De acordo com as medições feitas sobre a validade dos vetores de ﬂuxo calculados,

a utilização da informação de cor possibilitou um acréscimo de até 30% na quantidade

de medidas estimadas consideradas como válidas, em relação aos métodos que utilizam

informação em escala de cinza. Conforme o modelo de cor utilizado, talvez não seja

necessária a utilização de todos os canais de informação de uma imagem tri-canal. A

utilização de apenas dois canais do modelo de cor YUV (YU, YV ou UV) apresentou

diferenças da ordem de apenas 5% de medidas válidas entre as escolhas utilizadas, e em

torno de 7% abaixo quando da utilização dos três canais.

O aumento do tamanho da janela de observação possibilita uma diminuição na carga

de processamento. Ainda, o uso de aleatoriedade na escolha dos pixels dentro de uma

janela N ×N, como no método de Caldeira (2002), pode comprometer a estimação do

CAPÍTULO 2. DETECÇÃO DO MOVIMENTO INERENTE A UMA CENA

(a) Lucas e Kanade (b) Eliete

Figura 2.19: Resultados para a imagem 2.18a

(a) Bouguet (b) Método proposto

Figura 2.20: Resultados para a imagem 2.18b.

2.2. FLUXO ÓPTICO

vetor. Testes mostraram que uma igual distribuição espacial na escolha dos pixels dentro

da janela favorece a estimativa. Além disso, o método de cálculo do gradiente inﬂuencia

diretamente no resultado do vetor de ﬂuxo calculado.

Por ﬁm, os testes realizados mostraram que a utilização da informação de cor con-

tribui para aumentar a densidade do campo de ﬂuxo óptico estimado. Em contrapartida,

a quantidade de informação fornecida aumenta com o uso de cores no cálculo do ﬂuxo

óptico e como consequência, um aumento na carga de processamento. A escolha de uma

certa quantidade de pixels em uma janela de ﬂuxo constante, N×N, pode ser feita levando

em conta sua relevância no cálculo do referido vetor de ﬂuxo. O estudo desta relevância,

como o feito por Sebastien (2003), pode fazer com que a quantidade de pixels a ser utili-

zado diminua, o que contribuiria para uma maior conﬁabilidade na estimação do vetor de

ﬂuxo óptico.

CAPÍTULO 2. DETECÇÃO DO MOVIMENTO INERENTE A UMA CENA

Capítulo 3

Geometria de Duas Imagens

Apesar da grande quantidade de informação contida em uma imagem, os dados a res-

peito de profundidade em uma cena não estão disponíveis. Utilizando as informações

fornecidas por duas imagens, a profundidade pode ser calculada através de um procedi-

mento de triangulação. De forma clara, isto explica o fato de que a maioria dos animais

possuem dois olhos ou, caso possuam somente um, moverem a cabeça para perceber a

profundidade da cena [Forsyth e Ponce 2002]. Tais conceitos servem como motivação

para equipar um robô autônomo com um conjunto de câmeras estéreo ou com um sistema

monocular capaz de realizar uma análise precisa de seu movimento e do ambiente que o

cerca.

Na maioria das aplicações em visão computacional, um sistema capaz de adquirir

imagens de uma cena pode ser constituído de duas câmeras, no caso de um sistema es-

téreo, ou somente uma câmera, no caso do sistema monocular. No primeiro caso, cada

uma das duas imagens a serem tratadas é adquirida por cada câmera separadamente no

espaço. Já no segundo caso, as imagens são adquiridas pela mesma câmera segundo um

intervalo de tempo determinado. A partir desta deﬁnição, pode-se mostrar que a primeira

imagem de qualquer ponto deve estar no plano formado pela segunda imagem do mesmo

ponto e pelos centros ópticos das câmeras no momento da aquisição. No caso de um

sistema monocular em movimento, o centro óptico é o mesmo mas estará em posições

diferentes dentro de um determinado intervalo de tempo. Tal conceito, conhecido como

restrição epipolar, pode ser representado algebricamente por uma matriz chamada de ma-

triz essencial quando os parâmetros intrínsecos das câmeras são conhecidos, e de matriz

fundamental caso contrário.

As seções a seguir permitem um melhor entendimento dos conceitos que se refe-

rem a geometria epipolar, matriz fundamental e matriz essencial, bem como a relação

entre tais conceitos. Antes disso, o primeiro passo na análise e reconstrução de cenas

consiste no entendimento da geometria projetiva. A geometria projetiva descreve con-

CAPÍTULO 3. GEOMETRIA DE DUAS IMAGENS

ceitos e fundamentos relacionados à projeção de uma cena em uma imagem. Um deta-

lhamento mais profundo dessas deﬁnições pode ser obtido em [Faugeras 1993, Forsyth e

Ponce 2002, Hartley e Zisserman 2004].

3.1 Pontos e Retas

Pontos em um espaço n-dimensional R

são representados por um vetor coluna de

coordenadas com dimensão n+ 1 descrito por



... q

n+1



. Tais coordenadas

são conhecidas como coordenadas homogêneas. Desta forma, um ponto no espaço 3D

é representado por Q =



X Y Z 1



no sistema de coordenadas do mundo, enquanto

que suas coordenadas da imagem na retina são descritas pelo ponto q =



x y 1



coordenadas homogêneas no espaço 2D.

A reta no plano é representada pela equação ax+ by+ c = 0. Diferentes valores de a,

b e c deﬁnem diferentes retas. Uma reta pode ser representada pelo vetor homogêneo de

coordenadas l =



a b c



. O ponto q estará sobre a reta l se e somente se seu produto

interno for igual a zero, ou seja, l·q = l

q = 0. Do mesmo modo, planos no espaço são

representados pela letra grega π usando vetores de coordenadas homogêneas de dimensão

4. A incidência de um ponto no plano é veriﬁcada pela equação π

Q = 0.

3.2 Modelo da Câmera

A câmera é um dispositivo capaz de executar um mapeamento entre o mundo 3D e a

imagem 2D. O modelo de câmera pinhole é amplamente utilizado e executa uma perfeita

transformação em perspectiva de um espaço 3D para o plano da imagem. De certa forma,

também precisa ser levado em conta a mudança de coordenadas dos pontos do sistema do

mundo para o sistema da imagem. Generalizando, a câmera executa uma transformação

linear projetiva ao invés de uma mera transformação em perspectiva.

Ao ser considerada a projeção central de pontos no espaço em um plano, alguns con-

ceitos são relevantes. De acordo com a Figura 3.1, a reta que passa pelo centro de projeção

da câmera, também chamado de centro óptico, perpendicular ao plano da imagem é cha-

mada de eixo principal da câmera, e o ponto onde o eixo principal intercepta o plano da

imagem é chamado de ponto principal. O plano através do centro óptico da câmera e

paralelo ao plano da imagem é chamado de plano principal da câmera.

Ainda na Figura 3.1, considere o centro de projeção como sendo a origem do sistema

de coordenadas Euclidiano, e o plano da imagem sendo o plano Z = f. Utilizando o

3.2. MODELO DA CÂMERA

modelo de câmera pinhole, um ponto Q no espaço 3D é mapeado para o ponto no plano

da imagem q. Tal mapeamento pode ser ilustrado por meio de uma reta que une o ponto

Q ao centro de projeção C e encontra o plano da imagem em q.

Eixo Principal

Plano da Imagem

fY/Z

Figura 3.1: Geometria da câmera pinhole. C é o centro da câmera e p o ponto principal.

O centro da câmera está localizado na origem do sistema de coordenadas.

Analisando a Figura 3.1, através da semelhança de triâgulos veriﬁca-se facilmente

que o ponto



X Y Z



no espaço 3D é mapeado para o ponto



fX/Z fY/Z f



plano da imagem. Ignorando a última coordenada da imagem, a expressão



X Y Z



→



fX/Z fY/Z



(3.1)

representa o mapeamento de uma projeção central a partir do sistema de coordenadas do

mundo para o sistema de coordenadas da imagem. O mapeamento em questão relaciona

um espaço Euclideano 3D com um espaço Euclidiano 2D.

Caso os pontos 3D e 2D sejam representados por vetores de coordenadas homogêneas,

então a projeção central é expressada de forma simples como um mapeamento entre suas

coordenadas homogêneas. Em particular, a Equação 3.1 pode ser reescrita em termos de

multiplicação de matrizes como













→



















f 0

1 0



















. (3.2)

As coordenadas de pixel x e y para cada ponto q da imagem são as únicas informações

disponíveis caso a câmera não esteja calibrada. No caso da câmera estar calibrada, a

relação entre o ponto 3D Q e sua projeção q na imagem é dada pela seguinte equação

CAPÍTULO 3. GEOMETRIA DE DUAS IMAGENS

matricial

wq = PQ, (3.3)

onde w é um fator de escala desconhecido e P é a matriz de projeção perspectiva para o

modelo pinhole de projeção central.

A Equação 3.1 assume o ponto principal como sendo a origem do sistema de co-

ordenadas no plano da imagem. Na prática isto pode não acontecer. Desse modo, o

mapeamento pode ser descrito da forma



X Y Z



→



fX/Z + p

fY/Z+ p



(3.4)

onde (p

, p

) são as coordenadas do ponto principal.

A Equação 3.4 pode ser convenientemente expressada em termos de coordenadas ho-

mogêneas como













→







fX + Zp

fY + Zp













f p

1 0



















. (3.5)

Agora, escrevendo

K =







f p







, (3.6)

a Equação 3.5 pode ser escrita de forma simpliﬁcada como

q = K



I | 0



Q. (3.7)

A matriz K é chamada de matriz de calibração da câmera. Aqui, o centro óptico da

câmera é assumido estar localizado na origem do sistema de coordenadas Euclidiano, com

o eixo principal apontando na direção do eixo Z. Este sistema é conhecido como sistema

de coordenadas da câmera.

De maneira geral, os pontos no espaço são descritos em termos de um outro sistema

de coordenadas Euclidiano, conhecido como sistema de coordenadas do mundo. Os dois

sistemas de coordenadas estão relacionados por uma rotação e uma translação, como

ilustrado na Figura 3.2.

Conforme a tranformação Euclidiana entre os sistemas de coordenadas do mundo e

3.2. MODELO DA CÂMERA

R, t

cam

Figura 3.2: Transformação Euclidiana entre o sistema de coordenadas do mundo e o

sistema de coordenadas da câmera.

da câmera, a matriz da câmera P pode ser escrita na forma matricial como a equação

P = K



R t



, (3.8)

onde K é a matriz de calibração da câmera, de dimensão 3×3, que realiza o mapeamento

entre as coordenadas normalizadas da imagem (cm) e as coordenadas de imagem na retina

da câmera (pixels). Além disso, (R,t) descreve a rotação e a translação a partir do sistema

de coordenadas do mundo para o sistema de coordenadas da câmera.

As coordenadas normalizadas

q da imagem são obtidas através da remoção do efeito

da matriz de calibração K no sistema de aquisição da imagem, de acordo com a expressão

q = K

−1

q. (3.9)

No caso de um sistema de aquisição de imagens constituído por uma única câmera em

movimento, as matrizes de projeção normalizadas para duas imagens da mesma cena são

representadas por

P =



I | 0



′



R | t



, (3.10)

onde o sistema de coordenadas do mundo está ajustado na posição da câmera no momento

da aquisição da primeira imagem da cena.

Todos os quantiﬁcadores geométricos citados anteriomente relacionados à segunda

vista da mesma câmera são indicados por

′

. Por exemplo, caso q seja um ponto na

primeira imagem da cena, q

′

será o ponto correspondente na segunda imagem da mesma

cena.

CAPÍTULO 3. GEOMETRIA DE DUAS IMAGENS

3.2.1 Câmera CCD

No modelo de câmera pinhole as coordenadas da imagem são coordenadas Euclidi-

anas. Tal fato implica em as coordenadas possuirem igual escala em ambas as direções

axiais. No caso de câmeras CCD, existe a possibilidade de os pixels não serem quadrados.

Como as coordenadas de imagem são medidas em pixels, esta característica das câmeras

CCD introduz fatores de escala desiguais em cada direção axial. Caso o número de pixels

por unidade de distância em coordenadas de imagem seja m

e m

nas direções x e y,

então a transformação das coordenadas do mundo para as coordenadas de imagem pode

ser obtida multiplicando a Equação 3.6 por um fator de escala diag(m

,1). Assim, a

matriz de calibração para câmeras CCD pode ser formulada como

K =













, (3.11)

onde α

= fm

e α

= fm

representam o comprimento focal da câmera em pixels nas

direções x e y, respectivamente. Da mesma forma, q

= (x

) é o ponto principal com

coordenadas x

= m

e y

= m

, também em pixels.

Geralmente, as câmeras CCD fornecem um sinal de vídeo analógico a um disposi-

tivo digitalizador que o converte em sinal digital. Nos últimos anos, cada vez mais as

webcam’s com sensores CCD têm sido utilizadas em aplicações envolvendo robôs, prin-

cipalmente devido ao seu baixo custo. A maioria dessas câmeras utilizam interface USB

(Universal Serial Bus) como forma de comunicação direta com o computador, evitando

assim o uso de um dispositivo digitalizador de imagens, o que torna o projeto ainda mais

viável ﬁnanceiramente.

3.3 Homograﬁa Planar

As imagens de um objeto plano a partir de duas diferentes perspectivas são relaciona-

dos por uma homograﬁa. Também chamada de transformação projetiva planar, colineação

ou projetividade, uma homograﬁa descreve um mapeamento linear entre espaços planares

bidimensionais.

Considere duas imagens do mesmo plano π e um ponto Q

deste plano. Desta forma,

q e q

′

representam as projeções de Q

na primeira imagem I e na segunda imagem I

′

, res-

pectivamente. O mapeamento q ↔ q

′

corresponde à homograﬁa H induzida unicamente

pelo plano π, conforme é ilustrado na Figura 3.3.

3.3. HOMOGRAFIA PLANAR

C C’

e’e

q q’

l’

I I’

Figura 3.3: Considere duas imagens I e I

′

do mesmo plano π, a homograﬁa planar H

consiste em um mapeamento dos pontos q da imagem I para os pontos q

′

da imagem I

′

A homograﬁa planar é representada por uma matriz não-singular H de dimensão 3×3.

A relação entre os pontos 2D das duas imagens de um mesmo ponto 3D pertencente a um

plano no espaço pode ser expressada pela seguinte equação







′







≃

























, (3.12)

ou, em sua forma matricial por

′

≃ Hq. (3.13)

A homograﬁa H da Equação 3.13 pode ser alterada através da multiplicação por um

fator de escala não-zero arbitrário sem no entanto alterar a transformação projetiva a qual

representa. Consequentemente, pode ser dito que H é uma matriz homogênea visto que,

em uma representação homogênea de um ponto, somente a relação dos elementos da

matriz é signiﬁcativa. Em vista disso, na Equação 3.12, a matriz H possui 9 entradas

mas é deﬁnida por um fator de escala. Este fato justiﬁca o uso da aproximação (≃) na

Equação 3.12, além de deﬁnir o número de graus de liberdade igual a 8.

Em uma transformação projetiva, torna-se evidente que o mapeamento ponto-a-ponto

preserva retas. Dado que o ponto q está sobre a reta l, então

q = 0. (3.14)

Duas imagens da mesma reta L no espaço 3D, dadas por l e l

′

, estão relacionadas por uma

CAPÍTULO 3. GEOMETRIA DE DUAS IMAGENS

transformação dada por uma homograﬁa H, de forma a satisfazer a Equação 3.14. Desta

maneira, a transformação aplicada a uma reta é expressa pela equação matricial

′

≃ H

−T

l. (3.15)

3.3.1 Homograﬁa Aﬁm

Uma homograﬁa entre duas imagens de uma mesma superfície planar pode ser apro-

ximada por uma transformação aﬁm caso o deslocamento da câmera entre as duas aquisi-

ções seja pequeno. A homograﬁa aﬁm H

é um caso especial de homograﬁa planar e pode

ser deﬁnida como uma transformação linear não-singular seguida por uma translação. A

representação da matriz H

é formulada como na Equação 3.16

′

= H

q =



A t



q. (3.16)

A homograﬁa aﬁm H

possui 6 graus de liberdade que correspondem aos seis ele-

mentos indeﬁnidos da matriz, e tem a forma







0 0 1







. (3.17)

3.4 Estimação da Homograﬁa Planar

A estimação de homograﬁas a partir de imagens constitui um importante processo

em tarefas como calibração [Zhang 2002], retiﬁcação métrica [Criminisi et al. 2000],

reconstrução 3D [Li e Chellappa 2006, Zhang e Xiao 2008], odometria visual [Wang

et al. 2005], etc. Para algumas aplicações, apenas uma simples similaridade ou transfor-

mação aﬁm pode ser suﬁciente. Em outras situações, uma transformação completa se faz

necessária. Como exemplo, problemas referentes a reconhecimento 3D frequentemente

necessitam de um tratamento completo sobre a transformação projetiva em questão [Jain

e Jawahar 2006].

Algumas características presentes em imagens como pontos e retas são os principais

tipos de dados utilizados na estimação de homograﬁas. Os métodos de estimação recupe-

ram a homograﬁa como uma relação linear entre pontos, sendo aplicados na recuperação

da homograﬁa induzida por um plano dado um número suﬁciente de pares de pontos

correspondentes entre as duas imagens da mesma cena.

3.4. ESTIMAÇÃO DA HOMOGRAFIA PLANAR

Esta seção ilustra dois métodos baseados em correspondência de pontos. Existe na

literatura uma grande variedade de métodos, como aqueles baseados em retas [Zeng

et al. 2008], baseados em pontos e retas [Dubrofsky e Woodham 2008] e baseados em

contornos [Jawahar 2006, Ruiz et al. 2006]. Agarwal et al. (2005) apresenta uma interes-

sante investigação sobre métodos de estimação de homograﬁa.

3.4.1 Transformação Linear Direta (DLT)

Considere um par de pontos correspondentes q

↔ q

′

, entre duas imagens da mesma

cena. A Equação 3.13 pode ser expressa em termos do produto vetorial q

′

×(Hq

) = 0.

Seja a j-ésima linha da matriz H descrita por h

, a seguinte expressão pode ser obtida













. (3.18)

Dado que o ponto q

′

pode ser escrito como o vetor de coordenadas



′



, o

produto vetorial citado anteriormente pode ser escrito explicitamente como

′

×Hq







′

−w

′

−x

′

−y

′







. (3.19)

A Equação 3.19 pode ser reescrita na forma







−w

′

−x

′

−y

′



















= 0. (3.20)

A Equação 3.20 forma um sistema de três equações, mas somente duas delas são

linearmente independentes. Sendo assim, cada par de pontos correspondentes fornece

duas equações relacionadas com as entradas da matriz H. O sistema composto por essas

duas equações formuladas por cada par correspondente é dado por



−w

′

−x

′















= 0. (3.21)

CAPÍTULO 3. GEOMETRIA DE DUAS IMAGENS

Considere um conjunto de 4 pares de pontos correspondentes q

↔ q

′

, i = 1, 2, 3, 4.

Um sistema de equações S

h = 0 é obtido a partir da Equação 3.21, onde a matriz S é

obtida a partir de cada par de correspondências e h é o vetor de entradas da matriz H a

serem estimadas. Tal sistema pode ser escrito como







0 0 0 −w

′

−w

′

−w

′

0 0 0 −x

′

−x

′

−x

′

0 0 0 −w

′

−w

′

−w

′

0 0 0 −x

′

−x

′

−x

′

0 0 0 −w

′

−w

′

−w

′

0 0 0 −x

′

−x

′

−x

′

0 0 0 −w

′

−w

′

−w

′

0 0 0 −x

′

−x

′

−x

′



















= 0.

(3.22)

Na prática, os pontos extraídos das imagens não satisfazem a relação q

′

= Hq

devido

ao ruído existente na extração destes pontos a partir das imagens utilizadas. Assim, a

estimação de H é obtida pela minimização de um funcional, ou seja, encontrar H de tal

forma que q

′

−Hq

 seja mínimo.

O número de medições está relacionado ao número de características correspondentes

nas duas imagens necessárias para validar a transformação projetiva H. Conforme expli-

cado na Seção 3.3, a matriz H possui 8 graus de liberdade. Quatro correspondências de

pontos ou retas são suﬁcientes para computar H, visto que cada correspondência produz

duas equações em H ao ser utilizada a Equação 3.21.

A utilização do número mínimo de pares de pontos correspondentes na estimação de

H pode apresentar resultados pouco robustos ao ruído presente. Portanto, um número de

características acima do mínimo necessário pode ser utilizado para tornar a solução mais

precisa.

Considere agora n pares de pontos correspondentes entre duas imagens de um mesmo

plano. Esses pares de pontos podem ser relacionados por uma homograﬁa H e utilizados

para formular um sistema de equações na forma matricial como Sh = 0, onde S é uma

matriz 2n×9 de acordo com a Equação 3.22. Para este sistema de equações, o objetivo

é encontrar uma solução h diferente de zero que minimiza uma função de custo aceitável

sujeita à restrição h = 1. O problema reside em encontrar um mínimo para a relação

Hh/h. A solução pode ser dada como o autovetor unitário de S

S com o menor

autovalor associado. De forma equivalente, a solução é o vetor singular associado com o

3.4. ESTIMAÇÃO DA HOMOGRAFIA PLANAR

menor valor singular de S.

A solução pode ser obtida utilizando-se Decomposição em Valores Singulares (SVD).

O SVD de S é obtido como S= UDV

, com D sendo uma matriz diagonal de autovalores

com entradas positivas e organizada em ordem decrescente. Neste caso, h corresponde à

última coluna da matriz de autovetores V. Em seguida, a homograﬁa H é determinada a

partir do vetor h estimado.

O sistema de equações Sh = 0 pode ser mal-condicionado. Portanto, melhores re-

sultados podem ser obtidos através de uma simples normalização nos dados de entrada

utilizados para formular o sistema. Esta normalização irá anular os efeitos da seleção

arbitrária da origem e escala do sistema de coordenadas da imagem, e signiﬁcará que o

algoritmo combinado é invariante a transformação de similaridade da imagem. A seção

seguinte discute este processo.

Normalização dos dados de entrada no cálculo da homograﬁa

Uma transformação de normalização é aplicada às coordenadas dos pontos da imagem

utilizados para estimar a homograﬁa H, como sugerido em [Hartley e Zisserman 2004].

O procedimento é executado em dois passos. Primeiro, as coordenadas são transladadas

de forma que o centróide de todos os pontos esteja na origem do sistema de coordenadas.

Em seguida, as coordenadas são também escalonadas de modo que a distância média dos

pontos à origem seja igual a

√

2. Esta transformação é aplicada a cada um dos pontos das

duas imagens independentemente.

As coordenadas q e q

′

são substituídas por

q = Tq e

′

= T

′

. Assim, utilizando a

Equação 3.13 obtém-se

′−1

′

= HT

−1

q ⇒

′

= T

′

−1

q (3.23)

Isto implica que T

′

−1

é a homograﬁa

H relacionada ao par de pontos correspon-

dentes

′

↔

q. A homograﬁa H relacionada ao par original q

′

↔ q pode ser obtida por

′−1

HT = T

′−1

′

−1

)T = H. (3.24)

O processo de normalização das entradas é aplicado conforme os seguintes passos:

1. Transformação composta por uma translação e um escalonamento das coordenadas

das duas imagens segundo T e T

′

q = Tq e

′

= T

′

;

2. Estimação da homograﬁa

H referente ao par de correspondência

′

↔

3. Cálculo da homograﬁa original aplicando a transformação inversa H = T

′−1

HT.

CAPÍTULO 3. GEOMETRIA DE DUAS IMAGENS

O trabalho apresentado por Hartley (1997) mostrou que a normalização dos dados pro-

picia melhores resultados e deve ser considerada como um passo obrigatório no algoritmo

de estimação da homograﬁa.

3.4.2 RANSAC

O processo de detecção dos pontos de interesse não representa a única fonte de erro

no conjunto de correspondências estabelecidas entre duas imagens. Na prática, as cor-

respondências são calculadas automaticamente e falsos pares de pontos correspondentes

(outliers) são frequentes. Estas falsas correspondências comprometem a estimação da

homograﬁa e necessitam ser identiﬁcadas. Em vista disso, o objetivo consiste em de-

terminar um conjunto de correspondências verdadeiras (inliers) a partir do conjunto de

correspondências calculadas, de modo que a homograﬁa seja estimada de maneira ótima.

O Algoritmo RANSAC (Random Sample Consensus) [Fischler e Bolles 1981] pode

ser utilizado para o cálculo da homograﬁa e obtenção das correspondências verdadeiras

a partir do conjunto de correspondências estabelecido inicialmente. Basicamente, o al-

goritmo RANSAC consiste em selecionar uma amostra inicial de pontos do conjunto de

correspondências e calcular a homograﬁa utilizando o método DLT (Seção 3.4.1). Base-

ado na homograﬁa calculada, falsas correspondências são rejeitadas utilizando-se de um

parâmetro de erro deﬁnido, para em seguida a homograﬁa ser recalculada. O procedi-

mento é melhor explicado no Algoritmo 3.1.

Algoritmo 3.1 Algoritmo RANSAC.

1 Selecionar de forma aleatória 4 pares de pontos correspondentes do conjunto e cal-

cular a homograﬁa.

2 Selecionar todas as correspondências que estejam de acordo com a homograﬁa cal-

culada. Uma correspondência (q;q

′

), está de acordo com a homograﬁa H, se d(Hq,q

′

)

for menor que algum limiar. d(·) representa a distância Euclidiana entre dois pontos.

3 Repetir passos 1 e 2 até que um número suﬁciente de pares de pontos correspondentes

esteja de acordo com a homograﬁa calculada.

4 Recalcular a homograﬁa usando todas as correspondências verdadeiras.

Algumas observações importantes sobre o método RANSAC devem ser levadas em

consideração. O limiar da distância deve ser escolhido de tal forma que a correspon-

dência seja verdadeira com uma certa probabilidade. Na prática, esse limiar é escolhido

de forma empírica de modo que a probabilidade da correspondência entre os pontos ser

verdadeira seja alta, tal como 95%. Em segundo lugar, utilizar todas as possíveis esco-

lhas de pontos correspondentes seria computacionalmente inviável. Ao invés disso, um

3.4. ESTIMAÇÃO DA HOMOGRAFIA PLANAR

grande número de amostras é utilizado de modo que pelo menos um conjunto de 4 cor-

respondências seja verdadeira com uma alta probabilidade, tal como 99%. Outra regra

empregada consiste em ﬁnalizar o procedimento caso o tamanho do conjunto utilizado no

cálculo da homograﬁa seja similar ao conjunto de correspondências verdadeiras presentes

no conjunto inicial de dados.

3.4.3 Estimação da Homograﬁa usando o Modelo Aﬁm

Uma versão modiﬁcada do método DLT (Seção 3.4.1) é aplicada para estimar a homo-

graﬁa no modelo aﬁm H

. Visto que a homograﬁa aﬁm H

, expressa pela Equação 3.17,

possui somente 6 entradas, a Equação 3.13 pode ser reformulada em termos de um con-

junto não-homogêneo de equações lineares como







1 0 0 0

0 0 0 x

1 0 0 0

0 0 0 x

























′







, (3.25)

ou na forma matricial

= X

′

. (3.26)

Na Equação 3.25,





↔



′



, i = 1,. . .,n, são os pares de pontos correspon-

dentes em coordenadas não-homogêneas e H

tem a forma







0 0 1







. (3.27)

Em vista disso, percebe-se que H

pode ser estimada a partir de 3 pares de pontos

correspondentes q

↔q

′

, i = 1,2,3, através da solução da Equação 3.26 usando o método

da pseudo-inversa como

= (X

−1

·X

X’, (3.28)

cujo cálculo é rápido devido às pequenas dimensões das matrizes.

CAPÍTULO 3. GEOMETRIA DE DUAS IMAGENS

3.4.4 Erro de Reprojeção

Uma medida de erro pode ser considerada após uma homograﬁa H ter sido estimada.

Com o objetivo de veriﬁcar se um dado par de pontos correspondentes pertence ao plano

representado por H, o erro de reprojeção pode ser deﬁnido como



−

+ |q

′

−

′

, (3.29)

onde

′

= Hq e

= H

−1

′

Quando o erro de reprojeção e

estiver abaixo de um certo limiar, o par de pontos

correspondentes q

↔ q

′

pertence ao plano representado por H .

3.5 Geometria Epipolar

Considere duas imagens q e q

′

de um ponto no espaço Q adquirido por câmeras com

centros ópticos C e C

′

, como ilustrado na Figura 3.4. Os pontos q, q

′

, Q, C e C

′

perten-

cem ao mesmo plano epipolar, deﬁnido pela interseção das duas semi-retas CQ e C

′

O ponto q

′

encontra-se sobre a reta l

′

onde este plano e o plano da imagem Π

′

da segunda

câmera se interceptam. A reta l

′

é a reta epipolar associada ao ponto q, passando pelo

ponto e

′

, chamado de epipólo, onde a linha-base que une os centros ópticos C e C

′

in-

tercepta o plano da imagem Π

′

. De forma idêntica, o ponto q encontra-se sobre a reta

epipolar l asociada ao ponto q

′

. A reta epipolar l passa pelo epipólo e determinado pela

interseção da linha-base com o plano da imagem Π.

C C’

e’

l’

q q’

′

Figura 3.4: Plano epipolar: o ponto Q, os centros ópticos C e C

′

das duas câmeras, e as

duas imagens q e q

′

de Q estão sobre o mesmo plano.

Os pontos e e e

′

são chamados de epipólos das duas câmeras. O epipólo e

′

corres-

3.5. GEOMETRIA EPIPOLAR

ponde à imagem do centro óptico C da primeira câmera observada pela segunda câmera,

e vice-versa. Como dito anteriormente, se q e q

′

são imagens do mesmo ponto, então

′

deve estar sobre a reta epipolar associada a q. Esta restrição epipolar dita uma regra

fundamental em visão estéreo e análise de movimento.

3.5.1 Matriz Fundamental

A geometria epipolar é um ponto crucial em visão computacional, sendo representada

por uma matriz de dimensão 3×3 chamada de Matriz Fundamental, no caso de o sistema

não estar calibrado, ou de Matriz Essencial para o caso do sistema estar calibrado. A

matriz fundamental encapsula toda a informação geométrica intrínseca contida em duas

imagens da mesma cena. Além disso, consiste na única maneira de calcular a geometria

epipolar [Zhang 1998].

Derivação Geométrica

O mapeamento de um ponto em uma imagem para uma correspondente reta epipolar

em outra imagem pode ser decomposto em dois passos. No primeiro passo, o ponto q

é mapeado para algum ponto q

′

na outra imagem obedecendo a restrição epipolar. No

segundo passo, a reta epipolar l

′

é obtida como uma reta que une q

′

ao epipólo e

′

De acordo com a Figura 3.3, o raio que passa pelo centro óptico da primeira câmera

em direção ao ponto Q no espaço, intercepta o plano da imagem no ponto q. Este ponto

Q é então projetado em um ponto q

′

na segunda imagem. Este procedimento é conhecido

como uma transferência através do plano π. Desde que o ponto Q está sobre o raio

correspondente a q, o ponto projetado q

′

deve estar sobre a reta epipolar l

′

correspondente

à imagem deste raio.

Os pontos q e q

′

são as imagens do ponto Q. O conjunto de todos os pontos q

na pri-

meira imagem e os pontos correpondentes q

′

na segunda imagem são projetivamente equi-

valentes, desde que eles também os sejam ao conjunto de pontos coplanares Q

. Assim,

existe uma homograﬁa H

capaz de mapear cada ponto q

em seu ponto correspondente

′

Seja o ponto q

′

, a reta epipolar l

′

que passa por q

′

e pelo epipólo e

′

pode ser escrita

como l

′

= e

′

×q

′

= [e

′

]

′

, onde [e

′

]

é a matriz anti-simétrica formada a partir do vetor

′

. Desde que q

′

pode ser escrito como q

′

= H

q, a reta epipolar l

′

pode ser dada como

′



′



q = Fq, (3.30)

CAPÍTULO 3. GEOMETRIA DE DUAS IMAGENS

onde a matriz fundamental é deﬁnida por F = [e

′

]

. Sendo assim, desde que [e

′

]

possui rank 2 e H

possui rank 3, F é uma matriz de rank 2.

Derivação Algébrica

A forma da matriz fundamental em termos de duas matrizes de projeção da câmera

P e P

′

, pode ser derivada algebricamente. Assumindo que o sistema de coordenadas do

mundo coincide com o sistema de coordenadas da primeira câmera e utilizando o modelo

pinhole, teremos

sq = K



I 0



Q e s

′

= K



R t



Q. (3.31)

Eliminando Q, s e s

′

obtém-se a relação entre todos os pontos da primeira e segunda

imagens da mesma cena, dada por

′T

′−T

[t]

−1

q = 0, (3.32)

onde F = K

′−T

[t]

−1

Suponha duas imagens adquiridas por câmeras com centros ópticos não-coincidentes,

então a matriz fundamental F é a única matriz homogênea 3×3 que satisfaz a equação

′T

Fq = 0. (3.33)

Propriedades da Matriz Fundamental

A matriz F deﬁnida pela Equação 3.33 possui rank 2 e é deﬁnida por um fator de

escala. Além disso, algumas propriedades da matriz fundamental podem ser enumeradas:

1. Caso F seja a matriz do par de câmeras (P,P

′

), entao F

é a matriz fundamental do

par de câmeras em ordem oposta (P

′

,P).

2. Seja um ponto q na primeira imagem, a reta epipolar correspondente é dada por

′

= Fq. Da mesma forma, l = F

′

representa a reta epipolar correspondente a q

′

na segunda imagem.

3. Para algum ponto q (que não seja e) a reta epipolar l

′

contém o epipólo e

′

. Assim,

′

satisfaz e

′

(Fq) = (e

′T

F)q = 0 para todo ponto q. Portanto, e

′T

F = 0, ou seja, e

′

é o vetor-nulo esquerdo de F. Da mesma forma, Fe = 0, ou seja, e é o vetor-nulo

direito de F.

3.5. GEOMETRIA EPIPOLAR

4. Como matriz homogênea 3 ×3, a matriz F possui 8 graus de liberdade. Além

disso, F também satisfaz a restrição det(F) = 0 que remove um grau de liberdade.

Portanto, a matriz fundamental F possui 7 graus de liberdade.

3.5.2 Estimação da Matriz Fundamental

A estimação da informação tridimensional representa um problema bastante inves-

tigado em visão computacional. Uma forma de solucionar este problema consiste em

calcular a geometria epipolar existente entre duas imagens da mesma cena. A geome-

tia epipolar é baseada essencialmente em correspondência de imagens. Sendo assim, a

estimação da matriz fundamental pode ser feita através de correspondências de pontos

presentes nessas imagens.

Existem diversos métodos para estimar a matriz fundamental. Tais métodos podem

ser classiﬁcados como: lineares, iterativos e robustos. Métodos lineares são rápidos, fá-

ceis de implementar e produzem bons resultados na ausência de falsas correspondências

(outliers). Além disso, são frequentemente utilizados para inicializar os métodos itera-

tivos. Os métodos iterativos representam otimizações dos métodos lineares. Esta classe

de métodos consiste na minimização de uma medida de distância simétrica entre os pon-

tos e as retas epipolares. Geralmente, técnicas não-lineares são utilizadas para minimizar

uma função distância sobre os parâmetros da matriz fundamental e a real localização das

correspondências. Métodos robustos [Torr e Murray 1997] são baseados na detecção de

modelos geométricos mais precisos e remoção de falsas correspondências encontradas

no processo de detecção. Estudos comparativos destes métodos são encontrados na litera-

tura [Luong et al. 1993, Luong e Faugeras 1996, Zhang 1998, Salvi et al. 2001, Armangué

e Salvi 2003]. Baseado nosresultados desses trabalhos, as seções aseguir discutem alguns

desses métodos, concentrando-se principalmente nos métodos lineares.

Algoritmo dos 8-Pontos

O clássico algoritmo dos 8-pontos proposto por Longuet-Higgins (1981) é ampla-

mente utilizado como método linear para o cálculo da geometria epipolar a partir de duas

imagens de uma mesma cena. De acordo com a deﬁnição da matriz fundamental, um

par de pontos correspondentes q =



x y 1



e q

′



′



entre duas imagens deve

satisfazer a Equação 3.33. Esta equação pode ser reescrita como uma equação linear e

homogênea em relação aos elementos da matriz F, como

f = 0, (3.34)

CAPÍTULO 3. GEOMETRIA DE DUAS IMAGENS

onde

m =



′

x y 1



f =





Caso n pares de pontos correspondentes estejam disponíveis, um sistema de equações

lineares é obtido a partir da Equação 3.34, tal como

Af =







′



















= 0, (3.35)

onde cada par de pontos correspondentes q

↔ q

′

, i = 1,2,...,n, fornece uma equação

para os elementos desconhecidos da matriz F.

Assumindo a existência de uma solução não-zero para o Sistema 3.35, apesar de a

matriz A possuir 9 colunas, seu rank deve ser pelo menos igual a 8. De fato, exceto em

alguns casos, a matriz A terá rank exatamente igual a 8, e existirá uma solução única

para f. De forma a evitar a solução trivial f = 0, a restrição adicional f = 1 é aplicada.

Uma forma de assegurar esta restrição é forçar que um dos elementos de F seja igual a

1. Sendo assim, a matriz F possuirá 8 graus de liberdade e será deﬁnida por um fator de

escala desconhecido.

O objetivo é encontrar uma solução de mínimos quadrados para o Sistema 3.35. A

solução é o vetor f que minimiza Af sujeito à restrição f = f

f = 1 [Hartley 1997].

Tal solução pode ser encontrada com apenas 8 correspondências de pontos. Caso estejam

disponíveis mais de 8 correspondências, o Sistema 3.35 é dito sobredeterminado. Assim,

a solução pode ser dada como o autovetor associado ao menor autovalor de A

A. Desde

que A

A seja semi-deﬁnida positiva e simétrica, todos os seus autovetores são reais e

positivos, ou zero. O menor autovalor de A

A está associado à última coluna de V, que

3.5. GEOMETRIA EPIPOLAR

pode ser obtido utilizando a decomposição em valores singulares dada pela expressão

A = UDV

. (3.36)

A vantagem de utilizar o critério linear é que métodos desse tipo produzem uma solu-

ção analítica. Em contrapartida, tais métodos são sensíveis a ruído. Uma das razões reside

no fato de que a restrição de rank-2 da matriz fundamental estimada não é satisfeita. Esta

restrição deve ser assegurada visto que a singularidade é uma importante propriedade da

matriz fundamental.

Devido a imprecisões no processo de detecção de correspondências entre as duas ima-

gens, o rank da matriz A pode ser igual a 9. Como consequência disso, a solução para

o Sistema 3.35 seria uma matriz F não-singular. Como forma de assegurar a restrição de

rank-2 para a matriz F estimada, Tsai e Huang (1984) sugeriram encontrar uma matriz

singular F

′

que minimiza a norma de Frobenius dada por F−F

′

. A matriz singular

′

pode ser determinada através da decomposição em valores singulares de F = UDV

onde D é a matriz diagonal dos valores singulares representada por D = diag(r, s,t), com

r ≥ s ≥ t. A matriz F

′

corrigida é obtida tornando o último valor singular t = 0, como

′

= Udiag(r, s,0)V

. (3.37)

Algoritmo dos 8-Pontos Normalizado

Hartley (1997) sugere utilizar uma simples normalização nos dados utilizados no cál-

culo da matriz fundamental a partir do algoritmo original dos 8-pontos. A justiﬁcativa

apresentada por Hartley para a utilização do processo de normalização consiste em uma

forma de melhorar a condição do problema. O estudo comparativo apresentado em seu

trabalho sugere que o algoritmo dos 8-pontos normalizado apresenta resultados superio-

res ou idênticos aos melhores algoritmos iterativos, além de ser mais fácil de implementar

e possuir um tempo de execução cerca de 20 vezes menor.

A solução da equação Af= 0 é o menor autovetor da matriz A

A. A matriz A

A pode

ser expressada também pelo produto resultante da decomposição em valores singulares

UDV

, onde U e V são ortogonais e D é a matriz diagonal dos autovalores representada

como D = diag(d

,...,d

). Sendo assim, o menor autovetor de A

A é igual à última

coluna da matriz V.

O número de condição k = d

é um importante fator na análise de estabilidade

de problemas lineares. Se o valor de k é grande, pequenas mudanças nos dados (posi-

ções dos pontos correspondentes) podem causar mudanças signiﬁcativas na solução. A

CAPÍTULO 3. GEOMETRIA DE DUAS IMAGENS

principal razão para a matriz A

A ser mal-condicionada é a falta de homogeneidade nas

coordenadas dos pontos na imagem.

Como exemplo, em uma imagem de dimensões 200×200 pixels, um ponto qualquer

terá coordenadas do tipo



100 100 1



. Assim, as linhas da matriz A terão basicamente

a forma





e os elementos da matriz A

A serão valores entre 10

e 1.

A Propriedade de Entrelaçamento para os autovalores de uma matriz simétrica é uti-

lizada de forma a obter uma faixa de valores do número de condição da matriz [Golub e

Loan apud [Hartley 1997]]. Suponha que os elementos da diagonal da matriz A

A são

iguais a





A submatriz principal r ×r formada pelas últimas r colunas e r linhas é denotada por X

e λ

) é o seu i-ésimo maior autovalor. Assim, X

= A

A e seu número de condição

é igual a k = λ

)/λ

). Considerando os autovalores de X

, desde que a soma dos

autovalores λ

) + λ

) = 10

+ 1 e a matriz X é semi-deﬁnida positiva, pode-se

concluir que λ

) ≤10

+ 1.

Pela propriedade do entrelaçamento, os autovalores são ordenados como λ

) ≤

) ≤ ···λ

) ≤ 10

+ 1. Além disso, o maior autovalor de A

A não é menor

que o maior elemento da diagonal que é igual a 10

. Por isso, o número de condição é

k = λ

)/λ

) ≥ 10

/(10

+ 1). De fato, λ

) será muito menor que 10

+ 1, e o

número de condição será bem maior.

Como forma de solucionar este problema, os pontos correspondentes são transladados

nas duas imagens independentemente. Ao ﬁnal do processo de translação, os centróides

de cada conjunto de pontos devem estar localizados na origem do sistema de coordenadas

de cada uma das imagens. O esquema de normalização proposto é semelhante aoilustrado

na Seção 3.4.1.

A segunda parte do algoritmo dos 8-pontos original sugere que a solução para a matriz

fundamental seja a matriz singular F

′

mais próxima a F, utilizando a norma de Frobenius.

Este método trata todos os elementos da matriz fundamental F de maneira igual, não

observando suas magnitudes. Os elementos de pequeno valor absoluto da matriz F são

pertubados mais intensamente devido a sua magnitude que os elementos de alto valor.

Os elementos mais importantes da matriz fundamental são exatamente aqueles que estão

sujeitos à maior pertubação relativa quando a restrição de singularidade é assegurada sem

uma normalização inicial dos dados.

3.5. GEOMETRIA EPIPOLAR

Desde que os pontos correspondentes nas duas imagens são transformados indepen-

dentemente por uma translação e um escalonamento isotrópico, a matriz fundamental

computada descreve uma relação entre as coordenadas normalizadas pelo processo. Em

vista disso, a matriz

F deve ser convertida de maneira a descrever a relação entre as reais

coordenadas dos pontos correspondentes em cada imagem. Suponha que os pontos cor-

respondentes q

na primeira imagem e q

′

na segunda imagem foram substituídos após a

normalização por

= Tq

′

= T

′

, substituindo na Equação 3.33 obtém-se a relação

′T

′−T

−1

= 0. (3.38)

Assim, a relação entre as matrizes fundamentais

F e F é dada por

F = T

′−T

−1

, (3.39)

que pode ser reescrita como

F = T

′T

FT. (3.40)

Em resumo, o algoritmo dos 8-pontos normalizado pode ser descrito pelos seguintes

passos:

1. Aplicar uma transformação, composta por uma translação e um escalonamento,

às coordenadas dos pontos nas duas imagens separadamente, conforme T e T

′

= Tq

′

= T

′

;

2. Utilizar o algoritmo original dos 8-pontos para calcular a matriz fundamental

F a

partir dos pontos correspondentes

↔

′

;

3. Obter a matriz fundamental original F a partir da transformação inversa F= T

′T

FT.

Erro de Reprojeção para a Matriz Fundamental

Uma medida de erro de reprojeção pode ser utilizada com o objetivo de validar a

estimação de uma matriz fundamental. Seja l = F

′





a reta epipolar de

q, e l

′

= Fq =



′



a reta epipolar de q

′

. A distância entre um ponto q e sua

correspondente reta epipolar l é dada por

d(q,l) =



+ l

. (3.41)

O erro de reprojeção relacionado ao par de correspondências (q,q

′

) para a matriz

CAPÍTULO 3. GEOMETRIA DE DUAS IMAGENS

fundamental estimada pode ser formulado como



d(q,l)

+ d(q

′

)









+ l

′T

′



′2

+ l

′2

. (3.42)

Métodos Iterativos

A idéia natural por trás dos métodos iterativos consiste na minimização da distância

entre pontos e retas epipolares, dada por

min

∑

,Fq

′

) + d

′

)). (3.43)

Dado que l

′

= Fq



′



e l

= F

′





correspondem às retas

epipolares associadas à matriz fundamental F. Utilizando a distância entre o ponto q

′

e sua

correspondente reta epipolar l

′

= Fq

dada pela Equação 3.41, e o fato de que q

′T

′

, o critério a ser minimizado dado pela Equação 3.43 pode ser reescrito como

min

∑

′T

)

, (3.44)

onde



+ l

′2

+ l

′2



1/2

. (3.45)

O problema de minimização apresentado pela Equação 3.44 pode ser solucionado

por uma técnica linear de mínimos quadrados ponderada. Os pesos w

podem ser cal-

culados para cada par de pontos correspondentes e a correspondente equação linear do

Sistema 3.34 pode ser multiplicada por w

. Ao ﬁnal, o algoritmo dos 8-pontos original

pode ser utilizado para estimar a matriz fundamental que minimiza o critério dado pela

Equação 3.44.

O problema é que os pesos w

dependem da matriz fundamental. Para solucionar este

fato, um método linear iterativo é utilizado. Primeiro, assume-se todo w

= 1 e executa

o algoritmo dos 8-pontos para obter uma estimativa inicial da matriz fundamental. Os

pesos w

são então computados a partir desta solução inicial. A seguir, o esquema linear

de mínimos quadrados ponderados é executado de modo a melhorar a estimativa de F.

Este procedimento pode ser repetido diversas vezes.

A melhoria na estimação da matriz fundamental não é signiﬁcante comparada com

o método linear original. A principal razão é devido a restrição de rank-2 da matriz

3.5. GEOMETRIA EPIPOLAR

fundamental não ser levada em consideração. Como solução para este fato, Zhang (1998)

sugere uma minimização não-linear no espaço de parâmetros como forma de resolver

este problema. Este método consiste na parametrização da matriz fundamental, mantendo

em mente que ela possui rank igual a 2. Mais tarde, Zhang e Loop (2001) aperfeiçoaram

o método para a utilização de somente uma parametrização da matriz fundamental, dada

por

F =







a b −ax

−by

c d −cx

−dy

−ax

′

−cy

′

−bx

′

−dy

′

(ax

+ by

′

+ (cx

+ dy

′







(3.46)

onde (x

) e (x

′

) são as coordenadas dos epipólos na primeira e segunda imagem

respectivamente. A Equação 3.46 é somente uma das possibilidades de parametrização

que pode ser obtida. O procedimento iterativo deste método possibilita computar uma

melhor matriz fundamental baseada na restrição de rank-2.

A minimização da Equação 3.44 não é precisa suﬁciente para obter boa estimação.

Como forma de solucionar isto, métodos iterativos baseados no gradiente [Hartley e

Zisserman 2004] precisam ser considerados. Neste caso, a equação a ser resolvida é

do tipo

min

∑

′T

)

, (3.47)

onde g



+ l

′2

+ l

′2

Wu et al. (2005) apresentaram o algoritmo dos 8-pontos fatorizado. Seu algoritmo é

composto de três passos: (1) A matriz de correspondências m da Equação 3.34 do algo-

ritmo dos 8-pontos tradicional é decomposta em duas matrizes fatorizadas; (2) Algumas

variáveis auxiliares são inseridas e um novo problema de minimização é formulado atra-

vés da construção de uma nova matriz de medições de correspondências; (3) A matriz

fundamental é determinada solucionando este problema de minimização utilizando míni-

mos quadrados.

Métodos Robustos

Em diversas aplicações de visão computacional os dados necessários ao processo de

estimação da matriz fundamental muitas vezes estão corrompidos por ruídos no processo

de aquisição. Além disso, falsos pares de correspondência podem estar presentes. Fal-

sas correspondências podem interferir no processo de estimação e degenerar a solução

ﬁnal. Em tais circunstâncias, o desenvolvimento de estimadores robustos se torna essen-

CAPÍTULO 3. GEOMETRIA DE DUAS IMAGENS

cial. Métodos robustos conseguem recuperar a descrição signiﬁcativa dos dados mesmo

quando estes possuem elementos degenerativos (outliers) [Torr e Murray 1997].

O método Estimadores-M [Hartley e Zisserman 2004] sugere reduzir o efeito de falsas

correspondências através do uso de uma ponderação para o residual de cada par corres-

pondente. Diversas variantes do método são obtidas pelo uso de uma grande variedade de

funções de ponderação. Os resultados obtidos são bons na presença de falsas correspon-

dências mas são ruins em relação a pontos mal-localizados pelo detector.

As técnicas LMedS e RANSAC são bastante similares. As duas técnicas utilizam um

esquema de seleção aleatória de um conjunto de pontos a ser utilizado no cálculo da ma-

triz fundamental a partir de um método linear previamente escolhido. A diferença entre

as duas técnicas consiste na maneira em como elas determinam a melhor matriz estimada.

O método LMedS calcula a média das distâncias entre os pontos e as retas epipolares

para cada matriz fundamental. A matriz escolhida deve minimizar tal média. O método

RANSAC calcula o número de pontos correspondentes corretos para cada matriz funda-

mental estimada e escolhe uma matriz que maximiza o conjunto de pontos. Uma vez que

as falsas correspondências são eliminadas, a matriz fundamental é recalculada com o ob-

jetivo de obter uma melhor aproximação da estimativa. Outra diferença é que o método

LMedS é mais restritivo que o RANSAC de forma que ele elimina mais pontos. Entretanto,

a principal restrição de ambas as técnicas é a falta de repetitibilidade devido a forma ale-

atória de selecionar os pontos [Armangué e Salvi 2003]. Uma generalização do método

RANSAC é sugerida por Torr e Zisserman (2000), chamado de MLESAC. Enquanto que

o método RANSAC baseia-se principalmente no número de correspondências corretas, o

MLESAC é baseado em uma formulação de máxima verossimilhança da solução encon-

trada.

Lehmann et al. (2007) apresentaram uma nova técnica para o problema da estimação

da matriz fundamental. Ao invés de analisarem a geometria de pares de pontos correspon-

dentes entre duas imagens, o problema é tratado no domínio da frequência através do uso

de Projeção Integral, mostrando que este é um modelo razoável para câmeras ortográﬁ-

cas. Isto reduz o problema para a identiﬁcação de retas correspondentes no domínio da

frequência que não requer informação sobre correrspondência no domínio espacial. Yin e

Xie (2003) utilizam a geometria epipolar obtida a partir de imagens estéreo não-calibradas

para o reconhecimento de gestos de mãos. A matriz fundamental é estimada utilizando

uma combinação de técnicas tais como normalização dos pontos correspondentes, restri-

ção de rank-2, método linear e não-linear, bem como o método de Estimadores-M.

3.5. GEOMETRIA EPIPOLAR

3.5.3 Matriz Essencial

A matriz essencial [Longuet-Higgins 1981] é um caso particular da matriz fundamen-

tal para o caso em que os parâmetros intrínsecos da câmera são conhecidos. Historica-

mente, a matriz essencial foi introduzida antes da matriz fundamental. Assim, a matriz

fundamental pode ser vista como uma generalização da matriz essencial onde a calibração

das câmeras foi removida. A matriz essencial possui poucos graus de liberdade e algumas

propriedades adicionais comparadas com a matriz fundamental.

Considere a matriz da câmera P = K



R | t



, e um ponto na imagem q = PQ.

Caso a matriz de calibração K seja conhecida, a sua inversa pode ser aplicada ao ponto

q para a obtenção do ponto

q = K

−1

q. Assim,

q =



R | t



Q, onde

q é o ponto da

imagem escrito em coordenadas homogêneas normalizadas. A matriz de câmera

P =

−1

P =



R | t



é chamada de matriz normalizada da câmera, onde o efeito da matriz

de calibração foi removido.

Agora, considere um par de matrizes normalizadas de câmeras

P =



I | 0



′



R | t



. A matriz fundamental para o par de câmeras normalizadas é chamada de

matriz essencial e tem a forma

E = [t]

R. (3.48)

A equação que deﬁne a relação expressada pela matriz essencial para o par de pontos

correspondentes q ↔ q

′

, em coordenadas normalizadas, é dada por

′T

q = 0. (3.49)

Substituindo

q e

′

na Equação 3.49 obtém-se q

′−T

′T

−1

q = 0. Comparando com a

relação dada pela Equação 3.33, obtém-se a relação entre a matriz fundamental e a matriz

essencial dada por

E = K

′T

FK. (3.50)

Conforme a Equação 3.48, a matriz essencial possui somente 5 graus de liberdade: a

rotação R e a translação t possuem 3 graus de liberdade cada uma, mas existe um fator

de escala como na matriz fundamental, ou seja, a matriz essencial também é uma matriz

homogênea. O reduzido número de graus de liberdade se traduz em restrições extras que

são satisfeitas pela matriz essencial, comparada com a matriz fundamental. Tais restrições

determinam que a matriz essencial:

1. Codiﬁca somente os parâmetros extrínsecos da câmera;

2. Possui rank igual a 2, desde que R possui rank igual a 3 e t possui rank igual a 2;

CAPÍTULO 3. GEOMETRIA DE DUAS IMAGENS

3. Possui dois valores singulares diferentes de zero e iguais, e o terceiro igual a zero.

Extração das Matrizes de Câmeras a partir da Matriz Essencial

A matriz essencial E pode ser calculada diretamente a partir da Equação 3.49 uti-

lizando coordenadas homogêneas normalizadas, ou a partir da matriz fundamental uti-

lizando a Equação 3.50. Uma vez que a matriz essencial tenha sido calculada, quatro

possíveis soluções para as matrizes das câmeras podem ser recuperadas a partir de E,

com exceção do fator de escala que não pode ser determinado.

Sendo a matriz da primeira câmera deﬁnida por

P =



I | 0



, para o cálculo da

matriz da segunda câmera,

′

, é necessário escrever E como o produto entre uma matriz

anti-simétrica S e uma matriz de rotação R, deﬁnido por

E = SR. (3.51)

Na Equação 3.51, a matriz S representa o movimento de translação relativo entre as

duas câmeras, deﬁnido como

S =







0 −t

−t







, (3.52)

onde t

, t

e t

representam a translação nos eixos x, y e z respectivamente.

A decomposição em valores singulares da matriz essencial pode ser dada por E =

U diag(1,1,0)V

. Utilizando as matrizes

W =







0 −1 0

1 0 0

0 0 1







e Z =







0 1 0

−1 0 0

0 0 0







, (3.53)

existem, ignorando os sinais, duas possíveis fatorizações da Equação 3.51, deﬁnidas por

S = UZU

e R = UWV

ou UW

. (3.54)

A fatorização dada pela Equação 3.54 determina a translação t da matriz da câmera

′

, a menos de um fator de escala, a partir de S = [t]

. Entretanto, a norma de Frobenius

de S = UZU

é igual a

√

2. Isto signiﬁca que S = [t]

, incluindo o fator de escala. Então

t = 1 deﬁne uma normalização conveniente para a linha-base das duas matrizes das

3.6. CONSIDERAÇÕES FINAIS

câmeras.

Desde que St = 0, segue que t = U(0,0,1)

= u

, onde u

corresponde à última

coluna de U. Entretanto, o sinal de E, e consequentemente t, não pode ser determinado.

Então, a partir de uma dada matriz essencial, existem quatro possíveis escolhas para a

matriz de câmera

′

, baseado nas duas possíveis escolhas de R e nos dois possíveis sinais

de t, determinadas por

′



UWV

| +u



′



UWV

| −u



′



| +u



′



| −u



. (3.55)

Percebe-se claramente que a diferença entre as duas primeiras soluções dadas pelas

Equações 3.55 consiste somente em uma inversão da direção do vetor de translação. Essa

também é a diferença entre as soluções

′

. A diferença entre

′

é um pouco

mais complicada. Entretanto, veriﬁca-se que







UWV







, (3.56)

e VW

= V diag(−1,−1,1)V

consiste de uma rotação de 180

em torno da reta

que une os centros ópticos das duas câmeras. As duas soluções relacionadas desta maneira

são conhecidas como par rotacionado. As quatro soluções são ilustradas na Figura 3.5,

onde um ponto reconstruído Q estará em frente de ambas as câmeras em somente uma

das quatro opções.

Assim, testar com a reconstrução de um ponto é suﬁciente para decidir entre as quatro

diferentes soluções da matriz de câmera

′

. A reconstrução de um ponto 3D pode ser

feita segundo algum método de triangulação a partir de um par correspondente conhecido

entre as duas imagens, q→q

′

, e as quatro soluções dadas pelas Equações 3.55. A solução

correta é aquela em que o ponto triangulado encontra-se na frente das duas câmeras.

3.6 Considerações Finais

Neste capítulo foram apresentados alguns conceitos e notações relevantes ao que é

proposto nesta tese. Alguns métodos e algoritmos existentes na literatura foram relacio-

CAPÍTULO 3. GEOMETRIA DE DUAS IMAGENS

P’P

(a)

P’ P

(b)

P’P

(c)

P’ P

(d)

Figura 3.5: Entre as ﬁguras dos lados direito e esquerdo existe uma linha-base reversa.

Entre as ﬁguras de cima e de baixo, a câmera

′

está rotacionada 180

em torno da linha-

base. Perceba que apenas em (a) o ponto reconstruído está em frente das duas câmeras.

nados por terem sido objeto principal de estudo. O capítulo seguinte trata dos diversos

módulos envolvidos no sistema de segmentação proposto, e dos experimentos realizados.

Capítulo 4

Sistema Proposto

Planos são elementos visuais comuns e constituem uma excelente fonte de informação

presente em um ambiente. Tais elementos podem ser utilizados em tarefas que requerem

informação visual da cena [Okada et al. 2001, Pears et al. 2005, Dao et al. 2005, Ohnishi

e Imiya 2006]. Os planos também podem ser usados para reconstruir a forma 3D do

ambiente. Em um sistema de visão, um par de imagens capturadas por uma simples

câmera em movimento pode ser utilizada para extrair tais informações.

Seguindo esta linha de raciocínio, esta tese apresenta um sistema de segmentação de

planos no espaço tridimensional a partir de duas imagens de uma sequência capturada por

uma única câmera. O sistema desenvolvido nesta tese, os testes e os resultados obtidos

são descritos ao longo deste capítulo.

4.1 Diagrama de Blocos do Sistema Proposto

Esta tese apresenta um sistema que visa a obtenção da reconstrução métrica dos prin-

cipais planos presentes em uma cena. A Figura 4.1 ilustra o diagrama de blocos detalhado

de todo o sistema proposto.

O primeiro passo consiste em computar um conjunto de pares de pontos correspon-

dentes entre duas imagens de uma sequência capturada por um sistema de visão mono-

cular. A partir desse conjunto de correspondências, um método baseado em homogra-

ﬁas é utilizado com o objetivo de detectar e segmentar planos usando o modelo aﬁm.

Cada homograﬁa aﬁm representa uma superfície planar detectada na cena. Um algoritmo

foi desenvolvido para agrupar pontos pertencentes ao mesmo plano na imagem. Após

agrupados, cada plano é representado por um conjunto de pontos correspondentes e sua

homograﬁa associada.

A partir dos planos detectados, um procedimento de expansão é aplicado. A expansão

de cada plano é obtida a partir de um processo que observa a diferença entre o ﬂuxo planar

CAPÍTULO 4. SISTEMA PROPOSTO

Triangulação 3D

Detecção de Planos

de Interesse

Detecção de

Correspondências

Detecção de Pontos

Detecção de

Imagem 1

Imagem 2

Reconstrução 3D

de Interesse

Planos

Recuperação das

Matrizes de Câmera

Expansão de

PLANOS

Cálculo da

Matriz Essenc.

Cálculo da

Matriz Fund.

Estimação do

Fluxo Óptico

Cálculo do

Fluxo Planar

Planos

Expansão de Planos

Figura 4.1: Diagrama de blocos detalhado do sistema proposto.

e o ﬂuxo estimado de cada pixel da imagem. Um método de estimação do ﬂuxo óptico

baseado na informação de cor é proposto.

No passo seguinte, utilizando os pontos agrupados e seus correspondentes, a matriz

fundamental é estimada com o objetivo de extrair a geometria epipolar da cena. As-

sumindo que os parâmetros intrínsecos da câmera são conhecidos, a matriz essencial é

calculada. Assim, as matrizes de projeção da câmera são extraídas a partir da matriz

essencial. Ao ﬁnal do processo, os pontos pertencentes a cada superfície planar são tri-

angulados utilizando técnicas lineares para obter a representação tridimenssional da cena

no sistema de coordenadas do mundo, a menos de um fator de escala. As seções a seguir

detalham cada etapa envolvida no sistema proposto.

4.2 Detecção e Expansão dos Planos 2D

As fases de detecção e expansão dos planos são subdivididas nos seguintes módulos:

• estabelecimento de correspondência única entre pontos de interesse detectados nas

4.2. DETECÇÃO E EXPANSÃO DOS PLANOS 2D

duas imagens;

• detecção dos planos presentes na cena, baseada no cálculo de homograﬁas segundo

o modelo aﬁm;

• estimação do ﬂuxo óptico a partir da informação de cor presente nas imagens;

• expansão dos planos detectados a partir do ﬂuxo óptico estimado e das homograﬁas

calculadas.

Cada módulo é detalhado nas seções a seguir.

4.2.1 Detecção de Correspondências

A combinação do detector de Harris com o descritor SIFT é utilizada na etapa de

identiﬁcação de pares de pontos correspondentes entre as duas imagens. Utilizando o

detector de Harris, dois conjuntos de pontos de interesse C

e C

são obtidos para a

primeira e segunda imagem, respectivamente. Em seguida, o descritor SIFT é calculado

para cada ponto de interesse nos conjuntos C

e C

. Os pares de pontos correspondentes

entre as duas imagens são obtidos de acordo com um procedimento de busca regressiva e

ﬁltragem, baseada na correlação dos descritores calculados.

Primeiramente, uma medida de correlação baseada na distância Euclidiana entre dois

descritores SIFT é deﬁnida. Considere S



··· s



o vetor de n elementos

que representa o descritor SIFT do ponto j do conjunto C

. A distância Euclidiana entre

dois descritores de pontos representados pelos vetores S

e S

é dada por

SIFT

) =



−s

)

+ (s

−s

)

+ ···+ (s

−s

)

. (4.1)

Em seguida, para cada ponto em C

, um ponto correspondente é procurado em C

que

satisfaça a medida de correlação dada pela Equação 4.1. Com o objetivo de melhorar a

eﬁciência computacional, para cada ponto a busca é realizada somente em uma vizinhança

do ponto na segunda imagem, deﬁnida por uma janela de busca. O tamanho da janela de

busca depende do movimento relativo entre as imagens. Todos os pontos do conjunto C

que não possuirem um correspondente no conjunto C

são descartados, dando origem a

um novo conjunto C

′

com menos pontos. De forma semelhante, os pontos do conjunto

que não forem associados a algum ponto no conjunto C

também são descartados,

dando origem a um novo conjunto de pontos C

′

No próximo passo, um procedimento de ﬁltragem regressiva é aplicado de forma a

prevenir que dois ou mais pontos no conjunto C

′

tenham o mesmo correspondente na

segunda imagem. Para cada ponto em C

′

, somente o ponto melhor correlacionado em

CAPÍTULO 4. SISTEMA PROPOSTO

′

é mantido. Ao ﬁnal do procedimento de ﬁltragem, o conjunto M de pares de pontos

correspondentes entre as duas imagens é obtido.

O procedimento completo de busca por correspondências entre duas imagens é des-

crito no Algoritmo 4.1.

Algoritmo 4.1 Algoritmo de busca por pares de pontos correspondentes entre duas ima-

gens.

Dado:

e I

: duas imagens da mesma cena;

Deﬁnir:

M: conjunto vazio de correspondências;

W: janela de busca;

SIFT

: função de distância entre descritores SIFT;

ini

: limiar de correlação inicial para a medida d

SIFT

;

Executar o detector de Harris e obter C

e C

;

Computar o descritor SIFT S

de cada ponto em C

e C

;

for j = cada ponto de C

← T

ini

;

for w = cada ponto de C

em W do

if d

SIFT

) < T

then

Inserir correspondência j ↔ w em M;

Atualizar T

← d

SIFT

);

end if

end for

Descartar pontos de C

e C

sem correspondentes, e obter os conjuntos C

′

e C

′

;

Dado o conjunto de correspondências M

for w = cada ponto de C

′

Veriﬁcar correspondente j em C

′

com menor d

SIFT

associado;

Eliminar outras possíveis correspondências de w do conjunto M;

end for

Vetor de correspondências únicas M entre as duas imagens obtido;

4.2.2 Detecção dos Planos

O estágio de detecção de planos consiste basicamente em selecionar pares de pontos

no conjunto M de correspondências estabelecidas entre as duas imagens, para o cálculo

de uma homograﬁa que represente um plano da cena. A partir daí, dadas as homogra-

ﬁas calculadas, tentar agrupar pontos com homograﬁas semelhantes baseado no erro de

reprojeção [Aires, Araújo e Medeiros 2008b, Aires, Araújo e Medeiros 2008a].

4.2. DETECÇÃO E EXPANSÃO DOS PLANOS 2D

Para o cálculo de uma homograﬁa utilizando o modelo aﬁm são necessários, no mí-

nimo, três pares de pontos correspondentes. Como forma de facilitar a escolha de tais

pontos, uma triangulação de Delaunay [Preparata e Shamos 1985, Seo et al. 2004] é exe-

cutada somente nos pontos de interesse detectados na primeira imagem e pertencentes

ao conjunto de correspondências M. Desde que um conjunto T de triângulos tenha sido

obtido a partir desse procedimento de triangulação, um esquema de ﬁltragem é aplicado

com o objetivo de descartar triângulos que provavelmente pertençam a planos virtuais

na imagem. Somente triângulos com todas as arestas dentro de uma certa faixa de com-

primento são considerados válidos. Ainda, triângulos com arestas de tamanhos válidos

podem ter seus vértices praticamente colineares. A colinearidade dos três pontos utiliza-

dos no cálculo da homograﬁa aﬁm deve ser evitada para não degenerar a solução. Para

solucionar este problema, triângulos com áreas menores que um determinado valor tam-

bém são descartados, e obtém-se um novo conjunto de triângulos T

′

. O procedimento é

descrito no Algoritmo 4.2.

Algoritmo 4.2 Algoritmo de obtenção e ﬁltragem de triângulos.

Dado:

M: correspondências entre as duas imagens;

Deﬁnir:

min

e a

max

: limiares para tamanho aceitável das arestas dos triângulos;

min

: limiar para tamanho da área aceitável dos triângulos;

Obter o conjunto de triângulos T a partir da triangulação de Delaunay nos pontos de M

pertencentes à primeira imagem;

Criar um conjunto vazio de triângulos válidos, T

′

;

for j = cada triângulo de T do

Calcular as três arestas (a

) do triângulo j;

Calcular a área A

do triângulo j;

if (a

min

< a

max

) & (a

min

< a

max

) & (a

min

< a

max

) then

if A

< A

min

then

Inserir triângulo j no conjunto T

′

;

end if

end for

O conjunto T

′

de triângulos obtido a partir do esquema de ﬁltragem é usado em um

procedimento de votação que visa agrupar pontos pertencentes ao mesmo plano na ima-

gem. O esquema de agrupamento de pontos é baseado na homograﬁa aﬁm e no erro de

reprojeção. Tal procedimento consiste em selecionar um triângulo do conjunto T

′

e seus

Planos virtuais sãoformados por pontos coplanares mas que nãocorrespondem a uma mesma superfície

planar real existente na cena.

CAPÍTULO 4. SISTEMA PROPOSTO

pontos correspondentes em M, calcular a homograﬁa aﬁm H

, e a partir daí tentar agrupar

pontos correspondentes de M que estejam de acordo com a homograﬁa calculada, ou seja,

que pertençam ao mesmo plano deﬁnido por H

. O procedimento é repetido até que todos

os pontos de M estejam associados a algum plano. Testes preliminares detectaram que o

modelo é sensível à homograﬁa calculada inicialmente, portanto, sensível à escolha do

primeiro triângulo. Em vista disso, um procedimento inicial é adotado para melhorar a

detecção de planos proposta.

Considere o conjunto de correspondências M e o conjunto de triângulos T

′

. Para cada

triângulo de T

′

uma homograﬁa aﬁm é calculada a partir dos pontos desse triângulo e de

seus correspondentes deﬁnidos em M. A solução para o cálculo da homograﬁa aﬁm é

dada conforme a Equação 3.28 (pág. 63). Todas as homograﬁas calculadas formam um

conjunto H

. Para cada homograﬁa em H

, veriﬁca-se o número de correspondências

de M que pertencem ao plano deﬁnido por essa homograﬁa, de acordo com um limiar

baseado no erro de reprojeção calculado. Homograﬁas com um número elevado de cor-

respondências associadas (inliers) representam possíveis planos reais. Em contrapartida,

homograﬁas com um número reduzido de correspondências são possíveis representações

de planos virtuais, e os triângulos que representam tais homograﬁas são removidos do

conjunto T

′

. Os triângulos restantes do conjunto T

′

são ordenados de maneira decres-

cente conforme o número de correspondências associadas a suas homograﬁas, em um

novo conjunto de triângulos T

′′

. Esse procedimento consiste em mais uma boa forma de

eliminar possíveis planos virtuais, sendo descrito pelo Algoritmo 4.3.

O procedimento de detecção é inicializado com o triângulo usado no cálculo da ho-

mograﬁa pertencente a H

com a maior quantidade de correspondências de M associadas.

Dado o conjunto de correspondências M e o conjunto de triângulos T

′′

, deﬁne-se H

como o conjunto das m homograﬁas que representam o mapeamento de cada plano detec-

tado na cena. Inicialmente, H

é considerado vazio. O primeiro triângulo de T

′′

fornece

a primeira homograﬁa aﬁm H

, já calculada na etapa anterior. A homograﬁa H

ob-

tida é incluída em H

, e cada ponto utilizado em seu cálculo é marcado como visitado e

associado à homograﬁa H

(1), ou seja, o primeiro plano detectado.

No passo seguinte, o próximo triângulo de T

′′

é considerado. Todos os pontos do

triângulo e seus correspondentes dados por M são veriﬁcados se pertencentes a um plano

deﬁnido por alguma homograﬁa em H

. Para isso, se o ponto estiver marcado como

não-visitado e o erro de reprojeção para uma determinada H

(i) estiver abaixo de um

certo limiar deﬁnido, o ponto é marcado como visitado e associado à homograﬁa H

(i).

Caso o ponto tenha sido marcado como visitado e o novo erro de reprojeção seja menor

que o anterior, o ponto é associado ao plano deﬁnido por H

(i). Este procedimento é

4.2. DETECÇÃO E EXPANSÃO DOS PLANOS 2D

Algoritmo4.3Algoritmo para escolha da homograﬁa inicial do procedimento de detecção

de planos.

Dado:

M: correspondências entre as duas imagens;

′

: triângulos de Delaunay da primeira imagem;

: limiar do erro de reprojeção;

: limiar da quantidade de correspondências corretas;

Deﬁnir:

errR(w,H): função erro de reprojeção para a correspondência w em relação à ho-

mograﬁa aﬁm H;

numIn: quantidade de correspondências corretas associadas à homograﬁa calculada;

for j = cada triângulo de T

′

Calcular H

( j);

numIn = 0;

for w = cada correspondência de M do

if errR(w,H

( j)) < T

then

numIn = numIn+1;

end if

end for

if numIn < T

then

Descarta triângulo j de T

′

;

end if

end for

Obter T

′′

como um conjunto dos triângulos restantes de T

′

ordenados segundo a quan-

tidade de correspondências associadas a cada triângulo;

realizado para cada homograﬁa em H

. Cada vez que houver atualização no conjunto de

pontos associados a uma determinada homograﬁa, a mesma é atualizada. No caso onde

todos os pontos do triângulo não pertençam a nenhum plano existente em H

, uma nova

homograﬁa aﬁm H

é calculada com tais pontos. Assim, um novo plano é deﬁnido e a

nova homograﬁa é incluída em H

. O procedimento é repetido até que todos os triângulos

de T

′′

tenham sido visitados.

Em seguida, cada correspondência não-visitada no conjunto M é veriﬁcada se perten-

cente a algum planodeﬁnido no conjunto H

. Ao ﬁnal, cada plano é representado por uma

homograﬁa aﬁm em H

e planos com um pequeno número de pontos são descartados. O

método de detecção proposto é descrito no Algoritmo 4.4.

4.2.3 Expansão dos Planos

A detecção de planos fornece como resultado múltiplas regiões planares no espaço bi-

dimensional da imagem como forma de facilitar sua análise. Porém, os planos detectados

CAPÍTULO 4. SISTEMA PROPOSTO

Algoritmo 4.4 Algoritmo de detecção dos planos de uma cena.

Dado:

M: correspondências entre as duas imagens;

′′

: conjunto de t triângulos de Delaunay (homograﬁas associadas já calculadas no

Algoritmo 4.3);

: limiar do erro de reprojeção;

Deﬁnir:

errR(q,H): função erro de reprojeção para o ponto q e seu correspondente deﬁnido

em M, em relação à homograﬁa aﬁm H;

Criar um conjunto vazio de homograﬁas H

;

A partir de T

′′

(1) e M, obter a primeira H

e inserir em H

;

Associar os três pontos de T

′′

(1) a H

(1), e marcar cada um como visitado;

for j = 2 : t do

for i = cada homograﬁa de H

for cada ponto q de T

′′

( j) do

if q marcado como não-visitado then

if errR(q,H

(i)) < T

then

Associar q a H

(i);

q ← visitado;

end if

else if q ← visitado then

if errR(q,H

(i)) < errR(q,H

(i))

then

Atualizar q para H

(i);

end if

end for

Atualizar H

(i) com os pontos associados;

end for

if Todo q de T

′′

( j) estiver marcado como não-visitado then

Obter nova H

e inserir em H

;

Associar todo q a H

;

Marcar todo q como visitado;

end if

end for

Para cada ponto marcado como não-visitado, veriﬁcar se o mesmo pode ser associado

a alguma homograﬁa existente no conjunto H

Descartar pontos não associados a alguma das homograﬁas de H

são regiões pequenas em relação ao plano real. A partir do método de detecção proposto

na Seção 4.2.2, o ﬂuxo óptico estimado a partir da sequência de imagens é utilizado na

expansão de cada plano presente na cena.

Cada plano detectado na imagem é representado por uma homograﬁa aﬁm. Essa ho-

mograﬁa estabelece o movimento entre duas imagens sucessivas de um ponto pertencente

4.2. DETECÇÃO E EXPANSÃO DOS PLANOS 2D

a um mesmo plano. Tal movimento também é caracterizado pelo ﬂuxo óptico estimado

a partir de duas imagens consecutivas. A partir daí, a expansão dos planos pode ser feita

comparando os movimentos descritos pela homograﬁa de cada plano e o ﬂuxo óptico

estimado.

O primeiro passo consiste em estimar o ﬂuxo óptico v

= (v

) entre as duas ima-

gens consecutivas da cena. O método de estimação do ﬂuxo óptico utilizado é descrito na

Seção 2.2.5 (pág. 37). Em seguida, o ﬂuxo planar v

= (v

) é calculado em cada pi-

xel da imagem, para cada homograﬁa resultante do processo de detecção. O ﬂuxo planar

é o movimento deﬁnido pela homograﬁa que representa cada plano, sendo calculado por

= q

′

−q = H

q−q. (4.2)

O passo seguinte estabelece uma comparação entre o ﬂuxo estimado v

e o ﬂuxo

planar v

em cada pixel da imagem. Caso o erro entre v

e v

esteja abaixo de um certo

valor, o pixel pertence ao plano representado pela homograﬁa utilizada no cálculo do ﬂuxo

planar. O erro entre os dois ﬂuxos pode ser deﬁnido pela equação

err



−v

)

+ (v

−v

)

. (4.3)

O Algoritmo 4.5 descreve os passos envolvidos na fase de expansão de planos do

sistema proposto.

Algoritmo 4.5 Algoritmo para expansão dos planos detectados na cena.

Dado:

: conjunto de homograﬁas que representam cada plano detectado;

: limiar do erro entre o ﬂuxo estimado v

e o ﬂuxo planar v

;

Deﬁnir:

err

): erro entre ﬂuxo planar e ﬂuxo estimado;

Estimar o ﬂuxo óptico v

para todos os pixels da imagem;

for i = cada pixel da primeira imagem do

for j = cada homograﬁa de H

Calcular o ﬂuxo planar v

(i) = H

( j)q(i)−q(i);

if err

(i),v

(i)) < T

then

Associar pixel i como pertencente ao plano deﬁnido pela homograﬁa j;

Atualizar T

= err

(i),v

(i));

end if

end for

CAPÍTULO 4. SISTEMA PROPOSTO

4.2.4 Testes e Resultados

O estágio anterior ao sistema proposto consiste na aquisição de imagens a serem uti-

lizadas nos experimentos. Neste trabalho, diversas cenas de ambientes internos e exter-

nos foram utilizadas nos testes. Para cada uma das cenas, as imagens foram captura-

das de forma sequencial por uma única câmera. Além disso, nenhum estágio de pré-

processamento foi aplicado nas imagens capturadas. As imagens internas foram adqui-

ridas por uma webcam Logitech



modelo QC5000, e as imagens externas foram adqui-

ridas por uma câmera Sony



modelo H50. Cada uma dessas imagens possui o tamanho

de 320×240 pixels para as cenas internas e 640×480 pixels para as cenas externas. A

Figura 4.2 ilustra algumas das imagens utilizadas nos experimentos.

Esta tese não trata especiﬁcamente do problema de determinação dos parâmetros in-

trínsecos da câmera através da calibração. Assim, é suposto que a câmera tenha sido

calibrada antes da inicialização do sistema. Para isso, o método de calibração de Zhang

(2002) foi utilizado. Testes foram executados em diferentes sequências de imagens inter-

nas e externas. Os resultados são apresentados para cada etapa do sistema completo com

o objetivo de validar o método proposto.

Detecção de planos

O primeiro passo consiste em detectar pontos de interesse nas duas imagens da sequên-

cia. O método de Harris foi utilizado com as derivadas espaciais sendo calculadas com a

máscara de Sobel [Gonzalez e Woods 2007], e a derivada temporal utilizando o método

das diferenças ﬁnitas [Horn e Schunck 1981]. A janela gaussiana de ponderação (Equa-

ção 2.5) possui tamanho 9×9 pixels e variância σ = 1, 5. Além disso, a constante de

Harris foi ajustada como k = 0, 04 (Equação 2.6, pág. 18).

Um ponto de interesse é encontrado se o valor da resposta do detector, C

, for maior

que um valor pré-deﬁnido de forma empírica, T

= 0,1. Por ﬁm, um esquema de su-

pressão não-máxima é aplicado na vizinhança de um ponto detectado com o objetivo de

descartar pontos de interesse com baixa resposta do detector. Para isso, uma região de

vizinhança de tamanho 15×15 pixels é utilizada, para o caso das imagens internas. No

caso das imagens externas, a região de vizinhança possui tamanho 25×25 pixels.

Seguindo a fase de detecção de pontos de interesse, o descritor SIFT é utilizado para

estabelecer a correspondência única entre pares de pontos nas duas imagens. Para cada

ponto detectado, o descritor é montado a partir de uma região de 16×16 pixels, dividida

em 16 sub-regiões de 4×4 pixels. Cada sub-região é descrita por um histograma de 8

intervalos de orientação. Assim, o descritor formado possui dimensão igual a 128 (16×8).

4.2. DETECÇÃO E EXPANSÃO DOS PLANOS 2D

(a) Int 01 (b) Int 02

(e) Ext 02

Figura 4.2: Exemplos de imagens utilizadas nos experimentos.

Sendo assim, o esquema descrito no Algoritmo 4.1 é empregado para obter um con-

junto de pares de pontos correspondentes. Como o movimento entre as imagens é conhe-

cido ser pequeno, a busca por pontos correspondentes é feita somente em uma região de

vizinhança de 5×5 pixels. O valor do limiar inicial da distância entre os descritores é

determinado como sendo T

ini

= 2.

CAPÍTULO 4. SISTEMA PROPOSTO

A Tabela 4.1 apresenta a quantidade de pontos de interesse detectados em cada ima-

gem da Figura 4.2, bem como os dados referentes aos pares de pontos correspondentes

encontrados entre as duas imagens consecutivas da sequência. Pode-se perceber a alta

taxa de pares de pontos correspondentes encontrados, enquanto o número de correspon-

dências falso-positivas mantém-se baixo.

Tabela 4.1: Dados referentes ao processo de detecção de pontos de interesse, e busca por

pares de pontos correspondentes entre as duas imagens. Pontos de interesse detectados

no primeiro e segundo quadros da sequência (Q1 e Q2), quantidade de pares de pontos

correspondentes e número de correspondências falso-positivas.

PdI Q1 PdI Q2 Corresp. Falso-Posit.

Int 01 86 85 66 6

Int 02 73 79 64 4

Int 03 181 177 129 5

Ext 01 199 200 115 2

Ext 02 210 200 146 4

Seguindo o Algoritmo 4.2, dado o conjunto de pares de pontos correspondentes, o es-

quema de triangulação de Delaunay é executado e triângulos que possam vir a representar

possíveis planos virtuais são descartados. Somente são aceitos como válidos triângulos

com arestas de tamanho entre 10 e 90 pixels, e com área maior que 90 pixels

. A Fi-

gura 4.3 ilustra os triângulos obtidos a partir da triangulação de Delaunay, antes e após

o processo de ﬁltragem. Claramente, observa-se que a grande maioria dos triângulos

eliminados no processo corespondem a planos virtuais presentes na cena.

(a) (b)

Figura 4.3: (a) Resultado da triangulação de Delaunay a partir do conjunto de pontos de

interesse detectados na Primeira imagem. (b) Conjunto de triângulos resultante após o

procedimento de ﬁltragem.

4.2. DETECÇÃO E EXPANSÃO DOS PLANOS 2D

A escolha da homograﬁa inicial (Algoritmo 4.3) para o procedimento de detecção

de planos é feita utilizando o valor de limiar T

= 2 para o erro de reprojeção. Para

o processo de agrupamento de pontos em planos, somente são utilizados os triângulos

cujas homograﬁas relacionadas possuam um número de pares de pontos correspondentes

associados maior ou igual a T

= 5. Em seguida, os pontos foram agrupados de acordo

com o Algoritmo 4.4 utilizando um limiar inicial para o erro de reprojeção da homograﬁa

igual a T

= 2. Ao ﬁnal desta etapa, somente planos deﬁnidos por grupos com 4 ou mais

pontos são considerados. A Tabela 4.2 apresenta os resultados numéricos do experimento,

enquanto a Figura 4.4 (pág. 92) ilustra os planos detectados após o processo.

Tabela 4.2: Dados referentes ao processo de detecção de planos baseada no cálculo da ho-

mograﬁa: quantidade de pontos detectados em cada plano, número de pontos descartados

e número de pontos classiﬁcados de forma errônea.

Plano 1 Plano 2 Plano 3 Descartados Errôneos

Int 01 16 19 - 31 02

Int 02 27 14 14 09 08

Int 03 86 25 12 06 45

Ext 01 25 14 38 38 03

Ext 02 35 35 - 76 02

Os resultados apresentados na Figura 4.4 e na Tabela 4.2 mostram que o método de

detecção de planos apresentado funciona bem para as imagens utilizadas. Considerando

o número de pares de pontos correspondentes apresentado na Tabela 4.1, a taxa de clas-

siﬁcação obtida é aceitável. Além disso, somente para o caso da imagem da Figura 4.4c

ocorreu uma elevada taxa de pontos erroneamente classiﬁcados, o que pode ser justiﬁcado

pela complexidade existente no fundo da imagem.

Expansão de planos

O passo seguinte consiste no processo de expansão dos planos detectados. O método

descrito na Seção 2.2.5 (pág. 37) foi utilizado na estimação dos vetores de ﬂuxo óptico

da imagem. De acordo com o método utilizado, cada quadro da sequência de imagens

foi subdividido em regiões de movimento constante de tamanho 5×5 pixels. Para cada

região, somente 9 pixels igualmente distribuídos no espaço foram utilizados na estimação

dos vetores de ﬂuxo óptico.

O ﬂuxo óptico estimado é comparado com o ﬂuxo planar (Equação 4.2) calculado a

partir da homograﬁa que representa cada plano detectado. Caso o erro err

(Equação 4.3)

seja menor que 0, 5, o ponto é considerado pertencente ao plano dado pela homograﬁa

CAPÍTULO 4. SISTEMA PROPOSTO

(a) (b)

(e)

Figura 4.4: Resultado do procedimento de detecção de planos para as imagens da Fi-

gura 4.2.

utilizada para o cálculo do ﬂuxo planar. Ao ﬁnal do processo, cada plano é formado por

um conjunto de pontos correspondentes.

Uma medida de erro foi utilizada com o objetivo de medir a precisão da detecção e

expansão dos planos. Primeiramente, os principais planos presentes na imagem foram

4.2. DETECÇÃO E EXPANSÃO DOS PLANOS 2D

detectados manualmente. Em seguida, os planos detectados manualmente e detectados

pelo sistema proposto foram comparados e o erro dado por

err

= 100

∑

x,y

(x,y) −D

(x,y)|

∑

x,y

(4.4)

onde D

(x,y) e D

(x,y) correspondem a 1 ou 0 conforme o ponto (x, y) pertença ou não

ao plano detectado manualmente (D

) ou ao plano detectado pelo sistema (D

A Figura 4.5 ilustra os principais planos expandidos em cada cena. A Tabela 4.3

apresenta o erro obtido no processo de expansão, bem como a quantidade de pontos erro-

neamente classiﬁcados. Os dados mostram que todos os erros calculados estão abaixo de

20%.

Figura 4.5: Resultado do procedimento de expansão de planos.

Caso o movimento entre as duas imagens sucessivas seja grande, o cálculo do ﬂuxo

óptico é comprometido. Em virtude disso, na cena dada pela Figura 4.2d (pág. 89) ne-

nhum dos planos detectados foi expandido.

O experimento foi realizado também com sequências de imagens obtidas assumindo

o movimento da câmera constante. Os resultados apresentados nas Tabelas 4.4 e 4.5

CAPÍTULO 4. SISTEMA PROPOSTO

Tabela 4.3: Erro (%), medidas falso-positivas FP (%) e falso-negativas FN (%) obtidas no

processo de expansão de planos para as imagens da Figura 4.5.

Obstáculos Chão

Erro FP FN Erro FP FN Erro FP FN

Int 01 5,18 1,33 3,85 - - - 11,55 2,13 9,42

Int 02 2,43 1,23 1,20 5,96 0,32 5,64 9,77 4,66 5,11

Int 03 17,50 15,76 1,74 5,49 3,73 1,76 11,33 0,60 10,73

Ext 01 17,14 5,91 11,23 - - - 11,92 3,19 8,73

Tabela 4.4: Erro (%), medidas falso-positivas FP (%) e falso-negativas FN (%) obtidas no

processo de expansão de planos para as imagens da Figura 4.6.

Obstáculo Chão

Erro FP FN Erro FP FN

Quadro 01 2,07 1,28 0,79 8,55 0,63 7,92

Quadro 09 2,19 0,77 1,42 13,40 4,75 8,65

Quadro 16 2,39 1,22 1,17 8,24 0,51 7,73

Quadro 23 3,06 1,79 1,27 10,40 0,72 9,68

Tabela 4.5: Erro (%), medidas falso-positivas FP (%) e falso-negativas FN (%) obtidas no

processo de expansão de planos para as imagens da Figura 4.7.

Obst. Direito Obst. Esquerdo Chão

Erro FP FN Erro FP FN Erro FP FN

Quadro 01 2,26 1,17 1,08 3,05 1,91 1,14 9,19 0,67 8,52

Quadro 11 2,21 0,58 1,63 2,54 0,85 1,69 11,46 0,48 10,98

Quadro 21 2,88 1,52 1,36 2,27 0,71 1,56 10,54 2,18 8,36

Quadro 31 5,06 3,88 1,18 4,19 0,89 3,30 18,02 1,33 16,69

apresentam uma baixa taxa de erro relacionada ao processo de classiﬁcação de pontos

como pertencentes a um dos planos detectados.

Finalmente, as Figuras 4.6 e 4.7 mostram, para as duas sequências de imagens utili-

zadas, que o procedimento de expansão dos principais planos presentes nas cenas produz

resultados aceitáveis.

4.2. DETECÇÃO E EXPANSÃO DOS PLANOS 2D

Figura 4.6: Resultado do processo de detecção e expansão de planos para os quadros 1,

9, 16 e 23 de uma sequência.

Figura 4.7: Resultado do processo de detecção e expansão de planos para os quadros 1,

11, 21 e 31 de uma sequência.

CAPÍTULO 4. SISTEMA PROPOSTO

4.3 Reconstrução Métrica dos Planos Identiﬁcados

Nesta seção é tratado o problema de reconstrução 3D dos planos detectados na ima-

gem. A matriz fundamental é calculada a partir de um esquema iterativo que utiliza o

algoritmo dos 8-pontos normalizado. Supondo que os parâmetros intrínsecos da câmera

são conhecidos, o próximo passo consiste em obter a matriz essencial. Em seguida, os

parâmetros de movimento relativo entre as câmeras são computados a partir da matriz

essencial. Ao ﬁnal, as matrizes da câmera no momento da aquisição de cada imagem

são recuperadas, e as coordenadas dos pontos 3D são determinadas por triangulação. A

reconstrução obtida é deﬁnida por um fator de escala. O procedimento é detalhado a

seguir.

4.3.1 Extração da Geometria Epipolar

O algoritmo dos 8-pontos normalizado (Seção 3.5.2, pág. 69) é utilizado para estimar

a matriz fundamental. Apesar de o termo “8-pontos” ser aplicado, um número maior de

pares de pontos correspondentes é usado no procedimento de estimação. Neste caso, um

problema linear de mínimos quadrados deve ser resolvido. Como forma de melhorar a

qualidade da estimativa da matriz fundamental, um esquema iterativo simples é combi-

nado ao algoritmo dos 8-pontos normalizado. A solução para a matriz fundamental é

deﬁnida por um fator de escala e sua singularidade é assegurada ao ﬁnal de todo o pro-

cesso.

Um esquema iterativo aplicado à estimação da matriz fundamental a partir do algo-

ritmo dos 8-pontos normalizado é utilizado. Basicamente, a idéia do método consiste

na atualização de F a partir do erro de reprojeção calculado para cada correspondência

utilizada na estimação. Inicialmente, um conjunto de correspondências é deﬁnida para a

estimação de F pelo algoritmo dos 8-pontos normalizado. Conhecida a primeira solução

, o erro de reprojeção e

dado pela Equação 3.42 é calculado para cada par correspon-

dente utilizado no processo de estimação de F

. Os pares de pontos correspondentes com

um erro acima de um certo limiar T

são descartados. Uma nova matriz fundamental F

estimada e o processo é repetido até que uma condição de parada seja satisfeita. A con-

dição de parada é relacionada à mediana do erro de reprojeção e ao número de iterações

executadas no procedimento.

Ao ﬁnal do processo iterativo de estimação, a singularidade da matriz fundamental

deve ser assegurada. Para isso, é calculada a decomposição em valores singulares de

F = UDV

′

T, onde D = diag(r,s,t), e r ≥ s ≥ t sendo os valores singulares. A solução

4.3. RECONSTRUÇÃO MÉTRICA DOS PLANOS IDENTIFICADOS

ﬁnal é a matriz

F que minimiza a norma de Frobenius F−

F, dada por

F = U diag(λ,λ,0)V

′

T, (4.5)

onde λ = (r+ s)/2.

4.3.2 Recuperação dos Parâmetros de Movimento

Os parâmetros de movimento são representados pelas matrizes da câmera no momento

da aquisição de cada imagem. Dado que o sistema de coordenadasde referência do mundo

é posicionado na câmera no momento da aquisição da primeira imagem da cena, a matriz

da câmera relacionada à primeira imagem é deﬁnida como

P = K



I | 0



. (4.6)

De tal forma, a matriz da câmera relacionada com a segunda imagem é deﬁnida por

′

= K



R | t



, sendo o movimento caracterizado pela rotação R e pela translação t

efetuadas pela câmera entre os instantes de cada aquisição.

O problema de encontrar os parâmetros de movimento da câmera torna-se simples

quando a matriz de calibração interna é conhecida. Neste trabalho é suposto que a ma-

triz de calibração K da câmera é obtida por um processo efetuado antes do sistema ser

iniciado.

Assim, a matriz essencialEpode ser facilmenteobtida a partir de F pela Equação 3.50.

No caso de um sistema monocular, K

′

= K, portanto

E = K

FK. (4.7)

Uma vez que a matriz essencial tenha sido obtida, os parâmetros de movimento R

e t podem ser extraídos. O procedimento de fatorização da matriz E, descrito na Se-

ção 3.5.3 (pág. 76), é empregado e produz como resultado quatro possíveis soluções

(Equações 3.55, pág. 77) para a matriz da câmera relacionada com a segunda imagem.

4.3.3 Restrição de Posicionamento e Reconstrução 3D

De acordo com a restrição de posicionamento, qualquer ponto na cena deve estar na

frente da câmera no momento da aquisição de ambas as imagens [Hartley 1993]. Este

fato deve ser observado de modo a determinar qual das quatro possíveis soluções para a

matriz da segunda câmera P

′

é a verdadeira. Um ponto é suﬁciente para solucionar esta

CAPÍTULO 4. SISTEMA PROPOSTO

ambiguidade. O ponto deve ser triangulado usando o par de matrizes de câmera

P e

′

onde

′

corresponde a cada uma das quatro soluções dadas pelas Equações 3.55.

O método de triangulação linear é o mais comumente usado [Hartley e Sturm 1994].

De acordo com a Equação 3.3, wq e w

′

são as projeções do ponto Q nas duas imagens.

Sendo p

a i-ésima linha da matriz de projeção P da câmera, as seguintes equações podem

ser obtidas

wx = p

wy = p

w = p

(4.8)

A partir das Equações 4.8, a terceira equação pode ser substituída nas duas primeiras,

obtendo-se

Q = p

(4.9)

Desse modo, a partir de duas imagens de uma mesma cena, um conjunto de quatro

equações lineares nas coordenadas do ponto Q é obtido. Este sistema linear de equações

pode ser escrito na forma matricial como

AQ = 0 (4.10)

onde A é uma matriz 4×4 deﬁnida como

A =







−p

′

′T

−p

′T

′

′T

−p

′T







. (4.11)

O Sistema 4.10 pode ser solucionado por um método linear que consiste em mini-

mizar AQ, sujeito à condição Q= 1. A solução pode ser obtida por decomposição

em valores singulares, e é dada pelo autovetor unitário associado ao menor autovalor da

matriz A

A precisão da estimativa pode ser melhorada caso as Equações 4.9 sejam ponderadas

e a solução encontrada de forma iterativa. Basicamente, a idéia do método linear iterativo

é alterar os pesos adaptativamente de maneira que as equações ponderadas correspondam

aos erros nas medições das coordenadas da imagem.

4.3. RECONSTRUÇÃO MÉTRICA DOS PLANOS IDENTIFICADOS

O esquema consiste em minimizar a diferença entre o valor medido da coordenada q

e a projeção de Q dada por p

Q/p

Q. Considerando a equação xp

Q = p

Q, haverá

um erro a ser considerado, dado por

ε = xp

Q−p

Q. (4.12)

Assim, o objetivo é minimizar

′

= x−

. (4.13)

Caso o fator 1/p

Q seja usado para ponderar a primeira das Equações 4.9, o erro

dado pela Equação 4.13 será realmente aquele a ser minimizado. O mesmo fator é usado

na segunda das Equações 4.9. Para a segunda imagem, o fator de ponderação correto é

1/p

′T

Q. Visto que os pesos dependem de Q, seu valor é desconhecido até as equações

terem sido solucionadas. Desse modo, o procedimento é inicializado com os dois pesos

iguais a 1, e o Sistema 4.11 é resolvido para encontrar Q

. A partir daí, novos pesos são

calculados e utilizados na obtenção de um novo valor para Q.

Somente uma das quatro possíveis soluções de P

′

(Equações 3.55, pág. 77) faz com

que o ponto triangulado Q esteja na frente da câmera no momento da aquisição das duas

imagens. Primeiramente, as matrizes da câmera devem ser normalizadas de maneira a

determinar qual matriz de rotação (R

ou R

) possui determinante maior que 0. Considere

as coordenadas homogêneas q e q

′

as projeções na imagem do ponto Q. Então, Q estará

na frente da câmera somente se

> 0 e q

′

> 0, (4.14)

onde o termo subscrito deﬁne o elemento do vetor de coordenadas em questão.

Em vista disso, um ponto é suﬁciente para determinar a solução correta de P

′

. De-

vido a presença de outliers, a restrição de posicionamento é aplicada a um conjunto de

correspondências. O conjunto de correspondências escolhido é o mesmo utilizado na es-

timação de F. Então, usando as quatro possíveis matrizes para P

′

, cada correspondência

é triangulada para determinar a conﬁguração de matrizes de câmera P e P

′

. A partir da

Equação 4.14, o par de matrizes (P,P

′

) válido para o sistema de visão monocular é repre-

sentado pela conﬁguração predominante nos resultados do procedimento de triangulação.

Ao ﬁnal, utilizando a conﬁguração válida, todos os pontos são triangulados para obter o

a reconstrução métrica dos planos, determinados por um fator de escala.

100

CAPÍTULO 4. SISTEMA PROPOSTO

4.3.4 Testes e Resultados

A matriz fundamental F poderia ser estimada a partir de todos os pares de pontos cor-

respondentes encontrados (Seção 4.2.1, pág. 81). Isto não foi adotado devido à presença

de falsas correspondências. Testes foram feitos para estimar a matriz fundamental a partir

de todas as correspondências mas os resultados não são aceitáveis devido à presença de

mínimos locais no processo iterativo de minimização do erro. Dessa maneira, o estágio

prévio de eliminação de triângulos e planos que possam representar planos virtuais é uma

importante etapa para remover falsas correspondências dos dados usados na estimativa de

F, consequentemente aumentando a robustez do processo.

Para o cálculo da matriz fundamental, somente os pontos pertencentes aos planos de-

tectados são utilizados. Em todos os casos, o procedimento de cálculo é efetuado somente

com três iterações. A Figura 4.8 ilustra o erro mediano obtido em cada iteração do proce-

dimento.

(a) Imagens da Figura 4.2

(b) Sequência da Figura 4.6 (c) Sequência da Figura 4.7

Figura 4.8: Gráﬁco do erro mediano obtido no processo iterativo de estimação da matriz

fundamental.

4.4. CONSIDERAÇÕES FINAIS

101

Após o cálculo da matriz fundamental, a matriz essencial é obtida a partir da Equa-

ção 3.50. Em seguida, as matrizes de câmera são obtidas e os pontos pertencentes aos

planos detectados são triangulados para a obtenção do modelo 3D da cena, deﬁnido

por um fator de escala. Para todos os casos, apenas duas iterações foram suﬁcientes

para o procedimento de triangulação convergir. As Figuras 4.9, 4.10 e 4.11, nas pági-

nas 102, 103 e 104, ilustram as posições 3D estimadas, deﬁnidas por um fator de escala,

dos pontos correspondentes para algumas cenas utilizadas nos experimentos.

4.4 Considerações Finais

O sistema proposto segmenta planos no espaço a partir da informação de homogra-

ﬁas, ﬂuxo óptico e reconstrução métrica. A determinação dos parâmetros envolvidos nos

diversos módulos do sistema foi feita de forma empírica. Um importante ponto a desta-

car é que tais parâmetros foram mantidos constantes para todas as imagens em todos os

experimentos.

Os resultados apresentados na Tabela 4.1 (pág. 90) caracterizam a robustez do sis-

tema à presença de falsas-correspondências. O estágio de ﬁltragem dos triângulos obtidos

pelo procedimento de triangulação de Delaunay constitui um importante passo para a eli-

minação de planos virtuais preliminar ao estágio de detecção de planos. Testes foram

realizados sem a etapa de ﬁltragem citada e os resultados sugeriram a presença de planos

virtuais na cena. Esta etapa de ﬁltragem combinada com a etapa de escolha da homo-

graﬁa inicial para o processo de agrupamento de pontos pertencentes ao mesmo plano,

contribuem de forma decisiva para a eliminação de planos virtuais que poderiam vir a ser

detectados.

A Figura 4.4 (pág. 92) e a Tabela 4.2 (pág. 91) ilustram a robustez do sistema quanto à

detecção de planos virtuais. O único caso onde o sistema detectou um plano virtual como

um plano da cena foi no caso da Figura 4.2d (pág. 89). Além disso, em todos os casos as

falsas-correspondêcias foram descartadas ou não classiﬁcadas como pertencentes a algum

dos planos detectados. Isto serve para comprovar que os diversos estágios de ﬁltragem

empregados durante o processo são de grande valia para o sistema proposto.

Os resultados obtidos na fase de expansão de planos baseada na comparação do ﬂuxo

estimado com o ﬂuxo planar foram satisfatórios. Em todos os casos, com exceção da

cena ilustrada na Figura 4.2e, os planos foram corretamente expandidos. O problema da

Figura 4.2e ilustra uma deﬁciência do sistema. Quando o movimento entre as imagens

é grande o algoritmo de estimação do ﬂuxo óptico não consegue detectar o movimento

presente na cena. Como consequência, a expansão dos planos ﬁca comprometida. Ape-

102

CAPÍTULO 4. SISTEMA PROPOSTO

(a) Int 01

(b) Int 02

Figura 4.9: Posição 3D estimada, deﬁnida por um fator de escala, dos pontos correspon-

dentes para as imagens de cenas internas ilustradas nas Figuras 4.2a e 4.2b. O ponto

vermelho ilustra a posição da câmera no momento da aquisição do primeiro quadro.

4.4. CONSIDERAÇÕES FINAIS

103

(a) Ext 01

(b) Ext 02

Figura 4.10: Posição 3D estimada, deﬁnida por um fator de escala, dos pontos corres-

pondentes para as imagens de cenas externas ilustradas nas Figuras 4.2d e 4.2e. O ponto

vermelho ilustra a posição da câmera no momento da aquisição do primeiro quadro.

104

CAPÍTULO 4. SISTEMA PROPOSTO

(a) Seq 01

(b) Seq 02

Figura 4.11: Posição 3D estimada, deﬁnida por um fator de escala, dos pontos correspon-

dentes para o primeiro quadro das sequências ilustradas nas Figuras 4.6 e 4.7. O ponto

vermelho ilustra a posição da câmera no momento da aquisição do primeiro quadro.

4.4. CONSIDERAÇÕES FINAIS

105

sar disso, os pontos dos planos detectados podem ser utilizados no processo de extração

da geometria epipolar, recuperação das matrizes da câmera e reconstrução métrica dos

planos, como pode ser conﬁrmado no resultado apresentado na Figura 4.10b (pág. 103).

A grande diﬁculdade encontrada residiu principalmente na aquisição das imagens. Os

resultados fornecidos pelo sistema são fortemente dependentes do processo de aquisição.

Além disso, a análise dos resultados obtidos em cada etapa possibilitou observar que a

fase de estabelecimento de correspondências é uma das mais cruciais do sistema. Isto

porque a presença de falsas correspondências interfere no resultado ao longo de todo o

processo, tanto na estimação das homograﬁas na fase de detecção de planos, quanto na

estimação da matriz fundamental na fase de recuperação das matrizes da câmera.

Na fasededetecção de planos, determinar de forma precisa a quantidade aceitável para

que um grupo de pontos represente um plano é um desaﬁo. A métrica utilizada no sistema

é baseada somente em um limiar pré-estabelecido, onde geralmente são selecionados os

maiores grupos de pontos.

De maneira geral, os resultados mostram o bom funcionamento do sistema. Em vista

das diﬁculdades encontradas, os resultados apresentados são bastante promissores apesar

do conjunto de imagens de testes ser restrito.

106

CAPÍTULO 4. SISTEMA PROPOSTO

Capítulo 5

Conclusões e Trabalhos Futuros

Nesta tese, foi apresentado um sistema capaz de segmentar os principais planos pre-

sentes em uma cena. O sistema desenvolvido é baseado na utilização de homograﬁas,

ﬂuxo óptico e reconstrução métrica para segmentar os planos no espaço. Testes foram

conduzidos com sequências de imagens capturadas em ambientes internos e externos, e

resultados foram apresentados. Uma importante característica do sistema reside no fato

de o mesmo fazer uso de técnicas simples na solução de um problema real.

Em vista do que foi apresentado, a principal contribuição deste trabalho consiste na

integração de técnicas em um sistema cujo objetivo é solucionar o problema da segmen-

tação de planos no espaço 3D. A combinação de um conjunto de técnicas clássicas e com

bom desempenho já provado contribuiu para o desenvolvimento de um sistema robusto

para a segmentação de planos. No sistema proposto, eventuais erros em um dos módu-

los são corrigidos ou descartados pelos demais módulos. Além disso, ressalta-se o fato

de que a segmentação é feita a partir de duas imagens adquiridas por um sistema de vi-

são monocular, onde a distância percorrida pela câmera no intervalo de duas aquisições

consecutivas é desconhecida. Caso os dados de odometria referente ao movimento da câ-

mera estejam disponíveis, torna-se possível a recuperação do fator de escala relacionado

à determinação da posição 3D dos planos.

Em adição, contribuições mais especíﬁcas podem ser citadas:

• Desenvolvimento de um método de detecção dos principais planos presentes em

uma cena. Este método integra um procedimento de busca por pares de pontos

correspondentes entre duas imagens sucessivas, baseado no detector de Harris e no

descritor SIFT, e um procedimento de agrupamento de pontos baseado em triangu-

lação de Delaunay e homograﬁa aﬁm;

• Desenvolvimento de um método de estimação de ﬂuxo óptico baseado na informa-

ção de cor presente nas imagens. Este método constitui uma modiﬁcação de um

algoritmo clássico utilizando os três canais de informação da imagem no modelo

108

CAPÍTULO 5. CONCLUSÕES E TRABALHOS FUTUROS

de cor YUV;

• Desenvolvimento de um método de expansão dos planos detectados baseado na

comparação entre o ﬂuxo planar e o ﬂuxo óptico estimado para cada pixel da ima-

gem;

• Extração da geometria epipolar da cena, e recuperação da informação tridimensio-

nal de cada plano identiﬁcado utilizando uma técnica linear de triangulação espa-

cial;

• Execução de testes e análise dos resultados de cada etapa envolvida no processo, de

forma a facilitar o entendimento das vantagens e desvantagens do sistema proposto.

Inicialmente, a partir de um conjunto de pares de pontos correspondentes entre as duas

imagens de uma sequência, é proposto um esquema de agrupamento de pontos baseado

em homograﬁas e utilizado na obtenção da detecção dos principais planos presentes na

imagem. Em virtude de o movimento da câmera entre as aquisições de imagens suces-

sivas ser pequeno, o modelo aﬁm foi utilizado no processo de estimação da homograﬁa.

Além disso, tal modelo foi escolhido por sua simplicidade, visto que somente três pontos

são necessários no processo de estimação. Sendo assim, o procedimento de triangulação

de Delaunay foi utilizado como forma de facilitar a escolha dos pontos utilizados na es-

timação. Além disso, o esquema de ﬁltragem aplicado ao conjunto de triângulos obtidos

constitui uma importante forma de evitar a detecção de possíveis planos virtuais.

A escolha da homograﬁa inicial a ser utilizada no processo de agrupamento é um

importante fator a ser considerado. Em todas as situações, os melhores resultados foram

obtidos quando o procedimento é executado utilizando o grupo de triângulos ordenados

segundo a quantidade de pontos associados a suas respectivas homograﬁas.

O procedimento de expansão de planos do sistema proposto é baseado na informação

de ﬂuxo óptico estimado a partir das duas imagens em sequência da cena. Um novo

método de estimação do ﬂuxo a partir da informação de cor é proposto. Testes foram

realizados com diversos sistemas de cor e os melhores resultados foram obtidos com o

modelo YUV. Os resultados apresentados na Seção 2.2.5 (pág. 37) demonstram que a

utilização da informação de cor melhora a precisão e a robustez da estimação do ﬂuxo

óptico. Além disso, os resultados apresentados na Seção 4.2.3 (pág. 85) atestam o bom

funcionamento do processo de expansão dos planos combinando informação do ﬂuxo

planar e do ﬂuxo estimado. Os resultados demonstram a conﬁabilidade do método, visto

que o erro obtido no processo de expansão dos planos é baixo.

A reconstrução métrica dos planos é obtida a partir da recuperação da geometria epi-

polar da cena. A matriz fundamental foi estimada usando os pontos pertencentes a cada

plano detectado. O gráﬁco do erro mediano obtido no processo de estimação da matriz

109

fundamental é apresentado e os resultados satisfatórios. Supondo o sistema calibrado a

priori, a matriz essencial foi calculada e as matrizes da câmera obtidas. Ao ﬁnal, um

procedimento linear de triangulação foi utilizado para computar as coordenadas 3D do

conjunto de pontos pertencente a cada plano, deﬁnidas por um fator de escala. Os resulta-

dos apresentados no processo de reconstrução métrica são apenas visuais, mas sua análise

permite conﬁrmar o bom funcionamento do sistema proposto.

Uma análise mais profunda acerca da inﬂuência de falsas correspondências ao longo

de todo o processo é necessária. Com asdiversasetapasdeﬁltragemexistentes no sistema,

em todas as situações o número de pontos classiﬁcados erroneamente como pertencentes

a algum plano foi baixo.

Outro problema é a existência de pontos de interesse mal-localizados. Geralmente,

o par de pontos correspondentes é detectado em regiões aproximadas nas duas imagens.

Isto não caracteriza uma falsa correspondência visto que o movimento entre quadros é

pequeno. Em contrapartida, a variação na aproximação citada pode produzir um vetor de

movimento não condizente com o movimento da região onde se encontra o ponto. Este

foi o motivo que provocou as falsas classiﬁcações na imagem da Figura 4.4b (pág. 92).

A modiﬁcação do método visando tratar este tipo de problema é objeto de estudo futuro

deste trabalho.

Outras possibilidades de trabalhos futuros compreendem o estudo e análise das de-

mais técnicas existentes para cálculo de homograﬁas, estimação da matriz fundamental

e recuperação das matrizes da câmera. Além disso, é importante salientar a necessidade

de calcular o fator de escala inerente ao processo de estimação da geometria epipolar e

reconstrução métrica. Como sugestão, pode-se pensar em mesclar as informações pro-

duzidas por este sistema com a informação da altura conhecida da câmera, ou dados de

odometria.

Como já foi citado, os parâmetros intrínsecos da câmera são determinados a priori.

Outra sugestão de trabalho futuro seria inserir o processo de calibração no sistema de

segmentação proposto, tornando-o automático.

Finalmente, o principal desaﬁo consiste em embarcar e testar o sistema em uma pla-

taforma robótica móvel. A princípio, a complexidade computacional de cada etapa en-

volvida deve ser investigada de forma a comprovar a viabilidade em tal aplicação. Em

vista disso, a adequabilidade do sistema à execução em tempo-real é uma sugestão de tra-

balho futuro. O trabalho apresentado nesta tese sugere direções da utilização do sistema

proposto em aplicações práticas que possam fazer uso da informação de localização dos

planos presentes em uma cena.

110

CAPÍTULO 5. CONCLUSÕES E TRABALHOS FUTUROS

Referências Bibliográﬁcas

Agarwal, Anubhav, C. V. Jawahar e P. J. Narayanan (2005), A survey of planar homo-

graphy estimation techniques, Relatório Técnico IIIT/TR/2005/12, Centre for Visual

Information Technology.

Aires, Kelson R. T. e Adelardo A. D. de Medeiros (2007), Estimação do ﬂuxo óptico com

a adição de informação de cor, em ‘Anais do VIII Simpósio Brasileiro de Automação

Inteligente’, Florianópolis, SC, Brazil.

Aires, Kelson R. T., Andre M. Santana e Adelardo A. D. de Medeiros (2008), Optical ﬂow

using color information: preliminary results, em ‘Proceedings of the 2008 ACM

Symposium on Applied Computing’, ACM, Fortaleza, CE, Brazil, pp. 1607–1611.

Aires, Kelson R. T. e Helder de J. Araújo (2008), Optical ﬂow estimation using color in-

formation: study and results, em ‘Proceedings of V Congresso Luso-Moçambicano

de Engenharia’, Maputo, Moçambique.

Aires, Kelson R. T., Helder de J. Araújo e Adelardo A. D. de Medeiros (2008a), Plane

detection from monocular image sequences, em ‘Proceedings of 8th IASTED In-

ternational Conference on Visualization and Image Processing - VIIP2008’, ACTA

Press, Mallorca, Spain.

Aires, Kelson R. T., Helder de J. Araújo e Adelardo A. D. de Medeiros (2008b), Plane de-

tection using afﬁne homography, em ‘Proceedings of the XVII Congresso Brasileiro

de Automática - CBA2008’, Juiz de Fora, MG, Brazil.

Amintabar, A. e B. Boufama (2008), Homography-based plane identiﬁcation and mat-

ching, pp. 297–300.

Andrews, R. e B. Lovell (2003), Color optical ﬂow, em ‘Proceedings of Workshop on

Digital Image Computing’, Brisbane, Australia.

Armangué, Xavier e Joaquim Salvi (2003), ‘Overall view regarding fundamental matrix

estimation’, Image and Vision Computing 21, 205–220.

111

112

REFERÊNCIAS BIBLIOGRÁFICAS

Barron, J. L., D. J. Fleet, S. S. Beauchemin e T. A. Burkitt (1994), Performance of optical

ﬂow techniques, Relatório técnico, Dept. Comp. Sci., Univ. Western Ontario.

Barron, J. L., S. S. Beauchemin e D. J. Fleet (1994), On optical ﬂow, em I.Plander, ed.,

‘6th Int. Conf. on Artiﬁcial Intelligence and Information-Control Systems of Robots

(AIICSR)’, World Scientiﬁc, Bratislava, Slovakia, pp. 3–14. Sept. 12-16, 1994,

Smolenice Castle, Slovakia.

Barron, J. e R. Klette (2002), Quantitative color optical ﬂow, em ‘Proceedings of 16th

International Conference on Pattern Recognition’, Vol. 4, pp. 251–255.

Barron, J.L., D.J. Fleet, S.S. Beauchemin e T.A. Burkitt (1992), ‘Performance of optical

ﬂow techniques’, CVPR 92, 236–242.

Beauchemin, S. S. e J. L. Barron (1995), ‘The computation of optical ﬂow’, ACM Com-

puting Surveys 27(3), 433–467.

Bouguet, Jean-Yves (1999), ‘Pyramidal implementation of the Lucas Kanade feature trac-

ker’, OpenCV Documentation, Intel Corporation, Microprocessor Research Lab.

Caldeira, Eliete M. de O. (2002), Navegação Reativa de Robôs Móveis com Base no

Fluxo Óptico, Tese de doutorado, UFES, Vitória, ES.

Camus, Theodore A. (1994), Real-Time Optical Flow, Tese de doutorado, Department of

Computer Science, Brown University, Providence, USA.

Camus, Theodore Armand (1995), Real-time quantized optical ﬂow, em ‘Proceedings

of the IEEE Computer Architectures for Machine Perception’, Villa Olmo, Como,

Italy.

Chen, Zezhi, Nick Pears e Bojian Liang (2006), ‘Monocular obstacle detection using

reciprocal-polar rectiﬁcation’, Image Vision Computing 24(12), 1301–1312.

Corso, J., D. Burschka e G. Hager (2003), Direct plane tracking in stereo images for

mobile navigation, Vol. 1, pp. 875–880.

Criminisi, A., I.Reid e A. Zisserman (2000), ‘Single view metrology’, International Jour-

nal of Computer Vision V40(2), 123–148.

Dao, Nguyen Xuan, Bum-Jae You e Sang-Rok Oh (2005), Visual navigation for indoor

mobile robots using a single camera, em ‘International Conference on Intelligent

Robots and Systems’, IEEE Computer Society, pp. 1992–1997.

REFERÊNCIAS BIBLIOGRÁFICAS

113

DeSouza, Guilherme N. e Avinash C. Kak (2002), ‘Vision for mobile robot naviga-

tion: A survey’, IEEE Transactions on Pattern Analysis and Machine Intelligence

24(2), 237–267.

Dewilde, Patrick, Klaus Diepold e Walter Bamberger (2004), Optical ﬂow computation

and time-varying system theory, em ‘16th International Symposium on Mathemati-

cal Theory of Networks and Systems, MTNS2004’, Katholieke Universiteit Leuven,

Belgium.

Dubrofsky, Elan e Robert J. Woodham (2008), Combining line and point correspondences

for homography estimation, em ‘Proceedings of the 4th International Symposium on

Advances in Visual Computing’, Springer-Verlag, Berlin, Heidelberg, pp. 202–213.

Faugeras, Olivier (1993), Three-Dimensional Computer Vision, MIT Press.

Fischler, Martin A. e Robert C. Bolles (1981), ‘Random sample consensus: A paradigm

for model ﬁtting with applications to image analysis and automated cartography’,

Commun. ACM 24(6), 381–395.

Forsyth, David A. e Jean Ponce (2002), Computer Vision: A Modern Approach, 1

edição,

Prentice Hall Professional Technical Reference.

Fraundorfer, Friendrich, Konrad Schindler e Horst Bischof (2006), ‘Piecewise planar

scene reconstruction from sparse correspondences’, Image and Vision Computing

24(4), 395–406.

Gamarra, D., Teodiano Bastos-Filho, Mário Sarcinelli-Filho, Carlos Soria e R. Carelli

(2005), Optical ﬂow calculation using data fusion with decentralized information

ﬁlter, em ‘Proceedings of the IEEE International Conference on Robotics and Auto-

mation’, Barcelona, Spain, pp. 2853–2858.

Golland, P. e A. M. Bruckstein (1997), ‘Motion from color’, Computer Vision and Image

Understanding: CVIU 68(3), 346–362.

Golland, Polina (1995), Use of color for optical ﬂow estimation, Dissertação de mestrado,

Israel Institute of Technology, Haifa, Israel.

Gong, Haifeng, Qing Yang, Chunhong Pan e Hanqing Lu (2004), Generalized optical

ﬂow in the scale space, em ‘Third International Conference on Image and Graphics’,

pp. 536–539.

114

REFERÊNCIAS BIBLIOGRÁFICAS

Gonzalez, Rafael C. e Richard E. Woods (2007), Digital Image Processing, 3rd

edição,

Prentice Hall.

Harris, C. e M. Stephens (1988), A combined corner and edge detection, em ‘Proceedings

of The Fourth Alvey Vision Conference’, pp. 147–152.

Hartley, Richard I. (1993), Cheirality invariants, em ‘In Proc. DARPA Image Understan-

ding Workshop’, pp. 745–753.

Hartley, Richard I. (1997), ‘In defense of the eight-point algorithm’, IEEE Transactions

on Pattern Analysis and Machine Intelligence 19(6), 580–593.

Hartley, Richard I. e Andrew Zisserman (2004), Multiple View Geometry in Computer

Vision, 2

edição, Cambridge University Press.

Hartley, Richard I. e Peter Sturm (1994), Triangulation, em ‘In Proceedings of ARPA

Image Understanding Workshop’, pp. 957–966.

Horn, B.K.P. e B.G. Schunck (1981), ‘Determining optical ﬂow’, Artiﬁcial Intelligence

16(1-3), 185–203.

Jain, Paresh Kumar e C. V. Jawahar (2006), Homography estimation from planar con-

tours, em ‘Proceedings of the 3rd International Symposium on 3D Data Processing,

Visualization and Transmission’.

Jawahar, C. V. (2006), Homography estimation from planar contours, em ‘3D Data Pro-

cessing, Visualization, and Transmission, Third International Symposium on’, IEEE

Computer Society, Washington, DC, USA, pp. 877–884.

Kawamoto, Kazuhiko, Daisuke Yamada, Atsushi Imiya e Reinhard Klette (2002), Naviga-

tion using optical ﬂow ﬁelds: An application of dominant plane detection, Relatório

técnico, Computer Science Department of The University of Auckland.

Kim, Min Young e Hyungsuck Cho (2006), ‘An active trinocular vision system of sen-

sing indoor navigation environment for mobile robots’, Sensors and Actuators A:

Physical 125(2), 192–209.

Kim, Young-geun e Hakil Kim (2004), Layered ground ﬂoor detection for vision-based

mobile robot navigation, Vol. 1, pp. 13–18.

Kröse, Ben J. A., A. Dev e Frans C. A. Groen (2005), ‘Heading direction of a mobile

robot from the optical ﬂow’, Imaging and Vision Computing 18(5), 415–424.

REFERÊNCIAS BIBLIOGRÁFICAS

115

Lai, S. H. e B. C. Vemuri (1998), ‘Robust and efﬁcient computation of optical ﬂow’,

International Journal of Computer Vision 29, 87–105.

Lehmann, Stefan, Andrew P. Bradley, I. Vaughan L. Clarkson, John Williams e Peter J.

Kootsookos (2007), ‘Correspondence-free determination of the afﬁne fundamental

matrix’, IEEE Trans. Pattern Anal. Mach. Intell. 29(1), 82–97.

Li, Jian e R. Chellappa (2006), ‘Structure from planar motion’, IEEE Transactions on

Image Processing 15, 3466–3477.

Liang, Bojian e Nick Pears (2002), ‘Ground plane segmentation from multiple visual

cues’, Second International Conference on Image and Graphics 4875(1), 822–829.

Lim, SukHwan e Abbas El Gamal (2001), Optical ﬂow estimation using high frame rate

sequences, em ‘International Conference on Image Processing’, Vol. 2, pp. 925–928.

Liu, Hongche, Tsai-Hong Hong, Martin Herman, Ted Camus e Rama Chellappa (1998),

‘Accuracy vs efﬁciency trade-offs in optical ﬂow algorithms’, Computer Vision and

Image Understanding: CVIU 72(3), 271–286.

Longuet-Higgins, H. C. (1981), ‘A computer algorithm for reconstructing a scene from

two projections’, Nature 293, 133–135.

Lowe, David (2003), Distinctive image features from scale-invariant keypoints, em ‘In-

ternational Journal of Computer Vision’, Vol. 20, pp. 91–110.

Lucas, B.D. e Takeo Kanade (1981), An iterative image registration technique with an

application to stereo vision, em ‘IJCAI81’, pp. 674–679.

Luong, Quang-Tuan e Olivier D. Faugeras (1996), ‘The fundamental matrix: The-

ory, algorithms and stability analysis’, International Journal of Computer Vision

17(1), 43–75.

Luong, Quang-Tuan, Rachid Deriche, Olivier Faugeras e Theodore Papadopoulo (1993),

On determining the fundamental matrix: Analysis of different methods and experi-

mental results, Research Report RR-1894, INRIA.

Madjidi, Hossein e Shahriar Negahdaripour (2003), Robust optical ﬂow estimation using

underwater color images, em ‘Proceedings of Oceans’03’, San Diego, Ca.

116

REFERÊNCIAS BIBLIOGRÁFICAS

Madjidi, Hossein e Shahriar Negahdaripour (2004), On robustness and localization accu-

racy of optical ﬂow computation from color imagery, em ‘Proceedings of the 2nd

International Symposium on 3D Data Processing, Visualization and Transmission’,

pp. 317–324.

Markandey, Vishal e Bruce E. Flichbaugh (1990), Multispectral constraints for opti-

cal ﬂow computation, em ‘Proceedings of Third IEEE International Conference on

Computer Vision ICCV’, Osaka, Japan, pp. 38–41.

McCane, B., B. Galvin e K. Novins (1998), ‘The evaluation of optical ﬂow algorithms’,

International Conference on Control, Automation, Robotics and Vision .

McCane, B., B. Galvin, K. Novins e S. Mills (1998), ‘Recovering motion ﬁelds: An eva-

luation of eight optical ﬂow algorithms’, Proceedings of the Ninth British Machine

Vision Conference (BMVC-98) 1, 195–204.

McCarthy, Chris e Nick Barnes (2004), Performance of optical ﬂow techniques for indoor

navigation with a mobile robot, em ‘Proceedings of the IEEE International Confe-

rence on Robotics and Automation’, New Orleans, LA, USA, pp. 5093–5098.

Medeiros, Adelardo A. D. (1998), Introdução à robótica, em ‘ENA’98 - XVII Encontro

Nacional de Automática’, Natal, RN, BRA, pp. 56–65.

Mikolajczyk, K., T. Tuytelaars, C. Schmid, A. Zisserman, J. Matas, F. Schaffalitzky, T.

Kadir e L. Van Gool (2005), ‘A comparison of afﬁne region detectors’, International

Journal of Computer Vision 65(1-2), 43–72.

Mikolajczyk, Krystian e Cordelia Schmid (2005), ‘A performance evaluation of lo-

cal descriptors’, IEEE Transactions on Pattern Analysis and Machine Intelligence

27(10), 1615–1630.

Mitiche, Amar e Abdol-Reza Mansouri (2004), ‘On convergence of the Horn and

Schunck optical-ﬂow estimation method’, IEEE Transactions on Image Processing

13(6), 848–852.

Montijano, E. e C. Sagues (2008), Position-based navigation using multiple homo-

graphies, em ‘IEEE International Conference on Emerging Technologies and Fac-

tory Automation - ETFA 2008’.

Moravec, Hans P. (1977), Towards automatic visual obstacle avoidance, em ‘Proceedings

of the 5th International Joint Conference on Artiﬁcial Intelligence’, p. 584.

REFERÊNCIAS BIBLIOGRÁFICAS

117

Ohnishi, Naoya e Atsushi Imiya (2006), ‘Dominant plane detection from optical ﬂow for

robot navigation’, Pattern Recognition Letters 27(9), 1009–1021.

Ohta, Naoya (1989), ‘Optical ﬂow detection by color images’, IEEE International Con-

ference On Image Processing pp. 801–805.

Ohta, Naoya e Satoe Nishizawa (2006), ‘How much does color information help opti-

cal ﬂow computation?’, IEICE Transactions on Information and Systems - Oxford

Journal 5, 1759–1762.

Okada, Kei, Satoshi Kagami, Masayuki Inaba e Hirochika Inoue (2001), Plane segment

ﬁnder: Algorithm, implementation and applications, em ‘IEEE International Confe-

rence on Robotics and Automation’, Vol. 2, IEEE Computer Society, pp. 2120–2125.

Pears, Nick e Bojian Liang (2001), Ground plane segmentation for mobile robot visual

navigation, em ‘IEEE International Conference on Intelligent Robots and Systems’,

Vol. 3, IEEE Computer Society, pp. 1513–1518.

Pears, Nick, Bojian Liang e Zezhi Chen (2005), ‘Mobile robot visual navigation using

multiple features’, EURASIP J. Appl. Signal Process. 2005, 2250–2259.

Piazzi, Jacopo e Domenico Prattichizzo (2006), Plane detection with stereo images, em

‘IEEE International Conference on Robotics and Automation’, IEEE Computer So-

ciety, pp. 922–927.

Preparata, Franco P. e Michael I. Shamos (1985), Computational Geometry: An Introduc-

tion (Monographs in Computer Science), Springer.

Proesmans, M., L. Van Gool, E. Pauwels e A. Oosterlinck (1994), ‘Determination of opti-

cal ﬂow and its discontinuities using non-linear diffusion’, 3rd European Conference

on Computer Vision, ECCV’94 2, 295–304.

Ruiz, Alberto, Pedro de Teruel e Lorenzo Fernández (2006), ‘Robust homography esti-

mation from planar contours based on convexity’, Computer Vision – ECCV 2006

pp. 107–120.

Russel, Stuart e Peter Norvig (1995), ArtiﬁcialIntelligence: A Modern Approach, Prentice

Hall.

Salvi, J., X. Armangue e J. Pages (2001), A survey addressing the fundamental matrix es-

timation problem, em ‘IEEE International Conference on Image Processing’, Vol. 2,

Thessaloniki, Greece, pp. 209–212.

118

REFERÊNCIAS BIBLIOGRÁFICAS

Sarcinelli-Filho, Mário, Hansjorg A. Schneebeli e Eliete M. O. Caldeira (2002a), Optical

ﬂow-based obstacle detection and avoidance in mobile robot navigation, em ‘Pro-

ceedings of the 10th IEEE Mediterranean Conference on Control and Automation’,

Lisboa, Portugal.

Sarcinelli-Filho, Mário, Hansjorg A. Schneebeli e Eliete M. O. Caldeira (2002b), Using

optical ﬂow to control mobile robot navigation, em ‘Proceedings of the 15th IFAC

World Congress on Automatic Control’, Barcelona, Espanha.

Sarcinelli-Filho, Mário, Hansjorg A. Schneebeli, Eliete M. O. Caldeira e Bruno M. Silva

(2003), Optical ﬂow-based reactive navigation of a mobile robot, em ‘Proceedings

of the 2003 IEEE International Symposium on Industrial Electronics - ISIE 2003’,

Rio de Janeiro, RJ, Brasil. aceito para publicação e posteriormente retirado pelos

autores.

Schmid, Cordelia, Roger Mohr e Christian Bauckhage (2000), ‘Evaluation of interest

point detectors’, International Journal of Computer Vision 37(2), 151–172.

Sebastien, Dey (2003), ‘Low overhead optical ﬂow based robot navigation’, The Robotics

Institute, Carnegie Mellon. Diploma Work 2002-2003.

Selvatici, Antonio Henrique Pinto e Anna Helena Reali Costa (2004), Obstacle avoidance

using time-to-contact information, em ‘5th Symposium on Intelligent Autonomous

Vehicles’, Vol. 1, Instituo Superior Técnico, Lisboa, Portugal.

Seo, Jung-Kak, Hyun-Ki Hong, Cheung-Woon Jho e Min-Hyung Choi (2004), ‘Two

quantitative measures of inlier distributions for precise fundamental matrix estima-

tion’, Pattern Recognition Letters 25(6), 733–741.

Silveira, Geraldo, Ezio Malis e Patrick Rives (2006), Real-time robust detection of planar

regions in a pair of images, em ‘International Conference on Intelligent Robots and

Systems’, IEEE Computer Society, pp. 49–54.

Simoncelli, Eero P., Edward H. Adelson e David J. Heeger (1991), Probability distributi-

ons of optical ﬂow, em ‘Proceedings of Conference on Computer Vision and Pattern

Recognition’, IEEE Computer Society, Mauii, Hawaii, pp. 310–315.

Singh, Ajit (1991), Optic Flow Computation: A Uniﬁed Perspective, IEEE Computer

Society Press.

REFERÊNCIAS BIBLIOGRÁFICAS

119

Soria, Carlos Miguel, Ricardo Carelli e Mário Sarcinelli-Filho (2003), Optical ﬂow es-

timation using data fusion, em ‘Anais do VI Simpósio Brasileiro de Automação

Inteligente - VI SBAI’, Bauru, Sp, Brazil, pp. 259–265.

Sturm, P. F. e S. J. Maybank (1999), ‘On plane-based camera calibration: A general algo-

rithm, singularities, applications’, Computer Vision and Pattern Recognition 1, 432–

437.

Suhr, Jae Kyu, Kwanghyuk Bae, Jaihie Kim e Ho Gi Jung (2007), Free parking space

detection using optical ﬂow-based euclidean 3d reconstruction, em ‘MVA’, pp. 563–

566.

Tagliasacchi, Marco (2006), ‘A genetic algorithm for optical ﬂow estimation’, Image and

Vision Computing, In Press .

Tarel, Jean-Philippe (1997), ‘Global 3d planar reconstruction with uncalibrated cameras

and rectiﬁed stereo geometry’, Machine Graphics and Vision 6(4), 393–418.

Torr, Phillip H. S. e Andrew Zisserman (2000), ‘Mlesac: A new robust estimator with

application to estimating image geometry’, Computer Vision Image Understanding

78(1), 138–156.

Torr, Phillip H. S. e David W. Murray (1997), ‘The development and comparison of robust

methods for estimating the fundamental matrix’, International Journal Computer

Vision 24(3), 271–300.

Tsai, Roger Y. e Thomas S. Huang (1984), ‘Uniqueness and estimation of three-

dimensional motion parameters of rigid objects with curved surfaces’, IEEE Tran-

sactions on Pattern Analysis and Machine Intelligence 6, 13–27.

Vincent, Étienne. e Robert Laganière (2001), Detecting planar homographies in an image

pair, em ‘Proceedings of the 2nd International Symposium on Image and Signal

Processing and Analysis’, Pula, Croatia, pp. 182–187.

Wang, Hui, Kui Yuan, Wei Zou e Qingrui Zhou (2005), Visual odometry based on locally

planar ground assumption, em ‘2005 IEEE International Conference on Information

Acquisition’, Vol. 27.

Weijer, Joost van de e Theo Gevers (2004), Robust optical ﬂow from photometric invari-

ants, em ‘International Conference on Image Processing’, Vol. 3, pp. 1835–1838.

120

REFERÊNCIAS BIBLIOGRÁFICAS

Wu, F. C., Z. Y. Hu e F. Q. Duan (2005), 8-point algorithm revisited: Factorized 8-point

algorithm, em ‘Proceedings of the Tenth IEEE International Conference on Compu-

ter Vision’, Vol. 1, IEEE Computer Society, Washington, DC, USA, pp. 488–494.

Yin, Xiaoming e Ming Xie (2003), ‘Estimation of the fundamental matrix from unca-

librated stereo hand images for 3d hand gesture recognition’, Pattern Recognition

36(3), 567–584.

Zeng, Hui, Xiaoming Deng e Zhanyi Hu (2008), ‘A new normalized method on line-based

homography estimation’, Pattern Recogn. Lett. 29(9), 1236–1244.

Zhang, Dengsheng e Guojun Lu (2000), An edge and color oriented optical ﬂow estima-

tion using block matching, em ‘5th International Conference on Signal Processing,

WCCC-ICSP’, Vol. 2, pp. 1026–1032.

Zhang, Ying-Kang e Yang Xiao (2008), A practical method of 3d reconstruction based on

uncalibrated image sequence, em ‘9th International Conference on Signal Processing

- ICSP 2008’, Beijing, China, pp. 1368–1371.

Zhang, Zhengyou (1998), ‘Determining the epipolar geometry and its uncertainty: A

review’, International Journal of Computer Vision 27(2), 161–198.

Zhang, Zhengyou (2002), A ﬂexible new technique for camera calibration, Relatório Téc-

nico MSR-TR-98-71, Microsoft Research, Redmond, WA 98052.

Zhang, Zhengyou e Charles Loop (2001), ‘Estimating the fundamental matrix by transfor-

ming image points in projective space’, Computer Vision and Image Understanding

82(2), 174–180.

Zhou, Jin e Baoxin Li (2006a), Homography-based ground detection for a mobile robot

platform using a single camera, em ‘IEEE International Conference on Robotics and

Automation - ICRA 2006’, Vol. 15, pp. 4100–4105.

Zhou, Jin e Baoxin Li (2006b), Robust ground plane detection with normalized homo-

graphy in monocular sequences from a robot platform, em ‘IEEE International Con-

ference on Image Processing - ICIP 2006’, Atlanta, GA, pp. 3017–3020.

Zucchelli, Marco, José Santos-Victor e Henrik I. Christensen (2002), Multiple plane seg-

mentation using optical ﬂow, em ‘British Machine Vision Conference’, pp. 313–322.

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 