Recherche d'image modèle

Question

Je dois faire un programme qui fait ceci: donné une image (5 * 5 pixels), je dois chercher combien d'images comme cela existe dans une autre image, composée par beaucoup d'autres images. C'est-à-dire que j'ai besoin de rechercher un motif donné dans une image.

La langue à utiliser est C. Je dois utiliser l'informatique parallèle pour rechercher dans les 4 angles (0º, 90º, 180º et 270º).

Quelle est la meilleure façon de faire cela?

Answer 1

Semble simple.

• Créez 4 versions de l'image pivotées de 0 °, 90 °, 180 ° et 270 °.
• Commencez quatre threads chacun avec une version de l'image.
• Pour toutes les positions de (0,0) à (width - 5, height - 5)
  • Comapare les 25 pixels de l'image de référence avec les 25 pixels à la position actuelle
  • Si elles sont égales assez en utilisant une certaine mesure, signaler la conclusion.

Answer 2

Il n'y a pas besoin de créer les trois versions de l'image, il suffit de les traiter différemment ou utiliser quelque chose comme la classe que j'ai créé here supplémentaires. Mieux encore, il suffit de dupliquer la matrice 5x5 et de les faire pivoter à la place. Vous pouvez ensuite scanner linéairement l'image pour toutes les rotations (ce qui est une bonne chose).

Ce problème ne s'échelonnera pas bien pour le traitement parallèle car le goulot d'étranglement accède certainement aux données d'image. Le fait que plusieurs threads accèdent aux mêmes données le ralentira, en particulier si les threads sont désynchronisés, c'est-à-dire que l'un des threads dépasse les autres threads et que les autres threads finissent par recharger les données rejetées par le premier thread . Donc, la solution que je pense sera la plus efficace est de créer quatre threads qui balaient 5 lignes de l'image, un thread par rotation. Un cinquième thread charge les données d'image une ligne à la fois et passe la ligne à chacun des quatre threads d'analyse, en attendant que les quatre threads à compléter, à savoir charger une ligne d'image, ajouter à cinq ligne tampon, démarrer les quatre threads d'analyse , attendez que les threads se terminent et répétez jusqu'à ce que toutes les lignes d'image soient lues.

Answer 3

Utilisez la corrélation normalisée pour déterminer une correspondance des modèles.

@Daniel, la solution de Daniel est bonne pour exploiter vos multiples processeurs. Il ne mentionne pas une métrique de qualité qui serait utile et je voudrais suggérer une métrique de qualité très courante dans le traitement d'image.

Je suggère d'utiliser normalized correlation [1] comme métrique de comparaison, car elle génère un nombre compris entre -1 et +1. Lorsque 0 n'est pas une corrélation, 1 serait sortie si les deux modèles étaient identiques et -1 serait si les deux modèles étaient exactement opposés. Une fois que vous avez calculé la corrélation normalisée, vous pouvez tester si vous avez trouvé le modèle en faisant threshold test ou un test de crête à moyenne [2].

[1 - footnote] Comment implémentez-vous la corrélation normalisée? C'est assez simple et il n'y en a que deux pour les boucles.Une fois que vous avez une implémentation qui est assez bonne, vous pouvez vérifier votre implémentation en vérifiant si l'image identique vous obtient un 1.

[2 - footnote] Vous faites le ratio du max (array)/average (array_without_peak). Puis seuil pour vous assurer que vous avez un bon ratio entre le pic et la moyenne.

Answer 4

5 * 5 = 25

25 bits correspondent à un nombre entier. Chaque image peut être codée sous la forme d'un tableau de 4 entiers.

Itére votre plus grande image, (heureusement, il n'est pas trop grand), tirant sur toutes les sous-images 5 * 5, convertir en tableau de 4 entiers et de comparer.