Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » bitmap comparison

This thread is locked; no one can reply to it. rss feed Print
bitmap comparison
Neil Walker
Member #210
April 2000
avatar

Hello,
Is there a better way than this to compare two bitmaps than something like this, the two bitmaps are guaranteed to be the same size and depth, btw.

for(int y=0;y<Current->h;y++)
{
 for(int x=0;x<Current->w;x++)
 {        
  if(_getpixel(Current,x,y)!=_getpixel(Checking,x,y))
   return false;
 }
}

Neil.
MAME Cabinet Blog / AXL LIBRARY (a games framework) / AXL Documentation and Tutorial

wii:0356-1384-6687-2022, kart:3308-4806-6002. XBOX:chucklepie

Tobias Dammers
Member #2,604
August 2002
avatar

For a single comparison of arbitrary bitmaps, no.
There are some scenarios though that allow for certain optimizations.
1) If you need mip-maps of these bitmaps somewhere else in the code, and you have already calculated them, you can compare lower-resolution mipmap levels first (starting with the 1x1 degenerate case). This will cut your computing time for the more obvious reject cases, but it will increase computing time for the accept cases. In other words, the more similar the images are, the longer the comparison will take. So this would be beneficial only for cases where there are lots of fails and few passes.
2) If you are using some sort of pixel-perfect collision detection masks, you can first compare these. If the collision masks aren't equal, neither are the bitmaps.
3) In many cases, you can use direct access through the line pointers of the BITMAP struct. For lower color depths, this means that you can compare 2 or 4 pixels at once. This won't work with video or system bitmaps, though.
4) Store some sort of checksum along with the bitmap when loading / creating, and compare that first. A checksum comparison is very cheap once you have the checksum, but it may weed out a huge part of otherwise expensive comparisons. Again, this is only beneficial if the checksum generation process is less time-critical than the actual comparison. It's useless if you only ever compare the two bitmaps once in the program.

---
Me make music: Triofobie
---
"We need Tobias and his awesome trombone, too." - Johan Halmén

Evert
Member #794
November 2000
avatar

Quote:

In many cases, you can use direct access through the line pointers of the BITMAP struct. For lower color depths, this means that you can compare 2 or 4 pixels at once.

Best to use libc's memcmp in that case; that will probably compare memory areas in the most optimal way already.

Tobias Dammers
Member #2,604
August 2002
avatar

Good point.

---
Me make music: Triofobie
---
"We need Tobias and his awesome trombone, too." - Johan Halmén

Johan Halmén
Member #1,550
September 2001

But bitmaps might have some undefined bytes, like padding bytes in the end of a row, which might be different, even if the bitmaps are equal. memcmp() might make you believe they are different.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

Evert
Member #794
November 2000
avatar

Quote:

But bitmaps might have some undefined bytes, like padding bytes in the end of a row, which might be different, even if the bitmaps are equal. memcmp() might make you believe they are different.

Not if you tell it to only compare to the end of the line...

Neil Walker
Member #210
April 2000
avatar

I've wrote a program - don't know if there's one already, but mine's better ;) that takes in a bitmap file (e.g. a map of a game/screen/etc), extracts all the tiles, saves the unique ones out (resizing if you want it to) and generates a simple map file/array of the tile map. I'll post it to the depot later if anyone's interested. I just wanted to get it to go a bit faster, so I'll try the memcpy. At the minute a 16x16 tiled bitmap of a bitmap of 3000x400 pixels takes about 20 seconds, which isn't that bad considering it's not a real-time game or anything.

Neil.
MAME Cabinet Blog / AXL LIBRARY (a games framework) / AXL Documentation and Tutorial

wii:0356-1384-6687-2022, kart:3308-4806-6002. XBOX:chucklepie

Indeterminatus
Member #737
November 2000
avatar

If you don't want to compare two bitmaps for their exact identity, but say find out how similar they are, there are better approaches. Not intending to sound vague, I don't want to force the information on you, and I also don't want to write long posts risking noone's even interested.

edit: And I did well not to spit out all the drivel. After re-reading your last post I can see now it would have been pointless. Leaving the original post for archiving purposes, even though it isn't helpful in any way.

_______________________________
Indeterminatus. [Atomic Butcher]
si tacuisses, philosophus mansisses

Richard Phipps
Member #1,632
November 2001
avatar

Neil: I did this once as well. But the code is now lost in the mists of time.. :)

Maikol
Member #4,997
September 2004
avatar

Maybe this?

int  are_the_same(BITMAP *b1,BITMAP *b2)
{
  char *p1 = &b1->line[0][0], *p2 = &b2->line[0][0];

while (p1 < &b1->line[b1->w * b1->h * 24]) {
  if (*p1 == *p2)
    return 0;
  p1++;
  p2++;
  }
return 1;
}

Comparing byte by byte, p1 and p2 will go over their memory starting at [0,0], the begining; if the memory pointed to is different 0 is returned. If all matches, while loop ends and 1 is returned.

The while condition means: while p1 points into a zone of memory in b1 (of course b1 and b2 must have equal h and w, so no matter what bitmap you use), go on. The &b1->line[b1->w * b1->h * 24] is the latest position of the bitmap isn't it?

El sabio no dice todo lo que piensa, pero siempre piensa todo lo que dice
Aristóteles

Richard Phipps
Member #1,632
November 2001
avatar

Neil Walker
Member #210
April 2000
avatar

Quote:

Neil: I did this once as well. But the code is now lost in the mists of time..

Yeah, but mine works ;)

I'll try that sample out and see if it's any faster.

Neil.
MAME Cabinet Blog / AXL LIBRARY (a games framework) / AXL Documentation and Tutorial

wii:0356-1384-6687-2022, kart:3308-4806-6002. XBOX:chucklepie

Richard Phipps
Member #1,632
November 2001
avatar

Neil Walker
Member #210
April 2000
avatar

Quote:

Maybe this?

It doesn't work and it's no faster. I'll just leave it using the getpixel code :) thanks anyway.

It's not finished yet and just a windows binary, but
http://retrospec.sgn.net/users/nwalker/TileExtracter.zip

There are two maps in the zip, the config out of the box is for the last 10 or so rows of Marauder. Just change the offsets if you want to do the whole map.

If you do Rex (it's just two screens), change the tile size to 8 pixels and offsets to 0. All outputs go to the 'extract' directory. I plan on making it save to map/fmp format for Mappy as well. Delete the 'extract' directory before you run each as it won't do it for you.

Neil.
MAME Cabinet Blog / AXL LIBRARY (a games framework) / AXL Documentation and Tutorial

wii:0356-1384-6687-2022, kart:3308-4806-6002. XBOX:chucklepie

Go to: