Detecção de círculos (elipses) na nuvem de pontos 2D

14

Dado um conjunto de pontos (2D) ou seja, nuvem de pontos (PC), a pergunta é sobre um robust, accuratee computing-friendlymétodo para encontrar círculos (ou elipses em versão avançada).

A idéia intuitiva é usar a Pesquisa de força bruta em todos os pontos possíveis (como centro) {infinito!} E raios (novamente infinito!). Isso é extremamente extremamente lento e ineficiente.

Conforme demonstrado abaixo, cada círculo ajustado seria classificado com base no número de pontos ( nn) posicionados na circunferência do círculo a uma distância menor que um limite ( t). Portanto, há derrpara apresentar uma distância média.

De forma avançada, elipses são de interesse para serem ajustadas.

Alguma idéia, invadir o cérebro, experiências, comentários? insira a descrição da imagem aqui

Desenvolvedor
fonte
Boa pergunta. Qual programa você usou para gerar esse diagrama?
Jason R
@JasonR Como sempre, Python + MatPlotLib .
Developer

Respostas:

14

As melhores idéias que exatamente tentam resolver esse problema são as transformações de Hough .

Basicamente, o sinal no espaço ocupado será r, x, ycoordenado. Aqui r significa raio e x,ysignifica centro. Todos os pontos podem pertencer a um ou muitos círculos. Portanto, no plano Hough, percorra todos os círculos possíveis onde esse ponto poderia pertencer e faça um +1. Esta não é uma pesquisa, apenas uma coleção.

Agora, se um círculo real existir, muitos pontos serão adicionados e a pontuação desse r, x, yserá muito maior do que todos os outros. Selecionar esse ponto permitirá que você escolha os círculos certos.

Aqui está um artigo clássico de 1971 (antes de eu nascer!) Que inventou esse conceito.

  1. USO DO TRASFORMAMENTO HOUGH PARA DETECTAR LINHAS E CURVAS EM FOTOS Por: Richard O. Duda, Peter E. Hart Tech, relatório de Inteligência Artificial Cente, abril de 1971.

Para o Tutorial, sugiro referências abaixo:

  1. HIPR2 -Link
  2. Amos storkey
  3. Referência IDL

Especificamente para detecção de círculo, você pode consultar isso abaixo:

  1. AI Shack
  2. Relatório Técnico da Chicago Univ.
  3. Notas de aula do Instituto Rochester

Esses métodos são muito eficientes e muito amigáveis ​​ao computador.

Dipan Mehta
fonte
1
Posso garantir os artigos da AI Shack, eles realmente ajudam a entender a matemática mais rigorosa que você lerá em outros lugares.
Ivo Flipse
1
Boa resposta. Eu já estou familiarizado com o Hough Transform (HT). O que eu usei foi para detecção de linhas. Houve um pouco de dificuldade para determinar os segmentos de linha. Foi recomendado o uso da Probabilistic Hough Transform (PHT). Não tive uma ideia clara sobre a extensão. Eu pensei que pode ser tão complexo para círculos ou aparecer outras dificuldades. Em relação às minhas experiências, o HT é bom, mas não perfeito. Também é minha preocupação como estender o HT para 3D. Vou tentar revisar os links fornecidos. Sua resposta é bastante boa para ser candidato como resposta.
Developer
AI Shack, e Tech Report de Chicaco ligações estão mortos
Mehdi