Transformada Hough — Detectando formas geométricas em imagens
Olá, amável ser!
Nesta semana o Turing Talks se afasta um pouco dos tópicos de Inteligência Artificial para explorar uma técnica elementar de detecção em imagens: a Transformada Hough. Aqui você aprenderá como funciona um detector de formas geométricas parametrizáveis, além de como aplicá-lo para retas e círculos com OpenCV e Python.
Antes de abrir seu editor de código e pesquisar exemplos de aplicação, como eu sei que você faz quando quer aprender uma função nova, é interessante entender o funcionamento interno da técnica que vamos utilizar. Por isso, nesse primeiro texto explicaremos a teoria por trás dela e em um próximo artigo falaremos sobre a aplicação.
Então, pelo menos por agora, feche seu Vim, VSCode ou editor favorito, relaxe, e venha conosco nessa mágica viagem geométrica!
Transformada Hough Para Linhas
Antes de partir para círculos, é interessante começar com uma forma mais simples: a reta.
Mas o que é uma reta?
Retas não tem uma definição matemática clara, mas nós sabemos o que são e como representá-las. No ensino médio, ou até antes, aprendemos que podemos definir uma reta pela função y = a x + b.
Porém, aqui utilizaremos uma representação um pouco diferente, mas mais adequada para nossa aplicação, a equação polar:
Como é possível deduzir dos gráficos, o parâmetro r é a mínima distância da reta ao centro do plano e θ o ângulo de inclinação da normal (pontilhada) à reta.
Agora que temos uma boa representação, vamos a uma provocação. Como faríamos para achar todas as retas que passam por um ponto?
Na equação podemos substituir x e y pelas coordenadas do ponto e teríamos uma equação com duas incógnitas, r e θ.
Mas sabemos que seno e cosseno se repetem a cada 180, assim, se passarmos por todos os thetas até 180, encontraremos os r’s correspondentes e, por consequência, todas as retas que passam por aquele ponto.
Por fim, teremos um função que só depende de theta:
Com o que temos, já é possível procurar retas em imagens!
Vamos testar em um exemplo:
Sabemos que com a equação da reta nos possibilita encontrar todas as retas que passam por um ponto. Se utilizarmos a equação no ponto demarcado, teremos uma curva no espaço dos parâmetros.
Se fizermos isso para mais pontos teremos mais curvas:
No segundo gráfico é possível perceber que há vários pontos em que as curvas se encontram, mas dois deles saltam aos olhos. As coordenadas do ponto em que todas as curvas azuis se cruzam são r= 3 e θ = π/4, os quais representam os parâmetros da reta azul no primeiro gráfico. Podemos observar o mesmo no cruzamento das curvas laranjas, onde temos os parâmetros r=1 e θ=π/3.
Encontramos as duas retas da imagem!
Mas no segundo gráfico há alguns outros cruzamentos, como sabemos quais realmente representam parâmetros de retas na imagem original?
Para tal, utilizaremos o conceito de acumulador.
O acumulador é uma lista onde guardaremos todos os cruzamentos. Para detectar as retas escolheremos os cruzamentos com maiores recorrências no acumulador.
No nosso exemplo, se escolhermos somente cruzamentos entre 3 ou mais curvas, conseguiremos encontrar as duas retas e não teremos nenhuma falsa detecção. Esse limite de recorrência é uma escolha de projeto que pode variar de imagem pra imagem, seu ajuste mal feito pode causar falsas detecções ou falhas em detectar retas existentes.
O que descrevemos aqui é o funcionamento básico da Transformada Hough.
Transformada Hough Para Círculos
Para círculos se aplica a mesma técnica utilizada para as retas, mas com parâmetros diferentes.
Um círculo pode ser definido se obtivermos seu raio e as coordenadas de seu centro (xc, yc). Então, basta percorrer os pontos da imagem procurando os possíveis círculos com base nesses parâmetros.
Se um ponto pertence a uma circunferência ideal, o centro desta circunferência estará na direção normal a esse ponto.
Cada ponto na reta normal representa uma possivel cordenada do centro da circunferência. Quanto ao raio, basta medirmos a distância do ponto atual ao ponto na borda do círculo.
Como fizemos com as retas, também mapearemos os pontos da imagem à curvas no espaço dos parâmetros.
Para sabermos que aquele circulo realmente está na imagem utilizaremos o acumulador novamente. Parâmetros de circulos com muitas aparições no acumulador tem grandes chances de estarem presentes na imagem.
Como temos três parâmetros dessa vez (raio e coordenadas do centro) o espaço dos parâmetros é tridimensional. Isso torna o aprofundamento da explicação neste texto inviável. Entretanto, se você quer saber mais a fundo sobre a aplicação da transformada em círculos você pode dar uma olhada no paper da aplicação oficial utilizada no OpenCV (a qual falaremos no próximo texto).
Resumo
- Define-se uma equação ou conjunto de parâmetros para representar a forma geométrica a ser detectada (reta, circulo, elipse).
- Percorre-se a imagem mapeando seus pontos a uma curva nos espaço dos parâmetros escolhidos.
- Os pontos de intersecção presentes no espaço dos parâmetros são anotados no acumulador.
- Os parâmetros das retas presentes na imagem serão os dos pontos com maiores recorrência no acumulador.
Se a explicação ainda ficou muito confusa ou abstrata para você, espere a parte 2 deste texto, nela aplicaremos a Transformada Hough em imagens reais!
Finalmente, espero que você tenha gostado do texto de hoje e aprendido algo novo.
Para mais textos sobre Visão Computacional, IA e outros temas, continuem acompanhando o Turing Talks. E se quiser saber mais sobre o Grupo Turing siga a gente nas redes sociais: Facebook, Linkedin, Instagram, e servidor no Discord!
