Wikipedia · einfach zusammengefasst · Stand
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 …
Inhalt5 Abschnitte
Grundidee und Einsatz
Die Histogramm-Differenz, abgekürzt HD, ist eine positive Zahl, die aus der Differenz zweier Histogramme berechnet wird. Sie dient als Maß dafür, wie unterschiedlich zwei Histogramme sind. Anwendung findet sie besonders in der Schnitterkennung und in der Bildverarbeitung, zum Beispiel beim Vergleich von Bildern anhand ihrer Helligkeits- oder Farbverteilung.
Ein Histogramm beschreibt, wie oft bestimmte Werte vorkommen. In der Bildverarbeitung bedeutet das meist: Für jeden möglichen Farb- oder Grauwert wird gezählt, wie viele Pixel eines Bildes genau diesen Wert besitzen. Je größer die Histogramm-Differenz zweier Bilder ist, desto stärker unterscheiden sich ihre Histogramme nach dem verwendeten Verfahren.
Arten der Histogramm-Differenz
Es gibt mehrere verbreitete Formen der Histogramm-Differenz. Die wichtigsten im Artikel genannten sind die absolute Histogramm-Differenz HD_abs, die quadrierte Histogramm-Differenz HD_squ und die absolute Differenz der kumulierten Histogramme HD_EMD.
Wenn allgemein von „der“ Histogramm-Differenz gesprochen wird, ist damit stets die absolute Histogramm-Differenz gemeint. HD_EMD ist die Implementierung der Earth Mover's Distance für eindimensionale Diagramme. Weitere Formen werden aus der Differenz kontinuierlicher Wahrscheinlichkeitsdichtefunktionen abgeleitet, etwa die Kullback-Leibler-Divergenz oder die Jensen-Shannon-Divergenz.
Die verschiedenen Formen unterscheiden sich darin, wie empfindlich sie auf Unterschiede zwischen den Histogrammen reagieren. Die quadrierte Differenz gewichtet größere Einzelunterschiede stärker, weil Differenzen quadriert werden. Die kumulierte Variante arbeitet mit kumulierten Histogrammen und ist dadurch in der Schnitterkennung unempfindlicher gegenüber kleineren Helligkeitsunterschieden.
Histogramme und kumulierte Histogramme
Mathematisch ist ein Histogramm eine Abbildung von einer Definitionsmenge in eine Wertemenge: H: D → W. In der Bildverarbeitung und Schnitterkennung ist die Definitionsmenge meist die Menge aller möglichen Farbwerte. Bei Grauwert-Bildern mit 8 Bit Farbtiefe ist sie gewöhnlich D = {0,1,...,255} ⊂ N_0.
Der Wertebereich entspricht der möglichen Anzahl von Pixeln im Bild. Wenn h die Höhe und b die Breite eines Bildes in Pixeln sind, dann gilt W = {0,1,...,h·b} ⊂ N_0. Der Wert H(d) gibt an, wie viele Pixel des Bildes die Helligkeit d haben. Ein Histogramm entspricht dabei einer diskretisierten Wahrscheinlichkeitsdichtefunktion.
Ein kumuliertes Histogramm ist eine andere Darstellungsform desselben Histogramms. Definitionsmenge und Wertebereich bleiben gleich. Es wird berechnet durch K(i) = Σ_{d<i} H(d). Es entspricht einer diskretisierten Verteilungsfunktion. In der Bildverarbeitung und Schnitterkennung gibt der Wert des kumulierten Histogramms an der Stelle d an, wie viele Pixel des Bildes die Helligkeit d haben oder dunkler sind.
Formeln und Eigenschaften
Die absolute Histogramm-Differenz ist definiert als HD_abs = Σ_{d∈D} |H_2(d) − H_1(d)|. Für jeden Wert d der Definitionsmenge wird also der Betrag der Differenz zwischen den beiden Histogrammwerten gebildet; anschließend werden alle Beträge addiert.
Die quadrierte Histogramm-Differenz ist definiert als HD_squ = Σ_{d∈D} (H_2(d) − H_1(d))². Hier wird jede Differenz quadriert und dann aufsummiert.
Die kumulierte Histogramm-Differenz ist definiert als HD_EMD = Σ_{d∈D} |K_2(d) − K_1(d)|. Sie vergleicht nicht die ursprünglichen Histogramme H_1 und H_2, sondern ihre kumulierten Histogramme K_1 und K_2.
Alle drei Differenzen sind positiv semidefinit. Das bedeutet, dass ihr Wert stets größer oder gleich 0 ist: HD ≥ 0.
Berechnung im Programm
In der Informatik werden Bilder und Histogramme typischerweise durch Datenstrukturen dargestellt. Ein Bild enthält seine Breite, seine Höhe und ein Pixel-Feld. Ein Histogramm kann als Feld long Histogramm[0..d-1] gespeichert werden, wobei d die Anzahl aller möglichen Farbwerte bezeichnet. Im Artikel steht außerdem: w bezeichnet die Breite und h die Höhe des Bildes in Pixeln.
Der Algorithmus besteht aus drei Hauptschritten. Zuerst wird das Histogramm eines Bildes berechnet: Für jedes Pixel wird sein Farbwert gelesen, und der entsprechende Zähler im Histogramm wird um 1 erhöht. Danach kann aus diesem Histogramm ein kumuliertes Histogramm berechnet werden: K[0] wird auf H[0] gesetzt, und für jeden weiteren Farbwert i gilt K[i] = K[i−1] + H[i].
Im dritten Schritt wird die Differenz zweier Histogramme oder zweier kumulierter Histogramme berechnet. Dazu läuft der Algorithmus über alle möglichen Farbwerte von 0 bis MaxColorValue. Für HD_abs wird jeweils abs(H2[i] − H1[i]) addiert. Für HD_squ wird jeweils (H2[i] − H1[i])² addiert. Zurückgegeben wird je nach gewünschtem Verfahren HD_abs oder HD_squ; für HD_EMD würden entsprechend die kumulierten Histogramme verglichen.
Die Komplexität des Algorithmus beträgt Θ(b,h,f) = b·h + f. Dabei ist b die Breite, h die Höhe der Bilder in Pixeln und f die Anzahl der verschiedenen Farben.