Forum > Graphics

Fast way of comparing 2 bitmaps

<< < (2/5) > >>

Pi:

--- Quote from: furious programming on July 26, 2022, 12:37:01 am ---If you want to iterate very fast through bitmap pixels, just use TBitmap.ScanLine and compare pixel by pixel using pointers.

--- End quote ---
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).


--- Quote from: derek.john.evans on July 26, 2022, 03:40:30 am ---You could automate the imagemagick command line tools if you don't want to code it from scratch.

--- End quote ---
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:

--- Quote from: Pi on July 26, 2022, 01:36:06 pm ---Thanks. I'd read about scanline, but couldn't see any example code where it did something a bit like it.
--- End quote ---

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


--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---function CompareBitmaps(ABitmapA, ABitmapB: TBitmap): Integer;type  TBitmapPixel = record B, G, R: UInt8 end;  PBitmapPixel = ^TBitmapPixel;var  PixelA, PixelB: PBitmapPixel;  LineIndex, PixelIndex: Integer;begin  Result := 0;   for LineIndex := 0 to ABitmapA.Height - 1 do  begin    PixelA := ABitmapA.ScanLine[LineIndex];    PixelB := ABitmapB.ScanLine[LineIndex];     for PixelIndex := 0 to ABitmapA.Width - 1 do    begin      // compare pixel channels       PixelA += 1;      PixelB += 1;    end;  end;end;
Now, you can add any code to compare pixels in the place of the comment. For example:


--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---// count how many channels differResult += Ord(PixelA^.R <> PixelB^.R);Result += Ord(PixelA^.G <> PixelB^.G);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  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---// count how many pixels differResult += Ord((PixelA^.R <> PixelB^.R) or (PixelA^.G <> PixelB^.G) or (PixelA^.B <> PixelB^.B)); // or just in the form of conditionif (PixelA^.R <> PixelB^.R) or (PixelA^.G <> PixelB^.G) or (PixelA^.B <> PixelB^.B) then  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  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---function CompareBitmaps(ABitmapA, ABitmapB: TBitmap): Integer;var  PixelA, PixelB: PUInt32;  LineIndex, PixelIndex: Integer;begin  Result := 0;   for LineIndex := 0 to ABitmapA.Height - 1 do  begin    PixelA := ABitmapA.ScanLine[LineIndex];    PixelB := ABitmapB.ScanLine[LineIndex];     for PixelIndex := 0 to ABitmapA.Width - 1 do    begin      // count how many pixels differ      Result += Ord(PixelA^ <> PixelB^);       PixelA += 1;      PixelB += 1;    end;  end;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  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---function CompareBitmaps(ABitmapA, ABitmapB: TBitmap): Integer;var  PixelA, PixelB, PixelStop: PUInt32;  LineIndex: Integer;begin  Result := 0;   for LineIndex := 0 to ABitmapA.Height - 1 do  begin    PixelA    := ABitmapA.ScanLine[LineIndex];    PixelB    := ABitmapB.ScanLine[LineIndex];    PixelStop := PixelA + ABitmapA.Width;     while PixelA < PixelStop do    begin      // count how many pixels differ      Result += Ord(PixelA^ <> PixelB^);       PixelA += 1;      PixelB += 1;    end;  end;end;
Not tested but, I used this approach many times in the past.

Pi:

--- Quote from: furious programming on July 26, 2022, 03:47:14 pm ---Something like the following should be a valid pattern to iterate through bitmap pixels (both bitmaps must have the same dimensions):

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

--- Quote from: SymbolicFrank on July 26, 2022, 03:29:04 pm ---Load them as textures onto your GPU and write a shader that does the comparison.

