Localização rápida de linhas irregulares em conjuntos de pontos

12

Em uma classe específica de detectores, nossos dados são apresentados como pares de pontos em duas dimensões, e queremos agrupar esses pontos em linhas.

Os dados são barulhentos e são armazenados em uma direção, mas não na outra. Não podemos garantir um acerto em cada compartimento, mesmo quando cada elemento detector estiver funcionando, portanto pode haver pulos.

Nossa cadeia de análise atual parece

  1. Ajustar resultados para a calibração de elementos detectores individuais
  2. Localizar clusters
  3. Linhas ásperas de ajuste nos clusters
  4. Conecte clusters em estruturas mais longas, semelhantes a linhas
  5. ...

Esta questão diz respeito ao passo (3).

Usamos uma transformação Hough para essa etapa e ela funciona bem, mas, ao tentarmos escalar do ambiente de teste para a simulação de um projeto em escala real, ela se torna inaceitavelmente lenta.

Estou procurando uma maneira mais rápida.


Para aqueles que se importam com o caso de uso real, aqui está uma câmara de projeção de tempo com argônio líquido

dmckee --- gatinho ex-moderador
fonte
1
Também fizemos um método recursivo de Hough Transform para rastreamento de caminhos através de câmaras proporcionais com múltiplos fios no FermiLab. A tese de Erik Kangas tem todos os detalhes. Eu acho que essa ainda é a melhor maneira de fazer isso.
precisa saber é o seguinte
1
Você quis dizer "... pares no ponto ..." ou "... pares de pontos ..." na primeira frase?
Bill Barth

Respostas:

2

Existe uma versão probabilística da transformação de Hough (PHT) mais rápida. Conforme descrito por Bradski & Kaehler em seu livro OpenCV:

A ideia é que o pico seja alto o suficiente, e atingi-lo apenas uma fração do tempo será suficiente para encontrá-lo.

A biblioteca OpenCV apresenta uma implementação para o PHT.

Existem outras alternativas. Não é difícil criar uma versão distribuída da transformação Hough. Apenas divida seu conjunto de pontos em partes menores e use a estrutura MapReduce para resumir todos os acumuladores. Outra idéia é executar uma versão grossa da transformação Hough usando um espaço de parâmetro com baixa resolução. Escolha seus melhores candidatos e execute uma iteração mais fina usando um espaço de parâmetro com uma resolução mais alta. Talvez seja essa a ideia por trás da ESF de Gandalf.

º.
fonte
1
O PHT foi proposto em: Matas, J. e Galambos, C. e Kittler, JV, Detecção Robusta de Linhas Utilizando a Transformada de Hough Probabilística Progressiva. CVIU 78 1, pp 119-137 (2000).
TH.
O procedimento então o procedimento fino pode ser generalizado em várias etapas, que é o que Gandalf faz.
dmckee --- ex-moderador gatinho
BTW - Desde que eu fiz essa pergunta, um colega adicionou um módulo usando a versão probabilística progressiva da transformação ao nosso código. Isso ocorreu com várias alterações associadas, por isso é difícil caracterizar exatamente qual a diferença que fez, mas faz parte de um pacote que acelerou consideravelmente algumas etapas da análise. Então, eu vou aceitar isso como o conselho "vencedor".
dmckee --- gatinho ex-moderador
5

Meu colega encontrou a Fast Hough Transform na biblioteca Gandalf , que parece muito promissora, mas pode ser muito trabalhosa para integrar, por isso estou procurando outras abordagens.

A implementação de Gandalf é interessante: eles avaliam o espaço acumulador de maneira recursiva, como se estivessem atravessando uma árvore quádrupla ou octa. Regiões sem muita densidade são jogadas fora à medida que avançam.

dmckee --- gatinho ex-moderador
fonte