multifoveamento em multirresolução com fóveas móveis...universidade federal do rio grande do...

UNIVERSIDADE DO RIO GRANDE DO NORTEFEDERAL

UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE

CENTRO DE TECNOLOGIA

PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E

DE COMPUTAÇÃO

Multifoveamento em Multirresolução comFóveas Móveis

Petrúcio Ricardo Tavares de Medeiros

Orientador: Prof. Dr. Rafael Beserra Gomes

Co-orientador: Prof. Dr. Luiz Marcos Garcia Gonçalves

Dissertação de Mestrado apresentada aoPrograma de Pós-Graduação em EngenhariaElétrica e de Computação da UFRN (área deconcentração: Engenharia de Computação)como parte dos requisitos para obtenção dotítulo de Mestre em Ciências.

Número de ordem PPgEEC: M469Natal, RN, junho de 2016

Catalogação da Publicação na Fonte Universidade Federal do Rio Grande do Norte - Sistema de

Bibliotecas Biblioteca Central Zila Mamede / Setor de Informação e Referência

Medeiros, Petrúcio Ricardo Tavares de. Multifoveamento em multirresolução com fóveas móveis /

Petrúcio Ricardo Tavares de Medeiros. - 2016. 100 f. : il.

Dissertação (mestrado) - Universidade Federal do Rio Grande do Norte, Centro de Tecnologia, Programa de Pós-Graduação em Engenharia Elétrica e de Computação. Natal, RN, 2016.

Orientador: Prof. Dr. Rafael Beserra Gomes. Coorientador: Prof. Dr. Luiz Marcos Garcia Gonçalves.

1. Visão computacional - Dissertação. 2. Multirresolução - Dissertação. 3. Multifoveamento - Dissertação. 4. Feature - Dissertação. 5. SURF (Feature) - Dissertação. I. Gomes, Rafael Beserra. II. Gonçalves, Luiz Marcos Garcia. III. Título.

RN/UF/BCZM CDU 004.932

A todos que contribuiram para odesenvolvimento deste trabalho.

Agradecimentos

Ao meu orientador e ao meu co-orientador, professores Rafael Beserra e Luiz Marcos,sou grato pela orientação.

À Ana Karoline pela paciência e por toda contribuição.

À minha família pelo apoio durante esta jornada.

À CAPES, pelo apoio financeiro.

Resumo

O foveamento é uma técnica de visão computacional capaz de promover a redução da

informação visual através de uma transformação da imagem, em domínio espacial, para o

domínio de multirresolução. Entretanto, esta técnica se limita a uma única fóvea com mo-

bilidade dependente do contexto. Neste trabalho são propostas a definição e a construção

de um modelo multifoveado denominado MMMF (multifoveamento em multirresolução

com fóveas móveis) baseado em um modelo anterior denominado MMF (multirresolução

com fóvea móvel). Em um contexto de múltiplas fóveas, a aplicação de várias estrutu-

ras MMF, uma para cada fóvea, resulta em um considerável aumento de processamento,

uma vez que há interseções entre regiões de estruturas distintas, as quais são processadas

múltiplas vezes. Dadas as estruturas de fóveas MMF, propomos um algoritmo para obter

regiões disjuntas que devem ser processadas, evitando regiões redundantes e, portanto,

reduzindo o tempo de processamento. Experimentos são propostos para validar o modelo

e verificar a sua aplicabilidade no contexto de visão computacional. Resultados demons-

tram o ganho em termos de tempo de processamento do modelo proposto em relação ao

uso de múltiplas fóveas do modelo MMF.

Palavras-chave: Visão computacional, multirresolução, multifoveamento, features,

SURF.

Abstract

Foveation is a computer vision technique for visual information reduction obtained

by applying an image transformation in the spatial domain to the multiresolution do-

main. However, this technique is limited to a single fovea context-dependent mobility.

This work proposes the definition and the construction of a multifoveated model called

MMMF (Multiresolution Multifoveation using Mobile Foveae) based on an earlier model

called MMF (Multiresolution with Moving Fovea). In the context of multiple foveae, the

application of various MMF structures, one for each fovea, results in an increase in pro-

cessing time, since there are intersections between regions of different structures, which

are processed multiple times. Given MMF structures, an algorithm in order to get disjoint

regions which are to be processed is proposed, avoiding redundant regions and thereby

reducing the processing time. Experiments are proposed to validate the model and to ve-

rify its applicability in the computer vision context. Results show the gain in processing

time of the proposed model compared to the use of multiple MMF structures.

Keywords: computer vision, multiresolution, multifoveation, features, SURF.

Sumário

Sumário i

Lista de Figuras v

Lista de Tabelas ix

Lista de Símbolos e Abreviaturas xi

1 Introdução 1

1.1 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3 Contribuição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.4 Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.5 Organização do Texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Embasamento Teórico 11

2.1 Abstração de Dados (Features) . . . . . . . . . . . . . . . . . . . . . . . 12

2.2 Pré-processamento Usando Imagens em Multirresolução . . . . . . . . . 13

2.2.1 Pirâmides Gaussiana e Laplaciana . . . . . . . . . . . . . . . . . 14

2.2.2 Espaço de Escalas . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.2.3 A Representação Log-polar . . . . . . . . . . . . . . . . . . . . 16

2.2.4 A Transformada Wavelet . . . . . . . . . . . . . . . . . . . . . . 18

2.2.5 Pirâmide com Filtros Direcionais . . . . . . . . . . . . . . . . . 20

i

2.2.6 Multicaracterísticas (ou Múltiplas Features) em Multirresolução

