Control Keys

→ move to next slide (also Enter or Spacebar).
← move to previous slide.
 d  enable/disable drawing on slides
 p  toggles between print and presentation view
CTRL  +  zoom in
CTRL  -  zoom out
CTRL  0  reset zoom

Slides can also be advanced by clicking on the left or right border of the slide.

Notation

Type Font Examples
Variables (scalars) italics $a, b, x, y$
Functions upright $\mathrm{f}, \mathrm{g}(x), \mathrm{max}(x)$
Vectors bold, elements row-wise $\mathbf{a}, \mathbf{b}= \begin{pmatrix}x\\y\end{pmatrix} = (x, y)^\top,$ $\mathbf{B}=(x, y, z)^\top$
Matrices Typewriter $\mathtt{A}, \mathtt{B}= \begin{bmatrix}a & b\\c & d\end{bmatrix}$
Sets calligraphic $\mathcal{A}, B=\{a, b\}, b \in \mathcal{B}$
Number systems, Coordinate spaces double-struck $\mathbb{N}, \mathbb{Z}, \mathbb{R}^2, \mathbb{R}^3$

From 1D to 2D

  • In the previous chapters about discrete-time signals, many foundations of digital signal processing have already been covered: sampling theorem, convolution, low-pass, high-pass, etc.
  • In principle, images are also discrete signals, but now:
    • Discrete in space instead of discrete in time
    • Two dimensions $\mathrm{f}[x,y]$ instead of only one $\mathrm{f}[n]$

Convolution in 2D

  • The discrete-time convolution of two signals $\mathrm{a}[n]$ and $\mathrm{b}[n]$ is defined by:
    $\mathrm{f}[n] = \mathrm{a}[n] \ast \mathrm{b}[n] = \sum\limits_{k = -\infty}^{\infty} \mathrm{a}[k] \, \,\mathrm{b}[n-k]$
  • In the same way, the convolution can be defined in 2D:
    $\mathrm{f}[x,y] = \mathrm{a}[x,y] \ast \mathrm{b}[x,y] = \sum\limits_{j = -\infty}^{\infty} \sum\limits_{k = -\infty}^{\infty} \mathrm{a}[j, k] \, \,\mathrm{b}[x-j,y-k]$

Convolution of Images

  • 2D convolution:
    $\mathrm{f}[x,y] = \mathrm{a}[x,y] \ast \mathrm{b}[x,y] = \sum\limits_{j = -\infty}^{\infty} \sum\limits_{k = -\infty}^{\infty} \mathrm{a}[j, k] \, \,\mathrm{b}[x-j,y-k]$
  • As an example, consider the convolution between an image $\mathrm{a}[x,y]$ of size 4 x 3 pixels with a so-called kernel $\mathrm{b}[x,y]$ of size 3 x 3 pixels:
    convolve2d_part
    $b[x,y]$
    $x$
    $y$
    $-1$
    $0$
    $1$
    $-1$
    $0$
    $1$
    $a[x,y]$
    $x$
    $y$
    $0$
    $1$
    $2$
    $0$
    $1$
    $2$
    $3$
  • Outside the defined area all values of the kernel $\mathrm{b}[x,y]$ are zero, therefore
    $\mathrm{f}[x,y] = \mathrm{a}[x,y] \ast \mathrm{b}[x,y] = \sum\limits_{j = x-1}^{x+1} \,\, \sum\limits_{k = y-1}^{y+1} \, \mathrm{a}[j, k] \, \,\mathrm{b}[x-j,y-k]$

Convolution of Images

  • 2D convolution for the example:
    $\mathrm{f}[x,y] = \mathrm{a}[x,y] \ast \mathrm{b}[x,y] = \sum\limits_{j = x-1}^{x+1} \,\, \sum\limits_{k = y-1}^{y+1} \, \mathrm{a}[j, k] \, \,\mathrm{b}[x-j,y-k]$
