Recent

Author Topic: [SOLVED]Better/Fastest way to compare two images.  (Read 9773 times)

gafe

  • New Member
  • *
  • Posts: 22
[SOLVED]Better/Fastest way to compare two images.
« on: November 14, 2014, 07:38:17 pm »
Hi:

I'm doing a couple of apps to learn the language, one is a copy utility that can copy only changed parts of a file (i have questions about this, it's working, but will post another topic other day) and a remote control (like vnc) utility.
As a proof of concept, i have it working sending a tjpegimage saved in a tmemorystream over the network every second, and it works well...but the next step is getting the differences between two images to send only those.
I read the wiki, but i'm not sure what's the best/fast way to compare two images...TLazIntfImage? TBGRABitmap? Also, as i don't know anything about graphics processing, i have other question:
Will it be hard to change bit depth? Scale to lower resolutions?
If someone it's interested, i can make a zip of source code, but it's very early code, and the processing of TCP streams it's implemented badly (messages between client/server not of fixed lenght, for example)
Thanks all.
« Last Edit: November 16, 2014, 09:59:27 am by gafe »

derek.john.evans

  • Guest
Re: Better/Fastest way to compare two images.
« Reply #1 on: November 14, 2014, 07:50:03 pm »
I did something similar a few years back.  I XOR-ed each 32bit pixel with the previous frame. All the pixels that are the same will go black. Then compress to PNG or some TStream based compressor before sending.

gafe

  • New Member
  • *
  • Posts: 22
Re: Better/Fastest way to compare two images.
« Reply #2 on: November 14, 2014, 08:57:31 pm »
Thanks, that's smart. I'm looking and i think i can implement that with bitblt http://lazarus-ccr.sourceforge.net/docs/lcl/lclintf/bitblt.html and SRCINVERT "Fills the destination area with (Dst xor Src)"....

Will try it if i have time this weekend...thanks again...

User137

  • Hero Member
  • *****
  • Posts: 1791
    • Nxpascal home
Re: Better/Fastest way to compare two images.
« Reply #3 on: November 14, 2014, 09:10:13 pm »
You are talking about verifying data from corruption in network transfer. For this you don't need to specify image comparison, but raw byte array comparison which is much simpler. What you get from stream is just byte data in essence.

gafe

  • New Member
  • *
  • Posts: 22
Re: Better/Fastest way to compare two images.
« Reply #4 on: November 14, 2014, 09:32:28 pm »
You are talking about verifying data from corruption in network transfer. For this you don't need to specify image comparison, but raw byte array comparison which is much simpler. What you get from stream is just byte data in essence.
No, that's not what i mean (not a native english speaker)...i try to get the difference between two images (two bitmaps, for example) to repaint/redraw that difference only in another computer....

circular

  • Hero Member
  • *****
  • Posts: 3443
    • Personal webpage
Re: Better/Fastest way to compare two images.
« Reply #5 on: November 14, 2014, 11:14:16 pm »
Hi! You can use XOR as Derek suggested. Also if you have the bounds, you can send only this rectangle of data. Note that using the XOR method, you cannot use JPEG compression, because of the loss of quality, you can't know which pixels to keep and the losses may add with time.

With JPEG compression, you can determine the region that has changed as a matrix of 8x8 blocks, fill the rest with black, and send both the JPEG of that and the matrix of change. The size of the matrix will be small if you store in a bit array. One byte can be used to store 8 bits, so that represents 8x8x8 = 512 pixels.
Conscience is the debugger of the mind

gafe

  • New Member
  • *
  • Posts: 22
Re: Better/Fastest way to compare two images.
« Reply #6 on: November 14, 2014, 11:34:35 pm »
Thanks....which method do you think will be faster, as i have to iterate over all the pixels in a image? a Tlazintfimage? use TFastBitmapPixel ? raw memory? TBGRABitmap.ScanLine? ...there's a lot of examples in the wiki...don't know what to choose as i never did graphics programming....

Laksen

  • Hero Member
  • *****
  • Posts: 656
    • J-Software
Re: Better/Fastest way to compare two images.
« Reply #7 on: November 15, 2014, 12:45:19 am »
The fastest would be to use a block sized fuzzy hash based approach. Fuzzy has was developed for this purpose.

Here was the port I made a few years ago: http://j-software.dk/pasfuzzy.zip

It was faster than the C version back then, and could extremely easily be made thread safe unlike the C version :)

Eugene Loza

  • Hero Member
  • *****
  • Posts: 570
    • My "almost daily" development blog
