Reconhecimento de padrões de pontos

Tendo dois tamanhos diferentes de conjuntos de pontos (2D por simplicidade) dispersos em dois quadrados de tamanhos diferentes, a questão é:

1- como encontrar alguma ocorrência do pequeno ao grande?
2- Alguma idéia de como classificar as ocorrências, como mostra a figura a seguir?

Aqui está uma demonstração simples da pergunta e uma solução desejada:

Atualização 1:
A figura a seguir mostra uma visão um pouco mais realista do problema que está sendo investigado.

Em relação aos comentários, as seguintes propriedades se aplicam:

• a localização exata dos pontos está disponível
• o tamanho exato dos pontos está disponível
  • tamanho pode ser zero (~ 1) = apenas um ponto
• todos os pontos são pretos em um fundo branco
• não há efeito de escala de cinza / anti-aliasing

Aqui está minha implementação do método apresentado por endolithalgumas pequenas alterações (eu girei o alvo em vez da fonte, pois é menor e mais rápido na rotação). Aceitei a resposta do endólito porque estava pensando nisso antes. Sobre o RANSAC Não tenho experiência até agora. Além disso, a implementação do RANSAC requer muito código.

Esta não é a melhor solução, mas é uma solução. Eu gostaria de aprender melhores técnicas:

Se eles não fossem rotacionados ou redimensionados, você poderia usar uma simples correlação cruzada das imagens. Haverá um pico brilhante onde quer que a imagem pequena ocorra na imagem grande.

• Registrando uma imagem usando correlação cruzada normalizada
• Correspondência e convolução baseadas em modelo

Você pode acelerar a correlação cruzada usando um método FFT, mas se estiver apenas combinando uma imagem de origem pequena com uma imagem de destino grande, o método de multiplicação e adição de força bruta às vezes é (geralmente não) mais rápido.

Fonte:

Alvo:

Correlação cruzada:

Os dois pontos positivos são os locais correspondentes.

Mas você faz ter um parâmetro de rotação na sua imagem exemplo, de modo que não irá funcionar por si só. Se apenas a rotação é permitida, e não a escala, ainda é possível usar a correlação cruzada, mas você precisa correlacionar, girar a fonte, correlacioná-la com toda a imagem de destino, girá-la novamente, etc. para todas as rotações.

Observe que isso nem sempre encontrará a imagem. Se a imagem de origem for ruído aleatório e o alvo for ruído aleatório, você não a encontrará, a menos que pesquise exatamente no ângulo certo. Em situações normais, provavelmente o encontrará, mas depende das propriedades da imagem e dos ângulos nos quais você pesquisa.

Esta página mostra um exemplo de como isso seria feito, mas não fornece o algoritmo.

Qualquer deslocamento em que a soma esteja acima de algum limite é uma correspondência. Você pode calcular a qualidade da correspondência correlacionando a imagem de origem consigo mesma e dividindo todas as suas somas por esse número. Uma combinação perfeita será 1.0.

Isso será muito pesado computacionalmente, e provavelmente existem métodos melhores para combinar padrões de pontos (sobre os quais eu gostaria de saber).

Exemplo rápido de Python usando escala de cinza e método FFT:

from __future__ import division
from pylab import *
import Image
import ImageOps

source_file = 'dots source.png'
target_file = 'dots target.png'

# Load file as grayscale with white dots
target = asarray(ImageOps.invert(Image.open(target_file).convert('L')))

close('all')
figure()
imshow(target)
gray()
show()

source_Image = ImageOps.invert(Image.open(source_file).convert('L'))

for angle in (0, 180):
    source = asarray(source_Image.rotate(angle, expand = True))
    best_match = max(fftconvolve(source[::-1,::-1], source).flat)

    # Cross-correlation using FFT
    d = fftconvolve(source[::-1,::-1], target, mode='same')

    figure()
    imshow(source)


    # This only finds a single peak.  Use something that finds multiple peaks instead:
    peak_x, peak_y = unravel_index(argmax(d),shape(d))

    figure()    
    plot(peak_y, peak_x,'ro')
    imshow(d)

    # Keep track of all these matches:
    print angle, peak_x, peak_y, d[peak_x,peak_y] / best_match

Bitmaps de uma cor

Para bitmaps de uma cor, isso seria muito mais rápido. A correlação cruzada se torna:

• Coloque a imagem de origem sobre a imagem de destino
  • AND bit a bit - todos os pixels sobrepostos (muito mais rápido que a multiplicação)
  • somar todos os 1s na área sobreposta
