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)

 

[Glenn9999]

I'm trying to figure out the highest performing method of comparing two images with each other.

If you're not already aware of it, look for something called the Sampling Profiler. It's the essential first step to look at performance of your code. Properly used, it will show you exactly where your code spends the majority of its time.

That being said, the best performing algorithm is always the one that is the simplest. Simplify and correct what you're doing and you'll get greater gains than anything in asm. In other words, a crappy algorithm written in asm is still a crappy algorithm, especially compared with a well-designed algorithm written in non-ASM. Make sure you got the best thing going that you can in Delphi before you consider trying to write it in ASM.

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 not sure this is the place you're going to find answers on "best recommended image streaming practices". You might try asking some people that have worked on open-source projects which do this, or look at the source of these projects.

Hope that helps.

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

 

[DelphiAaron]

found this on torry

...compare two images pixel by pixel?

procedure TForm1.Button1Click(Sender: TObject);
var
  b1, b2: TBitmap;
  c1, c2: PByte;
  x, y, i,
  different: Integer; // Counter for different pixels
begin
  b1 := Image1.Picture.Bitmap;
  b2 := Image2.Picture.Bitmap;
  Assert(b1.PixelFormat = b2.PixelFormat); // they have to be equal
  different := 0;
  for y := 0 to b1.Height - 1 do
  begin
    c1 := b1.Scanline[y];
    c2 := b2.Scanline[y];
    for x := 0 to b1.Width - 1 do
      for i := 0 to BytesPerPixel - 1 do // 1, to 4, dep. on pixelformat
      begin
        Inc(different, Integer(c1^ <> c2^));
        Inc(c1);
        Inc(c2);
      end;
  end;
end;

Aaron

 

[djjd47130]

Thanks for the tip, actually I've already come across that exact code. Let me explain more about what I'm doing. I'm making a remote desktop application which needs to stream real-time screenshots from one computer through a server to the other computer(s).

I have the system already working, but I'm trying to optimize the network performance by only sending the bits and pieces of the screen which have changed since the last time it was sent. Just the code for splitting the image into pieces alone takes about one second, which is not acceptable for this type of system.

I'm sure plenty of people have done systems like this before, and I'm trying to figure out the best way to do it. Any tips and pointers I could use would be greatly appreciated, any advice you can think of to make this perform nice.

 

[whosrdaddy]

No need for assembler...

All major implementations use a mirror display driver.
When the OS paints on the screen, it is picked up by the mirror driver and sent through the network.

more info here:

http://msdn.microsoft.com/en-us/library/ff568315.aspx

google will reveal some more resources on this subject...

/Daddy

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

 

[djjd47130]

I just thought I'd share that I have put together the best method for comparing two images. What I do is save them both to memory streams, then loop through the streams and compare bit by bit.

function BitmapsAreSame(Bitmap1, Bitmap2: TBitmap): Boolean;
var
  S1, S2: TMemoryStream;
  X: Integer;
begin
  if
    (Bitmap1.Width = Bitmap2.Width) and
    (Bitmap1.Height = Bitmap2.Height) and
    (Bitmap1.PixelFormat = Bitmap2.PixelFormat) then
  begin
    Result:= True;
    S1:= TMemoryStream.Create;
    S2:= TMemoryStream.Create;
    try
      Bitmap1.SaveToStream(S1);
      Bitmap2.SaveToStream(S2);
      if S1.Size <> S2.Size then
      begin
        Result:= False;
        Exit;
      end;     
      S1.Position:= 0;
      S2.Position:= 0;
      for X:= 1 to S1.Size do
      begin
        if S1.Read(X, 1) <> S2.Read(X, 1) then
        begin
          Result:= False;
          Exit;
        end;
      end;   
    finally
      S1.Free;
      S2.Free;
    end;
  end else begin
    Result:= False;
    Exit;
  end;
end;

 

[djjd47130]

And, this method of using streams is extremely fast. Comparing an 24bit bitmap 1920 x 1080 gives result in about half a second. Pixel by pixel will take at least 2 seconds.

 

[whosrdaddy]

djjd47130,

I see several problems in your last code sample...
do you see them?

/Daddy

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

 

[Glenn9999]

And, this method of using streams is extremely fast. Comparing an 24bit bitmap 1920 x 1080 gives result in about half a second. Pixel by pixel will take at least 2 seconds.