(MRMF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.2.7 Multirresolução com Fóvea Móvel (MMF) . . . . . . . . . . . . 24

2.2.8 Movimento da fóvea . . . . . . . . . . . . . . . . . . . . . . . . 26

3 Trabalhos relacionados 29

4 Problemática 35

4.1 Região de interseção entre níveis . . . . . . . . . . . . . . . . . . . . . . 35

4.2 Disposição das interseções . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.3 Identificação do vértice de interseção . . . . . . . . . . . . . . . . . . . . 39

4.3.1 Formalismo matemático . . . . . . . . . . . . . . . . . . . . . . 40

4.4 Vetor de direção das regiões . . . . . . . . . . . . . . . . . . . . . . . . 45

4.5 Conjunto de regiões sem interseção . . . . . . . . . . . . . . . . . . . . 46

4.6 Extração multifoveada de features . . . . . . . . . . . . . . . . . . . . . 47

5 Implementação 53

5.1 Biblioteca de visão computacional e reuso de códigos . . . . . . . . . . . 53

5.2 A estrutura multifoveada . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5.2.1 Configuração das estruturas do sistema multifoveado . . . . . . . 55

5.2.2 Incorporação ao método MMF . . . . . . . . . . . . . . . . . . . 56

5.3 Operações de inserção e remoção de estruturas . . . . . . . . . . . . . . 58

5.3.1 Precedência entre estruturas . . . . . . . . . . . . . . . . . . . . 59

6 Experimentos e Resultados 61

6.1 Processamento em relação à distância entre fóveas . . . . . . . . . . . . 61

6.2 Comparação entre os métodos . . . . . . . . . . . . . . . . . . . . . . . 66

6.2.1 Disposição nos extremos da imagem . . . . . . . . . . . . . . . . 67

6.2.2 Disposição ao redor da origem . . . . . . . . . . . . . . . . . . . 68

6.2.3 Disposição das fóveas na origem . . . . . . . . . . . . . . . . . . 69

7 Conclusão 71

Referências bibliográficas 73

Lista de Figuras

1.1 Representação de duas estruturas foveadas em pirâmide. . . . . . . . . . 4

1.2 Figura panorâmica construída a partir de um conjunto de imagens . . . . 7

1.3 Imagens utilizadas para confeccionar a imagem panorâmica . . . . . . . . 7

1.4 Rastreamento de pessoas em uma faixa de pedestres . . . . . . . . . . . . 8

2.1 Função gaussiana bidimensional e sua curva de nível. . . . . . . . . . . . 15

2.2 Pirâmide gaussiana. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.3 Pirâmide laplaciana. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.4 Espaço de escalas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.5 Representação da imagem no domínio log-polar (imagem esquerda) e sua

reconstrução no domínio cartesiano (imagem direita). . . . . . . . . . . . 18

2.6 Decomposição da imagem utilizando a transformada wavelet (imagem

esquerda) e equalização da decomposição (imagem direita). . . . . . . . . 19

2.7 Filtros direcionais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.8 Pirâmide com filtros direcionais . . . . . . . . . . . . . . . . . . . . . . 21

2.9 Reconstrução da pirâmide com filtros direcionais . . . . . . . . . . . . . 21

2.10 Construção do domínio de multirresolução com MCMR . . . . . . . . . . 23

2.11 Construção das camadas . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.12 Construção dos níveis com o MMF. . . . . . . . . . . . . . . . . . . . . 25

2.13 Vetor de mobilidade da fóvea . . . . . . . . . . . . . . . . . . . . . . . . 27

4.1 Intersecção entre elementos de P2. . . . . . . . . . . . . . . . . . . . . . 37

4.2 Disposições das regiões de interseção entre duas fóveas . . . . . . . . . . 38

v

4.3 Interseção entre duas estruturas fóveadas com o MMF . . . . . . . . . . . 40

4.4 Projeção (linhas em azul) dos vértices das regiões no plano yz. Cada

vértice, ao longo dos níveis, projeta um segmento de reta. . . . . . . . . . 40

4.5 Disposições de duas fóveas projetadas no plano xz. . . . . . . . . . . . . 41

4.6 Vetor que define a direção da região eliminada, sendo esta construída a

partir das informações centrais de cada região. . . . . . . . . . . . . . . . 46

4.7 Exemplo de distribuição de vértices de interseção dentro de uma imagem. 49

4.8 Exemplo de direção das regiões que devem ser eliminadas. . . . . . . . . 49

4.9 Exemplo de divisão do nível em regiões verticais. . . . . . . . . . . . . . 49

4.10 Exemplo de nível com regiões de interseção eliminadas. . . . . . . . . . 50

5.1 Organização das fóveas na interface multifoveada. . . . . . . . . . . . . . 54

5.2 Inserção de fóveas na lista. . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.3 Remoção de fóveas a lista. . . . . . . . . . . . . . . . . . . . . . . . . . 59

6.1 Disposição das Fóveas f (azul) e g (verde) para o deslocamento diagonal. 62

6.2 Gráfico do número de pixels processados no último nível da fóvea g com

uma variação na distância entre as fóveas realizado a partir de um deslo-

camento diagonal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

6.3 Gráfico do número de pixels processados em todos os níveis da fóvea g

com uma variação na distância entre as fóveas realizado a partir de um

deslocamento diagonal. . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

6.4 Disposição das Fóveas f (azul) e g (verde) para o deslocamento vertical. . 64

6.5 Gráfico do número de pixels processados no último nível da fóvea g com

uma variação na distância entre as fóveas realizado a partir de um deslo-

camento vertical. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

6.6 Gráfico do número de pixels processados em todos os níveis da fóvea g

com uma variação na distância entre as fóveas realizado a partir de um

deslocamento vertical. . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

6.7 Imagem em forma de tabuleiro de xadrez utilizada para realizar os testes

referentes ao posicionamento de 4 fóveas. . . . . . . . . . . . . . . . . . 66

Lista de Tabelas

3.1 Trabalhos relacionados à técnica de multifoveamento . . . . . . . . . . . 34

4.1 Tabela de exemplo da definição do vetor de direção entre as regiões, le-

vando em consideração a variação nas coordenadas x e y. . . . . . . . . . 47

6.1 Tempo médio (milissegundos) e desvio padrão para a obtenção dos key-

points, considerando as poses (−95,−95), (95,95), (95,−95) e (−95,95). 67

6.2 Tempo médio (milissegundos) e desvio padrão para a obtenção dos des-

critores, considerando as poses (−95,−95), (95,95), (95,−95) e (−95,95). 67


points, considerando as poses (-30,-30), (30,30), (30,-30) e (-30,30). . . . 68


critores, considerando as poses (-30,-30), (30,30), (30,-30) e (-30,30). . . 68


points, considerando que todas as fóveas estão posicionadas na origem. . 69


critores, considerando que todas as fóveas estão posicionadas na origem. . 69

ix

Lista de Símbolos e Abreviaturas

AV D : Absolute Value of Differences

CPU : Central Processing Unit

CT : Contrast Threshold

CV R : Cartesian Variable Resolution

DCT : Discrete Cosine Transform

FPGA : Field Programmable Gate Array

MMF : Multiresolution with Moving Fovea

MMMF : Multiresolution Multifoveation using Mobile Foveae

MRMF : Multiresolution Multifeatures

OpenCV : Open Source Computer Vision

PSNR : Peak Signal-to-Noise Ratio

SAD : Sum of Absolute Differences

SFMG : Shifted Fovea Multiresolution Geometry

SSIM : Structural Similarity Index Measure

fc : Cut-off frequency

xi

Capítulo 1

Introdução

O desenvolvimento de sistemas robóticos eficientes está diretamente associado ao

aperfeiçoamento dos atuadores, cuja finalidade é proporcionar a interação com o am-

biente, e dos sensores, os quais possibilitam a extração de dados que são mapeados em

informação sobre o ambiente útil aos robôs no desempenho de tarefas. Em robôs, câme-

ras são geralmente utilizadas como sensores visuais, que são capazes de extrair uma vasta

quantidade de informação. As imagens adquiridas por câmeras passam por um proces-

samento, a fim de se extrair características (ou features), que servem como entrada para

algum processo de decisão (reasoning).

Em se tratando de Robótica, o processamento da informação deve ser realizado, ge-

ralmente, obedecendo a alguma restrição de tempo real, visando garantir que os atuadores

possam executar alguma tarefa em tempo hábil. Porém, é sabido que processar imagens

é uma tarefa bastante custosa, computacionalmente falando. Então, a ideia é reduzir a

quantidade de processamento, o que pode ser feito tanto pela redução da quantidade de

dados a serem processados quanto pela abstração de features (feature selection) a par-

tir desses dados. Através dessas duas abordagens podemos garantir o processamento de

informação visual em tempo real (Gomes et al. 2010). Reduzir a quantidade de dados a

serem processados é a abordagem a ser estudada no presente trabalho. Uma proposta para

isso, que tem inspiração no sistema de visão biológico, é a aplicação da técnica conhecida

como foveamento (Gomes et al. 2010). A ideia dessa técnica é manter a resolução má-

2 CAPÍTULO 1. INTRODUÇÃO

xima possível em uma porção pequena da imagem, denominada de fóvea, similar à região

de mesmo nome existente na retina do olho biológico, e diminuir a resolução da imagem

à medida que se afasta da fóvea (região central da imagem).

Não obstante vários estudos de neurobiologia terem confirmado a existência dessa es-

trutura de sensores em multirresolução, na retina do olho biológico, a sua existência é

percebida facilmente quando fixamos nossos olhos em algum objeto e tentamos prestar

atenção em partes variadas do campo de visão. Pode-se verificar a existência de uma re-

gião aproximadamente central (no centro do campo de visão) com maior acuidade visual,

projetada diretamente na fóvea, e uma perda de acuidade visual de forma logarítmica com

relação à distância para a fóvea (Traver & Bernardino 2009).

A técnica de foveamento, ao se inspirar no sistema de visão biológico, incorpora uma

limitação inerente que pode ser observada durante as tarefas de atenção visual. Esta limi-

tação decorre da impossibilidade da aplicação de vários pontos de atenção visual em uma

cena de uma única vez. Além disso, outro problema é definir qual o ponto em que a fóvea

deve ser posicionada. Por exemplo, se durante a execução de uma tarefa de atenção do

tipo top-down, em que o cérebro diz onde a atenção deve ser posta (como na leitura de

um texto, por exemplo), for ativada, por algum motivo (uma interrupção por alguma pes-

soa passando no campo visual, por exemplo), a atenção do tipo bottom-up, então deve-se

definir qual tarefa (continuar a leitura ou voltar atenção à pessoa) deverá conter a fóvea.

Para resolver este tipo de problema, se quisermos um sistema que possa executar as duas

ao mesmo tempo, é essencial mover a fóvea entre as duas tarefas (ou que se tenha duas

fóveas), a fim de garantir que a meta proposta pela atenção top-down seja alcançada e que

o sistema esteja preparado para reagir a qualquer ocorrência que foge da normalidade,

ou seja, que requer a atenção bottom-up. Convém ressaltar que o paralelismo da fóvea

(duas fóveas) não é possível biologicamente, mas é possível alternar a posição dela, com

a realização de movimentos sacádicos.

Então, notamos que a percepção visual biológica é bastante complexa e eficiente para

1.1. METODOLOGIA 3

garantir com precisão que a fóvea esteja em apenas um objeto (ou região de atenção) por

vez. A fim de contornar esta limitação em termos computacionais, a literatura sugere

a utilização da técnica de multifoveamento, que se caracteriza pela aplicação de várias

fóveas na imagem. Podemos conseguir isso através da replicação de algum algoritmo

de foveamento, porém esta metodologia deve provocar o processamento de informações

redundantes. Em outras palavras, o aumento de estruturas foveadas na imagem provocaria

um aumento significativo na extração de features visuais.

Então, neste trabalho, propomos uma nova abordagem de multifoveamento, que é

uma técnica que determina várias regiões de maior acuidade visual possível na imagem,

diferentemente do conceito da fóvea biológica, acima, com intuito de fornecer maior ca-

pacidade de atenção visual aos sistemas robóticos. Para isso, estendemos o trabalho de

foveamento com mobilidade dependente do contexto proposto por Gomes (Gomes 2013),

onde é realizada uma transformação de uma imagem no domínio de espaço para o domínio

de multirresolução. Após esta transformação, a imagem original passa a ser representada

por várias imagens de tamanho reduzido, diminuindo assim o tempo de processamento

para extração de features, ou pontos que se destacam na região. Através da extração

de features, pode-se inferir algum conhecimento sobre uma determinada região da ima-

gem (Gomes 2013), em tempo real (Gomes et al. 2008).

1.1 Metodologia

Utilizamos a formalização matemática do método de Multirresolução com Fóvea Mó-

vel (MMF , sigla em inglês), que delimita regiões no domínio de espaço que deverão

ser transformadas para o domínio de multirresolução (Gomes 2013), com a finalidade de

introduzir uma metodologia capaz de detectar as regiões de interseções no esquema de

multirresolução.

Para isso, é necessário compreender as estruturas MMF como sendo pirâmides que


se interceptam no espaço. Essas pirâmides são construídas posicionando cada porção, do

domínio de espaço, no plano xy de tal forma que o eixo z represente o nível de escala

da estrutura MMF . A Figura 1.1 apresenta a interseção entre duas estruturas no domínio

MMF , com suas fóveas tendo a dimensão de um pixel.

f1f2

O

x

y

z

Figura 1.1: Representação de duas estruturas foveadas em pirâmide.

Fazendo uso da transformação linear de projeção ortogonal nos planos xz e yz pode-

mos inferir algebricamente as posições de interseções entre duas fóveas. Consequente-

mente, podemos delimitar as regiões de interseção em cada nível do modelo MMF . A

partir desta metodologia, é possível eliminar o processamento redundante decorrente da

sobreposição no espaço da estrutura de multirresolução. Ademais, foram realizadas novas

formulações matemáticas para garantir que o método comporte a técnica de multifovea-

mento.

1.2 Motivação

A motivação desta pesquisa advém do trabalho iniciado durante a tese de doutorado de

Gonçalves (Gonçalves 1999) em 1999, que propôs um método de Multicaracterística em

1.3. CONTRIBUIÇÃO 5

Multirresolução (MRMF , sigla em inglês) implementado em um sistema computacional

com processador dedicado. Esse aparato computacional processa as imagens adquiridas

por câmeras montadas em uma cabeça (estéreo), articulada, com 4 graus de liberdade.

Após aplicação do método MRMF em questão, são extraídas características já no domí-

nio de multirresolução. Neste domínio, a estrutura MRMF é composta por imagens com

pixels em diferentes resoluções espaciais, mas tendo todas elas o mesmo tamanho (diga-

mos 20×15 pixels, em caso de 5 níveis de escalas diferentes), bem reduzido em relação

à imagem original (digamos 640×480).

O MRMF foi melhor formalizado matematicamente no trabalho de mestrado de Go-

mes (Gomes 2013), que ainda contribuiu, no seu doutorado, dando mobilidade à estrutura

de multirresolução, a qual passou a ser conhecida como MMF . Gomes pôde comprovar

durante a análise dos resultados de sua tese que a extração de features na imagem foveada

ocorre em maior quantidade na fóvea.

Podemos perceber que todo o avanço desta linha de pesquisa busca contribuir para o

desenvolvimento da visão computacional para aplicações de tempo real, especialmente na

extração de features. Com esta intenção, a proposta deste trabalho é estender o método

MMF para que este seja capaz de suportar múltiplas fóveas móveis e assim fornecer

a capacidade de manter a atenção visual em diversos contextos ao mesmo tempo, por

exemplo, em diversos objetos que se movem no campo de visão.

1.3 Contribuição

A contribuição deste trabalho é a extensão da técnica MMF com o propósito de ga-

rantir o suporte à criação de múltiplas fóveas, cujas posições podem ser modificadas em

tempo de execução, no decorrer da aplicação, se necessário. Uma maneira trivial de fazer

isso seria a simples reexecução do método MMF várias vezes para construção da estrutura

multifoveada. Porém, queremos evitar isso porque uma parte significativa da informação


seria reprocessada várias vezes. Por exemplo, o nível de resolução mais grosseiro se-

ria o mesmo, sendo recalculado para todas as fóveas. Desta forma, o processamento de

features nessa estrutura terminaria sendo elevado devido à quantidade de redundâncias.

Por esta razão, propomos um método capaz de garantir que não ocorra nenhuma re-

dundância de processamento durante a extração de features, ou seja, que nas regiões de

interseção entre as imagens no domínio de multirresolução não ocorra a extração repeti-

tiva de features, a cada nova fóvea inserida, caso esta já tenha sido calculada para uma das

fóveas anteriores. Para isso, basta definir os limites dessas regiões de interseção, e nessas

evitar o reprocessamento. Esta tarefa não é tão simples, principalmente se o número de

estruturas for elevado, mas há todo um formalismo que permite a sua implementação que

foi desenvolvido neste trabalho.

1.4 Aplicações

O multifoveamento pode ser aplicado durante a confecção de uma imagem panorâ-

mica, como na Figura 1.2, construída a partir de um conjunto de imagens. No caso,

foram utilizadas as seis primeiras imagens do dataset cvc01passadis para a construção da

imagem panorâmica a partir do benchmark de visão computacional, disponível no sítio

link: http://www.iiia.csic.es/ãramisa/datasets/iiiapanos.html (acessado em 22 de junho de

2016), que contém sobreposições (vide Figura 1.3). Nesta tarefa, ocorre a necessidade de

se identificar features semelhantes entre as imagens para realizar uma colagem perfeita

entre imagens adjacentes (com certa sobreposição).

Podemos aplicar várias fóveas, em diferentes posições, a cada imagem do conjunto e

para cada uma das fóveas definir extrações de features distintas, tais como cores, arestas

ou bordas, cantos (corners), e blobs. Consequentemente, é possível realizar a colagem

com melhor perfeição, para a criação da imagem panorâmica, pois não se usará apenas a

correlação entre um mesmo grupo de features, mas sim um conjunto de correlações entre

1.4. APLICAÇÕES 7

Figura 1.2: Figura panorâmica construída a partir de um conjunto de imagens (Ramisaet al. 2008).

Figura 1.3: Imagens utilizadas para confeccionar a imagem panorâmica (Ramisa et al.2008).

múltiplos grupos de features distintas.

No processo de atenção visual, é indiscutível a importância de múltiplas fóveas (Dhavale

& Itti 2003), visto que o foveamento não consegue manter com precisão a atenção em todo

o campo de visão, ou seja, é possível que um robô não consiga desviar de dez objetos jo-


gados ao mesmo tempo em sua direção. Enquanto que, durante o uso de multifoveamento

poderia ser adicionada uma fóvea a cada estímulo detectado e o robô poderia estabelecer

um controle para reagir diante desta situação.

Ainda, outra aplicação é em atenção top-down, na busca por um determinado objeto

ou padrão em meio a outros objetos distraidores. Usando algum método grosseiro de

verificação, podem ser determinadas várias posições para fóveas, para vários candidatos

(incluindo distraidores), e depois percorridas essas fóveas com mais detalhes para confir-

mar a presença (ou não) do objeto em questão na mesma, descartando objetos meramente

distraidores da atenção.

Figura 1.4: Rastreamento de pessoas em uma faixa de pedestres (Yang et al. 2016).

A aplicação que mais justifica a utilização de multifoveamento é o rastreamento de

múltiplos alvos, como observado na Figura 1.4, porque é impossível com uma única fó-

vea rastrear vários objetos a cada frame. A Figura 1.4 foi extraída em 3 momentos do

dataset TUD-Crossing disponível no sítio: https://motchallenge.net/tracker/NOMTwSDP

(acessado em 22 de junho de 2016). O olho humano consegue extrair várias features em

todo o campo de visão e através dessas podemos inferir a posição dos objetos na cena,

mas sem garantir precisão. Para garantir o rastreamento com precisão de todos os objetos

é necessário aplicar uma fóvea a cada objeto ou realizar o movimento da estrutura foveada

1.5. ORGANIZAÇÃO DO TEXTO 9

para cada objeto. Porém, este último procedimento só pode ser realizado em tempo real

se houver poucos objetos a serem rastreados.

1.5 Organização do Texto

No Capítulo 2, é apresentado um apanhado dos métodos mais relevantes sobre as téc-

nicas de foveamento e multifoveamento, ressaltando-se como estas foram desenvolvidas

e para o que se propõem. No Capítulo 3, são mostrados os vários trabalhos relacionados

ao tema, com ênfase na metodologia escolhida, sendo feita uma discussão dos resultados

obtidos na literatura. O Capítulo 4 formaliza matematicamente o problema de multi-

foveamento e apresenta uma solução sem redundância de cálculos. Em sequência, no

Capítulo 5, mostramos as implementações do método de Multifoveamento em Multirre-

solução com Fóveas Móveis (MMMF) e no Capítulo 6 nos dedicamos aos experimentos

para verificação da técnica e discussão dos resultados obtidos após a aplicação do algo-

ritmo MMMF . Por fim, o Capítulo 7 é destinado a expor as considerações deste trabalho,

indicando possibilidades de trabalhos futuros.

Capítulo 2

Embasamento Teórico

Neste capítulo, é apresentada a base teórica envolvendo os métodos de multirresolu-

ção, tais como o espaço de escalas, log-polar, wavelets, pirâmides com filtros direcionais,

MRMF e MMF , bem como os conceitos teóricos por detrás da extração de características

ou features.

Para motivar a leitura, tratemos primeiro dos dois problemas relevantes citados no

Capítulo 1, ainda em aberto, que são formulados pela comunidade científica, a respeito

da extração de features. O primeiro deles diz respeito à definição de quais são as ca-

racterísticas relevantes a serem extraídas de um conjunto de dados (em nosso caso, uma

imagem). Note que um conjunto muito grande de features pode ser oneroso ao sistema

computacional, principalmente quando se tem restrições de tempo real. Por exemplo, se

for necessário aplicar vários filtros (implementados por correlação) em uma imagem, isso

pode ser muito caro computacionalmente.

O segundo problema diz respeito a quais features devem ser escolhidas desse con-

junto, que sejam úteis para que uma tarefa em execução possa ser completada com efi-

cácia. Este também é um problema não trivial, dependendo muito do contexto em que

a tarefa se encontra inserida. Se for um contexto em que se deseja localizar objetos em

forma de planos, por exemplo, locais amplos de intensidade constante (gradiente zero

ou bem próximo disso) dão indícios da existência de planos, portanto o filtro gradiente

é uma feature relevante. Porém, no caso de objetos com forma de elipses ou círculos,

12 CAPÍTULO 2. EMBASAMENTO TEÓRICO

ou ainda portas, janelas e outros objetos representados por figuras geométricas mais bem