convolve2d
Image
$a[x,y]$
$x$
$y$
$0$
$1$
$2$
$0$
$1$
$2$
$3$
Kernel
$b[x,y]$
$x$
$-1$
$0$
$1$
$y$
$-1$
$0$
$1$
Mirrored Kernel
$x$
$1$
$0$
$-1$
$y$
$1$
$0$
$-1$
Result
$f[x,y]$

Filter Kernels

  • In the following, we will first experiment with different filter kernels $\mathrm{b}[x,y]$
  • Later, the theory will be discussed in more detail
  • Note: In the literature the mirrored kernel is often given directly. In the following the mathematically correct convolution operator $b[x,y]$ is given (of course, it does not matter in case of symmetric kernels)

Filter Kernels

  • What is the effect of this filter kernel?
    $\begin{bmatrix}\frac{1}{9} & \frac{1}{9} & \frac{1}{9}\\ \frac{1}{9} & \frac{1}{9} & \frac{1}{9}\\ \frac{1}{9} & \frac{1}{9} & \frac{1}{9} \end{bmatrix} = \frac{1}{9}\begin{bmatrix}1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1& 1 \end{bmatrix}$
  • Answer:
    • Moving average (average filter)
    • A kind of low-pass filter (but also allows high frequencies to pass, because of the sinc function in the frequency domain)
horse_128
Original 		horse_128
3 x 3 		horse_128
5 x 5 		horse_128
7 x 7 		horse_128
21 x 21

Filter Kernels

  • What is the effect of this filter kernel?
    $\frac{1}{3}\begin{bmatrix}0 & 1 & 0\\ 0 & 1 & 0\\ 0 & 1& 0 \end{bmatrix}$
  • Answer:
    • Average filter in $y$-direction
    • Average filter in $x$-direction correspondingly:
      $\frac{1}{3}\begin{bmatrix}0 & 0 & 0\\ 1 & 1 & 1\\ 0 & 0& 0 \end{bmatrix}$
    • In fact, a filter with the size of 1 x 3 pixels or 3 x 1 Pixel pixels is sufficient

Filter Kernels

  • Average filter in $y$-direction
    horse_128
    Original     		horse_128
    3 x 1     		horse_128
    5 x 1     		horse_128
    7 x 1     		horse_128
    21 x 1
  • Average filter in $x$-direction
    horse_128
    Original     		horse_128
    1 x 3     		horse_128
    1 x 5     		horse_128
    1 x 7     		horse_128
    1 x 21

Filter Kernels

  • What is the effect of this filter kernel?
    $\frac{1}{256} \begin{bmatrix} 1 & 4 & 6 & 4 & 1\\ 4 & 16 & 24 & 16& 4\\ 6 & 24 & 36 & 24& 6\\ 4 & 16 & 24 & 16& 4\\ 1 & 4 & 6 & 4 & 1\\ \end{bmatrix}$
  • Answer:
    • Gaussian smoothing filter:
      $\mathrm{b}[x,y] = \exp\left( - \frac{x^2 + \,y^2}{2 \, \sigma^2}\right)$
      and normalization of the values so that the sum is equal to 1 ist
    • Low-pass filter (also a Gaussian in the frequency domain)
    • Used here: Integer approximation by binomial coefficients
    • Small version: $\frac{1}{16} \begin{bmatrix} 1 & 2 & 1\\ 2 & 4 & 2\\ 1 & 2 & 1 \end{bmatrix}$

Filter Kernels

  • Filtering with binomial filter kernels of different sizes:
    horse_128
    Original     		horse_128
    3 x 3     		horse_128
    5 x 5     		horse_128
    7 x 7     		horse_128
    21 x 21

