DETECÇÃO DE GUIAS UTILIZANDO VARIAÇÕES DA TRANSFORMADA DE
HOUGH
Vinícius M. P. Ferriani
ITA – Divisão de Engenharia Eletrônica
Praça Mal. Eduardo Gomes, 50
12228-900 São José dos Campos – SP
[email protected]
Carlos H. C. Ribeiro
ITA – Divisão de Ciência da Computação
Praça Mal. Eduardo Gomes, 50
12228-900 São José dos Campos – SP
[email protected]
Resumo: Utilizando filtros que fazem a derivada direcional de uma imagem, transformada de Hough e
filtro de Kalman, foi construído um sistema de detecção de guias, como parte de um projeto mais
amplo de desenvolvimento de um sistema de vigilância de ambientes externos baseado em robôs
móveis Pioneer. Tendo como plataforma de visão uma webcam de baixa resolução, o algoritmo
implementado conseguiu identificar guias retas e curvas leves em um ambiente de atuação típico.
Abstract: Using filters that evaluate the directional derivative of an image, Hough transform and the
Kalman filter, a sidewalk detection system was developed as part of a broader project on the
development of a monitoring system for outdoor environments based on Pioneer mobile robots.
Having as vision platform a low resolution webcam, the implemented algorithm managed to identify
straight and slightly curved sidewalks in a typical actuation environment.
1. INTRODUÇÃO
Esse projeto está relacionado ao desenvolvimento de um sistema de vigilância de ambientes
externos baseado em robôs móveis Pioneer. Através de um sistema de visão computacional, consiste
em desenvolver e implementar algoritmos de detecção de bordas baseados no filtro Sobel, na
parametrização de retas através de transformada de Hough e no Filtro de Kalman, visando determinar
onde guias de calçadas se encontram.
Primeiramente o sistema foi desenvolvido usando o pacote MatLab [1]. Em seguida foi
confeccionado um sistema de calibração de algoritmos e parâmetros em Java utilizando o software
NetBeans 3.6 e Java Media Framework [2][3] para a obtenção de imagens da câmera. Neste caso o
algoritmo foi implementado para operação em tempo real, e dá a possibilidade de comparar quase
instantaneamente diversas combinações de filtros e parâmetros para as imagens capturadas através do
sistema de visão.
O sistema de visão utiliza apenas uma Webcam para a obtenção das imagens. A escolha desta
alternativa tem o objetivo de tornar o projeto barato, mas ainda assim efetivo.
Para os testes em campo foi feita uma plataforma em metal para emular as características
físicas dos robôs móveis Pioneer. Assim, pudemos testar os algoritmos em uma situação mais próxima
possível do que será enfrentada pelo robô, quando o algoritmo nele for implementado.
O objetivo deste artigo é descrever os algoritmos e a implementação nos dois sistemas, bem
como mostrar alguns resultados de testes e apresentar conclusões com base nestas informações.
Detalhes da implementação Java e dos testes completos foram objeto de desenvolvimento por outros
participantes do projeto [4][5], e fogem do escopo deste artigo.
2. BASE TEÓRICA
2.1 Filtro Sobel
O filtro Sobel é uma matriz com a qual se pode fazer uma convolução, e que produz a
derivada direcional da imagem [6]. Na Equação (1), a matriz A calcula a derivada Sobel no sentido
vertical, e a matriz B calcula a derivada no sentido horizontal.
⎛ −1 0 1⎞
⎛1 0 −1⎞
2
1⎞
⎛1
⎛ − 1 − 2 − 1⎞
⎜
⎟,
⎜
⎟
⎜
⎟,
⎜
⎟,
0
0 ⎟ Dij = ⎜ 2 0 − 2 ⎟
0
0 ⎟ Bij = ⎜ − 2 0 2 ⎟ Cij = ⎜ 0
Aij = ⎜ 0
⎜ −1 0 1⎟
⎜1 0 −1⎟
⎜ − 1 − 2 − 1⎟
⎜1
2
1 ⎟⎠
⎝
⎠
⎝
⎠
⎝
⎠
⎝
(1)
2.2 Filtros com Derivada Direcional
Para obtermos uma derivada direcional da imagem, utilizamos uma extrapolação da derivada
de Sobel:
I × cos(θ + 45º ) ⎞
⎛ I × cos(θ + 135º )
I × cos(θ + 90º )
⎜
⎟
2
⎜
⎜
Dirij ( I , θ ) =⎜ I × cos(θ + 180º )
⎜
⎜ I × cos(θ + 225º )
⎜
2
⎝
⎟
⎟
I × cos(θ )
⎟
⎟
I × cos(θ + 315º ) ⎟
⎟
2
⎠
2
0
I × cos(θ + 270º )
(2)
onde I é a intensidade do filtro e θ é o ângulo de derivada desejado. Outras formas de obter derivadas
direcionais são dadas por:
⎧
⎛ Aij ⎞
2
2
⎪ I × Aij + Bij , arctan⎜⎜ ⎟⎟ ∈ [θ − ρ ,θ + ρ ]
⎪
(3)
⎝ Bij ⎠
biSobelij = ⎨
⎞
⎛
A
ij
⎪
0, arctan⎜ ⎟ ∉ [θ − ρ ,θ + ρ ]
⎜B ⎟
⎪
⎝ ij ⎠
⎩
⎧
⎛ ( Aij − Cij ) ⎞
2
2
⎟ ∈ [θ − ρ ,θ + ρ ]
⎪ I × ( Aij − Cij ) + ( Bij − Dij ) , arctan⎜⎜
( Bij − Dij ) ⎟⎠
⎪
⎝
(4)
quadSobelij = ⎨
⎛
⎞
A
C
(
−
)
ij
ij
⎪
⎟ ∉ [θ − ρ ,θ + ρ ]
0, arctan⎜
⎪
⎜ (B − D ) ⎟
ij ⎠
⎝ ij
⎩
Pudemos observar que os resultados da seleção de ângulos utilizada nos algoritmos biSobel e
quadSobel são tão efetivos quanto a rotação da matriz de derivadas (Dir), no intuito de obter apenas os
pontos correspondentes às retas cujos ângulos de inclinação estão próximos à θ. Entretanto, biSobel e
quadSobel são mais vantajosas porque nestes podemos selecionar diretamente o intervalo de aceitação
r em torno do ângulo central θ.
2.3 Transformada de Hough e Filtro de Kalman
A transformada de Hough [6] é um algoritmo de procura da reta de melhor ajuste em um
conjunto de pontos dado. Para cada uma das infinitas retas que passam por cada ponto (x, y), existe
um (r, θ) associado satisfazendo a Equação (5):
(5)
x cos(θ ) + y sin(θ ) = r
Os pontos (x,y) onde as retas candidatas devem passar estão definidos em uma imagem J(x,y).
Para cada um dos pontos definidos como cantos, somamos o valor de sua intensidade à imagem
resultado R(r, θ), percorrendo θ e obtendo o r correspondente. Ao fim disso, esta votação é
normalizada e o ponto (r, θ) com maior número de votos corresponderá ao (r, θ) da reta vencedora.
O Filtro de Kalman [7] consiste em uma representação de uma crença posterior a respeito de
uma grandeza na forma de uma gaussiana, e uma matriz de erro P associada. Ele apresenta duas fases
a serem executadas a cada unidade de tempo t: a fase de propagação e a fase de atualização.
Na fase de propagação calcula-se o próximo valor esperado utilizando um modelo físico e os
dados anteriores, com erro do modelo Qt, e o erro Pt do filtro aumenta. Em seguida passa-se à fase de
atualização, onde, de posse dos valores obtidos dos sensores e dos modelos dos sensores (com um erro
Rt associado), corrige-se o valor das grandezas físicas, e o valor do erro Pt é diminuído. No nosso caso,
as grandezas físicas formam um vetor, e são os valores inteiros dos índices de r e θ correspondentes à
reta procurada, sendo máximos no gráfico resultante da transformada de Hough.
Assumimos que estes valores devem permanecer constantes ao longo do tempo, o que torna o
Filtro de Kalman na verdade uma média ponderada entre os valores atuais dos sensores e os valores
anteriores (a ponderação é determinada pelos valores Ro e Qo).
2
3. IMPLEMENTAÇÃO EM MATLAB
3.1 Algoritmo Utilizando o Matlab
1. Se a imagem não estiver em preto e branco, transforma a mesma para preto e branco.
2. Realiza convoluções na imagem com os filtro sobel A e B, e soma os seus quadrados. No caso
específico do MatLab, estão sendo cobertas as derivadas em qualquer direção desta forma.
3. O filtro retorna uma imagem binária dizendo se o ponto (x,y) é considerado um canto ou não
(ultrapassa um determinado limite).
4. Realiza a transformada de Hough de acordo com o dimensionamento especificado.
5. Acha o máximo da matriz de acumuladores e mostra a imagem resultado desta Transformada.
6. Obtém a derivada da imagem da Transformada de Hough utilizando a aproximação sobel
vertical da derivada.
7. Obtém o ponto de máximo da imagem resultante, que se torna a linha principal.
8. Elimina pontos ao redor desse primeiro máximo e obtém um segundo máximo (linha
secundária).
9. Apresenta as retas cujos acumuladores tem valores acima de um determinado limite em azul, a
linha principal e a linha secundária em pontilhado verde. Retorna o tempo gasto na operação.
3.3 Testes e Resultados
3.3.1 Primeiro conjunto de testes
No algoritmo, no primeiro conjunto de testes, obteve razoável sucesso nas suas análises,
conseguindo distinguir as duas retas principais em condições normais. Quando a guia apresenta curva
acentuada ele só conseguiu obter uma das retas, e às vezes nenhuma. A obtenção de curvas foi tratada
posteriormente no algoritmo implementado em Java, mas ainda não é perfeita.
Foram encontrados problemas onde um objeto do cenário apresentou maior gradiente e foi
detectado como guia. Para resolver esse problema, foram apresentadas três soluções: deixar a câmera
mais voltada para o chão e sem o horizonte, utilizar um filtro que detecte contraste em uma
determinada direção específica, e processar apenas uma parte de interesse da imagem.
3.3.2 Segundo conjunto de testes
No segundo conjunto de testes a câmera foi colocada 25 cm da margem da rua e a 30 cm de
altura. Esses testes tiveram como objetivo testar uma maior inclinação da câmera na direção do chão.
Pode-se notar (Figura 1) que o algoritmo obtém pouco sucesso quando a câmera está inclinada
para a frente. Já quando ela está inclinada para baixo, o algoritmo consegue obter uma das retas, com
razoável confiabilidade. No entanto, como a câmera é um sensor relativamente caro e tem diversas
outras utilidades se apontado para frente, foram implementados algoritmos para as soluções 2 e 3
apresentadas no item 3.3.1, isto é, processamento de apenas uma parte da imagem e utilização da
derivada direcional. Entretanto, esses algoritmos já foram somente implementados em Java.
(a)
(b)
3
(c)
(d)
Figura 1: Resultados do processamento da Transformada de Hough no Matlab. Em a e b a câmera está
orientada para frente, e nas figuras c, d e e a câmera está inclinada para baixo em 30º.
4. Software de Calibração de Algoritmo em Java
Para o ajuste e calibração dos algoritmos e filtros, foi implementada uma interface em Java.
4.1 Filtros
Os filtros mais importantes implementados foram:
• grayscale - filtro que torna a imagem em preto e branco.
• edge - filtro que realça os cantos da imagem.
• gaussiana3 (com ou sem ajuste de sigma) - elimina ruídos da imagem com matriz 3x3.
• gaussiana5 (com ou sem ajuste de sigma) - elimina ruídos da imagem com matriz 5×5.
• sobel (com ajuste de Intensidade e ângulo principal)
• biSobel (com ajuste de Intensidade, ângulo central θ e alcance do ângulo r)
• quadSobel (com ajuste de Intensidade, ângulo central θ e alcance do ângulo r)
4.2 Transformada de Hough e Filtro de Kalman
A transformada de Hough é inicializada com o número de partições em θ e em r, o limite para
se considerar um ponto da imagem fonte como sendo um ponto de canto, e as dicas de renderização. O
comando hough colocado na janela “Resultados” também é responsável por chamar o filtro de
Kalman, atualizando os valores de Ro e Qo e obtendo os valores de (r, θ) e do erro P.
O centro da bola vermelha após o filtro de Hough indica o máximo da função Hough(r, θ). O
centro da bola verde indica o (r, θ) retornados pelo filtro de Kalman. O raio do círculo verde depende
de Ro e Qo, e após alguma mudança nessas variáveis ele se estabiliza novamente. Este valor indica o
intervalo de confiança ao redor de (r, θ) para o próximo máximo (r, θ). Caso ele não esteja neste
intervalo, será ignorado, até que a cada NumFalhas (predefinido) erros os valores de (r, θ) são aceitos.
Esse sistema faz com que pequenas perturbações nos valores de (r, θ) máximos obtidos pela
Transformada de Hough não atrapalhem o valor de (r, θ) após o filtro de Kalman. A variável
NumFalhas tem a função de atualizar os valores de (r, θ) caso a mudança persista por tempo suficiente.
As retas encontradas são mostradas sobre os resultados dos filtros. A reta vermelha é a reta de
máximo encontrada apenas pela transformada de Hough, enquanto a reta verde é a reta fornecida como
certa após tanto a transformada de Hough quanto o Filtro de Kalman.
4.3 Interface com o Usuário
A aplicação foi desenvolvida utilizando MDI. Há apenas uma janela “Original” dentro da
janela mãe, e podem ser criadas várias janelas “Resultados”. A janela “Original” contém a imagem
original, uma caixa de texto e um botão que cria janelas “Resultados” com o texto da caixa de texto.
Clicando e arrastando o mouse dentro da imagem original é possível selecionar uma área a ser
utilizada com a filtro clip, isto é, uma área que será recortada para a aplicação dos filtros. Esta é a
solução do problema de filtrar apenas uma parte da imagem, proposto em 3.3.2.
4
A caixa de texto da janela “Resultados” pode ser modificada a qualquer momento. Clicando
com o botão direito na janela Resultados é possível alternar quais imagens dos filtros aparecem na
janela.
5. Plataforma de Testes
Por
fim,
confeccionou-se
uma
plataforma de testes de metal, com dimensões:
(45x50x30) cm (largura, comprimento, e altura
da lente da câmera). Sobre a plataforma foi
fixado um laptop com velcro. A câmera foi
afixada com fita isolante. Esta plataforma
(Figura 2) foi utilizada para se obter a melhor
configuração para os filtros e parâmetros
possíveis. Alguns dos testes estão na próxima
seção.
Figura 2: Plataforma de testes em um corredor.
5.1 Resultados e Análise de Testes na Plataforma
(a)
(b)
Figura 3: Testes. a) Elementos Adversos, b) Horizonte, tamanho da transformada e Filtro de Kalman
Os testes estão nas figuras 3 e 4. Em (a), há chuva e tempo nublado. Ao topo apresenta-se a
interferência de uma pessoa atravessando a visão da câmera, e abaixo temos poças d’água. Em (b) há
um estacionamento de bicicleta. Assim que cortamos a imagem, vemos que ele começa a identificar a
reta errada, porque o tamanho da imagem do filtro de Hough é muito grande. A solução para este
problema é manter um tamanho da imagem do filtro de Hough comparável ao tamanho da imagem
original. A terceira, quarta e quinta análises mostram o Filtro de Kalman em ação.
5
Figura 4: Testes: tomada de curva e na curva.
Na figura 4 temos a
entrada em uma curva e
durante a mesma. É possível
acompanhar a curva, desde
que não se esteja perto demais
dela, ou que não seja
acentuada
demais.
Para
esquinas, as guias somem
rapidamente do ângulo de
visão da câmera. Sem
podermos virar a câmera com
algum tipo de motor, ou
termos algum outro sensor, o
algoritmo não consegue se
orientar. Para curvas menos
inclinadas a figura (c) mostra
sucesso até que a curva suma
do campo de visão da câmera.
6. Conclusões
O algoritmo implementado em Java se apresentou mais rápido que o algoritmo em MatLab,
por isso nos voltamos para a plataforma Java. Os filtros direcionais selecionaram com boa precisão os
valores de θ, e o filtro de Kalman foi capaz de reduzir drasticamente os problemas de flutuação da
transformada de Hough. O algoritmo conseguiu linearizar pequenas curvas, e nas curvas acentuadas
seria necessária alguma outra solução. A seqüência e parametrização mais adequadas para a detecção
de guias foram: clip();grayScale();gaussiana5;bisobel(1, 70, 15);hough(150, 150, 45, 10, 50, 5);
Com isso, pode-se dizer que a pesquisa feita a respeito de detecção de guias utilizando
variações da Transformada de Hough foi concluída com sucesso. Cabem agora próximas pesquisas a
respeito de como aplicar as informações obtidas com esses algoritmos na navegação de um robô
móvel de vigilância, ou em outras aplicações.
Agradecimentos
Agradeço ao professor Carlos Henrique Costa Ribeiro, ao técnico Ronaldo, do ITA, e ao
CNPq, órgão financiador desta pesquisa.
Referências Bibliográficas
1. Hanselman, D. C.; Littlefield, B.; “MATLAB 5: versão do estudante: guia do usuário”.
Makron Books, 1999.
2. Santos, R.; “Introdução à Programação Orientada a Objetos usando JAVA”, Editora Campus,
2003.
3. Deitel, H. M.; Deitel, P. J.; “Java Como Programar”, Editora Bookman, 4a. Edição, 2003.
4. Barros, R. A., “Implementação de métodos e classes de processamento de imagens para
sistema de navegação robótica”, Relatório Final PIBIC/CNPq, Instituto Tecnológico de
Aeronáutica, 2005.
5. Reineri, S., “Implementação e análise de algoritmos de tempo real para detecção de bordas em
navegação utilizando robô móvel de vigilância”, Relatório Final PIBIC/CNPq, Instituto
Tecnológico de Aeronáutica, 2005.
6. Dudek, G. e Jenkin, M. “Computational principles of Mobile Robotics”, Cambridge
University Press, 2000.
7. Russell, S. e Norvig, P.; “Inteligência Artificial”, Editora Campus, 2003.
6