Bilder schnell miteinander vergleichen

[Flips]

Hi.

Folgender Code ermöglicht das schnelle Vergleichen zweier Bitmaps und gibt, falls sie nicht identisch sind, ihre Unterschiede in Pixel aus. Der Algorithmus war ein Teil eines Jugend forscht Projektes und hat sich als schnellster unter vielen erwiesen. Ein Bild von 1024*768 wird auf einem AMD Athlon XP 2600+ @ 1,9 GHz in 4,4ms verglichen.

Delphi-Quellcode:

type
  PRGBTripleArray = ^TRGBTripleArray;
  TRGBTripleArray = array [0..50000000] of TRGBTriple;

function CompareImages(Image1,Image2:TBitmap):Int64;
var x,y:integer;
    P1,P2:PRGBTripleArray;
    summe1,summe2:integer;
begin
result := 0;
summe1 := 0;
summe2 := 0;
for y := 0 to Image1.Height -1 do
  begin
    P1 := Image1.ScanLine[y];
    P2 := Image2.ScanLine[y];
      if not CompareMem(p1,p2,Image1.Width*SizeOf(TRGBTriple)) then
        begin
          for x := 0 to Image1.Width-1 do
            begin
              inc(summe1,RGB(P1[x].rgbtRed,P1[x].rgbtGreen,P1[x].rgbtBlue));
              inc(summe2,RGB(P2[x].rgbtRed,P2[x].rgbtGreen,P2[x].rgbtBlue));
              if summe1 <> summe2 then
                begin
                  summe1 := 0;
                  summe2 := 0;
                  inc(result);
                end;
            end;
        end;
  end;
Application.ProcessMessages;
end;

Ein Aufruf könnte so erfolgen:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
begin
ShowMessage(IntToStr(CompareImages(Image1.Picture.Bitmap,Image2.Picture.Bitmap)));
end;

Bei Rückfragen einfach melden.
Hf, Flips :coder:

[EDatabaseError]

kann es sein das es bei zu großen bildern ne AV auslöst?

mfg
tobi

[Phantom1]

Zitat:

Zitat von EDatabaseError

kann es sein das es bei zu großen bildern ne AV auslöst?

der code oben dürfte auch bei großen bildern ok sein, es könnte aber eine AV kommen wenn man vergisst das pixelformat auf pf24bit zu stellen :wink:

Hab den Code von Flips mal optimiert, ist jetzt ca 4 mal schneller:

Delphi-Quellcode:

function CompareImages(Bitmap1, Bitmap2: TBitmap): LongWord;
var
  xy: integer;
  P1, P2: PInteger;
begin
  Result:=0;
  Bitmap1.PixelFormat:=pf32bit;
  Bitmap2.PixelFormat:=pf32bit;
  P1:=Bitmap1.ScanLine[Bitmap1.Height-1];
  P2:=Bitmap2.ScanLine[Bitmap2.Height-1];
  for xy:=1 to Bitmap1.Height*Bitmap1.Width do begin
    Inc(Result, Byte(P1^<>P2^));
    Inc(P1);
    Inc(P2);
  end;
end;

mfg

[Flips]

Thx für das ganze Feedback. Ich will jetzt ned böse sein, finds ja nett das du den Code optimiert hast, aber dein Code is 6* langsamer :X

[Igotcha]

Was bringt mir der Code aus dem Ursprungspost? Ist nicht böse gemeint ;-)

Hintergrund: Ich suche und versuche mich schon seit längerem sporadisch an einem Code, der 2 Bilder auf "Gleichheit" analysiert, um Doubletten in der privaten Bilderflut Herr zu werden.

Um 2 Bilder zu vergleichen, ob sie "identisch" sind, reicht ein Hash. Gleicher Hash = gleiche Bilder. Da nehme ich eine x-beliebige Hashfunktion.

Was nützt mir o.g. Code, wenn ich als Ergebnis bekomme, dass x Pixel unterschiedlich sind? Ich weiss, dass sie dann offenbar nicht "identisch" sind - aber das bekomme ich auch anders heraus.

2 Bilder sind bei mir aber auch "gleich", wenn sie z.B. inhaltlich gleich, aber in einer anderen Auflösung vorliegen und da hilft mir der o.g. Code nicht.

Viele Grüße
Igotcha

[Flips]

Mhh gute Argumente^^
Klar, wenn man wissen will ob sie identisch sind nimmt man den Hash.
Klar, es geht nur bei Bildern gleicher Auflösung.