I found logic problems with your code, too, but I wanted to address more the performance aspects of your code. Actually, I found it pretty slow compared to the alternative. As I said, simplifying your code will always pay the biggest dividends. That said, VCL is usually to be avoided if you want the best performance, but you can usually get decent performance if you know enough about how the VCL works.

In your code, you copy data that are already in memory with the TBitmaps to TMemoryStream. This is unnecessary, and causes a major performance hit. Another example is to look at the code tayloredwarez posted - going pixel by pixel is unnecessary as well and causes a major performance hit.

Also, if you are concerned about performance, you want to test using the computer and not your stop watch. See faq102-7376 for examples.

The simplest code that does the job right is what you want.
That being said:
1) I did this code and tested it on all the cases I could think of (similar, different sizes, different bit depths, same image slightly changed) and it worked. There might be some attribute I forgot.
2) This code is literally instantaneous on the cases I tested it against (almost milliseconds). You would have to use the hi-res timer code to optimize this past what has already been done.
3) I included the test code I was using.

function timeGetTime: DWord; stdcall; external 'winmm.dll' name 'timeGetTime';

function MyBitmapsAreSame(Bitmap1, Bitmap2: TBitmap): Boolean;
var
  scanptr1, scanptr2: pointer;
  i: integer;
begin
  Result := false;
  if (Bitmap1.Width = Bitmap2.Width) and
     (Bitmap1.Height = Bitmap2.Height) and
     (Bitmap1.PixelFormat = Bitmap2.PixelFormat) then
      for i := 0 to (Bitmap1.Height-1) do
        begin
          scanptr1 := Bitmap1.ScanLine[i];
          scanptr2 := Bitmap2.ScanLine[i];
          Result := CompareMem(scanptr1, scanptr2, Bitmap1.Width);
          if Result = false then break;
        end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  a, b: TBitmap;
  Time: DWord;
  Bitmap_Similar: Boolean;
