Comment mesurer la similarité entre deux images ?[fermé]

https://stackoverflow.com/questions/25977

09-06-2019
|

Question

Je voudrais comparer une capture d'écran d'une application (peut-être une page Web) avec une capture d'écran prise précédemment pour déterminer si l'application s'affiche correctement.Je ne veux pas de comparaison exacte, car l'aspect pourrait être légèrement différent (dans le cas d'une application Web, selon le navigateur, certains éléments pourraient se trouver à un emplacement légèrement différent).Cela devrait donner une mesure de la similitude des captures d’écran.

Existe-t-il une bibliothèque/un outil qui fait déjà cela ?Comment le mettriez-vous en œuvre ?

La solution

Cela dépend entièrement du degré d’intelligence que vous souhaitez donner à l’algorithme.

Par exemple, voici quelques problèmes :

images recadrées vs.une image non recadrée
images avec un texte ajouté vs.un autre sans
images en miroir

Le plus simple et le plus simple algorithme J'ai vu que cela consiste simplement à suivre les étapes suivantes pour chaque image :

redimensionnez à quelque chose de petit, comme 64x64 ou 32x32, ne tenez pas compte du rapport hauteur/largeur, utilisez un algorithme de mise à l'échelle combinant au lieu du pixel le plus proche
redimensionnez les gammes de couleurs pour que la plus foncée soit le noir et la plus claire le blanc
faites pivoter et retournez l'image de sorte que la couleur la plus claire soit en haut à gauche, puis en haut à droite soit ensuite plus sombre, en bas à gauche soit ensuite plus sombre (dans la mesure du possible bien sûr)

Modifier UN combinaison d'un algorithme de mise à l'échelle en est un qui, lors de la réduction de 10 pixels à un, le fera en utilisant une fonction qui prend la couleur de tous ces 10 pixels et les combine en un seul.Peut être réalisé avec des algorithmes tels que la moyenne, la valeur moyenne ou des algorithmes plus complexes comme les splines bicubiques.

Calculez ensuite la distance moyenne pixel par pixel entre les deux images.

Pour rechercher une correspondance possible dans une base de données, stockez les couleurs des pixels sous forme de colonnes individuelles dans la base de données, indexez-en un certain nombre (mais pas toutes, sauf si vous utilisez une très petite image) et effectuez une requête qui utilise une plage pour chacun. valeur de pixel, c'est à dire.chaque image où le pixel de la petite image est compris entre -5 et +5 de l'image que vous souhaitez rechercher.

Ceci est facile à mettre en œuvre et assez rapide à exécuter, mais ne gère bien sûr pas les différences les plus avancées.Pour cela, vous avez besoin d’algorithmes beaucoup plus avancés.

Autres conseils

La manière « classique » de mesurer cela consiste à diviser l'image en un certain nombre canonique de sections (par exemple une grille 10x10), puis à calculer un histogramme des valeurs RVB à l'intérieur de chaque cellule et à comparer les histogrammes correspondants.Ce type d'algorithme est préféré à la fois en raison de sa simplicité et de son invariance à la mise à l'échelle et à la (petite !) traduction.

Utilisez un histogramme de couleurs normalisé.(Lire la section sur les candidatures ici), ils sont couramment utilisés dans les systèmes de récupération/correspondance d'images et constituent un moyen standard de mise en correspondance d'images qui est très fiable, relativement rapide et très simple à mettre en œuvre.

Essentiellement, un histogramme des couleurs capturera la distribution des couleurs de l’image.Celle-ci peut ensuite être comparée à une autre image pour voir si les distributions de couleurs correspondent.

Ce type de correspondance est assez résistant à la mise à l'échelle (une fois l'histogramme normalisé), à la rotation/décalage/mouvement, etc.

Évitez les comparaisons pixel par pixel, car si l'image est légèrement pivotée/décalée, cela peut entraîner une différence importante.

Les histogrammes seraient simples à générer vous-même (en supposant que vous puissiez accéder aux valeurs des pixels), mais si vous n'en avez pas envie, le OuvrirCV la bibliothèque est une excellente ressource pour faire ce genre de choses. Ici est une présentation PowerPoint qui vous montre comment créer un histogramme à l'aide d'OpenCV.

Les algorithmes d'encodage vidéo comme MPEG ne calculent-ils pas la différence entre chaque image d'une vidéo afin de pouvoir simplement encoder le delta ?Vous pourriez examiner comment les algorithmes de codage vidéo calculent ces différences d’images.

Regardez cette application de recherche d'images open source http://www.semanticmetadata.net/lire/.Il décrit plusieurs algorithmes de similarité d'images, dont trois sont issus de la norme MPEG-7 :ScalableColor, ColorLayout, EdgeHistogram et Auto Color Correlogram.

Vous pouvez utiliser une approche mathématique pure de O(n^2), mais cela ne sera utile que si vous êtes certain qu'il n'y a pas de décalage ou quelque chose comme ça.(Même si vous avez quelques objets avec une coloration homogène, cela fonctionnera quand même plutôt bien.)

