Reconnaissance ponctuelle

Ayant deux ensembles de points de taille différente (2D pour simplifier) ​​répartis dans deux carrés de tailles différentes, la question est la suivante:

1- Comment trouver une occurrence du petit à travers le grand?
2- Une idée sur la manière de classer les occurrences comme indiqué sur la figure suivante?

Voici une démonstration simple de la question et une solution souhaitée:

Mise à jour 1:
La figure suivante montre une vue un peu plus réaliste du problème à l’étude.

En ce qui concerne les commentaires, les propriétés suivantes s'appliquent:

• l'emplacement exact des points est disponible
• taille exacte des points sont disponibles
  • taille peut être zéro (~ 1) = seulement un point
• tous les points sont noirs sur fond blanc
• il n'y a pas d'effet d'échelle de gris / anti-aliasing

Voici ma mise en œuvre de la méthode présentée par endolithavec quelques petites modifications (j'ai fait pivoter la cible au lieu de la source car elle est plus petite et plus rapide en rotation). J'ai accepté la réponse d'Endolith parce que j'y pensais auparavant. À propos de RANSAC je n'ai aucune expérience jusqu'à présent. De plus, la mise en œuvre de RANSAC nécessite beaucoup de code.

Ce n'est pas la meilleure solution, mais c'est une solution. J'aimerais apprendre de meilleures techniques:

Si elles ne devaient pas faire l'objet d'une rotation ou d'une réduction, vous pouvez utiliser une simple corrélation croisée des images. Il y aura un pic lumineux partout où la petite image apparaît dans la grande image.

• Enregistrement d'une image à l'aide d'une corrélation croisée normalisée
• Correspondance et convolution basées sur des modèles

Vous pouvez accélérer la corrélation croisée en utilisant une méthode FFT, mais si vous faites simplement correspondre une image source petite à une image cible grande, la méthode multiplication-ajout force-brute est parfois (généralement) plus rapide.

La source:

Cible:

Corrélation croisée:

Les deux points lumineux sont les emplacements qui correspondent.

Mais vous n'avez un paramètre de rotation dans votre image par exemple, de sorte que ne fonctionnera pas par lui - même. Si seule la rotation est autorisée, et non la mise à l'échelle, il est toujours possible d'utiliser la corrélation croisée, mais vous devez effectuer une corrélation croisée, faire pivoter la source, la corréler avec l'image cible entière, la faire pivoter à nouveau, etc. toutes les rotations.

Notez que cela ne trouvera pas forcément jamais l'image. Si l'image source est un bruit aléatoire et que la cible est un bruit aléatoire, vous ne le trouverez pas à moins de chercher exactement au bon angle. Dans des situations normales, il le trouvera probablement, mais cela dépend des propriétés de l’image et des angles de recherche.

Cette page montre un exemple de la procédure à suivre, mais ne donne pas l'algorithme.

Tout décalage dont la somme est supérieure à un seuil est une correspondance. Vous pouvez calculer la qualité de la correspondance en corrélant l'image source avec elle-même et en divisant toutes vos sommes par ce nombre. Un match parfait sera 1.0.

Cela demandera beaucoup de temps, cependant, et il existe probablement de meilleures méthodes pour faire correspondre les motifs de points (ce que j'aimerais connaître).

Exemple rapide Python utilisant la méthode de niveaux de gris et de 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 1 couleur

Pour les bitmaps à une couleur, cela serait toutefois beaucoup plus rapide. La corrélation croisée devient:

• Placez l'image source sur l'image cible
  • ET au niveau du bit ET tous les pixels qui se chevauchent (beaucoup plus rapidement que la multiplication)
  • additionner tous les 1 dans la zone superposée
• Déplacer l'image source de 1 pixel
  • ET au niveau du bit ET tous les pixels superposés
  • additionner tous les 1
• ...

Sertir une image en niveaux de gris sur une image binaire peut ensuite suffire.

Nuage de points

Si la source et la cible sont toutes deux des motifs de points, une méthode plus rapide consisterait à trouver les centres de chaque point (corrélation croisée une fois avec un point connu, puis à rechercher les pics) et à les stocker sous la forme d'un ensemble de points, puis à faire correspondre la source. pour cibler en faisant pivoter, en traduisant et en trouvant l'erreur des moindres carrés entre les points les plus proches dans les deux ensembles.

Du point de vue de la vision par ordinateur: le problème de base consiste à estimer une homographie entre votre ensemble de points cible et un sous-ensemble de points dans le grand ensemble. Dans votre cas, avec rotation uniquement, ce sera une homographie affine. Vous devriez regarder dans la méthode RANSAC . Il est conçu pour trouver un match dans un ensemble avec de nombreuses valeurs aberrantes. Vous êtes donc armé de deux mots clés importants, homographie et RANSAC .

OpenCV offre des outils pour calculer ces solutions, mais vous pouvez également utiliser MATLAB. Voici un exemple RANSAC utilisant OpenCV . Et une autre implémentation complète .

Une application typique pourrait être de trouver une couverture de livre dans une image. Vous avez une photo de la couverture du livre et une photo du livre sur une table. L’approche n’est pas de faire une correspondance de modèle, mais de trouver les angles saillants dans chaque image et de comparer ces ensembles de points. Votre problème ressemble à la seconde moitié de ce processus: trouver le point dans un grand nuage. RANSAC a été conçu pour le faire de manière robuste.

J'imagine que les méthodes de corrélation croisée peuvent également fonctionner pour vous, car les données sont très propres. Le problème est que vous ajoutez un autre degré de liberté avec la rotation et que la méthode devient très lente.

Si le modèle est binaire clairsemé, vous pouvez faire une simple covariance de vecteurs de coordonnées au lieu d'images. Prenez les coordonnées des points dans la sous-fenêtre triée en haut à gauche, créez un vecteur à partir de toutes les coordonnées et calculez la covariance avec un vecteur composé des coordonnées des points du motif trié en haut à gauche. Vous pouvez également utiliser des poids. Après cela, force brute proche voisin recherche la covariance maximale sur une grille de la grande fenêtre (et également sur des angles de rotation). Après avoir trouvé des coordonnées approximatives avec la recherche, vous pouvez les affiner avec la méthode des moindres carrés repondérés.

PS Idea is, au lieu de travailler avec une image, vous pouvez travailler avec des coordonnées de pixels non nuls. Recherche commune du plus proche voisin. Vous devez effectuer une recherche exhaustive de tous les espaces de recherche, à la fois en translation et en rotation, à l'aide d'une grille, c'est-à-dire une étape dans l'angle des coordonnées et de la rotation. Pour chaque coordonnée / angle, vous prenez un sous-ensemble de pixels dans la fenêtre dont le centre est pivoté selon cet angle, prenez leurs coordonnées (par rapport au centre) et comparez-les aux coordonnées de pixel du motif que vous recherchez. Vous devez vous assurer que, dans les deux ensembles, les points sont triés de la même manière. Vous trouvez les coordonnées avec la différence minimale (covariance maximale). Après cette correspondance approximative, vous pouvez trouver une correspondance précise avec une méthode d'optimisation. Désolé je ne peux pas le relayer plus simple que cela.

Je suis très surpris pourquoi personne n'a mentionné les méthodes de la famille de transformée de Hough généralisée . Ils résolvent directement ce problème particulier.

Voici ce que je propose:

1. Prenez le modèle et créez la table R en indexant les bords du modèle. Les arêtes que je sélectionne sont les suivantes:

2. Utilisez l' implémentation OpenCV par défaut de la transformation de Hough généralisée pour obtenir:

où les emplacements correspondants sont marqués. La même méthode serait toujours fonctionnelle même si les contours sont réduits à un seul point, car la méthode ne nécessite pas d'intensités d'image.

De plus, la gestion des rotations est très naturelle pour les systèmes de Hough. En fait, dans le cas 2D, il s’agit simplement d’une dimension ajoutée dans l’accumulateur. Au cas où vous voudriez entrer dans les détails pour le rendre vraiment efficace, M. Ulrich explique beaucoup de trucs dans son papier .

C'est une bonne application pour le hachage géométrique. page wikipedia de hachage géométrique