• Mover a imagem de origem em 1 pixel
  • E bit a bit todos os pixels sobrepostos
  • somar todos os 1s
• ...

Limitar uma imagem em escala de cinza para binária e fazer isso pode ser bom o suficiente.

Nuvem

Se a origem e o destino forem ambos padrões de pontos, um método mais rápido seria encontrar os centros de cada ponto (correlacionar uma vez com um ponto conhecido e depois encontrar os picos) e armazená-los como um conjunto de pontos; para segmentar girando, traduzindo e encontrando o erro de mínimos quadrados entre os pontos mais próximos nos dois conjuntos.

Do ponto de vista da visão computacional: o problema básico é estimar uma homografia entre o conjunto de pontos de destino e um subconjunto de pontos no conjunto grande. No seu caso, apenas com rotação, será uma homografia afim. Você deve procurar o método RANSAC . Ele foi projetado para encontrar uma correspondência em um conjunto com muitos valores discrepantes. Então, você está armado com duas palavras-chave importantes, homografia e RANSAC .

O OpenCV oferece ferramentas para calcular essas soluções, mas você também pode usar o MATLAB. Aqui está um exemplo de RANSAC usando OpenCV . E outra implementação completa .

Uma aplicação típica pode ser encontrar uma capa de livro em uma imagem. Você tem uma foto da capa do livro e uma foto do livro em uma mesa. A abordagem não é fazer a correspondência de modelos, mas encontrar cantos salientes em cada imagem e comparar esses conjuntos de pontos. Seu problema parece com a segunda metade desse processo - encontrar o ponto definido em uma grande nuvem. O RANSAC foi projetado para fazer isso de maneira robusta.

Eu acho que os métodos de correlação cruzada também podem funcionar para você, pois os dados são muito limpos. O problema é que você adiciona outro grau de liberdade com a rotação, e o método se torna muito lento.

Se o padrão é binário esparso, você pode fazer uma covariância simples de vetores de coordenadas em vez de imagens. Pegue coordenadas de pontos na sub-janela ordenada à esquerda, faça um vetor com todas as coordenadas e calcule a covariância com o vetor feito de coordenadas de pontos do padrão ordenado à esquerda. Você também pode usar pesos. Depois disso, faça com que a força bruta do vizinho mais próximo procure a covariância máxima em alguma grade na grande janela (e também a grade em ângulos de rotação). Depois de encontrar coordenadas aproximadas com a pesquisa, você pode refiná-las com o método de mínimos quadrados ponderados.

PS Idea é que, em vez de trabalhar com imagem, você pode trabalhar com coordenadas de pixels diferentes de zero. Pesquisa de vizinho mais próximo comum. Você deve fazer uma pesquisa exaustiva de todo o espaço de pesquisa, tanto de translação quanto de rotação, usando alguma grade, que é um passo na coordenada e no ângulo de rotação. Para cada coordenada / ângulo, você pega um subconjunto de pixels na janela com o centro com essa coordenada girada para esse ângulo, pega suas coordenadas (em relação ao centro) e as compara com as coordenadas de pixel do padrão que você procura. Você deve se certificar de que, nos dois conjuntos, os pontos sejam classificados da mesma maneira. Você encontra coordenadas com diferença mínima (covariância máxima). Após essa correspondência aproximada, você poderá encontrar uma correspondência precisa com algum método de otimização. Desculpe, não posso retransmitir isso de maneira mais simples que isso.

Estou muito surpreso porque ninguém mencionou métodos da família Generalized Hough Transform . Eles resolvem diretamente esse problema específico.

Aqui está o que eu proponho:

1. Pegue o modelo e crie a tabela R , indexando as bordas do modelo. As arestas que seleciono são as seguintes:

2. Use a implementação padrão OpenCV da transformação Hough generalizada para obter:

onde os locais correspondentes estão marcados. O mesmo método ainda seria funcional, mesmo que as bordas se reduzam a um único ponto, porque o método não requer intensidades de imagem.

Além disso, lidar com rotações é muito natural para esquemas de Hough. De fato, para o caso 2D, é apenas uma dimensão adicional no acumulador. Caso você queira entrar em detalhes sobre como torná-lo realmente eficiente, M. Ulrich explica muitos truques em seu artigo .

Esta é uma boa aplicação para o hash geométrico. página da Wikipédia com hash geométrico