Comparer 2 bitmap rapidement

Version imprimable

21/04/2008, 23h00
deejay2221

Comparer 2 bitmap rapidement

Bonjours.

Je suis en train de développer un programme qui fais des captures d'écrans et compare l'image avec l'ancienne.

Naturellement j'ai débuté en faisant une double boucle en passant chacun des pixels avec la fonction GetPixel() mais c'est extrèmement lent et ça rempli la mémoire de classes inutilement.

Mon Core 2 Duo 2.33 est au maximum pendant au moins 2 secondes pour chacune des images traité. C'est trop lent.

Quelqu'un aurait connaissance d'une façon plus rapide et moins exigeant pour le CPU?

Merci
21/04/2008, 23h36
smyley

Si tu enregistre l'image dans un MemoryStream et que tu calcules sont Hash, ça pourrai peut être servir de méthode plus rapide non ? (et si deux Hash sont égaux, tu reprends l'ancienne méthode pour être sur).
22/04/2008, 00h57
tomlev

Citation:

Envoyé par smyley

Si tu enregistre l'image dans un MemoryStream et que tu calcules sont Hash, ça pourrai peut être servir de méthode plus rapide non ? (et si deux Hash sont égaux, tu reprends l'ancienne méthode pour être sur).

Je ne suis pas sûr que ça change grand chose aux perfs... dans un cas comme dans l'autre, on va quand même lire toutes les données des 2 images. Cela dit, la méthode GetPixel est réputée assez lente, donc ça vaut peut-être le coup d'essayer...

Par contre pour le coup des 2 hash égaux, je pense pas que ce soit une bonne idée. Dans la plupart des cas l'image va être identique (si on a touché à rien entre temps), donc l'ancienne méthode va être appelée quasiment à chaque fois. De toutes façons, la probabilité d'avoir une collision (même hash pour 2 images différentes) est infime, donc je pense que le test sur les hash est suffisant.
22/04/2008, 01h50
smyley

Citation:

Envoyé par tomlev

Par contre pour le coup des 2 hash égaux, je pense pas que ce soit une bonne idée. Dans la plupart des cas l'image va être identique (si on a touché à rien entre temps), donc l'ancienne méthode va être appelée quasiment à chaque fois. De toutes façons, la probabilité d'avoir une collision (même hash pour 2 images différentes) est infime, donc je pense que le test sur les hash est suffisant.