comportadas, a transformada Hough (primeiro caso) ou features baseadas no filtro de Har-

ris (detector de cantos para os outros casos) podem ser usados. Note que ter todas essas

características disponíveis a todo quadro processado (a 30 fps) pode ser oneroso, ou até

não factível.

Então, parece natural ter apenas um conjunto delas sendo calculado a um dado tempo.

Ou então prover uma técnica que as calcule sobre alguma estrutura com menos informa-

ção, porém preservando a informação em alguma região da imagem que seja essencial à

tarefa em questão. Aqui a ideia de foveamento se encaixa como uma luva. De fato, se

usarmos esta estrutura, como será visto, é possível acelerar o processamento em muitas

vezes na extração de features

2.1 Abstração de Dados (Features)

Formalmente, a cena pode ser representada em uma imagem por meio de uma ma-

triz bidimensional, onde cada célula, ou pixel, dessa matriz guarda um valor de cor que

descreve a tonalidade do raio de luz que foi refletido pela superfície dos objetos. A mani-

pulação computacional desses pixels possibilita a extração das features dos objetos, tais

como: textura, forma e posição (a um nível de abstração mais alto). As features descre-

vem de forma abstrata os objetos da cena e por esta razão são bastante exploradas nos

algoritmos de matching, identificação e classificação de objetos, controle de atenção e

sistemas de navegação robótico. Na prática, são valores calculados, com posições (espa-

cial) bem definidas na imagem. Essas duas características são essenciais para que se tenha

uma feature: poder ser medida de algum modo e ter uma posição espacial bem definida

na imagem (ou na cena).

2.2. PRÉ-PROCESSAMENTO USANDO IMAGENS EM MULTIRRESOLUÇÃO 13

2.2 Pré-processamento Usando Imagens em Multirreso-

lução

Durante a evolução da pesquisa, voltamos nossos esforços para extrair o melhor de-

sempenho da estrutura. É por este motivo que cientistas buscam compreender e imitar o

sistema humano e, consequentemente, transferir estes conhecimentos para os robôs (Traver

& Bernardino 2009). A robótica sempre se inspirou nas características dos seres huma-

nos para a construção de robôs, visto que o ser humano estaria mais apto a se relacionar

com máquinas que possuíssem suas feições. Desta forma, muitos dos aspectos e sentidos

humanos foram e estão sendo incorporados aos sistemas robóticos, tais como: forma de

andar, falar e ver.

O sistema de visão é o mais complexo e completo entre todos e isso vale também na

Robótica, onde o sistema visual exige muito mais processamento para ser imitado por

um sistema computacional. Para resolver este problema, Uhr propõe aproximá-lo a um

cone de reconhecimento, onde, quanto mais próximo do pico menor qualidade encon-

tramos (Uhr 1972). Esta forma de representação, de certa forma, simula o inverso do

comportamento da visão biológica, pois na visão biológica é oferecida maior qualidade

de resolução à região que se encontra no centro da retina, ou próxima dessa. Esta região,

denominada fóvea, é composta por uma pequena área na parte central da retina, bem no

fundo do olho, que apresenta a maior acuidade visual (Oxford dictionary of english 2010)

que diminui de acordo com a aproximação à periferia do campo visual (ou da retina).

O funcionamento do olho humano é de certa forma similar ao de uma câmera, quer

dizer, seria mais correto dizer o oposto. Na visão biológica, raios de luz filtrados pe-

las lentes, passam através da córnea, que é membrana que protege o olho, entrando pela

pupila, que é o orifício central da íris que altera de diâmetro de acordo com a maior ou

menor intensidade de luz. O cristalino direciona então os raios de luz para a retina, no

fundo do olho, onde estão efetivamente localizados os sensores. Encontramos na retina


dois tipos de células fotoreceptoras: os cones, sensíveis a todo o espectro de cores visível,

e os bastonetes, que são células com sensibilidade à iluminação. Os bastonetes são dis-

tribuídos mais uniformemente na retina, enquanto que os cones são mais concentrados na

região que apresenta a maior acuidade visual, conhecida como fóvea. Os fotoreceptores

convertem os dados visuais em estímulos que são interpretados pelo cérebro, e assim a

informação visual é processada.

A partir dos estudos de Uhr, outros métodos foram propostos posteriormente, tais

como, por exemplo, as pirâmides gaussiana e laplaciana, os espaços de escalas, a repre-

sentação log-polar, a transformada wavelets, o modelo de pirâmide com filtros direcionais

e multirresolução com fóvea móvel. Estes modelos buscam, assim como proposto por

Uhr, facilitar o processo de extração de feature ou diminuir a complexidade computacio-

nal exigida em tarefas como a extração e descrição de features.

2.2.1 Pirâmides Gaussiana e Laplaciana

O procedimento para gerar a pirâmide gaussiana é aplicar um filtro gaussiano (vide

Figura 2.1) na imagem original e realizar uma reamostragem da imagem suavizada. Ge-

ralmente são usadas amostragens com fator 2, ou seja, para construir o primeiro nível da

pirâmide gaussiana os pixels são reamostrados saltando de dois em dois na imagem sua-

vizada (horizontal e verticalmente), sendo este processo repetido para a criação de novos

níveis. Consequentemente, o tamanho de cada nível é metade da dimensão do anterior

como pode ser visto na Figura 2.2.

A construção da pirâmide laplaciana é realizada usando os níveis da pirâmide gaus-

siana. O primeiro nível da pirâmide laplaciana é dado pela diferença entre a imagem

original e sua resposta à filtragem gaussiana. No segundo, nível usamos a imagem re-

lativa ao segundo nível da pirâmide gaussiana e realizamos a diferença com a filtragem

gaussiana dela mesma, e assim sucessivamente. Quando chega ao topo da pirâmide la-

placiana, não tem mais como calcular a diferença porque a pirâmide gaussiana não tem


−2 0 2 4 6 −5

00

0.5

1

µ

0.8

0.80.6

0.6

0.60.6

0.4

0.4

0.4

0.40.4

0.2

0.20.2 0.2

0.2

0.20.2

µ

0 1 2 3 4−3

−2

−1

0

1

Figura 2.1: Função gaussiana bidimensional e sua curva de nível.

Figura 2.2: Pirâmide gaussiana.

mais camadas superiores. Isso indica o final da transformação, então, o nível de topo da

laplaciana recebe o topo da gaussiana. A Figura 2.3 apresenta uma transformação para

o espaço de pirâmide laplaciana. A partir desta figura, percebemos o destaque de bordas

(ou arestas) nos níveis da pirâmide laplaciana. Isso acontece devido à formalização ma-

temática do operador laplaciano, cuja função é dar destaque as mudanças de intensidade

do sinal fazendo uso da segunda derivada.


Figura 2.3: Pirâmide laplaciana.

2.2.2 Espaço de Escalas

A teoria de espaço de escalas nasceu da observação da representação dos objetos do

mundo real em imagens. É percebido que estes objetos aparecem em diversos níveis de

escalas. Este pensamento foi incorporado em um sistema de representação multiescala,

onde o parâmetro que determina a escala (σ) é inversamente proporcional à nitidez da

imagem.

Pode ser verificado na Figura 2.4 que todas as imagens, após a transformação, mantêm

a dimensão original, mas os elementos se espalham com o aumento do valor do parâmetro

σ. De acordo com Lindeberg (Lindeberg 1989), dentre as transformações lineares, o

núcleo gaussiano é o único capaz de gerar o espaço de escalas. O formalismo matemático

para esta técnica é apresentado em sua tese de doutorado (Lindeberg 1991).

2.2.3 A Representação Log-polar

Na década de 70, foram realizadas várias pesquisas usando animais como coelhos,

gatos, e macacos, com intuito de estudar o sistema de visão desses mamíferos. Com o


(a) σ = 1.0 (b) σ = 1.5

(c) σ = 2.0 (d) σ = 2.5

Figura 2.4: Espaço de escalas

resultado desses estudos, cientistas perceberam que a transmissão da informação entre a

retina e o córtex visual obedece, de certa forma, à lei logarítmica-polar. A definição deste

modelo representa os planos da retina e do córtex cerebral pelas variáveis z = x+ jy e

w = ξ+ jη, respectivamente. O mapeamento complexo log-polar é feito de acordo com

a Equação 2.1 (Traver & Bernardino 2009).

w = log(z) (2.1)


e as coordenadas de excentricidade e ângulo são obtidas pelas Equações 2.2 e 2.3, respec-

tivamente.

ξ = log(|z|) = log(√

x2 + y2) (2.2)

η = arg(z) = atan2(y,x) (2.3)

O resultado da aplicação da técnica log-polar pode ser verificado na Figura 2.5. A

Figura 2.5 mostra a representação no domínio log-polar e a reconstrução da imagem no

domínio do espaço, sendo esta última bastante semelhante as imagens geradas pelo nosso

sistema de visão, motivando cada vez mais seu uso na literatura.

Figura 2.5: Representação da imagem no domínio log-polar (imagem esquerda) e suareconstrução no domínio cartesiano (imagem direita).

2.2.4 A Transformada Wavelet

A decomposição (ou transformada) wavelet distingue-se dos outros modelos apresen-

tados devido à mudança do sinal bidimensional para o domínio de frequência. Por defini-

ção, determinar a transformada discreta de wavelets consiste em identificar os parâmetros


ck e d j,k na Equação 2.4, com k e j pertencentes ao conjunto dos números inteiros.

f (t) =∞

∑k=−∞

ckφ(t− k)+∞

∑k=−∞

∞

∑j=0

dk, jΨ(2 jt− k), (2.4)

Na Equação 2.4, φ(t) e Ψ(t) são as funções wavelets que representam o detalhe e a

escala. A partir delas podemos calcular filtros passa-alta e passa-baixa, respectivamente.

Através da combinação destes filtros podemos especificar a faixa de frequência do sinal

bidimensional (Mallat 1989). A base da transformada wavelet de Haar é a mais simples,

geralmente usada, mas outras bases, como por exemplo o laplaciano do gaussiano e a base

de Morlet, mais complexas, podem ser derivadas e aplicadas, desde que sejam atendidas

as restrições de ortonormalidade da base. Ou seja, as funções de base devem possuir

norma 1 (sua integral) e devem ser ortogonais entre si, quer dizer, como o produto interno

entre cada par de funções componentes igual a zero. A Figura 2.6 mostra um exem-

plo da transformada wavelet com 3 decomposições utilizando a transformada discreta de

wavelet (DWT, da sigla em inglês). Na Figura 2.6 são apresentadas a imagem real da

decomposição e uma imagem equalizada (para efeitos de visualização) com o resultado

da decomposição, respectivamente.

Figura 2.6: Decomposição da imagem utilizando a transformada wavelet (imagem es-querda) e equalização da decomposição (imagem direita).


Na Figura 2.6 da direita, pode ser observado que durante a primeira decomposição do

método, são geradas 4 imagens: a imagem original comprimida e as imagens de features

horizontais, diagonais e verticais. Para a segunda decomposição, a imagem comprimida

será decomposta em mais 4 novas imagens e assim sucessivamente, até que um nível

desejado seja atingido.

Este método é bastante explorado na compressão de vídeos, devido à facilidade de

reconstrução da imagem original fornecida pelos coeficientes de decomposição. A com-

pressão pode ser observada no resultado da decomposição, dado que a imagem original

passa a ser representada por 4 imagens de 1/4 do seu tamanho. No entanto, três dessas

imagens, as formadas pelas features, podem ser eficientemente comprimidas por possuí-

rem um range menor na determinação do valor do sinal, portanto usando menos bits para

representação dos valores.

2.2.5 Pirâmide com Filtros Direcionais

A pirâmide com filtros direcionais é proposta por Freeman e Adelson (Freeman &

Adelson 1991) e assemelha-se a uma variação da transformada wavelet. Neste modelo,

em cada nível, são utilizados filtros direcionais com orientações de 0, 45, 90 e 135 graus

(vide Figura 2.7). A aplicação desses filtros na imagem gera 4 novas imagens nas quais

aparecem ressaltados os contornos horizontais, diagonais de 45 graus, verticais e dia-

gonais de 135 graus, como pode ser observado na Figura 2.8. Este método também é

bastante utilizado para compressão de imagens (Adelson & Simoncelli 1987), pois as

imagens comprimidas podem ser combinadas com os 4 filtros para restaurar a imagem

original (veja a Figura 2.9).


(a) 0 graus (b) 45 graus (c) 90 graus (d) 135 graus

Figura 2.7: Filtros direcionais (Freeman & Adelson 1991, p. 16).

Figura 2.8: Pirâmide com filtros direcionais (Freeman & Adelson 1991, p. 16).

(a) Imagem original (b) Imagem reconstruída

Figura 2.9: Reconstrução da pirâmide com filtros direcionais (Freeman & Adelson 1991,p. 16).

2.2.6 Multicaracterísticas (ou Múltiplas Features) em Multirresolu-

ção (MRMF)

O método MRMF original, que serviu de base para o método MMF , é também inspi-

rado pela abordagem piramidal, usando a mesma ideia de que em um espaço de escalas


as características aparecem melhor realçadas em um determinado nível. Assim, a ideia é

também produzir uma estrutura em níveis de escala para facilitar a extração (abstração)

de features. Porém, distingue-se deste modelo no que diz respeito à dimensão dos dados

resultantes do seu processamento, pois gera imagens todas com exatamente o mesmo ta-

manho, no domínio de multirresolução. A Figura 2.10 mostra que o limite das regiões

em um nível no domínio do espaço são variantes, ao passo que as imagens no domínio

de multirresolução têm todas a mesma dimensão que a fóvea (nível de maior resolução).

São várias as abordagens para este esquema, sendo as principais descritas a seguir.

A ideia do esquema MRMF é mapear uma região inicialmente pequena da imagem

original, mas com a maior resolução possível, no nível de maior resolução da estrutura

transformada, a fóvea. No caso, a maior resolução possível é a mesma resolução da

imagem original, então, digamos, os 20×15 pixels centrais da imagem original compõem

este nível (se for usada uma fóvea com 20×15). Em seguida, deve-se tomar uma região

