Summe der absoluten Differenzen

Die Summe der absoluten Differenzen (Abkürzung SAD, von engl. sum of absolute differences) ist eine positive Zahl, die durch Bildung der Differenz zweier digitaler Bilder entsteht. Sie dient als Maß für die Unterschiedlichkeit zweier Bilder und findet Anwendung in der Bildverarbeitung und Schnitterkennung.

Die SAD wird gewonnen, indem die Farbwerte der Bilder Bildpunkt für Bildpunkt voneinander subtrahiert und betragsweise aufsummiert werden.

Mathematische Grundlagen

Ein Bild ist eine Abbildung von einer zweidimensionalen Definitionsmenge in einen Wertebereich $B:\mathbb {D} _{1}\times \mathbb {D} _{2}\to \mathbb {W}$. Die Definitionsmenge entspricht der Menge aller Bildpunkte des Bildes und ist demnach gegeben durch $\mathbb {D} _{1}\times \mathbb {D} _{2}=\{0,1,...,b-1\}\times \{0,1,...,h-1\}$, wobei b die Breite und h die Höhe des Bildes in Pixeln bezeichnet. Der Wertebereich entspricht dem Farbraum des Bildes und ist für ein gewöhnliches Grauwert-Modell mit 7 Bit Farbtiefe gegeben durch $\mathbb {W} =\{0,1,...,127\}$; handelt es sich um ein Farbbild, ist der Wertebereich in der Regel dreidimensional.

Gegeben zwei gleich große Bilder $B_{1}$ und $B_{2}$ ist die Summe der absoluten Differenzen definiert durch:

$SAD=\sum _{x=0}^{b-1}\sum _{y=0}^{h-1}\left|B_{2}(x,y)-B_{1}(x,y)\right|$

wobei b die Breite und h die Höhe der Bilder bezeichnet.

Die Summe der absoluten Differenzen ist positiv semidefinit, also stets $\geq 0$.

Umsetzung in der Informatik (monochrome Bilder)

Ein digitales Bild wird in der Informatik im Allgemeinen durch den folgenden Datentyp repräsentiert:

type Bild {
   int Breite;
   int Hoehe;
   int Pixel[0..Breite][0..Hoehe];
}

Der Algorithmus wird durch folgenden Pseudocode umgesetzt:

long berechneSAD(Bild B1, Bild B2)
{
   long SAD = 0;
   For x = 0 to B1.Width - 1 do
      For y = 0 to B2.Height - 1 do
         SAD = SAD + abs(B2.Pixel[x][y] - B1.Pixel[x][y])
}

Der Algorithmus hat eine Komplexität von $\Theta (n)=n$, wobei n die Anzahl Pixel bezeichnet.