Filter Kernels

  • What is the effect of this filter kernel?
    $\frac{1}{8}\begin{bmatrix}1 & 0 & -1\\ 2 & 0 & -2\\ 1 & 0& -1 \end{bmatrix}$
  • Answer:
    • Edge filter in $x$-direction
      horse_128
      Original       		horse_128
      x-direction
      $\frac{1}{8}\begin{bmatrix}1 & 0 & -1\\ 2 & 0 & -2\\ 1 & 0& -1 \end{bmatrix}$
      		horse_128
      y-direction
      $\frac{1}{8}\begin{bmatrix}1 & 2 & 1\\ 0 & 0 & 0\\ -1 & -2& -1 \end{bmatrix}$

Filter Kernels

  • What is the effect of this filter kernel?
    $\begin{bmatrix}0 & -1 & 0\\ -1 & 4 & -1\\ 0 & -1& 0 \end{bmatrix}$
  • Answer:
    • Laplace filter (2nd order derivative)
    • Edge filter in $x$-direction and $y$-direction

Separable Filters

Separable Filters

  • For a separable filter kernel, the convolution can be split into several convolutions, i.e.
    $\mathrm{f}[x,y] = \mathrm{a}[x,y] \ast \mathrm{b}[x,y] = \left(\mathrm{a}[x,y] \ast \mathrm{b}_1[x,y]\right) \ast \mathrm{b}_2[x,y]$
  • Here, the separated filter kernels $\mathrm{b}_1[x,y]$ and $\mathrm{b}_2[x,y]$ are smaller and therefore faster to execute
  • Most of the filter kernels studied so far are x/y-separable, e.g.
    $\frac{1}{9}\begin{bmatrix}1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1& 1 \end{bmatrix} = \frac{1}{3}\begin{bmatrix}1\\ 1\\ 1 \end{bmatrix} \,\, \ast \,\, \frac{1}{3}\begin{bmatrix}1 & 1 & 1\\ \end{bmatrix} $
  • For a $K \times K$ sized filter kernel, the computational cost is reduced from $K^2$ to $2\, K$ by the separation

Separable Filters

  • In general, the combined filter kernel of size $K \times K$ results from the x/y-separated kernels of size $K$ by
    $ \frac{1}{w_y}\begin{bmatrix}y_1\\ y_2\\ \vdots\\ y_K \end{bmatrix} \,\, \ast \,\, \frac{1}{w_x}\begin{bmatrix}x_1 & x_2 & \dots & x_K\\ \end{bmatrix} = \frac{1}{w_y w_x} \begin{bmatrix}y_1 x_1 & y_1 x_2& \dots & y_1 x_K\\ y_2 x_1 & y_2 x_2& \dots & y_2 x_K \\ \vdots & \vdots & \ddots & \vdots \\ y_K x_1 & y_K x_2&\dots & y_K x_K \end{bmatrix} $
  • How can this Gaussian filter be separated?
    $\frac{1}{16} \begin{bmatrix} 1 & 2 & 1\\ 2 & 4 & 2\\ 1 & 2 & 1 \end{bmatrix}$
  • Answer:
    $\frac{1}{16} \begin{bmatrix} 1 & 2 & 1\\ 2 & 4 & 2\\ 1 & 2 & 1 \end{bmatrix} = \frac{1}{4}\begin{bmatrix}1\\ 2\\ 1 \end{bmatrix} \,\, \ast \,\, \frac{1}{4}\begin{bmatrix}1 & 2 & 1\\ \end{bmatrix} $

Separable Filters

  • How can this filter, which is responsive to edges in the $x$-direction, be separated?
    $\frac{1}{8} \begin{bmatrix}1 & 0 & -1\\ 2 & 0 & -2\\ 1 & 0& -1 \end{bmatrix}$
  • Answer:
    $\frac{1}{8} \begin{bmatrix}1 & 0 & -1\\ 2 & 0 & -2\\ 1 & 0& -1 \end{bmatrix} = \frac{1}{4}\begin{bmatrix}1\\ 2\\ 1 \end{bmatrix} \,\, \ast \,\, \frac{1}{2}\begin{bmatrix}1 & 0 & -1\\ \end{bmatrix} $
  • Interesting. It is apparently a combination of a Gaussian filter in the $y$-direction and an edge filter in the $x$-direction