Bildvergleich mit ZeroMeanNormalizedCross-Correlation (ZNCC)

[christian.noeding]

Auf der Suche nach einer Möglichkeit, mehrere Bilder miteinander zu vergleichen bin ich auf die Kreuz-Korrelation gestoßen. Mit dem folgenden Algorithmus kann man zwei Canvas beliebiger Größe miteinander vergleichen und bekommt das Ergebnis als Prozentwert der Übereinstimmung zurück. 100% bedeutet demnach perfekte Übereinstimmung.
Alternativ kann der schwächere SSD Algorithmus verwendet werden. Link: SSD

Delphi-Quellcode:

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

Delphi-Quellcode:

function RGB2TColor(const R, G, B: Byte): Integer;
begin
  // convert hexa-decimal values to RGB
  Result := R + G shl 8 + B shl 16;
end;

Delphi-Quellcode:

procedure TColor2RGB(const Color: TColor; var R, G, B: Byte);
begin
  // convert hexa-decimal values to RGB
  R := Color and $FF;
  G := (Color shr 8) and $FF;
  B := (Color shr 16) and $FF;
end;

Delphi-Quellcode:

// ZeroMeanNormalizedCross-Correlation (ZNCC) (wird MAXIMAL bei guter Übereinstimmung)

function TForm1.ZNCC(Bild1, Bild2: TBitmap):Single;
var
  x, y:integer;
  P1,P2:array[0..31] of PRGBTripleArray;

  a, b, zaehler, nenner1, nenner2, nenner, summe1, summe2, mean1, mean2:single;

  ZNCCvalue:Extended;
begin
  // ZeroMeanNormalizedCross-Correlation (ZNCC) (wird MAXIMAL bei guter Übereinstimmung)
  zaehler:=0.0;
  nenner1:=0.0;
  nenner2:=0.0;
  summe1:=0.0;
  summe2:=0.0;

  // Bildformat auf 24bit setzen (also ohne Alpha-Kanal)
  Bild1.PixelFormat := pf24bit;
  Bild2.PixelFormat := pf24bit;

  // Summen bilden
  for y:=0 to Bild1.Height-1 do
  begin
    P1[y]:=Bild1.ScanLine[y];
    P2[y]:=Bild2.ScanLine[y];

    for x:=0 to Bild1.Width-1 do
    begin
      summe1:=summe1+RGB2TColor(P1[y][x].rgbtRed, P1[y][x].rgbtGreen, P1[y][x].rgbtBlue);
      summe2:=summe2+RGB2TColor(P2[y][x].rgbtRed, P2[y][x].rgbtGreen, P2[y][x].rgbtBlue);
    end;
  end;

  mean1:=(1/power((Bild1.Width-1)+(Bild1.Height-1)+1,2))*summe1;
  mean2:=(1/power((Bild1.Width-1)+(Bild1.Height-1)+1,2))*summe2;
  for x:=0 to Bild1.Width-1 do
  begin
    for y:=0 to Bild1.Height-1 do
    begin
      a:=RGB2TColor(P1[y][x].rgbtRed, P1[y][x].rgbtGreen, P1[y][x].rgbtBlue)-mean1;
      b:=RGB2TColor(P2[y][x].rgbtRed, P2[y][x].rgbtGreen, P2[y][x].rgbtBlue)-mean2;
      zaehler:=zaehler+(a*b);
      nenner1:=nenner1+power(a, 2);
      nenner2:=nenner2+power(b, 2);
    end;
  end;
  nenner:=sqrt(nenner1*nenner2);

  if nenner>0 then
    ZNCCvalue:=zaehler/nenner
  else
    ZNCCvalue:=0.0;

  result:=ZNCCvalue*100;
end;

Der Code hat bei mir gut funktioniert. Anbei auch nochmal der Original-Algorithmus.

viel Erfolg,
Christian

Edit: Verwendung von .Pixels auf .ScanLine geändert. Durchlaufgeschwindigkeit bei Vergleich von 500 Dateien mit 32x32px <120ms auf einem Core2Duo mit 2,4Ghz

[rollstuhlfahrer]

es wäre vielleicht noch besser, wenn man nicht nur quadratische Bilder vergleichen kann. Die meisten Bilder die man im Internet zu, Beispiel findet sind ja alle rechteckig. Gleiches gilt auch für den anderen Algorithmus.

Bernhard

PS: 100% (Rückgabewert 100) ist dann bei totaler Übereinstimmung?

[christian.noeding]

Hi,

habe ja bei meinem anderen Codebeispiel auch schon geantwortet (siehe SSD). Algorithmus wird noch ausgebaut, wenn ich Zeit habe. Als erster Ansatz sollte das aber vielen schonmal ausreichen :)

Zitat:

PS: 100% (Rückgabewert 100) ist dann bei totaler Übereinstimmung?

Exakt - und das funktioniert auch gut.

[anubis2k5]

zum testen fehlt mir leider die Deklaration der Variable "Power"... :gruebel:

[rollstuhlfahrer]

Power ist keine Variable sondern eine Funktion. Diese sollte sich in der Unit Math befinden. Wenn nicht einfach mal danach suchen.

Bernhard

PS: Hier sollte es auch reichen einfach die Schleifen zu erweitern, oder?

[christian.noeding]

Hi Bernhard,


Problem bei der Erweiterung der Schleife: die Mittelwertberechnung wird dann falsch, da hier von quadratischen Bildern ausgegangen wird. Hier müsste man eine andere Berechnungsvorschrift finden. Ist aber bestimmt möglich :)


ciao,
Christian

[anubis2k5]

:wall: Ach! An das neue Hilfesystem von Delphi muss ich mich erstmal noch gewöhnen...

[bossberlin112]

Hallo, leider funktioniert das ganze nicht.

Es gibt immer eine Exception hier:

for x:=0 to Bild1.Width-1 do
begin
summe1:=summe1+RGB2TColor(P1[y][x].rgbtRed, P1[y][x].rgbtGreen, P1[y][x].rgbtBlue);
summe2:=summe2+RGB2TColor(P2[y][x].rgbtRed, P2[y][x].rgbtGreen, P2[y][x].rgbtBlue);
end;

Ich möchte 2 Bilder vergleichen und den Prozentwert der Übereinstimmung bestimmen. Gibt's ne aktuellere Version bzw. ein Testprogramm, um evtl. Fehler auszuschließen?!

Derzeit bestimme ich die Anzahl unterschiedlicher Pixel über folgende Funktion, allerdings ist mir nicht ganz klar, wie ich hier den Korrelationskoeffizient bestimme etc. .... kann wer helfen? :-D

Code:

function TForm1.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;

[bernhard_LA]

für die einfache Cross Correlation gibt es unter http://sourceforge.net/p/nccfastncc/code/3/tree/trunk/ ein fertiges Demo Projekt zum testen.


Zero Mean Cross Correlation , bzw. Fast NCC sind dann die Erweiterungen zu obigem Projekt .
Durch die Weiterentwicklung von obigem Code konnten wir ~ 100 x schneller werden,
den Code kann ich leider nicht posten, war eine Auftragsarbeit.

[christian.noeding]

Zitat:

Hallo, leider funktioniert das ganze nicht.

Es gibt immer eine Exception hier:

Hi,

Du musst natürlich noch die Pixelanzahl, also die Breite der Arrays P1,P2 und TRGBTripleArray anpassen. Im Beispiel ist es für ein 32x32 Pixel-Bild angegeben, weshalb das Array von 0 bis 31 geht. Wenn Du eine andere Größe verwendest, musst Du hier das Array anpassen.


viele Grüße,
Christian