Recent

Author Topic: Fast way of comparing 2 bitmaps  (Read 1850 times)

dje

  • Full Member
  • ***
  • Posts: 107
Re: Fast way of comparing 2 bitmaps
« Reply #15 on: July 27, 2022, 07:59:21 am »
findimagedupes looks interesting. Its a debian perl script that seems to automate ImageMagick.

Source code:
https://github.com/jhnc/findimagedupes
https://sources.debian.org/src/findimagedupes/2.18-7/findimagedupes/

Man Page:
https://manpages.ubuntu.com/manpages/bionic/man1/findimagedupes.1p.html

The algorithm is described as:
Quote
To calculate an image fingerprint:

 1. Read image.
 2. Resample to 160x160 to standardize size.
 3. Grayscale by reducing saturation.
 4. Blur a lot to get rid of noise.
 5. Normalize to spread out intensity as much as possible.
 6. Equalize to make image as contrasty as possible.
 7. Resample again down to 16x16.
 8. Reduce to 1bpp.
 9. The fingerprint is this raw image data.

To compare two images for similarity:

 1. Take fingerprint pairs and xor them.
 2. Compute the percentage of 1 bits in the result.
 3. If percentage exceeds threshold, declare files to be similar.

Maybe run a test on your images to see what happens. If the results are successful, then you have place to start from.
ie: What needs to be re-coded in Pascal to achieve the same results.


dje

  • Full Member
  • ***
  • Posts: 107
Re: Fast way of comparing 2 bitmaps
« Reply #16 on: July 27, 2022, 08:17:21 am »
Sorry, another piece of info: PascalMagick? Never used it, unsure if it works, but if it does, you should be able to convert the findimagedupes algorithm to Pascal.

https://wiki.freepascal.org/PascalMagick
https://sourceforge.net/projects/lazarus-ccr/files/PascalMagick/PascalMagick%200.4/
https://blog.dummzeuch.de/2019/10/22/pascalmagick-magickdistortimage-in-delphi/

Just some thoughts :-)

Pi

  • Jr. Member
  • **
  • Posts: 75
Re: Fast way of comparing 2 bitmaps
« Reply #17 on: July 27, 2022, 05:12:37 pm »
Sorry, another piece of info: PascalMagick? Never used it, unsure if it works, but if it does, you should be able to convert the findimagedupes algorithm to Pascal...
Thanks. I'm checking that too. I was thinking that finding the most similar image from a directory may be better for what I described above but I can also use a dupe finder (eg. for finding duplicate frames in a video and working out the real frame rate). In the "findimagedupes.1p" link they resample the images down to 16x16 pixels I think which I thought may be a bit low if you're comparing 1080p or higher video frame bmps. I'll check the code though thanks.
Lazarus version 0.9.30.4 + Lazarus 32 bit 1.2.6

dseligo

  • Hero Member
  • *****
  • Posts: 708
Re: Fast way of comparing 2 bitmaps
« Reply #18 on: July 28, 2022, 12:28:46 am »
Code: Pascal  [Select][+][-]
  1. PixelA += 1;

+=

Ehhhhhh
documentation read:  https://www.freepascal.org/docs-html/prog/progsu10.html

I know it can be used. But I made a comment because I don't like it.

circular

  • Hero Member
  • *****
  • Posts: 3845
    • Personal webpage
Re: Fast way of comparing 2 bitmaps
« Reply #19 on: July 30, 2022, 08:23:15 am »
Actually in BGRABitmap you have BGRADiff (or BGRAWordDiff to be more precise) function that you can apply to two pixels and give you the a color difference that is close to perceived difference.

Based on winni example:
Code: Pascal  [Select][+][-]
  1. uses ....,BGRABitmap, BGRABitmapTypes;
  2. .....
  3.  
  4. procedure TForm1.Button1Click(Sender: TObject);
  5. var bmp1,bmp2 : TBGRAbitmap;
  6.     p1,p2:PBGRAPixel;
  7.     i : integer;
  8.     diff: int64;
  9. begin
  10.   bmp1 := TBGRAbitmap.create(image1.Picture.Bitmap);
  11.   bmp2 := TBGRAbitmap.create(image2.Picture.Bitmap);
  12.   if bmp1.NbPixels <> bmp2.NbPixels then
  13.   begin
  14.     showMessage ('Different Dimensions!');
  15.     exit;
  16.   end;
  17.   p1 := bmp1.data;
  18.   p2 := bmp2.data;
  19.   for i := 0 to bmp1.NbPixels-1 do
  20.   begin
  21.     inc(diff, BGRADiff(p1^, p2^));
  22.     inc(p1);
  23.     inc(p2)
  24.   end;
  25.   // average difference of pixels
  26.   diff := round(diff / bmp1.NbPixels);
  27.   bmp1.free;
  28.   bmp2.free;
  29. end;