begin
  a := TBitmap.Create;
  b := TBitmap.Create;
  try
    A.LoadFromFile('TEST1.BMP');
    B.LoadFromFile('TEST4.BMP');
    Time := timeGetTime;
    Bitmap_Similar := MyBitmapsAreSame(a, b);
    Time := timeGetTime - Time;
    if Bitmap_Similar then
      ShowMessage('Bitmaps are similar.' + #13#10 + 'Completed in ' + IntToStr(Time) + ' ms.')
    else
      ShowMessage('Bitmaps are not similar.' + #13#10 + 'Completed in ' + IntToStr(Time) + ' ms.');
  finally
    A.Free;
    b.Free;
  end;
end;

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

 

[djjd47130]

Yes actually I realized that right after I posted it.. I pulled the code from the wrong unit, that was an older unfinished version. Here's the latest version:

function BitmapsAreSame(Bitmap1, Bitmap2: TBitmap): Boolean;
var
  S1, S2: TMemoryStream;
  M1, M2: Integer;
  X: Integer;
begin        
  Result:= True;
  if  (Bitmap1.Width        <> Bitmap2.Width)       or
      (Bitmap1.Height       <> Bitmap2.Height)      or
      (Bitmap1.PixelFormat  <> Bitmap2.PixelFormat) then
  begin
    Result:= False;
    Exit;
  end;
  S1:= TMemoryStream.Create;
  S2:= TMemoryStream.Create;
  try
    Bitmap1.SaveToStream(S1);
    Bitmap2.SaveToStream(S2);
    if S1.Size <> S2.Size then
    begin
      Result:= False;
      Exit;
    end;     
    S1.Position:= 0;
    S2.Position:= 0;
    for X:= 1 to S1.Size do
    begin
      S1.Read(M1, 1);
      S2.Read(M2, 1);
      if M1 <> M2 then
      begin
        Result:= False;
        Exit;
      end;
      S1.Position:= S1.Position + 1;
      S2.Position:= S1.Position;
    end;   
  finally
    S1.Free;
    S2.Free;
  end;
end;

 

[DjangMan]

Should:

for X:= 1 to S1.Size do

be

for X:= 0 to S1.Size-1 do

?

 

[DjangMan]

Oops - clicked send too soon.

You have that code in the try..finally so any error (which I'm thinking there should be) won't appear.

Actually - it probably does work - but for the wrong reason. If you've gotten to that point then the images are the same so it doesn't matter. But you might try adjusting the last pixel of an image to see for sure.

 

[djjd47130]

I also clocked that at 18ms for a 1920x1080 24bit bitmap

That should translate to about 2-3 ms when it's broken into a 50x50p block. This remote desktop I'm building will work like this:
- Take screenshot and assign to bmp
- Load screenshot bmp into image splitter
- Loop through X and Y of image splitter bmp
-- Acquire Row X and Column Y sections of screenshot bmp
-- Compare section to the last sent section (in previous screenshot)
-- If the images are different, then
--- Convert bmp to jpg with compression
--- Load jpg into memory stream
--- Send server notification of new screenshot (provide x and y of screen)
--- Send server memory stream

 

[Glenn9999]

Yes actually I realized that right after I posted it..

Try again. I tried the newest version in the thread on the same bitmap and it came back as "not identical".

And speaking of that, I'll try again too. I posted mine and had to go somewhere and realized when I went out the door that I forgot to multiply by the pixel size.

Sooo...

function GetPixelSize(informat: TPixelFormat): Integer;
  // returns proper byte size for input
  begin
    case informat of
      pf8bit: Result := 1;
      pf16bit: Result := 2;
      pf24bit: Result := 3;
      pf32bit: Result := 4;
    else
      Result := 0;
    end;
  end;

function MyBitmapsAreSame(Bitmap1, Bitmap2: TBitmap): Boolean;
var
  scanptr1, scanptr2: pointer;
  i: integer;
  PixelSize: byte;
begin
  Result := false;
  if (Bitmap1.Width = Bitmap2.Width) and
     (Bitmap1.Height = Bitmap2.Height) and
     (Bitmap1.PixelFormat = Bitmap2.PixelFormat) then
    begin
      PixelSize := GetPixelSize(Bitmap1.PixelFormat);
      for i := 0 to (Bitmap1.Height-1) do
        begin
          scanptr1 := Bitmap1.ScanLine[i];
          scanptr2 := Bitmap2.ScanLine[i];
          Result := CompareMem(scanptr1, scanptr2, Bitmap1.Width*PixelSize);
          if Result = false then break;
        end;
    end;
end;

FWIW, yours runs on my computer in 47 ms and mine runs 16 ms on a 3200x2400 24bit bmp. a 50x50 compare should be instantaneous.

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

 

[whosrdaddy]

djjd47130,

I still see problems in your code...
<hint>memory leak </hint>

/Daddy

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

 

[Glenn9999]

I still see problems in your code...

FWIW, I fixed the code and tested it to see how it would run. The corrected version is about 10x slower. I didn't really think about it at the time I posted something above, but the OP's code is pixel-by-pixel as well.

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

 

[whosrdaddy]

Should:

for X:= 1 to S1.Size do

be

for X:= 0 to S1.Size-1 do

?

that won't make any difference as he's not using X...

/Daddy



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

 

[whosrdaddy]

Since no one sees the problem with djjd47130's code I will go ahead and post the "memory leak" free code.
The main problems are the "Exit" parts after the creation of the 2 TMemoryStreams. You can't just create an object and say: "oh well I don't have to do anything here, see ya, you do the cleanup for me?".

here is my (nonleaking) version.

function BitmapsAreSame(Bitmap1, Bitmap2: TBitmap): Boolean;
var
  S1, S2: TMemoryStream;
  M1, M2: Integer;
  X: Integer;
begin
  Result:= True;
  Result := not((Bitmap1.Width        <> Bitmap2.Width)   or
                (Bitmap1.Height       <> Bitmap2.Height)  or
                (Bitmap1.PixelFormat  <> Bitmap2.PixelFormat));
  if Result then
   begin
    S1:= TMemoryStream.Create;
    S2:= TMemoryStream.Create;
    try
      Bitmap1.SaveToStream(S1);
      Bitmap2.SaveToStream(S2);
      if S1.Size = S2.Size then
      begin
        S1.Position:= 0;
        S2.Position:= 0;
        for X:= 1 to S1.Size do
        begin
          S1.Read(M1, 1);
          S2.Read(M2, 1);
          if M1 <> M2 then
          begin
            Result:= False;
            Exit;
          end;
          S1.Position:= S1.Position + 1;
          S2.Position:= S1.Position;
        end;
      end;
    finally
      S1.Free;
      S2.Free;
    end;
   end;
end;

that being said, I prefer Glenn's code as he is doing scanline comparison which is much faster.
Tile comparison will be indeed much faster (as glenn suggested)...

/Daddy

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

 

[whosrdaddy]

mmm, forgot the third "Exit;".

replacing it with break; will do...

/Daddy

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

 

[djjd47130]

Thank you all.

I see Glenn's code is in fact much faster, in as little as 0 ms for the same large images.