Comparateur d’images

Quand on commence à gérer des collections de centaines voire de milliers d’images, qu’on fait des retouches, des backups, des déplacements, des copies, etc., on finit par régulièrement se retrouver avec des doublons. L’objectif est donc de détecter rapidement les images dupliquées, et ce même si elles ont été légèrement retouchées.

Type de comparaison

Je vois deux types de comparaisons possibles : comparer les pixels et comparer les formes. La comparaison de formes est plus efficaces (on détecte mieux les similarités/différences), mais est bien plus complexe (bien qu’il existe des bibliothèques comme Emgu CV – portage .NET de Open CV) et plus lent. Je suis donc parti sur une comparaison des pixels.

Premier problème : la taille des images

La taille des images pose deux problèmes.

  • Plus l’image est grande, plus le nombre de pixels et donc de comparaisons à faire est grand, donc plus c’est lent.
  • Si l’on redimensionne une image, on ne peut plus comparer les pixels 1 à 1, puisqu’un pixel sur la « petite » image correspond à plusieurs pixels sur la « grande » image.

Un moyen simple de venir à bout de ces deux problèmes : redimensionner arbitrairement toutes les images dans une taille fixe, petite et carrée.

Deuxième problème : la comparaison entre deux pixels

De base, l’information d’un pixel se trouve sous les trois composantes R (rouge), G (vert) et B (bleu). Une simple comparaison avec une petite marge d’erreur marche, mais comparer les deux pixels sur ces trois composantes n’est pas un moyen très souple. Selon moi, un meilleur axe d’analyse est d’utiliser les composantes H (teinte), S (saturation) et L (luminosité).

En effet, la teinte est une composante bien plus importante que les deux autres lors de la comparaison d’images. Il est rare de faire des retouches sur la teinte (contrairement à la saturation ou la luminosité). Au final, la marge d’erreur acceptable doit donc être plus grande pour la saturation et pour la luminosité que pour la teinte.

Cependant, une comparaison sur la teinte est une mauvaise chose sur des pixels trop peu saturés ou trop sombres. Tout d’abord, parce que l’appareil photo risque de « bruiter » la photo (c’est-à-dire justement d’avoir des teintes différentes pour des pixels très semblables), mais également parce qu’un pixel sans saturation ou sans luminosité est considéré comme rouge (ce qui nous ferait passer, par exemple, d’un bleu très foncé à un noir avec une teinte rouge). Pour ces raisons, on ne fait qu’une comparaison de luminosité si la luminosité du pixel est en dessous d’un certain seuil. Sinon, on fait une comparaison de luminosité + saturation si sa saturation est en dessous d’un certain seuil. Sinon, on fait une comparaison teinte + saturation (avec un grosse marge) + luminosité (avec une grosse marge).

Le test

Ajoutons un pourcentage de pixels en erreur acceptable pour considérer les deux images comme identiques et un autre pourcentage pour considérer les deux images comme similaires. Je lance le teste, touche un peu aux différents seuils, marges, pourcentages… pour avoir des résultats probants.

J’ai trois types de résultats :

  • Les bons résultats
  • Les images différentes considérées comme semblables
  • Les images semblables considérées comme différentes

Les images semblables considérées comme différentes

Après analyse, je les ai séparées en deux types : celles qui ont des différences ponctuelles et celles qui ont des différences globales.

Pour les différences ponctuelles (texte, watermark, suppression des yeux rouges…), j’ai décidé d’ajouter un niveau lors de la comparaison de deux pixels. Au lieu de Similaires/Différents, j’ai Quasi-identiques/Similaires/Différents. Lors de la comparaison globale, les pixels quasi-identiques ont un coefficient supérieur.

Pour les différences globales, il s’agit souvent d’une modification des niveaux, donc de la luminosité et de la saturation. J’ai donc décidé, sur mes mini-images, de rendre le pixel le plus foncé noir et le pixel le plus clair blanc, et de modifier la luminosité de tous les autres pixels en conséquence.