Maybe doing the sum of squares, divide by pixel count and then square root would be better statistically.
Conscience is the debugger of the mind

Thaddy

  • Hero Member
  • *****
  • Posts: 11910
Re: Fast way of comparing 2 bitmaps
« Reply #20 on: July 30, 2022, 11:01:14 am »
The simplest way is doing a hash on both. Does not need a secure hash.
But, given the outlay of your architecture I suspect you maybe want to detect if an image contains stenography compared to the original: in that case simply use a hash, elf-hash may suffice and is extremely fast (7 ops in assembler, 15 ops in pure pascal on Intel).
And if the hashes do not match you can further investigate pixel by pixel, which is of course much slower.
But that is a real life scenario.
« Last Edit: July 30, 2022, 11:09:06 am by Thaddy »
Black themes should be banned.

Pi

  • Jr. Member
  • **
  • Posts: 75
Re: Fast way of comparing 2 bitmaps
« Reply #21 on: July 31, 2022, 01:56:00 pm »
Actually in BGRABitmap you have BGRADiff (or BGRAWordDiff to be more precise) function that you can apply to two pixels and give you the a color difference that is close to perceived difference...
Thanks. I'll try that way too.
The simplest way is doing a hash on both. Does not need a secure hash.
But, given the outlay of your architecture I suspect you maybe want to detect if an image contains stenography compared to the original: in that case simply use a hash, elf-hash may suffice and is extremely fast (7 ops in assembler, 15 ops in pure pascal on Intel).
And if the hashes do not match you can further investigate pixel by pixel, which is of course much slower.
Thanks. The original reason for this in the original post was to save having to rotoscope 642 frames of video which would take a long time (because the source video which was 814 frames had already been rotoscoped and that 814 frame video seemed to have just been edited down with various cuts and re-timings (eg. speed ups) to get to the 642 frame video, so it should have just been a case of copying the equivalent rotoscoped frames from the 814 frame video to create the  642 frame video. But they probably wouldn't have matched exactly due to re-compression of the video. So if a hash looked for the exact match of the pixel values to see if it was the same frame it probably wouldn't work correctly in that case due to re-compression of the video making the rgb values in the exported frames slightly different.

I did think another way could be to look at either smaller resolution bmps versions of each frame first or only looking at every so many pixels of the bmps (in the original post I'd mentioned only checking every 100 pixels of the x & y but that it was still not working fast enough that way). eg. in theory you could look at a quarter size bitmaps first (or some other low enough resolution) to find the ones that look closest rgb-wise at that size, then just looking at the closest so many ones at half size, then the closest ones at full size. So that may be a faster way to find the closest frame rgb-wise than comparing just every full size pixel of every image (since at full res you'd only be checking the ones that were close at the lower resolutions).

There's probably quite a lot of uses for things like this though. Just finding duplicated frames in one video should also help with rotoscoping work since it should allow you to calculate if a 60 fps video really contains just a 24 or 30 source video or similar low fps video within a video encoded at higher fps (in which case you could just export it at the true frame rate and roto that, and save a lot of time rotoscoping. The original thing about copying rotoscoped matching frames (.bmps) might also work for much longer videos (especially if just the lower res versions are compared first, to speed it up), eg. if you needed to rotoscope a 30-60 minute talking head video, it might be that just a 5 minute section would be enough to get close enough mask shapes for the rest, and you could use these "closest frames" functions to copy the rotoscoped 5 minute vid frames to the closest frames of the 30-60 minute video, creating an accurate enough rotoscoped video up to 60 mins. Though maybe some AI might be a better way for that.
« Last Edit: July 31, 2022, 02:00:32 pm by Pi »
Lazarus version 0.9.30.4 + Lazarus 32 bit 1.2.6

 

TinyPortal © 2005-2018