Algorithme de comparaison d'images
-
10-07-2019 - |
Question
J'essaie de comparer des images entre elles pour déterminer si elles sont différentes. J'ai d'abord essayé de faire une corrélation de Pearson des valeurs RVB, ce qui fonctionne également très bien à moins que les images soient légèrement décalées. Donc, si vous avez des images 100% identiques mais que l’une est un peu déplacée, la valeur de ma corrélation est mauvaise.
Des suggestions pour un meilleur algorithme?
BTW, je parle de comparer des milliers d’images
Modifier: Voici un exemple de mes images (microscopiques):
im1:
im2:
im3:
im1 et im2 sont identiques mais un peu décalés / coupés, im3 devrait être reconnu comme complètement différent ...
Modifier: Le problème est résolu avec les 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
La solution
Une question similaire a été posée il y a un an et a de nombreuses réponses, y compris une concernant la pixellisation des images, que je voulais suggérer au moins comme une étape de pré-qualification (car elle exclurait très rapidement des images très non similaires).
Vous y trouverez également des liens vers des questions encore antérieures, qui contiennent encore plus de références et de bonnes réponses.
Voici une implémentation utilisant certaines des idées de Scipy, en utilisant les trois images ci-dessus (enregistrées au format im1.jpg, im2.jpg, im3.jpg, respectivement). La sortie finale montre im1 comparée à elle-même, sous forme de ligne de base, puis chaque image comparée aux 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 par rapport à lui-même donne un score de 42105, im2 par rapport à im1 n’est pas très éloigné de cela, mais im3 par rapport à l’un des autres donne bien moins de la moitié de cette valeur. Il vous faudra expérimenter avec d’autres images pour voir comment cela pourrait fonctionner et comment l’améliorer.
La durée d’exécution est longue ... plusieurs minutes sur ma machine. J'essaierais de procéder à un pré-filtrage pour éviter de perdre du temps à comparer des images très différentes, peut-être avec l'option "comparer la taille du fichier jpg". astuce mentionnée dans les réponses à l’autre question, ou avec la pixellisation. Le fait que vous ayez des images de différentes tailles complique les choses, mais vous ne donnez pas suffisamment d'informations sur l'ampleur de la dépeçage à laquelle on pourrait s'attendre. Il est donc difficile de donner une réponse spécifique tenant compte de cela.
Autres conseils
Je l’ai fait avec une comparaison d’histogramme d’image. Mon algorithme de base était le suivant:
- Fractionner l'image en rouge, vert et bleu
- Créez des histogrammes normalisés pour les canaux rouge, vert et bleu et concaténez-les dans un vecteur
(r0 ... rn, g0 ... gn, b0 ... bn)
où n est le nombre de "seaux", 256 devraient suffire - soustrayez cet histogramme de l'histogramme d'une autre image et calculez la distance
voici du code avec numpy
et 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 0, plus elles divergent, plus la distance est grande.
Cela a très bien fonctionné pour les photos pour moi mais a échoué pour les graphiques tels que les textes et les logos.
Vous devez vraiment préciser la question, mais, en regardant ces 5 images, les organismes semblent tous être orientés de la même manière. Si tel est toujours le cas, vous pouvez essayer de procéder à une corrélation croisée normalisée entre les deux images et en prenant la valeur maximale en tant que votre degré de similitude. Je ne connais pas de fonction de corrélation croisée normalisée en Python, mais il existe une fftconvolve () et vous pouvez effectuer 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 tel qu'écrit car les images sont de tailles différentes et que la sortie n'est ni pondérée ni normalisée.
L'emplacement de la valeur de crête de la sortie indique le décalage entre les deux images, et la magnitude de la crête indique la similarité. Il devrait y avoir un moyen de le pondérer / de le normaliser pour pouvoir faire la différence entre un bon match et un mauvais match.
Ce n’est pas une réponse aussi bonne que je le souhaite, étant donné que je n’ai pas encore compris comment le normaliser, mais je le mettrai à jour si je le découvre, et cela vous donnera l’idée de regarder. dans.
Si votre problème concerne les pixels décalés, vous devriez peut-être comparer à une transformation 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 ont 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 FFT, afin que vous puissiez obtenir un bon boost de performance 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 vous renseigner un peu là-bas.
Vous avez ici un prototype ... vous pouvez en jouer un peu 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 rendre les images floues, puis de soustraire les valeurs en 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 à l'étape précédente, vous pouvez répéter le déplacement dans la direction du dégradé et la soustraction jusqu'à la différence. est inférieur à un certain seuil ou augmente à nouveau. Cela devrait fonctionner si le rayon du noyau flou est plus grand que le décalage des images.
Vous pouvez également essayer certains des outils couramment utilisés dans le flux de production photographique pour fusionner plusieurs expositions ou créer des panoramas, comme le Outils Pano .
J'ai suivi un cours de traitement d'image il y a longtemps et je me souviens qu'en effectuant une correspondance, je commençais normalement à rendre l'image en niveaux de gris, puis à en rendre les contours plus nets afin de ne voir que les contours. Vous (le logiciel) pouvez alors 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 défini, les images ne sont pas égales et vous pouvez passer au suivant. Les images avec un seuil inférieur peuvent ensuite être analysées.
Je pense qu'au mieux, vous pouvez radicalement éliminer les correspondances possibles, mais vous devrez personnellement comparer 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.
Tout d’abord, la corrélation est une mesure de similarité plutôt imprécise, qui nécessite beaucoup de temps de calcul. Pourquoi ne pas simplement choisir la somme des carrés si les différences entre pixels individuels?
Une solution simple, si le décalage maximum est limité: générez toutes les images décalées possibles et recherchez celle qui correspond le mieux. Assurez-vous de calculer votre variable de correspondance (corrélation, par exemple) uniquement sur le sous-ensemble de pixels pouvant être mis en correspondance dans toutes les images décalées. De plus, votre décalage maximum doit être nettement inférieur à la taille de vos images.
Si vous souhaitez utiliser des techniques de traitement d'image plus avancées, je vous suggère de consulter EIFT c’est une méthode très puissante qui (théoriquement en tout cas) peut bien faire correspondre les éléments dans les images indépendamment de la translation, de la rotation et de l’échelle.
Je suppose que vous pourriez faire quelque chose comme ceci:
-
estime le déplacement vertical / horizontal de l'image de référence par rapport à l'image de comparaison. une SAD simple (somme de la différence absolue) avec des vecteurs de mouvement ferait à.
-
décale l'image de comparaison en conséquence
- calculez la corrélation pearson que vous tentiez de faire
La mesure de décalage n’est pas difficile.
- Prenez une région (disons environ 32x32) dans l’image de comparaison.
- Déplacez-le de x pixels en horizontal et de y pixels en direction verticale.
- Calculez le SAD (somme de la différence absolue) w.r.t. image originale
- Faites ceci pour plusieurs valeurs de x et y dans une petite plage (-10, +10)
- Trouvez l'endroit où la différence est minimale
- Choisissez cette valeur comme vecteur de déplacement de décalage
Remarque:
Si le SAD arrive très haut pour toutes les valeurs de x et y, vous pouvez néanmoins supposer que les images sont très différentes et qu'une mesure par décalage n'est pas nécessaire.
Pour que les importations fonctionnent correctement sur mon Ubuntu 16.04 (à compter d'avril 2017), j'ai installé Python 2.7 et les suivantes:
sudo apt-get install python-dev
sudo apt-get install libtiff5-dev libjpeg8-dev zlib1g-dev libfreetype6-dev liblcms2-dev libwebp-dev tcl8.6-dev tk8.6-dev python-tk
sudo apt-get install python-scipy
sudo pip install pillow
Ensuite, j'ai modifié les importations de Snowflake en ces suivantes:
import scipy as sp
from scipy.ndimage import imread
from scipy.signal.signaltools import correlate2d as c2d
Quelle merveille que le script de Snowflake fonctionne pour moi huit ans plus tard!