maior da imagem original, digamos, com o dobro das dimensões (se for usada a escala

2), ou 40×30, porém reduzindo a imagem resultante por algum processo de filtragem, de

forma que o resultado é uma imagem que tenha o mesmo tamanho da primeira (fóvea), no

caso de 20×15. Este processo é repetido aumentando-se o escopo da região na imagem

original até que no nível mais grosseiro da estrutura se tenha a imagem original toda

(digamos de tamanho 640×480, para o caso ilustrado) transformada (reduzida) para uma

imagem também de 20×15 pixels (resultando na resolução mais grosseira possível, mas

abrangendo toda a imagem original).

Note que este processo acarreta em perda de informação na periferia da imagem, uma

vez que a região de maior resolução abrange sempre a parte central da imagem, dimi-

nuindo a resolução para a periferia, o que seria de certa forma similar ao sistema visual

biológico. Assim, um robô com esse sistema de visão deve mover seus sensores visuais

(câmeras), realizando movimentos sacádicos, se desejar manter um objeto de interesse na

região de maior resolução. Para objetos que se movem no campo de visão, o processa-


mento em tempo real não é possível usando este modelo, pois a movimentação dos re-

cursos é onerosa, computacionalmente, e também biologicamente, uma vez que levamos

cerca de 80 a 200 milisegundos para realizar um movimento sacádico. Um movimento

sacádico em uma cabeça estéreo pode demorar até 500 milisegundos (Gomes et al. 2010).

Com o intuito de minimizar ou até resolver este problema, a inovação proporcionada

por Gomes, Carvalho & Gonçalves (2013) com o método MMF , como o próprio nome já

diz, justamente tenta evitar a realização de movimentos sacádicos, provendo mobilidade

à fóvea e economizando assim movimentos do sensor enquanto o objeto de interesse se

encontra na imagem (Bezerra 2006). Claro, isto só é possível de se realizar até que a

fóvea chegue a um limite dentro da imagem. Após isso o movimento deve ser realizado,

de qualquer maneira, para manter o objeto em questão na imagem.

Figura 2.10: Construção do domínio de multirresolução com MCMR (Bezerra 2006,p. 35).


2.2.7 Multirresolução com Fóvea Móvel (MMF)

O modelo de multirresolução com fóvea móvel (MMF) formalizado por Gomes et al.

(2008) pode ser compreendido fazendo-se uma analogia com uma pirâmide, onde o pico,

móvel, apresenta maior acuidade e a base uma resolução mais grosseira. Com esta abor-

dagem, é possível obter uma acuidade visual com boa resolução em qualquer parte da

imagem, desde que a fóvea seja posicionada (movida) para esta região. Gomes (2013)

demonstra que é possível reduzir o tempo de processamento utilizando o modelo MMF

sem prejudicar a eficácia das tarefas, desde que a fóvea seja propriamente controlada. As

subseções a seguir apresentam melhor a formalização dessa proposta.

Construção das camadas

A construção das camadas da pirâmide é o início do pré-processamento necessário

para a construção da estrutura MMF . Nesta construção de camadas, a imagem é mapeada

para um conjunto de k níveis, de tamanho W , com índices de 0 até m, onde m é o nível da

fóvea (vide Figura 2.12). Consideramos uma imagem I de tamanho U = (Ux,Uy), e para

cada nível k, delimitamos uma porção de tamanho S = (Sx,Sy) de I que será mapeada para

o domínio de multirresolução. Define-se que S0 = U e Sm = W , enquanto que os níveis

intermediários são obtidos através de interpolação, conforme a Equação 2.5. A Figura

2.11 apresenta as regiões da imagem no domínio espacial que serão transformadas para o

domínio de multirresolução.

Uma vantagem é que o armazenamento dos valores de um pixel no domínio de mul-

tirresolução não precisa ser necessariamente realizado. De fato, na tese de Gomes, as re-

giões determinam apenas onde e em quais escalas as features devem ser extraídas (Gomes

2013). Durante a implementação desta estrutura, não ocorre o armazenamento do domí-

nio de multirresolução, ou seja, durante a extração ou descrição das features não é feita

alocação de memória para as k imagens de tamanho W , porque a equação 2.5 já informa,

em I, a dimensão da porção que será processada.


Figura 2.11: Construção das camadas, adaptado de (Gomes et al. 2008, p. 20).

Figura 2.12: Construção dos níveis com o MMF.


Sk =mU +Wk− kU

m(2.5)

2.2.8 Movimento da fóvea

Em seu trabalho, Gomes define que a mobilidade da fóvea pode ser controlada através

de um vetor da fóvea F e que esta mobilidade pode ser realizada somente entre os limites

da imagem (Gomes 2013). Portanto, podemos definir que o vetor F , com origem no

centro da imagem I, está entre (W −U)/2 e (U −W )/2. Consequentemente, F = (0,0)

quando a fóvea é posicionada no centro de I.

Fazendo uso do vetor F , podemos definir a Equação 2.6, que indica a posição de início

de cada região, no domínio de espaço, que deve ser transformada. O nível em destaque na

Figura 2.13 mostra a escala que está sendo mapeada para o domínio de multirresolução,

e, como foi dito anteriormente, o vetor fóvea F sai do centro da imagem e aponta agora

para a região onde se encontra a fóvea.

δk =k(U−W +2F)

2m(2.6)

É mostrado no trabalho que o método MMF pode ser aplicado para rastreamento de

objetos, visão estéreo, matching entre duas imagens, reconhecimento e atenção visual,

provendo compressão da informação e garantindo a execução em tempo real. Além disso,

este modelo também foi estendido para o domínio 3D, para realização de reconhecimento

baseado no foveamento em nuvem de pontos (Gomes, Silva, Rocha, Aroca, Velho &

Gonçalves 2013).


Figura 2.13: Vetor de mobilidade da fóvea, adaptado de (Gomes et al. 2008, p.21).

Capítulo 3

Trabalhos relacionados

Do que pudemos verificar extensivamente, são encontrados poucos trabalhos na lite-

ratura implementando a técnica de multifoveamento. A Tabela 3.1 organiza esses estudos

de acordo com o ano de publicação, realçando detalhes de cada um deles. No trabalho de

Dario, a técnica de multifoveamento é explorada para a análise da disposição de sensores

piroelétricos e piezoelétricos em um sistema tátil (Dario et al. 1986). Para a realização

do trabalho, é empregada uma estrutura que inclui plataforma estática, emissor de infra-

vermelho e um dedo explorador. O sistema eletromecânico infere a posição e orientação

de um objeto posicionado na plataforma a partir de uma imagem binária gerada pelos

sensores. A pesquisa em questão busca analisar a precisão dos sensores distribuídos de

forma regular (ortogonal e hexagonal) e de forma não regular (fóvea e multifóvea), con-

siderando que todos os sensores tem o formato circular. O resultado da configuração

multifóvea mostra que os erros de cálculos de posição e orientação dos padrões não au-

mentam significativamente em relação às outras abordagens, porém não apresenta maior

precisão em relação às outras disposições.

O mapeamento log-polar foi utilizado por Lim para rastrear múltiplos objetos (Lim

et al. 1996). Nesse trabalho, a identificação do objeto é realizada através da divisão da

imagem log-polar em 4 regiões: região guardada, ativa, passiva e semi-visível. A região

guardada contém 4 pixels de raio no domínio cartesiano e serve para garantir que o objeto

rastreado não seja perdido, enquanto que a região ativa possui 97 pixels de raio, em do-

30 CAPÍTULO 3. TRABALHOS RELACIONADOS

mínio cartesiano, para detectar o tamanho, distância e o movimento dos objetos, e assim

definir qual objeto será foveado na próxima iteração. Após a detecção, a câmera é posici-

onada de tal forma que o centro do objeto esteja no centro da imagem. Além disso, este

objeto é identificado com uma tag que o distingue na cena. De acordo com os autores, as

regiões passiva e semi-visível, no domínio log-polar, não recebem nenhum processamento

porque suas informações não agregam desempenho ao método, ou seja, não há detecção

de features .

Para realizar o reconhecimento de objetos com diversas dimensões e singularidades,

Camacho implementou um algoritmo em Field Programmable Gate Array (FPGA) ba-

seado em pirâmide gaussiana, que suporta múltiplas fóveas (Camacho et al. 1998). Para

isso, são definidos fatores de subdivisão em cada lado da fóvea para a construção dos

níveis da estrutura . Os níveis são referenciados pela origem ou canto superior esquerdo e

são delimitados através de uma relação entre a mínima subdivisão do nível e a subdivisão

em cada lado da fóvea. Com a fóvea definida, são realizados os cálculos dos fatores de

subdivisão laterais necessários para criação dos níveis inferiores da pirâmide. De acordo

com Camacho, o multifoveamento é realizado pela reexecução deste procedimento e apre-

senta como vantagem a possibilidade de processamento paralelo para as várias regiões de

interesse . Em seu trabalho, é exposta uma aplicação que relaciona os últimos níveis de di-

ferentes regiões de interesse, antes de serem gravados em memória, através do algoritmo

temporal de diferenças de valores absolutos (AV D) para gerar uma máscara contendo as

regiões de movimento detectadas.

Em estudos sobre a atenção visual, é realizada a extração de features de baixo ní-

vel, como cores, movimento, orientações e intensidade, para a criação de um mapa de

saliências, semelhante aos dados de movimentações dos olhos humanos, explorando a

abordagem multifoveada de compressão de vídeo (Dhavale & Itti 2003). No trabalho em

questão, são avaliadas duas abordagens de foveamento, a primeira é baseada em objeto

e a segunda em localização. A metodologia empregada nesse trabalho é a replicação do

31

método de pirâmide gaussiana para cada fóvea. Através da ponderação do valor da menor

saliência e da menor distância do ponto ao objeto, é gerado um valor que define qual saída

da pirâmide será utilizada para compor a imagem multifoveada. É apontado no artigo que

o grande defeito dessa metodologia é que os frames são calculados e após a mudança da

fóvea aparecem suavizados. Os resultados apresentam uma taxa de compressão de 1,8

sem uma deterioração perceptível da qualidade. Também é verificado que a abordagem

de localização apresenta maior compressão do que a baseada em objetos.

A compressão com perdas de dados pode ser implementada considerando a técnica de

resolução variável cartesiana (CV R, da sigla em inglês) (Basu & Wiebe 1998). O CV R

é capaz de manipular o formato da fóvea pela variação dos fatores de escala horizontal e

vertical, dependendo da posição da fóvea. Quando é realizada a inserção de mais regiões

de interesse, é necessário definir quando se deve reduzir a resolução ao redor da fóvea

para compensar ou se deve reter a informação adicional reduzindo a taxa de compressão.

Para resolver este problema, Basu e Wiebe propõem duas abordagens, sendo a primeira

cooperativa e a segunda competitiva. Na abordagem cooperativa, todas as fóveas contri-

buem para calcular a localização do ponto na imagem transformada. O problema dessa

estratégia é que são geradas linhas visuais entre as fóveas com a mesma resolução da

fóvea, enquanto que na abordagem competitiva as fóveas competem para calcular a posi-

ção de um ponto da imagem. A fóvea mais próxima do ponto em análise determinará a

sua localização. Esta técnica é incorporada a uma aplicação de videoconferência e obtém

valores de taxa de compressão acima de 98% com a codificação entre frames.

Em aplicações como rastreamento, segurança e supervisão de tráfego, é necessá-

rio prover qualidade da informação em um amplo campo de visão, porém, isso requer

maior recurso de rede. Rodríguez et al. (2002) propôs realizar a compressão das informa-

ções estáticas do vídeo e realizar a transmissão a taxas diferentes para resoluções distin-

tas (Rodríguez et al. 2002). Para isso, foi usado o método cartesiano exponencial (SFMG)

com estimadores de deslocamento, com a intenção de escolher as regiões de interesse e

32 CAPÍTULO 3. TRABALHOS RELACIONADOS

relacioná-las entre os frames. O multifoveamento é conseguido pela sobreposição das

estruturas, separadamente. A transmissão da estrutura é realizada garantindo maior pri-

oridade para os níveis próximos da fóvea. Na recepção da informação visual, as regiões

que não foram recebidas são reaproveitadas de pacotes anteriores podendo acarretar num

problema, quando o deslocamento é grande e a banda da rede é limitada à região da fó-

vea. Neste caso, a fóvea apresenta uma parte da informação da camada anterior. Uma

proposta para solucionar este problema é enviar uma fóvea que englobe todo o movi-

mento. De acordo com os autores a principal vantagem do método é garantir a qualidade

do alvo mesmo com uma banda de rede variável.

O modelo de foveamento que utiliza a variação espacial do sistema de visão humano

nasceu por meio da definição de um limiar de contraste (CT ) encontrado pela função

da frequência espacial e da excentricidade retinal. Através deste CT é possível definir

uma frequência de corte ( fc), ou seja, uma frequência que delimita o que é visível. A

ideia deste método proposto por Sankaran é filtrar as imagens de acordo com a frequência

fc previamente definida (Sankara et al. 2005). A extensão do modelo foveado para o

multifoveamento é realizada incorporando mais fc ao sistema. O algoritmo proposto

extrai sequencialmente cada frame do vídeo, realiza uma subtração com o background

da cena e aplica um limiar (threshold) para encontrar a posição aproximada do objeto,

divide o frame em vários blocos de mesmo tamanho e para cada bloco define uma flag

de existência do objeto, realiza o foveamento no centro de cada bloco com a flag setada

e mistura todos os blocos foveados baseados na seletividade da frequência. Este método

pode ser implementado no domínio espacial com complexidade O(n2) e no domínio DCT

com complexidade O(1), onde n é o número de possíveis distâncias de visualização.

O estudo sobre a combinação da utilização do foveamento adaptativo de multipontos

definido por Sankaran (Sankara et al. 2005) com o reuso da informação de alta resolução

com o objetivo de produzir vídeos com uma qualidade comparável ou superior aos demais

métodos de compressão (Pioppo et al. 2006). A qualidade é avaliada por meio da métrica

33

do índice de similaridade estrutural (SSIM) bem como pela relação sinal-ruído de pico

tradicional (PSNR). Porém, o PSNR não é uma boa métrica, porque o multifoveamento

