CODEWITHSUNDEEP
arrayswindowssearchbitmap
Govind Parmar
Govind Parmar

Reputation: 21532

Finding a sub-bitmap within a bitmap?

I'm trying to write an algorithm to determine whether the bits in a 24-bit bitmap loaded from a file exists within an array of bits already in memory. This is not as easy as it sounds: the array memBmp is returned from GetDIBits, so it is a series of rows and padding; so finding whether a sub-bitmap exists does not simply involve comparing contiguous subarrays within memBmp.

Example:

memBmp:

0 0 0 0 0 1 0 1 0 0

0 0 0 0 0 1 0 1 0 0

0 0 0 0 0 1 0 1 0 0

If the bitmap loaded from the file consisted of:

1 0 1

1 0 1

1 0 1

This algorithm would need to recognize that that is a "sub-bitmap" of memBmp.

I have the basic outline set up, but I am completely clueless as to how to write the match-checking part of this algorithm:

int FindBitmap(TCHAR *file, BYTE *memBmp, int membmpWidth, int membmpHeight)
{
    HBITMAP hBitmap = (HBITMAP) LoadImage(NULL, file, IMAGE_BITMAP, 0, 0, LR_LOADFROMFILE);

    BITMAP bm;
    HDC hDC1 = CreateCompatibleDC(NULL);
    BITMAPINFO bi;
    BYTE *data;
    if(!hBitmap)
    {
        return -1;
    }
    GetObject(hBitmap, sizeof(bm), &bm);
    SelectObject(hDC1, hBitmap);
    bi.bmiHeader.biSize = sizeof(BITMAPINFOHEADER);
    bi.bmiHeader.biWidth = bm.bmWidth;
    bi.bmiHeader.biHeight = -bm.bmHeight;
    bi.bmiHeader.biPlanes = 1;
    bi.bmiHeader.biBitCount = 24;
    bi.bmiHeader.biCompression = BI_RGB;        
    bi.bmiHeader.biSizeImage = 0;        

    data = (BYTE*)malloc(4*bm.bmWidth*bm.bmHeight);
    GetDIBits(hDC1, hBitmap, 0, bm.bmHeight, data, &bi, DIB_RGB_COLORS);

    // Now what?

    free(data);
    return 0;

}

Upvotes: 0

Views: 287

Answers (2)

Mahmoud Fayez
Mahmoud Fayez

Reputation: 3459

search for the first row then compare the subsequent rows when you find it

for (i = 0; i < ImgWidth - TrgtWidth; i ++)
{
    for (j = 0; j < ImgHeight - TrgtHeight; j++)
    {
        // find first row of trgt[0] at location img[i][j]
        // if you find it iterate over the other rows to confirm they also match.
        // otherwise continue looking for match only for the first row.
    }
}

Upvotes: 1

Floris
Floris

Reputation: 46365

Turn your array on its side and add a fourth column of zeros. Do the same with your sub bitmap. Now recognize that the four bits in a row represent a hex digit, construct the hex string for both (8 elements long for one, some value for the other). Use string matching functions to see if one exists in the other.

Example with bitmap you gave:

00010100
00010100
00010100

Turn on its side, add zeros:

0000 = '0'
0000 = '0'
0000 = '0'
1110 = 'E'
0000 = '0'
0000 = 'E'
0000 = '0'
0000 = '0'

Do the same for the sub array :

1110 = 'E'
0000 = '0'
0000 = 'E'

So you can now search for "E0E" in "000E0E00" - which will match.

you don't really need to add the zeros - you can treat the three bits in a row as an octal number (0-7). But using string matching functions for the final "does X belong to Y" will make your life easier...

Upvotes: 1

Related Questions