De daglige rutinene

uma metodologia para localização, utilizando apenas a informação obtida dos sonares e o prévio conhecimento abstrato sobre a estrutura do ambiente local.

Outras variações desta transformada podem ser utilizadas, como no trabalho de Fors- berg et al. (1995), por exemplo. Eles propuseram uma metodologia de navegação de robôs móveis com autolocalização no ambiente. Para a representação local, eles consi- deraram que o robô atuava em ambientes retangulares. Cada parede era representada por uma linha reta obtida por transformada de Hough ponderada. O intuito de utilizar esta variação do algoritmo de Hough era diminuir a influência de máximos locais na matriz acumuladora, os quais eram provenientes de pontos espúrios retornados pelo sensor laser utilizado. Com isto, procedia-se a busca, na matriz acumuladora, dos quatros maiores valores, correspondendo assim às quatro retas que se ajustavam às paredes do ambiente. O grande problema relatado pelos autores na época foi o elevado custo computacional exigido pelo método.

Uma observação importante é que as considerações utilizadas para o mapeamento local de Forsberg et al. (1995) são, também, similares às considerações adotadas para esta tese. Uma das diferenças entre as duas abordagens é o tipo de ferramenta utilizada. Em ambos são usados variações do algoritmo padrão de Hough. Porém, enquanto aqui foi utilizada uma modificação da transformada generalizada de Hough, Forsberg et al. (1995) optaram por aplicar o algoritmo padrão para retas com ponderação no procedimento de voto na matriz acumuladora. É necessário ressaltar que os resultados finais são distintos.

4.2

Transformada Generalizada de Hough

Embora seja apropriada para encontrar uma série de curvas qu e se ajustem a um con- junto de pontos coletados de sensores extraceptivos, como sonares ou lasers, o algoritmo padrão de Hough não pode detectar formas geométricas que não podem ser descritas por formas analíticas.

Dessa maneira, algoritmos mais generalistas foram apresentados para suprir essa de- ficiência. O principal deles foi proposto por Ballard (1981), que criou a chamada trans- formada generalizada de Hough. O seu objetivo era detectar quaisquer outros tipos de formas geométricas em uma imagem digital.

Esta figura generalizada foi definida através dos seguintes parâmetros:

a= {y, s, θ} (4.6)

onde y= (xr, yr) é a posição de origem da forma geral, s = (sx, xy) são fatores de escala nos eixos x e y respectivamente eθ é a orientação da forma geral na figura. Outros parâmetros

podem ser facilmente adicionados, ou retirados, nesta forma geométrica a. No entanto, o algoritmo também deve sofrer as respectivas modificações.

O objetivo da transformada generalizada de Hough, então, é obter o melhor conjunto de parâmetros do vetor a a partir de um conjunto de dados de referência (pixels). Ou seja, deseja-se saber quantas instâncias da forma a existem em uma imagem. Esta imagem na qual se deseja encontrar a referida figura é denomidada de imagem de busca.

64 CAPÍTULO 4. REPRESENTAÇÃO MÉTRICA LOCAL

outra imagem, chamada de imagem de referência, que tem a forma a desejada. Desta ima- gem de referência utiliza-se a informação do gradiente dos pixels da figura desejada para construir uma tabela, denominada de tabela-R. A construção desta tabela-R é realizada em uma fase off-line do algoritmo.

A tabela-R, por conter informações sobre a posição e orientação dos pixels da figura geral na imagem de referência, serve como guia na procura da figura desejada na imagem de busca. Ela auxilia o procedimento de votação dos elementos do espaço acumulador.

Para montar esta tabela-R, adota-se a seqüência de passos descrita no algoritmo 4.1. A figura 4.5 ilustra a construção de uma tabela-R dada uma forma geral a.

Escolher um ponto de referência y para a forma desejada na imagem de referência. Nor- malmente utiliza-se o centróide da figura, como sugerido por Ulrich et al. (2003);

Para cada ponto x na borda da imagem: Computar a direção do gradienteφ(x);

Calcular a distância até a origem escolhida r= y − x;

Armazenar r como função deφ(x).

Algoritmo 4.1: Seqüência passos para construção da tabela-R, dada uma imagem de

referência. r x y φ i φ(x) r 0 φ0 r0 1 φ1 r1 .. . ... ... n φn rn (4.7)

