none
Compare Bitmaps in efficient way

    Question

  • Hi

     

    I am comparing two bitmaps by compare Size first then compare all the pixels, when two pixels are not the same, the algrithm will end and................... Phew!!!!!

     

    The problem is that I am creating an application that will work with images all the time

    and actually this comparing will be part of Equals method wich will be used by hashtable,  I will not just compare two images, I will compare one image to all the images in the hashtable, imagine comparing 1000,000 pixel 300 times. 

     

    if all the images are conatining (say a sea and sky) then I should hope that they are not fabricated images and the wind is fast on the day images was phtographed.  so that I don't have the same Sea and SKY, and every Equal will have to compare 500 pixel before, it says "they are not equal, return false".

     

    You see now, it is not efficient to use the suggested algorithm.

     

    So I will suggest another two things:

     

    - Use unmanged code ( but How ??????????????????????????? )

    - Downsample images, but I will say also how?????????????? because I always use

    Graphics.DrawImage and Graphics.interpolationMode.  and I don't want to draw Bitmap I want to DownSample it temproraly.

     

    another thing, if two different pictures downsampled, they might have the same pixel colors, but this is very rare, Do you agree? do u think it is a good idea?  what is the potential that wrong result appear??

     

    Any another thoughts ????????????

     

    Thank you for your time.

    Bye Bye

     

    Monday, June 18, 2007 11:19 AM

Answers

  • See this thread:  http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=1741989&SiteID=1  Comparing strings like this: 

    Code Snippet

          Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

                Dim S1 As String = My.Computer.FileSystem.ReadAllText("C:\Test1.bmp")

                Dim S2 As String = My.Computer.FileSystem.ReadAllText("C:\Test2.bmp")

                If String.Compare(S1, S2) = 0 Then

                      MsgBox("The two files are identical")

                Else

                      MsgBox("The two files are different")

                End If

          End Sub

    seems to work. 

     

    Monday, June 18, 2007 11:47 AM
  • I think this is about as fast as you can go:

        public unsafe static bool ImageEquals(Bitmap img1, Bitmap img2) {
          if (img1.Width != img2.Width || img1.Height != img2.Height) return false;
          if (img1.PixelFormat != img2.PixelFormat) return false;
          Rectangle rc = new Rectangle(0, 0, img1.Width, img1.Height);
          BitmapData bd1 = img1.LockBits(rc, ImageLockMode.ReadOnly, img1.PixelFormat);
          BitmapData bd2 = img2.LockBits(rc, ImageLockMode.ReadOnly, img1.PixelFormat);
          bool retval = true;
          int* p1 = (int*)bd1.Scan0;
          int* p2 = (int*)bd2.Scan0;
          int cnt = img1.Height * bd1.Stride / 4;
          for (int ix = 0; ix < cnt; ++ix)
            if (*p1++ != *p2++) {
              retval = false;
              break;
            }
          img1.UnlockBits(bd1);
          img2.UnlockBits(bd2);
          return retval;
        }

    Project + properties, Build tab, turn on "Allow unsafe code". I got 0.19 msec on a 300 x 300 x 24bpp image when they matched, 0.03 msec when they mis-matched on the first pixel.
    Thursday, June 21, 2007 4:38 PM
    Moderator
  • At some point you must be comparing bitmap files.  300 1,000,000 pixels bitmaps would occupy more than 1.2 GB of memory.

    If your 300 bitmaps only differ by one or two pixels and you have to compare each new bitmap with all 300, then you should use a native and assembly language dll to do the comparison. 

    If you have 300 distinct bitmaps all of the same format and width and height, how may distinct bitmaps do you have when you reduce the size of all of them by 1/4?  That is compare every other pixel in both directions.  By 1/4 again?

    Use graphics with NearestNeighbor interpolation to downsample the bitmaps.  The pixels you compare in the downsampled bitmaps will be the same as in the original bitmaps.

    You can probably make an hierarchal tree that will reduce most comparisons to a look-up table.

    Is the link I gave you the first one you found on these forums that contained errors?

    Thursday, June 21, 2007 9:18 PM
  • The nobugs way will compare the image data, so if 2 images are the same visually but have different formats, this method will return false, but maybe in your case you want to check the visual representation of the image, like you said you're after downsampling.
    For the downsampling, don't use interpolation since it involves calculation, and this alone will cost more time than the comparison. you can use simply do this(algorithm), the width iof the image is SX, the height is SY. constx, consty are constants.


    bool compare = true;
    for x = 1 to SX by step = SX/constx
    for y = 1 to SY by step = SY/consty
    if (color pixel from image1 on  (x,y) is not equal color pixel from image2 on  (x,y))
                       { compare = false; goto end;}
    next
    next

    end: return compare;


    constx < SX, if the images are too close constx should be high in value, say constx = SX/2, if the 2 images are too much different, constx will be something low, like constx = SX/100.
    If you need advanced downsampling, using interpolation, image filters... this should not be addressed in the class library forum.
    Hope this helped
    Friday, June 22, 2007 1:04 PM

