Bilder schnell miteinander vergleichen

[Phantom1]

Ich hab meinen Code jetzt nochmal optimiert, dieser ist jetzt auch bei Bildern die keine oder nur wenige Unterschiede haben schneller:

Delphi-Quellcode:

function CompareImages(Bitmap1, Bitmap2: TBitmap): LongWord;
var
  xy: integer;
  P1, P2: PRGBTriple;
begin
  Result:=0;
  Bitmap1.PixelFormat:=pf24bit;
  Bitmap2.PixelFormat:=pf24bit;
  P1:=Bitmap1.ScanLine[Bitmap1.Height-1];
  P2:=Bitmap2.ScanLine[Bitmap2.Height-1];
  if not CompareMem(P1, P2, Bitmap1.Width*Bitmap1.Height*3) then
    for xy:=1 to Bitmap1.Height*Bitmap1.Width do begin
      if (P1^.rgbtRed<>P2^.rgbtRed) or (PWord(P1)^<>PWord(P2)^) then
        Inc(Result);
      Inc(P1);
      Inc(P2);
    end;
end;

Gleiche Bilder vergleichen (500 durchläufe):
Flips Algo: 1,0 sek
mein Algo: 0,8 sek

zwei komplett unterschiedliche Bilder vergleichen (500 Durchläufe):
Flips Algo: 3,7 sek
mein Algo: 1,0 sek

Noch schneller dürfte es warscheinlich nur mit Assembler gehen ^^

EDIT: kleine Änderung am Code

mfg

[Vjay]

Zitat:

(P1^.rgbtRed<>P2^.rgbtRed) or
(P1^.rgbtGreen<>P2^.rgbtGreen) or
(P1^.rgbtBlue<>P2^.rgbtBlue)

Wäre es nicht besser die drei Bytes auf einmal zu prüfen?

[Phantom1]

Zitat:

Zitat von Vjay

Zitat:

(P1^.rgbtRed<>P2^.rgbtRed) or
(P1^.rgbtGreen<>P2^.rgbtGreen) or
(P1^.rgbtBlue<>P2^.rgbtBlue)

Wäre es nicht besser die drei Bytes auf einmal zu prüfen?

Hast du eine bessere möglichkeit gefunden?

EDIT: hab eben doch noch eine bessere möglichkeit gefunden:

Delphi-Quellcode:

if (P1^.rgbtRed<>P2^.rgbtRed) or (PWord(P1)^<>PWord(P2)^) then

Dadurch wird der Vergleich nochmals um etwa 0,2 sek schneller. Hab den Code oben geändert.

mfg

[EDatabaseError]

So...
ich hab jetzt mal beide codes von oben getestet.

Resultat:

das Testbild ist im Anhang

beim 1:
AV auch wenn das Bild gleich ist

beim 2:
Bei gleichem Bild OK
Bei unterschiedlichen Bildern AV


:drunken:

Mfg
Tobi

[Phantom1]

Zitat:

Zitat von EDatabaseError

So...
ich hab jetzt mal beide codes von oben getestet.

Hast du auch mein Code getestet? Bei mir gehts jedenfalls ohne Probleme mit dem pi.bmp (egal ob die unterschiedlich sind oder nich).

mfg

[negaH]

Delphi-Quellcode:

(P1^.rgbtRed<>P2^.rgbtRed) or
(P1^.rgbtGreen<>P2^.rgbtGreen) or
(P1^.rgbtBlue<>P2^.rgbtBlue)

Delphi-Quellcode:

if (P1.R xor p2.R) or (P1.G xor P2.G) or (P1.B xor P2.B) <> 0 then

sollte schneller sein. Dein obiger Source wird durch den Compiler in 3 Compare (quasi Subtrationen) Operationen mit jeweils einem Branch/bedingten Sprung umgesetzt. Mein nachfolgender Code verknüpft alle Werte erstmal mit simplen boolschen Operationen und wenn das Gesamtresultat <> 0 ist wird mit einem begingten Sprung ausgewertet. Bedingte Spünge sind ein Graus für die Branchprediction Unit der CPU und führen meistens zum Invalidieren des Instructioncache. Zudem können die 3 XOR + 3 OR Operationen quasi in parallel durch den Instructiondecoder ausgewertet werden, in mehreren Pipes der CPU. Erst am Ende wird ein bedingter Sprung ausgeführt der in letzten Falle nur überprüft ob die vorhergehenden Operationen das Zero Flag Z gesetzt/gelöscht haben.

Noch schneller wenn man AND masked und nicht in 24Bit RGB sondern als 32Bit zugreift

Delphi-Quellcode:

if P1 xor P2 and $FFFFFF <> 0 then

Zur Behauptung "schnellster Code" kann ich nur sagen "alles relativ" und wenn man "misst dann misst man nur Mist".

Ich gebe dir 2 Bitmaps mit 16Bit Farbauflösung. Du vergleichst sie aber im 24Bit Modus was dazu führt das die Delphi Bitmap VCL diese 16Bit Aufkösung erstmal in 24Bit umrechnen muß. Das erfolgt übers Windows API. Diese Operation hast du in deiner Meßschleife überhaupt nicht berücksichtigt. Ergo: Wenn überhaupt ist dein Code relativ optimiert ausschließlich bezogen auf Windows Bitmaps in 24 Bit Farbtiefe. Problem? es gibt unzählige Formate für Bitmaps und noch viel mehr in anderen Formaten. Die Umwandlung in das benötigte 24Bit Bitmap Format ist aber gerade der Punkt der die meiste Zeit frisst.

