Thread: Algorithm that compares two images

  1. #1
    Registered User
    Join Date
    Apr 2008
    Posts
    204

    Algorithm that compares two images

    Firsly sorry to those in charge if you think I am reposting. My last thread changed topics basically, so maybe should get a more descriptive name.

    Secondly, I have written the following method to look for one bitmap inside another larger bitmap. The bitmaps are both 24 bit so I am converting the pixel data into 4 bytes and comparing the first three for each pixel.
    I think I am pretty close, but it always returns false even if the smaller image does exist inside the other. Can anyone spot the error of my ways?
    Code:
    bool comparePixelData(fstream &dFileLarge, Image &dInfoLarge, fstream &dFileSmall, Image &dInfoSmall)
    {
    
        unsigned int pixelLarge[dInfoLarge.imageWidth][dInfoLarge.imageHeight];
        unsigned int pixelSmall[dInfoSmall.imageWidth][dInfoSmall.imageHeight];
        unsigned char bytesLargeImage[4], bytesSmallImage[4];
        bool badPixel;
                    // Iterate through every row
                for (int fullRow = 0; fullRow < dInfoLarge.imageWidth; fullRow++)
                {
                    // Iterate through every pixel in the row
                    for (int fullColumn = 0; fullColumn < dInfoLarge.imageHeight; fullColumn++)
                    {
                        bytesLargeImage[0] = (pixelLarge[fullRow][fullColumn] >> 24) & 0xFF;
                        bytesLargeImage[1] = (pixelLarge[fullRow][fullColumn] >> 16) & 0xFF;
                        bytesLargeImage[2] = (pixelLarge[fullRow][fullColumn] >> 8) & 0xFF;
                        bytesLargeImage[3] = pixelLarge[fullRow][fullColumn] & 0xFF;
    
                        bytesSmallImage[0] = (pixelSmall[0][0] >> 24) & 0xFF;
                        bytesSmallImage[1] = (pixelSmall[0][0] >> 16) & 0xFF;
                        bytesSmallImage[2] = (pixelSmall[0][0] >> 8) & 0xFF;
                        bytesSmallImage[3] = pixelSmall[0][0] & 0xFF;
                        // If the current pixel on the full image is the
                        // same as the top left pixel on the small image...
                        if ((bytesLargeImage[0] == bytesSmallImage[0]) && (bytesLargeImage[1] == bytesSmallImage[1]) && (bytesLargeImage[2] == bytesSmallImage[2]))
                        {
                            // So far, we haven't found a mismatched pixel
                            badPixel = false;
    
                            // Iterate through every row in the small image
                            for (int smallRow = 0; smallRow < dInfoSmall.imageWidth; smallRow++)
                            {
                                // Iterate through every pixel in the row
                                for (int smallColumn = 0; smallColumn < dInfoSmall.imageHeight; smallColumn++)
                                {
                                                bytesLargeImage[0] = (pixelLarge[fullRow + smallRow][fullColumn + smallColumn] >> 24) & 0xFF;
                                                bytesLargeImage[1] = (pixelLarge[fullRow + smallRow][fullColumn + smallColumn] >> 16) & 0xFF;
                                                bytesLargeImage[2] = (pixelLarge[fullRow + smallRow][fullColumn + smallColumn] >> 8) & 0xFF;
                                                bytesLargeImage[3] = pixelLarge[fullRow + smallRow][fullColumn + smallColumn] & 0xFF;
    
                                                bytesSmallImage[0] = (pixelSmall[smallRow][smallColumn] >> 24) & 0xFF;
                                                bytesSmallImage[1] = (pixelSmall[smallRow][smallColumn] >> 16) & 0xFF;
                                                bytesSmallImage[2] = (pixelSmall[smallRow][smallColumn] >> 8) & 0xFF;
                                                bytesSmallImage[3] = pixelSmall[smallRow][smallColumn] & 0xFF;
    
                                    // If the pixel on the full image isn't the same as on the small image...
                                    if ((bytesLargeImage[0] != bytesSmallImage[0]) | (bytesLargeImage[1] != bytesSmallImage[1]) | (bytesLargeImage[2] != bytesSmallImage[2]))
                                    {
                                        // There is a mismatched pixel so set bad pixel to true
                                        badPixel = true;
    
                                        // Break out of inner loop
                                        break;
                                    }
                                }
    
                                // If we found a bad pixel, break out of outer loop
                                if (badPixel == true)
                                {
                                    break;
                                }
                            }
    
                            // If we passed through all pixels in small image, return location
                            if (badPixel == false)
                            {
                                return true;
                            }
                        }
                    }
                }
    
                // If we looped until here, not match was found
                return false;
    
    }
    Thanks

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Your code is difficult to read. The variable names are generally too long. Also, goto is useful (and COMPLETELY structured) for a double-break. You also have extraneous code (the separate check of the top-left pixel).

    As far as outright bugs, you have fullRow go up to dInfoLarge.imageWidth, but shouldn't it be imageHeight? Vice versa for the fullColumn. Same problem with smallRow and smallColumn.

    Even worse, you haven't initialized pixelLarge or pixelSmall! However, they seem kind of pointless if the data is available from dInfoLarge and dInfoSmall.

    Also, you're comparing all 4 bytes, but aren't the pixels 3 bytes? And can't you just compare the integers themselves instead of shifting their bits into an array of unsigned chars?
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    It probably would have been best to continue the previous thread, regardless of the title. But in any case, here's a link to it for others:
    bitmap images

    To make each pixel 3-bytes in size, you should have either a struct holding an array or three bytes, or a struct with 3 byte variables (red, green, blue), and in both cases you will want to #pragma pack(1)

    Do you have to read the bitmap yourself though? Here is a good piece of code that someone wrote for loading any bitmap into a 24 bit DIB:
    flipcode - 24-bit BGR Windows DIB Class

    As for the actual algorithm, you may want to consider writing something like a 2D version of the Boyer-Moore string matching algorithm, but for bitmaps. That would be a massive speed increase. I'll leave that as a separate thing for you to research.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Apr 2008
    Posts
    204
    Yeah, Im not sure what I did to result in all that white space at the bottom of the code. Yeah Im still trying to understand a global consensus on variable names. At work we code in Java and my team leader always says "make the variable names understandable - it doesnt matter how long they are". But then on C/C++ forums, I get told that long variable names are not a good idea, so Im still trying to work that one out and converge on a best option...

    Im not comparing all 4 bytes, I am setting the value of all 4 for debugging purposes, however only comparing the first three...

    iMalc, well Im trying to move from C to C++, and I learnt by OOP in java, so i want to do it myself really, otherwise it will be hard to get myself (will power...) to read the other code to understand what its doing.
    Yeah, I'll look into implementing that algorithm, thanks

  5. #5
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    As a general debugging technique, I'd suggest that you create a test case where the code SHOULD work, then step through the code and figure out why it DOESN'T.

    More specific to this problem, this kind of image comparison with four nested loops can be a headache to read and think about. It may help to split the work up to separate the checking of each possible match position from the looping over image pixels:

    Code:
    bool found = false;
    int rowOffset;
    int colOffset;
    for (rowOffset = 0; !found && rowOffset <= haystackHeight - needleHeight; ++rowOffset)
    {
        for (colOffset = 0; !found && colOffset <= haystackWidth - needleWidth; ++colOffset)
        {
            if (ImageMatchFound(rowOffset, colOffset))
            {
                found = true;
            }
        }
    }
    if (found)
    {
        // Image match was found at location rowOffset, colOffset within haystack
    }
    Where the ImageMatchFound() function just compares pixel-by-pixel and doesn't need to worry about looping over each match location. The code will be easier to understand and debug if you do this.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  6. #6
    Registered User
    Join Date
    Apr 2008
    Posts
    204

    Almost there!

    Hi guys, had to take a couple of weeks off this problem. Back on it now.

    So I simplified the algorithm so that its just comparing the integer values rather than trying to convert to rgb values. I also made the changes that oogabooga mentioned. Its still a little scruffy in places, such as the two loops to fill the pixel arrays.
    Firstly just to say my plan for my final algorithm, is to find the row in the smaller image with the most "entropy" and then search for that one. If it is found, look for the rest of the image around it. I think that will be quite a fast way of going about it.

    Secondly, there is good news and bad news. If I have two images identical and I ask it to find one within the other it is succesful. But if I crop the image down, so that I have a piece of the same image, it cant find it. I think I must be leaving the loop at the wrong time when it doesnt find the image.
    I have attached the cpp file, and two images flag1.bmp and flag2.bmp flag2 is a crop of flag1. The algorithm is on line 147
    If someone else could run it and see what they think that would be greatly appreciated.
    If you enter flag1.bmp as the large and small image, it finds it at 0,0. If you put flag2.bmp as the small image it doesnt find it.

    Thank you very much
    Alex
    Attached Images Attached Images Algorithm that compares two images-flag1-bmp Algorithm that compares two images-flag2-bmp 
    Attached Files Attached Files

  7. #7
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Although you probably do want to store each pixel as an integer for faster comparison, you can't read them in that way since each pixel only takes 3 bytes (not 4 or 8).

    Another problem is that each row is rounded up to the nearest multiple of 4, so there may be some bytes to skip at the end of each row. E.g., if the image is 10 pixels wide it will have 30 bytes of pixel info and then 2 extra bytes for each row.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Yep, you're still reading the pixels incorrectly.
    Please refer to my previous post, excluding the last paragraph for now as that is for when you get a basic version working first.

    Oh what the heck:
    Code:
    #pragma pack(1)
    struct BGR24Pixel {
    	unsigned char blue, green, red;
    };
    #pragma pack()
    or
    Code:
    #pragma pack(1)
    struct BGR24Pixel {
    	unsigned char comp[3];
    };
    #pragma pack()
    Now 'pixelLarge' etc needs to be an array of one of those.

    Either that or you need to do a conversion from 24-bit to 32-bit as you read it in. Your code is not doing that, though you are clearly trying to. The key mistake being that you read 4 bytes upon each read, instead of 3.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Another thing that you're doing wrong is that you have your loops reversed, varying your row variable faster than your column variable. I.e., you're doing this:
    Code:
        for(int i = 0; i < dInfoLarge.imageWidth; i++)
            for(int j = 0; j < dInfoLarge.imageHeight; j++)
            {
                dFileLarge.seekg(dInfoLarge.offSet + i);
                dFileLarge.read((char*)&pixelLarge[i][j], sizeof(pixelLarge[0][0]));
            }
    whereas you should be doing something like this:

    Code:
        dFileLarge.seekg(dInfoLarge.offSet);
        for(int i = 0; i < dInfoLarge.imageHeight; i++)
            for(int j = 0; j < dInfoLarge.imageWidth; j++)
                dFileLarge.read((char*)&pixelLarge[j][i], sizeof(pixelLarge[0][0]));
    except of course that you need to be reading data in three-byte chunks and have to skip the padding at the end of each row.

    Write a program that simply reads the bitmap data and prints it. Get that working before moving on. Use a simple little bitmap like the one below for testing. Remember that the RGB values are stored in reverse, BGR, and also that the rows are stored in reverse, the bottom row first the top row last.

    (The big version of the bmp file is just so people can see what it looks like. Use the small one to the lower left of the big one. It's easy to miss! )
    Attached Images Attached Images Algorithm that compares two images-test-bmp Algorithm that compares two images-test_big-bmp 
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  10. #10
    Registered User
    Join Date
    Apr 2008
    Posts
    204
    ok right. I kind of get what you mean. So My original method of trying to break it down to the bytes was probably better? But not comparing as Bytes, but integers? Any chance you can show me a slice of code to push me in the right direction? Thanks

  11. #11
    Registered User
    Join Date
    Apr 2008
    Posts
    204
    Sorry ignore that last message, I think I posted it and hadnt refreshed the page or something.
    OK I get what you mean about the structure, so I've changed the loading of the bitmap to this now (taking into account both your points):
    Code:
        BGR24Pixel pixelLarge[dInfoLarge.imageWidth][dInfoLarge.imageHeight];
    
        for(int i = 0; i < dInfoLarge.imageHeight; i++)
        {
            for(int j = 0; j < dInfoLarge.imageWidth; j++)
            {
                dFileLarge.seekg(dInfoLarge.offSet + i);
                dFileLarge.read(reinterpret_cast<char *>(&pixelLarge[i][j]), sizeof(pixelLarge[0][0]));
            }
        }
    So now Ive got to read the pixel data in correctly...what I understand is:
    pixel[i][j].blue needs to = (pixelLarge[i][j] >> 24) & 0xFF
    pixel[i][j].green needs to = (pixelLarge[i][j] >>16) & 0xFF
    pixel[i][j].red needs to = (pixelLarge[i][j] >> 8) & 0xFF

    that obviously wouldnt work, but in terms of pseudo-ing it I think based on your previous comments thats what I need to end up with?

    Im trying to work towards a method that displays the data here:
    Code:
    void displayPixelData(fstream &dFile, Image &dInfo)
    {
        BGR24Pixel pixel[dInfo.imageWidth][dInfo.imageHeight];
        unsigned char bytes[4];
        int imageSize = sizeof(pixel[0][0]);
        for(int i = 0; i < dInfo.imageHeight; i++)
        {
            for(int j = 0; j < dInfo.imageWidth; j++)
            {
                dFile.seekg(dInfo.offSet + i);
                dFile.read(reinterpret_cast<char *>(&pixel[i][j]), imageSize);
              cout << "@ " << i << ":" << j << " = " << pixel[i][j].blue << " & " << pixel[i][j].green << " & " << pixel[i][j].red << endl << endl;
            }
        }
    }
    but its this line:
    dFile.read(reinterpret_cast<char *>(&pixel[i][j]), imageSize);
    thats catching me out, because Im not sure how to get the pointer to direct the correct bytes into the BGR parts of the struct.

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You've got the cast, and in fact the whole read line correct.

    I think the issue now is that seekg. Firstly, you should no longer need to seek inside the innermost loop. Secondly, you'll need to multiply i by the rowBytes. Afterall, the next line down doesn't start a mere one byte after the start of the previous line.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  13. #13
    Registered User
    Join Date
    Apr 2008
    Posts
    204
    Hi iMalc,
    so I get what you mean about the seekg line, but Im confused as to what you mean about rowBytes. I dont quite get why the next row wouldnt be on the next row if that makes any sense?

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Okay, lets imagine that dInfo.imageWidth is 64 and dInfo.offSet is 30.
    The calculation you have makes the first line start at 30 bytes into the file and continue for 64 more bytes, up to byte 93
    The second line starts at 31 bytes into the file and continue for 64 more bytes, up to byte 94
    The third line starts at 32 bytes into the file and continue for 64 more bytes, up to byte 95
    Notice how the lines overlap?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #15
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Just so we're clear on the format, here's the pixel data for a 3x3 square with all red in the top row, all green in the middle row, all blue in the bottom row (remember RGB's are stored BGR and the rows are stored in reverse order). Note the 3 padding bytes at the end of each row (to make the bytes in each row a multiple of 4).
    Code:
    ff 00 00  ff 00 00  ff 00 00  00 00 00      # all blue (bottom row)
    00 ff 00  00 ff 00  00 ff 00  00 00 00      # all green (middle row)
    00 00 ff  00 00 ff  00 00 ff  00 00 00      # all red (top row)
    You only need to do the seek ONCE, before the double loop, to the position that the pixel data begins. After that, each time you do a read, the file pointer is automatically incremented.

    Personally, I might read the pixel data something like the code below. I wouldn't bother storing R, G, B separately because you're not actually interested in those values. The code below reads the data a byte at a time and only seeks once.
    Code:
    unsigned **
    readPixelData(fstream &dFile, Image &dInfo)
    {
        // Dynamically create a 2D array.
        unsigned **pixels = new unsigned *[dInfo.imageWidth];
        for (int x = 0; x < dInfo.imageWidth; x++)
            pixels[x] = new unsigned[dInfo.imageHeight];
    
        // Position file pointer to start of pixel data.
        dFile.seekg(dInfo.offSet);
    
        // Read pixel data.
        for(int y = 0; y < dInfo.imageHeight; y++) {
            char byte;
            for(int x = 0; x < dInfo.imageWidth; x++) {
                unsigned n;
                dFile.get(byte);  n = (byte & 0xff);
                    //cout << setw(3) << (byte & 0xff) << ' ';
                dFile.get(byte);  n = (n << 8) | (byte & 0xff);
                    //cout << setw(3) << (byte & 0xff) << ' ';
                dFile.get(byte);  n = (n << 8) | (byte & 0xff);
                    //cout << setw(3) << (byte & 0xff) << "    ";
                pixels[x][y] = n;
                    //cout << setw(8) << pixels[x][y] << '\n';
            }
    
            // Skip padding bytes at the end of each row.
            for (int i = 0; i < 4 - dInfo.imageWidth % 4; i++)
                dFile.get(byte);
    
            //cout << '\n';
        }
    
        return pixels;
    }
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 12-14-2009, 07:42 AM
  2. compares 2 arguments and replaces characters
    By help123 in forum C Programming
    Replies: 9
    Last Post: 04-14-2005, 09:22 AM
  3. Images
    By face_master in forum Windows Programming
    Replies: 4
    Last Post: 07-29-2002, 12:03 AM
  4. Compares C++ and Pascal
    By Jaguar in forum A Brief History of Cprogramming.com
    Replies: 13
    Last Post: 07-19-2002, 11:28 AM