Non mais le truc aurait été qu'il trouve par malchance une collision et le programme ne fonctionnerai pas correctement et personne ne saurait pourquoi vu que c'est pas trop à ça qu'on pense en premier. Il faudrait quand même vérifier, peut être avec quelques pixels pris aux hasard par exemple car même si la probabilité est très petite, elle n'est pas nulle (d'ailleurs un hash en moyenne ne dépasse pas quelques octets alors allez voir le nombre de combinaisons possibles de bit dans le hash par rapport au nombre de combinaisons possibles de bit dans une image de 400 Ko :aie:)
22/04/2008, 10h58
tomlev

Une autre solution, si on est pas trop regardant sur la précision, serait de générer des miniatures des 2 images (Image.GetThumbnailImage) et de comparer ces miniatures. Ca irait nettement plus vite...

On parle ici de capture d'écran, donc d'image assez petite finalement, avec une résolution de 72 dpi. C'est vraiment pas énorme.

L'idée du hash est très bonne; c'est ce que je ferais. Mais tu peux continuer sur ta lancée en comparant les pixels, il y a moyen de contourner GetPixels via une méthode unsafe.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
using System;
using System.Drawing;
using System.Drawing.Imaging;
 
namespace Image {
    public unsafe class FastBitmap {
 
        public struct PixelData {
            public byte blue;
            public byte green;
            public byte red;
        }
 
        Bitmap Subject;
        int SubjectWidth;
        BitmapData bitmapData = null;
        Byte* pBase = null;
 
        public FastBitmap(Bitmap SubjectBitmap) {
            this.Subject = SubjectBitmap;
            try {
                LockBitmap();
            } catch (Exception ex) {
                throw ex;
            }
 
        }
 
        public void Release() {
            try {
                UnlockBitmap();
            } catch (Exception ex) {
                throw ex;
            }
        }
 
        public Bitmap Bitmap {
            get {
                return Subject;
            }
        }
 
        public void SetPixel(int X, int Y, Color Colour) {
            try {
                PixelData* p = PixelAt(X, Y);
                p->red = Colour.R;
                p->green = Colour.G;
                p->blue = Colour.B;
            } catch (AccessViolationException ave) {
                throw (ave);
            } catch (Exception ex) {
                throw ex;
            }
        }
 
        public Color GetPixel(int X, int Y) {
            try {
                PixelData* p = PixelAt(X, Y);
                return Color.FromArgb((int)p->red, (int)p->green, (int)p->blue);
            } catch (AccessViolationException ave) {
                throw (ave);
            } catch (Exception ex) {
                throw ex;
            }
        }
 
        private void LockBitmap() {
            GraphicsUnit unit = GraphicsUnit.Pixel;
            RectangleF boundsF = Subject.GetBounds(ref unit);
            Rectangle bounds = new Rectangle((int)boundsF.X,
                (int)boundsF.Y,
                (int)boundsF.Width,
                (int)boundsF.Height);
 
            SubjectWidth = (int)boundsF.Width * sizeof(PixelData);
            if (SubjectWidth % 4 != 0) {
                SubjectWidth = 4 * (SubjectWidth / 4 + 1);
            }
 
            bitmapData = Subject.LockBits(bounds, ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
            pBase = (Byte*)bitmapData.Scan0.ToPointer();
        }
 
        private PixelData* PixelAt(int x, int y) {
            return (PixelData*)(pBase + y * SubjectWidth + x * sizeof(PixelData));
        }
 
        private void UnlockBitmap() {
            Subject.UnlockBits(bitmapData);
            bitmapData = null;
            pBase = null;
        }
    }
}

22/04/2008, 14h21
suvuk

Le framework a déjà des outils pour faire ça, va voir http://msdn2.microsoft.com/en-us/library/5ey6h79d.aspx.
Tu fais un lockbits puis copy sur chacune de tes images et ensuite tu compare octet par octet (dès que tu trouve une différence, tu stoppe).
J'avais fait un petit programme de gestion d'images (y'a un moment, j'ai plus le code sous la main) qui mettais quelques dixièmes de seconde pour inverser ou appliquer un filtre à une image 1280x1024, je trouve ça honnête
22/04/2008, 15h22
deejay2221

wow merci

J'ai de la misère à comprendre chacune de vos réponse ou presque. Je n'avais jamais entenu parlé du Hash avant. J'avais déjà vu l'option avant dans l'intellisens, sans savoir ça servait à quoi.

Je vais regarder ça en détail. Je vais aussi regarder si la méthode GetThumbnailImage antialias les images. Si oui, un pixel peut faire une différence sur 24 bits de couleurs et donc, ça peut être assez précis pour moi.

Je vais aussi vérifier ce que fait lockbit, et finalement la méthode unsafe avant de mettre cette discution comme résolu ;)

Merci encore
22/04/2008, 15h37
tomlev

Citation:

Envoyé par deejay2221

Je n'avais jamais entenu parlé du Hash avant. J'avais déjà vu l'option avant dans l'intellisens, sans savoir ça servait à quoi.

Attention, il ne s'agit pas de la méthode GetHashCode... dans ce contexte, un hash est un code qui permet de caractériser un objet en tenant compte de toutes ses données. Pour 2 objets identiques, le hash sera toujours identique. Pour 2 objets différents, il devrait être toujours différent (si ce n'est pas le cas, on a affaire à une collision, mais c'est très rare).
Pour plus d'infos là-dessus, va faire un tour sur Wikipedia :
http://fr.wikipedia.org/wiki/Hash
22/04/2008, 17h34
deejay2221

ah oké parfait!

Mais si on n'accède pas au Hash par GetHashCode, on fait comment alors?

Là je viens d'essayé la solution à Suvuk :
http://msdn2.microsoft.com/en-us/library/5ey6h79d.aspx

La boucle se fait en une fraction de seconde et le CPU n'a même pas l'air de travailler. C'est génial. Sauf que je ne suis pas plus avancé puisque les comparaisons fonctionnent pour 1/2 seconde au début et puis après je n'ai plus rien. La comparaison d'image dit que les 2 images sont toujours identiques.

Je n'ai aucune idée d'où ça vient. Je ne sais pas si c'est un bug de pointeur ou quoi... pourtant j'ai copié exactement le code de MSDN. C'est que c'est long de débugger en passant dans une boucle de plus de 7 millions de bytes :(

Si je ne trouve pas, je vais essayer le truc du hash
22/04/2008, 17h44
suvuk

Tu dois avoir un soucis ailleurs, tu peux faire envoyer le code ?

J'ai oublié de vous envoyé mon code
Si ça peut vous aider ;)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
    public static byte[] RGBValues(Bitmap p_bmp)
        {
            // Lock the bitmap's bits.  
            Rectangle rect = new Rectangle(0, 0, p_bmp.Width, p_bmp.Height);
            System.Drawing.Imaging.BitmapData bmpData =
                p_bmp.LockBits(rect, System.Drawing.Imaging.ImageLockMode.ReadWrite,
                p_bmp.PixelFormat);
 
            // Get the address of the first line.
            IntPtr ptr = bmpData.Scan0;
 
            // Declare an array to hold the bytes of the bitmap.
            int bytes = bmpData.Stride * p_bmp.Height;
            byte[] rgbValues = new byte[bytes];
 
            // Copy the RGB values into the array.
            System.Runtime.InteropServices.Marshal.Copy(ptr, rgbValues, 0, bytes);
 
            // Unlock the bits.
            p_bmp.UnlockBits(bmpData);
 
            return rgbValues;
        }
 
    public static bool SontBitmapsDifferents(Bitmap p_bmp1, Bitmap p_bmp2)
        {
            byte[] bits1 = RGBValues(p_bmp1);
            byte[] bits2 = RGBValues(p_bmp2);
 
            for (int i = 0; i != bits1.Length; i++)
            {
                if (bits1[i] != bits2[i])
                    return false;
            }
            return true;
        }

22/04/2008, 17h59
suvuk

:koi: Y'a aucune raison que ce code ne marche pas, le problème est peut être plus haut, dans les fonctions qui appellent SontBitmapsDifferents... tu n'as pas de fuites mémoires (ça peut provoquer des comportements étranges), tu t'emmêle pas en passant les paramètres... ?

(au fait, dans ton for tu devrais mettre i < bits1.Length au lieu de !=)
22/04/2008, 18h00
tomlev

Citation:

Envoyé par deejay2221

Mais si on n'accède pas au Hash par GetHashCode, on fait comment alors?

En utilisant les fonctionnalités de cryptographie du framework. Par exemple, les classes MD5CryptoServiceProvider (pour un hash MD5, 128bits) ou SHA1CryptoServiceProvider (pour un hash SHA-1, 160bits), ou même SHA512CryptoServiceProvider (SHA512, 512 bits).
Plus la taille du hash est importante, moins tu as de risque de collisions (mais c'est plus long à calculer)
22/04/2008, 18h12
deejay2221

Citation:

En utilisant les fonctionnalités de cryptographie du framework. Par exemple, les classes MD5CryptoServiceProvider (pour un hash MD5, 128bits) ou SHA1CryptoServiceProvider (pour un hash SHA-1, 160bits), ou même SHA512CryptoServiceProvider (SHA512, 512 bits).
Plus la taille du hash est importante, moins tu as de risque de collisions (mais c'est plus long à calculer)

Merci beaucoup !!!

Pour ce qui est de mon code, j'avais seulement inverser les return true et return false comme un cave. J'avais pris ma fonction dans le sens de SontBitmapsIdentique() au lieu de SontBitmapsDifferents() :roll:

Là ça marche #1 !!! :mrgreen:

Merci tout le monde