Turning BMP Image To Min. Finite Automata

[ReVolt]

Hello I have problem with this... I don't know how to start with it, first thing that came up to my mind was "loop through an array of bits" in bitmap (monochromatic), but I can't get the bits.
So I've searched the internet and found lots of examples but they didn't helped me much.
Here's code I have:

#include <iostream>
#include <fstream>

using namespace std;

unsigned char* readBMP(char* filename)
{
    int i;
    FILE* f = fopen(filename, "rb");
    unsigned char info[54];
    fread(info, sizeof(unsigned char), 54, f); // read the 54-byte header

    // extract image height and width from header
    int s = *(int*)&info[2];
	int bisize = *(int*)&info[14];
	int width = *(int*)&info[18];
    int height = *(int*)&info[22];
    int size = 3 * width * height;
	
    unsigned char* data = new unsigned char[size]; // allocate 3 bytes per pixel
    fread(data, sizeof(unsigned char), size, f); // read the rest of the data at once	
	
	fclose(f);
    for(i = 0; i < size; i += 3)
    {
            unsigned char tmp = data[i];
            data[i] = data[i+2];
            data[i+2] = tmp;
    }

    return data;
}

int main(int argc, char **argv)
{

	unsigned char *data;
	if(argc == 2)
	{
	data = readBMP(argv[1]);
	cout << data;
	}
	else
		return -1;

	return 0;
}

No erros, it's working fine but I just can't get the bits of picture. I've tried to "cout" values form header (width, height) and they're ok, but I wonder how to get representation of picture itself. I thought that this code will give me something like array of 1 and 0.

I have to convert black and white (monochromatic) bmp image to min. finite automata.

I'll be very thankful for any advice
PS: sorry for my english it's while since i spoke or wrote something in english

[KRAkatau]

Well, if you have an RGB bmp image, and you know that it's only black and white pixels, then you can check if the pixel is black or white simply like that:

bool isBlack(unsigned char* data, int width, int height, int x, int y)
{
    return data[3 * (y * width + x)] == 0;
}

Basically, every unsigned char triplet in a bmp represent red, green, and blue for every pixel. Black pixels will have (0, 0, 0) and white ones (255, 255, 255).

However,I have no idea what you mean by converting an image to "min. finite automata".

[ReVolt]

thanks, the image will be monochomatic always so it will contain only back or white pixels

your post is very helpfull for me but can you tell me how is the char triplet stored in that array I have. It's just sequence of those numbers (something like 000255255255000....) or is it stored different way...

Don't waste your time with that automata thing I thing I fugured that out..

[KRAkatau]

Basically, yes, it's just a sequence of numbers as you've written.
Logically, though, this is not a simple sequence of unsigned chars - it is a 2D array of unsigned char triplets (although physically it's 1D) - that's why I wrote the formula data[3 * (y * width + x)] - it means that logically, we have a 2D array each line of which is width triplets long. So if you want to access line number y you should skip y * width * 3 elements. Similarly, you need to skip x * 3 elements to access pixel number x in line y. And this sums up to the formula above.

Hope this helps a bit :)

[ReVolt]

wow it helps a lot! thank you!
can you tell me just one more thing, if a have image let's say 60 pixels width and 40 pixels height it will be 2D array anyway or it will change...
and the x and y I'm passing to that function are the real coordinates of pixel?

[KRAkatau]

1) Yes, it will still be 2D.
2) Yes, these will be the actual pixel coordinates.

[ReVolt]

so i've tried to read bmp but i'm still doing something wrong:

#include <iostream>
#include <fstream>

using namespace std;

unsigned char* readBMP(char *filename, int *w, int *h)
{
    int i;
    FILE* f = fopen(filename, "rb");
    unsigned char info[54];
    fread(info, sizeof(unsigned char), 54, f); // read the 54-byte header

    // extract image height and width from header
	int b33 = *(int*)&info[30];
	int width = *(int*)&info[18];
    int height = *(int*)&info[22];
    int size = 3 * width * height;
	cout << b33 << endl;
	*w = width;
	*h = height;

    unsigned char* data = new unsigned char[size]; // allocate 3 bytes per pixel
    fread(data, sizeof(unsigned char), size, f); // read the rest of the data at once	
	
	fclose(f);
    for(i = 0; i < size; i += 3)
    {
            unsigned char tmp = data[i];
            data[i] = data[i+2];
            data[i+2] = tmp;
    }

    return data;
}


bool isBlack(unsigned char* data, int width, int height, int x, int y)
{
    return data[3 * (y * width + x)] == 0;
}

int main(int argc, char **argv)
{

	unsigned char *data;
	int w, h;
	int *bits;
	if(argc == 2)
	{
		data = readBMP(argv[1], &w, &h);
		bits = new int[w*h];
		for(int i = 1; i <= h; i++)
			for(int j = 0; j < w; j++)
			{
				if(isBlack(data, w, h, i, j))
					bits[i*j] = 0;
				else
					bits[i*j] = 1;
			}
			
		cout << w << " " << h << " " << endl;
		
		for(int i = 1; i <= h; i++)
		{
			for(int j = 0; j < w; j++)
			{
				cout << bits[i*j] << " ";
			}
			cout << endl;
		}
	}
	else
		return -1;	

	return 0;
}

and here's product of this program:
3 - compression method
5 5 - width and height
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 1

but png looks like this: http://web8.eu/bmp.png

and if a try to read bmp 60x10 program crashes...

[KRAkatau]

Ehm. So is it a bmp or png file? These are different image storage formats..

Loops in lines 52 and 63 are incorrect - they should look like this:
for(int i = 0; i < h; i++).
Probably you made it run from 1 to h is because your addressing of 2D arrays is incorrect. Instead of bits[i*j] it should be bits[i * w + j]. If you don't understand why is that - tell me I will either try to explain why or give you a link.

[ReVolt]

That png shows the bmp in picture viewer :)

hmm... I'm really confused, I just cant imagine in right, would you post the link please.

[KRAkatau]

The reason why you need to address it as shown is because of how the array is laid out in memory.

Assume you have a 2D array of size 4x3:

1 8 9 4
3 7 6 0
2 4 5 8

.
In memory it will be laid out like 1 8 9 4 3 7 6 0 2 4 5 8, and the array pointer will point to the memory location of the number 1.

So to find out what is the value of array in row 2 and column 1 you need to:
1) find out where in memory is the beginning of row 2
2) offset from the beginning of row 2 by 1.

1) As the array is laid out in row-major order ( http://en.wikipedia.org/wiki/Row-major_order ) - you need to skip 2 full rows from the beginning of the array - hence bits[i * w...]
2) Offset by 1 from the beginning of the row 2.
That's how the formula bits[i*w + j] is derived - it means - skip i full rows and j elements from the beginning of the array bits.

Hope this is more helpful than confusing :)

[ReVolt]

Thanks for your help, so if I have the image (5x5) the array should look like this: 000255255255000255255255000/first row/255255255000.....

[KRAkatau]

Yes, pretty much like that.

[ReVolt]

thanks, but I have to consider the offset at each row em I right?