Algorithme de comparaison d'images

Question

J'essaie de comparer les images entre elles pour savoir si elles sont différentes. J'ai d'abord essayé de faire une corrélation de Pearson des valeurs RVB, ce qui fonctionne assez bien, sauf si les images sont un peu décalées. Ainsi, si j'ai des images 100% identiques mais que l'une d'entre elles est un peu décalée, j'obtiens une mauvaise valeur de corrélation.

Des suggestions pour un meilleur algorithme ?

BTW, je parle de comparer des milliers d'images...

Modifier : Voici un exemple de mes photos (microscopiques) :

im1 :

im2 :

im3 :

im1 et im2 sont les mêmes mais un peu décalées/coupées, im3 devrait être reconnu comme complètement différent...

Edit : Le problème est résolu grâce aux suggestions de Peter Hansen ! Fonctionne très bien ! Merci à toutes les réponses ! Quelques résultats peuvent être trouvés ici http://labtools.ipk-gatersleben.de/image%20comparison/image%20comparision.pdf

Answer 1

A question similaire Cette question a été posée il y a un an et a donné lieu à de nombreuses réponses, dont une concernant la pixellisation des images, que j'allais suggérer comme étant au moins une étape de présélection (car elle permettrait d'exclure assez rapidement les images très peu similaires).

Vous y trouverez également des liens vers des questions encore plus anciennes, avec encore plus de références et de bonnes réponses.

Voici une mise en œuvre utilisant certaines des idées avec Scipy, en utilisant vos trois images ci-dessus (enregistrées comme im1.jpg, im2.jpg, im3.jpg, respectivement). La sortie finale montre im1 comparé avec lui-même, comme ligne de base, et ensuite chaque image comparée avec les autres.

>>> import scipy as sp
>>> from scipy.misc import imread
>>> from scipy.signal.signaltools import correlate2d as c2d
>>>
>>> def get(i):
...     # get JPG image as Scipy array, RGB (3 layer)
...     data = imread('im%s.jpg' % i)
...     # convert to grey-scale using W3C luminance calc
...     data = sp.inner(data, [299, 587, 114]) / 1000.0
...     # normalize per http://en.wikipedia.org/wiki/Cross-correlation
...     return (data - data.mean()) / data.std()
...
>>> im1 = get(1)
>>> im2 = get(2)
>>> im3 = get(3)
>>> im1.shape
(105, 401)
>>> im2.shape
(109, 373)
>>> im3.shape
(121, 457)
>>> c11 = c2d(im1, im1, mode='same')  # baseline
>>> c12 = c2d(im1, im2, mode='same')
>>> c13 = c2d(im1, im3, mode='same')
>>> c23 = c2d(im2, im3, mode='same')
>>> c11.max(), c12.max(), c13.max(), c23.max()
(42105.00000000259, 39898.103896795357, 16482.883608327804, 15873.465425120798)

Notez donc que im1 comparé à lui-même donne un score de 42105, im2 comparé à im1 n'en est pas loin, mais im3 comparé à l'un ou l'autre des autres donne bien moins de la moitié de cette valeur. Il vous faudra expérimenter avec d'autres images pour voir comment cette méthode peut fonctionner et comment vous pouvez l'améliorer.

Le temps d'exécution est long... plusieurs minutes sur ma machine. J'essaierais un pré-filtrage pour éviter de perdre du temps à comparer des images très dissemblables, peut-être avec l'astuce "comparer la taille des fichiers jpg" mentionnée dans les réponses à l'autre question, ou avec la pixellisation. Le fait que vous ayez des images de tailles différentes complique les choses, mais vous n'avez pas donné suffisamment d'informations sur l'ampleur du massacre auquel on peut s'attendre, il est donc difficile de donner une réponse spécifique qui en tienne compte.

Answer 2

J'ai déjà fait cela avec une comparaison d'histogrammes d'images. Mon algorithme de base était le suivant :

1. Diviser l'image en rouge, vert et bleu
2. Créer des histogrammes normalisés pour les canaux rouge, vert et bleu et les concaténer dans un vecteur. (r0...rn, g0...gn, b0...bn) où n est le nombre de "seaux", 256 devrait suffire
3. soustraire cet histogramme de l'histogramme d'une autre image et calculer la distance

voici du code avec numpy y pil

r = numpy.asarray(im.convert( "RGB", (1,0,0,0, 1,0,0,0, 1,0,0,0) ))
g = numpy.asarray(im.convert( "RGB", (0,1,0,0, 0,1,0,0, 0,1,0,0) ))
b = numpy.asarray(im.convert( "RGB", (0,0,1,0, 0,0,1,0, 0,0,1,0) ))
hr, h_bins = numpy.histogram(r, bins=256, new=True, normed=True)
hg, h_bins = numpy.histogram(g, bins=256, new=True, normed=True)
hb, h_bins = numpy.histogram(b, bins=256, new=True, normed=True)
hist = numpy.array([hr, hg, hb]).ravel()

si vous avez deux histogrammes, vous pouvez obtenir la distance comme ceci :

diff = hist1 - hist2
distance = numpy.sqrt(numpy.dot(diff, diff))

Si les deux images sont identiques, la distance est de 0, plus elles divergent, plus la distance est grande.

Cela a bien fonctionné pour les photos, mais pas pour les graphiques comme les textes et les logos.

Answer 3

Si votre problème concerne des pixels décalés, vous devriez peut-être comparer avec une transformée de fréquence.

La FFT devrait être OK ( numpy a une implémentation pour les matrices 2D ), mais j'entends toujours dire que les ondelettes sont meilleures pour ce genre de tâches ^_^

En ce qui concerne les performances, si toutes les images sont de la même taille, si je me souviens bien, le paquet FFTW a créé une fonction spécialisée pour chaque taille d'entrée de la FFT, ce qui permet d'augmenter les performances en réutilisant le même code... Je ne sais pas si numpy est basé sur FFTW, mais si ce n'est pas le cas, vous pourriez peut-être essayer d'enquêter un peu là-dessus.

Vous avez ici un prototype... vous pouvez jouer un peu avec pour voir quel seuil correspond à vos images.

import Image
import numpy
import sys

def main():
    img1 = Image.open(sys.argv[1])
    img2 = Image.open(sys.argv[2])

    if img1.size != img2.size or img1.getbands() != img2.getbands():
        return -1

    s = 0
    for band_index, band in enumerate(img1.getbands()):
        m1 = numpy.fft.fft2(numpy.array([p[band_index] for p in img1.getdata()]).reshape(*img1.size))
        m2 = numpy.fft.fft2(numpy.array([p[band_index] for p in img2.getdata()]).reshape(*img2.size))
        s += numpy.sum(numpy.abs(m1-m2))
    print s

if __name__ == "__main__":
    sys.exit(main())

Une autre façon de procéder pourrait être de brouiller les images, puis de soustraire les valeurs des pixels des deux images. Si la différence est non nulle, vous pouvez déplacer l'une des images de 1 px dans chaque direction et comparer à nouveau. Si la différence est inférieure à celle de l'étape précédente, vous pouvez répéter le déplacement dans la direction du gradient et la soustraction jusqu'à ce que la différence soit inférieure à un certain seuil ou augmente à nouveau. Cela devrait fonctionner si le rayon du noyau de flou est plus grand que le décalage des images.

Vous pouvez également essayer certains des outils couramment utilisés dans le flux de travail photographique pour mélanger plusieurs expositions ou réaliser des panoramas, comme l'outil Outils Pano .

Answer 4

Vous devez vraiment mieux préciser la question, mais, en regardant ces 5 images, les organismes semblent tous être orientés de la même façon. Si c'est toujours le cas, vous pouvez essayer de faire un corrélation croisée normalisée entre les deux images et en prenant la valeur maximale comme votre degré de similarité. Je ne connais pas de fonction de corrélation croisée normalisée en Python, mais il existe une fonction similaire en Python. fftconvolve() et vous pouvez faire la corrélation croisée circulaire vous-même :

a = asarray(Image.open('c603225337.jpg').convert('L'))
b = asarray(Image.open('9b78f22f42.jpg').convert('L'))
f1 = rfftn(a)
f2 = rfftn(b)
g =  f1 * f2
c = irfftn(g)

Cela ne fonctionnera pas comme écrit puisque les images sont de tailles différentes, et la sortie n'est pas du tout pondérée ou normalisée.

L'emplacement de la valeur de crête de la sortie indique le décalage entre les deux images, et l'ampleur de la crête indique la similarité. Il devrait y avoir un moyen de pondérer/normaliser cette valeur afin que vous puissiez faire la différence entre une bonne et une mauvaise correspondance.

La réponse n'est pas aussi bonne que je le souhaiterais, car je n'ai pas encore trouvé comment normaliser les données, mais je la mettrai à jour si je trouve une solution, et cela vous donnera une idée à examiner.

Answer 5

J'ai suivi des cours de traitement d'images il y a longtemps, et je me souviens que, lors de la mise en correspondance, je commençais normalement par rendre l'image en niveaux de gris, puis j'accentuais les bords de l'image pour ne voir que les bords. Vous (le logiciel) pouvez ensuite décaler et soustraire les images jusqu'à ce que la différence soit minimale.

Si cette différence est supérieure au seuil que vous avez fixé, les images ne sont pas égales et vous pouvez passer à la suivante. Les images avec un seuil plus petit peuvent alors être analysées ensuite.

Je pense que, dans le meilleur des cas, vous pouvez radicalement réduire le nombre de correspondances possibles, mais vous devrez comparer personnellement les correspondances possibles pour déterminer si elles sont vraiment égales.

Je ne peux pas vraiment montrer le code car c'était il y a longtemps, et j'ai utilisé Khoros/Cantata pour ce cours.