Aber der Code ist so gemeint wie dieser hier. Ich hab mal einen gebraucht der mir aus 2 auflösungsgleichen Bildern die unterschiedlichen Pixel liefert und gemerkt, dass im Internet befindliche Algo's einfach viel zu langsam sind. Deshalb hab ich mir gedacht, probier ich die mal zu optimieren. Und da mir das gelungen ist (ob das andere jetzt auch so sehn sei dahingestellt), wieso auch nicht andere daran teilhaben lassen? ;-)
Ich meins doch nur gut :wink:

:pale: :duck:

[Phantom1]

Zitat:

Zitat von Flips

Thx für das ganze Feedback. Ich will jetzt ned böse sein, finds ja nett das du den Code optimiert hast, aber dein Code is 6* langsamer :X

Das kann ich so aber nich stehen lassen :wink: wie hast du denn die zeit gemessen?

ich messe die Zeit so hier:

Delphi-Quellcode:

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

  for i:=1 to 500 do
    CompareImages(image1.Picture.Bitmap, Image2.Picture.Bitmap);

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

Insgesamt 500 durchläufe um messungenauigkeiten zu verhindern, dein Code braucht da 5,2 sek und im vergleich dazu mein code nur 1,7 sek.

Getestet habe ich das mit 2 verschiedenen Bildern (1024x768) auf einem Athlon64 X2 4600+ und 2GB RAM.

mfg

[Flips]

ich hab sie mit dem QueryPerformanceCounter gemessen.

Delphi-Quellcode:

procedure CompareImagesWithTesting(Image1,Image2:TBitmap);
var x,y:integer;
    P1,P2:PRGBTripleArray;
    summe1,summe2:integer;
begin
differents := 0;
summe1 := 0;
summe2 := 0;
QueryPerformanceFrequency(freq);
QueryPerformanceCounter(zeit1);
for y := 0 to Image1.Height -1 do
  begin
    P1 := Image1.ScanLine[y]; 
    P2 := Image2.ScanLine[y];
      if not CompareMem(p1,p2,Image1.Width*SizeOf(TRGBTriple)) then
        begin
          for x := 0 to Image1.Width-1 do
            begin
              inc(summe1,RGB(P1[x].rgbtRed,P1[x].rgbtGreen,P1[x].rgbtBlue));
              inc(summe2,RGB(P2[x].rgbtRed,P2[x].rgbtGreen,P2[x].rgbtBlue));
              if summe1 <> summe2 then
                begin
                  summe1 := 0;
                  summe2 := 0;
                  inc(differents);
                end;
            end;
        end;
  end;


QueryPerformanceCounter(zeit2);
Application.ProcessMessages;
Form1.Memo1.Lines.Add(FormatFloat('0.0000', (zeit2 - zeit1) * 1000 / freq));
Form1.Memo2.Lines.Add(IntToStr(differents));
end;

Hab ja für Jufo noch en Programm geschrieben. 100 Durchläufe

[alzaimar]

Die beiden Algorithmen sind so nicht vergleichbar, da Phantoms Algo zunächst auf 32 bit Farbtiefe umrechnet. Auch ohne diese Umrechnung kann man die Verfahren nicht vergleichen, da eben das zugrundeliegende Pixel unterschiedlich ist.

Flips' Verfahren ist aber wirklich ordendlich schnell. Sofern die Bilder identisch oder doch Zeilenweise hinreichend gleich sind, denn er prüft zunächst mit CompareMem, ob die beiden 'Scanlines' überhaupt Unterschiede aufzeigen.

Wenn schon, dann kann man ja gleich die gesamte Bitmap per CompareMem vergleichen (bringt nochmal 10%).

Wie schon erwähnt, ist der Algorithmus nett, aber nicht zu gebrauchen. Immerhin ist der ungewöhnliche Vergleich interessant.

Viel interessanter wäre es, einen Ähnlichkeitsindex von zwei beliebigen Bildern zu erstellen, die unterschiedlich kodiert (JPEG vs. BMP) und in unterschiedlichen Farbtiefen und Auflösungen vorliegen.

[Flips]

Zitat:

Flips' Verfahren ist aber wirklich ordendlich schnell.

Endlich ma ne positive Meinung :stupid:

Zitat:

Wie schon erwähnt, ist der Algorithmus nett, aber nicht zu gebrauchen. Immerhin ist der ungewöhnliche Vergleich interessant.

Hachja wie aufbauend :-D :-D :-D
Nee jetzt ma im Ernst, klingt vll als wär ich schwer von Begriff aber warum ist der jetzt ned zu gebrauchen? Hab das ned so ganz verstanden? :wink: :stupid: