Histogramm-Differenz

Die Histogramm-Differenz (Abkürzung HD) ist eine positive Zahl, die durch Bildung der Differenz zweier Histogramme entsteht. Sie dient als Maß für die Unterschiedlichkeit zweier Histogramme und findet Anwendung in der Schnitterkennung und der Bildverarbeitung.

Man unterscheidet zahlreiche Formen von Histogramm-Differenzen, wobei die folgenden einer hohen Verbreitung unterliegen: die absolute Histogramm-Differenz ${\displaystyle HD_{abs}}${\displaystyle HD_{abs}}, die quadrierte Histogramm-Differenz ${\displaystyle HD_{squ}}${\displaystyle HD_{squ}} und die absolute Differenz der kumulierten Histogramme ${\displaystyle HD_{EMD}}${\displaystyle HD_{EMD}}. Die ${\displaystyle HD_{EMD}}${\displaystyle HD_{EMD}} ist dabei die Implementierung Earth Mover's Distance für eindimensionale Diagramme.^[1] Spricht man von „der" Histogramm-Differenz, so ist stets die absolute Histogramm-Differenz gemeint. Weitere Formen der Histogramm-Differenz werden aus der Differenz der kontinuierlichen Wahrscheinlichkeitsdichtefunktionen abgeleitet, wie die Kullback-Leibler-Divergenz oder die Jensen-Shannon-Divergenz.

Die unterschiedlichen Formen der Histogramm-Differenz unterscheiden sich hinsichtlich ihrer Empfindlichkeit gegenüber Unterschieden zwischen den Histogrammen.

Histogramme sind Abbildungen von einer Definitionsmenge in eine Wertemenge ${\displaystyle H:\mathbb {D} \to \mathbb {W} }${\displaystyle H:\mathbb {D} \to \mathbb {W} }.

Es entspricht dabei einer diskretisierten Wahrscheinlichkeitsdichtefunktion.

Ein kumuliertes Histogramm ist eine alternative Darstellungsform eines Histogramms. Definitionsmenge und Wertebereich bleiben gleich, das kumulierte Histogramm ergibt sich aus der Formel:

${\displaystyle K(i)=\sum _{d<i}^{}H(d)}${\displaystyle K(i)=\sum _{d<i}^{}H(d)}

Es findet seine Entsprechung in der diskretisierten Verteilungsfunktion.

Die drei oben Histogramm-Differenzen sind definiert durch:

• absolute Histogramm-Differenz:

  ${\displaystyle HD_{abs}=\sum _{d\in \mathbb {D} }\left|H_{2}(d)-H_{1}(d)\right|}${\displaystyle HD_{abs}=\sum _{d\in \mathbb {D} }\left|H_{2}(d)-H_{1}(d)\right|}

• quadrierte Histogramm-Differenz:

  ${\displaystyle HD_{squ}=\sum _{d\in \mathbb {D} }\left(H_{2}(d)-H_{1}(d)\right)^{2}}${\displaystyle HD_{squ}=\sum _{d\in \mathbb {D} }\left(H_{2}(d)-H_{1}(d)\right)^{2}}

• kumulierte Histogramm-Differenz:

  ${\displaystyle HD_{EMD}=\sum _{d\in \mathbb {D} }\left|K_{2}(d)-K_{1}(d)\right|}${\displaystyle HD_{EMD}=\sum _{d\in \mathbb {D} }\left|K_{2}(d)-K_{1}(d)\right|}

Alle drei Differenzen sind positiv semidefinit, also stets ${\displaystyle \geq 0}${\displaystyle \geq 0}.

Bilder und Histogramme werden in der Informatik im Allgemeinen durch die folgenden Datentypen repräsentiert:

typeBild{
intBreite;
intHoehe;
intPixel[0..Breite][0..Hoehe];
}
longHistogramm[0..d-1];

Hierbei bezeichnet w die Breite und h die Höhe des Bildes in Pixeln, während d die Anzahl aller möglichen Farbwerte der Bilder bezeichnet.

Der Algorithmus zur Ermittlung der Histogramm-Differenz setzt sich dann aus den folgenden Teilen zusammen:

//1.)Histogrammermitteln:
HistogrammberechneHistogramm(BildB)
{
HistogrammH;
Forx<-0toB.Hoehe-1do
Fory<-0toB.Breite-1do
H[B.Pixel[x][y]]<-H[B.Pixel[x][y]]+1
returnH;
}
//2.)KumuliertesHistogrammermitteln:
HistogrammberechneKumuliertesHistogramm(HistogrammH)
{
HistogrammK;
K[0]<-H[0];
Fori<-1toMaxColorValuedo
K[i]<-K[i-1]+H[i]
returnK;
}
//3.)DifferenzzweierHistogrammeoderkumulierterHistogrammebilden:
intberechneHistogrammDifferenz(HistogrammH1,HistogrammH2)
{
intHD_abs,HD_squ<-0;
Fori<-0toMaxColorValuedo
HD_abs<-HD_abs+abs(H2[i]-H1[i])
HD_squ<-HD_squ+(H2[i]-H1[i])^2;
returnHD_abs;
//oder:returnHD_squ;
}

Der Algorithmus hat eine Komplexität von ${\displaystyle \Theta (b,h,f)=b\cdot h+f}${\displaystyle \Theta (b,h,f)=b\cdot h+f}, wobei b die Breite und h die Höhe der Bilder in Pixeln und f die Anzahl der verschiedenen Farben bezeichnet.

1. ↑ Julien Rabin, Julie Delon und Yann Gousseau: Circular Earth Mover’s Distance for the comparison of local features. In: 19th International Conference on Pattern Recognition. ICPR 2008. 2008, doi:10.1109/ICPR.2008.4761372 . 

• Computergrafik
• Filmtechnik
• Bildverarbeitung

• Wikipedia:Überarbeiten