Bildvergleich mit Summe der quadratischen Unterschiede (SSD)

[christian.noeding]

Ein kleiner, schneller Algorithmus, um Bilder miteinander zu vergleichen ist der SSD (Sum of Squared Differences) Algorithmus. Die Formel ist im Anhang zu diesem Post.

Das Bild wird zunächst in den L*a*b*-Farbraum umgerechnet, um das Bild nur über die Helligkeit eines Pixels zu vergleichen. Anschließend wird der Algorithmus ausgeführt. Der zurückgegebene Wert wird größer, je UNTERSCHIEDLICHER die Bilder sind.

Der SSD-Algorithmus ist allerdings nicht wirklich super. Besser ist der ZNCC, den ich ebenfalls hier in der CodeLib beschrieben habe (Link zum ZNCC)

Delphi-Quellcode:

function SSD(Canvas1, Canvas2: TCanvas; Pixel:integer):Single;
var
  x, y:integer;
  Gamma, Intensity1, PixelValue1, Intensity2, PixelValue2:single;
  R1, G1, B1, R2, G2, B2, Grayscale1, Grayscale2:byte;
  MyColor1, MyColor2:TColor;

  SSDvalue:Extended;
begin
  SSDvalue:=0.0;
  Gamma:=2.2;

  for x:=0 to (Pixel-1) do
  begin
    for y:=0 to (Pixel-1) do
    begin
      MyColor1:=Canvas1.Pixels[x, y];
      TColor2RGB(MyColor1, R1, G1, B1);

      MyColor2:=Canvas2.Pixels[x, y];
      TColor2RGB(MyColor2, R2, G2, B2);

      // Graustufenbild 1 (Umrechnung auf L*a*b - Farbraum)
      Intensity1:=0.2126 * Power(R1/255, Gamma) + 0.7152 * Power(G1/255, Gamma) + 0.0722 * Power(B1/255, Gamma);
      Grayscale1:=255-round(116*Power(Intensity1, 1/3)-16);
      PixelValue1:=Grayscale1/255;

      // Graustufenbild 2 (Umrechnung auf L*a*b - Farbraum)
      Intensity2:=0.2126 * Power(R2/255, Gamma) + 0.7152 * Power(G2/255, Gamma) + 0.0722 * Power(B2/255, Gamma);
      Grayscale2:=255-round(116*Power(Intensity2, 1/3)-16);
      PixelValue2:=Grayscale2/255;

      // SumOfSquaredDifferences (SSD) (wird MINIMAL (<1) bei guter Übereinstimmung)
      SSDvalue:=SSDvalue+Power((PixelValue1-PixelValue2), 2);
    end;
  end;

  result:=SSDvalue;
end;

[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: Bei totaler Übereinstimmung sollte der Rückgabewert doch eigentlich 0 sein, oder?

[christian.noeding]

Hi,

du hast recht, der Wert ist =0, wenn identisch. Wird gleich angepasst :)

Ich habe den Algorithmus derzeit nur für 32x32 Icons getestet. Wenn ich etwas Zeit habe, baue ich den Code noch aus.


bis dann,
Christian

[rollstuhlfahrer]

Hi,

reicht es denn nicht einfach aus, dass man die Schleifen so umschreibt, dass die eine von 0 bis Breite -1 und die andere von 0 bis Höhe -1 geht?

Bernhard

[himitsu]

Zitat:

Zitat von christian.noeding

Ein kleiner, schneller Algorithmus,

nja, .Pixels ist nicht unbedingt schnell.
gegenüber .ScanLine arbeitet man damit sogar arschlangsam :angel:

[schöni]

Hallo,

Klasse Arbeit. Hab mir die Formeln auch angeschaut. Wofür stehen u, i, v j, n? Img ist sicher ein zu untersuchendes Bild?

[christian.noeding]

@himitsu: ich bezog mich auf den Algorithmus - nicht auf das auslesen des Bildes :) aber du hast recht - eine Scanline-Optimierte Variante sollte deutlich schneller sein

@schöni:
n = Pixelanzahl "Pixel"
i,j = Laufvariablen "x","y"
u1,u2,v1,v2 = Bildmittelpunkt - die Formel geht eigentlich vom Zentrum aus
Img1, Img2 = das eigentliche Bild, korrekt


bis dann,
Christian

[schöni]

Zitat:

Zitat von christian.noeding

@himitsu: ich bezog mich auf den Algorithmus - nicht auf das auslesen des Bildes :) aber du hast recht - eine Scanline-Optimierte Variante sollte deutlich schneller sein

@schöni:
n = Pixelanzahl "Pixel"
i,j = Laufvariablen "x","y"
u1,u2,v1,v2 = Bildmittelpunkt - die Formel geht eigentlich vom Zentrum aus
Img1, Img2 = das eigentliche Bild, korrekt


bis dann,
Christian

Ok, Danke so weit!

Da müssen u und v also mit weiteren Formeln erst berechnet werden. Die Potenzen treten nämlich in der angegebenen Formel nicht auf. Erst im konkreten Algorhithmus.

u1 wäre dann x-Koordinate Bild 1, u2 -> x-Koordinate Bild 2, analog v1,v2 die y Koordinaten.

Wenn vom Zentrum des Bildes aus verglichen wird, verstehe ich den Lauf von -n bis +n nicht.
Ich kann ihn im obigen Quellcode zumindest nicht erkennen.
Einleuchtend wäre für mich, vom Zentrum des Bildes aus in 4 Richtungen zu vergleichen.

Die Umwandlung in ein Graustufenbild verstehe ich als eine Anpassung an praktische Erfordernisse. Komplexität reduzieren um nur noch die reine Bildinformation vergleichen zu müssen.
Das ist aber in der Formel zunächst auch nicht enthalten. Wird erst bei der Implementation des konkreten Algorhithmus eingeführt.

[christian.noeding]

Zitat:

u1 wäre dann x-Koordinate Bild 1, u2 -> x-Koordinate Bild 2, analog v1,v2 die y Koordinaten.

Korrekt

Zitat:

Wenn vom Zentrum des Bildes aus verglichen wird, verstehe ich den Lauf von -n bis +n nicht.
Ich kann ihn im obigen Quellcode zumindest nicht erkennen.
Einleuchtend wäre für mich, vom Zentrum des Bildes aus in 4 Richtungen zu vergleichen.

In der Formel wird u und v als Bildmittelpunkt angegeben. Das Aufsummieren von -n bis n lässt also Zeilenweise von linkem Rand bis rechten Rand des Bildes aufsummieren. Ich habe der Einfachheit halber gleich von 0 bis Bildbreite und dann von 0 bis Bildhöhe aufsummiert. Sollte das gleiche Resultat bringen.

Zitat:

Die Umwandlung in ein Graustufenbild verstehe ich als eine Anpassung an praktische Erfordernisse. Komplexität reduzieren um nur noch die reine Bildinformation vergleichen zu müssen.
Das ist aber in der Formel zunächst auch nicht enthalten. Wird erst bei der Implementation des konkreten Algorhithmus eingeführt.

Richtig. Ich habe ehrlich gesagt keine Möglichkeit gefunden, alle drei Bildfarben gleichzeitig in den Algorithmus einzubinden. Hast du da eine Lösung?


bis dann,
Christian