Quoi qu'il en soit, l'idée est de calculer le produit scalaire normalisé des deux matrices.C = sum(Pij*Qij)^2/(sum(Pij^2)*sum(Qij^2)).

Cette formule est en fait le "cosinus" de l'angle entre les matrices (bizarre).Plus la similitude est grande (disons Pij=Qij), C sera 1, et s'ils sont complètement différents, disons pour chaque i,j Qij = 1 (en évitant la division zéro), Pij = 255, puis pour la taille nxn, le plus gros n sera, plus nous nous rapprocherons de zéro.(Par calcul approximatif : C=1/n^2).

Tu auras besoin la reconnaissance de formes pour ça.Pour déterminer de petites différences entre deux images, Filets Hopfield fonctionnent assez bien et sont assez faciles à mettre en œuvre.Cependant, je ne connais aucune implémentation disponible.

Une solution rubis peut être trouvé ici

Extrait du fichier Lisez-moi :

Phashion est un wrapper Ruby autour de la bibliothèque pHash, "hachage perceptuel", qui détecte les fichiers multimédias en double et presque en double.

La manière de mesurer la similarité entre deux images dépend entièrement de ce que vous souhaitez mesurer, par exemple :contraste, luminosité, modalité, bruit...puis choisissez la mesure de similarité la mieux adaptée à vos besoins.Vous pouvez choisir parmi FOU (différence absolue moyenne), MSD (différence quadratique moyenne) qui sont utiles pour mesurer la luminosité... il existe également CR (coefficient de corrélation) qui permet de représenter la corrélation entre deux images.Vous pouvez également choisir parmi des mesures de similarité basées sur un histogramme telles que SDH (écart type de l'histogramme de l'image de différence) ou des mesures de similarité multimodales comme MI (information mutuelle) ou INM (informations mutuelles normalisées).

Étant donné que ces mesures de similarité coûtent beaucoup de temps, il est conseillé de réduire la taille des images avant de leur appliquer ces mesures.

Je me demande (et je lance vraiment l'idée pour qu'elle soit abattue) si quelque chose pourrait être dérivé en soustrayant une image de l'autre, puis en compressant l'image résultante sous forme de jpeg ou de gif et en prenant la taille du fichier comme une mesure de similarité.

Si vous aviez deux images identiques, vous obtiendriez une boîte blanche, qui se compresserait très bien.Plus les images différaient, plus elles seraient complexes à représenter, et donc moins compressibles.

Ce n'est probablement pas un test idéal, et probablement beaucoup plus lent que nécessaire, mais cela pourrait fonctionner comme une implémentation rapide et sale.

Vous pouvez consulter le code de l'outil open source trouver des images dupes, bien qu'il semble avoir été écrit en Perl, je ne peux donc pas dire à quel point il sera facile à analyser...

En lisant la page findimagedupes que j'ai aimé, je vois qu'il y a un Implémentation C++ du même algorithme.Vraisemblablement, ce sera plus facile à comprendre.

Et il semble que vous puissiez également utiliser gqview.

Eh bien, je ne réponds pas directement à votre question, mais j'ai vu cela se produire.Microsoft a récemment lancé un outil appelé PhotoSynthé qui fait quelque chose de très similaire pour déterminer les zones qui se chevauchent dans un grand nombre d'images (qui peuvent avoir des formats d'image différents).

Je me demande s'ils ont des bibliothèques ou des extraits de code disponibles sur leur blog.

pour développer la note de Vaibhav, câlin est un « autostitcher » open source qui devrait avoir un aperçu du problème.

Il existe un logiciel de récupération d'images basé sur le contenu, qui fait (partiellement) ce dont vous avez besoin.Toutes les références et explications sont liées depuis le site du projet et il existe également un court manuel (Kindle) : LIRE

Eh bien, une méthode vraiment basique à utiliser pourrait passer en revue chaque couleur de pixel et la comparer avec la couleur de pixel correspondante sur la deuxième image - mais c'est probablement un très très solution lente.

Si c'est quelque chose que vous ferez de manière occasionnelle et qui n'a pas besoin d'être automatisé, vous pouvez le faire dans un éditeur d'images prenant en charge les calques, tel que Photoshop ou Paint Shop Pro (probablement GIMP ou Paint.Net aussi, mais je' je ne suis pas sûr de cela).Ouvrez les deux captures d’écran et placez-en une sous forme de calque sur l’autre.Changez le mode de fusion des calques en Différence, et tout ce qui est identique entre les deux deviendra noir.Vous pouvez déplacer la couche supérieure pour minimiser les différences d’alignement.

Vous pouvez utiliser le réseau siamois pour voir si les deux images sont similaires ou différentes après ceci Didacticiel.Ce tutoriel regroupe les images similaires alors que vous pouvez utiliser L2 distance pour mesurer la similarité de deux images.

Au delà de toute comparaison permet une comparaison pixel par pixel des images, par exemple :

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow