Exercício 05

Detecção de retas usando a Transformada de Hough com backmapping

Introdução

O objetivo deste exercício é implementar a transformada de Hough com backmapping para detectar linhas retas em uma imagem. As retas são parametrizadas na forma rho = x * cos(theta) + y * sin(theta), onde rho é a distância normal da reta até a origem, e theta é o ângulo que a reta normal faz com o eixo x. A transformada de Hough mapeia pontos de coordenadas (x,y) em senóides no espaço de parâmetros (rho,theta). As senóides de pontos colineares se intersectam em (rho1, theta1), que correspondem aos parâmetros da reta a que pertencem tais pontos.

Método Utilizado

O programa foi desenvolvido usando o MATLAB versão 6.0.0.88 Release 12. Foram criadas as seguintes funções:

mi: função auxiliar para a implementação da transformada de Hough
normalhough: transformada normal de Hough (sem backmapping)
backhough: transformada de Hough com backmapping
reverse: a partir da matriz de acumuladores gerada pela transformada de Hough, gera uma imagem contendo as linhas retas correspondentes aos picos maiores que um dado limiar
hough: executa a transformada de Hough com backmapping sobre uma imagem e devolve uma imagem contendo as linhas retas detectadas

Para utilizar o programa, deve-se executar a função hough passando como argumentos a matriz contendo a imagem de entrada, a dimensão da matriz de acumuladores (Ntheta x Nrho) e o limiar thr que será usado para filtrar os picos maiores na matriz de acumuladores. Como resultado da função, teremos uma imagem binária contendo as linhas retas detectadas.

Um exemplo de utilização do MATLAB para ler uma imagem, detectar as linhas retas presentes nela e guardar o resultado em outro arquivo seria:


>> threshold = 5;

>> Ntheta = 300;

>> Nrho = 300;

>> img = imread('img_entrada.bmp');

>> lines = hough(img, Ntheta, Nrho, threshold); 

>> imwrite(lines, 'retas.bmp');

O código do EP como um todo pode ser obtido aqui.

Resultados

Os resultados da execução do programa em algumas imagens (1 e 2) podem ser vistos abaixo, para Nrho = Ntheta = 300.
A primeira imagem é binária e a segunda é em níveis de cinza entre 0 e 255.

Imagem de entrada e sobreposição às linhas retas detectadas, para thr = 20

Imagem com ruído, e linhas retas detectadas para thr = 5, 7 e 10

Na execução do exemplo com threshold 7, as matrizes de acumuladores (Transformada de Hough) obtidas sem e com backmapping foram:

Transformada de Hough normal

Conclusão

Através deste exercício foi possível comprovar a eficácia da Transformada de Hough na detecção de linhas retas em uma imagem, e sua robustez quanto à presença de ruído nas imagens. A utilização de backmapping permite maior robustez na detecção dos picos que representam as linhas retas no espaço de parâmetros (rho, theta).

Porém, a transformada em si não detecta os extremos das linhas retas existentes na imagem. Para isto, existem técnicas de análise de conectividade descritas no livro. Neste exercício a implementação destas técnicas não foi realizada.

Outro fator importante a considerar é a complexidade computacional da transformada de Hough. A execução do programa mostrou que a transformada pode não ser adequada para detecção de objetos com um espaço de parâmetros de dimensão maior ou para imagens muito grandes, devido ao grande número de operações realizadas.

Bibliografia

R. M. Cesar Jr e L. F. Costa. Shape analysis and classification: Theory and Practice. CRC Press, 2001, seção 5.6.

Daniel André Vaquero
daniel at linux.ime.usp.br
Thu, 6 Nov 2003 00:20:40 -0200