Quelle est la façon la plus rapide de comparer deux bitmaps de taille égale pour déterminer s'ils sont identiques?

Question

Je suis en train d'écrire une fonction pour déterminer si deux de taille égale bitmaps sont identiques ou pas. La fonction que j'ai droit compare simplement un pixel à la fois dans chaque image, retour faux sur le premier non-égalité de pixel.

Bien que cela fonctionne, et fonctionne bien pour les petites images, dans la production, je vais utiliser cela dans une boucle serrée, et sur de plus grandes images, j'ai donc besoin d'une meilleure façon. Quelqu'un aurait-il des recommandations?

La langue que j'utilise est C# par la manière - et oui, je suis déjà à l'aide de l' .LockBits méthode. =)

Edit: j'ai codé les mises en oeuvre de certaines des suggestions, et ici sont les points de repère. Le programme d'installation: deux identiques (dans le pire des cas), des bitmaps, 100x100 dans la taille, avec 10 000 itérations chaque. Voici les résultats:

CompareByInts (Marc Gravell) :   1107ms
CompareByMD5  (Skilldrick)   :   4222ms
CompareByMask (GrayWizardX)  :    949ms

Dans CompareByInts et CompareByMask je suis en utilisant des pointeurs pour accéder à la mémoire directement; dans le MD5 méthode que je suis en utilisant le Maréchal.Copie de récupérer un tableau d'octets et le passer comme un argument de MD5.ComputeHash. CompareByMask n'est que légèrement plus rapide, mais étant donné le contexte, je pense que toute amélioration est utile.

Merci à tous. =)

Edit 2: vous avez Oublié de tourner optimisations - faire qui donne GrayWizardX réponse encore plus d'un coup de pouce:

CompareByInts   (Marc Gravell) :    944ms
CompareByMD5    (Skilldrick)   :   4275ms
CompareByMask   (GrayWizardX)  :    630ms
CompareByMemCmp (Erik)         :    105ms

Intéressant de noter que la méthode MD5 n'améliorent pas du tout.

Edit 3: Posté ma réponse (comparateur de mémoire) qui a fait sauter les autres méthodes hors de l'eau. o.O

Answer 1

Edit 8-31-12: par Joey commentaire ci-dessous, être conscient du format des images bitmap que vous comparez. Ils peuvent contenir rembourrage sur les progrès qui rendent les images inégales, en dépit d'être l'équivalent de pixel-sage. Voir cette question pour plus de détails.

---

La lecture de cette réponse à une question concernant la comparaison des tableaux d'octets a donné une plus grande vitesse de méthode: à l'aide de P/Invoke et le comparateur de mémoire les appels de l'API dans msvcrt. Voici le code:

[DllImport("msvcrt.dll")]
private static extern int memcmp(IntPtr b1, IntPtr b2, long count);

public static bool CompareMemCmp(Bitmap b1, Bitmap b2)
{
    if ((b1 == null) != (b2 == null)) return false;
    if (b1.Size != b2.Size) return false;

    var bd1 = b1.LockBits(new Rectangle(new Point(0, 0), b1.Size), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);
    var bd2 = b2.LockBits(new Rectangle(new Point(0, 0), b2.Size), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);

    try
    {
        IntPtr bd1scan0 = bd1.Scan0;
        IntPtr bd2scan0 = bd2.Scan0;

        int stride = bd1.Stride;
        int len = stride * b1.Height;

        return memcmp(bd1scan0, bd2scan0, len) == 0;
    }
    finally
    {
        b1.UnlockBits(bd1);
        b2.UnlockBits(bd2);
    }
}

Answer 2

Si vous essayez de déterminer s'ils sont égaux à 100%, vous pouvez inverser l'un et l'ajouter à l'autre si son zéro, ils sont identiques. Étendre cela en utilisant du code dangereux, prendre 64 bits à la fois et faire le calcul de cette façon, toute différence peut entraîner un échec immédiat.

Si les images ne sont pas identiques à 100% (en comparant png à jpeg), ou si vous ne recherchez pas une correspondance à 100%, vous avez encore du travail devant vous.

Bonne chance.

Answer 3

Eh bien, vous utilisez .LockBits , donc vous utilisez probablement du code dangereux. Plutôt que de traiter chaque origine de ligne ( Scan0 + y * Stride ) comme un byte* , envisagez de la traiter comme un int* ; int arithmétique est assez rapide, et vous n'avez qu'à faire 1/4 de travail. Et pour les images en ARGB, vous pouvez toujours parler en pixels, ce qui simplifie les calculs.

Answer 4

Pourriez-vous prendre un hachage de chacun et comparer? Ce serait légèrement probabiliste, mais pratiquement pas.

Merci à Ram, voici un exemple d'implémentation de cette technique.

Answer 5

Si le problème est juste de trouver les doublons exacts entre les deux images, puis juste un peu au niveau de la comparaison aurez à faire. Je ne sais pas C# mais en C je voudrais utiliser la fonction suivante:

int areEqual (long size, long *a, long *b)
{
    long start = size / 2;
    long i;
    for (i = start; i != size; i++) { if (a[i] != b[i]) return 0 }
    for (i = 0; i != start; i++) { if (a[i] != b[i]) return 0 }
    return 1;
}

Je voudrais commencer à chercher dans le milieu, car je soupçonne qu'il ya une meilleure chance de trouver l'inégalité de bits de près le milieu de l'image que le début; bien sûr, ce serait vraiment dépendre sur les images vous sont deduping, la sélection aléatoire endroit pour commencer peut-être mieux.

Si vous essayez de trouver les doublons exacts entre des centaines d'images puis de les comparer toutes les paires d'entre eux est inutile. D'abord calculer le hash MD5 de chaque image et la placer dans une liste de paires (md5Hash, imageId); ensuite trier la liste par la m5Hash. Ensuite, seulement des comparaisons par paires sur les images qui ont le même md5Hash.