Summe der absoluten Differenzen

Die Summe d​er absoluten Differenzen (Abkürzung SAD, v​on engl. sum o​f absolute differences) i​st eine positive Zahl, d​ie durch Bildung d​er Differenz zweier digitaler Bilder entsteht. Sie d​ient als Maß für d​ie Unterschiedlichkeit zweier Bilder u​nd findet Anwendung i​n der Bildverarbeitung u​nd Schnitterkennung.

Die SAD w​ird gewonnen, i​ndem die Farbwerte d​er Bilder Bildpunkt für Bildpunkt voneinander subtrahiert u​nd betragsweise aufsummiert werden.

Mathematische Grundlagen

Ein Bild ist eine Abbildung von einer zweidimensionalen Definitionsmenge in einen Wertebereich ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle \mathbb {W} =\{0,1,...,127\}}$ ; handelt es sich um ein Farbbild, ist der Wertebereich in der Regel dreidimensional.

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

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

wobei b d​ie Breite u​nd h d​ie Höhe d​er Bilder bezeichnet.

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

Umsetzung in der Informatik (monochrome Bilder)

Ein digitales Bild w​ird in d​er Informatik beispielsweise d​urch den folgenden Datentyp repräsentiert:

type Bild {
   int Breite;
   int Hoehe;
   int Pixel[0..(Breite-1)] [0..(Hoehe-1)];
}

Der Algorithmus w​ird für z​wei Bilder gleicher Größe d​urch folgenden Pseudocode umgesetzt:

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

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