Figura 4.5: Exemplo ilustrativo de geração da tabela-R a partir das informações de uma forma de referência.

Observa-se que tanto a imagem de referência como a imagem de busca devem ser tratadas por ferramentas da área de processamento de imagens para a obtenção de imagens binarizadas antes da aplicação do método.

Uma vez que a tabela-R esteja criada, deve-se construir um espaço vetorial acumula- dor multidimensional, com número de dimensões igual ao número de parâmetros da forma

a. Cada parâmetro é discretizado dentro de um intervalo de busca apropriado, para que

sua representação no espaço de Hough seja possível. Assim como no algoritmo padrão, os valores iniciais dos elementos do espaço vetorial de Hough devem ser nulos.

4.2. TRANSFORMADA GENERALIZADA DE HOUGH 65

Com isso, passa-se para a forma on-line da transformada generalizada, a qual é apre- sentada no algoritmo 4.2.

Criar um espaço vetorial multidimensional_{A(y, s, θ) para acumular os votos obtidos com} o algoritmo. Todos os seus elementos devem ser iguais a zero;

Para cada pixel x na imagem de busca:

Para cada possível ânguloθ que a forma possa assumir:

Para cada possível fator de escala s que a forma possa ter:

Calcular o possível centro da forma a na imagem de busca através de

y_{= T}o(x + Ts(r))

onde_To eTssão as transformações de orientação e de escala, respectiva- mente, que o ponto central da forma na imagem de busca pode sofrer. Incrementar o elemento correspondente no espaço acumulador multidimen- sional, desde que este espaço tenha um elemento com os índices correspon- dentes aos valores dos parâmetros obtidos

A(y, s, θ) = A(y, s, θ) + 1

Valores máximos no espaço acumulador são as possíveis instâncias da forma desejada.

Algoritmo 4.2: Transformada generalizada de Hough, dada uma tabela-R previamente

construída.

A desvantagem deste algoritmo é a grande quantidade de memória utilizada para ar- mazenar o espaço acumulador e o alto custo computacional exigido para o seu tratamento (inicialização, incremento de elementos e busca de valores máximos).

Diversos trabalhos têm sido apresentados visando a redução deste esforço. Olson (1998) utilizou técnicas de agrupamento de pontos em uma imagem digital para melhorar o desempenho da transformada generalizada de Hough. No seu caso, ele tratou de obter objetos 3D dada uma imagem bidimensional.

Ulrich et al. (2003) apresentaram uma metodologia para obter formas genéricas em tempo real. Para isto, eles utilizaram um procedimento hierárquico, tanto na busca de pixels na imagem de referência quanto na imagem de busca. Ou seja, eles geravam ima- gens de referência e de busca com baixa resolução nos pixels. A partir disto, criavam a tabela-R e aplicavam a transformada generalizada. Este procedimento era repetido até atingir uma resolução aceitável.

Em trabalhos envolvendo robótica, a transformada generalizada tem sido pouco utili- zada por causa de resultado satisfatório do algoritmo padrão. Uma exceção foi o trabalho de Chen e Tsai (1998) que apresentou uma metodologia de aprendizado do ambiente durante a navegação do robô móvel em ambientes internos. O modelo deste ambiente explorado foi obtido através da aplicação de uma transformada generalizada de Hough modificada. Eles implementaram um algoritmo ponderado, no qual o espaço acumula-

66 CAPÍTULO 4. REPRESENTAÇÃO MÉTRICA LOCAL

dor não tinha seus elementos incrementados por 1, mas sim por um fator em função da distância dos pontos coletados do ambiente. O robô foi dotado de câmeras e encoders para obtenção das informações sensoriais. Inicialmente, os autores extrairam as linhas verticais das imagens coletadas. Como cada linha vertical correspondia a um ponto em um plano bidimensional transversal a estas linhas, Chen e Tsai (1998) aplicaram o seu algoritmo para atualizar a pose do robô (uma vez que cada ponto tinha como referência a posição atual do robô) e para obter a representação local.

Neste sentido, o método aqui empregado para obter a geometria de um espaço local utilizando uma transformada generalizada de Hough modificada traz o ineditismo para esta tese de doutorado, uma vez que não foram encontradas referências sobre tal aplica- ção. Nas próximas seções serão apresentados os algoritmos empregados para obter os resultados deste trabalho.