High performance code to compare two images

[djjd47130]

Hi,

I'm trying to figure out the highest performing method of comparing two images with each other. This will be involved in streaming images basically as a video, I'm cutting each image into 100p x 100p pieces, and comparing all those pieces of the image with the same pieces of the previous image, so I only stream the pieces of the image which have changed since the last image was sent. I'm sure asm would be the best solution here, but it's too hard to find someone who knows asm. I'd also like to see how I may perform this comparison for all the pieces simultaneously. I'm currently using bmp to jpg compression already, so either a bmp or jpg solution would work, unless someone may have a better method to stream images. Obviously there's plenty of video streaming already, but my source is not video, but rather a non-stop supply of bmp images, the original format must remain as is. From there, whatever conversions are done depend on the best recommended image streaming practices, which is what I need someone's advice for.

(I'm still fairly new to streaming)

 

[djjd47130]

By the way Glenn, I'm not too familiar with data types, formats, or size of such. When you get the size of certain pixel formats, the pf8bit gets a size of 1. What about 4 bit? is that size .5? or is it also 1?

 

[Glenn9999]

I don't know if this stems from a difference in how D3 implements TMemoryStream compared to TD2006 (i'll find out), but whosrdaddy's code fails for me too.

var
  M1, M2: Integer;
  S1, S2: TMemoryStream;

 S1.Read(M1, 1);
 S2.Read(M2, 1);

 S1.Position:= S1.Position + 1;
 S2.Position:= S1.Position;

The S1.Read and S2.Read returns differing values into M1 & M2, which cause a failure. Why that is will take more research, but the main problem I noticed when I did my bugfix version is illustrated by this part of the manual for Read

Use Read to read the contents of the memory stream into a buffer, starting at the current position. Read will read up to Count bytes from the current position in Memory. If Count bytes extends beyond the end of the memory buffer, Read will only transfer the data up to the end of the associated memory buffer. Read returns the number of bytes actually transferred to Buffer, and advances the current position accordingly. If the return value is less than Count, it means that reading reached the end of the stream data.

So the code reads 1 byte into an integer, and then advances the current position 1 byte AFTER the byte that has been read (skipping it). So in effect, the last 2 lines of code I quoted are unnecessary and makes it check every other byte instead of every single byte.

Removing those last two lines and making the reads look like this:

S1.Read(M1, Sizeof(M1));

seems to fix this problem on my end. Of course there are possible issues to using signed integers types to compare random byte data, so I would use an array of bytes instead of the integers.

It is not possible for anyone to acknowledge truth when their salary depends on them not doing it.

 

[Glenn9999]

When you get the size of certain pixel formats, the pf8bit gets a size of 1. What about 4 bit? is that size .5? or is it also 1?

I just did that to try and catch the most common cases today, and didn't intend on supporting everything.

Anyhow, there are 8 bits in a byte, so there's the math. The ones I did are fine to multiply, but to be correct on the others you have to divide or if you remember arithmetic multiply by (1/value). For pf4bit that makes it 2 pixels per byte (1/2), for pf1bit it makes it 8 pixels per byte (1/8).

pf15bit is a wierd case and looking at TBitmap documentation was what made me first aware of it. I can't say I ever saw a bmp that used it. Even this graphics program I have doesn't support it. So I'd probably not bother there.

It is not possible for anyone to acknowledge truth when their salary depends on them not doing it.

 

[whosrdaddy]

, but whosrdaddy's code fails for me too.

I was just pointing out that there was a memoryleak, I never tested the code.
Thinking about this subject, wouldn't it be faster to check some pixels in a specific pattern (and not all pixels)?
And if the image stays the "same", force a refresh anyway after x time?.
I am thinking about an "X" pattern

something like this:
___
|XXX|
|XXX|
|XXX|

so X is a rectangular tile where you test only the x pixels
This means that pixels that change outside the X shape won't be detected, but most objects on screen have rectangular shape and should be detected (if the X tile is small enough). Off course if you make the tile to small, you need to test more pixels and lose more time.

Another option would be tiles and test in a checkered flag pattern.

Will try to make a protope app to see if this can beat full bitmap scanline comparison.

/Daddy






-----------------------------------------------------
What You See Is What You Get
Never underestimate tha powah of tha google!

 

[Glenn9999]

I was just pointing out that there was a memoryleak, I never tested the code.

That's fine, I didn't realize that you never tested it. I just thought I'd go ahead and point out the other problem I noticed with the code.

It is not possible for anyone to acknowledge truth when their salary depends on them not doing it.

 

[whosrdaddy]

lol

"lots of problems I see my young jedi!"

Cheers,
Daddy

-----------------------------------------------------
What You See Is What You Get
Never underestimate tha powah of tha google!

 

[Glenn9999]

Thinking about this subject, wouldn't it be faster to check some pixels in a specific pattern (and not all pixels)?

You could probably do certain rows vertically and not others and gain a little time (assuming it works). The problem with optimizing the code I posted as-is that it's already to the point of where you're talking only tenths of milliseconds difference in changes (I tried a couple of things) when you process a huge BMP file. The OP mentioned 100x100, so any differences are infinitesimal unless it is called millions of times.

FWIW, the code I posted profiled out to 99% of it's time in CompareMem, so that's where any real optimization has to take place.

It is not possible for anyone to acknowledge truth when their salary depends on them not doing it.

 

[djjd47130]

Yes Glenn I did think about that, and I've already implemented it, with a property 'SkipLines'.

Thank you all for your input, it helped me a bunch. As I said before, I'm still rather new to working with images, streams, and sockets. Prior to this project, most of what I knew was working with data via SQL.

 

[djjd47130]

Update: I have long since changed this code around, and now I have it scanning the lines of the original screenshot to begin with. I dumped the idea of the image blocks, and now I'm streaming the individual lines which are converted to compare in the first place. I'm using Bitmap.ScanLine and CompareMem and streaming new lines instead blocks. Now I'm on to the socket streaming part, but that's another story...

JD Solutions