



\subsubsection*{Sampling and interpolation}

Digital images, only defined for  $(n_1,n_2)\in\relative^2$, will be denoted by $\bu(n_1,n_2)$.
 The  sampled image
 $\bu=\SA_1 u$ is  defined on $\relative^2$ by \begin{equation} \bu(n_1,n_2)=(\SA_1u) (n_1,n_2)=:u(n_1,
n_2); \label{defsampling}\end{equation}

\subsubsection{The practical Shannon interpolation: zero-padding}   Let $a>0$ and consider a function $u$ from $[0,a]^2$
to $\real$ such that $u(x+a,y+a)=u(x,y)$. Fix an integer $N$, and consider the $N^2$ samples of $u$, $\bu_{k,l}=(\SA
u)\left(\frac{ka}{N},\frac{la}{N}\right)$ on $[0,a]^2$.

\begin{definition}\label{defDFT} The  discrete Fourier transform  (DFT) of  the $N^2$ samples
 $u=(u_{k,l})_{k,l=0,1,\dots, N-1}$ is  the double sequence of
discrete Fourier coefficients for $m,n \in \{-\frac N 2,...,\frac N 2 -1\}$ defined by
\begin{equation}
\label{TFD2} DFT(u)_{m,n}=
\tilde{u}_{m,n}=\frac{1}{N^2}\sum_{k=0}^{N\!-\!1}\sum_{l=0}^{N\!-\!1}u_{k,l}\omega_N^{-mk}\omega_N^{-nl },
\end{equation}
where $\omega_N=: e^{\frac{2i\pi}N}$ is the first $N$-root of 1.
\end{definition}

\begin{proposition}\label{inverseDFT}
Consider the trigonometric polynomial
\begin{equation}\label{definitionofIonasquare}I\bu(x,y)=\sum_{m,n=-\frac
N2}^{\frac N2-1}\tilde u_{m,n}\exp(\frac{2i\pi mx}{a})\exp(\frac{2i\pi ny}{a}).
\end{equation}
 Then its coefficients
$\tilde u_{m,n}$ are the only complex numbers such that for every  $k, l \in \{0, ..., N\!-\!1\}$,
$I\bu\left(\frac{ka}{N},\frac{la}{N}\right)=\bu\left(\frac{ka}{N},\frac{la}{N}\right)$. In consequence, the discrete
inverse transform of the DFT $\bu\to \tilde u$ is nothing but the calculation of the value of the polynomial at the
samples $(\frac {ka}N, \frac {la}N)$, $0\leq k,l\leq N\!-\!1$. In other terms, setting $\tilde{u}=DFT(\bu)$, the
inverse transform $DFT^{-1}$ is given by
$$\bu(k,l)=\sum_{-\frac N2}^{\frac N2-1}\sum_{-\frac N2}^{\frac
N2-1}\tilde \bu_{m,n}\omega_N^{km+ln},$$ for every $k,l =0,1,\dots N-1$.
\end{proposition}


\begin{exercise}  Recall that $\omega_N=\exp\left(\frac{2i\pi}{N}\right)$,  $N$-th root of 1. Show that
$\sum_{k=0}^{N\!-\!1}\omega_N^k=0$, and that $\sum_{k=0}^{N\!-\!1}\omega_N^{kl}=0$ for $l\neq 0$ modulo $N$ and finally
that for every $k_0$, $\sum_{k=k_0}^{k_0+N\!-\!1}\omega_N^{kl}=0$ for all $l\neq 0$ modulo $N$. Using these relation
show the above proposition, namely that $DFT(DFT^{-1})=Id$.\finex
\end{exercise}


\begin{proposition}\label{mainsamplinginterpolationframework} If $u(x,y)$ is a $a$-periodic  band-limited function, then it is a trigonometric polynomial.  If
 its highest degree is
$\frac N2-1$, with $N$ even, then its coefficients  $\tilde u_{m,n}$ are obtained by DFT from the samples
$\bu(k,l)=u(\frac{ka}N, \frac{la}N)$.
 In consequence for such functions we have $I\SA u=u$.
\end{proposition}

\subsubsection*{Zoom in by zero-padding} Let $(u_{k,l})$ be a digital image and define its zoomed version
$\left(v_{i,j}\right)_{i,j=0,\;...,\; 2N\!-\!1}$ as the inverse discrete Fourier transform of   $\tilde v_{i,j}$
defined for $i,j=-N,\;...,\;N\!-\!1$ by

\begin{equation}
\label{TFDzoom2}
 \tilde{v}_{m,n} = \tilde u_{m,n} \hbox{  if  } -\frac N2\leq m, n\leq \frac N2-1, \;\; \tilde
v_{m,n}=0
 \hbox {  otherwise}.
\end{equation}


\begin{proposition} \index{zoom discret par Fourier} \label{zeropadding}
The image $v$ whose Discrete Fourier Transform  is given by (\ref{TFDzoom2}) satisfies $v_{2k,2l}=u_{k,l}$, for $k,l=0,
..., N\!-\!1$.
\end{proposition}


\subsubsection{Gaussians}
  $G_\sigma$
denotes the  convolution operator on $\RR^2$  with  the gauss kernel $G_\sigma(x_1,x_2)=\frac
1{2\pi(\sigma)^2}e^{-\frac{x_1^2+x_2^2}{2(\sigma)^2}}$, namely $G_\sigma u(x,y)=: (G_\sigma \ast u)(x,y).$
\begin{equation}
\label{continuoussemigroupproperty}G_{\sigma} G_{\beta}= G_{\sqrt{\sigma^2+ \beta^2}}.\end{equation}

  \begin{equation}\label{commutationconvolutionzoomcontinus}G_\sigma  H_\gamma u=
H_\gamma G_{\sigma\gamma}  u.\end{equation}

\begin{definition}\label{definitiondiscretegaussianconvolution}
The {\bf discrete gaussian convolution} applied to a digital image $\bu$ is defined as a digital operator by
\begin{equation}\label{defGdelta} \bG_\delta \bu= : \SA_1 G_\delta I\bu.\end{equation}
\end{definition}

 \begin{proposition} This definition maintains the gaussian semi-group property,
\begin{equation}\label{discretesemigroupproperty}\bG_{\delta} \bG_{\beta}= \bG_{\sqrt{\delta^2+ \beta^2}}.\end{equation}
\end{proposition}

\begin{proposition}
 For every $\sigma$  larger than 0.8 and every continuous and bounded image $u_0$, the gaussian blurred image $G_\sigma
 u_0$ is well sampled, namely $I\bS_1G_\sigma u_0=G_\sigma u_0$.
\end{proposition}




\subsubsection{Discrete sampling\label{discretesetting}}

\begin{itemize}
\item  If $\bu$ is digital and therefore only defined on  $\relative^2$ and if $\delta$ is an integer, then one can
define any sub- or over-sampling operations on $\bu$. But this requires  interpolating $\bu$ first.   Thus we define a
{\it digital subsampling operator} by
\begin{equation}\label{defdiscretesampling}\SAD_\delta \bu=: \SA_\delta I\bu.\end{equation}   Notice  that
  $\SAD_\delta$  is a
discrete filter which can be interpreted as a {\rm re-sampling} operator.


\item Zooming in by oversampling. For every $\gamma\leq 1,$
\begin{equation}\label{commutationinterpolationsampling}
I\SAD_\gamma \bu=H_\gamma I\bu.\end{equation}


\item Corollary: If $\gamma\leq 1$, then \begin{equation}\label{compositionofsampling}
\SAD_\beta\SAD_\gamma=\SAD_{\beta\gamma}.\end{equation}


\item a discrete commutation formula :  Assume $\bu$ is a digital image. Then
  for $\gamma<1$,
\begin{equation}\label{discretecommutation}\bG_\beta \SAD_\gamma \bu=\SAD_\gamma \bG_{\beta\gamma}\bu.\end{equation}

\end{itemize}