apresenta distorções nos frames. Os autores notam que a qualidade da informação diminui

quando a fóvea se afasta. Então, a ideia é reutilizar as informações de qualidade do frame

anterior ao movimento. Para aplicar esta estratégia, são definidos dois limiares, o primeiro

é responsável por detectar o movimento e o segundo por detectar ausência de mudanças

do background da cena. Se a soma de diferenças absolutas (SAD) entre os frames anterior

e atual exceder o limiar de movimento, ele é foveado e se for menor que o segundo limiar

ou da média entre o SAD anterior e atual, então o bloco não é foveado. Este método

apresenta um ganho de compressão de 2,25 a 11% sem degradar a qualidade de forma

perceptível.

Após a análise da literatura, constatamos que o multifoveamento pode ser aplicado

em diversos contextos através da replicação de uma estrutura de multirresolução. Todos

os trabalhos citados, desenvolvidos em software, utilizam a extração de features de movi-

mento para inferir conhecimento sobre o contexto. Dentre esses trabalhos, existem alguns

que realizam o multifoveamento em tempo real, mas para fazer isso utilizam hardware de-

dicado (uma FPGA) para permitir o processamento paralelo. A replicação provoca uma

interseção entre os níveis das fóveas se não forem tratadas anteriormente e os únicos tra-

balhos da literatura que tratam essa redundância de informação são Camacho (Camacho

et al. 1998) e Rodríguez (Rodríguez et al. 2002).

Nos dois trabalhos, as fóveas são processadas separadamente dos anéis, níveis da

estrutura foveada sem a fóvea, para eliminar o processamento redundante. A solução

proposta por Camacho (Camacho et al. 1998), de separar a fóvea da estrutura acaba sendo

paliativa, porque entre os anéis ainda existe redundância de informação. O diferencial

a mais do método proposto nessa dissertação é a identificação de toda a redundância

existente para replicação da estrutura foveada.

34C

APÍT

UL

O3.

TR

AB

AL

HO

SR

EL

AC

ION

AD

OS

Trabalho Metodologia Contexto Implementação Multifóveas Features Real-time Domínio(Dario et al. 1986) Espaço variante Reconhecimento Hardware Sim Sim Não Espacial(Lim et al. 1996) Log-polar Tracking Software Sim Sim Sim Espacial

(Camacho et al. 1998) Pirâmide Gaussiana Tracking Software Sim Sim Sim Espacial(Basu & Wiebe 1998) Resolução Variável Cartesiana Compressão Software Sim Sim Sim Espacial

(Rodríguez et al. 2002) Cartesiano exponencial Compressão Software Sim Sim Não Espacial(Dhavale & Itti 2003) Pirâmide Gaussiana Atenção visual Software Sim Sim Não Espacial

(Sankara et al. 2005) Multipontos Adaptativo Compressão Software Sim SimNão EspacialSim Frequência

(Pioppo et al. 2006) Multipontos Adaptativo Compressão Software Sim SimNão EspacialSim Frequência

Tabela 3.1: Trabalhos relacionados à técnica de multifoveamento

Capítulo 4

Problemática

O propósito deste capítulo é oferecer uma visão geral sobre o problema que ocorre du-

rante a extração de features em uma abordagem multifoveada que utiliza a reexecução do

método MMF . Primeiramente, estendemos o formalismo do MMF para múltiplas fóveas.

Em seguida, é apresentada a solução proposta para resolver o problema em questão.

4.1 Região de interseção entre níveis

No processo de extração de features, o método MMF especifica a região, no domínio

de espaço, onde deverá ser realizada a extração. Esta região é dada em função do nível

k através das equações de δk e Sk definidas nas Equações 2.6 e 2.5, respectivamente.

Gomes (Gomes 2013) propõe um algoritmo para extração de feature do tipo SURF com

o método MMF que utiliza as equações de δk e Sk para delimitar a região de extração em

cada escala.

O método MMF transforma uma imagem no domínio espacial em m imagens com a

mesma dimensão da fóvea. Considerando que esse modelo seja aplicado para n estruturas,

todas com o mesmo número de níveis m e o mesmo valor para W , definimos como P um

conjunto de pares ordenados através da Equação 4.1. Dessa forma, P é formado por todos

os valores de δk, j e Sk, j, onde o δk e Sk são todas as delimitações do nível k para a estrutura

j. Além disso, o índice n que aparece na Equação 4.1 representa o número de fóveas da

36 CAPÍTULO 4. PROBLEMÁTICA

estrutura multifoveada.

P = {(δk, j,Sk, j)|k ∈ [0,1, . . . ,m]∧ j ∈ [1,2, . . . ,n]} (4.1)

Aplicando o método MMF para uma fóvea f de tamanho W = (Wx,Wy) posicionada

em (x1,y1) com k = m níveis, é gerada uma quantidade de m elementos em P garantindo

uma cardinalidade |P| = m. Na inserção da segunda fóvea g de tamanho W posicionada

em (x2,y2) com m níveis são obtidos mais m pares ordenados no conjunto P. Em um caso

particular, se verificarmos que a distância euclidiana entre as posições das fóveas é igual

a zero, então P contém 2m elementos devido à criação de mais m imagens no domínio

de multirresolução, porém |P| = m, pois os elementos obtidos pela primeira fóvea são

iguais aos obtidos pela segunda fóvea. Portanto, o domínio de multirresolução apresenta

m regiões e m réplicas. Caso isto não aconteça, podemos garantir a replicação de no

mínimo uma região no domínio de multirresolução, a qual ocorre no primeiro nível das

duas fóveas, visto que S0,i =U e δ0,i = (0,0), qualquer que seja i, por definição do modelo

MMF .

A Figura 4.1 ilustra um exemplo de interseção entre duas regiões do mesmo nível de

fóveas diferentes (o índice deste nível será omitido por simplificação), onde: δ1 = (1,9),

δ1 + S1 = (6,4), δ2 = (4,6), δ2 + S2 = (9,1). Lembre-se de que em P são armazenadas

somente as informações de início (δ) e tamanho (S) de cada região. Sabendo que a ex-

tração de features é realizada no domínio de multirresolução, podemos concluir que as

features que estão nessas regiões de intersecção serão duplicadas. Diante desses fatos,

percebemos a desvantagem computacional do método MMF para a criação de múltiplas

fóveas utilizando a abordagem de reexecução do método.

É possível determinar interseções entre as regiões definidas em P: (1) entre regiões

de níveis diferentes de uma mesma fóvea (Camacho et al. 1998), (2) entre regiões de um

mesmo nível para fóveas diferentes e (3) entre regiões de níveis diferentes entre fóveas

4.2. DISPOSIÇÃO DAS INTERSEÇÕES 37

δ1x

δ1 y

δ1x +S1x

δ1 y+

S 1y

δ2x

δ2 y

δ2x +S2x

δ1 y+

S 2y

Figura 4.1: Intersecção entre elementos de P2.

distintas. É de interesse desta pesquisa, especificamente, o segundo tipo de interseção,

o qual será o único a ser analisado adiante. Isso se deve ao fato de que, no contexto

dos trabalhos desenvolvidos no modelo MMF , níveis diferentes, seja da mesma fóvea

ou não, processam informações de escalas diferentes e, portanto, não há redundância na

computação, entre eles.

4.2 Disposição das interseções

Na seção anterior foi apresentado o problema que ocorre durante a extração de fe-

atures de múltiplas fóveas no domínio de multirresolução. Uma possível solução para

este problema é a identificação das regiões de interseção no domínio de multirresolução

e evitar a extração redundante de features. A Figura 4.2 mostra quais são as disposições


possíveis de regiões de interseção entre duas fóveas.

Figura 4.2: Disposições das regiões de interseção entre duas fóveas

As regiões preenchidas com a cor azul na Figura 4.2 foram processadas pela fóvea

f . A primeira linha da figura mostra todas as situações quando a coordenada x de f for

menor que a coordenada x da fóvea g. A linha de figuras do meio ilustra todas as situações

quando a coordenada x é igual para as duas fóveas e a terceira quando a coordenada x de

f for maior que a coordenada x de g

As regiões preenchidas com a cor verde claro na Figura 4.2 são as regiões de g que não

tem interseção com f . Note que nem todas dessas regiões são convexas, o que dificulta

a sua representação com apenas duas variáveis em P. Para garantir que todas as regiões

sejam representadas apenas por δ e S é necessário quebrar as regiões não convexas em

4.3. IDENTIFICAÇÃO DO VÉRTICE DE INTERSEÇÃO 39

regiões retangulares. Quando todas as regiões preenchidas com verde claro forem trans-

formadas em regiões convexas podemos armazenar em P assegurando que não existirá

extração redundante de features.

A região de interseção entre duas fóveas f e g é definida como o produto cartesiano:

Ix× Iy, onde Ix e Iy são definidas pelas Equações 4.2 e 4.3. Estas equações representam

o intervalo, em cada componente, que delimitam a região de interseção do nível k entre

duas fóveas i e j.

Ix = [δk,i,x,δk, j,x +Sk, j,x] (4.2)

Iy = [δk,i,y,δk, j,y +Sk, j,y] (4.3)

4.3 Identificação do vértice de interseção

A região de interseção em cada nível da estrutura MMF pode ser melhor visualizada

através da sobreposição das porções dos níveis da estrutura no domínio de espaço. Na

Figura 4.3 são ilustradas duas fóveas f e g geradas, respectivamente, a partir do método

MMF quando k→∞, que se diferenciam em suas poses. Nessa figura, a parte mais escura

entre as estruturas indica a região de interseção entre as duas fóveas.

Percebemos pela análise da Figura 4.3 que a área ocupada pela região de interseção

aumenta quando as duas fóveas se aproximam e diminui quando as fóveas se afastam.

Consequentemente, para identificar as regiões de interseção a cada nível das estruturas,

faz-se necessário uma nova formalização matemática para o método MMF , que utilize a

disposição das fóveas e considere as estruturas com a mesma quantidade de níveis.


fg

x

y

z

Figura 4.3: Interseção entre duas estruturas fóveadas com o MMF .

4.3.1 Formalismo matemático

O método MMF determina as regiões de cada nível da fóvea a partir das equações 2.6

e 2.5, as quais definem uma região retangular de 4 vértices, fazendo uso da técnica de

interpolação linear entre a imagem original e a fóvea (Gomes 2013). A projeção no plano

xz ou yz de cada uma das regiões retangulares ao longo de todos os níveis está contida em

uma reta (vide Figura 4.4), ou seja, a estrutura MMF pode ser representada nos planos

através de três segmentos de retas que indicam seu contorno.

f

x

y

z

Figura 4.4: Projeção (linhas em azul) dos vértices das regiões no plano yz. Cada vértice,ao longo dos níveis, projeta um segmento de reta.


A Figura 4.5 apresenta duas disposições de projeções das fóveas A e B no plano xz,

onde a e b representam as projeções dos centros das fóveas, respectivamente. As pro-

jeções a e b podem representar tanto a projeção do componente x da primeira fóvea ( f )

como da segunda (g). Na Figura 4.5 (a), se a é a componente x de projeção da segunda

fóvea (gx), então a posição inicial/final da região de interseção à nível de projeção (vér-

tice de interseção), ou seja, o início/fim do processamento sem interseção é a posição ua,

caso contrário ub. De forma análoga ocorre na Figura 4.5 (b). Observe que a variável w

representa as dimensões das fóveas projetadas, contém a mesma quantidade de níveis m

para ambas fóveas e a dimensão da imagem original na componente x é representada por

Ux. Além disso, a partir das Figuras 4.5 (a) e (b) podemos perceber que p1 representa o

limite mais distante da origem de projeção no plano xz entre as projeções a e b. Enquanto

que p2 corresponde ao limite mais próximo da origem da projeção entre as projeções a e

b.

0 Ux

a bm

p2

w

p1

w

k

ua ub x

z

δk,bx δk,ax +Sk,ax

(a) b− w2 > a+ w

2

0 Ux

a bm

p1

w

p2

w

k

ua ub x

z

δk,bx δk,ax +Sk,ax

(b) b− w2 < a+ w

2

Figura 4.5: Disposições de duas fóveas projetadas no plano xz.

A partir da definição da componente x da interseção definida pela Equação 4.2 po-

demos deduzir equações que definem ua e ub dependendo das disposições das fóveas na

componente x. Observando a Figura 4.5 (a) temos que ua é exatamente a componente x de

δk,b (vide Equação 4.4) e ub é a componente x de δk,a +Sk,a (vide Equação 4.12). Sendo


assim, podemos deduzir expressões para ua e ub que represente essa distribuição.

ua = δk,bx (4.4)

Considerando a Equação 2.6 definida por Gomes (2013) e substituindo na Equação 4.4

obtemos a Equação 4.5. Colocando o k em evidência e dividindo os termos do numerador

pelo 2 do denominador chegamos a Equação 4.7.

ua =kUx− kw+2kB

2m(4.5)

ua =k(Ux−w+2B)

2m(4.6)

ua =k(B+ Ux−w

2 )

m(4.7)

Ainda simplificando a expressão podemos renomear uma parte da Equação 4.7 para

a variável p1 (vide Equação 4.9) como pode ser observada na Equação 4.8. De acordo

com Gomes, Carvalho & Gonçalves (2013), temos que: B = b− Ux2 e substituindo essa

informação na Equação 4.9 obtemos a Equação 4.11 que representa a simplificação da

variável p1.

ua =kp1

m(4.8)

p1 = B+Ux−w

2(4.9)

p1 = b−Ux

2+

Ux−w2

(4.10)

p1 = b− w2

(4.11)

Como citado anteriormente, a partir da análise da Figura 4.5 (a) inferimos que ub é

exatamente a componente x de δk,a +Sk,a apresentada na Equação 4.12.


ub = δk,ax +Sk,ax (4.12)

Fazendo uso das Equações 2.6 e 2.5 e multiplicando por 22 a equação de Sk,ax , encon-

tramos a Equação 4.15, que após uma simplificação e organização dos termos pode ser

representada pela Equação 4.18.

ub =kUx− kw+2kA

2m+

mUx− kUx + kwm

(4.13)

ub =kUx− kw+2kA

2m+

