Um Implementação da Um Implementação da Transformada de Hough Transformada de Hough

Para Detecção de Linhas e Para Detecção de Linhas e Círculos Círculos

Professor: Antônio A. F. OliveiraProfessor: Antônio A. F. Oliveira

Alunos: Carlos Henrique da C. CavalcantiAlunos: Carlos Henrique da C. Cavalcanti

Leonardo Oliveira B. de CarvalhoLeonardo Oliveira B. de Carvalho

Tópicos Abordados:Tópicos Abordados: O que é a Transformada de HoughO que é a Transformada de Hough A Transformada de Hough para A Transformada de Hough para

detecção de retasdetecção de retas A Transformada de Hough para A Transformada de Hough para

detecção de círculos no Matlabdetecção de círculos no Matlab Observações FinaisObservações Finais PerguntasPerguntas BibliografiaBibliografia

A Transformada de HoughA Transformada de Hough Introdução :Introdução :

A Transformada de Hough foi desenvolvida por Paul A Transformada de Hough foi desenvolvida por Paul Hough em 1962 e patenteada pela IBM. Hough em 1962 e patenteada pela IBM.

Originalmente, foi elaborada para detectar Originalmente, foi elaborada para detectar características analiticamente representáveis em características analiticamente representáveis em imagens binarizadas, assim como linhas, círculos e imagens binarizadas, assim como linhas, círculos e elipses. elipses.

Na última década tornou-se uma ferramenta de uso Na última década tornou-se uma ferramenta de uso comum na visão artificial para o reconhecimento destas comum na visão artificial para o reconhecimento destas características.características.

A Transformada de HoughA Transformada de Hough Definição :Definição :

A Transformada de Hough (TH) é um método padrão para A Transformada de Hough (TH) é um método padrão para detecção de formas que são facilmente parametrizadas detecção de formas que são facilmente parametrizadas (linhas, círculos, elipses, etc.) em imagens digitalizadas. (linhas, círculos, elipses, etc.) em imagens digitalizadas.

O conceito principal da TH está em definir um O conceito principal da TH está em definir um mapeamento entre o espaço de imagem e o espaço de mapeamento entre o espaço de imagem e o espaço de parâmetros. Cada borda de uma imagem é transformada parâmetros. Cada borda de uma imagem é transformada por esse mapeamento para determinar células no espaço por esse mapeamento para determinar células no espaço de parâmetros, indicadas pelas primitivas definidas de parâmetros, indicadas pelas primitivas definidas através do ponto analisado. Essas células são através do ponto analisado. Essas células são incrementadas, e indicarão no final do processo, através incrementadas, e indicarão no final do processo, através da máxima local de um acumulador, quais os parâmetros da máxima local de um acumulador, quais os parâmetros correspondentes a forma especificada.correspondentes a forma especificada.

A Transformada de HoughA Transformada de Hough

A idéia é aplicar na imagem uma transformação tal que A idéia é aplicar na imagem uma transformação tal que todos os pontos pertencentes a uma mesma curva sejam todos os pontos pertencentes a uma mesma curva sejam mapeados num único ponto de um novo espaço de mapeados num único ponto de um novo espaço de parametrização da curva procurada.parametrização da curva procurada.

A Transformada de HoughA Transformada de Hough Um passo necessário no processo de aplicação da TH é a Um passo necessário no processo de aplicação da TH é a

detecção de bordas e a limiarização. Foi usado do método de detecção de bordas e a limiarização. Foi usado do método de CannyCanny para a realização desta tarefa. A detecção de bordas para a realização desta tarefa. A detecção de bordas e a escolha de um limiar ótimo pode ser realizada por meio e a escolha de um limiar ótimo pode ser realizada por meio de métodos existentes na literatura.de métodos existentes na literatura.

A Transformada de HoughA Transformada de Hough Variações da Transformada de Hough:Variações da Transformada de Hough:

– Transformada Probabilística de Hough Transformada Probabilística de Hough

– Transformada Randômica de Hough Transformada Randômica de Hough

– Transformada Hierárquica de Hough Transformada Hierárquica de Hough

– Transformada Combinatorial de HoughTransformada Combinatorial de Hough

A Transformada de Hough A Transformada de Hough Para Detecção de RetasPara Detecção de Retas

Utilizamos coordenadas polares para representação de Utilizamos coordenadas polares para representação de uma reta. uma reta.

Supondo Supondo rr o comprimento da reta e o comprimento da reta e qq a orientação do a orientação do vetor normal da reta, para todo o ponto (x,y) vetor normal da reta, para todo o ponto (x,y) pertencente a reta, temos que a equação pertencente a reta, temos que a equação r= x . cos ( q r= x . cos ( q ) + y . sin ( q )) + y . sin ( q ) é satisfeita.é satisfeita.

A TH dos pixels da imagem é registrada em um A TH dos pixels da imagem é registrada em um histograma (matriz) bidimensional. Cada pixel (x,y) do histograma (matriz) bidimensional. Cada pixel (x,y) do espaço real produz uma curva senoidal no espaço de espaço real produz uma curva senoidal no espaço de Hough.Hough.

Vamos ver um exemploVamos ver um exemplo

A Transformada de Hough A Transformada de Hough para detecção de círculos no para detecção de círculos no

MatlabMatlab Para a detecção de círculos em imagens, foi utilizado o Para a detecção de círculos em imagens, foi utilizado o

software MATLAB.software MATLAB. Foi usado um processo de eleição de círculos onde os Foi usado um processo de eleição de círculos onde os

votos são atribuídos aos pontos de passagem dos votos são atribuídos aos pontos de passagem dos possíveis círculos existentes na imagem. possíveis círculos existentes na imagem.

Os votos são acumulados em uma matriz de Os votos são acumulados em uma matriz de acumulação de votos, sendo que a detecção de um acumulação de votos, sendo que a detecção de um possível círculo é obtida quando um valor máximo possível círculo é obtida quando um valor máximo (cume) é obtido no acumulador de votos. (cume) é obtido no acumulador de votos.

A pesquisa nos pixels da imagem binária que contém as A pesquisa nos pixels da imagem binária que contém as bordas da imagem original é feita utilizando-se a bordas da imagem original é feita utilizando-se a definição matemática abaixo, onde a e b são as definição matemática abaixo, onde a e b são as coordenadas do centro do círculo e r é o raio do círculo.coordenadas do centro do círculo e r é o raio do círculo.

(x - a)2 + (y - b)2 = R2(x - a)2 + (y - b)2 = R2

A Transformada de Hough A Transformada de Hough para detecção de círculos no para detecção de círculos no

MatlabMatlab

Assim, o algoritmo inicia com a leitura da imagem original, Assim, o algoritmo inicia com a leitura da imagem original, convertendo-se esta imagem para tons de cinza, usando-se convertendo-se esta imagem para tons de cinza, usando-se logo a seguir, o método de Canny para a obtenção da logo a seguir, o método de Canny para a obtenção da imagem binária que contém os pixels das bordas da imagem. imagem binária que contém os pixels das bordas da imagem.

O usuário deve fornecer, além da imagem, os parâmetros O usuário deve fornecer, além da imagem, os parâmetros raioraio (raio dos círculos a serem encontrados na imagem) e (raio dos círculos a serem encontrados na imagem) e dist dist (resolução da matriz de acumulação de votos).(resolução da matriz de acumulação de votos).

Para nosso exemplo considere raio=10 e dist=3Para nosso exemplo considere raio=10 e dist=3

A Transformada de Hough A Transformada de Hough para detecção de círculos no para detecção de círculos no

MatlabMatlab

Imagem OriginalImagem Original Imagem BinarizadaImagem Binarizada Bordas da ImagemBordas da Imagem

A imagem está pronta para aplicarmos a Transformada de A imagem está pronta para aplicarmos a Transformada de HoughHough

A Transformada de Hough A Transformada de Hough para detecção de círculos no para detecção de círculos no

MatlabMatlab

Projeção da TransformadaProjeção da Transformada Domínio da TransformadaDomínio da Transformada

A Transformada de Hough A Transformada de Hough para detecção de círculos no para detecção de círculos no

MatlabMatlab

Imagem com os círculos detectados de raio R = 10 :Imagem com os círculos detectados de raio R = 10 :

Observações FinaisObservações Finais O método da Transformada de Hough para detecção de O método da Transformada de Hough para detecção de

bordas é aplicável quando se possui informações precisas bordas é aplicável quando se possui informações precisas acerca da forma da curva. Os dados de base da acerca da forma da curva. Os dados de base da Transformada de Hough são geralmente pontos de uma Transformada de Hough são geralmente pontos de uma imagem obtidos através das transformações de gradiente e imagem obtidos através das transformações de gradiente e da limiarização. da limiarização.

A Transformada de Hough é um método de acumulação de A Transformada de Hough é um método de acumulação de requisitos muito geral, possibilitando detectar qualquer requisitos muito geral, possibilitando detectar qualquer

curva, mesmo pouco visível ou fortemente ruidosa.curva, mesmo pouco visível ou fortemente ruidosa. O método pode ser expandido para a determinação de O método pode ser expandido para a determinação de

outras formas geométricas, desde que a sua equação seja outras formas geométricas, desde que a sua equação seja conhecida (bastariam algumas alterações na função conhecida (bastariam algumas alterações na função implementada).implementada).

PerguntasPerguntas

Nosso muito obrigado a Nosso muito obrigado a todos. A nossos amigos todos. A nossos amigos Rodrigo Morante e Vitor Rodrigo Morante e Vitor Vasconcelos Vasconcelos pelas dúvidas pelas dúvidas tiradas.tiradas.

Valeu.Valeu.

BibliografiaBibliografia

Papers e Livros:Papers e Livros: A Space-Efficiente Hough Transform Implementation for A Space-Efficiente Hough Transform Implementation for

Object Detection - Chistopher M. Brown - Computer Object Detection - Chistopher M. Brown - Computer Science Departament - University of Rochester - Science Departament - University of Rochester - Rochester, NYRochester, NY

Uso da Transformada de Hough na Detecção de Circulos Uso da Transformada de Hough na Detecção de Circulos em Imagens Digitais - Glaucius Décio Duarte - Prof.. em Imagens Digitais - Glaucius Décio Duarte - Prof.. Adjunto da ESIN/UCPel, Pelotas - RS - BrasilAdjunto da ESIN/UCPel, Pelotas - RS - Brasil

Matlab - Image Processing Toolbok - The Mathworks Inc.Matlab - Image Processing Toolbok - The Mathworks Inc. Sites:Sites: http://www.inf.ufsc.br/~visao/2000/Hough/http://www.inf.ufsc.br/~visao/2000/Hough/