C++

Forum

 
Efficiently Comparing two Bitmaps (Pixel Arrays)

Jack Hammered (30)
I have a bitmap stored in an array (unsigned char* lpPixelArray) which is taken via WinAPI (Screen-shots). I was wondering how efficient my current method of comparison is (I did try memcpr at one point but it was taking a lot longer to process) and my loops!.

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
 
int iLenX = 0;
	int iLenY = 0;

	// Checks whether to scan / poll the taskbar
	if (SingleMonitorInfo::intCheckTaskbar)
	{
		iLenX = (SingleMonitorInfo::rcMonitorArea.right - SingleMonitorInfo::rcMonitorArea.left);
		iLenY = (SingleMonitorInfo::rcMonitorArea.bottom - SingleMonitorInfo::rcMonitorArea.top);
	}
	else
	{
		iLenX = (SingleMonitorInfo::rcWorkArea.right - SingleMonitorInfo::rcWorkArea.left);
		iLenY = (SingleMonitorInfo::rcWorkArea.bottom - SingleMonitorInfo::rcWorkArea.top);
	}

	unsigned long byteStreamSize = (iLenX * 4 * iLenY);

	if (iLenX <= 0 && iLenY <= 0)
	{
		// ERROR HANDELING
		/* "Error calculating desktop area" */
		return 1;
	}

	HDC hDisplay = CreateDC(SingleMonitorInfo::szDeviceName, SingleMonitorInfo::szDeviceName, NULL, NULL);
	if (!hDisplay)
	{
		// ERROR HANDELING
		/* "Error creating DC" */
		return 2;
	}

	HDC hBuffer = CreateCompatibleDC(hDisplay);
	if (!hBuffer)
	{
		// ERROR HANDELING
		/* "Error creating compatible DC" */
		DeleteDC(hDisplay);
		return 3;
	}

	HBITMAP hBitmap = CreateCompatibleBitmap(hDisplay, iLenX, iLenY);
	if (!hBitmap)
	{
		// ERROR HANDELING
		/* "Error creating compatible bitmap" */
		DeleteDC(hBuffer);
		DeleteDC(hDisplay);
		return 4;
	}

	HBITMAP hPreviousBitmap = static_cast<HBITMAP>(SelectObject(hBuffer, hBitmap));
	if (!hPreviousBitmap)
	{
		// ERROR HANDELING
		/* "Error selecting previous bitmap" */
		DeleteDC(hBuffer);
		DeleteDC(hDisplay);
		DeleteObject(hBitmap);
		return 5;
	}

	if (!BitBlt(hBuffer, 0, 0, iLenX, iLenY, hDisplay, 0, 0, SRCCOPY))
	{
		// ERROR HANDELING
		/* "Error with bit block transfer" */
		SelectObject(hBuffer, hPreviousBitmap);
		DeleteDC(hBuffer);
		DeleteDC(hDisplay);
		DeleteObject(hBitmap);
		DeleteObject(hPreviousBitmap);
		return 6;
	}

	BITMAP bmpDisplay;

	if (!GetObject(hBitmap, sizeof(BITMAP), &bmpDisplay))
	{
		// ERROR HANDELING
		/* "Cannot get bitmap object" */
		SelectObject(hBuffer, hPreviousBitmap);
		DeleteDC(hBuffer);
		DeleteDC(hDisplay);
		DeleteObject(hBitmap);
		DeleteObject(hPreviousBitmap);
		return 7;
	}

	BITMAPINFOHEADER bmpInfo;

	bmpInfo.biSize = sizeof(BITMAPINFOHEADER);
	bmpInfo.biWidth = bmpDisplay.bmWidth;
	bmpInfo.biHeight = bmpDisplay.bmHeight;
	bmpInfo.biPlanes = 1;
	bmpInfo.biBitCount = 32;
	bmpInfo.biCompression = BI_RGB;
	bmpInfo.biSizeImage = 0;
	bmpInfo.biXPelsPerMeter = 0;
	bmpInfo.biYPelsPerMeter = 0;
	bmpInfo.biClrUsed = 0;
	bmpInfo.biClrImportant = 0;

	unsigned char* lpBitmap = NULL;
	lpBitmap = (unsigned char*)malloc(byteStreamSize);

	if (!GetDIBits(hBuffer, hBitmap, 0, iLenY, lpBitmap, (BITMAPINFO *)&bmpInfo, DIB_RGB_COLORS))
	{
		// ERROR HANDELING
		/* "GetDIBits failed" */
		SelectObject(hBuffer, hPreviousBitmap);
		DeleteDC(hBuffer);
		DeleteDC(hDisplay);
		DeleteObject(hBitmap);
		DeleteObject(hPreviousBitmap);
		free(lpBitmap);
		return 8;
	}

	if (lpBitmap == NULL)
	{
		// ERROR HANDELING
		/* "GetDIBits copy to lpBitmap failed" */
		SelectObject(hBuffer, hPreviousBitmap);
		DeleteDC(hBuffer);
		DeleteDC(hDisplay);
		DeleteObject(hBitmap);
		DeleteObject(hPreviousBitmap);
		free(lpBitmap);
		return 9;
	}


