Histogram difference

This article or section needs to be revised. Details should be given on the talk page. Please help to improve it , and then remove this flag.

The histogram difference (abbreviation HD ) is a positive number that results from forming the difference between two histograms . It serves as a measure of the difference between two histograms and is used in section recognition and image processing .

A distinction is made between numerous forms of histogram differences, the following being subject to a high level of distribution: the absolute histogram difference , the squared histogram difference and the absolute difference between the cumulative histograms . This is the implementation of Earth Mover's Distance for one-dimensional diagrams. When one speaks of "the" histogram difference, the absolute histogram difference is always meant. Further forms of the histogram difference are derived from the difference in the continuous probability density functions , such as the Kullback-Leibler divergence or the ${\displaystyle HD_{abs}}$ ${\displaystyle HD_{squ}}$ ${\displaystyle HD_{EMD}}$ ${\displaystyle HD_{EMD}}$Jensen-Shannon divergence .

The different forms of the histogram difference differ in terms of their sensitivity to differences between the histograms.

Mathematical basics

Histograms are mappings of a set of definitions into a set of values . ${\displaystyle H:\mathbb {D} \to \mathbb {W} }$

In image processing and section recognition, the definition set corresponds to the set of all possible color values ​​of the image; Since gray- scale images with a color depth of 8  bits are usually used, the definition set is usually given by. The range of values ​​then corresponds to the size of the image: if h corresponds to the height and b to the width of the image in pixels . The value of the histogram at point d then indicates how many pixels in the image have brightness d. ${\displaystyle \mathbb {D} =\{0,1,...,255\}\subset \mathbb {N} _{0}}$ ${\displaystyle \mathbb {W} =\{0,1,...,h\cdot b\}\subset \mathbb {N} _{0}}$

It corresponds to a discretized probability density function .

A cumulative histogram is an alternative form of representation of a histogram. The amount of definition and the range of values ​​remain the same, the cumulative histogram results from the formula:

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

It finds its equivalent in the discretized distribution function .

Cumulative histograms are mainly used by the section recognition, because they are less sensitive to minor differences in the brightness of two images. In image processing and section recognition, the value of the cumulative histogram at point d indicates how many pixels in the image have brightness d or are darker.

The three above histogram differences are defined by:

• absolute histogram difference:

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

• squared histogram difference:

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

• cumulative histogram difference:

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

All three differences are positive semidefinite, i.e. always . ${\displaystyle \geq 0}$

Implementation in IT

In computer science, images and histograms are generally represented by the following data types:

 type Bild {
    int Breite;
    int Hoehe;
    int Pixel[0..Breite][0..Hoehe];
 }

 long Histogramm[0..d-1];

Here, w denotes the width and h the height of the image in pixels, while d denotes the number of all possible color values ​​of the images.

The algorithm for determining the histogram difference then consists of the following parts:

 // 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;
 }

The algorithm has a complexity of , where b denotes the width and h the height of the images in pixels and f the number of different colors. ${\displaystyle \Theta (b,h,f)=b\cdot h+f}$

Individual evidence

1. ^ Julien Rabin, Julie Delon and 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 .