Informações

Curriculo...

Publicações

Pesquisa

Projetos

Ensino de Graduação

Ensino de Pós Graduação 

  • Visão Computacional
    • Cursos

    Você lê?
    Seminário Visão Computacional - CPGCC/UFSC - 2000.2

    Reconhecimento de Formas: A Transformada de Hough

    Teobaldo Jamundá





    Introdução

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

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

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

    Definição 

    A transformada de Hough (HT) é um método padrão para detecção de formas que são facilmente parametrizadas (linhas, círculos, elipses, etc.) em imagens computacionais. Em geral, a transformada é aplicada após a imagem sofrer um pré-processamento, comumente a detecção de bordas.

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

    Visão Geral

    Uma imagem computacional (digitalizada) é formada por um conjunto de pontos que possuem determinadas características, os quais são chamados de pixels.

    A transformada de Hough consiste em mapear um pixel da imagem em uma curva no espaço de parâmetros, organizado em forma de um acumulador n dimensional, onde n corresponde ao número de parâmetros.

    Técnica da Transformada de Hough

    Há várias parametrizações possíveis para o espaço de linhas. Hough usou a equação declive-intercepte, definida por y = a.x + b,como representação paramétrica de uma linha (figura 1), o que conduziu a dificuldade prática de um espaço de parâmetro ilimitado para linha que são paralelas ao eixo y, cuja solução será abordada posteriormente.
     

    Figura 1 – representação da equação da reta (declive-intercepte)

    O algoritmo de Hough requer um acumulador de dimensão igual ao número de parâmetros desconhecidos na equação da família de curvas que são buscadas. Por exemplo, achar segmentos de linhas usando a equação y = ax + b requer achar dois parâmetros para cada segmento: ae b.As duas dimensões da matriz acumuladora para esta família correspondem aos valores ‘quantizados’ para ae b.

    Assim, usando uma matriz acumuladora A, o procedimento de Hough examina cada pixel e calcula os parâmetros da curva (equação) especificada que passa pelo pixel. Caso esteja analisando uma imagem que não foi pré-processada com algoritmo de detecção de bordas, fato incomum na transformada de Hough, será examinado o pixel e sua vizinhança na imagem, para determinar se há evidência de extremidade naquele pixel. Somente se houver realizar-se-á o calculo dos parâmetros.

    Após calculados os parâmetros de um determinado pixel, eles são ‘quantizados’ para um valor correspondente ae b, e o acumulador A(a , b) é incrementado.

    Quando todos pixels tiverem sido processados, é procurado no acumulador A os maiores valores (picos). Eles indicam os parâmetros de prováveis linhas na imagem.

    Abaixo é demonstrado um pequeno exemplo utilizando a técnica supracitada, cujo cálculo é realizado apenas para dois pixels pertencentes a uma linha (reta) de uma imagem, apresentada na figura 2a, (plano x-y ou espaço real). Na figura 2b (plano a-b ou espaço de Hough), pode-se verificar as linhas geradas pelos parâmetros calculados, onde a linha verde refere-se ao ponto (1,1) e a azul ao ponto (2,2) do plano x-y.


    Figura 2a – Plano x-y ( imagem ) 


    Figura 2b – Plano a-b ( parâmetros ) 

    Para este exemplo foi estipulado o intervalo [-2, 3] para a, e empregado os valores de x e y do pixel que está sendo examinado na equação b = -ax + y, possibilitando o cálculo do valor de b. Os valores são utilizados para incrementar o referido elemento do acumulador A(a , b) e traçar uma reta no plano a-b . Segue o quadro 1, mostrando os valores utilizados e os parâmetros obtidos.
     
     
    X
    y
    a
    b = -a.x + y
    Acumulador A(a , b)
    incrementado
    1
    1
    -2
    3
    A (-2, 3)
    1
    1
    -1
    2
    A (-1, 2)
    1
    1
    0
    1
    A ( 0, 1)
    1
    1
    1
    0
    A (1, 0) *
    1
    1
    2
    -1
    A (2, -1)
    1
    1
    3
    -2
    A (3, -2)
    2
    2
    -2
    6
    A (-2, 6)
    2
    2
    -1
    4
    A (-1, 4)
    2
    2
    0
    2
    A ( 0, 2)
    2
    2
    1
    0
    A (1, 0) *
    2
    2
    2
    -2
    A (2, -2)
    2 
    2
    3
    -4
    A (3, -4)
    * único elemento do acumulador que é incrementado 2 vezes, indicando colinearidade entre esses pontos.

    Quadro 1 – Cálculo do parâmetro b e indicação do elemento incrementado no acumulador A.

    Ao procurar o máximo no acumulador A(a , b), verifica-se que este indicará o elemento referenciado por a = 1e b = 0. Isto significa que a equação y = 1.x + 0, ou simplesmente y = x, é a equação que melhor define uma reta que passa sobre os pontos (1,1) e (2,2) da imagem. Tendo esta informação faz-se um pós-processamento para determinar onde começa e termina a reta encontrada, caso haja interesse.

    Um limiar pode ser utilizado quando procura-se o(s) máximo(s) no acumulador, a fim de determinar um valor mínimo de pontos colineares. Se o valor do acumulador não for superior ao do limiar então será considerado um ruído.

    As detecções de outras formas utilizando a transformada de Hough usam o mesmo princípio, há somente alteração no número de parâmetros da equação que será empregada, e em conseqüência na dimensão do acumulador.
     

    Linha


    Duda e Hart [1] utilizaram coordenada polar para representação de uma linha. Sugeriram que linhas poderiam ser completamente parametrizadas usando o comprimento, r , e a orientação, q, do vetor normal para a linha da imagem original (figura 3). Usando esta parametrização, todo o ponto (x,y) na linha satisfará a equação r= x . cos ( q ) + y . sin ( q ).

    Figura 3 – representação da equação da reta (coordenada polar)

    Computa-se a transformada de Hough dos pixels da imagem, registrando os resultados em um histograma (matriz) bidimensional. Cada pixel (x,y) do espaço real produz uma linha senoidal no espaço de Hough. A linha no espaço de Hough parecerá como mostrado na figura 4, para representação de Duda-Hart. 


    Figura 4 – Imagem original e representação dos pontos (1,1), (2,2) e (3,3) no espaço de Hough.

    O histograma torna-se complicado quando a imagem contiver muitas linhas, com máximos múltiplos, dos quais muitos não correspondem à linhas, mas a ruídos. Assim deve-se interativamente descobrir a maior linha da imagem, remover sua contribuição do histograma, e então repetir o processo para achar sucessivamente a maior das linhas restantes. A cada repetição acha-se o máximo global e obtém-se a equação da linha correspondente. Um simples pós-processamento pode ser usado para achar os pontos de começo e fim de cada linha. 

    Círculos 

    Será apresentada uma implementação sugerida por E. R. Davies [2]. Círculos são parametrizados por (x, y, r), onde (x, y) referem-se a posição de centro e r ao raio, conforme figura 5 abaixo.


    Figura 5 – Representação geométrica de um círculo

    Para evitar as exigências computacionais da transformada de Hough 3-D, o problema é organizado em duas fases: 

    1. achar o centro de todos círculos;

    2. achar o raio de cada círculo.

    Note que dado qualquer pixel em um círculo, o centro do círculo correspondente localiza-se sobre a normal da tangente daquele pixel. Assim, dado vários pixels do mesmo círculo, a normal deles cruzarão o centro do círculo. Assim, definindo-se um histograma em cima de (x,y) no espaço de parâmetros, achar-se-á o centro que é correspondente à imagem. Para cada pixel pode-se calcular a tangente como a linha que se ajusta melhor a todos pixels de uma vizinhança pequena (usando o método mínimos-quadrado). Isto permite calcular a normal e registrá-la no histograma. Os máximos do histograma dão os locais de centros dos possíveis círculos. O próximo passo é achar o raio correspondente ao centro (ou raio para círculos múltiplos, centrados no mesmo local). Faz-se isso através de um histograma para cada centro. Ou seja, para todo pixel na imagem computa-se sua distância até o centro de determinado círculo. Esta distância é registrada em um histograma unidimensional (vetor). O máximo dos histogramas correspondem aos raios dos círculos. Finalmente deve-se aplicar um passo de pós-processamento para decidir se os parâmetros encontrados correspondem a um círculo na imagem.
     

    Elipses


    Uma elipse é definida por cinco parâmetros, porém cinco parâmetros na Transformada de Hough é inviável computacionalmente e requer muita memória. Então será mostrado abaixo a aproximação de Yuen que separa a tarefa em duas passagens: 

    1. identificação do centro da elipse, isto requer dois parâmetros da Transformada de Hough. 

    2. avaliação dos outros três parâmetros (referentes aos eixos) usando uma simples implementação focada da Transformada de Hough .

         O centro da elipse pode ser definido como segue. Considere dois pontos P e Q (veja figura 6) em uma elipse e calcule as tangentes destes pontos. Onde r é o ponto onde estas tangentes cruzam-se e M o ponto central do segmento PQ. Para uma elipse perfeita, o centro ficará sobre a linha que origina em r e passa por M. Linhas formadas por pares diferentes de pontos da elipse cruzar-se-ão no centro da mesma. Esses parâmetros da transformada de Hough são usados para acumular estas linhas, sendo que o máximo do histograma corresponderá a interseção das mesmas. Como este algoritmo registra uma entrada para cada par de pixel na imagem, é computacionalmente muito exigido.


    Figura 6 – Representação geométrica de uma elipse

    Pode-se aplicar um pós-processo semelhante ao usado para círculos, objetivando diferenciar parâmetros gerados por uma elipse na imagem dos gerados por ruído. Para fazer isso, conta-se o número de pixels que ficam próximo de cada elipse e dividi-se pelo perímetro da elipse. Se a relação estiver abaixo de um valor limiar, descarta-se como ruído. 

    Abaixo, as figuras 7a, 7b e 7c mostram um exemplo da aplicação da transformada de Hough para detecção de elipses. A figura 7a mostra uma imagem real de 256 x 256 x 8-bit. A figura 7b mostra os resultados de aplicar o operador de detecção de bordas Canny, e a figura 7c mostra as elipses detectadas (em branco). 
     

    Figura 7a - Original 
    Figura 7b - Após detecção bordas 
    Figura 7c - Elipses detectadas

    Variações na Implementação da Transformada de Hough


    a) Transformada Probabilística de Hough

    Introduzida em 1990 por N. Kiryati, Y. Eldar e A. M. Bruckshtein. A transformada probabilística afirma que para descobrir objetos é suficiente computar a transformada de Hough só de uma proporção a (0% < a £ 100%) de pixels na imagem. Estes pixels são randomicamente escolhidos de acordo com uma função de densidade de probabilidade uniforme, definida em cima da imagem. Isto é equivalente a computar a transformada padrão de uma amostra da imagem.

    b) Transformada Randômica de Hough

    Inventada em 1989 por Lei Xu, Erkki Oja e Pekka Kultanen. Considere a detecção de uma linha. Um par de pixel é randomicamente escolhido, e os parâmetros da linha que passam através desses pixels são computados. Esta linha é registrada como uma entrada no histograma. Este procedimento é repetido um número predeterminado de vezes, onde o número de vezes é bem menor que a quantidade de pares de pixels da imagem. Este algoritmo é repetido para cada segmento de linha a ser detectado. Assim o máximo do histograma é achado, e a equação da linha é computada. Então, os pixels da imagem sob essa linha são removidos, sobrando uma imagem mais simples para ser analisada. O processo é repetido para encontrar a próxima linha; e somente pára quando nenhuma linha for detectada em um determinado número de iterações. 

    c) Transformada Hierárquica de Hough

    O algoritmo é baseado em uma estrutura de pirâmide, onde cada camada divide a imagem em sub-imagens. A pirâmide convencional é confeccionada com P+1 níveis. Em cada nível l, a imagem é dividida em 2P-1 x 2P-1 sub-imagens, onde P é o nível superior da pirâmide, representando a imagem completa. No nível inferior da pirâmide, pequenos segmentos de linhas são detectados através da transformada de Hough em uma pequena sub-imagem, facilitando a diferenciação entre linhas ‘reais’ e pontos casualmente alinhados. O método é também relativamente eficiente, já que somente um pequeno vetor acumulador é necessário para representar todas possíveis linhas que passam através da sub-imagem.

    Tipicamente cada sub-imagem contém duas linhas. Esses resultados são propagados através da pirâmide, para obter-se a representação global dos segmentos de linha, formados a partir do agrupamento de linhas existentes nas sub-imagens. 

    d) Transformada Combinatorial de Hough

    Foi apresentada por D. Ben Tzvi e M. B. Sandler em 1989, como a forma mais eficiente de calcular-se a Transformada de Hough. Cada 2 pontos na imagem indicam uma possível colinearidade. Se (r0 ,q0), são os parâmetros que descrevem a linha que une os dois pontos, então os parâmetros do segmento de linha podem ser derivados da equação paramétrica r= x . cos ( q ) + y . sin ( q ), dados os pontos (x1 , y1) e (x2 , y2).

    1) r0 = x1 . cos ( q0 ) + y1 . sin ( q0 )

    2) r0 = x2 . cos ( q0 ) + y2 . sin ( q0 )

    Subtraindo as duas equações acima temos: qo = arctan ( D x / D y )

    Para determinar se qualquer parte de um conjunto m de pontos é colinear, todas as possíveis combinações de segmentos de linha entre dois pontos precisam ser calculadas.

    C m 2 = m! / (2!(m-2)!) 

    Cada um destes cálculos, cada par de ponto, contribui para o incremento do acumulador na posição (r0 ,q0).
     
     

    Conclusão


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

    A transformada de Hough é um método de acumulação de requisitos muito geral, possibilitando detectar qualquer curva, mesmo pouco visível ou fortemente ruidosa
     
     

    Referências Bibliográficas

    [1] Duda, R. and Hart, P. - Use of the Hough transformation to detect lines and curves in pictures. Comm. of ACM 15, 1. 11-15; 1972
    [2] Davies E.R - Image space transform for detecting straight edges in industrial images, Pattern Recognition Letters, 4, 185-192; 1986 

     

     

    [3] H. K. Yuen, J. Illingworth, and J. Kittler - Detecting partially occluded ellipses using the Hough transform, Image and Vision Computing, vol. 7, no. 1, pp. 31-37, Feb 1989. 

    [5] http://ciips.ee.uwa.edu.au/~ram/papers/Tech_Reports

    [6] http://w3.mor.itesm.mx/~giovani/soluciones/soluciones.html

    [7] http://www.cs.technion.ac.il/~aer/Vision/Hough/

    Applets Java ( demonstração – linhas e círculos )

    Contato:
    Tel.: +55-48-331 7552/9498
    FAX: +55-48-331-9770
    awangenh@inf.ufsc.br