--- End quote ---
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  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---// very rough + simplified colour distance (rgba to 8-bit).// useless since real camera data is 8-bit, but made because simulating the 32-bit// images was too slow in plain pascal.{$ifdef iacamarker}{$info iacamarker on in production code!}{$endif} const      splitsh6 :  array[0..31] of byte = (  $00,$04,$08,$0C,$01,$05,$09,$0d,                                            $02,$06,$0A,$0E,$03,$07,$0B,$0F,                                            $00,$04,$08,$0C,$01,$05,$09,$0d,                                            $02,$06,$0A,$0E,$03,$07,$0B,$0F);      permto8 :  array[0..31] of byte = (   $00,$00,$00,$00,$04,$00,$00,$00,                                            $01,$00,$00,$00,$05,$00,$00,$00,                                            $02,$00,$00,$00,$06,$00,$00,$00,                                            $03,$00,$00,$00,$07,$00,$00,$00);  // http://threadlocalmutex.com/?p=8// reduce Rgba andmask to 8bit for distance image, splitchannel variant// stackframe comes from VS code. (not related to the body of the code)procedure asmColourDistance(prgba1,prgba2 : pbyte;pdest8:pbyte;countinner,countouter: integer);assembler; nostackframe;// src= rcx src2, rdx, pdest8 r8 countinner=r9,countouter=stackasm  mov   rax, rsp        mov     QWORD PTR [rax+8], rbx        mov     QWORD PTR [rax+16], rdi        push    rbp        mov     rdi,[rsp+$30]         sub     rsp, 128                                // 00000080H        vmovaps XMMWORD PTR [rax-24], xmm6        vmovaps XMMWORD PTR [rax-40], xmm7        vmovaps XMMWORD PTR [rax-56], xmm8        vmovaps XMMWORD PTR [rax-72], xmm9        vmovaps XMMWORD PTR [rax-88], xmm10        vmovaps XMMWORD PTR [rax-104], xmm11        lea     rbp, QWORD PTR [rax-104]        and     rbp, -32                                // ffffffffffffffe0H         mov     rax,rdi        // pixels naar slagen.       shr     r9,5        mov      r11d,$7F7F7F7F       movd     xmm0,r11d       vpbroadcastd ymm11,xmm0        // in FPC code, loads of constants should now be 32-byte aligned (constmin)       vmovdqa  ymm9, [rip+permto8]       vmovdqa  ymm10,[rip+splitsh6] @louter:        mov     r11,r9align 16@linner:{$ifdef iacamarker}        mov ebx, 111          // Start marker bytes       db $64, $67, $90   // Start marker bytes{$endif}        //first load        vmovdqa  ymm0,[rcx]        vpsrlw  ymm0,ymm0,1        vpand   ymm0,ymm0,ymm11        vmovdqa  ymm1,[rdx]        vpsrlw  ymm1,ymm1,1        vpand   ymm1,ymm1,ymm11        vpsubsb ymm1,ymm1,ymm0        vpabsb  ymm0,ymm1        // arrange dwords together.   // absolute difference.        vpshufb ymm0,ymm0,ymm10        // gather qwords together.         vpermd  ymm4,ymm9,ymm0         // ymm4..7 are channels to store.        // ymm4 is already loaded.         // process first load        vpermq  ymm5,ymm4,1+2*4+3*16+0*64        vpermq  ymm6,ymm4,2+1*4+3*16+0*64        vpermq  ymm7,ymm4,3+1*4+2*16+0*64         // second load        vmovdqa  ymm0,[rcx+32]        vpsrlw   ymm0,ymm0,1        vpand    ymm0,ymm0,ymm11        vmovdqa  ymm1,[rdx+32]        vpsrlw   ymm1,ymm1,1        vpand    ymm1,ymm1,ymm11        vpsubsb  ymm1,ymm1,ymm0        vpabsb   ymm0,ymm1        // arrange dwords together.        vpshufb  ymm0,ymm0,ymm10        // gather qwords together.        vpermd   ymm2,ymm9,ymm0         //process second load.        vpermq   ymm1,ymm2,1+0*4+3*16+2*64        vpblendd ymm4,ymm4,ymm1,4+8        vpblendd ymm5,ymm5,ymm2,4+8        vpermq   ymm0,ymm2,3+2*4+1*16+0*64        vpblendd ymm6,ymm6,ymm0,4+8        vpermq   ymm2,ymm2,1+3*4+2*16+0*64        vpblendd ymm7,ymm7,ymm2,4+8         // third load        vmovdqa  ymm0,[rcx+64]        vpsrlw  ymm0,ymm0,1        vpand   ymm0,ymm0,ymm11        vmovdqa  ymm1,[rdx+64]        vpsrlw  ymm1,ymm1,1        vpand   ymm1,ymm1,ymm11        vpsubsb ymm1,ymm1,ymm0        vpabsb  ymm0,ymm1        // arrange dwords together.        vpshufb ymm0,ymm0,ymm10        // gather qwords together.        vpermd  ymm2,ymm9,ymm0         //process third load.        vpermq   ymm1,ymm2,1+2*4+0*16+3*64        vpblendd ymm4,ymm4,ymm1,16+32        vpermq   ymm0,ymm2,3+2*4+1*16+0*64        vpblendd ymm5,ymm5,ymm0,16+32        vpblendd ymm6,ymm6,ymm2,16+32        vpermq   ymm1,ymm2,2+1*4+3*16+0*64        vpblendd ymm7,ymm7,ymm1,16+32         // fourth load        vmovdqa  ymm0,[rcx+96]        vpsrlw  ymm0,ymm0,1        vpand   ymm0,ymm0,ymm11        vmovdqa  ymm1,[rdx+96]        vpsrlw  ymm1,ymm1,1        vpand   ymm1,ymm1,ymm11        vpsubsb ymm1,ymm1,ymm0        vpabsb  ymm0,ymm1        // arrange dwords together.        vpshufb ymm0,ymm0,ymm10        // gather qwords together.        vpermd  ymm2,ymm9,ymm0         //process fourth load.        vpermq   ymm1,ymm2,1+2*4+3*16+0*64        vpblendd ymm4,ymm4,ymm1,64+128        vpermq   ymm0,ymm2,3+2*4+0*16+1*64        vpblendd ymm5,ymm5,ymm0,64+128        vpermq   ymm3,ymm2,1+3*4+0*16+2*64        vpblendd ymm6,ymm6,ymm3,64+128        vpblendd ymm7,ymm7,ymm2,64+128         // we now have 3 regs with abs differences per colour channel. (ignoring channel a)        // we could do something more interesting, but for now, just add them        // together.        vpaddsb  ymm4,ymm4,ymm5        vpaddsb  ymm6,ymm6,ymm7        vpaddsb  ymm4,ymm4,ymm6        vmovdqa [r8],ymm4{$ifdef iacamarker}    mov ebx, 222          // End marker bytes    db $64, $67, $90   // End marker bytes{$endif}         add   rdx,128        add   rcx,128        add   r8,32        dec   r11        jne   @linner        dec   rax        jne   @louter        vzeroupper        lea     r11, QWORD PTR [rsp+128]        mov     rbx, QWORD PTR [r11+16]        mov     rdi, QWORD PTR [r11+24]        vmovaps xmm6, XMMWORD PTR [r11-16]        vmovaps xmm7, XMMWORD PTR [r11-32]        vmovaps xmm8, XMMWORD PTR [r11-48]        vmovaps xmm9, XMMWORD PTR [r11-64]        vmovaps xmm10, XMMWORD PTR [r11-80]        vmovaps xmm11, XMMWORD PTR [r11-96]        mov     rsp, r11        pop     rbp        ret     0end;                    

Navigation

[0] Message Index

[#] Next page

[*] Previous page

Go to full version