Detectar padrões circulares nos dados da nuvem de pontos

10

Para algum algoritmo de reconstrução de volume em que estou trabalhando, preciso detectar um número arbitrário de padrões circulares nos dados de pontos 3D (provenientes de um dispositivo LIDAR). Os padrões podem ser arbitrariamente orientados no espaço e supõe-se que estejam (embora não perfeitamente) em planos 2d finos. Aqui está um exemplo com dois círculos no mesmo plano (embora lembre-se de que este é um espaço 3d):

insira a descrição da imagem aqui

Eu tentei muitas abordagens .. a mais simples (mas a que funciona melhor até agora) é agrupar com base em conjuntos separados do gráfico do vizinho mais próximo. Isso funciona razoavelmente bem quando os padrões estão distantes, mas menos com círculos como os do exemplo, muito próximos um do outro.

Eu tentei o K-means, mas não dá certo: suspeito que o arranjo de pontos circulares talvez não seja adequado. Além disso, tenho o problema adicional de não conhecer antecipadamente o valor de K.

Tentei abordagens mais complicadas, com base na detecção de ciclos no gráfico do vizinho mais próximo, mas o que obtive foi muito frágil ou computacionalmente caro.

Também li sobre muitos tópicos relacionados (transformação de Hough, etc), mas nada parece se aplicar perfeitamente nesse contexto específico. Qualquer idéia ou inspiração seria apreciada.

cjauvin
fonte
Uma pergunta mais simples: como você detectaria segmentos de linha em dados bidimensionais?
charles.y.zheng
"..como os dos exemplos"? Que exemplos? Você pode adicionar um link?
onestop 12/03
A transformação Hough é a escolha óbvia. Deve funcionar bem.
whuber
Enquanto isso, tenho reputação suficiente para adicionar o exemplo de imagem a que eu estava me referindo.
cjauvin
3
Este não é um problema de cluster. Nas estatísticas, "clusters" consistem em conjuntos de objetos que são mutuamente mais próximos um do que outros objetos. A proximidade não captura a circularidade: é por isso que nem o K-significa nem qualquer outro algoritmo de agrupamento funcionará. Por esse motivo, essa pergunta provavelmente se encaixa melhor nos sites de processamento de imagem ou GIS, onde você pode encontrar alguns especialistas sobre esse assunto.
whuber

Respostas:

9

Uma transformação Hough generalizada é exatamente o que você deseja. A dificuldade é fazê-lo com eficiência, porque o espaço dos círculos em 3D tem seis dimensões (três para o centro, duas para orientar o plano, uma para o raio). Isso parece excluir um cálculo direto.

Uma possibilidade é dar uma espiada no resultado através de uma sequência de transformações mais simples de Hough. Por exemplo, você pode começar com a transformação (usual) de Hough para detectar subconjuntos planares: esses requerem apenas uma grade 3D para o cálculo. Para cada subconjunto plano detectado, corte os pontos originais ao longo desse plano e execute uma transformação Hough generalizada para detecção de círculo. Isso deve funcionar bem, desde que a imagem original não tenha muitos pontos coplanares (exceto os formados pelos círculos) que poderiam abafar o sinal gerado pelos círculos.

Se os tamanhos dos círculos tiverem um limite superior predeterminado, você poderá economizar bastante computação: em vez de olhar para todos os pares ou triplos de pontos na imagem original, você poderá focar em pares ou triplos em uma vizinhança delimitada de cada ponto.

whuber
fonte
Eu tentaria combinar todas as abordagens sugeridas: primeiro cluster baseado apenas na distância, conforme discutido no pôster original, o que fornecerá clusters que podem consistir em vários círculos. Em seguida, use Hough para detectar subconjuntos planares dentro de cada cluster. Em cada subconjunto plano, use novamente Hough para encontrar círculos. Se esse último passo for caro, você poderá executar um curto-circuito eficaz: tente alguns triplos, adivinhe um círculo e veja se uma fração substancial dos pontos do seu subconjunto está muito próxima desse círculo. Nesse caso, registre esse círculo e remova todos esses pontos e continue.
Erik P.Mar
3
Essa última idéia é chamada RANSAC e provavelmente poderia ser usada por si só, especialmente se o número de círculos por imagem for pequeno.
SheldonCooper
Obrigado pelas idéias esclarecedoras! A transformação Hough de várias etapas me parece a solução mais poderosa e geral, mas o RANSAC realmente parece mais fácil de implementar e pode ser apenas o suficiente no meu contexto. Um problema que notei rapidamente com ele é o caso de padrões de tamanhos desequilibrados, o que obviamente influencia a amostragem em objetos maiores. Alguma opinião sobre esse problema?
cjauvin
Depois de detectar o círculo maior, remova todos os pontos que pertencem a ele da amostragem.
SheldonCooper 13/03
0

número

sdgaw erzswer
fonte