This is how I grab the pixel stream using WinAPI.

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
// Checks if there is currently a pixel array
	if (!lpPixelArray)
	{
	// If array is NULL copy pixel array
		lpPixelArray = (unsigned char*)malloc(iLenX * 3 * iLenY);
		int i = 0;
		while (i < (iLenX * iLenY))
		{
			// The new array has 4 bytes Red Green Blue and Alpha per pixel, however only Red Green and Blue is needed
			lpPixelArray[(i * 3)] = lpBitmap[(i * 4)];
			lpPixelArray[(i * 3) + 1] = lpBitmap[(i * 4) + 1];
			lpPixelArray[(i * 3) + 2] = lpBitmap[(i * 4) + 2];
			i++;
		}
		SelectObject(hBuffer, hPreviousBitmap);
		DeleteDC(hBuffer);
		DeleteDC(hDisplay);
		DeleteObject(hBitmap);
		DeleteObject(hPreviousBitmap);
		free(lpBitmap);
		return 0;
	}
	else
	{
	// If there is an array it compares the new array against the old
		// If the double dMaxPercentDifference is greater or equal to one
		if (SingleMonitorInfo::dMaxPercentDifference >= 1)
		// If greater or equal to one - (As soon as one pixel is different, it should exit)
		{
			int i = 0;
			while (i < (iLenX * iLenY))
			{
				// The new array has 4 bytes Red Green Blue and Alpha per pixel, however only Red Green and Blue is needed
				if ((lpPixelArray[(i * 3)]) != (lpBitmap[(i * 4)]) ||
					(lpPixelArray[(i * 3) + 1]) != (lpBitmap[(i * 4) + 1]) ||
					(lpPixelArray[(i * 3) + 2]) != (lpBitmap[(i * 4) + 2]))
				{
					while (i < (iLenX * iLenY))
					{
						lpPixelArray[(i * 3)] = lpBitmap[(i * 4)];
						lpPixelArray[(i * 3) + 1] = lpBitmap[(i * 4) + 1];
						lpPixelArray[(i * 3) + 2] = lpBitmap[(i * 4) + 2];
						i++;
					}
					SelectObject(hBuffer, hPreviousBitmap);
					DeleteDC(hBuffer);
					DeleteDC(hDisplay);
					DeleteObject(hBitmap);
					DeleteObject(hPreviousBitmap);
					free(lpBitmap);
					return 0;
				}
				else
				{
					i++;
				}
			}
			SelectObject(hBuffer, hPreviousBitmap);
			DeleteDC(hBuffer);
			DeleteDC(hDisplay);
			DeleteObject(hBitmap);
			DeleteObject(hPreviousBitmap);
			free(lpBitmap);
			return 0;
		}
		else
		// else if less than one - (As soon as % pixels are different, it should exit)
		{
			int i = 0, j = 0;
			int iMax = static_cast<int>(iLenX * iLenY * SingleMonitorInfo::dMaxPercentDifference);
			int iMin = ((iLenX * iLenY) - iMax);

			if (iMin < 0)
			{
				return 11;
			}

			while (i < iMax)
			{
				if (j <= iMin)
				{
					if ((lpPixelArray[(i * 3)]) != (lpBitmap[(i * 4)]) ||
						(lpPixelArray[(i * 3) + 1]) != (lpBitmap[(i * 4) + 1]) ||
						(lpPixelArray[(i * 3) + 2]) != (lpBitmap[(i * 4) + 2]))
					{
						lpPixelArray[(i * 3)] = lpBitmap[(i * 4)];
						lpPixelArray[(i * 3) + 1] = lpBitmap[(i * 4) + 1];
						lpPixelArray[(i * 3) + 2] = lpBitmap[(i * 4) + 2];
						j++;
					}
					i++;
				}
				else
				{
					for (int c = i; c < (iLenX * iLenY); c++)
					{
						lpPixelArray[(i * 3)] = lpBitmap[(i * 4)];
						lpPixelArray[(i * 3) + 1] = lpBitmap[(i * 4) + 1];
						lpPixelArray[(i * 3) + 2] = lpBitmap[(i * 4) + 2];
					}
					SelectObject(hBuffer, hPreviousBitmap);
					DeleteDC(hBuffer);
					DeleteDC(hDisplay);
					DeleteObject(hBitmap);
					DeleteObject(hPreviousBitmap);
					free(lpBitmap);
					return 0;
				}
			}
			SelectObject(hBuffer, hPreviousBitmap);
			DeleteDC(hBuffer);
			DeleteDC(hDisplay);
			DeleteObject(hBitmap);
			DeleteObject(hPreviousBitmap);
			free(lpBitmap);
			return 0;
		}
	}
	return 0;


Here is the probably highly inefficient code to compare the lpPixelArray(s). Would you suggest I have different return values? Such as:
(0 for success and unchanged)
(-1 for success and changed)
(>0 for failed method and error code)
wizebin (148)
To be honest, I'm impressed with the way your code looks, it looks fairly well thought out. Although your variable names suffer from algorithmic ambiguities, I'm not sure you can choose any more verbose names because of the nature of the code.

It is difficult to make comparisons any more efficient simply because you do have to look at each byte.

Your computer is capable of many many millions of operations per second (probably around 2 billion flat operations) so sometimes it is not necessary to change code, especially if you're not having issues with your current code. This is a common issue called premature optimization.

That being said, there are always things you can do to speed things up if you're clever.

In this case, since you know each image is going to be the same size, you can prioritize what bytes you check first by using a heat map. As you do your normal operation you can keep track of which bytes tend to be different the most, and check a sample of those bytes first.

As far as your return codes, you can do what you'd like, but I dislike having negative success messages. Just be consistent.

Jack Hammered (30)
Thank you, I thought the names were useful and I don't understand what you mean from algorithmic ambiguity. The names always confuse me no matter how I write them.

I like your idea of a heat map! Sounds like a fun. I keep thinking of methods to do this, but currently I can only think of either hashmaps, which I don't think are suitable here, or adding another index array the same size. I will do further research on this, though there doesn't seem to be much relevant reading that I could find.

Basically I cannot think of a way of having a dynamically increasing array that then would return to the simple incremental loops: Well not a way that does it efficiently... As I am unsure how it would then 'skip' over the already checked bytes.

So would you suggest:
(0 for success and unchanged)
(+1 for success and changed)
(<0 for failed method and error code)
For the error codes so that it is more generically understandable / logical?
Jack Hammered (30)
Also it seems my class might benefit from the copy and swap idiom wrapper for the lpPixelArray. Information found here: http://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom

Although I understand very little of it, would it be possible to do a similar thing with my class?
Topic archived. No new replies allowed.