C / C++ / MFC

jhwurmbach9-Oct-07 1:16

9-Oct-07 1:16

You loop over the pixel and make a map<int, int=""> with the color_number as key and the number of pixel with this color_number as value.

typedef std::map<int, int> HistoMapT;
HistoMapT theMap;

For every color-number you encounter, you add one to the value under the key "color-number"
E.g. The first pixel has value 30:
You check if this number is already in the map. When it is, you increment its value. When its not, you insert it with a value of 1:

HistoMapT::iterator theIterator = theMap.find(color_number);
  int value = 1;
  if (theIterator != theMap.end() ) {
    value += theIterator.second;
  }
  theMap.insert(MAKEPAIR(color_number, value));

You see, std::map is quite helpful here, providing you with elegant and easy to read code.

Though I speak with the tongues of men and of angels, and have not money, I am become as a sounding brass, or a tinkling cymbal.
George Orwell, "Keep the Aspidistra Flying", Opening words

{

C^hris L^osinger9-Oct-07 3:13

9-Oct-07 3:13

jhwurmbach wrote:
You see, std::map is quite helpful here, providing you with elegant and easy to read code.

maybe, but it will be very very slow, compared to:

int * histogram = new int[256 * 256 * 256];
memset(histogram, 0, 256 * 256 * 256 * sizeof(int));

for (int x=0;x< w;x++) 
  for (int y=0;y< h;y++)
  {
    histogram[(int)RGB(pixel.Red, pixel.Green, pixel.Blue)]++;
    pixel++;
  }

jhwurmbach9-Oct-07 3:51

Re: Bitmap-Histogram using MFC [modified]

9-Oct-07 3:51

Chris Losinger wrote:
maybe, but it will be very very slow

May or may not. That probably depends on the pattern of usage and the picture.

You are newing 28MB in one piece here.
AND you are still limited to 8-bit per color.

Though I speak with the tongues of men and of angels, and have not money, I am become as a sounding brass, or a tinkling cymbal.
George Orwell, "Keep the Aspidistra Flying", Opening words

C^hris L^osinger9-Oct-07 4:14

9-Oct-07 4:14

jhwurmbach wrote:
May or may not.

you're calling how many functions per pixel?

vs. my single macro (which is a couple of bit shifts and logical ORs) and an array index.

jhwurmbach wrote:
You are newing 28MB in one piece here

64MB. but that's really not a big deal. your map will potentially require many times more than that.

you're right that your map will require less memory (though more memory allocations) in cases where images have few colors.

jhwurmbach wrote:
AND you are still limited to 8-bit per color.

true. it's an easy enough problem to fix. and your map will potentially suffer the same memory bloat.

-- modified at 10:34 Tuesday 9th October, 2007

ok... i'm bored, so i did some testing:

typedef std::map< int, int> HistoMapT ;

const int w = 1000;
const int h = 1000;

BYTE *p = = new BYTE[w * h * 3];

// init to a gradient (also ran init'd to 0s)
for (int x=0;x< w;x++)
{
	for (int y=0;y< h;y++)
	{
		p[x * 3 + y * w * 3 + 0] = x % 256;
		p[x * 3 + y * w * 3 + 1] = y % 256;
		p[x * 3 + y * w * 3 + 2] = (x + y) % 256;
	}
}


{
	CTimer c("Map"); // TRACE's time elapsed from construction to destruction
	BYTE * pix = p;
	HistoMapT theMap;

	for (int x=0;x< w;x++)
	{
		for (int y=0;y< h;y++)
		{
			int color_number = RGB(pix[0], pix[1], pix[2]);
			HistoMapT::iterator theIterator = theMap.find(color_number);
			int value = 1;
				
			if (theIterator != theMap.end() ) 
			{
				value += (*theIterator).second;
			}
			theMap.insert(std::pair< int, int>(color_number, value));

			pix+=3;
		}
	}
}

{	
	CTimer c("C");
	BYTE * pix = p;
	int *histo = new int[256 * 256 * 256];
	memset(histo, 0, 256 * 256 * 256 * 4);
	for (int x=0;x< w;x++)
	{
		for (int y=0;y< h;y++)
		{
			histo[RGB(pix[0], pix[1], pix[2])]++;
			pix+=3;
		}
	}

	delete [] histo;
}

delete [] p;

here are the results:

// source image init'd to gradients
Map 2.01s
C 0.16s

// source image init'd to all zero
Map 0.30s
C 0.08s

// changing the source init to
p[x * 3 + y * w * 3 + 0] = x % 256;
p[x * 3 + y * w * 3 + 1] = y % 256;
p[x * 3 + y * w * 3 + 2] = x / 256;

Map 11.25s
C 0.08s

-- modified at 10:42 Tuesday 9th October, 2007

-- modified at 10:54 Tuesday 9th October, 2007

jhwurmbach9-Oct-07 4:39

Re: Bitmap-Histogram using MFC [modified]

9-Oct-07 4:39

[memory block size]

Chris Losinger wrote:
64MB. [...]Your map will potentially require many times more than that.

Yes. Potentially. Very probably much less, by leaving out the unused color values.
But that sure depends on the picture you process.

[limit to 8bpp]

Chris Losinger wrote:
true. it's an easy enough problem to fix.

Sure. At the expense of much more obligate alocated memory in one piece.
And no, the map will behave much more conservative, as the saved memory by not storing the unused pixel values will be more prominent.

But you are right in that the access is slower. This might or might not be an issue.

Though I speak with the tongues of men and of angels, and have not money, I am become as a sounding brass, or a tinkling cymbal.
George Orwell, "Keep the Aspidistra Flying", Opening words

C^hris L^osinger9-Oct-07 4:44

9-Oct-07 4:44

i ran the timing tests (see the update above). the C version absolutely kills the map version. more than 3x faster for solid 0s, two orders of magnitude faster for one of the gradients.

-- modified at 10:55 Tuesday 9th October, 2007

-- modified at 10:58 Tuesday 9th October, 2007

jhwurmbach9-Oct-07 5:21

9-Oct-07 5:21

Chris Losinger wrote:
i ran the timing tests

Me too.
From your test-code I got 56msec vs. 85 msec for the map. Thats factor 1.5
I'm still unimpressed.

Though I speak with the tongues of men and of angels, and have not money, I am become as a sounding brass, or a tinkling cymbal.
George Orwell, "Keep the Aspidistra Flying", Opening words

C^hris L^osinger9-Oct-07 5:26

9-Oct-07 5:26

jhwurmbach wrote:
From your test-code I got 56msec vs. 85 msec for the map.

debug or release ?

jhwurmbach wrote:
Thats factor 1.5
I'm still unimpressed.

if only my customers were so ambivalent about performance!

jhwurmbach9-Oct-07 5:45

9-Oct-07 5:45

Chris Losinger wrote:
debug or release

VC++ 7.1. Release mode.
There is so much security built in in Debug, that there is no point comparing with raw C.

Chris Losinger wrote:
if only my customers were so ambivalent about performance!

They are for me. At least for the sub-second delays we are talking about here.

I have added the stdext::hash_map and now I get
map: 57 msec
hash_map: 24 msec
C-Array: 85 msec

Here is my code:

// _Template.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "Windows.h"
#include "MMSystem.h"
#pragma comment( lib, "winmm")

#include <tchar.h>
#include <iostream>
#include <map>
#include <hash_map>

#undef max
#undef min

static const int TARGET_RESOLUTION = 1;// 1-millisecond target resolution

int _tmain(int argc, _TCHAR* argv[])
{
	typedef std::map<int, int> HistoMapT ;
	typedef stdext::hash_map< int, int> HashHistoMapT;
	typedef std::pair<int, int> Int_PairT;

	const int w = 1000;
	const int h = 1000;

	//Init Multimedia timer
	TIMECAPS tc = {0};
	UINT     wTimerRes = 5; //default

	if( ::timeGetDevCaps( &tc, sizeof(TIMECAPS)) != TIMERR_NOERROR) 
	{
		std::cout << "Timer Error";
		return system("pause");
	}

	wTimerRes = std::min( std::max( tc.wPeriodMin, (UINT)TARGET_RESOLUTION), tc.wPeriodMax);
	::timeBeginPeriod( wTimerRes); 

	// init to a gradient (also ran init'd to 0s)
	BYTE *p = new BYTE[w * h * 3];
	for (int x=0; x< w;x++)
	{
		for (int y=0;y< h;y++)
		{
			p[x * 3 + y * w * 3 + 0] = w % 256;
			p[x * 3 + y * w * 3 + 1] = h % 256;
			p[x * 3 + y * w * 3 + 2] = (w + h) % 256;
		}
	}

	//Timing of std::map
	const UINT before1 = ::timeGetTime();
	{
		BYTE * pix = p;
		HistoMapT theMap;

		for (int x=0;x< w;x++)
		{
			for (int y=0;y< h;y++)
			{
				const int color_number = RGB(pix[0], pix[1], pix[2]);
				HistoMapT::iterator theIterator = theMap.find(color_number);
				int value = 1;
				if (theIterator != theMap.end() ) 
				{
					value += (*theIterator).second;
				}
				theMap.insert(Int_PairT(color_number, value));

				pix+=3;
			}
		}
	}
	const UINT after1 = ::timeGetTime();

	//Timing of stdext::hash_map
	const UINT before2 = ::timeGetTime();
	{
		BYTE * pix = p;
		HashHistoMapT theMap;

		for (int x=0;x< w;x++)
		{
			for (int y=0;y< h;y++)
			{
				const int color_number = RGB(pix[0], pix[1], pix[2]);
				HashHistoMapT::iterator theIterator = theMap.find(color_number);
				int value = 1;
				if (theIterator != theMap.end() ) 
				{
					value += (*theIterator).second;
				}
				theMap.insert(Int_PairT(color_number, value));

				pix+=3;
			}
		}
	}
	const UINT after2 = ::timeGetTime();

	//Timing of C-Array
	const UINT before3 = ::timeGetTime();
	{	
		BYTE * pix = p;
		int *histo = new int[256 * 256 * 256];
		memset(histo, 0, 256 * 256 * 256 * sizeof(histo[0]));
		for (int x=0;x< w;x++)
		{
			for (int y=0;y< h;y++)
			{
				histo[RGB(pix[0], pix[1], pix[2])]++;
				pix+=3;
			}
		}

		delete [] histo;
	}
	const UINT after3 = ::timeGetTime();

	delete [] p;

	::timeEndPeriod( wTimerRes);
	std::cout << "Elapsed timing map: " << (after1 - before1) << " msec." << std::endl;
	std::cout << "Elapsed timing hash_map: " << (after2 - before2) << " msec." << std::endl;
	std::cout << "Elapsed timing C-Code: " << (after3 - before3) << " msec." << std::endl;

	return system("pause");
}

Though I speak with the tongues of men and of angels, and have not money, I am become as a sounding brass, or a tinkling cymbal.
George Orwell, "Keep the Aspidistra Flying", Opening words

C^hris L^osinger9-Oct-07 5:52

9-Oct-07 5:52

there was a bug in my original test code.

you need to change this:

p[x * 3 + y * w * 3 + 0] = w % 256;
p[x * 3 + y * w * 3 + 1] = h % 256;
p[x * 3 + y * w * 3 + 2] = (w + h) % 256;

(w and h are constant so the image is a solid color)

to this:

p[x * 3 + y * w * 3 + 0] = x % 256;
p[x * 3 + y * w * 3 + 1] = y % 256;
p[x * 3 + y * w * 3 + 2] = (x + y) % 256;

Elapsed timing map: 1002 msec.
Elapsed timing hash_map: 1887 msec.
Elapsed timing C-Code: 120 msec.
Press any key to continue . . .

jhwurmbach9-Oct-07 5:55

9-Oct-07 5:55

Chris Losinger wrote:
Elapsed timing map: 1002 msec.
Elapsed timing hash_map: 1887 msec.
Elapsed timing C-Code: 120 msec.
Press any key to continue . . .

Here, its
Elapsed timing map: 455 msec.
Elapsed timing hash_map: 247 msec
Elapsed timing C-Code: 185 msec.

Are you still in Debug?

Though I speak with the tongues of men and of angels, and have not money, I am become as a sounding brass, or a tinkling cymbal.
George Orwell, "Keep the Aspidistra Flying", Opening words

C^hris L^osinger9-Oct-07 6:09

9-Oct-07 6:09

jhwurmbach wrote:
Are you still in Debug?

nope.

VS05, Release. optimized for "Maximize Speed"