Re: Better/Fastest way to compare two images.
« Reply #8 on: November 15, 2014, 09:02:08 am »
If its for expansion later, I'd better thought of 2d Fourier transform (FFT will be quicker) plus correlation analysis of both results to counter scaling and brightness. That would not just show pixel-by-pixel comparison, but would be able to detect scaled and processed images (e.g. with different JPEG compression quality / or two scanned images of the same document with different DPI), but not HUE/Saturation changes, rotation or other deformation, those should be handled separately.
Thou, it's definately not the fastest way :)
Lazarus 1.9 + FPC 3.1.1 Debian Jessie 64 bit.

My Free and Open Source games in Lazarus/FreePascal/CastleGameEngine:
https://decoherence.itch.io/
(and some ancient games in Turbo Pascal too)
Sources are here: https://github.com/eugeneloza?tab=repositories

gafe

  • New Member
  • *
  • Posts: 22
Re: Better/Fastest way to compare two images.
« Reply #9 on: November 15, 2014, 11:34:00 am »
I could try later the hash approach (but that means processing all the pixels anyway)... and the fourier transform seems overkill for this little project. As my time is limited (you know, children,family,work...) i will try starting with tlazintfimage getdatalinestart and grow from there to a bgrabitmap if i need it to process the image later (change bit depth, to grayscale,etc.)
Thanks for your suggestions...i think that's what keeps the fpc/lazarus environment working....

Laksen

  • Hero Member
  • *****
  • Posts: 656
    • J-Software
Re: Better/Fastest way to compare two images.
« Reply #10 on: November 15, 2014, 11:44:33 am »
You don't have to hash the pixels just the file directly. That assumes the compressions are roughly the same of course

gafe

  • New Member
  • *
  • Posts: 22
Re: Better/Fastest way to compare two images.
« Reply #11 on: November 15, 2014, 01:05:09 pm »
There's no file...right now is:
Bitmap of screen - tjpegimage - savetostream - send tmemorystream over network

circular

  • Hero Member
  • *****
  • Posts: 3443
    • Personal webpage
Re: Better/Fastest way to compare two images.
« Reply #12 on: November 16, 2014, 02:28:34 am »
Thanks....which method do you think will be faster, as i have to iterate over all the pixels in a image? a Tlazintfimage? use TFastBitmapPixel ? raw memory? TBGRABitmap.ScanLine? ...there's a lot of examples in the wiki...don't know what to choose as i never did graphics programming....
Basically the fastest way is to do direct access with TBGRABitmap or TLazIntfImage or TRawImage. I suppose using one or the other is not very significant compared to doing the actual processing and compression. Of course, if you want more functions, TBGRABitmap provides a lot. There is also Graphics32 that is similar but may be less portable. And also AggPas but may be more complicated to use.
Conscience is the debugger of the mind

gafe

  • New Member
  • *
  • Posts: 22
Re: Better/Fastest way to compare two images.
« Reply #13 on: November 16, 2014, 09:57:47 am »
Well, i did a quick test of comparing all pixels of two screencaptures (1 screencapture one second after): tlazintinfimage - 192 ms and tbgrabitmap ¡26 ms! . That is with 1920x1080 24bit in a old AMD Athlon(tm) II X2 245.
As there is a lot of difference this is how i done it:
- Tlazintinfimage:
Code: [Select]
    for py:=0 to SrcIntfImg.Height-1 do begin
      for px:=0 to SrcIntfImg.Width-1 do begin
        if (SrcIntfImg.Colors[px,py] <> TempIntfImg.Colors[px,py] ) then
        begin

        end
        else
        TempIntfImg.Colors[px,py]:=TColorToFPColor(clBlack);
        {TempIntfImg.Colors[px,py]:=SrcIntfImg.Colors[px,py] xor TempIntfImg.Colors[px,py]; }
      end;
    end;       

and tbgrabitmap (SrcIntfImg in this case is a TBGRABitmap, didn't change the name):
Code: [Select]
for n:=SrcIntfImg.NbPixels-1 downto 0 do
    begin
       if p^ = r^   then
       begin
         r^:=CSSBlack;
       end
       else
       begin

       end;
       inc(p);
       inc(r);
    end; 
                 
Also, TBGRABitmap gives more options to process the image....for me there's a winner  :)
Thank you all again.         
« Last Edit: November 16, 2014, 10:01:52 am by gafe »

BigChimp

  • Hero Member
  • *****
  • Posts: 5740
  • Add to the wiki - it's free ;)
    • FPCUp, PaperTiger scanning and other open source projects
Re: [SOLVED]Better/Fastest way to compare two images.
« Reply #14 on: November 16, 2014, 11:18:44 am »
Great - thanks for posting such a useful solution!
Want quicker answers to your questions? Read http://wiki.lazarus.freepascal.org/Lazarus_Faq#What_is_the_correct_way_to_ask_questions_in_the_forum.3F

Open source including papertiger OCR/PDF scanning:
https://bitbucket.org/reiniero

Lazarus trunk+FPC trunk x86, Windows x64 unless otherwise specified

 

TinyPortal © 2005-2018