A transformada de Hough é uma técnica de extração de características usada em análise de imagens, visão computacional, reconhecimento de padrões e processamento digital de imagens. Seu propósito é encontrar instâncias imperfeitas de objetos dentro de uma certa classe de formas por meio de um procedimento de votação. Esse procedimento de votação é realizado em um espaço de parâmetros, a partir do qual candidatos a objetos são obtidos como máximos locais em um espaço acumulador explicitamente construído pelo algoritmo. Matematicamente, é a transformada de Radon no plano, conhecida desde pelo menos 1917, mas a transformada de Hough refere-se especificamente ao seu uso em análise de imagens.
A transformada de Hough clássica preocupava-se em identificar linhas em uma imagem, mas desde então foi estendida para identificar posições de formas arbitrárias, mais comumente círculos ou elipses. A transformada como universalmente usada hoje foi inventada por Richard Duda e Peter Hart em 1972, que a chamaram de "transformada de Hough generalizada" após a patente relacionada de Paul Hough de 1962. Foi popularizada na comunidade de visão computacional por Dana H. Ballard por meio de um artigo de jornal de 1981 intitulado "Generalizing the Hough transform to detect arbitrary shapes."
História
A transformada de Hough foi inicialmente inventada para análise automática de fotografias de câmaras de bolhas por Paul Hough em 1959. Foi patenteada como patente dos EUA 3.069.654 em 1962 e atribuída à Comissão de Energia Atômica dos EUA sob o nome "Método e Meios para Reconhecer Padrões Complexos". Essa patente usava uma parametrização de inclinação-intercepto para linhas retas, o que levava de forma incômoda a um espaço de transformação ilimitado, pois a inclinação pode tender ao infinito.
A parametrização rho-theta universalmente usada hoje foi descrita pela primeira vez em um artigo de 1972 de Richard Duda e Peter Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures", publicado na Communications of the ACM. Essa parametrização já era padrão para a transformada de Radon desde pelo menos a década de 1930. Frank O'Gorman e M.B. Clowes publicaram uma variação em 1976 na IEEE Transactions on Computers, intitulada "Finding Picture Edges Through Collinearity of Feature Points". A história de como a forma moderna foi inventada é detalhada no artigo de Peter Hart de 2009 "How the Hough Transform was Invented" na IEEE Signal Processing Magazine.
Teoria
Na análise automatizada de imagens digitais, um subproblema frequentemente surge de detectar formas simples, como linhas retas, círculos ou elipses. Um detector de bordas pode ser usado como estágio de pré-processamento para obter pontos de imagem na curva desejada. No entanto, devido a imperfeições nos dados da imagem ou no detector de bordas, pode haver pontos ausentes ou desvios espaciais entre a forma ideal e pontos de borda ruidosos. A transformada de Hough aborda isso realizando um procedimento explícito de votação sobre um conjunto de objetos de imagem parametrizados, tornando possível agrupar pontos de borda em candidatos a objetos.
Detecção de Linhas
O caso mais simples é a detecção de linhas retas. Em geral, uma linha y = mx + b pode ser representada como um ponto (b, m) no espaço de parâmetros, mas linhas verticais apresentam um problema devido a valores de inclinação ilimitados. Duda e Hart propuseram usar a forma normal de Hesse: r = x cos(theta) + y sin(theta), onde r é a distância da origem ao ponto mais próximo na linha, e theta é o ângulo entre o eixo x e a linha que conecta a origem a esse ponto mais próximo. Cada vetor na linha é perpendicular ao segmento de linha de comprimento r da origem. O ponto de interseção está em P0 = (r cos(theta), r sin(theta)). Para qualquer ponto P na linha, o vetor P - P0 deve ser ortogonal a P0, impondo (P - P0) ponto P0 = 0, o que simplifica para r(x cos(theta) + y sin(theta)) = r^2(cos^2(theta) + sin^2(theta)).
Algoritmo e Procedimento de Votação
Na prática, a transformada de Hough discretiza o espaço de parâmetros em um array acumulador. Para cada ponto de borda na imagem, o algoritmo calcula todos os valores possíveis de parâmetros (por exemplo, r e theta para linhas) que poderiam corresponder a uma forma passando por aquele ponto, e incrementa as células acumuladoras correspondentes. Após processar todos os pontos, máximos locais no acumulador indicam prováveis candidatos a formas. Esse procedimento de votação é robusto a ruído e dados ausentes, pois não exige que todos os pontos em uma forma estejam perfeitamente alinhados.
Extensões e Aplicações
A transformada de Hough generalizada, introduzida por Dana Ballard em 1981, estende a técnica a formas arbitrárias usando um ponto de referência e uma tabela de orientações de borda. Isso permite a detecção de formas complexas além de linhas, círculos e elipses. A transformada tem sido amplamente aplicada em campos como direção autônoma, imagem médica e inspeção industrial. Em sistemas de Computer vision, é frequentemente combinada com algoritmos de detecção de bordas para identificar objetos em pipelines de processamento digital de imagens. Sua base matemática na transformada de Radon a conecta a técnicas mais amplas de análise de imagens usadas em aplicações de aprendizado de máquina e inteligência artificial.
Limitações e Variantes
Uma limitação da transformada de Hough clássica é seu custo computacional, especialmente para espaços de parâmetros de alta dimensão. Variantes como a transformada de Hough probabilística e a transformada de Hough circular foram desenvolvidas para melhorar a eficiência. A versão probabilística amostra um subconjunto de pontos de borda para reduzir a computação, enquanto a transformada circular usa um espaço de parâmetros tridimensional (centro x, centro y, raio). Essas variantes são comumente implementadas em bibliotecas como opencv e são usadas em sistemas de tempo real, incluindo aqueles em veículos autônomos e robótica.
Ver Também
- transformada de radon
- detecção de bordas
- visão computacional
- processamento de imagens