Quelltext der Seite Histogramm-Differenz

{{Überarbeiten}}
Die '''Histogramm-Differenz''' (Abkürzung '''HD''') ist eine positive [[Zahl]], die durch Bildung der [[Subtraktion|Differenz]] zweier [[Histogramm]]e 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 <math>HD_{abs}</math>, die '''quadrierte''' Histogramm-Differenz <math>HD_{squ}</math> und die absolute Differenz der '''kumulierten''' Histogramme <math>HD_{EMD}</math>. Die <math>HD_{EMD}</math> ist dabei die Implementierung [[Earth Mover's Distance]] für eindimensionale Diagramme.<ref>{{Literatur |Autor=Julien Rabin, Julie Delon und Yann Gousseau |Titel=Circular Earth Mover’s Distance for the comparison of local features |Sammelwerk=19th International Conference on Pattern Recognition. ICPR 2008. |Datum=2008 |DOI=10.1109/ICPR.2008.4761372}}</ref> 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 [[Wahrscheinlichkeitsdichtefunktion]]en 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.

== Mathematische Grundlagen ==
Histogramme sind Abbildungen von einer [[Definitionsmenge]] in eine Wertemenge <math>H: \mathbb{D} \to \mathbb{W}</math>.

{| class="wikitable"
|In der Bildverarbeitung und Schnitterkennung entspricht die Definitionsmenge der Menge aller möglichen Farbwerte des Bildes; da in der Regel [[Grauwert]]-Bilder mit einer Farbtiefe von 8&nbsp;[[Bit]] verwendet werden, ist die Definitionsmenge hier meist durch <math>\mathbb{D}=\{0, 1, ..., 255\} \subset \mathbb{N}_0</math> gegeben. Der Wertebereich entspricht dann der Größe des Bildes: <math>\mathbb{W}=\{0, 1, ..., h \cdot b\} \subset \mathbb{N}_0</math>, wenn h der Höhe und b der Breite des Bildes in [[Pixel]]n entspricht. Der Wert des Histogramms an der Stelle&nbsp;d gibt dann an, wie viele Pixel des Bildes die Helligkeit&nbsp;d haben.
|}

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:

: <math>K(i)=\sum_{d<i}^{} H(d)</math>

Es findet seine Entsprechung in der diskretisierten [[Verteilungsfunktion]].

{| class="wikitable"
|Kumulierte Histogramme werden vor allem von der Schnitterkennung verwendet, denn sie sind unempfindlicher für kleinere Unterschiede in der Helligkeit zweier Bilder. In der Bildverarbeitung und Schnitterkennung gibt der Wert des kumulierten Histogramms an der Stelle&nbsp;d an, wie viele Pixel des Bildes die Helligkeit&nbsp;d haben oder dunkler sind.
|}

Die drei oben Histogramm-Differenzen sind definiert durch:

* absolute Histogramm-Differenz:
*: <math>HD_{abs}=\sum_{d\in\mathbb{D}} \left| H_2(d)-H_1(d) \right|</math>
* quadrierte Histogramm-Differenz:
*: <math>HD_{squ}=\sum_{d\in\mathbb{D}} \left( H_2(d)-H_1(d) \right)^2</math>
* kumulierte Histogramm-Differenz:
*: <math>HD_{EMD}=\sum_{d\in\mathbb{D}} \left| K_2(d)-K_1(d) \right|</math>

Alle drei Differenzen sind positiv semidefinit, also stets <math>\ge0</math>.

== Umsetzung in der Informatik ==
Bilder und Histogramme werden in der Informatik im Allgemeinen durch die folgenden Datentypen repräsentiert:
<syntaxhighlight lang="haskell">
 type Bild {
    int Breite;
    int Hoehe;
    int Pixel[0..Breite][0..Hoehe];
 }

 long Histogramm[0..d-1];
</syntaxhighlight>

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:
<syntaxhighlight lang="haskell">
 // 1.) Histogramm ermitteln:
 Histogramm berechneHistogramm(Bild B)
 {
    Histogramm H;
    For x <- 0 to B.Hoehe - 1 do
       For y <- 0 to B.Breite - 1 do
          H[B.Pixel[x][y]] <- H[B.Pixel[x][y]] + 1
    return H;
 }

 // 2.) Kumuliertes Histogramm ermitteln:
 Histogramm berechneKumuliertesHistogramm(Histogramm H)
 {
    Histogramm K;
    K[0] <- H[0];
    For i <- 1 to MaxColorValue do
       K[i] <- K[i-1] + H[i]
    return K;
 }

 // 3.) Differenz zweier Histogramme oder kumulierter Histogramme bilden:
 int berechneHistogrammDifferenz(Histogramm H1, Histogramm H2)
 {
    int HD_abs, HD_squ <- 0;
    For i <- 0 to MaxColorValue do
       HD_abs <- HD_abs + abs(H2[i] - H1[i])
       HD_squ <- HD_squ +(H2[i] - H1[i])^2;
    return HD_abs;
    // oder: return HD_squ;
 }
</syntaxhighlight>

Der Algorithmus hat eine [[Komplexität]] von <math>\Theta(b,h,f)=b\cdot h+f</math>, wobei b die Breite und h die Höhe der Bilder in Pixeln und f die Anzahl der verschiedenen Farben bezeichnet.
== Einzelnachweise ==
<references />

[[Kategorie:Computergrafik]]
[[Kategorie:Filmtechnik]]
[[Kategorie:Bildverarbeitung]]