Correspondência de perfil em uma nuvem de pontos

Uma nuvem de pontos é gerada usando a função aleatória uniforme para (x,y,z). Conforme mostrado na figura a seguir, está sendo investigado um plano de interseção plano ( perfil ) que corresponde ao melhor (mesmo que não exatamente) um perfil de destino, ou seja, dado no canto inferior esquerdo. Então a questão é:

1- Como encontrar um jogo de dado target 2D point mapatravés point cloudconsiderando as seguintes notas / condições?
2- Quais são então as coordenadas / orientações / grau de similaridade etc?

Nota 1: O perfil de interesse pode estar em qualquer lugar com qualquer rotação ao longo dos eixos e também pode ter uma forma diferente, por exemplo, um triângulo, retângulo, quadrilátero etc., dependendo de sua localização e orientação. Na demonstração a seguir, apenas um retângulo simples é mostrado.

Nota 2: Um valor de tolerância pode ser considerado como a distância dos pontos do perfil. Para demonstrar isso para a figura a seguir suponha que uma tolerância de 0.01vezes a menor dimensão (~1)assim tol=0.01. Portanto, se removermos o restante e projetarmos todos os pontos restantes no plano do perfil que está sendo investigado, poderemos verificar sua semelhança com o perfil de destino.

Nota 3: Um tópico relacionado pode ser encontrado no reconhecimento de padrões de pontos .

Isso sempre exigirá muita computação, especialmente se você quiser processar até 2000 pontos. Tenho certeza de que já existem soluções altamente otimizadas para esse tipo de correspondência de padrões, mas você precisa descobrir como é chamado para encontrá-las.

Como você está falando de uma nuvem de pontos (dados esparsos) em vez de uma imagem, meu método de correlação cruzada não se aplica realmente (e seria ainda pior em termos computacionais). Algo como o RANSAC provavelmente encontra uma correspondência rapidamente, mas eu não sei muito sobre isso.

Minha tentativa de uma solução:

Premissas:

• Você deseja encontrar a melhor correspondência, não apenas uma correspondência frouxa ou "provavelmente correta"
• A correspondência terá uma pequena quantidade de erro devido a ruído na medição ou cálculo
• Os pontos de origem são coplanares
• Todos os pontos de origem devem existir no destino (= qualquer ponto não correspondido é uma incompatibilidade para todo o perfil)

Portanto, você deve conseguir vários atalhos desqualificando as coisas e diminuindo o tempo de computação. Em resumo:

1. escolha três pontos da fonte
2. pesquise pontos alvo, encontrando conjuntos de 3 pontos com a mesma forma
3. quando for encontrada uma correspondência de 3 pontos, verifique todos os outros pontos no plano que eles definem para ver se são coincidentes
4. se mais de uma correspondência de todos os pontos for encontrada, escolha aquela com a menor soma do erro de distâncias em 3D

Mais detalhado:

pick a point from the source for testing s1 = (x1, y1)
Find nearest point in source s2 = (x2, y2)
d12 = (x1-x2)^2 + (y1-y2)^2
Find second nearest point in source s3 = (x3, y3)
d13 = (x1-x3)^2 + (y1-y3)^2
d23 = (x2-x3)^2 + (y2-y3)^2

for all (x,y,z) test points t1 in target:
    # imagine s1 and t1 are coincident
    for all other points t2 in target:
        if distance from test point > d12:    
            break out of loop and try another t2 point
        if distance ≈ d12:
            # imagine source is now rotated so that s1 and s2 are collinear with t1 and t2
            for all other points t3 in target:
                if distance from t1 > d13 or from t2 > d23:
                    break and try another t3
                if distance from t1 ≈ d13 and from t2 ≈ d23:
                    # Now you've found matching triangles in source and target
                    # align source so that s1, s2, s3 are coplanar with t1, t2, t3
                    project all source points onto this target plane 
                    for all other points in source:
                        find nearest point in target
                        measure distance from source point to target point
                        if it's not within a threshold:
                            break and try a new t3
                        else:
                            sum errors of all matched points for this configuration (defined by t1, t2, t3)

Qualquer configuração que tenha o erro mínimo ao quadrado para todos os outros pontos é a melhor correspondência

Como estamos trabalhando com três pontos de teste de vizinhos mais próximos, os pontos de destino correspondentes podem ser simplificados, verificando se estão dentro de um raio. Se procurarmos um raio de 1 a partir de (0, 0), por exemplo, podemos desqualificar (2, 0) com base em x1 - x2, sem calcular a distância euclidiana real, para acelerar um pouco. Isso pressupõe que a subtração é mais rápida que a multiplicação. Também existem pesquisas otimizadas baseadas em um raio fixo mais arbitrário .

function is_closer_than(x1, y1, z1, x2, y2, z2, distance):
    if abs(x1 - x2) or abs(y1 - y2) or abs(z1 - z2) > distance:
        return False
    return (x1 - x2)^2 + (y1 - y2)^2 + (z1 - z2)^2 > distance^2 # sqrt is slow

$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2+(z_1 - z_2)^2}$

O tempo mínimo de cálculo seria se nenhuma correspondência de 2 pontos fosse encontrada. Se houver 2000 pontos no alvo, seriam cálculos de distância de 2000 * 2000, embora muitos fossem desqualificados por uma subtração, e os resultados dos cálculos anteriores pudessem ser armazenados, então você só precisa fazer = 1,999,000.$2000 \choose 2$

Na verdade, como você precisará calcular tudo isso de qualquer maneira, encontre ou não correspondências, e como você se importa apenas com os vizinhos mais próximos para esta etapa, se você tiver memória, provavelmente será melhor pré-calcular esses valores usando um algoritmo otimizado . Algo como uma triangulação de Delaunay ou Pitteway , em que todos os pontos do alvo estão conectados aos vizinhos mais próximos. Armazene-os em uma tabela e procure-os para cada ponto ao tentar ajustar o triângulo de origem a um dos triângulos de destino.

Há muitos cálculos envolvidos, mas deve ser relativamente rápido, uma vez que está apenas operando nos dados, o que é escasso, em vez de multiplicar muitos zeros sem sentido, como envolveria a correlação cruzada de dados volumétricos. Essa mesma idéia funcionaria para o caso 2D se você localizasse primeiro os centros dos pontos e os armazenasse como um conjunto de coordenadas.

Eu adicionaria a descrição @ mirror2image na solução alternativa ao lado do RANSAC; você pode considerar o algoritmo ICP (ponto mais próximo iterativo); uma descrição pode ser encontrada aqui !

Penso que o próximo desafio ao usar este ICP é definir sua própria função de custo e a posição inicial do plano de destino em relação aos dados do ponto da nuvem 3D. Uma abordagem prática é introduzir algum ruído aleatório nos dados durante a iteração para evitar a convergência para os mínimos falsos. Esta é a parte heurística que acho que você precisa criar.

Atualizar:

As etapas na forma simplificada são:

1. Encontre o ponto mais próximo para cada ponto de entrada.
2. Calcule a transformação da entrada para o destino e mova os pontos de entrada usando a transformação.
3. Calcule a função de similaridade (por exemplo, a distância para cada ponto de entrada em relação ao seu ponto alvo correspondente).
4. Verifique a condição de parada.

Itere a etapa 1-4.

Há uma biblioteca disponível que você pode considerar aqui ! (Ainda não tentei), há uma seção na parte de registro (incluindo outros métodos).