All replies

  • See this thread:  http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=1741989&SiteID=1  Comparing strings like this: 

    Code Snippet

          Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

                Dim S1 As String = My.Computer.FileSystem.ReadAllText("C:\Test1.bmp")

                Dim S2 As String = My.Computer.FileSystem.ReadAllText("C:\Test2.bmp")

                If String.Compare(S1, S2) = 0 Then

                      MsgBox("The two files are identical")

                Else

                      MsgBox("The two files are different")

                End If

          End Sub

    seems to work. 

     

    Monday, June 18, 2007 11:47 AM
  • Thanks

    Actually I am comparing two Bitmap(s), not bitmaps files, Sorry I think I have not been clear enough.  Further, the link, which you have sent to me is full of errors, like suggesting to use Equals, Bitmap does not override Equals.  and I can compare Bitmaps, but I need to compare Bitmaps fast.

     

    so what do you think about downsampling bitmaps then comparing it?? Does downsampling might make two different pictures the same picture.  so is this comparing way valid?  and when and why it will no be valid??  I know this is a difficult question. but I hope that someone know how downsampling exactly works to tell me what he thinks?

    Thursday, June 21, 2007 1:18 PM
  • I think this is about as fast as you can go:

        public unsafe static bool ImageEquals(Bitmap img1, Bitmap img2) {
          if (img1.Width != img2.Width || img1.Height != img2.Height) return false;
          if (img1.PixelFormat != img2.PixelFormat) return false;
          Rectangle rc = new Rectangle(0, 0, img1.Width, img1.Height);
          BitmapData bd1 = img1.LockBits(rc, ImageLockMode.ReadOnly, img1.PixelFormat);
          BitmapData bd2 = img2.LockBits(rc, ImageLockMode.ReadOnly, img1.PixelFormat);
          bool retval = true;
          int* p1 = (int*)bd1.Scan0;
          int* p2 = (int*)bd2.Scan0;
          int cnt = img1.Height * bd1.Stride / 4;
          for (int ix = 0; ix < cnt; ++ix)
            if (*p1++ != *p2++) {
              retval = false;
              break;
            }
          img1.UnlockBits(bd1);
          img2.UnlockBits(bd2);
          return retval;
        }

    Project + properties, Build tab, turn on "Allow unsafe code". I got 0.19 msec on a 300 x 300 x 24bpp image when they matched, 0.03 msec when they mis-matched on the first pixel.
    Thursday, June 21, 2007 4:38 PM
    Moderator
  • At some point you must be comparing bitmap files.  300 1,000,000 pixels bitmaps would occupy more than 1.2 GB of memory.

    If your 300 bitmaps only differ by one or two pixels and you have to compare each new bitmap with all 300, then you should use a native and assembly language dll to do the comparison. 

    If you have 300 distinct bitmaps all of the same format and width and height, how may distinct bitmaps do you have when you reduce the size of all of them by 1/4?  That is compare every other pixel in both directions.  By 1/4 again?

    Use graphics with NearestNeighbor interpolation to downsample the bitmaps.  The pixels you compare in the downsampled bitmaps will be the same as in the original bitmaps.

    You can probably make an hierarchal tree that will reduce most comparisons to a look-up table.

    Is the link I gave you the first one you found on these forums that contained errors?

    Thursday, June 21, 2007 9:18 PM
  • The nobugs way will compare the image data, so if 2 images are the same visually but have different formats, this method will return false, but maybe in your case you want to check the visual representation of the image, like you said you're after downsampling.
    For the downsampling, don't use interpolation since it involves calculation, and this alone will cost more time than the comparison. you can use simply do this(algorithm), the width iof the image is SX, the height is SY. constx, consty are constants.


    bool compare = true;
    for x = 1 to SX by step = SX/constx
    for y = 1 to SY by step = SY/consty
    if (color pixel from image1 on  (x,y) is not equal color pixel from image2 on  (x,y))
                       { compare = false; goto end;}
    next
    next

    end: return compare;


    constx < SX, if the images are too close constx should be high in value, say constx = SX/2, if the 2 images are too much different, constx will be something low, like constx = SX/100.
    If you need advanced downsampling, using interpolation, image filters... this should not be addressed in the class library forum.
    Hope this helped
    Friday, June 22, 2007 1:04 PM
  • Test
    Monday, June 25, 2007 7:28 PM
  • Hi

     

    Thanks John Wein for your time. I will consider NearestNeighbor. but I will think about what bruno_1 had said, because it make a sense that DownSampling algorithms will cause more wasting of time. because it will put the algortihm in the worst case all the time, I mean what if the algorithm returns from the first comparison then it was wasting of time to downsample.  thus I might put something together and say, well (if they are more than 60000 Pixels square then Downsample, otherwise leave it as it is and do as nobugz says, with hope that worst case will not happen all the way in).

     

     bruno_1, your algorithm make a sense but. I think if u tryed to mathmatically conclude, what is the probability of having two different bitmaps having the same pixel on each step, you will find either "You will never know", or "probability >= .1" and this is not acceptable, because it will cause nasty bugs in my application......hmmmm I am not sure about that, I must rethink about it when I wake up tommorow.

     

    Thanks every one.  if things went bad, this answers will be helpful.


     

    Monday, June 25, 2007 7:54 PM
  • A pixel-by-pixel comparison is about as fast as you'll get it. Trying to do some fancy divide-and-conquer method (like bruno_1's method) will a) add extra calculations and b) make the code harder to understand anyway.

     

    To illustrate my point, there are basically four possibilities:

    1. The bitmaps are exactly the same,
    2. The bitmaps are wildly different,
    3. The bitmaps are almost the same (differing by only a couple of pixels), or
    4. The bitmaps are "kind of" the same

    #1 is obvious: you'd have to compare every pixel anyway.

     

    #2 is also pretty obvious - pixel-by-pixel or divide-and-conquer won't be much different because you're going to find a difference after only a couple of comparisons either way.

     

    #3 is where you need to think about it a bit more.  You may think divide-and-conquer would be "more likely" to find a difference sooner, but statistically speaking, it's still going to take n/2 comparisons to find a difference whether you choose divide-and-conquer or pixel-by-pixel.

     

    #4 is what you actually make your descision with. What are the chances that the bitmaps will be same with a difference in only certain areas? For example, if you're looking at two consecutive frames of a video stream -- most areas of the image are the same, only in localized areas are there differences. If this is the case, then divide-and-conquer may make a difference.

     

    So, to conclue, in the general case, pixel-by-pixel is statistically going to give you the same performance characteristics that divide-and-conquer will give. Application-dependenct characteristics of your image, however, may mean you're not always dealing with the "general case". Hope that makes sense

    Tuesday, June 26, 2007 5:13 AM
  • The word "Efficient" should be specified based on the most heavy task.

    For example, do the comparison operations have a higher performance cost than the disk\memory access? This depends on your platform and the way you store your bitmaps - for example, locking a texture in Direct X is not like reading a bmp file from the hard disk.The format with which you store your images also can make a difference. Some image compression techniques produces some sort of hash, so you can compare the compressed image bytes and if the two images are different you will find the compressed image bytes different at the start of the file so your comparison loop will be short.

    One thing to think about to decrease the comparison operations is comparing some pixels not all the pixels. If the two images have x pixels, you can skip 4 pixels every time, so you compare pixels 0,5,10,15, etc. The number of pixels you skip can be a variable that can be changed based on the expected level of variation between the images.You can also choose the pixels to compare randomly to be able to detect images that are different but share a sort of pattern. This also can decrease your disk access if you are reading pixel per pixel from the hard disk and not loading the whole image.

    The point is to think what is the most costing activity and try to decrease it. You can provide some more details about your application so that you can get more detailed answers.
    Tuesday, June 26, 2007 7:55 AM
  • HI

    Muhammad Adel, I just want to tell you that we are BALADIAT.  I am from Alex, and you are from Cairo or Alex.. I guess

     

    I beleive that stepping every some constant so that, you are comparing less number of pixels is a kind of gambling.  You will never know what is the probability of  having two pictures which are having the same pixel every (constant interval), and the rest of pixels are different.  I don't want to depend on Randomized Algorithm. even if it is too fast. 

     

    further

     

    I will convert everything to jpg with certain Color depth (I did not decide yet),

    Does JPG have that hashCode you are talking about?

     

    By the way Bitmaps are already in memory.  forget about HardDisk

     

    Dean Harding, I think I will Dig further in comparing images as raw bytes as alot of people said, specially if the first few bytes are that Hashcode.

     

    I think that I will buy a book in image processing.

     

    Bye

    Tuesday, June 26, 2007 9:50 AM
  • Careful with JPEG, it is a lossy compression and there's no guarantee made that it will compress the same way every time.  PNG would be a more reliable choice.
    Tuesday, June 26, 2007 12:34 PM
    Moderator
  • nobugz:

    From what I can decipher, I'm guessing he actually wants to compare pictures.  If that's the case then he needs a lot more than comparing pixels.  Visually two pictures can be identical with no two pixels being identical.  I think Fourier Analysis is probably necessary to compare pictures efficiently.  I'm also thinking that bitblt with ROP srcinvert and then counting the pixels above a threshold by area might be sufficient.

    Tuesday, June 26, 2007 2:12 PM
  • I dunno, the OP emphasized speed.  An algorithm that could find a match between two images that has something as trivial as a one pixel offset is not going to buy him speed. Srcinvert won't do it.  The OpenCV library is probably a good bet.
    Tuesday, June 26, 2007 8:37 PM
    Moderator
  • My srcinvert suggestion was for the case where we are comparing actual pictures.  That is where practically none of the pixels match, but the photos are visually identical.
    Tuesday, June 26, 2007 8:45 PM
  • I think we need more information here... what is the actual reason for comparing bitmaps?

     

    Clearly, skipping pixels is no good if you don't want any chance of false positives (i.e. saying two pictures are the same even if they differ by a single pixel).

     

    Secondly, with jpegs, if you're using the same compressor and parameters to compress, you're going to get the same image. The jpeg standard does not use random numbers, so the same algorithm will produce the same result. However, two different compressors will quite likely produce slightly different results for the same inputs -- depending on the details of their algorithm. But this is somewhat irrelevent.

     

    Anyway, if the OP could let us know what the application is actually doing the comparison for, we can probably come up with something better. If you need a pixel-perfect comparison then you'll have to compare pixel-by-pixel. If you only need to know if two images are visually the same, then something else is in order (and what sort of threshold are two images visually the same?)

    Thursday, June 28, 2007 3:06 AM