Fast way of comparing 2 bitmaps

[Pi]

Do you know one of the fastest ways of comparing 2 bitmaps colour-wise?

eg. in this case I have 2 folders of bmp sequences from videos, and I want to go through the bitmaps in folder 1 looking for the closest bitmap to it in folder 2 (eg. the one that looks the same/nearly the same).
There's 642 bmps in folder 1 and 814 bmps in folder 2.

I'm currently loading each image into an image control (so 2 image controls on a form) and doing a for loop through the pixels and looking at the colour
eg. 

Code: Pascal  [Select][+][-]

1. col_1:=image1.Picture.Bitmap.Canvas.Pixels[x,y];

Then using getrvalue, getgvalue etc. to find the differences (using abs to make it a positive number) between the rgb values at each pixel position, totalling them up for an image comparison and storing the image nr with the lowest difference.

The images are 1080x1920 and it takes a long time to process every pixel (eg. if I compared every pixel of every image in folder 1 with every image in folder 2 I think it would take years to complete).
I changed it so it skips pixels (so in the for loop if it's not divisible by a certain number then go back to the loop. That will reduce precision but it still isn't fast enough with it just looking at every 100 pixels in the x & y.

Is there a faster way? Can someone please give me a hint how to do this using scanline if that will be a lot faster? Is using scanline the fastest way? It might be that comparing the grey-scale values might be good enough if comparing all the red, green and blue values will be too slow.

[winni]

Hi!

Install the BGRAbitmapPack available through the Online Package Manager.

This code creates copies of image1 and image2.
Then it compares the raw data of the two bitmaps and the difference is available in  dred,dgreen,dblue and dalpha.
There you have to put your code for the difference.

BGRAbitmap is not optimized for speed, but it is explicit faster than the TCanvas which is realy slow.

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.     dred,dgreen,dblue, dalpha : Integer;
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.      dred := p2^.red -p1^.red;
22.      dgreen := p2^.green -p1^.red;
23.      dblue := p2^.blue -p1^.blue;
24.      dalpha := p2^.alpha -p1^.alpha;
25.       .....
26.      inc(p1);
27.      inc(p2)
28.      end;
29.   bmp1.free;
30.   bmp2.free;
31. end;

Winni

[Pi]

Thanks a lot. I'm installing that now and will try that code.

edit: Thanks a lot. I've used and edited the code (after doing the online install and adding it to one of the package things) and it seems to be working now, faster than before. Thank you.

[furious programming]

If you want to iterate very fast through bitmap pixels, just use TBitmap.ScanLine and compare pixel by pixel using pointers.

[dje]

You could automate the imagemagick command line tools if you don't want to code it from scratch.

https://legacy.imagemagick.org/Usage/compare/#compare
https://imagemagick.org/script/compare.php
https://legacy.imagemagick.org/discourse-server/viewtopic.php?t=29587
https://legacy.imagemagick.org/discourse-server/viewtopic.php?t=30175
http://www.fmwconcepts.com/imagemagick/similar/index.php

edit: There is a ton of information if you google "find similar images using imagemagick"

It looks like imagemagick handles all kinds of variations in images, including size, color, images in images, etc.

http://www.imagemagick.org/discourse-server/viewtopic.php?t=32522

[Pi]

If you want to iterate very fast through bitmap pixels, just use TBitmap.ScanLine and compare pixel by pixel using pointers.

Thanks. I'd read about scanline, but couldn't see any example code where it did something a bit like it. Are there any links/examples where it does something like this please (where each pixel value is checked/accessed using pointers)?

The code given by winni worked a lot faster than my code, but when comparing each of 642 images with 814 still took quite a long time when working with 1080x1920 images. Though I thought in future I could render the images at half the width and height (just for the comparisons) and it should still be able to find the closest images and should be quite a bit faster (4x as fast maybe).

You could automate the imagemagick command line tools if you don't want to code it from scratch.

Thanks. I'm checking out those links too. The link to the script (http://www.fmwconcepts.com/imagemagick/similar/index.php), said I'd need to contact him if I needed it for commercial use though.

I'm not sure how complex it would be to do what I want in that with scripting since what I was using it for was finding the image (and it's frame nr) that was the closest match for a particular frame in the folder with about 600 images and then copying another file from another folder with that frame number to a new directory with the frame number that I was checking against. eg. a video of 814 frames had been rotoscoped, a new source video of 642 frames was given that seemed to only contain frames from the 814 frame video but with cuts/edits & retimings, so that copied the rotoscoped frames (png sequence with alpha in a different directory) based on the image frames of the 814 bmp sequence that were the closest match. So that helped having things work in functions in Lazarus to do that (eg. since you knew the frame/image nrs (of the frames you were checking and the ones you were checking against, the difference amount from each comparison as an integer, the frame nr of the closest match etc.).

[SymbolicFrank]

Load them as textures onto your GPU and write a shader that does the comparison.

[furious programming]

Thanks. I'd read about scanline, but couldn't see any example code where it did something a bit like it.

Something like the following should be a valid pattern to iterate through bitmap pixels (both bitmaps must have the same dimensions):

Code: Pascal  [Select][+][-]

1. function CompareBitmaps(ABitmapA, ABitmapB: TBitmap): Integer;
2. type
3.   TBitmapPixel = record B, G, R: UInt8 end;
4.   PBitmapPixel = ^TBitmapPixel;
5. var
6.   PixelA, PixelB: PBitmapPixel;
7.   LineIndex, PixelIndex: Integer;
8. begin
9.   Result := 0;
10.  
11.   for LineIndex := 0 to ABitmapA.Height - 1 do
12.   begin
13.     PixelA := ABitmapA.ScanLine[LineIndex];
14.     PixelB := ABitmapB.ScanLine[LineIndex];
15.  
16.     for PixelIndex := 0 to ABitmapA.Width - 1 do
17.     begin
18.       // compare pixel channels
19.  
20.       PixelA += 1;
21.       PixelB += 1;
22.     end;
23.   end;
24. end;

Now, you can add any code to compare pixels in the place of the comment. For example:

Code: Pascal  [Select][+][-]

1. // count how many channels differ
2. Result += Ord(PixelA^.R <> PixelB^.R);
3. Result += Ord(PixelA^.G <> PixelB^.G);
4. Result += Ord(PixelA^.B <> PixelB^.B);

So the result of the code above will be the sum of channels that differ. If you want to calculate how many pixels differ, you can increase the Result once per pixel:

Code: Pascal  [Select][+][-]

1. // count how many pixels differ
2. Result += Ord((PixelA^.R <> PixelB^.R) or (PixelA^.G <> PixelB^.G) or (PixelA^.B <> PixelB^.B));
3.  
4. // or just in the form of condition
5. if (PixelA^.R <> PixelB^.R) or (PixelA^.G <> PixelB^.G) or (PixelA^.B <> PixelB^.B) then
6.   Result += 1;

If you have 32-bit image (bitmap, PNG or any other with ScanLine), you can compare all pixel channels in one iteration of the loop. I can't remember but the 24-bit bitmap most likely also stores pixels in the internal buffer as 32-bit blocks, so you can also use integer-to-integer comparison. In such a case, the entire code will look like this:

Code: Pascal  [Select][+][-]

1. function CompareBitmaps(ABitmapA, ABitmapB: TBitmap): Integer;
2. var
3.   PixelA, PixelB: PUInt32;
4.   LineIndex, PixelIndex: Integer;
5. begin
6.   Result := 0;
7.  
8.   for LineIndex := 0 to ABitmapA.Height - 1 do
9.   begin
10.     PixelA := ABitmapA.ScanLine[LineIndex];
11.     PixelB := ABitmapB.ScanLine[LineIndex];
12.  
13.     for PixelIndex := 0 to ABitmapA.Width - 1 do
14.     begin
15.       // count how many pixels differ
16.       Result += Ord(PixelA^ <> PixelB^);
17.  
18.       PixelA += 1;
19.       PixelB += 1;
20.     end;
21.   end;
22. end;

Even faster way will be to use pointers to current and last pixel in the row, instead of using second nested for-loop (this is the fastest way of iteration):

Code: Pascal  [Select][+][-]

1. function CompareBitmaps(ABitmapA, ABitmapB: TBitmap): Integer;
2. var
3.   PixelA, PixelB, PixelStop: PUInt32;
4.   LineIndex: Integer;
5. begin
6.   Result := 0;
7.  
8.   for LineIndex := 0 to ABitmapA.Height - 1 do
9.   begin
10.     PixelA    := ABitmapA.ScanLine[LineIndex];
11.     PixelB    := ABitmapB.ScanLine[LineIndex];
12.     PixelStop := PixelA + ABitmapA.Width;
13.  
14.     while PixelA < PixelStop do
15.     begin
16.       // count how many pixels differ
17.       Result += Ord(PixelA^ <> PixelB^);
18.  
19.       PixelA += 1;
20.       PixelB += 1;
21.     end;
22.   end;
23. end;

Not tested but, I used this approach many times in the past.

[Pi]

Something like the following should be a valid pattern to iterate through bitmap pixels (both bitmaps must have the same dimensions):

Thanks a lot. I'll try it that way based on your code.

Load them as textures onto your GPU and write a shader that does the comparison.

Thanks. I'll look into that but I've never written shader so that way might be too complex.

[marcov]

Or just use AVX2. This calculates sum ( abs(r1-r2)+abs(b1-b2)+abs(g1-g2)) and stores it (saturated) in a one byte bitmap.

It was made as a quick demo to get a feel how much this could be optimized for system dimensioning purposes and has some limitations:

• topdown only
• No alignment or rest bytes usage, use image widths that are multiples of 32
• meant for win64, though changing for Linux 64-bit would be doable
• not heavily tested

Code: Pascal  [Select][+][-]

1. // very rough + simplified colour distance (rgba to 8-bit).
2. // useless since real camera data is 8-bit, but made because simulating the 32-bit
3. // images was too slow in plain pascal.
4. {$ifdef iacamarker}
5. {$info iacamarker on in production code!}
6. {$endif}
7.  
8. const
9.       splitsh6 :  array[0..31] of byte = (  $00,$04,$08,$0C,$01,$05,$09,$0d,
10.                                             $02,$06,$0A,$0E,$03,$07,$0B,$0F,
11.                                             $00,$04,$08,$0C,$01,$05,$09,$0d,
12.                                             $02,$06,$0A,$0E,$03,$07,$0B,$0F);
13.       permto8 :  array[0..31] of byte = (   $00,$00,$00,$00,$04,$00,$00,$00,
14.                                             $01,$00,$00,$00,$05,$00,$00,$00,
15.                                             $02,$00,$00,$00,$06,$00,$00,$00,
16.                                             $03,$00,$00,$00,$07,$00,$00,$00);
17.  
18.  
19. // http://threadlocalmutex.com/?p=8
20. // reduce Rgba andmask to 8bit for distance image, splitchannel variant
21. // stackframe comes from VS code. (not related to the body of the code)
22. procedure asmColourDistance(prgba1,prgba2 : pbyte;pdest8:pbyte;countinner,countouter: integer);assembler; nostackframe;
23. // src= rcx src2, rdx, pdest8 r8 countinner=r9,countouter=stack
24. asm
25.   mov   rax, rsp
26.         mov     QWORD PTR [rax+8], rbx
27.         mov     QWORD PTR [rax+16], rdi
28.         push    rbp
29.         mov     rdi,[rsp+$30]
30.  
31.         sub     rsp, 128                                // 00000080H
32.         vmovaps XMMWORD PTR [rax-24], xmm6
33.         vmovaps XMMWORD PTR [rax-40], xmm7
34.         vmovaps XMMWORD PTR [rax-56], xmm8
35.         vmovaps XMMWORD PTR [rax-72], xmm9
36.         vmovaps XMMWORD PTR [rax-88], xmm10
37.         vmovaps XMMWORD PTR [rax-104], xmm11
38.         lea     rbp, QWORD PTR [rax-104]
39.         and     rbp, -32                                // ffffffffffffffe0H
40.  
41.         mov     rax,rdi
42.  
43.        // pixels naar slagen.
44.        shr     r9,5
45.  
46.        mov      r11d,$7F7F7F7F
47.        movd     xmm0,r11d
48.        vpbroadcastd ymm11,xmm0
49.  
50.        // in FPC code, loads of constants should now be 32-byte aligned (constmin)
51.        vmovdqa  ymm9, [rip+permto8]
52.        vmovdqa  ymm10,[rip+splitsh6]
53.  
54. @louter:
55.         mov     r11,r9
56. align 16
57. @linner:
58. {$ifdef iacamarker}
59.         mov ebx, 111          // Start marker bytes
60.        db $64, $67, $90   // Start marker bytes
61. {$endif}
62.         //first load
63.         vmovdqa  ymm0,[rcx]
64.         vpsrlw  ymm0,ymm0,1
65.         vpand   ymm0,ymm0,ymm11
66.         vmovdqa  ymm1,[rdx]
67.         vpsrlw  ymm1,ymm1,1
68.         vpand   ymm1,ymm1,ymm11
69.         vpsubsb ymm1,ymm1,ymm0
70.         vpabsb  ymm0,ymm1
71.         // arrange dwords together.   // absolute difference.
72.         vpshufb ymm0,ymm0,ymm10
73.         // gather qwords together.
74.  
75.         vpermd  ymm4,ymm9,ymm0
76.  
77.         // ymm4..7 are channels to store.
78.         // ymm4 is already loaded.
79.  
80.         // process first load
81.         vpermq  ymm5,ymm4,1+2*4+3*16+0*64
82.         vpermq  ymm6,ymm4,2+1*4+3*16+0*64
83.         vpermq  ymm7,ymm4,3+1*4+2*16+0*64
84.  
85.         // second load
86.         vmovdqa  ymm0,[rcx+32]
87.         vpsrlw   ymm0,ymm0,1
88.         vpand    ymm0,ymm0,ymm11
89.         vmovdqa  ymm1,[rdx+32]
90.         vpsrlw   ymm1,ymm1,1
91.         vpand    ymm1,ymm1,ymm11
92.         vpsubsb  ymm1,ymm1,ymm0
93.         vpabsb   ymm0,ymm1
94.         // arrange dwords together.
95.         vpshufb  ymm0,ymm0,ymm10
96.         // gather qwords together.
97.         vpermd   ymm2,ymm9,ymm0
98.  
99.         //process second load.
100.         vpermq   ymm1,ymm2,1+0*4+3*16+2*64
101.         vpblendd ymm4,ymm4,ymm1,4+8
102.         vpblendd ymm5,ymm5,ymm2,4+8
103.         vpermq   ymm0,ymm2,3+2*4+1*16+0*64
104.         vpblendd ymm6,ymm6,ymm0,4+8
105.         vpermq   ymm2,ymm2,1+3*4+2*16+0*64
106.         vpblendd ymm7,ymm7,ymm2,4+8
107.  
108.         // third load
109.         vmovdqa  ymm0,[rcx+64]
110.         vpsrlw  ymm0,ymm0,1
111.         vpand   ymm0,ymm0,ymm11
112.         vmovdqa  ymm1,[rdx+64]
113.         vpsrlw  ymm1,ymm1,1
114.         vpand   ymm1,ymm1,ymm11
115.         vpsubsb ymm1,ymm1,ymm0
116.         vpabsb  ymm0,ymm1
117.         // arrange dwords together.
118.         vpshufb ymm0,ymm0,ymm10
119.         // gather qwords together.
120.         vpermd  ymm2,ymm9,ymm0
121.  
122.         //process third load.
123.         vpermq   ymm1,ymm2,1+2*4+0*16+3*64
124.         vpblendd ymm4,ymm4,ymm1,16+32
125.         vpermq   ymm0,ymm2,3+2*4+1*16+0*64
126.         vpblendd ymm5,ymm5,ymm0,16+32
127.         vpblendd ymm6,ymm6,ymm2,16+32
128.         vpermq   ymm1,ymm2,2+1*4+3*16+0*64
129.         vpblendd ymm7,ymm7,ymm1,16+32
130.  
131.         // fourth load
132.         vmovdqa  ymm0,[rcx+96]
133.         vpsrlw  ymm0,ymm0,1
134.         vpand   ymm0,ymm0,ymm11
135.         vmovdqa  ymm1,[rdx+96]
136.         vpsrlw  ymm1,ymm1,1
137.         vpand   ymm1,ymm1,ymm11
138.         vpsubsb ymm1,ymm1,ymm0
139.         vpabsb  ymm0,ymm1
140.         // arrange dwords together.
141.         vpshufb ymm0,ymm0,ymm10
142.         // gather qwords together.
143.         vpermd  ymm2,ymm9,ymm0
144.  
145.         //process fourth load.
146.         vpermq   ymm1,ymm2,1+2*4+3*16+0*64
147.         vpblendd ymm4,ymm4,ymm1,64+128
148.         vpermq   ymm0,ymm2,3+2*4+0*16+1*64
149.         vpblendd ymm5,ymm5,ymm0,64+128
150.         vpermq   ymm3,ymm2,1+3*4+0*16+2*64
151.         vpblendd ymm6,ymm6,ymm3,64+128
152.         vpblendd ymm7,ymm7,ymm2,64+128
153.  
154.         // we now have 3 regs with abs differences per colour channel. (ignoring channel a)
155.         // we could do something more interesting, but for now, just add them
156.         // together.
157.         vpaddsb  ymm4,ymm4,ymm5
158.         vpaddsb  ymm6,ymm6,ymm7
159.         vpaddsb  ymm4,ymm4,ymm6
160.         vmovdqa [r8],ymm4
161. {$ifdef iacamarker}
162.     mov ebx, 222          // End marker bytes
163.     db $64, $67, $90   // End marker bytes
164. {$endif}
165.  
166.         add   rdx,128
167.         add   rcx,128
168.         add   r8,32
169.         dec   r11
170.         jne   @linner
171.         dec   rax
172.         jne   @louter
173.         vzeroupper
174.         lea     r11, QWORD PTR [rsp+128]
175.         mov     rbx, QWORD PTR [r11+16]
176.         mov     rdi, QWORD PTR [r11+24]
177.         vmovaps xmm6, XMMWORD PTR [r11-16]
178.         vmovaps xmm7, XMMWORD PTR [r11-32]
179.         vmovaps xmm8, XMMWORD PTR [r11-48]
180.         vmovaps xmm9, XMMWORD PTR [r11-64]
181.         vmovaps xmm10, XMMWORD PTR [r11-80]
182.         vmovaps xmm11, XMMWORD PTR [r11-96]
183.         mov     rsp, r11
184.         pop     rbp
185.         ret     0
186. end;                  
187.  

[furious programming]

And of course it would be good to use all available CPU cores to do this job.

[Pi]

Or just use AVX2. This calculates sum ( abs(r1-r2)+abs(b1-b2)+abs(g1-g2)) and stores it (saturated) in a one byte bitmap...

Thanks a lot. I'll try that too. The original images I was checking were 1080 wide x 1920 high (so not 32 pixel multiple)  but I'll check it with 1920 width images.

[dseligo]

Code: Pascal  [Select][+][-]

1. PixelA += 1;

+=

Ehhhhhh

[Thausand]

Code: Pascal  [Select][+][-]

1. PixelA += 1;

+=

Ehhhhhh

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

[lainz]

And of course it would be good to use all available CPU cores to do this job.

An example of multiple thread filter is here:
https://github.com/bgrabitmap/multithreadedfilter/blob/master/umultithreadfilter.pas