Reconnaissance ponctuelle

46

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: entrez la description de l'image ici


Mise à jour 1:
La figure suivante montre une vue un peu plus réaliste du problème à l’étude. entrez la description de l'image ici

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. entrez la description de l'image ici

Développeur
la source
1
Vous cherchez une solution pour faire correspondre ces points ou pour des images plus complexes? Combien de points pourrait-il y avoir dans les images?
Oui, c'est très important. Si ce ne sont que des points de taille connue, vous pouvez optimiser cela. Si vous avez le contrôle sur les repères fiduciaires, vous pouvez optimiser cela. Soyez plus précis sur ce que vous utilisez pour cela.
endolith
Pour le problème sur lequel je travaille, il existe des ensembles de points (plusieurs centaines de points chacun) dans lesquels un autre ensemble de points de taille inférieure (par exemple <100) est recherché. La démonstration ci-dessus est tellement simplifiée et claire que le vrai problème semble compliqué. Il y a également un intérêt à trouver des correspondances classées sur la base de points non souhaités.
Développeur
1
Y aura-t-il juste des points noirs et blancs? Les obtenez-vous d'un appareil photo / scanner / autre chose? Les valeurs binaires pourraient rendre les calculs beaucoup plus rapides.
endolith
Avez-vous un problème pour trouver les centres des points, ou simplement pour trouver la miniature dans l’ensemble, connaissant la position des points?

Réponses:

17

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.

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:

entrez la description de l'image ici

Cible:

entrez la description de l'image ici

Corrélation croisée:

entrez la description de l'image ici

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
  • 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.

endolithe
la source
1
C'est vrai, pour le problème à l'étude, il n'y a pas d'échelle mais une rotation peut avoir lieu. Merci pour le lien et la réponse.
Développeur
@Developer: Eh bien, cela fonctionnera alors, mais il existe probablement un meilleur moyen. S'il ne s'agit que d'une image binaire, la corrélation croisée sera beaucoup plus rapide. (Existe-t-il une FFT pour un signal binaire?) La rotation est-elle arbitraire? Vous devez expérimenter un ensemble de valeurs de rotation qui donne de bons résultats, comme une incrémentation de 1 degré ou de 5 degrés, etc.
endolithe
1
Oui c'est un problème binaire. Je me souviens aussi de quelque part qu'il y avait une telle méthode pour trouver un signal plus court modulé sur un signal plus long avec des amplitudes différentes. Je me souviens que quelle que soit la complexité, cela fonctionnait très bien et montrait des points de sélection comme points de départ des événements. Comme le problème est en 2D, il n’est pas clair pour moi d’utiliser un concept similaire. Ceci est également compliqué à cause de la rotation qui s’applique en 2D.
Développeur
1
Oui, cela devient impossible lorsque l'on ajoute la liberté de rotation. C'est pourquoi des méthodes telles que RANSAC ont été développées. Je pense que cela aide de penser en dehors de la boîte DSP sur celui-ci.
Matt M.
@ Matt: ça marche, c'est juste lent. :)
endolithe
22

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.

entrez la description de l'image ici

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.

Matt M.
la source
J'ai ajouté un peu plus de détails dans la question. Je vais vérifier vos liens en profondeur mais une impression rapide a été qu'ils sont des concepts différents!
Développeur
1
On dirait que c'est en effet un problème RANSAC / homographie :)
Matt M.
Bien. C'était un nouveau concept pour moi. Je vais l'essayer dès que possible. Si je suis confronté à des difficultés, je partagerai avec vous de grands membres de la communauté qui apporteront leur soutien.
Développeur
Simple Q: Est-il possible / faisable d'appliquer la méthode RANSAC / homographie à un nuage de points 3D?
Développeur
Ce n'est pas une solution valable. Malheureusement, la question ne contient pas d’informations d’intensité et, par conséquent, de simples schémas de descripteurs ne fonctionneraient pas. Le problème est plutôt plus géométrique que cela.
Tolga Birdal
3

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.

miroir2image
la source
1
Voulez-vous nous donner un exemple avec plus d'explications sur votre idée? La version actuelle de votre réponse m'embrouille.
Développeur
3

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:

entrez la description de l'image ici

  1. Utilisez l' implémentation OpenCV par défaut de la transformation de Hough généralisée pour obtenir: entrez la description de l'image ici

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 .

Tolga Birdal
la source