(image-quantization)=
# Image quantization

Image quantization [^1] describes the process of extracting meaningful
information from images and converting them into discrete values which
enable us to easily perform numerical computations.

Discrete images are often quantized by compressing a range of values
into a single representative natural number, i.e.
```{math}
f_h: \Omega_h \xrightarrow{ } \{0,...,N-1\}^m \quad \text{ with } \quad N\in \N.
```
The most common choices for the amount of different image values
$N\in\N$ are $N=256$ or $N=1024$.

````{prf:remark} Processing quantized images
:label: rem:processing_images
In practice one would never perform numerical computations directly on
the data structure of quantized images as large rounding errors would
occur and lead to visible artefacts, e.g., color distortion or a loss of
image quality.

To prevent these problems one typically uses the following processing
pipeline:

1.  Load a quantized image

2.  Convert image values to float representation (e.g., [IEEE 754
    format](https://en.wikipedia.org/wiki/IEEE_754))

3.  Perform image processing on float values

4.  Quantize resulting image again

5.  Save quantized result

````

````{prf:definition} Histogram
Let $\Theta:=\{z_j\in \R \mid j=1,...,N\}$ be a finite set of $N\in \N$
real values.\
Let $a:=\min_{j=1,...,N}{z_j},b:=\max_{j=1,...,N}{z_j}$ be the
minimal/maximal values in $\Theta$.\
We partition the interval $[a,b] \subset \R$ into $m \in \N$
subintervals called *bins*, with fixed size $h:=\frac{b-a}{m}$ via
$x_i=a + i\cdot h, \, i=0,...,m$.\
These bins are labeled $b_{i+1}=[x_i,x_{i+1}), \, i=0,...,m-2$ and
$b_m=[x_{m-1},x_m]$. The height of each bar and therefore the y-axis
represents the number of datapoints in one bin, we call this
*frequency*. With that, we define an (absolute) histogram
$H_{\Theta}: \{1,...,m\}\xrightarrow{ }\{0,...,N\}$ as
```{math}
H_{\Theta}(k):=|\{z_j\in \Theta | z_j \in b_k\}|.
```
This function gives us the amount of data points in the k-th bin.

````

::: center
:::

In this example there are two datapoints in the first bin, one datapoint
in the second bin and so on. To put such histograms in a better
perspective we scale the y-axis by $\frac{1}{N}$. Then the height of one
bar represent the percentage the total amount of data points in one bin.

````{prf:definition} Relative Histograms
The relative histogram $h_{\Theta}: \{1,...,m\}\xrightarrow{ }[0,1]$ is
defined as
```{math}
h_{\Theta}(k) = \frac{H_{\Theta}}{N} \Rightarrow \sum_k h_\Theta = 1.
```

````

::: center
:::

Thus $h_\Theta$ is an estimator for a probability density function
(PDF). In image processing such histograms find several important
applications, for example *Image quality assessment*. A histogram gives
a great overview of brightness, contrasts and the overall color range of
the image as it plots the number of pixels of a certain shade over the
value of said shade. Such histograms are called *image histograms*.

````{prf:definition} Image histogram
:label: def:image_histogram
Let $f_h:\Omega_h\xrightarrow{ }\{0,...,N\}$ be a discrete monochrome
image. We define the (absolute) image histogram
$H_f:\{0,...,N-1\}\xrightarrow{ }\{0,...,\lvert \Omega_h \rvert\}$ as
the amount of pixels with a certain gray value, i.e.,
```{math}
H_{f_h}(k) \ \coloneqq \ \lvert \{ x \in \Omega_h:f(x)=k \} \rvert  \quad \implies \quad \sum_{k=0}^{N-1} H_{f_h}(k)= \lvert \Omega_h \rvert.
```
The relative image histogram $h_{f_h}:\{0,...,N\}\xrightarrow{ }[0,1]$
is defined as
```{math}
h_{f_h}(k) = \frac{H_{f_h}(k)}{\lvert \Omega_h \rvert}.
```

````

A relative histogram is a discrete variant of a [probability density
function
(PDF)](https://en.wikipedia.org/wiki/Probability_density_function) as it
encodes the probability that a random image pixel has a certain value.

````{prf:remark} Coarse image histograms
Sometimes one is not interested in the frequency of every possible image
intensity value $k \in \{0,\ldots,N-1\}$ of a discrete image $f_h$, but
rather in the amount of pixels that fall in certain value ranges, i.e.,
histogram bins with a width larger than $1$.

In this case, we first specify the amount of resulting bins $m \in \N^+$
and then regard a coarse image histogram with bin width
$\alpha \coloneqq \frac{N-1}{m}$ with frequencies:
```{math}
H_{f_h}(k) \ \coloneqq \ | \{ x_i \in \Omega_h \, : \, f_h(x_i) \in [k \alpha, (k+1)\alpha) \}|.
```

````
```{figure} ../atelier/img/Hist_normalized_hist.png
---
name: ""
---
Grayscale astronaut image with image histogram and relative histogram.
```

An image histogram yields a good graphical representation of a colors
tonal distribution in one image. The x-axis represents the different
shades of the color while the y-axis the number of pixel of each tonal
value in the image. For an example see the following picture and the
corresponding image histograms for red, green and blue tones.

```{figure} ../atelier/img/Hist_color.png
---
name: ""
---
Astronaut RGB image with histograms of the three color channels.
```

Important to understand is that the values further to the right of the
x-axis represent higher and the values further to the left lower
brightness. So the x-axis ranges from no brightness (pitch black) to
maximum brightness (bright white).

The last piece of information to make working with image histograms easy
as pie lies in so called *cumulative image histograms*.

````{prf:definition} Cumulative image histogram
We define a *cumulative image histogram* as
```{math}
h_{c}(k) \ \coloneqq \ \sum_{i=0}^{k} h_{f_h}(i) .
```

````

This function is a discrete variant of a [cumulative distribution
function
(CDF)](https://en.wikipedia.org/wiki/Cumulative_distribution_function),
which measures the probability that an image pixel takes a value less or
equal than a specific number. Such a function gives information of how
well contrasted an image is. The closer the Cumulative Image Histogram
is to a line the better and wider contrasted the picture is. To change
pictures based on their histogram we require a couple of tools.

```{figure} ../atelier/img/Hist_cdf.png
---
name: ""
---
Grayscale image of an astronaut with the respective relative and
cumulative histogram.
```

[^1]: In mathematics quantization is the process of mapping from
    continuous infinite values to a smaller, finite set of discrete
    values. An easy example would be to rank the taste of food with
    scores between 1 and 10.