Gruß Hagen

[Phantom1]

Zitat:

Zitat von negaH

Delphi-Quellcode:

(P1^.rgbtRed<>P2^.rgbtRed) or
(P1^.rgbtGreen<>P2^.rgbtGreen) or
(P1^.rgbtBlue<>P2^.rgbtBlue)

Delphi-Quellcode:

if (P1.R xor p2.R) or (P1.G xor P2.G) or (P1.B xor P2.B) <> 0 then

sollte schneller sein.

Die xor variante ist bei mir deutlich langsamer (ca 50%), habs mit Delphi7 und Delphi2006 getestet.

Zitat:

Zitat von negaH

Noch schneller wenn man AND masked und nicht in 24Bit RGB sondern als 32Bit zugreift

Mein erst geposteter Code war ja für 32bit Bmps, in diesem Fall war aber 24bit schneller. Warum das so ist weiß ich allerdings nich.

zwischen

Delphi-Quellcode:

if P1^<>P2^ then

und

Delphi-Quellcode:

if P1^ xor P2^ and $FFFFFF <> 0 then

konnte ich bei 32bit auch kein unterschied feststellen, waren beide gleichschnell.

mfg

[negaH]

1.) hast du dir den durch den Compiler erzeugten Code in Assembler angeschaut ?
2.) wie hast du was gemessen ?
3.) der von mir vorfeschlagene 32Bit Zugriff bezog sich auf 24Bit Bitmapdaten, deshalb auch die AND Maske mit $00FFFFFF.


Gruß Hagen

sorry

Zitat:

habs mit Delphi7 und Delphi2006

sehe ich erst jetzt. Vergiß Delphi6,7,D2006 wenn es um Optimierungen geht. In diesen Versionen basiert der Borland Compiler auf einem Intel Produkt. Im Vergleich zu Delphi5 ist der erzeugte Code bis zu 30% langsammer als der vom Original Borland Compiler der bis zum Delphi5 benutzt wurde. Frage dich mal warum ab D7 in deren Licence.txt oä. es strickt verboten wurde Performancevergleiche mit älteren Versionen zu veröffentlichen !!

Ich persönlich hatte schon Codestücken die mehr als 200% langsammer waren als mit D5 compiliert. Das ist auch ein Grund warum ich privat im Hobby immer noch am liebsten mit Delphi 5 arbeite. Die nachfolgenden Versionen bieten, mal abgesehen von Gimmeck-VCLs wie TXPManifest etc.pp. nichts wirklich neues im Vergleich zum Delphi5. Nebenbei bemerkt ist der erzeugte Code mit D5 zusätzlich noch kompakter !

[Phantom1]

Zitat:

Zitat von negaH

1.) hast du dir den durch den Compiler erzeugten Code in Assembler angeschaut ?

habe ich nicht

Zitat:

Zitat von negaH

2.) wie hast du was gemessen ?

so hier:

Delphi-Quellcode:

procedure TForm2.Button1Click(Sender: TObject);
var
  start, stop: Int64;
  i: Integer;
begin
  start:=GetTickCount;

  for i:=1 to 500 do
    CompareImages(Bitmap1, Bitmap2);

  stop:=GetTickCount;
  Caption:=IntToStr(stop-start);
end;

Mit dem QueryPerformanceCounter ginge es zwar noch etwas genauer, aber das fällt bei den großen Unterschieden nicht ins gewicht.

Jetzt zu den Messungen:

Delphi-Quellcode:

(P1^.rgbtRed<>P2^.rgbtRed) or
(P1^.rgbtGreen<>P2^.rgbtGreen) or
(P1^.rgbtBlue<>P2^.rgbtBlue)

ca 1100 ms

Delphi-Quellcode:

(P1^.rgbtRed xor p2^.rgbtRed) or (P1^.rgbtGreen xor P2^.rgbtGreen) or (P1^.rgbtBlue xor P2^.rgbtBlue) <> 0

ca 1450 ms

Hab natürlich mehrere Messungen vorgenommen und den Mittelwert genommen.

Zitat:

Zitat von negaH

3.) der von mir vorfeschlagene 32Bit Zugriff bezog sich auf 24Bit Bitmapdaten, deshalb auch die AND Maske mit $00FFFFFF.

Achso, das ergibt natürlich mehr sinn, hatte mich schon gewundert.

Delphi-Quellcode:

(PInteger(P1)^ xor PInteger(P2)^) and $00FFFFFF <> 0

Bei 24bit ergab meine Messung hier 1100 ms

Zitat:

Zitat von negaH

sehe ich erst jetzt. Vergiß Delphi6,7,D2006 wenn es um Optimierungen geht. In diesen Versionen basiert der Borland Compiler auf einem Intel Produkt. Im Vergleich zu Delphi5 ist der erzeugte Code bis zu 30% langsammer als der vom Original Borland Compiler der bis zum Delphi5 benutzt wurde. Frage dich mal warum ab D7 in deren Licence.txt oä. es strickt verboten wurde Performancevergleiche mit älteren Versionen zu veröffentlichen !!

Sehr interessant, das wusste ich noch nicht, leider hab ich kein Delphi5.

mfg

[Hawkeye219]

and bindet stärker als xor, man sollte also hier Klammern setzen:

Delphi-Quellcode:

(PInteger(P1)^ xor PInteger(P2)^) and $00FFFFFF <> 0

Gruß Hawkeye