Sum of the absolute differences

The sum of the absolute differences (abbreviation SAD , from English sum of absolute differences ) is a positive number that is created by forming the difference between two digital images . It serves as a measure of the difference between two images and is used in image processing and section recognition .

The SAD is obtained by subtracting the color values ​​of the images from one another pixel by pixel and adding them up.

Mathematical basics

An image is a mapping of a two-dimensional set of definitions into a range of values . The definition set corresponds to the set of all image points in the image and is therefore given by , where b denotes the width and h the height of the image in pixels . The range of values ​​corresponds to the color space of the image and is given for a normal gray value model with 7 bit color depth by ; if it is a color image, the range of values ​​is usually three-dimensional. ${\displaystyle B:\mathbb {D} _{1}\times \mathbb {D} _{2}\to \mathbb {W} }$ ${\displaystyle \mathbb {D} _{1}\times \mathbb {D} _{2}=\{0,1,...,b-1\}\times \{0,1,...,h-1\}}$ ${\displaystyle \mathbb {W} =\{0,1,...,127\}}$

Given two images of equal size and , the sum of the absolute differences is defined by: ${\displaystyle B_{1}}$ ${\displaystyle B_{2}}$

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

where b is the width and h is the height of the images.

The sum of the absolute differences is positive semidefinite, i.e. always . ${\displaystyle \geq 0}$

Implementation in IT (monochrome images)

In computer science, for example, a digital image is represented by the following data type:

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

The algorithm is implemented for two images of the same size using the following pseudocode :

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])
 }

The algorithm has a complexity of , where n denotes the number of pixels. ${\displaystyle \Theta (n)=n}$