Les images différentes considérées comme semblables

Là encore, j’ai remarqué 2 cas dans lesquels j’avais ce genre de faux positifs : les images très hautes ou très larges, et les images quasiment sans couleur.

Lorsqu’une image est très haute ou très large, sa hauteur ou sa largeur contient beaucoup d’informations, que l’on perd lors du redimensionnement. L’algorithme actuel ne permet donc pas de les comparer efficacement. J’ai tout simplement décidé d’ignorer ces images.

Comme expliqué précédemment, le moyen le plus fiable pour comparer deux pixels, c’est la teinte. Mais si l’image n’a pas de couleurs, il n’est pas possible d’utiliser ce paramètre pour la comparaison. J’ai donc ajouté un pourcentage seuil sur les pixels comparés via teinte + saturation + luminosité. Si deux images qui semblent similaires ont un pourcentage de comparaison avec teinte inférieur au seuil, je renvoie un nouveau résultat de comparaison : Unknown.

Les limites de l’algorithme

Cet algorithme ne fonctionne pas dans les cas suivants :

  • L’image est très grande ou très large
  • L’image n’est pas assez colorée
  • L’une des images est une composition de l’autre (on a rajouté un cadre, on a découpé une photo, on a ajouté quelque chose en dessous…)

Performances

Pour trouver les doublons, il faut deux étapes. La première étape consiste à créer les images miniatures (que je nomme empreintes), à obtenir les composantes H, S et L, et à régler la luminosité. Cette étape doit être effectuée une fois par image. La deuxième étape est la comparaison une à une de l’intégralité des images. Le nombre de comparaisons est donc (n)(n-1)/2.

Niveau mémoire vive, une empreinte utilise 4 octets par pixel. Donc avec une empreinte de 32×32, on arrive à 4 ko par empreinte, donc par image à comparer. Une collection de 10 000 images ne prendrait donc que 40 Mo.

En ce qui concerne le processeur, celui-ci est très utilisé pendant la génération des empreintes (jusqu’à 100% si le disque n’est pas l’élément limitant), et l’est également pendant la comparaison (100%).

Remplacer les for par des Parallel.For permet de répartir la charge sur l’ensemble des cœurs, et réduit donc considérablement le temps nécessaire.

Sur mon laptop, la création de 453 empreintes a pris 11 secondes. Les 102 378 comparaisons ont pris 3 secondes.

Le code

Enumérations

ComparisonResult

[pastacode lang= »cpp » message= » » highlight= » » provider= »manual »]

namespace PicCloneFinder { public enum ComparisonResult { Unknown = 0, Different = 1, Similar = 2, VeryClose = 3, Identical = 4 } }

[/pastacode]

ImageRotation

[pastacode lang= »cpp » message= » » highlight= » » provider= »manual »]

namespace PicCloneFinder { /// <summary> /// Rotation of the image, clockwise. /// </summary> public enum ImageRotation { /// <summary> /// No rotation. /// </summary> None = 0, /// <summary> /// 90° rotation, clockwise. /// </summary> Quarter = 90, /// <summary> /// 180° rotation. /// </summary> Half = 180, /// <summary> /// 270°, clockwise. /// </summary> ThreeQuarters = 270 } }

[/pastacode]

ImageMirror

[pastacode lang= »cpp » message= » » highlight= » » provider= »manual »]

namespace PicCloneFinder { /// <summary> /// Mirror of the image. /// </summary> public enum ImageMirror { /// <summary> /// No mirror. /// </summary> None = 0, /// <summary> /// Horizontal mirror. /// </summary> HorizontalMirror = 1, /// <summary> /// Vertical mirror. /// </summary> VerticalMirror = 2 } }

[/pastacode]

Structures

HSLColor

[pastacode lang= »cpp » message= » » highlight= » » provider= »manual »]

using System; using System.Drawing; using System.Globalization; namespace PicCloneFinder { /// <summary> /// A color with alpha, hue, saturation and lightness. /// </summary> [Serializable] public struct HSLColor : IEquatable<HSLColor>, IEquatable<Color> { /// <summary> /// Bits /// 32 -> 25 : Alpha /// 24 -> 16 : Hue /// 15 -> 09 : Saturation /// 08 -> 02 : Lightness /// </summary> private int _valueContainer; /// <summary> /// Gets the alpha (between 0 and 255). /// </summary> /// <value> /// The alpha. /// </value> public int A { get { return (_valueContainer >> 24) & 255; } } /// <summary> /// Gets the hue (between 0 and 359). /// </summary> /// <value> /// The hue. /// </value> public int H { get { return (_valueContainer >> 15) & 511; } } /// <summary> /// Gets the saturation (between 0 and 100). /// </summary> /// <value> /// The saturation. /// </value> public int S { get { return (_valueContainer >> 8) & 127; } } /// <summary> /// Gets the lightness (between 0 and 100). /// </summary> /// <value> /// The lightness. /// </value> public int L { get { return (_valueContainer >> 1) & 127; } } /// <summary> /// Initializes a new instance of the <see cref="HSLColor"/> struct. /// </summary> /// <param name="a">The alpha.</param> /// <param name="h">The hue.</param> /// <param name="s">The saturation.</param> /// <param name="l">The lightness.</param> /// <exception cref="ArgumentOutOfRangeException"> /// a;The alpha should be between 0 and 255. /// or /// h;The hue should be between 0 and 359. /// or /// s;The saturation should be between 0 and 100. /// or /// l;The lightness should be between 0 and 100. /// </exception> public HSLColor(int a, int h, int s, int l) { if (a > 255 || a < 0) throw new ArgumentOutOfRangeException("a", "The alpha should be between 0 and 255."); if (h > 359 || h < 0) throw new ArgumentOutOfRangeException("h", "The hue should be between 0 and 359."); if (s > 100 || s < 0) throw new ArgumentOutOfRangeException("s", "The saturation should be between 0 and 100."); if (l > 100 || l < 0) throw new ArgumentOutOfRangeException("l", "The lightness should be between 0 and 100."); _valueContainer = (a << 24) + (h << 15) + (s << 8) + (l << 1); } /// <summary> /// Gets an HSLColor from a <see cref="Color"/> object. /// </summary> /// <param name="c">The color.</param> /// <returns>An <see cref="HSLColor"/>.</returns> public static HSLColor FromColor(Color c) { return new HSLColor(c.A, (int)(c.GetHue()), (int)(100.0 * c.GetSaturation()), (int)(100.0 * c.GetBrightness())); } /// <summary> /// Indicates whether the current object is equal to another object of the same type. /// </summary> /// <param name="other">An object to compare with this object.</param> /// <returns> /// <c>true</c> if the current object is equal to the <paramref name="other" /> parameter; otherwise, <c>false</c>. /// </returns> public bool Equals(HSLColor other) { return this._valueContainer == other._valueContainer; } /// <summary> /// Indicates whether the current object is equal to another object of the same type. /// </summary> /// <param name="other">An object to compare with this object.</param> /// <returns> /// <c>true</c> if the current object is equal to the <paramref name="other" /> parameter; otherwise, <c>false</c>. /// </returns> public bool Equals(Color other) { return this._valueContainer == FromColor(other)._valueContainer; } /// <summary> /// Determines whether the specified <see cref="System.Object" />, is equal to this instance. /// </summary> /// <param name="obj">The <see cref="System.Object" /> to compare with this instance.</param> /// <returns> /// <c>true</c> if the specified <see cref="System.Object" /> is equal to this instance; otherwise, <c>false</c>. /// </returns> public override bool Equals(object obj) { if (obj == null) return false; if (obj is HSLColor) return Equals((HSLColor)obj); return false; } /// <summary> /// Implements the operator ==. /// </summary> /// <param name="obj1">The obj1.</param> /// <param name="obj2">The obj2.</param> /// <returns> /// The result of the operator. /// </returns> public static bool operator ==(HSLColor obj1, HSLColor obj2) { return obj1.Equals(obj2); } /// <summary> /// Implements the operator !=. /// </summary> /// <param name="obj1">The obj1.</param> /// <param name="obj2">The obj2.</param> /// <returns> /// The result of the operator. /// </returns> public static bool operator !=(HSLColor obj1, HSLColor obj2) { return !obj1.Equals(obj2); } /// <summary> /// Returns a hash code for this instance. /// </summary> /// <returns> /// A hash code for this instance, suitable for use in hashing algorithms and data structures like a hash table. /// </returns> public override int GetHashCode() { return _valueContainer; } /// <summary> /// Returns a <see cref="System.String" /> that represents this instance. /// </summary> /// <returns> /// A <see cref="System.String" /> that represents this instance. /// </returns> public override string ToString() { return string.Format(CultureInfo.InvariantCulture, "HSLColor {{A:{0}, H:{1}, S:{2}, L:{3}}}", A, H, S, L); } } }

[/pastacode]

Il est vrai que l’on perd de l’information puisque 360 x 101 x 101 représentent moins de valeurs de 256 x 256 x 256. Cependant, cela ne pose pas de problème pour la comparaison. J’ai utilisé des calculs bit à bit pour obtenir l’opacité, la teinte, la saturation et la luminosité, et ce afin de garantir que les informations sont enregistrées sur 4 octets.

Le framework .NET permet d’obtenir la teinte, la saturation et la luminosité à partir d’un objet Color, mais pas l’inverse. J’ai donc obtenu et implémenté l’algorithme moi-même pour la méthode ToColor().

J’ai respecté les best practices concernant les structures en C# :

  • Le type représente une valeur.
  • Le type est immutable (sa valeur ne peut pas changer).
  • Le type fait moins de 16 octets.

J’ai également fait tout le nécessaire pour vérifier l’égalité entre 2 HSLColors :

  • Surcharger Equals(object) et donc GetHashCode()
  • Implémenter IEquatable<HSLColor>
  • Surcharger l’opérateur == et donc l’opérateur !=.

Classes

ComparisonHash

[pastacode lang= »cpp » message= » » highlight= » » provider= »manual »]

using System; using System.Drawing; using System.Drawing.Imaging; using System.Runtime.InteropServices; namespace PicCloneFinder { /// <summary> /// Hash of an image for comparison /// </summary> public class ComparisonHash { public const int SquareEdge = 32; private HSLColor[][] _innerArray; private ImageRotation _rotation; private ImageMirror _mirror; /// <summary> /// Initializes a new instance of the <see cref="ComparisonHash"/> class. /// </summary> /// <param name="source">The source.</param> /// <exception cref="System.ArgumentException">Only 24 and 32 bpp images are supported.</exception> public ComparisonHash(Image source) { int depth = Bitmap.GetPixelFormatSize(source.PixelFormat) / 8; if (depth != 3 && depth != 4) { throw new ArgumentException("Only 24 and 32 bpp images are supported."); } double ratio = (double)source.Width / (double)source.Height; if (ratio > 5 || 1 / ratio > 5) { throw new ArgumentException("The width/height ratio is too high."); } byte[] temp = new byte[SquareEdge * SquareEdge * depth]; using (Bitmap bitmap = new Bitmap(source, SquareEdge, SquareEdge)) { BitmapData bd = bitmap.LockBits(new Rectangle(0, 0, SquareEdge, SquareEdge), ImageLockMode.ReadOnly, source.PixelFormat); Marshal.Copy(bd.Scan0, temp, 0, temp.Length); bitmap.UnlockBits(bd); } _innerArray = new HSLColor[SquareEdge][]; for (int x = 0; x < SquareEdge; x++) { _innerArray[x] = new HSLColor[SquareEdge]; } for (int y = 0; y < SquareEdge; y++) { for (int x = 0; x < SquareEdge; x++) { int a, r, g, b; int position = x * depth + y * SquareEdge * depth; b = temp[position]; g = temp[position + 1]; r = temp[position + 2]; a = depth == 4 ? temp[position + 3] : 255; _innerArray[x][y] = HSLColor.FromARGB(a, r, g, b); } } temp = null; SetMaxContrast(); _rotation = ImageRotation.None; _mirror = ImageMirror.None; } private void SetMaxContrast() { int min = 101; int max = -1; for (int y = 0; y < SquareEdge; y++) { for (int x = 0; x < SquareEdge; x++) { int tmpL = _innerArray[x][y].L; if (tmpL < min) min = tmpL; if (tmpL > max) max = tmpL; } } if (min == max) return; int delta = max - min; for (int y = 0; y < SquareEdge; y++) { for (int x = 0; x < SquareEdge; x++) { HSLColor old = _innerArray[x][y]; int newL = (old.L - min) * 100 / delta; _innerArray[x][y] = new HSLColor(old.A, old.H, old.S, newL); } } } /// <summary> /// Gets the <see cref="HSLColor" /> with the specified coordinates. /// </summary> /// <value> /// The <see cref="HSLColor" />. /// </value> /// <param name="x">The x.</param> /// <param name="y">The y.</param> /// <returns>The <see cref="HSLColor" />.</returns> /// <exception cref="System.InvalidOperationException"> /// Incorrect image rotation. /// or /// Incorrect image mirror. /// </exception> public HSLColor this[int x, int y] { get { int newX, newY; switch (_rotation) { case ImageRotation.None: newX = x; newY = y; break; case ImageRotation.Quarter: newX = y; newY = SquareEdge - x - 1; break; case ImageRotation.Half: newX = SquareEdge - x - 1; newY = SquareEdge - y - 1; break; case ImageRotation.ThreeQuarters: newX = SquareEdge - y - 1; newY = x; break; default: throw new InvalidOperationException("Incorrect image rotation."); } if (_mirror == ImageMirror.HorizontalMirror) newX = SquareEdge - newX - 1; else if (_mirror == ImageMirror.VerticalMirror) newY = SquareEdge - newY - 1; else if (_mirror != ImageMirror.None) throw new InvalidOperationException("Incorrect image mirror."); return _innerArray[newX][newY]; } } } }

[/pastacode]

Cette classe représente donc une empreinte d’une image. La propriété indexée permet d’obtenir la couleur (HSL) d’un pixel de l’image, mais peut se baser sur une rotation et/ou un miroir.

On peut aussi noter l’utilisation de la méthode Bitmap.LockBits() afin d’obtenir les pixels de l’image, sous forme d’un tableau de bytes, que je copie dans un autre tableau de bytes temporaire via Marshal.Copy(). Les méthode Bitmap.GetPixel() et Bitmap.SetPixel() sont extrêmement lentes, puisqu’elles font appel à LockBits et UnlockBits à chaque appel (donc pour chaque pixel), là où je ne le fais qu’une fois. A noter que la méthode Marshal.Copy() aurait pu être remplacée par du code unsafe.

Le seul paramètre de comparaison se trouvant dans cette classe et la largeur de l’empreinte, actuellement à 32.

PictureComparer

[pastacode lang= »cpp » message= » » highlight= » » provider= »manual »]

using System; namespace PicCloneFinder { public class PictureComparer { private const int MaxHDiff = 15; private const int MaxLDiff = 15; private const int MaxSDiff = 15; private const int LThreshold = 10; private const int SThreshold = 10; private const int SimilarityThreshold = 70; private const int CloseThreshold = 96; private const int ToleratedDifference = 20; private const double ExactMatchCoefficient = 1.3; private const int MinimumHueComparisons = 40; public ComparisonResult Compare(ComparisonHash hash1, ComparisonHash hash2) { int totalPixels = ComparisonHash.SquareEdge * ComparisonHash.SquareEdge; int maxDifferent = totalPixels * (100 - SimilarityThreshold) / 100; int exactMatch = 0; int similarPixels = 0; int differentPixels = 0; int hueComparisons = 0; for (int x = 0; x < ComparisonHash.SquareEdge; x++) { for (int y = 0; y < ComparisonHash.SquareEdge; y++) { HSLColor color1 = hash1[x, y]; HSLColor color2 = hash2[x, y]; if (color1 == color2) exactMatch++; else if (AreNearlyExact(color1, color2)) exactMatch++; else if (AreSimilar(color1, color2, ref hueComparisons)) similarPixels++; else differentPixels++; if (differentPixels >= maxDifferent) return ComparisonResult.Different; } } if (exactMatch == totalPixels) return ComparisonResult.Identical; if (similarPixels + exactMatch * ExactMatchCoefficient > totalPixels * CloseThreshold / 100) return ComparisonResult.VeryClose; if (hueComparisons > similarPixels * MinimumHueComparisons / 100) return ComparisonResult.Similar; return ComparisonResult.Unknown; } private bool AreSimilar(HSLColor color1, HSLColor color2, ref int hueComparisons) { if (color1.L < LThreshold || color2.L < LThreshold || color1.L > 100 - LThreshold || color2.L > 100 - LThreshold) { return LightnessComparison(color1, color2); } if (color1.S < SThreshold || color2.S < SThreshold) { return SaturationComparison(color1, color2); } hueComparisons++; return HueComparison(color1, color2); } private bool AreNearlyExact(HSLColor color1, HSLColor color2) { if (color1.L < LThreshold || color2.L < LThreshold || color1.L > 100 - LThreshold || color2.L > 100 - LThreshold) return false; return Math.Max(0, GetHueDiff(color1.H, color2.H) - 5) * 10 + GetDiff(color1.S, color2.S) + GetDiff(color1.L, color2.L) <= ToleratedDifference; } private bool HueComparison(HSLColor color1, HSLColor color2) { return GetHueDiff(color1.H, color2.H) < MaxHDiff && GetDiff(color1.S, color2.S) < MaxSDiff * 2 && GetDiff(color1.L, color2.L) < MaxLDiff * 2; } private bool SaturationComparison(HSLColor color1, HSLColor color2) { return GetDiff(color1.S, color2.S) < MaxSDiff && GetDiff(color1.L, color2.L) < MaxLDiff; } private bool LightnessComparison(HSLColor color1, HSLColor color2) { return GetDiff(color1.L, color2.L) < MaxLDiff; } private int GetDiff(int val1, int val2) { return Math.Abs(val1 - val2); } private int GetHueDiff(int val1, int val2) { return Math.Abs(180 - (540 + val1 - val2) % 360); } } }

[/pastacode]

La seule méthode publique de cette classe est la méthode Compare. C’est également cette classe qui, à l’exception de la largeur des empreintes, contient l’ensemble des paramètres de comparaison.

La majeure partie de cette classe a été décrite précédemment dans l’article. Je ne m’attarderai donc que sur la méthode GetHueDiff(). Une simple soustraction ne suffit pas dans ce cas, puisqu’une teinte de 359 n’a qu’une différence de 1 avec une teinte de 0. 180 correspond à la différence maximum entre deux teintes. 540 correspond à 180 (même raison) + 360 (pour garantir que le modulo 360 soit positif).

Code externe

Pour utiliser ce code, il suffit donc de :

  • Créer une instance de PictureComparer
  • Lister l’ensemble des fichiers à comparer.
  • Appeler Image.FromFile() sur chacun des fichiers en question
  • Créer un new ComparisonHash() à partir de chacune de ces images
  • Faire une double boucle Parallel.For sur l’ensemble des ComparisonHash, sans revenir sur une paire déjà comparée.

[pastacode lang= »cpp » message= » » highlight= » » provider= »manual »]

Parallel.For(0, hashes.Count, i => { Parallel.For(i + 1, hashes.Count, j => { } }

[/pastacode]

  • Appeler la méthode Compare de l’instance de PictureComparer sur le hash [i] et le hash [j].

 

Pierre-Etienne BEAU,

alias Krimog

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.