mUx− kUx + kwm

(22

)(4.14)

ub =kUx− kw+2kA

2m+

2(mUx− kUx + kw)2m

(4.15)

ub =2mUx−2kUx +2kA+2kw− kw+ kUx

2m(4.16)

ub =2mUx−2kUx +2kA+ k(Ux +w)

2m(4.17)

ub =mUx− kUx + kF +

k(Ux+w f )2

m(4.18)

De forma similar a simplificação anterior, renomeamos uma parte da expressão para

a variável p2 (vide Equação 4.20), obtendo assim a Equação 4.19. A variável p2 foi

reduzida utilizando A = a−Ux/2 para resultar na Equação 4.22.

ub =mUx− kUx + kp2

m(4.19)

p2 = A+(Ux +w)

2(4.20)

p2 = a−Ux

2+

(Ux +w)2

(4.21)

p2 = a+w2

(4.22)

Ao realizar os mesmo procedimentos para a Figura 4.5 (b) encontramos as mesmas


equações descritas acima. Verifique na Figura 4.5 que a identificação do vértice de inter-

seção depende das disposições das fóveas. Sendo assim, é importante definir se a fóvea

g se encontra próximo ou distante da origem em relação a fóvea f . Para fazer isso, é

necessário verificar os limites de projeção de cada fóvea das Figuras 4.5 (a) e (b). Fa-

zemos isso através da análise de uma condição definida pelas Equações 4.23 e 4.24, que

indicam qual a fóvea está distante (vd) ou próximo (vp) da origem na componente u no

plano uz. Considere que fu e gu são as projeções dos centros das fóveas f e g em u, onde

u representa as componentes x ou y nos planos de projeção.

vd =

(max

[max( fu,gu)−

w2,min( fu,gu)+

w2

],m

)(4.23)

vp =

(min

[max( fu,gu)−

w2,min( fu,gu)+

w2

],m

)(4.24)

Lembre-se que a e b são as projeções centrais das fóveas. Consequentemente, se

g± w2 = vd , temos que ua representará a interseção da fóvea f em g. Caso contrário, ub

representará essa interseção.

O uso das Equações 4.8 e 4.19 geram um problema quando k = 0, pois ua ou ub

acaba aparecendo tanto na origem quanto na extremidade da projeção. Para resolver esse

caso especial, é necessário adicionar uma nova equação ao sistema, de tal forma que para

todo índice k = 0 a interseção é toda a imagem, visto que a base é comum. Note que há

simétria entre as projeções dos planos xz e yz. Portanto, as equações encontradas para

o plano xz podem ser utilizadas adequando os parâmetros para o plano yz. Desta forma,

nosso sistema é apresentado pela Equação 4.25, sendo este capaz de representar todas

as interseções entre duas estruturas foveadas dependente dos níveis e da disposição das

fóveas.

4.4. VETOR DE DIREÇÃO DAS REGIÕES 45

u f∩g =

U, se k = 0

Um−Uk+kp2m , se gu± w

2 = vp

kp1m , se gu± w

2 = vd

(4.25)

vd =

(max

[max( fu,gu)−

w2,min( fu,gu)+

w2

],m

)(4.26)

vp =

(min

[max( fu,gu)−

w2,min( fu,gu)+

w2

],m

)(4.27)

4.4 Vetor de direção das regiões

A Equação 4.25 retorna somente o vértice de interseção em cada nível. Porém, pre-

cisamos definir, além dos componentes do vértice de interseção, a direção da região de

interseção entre as duas fóveas. Para tal, consideramos a diferença entre as posições cen-

trais de cada nível das fóveas f e g e consideramos as variações em x e y para definir a

posição de f em relação a g. A Figura 4.6 mostra um exemplo desse vetor direcional.

A partir desse vetor, um ponto colateral (nordeste, sudeste, noroeste ou sudoeste) é

atribuído de acordo com a menor distância angular. Se o vetor for paralelo a um dos eixos

(norte-sul, leste-oeste), então há dois pontos colaterais mais próximos e qualquer um deles

pode ser escolhido. A Tabela 4.1 apresenta um exemplo de definição de direções das

regiões de acordo com a variação dos termos ∆x e ∆y. Após a análise da tabela, notamos

que cada linha representa uma das possíveis configurações apresentada pela Figura 4.2 e

que as cinco últimas linhas desta tabela pode ser definida de acordo com a implementação

do algoritmo. Para o desenvolvimento deste trabalho foi considerada a Tabela 4.1 como

referência para determinar as direções entre as regiões.


f

g

∆x

∆y

O x

y

Figura 4.6: Vetor que define a direção da região eliminada, sendo esta construída a partirdas informações centrais de cada região.

4.5 Conjunto de regiões sem interseção

Considerando todas as regiões de um mesmo nível, obtidas em P, as quais podem

conter interseção entre si, propomos um algoritmo para obtenção de um novo conjunto de

regiões Q que representa a união de todas essas regiões, do mesmo nível, sem interseções.

A ideia para obtenção dessas regiões consiste em, para cada nível de cada uma das fóveas,

obter um conjunto de regiões retangulares que representa a região desse nível, possivel-

mente não convexa, uma vez eliminadas as interseções com as regiões do mesmo nível

das demais fóveas. Esse conjunto de regiões é então adicionado ao conjunto de regiões

Q.

Para tal finalidade, para cada nível, são calculados os vértices de interseção que estão

dentro da região analisada (vide Figura 4.7) e as direções das regiões de interseção (vide

4.6. EXTRAÇÃO MULTIFOVEADA DE FEATURES 47

∆x ∆y Direçãopositivo positivo Nordestepositivo negativo Sudestenegativo positivo Noroestenegativo negativo Sudoeste

zero positivo Nordestezero negativo Sudeste

positivo zero Sudestenegativo zero Sudoeste

zero zero -

Tabela 4.1: Tabela de exemplo da definição do vetor de direção entre as regiões, levandoem consideração a variação nas coordenadas x e y.

Figura 4.8). Seja t o número de vértices de interseção, a região do nível em questão

é dividida em até t + 1 regiões retangulares tendo como referência a abscissa de cada

vértice, conforme exemplificado na Figura 4.9. A cada iteração, o algoritmo altera o

tamanho das extremidades das regiões e, ao final do algoritmo, essas regiões representam

o conjunto de regiões sem redundâncias (vide Figura 4.10).

Para fazer isso, são considerados dois vetores unidimensionais com o tamanho t +1,

onde o primeiro é de máximos e o segundo de mínimos. O vetor de máximo armazena as

maiores ordenadas dos vértices de cada uma dessas regiões e o vetor de mínimo armazena

as menores. Portanto, o primeiro é inicializado com o valor de δk, enquanto que o segundo

é inicializado com os valores de δk +Sk do nível k em análise. O Algoritmo 1 demonstra

como deve ser realizada a implementação desta ideia. Esse algoritmo exige que antes de

sua execução seja feita a ordenação prévia dos vértices de interseção na ordem crescente

garantindo que a direção entre as regiões não seja perdida.

4.6 Extração multifoveada de features

O Algoritmo 1 pode ser facilmente incorporado ao código do método MMF utilizando

uma das duas abordagens de processamento:


Algoritmo 1: Algoritmo de eliminação das regiões de interseção entre níveis.Entrada: Vértices de interseções (xi,yi), onde i ∈ [0, . . . , t−1]; Vetor de direção

dos vértices di, onde i ∈ [0, . . . , t−1]; Vetor de máximos (v) de dimensãot; Vetor de mínimos (u) de dimensão t

Saída: Construção do conjunto Q1 para cada vértice i de interseção faça2 se di == noroeste então3 v[ j] = min(v[ j],yi), para j ∈ [0,1, ..., i];4 senão5 se di == nordeste então6 v[ j] = min(v[ j],yi), para j ∈ [i+1, ..., t];7 senão8 se di == sudeste então9 u[ j] = max(u[ j],yi), para j ∈ [i+1, ..., t]

10 senão/* di == sudoeste */

11 u[ j] = max(u[ j],yi), para j ∈ [0,1, . . . , t]12 fim13 fim14 fim15 fim16 Q← v,u;17 retorna Q;


P1

P2P3 P4

P5

P6

Figura 4.7: Exemplo de distribuição de vértices de interseção dentro de uma imagem.

Figura 4.8: Exemplo de direção das regiões que devem ser eliminadas.

Figura 4.9: Exemplo de divisão do nível em regiões verticais.


Figura 4.10: Exemplo de nível com regiões de interseção eliminadas.

• Verificação pixel a pixel

• Envio de blocos de regiões sem redundância

Na primeira abordagem, o algoritmo para extração de features SURF realiza a cada

pixel da região uma consulta ao conjunto Q com intuito de verificar se o pixel está em uma

das regiões que ainda não foram processadas. Desta forma, havendo x fóveas já processa-

das serão necessárias, no pior caso, x+1 verificações no conjunto Q. Esta busca pode ser

substituída para verificar se o pixel não está em nenhuma das regiões processadas garan-

tindo, no pior caso, x verificações. A vantagem da primeira busca, em Q, é que pode ser

realizada entre 0 e x+1 verificações dependendo do posicionamento das fóveas, enquanto

que na segunda exige as x verificações. Por outro lado, a primeira busca necessita de um

pré-processamento para encontrar as regiões não processadas. A partir disso são gerados

dois questionamentos: é melhor ter (1) o custo de descobrir as regiões não processadas

para ter entre 0 e x+ 1 verificações por pixel ou (2) ter exatamente x verificações por

pixel?

Em relação à segunda abordagem, envio de blocos, todas as regiões em Q serão pro-

cessadas individualmente, ou seja, cada par ordenado do conjunto Q é considerado uma

região de processamento para o SURF . O desempenho computacional proporcionado por

esta abordagem é superior à verificação pixel a pixel. Por exemplo, imagine 10 fóveas


em uma imagem 640×480 e 10 regiões no mesmo nível com tamanho 120×90 gerando

|Q|= 10; na primeira abordagem todos os pixels do nível são percorridos e verificados 10

vezes no conjunto Q, mesmo que seja verificado que boa parte dos pixels já foram proces-

sadas, perde-se tempo nessa verificação ( 120× 90× 10/samplestep2 pixels); enquanto

que na segunda abordagem já teremos um conjunto de regiões retangulares que na pior

das hipóteses totalizam o tamanho da própria imagem ( 120× 90/samplestep2 pixels).

Este exemplo pode ser ampliado para infinitas fóveas, provando a eficiência da segunda

abordagem.

Capítulo 5

Implementação

Neste capítulo, são apresentados os detalhes das implementações realizadas visando

estender o método MMF para suportar múltiplas fóveas. Para tal, foi necessário realizar

modificações no algoritmo para extração de features, tal como SURF , como proposto no

trabalho de Gomes (Gomes 2013).

5.1 Biblioteca de visão computacional e reuso de códigos

Para estender o trabalho de Gomes (Gomes 2013) foi necessário utilizar a biblioteca

OpenCV na sua Versão 2.4.9 e o método MMF disponível no repositório foveatedFea-

tures 1 do GitHub. A Versão 2.4.9 da biblioteca OpenCV foi necessária porque o mé-

todo proposto por Gomes utiliza algumas funções que tiveram seus headers modificados

nas novas versões da biblioteca. A atualização da biblioteca para a versão corrente do

OpenCV não é de fundamental importância para a realização deste trabalho e pode ser

realizada posteriormente sem nenhum prejuízo ao método proposto.

Para a implementação neste trabalho, realizamos uma bifurcação (fork) do repositó-

rio foveatedFeatures 2 no GitHub. Este procedimento é utilizado buscando conservar a

identidade dos códigos de Gomes. A utilização da bifurcação é bastante explorada nas

1O projeto de extração de features a partir de imagens foveadas é open source e está disponível no link:https://github.com/rafaelbes/foveatedFeatures.git.

2Disponível no link: https://github.com/petrucior/foveatedFeatures.git.

54 CAPÍTULO 5. IMPLEMENTAÇÃO

contribuições da comunidade open source, visto que cada bifurcação tem uma vida pró-

pria que apenas é agregada ao projeto principal com a aceitação do administrador do

repositório principal.

5.2 A estrutura multifoveada

A implementação da estrutura multifoveada é realizada a partir de uma interface que

armazena as estruturas MMF em uma lista. Cada estrutura foveada é configurada e ar-

mazenada em um nó da lista (vide Figura 5.1). Esta configuração exige como argumento

um arquivo com o objetivo de definir as porções de cada nível da estrutura foveada, para

construir o conjunto Q, sendo este conjunto a união de todas as regiões de processamento

de um mesmo nível sem interseções, fazendo uso da Equação 4.25. A configuração de

cada fóvea considera todas as fóveas que foram processadas anteriormente, exigindo que

a Equação 4.25 seja utilizada entre a fóvea atual e cada uma das fóveas previamente inse-

ridas ao sistema multifoveado.

Fóvea 1 Fóvea 2

analisa

Fóvea 3

analisa

analisa

. . .

Figura 5.1: Organização das fóveas na interface multifoveada.

A Figura 5.1 mostra como a estrutura multifoveada é organizada em forma de lista.

Além disso, são apresentadas setas pontilhadas que representam a verificação das interse-

ções com as fóveas anteriormente processadas. Observe o terceiro nó da lista, que contém

a estrutura da terceira fóvea, e verifique que há duas setas pontilhadas, uma para o segundo

e a outra para o primeiro nó da lista. Estas setas indicam que para processar a estrutura

da Fóvea 3 e eliminar as informações redundantes é necessário analisar a disposição das

Fóveas 1 e 2.

5.2. A ESTRUTURA MULTIFOVEADA 55

5.2.1 Configuração das estruturas do sistema multifoveado

Como citado anteriormente, cada nova estrutura foveada inserida verifica sua interse-

ção com as demais estruturas já incorporadas ao sistema. Este procedimento é realizado

através da análise da Equação 4.25, em cada nível, nos pares formados com a fóvea inse-

rida e todas as estruturas já processadas.

Algoritmo 2: Algoritmo de identificação dos vértices de interseção.Entrada: U : dimensão da imagem, k: nível em análise; m: quantidade de níveis;

w, f1u e f2u: dimensão e as componentes da posição centralSaída: v: detectando o vértice de interseção

1 para cada nível k de f faça2 p1← max

[max( f1u, f2u)− w

2 ,min( f1u, f2u)+ w2

]p2← min

[max( f1u, f2u)− w

2 ,min( f1u, f2u)+ w2

]3 se k == 0 então4 v←Uk5 senão6 se f2u± w

2 == p2 então7 v← Um−Uk+kp2

m8 senão9 v← kp1

m10 fim11 fim12 fim13 retorna v;

O Algoritmo 2 gera os vértices de interseção entre duas fóveas. Porém, somente os

vértices não informam para onde a região está deslocada. Este problema foi resolvido

adicionando um vetor de direção entre a fóvea atual e a processada anteriormente. Após

toda esta análise, os níveis da nova estrutura terminam sendo reorganizados como vá-

rias regiões convexas (vide Figura 4.10) com o Algoritmo 1 eliminando redundâncias de

informação.


5.2.2 Incorporação ao método MMF

As regiões convexas geradas na Subseção anterior são representadas através de δ e S e

podem ser incorporadas ao SURF através de duas abordagens: (1) verificar se cada pixel

está dentro de alguma região sem interseção e (2) enviar toda a região sem interseção para

ser processada. Estas duas abordagens são incorporadas ao Algoritmo 3, construído de

forma genérica para a seleção foveada de features (Gomes 2013).

O Algoritmo 3 realiza a extração das features em todos os níveis da estrutura (Linha

4). Em seguida, é feita a variação da escala (Linha 6) para que cada feature tenha sua

extração em todas as escalas definidas, neste passo do algoritmo SURF , não redimensiona

a imagem, pois ao invés de diminuir a imagem para várias escalas é proposto o aumento

do tamanho do filtro (Bay et al. 2008). Para cada variação de nível e escala, são calculados

os deslocamentos (Linhas 8 e 9), tamanhos (Linhas 11 e 12) e os limites inferiores (Linhas

14 e 15) e superiores (Linhas 17 e 18) de cada nível. A partir daí, percorre-se todos os

pixels de p em p dependendo da escala, verificando para cada um se é feature ou não.

Para mais detalhes da implementação, o leitor pode recorrer a tese de doutoramento de

Gomes (Gomes 2013).

A primeira abordagem, verificação pixel a pixel, é incorporada ao Algoritmo 3 entre

as Linhas 20 e 21, porque antes de realizar a verificação de que o pixel é uma feature,

faz-se necessário examinar se este é uma informação proveniente de cálculos já realiza-

dos por outras estruturas foveadas. Para fazer isso, adicionamos mais um laço que varre

todas as regiões convexas sem redundâncias e tentamos buscar o pixel em alguma dessas

regiões. Se o pixel não está dentro de alguma dessas regiões, então não há necessidade da

verificação se ele é uma feature, porque esta verificação foi realizada por fóveas anterio-

res.

Na segunda abordagem, envio de blocos, as Linhas de 8 à 12 apenas são utilizadas

para a construção da primeira fóvea. Por este motivo, é preciso reescrever essas equações

para que possam representar as regiões convexas que não tem redundância. Esta mudança

5.2. A ESTRUTURA MULTIFOVEADA 57

Algoritmo 3: Algoritmo utilizando foveamento para obter features em uma imagem,onde f (I, i, j, p) é uma função que determina se o pixel (i, j) na escala p é umafeature ou não (Gomes 2013, p. 48).

Entrada: I,w,h: imagem I de tamanho w x h; Ei,E f : vetor de escalas; Fx,Fy:coordenada da fóvea; Sm: tamanho do último nível; G: fator decrescimento; m: número de níveis menos um

Saída: c: conjunto de features1 S0,x← w2 S0,y← w3 // Para cada nível k4 para k← 0 até m faça5 // Para cada escala p associada ao nível k6 para p← Ei[k] até E f [k] incrementando ∆ faça7 // Cálculo do deslocamento de cada nível8 δx← k ∗ (S0,x−Sm,x +2∗Fx)/(2∗m)9 δy← k ∗ (S0,y−Sm,y +2∗Fy)/(2∗m)

10 // Cálculo do tamanho de cada nível11 Sk,x← (k ∗Sm,x− k ∗S0,x +m∗S0,x)/m12 Sk,y← (k ∗Sm,y− k ∗S0,y +m∗S0,y)/m13 // Limite inferior da delimitação14 Lx← max(0,δx−Gx)15 Ly← max(0,δy−Gy)16 // Limite superior da delimitação17 Ux← min(S0,x,δx +Sk,x +Gx)18 Uy← min(S0,y,δy +Sk,y +Gy)19 para i← Ly até Uy incrementando p faça20 para j← Lx até Ux incrementando p faça21 se f (I, i, j, p) então22 adicionar (i, j, p) ao conjunto c23 fim24 fim25 fim26 fim27 fim28 retorna c;


é feita apenas realizando a verificação de que se o processamento está sendo realizado da

segunda fóvea ou posteriores devemos considerar os δ e S obtidos a partir do Algoritmo 1.

Como esta abordagem acrescenta apenas uma verificação e a ordem desta operação é

O(1), presume-se que esta metodologia é mais eficiente que a proposta anteriormente.

5.3 Operações de inserção e remoção de estruturas

Na Seção 5.2, acima, é descrito que o formato de armazenamento das estruturas fo-

veadas é realizado usando uma lista. Como a lista é simplesmente encadeada, a inserção

de um novo nó nesta lista é realizada através de um ponteiro deste novo nó para o nó de

continuidade da lista, com o intuito de garantir que o resto da lista não seja perdida, e

conectar o nó anterior ao novo nó (vide Figura 5.2). Este procedimento é comum a todas

as inserções em estruturas de dados com listas simplesmente encadeadas. Porém, obser-

vamos que a inserção de uma nova estrutura deve ser seguida da atualização das estruturas

posteriores ao nó inserido.

Fóvea 1 Fóvea 2 Fóvea 3 . . .

Fóvea n

Figura 5.2: Inserção de fóveas na lista.

A Figura 5.2 descreve como ocorre a inserção de uma estrutura foveada na lista de

armazenamento no modelo multifoveado. Verificamos que as setas representam os pon-

teiros entre os nós. Quando esses ponteiros aparecem em vermelho, representam os pon-

teiros que estão sendo eliminados e quando estão em azul como adicionados. Portanto,

podemos deduzir que a lista está adicionando um quarto elemento entre as Fóveas 1 e 2.

Este tipo de inserção pode ser realizado para resolver o problema de precedência, o qual

será comentado na próxima seção. Para a construção deste trabalho apenas inserimos os

nós no final da fila e isso ocasionou o problema que será comentado adiante.

5.3. OPERAÇÕES DE INSERÇÃO E REMOÇÃO DE ESTRUTURAS 59

A operação de remoção de nós da lista é realizada fazendo com que o nó anterior

aponte para o nó seguinte do nó removido e a consequente devolução da memória do nó

removido ao sistema (vide Figura 5.3). Este procedimento é o mesmo que ocorre corri-

queiramente em estruturas em forma de lista simplesmente encadeada. A atualização da

informação dos nós posteriores ao excluído deve ser realizada porque algumas interseções

podem não existir após a remoção.

Fóvea 1 Fóvea 2 Fóvea 3 . . .

Figura 5.3: Remoção de fóveas a lista.

Assim como na operação anterior, a Figura 5.3 representa em vermelho a informação

que será eliminada e em azul a informação que está sendo adicionada. Notamos, a partir

da análise desta figura que o nó e os apontadores da estrutura da Fóvea 2 está sendo

removida apenas com a modificação do apontador do Nó 1.

5.3.1 Precedência entre estruturas

O MMF define um vetor que indica se haverá extração de features em cada nível

da fóvea. Porém, este fator não foi considerado na modelagem do MMMF e por este

motivo é necessário adicionar as fóveas garantindo que haja prioridade para as fóveas

com extração de features nas primeiras camadas. O modelo MMMF ignora todas as

regiões que foram processadas a priori, independentemente das regiões terem sido ou não

configuradas para a extração das features. Como citado na seção anterior, uma forma de

resolver este problema é realizar a inserção das estruturas levando em consideração os

níveis de extração de features de cada estrutura.

Capítulo 6

Experimentos e Resultados

Neste capítulo, são apresentados os resultados obtidos fazendo uso da abordagem de

verificação pixel a pixel e envio de blocos sem redundância. Os testes foram utilizados

para analisar o desempenho computacional comparado ao método MMF com a aborda-

gem de reexecução. Ademais, servem para analisar a eficiência do método proposto com

relação à eliminação de redundâncias. Todos os experimentos deste capítulo foram reali-

zados com a feature SURF .

6.1 Processamento em relação à distância entre fóveas

Com a abordagem de verificação pixel a pixel, foi realizado um teste com duas fóveas

de W = (60,60), m = 2 e extração de features em todos os níveis. Essas fóveas são

localizadas nas posições de canto superior esquerdo (g) e canto inferior direito ( f ) (vide

Figura 6.1). O sistema foi modificado para realizar a contagem de todos os pixels da

Fóvea g durante a extração de features, enquanto é realizado um deslocamento diagonal

da Fóvea g em direção à Fóvea f visando verificar a taxa de reprocessamento evitada.

Considerando que a Fóvea f já foi processada, o gráfico da Figura 6.2 mostra o número

de pixels processados no último nível da Fóvea g em função da distância entre as duas

fóveas, e a Figura 6.3 apresenta a soma de todos os pixels processados em todos os níveis

de acordo com a distância.

62 CAPÍTULO 6. EXPERIMENTOS E RESULTADOS

Figura 6.1: Disposição das Fóveas f (azul) e g (verde) para o deslocamento diagonal.

0 100 200 300 400 500

0

1,000

2,000

3,000

4,000

Distância euclidiana entre fóveas

Núm

ero

depi

xels

último nível

Figura 6.2: Gráfico do número de pixels processados no último nível da fóvea g com umavariação na distância entre as fóveas realizado a partir de um deslocamento diagonal.

Através da análise da Figura 6.2, verificamos que há um aumento no processamento

de acordo com o aumento da distância entre as Fóveas f e g, o que é esperado uma vez

6.1. PROCESSAMENTO EM RELAÇÃO À DISTÂNCIA ENTRE FÓVEAS 63

0 100 200 300 400 500

0

0.5

1

1.5

2

·104


Núm

ero

depi

xels

todos níveis

Figura 6.3: Gráfico do número de pixels processados em todos os níveis da fóvea g comuma variação na distância entre as fóveas realizado a partir de um deslocamento diagonal.

que o número de pixels redundantes diminui nas camadas superiores da estrutura, não

havendo redundância por estarem mais separadas. Do contrário, percebemos que quando

as fóveas são posicionadas na mesma localização, ou seja, quando houver sobreposição

total da segunda fóvea sobre a primeira, nenhum pixel da Fóvea g será processado, pois

todos já foram processados anteriormente pela Fóvea f , em todos os seus níveis. Isso

permite economizar tempo de processamento, evitando reprocessamento de pixels no caso

de sobreposições entre fóveas.

Na Figura 6.3, observa-se que há uma curva com degraus para a quantidade de proces-

samento. Isto ocorre devido à amostragem de uma camada para outra no método MMF ,

quer dizer, para cada nível é associado um fator de amostragem. Consequentemente, o

somatório de todos os níveis deverão ter níveis que continuam somando enquanto que

outros já terminaram. Note que quando a distância entre f e g é pequena, esses degraus

são mais suaves, porque não há muitos pixels sendo processados em g.

Considerando todos os parâmetros utilizados no primeiro teste, foi realizado um des-


locamento vertical da Fóvea g em direção à Fóvea f . Mantendo a posição da Fóvea f

e posicionando a Fóvea g no canto superior direito (vide Figura 6.4). Obtivemos os re-

sultados relativos à quantidade de processamento apresentados pelas Figuras 6.5 e 6.6.

A Figura 6.5 indica a quantidade de processamento para os pixels na última camada da

Fóvea g. Fazendo uma comparação entre as Figuras 6.2 e 6.5 percebemos um comporta-

mento linear nessa última, enquanto que a primeira curva apresenta um aumento suave.

Também constatamos que o aumento da distância entre as fóveas proporciona o aumento

do processamento dos pixels.

Assim como na Figura 6.3, os degraus também estão presentes na Figura 6.6 que apre-

senta o somatório de todos os níveis da Fóvea g para um deslocamento vertical. Observe

que o comportamento linear também aparece, porém em comparação com a Figura 6.3

não é tão distinto.

Figura 6.4: Disposição das Fóveas f (azul) e g (verde) para o deslocamento vertical.

6.1. PROCESSAMENTO EM RELAÇÃO À DISTÂNCIA ENTRE FÓVEAS 65

0 100 200 300 400 5000

1,000

2,000

3,000

4,000


Núm

ero

depi

xels

último nível

Figura 6.5: Gráfico do número de pixels processados no último nível da fóvea g com umavariação na distância entre as fóveas realizado a partir de um deslocamento vertical.

0 100 200 300 400 500

0

0.5

1

1.5

·104


Núm

ero

depi

xels

todos níveis

Figura 6.6: Gráfico do número de pixels processados em todos os níveis da fóvea g comuma variação na distância entre as fóveas realizado a partir de um deslocamento vertical.


6.2 Comparação entre os métodos

Para todos os experimentos desta seção, é utilizado um Laptop Intel Core i5 2,3GHz

com 4GB de memória RAM e sistema operacional Linux Ubuntu 14.04. Nesta seção,

apresentamos resultados da execução do método MMF original com uma abordagem de

reexecução simples (ou seja, sem verificar a redundância de processamento), do MMMF

proposto com a abordagem de verificação por pixel e do MMMF com envio de informação

de blocos com redundância. Os algoritmos são testados para 1, 2, 3 e 4 fóveas, com

tamanho W = (60,60), submetidos a 5000 iterações. As fóveas contêm 3 níveis e o

programa está configurado para realizar a extração de features (SURF) em todos eles.

Todos os testes desta seção são realizados com uma imagem em forma de tabuleiro

de xadrez, de dimensões 250×250, sendo que cada célula tem dimensão de 5×5 pixels

(vide Figura 6.7). Escolhemos esta imagem pensando em distribuir uniformemente blobs

por toda imagem. Fazendo isso, garantimos que todas as poses das fóveas extrai a mesma

quantidade de features. As tabelas apresentadas abaixo indicam a média (µ) e o desvio

padrão (σ) de cada um dos testes.

Figura 6.7: Imagem em forma de tabuleiro de xadrez utilizada para realizar os testesreferentes ao posicionamento de 4 fóveas.

6.2. COMPARAÇÃO ENTRE OS MÉTODOS 67

6.2.1 Disposição nos extremos da imagem

Neste teste, as fóveas estão distribuídas nas extremidades da imagem. As Tabe-

las 6.1 e 6.2 foram obtidas considerando as fóveas posicionadas em (−95,−95), (95,95),

(95,−95) e (−95,95), respectivamente. Essas posições são argumento do método multi-

foveado e a origem deste sistema de coordenadas é o centro da imagem.

Método 1 fovea 2 foveas 3 foveas 4 foveasµ σ µ σ µ σ µ σ

MMF 1.19 0.43 1.81 0.11 2.70 0.23 3.59 0.23MMMF px/px 1.34 0.52 1.86 0.12 2.71 0.20 3.44 0.23MMMF blocos 1.31 0.51 1.56 0.10 2.02 0.23 2.36 0.18

Tabela 6.1: Tempo médio (milissegundos) e desvio padrão para a obtenção dos keypoints,considerando as poses (−95,−95), (95,95), (95,−95) e (−95,95).



Tabela 6.2: Tempo médio (milissegundos) e desvio padrão para a obtenção dos descrito-res, considerando as poses (−95,−95), (95,95), (95,−95) e (−95,95).

De acordo com a Tabela 6.1, o método MMMF com abordagem por envio de blocos,

em todos os testes, é mais rápido que o MMMF com a abordagem pixel a pixel para a

descrição dos keypoints. O desempenho superior por blocos ocorre porque na abordagem

do MMMF por pixels perde-se muito tempo verificando se o pixel encontra-se na região

de redundância. Na comparação com o método MMF tradicional com reexecução (pri-

meira linha da Tabela 6.1), o MMMF com abordagem por envio de blocos, é mais rápido

em quase todos os testes para a descrição dos keypoints, excetuando-se no caso de apenas

uma fóvea, o que já era esperado. Além disso, podemos verificar através da Tabela 6.2 que

as duas abordagens de MMMF na computação dos descritores são superiores em relação

ao MMF .


6.2.2 Disposição ao redor da origem

As distribuições deste teste ficam contornando a fóvea, porém não há interseção no

último nível. As Tabelas 6.3 e 6.4 foram construídas considerando as poses (-30,-30),

(30,30), (30,-30) e (-30,30), respectivamente.



Tabela 6.3: Tempo médio (milissegundos) e desvio padrão para a obtenção dos keypoints,considerando as poses (-30,-30), (30,30), (30,-30) e (-30,30).



Tabela 6.4: Tempo médio (milissegundos) e desvio padrão para a obtenção dos descrito-res, considerando as poses (-30,-30), (30,30), (30,-30) e (-30,30).

Com relação à extração de keypoints, percebemos pela Tabela 6.3 que as duas abor-

dagens de MMMF apresentam um desempenho superior ao MMF em quase todas as

distribuições de fóvea, exceto quando há somente uma fóvea. Na obtenção dos keypoints

percebemos que quando há uma fóvea o método MMF se sobressai com relação aos ou-

tros. Isto ocorre porque as abordagens do MMMF realizam algumas operações adicionais

por terem sido implementadas como interface. Em oposição a esta observação, percebe-se

que a computação posterior dos descritores pelas abordagens MMMF são mais eficientes

do que a MMF , visto que não há redundância dos keypoints.

6.2. COMPARAÇÃO ENTRE OS MÉTODOS 69

6.2.3 Disposição das fóveas na origem

As Tabelas 6.5 e 6.6 foram construídas considerando todas as fóveas na posição (0,

0), ou seja, com sobreposição total de todas as outras fóveas sobre a primeira. Ou seja,

neste teste, esperamos que todos os níveis das fóveas computadas após a primeira fóvea

sejam tenham redundância com esta. Consequentemente, espera-se que o processamento

das Fóveas 2, 3 e 4 não deverão consumir muito tempo.



Tabela 6.5: Tempo médio (milissegundos) e desvio padrão para a obtenção dos keypoints,considerando que todas as fóveas estão posicionadas na origem.



Tabela 6.6: Tempo médio (milissegundos) e desvio padrão para a obtenção dos descrito-res, considerando que todas as fóveas estão posicionadas na origem.

De fato, esta hipótese de que o processamento das Fóveas 2, 3 e 4 não deverão con-

sumir muito tempo é constatada através das Tabelas 6.5 e 6.6 para a abordagem de envio

de blocos. Na abordagem de verificação de pixels isso não ocorre, porque todos os pixels

terminam sendo verificados e isso acaba consumindo processamento, mas ainda assim

esse método é mais eficiente que o MMF tradicional com reexecução sem verificação de

redundância, tanto na extração dos keypoints quanto na computação dos descritores.

Capítulo 7

Conclusão

Neste trabalho, são propostas duas abordagens que estendem o método MMF (Gomes

2013), para que este seja capaz de suportar múltiplas fóveas. A partir de um estudo inicial

na literatura, foi percebido que todos os métodos utilizam a reexecução de uma técnica

de foveamento mas simples para construção do multifoveamento. Porém, esta medologia

quando aplicada ao método MMF provoca redundâncias no processo de extração e com-

putação das features, devido à ocorrência de regiões de interseções entre pares de fóveas

no seus diversos níveis. Assim, é interessante prover uma maneira de não recalcular re-

giões para fóveas futuras se a mesma já foi calculada anteriormente. Buscando resolver

este problema, propomos duas abordagens, sendo uma de verificação de pixels e outra

por envio de blocos, os quais dependem da quantidade de níveis e das distâncias entre

as fóveas. A partir dessas abordagens, constatamos que o método MMMF com envio de

blocos apresenta o melhor desempenho em relação a abordagem de verificação pixel a

pixel e é muito superior ao método MMF com simples reexecução.

As abordagens sugeridas neste trabalho são limitadas às estruturas que contenham

as mesmas quantidades de níveis, e também, as mesmas dimensões das estruturas de

fóvea. Estas limitações podem ser contornadas reescrevendo-se as equações algébricas

apresentadas nesta dissertação, mas isso não afeta a sua utilização nem eficácia, da forma

como se encontra desenvolvida. Somando-se às limitações deste modelo multifoveado,

encontra-se a precedência entre as fóveas, no que se refere a extração de features nas

72 CAPÍTULO 7. CONCLUSÃO

camadas inferiores, discutida no Capítulo 5, o que também não limita o seu uso na maioria

das aplicações.

O multifoveamento pode ser explorado em diversas aplicações, provendo vários pon-

tos com acuidade visual na imagem. O potencial desta técnica é tão amplo que um sistema

que mantém o multifoveamento é capaz de ativar concomitantemente as atenções bottom-

up e top-down, com base no que foi desenvolvido. Assim, tarefas como a busca por

objetos em uma imagem em meio a outros objetos distraidores, o rastreio ou tracking de

vários objetos ao mesmo tempo, atenção top-down e bottom-up simultâneas, entre outras,

podem se beneficiar desta técnica.

Os próximos trabalhos a serem desenvolvidos futuramente são: (1) estender as duas

abordagens do MMMF para o domínio 3D reescrevendo o sistema para coordenadas de

fóveas no R4, onde cada vetor (x,y,z) está associado a um nível no domínio MMF e (2)

realizar uma análise de contexto para estabelecer a necessidade de inserção, alteração ou

remoção de fóveas. Essa análise de contexto pode ser realizada usando teoria dos grafos,

campos potenciais ou redes complexas.

Referências Bibliográficas

Adelson, E. H. & E. Simoncelli (1987), ‘Orthogonal pyramid transforms for image co-

ding’, Visual Communications and Image Processing II 845, 50–58.

Basu, A. & K. J. Wiebe (1998), ‘Enhancing videoconferencing using spatially varying

sensing’, IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems

and Humans 28, 137–148.

Bay, H., T. Tuytelaars & L. V. Gool (2008), ‘SURF: Speeded up robust features’, Com-

puter Vision and Image Understanding 110, 346–359.

Bezerra, L. C. A. (2006), Implementação de rotinas computacionais básicas para cabeça

estéreo robótica, Tese de doutorado, Universidade Federal do Rio Grande do Norte.

[Online; accessed 22-Maio-2016].

URL: http://repositorio.ufrn.br/handle/123456789/15389

Camacho, P., F. Arrebola & F. Sandoval (1998), Adaptive multifovea sensors for mobiles

tracking, em ‘IEEE International Conference on Electronics, Circuits and Systems’,

IEEE, Lisboa, pp. 449–452.

Dario, P., M. Bergamasco, A. Fiorillo & R. Leonardo (1986), Geometrical optimization

criteria for the design of tactile sensing patterns, em ‘IEEE International Conference

on Robotics And Automation’, IEEE, pp. 1268–1273.

Dhavale, N. & L. Itti (2003), Saliency-based multi-foveated mpeg compression, em ‘Se-

venth International Signal Processing and its Applications’, IEEE, pp. 229–232.

73

74 REFERÊNCIAS BIBLIOGRÁFICAS

Freeman, W. T. & E. H. Adelson (1991), ‘The design and use of steerable filters’, IEEE

Transactions on Pattern Analysis and Machine Intelligence 13(9), 891–906.

Gomes, R. B., B. M. Carvalho & L. M. G Gonçalves (2013), ‘Visual attention guided

features selection with foveated images’, Neurocomputing 120, 34–44.

Gomes, R. B., B. M. F. Silva, L. K. M. Rocha, R. V. Aroca, L. C. P. R. Velho & L. M. G.

Gonçalves (2013), ‘Efficient 3D object recognition using foveated point clouds’,

Computer & Graphics 37, 496–508.

Gomes, R. B., L. M. G. Gonçalves & B. M. Carvalho (2008), Real time vision for robo-

tics using a moving fovea approach with multi resolution, em ‘IEEE International

Conference on Robotics and Automation’, IEEE, Pasadena, CA, USA, pp. 19–23.

Gomes, R. B., R. Q. Gardiman, L. E. C. Leite, B. M. Carvalho & L. M. G.

Goncalves (2010), ‘Towards real time data reduction and feature abstraction

for robotics vision’, Robot Vision pp. 345–362. DOI: 10.5772/9305. Availa-

ble from: http://www.intechopen.com/books/robot-vision/towards-real-time-data-

reduction-and-feature-abstraction-for-robotics-vision.

Gomes, R.B. (2013), Seleção de features guiada por atenção visual em imagens com

fóvea, Tese de doutorado, Universidade Federal do Rio Grande do Norte. [Online;

accessed 22-Maio-2016].

URL: http://repositorio.ufrn.br/handle/123456789/15235

Gonçalves, L. M. G. (1999), Um sistema de controle robótico para integração de infor-

mação sensorial multi-modo, Tese de doutorado, Universidade Federal do Rio de

Janeiro. [Online; accessed 25-Maio-2016].

URL: http://www.cos.ufrj.br/index.php/pt-BR/publicacoes-pesquisa/details/15/790

REFERÊNCIAS BIBLIOGRÁFICAS 75

Lim, F. L., A. W. West & S. Venkatesh (1996), Tracking in a space variant active vision

system, em ‘Proceedings of the 13th International Conference on Pattern Recogni-

tion’, Vol. 1, IEEE, Vienna, pp. 745–749.

Lindeberg, T. (1989), ‘Feature detection with automatic scale selection’, International

Journal of Computer Vision 30(2), 90–95.

Lindeberg, T. (1991), Discrete scale-space theory and the scale-space Primal Sketch, Tese

de doutorado, Royal Institute of Technology. [Online; accessed 25-Maio-2016].

URL: http://www.csc.kth.se/ tony/abstracts/CVAP84.html

Mallat, S. G. (1989), ‘A theory for multiresolution signal decomposition: The wavelet

representation’, IEEE Transactions on Pattern Analysis and Machine Intelligece

11(7), 674–693.

Oxford dictionary of english (2010).

Pioppo, G., R. Ansari, A. Khokhar & G. Masera (2006), Low-complexity video compres-

sion combining adaptive multifoveation and reuse of high-resolution information,

em ‘International Conference on Image Processing’, IEEE, Atlanta, GA, pp. 3153–

3156.

Ramisa, A., A. Tapus, R. L. Mantaras & R. Toledo (2008), Mobile robot localization

using panoramic vision and combination of local feature region detectors, IEEE,

pp. 19–23.

Rodríguez, J. A., C. Urdiales, A. Bandera & F. Sandoval (2002), ‘Nonuniform video co-

ding by means of multifoveal geometries’, International Journal of Imaging Systems

and Technology 12, 27–34.

Sankara, S., R. Ansari & A. Khokhar (2005), Adaptive multifoveation for low-complexity

video compression with a stationary camera perspective, em ‘Proceedings of SPIE -

76 REFERÊNCIAS BIBLIOGRÁFICAS

The International Society for Optical Engineering’, Vol. 5685, SPIE, San Jose, CA,

United States, pp. 1007–1018.

Traver, J. & A. Bernardino (2009), ‘A review of log-polar imaging for visual perception

in robotics’, Robotics and Autonomous Systems 58, 378–398.

Uhr, L. (1972), ‘Layered recognition cone networks that pre-process, clas-

sify, and describe’, IEEE Computer Society 21(7), 758–768. DOI:

http://doi.ieeecomputersociety.org/10.1109/T-C.1972.223579.

Yang, Fan, Wongun Choi & Yuanqing Lin (2016), Exploit all the layers: Fast and accurate

CNN object detector with scale dependent pooling and cascaded rejection classifi-

ers, em ‘Proceedings of the IEEE International Conference on Computer Vision and

Pattern Recognition’.

multifoveamento em multirresolução com fóveas móveis...universidade federal do rio grande do...

Documents